JP4260899B2 - 中継データベースへの中央処理装置のハードウェア支援によるアクセス - Google Patents

Description

発明の分野
本発明は一般に、コンピュータ・ネットワーキング・デバイスに関する。さらに詳細には、本発明は、ハードウェア支援による中央処理装置の中継データベースへの効率的なアクセスを実現できるようにする、スイッチのサーチ・エンジンのアーキテクチャに関する。
発明の背景
費用効率の高い高性能スイッチの実装を達成する重要な面の１つは、あらゆるスイッチ設計の中心となる、中継データベースのサーチ・エンジンのアーキテクチャである。ハードウェアとソフトウェアの間で機能を最適に区分化すること、およびサーチ・エンジンとその「クライアント」（例えばスイッチの入力ポートおよび中央処理装置）の間の対話を効率的にすることは、スイッチ構造全体の性能において極めて重要な役割を果たす。
通常は、中央処理装置（ＣＰＵ）からの支援は、スイッチの中継データベースを維持するために必要である。例えば、ＣＰＵは、中継データベース中の古くなった層３フローを除去する、または無効にすることができる。また、ＣＰＵを使用して、中継データベース中のエントリを更新する、またはこれらのエントリをリオーダすることもできる。サーチ・エンジンが中継データベースを維持するのをＣＰＵが支援する場合には、ＣＰＵが中継データベース中のエントリを読み取り、更新し、またその他のかたちで操作するための機構がなければならない。
１つの手法は、ＣＰＵが中継データベースに直接アクセスできるようにすることである。この手法を使用すると、ＣＰＵは、プログラム入出力（ＰＩＯ）命令を使用して中継データベースを更新する。中継データベースへの直接アクセスは、通常はアービタなど何らかの種類の連結する論理を含むことになるので、この手法を使用するとコストが高くなり、複雑さが増す。さらに、サーチ・エンジンは、ＣＰＵのＰＩＯアクセスがサービスされる前に、不確定な期間、そのアクセスが完了するのを待機することを強いられることがある。したがって、ＰＩＯの速度が比較的低速であると、サーチ・エンジンの帯域幅の利用が非効率的になることがある。
この手法は、中継データベースで通常利用されるメモリが、データ操作のための低レベル命令を何十個または何百個も行うことがあることを考慮すると、さらに複雑になる。この状況では、これらの低レベル呼出しを実施するために大量のソフトウェアを開発しなければならない。ＣＰＵ１６１とこれらの低レベル呼出しの間に抽象化（abstraction）層を設けるように中継データベースのメモリ・ドライバに書き込むことができるが、いずれかのレベルで、ソフトウェアは利用されるあらゆる生の命令を常に知っていなければならない。
さらに、この抽象化層を使用しても、ＣＰＵは中継データベースにアクセスするために、最終的には生の命令を実行しなければならない。中継データベースの保守に必要な時間の相対的な長さは、保守中にＣＰＵが実行しなければならない命令数によって一部決まるので、この直接アクセス手法が非効率的であることは明らかであろう。さらに、複数の中継データベースを維持することができる分散スイッチング・デバイスの状況では、上記の非効率性は分散中継データベースの数だけ倍増する。
上記の内容に基づき、中継データベースのアクセス機構を集中化することが望ましい。さらに詳細には、スイッチ構造の帯域幅をより効率的に利用し、中継データベースの保守に必要な時間を短縮するために、スイッチのＣＰＵがハードウエアの支援によって効率的に中継データベースにアクセスできるようにすることが望ましい。中継データベースへのインタフェース論理の複製を回避するために、中継データベースにアクセスするための低レベル命令についてのスイッチ構造の知識を利用することも有利である。さらに、比較的小さなセットの独立した中継データベースのコマンドを用意して、サービス時間を制限し、全体的なＰＩＯを減少させることを保証することが望ましい。
発明の概要
ハードウエアの支援によってＣＰＵが中継データベースにアクセスできるようにする方法および装置について述べる。本発明の一態様によれば、スイッチ構造が、プロセッサの代わりに中継データベースへのアクセスを行う。スイッチ構造は、中継データベース・メモリへのアクセスを調停するように構成されたメモリ・アクセス・インタフェースを含む。スイッチ構造はまた、メモリ・アクセス・インタフェースおよび複数の入力ポートに結合されたサーチ・エンジンも含む。サーチ・エンジンは、中継データベース・メモリへのアクセスをスケジュールして実施し、そこから取り出した中継決定を入力ポートに送るように構成される。スイッチ構造は、プロセッサから要求された中継データベース・アクセスを実施するためにプロセッサとのインタフェースをとるように構成されたコマンド実行論理をさらに含む。
本発明の別の態様によれば、（１）供給されたアドレスを学習し、（２）供給されたサーチ・キーに対応する関連するデータを読み取り、（３）中継データベースのエントリをエージング（aging）し、（４）エントリを無効にし、（５）マスク・パー・ビット（mask per bit）（ＭＰＢ）の内容アドレス・メモリ（ＣＡＭ）に記憶することができるマスク・データなど、特定のサーチ・キーに対応するマスク・データにアクセスし、（６）中継データベースのエントリを置換し、（７）中継データベース中のサーチ・キーにアクセスするといった機能を実施するために、１つまたは複数のコマンドが与えられる。このようにして、ＣＰＵは、機能性を損なうことなくコマンドの圧縮されたセットを与えられ、またＣＰＵは、特定の中継データベース・メモリの生の命令のセットから保護される。
本発明のその他の特徴は、添付の図面および以下の詳細な説明から明らかになるであろう。
【図面の簡単な説明】
限定ではなく例示を目的として、添付の図面の各図に本発明を図示する。同じ参照番号は同様のエレメントを指すものとする。
第１図は、本発明の一実施形態によるスイッチを示す図である。
第２図は、第１図のスイッチ中で利用することができる例示的なスイッチ・エレメントを示す簡略ブロック図である。
第３図は、本発明の一実施形態による第２図のスイッチ構造を示すブロック図である。
第４図は、本発明の一実施形態による第５図のパイプライン式ヘッダ前処理サブブロックによって作用される総称パケット・ヘッダの一部分を示す図である。
第５図は、本発明の一実施形態による第３図のヘッダ処理論理のパイプライン式ヘッダ前処理サブブロックを示す図である。
第６図は、本発明の一実施形態による第２図の中継メモリの物理編成を示す図である。
第７図は、本発明の一実施形態による中継データベース・メモリのサーチ・スーパーサイクルの決定論理を示す流れ図である。
第８Ａ図から第８Ｃ図は、３つの例示的な中継データベース・メモリのサーチ・スーパーサイクル（ｓｕｐｅｒｃｙｃｌｅ）を示すタイミング図である。
第９図は、本発明の一実施形態による代表的な中継データベース・メモリ・アクセス・コマンドについての一般的なコマンド処理を示す流れ図である。
詳細な説明
ハードウエアの支援によってＣＰＵが中継データベースにアクセスできるようにするサーチ・エンジンのアーキテクチャについて述べる。以下の記述では、説明を目的として、本発明が完全に理解されるように多数の特定の詳細について述べる。しかし、これらの特定の詳細の一部を使用せずに本発明を実施することもできることは、当業者には明らかであろう。その他、周知の構造および装置はブロック図の形態で示してある。
本発明は、後述の様々なステップを含む。本発明の一実施形態によれば、これらのステップは後述のハードウェア構成要素によって実施されるが、別法として機械実行命令で実施することもでき、この命令を使用すると、それがプログラムされた汎用または専用のプロセッサにこれらのステップを実施させるために使用することができる。さらに、高速イーサネット・スイッチに関連して、本発明の実施形態について述べる。ただし、本明細書に記載の方法および装置は、その他のタイプのネットワーク・デバイスにも同様に適用することができる。
例示的なネットワーク・エレメント
本発明の教示に従って動作するネットワーク・エレメントの一実施形態の概要を、第１図に示す。ネットワーク・エレメントは、いくつかのノードおよびエンド・ステーションを多種多様な方法で相互接続するために使用される。特に、マルチ層分散ネットワーク・エレメント（ＭＬＤＮＥ）の適用分野では、イーサネットとも呼ばれるＩＥＥＥ８０２．３標準など、均質な（homogeneous）データ・リンク層にわたる事前決定された経路指定プロトコルに従って、パケットを経路指定することになる。その他の経路指定プロトコルを使用することもできる。
ＭＬＤＮＥの分散アーキテクチャは、いくつかの既知のまたは将来的な経路指定アルゴリズムに従ってメッセージ・トラフィックを経路指定するように構成することができる。好ましい実施形態では、ＭＬＤＮＥは、イーサネットＬＡＮ標準および媒体アクセス制御（ＭＡＣ）データ・リンク層を介して、インターネットのプロトコル・スイート、具体的に言うと伝送制御プロトコル（ＴＣＰ）およびインターネット・プロトコル（ＩＰ）を使用して、メッセージ・トラフィックを処理するように構成される。ＴＣＰはここでは層４プロトコルとも呼び、ＩＰは繰り返して層３プロトコルと呼ぶ。
ＭＬＤＮＥの一実施形態では、ネットワーク・エレメントは、分散型で、すなわちある機能の様々な部分がＭＬＤＮＥ中の様々なサブシステムによって実施され、それらの機能の最終的な結果が外部のノードおよびエンド・ステーションに対して透過なままとなるようなかたちで、パケット経路指定機能を実施するように構成されている。以下の記述および第１図のダイアグラムから分かるように、ＭＬＤＮＥは、設計者が、追加のサブシステムを付加することにより、予測によって外部接続の数を増加させることができるようにし、それによりＭＬＤＮＥを独立型のルータとする際により大きなフレキシビリティを見込む、スケーラブルなアーキテクチャを有する。
第１図にブロックの形態で示すように、ＭＬＤＮＥ１０１は、いくつかの内部リンク１４１を使用して完全に網目状となって相互接続され、より大きなスイッチを形成する、いくつかのサブシステム１１０を含む。少なくとも１つの内部リンクは、任意の２つのサブシステムを結合する。各サブシステム１１０は、中継データベースとも呼ばれる中継およびフィルタリング・データベース１４０に結合されたスイッチ・エレメント１００を含む。中継およびフィルタリング・データベースは、中継メモリ１１３と連想メモリ１１４を含むことができる。中継メモリ（またはデータベース）１１３は、受け取ったパケットのヘッダとの突合せに使用されるアドレス・テーブルを記憶する。連想メモリ（またはデータベース）は、ＭＬＤＮＥを介してパケットを中継するための中継属性を識別するために使用される、中継メモリ中の各エントリに関連するデータを記憶する。入出力能力を有するいくつかの外部ポート（図示せず）は、外部接続１１７とインタフェースをとる。一実施形態では、各サブシステムは、複数のギガビット・イーサネット・ポート、高速イーサネットポート、およびイーサネット・ポートをサポートする。各サブシステム中のやはり入出力能力を有する内部ポート（図示せず）は、内部リンク１４１に結合する。内部リンクを使用すると、ＭＬＤＮＥは複数のスイッチング・エレメントを互いに接続して、マルチギガビット・スイッチを形成することができる。
ＭＬＤＮＥ１０１は、ｐｅｒｉｐｈｅｒａｌ ｃｏｍｐｏｎｅｎｔｓ Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）などの通信バス１５１を介して個別のサブシステム１１０に結合された中央処理システム（ＣＰＳ）１６０をさらに含む。ＣＰＳ１６０は、中央メモリ１６３に結合された中央処理装置（ＣＰＵ）１６１を含む。中央メモリ１６３は、様々なサブシステムの個別の中継メモリ１１３に入っているエントリのコピーを含む。ＣＰＳは、各サブシステム１１０を直接制御し、これらと通信インタフェースをとり、ある程度集中化した通信および制御をスイッチ・エレメント間にもたらす。
例示的なスイッチ・エレメント
第２図は、第１図のスイッチ・エレメントの例示的なアーキテクチャを示す簡略ブロック図である。図示のスイッチ・エレメント１００は、中央処理装置（ＣＰＵ）インタフェース２１５、スイッチ構造・ブロック２１０、ネットワーク・インタフェース２０５、カスケード・インタフェース２２５、および共用メモリ・マネージャ２２０を含む。
イーサネット・パケットは、３つのインタフェース２０５、２１５、または２２５のいずれか１つを通って、ネットワーク・スイッチ・エレメント１００に入る、またはそこから出ることができる。簡単に言うと、ネットワーク・インタフェース２０５は、対応するイーサネット・プロトコルに従って動作し、１つまたは複数の外部ポート（図示せず）を介してネットワーク（図示せず）からイーサネット・パケットを受け取り、ネットワークにイーサネット・パケットを送る。任意選択のカスケード・インタフェース２２５は、スイッチング・エレメントを相互接続してより大きなスイッチを作成するための１つまたは複数の内部リンク（図示せず）を含むことができる。例えば、各スイッチ・エレメント１００を完全な網目状トポロジでその他のスイッチ・エレメントと互いに接続し、上述のマルチ層スイッチを形成することもできる。別法として、スイッチは、カスケード・インタフェース２２５を備えた、または備えない、単一のスイッチ・エレメント１００構成とすることもできる。
ＣＰＵ１６１は、ＣＰＵインタフェース２１５を介してネットワーク・スイッチ・エレメント１００にコマンドまたはパケットを送ることができる。こうして、ＣＰＵ１６１で実行される１つまたは複数のソフトウェア・プロセスで、外部の中継およびフィルタリング・データベース１４０中のエントリを管理することができる（新しいエントリを追加する、望ましくないエントリを無効にするなど）。しかし、代替実施形態では、ＣＰＵ１６１は、中継およびフィルタリング・データベース１４０に直接アクセスすることができる。いずれにしても、パケットを中継するために、ＣＰＵインタフェース２１５のＣＰＵポートは、スイッチ・エレメント１００への総称入力ポートに類似しており、単に別の外部ネットワーク・インタフェース・ポートであるように扱うことができる。ただし、ＣＰＵポートへのアクセスはＰＣＩバスなどのバスを介して行われるので、ＣＰＵポートはどのような媒体アクセス制御（ＭＡＣ）機能も必要としない。
ネットワーク・インタフェース２０５に戻って、次に入力パケット処理および出力パケット処理という２つの主なタスクについて簡単に述べる。入力パケット処理は、ネットワーク・インタフェース２０５の１つまたは複数の入力ポートで実施することができる。入力パケット処理は、（１）到着したイーサネット・パケットを受け取り、検査すること、（２）適当であるときにパケット・ヘッダを修正すること、（３）到着パケットを記憶するために共用メモリ・マネージャ２２０からのバッファ・ポインタを要求すること、（４）スイッチ構造ブロック２１０からの中継決定を要求すること、（５）外部共用メモリ２３０中に一時記憶するために到着パケット・データを共用メモリ・マネージャ２２０に送ること、および（６）中継決定を受け取った後で、１つまたは複数のバッファ・ポインタを、中継決定によって示された１つまたは複数の出力ポートに中継することを含む。出力パケット処理は、ネットワーク・インタフェース２０５の１つまたは複数の出力ポートで実施することができる。出力処理は、共用メモリ・マネージャ２２０からのパケット・データを要求すること、パケットをネットワーク上に送ること、およびパケットを送った後で、１つまたは複数のバッファの割振り解除を要求することを含む。
ネットワーク・インタフェース２０５、ＣＰＵインタフェース２１５、およびカスケード・インタフェース２２５は、共用メモリ・マネージャ２２０およびスイッチ構造ブロック２１０に結合される。パケットの中継やパケットのバッファリングなど重要な機能は、第２図に示すように集中化されることが好ましい。共用メモリ・マネージャ２２０は、到着パケットをバッファリングするための、外部共用メモリ２３０に対する効率的な集中インタフェースとなる。スイッチ構造ブロック２１０は、ＣＰＵ１６１の支援で中継およびフィルタリング・データベース１４０をサーチおよび維持するための、サーチ・エンジンおよび学習論理を含む。
集中化されたスイッチ構造ブロック２１０は、インタフェース２０５、２１５、および２２５に代わって中継およびフィルタリング・データベース１４０へのアクセスを行うサーチ・エンジンを含む。パケット・ヘッダの突合せ、層２ベースの学習、層２および層３のパケットの中継、フィルタリング、およびエージングは、スイッチ構造ブロック２１０によって実施することができる例示的な機能である。各入力ポートは、スイッチ構造ブロック２１０と結合され、受け取ったパケットに対する中継決定を受け取る。中継決定は、対応するパケットを送る１つまたは複数の出発ポート（例えば外部ネットワーク・ポートまたは内部カスケード・ポート）を示す。中継決定に追加の情報を含め、ＭＡＣ ＤＡを置換するための新しいＭＡＣ宛先アドレス（ＤＡ）などのハードウェア経路指定をサポートすることもできる。さらに、中継決定に優先順位指示を含め、スイッチ・エレメント１００を介したパケット・トラフィックの優先順位づけを容易にすることもできる。
この実施形態では、イーサネット・パケットは共用メモリ・マネージャ２２０によって集中してバッファリングされ、管理される。共用メモリ・マネージャ２２０は、あらゆる入力ポートおよび出力ポートとインタフェースをとり、それらの代わりにそれぞれ動的なメモリの割振りおよび割振り解除を実施する。入力パケット処理中には、１つまたは複数のバッファが外部共用メモリ２３０中で割り振られ、到着パケットは、例えばネットワーク・インタフェース２０５から受け取ったコマンドに応答して共用メモリ・マネージャ２２０を介して記憶される。その後、出力パケット処理中に、共用メモリ・マネージャ２２０は、このパケットを外部共用メモリ２３０から取り出し、使用されなくなったバッファを割振り解除する。全ての出力ポートがその中に記憶されたデータの送りを完了するまでバッファが解放されないことを保証するために、共用メモリ・マネージャ２２０は、バッファの所有権を追跡することが好ましい。
入力ポート／スイッチ構造インタフェース
スイッチ構造２１０の内部の詳細について述べる前に、入力ポート（例えばパケットを受け取ることができる任意のポート）とスイッチ構造２１０の間のインタフェースについて簡単に述べる。ＣＰＵインタフェース２１５、ネットワーク・インタフェース２０５、およびカスケード・インタフェース２２５それぞれの入力ポートは、スイッチ構造２１０からの到着パケットに対する中継決定を要求する。本発明の一実施形態によれば、以下のインタフェースを利用する。
（１）Ｆｗｄ＿Ｒｅｑ［Ｎ：０］―中継要求信号
これらの中継要求信号は、入力ポートからスイッチ構造２１０に出力される。これらには２つの目的がある。第１に、これらは、対応する入力ポートが有効なパケット・ヘッダを受け取り、このパケット・ヘッダをスイッチ構造にストリーミングする準備ができていることをスイッチ構造２１０に示す働きをする。ヘッダ転送認可信号（下記のＨｄｒ＿Ｘｆｒ＿Ｇｎｔ［Ｎ：０］を参照）は、パケット・ヘッダの転送が開始される前にアサートされるものと予想される。第２に、これらの信号は、ヘッダ転送認可が検出された後で、中継決定を求める要求として働く。中継要求信号は、中継決定の確認（下記のＦｗｄ＿Ａｃｋ［Ｎ：０］参照）がスイッチ構造２１０から検出された後のクロック周期中にアサート解除される。
（２）Ｈｄｒ＿Ｘｆｒ＿Ｇｎｔ［Ｎ：０］―ヘッダ転送認可信号
これらのヘッダ転送認可信号は、スイッチ構造２１０から入力ポートに出力される。さらに詳細には、これらの信号は、以下でさらに述べるスイッチ構造のヘッダ前処理論理から出力される。いずれにしても、ヘッダ転送信号は、ヘッダ前処理論理が、対応する入力ポートからパケット・ヘッダを受け取る準備ができていることを示す。ヘッダ転送認可のアサートを検出すると、対応する入力ポートは、連続的なヘッダ・フィールドをスイッチ構造２１０にストリーミングし始めることになる。
（３）Ｈｄｒ＿Ｂｕｓ［Ｘ：１］［Ｎ：０］―専用ヘッダ・バス
ヘッダ・バスは、各入力ポートからスイッチ構造２１０までの専用のＸビットの幅のバスである。一実施形態ではＸは１６であり、これによりパケット・ヘッダを２バイトで送ることが可能となる。
（４）Ｆｗｄ＿Ａｃｋ［Ｎ：０］―中継決定確認信号
これらの中継決定確認信号は、入力ポートからの対応する中継要求信号（上記のＦｗｄ＿Ｒｅｑ［Ｎ：０］参照）に応答して、スイッチ構造２１０によって生成される。これらの信号は、中継決定の準備ができていない間はアサート解除される。中継決定確認信号がアサートされると、対応する入力ポートは、中継決定バス（下記のＦｗｄ＿Ｄｅｃｉｓｉｏｎ［Ｙ：０］参照）が有効な中継決定を有しているものと仮定することになる。対応する入力ポートは、その中継決定確認を検出した後で、必要なら別の中継要求を行う。
（５）Ｆｗｄ＿Ｄｅｃｉｓｉｏｎ［Ｙ：０］―共用中継決定バス
この中継決定バスは、全ての入力ポートによって共用される。これは、パケットを中継する出力ポート番号を示す。中継決定は、発信されるパケットの優先順位、ＶＩＤの挿入、ＤＡの置換、およびその他入力ポートに有用となりうる情報を示すデータを含むこともできる。
スイッチ構造の概要
入力ポートとスイッチ構造２１０の間のインタフェースについて述べたので、次に、スイッチ構造２１０の内部の詳細について述べる。第３図を参照すると、例示的なスイッチ構造２１０のブロック図が示してある。一般に、スイッチ構造２１０は、入力ポートから出力ポートにパケットを向けることを担当する。スイッチ構造２１０の目的は、スイッチを通る遅延を低く保ち、全てのポートでワイヤスピード・スイッチングを達成するために、可能な限り短い時間で入力ポートに対して中継決定を生成することである。スイッチ構造の主な機能は、実時間のパケット・ヘッダの突合せ、層２（Ｌ２）ベースの学習、Ｌ２および層３（Ｌ３）のエージング、入力ポートの代わりに中継データベース・メモリ１４０から中継情報をサーチし、取り出すための、Ｌ２およびＬ３のサーチ・キーの形成、ならびに中継データベース・メモリ１４０中のエントリを効率的に管理するための、ソフトウェア用のコマンド・インタフェースを実施することである。
層２ベースの学習は、スイッチング・デバイスを通過するトラフィックに基づいて中継データベース１４０のＭＡＣアドレス部分を絶えず更新するプロセスである。パケットがスイッチング・デバイスに進入したときに、そのパケットのＭＡＣ出所アドレス（ＳＡ）をそのパケットが到着した入力ポートと相関させるエントリが、データベース中で作成される（または既存のエントリが更新される）。このようにして、スイッチング・デバイスは、どのサブネット上にノードがあるかを「学習」する。
エージングは、リンク層およびネットワーク層の両方で行われる。これは、エントリにタイム・スタンプし、満了したエントリを中継データベース・メモリ１４０から除去するプロセスである。エージングには、（１）ＭＡＣ ＳＡに基づくエージング、および（２）ＭＡＣ宛先アドレス（ＤＡ）に基づくエージングの２つのタイプがある。前者は層２のエージング用であり、後者は非アクティブな層３フローを除去する助けとなる。したがって、エージングは、非アクティブなフロー・スペースを新しいフローのために再利用する助けとなる。所定の時間間隔で、中継データベースのエントリ中にエージング・フィールドがセットされる。ＭＡＣ ＳＡまたはＭＡＣ ＤＡのサーチ中に発見されたエントリは、そのエージング・フィールドをクリアされる。このようにして、アクティブなエントリは、例えば０にセットされたエージング済みのビットを有する。定期的に、ソフトウェアまたはハードウェアで非アクティブな（満了した）エントリを中継データベース・メモリ１４０から除去し、それによりより効率的なデータベース管理を行うことができる。エージングは、学習されて以来「移動し、沈黙して」いたノードへの接続の回復も可能にする。このようなノードには、フラッディング（ｆｌｏｏｄｉｎｇ：溢れ）によってのみ到達することができる。
サーチ・キーの形成を実施するための例示的な論理について述べる前に、サーチ・キーを形成するプロセスについて簡単に述べる。本発明の一実施形態によれば、パケットは、大きく分けてＬ２エントリまたはＬ３エントリの２つのグループの１つに分類される。Ｌ３エントリは、いくつかのヘッダ・クラスの１つの一部分としてさらに類別することができる。ヘッダ・クラスの例としては、（１）パケット・ヘッダがＡＲＰパケットと関連していることを示すアドレス解決プロトコル（ＡＲＰ）クラス、（２）パケット・ヘッダがＲＡＲＰパケットと関連していることを示す逆ＡＲＰ（ＲＡＲＰ）クラス、（３）パケット・ヘッダがＰＩＭパケットと関連していることを示すＰＩＭクラス、（４）パケット・ヘッダがＲＳＶＰパケットと関連していることを示すリザベーション・プロトコル（Reservation Protocol）（ＲＳＶＰ）クラス、（５）パケット・ヘッダがＩＧＭＰパケットと関連していることを示すインターネット・グループ管理プロトコル（Internet Group Management Protocol）（ＩＧＭＰ）クラス、（６）パケット・ヘッダがＴＣＰパケットと関連していることを示す伝送制御プロトコル（ＴＣＰ）フロー・クラス、（７）パケット・ヘッダが非断片化ＵＤＰパケットと関連していることを示す非断片化ユーザ・データグラム・プロトコル（ＵＤＰ）フロー・クラス、（８）パケット・ヘッダが断片化ＵＤＰパケットと関連していることを示す断片化ＵＤＰフロー・クラス、（９）パケット・ヘッダがハードウェア経路指定可能なＩＰパケットと関連していることを示すハードウェア経路指定可能なインターネット・プロトコル（ＩＰ）クラス、および（１０）パケット・ヘッダがＩＰ Ｖ６パケットと関連していることを示すＩＰバージョン６（ＩＰ Ｖ６）クラスがある。
本発明の一実施形態では、サーチ・キーは、ヘッダ・クラスおよび到着パケットのヘッダから選択した情報の符号化に基づいて形成される。Ｌ２サーチ・キーは、ヘッダ・クラス、Ｌ２アドレス、およびＶＩＤに基づいて形成することができる。Ｌ３サーチ・キーは、ヘッダ・クラス、入力ポート・リスト、および例えばヘッダ・クラスに基づく選択可能なＬ３ヘッダ・フィールドに基づいて形成することができる。一実施形態では、局所スイッチ・エレメント１００のメモリ中でヘッダ・クラスごとにマスクを設け、ヘッダ・フィールドの選択を容易にすることができる。
第３図に示す実施形態では、スイッチ構造２１０は、ヘッダ前処理アービタ３６０、パケット・ヘッダ前処理論理３０５、サーチ・エンジン３７０、学習論理３５０、ソフトウェア・コマンド実行ブロック３４０、および中継データベース・メモリ・インタフェース３１０を含む。
ヘッダ前処理アービタ３６０は、パケット・ヘッダ前処理論理３０５、ならびにネットワーク・インタフェース２０５、カスケード・インタフェース２２５、およびＣＰＵインタフェース２１５の入力ポートに結合される。入力ポートは、パケット・ヘッダをスイッチ構造２１０に転送し、例えば上述の方法で中継決定を要求する。
スイッチ構造２１０は、より高速のネットワーク・リンクに優先権を与えることによって、混合したポート速度をサポートすることができる。例えば、ヘッダ前処理アービタ３６０は、Ｎ個のより低速のインタフェース（例えば高速イーサネット・ポート）のそれぞれにサービスするたびに高速のインタフェース（例えばギガビット・イーサネット・ポート）それぞれにサービスすることによってより高速のインタフェースに優先権を与える、優先順位付きのラウンドロビン方式で、中継要求間の調停をするように構成することができる。
サービスする中継要求を選択した後で、ヘッダ前処理アービタ３６０は、対応するパケット・ヘッダをヘッダ前処理論理３０５に送る。ヘッダ前処理論理３０５は、Ｌ２カプセル化のフィルタリングおよび整列、ならびにＬ３ヘッダの比較および選択論理を実施する。
サーチ・エンジン３７０は、サーチ要求を作成するために中継データベース・メモリ・インタフェース３１０に、またサーチ・キーを生成するための情報を求めるためにヘッダ前処理論理３０５に結合される。サーチ・エンジン３７０は、学習処理をトリガするために、学習論理３５０にも結合される。サーチ・エンジン３７０は、中継データベース・メモリ１４０へのアクセスをスケジュールして実施する論理を含み、またサーチ・キーの形成を実施すること、中継データベース・メモリ１４０から取り出したＬ２およびＬ３の結果を併合すること、フィルタリングすること、要求している入力ポートに対して中継決定を生成することなどを含む、中継およびフィルタ・アルゴリズムを実行する。学習のために、クリアされたエージ・ビットや修正された出力ポート・リストなど、更新された中継データベースのエントリ情報が、サーチサイクル中の適当な時点で学習論理３５０から与えられ、中継データベース・メモリ１４０が更新される。最後に、以下でさらに述べるように、中継データベース・メモリ１４０からサーチ結果を入手できるようになると、サーチ・エンジン３７０は中継決定を生成し、要求している入力ポートに対して送る。
中継データベース・メモリ・インタフェース３１０は、サーチ・エンジン３７０およびソフトウェア・コマンド実行ブロック３４０から中継データベース・メモリ１４０へのアクセス要求を受け取り、調停する。
ソフトウェア・コマンド実行ブロック３４０は、ＣＰＵバスに結合される。ＣＰＵ１６１と情報を交換するために、プログラマブルなコマンド・レジスタ、状態レジスタ、および内部レジスタをソフトウェア・コマンド実行ブロック３４０中に設けることができる。重要なこととして、比較的小さなコマンドのセットをＣＰＵに与えることにより、スイッチ構造２１０は、中継データベース・メモリの態様に応じて必要となることがある何十個または何百個もの低レベル命令からＣＰＵを保護する。例として、例えばＣＰＵが内容アドレス・メモリに直接アクセスできるようにするアーキテクチャでは、中継データベース・メモリにアクセスするために、追加のソフトウェアが大量に必要となる。スイッチ構造２１０が既に中継データベース・メモリ１４０のインタフェースについての知識を有することを考慮すると、この追加ソフトウェアは余分であり不要となる。
本発明では、分散中継データベースを有するアーキテクチャに関して、効率についてのさらなる考慮事項に対処する。例えば、分散アーキテクチャでは、中継データベース全体のイメージをソフトウェア中に保持することが望ましいことがある。この場合には、おそらくソフトウェアは定期的に、個別の中継データベースそれぞれから全てのエントリを読み取ることが必要となることになる。１つまたは複数の中継データベースは非常に大きくなることがあるので、ＣＰＵが１つまたは複数の中継データベースに直接アクセスできるようにするアーキテクチャは、非効率的なプログラム入出力（ＰＩＯ）を数多く必要とすることがある。
したがって、本明細書で述べるように、ＣＰＵ１６１と中継データベース１４０の間の中間物としてスイッチ構造２１０を利用すると有利であることになる。本発明の一実施形態によれば、ソフトウェア・コマンド実行ブロック３４０は、中継データベース・メモリ１４０への効率的なアクセスおよびその保守のために、所定のコマンドのセットをソフトウェアに与えることができる。後述するこの所定のコマンドのセットは全体的なＰＩＯを減少させるように決められる。これらのコマンドおよびプログラマブル・レジスタについては、以下でさらに詳細に述べる。
レジスタのセットの例としては、（１）ＣＰＵ１６１からコマンドを受け取り、保留のコマンドの状態を示すコマンドおよび状態レジスタ、（２）中継データベース１４０に書き込む新しいエントリを一時記憶する書込み新規エントリ・レジスタ、（３）適当な中継データベース・エントリを突き止めるために使用されるキーを記憶する書込みキー・レジスタ、（４）中継データベース１４０に書き込むデータを記憶する書込みデータ・レジスタ、（５）中継データベース・メモリ中の読取りまたは更新を行うロケーションを記憶する、アドレス・カウンタ・レジスタ、（６）読取りエントリ動作の結果を記憶する読取りエントリ・レジスタ、ならびに（７）その他の読取り動作の結果を記憶する読取りデータ・レジスタがある。
本発明の一実施形態では、中継データベース・メモリ１４０へのアクセスを容易にするために、アドレス・カウンタ・レジスタを使用する。ソフトウェアは、読取り／書込みのシーケンスの開始アドレスをそのシーケンスの最初の読取り／書込みの前にアドレス・レジスタにプログラムしさえすればよい。最初のメモリ・アクセスの後で、アドレス・レジスタは後続のアクセスのために自動的に増分される。このようにして、ソフトウェアが各メモリ・アクセスの前にアドレスを更新する必要がないことから追加のＰＩＯが節約されるので有利である。
ソフトウェア・コマンド実行ブロック３４０はさらに、中継データベース・メモリ・インタフェース３１０に結合される。コマンドおよびデータは、ソフトウェア・コマンド実行ブロック３４０によってプログラマブル・レジスタから読み取られ、適当な中継データベース・メモリ・アクセスの要求および事象は、第９図に関連してさらに詳細に述べるように生成される。ソフトウェア・コマンド実行ブロック３４０は、状態レジスタを介してコマンドの状態をソフトウェアに戻すこともできる。このようにして、ソフトウェア・コマンド実行ブロック３４０は、ハードウエアの支援によってＣＰＵが中継データベース・メモリ１４０にアクセスすることができるようにする。
パケット・ヘッダ処理
第４図は、本発明の一実施形態による第５図のパイプライン式ヘッダ前処理サブブロックによって作用される総称パケット・ヘッダの一部分を示している。この実施形態によれば、パケット・ヘッダ４９９は、４つの部分、すなわちＬ２ヘッダ部分４７５、Ｌ２カプセル化部分４８０、Ｌ３アドレス独立部分４８５、およびＬ３アドレス依存部分４９０に区分化される。
この例では、Ｌ２ヘッダ部分４７５は、ＭＡＣ ＳＡフィールドおよびＭＡＣ ＤＡフィールドを含むことができる。カプセル化のタイプ（例えばＩＥＥＥ８０２．１Ｑタグ式やＬＬＣ−ＳＮＡＰ）に応じて、Ｌ２カプセル化部分は、仮想ローカル・エリア・ネットワーク（ＶＬＡＮ）タグまたは８０２．３の型／長さのフィールド、およびＬＬＣ ＳＮＡＰフィールドを含むことができる。Ｌ３アドレス独立部分４８５は、ＩＰフラグ／フラグメント・オフセット・フィールド、およびプロトコル・フィールドを含むことができる。最後に、Ｌ３アドレス依存部分４９０は、ＩＰソース・フィールド、ＩＰ宛先フィールド、ＴＣＰソース・ポート、およびＴＣＰ宛先ポートを含むことができる。Ｌ３アドレス独立部分４８５およびＬ３アドレス依存部分４９０中のフィールドの相対位置は、Ｌ２カプセル化部分４８０中のカプセル化のタイプに応じて様々にすることができることに留意されたい。
第５図は、本発明の一実施形態によるパイプライン式ヘッダ前処理サブブロックを示している。この実施形態によれば、ヘッダ前処理論理３０５は、４ステージ・パイプラインとして実装することができる。パイプライン中の各ステージは、パケット・ヘッダ４９９の対応する部分に作用する。図示のパイプラインは、４つのステージ・アービタ５０１〜５０４、アドレス累積ブロック５１０、カプセル化ブロック５２０、Ｌ３ヘッダ・クラス突合せブロック５３０、およびＬ３アドレス依存ブロック５４０を含む。この例では、ヘッダ前処理論理３０５は、４つの入力ポートからのパケット・ヘッダを同時に処理することができる。例えば、アドレス累積ブロック５１０が第１の入力ポートからのパケットのＬ２ヘッダ部分４７５を処理し、カプセル化ブロック５２０が第２の入力ポートからのパケットのＬ２カプセル化部分４８０を処理し、Ｌ３ヘッダ・クラス突合せブロック５３０が第３の入力ポートのＬ３アドレス独立部分４８５を処理し、Ｌ３アドレス依存ブロック５４０が第４の入力ポートからのパケットのＬ３アドレス依存部分４９０を処理していることもある。
重要なこととして、４つのパイプライン・ステージに関してこの実施形態を説明したが、これより多いステージを利用することも、少ないステージを利用することもできること、および様々にグループ化したパケット・ヘッダ情報を使用することができることを理解されたい。第４図に示すこのヘッダ部分の識別は、便宜上選択したものである。これらのヘッダ部分４７５〜４９０の境界は、例示的な各ヘッダ部分４７５〜４９０内のフィールドの既知の特徴に基づいて容易に識別することができる。さらに、ヘッダ部分４７５〜４９０は、ほぼ同じ時間で処理することができる。
いずれにしても、引き続きこの例について述べると、アービタ５０１〜５０４がパイプラインのステージへのアクセスを調整する。アービタ５０１〜５０４は、所与のパケットが一度に１つのステージで連続して（アドレス累積ブロック５１０から始まってＬ３アドレス依存ブロック５４０で終わる）処理されるように機能する。パイプラインの最初のステージであるアドレス累積ブロック５１０は、パケット・ヘッダのＬ２ヘッダ部分４７５からＭＡＣ ＳＡおよびＭＡＣ ＤＡを抽出するように構成されている。アドレス累積ブロック５１０は、次いで、この抽出した情報を、Ｌ２サーチ・キー５４５の一部分として使用するためにサーチ・エンジンに送る。
カプセル化ブロック５２０は、パケット・ヘッダのＬ２カプセル化部分４８０のカプセル化のタイプを決定するように構成されている。上記で示したように、Ｌ２カプセル化部分に続くフィールドの相対的な位置決めは、利用するカプセル化のタイプに応じて様々となる。したがって、カプセル化ブロックはさらに、Ｌ２カプセル化部分４８０の始点からＬ３アドレス独立部分４８５の始点までのオフセットを計算する。次いで、このオフセットを後続のステージで使用して、パケット・ヘッダを適当に整列する。
Ｌ３ヘッダ・クラス突合せブロック５３０は、Ｌ３ヘッダ・クラスの識別を容易にするために既知である所定値を含むことができる複数のプログラマブル・レジスタとパケット・ヘッダとを比較することによって、Ｌ３ヘッダのクラスを決定するように構成されている。各プログラマブル・レジスタは、ただ１つのヘッダだけが任意の所与のパケットと一致することになるようにセットされるものとする。所与のレジスタが一致すると判定した後で、クラス・コードがサーチ・エンジンに出力され、Ｌ３サーチ・キーの一部分として使用される。
Ｌ３アドレス依存ブロック５４０は、適当なバイト数のＬ３アドレス依存部分４９０を、Ｌ３サーチ・キー５５５中で使用するために抽出するように構成されている。この抽出は、例えばＭ個のＣＰＵプログラマブルなバイトおよびビット・マスクを利用することによって実施することができる。ヘッダ・クラスに対応するプログラマブルなバイトおよびビット・マスクは、Ｌ３ヘッダ・クラス突合せブロック５３０によって決定され、所望のフィールドをマスクするために使用することができる。ヘッダ前処理論理３０５をパイプライン化することでハードウェアの実装オーバヘッドが節約されるので有利である。例えば、複数のパケット・ヘッダを、非パイプライン式で第５図の論理を実施するために普通なら必要となる４つの処理ブロックではなく、単一の処理ブロックで同時に処理することができる。上記ヘッダ前処理を中継データベース・メモリ１４０のアクセスとさらにパイプライン化することによって、追加の並列処理を達成することができることに留意されたい。例えば、Ｌ２サーチはパケットが第５図のパイプラインを完了するのを待つ必要はなく、パケット・ヘッダが第１のステージを完了すると直ちにＬ２サーチを開始することができ、Ｌ２サーチ・キーはサーチ・エンジン３７０から入手できるようになる。後続のＬ２サーチは、新しいＬ２サーチ・キーが入手可能となるにつれて、その前の中継データベース・メモリ・アクセスが完了した後で開始することができる。
中継データベース・メモリ
第６図は、本発明の一実施形態による第２図の中継データベース・メモリの物理編成を示している。図示の実施形態では、中継データベース・メモリ１４０は、２つのカスケード式のフルアソシエイティブ内容アドレス・メモリ（ＣＡＭ）６１０および６２０と、静的ランダム・アクセス・メモリ（ＳＲＡＭ）６３０とを含む。
スイッチ構造２１０は、ＣＰＵ１６１と協働して、組み合わせたリンク層（「層２」とも呼ぶ）およびネットワーク層（「層３」とも呼ぶ）のパケット・ヘッダ・フィールド・ベースの中継およびフィルタリング・データベース１４０を維持する。中継およびフィルタリング・データベース１４０は主にオフチップ・メモリ（例えば１つまたは複数のＣＡＭやＳＲＡＭ）に記憶され、実時間パケット・中継およびフィルタリング決定を下すための情報を含む。
本発明の譲受人は、層２（Ｌ２）エントリおよび層３（Ｌ３）エントリを互いに物理的にグループ化することが有利であることを発見した。したがって、Ｌ２エントリを「Ｌ２データベース」と呼び、Ｌ３エントリのグループを論理的に「Ｌ３データベース」と呼ぶこともできる。ただし、Ｌ２データベースおよびＬ３データベースが複数のＣＡＭにまたがることができることに留意することは重要である。すなわち、いずれかのＣＡＭが、Ｌ２エントリおよび／またはＬ３エントリを含むことができるということになる。層２および層３の中継データベースはともに、ＣＡＭ−ＲＡＭチップ・セットに記憶される。便宜上、中継データベース・メモリ１４０のＣＡＭ部分に入っているデータを「連想データ」と呼び、中継データベース・メモリ１４０のＳＲＡＭ部分に入っているデータを「関連データ」と呼ぶ。
以下でさらに説明するように、エントリは、第１のサイズのキーを使用してＬ２データベースから取り出すことができ、また第２のサイズのキーを使用してＬ３データベースから取り出すことができる。したがって、一実施形態では、スイッチング・エレメント１００は、様々な幅のＣＡＭを混合することができる。中継データベース・メモリ１４０の構成に関わらず、スイッチ構造２１０およびＣＰＵ１６１の論理ビューは、少なくとも２つの異なるサイズのビット突合せ動作を受け入れる連続メモリとなるものとし、このメモリの全体または一部は最大のビット突合せ動作と同じ幅となる。
ＣＡＭの様々な組合せを企図することができる。様々な幅、および様々な内部構造（例えばマスク・パー・ビット（ＭＰＢ）や大域マスク）のＣＡＭを利用することができる。いくつかの実施形態ではＣＡＭ６１０および６２０はともに同じ幅を有し、その他の実施形態ではＣＡＭ６１０および６２０は異なる幅を有することがある。例えば、一実施形態では、ＣＡＭ６１０および６２０はともに１２８ビットの幅および２Ｋの深さとなることがある。あるいは第１のＣＡＭ６１０は１２８ビットの幅となり、第２のＣＡＭ６２０は６４ビットの幅となることもある。Ｌ２エントリは通常はＬ３エントリより狭いので、ＣＡＭの幅が混合している実施形態では、狭い方のＣＡＭの幅をＬ２エントリのために最適化すると有利である。ただし、この場合には、より狭いＣＡＭにはＬ２エントリしか記憶することができない。しかし、それでも、Ｌ２およびＬ３のエントリはともに広い方のＣＡＭ中に存在することができる。
カスケード式の２重ＣＡＭ６１０および６２０に関連してこの実施形態について述べたが、論理ビューは１つの連続ブロックであるので、Ｌ２データベースおよびＬ３データベースは上記に示した数より多いＣＡＭを使用することも、少ないＣＡＭを使用することもできることを理解されたい。例えば、代替実施形態では、Ｌ２データベースおよびＬ３データベースを結合して単一のメモリにすることもできる。
中継データベース・メモリ１４０の例示的な物理編成について述べたが、次にその中に入っているデータについて簡単に述べる。ＳＲＡＭ６３０の１つまたは複数のラインは、ＣＡＭ部分の各エントリと関連づけることができる。ＣＡＭの一部分がＲＡＭとして使用されていることもあることに留意されたい。ただし、連想データと関連データを区分化することの目的の１つは、サーチを効率的にするために連想データの最小セットを生成しながら、残りの関連データを別個のメモリ、例えばより安価なＲＡＭに記憶することである。第８Ａ図〜第８Ｃ図に関連して以下に述べるように、連想データと関連データを分離することで、中継データベース・メモリ１４０をより効率的にサーチし、更新することが可能となる。連想データと関連データを効率的に区分化することにより、さらに別の利点ももたらされる。例えば、連想データ・フィールド中のデータの量を最小限に抑えることにより、中継データベースへのアクセス、およびＣＰＵ１６１によって実施することができるＬ３エントリの不定期な入替えなどの保守に必要となる時間および資源が減少する。さらに、効率的に区分化することで、中央メモリ１６３中の中継データベースの集合体コピーの保守を行うために中継データベース全体についてとることができるスナップ・ショットに要する時間が短縮される。
一般に、連想データは、サーチ・キーを突き合わせるデータである。パケット・アドレス情報は、通常はこの目的のために有用である。一実施形態では、連想データは、エントリのタイプ（例えばＬ２またはＬ３）に応じて下記のフィールドのうちの１つまたは複数を含むことができる。
（１）連想エントリのタイプを示すクラス・フィールド、
（２）到着パケットのＭＡＣ ＤＡまたはＳＡのフィールドと突き合わせることができる媒体アクセス制御（ＭＡＣ）アドレス、
（３）仮想ローカル・エリア・ネットワーク（ＶＬＡＮ）識別子（ＶＩＤ）フィールド、
（４）インターネット・プロトコル（ＩＰ）宛先アドレス、
（５）ＩＰ出所アドレス、
（６）ＴＣＰまたは非断片化ＵＤＰフローの宛先ポート番号、
（７）ＴＣＰまたは非断片化ＵＤＰフローのソース・ポート番号、および
（８）効率的なマルチキャスト経路指定をサポートする入力ポート・リスト。
連想データは、上述のマスク・パー・ビット（ＭＰＢ）ＣＡＭを利用することによって、上記の変数ビットを含むこともできる。
関連データは、一般に、パケットを中継することができる１つまたは複数の出力ポートを示す指示、制御ビット、ソースおよび宛先のノードがアクティブであるかどうかを常に把握しておくための情報などの情報を含む。また、関連データは、ＭＡＣ ＤＡの置換のためのＭＡＣアドレス、およびタグ付けのためのＶＩＤを含む。具体的に言うと、関連データは下記のフィールドのうち１つまたは複数を含むことができる。
（１）そのパケットを中継することができる１つまたは複数のポートのセットを示すポート・マスク、
（２）優先タグ付けおよび優先待合せのための優先順位フィールド、
（３）どのポートがそのパケットをベスト・エフォートとして待ち行列に入れるべきかを示すベスト・エフォート・マスク、
（４）パケット・ヘッダのみをＣＰＵに転送すべきであることを示すヘッダ・オンリー・フィールド、
（５）マルチキャスト経路指定を活動化するためのマルチキャスト経路フィールド、
（６）元のＤＡを置換するために使用される次のホップのＬ２ＤＡを決める次のホップ宛先アドレス、
（７）ＶＬＡＮ間の経路指定が、例えば到着タグと異なる発信タグを必要とするときに、そのパケットのための新しいタグとして使用することができる新規ＶＩＤフィールド、
（８）新しいＶＩＤフィールドを使用すべきであることを示す新規タグ・フィールド、
（９）中継データベース中でどのＬ２エントリがアクティブであるか、またどれを除去することができるかを決定する、エージング済みのソースの指示、
（１０）ＩＥＥＥ８０２．１ｄタイプのアドレス・エージングを実施し、中継データベース中でどのＬ２またはＬ３のエントリがアクティブであるか、またどれを除去することができるかを決定するための、エージング済みの宛先の指示、
（１１）Ｌ３の結果が利用できるときにもＬ２の結果を中継に使用するよう併合機能に命令するためのＬ２オーバライド指示、
（１２）中継データベース中の自動的なＬ２の学習またはエージングを受けない静的エントリを識別するための静的指示、
（１３）次のスイッチング・エレメント上で使用される突合せサイクル（Ｌ２またはＬ３）のタイプを制御するために内部（カスケード）リンクにわたって使用される、分散フロー指示、ならびに
（１４）エントリまたはエントリのグループの到着率を推定するためのフロー・レート・カウント。
中継データベースのサーチ・スーパーサイクルを決定する流れ
第７図は、本発明の一実施形態による、中継データベース・メモリのサーチ・スーパーサイクルの決定論理を示す流れ図である。ステップ７０２で、パケットを内部リンクで受け取るか外部リンクで受け取るかに応じて、処理はそれぞれステップ７０４またはステップ７０６に進む。
内部リンクに特有の処理としては、ステップ７０４、７１２、７１４、７２０、７２２、および７２４がある。ステップ７０４では、パケットは内部リンクで受け取られているので、検査を実施して、そのパケットが分散フローの一部であるかどうかを決定する。一部である場合には、処理はステップ７１４に進む。パケットが分散フローの一部でない場合には、処理はステップ７１２に進む。
内部リンクの場合には学習は実施されず、したがってステップ７１２で、中継データベース・メモリ１４０についてＤＡサーチのみが実施される。
ステップ７１４で、Ｌ３サーチを実施し、到着パケットについての中継決定を取り出す。ステップ７２０で、ステップ７１４のサーチ中に一致するＬ３エントリが発見されたかどうかを判定する。発見されなかった場合には、ステップ７２２で、クラス・アクション・デフォルトを適用し（例えばパケットまたはパケット・ヘッダをＣＰＵ１６１に中継する）、処理はステップ７８０に進む。一致するＬ３が発見された場合には、ステップ７２４で、一致するエントリに対応する関連データを中継データベース１４０から読み取り、処理はステップ７８０に進む。
ステップ７０８で、層２の学習が実施される。学習サイクル後に、ヘッダ・クラスが決定され、ステップ７１６で、このヘッダ・クラスはＬ３のユニキャスト経路のヘッダ・クラスと比較される。ステップ７１６で一致がある場合には、処理はステップ７２６に進み、そうでない場合には、ステップ７１８で別の試験が実施される。ステップ７１８で、ヘッダ・クラスは残りのＬ３ヘッダ・クラスと比較される。
Ｌ２として類別されたヘッダと関連するパケットに特有の処理としては、ステップ７２８および７３８がある。ヘッダ・クラスがＬ３ヘッダ・クラスでないと決定された場合には、ステップ７２８で、Ｌ２中継決定のためにＤＡサーチが実施される。ステップ７３８で、Ｌ２決定アルゴリズムを適用し、処理はステップ７８０に進む。
Ｌ３経路として類別されたヘッダと関連するパケットに特有の処理としては、ステップ７２６、７３２、７３４、７３６、７４８、７５０、７５４、７５６、７５２、７５８、および７６０がある。ステップ７２６で、中継データベース１４０についてＬ３サーチが実施される。一致するＬ３エントリが発見された（ステップ７３２）場合には、この一致するエントリに対応する関連データが中継データベース１４０から読み取られる（ステップ７３６）。そうでない場合には、ステップ７３４で、クラス・アクション・オプションが適用され、処理はステップ７８０に進む。
パケットがマルチキャスト・パケットである（ステップ７４８）場合には、Ｔｉｍｅ＿Ｔｏ＿Ｌｉｖｅ（ＴＴＬ）カウンタは０または１と突き合わせて試験され（ステップ７５０）、そうでない場合には、処理はステップ７５２に進む。ステップ７５０でＴＴＬが０または１であると決定された場合には、パケットは、ステップ７８０に進む前にＣＰＵ１６１に中継される。そうでない場合には、ステップ７５４で、宛先アドレスサーチを実施し、中継データベース１４０からＬ２中継・エントリを取り出し、Ｌ２決定アルゴリズムが適用される（ステップ７５６）。
ステップ７４８でパケットがユニキャスト・パケットであると決定された場合には、ＴＴＬは０または１と突き合わせて試験される（ステップ７５２）。ＴＴＬが０または１であると決定された場合には、パケットはＣＰＵ１６１に中継される。そうでない場合には、ステップ７６０でＬ３の突合せが利用され、処理はステップ７８０に進む。
Ｌ３として類別されたヘッダと関連するパケットに特有の処理としては、ステップ７３０、７４０、７４２、７６２、７６４、７６６、７４４、７４６、７６８、および７７０がある。ステップ７３０で、Ｌ３サーチが中継データベース１４０から要求される。一致するＬ３エントリが発見された（ステップ７４０）場合には、この一致するエントリに対応する関連データが中継データベース１４０から読み取られる（ステップ７４４）。そうでない場合、一致するＬ３エントリが発見されないときには、ステップ７４２で、中継データベース１４０中で一致するＬ２エントリを発見するためにＤＡサーチが実施される。
Ｌ２決定を使用すべきであると中継決定が示す場合（ステップ７６２）には、ステップ７７０でＬ２決定アルゴリズムが適用される。そうでない場合には、クラス・アクション・オプションが適用される（ステップ７６４）。Ｌ２の結果を使用してパケットを中継すべきであるとクラス・アクション・オプションが示す場合（ステップ７６６）には、処理はステップ７７０に進む。そうでない場合には、処理はステップ７８０に分岐する。
ステップ７４６で、パケットの宛先アドレスを使用して、中継データベース１４０について宛先アドレスサーチが実施される。Ｌ２決定を使用すべきであると中継決定が示す場合（ステップ７６８）には、処理はステップ７７０に進む。そうでない場合には、ステップ７４４で取り出された関連データが利用されることになり、処理はステップ７８０に進む。ステップ７７０で、Ｌ２決定アルゴリズムが適用され、処理はステップ７８０に進む。最後に、中継決定がアセンブルされる（ステップ７８０）。
第７図に示すように、外部リンクに到着するパケット処理は、通常は、２つから４つの連想ルックアップを必要とする（すなわち、Ｌ２ＳＡ突合せ、Ｌ２学習、ユニキャスト経路クラス突合せ、Ｌ２ＤＡ突合せのうちの２つ以上）。しかし、本発明の実施形態によれば、Ｌ２学習のためにポート更新アクセスが必要なときには、Ｌ２ＤＡ突合せをなくすことができる。こうして、貴重なサイクルが節約される。Ｌ２ＤＡ突合せがなくなると、トポロジの変化が起きたときに余分なパケットを１つフラッディングすることができるが、ポート更新アクセスは比較的まれな事象である。このようにして、連想ルックアップの数が通常は最大でパケットあたり３つまでに制限され、機能性を損なわないことは有利である。
中継データベースのサーチ・スーパーサイクルのタイミング
次に、中継データベース１４０内の中継情報の新しい区分化、およびパイプライン式の中継データベースのアクセスに鑑みて、サーチ・スーパーサイクルのタイミングについて述べる。
第８Ａ図〜第８Ｃ図は、３つの最悪の場合の内容アドレス・メモリのサーチ・スーパーサイクルを示すタイミング図である。第４図に関連して述べたＣＡＭ−ＲＡＭアーキテクチャの中でデータを区分化することで、中継データベース・メモリ・アクセスをパイプライン化することが可能となる。第８Ａ図〜第８Ｃ図に関連して理解されるように、スイッチ構造は、ＣＡＭアクセス内のＲＡＭの読取りおよび書込みを隠すことによって、貴重なサイクルを節約する。例えば、ＲＡＭの読取りおよび書込みは、少なくとも部分的には、図示の各スーパーサイクルごとにより低速のＣＡＭアクセス内で隠すことができる。
次に第８Ａ図を参照すると、Ｌ２ＳＡサーチおよびＬ２ＤＡサーチを含むサーチ・スーパーサイクルが示してある。第１のＣＡＭの短いサーチは、Ｌ２学習のためのＣＡＭ４１０および４２０のＬ２ＳＡサーチを表す。Ｌ２ＳＡサーチが完了すると直ちに、次のＣＡＭの短いサーチ（Ｌ２ＤＡサーチ）が行われている間に、ＳＲＡＭ６３０中の関連データを更新する（例えばＲＡＭの読取りおよびＲＡＭの書込み）ことができる。
第８Ｂ図は、Ｌ２サーチおよびＬ３サーチが結合された場合を示している。第１のＣＡＭの短いサーチはＬ２ＳＡサーチを表す。ＣＡＭの長いサーチは、Ｌ３エントリの突合せのための中継データベース１４０のサーチを表す。この場合も、学習が必要な場合にＬ２ＳＡサーチが完了すると、それに続くＣＡＭアクセスの間にＳＲＡＭの読取りおよび書込みを実施することができる。一致するＬ３エントリが発見された場合には、Ｌ２ＤＡサーチを表す第２のＣＡＭの短いサーチの間に、その一致するエントリに対応する関連データのＲＡＭバースト読取りを実施することができる。
第８Ｃ図は、Ｌ２サーチおよびＬ３サーチが結合されたもう１つの場合を示している。ただし、この場合には、第２のＣＡＭアクセスは実施されない。
ＣＡＭおよびＳＲＡＭをパイプライン化すると、メモリの速度が効果的に切り離されることを理解されたい。さらに、１つまたは複数のＣＡＭとＳＲＡＭとが区分化されることを理解されたい。ＣＡＭアクセスはＳＲＡＭへのアクセスより低速であるので、可能な限り多くの中継情報をＳＲＡＭに割り振ることが望ましい。
ＲＡＭの書込みの完了と第２のＣＡＭのアクセスの完了の間のギャップを観察すると、１つまたは複数のＣＡＭの速度を高めることでこれらのギャップを減少させることができることは明らかである。本発明の譲受人は、将来的な技術開発を予想してより高速のＣＡＭを開発することができるようにし、それにより、例えば追加の、またはより高速のポートのための追加の資源を生成している。
第８Ａ図〜第８Ｃ図にはパイプライン式の中継データベース・アクセスしか示していないが、本発明のスイッチ構造２１０の全体的な速度に寄与する要因がその他に多く存在することに留意することは重要である。例えば、上述のように、高度にパイプライン式のスイッチ構造論理は、パイプライン式のヘッダ処理、パイプライン式の中継データベース・アクセス、およびパイプライン式の中継データベース／ヘッダ処理を含む。
一般的なコマンド処理
本発明の一実施形態を実施することができる例示的な環境について述べたが、次に一般的なコマンド処理について述べる。第９図は、本発明の一実施形態による、典型的な中継データベース・メモリ・アクセス・コマンドについての一般的なコマンド処理を示す流れ図である。ステップ９１０で、ＣＰＵは、ＰＩＯを使用して、ソフトウェア・コマンド実行ブロック３４０中の適当なデータ・レジスタをプログラムする。例えば、特定の中継データベース・アクセス・コマンドは、コマンドを発行する前にＣＰＵ１６１から供給されなければならない指定アドレスで操作可能である。
ステップ９２０で、ＣＰＵ１６１は、そのコマンドについての適当なパラメータを供給した後で、所望のコマンドを発行する。これは、所望のコマンドに対応するコマンド・コードをコマンド・レジスタに書き込むことによって実施することができる。
この実施形態によれば、ＣＰＵ１６１は、ステップ９２０で発行されたコマンドが完了するまで、状態レジスタをポーリングする（ステップ９３０）。あるいは、コマンドが所定の最大応答時間を有するので、ＣＰＵ１６１は状態レジスタをポーリングする必要はなく、ＣＰＵ１６１はその他の機能を自由に実施することができ、コマンドが完了すると予想される時点で状態レジスタを検査することができる。別の代替形態は、スイッチ構造に割込み機構を設け、要求されたコマンドが完了したときにＣＰＵ１６１に通知するものである。
ステップ９４０で、コマンドが完了した後で、ＣＰＵは１つまたは複数の結果に作用することができる。これらの結果は、例えばソフトウェア・コマンド実行ブロック３４０中のメモリ・マップ・レジスタに与えることができる。この場合には、ＣＰＵ１６１は、必要ならＰＩＯ読取りで結果を取り出すことができる。
ステップ９５０で、ＣＰＵ１６１によるコマンドの発行は、ソフトウェア・コマンド実行ブロック３４０中の論理をトリガし、例えば適当なコマンド・パラメータをロードする。これらのコマンド・パラメータは、ステップ９１０で既にＣＰＵ１６１に与えられているものと想定する。
ステップ９６０で、ソフトウェア・コマンド実行ブロック３４０は、適当な中継データベース・メモリに特有の１つまたは複数のコマンドを発行し、要求されたタスクを実施する。このようにして、ＣＰＵ１６１は、中継データベース１４０を実装するために使用される特定の１つまたは複数のメモリの基礎をなす生の命令セットについての知識を必要としない。
ステップ９７０で、中継データベース１４０のアクセスが完了した後で、ソフトウェア・コマンド実行ブロック３４０は、適当なインタフェース・レジスタ中の１つまたは複数の結果を更新する。次いで、ステップ９８０で、ソフトウェア・コマンド実行ブロック３４０は、そのコマンドが完了したことをＣＰＵ１６１に対して示すように、１つまたは複数のコマンド状態フラグをセットする。その他の実施形態では、１つまたは複数の追加状態フラグを設け、コマンドがうまく完了したか否か、エラーが発生したか否か、および／またはＣＰＵ１６１に有用となりうるその他の情報を示すことができる。
一般的なコマンド処理の流れについて述べたが、例示的なコマンドのセットおよびその使用方法について次に述べる。
例示的なコマンドのセット
この実施形態によれば、中継データベース１４０中のエントリにアクセスするために１つまたは複数のコマンドが準備されている。特に、新しく学習された層２（Ｌ２）エントリを読み取ることは有用である。Ｌ２エントリを取り出すために、ＣＰＵ１６１は最初に、中継データベース・メモリ１４０をアドレッシングするように、スイッチ構造２１０中のカウンタをプログラムする。その後、ＣＰＵ１６１は、スイッチ構造２１０中のコマンド・レジスタにＲｅａｄ＿ＣＡＭ＿Ｅｎｔｒｙコマンドを書き込む。ＣＰＵがスイッチ構造にサービスされる番になると、スイッチ構造はカウンタを読み取り、中継データベース・メモリ１４０へのアクセスを実施し、新しく学習されたＬ２エントリを取り出す。スイッチ構造２１０は、次いで、ＣＰＵ１６１がアクセスできる出力レジスタにＬ２エントリを書き込み、コマンド状態終了フラグ（command status done flag）をセットする。コマンドが完了した後で、コマンドが成功したものと仮定すると、ＣＰＵ１６１は出力レジスタからＬ２エントリを読み取ることができる。
Ｒｅａｄ＿ＣＡＭ＿Ｅｎｔｒｙコマンドをアドレス・カウンタ・レジスタと組み合わせると、例えば、中継データベース全体のソフトウェアのイメージを更新と関連するバースト読取りに特に有用である。各メモリ・アクセスが完了するたびにハードウェアが自動的にアドレス・カウンタ・レジスタを増分することになるので、ソフトウェアは、最初のメモリ・アクセスの前にアドレス・レジスタをプログラムしさえすればよい。このようにして、ソフトウェアは、極めて効率的に中継データベース１４０全体を読み取ることができる。同様に、Ｌ３エントリの初期化中の書込みシーケンスなど、その他の中継メモリ・アクセスも簡略化されることは明らかであろう。次に、中継データベース・メモリ１４０にエントリを書き込む機構について述べる。
ＣＰＵ１６１が中継データベース・メモリにエントリを書き込むことができることも好都合である。特に、所定の充てん文字（またはダミー）の値で中継データベース中の全てのＬ３エントリを初期化することは有用となることがある。このコマンドは、例えば、Ｌ３エントリを無効にする、またはマスク・パー・ビット（ＭＰＢ）内容アドレス・メモリ（ＣＡＭ）中のマスクの更新を事前実施（before perform）するためにも有用となることがある。この目的のために、Ｗｒｉｔｅ＿ＣＡＭ＿Ｅｎｔｒｙコマンドが用意されている。この場合も、ＣＰＵ１６１は、最初にスイッチ構造２１０中の適当なカウンタをプログラムするものとする。ＣＰＵ１６１は、中継データベース・メモリ１４０に書き込むべきＬ３キーも用意する。これらのステップの後で、ＣＰＵ１６１は、ＰＩＯ書込みを使用して、Ｗｒｉｔｅ＿ＣＡＭ＿Ｅｎｔｒｙコマンドをコマンド・レジスタに発行することができる。その後、ＣＰＵ１６１はコマンド状態のポーリングを開始することができる。スイッチ構造２１０は、ＣＰＵ１６１から与えられたパラメータを読み取り、対応するＬ３エントリを所定の充てん文字（またはダミー）に初期化する。書込みが完了した後で、スイッチ構造２１０は、コマンド状態終了フラグをセットすることによってコマンドの状態をＣＰＵ１６１に通知する。
関連データにアクセスするためのコマンドも用意されている。本発明の一実施形態によれば、（１）供給されたアドレスを学習する、（２）供給されたサーチ・キーに対応する関連データを読み取る、（３）中継データベースのエントリをエージングする、（４）エントリを無効にする、（５）ＭＰＢ ＣＡＭに記憶することができる、特定のサーチ・キーに対応するマスク・データなどのマスク・データにアクセスする、（６）中継データベースのエントリを置換する、といった動作が行われる。
Ｌ２出所アドレスの学習は、Ｌｅａｒｎ＿Ｌ２＿ＳＡコマンドによって実施することができる。最初に、ＣＰＵ１６１は、Ｌ２サーチ・キーと、挿入する新しいエントリまたは修正したエントリとを、スイッチ構造２１０中の適当なレジスタにプログラムする。次いで、ＣＰＵ１６１は、Ｌｅａｒｎ＿Ｌ２＿ＳＡコマンドを発行し、コマンド状態のポーリングを開始する。スイッチ構造２１０は、ＣＰＵ１６１から与えられたデータを読み取る。供給されたアドレスと一致するエントリが中継データベース１４０中で発見されない場合には、新しいエントリが中継データベース中に挿入される。挿入が完了した後、または一致するエントリが既に存在していることが確認された後で、スイッチ構造２１０は、コマンド状態終了フラグをセットすることによってコマンドの状態をＣＰＵ１６１に通知する。
ＣＰＵ１６１がエージングを実施することができることも好都合である。特に、Ｌ２およびＬ３の中継データベースのエントリをエージングすることは有用である。この目的のために、Ａｇｅ＿ＳＡコマンドおよびＡｇｅ＿ＤＡコマンドがある。ＣＰＵ１６１は、適当なキーおよび修正したエージ・フィールドをスイッチ構造インタフェースに書き込む。次いで、ＣＰＵ１６１は、Ａｇｅ＿ＳＡコマンドまたはＡｇｅ＿ＤＡコマンドを発行する。Ａｇｅ＿ＳＡコマンドは、与えられたサーチ・キーに対応するＬ２エントリ中に出所アドレス・エージ・フィールドをセットする。Ａｇｅ＿ＤＡコマンドは、与えられたサーチ・キーに対応するＬ２またはＬ３のエントリについての宛先アドレス・エージ・フィールドをセットする。コマンドを発行した後で、ＣＰＵ１６１はコマンド状態のポーリングを開始することができる。スイッチ構造２１０は、ＣＰＵ１６１から与えられたデータを読み取り、一致するエントリ中の適当なエージ・フィールドを更新する。エージングが完了した後で、スイッチ構造２１０は、コマンド状態終了フラグをセットすることによってコマンドの状態をＣＰＵ１６１に通知する。
ＣＰＵ１６１は、例えばエージング済みのＬ２エントリなど、中継データベースのエントリを無効にする能力を有する必要がある。この目的のために、Ｉｎｖａｌｉｄａｔｅ＿Ｌ２＿Ｅｎｔｒｙコマンドがある。Ｉｎｖａｌｉｄａｔｅ＿Ｌ２＿Ｅｎｔｒｙコマンドを発行する前に、ＣＰＵ１６１は、スイッチ構造２１０中の適当なアドレス・カウンタをプログラムする。コマンドを発行した後で、ＣＰＵ１６１は、コマンド状態のポーリングを開始することができる。スイッチ構造２１０は、ＣＰＵ１６１から与えられたデータを読み取り、指定されたアドレス・カウンタのロケーションで妥当性ビットをリセットする。エントリの無効化が完了した後で、スイッチ構造２１０は、コマンド状態終了フラグをセットすることによってコマンドの状態をＣＰＵ１６１に通知する。
ＭＰＢ ＣＡＭを利用する実施形態では、通常は、ＣＡＭは交互に現れるデータとマスクのセットを記憶する。データの各セットは、対応するマスクを有する。マスクは、対応するＣＡＭのラインからデータの各部分をプログラマブルに選択できるようにする。したがって、ＣＰＵ１６１が、ＣＡＭ中の特定のアドレスに対応するマスク・データにアクセスすることができることは好都合である。特に、特定のＣＡＭのラインの様々な部分を選択するためにマスク・データを更新することは有用である。この目的のために、Ｕｐｄａｔｅ＿Ｍａｓｋコマンドがある。ＣＰＵ１６１は、アドレス・カウンタ・レジスタをプログラムし、新しいマスクを適当なレジスタ中にプログラムする。次いで、ＣＰＵ１６１は、Ｕｐｄａｔｅ＿Ｍａｓｋコマンドを発行し、コマンド状態のポーリングを開始することができる。スイッチ構造２１０は、ＣＰＵ１６１から与えられたパラメータを読み取り、指定されたアドレスに対応するマスク・データを更新する。マスク・データの更新が完了した後で、スイッチ構造２１０は、コマンド状態終了フラグをセットすることによってコマンドの状態をＣＰＵ１６１に通知する。ＣＰＵ１６１は、Ｒｅａｄ＿Ｍａｓｋコマンドを利用し、適当なアドレスを与えることによっても同様にマスク・データを読み取ることができる。
最後に、エントリを置換できることが望ましい。特に、充てん文字（またはダミー）のＬ３エントリを新しい有効なＬ３エントリで置換することは有用である。この目的のために、Ｒｅｐｌａｃｅ＿Ｌ３コマンドがある。ＣＰＵ１６１は、Ｌ３サーチ・キーをスイッチ構造２１０に与え、新しい有効なＬ３エントリを与える。次いで、ＣＰＵ１６１は、Ｒｅｐｌａｃｅ＿Ｌ３コマンドを発行し、コマンド状態のポーリングを開始することができる。スイッチ構造２１０は、ＣＰＵ１６１から与えられたパラメータを読み取り、一致するＬ３エントリを求めて中継データベース１４０のサーチを実施する。一致するＬ３エントリを突き止めた後で、一致するエントリに対応する関連データは、ＣＰＵ１６１から与えられた新しい有効なＬ３エントリで置換される。Ｌ３エントリが置換された後で、スイッチ構造２１０は、コマンド状態終了フラグをセットすることによってコマンドの状態をＣＰＵ１６１に通知する。
重要なこととして、特定のコマンド、および特定のコマンドを実行するための詳細なステップに関連して本発明の実施形態について述べたが、本発明はいかなる特定のコマンドのセットまたは実行のシーケンスにも限定されないことを当業者なら理解するであろう。
前述の説明では、特定の実施形態に関連して本発明について述べた。しかし、本発明のより広範な趣旨および範囲を逸脱することなく、様々な修正および変更をこれらに加えることができることは明らかであろう。例えば、本発明の実施形態は、ＩＰなど特定のネットワーク・プロトコルに関連して述べたものである。しかし、本明細書に記載の方法および装置は、その他のタイプのネットワーク・プロトコルにも等しく適用することができる。したがって、この明細書および図面は、限定的ではなく例示的な意味合いのものであると見なされたい。

