(57)【要約】【課題】  改良したマルチビットトライネットワーク検索エンジン及びその動作方法を提供する。【解決手段】  マルチビットトライネットワーク検索エンジンが、最長プレフィックスストライドの数に対応する数のパイプライン論理ユニット及びプレフィックステーブルを保持するための１組のメモリブロックによって実現されている。各パイプライン論理ユニットは１つのメモリアクセスへ制限され、且つパイプライン論理ユニットチェーン内の終了点は異なる長さのプレフィックスを取扱うべく可変である。該メモリブロックはメッシュ型クロスバーでパイプライン論理ユニットへ結合されており且つ１組の仮想メモリバンクを形成しており、任意の与えられた物理的メモリバンク内のメモリブロックは任意の特定のパイプライン論理ユニットに対する仮想メモリバンクへ割当てることが可能である。埋込型プログラム可能プロセッサが、仮想メモリバンクのコンフィギュレーションと共に、プレフィックステーブル内のルートの挿入及び削除を管理する。【選択図】      図１
2004194319.tif 000002
【特許請求の範囲】
【請求項１】
マルチビットトライ検索エンジンにおいて、
各々がアドレスプレフィックス内のストライドを処理する一連のパイプラインユニット、
各々が前記パイプラインユニットのうちの１つと関連しており且つ対応するパイプラインユニットにより処理されるストライドに対するプレフィックステーブルを保持する複数個の仮想メモリバンクとして形態特定することが可能な１組のメモリブロック、
前記パイプラインユニットのうちのいずれかを前記関連する仮想メモリバンクに対して割当てられたメモリブロックに対して選択的に結合させることが可能な形態特定可能相互接続体、
を有していることを特徴とするマルチビットトライ検索エンジン。
【請求項２】
請求項１において、前記形態特定可能相互接続体がメッシュ型クロスバーを有していることを特徴とするマルチビットトライ検索エンジン。
【請求項３】
請求項１において、各パイプラインユニットが、プレフィックス検索期間中に、前記仮想メモリバンクのうちの１つのメモリアクセスへ制限されることを特徴とするマルチビットトライ検索エンジン。
【請求項４】
請求項１において、プレフィックス検索に対する一連のパイプラインユニット内の終了点がプレフィックス長さに基づいて変化することを特徴とするマルチビットトライ検索エンジン。
【請求項５】
請求項１において、更に、
ルーチングテーブルデータセット内のプレフィックス分布に基づいて前記仮想メモリバンクの形態を制御するプログラム可能プロセッサ、
を有していることを特徴とするマルチビットトライ検索エンジン。
【請求項６】
請求項５において、前記一連のパイプラインユニットは、前記プログラム可能プロセッサによる関与なしでルート検索を処理するが、前記プレフィックステーブルへのルートの挿入及び削除は、前記一連のパイプラインユニットのうちの少なくとも一部と共に前記プログラム可能プロセッサを使用することを特徴とするマルチビットトライ検索エンジン。
【請求項７】
請求項１において、本検索エンジンがネットワークルーター内において実現されており且つネットワークプロセッサユニット及び前記プレフィックステーブル内のアドレスプレフィックスに対応する次のホップ情報を保持する外部メモリへ結合されていることを特徴とするマルチビットトライ検索エンジン。
【請求項８】
マルチビットトライ検索エンジンにおいて、
ルーチングテーブルに対するエントリ内の値に対する一致を決定するためにルート検索用のアドレスプレフィックスを一括的に処理する一連のパイプラインユニット、
各々が前記パイプラインユニットのうちの１つへ結合されると共にそれに関連している複数個の仮想メモリバンクであって、前記ルーチングテーブルを格納するマルチビットトライに対するプレフィックステーブルを一括的に保持する１組のメモリブロックから形成した複数個の仮想メモリバンク、
前記マルチビットトライに対するテーブル内のプレフィックス分布に基づいて前記仮想メモリバンクの各々に対してのメモリブロックの割当てを制御するプログラム可能制御器、
を有していることを特徴とするマルチビットトライ検索エンジン。
【請求項９】
請求項８において、更に、
各パイプラインユニットを関連する仮想メモリバンクへ結合するクロスバー、
を有しており、各パイプラインユニットはルート検索期間中にプレフィックス内のストライドを処理し且つ前記関連する仮想メモリバンクは対応するパイプラインユニットにより処理されるストライドに対するプレフィックステーブルを保持する、
ことを特徴とするマルチビットトライ検索エンジン。
【請求項１０】
請求項８において、プログラム可能制御器が汎用プロセッサと関連するメモリとを有しており、前記一連のパイプラインユニットが前記プロセッサによる関与なしで自動的にルート検索を処理し且つ前記プロセッサが前記ルーチングテーブル内のルートの挿入及び削除の処理に貢献することを特徴とするマルチビットトライ検索エンジン。
【請求項１１】
請求項８において、前記一連のパイプラインユニットが、少なくとも２つの異なる数のストライドのうちの１つを処理した後にアドレスプレフィックスの処理を終了するための少なくとも２つの終了点を包含していることを特徴とするマルチビットトライ検索エンジン。
【請求項１２】
マルチビットトライ検索エンジンを操作する方法において、
一連のパイプラインユニットのうちの１つにおけるアドレスプレフィックス内の各ストライドを処理し、
ストライドの処理期間中に、複数個の仮想メモリバンクとして形態特定された複数個のメモリブロックから形成した複数個の仮想メモリバンクのうちの１つを使用し、各仮想メモリバンクは前記パイプラインユニットのうちの１つと関連しており且つ対応するパイプラインユニットにより処理されるストライドに対するプレフィックステーブルを保持し、
形態特定可能な相互接続体を使用して前記関連する仮想メモリバンクへ割当てられたメモリブロックへ前記パイプラインユニットのうちのいずれかを選択的に結合させる、
ことを包含していることを特徴とする方法。
【請求項１３】
請求項１２において、前記形態特定可能な相互接続体がメッシュ型クロスバーを有していることを特徴とする方法。
【請求項１４】
請求項１２において、更に、
プレフィックス検索期間中に各パイプラインユニットを前記仮想メモリバンクの１つのメモリアクセスへ制限する、
ことを包含していることを特徴とする方法。
【請求項１５】
請求項１２において、更に、
プレフィックス長さに基づいてプレフィックス検索に対する一連のパイプラインユニット内の終了点を変化させる、
ことを包含していることを特徴とする方法。
【請求項１６】
請求項１２において、更に、
プログラム可能プロセッサを使用してルーチングテーブルデータセット内のプレフィックス分布に基づいて前記仮想メモリバンクの形態特定を制御する、
ことを包含していることを特徴とする方法。
【請求項１７】
請求項１５において、更に、
前記プログラム可能プロセッサによる関与なしで前記一連のパイプラインユニットにおけるルート検索を処理し、
前記プレフィックステーブルへのルートの挿入及び削除を処理するために前記一連のパイプラインユニットの少なくとも一部と共に前記プログラム可能プロセッサを使用する、
ことを包含していることを特徴とする方法。
【請求項１８】
請求項１２において、更に、
ネットワークプロセッサユニット及び前記プレフィックステーブル内のアドレスプレフィックスに対応する次のホップ情報を保持している外部メモリへ結合されているネットワーク検索エンジンを有するネットワークルーターを操作する、
ことを包含していること特徴とする方法。
【請求項１９】
マルチビットトライ検索エンジンを操作する方法において、
ルーチングテーブルに対するエントリ内の値に対する一致を決定するために一連のパイプラインユニット内において一括的にルート検索に対するアドレスプレフィックスを処理し、
複数個の仮想メモリバンクの各々を前記パイプラインユニットの関連する１つへ結合させ、前記仮想メモリバンクは少なくとも１つの物理的メモリバンク内のメモリブロックから形成されており且つ前記ルーチングテーブルを格納するマルチビットトライ用のプレフィックステーブルを一括的に保持し、
前記マルチビットトライ用のテーブル内のプレフィックス分布に基づいて前記仮想メモリバンクの各々に対する前記少なくとも１つの物理的メモリバンク内のメモリブロックの割当てを動的に制御する、
ことを包含していることを特徴とする方法。
【請求項２０】
請求項１９において、更に、
各パイプラインユニットを関連する仮想メモリバンクへ結合させるためにクロスバーを使用し、
ルート検索期間中にプレフィックス内のストライドを処理するために各パイプラインユニットを使用し、
対応するパイプラインユニットにより処理されるストライドに対するプレフィックステーブルをパイプラインユニットと関連する仮想メモリバンク内に格納する、
ことを包含していることを特徴とする方法。
【請求項２１】
請求項１９において、更に、
前記仮想メモリバンクの各々へメモリブロックの割当てを動的に制御するために汎用プロセッサ及び関連するメモリを使用し、
前記プロセッサによる関与なしで前記一連のパイプラインユニット内のルート検索を自動的に処理し、
前記ルーチングテーブル内のルートの挿入及び削除の処理期間中に前記プロセッサを使用する、
ことを包含していることを特徴とする方法。
【請求項２２】
請求項１９において、更に、
少なくとも２つの異なる数のストライドのうちの１つを処理した後に前記一連のパイプラインユニット内の少なくとも２つの終了点のうちの１つにおいてアドレスプレフィックスの処理を終了する、
ことを包含していることを特徴とする方法
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大略、マルチビットトライを基礎としたネットワーク検索エンジンに関するものであって、更に詳細には、マルチビットトライを基礎としたネットワーク検索エンジンの性能を改善する技術に関するものである。
【背景技術】
【０００２】
インターネットプロトコル（ＩＰ）等のパケットを基礎とした通信プロトコル用のネットワークルーターは、そのパケットに対して意図されたデスティネーション即ち宛先へのルート即ち経路に沿って次の隣りのものへ入力情報を指向させる。これを行うために、典型的に、そのルート即ち経路に沿っての各ルーターは、デスティネーションＩＰプレフィックスに対して適宜の次のホップアドレスを決定するためにプレフィックステーブルに関してアドレスプレフィックス（通常、単に、「プレフィックス」と呼称される）ルックアップ操作を実施せねばならない。このような操作は、埋込型ネットワークプロセッサか又は、より一般的には、別個のネットワーク検索エンジンのいずれかにより実施される。デスティネーションプレフィックス及び関連する次のホップ情報からなるプレフィックス（ルーチング）テーブルに関してサーチ即ち検索を実施することに加えて、ネットワーク検索エンジンは、典型的に、プレフィックステーブルを維持する作業を行う（即ち、プレフィックスの挿入及び削除）。
【０００３】
元々、ネットワーク検索エンジン用のハードウエアは三元内容アドレス可能メモリ（ＴＣＡＭ）を使用しており、該メモリは、データを格納するための１つと比較マスクを格納するための１つとの２つのメモリ要素及びビット比較器からなるタイプのメモリである。ＴＣＡＭは、マスク値の制御下で、データメモリ内に格納されている値を入力データと比較し、該マスク値は比較結果をオーバーライドするために「常に一致」（即ち、「ｄｏｎ’ｔ  ｃａｒｅ」）へプログラムさせることが可能である。動作について説明すると、ＴＣＡＭを基礎としたネットワーク検索エンジンは、各プレフィックスの関連する次のホップ情報が別のメモリ内の対応する（リンクした）位置内に格納されて、特定の優先付けした順番でＴＣＡＭアレイ内にルーチングテーブルのすべてのプレフィックスを格納することにより機能する。プレフィックスルックアップテーブル期間中、キーがＴＣＡＭアレイのコンパランド（比較オペランド）上に配置され且つ該メモリ内の全てのプレフィックスに対して比較される。全ての比較からの一致結果からなるアレイは優先度論理ユニットを介して送られて、最も高い優先度の一致を決定し、その勝者となった一致は次のホップメモリをアドレスするために使用され、それから対応する次のホップ情報が読取られ且つリターンされる。
【０００４】
より最近になって、汎用プロセッサ及び通常のメモリを使用するソフトウエアを基礎としたネットワーク検索エンジンが開発されている。このような装置内において、プロセッサは一連のメモリの読取及び比較動作でもってプレフィックス検索を実施する。ルーチングテーブルプレフィックス及び次のホップ情報が、典型的に、ルーチングテーブル及びルックアップ期間中のメモリアクセスの数を格納する場合におけるメモリの使用を減少させるべく開発された種々のソフトウエアアルゴリズムのうちの１つに従って構築されたデータ構造でメモリ内に格納される。これらの目的のために、マルチビットトライ及び対応するアルゴリズムは、検索動作のためのメモリアクセスの有界数で最善のデータ圧縮を達成するデータ構造及びアルゴリズムの範疇に属する。
【０００５】
トライ（「ｔｒｉｅ」、即ち「ｒｅｔｒｉｅｖｅ」（検索）の中間の４個の文字）は、二進ストリングを表わすために構築されたツリーを基礎としたデータ構造であり、その場合に、ストリング内の各ビットはツリー内の分岐間で取られる方向を決定する。二進（ユニビット即ち単一ビット）トライはビット毎に進行し且つ各ノードから高々２個の分岐を有しており、一方マルチビットは一度に複数個のビットを消費し且つ各ノードにおいて幾つかの分岐を有しており、各分岐は次のレベルへ通じている。各ノードにおける分岐選択期間中に消費されるビット数はストライドと呼称される。一様幅のストライドトライは、ストライド幅で割算した後のプレフィックス長の余りとすることが可能な最後のストライドを除いて、全てのストライドが同一の幅を有するトライである。
【０００６】
通常、マルチビットトライアルゴリズムは、一様なストライド幅のトライ内にプレフィックスを格納し且つ検索し、同一の親（次により高いストライドレベル）のストライド値を有する同一のレベルにおける全ての分岐をトライテーブルと呼称されるテーブル内にグループ化することにより動作する。長さ１のプレフィックスを各々がｎビットのｍ個のストライドに分割すると、次のレベルのトライテーブル内のエントリの可及的に最大の数は２nである。該アルゴリズムはトライノードと呼称されるデータ構造で次のレベル（子）トライテーブルのベースアドレスを包含するポインターと共に、親トライテーブル内のエントリ内に格納されている２nビットデータフィールド内に同一の親からの全ての次のレベルのストライド値をエンコードさせる。最大寸法２nの代わりに、存在するテーブルエントリの実際の数に対してメモリを割り当てることによりテーブル圧縮が達成される。各プレフィックスの最後のストライドに対して、この場合においては、ポインターが次のレベルのトライテーブルの代わりに次のホップ情報を包含するテーブルを指し示すことを除いて、端部ノードとして呼称される同様のタイプのデータ構造が使用される。
【０００７】
ルーチングテーブルルックアップも同一幅のストライドで実施され、次のレベルのストライドの値がデコードされ且つそのストライドの値の親のテーブルエントリにおける関連するデータフィールドと共に処理される。同一のプレフィックスストライド値を有する格納されているルート即ち経路がそのトライ内に存在するものと決定されると、親テーブル内の情報を使用してインデックスが計算され、次いでテーブルポインター及び計算されたインデックスを使用して検索が継続して行われ次のレベルのトライテーブルエントリへ通じるアドレスを形成する。一致が見つからない場合には、検索は成功せずに終了する。検索が端部ノードに到達し且つ一致が見つかった場合には、その検索は成功し且つ関連する次のホップ情報が次のホップテーブルから読取られる。
【０００８】
マルチビットトライネットワーク検索エンジンの既存の及び提案されている実現例は高性能ネットワークのために必要な処理能力を欠如しており、且つ現在及び将来の両方のルーチング即ち経路付けの必要性を取扱うのに必要な柔軟性を欠如している。何故ならば、プレフィックスの分布は動的なものであり且つ完全に予測することが不可能だからである。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、以上の点に鑑みなされたものであって、上述した如き従来技術の欠点を解消し、改良したマルチビットトライネットワーク検索エンジン及びその操作方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、最長プレフィックスストライドの数に対応する多数のパイプライン論理ユニット及びプレフィックステーブルを保持するための１組のメモリブロックによって実現されネットワークルーターにおいて使用するためのマルチビットトライネットワーク検索エンジンを提供している。各パイプライン論理ユニットは１つのメモリアクセスへ制限されており、且つパイプライン論理ユニットチェーン内の終了点は異なる長さのプレフィックスを取扱うために可変である。メモリブロックがメッシュ型クロスバーでパイプライン論理ユニットへ結合されており且つ１組の仮想メモリバンクを形成されており、物理的メモリ内の埋込型メモリブロックは任意の特定のパイプライン論理ユニットに対する仮想メモリバンクへ割当てることが可能である。埋込型プログラム可能プロセッサは、仮想メモリバンクのコンフィギュレーション（ｃｏｎｆｉｇｕｒａｔｉｏｎ）即ち形態特定と共に、プレフィックステーブル内のルートの挿入及び削除を管理する。
【発明を実施するための最良の形態】
【００１１】
以下に説明する図１乃至３及び本明細書において本発明の原理を説明するために使用する種々の実施例は単に例示的なものであって何等本発明の範囲を制限する態様で解釈されるべきものではない。当業者によって理解されるように、本発明の原理は、任意の適宜の構成の装置において実現することが可能である。
【００１２】
図１は、本発明の１実施例に基づく完全にコンフィギャラブル（ｃｏｎｆｉｇｕｒａｂｌｅ）即ち形態特定可能なメモリ、多段パイプラインマルチビットトライネットワーク検索エンジンを使用する処理システムを示している。処理システム１００はインターネットプロトコル（ＩＰ）ネットワークルーターの一部を実現しており且つ外部メモリ１０３へ結合されているネットワークパケット検索エンジン（ＮＰＳＥ）１０２へ結合されているシステム制御器即ちネットワーク処理ユニット（ＮＰＵ）１０１を包含している。ＮＰＳＥ１０２は次のホップアドレスに対するプレフィックスのみならずシステム制御器１０１からアドレス及び／又はコマンドを受取り、且つ次のホップアドレスをシステム制御器１０１へリターンする。ＮＰＳＥ１０２はプレフィックステーブル１０４から決定したデータテーブル内の次のホップアドレスへのデータポインターと共に、外部メモリへのデータテーブルメモリアドレスを外部メモリ１０３へ送信する。ＮＰＳＥ１０２は外部メモリ１０３から、アドレス及びデータポインターによって識別されたデータテーブル１０５内のテーブル及びエントリからの次のホップアドレスを受取る。システム制御器１０１はバックプレーン１０６へ結合されており且つネットワークインターフェース１０７を介してネットワークへ結合されている。
【００１３】
ＮＰＳＥ１０２は、好適には、高速３６ビットネットワークプロセッサユニット（ＮＰＵ）インターフェースによってシステム制御器１０１へ結合されており且つ高速３６ビットスタチックランダムアクセスメモリ（ＳＲＡＭ）インターフェースにより外部メモリ１０３へ結合している。各インターフェースはクワッドデータレート（ＱＤＲ）アーキテクチャにより実現されており、システム制御器１０１はＮＰＵインターフェースに対するマスターとして設けられており且つ外部メモリ１０３はＳＲＡＭインターフェースに対するスレーブとして設けられており、４．５キガバイト／秒（ＢＧ／ｓ）のピーク集合帯域幅に対し２５０メガヘルツ（ＭＨｚ）の最大クロック周波数でクロック当たり２個のワードにおいて３６ビット同時的データ入力／出力（Ｉ／Ｏ）を供給する。
【００１４】
図２Ａ乃至２Ｃは種々の提案に基づく且つ本発明の１実施例に基づくパイプライン型マルチビットトライネットワーク検索エンジンに対するマイクロアーキテクチャの比較図である。図２Ａはマルチビットビットマップトライアルゴリズムを実現するために２個のシンクロナスダイナミックランダムアクセスメモリ（ＳＤＲＡＭ）２１０ａ−２１０ｂ及び応用特定集積回路（ＡＳＩＣ）２０９を使用した１つの提案されたパイプライン型マルチビットトライネットワーク検索エンジンである。この実現例においては、プレフィックスストライドは２つのグループに分割されており且つ関連するトライテーブルは２つのメモリバンク２１０ａ−２１０ｂ内に格納されており、各グループに対して１個のバンクである。ルックアップ論理２１１により実施される全てのプレフィックス検索には２個のメモリバンク２１０ａ−２１０ｂに対する２つのパイプライン型動作が関与し、各バンクは各パイプラインにおいて複数回アクセスすることが可能である。プレフィックスの挿入及び削除もオンチップメモリからの助けを借りてＡＳＩＣ論理２１１により処理される。
【００１５】
図２Ａの実現例は高性能ネットワーク検索エンジンに対して必要とされる処理能力を欠如している。ルックアップが２つのパイプライン動作に分割されているので、クロックサイクル毎に単に２つの同時的な動作が存在するに過ぎない。インターネットプロトコルバージョン４（ＩＰｖ４）アドレスは、最大で３２個のプレフィックスビットを有することが可能であり、且つ妥当なストライド幅は４ビットであり、単一の検索を完了するのに最大で８個のメモリ参照を必要とする。最悪の場合において、検索を完了するのに各パイプラインステージ（段）において４つのメモリ参照が必要とされ、処理能力は最大帯域幅の４分の１に等しい。インターネットプロトコルバージョン６（ＩＰｖ６）の場合においては、プレフィックス幅は１２８ビットであり、その処理能力は何倍にもより低いものとなる場合がある。
【００１６】
図２ＢはＢ−ＴＲＥＥと呼称されるパイプライン型ツリーを基礎とした検索アルゴリズムの別の提案されている実現例を示しており、それはツリーテーブル内に部分的なプレフィックス値を格納し且つ検索期間中に次のテーブルインデックスを計算するために複数個の比較器に依存する。プレフィックスが４個の固定された寸法のメモリバンク２１２ａ−２１２ｂ内に格納され且つテーブルアップデートがパイプライン論理２１３ａ−２１３ｄによって実施される。使用されるアルゴリズムはビットマップ型マルチビットトライとは著しく異なるものであり且つ異なるハードウエア条件を有している。
【００１７】
図２Ａ及び２Ｂの両方の実現例は、現在及び将来のルーチング環境に対処するのに必要な柔軟性を欠如しており、且つそのハードウエアはテーブルアップデート及びメモリ管理操作を取扱うのに複雑になり過ぎる場合がある。各バンクに対して固定寸法のメモリをコミットさせることは危険性のあるアプローチである。何故ならば、全てのアルゴリズムソリューションに対するメモリ寸法条件は著しくルーチングテーブルデータセットに依存するからである。これらのデータセットに対するプレフィックス分布は異なるルーチング環境と共に変化する。迅速に変化するネットワーク環境においては、ルーチングプレフィックス分布の将来の傾向を完全に予測することは不可能である。各バンクの寸法を固定することは、別のバンクのまばらにしか使用されていないまま１個のメモリバンクを使い尽くす危険性をはらんでおり、ある条件下において検索エンジンの容量に影響を与える場合がある。更に、アルゴリズム全体をハードウエアで実現することは極めて複雑なものとなる場合のあるテーブルアップデート及びアップデート期間中のメモリの割当て／割当て解除を包含する種々の機能をサポートするのに必要な論理を複雑化させる。
【００１８】
図２Ｃは本発明の１実施例に基づく完全に形態特定可能なメモリ、多段パイプラインマルチビットトライネットワーク検索エンジンを示している。ＮＰＳＥ１０２は、ＮＰＳＥ１０２をシステム制御器１０１へ結合させるＮＰＵインターフェース２００と、アービター（仲裁器）２０１と、ＣＰＵ２０２によって実行されるプログラムを包含する関連するメモリ（ＳＲＡＭ）２０３を具備する中央処理ユニット（ＣＰＵ）２０２と、ＮＰＳＥ１０２を外部メモリ１０３へ結合させるＳＲＡＭ制御器２０４と、パイプライン論理ユニット２０５ａ−２０５ｎ及び一連の仮想メモリバンク（例示的実施例においては１６個）を形成する対応する組の形態特定可能なメモリブロック２０６ａ−２０６ｎのアレイ（例示的実施例においては１６個）とを包含しており、パイプライン論理ユニット２０５ａ−２０５ｎ及びメモリブロック２０６ａ−２０６ｎはメッシュ型クロスバー２０７によって結合されており、仮想バンクの形態特定を行うことを可能としている。ＮＰＳＥ１０２により実施される主要なタスクはルートの挿入、削除及び検索であり、そのことは、ＮＰＳＥ１０２が、内部及び外部メモリ内にルートを挿入し且つそれからルートを削除することによりルーチングテーブルを維持し、且つ提示されたプレフィックスに関してルートの検索を実施し且つ関連する次のホップ情報をリターンすることを期待している。
【００１９】
図３は本発明の１実施例に基づく完全に形態特定可能なメモリ、多段パイプラインマルチビットトライネットワーク検索エンジンに対する実行パイプ段を例示しており、図２Ｃと関連して理解することを意図している。ＮＰＳＥ１０２は可変段パイプライン型検索エンジンであり、動作が通過する実行ステージ（段）の数はプレフィックス長に依存する。この特徴は、検索エンジンが平均操作レイテンシー（待ち時間）を減少させることを可能とし、そのことは多くのルーチングシステムにおいて重要なことである。
【００２０】
ＮＰＳＥ１０２に対する実行パイプ段の数における可変部はプレフィックス検索コアであり、それは４個の実行パイプ段をスパンし且つ各メモリバンク２０６ａ−２０６ｎに関して操作即ち演算を行う。プレフィックス検索コアは、アドレスがクロスバーを介して指定されたメモリブロックへ送られるアドレスクロスバー段と、メモリアクセス段と、プレフィックスデータがパイプライン論理ユニット２０５ａ−２０５ｎへ戻るデータクロスバー段と、アクセスされたプレフィックスデータが検査され且つ新たなアドレスが次のメモリバンクに対して発生される最後のデータ処理（パイプライン論理）段とを包含している。
【００２１】
４ビットのストライド幅を有する３２ビットＩＰｖ４プレフィックスの場合には、検索パイプラインは、各パイプライン論理ユニット２０５ａ−２０５ｎによって１個づつ８個のメモリバンクに対してのアクセスを必要とする。各メモリアクセスは４個の実行パイプ段を必要とするので、このことは、その他の前部及び後部の不変の処理段に加えて、３２個の段（ステージ）となる。ＩＰｖ６プレフィックスの場合には、検索パイプラインは、通常、１６個のメモリアクセスを必要とする。何故ならば、典型的に、１２８アドレスプレフィックスビットのうち４６ビットのみが検索において関連性があるに過ぎないからである。この場合において必要とされる実行パイプ段の数は、その他の前部及び後部の不変の処理サイクルに加えて、６４である。
【００２２】
本発明においては、ＮＰＳＥ１０２によって取扱われる最大寸法のプレフィックス（例えば、ＩＰｖ６パケットの場合６４ビットプレフィックス）に対応する少なくとも最後のパイプライン論理ユニット２０５ｎ及び中間プレフィックス寸法（例えば、ＩＰｖ４パケットの場合３２ビットプレフィックス）に対応するもう１つのパイプライン論理ユニット２０５ｉが、両方共、パイプライン終了点に到達した場合に、信号アービター２０１及び／又はＣＰＵ２０２に対して適合される。適宜のパイプラインユニット２０５ｉ及び２０５ｎからの結果を使用してデータテーブルへアクセスし、そのことは多様な態様のうちのいずれかによって達成することが可能である。例示的な実施例はＳＲＡＭ制御器２０８の入力においてマルチプレクサを使用することを例示しているが、当業者によって理解されるように、例えば、パイプラインユニット２０５ｉからの結果は更なる処理を行うことなしに残りのパイプラインユニット２０５ｉ＋１乃至２０５ｎを関して単に通過させることが可能である。本願出願人の「トライを基礎としたルックアップアルゴリズムのパイプライン型ハードウエア実現例におけるルックアップレイテンシーを実現させる方法（Ａ  ＭＥＴＨＯＤ  ＴＯ  ＲＥＤＵＣＥ  ＬＯＯＫＵＰ  ＬＡＴＥＮＣＹ  ＩＮ  Ａ  ＰＩＰＥＬＩＮＥＤ  ＨＡＲＤＷＡＲＥ  ＩＭＰＬＥＭＥＮＴＡＴＩＯＮ  ＯＦ  Ａ  ＴＲＩＥ−ＢＡＳＥＤ  ＬＯＯＫＵＰ  ＡＬＧＯＲＩＴＨＭ）」という名称の米国特許出願に記載されているタイプの完全に可変型のパイプラインを使用することも可能であり、尚その特許出願を引用により本明細書に取込む。
【００２３】
メモリ寸法問題のデータセット依存性を解決するために、仮想バンクに対してメモリブロックを動的に割当てるための技術が本発明において実現されており、メッシュ型クロスバー２０７（即ち、リターンデータクロスバーと結合されており且つそれと相関されているアドレスクロスバー）及び仮想メモリバンク２０６ａ−２０６ｎを形成している１個又はそれ以上の物理的メモリ内の１組の小型のメモリブロックによって達成されている（注意すべきことであるが、メモリブロックの数はパイプラインユニット２０５ａ−２０５ｎの数よりも著しく大きく且つ全てのメモリブロックは仮想メモリバンク２０６ａ−２０６ｎとして論理的に編成した単一の物理的メモリ内に包含させることが可能である）。クロスバー２０７は関連するパイプライン論理ユニット２０５ａ−２０５ｎによってアクセスすることが可能なｎ個の仮想バンク２０６ａ−２０６ｎを形成するために１個又はそれ以上の物理的メモリから任意の数のメモリブロックを接続させる。与えられた仮想バンクに対して任意のメモリブロックの割当てはコンフィギュレーション即ち形態特定及び／又はそのブロックと関連する制御レジスタ（不図示）を修正することにより達成され、各仮想バンクの寸法は与えられたルーチング環境に対するプレフィックス分布に沿うように動的に調節することが可能であるので本装置に対してより大きな柔軟性を加えている。
【００２４】
パイプライン論理ユニットはプレフィックス検索を司るが、埋込型ＣＰＵ２０２はルートの挿入及び削除及び関連する所要のメモリ管理を実施する。ＣＰＵ２０２上で稼動するソフトウエアは各操作（演算）期間中データ構造を最適化させ、与えられた仮想バンクに対してメモリブロックの割当て及び割当て解除を行い、そのデータ構造を格納するために各ブロックにおけるメモリを管理し、且つ次のホップ情報を格納するために外部ＳＲＡＭにおけるメモリを管理し、本装置に対して柔軟性及びプログラム可能性を付加している。
【００２５】
動作について説明すると、ルート検索コマンドがＮＰＳＥ１０２へ送られると、そのコマンド及び関連するデータが同期され且つＮＰＵインターフェースユニット２００においてバッファされる。次いで、そのコマンドはアービター２０１を介して通過し且つ第一仮想バンク内の初期的ルートテーブルに対するアドレス及びその他の制御信号でパイプライン検索コア（パイプラインユニット２０５ａ−２０５ｎ）をアクセスすべくスケジュールされる。そのアドレスはアドレスクロスバーを介して通過し且つ指定されたメモリブロックへアクセスする。読取操作が実施され且つ読取データが出力データクロスバーを介して第一パイプライン論理ユニット２０５ａへリターンされる。トライエントリデータが処理され且つ検索器と比較されて一致条件を決定し且つ次のレベル（又はバンク）のアドレスを計算する。
【００２６】
次いで、次のルートテーブルアドレスがアドレスクロスバーを介して通過し且つ検索処理が繰返し行われる。この検索処理は、不一致が決定される場合、又は有効なルートが見つかったことを表わす葉ノード（端部ノード）に遭遇した場合に、パイプライン論理ユニット２０５ａ−２０５ｎのいずれかにおいて終了する。次いで、終了されたコマンドが、パイプライン終了点に到達するまで、何等のメモリアクセス及び処理を行うことなしに残りのパイプライン段を介して通過する。４ビットストライドを有するＩＰｖ４検索の場合、その終了点は８番目のパイプライン論理ユニットであり、４ビットストライドを有するＩＰｖ６の検索の場合には、その終了点は１６番目（即ち最後の）パイプライン論理ユニットである。
【００２７】
有効なルートが見つかった場合には、最後のメモリアクセスから計算されたアドレスがＳＲＡＭ制御器２０８へ送られ、それは、次いで、オフチップへ移行し外部の次のホップメモリ１０３へアクセスする。ＳＲＡＭデータがリターンされると、リターンされたデータが同期され且つＮＰＵインターフェースユニット２００の出力バッファにおいてバッファされる。一方、有効なルートが見つからない場合には、不一致結果が一連のパイプラインバッファを介して通過し且つ次のホップデータが到着するのと同じサイクル（検索の開始に関連し）においてＮＰＵインターフェースユニット出力バッファに到着する。これで検索は完了し且つＮＰＵ１０１による読出しを待機する。全ての検索操作はパイプライン型であり、従って高い検索処理能力を達成するためにＮＰＳＥ１０２はサイクル毎に１つの検索コマンドを実施することが可能である。
【００２８】
ルートの挿入及び削除の操作は、パイプラインサーチコアに加えて、本発明においては埋込型ＣＰＵ２０２へアクセスすることが必要である。検索コマンドと同様に、挿入／削除コマンドが、終了点を探し出すためにパイプライン検索コアへアクセスすべく最初にスケジュールされる、即ち、挿入又は削除されるべきプレフィックスが停止するトライレベルはプレフィックステーブル内のその他の（残りの）プレフィックスとオーバーラップする。その終了点は不一致結果又は葉ノード終了とすることが可能である。
【００２９】
通常の検索操作と異なり、コマンドが検索パイプライン終了点に到達すると、挿入及び削除操作は埋込型ＣＰＵ２０２をインタラプトさせ且つ挿入及び削除の作業を処理するソフトウエアプログラムを活性化させる。次いで、テーブルアップデートソフトウエア（ＳＲＡＭ２０３からＣＰＵ２０２内へロードされる）がアービター２０１及びパイプライン論理ユニット２０５ａ−２０５ｎから通過されたデータを処理する。ルート挿入又は削除操作期間中、個々の環境に依存してメモリブロックの割当て又は割当て解除を行うことが可能である。付加的なメモリブロックが仮想バンクに対して割り当てられると、ＣＰＵ２０２は適宜のパイプライン論理ユニット２０５ａ−２０５ｎに対してコンフィギュレーション（形態特定）レジスタ書込コマンドを発行し、クロスバー２０７のコンフィギュレーション即ち形態特定及び／又はメモリブロックコンフィギュレーションレジスタを修正する。次いで、一連の操作がパイプラインユニット２０５ａ−２０５ｎに対して発行され、仮想バンクに対して割当てられているメモリブロック内のルーチングテーブルデータ構造をアップデートし、且つ次いで外部メモリ操作がＳＲＡＭ制御器２０８へ送られて外部ＳＲＡＭ１０３をアップデートする。挿入又は削除の操作はトライテーブル及び次のホップテーブルがアップデートされた後に完了する。最後に、操作完了ステータスがＮＰＵインターフェースユニット２００内のステータスレジスタへ送られ、それはＮＰＵ１０１によって読取ることが可能である。
【００３０】
ルート挿入及び削除操作は、ルート検索操作とパイプライン型とさせることが可能であるが、メモリコヒーレンシィーを確保するために、一度にパイプライン内において１つのルート挿入又は削除操作がアクティブ即ち活性なものとすることが可能であるに過ぎない。
【００３１】
ＮＰＳＥ１０２は、可変パイプライン論理、形態特定可能メモリバンク及び関連するクロスバーを包含する１組の確信的なマイクロアーキテクチャ特徴、及び既存の解決手段に対し実質的な改良を与えるテーブルアップデート及びメモリ管理用の埋込型ＣＰＵを使用することにより、処理能力の欠如、アルゴリズム検索エンジンの典型的なハードウエア実現例に関連するプログラム可能性及び適用性問題を解決している。
【００３２】
本発明は検索処理を細かくパイプライン化することにより処理能力を取扱っている。各パイプラインにおいて１つのメモリアクセスのみを許容することにより、メモリ設計がサポートする最大処理能力を達成することが可能である。データセットの不確実性により発生されるメモリ分布問題に対する可能性を除去するために仮想バンクを使用している。メモリを小さなブロックに分割し且つクロスバーの使用を介して所要に応じ該ブロックを任意のメモリバンクへ動的に割当てることにより、各バンクの寸法は各データセットの個別的な条件に調整することが可能であり、全ての条件下において検索エンジン容量を最大とさせる。プログラム可能なプロセッサ及び関連するメモリを使用することにより、テーブルアップデート及びメモリ管理に対する全体的なプログラミングの柔軟性を可能なものとしている。本発明のアプローチにより、コアハードウエアのタスクが簡単化され且つ設計リスクが減少されている。
【００３３】
以上、本発明の具体的実施の態様について詳細に説明したが、本発明は、これら具体例にのみ制限されるべきものではなく、本発明の技術的範囲を逸脱することなしに種々の変形が可能であることは勿論である。
【図面の簡単な説明】
【００３４】
【図１】本発明の１実施例に基づく完全に形態特定可能なメモリ、多段パイプラインマルチビットトライネットワーク検索エンジンを使用した処理システムを示した概略図。
【図２Ａ】従来技術に基づくパイプライン型マルチビットトライネットワーク検索エンジンに対するマイクロアーキテクチャを示した概略図。
【図２Ｂ】従来技術に基づくパイプライン型マルチビットトライネットワーク検索エンジンに対するマイクロアーキテクチャを示した概略図。
【図２Ｃ】本発明の１実施例に基づくパイプライン型マルチビットトライネットワーク検索エンジンに対するマイクロアーキテクチャを示した概略図。
【図３】本発明の１実施例に基づく完全に形態特定可能なメモリ、多段パイプラインマルチビットトライネットワーク検索エンジンに対する実行パイプ段を示した概略図。
【符号の説明】
【００３５】
１００  処理システム
１０１  ネットワーク処理ユニット（ＮＰＵ）
１０２  ネットワークパケット検索エンジン（ＮＰＳＥ）
１０３  外部メモリ
１０４  プレフィックステーブル
１０５  データテーブル
１０６  バックプレーン
１０７  ネットワークインターフェース
【図１】
2004194319.tif 000003
【図２Ａ】
2004194319.tif 000004
【図２Ｂ】
2004194319.tif 000005
【図２Ｃ】
2004194319.tif 000006
【図３】
2004194319.tif 000007