TIPS/Linux/kernel/ipv4ルーティング処理

Last-modified: 2007-02-14 (水) 18:57:35

静的ルーティングテーブル

Linuxでは、フォワーディングインフォメーションベース(fib) という名前が付けられている。

  • 大きなルーティング情報を高速に検索できるよう下図のような構成になっている。
  • ルーティング情報は、各ネットマスク毎にゾーンに分割され管理される(fn_zone構造体)。
  • 各ゾーンでは、ルーティング情報(fib_node)がハッシュ管理される。

#ref(): File not found: "img91.gif" at page "TIPS/Linux/kernel/ipv4ルーティング処理"

  • ルーティング情報検索時(fn_hash_lookup関数)にはネットマスクの大きい方(fn_zone_listに継っているfn_zone)から順に検索を開始する。
  • 各ゾーン毎にhash管理されているfib_nodeに目的とするものがないかチェックを行い、目的のものが見つかった場合その情報を返却する。
  • このテーブルは、処理効率化のため二つのグループに分割して管理されている。
    • ユニキャスト(あるホストへの直接送信)とgateway経由の送信の経路情報を管理するmain_table。
    • ローカルマシン上の転送経路、ブロードキャスト、マルチキャストを管理するlocal_table。 
      (コンフィギュレーションにより、更に複数のテーブルに分割して 管理することも可能)

関数説明

ルーティング情報の追加削除は、明示的に行わねばならない。ネットワークインターフェイスのUP/DOWNもしくは、 routeコマンドによる操作である。最終的には下記関数が呼び出され、ルーティング情報の更新が行われる。

  • fib_lookup(), fn_hash_lookup()
    • 目的とするアドレスへ到達するためのルーティング情報を検索する。
  • fn_hash_insert()
    • ルーティング情報を追加する。ip_rt_ioctl関数から呼び出される。
  • fn_hash_delete()
    • ルーティング情報を削除する。ip_rt_ioctl関数から呼び出される。

ルーティングテーブルキャッシュ

  • ルーティング情報の参照頻度は非常に高い(各パケット送信毎、受信毎)のため、一度参照したルーティング情報を、一定時間ルーティングテーブルキャッシュ(rt_hash_table)内に保存する。
  • 次に同じルーティング情報を検索した場合、ルーティングテーブルキャッシュにヒットする。

#ref(): File not found: "img92.gif" at page "TIPS/Linux/kernel/ipv4ルーティング処理"

  • コネクションの確立したソケットに関しては、ソケット自体にルーティングテーブルをリンクしておき、ルーティングテーブルキャッシュさえも検索しなくて済むよう考慮されている。

関数説明

  • rt_intern_hash()
    • ルーティング情報をルーティングテーブルキャッシュに登録する。
  • rt_check_expire()
    • 一定時間利用されていないルーティングキャッシュエントリをクリアする。
      • 60～120秒。ip_rt_gc_interval値 = 60 の場合。
      • 実際には、内部監視もip_rt_tc_interval = 60秒間隔で行われるため、
        min60秒～max180秒と予想される
  • * ip_rt_redirect()
    • o ICMPによるルーティング情報の変更要求(より効率的な ルートを伝達するのに利用される)を受け付ける。変更要求に 従い、ルーティングテーブルキャッシュ上の情報をアップデートする。
    • o fib(静的ルーティングテーブル)の方は更新しないことに注意。
  • * inet_addr_type()
    • o アドレスのタイプを求める。(RTN_UNICAST, RTN_BROADCAST, RTN_MULTICAST等)を返却する。

フォワーディング処理時のルーティング

ルーティング処理で以下のことを解決する。

  • どのネットワークインターフェイスから送信すべきか？
  • ホストが同じネットワーク上にないとき、どのゲートウェイマシンに 対してパケットを送信すべきか？

パケット送信時にはソケットが持つルーティング情報(rtable構造体)とパケットのリンクを行い、その後そのルーティング情報に従い、送信処理を行う。

ルーティング情報検索高速化のため、ソケットのコネクション確立時、またはIPパケット送信(ip_queue_xmit関数)時にルーティング情報(rtable構造体)を入手(ip_route_output関数)し、ソケットにリンクしておく。

#ref(): File not found: "img93.gif" at page "TIPS/Linux/kernel/ipv4ルーティング処理"

ルートキャッシュヒットテスト

