(57)【特許請求の範囲】
【請求項１】
ルートルックアップエンジンの動作方法であって、
（ａ）タイプフラグ値、インダイレクトフラグ値、オーダデータ及びＲＬＥルートデータを含むリクエストブロックデータを含むルートルックアップリクエストを受取るステップ；
（ｂ）現オーダ値を「オーダデータ」にセットするステップ；
（ｃ）タイプフラグを「葉」か否かについて評価するステップ；
（ｄ）タイプフラグが「葉」を示していない場合にＲＬＥ  ＤＲＡＭアドレスを増分し、タイプフラグが「葉」である場合にステップ（ｇ）へ直接進むステップ；
（ｄ１）増分された該ＲＬＥ  ＤＲＡＭアドレスに対応する次のブロックデータを読み取るステップであって、該次のブロックデータはタイプフラグ、インダイレクトフラグ、オーダデータ及びＲＬＥルートデータを含む、ステップ；
（ｄ２）該次のブロックデータの該オーダデータに従って、該現オーダ値を増分するステップ；
（ｅ）増分された該現オーダ値を評価するステップ；
（ｅ１）該増分された現オーダ値が６４を越えている場合にステップ（ｉ）へ進むステップ；
（ｅ２）該増分された現オーダ値が３２を越えている場合にＬビットをセットするステップ；
（ｆ）ステップ（ｃ）に戻るステップ；
（ｇ）該インダイレクトフラグを評価するステップ；
（ｇ１）該インダイレクトフラグが許可でない場合にステップ（ｊ）へ直接進むステップ；
（ｇ２）該インダイレクトフラグが許可の場合に該ＲＬＥ  ＤＲＡＭアドレスを該ＲＬＥルートデータに等しくセットするステップ；
（ｇ３）該ＲＬＥ  ＤＲＡＭアドレスに対応する次のブロックデータを読み取るステップであって、該次のブロックデータはタイプフラグ、インダイレクトフラグ、オーダデータ及びＲＬＥルートデータを含む、ステップ；
（ｈ）該インダイレクトフラグ及び該タイプフラグを評価するステップ；
（ｈ１）該インダイレクトフラグが許可である場合、又は該タイプフラグが「ノード」を示している場合にステップ（ｉ）へ直接進むステップ；
（ｈ２）該インダイレクトフラグが許可でない場合、かつ該タイプフラグが「葉」を示している場合にステップ（ｊ）へ直接進むステップ；
（ｉ）該方法を終了しエラーを報告するステップ；
（ｊ）ＲＬＥルートデータに対応するルートテーブルデータを記憶して該方法を終了するステップ
からなる方法。
【請求項２】
ルートルックアップエンジンの動作方法であって、
ルートルックアップリクエストを受取るステップ、
ルートルックアップを実行するステップであって、
該ルックアップが該リクエストに対する最初のルックアップであるかの判断を行うステップ、
該ルックアップが該リクエストに対する最初のルックアップであるとき、該リクエストに対し現ブロックデータを使用し、該ルックアップが該リクエストに対して最初のルックアップでないとき、前回ブロックデータを使用するステップ、
該ブロックデータが「葉」を示しているかどうかの判断を行うステップであって、
該ブロックデータが「葉」を示している時、間接ビットが該ブロックデータに設定されているかどうかを判断し、該間接ビットが設定がされているとき、該ブロックデータからのルートテーブルルックアップエンジンルートから成るルートテーブルルックアップアドレスを供給し、該ルックアップテーブルから読取りを行い、該読取りは新規ブロックデータを供給し、該間接ビットが１に等しくなく、かつタイプビットがノードに等しくない場合に、結果を保存するこれらステップを実行するステップ；及び
該間接ビットが設定されていないとき、該結果を保存するステップを実行するステップ
からなる方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
データ転送においてルートルックアップを実行するルートルックアップエンジンに関する。
【０００２】
【従来の技術】
ルータのようなネットワークデバイスは処理動作のその一部としてルートルックアップを実行しなくてはならない。ルートルックアップは、次にパケットがどこに送られるべきかを判断するために、ルータにより受け取られる各パケットごとに必要となる。受信パケットは３２ビット長の宛先アドレスを含む。宛先アドレスはパケットの転送がなされる固有のアドレスを識別する。ルートルックアップでは受信パケットの宛先アドレスを使用して、ルーティングテーブルにおける次ホップアドレスと出口ポートを識別する。宛先アドレスが３２ビット長である場合、宛先可能数は１０憶以上となる。インターネットプロトコル（ＩＰ）アドレスはネットワーク番号とホスト番号から構成されている。ネットワーク番号は可変長であり、固有のネットワークを識別する。ネットワーク番号に連結しているのがホスト番号であり、ホスト番号は特定のネットワーク内の固有のホストシステムを識別する。受信アドレスのネットワーク番号部分はルーティングテーブルにおける複数エントリーとマッチングが行われる。この最適マッチは、アドレスの最初の部分のビットが最大数マッチングするものである。
【０００３】
【発明が解決しようとする課題】
しかしながら、この従来のルートルックアップにおいてマッチングを実行するために使用される従来技術による方法は複雑、かつ時間がかかる。よって、ルートルックアップを迅速、かつ効果的に実行するルートルックアップエンジンが必要とされる。
【０００４】
【課題を解決するための手段】
上述した問題を解決するため、本発明は次ホップインデックスを判断するルートルックアップエンジンを開示する。ルートルックアップエンジンはルックアップキーを受け取り、プレフィックスエキスパンションと可変ストライド（ｓｔｒｉｄｅ）ツリーキャプチャによりマルチビット樹木探索を実行する。ルートルックアップエンジンが返送するデータは、次ホップ情報およびステータスフラグより構成される。ルートルックアップエンジンはコンパクトでフィールド再利用可能なデータ構造を使用する。ルートルックアップエンジンでは仮想プライベートネットワーク上にてユニキャストＩＰアドレスルックアップおよびマルチキャストＩＰアドレスルックアップの両方を実行する。ルートルックアップエンジンは別々のインデックスメモリーと転送メモリーを使用する。ルートルックアップエンジンのサーチタイムの上界はルートテーブルサイズに関係なく決定される。
【０００５】
【発明の実施の形態】
ルートルックアップエンジンを開示する。ルートルックアップエンジンは多数アプリケーションにおいて使用が可能である。望ましい実施形態においては、ルートルックアップエンジンは非同期トランスファモード（ＡＴＭ）スイッチのインターネットプロトコル（ＩＰ）ルーティングサブシステムの一部である。ＡＴＭスイッチのルーティングサブシステムは迅速かつ効果的なルートルックアップメカニズムを提供する。図１はＡＴＭスイッチのトップレベルブロック図である。ＡＴＭスイッチは入／出力アダプタ５２を備えている。この入／出力アダプタはインターフェースオプティクス、同期光ネットワーク（ＳＯＮＥＴ）フレーマ、およびハイレベルデータリンク制御手順（ＨＤＬＣ）コントローラを備えている。ＡＴＭスイッチはまた、入／出力モジュール１０を備えている。入／出力モジュールは複数の転送エンジン２０を備えている。さらに入／出力モジュールはタイミング制御ユニット３０、ＤＣ電流変換／分配ユニット４０、スイッチファブリックインターフェース５０、および制御プロセッサ６０を備えている。入／出力モジュールのタイミング制御ユニット３０はローカルタイミングのシステムリファレンスを物理層に提供する。入／出力モジュールのＤＣ電流変換／分配ユニット４０は直流直流コンバータより成る。パックプレインより可能な４８ボルトはモジュールに必要な電圧に変換される。
【０００６】
スイッチファブリックインターフェース５０は、スイッチファブリック経由で各転送エンジンとスイッチにおける他のカードとを連結する。データはＡＴＭセル形式で搬送される。スイッチファブリック過密情報もまたファブリックから返送され、転送エンジン用に再フォーマット／サマライズされる。
【０００７】
制御プロセッサ６０は、バックグラウンド汎用プロセッサとしてペンティアムマイクロプロセッサにより構成される。転送エンジン２０については以下に詳細に記載する。
【０００８】
図２は入／出力モジュールの単一転送エンジン２０のブロック図である。転送エンジン２０は、制御メモリ１６０およびパケットメモリ１７０と連動するインバウンドセグメンテーション／再アセンブリ（ＳＡＲ）デバイス１５０、制御メモリ１９０およびパケットメモリ２００と連動するアウトバウンドセグメンテーション／再アセンブリ（ＳＡＲ）１８０、パケットヘッダーディストリビュータ２１０、パケット分類エンジン１１０、ルートルックアップエンジン１００、転送プロセッサ１３０、転送プロセッサと連動するキャッシュ１４０、およびＤＲＡＭ／ＳＲＡＭ１２０から構成されている。
【０００９】
転送エンジン２０はインバウンドパケットおよびアウトバウンドパケットを処理する。インバウンドパケットに関して、パケットはインバウンドＳＡＲ１５０にトランスファされ、そこでパケットはパケットメモリ１７０に保存される。インバウンドＳＡＲ１５０は最高サービス品質パケットをパケットヘッダーディストリビュータ２１０に送る。転送プロセッサ１３０はパケットヘッダーディストリビュータのステータスチェックを行い、インバウンドパケットの受取りがいつ可能になるかを判断する。転送プロセッサ１３０は、パケットヘッダーディストリビュータＦＩＦＯからのプライオリティの最も高いヘッダーを検索し、これをキャッシュ１４０に保存する。転送プロセッサ１３０はヘッダーを処理し、ルートルックアップエンジン１００とパケット分類エンジン１１０の両方に要求されたヘッダーエレメントを同時に送信する。そこで、それらはイグレス（ｅｇｒｅｓｓ）キューに保存される。ルートルックアップエンジン１００はパブリックあるいは仮想プライベートネットワークユニキャストルックアップを実行し、必要な場合、次のマルチキャストルックアップを実行する。一方で、パケット分類エンジン１１０はヘッダーエレメントに対してフィルタチェックを実行する。
【００１０】
ルートルックアップエンジン１００とパケット分類エンジン１１０のパケットヘッダーディストリビュータ２１０へのステータスパスが完了すると、転送プロセッサ１３０によりポーリングされるイグレスキューに結果を保存する。ルートルックアップエンジン１００の動作については詳細を後述する。転送プロセッサ１３０はポーリングを行い、次に、新規ヘッダーが公式化されるルートルックアップと分類結果を得る。次に伝送情報に加えて新規ヘッダーがパケットヘッダーディストリビュータ２１０に書込まれる。インバウンドＳＡＲ１５０は新規にフォーマット化されたヘッダーを検索し、それをパケットの残りとともにパケットメモリ１７０に返送して、そして、セグメント化されスイッチファブリックに伝送されるパケットをスケジュールする。
【００１１】
転送エンジン２０はアウトバウンドパケットを次のように処理する。ＡＴＭセルはスイッチパケットからアウトバウンドＳＡＲ１８０にトランスファされ、そこで全体パケットが再アセンブリされ、パケットメモリ２００に保存される。アウトバウンドＳＡＲ１８０は最高サービス品質パケットのヘッダーをパケットヘッダーディストリビュータ２１０に送信する。転送プロセッサ１３０はパケットヘッダーディストリビュータ２１０のステータスチェックを行い、アウトバウンドパケットの受け取りが可能であることを判断する。転送プロセッサ１３０はパケットヘッダーディストリビュータＦＩＦＯからプライオリティの最も高いヘッダーを検索して、それをそれらのキャッシュに保存する。転送プロセッサ１３０はヘッダーを処理し、ルートルックアップエンジン１００とパケット分類エンジン１１０の両方に要求されたヘッダーエレメントを同時に送信する。そこでそれらはイグレスキューに保存される。ルートルックアップエンジン１００はパブリックあるいは仮想プライベートネットワークユニキャストルックアップを実行し、必要な場合、次のマルチキャストルックアップを実行する。一方で、パケット分類エンジン１１０はヘッダーエレメントに対してフィルタチェックを行う。
【００１２】
ルートルックアップエンジン１００とパケット分類エンジン１１０のパケットヘッダーディストリビュータ２１０へのステータスパスが完了すると、転送プロセッサ１３０によりポーリングが行われるイグレスキューとなる。転送プロセッサ１３０はポーリングを行い、次に、新規ヘッダーが公式化されるルートルックアップと分類結果を得る。次に伝送情報に加えて新規ヘッダーがパケットヘッダーディストリビュータ２１０に書込まれる。アウトバウンドＳＡＲ１８０は新規にフォーマット化されたヘッダーを検索して、パケットの残りとともにパケットメモリ２００にそれを返送し、物理フレームインターフェースに伝送されるパケットをスケジュールする。
【００１３】
図３は転送エンジン２０のルートルックアップエンジン１００のブロック図である。ルートルックアップエンジンは転送プロセッサ１３０の次ホップインデックスを判断するハードウェアサーチエンジンである。ルートルックアップエンジン１００は、転送プロセッサインターフェース６５、入／出力ＦＩＦＯ４０および入／出力ＦＩＦＯ５０、ルックアップコントローラ２０、ルックアップテーブルＤＲＡＭ３０、および制御プロセッサインターフェース７０とにより構成される。転送プロセッサインターフェース６５はサーチエンジンのキーをロードするために使用される。キーは、物理ポート／論理ポートに固有のツリー根のアドレス／仮想プライベートネットワーク  ＩＤ、ＩＰ宛先アドレス、ＩＰソースアドレス、ツリーの第一レベルのオーダ、および、シーケンスエラーチェック用にヘッダーといっしょに返送されるオプショナルリクエストＩＤとにより構成される。制御プロセッサインターフェース７０はルックアップ間のテーブル更新に使用される。
【００１４】
その動作において、転送プロセッサは、ルートルックアップエンジンとパケット分類エンジン両方の共通アドレスに１つあるいはそれ以上のキャッシュラインを同時に書込む。転送プロセッサインターフェース６５はルートルックアップエンジンとパケット分類エンジン両方からの結果を同時に検索するために使用される。これらは、パケット分類エンジンより供給される結果部分とルートルックアップエンジンより供給される結果部分と共に同一アドレスから同時にリポートする。
【００１５】
ルートルックアップエンジンはＦＩＦＯもしくは他のインターフェースを備え、スループットを最大限にすることを可能にする。入／出力ＦＩＦＯは、転送プロセッサからの複数ルックアップリクエストを所定時間で明確にする。これらのパケットが異なるルックアップ時間を有する場合、ＦＩＦＯはいくつかのヘッダーバーストをイン／アウトさせることによりルックアップレートを平滑にする。ルートルックアップエンジンは仮想プライベートネットワーク（ＶＰＮ）上でユニキャストＩＰアドレスルックアップおよびマルチキャストＩＰアドレスルックアップの両方を実行する。各仮想プライベートネットワークは、その仮想プライベートネットワークに特定のテーブル根に対するポインタとして使用される。多重仮想プライベートネットワークはソフトウェアの間接処理により同一ルートテーブルをマップする。
【００１６】
ＩＰパケットを転送するために、パワープロセッサコントローラはルートルックアップリクエストをパケットヘッダディストリビュータに提示する。ルートルックアップエンジンのハードウェア可変ストライドツリーテーブルは、ルートルックアップエンジンからの回答と共に含まれる結果インデックスによりリクエストを解決するために使用される。インデックスがパワープロセッサコントローラに対し使用可能となると、これらは転送テーブルからの転送情報への直接アクセスのために使用される。
【００１７】
ルートルクアップからの結果は、次ホップインデックス、有効ルックアップ／ルート未発見ビット、ステータスフラグ、マルチキャストルックアップ実行ビット、統計情報、および、シーケンスエラーチェックのためのオプショナルリクエストＩＤにより構成される。
【００１８】
パケットがマルチキャストパケットである場合、ルートルックアップエンジンサーチはまず最初にＩＰ宛先アドレスにおいて実行され、次にＩＰソースアドレスにおいて実行される。サーチにはプレフィックスエキスパンションおよびキャプチャによるマルチビット樹木探索（ multi-bit tree search ）を用いる。次ホップインデックスが発見されたかあるいはキー終了に達した場合にサーチは終了となる。この試みにおいてＩＰソースアドレスの終了時にＩＰヘッダーサーチの６４ビット超を継続させると、ハードウェアエラーチェックはサーチを終了させ、エラーリポートを行う。ルーティングサブシステムのルートルックアップエンジンマネジャーはルートルックアップエンジンメモリ管理を行う。ルートルックアップエンジンメモリは、デフォルト仮想プライベートネットワーク（ＶＰＮ）、ＶＰＮ０を含む、構成された仮想プライベートネットワーク（ＶＰＮ）各々に対するハードウェア可変ストライドツリー（ＶＳＴ）ルートテーブルを保存するために使用される。各ハードウェアＶＳＴは最小の近接メモリスペースが保証されている。残りのメモリスペースはメモリブロックのフリープールとして利用可能である。ルートがＶＳＴテーブルに追加されると、また、これから削除されると、メモリブロックがこれらメモリプールから割当てされ、そして、これらメモリプールに解除される。ルーティングサブシステムはメモリの断片化を最小に保つよう管理する。
【００１９】
ルーティングサブシステムは、パワープロセッサコントローラのメモリ上の転送データベースレジデントとルートルックアップエンジンのメモリー上のハードウェアＶＳＴテーブルレジデントとを確実に同期させておく。同様に、カーネルプロセッサのメモリ上のソフトウェアＶＳＴテーブルレジデントはルートルックアップエンジンのハードウェアＶＳＴテーブルと同期を保たなくてはならない。
【００２０】
ルートルックアップエンジンはローカルメモリに備わったＶＳＴベースルートルックアップテーブルを含む。これらのＶＳＴテーブルは１つの特定ルートに一致する。ハードウェアＶＳＴテーブルの各エントリは、パワープロセッサコントローラメモリ上の転送テーブルレジデント内における相当転送エントリに対するインデックスを有する。
【００２１】
各ＶＰＮに関して、シングルソフトウェアＶＳＴはカーナルプロセッサのメモリにて維持され、相当のハードウェアＶＳＴはルートルックアップエンジンメモリにて維持される。ＶＳＴルートテーブルは高レートにて最適マッチングプレフィックスをサポートするＶＳＴデータ構造にて構築される。ＶＳＴテーブルはサーチキーを別個のビットストリングに分割することで構築される。サーチキーはＩＰアドレスである。ＶＳＴレベル数はルートルックアップ中の最大メモリアクセス数を特定する。このように、ルックアップを完了する時間はバウンドされるが決定性を持つものではない。各ＶＳＴレベル長はストライド長として知られ、その区分を表すノード内のエレメント数を判断する。
【００２２】
ハードウェアＶＳＴデータ構造は次のようになる。
エレメント
【表１】
0003926558.tif 000002
タイプ    ：  ０＝葉，１＝ノード
オーダ    ：  ノードについてlog2、葉についてプレフィックス長
ポインタ  ：  次ノードのベースアドレスに対するポインタ（無効の場合ゼロ、または転送エントリに対するインデックス（無効の場合０ｘＦＦＦＦＦＦ）
ノード
【表２】
0003926558.tif 000003
【００２３】
ハードウェアルートサーチデータ構造はノードにより構成され、その各々はエレメントのアレーである。ノードにおけるエレメント数はノードオーダにより決定する。ここでオーダは、このノードの評価に使用されるサーチキー（宛先ＩＰアドレス）のビット数である。各エレメントは、葉（ leaf ）か他のノードの根（ root ）のどちらかとして次ノードを指示するタイプインジケータを有する。現在のノードのタイプが「ノード」である場合、オーダは次ノードのオーダを示す。また、現在のノードのタイプが「葉」である場合、オーダは葉のプレフィックス長を示す。ポインタフィールドはエレメントタイプにより決定する。タイプが「葉」である場合、ポインタはフォアグラウンドの転送テーブルのインデックスであり、宛先アドレス／マスクペアの転送エントリを識別する。タイプが「ノード」である場合、ポインタは評価される次ノードのアドレスを識別するサーチスペースのポインタである。次のテーブルはオーダの意味と異なるタイプのポインタフィールドを示したものである。
【表３】
0003926558.tif 000004
【表４】
0003926558.tif 000005
Ｐ：  パリティビット。奇数パリティはハードウェアによりオプショナルにＳＤＲＡＭに書込まれ、ＳＤＲＡＭより読取られる。
｛１ビット｝
Ｔ：  タイプビット  ０＝ノード,１＝葉｛１ビット｝
Ｉ：  間接ビット。１＝間接,０＝ダイレクト
｛１ビット｝
オーダ  ：  １から３２に相当する次レベルのオーダ｛５ビット｝
RLE-Root/Flag.NHP：    （ルートルックアップエンジン（ＲＬＥ）根／フラグ．次ホップポインタ）:Ｔビットによってこのデータフィールドに対し２コンテキストが存在する。ノードの場合、次ノードポインタ｛２４ビット｝、または葉の場合、ＲＬＥ次ホップポインタ｛１６ビット｝にプリペンドされたＲＬＥフラグ（８ビット）。
【００２４】
ルートルックアップエンジン根はサーチ開始に使用される。ルートルックアップエンジン根は根ポインタとツリーの第一レベルのオーダを含む。第一ルックアップアドレスは根ポインタ、プラス、インデックスにより構成される。インデックスは宛先アドレスの上位ビットから導出される。ビット数は可変であり、第一レベルのオーダによって示される。このアドレスはテーブルからのエレメントをルックアップするために使用される。このエレメントが葉である場合、サーチは完了し、エレメントはパケット分類エンジン／ルートルックアップエンジンマネジャーにもどされる。エレメントがノードである場合、ポインタは次のルックアップに使用される。
【００２５】
次ルックアップのアドレスは上記のポインタ、プラス、インデックスから成る。インデックスは宛先アドレスからの「次」ビットから導出される。正確なビットは、最終レベルのオーダ、プラス、このレベルのオーダから導出される。ゆえに、インデックスに使用される宛先アドレスの相当ビットを知る目的で、各レベルのオーダがトラックされなくてはならない。
【００２６】
このアドレスはテーブルのエレメントをルックアップするために再度使用される。このエレメントが葉である場合、サーチは完了し、このエレメントはパケット分類エンジン／ルートルックアップエンジンマネジャーにもどされる。このエレメントがノードである場合、ポインタは次のルックアップに使用される。これは葉が見つけ出されるまで繰り返される。アクセス数やレベル数が最大数を超過した場合には、代わりにエラーが返送される。
【００２７】
ある構成においてはルートルックアップに間接方法を有することが望ましい。これは間接ビットを用い達成される。間接ビットが設定されると、葉フラグは無視され、オーダフィールドは使用されず、そのインデックスロケーションから返送されたルート結果により、現２４ビットポインタがダイレクトテーブルインデックスとして使用される。間接ファンクションはデプスをゼロに設定することにより呼び出すことも可能である。
【００２８】
図４は、本発明によりルートルックアップを実行する方法３００のフローチャートである。ルックアップはステップ３１０にてリクエストを受け取ることから開始する。ステップ３２０において、これがそのリクエストに対する最初のルックアップであるかどうかの判断が行われる。これがリクエストに対する最初のルックアップでない場合、ステップ３３０に示すように、ＴＹＰＥ、ＩＮＤＩＲＥＣＴ、ＯＲＤＥＲ、およびＲＬＥ  ＲＯＯＴの前回値が使用される。これがリクエストに対する最初のルックアップである場合、ＴＹＰＥ、ＩＮＤＩＲＥＣＴ、ＯＲＤＥＲ、およびＲＬＥ  ＲＯＯＴがリクエストブロックデータから取り出される。
【００２９】
ステップ３５０において、ＴＹＰＥビットが評価される。タイプが「葉」でない場合、ステップ４２０において、ＤＲＡＭアドレスは、宛先アドレスとソースアドレスが繋げられたＲＬＥ  ＲＯＯＴ＋０に設定される。
【００３０】
次にステップ４３０において、ＤＲＡＭアドレスからの読取りが実行され、ＴＹＰＥ、ＩＮＤＩＲＥＣＴ、ＯＲＤＥＲ、およびＲＬＥ  ＲＯＯＴの新規値が得られる。ステップ４４０において、現在のオーダが、現オーダ、プラス、オーダに設定される。
【００３１】
ステップ４５０において、現在のオーダが６４よりも小さいかあるいは等しいかの判断がなされる。そうでない場合、エラーコンディションが示されてサーチは終了する。現在のオーダが６４よりも小さいかあるいは等しい場合には、現在のオーダが３２より大きいかどうかがステップ４７０にて判断される。もしそうでない場合、ステップ３２０より開始する他のルックアップが実行される。現在のオーダが３２により大きい場合、ステップ４８０が実行され、マルチキャストオペレーションを示すＬビットが設定される。ステップ４８０の後、ステップ３２０より開始する他のルックアップが実行される。
【００３２】
ステップ３５０に戻り、ＴＹＰＥビットが「葉」でなかった場合、ステップ３６０にて間接ビットが設定されるかどうかが判断される。間接ビットが設定されない場合、ステップ４１０で示すようにルックアップは完了し、その結果が保存される。
【００３３】
間接ビットがステップ３６０にて設定されると、ステップ３７０において、ＤＲＡＭアドレスがＲＬＥ  ＲＯＯＴに設定される。ステップ３８０において、ＲＬＥ  ＤＲＡＭのアドレスが読取られ、ＴＹＰＥ、ＩＮＤＩＲＥＣＴ、ＯＲＤＥＲ、およびＲＬＥ  ＲＯＯＴの新規値が得られる。ステップ３９０において、ＩＮＤＩＲＥＣＴビットが設定される場合、あるいはタイプが「ノード」の場合、エラーコンディションが示され、ステップ４００で示すようにルックアップは終了する。ＩＮＤＩＲＥＣＴビットが設定されないか、あるいはＴＹＰＥビットがノードを示さないかのどちらかである場合、ステップ４１０で示すようにルックアップは完了となり、その結果が保存される。
【００３４】
以上、本発明の実施形態を詳細に説明したが、本発明の範囲を逸脱することなく他の方法でも具体化出来ることは当業者にとって明らかである。
【図面の簡単な説明】
【図１】ＡＴＭスイッチのトップレベルブロック図である。
【図２】転送エンジンのブロック図である。
【図３】本発明によるルートルックアップエンジンのブロック図である。
【図４】本発明に基づいてルートルックアップを実行するフローチャートである。
【図１】
0003926558.tif 000006
【図２】
0003926558.tif 000007
【図３】
0003926558.tif 000008
【図４】
0003926558.tif 000009