(57)【要約】      （修正有）【課題】  改良したマルチビットトライネットワーク検索エンジンを提供する。【解決手段】  マルチビットトライに関するプレフィックス検索動作期間中各々がストライドを処理する一連のハードウエアパイプラインユニットが、最後のパイプラインユニット以外の少なくとも１つのパイプラインユニット内において、検索結果を残りのパイプラインユニットを介して通過させるのではなく夫々のパイプラインユニットから検索結果をリタイアさせるメカニズムを包含している。早期のリタイアは、爾後のパイプラインユニットにおけるアクティブな検索動作の不存在と共に、処理すべき爾後のストライドの不存在又は検索の完了（ミス又は端部ノード一致）のいずれかによりトリガさせることが可能である。プレフィックス検索動作に対する最悪及び／又は平均のレイテンシーが減少される。【選択図】      図１
2004194321.tif 000002
【特許請求の範囲】
【請求項１】
マルチビットトライ検索エンジンにおいて、
マルチビットトライルーチングテーブルに関するプレフィックス検索動作期間中各々がストライドを処理する一連のハードウエアパイプラインユニット、
を有しており、少なくとも１つのパイプラインユニットが、与えられたプレフィックス検索動作に対して前記少なくとも１つのパイプラインユニットからの検索結果が次のパイプラインユニットへ継続するか又はリタイアされることを可能とする制御メカニズムを包含している、
ことを特徴とするマルチビットトライ検索エンジン。
【請求項２】
請求項１において、前記少なくとも１つのパイプラインユニットが、前記少なくとも１つのパイプラインユニットにより処理されるストライドを超えてプレフィックス検索動作のためのプレフィックス内にストライドが残存しているか否かを決定することを特徴とするマルチビットトライ検索エンジン。
【請求項３】
請求項２において、前記少なくとも１つのパイプラインユニットが、又、プレフィックス検索動作が爾後のパイプラインユニットにおいて処理中であるか否かを決定することを特徴とするマルチビットトライ検索エンジン。
【請求項４】
請求項１において、前記少なくとも１つのパイプラインユニットが、前記少なくとも１つのパイプラインユニット内の処理がプレフィックス検索動作を完了したか否か及びいずれかのプレフィックス検索動作が爾後のパイプラインユニットにおいて処理中であるか否かを決定することを特徴とするマルチビットトライ検索エンジン。
【請求項５】
請求項１において、前記少なくとも１つのパイプラインユニットが、爾後のパイプラインユニットにおいて処理中のいずれかのプレフィックス検索動作の完了前にプレフィックス検索動作に対する検索結果をリタイアさせることを特徴とするマルチビットトライ検索エンジン。
【請求項６】
請求項１において、２つ又はそれ以上のパイプラインユニットの各々が、夫々のパイプラインユニットからの検索結果が次のパイプラインユニットへ継続させるか又はリタイアさせることを可能とする制御メカニズムを包含していることを特徴とするマルチビットトライ検索エンジン。
【請求項７】
請求項６において、前記２つ又はそれ以上のパイプラインユニットが、２つ又はそれ以上の所定の最大プレフィックス長の各々に対する最後のストライドに対応する一連のパイプラインユニット内の位置に位置されていることを特徴とするマルチビットトライ検索エンジン。
【請求項８】
マルチビットトライ検索エンジンにおいて、
一連のハードウエアパイプラインユニット、
を有しており、各ユニットが、
入力又は先行するパイプラインユニットからインデックスを受取るバッファ、
マルチビットトライルーチングテーブルに関してのプレフィックス検索動作期間中にストライドを処理する論理、
を包含しており、
前記一連における少なくとも１つのパイプラインユニットが、
与えられたプレフィックス検索動作に対する前記少なくとも１つのパイプラインユニット内の処理論理から爾後のパイプラインユニット内のバッファか又は前記ルーチングテーブル内の次のホップ情報へアクセスする制御器のいずれかへ検索結果を送信するデマルチプレクサ、
前記デマルチプレクサを制御する制御論理、
を有していることを特徴とするマルチビットトライ検索エンジン。
【請求項９】
請求項８において、前記少なくとも１つのパイプラインユニット内の制御論理が、いずれかのストライドが、前記少なくとも１つのパイプラインユニットにより処理されるストライドを超えてプレフィックス検索動作に対するプレフィックス内に止まるか否かを決定することを特徴とするマルチビットトライ検索エンジン。
【請求項１０】
請求項９において、前記少なくとも１つのパイプラインユニット内の制御論理が、いずれかのプレフィックス検索動作が爾後のパイプラインユニットにおいて処理中であるか否かを決定することを特徴とするマルチビットトライ検索エンジン。
【請求項１１】
請求項８において、前記少なくとも１つのパイプラインユニット内の制御論理が、前記少なくとも１つのパイプラインユニット内の処理がプレフィックス検索動作に対し不一致又は端部ノード一致のいずれかを発生したか否か及びいずれかのプレフィックス検索動作が爾後のパイプラインユニットにおいて処理中であるか否かを決定することを特徴とするマルチビットトライ検索エンジン。
【請求項１２】
請求項８において、前記少なくとも１つのパイプラインユニット内の制御論理が、爾後のパイプラインユニットにおいて処理中のいずれかのプレフィックス検索動作の完了前にプレフィックス検索動作に対する検索結果をリタイアすることを特徴とするマルチビットトライ検索エンジン。
【請求項１３】
請求項８において、２つ又はそれ以上のパイプラインユニットの各々が、更に、
与えられたプレフィックス検索動作に対する少なくとも１つのパイプラインユニット内の処理論理からの検索結果を爾後のパイプラインユニット内のバッファか又は前記ルーチングテーブル内の次のホップ情報へアクセスするための制御器のいずれかへ送信するデマルチプレクサ、
前記デマルチプレクサを制御する制御論理、
を有していることを特徴とするマルチビットトライ検索エンジン。
【請求項１４】
請求項１３において、前記２つ又はそれ以上のパイプラインユニットが２つ又はそれ以上の所定の最大プレフィックス長の各々に対する最後のストライドに対応する一連のパイプラインユニット内の位置に位置されていることを特徴とするマルチビットトライ検索エンジン。
【請求項１５】
マルチビットトライ検索エンジンの動作方法において、
マルチビットトライルーチングテーブルに関するプレフィックス検索動作期間中に一連のハードウエアパイプラインユニットの各々におけるストライドを処理し、
少なくとも１つのパイプラインユニット内において、与えられたプレフィックス検索動作に対する少なくとも１つのパイプラインユニットからの検索結果を次のパイプラインユニットへ継続させるか又はリタイアさせるかのいずれかをイネーブルさせる、
ことを包含していることを特徴とする方法。
【請求項１６】
請求項１５において、更に、
いずれかのストライドが、前記少なくとも１つのパイプラインユニットにより処理されたストライドを超えてプレフィックス検索動作に対するプレフィックス内に止まるか否かを決定する、
ことを包含していることを特徴とする方法。
【請求項１７】
請求項１６において、更に、
いずれかのプレフィックス検索動作が爾後のパイプラインユニットにおいて処理中であるか否かを決定する、
ことを包含していることを特徴とする方法。
【請求項１８】
請求項１５において、更に、
前記少なくとも１つのパイプラインユニット内の処理がプレフィックス検索動作を完了したか否か及びいずれかのプレフィックス検索動作が爾後のパイプラインユニットにおいて処理中であるか否かを決定する、
ことを包含していることを特徴とする方法。
【請求項１９】
請求項１５において、更に、
爾後のパイプラインユニットにおいて処理中のいずれかのプレフィックス検索動作の完了前にプレフィックス検索動作に対する検索結果をリタイアさせる、
ことを包含していることを特徴とする方法。
【請求項２０】
請求項１５において、更に、
２つ又はそれ以上のパイプラインユニット内において、夫々のパイプラインユニットからの検索結果を次のパイプラインユニットへ継続させるか又はリタイアさせるかのいずれかをイネーブルさせる、
ことを包含していることを特徴とする方法。
【請求項２１】
請求項２０において、前記２つ又はそれ以上のパイプラインユニットが２つ又はそれ以上の所定の最大プレフィックス長の各々に対する最後のストライドに対応する一連のパイプラインユニット内の位置に位置されていることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大略、マルチビットトライを基礎としたネットワーク検索エンジンに関するものであって、更に詳細には、ハードウエアパイプライン型マルチビットトライを基礎としたネットワーク検索エンジンの性能を改良する技術に関するものである。
【背景技術】
【０００２】
インターネットプロトコル（ＩＰ）等のパケットを基礎とした通信プロトコル用のネットワークルーターは、入ってくる情報を、そのパケットに対して意図されたデスティネーション即ち宛先へのルート即ち経路に沿って次の隣りのものへ指向させる。これを行うために、典型的に、該ルートに沿っての各ルーターは、デスティネーションＩＰプレフィックスに対する適宜の次のホップアドレスを決定するためにプレフィックス（又はルーチング）テーブルに関してアドレスプレフィックス（通常、単に「プレフィックス」と呼称される）ルックアップ動作を実施せねばならない。このような動作は埋込型ネットワークプロセッサによるか、又は、より一般的には、別個のネットワーク検索エンジンのいずれかにより実施される。
【０００３】
元々、ネットワーク検索エンジン用のハードウエアは内容アドレス可能メモリ（ＣＡＭ）を使用しており、それはビット比較器と２つのメモリ要素、即ちデータを格納するために１つと比較マスクを格納するために別の１つとからなる１つのタイプのメモリである。ＣＡＭは比較結果を「常に一致」（即ち、「ｄｏｎ’ｔ  ｃａｒｅ」）へオーバーライドさせるべくプログラムすることが可能なマスク値の制御下において入力して来るデータをデータメモリ内に格納されている値と比較する。動作について説明すると、ＣＡＭを基礎としたネットワーク検索エンジンは、特定の優先付けした順番でＣＡＭアレイ内のルーチングテーブルの全てのプレフィックスを格納することにより機能し、各プレフィックスの関連する次のホップ情報は別のメモリ内の対応する（リンクした）位置に格納されている。プレフィックスルックアップ期間中、キーがＣＡＭアレイのコンパランド（比較オペランド）上に配置され且つメモリ内の全てのプレフィックスに対して比較される。全ての比較からの一致結果のアレイが優先度論理ユニットを介して送られて最も高い優先度の一致を決定し、勝者の一致が、それから対応する次のホップ情報が読取られ且つリターンされる次のホップメモリへアドレスするために使用される。
【０００４】
より最近になって、汎用プロセッサ及び通常のメモリを使用するソフトウエアを基礎としたネットワーク検索エンジンが開発されている。このような装置においては、プロセッサは一連のメモリ読取及び比較動作でプレフィックス検索を実施する。ルーチングテーブルプレフィックス及び次のホップ情報が、典型的に、ルックアップ期間中にメモリアクセスの数及びルーチングテーブルを格納する場合におけるメモリ使用を減少させるために開発された種々のソフトウエアアルゴリズムのうちの１つに従って構築されたデータ構造におけるメモリ内に格納される。これらの目的のために、マルチビットトライ及び対応するアルゴリズムは検索動作のための有界数のメモリアクセスで最良のデータ圧縮を達成するデータ構造及びアルゴリズムの範疇に属するものである。
【０００５】
トライ（「ｔｒｉｅ」、即ち「ｒｅｔｒｉｅｖｅ」（検索）の中間の４個の文字）は二進ストリングを表わすために構築されたツリーを基礎としたデータ構造であり、該ストリングにおける各ビット又はグループのビットはそのツリー内の分岐中において採用される方向を決定する。二進（ユニビット即ち単一ビット）トライはビット毎に進行し且つ各ノードから高々２つの分岐を有しており、一方マルチビットは一度に複数個のビットを消費し且つ各ノードにおいて幾つかの分岐を有しており、各分岐は次のレベルへ通じている。各ノードにおける分岐選択期間中に消費又は検査されるビットの数はストライドと呼称される。一様幅ストライドトライは、ストライド幅により割算された後にプレフィックス長の残りとすることが可能な可能性として最後のストライドを除いて、同一の幅を有する全てのストライドを具備するトライである。
【０００６】
通常、マルチビットトライアルゴリズムは、一様ストライド幅トライ内にプレフィックスを格納し且つ検索し、同一の親（次により高いストライドレベル）ストライド値を有し同一レベル内の全ての分岐をトライテーブルと呼称されるテーブル内へグループ化することにより動作する。各レベルにおいて、対応するストライド値は次のレベルへ到達するのに必要な情報を包含するトライテーブルエントリ内へのインデックスを与える。マルチビットトライは、共通の高次ビット（ストライド）を有するプレフィックスは同一の親トライテーブルを共用するという利点を有しており、プレフィックスを格納するのに必要なメモリを減少させる。
【０００７】
長さｌのプレフィックスが各々がｎビットからなるｍストライドへ分割する場合に、次のレベルのトライテーブル内のエントリの最大可能数は２nである。該アルゴリズムは同一の親からの全ての次のレベルのストライド値を、トライノードと呼称されるデータ構造で次のレベル（子）トライテーブルのベースアドレスを包含するポインターと共に、親トライテーブル内のエントリ内に格納される２nビットデータフィールドへエンコードさせる。最大寸法２nの代わりに、存在する実際の数のテーブルエントリに対してメモリを割り当てることによりテーブル圧縮が達成される。各プレフィックスの最後のストライドに対して、端部ノードと呼称される同様のタイプのデータ構造が使用されるが、この場合には、ポインターは次のレベルのトライテーブルの代わりに次のホップ情報を包含するテーブルを指し示すことが異なる。
【０００８】
ルーチングテーブルルックアップも同一幅ストライドで実施され、入力検索器（典型的に、３２又は６４ビットのＩＰアドレス）からの次のレベルのストライドの値が、そのストライド値の親のテーブルエントリにおける関連するデータフィールドと共に、デコードされ且つ処理される。同一のプレフィックスストライド値を有する格納されているルートがそのトライ内に存在するものと決定されると、親テーブル内の情報を使用してインデックスが計算され、次いでテーブルポインター及び計算されたインデックスを使用して検索が継続して行われ次のレベルのトライテーブルエントリへ通じるアドレスを形成する。一致が見つからない場合には、その検索は成功せずに終了する。検索が端部ノードに到達し且つ一致が見つかった場合には、その検索は成功であり且つ関連する次のホップ情報が次のホップテーブルから読取られる。
【０００９】
マルチビットトライにおいてルックアップを成功裡に完了することは複数個のレベルのトライをトラバースすることを必要とする。各レベルにおいて、ツリーノードがメモリからアクセスされ且つストライド値と共に使用されて次のレベルにおけるトライノードのアドレスを決定する。
【００１０】
然しながら、ハードウエアマルチビットトライネットワーク検索エンジン内のレイテンシー即ち待ち時間は、ネットワークルーター内、従ってネットワーク自身における全体的なレイテンシーに影響を与える場合がある。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
本発明は、以上の点に鑑みなされたものであって、上述した如き従来技術の欠点を解消し、改良したマルチビットトライネットワーク検索エンジン及びその動作方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、ネットワークルーター用のマルチビットトライネットワーク検索エンジンを提供しており、該検索エンジンは一連のハードウエアパイプラインユニットを有しており、各ユニットはマルチビットトライに関するプレフィックス検索動作期間中にストライドを処理し且つ、最後のパイプラインユニット以外の少なくとも１つのパイプラインユニット内において、検索結果を残りのパイプラインユニットを介して通過させるのではなく夫々のパイプラインユニットからの検索結果をリタイアさせるメカニズムを包含している。早期のリタイアは、パイプライン型検索動作の順番外完了をサポートしないシステムに対する爾後のパイプラインユニットにおけるアクティブな検索の動作の不存在と共に、処理すべき爾後のストライドの不存在か又は現在のストライドにおける検索の完了（不一致又は端部ノード一致）のいずれかによりトリガさせることが可能である。早期リタイアメカニズムは、そのパイプラインより短い最大プレフィックス長に対する最後のストライドに対応するパイプラインユニット（例えば、６４ビットプレフィックスではなく２０又は３２ビットプレフィックス）において、何等かのその他の基準に基づいて選択したパイプラインユニットにおいて、又は全てのパイプラインユニットにおいて包含させることが可能である。プレフィックス検索動作に対する最悪及び／又は平均のレイテンシー即ち待ち時間が減少される。
【発明を実施するための最良の形態】
【００１３】
以下に説明する図１乃至図４Ａ−４Ｂ、及び本明細書における本発明の原理を説明するために使用する種々の実施例は単に例示的なものであって、本発明の範囲を制限するような態様で理解すべきものではない。当業者によって理解されるように、本発明の原理は任意の適宜に構成した装置において実現することが可能なものである。
【００１４】
図１は本発明の１実施例に基づくコンフィギャラブル（ｃｏｎｆｉｇｕｒａｂｌｅ）即ち形態特定可能な多段パイプラインマルチビットトライネットワーク検索エンジンを使用する処理システムを示している。処理システム１００はインターネットプロトコル（ＩＰ）ネットワークルーターの一部を実現しており、且つ外部メモリ１０３へ結合されているネットワークパケット検索エンジン（ＮＰＳＥ）１０２へ結合しているシステム制御器又はネットワーク処理ユニット（ＮＰＵ）１０１を包含している。ＮＰＳＥ１０２は次のホップアドレスに対するプレフィックスのみならずシステム制御器１０１からアドレス及び／又はコマンドを受取り、且つ次のホップアドレスをシステム制御器１０１へリターンする。ＮＰＳＥ１０２は、プレフィックステーブル１０４から決定したデータテーブル内の次のホップアドレスへのデータポインターと共に、外部メモリに対するデータテーブルメモリアドレスを外部メモリ１０３へ送信する。ＮＰＳＥ１０２は外部メモリ１０３からアドレス及びデータポインターによって識別されるデータテーブル１０５内のテーブル及びエントリからの次のホップアドレスを受取る。システム制御器１０１はバックプレーン１０６へ結合しており且つネットワークインターフェース１０７を介してネットワークへ結合している。
【００１５】
ＮＰＳＥ１０２は、好適には、高速３２ビットネットワークプロセッサユニット（ＮＰＵ）インターフェースによりシステム制御器１０１へ結合しており、且つ高速３２ビットスタチックランダムアクセスメモリ（ＳＲＡＭ）インターフェースにより外部メモリ１０３へ結合している。各インターフェースは、クワッドデータレート（ＱＤＲ）アーキテクチャにより実現されており、システム制御器１０１がＮＰＵインターフェースに対するマスターとして且つ外部メモリ１０３がＳＲＡＭインターフェースに対するスレーブとして設けられており、４．５キガバイト／秒（ＧＢ／ｓ）のピーク集合帯域幅に対する２５０メガヘルツ（ＭＨｚ）の最大クロック周波数でクロック当たり２個のワードで３２ビット同時的データ入力／出力（Ｉ／Ｏ）を供給する。当業者によって理解されるように、ＮＰＵ及びＳＲＡＭインターフェースのその他のコンフィギュレーション即ち形態のものを使用することも可能である。
【００１６】
図２は本発明の１実施例に基づく形態特定可能多段パイプライン型マルチビットトライネットワーク検索エンジンに対するマイクロアーキテクチャの概略図である。ＮＰＳＥ１０２は、ＮＰＳＥ１０２をシステム制御器１０１へ結合させるＮＰＵインターフェース２００、アービター（仲裁器）２０１、ＣＰＵ２０２により実行されるプログラムを包含する関連するメモリ（ＳＲＡＭ）２０３を具備する中央処理装置（ＣＰＵ）２０２、ＮＰＳＥ１０２を外部メモリ１０３へ結合させるＳＲＡＭ制御器２０４、パイプライン論理ユニット２０５ａ−２０５ｎ及び一連の仮想メモリバンク２０６ａ−２０６ｎを形成する対応する組（この例示的実施例においては１６）の形態特定可能メモリブロックのアレイ（この例示的実施例においては１６）、とを包含しており、パイプライン論理ユニット２０５ａ−２０５ｎ及びメモリバンク２０６ａ−２０６ｎは仮想バンク形態特定をイネーブル即ち可能とさせるクロスバー２０７ａによって結合されている。ＮＰＳＥ１０２により実施される主要なタスクはルートの挿入、削除及び検索であり、そのことは、ＮＰＳＥ１０２が、内部及び外部メモリ内にルートを挿入し且つそれからルートを除去することによりルーチングテーブルを維持し、且つ提示されたプレフィックスに関してのルート検索を実施し且つ関連する次のホップ情報をリターンする。
【００１７】
図３は本発明の１実施例に基づく形態特定可能多段パイプライン型マルチビットトライネットワーク検索エンジン内のマルチビットトライ検索のハードウエアパイプライン化を示している。マルチビット検索アルゴリズムのハードウエア実現例において、複数個のトライレベルを介しての検索は図示した如くにパイプライン化することが可能であり、各処理レベルは与えられた検索器に対し異なるストライドに関して動作し且つ新たな検索器に対する処理が各サイクル毎に開始される。任意の与えられた時間において、パイプラインの各レベルは、そのレベルにおいてのストライドビット（その検索器に対し）を処理しながら、異なる検索器に関して動作を行う。１つの実現例においては、最後（パイプラインユニット２０５ｎ）以外のパイプラインユニットのいずれかにおけるミス又は端部ノード一致は、パイプラインユニットの残部を介して更なる処理を行うことなしに通過される結果を発生する。
【００１８】
殆どのマルチビットトライアルゴリズムは汎用のプログラム可能プロセッサ上で稼動するソフトウエアプログラムとして実現される。マルチビットトライアルゴリズムのハードウエア実現例が提案される範囲において、このようなハードウエアトライを介しての検索に関連するレイテンシー即ち待ち時間についての説明は割愛する。
【００１９】
マルチビットトライアルゴリズムのハードウエア実現例の輸入成分は、トライテーブルを格納するために必要とされるオンチップ格納部の量である。一方、メモリは、コアルーターにおける数十万個のプレフィックスを有する大きなルーチングテーブルを格納するのに充分に大きなものでなければならない。同時に、毎秒数億個の検索の高い処理能力ルックアップ条件に起因して、メモリへのアクセスはパイプライン化せねばならず、そのことは、メモリがコンフィギャラブル即ち形態特定可能なものであり且つパイプラインの各ステージ即ち段又はトライのレベルにおいての同時的アクセス可能性に対して柔軟性のあるものでなければならない。
【００２０】
オンチップで形態特定可能メモリ構造を有する１つの結果は、各トライレベルにおいてのストライドの処理がより時間がかかるということである。実施例のＮＰＳＥ１０２において、１６個のパイプラインユニット２０５ａ−２０５ｎが存在しており、各々は４ビットのストライドを処理する。インターネットプロトコルバージョン６（ＩＰｖ６）パケットに対する６４ビットアドレスプレフィックス（典型的に、ＩＰｖ６パケットに対する１２８ビットプレフィックスの６４ビットのみが検索において関連性がある）は書込速度において検査することが可能であるが、各レベルにおいて行われる作業はより大きく、形態特定可能オンチップＳＲＡＭメモリバンク２０６ａ−２０６ｎはアクセスされ、トライノードエントリが抽出され、且つ次のトライレベルアドレスが計算されることが必要である。各パイプラインユニット２０５ａ−２０５ｎにおけるこれらの処理に対して最大で４個のサイクルが必要とされる場合があり、その結果６４サイクルのレイテンシー即ち待ち時間となる。
【００２１】
同一のＮＰＳＥ１０２は各々が異なる最大プレフィックス長を有する複数個のルーチングテーブルを収容することが可能であり、例えばインターネットプロトコルバージョン４（ＩＰｖ４）パケットに対しての３２ビットプレフィックス又は仮想プライベートネットワーク（ＶＰＮ）パケットに対する２０ビットプレフィックスであり、パイプラインユニット２０５ａ−２０５ｎのレイテンシーは６４ビット未満の長さのプレフィックスに対して検索完了時間に不必要な制限を加える。更に、上述したパイプライン化実現例は、例えプレフィックスルックアップが最初の１つ又は２つのレベルで最も長いプレフィックスの一致を見つけ出す場合であっても６４サイクル全体のレイテンシーが無駄にされるという欠点を有しており、従って平均的な場合のルックアップレイテンシーも損失を被る。
【００２２】
図４Ａ及び４Ｂは本発明の種々の実施例に基づく形態特定可能多段パイプライン型マルチビットトライネットワーク検索エンジン内の処理レベルに対するパイプラインユニットの構造を詳細に示している。図４Ａは与えられたテーブルに対して最悪の場合のレイテンシーをアドレスする１つの実施例に対するパイプラインユニットの詳細を示している。構築され且つＮＰＳＥ１０２においてトラバースされる各テーブルは、特定のネットワーク適用例に対してのものであり、即ちＩＰｖ４／ＩＰｖ６、ＶＰＮ等の適用例であり、それはテーブル内の最大プレフィックス長ｌは通常知られていることを意味している。
【００２３】
この最大プレフィックス長はＮＰＳＥ１０２での検索に対するトライレベルの最大数Ｌmaxを決定し、尚Ｌmax＝ｃｅｉｌｉｎｇ（ｌ％４）であり、それはそのテーブルにおける検索に対する最悪のレイテンシーを決定する。従って、ＩＰｖ４テーブルは３２ビットの最大プレフィックス長及び８の検索レベルの最大数（４ビットストライドに対し）を有している。ＮＰＳＥ１０２においては、パイプラインユニット２０５ａ−２０５ｎ内の各ストライドレベル検索は４つのサイクルを必要とし、３２ビットＩＰｖ４検索器に対する最悪のレイテンシーは３２を超えることのないサイクルである。然しながら、８番目のパイプラインユニットの結果が上述した如くに残りの８個のパイプラインユニットを介して通過せねばならない場合には、完全な６４個のサイクルが必要とされる。
【００２４】
図４Ａは、全てのルックアップが順番に取扱われるものと仮定し、最悪のレイテンシーを６４サイクルから３２サイクルへ減少させる構造を例示している。一連のパイプラインユニット２０５ａ−２０５ｎ内の各パイプラインユニット２０５ｉは、バッファ４０２を介して前の処理レベルｉ−１からの入力を受取る対応する処理レベルｉに対する処理論理４０１を包含している。ルックアップ動作がパイプラインに沿って進行する場合に、ストライドが各レベルにおいて消費される場合に処理されるべき残存する入力検索器内の入力ビットの数が追跡される。少なくとも１つのパイプラインユニット内において（ＩＰｖ４／ＩＰｖ６ルックアップの例においては８番目のパイプラインユニット）、信号４０３が発生され、ストライドが残存していない時を表わす。この信号４０３は論理４０４によって使用されて制御ユニット４０５（例えば、デマルチプレクサ）への入力を発生し、検索結果がパイプラインを介して継続するか（即ち、処理レベルｉ＋１用のバッファへ通過される）又はリタイアされるか否かを決定する。
【００２５】
図４Ａの構造の場合には、ルックアップ動作が、入力検索器において処理されるべき更なるビットが存在していないレベルに到達すると、パイプラインにおけるさらに下方においてアクティブな検索が存在しない場合には、その動作の結果はリタイアすることが可能である。そのために、論理４０４は一連２０５ａ−２０５ｎ、即ち物理的に「前方」であるか又は更にパイプラインチェーンに沿ってのパイプラインユニット内の各爾後のパイプラインユニットからのアクティブな検索信号を受取るが、興味のある時刻において、時間においてより速い検索を処理する（現在のパイプラインユニットにおいて処理中の検索が発行される前に発行される）。然しながら、ＮＰＳＥ１０２が最大のサポートされる長さより短い単一長のプレフィックスを処理するに過ぎない場合（即ち、ＩＰｖ４又はＩＰｖ６プレフィックスのいずれかを取扱うべく適合されているが、動作において、ＮＰＳＥ１０２がＩＰｖ４プレフィックスのみを取扱うために使用される）、このようなアクティブな信号検索は必要とされない。
【００２６】
信号４０３、論理４０４及び制御ユニット４０５は、３２ビット検索器を有するテーブルに対する最悪の場合のレイテンシーは、８番目のものより大きな処理レベルにおけるアクティブの未決のルックアップが存在しない場合には、６４サイクルの代わりに３２サイクルであることを確保する。早期のリタイアの場合、成功したルックアップが次のホップポインター情報と共に外部ＳＲＡＭ１０３へ転送され、一方失敗したルックアップはＮＰＵ１０１へ帰還する。
【００２７】
更に、図４Ａにおける構造の複数個のインスタンスはパイプラインユニット２０５ａ−２０５ｎ内において実現することが可能である。例えば、ＩＰｖ４／ＩＰｖ６ルックアップを取扱うために８番目のパイプラインユニットにおいて実現されることに加えて、図４Ａの構造は、又、ＮＰＳＥ１０２が異なる長さのプレフィックスに対するルックアップを取扱う場合に５番目のものより大きな処理レベルにおいてアクティブな未決のルックアップが存在しない場合には、３２又は６４サイクルではなく２０サイクルで２０ビットＶＰＮプレフィックスに関するルックアップの早期のリタイアを可能とするために５番目のパイプラインユニットにおいて実現することが可能である。
【００２８】
図４Ｂは平均的な場合のレイテンシーに対処する場合である。図４Ａの構造であっても、８番目のものより速い処理レベルにおいて成功裡に又は不成功裡に完了した３２ビットプレフィックスルックアップは、尚且つ、８番目の処理レベルの後にリタイアするに過ぎない（何故ならば、ストライドが処理されるべく残存するからである）。然しながら、全てのルックアップが順番に処理されるものと仮定すると、図４Ｂの構造は、検索がより速くにパイプラインからリタイアすることを可能とする。処理されるべく残存する更なるストライドが存在するか否かに依存する信号の代わりに、処理論理４０１は、検索が完了したか否かを表わす信号４０６を発生する（即ち、ミス又は端部ノードに対する一致のいずれかが決定されたか否か）。
【００２９】
図４Ｂのシステムの場合には、検索動作が成功裡に又は不成功裡に完了すると、検索完了信号４０６がアサート即ち活性化される。信号４０６がアサートされ且つパイプラインの更に下側にアクティブな検索が存在しない場合には、この特定の検索は、処理されるべきプレフィックス内にストライドが残存するか否かに拘わらずに、パイプラインからリタイアすることが可能である。検索結果は、最早、パイプラインの残部を介して段階的に進むことは必要ではない。
【００３０】
図４Ｂの検索完了検知システムは、可及的に最も速い点において各検索のリタイアを可能とするために全てのパイプラインユニット２０５ａ−２０５ｎ（即ち、全ての処理レベルにおいて）内に実現することが可能である。然しながら、相互接続ルーチング（経路付け）及びタイミング拘束条件、及びその他の実際的な理由が、平均的な場合のレイテンシーに利点があるようなあるレベル又はプレフィックス長においてのみ図４Ｂの構造を使用することを正当化する場合がある。図４Ａ及び４Ｂのメカニズムは、最後のパイプラインユニット２０５ｎにおいて必要とされるものではないが、そのパイプラインユニット２０５ｎからのアクティブな検索信号が、処理レベルｉ乃至ｎ−１に対する先行するパイプラインユニットに対して必要とされる場合がある。
【００３１】
更に、図２のパイプライン実現例に対してエキストラなレベルの複雑性が付加され且つ全ての検索要求に対するトランズアクション識別子でパイプラインにおいて順番外に検索を完了することが許容される場合には、パイプライン内の後の処理レベルが未だにルックアップ要求を処理している場合であっても、検索を可及的速やかにリタイアさせることが可能である。ＮＰＵ１０１が順番外の検索結果及びＮＰＵ１０１とＮＰＳＥ１０２との間のインターフェースの性質を受付けることが可能であるか否かに依存して、検索応答を順番でリターンするために並び替えバッファを使用することが可能であり、設計の複雑性が増加することの犠牲により平均的なレイテンシーを減少させる。
【００３２】
本発明はパイプライン型マルチビットトライネットワーク検索エンジンにおけるルックアップ要求のレイテンシー即ち待ち時間を減少させる。検索エンジンパイプラインにおける長いレンテンシーを完全に利用するために充分な数のスレッドを発生することが不可能なＮＰＵは、しばしば、現在のスレッドが関連するルックアップ要求を完了するのを待機している間に、ルーターラインカードに関するそれらの入力キューがバックアップされていることを見出す。減少させた最悪又は平均的な場合のレイテンシーの場合に、ルックアップはより速く完了し且つこのような輻輳を減少させるか又は開始する。
【００３３】
以上、本発明の具体的実施の態様について詳細に説明したが、本発明は、これら具体例にのみ制限されるべきものではなく、本発明の技術的範囲を逸脱することなしに種々の変形が可能であることは勿論である。
【図面の簡単な説明】
【００３４】
【図１】本発明の１実施例に基づく形態特定可能多段パイプライン型マルチビットトライネットワーク検索エンジンを使用した処理システムを示した概略図。
【図２】本発明の１実施例に基づく形態特定可能多段パイプライン型マルチビットトライネットワーク検索エンジンに対するマイクロアーキテクチャを示した概略図。
【図３】本発明の１実施例に基づく形態特定可能多段パイプライン型マルチビットトライネットワーク検索エンジン内のマルチビットトライ検索のハードウエアパイプライン化を例示した概略図。
【図４Ａ】本発明の１実施例に基づく形態特定可能多段パイプライン型マルチビットトライネットワーク検索エンジン内の処理レベルに対するパイプラインユニットの詳細な構造を示した概略図。
【図４Ｂ】本発明の１実施例に基づく形態特定可能多段パイプライン型マルチビットトライネットワーク検索エンジン内の処理レベルに対するパイプラインユニットの詳細な構造を示した概略図。
【符号の説明】
【００３５】
１００  処理システム
１０１  ネットワーク処理ユニット（ＮＰＵ）
１０２  ネットワークパケット検索エンジン（ＮＰＳＥ）
１０３  外部メモリ
１０４  プレフィックステーブル
１０５  データテーブル
１０７  ネットワークインターフェース
【図１】
2004194321.tif 000003
【図２】
2004194321.tif 000004
【図３】
2004194321.tif 000005
【図４Ａ】
2004194321.tif 000006
【図４Ｂ】
2004194321.tif 000007