ip_route_output()

  • ルーティングキャッシュ(rt_hash_table)に 目的とするルーティングテーブル(rtable)が登録されていないか検索する。
  • 生成されたハッシュキーには、rtableがリストでチェーンされている
    それを一つずつチェックする
    • チェックは、da/sa/inputif/tos/fwmarkが同じであるかをチェックする
  • 一緒なものがあればキャッシュヒット
  • 一緒なものがなくリストが終わればキャッシュミス

ハッシュキー（ハッシュ値）の生成

発信元アドレス/送信先アドレス/入力インターフェイス情報/tosを元にキャッシュ。
rt_hash_code()でハッシュを作成する
引数は3つ（3word）で、da/sa ^ (iif << 5 )/tosの順

この先で、
jhash_3words()を呼ぶ＜＝＝ハッシュ生成ルーチン（3word用）
結果にhash-maskをかけることで、その長さ未満のハッシュ値が返る

例えば、ハッシュサイズが1024であれば、0x3FFをかけているので
jhash_3wordsの戻り値の下11bitがハッシュキーとなる

キャッシュヒット

ip_route_input()の続きで

  • rtableのlastuseにjiffiesの値を入れる（最終使用時刻の設定）
  • rtable(dst_entry)のリファレンスカウント(__use)をカウントアップ
  • パケットのskbのdstポインタにrtable(dst_entry)の値を入れる
  • return 0 (<==OK)

ルートキャッシュミス時

ip_route_output_slow

大元のルーティングテーブル (fib:forwarding-information-base) からルーティング情報を引き出す操作。

  • fib_lookup()
    • fibテーブルを検索し、目的のアドレスへ送信するための経路情報を求める

テーブルの検索

CONFIG_IP_MULTIPLE_TABLES
のdefineで決定する

  • CONFIG_IP_MULTIPLE_TABLES is not set
    • fib_lookup関数はlocal_table, main_tableの両方を検索する。
      • ふたつのtableしか見ていない
  • CONFIG_IP_MULTIPLE_TABLES=y
    • fib_lookup()関数がそもそも異なる（fib_rules.cのfib_lookup())
    • fib_rule構造体のリスト（iproute2のpolicyリスト）に従ってパケットとルールのチェックを行う
    • 一致した場合、そのアクションによって動作を確定
      case戻り値
      RTN_UNICASTテーブルを検索し、ルートがあれば0
      なければ続きのテーブルを舐める
      RTN_UNREACHABLE-ENETUNREACH
      RTN_BLACKHOLE(def)-EINVAL
      RTN_PROHIBIT-EACCES
  • RTN_UNICASTで発見時
    • policyに関連付けているテーブルをgetする ( fib_get_table() )
    • tb->tb_lookup()　でルートを検索
    • 一致ルートが無ければ、ループの頭に戻り、続きのfib_rule構造体をチェックする
    • 一致ルートがあれば発見
  • ルートlookup失敗=>廃棄
    • inputifのフォワーディング設定が不許可ならe_inval、エラーカウンタアップしない
    • それ以外はno_route処理

