(57)【要約】ステートフルなパケット内容マッチング機構を使った、パケット境界をまたぐ内容検査を実行するための方法および装置。ストリング検索アルゴリズム機械を容易にするためにパターン・データ構造が用いられる。はいってくるパケットはフローに分類され、対応するフロー待ち行列に保存される。フロー・テーブル項目は、所与のフローのためのパターン・データ構造を指定するために使われる。内容検査の間、アルゴリズム機械は部分一致または全体一致を指定する状態情報を更新する。先行パケットの終わり付近で部分一致が検出されると、その状態を反映するようフロー・テーブル項目の状態情報が更新され、後続パケットの内容検査がその状態で開始されるようにされる。結果として、パケット境界をまたぐ内容検査がサポートされる。この技法はさらに、パケット処理コンテキスト・パイプライン段において用いられてもよい。
2008544728.tif 000002
【特許請求の範囲】
【請求項１】
先行パケット中に第一の部分を、後続パケット中に第二の部分をもつ検索ストリングを同定するよう複数パケットにまたがる内容検査を実行する段階を有する方法であって、
前記内容検査が複数の命令スレッドの実行を介して実行される方法。
【請求項２】
前記内容検査が、複数の異なるストリングの並行した検索を含む、請求項１記載の方法。
【請求項３】
前記内容検査が、DAWG（Directed  Acyclic  Word  Graph［有向非環形語グラフ］）マッチ・アルゴリズムに基づくストリング検索アルゴリズムのコンピュータ実装を介して実行される、請求項２記載の方法。
【請求項４】
前記内容検査が、ウ・マンバー（Wu-Manber）アルゴリズムに基づくストリング検索アルゴリズムのコンピュータ実装を介して実行される、請求項２記載の方法。
【請求項５】
第一のパケットを受信する段階と；
前記第一のパケットを分類して、あるフローに割り当てる段階と；
前記フローに割り当てられた諸パケットにおいて検索すべき、一つまたは複数のストリングを特定する段階と；
前記第一のパケットの内容検査を第一の命令スレッドを使って用いる段階と；
前記第一のパケットの末尾付近に位置する、前記一つまたは複数の検索ストリングの一つの部分一致を検出する段階と；
前記部分一致に対応するストリング検索状態情報を保存する段階と；
第二のパケットを受信する段階と；
前記第二のパケットを分類して、前記フローに割り当てる段階と；
前記ストリング検索状態情報を取り出す段階と；
前記ストリング検索状態情報を用いて、前記第二のパケットの先頭から始まる前記検索ストリングの第二の部分を検出する段階とをさらに有する、請求項１記載の方法。
【請求項６】
ストリング一致条件が発生したことを同定する段階と；
前記フローに割り当てられたその後受信されるパケットを処理するために前記条件についての関連付けられたアクションを実行する段階とをさらに有する、請求項５記載の方法。
【請求項７】
少なくとも一つの検索ストリングについてオフセット機構を用いる段階をさらに有しており、該オフセット機構とは、関連する検索ストリングについてのオフセットとして定義されている第一のパケットの第一の部分をスキップするものである、請求項１記載の方法。
【請求項８】
少なくとも一つの検索ストリングについて深さ機構を用いる段階をさらに有しており、該深さ機構とは、パケット内での検索の深さを追跡し、関連する検索ストリングについて定義された深さに達すると検索を止めるものである、請求項１記載の方法。
【請求項９】
大文字・小文字を区別しないストリングの複数パケット検索を実行することをさらに含む、請求項１記載の方法。
【請求項１０】
前記内容検査が、ネットワーク・デバイスにおいてパケットを処理するために実行される動作のコンテキスト・パイプラインでの動作を含んでおり、動作のコンテキスト・パイプラインは、複数の計算エンジン上での複数の命令スレッドの実行を介して行われる、請求項１記載の方法。
【請求項１１】
命令を担持する機械可読媒体であって、該命令はマルチスレッド・ネットワーク・プロセッサ上で実行された場合：
先行パケット中に第一の部分を、後続パケット中に第二の部分をもつ検索ストリングを同定するよう複数パケットにまたがる内容検査を実行する段階を実行するものであり、
ある所与のパケットについての前記内容検査が、命令スレッドの別個のインスタンスの実行によって行われる、機械可読媒体。
【請求項１２】
請求項１１記載の機械可読媒体であって、前記命令の実行がさらに：
受信された第一のパケットを分類して、あるフローに割り当てる段階と；
前記フローに割り当てられた諸パケットにおいて検索すべき、一つまたは複数のストリングを特定する段階と；
前記第一のパケットの内容検査を第一の命令スレッドを使って用いる段階と；
前記第一のパケットの末尾付近に位置する、前記一つまたは複数の検索ストリングの一つの部分一致を検出する段階と；
前記部分一致に対応するストリング検索状態情報を保存する段階と；
受信された第二のパケットを分類して、前記フローに割り当てる段階と；
前記ストリング検索状態情報を取り出す段階と；
前記ストリング検索状態情報を用いて、前記第二のパケットの先頭から始まる前記検索ストリングの第二の部分を検出する段階とを含む動作を行う、機械可読媒体。
【請求項１３】
請求項１１記載の機械可読媒体であって、前記命令の実行がさらに：
少なくとも一つの共有メモリ資源内に、個々のフローに関連付けられた複数の項目を含むフロー・テーブルを維持する段階であって、各フロー・テーブル項目が：
該個々のフローに関連付けられた複数パターン検索のために用いられるパターン・データ構造を同定する情報；および
前記複数パターン検索の状態を同定する状態情報を含むような段階と；
パケットを受信するのに応答しての、
前記パケットをあるフローに分類する段階と；
前記パケットを、前記フローに割り当てられているフロー待ち行列に入れる段階と；
前記フローに対応するフロー・テーブル項目を位置特定する段階と；
前記パケットを、前記ネットワーク・プロセッサ上の計算エンジンのローカル・メモリにコピーする段階と；
前記フロー・テーブル項目によって同定された前記パターン・データ構造を前記計算エンジンのローカル・メモリにコピーする段階と；
前記計算エンジン上で、前記パターン・データ構造を使って、前記パケットの複数パターン・ストリング検索を実行する段階とを含む動作を行う、機械可読媒体。
【請求項１４】
請求項１３記載の機械可読媒体であって、前記命令の実行がさらに：
前記パケットを新しいフローに分類する段階と；
前記新しいフローに対応する新しい項目を前記フロー・テーブル中に生成する段階とを含む動作を行う、機械可読媒体。
【請求項１５】
前記内容検査が、DAWG（Directed  Acyclic  Word  Graph［有向非環形語グラフ］）マッチ・アルゴリズムに基づくストリング検索アルゴリズムのコンピュータ実装を介して実行される、請求項１１記載の機械可読媒体。
【請求項１６】
前記内容検査が、ウ・マンバー（Wu-Manber）アルゴリズムに基づくストリング検索アルゴリズムのコンピュータ実装を介して実行される、請求項１１記載の機械可読媒体。
【請求項１７】
複数のマルチスレッド計算エンジンを有するネットワーク・プロセッサ・ユニット（NPU）と；
前記NPUに通信上結合されたダイナミック・ランダム・アクセス・メモリ（DRAM）と；
前記NPUに通信上結合されたスタティック・ランダム・アクセス・メモリ（SRAM）と；
前記NPUに通信上結合された記憶装置とを有しており、該記憶装置には前記NPU上で実行されるべき命令が記憶されており、該命令は：
受信されたパケットを関連するフローに分類する段階と；
所与のフローについて複数パケットにまたがる内容検査を実行して、前記複数パケットを介して転送されるデータ・ストリーム内で、逐次的な一組のパケット内に各部分を有する検索ストリングを同定する段階とを含む動作を実行するためのものである、ネットワーク・ライン・カード。
【請求項１８】
前記NPUがインテルIPXベースのNPUである、請求項１７記載のネットワーク・ライン・カード。
【請求項１９】
前記内容検査が、DAWG（Directed  Acyclic  Word  Graph［有向非環形語グラフ］）マッチ・アルゴリズムに基づくストリング検索アルゴリズムのコンピュータ実装を介して実行される、請求項１７記載のネットワーク・ライン・カード。
【請求項２０】
前記内容検査が、ウ・マンバー（Wu-Manber）アルゴリズムに基づくストリング検索アルゴリズムのコンピュータ実装を介して実行される、請求項１７記載のネットワーク・ライン・カード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は概括的にはネットワーク装置に、より特定的には、排他的にではないが、パケット境界をまたぐパケット内容検査を実行するための技法に関する。
【背景技術】
【０００２】
企業ネットワークは日々多様なセキュリティ問題に脅かされている。これらの脅威は内部のこともあれば、外部のこともある。内部的な脅威は、不満を抱く従業員による侵入の試みから、従業員によって放されるウイルスもしくはワーム、あるいは単なる従業員によるネットワークアクセス行動だが企業のセキュリティ・ポリシーにより受け容れられないと見なされるものまである。外部的な脅威は知的財産を盗む試みにおける企業ネットワークへの熱心な攻撃から、サービス拒否攻撃、不正侵入、ウイルスおよびワームなどまである。これらすべての場合において、パケット・ファイアウォールがネットワーク管理者の主要な防衛形態である。
【０００３】
パケット・ファイアウォールはネットワーク・トラフィックの線上に位置し、はいってくるパケットを捕らえ、各パケットをファイアウォール規則の組と突き合わせて検証し、該パケットを受け容れるか、拒否するか、任意的にログ記録するかする。パケット・フィルタリングに加えて、ネットワーク管理者は時として、パケット・フィルタを、トラフィック管理ポリシーを施行するためにも使う。そのようなポリシーは、有害な行動を制限またはコントロールするのに有用である。パケット・ファイアウォールがあらゆるネットワーク・トラフィックの線上に位置してあらゆるネットワーク・トラフィックを検査するという事実のため、ファイアウォールは、ネットワーク・トラフィックの需要についていくのに十分なネットワーク・スループットを提供できることが重要である。今日の企業ネットワークでは、ファイアウォール規則は典型的には2500  Cisco  ACL（access  control  list［アクセス・コントロール・リスト］）規則に制限される。これらの規則はきわめて特定的であり、特定の活動またはホストを許容または拒否するよう設計されている。ACL規則はパフォーマンスと扱いやすさの理由でこの数に制限される。規則の数はルータのパフォーマンスに直接影響し、よってこれらの規則は少ない数に維持される。さらに、規則が多いと、規則管理はより誤りの影響を受けやすくなり、検証や修正が難しくなる。大組織では、規則はさまざまなサイトにおいてファイアウォールをまたいで配布され、必要に応じて適応され、誤りの可能性が増す。こうした理由から、規則の数は扱えるレベルに維持される必要がある。
【０００４】
典型的な進んだファイアウォール実装のもとでは、２レベルのフィルタリングが採用される。第一レベルでは、フィルタリングは適用可能なACL規則に基づいて実行される。この例では、ACLデータベースに対応する最高優先度の規則がパケット・ヘッダ情報に基づいて同定される。たとえば、該規則は、よく知られた分類アルゴリズムを使って、発信元アドレス、宛先アドレス、発信元ポート、宛先ポートおよびプロトコルについての値に対応する５項組の入力に基づいて同定されてもよい。多くの攻撃（特にサービス拒否攻撃）は特定のポートを使う既知の発信元アドレスから発するので、そうした攻撃に対応するパケットは容易に同定でき、適切な規則（たとえばパケットを破棄する）が所望のファイアウォール・ポリシーを実施するために用いられうる。この第一レベルのフィルタリングは、現代のネットワーキング装置を使ったラインレート速度で実装できる。いくつかの実装のもとでは、専用コンポーネントまたは別個のコンピュータがこれらのフィルタリング動作を実行するために用いられる。
【０００５】
第二レベルのフィルタリングはパケット検査に関係する。この場合、実際のパケット・ペイロードの中で特定のストリングまたはストリングの集合が検索される。たとえば、ファイアウォール・アプリケーションは、パケット中に存在するウイルスまたはインターネット・ワームを示すある種のストリングを検索する必要がありうる。加えて、他の非セキュリティ・アプリケーションが、負荷均衡や課金といった目的のために、同様にパケット・ペイロードの中をのぞく必要があるかもしれない。「内容検査（content  inspection）」または「（深）パケット検査（(deep)  packet  inspection）」として知られるこれらの動作は、候補パターンがないかどうかパケット・ペイロードを検査し、そうしたパターンの有無に基づいてアクションをすることに関わる。
【０００６】
いくつかのファイアウォール実装のもとでは、パケット検査／内容検査の負担は、ラインレート速度をサポートしない別個のアプリケーションまたはサブシステムに任される。たとえば、こうした動作は別個のコンピュータ・ホストによって、あるいはネットワーク・デバイスに結合されるかネットワーク・デバイスによって提供される組み込みの汎用プロセッサによって実行されうる。こうした動作はラインレートで実行されない（よって対応する処理遅延に制約されない）ので、こうした処理はより大容量だが低速の、より安価なメモリ（たとえばDRAM（ダイナミック・ランダム・アクセス・メモリ））を用い、通常のストリング検索技法を用いることができる。
【０００７】
ネットワーク・プロセッサ（ネットワーク・プロセッサ・ユニット（NPU:  network  processor  unit）とも称される）は、そのコスト効率、処理速度、柔軟性およびアップグレード性のため、多様なネットワーキング装置でますます使われている。次世代ネットワーキング・プラットフォームを構築する際、堅牢なファイアウォール機能の追加は、特化したファイアウォール・コンポーネントの追加を必要とすることなく、ネットワーク・プロセッサ技術を利用して、NPUコードにファイアウォール機能を再使用可能かつスケーラブルな仕方で追加することにより行うことが望ましい。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
内容検査／パケット検査における主要な課題の一つは、複数パケットにまたがるパターンのスキャンに関わる。専用のファイアウォール資源（たとえば別個のコンポーネントまたはシステム上で走る内容検査アプリケーション）を使った通常の手法のもとでは、この問題は、単にパケット・ストリームをバッファリングすることによって解決される。複数パケットのペイロード内容が単一のバッファ中にまとめられ（これでパケット境界がなくなる）、転送されているデータ・ストリームのコピーが形成され、適切なパターンマッチング・アルゴリズムを用いてマッチがあるかどうかバッファ中のデータがスキャンされる。この技法は通常のパターンマッチング・アルゴリズムを修正する必要がない一方、記憶装置への著しい要求を課す。さらに、この機構は、フローが少なければシステム中に比較的簡単に実装できる一方、多数のフローを同時にサポートする必要があるシステムにはうまく拡張できない。さらに、この技法はネットワーク・プロセッサとともに使うのにもなじまないし、多数の同時フローがサポートされるべきときにはラインレートで実行できない。
【０００９】
以上の側面および本発明の付随する利点は、付属の図面と一緒に以下の詳細な記述を参照することによって本発明がよりよく理解されればより容易に認識されるであろう。図面において、同様の参照符号は、特に断りのない限りさまざまな図を通じて同様の部分を指す。
【発明を実施するための最良の形態】
【００１０】
ここではパケット境界をまたぐストリング検索を実行する方法および装置の実施形態を記載する。以下の記載では、本発明の実施形態の包括的な理解を与えるために数多くの個別的な詳細が述べられるが、当業者は、そうした個別的な詳細の一つまたは複数がなくても、あるいは他の方法、コンポーネント、材料などと一緒でも、本発明が実施できることを認識するであろう。その一方、本発明の諸側面をかすませるのを避けるため、よく知られた構造、材料または動作は詳細に図示や記述はしない。
【００１１】
本明細書における「ある実施形態」または「実施形態」という言及は、その実施形態との関連で述べられるある特定の特徴、構造または特性が本発明の少なくとも一つの実施形態に含まれることを意味する。よって、本明細書の随所に「ある実施形態では」といった句が現れることは、必ずしもそのすべてが同じ実施形態を指しているのではない。さらに、特定の特徴、構造または特性は一つまたは複数の実施形態においていかなる好適な仕方で組み合わされてもよい。
【００１２】
ここに記載された実施形態の諸側面によれば、ラインレート速度を維持し、スケーラブルな解決策を提供しつつ、パケット境界をまたぐ内容検査を容易にする機構が開示される。これらの機構は、部分ストリング検索の結果についての情報を維持しつつ、パケット境界で内容検査を停止および再開することを許容する、状態に基づく（state-based）内容検査を用いる。同時に、これらの機構は、NPUを使ってラインレート速度をサポートしつつ、最小限のバッファリングで実装できる。現代のネットワーク・プロセッサに対する機構の実装をよりよく認識し、理解するために、まず典型的なパイプライン・ベースのNPU処理動作について述べる。それに続いて、さまざまな実施形態の詳細を論じる。
【００１３】
インテル（登録商標）のIXP2xxxファミリーのネットワーク・プロセッサのような現代のネットワーク・プロセッサは、ラインレートのパケット処理動作を容易にするために、複数のマルチスレッド処理要素（たとえばマイクロエンジン（ME:  microengine））を用いる。パケットを処理するために、ネットワーク・プロセッサ（および／またはネットワーク・プロセッサを用いるネットワーク装置）は、パケット・ヘッダからパケットの宛先、サービスのクラスなどを示すデータを抽出し、ペイロード・データをメモリに保存し、パケット分類および待ち行列化動作を実行し、そのパケットについての次ホップを決定し、そのパケットを転送する適切なネットワーク・ポートを選択する、などの必要がある。これらの動作は一般に「パケット処理」動作と称される。
【００１４】
パケットに対する動作のいくつかは、他の機能へのインターフェースも最小限で、あるいは厳密な順序の実装をもって、よく定義されている。例としては、あるパケットの逐次のセグメントのためのDRAMバッファ内のパケット・データの現在アドレスのようなパケット状態情報の更新、送信のために待ち行列に入れたり待ち行列から出したりしつつ連結リスト（linked-list）ポインタを更新すること、およびある接続フロー（connection  flow）のパケットの監視（policing）またはマーキング（marking）を含む。これらの場合においては、動作は、所定のサイクル段予算の範囲内で実行できる。対照的に、一連のパケットに対する動作を厳密な順序に保ち、同時に多くの段にまたがるサイクル予算を達成することにおいては困難が生じうる。この種の機能を実行するコードのブロックは、コンテキスト・パイプ段（context  pipe  stage）と呼ばれる。
【００１５】
コンテキスト・パイプラインでは、時間の進行とともに種々の機能が種々のマイクロエンジン（ME）上で実行されていき、パケット・コンテキストは機能またはME間で渡される。その様子は図１に示されている。図示した構成では、z個のME  １００0-zがパケット処理動作のために使われ、各MEはn個のスレッドを走らせている。各MEは、そのMEによって実行される個別機能に対応するコンテキスト・パイプ段を構成する。二つ以上のコンテキスト・パイプ段をカスケードさせることで、コンテキスト・パイプラインが構成される。コンテキスト・パイプラインの名称は、パイプラインを通じて動いていくのがコンテキストであるという観察に由来する。
【００１６】
コンテキスト・パイプラインのもとで、ME内の各スレッドはパケットを割り当てられる。各スレッドは同じ機能を実行するが、それは異なるパケットに対してである。パケットが到着すると、パケットは厳密な順序でMEスレッドに割り当てられる。たとえば、インテルIXP2800（登録商標）MEの一つのコンテキスト・パイプ段においては、典型的には８つのスレッドが割り当てられる。８つのスレッドに割り当てられた８つのパケットのそれぞれは、その最初のパイプ段を、８つのパケット全部の到着レート以内に完了させなければならない。図１に示した命名法MEi.jでは、iはi番目のME番号に対応し、jはi番目のME上で走るj番目のスレッドに対応する。
【００１７】
より高度なコンテキスト・パイプライン化技法は、インターリーブされた段階的パイプ化（phased  piping）を用いる。この技法は同一のスレッド上に８パケット離間した複数パケットをインターリーブする。一例を挙げれば、ME0.1はパイプ段０の作業をパケット１に対して完了させ、パイプ段０の作業をパケット９に対して開始する。同様に、ME0.2はパケット２および１０に対してはたらくことになる。実際、一つのパイプ段では16個のパケットが同時に処理されることになる。パイプ段０はそれでも8パケットの到着レートごとに進まなければならない。インターリーブの利点は、メモリ遅延がまるまる8パケットの到着レートによってカバーされることである。
【００１８】
これから述べる諸実施形態の諸側面によれば、新しい内容検査方式および機構が、複数のマルチスレッド処理要素を用いるNPUを使って実装される。それらの方式は、共通のフローに割り当てられた個々のパケットの内容検査が、一つまたは複数の計算エンジン（たとえばマイクロエンジン）上で実行される異なる命令スレッドを使って実行されるコンテキスト・パイプライン化技法を介して実装される。それらの方式を容易にするため、内容検査状態情報が、前記命令スレッドおよび計算エンジンにとってアクセス可能であるデータ構造中に維持される。たとえば、第一の計算エンジン上で実行される第一のスレッドは、候補パターンにマッチするが単一のパケット内に完全に含まれてはいないストリング（すなわち、そのストリングの個々の部分が個々のパケットに含まれている）を集団的に含んでいる複数パケットのうちの第一のパケットに対してストリング検索を実行するために使われる。該第一のスレッドは、ストリング検索に係る状態情報を維持し、該情報は、第一のパケットの終わりに遭遇したときの部分マッチを同定する。一方、同じまたは異なる計算エンジンのいずれかで実行される第二のスレッドが、候補パターンの残りの部分のはじめを含む第二のパケットに対してストリング検索を実行するために用いられる。第二のスレッドは、第一のスレッドによって生成された状態情報を用いて、第一のスレッドがやめた点から検索を続ける。マッチが同定されると、対応する所定の規則またはアクション（「アクション・ターゲット」ともいう）に基づいて適切なアクションがされる。内容検査プロセス全体は、ラインレート速度をサポートする仕方の従来式のNPUパケット処理動作とパラレルな仕方で実行される。さらに、本機構は、多数の同時フローをサポートするよう簡単に拡張される。
【００１９】
図２は、ここに記載されるパケット処理動作の諸側面を実装するためのソフトウェア・アーキテクチャ２００のさまざまなコンポーネント、データ構造および処理ブロックの高レベルの概観を示している。コンポーネントとしては、深パケット検査手段（DPI:  Deep  Packet  Inspector）モジュール２０２、フロー・マネージャ・モジュール２０４、規則エンジン・モジュール２０６、ログ記録手段（logger）モジュール２０８およびターゲット・ハンドラ・モジュール２１０が含まれる。データ構造としては、フロー・テーブル２１２および規則テーブル２１４が含まれる。処理ブロックとしては、入力検証（verification）ブロック２１６、フロー有効確認（validation）ブロック２１８、規則マッチ・ブロック２２０、ログ例外ブロック２２２、例外生成ブロック２２４、ポリシー実行ブロック２２６および応答生成ブロック２２８が含まれる。
【００２０】
深パケット検査（Deep  Packet  Inspection）モジュール２０２は、適用可能な検索パターンに基づいてさまざまなストリング検索動作を実行するために使われる。これについてはのちにさらに詳細に述べる。フロー・マネージャ２０４は、フロー・テーブル２１２にアクセスし、これを管理するためのAPI（Application  Program  Interface［アプリケーション・プログラム・インターフェース］）を提供する。規則エンジン２０６は、あるレベルの変換（translation）を実装するAPIを、規則テーブル２１４に提供する。たとえば、ユーザー指定の規則は、高速経路（fast  path）（たとえば計算エンジン）処理コードによって使用可能な形になる前に複数レベルの変換を経ることになる。（ここで簡単のために示されているように）単一モジュールとして具現されるよりも、DPIモジュール２０２は、NPU計算エンジン上で走らされる対応するスレッドを介して実装されるさまざまなプロトコル固有機能の集合と考えられるべきである。
【００２１】
ログ記録手段モジュール２０８は、ログ記録機能を管理する。このモジュールは、ログ記録を直接扱ってもよいし、あるいはログ記録機能を実行するのに異なるプロセッサ（たとえば、NPU内の汎用プロセッサまたは別個のコンピュータ・ホスト内のプロセッサ）内の別のコンポーネントからのサービスを使ってもよい。典型的には、ファイアウォールにおけるログ記録機能は、単純なテキストベースのログ記録から包括的なレポート生成のためにデータをリレーショナル・データベースにダンプするまでさまざまでありうる。このモジュールの複雑さは、提供される機能に依存して変わる。
【００２２】
パケットが本システムにはいると、まず、プロトコル準拠性、チェックサムなどについて入力検証ブロック２１６によって検証される。ひとたびこの健全性チェックが実行されると、フロー有効確認ブロック２１８が、そのパケットが既知の（たとえば既存の）フローに属しているか、新しいフローを要求するかが検証される。そのパケットがどの既知のフローにも属していない場合には、フロー・テーブル２１２に新しい項目が追加され、パケット・メタデータ（たとえばヘッダ・データ）が規則マッチング・ブロック２２０に渡される。このブロックは、ある集合の一通りのマッチ構造について反復され、すべてのマッチについて条件が評価される。マッチされるにつれてターゲット・アクションがパケット・メタデータ内にエンコードされる。よって、パケットは、二つ以上のターゲット・アクションが関連付けられることができる。たとえば、パケットを先に送るとともに、ログ記録することが要求されてもよい。ひとたびパケットが諸規則に対してマッチされれば、そのパケットはさらなる処理のためにターゲット・ハンドラ・ブロック２１０に渡される。このブロックは、パケット・メタデータに関連付けられたアクションを実行する。
【００２３】
はいってくるパケットが既知のフローに属する場合、そのパケットは改めてアクセス規則にマッチされはしない。その代わり、そのパケットはターゲット・ハンドラ・モジュール２１０に直接渡され、ターゲット・ハンドラ・モジュール２１０が適用可能なアクション（単数または複数）のためのあらゆる必要な処理を実行する。そのフローのパケットに対して実行する必要のあるアクションは、そのフローについて存在している対応するフロー・テーブル項目に保存されているか、他の仕方でポイントされている。
【００２４】
図３のフローチャートを参照すると、各入力パケットの処理の間に以下の動作が実行される。プロセスはブロック３００で始まり、ここでフロー分類が実行される。一般に、フロー分類は、この目的のために一般に用いられるいくつかの方式のうちの一つによって実行されうる。典型的には、フローはACL規則データベースに基づいて分類されるが、他の分類機構が用いられてもよい。フロー分類の目的は、そのパケットを対応するフローに割り当てることである。
【００２５】
伝統的には、メッセージ（たとえばパケット）を分類するための規則はフィルタ（またはファイアウォールの用語では規則）と呼ばれ、パケットまたはフロー分類の問題は、ネットワーク要素のところにはいってくる各メッセージについて最低コストのマッチング・フィルタまたは規則を決定することである。関連情報は、各メッセージ（パケット）内のK個の相異なるフィールドに含まれている。たとえば、IPv4パケットのための関連フィールドは、宛先アドレス（32ビット）、発信元アドレス（32ビット）、プロトコル・フィールド（8ビット）、宛先ポート（16ビット）、発信元ポート（16ビット）および任意的にTCPフラグ（8ビット）を含みうる。フラグの数は限られているので、実装によってはプロトコルとフラグは一つのフィールドにまとめられてもよい。
【００２６】
図４ａは、５項組フロー分類方式を図解する、使用される例示的なパケット構造を示している。一般に、この方式は任意のK項組分類のために拡張できる。各パケットは、そのヘッダにさまざまなフィールドを含み、フィールドの数および詳細は転送機構に依存する（たとえばTCP/IPパケットはUDPパケットとは異なるフィールドをもつ）。パケット・ヘッダ・データに続いてパケット・ペイロード・データ（パケット・データまたはペイロードとも一般に称される）がある。任意的なパケット・フッタがパケットの末尾に含められていてもよい。
【００２７】
図４ａの図示された例では、ＦＬＤ１〜５によって描かれているように、分類を実行するもとになる５個のフィールドが選択されている。各パケット・フィールドは対応するフィールド値（Ｖ１〜ＶＮ）を含んでいる。ＦＬＤ１〜５は、発信元アドレス、宛先アドレス、発信元ポート、宛先ポート、プロトコル情報、誤り検査情報などといったヘッダ情報を表す。ペイロード・フィールド４００は、ペイロード・データを含むパケットの部分を定義する。場合によっては、ＦＬＤ  Ｎによって描かれるようなフッタ内の情報もフロー分類のために用いられてもよい。
【００２８】
たいていの分類方式では、ヘッダ情報のみが分類を実行するのに使われるが、個別的なACL規則に依存して、パケット・ペイロードおよび／またはフッタに含まれる追加的な情報を含めることが必要になることがある。簡潔のため、以下ではヘッダ情報のみに基づくパケット分類を論じる。
【００２９】
パケットが受信されると、そのパケットは解析されて、そのヘッダから、分類方式に基づいて、選択されたフィールド値が抽出される。図示した例については、これらはＦＬＤ１〜５からの値Ｖ１〜Ｖ５である。抽出されたフィールド値は次いで、そのパケットがマッチする分類規則の集合を、よって結果として得られるフローの関連付けられた集合を決定するための規則データベースを検索するために使われる。
【００３０】
図４ｂに図示されるように、フィルタ（ACL）データベースは、フィルタfilt1、filt2、…、filtNの有限の集合からなり、各フィルタは対応する分類規則およびフローに関連付けられている。各フィルタは、その分類方式に適用可能なフィールド（または部分的なフィールド）それぞれに一つの値で、合計K個の値の組み合わせである。フィルタ中の各フィールドは、完全一致（exact  match）、前方一致（prefix  match）または範囲一致（range  match）の三種類のマッチが許される。完全一致では、パケットのヘッダ・フィールドはフィルタ・フィールドに厳密に一致すべきである。前方一致では、フィルタ・フィールドはヘッダ・フィールドのプレフィックスであるべきである。範囲一致では、フィルタによって指定された範囲内にヘッダ値があるべきである。各フィルタfiltiは関連付けられた指令（directive）（すなわちアクション）をもち、それがそのフィルタにマッチするパケットをどのように扱うべきかを指定する。
【００３１】
一般に、分類規則マッチングは、数多くの既知の技法のうちの一つを使って実行されうる。たとえば、ある実施形態では、集約ビット・ベクトル（aggregated  bit  vector）方式が用いられる。この方式では、各フィールド値は、ACLテーブル内の諸マッチング規則を同定する対応するビット・ベクトルに関連付けられている。（実際上は、ほとんどとは言わないまでも多くのビット値はマッチがないことを示す0なので、ビット・ベクトルは、各ビット・ベクトルの記憶サイズを減らすために集約方式または階層方式を使って格納される。）ビット・ベクトルは次いで論理的にANDされ、その結果がマッチング規則を指定する。すると最高優先度のマッチング規則が簡単に同定されうる。他の方式、たとえばこれに限られないが、再帰フロー分類（RFC:  Recursive  Flow  Classification）（Pankaj  Gupta  and  Nick  McKeown,  Packet  Classification  on  Multiple  Fields,  ACM  SIGCOMM  1999）などを用いてもよい。
【００３２】
図３に戻ると、ひとたびパケットがフローに分類されると、判断ブロック３０２で、対応するフロー・データ構造（すなわちフロー・テーブル項目）がフロー・テーブル２１２に存在しているかどうかの判定がなされる。フロー・テーブル項目がすでに存在していれば、論理はブロック３０４に進み、フロー構造および対応する状態情報が取得される。フロー・テーブル項目がまだ存在していない場合には、ブロック３０６に示されるように、新しいフロー構造がフロー・テーブル内に割り当てられ、その状態が初期化される。フロー・データ構造および状態情報のさらなる詳細についてはのちに論じる。
【００３３】
ある実施形態では、フロー・テーブル項目は、二重ハッシュ方式を使うハッシュ・テーブルに維持されている。図５に示されるように、ハッシュ・テーブルは、SRAM（シンクロナス・ランダム・アクセス・メモリ）に維持される一次テーブルおよびDRAM（ダイナミック・ランダム・アクセス・メモリ）に維持される二次テーブルの二つのテーブルとして編成される。一次テーブルはスロットの集合に分割され、各スロット項目が二次テーブル内のフロー項目に対応する。一次テーブルは二つの指数によってインデックスされる：第一の値がスロット語を同定し（スロットは8ビット値――署名7ビットとフラグ1ビット――である）、第二の値（署名）が該スロットに保存されており、そのスロットを同定するために使われる。二次テーブルにおけるフロー項目は、スロット語指数およびマッチする署名値をもつスロット番号によってインデックスされる。フロー・テーブルはハッシュ・テーブルの二つの集合として維持される。第一のテーブルにおけるフロー項目の検索が失敗した場合に、第二のテーブルにおけるその項目の検索が実行される。
【００３４】
関連するフローに依存して、内容検査が要求されることも、されないこともある。たとえば、「信頼される」発信元アドレスから送られた、あるいは特定の宛先ポートに送られるパケットは、規則データベースによって信頼できると見なされてよく、「先に送る（forward）」という関連付けられたポリシー（すなわちアクション）をもつ対応する信頼されたフローに割り当てられることができる。対照的に、信頼されない発信元アドレスのために送られたパケットは、「破棄（drop）」という関連付けられたポリシーをもつ信頼されないフローに割り当てられうる。他の場合では、フローは「内容検査」という、内容の検査が実行されることを要求する関連付けられたポリシーをもつこともありうる。判断ブロック３０８によって描かれるように、内容検査が要求される場合、ブロック３１２において内容検査動作が、取得された状態情報をもって開始される。内容検査が要求されないパケットについては、継続ブロック３１０によって描かれるように、パケット処理の続きが実行される。
【００３５】
全体的に、検索機構の実装は二つの段階を含む：ビルドまたは前処理段階と、ランタイム段階である。ビルド段階の間に、さまざまなデータ構造およびテーブルがビルドされ、のちに対応する初期化動作の間にメモリ内に格納されるべく保存される。一般に進行的であるランタイム段階の間には、前記のデータ構造およびテーブルを使って受信されたパケットに対して検索が実行される。
【００３６】
ビルド段階のある実施形態の詳細が図６に示されている。プロセスはブロック６００で始まり、検索基準が定義される。これは、非常に一般的な形で、あるパターン（ストリング）の別のあるストリング（この例ではパケット・データ）内での生起を検索する問題として陳述できる。この問題は、古典的な文字列マッチング問題と同一である。それは形式的には次のように述べられる：
n文字のテキスト・ストリングTおよびm文字のパターン・ストリングPが与えられたとき、TにおけるPのすべての生起位置を見出せ。
【００３７】
ファイアウォール使用のコンテキストでは、上記の問題は、パケット・データ中でのウイルスもしくはワームのシグネチャ、プロトコル・コマンドまたは既知の実行形式の名前の存在を見出す問題に対応付けできる。通例は、すべての生起を見出すのではなく、T内のPの存在を検索すれば十分であろう（これは問題を真に緩和することにはならない。理論的にいうと、最初の生起を見出すことは、複数の生起を見出すことと同じくらい「困難」である）。たいていの実際的なファイアウォールおよびIDSアプリケーションでは、検索すべきシグネチャ・ストリングは前もって知られていないことがある。できうる最善のことは、ある特定のフローのコンテキストにおいて、フィールドを、検索する必要のあるパターンの集合に絞り込むことである。したがって、より一般的な問題は、所与のテキストT内におけるパターンの集合{P}のいずれかまたは全部の生起を検索することである。
【００３８】
時として、マッチされるべき厳密なストリング（単数または複数）は前もって知られていない。シグネチャは変形した形で生起することもできる。ここで、変形（morphing）とは、通例、元のパターンに対する小さな変更である。そのような場合、ストリングの近似マッチングも扱う必要がある。時に、既知のストリングではなく正規表現にマッチする必要があることもある。これらすべてのための技法はデータ・マイニングおよびデータ検索の用途で今日用いられている。一般に、これらのアルゴリズムは単純なストリング検索アルゴリズムよりいくぶん複雑であり、より高いメモリおよびサイクル要求をもつ。
【００３９】
前述したポリシー（条件）のコンテキストでは、異なるポリシーには異なるパターン集合{P}が適用されうる。たとえば、ある種のフローで検索するのは特定のパターン集合だけでよいこともあり、他のフローはより広い、あるいは全く異なるパターン集合の検索を含むこともある。したがって、適切なパターン集合が各ポリシーのために指定される。一般に、用いられる検索アルゴリズムに依存して、パターン集合は厳密なマッチ（exact  matches）を含んでいてもよいし、および／または近似的なマッチ（たとえばワイルドカード文字を使ったマッチ）を含んでいてもよい。
【００４０】
次に、ブロック６０２で、データ構造および関係するテーブル（まとめてパターン・データ構造（DS:  data  structures）と称される）が、用いられるべき選択された検索アルゴリズム（単数または複数）に基づいてビルドされる。この側面は以下のさらなる詳細においてカバーされる。
【００４１】
判断ブロック６０４によって描かれるように、オフセットおよび／または深さ情報も検索基準に関連付けられていてもよい。しばしば、ある特定のパターンについては、単にそれを構成するバイトのストリングよりも多くの情報が知られている。そのような情報は、パケット（または対応するビット・ストリーム）中で、パターンが生起しうる領域を絞り込むのを助けることがありうる。ここでの用法では、この情報はオフセットおよび深さを含む。オフセット値は、パケット（またはビット・ストリーム）先頭から、検索を開始する前にスキップできるバイト数を示す。深さ値は、パターンを見出す可能性を有するために検索する必要のある、パケット（またはビット・ストリーム）内の最大バイト数を示す。オフセット値と深さ値はタグ値とも称される。
【００４２】
そのような情報は、単一パターンに関する場合には非常に有用だが、各パターンが異なるオフセットおよび深さを有しうる複数パターンの場合に拡張するのは少しばかり難しくなる。この情報を使う素朴な方法は、単に、適用可能な状態機械において受理状態（accepting  state）に達するたびにタグ値を検査することである。だが、これは非効率的であり、かつ誤っている。受理状態に達したときにオフセットまたは深さがマッチしない場合、（機械内で）異なる経路に外れることによって、他の（有効な）パターンを潜在的に見逃した可能性があるのである。したがって、オフセットおよび深さの検査は、アルゴリズムの全ステップに組み込んで、正しい状態遷移がなされるようにしてやる必要がある。これが達成される一つの方法は、適切なタグ値情報を適用可能なパターン・データ構造中に組み込む（加える）ことによってである。これはブロック６０６に描かれており、のちにさらに詳細に説明する。パターン・データ構造が完全にビルドされたのち、該パターン・データ構造はブロック６０８でファイルなどに保存される。その後の初期化動作の間、該パターン・データ構造はメモリおよび／またはコード記憶にロードされ、対応するパターン・データ探索データがメモリにロードされる。これはそれぞれブロック６１０および６１２に描かれている。
【００４３】
このデータがどこにどのようにして保存されるかを解説するため、図７に示されている実行環境に注意を向ける。実行環境は、NPU７０２を含むネットワーク・ライン・カード７００に係り、該NPU７０２は、SRAMインターフェース（I/F）７０５を介してSRAM記憶（SRAM）７０４に結合され、DRAMインターフェース７０７を介してDRAM記憶（DRAM）７０６に結合されている。NPU７０２について選択されたモジュールも描かれている。それには、深パケット検査モジュール２０２、フロー・マネージャ・モジュール２０４、待ち行列マネージャ・モジュール７０８、受信エンジン７１０およびバッファ・マネージャ７１２が含まれる。上記した仕方で、これらのモジュールのそれぞれに関連付けられた動作は、ME７１４上で実行される対応する命令スレッドによって容易にされる。ある実施形態では、命令スレッドは初期には命令記憶７１５に記憶されている。該命令記憶７１５は、フラッシュメモリまたは大容量記憶装置などのような不揮発性記憶装置を含む。
【００４４】
図７に示されるように、さまざまなデータ構造およびテーブルはSRAM７０４に記憶されている。これらは、フロー・テーブル２１２、ポリシー・データ構造テーブル７１６およびパターン・データ構造テーブル７１８を含む。また、パケット・メタデータ７２０は典型的にはやはりSRAMに記憶される。図５を参照して上記したように、フロー・テーブルの各部分は、SRAM７０４とDRAM７０６の間で分割されてもよい。簡単のため、図７ではフロー・テーブル２１２の全体がSRAM７０４内に描かれている。
【００４５】
典型的には、パケット処理のために頻繁にアクセスされる情報（たとえばメタデータ７２０）はSRAMに記憶され、まとまったパケット・データ（パケット全体またはパケット・ペイロード全体）はDRAMに記憶される。この後者はアクセス遅延が長くなるが、コストは著しく低くなる。したがって、典型的な実装では、DRAM記憶において利用可能なメモリ・スペースは、SRAM記憶によって提供されるよりずっと大きい。
【００４６】
図７の左下コーナーに示されるように、各ME７１４はローカル・メモリ７２２、ローカル・レジスタ７２４、別個のSRAMおよびDRAM読み出しおよび書き込みバッファ７２６（便宜上、単一のブロックとして描かれている）、コード記憶７２８および計算コア（たとえば、演算論理回路（ALU:  Arithmetic  Logic  Unit））７３０を含む。一般に、情報はSRAMおよびDRAM書き込みおよび読み出しバッファを介してMEから、あるいはMEに渡されうる。さらに、ある実施形態では、チェーンまたはクラスタに構成されているMEどうしの間でデータが効率的に渡されることを可能にする、次の隣人（next  neighbor）バッファ（図示せず）が設けられる。
【００４７】
のちに述べるように、各パターン・データ構造は、対応する状態機械またはテーブル・ベースの機械を実現するための情報を与える。さまざまなパターン・データ構造は典型的には図７に示されるようにパターン・データ構造７１８内に記憶されるが、選択されたパターン・データ構造が、命令コードとデータ両方を記憶するように構成された選択されたコード記憶内に記憶される例もありうる。
【００４８】
図６について上記したように、ブロック６１２では、パターン・データ構造を記憶することに加えて、関連付けられたパターン・データ構造探索データも同様に記憶される。図７に示した実施形態では、探索データは、ポリシー・データ構造テーブル７１６における対応するポリシーに関連付けられたポインタとして記憶される。他の方式も採用されうる。パターン・データ構造探索データは、部分的には、のちに述べる仕方でフロー・テーブル項目をビルドするために使用される。
【００４９】
ランタイムの内容検査段階の間に実行される動作の概観が図８ａおよび図８ｂに示されている。ここで、図８ａは、フロー中の第一のパケットの処理の間に実行される動作を描いており、図８ｂはフロー中のその後の任意のパケット（i番目のパケットによって表されている）の処理の間に実行される動作を描いている。図８ａおよび図８ｂのそれぞれにおけるブロック８００に示されるように、入力バケットを受信するのに応答して、初期パケット処理動作が、一つまたは複数のME７１４上での一つまたは複数のスレッドの実行を介して実行される。これらのスレッドを内容検査のために使われる他のスレッドから区別するため、図８ａおよび図８ｂではこれらのスレッドは検索前（pre-search）スレッドと表示されている。
【００５０】
より詳細には、図７を参照すると、入力パケット７３２がライン・カード７００で受信されると、入力パケットは受信エンジン７１０によって処理される。該受信エンジン７１０は入力パケットを、進行中のコンテキスト・パイプライン・パケット処理動作に関連付けて、一時的に受信（Rx）バッファ７３４に保存する。パケット・ヘッダが抽出され、対応するパケット・メタデータ７２０がSRAM７０４に記憶される。パケットはまた、上で論じた仕方で分離され、既存のまたは新しいフローに割り当てられる。各フローは、DRAM７０６に保存されている関連付けられた待ち行列をもつ。このことはフロー待ち行列７３６によって描かれている。待ち行列は一般に待ち行列マネージャ７０８および／またはフロー・マネージャ２０４によって管理される。フロー待ち行列の生成に際して、関連付けられた情報がメタデータ７２０に加えられ、それにより待ち行列からの取り出し（dequeuing）のようなその後の動作のために、待ち行列中の最初（先頭）と最後（末尾）がすぐに同定できる。
【００５１】
パケット・ストリームは、さまざまなネットワーク・ノードから、フロー・ポリシーおよびその他の基準さらにはもっと予測しにくいネットワーク動作に基づいて非同期的な仕方で受信される。結果として、図７に示されるように、逐次ベースでは、種々のフローからのパケットが混ざり合った仕方で受信されうる。たとえば、入力パケット７３２にそれぞれはF#-#と表示されている。ここで、F#はフローを同定し、-#は所与のフローの逐次的なパケットを同定する。理解されるであろうように、パケットは、該パケットが意図されているフローを特定的に同定する情報は含まず、そのような情報はフロー分類の間に決定される。しかしながら、パケット・シーケンス・データは、TCPヘッダのような適用可能なパケット・ヘッダにおいて与えられる（たとえばTCPパケット・シーケンス番号）。図７では、フロー待ち行列７３６はフロー#1における最初の５つのパケットを含んでいる。以前と同様、パケットは、ブロック８００において実行される待ち行列化動作の間に、分類されたのち、対応するフロー待ち行列に加えられる。
【００５２】
ブロック８００の動作に続いて、図３に示されるのに類似の動作が実行され、要求される内容検索が実現される。上で論じたように、パケットが新しいフローに割り当てられる場合には、ブロック３０６で対応するフロー・テーブル項目が生成される。図７に示した実施形態では、各フロー・テーブル項目はフローID、バッファ・ポインタ、ポリシー・ポインタ、パターン・データ構造ポインタ、状態情報および統計情報を含む。（フロー・テーブル項目は図示していない他の情報をも含んでいてもよい。）フローIDは、フロー・テーブル項目探索のために使われ、ある実施形態では図５に示したフロー・テーブル・インデックス方式に従うハッシュ・インデックスを含む。ある実施形態では、バッファ・ポインタは適用可能なメタデータ７２０をポイントし、該メタデータ７２０が今度はフロー・テーブル項目に関連付けられたフロー待ち行列中の先頭パケットおよび末尾パケットへのポインタを含む。ポリシー・ポインタは、ポリシー・データ構造テーブル７１６内のポリシー・データ構造をポイントする。上で論じたように、各フローはポリシーに関連付けられる。フロー分類の間に、ポリシーが同定され、対応するポリシー・ポインタがフロー・マネージャ２０４に与えられる。
【００５３】
上で論じたように、内容検査を要求する各ポリシーは、パターン・データ構造にも関連付けられている。こうして、ある実施形態では、パターン・データ構造ポインタはポリシー・データ構造から抽出されうる。
【００５４】
状態情報は、深パケット検査モジュール２０２によって使われる対応するアルゴリズム状態の状態を保存するために使われるもので、のちにより詳細に述べる。統計情報はさまざまな目的のために使われ、それには内容検査が完了したフローにおける最終パケットの現在シーケンス番号を同定することが含まれる。このようにして、所与のフローについて検査されるべき次のパケットが、対応するフロー待ち行列における先頭パケットに対するその相対位置に基づいて同定されうる。
【００５５】
図８ａのブロック８０２Ａに示されるように、パケットがフロー中の最初のパケットであれば、ある第一のスレッドがME７１４上で立ち上げられ、適用可能なパターン集合{P}に鑑みて何らかのマッチを同定すべくそのパケットのパターン検索を実行する。したがって、このパケットのための新しいフロー・テーブル項目に対応する、状態情報を含むデータがスレッドによって読み込まれるが、該状態情報は状態機械が初期状態にあることを示す。ブロック８０４では、対応するフロー待ち行列におけるパケットの位置が、バッファ・ポインタおよびメタデータを使って同定され、パケットがMEのローカル・メモリ７２２にコピーされる。ブロック８０６Ｂでは、適用可能なパターン・データ構造（前記のパターン・データ構造ポインタによって同定される）がパターン・データ構造テーブル７１８から取得され、ローカル・メモリ７２２にコピーされる。対応する検索アルゴリズムの既存の状態７３８は初期状態に初期化されるが、該初期状態は部分一致が現在存在していないことを示すものである。
【００５６】
パターン検索動作はパケットの先頭（たとえば、パケット・ペイロード・データの先頭）で開始され、パケットの末尾に達するまで反復的な仕方で実行される。開始ループ・ブロック８０８および終了ループ・ブロック８１６によって描かれるように、適用可能なアルゴリズム機械は、その特定の検索アルゴリズムに依存して一文字または複数文字を有しうる検索きざみを用いる。各きざみに応答して、機械の既存の状態７３８が適宜更新される。ブロック８１２では、機械によって全体の一致（full  match）が同定されたかどうかの判定がなされる。そうであれば、継続ブロック８１４によって描かれるように、検索条件のための関連付けられたアクションが実行され、スレッドは終了する。
【００５７】
一般に、関連付けられたアクションは、同じまたは別のME上の同じまたは別の（こちらのほうがありそう）スレッドによって実行されうる。任意的に、関連付けられたアクションはNPUの汎用プロセッサ（明快のため図示せず）によって実行されてもよい。一致するストリングが悪意のあるワームなどの存在を同定している場合、関連付けられたアクションは典型的にはそのフローにおける残りのパケットすべてを破棄し、可能性としてはその発信元アドレスについてACLデータベース・アクションを更新することであろう。残りのパケットを破棄することは、対応するフロー・テーブル項目におけるポリシー・ポインタを更新して、そのフローについてのポリシーが「内容を検査」から「破棄」に実質的に切り換えられるようにすることによって達成されうる。
【００５８】
ひとたびパターン検索アルゴリズムが（マッチなしに）パケットの終わりに達したら、関連付けられたフロー・テーブル項目における状態情報および統計情報がブロック８１８で更新される。この時点で、第一のスレッドの実行は終了する。
【００５９】
図８ｂに目を転じると、同じフローに分類されたその後のパケットの受信に際して、同様の動作が実行される。そのことは図８ａおよび図８ｂにおける同様の番号をもつブロックに示されている。ブロック８０２Ｂでは、i番目のスレッドが同じまたは別のME７１４上で立ち上げられる。ここで、iはパケット・シーケンス番号（ヘッダにおける実際のシーケンス番号から規格化されたもの）を表す。最初のパケットを処理したあとでは、読み込まれたフロー・テーブル項目は、前のパケットによって更新された既存の状態を含む既存の項目であろう。前と同様、統計を含むフロー・テーブル項目情報は、フロー待ち行列においてそのパケットを位置特定するために使われる。その後、該パケットはブロック８０４においてMEのローカル・メモリ７２２にコピーされる
ブロック８０６Ｂでは、適用可能なパターン・データ構造がMEによって図８ａのブロック８０６Ａと同様の仕方で取得される。しかしながら、前のパケット（たとえば最初のパケット）を処理した結果として、機械の状態は前のパケットによって更新された既存の状態に初期化されるであろう。直前のパケットの終わりにおいて部分一致が存在していた場合には、その既存の状態は機械において初期状態（たとえば0）以外のどこかにある。部分一致が存在していなかった場合には、既存の状態は初期状態である。
【００６０】
ブロック８０８、８１０、８１２、８１４、８１６のパターン検索動作は最初のパケットに適用されるのと同様の仕方で実行される。唯一の違いは機械の初期状態である。したがって、直前のパケットの終わりの時点で部分一致が存在していた場合、パターン検索は、状態機械がやめた点で開始され、パターン集合{P}の中の一つまたは複数のストリングの第二の部分（残りのマッチする部分）をさがす。前と同様、全体の一致が同定される場合には、関連付けられたアクションが継続ブロック８１４で実行される。
【００６１】
上で論じたように、検索基準はそれぞれのパターン・ストリングについてオフセットおよび深さの値を指定することがある。この場合、パターン検索処理はこの追加的な検索情報を取り入れるよう増強されうる。図９に示されるように、図８ａまたは８ｂ（適用可能なほう）がすでに実行済みであるとして、パケットの先頭から開始する。ブロック９００では、パケットの一部がスキップされてオフセットに到達し、この点から検索が始まる。のちに論じるさらなる詳細では、この動作は個々のパターン検索ごとに実装されうる。つまり、複数パターン検索が採用されるとき、いくつかのパターンが他のいくつかのパターンとは異なる点でオフセットされてもよいのである。パケットがフローにおける最初のパケットである場合、オフセットに対応するバイト数がパケットのはじめからスキップされる。
【００６２】
一つまた複数の検索パターンについてオフセットが最初のパケットの全長よりも大きいことが理論的には可能である。したがって、この場合、そのような検索パターンについてはパケット全体がスキップされ、最初のパケットの長さがオフセット値から差し引かれる。それにより、後続パケットについてスキップされるべきオフセットの部分は、ビット・ストリームのどれだけがすでにスキップされているかを考慮することになる。たとえば、特定の検索パターンについてのオフセットが所与のプロトコルについてのパケット・ペイロードの最大サイズより大きい場合を考える。この特定の検索パターンについては、最初のパケット全体がスキップされ、検索は、元のオフセットと最初のパケットの大きさとの差に等しいオフセットのところで第二のパケットにおいて始まることになる。ある実施形態では、このマルチパケット・オフセット方式は、関連付けられたフロー・テーブル項目における適切な統計情報を更新することによって容易にされうる。これについてはのちにブロック９２０を参照しつつ論じる。
【００６３】
開始ループ・ブロック９０２および終了ループ・ブロック９１４によって描かれるように、パターン検索は、パケット・ペイロード・データにわたる反復を含む。データ内での位置は、その検索アルゴリズムによって用いられる適用可能な検索きざみによって進められる。パターン集合{P}における各検索パターンのための開始点はその検索パターンのための有効オフセットであろう。各検索きざみだけ動くのに応じて、ブロック９０４で状態機械が更新される。判断ブロック９０６で示されるように、機械によって検索ストリングの一致が示される場合、継続ブロック９０８で、関連付けられたアクションが実行される。マッチが存在しない場合には、論理は判断ブロック９１０に進んで、該当する検索ストリングについて、深さに達しているかどうかが判定される。もし達していれば、そのストリングについての検索は、終了ブロック９１２に描かれるように、完了である。達していなければ、プロセスは開始ループ・ブロック９０２に戻り、次の反復を開始する。
【００６４】
パケットの終わりに到達すると、判断ブロック９１６に描かれているように、実装に依存して二つのアクションが生じうる。フローにおける最初のパケットしか検索しない実施形態では、そのフローについての検索プロセスは、マッチが見出されなかったとして完了である。結果として、フロー・テーブル項目におけるポリシー・ポインタがブロック９１８で、内容検索を実行しないポリシーをポイントするように更新される。それにより、そのフロー中の残りのパケットに対しては検索は実行されない。（オフセットの側面に関する）マルチパケット検索がサポートさている場合には、ブロック９２０に描かれているように、次のパケットについて用いられるべきオフセットにおけるスキップされるパケットの大きさを取り入れるよう、フロー・テーブル項目において統計情報が更新される。
【００６５】
ある実施形態では、所与の検索パターンについて用いられる有効深さがマルチパケット検索をサポートするよう調整されることができる。たとえば、オフセットが最初のパケットの大きさよりも小さい一方、深さは最初のパケットの大きさより大きい状況を考える。この状況は、第一のパケットの大きさだけ第二のパケットに適用される深さの値を減らすことによって対処できる。ブロック９２０においては、この動作も実行されうる。さらに、このシナリオでは、フロー・テーブル項目において、状態情報も、上で論じたのと同じ仕方で最初のパケットの終わりに状態機械の状態を反映するよう更新されることを注意しておく。
【００６６】
ある実施形態では、適用可能なパターン・データ構造に含まれるデータを介して、オフセットおよび深さの動作を実施するための機構が提供される。したがって、図９にはブロック９２２が含まれていて、マルチパケット実装のもとでのオフセットおよび／または深さを取り入れるようパターン・データ構造が調整されることを示している。この動作は、ブロック９２０で更新された統計情報を使って、別のスレッド（そのフローにおける次のパケットを処理するために立ち上げられる）によって実行される。
【００６７】
〈複数パターン検索アルゴリズム〉
複数パターンの生起を検索する最も単純な方法は、数あるよく知られた単一パターン・アルゴリズムのうち任意のものを一つ一つのパターンに反復的に適用することである。1970年代の終わり以来、いくつもの複数パターン・アルゴリズムが提案されてきた。FSM（Finite  State  Machine［有限状態機械］）系の諸アルゴリズムが伝統的には研究の焦点であったが、FSMを使わない他の効率的なアルゴリズムもある。Wu  and  Manberによって提案されたものがその例である。
【００６８】
FSMアルゴリズムは、以下の考察に基づいている。有限アルファベットおよびパターンが与えられたときに、テキスト・ストリングを処理してそのパターンの生起を返すことのできる有限状態オートマトンを効率的な仕方で構築することが可能である。機械におけるあらゆる状態（数字で表される）は、前記パターンのうちそれまでにマッチした最長プレフィックスに対応する。これは、テキスト中のあらゆる文字をスキャンする必要があるのがちょうど１回であるという性質をもつ。前処理は主として、機械遷移関数（machine  transition  function）を計算することに関する。アルゴリズムの実行は、検索テキストをFSMに入力として供給することに関わる。Pの生起は、受理状態に達したときに常に検出される。
【００６９】
一般に、ここに記載される諸実施形態によって用いられるパターン検索のためには、どの型のFSMアルゴリズムを実装してもよい。FSMアルゴリズムがどのように機能するかをよりよく理解するために、有名なAho-Corasick  (AC)アルゴリズム（A.  V.  Aho,  M.  Corasick,  “Efficient  string  matching:  an  aid  to  bibliographic  search”,  Communications  of  the  ACM,  vol.  18  (1975)  333-340）の簡潔な記述をこれから論じる。以下の記述は上記の文書から取られている。
【００７０】
K＝{y1,y2,...,yk}をキーワードと呼ばれるストリングの有限集合とし、xを任意のストリングとし、xのことをテキスト・ストリングと呼ぶことにする。我々の問題は、xのうち、Kに含まれるキーワードになっている部分ストリングをすべて位置特定し、同定することである。複数の部分ストリングが互いに重なり合っていてもよい。Kについてのパターン・マッチング機械とは、入力としてテキスト・ストリングxを取り、出力としてKのキーワードが部分ストリングとして現れるx内の位置を生成するプログラムである。パターン・マッチング機械は一組の状態からなる。各状態はある数字によって表される。機械は、x内の記号を逐次読み、状態遷移をして、時折出力を出すことによってテキスト・ストリングxを処理する。パターン・マッチング機械の振る舞いは、三つの関数によって支配される。その三つの関数とは、移行（goto）関数g、失敗（failure）関数fおよび出力（output）関数outputである。
【００７１】
図１０は、キーワードの集合{he,she,his,hers}についてのパターン・マッチング機械によって使用される関数を示している。状態は0,1,...,9である。移行関数gは状態と入力記号からなる対を状態またはメッセージ「失敗」にマッピングする。有向グラフが移行関数を表している。たとえば、0から1へのhと表示したエッジはg(0,h)＝1となることを示している。矢印がなければ「fail（失敗）」を表す。よって、eでもiでもないあらゆる入力シンボルσについてg(1,σ)＝failである。すべてのパターン・マッチング機械は、あらゆる入力記号σについてg(0,σ)≠failという性質をもっている。状態0についての移行関数のこの性質は、機械によって、機械サイクル毎に一つの入力記号が処理されることを保証する。失敗関数fは状態を状態にマッピングする。失敗関数は、移行関数がfailを報告するたびに参照される。あるいくつかの状態は、キーワードの集合がみつかったことを示す出力状態として指定されている。出力関数は、あらゆる状態にキーワードの集合（空でもよい）を関連付けることによってこの概念を定式化するものである。
【００７２】
パターン・マッチング機械の動作サイクル（operation  cycle）は次のように定義される。sを機械の現在の状態とし、aを入力ストリングxの現在の記号とする。
１．g(s,a)＝s′であれば、機械は移行遷移をする。状態s′にはいり、xの次の記号が現在入力記号となる。さらに、output(s′)が空でなければ、機械は集合output(s′)を、現在入力記号の位置とともに出す。動作サイクルはこれで完了となる。
２．g(s,a)＝failであれば、機械は失敗関数fを参照し、失敗遷移をすると言われる。f(s)＝s″であれば、機械は、s′を現在状態とし、aを現在の入力記号としてサイクルを繰り返す。
【００７３】
最初、機械の現在状態は開始状態であり、テキスト・ストリングの最初の記号が現在入力記号である。機械は次いで、テキスト・ストリングの各記号に対して1動作サイクルを行うことによってテキスト・ストリングを処理する。
【００７４】
〈DAWGマッチでの実装〉
ある実施形態では、DAWGマッチ・アルゴリズムとして知られるFSMベースのアルゴリズム（M.  Crochemore,  A.  Czumaj,  L.  Gasieniec,  T.  Lecroq,  W.  Plandowski,  and  W.  Rytter,  “Fast  practical  multi-pattern  matching”,  Inf.  Process.  Lett.,  71  ((3-4)):  107-113,  1999）が用いられる。このアルゴリズムはよりよい平均実行時間を得るためにAho-CorasickとBoyer-Mooreの考えを組み合わせたものである。それは、所与のパターン集合の逆パターンについてAC状態機械とDAWG（Directed  Acyclic  Word  Graph［有向非環形語グラフ］）の両方の計算を要求する。AC状態機械のための遷移関数を計算する間、シフト（shift）・テーブルも計算される。これは、ある特定の状態において、スキップされる領域にパターンが生起しないことを保証する最大シフトを記憶するものである（前記の状態は、これまでスキャンされたテキストのサフィックスに一致するパターンの最長プレフィックスに対応する）。この関数は、Apostolico-Giancarloスキップ関数に対応する。該アルゴリズムのあるステップで、DAWGはまず右から左へと不一致があるまでスキャンするのに使われ、不一致があったらAC機械が左から右へスキャンしてプレフィックスを認識してシフト値を決定するのに使われる。DAWGを使ってマッチされた文字の集合が前の段階でACによってマッチされたプレフィックスと重なったら、マッチが報告される。
【００７５】
DAWGマッチ・アルゴリズムのためのパターン・データ構造の一実施例を下記に呈示する。対応するメモリ・データ構造は図１１に示す。
struct  pattern{
char  *string;  /*バイトのストリングへのポインタ*/
int  length;  /*stringのバイト数*/
int  offset;  /*stringはテキストの最初のoffsetバイト以内に生じないはず*/
int  depth;  /*stringはテキストの最初のdepthバイト以内に生じる必要*/
char  fcase;  /*Flag(0=大文字・小文字の違いを無視;  1=大文字・小文字を区別)*/
struct  Pattern  *prev;  /*前のパターンへのポインタ（条件付き検索のため；prevがみつかったときのみstringを検索）*/
struct  Pattern  *next;  /*次のパターンへのポインタ（条件が満たされるためにはnextはテキスト中でstringのあとにくる必要（またはRegExの修正））*/
int  prev_pat_num;  /*あらかじめ順序付けられたリストにおけるprevのパターン番号*/
int  next_pat_num;  /*あらかじめ順序付けられたリストにおけるnextのパターン番号*/
int  distance;  /*offsetと同義；テキストの開始位置はprev（もしみつかれば）の終わりよりあとの最初のバイト*/
int  within;  /*depthと同義；テキストの開始位置はprev（もしみつかれば）の終わりよりあとの最初のバイト*/
int  exact;  /*テキスト中でのstringの厳密な開始位置*/
int  relative;  /*exactと同義；テキストの開始位置はprev（もしみつかれば）の終わりよりあとの最初のバイト*/
};
prevとnextの値は、定義されていない場合にはNULLである。offsetおよびdistanceのデフォルト値は、明示的に定義されない限り0とする。前処理については、ポインタ値prevおよびnextが使われる。マイクロコードでのアルゴリズム実装のためには、prev_pat_numおよびnext_pat_numが、より普遍的にはパターン・インデックス値が使われるように使われる（パターン構造が一定の大きさなので、これらの値から実際のパターン・アドレスが計算できる）。
【００７６】
図１１のメモリ・マップ・データ構造では、アドレスはワード（４バイト）境界に整列されている。実際のパターン・ストリングは、このデータ構造の最初のフィールドで示されるバイト・アドレスに始まるシーケンスである。実際上は、パターン・ストリングは連続的に、最後のパターン・データ構造の終わりのすぐあとに記憶される。これにより、メモリの事前割り当て、前処理の間の相対アドレスの計算が可能になり、維持される必要があるポインタも一つだけ（最初のパターン構造のアドレス）となる。
【００７７】
AC機械は、決定論的な有限状態オートマトン（Q,δ,f,s0,T）を用いる。ここで、Qは状態の集合、δは遷移関数、fは失敗関数、s0は開始状態、Tは受理状態の集合である。遷移関数は、所定の入力に際して、ある特定の状態からどの状態に移るかを決定する。失敗関数は、遷移関数によって定義されていない(状態,入力)対のための例外遷移を示す。
【００７８】
AC機械は、ノードのトライ（trie）として構成され、単に開始状態へのポインタによって指定できる。ある実施形態では、次のデータ構造が用いられる。対応するメモリ・データ構造が図１２に示されている。
struct  transition{
char  input;  /*状態遷移をトリガーするバイト値*/
struct  AC_node  *destination;  /*宛先AC機械状態（ノード）へのポインタ*/
};
struct  AC_node{
int  node_id;  /*状態IDとしての一意的な整数*/
int  shift;  /*最大の安全なシフト値（DAWGマッチ用）：
shiftは、スキップされる領域にパターンが生起できないことを保証しつつスキップできる最小距離*/
int  offset;  /*この状態によって示されるプレフィックスは、テキストの最初のoffsetバイトで、あるいはそれよりあとに終了する必要*/
int  depth;  /*この状態によって示されるプレフィックスは、テキストのdepthバイト以内に終了する必要*/
struct  AC_node  *fail;  /*失敗状態へのポインタ*/
int  num_transitions;  /*この状態からの遷移数*/
struct  transition  *next;  /*この状態からの遷移のリスト；入力バイトのASCII値により順序付けられている*/
char  faccepting;  /*フラグ（1=受理；0=非受理）*/
int  num_outputs;  /*状態が受理の場合の、認識されたパターン数*/
struct  Pattern  **output;  /*状態が受理の場合の、認識されたパターン*/
int  *pattern_numbers;  /*あらかじめ順序付けされたパターンのリストにおける、インデックス値としての、認識されたパターンのリスト*/
};
offset、faccepting、num_transitionsおよびnum_outputsのデフォルト値は、明示的に定義または計算されない限り、0である。depthのデフォルト値は、明示的に定義または計算されない限り、−1である。前処理（機械の計算）の間、ポインタはdestination、failおよびoutputのためにのみ使用される。マイクロコード実装は諸状態についてpattern_numbersおよびnode_idを使う（これらから実際のメモリ・アドレスが計算される）。
【００７９】
ある実施形態では、図１３に示されるように、AC機械インデックス構造が用いられる。インデックスおよび各AC機械ノードはメモリ内で独立して再配置可能なように設計されるが、状態IDによって順序付けされた連続的な仕方で状態情報を保存し、インデックスの直後に構造情報を保存することが有利である。これにより、種々のアドレス（相対）が前処理の間に計算されることが許容され、維持すべきポインタの数が一つ（インデックス構造の基底アドレス）に減り、メモリの事前割り当てが可能になる。
【００８０】
有向非環形語グラフまたはサフィックス・オートマトンは、所与の集合におけるパターンのあらゆるサフィックスを認識する（DAWGマッチ・アルゴリズムは入力として反転したパターンをとる）。DAWGは失敗関数をもたず、状態は、出力パターンが関連付けられている必要はない。DAWGデータ構造の一つの実施例を下記に呈示する。一方、対応するメモリ・データ構造は図１４に示されている。
struct  suf_transition{
char  input;  /*状態遷移をトリガーするバイト値*/
char  flag;  /*フラグ（0=一次エッジ；1=二次エッジ）*/
struct  DAWG_node  *destination;  /*宛先DAWG状態（ノード）へのポインタ*/
};
struct  DAWG_node{
int  node_id;  /*状態idとしての一意的な整数*/
int  num_transitions;  /*この状態からの遷移数*/
struct  suf_transition  *next;  /*この状態からの遷移のリスト；入力バイトのASCII値により順序付け*/
struct  DAWG_node  *suffix_pointer;  /*DAWGの計算のために使われる仮想木における親へのポインタ*/
}
flagおよびnum_transitionsのデフォルト値は、明示的に指定または計算されない限り、0である。flagはDAWGの構築のためにのみ使われ、実際のストリング・マッチングで果たす役割はない。ポインタは前処理（機械の計算）の間にはdestinationのためにのみ使われる。マイクロコード実装は状態のためにnode_idを使う（実際のメモリ・アドレスはこれらから計算される）。DAWG機械インデックス構造はAC機械インデックス構造と同一である。DAWGインデックスおよび構造は、AC機械について上で論じたのと同様の仕方で連続的に保存される。
【００８１】
DAWGのようなサフィックス木は、所与の集合内のパターンのあらゆるサフィックスを認識する（ACサフィックス木アルゴリズムは入力として反転したパターンをとる）。この構造は、本質的には、ほぐされて木になっていないDAWGであり、よってソースから他の任意の状態への一意的な経路がある。サフィックス木データ構造の一つの実施例の詳細を下記に与える。対応するメモリ・データ構造は図１５に示される。
struct  tree_transition{
char  input;  /*状態遷移をトリガーするバイト値*/
struct  suffix_node  *destination;  /*宛先サフィックス木状態（ノード）へのポインタ*/
};
struct  suffix_node{
int  node_id;  /*状態IDとしての一意的な整数*/
int  num_transitions;  /*この状態からの遷移数*/
struct  tree_transition  *next;  /*この状態からの遷移のリスト；入力バイトのASCII値により順序付け*/
struct  AC_node  *ACnode;  /*ソースから出発し、このサフィックス木状態によって認識されるパターンの反転を入力とするスキャンが終了するAC機械状態*/
};
num_transitionsのデフォルト値は、明示的に指定または計算されない限り、0である。ACnodeが、DAWGとサフィックス木とを区別するものである。サフィックス木では、各状態は、開始状態からバイトの一意的な経路（パターンの部分ストリング）によって到達される。したがって、各状態は、その通過されたストリングを表す一意的なAC機械ノードを有する。たとえば、サフィックス木における状態sが開始状態からストリングc1c2c3…cnによって到達可能であるとする。このストリングがAC機械への入力として提供されるとする。AC機械が状態dで止まるとすると、s->ACnodeの値はdにセットされる。前処理（機械の計算）の間は、ポインタはdestinationおよびACnodeについてのみ使われる。マイクロコード実装は諸状態のためにnode_idを使う（これらから実際のメモリ・アドレスが計算される）。サフィックス木機械は、AC機械インデックス構造と同一のインデックス構造を用いる。一方、サフィックス木インデックスおよび構造は、AC機械のために上で論じたのと同様の仕方で連続的に保存される。
【００８２】
パターン・データ構造をビルドするために使われる前処理動作の間、大文字・小文字を区別しないパターンについてパターン・リストがスキャンされる。状態機械を決定論的に保ち、かつ（パケット・ペイロード内で）大文字・小文字のどのような組み合わせで生起しようとそのようなパターンを認識できるために、ある実施形態では、その特定のパターンが生起しうるバイト・ストリングのあらゆる組み合わせが生成される。これらすべての新しい組み合わせがパターン・リストに追加されるが、prevポインタを使って元のパターンをポイントするため、これらの指数関数的な数の新しいパターンを記憶するためにメモリ・スペースが浪費されることはない。
【００８３】
実際上は、大文字・小文字を区別しないパターンを生成および／または除去するために用いられる選択動作は手動でもプログラムによるものでもよい。たとえば、同じ基本的な文字ストリングの組み合わせを、すべて小文字、すべて大文字および最初の文字のみ大文字の形を使って保存するのは納得がいくかもしれないが、ランダムに大文字を含む文字ストリングの形を生成することは典型的にはずっと恩恵が低いであろう。
【００８４】
以上の実装は、AhoおよびCorasickによって提案され、上に文献を示した基本的なAC機械構築アルゴリズムにいくつかの追加を提供する。それには次のようなものが含まれる：
シフト計算：これはCrochemore  et  al.によって提案されたDAWGマッチ・アルゴリズムのために必要である；
オフセットおよび深さ計算：パターンが、パケットのデフォルトの先頭および末尾に等しくないオフセットおよび深さを関連付けられている場合、各状態について値を計算する必要がある。各状態についてこれらの値を計算しなかったとすると、不要な状態遷移をすることになる；受理状態が見出されたときにのみ、出力パターンが有効かどうかを知るのであり、その過程でいくつかの有効なパターンを逃すかもしれない；
大文字・小文字を区別しないパターンを組み込む：大文字・小文字を区別しないパターンについてのあらゆる可能な組み合わせのストリングを計算することによって、大文字・小文字を区別しないパターンが常に認識されることを保証する。ある実施形態では、パターンの不要な組み合わせを保存するのではなく、任意の受理状態における出力が元パターンとしてマークされる。
【００８５】
図６、図７、図８ａ、図８ｂおよび図９に示され、上で論じた実施形態に鑑み、DAWGアルゴリズムおよびサフィックス木アルゴリズムは、選択されたME上のマイクロコード・スレッドの実行を介して実装される。以上の記述に加えて、動作は以下のようにまとめられる。まず、パターン集合{P}内の任意のパターンの可能な最長プレフィックスをTのサフィックスにマッチさせようとする試みがされる。上記のDAWGアルゴリズムおよびサフィックス木アルゴリズムについては、プレフィックス値は、集合{P}内のパターンを認識するAC機械の等価な状態によって表現できる。
【００８６】
フロー中の最初のパケットについては、前のパターンにおいてマッチされたパターンのプレフィックスは空のストリングである。よって、prev_state入力はAC機械の開始状態になる。何らかのパケットについて、この値が開始状態に等しくなければ、AC機械はTをその最初の文字から前方方向にスキャンするために使われ、該スキャンはprev_stateから始まって、好適なシフト値が得られてDAWGがそのスキャンを開始できるまで行われる。
【００８７】
ループ反復の間、パケット・スキャンの終わり付近で、DAWGによってスキャンされるべきパケット内容の部分ストリングがパケットの末端をまたぐであろう（すなわち、pos>=パケット・サイズ）。これが起こるとき、ループから外れて、最後のループ反復において機械がやめたところから（すなわちパケット中の同じ状態および同じ文字位置で）パケットのスキャンを再開する必要がある。AC機械スキャンはパケットの末端に達するまで続き、パケットの末端に達した時点で、AC機械状態が関連付けられたフロー・テーブル項目におけるprev_stateとして記録される。この状態は、シーケンス中の次のパケットを処理するための状態を初期化するために用いられる。
【００８８】
複数パケットにまたがるパターンを検出するためのこの機構は、そのフローのパケットが順に到着する場合にのみ機能する。prev_state値が意味をなすのは、現在パケットのシーケンス番号が、そのフローにおいて前に到着したパケットより1大きい場合のみである。パケットが順に到着しない場合（これはTCPおよびその他の接続指向の（connection-oriented）プロトコルにあてはまる）、そのようなパターン検出は、フロー項目中にprev_state値を保存するだけでは実行できない。この問題は、いくつかの状況については、そのような状態値の複数のインスタンスを、関連するパケット・シーケンス番号とともに記憶することによって対処されうる。しかしながら、この解決策は、シーケンス上では前のパケットがまだスキャンされていないうちにパケットが到着する場合には機能しない（というのも、我々の機械データ構造の性質上、パケットの先頭においてパターン・サフィックスを検出するのが難しくなるからである；パケットの末尾でプレフィックスを検出するのは比較的たやすい）。もう一つのアプローチは、状態値のバッファリングと保存の組み合わせを使うことである。この実装では、パケットがシーケンスを外れて到着する場合、シーケンス上それより前のパケットが到着してスキャンされるまでバッファリングされることができる。
【００８９】
上で論じたように、検索される必要のある単数または複数のパケットの部分を減らすために、オフセットおよび深さのタグ値が与えられてもよい。この発想は、AC機械のスキャンにおけるあらゆるステップの間に、オフセットおよび深さの値をスキャンされるべき文字位置に突き合わせて検査し、正しい経路を進んでいるかどうかを判断できるはずというものである。現在状態に関連付けられた値が現在のテキスト位置までマッチしない場合、失敗遷移がなされる。AC機械状態は、検索しているパターンの一つまたは複数のプレフィックスを表すものである。したがって、パターンを見逃さないことを保証するために、その状態のために最も保守的なオフセットおよび深さの値を設定する必要がある。このために我々が使う公式は、Crochemore  et  al.に、そして上記の前処理アルゴリズムに記載されているような、シフト値を計算するために使われる公式と同じである。パターンが処理されるときは常に、ある状態についてのオフセットおよび深さが、それぞれ開始状態からの距離およびパターンの末端までの距離に基づいて計算される。その後のパターンの処理の間にその状態に再び達すると、オフセットは、現在計算された値と前に設定された値のうち小さいほうとして計算される。深さは、現在計算された値と前に設定された値のうちの大きいほうとして計算される（未指定の深さは無限大、あらゆる指定値より大きな値となる）。オフセットおよび深さは失敗状態計算の間に変えられる必要はない。パケット・スキャンの間に無効なオフセットまたは深さをもつ状態に通りがかったら、失敗状態へのジャンプが自動的になされる。
【００９０】
以上の方式は、単一のパケットが検索される場合について機能する。上で論じたように、ある実施形態では、オフセットおよび／または深さがパケットをまたいで適用される場合を扱う用意がされる。この方式を実装するために、アプリケーション・パターン・データ構造を、ひとたびローカル・メモリにコピーされてから、オフセットおよび／または深さの値を調整するために、修正することが必要である。同時に、対応するデータは、関連するフロー・テーブル項目に（たとえば、統計情報中に）保存される必要がある。これは：１）パターン・データ構造が調整される必要があること；および２）その調整がどういうものでなければならないかを反映するためである。
【００９１】
多くの事例では、複数パケットにまたがるオフセットおよび深さ検索を実行することは不要である。適用可能なパターン集合が多数の検索ストリングを含む場合には、統計情報中に各パターンについてのオフセットおよび／または深さの情報を維持することも通例は実際的ではない。同時に、オフセットおよび深さの検索は、典型的には、特定のシグネチャ（あるいは、ほんの若干数のシグネチャ）をさがすために用いられる。結果として、そうしたシグネチャ（単数または複数）に対応する統計情報は、過度なメモリ量を消費することなく、フロー・テーブル項目において維持できる。パケットをまたぐオフセットおよび深さ検索がサポートされるかどうかは個々の実装に任される。
【００９２】
〈Wu-Manberアルゴリズムでの実装〉
いくつかの実施形態では、Wu-Manberアルゴリズム（[WM92]  S.  Wu,  U.  Manber,  “Fast  Text  Searching  Allowing  Errors”,  Communications  of  the  ACM  35  (10):  83-91  (1992);および[WM94]  S.  Wu  and  U.  Manber.  “A  fast  algorithm  for  multi-pattern  searching”.  Technical  Report  TR-94-17,  University  of  Arizona,  1994）に基づく検索方式が用いられる。Wu  and  Manberは上記の状態機械に基づくアルゴリズムから非常に難しいアプローチをとっている。これらのアルゴリズムは、単独の文字ではなく文字のブロックを同時にマッチングすることによる他のアプローチとも異なっている。パターンの全長をMとすると、ブロックの推奨サイズ（B）はlog|Σ|2Mである。アルゴリズムは、SHIFT、HASHおよびPREFIXと呼ばれる三つの探索表を事前計算する。SHIFTテーブルは、文字のブロックのハッシュされたマッピングである整数によってインデックスされる。このテーブルは、よく知られたBoyer-Mooreアルゴリズム（Boyer  and  J.  Moore.  “A  fast  string  searching  algorithm”.  Communications  of  the  ACM,  20:  762-772,  1977）における不良文字（bad  character）テーブルと等価である。複数のパターンに共通な部分ストリングのための項目は、より保守的であるために、最低限の可能なシフト値を含む。Bのより大きな値については、いくつかのストリングを同じ位置にマッピングし、各場合においてシフト値の最小値を設定することによってテーブルを圧縮することができる。SHIFTへのインデックスに使われる整数は、HASHへのインデックスにも使われる。HASHは、その整数にマッピングされるストリングへのポインタを保存するものである。PREFIXテーブルは、各パターンのプレフィックスについてハッシュ値を含んでおり、プレフィックスのサイズは実装による。各アルゴリズム・ステップにおいて、B文字の集合（スキャンされるテキスト部分ストリングの右端の）がハッシュされて一つの整数にされ、これがSHIFT値をさがすために使われる。この値が0より大きければ、テキストはシフトされる。そうでなければ、この部分ストリング（サイズms；ここでmsは最も短いパターンの長さ）のプレフィックスのハッシュが計算され、対応するHASH項目における各ストリングのプレフィックスにマッチされる（PREFIXテーブルを使って）。プレフィックスがマッチすれば、実際のテキスト・マッチが起こる。このアルゴリズムは、マッチングの際に最短パターン長のみが考慮されるので、パターン・サイズがほとんど一様であることに依存する。
【００９３】
パターン・データ構造もその対応するメモリ・データ構造も、DAWGマッチ・アルゴリズムのために使われたのと同一である。パターン・データ構造を標準化することで、内容検査フレームワークを拡張し、種々の検索アルゴリズムを実装することが容易になる。シフト・テーブルは、整数の二次元配列S[n][4]として構築される。図１６および下記の例示的なシフト・テーブル・メモリ・データ構造に示されるように、各テーブル項目S[k]は、整数配列へのポインタを有しており、整数配列は次の構造をもつ：
{
S[k][0]:  int;  /*一次シフト値*/
S[k][1]:  int;  /*二次シフト値*/
S[k][2]:  int;  /*オフセット*/
S[k][3]:  int;  /*深さ*/
}
「k」は、シフト・テーブルをインデックスするために使われる値である（通例はロング整数）。アルファベットの大きさがAで、ハッシュ値として使う部分ストリング（ストリングのひとかたまり）の大きさがBであるとすると、テーブルの最大サイズはABである。「k」は文字B個のブロックから得られる（一意的な）ハッシュ値である（最も単純なハッシュ関数は、そのブロックをB個の数字からなるA進数と考えることである）。一次シフト（primary  shift）とは、スキャン位置が右にシフトされなければならない距離を指す。この値が0になるのは、スキャンされた部分ストリングが、パターンの一つにおけるある好適な位置での部分ストリングにマッチする場合のみである。二次シフト（secondary  shift）とは、一次値が0であるときにのみスキャン位置を右にシフトしなければならない距離を指す。このシフト値は、primary_shift＝0についてテキスト位置を処理したあとで、デフォルトのシフト1を置き換える。この値は常に0より大きい（よって、primary_shiftが0に等しいときはそれより大きい）。
【００９４】
オフセットは、（すべてのパターンは打ち切られて最小パターン・サイズになっているとして）考えている現在部分ストリングで終わる有効なパターンが生起しうる、パケット内容の始まりからの最小距離である。深さは、（すべてのパターンは打ち切られた最小パターン・サイズになっているとして）考えている現在部分ストリングで終わる有効なパターンが終わるまでの、パケット内容の始まりからの最大距離である。オフセット、深さおよびsecondary_shift値が意味をなし、使用されるのは、primary_shift値が0である場合のみである。すなわち、テキスト（パケット内容）中の部分ストリングが考えられているパターンの一つの、終わりの部分にマッチするときのみである。
【００９５】
HASHテーブルは、ポインタH[n]の一次元配列として構築される。図１７の例示的なHASHテーブル・メモリ・データ構造に示されるように、各テーブル項目H[k]はパターン・データ構造へのポインタを有する。テーブルへのインデックスはシフト・テーブルの場合と同一である。パターン（打ち切られて最小パターン・サイズになっている）は、末尾のB文字のかたまりのハッシュ値によってソートされる。H[k]の値は、「k」以上のハッシュ値をもつこのソートされたリストにおける最初のパターンである。
【００９６】
パターン・データ構造は固定サイズをもつので、メモリからランダムな仕方でアクセスされることができる。したがって、パターン・データ構造のアドレスは、配列内でのパターンのシーケンス番号を使って計算できる。したがって、メモリ中でHASHテーブル内に保存されている値は、パターンを再配置可能にするため、実際のアドレスではなく、パターン・インデックス番号（0からパターン数−1までの範囲）をもつ。
【００９７】
PREFIXテーブルは、整数（通例はロング整数）の一次元配列として構築される。テーブルのサイズは、パターン集合内のパターン数に等しく、パターン（またはパターン・インデックス番号）はPrefixテーブルの任意の項目へのインデックスとして使われる。値Prefix[k]は、パターン番号「k」内の最初のB′個の文字のハッシュである（「k」は0からパターン数−1までの範囲）。ハッシュは典型的には、シフト・テーブルについて計算したのと同一の仕方で（プレフィクスをB′個の数字からなるA進数と考えることによって）計算される。メモリ表現では（その一つの実施例が図１８に示されている）、用いられるべきアルファベットはASCII集合全体を含むので、各テーブル項目は未修正のプレフィックス値である。
【００９８】
SHIFTテーブルおよびHASHテーブルの両方は大量の冗長な情報を含む。これらのテーブルの大きさは指数関数的である一方、パターンの集合は数は少ないと思われる。したがって、SHIFTテーブル値のほとんどは、デフォルト値に等しいと期待できる。同様に、多数のHASHテーブル項目は、決して探されることのない無用な情報を含むことになる。他方、メモリのこのかなりの浪費は、一定時間で情報を探し出すというパフォーマンス上の恩恵によって埋め合わされる。Bのより大きな値（3以上）については、メモリ使用は禁止的になり、よって、圧縮データ構造としては、どの情報をとってくるにも比較的少数の探索しか必要とされないB+木を使う。
【００９９】
B+木はノードの木として構築される。ここで、それぞれの葉はルートから一定距離をもつ。レベルの数は任意だが、我々は深さを2に選んだ。たいていの実用的な目的にはこれで十分であろう。それぞれの子ノードは、次の構造の配列である。
struct  hash_record{
long  key_value;  /*ハッシュ値（SHIFTテーブルおよびHASHテーブルへのインデックス）*/
int  primary_shift;  /*一次シフト（SHIFTテーブルにおけるような）*/
int  secondary_shift;  /*二次シフト（SHIFTテーブルにおけるような）*/
int  offset;  /*オフセット（SHIFTテーブルにおけるような）*/
int  depth;  /*深さ（SHIFTテーブルにおけるような）*/
struct  Pattern  *patlist_start;  /*パターン・リスト先頭へのポインタ（HASHテーブル項目）*/
struct  Pattern  *patlist_end;  /*パターン・リスト末尾へのポインタ（次のHASHテーブル項目）*/
int  pstart;  /*patlist_startのソートされたリスト中のパターン番号*/
int  pend;  /*patlist_endのソートされたリスト中のパターン番号*/
};
ルート・ノードは特別であり、一定サイズの配列である。各要素は次のように構築される：
struct  bplus_tree_node{
struct  hash_record  *list;  /*子ノードへのポインタ*/
int  num_elements;  /*list中の要素数*/
};
struct  bplus_tree_node  root[A];
ルート・ノードの例示的なメモリ構造は図１９に示されている。ルートは、struct bplus_tree_node型のA個の要素を有する。ここで、Aはアルファベットの大きさである（ASCII集合の場合は256）。
【０１００】
SHIFTテーブルを考える。インデックス値がB個の文字c1c2…cBのかたまりのハッシュであるとすると、ルートの各要素は、そのかたまりの最上位バイトc1のハッシュ値を計算することによってランダムにアクセスされることができる。そのかたまりの残り（c2…cB）は、子ノードの要素のkey_valueにマッピングされる。各子ノード（list）は、B−1の大きさのストリングについて、あらゆる可能なハッシュ値についての項目を含む必要はない。関連するデフォルトの一次シフト値（これは、最小パターンサイズ−B＋1に等しいであろう）をもたない要素についてのみ項目を含む。SHIFTテーブル[c1c2…cB]内に位置する情報にアクセスするには、root[c1].list(k)をさがす（ここで、list(k)は、root[c1].list内で、c2…cBのハッシュ値に等しいキー値（key  value）をもつ要素を指す）。HASHテーブル値も同じようにして探される。
【０１０１】
以上の構造の各項目の意味は一般に自明である。patlist_endおよびpendパラメータは、特定のHASHテーブル項目から得られるパターンのリスト内の最後のパターンを指すのではなく、次のHASH項目によってポイントされるパターン、あるいはグローバルなソートされたパターン・リストにおいてこのリストの次のパターンを指す。
【０１０２】
図２０は、子ノード・メモリ・データ構造の一つの実施例を示している。ルート・ノードおよび各子ノードは、メモリ内で独立して再配置可能なように設計されてはいるが、図２０の実施形態は、子ノードがルート構造のすぐあとにくるように実装されている。また、子ノードはメモリ内に連続的な仕方で書かれ、親要素のインデックス値によって順序付けられる。このデータを連続的に保存することは、メモリの事前割り当てを容易にし、明示的に指定される必要があるポインタが一つだけ（ルートの最初の語のアドレス）になる。
【０１０３】
Wu-Manberアルゴリズムは、すべてのパターンは等しい長さであると想定している。その正しい動作はこの想定に依拠している。これは実際的な想定ではないので、すべてのストリングを最短パターンの大きさになるよう打ち切る必要がある。アルゴリズム実行の際、完全なパターンがマッチされるのは、候補位置が発見されるときである。すべての前処理機能に渡されるパターンは打ち切られる。
【０１０４】
ビルドSHIFT、HASH、PREFIXおよびB+木を使った擬似コードの例が、本明細書の付録に与えられている。さらに、Wu-Manberアルゴリズムの変形を実装するための擬似コードも同様に付録に与えられている。
【０１０５】
付録のWu-Manberアルゴリズムは、[WM94]において記載されるアルゴリズムとはかなり変わっている。このアルゴリズムは、オフセット、深さおよび大文字・小文字の区別無視といった追加的な特徴をサポートする。基本的なアルゴリズムにおいてもさらに一つの相違がある。それは二次シフト値である。Wu  and  Manber[WM94]によって提案された元のアルゴリズムでは、一次シフト値が0とわかったら、スキップ値は常に強制的に1となった。これは、確実に正しい動作を保証するが、スキップ1は保守的すぎる。二次シフトは、考えている部分ストリング（サイズBのかたまり）にマッチするためにスキップされる必要のある最小距離を示す。このスキップのための最大の安全な値は、SHIFTテーブルの計算の際に計算された二番目に低いシフトとなる。これはまさに我々の二次シフトの定義である。
【０１０６】
Wu-Manberアルゴリズムの説明から明らかなように、前のパケットの終わりでマッチされる任意のパターン（サフィックス）の最大のプレフィックスが、アルゴリズムが次のパケットのために実行されるときにアルゴリズムへの入力として与えられる。この情報は二つの部分で与えられる：プレフィックスがマッチされたパターン・ストリングの最初のバイトのアドレスprefix_addressと、該プレフィックスの大きさprefix_length（またはうまくマッチされたパターンのバイト数）。フロー中の最初のパケットについては、前のパターンにおいてマッチされたパターンのプレフィックスは空ストリングであり、よってprefix_lengthパラメータの値は0となり、prefix_addressは未初期化状態となる。
【０１０７】
ループ反復の間に、パケット・スキャンの終わり付近で、テーブル項目へのインデックスとして使われるべきかたまりがパケットの末端をまたぐ（すなわち、位置>=パケット・サイズ）。これが起こるとき、部分的に、素朴なストリング・マッチング・アルゴリズムに回帰しなければならない。パケットの終わりにまだいくつかの検査される文字が残されている間は、それらが我々のパターン集合中のあらゆるパターンの（同じサイズの）プレフィックスにマッチされる。マッチが得られるや否や、該マッチの長さおよびアドレスがprefix_lengthおよびprefix_addressにそれぞれ記録される。シーケンス上、次のパケットがスキャンされるべきとき、このマッチしたプレフィックスがパケット内容に付加され、通常の仕方でスキャンが進行する。
【０１０８】
複数パケットにまたがるパターンにマッチするこの技法は、パケットがシーケンスから外れて到着すると失敗する。パケットの始まりにおいて任意のサフィックスにマッチして、それが前のパケットで始まったパターンの一部であることを期待するというのではうまくいかない。DAWGマッチの場合について述べたように、バッファリングと状態維持の組み合わせが包括的な解決策を与えることができる。
【０１０９】
いくつかの実施形態では、以上のWu-Manberアルゴリズムはオフセット／深さ検索のために用いられることがありうる。パターンにマッチしようと試みる間、オフセットと深さの制約条件が満たされることと、存在するかもしれないが無効な制限値をもつと判明するパターンをマッチしようとしてサイクルを無駄にしないことをも保証する必要もある。したがって、各SHIFTテーブル項目に有効なオフセットおよび深さの値を関連付ける。オフセットおよび深さの値は、シフト値と同じようにして、可能な最も安全な値を選択することによって設定される。バイトのかたまりSがSHIFTテーブルへのインデックスに使われる場合、対応するオフセットは、このかたまりで終わる任意のパターンの最小オフセットに設定される（該パターンはまず打ち切られて最短パターン長にされる）。同様に、深さは、(深さ−長さ＋最小パターン・サイズ)の最大値に設定される。これが、打ち切られたパターンがテキスト内のどこで終わらなければならないかを示すのである。
【０１１０】
パケット・スキャンの間、一次シフト値0が観測されると、まずオフセットおよび深さ（テーブルから探し出される）をチェックし、それらを現在テキスト位置にマッチする。制約条件が満たされる場合にのみ、HASHテーブルによって示されるパターンのリストを通じたサイクルに進む。この手順の間、PREFIXテーブル・マッチが成功したあとでかつパターン全体のマッチがバイトごとに試みられる前、パターン自身に関連付けられたオフセットおよび深さが現在のテキスト位置とマッチされる。現在位置が限界内であれば、完全なパターン・マッチが試みられる。上記したオフセットおよび深さのチェックのいずれかが失敗すれば、位置は、二次シフトに等しい値だけ進められ、検索が継続される。
【０１１１】
大文字・小文字の区別無視は幸運にも、DAWGマッチ・アルゴリズムに比べてWu-Manberアルゴリズムによって、ずっと大きなメモリ効率で扱える。必要になってくる追加的な仕事は、ほとんど前処理段階に移せる。SHIFTテーブルを更新する間、大文字・小文字を区別しないパターンが処理されれば、考えられている長さBのかたまりのあらゆる大文字・小文字を区別しない組み合わせが計算され、そうした組み合わせのそれぞれに対応するSHIFTテーブル項目は調整される。HASHテーブルおよびPREFIXテーブルについては、インデックス値とプレフィックス値は、大文字・小文字を区別しないパターンの小文字の等価物から計算される。
【０１１２】
パケット・スキャンの間、SHIFTテーブル探索はストレートであり、Wu  and  Manberによって提案された元のアルゴリズムに何らの追加も必要とされない。すべての潜在的な大文字・小文字の組み合わせについて有効なSHIFT項目が存在するからである。しかし、HASHテーブル探索については、二つの別個のインデックス値を計算する必要がある：
かたまりの文字そのままを使った通常のインデックス；および
Bかたまり内のすべての大文字を小文字に変換することによって計算された小文字インデックス。
【０１１３】
二番目のインデックスが必要なのは、大文字・小文字を区別しないパターンについてのHASH項目が小文字のみから計算されるからである。プレフィックスをチェックし、それに続いて完全なパターンをマッチングするサイクル全体は二度行われる。一度は通常のインデックス値について、もう一度は小文字のインデックス値についてである。同様に、パターン・プレフィックスの通常版と小文字版が計算される。考えているパターンが大文字・小文字を区別しない場合、小文字のプレフィックスがマッチングされ、そうでなければ、通常のプレフィックスがマッチングされる。ひとたびアルゴリズムが、パターンをバイトごとにパケット内容とマッチングするのに取りかかれば、大文字・小文字を区別しないマッチングはストレートになる。
【０１１４】
ある実施形態では、内容検査フレームワークは、前に実装されたステートフルな（stateful）ファイアウォール・フレームワークに組み込めるモジュールとして設計される。インテルIXP処理モデルのもとでは、内容検査フレームワークは、単一のマイクロブロックとして、任意のパケット処理パイプラインに組み込まれることができる。ある実施形態では、ファイアウォールは規則の処理のためにCA（条件‐アクション［Condition-Action］）対を使う。たとえば、ある種のCA規則は内容検査に係ることができる。特定の有害なパターンをパケット内容と突き合わせてチェックし（条件）、パターンが検出されたらそのパケットを破棄する（アクション）といったように。
【０１１５】
典型的な内容検査CA規則のためのメモリ・マップが図２１に示される。最初の２語（または最初のロング語）はリザーブされており、実際の情報は8バイトのオフセットのところから始まる。各フィールドの意味は次のとおりである。
【０１１６】
１．アルゴリズム・コード：これは使用すべきアルゴリズムの検索種別を示す：
1＝DAWGマッチ・アルゴリズム
2＝サフィックス木マッチ・アルゴリズム
3＝Wu-Manberアルゴリズム
4＝SHIFTテーブルおよびHASHテーブルの代わりにB+木構造を使ったWu-Manberアルゴリズム
5＝厳密な開始位置を与えられたパターンにマッチ（すなわち、パターンは指定された位置から始まるか、さもなければ全く生起しないと想定される）。
【０１１７】
２．SRAMアドレス：これは、パターン検索のために使われるデータ構造のアドレス（またはアドレスのインデックスへのポインタ）を示す。最初の４つのアルゴリズムについては、このアドレスはマスター・インデックスの最初の語をポイントする。これは、検査のために使われるさまざまなデータ構造のアドレスについての情報を含んでいる。
【０１１８】
３．「またがりパターン・チェック」ポリシー：最初の４つのアルゴリズム・コードについては、これは単に値0（複数パケットにまたがりうるパターンがあるかどうかチェックをするべきではないことを示す）または1（そのようなチェックがされなければならないことを示す）をもつフラグである。厳密位置マッチについては、このフィールドは、パターン・マッチが実行されるべきパケット内容内の位置を（最初のバイトからのオフセットとして）示す。
【０１１９】
複数パケットにまたがるパターンについてチェックするためには、フロー・テーブルにおける現在のフローに対応する項目とともに、部分マッチ情報を保存する必要がある（DAWGマッチについてはAC状態、Wu-Manberについてはパターン・アドレスおよびプレフィックス長）。また、処理されるべき次のパケットが到着するときに、保存されている情報の有効性に関する何らかの情報を保存する必要もある。したがって、TCPフローのために、次の期待されるオフセットのシーケンス番号を、状態情報とともに保存する。同様の種類のシーケンス情報は、その他いかなる接続指向のプロトコルのために保存されることもできる。
【０１２０】
フロー・テーブル項目のある実施形態では、この情報は、次の仕方で保存される。最初の語は、次のパケットの最初のバイトの期待されるシーケンス番号であり、二番目の語は前のスキャンの終わりからのAC機械状態（アルゴリズム・コード１および２について）またはプレフィックス長（アルゴリズム・コード３および４）であり、三番目の語は部分的にマッチされたパターン・アドレスである（アルゴリズム・コード３および４についてのみ使用）。
【０１２１】
初期化およびコード負荷
図７に戻ると、ネットワーク・ライン・カードまたはネットワーク・デバイスの初期化の間に、ここに記載されるさまざまなパケット処理および内容検査の機能および動作を容易にするコーディングされた命令（たとえばマイクロコード）が、選択されたMEのコントロール記憶７２８にロードされる。一般に、命令は、フラッシュメモリ・デバイスのような不揮発性記憶デバイスを含む命令記憶７１５からロードされてもよい。不揮発性記憶の他の例としては、読み出し専用メモリ（ROM）、プログラム可能ROM（PROM）および電気的に消去可能なPROM（EEPROM）が含まれる。
【０１２２】
（ライン・カード７００に）ローカルな記憶デバイスから命令をロードすることに加えて、命令は外部ソースからロードされてもよい。たとえば、ある実施形態では、命令は別のライン・カード（図示せず）によってホストされたディスク・ドライブ上に記憶されているか、そうでなければライン・カード７００がインストールされているネットワーク要素によって提供される。さらに別の実施形態では、命令はリモート・サーバーなどからネットワークを介して搬送波（carrier  wave）としてダウンロードされる。
【０１２３】
一般に、図面に示され、本稿で論じた機能ブロックのそれぞれは、ハードウェアのプログラム可能論理を使って実装されても、一つまたは複数の計算エンジン上での対応するスレッドの実行を介してファームウェア／ソフトウェアのプログラム可能論理を使って実装されても、両者の組み合わせを使って実装されてもよい。たとえば、ある実施形態では、深パケット検査モジュール２０２、フロー・マネージャ２０４、待ち行列マネージャ７０８および受信エンジン７１０のそれぞれについて描かれた動作は、NPU内の一つまたは複数の計算エンジン上の対応する命令スレッドを、パケット処理のために使われるコンテキスト・パイプラインに統合された仕方で実行することによって容易にされる。任意的に、上記の機能ブロックによって提供されるさまざまな動作の全部または一部は、NPUなどに埋め込まれた適切にプログラムされた論理によって実装されてもよい。
【０１２４】
このように、本発明の実施形態は、ファームウェア／ソフトウェア・モジュールおよび／または何らかの形の処理コア上で実行されるプログラムとして、あるいはそれらをサポートするよう使われてもよいし、あるいはさもなければ機械可読媒体上または機械可読媒体内に実装もしくは実現されてもよい。機械可読媒体は、機械（たとえばコンピュータ）によって可読な形の情報を保存または送信するための任意の機構を含む。たとえば、機械可読媒体は、読み出し専用メモリ（ROM）、ランダム・アクセス・メモリ（RAM）、磁気ディスク記憶媒体、光記憶媒体およびフラッシュメモリ・デバイスなどといったものを含むことができる。さらに、機械可読媒体は、伝搬される信号を含むことができる。それは、電気的、光学式、音響的またはその他の形の伝搬される信号といったものである（たとえば搬送波、赤外線信号、デジタル信号など）。
【０１２５】
本発明の例示される諸実施形態の上記の記述は、要約において述べられていることを含め、網羅的であることは意図されておらず、開示されている厳密な形に本発明を制限することも意図されていない。本発明の個別的な実施形態や本発明の例がここで例示的な目的のために記述されているが、さまざまな等価な修正が本発明の範囲内で可能である。そのことは当業者は認識するであろう。
【０１２６】
上記の詳細な記述に照らして、本発明に対してこれらの修正をなすことができる。付属の請求項で使われる用語は、明細書および図面で開示されている個別的な実施形態に本発明を限定するものと解釈されるべきではない。むしろ、本発明の範囲は、完全に付属の請求項によって決定されるべきものである。請求項は、請求項の解釈の確立された慣行に従って解釈されるものである。
【０１２７】
〈付録〉
１．SHIFTテーブルの構築のためのアルゴリズムを下記に擬似Cコードで与える。
入力：パターンの配列、テーブルへのハッシングのために使われるかたまり（Chunk）の大きさ（B）、アルファベットの大きさ（A）
出力：SHIFTテーブルへのポインタ
【０１２８】
【表１】
2008544728.tif 000003
【０１２９】
２．HASHテーブルの構築のためのアルゴリズムを下記に擬似Cコードで与える。
入力：パターンの配列、テーブルへのハッシングのために使われるかたまり（Chunk）の大きさ（B）、アルファベットの大きさ（A）
出力：HASHテーブルへのポインタ
【０１３０】
【表２】
2008544728.tif 000004
【０１３１】
３．PREFIXテーブルの構築のためのアルゴリズムを下記に擬似Cコードで与える。
入力：パターンの配列、プレフィックスの大きさ（B′）、アルファベットの大きさ（A）
出力：PREFIXテーブルへのポインタ
【０１３２】
【表３】
2008544728.tif 000005
【０１３３】
４．B+木の構築のためのアルゴリズムを下記に擬似Cコードで与える。
入力：ハッシュ値でソートされたパターンの配列（ハッシュはSHIFTテーブルおよびHASHテーブルについてと同じようにして計算される）、プレフィックスの大きさ（B′）、アルファベットの大きさ（A）、SHIFTテーブル、HASHテーブル
出力：B+木のルートへのポインタ
【０１３４】
【表４】
2008544728.tif 000006
フィールドkey_valueは、すべてのレコード（デフォルトのシフト値をもつものを含む）を加えたら、実際にはhash_record構造リストのインデックスである。したがって、上記のアルゴリズムは、list（木の子ノードのそれぞれについての）がkey_valueの昇順にソートされることを保証する。
【０１３５】
〈Wu-Manberアルゴリズム〉
入力：パケット内容（バイトのストリング）T[0…n−1]、SHIFTテーブル、HASHテーブル、PREFIXテーブル、最短パターンの長さ、パターン数、かたまりの大きさ（B）、プレフィックスの大きさ（B′）、パケット境界をまたぐパターンがあるかどうかチェックする必要があるかどうかを示すフラグ（ポリシー）、前のパケットの末尾でマッチされるパターン・プレフィックスの長さ、前のパケットの末尾でマッチされたプレフィックスをもつパターン・ストリングのアドレス。
出力：検出されたパターンの素性（一つも検出されなければ−1）、ストリングTの先頭からのオフセットとしてのパターンの開始位置。
【０１３６】
このアルゴリズムを下記に擬似Cコードで与える。
【０１３７】
【表５】
2008544728.tif 000007
【０１３８】
【表６】
2008544728.tif 000008
【０１３９】
【表７】
2008544728.tif 000009
【０１４０】
〈B+木を使ったWu-Manberアルゴリズム〉
入力：パケット内容（バイトのストリング）T[0…n−1]、B+木のルートへのポインタ； PREFIXテーブル、最短パターンの長さ、パターン数、かたまりの大きさ（B）、プレフィックスの大きさ（B′）、パケット境界をまたぐパターンがあるかどうかチェックする必要があるかどうかを示すフラグ（ポリシー）、前のパケットの末尾でマッチされるパターン・プレフィックスの長さ、前のパケットの末尾でマッチされたプレフィックスをもつパターン・ストリングのアドレス。
出力：検出されたパターンの素性（一つも検出されなければ−1）、ストリングTの先頭からのオフセットとしてのパターンの開始位置。
【０１４１】
このアルゴリズムは、シフト値とポインタ探索に使われるデータ構造のほかは、前記したWu-Manberアルゴリズムと同一である。一次シフトおよび二次シフトならびにオフセットおよび深さの値は、ここではSHIFTテーブルの代わりに、B+木の、子項目から（hash_record構造から）見つけ出される。所与の位置で生起しうる候補パターンへのポインタも、HASHテーブルではなく、同じB+木の、子ノード項目から得られる。しかし、SHIFTテーブルやHASHテーブルとは違って、これらの値は（一定時間で）直接見つけ出すことはできない。逐次スキャンは効率が悪すぎる。よって、我々は適切なレコードを位置特定するために二分探索を使う。探索ステップを下記に述べる：
１．ハッシュ値を計算するために使われるかたまり（部分ストリング）c1c2…cBを取得する。
２．最上位バイト（c1）を使って適切な子ノード・ポインタおよび子ノード数（root[c1].listおよびroot[c1].num_elements）を位置特定する。
３．整数にマッピングされたかたまりの残りc2…cBを使って、適切なhash_record構造を位置特定する。この整数は任意のマッチする構造のkey_valueになる。すべての構造はkey_valueに基づいて昇順にソートされているので、単純な二分探索が、必要なデータを返す。アルファベットの大きさが256の場合については、レコードを位置特定するのに必要とされる探索は最大8回である。
【０１４２】
このデータ探索を別としてすべてのアルゴリズム・ステップは、上記のWu-Manberアルゴリズムと同一である。
【０１４３】
Bについての実際的な値は2および3である（B＝1とすると、それでも機能はするが、木を構築する目的が無になる）。B′についての実際的な値は4またはそれ未満である。BおよびB′はどちらも最短パターンの長さより小さくなければならない。
【図面の簡単な説明】
【０１４４】
【図１】コンテキスト・パイプラインを使った複数計算エンジンを介して複数機能を処理するための技法を示す概略図である。
【図２】ここに記載される本発明の実施形態の諸側面を実装するためのソフトウェア・ブロック・アーキテクチャを示す概略図である。
【図３】内容検査がパケットに対して実行されるべきかどうかを決定するある実施形態によって実行される動作および論理を示すフローチャートである。
【図４ａ】フロー分類のために用いられるパケットのさまざまな部分を示す図である。
【図４ｂ】分類規則および付随するフローのセットを示す図である。
【図５】一次ハッシュ表および二次ハッシュ表を用いるハッシュ表探索方式のある実施形態を示す図である。
【図６】パターン・データ構造を生成するための前処理動作の間の動作および論理を示すフローチャートである。
【図７】内容検査を含むパケット処理動作を実行する命令スレッドを実行するために使われる複数計算エンジンをもつNPUを含むネットワーク・ライン・カードによって用いられる、データ・フローおよび機能ブロックを示す概略図である。
【図８ａ】フロー中の最初のパケットの内容検査の間に実行される動作および論理を示すフローチャートである。
【図８ｂ】フロー中の最初のパケット以外のパケットの内容検査の間に実行される動作および論理を示すフローチャートである。
【図９】オフセットおよび深さ検索情報を用いる内容検査動作を示すフローチャートである。
【図１０】例示的なAC状態機械データ構造に対応する移行関数、失敗関数、出力関数を示す図である。
【図１１】メモリに記憶されるべきパターン・データ構造のある実施形態を示す図である。
【図１２】AC機械ノードのメモリ・データ構造のある実施形態を示す図である。
【図１３】AC機械インデックスのメモリ・データ構造のある実施形態を示す図である。
【図１４】メモリに記憶されるべきDAWGデータ構造のある実施形態を示す図である。
【図１５】サフィックス木のメモリ・データ構造のある実施形態を示す図である。
【図１６】SHIFTテーブルのメモリ・データ構造のある実施形態を示す図である。
【図１７】HASHテーブルのメモリ・データ構造のある実施形態を示す図である。
【図１８】PREFIXテーブルのメモリ・データ構造のある実施形態を示す図である。
【図１９】ルート・ノードのメモリ・データ構造のある実施形態を示す図である。
【図２０】子ノードのメモリ・データ構造のある実施形態を示す図である。
【図２１】条件‐アクション規則のメモリ・データ構造のある実施形態を示す図である。
【図１】
2008544728.tif 000010
【図２】
2008544728.tif 000011
【図３】
2008544728.tif 000012
【図４ａ】
2008544728.tif 000013
【図４ｂ】
2008544728.tif 000014
【図５】
2008544728.tif 000015
【図６】
2008544728.tif 000016
【図７】
2008544728.tif 000017
【図８ａ】
2008544728.tif 000018
【図８ｂ】
2008544728.tif 000019
【図９】
2008544728.tif 000020
【図１０】
2008544728.tif 000021
【図１１】
2008544728.tif 000022
【図１２】
2008544728.tif 000023
【図１３】
2008544728.tif 000024
【図１４】
2008544728.tif 000025
【図１５】
2008544728.tif 000026
【図１６】
2008544728.tif 000027
【図１７】
2008544728.tif 000028
【図１８】
2008544728.tif 000029
【図１９】
2008544728.tif 000030
【図２０】
2008544728.tif 000031
【図２１】
2008544728.tif 000032
【国際調査報告】
2008544728.tif 000033
2008544728.tif 000034
2008544728.tif 000035