(57)【要約】高速パケット転送のための方法及びシステムは、入力アドレス内のビットに基づいて、オンチップメモリに記憶されたトライ（ＳＴ１）データ構造を横断的に探索することを含む。入力アドレス内のビットは、データ構造における予め決められたロケーションとして現れる。第１の値を有しかつ決められたロケーションより前に位置したビットのビット数が計算される。計算されたビット数（ＳＴ４）は、上記入力アドレスを有するパケットが転送される先であるアドレスの第２の記憶装置におけるオフセットに対応する。アドレスは、オフチップメモリ装置への単一のアクセスを使用して抽出されることが可能である（ＳＴ９）。
2004537921.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータネットワークにおいてパケットが方向付けられる次のノードに対応する出力ポートを決定するための方法であって、
（ａ）複数の可変長のネットワークアドレスのプレフィックスに基づいてデータ構造を構成することと、
（ｂ）上記データ構造を第１の記憶装置に記憶することと、
（ｃ）上記複数のネットワークアドレスのプレフィックスに対応する複数の出力ポート識別子にてなるセットを第２の記憶装置に記憶することと、
（ｄ）入力されたアドレス内のビットに基づいて上記第１の記憶装置におけるデータ構造を横断的に探索し、上記入力されたアドレスに一致する最も長いネットワークアドレスのプレフィックスに対応するデータ構造内のロケーションを決定することと、
（ｅ）上記データ構造における上記ロケーションに基づいて、上記入力されたアドレスに対応する上記出力ポート識別子のための上記第２の記憶装置におけるオフセットを決定することとを含む方法。
【請求項２】
データ構造を構成することは、トライデータ構造を構成することと、上記トライデータ構造を示すビットパターンを上記第１の記憶装置に記憶することとを含む請求項１記載の方法。
【請求項３】
上記データ構造を横断的に探索することは、
（ａ）開始ポインタを、上記第１の記憶装置に記憶された上記ビットパターンにおける最初のＸビットパターンを指示するように初期化することを含み、上記最初のＸビットパターンは上記トライデータ構造における第１のレベルに対応し、Ｘは上記トライデータ構造の次数に等しい整数であり、
（ｂ）上記入力されたアドレスの最初のｌｏｇ２（Ｘ）ビットを読み込み、上記最初のｌｏｇ２（Ｘ）ビットの値に基づいて上記第１の記憶装置に記憶された上記ビットパターンにおけるオフセットを計算することと、
（ｃ）上記オフセットによって指示されるビットが第１の値又は第２の値のいずれを有するかを決定することと、
（ｄ）上記ビットが第１の値を有するという決定に応答して、上記開始ポインタの現在のレベルをインクリメントし、上記トライデータ構造の先行するレベルにおけるオフセットより前の上記第１の値を有するビットのビット数に基づいてオフセットを計算し、上記第１の値を有するビットのビット数に基づいて現在のレベルにおける新たなビットの位置を指示するように上記開始ポインタを進め、ステップ（ｃ）が結果的に上記第２の値を有するビットを指示するオフセットをもたらすまでステップ（ｂ）乃至（ｄ）を上記入力されたアドレス内の各ｌｏｇ２（Ｘ）ビットについて繰り返すことと、
（ｅ）上記オフセットによって指示されるビットが上記第２の値を有するという決定に応答して、上記オフセットの現在の位置に至るビットまでの上記第１の値を有するビットであって、当該オフセットの現在の位置のビットも含む上記第１の値を有するビットの合計のビット数を計算することとを含み、計算された上記第１の値を有するビットの上記合計のビット数は、上記出力ポート識別子を抽出する上記第２の記憶装置におけるオフセットに対応する請求項２記載の方法。
【請求項４】
上記データ構造を第１の記憶装置に記憶することは、上記トライデータ構造における各ノードに対する単一のビットを上記第１の記憶装置に記憶することを含む請求項２記載の方法。
【請求項５】
上記データ構造を第１の記憶装置に記憶することは、次のホップアドレスポインタ情報を上記第１の記憶装置から除外することを含む請求項２記載の方法。
【請求項６】
上記データ構造は、第１の値のビットが子を有するノードを表しかつ第２の値のビットが子を持たないノードを表すトライ構造を備える請求項１記載の方法であって、ステップ（ｂ）において取得されるロケーションに基づいて上記第２の記憶装置におけるオフセットを決定することは、
（ａ）上記ロケーションより前の上記第１の値を有するビットのビット数を計数することと、
（ｂ）上記第１の値を有する上記ビットのビット数に基づいて、上記出力ポート識別子に対応する上記第２の記憶装置におけるオフセットを計算することとを含む請求項１記載の方法。
【請求項７】
上記第１の記憶装置は上記第２の記憶装置より短いアクセス時間を有する請求項１記載の方法。
【請求項８】
パケットがルーティングされる次のノードのネットワークアドレスに対応する出力ポート識別子を決定するための方法であって、
（ａ）入力されたネットワークアドレス内のビットに基づいてトライデータ構造を横断的に探索し、上記入力されたネットワークアドレス内のビットに基づいて上記データ構造におけるロケーションを決定することと、
（ｂ）上記トライデータ構造における上記ロケーションより前の第１の値を有するビットのビット数の計数値を保持することと、
（ｃ）上記第１の値を有する上記ビットのビット数に基づいて、記憶装置から出力ポート識別子を抽出するためのオフセットを決定することと、
（ｄ）上記オフセットを使用して上記出力ポート識別子を抽出することとを含む方法。
【請求項９】
入力されたネットワークアドレス内のビットに基づいてトライデータ構造を横断的に探索することは、第１の記憶装置に記憶されたビットパターンを横断的に探索することを含み、
上記出力ポート識別子を抽出することは、上記第１の記憶装置より低速である第２の記憶装置から上記出力ポート識別子を抽出することを含む請求項８記載の方法。
【請求項１０】
上記トライデータ構造におけるロケーションを決定することは、上記入力されたネットワークアドレス内のすべてのビットに基づいて、上記トライデータに子を持たないオフセットを位置決めすることを含む請求項８記載の方法。
【請求項１１】
ステップ（ａ）乃至（ｄ）はハードウェアで実装される請求項８記載の方法。
【請求項１２】
ステップ（ａ）乃至（ｄ）はソフトウェアで実装される請求項８記載の方法。
【請求項１３】
ステップ（ａ）乃至（ｄ）はハードウェアとソフトウェアとの組み合わせで実装される請求項８記載の方法。
【請求項１４】
ネットワークアドレスに対応する出力ポート識別子に関する高速のルックアップを実行するための高速パケット転送エンジンであって、
（ａ）複数の可変長のネットワークアドレスのプレフィックスに対応するトライデータ構造を記憶する第１の記憶装置を備え、上記トライデータ構造は、可変長のネットワークアドレスのプレフィックスに対応するロケーションに複数の葉ノードを含み、
（ｂ）複数の出力ポート識別子を記憶する第２の記憶装置と、
（ｃ）入力されたアドレス内のビットに基づいて上記第１の記憶装置内のトライデータ構造における葉ノードのロケーションを決定し、上記ロケーションに基づいて上記第２の記憶装置から出力ポート識別子を抽出するためのオフセットを決定するプロセッサとを備える高速パケット転送エンジン。
【請求項１５】
上記トライデータ構造は内部ノードを含み、ポインタ情報は上記内部ノードに記憶されない請求項１４記載の高速パケット転送エンジン。
【請求項１６】
上記第１の記憶装置は上記第２の記憶装置より短いアクセス時間を有する請求項１４記載の高速パケット転送エンジン。
【請求項１７】
上記第１の記憶装置は上記トライデータ構造を示すビットパターンを記憶し、上記トライデータ構造における各ノードは上記ビットパターンにおける単一のビットによって表される請求項１４記載の高速パケット転送エンジン。
【請求項１８】
上記第１の記憶装置と上記プロセッサとは第１のチップ上に設けられた請求項１４記載の高速パケット転送エンジン。
【請求項１９】
上記第２の記憶装置は、上記第１のチップから分離された第２のチップ上に設けられた請求項１８記載の高速パケット転送エンジン。
【請求項２０】
上記プロセッサは、
（ａ）上記入力されたアドレスからビットを抽出するビット抽出器と、
（ｂ）上記第２の記憶装置における上記オフセットに対応する第１の値を有するビットのビット数の総和を計算するために使用されるマスクを生成するビットをマスキングするマスク生成器と、
（ｃ）上記マスクと上記入力されたアドレスから抽出された上記ビットとを使用して上記第１の値を有するビットのビット数の総和を計算するオフセット計算機とを備え、上記オフセットは上記総和に対応する請求項１４記載の高速パケット転送エンジン。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高速パケット転送のための方法及びシステムに関する。特に、本発明は、パケットの転送先である次のノードに対応したインタフェースを決定するために、入力されたアドレス内のビットに基づいたデータ構造において取得されるロケーションが使用される、高速パケット転送のための方法及びシステムに関する。
【背景技術】
【０００２】
関連出願．
本出願は、２００１年１０月１８日に出願された米国特許出願シリアル番号第０９／９８１，８５８号及び２００１年７月３１日に出願された米国仮特許出願シリアル番号第６０／３０８，９４１号の利益を主張するものであり、上記各出願による開示内容は参照によりそのままここに含まれる。
【０００３】
交付金についての申告．
本研究は、国家安全保障局（ＮＳＡ）から交付番号（grant number）１００９３．００２により支援されたものである。従って、米国政府は本発明に所定の権利を保有する。
【０００４】
インターネットのトラフィックは、毎年１０倍の倍率で増大しているが、インターネット上のホストの数は２年毎に３倍の倍率で増大している。このことは、同じ性能のレベルを維持するためには、パケットは今や、転送するデータベースがより大きくなっているにも関わらず、より高速に転送される必要があることを意味する。データベースがより大きくなると、パケットの転送先である次のノードのアドレスを決定するために必要とされるメモリアドレスの数を増大させる。このようなアドレスは、一般に、次のホップアドレスと呼ばれる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ギガビット又はテラビットのルーティングのような高速ルーティングの需要を満たすためには、アドレスのルックアップをハードウェアにおいて実行することが望ましい。現時点では、最も高速なソフトウェアによるアプローチでもアドレスのルックアップを実行するには平均で数百ナノ秒を必要とし、そのような高速転送には不適当である。アドレスのルックアップをハードウェアにおいて実行することに伴う１つの問題点は、より大きくなった転送テーブルが、アドレスのルックアップを実行するチップのメモリに格納されないということにある。アドレスのルックアップをハードウェアにおいて実行することに伴う１つの問題点は、必要なテーブルを記憶するためには大量のメモリが必要とされることにある。従って、テーブルは、大型で低速であってかつ通常はオフチップであるメモリに記憶される。さらに、アドレスのルックアップはテーブルへの複数回のアクセスを必要とする。一般に、大型で低速でありかつ通常はオフチップであるメモリに記憶されたテーブル全体（full table）にアクセスすることは、アドレスのルックアップを実行する時間を大幅に延長させる。従って、高速なアドレスのルックアップ方式では、低速な、テーブル全体へのアクセスの回数が減少される必要がある。
【０００６】
高速なアドレスのルックアップにおけるもう１つの重要な要素は、一定のアドレスルックアップ時間の必要性である。一定のアドレスルックアップ時間を有することは、光バーストスイッチング（ＯＢＳ）等の新たに登場したアプリケーションにとっては特に重要である。光バースト交換ネットワークにおいては、信号方式又はシグナリング（signaling）はアウトオブバンド（out of band）で実行される。シグナリングチャンネルだけが、光／電気／光（Ｏ／Ｅ／Ｏ）変換を受ける。シグナリングメッセージはデータバーストより前に送信され、経路に沿ったノードの各々において解釈される。シグナリングメッセージに応答して、ノードは、データバーストが到着する前にデータバーストのための経路を確立する。利用可能な経路に関する確認をネットワークノードから受信することなく、データバーストは、予め決められた遅延の後に送信される。遅延は、経路に沿ったノードの数に依存する。各ノードにおけるセットアップ時間が可変であれば、遅延は予測不可能であり、結果として効率の悪いネットワークをもたらす。従って、ネットワークアドレスのルックアップを実行するために使用される機構は、高速で一定のルックアップ時間を達成することが望ましい。
【０００７】
パケットの次のホップアドレスを決定するためのルックアップは、パケット転送において、時間について最も重要な部分である。大型のデータベースを検索することの問題点は、ルーティングテーブルが複数の可変長のプレフィックスとそれらの対応する次のホップアドレスとを記憶するという事実と合わさってさらに悪化する。パケットを転送するためには、ルータは、ルーティングテーブルにおいて、転送されるパケット内の宛先アドレスに最も長く一致するプレフィックスを発見する必要がある。下記に示した表１は、ある例示的なルーティングテーブルを示している。
【０００８】
【表１】
2004537921.tif 000003
【０００９】
表１において、左側のエントリは、転送されるパケットの宛先アドレスフィールドにおけるビットと比較される、ネットワークアドレスのプレフィックスである。表１において、キャラクタ「＊」はワイルドカード（任意の数字）を表す。表１の右欄は、パケットの転送先であるノード又はネットワークインタフェースに対応する識別子を表す。例えば、大部分のルータはいくつかのネットワークインタフェースを有し、１つのインタフェースは、ルータの直接の接続先である各ノードに対応している。表１での次のホップの欄における識別子は、これらのインタフェースに対応している可能性がある。
【００１０】
表１をそのルーティングテーブルとして使用するルータが、最初の８ビットが０１１１０１０１である宛先ネットワークアドレスを有するパケットを受信する場合、表１中の複数のプレフィックスがこのアドレスに一致する。例えば、アドレス０１＊、０１１１＊及び０１１１０１＊は、上記宛先アドレスに一致する。一致するこれらのアドレスのうちで、最も長く一致するものは、プレフィックス０１１１０１＊を備えたエントリである。次のホップアドレスに対応する識別子は、１である。
【００１１】
最も長く一致するプレフィックスを検索するために、多数のアプローチが開発されている。ほとんどのアプローチは、探索トライ（trie）又は探索木（探索ツリー）のいずれかのカテゴリに入る。従来の探索トライでは、受信されたパケットのアドレス内の各ビットは、トライを通る経路を決定するために使用される。「０」は、トライ内のサブツリーの左半分を指示し、「１」はトライ内のサブツリーの右半分を指示する。ルックアップは、葉（リーフ）ノードの位置が決定されるまでトライを横断的に探索する（トラバースする）ことによって進行する。トライデータ構造は、子ノードに対するポインタを記憶した複数のノードを含む。すべての葉と、いくつかの内部ノードとは、次のホップ情報を含む。いくつかの実装は、次のホップ情報を記憶する葉のみを必要とするが、この場合、内部ノードは子ノードに対するポインタのみを記憶する。大部分の従来型の実装では、複数の次のホップアドレスを含むトライ構造の全体が１つのメモリに記憶される。木に基づくルックアップでは、転送されるパケット内の宛先アドレスの値が、木データ構造における各サブツリーのメジアン値と比較される。その値がメジアン値より小さいならば、探索はサブツリーの左半分へ進み、その値がメジアン値よりも大きいならば、探索はサブツリーの右半分へ進む。この場合もまた、データ構造の全体はただ１つのメモリのみに記憶され、探索はあるエントリに進み、そのエントリも同様に次のホップエントリを記憶している。
【００１２】
トライに基づくアドレスのルックアップ及び木に基づくアドレスのルックアップに伴う１つの問題点は、従来のアプローチが、すべての内部ノードにおける子ノードに対するポインタを記憶するという事実にある。複数のノードにおけるポインタを記憶することは、データ構造のサイズを増大させる。ルーティングテーブルが大型になるにつれて、このようなデータ構造はオンチップメモリに完全には格納されなくなる。その結果、オフチップメモリへのアクセスが必要になる。複数回のオフチップメモリへのアクセスが必要になるので、高速かつ一定のネットワークアドレスのルックアップという目標は達成され得ない。従って、従来型の木に基づきかつトライに基づくルックアップ方式に関連付けられた問題点を除去した、高速なアドレスのルックアップのための方法及びシステムに対する必要性が存在する。
【課題を解決するための手段】
【００１３】
１つの態様によれば、本発明は、コンピュータネットワークにおいてパケットが方向付けられる次のノードに対応する出力ポートを決定するための方法を含む。本方法は、可変長のネットワークアドレスのプレフィックスに基づいてデータ構造を構成することを含む。データ構造は記憶装置に記憶される。ネットワークアドレスのプレフィックスに対応する出力ポート識別子のセットは、もう１つの記憶装置に記憶される。データ構造は、入力されたアドレス内の複数のビットに基づいて横断的に探索され、入力されたアドレスに一致する最も長いネットワークアドレスのプレフィックスに対応するロケーションが決定される。データ構造におけるロケーションは、入力されたアドレスに対応する出力ポート識別子のための第２の記憶装置におけるオフセットを決定するために使用される。
【００１４】
最も長く一致するプレフィックスは、データ構造内で取得されるロケーションに基づいて決定可能であるので、ポインタがデータ構造内のノードにおいて記憶されているという必要条件は存在しない。その結果、データ構造のサイズと、結果的にメモリの必要条件とが削減される。従って、データ構造はオンチップメモリに格納され、このことは、ルックアップ時間を短縮する。
【００１５】
従って、本発明の目的は、複数の内部ノードにおけるポインタを記憶することを必要とする従来のアルゴリズムの問題点を除去する、高速なアドレスのルックアップのための方法及びシステムを提供することにある。
【００１６】
本発明のさらにもう１つの目的は、入力されたアドレスに基づいて取得される転送テーブルのデータ構造におけるロケーションに基づいて、次のホップアドレスを位置決めするためのオフセットを計算する、高速なネットワークアドレスのルックアップのための方法及びシステムを提供することにある。
【００１７】
これまで本発明の目的のうちのいくつかについて述べたが、以下で最も良く説明されるような添付の図面に関連して解釈するとき、説明の進行に伴って他の目的も明らかとなるであろう。
【００１８】
次に、添付の図面を参照して本発明の好適な実施形態について説明する。
【発明を実施するための最良の形態】
【００１９】
以下、添付の図面を参照して、本発明の好適な実施形態について説明する。まずは、高速なネットワークアドレスのルックアップに適当でありかつ内部ノードにおけるポインタの記憶を必要としないデータ構造を構成するための例示的な方法について説明する。次に、このデータ構造を使用して高速なネットワークアドレスのルックアップを実行する方法について説明する。最後に、本発明を実装することのできる例示的なハードウェアについて検討する。
【００２０】
高速なネットワークアドレスのルックアップに係るデータ構造の構築．
ある態様によれば、本発明は、オンチップメモリに転送テーブルのデータ構造を記憶するための方法を含む。このような方法は、内部ノードにおけるポインタの記憶を必要としない。その結果、データ構造はより小さくされることが可能であり、オンチップメモリに格納される可能性が高くなる。ある実施形態では、データ構造はトライデータ構造である。トライデータ構造を構成する一例は、ネットワークアドレスのプレフィックスにてなるセットに基づくものであった。下記の表２は、例示的なアドレスのプレフィックスと次のホップアドレスに対応する識別子とを示す。表２中のプレフィックスは、ＩＰアドレスに対応することが可能である。例えば、表２の最初のエントリにおけるプレフィックス１０＊は、ＩＰアドレス１２８．０．０．０に対応することが可能である。しかしながら、本発明はＩＰアドレスに限定されない。ここに説明した方法及びシステムは、アドレスのルックアップが可変長のプレフィックスに基づいて実行されるあらゆる方式において、高速パケット転送のために使用されることが可能である。本発明のアプリケーションの例には、ＩＰ転送及び光バーストスイッチングが含まれる。
【００２１】
【表２】
2004537921.tif 000004
【００２２】
トライデータ構造を構築するために、プレフィックスは、好適には昇順でソーティングされる。２つのプレフィックスが同じ値を有する場合は、長さが短い方のプレフィックスがより小さいとされる。例えば、プレフィックス１０＊は１００＊より小さいものとされる。下に示した表３は、昇順でソーティングされた後の表２のプレフィックスを示す。
【００２３】
【表３】
2004537921.tif 000005
【００２４】
いったんプレフィックスがソーティングされると、次のステップは、トライデータ構造の構築を開始することである。トライデータ構造を構築する際にはトライの完成（trie completion）が果たされ、この場合、葉のみが有効なプレフィックスを表現するということを保証する必要がある。以下で説明される図面では、トライデータ構造内の各葉のそばの数字は、次のホップアドレスを表す。但し、これらのアドレスは、単に例示の目的で図面内に示されたものである。本発明に係るトライデータ構造は、次のホップアドレス又は次のホップアドレスのポインタが葉ノードにおいて記憶されることを必要としない。各ノードに対してメモリに記憶されるのは単一のビットのみであるということは、本発明の１つの特徴である。
【００２５】
図１は、初期設定におけるトライデータ構造を示す。図１において、このトライデータ構造は、根ノード１００と、複数の葉ノード１０２とを含む。ここに説明された実装では１６方向（１６ウェイ）トライが使用されているので、図示された例には１６個の葉ノードが存在する。これらの葉ノードは、別のノードと交差することなく根ノード１００に直接に接続されているので、根ノード１００の子と呼ばれる。各葉ノード１０２は、アスタリスクで表されたデフォルトである次のホップアドレスを指示するように初期化される。
【００２６】
いったん根ノード１００が初期化されると、トライには、表３におけるソーティングされたリストからの各エントリが追加される。表３中の最初のエントリは、００１００１１０＊である。図２は、このエントリを追加した後のトライデータ構造を示す。このプレフィックスの最初の４ビット（００１０）は、根ノード１００のビット２を指示する。図２において、根ノード１０２のビット２は、左から３番目の子ノード１０２で表される。このプレフィックスは４ビットより長いため、根ノード１００の３番目の子には追加ノード１０４が追加される。ノード１０４の子である複数の葉ノード１０６は、それらの親（根ノード１００）の次のホップエントリを継承する。プレフィックスの次の４ビット（０１１０）は、新たに追加されたノード１０４の子６を指示する。表３から、このエントリに対応する次のホップアドレスは５になる。その結果、ノード１０４の６番目の子に対応する次のホップアドレスは５に変更される。
【００２７】
データ構造に追加されるテーブル内の次のエントリは０１＊であり、これに対する次のホップは７である。図３は、トライデータ構造にこのエントリを追加した結果を示す。０１＊で表されるプレフィックスの範囲に含まれる根ノード１００の子は、０１００、０１０１、０１１０及び０１１１である。従って、根ノード１００の４番目と、５番目と、６番目と、７番目の子に関連付けられた次のホップアドレスは、デフォルトのルートから７に変更される。
【００２８】
データ構造に追加される表３中の次のエントリは、０１００００００＊である。このエントリに対応する次のホップアドレスは、１２である。図４は、このエントリを追加した後のデータ構造を示す。図４においては、このエントリの最初の４ビット（０１００）に対応して、新たなノード１０８が根ノード１００の４番目の子に追加されている。ノード１０８の子は、ノード１０８の親から次のホップアドレス７を継承する。このエントリに係る次の４個の数字（００００）は、ノード１０８の０番目の子に対応する。従って、この０番目の子の次のホップアドレスは、７から１２に変更される。
【００２９】
データ構造に追加される表３からの次のエントリは０１０１＊であり、これに対する次のホップアドレスは２である。図５は、このエントリを追加した後のデータ構造を示す。図５では、根ノード１００の５番目の子に係る次のホップアドレスが、７から２に変更されている。
【００３０】
表３からデータ構造に追加される次のプレフィックスは０１１１＊であり、これに対する次のホップは９である。図６は、データ構造にこのエントリを追加した結果を示す。図６では、根ノード１００の７番目の子の次のホップアドレスが、７から９に変更されている。
【００３１】
データ構造に追加される表３からの次のエントリは、０１１１００００００１１００＊である。このエントリに関連付けられた次のホップアドレスは５である。図７は、このエントリを追加した後のデータ構造を示す。図７では、このエントリの最初の４ビット（０１１１）により、データ構造にノード１１２が追加されている。ノード１１２の複数の子１１４は、ノード１１２の親から次のホップアドレス９を継承する。このエントリの次の４ビット（００００）は、データ構造にノード１１６を追加させる。ノード１１６の複数の子１１８は、ノード１１６の親から次のホップアドレス９を継承する。このデータ構造における次の４ビット（００１１）は、当該データ構造にノード１２０を追加させる。ノード１２０の複数の子１２２は、ノード１２０の親から次のホップアドレス９を継承する。最終的に、このエントリの最後の２ビット（００＊）により、ノード１２０の子００００、０００１、００１０及び００１１に係る次のホップアドレスが９から５に変更される。
【００３２】
データ構造に追加される表３からの次のエントリは１０＊であり、これに対する次のホップアドレスは３である。図８は、このエントリを追加した後のデータ構造を示す。このエントリは、葉ノード１００の子を変化させるのみである。特に、子１０００、１００１、１０１０及び１０１１に関連付けられた次のホップアドレスが、デフォルト値（＊）から３に変更される。
【００３３】
データ構造に追加される表３からの次のエントリは、１０００＊である。このエントリに関連付けられた次のホップアドレスは、６である。図９は、このエントリを追加した後のデータ構造を示す。図９からは、このエントリによって、根ノード１００の８番目の子に関連付けられた次のホップアドレスのみが更新されたことが分かる。この図はまた、ソーティングにおいて１０＊を１０００＊の前に置くことの重要性を説明する。仮にこれが逆転していれば、根ノード１００の子１０２の次のホップは、＊＊＊＊７２７９３３３３＊＊＊＊に間違って設定されることになったであろう。
【００３４】
データ構造に追加される表３からの次のエントリは、１０００１１００＊である。このエントリに対応する次のホップアドレスは、３である。図１０は、このエントリを追加した後のデータ構造を示す。このエントリの最初の４ビット（１０００）により、根ノード１００の８番目の子に新しいノード１２４が追加される。ノード１２４の複数の子１２６は、ノード１２４の親から次のホップアドレス６を継承する。このエントリの次の４ビット（１１００＊）は、ノード１２４の１２番目の子に関連付けられた次のホップアドレスを６から３に変更させる。
【００３５】
データ構造に追加される表３からの最後のエントリは、１０００１１００００００１１００＊である。このエントリに対応する次のホップアドレスは、３である。図１１は、データ構造にこのエントリを追加した結果を示す。このエントリの最初の４ビット（１０００）は、根ノード１００の８番目の子に対応する。しかしながら、ノード１２４が既にデータ構造に追加されているので、これらのビットはデータ構造を変化させない。プレフィックスの次の４ビット（１１００）は、ノード１２４の１２番目の子を指示する。新しいノード１２８が追加され、ノード１２８の複数の子１３０は、ノード１２８の親から次のホップアドレス３を継承する。このエントリの次の４ビット（００００）は、ノード１２８の０番目の子を指示する。これらのビットにより、ノード１３２が追加される。ノード１３２の複数の子１３４は、ノード１３２の親から次のホップアドレス３を継承する。本アドレスの次の４ビット（１１００＊）は、ノード１３２の１２番目の子に関連付けられた次のホップアドレスを３から２に変更させる。
【００３６】
このように、図１１は、表３のエントリに基づくトライデータ構造を示す。先に述べたように、図１１と、図１１に至るまでの準備的な諸図面とにおいて次のホップアドレスを示したが、本発明の重要な態様により、これらの次のホップアドレスは、アドレスのルックアップを実行するプロセッサのメモリに記憶される実際のデータ構造からは省かれる。図１乃至１１において、次のホップアドレスは、データ構造を構成するプロセスをより明確に説明するための単なる例示を目的として葉ノードの隣に示されている。
【００３７】
いったんトライデータ構造が構成されると、オンチップメモリに記憶されるビットパターンは、トライデータ構造の幅優先探索を実行することにより、トライデータ構造から構成されることが可能である。例えば、図１１に示されたデータ構造では、子を有するノードはオンチップメモリにおいて１で表され、子を持たないノードは０で表されることが可能である。従って、根ノード１００の複数の子１０２を表すビットパターンは、ビットパターン００１０１００１１０００００００で表すことができる。図１１に示された残りの子に関しても、ビットパターンを生成することができる。各ノードに対して、ポインタ又は次のホップアドレス等のいかなる追加情報も記憶される必要がない。その結果、本発明に係る転送テーブルのデータ構造は、従来型の転送テーブルのデータ構造より小さくなり、よってオンチップメモリに格納される可能性が高くなる。
【００３８】
図１２は、本発明の一実施形態に係るトライデータ構造のためのオンチップメモリに記憶されることが可能な例示的なビットパターンを示す。図１２に示された参照番号は、図１１に示された子ノード又は葉ノードの参照番号に対応している。図１２から、各葉ノードに対してポインタも次のホップアドレス情報も記憶されるのではないということが分かる。各ノードは、オンチップメモリにおいて単一のビットで表されることが可能である。その結果、本発明の一実施形態に係るデータ構造はサイズに関して圧縮され（コンパクトになり）、オンチップメモリに格納される可能性が高くなる。
【００３９】
次のホップアドレスは、オフチップメモリ装置に記憶されることが可能である。図１３は、オフチップメモリ装置に次のホップアドレスを記憶するための例示的な方法を示す。図１３において、ブロック１３６は、ＤＲＡＭ等のオフチップメモリ装置を表す。メモリ装置１３６内の行１３８乃至１５４は各々、図１１に示された複数の子に対応する次のホップアドレスにてなるセットを記憶する。例えば、参照番号１３８によって示される行０は、根ノード１００の複数の子１０２に対応する次のホップアドレスを記憶する。同様に、参照番号１４０によって示される行１は、ノード１０４の複数の子１０６に係る次のホップアドレスを記憶する。メモリ装置１３６内における残りの行のそれぞれも、次のホップアドレスにてなるセットを記憶する。図１３に示されたデータ構造の各行における次のホップアドレスの位置は、オンチップメモリに記憶された転送テーブルのデータ構造における対応する子の位置に対応している。例えば、図１１において、根ノード１００の４番目の子に係る次のホップアドレスは７である。従って、図１２では、オフチップメモリ内の行１３８の４番目の位置に７が記憶されている。
【００４０】
データ構造の探索．
本発明の一実施形態に係るネットワークアドレスのルックアップは、２つのステージで実行されることが可能である。第１のステージはオンチップのルックアップを含み、ここでは、受信されたパケット内のアドレスに対応する最も長い経路が、オンチップメモリに記憶されたビットパターンから決定される。対応する次のホップアドレスが記憶されるオフチップメモリ内の行及び列アドレスは、オンチップメモリに記憶されたデータ構造から計算される。第２のステージでは、計算されたアドレスに基づいて単一のオフチップのルックアップが実行され、次のホップアドレスが読み込まれる。この実施形態では単一のオフチップのアクセスのみが必要とされ、このことは、ネットワークアドレスのルックアップ時間を従来のルックアップ方法よりも短縮する。これらの２つのステージは、オフチップメモリのために使用されることが可能なＤＲＡＭへの現在のアクセス時間として与えられる６０乃至６５ナノ秒毎に、所定の結果を出すようにパイプライン化されることが可能である。このような方式では、毎秒１５００万回を超えるルックアップがもたらされる。速度をさらにずっと上げるためには、同一の情報を含む複数のＤＲＡＭを並列に使用することができる。
【００４１】
図１４は、本発明の一実施形態に係る、データ構造を探索しかつ次のホップアドレスを決定する際の例示的なステップを示す。図１４を参照すると、ステップＳＴ１で、開始ポインタは、オンチップメモリ内のデータ構造における最初のＸビットパターンを指示するように初期化される。ここで、Ｘはトライの次数である。例えば、図１１に示されたデータ構造では、トライの次数は１６である。従って、開始ポインタは、データ構造における最初の１６ビットパターンを指示することになる。次にステップＳＴ２において、転送されるパケット内の宛先アドレスの最初のｌｏｇ２（Ｘ）ビットが読み込まれる。ステップＳＴ３では、この最初のｌｏｇ２（Ｘ）ビットが、Ｘビットパターンにおける開始ポインタからのオフセットとして使用される。
【００４２】
ステップＳＴ４では、オフセットに位置するビットが０であるか、あるいは１であるかが決定される。このビットが１であれば、ステップＳＴ５で開始ポインタが次のレベルに移動される。ステップＳＴ６では、現在のレベルにおける１のビット数の総和を用いかつＸを乗算することにより、開始ポインタのための新しい位置が計算される。ステップＳＴ７では、開始ポインタが、計算された位置へ移動される。ステップＳＴ２乃至ＳＴ７は、オフセットに位置するビットが０になるまで繰り返される。オフセットによって指示されるステップが０になる場合には、ステップＳＴ８において探索は終了され、オフセットの最後の位置となった１までの１の合計のビット数であって、このオフセットの最後の位置となった１も含む１の合計のビット数が計算される。この１のビット数は、次のホップアドレスを記憶するオフチップメモリ内の行に対応する。転送テーブルのアドレスルックアップにおけるオフセットの最後の位置は、次のホップアドレスを記憶するオフチップメモリ内の列に対応する。ステップＳＴ９では、計算されたオフチップメモリのロケーションに位置した次のホップアドレスが抽出される。ステップＳＴ１０では、次のホップアドレスに対応する出力インタフェースにパケットが送信される。
【００４３】
次に、図１４に示されたステップを使用してデータ構造を探索する２つの例について説明する。第１の例では、４方向トライが探索される。第２の例では、１６方向トライが探索される。図１５Ａ及び１５Ｂは各々、本発明の一実施形態に係る、例示的な４方向トライと、この４方向トライをオンチップメモリに記憶するために使用される転送テーブルのビットパターンとを示す。このデータ構造は、例示的な入力アドレス１００１１１０を使用して探索される。再度図１４を参照すると、ステップＳＴ１において、開始ポインタはデータ構造における最初のＸビットパターンを指示するように初期化される。ここで、Ｘは木の次数である。木の次数は４であることから、開始ポインタは、データ構造における最初の４ビットパターンを、又は１０１０を指示するように初期化される。根ノードに対応する最初の１は無視されることが可能である。図１６は、図１４に示されたステップＳＴ１の実行後における開始ポインタの第１の位置Ｓ１を示す。ステップＳＴ２では、アドレスの最初のｌｏｇ２（４）ビットが読み込まれる。ｌｏｇ２（４）＝２であることから、アドレスの最初の２ビット（１０）が読み込まれる。ステップＳＴ３では、最初のｌｏｇ２Ｘビットが、Ｘビットパターンにおける開始ポインタからのオフセットとして使用される。この例では、オフセットは２である。従って、オフセットは、開始ポインタから２ビットの位置に位置決めされる。図１７は、図１４でのステップＳＴ３の実行後における、開始ポインタ及びオフセットの第１の位置Ｓ１及びＯ１を示す。
【００４４】
ステップＳＴ４では、オフセットに位置するビットが１であるか否かが決定される。図１７に示された例では、オフセットの位置Ｏ１に位置するビットは１である。従って、ステップＳＴ５において、開始ポインタは次のレベルに移動される。次のレベルにおける開始ポインタの新たな位置は、次のレベルにおけるオフセットの位置がスキップされる前の、先行するレベルにおける１のビット数の総和を用い、次いで、Ｘを乗算することによって計算される。第１のレベルにおいて位置Ｏ１より前にある１は１つであることから、次のレベルにおける最初の１×４＝４ビットはスキップされる。図１８は、図１４でのステップＳＴ５乃至ＳＴ７の実行後における開始ポインタの位置Ｓ２を示す。
【００４５】
次に、制御はステップＳＴ２に戻り、このとき、アドレスの次の２ビット又は０１が読み込まれる。次にステップＳＴ３が実行され、オフセットは開始ポインタの現在の位置から１ビットだけ移動される。図１９は、ステップＳＴ３の実行後における、開始ポインタ及びオフセットの位置Ｓ２及びＯ２を示す。図１９からは、オフセットによって指示されるビットが０であるということが分かる。従って、制御はステップＳＴ８へ進み、ここで探索は終了され、１のビット数が計算される。１のビット数は、オフセットの現在の位置より前に存在し、かつ現在の０に至るまでの１を含む、データ構造又はビットパターンにおける１の合計のビット数に等しい。図１５Ａに示されたように、位置Ｏ１より前に存在しかつこの位置Ｏ１の分も含む１の合計のビット数は２である。従って、オフチップメモリの行は２である。ここで、行の番号は０から始まる。オフチップメモリ内の列は、位置Ｏ２によって決定される。Ｏ２は、転送テーブルのデータ構造において、ビットパターンの開始部から１番目の位置（ゼロから始まる）に位置決めされる。従って、次のホップアドレスは、オフチップメモリ内の行３、列１から抽出されることが可能である。
【００４６】
次に、図１乃至図１３で構成されたデータ構造を使用する探索の一例について説明する。図２０は、オンチップメモリ内における、図１２に示されたデータ構造のある例示的な構成を示す。図２０では、データ構造のビットは１６進数形式で表されている。図２０における各行は、オンチップメモリ内の行を表す。また各行は、現在のレベルにおける先行する行からの１のビット数の総和を示す総和の値も記憶する。この例では、各レベルのビットパターンは単一の行に格納されることから、総和のビットはすべて０である。しかしながら、本発明は、レベルが１つよりも多くの行にわたる、より大きいデータ構造を使用して実装されてもよい。そのような例では、総和の値は、与えられたレベルに対応する、先行する行における１のビット数を示す。
【００４７】
この例のオフチップメモリのデータ構造は、図１３に示されている。次のホップアドレスを位置決めする機能を説明するために、例示的な入力アドレス１１２．４８．３２．２４８を使用する。このアドレスに対応する２進数表現は、０１１１  ００００  ００１１  ００００  ００１０  ００００  １１１１  １０００である。この入力アドレスの最初の４ビット（０１１１）は、データ構造のレベル０に対するビットパターンにおけるビット７（ビット０から始まる）になる。図１２に示されたように、このビットは１である。オフセットによって指示されるビットは１であるので、開始ポインタは次のレベルに移動される。次のレベルにおける開始ポインタの位置は、レベル０におけるオフセットの現在の位置より前の１のビット数の総和を用い、木の次数である１６を乗算することによって計算される。図１２に示されたように、レベル０にはビット７より前に２つの１が存在するということが分かる。従って、開始ポインタに対する新たな位置Ｓ２は、レベル１における２×１６＝ビット３２に位置決めされる。
【００４８】
入力アドレスの次の４ビットは、００００である。従って、オフセットの位置Ｏ２は、開始ポインタの位置Ｓ２に対応する。このビットは１に設定されているので、開始ポインタは次のレベルに移動される。レベル１には、この１より前に１は存在しないので、開始ポインタの新たな値はレベル２における最初の０である。この位置は、図１２においてＳ３で示されている。入力アドレスの次の４ビットは、００１１である。従って、オフセットＯ３の新たな位置は、データ構造のレベル２における３番目のビットである。オフセットの現在の位置によって指示される値は１であるので、開始ポインタはレベル３に移動する。レベル２においてＯ３より前に１は存在しないため、レベル３ではビットがスキップされる必要はない。従って、開始ポインタのロケーションＳ４は、図４における０番目のビットに対応する。入力アドレスにおける次の４ビットは、００００である。よってオフセットは０であり、レベル４におけるオフセットの位置Ｏ４は開始ポインタの位置Ｓ４に対応する。こうして探索は終了する。位置Ｏ３に位置した１までの１の合計のビット数であって、位置Ｏ３に位置した１も含む１の合計のビット数は、７である。１の合計のビット数が７であるため、次のホップアドレスは、オフチップメモリの行７に位置している。オフセットの最後の位置Ｏ４は位置０であるので、次のホップアドレスは、オフチップメモリの行７における列０に位置している。図１３を参照すると、行８における位置０に位置した次のホップアドレスは５である。本発明は、オンチップメモリにおいて取得されるロケーションに基づいて、次のホップアドレスの正確な位置が決定されるようにするので、次のホップアドレスを取得するために、ただ１回のオフチップメモリへのアクセスが必要とされる。その結果、ルックアップ時間はより速くなり、また、一定となる見込みが高くなる。
【００４９】
オンチップのデータ構造におけるエントリの挿入及び削除．
エントリのいかなる挿入又は削除も、オンチップメモリにおける異なるパターンをもたらす。従って、エントリの更新は、トライデータ構造の再構成を必要とする。しかしながら、実際には、ほとんどの現実の実装において、ルーティングテーブルの更新は、探索の回数ほど頻繁には発生しない。さらに、効率を改善するために複数の更新がバッチ処理で実行されることも可能である。
【００５０】
例示的なハードウェア実装．
図２１は、本発明に係る方法及びデータ構造を実装することが可能な転送エンジンを含んだルータを示すブロック図である。図２１において、ルータ２００は、複数の回線カード２０２と、スイッチファブリック装置２０４と、処理装置２０６とを含む。各回線カード２０２は、ルーティングテーブル２１０からコピーされた転送テーブル２０８を含む。また各回線カード２０２は、スイッチファブリック装置２０４をスケジューリングしかつ構成するスケジューラ２１２を含む。各回線カードは、転送及びスケジューリングの動作を実行するためにそれ自体のプロセッサを含む。
【００５１】
動作において、ルータ２００の回線カード２０２のうちの１つによってパケットが受信されるとき、次のホップアドレスに対応する出力ポート識別子のアドレスを決定するために、転送テーブル２０８においてルックアップが実行される。いったん出力ポート識別子が決定されれば、パケットは、スイッチファブリック装置を介して、適切な出力ポートに関連付けられた回線カードへ転送される。
【００５２】
本発明に係るデータ構造及びアドレスのルックアップアルゴリズムは、回線カード上で、あるいはルーティングのルックアップを実行する中央処理装置上で実行されることが可能である。回線カード上でルックアップを実行することはルックアップ速度を増大させることから、本発明に係るデータ構造及びルックアップ方法は、好適には回線カード上に実装される。
【００５３】
図２２は、本発明の一実施形態に係る、回線カード上に実装されることが可能な例示的な転送エンジンを示す。図２２において、転送エンジン３００は、トライデータ構造を記憶しかつ当該トライデータ構造におけるルックアップを実行するためのＡＳＩＣ３０２と、次のホップアドレスを記憶するためのオフチップメモリ３０４と、ルーティングテーブル及び転送テーブルを更新するためのＣＰＵ３０６とを含む。ＡＳＩＣ３０２は、ビット抽出器３０８と、マスク生成器３１０と、１のビット数の総和計算機３１２と、オンチップメモリ装置３１４とを含む。ビット抽出器３０８は、入力アドレスからビットを抽出する。マスク生成器３１０は、現在のビットの位置までの１のビット数の総和を計算するために使用されるマスクを生成する。１のビット数の総和生成器３１２は現在の１のビット数の総和を計算し、オフセットの位置を計算するためにこの情報をビット抽出器３０８へフィードバックする。オンチップメモリ３１４は、トライデータ構造を記憶する。
【００５４】
先に論じた１６方向トライの例では、入力アドレスは、４ビットを単位として処理される。従って、ビット抽出器３０８は、入力アドレスから、ビットを４ビットのセグメントで抽出する。ビット抽出器３０８は、この情報をオフセットと共にマスク生成器３１０へ出力する。マスク生成器３１０は、１のビット数の総和を計算するために使用されるマスクを生成する。１のビット数の総和計算機３１２は、このマスクを現在のオンチップメモリの行に受信して、次のオフセットを決定する。いったんオンチップメモリ内の横断的な探索が完了すると、ＡＳＩＣ３０２は、計算された値を使用してオフチップメモリ３０４に対する読み込み要求を生成する。１回のオフチップのアクセス時間で、次のホップアドレスを入手可能である。
【００５５】
ある例では、オンチップメモリの横断的な探索は、有限状態マシン（ＦＳＭ）として実装されることが可能である。図２３は、本発明の一実施形態に係るオンチップのデータ構造を横断的に探索するための例示的な状態を示す状態図である。この説明される例では、有限状態マシン４００は、２つの状態Ｓ０及びＳ１を含む。状態Ｓ０において、転送エンジン３００はアドレスビットを抽出し、現在のオンチップメモリの行を読み込む。次いでこの状態マシンは状態Ｓ１に遷移し、ここで、この状態マシンはマスクを生成して１のビット数の総和を計算する。以下に説明されるある例示的な実装においては、各状態は、完了するまでに８ナノ秒を必要とする。その結果、オンチップメモリにおける各レベルの横断的な探索は、たった１６ナノ秒で行うことが可能である。
【００５６】
ルックアップの処理が実行されているアドレスが、３２ビットのＩＰｖ４アドレスであれば、オンチップメモリには８つの記憶レベルが存在する。従って、オンチップメモリを横断的に探索するには１２８ナノ秒かかるであろう。図２３に示された状態マシンは、スループットを向上させるために展開され（アンロールされ）かつパイプライン化されることが可能である。図２４は、本発明の一実施形態に係る高速なアドレスのルックアップを実装するパイプライン化された一例を示す。図２４において、ブロック５００は、ＳＲＡＭのようなオンチップメモリにおけるレベル１乃至４の横断的な探索を表す。ブロック５０２は、上記オンチップメモリにおけるレベル５乃至８の横断的な探索を表す。最後に、ブロック５０４は、オフチップメモリのルックアップを表す。図２４に示されたように、合計のルックアップ時間は１９２ナノ秒である。ブロック５００及び５０２におけるルックアップ時間は、ブロック５０４で示されたオフチップメモリにおけるルックアップに一致する。
【００５７】
本発明の一実施形態に係る転送エンジンの設計に使用される最も重要なブロックは、マスクを生成するブロックと、１のビット数の総和を計算するブロックである。次に、これらのブロックのために設計された例について詳述する。
【００５８】
マスクの生成．
所定のビットの位置までの１のビット数の総和を計算するには、オンチップメモリ内の行から不要のビットを除去するためにマスクが生成される必要がある。例えば、図１２に示されたオンチップメモリ構造の行０では、ビット７までの１のビット数の総和を計算することが必要とされており、ビット７に続くビットは不要である。従って、不要なビットを除くために生成されなければならない対応するマスクは、１１１１  １１１０  ００００  ００００である。このマスクは、オンチップメモリの行との間でビット毎に論理積演算されることが可能であり、（１１１１  １１１０  ００００  ００００）ＡＮＤ（００１０  １００１  １０００  ００００）＝（００１０  １０００  ００００  ００００）となる。オンチップメモリの行との間でビット毎に論理積演算した後に取得される結果は、１のビット数の総和計算機３１２へ入力され、１のビット数の総和が計算される。
【００５９】
図２５は、図２２に示されたマスク生成器３１０の例示的なハードウェア実装を示す。図２５において、マスク生成器３１０は、復号化器６００とマスク生成器回路６０２とを含む。復号化器６００は、オフセットのビットの位置を復号化する。このビットの位置に依存して、復号化器６００の出力の１つが設定される。復号化器のこの出力はマスク生成器回路６０２へ入力され、この回路はマスクのためのビットパターンを生成する。例えば、オフセットがオンチップメモリの行におけるビット７に位置していれば、復号化器６００の７番目の出力が設定され、マスク生成器回路６０２はマスク１１１１  １１１０  ００００  ００００を生成する。
【００６０】
図２６は、図２５に示されたマスク生成器回路６０２の例示的な内部ブロック図である。入力ｉｎ０乃至ｉｎ１２７は、復号化器６００に接続される。出力０乃至１２７は、１２８ビットのマスクを出力する。入力ｉｎ０乃至ｉｎ１２７は出力０乃至１２７に接続され、ビットの位置に対応するマスクを生成する。例えば、ビット１２６がオフセットの現在の位置であれば、１２６以下の全ての出力ラインはハイレベルになり、出力ライン１２７はローレベルになる。
【００６１】
マスク生成器６０２を通過する際の遅延は、１２８のファンアウトを有するライン１２７における最大の遅延である。図２５に示された例では、復号化器６００は８：１２８ビット復号化器を備える。現在のハードウェアを使用すると、この復号化器は復号化するために約０．７ナノ秒かかる。マスク生成器は、適切なマスクを生成するために約０．６ナノ秒かかる。
【００６２】
１のビット数の総和の計算．
本発明の一実施形態に係る１のビット数の総和の計算は、多数の方法のうちの任意のもので実行されることが可能である。ある簡単な方法は、複数の加算器のバンク（列）を使用するものである。図２７は、１２８ビット幅のオンチップメモリの行に係る１のビット数の総和を計算するために使用されることが可能な、例示的な加算器のバンクを示す。図２７において、１のビット数の総和計算機３１２は、１８個の７：３圧縮器７００と、９個の３ビット加算器７０２と、５個の４ビット加算器７０４と、２個の５ビット加算器７０６と、１個の６ビット加算器７０８と、１個の７ビット加算器７１０とを含む。７：３圧縮器７００は、入力における１のビット数を数え上げるカウンタとして考えることができる。１２８ビット入力は、これらの圧縮器を１８個だけ必要とする。このステージの後に取得される１８個の３ビットの結果値は、図２７に示されたように、次のステージで９個の３ビット加算器７０２を使用して加算されることが可能である。３ビット加算器７０２の出力は、９個の４ビットの結果値である。このプロセスは、単一の８ビットの結果値が出力されるまで、加算器７０４乃至７１０を使用して繰り返される。従って、図２７に示された加算器段の合計の個数は６である。０．１８μ技術の場合、３２ビット加算器は、加算するために約０．６ナノ秒を必要とする。加算するためにかかる時間がより短いより小規模の加算器について同様の組み合わせを仮定すると、総和を計算するために必要な最悪の場合の時間推定値は、４ナノ秒未満になる。全体で、１のビット数の総和を計算する合計時間は、図２３に示された各状態の場合の合計時間である８ナノ秒を大きく下回る。
【００６３】
性能解析．
高速ルックアップアルゴリズムを、「ミシガン大学及びメリットネットワーク：インターネット性能管理及び解析（ＩＰＭＡ）プロジェクト（Michigan University and Merit Network. Internet Performance Management and Analysis (IPMA) Project）」（http://nic.merit.edu/ipma）からのインターネットルーティングテーブル上で実行した。その結果は表４にまとめられており、これは、これらのルーティングテーブルに必要なメモリの量を示している。
【００６４】
【表４】
2004537921.tif 000006
【００６５】
例えば、２３，０００個を超えるエントリを有するメイイースト（MaeEast）のルーティングテーブルは、ビットパターンを記憶するために約２５ｋＢのＳＲＡＭを必要とし、かつ次のホップアドレスを記憶するために約１２ＭＢのＤＲＡＭを必要とする。従来のトライ実装では、約２５ＭＢのＤＲＡＭメモリが必要とされたであろう（表における終わりから２番目のエントリ）。表における最後のエントリは、オンチップＳＲＡＭにおいて達成されることが可能な圧縮の量を示す。すべてのルーティングテーブルで、１個のエントリにつき約１バイトのＳＲＡＭメモリが必要とされた。これは非常に優れたスケーラビリティをもたらすが、このことは、ルーティングテーブルのサイズが増大する場合に重要となる。
【００６６】
圧縮．
達成される転送テーブルの全体的圧縮は、従来の方式より遙かに高い。必要なＳＲＡＭは、現在の製造技術で与えられる単一のチップに格納できるほど十分に小さい（ＤＲＡＭメモリの５００分の１）。この圧縮は、より大きいルーティングテーブルを必要とするか、又は異なる階層用に複数のテーブルを必要とする可能性のあるＩＰｖ６にとって特に有利である。先に述べたように、本発明によれば、データは、転送テーブルにおけるどのエントリに対しても約１バイトに圧縮される。これに比較して、デガーマークほかの「エム．デガーマーク，エイ．ブロドニク，エス．カールソン及びエス．ピンク，“高速ルーティングルックアップ用小型転送テーブル”，ＡＣＭ  ＳＩＧＣＯＭＭ論文集，ｖｏｌ．２７，ｐｐ．３−１４，１９９７年１０月（M. Degermark, A. Brodnik, S. Carlson, S. Pink, "Small Forwarding Tables for Fast Routing Lookups", in Proc. ACM SIGCOMM, vol. 27, pp. 3-14, Oct. 1997）」に記述されている転送テーブルは、１個のエントリにつき５乃至６バイトを使用する。ホワンほかの「エヌ．−エフ．ホワン及びエス．−エム．チャオ，“マルチギガビットスイッチングルータのための新規なＩＰ−ルーティングルックアップ方式とハードウェアアーキテクチャ”，ＩＥＥＥジャーナル・オン・セレクテッドエリアズ・イン・コミュニケーションズ，ｖｏｌ．１７，ｐｐ．１０９３−１１０４，１９９９年６月（N. -F. Huang and S. -M. Zhao, "A Novel IP-Routing Lookup Scheme and Hardware Architecture for Multigigabit Switching Routers", IEEE Journal on Selected Areas in Communications, vol. 17, pp. 1093-1104, June 1999）」に記述されている実装は、さらに大きい転送テーブルを有する。また、この方式を用いた場合の全体的なメモリ消費量（ＳＲＡＭ及びＤＲＡＭ）は、従来の実装において必要とされるもののほぼ半分である。３３３ＭＨｚのプロセッサを有するサン・ウルトラ５（SUN Ultra 5）上では、木を構築するための静的命令カウントは１７０であり、ＳＲＡＭデータ及びＤＲＡＭデータを構築するために必要な合計ＣＰＵ時間は１００ミリ秒のオーダーである。ほとんどの転送テーブルはほぼ１秒に１回の更新しか必要としないので、スクラッチからデータベース全体を構築することなど問題ではない。
【００６７】
ここに記述した例示的な実装におけるメモリアクセスの回数は、ＳＲＡＭアクセスについて８回であり、ＤＲＡＭアクセスについて１回である。ＳＲＡＭアクセスの回数は、ＳＲＡＭを分割して最初の１６ビット上で直接的なルックアップを実行することにより、さらに減少されることが可能である。このとき、アクセス回数は、ＳＲＡＭアクセスについて５回になり、ＤＲＡＭアクセスについて１回になる。複数の待ち行列と複数のＤＲＡＭとを並列に実装することによって、さらに高いスループットを得ることができる。ここに記述した例示的な実装では、６４ナノ秒毎にルックアップを実行可能であり、これは毎秒１５００万回を超えるルックアップをもたらす。従来の実装では、必要とされるメモリアクセスの回数はＤＲＡＭアクセスについて８回であり、ＤＲＡＭアクセスは極めて高価である。例えば、「１２８ＭＢ  ＤＤＲ  ＳＤＲＡＭデータシート」（http://www.micronicom/products/datasheets/ddrsdramds.html）によれば、ＤＲＡＭアクセスのコストはランダムな読み出し／書き込みにつき６０ナノ秒である。従って、多数のＤＲＡＭアクセスを必要とする従来の実装は本発明よりかなり遅い。
【００６８】
本発明の実施形態に使用されるメモリの量は、「ビー．ランプソン及びジー．ブイ．ブイ．シュリーニバサン，“マルチウェイ及びマルチカラム探索を用いたＩＰルックアップ”，ＩＥＥＥ  ＩＮＦＯＣＯＭ’９８論文集，ｖｏｌ．３，（カリフォルニア州サンフランシスコ），ｐｐ．１２４８−１２５６，１９９８年（B. Lampson and G. V. V. Srinivasan, "IP Lookup using Multiway and Multicolumn search", in Proc. IEEE INFOCOM'98, vol. 3, (San Francisco, CA), pp. 1248-1256, 1998）」に記述されているような、３乃至４ＭＢのパトリシア（Patricia）の２進数方式及び基本的な２進数方式より多い。この増大されたメモリ使用量は、本発明のいくつかの実施形態にはトライの深さを減らすために１６方向トライを使用するものがあることと、トライの完成は余分なメモリを占有することとに起因する。深さを減らすことに加えて、１６方向トライを使用することの１つの優位点は、より小さいＳＲＡＭメモリが必要とされるということにある。図１３から分かるように、ＤＲＡＭデータにはより多くの冗長性があるが、ＤＲＡＭアクセス回数を減らすために余分なオフチップＤＲＡＭメモリを使用することは、よりよい代案である。
【００６９】
設計においては、５１２又は１２０４ビット幅のＳＲＡＭのような、より広い幅を有するＳＲＡＭを使用することができる。このことはシステムの性能を変えるものではないが、転送エンジンにおいて使用されるメモリのオーバーヘッドを減少させるであろう。現在の実装では、ＳＲＡＭの行における１２８ビットのデータ毎に１のビット数の総和の値を保持するために２０ビットが使用される。この設計におけるメモリのオーバーヘッドは１５乃至１６％増しとなる。５１２ビット幅のＳＲＡＭを使用することによって、メモリのオーバーヘッドを４％未満に減らすことができる。メモリアクセスの回数は同じままである。より広い幅を有するＳＲＡＭを設計において使用すると、１のビット数の総和を計算するための追加のハードウェアが必要になるが、タイミング上の拘束条件は、現在の技術を用いることでなお満たされるであろう。
【００７０】
結論．
ハードウェアに容易に実装されるアドレスのルックアップ方式について説明されている。本発明は、多くの時間を必要とするオフチップＤＲＡＭアクセスを制限する。ある実装では、１回のルックアップに必要なＤＲＡＭアクセスは１回だけである。これは、経路に関連した追加情報を含む小型のオンチップＳＲＡＭを有することによって達成される。必要なＳＲＡＭの量は非常に少なく、ＤＲＡＭメモリの約５００倍の圧縮を達成することができる。実際のルーティングテーブルでは、テーブル内の１個のエントリにつき１バイトのＳＲＡＭメモリが必要である。ＳＲＡＭ及びＤＲＡＭの動作は、６４ナノ秒毎にルックアップを行って結果的に毎秒１５００万回を超えるルックアップレートが可能となるように、パイプライン化される。
【００７１】
遅延の計算及び仮定．
マスク生成器回路に対する前述の遅延を決定するため、入力上の最大負荷（ＣＬ）は、１２８＊Ｃｉｎとなる。ここで、Ｃｉｎは受信機の入力キャパシタンスである。負荷を駆動するためには、各ステージが先行するステージよりファクタ（ｕ）だけそれぞれ大きい、複数ステージのバッファが必要である。バッファ内のステージ数はＮであり、ここで次式が成り立つ。
【００７２】
［数１］
ＣＬ＝ｘＣｉｎ＝ｕｎＣｉｎ
【００７３】
最適なステージ比はｅ（２．７１８２）に等しいということを示すことができる。（ジェイ．エム．ラバイ，“デジタル集積回路：設計見通し”，第８章，プレンティスホール・インコーポレイテッド，１９９６年（J. M. Rabaey, Digital Integrated Circuits: A Design Perspective, ch. 8, Prentice-Hall Inc., 1996））バッファの設計においてステージ比を３であるとすると、合計の遅延は次式によって与えられる。
【００７４】
［数２］
Ｔｐ＝Ｎ＊μ＊ｔｐ０
【００７５】
ここで、ｔｐ０は、最小のサイズのトランジスタを通過するときの遅延である。ｔｐ０は、０．２５μＣＭＯＳ技術ではほぼ４０ピコ秒であり、これにより、マスク生成器に対する合計の遅延は０．６ナノ秒になる。
【００７６】
本発明の様々な詳細は、本発明の範囲を逸脱することなく変更され得ることは理解されるであろう。さらに、これまでの説明は単に例示を目的としたものであって限定するためのものではなく、本発明は請求の範囲によって画成される。
【図面の簡単な説明】
【００７７】
【図１】葉ノードがデフォルトの次のホップアドレスを指示しているトライデータ構造を表す図である。
【図２】図１に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図３】図２に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図４】図３に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図５】図４に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図６】図５に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図７】図６に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図８】図７に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図９】図８に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図１０】図９に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図１１】図１０に示されたトライデータ構造へ次のホップアドレスが追加されているトライデータ構造を表す図である。
【図１２】本発明の一実施形態に係る、オンチップメモリに転送テーブルのデータ構造を記憶するためのビットパターンを示す図である。
【図１３】本発明の一実施形態に係る、オフチップメモリ装置における次のホップアドレスの記憶ロケーションを示すメモリの図である。
【図１４】本発明の一実施形態に係る、トライデータ構造において次のホップアドレスを決定するための例示的なステップを示すフローチャートである。
【図１５Ａ】次のホップアドレスを記憶するトライデータ構造を示すデータ構造図である。
【図１５Ｂ】本発明の一実施形態に係る、アドレスのルックアップを実行する際に図１５Ａのデータ構造において取得されるロケーションを示すビットパターンである。
【図１６】本発明の一実施形態に係る、ルックアップアルゴリズムの１つのステップの後にネットワークアドレスのルックアップを実行する際の開始ポインタの位置を示すビットパターンである。
【図１７】本発明の一実施形態に係る、ネットワークアドレスのルックアップを実行する際における開始ポインタ及びオフセットの位置を示すビットパターンである。
【図１８】本発明の一実施形態に係る、ネットワークアドレスのルックアップを実行する際における開始ポインタ及びオフセットの位置と開始ポインタの新しい位置とを示すビットパターンである。
【図１９】本発明の一実施形態に係る、ネットワークアドレスのルックアップの実行における開始ポインタ及びオフセットの位置と、開始ポインタの新しい位置と、オフセットの新しい位置とを示すビットパターンである。
【図２０】本発明の一実施形態に係る、１６進数形式で記憶された図１２のデータ構造を示すメモリの図である。
【図２１】本発明の実施形態に係る高速パケット転送のための方法及びシステムを動作させることのできるルータを示すブロック図である。
【図２２】本発明の一実施形態に係る高速パケット転送エンジンのブロック図である。
【図２３】本発明の一実施形態に係る、データ構造において取得されたロケーションに基づいて次のホップアドレスを決定する際の例示的な状態を示す状態図である。
【図２４】本発明の一実施形態に係る、次のホップアドレスを決定するための例示的なステップと最悪ケースの時間推定値とを示すフローチャートである。
【図２５】図２２に示されたマスク生成モジュール３１２のブロック図である。
【図２６】図２５に示されたマスク生成器６０２の回路図である。
【図２７】図２５に示された１のビット数の総和生成器３１４を示すブロック図である。
【符号の説明】
【００７８】
１００…根ノード、
１０２，１０６，１１４，１１８，１２２，１２６，１３０，１３４…子、
１０４，１０８，１１２，１１６，１２０，１２４，１２８，１３２…ノード、
１３６…メモリ装置、
１３８，１４０，１４２，１４４，１４６，１４８，１５０，１５２，１５４…行、
２００…ルータ、
２０２…各回線カード、
２０４…スイッチファブリック装置、
２０６…処理装置、
２０８…転送テーブル、
２１０…ルーティングテーブル、
２１２…スケジューラ、
３００…転送エンジン、
３０２…ＡＳＩＣ、
３０４…オフチップメモリ、
３０６…ＣＰＵ、
３０８…ビット抽出器、
３１０…マスク生成器、
３１２…１のビット数の総和計算機、
３１４…オンチップメモリ装置、
６００…復号化器、
６０２…マスク生成器回路、
７００…７：３圧縮器、
７０２…３ビット加算器、
７０４…４ビット加算器、
７０６…５ビット加算器、
７０８…６ビット加算器、
７１０…７ビット加算器、
Ｏ１，Ｏ２，Ｏ３，Ｏ４…オフセットの位置、
Ｓ１，Ｓ２，Ｓ３，Ｓ４…開始ポインタの位置。
【図１２】
2004537921.tif 000007
【図１４】
2004537921.tif 000008
【図２０】
2004537921.tif 000009
【図２１】
2004537921.tif 000010
【図２２】
2004537921.tif 000011
【図２３】
2004537921.tif 000012
【図２４】
2004537921.tif 000013
【図２５】
2004537921.tif 000014
【図２７】
2004537921.tif 000015
【国際公開パンフレット】
2004537921.tif 000016
2004537921.tif 000017
2004537921.tif 000018
2004537921.tif 000019
2004537921.tif 000020
2004537921.tif 000021
2004537921.tif 000022
2004537921.tif 000023
2004537921.tif 000024
2004537921.tif 000025
2004537921.tif 000026
2004537921.tif 000027
2004537921.tif 000028
2004537921.tif 000029
2004537921.tif 000030
2004537921.tif 000031
2004537921.tif 000032
2004537921.tif 000033
2004537921.tif 000034
2004537921.tif 000035
2004537921.tif 000036
2004537921.tif 000037
2004537921.tif 000038
2004537921.tif 000039
2004537921.tif 000040
2004537921.tif 000041
2004537921.tif 000042
2004537921.tif 000043
2004537921.tif 000044
2004537921.tif 000045
2004537921.tif 000046
2004537921.tif 000047
2004537921.tif 000048
2004537921.tif 000049
2004537921.tif 000050
2004537921.tif 000051
2004537921.tif 000052
2004537921.tif 000053
2004537921.tif 000054
2004537921.tif 000055
2004537921.tif 000056
2004537921.tif 000057
2004537921.tif 000058
2004537921.tif 000059
2004537921.tif 000060
2004537921.tif 000061
2004537921.tif 000062
2004537921.tif 000063
2004537921.tif 000064
2004537921.tif 000065
2004537921.tif 000066
2004537921.tif 000067
2004537921.tif 000068
2004537921.tif 000069
2004537921.tif 000070
2004537921.tif 000071
2004537921.tif 000072
【国際調査報告】
2004537921.tif 000073