ロンゲストプレフィックスマッチと高速転送

最長一致が必要になる理由

ルータが受け取ったパケットの宛先 IP アドレスは、転送テーブル（FIB: Forwarding Information Base）の複数の経路に同時に一致しうります。たとえば 10.0.0.0/8、10.1.0.0/16、10.1.2.0/24 が登録されているとき、宛先 10.1.2.5 は3つすべてに一致します。このとき選ぶべきは最もプレフィックス長が長い（=最も具体的な）10.1.2.0/24 です。これが**ロンゲストプレフィックスマッチ（最長一致）**です。

なぜこの規則なのか。CIDR によるアドレス集約では、広い範囲を1本の集約経路で表しつつ、その内側の一部だけ別経路へ向ける、という運用が日常的に起きます。最長一致があるからこそ「デフォルトは集約経路、例外だけ具体経路」という重ね書きが成立します。0.0.0.0/0（デフォルトルート）はプレフィックス長0なので、他のどの経路にも負け、文字どおり最後の受け皿になります。

素朴な実装の限界

最も単純な実装は、FIB の全エントリを走査し、一致するものの中から最長のものを選ぶ線形探索です。エントリ数を N とすると1パケットあたり O(N) になります。コアルータの FIB は IPv4 全経路で100万エントリ規模に達するため、これでは毎秒数億パケットを処理する要求にまったく届きません。

プレフィックス長ごとにハッシュ表を持ち、長い方から順に引く方法もあります。IPv4 なら長さ0から32まで最大33回のハッシュ参照で済みますが、最長一致を確定するには「短い長さで一致しても、より長い一致がないか確認する」必要があり、単純な完全一致ハッシュとは設計が変わります。実用解として広く使われてきたのが、次のトライ木と TCAM です。

トライ木による検索

**トライ木（trie）**は、プレフィックスのビット列を木の経路として表すデータ構造です。アドレスを最上位ビットから1ビットずつたどり、0なら左、1なら右へ進みます。経路上に出現する各プレフィックスのノードへ次ホップを記録しておき、たどる途中で出会った最も深いノードが最長一致になります。

素朴な1ビットトライはアドレス幅ぶんの深さ（IPv4 で最大32段）を持ち、メモリと探索段数が増えます。これを圧縮したのが **Patricia トライ（PATRICIA）**です。

1ビットトライ:            Patricia（分岐のないノードを圧縮）:
  分岐のない中間ノードを       各ノードに「次に見るべきビット位置」を持たせ、
  延々とたどる               枝分かれする箇所だけをノードにする

Patricia では、子が1つしかない中間ノードを畳み込み、各ノードに「次に検査するビット位置（skip 値）」を格納します。これにより木の深さは「実際に分岐する回数」に縮み、探索段数が実プレフィックス数に依存する形になります。さらに転送特化で発展させたのが **LC-trie（Level-Compressed trie）**で、密に埋まった部分木を一度に複数ビット読む多分岐ノードへ変換し、段数をさらに減らします。

実装上の重要点は、たどる途中で見つかった一致を逐次更新することです。深いノードへ進むほど長いプレフィックスなので、最後に出会った一致ノードを保持すれば、それが自動的に最長一致になります。木構造の更新（経路の追加・削除）も局所的なノード操作で済み、頻繁な経路変動に追従しやすい点もソフトウェア FIB に向いています。

TCAM によるハードウェア検索

ソフトウェアのトライがアドレス幅に比例する段数を要するのに対し、ハードウェアではそれを1サイクルに圧縮します。鍵が **TCAM（Ternary Content-Addressable Memory）**です。

通常のメモリはアドレスを与えて中身を読みますが、CAM は逆に中身（キー）を与えて、それが格納されているアドレスを返す連想メモリです。TCAM はさらにビットごとに 0／1／X（ドントケア）の3状態を持てます。この X が決定的で、プレフィックスの「マスクされた部分」をそのまま表現できます。10.1.2.0/24 は上位24ビットが 0／1、下位8ビットがすべて X として1エントリに格納されます。

検索時、TCAM は全エントリと入力キーを同時に並列照合します。各エントリは「自分の非 X ビットがキーと一致するか」を1サイクルで判定し、一致したエントリの行をすべて立てます。

TCAM で最長一致を保証する仕組み

並列照合だけでは「複数のエントリが一致した」ところまでしか分かりません。最長一致を得るには、一致した行の中から最もプレフィックス長が長いものを1つ選ぶ必要があります。TCAM はこれを2段で解決します。

第一に、エントリを プレフィックス長の降順で物理アドレスへ配置します。長いプレフィックスほど若いアドレスに置く、という規約です。第二に、一致行のうち最小アドレスを返す優先順位エンコーダをハードウェアで持ちます。降順配置と最小アドレス選択を組み合わせると、複数一致のうち最長のものが必ず選ばれます。返ったインデックスで隣接 SRAM を引き、次ホップやインターフェースを得て転送します。

TCAM のもう一つの代償は消費電力です。検索のたびに全エントリのセルを駆動するため、容量に比例して電力と発熱が増えます。FIB が大きいハイエンドルータほど TCAM の容量・電力・コストが設計の制約になり、近年はルーティングプロトコルが生成する経路規模に対し、アルゴリズム的なトライ系（多くは専用ネットワークプロセッサ上）との併用や使い分けが進んでいます。

まとめ

最長一致は、集約経路と具体経路を矛盾なく共存させるための転送規則であり、その実装が転送速度を決めます。ソフトウェアは Patricia／LC-trie で探索段数をアドレス幅に抑え、ハードウェアは TCAM のドントケアと優先順位エンコーダで1サイクル並列照合を実現します。どちらも「最も具体的な経路を選ぶ」という同じ意味を、まったく異なる手段で達成している点が要諦です。経路計算の上流である最短経路アルゴリズムの数理とあわせて理解すると、制御プレーンが決めた経路がデータプレーンでどう高速に引かれるか、という全体像が一本の線でつながります。