【手続補正書】
【提出日】平成16年10月6日(2004.10.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
サーチ・キーからのＮビット（Ｎは整数）を、少なくとも１つのエントリを持つダイレクト・テーブルおよび前記１つのエントリに動作可能なように結合された複数のノードを含むツリー構造を含むデータ構造への指標として使用する動作と、
前記ツリー構造をサーチするときに横断されるノード数のカウントである閾値を設定する動作と、
前記サーチ・キーからの選択ビットを使用して前記閾値が満たされるまで前記ツリー構造を横断する動作と、
前記閾値が満たされたことに応答して、前記サーチ・キーに関連して講ずべき処置を得るために連想記憶メモリ（ＣＡＭ）内の少なくとも１つのエントリから情報を読み取る動作と、
エントリが所与の期間使用されていないときに前記ＣＡＭからそのエントリを削除する動作と
を含むサーチ方法。
【請求項２】
前記閾値が満たされたことに応答して、前記サーチ・キーの選択ビット、および前記キーに関連して講ずべき処置をそこから見つけることのできる情報を含む少なくとも１つのエントリを連想記憶メモリに記憶するステップをさらに含む請求項１に記載の方法。
【請求項３】
Ｎビットが宛先ＭＡＣアドレスの最初の１６ビットを含む請求項１または２に記載の方法。
【請求項４】
リーフが選択されたノードに動作可能なように結合され、
リーフが前記所与の期間よりも長い期間使用されていないときに前記ツリーからそのリーフを削除するステップ
をさらに含む、請求項１または請求項２に記載の方法。
【請求項５】
前記情報が、前記処置が記憶された前記ツリー構造のリーフのアドレスを含む請求項１に記載の方法。
【請求項６】
複数のプロトコル・プロセッサを含む組み込みプロセッサ複合体と、
前記プロセッサ複合体に動作可能なように結合された制御点プロセッサと、
各プロトコル・プロセッサにアクセス可能であり、高速パターン・サーチ、データ操作およびフレーム構文解析を提供する複数のハードウェア・アクセラレータ・コプロセッサと、
ダイレクト・テーブル、および相互に動作可能なように連鎖するノードおよびリーフを持つツリー構造を含むデータ構造を記憶する、前記プロセッサ複合体に動作可能なように結合された少なくとも１つのメモリ・デバイスと、
前記プロセッサ複合体に動作可能なように結合され、ツリー・サーチ・ルーチンの間にアクセスされるノードの最大数を表す値を記憶するメモリ位置と、
前記プロセッサ複合体に動作可能なように結合され、パケットに関連して講ずべき処置に関する情報を含むリーフが記憶された場所を識別するポインタを記憶する連想記憶メモリ（ＣＡＭ）と
を含み、少なくとも１つのコプロセッサが、
サーチ・キーからのＮビット（Ｎは整数）を、ダイレクト・テーブルを含む前記データ構造への指標として使用する方法ステップと、
前記サーチ・キーからの選択ビットを使用して、アクセスされるノードの最大数が満たされるまで前記ツリー構造を横断する方法ステップと、
前記サーチ・キーの選択ビットを含む少なくとも１つのエントリ、およびパケットに関連して講ずべき処置に関する情報を含むリーフが記憶された位置を識別するポインタを前記ＣＡＭに記憶する方法ステップと、
前記サーチ・キーに関連して講ずべき処置を得るために前記ＣＡＭ内の少なくとも１つのエントリから情報を読み取る方法ステップと、
エントリが所与の期間使用されていないときにそのエントリを前記ＣＡＭから削除する方法ステップと
を実施するように動作する装置。
【請求項７】
前記ＣＡＭが、前記ポインタと対をなす、前記パケット内の宛先ＭＡＣアドレスの選択された一部をさらに含む請求項６に記載の装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【発明の名称】ネットワーク・プロセッサおよびコンピュータ・システム用ハイブリッド・サーチ・メモリ
【技術分野】
【０００１】
本発明は、コンピュータ・データベース構造に関し、より詳細には、ネットワーク・プロセッサ・データベース構造に関する。
【背景技術】
【０００２】
情報配布のためのコンピュータ・ネットワークの使用は、従来技術において周知である。従来のコンピュータ・ネットワークは、通信インフラストラクチャによって相互接続された複数の端末を含む。このインフラストラクチャには、交換機、ルータ、ネットワーク・プロセッサおよびインターネットや、イントラネットと呼ばれる専用ネットワークなどの伝送設備が含まれる。経路指定その他の決定は、通常、パケット内の情報に基づいて交換機で行われる。
【０００３】
この決定を支援するために、各ネットワーク・プロセッサ交換機その他のデバイス（device）はデータベースおよび検索（lookup）方法を備える。パケットを受信すると、交換機またはネットワーク・プロセッサ制御機構あるいはその両方が、そのパケットをデータベースに相関付け、事前に記憶された情報に基づいてそのパケットを処理する。データベース検索方法の一例が米国特許第５，４１４，７０４号に記載されている。
【０００４】
この決定が行われる速度は、ネットワークの有効性にとって非常に重大である。ネットワークの有効性を測定する１つの基準は、それが媒体速度で情報を処理する（すなわち決定を行う）能力である。
【特許文献１】米国特許第５，４１４，７０４号
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、以下で述べるように、制御機構がパケットをデータベースに相関付ける速度を向上させる。
【課題を解決するための手段】
【０００６】
米国特許第５，４１４，７０４号には、プログラム可能ハッシュ法、二分探索法、および小型連想記憶メモリ（ＣＡＭ）の組み合わせを使用するデータベースのサーチ方法が開示されている。これは、平均２回の読取り、最悪の場合は４回の読取りを必要とする。
【０００７】
第１の態様によれば、本発明は、サーチ・キーからのＮビット（Ｎは整数）を、少なくとも１つのエントリを持つダイレクト・テーブルおよび前記１つのエントリに動作可能なように結合された複数のノードを含むツリー構造を含むデータ構造への指標として使用する動作と、そのツリー構造をサーチするときに横断されるノード数のカウントである閾値を設定する動作と、サーチ・キーからの選択ビットを使用して閾値が満たされるまで前記ツリー構造を横断する動作と、閾値が満たされたことに応答して、そのサーチ・キーに関連して講ずべき処置を得るために連想記憶メモリ（ＣＡＭ）内の少なくとも１つのエントリから情報を読み取る動作と、エントリが所与の期間使用されていないときにＣＡＭからそのエントリを削除する動作とを含むサーチ方法を提供する。
【０００８】
好ましくは、この方法は、閾値が満たされたことに応答して、サーチ・キーの選択ビット、およびそのキーに関連して講ずべき処置をそこから見つけることのできる情報を含む少なくとも１つのエントリを、連想記憶メモリに記憶するステップも含む。
【０００９】
好ましくは、このツリー構造は、選択されたノードに動作可能なように結合された複数のノードおよびリーフを含む。好ましくは、このツリー構造は、選択されたノードに位置決めされた、サーチ情報を運ぶパターン・サーチ制御ブロック（ＰＳＣＢ）をさらに含む。
【００１０】
例えば、Ｎビットは、宛先ＭＡＣアドレスの先頭１６ビットを含むことができ、さらに選択ビットは、その宛先ＭＡＣアドレスの残り３２ビットを含むことができる。
【００１１】
任意選択で、サーチ・キーは、データ・パケットの一部を含む。
【００１２】
任意選択で、読み取りのステップは、ＮビットをＣＡＭへの指標として使用するステップをさらに含む。
【００１３】
第２の態様によれば、本発明は、複数のプロトコル・プロセッサを含む組み込みプロセッサ複合体と、プロセッサ複合体に動作可能なように結合された制御点プロセッサと、各プロトコル・プロセッサにアクセス可能であり、高速パターン・サーチ、データ操作およびフレーム構文解析を提供する複数のハードウェア・アクセラレータ・コプロセッサと、ダイレクト・テーブル、および相互に動作可能なように連鎖するノードおよびリーフを持つツリー構造を含むデータ構造を記憶する、プロセッサ複合体に動作可能なように結合された少なくとも１つのメモリ・デバイスと、プロセッサ複合体に動作可能なように結合され、ツリー・サーチ・ルーチンの間にアクセスされるノードの最大数を表す値を記憶するメモリ位置と、プロセッサ複合体に動作可能なように結合され、パケットに関連して講ずべき処置に関する情報を含むリーフが記憶された位置を識別するポインタを記憶する連想記憶メモリ（ＣＡＭ）とを含み、少なくとも１つのコプロセッサが、サーチ・キーからのＮビット（Ｎは整数）を、ダイレクト・テーブルを含むデータ構造への指標として使用する方法ステップと、そのサーチ・キーからの選択ビットを使用してアクセスされるノードの最大数が満たされるまで前記ツリー構造を横断する方法ステップと、サーチ・キーの選択ビットを含む少なくとも１つのエントリ、およびパケットに関連して講ずべき処置に関する情報を含むリーフが記憶された位置を識別するポインタをＣＡＭに記憶する方法ステップと、サーチ・キーに関連して講ずべき処置を得るためにＣＡＭ内の少なくとも１つのエントリから情報を読み取る方法ステップと、エントリが所与の期間使用されていないときにそれをＣＡＭから削除する方法ステップとを実施するように動作する装置を提供する。
【００１４】
任意選択で、この装置は、プロセッサ複合体に動作可能なように結合され、ツリー・サーチ・ルーチンの間にアクセスされるノードの最大数を表す値を記憶するメモリ位置と、プロセッサ複合体に動作可能なように結合され、リーフが記憶された位置を識別するポインタを記憶する連想記憶メモリ（ＣＡＭ）とをさらに含む。
【００１５】
好ましくは、制御点プロセッサは、データ構造を調整する情報を含むフレームを生成し、転送するようにプログラムされる。
【００１６】
第３の態様によれば、本発明は、少なくとも２つのエントリを持つダイレクト・テーブルと、それら少なくとも２つのエントリに動作可能なように結合され、相互に動作可能なように連鎖する複数のノードおよびリーフを持つツリー構造と、前記ツリー構造の探索（walk）中にアクセスされるノードの最大数を示す閾値を記憶する記憶と含むデータ構造を提供する。
【００１７】
好ましくは、このデータ構造は、リーフが閾値の上のノードに接続されている場合にはそのリーフ情報が記憶された連想記憶メモリ（ＣＡＭ）をさらに含む。
【００１８】
本発明の一実施形態は、例えば、データ・パケットから取り出されたキーを提供するプロセッサと、そのキーを使用して、閾値に達するまでツリー構造を探索するためのツリー・ウォーク論理（tree walk logic）と、そのキーを使用してＣＡＭをサーチするＣＡＭ制御機構と、ツリー・ウォーク論理またはＣＡＭ制御機構からの最初の使用可能な結果を使用してそのデータ・パケットに関連して講ずべき処置を決定する制御機構とを含むシステムを提供することができるであろう。
【００１９】
本発明の別の実施形態は、例えば、データ・パケットから取り出されたキーを提供する動作と、前記キーをツリー・ウォーク論理で使用して閾値に達するまでツリー構造をサーチする動作と、前記キーをＣＡＭ制御機構で使用してＣＡＭをサーチする動作と、動作（ｂ）または（ｃ）からの最初の結果を使用してデータ・パケットに関連して講ずべき処置を決定する動作とを含むサーチ方法を提供することができるであろう。
【００２０】
したがって、本発明は、ダイレクト・テーブル（ＤＴ）、パトリシア・ツリー構造および連想記憶メモリ（ＣＡＭ）を含むメモリ構造を使用してデータベース情報を記憶する。このメモリ構造およびサーチ方法は、パケットをネットワーク・プロセッサ内のデータベースに相関付けることに伴う待ち時間を短縮する。
【００２１】
好ましくは、データベース構造は、複数のエントリに区分されたダイレクト・テーブル（ＤＴ）を含む。各エントリは、「パターン・サーチ制御ブロック（ＰＳＣＢ）」と呼ばれる、リーフおよび複数のノードを持つパトリシア・ツリーに関連付けられる。パケットの一部に関連して講ずべき処置は、ＤＴ内のエントリに合致する「キー」と呼ばれ、そのリーフに記述される。リーフに到達するには、ツリーを探索する必要がある（以下で詳細を述べる）。
【００２２】
一般に、待ち時間は、ＤＴ内のエントリとリーフとを隔てるＰＳＣＢの数によって決定される。ＰＳＣＢの数が大きいほど、そのリーフ内の情報にアクセスするのにかかる時間が長くなり、ＰＳＣＢの数が少ないほど、情報がより迅速に得られる。ツリーのリーフに向かって各ノードにアクセスするプロセスは、「ツリー・ウォーク」、「ツリーの探索（ウォーキング）」などと呼ばれる。
【００２３】
任意選択で、１つのテーブル・エントリと関連するリーフの間で横断されるＰＳＣＢの数を制限する閾値が設定される。その後、ＣＡＭは、フレームに関連して講ずべき処置を含むリーフが位置するアドレスを記憶する。リーフにアクセスすることによって、フレームに関連して講ずべき処置が得られる。
【００２４】
データ構造は、ツリーのリーフを付加し、または削除し、あるいはその両方を行うことによって維持することができる。この付加または削除あるいはその両方によってＰＳＣＢの数を増減させることができる。データベース調整を補うために、ＣＡＭ経時処理機構（CAM aging mechanism）によってＣＡＭに適当な削除または付加あるいはその両方が行われる。
【００２５】
本発明の一利点は、本発明の教示によるブースタＣＡＭまたは閾値あるいはその両方を援用することによって、メモリ・ベースの検索論理システムの待ち時間が制限される（短縮される）ことである。例えば、この閾値は、個々のサーチの間に横断することのできるＰＳＣＢの数に限度を設定する。
【００２６】
別の利点は、ＣＡＭを使用して選択されたリーフに関連する情報を追跡し、それ以外のリーフには（以下で述べる）通常の「ツリー・ウォーク」によってアクセスする場合、大規模なパトリシア・ツリーをより低コストで実装できることである。
【００２７】
本発明の別の利点は、本発明が、データ構造内で大規模なパトリシア・ツリーを実装するための、比較的低コストで待ち時間の短い解決法を提供することである。本発明以前には、大規模なパトリシア・ツリー・データ構造のサーチに伴う長い待ち時間が原因で、ある種の設計では大規模パトリシア・ツリー・データ構造が許容されなかった。
【００２８】
次に本発明を、一例として、添付の図面に示す本発明の好ましい一実施形態を参照して説明する。
【発明を実施するための最良の形態】
【００２９】
本明細書で説明する本発明は、任意ｎコンピュータ・データベース・システムで使用することができる。本発明は、ネットワーク・プロセッサ（ＮＰ）で適切に働き、したがって、以下ではその環境で説明する。
【００３０】
図１に、本発明の好ましい実施形態によるブースタＣＡＭシステム１５を含むネットワーク・プロセッサのアーキテクチャを示す。ブースタＣＡＭシステム１５は、通信媒体１５ａによって組み込みプロセッサ複合体（ＥＰＣ）１２に結合される。単一チップとしても複数のチップとしても実装できるこのネットワーク・プロセッサは、イーサネット（Ｒ）・パケットやＩＰ  ｏｖｅｒ  ＳＯＮＥＴ（ＰＯＳ）を含む物理層デバイス２６、ＰＭＭ入り（PMM-Ingress）多重化ＭＡＣ２２、および入りデータ記憶４２および入りスイッチ・インターフェース１８を含むエンキュー・デキュー・スケジューリング（ＥＤＳ）１４を含む。出口側では、このネットワーク・プロセッサは、出スイッチ・インターフェース２０、エンキュー・デキュー・スケジューリング１６、および出データ記憶４４を含む。
【００３１】
さらに図１を参照すると、組み込みプロセッサ複合体（ＥＰＣ）１２は、通信媒体を介して入りＥＤＳおよび出ＥＤＳに結合される。組み込みプロセッサ複合体には、内蔵Ｓ−ＲＡＭ２８、Ｄ−ＲＡＭ３２および外付けＳ−ＲＡＭ３０を含む複数の異なる記憶モジュールが接続される。組み込みプロセッサ複合体には組み込みＰＣプロセッサ３４が結合される。ＰＣＩバスは外部から組み込みプロセッサ３４へのアクセスを提供する。図１ではプロセッサ３４は組み込まれるものとして示されているが、代替の好ましい一実施形態として、このプロセッサが外付けとして提供され、物理層デバイスを介してネットワーク・プロセッサに結合されるものもある。以下で説明するように、本発明のデータ構造は、ＰｏｗｅｒＰＣ３４で生成され、記憶モジュールにダウンロードされる。簡略にするために、以下では、本発明に密接に関連するネットワーク・プロセッサの要素および機能だけを説明する。このネットワーク・プロセッサは、特にイーサネット（Ｒ）・パケットまたはＩＰ  ｏｖｅｒ  ＳＯＮＥＴあるいはその両方に対応するプログラム可能な交換／経路指定システムであると言えば十分であろう。ＰｏｗｅｒＰＣ３４は、以下では制御点（ＣＰ）と呼ばれ、図１に示すように組み込むこともでき、代替の実施形態では、外付けで、物理層デバイス２６また制御および管理支援を提供する他の適当な機構を介してプロセッサに接続することもできる。この組み込みプロセッサ複合体は、処理能力を提供する複数の並列プロトコル・プロセッサを含む。各プロトコル・プロセッサは、パターン・サーチ、データ操作、内部データ管理、フレーム構文解析、フィルタリング機能のためのデータ事前取り出しを提供するコプロセッサにアクセスすることができる。
【００３２】
本発明は、具体的には、ネットワーク・プロセッサのフィルタリング機能に関連し、以下では、このフィルタリングまたは分類プロセスで使用されるデバイスだけについて説明する。これらのデバイスには、コプロセッサを備える組み込みプロセッサ複合体、外付けまたは組み込みで提供される汎用プロセッサであるＣＰ３４、ブースタＣＡＭシステム１５、および本発明と密接に関連するデータ・パターンが記憶されるメモリが含まれる。以下でより詳細に説明するように、コプロセッサは、パケットの各部分を、ネットワーク・プロセッサ・メモリに記憶されたデータ構造に相関付け、そのパケットに関連して講ずべき処置を記述する情報を取り出す。ブースタＣＡＭシステムは、メモリからこの決定が取り出される速度を加速する。
【００３３】
図２に、組み込みプロセッサ複合体の例示的一実施形態を示す。これは、約２１２８ＭＩＰＳの副次処理能力を提供する複数のプロトコル・プロセッサを含む。各プロトコル・プロセッサ４０は、３段階パイプライン（取り出し、復号化および実行）汎用レジスタ、専用レジスタ、８命令キャッシュ（eight instruction cache）、専用算術論理演算装置（ＡＬＵ）およびすべてが１３３ＭＨｚで動作するコプロセッサを含む。プロトコル・プロセッサのうち少なくとも２つは専用である。１つは、誘導フレーム（guidedframe）・ハンドラと呼ばれ、制御プロセッサからネットワーク・プロセッサ内の他のエンティティに情報を搬送する誘導フレームを処理するためのものであり、１つは、汎用ツリー・ハンドラと呼ばれ、制御されたメモリ内で検索データを構築すると共に、パケットに関連してどの処置を講ずべきか決定するためにそのメモリをサーチするためのものである。
【００３４】
図３に、プロトコル・プロセッサ４０の例示的一実施形態を示す。プロトコル・プロセッサ４０は、汎用レジスタ（ＧＰＲ）および算術論理演算装置（ＡＬＵ）を備えるＣＬＰ（コア言語プロセッサ（core language processor））７２を含む。チェックサム・コプロセッサ６２、データ・ストア（ＤＳ）コプロセッサ６４、エンキュー・コプロセッサ６６、ＷＥＢコプロセッサ６８およびツリー・サーチ・エンジン（ＴＳＥ）コプロセッサ７０は独立のバスを介してＣＬＰに結合される。
【００３５】
チェックサム・コプロセッサ６２はヘッダ・チェックサムを計算する。
【００３６】
データ・ストア（ＤＳ）コプロセッサ６４は、フレーム・バッファ・メモリ４２、４４（入り方向および出方向）をインターフェースして直接メモリ・アクセス（ＤＭＡ）機能を提供する。
【００３７】
エンキュー・コプロセッサ６６は、２５６ビット作業レジスタへのアクセスを制御し、キー・フレーム・パラメータを含む。このコプロセッサは完了ユニット４６（図１および図２）とのインターフェースを提供してフレームをスイッチおよび宛先ポート待ち行列に入れる。
【００３８】
ＷＥＢコプロセッサは、内部レジスタ、カウンタおよびデバッガ統計収集用メモリへのすべてのプロトコル・プロセッサ・アクセスを提供する。
【００３９】
ツリー・サーチ・エンジン（ＴＳＥ）コプロセッサ７０は、プロトコル・プロセッサと並列に動作し、（メモリＲＥＡＤ、ＷＲＩＴＥ、ＲＥＡＤ／ＷＲＩＴＥを含む）ツリー・サーチ命令、メモリ範囲チェックを実施する。また、ＴＳＥコプロセッサは、パトリシア・ツリー構造に記憶されたデータベースに対してパケットのサーチを行うと共に、本発明の教示によるブースタＣＡＭへのアクセスも行う。代替の一実施形態では、論理を使用してＣＡＭ内の情報のコピーまたはそこからの情報の削除、あるいはその両方を行うこともできる。
【００４０】
図１および図２に戻ると、図示のように組み込み、あるいは物理層デバイス２６を介してネットワーク・プロセッサに接続することのできる制御点プロセッサ３４は、ネットワーク・プロセッサ全体の管理を提供する。このために、（以下で説明する）データ構造が汎用プロセッサで生成され、メモリにダウンロードされる。リーフの削除や付加などの更新は、前述の誘導セルを使用して組み込みプロセッサ複合体との間で制御情報をやりとりするＣＰプロセッサ３４を介して実施される。組み込みプロセッサ複合体のうちの選択されたものがそれに関連するツリー・サーチ・エンジンを使用してそれぞれの記憶およびブースタＣＡＭシステム１５とやりとりする。
【００４１】
図４から図１４に、本発明の教示による様々なデータ構造を示す。これらのデータ構造を使用して特許請求される発明をさらに説明する。
【００４２】
図４にプロトコル・プロセッサ１０のメモリに記憶されたデータ構造を表す図を示す。このデータ構造は、複数のエントリを持つダイレクト・テーブル（ＤＴ）を含み、その１つのエントリだけが横線で挟まれた領域として示され、それがパターン・サーチ制御ブロック（ＰＳＣＢ）と呼ばれる複数のノードを持つパトリシア・ツリー構造に接続されている。各ＰＳＣＢは、経路指定決定情報を含み、１つまたは複数のリーフに接続される。図４にそのうちの５つを示す。これらのリーフに含まれるのは、このツリー構造に記憶された情報に対して相関付けられているパケットに関連して行うべき決定または処置である。前述のように、この相関付けは、ピコ命令またはピコ・コードを実行するピコプロセッサ（コプロセッサ）によって実施されることになるが、他の手段によって実施することもできる。
【００４３】
図４をさらに参照すると、各ツリー構造にＣＡＭコピー閾値が関連付けられている。このＣＡＭコピー閾値（縦線で示す）は、システムに記憶された、リーフに到達するために横断することのできるＰＳＣＧの最大数を示す数である。横断されるノード数がＣＡＭコピー閾値を超えると、相関機構（コプロセッサまたはハード）がＣＡＭにアクセスしてそのリーフに関連する情報を取得する。普通、リーフのアドレスは、そのリーフ内の情報ではなくＣＡＭに記憶される。リーフが位置するアドレスだけを記憶することによって、ＣＡＭ内のスペースが保たれる。ＣＡＭが非常に高速で、低密度で、高価な記憶機構であるため、ＣＡＭ内のスペースは貴重である。図４〜図１４で、「ＣＡＭコピー閾値」と表示された破線は、システムのメモリに記憶された閾値を図示したものである。ダイレクト・テーブルに記憶された情報は、データ構造に相関付けられているパケット内の情報の複製である。
【００４４】
次に図５を見ると、データ・パターンまたは構造に相関付けられるパケットの宛先アドレス（ＤＡ）が示されている。このＤＡアドレスはＡ部およびＢ部に区分される。Ａ部はダイレクト・テーブル内で指標として使用され、Ｂ部はツリーの探索（ウォーキング）に使用される。この適用例で使用されるように、ツリーを探索するとは、ＰＳＣＢにアクセスし、あるＰＳＣＢに記憶された情報を使用して次のＰＳＣＢに進むことを意味する。このプロセスはリーフに到達するまで続けられる。リーフは、パケットに関連して講ずべき処置を含む情報を記憶する。好ましい一実施形態では、この宛先アドレスは、４８ビットＭＡＣアドレスである。Ａと表示された最初の１６ビットはダイレクト・テーブルへのアクセスに使用され、残りの３２ビットはそのエントリに関連するツリーの探索に使用される。より詳細には、ＭＡＣ宛先アドレスの最初の１６ビットはＤＴ内の各エントリと比較される。この最初の１６ビットと１つのエントリの間で一致が見つかった場合は、それ以外の３２ビットのうちの選択されたビットを使用して、関連するリーフに到達するまでツリーを探索する。ハッシュ手順を使用してＤＴおよびそのＤＴへのエントリをセットアップすることもできることに留意すべきである。ハッシュ手順は当分野では周知であり、以下ではこれ以上説明しない。
【００４５】
パケット内の他のエンティティを使用してダイレクト・テーブルにアクセスし、そのエントリに関連するツリーを探索することもできることに留意すべきである。例を挙げると、データ・テーブル内の各エントリは、フレームのＡ部と相関するはずである。ピコ・コードを実行するコプロセッサは、データ・テーブルを個々のパケットのうちの１６ビットに相関付ける。データ・テーブル内の１つのエントリがそのテーブル内のエントリに一致する場合は、残り３２ビットを使用して以下のようにツリーを探索する。残り３２ビット中の有効ビットをＰＣＢ１に対して突き合わせる。ビットが論理０の場合は、ＰＳＣＢに０で記憶された処置を実施する。ビットが論理１の場合は、ＰＳＣＢに１で記憶された処置を実施する。基本的に、ＰＳＣＢ内の情報は、ＰＳＣＢ３に至る「Ｘ」と表示された経路に沿ってツリーを探索するか、それともＰＳＣＢ２に至る「Ｙ」と表示された経路に沿ってツリーを探索するかを指図する。ＰＳＣＢ２は、リーフ２またはリーフ１にある情報を指し示す情報を持つはずである。「Ｘ」経路を探索する場合、次のノードはＰＳＣＢ３、次いでＰＳＣＢ４になるはずである。この例では、閾値は３に設定され、すべてのリーフがこの閾値の下に位置しているので、ブースタＣＡＭは使用されないことになる。
【００４６】
次に図１５を見ると、ブースタＣＡＭが図示されている。このＣＡＭは、ＣＡＭに情報を書き込むと共にＣＡＭ内の情報の計時処理（削除）を行う機構を含む既製品である。このＣＡＭは従来技術で周知であり、したがって、本明細書では詳細には論じない。ＣＡＭは複数のエントリを持つと言えば十分であろう。その１つを１５Ｂに示す。本発明のために、ＣＡＭを１５Ｃ部と１５Ｄ部に区分する。１５Ｃ部には、ＭＡＣデータ・アドレスのＡ+Ｂ部（図５）が入れられ、１５Ｄ部にはツリー構造からのリーフの位置アドレス（ＬＡ）が記録される。動作に際して、パケットの宛先アドレスのビット３２〜ビット４８がブースタＣＡＭに記憶され、ブースタＣＡＭシステム１５のブースタＣＡＭにアクセスするための指標としても使用される。ブースタＣＡＭの１５Ｄ部内の関連するリーフ・アドレスが読み出され、そのリーフ・アドレスに記憶された情報へのアクセスに使用される。次に図４を見ると、ブースタＣＡＭの使用は図４のデータ構造には適用できないはずである。というのは、図４の各リーフは、ＣＡＭコピー閾値の左側のＰＳＣＢに接続されており、これはＰＳＣＢが設定閾値より下にあることを示すからである。次に、リーフが閾値より上にあるＰＳＣＢに接続されているためにＣＡＭが使用されることになる状態について論じる。ツリーにリーフが付加されると、いくつかの状況が起こり得る。
【００４７】
Ａ）リーフが閾値の上（すなわちＣＡＭコピー閾値の右側）にあるノードに挿入される。この状況では、挿入はＣＡＭ内のリーフのコピーをトリガすることになるサーチを必要とする。図６はそうした状況の一例である。図６では閾値は３に設定される。リーフ６が挿入され、４つのノード（すなわちＰＳＣＢ１、ＰＳＣＢ３、ＰＳＣＢ４、ＰＳＣＢ５）を経た後で初めてそこに到達する。挿入時に、リーフ６のアドレスはＣＡＭにコピーされる。ここでリーフ５は閾値の上にあるが、これは、このリーフを必要とするトラフィックがない場合は、ＣＡＭにコピーされない。
【００４８】
Ｂ）別の状況が、リーフが閾値の下に挿入され、閾値を超えるリーフを生じない場合である。この場合、ＣＡＭ内容に関しては何も変更されない。
【００４９】
Ｃ）別の状態が、リーフは閾値の下に挿入されるが、他の１つまたは複数のリーフが閾値を超え、またはその外側になる場合である。この場合、閾値を超えたどのリーフも直ぐにはＣＡＭにコピーされない。その代わり、そのリーフは、そこに通常の検索によって到達した時点で、すなわちそれが実際に使用されるときにはじめてコピーされる。したがって、ＣＡＭは、現在のネットワーク・トラフィックに必要とされる「有用な」リーフだけを含む。
【００５０】
Ｄ）図７に、今度はリーフ５およびリーフ６が検索時にＣＡＭにコピーされる状況を示す。図６を参照して、リーフ６がＣＡＭにコピーされたときに、リーフ５はトラフィックに必要とされなかったのでコピーされなかったことを想起する必要がある。しかし、それは、必要とされればすぐにＣＡＭにコピーされる。これもやはり、ＣＡＭが高価なタイプの記憶であるためにＣＡＭリソースを保持するための技法である。
【００５１】
Ｅ）図８に、３つのリーフ、すなわちリーフ５、リーフ６、リーフ７がＣＡＭにコピーされる状況を示す。リーフ７が挿入されるのは、５つのＰＳＣＢ（閾値より上＝３）を経た後でそこに到達するからである。これはＣＡＭにコピーされる。
【００５２】
Ｆ）図９に、ＣＡＭからリーフ６のアドレスが削除される状況を示す。この削除はＣＡＭ経時処理機構によって実行される。これが活動化されるのは、リーフ６が、所与の期間どのトラフィックによっても使用されていないからである。
【００５３】
Ｇ）図１０に、リーフ６が検索時にＣＡＭに再コピーされる状況を示す。図９では、リーフ６は、トラフィックがその使用を必要としなかったために削除された。図１０では、今度はトラフィックがリーフ６を再度必要としている。したがって、それはＣＡＭに再コピーされ、しかるべくマークされる。これらの例は、経時処理機構が、リーフ内の情報の使用または不使用に基づいて周期的にＣＡＭからリーフ情報を削除することを示すことに留意すべきである。
【００５４】
Ｈ）以上、ツリーにリーフを付加するときに存在する状態について論じてきた。次に、ツリーからリーフを削除するときに存在する状態について論じる。ツリーからのリーフの削除は、経時処理または制御点動作が原因でトリガされ得る。経時現象は、リーフが一定期間使用されず、経時処理機構がそれを記憶から削除するときに発生する。制御点削除は、制御点にある汎用プロセッサが、何らかの理由で、記憶からリーフを削除すべきであると決定したときに発生する。経時による削除または制御点による削除のどちらの場合にも、そのリーフが論理１に設定されたコピー済みビットを持つ場合には、それに対応するエントリがＣＡＭから除去される。
【００５５】
Ｉ）このリーフが０に設定されたコピー済みビットを持つ場合には、ＣＡＭ内容は変更されない。リーフを削除した結果、閾値より上にあった他のリーフが、リーフが削除されると閾値の下に戻ることがある。これらのリーフが以前にＣＡＭにコピーされていた場合は、それらはＣＡＭ経時処理機構によってＣＡＭから削除される。この経時処理のタイムアウトは、通常、ツリーの経時処理より短い。これによって、検索でより頻繁に使用されるリーフによるＣＡＭエントリの効率的な再利用が可能になる。ＣＡＭ経時処理によってＣＡＭエントリが削除されると、検索でそこに到達したときに、それに対応するリーフがＣＡＭに再コピーされる。その検索だけが閾値より長い存続期間を有し、それに続く検索はそのＣＡＭコピーを有利に利用することになる。
【００５６】
Ｊ）図１１に、リーフ５がツリーから削除される状況を示す。この削除は、制御点プロセッサからの、またはツリー経時処理機構による明示的削除処置に基づくものであり得る。この状況では、ＣＡＭコピーも削除される。リーフ６およびリーフ７のＣＡＭコピーは、閾値より上にあるＰＳＣＢ６に接続されているため残存することに留意すべきである。
【００５７】
Ｋ）図１２に、リーフ４が、明示的削除処置またはツリー経時処理によってツリーから削除される状況を示す。リーフ４のＣＡＭコピーもＣＡＭから削除される。リーフ６およびリーフ７は閾値の下に戻るが、それらのＣＡＭコピーはこのときには削除されないことに留意すべきである。
【００５８】
Ｌ）図１３に、以前にＣＡＭに記録されたリーフ７が、ＣＡＭ経時処理機構によって今度は除去される例を示す。この除去がトリガされるのは、リーフ７が、所与の期間どのトラフィックによっても使用されていないからである。
【００５９】
Ｍ）図１４では、リーフ６は所与の期間使用されておらず、ＣＡＭ経時処理機構はこれをＣＡＭから削除する。
【００６０】
図１６に本発明に教示によるハイブリッド検索機構の構成図を示す。このハイブリッド検索機構は、ＣＬＰ（コア言語プロセッサ）７２、ツリー・サーチ・エンジン（ＴＳＥ）７０、記憶３０（Ｓ−ＲＡＭ、ＤＤＲＡＭなど）およびＣＡＭ１５を含む。記憶３０には前述のツリー構造が記憶される。ＣＡＭには前述のＣＡＭ情報が記憶される。
【００６１】
ＴＳＥ７０は、ツリー・ウォーク論理１５１、ＣＡＭ制御機構１５２、およびメモリ・アービタ１５３を含む。ＴＳＥはＣＬＰ７２、Ｓ−ＲＡＭ、Ｄ−ＲＡＭその他の任意の適当なメモリである記憶３０、およびＣＡＭ１５に接続される。記憶は、前述検索データ構造（ＤＴ、ＰＳＤＢ、リーフ）を記憶する。ＣＡＭは、前述したようなキーの動的コピーを含む。
【００６２】
ＣＬＰ７２は、フレームから生成された、サーチすべきキーをＴＳＥに与える。メモリ・アービタ１５３は、このキーを、ツリー・ウォーク論理１５１とＣＡＭ制御機構１５２とに転送する。
【００６３】
ツリー・ウォーク論理はＤＴで最初の検索ステップを自動的に実施し、リーフに到達するまでＰＳＣＢの連鎖をたどってサーチ動作を続行する。ＰＳＣＢノードの連鎖をたどる際に、ＰＳＣＢカウンタ１５４は、横断されるノード数をカウントする。
【００６４】
同時に、ＣＡＭ制御機構は、キーを、そのキーの高速サーチを実施するＣＡＭに転送する。
【００６５】
同時に開始されたこれら２つの動作は、ツリー・ウォーク論理とＣＡＭのどちらが先に終了してもよい。
【００６６】
ＣＡＭが先に終了した場合、それはメモリ・アービタに結果（リーフ・アドレス）を返し、それによってウォーク・ツリー論理でまだ実行されている動作が打ち切られる。これは、ＣＡＭでキーが見つかり、そのため、ツリー・ウォーク論理でサーチを続行させる際に値がないからである。次いで、メモリ・アービタは、リーフの実際の内容を取り出すために、ツリー・ウォーク論理を介して記憶に読取り要求を出す。
【００６７】
ツリー・ウォーク論理が先に終了した場合、それは結果（リーフ・アドレスおよびリーフ内容、ＰＳＣＢカウント）をメモリ・アービタに返す。メモリ・アービタは、ＣＡＭ制御機構にＣＡＭでのサーチ・プロセスを打ち切るよう要求する。これによって、ＣＡＭの経時処理機構が、記憶内で非常に高速で（ＣＡＭを介するよりも高速で）実際にサーチされるキーに対応するＣＡＭエントリを削除することができ、記憶内でより長時間のサーチを必要とするはずの他のキーにより多くの余地を残すことができるようになる。
【００６８】
ＰＳＣＢカウントは、ツリー・ウォーク論理によって提供されるサーチ結果に含まれる。メモリ・アービタは、このカウントが閾値を超えた場合には、直前にサーチされたキーに対応するＣＡＭエントリを付加するようＣＡＭ制御機構に要求するために、このカウントを使用してそれを事前設定された閾値と比較する。
【００６９】
この閾値は、すでに記憶されているがメモリ内より低速でサーチされるキーのＣＡＭへの付加を求める要求を回避するために、記憶内のサーチ動作がＣＡＭ内のサーチより長くなることを保証するように構成される。
【図面の簡単な説明】
【００７０】
【図１】ネットワーク・プロセッサの一例を示す構成図である。
【図２】組み込みプロセッサ複合体（ＥＰＣ）の詳細を示す図である。
【図３】プロトコル・プロセッサ構造を示す図である。
【図４】ツリー・データ構造を示す図である。
【図５】パケットをデータベースに相関付けるのに使用されるパケットの一部を示す図である。
【図６】リーフ６がＣＡＭコピー閾値の上に挿入され、このリーフがネットワーク・トラフィックによって必要とされる場合に限りＣＡＭに挿入される、ツリー・データ構造を示す図である。
【図７】リーフ５が現在ＣＡＭ閾値の上にあり、このリーフがネットワーク・トラフィックによって必要とされる場合に限りコピーされるツリー・データ構造を示す図である。
【図８】第２のリーフ７がＣＡＭコピー閾値の上に挿入されるツリー・データ構造を示す図である。
【図９】一定期間ネットワーク・トラフィックによって使用されないリーフがＣＡＭから削除されるツリー・データ構造を示す図である。
【図１０】図９で削除されたリーフが、今度は、トラフィックによって必要とされ、それが検索時にＣＡＭに再コピーされるツリー・データ構造を示す図である。
【図１１】ツリーからリーフが削除され、それが同様にＣＡＭからも削除されるツリー・データ構造を示す図である。
【図１２】削除されたリーフによって、以前にＣＡＭコピー閾値の上にあったリーフをＣＡＭコピー閾値の下になるツリー・データ構造を示す図である。
【図１３】一定期間トラフィックによって使用されないリーフ７がＣＡＭから除去されるツリー・データ構造を示す図である。
【図１４】トラフィックによって使用されない別のリーフ６がＣＡＭから削除されるツリー・データ構造を示す図である。
【図１５】ブースタＣＡＭ内のデータの構造を示す図である。
【図１６】本発明の教示によるハイブリッド検索機構を示す構成図である。