ルーティングテーブル
IPv4のルーティングテーブルに関するメモ
FIBはハッシュ構造をしている(*1)。
ルーティングエントリは宛先のプレフィクス長(サブネットマスク長)毎に分けて管理される。各プレフィクス長(0〜32)毎にZone(struct fn_zone)が存在し、プレフィクス長(Zone)毎にハッシュテーブル(fz_hash)を持つ。宛先のプレフィクス長が同じルーティングエントリは、同じハッシュ(fz_hash)の中につながれることになる。
ハッシュの各エントリにはルーティングエントリの実体であるstruct fib_nodeがつながれる。ハッシュのキーはルーティングエントリの宛先IPアドレスを元に算出されている。
各Zoneはstruct fn_hashのfn_zones[]からポイントされる。fn_zones[0],[1],...から順番にプレフィクス長0,1...のZoneがつながれる(*2)。また、Zoneはstruct fn_hashのfn_zone_listを先頭として、プレフィクスの長いZoneから順番にfz_nextでチェーンされている。ルーティングエントリの検索時は、このfn_zone_listをたどってプレフィクス長の長いエントリから検索されていくので、LongestMatch(*3)をすることになる。
struct fib_nodeのfn_keyにはルーティングエントリの宛先が格納されている。Gatewayなどの情報はここからさらにfib_aliasなどの情報をたどる必要がある。
(*1) 以前はハッシュ構造のみだったが、どこかのバージョンからfib_trie.cが追加されて CONFIG_IP_FIB_TRIEを定義するとTree構造にもなるようになった。tb_dataの先がTree構造になるみたい。
(*2) fn_zones[0]はプレフィクス長0のZoneなのでデフォルトルート用となる。
(*3) 宛先が192.168.10.0/24と192.168.0.0/16のエントリそれぞれある状態で、DstIP192.168.10.1で検索したら192.168.10.0/24の方のエントリにヒットする。
struct fib_infoに送信I/FやGatewayの情報が格納されている。fib_nh[]配列にGatewayに関する情報が格納される。fib_nh[]は通常1エントリのみとなる。マルチパス(ある宛先に対して複数のGatewayを設定してロードバランスを行う)を行う場合は複数エントリが存在する。nh_devに送信インタフェースのnet_device構造体へのポインタが格納されており、nh_gwにはGatewayのIPアドレスが格納されている。
[捕捉 - CONFIG_IP_MULTIPLE_TABLES]
ルールはstruct fib_ruleで管理されfib_rulesにチェーンされている。各struct fib_ruleにはパケットの検索条件が格納されている。経路検索時にはfib_rulesに連なっているルールを順番にチェックして行き、ルールにマッチしたパケットは対応するFIB(.r_table)で検索に行う。FIBを検索して該当エントリがなければ次のルールを調べるという動作を繰り返す。このため、ポリシーを設定したstruct fib_ruleとマッチした時に使用するFIBを登録しておけばポリシールーティングを行える。
デフォルトでは、local_rule,main_rule,default_ruleの3つのルールが登録されている。これらのルールには特に条件は設定されていないので、全パケットが該当する。このため、経路検索時はまずip_fib_local_tableが検索され、該当エントリがなければip_fib_main_tableが検索されて行くという動作になる(*1)。
(*1) ip_fib_main_tableでエントリがない場合、default_ruleでもう一回ip_fib_main_tableを見にいってしまいそうだが、まだ調べていない。
ルーティングキャッシュの構造を図4に示す。ルーティングキャッシュはハッシュ構造になっている。struct rt_hash_table[]がハッシュテーブルになっており、各エントリからstruct rtableのリストが連なっている。rtableキャッシュはパケットのフロー(SrcIP,DstIP,受信I/F,送信I/F,TOSの組み合わせ)単位に作成される。このため、例えば宛先が異なる2つのパケットに対しては同じルーティングエントリを使用するような場合でも、フロー(DstIP)が異なるので別々にrtableが作成されることになる。
rtableのrt_gatewayにはGatewayのIPアドレスが格納されている。他にもrtable内にはプロトコル非依存の宛先に関する情報struct dst_entryが格納されている。struct dst_entryには、通信時に使用するARPエントリ(IPv4の場合)へのポインタや、送受信ルーチンへのポインタなどが格納されている。
ルーティングキャッシュの内容は/proc/net/rt_cacheで確認できる。コマンドだと、netstat -rnC。"C"がないとFIBの方が表示される。
fn_hash_lookup()
ip_route_input_slow()
fib_magic()
--------------------------------------
自足経路／ネットワーク経路の登録
SIOCSIFADDR
inet_ioctl()
devinet_ioctl()
struct in_ifaddr ifaを作成
inet_set_ifa()
inet_insert_ifa()
ifaをデバイスのチェーンにつなぐ
rtmsg_ifa(RTM_NEWADDR, ifa)
notifier_call_chain(&inetaddr_chain,
NETDEV_UP, ifa)
inetaddr_chainに登録されている
notifierのハンドラをコール。
notifierは初期化時(ip_fib_init())に
register_inetaddr_notifier()
で一つ登録しているだけ。
ハンドラはfib_inetaddr_event()。
1. 概要
Linuxではルーティングテーブルのことをフォワーディングインフォメーションベース(FIB)と呼ぶ(以下でルーティングテーブルと呼んだ場合はFIBのことを指す)。また、パケットの送受信で参照されたルーティングエントリはルートキャッシュにキャッシュして次から素早くルーティングエントリを検索できるようになっている。2. フォワーディングインフォメーションベース
2.1 FIBの構造
FIBの構造を図1に示す。
図1 FIBの構造
FIBはハッシュ構造をしている(*1)。
ルーティングエントリは宛先のプレフィクス長(サブネットマスク長)毎に分けて管理される。各プレフィクス長(0〜32)毎にZone(struct fn_zone)が存在し、プレフィクス長(Zone)毎にハッシュテーブル(fz_hash)を持つ。宛先のプレフィクス長が同じルーティングエントリは、同じハッシュ(fz_hash)の中につながれることになる。
ハッシュの各エントリにはルーティングエントリの実体であるstruct fib_nodeがつながれる。ハッシュのキーはルーティングエントリの宛先IPアドレスを元に算出されている。
各Zoneはstruct fn_hashのfn_zones[]からポイントされる。fn_zones[0],[1],...から順番にプレフィクス長0,1...のZoneがつながれる(*2)。また、Zoneはstruct fn_hashのfn_zone_listを先頭として、プレフィクスの長いZoneから順番にfz_nextでチェーンされている。ルーティングエントリの検索時は、このfn_zone_listをたどってプレフィクス長の長いエントリから検索されていくので、LongestMatch(*3)をすることになる。
struct fib_nodeのfn_keyにはルーティングエントリの宛先が格納されている。Gatewayなどの情報はここからさらにfib_aliasなどの情報をたどる必要がある。
(*1) 以前はハッシュ構造のみだったが、どこかのバージョンからfib_trie.cが追加されて CONFIG_IP_FIB_TRIEを定義するとTree構造にもなるようになった。tb_dataの先がTree構造になるみたい。
(*2) fn_zones[0]はプレフィクス長0のZoneなのでデフォルトルート用となる。
(*3) 宛先が192.168.10.0/24と192.168.0.0/16のエントリそれぞれある状態で、DstIP192.168.10.1で検索したら192.168.10.0/24の方のエントリにヒットする。
表1 struct fib_tableのフィールド(一部)
|
フィールド |
説明 |
|---|---|
|
tb_lookup |
エントリの検索/エントリの追加、削除を行うためのハンドラへのポインタ。 FIBがハッシュ形式の場合は以下のように設定される。(fib_hash_init()) .tb_lookup = fn_hash_lookup .tb_insert = fn_hash_insert .tb_delete = fn_hash_delete .tb_flush = fn_hash_flush .tb_select_default = fn_hash_select_default .tb_dump = fn_hash_dump |
|
tb_insert |
|
|
tb_delete |
|
|
tb_dump |
|
|
tb_flush |
|
|
tb_select_default |
|
|
tb_data |
ハッシュデータへのポインタ。CONFIG_IP_FIB_TRIEの定義があると、Tree構造へのポインタになる模様。 |
2.2 ルーティングエントリ(fib_node)の構造
fib_nodeの構造を図2に示す。fib_nodeのfn_keyにはルーティングエントリの宛先アドレスが格納されており、エントリ検索の際に参照される。struct fib_infoに送信I/FやGatewayの情報が格納されている。fib_nh[]配列にGatewayに関する情報が格納される。fib_nh[]は通常1エントリのみとなる。マルチパス(ある宛先に対して複数のGatewayを設定してロードバランスを行う)を行う場合は複数エントリが存在する。nh_devに送信インタフェースのnet_device構造体へのポインタが格納されており、nh_gwにはGatewayのIPアドレスが格納されている。
図2 fib_nodeの構造
2.3 FIBの種類
FIB(struct fib_table)は用途に応じて複数存在している。通常は以下の2つのFIBが存在する。
表2 FIBの種類
|
FIB |
説明 |
|---|---|
| ip_fib_main_table |
通常のルーティングエントリが登録される。 netstat -rnで表示されているのもこのFIBのエントリ。 |
| ip_fib_local_table |
あて先がRTN_UNICAST以外(ローカルマシン上の転送経路、ブロードキャスト、マルチキャストを管理)の経路が登録される。 自システム宛の経路(10.0.0.1のアドレスを設定している場合は'Dst:10.0.0.1/32 -> I/F lo')などもここに登録される。 |
[捕捉 - CONFIG_IP_MULTIPLE_TABLES]
CONFIG_IP_MULTIPLE_TABLESを定義すると、 ip_fib_main_table,ip_fib_local_tableではなくfib_tables[]に複数のFIBが存在するようになる。
パケットのSrcIP,DstIP,TOSなどの値を使ってパケット種別に応じてFIBを使い分けることでポリシールーティングが行えるようになる。検索時にどのFIBを使用するかは「2.4ルール」を参照。
パケットのSrcIP,DstIP,TOSなどの値を使ってパケット種別に応じてFIBを使い分けることでポリシールーティングが行えるようになる。検索時にどのFIBを使用するかは「2.4ルール」を参照。
2.4 ルール
ルールにより、SrcIP,DstIP,TOSなどのパケット種別に応じて経路検索時に使用するFIBを分けることができる。これによりポリシールーティングを行うことができる。ルールはstruct fib_ruleで管理されfib_rulesにチェーンされている。各struct fib_ruleにはパケットの検索条件が格納されている。経路検索時にはfib_rulesに連なっているルールを順番にチェックして行き、ルールにマッチしたパケットは対応するFIB(.r_table)で検索に行う。FIBを検索して該当エントリがなければ次のルールを調べるという動作を繰り返す。このため、ポリシーを設定したstruct fib_ruleとマッチした時に使用するFIBを登録しておけばポリシールーティングを行える。
デフォルトでは、local_rule,main_rule,default_ruleの3つのルールが登録されている。これらのルールには特に条件は設定されていないので、全パケットが該当する。このため、経路検索時はまずip_fib_local_tableが検索され、該当エントリがなければip_fib_main_tableが検索されて行くという動作になる(*1)。
(*1) ip_fib_main_tableでエントリがない場合、default_ruleでもう一回ip_fib_main_tableを見にいってしまいそうだが、まだ調べていない。
図3 fib_ruleとFIB
3. ルーティングキャッシュ
FIBのルーティングエントリはルーティングキャッシュにキャッシュして使用する2段構造になっている。IP層からの経路検索の際はまずルーティングキャッシュが調べられ、なければFIBを検索する。FIB内にエントリが見つかった場合はルーティングキャッシュにキャッシュされる。ルーティングキャッシュの構造を図4に示す。ルーティングキャッシュはハッシュ構造になっている。struct rt_hash_table[]がハッシュテーブルになっており、各エントリからstruct rtableのリストが連なっている。rtableキャッシュはパケットのフロー(SrcIP,DstIP,受信I/F,送信I/F,TOSの組み合わせ)単位に作成される。このため、例えば宛先が異なる2つのパケットに対しては同じルーティングエントリを使用するような場合でも、フロー(DstIP)が異なるので別々にrtableが作成されることになる。
rtableのrt_gatewayにはGatewayのIPアドレスが格納されている。他にもrtable内にはプロトコル非依存の宛先に関する情報struct dst_entryが格納されている。struct dst_entryには、通信時に使用するARPエントリ(IPv4の場合)へのポインタや、送受信ルーチンへのポインタなどが格納されている。
ルーティングキャッシュの内容は/proc/net/rt_cacheで確認できる。コマンドだと、netstat -rnC。"C"がないとFIBの方が表示される。
図4 ルーティングキャッシュ
表3 struct dst_entryのフィールド(一部)
|
フィールド |
説明 |
|---|---|
|
neighbor |
使用するARPエントリへのポインタ |
|
input |
このエントリにヒットしたパケットに適用される受信ルーチン IPv4の場合、外部への経路にはip_forward()、自システム宛の経路にはip_local_deliver()が設定されている。dst_input()で呼び出される。 |
|
output |
このエントリにヒットしたパケットに適用される送信ルーチン ip_output()が設定されている。dst_output()で呼び出される。 |
4. 関連関数
4.1 FIB関連
fib_lookup()
ルーティングテーブル(fib)の検索を行なう。
fib_rulesに登録されているルールを順番にチェックして、パケットフローにマッチしたルールのFIBにtb->tb_lookup()で検索に行く。通常ルールはlocal_rule -> main_rule -> default_ruleの順にチェックされるので、FIBはまずip_fib_local_tableを検索してエントリがなければ、ip_fib_main_tableを検索することになる。
tb->tb_lookupには、FIBの検索ルーチンが登録されている。Hash型のFIBの場合はfn_hash_lookup()。
fib_rulesに登録されているルールを順番にチェックして、パケットフローにマッチしたルールのFIBにtb->tb_lookup()で検索に行く。通常ルールはlocal_rule -> main_rule -> default_ruleの順にチェックされるので、FIBはまずip_fib_local_tableを検索してエントリがなければ、ip_fib_main_tableを検索することになる。
tb->tb_lookupには、FIBの検索ルーチンが登録されている。Hash型のFIBの場合はfn_hash_lookup()。
fn_hash_lookup()
ルーティングテーブル(fib)検索の内部ルーチン。Hashからエントリを探す。
ネットマスクの大きい方のZoneから(fn_zone_list順)順に検索。
4.2 ルーティングキャッシュ関連
ip_route_input()
IPパケット受信時のルーティングキャッシュの検索ルーチン。
IP層の受信処理から呼ばれる。
IP層の受信処理から呼ばれる。
ルーティングキャッシュにエントリがなければ、ip_route_input_slow()でFIBに検索にいく。
ip_route_input_slow()
ルーティングキャッシュにエントリがなかった場合に、FIBを検索する。
FIBで見つかったエントリは、対応するstruct rtableを作成してルーティングキャッシュに入れる。
FIBで見つかったエントリは、対応するstruct rtableを作成してルーティングキャッシュに入れる。
4.3 その他
fib_inetaddr_event()
IP層用のNotifierハンドラ
アドレスが追加、削除された時に呼ばれる。
register_inetaddr_notifier()でinetaddr_chainに登録されている。
アドレスが追加、削除された時に呼ばれる。
register_inetaddr_notifier()でinetaddr_chainに登録されている。
アドレス追加(event = NETDEV_UP)時
fib_add_ifaddr(ifa)を呼び出して、自システム宛の経路(RTN_LOCAL)(*1)、ブロードキャストアドレス宛の経路(RTN_BROADCAST)(*2)、ネットワーク経路(RTN_UNICAST/RTN_LOCAL)(*3)を登録する。自システム宛の経路、ブロードキャストアドレス宛の経路はip_fib_local_tableのFIBに登録される。
(*1) 設定したアドレスが10.0.0.1/24の場合、10.0.0.1/32宛の経路が設定される。この経路は自システム宛(10.0.0.1)のパケットを受信するのに必要。経路をFIBからルーティングキャッシュにキャッシュする時(ip_route_input_slow())、RTN_LOCAL型の経路はrtableの受信ハンドラをip_local_deliver()に設定している。このため、10.0.0.1宛のパケットはip_local_deliver()に送られ自システムで受信される。
(*2) 10.0.0.255/32宛の経路が設定される。(*1)とおなじく、ブロードキャストパケットを受信するのに必要。
(*3) 10.0.0.0/24宛の経路が設定される。この経路は自システムが接続されたネットワーク(この場合、10.0.0.0/24)への送信を行なうのに使われる。
(*1) 設定したアドレスが10.0.0.1/24の場合、10.0.0.1/32宛の経路が設定される。この経路は自システム宛(10.0.0.1)のパケットを受信するのに必要。経路をFIBからルーティングキャッシュにキャッシュする時(ip_route_input_slow())、RTN_LOCAL型の経路はrtableの受信ハンドラをip_local_deliver()に設定している。このため、10.0.0.1宛のパケットはip_local_deliver()に送られ自システムで受信される。
(*2) 10.0.0.255/32宛の経路が設定される。(*1)とおなじく、ブロードキャストパケットを受信するのに必要。
(*3) 10.0.0.0/24宛の経路が設定される。この経路は自システムが接続されたネットワーク(この場合、10.0.0.0/24)への送信を行なうのに使われる。
fib_magic()
カーネルが自分で経路を作成する場合に使用する。
RoutingRequestを自分で作成して、経路の追加/削除を行なう。
アドレス設定時の自システム宛経路作成などもこのルーチンが使用される。
RoutingRequestを自分で作成して、経路の追加/削除を行なう。
アドレス設定時の自システム宛経路作成などもこのルーチンが使用される。
--------------------------------------
自足経路／ネットワーク経路の登録
SIOCSIFADDR
inet_ioctl()
devinet_ioctl()
struct in_ifaddr ifaを作成
inet_set_ifa()
inet_insert_ifa()
ifaをデバイスのチェーンにつなぐ
rtmsg_ifa(RTM_NEWADDR, ifa)
notifier_call_chain(&inetaddr_chain,
NETDEV_UP, ifa)
inetaddr_chainに登録されている
notifierのハンドラをコール。
notifierは初期化時(ip_fib_init())に
register_inetaddr_notifier()
で一つ登録しているだけ。
ハンドラはfib_inetaddr_event()。