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
```

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

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

## 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テーブル。以下の通り表示され方は違えど同じ[^3]

```
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テーブルはデフォルトで空。
これら以外のテーブルを手動で追加することも可能で、さらにテーブルを選択するときの条件を設定できる。
指定できる条件は以下の4つ

- 送信元と送信先のIPアドレス
- パケットを受け取ったinterface
- TOS
- netfilterによるタグ付け(Fwmark)

送信先のIPアドレスとTOS以外は単独のrouteでは指定できない。


---
だけど、ネットワーク屋さんでない限り使わなそうな気がする。
結局のところ、普通に今まで通りnetstat -rやrouteコマンドで見る情報で十分ということになる。

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

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

## その他
ググると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](https://amzn.to/2JQof2P)を読んだ[^1]。これ、2005年の本でかなり古いけどめっちゃ勉強になった。流石に13年前だと変わってるところもあると思うけど、多分ほとんど今も有効。というかこの本にすでにnet-toolsは古いからiproute2使え、って書いてるのに13年たってもまだnetstatやらrouteやらifconfigやら使っていて残念な気持ちになった[^2]。これからは積極的にipコマンド使っていこうと思う。

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

[^1]: 全部は読んでない。とりあえず知りたかったLookup周りだけ読んだ。
[^2]: まぁネットワーク周りの設定とか結構失敗したらクリティカルな作業になることが多いから、できるだけ今まで通りのコマンド使いたい気持ちは分かる
[^3]: mainテーブルであることを強調するためにip route show table mainなんて長いコマンドを使っているが、ip routeで同じ結果が得られる。
[^5]: [このメソッド](https://github.com/torvalds/linux/blob/v4.17/net/ipv4/fib_trie.c#L1124)の[ここ](https://github.com/torvalds/linux/blob/v4.17/net/ipv4/fib_trie.c#L1153)で同じ優先順位のrouteを見つけて、[それの手前にinsertしてる](https://github.com/torvalds/linux/blob/v4.17/net/ipv4/fib_trie.c#L1232)っぽい。
[^6]: TOSって知らなかったんだけど、読んだはずのマスタリングTCP/IP入門編にちゃんと書いてあってとても残念な気持ちになった。あと、このIPv4ヘッダのビット使わないのもったいないから当初の意図とは別の目的で使いまわそう、という提案がなされているらしく、[Wikipediaのページ](https://en.wikipedia.org/wiki/Type_of_service)の一文目から「別の方法で5つのRFCに定義されている」(訳)と書かれていて結構インパクトある。
[^7]: 実際に動かして確認しようとしたけど、環境作るのくっそめんどくさくてやめた。