(57)【特許請求の範囲】
【請求項１】
高速ルータのフロントエンドで高速インターネット・プロトコル（ＩＰ）ルックアップ機能要件を満たし、特別設計の処理要素のアレイ編成である装置であって、
前記処理要素は、任意のルーティング・テーブルの二項トライ（ＢＴ）データ構造表現を前記装置にマッピングすることを可能にする、複数の交差する様々な長さの並列パイプラインを形成し、ここで、ＢＴデータ構造の使用は前記装置における平均パイプライン長を短縮するものであり、
前記装置は、探索中にトラバースされるノードの数が、探索キー（ＩＰアドレス）内の最上位セット・ビット位置と最下位セット・ビット位置との間のビットによって決まる、ルックアップ（探索）方法；および、
以下を含むマッピング方法：
ｉ．二重根区分と称するトライ区分方法であって、ＢＴノードが２つのグループに分割され、一方のグループが、アドレス内により多くの「０」ビットを有するノードを含み（上部ＢＴ）、他方のグループが、アドレス内により多くの「１」ビットを有するノードを含み（下部ＢＴ）、両区画が、元の深さの約半分である別個の、しかし同様のＢＴとして表され、根ノード・アドレスが、一方の区画ですべて「０」であり、これが西側ＰＥから開始することによって装置にマッピングされ、他方の区画ですべて「１」であり、これが北側ＰＥから開始することによって装置にマッピングされるものである、トライ区分方法；
ｉｉ．ＢＴクラスタリングと称するクラスタリング方法であって、以下：
ａ．上位ＢＴクラスタリングであって、プレフィックスの先行する０が除去され、これが、除去された先行する０の数に基づいて二項トライの上部部分を複数のクラスタに区分することに対応し、除去された先行する０の数がクラスタ・インデックスとして使用される、ステップと、
ｂ．下部ＢＴクラスタリングであって、プレフィックスの先行する１が除去され、除去された先行する１の数を使用して複数のクラスタが得られ、削除された先行する１の数がクラスタ・インデックスとして使用されるステップと、
を含むクラスタリング方法；
ｉｉｉ．サブトライの根を、対応する入力ステージＰＥ上に格納するためのインデックス計算方法；および
ｉｖ．各トライ・ノードの左側子ノードを南の隣接ＰＥに格納し、また各トライ・ノードの右側子ノードを東の隣接ＰＥに格納するＢＴ格納方法、ここで、長いサブトライ経路はラップアラウンド接続を使用することによって格納される；
を実行するものである、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、第１に、マルチパイプライン並列性の思想を使用するＳＲＡＭベースのシストリック・アレイ・アーキテクチャを含むＳＲＡＭベースのパイプラインＩＰルックアップ・アーキテクチャを提供し、それについて、基本アーキテクチャとしてその利点を強調して明らかにする。この基本アーキテクチャでは、複数の交差する様々な長さのパイプラインが、処理要素の２次元配列上で環状に構築される。このアーキテクチャは、従来のバイナリ・プレフィックス木ではなく、任意のタイプのプレフィックス木の使用をサポートする。本発明は、第２に、実質的な性能向上を達成するような、二項全域木（ｂｉｎｏｍｉａｌ  ｓｐａｎｎｉｎｇ  ｔｒｅｅ）に基づく代替の、より有利なプレフィックス木の新規な使用を提案する。この新しい手法は、４側入力および３ポインタ実装を含む他の拡張で改良されており、基本アーキテクチャの並列性および探索能力を著しく高め、あらゆる既存のＩＰルックアップ手法よりはるかに高いスループットを提供し、たとえば７ＴｂｐｓのルータＩＰルックアップ・フロントエンド速度を可能にする。このシストリック・アレイ・アーキテクチャにおける理論上の最悪ルックアップ遅延は高いが、平均遅延は非常に低く、大きな遅延がまれに観測されるにすぎない。その新しい形態にある構造は、処理要素の点でスケーラブルであり、また、ＩＰｖ６アドレッシング方式に十分適したものである。
【背景技術】
【０００２】
（トライ・ベースのＩＰルックアップ）
ＩＰルックアップ解決策は、ソフトウェア・ベースの手法とハードウェア・ベースの手法として２つの主なグループに分類することができる。ＬＰＭのソフトウェア・ベースの解決策については、最も一般的に遭遇するデータ構造は二分木であり、二分木では、ルーティング・テーブル内のプレフィックスがマーク付きの木ノードによって表され、根からノードへの経路がプレフィックスを表す。図１は、プレフィックス・テーブル、およびその対応するプレフィックス木（文献ではバイナリ・トライと呼ばれる）を示す。
【０００３】
ＩＰルックアップは、探索されたＩＰアドレス内のビットを使用してバイナリ・トライをトラバースすることによって実施される。葉ノードまたはヌルポインタに到達したとき、探索動作が終了し、最後に一致したプレフィックスが最長一致プレフィックスとして選択される。プレフィックス・ノードすべてが葉にプッシュされる場合には、バイナリ・トライは、葉にプッシュされる（ｌｅａｆ−ｐｕｓｈｅｄ）バイナリ・トライと呼ばれる。葉にプッシュされるトライでは、葉でないノードは、その子へのポインタだけを含み、葉ノードは、その関連のプレフィックスに対応するポート番号だけを含む。
【０００４】
（高速ＩＰルックアップのためのＳＲＡＭベースのパイプライン・アーキテクチャ）
単一ＳＲＡＭベースのＩＰルックアップ解決策は、単一の探索プロセスを完了するために、トライ・トラバース中に複数のメモリ・アクセスを必要とする。ＩＰアドレスの探索中には、新たに入来する探索要求が、継続中のルックアップが終了するのを待つ。これを高速化するために、様々なＳＲＡＭベースのパイプライン・アーキテクチャが提案されている［１４］［１５］［１６］［１７］［１９］［２０］［２１］［２２］［２３］［２４］［２５］。これらのアーキテクチャでは、トライが区分され、パイプラインにマッピングされる。これらのパイプラインは、順次接続される別々のメモリ・バンクで構成される。次いで、これらの別々の複数のメモリ要素に対して、パイプラインを介してトライ・トラバースが実施される。
【０００５】
メモリ要素が十分にあり、従来の１次元パイプライン・アーキテクチャでは、探索中に２回以上アクセスされるステージはない。スループットはパイプラインを使用して改善されるが、パイプライン・ステージにバイナリ・トライの通常のマッピングを行うと、メモリ利用が不均衡になる。様々な異なる解決策がメモリ平衡化問題に対処するために提案されている［１４］［１５］［１６］［１９］［２１］。Ｂａｂｏｅｓｃｕら［１４］は、任意のパイプライン・ステージで探索を行うことを可能にするリング・パイプライン・アーキテクチャを提案している。この手法は、バイナリ・トライをサブツリーに分割し、各サブツリー開始点を異なるパイプライン・ステージに割り振り、平衡パイプラインを生み出すことに基づくものである。次いで、各探索のための開始ステージがハッシュ関数によって決定される。サブツリーは、レベルに基づくマッピングを使用することによってパイプライン内に格納され、同じレベルのトライ・ノードは、同じパイプライン・ステージに格納される。各サブツリーの深さは、パイプライン・ステージの数以下となるように選択されるが、パイプラインは、最後のステージから最初のステージに逆戻りすることができ、したがってリング構造と呼ばれる。このパイプライン・アーキテクチャは、２つの仮想データ経路を有する。第１の経路は、奇数クロック・サイクル中に活動状態であり、開始ステージを見つけるために使用される。換言すれば、探索が開始されたとき、関連のサブツリーの根が見つかるまでパイプラインがトラバースされる。第２のデータ経路は、偶数クロック・サイクル中に活動状態であり、パイプラインの最後のステージまで継続する実際の探索に対応する。探索が完了したとき、結果は、残りのステージを通って出力するために最後のステージに伝播する。したがって、各パイプライン・ステージは、最大入力パケット・レートの２倍の速度で機能する。したがって、述べたＢａｂｏｅｓｃｕらのアーキテクチャのスループットは、クロック・サイクルあたり０．５ルックアップになる。
【０００６】
［１５］では、先の手法が、環状適応的単調パイプライン（Ｃｉｒｃｕｌａｒ，Ａｄａｐｔｉｖｅ  ａｎｄ  Ｍｏｎｏｔｏｎｉｃ  Ｐｉｐｅｌｉｎｅ／ＣＡＭＰ）と呼ばれるアーキテクチャで拡張されている。ＣＡＭＰは、メモリ・ブロックの環状パイプラインを有する。第１のブロックは、アドレスの最初のｒ個のビットに対して直接ルックアップを実施し、対応するサブツリーの根ノードが格納されているステージを見つける。ＣＡＭＰは、スループットを改善するために、複数のパケット入口点およびパケット出口点を有する。最初に、トライは、１つの根サブトライと、複数の葉サブトライに分割される。根サブトライは、テーブルとして実装されたＩＰアドレスの最初のｒ個のビットを処理し、最大２ｒ個のサブトライが個々にパイプラインにマッピングされる。各パイプライン・ステージは、２つの入口点と１つの出口点を有する。次いで、入来する要求について、各ステージでＦＩＦＯキューを使用してアクセス衝突が解決される。要求は、パイプライン・ステージに入るためにアイドル・サイクルを待つ。ＣＡＭＰアーキテクチャは、クロック・サイクルあたり０．８ルックアップのスループットを達成することができる。
【０００７】
探索木のレベルではなく高さに基づく代替のマッピングを用いて、最悪のステージあたりメモリ限界が得られている［１９］。ノードの高さは、ルートが更新されたときプレフィックス分布が変化すると変化するので、このマッピングは動的なものになる。
【０００８】
Ｊｉａｎｇら［１６］は、各パイプラインが同時に動作しルックアップを高速化することができる最初の並列マルチパイプライン・アーキテクチャ（並列最適化線形パイプライン（Ｐａｒａｌｌｅｌ  Ｏｐｔｉｍｉｚｅｄ  Ｌｉｎｅａｒ  Ｐｉｐｅｌｉｎｅ／ＰＯＬＰ））を提案した。
【０００９】
トライが最初にサブツリーに区分され、次いでサブツリーがパイプラインにマッピングされる。平衡マッピングを実施するために、Ｊｉａｎｇらは、近似アルゴリズムを提案した。また、各パイプライン内で、ノードからステージへのマッピングが行われ、一部のステージでｎｏｐ（何もしない）［２１］を使用し、トライ・ノード分布を平衡化する。この手法は、メモリ消費の点で効率的であるが、探索プロセスが複雑である。
【００１０】
ｎ個の並列宛先インデックス・テーブル（ＤＩＴ）を使用し、ｎ個のパケットを同時に処理し、サブツリーとパイプラインの間のマッピングを処理する。ＤＩＴでは、ＩＰアドレスの最初の数ビットを使用してパイプラインＩＤが得られる。このパイプラインは、対応するサブツリーと、パイプラインの最初のステージ内のサブツリーの根のアドレスとを格納するものである。また、ＰＯＬＰアーキテクチャは、短期的なトラフィックの偏倚のためにプレフィックス・キャッシングを使用し、一方、パイプライン間の長期的なトラフィックは、交換をベースとするアルゴリズムによって平衡化される。このアルゴリズムは、サブツリーをパイプラインに動的に再マッピングし、探索プロセスに余分な分裂をもたらす。ＰＯＬＰは、後の研究でさらに改善される。たとえば、双方向線形パイプラインが［１７］で導入され、レイヤ４交換からのフロー・キャッシングの思想が［２２］で導入されている。フロー・キャッシングは、キャッシュ更新のための長い待ち時間を解消する。ＰＯＬＰ電力効率を改善するために、ハイブリッドＳＲＡＭ／ＴＣＡＭセレクタ・ユニットもまた［２４］［２５］で提案されており、その目的は、ハイブリッド区分方式を導入することによってパイプライン長を短縮することである。
【００１１】
以下の特許は、本発明に関連する。
【００１２】
・米国特許第７４１８５３６号「Ｐｒｏｃｅｓｓｏｒ  ｈａｖｉｎｇ  ｓｙｓｔｏｌｉｃ  ａｒｒａｙ  ｐｉｐｅｌｉｎｅ  ｆｏｒ  ｐｒｏｃｅｓｓｉｎｇ  ｄａｔａ  ｐａｃｋｅｔｓ」
上記の発明において提供されているネットワーク・プロセッサの「ＩＰルックアップ・ユニット」もまた、シストリック・アレイ・アーキテクチャを使用することによって設計されている。しかし、シストリック・アレイ・アーキテクチャの各ステージは、小さいレジスタ・ファイルおよび機能ユニットで構成され、１次元だけで単一のパイプライン挙動を示す。一方、本発明では、シストリック・アレイ・アーキテクチャにおける処理要素（ＰＥ）が、単一のＳＲＡＭユニット、ＦＩＦＯキュー、および論理ユニットを有する。本発明において提供される新しいアーキテクチャは、並列パイプラインを２次元で使用するシストリック・アレイ・アーキテクチャである。複数の交差する様々な長さのパイプラインが、ＰＥの２次元配列上で環状に構築され、したがって並列性から、より多くの利益が得られる。
【００１３】
・米国特許第７０６９３７２号「Ｐｒｏｃｅｓｓｏｒ  ｈａｖｉｎｇ  ｓｙｓｔｏｌｉｃ  ａｒｒａｙ  ｐｉｐｅｌｉｎｅ  ｆｏｒ  ｐｒｏｃｅｓｓｉｎｇ  ｄａｔａ  ｐａｃｋｅｔｓ」
この既存の特許では、ルーティング・テーブル全体を格納するために、単一のオンチップ・メモリ・ユニットが使用される。本発明内で開発された構造では、シストリック・アレイ・アーキテクチャ内の各ＰＥが、より小さなメモリ・ユニットを維持し、したがって、２つ以上のメモリ・ユニットを使用することによって、各ユニットに対して並列かつ独立にメモリ・アクセスすることが可能であり、これは並列性をさらに高める。
【００１４】
・米国特許第７３８２７８７号「Ｐａｃｋｅｔ  ｒｏｕｔｉｎｇ  ａｎｄ  ｓｗｉｔｃｈｉｎｇ  ｄｅｓｉｇｎ」
この既存の特許では、すべてのユニットがプログラマブルである。本発明内の新しい構造では、シストリック・アレイ内の各ＰＥが次の１つをトリガし、したがってプログラマブル性は必要とされない。
【００１５】
・米国特許第７５２５９０４号「Ｒｅｄｕｎｄａｎｔ  ｐａｃｋｅｔ  ｒｏｕｔｉｎｇ  ａｎｄ  ｓｗｉｔｃｈｉｎｇ  ｄｅｖｉｃｅ  ａｎｄ  ｍｅｔｈｏｄ」
この既存の特許で提案されている構造は、４０Ｇｂｐｓのライン速度で動作する。一方、本発明内で開発された新しい構造で達成される性能レベルは、約７Ｔｂｐｓである。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】米国特許第７４１８５３６号
【特許文献２】米国特許第７０６９３７２号
【特許文献３】米国特許第７３８２７８７号
【特許文献４】米国特許第７５２５９０４号
【発明の概要】
【課題を解決するための手段】
【００１７】
インターネット上でのホストの数の増大およびライン速度の上昇により、ライン・データ・レートで動作することができ、ますます増加するルーティング・テーブル・エントリに対処することができる強力な転送エンジンが生まれた。インターネットの初期には、単純なクラス・ベースのアドレッシング方式で十分であったが、ＣＩＤＲ（ｃｌａｓｓｌｅｓｓ  ｉｎｔｅｒ  ｄｏｍａｉｎ  ｒｏｕｔｉｎｇ）方式の導入に伴い、ＩＰルート・ルックアップが、インターネット・ルータにとって主なタスクとなった。ＣＩＤＲは、２つの主な利点を有する。第１に、プレフィックスをＣＩＤＲ内で任意の長さのものにすることができ、したがってアドレス空間をより効率的に使用することができる。第２に、ＣＩＤＲは、ネットワークの任意のアグリゲーションを可能にし、したがってルーティング・テーブル・エントリの数が減少し、これは転送テーブルの肥大化を遅らせる。ＣＩＤＲでは、プレフィックスの重なり合いのため、２つ以上のエントリがルーティング・テーブル内で一致する可能性がある。そのような場合、正しく判断するために、ルータは、最長プレフィックス・マッチング（ＬＰＭ）と呼ばれる特定の（ｍｏｓｔ  ｓｐｅｃｉｆｉｃ）一致を見つけなければならない。ＬＰＭは、完全一致を見つけることより困難である。なぜなら、到着するパケットの宛先アドレスが、最長一致プレフィックスの長さについて情報を担持していないからである。ＬＰＭについては、文献［１］［２］でソフトウェア・ベースの解決策とハードウェア・ベースの解決策が共に提案されている。これらのＩＰルート・ルックアップの成功を測定するために、メモリ・アクセスの数、メモリ・サイズ、更新時間、スケーラビリティ、および柔軟性など、様々なメトリクスが使用される。
【００１８】
連想メモリ（ＣＡＭ）を使用して、予め格納されたメモリ・エントリのリスト全体において１クロック・サイクル内で、キーを探索することができる。従来のＣＡＭは、バイナリ値を格納し、したがって完全一致だけを求めてＣＡＭを探索することができる。各セルが０、１、または指定なし（ｄｏｎ’ｔ  ｃａｒｅ）をとることができる３値連想メモリ（ＴＣＡＭ）は、指定なしが探索中にワイルドカードとして働くことができ、したがってＬＰＭを１サイクル内で自然に解決することができるので、より強力である［３］。ＴＣＡＭは、非常に普及しているが、大きな欠点としてコストが高く、高電力消費である［４］［５］［６］［７］［８］［９］［１０］［１１］［１２］［１３］。他の不利な点は、更新レートが遅く、スケーラビリティが低いことである。インターネットは、ルート変更を反映するために、転送テーブルが頻繁に更新されることを必要とし、プレフィックスの追加または削除を含む単一の更新は、ＴＣＡＭエントリの順序を維持するために複数のＴＣＡＭエントリの移動を必要とする可能性がある。低いスケーラビリティは、ＴＣＡＭ出力ステージに優先度エンコーダが必要であることに起因する。一方、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）は、ＴＣＡＭに比べて密度、電力消費、および速度特性が良好である。しかし、ＳＲＡＭを使用してＬＰＭを解決する場合、メモリ・アクセスの数は、ルーティング・テーブル内でプレフィックスを格納する二分木の平均深さによって決まる。単一のＳＲＡＭ上での木のトラバース・プロセスは、最長一致プレフィックスを見つけるために複数のメモリ・アクセス、したがって複数のクロック・サイクルを必要とする。したがって、スループットを改善するＳＲＡＭベースのパイプライン・アーキテクチャもまた、普及してきた［１４］［１５］。各パイプラインが同時に動作することができるＩＰルックアップのための最初の並列マルチパイプラインＳＲＡＭベース・パイプライン・アーキテクチャは、［１６］で登場し、［１７］で改良された。
【００１９】
シストリック・アレイは、複数の交差するパイプラインのための自然な構造である。本発明では、マルチパイプライン並列性の思想が使用され、高速ＩＰルックアップのための新規なＳＲＡＭベースのシストリック・アレイ・アーキテクチャ（ＳＡＡＦＦＩＬと呼ばれる）が開発される。そのために、ｉ）基本ＳＲＡＭ、ＦＩＦＯキュー、および関連の周辺論理回路で構成された特別なシストリック・アレイ処理要素（ＰＥ）が設計され、ｉｉ）本発明のＰＥが、異なる長さの交差するパイプラインを得るために２次元環状構造で編成され、ｉｉｉ）適切かつ効率的な木マッピング方式が工夫され、ｉｖ）対応するＩＰルックアップ・プロセスが提供される。ＳＡＡＦＦＩＬでは、ｎ個の並列パイプラインのそれぞれがｍ個のステージを有し合計ｎｍ個のリソースを有する並列パイプラインを使用するのではなく、リソースの
【数１】
0005529976.tif 000002
平方グリッドの形態にある環状構造が使用される。ＳＡＡＦＦＩＬを使用して、２ＴｂｐｓのルータＩＰルックアップ・フロントエンド速度が可能になった。
【００２０】
本発明では、基本アーキテクチャＳＡＡＦＦＩＬは、はるかに良好な性能を達成するように実質的に拡張される。全体的に、本発明では、以下の主な提案を行う。
【００２１】
１．高速ＩＰルックアップのためのＳＲＡＭベースのパイプライン・アーキテクチャが再検討され、基本アーキテクチャとしてのＳＡＡＦＦＩＬが、その利点を強調して明らかにされる。
２．基本アーキテクチャＳＡＡＦＦＩＬは、二項全域木に基づいて代替のより有利なプレフィックス木の新規な使用を含むことにより改良され、実質的な性能向上を達成する（ＳＡＡＦＦＩＬ−ＢＴと呼ばれる）。そのために、本発明では、
ａ）二項全域木ベースの転送テーブル構築方法が工夫され、
ｂ）二重根区分（ｄｕａｌ  ｒｏｏｔ  ｐａｒｔｉｔｉｏｎｉｎｇ）と称する新規な概念の開発を含めて、アーキテクチャ上への二項全域木マッピング方針が設計され、
ｃ）対応するＩＰルックアップ・プロセスが、新しい構造ＳＡＡＦＦＩＬ−ＢＴのために提供され、
ｄ）ＳＡＡＦＦＩＬ−ＢＴ用のセレクタ・ユニット設計が与えられる。
３．ＳＡＡＦＦＩＬ−ＢＴが、さらに性能を増すために拡張される。そのために、以下が考慮される。すなわち、
ａ）入力でのキャッシュ使用
ｂ）ＰＥでのデュアル入力／出力ＳＲＡＭ使用
ｃ）４側入力の可能性
ｄ）二項全域木の３ポインタ表現および実装
４．本発明の有効性は、合成ＩＰトレースおよび現実ＩＰトレースを使用するシミュレーションを通して実証される。そのために、以下が考慮される。すなわち、
ａ）スループット
ｂ）遅延統計
ｃ）メモリ・ユニットにわたる木ノード分布
ｄ）探索負荷分布
【００２２】
任意の種類のプレフィックス木を、本発明のＰＥの２次元配列上にマッピングすることができる。アーキテクチャの修正を必要とする二分探索木ではなく、二項全域木の使用により、ＳＡＡＦＦＩＬの利点に加えて、以下の利点がもたらされる。すなわち、
・より短い探索経路、したがってより短いパイプライン（スループットの利点）
・ＳＲＡＭに格納されるより少ない木ノード（メモリ・サイズ、したがってアクセス時間の削減）
【００２３】
二項全域木から利益を得るために、その効率的な実装を使用すべきである。本発明では、マルチポインタ二項全域木実装が、拡張として使用される。また、上述の提案されているアーキテクチャに対する他の拡張も、小さな修正と共に可能である。たとえば、このアーキテクチャは、特定のパイプラインに向かって探索要求を時間的に偏倚する処理をするために、キャッシュ使用に適している。また、ＰＥでのデュアル入力／出力ＳＲＡＭ使用に、また４側入力の可能性に適している。
【００２４】
本発明では、全体的に、探索エンジン、すなわちＳＡＡＦＦＩＬ−ＢＴが、高められた並列性および探索能力と共に得られ、基本発明のＳＡＡＦＦＩＬを含めて既存のアーキテクチャより高い性能をもたらす。シミュレーションでは、ＩＰルックアップのための高速ルータ・フロントエンドとして使用することができるＳＡＡＦＦＩＬ−ＢＴは、二項全域木および提案されている拡張の使用により、７Ｔｂｐｓの速度で動作することができることが示されている。本発明者らの知る限りでは、これは、あらゆる既存のＩＰルックアップ手法よりはるかに良好である。シストリック・アレイ構造における理論上の最悪ルックアップ遅延は高いが、平均遅延は非常に低く、大きな遅延が非常にまれに観測されるにすぎない。その新しい形態にある構造は、処理要素の点でスケーラブルであり、また、ＩＰｖ６アドレッシング方式に十分適したものである。
【００２５】
本書の残りの部分は、以下のように編成されている。すなわち、セクション２は、プレフィックス木探索に関する簡単な背景情報および既存のＳＲＡＭベースのパイプライン・アーキテクチャの再検討を提示する。セクション３は、高速ＩＰルックアップのための本発明のマルチパイプライン・シストリック・アレイ・アーキテクチャ（ＳＡＡＦＦＩＬ）を提示し、この構造についてその利点を強調して明らかにする。セクション４は、二項全域木を使用するためのＳＡＡＦＦＩＬの採用について述べ、ＳＡＡＦＦＩＬ−ＢＴを提示する。セクション５は、全体的な性能を改善するためのさらなる拡張を提示する。セクション６は、シミュレーション結果について論じ、本発明の性能を評価する。
【００２６】
本発明についてより詳細に述べるために、必要な図が用意され、本説明に添付されている。図の一覧および定義を下記に示す。
【図面の簡単な説明】
【００２７】
【図１Ａ】プレフィックス・テーブルの一例の図である。
【図１Ｂ】図１Ａにおけるプレフィックス・テーブルに対応するバイナリ・トライの一例の図である。
【図２】例示的なＳＲＡＭベースの並列パイプライン・アーキテクチャの図である。
【図３】例示的な４×４シストリック・アレイの図である。
【図４】４×４ＳＡＡＦＦＩＬの図である。
【図５】処理要素（ＰＥ）の図である。
【図６Ａ】初期区分の一例の図である。
【図６Ｂ】０１サブトライのマッピングの一例の図である。
【図６Ｃ】０スキップ・クラスタの図である。
【図７】５ビット・アドレス空間を有する二項全域木の図である。
【図８】ＢＴの二重根区分の一例の図である。
【図９】図８における上部ＢＴのＦＣＮＳ表現の図である。
【図１０】１０３．５４．１９２．０に対するＩＰ探索例の図である。
【図１１】２４ビット・ストリング内の「１」の数を「０」と比較するための回路の図である。
【図１２】２４ビット・ストリング内の最上位セット・ビット位置を見つけるための回路の図である。
【図１３】ｒ＝８であるセレクタ・ユニット（ＳＵ）の図である。
【図１４】４側４×４ＳＡＡＦＦＩＬ−ＢＴの図である。
【図１５】二項木表現の一例の図である。
【図１６Ａ】Ｔ４についてのＳＡＡＦＦＩＬ−ＢＴ−ｄ／ｆ／ｔにおける瞬間スループット変動の図である。
【図１６Ｂ】Ｔ５についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔにおける瞬間スループット変動の図である。
【図１７】Ｔ４についてのＳＡＡＦＦＩＬ−ＢＴ−ｄ／ｆ／ｔおよびＴ５についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔのシミュレーションのための遅延ヒストグラムの図である。
【図１８Ａ】Ｔ５についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔに関するＳＲＡＭにわたるトライ・ノード分布の図である。
【図１８Ｂ】Ｔ５についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔに関するＳＲＡＭにわたる探索負荷分布の図である。
【図１９Ａ】Ｔ４についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔに関する高速化対キャッシュ・サイズおよびＳＵの数の図である。
【図１９Ｂ】Ｔ４についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔに関する平均遅延対キャッシュ・サイズおよびＳＵの数の図である。
【発明を実施するための形態】
【００２８】
（表の簡単な説明）
本発明についてより詳細に述べるために、必要な表が用意され、本説明に添付されている。表の一覧および定義を下記に示す。
表１−プレフィックス・テーブルの一例を示す。
表２−図１５についてプレフィックスの探索経路長を示す。
表３−ＳＡＡＦＦＩＬ−ＢＴのスループットを示す。
表４−ナノ秒を単位とするＳＲＡＭアクセス時間推定値を示す。
表５−クロック・サイクルを単位とするＳＡＡＦＦＩＬ−ＢＴの平均ルックアップ遅延を示す。
表６−既存の並列アーキテクチャとの比較を示す。
【００２９】
（高速ＩＰルックアップのためのシストリック・アレイ・アーキテクチャ（ＳＡＡＦＦＩＬ））
シストリック・アレイは、データ処理要素（ＰＥ）の行列風パイプライン・ネットワーク構成である。これは、並列コンピューティングの専用化された形態であり、ＰＥは、データを計算し、それを処理の直後に隣接するＰＥと共有する。ＰＥは、中央処理装置と同様であるが、プログラム・カウンタを除く。なぜなら、動作が同期式であるがトランスポートトリガ型、すなわちデータ・オブジェクトの到着によるものであるからである。シストリック・アレイは、しばしば矩形であり、データは、その配列にわたって隣接するＰＥ間を流れ、しばしば異なるデータが異なる方向で流れる。外界との通信は、配列境界でのみ行われる。図３は、例示的な４×４シストリック・アレイを示す。
【００３０】
シストリック・アレイは、通常、コストがかかり、非常に専用化され、構築するのが困難であることが知られているが、同期、モジュール性、規則性、局所性、有限接続、並列パイプライン化、およびモジュール拡張可能性など、魅力的な特性を有する。
【００３１】
並列パイプラインを自然に実装するシストリック・アレイは、ＳＲＡＭベースの並列ＩＰルックアップにとって良好な候補であることに留意されたい。探索を高速化する、したがってルータのスループットを高めるために、図４に示されているシストリック・アレイのような編成を使用することが本発明で提案される。
【００３２】
この手法では、既存の１次元ＳＲＡＭベースのマルチパイプライン提案とは対照的に、探索プロセス中に、（東または南に向かう）多次元データ・フローがシストリック・アレイを通って存在することができ、このようにして、実際のＩＰトラフィック条件下でのパイプラインの利用が増大する。本発明では、図４に示されているように各行および列のエンドポイント間の接続を含むように、一般的なシストリック・アレイ構造が拡張される。したがって、プレフィックス木内の枝に対応するパイプラインを、対応する行または列の周りでラッピングすることによって、ＰＥの配列上にマッピングすることができる。セレクタ・ユニット（ＳＵ）が、新しい探索要求の開始ステージを指定する。複数の探索要求が入力ステージＰＥに到着することができるので、探索するためにあるＩＰアドレスをシステムに入れることができるように、コンテンション・リゾルバが必要とされる。各ＳＵは、他のすべてのＣＲに接続される。ＳＵの数は設計的事項であり、システムに入ることができる探索要求の最大数を定義する。各行および列のエンドポイントもまた、ＣＲに接続される。循環探索が存在する場合、ＳＵからの他の探索要求はＣＲによって受け入れられない。
【００３３】
バックプレーンは、（図４の場合のように）バックプレーンの単純化が望ましい場合、出力境界ＰＥだけからポート番号（次のホップ・ルータ）情報を得てもよく、配線の複雑さが問題でない場合、各ＰＥがバックプレーンにこの情報を提供してもよい。
【００３４】
（処理要素）
本発明のシストリック・アレイ内のＰＥは、図５に示されているように、ＦＩＦＯキュー・ブロックと、ＳＲＡＭメモリ・ユニットと、何らかの追加のコンピュータ論理とからなる。
【００３５】
各要素は、ＦＩＦＯキューに直接接続される２つの入力バス（北および西）を有する。２つの出力バス（東および南）が、隣接するＰＥに接続する。ＦＩＦＯキューは、１回のＳＲＡＭアクセス・サイクル中に、２つの探索要求が北入力および西入力からＰＥに同時に到着する可能性があるので使用される。ＦＩＦＯキューは、ＳＲＡＭ、およびいくつかの関連のレジスタを使用して実装することができる。１回のＳＲＡＭ読取りサイクルで、２つの要求をこのキューに挿入することができることが仮定されている。これは、ＦＩＦＯキューのサイズが、主ＳＲＡＭユニットのサイズに比べてはるかに小さくなるように選択されるので合理的である。ＦＩＦＯキューおよびＳＲＡＭブロックに加えて、各ＰＥは、ＩＰプレフィックス探索を次のステージにルーティングするために追加の組合せ回路を含む（図５）。システム・クロックごとに、北および／または西（データが使用可能な場合）から到着する２つの新しいフレーム（探索されるＩＰアドレス・ビットに追加のアーキテクチャ上のデータを加えたもの）をキューに挿入することができ、ＦＩＦＯキュー（空でない場合）から取り出されたフレームをＳＲＡＭブロックに提供することができ、次いでＳＲＡＭブロックは、それを変換し、次のステージの東または南のＦＩＦＯキューの入力にルーティングする。任意の２つのＰＥ間の接続（並列で転送されるフレーム）は、２ｎ×（２ｎ＋ｍ＋１）ビットのＳＲＡＭについて、（２４＋ｎ＋ｍ）ビット幅のデータ・バスからなり、最後のビットはデータ可用性（ＤＡＶ）信号である。最上位の２４データ・ビットは、探索されるキー（ＩＰアドレス）の最下位２４ビットであり、次のｎビットが、次のステージのＳＲＡＭユニット内でアクセスされるアドレスに使用され、最後のｍビットが、ポート番号情報を転送するために使用される。図５は、ｎ＝１２、ｍ＝５と仮定する。探索パケットは、探索が終了したとき最後のステージから引き返さないように、各トラバースされたＰＥを介した最後の最長一致ポート番号を担持する。ポート番号フィールドは、ＳＲＡＭブロックのいくつかにおいて更新されてもよい。このようにして、最後のステージに一致がない場合、最長一致に対応する以前の一致で更新されたポート番号が、探索の最後のステージで、引き返すことなしに得られる。
【００３６】
現在のステージに対応するＩＰアドレス・ビットにより、次のホップが南になるか東になるかが決まる。各ＳＲＡＭユニットは、南および東の隣接ＳＲＡＭインデックスの２つのｎビットと、ｍビットのポート番号フィールドと、有効ビット（現在の木ノードがプレフィックス・ノードであるか、それとも中間ノードであるかを示す）とを有する（２ｎ＋ｍ＋１）ビットを各エントリに格納する。
【００３７】
葉にプッシュされるトライが使用される場合、葉でないノードは、その子へのポインタだけを含み、葉ノードは、ポート番号だけを含むので、（２ｎ＋１）ビット幅のＳＲＡＭを使用すれば十分となる。次いで、サブセクション３．３で述べるように、適切なプレフィックス探索木マッピング方針を使用して、転送テーブルが構築される。
【００３８】
（輻輳制御機構）
交差するパイプライン上でのリソース使用の衝突は各ＰＥ内のキューを使用して処理されるので、キューのオーバーフローによるパケット損失の可能性がある。単純な輻輳制御機構を使用することができる。１つの可能性は、ＡＩＭＤ（ａｄｄｉｔｉｖｅ  ｉｎｃｒｅａｓｅ  ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｄｅｃｒｅａｓｅ）方針である。ＦＩＦＯキューの占有が、予め定義された閾値を超えた場合には、ＳＵの半分を非活動化し、システム全体の入力での負荷を低減する。一方、キューの占有が閾値未満である場合には、すべてのＳＵが再び活動状態になるまで各クロック・サイクルで１つだけ活動状態のＳＵの数を増加させることができる。
【００３９】
（木マッピング）
ＰＥへのプレフィックス木マッピングは、重要な問題である。ステージ全体わたって不均衡な木ノード分布は、全体的な性能を低下させるおそれがある。なぜなら、システムのクロック・レートがステージのメモリ・アクセス時間に密接に依存しており、メモリのアクセス時間はそのサイズに比例するからである。メモリが大きいほど、メモリのアクセス時間は遅くなる。
【００４０】
木マッピングは、２つのステージで行われる。
【００４１】
１．初期区分：パイプライン型アーキテクチャでは、プレフィックス探索木が別々のメモリ・ブロック上に区分され、これらのメモリ要素に対して複数のサイクルでトライ・トラバースが実施される。ＰＥ内のメモリ・ユニットまたはＳＡＡＦＦＩＬ内のステージもまた、そのような木ノードを格納するために使用される。並列パイプラインを利用するためには、二分探索木を別々のサブツリーに分割しなければならない（初期区分と呼ばれる）。どのプレフィックス探索木タイプ（たとえば、バイナリまたは二項）を使用するとしても、環状パイプラインおよび初期区分を使用することは、パイプライン・ステージ上の木ノードの平衡分布をもたらす助けとなり得る。
【００４２】
先の業績と同様に、本発明の区分方針は、プレフィックスのいくつかの初期ビットを、トライを互いに素なサブトライに区分するためのインデックスとして使用することである。この目的に使用されるｒ個の初期ビットは、初期ストライドと呼ばれる。初期ストライド値がサブトライを定義し、したがって、次いで２ｒ個の可能なサブトライをパイプライン上にマッピングすることができる。図６ａは、ｒ＝２の場合のバイナリ・トライに対する初期区分を示す。
【００４３】
２．サブトライ・マッピング：サブトライが入力ステージの数より多い可能性がある。適切な方針内で初期ストライド値を使用し、対応するサブトライの根が格納される開始ステージＰＥを決定することができる。その後で、単に各サブトライ・ノードを、連続するＰＥ内に格納することによって、ノードからステージへのマッピングを行うことができる。図６ｂは、そのようなサブトライ（たとえば、サブトライＩＤ０１）を３×３ＳＡＡＦＦＩＬで対応するＰＥにマッピングするところを示す。この例示的なマッピングでは、対応するプレフィックス・ビットが０である場合には、次の木ノードが南の隣接ＰＥに格納され、そうでない場合には、東に格納される。境界ＰＥ間の環状接続が許されないならば、そのようなマッピングは可能でないことになろう。
【００４４】
第３のレベルの区分（０スキップ（または１スキップ・）クラスタリング）が導入される場合、プレフィックスの先頭の０（または１）をスキップすることも可能である。その詳細については後述するが、図６ｃは、１０サブトライだけについて０の場合を示す。
【００４５】
サブトライをＰＥに２次元でマッピングすることにより、あるレベルの偶然性がもたらされ、したがって、既存の手法と異なり、ＳＲＡＭユニットにわたって木ノード分布を平衡させるために、余分な努力が必要とされない。
【００４６】
（ルックアップ・プロセス）
ＩＰルックアップ・プロセス（探索要求）は、セレクタ・ユニットで始まる。次いでこのＳＵは、探索されたキーの初期ストライドを使用して、入力ステージＰＥ、およびこのＰＥ内の対応するサブトライの根のメモリ・アドレスを見つける。
【００４７】
同じ入力ステージＰＥに複数の同時の探索要求が到着した場合には、それらの要求の１つがＣＲによって選択され、他の要求は、任意の適切な方針を使用して保留にされる。循環探索がある場合、他の探索要求は、対応するＣＲによって受け入れられず、循環探索が、ＰＥに対して許されているその動作を継続する。保持状態にあるＳＵは、その現在の要求を保留のまま保ち、新しい要求を受け入れることができず、次のサイクルで同様に競争する。ＣＲは、それらの勝者の探索要求をそれらの入力ステージＰＥに入れる。次いで、初期ストライド以外のビットを使用して、探索が他のＳＡＡＦＦＩＬステージを通って流れる。ＩＰアドレスの対応するビットが０である場合には、次のホップが南に向かい、そうでない場合には、東に向かう。格納されたプレフィックス・ノードが有効である、すなわち探索木内で着色されている場合、各ＰＥを介して、トラバースするフレーム内の５ビット・ポート番号フィールドが更新される。葉にプッシュされるトライの場合、ポート番号は、葉ノードだけから得られる。換言すれば、ＬＰＭは、そのようなトライに対する各パイプラインの最後のステージでのみ見つけることができる。
【００４８】
（ＳＡＡＦＦＩＬの利点）
既存のＳＲＡＭベースの手法に比べたＳＡＡＦＦＩＬの主な利点は、以下のように列挙することができる。
・探索エンジンへの要求入口点の数が増大され、したがって入力コンテンションが低減される。交差するパイプライン上でのリソース（ＰＥ）使用衝突は、各ＰＥ内のＦＩＦＯキューを使用して処理される。
・境界以外の任意のステージからの出口点を設け、動作するパイプをより短く保つことにより、既存のアーキテクチャと異なり、他の並列探索動作のためのリソース可用性が高まる。
・プレフィックス・サブツリーをＰＥに２次元でマッピングすることにより、あるレベルの偶然性がもたらされ、したがって、既存の手法と異なり、ＳＲＡＭユニットにわたって木ノード分布を平衡させるために、余分な努力が必要とされない。
・提案されているアーキテクチャは、ＰＥの数の点でスケーラブルであり、したがってＩＰｖ６アドレッシング方式に十分適したものである。プレフィックス長がより大きく、たとえばＩＰｖ６の場合のように１２８になった場合、ＰＥ内のメモリ・ユニットのサイズ、ＰＥ内のＦＩＦＯキューの幅、およびＰＥ間の接続の幅だけ増大させる必要がある。ＰＥの数、およびそれらの編成は、変えずにおくことができる。
【００４９】
（高速ＩＰルックアップのためのシストリック・アレイ・アーキテクチャ（ＳＡＡＦＦＩＬ−ＢＴ））
Ｃｈａｎｇ［２６］は、バイナリ・トライに似ているが、メモリ要件およびルックアップ時間の点で性能がより良好な、単純な探索および更新プロセスを有する二項全域木ベースのＩＰルックアップ手法を提案している。バイナリ・トライではなく二項プレフィックス木を使用することは、メモリ使用が少ないことに加えて、スループットの点で著しい性能上の利点をもたらすことができるが、ＳＡＡＦＦＩＬの一部の修正を必要とし、したがってＳＡＡＦＦＩＬ−ＢＴとなる。二項プレフィックス木の効率的な実装もまた、明らかに有益である。
【００５０】
（二項トライ）
図７は、木の各ノードが一定の長さのバイナリ・アドレスを有する５ビット二項全域木を示す。
【００５１】
ノード・アドレス内に同数の「１」ビットを含むノードが、二項全域木の同じレベルにある。換言すれば、二項全域木内のあるノードのレベルは、そのノード・アドレス内の「１」ビットの数によって決まる。それらのノードのいくつかがプレフィックス・ノードとしてマークされ、未使用のノードがバイナリ・トライの場合のように削除された場合には、この構造は、二項プレフィックス木（本文を通して略して二項トライ）と呼ばれる。同様に、ＢＴでは、探索プロセスを通してトラバースされるノードの数は、ノード・アドレス内の「１」の数によって決まる。したがって、ＢＴ内の探索動作は、バイナリ・トライ内のものとは異なる。たとえば、最良一致プレフィックス（ＢＭＰ）が５ビット・アドレス空間内で０１０１０／５である場合、根とＢＭＰノードの間の距離は、２ホップにすぎない。すなわち、ノード・アドレス０００００、０１０００、および０１０１０が訪問されるだけである（図７）。
【００５２】
（二項トライ・ベースの転送テーブル）
バイナリ・トライからそのＢＴ表現への変換は簡単である。初期プレフィックス・テーブルを使用して、新しいテーブルが生成され、この新しいテーブルを使用してＢＴが構築される。ＢＴアドレス・テーブルと呼ばれる新しいプレフィックス・テーブルは、「０」（または「１」）をすべてのプレフィックスに付加することによって得ることができる一定の長さのプレフィックスを含むべきである。たとえば、「０」を付加する場合、プレフィックス０１１＊および１０＊が、５ビット・アドレス空間内でそれぞれ０１１００および１００００に変換されることになる。しかし、「０」（または「１」）を付加することにより、衝突が発生する可能性がある。すなわち、複数のプレフィックスをＢＴの単一のノード上にマッピングすることができる。プレフィックス０１＊および０１０＊は、上記の手法で５ビットＢＴ内の同じノード０１０００上にマッピングされることになる例である。そのような衝突するプレフィックスを処理するために２つの解決策を使用することができる［２６］。第１の解決策は、衝突するプレフィックスを格納するために追加のプレフィックス配列を使用することである。第２の解決策は、複数のプレフィックスを格納するＢＴノードがないように、長さの短い衝突するプレフィックスを、より長いものに伸長することである。第１の手法は、更新がより単純であるという利点を有し、一方、プレフィックス伸長では、追加のプレフィックス配列が必要とされない。しかし、本発明では、最小独立プレフィックス・セット（ＭＩＰＳ）アルゴリズム［２７］［２８］の使用が好ましい。これは第２の手法のより複雑なバージョンであるが、独立プレフィックスを生成しながら、転送テーブルに対してメモリ圧縮をももたらす。次いで、ＭＩＰＳ出力が、ＢＴの構築に使用される。
【００５３】
（二項木マッピング）
二項木マッピングは、３つの主なステップからなる。
【００５４】
１．初期区分は、元のバイナリ・トライに対してセクション３．３で述べたように行われる。
【００５５】
２．二重根区分：本発明では、ＢＴノードを２つのグループに分割することができることに留意されたい。一方のグループは、アドレス内により多くの「０」ビットを有するノードを含み、他方のグループは、残りのもの（アドレス内により多くの「１」ビットを有する）を含む。たとえば、図７では、第１のグループ（上部ＢＴ）がレベル０、１、２にあるノードを含み、一方、他方のグループ（下部ＢＴ）がレベル３、４、５にあるノードを含む。
【００５６】
ＢＴは、両区画を、元の深さの約半分である別個の、しかし同様のＢＴとして表すことができるという良い特性を有する。根ノード・アドレスは、一方のＢＴでは、すべて「０」であり、他方では、すべて「１」である（図８でわかる）。本発明では二重根区分と呼ばれるこの手法は、プレフィックス探索に対して著しい深さの利点をもたらす。二重根区分は、ＢＴだけでなくＢＴの任意のサブトライに適用可能であり、したがって、バイナリ・トライの初期区分の結果として得られる各プレフィックス・テーブルについて、２つの別々のＢＴを構築することができる。
【００５７】
二重根区分からより多くの利益を得るために、この部では、先のサブセクション４．２で述べたプレフィックス変換ステップの、以下の修正が提案される。この修正では、プレフィックス内の「１」の数と「０」の数との差が、以下のように使用される。
プロシージャＰｒｅｆｉｘＣｏｎｖｅｒｓｉｏｎ
入力：プレフィックスｐ１ｎ１：ｐ１ｎ０内の「１」の数：ｐ１ｒ内の「０」の数：初期ストライド
出力：ｑ＝｛ｑ１，ｑ２｝  式中ｑ１およびｑ２は、３２ビットＢＴノード・アドレス
１：ｉｆ｜ｎ１−ｎ０｜<（３２−ｒ−ｌｅｎｇｔｈ（ｐ））  ｔｈｅｎ
２：ｑ１＝ｐ＋０（３２−ｒ−ｌｅｎｇｔｈ（ｐ））；「０」をｐに付加する
３：ｑ２＝ｐ＋１（３２−ｒ−ｌｅｎｇｔｈ（ｐ））；「１」をｐに付加する
４：ｑ＝｛ｑ１，ｑ２｝
５：ｅｌｓｅ
６：ｉｆ（ｎ１−ｎ０）>０  ｔｈｅｎ
７：ｑ１＝ｐ＋１（３２−ｒ−ｌｅｎｇｔｈ（ｐ））；「１」をｐに付加する
８：ｅｌｓｅ
９：ｑ１＝ｐ＋０（３２−ｒ−ｌｅｎｇｔｈ（ｐ））；「０」をｐに付加する
１０：ｑ＝｛ｑ１｝
１１：ｅｎｄ
【００５８】
上記の方法では、プレフィックスのいくつかには、すべて「１」が付加され（７行目）、いくつかには、すべて「０」が付加され（９行目）、いくつかは両方である（２〜３行目）。
【００５９】
本発明では、あるノードのレベルは、プレフィックス内の「１」の数（上部ＢＴ内）および「０」の数（下部ＢＴ内）によって決まることに留意されたい。本発明における新しい手法は、プレフィックス変換をより賢明にすることにより、平凡な手法に比べて、プレフィックスが、その対応するＢＴ内でより良好なレベルに配置されることを保証する。たとえば、プレフィックス１０１１１＊は、本発明を使用して、７ビット・アドレス空間内でバイナリ・アドレス１０１１１１１に変換されることになり、次いでこれは、下部ＢＴのレベル１に格納されることになる。しかし、平凡な「０」を付加する場合には、この変換は１０１１１００になり、次いでこれは、同じ区画のレベル３に格納されることになろう。このようにして、プレフィックス１０１１１＊に到達するために必要とされるメモリ・アクセスの数は、３から１に削減されることになる。
【００６０】
表１および図８は、単純な二重根区分の例を示す。表１列は、プレフィックス、およびそれらの関連のポート番号を与える。第１列に示されている元のプレフィックス・テーブルが、最初にＭＩＰＳアルゴリズムに適用される。次に、得られる互いに素なプレフィックス・セット（第２列）が、上記のプレフィックス変換アルゴリズムを使用してＢＴアドレス・テーブル（第３列）に変換される。次いで、プレフィックスに対応する５ビットの一定の長さのアドレスを含むこの最終テーブルが、図８の場合のように、２つの別々のＢＴ（上部および下部のＢＴまたは区画）を構築するために使用される。破線のノードは、これらの二項全域木ノードが代表ＢＴ内のメモリ内に格納されず、例示のためだけに図に含まれていることを示す。
【００６１】
【表１】
0005529976.tif 000003
【００６２】
二重根区分のために、探索深さが削減される。この利点は、実装ではある程度失われるが、スループットで表した探索性能は、依然として著しく高められる可能性がある。
【００６３】
二項木では、ノードの子の数が固定でない。そのような木構造は様々な方法で実装することができ、その１つは、ＦＣＮＳ（ｆｉｒｓｔ−ｃｈｉｌｄ−ｎｅｘｔ−ｓｉｂｌｉｎｇ）表現である。ＢＴアドレス・テーブルのサイズの膨張（複製による）はあるが、得られる二項サブトライは、元のバイナリ・トライに比べて、トライ・ノードおよびリンクの数が少ない。
【００６４】
３．サブツリー・マッピング：ＦＣＮＳ表現を使用し、ＢＴを実装する。図９に示されているように、あらゆるノードが、その最も右側の子、およびその次（最も近い左）の兄弟とリンクされる。
【００６５】
ＢＴ上での探索中にトラバースされるノードの数は、ノード・アドレス内の「１」の数によって決まり、一方、上部（下部）ＢＴのＦＣＮＳ表現内の最初のビットと最後のセット（リセット）ビットとの間のビットの数によって決まる。ＦＣＮＳ経路長が長くなることを埋め合わせるために、本発明でＢＴクラスタリングと呼ぶ第３のレベルの区分が導入される場合、本発明では、探索キーの先頭のいくつかの０をスキップすることができることに留意されたい。ＢＴクラスタリングは、上部ＢＴと下部ＢＴに共に適用することができる。以下では、ＢＴクラスタリングについて、上部ＢＴだけに関して論じる。下部ＢＴについては、「セット・ビット」という表現を「リセット・ビット」で、また「西」を「北」側で置き換える必要がある。
【００６６】
ＢＴクラスタリングでは、ＢＴの根ノードが除去され、したがって、より小さな、互いに素なＢＴ（クラスタ）が生じる（たとえば、図８における区画１内の４つのクラスタ）。各クラスタの根ノードは、以前、ＢＴの第２のレベル内にあり、各クラスタは、クラスタ・メンバのノード・アドレスの最上位セット・ビットが同じ位置にあるように特徴付けられる。
【００６７】
次いで、上部ＢＴクラスタが西側から、また下部ＢＴが北側から開始して、ＳＡＡＦＦＩＬ−ＢＴにマッピングされる。ＢＴクラスタが入力ステージの数より多い可能性がある。マッピングは、入力での負荷平衡が達成され、同時に入力ステージＰＥインデックスおよび対応するクラスタの根メモリ・アドレスが、ＩＰルックアップが始まる前に、容易に計算されるように行われるべきである。１つのそのような方針、ならびにその対応するインデックスおよびアドレス公式を下記に示す。
ｒ：初期ストライド
ｑ：サブツリーＩＤ（初期ｒビットの十進法の等価量）
ｘ：残りの（３２−ｒ）ビット内の最も左側のセット・ビット位置
ｎ：西側における入力ステージＰＥの数
ｍ：ＢＴベース・インデックス
ｗ：入力ステージＰＥインデックス
ｐ：上部ＢＴクラスタのための根メモリ・アドレス
【００６８】
合計では、２ｒ×（３２−ｒ）個のクラスタＢＴがある。ｑは、初期区分によるグループ・インデックスである。ｘは、ＢＴクラスタ・インデックスであり、ｍは、ある特定のグループｑの最初（ｘ＝０）のクラスタに関する入力ステージＰＥインデックスである。したがって、ｘが、ＢＴベース・インデックスからのオフセットとして使用される。
【００６９】
例外として、残りの２４ビットにすべて「０」または「１」を有するプレフィックス（ｘ．０．０．０またはｘ．２５５．２５５．２５５）は、ＳＵ内でサイズが５１２行の小さなハッシュ・テーブル内に格納すべきであり、そのようなＩＰアドレスについてのみ、ルックアップは、これらのテーブルだけに対して実施すべきである。
【００７０】
ノードからステージへのマッピングは、各クラスタ・ノードを、連続するＰＥ内に単に格納することによって行われる。対応するアドレス・ビットが０である場合には、次のノードが南の隣接ＰＥに格納され、そうでない場合には、東に格納される。このノードからステージへのマッピングは、下部ＢＴクラスタについても上部ＢＴクラスタについても同じである。
【００７１】
ルーティング・テーブル更新は、他の既存のパイプライン・アーキテクチャの場合のように処理することができる。この要件に関して、特別な「更新」パケットが、ルックアップの場合と同様にして、しかしＰＥに追加された追加的な特別設計の論理ユニットを介して、パイプラインをトラバースすることができる。各ルート更新は、いくつかの書込みメッセージを有することができる。最後に、経路上の対応するＰＥが、それらの関連のメモリに対して「書込み」コマンドを発行する［２０］。本書の残りの部分は、話を簡単にするために、更新問題についてこれ以上考察しない。
【００７２】
（ルックアップ・プロセス）
先のサブセクションの場合のように、話を簡単にするために、ＩＰルックアップについて、上部ＢＴだけにおいてキー値に関して論じる。下部ＢＴのキー値については、「セット・ビット」という表現を「リセット・ビット」で、また「西」を「北」側で置き換える必要がある。
【００７３】
探索プロセスでは、トラバースされるノードの数が、最上位セット・ビットと最下位セット・ビットの間のビットによって決まる。ＩＰルックアップは、使用可能な（非保持状態）セレクタ・ユニット（ＳＵ）から始まる。ＳＵは、入力側を西または北として指定する。次いで、ＳＵは、式１〜４を使用して、入力ステージＰＥインデックスと、対応するクラスタの根メモリ・アドレスとを計算する。さらに、ＳＵは、探索キーがトラバースすることになるＰＥホップの最大数を見つけ出し、対応するＣＲを介して探索を開始する。ＣＲは、サブセクション３．４で述べるように動作する。
【００７４】
図１０は、１６×１６ＳＡＡＦＩＬ−ＢＴ上の例示的なＩＰアドレス１０３．５４．１９２．０に対するルックアップ・プロセスを示す。
【００７５】
初期ストライドが８の場合（初期区分による）、ＩＰアドレス１０３．５４．１９２．０は、残りの２４ビットにおいて０の数が１の数より多いので、上部ＢＴクラスタに対応する（二重根区分による）。最上位セット・ビットおよび最下位セット・ビットのビット位置は、それぞれ２および９である。入力ステージＰＥインデックスは９であり、対応するクラスタの根メモリ・アドレスは１０３である。最後に、探索がトラバースすることができるホップの最大数は、９−２＝７である。
【００７６】
入力ステージＰＥを見つけた後で、最上位セット・ビットと最下位セット・ビットの間のビット値に応じて、探索が東または南に向かって継続する。
ｍ（ｑ，ｎ）＝ｑ  ｍｏｄ  ｎ          （１）
ｗ（ｑ，ｘ，ｎ）＝（ｍ＋ｘ）ｍｏｄ  ｎ          （２）
ｋ（ｒ，ｎ）＝（（３２−ｒ）＋ｎ）／ｎ          （３）
【００７７】
【数２】
0005529976.tif 000004
対応するビットが「１」である場合には、東の隣接ノードが次のノードであり、そうでない場合には南である。図１０は、入力ステージＰＥを行インデックスおよび列インデックスでのみマークしており、この例示的な探索は、ＰＥ（１１，５）で終了し、パイプラインのこのステージでの有効プレフィックスを想定している。
【００７８】
ＳＡＡＦＦＩＬ−ＢＴは、わずかに修正されたＰＥ論理ユニットを有し、その結果、トラバースするフレームが、追加の５ビット・ホップ・カウンタ、単一ビットのパケット・タイプを含み、以下の機能が実装される。トラバースするパケットに残されているＰＥの数を示すホップ・カウンタ値が、各ホップで増分される。パケット・タイプは、パケットが上部ＢＴクラスタに属するか、それとも下部ＢＴクラスタかを示し、この情報は、ノードを訪問している間に、フレーム内のポート番号フィールドが更新されるか否か判定するために使用される。ポート番号フィールドは、パケット・タイプが０（下部ＢＴクラスタ）であり、次のノードへの移行が東に向かう場合、またはパケット・タイプが１（上部ＢＴクラスタ）であり、次のノードへの移行が南に向かう場合、有効プレフィックス・ノードにおいて更新される。ルックアップの最後のステージは、最長一致規則によって指定される。最後のステージで有効プレフィックスが見つからない限り、最長一致プレフィックスは、最後の「１回」（東行き）の移行の１つ前であり、ポート番号は、最後に更新されたものである。たとえば、図１０では、最長一致プレフィックスは、最後のステージ（１１，５）内のプレフィックスが有効なものでなかった場合、座標（１１，４）にあるものとなる。
【００７９】
（セレクタ・ユニット）
セレクタ・ユニットは、探索キーを入力する組合せ論理回路である。各セレクタから各ＣＲへの経路がある。セレクタ・ユニットの数ｎは、ＳＡＡＦＦＩＬ−ＢＴの性能に密接に影響を及ぼす。なぜなら、サイクルあたり、最大ｎ個の探索要求がシステムに入ることができるからである。ＳＡＡＦＦＩＬ−ＢＴ用のセレクタ・ユニットは、バイナリ・トライ用のものより複雑である。ＳＵは、以下の機能を実装する。
−  ＩＰアドレスの残りの２４ビット内の１と０の数を比較することによって、入力側（パケット・タイプ）を西または北として指定する（図１１は、２４ビット・ストリング中の１と０の数を比較する論理回路のブロック図を示す）。
−  キーの最上位セット・ビットまたはリセット・ビットのビット位置を使用することによって、入力ステージおよび根メモリ・アドレスを見つける（図１２は、２４ビット２進数における最上位セット・ビットのビット位置を見つける論理回路のブロック図を示す）。
−  最下位セット・ビットのビット位置またはリセット・ビット位置を加えて使用することによって、ホップの最大数を計算する。
【００８０】
ＳＵの全体的なブロック図を図１３に示す。
【００８１】
（ＳＡＡＦＦＩＬ−ＢＴの拡張）
（キャッシュ使用）
キャッシュ・ユニットは、短期的なトラフィックの偏倚を処理するために並列アーキテクチャで一般的に使用される。入力トラフィックが（バースト期間内に）数ステージだけに偏倚されたとき、並列性が低下する。キャッシングは、そのような期間内の性能劣化を防止する。
【００８２】
文献内の並列アーキテクチャ（ＴＣＡＭおよびＳＲＡＭベースのもの）は、キャッシングをそれらの構造の一部とみなし、［１３］［１６］では、キャッシュ使用がそれらの性能を著しく高めることが実証される。一方、ＳＡＡＦＦＩＬ−ＢＴは、キャッシュなしでより高い性能を有することを目的とする。しかし、適切なキャッシング方式を用いて拡張することは依然として可能である。以下のように、２つの代替を使用することができる。
【００８３】
ＰＰＭ（ｐｏｐｕｌａｒ  ｐｒｅｆｉｘ  ｍａｔｃｈｉｎｇ）［１３］：この手法では、小さなキャッシュ・ユニット（ＰＰＭ）がＳＵ内で維持され、最も人気のあるプレフィックスが格納される。入来するパケットは、このキャッシュ内で最初に探索される。ヒットした場合には、パケットがバックプレーンに直接転送され、そうでない場合には、対応する並列アーキテクチャ内の探索プロセスが開始される。２つ以上のパケットが同じ入力ステージに転送されるときはいつでも、コンテンションが発生する。次いで、このコンテンションは、キャッシュにプレフィックスを配置するプロセスをトリガする。このタイプのキャッシングは、いくつかの更新上の難点を有する。
【００８４】
バイナリ・トライ実装では、親プレフィックスをキャッシュ・ユニットに書き込む際に、時間のかかる計算が必要とされる。子プレフィックスと一致する入来ＩＰアドレスもまた、その先祖プレフィックスと一致するが、最長一致プレフィックスを見つけなければならない。先祖プレフィックスがキャッシュ内に存在する場合、それに一致するＩＰアドレスは、依然としてより長い一致をキャッシュの外で有する可能性がある。したがって、先祖プレフィックスをキャッシュ・ユニットに直接書き込むことはできず、先祖プレフィックスの拡張をキャッシュに配置すべきである。この問題は、ＢＴ実装には存在しない。なぜなら、ノード・アドレスすべてが等しい長さを有し、プレフィックスではなくＩＰアドレス全体をキャッシュすることができるからである（ＩＰアドレス・キャッシング）。
【００８５】
ＴＣＡＭベースの並列アーキテクチャでは、キャッシュ配置は、コンテンションに続く次のサイクルで始まる。ＳＲＡＭベースの並列パイプライン・アーキテクチャでは、しばらくしてからルックアップ結果が取り出されるため、キャッシュ配置を開始するのに、より時間がかかる。パイプライン長がフローのバースト長より長い場合、フローのパケットすべてがキャッシュをミスするが、キャッシュ配置は役に立たないものになる。
【００８６】
２．フロー・プレキャッシング［２２］：この手法では、フローのＩＰアドレスが、そのポート番号情報が取り出される前にキャッシュされる。到着するパケットがキャッシュされたフローに一致する場合、対応するフローＩＤがそのパケットに割り当てられ、そのパケットは、どのような演算をも実施することなしに最小限の負荷でパイプラインをトラバースする。ポート番号は、最後にアウトバウンド・フロー・テーブルから取り出される。
【００８７】
到着するパケットがキャッシュされたフローのどれにも一致しない場合、選択された入力ステージに向けて送られ、ルックアップが始まり、インバウンド・フロー・テーブル（フロー・キャッシュ）がフローＩＤだけを使用して更新される。パケットがパイプラインを出るとき、探索結果をアウトバウンド・フロー・テーブルに書き込み、次いでこのテーブルがフローの残りの部分によって使用されることになる。
【００８８】
キャッシュが使用されない場合、フロー内パケット順序は保存されるが、どのようなタイプのキャッシュ使用も、明らかに適切な再順序付け機構を必要とする。
【００８９】
（デュアル入力／出力ＳＲＡＭ使用）
ＳＡＡＦＦＩＬ−ＢＴにおけるＰＥ内のＳＲＡＭを、スループットを高めるように２つのキーを一度に処理することを可能にするデュアル入力／出力ＳＲＡＭと置き換えることができる。そのためには、ＳＲＡＭのメモリ・サイズを変えずにおきながら、ＰＥ内の論理ユニットだけを修正すべきである。
【００９０】
（デュアル入力／出力ＳＲＡＭを用いた４側ＳＡＡＦＦＩＬ−ＢＴ）
ＳＡＡＦＦＩＬ−ＢＴもまた、図１４に示されているように４側入力境界を有することができるように拡張することができる。
【００９１】
このようにして、入力ステージＰＥの数が、組合せ論理の２倍の増大と引き替えに２倍になる。この拡張では、ＰＥ間の双方向リンクが必要とされる。各ＰＥが４つの隣接ノードから探索要求を受け、一度に２つを処理し、トラバースするフレームを、その４つの隣接ノードの２つに再び転送する。どのキューから２つのトラバースするフレームがフェッチされることになるかは、適切なスケジューリング・アルゴリズムによって決まる。探索側を西（北）または東（南）として指定するために、初期ストライド値を使用することができる。
【００９２】
（３ポインタの場合）
ＰＥの可用性はパイプラインの長さに密接に依存するため、パイプラインをより短くすることは、ＳＡＡＦＦＩＬの性能にとって重要である。セクション４．３の使用では、ＢＴを実装するためにＦＣＮＳ表現が提案されていた。これはバイナリ・トライより良好に動作するが、ＦＣＮＳは、ＢＴのより短い探索経路の利点をある程度失わせる。その代わりに、本発明では、ＢＴの３ポインタ表現を使用する改良が提案される。組合せ論理の小さな修正にもかかわらず、この拡張ではメモリ・サイズが減少し、二重根区分からより多くの利益が得られる。図１５は、２ポインタ表現および３ポインタ表現の場合の例示的なＢＴを示す。
【００９３】
各子には、最も右側の子から０で始まるＩＤが割り当てられる。ｓは、第３のポインタが指す子ノードのインデックスである。換言すれば、ｓは、上部ＢＴについてプレフィックス内の「１」ビットの後でスキップされる、連続する「０」の長さ、および下部ＢＴについて「０」ビットの後でスキップされる、連続する「１」の長さを示す。図１５ｃでは、ｓは２であり、したがって第３のポインタは、右から３番目の子を指す。
【００９４】
パイプライン長を短縮することに加えて、３ポインタ使用はまた、ノードまたはポインタの数の削減をもたらす。表２は、それぞれ２ポインタ表現および３ポインタ表現の場合の、図１５におけるプレフィックスの探索経路長を示す。
【００９５】
【表２】
0005529976.tif 000005
【００９６】
この例の場合、３ポインタ表現は、合計の探索経路長において約２３％（７０から５４へ）の削減をもたらす。また、この表は、３ポインタ表現が使用された場合、二重根区分の利益が増すことを示す。２ポインタの場合には、二重根区分の使用により、合計のプレフィックス探索長が約１４％（７０から６０へ）減少し、一方、３ポインタの場合には、この減少は２６％（５４から４０へ）である。
【００９７】
この拡張は、余分なポインタ記憶を必要とすることによりＳＲＡＭサイズを増大させることはないが、メモリ・ユニットにわたって木ノード分布に影響を及ぼす可能性がある。それに応じてトラバースするフレームのサイズを更新すべきであり、そのような状況では適切な論理を設計すべきである。
【００９８】
（シミュレーション結果）
Ｖｉｓｕａｌ  Ｃ＋＋を使用してＳＡＡＦＦＩＬ−ＢＴをシミュレーションする。対応するルーティング・テーブルに関連付けられたパブリックＩＰトレースが使用可能でないため、本発明のシミュレーションで使用されるＩＰパケット・トレースを生成するために、２つの方法に従った。第１に、［２９］からの使用可能な現実バックボーン・ルーティング・テーブルを使用することによって、３つのパケット・トレースが生成された。これらの合成により生成されたパケット・トレースは、間隔［１，ｋ］で均一に分配されたバースト長を有し、ｋは、Ｔ１、Ｔ２、Ｔ３の場合についてそれぞれ２、５、１０として選択される。第２に、［３０］からの現実バックボーンＩＰパケット・トレースＴ４、Ｔ５の対応するルーティング・テーブルが、現実プレフィックス長分布［２９］を使用することによって構築された。
【００９９】
シミュレーションは、３２個以下のセレクタ・ユニットを有する１６×１６ＳＡＡＦＦＩＬ−ＢＴについて実施された。ＣＲ方針として、単純な優先度ベースのスケジューリング機構を使用する。シミュレーションはキャッシュあり、キャッシュなしで実施する。使用するとき、キャッシュ・サイズは５０と仮定する。小さいＣＡＭを有するキャッシュを実装することができるので、キャッシュ探索は、単一のクロック・サイクルで実施されるものと仮定することができる。
【０１００】
ＦＩＦＯキュー・サイズおよび輻輳制御のための閾値は、それぞれ３０および１０として選択される。初期ストライド値は、８として使用される。二重根区分では、各区画内のプレフィックスの数を平衡させるために、トライ分割レベルを上げることも下げることもできる。本発明のシミュレーションでは、この分割レベルは、Ｔ４およびＴ５に関して、２側ＳＡＡＦＦＩＬ−ＢＴについてＢＴの第７レベル、４側拡張についてＢＴの第５レベルとして選択される。この分割レベルは、Ｔ１、Ｔ２、Ｔ３の場合に関して、２側ＳＡＡＦＦＩＬ−ＢＴおよびその４側拡張の両方についてＢＴの第３レベルとして選択される。４側ＳＡＡＦＦＩＬ−ＢＴでは、探索側を西（北）または東（南）として指定する際に、初期ストライド値が以下のように使用された。すなわち、初期ストライド値の十進法の等価量が、Ｔ１、Ｔ２、Ｔ３について１００（Ｔ４およびＴ５について８５）より高い場合には、探索側が東、そうでない場合には西として選択される。２つのキューのいずれかを選択するためにラウンド・ロビン・スケジューラが使用される。
【０１０１】
本発明のシミュレーションに使用されるルーティング・テーブルが、まずＭＩＰＳアルゴリズム［２８］に適用され、互い素なプレフィックスが最初に得られる。ＭＩＰＳを使用することにより、合成トレースについては観察されないが、現実バックボーン・ルーティング・テーブル例（Ｔ１、Ｔ２、Ｔ３の場合）において約５０％の圧縮（プレフィックス２８０，３３９個から１３５，７１２個への減少）が達成される。ＢＴベースの転送テーブルがこれらの互いに素なプレフィックスから構築され、次いでＰＥ上にマッピングされる。
【０１０２】
スループット：表３は、様々なパケット・トレースに関して、提案されている拡張のいくつかの組合せについてＳＡＡＦＦＩＬ−ＢＴのスループット（１サイクル内で実施されるルックアップの数（また高速化））を示す。
【０１０３】
【表３】
0005529976.tif 000006
【０１０４】
比較のために、対応するテスト・ケースにおけるＳＡＡＦＦＩＬスループットをも示す。提案されている拡張の組合せすべての効果を示すことは、過大な数の可能性を用いた実験設計を必要とし、したがって表３は、組合せの選択されたグループだけを列挙する。キャッシュありとなしの場合についての結果は、容易に比較することができる。各個々の拡張は、ある程度有益であるが、本発明では、特定の組合せではなくすべてを使用することにより、現実トレースについて約２７という実質的に高いスループット数値を達成することができることに留意されたい。
【０１０５】
以下のような結論もまた可能である。すなわち、ｉ）キャッシュ使用は、実際のトラフィック・トレース、すなわちＴ４およびＴ５についてより有益であり、ｉｉ）キャッシュ使用は、３ポインタ拡張の場合、この拡張はパイプライン長を、また暗に探索結果を取り出すために費やされる時間を短縮するので、より有益である。
【０１０６】
図１６は、例として、Ｔ４についてのＳＡＡＦＦＩＬ−ＢＴ−ｄ／ｆ／ｔおよびＴ５についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔのシミュレーション中の瞬間スループット変動を示す。瞬間スループットは、過去のウィンドウ・サイズ１０にわたって１０サイクルごとに１回計算されるＩＰルックアップの平均数として定義される。
【０１０７】
瞬間スループットは、Ｔ４について過渡期間後、大きく変動せず、１０の合理的な帯域内に留まっている。瞬間スループットは、Ｔ５について２０の帯域内で変動するが、低スループット状態に長く留まっていない。この数値は、全体的なルータ設計作業において、必要とされる入力バッファ・サイズを計算するために使用することができ、このバッファ・サイズが必ずしも過大でないことを示す。
【０１０８】
本発明のシミュレーションに基づいて、２５６ＳＲＡＭユニットのそれぞれは、Ｔ１、Ｔ２、Ｔ３の場合について４Ｋノード未満、Ｔ４、Ｔ５の場合について８Ｋノード未満を格納すべきであり、この差の理由は、ＭＩＰＳアルゴリズムをプレフィックス・テーブルに適用することであると結論することができる。前述したように、ＭＩＰＳアルゴリズムは、現実バックボーン・ルーティング・テーブル（Ｔ１、Ｔ２、Ｔ３）に対する比較を実現し、一方、実際のパケット・トレース（Ｔ４、Ｔ５）に対応する、合成により生成されたプレフィックス・テーブルを拡張する。メモリ内の各ノードについて、３２ビットが格納される（２つの１３ビット・ポインタ・フィールド、５ビット・ポート番号、および有効ビット）したがって、ＳＡＡＦＦＩＬ−ＢＴにおいてルーティング・テーブル全体を格納するために必要とされる合計メモリは、２５６×２１３×３２＝６５５３６Ｋビット＝８ＭＢ（Ｔ４およびＴ５の場合について）である。ＰＥ内のＳＲＡＭサイズが、以下のようにシステム・クロック周波数を決定する際に使用される。
【０１０９】
全体的なシステムのクロック・レートは、メモリ・アクセス時間によって決まる。表４は、異なるサイズ、および異なるＶＬＳＩ技術についてＳＲＡＭアクセス時間を列挙しており、これらはＣＡＣＴＩ装置［３１］を使用して得られた推定値である。メモリが大きいほど、アクセス時間が長くなる。ＳＡＡＦＦＩＬ−ＢＴでは、単一のクロック・サイクルが１回のＦＩＦＯキュー読取り／書込みおよび１回のＳＲＡＭ読取り動作を含み、したがって、クロック・サイクル期間は、６５ｎｍＳＲＡＭ技術を使用して約１．２ｎｓとなるように選択することができる（６４行のＦＩＦＯキュー・サイズおよび８１９２行のＳＲＡＭサイズを想定する）。表３から、実際のトレースの高速化は、ＳＡＡＦＦＩＬ−ｃにおいて約８であり、したがってＳＡＡＦＦＩＬは、１秒あたり６６．７億個のパケットを処理することができ、すなわち４０バイトＩＰパケットを想定して約２Ｔｂｐｓのルータ・フロントエンド速度に対応することに留意されたい。提案されている拡張のすべてを使用するＳＡＡＦＦＩＬ−ＢＴの場合、スループットは約２７に達する。単純なＳＲＡＭとデュアル入力／出力ＳＲＡＭのアクセス時間が等しいと仮定すると、ＳＡＡＦＦＩＬ−ＢＴは、約７Ｔｂｐｓのルータ・フロントエンド速度を達成する。
【０１１０】
【表４】
0005529976.tif 000007
【０１１１】
遅延統計：表５は、表３に示されているスループット結果と同様にして、ＳＡＡＦＦＩＬ、ＳＡＡＦＦＩＬ−ＢＴ、およびその可能な拡張について平均ルックアップ遅延を示す。
【０１１２】
【表５】
0005529976.tif 000008
【０１１３】
各個々の拡張は、平均遅延を低減する上である程度有益であるが、特定の組合せではなくすべてを使用することにより、現実トレースについて約６という、より低い平均遅延数値を達成することができることに留意されたい。スループットのサブセクションにおけるものと同様の結論もまた可能である。
【０１１４】
図１７は、例として、実際のトレースＴ４、Ｔ５のシミュレーション中に得られたルックアップ遅延ヒストグラムを示す。理論上の最悪ルックアップ遅延、すなわち各ＰＥにおけるＦＩＦＯキュー・サイズ×探索全体にわたって使用されるＩＰビットの数は、提案されているアーキテクチャについては高いが、平均遅延は、かなり低いことがわかる。ルックアップ遅延は、２クロック・サイクルと５０クロック・サイクルの間であり、２０より大きい遅延を受けるパケットは非常に少なく、平均遅延は、この場合約６である。基本アーキテクチャＳＡＡＦＦＩＬもまた、同様の特性を示すが、約１４サイクルという平均遅延は、ＳＡＡＦＦＩＬ−ＢＴ、およびその拡張が、基本アーキテクチャＳＡＡＦＦＩＬのスループットを高めるだけでなく、平均ルックアップ遅延を低減する上でも非常に効果的であることを実証している。
【０１１５】
全体的な比較：表６は、拡張されたＳＡＡＦＦＩＬ−ＢＴを、文献でより早く提案されている他の並列解決策と比較する。データは、それぞれの書面で最良の報告値に対応するか、またはそのような最良値が報告されていない場合には計算値であり、計算は、適切なサイクル時間の仮定に基づくものである。表６は、ＳＡＡＦＦＩＬ−ＢＴが、実質的に安全なマージンと共に、既存のＩＰルックアップ手法の中で先頭に立つことを示す。
【０１１６】
【表６】
0005529976.tif 000009
【０１１７】
メモリ・ユニットにわたるトライ・ノード分布：各ＰＥのＳＲＡＭブロック内に格納されたトライ・ノードの数が、Ｔ５についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔに関して、例として図１８ａに示されている。ｘ軸およびｙ軸は、ＰＥインデックスを示し、ｚ軸は、対応するメモリ・ユニットに格納された合計のＢＴノードの数を示す。平衡化に余分な努力が払われていないことに注目して、分布は、許容可能な平衡状態とみなすことができることに留意されたい。試行錯誤により、マッピング中にコーナＰＥでクラスタ根ノードを割り当てないことによって、より良好なスループットおよび遅延性能が得られる。
【０１１８】
探索負荷分布：図１８ｂは、Ｔ５についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔに関して、例として、各ＰＥのＳＲＡＭブロック内の探索動作の総数を示す。ＰＥに対する負荷は、すべてのＰＥにわたって許容可能に平衡化されていることに留意されたい。
【０１１９】
ＳＵの数およびキャッシュ・サイズの最適化：図１９は、Ｔ４についてのＳＡＡＦＦＩＬ−ＢＴ−ｃ／ｄ／ｆ／ｔに関して、平均スループットおよび平均遅延対キャッシュ・サイズ対ＳＵの数を示す。以下の結論が可能である。すなわち、（ｉ）ＳＵ>３２の場合、スループットは変化しない、（ｉｉ）キャッシュ使用はスループットを高める上で効果的であるが、キャッシュ・サイズを１６より増やしてもスループットは変化しない、（ｉｉｉ）ＳＵの数が増大するにつれて平均遅延が増大する、（ｉｖ）キャッシュ・サイズを増大すると、平均遅延がわずかに減少する、（ｖ）ＳＵの数＝３２、キャッシュ・サイズ＝５０が合理的な選択肢と思われる。
【表７】
0005529976.tif 000010
【表８】
0005529976.tif 000011
【表９】
0005529976.tif 000012
【図１Ａ】
0005529976.tif 000013
【図１Ｂ】
0005529976.tif 000014
【図２】
0005529976.tif 000015
【図３】
0005529976.tif 000016
【図４】
0005529976.tif 000017
【図５】
0005529976.tif 000018
【図６Ａ】
0005529976.tif 000019
【図６Ｂ】
0005529976.tif 000020
【図６Ｃ】
0005529976.tif 000021
【図７】
0005529976.tif 000022
【図８】
0005529976.tif 000023
【図９】
0005529976.tif 000024
【図１０】
0005529976.tif 000025
【図１１】
0005529976.tif 000026
【図１２】
0005529976.tif 000027
【図１３】
0005529976.tif 000028
【図１４】
0005529976.tif 000029
【図１５】
0005529976.tif 000030
【図１６Ａ】
0005529976.tif 000031
【図１６Ｂ】
0005529976.tif 000032
【図１７】
0005529976.tif 000033
【図１８Ａ】
0005529976.tif 000034
【図１８Ｂ】
0005529976.tif 000035
【図１９Ａ】
0005529976.tif 000036
【図１９Ｂ】
0005529976.tif 000037