(57)【要約】【課題】構文解析を行うプログラマブル状態マシンの状態遷移規則テーブルに状態遷移規則を格納するデータ構造によってサポートされる構文解析および検索の方法を含むディープ・パケット処理のための方法および装置を提供すること。【解決手段】次いでＢａＲＴ圧縮アルゴリズムを使用して状態遷移規則テーブルが圧縮される。各遷移規則は、テスト値、テスト・マスク、および次状態フィールドを含んでいる。第２の実施形態では、状態遷移規則テーブルが互いに素の状態空間に対応する複数の状態遷移規則テーブルに分割され、したがってストレージ・スペースの使用において柔軟性の向上が可能となる。最後に、構文解析および検索の方法を、同じハードウェアを使用して実施することができる。検索および構文解析の方法は、二者択一的に、または任意の組み合わせでワイヤスピードで実施することができる。
2005538624.tif 000002
【特許請求の範囲】
【請求項１】
結果として得られるアドレスを指すように入力単語連鎖（input word chain）内の単語パターンを識別することによってプログラマブル状態マシンのデータ構造を作成して、前記入力単語連鎖を構文解析する方法であって、
前記入力単語連鎖の前記単語パターンを識別するために、前記プログラマブル状態マシンの状態に対応する状態テーブルを作成するステップであって、各状態テーブル・エントリが、ｓビットの現在の状態、入力されたｎビットの単語、およびｓビットの次状態を含む前記作成するステップと、
前記ｓビットの現在の状態、前記入力されたｎビットの単語を含むテスト値、前記ｓビットの現在の状態と前記入力されたｎビットの単語との組み合わせのテスト・マスク、および前記ｓビットの次状態として表される３値一致状態をそれぞれ含む状態遷移規則エントリの数を低減するように前記エントリを変換することによって前記状態テーブル内のエントリ数を低減するステップと、
前記ステップの実行によって取得された前記低減された状態テーブル・エントリを、最も頻繁に使用される遷移規則の優先順位が最も高い状態の優先順位で配列するステップと
を含む方法。
【請求項２】
前記低減された状態テーブルのハッシュ・インデックスとして、前記ｓビットの現在の状態と前記入力されたｎビットの単語との組み合わせの中の１組のｉビット位置、および最大でＮ個のテーブル・エントリがハッシュ・インデックス値に一致し得るような整数Ｎを定義するステップと、
２ｉエントリを有する、前記ハッシュ・インデックスによってインデックス付けされた圧縮済み状態テーブルを作成するステップであって、各エントリが前記ハッシュ・インデックスの１つの値に対応しており、それぞれ同じハッシュ・インデックス値に対応し、優先順位の順に書き込まれる前記低減された状態テーブルの最大Ｎ個の遷移規則を有するステップと、
第２のバイナリ値に符号化された前記ハッシュ・インデックスのビット位置を除く第１のバイナリ値に符号化されたビットを有する、前記ハッシュ・インデックスに対応するｓ＋ｎビットのインデックス・マスクを保存し、前記圧縮済み空間テーブルのベース・アドレス・ポインタ（ＳＰ１、ＳＰ２）を保存するステップと、
をさらに含む請求項１に記載の方法。
【請求項３】
前記圧縮済み状態遷移規則テーブルを複数の圧縮済み状態遷移規則テーブルに分割するステップと、
前記分割された圧縮済み状態テーブルのそれぞれにおいて、前記状態遷移規則での前記次状態の前記分割された圧縮済みテーブルの前記インデックス・マスクおよびベース・アドレス・ポインタで各状態遷移規則を拡張するステップと
をさらに含む請求項１または２に記載の方法。
【請求項４】
請求項１ないし３のいずれか一項に従って作成されたプログラマブル状態マシンのデータ構造を使用して入力単語連鎖を構文解析する方法であって、
前記現在の状態、前記データ構造の現在のインデックス・ビット・マスク、および現在のベース・ポインタを初期化するステップと、
前記入力単語連鎖の第１の単語を前記現在の入力として定義するステップと、
前記インデックス・マスクに従って前記現在の状態および現在の入力から前記ハッシュ・インデックスを抽出するステップと、
前記現在のベース・ポインタによって示された前記空間テーブルにおいて、前記ハッシュ・インデックスに対応する前記エントリを検索し、複数の遷移規則が一致する場合、前記現在の状態および入力に一致する前記状態遷移規則を検索し、優先順位が最も高いものを選択するステップと、
前記次状態が最終状態ではない場合、前記現在の状態、前記データ構造の前記現在のインデックス・マスク、および前記現在のベース・ポインタの前記新しい値を抽出するステップと、
前記入力単語連鎖の次の単語を前記現在の入力として定義するステップと、
前記次の読み取られた状態が最終となるまで、直前のハッシュ・インデックスの抽出ステップ、新しい値の検索ステップおよび抽出ステップを繰り返すステップと
を含む方法。
【請求項５】
請求項１から３のいずれか一項に従って作成されたプログラマブル状態マシンのデータ構造を使用して入力単語連鎖に対応する結果として得られた値を検索する方法であって、前記圧縮済みテーブルが前記入力された単語のｎビット中から取得されたハッシュ・インデックスを使用して構築され、前記状態レジスタに対応する前記テスト・ベクトル内の２つの最左ビットは未使用であり、各遷移規則の次状態ビットは未使用であり、前記遷移規則の前記ベース・アドレス・ポインタは最終結果（Ｐ、Ｒ、Ｑ）を含む可能性があり、前記方法は
前記入力単語連鎖の第１の単語を前記現在の入力として定義するステップと、
前記インデックス・マスクに従って前記現在の入力から前記ハッシュ入力を抽出するステップと、
前記現在のベース・ポインタによって示された前記空間テーブルにおいて、前記ハッシュ・インデックスに対応する前記エントリを検索し、複数の遷移規則が一致する場合、前記現在の状態および入力に一致する前記状態遷移規則を検索し、優先順位が最も高いものを選択するステップと、
前記ベース・アドレス・ポインタ・フィールドを読み取り、最終結果が含まれていない場合、前記ベース・アドレス・ポインタ・フィールドが前記最終結果を含むまで、以下のステップを繰り返すステップと、
前記入力単語連鎖の次の単語を前記現在の入力として定義するステップと、
前記次の単語が前記読み取られたベース・アドレス・ポインタによって示された前記遷移規則の前記テスト・マスクをマップすることをチェックするステップと、
前記ベース・アドレス・ポインタ・フィールドを読み取るステップと
を含む方法。
【請求項６】
様々な単語の連鎖にある入力パケットを受信すると、すべての単語が処理されるまで、請求項４の方法のステップ、および請求項５の方法のステップを二者択一的に繰り返すステップを含むワイヤスピードのディープ・パケット処理を行う方法。
【請求項７】
様々な単語の連鎖にある入力パケットを受信すると、すべての単語が処理されるまで、前記ディープ・パケット処理に対応する順序で、請求項４の方法のステップの組と請求項５の方法のステップの組とを組み合わせるステップを含むワイヤスピードのディープ・パケット処理を行う方法。
【請求項８】
コンピュータに請求項１ないし７のいずれかの方法に記載の各ステップを実行させるためのコンピュータ・プログラム。
【請求項９】
結果として得られるアドレスを指すように入力単語連鎖（input word chain）内の単語パターンを識別することによってプログラマブル状態マシンのデータ構造を作成して、前記入力単語連鎖を構文解析する装置であって、
前記入力単語連鎖の前記単語パターンを識別するために、前記プログラマブル状態マシンの状態に対応する状態テーブルを作成する手段であって、各状態テーブル・エントリがｓビットの現在の状態、入力されたｎビットの単語、およびｓビットの次状態を含む、前記作成する手段と、
前記ｓビットの現在の状態、前記入力されたｎビットの単語を含むテスト値、前記ｓビットの現在の状態と前記入力されたｎビットの単語との組み合わせのテスト・マスク、および前記ｓビットの次状態として表される３値一致状態をそれぞれ含む状態遷移規則エントリの数を低減するように前記エントリを変換することによって前記状態テーブル内のエントリ数を低減する手段と、
前記手段によって取得された前記低減された状態テーブル・エントリを、最も頻繁に使用される遷移規則の優先順位が最も高い状態の優先順位で配列するステップと
を含む装置。
【請求項１０】
結果として得られるアドレスを指すように入力単語連鎖（input word chain）内の単語パターンを識別することによってプログラマブル状態マシンのデータ構造を作成して、前記入力単語連鎖を構文解析するチップ埋め込み装置であって、
前記入力単語連鎖の前記単語パターンを識別するために、前記プログラマブル状態マシンの状態に対応する状態テーブルを作成する手段であって、各状態テーブル・エントリがｓビットの現在の状態、入力されたｎビットの単語、およびｓビットの次状態を含む、前記作成する手段と、
前記ｓビットの現在の状態、前記入力されたｎビットの単語を含むテスト値、前記ｓビットの現在の状態と前記入力されたｎビットの単語との組み合わせのテスト・マスク、および前記ｓビットの次状態として表される３値一致状態をそれぞれ含む状態遷移規則エントリの数を低減するように前記エントリを変換することによって前記状態テーブル内のエントリ数を低減する手段と、
前記手段によって取得された前記低減された状態テーブル・エントリを、最も頻繁に使用される遷移規則の優先順位が最も高い状態の優先順位で配列するステップと
を含むチップ埋め込み装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に通信パケット処理に関し、より詳細にはパケット・ペイロードを含むパケット内の情報の柔軟な構文解析および検索の方法に関する。
【背景技術】
【０００２】
パケット分類は、着信パケットから情報を抽出し（構文解析と呼ばれる）、これを使用して規則に従ってデータ・ベースを検索する、ルーターおよびスイッチなどのネットワーキング機器で実施される機能である。一致する規則が見つかると、そのパケットの処理は、その規則に関連付けられているデータに基づいて行われる。構文解析された情報、規則、および規則が検索される方法は、アプリケーションに依存する。
【０００３】
例えば、ＩＰ転送アプリケーションでは、パケット分類は、ＩＰヘッダーからＩＰ宛先アドレスを構文解析し、次いでそれを使用して、最長接頭部一致検索（longest-matching prefix search）に従ってルーティング・テーブルを検索するステップから成る。この検索から得られたルーティング・テーブル・エントリは、パケットが転送される次ホップのアドレスを提供する。別の例はファイアウォール・アプリケーションであり、このアプリケーションでは、いくつかのフィールド（例えばＩＰソースおよび宛先アドレス、ＴＣＰポート番号、ＰＲＯＴバイトなど）がパケット・ヘッダーから構文解析され、次いで１組のファイアウォール規則からの優先度が最も高い一致規則の検索に使用される。このファイアウォール規則に関連付けられているデータは、次いでパケットがファイアウォールへのアクセスを許可されるか拒否されるかを示す。
【０００４】
記載した２つの例など、従来のアプリケーションには、情報が、固定された相対的に小さいサイズ（一般に最高３２ビット）を有するパケット・ヘッダー内の固定された位置（最高レイヤ４）にあるよく知られているフィールドから構文解析されるという共通点がある。さらに分類は、次の２つの別個の段階で実行することができる。まず、情報がパケット・ヘッダーから構文解析される。次に、構文解析された情報は、データ・ベースの検索に使用される。
【０００５】
Ｗｅｂサーバー・ロード・バランシング、侵入検知、およびウィルス・スキャンは、上記の「従来の」アプリケーションが必要とするものより進んだパケット分類機能を必要とする重要な新興アプリケーションの例である。こうしたより進んだ機能は、具体的には次の側面との関連がある。
１）パケット・ヘッダーからの情報に加えて、パケット・ペイロードからの情報も検査する必要がある。
２）ペイロード内の検査する必要がある情報の位置および量は、必ずしもあらかじめわかっているとは限らず、いくつかのアプリケーションでは、分類操作中にしか決定できない。一部のアプリケーションは、ペイロード内で情報を探し出すためにパターンマッチおよび正規表現ベースの検索の使用を必要とする。
３）パケット分類に関わる情報の量は、最高数百バイトから成る可能性がある。
【０００６】
Ｗｅｂサーバーロード・バランサー・アプリケーションでは、ペイロード内の検査が必要な情報の例は、ＵＲＬ、クッキー、およびＳＳＬ識別子である。別の例は、ウィルス・スキャン・アプリケーションによって検査されるウィルスに関連する１組の既知の文字列である。
【０００７】
上記から、次の２つの点で、パケット分類は現在、より複雑になっていることを理解できよう。
１）構文解析する必要のある情報の位置および量があらかじめわかっていないアプリケーション、および大量の情報を構文解析する必要があるアプリケーションでは、構文解析操作はより難しくなっている。
２）いくつかのアプリケーションでは、構文解析および検索の２つの別個の段階を使用することができるのではなく、代わりに、構文解析および検索を交互のステップで繰り返す、または２つのステップを結合する（例えばパターンマッチなど）必要がある。
【０００８】
上記で概説した機能上の要件に加えて、１Ｇｂ／秒から１０Ｇｂ／秒の間の今日の一般的なリンク速度の着信パケットに対して、その場でパケット分類を行う（これをワイヤスピード・パケット分類と呼ぶ）必要がある。第２の要件は、パケット分類に使用されるデータ構造は、コストを最低限に抑えるために、データ構造の格納に必要なメモリが最低量で済むように構成されるべきであることである。第３の要件は、いくつかの新しいアプリケーション（Ｗｅｂサーバー・ロード・バランシングなど）の動的な性質によって必要とされるような規則の組の迅速な更新のサポートである。
【０００９】
上記の進んだパケット分類に適した柔軟な構文解析機能を実現するための標準の解決策は、プログラマブル状態マシン（programmable state machine）である。次に、プログラマブル状態マシンの従来技術の実装の概念および欠点について、図１および図２を使用して説明する。
【００１０】
図１は、４ビット文字の入力ストリームから２つのパターン「１２１ｈ」（ｈは１６進数を意味する）および「ＡＢｈ」を構文解析する状態図を示している。円で表された考え得る６つの状態（Ｓ０、Ｓ１、Ｓ２、Ｓ３、Ｓ４、Ｓ５）があり、矢印は状態遷移を表す。ノードＳ３およびＳ５は最終状態である。
【００１１】
図２は、状態遷移当たり１つのメモリ・アクセスを必要とする、図１の状態図でのプログラマブル状態マシンの従来技術の実装を示している。この例では、状態に、次の３ビット状態ベクトルが割り当てられる。
Ｓ０−０００ｂ  Ｓ２−０１０ｂ  Ｓ４−１００ｂ
Ｓ１−００１ｂ  Ｓ３−０１１ｂ  Ｓ５−１０１ｂ
【００１２】
図２で、４ビットの入力値に連結されている現在の状態（３ビット）は、現在の状態と入力値との考え得る組み合わせごとに次状態を含み、結果として合計２（３＋４）＝２７＝１２８のテーブル・エントリが得られるテーブルへのオフセット（アドレス）として使用される。この手法の欠点は、（１）ストレージの使用効率が悪い（例えば図２には１２８のテーブル・エントリがあり、その多くは同じ次状態を含んでいる）、および（２）所与の状態図について、テーブルを「プログラミング」する間に書き込まれる必要があるテーブル・エントリの数が多く、結果として構築（更新）時間が長くなることである。
【００１３】
ソリダム（Solidum）の米国特許第ＵＳ０６１６７０４７号では、パケット分類のためのプログラマブル状態マシンが開示されている。ソリダムの特許手法は、状態遷移当たり最高で１つのメモリ・アクセスを必要とするが、図２に示した実装の概念より少ないメモリで済む。ソリダムの手法の欠点は、極めて複雑なハードウェア、つまり少なくとも１つのプロセッサ、１つのプログラム・メモリ、および個別のスタック・メモリを必要とすることである。これによってチップ面積のコスト、および消費電力が増す。
【００１４】
上記の進んだパケット分類に適した柔軟な検索機能を実現するための従来の解決策は、ツリー構造である。一例は、Ｄ．Ｒ．モリソン（D. R. Morrison）の原著論文「パトリシア−英数字で符号化された情報を取り出すための実用的なアルゴリズム（Patricia -Practical Algorithm to Retrieve Information Coded in Alphanumeric）、ジャーナル・オブＡＣＭ（Journalof the ACM）、第15巻、1968年に記載のパトリシア・ツリーである。
【００１５】
従来技術の欠点は、効率的な構文解析および効率的な検索の両方をサポートできる解決策が存在しないことである。一般に状態空間が大きすぎ、次状態を決定するために、メモリ要件が増大する、または論理が複雑になる、およびその両方をもたらすため、プログラマブル状態マシンは、検索を効率的に実施することができない。一方、特にプログラマブル状態マシンは、一般のツリー検索で行われるブランチ機能より複雑な一般の状態遷移をより効率よく扱うことができるため、ツリー構造は、プログラマブル状態マシンと同じぐらい効率よく構文解析を実施することができない。したがって、ツリー構造を使用した構文解析の実施は、多くのノードを必要とし、したがってメモリ要件の増大をもたらすことになる。
【特許文献１】米国特許第ＵＳ０６１６７０４７号
【非特許文献１】Ｄ．Ｒ．モリソン（D. R. Morrison）の原著論文「パトリシア−英数字で符号化された情報を取り出すための実用的なアルゴリズム（Patricia-PracticalAlgorithm to Retrieve Information Coded in Alphanumeric）、ジャーナル・オブＡＣＭ（Journal ofthe ACM）、第15巻、1968年
【非特許文献２】ジャン・バン・ルンテレン（Jan Van Lunteren）による「大きい埋め込みメモリにおける非常に大きいルーティング・テーブルの検索（SearchingVery Large Routing Tables in Wide Embedded Memory）」という名称の会議論文、ＩＥＥＥグローブコム（IEEEGlobecom）第3巻の会議録で発行、1615〜1619頁、2001年11月
【発明の開示】
【発明が解決しようとする課題】
【００１６】
したがって、従来技術の欠点は、構文解析および検索を実施するために異なるハードウェアを使用する必要があることである。第２の欠点は、これによって、上述した構文解析および検索の交互の使用、または構文解析および検索の組み合わせをサポートする、より進んだパケットの分類機能の実現がより複雑となることである。
【課題を解決するための手段】
【００１７】
したがって本発明の目的は、構文解析操作および検索操作を実行しながら高速を維持できるディープ・パケット処理方法および装置を提供することである。
【００１８】
本発明の別の目的は、ストレージ要件、およびハードウェア実装の複雑さを低減することである。
【００１９】
これらの目的は、請求項１から３に従ってプログラマブル状態マシンのデータ構造を作成する方法の使用によって達成される。データ構造は、構文解析を行うプログラマブル状態マシンの状態遷移規則を含む。ストレージ要件は、ＢａＲＴとして知られているアルゴリズムの使用によって、また個別の状態遷移規則テーブルを使用して実装される複数の状態空間に状態を分散させることによって低減される。請求項４の構文解析方法は、データ構造を利用し、ワイヤスピードで実行することができる。
【００２０】
請求項５の検索方法も、同じデータ構造を使用し、ワイヤスピードで実行することができる。構文解析および検索の方法は、請求項６および７に従って、二者択一的に、または組み合わせて、依然としてワイヤスピードで実行することができる。請求項８に従って、同じハードウェアを使用して構文解析および検索を行うことができる。メモリ要件が低減されるため、本発明を具現化するハードウェアの解決策の例は、請求項９に従ってオンチップ・メモリで実施することができる。コンピュータ・プログラムは、請求項１０に従って本発明の例を有利に実施することができる。
【００２１】
すでに開示されている圧縮技術をルックアップ方式の実施に使用すると、本発明の好ましい実施形態は、構文解析のための効率的なプログラマブル状態マシンと効率的なツリーベースの検索機構の組み合わせを可能にする強力なデータ構造を提供する。
【００２２】
本発明の特に好ましい実施形態では、同じハードウェアを使用して構文解析および検索を行うことができる。
【００２３】
次に本発明の好ましい実施形態を、ほんの一例として、添付の解説を参照して説明する。
【発明を実施するための最良の形態】
【００２４】
プログラマブル状態マシン
本発明の好ましい実施形態では、ディープ・パケット処理を行う方法が提供される。方法は、従来技術のプログラマブル状態マシンを改良するデータ構造の作成を含む。データ構造では、状態遷移は、現在の状態および入力値の組み合わせ、および次状態の３値一致状態（ternary match condition）をそれぞれ含む、いわゆる状態遷移規則のリストとして示される。３値一致状態では、一致するパターンは、３つの可能な状態０、１、またはＸを有するビットを含む。Ｘは、「値が決められていない」状態のワイルドカード記号である。
【００２５】
状態遷移規則が所与の現在の状態および入力に一致する３値一致状態を含んでいる場合、この状態遷移規則は、一致していると言われる。複数の状態遷移規則が同じ現在の状態および入力にすべて一致する可能性がある場合、これらの状態遷移規則には異なる優先順位が割り当てられる。
【００２６】
次に、所与の現在の状態および入力値について、現在の状態および入力値に一致する、優先順位の最も高い状態遷移規則によって次状態が決定される。
【００２７】
図１の状態マシンの状態遷移規則のリストの例（優先順位の高い順）は、
【００２８】
【表１】
2005538624.tif 000003
となる（「＊」および「ｘ」は「値が決められていない」ことを意味するワイルドカード記号であり、「＊」は、状態全体または入力値全体のワイルドカードとして使用され、「ｘ」は単一ビット位置のワイルドカードとして使用される）。
【００２９】
こうした規則を生成する考え得る１つのアルゴリズムについては、図１２を参照して本書で後述することに留意されたい。
【００３０】
次に、現在の状態Ｓおよび入力Ｉに一致する優先順位の最も高い状態遷移規則を検索することによって次状態が決定される。例えば、現在の状態がＳ２であり、入力が１に等しい場合、状態遷移規則１が一致し、次状態がＳ３であることを示す。１に等しい入力との組み合わせの他の任意の現在の状態では、状態遷移規則２が一致し、状態Ｓ１への遷移がもたらされる。図１のすべての状態遷移は、たった６つの状態遷移規則で表される。
【００３１】
状態遷移規則が少数しかない場合、好ましい実施形態では、これらは、いわゆる状態遷移規則エントリ、略して遷移規則エントリとして、レジスタまたは１つのメモリ位置に格納される。これを図３に、上記の６つの状態遷移規則について示している。各遷移規則エントリの３値一致状態は、（バイナリ）テスト値および（バイナリ）テスト・マスクの組み合わせとして格納される。現在の状態および入力値のビットがテスト・マスク内のセット・ビットに対応するビット位置にあるビットに等しい場合、３値一致状態は一致する。残りのビット位置は関係ない。例えば、状態遷移規則２の３値一致状態「ｘｘｘ０００１」は、テスト値００００００１ｂおよびテスト・マスク０００１１１１ｂとして、対応する遷移規則エントリに格納される。
【００３２】
本発明の好ましい実施形態では、対応する遷移規則エントリ内にテスト値およびテスト・マスクとして格納されている３値一致状態に対する現在の状態および入力文字の並列比較を行うことによって次状態が決定される。複数の一致がある場合、優先順位の最も高い一致する遷移規則エントリが選択される（図３では、エントリは優先順位の高い順に左から右に格納されている）。この操作は、２つの最終状態（Ｓ３またはＳ５）のうちの１つに到達するまで、新しい４ビット入力文字ごとに行われる。
【００３３】
ＢａＲＴ圧縮
状態が多すぎる状態マシンでは、実施上の問題（メモリ幅、タイミングなど）によって、すべての遷移規則エントリを１つのメモリ位置に格納すること、またはすべてのエントリを並行してテストすることが不可能になる場合がある。この場合、好ましい実施形態は、ＢａＲＴ圧縮方式を使用して、複数のメモリ位置に遷移規則エントリを分散させる。ＢａＲＴ比較方式は、ジャン・バン・ルンテレン（Jan Van Lunteren）による「大きい埋め込みメモリにおける非常に大きいルーティング・テーブルの検索（SearchingVery Large Routing Tables in Wide Embedded Memory）」という名称の会議論文、ＩＥＥＥグローブコム（IEEEGlobecom）第3巻の会議録で発行、1615〜1619頁、2001年11月に開示されている。
【００３４】
ＢａＲＴ圧縮方式は、完全一致検索、接頭部一致検索、および３値一致検索の特殊なハッシュ関数に基づいている。ハッシュ・インデックス（圧縮インデックスと呼ぶ）は、入力ビットの選択されたサブセット（この場合、現在の状態および入力文字）を含む。これらのビットは、各圧縮インデックス値の衝突の数が値Ｎによって制限されるように選択される。言い換えれば、圧縮インデックスの所与の値について、最高でＮ個のエントリが入力に一致し得る。次いでこれらのエントリは、ハッシュ・テーブル（好ましい実施形態では圧縮済み状態遷移規則テーブルと呼ばれる）内のその圧縮インデックス値に対応する位置に格納される。次に、この概念について、図３の例で衝突範囲Ｎ＝４の場合にそれを適用することによって説明する。
【００３５】
図４で、圧縮インデックスは、状態レジスタ４３０の第２のビット、および４ビットの入力４４０の最上位ビットから成る。圧縮インデックスを形成するビットを決定する方法については後述する。圧縮インデックスは２ビットから成るため、圧縮済み状態遷移規則テーブルは、最高でＮ＝４の遷移規則エントリをそれぞれ含む４（２２）ブロックを含む。ブロックは、図４に行として示されている。各ブロックは、１つのメモリ位置に格納され、１回のメモリ・アクセスで読み取ることができる。テーブルのベース・アドレスは、ポインタ４１０に格納される。圧縮インデックスは、圧縮インデックスとして抽出されたビットに対応するビット位置にあるセット・ビットを有するいわゆるインデックス・マスク（index mask）４２０によって指定することができる。
【００３６】
図４では、図をより簡潔にし、わかりやすくするために、遷移規則エントリのテスト値フィールドおよびテスト・マスク・フィールドが１つの３値テスト・ベクトル・フィールド（ternary test vector field）に結合されている。「０」、「１」、「ｘ」から成る３値ベクトルは、状態遷移規則テーブル４００に格納され、例えば、３値「ｘｘｘ  ０００１」は、テスト値／テスト・マスクの組み合わせ「０００  ０００１／０００  １１１１」に対応する。
【００３７】
現在、圧縮インデックスの値ごとに、最高でＮ＝４の遷移規則エントリが現在の状態および入力文字に一致し得る。例えば、現在の状態の第２のビット、および入力文字の最上位ビットがいずれもゼロに等しい場合、圧縮インデックス値００ｂに対応するブロック内に含まれる３つの遷移規則エントリのみが現在の状態および入力文字に一致し得る。すべての状態遷移規則エントリ、すなわち図３に示したものと同じものは、このように、様々な圧縮インデックス値に分散される（いくつかの遷移規則エントリは、複数の圧縮インデックス値と一致する可能性があり、したがって複数のブロックに格納されることに留意されたい）。圧縮インデックスの一部である３値ベクトルのビットには、説明上、図４の遷移規則エントリ内で下線を付けている。
【００３８】
次に、所与の現在の状態および入力文字について、次状態を次の方法で決定することができる。まず、圧縮インデックス・ビットが、インデックス・マスク４２０に基づいて、現在の状態および入力文字から抽出される。次に、この圧縮インデックスを使用して、ポインタ４１０によって参照される圧縮済み状態遷移規則テーブル内の１つのブロックを選択する。次いでブロック全体が１回のメモリ・アクセスを使用して読み取られる。次いで上述したように、１つのブロック内のすべての遷移規則エントリが並行して比較される。また、この場合、エントリは、優先順位の高い順にブロック内に配列され、すなわち次状態は、一致する最初の遷移規則エントリから取得される（左から右に）。次いで状態レジスタに、選択された一致するエントリから次状態をロードする。
【００３９】
圧縮インデックスを抽出し、優先順位の最も高い一致エントリを見つけ、状態レジスタを更新するプロセスは、２つの最終状態（Ｓ３またはＳ５）のうちの１つに到達するまで、新しい入力文字ごとに行われる。
【００４０】
ＢａＲＴ圧縮の場合のインデックス・マスク計算
本発明の好ましい実施形態では、圧縮インデックスを含むビットは、次の方法で選択される。これは、インデックス・マスク計算とも呼ばれる。というのは、インデックス・マスクは、圧縮インデックスの一部であるビットを一意に定義するからである。
【００４１】
現在の状態および入力文字がともに合計ｍビットから成る場合、合計２ｍの異なる可能なインデックスが存在し、現在の状態および入力文字から０、１、２、・・・、ｍビットを抽出する考え得るすべての方法がそれぞれカバーされる。第１のステップで、こうしたすべてのインデックス・マスクを決定し、セット・ビット数の少ない順に配列する。例えば、図４では、現在の状態および入力文字は、合計ｍ＝７ビットを含む。セット・ビット数の少ない順に配列される２７＝１２８の可能なインデックス・マスクは、次の通りである。
0000000,
1000000, 0100000, 0010000, ..., 0000001,
1100000, 1010000, 1001000, ..., 0000011,
1110000, 1101000, 1100100, ..., 0000111,
...
1111110, 1111101, 1111011, ..., 0111111,
1111111
【００４２】
次に、これらのインデックス・マスクが所与の順序で処理される。所与の１組の遷移規則エントリについて、インデックス・マスクごとに、そのインデックス・マスクに対応するすべての可能な圧縮インデックス値について起こる衝突の最大数が決定される。衝突の最大数が所与の衝突範囲Ｎを超えない第１のインデックス・マスクは、インデックス・マスク計算の結果となるインデックス・マスクである。
【００４３】
インデックス・マスクがｋ個のセット・ビットを含む場合、対応する圧縮インデックスは、合計ｋビットから成り、対応する圧縮済み状態遷移規則テーブルは、（最高で）Ｎ個のエントリの２ｋ個のブロックを含む。セット・ビット数の少ない順に配列されたインデックス・マスクをテストすることによって、見つかった第１のインデックス・マスクは、最小数のセット・ビットを有し、その結果最も少ない圧縮済み状態遷移規則テーブルが（すなわち最も高い圧縮で）得られる。
【００４４】
上記のインデックス・マスク計算は、考え得るすべてのインデックス・マスクをテストする総当たり手法である。インデックス・マスクの選択されたサブセットのみをテストすることによってインデックス・マスク計算をより速く簡単にすることができる。このサブセットは、衝突範囲Ｎとの組み合わせで遷移規則エントリの数に基づいて選択することができる。例えば、衝突範囲Ｎ＝４、および３２個の遷移規則エントリの場合、圧縮済み状態遷移規則テーブルは、すべての遷移規則エントリを格納できるようにするには、Ｎ＝４エントリの少なくとも８つのブロック（８×４＝３２）を含む必要がある。８ブロックにインデックスを付けるために、圧縮インデックスは、少なくとも３ビット（２３＝８）から成っていなければならない。したがって、少なくとも３つのセット・ビットを含むインデックス・マスクのみをテストするだけでよい。
【００４５】
当業者は、ハードウェア実装で使用可能な並列処理を使用して、遷移規則エントリの数に比例する最適なインデックス・マスクを一度に決定することができるインデックス・マスク計算を実現することができる。
【００４６】
改良されたプログラマブル状態マシン
本発明の第２の実施形態では、ディープ・パケット処理を改良することができる。図４に示すような各遷移規則エントリは、インデックス・マスクおよびポインタ・フィールドによって拡張される。こうしたエントリを図５に示している。このテーブル・エントリを使用して、プログラマブル状態マシンを実施して構文解析を行い、ツリー状構造を実施して検索を行うことができる。
【００４７】
上記の第１の好ましい実施形態では、ｓ個の状態を有するプログラマブル状態マシンを実施するために、少なくともｌｏｇ（ｓ）個のビットを含む状態レジスタがある。拡張された遷移規則エントリによって、状態の数に依存しない固定された数のビットを有するより小さい状態レジスタを使用してプログラマブル状態マシンをサポートすることができる。これによって、多数の状態を含む状態マシンをより有効にサポートすることができる。次に、これについて、図６に示したデータ構造を取得するために、図１の状態マシンの例を使用して説明する。図７に示したフロー図によって様々なステップが説明されている。
【００４８】
第２の好ましい実施形態での第１のステップ７００のように、すべての状態は、より小さい状態空間に分散され、それには各状態空間内で一意の状態ベクトルが割り当てられる。この例では、図１の６つの状態は、次の方法で、次の状態ベクトル割当付きで２つの状態空間に分散される。
【００４９】
【表２】
2005538624.tif 000004
この分散は、任意の方法で行うことができることに留意されたい。しかし、分散の一般的な目的は、状態レジスタのサイズから生じる。例えば、実施上の問題または他の理由によってｋビットから成る状態レジスタがもたらされた場合、状態は、各状態空間が最高で２ｋを含むように複数の状態空間に分散されるべきである。この状況で、最高でｋビットの一意の状態ベクトルを、状態レジスタに合う状態空間内の各状態に割り当てることができる。
【００５０】
２つの状態空間への状態の上記の分散を適用した後、７１０で、元の状態遷移規則を次のように書くことができる。
【００５１】
【表３】
2005538624.tif 000005
次のステップ７２０で、第１の好ましい実施形態と同じ方法で圧縮済み状態遷移規則テーブルを使用して各状態空間が実装される。第１の好ましい実施形態との差は、ここでは、次状態がその一部である状態空間に「関連付けられている」インデックス・マスクおよびポインタが、次状態とともに、拡張された遷移規則エントリに格納されていることである。
【００５２】
図６は、メモリ幅によって１つの位置に４つの遷移規則エントリを格納し、それらを並行して比較することができる実装の場合の結果として得られる構造を示している。状態空間１に対応する圧縮済み状態遷移規則テーブル６１０は、４つのエントリの１つのブロックから成る。状態空間２に対応する圧縮済み状態遷移規則テーブル６００は、２つのエントリ・ブロックから成り、これらは、現在の状態レジスタ６３０および４ビット入力文字６４０から抽出された１ビットの圧縮インデックス６２０を使用して選択される。２つの圧縮済みテーブルに対応する２つのベース・ポインタ６５０および６６０は、それぞれＳＰ１およびＳＰ２として示されている。
【００５３】
図８および図９は、７２０の状態空間ごとに圧縮済み状態遷移規則テーブルを作成することを説明するフロー図を示している。次にこれについて、次のテスト・ベクトルを備える５つのエントリを含む第２の状態空間に関して説明する。
エントリ１  00 0001
エントリ２  xx 0001
エントリ３  10 1011
エントリ４  xx 1010
エントリ５  xx xxxx
【００５４】
９００で、エントリ・ブロック当たりのエントリの最大数はＮ＝４８００に等しい。遷移規則の数は５に等しく、これは、エントリ・ブロック当たりのエントリの最大数より大きい（テスト８１０に対してＹｅｓと回答）ため、圧縮済みテーブルは、複数のエントリ・ブロックを含み、圧縮インデックスによって複数のエントリ・ブロックにインデックスを付ける必要がある。このために、８３０で、次の方法でインデックス・マスクを計算する必要がある。まず、９１０で、考え得るすべてのインデックス・マスクが決定され、セット・ビット数の少ない順に配列される。セット・ビットがより少ないことは、圧縮インデックスがより少なく、エントリ・ブロックがより少なく、したがってより良い圧縮が行われることに相当する。６ビット・ベクトル（２ビットの状態＋４ビットの入力）の合計６３（２６−１）の可能な非ゼロの値が存在し、これらは、セット・ビット数の少ない順に配列される。
100000b
010000b
001000b
000100b
000010b
000001b
110000b
101000b
100100b
...
111111b
【００５５】
９２０で、第１のインデックス・マスクは１０００００ｂである。９３０で、このインデックス・マスクに、２つの可能な圧縮インデックス値、つまり０ｂおよび１ｂが対応する。このインデックス・マスクでは、９４０で、エントリが次の方法で２つの圧縮インデックス値にマップされる
0b: エントリ 1, 2, 4, 5
1b: エントリ 2, 3, 4, 5
（このマッピングは、テスト・ベクトルの最左ビットを取得することによって得られ、０ｂの場合、エントリはインデックス０ｂにマップされ、１ｂの場合、エントリはインデックス１ｂにマップされ、ｘｂの場合、エントリはインデックス０ｂおよびインデックス１ｂの両方にマップされる）。
【００５６】
９５０で、１つの圧縮インデックス値にマップされるエントリの最大数はＭ＝４に等しい。Ｍ＜＝Ｎ（以下）であるため、このインデックス・マスクが選択される（テスト９６０に対してＹｅｓと回答）。Ｍ＞Ｎ（テスト９６０に対してＮｏと回答）の場合、次のインデックス・マスクが選択される（９７０）。
【００５７】
８４０で、インデックス・マスク１０００００ｂのセット・ビット数はｋ＝１に等しい。したがってテーブルは、それぞれＮ＝４エントリを含む２ｋ＝２のブロック・エントリ（両方の圧縮インデックス値に対応）から成る。したがって、テーブルは合計２×４＝８のエントリを含む。８５０で十分なメモリが割り当てられた後、８６０で、エントリを、優先順位が高い順に配列された２つのブロックのそれぞれの中に書き込むことができる（上述したように、圧縮インデックス値０ｂにはエントリ１、２、４、５、圧縮インデックス値１ｂにはエントリ２、３、４、５）。同じ手順を使用して、状態空間１の圧縮済みテーブルを構築する。この場合、遷移規則の数は、１つのエントリ・ボックス（Ｎ＝４）内のエントリ数未満であり、テスト８１０に対してＮｏと回答する。したがって、８２０で、インデックス・マスクは００００００ｂに等しく、８４０、８５０、８６０で、圧縮済みテーブルは、１つのエントリ・ブロックのみから成る。両方のテーブルが構築された後、８７０、７３０で、テーブルごとのインデックス・マスク／ポインタの組み合わせを、対応する状態空間内に次状態を含むエントリ内の対応するフィールドに書き込むことができる。
【００５８】
実用上の実装形態では、エントリ数は一般に、本明細書に提示した本発明の様々な実施形態の説明に使用されている状態図を用いたものよりかなり多い。
【００５９】
検索
図１０は、検索に使用できる上記の第２の好ましい実施形態によるデータ構造の例を示している。圧縮済みテーブル内の遷移規則エントリの状態レジスタ・フィールドおよび次状態フィールドは、この検索には使用されず、状態レジスタに対応するテスト・ベクトル内の最左２ビットは、ｘｘｂ（値が決められていない）に等しい。
【００６０】
データ構造は、図１０に示すように第１  １０００、第２  １０１０、および第３  １０２０の４ビット入力値から成る１２ビット・ベクトルで接頭部検索を実施する。接頭部および対応する検索結果は次の通りである。
【００６１】
【表４】
2005538624.tif 000006
【００６２】
この例のデータ構造は、入力値のうちの１つによってそれぞれ「インデックス付けされた」３つの圧縮済みテーブルから成る。第１の入力値によってインデックス付けされた圧縮済みテーブルを使用して、０００１ｂ（接頭部１）、０１０１ｂ（接頭部２）、および１０１０ｂ（接頭部３）である接頭部の最初の４ビットに基づいて、上記の接頭部が入力に一致するかどうかを決定する。こうした接頭部に対応するテスト・ベクトルは、
xx 0001b (接頭部1)
xx 0101b (接頭部2)
xx 1010b (接頭部3)
となる（上述したように、状態レジスタ（１０３０）に関連するビット位置はｘｘｂを含む）。
【００６３】
この例では、エントリ・ブロック当たりのエントリ数がＮ＝２に等しくなるように選択される。Ｎのこの値、および上記のテスト・ベクトルでは、ＢａＲＴアルゴリズムに従って計算された圧縮インデックスは、１ビット１０７０から成り、接頭部１および接頭部２に関連するエントリは、圧縮インデックス値０ｂにマップされ、接頭部３に関連するエントリは圧縮インデックス値１ｂにマップされる。
【００６４】
接頭部２および接頭部３は４に等しい長さを有する。したがって、これらの接頭部のそれぞれに対応するエントリに格納されているテスト・ベクトルが最初の４ビット入力値に一致する場合、これは、対応する接頭部が入力文字に一致することを意味する。この場合、検索結果を、一致するエントリのポインタ・フィールドから取り出すことができる。第１の入力値が「５」ｈに等しい場合、結果はＱとなる。第１の入力値が「Ａ」ｈに等しい場合、結果はＲとなる。
【００６５】
接頭部１は１２に等しい長さを有する。これは、この接頭部が一致するかどうかを決定するために、すべての３つの入力値１０００、１０１０、１０２０をテストする必要があることを意味する。これは、図１０のデータ構造で次の方法で実施される。第１の入力値１０００は、圧縮済みテーブル１０４０によってテストされる。第１の入力値が接頭部１に関連するエントリに格納されているテスト・ベクトルｘｘ  ０００１ｂに一致し、エントリ・ブロック内の最左エントリが圧縮インデックス値０ｂに対応する場合、このエントリのインデックス・マスク・フィールドおよびポインタ・フィールドが取り出され、第２の圧縮済みテーブル１０５０にアクセスするために使用され、第２の入力値１０１０のテストが行われる。このテーブル内の有効なエントリのみが、ｘｘｂ（状態レジスタ）で始まり、次いで第２のグループの４ビットの接頭部を含み、結果的にｘｘ  ００１０ｂとなるテスト・ベクトルを含む。このテスト・ベクトルが第２の入力値１０１０に一致する場合、このエントリのインデックス・マスク・フィールドおよびポインタ・フィールドが取り出され、第３の圧縮済みテーブル１０６０にアクセスするために使用され、第３の入力値１０２０のテストが行われる。このテーブル内の有効なエントリのみが、ｘｘｂ（状態レジスタ）で始まり、次いで第３のグループの４ビットの接頭部を含み、結果的にｘｘ  ００１１ｂとなるテスト・ベクトルを含む。このテスト・ベクトルが第３の入力値１０２０に一致する場合、これは、接頭部１が所与の組の３つの入力値に一致していることを意味する。この場合、検索結果を、一致するエントリのポインタ・フィールドから取り出すことができる。３つの４ビット入力文字が「１２３」ｈに等しい場合、結果はＰとなる。
【００６６】
構文解析および検索の操作
図１１のフロー図は、第２の好ましい実施形態による構文解析および検索の方法の例を示している。第１のステップ１１００は、状態レジスタ、現在のインデックス・マスク、および現在のベース・ポインタを、構文解析または検索の操作に関与する第１の圧縮済みテーブルに対応する値で初期化することである。次のステップ１１１０は、分析すべき第１の入力文字を検索することである。次のステップ１１２０は、現在のインデックス・マスクに基づいて、入力データおよび状態レジスタから圧縮インデックス値を抽出し、これを使用して、現在のベース・ポインタによって参照される圧縮済みテーブル内の１つのエントリ・ブロックを選択することである。次のステップ１１３０で、各エントリ内のテスト・ベクトルを状態レジスタおよび入力文字と比較することによって、一致するエントリが選択されたエントリ・ブロック内で検索される。見つかった第１の一致するエントリが選択される。一致が見つからない場合、つまりテスト１１４０への回答がＮｏの場合、操作が終了する。一致が見つかり、テスト１１４０への回答がＹｅｓの場合、読み取られたエントリが最終である、つまりテスト１１５０への回答がＹｅｓである第１の場合がある。構文解析では、これは、状態マシンの最終状態に到達したことを意味する。図１の例ではＳ３およびＳ５である。検索では、これは、結果が見つかったことを意味する（一例として、図１０の例で、「Ａ」ｈの入力値の場合、Ｒ）。最終エントリは、例えばフラグ・ビット、またはポインタの特殊な値を使用するなど、様々な方法で識別することができる。この場合、最終エントリが見つかった場合、操作が終了する。一致するエントリが最終エントリではない場合、つまりテスト１１５０への回答がＮｏである場合、１１６０で、現在の状態レジスタの新しい値、現在のインデックス・マスク、および現在のベース・ポインタが一致するエントリから抽出され、現在の値になり、１１７０で、新しい４ビット文字値が選択される。新しい値に基づいて、１１２０で開始するループに再度入る。このループは、一致するエントリが見つからなくなる、つまりテスト１１４０に対する回答がＮｏ、または最終エントリが一致することがわかる、つまりテスト１１５０に対する回答がＹｅｓとなるまで実行される。
【００６７】
優先順位付けされた状態遷移規則を導出するアルゴリズム
図１２は、現在の状態および入力値についての３値一致状態をそれぞれ含む状態遷移規則を含む優先順位付けされたリストを導出する方法の一例を示すフロー図を示している。この方法を使用して、本発明の実施形態のプログラマブル状態マシンをサポートするデータ構造を構築することができる。このアルゴリズムは、図１に示す状態図の例を使用して説明する。この状態図の状態遷移は次の通りである。
【００６８】
【表５】
2005538624.tif 000007
１２００で、処理されていない入力値ｉが選択される。次に、１２１０で、この入力値ｉについて、最も頻繁に起こる次状態ｓが決定され、１２２０で、その次状態ｓへの入力値ｉを含むすべての遷移が優先順位１の１つの遷移規則「＊ｉ−＞ｓ」に置き換えられる。１２３０で、同じ入力ｉを含むが、ｓと異なる次状態を含むすべての遷移に、優先順位２が割り当てられる。すべての入力値が処理されるまで、つまりテスト１２４０に対する回答がＹｅｓになるまで、テスト１２４０に対する回答がＮｏとしてこれらのステップが繰り返される。ループの実行の結果は次の通りである。
【００６９】
【表６】
2005538624.tif 000008
【００７０】
次のステップ１２５０は、優先順位２の任意の遷移規則では起こらない、優先順位１の遷移規則内で最も頻繁に起こる次状態ｓを決定することである。こうした状態が存在しない場合、遷移規則リストが完了し、つまりテスト１２６０に対する回答がＮｏである場合、方法が終了する。この例では、こうした状態が存在し、すなわちＳ０であり、テスト１２６０に対する回答がＹｅｓとなる。次状態Ｓ０を含む優先順位１のすべての遷移規則は、１２７０で、優先順位０のデフォルトの遷移規則「＊  ＊−＞Ｓ０」によって置き換えられる。この結果は次の通りである。
【００７１】
【表７】
2005538624.tif 000009
【図面の簡単な説明】
【００７２】
【図１】４ビット文字の入力ストリームからのパターンの構文解析を示す状態図である。
【図２】図１の状態図での従来技術のプログラマブル状態マシンの実施を示す図である。
【図３】図１の状態図を実施し、１つのレジスタまたはメモリ位置に格納される、第１の好ましい実施形態による６つの遷移規則エントリを示す図である。
【図４】図１の状態図を実施し、最高Ｎ＝４の遷移規則エントリが各メモリ位置に格納されるように構成されている、第１の好ましい実施形態によるＢａＲＴ圧縮済み状態遷移規則テーブルを示す図である。
【図５】第２の好ましい実施形態による遷移規則エントリ内のフィールドを示す図である。
【図６】図１の状態図を実施し、最高Ｎ＝４の遷移規則エントリが各メモリ位置に格納されるように構成されている、第２の好ましい実施形態による２つのＢａＲＴ圧縮済み状態遷移規則テーブルを示す図である。
【図７】第２の好ましい実施形態によるデータ構造の作成を示すフロー図である。
【図８】図７に示したデータ構造の作成の１ステップである圧縮済み状態遷移規則テーブルの作成を示すフロー図である。
【図９】図８に示した圧縮済み状態遷移規則テーブルの作成の１ステップである、最小数のエントリ・ブロックに遷移規則エントリを分散させるインデックス・マスクの計算を示すフロー図である。
【図１０】３つの入力文字に対して接頭部一致検索を実施し、最高Ｎ＝２のエントリが各メモリ位置に格納されるように構成される、第２の好ましい実施形態による３つのＢａＲＴ圧縮済みテーブルから成るデータ構造を示す図である。
【図１１】第２の好ましい実施形態による検索および構文解析のプロセスを示すフロー図である。
【図１２】所与の状態図について、現在の状態および入力値についての３値一致状態をそれぞれ含む、第１および第２の好ましい実施形態による状態遷移規則の優先順位付きリストの導出を示すフロー図である。
【図１】
2005538624.tif 000010
【図２】
2005538624.tif 000011
【図３】
2005538624.tif 000012
【図４】
2005538624.tif 000013
【図５】
2005538624.tif 000014
【図６】
2005538624.tif 000015
【図７】
2005538624.tif 000016
【図８】
2005538624.tif 000017
【図９】
2005538624.tif 000018
【図１０】
2005538624.tif 000019
【図１１】
2005538624.tif 000020
【図１２】
2005538624.tif 000021
【国際調査報告】
2005538624.tif 000022
2005538624.tif 000023
2005538624.tif 000024
2005538624.tif 000025
2005538624.tif 000026