Claims (23)

1. 中継データベース・メモリ（１４０）へのアクセスを調停するように構成されたメモリ・アクセス・インタフェース（３１０）と、
   メモリ・アクセス・インタフェースに結合され、中継データベース・メモリへのアクセスをスケジュールして実施し、そこから取り出した中継決定を複数の入力ポートに送るように構成されたサーチ・エンジン（３７０）と、
   プロセッサ（１６１）に代わって中継データベースのアクセスを実施するために、このプロセッサとのインタフェースをとるように構成されたコマンド実行論理とを含み、
   前記中継データベースのアクセスは、前記中継データベース・メモリの特定の実行に関連している装置に依存した動作のセットからの動作を含み、
   前記コマンド実行論理は、前記メモリ・アクセス・インタフェースと前記プロセッサ間に結合され、前記中継データベース・メモリの特定の実行から独立している所定のコマンドのセットをサポートし、前記プロセッサによる、前記所定のコマンドのセットからのコマンドの発行に応答して装置に依存した動作のセットの１つ以上の動作を実施する、スイッチ構造（２１０）。
2. コマンド実行論理が、所定のコマンドのセットに応答する論理をさらに含む請求項１に記載のスイッチ構造。
3. 所定のコマンドのセットが、中継データベース・メモリからサーチ・キーを読み取るコマンドを含む請求項２に記載のスイッチ構造。
4. 所定のコマンドのセットが、中継データベース・メモリにサーチ・キーを書き込むコマンドを含む請求項２に記載のスイッチ構造。
5. 所定のコマンドのセットが、供給されたサーチ・キーに対応する中継データベース・メモリからデータを読み取るコマンドを含む請求項２に記載のスイッチ構造。
6. 所定のコマンドのセットが、供給されたアドレスの学習を実施するコマンドを含み、供給されたアドレスに一致するエントリが中継メモリ・データベース中で発見されない場合に、新しいエントリが挿入されることになる請求項２に記載のスイッチ構造。
7. 所定のコマンドのセットが、第１のタイプの中継データベース・メモリのエントリをエージングするコマンドを含む請求項２に記載のスイッチ構造。
8. 所定のコマンドのセットが、第２のタイプの中継データベースのエントリをエージングするコマンドを含む請求項２に記載のスイッチ構造。
9. 所定のコマンドのセットが、アクティブなエントリを無効にするコマンドを含む請求項２に記載のスイッチ構造。
10. 所定のコマンドのセットが、特定のサーチ・キーに対応するマスク・データを更新するコマンドを含む請求項２に記載のスイッチ構造。
11. 所定のコマンドのセットが、特定のサーチ・キーに対応するマスク・データを読み取るコマンドを含む請求項２に記載のスイッチ構造。
12. 所定のコマンドのセットが、エントリを置換するコマンドを含む請求項２に記載のスイッチ構造。
13. プロセッサ（１６１）との間でデータを通信するバス・インタフェースと、
    そのバス・インタフェースに結合され、中継データベース・メモリへのハードウェアの支援によるプロセッサ・アクセスを行うように構成されたスイッチ構造（２１０）とを含むネットワーク・デバイスであって、
    前記スイッチ構造は、
    中継データベース・メモリへのアクセスを調停するように構成されたメモリ・アクセス・インタフェース（３１０）と、
    メモリ・アクセス・インタフェースに結合され、中継データベース・メモリへのアクセスをスケジュールして実施し、そこから取り出した中継決定を複数の入力ポートに送るように構成されたサーチ・エンジン（３７０）と、
    前記メモリ・アクセス・インタフェースと前記プロセッサ間に結合されたコマンド実行論理であって、プロセッサに代わって中継データベース・メモリ・アクセスを提供する所定のコマンドのセットをサポートするように構成され、１つ以上のプログラム可能な入力レジスタと１つ以上の出力レジスタから成っているインタフェース・メモリを含むコマンド実行論理とを含み、
    前記１つ以上のプログラム可能な入力レジスタは、前記プロセッサから前記所定のコマンドのセットのコマンドとこのコマンドに関連したデータとを受け取るためのものであり、
    前記１つ以上のプログラム可能な出力レジスタは、前記プロセッサが中継データベース・メモリ・アクセスの結果と中継データベース・メモリ・アクセス状況とを読み取ることができるようにしてなる、ネットワーク・デバイス。
