panda's tech note

Poptrie

IPルーティングとLongest Prefix Matching (最長一致)

IPルーティングは,中継器であるルータが宛先アドレスを見て宛先に近いルータにパケットを転送することで行われます。ルータはすべての宛先アドレスへの転送先をひとつひとつ持っているわけではなく,プレフィックスごとに転送先を持っています。プレフィックスと転送先(Next hop)の組み合わせを経路と呼びます。また,ルータが転送先決定に使用する経路の一覧を経路表(ルーティングテーブル)と呼びます。ある宛先アドレスが複数のプレフィックスに一致する場合は,プレフィックス長が最も長い経路を選択します。これをLongest Prefix Matching(最長一致)規則と呼びます。

なお,他の全ての経路にマッチしなかった場合に使用される経路はデフォルトルートと呼ばれますが,これは0.0.0.0/0をプレフィックスとした経路のことを意味します。

例えば,以下の5つのエントリを持ったルーティングテーブルを考えます。Next hopは転送先のルータのIPアドレスが入っていますが,4番目の経路はこのルータのローカルサブネットlink #1198.51.100.0/28)への転送を意味しています。このとき,宛先203.0.113.1に対する経路は,1〜4のどの経路にもマッチせず,デフォルトルートである5番目の経路にマッチするため,パケットを198.51.100.2に転送します。宛先192.0.2.252に対する経路は,2番目と5番目の経路にマッチしますが,最長一致規則により,経路長が最も長い2番目の経路が選択され,パケットを198.51.100.3に転送します。

ID プレフィックス Next hop
1 192.0.2.0/25 198.51.100.2
2 192.0.2.128/25 198.51.100.3
3 198.51.100.0/24 198.51.100.3
4 198.51.100.0/28 link #1
5 0.0.0.0/0 198.51.100.2