PR

ルーターがパケットを転送するときにキモとなるのは,経路を経路表から見つけ出す経路検索と,ヘッダー情報が条件と合致するパケットを探し出すフィルタ検索。では,検索を高速に処理するために,ルーターはどんなテクニックを使っているのだろうか。Part3では,この点にスポットを当てて解説しよう。

 Part2で見たように,ルーターがパケットを転送するときにキモとなるのはヘッダーの解析処理だ。あて先IPアドレスに対応する経路を経路表から見つけ出す経路検索と,ヘッダー情報が特定の条件と合致するパケットを探し出すフィルタ検索。この二つが処理の柱である。

 この二つの検索処理,一見,簡単そうだが実は一筋縄でいかない。ルーターには膨大なパケットが流れ込んでくる。1ギガのイーサネット・インタフェースが1本あるだけでも,毎秒10万個以上のパケットを処理しなければならない。一刻の猶予もない。

 では,検索を高速に処理するために,ルーターはどんなテクニックを使っているのだろうか。Part3では,この点にスポットを当ててみる。

選べる経路は一つとは限らない

 経路検索は経路表に書かれているルートの中から,あて先IPアドレスに適合するルートを見つけ出す処理である。その検索方法は「ロンゲストマッチ検索」と呼ばれる。

 経路表は,あて先となるネットワークのネットワーク・アドレス,ルーターのアドレス,送出インタフェースなどの情報を一組にしてまとめている。経路検索の対象は,この中のネットワーク・アドレスだ。

 ネットワーク・アドレスのうち,サブネット・マスクで区切られた前半部分をネットワーク部と呼ぶ。例えば,192.168.4.0/26だと,アドレスを2進数表記にしたときの先頭から26ビットがネットワーク部になる。

 ルーターはパケットのあて先IPアドレスと,経路表に書かれたネットワーク・アドレスのネットワーク部を先頭のビットから順番に照合していく(図1)。そして,ネットワーク部がすべて一致したものが候補になる。

図1●ロンゲストマッチ検索は手間がかかる
図1●ロンゲストマッチ検索は手間がかかる
経路表からパケットの転送先を決めるロンゲストマッチ検索は,単純な一致検索と違って条件分岐があるので手間がかかる。

 しかし,候補は一つとは限らない。複数の候補が見つかったときは,一致したビットが最も長いルートを採用する。これがロンゲストマッチだ。

 このロンゲストマッチ検索は意外と面倒である。検索で見つかる候補が一つとは限らず,複数見つかったときにどれがロンゲストマッチかを判断する必要があるからだ。このため,経路表を順番に舐めていき,最初に見つかった候補をロンゲストマッチとして選ぶといった方法が使えない。

 もしテーブルを順番に舐める方式でロンゲストマッチを探すと,経路表を最後まで確認して候補をリストアップし,その候補からロンゲストマッチを選ぶ必要がある。少し考えればわかるように,こんな方法では経路表が大きくなるほど検索時間がかかる。

ビットごとに分岐するツリーを使う

 実際のルーターでは経路表を1行ずつ舐めるなどという方法は使わない。経路検索を高速化する手法はいくつかあるが,ここでは定番として知られているツリー法から紹介しよう(図2)。

図2●ロンゲストマッチを高速化するツリー検索の動作
図2●ロンゲストマッチを高速化するツリー検索の動作
ツリー方式では経路表からあらかじめ条件分岐のツリーを作っておく。先頭のビットから順番に分岐をたどり,最終的にたどり着いたところがロンゲストマッチになる。図では25ビット目以降のツリーだけを見せている

 ツリー法では,経路表から検索用のツリーをあらかじめ作っておく。ビットが0の場合と1の場合で1ビットごとに32回条件分岐するツリーを作り,あて先ネットワークのアドレスを先頭から順に当てはめていく。ただし,ネットワーク部が尽きたら,ツリーはそこで切る。この作業をすべての経路について実施すると,1本のツリーが出来上がる。

 図2の例では,三つの経路が経路表に登録されている場合の25ビット目以降をツリー化した。ネットワークAは25ビット目以降が「00」だから,26ビット目の0でツリーは終わりになる。ところが,ネットワークAのアドレスと26ビット目まで同じネットワークB(0001)とネットワークC(0010)があるので,26ビット目の0のあとに28ビットまでツリーを続けておく。これで検索ツリーの準備は完了だ。

 あとは,受信パケットに書かれたあて先IPアドレスの先頭ビットから正確にツリーをたどっていくだけだ。ツリーの末尾までたどり着いたら検索終了である。図では25ビット目以降が「00010100」というアドレスを検索している。順にたどると28ビット目で末端に着き,同時にロンゲストマッチがネットワークBだとわかる。

 もしあて先IPアドレスが「00001001」や「0011001」ならネットワークAになる。また「01001000」なら経路表に該当するルートがないと26ビット目でわかる。

 ツリー法のメリットは最大でも32回の条件分岐検索で,どんなあて先でも必ずロンゲストマッチ(もしくは候補なし)を探し出せること。ツリーさえ正確に作っておけば,マッチする候補がいくつあっても,ツリーをたどるとロンゲストマッチに到達する。