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

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

1. 概要

Linuxではルーティングテーブルのことをフォワーディングインフォメーションベース(FIB)と呼ぶ(以下でルーティングテーブルと呼んだ場合はFIBのことを指す)。また、パケットの送受信で参照されたルーティングエントリはルートキャッシュにキャッシュして次から素早くルーティングエントリを検索できるようになっている。

2. フォワーディングインフォメーションベース

2.1 FIBの構造

FIBの構造を図1に示す。


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の方のエントリにヒットする。

フィールド	説明
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.3 FIBの種類

FIB(struct fib_table)は用途に応じて複数存在している。通常は以下の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]

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のルーティングエントリはルーティングキャッシュにキャッシュして使用する2段構造になっている。IP層からの経路検索の際はまずルーティングキャッシュが調べられ、なければFIBを検索する。エントリが見つかった場合はルーティングキャッシュにキャッシュされる。

ルーティングキャッシュの構造を図4に示す。ルーティングキャッシュはハッシュ構造になっている。struct rt_hash_table[]がハッシュテーブルになっており、各エントリからstruct rtableのリストが連なっている。rtableのrt_gatewayにはGatewayのIPアドレスが格納されている。rtable内にはプロトコル非依存の宛先に関する情報struct dst_entryが格納されている。struct dst_entryには、通信時に使用するARPエントリ(IPv4の場合)へのポインタや、送受信ルーチンへのポインタなどが格納されている。

ルーティングキャッシュの内容は/proc/net/rt_cacheで確認できる。

フィールド	説明
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テーブルを取得して検索していく
        local_rule -> main_rule -> default_rule

                fib_get_table(r->r_table)
                        ip_fib_main_table or ip_fib_local_tableの
                        アドレスが返される

                tb->tb_lookup() - fn_hash_lookup()
                                  fib_hash_init()で設定されている
                        指定したfibテーブルの検索を行う


fn_hash_lookup() - ルーティングテーブル(fib)検索
        ネットマスクの大きい方のZoneから(fn_zone_list順)順に検索。
        各ゾーンのhashからfib_nodeを検索する。

        上位ルーチン - fib_lookup()


IPv6のようにアドレス長が長くなるとZoneの数が増えて不利になる？



[経路の追加]
tb->tb_insert() - fn_hash_insert()


[経路の削除]
tb->tb_delete() - fn_hash_delete()

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

ip_route_input()
        ハッシュから検索

        ハッシュになければip_route_input_slow()で
        fibから検索する。


ip_route_input_slow()
        fib_lookup() - fibから検索

        見付かったらstruct rtableを作成しHashに登録しておく。






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


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に自足経路を追加

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