ルーティングテーブル

Rev.24を表示中。最新版はこちら。

IPv4のルーティングテーブルに関するメモ

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ルール」を参照。

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で確認できる。

図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()。

fn_hash_lookup()

ルーティングテーブル(fib)検索の内部ルーチン。Hashからエントリを探す。

ネットマスクの大きい方のZoneから(fn_zone_list順)順に検索。

4.2 ルーティングキャッシュ関連

ip_route_input()

IPパケット受信時のルーティングキャッシュの検索ルーチン。
IP層の受信処理から呼ばれる。

ルーティングキャッシュにエントリがなければ、ip_route_input_slow()でFIBに検索にいく。

ip_route_input_slow()

ルーティングキャッシュにエントリがなかった場合に、FIBを検索する。

FIBで見つかったエントリは、対応するstruct rtableを作成してルーティングキャッシュに入れる。

--------------------------------------
自足経路／ネットワーク経路の登録

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()。

Notifierハンドラ
fib_inetaddr_event(NETDEV_UP)
        fib_add_ifaddr(ifa)
                fib_magic(RTM_NEWROUTE, RTN_LOCAL,...)
                        RT_TABLE_LOCALに自足経路を追加

                ブロードキャストアドレスも経路追加