今日は,あて先検索の残り二つの方式について解説していきます。

検索方法を工夫して時間を短縮

 それでは(b)のツリー検索方式を見ていきましょう。ツリー検索方式では,フォワーディング・テーブルとして,ルーティング・テーブルのIPアドレスのビット・パターンに従って分岐するツリー・テーブルを作成しておきます。例えば,1ビットごとに分岐するツリーの場合,1ビットごとに「0」と「1」の二つの値に従ってツリーの分岐させます(図3)。検索時には,パケット・ヘッダー内のあて先IPアドレスを上位ビットから検査し,ビットの値に従ってツリーをたどります。1ビットごとに分岐するツリーの場合,IPv4のIPアドレスのビット長は32ビットなので,最大でも32回ツリーをたどれば検索が終了します。

図3●ツリー検索方式によるあて先検索処理
図3●ツリー検索方式によるあて先検索処理
ルーティング・テーブルのあて先IPアドレスをビット・パターンに変換し,1ビットずつ分岐するツリー・テーブルを作成しておく。あて先となるIPアドレスもビット・パターンに変換し,1ビットずつ読み出して比較していけば,IPv4アドレスの場合は32回の読み出し処理で済む。

 ある分岐点から次の分岐点に進むには,テーブル・メモリー内の情報を1回読み出す必要があります。読み出した情報の中に,次の分岐点の情報が格納されているテーブル・メモリー内のアドレスが含まれるので,その値を使って再度テーブル・メモリー内の情報を読み出します。このように,一つの分岐点から次の分岐点へ進むためには,検索エンジンがテーブル・メモリーからデータを読み出し,次の読み出し要求を出すまでの時間が必要です。読み出し要求を受けてからデータが出力され,パケット処理部がデータを受け取るまでの時間は,前出のSSRAMの読み出し間隔(3.8ns)の4~10倍程度になります。

 この値を10倍と仮定すると,1ビットごとに分岐させるツリーで一つの経路を検索するのにかかる時間は,最大で 3.8ns×10×32=1216nsとなります。これも,10Gビット/秒の回線1本分を流れるパケットを処理すべき67nsの約18倍になってしまいます。

 この時間を短くする方法はいくつかあります。1ビットごとに分岐させるのではなく,4ビットごとあるいは8ビットごとに分岐させるようにツリーを作り変えたり,ツリーの段数ごとに物理的に異なるテーブル・メモリーを用意したりすることで,検索時間の短縮は可能です。

 例えば,8ビットごとに分岐させるツリーの場合,ツリーの分岐回数は32ビット÷8ビットの4回となります。また,この4回の分岐ごとに異なるテーブル・メモリーを用意できれば,あるパケットの1回目の分岐検索を実行した後,次のパケットの1回目の分岐検索を続けて実行できるようになり,連続で検索処理を行えるようになります。この場合の検索時間は,1回分岐をたどる時間である3.8ns×10=38nsとなり,10Gビット/秒の回線1本分を流れるパケットを処理できることになります。

 ただし,分岐させるビット数を多くしたり,分岐ごとにテーブル・メモリーを用意することは,検索エンジンとテーブル・メモリーを接続する信号線の数が多くなり,検索エンジンのコスト上昇や,メモリー個数の増加による装置のコスト上昇につながってしまうというデメリットがあります。

特別なメモリーを使ってエントリを同時検索

 あて先検索方式の最後として(c)の全エントリ同時検索方式を紹介しましょう。これは,CAMと呼ばれる特殊なメモリー素子を使うことで検索を非常に高速に実行する方式です。その流れを追って見ていきます。

 ルーターは,ルーティング・テーブル内のあて先IPアドレスを全てCAMに設定しておきます。検索エンジンは,受信したパケットのあて先IPアドレスを検索キーとしてCAM内のすべてのエントリに対して一致比較を実施します。CAMは,こうした検索が可能なメモリー素子です。検索エンジンは,一致したエントリの登録位置を読み出します。CAMとは別に用意した通常のSSRAMなどのメモリーに,登録位置と1対1に対応させてあて先情報を格納しておけば,CAMの検索が1回と,一致した登録位置に対応するあて先情報の読み出しが1回であて先の検索が終了します(図4)。

図4●全エントリ同時検索方式によるあて先検索処理
図4●全エントリ同時検索方式によるあて先検索処理
CAM(content addressable memory)という特殊なメモリーを使い,あて先となるIPアドレスに対応する送信ポートの書き込んである場所を1回で見つけ出す。読み込み回数が少ないので,あて先検索処理を高速化できる。

 CAMの検索に必要な時間間隔は,現状で7.5ns程度です。SSRAMの読み出し時間は前出の通り3.8nsなので,この二つを連続して処理できれば,時間の長い7.5nsだけを考えればよいので,67(ns) ÷ 7.5(ns) ≒ 8.9となり,10Gビット/秒の回線8本分のパケットを処理できる計算になります。

 このように,ほかの検索方式に比べて全エントリ同時検索方式は圧倒的に高速ですが,CAMのビット単価が通常メモリーに対して高価で,20万件もの大規模テーブルを格納すると装置のコストが膨れ上がってしまいます。また,実装面積が増えてしまうことや消費電力が大きいこともデメリットとして挙げられます。

 こうしたデメリットはあるものの,性能が重視されるハイエンド・ルーターでは,(c)の全エントリ検索方式が多く採用されています。性能よりも消費電力や実装面積,コストなどを重視する場合は(b)のツリー検索方式が採用される傾向にあります。ルーター装置が目標とする性能・消費電力・コストに応じて異なる方式が採用されているのです。

林 剛久(はやし たけひさ) アラクサラネットワークスCTO

赤羽 真一(あかはね しんいち) アラクサラネットワークス 第二製品開発部

石川 有一(いしかわ ゆういち) アラクサラネットワークス 第二製品開発部

加賀野井 晴大(かがのい てるお) アラクサラネットワークス 第二製品開発部

<<【1】を読む 
>>【3】を読む