(57)【要約】  ハッシング及びパターン・マッチングが、情報処理システムで用いられて、イーサネット(登録商標)・ベースのネットワークのようなネットワーク（図２：１８０，２１０，２２０，２３０）からの到来メッセージを処理する。ハッシング及びパターン・マッチングを用いることにより、ソフトウエア・ベースのプロセッサ・タスクを増大させることなしに、メッセージの受け入れ及び拒絶の効率が増大される。ハッシュ関数及びパターン関数が、情報処理システムにより受信されたメッセージについて実行され、且つメッセージが、ハッシュ結果及びパターン・マッチング結果のうちの少なくとも１つに基づいて選択的に受け入れられる。到来メッセージをパターンの存在及びパターンの不存在に関して検索することができる。到来メッセージを複数のパターンの存在に関して検索することができる。パターン・マッチングの結果は、メッセージの受け入れ及び拒絶のためばかりでなく、到来メッセージの選択的格納のような他の事後受け取りタスクのためにも、特定のパターン・マッチを有するメッセージの識別された相対優先度又は絶対クリティカリティに従って用いられることができる。
2007512770.tif 000002
【特許請求の範囲】
【請求項１】
メッセージを受信するステップと、
第１のパターンに対応する第１のパターン・マッチが前記の受信されたメッセージ内に検出されたかどうかを決定するステップであって、前記第１のパターンが、パターン・マッチ・データにより指示され、且つ対応の逆パターン・インディケータ及び対応のパターン・マッチ受け入れインディケータを有する、前記決定するステップと、
第１のパターン・マッチが検出されたとき、前記メッセージを前記対応のパターン・マッチ受け入れインディケータに基づいて選択的に受け入れるステップと、を備え、
前記対応の逆パターン・インディケータが第１の値を有する場合、第１のパターン・マッチが、第１のパターンが前記の受信されたメッセージ内に検出されたとき検出され、
前記対応の逆パターン・インディケータが第２の値を有する場合、第１のパターン・マッチが、第１のパターンが前記の受信されたメッセージ内に検出されないとき検出される、方法。
【請求項２】
前記第１のパターンが、対応の連続検索イネーブル・インディケータを有し、
前記メッセージを前記対応のパターン・マッチ受け入れインディケータに基づいて選択的に受け入れる前記ステップが、前記メッセージを前記対応のパターン・マッチ受け入れインディケータ及び前記対応の連続検索イネーブル・インディケータに基づいて選択的に受け入れるステップを備える
請求項１記載の方法。
【請求項３】
前記第１のパターンが、前記の受信されたメッセージ内の位置で前記第１のパターン・マッチが検出されたかどうかを決定する当該位置を指示する対応のマッチ・インデックスを有する請求項１記載の方法。
【請求項４】
前記第１のパターン・マッチが検出されたとき、前記方法は更に、
第２のパターン・マッチが前記の受信されたメッセージ内に検出されたかどうかを決定するステップであって、第１のパターン及び第２のパターンのそれぞれが、対応の連結インディケータを有し、メッセージを選択的に受け入れる前記ステップが、第１のパターンに対応する前記パターン・マッチ受け入れインディケータと、第１のパターンに対応する連結インディケータ及び第２のパターンに対応する連結インディケータのうちの少なくとも１つの連結インディケータとに基づく、前記決定するステップと、
前記第２のパターン・マッチが検出され、且つ第１のパターンに対応する連結インディケータ及び第２のパターンに対応する連結インディケータのうちの少なくとも１つの連結インディケータが第１及び第２のパターンの連結を指示する場合、第１のパターンに対応するパターン・マッチ受け入れインディケータが前記の受信されたメッセージの受け入れを指示するとき、前記メッセージを選択的に受け入れるステップと、
前記第２のパターン・マッチが検出されず、且つ第１のパターンに対応する連結インディケータ及び第２のパターンに対応する連結インディケータのうちの前記少なくとも１つの連結インディケータが第１及び第２のパターンの連結を指示する場合、第１のパターン・マッチが検出されなかったと見なすステップと
を備える請求項１記載の方法。
【請求項５】
ハッシュ関数を実行して、ハッシュ・ヒットが生じたかどうかを決定するステップであって、ハッシュ・ヒットが生じ、第１のパターン・マッチが検出され、且つ第１のパターンに対応するパターン・マッチ受け入れインディケータが前記の受信されたメッセージの受け入れを指示するとき、前記メッセージを選択的に受け入れるステップを更に備える請求項１記載の方法。
【請求項６】
前記メッセージが受け入れられたとき、
前記方法が更に、
バッファ記述子キュー（ＢＤＱ）をパターン・マッチ属性に基づいて選択するステップと、
前記メッセージをメモリに前記の選択されたＢＤＱに従って格納するステップと、
前記の受け入れられたメッセージの少なくとも一部分をキャッシュに選択的に格納するステップであって、前記の受け入れられたメッセージの一部分が、前記パターン・マッチ属性により指示される、前記選択的に格納するステップと
を備える請求項１記載の方法。
【請求項７】
メッセージを受信する入力と、
第１のパターンに対応する第１のパターン・マッチが前記受信されたメッセージ内に検出されたかどうかを決定するパターン・マッチング論理であって、第１のパターンを指示するパターン・マッチ・データを格納し、且つ第１のパターンに対応するパターン・マッチ受け入れインディケータ及び第１のパターンに対応する逆パターン・インディケータを含むパターン・マッチ制御を格納する少なくとも１つのパターン・マッチ・レジスタを備える前記パターン・マッチング論理と、
前記パターン・マッチング論理に結合された制御論理であって、前記第１のパターン・マッチが検出され且つ第１のパターンに対応するパターン・マッチ受け入れインディケータが前記の受け入れられたメッセージの受け入れを指示するとき、前記の受信されたメッセージを選択的に受け入れる前記制御論理と、を備え、
前記対応の逆パターン・インディケータが第１の値を有する場合、第１のパターン・マッチが、第１のパターンが前記の受信されたメッセージ内に検出されたとき検出され、
前記対応の逆パターン・インディケータが第２の値を有する場合、第１のパターン・マッチが、第１のパターンが前記の受信されたメッセージ内に検出されなかったとき検出される、パケット制御器。
【請求項８】
メッセージを受信するステップと、
前記メッセージについてハッシュ関数を実行して、ハッシュ結果を与えるステップと、
前記メッセージについてパターン・マッチングを実行して、パターン・マッチ結果を与えるステップと、
前記メッセージを前記パターン・マッチ結果に少なくとも基づいて選択的に受け入れるステップと
を備える方法。
【請求項９】
前記メッセージを選択的に受け入れる前記ステップが、前記パターン・マッチ結果及び前記ハッシュ結果に基づいている請求項８記載の方法。
【請求項１０】
前記パターン・マッチ結果が、前記の受信されたメッセージが第１の所定のパターン及び第２の所定のパターンのうちの少なくとも１つを含むかどうかを指示する請求項８記載の方法。
【請求項１１】
前記パターン・マッチ結果が、前記の受信されたメッセージが第１の所定のパターン及び第２の所定のパターンを含むかどうかを指示する請求項８記載の方法。
【請求項１２】
前記メッセージが受け入れられたとき、
前記方法は更に、
バッファ記述子キュー（ＢＤＱ）を前記パターン・マッチ結果に基づいて選択するステップであって、前記パターン・マッチ結果が、前記の受信されたメッセージが第１のパターンを含むかどうかを指示し、パターン・マッチ属性を与える、前記選択するステップと、
前記メッセージをメモリに前記の選択されたＢＤＱに従って格納するステップと、
前記の受け入れられたメッセージの少なくとも一部分をキャッシュに選択的に格納するステップであって、前記の受け入れられたメッセージの一部分が、前記パターン・マッチ属性により指示される、前記選択的に格納するステップと
を備える請求項８記載の方法。
【請求項１３】
メッセージを受信するステップと、
ハッシュ関数を実行して、ハッシュ・ヒットが生じたかどうかを決定するステップと、
第１のパターンに対応する第１のパターン・マッチが前記の受信されたメッセージ内に検出されたかどうかを決定するステップであって、前記第１のパターンが、パターン・マッチ・データにより指示され、且つ対応のパターン・マッチ受け入れインディケータを有する、前記決定するステップと、
前記第１のパターン・マッチが検出された場合、第１のパターンに対応する前記パターン・マッチ受け入れインディケータが前記の受信されたメッセージの受け入れを指示し且つハッシュ・ヒットが生じたとき、前記の受信されたメッセージを選択的に受け入れるステップと、
前記第１のパターン・マッチが検出され、且つ第１のパターンに対応する前記パターン・マッチ受け入れインディケータが前記の受信されたメッセージの拒絶を指示し、且つハッシュ・ヒットが生じたとき、前記の受信されたメッセージを拒絶するステップと
を備える方法。
【請求項１４】
前記第１のパターン・マッチが検出された場合、第１のパターンに対応する前記パターン・マッチ受け入れインディケータが前記の受信されたメッセージの受け入れも拒絶も指示せず、且つハッシュ・ヒットが生じたとき、前記の受信されたメッセージを選択的に受け入れるステップを備える請求項１３記載の方法。
【請求項１５】
前記第１のパターン・マッチが検出されたかどうかを決定する前記ステップが更に、連結インディケータに基づいている請求項１３記載の方法。
【請求項１６】
前記第１のパターン・マッチが検出された場合、第１のパターンに対応する前記パターン・マッチ受け入れインディケータが前記の受信されたメッセージの受け入れを指示し、且つ前記ハッシュ・ヒットが生じたとき、前記の受信されたメッセージが、連続検索インディケータに基づいて選択的に受け入れられる請求項１３記載の方法。
【請求項１７】
前記第１のパターンが、対応の逆パターン・インディケータを有し、
前記逆パターン・インディケータが第１の値を有する場合、前記第１のパターン・マッチが、前記の受信されたメッセージが第１のパターンを含むとき検出される
請求項１３記載の方法。
【請求項１８】
メッセージを受信する入力と、
ハッシュ関数を実行して、ハッシュ・ヒットが前記の受信されたメッセージ内で生じたかどうかを決定するハッシュ論理と、
前記ハッシュ論理に結合され、第１のパターンに対応する第１のパターン・マッチが前記受信されたメッセージ内に検出されたかどうかを決定するパターン・マッチング論理であって、第１のパターンを指示するパターン・マッチ・データを格納し且つ第１のパターンに対応するパターン・マッチ受け入れインディケータを含むパターン・マッチ制御を格納する少なくとも１つのパターン・マッチ・レジスタを備える前記パターン・マッチング論理と、
前記ハッシュ論理及びパターン・マッチング論理に結合された制御論理であって、前記第１のパターン・マッチが検出され、且つ第１のパターンに対応する前記パターン・マッチ受け入れインディケータが前記の受信されたメッセージの受け入れを指示し、且つハッシュ・ヒットが生じたとき、前記の受信されたメッセージを選択的に受け入れ、前記第１のパターン・マッチが検出されず且つハッシュ・ヒットが生じたとき、前記の受信されたメッセージを拒絶する前記制御論理と
を備えるパケット制御器。
【発明の詳細な説明】
【技術分野】
【０００１】
［背景］
［分野］
本発明は、ネットワーク通信に関し、より詳細には、イーサネット(登録商標)・ネットワークのようなネットワークを介して受信されたメッセージを処理することに関する。
【０００２】
［関連技術］
ローカル・エリア・ネットワーク（ＬＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、及び他の種類のネットワークは、典型的には、様々なパケット・ベースの通信プロトコルに従って動作するコネクションを介して結合された多数の情報処理システムを含む。例えば、イーサネット(登録商標)ＩＥＥＥ８０２．３プロトコルは、キャリア・センス多重アクセス／衝突検出（ＣＳＭＡ／ＣＤ）アプローチに基づいた広範に使用のＬＡＮプロトコルである。イーサネット(登録商標)とＩＥＥＥ８０２．３プロトコルとは、似ていて、そして同じＬＡＮ上で共存することができるので、これら両方は、時々イーサネット(登録商標)と呼ばれる。１０／１００イーサネット(登録商標)は、１０から１００メガビット／秒（Ｍｂｐｓ）の増大したイーサネット(登録商標)速度を与え、そしてバックボーン及び厳しい接続性に関して単純で且つ費用対効果が大きいオプション（選択）を提供する。ギガビット・イーサネット(登録商標)は、基本イーサネット(登録商標)・プロトコルの上に形成される別のイーサネット(登録商標)・プロトコルであるが、しかし速度を１０／１００イーサネット(登録商標)より１０倍の１０００Ｍｂｐｓ又は１ギガビット／秒（Ｇｂｐｓ）に増大する。
【０００３】
ネットワークの中の装置（デバイス）は、多くの場合、それらに向けられたメッセージとそれらに向けられていないメッセージとを受信する。従って、そのような装置は、各到来メッセージを局所的に分析して、当該装置がメッセージを受け入れるかどうかを決定しなければならない。典型的には、各装置は、各受信されたメッセージのアドレスと或る形式で比較しなければならないアドレスを有する。正確なアドレス・マッチは、比較されるべきアドレスの長さ及び非常に多数のアドレスの故に、計算上集約的である。装置が多数の他の装置に対するメッセージを受け入れることができ、非常に多数のメッセージが、受信され、且つネットワークの速度が益々増大しているので、到来メッセージを処理（例えば、受け入れ、又は拒絶）する問題は、ネットワークの中の様々な装置でボトルネックを引き起こし、そして全体の性能を落とすことになる。従来のデスティネーション・アドレス（宛先アドレス）認識方法は、メディア・アクセス制御（ＭＡＣ）レベルより高いオープン・システム相互接続（ＯＳＩ）レベルで行われるポスト・フィルタリングを必要とし、そして著しいソフトウエア及び一般的処理ハードウエア介入を必要とする。幾つかの技術は、コンテント・アドレサブル・メモリ（ＣＡＭ）を採用するが、しかしそのような技術は、典型的には、高価であり、過剰に電力を消費し、柔軟性が無い。従って、到来メッセージを処理する性能を増強する必要性が存在する。
【０００４】
到来メッセージを単に受け入れ又は拒絶することに加えて、各装置は、典型的には、メッセージを受信することに応答して実行すべき様々なタスクを有する。従って、メッセージにより受信された一部のデータは、格納され、且つ或る短い時間内にアクセスされる必要がある。従って、受信されたメッセージを事前処理することによりそのようなメッセージの処理を増強して（例えば、受信されたメッセージがプロセッサ又はソフトウエア駆動のシステム資源により検査される前にインバウンド・メッセージをソートすることにより）、他のタスクのためそのような資源の使用を解放し、且つ重要な又は高い優先度フレームにアクセスするレイテンシー（待ち時間）を低減することが有利であろう。
【０００５】
本発明は、添付図面を参照することにより、より良く理解され、そしてその多くの目的、特徴及び利点が、当業者に明らかにされるであろう。異なる図面においての同じ参照番号の使用は、類似又は同一の構成要素を示す。
【０００６】
［詳細な説明］
以下の説明は、本発明の少なくとも一つの例の詳細な説明を提供することを意図しており、本発明自体を制限するものと取るべきでない。むしろ、いずれの多くの変形は、この説明に続く特許請求の範囲において適切に定義される本発明の範囲内に入り得る。
【０００７】
図１は、本発明の一実施形態に従った情報処理及び通信システム１００を示すブロック図である。情報処理及び通信システム１００は、プロセッサ１１０、キャッシュ１２０、メモリ１３０、システム・バス１４０、周辺装置１５０、及びパケット制御器１６０を含む。プロセッサ１１０、キャッシュ１２０、メモリ１３０、周辺装置１５０、及びパケット制御器１６０は、全て、システム・バス１４０を介して結合されている。情報処理及び通信システム１００は、イーサネット(登録商標)、ギグイーサネット(登録商標)（Ｇｉｇ−Ｅｔｈｅｒｎｅｔ(登録商標)）及び／又はエックスギグイーサネット(登録商標)（ＸＧｉｇ−Ｅｔｈｅｒｎｅｔ(登録商標)）制御器であり得て、又はさもなければそれらと互換性のあるものであり、ネットワーク・スイッチ、又はルータ、又はネットワーク内で通信するための他の種類の装置（デバイス）であり得る。
【０００８】
パケット制御器１６０は、バス・インターフェース・ユニット（ＢＩＵ）１７０、受信部１８０、送信部１８５、及びメディア・アクセス制御器（ＭＡＣ）１９０を含む。バス・インターフェース・ユニット１７０は、システム・バス１４０に結合されている。バス・インターフェース・ユニット１７０は、接続１７２を介して受信部１８０に、そして接続１７４を介して送信部１８５に結合されている。ＭＡＣ１９０は、接続１９２を介して受信部１８０に、そして接続１９４を介して送信部１８５に結合されている。ＭＡＣ１９０は、物理層ハードウエアに結合されて、パケットのようなメッセージを物理的（ＰＨＹ）接続１９８を介して他の装置から受信する。
【０００９】
メッセージは、ＭＡＣ１９０で受信され、そして受信部１８０に通される。メッセージは、アドレス認識、ハッシング、パターン・マッチング、又はハッシング且つパターン・マッチング（例えば、少なくとも図２から図９を参照して以下で説明されるようなもの）に応じて受け入れられたり又は受け入れられなかったりする。受け入れられたメッセージからの情報は、メモリ１３０に通される。特にプロセッサ１１０又は他のシステム資源による迅速なアクセスが適格であるという或る一定の情報が、パターン・マッチングにより識別され、その場合、そのような情報は、メモリ１３０に送られた正常なメッセージ・データから抽出され、そしてその抽出されたデータは、（例えば、少なくとも図２から図６及び図１０から図１１を参照して以下で説明されるように）キャッシュ１２０にスタッシュ（ｓｔａｓｈ）される。
【００１０】
開示されるデスティネーション・アドレス認識プロトコルは、ポスト・フィルタリングの必要性を最小にし、そして更なるソフトウエア及びハードウエア介入をより高いＯＳＩレベルで要求する代わりにメディア・アクセス制御レベルで行われることができる。一部の組のアドレスに対して、ユーザは、ＭＡＣレベルで完全なフィルタリングをもたらす１組のパターンを見つけることができるであろう。決定性アルゴリズムを用いて、必要とされるパターンを発生して、完全なハッシュ時間フィルタリング（ｈａｓｈ−ｔｉｍｅ  ｆｉｌｔｅｒｉｎｇ）を保証し得る。開示されるプロトコルはまた、単にデスティネーション・アドレス内ばかりでなく受け入れられたフレーム全体にわたりパターン・マッチ検索を可能にして、ハッシュ時間フィルタリングの結果を精緻にする。
【００１１】
メモリ１３０は、以下で更に詳細に説明されるように、到来メッセージを格納するフレーム・データ・バッファ１３４と、その格納されたメッセージを追跡するバッファ記述子キュー１３２とを含む。キャッシュ１２０は、１又はそれより多くのバッファ記述子キュー１２２を格納し得る格納場所と、プロセッサ１１０の続いての使用のため、抽出されたデータ１２４をスタッシュ（即ち、格納）する格納場所とを含む。抽出されたデータは、本明細書で説明される或る一定のパターン・マッチング・プロトコルに従って、キャッシュ１２０に格納のため到来メッセージの正常なフレーム・データから抽出されるデータである。抽出されたデータは、例えば、臨界的データ（重要なデータ）（ｃｒｉｔｉｃａｌ  ｄａｔａ）、サービスの質（ＱＯＳ）レベル・データ、又は他の高優先度データであり得て、それらに対して早められたアクセス時間が望ましい。メモリ１３０及びキャッシュ１２０は、プロセッサ１１０によりアクセス可能であり、そして情報処理及び通信システム１００内の他の装置又はプロセッサ（図示せず）によりアクセス可能ですらあり得る。
【００１２】
図２は、情報処理及び通信システム１００のパケット制御器１６０の受信部１８０を示すブロック図である。受信部１８０は、直接メモリ・アクセス（ＤＭＡ）制御器２１０、受信ＦＩＦＯ２２０、及びアドレス／データ・フィルタ（ＡＤＦ）２３０を含む。ＡＤＦ２３０は、メッセージをＭＡＣ１９０から受信し、そしてそのようなメッセージをＦＩＦＯ２２０に選択的に与えるよう結合されている。アドレス／データ・フィルタ２３０により受信可能である、フレームを有する典型的なメッセージ・パケットが、図３を参照して以下でより詳細に説明される。ＤＭＡ２１０は、ＦＩＦＯ制御器２２２の制御下で、メッセージ情報（例えば、アドレス及びデータ情報、及び以下で説明されるパターン状態（ステータス）情報のようなメッセージフィルタ結果）を受信ＦＩＦＯ２２０から受信するよう結合されている。
【００１３】
ＡＤＦ２３０は、一時キュー２３４、パターン・マッチング論理２３２、及びアドレス認識及びハッシュ論理２３８を含む。一時キュー２３４、パターン・マッチング論理２３２及びアドレス認識及びハッシュ論理２３８のそれぞれは、メッセージ（例えば、フレーム）をＭＡＣ１９０から受信するよう結合されている。一時キュー２３４は、メッセージ・フィルタ結果情報をパターン・マッチング論理２３２及びアドレス認識及びハッシュ論理２３８から受信して、それに応答してそのフレーム（又は、当該フレームの一部分）及びメッセージ・フィルタ結果情報を受信ＦＩＦＯ２２０に与えるよう結合されている。
【００１４】
パターン・マッチング及びハッシング論理無しで、直接且つフルのアドレス比較が、全ての受信されたメッセージのデスティネーション・アドレスと、情報処理及び通信システム１００又は他のシステム（その他のシステムのため、情報処理及び通信システム１００がメッセージを受け入れるよう構成される。）のアドレスとの間で実行されなければならないであろう。そのようなフル・アドレス比較は、典型的には、その比較が典型的にはソフトウエアの制御下で起きるのでプロセッサ１１０を或る形式で中断することを含む。
【００１５】
しかしながら、図示の実施形態においては、パターン・マッチング論理２３２及びハッシュ論理２３８は、フル・アドレス比較の発生の頻度を少なくするため設けられ、それによりプロセッサ１１０が他のタスクを実行するため自由になるのを可能にする。パターン・マッチング論理２３２は、受信されたフレームについてパターン・マッチング解析を実行して、パターン・マッチング結果に従ってフレームの選択的受け入れを可能にする。パターン・マッチングは、パターン・マッチング（ＰＭ）レジスタ２３３に格納された値（例えば、制御ビット又はフィールド）の制御の下で実行される。ハッシュ論理２３８は、受信されたフレームのアドレスについてハッシング解析を実行して、ハッシュ・ヒット又はミス結果に従ってフレームの選択的受け入れを可能にして、更に、高い受け入れ確率でアドレスについてのフル・アドレス比較を実行する可能性を増大させる。
【００１６】
パターン・マッチング論理２３２のＰＭレジスタ２３３は、１６個のエントリを含む。各エントリは、５個の３２ビットレジスタを含む。図５を参照すると、各エントリは、パターン（ＰＭＤＡＴＡ）、パターン・マスク（ＰＭ ＭＡＳＫ）、及びパターン・マッチング制御（ＰＭ ＣＯＮＴＲＯＬ）フィールドを含む。パターン・マッチング制御フィールドは、マッチング・インデックス（ＭＩ）フィールド、連続検索イネーブル（ＣＳＥ）フィールド、反転（ＩＶ）フィールド、連結パターン（ＣＰ）フィールド、及びパターン・マッチ受け入れ制御（ＰＭＡＣ）フィールドを含む。
【００１７】
ＰＭ ＤＡＴＡフィールドは、受信されたフレームと比較するためのビット・パターンを含む。ＰＭＤＡＴＡビット・パターン（例えば、４バイト・パターン）がフレームの中に見つけられる場合、パターン・マッチは、検出されない。ＰＭＤＡＴＡフィールドは、図示の実施形態においては３２ビット長である。ＰＭ ＭＡＳＫフィールドは、上記比較が行われているときパターンの中の或る一定のビットをマスクさせるビットを含む。例えば、フレームの一部分内のベンダ（ｖｅｎｄｏｒ）識別ビットは、ＰＭＭＡＳＫが適切に設定されているとき無視され得る。
【００１８】
マッチング・インデックス（ＭＩ）フィールドは、マッチングが受信されたフレーム・パターンにおいてどの位の深さで対応のＰＭ ＤＡＴＡのため開始すべきかを含む。例えば、ＭＩフィールドは、０から２５６ビットの検索開始範囲を指示する６ビットを含む。一実施形態においては、ＭＩは、４バイトの倍数で、パターン・マッチングの実行を始める受信フレーム（ＤＡフィールドからＦＣＳまででＤＡフィールド及びＦＳＣを含む）の開始点からのインデックス（指数）を指定する。ＭＩがクリアされた場合、デスティネーション・アドレスの最初の４バイトは、パターン・マッチングのための開始点を与える。ＭＩのためのプログラムされた最大の値は、現在説明している実施形態において６３（２５２バイト・オフセット）である。各４バイト・パターンのためのＭＩ値は、連続又は非連続のパターンを可能にするときでさえ遵守（ｈｏｎｏｒ）される。
【００１９】
連続検索イネーブル（ＣＳＥ）フィールドは、マッチ（一致）が見つけられるとき取るべき動作の種類に影響を及ぼす。特に、ＣＳＥビットは、活動がパターン・マッチ直後に取られるべきか、又は更なるパターン・マッチ検索がパターン・マッチの際に行われるべきかを指示する。セットＣＳＥビット（ｓｅｔ  ＣＳＥ  ｂｉｔ）は、マッチがエントリについて行われる場合パターン・マッチングが継続されるべきであることを指示する。例えば、パターン・マッチが見つけられ且つ連続検索がイネーブルされる場合、パターン・マッチング論理２３２は、ＰＭＤＡＴＡの他のマッチをＰＭレジスタ２３３の他のレジスタから最大２５６バイトまで検索を継続する。他のマッチに遭遇しない場合、最後にマッチされたエントリに対応する属性が、用いられる。全ての連続したパターンは、最終の受け入れのためパターン・マッチングに基づいて拒絶する必要がない。例えば、最初のパターン・マッチは、少なくとも条件付けして受け入れなければならず、そして、全ての後続のパターンは、受け入れなければならないか、又はフレームを受け入れるため受け入れもしないし拒絶もしない。後続のパターン・マッチの拒絶が生じる場合、ＣＳＥの値が無視され、フレームが拒絶され、そして検索が打ち切られる。パターン・マッチが見つけられ且つ連続の検索がディスエーブルされる（ＣＳＥ＝０）場合、他の全てのパターンの検索は、パターン・マッチング論理２３２により打ち切られ、そしてフレームが、受け入れるか又は拒絶され、又は別の決定が、特定のパターン・マッチが起こることに基づいて行われる。
【００２０】
連結されたパターン（ＣＰ）フィールドは、ＰＭレジスタ２３３の各エントリで利用可能な３２ビットより大きいビットのＰＭ ＤＡＴＡの比較を可能にする。ＣＰビットが設定される場合、現在のＰＭレジスタに続く直ぐ隣りのＰＭレジスタ２３３は、このパターンの連続と見なされ、そして次のＰＭＤＡＴＡエントリは、現在のＰＭ ＤＡＴＡエントリに連結される。この場合、各ＰＭ ＤＡＴＡエントリは、パターン・マッチが起こるべきフレームの中に見つけられなければならないが、しかし２組のマッチング・ビットは、それらのそれぞれのＭＩに従ってフレーム内のどこにでもあることができる。ＣＰビットが設定されない場合、パターン連結は、起こらない。最後のＰＭレジスタ２３３のＣＰフィールドは、そこに格納されている値に拘わらずクリアされたと見なされる。ＣＰが設定されている数値の最も低いＰＭレジスタ２３３は、連結されたパターンに用いられるパターン・マッチング制御及び属性情報（ＭＩを除く）を含む。各連結されたパターンに対して、ＭＩフィールドは、（ＭＩがクリアされたままである場合）全てのパターンがフレームの最初の４バイトに対してマッチしようと試みないように、適切な４バイトの倍数に設定されねばならない。
【００２１】
反転（ＩＶ）フィールドは、真又は相補形式でフレームに対するパターンの比較を可能にする。例えば、反転が設定されない（ＩＶ＝０）とき、パターン・マッチは、データ・マッチが生じる（例えば、ＰＭＤＡＴＡが受信されたフレームに見つけられる）ときのみ生じる。反転が設定された（ＩＶ＝１）とき、パターン・マッチは、データ・マッチが生じない（例えば、ＰＭＤＡＴＡが受信されたフレームに見つけられない）ときのみ生じる。
【００２２】
ＰＭＡＣフィールドは、フレームのフィルタリングをパターン・マッチングに基づいて制御する。ＰＭＡＣは、２ビットを格納し、その２ビットは、（ｉ）対応のパターンに関するパターン・マッチングがイネーブルされるかどうかと、（ｉｉ）パターン・マッチングが対応のパターンに関してイネーブルされる場合、パターン・マッチングの効果が１回完了したこととを指示する。例えば、ＰＭＡＣフィールドが００である場合、特定のエントリに関するパターン・マッチングがディスエーブルされ、パターン・マッチングが対応のパターンに関して生じなく、そしてパターン・マッチング論理２３２が、次のＰＭレジスタ２３３の中の次のパターンに自由に移動する。ＰＭＡＣフィールドが００でない場合、パターン・マッチングが、イネーブルされる。ＰＭＡＣフィールドが１１である場合、フレームは、パターン・マッチの際に拒絶される。ＰＭＡＣフィールドが１０である場合、フレームは、連続の検索がディスエーブルされる（ＣＳＥ＝０）ならば絶対的に受け入れられか、又は連続の検索がイネーブルされる（ＣＳＥ＝１）ならば条件付きで受け入れられるかのいずれかである。ＰＭＡＣフィールドが０１である場合、フレームは、受け入れも拒絶もされない。この場合、パターンは、マッチが生じた場合フレームを受け入れ又は拒絶するため用いられる判定基準ではなく、そして情報は、パターン・マッチ結果について事後処理のため収集されるが、しかし収集された情報に基づいてフレームを受け入れ又は拒絶するための判定はされない。事後処理は、前のパターンに基づいて又はデスティネーション・アドレス認識に基づいて受け入れられるフレーム上のデータをファイリング又は抽出することを含み、又は他の分類機能を含むことができる。フレームは、ハッシュ・プロセス、別のパターン・マッチング・プロセス、又は類似のものにより後で受け入れられることができる。
【００２３】
図２を再度参照すると、ＤＭＡ２１０は、受信バッファ２１１、抽出エンジン２１２、パターン属性レジスタ２１３、バッファ記述子及びファイリング・プロセッサ（ＢＤＦＰ）２１４、ステータス・レジスタ２１５、及びバッファ記述子アドレス・レジスタ２１６を含む。本明細書で説明される論理ブロックは、例示であり、そしてことなる実施形態は、機能の異なる論理仕切りを有し得る。例えば、一実施形態において、ＤＭＡ２１０は、抽出、バッファ記述子処理及びファイリング処理を実行するメモリ制御器を含むように想定し得る。
【００２４】
受信バッファ２１１は、メッセージ・フレームを受信ＦＩＦＯ２２０から受信するよう結合されている。ステータス・レジスタ２１５は、パターン・ステータス（ＰＳ）情報を受信ＦＩＦＯ２２０から受信するよう結合されている。パターン・ステータスは、パターン番号（例えば、ＰＭレジスタ番号）及び対応のパターン・ヒット指示を含む。ＦＩＦＯ制御器２２２は、そのような情報の転送を制御するためＤＭＡ２１０に結合されている。受信バッファ２１１は、フレーム・データをバス・インターフェース・ユニット１７０に接続１７２を介して与えるよう結合されている。
【００２５】
抽出エンジン２１２は、抽出制御情報を受信バッファ２１１に与えて、どのフレーム情報がキャッシュ１２０へ送るため抽出されるべきであるかを指示するよう結合されている。抽出エンジン２１２は、その抽出された情報についての属性をバス・インターフェース・ユニット１７０に接続１７２を介して与えるよう結合されている。例えば、抽出エンジン２１２は、受信ＦＩＦＯによりメモリ及び／又はキャッシュに送られたデータが抽出されたか又は正常であるかどうかと、それがメモリ１３０に格納されるか、又はそれら両方がメモリ１３０に格納され、且つキャッシュ１２０にスタッシュされるかどうかとを指示し、そしていずれの優先度情報は、データと関連付けられる。ステータス・レジスタ２１５は、パターン・ステータス情報を抽出エンジン２１２に与えて、どのフレーム・データが抽出されるべきであるかを指示する。抽出エンジン２１２はまた、抽出制御情報をパターン属性レジスタ２１３から受信するよう結合される。例えば、パターン属性レジスタ２１３は、抽出インデックス及び抽出長さを抽出エンジン２１２に与える（以下で説明する。）。
【００２６】
パターン属性レジスタ２１３は、どのバッファ・キューにフレーム・データ（ＰＭＦ）をファイリングするかを指示するファイリング情報をバッファ記述子アドレス・レジスタ２１６に与えるよう結合されている。ステータス・レジスタ２１５は、マッチングされた実際のパターンの指示のようなパターン・マッチ情報をＢＤＦＰ２１４に与えるよう結合されている。バッファ記述子アドレス・レジスタ２１６は、各バッファ記述子キュー（ＢＤＱ４１０，４２０，４３０及び４４０）のための基底アドレスと、各キュー・ポインタ（ＢＤＱ＿ＢＡＳＥ、ＢＤＱ＿ＣＵＲＲＥＮＴ、及びＢＤＱ＿ＮＥＸＴ）と、デフォルト・キューをＢＤＦＰ２１４に与えるよう結合されている。ＢＤＦＰ２１４は、アドレス及びデータ情報をバス・インターフェース・ユニット１７０に接続１７２を介して与えるよう結合されている。
【００２７】
パターン属性レジスタは、マッチが発生した際の活動、フレーム情報をファイルする場所、フレーム情報を抽出する時、及び受信フレーム及びそれらの関連のバッファ記述子を格納する仕方を指定するためユーザにより書き込まれる。合計１６個のレジスタ又はエントリは、現在説明している実施形態においてサポートされる。１つのそのようなレジスタ（又は代替レジスタ）は、デフォルト・レジスタとして指定され、そしてパターン・マッチが生じないときの活動を指定するための情報を含み得る。図５を参照すると、各エントリは、抽出されたキャッシュ（例えば、Ｌ２キャッシュ）書き込みタイプ（ＥＬＣＷＴ）、バッファ記述子キャッシュ書き込みタイプ（ＢＤＬＷＴ）、キュー分類（ＱＣ）、パターン・マッチ・ファイル（ＰＭＦ）、パターン・マッチ抽出（ＰＭＥ）、抽出されたインデックス（ＥＩ）、及び抽出された長さ（ＥＬ）を含む。他のビット・フィールドは、任意の数の他の機能をイネーブルする又はサポートするため含められ得る。例えば、データ・スヌープ・ビット（ｄａｔａ  ｓｎｏｏｐ  ｂｉｔ）は、受信されたフレームをメモリに対してスヌーピングすること、又は受信されたバッファ・データ・メモリ・アクセスをスヌーピングすることをサポートするため含められ得る。この場合、メモリに対するアクセスが存在するとき、キャッシュは、メモリに対する読み出し又は書き込みアクセスをスヌーピングすることができ、それによりキャッシュは、アドレスを検出し、次いで、例えば、キャッシュに格納されたデータのコピーを無効化すること、メモリからのキャッシュ・データを更新すること、又はデータをメモリに格納することと実質的に並列にデータをキャッシュに格納することのような適切な活動を取ることができる。パターン属性レジスタは、説明した情報のコンテンツのための例示的メモリ場所である。他の実施形態は、他のビット構成、分散されたレジスタ場所、等々を含む、そのような情報コンテンツを格納するための他の構成を含み得る。
【００２８】
抽出された記述子キャッシュ書き込みタイプ（ＥＬＣＷＴ）フィールドは、抽出されたデータに関して実行するための書き込みトランザクション・タイプを指定する。抽出書き込みトランザクションは、パターン・マッチング抽出（ＰＭＥ）フィールドが設定される場合に生じ、対応のパターン・マッチが生じ、そして抽出長さ（ＥＬ）フィールドが非ゼロである。一実施形態において、ＥＬＣＷＴが００である場合、割り当てが実行されない。ＥＬＣＷＴが０１である場合、抽出が生じない。ＥＬＣＷＴが１０である場合、キャッシュ行が割り当てられる。そして、ＥＬＣＷＴが１１である場合、キャッシュ行が、割り当てられ、そしてロックされる。連結されたパターン構成の場合、用いられるＥＬＣＷＴは、最低の数値パターン属性レジスタからである。キャッシュへの書き込みは、スヌープを用いて実行される。
【００２９】
バッファ記述子キャッシュ書き込みタイプ（ＢＤＬＷＴ）フィールドは、受信フレームのためのバッファ記述子に関して実行するための書き込みタイプを指定する。これは、パターン・マッチが生じた場合、ＰＭＦ又はＰＭＥの値に拘わらず生じる。キャッシュへの書き込みは、スヌープを用いて実行される。一実施形態において、ＢＤＬＷＴが００である場合、割り当てが、実行されない。ＢＤＬＷＴが１０である場合、キャッシュ行が、割り当てられる。そして、ＢＤＬＷＴが１１である場合、キャッシュ行が、割り当てられ、そしてロックされる。
【００３０】
パターン・マッチ抽出（ＰＭＥ）フィールドは、パターン・マッチ・ベースの抽出がイネーブルされるかどうかを指示する。パターン・マッチ抽出ビットが設定される（ＰＭＥ＝１）場合、抽出がイネーブルされる。パターン・マッチ抽出ビットが設定されない（ＰＭＥ＝０）場合、抽出がディスエーブルされる。
【００３１】
キュー分類（ＱＣ）は、ＰＭＦフィールドが設定され且つ対応のパターン・マッチが生じる場合到来フレームをファイルする受信キュー分類を指定する。連結されたパターン構成の場合、用いられるＱＣは、最初の４バイト・パターンからである。ＱＣが００である場合、キュー＃０が、用いられ、そしてＢＤＱ０＿ＢＡＳＥにより指定されたアドレスで開始するバッファ記述子が、用いられる。ＱＣが０１である場合、キュー＃１が、用いられ、そしてＢＤＱ１＿ＢＡＳＥにより指定されたアドレスで開始するバッファ記述子が、用いられる。ＱＣが１０である場合、キュー＃２が、用いられ、そしてＢＤＱ２＿ＢＡＳＥにより指定されたアドレスで開始するバッファ記述子が、用いられる。ＱＣが１１である場合、キュー＃３が、用いられ、そしてＢＤＱ３＿ＢＡＳＥにより指定されたアドレスで開始するバッファ記述子が、用いられる。
【００３２】
パターン・マッチ・ファイル（ＰＭＦ）フィールドは、フレームがメモリ１３０の中のどこにファイルされるかを決定するためＱＣフィールドが用いられるかどうかを指示する。例えば、ＰＭＦ＝０であり且つマッチが生じる場合、デフォルト属性レジスタの中のＱＣフィールドが、フレームがファイルされる場所を決定するため用いられる。ＰＭＦ＝１であり且つマッチが生じる場合、マッチされたパターンに対応するレジスタの中のＱＣフィールドが、フレームがファイルされる場所を決定するため用いられる。
【００３３】
パターン属性レジスタ２１３はまた、パターン・マッチが生じ且つパターン属性レジスタ２１３の中のパターン・マッチ抽出（ＰＭＥ）ビットが設定される場合、用いられるべき抽出インデックス及び抽出長さを指定するためユーザにより書き込まれる。抽出されたインデックス（ＥＩ）は、それからデータを抽出することを始める受信フレーム内の最初のバイトを指す。ＤＭＡ制御器２１０は、パターン・マッチ抽出フィールドが設定され（ＰＭＥ＝１）且つ対応のパターン・マッチが生じる場合抽出を実行するためこのフィールドを用いる。連結されたパターン構成の場合（ＣＰ＝１）、用いられるＥＩは、最低の数値レジスタ（例えば、連結されたチェーンの中の最初のレジスタ）からである。抽出された長さ（ＥＬ）フィールドは、受信されたフレームから抽出するためバイトの数を指定する。ＤＭＡ制御器２１０は、パターン・マッチ抽出フィールドが対応のパターン・マッチのため設定される（ＰＭＥ＝１）場合抽出を実行するためこのフィールド抽出を実行するためこのフィールドを用いる。連結されたパターン構成の場合、最低の数値パターン属性レジスタからのＥＬが、用いられる。ＥＬがゼロである場合、抽出は、行われない。
【００３４】
図４は、複数の例示的バッファ記述子キューＢＤＱ０、ＢＤＱ１、ＢＤＱ２、…ＢＤＱＭを示すブロック図である。各バッファ記述子キューは、例えば、ＢＤＱ０：ＢＤ０４１２、ＢＤ１ ４１４、ＢＤ２ ４１６、…ＢＤＮ４１８に関して示された格納場所のような幾つかのバッファ記述子を含む。各バッファ記述子キューは、リング（環状）構造を有し、そして３つのポインタ、ＢＤＱ＿ＢＡＳＥ、ＢＤＱ＿ＣＵＲＲＥＮＴ、及びＢＤＱ＿ＮＥＸＴを介してアクセスされる。各バッファ記述子格納場所は、メモリ１３０及び／又はキャッシュ１２０に格納された受信されたフレーム情報についての情報を格納する。例えば、そのような情報は、ステータス及び制御４５２、データ長さ４５４、データ・バッファ・ポインタ４５６、パターン・マッチ・ステータス４５８、関連の抽出インデックス４６０、抽出長さ４６２、及びバイト・カウント４６４を含む。各バッファ記述子キューは、対応のフレームに関して異なる優先度を表す。図１に示されるように、バッファ記述子キューは、メモリ１３０に格納され、そしてまた時々、ＢＤＬＷＴが適切に設定される場合キャッシュ１２０に格納される。バッファ記述子キューは、フレーム・データの対応の抽出が生じる場合も又は生じない場合も格納され得る。
【００３５】
図６は、情報処理及び通信システム１００の例示的動作フローを示すフロー・チャートである。ひとたびフレームが動作６１０中に受信されると、ＡＤＦ２３０は、フレームが動作６２０中に受け入れられるべきかどうかを決定する。フレームを受け入れるプロセスは更に、本明細書では図７から図９を参照して説明される。フレームが判断６２０中に受け入れられない場合、ＡＤＦ２３０は更に、動作６１０でフレームを待つ。フレームが判断６２０中に受け入れられる場合、フレーム及びパターン・ステータスは、動作６３０中に一時キュー２３４から受信ＦＩＦＯ２２０へ与えられる。フレーム及びパターン・ステータスが受信ＦＩＦＯ２２０に渡された後で、パターン・ステータス及びフレーム・データは、動作６４０中にＤＭＡ２１０へ与えられる。ひとたびパターンがＤＭＡ２１０へ送られてしまうと、ＤＭＡ２１０は、動作６５０中にフレーム・データをメモリに格納することができる。また、動作６５０中に、パターン・マッチ・レジスタ２３３のイネーブルされたパターンと整合するいずれかのデータが、抽出され、そしてキャッシュ１２０にスタッシュされる。フレーム・データを格納し且つ抽出されたフレーム・データをスタッシュするプロセスは更に、本明細書では少なくとも図１０及び図１１を参照して説明される。
【００３６】
図３は、フレームの受信動作６１０中にアドレス／データ・フィルタ２３０により受信可能なフレームを有する例示的メッセージ・パケットを示す。図示のフォーマットは、イーサネット(登録商標)／ＩＥＥＥ８０２．３標準メッセージと互換性がある。メッセージ３００は、プリアンブル、フレーム開始デリミタ（ＳＦＤ）、及びフレームを含む。プリアンブル及びフレーム開始デリミタは、フレームを受信し処理する際にシステムを支援するためセットアップ情報を与える。プリアンブルは、受信器タイミング同期化のため用いられる交互になっている１と０の７バイト・フィールドを与える。例えば、各バイトは、値０ｘ５５を含む。フレーム開始デリミタは、フレームの始めを指示する。フレーム開始デリミタのための代表的値は、０ｘＤ５のシーケンスである（ビットの順序は最下位ビットが最初であるので１０１０１０１１の２値である）。図示のフレームは、６４バイトから１５１８バイトまでの長さを有し、そして６バイト・デスティネーション・アドレス（ＤＡ）、６バイト・ソース・アドレス（送信元アドレス）、２バイト・タイプ／長さフィールド、４６バイトから１５００バイトの論理リンク制御（ＬＬＣ）フレーム、及び４バイト・フレーム検査シーケンスを含む。
【００３７】
フレームのデスティネーション・アドレスは、３バイト・ベンダ・フィールド、及び３バイト・ユーザ値を含む。ユーザ値の最初のビットは、アドレスを個々のアドレス（０）又はグループ・アドレス（１）として識別する。２番目のビットは、アドレスがローカルに定義される（１）か、又はグローバルに定義される（０）かを指示する。図示のように、ソース・アドレス及びデスティネーション・アドレスは、４８ビットを含む。他の実施形態は、ＩＥＥＥ８０２．３仕様書のより前のバージョンにおける１６ビット・アドレスのような異なるアドレス長を用い得る。
【００３８】
タイプ／長さフィールドは、イーサネット(登録商標)・タイプ・フィールド及び／又はＩＥＥＥ８０２．３長さフィールドに対応する。タイプ・フィールドは、フレームの残りの部分で用いられるプロトコル（例えば、ＴＣＰ／ＩＰ）を示す。長さフィールドは、フレームのデータ部分の長さを指定する。一般的に、長さフィールドは、イーサネット(登録商標)とＩＥＥＥ８０２．３の両方のフレームを同じネットワーク上で使用することを容易にするためいずれのタイプ・フィールドから一意である。タイプ・フィールドは、１５３６（０ｘ０６００）以上でしかし６５５３５（０ｘＦＦＦＦ）未満の１０進数により識別される。その数が０と１５００との間（０ｘ００００から０ｘ０５ＤＣ）である場合、このフィールドは、ＭＡＣクライアント・データの長さを指示する。図示の実施形態において、１５０１から１５３６（０ｘ５ＤＤから０ｘ５ＦＦ）までの範囲は、定義されていない。
【００３９】
論理リンク制御（ＬＬＣ）は、例えば、ＦＤＤＩ、イーサネット(登録商標)、トークン・リング及び他のものようなメディアのタイプに拘わらずサービスをネットワーク層に与えることを担当している。ＬＬＣ層は、メディア・アクセス制御（ＭＡＣ）層とプロトコル・スタックの上位層との間で通信するためＬＬＣプロトコル・データ・ユニット（ＰＤＵ）を利用する。３つの変数が、ＬＬＣ−ＰＤＵを介した上位層へのアクセスを決定する。当該変数は、デスティネーション・サービス・アクセス・ポイント（ＤＳＡＰ）、ソース・サービス・アクセス・ポイント（ＳＳＡＰ）、及び制御変数を含む。ＤＳＡＰアドレスは、上位層のためのプロトコル情報を与えるステーション（局）内の一意の識別子を指定する。ＳＳＡＰは、ソース・アドレスに関する同じ情報を与える。
【００４０】
ＬＬＣフレームは、プリアンブル、及び情報フィールドを含む。プリアンブルは、ＤＳＡＰフィールド、ＳＳＡＰフィールド、及び制御フィールドを含む。情報フィールドは、データ、及びオプションのパディング（埋め込み）を含む。パディングは、一般的に、ＩＥＥＥ８０２．３標準で指定されるように６４オクテットの最小フレーム・サイズを保証するためデータが４６オクテット／バイトより小さい場合のみ必要とされる。８０２．３ｘにおいては、データ・フィールドの最初の２オクテットは、演算コード（ＯＰ）（ポーズ（休止）＝０ｘ０００１）として用いられ、そして２番目の２オクテットは、ポーズ時間（ＰＴ）パラメータ（オンのためポーズ時間＝０ｘ００００及びオフのためポーズ時間＝０ｘＦＦＦＦ）を送信するため用いられる。その上、３番目の２オクテット・フィールドは、延長されたポーズ制御パラメータ（ＰＴＥ）のため用いられることができる。ＬＬＣに代わりに、イーサネット(登録商標)・フレームは、類似のフィールドを有する異なるプロトコルを用いることができる。これらのフィールドの使用は用いられるプロトコルと共に変わるので、それらを検査してそれらのコンテンツを報告する能力は、イーサネット(登録商標)・フレーム処理を著しく促進することができ、そしてそのような能力は、パターン・マッチングを用いることにより増強され得る。
【００４１】
フレーム検査シーケンス（ＦＳＣ）は、プリアンブル、ＳＦＤ及びＣＲＣを除く全てのフィールド上の標準ＣＣＩＴＴ−ＣＲＣ多項式を用いて得られる標準の３２ビット巡回冗長検査（ＣＲＣ）を指定する。
【００４２】
図７及び図８は、パターン・マッチングを用いてメッセージをハッシュ・フィルタリングする方法を示すフロー・チャートである。図７を参照すると、到来フレームが動作６１０中に一時キュー２３４で受信された後で、パターン・マッチング論理２３２は、ＰＭレジスタ２３３にアクセスし、そして様々なエントリを連続して選択して、ＰＭレジスタ２３３に格納されているパターンが一時キュー２３４の中のフレーム情報に含まれているかどうかを決定する。
【００４３】
例えば、ＡＤＦ２３０は、パターン・マッチ・イネーブル・ビット（ＰＭＥＮ）を含むＡＤＦグローバル制御レジスタを検査して、パターン・マッチングがイネーブルされているかどうかを決定する。パターン・マッチングがイネーブルされていない（ＰＭＥＮ＝０）の場合、フローは、グループ・アドレス判断７１５に進む。パターン・マッチングがイネーブルされている（ＰＭＥＮが非ゼロである）場合、パターン・マッチング・プロセス７１０は、開始される。パターン・マッチング・プロセス７１０がフレームが受け入れられる又は拒絶されるという結果になる（これは、以下で図９を参照してより詳細に説明する。）場合、フローは、ブロック７１０から図示の「受け入れ」又は「拒絶」のフロー・チャート・ノードのうちのそれぞれのノードを介して図８のフレーム受け入れ動作８６０及フレーム拒絶動作８６０のうちのそれぞれの動作に進む。パターン・マッチング・プロセス７１０がフレーム受け入れ又は拒絶判断を行うという結果にならない場合、フローは、パターン・マッチング・プロセス７１０から図示の「判断／パターン・マッチが未検出」ノードを介して前述のグループ・アドレス判断７１５に進む。
【００４４】
グループ・アドレス判断７１５中に、受信部１８０は、受信されたフレームの中のアドレスがグループ・アドレスであるかどうかを決定する。現在説明されている実施形態においては、フレームのユーザ値の最初のビットは、アドレスを個々のアドレス（０）又はグループ・アドレス（１）として識別する。アドレスがグループ・アドレスでない場合、フローは、ステーション（局）・アドレス判断７２０に進む。アドレスがグループ・アドレスである場合、フローは、ブロードキャスト（放送）・アドレス判断７２５に進む。
【００４５】
ステーション・アドレス判断７２０中に、受信部１８０は、受信されたフレームの中のアドレスがフレーム・データとの正確な４８ビット比較を実行することによりステーション・アドレスであるかどうかを決定する。アドレスがステーション・アドレスであると決定される場合、フローは、ブロック７２０から図示の「受け入れ」フロー・ノードを介して図８のフレーム受け入れ動作８６０にすすみ、そしてフレームは、フレーム受け入れ動作８６０で受け入れられる。アドレスがステーション・アドレスでないと決定される場合、フローは、ハッシュ・ヒット判断７４０に進む。
【００４６】
ブロードキャスト判断７２５中に、受信部１８０は、受信されたフレームの中のアドレスがブロードキャスト・アドレスであるかどうかを決定する。代表的ブロードキャスト・アドレスは、０ｘＦＦＦＦＦＦ−ＦＦＦＦＦＦのアドレスである。アドレスがブロードキャスト・アドレスであると決定された場合、フローは、ブロードキャストがイネーブル化されているかの判断７３０に進む。アドレスがブロードキャスト・アドレスでないと決定された場合、フローは、前述のハッシュ・ヒット判断７４０に進む。
【００４７】
ブロードキャストがイネーブルされているかの判断７３０中に、受信部１８０は、ブロードキャスト機能がイネーブルされているかどうかを決定する。ブロードキャスト機能は、ＡＤＦグローバル制御レジスタ・ビットＢＣ＿ＲＥＪがリセットされるときイネーブルされる。ブロードキャスト機能がイネーブルされる場合、フローは、ブロック７３０から図示の「受け入れ」フロー・チャート・ノードを介して図８のフレーム受け入れ動作８６０に進み、そしてフレームは、フレーム受け入れ動作８６０で受け入れられる。ブロードキャスト機能がイネーブルされない場合、フローは、プロミスキャス（無差別）・モード判断７３５に進む。
【００４８】
プロミスキャス・モード判断７３５中に、受信部１８０は、プロミスキャス・モードが、イネーブルされるかをどうかを決定する。プロミスキャス・モードは、ＡＤＦグローバル制御レジスタ・プロミスキャス・ビットがセットされる（ＰＲＯＭ＝１）ときイネーブルされる。受信部１８０がプロミスキャス・モードであるとき、パターン・マッチングにより拒絶されなかった全てのフレームは、受け入れられる。一般的に、プロミスキャス・モードは、テストのため用いられ、そしてめったに用いられない。プロミスキャス・モードがイネーブルされる場合、フローは、ブロック７３５から図示の「受け入れ」フロー・チャート・ノードを介して図８のフレーム受け入れ動作８６０に進み、そしてフレームは、フレーム受け入れ動作８６０で受け入れられる。プロミスキャス・モードがディスエーブルされる場合、フローは、ブロック７３５から図示の「拒絶」フロー・チャート・ノードを介して図８のフレーム拒絶動作８７０に進み、そしてフレームは、フレーム拒絶動作８７０で拒絶される。
【００４９】
パターン・マッチングがプロミスキャス・モード判断７３５の前に又はそれと平行して（又は、さもなければ、プロミスキャス・モード判断７３５の結果としての受け入れの前に）動作７１０で実行されるので、全てのアドレスからのフレームがフレームの拒絶を起こすパターンを含む１又はそれより多い特定のフレームを除いて受け入れられる識別力のあるプロミスキャス・モード（ｄｉｓｃｒｉｍｉｎａｔｉｎｇ  ｐｒｏｍｉｓｃｕｏｕｓ  ｍｏｄｅ）が用いられ得る。例えば、特定のアドレスは、他の全てのアドレスが受け入れられる一方パターン・マッチングの支援を得て拒絶され得る。
【００５０】
ハッシュ・ヒット判断７４０中に、受信部１８０は、フレーム・デスティネーション・アドレスについてハッシュ・ヒットが起こったかどうかを決定する。４８ビット・デスティネーション・アドレスが３２ビット巡回冗長検査（ＣＲＣ）チェックサムの一部分を用いることにより２５６ビン（又は、他の実施形態においてはそれより多くのビン）のうちの１つのビンにマップされる。例えば、多数のアドレス１２２２に対して発生された多数の対応のＣＲＣ１２２４を示す図１２を参照されたい。行１２０１−１２１０の各行の各１６進ＣＲＣ１２２４は、同じ行の６バイト１６進デスティネーション・アドレスに対応する。
【００５１】
情報処理及び通信システム１００のセットアップ中に、ＣＲＣチェックサムのビットを用いて、ハッシュ・テーブルの中へインデックスする。一実施形態において、８個のビットを用いて、２５６ビン・テーブルをインデックスする。８ビット・フィールドのより高次の３ビットを用いて、個人ハッシュ・テーブル及び／又はグループ・ハッシュ・テーブルの中の８ハッシュ・バケット・レジスタ（ｂｕｃｋｅｔ  ｒｅｇｉｓｔｅｒｓ）のうちの１つを選択する。より低次の５ビット・フィールドは、選択された３２ビット・レジスタ内の１ビットを選択する。同じチェックサムは、制御器がフレームを受信するとき用いられる。到来アドレスのＣＲＣチェックサムがグループ／個人ハッシュ・テーブルの中に設定されるビットを選択する場合、ハッシュ・ヒットが、起きたことになる。さもなければ、ハッシュ・ヒットは、起きていないことになる。
【００５２】
図示の実施形態において、ＣＲＣの最初の８ビットは、ハッシュ・テーブルの中の１つのビットを選択する。行１２０１−１２０３及び１２０６のアドレスは、システムにより受信されることになり、従って、ハッシュ・テーブルをセットアップするため用いられた。行１２０１において、１６進値０ｘ０４は、ハッシュ・バケット・ビン４に対してマップする。行１２０２において、１６進値０ｘ０Ｆは、ハッシュ・バケット・ビン１５に対してマップする。行１２０３において、１６進値０ｘ１５は、ハッシュ・バケット・ビン２１に対してマップする。行１２０６において、１６進値０ｘＣＢは、ハッシュ・バケット・ビン２０３に対してマップする。こうして、バケット・ビン４、１５、２１及び２０３のいずれかを選択するＣＲＣを有するアドレスは、そのようなアドレスが受信されるときハッシュ・ヒットである。
【００５３】
ハッシュ・テーブルの有効性は、アドレスの数が増大するにつれ低下する。例えば、２５６ビン・ハッシュ・テーブルに格納されたアドレスの数が増大するにつれ、膨大な数のハッシュ・テーブル・ビンがセットされ、意図しないフレームの著しく小さい小部分がメモリに到達するのを妨げられる。ハッシュ・フィルタリングの１つの利点は、ハッシングの速度が、デスティネーション・アドレス・リストの中のアドレスの数に依存しないことである。また、パターン・マッチング無しのハッシング単独プロトコルは、１組の選択されたアドレスとマッチするフレームを拒絶するため用いられることができないことに注目すべきである。それは、意図しないアドレスが、受信されてしまった筈であるフレームの拒絶をもたらす、ハッシュ・テーブル内の同じビットに対して、マッチすることができるからである。従って、ハッシュ・フィルタリングのみが、メモリに到達するフレームのポスト・フィルタリングを必要とする不完全なフィルタリングをもたらす。これは、図１２に示される受信されたデスティネーション・アドレスを参照して以下に一例として説明される。
【００５４】
ハッシュ・ヒット判断７４０中に、各受信されたアドレスに関するＣＲＣを用いて、ハッシュ・バケット・ビンを選択する。選択されたビンがヒットを指示する場合、ハッシュ・ヒットが生じたことになる。例えば、アドレス１２０１−１２０３及び１２０６−１２１０のいずれかが受信されたとき、ビン４、１５、２１及び２０３のうちの１つが、選択され、そしてハッシュ・ヒットが、生じたことになる。従って、アドレス１２０４又はアドレス１２０５が受信されたとき、ビン４、１５、２１及び２０３のうちのどれも選択されなく、そしてハッシュ・ヒットは、生じていないことになる。フレームは、典型的には、ハッシュ・ヒットが生じなかったとき拒絶される。このように、アドレス１２０４及びアドレス１２０５は、拒絶される。しかしながら、図１２のアドレス１２０７−１２１０は、ハッシュ・ヒットを発生したが、しかし情報処理及び通信システム１００による受け取り及び受け入れのための意図されたアドレスではない。従って、フィルタリングの別の手段を採用しなければならない。
【００５５】
情報処理及び通信システム１００は、パターン・マッチングを用いて、到来アドレスを更にフィルタリングし、それによりプロセッサ／ソフトウエア・ベースのポスト・フィルタリングの必要性が、最小にされ、又は排除すらされる。例えば、パターンは、ＰＭレジスタに格納され得て、それによりハッシュ・ヒットをミスリードすることを起こすアドレスは、拒絶され得る。図示の実施形態において、アドレスは、それらのアドレスが特定のベンダＩＤ（デスティネーション・アドレスの最初の２４ビット）用に意図されてない場合拒絶されることができる。０ｘ００５０ＦＣ０４のパターンは、ＰＭＤＡＴＡとして０ｘＦＦＦＦＦＦ００のＰＭ ＭＡＳＫと共に格納されてしまう。このように、０ｘ００５０ＦＣを最初の２４ビットの中に有していない各アドレスは、パターン・マッチングにより拒絶される。この場合、アドレス１２０７−１２０９は、拒絶されるが、しかし１２１０は、そのベンダＩＤが所望のベンダＩＤとマッチするので拒絶されない。
【００５６】
更なるパターンが、プロセスを改善するため格納され得る。例えば、２つのパターンを用いる。即ち、第１のパターンは、ＰＭ ＤＡＴＡ０ｘ００５０ＦＣ０４及び０ｘＦＦＦＦＦＦＦＦのＰＭ ＭＡＳＫを、そして第２のパターンは、０ｘＦＦＦＦＦＦＦＦ−ＦのＰＭＭＡＳＫを有するＰＭ ＤＡＴＡ０ｘ００５０ＦＣ０３−Ｃを用い得る。こうして、ハッシュ・ヒットであるがしかしその最初の３２ビット内に０ｘ００５０ＦＣ０４を且つその最初の３６ビット内に０ｘ００５０ＦＣ０３−Ｃを持たない各アドレスは、パターン・マッチング及びハッシングを通じて効果的に無視され得る。この場合、アドレス１２０７−１２１０は、パターン・マッチング及びハッシングに起因して効果的に拒絶され、そして所望のアドレスのみが、情報処理及び通信システム１００により受け入れられる。
【００５７】
こうして、受信されたアドレス１２０１−１２１０は、様々な異なる結果を引き起こす。アドレス１２０４及び１２０５は、ハッシュ・ミスを引き起こし、従って受け入れられない。アドレス１２０１−１２０３及び１２０６−１２１０は、ハッシュ・ヒットを引き起こす。アドレス１２０１−１２０３は、ハッシュ・ヒット及びパターン・マッチを、第１のパターンがその中に見つけられることに起因して引き起こす。従って、アドレス１２０１−１２０３が、受け入れられる。アドレス１２０６は、ハッシュ・ヒット及びパターン・マッチを、第２のパターンがその中に見つけられることに起因して引き起こす。従って、アドレス１２０６が、受け入れられる。アドレス１２０７−１２１０は、第１及び第２のパターンがその中に見つけられないので、ハッシュ・ヒットを引き起こしながら、パターン・マッチをもたらさない。従って、アドレス１２０７−１２１０は、受け入れられない。
【００５８】
一般に、３２個のグループ・アドレスがハッシュ・テーブルに格納され、且つランダムなグループ・アドレスが受信された場合、ハッシュ・テーブルは、高いパーセンテージ（例えば、或る事例では、８５％程度又はそれより高いパーセンテージ）のグループ・アドレス・フレームがメモリに到達するのを阻止する。現在の開示のパターン・マッチング無しでは、情報処理及び通信システム１００上で動作するソフトウエアは、それらのアドレスが正しいアドレスを含むかどうかを決定するため、メモリ１３０に到達するそれらのアドレスを更にフィルタリング（即ち、ポスト・フィルタリング）しなければならないであろう。前述の例では、アドレス１２０７−１２１０は、パターン・マッチングを誘発される拒絶条件がトリガされること無しに、更なるポスト・フィルタリングを含むプロセッサ１１０を要求したであろう。
【００５９】
図８を参照すると、受信部１８０は、パターン・マッチングが、パターン・マッチがイネーブルされたかの判断８４５中に、選択されたレジスタの中の選択されたパターンＰＭＤＡＴＡに関してイネーブルされるかどうかを決定する。パターン・マッチングがイネーブルされない場合（ＰＭＥＮ＝０）、フローは、ハッシュ／プロミスキャス判断８５５に進む。パターン・マッチングがイネーブルされる場合（ＰＭＥＮ＝１）、パターン・マッチング・プロセス８５０が、開始される。パターン・マッチング・プロセス８５０が（図９を参照して以下で更に詳細に説明されるように）フレームが受け入れられ又は拒絶されることをもたらす場合、フローは、ブロック８５０から図示の「受け入れ」及び「拒絶」のフロー・チャート・ノードのそれぞれのノードを介してフレーム受け入れ動作８６０及びフレーム拒絶動作８７０のそれぞれの動作に進む。フレームの受け入れ又は拒絶の判断を行わないで、パターン・マッチがパターン・マッチング・プロセス８５０中に行われる場合、又はパターン・マッチが行われない場合、フローは、パターン・マッチング・プロセス８５０から図示の「判断／パターン・マッチが未検出」ノードを介して、パターン・マッチが検出されなかったかどうかの判断８５２に進む。
【００６０】
現在説明している図示の実施形態におけるパターン・マッチが検出されなかったかどうかの判断８５２に言及すると、１６個のパターンのいずれもがパターン・マッチが検出されたことをもたらさなかった場合、フローは、判断８５２から図示の「拒絶」フロー・チャート・ノードを介してフレーム拒絶動作８７０に進む。他の実施形態において、フレームは、プロセッサ１１０により更にフィルタリングするため保持され得る。変形の実施形態において、フレームは、パターンが検出されたフレームより低い優先度を与えられ、それによりプロセッサ１１０は、低い信頼度フレーム（ハッシュ・ヒットを有するがしかしパターン・マッチが無い。）の前に高い信頼度フレーム（ハッシュ・ヒット及びパターン・マッチを有する。）に焦点を合わせる。別の変形の実施形態においては、フレームは、異なる処理要素に対応する異なるキューに格納され得る。１６個のパターンのうちの少なくとも１つがパターン・マッチが検出されたことをもたらした場合、フローは、判断８５２から図示の「判断無し」のフロー・チャート・ノードを介して前述のハッシュ／プロミスキャス判断８５５に進む。これまで説明した図７及び図８の要素は、メディア・アクセス制御機能に対応する。
【００６１】
ハッシュ／プロミスキャス判断８５５中に、データ・リンク機能は、判断無しのパターン・マッチ（例えば、受け入れ無し且つ拒絶無し）があったか、又はパターン・マッチが無かったとき実行される。受信部１８０（例えば、ＡＤＦ２３０の状態マシン）は、完全なハッシュ・ヒットが生じたかどうか及び／又はプロミスキャス・モードがイネーブルされるかどうかを決定する。完全なハッシュ・ヒットは、１つのアドレスのみに一義的に対応するハッシュ・ヒット及びパターン・マッチの両方が起きたとき起きる。対照的に、高い信頼度のハッシュ・ヒットは、少ない数のアドレスであるがしかし２個以上のアドレスに対応するハッシュ・ヒット及びパターン・マッチが起きるとき起きる。高い信頼度のハッシュ・ヒットは、その高い信頼度のアドレスが実際に求められたアドレスである確率を増強するパターン・マッチングの使用に起因して従来のアドレス・フィルタリングを越えて増強された性能を与える。システム及び／又はネットワーク特性を用いたパターンの注意深い選択は、ハッシュ・ヒットが完全である一層高い確率をもたらすことができる。完全なハッシュ・ヒットが起きたか又はプロミスキャス・モードがイネーブルされる場合、受信されたフレームは、フレーム受け入れ動作８６０で受け入れられる。完全なハッシュ・ヒットが起こらず、またプロミスキャス・モードがイネーブルされない場合、フローは、完全アドレス・マッチ判断８６５に進む。
【００６２】
完全アドレス・マッチ判断８６５中に、プロセッサ１１０は、完全アドレス・マッチが起きたかどうかを決定する。情報処理及び通信システム１００は、当該アドレスと情報処理及び通信システム１００に既知のアドレスとの直接比較を実行する。情報処理及び通信システム１００は、受信されたアドレスを優先キュー又は類似のものに格納し、それにより受け入れの高い予測可能性を有するアドレス（高い信頼度フレーム）が、受け入れの低い予測可能性を有するアドレス（低い信頼度フレーム）より前に処理される。そのような完全且つ直接の比較は、情報処理及び通信システム１００の処理資源の観点からコストが高い。従って、本明細書で説明されるパターン・マッチング及びハッシングが、そのようなコストの高い直接アドレス比較を回避するため求められる。こうして、情報処理及び通信システム１００は、そのシステムの性能を増強するためできるだけ多く直接アドレス比較なしにしたパターン・マッチングを用いることができる。完全アドレス・マッチがある場合、受信されたフレームは、フレーム受け入れ動作８６０で受け入れられる。完全アドレス・マッチが無い場合、受信されたフレームは、フレーム拒絶動作８７０で拒絶される。
【００６３】
図９は、情報処理及び通信システム１００により受信されたメッセージ・アドレスをパターン・マッチングする方法を示すフロー・チャートである。フレームは、パターン・マッチが生じたかどうかに依存して受け入れられ又は拒絶され得る。メッセージ・フレームのいずれかの部分が、ＩＰアドレスを含むマッチのため検査され得る。図９の動作は、最終処分（受け入れ又は拒絶）が別のパターン・マッチを試みる前に１つのパターン・マッチの発生により命令されない場合、パターン・マッチングは、対応のパターン・マッチがアクセプタ・インディケータが許す（例えば、ＰＭＡＣ＝１）各パターンに対してイネーブルされるとき（ＰＭＥＮ＝１）イネーブルされる。パターン・データがイネーブルされた場合、メッセージ・データは、パターン・マッチに関して検査される。パターン・マッチ・データ・セットがイネーブルされない場合、又はパターン・マッチが見つけられない場合、次のパターンが選択され、そして処理が繰り返される。連続検索がイネーブルされる場合、検索が、マッチに関係なく次のパターンに関して続けられる。
【００６４】
受信動作９３５を参照すると、到来フレームの複数のバイトは、その到来フレームを受け入れるか又は拒絶するかの判断を行うまで一時的格納のため一時キュー２３４の中に受信される。到来フレームの複数のバイトはまた、パターン・マッチング論理２３２及びアドレス認識及びハッシュ論理２３８に与えられて、それによりそのような判断は、上記複数のバイトが一時キュー２３４により受信されている間に行われ得る。複数のバイトが受信動作９３５中に受信されてしまった後で、フローは、パターン・マッチ決定動作９０５に進む。
【００６５】
パターン・マッチ決定動作９０５を参照すると、パターン・マッチング論理２３２は、ＰＭレジスタ２３３に格納されたパターン・マッチ・データが受信されたフレームの中のデータとマッチするかどうかを決定する。例えば、パターン・マッチング論理は、ＰＭレジスタ２３３のうちの最初のＰＭレジスタの中のＰＭＤＡＴＡを到来フレームと、それが一時キュー２３４に格納されるにつれ比較する。一時キュー２３４は、判断が行われるまでフレームを格納するため用いられる。パターン・マッチは、例えば、ＰＭＤＡＴＡの各ビット（最大４バイトまで）がメッセージ・インデックスＭＩに従って配置されたメッセージ・データの各ビットとマッチする場合に起きる。マッチングは、最大２５２バイトのオフセットを有するフレームの中に最大２５６バイトまでの深さで生じ得る。或る一定のＰＭＤＡＴＡは、対応のＰＭ ＭＡＳＫによりマスクされ得る。例えば、ＰＭ ＤＡＴＡの各ビットは、対応のＰＭ ＭＡＳＫビットがクリアされる場合マッチに関して検査されない。前のパターンの連結パターン（ＣＰ）フィールドが設定される場合、両方のＰＭＤＡＴＡフィールド（現在のＰＭ ＤＡＴＡと前のＰＭレジスタのＰＭ ＤＡＴＡ）は、フレームの中に見つけられる場合のみ生じる。ＰＭＡＣフィールドは、対応のＰＭ ＤＡＴＡがイネーブルされるかどうかを決定し、そしてそれがイネーブルされる場合、マッチの際に取るべき活動方針が取られる。パターン・マッチ決定動作９０５は、受信動作９３５と平行に行い得る。
【００６６】
パターン・マッチ決定動作９０５を参照すると、パターン・マッチングがディスエーブルされる場合（例えば、ＰＭＡＣ＝００）、フローは、フレームの終わり（ＥＯＦ）又はキュー・フル判断（キューがフルかどうかの判断）９３０まで進む。パターン・マッチがパターン・マッチ決定動作９０５中に見つけられない場合、フローはまた、ＥＯＦ又はキュー・フル判断９３０まで進む。パターン・マッチが有り、且つパターン・マッチングが判断９１０中にディスエーブルされない（例えば、ＰＭＡＣ≠００）場合、フローは、フレーム受け入れ判断９１５に進む。
【００６７】
ＥＯＦ／キュー・フル判断９３０を参照すると、一時キュー２３４がフル（一杯）でなく、且つフレームの終わりがまだ受信されていない（で更にフレームが拒絶されてなかった）場合、受信動作９３５中に一時キュー２３４の中に追加のバイトを受信することを継続し、そしてフローは、パターン・マッチ決定動作９０５に進んで、受信された追加のフレーム情報についてパターン・マッチングを開始する。フレームの終わりが受信されたか、又は一時キュー２３４がフルである場合、フローは、全拒絶モード判断９４０に進む。
【００６８】
全拒絶モード判断９４０を参照すると、ＡＤＦ２３０が全拒絶モードにあると決定された場合、フレームは、拒絶され、そして動作フローは、どの対応のフローが図９に示されるパターン・マッチング・フローを開始したかに応じて図７か又は図８のいずれかに示されるように継続する。ＡＤＦ２３０が全拒絶モードでない場合、フレームについての判断は行われず、そしてフローは、どのフローが図９に示されるパターン・マッチングを開始したかに応じて図７か又は図８のいずれかに示されるように継続する。
【００６９】
フレーム受け入れ判断９１５を参照すると、ＡＤＦ２３０が１つのパターンに関してフレームを受け入れている場合（例えば、特定のＰＭＤＡＴＡに関してＰＭＡＣ＝１０）、フレームは、条件付きで受け入れられ、そしてフローは、連続的検出判断９４５に進む。ＡＤＦ２３０が１つのパターンに関してフレームを受け入れていない場合（例えば、特定のＰＭＤＡＴＡに関してＰＭＡＣ≠１０）、フローは、フレーム拒絶判断９２０に進む。
【００７０】
フレーム拒絶判断９２０を参照すると、ＡＤＦ２３０が１つのパターンに関してフレームを拒絶している場合（例えば、特定のＰＭ ＤＡＴＡに関してＰＭＡＣ＝１１）、到来フレームは、それが拒絶のＰＭＡＣ値と関連付けられたＰＭ ＤＡＴＡを含む（、又はさもなければそのようなＰＭ ＭＡＳＫ、ＣＰ等のような他のファクタを考慮してマッチを引き起こす）ので拒絶される。次いで、フローは、どのフローが図９に示されるパターン・マッチングを開始したかに応じて図７か又は図８のいずれかに示されるように継続する。ＡＤＦ２３０がパターンに関してフレームを拒絶していない場合（例えば、特定のＰＭＤＡＴＡに関してＰＭＡＣ≠１１であり、この場合ＰＭＡＣ＝０１である。）、フローは、連続的検索判断９２５に進む。
【００７１】
連続的検索判断９２５を参照すると、パターンの連続的検索がイネーブルされる場合（例えば、ＣＳＥ＝１）、フローは、ＥＯＦ又はキュー・フル判断９３０に進む。連続的検索が連続的検索判断９２５中にイネーブルされない場合（例えば、ＣＳＥ＝０）、前述のパターン・マッチについて判断を行わず、そしてフローは、全拒絶モード判断９４０に進む。
【００７２】
連続的検索判断９４５を参照すると、パターンの連続的検索がイネーブルされる場合（例えば、ＣＳＥ＝１）、フローは、ＥＯＦ又はキュー・フル判断９５０に進む。連続的検索が連続的検索判断９４５中にイネーブルされない場合（例えば、ＣＳＥ＝０）、到来フレームは、受け入れられる。フレームは、それがＰＭＤＡＴＡを含む（、又はさもなければそのようなＰＭ ＭＡＳＫ、ＣＰ等のような他のファクタを考慮してマッチを引き起こす）ので受け入れられ、そしてパターン・マッチングが、イネーブルされ（ＰＭＡＣ＝１０）、そして更なる検索を行うことが必要である（ＣＳＥ＝０）。次いで、フローは、どのフローが図９に示されるパターン・マッチングを開始したかに応じて図７か又は図８のいずれかに示されるように継続する。
【００７３】
ＥＯＦ／キュー・フル判断９５０を参照すると、フレームの終わりが受信されたか、又は一時キュー２３４がフルである場合、到来フレームが、受け入れられる。フレームは、パターン・マッチが起きたので受け入れられ、パターン・マッチングが、イネーブルされ（ＰＭＡＣ＝１０）、そしてフレームの終わりが到達されてしまい、又は一時キューがフルとなり、そのため更なるパターン・マッチングが可能でない。次いで、フローは、どのフローが図９に示されるパターン・マッチングを開始したかに応じて図７か又は図８のいずれかに示されるように継続する。
【００７４】
一時キュー２３４がフルでなく、且つフレームの終わりがまだＥＯＦ／キュー・フル判断９５０中に受信されていなかった場合、追加のバイトが、受信動作９５５中に一時キュー２３４の中に受信され、そしてフローは、パターン・マッチ決定動作９６０に進んで、次のパターンに関して追加の受信されたフレーム情報についてパターン・マッチングを開始する。パターン・マッチ決定動作９６０は、上記で説明したパターン・マッチ決定動作９０５に機能的に類似している。受信動作９５５は、パターン・マッチ決定動作９６０と平行して行い得る。パターン・マッチ決定動作９６０後に、フローは、パターン・マッチ判断９６５に進む。
【００７５】
パターン・マッチ判断９６５を参照すると、パターン・マッチングが現在選択されたパターン（例えば、現在選択されたパターンＰＭレジスタ２３３の中のＰＭＤＡＴＡ）に関してディスエーブルされる場合（例えば、ＰＭＡＣ＝００）、フローは、ＥＯＦ／キュー・フル判断９５０に進む。パターン・マッチがパターン・マッチ決定動作９６５中に見つけられない場合、フローはまた、ＥＯＦ／キュー・フル判断９５０に進む。パターン・マッチがあり、且つパターン・マッチングがパターン・マッチ決定動作９６５中にディスエーブルされない場合（例えば、ＰＭＡＣ≠００）、フローは、フレーム否拒絶判断（フレームを拒絶しないかどうかの判断）９７０に進む。
【００７６】
フレーム否拒絶判断９７０を参照すると、ＡＤＦ２３０が次のパターン（例えば、対応のＰＭ ＤＡＴＡ）に関してフレームを拒絶していない（例えば、ＰＭＡＣ＝０１又はＰＭＡＣ＝１０）、フローは、ＥＯＦ／キュー・フル判断９５０に進む。さもなければ、到来フレームは、拒絶パターン（ＰＭＡＣ＝１１）が検出されたので拒絶される。次いで、フローは、どのフローが図９に示されるパターン・マッチングを開始したかに応じて図７か又は図８のいずれかに示されるように継続する。
【００７７】
図１０を参照すると、受け入れられたメッセージを図１のシステム内で処理する方法が示されている。図示の実施形態の１つの利点は、パケット内の臨界的データへのシステム・アクセスがそれがより高いレベルの資源を用いること無しに受信されたときそれを検出し、且つ後続のより早いアクセスのためそれを記述子情報と一緒にキャッシュに置くことにより増強されることができることである。
【００７８】
図示のフローは、パターン・ステータスがパターン・ステータス受信動作１００５中にＤＭＡ２１０に与えられ且つステータス・レジスタ２１５の中に置かれたとき開始される。一般的に、その後、フレーム・データは、メモリ１３０にファイルされ、及び／又はパターン・ステータス情報に応じてキャッシュ１２０にスタッシュされる。ファイルすることには、パケット署名に基づいてメモリ内のパケットをグループ化することが含まれ、そして抽出には、パケットの特定の部分を（例えば、抽出インデックス及び長さ値を用いることにより）その位置を突きとめることが含まれ、そしてスタッシング（スタッシュすること）には、抽出されたデータをプロセッサ・キャッシュ空間の中にコピーすることが含まれる。抽出は、プロセッサ・キャッシュ・メモリに割り当て、そしてそれをロックすることができるが、しかしソフトウエアは、抽出中にＤＭＡによりロックされたそのキャッシュの中の全てのデータのロックを解くことを担っている。抽出されたデータは、フレーム・データから除去されず、むしろ、全てのフレーム・データは、メモリに格納され、そして抽出データのみが、プロセッサ・キャッシュにコピーされる。そのようなファイリング及びスタッシングは、以下でより詳細に説明される。
【００７９】
バッファ記述子選択動作１０１０を参照すると、ＤＭＡ２１０のＢＤＦＰ２１４は、バッファ記述子を、パターン・ステータス、及びパターン・マッチ属性レジスタ２１３の中のキュー分類（ＱＣ）フィールドに基づいて選択する。ＱＣフィールドは、バッファ記述子キュー１２２／１３２のどちらを用いるべきかを決定する。パターン・ステータスは、適切なＱＣフィールドに対するポインタを含む。パターン・ステータスはまた、あるならば、どのパターン・マッチが起きたかを指示する。パターン・マッチが起きた場合、マッチされたパターンは、データをフレームから抽出させ、そして抽出されたデータ１２４としてキャッシュ１２０にスタッシュさせる。従って、バッファ記述子キュー１２２が、バッファ記述子キュー１３２に加えて選定される。パターン・マッチが起きなかった場合、抽出は生じないであろうし、その結果バッファ記述子キュー１３２のみを用いることをもたらす。バッファ記述子選択動作１０１０後に、フローは、抽出準備動作１０１５に進む。
【００８０】
抽出準備動作１０１５中に、抽出エンジン２１２は、パターン・ステータスがパターン・マッチを指示する場合、抽出インデックス（ＥＩ）及び抽出長さ（ＥＬ）をパターン属性レジスタ２１３から獲得する。抽出準備動作１０１５後に、フローは、ＢＤＱ使用可能判断１０２０に進む。
【００８１】
ＢＤＱ使用可能判断１０２０を参照すると、ＢＤＦＰ２１４は、選択されたバッファ記述子キュー（ＢＤＱ）が使用可能かどうかを決定する。即ち、ＢＤＦＰ２１４は、選択されたＢＤＱの中に空の空間があるかどうかを決定する。選択されたＢＤＱが使用可能である場合、フローは、フロー・チャート・ノード「Ａ」を介してＢＤＱポインタ更新動作１０３０に進む。選択されたＢＤＱが使用可能でない場合、フローは、フラッシュ動作１０２５に進み、そこで、フレーム及びステータス・フレーム長さが、受信ＦＩＦＯ２２０からフラッシュされ、そしてフローは、パターン・ステータス受信動作１００５に進む。
【００８２】
ＢＤＱポインタ更新動作１０３０を参照すると、ＢＤＦＰ２１４は、バッファ記述子キューの現在ポインタ（ＢＤＱ＿ＣＵＲＲＥＮＴ）が次のバッファ記述子キュー（ＢＤＱ＿ＣＵＲＲＥＮＴ＝ＢＤＱ＿ＮＥＸＴ）を指すよう更新する。現在のＢＤＱポインタが更新された後で、フローは、ＢＤＱエンプティ判断（ＢＤＱが空であるかの判断）１０３５に進む。
【００８３】
ＢＤＱエンプティ判断１０３５を参照すると、ＢＤＦＰ２１４は、ＢＤＱ＿ＣＵＲＲＥＮＴにより指し示されたエントリが空（エンプティ）であるかどうかを決定する。現在のＢＤＱエントリが空でない場合、選択されたバッファ記述子キューは、使用不能のマーク付け動作１０４０中に使用不能とマーク付けされ、そしてフローは、フラッシュ動作１０２５に進む。現在のＢＤＱエントリが空である場合、フローは、転送動作１０４５に進む。
【００８４】
転送動作１０４５を参照すると、ＢＤＦＰ２１４は、フレーム・データを受信ＦＩＦＯ２２０から受信バッファ２１１へ転送する。当該転送は、フレームの終わり（ＥＯＦ）が受信される、又は受信バッファ２１１がフルになるまで続行する。フレーム・データが転送された後で、フローは、ＥＯＦ判断１０５０に進む。
【００８５】
ＥＯＦ判断１０５０を参照すると、フレームの終わりが転送動作１０４５中に受信されなかった場合、フローは、選択的抽出及びスタッシング動作１０６０に進む。フレームの終わりが転送動作１０４５中に受信された場合、フローは、ステータス・フレーム長さ獲得動作１０５５に進み、そのステータス・フレーム長さ獲得動作１０５５中に、抽出エンジン２１２は、ステータス・フレーム長さをステータス・レジスタ２１５から獲得する。ステータス・フレーム長さ獲得動作１０５５後に、フローは、選択的抽出及びスタッシング動作１０６０に進む。
【００８６】
データは、選択的抽出及びスタッシング動作１０６０中にキャッシュ１２０の中にスタッシュするため受信されたフレームから制御可能に抽出される。選択的抽出及びスタッシング動作１０６０は、以下で図１１を参照してより十分に説明されるであろう。選択的抽出及びスタッシング動作１０６０後に、フローは、ＥＯＦ判断１０６５に進む。
【００８７】
ＥＯＦ判断１０６５を参照すると、フレームの終わりが選択的抽出及びスタッシング動作１０６０中に受信された場合、フローは、ＥＯＦ更新判断１０８０に進む。フレームの終わりが選択的抽出及びスタッシング動作１０６０中に受信されなかった場合、フローは、バッファの終わり（ＥＯＢ）判断１０７０に進む。
【００８８】
ＥＯＦ更新判断１０８０を参照すると、ＢＤＦＰ２１４は、現在のバッファ記述子キューのステータス及び制御情報を更新する。例えば、ＢＤＦＰ２１４は、抽出生起ビットを現在のＢＤＱ１２２に設定して、抽出されたデータ１２４がキャッシュ１２０に格納されたことを指示する。次のＢＤＱポインタ（ＢＤＱ＿ＮＥＸＴ）は、選択されたＢＤＱの中の次の位置を指すよう設定される。現在のＢＤＱのコンテンツは、キャッシュにＢＤＬＷＴに従ってコピーされる。例えば、パターン・マッチが起きた場合、そしてＢＤＬＷＴが００である場合、割り当ては、実行されない。ＢＤＬＷＴが１０である場合、キャッシュ１２０の行が割り当てられ、そしてＢＤＬＷＴが１１である場合、キャッシュ１２０の行が、割り当てられ、そしてロックされる。ＥＯＦ更新判断１０８０後に、フローは、パターン・ステータス受信動作１００５に進み、それにより、より多くのデータが、次のフレームから処理され得る。
【００８９】
ＥＯＢ判断１０７０を参照すると、メモリ１３０の中のフレーム・データ・バッファ１３４の終わりが選択的抽出及びスタッシング動作１０６０中に遭遇される場合、フローは、ＥＯＢ更新動作１０７５に進む。データ・バッファの終わりが選択的抽出及びスタッシング動作１０６０中に遭遇されない場合、フローは、上記で説明した転送動作１０４５に進む。
【００９０】
ＥＯＢ更新動作１０７５を参照すると、ＢＤＦＰ２１４は、現在のバッファ記述子キューのステータス及び制御情報を更新する。例えば、ＢＤＦＰ２１４は、現在のＢＤＱ１２２の中の抽出生起ビットを設定して、抽出されたデータ１２４がキャッシュ１２０に格納されたことを指示する。次のＢＤＱポインタ（ＢＤＱ＿ＮＥＸＴ）は、選択されたＢＤＱの中の次の位置を指すよう設定される。現在のＢＤＱのコンテンツが、キャッシュにＢＤＬＷＴに従ってコピーされる。ＥＯＢ更新動作１０７５後に、フローは、ノードＡに進み、それにより、より多くのデータが、同じフレームから処理されることができる。
【００９１】
図１１は、６４バイト・バッファを用いて図１のシステムによりメッセージの複数の一部分を抽出してスタッシングする方法を示すフロー・チャートである。図１１に示される方法は、図１０の選択的抽出及びスタッシング動作１０６０により呼び出される。
【００９２】
図１１を参照すると、抽出エンジン２１２は、抽出が抽出要求判断１１０５中に、所与のパターン・マッチのため要求されたかどうかを決定する。抽出エンジン２１２はまた、抽出追加（ＥＸ＿ＡＤＤ）フィールド及び抽出長さ（ＥＬ）フィールドのような様々な抽出フィールドを検査する。抽出追加フィールドは、抽出長さに対応の抽出インデックスを加えてもの（例えば、ＥＸＡＤＤ＝ＥＬ＋ＥＩ［１１：１５］）に等しい。抽出が要求された場合（ＰＭＥ＝１）、抽出追加値はゼロより大きく、抽出長さはゼロより大きく、そしてフローは、ＥＬ≦６４判断１１２５に進む。抽出が要求されない場合、抽出追加値がゼロであり、又は抽出長さがゼロであり、フローは、整列判断１１１０に進む。
【００９３】
整列判断１１１０を参照すると、目標アドレスが６４バイトの整列されたアドレスで無い場合、フローは、ＭＡＸ（３２Ｂ）送信動作１１２０に進み、そこで最大の３２バイトの正常データがメモリ１３０に送られる。ＭＡＸ（３２Ｂ）は、３２バイトを含む最高のバイト数であり、（例えば、ここで、ｘはバイト数とすると、ＭＡＸ（ｘＢ）≦ｘバイトである。）。目標アドレスが６４バイトの整列されたアドレスである場合、フローは、ＭＡＸ（６４）送信動作１１２０に進み、そこでＭＡＸ（６４Ｂ）の正常データが、メモリ１３０に送られる。ＭＡＸ（３２Ｂ）送信動作１１１５か又はＭＡＸ（６４Ｂ）送信動作１１２０かのいずれかの後で、抽出フローを出て、そしてフローは、図１０のＥＯＦ判断１０６５に進む。
【００９４】
ＥＩ≦６４判断１１２５を参照すると、抽出インデックスが６４より大きい場合、抽出されるべきデータは、まだ到着されてなく、そしてフローは、ＭＡＸ（６４Ｂ）送信動作１１３０に進み、そこでＭＡＸ（６４Ｂ）の正常データが、メモリ１３０に送られる。ＭＡＸ（６４Ｂ）送信動作１１３０後に、抽出インデックスは、ＥＩ減分動作１１３５中に６４だけ減分され（例えば、ＥＩ＝ＥＩ−６４）、そして抽出フローを出て、フローは、図１０のＥＯＦ判断１０６５に進む。
【００９５】
ＥＩ≦６４判断１１２５を再び参照すると、抽出インデックスが６４以下である場合、フローは、相対的ＥＩ格納動作１１４０に進む。相対抽出インデックスは、メモリ１３０の中のデータ・バッファ内の１つの位置に対するインデックスであり、そこから、抽出されたデータが、始まる。相対抽出インデックスは、それが後にＥＯＢ更新動作１０７５又はＥＯＦ更新判断１０８０（図１０）中にメモリ１３０の中の適切なＢＤＱに及び／又はキャッシュ１２０に書き込まれるまでＢＤＦＰ２１４によりＤＭＡ２１０に内部的に格納される。相対的ＥＩ格納動作１１４０後に、フローは、ＥＩ≦３２判断１１４５に進む。
【００９６】
ＥＩ≦３２判断１１４５を参照すると、抽出エンジン２１２は、抽出インデックスとの比較を実行し、そして例えば、抽出エンジン２１２内のＤＭＡ２１０に内部的に格納されている抽出データ・フラグを検査する。例えば、抽出インデックスが３２より大きく、そして抽出データ・フラグが真でない場合、フローは、ＭＡＸ（３２Ｂ）送信動作１１５０に進み、そこでＭＡＸ（３２Ｂ）の正常データが、メモリ１３０に送られる。ＭＡＸ（３２Ｂ）送信動作１１５０後に、抽出データ・フローを出て、そしてフローは、図１０のＥＯＦ判断１０６５に進む。
【００９７】
ＥＩ≦３２判断１１４５を再び参照すると、抽出インデックスが３２以下であるか、又は抽出データ・フラグが真である場合、フローは、３２Ｂ未満判断１１６０に進む。受信されたフレームから抽出すべき少なくとも３２バイトのデータがある場合（例えば、ＥＸ＿ＡＤＤ≧３２Ｂ）、フローは、３２Ｂ送信動作１１７０に進み、そこで３２バイトの抽出データが、ＥＬＣＷＴに従って、メモリ１３０に送られ、キャッシュ１２０にコピーされる。例えば、ＥＬＣＷＴが００である場合、割り当てが実行されず、ＥＬＣＷＴが０１である場合、抽出が生じず、ＥＬＣＷＴが１０である場合、キャッシュ行が割り当てられ、そしてＥＬＣＷＴが１１である場合、キャッシュ行が割り当てられ且つロックされる。受信されたフレームから抽出すべき３２バイト未満のデータがある場合（例えば、ＥＸ＿ＡＤＤ＜３２Ｂ）、フローは、切り上げ動作１１６５に進み、そこでＥＸ＿ＡＤＤは、３２の値に切り上げられ、そしてフローは更に、３２Ｂ送信動作１１７０に進む。
【００９８】
３２Ｂ送信動作１１７０後に、フローは、減分動作１１７５に進み、その減分動作１１７５中に、抽出追加フィールドは、抽出された３２バイト・セグメントの数だけ減分される（例えば、ＥＸ＿ＡＤＤ＝ＥＸ＿ＡＤＤ−３２）。減分動作１１７５後に、抽出データ・フラグは、フレームの終わり（ＥＯＦ）が到達されたか又はＥＸ＿ＡＤＤ＝０である場合クリア動作１１８０中にクリアされる。クリア動作１１８０後に、抽出フローを出て、そしてフローは、図１０のＥＯＦ判断１０６５に進む。
【００９９】
一実施形態において、メッセージ・フレームの一部分が、情報処理及び通信システム１００によりパケット制御器１６０のＭＡＣ１９０で受信される（図１及び図６、動作６１０を参照）。メッセージ・フレームのその受信された部分（「受信されたフレーム」）は、図２のアドレス／データ・フィルタ２３０の一時キュー２３４に与えられる。フレームは、アドレス／データ・フィルタ２３０により処理されて、それが受け入れられるべきか又は拒絶されるべきかを決定する（図６、動作６２０を参照）。アドレス認識、ハッシング、完全なハッシングのためパターン・マッチングを有するハッシング、及びパターン・マッチング（図７〜図９）が、アドレス認識及びハッシュ論理２３８及びパターン・マッチング論理２３２により上記「受信されたフレーム」について実行される。アドレス認識及びハッシュ論理２３８は、ハッシング、及びいずれの必要なフルのアドレス比較を実行する。ＰＭレジスタ２３３は、マッチングされるべきパターンの数に対応するレジスタの数を含む。パターン・マッチング論理２３２は、パターン・マッチングを、ＰＭレジスタ２３３に格納されているコンフィギュレーション値に基づいて（例えば、連続検索及び／又は連結能力を用いて）実行する。パターン・マッチング及びハッシング又は他のフェール・セーフ条件後に受け入れられた場合、受信されたフレーム及びパターン・ステータス情報（パターン・マッチ結果）は、受信ＦＩＦＯ２２０に転送される（図６、動作６３０参照）。
【０１００】
次いで、受信されたフレームは、受信バッファ２１１に転送され、そしてパターン・ステータス情報は、ＤＭＡ２１０のステータス・レジスタ２１５に転送される（図６、動作６４０参照）。抽出エンジン２１２は、パターン属性レジスタ２１３及びステータス・レジスタ２１５にアクセスして、データが受信バッファ２１１の中の受信されたフレームから抽出されるべきかを決定し、そして適用できるようなデータの抽出を制御する（図１０及び図１１参照）。ＢＤＦＰは、ステータス・レジスタ２１５及びバッファ記述子アドレス・レジスタにアクセスし、そしてメモリ１３０及び／又はキャッシュ１２０に書き込まれるべきアドレス及びデータ情報を発生する。ＢＤＦＰ２１４からのアドレス情報は、フレーム・データのためのデータ・バッファ内にデータ・バッファ・ポインタ（例えば、データ・バッファ・ポインタ４５６）、又はバッファ記述子キューの中の複数の次のエントリのうちの１つのエントリに対する１又は複数のポインタ（例えば、ＢＤＱ＿ＢＡＳＥ、ＢＤＱ＿ＣＵＲＲＥＮＴ、ＢＤＱ＿ＮＥＸＴ）を含む。データ情報は、図４に示される、ステータス及び情報４５２、データ長さ４５４、データ・バッファ・ポインタ４５６、パターン・マッチ・ステータス４５８、相対抽出インデックス４６０、抽出長さ４６２、及びバイト・カウント４６４を含む。
【０１０１】
次いで、フレームの全て又は一部分は、対応のバッファ記述子キュー１３２／１２２の中の対応の記述情報と一緒に、メモリ１３０にファイルされ（「正常データ」）、及び／又はキャッシュ１２０にスタッシュされる（「抽出されたデータ」）（図６、動作６５０、及び図１０及び図１１参照）。より詳細には、受信バッファ２１１は、正常な又は抽出されたフレーム・データをバス・インターフェース・ユニット（ＢＩＵ）１７０に与え、抽出エンジン２１２は、属性をＢＩＵ１７０に与え、当該ＢＩＵ１７０は、フレーム・データを正常データ又は抽出されたデータとして識別し、そしてＢＤＦＰ２１４は、アドレス情報及びバッファ記述子データをバッファ記述子アドレス・レジスタ２１６からＢＩＵ１７０へ与える。ＢＩＵ１７０は、フレーム・データをキャッシュ１２０及び／又はメモリ１３０に格納するためシステム・バス１４０に通す。正常フレーム・データは、少なくとも１つのデータ・バッファ１３４に格納され、そして正常フレーム・データについての記述子データは、バッファ記述子キュー１３２に格納される。抽出が生じた場合、抽出されたフレーム・データは、キャッシュ部分１２４に格納（「スタッシュ」）される。
【０１０２】
上記の記載は、本発明の少なくとも１つの実施形態を説明することを意図している。上記の記載は、本発明の範囲を定義することを意図するものではない。むしろ、本発明の範囲は、添付の特許請求の範囲で定義される。従って、本発明の他の実施形態は、上記の記載の態様に対する他の変形、変更、追加及び／又は改良を含む。
【０１０３】
一実施形態は、ユーザがより長いパターンを形成するため連結され且つ最初の２５６バイト内のフレームの一部分とマッチするため用いられることができる最大１６個の４バイト・パターンをプログラムすることを可能にする新規な形式のパターン・マッチングを組み込む。フレームを受け入れ／拒絶し、フレームをメモリの中の４つのキューのうちの１つのキューにファイルし、抽出されたフレーム・データをプロセッサのキャッシュに書き込むようプログラムされることができる１組の属性は、各パターンと関連付けられる。パターン・マッチング能力は、最大１６個の一義的４バイト・パターンのサポート、ビット毎ベースのパターン・マッチング、フレームの中への最大２５６バイト深さのマッチング範囲、最大２５６バイトのオフセット、最大６４バイトの４バイト増分のプログラム可能パターン・サイズ、マッチが検出されたときの受け入れ又は拒絶フレーム、及び正確なマッチのための最大８ユニキャスト・アドレスを含む。
【０１０４】
この実施形態は、パターン・マッチングのパワーをハッシュ・フィルタリングの使用と組み合わせて、ポスト・フィルタリングを必要としないアドレス認識方法を提供し、そして更なるソフトウエア介入を論理リンク制御器レベルで必要とする代わりにＭＡＣレベルで行うことができる。フレームの処理を促進するための１つの方法は、ハッシュ・テーブル上でヒットをたまたま獲得するいずれのデスティネーション・アドレスが本当に本システムが捜している複数のアドレスのうちの１つである信頼度を増大する方法である。２以上のアドレスが同じ８個の最上位ビットを有するＣＲＣを有するであろうから、パターン・マッチングを有するハッシュ・テーブルの使用は、ハッシュ・ヒットについて行われなければならない（アドレスを検索し、そしてそれを有効なデスティネーション・アドレスのリストと比較すること）余分の処理が無駄な努力でない機会を著しく増大させる方法を与える。これは、それが意図しないハッシュ・テーブル・ヒットにより引き起こされる余分のメモリバス利用を低減するので価値がある。ハッシュされることができるアドレスの数はまた、アドレスの数が増大するにつれハッシュ・テーブル有効度が低下することにより制限される。ユーザは最初にハッシュ・テーブルを作るので、そしてハッシュされるべきアドレスの数が通常比較的低い（３２から６４）ので、ユーザのアドレスの全てではないとしても大部分をカバーすることができるであろう共通のパターンを見つけることが比較的容易である。少数のパターン・マッチ・レジスタを用いて、ユーザは、所望のキューにファイルされる何かがヒットであり、そして比較テーブルを必要としないで処理されることができることを保証することができるであろう。
【０１０５】
一実施形態において、ＣＲＣチェックサムはグループ／個人ハッシュ・テーブルに設定されるビットを選択する場合、フレームは、パターン・マッチ結果が出るまで単純に条件付けされて受け入れられる。ベンダのコードが、例えば、マッチすべきパターンとして非常に高い有効性を有して用いられることができる。パターンがより選択的であれば（用いられるビットがより少ない）、高い信頼度のハッシュ・ヒット・キュー方法がより実効的になる。極めて選択的パターンの場合、ハッシュ・テーブルで用いられることができるアドレスの数は、増大され、そして依然実効的のままであることができる。この実施形態の別の利点は、フレームを拒絶するために良好なフレームを拒絶する危険性無しにそれ自体でハッシングすることを用いることができないのに対し、ハッシュ衝突の不確実さが排除されるので、組み合わされたパターン・マッチング及びハッシュ・フィルタリングを用いて、「ハッシングすることによるフレーム拒絶」を実行することができることにある。更なる柔軟性は、ユーザがパターン・マッチング及びハッシュが「マッチ・キュー無しの高い確率」で拒絶したフレームをファイルすることができ、それによりフレームは、上記方法の実効性を更に確認するため検査されることができることである。
【０１０６】
本明細書で説明されるように、ＡＤＦ２３０の様々な制御論理は、ＡＤＦ２３０の前述の構成要素の間に分散され、そして別々の論理ブロックとして図示されていない。代替として、例えば、ＡＤＦ２３０の全体動作を制御し且つパターン・マッチング及びハッシングの機能を含む状態マシンを表す別々の制御論理ブロックを含み得る。そのような状態マシンは、本明細書で説明される機能を実現するための或る一定数の状態を含むかもしれないであろう。例えば、状態マシンは、データが受信され且つフレームが受け入れられる際に、アイドル状態からパターン・ステータス状態へ遷移し得るであろう。パターン・ステータス状態において、パターン・ステータス情報は、受信ＦＩＦＯ２２０に対して使用可能にされ得る。次いで、状態マシンは、受信されたフレームが一時キュー２３４から送られる一時キュー・データ・フェーズへ遷移することができる。次いで、状態マシンは、デスティネーション・アドレス・フィルタリングと関連付けられたフレーム長さ及びステータス（例えば、ブロードキャスト・アドレス、グループ／シングル・アドレス、プロミスキャス・モード）が受信ＦＩＦＯ２２０に転送されるフレーム・ステータス状態に入る。他の状態及び状態マシンが、本明細書で説明される機能に従って実現され得る。
【０１０７】
一実施形態において、１つの方法は、メッセージを受信するステップと、第１のパターンに対応する第１のパターン・マッチが受信されたメッセージ内に検出されたかどうかを決定するステップであって、当該第１のパターンがパターン・マッチ・データにより指示され且つ対応の逆パターン・インディケータを有する、上記決定するステップとを含む。第１のパターン・マッチが検出されたとき、メッセージは、対応のパターン・マッチ受け入れインディケータに基づいて選択的に受け入れられる。対応の逆パターン・インディケータが第１の値を有する場合、第１のパターン・マッチは、第１のパターンが受信されたメッセージ内で検出されたとき検出され、そして対応の逆パターン・インディケータが第２の値を有する場合、第１のパターン・マッチは、第１のパターンが受信されたメッセージ内に検出されなかったとき検出される。
【０１０８】
更なる実施形態において、メッセージを受信するステップは、パケットの少なくとも１つの部分を受信するステップを含む。一実施形態において、パケットは更に、イーサネット(登録商標)・パケットとして特徴付けられる。更なる実施形態において、対応のパターン・マッチ受け入れインディケータは、受信されたメッセージの受け入れ、拒絶、及び受け入れも拒絶も無しのうちの１つを指示する。
【０１０９】
更なる実施形態において、第１のパターンは、対応の連続検索イネーブル・インディケータを有し、そこにおいて、メッセージは、対応のパターン受け入れインディケータ及び対応の検索イネーブル・インディケータに基づいて選択的に受け入れられる。別の実施形態において、第１のパターン・マッチが検出され、そして第１のパターンに対応するパターン・マッチ受け入れインディケータが受信されたメッセージの受け入れを指示する場合、受信されたメッセージは、第１のパターンに対応する連続検索イネーブル・インディケータが連続検索無しを指示するとき受け入れられる。また別の実施形態において、第１のパターン・マッチが検出され、そして第１のパターンに対応するパターン・マッチ受け入れインディケータが受信されたメッセージの受け入れを指示する場合、受信されたメッセージは、第１のパターンに対応する連続検索インディケータが連続検索を指示するとき受け入れられ、そして第２のパターンに対応する第２のパターン・マッチが、検出され、当該第２のパターンは、受信されたメッセージの拒絶を指示しない対応のパターン受け入れインディケータを有する。一実施形態において、第２のパターンは、パターン・マッチ・データにより指示され、そして第２のパターンに対応するパターン・マッチ受け入れインディケータが、受信されたメッセージを受け入れることと、受信されたメッセージを受け入れも拒絶もしないこととのうちの１つを指示する。一実施形態において、第２のパターンに対応するパターン・マッチ受け入れインディケータは、受信されたメッセージを受け入れることと、受信されたメッセージを受け入れも拒絶もしないこととのうちの１つを指示し、そしてパターン・マッチングが、第２のパターンに関してディセーブルされる。更に別の実施形態において、第２のパターンは、対応の逆パターン・インディケータを有し、そこにおいて、第２のパターンに対応する逆パターン・インディケータが第１の値を有する場合、第２のパターン・マッチは、第２のパターンが受信されたメッセージ内に検出されたとき検出され、そして第２のパターンに対応する逆パターン・インディケータが第２の値を有する場合、第２のパターン・マッチは、第２のパターンが受信されたメッセージ内に検出されなかったとき検出される。
【０１１０】
別の実施形態において、第１のパターン・マッチが検出され、そして第１のパターンに対応するパターン・マッチ受け入れインディケータが受信されたメッセージの受け入れを指示する場合、メッセージは、第１のパターンに対応する連続検索インディケータが連続検索を指示し、そして受信されたメッセージの拒絶を指示する対応のパターン・マッチ受け入れインディケータを有する第２のパターンに対応する第２のパターン・マッチが、検出されたとき受け入れられない。更なる実施形態において、第２のパターンは、対応の逆パターン・インディケータを有し、そこにおいて、第２のパターンに対応する逆パターン・インディケータが第１の値を有する場合、第２のパターン・マッチは、第２のパターンが受信されたメッセージ内に検出されたとき検出され、そして第２のパターンに対応する逆パターン・インディケータが第２の値を有する場合、第２のパターン・マッチは、第２のパターンが受信されたメッセージ内に検出されなかったとき検出される。
【０１１１】
別の実施形態において、本方法は更に、第１のパターンが検出されないときメッセージを拒絶するステップを含む。更に別の実施形態において、第１のパターンは、受信されたメッセージ内の位置で第１のパターン・マッチが検出されたかどうかを決定する当該位置を指示する対応のマッチ・インデックスを有する。別の実施形態において、第１のパターン・マッチが検出されたとき、本方法は更に、第２のパターン・マッチが受信されたメッセージ内に検出されたかどうか決定するステップであって、第１のパターン及び第２のパターンのそれぞれが対応の連結インディケータを有する、上記決定するステップを含み、そこにおいて、メッセージを選択的に受け入れることが、第１のパターンに対応するパターン・マッチ受け入れインディケータと、第１のパターンに対応する連結インディケータ及び第２のパターンに対応する連結インディケータのうちの少なくとも１つとに基づいている。この実施形態において、第２のパターン・マッチが検出され、そして第１のパターンに対応する連結インディケータと第２のパターンに対応する連結インディケータとのうちの少なくとも１つが第１のパターンと第２のパターンとの連結を指示する場合、メッセージは、第１のパターンに対応するパターン・マッチ受け入れインディケータが受信されたメッセージの受け入れを指示するとき選択的に受け入れられる。この実施形態において、第２のパターン・マッチが検出されず、そして第１のパターンに対応する連結インディケータと第２のパターンに対応する連結インディケータとのうちの少なくとも１つが第１のパターンと第２のパターンとの連結を指示するとき、第１のパターン・マッチが、検出されなかったと見なす。
【０１１２】
更に別の実施形態において、第２のパターンは、対応の逆パターン・インディケータを有し、そこにおいて、第２のパターンに対応する逆パターン・インディケータが第１の値を有する場合、第２のパターン・マッチは、第２のパターンが受信されたメッセージ内に検出されたとき検出され、そして第２のパターンに対応する逆パターン・インディケータが第２の値を有する場合、第２のパターン・マッチは、第２のパターンが受信されたメッセージ内に検出されなかったとき検出される。
【０１１３】
別の実施形態において、本方法は更に、ハッシュ・ヒットが生じたかどうかを決定するハッシュ機能を実行するステップを含む。この実施形態において、ハッシュ・ヒットが生じたとき、第１のパターン・マッチが、検出され、そして第１のパターンに対応するパターン・マッチ受け入れインディケータが、受信されたメッセージの受け入れを指示し、メッセージは、選択的に受け入れられる。
【０１１４】
別の実施形態において、メッセージが受け入れられたとき、本方法は更に、バッファ記述子キュー（ＢＤＱ）をパターン・マッチ属性に基づいて選択するステップと、メッセージを選択されたＢＤＱに従ってメモリに格納するステップと、受け入れられたメッセージの少なくとも一部分をキャッシュに選択的に格納するステップとを含む。この実施形態において、受け入れられたメッセージの上記一部分は、パターン・マッチ属性により指示される。更に別の実施形態において、パターン・マッチ属性は、第１のパターンに対応する複数のＢＤＱのうちの１つのＢＤＱであって選択されたＢＤＱに対応する当該１つのＢＤＱを指示する。更に別の実施形態において、パターン・マッチ属性は、第１のパターンに対応する。更に別の実施形態において、メッセージが受け入れられたとき、メッセージは更に、第２のパターンに対応する第２のパターン・マッチが存在するかどうか決定することを含み、パターン・マッチ属性は、第２のパターンに対応する。
【０１１５】
別の実施形態において、パターン・マッチ属性は、パターン・マッチ抽出インディケータを与える。この実施形態において、受け入れられたメッセージの一部分は、パターン・マッチ抽出インディケータが抽出がイネーブルされることを指示するときキャッシュに格納され、そして受け入れられたメッセージの上記一部分は、パターン・マッチ抽出インディケータが抽出がディセーブルされることを指示するときキャッシュに格納されない。別の実施形態において、パターン・マッチ属性は、抽出インデックス及び抽出長さを与えて、キャッシュに格納された受け入れられたメッセージの一部分を指示する。
【０１１６】
別の実施形態において、メッセージが受け入れられたとき、本方法は更に、選択されたＢＤＱの少なくとも一部分をキャッシュに格納するステップを含む。
【０１１７】
代替実施形態は、入力、パターン・マッチング論理、及びパターン・マッチ論理に結合された制御論理を含むパケット制御器に関連する。この実施形態において、入力は、メッセージを受信する。パターン・マッチング論理は、第１のパターンに対応する第１のパターン・マッチが受信されたメッセージ内に検出されたかどうかを決定する。パターン・マッチング論理は、少なくとも１つのパターン・マッチ・レジスタを含み、当該少なくとも１つのパターン・マッチ・レジスタは、第１のパターンを指示するパターン・マッチ・データを格納し、そして当該少なくとも１つのパターン・マッチ・レジスタは更に、第１のパターンに対応するパターン・マッチ受け入れインディケータと第１のパターンに対応する逆パターン・インディケータとを含むパターン・マッチ制御を格納する。制御論理は、第１のパターン・マッチが検出され、そして第１のパターンに対応するパターン・マッチ受け入れインディケータが受信されたメッセージの受け入れを指示するとき受信されたメッセージを選択的に受け入れる。対応の逆パターン・インディケータが第１の値を有する場合、第１のパターン・マッチは、第１のパターンが受信されたメッセージ内に検出されたとき検出される。対応の逆パターン・インディケータが第２の値を有する場合、第１のパターン・マッチは、第１のパターンが受信されたメッセージ内に検出されなかったとき検出される。
【０１１８】
更なる実施形態において、パターン・マッチ制御は更に、連結インディケータを含む。この実施形態において、パターンマッチング論理は、連結インディケータを用いて、第１のパターン・マッチが検出されたかどうかを決定する。別の実施形態において、連結インディケータが第１の値を有するとき、第１のパターン・マッチは、第１のパターン及び第２のパターンに対応する。この実施形態において、第２のパターンは、少なくとも１つのパターン・マッチ・レジスタ内に格納されている第２のパターン・マッチ・データにより指示される。別の実施形態において、連結インディケータが第２の値を有する場合、第１のパターン・マッチは、第１のパターンに対応し、第２のパターンに対応しない。別の実施形態において、パターン・マッチ制御は、第２のパターンに対応する逆パターン・インディケータを含む。
【０１１９】
別の実施形態において、パターン・マッチ制御は更に、連続検索インディケータを含む。この実施形態において、制御論理は、第１のパターン・マッチが検出され、そして第１のパターンに対応するパターン・マッチ受け入れインディケータが受信されたメッセージの受け入れを指示するとき、受信されたメッセージを連続検索インディケータに基づいて選択的に受け入れる。
【０１２０】
本明細書に記述したアーキテクチャは、単に例示であり、実際には、同じ機能を達成する多くの他のアーキテクチャを実行することができることが理解される筈である。抽象的に、しかし依然一定の意味において、同じ機能を達成するための構成要素のいずれの構成は、所望の機能を達成するように実効的に「関連付けられ」ている。従って、特定の機能を達成するため本明細書において組み合わされた任意の２つの構成要素は、アーキテクチャ又は中間構成要素に拘わらず所望の機能が達成されるように互いに「関連付けられ」ているとして見ることができる。同様に、そのように関連付けられた任意の２つの構成要素はまた、所望の機能を達成するため、互いに「動作的に接続されている」、又は「動作的に結合されている」と見ることができる。
【０１２１】
当業者は、論理ブロック間の境界が単に例示であり、代替実施形態は論理ブロック又は回路構成要素を合併させ、又は機能の代替分解を様々な論理ブロック又は回路構成要素に課し得ることを認めるであろう。更に、代替実施形態は、特定の構成要素の複数の実例を組み合わせ得る。
【０１２２】
更に、当業者は、上記で説明した動作の機能間の境界が単に例示であることを認めるであろう。複数の動作の機能は、単一の動作の中に組み合わされ得て、及び／又は単一の動作の機能は、追加の動作に分散され得る。更に、代替実施形態は、特定の動作の複数の事例を含み得て、そして動作の順序は、様々な他の実施形態において変えられ、又は更に並列に実行され得る。
【０１２３】
上記の詳細な説明が例示であるので、「一実施形態」が説明されるとき、それは、例示的実施形態である。従って、この文脈における単語「一」の使用は、１つで且つ唯１つの実施形態が説明した特徴を有することを示す意図ではない。むしろ、多くの他の実施形態は、例示の「一実施形態」の説明した特徴を有し得て、そして多くの場合有する。従って、上記で用いられるように、本発明が一実施形態の文脈で説明されるとき、その１つの実施形態は、本発明の多くの有り得る実施形態のうちの１つである。
【０１２４】
詳細な説明における用語「一実施形態」の使用についての上記の注意にも拘わらず、請求項に記載の構成要素の特定の数が添付の特許請求の範囲において意図される場合、そのような意図は、特許請求の範囲に明示的に記載され、そしてそのような記載がない場合、そのような限定が存在しない又は意図していないことが当業者に理解されるであろう。例えば、添付の特許請求の範囲において、請求項に記載された構成要素が「１つ」の特徴を有するよう記載されているとき、その構成要素は、記載された複数の特徴のうちの１つ且つ唯１つの特徴に限定されることを意図している。更に、請求項に記載された構成要素が、添付の特許請求の範囲において、「１つ（ｏｎｅ）」の特徴を含む又は備えると記載されるときは、その構成要素が、記載された複数の特徴のうちの１つ且つ唯１つの特徴に限定されることを意図していない。むしろ、例えば、「特徴（“ａ”ｆｅａｔｕｒｅ）」を含む請求項は、問題の特徴のうちの１又はそれより多くの特徴を含む装置又は方法と読むべきである。即ち、問題の装置又は方法が１つの特徴を含むので、当該請求項は、当該装置又は方法がそのような別の類似の特徴を含むかどうかに拘わらずにその装置又は方法を読むべきである。単語「ａ」を無限定の前置き冠詞として特許請求の範囲の特徴に対して使用することが、見つけ得る反対に対するいずれの相反する又は前例の判例法にも拘わらず、過去の多くの公判により採用された解釈と同一であるとして本出願人により採用されている。同様に、請求項に記載の構成要素が添付の特許請求の範囲において上記の特徴（例えば、「前記」特徴（“ｔｈｅ”ｆｅａｔｕｒｅ）を含む又は備えるとして記載されているので、その構成要素は、定冠詞の同一の使用により単に記載された複数の特徴のうちの１つ且つ唯１つの特徴に限定されないことを意図している。
【０１２５】
更に、特許請求の範囲における「少なくとも１つ」及び「１又はそれより多く」のような前置き句の使用は、たとえ同じ請求項が「１又はそれより多く」又は「少なくとも１つ」の前置き句及び英語の「ａ」又は「ａｎ」のような不定冠詞を含むときでも、請求項に記載の別の構成要素に対する不定冠詞「ａ」又は「ａｎ」の導入がそのようなに導入された請求項に記載の構成要素を含むいずれの特定の請求項を唯１つのそのような構成要素を含む発明に限定することを意味すると解釈すべきでない。同じことが、定冠詞の使用に対しても当てはまる。
【０１２６】
本発明の特定の実施形態が示されそして説明されたが、本明細書の教示に基づいて、様々な変更、代替構成、及び均等物が添付の特許請求の範囲から逸脱すること無しに用いられ得ることが当業者に明らかであろう。従って、添付の特許請求の範囲は、本発明の真の趣旨及び範囲内にある全てのそのような変化、変更等を特許請求の範囲の範囲内に包含する。更に、本発明は添付の特許請求の範囲によってのみ定義されると理解されるべきである。上記の説明は、本発明の実施形態の網羅的リストを提示することを意図していない。さもなければ明記していない場合、本明細書に提示された各例は、非限定の用語、非排他的の用語、又は類似の用語が各例で同時に表されていようといまいと、非限定の又は非排他的な例である。幾つかの例示的実施形態及びそれらに対する例示的変形の概要を説明する試みがなされたが、他の実施形態及び／又は変形が、添付の特許請求の範囲に定義される本発明の範囲内にある。
【図面の簡単な説明】
【０１２７】
【図１】図１は、本発明の一実施形態に従った情報処理及び通信システムを示すブロック図である。
【図２】図２は、図１の情報処理及び通信システムのパケット制御器の受信部分を示すブロック図である。
【図３】図３は、図１の情報処理及び通信システムにより受信可能で且つパース（構文解析）可能である例示的メッセージ・アドレス・フォーマットを示すブロック図である。
【図４】図４は、図１の例示的バッファ記述子キューを示すブロック図である。
【図５】図５は、図１の例示的パターン・マッチ及びパターン・マッチ属性レジスタを示すブロック図である。
【図６】図６は、図１の情報処理及び通信システムによる受信メッセージを処理する方法を示すフロー・チャートである。
【図７】図７は、図１の情報処理及び通信システムにより受信されたメッセージ・アドレスをハッシングし、パターン・マッチングする方法の一部を示すフロー・チャートである。
【図８】図８は、図１の情報処理及び通信システムにより受信されたメッセージ・アドレスをハッシングし、パターン・マッチングする方法の別の部分を示すフロー・チャートである。
【図９】図９は、図７の例示的フロー内における、図１の情報処理及び通信システムにより受信されたメッセージ・アドレスをパターン・マッチングする方法を示すフロー・チャートである。
【図１０】図１０は、図１の情報処理及び通信システム内において、受け入れられたメッセージを処理する方法を示すフロー・チャートである。
【図１１】図１１は、図１の情報処理及び通信システムによりメッセージの複数の部分を抽出し、スタッシュする方法を示すフロー・チャートである。
【図１２】図１２は、ハッシング及び／又はパターン・マッチングを用いて処理された多数のアドレスを示すテーブルである。
【図１】
2007512770.tif 000003
【図２】
2007512770.tif 000004
【図３】
2007512770.tif 000005
【図４】
2007512770.tif 000006
【図５】
2007512770.tif 000007
【図６】
2007512770.tif 000008
【図７】
2007512770.tif 000009
【図８】
2007512770.tif 000010
【図９】
2007512770.tif 000011
【図１０】
2007512770.tif 000012
【図１１】
2007512770.tif 000013
【図１２】
2007512770.tif 000014
【国際調査報告】
2007512770.tif 000015