no_route処理

  • in_no_routeのカウンタをアップ（ RT_CACHE_STAT_INC(in_no_route) ）
  • res.type = RTN_UNREACHABLE　（ res = struct fib_result * , fib_lookupの戻り値）
  • dst_entry.error = ( fib_lookup()の戻り値の絶対値をいれる　）
  • 届かない形でrtable(dst_entry)を作成し、キャッシュに登録する

ルートlookup成功後

  • fib_validate_source() で発信元アドレスの正常性チェック
  • 経路情報より、入出力関数を登録
  • dst_entry.input = (入力関数) , dst_entry.output = (出力関数)
    • ローカルマシンへの配送なら、
      入力関数として ip_local_deliver関数を登録
      出力関数としてip_rt_bug関数を登録（ありえない）
    • 他マシンへの転送なら、
      入力デバイスが転送NGであればe_invalへ
      入力関数としてip_forward関数 <==フォワーディングパケット用（受信処理で呼ばれる）
      出力関数としてip_output関数 <==自局送信パケット用（送信処理で呼ばれる）
    • 共通のパケット情報を入れる
      • saddr/daddr/tos/fwmark/iif/out_dev
  • rt_set_nexthop()
    • fibテーブルから得た情報を元に、情報を反映
      • ゲートウェイ情報、MTU情報、 ウィンドウサイズ情報、RTT情報
  • rt_intern_hash()
  • rtable構造体を一つ確保(dst_alloc関数)し、ルーティング キャッシュ(rt_hash_table)に登録

ポリシールーティングに必要な機能

ポリシールーティングに絡む部分として

  • 検索するルートテーブルを決めるポリシー
  • ルーティングキャッシュ用のハッシュ関数
  • キャッシュヒットを決定する項目

がある

これらの部分を改良することで、
IPのSrcAddr/DstAddr/Tos/Protocol、UDP/TCPのSrtPort/DstPort、InputIF
の条件でポリシールーティングが可能となる。

実際には、mangleを用いることで、上記の条件で各パケットにマーク付け(fwmark)
することで、ポリシールーティングが可能であるが、

  • 全てのFWパケットにmangleの処理を実行する必要がある
  • そのmangleの実行処理が重い( netfilter機能を用いる ）

ため、ルーティング処理のパフォーマンスが落ちることが予想される

そこで、ルーティング処理がより落ちないために、

  • mangleを通さないでルーティングテーブルを選ぶ手法
  • 必要な条件要素をルーティングキャッシュに盛りこむ手法

の適用が考えられる

検索するルートテーブルを決めるポリシー

カーネル2.6.9時点での判定要素 

               if (((saddr^r->r_src) & r->r_srcmask) ||
                   ((daddr^r->r_dst) & r->r_dstmask) ||
                   (r->r_tos && r->r_tos != flp->fl4_tos) ||
#ifdef CONFIG_IP_ROUTE_FWMARK
                   (r->r_fwmark && r->r_fwmark != flp->fl4_fwmark) ||
#endif
                   (r->r_ifindex && r->r_ifindex != flp->iif))

ルーティングテーブルを決めるポリシーの要素は

  • SA(prefix)
  • DA(prefix)
  • tos
  • fwmark (mangle)
  • iif
    となる

変更

mangleを用いないようにするために、ここに

  • IP-Protocol
  • (UDP/TCPの場合)SrtPort/DstPort

を追加する必要がある

ハッシュ関数

カーネル2.6.9時点でのキー要素 

hash = rt_hash_code(daddr, saddr ^ (dev->ifindex << 5), tos);
static unsigned int rt_hash_code(u32 daddr, u32 saddr, u8 tos)
{
       return (jhash_3words(daddr, saddr, (u32) tos, rt_hash_rnd)
               & rt_hash_mask);
}
  • DAddr
  • SAddr
  • tos
    が関与している
    （rt_hash_rndは、フラッシュ毎に変更されるランダムな数）

変更

現状のままの場合、通信している2つのノードにおいてTCP/UDPやPort番号の違っても
ハッシュキーは同一のものとなる
ハッシュキーが同一の場合、コンフリクトが発生し、同じキーのリストにつながる
このリストの検索時間が長くなってしまい、パフォーマンスに影響を与えるため、
改良が必要となる

また、ハッシュ関数の生成部分は全てのパケットが通るため、
非常に短時間に生成されなければならない。
上記のjhash_3wordsを利用し、且つ以下の要素を盛りこむような
実装がベストと言える

  • DPort
  • SPort
  • Protocol

例えば

hash = rt_hash_code(daddr ^ (proto << 5)
                   , saddr ^ (dev->ifindex << 5)
                   , (u_long)dport <<16 + sport ^ ( tos << 5 ) );

などのようにする
（詳細は検討中…）

キャッシュヒットを決定する項目

カーネル2.6.9時点での判定要素 

               if (rth->fl.fl4_dst == flp->fl4_dst &&
                   rth->fl.fl4_src == flp->fl4_src &&
                   rth->fl.iif == flp->iif &&  <==送信処理時は0であるかどうか
                   rth->fl.oif == flp->oif &&  <==受信処理時は0であるかどうか
#ifdef CONFIG_IP_ROUTE_FWMARK
                   rth->fl.fl4_fwmark == flp->fl4_fwmark &&
#endif
                   !((rth->fl.fl4_tos ^ flp->fl4_tos) &
                           (IPTOS_RT_MASK | RTO_ONLINK))) {

つまり受信処理では

  • DA
  • SA
  • iif　(送信処理ではoif)
  • fwmark (いわゆるmangle)
  • tos
    が同じであることがヒットの条件

変更

fwmarkを用いることで、全てのパケットをキャッシュ可能としている
しかし、mangleを使用しないでヒットさせたいため
ここに、tcp/udpのSrc-Port/Dst-Port、IP-Protocolをいれる必要がある