Linux
Network
Routing

Linuxはどのようにしてパケットのroute選択をするのか

TL;DR

  1. マッチするrouteのうち一番specificな(netmaskが長い)routeを選択する
  2. netmaskの長さが同じrouteが複数ある場合、metricが小さいrouteを選択する
  3. metricが同じrouteが複数あった場合、最後に追加したrouteを選択する

例えば以下のサブネットのrouteがあった時、10.1.1.2のrouteは2になる。

1. 10.0.0.0/8  metric 0
2. 10.1.0.0/16 metric 100
3. 10.1.0.0/16 metric 101

詳細

大体は↑に書いてあるルールの通りで問題ないと思うけど、せっかく勉強したので詳細も書いておく。

Policy Routing

LinuxにはPolicy Routingというルーティングテーブルを複数持てる機能がある。デフォルトでは以下の3つ。

root@cff5ecbc4f63:/# ip rule
0:  from all lookup local
32766:  from all lookup main
32767:  from all lookup default

最初の列の0, 32766, 32767はpriorityで、小さい方から評価される。で、普段netstat -rとかrouteコマンドで表示されるのはmainテーブル。以下の通り表示され方は違えど同じ1

root@cff5ecbc4f63:/# route
Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
default         172.17.0.1      0.0.0.0         UG    0      0        0 eth0
172.17.0.0      0.0.0.0         255.255.0.0     U     0      0        0 eth0

root@cff5ecbc4f63:/# ip route show table main
default via 172.17.0.1 dev eth0
172.17.0.0/16 dev eth0 proto kernel scope link src 172.17.0.2

localテーブルはブロードキャストや自分自身に対するrouteなので、普段は気にしなくて良いことが多いだろう

root@cff5ecbc4f63:/# ip route show table local
broadcast 127.0.0.0 dev lo proto kernel scope link src 127.0.0.1
local 127.0.0.0/8 dev lo proto kernel scope host src 127.0.0.1
local 127.0.0.1 dev lo proto kernel scope host src 127.0.0.1
broadcast 127.255.255.255 dev lo proto kernel scope link src 127.0.0.1
broadcast 172.17.0.0 dev eth0 proto kernel scope link src 172.17.0.2
local 172.17.0.2 dev eth0 proto kernel scope host src 172.17.0.2
broadcast 172.17.255.255 dev eth0 proto kernel scope link src 172.17.0.2

で、defaultテーブルはデフォルトで空。
これら以外のテーブルを手動で追加することも可能だけど、ネットワーク屋さんでない限り使わなそうな気がする。
結局のところ、普通に今まで通りnetstat -rやrouteコマンドで見る情報で十分ということになる。

キャッシュ

↑のテーブルを参照する前に、キャッシュを参照する。キャッシュでヒットしなければlocal, mainとテーブルを参照することになる。

TOS

テーブルごとの選択の仕方は大体TL;DR通りなのだけれど、省略したところがある。実際はmetricチェックの前にTOS(Type of Service)のチェックが入る。TOSの設定をしていないrouteとTOSを設定していてそのパケットのTOSと一致するrouteがあれば、設定している方が優先される。
このTOS、IPv4ヘッダのフィールドの一つでパケットの優先順位などを設定できるらしい。けれど、マスタリングTCP/IP入門編第5版によると現在ほとんど使われていないらしい。これに頼ったroute設定なんて使われてなさそうなので多分気にしなくて良いと思う。2

netmask, metric, tosが同じ場合

参考にした本には、「単純に先に見つけた方。これはrouteを追加する順番が影響することを意味する」的なことが書いてあったんだけど、後勝ちなのか先勝ちなのか書いてなかった。
せっかくなのでLinuxのソースコードを読んで見ると、優先順位の高い順のrouteのリストにrouteを追加する時に、同じ優先順位のrouteの手前に追加していたので、後勝ちらしい3。動作確認はしてないから読み間違えてたらごめんなさい。4
また、じゃあルーティングテーブル表示した時の順番的に上が優先なのか下が優先なのか気になったけど、これって結局表示するアプリケーションの実装によるのでそれぞれソースコード読む必要があるしこれを調べることにどれほど意味があるんだみたいな気持ちになって力尽きた。

その他

ググるとAdministrative Distanceと言う単語が出てくるけど、Ciscoのルータとかで使われてる概念らしく、少なくともLinuxのカーネルとは関係なさそうだった。最初気づかなくて混乱した。

まとめ

書いたことをまとめると、

  1. キャッシュを参照する
  2. キャッシュになければlocalテーブルを参照する
  3. localテーブルになければ手動で追加したテーブルを(あれば)参照する
  4. 手動で追加したテーブルになければmainテーブルを参照する
  5. mainテーブルになければdefaultテーブルを参照する

で、テーブルごとのアルゴリズムが

  1. マッチするrouteのうち一番specificな(netmaskが長い)routeを選択する
  2. netmaskの長さが同じrouteが複数ある場合、TOSが設定されていてマッチするrouteを選択する。
  3. TOSが同じrouteが複数ある場合、metricが小さいrouteを選択する
  4. metricが同じrouteが複数あった場合、最後に追加したrouteを選択する

と言う感じ。

参考にした本

仕事でroute選択周りでハマったので調べてたんだけど、ネットをさまよってもまとまった情報がないし何が正しいのかわからんかった。で、そこらへんがちゃんと書いてありそうな
Understanding Linux Network Internalsを読んだ5。これ、2005年の本でかなり古いけどめっちゃ勉強になった。流石に13年前だと変わってるところもあると思うけど、多分ほとんど今も有効。というかこの本にすでにnet-toolsは古いからiproute2使え、って書いてるのに13年たってもまだnetstatやらrouteやらifconfigやら使っていて残念な気持ちになった6。これからは積極的にipコマンド使っていこうと思う。

あと、これは愚痴なんだけど、この本に「metricって言葉は2つの意味で使われるから注意な」的なことが書いてあるんだけど、ルーティングテーブルを表示した時に出てくるmetricはその2つの意味のどちらでもなく第3の意味で使われていてだいぶハマった。この本ではこのルーティングテーブルのmetricを指す言葉としてpriorityという言葉が使われているっぽい。ソースコード的にはfib_priorityと言う変数名。


  1. mainテーブルであることを強調するためにip route show table mainなんて長いコマンドを使っているが、ip routeで同じ結果が得られる。 

  2. TOSって知らなかったんだけど、読んだはずのマスタリングTCP/IP入門編にちゃんと書いてあってとても残念な気持ちになった。あと、このIPv4ヘッダのビット使わないのもったいないから当初の意図とは別の目的で使いまわそう、という提案がなされているらしく、Wikipediaのページの一文目から「別の方法で5つのRFCに定義されている」(訳)と書かれていて結構インパクトある。 

  3. https://github.com/torvalds/linux/blob/v4.17/net/ipv4/fib_trie.c#L1124ここで同じ優先順位のrouteを見つけて、それの手前にinsertしてるっぽい。 

  4. 実際に動かして確認しようとしたけど、環境作るのくっそめんどくさくてやめた。 

  5. 全部は読んでない。とりあえず知りたかったLookup周りだけ読んだ。 

  6. まぁネットワーク周りの設定とか結構失敗したらクリティカルな作業になることが多いから、できるだけ今まで通りのコマンド使いたい気持ちは分かる