14. 所定のコマンドのセットが、中継データベース・メモリにサーチ・キーを書き込むコマンドを含む請求項１３に記載のネットワーク・デバイス。
15. 所定のコマンドのセットが、供給されたサーチ・キーに対応する中継データベース・メモリからデータを読み取るコマンドを含む請求項１３に記載のネットワーク・デバイス。
16. 所定のコマンドのセットが、供給されたアドレスの学習を実施するコマンドを含み、供給されたアドレスに一致するエントリが中継メモリ・データベース中で発見されない場合に、新しいエントリが挿入されることになる請求項１３に記載のネットワーク・デバイス。
17. 所定のコマンドのセットが、第１のタイプの中継データベース・メモリのエントリをエージングするコマンドを含む請求項１３に記載のネットワーク・デバイス。
18. 所定のコマンドのセットが、第２のタイプの中継データベースのエントリをエージングするコマンドを含む請求項１３に記載のネットワーク・デバイス。
19. 所定のコマンドのセットが、アクティブなエントリを無効にするコマンドを含む請求項１３に記載のネットワーク・デバイス。
20. 所定のコマンドのセットが、特定のサーチ・キーに対応するマスク・データを更新するコマンドを含む請求項１３に記載のネットワーク・デバイス。
21. 所定のコマンドのセットが、特定のサーチ・キーに対応するマスク・データを読み取るコマンドを含む請求項１３に記載のネットワーク・デバイス。
22. 所定のコマンドのセットが、エントリを置換するコマンドを含む請求項１３に記載のネットワーク・デバイス。
23. 中央処理装置（ＣＰＵ）の、ネットワーク・デバイスの中継データベース・メモリへのアクセスを実現する方法であって、
    中継データベース・メモリにアクセスするための複数のコマンドを提供するステップと、
    複数のコマンドのうち保留のコマンドの状態を示す状態指示を提供するステップと、
    複数のコマンドのうちの１つのコマンドをその中に記憶しているデータベース・アクセス要求を中央処理装置（ＣＰＵ）から受け取るステップと、
    データベース・アクセス要求に応答して、中継データベース・メモリへのアクセスを実施するステップと、
    データベース・アクセス要求が完了していることをＣＰＵに通知する状態指示をセットするステップとを含む方法。

Images