説明

最適フィルタマッチング及びトランスポートレベル共有を用いた2ステージパケット分類のための方法及び装置

2ステージパケット分類のための方法及び装置であり、その2ステージパケット分類スキームは、第1ステージ及び第2ステージを有する。第1分類ステージでは、1つのパケットがパケットのネットワークパスに基づいて分類される。第2分類ステージでは、パケットは、パケットの1以上のトランスポート(又は他の)フィールドに基づいて分類される。最適フィルタマッチング及びトランスポートレベル共有の実施形態も開示され、これらの技術の1つ又は両方が2ステージ分類方法に実装される。


【発明の詳細な説明】
【技術分野】
【0001】
本発明は、広くコンピュータネットワーキングに関し、特に、パケットを分類する方法及び装置に関する。
【背景技術】
【0002】
従来、コンピュータネットワークにおけるパケットルーティングは、パケットの宛先アドレスだけに基づいている。このルーティング技術は、一般的に"ベストエフォート"配送であり、同一アドレスに向かう全てのトラフィックは同様に扱われる。しかしながら、宛先アドレスだけに基づいたパケットルーティングは、より広い帯域幅、高められたセキュリティ、並びに増大する柔軟性及びサービス差別化に対する増大する要求に応えるには不十分である。これらの目的に応えることを目的として、機器ベンダ及びサービスプロバイダは、ファイアウォールを通過するルーティング、サービス品質(QoS)ベース転送、及び帯域及び/又はリソース予約を含む、より差別化したルーティング形式を提供している。
【0003】
一般的に、ファイアウォールは、トラフィックの特定のクラス(例えば、"望ましくない"又は"疑わしい"トラフィック)をブロックすることができる、いくつかのコンポーネント、又は複数のコンポーネントの組み合わせを有する。ファイアウォールは、組織ネットワーク及び他の企業ネットワークでしばしば利用され、ファイアウォールは通常、ネットワークの入口及び/又は出口ポイント、すなわち"信頼境界"において実装される。典型的なファイアウォールは、望ましいセキュリティポリシーを実行すべく設計された一連のルール又はフィルタを有する。
【0004】
ネットワークサービスプロバイダは、それぞれが異なるサービス、サービスプライオリティ、及び価格を必要とする多様な顧客を持つ。異なる顧客に差別化されたサービスを提供することを目的として、すなわち、より一般的には、ネットワークトラフィックの特定のクラスへの望ましい処理を提供することを目的として、機器ベンダは、QoSベースフォワーディング及び帯域/リソース予約を含む多様なメカニズムを実装してきている。QoSベースフォワーディングの目標は、異なる顧客及び/又はトラフィックタイプに対するサービス差別化を提供することである。QoSベースフォワーディングは、例えば、サービスクラスに基づくフォワーディング、特別なキューイングプロシージャ(例えば、プレフローキューイング)、及びフェアスケジューリングメソッドを含んでよい。帯域幅又はリソース予約は、QoSフォワーディングに密接に関係している。帯域予約は、特定のタイプのトラフィックに対する指定されたバンド幅の予約を含む。例えば、帯域予約は2点間のトラフィックに適用されてよいし、帯域予約は特定のアプリケーション(例えば、マルチメディア、ビデオ等)に関連するトラフィックに適用されてよい。
【0005】
他のポリシーベースのパケットフォワーディング技術を実行するだけでなく、ネットワークトラフィックのより差別化されたルーティングを提供する上記のルーティング手法(例えば、ファイアウォール、QoSフォワーディング、帯域予約)を実装することを目的として、パケットを分類する必要がある。全般的に、パケット分類は、異なるフローに属するパケットの間、又は異なるトラフィックタイプに関するパケットの間で弁別する段階を持つ。ここで用いられたように、"フロー"は、少なくともいくつかの共通するヘッダ特性(例えば、2つの特定のアドレスの間を流れる複数のパケット)を共有する一連のパケットである。パケットは、通常、パケットのヘッダ内の1以上のフィールドに基づいて分類される。そのパケットがいずれのフローに一致するか、又はそのパケットがいずれのトラフィックタイプに関するかを特定すべく、1以上のルールがヘッダ情報に適用される。
【0006】
パケット分類ルールは、多くは、関連するプライオリティ及びアクションだけでなく受信したパケットのヘッダ内の多くの対応する複数のフィールドに対して比較される、いくつかのフィールドを含む。分類データベースを形成する複数のルールのセットは優先順位づけされたリストで編成されてよく、より高いプライオリティを持つルールがより低いプライオリティを持つルールより優先される。パケットが受信されたとき、当該パケットに適用されるべき最もプライオリティの高いアクションを決定すべく、当該パケットの複数の内容(例えば、特定の複数のヘッダフィールド)が分類データベースの中の各ルールと比較される。
【0007】
ハッシュ方式、ビットパラレズム技術、及び内容参照可能メモリ(CAM)を用いた実装を含む、ヘッダデータに基づいてパケット分類を実行するための多くの方法−ハードウェア及びソフトウェア実装の両方−は、当業者に知られている。ハッシュ法は、ルールのそれぞれのフィールドにおいて用いられるビットマスクに応じたルールのグループを生成し、ルールのグループのそれぞれは1つのハッシュテーブル(又は複数のハッシュテーブル)によって表現される。受信されたパケットとマッチしている1つのルールを特定することは、ハッシュテーブル上の一連のルックアップを要する。
【0008】
ビットパラレリズムは、n次元分類問題を、それぞれ1次元の複数のステージに分割する。それぞれは、ビットベクトルは、システムに記憶されたルールの数に等しい長さを持ち、ビットベクトルにおける1つのビットは、当該ビットに対応するルールが受信されたパケットの適切なフィールドとマッチする値の範囲を示す場合にセットされる。全ての戻されたビットベクトルにおいてセットされたそれらのビットを持つルールは受信されたパケットとマッチする。標準的なビットパラレリズムスキームにおける改良は、集合ビットベクトル(ABV)法である。ABV法において、それぞれの"フル"ビットベクトルは圧縮されて、より小サイズのビットセット("集合ビットベクトル"と呼ぶ)として表される。集合ビットベクトルにおけるそれぞれのビットは、フルビットベクトルからのビットのグループを表し、集合ビットベクトルにおける1つのビットは、(フルビットベクトルにおける)関連するビットのグループの中の少なくとも1つのビットがセットされた場合にセットされる。
【0009】
CAM実装においては、CAMエントリのそれぞれは、1つの値及び1つのビットマスクに関連する。当該値は1つのルールの1以上のフィールドを含み、当該ビットマスクは、サーチキーのビットのいずれが、そのキーが当該値に対して比較されるときに考慮されるかを指定する。CAMユニット−サーチキーを複数のエントリに対して同時に比較する能力を有してよい−は、最も高いプライオリティでマッチしているエントリに関連する1つのインデックスを戻し、このインデックスはパケットに対するアクションを特定するために使用される。
【0010】
ファクタの数は、要求される多数のメモリアクセス、大きい記憶容量要件、及び(少なくともCAM実装について)著しい電力消費を含む、上記の分類スキームのパフォーマンスにインパクトを与える。他のファクタだけでなく帯域幅及びメモリオーバヘッドによって、これらのパケット分類技術は、分類データベースサイズの増大だけでなくリンク速度の進歩に追随すべく取り組み、パケット分類は高速リンク(例えば、ギガビット容量)をサポートしているルータにおけるボトルネックになり得る。
【図面の簡単な説明】
【0011】
【図1】1つのルータを備えるネットワークの一実施形態を示す概略図である。
【0012】
【図2】図1に示されたルータの一実施形態を示す概略図である。
【0013】
【図3】図2に示されたプロセッシングデバイスの一実施形態を示す概略図である。
【0014】
【図4】1つの典型的なパケットの構成を示す概略図である。
【0015】
【図5A】パケット分類ルールの一実施形態を示す概略図である。
【図5B】パケット分類ルールの一実施形態を示す概略図である。
【図5C】パケット分類ルールの一実施形態を示す概略図である。
【0016】
【図6】2ステージパケット分類部の一実施形態を示す概略図である。
【0017】
【図7】2ステージパケット分類のための方法の一実施形態を示すブロック図である。
【0018】
【図8】分類データベースの具体例の一部を示す概略図である。
【0019】
【図9】2ステージパケット分類のための方法の他の一実施形態を示すブロック図である。
【0020】
【図10】複数のルールを持つ分類データベースの一実施形態を示す概略図である。
【0021】
【図11A】複数のルールセットへの分類データベースの構成の一実施形態を示す概略図である。
【図11B】複数のルールセットへの分類データベースの構成の一実施形態を示す概略図である。
【0022】
【図12A】2つの部分的に重なるフィルタの一実施形態を示す概略図である。
【図12B】2つの部分的に重なるフィルタの一実施形態を示す概略図である。
【図12C】2つの部分的に重なるフィルタの一実施形態を示す概略図である。
【0023】
【図13A】2つの完全に重なるフィルタの一実施形態を示す概略図である。
【図13B】2つの完全に重なるフィルタの一実施形態を示す概略図である。
【図13C】2つの完全に重なるフィルタの一実施形態を示す概略図である。
【0024】
【図14】送信元及び宛先アドレス空間内の2つのパラレルなルックアップの一実施形態を示す概略図である。
【0025】
【図15】分類データベースのフィルタからの非存在フィルタの構成を示す概略図である。
【0026】
【図16A】第1分類ステージデータ構造の一実施形態を示す概略図である。
【0027】
【図16B】パラレル最長プレフィックスマッチルックアップテーブルの一実施形態を示す概略図である。
【0028】
【図16C】図16Aのプライマリルックアップテーブルの一実施形態を示す概略図である。
【0029】
【図17】第2分類ステージデータ構造の一実施形態を示す概略図である。
【0030】
【図18】最適フィルタママッチング及びトランスポートレベル共有を使用した2ステージパケット分類のための方法の一実施形態を示すブロック図である。
【0031】
【図19】ワイドフィルタを含むフィルタデータベースの一実施形態を示す概略図である。
【0032】
【図20A】第1分類ステージデータ構造の他の一実施形態を示す概略図である。
【0033】
【図20B】パラレル最長プレフィックスマッチルックアップテーブルの他の一実施形態を示す概略図である。
【0034】
【図20C】最適フィルタママッチング及びトランスポートレベル共有を使用した2ステージパケット分類に係る方法の一実施形態を示すブロック図である。
【0035】
【図21】2ステージパケット分類データ構造を生成及び更新する方法の一実施形態を示すブロック図である。
【発明を実施するための最良の形態】
【0036】
パケット分類部の複数の実施形態がここに開示される。開示されたパケット分類部の複数の実施形態は、パケット転送部(例えば、ファイアウォール、QoSベースのフォワーダ)を実装しているルータに関連して以下に記載される。一方で、開示された複数の実施形態は用途において制限されず、さらには、続く本文及び図面で記載されるパケット分類部の実施形態は一般的に、パケットの分類又は他の通信が必要とされるデバイス、システム、及び/又は環境のいずれにも適用可能であるということが理解されるべきである。
【0037】
ネットワーク100の一実施形態を図1に示す。ネットワーク100は、パケット転送部201を有するルータ200を備える。ルータ200(及びパケット転送部201)は、他の望ましいセキュリティベースのフォワーディングスキームだけでなく、特定のセキュリティポリシー、QoSフォワーディング、及び/又はリソース予約を実装してよい。ルータ200は、異なるフローに属するパケット及び/又は異なるトラフィックタイプに関連するパケットを区別すべく、望ましいフォワーディングポリシーを実装すべく設計されたルールセットを持つ1つのパケット分類部600も有してよい。パケット分類部600の実施形態は以下により詳細に説明される。(パケット転送部201及びパケット分類部600だけでなく)ルータ200は、適切な任意のコンピューティングシステム或いはデバイス(又はデバイスの組み合わせ)上に実装されてよい。ルータ200の一実施形態は、図2及び添付の本文に関連して以下に説明される。ルータ200は、明確さ及び理解し易さを目的として図1から省略された他のコンポーネント(例えば、スケジューラ、トラフィックマネージャ等)を有してよいことが理解されるべきである。
【0038】
ルータ200は、複数のリンク130−リンク130a、130b、・・・130n−を介して、多くのノード110及び/又は多くのサブネット120と結合されている。ノード110は任意のアドレス可能なデバイスを有する。例えば、ノード110は、サーバ、デスクトップコンピュータ、ラップトップコンピュータ、又はハンドヘルドコンピューティングデバイス(例えば、情報携帯端末、すなわちPDA)のような、コンピュータシステム又は他のコンピューティングデバイスを有してよい。サブネット120は、他のノードの集合を有してよく、サブネット120は、他のルータ又はスイッチも有してよい。リンク130a−nのそれぞれは、任意の適切なプロトコル−例えばTCP/IP(トランスミッション・コントロール・プロトコル/インターネットプロトコル)、HTTP(ハイパーテクスト転送プロトコル)、その他−を通じた情報交換をサポートしている任意の適切な媒体−例えば、無線、銅線、光ファイバ、又はそれらの組み合わせ−を通じて確立される。
【0039】
ネットワーク100は、ローカルエリアネットワーク(LAN)、大都市圏ネットワーク(MAN)、広域ネットワーク(WAN)のような任意のタイプのネットワークを有してよい。ルータ200は、例えばインターネット及び/又は他のLAN、MAN、LAN、又はWLANを介して、ネットワーク100を他のネットワーク(又は複数のネットワーク)5に結合してもよい。ルータ200は、任意の適切なプロトコル(例えば、TCP/IP、HTTP等)を用いた、無線、銅線、及び/又は光ファイバ接続を含む任意の適切な媒体を介して他のネットワーク5に接続されてよい。
【0040】
図1に示されたネットワーク100は、そのようなシステムの実施形態の一例を示すことが目的とされており、さらには、ネットワーク100は任意の適切な構成を有してよいことが理解されるべきである。例えば、ネットワーク100は、理解し易さのために図1から省略された追加のノード110、サブネット120、及び/又は他のデバイス(例えば、スイッチ、ルータ、ハブ等)を備えてよい。さらに、ネットワーク100は、図1に示されたコンポーネントの全てを含まなくてよいことが理解されるべきである。
【0041】
他の実施形態では、ルータ200は、パケット分類部600が(ハードウェア、ソフトウェア、或いはハードウェア及びソフトウェアの組み合わせで)実装され得る任意の適切なコンピューティングデバイスを有してよい。そのようなコンピューティングシステムの一実施形態が図2に示される。
【0042】
図2を参照すると、ルータ200は、様々なコンポーネントが結合されたバス205を有する。バス205は、ルータ200のコンポーネントを相互に接続する1以上のバス−例えば、システムバス、ペリフェラルコンポーネントインタフェース(PCI)バス、スカジー(SCSI)バス等−の集合を示すことが意図されている。これらのバスを1つのバス205として表すことは理解し易くすることを目的として提供されており、ルータ200はそのように限定されないことが理解されるべきである。当業者は、ルータ200が任意の適切なバスアーキテクチャを有し、任意の数及び組み合わせのバスを有してよいことを理解し得る。
【0043】
プロセッシングデバイス(又は複数のデバイス)300がバス205に結合されている。プロセッシングデバイス300は、マイクロプロセッサ、ネットワークプロセッサ、特定用途向け集積回路(ASIC)、フィールド・プログラマブル・ゲートアレイ(FPGA)、又は類似のデバイスを含む任意の適切なプロセッシングデバイス又はシステムを含んでよい。プロセッシングデバイス300の一実施形態は、図3及び付随する本文で以下に説明される。図2は1つのプロセッシングデバイス300を示すが、ルータ200は2以上のプロセッシングデバイスを含み得ることが理解されるべきである。
【0044】
ルータ200は、バス205に結合されたシステムメモリ210も含んでよい。システムメモリ210は、例えば、スタティックランダムアクセスメモリ(SRAM)、ダイナミックランダムアクセスメモリ(DRAM)、シンクロナスDRAM(SDRAM)、又はダブルデータレートDRAM(DDRDRAM)のような任意の適切なタイプ及び数のランダムアクセスメモリを含む。ルータ200が動作している間、他のプログラム218だけでなくオペレーティングシステム(又は複数のオペレーティングシステムのセット)214、パケット分類部600はシステムメモリ210に常駐してよい。図2の実施形態においては、以下に説明されるが、パケット分類部の一部−すなわち、パケット分類部の第1ステージ600a(STAGE1 PCKT CLSSFR)−は、システムメモリ210に常駐し得る複数のソフトウェアルーチンを含むが、パケット分類部の他の部分−すなわち、パケット分類部の第2ステージ600b(STAGE 2 PCKT CLSSFR)−はハードウェアで実装される。一方で、図2の実施形態は開示されたパケット分類部の単なる1つの実装を表し、さらに、開示されたパケット分類部は任意の他の適切なソフトウェア及び/又はハードウェア構成で実装されてよいことが理解されるべきである。例えば、他の実施形態では、第2分類ステージ600bもソフトウェアで実装されてよく、その場合、第2ステージ600bはシステムメモリ210に常駐する(及び場合によっては記憶装置230に記憶される)ソフトウェアルーチンのセットを含んでよい。
【0045】
ルータ200はさらに、バス205に結合された読み出し専用メモリ(ROM)220を有してよい。動作している間、ROM220は、プロセッシングデバイス300のための一時的な命令及び変数を記憶してよい。ルータ200はバス205に結合された記憶装置(又は複数の記憶装置)230を有してもよい。記憶装置230は、例えばハードディスクドライブのような任意の適切な不揮発性メモリを含んでよい。オペレーティングシステム214及び他のプログラム218(例えば、パケット転送部201のソフトウェア実装)だけでなくパケット分類部600(例えば、パケット分類部600の第1ステージ600a)も記憶装置230に記憶されてよい。さらに、取り外し可能な記憶メディアにアクセスするためのデバイス240(例えば、フレキシブルディスクドライブ又はCD−ROMドライブ)がバス205に結合されてよい。
【0046】
ルータ200は、バス205に結合された1以上の入力デバイス250を有してよい。共通の入力デバイス250は、他のデータ入力デバイスだけでなく、マウスのようなポインティングデバイス、キーボードを含む。1以上の出力デバイス260がバス205に結合されてよい。共通の出力デバイス260は、ビデオディスプレイ、プリンティングデバイス、オーディオ出力デバイス、及びステータスインジケータ(例えばLED)を含む。
【0047】
ルータ200は、バス205に結合されたネットワーク/リンクインタフェース270をさらに有してよい。ネットワーク/リンクインタフェース270は、ルータ200を他のネットワーク(又は複数のネットワーク)5と結合することができ、さらにルータ200をリンク130a−nのそれぞれと結合することができる、任意の適切なハードウェア、ソフトウェア、或いはハードウェア及びソフトウェアの組み合わせを含む。
【0048】
図2に示されたルータ200は、そのようなデバイスの実施形態の一例を表すことを目的としており、さらに、このシステムが明快さ及び理解し易さのために省略された多くの追加のコンポーネントを含んでよいことが理解されるべきである。例として、ルータ200は、信号線及びバスだけでなく、DMA(ダイレクトメモリアクセス)コントローラ、プロセッシングデバイス300に関するチップセット、追加のメモリ(例えばキャッシュメモリ)を有してよい。また、ルータ200は、図2に示されたコンポーネントの全ては有しなくてよいことが理解されるべきである。
【0049】
一実施形態では、パケット分類部600又はパケット分類部の一部は、コンピューティングデバイス−例えば図2のルータ200又は他の適切なコンピューティングデバイス−上で実行される命令のセット(すなわち、ソフトウェアアプリケーション)を含んでよい。命令のセットは、記憶装置230(又は他の適切なプログラムメモリ)内にローカルに記憶されてよい。他にも、当該命令はリモートの記憶装置(図示せず)に記憶され、ネットワーク100(又は他のネットワーク5)を介してアクセスされてよい。動作している間、命令のセットはプロセッシングデバイス300上で実行されてよく、その命令(又はそれらの一部)はシステムメモリ210に常駐してよい。
【0050】
他の実施形態では、パケット分類部600(又はパケット分類部の一部)は、例えば磁気メディア(例えばフレキシブルディスク又は磁気テープ)、光アクセス可能ディスク(例えばCD−ROMディスク)、フラッシュメモリデバイス等のような機械アクセス可能メディアに記憶された命令のセットを含んでよい。パケット分類部600を実行し続けることを目的として、例えば、図2のルータ200、取り外し可能な記憶メディアにアクセスするデバイス240は、機械アクセス可能メディア上の命令にアクセスしてよく、それから当該命令はプロセッシングデバイス300で実行されてよい。本実施形態では、命令(又はそれらの一部)は、システムメモリ210に再びダウンロードされてよい。
【0051】
さらなる実施形態では、パケット分類部600又はパケット分類部の一部はハードウェアで実装されてよい。例えば、パケット分類部600(又はそれらの一部)は内容参照可能メモリ(CAM)を用いて実装されてよい。また、さらなる実施形態では、パケット分類部600はソフトウェア及びハードウェアの組み合わせを用いて実装されてよい。
【0052】
以下に詳細に説明される特別な一実施形態では、パケット分類部600は2ステージパケット分類システムを持ち、この2ステージ分類スキームはハードウェア及びソフトウェアの両方で実装される。2ステージパケット分類部は、第1ステージ600a及び第2ステージ600bを持つ(図2を参照)。一実施形態では、第1ステージ600aはソフトウェアで実装され、第2ステージ600bはハードウェアで実装される。
【0053】
前述したように、プロセッシングデバイス300の一実施形態は図3及び付随する本文に示される。一方で、図3に示されたプロセッシングデバイス300は、パケット分類部600の開示された実施形態が実装され得るプロセッシングデバイスの単なる一実施形態であることを理解すべきである。当業者は、パケット分類部600の開示された実施形態が多くの他のタイプのプロセッシングシステム及び/又はプロセッサアーキテクチャで実装され得ることを理解するだろう。
【0054】
図3に転じると、プロセッシングデバイス300は、種々の機能ユニットが結合されるローカルバス306を持つ。バス305は、プロセッシングデバイス300の種々の機能ユニットを相互に接続する1以上のオンチップバスの集合を表すことを目的とする。1つのバス305としてのこれらローカルバスの表現は理解し易さのために提供されており、プロセッシングデバイス300がそのように限定されないことを理解すべきである。当業者は、プロセッシングデバイス300が任意の適切なバスアーキテクチャを有してよく、任意の数及び任意の組み合わせのバスを有してよいことを理解するだろう。
【0055】
1つのコア310及び複数のプロセッシングエンジン320(例えば、プロセッシングエンジン320a、320b、・・・、320k)がローカルバス305に結合される。一実施形態では、コア310は、オペレーティングシステム214を実行し得る汎用プロセッシングシステムを持ってよい。コア310は、プロセッシングデバイス300のオペレーションを制御し、実行のためにプロセッシングエンジン320への命令の供給のような種々の管理機能を実行してよい。プロセッシングエンジン320a−kは、任意の適切なプロセッシングシステムを持ち、それぞれが1つの整数演算ユニット(ALU)、1つのコントローラ、及び(リード/ライトオペレーションの間にデータを記憶するための)複数のレジスタを持ってよい。また、一実施形態では、それぞれのプロセッシングエンジン320a−kは、複数(例えば4個)の実行スレッドを提供する。
【0056】
また、オンチップメモリサブシステム330がローカルバス305に結合される。1つのユニットとして示されているが、オンチップメモリサブシステム330は、多くの別個のメモリユニット及び/又はメモリタイプを持ってよい−実際には持つことが見込まれる−。例えば、そのようなオンチップメモリは、SDRAM、SRAM、及び/又はフラッシュメモリ(例えば、FlashROM)を持つ。オンチップメモリに加えて、プロセッシングデバイス300はオフチップメモリ(例えば、ROM220、オフチップキャッシュメモリ等)と結合されてよいことが理解されるべきである。
【0057】
プロセッシングデバイス300は、ローカルバス305と結合されたバスインタフェース340をさらに持つ。バスインタフェース340は、バス205を含む、ルータ200の他のコンポーネントとのインタフェースを提供する。簡単のために、バスインタフェース340は1つの機能ユニットとして示されている。しかしながら実際には、プロセッシングデバイス300が複数のバスインタフェースを持ってよいことが理解されるべきである。例えば、プロセッシングデバイス300は、他のインタフェースだけでなくPCIバスインタフェース、IX(インターネット・エクスチェンジ)バスインタフェースを持ってよく、バスインタフェース340は1以上のそのようなインタフェースの集合を表すことが意図されている。
【0058】
図3に関連して図示され説明されたプロセッシングデバイス300の実施形態は、パケット分類部の開示された実施形態とともに用いられることが考えられるプロセッシングデバイスの単なる一例に過ぎず、さらに、プロセッシングデバイス300は、図3に示されたコンポーネントに加えて、明確さ及び理解し易さのために省略された他のコンポーネントを持ってよいことが理解されるべきである。例えば、プロセッシングデバイス300は他の機能ユニット(例えば、命令デコーダユニット、アドレス変換ユニット等)、熱管理システム、クロック回路、追加のメモリ、及びレジスタを持ってよい。また、プロセッシングデバイスは、図3に示された要素の全ては持たなくてよいことが理解されるべきである。
【0059】
図4を参照すると、ルータ200で(例えば他のネットワーク5から)受信され得るパケット400の一例が示される。パケット400は、ヘッダ410及びペイロード(又はデータ)450を有する。ヘッダ410は、任意の適切なフォーマットを有してよく、図4に示されたパケット400はTCP/IPプロトコルに関するヘッダの一例を示す。例えば、インターネット・エンジニアリング・タスクフォース標準勧告文章(IETF RFC)791、インターネットプロトコル(1981)、及びIETF RFC 793、トランスミッションコントロールプロトコル(1981)を参照すること。図4では、ヘッダ410は、フィールド420a、420b、・・・、420xを含む複数のフィールドを有する。概して、フィールド420a−xは、パケット400についての特定情報を含む。例として、ヘッダ410は、プロトコル420i(例えばTCP)、発信元アドレス420k、宛先アドレス420j、発信元ポート番号420m、及び宛先ポート番号420nを含む。発信元及び宛先アドレス420k、420iのそれぞれは32ビットを持ち、発信元ポート番号及び宛先ポート番号420m、420nのそれぞれは8ビットを持つ。これらはパケットのヘッダ内に含まれ得る情報のタイプの単なる少数の例であり、さらに、パケットヘッダ410は特定のハードウェア及び/又はアプリケーションで近い将来に必要とされる任意の情報を含み得ることが、当業者によって理解されるだろう。また、パケットのフォーマットは、図4に関連して示され説明されたフォーマットに限定されないことが理解されるべきである(例えば、ヘッダフィールドの幅が変更可能であり、フィールドのタイプ及び数が変更可能、等)。
【0060】
通信はここでは一般的に"パケット"として呼ばれる。しかしながら、開示された実施形態は、任意のタイプの通信(例えば、パケット、セル、フレーム等)に、フォーマット又は内容に関係なく適用可能であることが理解されるべきである。
【0061】
図5Aに転じると、パケット分類ルール500の一実施形態が示される。概して、ルール500は、基準を満たしているパケットが属する特定のフローを表す基準のセットを規定する。ルール500は、フィールド510a(FIELD 1)、510b(FIELD 2)、・・・、510n(FIELD N)を含むいくつかのフィールドを有する。1つのルールは任意の適切な数のフィールド510a−nを有してよく、1つのルール内のフィールドの数はここでは次元と呼ばれる(すなわち、ルール500はN次元を有する)。一実施形態では、フィールド510a−nのそれぞれは、発信元又は宛先アドレスのような、1つのパケットのヘッダにおける1つのフィールドに対応する。しかしながら、他の実施形態では、ルールのコンポーネント510a−nは、アプリケーションヘッダフィールド、リンク識別情報、時刻等のような、他の情報を含んでよい。概して、それぞれのフィールド510a−nについて、パケット内の対応するフィールドがルールのそのフィールドとマッチ場合に、パケットはルール500と"マッチ"する(典型的には分類ルール内の1つのフィールドは値の範囲として表され、1つの値は、当該値がそのフィールドに対応する範囲に含まれる場合に、ルール内のフィールドとマッチする)。ルール500は、そのルールとマッチするいずれのパケットにも適用されるべき対応づけられたアクション520(例えば、アクセプト、ブロック等)をさらに含む。ルール500は、プライオリティ530にも対応づけられている。
【0062】
図5Bを参照すると、パケット分類ルール501の他の実施形態が示される。ルール501は、いくつかのトランスポートレベルフィールド510cだけでなく、発信元アドレスフィールド510a及び宛先アドレスフィールド510bを有する。トランスポートレベルフィールド510cは、例えば、プロトコル515a、送信元ポート番号515b、及び宛先ポート番号515cを含む。トランスポートレベルフィールド510cは前述のフィールドに限られず、トランスポートレベルフィールド510cは他のフィールド515d−kを含んでよい(又はより少ないフィールドを含んでよい)。他の考えられるトランスポートレベルフィールドは、他のフィールドだけでなく、例えばTCP SYNフラグ及びRSVPヘッダフィールド(例えば、IETF RFC 2205、リソース・リザベーション・プロトコル(RSVP)−機能仕様書バージョン1(1997)を参照すること)のような複数のプロトコルフィールドを含む。ルール501は、関連するアクション520及びプライオリティ530も含む。
【0063】
図5Cは、図5Bに示されたルールの一例を示す。図5Cのルール502は、"128.128.*"である発信元IP(インターネットプロトコル)アドレス510a、"128.67.120.84"である宛先IPアドレス510b、"TCP"であるプロトコル510c、"80"である発信元ポート番号510d、"*"である宛先ポート番号510eを指定する。ここで、文字"*"はワイルドカードを示す(すなわち、任意の値がワイルドカードにマッチし得る)。アクション540は"ブロック"(すなわち、当該ルールを満たす任意のパケットが許可されない)であり、ルール502は"2"を示すプライオリティ540を含む。勿論、図5Cがルールの単なる一例を表し、さらに、ルールは任意の適切な数及びタイプのヘッダフィールドを含んでよい(すなわち、ルールは任意の次元を持ってよい)ことが理解されるべきである。
【0064】
1つのルールのフィールドのそれぞれは、完全一致(例えば"80"に一致する発信元ポート番号)、プレフィックス(例えば"128.128.*"の発信元アドレス)、範囲指定(例えば、発信元ポート番号"−1023")として表現されてよい。一方で、いくつかの範囲(例えば、">1023"である発信元ポート番号)は、プレフィックスによって表することができず、そのような表現はプレフィックスのセットに分解されてよい。例えば、">1023"の範囲は、以下の一連の(バイナリ形式での)プレフィックス、すなわち、"000001**********"、"00001***********"、"0001************"、"001*************"、"01**************"、及び"1***************"で表され得る。このように、フィールド">1023"を持つルールは、6つの異なるルールに展開され、6つの別個のプレフィックスのそれぞれが範囲指定">1023"を形成する。Kビットの範囲は一般的に最大(2K−2)個のプレフィックスに分解されることに注意すべきである。
【0065】
図6には、パケット分類部600の一実施形態が示されている。パケット分類部600は、分類プロセスを2ステージに分割する。パケット分類部600は、第1ステージ600a(STAGE 1)及び第2ステージ600b(STAGE 2)を含む。第1ステージ600aにおいて、パケットはそのネットワークパスに基づいて分類され、第1ステージ600aにおいて、パケットは1以上の他のフィールド(例えば、トランスポートレベルフィールド)に基づいて分類される。ロジック610及びデータ構造1600は第1ステージ600aに関連し、ロジック620及びデータ構造1700は第2ステージ600bに関連する。
【0066】
第1ステージロジック610は、受信したパケットをそのパケットのネットワークパスに基づいて分類することができる、任意の適切なソフトウェア、ハードウェア、或いはフトウェア及びハードウェアの組み合せを持つ。一実施形態では、第1ステージロジック610は、受信したパケットの送信元及び宛先アドレスに基づいて1つの結果を決定し、この結果は分類部の第2ステージ600bに供給される。パケットのネットワークパスに基づいてパケットを分類する方法の様々な実施形態が以下に記載される。複数のネットワークパスは、通常、送信元及び宛先アドレス(例えば、送信元IPアドレス及び宛先IPアドレス)によって表される。しかしながら、1つのネットワークパスの表現は、送信元−宛先アドレスのペアに限定されず、さらに、マルチプロトコルラベルスイッチング(MPLS)ラベル(例えばIETF RFC 3031 Multiprotocol Label Switching Architecture (2001)を参照すること)、1つの送信元IPアドレスと1つの宛先アドレスマルチキャストグループとの組み合わせ等のような、別の代替の基準が1つのネットワークパスを特定すべく用いられ得ることが理解されるべきである。第1ステージデータ構造1600は、以下においてもより詳細に説明されるが、他のメモリタイプだけでなくSRAM、DRAM、SDRAM、DDRDRAMを含む任意の適切なメモリ内に記憶されてよい。
【0067】
第2ステージロジック620は、受信されたパケットのヘッダに含まれる複数のトランスポートレベルフィールド(又は他のフィールド)に基づいて、受信されたパケットを分類することができる、任意の適切なソフトウェア、ハードウェア、或いはフトウェア及びハードウェアの組み合せを持つ。一実施形態では、第2ステージロジック620は、分類の第1ステージからの結果を受信して、この結果及び受信したパケットの他の複数のフィールド(例えば、複数のトランスポートレベルフィールド)に基づいて、パケットに適用されるべき又は実行されるべきアクションを決定する。パケットのヘッダに含まれる1以上のトランスポートレベルフィールド(又は他の複数のフィールド)に基づいてパケットを分類する方法の多様な実施形態が以下に記載される。第2ステージデータ構造1700は、他のメモリタイプだけでなくCAM、SRAM、DRAM、SDRAMのような任意の適切なタイプのメモリ内に記憶されてよい。第2ステージデータ構造1700は、以下により詳細に説明される。
【0068】
1つの特有な実施形態では、上記で触れられたように、パケット分類部600はソフトウェア及びハードウェアの組み合わせに実装される。より具体的には、第1分類ステージ600aはソフトウェアに実装され、第2分類ステージ600bはハードウェアに実装される。本実施形態では、第1分類ステージ600aは、メモリ(例えば、図2に示されたシステムメモリ210及び/又は図3に示されたオンチップメモリサブシステム330)に記憶されて、プロセッシングデバイス(例えば、図3のプロセッシングデバイス300)上で実行される命令のセットを持ち、一方で第2ステージ600bはCAM(又は他のハードウェア構成)を用いて実装され得る。
【0069】
後述の2ステージ分類スキームは、図6の2ステージパケット分類部600に実装されるように、2ステージパケット分類のための方法700の一実施形態を示す図7にさらに図示される。図7のブロック710を参照すると、パケットが受信され、そして、ブロック720に記載のように、パケットは、パケットのネットワークパスに基づいて最初に分類される。一般的に、パケットのネットワークパスは、パケットのヘッダに含まれる送信元及び宛先アドレスで表される。その後、パケットは、受信されたパケットのヘッダに含まれる1以上の他のフィールドに基づいて分類され、それはブロック730に示される。2ステージ分類(ブロック720、730を参照)の結果に基づいてプライオリティの最も高いアクションが特定されて、ブロック740に示されるようにこのアクションがパケットに適用される。
【0070】
通常、インターネットには、多くの他の巨大ネットワークと同様に、ネットワークにわたる多くの考え得るルートが存在するが、比較的少数のアプリケーションしか存在しない。したがって、別個のネットワークパスの数は、一般的にアプリケーションの数よりはるかに大きいということになる。これらの考えは、分類ルールのセットにある送信元−宛先アドレスのペアの数が一般的に他のフィールド(例えば、ポート番号及びプロトコルのようなトランスポートレベルフィールド)の数よりはるかに大きいことを示唆する、実際の分類データベースの分析によって実証される。これらの分析は、多くの異なる送信元−宛先アドレスのペアがトランスポートレベルフィールド(又は他のフィールド)の同じセットを使用しているということ、さらに、セットのそれぞれのメンバーに関連する相対的プライオリティ及びアクションが、セットのそれぞれの出現において概して同じであるということも示唆する。その上、それぞれのセット内のエントリの数は一般的に小さい。
【0071】
分類データベース内の送信元−宛先アドレスのペアがルーチン的にトランスポートレベルフィールドの同じセットを使用しているという事実が、図8に示される。本図を参照すると、分類データベース800の一例が示されている。この分類データベース800は、いくつかの分類ルールを持ち、それぞれのルールは、関連する1つのアクション820及び1つの絶対的プライオリティ830aだけでなく、1つの送信元IPアドレス810a、1つの宛先IPアドレス810b、1つのプロトコル810c、1つの送信元ポート番号810d、及び1つの宛先ポート番号810eを含む。ルールの2つのグループ801、802が図8に示され、第1グループのルールのそれぞれは、送信元及び宛先IPアドレス810a−bによって表されるように同じネットワークパスを持ち、第2グループのルールのそれぞれは同じネットワークパスを持つ(しかし、第1グループのネットワークパスとは異なる)。ルールのセット(801又は802)内のそれぞれのルールの相対的なプライオリティ830bも、図8に示されている。2つのルールグループ801、802はそれぞれ異なる送信元−宛先アドレスのペアを持つが、これらのルールグループは同じトランスポートレベルフィールド、相対的プライオリティレベル(すなわち、ルールグループ801用のプロトコル、ポート番号指定、アクション、及びプライオリティは、グループ802用に反復される)の同じセットを共有する(1以上の)トランスポートレベルフィールド、1つのアクション、及び1つの相対的プライオリティのセットの組み合わせは、ここでは"トリプレット"として呼ばれる。
【0072】
図6に戻ると、パケット分類の第1ステージ600aにおいて、この分類ステージを著しく簡略化する第1ステージにおける分類が送信元及び宛先アドレスに基いて実行され得るので、N次元分類問題は2次元問題に変えられる。第2ステージ600bはいくつかのフィールド(例えば、3つ以上のフィールド)に基づく分類を含むが、この分類問題の複雑さは、後に述べる実際の分類データベースの特性を利用することによって著しく低減され得る。特に、多くの送信元−宛先アドレスのペアがトリプレット(すなわち、トランスポートレベルフィールドの1つのセット、1つのアクション、及び1つの相対的プライオリティ)の同じグループを共有するということを理解することによって、チェックされるべきエントリの数−そしてメモリアクセスの数−は実質的に低減される。複数の送信元−宛先アドレスのペアをトランスポートレベル(又は他の)フィールドの様々なセットの1グループと関係づけるという概念は−すなわち、これらの送信元−宛先アドレスのペアのそれぞれがトリプレットの同じセットを使用するので−ここでは"トランスポート共有"("TLS")と呼ばれる。トランスポートレベルフィールドの1グループは送信元−宛先アドレスの複数のペアによって潜在的に共有され得るが、トランスポートレベルフィールドの一意のグループのそれぞれは一度記憶され、それによりパケット分類システムのストレージ要件を低減する。
【0073】
2ステージ分類スキームの第1ステージ600aは、上記のように、多次元分類問題を2次元分類問題に変えることによって簡略化される。しかしながら、パケットが分類データベース内のいくつかのルールにマッチする可能性があり−そして実際にはマッチしそうである−、したがって、第1ステージ600aは複数のマッチを戻すだろう。複数のマッチは、少なくとも部分的には、分類データベース内の全ルールの送信元−宛先アドレスのペアのオーバーラップ性によって、そして第2には、送信元−宛先アドレスのペアは任意のプライオリティに関連し得るという事実によって生じ得る。考えられる全てのマッチングルールを見つけることは、第1分類ステージにおいて必要とされるメモリアクセスの数を著しく増加させ得る。さらに、複数のマッチが第1分類ステージから戻されたとき、分類の第1及び第2ステージ600a、600b間での結果のマージが困難となる。したがって、他の実施形態では、簡略化してパケット分類の第1ステージ600aの効率を向上させるべく、1つの最適なマッチが第1ステージから戻される。一実施形態では、"最適マッチ(most specific match)"は、パケットのネットワークパスについての最大量の情報を提供するマッチである(例えば、IPネットワークでは、最適マッチは、パケットをカバーしている全てのフィルタの共通集合である)。第1分類ステージ600aから1つのマッチングフィルタを決定して戻すプロセスは、ここで"最適フィルタマッチング(most specific filter matching)"(又は、"MSFM")と呼ばれる。
【0074】
図9に転じて、2ステージパケット分類のための方法900の他の実施形態が示される。2ステージパケット分類のための方法900は、トランスポートレベル共有及び最適フィルタマッチングの双方を実装する。図9のブロック910を参照すると、パケットが受信される。ブロック920で説明するように、分類の第1ステージにおいて、パケットはパケットの送信元及び宛先アドレスに基づいて、1つの最適マッチを発見すべく分類される。ブロック930で説明される分類の第2ステージにおいて、パケットは、トランスポートレベル共有を用いて、1以上のトランスポートレベルフィールドに基づいて分類される。ブロック940で説明されるように、その分類の2つのステージの結果に基づいて、最も高いプライオリティのアクションが決定されてパケットに適用される。他の実施形態では、第2ステージにおけるトランスポートレベル共有なしで最弱フィルタマッチングが第1ステージにおいて使用され、さらなる実施形態では、第1ステージにおける最適フィルタマッチングなしでトランスポートレベル共有が第2ステージにおいて使用されるということが理解されるべきである。
【0075】
最適フィルタマッチング(MSFM)及びトランスポートレベル共有(TLS)の双方が、以下により詳細に説明される。この議論は、TLSの説明から始まり、MSFMの説明が続く。
【0076】
典型的な分類データベースは、複数のルールの1つのリストを持つ。このことは、ルール1005a、1005b、・・・、1005yを含むいくつかの複数のルール1005を持つ分類データベース1000を示す図10に示される。ルール1005a−yのそれぞれは、例えば、関連するアクション1020及びプライオリティ1030だけでなく、1つの送信元アドレス1010a、1つの宛先アドレス1010b、及び1以上のトランスポートレベルフィールド1010c(又は他のフィールド)を持つ。ルール1005のそれぞれについて、トランスポートレベルフィールド1010c、アクション1020、及びプライオリティ1030の組合せは、前述したように"トリプレット"1040と呼ばれる。前に議論したように、典型的な分類データベースは、送信元−宛先ペアの数に比べて比較的少ない一意のトランスポートレベルフィールドセットを持ち、さらに、典型的なデータベースにおけるトランスポートレベルフィールドセットの同じグループは、複数の送信元−宛先ペアによって共有される(図8及び付随する本文を参照すること)。分類データベースのこの特性を利用すべく、データベース1000の複数のルール1005は複数のルールセットにグループ化される。1つのルールセットは、同じ送信元及び宛先アドレスのペアを持つデータベースのルールを含む。例えば、図8に戻って、グループ801内の複数のルールは、第1ルールセットを有し(すなわち、それらは送信元アドレス"192.128.10.5"及び宛先アドレス"172.128.*"を共有する)、グループ802内の複数のルールは、第2ルールセットを有する(すなわち、それらは送信元アドレス"128.128.10.7"及び宛先アドレス"172.128.*"を共有する)。
【0077】
いくつかのルールセットへの分類データベースのパーティショニングの一例が、図11Aに示される。本図を参照すると、分類データベース1100は、ルールセット1150a、1150b、・・・、1150qを含むいくつかのルールセット1150に組織化される。それぞれのルールセット1150a−qは1以上のルールを含み、任意のルールセット1150内のそれぞれのルールは、ルールセット内の他の全てのルールと同じ送信元及び宛先アドレスのペアを共有する。一実施形態では、図11Aに示されるように、データベース1100のルールは、それぞれのルールセット1150a−qのルールがデータベース内の連続的な空間を占めるよう配列される。また、1つのルールセット1150内のルールは、連続するプライオリティレベルを占める。しかしながら、他の実施形態では、1つのルールセットは連続するプライオリティレベルを占めないルールによって形成されてよい。ルールセット1150a−qは、それぞれフィルタ1160と関連していると考えられる(すなわち、ルールセット1150aはフィルタ1160aと関連し、ルールセット1150bはフィルタ1160bと関連する、等)。1つのルールセット1150のためのフィルタ1160は、そのルールセットのための送信元−宛先ペアを含む。図11Aの実施形態は、1つの分類データベースの複数のルールが複数のルールセットを形成する方法の一例に過ぎないことが理解されるべきである。
【0078】
図11Aにおけるそれぞれのルールセット1150(及び対応するそれぞれのフィルタ1160)は、関連するトリプレットのグループを持っており、それぞれのトリプレットは、複数のトランスポートレベル(又は他の)フィールド、1つのアクション、及び1つの相対的プライオリティを持つ。図8に再び戻ると、ルールセット801、802のそれぞれは、それに関連する3つのトリプレットの1つのグループを持つ。そして、図8の例において、それぞれのルールセット801、802はトリプレットの同じグループを偶然に持つ(すなわち、ルールセット801、802送信元−宛先ペアがそれぞれ、トリプレットの同じセットを共有する)。任意のルールセット及びフィルタに関連するトリプレットは、ここで"複数のビン"、そして、(以下に説明される"ラージビン"と区別されるよう)ここにおいて"複数のスモールビン"と呼ばれる複数のグループを形成する。したがって、図11Aに示されるように、それぞれのルールセット1150及び対応するフィルタ1160は、トリプレットのスモールビン1170に関連する(すなわち、ルールセット1150a及びフィルタ1160aはスモールビン1170aと関連する、等)。トランスポートレベル共有の概念に導くのは、トランスポートレベルフィールドの種々のセットの1つのグループ(すなわち、スモールビン)を、1つのルールセットに含まれる複数のルールの間で共有することである。
【0079】
図11Aのデータベース1100に関連するスモールビン1170は、図11Bにさらに示される。図11Bを参照すると、データベース1100は、スモールビン1170の集合に関連づけられている。それぞれのスモールビン1170は、1以上のエントリ1172を含み、それぞれのエントリ1172は、1以上のトランスポートレベル(又は他の)フィールド1174、1つの相対的プライオリティ1175、及び1つのアクション1176(すなわち、トリプレット)を持つ。図11Bに示されるように、スモールビン1170は、"複数のラージビン"にさらに論理的に組織化されてよく、それぞれのラージビン1180は、2以上のスモールビン1170の集合を含む。ラージビン1180の生成は以下に説明される。
【0080】
トランスポートレベルフィールドに基づいてパケットを分類するために使用される第2ステージデータ構造1700が、以下に説明される。以下に最適フィルタマッチングの議論に着目する。
【0081】
前に示唆したように、パケットのネットワークパスに基づいてパケットを分類するとき、パケットは分類データベース内の複数のルールにマッチする可能性がある。第1分類ステージ600aの効率を向上すべく−例えば、要求されるメモリアクセス数を低減すべく−、さらに、第1ステージの結果を第2分類ステージ600bとマージすることを簡略化すべく、第1ステージから1つの最適マッチを戻すことが望ましい。
【0082】
"フィルタ"という用語は、ここでは1つのルールセットに関連する送信元−宛先アドレスのペアを参照するために用いられるので、この議論におけるこの時点では、"ルール"ではなく"フィルタ"という用語が用いられる(図11A−11B及び付随する上の本文を参照すること)。しかしながら、"フィルタ"及び"ルール"という用語が、多くの場合区別なく使用されることが理解されるべきである。
【0083】
送信元及び宛先アドレスに基づいて分類されるパケットが複数のフィルタにマッチすることは、少なくとも部分的には、分類データベース内のフィルタのオーバーラップ性による。これは図12Aから12C及び図13Aから13Cにおいて概略的に図示される。まず図12Aを参照すると、1つのルールの送信元及び宛先アドレスは、2次元空間内の1つの領域(すなわち、矩形、線、又は点)として考えられる。図12Aでは、分類データベースの第1フィルタ1210は、F1とラベル付けされた矩形によって示される2次元空間を占める。フィルタF1は、トリプレットのスモールビン1215(B1)に関連する。図12Bに転じて、データベースの第2フィルタ1220(F2)も、送信元及び宛先アドレス空間における領域を占めており、このフィルタF2は、トランスポートレベルフィールドのスモールビン1225(B2)に関連する。
【0084】
フィルタF1及びF2は共に図12Cに示され、これら2つのフィルタによって定義された領域はオーバーラップ又は交わっていることがわかり、F1及びF2の共通集合は参照番号1290によって示されている。図12A−12Cに示されたフィルタF1及びF2は、"部分的にオーバーラップ"しているといえる。パケット(P)1205がフィルタF1及びF2の共通部分1290に含まれる送信元−宛先アドレスペアを持っている場合、このパケットは両方のフィルタにマッチする(すなわち、フィルタF1及びF2がパケットPによって定義される少なくとも点を共通して持つ)。また、パケットPは、フィルタF1及びF2の共通部分1290に含まれる任意の他のパケットだけでなく、F1及びF2に関連するスモールビンB1及びB2の集合(union)に関連するだろう。2以上のフィルタの共通部分に関連するスモールビンのこの集合は、ここでは"ラージビン"と呼ばれる。ビンB1及びB2の集合を持つラージビンは、図2Cにおける参照数字1295によって示される。
【0085】
フィルタは、"完全にオーバーラップ"していてもよく、このシナリオは図13A−13Cに示される。第1フィルタ1310(F1)は、図13Aに示される2次元空間内の領域を占め、第2フィルタ1320(F2)は図13Bに示されるこの空間内の領域占める。フィルタF1は関連するスモールビン1315(B1)を持ち、フィルタF2は関連するスモールビン1325(B2)を持つ。次に図13Cを参照すると、双方のフィルタF1及びF2が示され、これらのフィルタは共通部分1390でオーバーラップする(この場合、共通部分1390はF2によって定義される領域と等価である)。F2によって定義される領域(及び共通部分1390)は、フィルタF1の2次元空間に完全に含まれ、フィルタF1及びF2は、"完全にオーバーラップ"していると言える。この共通部分1390に含まれるパケット(P)1305は両方のフィルタF1及びF2にマッチし、このパケットP(及びこの共通部分1390に含まれる任意の他のパケット)は、スモールビンB1及びB2の集合を持つラージビン1395と関連するだろう。
【0086】
図12A−12C及び13A−13Cから分かるように、2つ(又はさらに多く)のフィルタの共通部分内にある送信元アドレス及び宛先アドレスを持つパケットは両方のフィルタにマッチするだろう。分類の第1ステージから1つのマッチのみを戻すという目標を達成すべく、全てのフィルタの共通部分がフィルタデータベース内に含まれる(すなわち、第1ステージデータ構造1600)。さらに、それぞれのフィルタ共通部分は、その共通部分を形成する個々のフィルタのトランスポートレベルフィールドの集合に関連している。言い換えると、上記したように、それぞれのフィルタ共通部分は、2以上のスモールビンの集合を持つラージビンに関連している。全てのフィルタ共通部分をルックアップテーブルに加えることは、理論的には極めて大きな記憶容量を必要とする。しかしながら、実際の分類データベースの検討は、実際上、フィルタ共通部分を記憶するために必要とされる追加の容量は、理論的な上限より著しく小さいことを示唆する。
【0087】
パケットをその送信元及び宛先アドレスに基づいて分類すべく、問題は、パケットが位置する複数のフィルタの最小の共通部分(又は、パケットが共通部分に含まれない場合は、単にそのフィルタ)を発見することの1つになる。複数のフィルタのこの最小の共通部分を発見すべく、第1分類ステージ(2次元分類問題)は2つの1次元ルックアップに分けられる。これは、第1次元1410及び第2次元1420を示す図14に概略的に示される。第1次元1410において、受信されたパケットの送信元アドレスが送信元アドレスルックアップデータ構造1412のエントリと比較され、1つのマッチが発見された場合に、1つのインデックス1414(I1)が戻される。同様に、第2次元1420において、そのパケットの宛先アドレスが宛先アドレスルックアップデータ構造1422のエントリと比較され、1つのマッチが発見された場合に、1つの第2インデックス1424(I2)が戻される。そして、その2つのインデックス1414、1424(I1及びI2)は、他のルックアップデータ構造(例えば、ハッシュテーブル)に問い合わせるために用いられるキー1430を形成すべく結合される。一実施形態では、それぞれ第1及び第2次元1410、1420のルックアップデータ構造1412、1422上で実行されるルックアップは、最長プレフィックスマッチ(LPM)を用いて実行される。さらなる実施形態では、2つの次元1410、1420における複数のルックアップはパラレルに実行される。送信元及び宛先の次元において2つのパラレルで独立したルックアップを利用することは、比較的少数のメモリアクセスしか必要とせず、リーズナブルな記憶要件しか提示しないと考えられる。
【0088】
図14に示されたパラレルなLPMルックアップスキームは、パケットが含まれるフィルタの最小の共通部分、又はこのスキームは1つの"非存在"フィルタを戻す。1つの非存在フィルタは、1つのフィルタの送信元アドレス及び異なるフィルタの宛先アドレスを持つ。非存在フィルタは、送信元及び宛先アドレスにおけるルックアップが独立に実行される(しかしながら、一実施形態では、これらのルックアップはパラレルに実行される)という事実に起因する。
【0089】
非存在フィルタの概念は、1つの例を参照することで最もよく理解されるだろう。図15を参照すると、データベースは文字A、B、C、D、及びEによって示される5つのフィルタを含み、これらのフィルタは2次元アドレス空間1500内で示される。フィルタAは、送信元及び宛先アドレス空間の全体をカバーし、このフィルタは"*"によって示される(すなわち、これは送信元及び宛先アドレスの両方においてワイルドカード文字"*"を持つ)。フィルタBは"*,Y*"の形式を持ち、この形式のフィルタ(すなわち、"*,Y*"又は"X*,*")は"部分指定フィルタ"と呼ばれる。フィルタC、D、及びEは、"完全指定フィルタ"と呼ばれ、これらのフィルタは"X*,Y*"の形式を持つ。例として、フィルタ"送信元アドレス 128.172.*/宛先アドレス *"は1つの部分指定フィルタであり、フィルタ"送信元アドレス 128.172.*/宛先アドレス 128.128.*"は1つの完全指定フィルタである。フィルタA、B、C、D、及びEの送信元及び宛先アドレスの組合せは、2次元空間内の12個の異なる領域を形成する。最初の5つの領域はフィルタA、B、C、D、及びEに一致する。R1からR7で示される(破線により示される)他の7つの領域は、非存在フィルタに該当する。領域R1からR7は1つのフィルタの宛先アドレス及び他のフィルタの送信元アドレスから形成され、これらの領域は、上記のように送信元及び宛先アドレスにおけるルックアップが独立に実行されることによって生成される。例えば、領域R4は、フィルタEの送信元アドレス及びフィルタDの宛先アドレスを結合することによって生成され、これは存在しないフィルタをもたらす。図15に示される図は、通常、クロス積テーブルとして呼ばれる。
【0090】
図14のパラレルルックアップスキームが1つの結果を戻すことを保証すべく、非存在フィルタR1からR7の全てがフィルタデータベース内に入れられる必要があるように思われる。いくつかの従来技術(例えば、クロス積テーブルスキーム)は、全ての非存在フィルタをフィルタデータベースに加えることを提案している。しかしながら、実際の分類データベースの分析は、非存在フィルタの数が非常に大きくなり得ること示唆しており、したがってフィルタデータベースに加えられる非存在フィルタの数を最小化することが望ましい。したがって、一実施形態では、全ての可能な非存在フィルタの1つのサブセットのみが、分類データ構造に含まれる。分類データ構造への全ての考えられる非存在フィルタの追加が避けられる方法(及び全ての考えられる非存在フィルタの代わりにデータ構造に配置された非存在フィルタの1つのサブセット)は、以下により詳細に説明される。
【0091】
図15を参照すると、領域R1からR7の多くが、少数の他のフィルタにまとめられることがわかる。特に、R1、R3、及びR4を完全にカバーする最小のフィルタは、全2次元空間であるフィルタAである。領域R1、R3、及びR4の1つに入る任意のパケットの送信元又は宛先アドレスの一方におけるサーチは、領域Aに含まれるフィルタの送信元又は宛先アドレスを戻す。したがって、フィルタ"*,*"への別個のエントリが存在すれば、非存在フィルタR1、R3、及びR4はフィルタAに集約され、R1、R2、及びR4への別個のエントリはフィルタデータベースから除かれる。同様に、領域R5、R6、及びR7は、フィルタBによって完全にカバーされ、これらの非存在フィルタはフィルタBへのエントリに集約される。領域R5、R6、又はR7の1つにある任意のパケットについて、このパケットの宛先アドレスにおけるサーチは、フィルタBの宛先アドレスを戻すだろう。したがって、部分的に指定されたフィルタBへの別個のエントリが分類データ構造内に用意されているかぎり、R5、R6、及びR7の別個のデータベースエントリは必要とされない。
【0092】
領域R2は、しかしながら、任意の他のフィルタとマージされる。フィルタDの送信元アドレス及びフィルタEの宛先アドレスから形成されるこの領域は、1つの完全指定フィルタ−すなわち、フィルタCによって完全にカバーされる。非存在フィルタR2は、1つの完全指定フィルタ内に完全に含まれるただ1つのものであるという点で、他の非存在フィルタと区別される。非存在フィルタR2は、フィルタC又は他のエントリに集約されることができず、このフィルタへの1つのエントリはフィルタデータベースに配置される。R2のような非存在フィルタは、ここでは"インジケータフィルタ"と呼ばれる。インジケータフィルタは、そのインジケータフィルタを完全にカバーするフィルタの考えられる最小の共通部分に相当するトランスポートレベルフィールドのセットと関連づけられる。例として、図15に示されたフィルタのセットについて、領域R2を完全にカバーするフィルタはフィルタA及びCであり、これらの2つのフィルタの共通部分はフィルタCに簡略化される。したがって、インジケータフィルタR2は、フィルタCと同じトランスポートレベルフィールドのセットに関連づけられるだろう。
【0093】
いくつかの追加の観察が、第1ステージデータ構造1600の開発の助けとなる。全般的に、分類データベース内のフィルタの間で部分的にオーバーラップする3つの送信元、すなわち、(1)部分指定フィルタ(すなわち、"X*,*"又は"*,Y*"形式のフィルタ)の間で生成された部分的なオーバーラップ、(2)完全指定フィルタ(すなわち、"X*,Y*"形式のフィルタ)の間で生成された部分的なオーバーラップ、及び(3)部分指定フィルタ及び完全指定フィルタの間で生成された部分的なオーバーラップが存在する。送信元次元においてワイルドカードを持つ部分指定フィルタのそれぞれは、宛先次元においてワイルドカードを持つ部分指定フィルタの全てと部分的なオーバーラップを生成し、そのような部分指定フィルタの共通部分によって生成される部分的なオーバーラップの数は、送信元及び宛先次元のそれぞれにおける部分指定フィルタの数の積に一致する。部分指定フィルタの共通部分による部分的なオーバーラップの数は、理論的にはかなり大きくなる。一方、完全指定フィルタは、わずかな数の互いの部分的オーバーラップを生成する。この結果は、実際上、殆どの完全指定フィルタが2次元アドレス空間における直線セグメント又は点であることによる。
【0094】
先の段落において示唆されたように、典型的には、部分指定フィルタが、典型的な分類データベース内のフィルタ間での部分的オーバーラップの主原因である。しかしながら、部分指定フィルタは、多くの場合、分類データベース内の全フィルタ数の小さな割合を占める。なぜなら、ネットワーク管理者は通常、特定のアドレスドメインの間で交換されるトラフィックに適用されるルールを指定するからである。したがって、部分指定フィルタによってもたらされる部分的フィルタオーバーラップの数は、実際には理論的な最悪のケースより著しく小さい。また、上記したように、完全指定フィルタは、フィルタ間の部分的オーバーラップをわずかな数生成する。したがって、実際の分類データベースに存在する部分的オーバーラップの数は、概して、理論上発生することが期待されるより著しく小さい。
【0095】
ここでは、図13A−13Cに示したような、完全にオーバーラップするフィルタについて考慮していないことに注意すべきである。先に説明したように、一実施形態では、最長プレフィックスマッチ(LPM)が、MSFMで実行される2つの1次元サーチのそれぞれにおいて使用される。フィルタが完全にオーバーラップする場合、これらのフィルタの共通部分はこれらのフィルタの1つに等しく、LPMサーチがそのフィルタを特定する。したがって、第1ステージデータ構造1600は、一実施形態では、完全にオーバーラップするフィルタについて説明する必要がない。
【0096】
上記の観察及び議論(図6−15及び付随する本文を参照すること)は、第2ステージデータ構造170だけでなく第1ステージデータ構造1600を構築するために使用することができる"基本要素"を提供し、これらの2つのデータ構造の実施形態が以下に説明される。パケットを分類するための(すなわち、パケットに適用すべき1つのアクションを特定するための)第1及び第2ステージデータ構造1600、1700をサーチする方法の実施形態が、以下に提示される。
【0097】
ここで図16Aを参照すると、第1ステージデータ構造1600の一実施形態が示される。第1ステージデータ構造1600は、パラレルLPMデータ構造1601及びフォワーディングテーブル1602を有する。先に説明したように、MSFMスキームは、図14に関連して先に提示及び説明されたような、送信元及び宛先アドレス上でそれぞれ実行される2つの1次元サーチを用いる。したがって、パラレルLPMデータ構造は、1つの送信元アドレスルックアップデータ構造1610及び1つの宛先アドレスルックアップデータ構造1620を含む。一実施形態では、送信元及び宛先アドレスルックアップデータ構造1610、1620は、トライデータ構造として実現される。しかしながら、送信元及び宛先アドレスルックアップデータ構造1610、1620を実現するために他の代替のデータ構造を使用し得ることが当業者に理解されるだろう。
【0098】
さらに図16Bに、パラレルLPMデータ構造1601の一実施形態が概略的に示される。送信元アドレスルックアップデータ構造1610は、複数のエントリ1612を含み、それぞれのエントリ1612は、1つの送信元プレフィックス1614a、1つのフィルタタイプ1614b、及び1つのインデックス値1614c(又は他の識別子)を指定する。同様に、宛先アドレスルックアップデータ構造1620は複数のエントリ1622を含み、それぞれのエントリ1622は、1つの宛先プレフィックス1624a、1つのフィルタタイプ1624b、及び1つのインデックス値1624c(又は他の識別子)を指定する。ルックアップデータ構造1610、1620の双方において、フィルタタイプ1614b、1624bは、エントリ1612、1622が1つの完全指定フィルタ又は1つの部分指定フィルタのいずれに関連しているかを示す。パラレルLPMデータ構造1601上でサーチが実行されたとき、送信元アドレスルックアップデータ構造1610内のマッチする完全指定フィルタに関連する1つの第1インデックス1691(I1)、宛先アドレスルックアップデータ構造1620内のマッチする完全指定フィルタに関連する1つの第2インデックス1692(I2)、送信元アドレスルックアップデータ構造内のマッチする部分指定フィルタに関連する1つの第3インデックス1693(I3)、及び宛先アドレスルックアップデータ構造内のマッチする部分指定フィルタに関連する1つの第4インデックス1694(I4)を含む、4つのインデックス(又は他の識別子)が戻される。先に説明したように、送信元及び宛先アドレス次元におけるサーチは、一実施形態において、パラレルに実行される。
【0099】
完全指定フィルタに関連する最初の2つのインデックス1691及び1692(I1及びI2)は、1つのキー1690を生成すべく結合される。完全指定フィルタに関連するキー1690は、部分指定フィルタに関連する第3及び第4インデックス1693、1694だけでなく、以下に説明されるようにフォワーディングテーブル1602をサーチするために使用される。この時点において完全及び部分指定フィルタの間を区別する理由は、マッチしているフィルタは部分指定フィルタであり、最長プレフィックスマッチは分類の第1ステージにおいて使用されるからであり、期待される部分指定フィルタは特定されない(すなわち、特定すべきマッチしている送信元又は宛先プレフィックスは、実際のマッチングフィルタの対応するプレフィックスより"長い")。
【0100】
一実施形態では、図16Aに示されるように、フォワーディングテーブル1620は、プライマリテーブル1630及び2つのセカンダリテーブル1640a、1640bを有する。プライマリテーブル1630は、複数の完全指定フィルタ、複数の完全指定フィルタ共通部分、及び複数のインジケータフィルタのための複数のエントリを含む。繰り返すと、1つのインジケータフィルタは、異なる送信元−宛先ペアの送信元及び宛先プレフィックスから形成された1つの領域であり、完全指定フィルタ又はフィルタ共通部分で集約されることができない(例えば、上記で議論したように、図15の領域R2を参照すること)。セカンダリテーブル1640a−bの一方は、送信元次元においてワイルドカードを持っている部分指定フィルタのための複数のエントリを含み、セカンダリテーブル1640a−bの他方は、宛先次元においてワイルドカードを持っている部分指定フィルタのための複数のエントリを含む。セカンダリテーブル1640a、1640bは、インジケータフィルタを含まない。上記したように、1つのフィルタの送信元(又は宛先)プレフィックス及び他のフィルタの宛先(又は送信元)プレフィックスから生成される同じ領域は部分指定フィルタで集約され(図15、領域R5、R6、及びR7を参照すること)、そのような領域のための複数のエントリはプライマリテーブルに追加される必要はない。
【0101】
プライマリテーブル1630の一実施形態が、図16Cに示される。本図を参照すると、プライマリテーブル1630はいくつかのエントリ1632を含み、それぞれのエントリは1つのキー1637a及び1以上のビンポインタ1637bを持つ。パラレルLPMサーチ(図16Bを参照すること)において特定された第1及び第2インデックス1691、1692(I1及びI2)から生成されたキー1690は、プライマリテーブル1630をサーチするために使用される。キー1690がプライマリテーブルのエントリ1632のいずれかのキー1637aとマッチする場合、そのエントリ内のビンポインタ1637bによって識別されるビンは、受信されたパケットに適用されるべき1つのアクション(例えば、プライオリティの最も高い1つのアクション)を発見すべくアクセスされる。プロセスは以下により詳細に説明される。1つのエントリ1632は、1つのスモールビン1670、又はそれに代えて複数のスモールビンの1つのグループ−すなわち、1つのフィルタ共通部分に対応する複数のスモールビンの1つの共通集合を持つ1つの"ラージビン"1680を指す。いくつかの実施形態では、例えばルールセットが連続するプライオリティレベルを占める複数のルールから成る場合に生じる結果として、プライマリテーブルの対応するエントリはラージビンに含まれる全てのスモールビンへのポインタを含むので、1つのラージビン1680が記憶されている必要はないということに注意すること。他の実施形態では、一方で、複数のラージビンが記憶されてよい(例えば、ルールセット内の複数のルールが非連続なプライオリティレベルを占める場合)。また、図16Cに示されるように、トランスポートレベル共有の結果、複数のエントリ1632が、同じスモールビン(又は複数のビン)1670を示す又は共有してよい。
【0102】
セカンダリテーブル1640a、1640bのそれぞれは、プライマリテーブル1630と類似している。一方で、セカンダリテーブルの一方にアクセスするためのキーは、第3インデックス1693(I3)を含み、他方のセカンダリテーブルにアクセスするためのキーは第4インデックス1694(I4)を含む。プライマリテーブル1630上での問い合わせが1つのマッチを戻した場合、セカンダリテーブル1640a−bは無視され、プライマリテーブルのマッチしているエントリが最適マッチングフィルタに該当する。一方で、プライマリテーブルでマッチが発見されない場合、セカンダリテーブル1640a−bのうちの1つにおける1つの問い合わせが1つのマッチを戻し、このマッチしているエントリが最適マッチングフィルタに該当するだろう。プライマリ及びセカンダリテーブル1630上の複数のクエリが1つのマッチを戻さない場合には、全2次元フィルタ空間(すなわち"*.*")に該当する1つのデフォルトフィルタが最適フィルタとして使用される。
【0103】
一実施形態では、プライマリテーブル1630及びセカンダリテーブル1640a、1640bは、ハッシュテーブルとして実装される。この実施形態では、プライマリ及びセカンダリハッシュテーブルをサーチするために用いられる1つのサーチキーを生成すべく、1つのハッシュ関数がキー(すなわち、キー1690或いは第3及び第4インデックス1693、1694)に適用されてよい。もちろん、ハッシュテーブルは、プライマリ及びセカンダリテーブル1630、1640a−bが実装される方法の単なる一例を表し、さらに他の代替のデータ構造が利用され得ることが理解されるべきである。
【0104】
ここで、一実施形態は図17に示される第2ステージデータ構造1700に着目する。第2ステージデータ構造1700の構築は、上記のいくつかの概念によって導かれる。最初に最も重要なことには、トランスポートレベル共有は、第1ステージデータ構造内の複数のエントリに、トランスポートレベルフィールドの別個のセットのグループ、より厳密には、それぞれが1以上のトランスポートレベルフィールド、1つのアクション、及び1つの相対的プライオリティ(すなわち、ルールの絶対的プライオリティと区別される、1つのルールセット内の1つの相対的プライオリティ)を持つトリプレットのグループを共有させることを可能にする。したがって、トリプレットのグループのそれぞれ−すなわち、それぞれのスモールビン−は、一度記憶されさえすればよい。第2に、1つのフィルタ共通部分に関連する2以上のスモールビンの集合(union)は論理的には1つのラージビンとして考えられるが、第1ステージデータ構造1600のプライマリ及びセカンダリテーブル1630、1640a−bは1つのエントリに関連する全てのスモールビンへのポインタを持つので、ラージビンは記憶される必要はない。繰り返すと、他の実施形態では、複数のラージビンは記憶されてもよい。トランスポートレベル共有により、第2ステージデータ構造1700は、単に複数のスモールビンに組織化された複数のトリプレットの1つのリストになり、トランスポートレベル共有によって提供されるエントリの低減によって、第2ステージデータ構造1700のためのメモリ記憶容量要件は他の分類技術と比較して相対的に小さい。
【0105】
図17を参照すると、第2ステージデータ構造1700はいくつかのトリプレット1710を持ち、それぞれのトリプレット1710は、1以上のトランスポートレベル(又は他の)フィールド1719a、1つのアクション1719b、及び相対的プライオリティ1719cを持つ。それぞれのトリプレット1710は、1つのスモールビン1720(複数のスモールビン1720a、1720b、・・・、720kのうちの1つ)と関係づけられている。スモールビン1720a−kは、トリプレット1710の複数のグループを持ち、1つのスモールビンが記憶されるメモリロケーションは、対応するポインタ1725によって特定され得る(すなわち、スモールビン1720aは対応するポインタ1725aによって特定され、スモールビン1720bは対応するポインタ1725bによって特定される等)。前述のように、ビンポインタ1725a−kは、フォワーディングテーブル1602に記憶される(図16Aを参照すること)。1つのスモールビン1720(又は、ラージビンが記憶されている場合には1つのラージビン)に関連するポインタ1725が第1ステージデータ構造1600上の1つの問い合わせで特定された場合、対応するスモールビン1720内の全てのトリプレットは受信されたパケットに対して比較される。少なくとも1つのマッチが発見された場合、そのマッチしているトリプレットに関連するアクションが、受信されたパケットに適用され得る。一実施形態では、このアクションは生じた最も高いプライオリティを持つ。
【0106】
一実施形態では、この第2ステージデータ構造1700は、ternary CAMのような内容参照可能メモリ(CAM)に実装されてよい。この実施形態では、CAMは、それぞれが第2ステージデータ構造1700のトリプレット1710のうちの1つと関連するいくつかのエントリを含む。第2ステージデータ構造1700がCAMに実装されたさらなる実施形態では、多くのCAMエントリ(例えば、1以上のスモールビン1720に関連するトリプレット1710)はパラレルにサーチされてよい。
【0107】
図18を参照すると、図1から17及び上記の付随する本文において示された2ステージパケット分類を用いて実行されるような、パケット分類方法の一実施形態が示される。本図のブロック1805を参照すると、1つのパケットが受信される。ブロック1810a及び1810bで説明されるように、送信元アドレス上及び宛先アドレス上で1つのルックアップが実行される(図14の部材1410、1420、及び図16Aの部材1610、1620を参照すること)。一実施形態では、図18に示されるように、送信元及び宛先アドレス上で複数の問い合わせがパラレルに実行される。一方で、他の実施形態では、これらの問い合わせがパラレルに実行されなくてもよい。送信元アドレスでの問い合わせに基づいて、1つの完全指定フィルタに関連する最長プレフィックスマッチ(LPM)及び1つの部分指定フィルタに関連するLPMが特定され、これはブロック1815aに示される。マッチしている完全指定フィルタに関連する1つのインデックスI1及びマッチしている部分指定フィルタに関連する1つのインデックスI3が戻される(図16Bの部材1691、1693を参照すること)。同様に、宛先アドレスでの問い合わせから、1つの完全指定フィルタに関連する最長LPM及び1つの部分指定フィルタに関連するLPMが特定され−ブロック1815bを参照すること−、そしてマッチしている部分指定フィルタに関連する1つのインデックスI4だけでなくマッチしている完全指定フィルタに関連する1つのインデックスI2が戻される(図16Bの部材1692、1694を参照すること)。
【0108】
そして、マッチしている完全指定フィルタに関連する2つのインデックスI1及びI2が、1つのキー(図16Bの部材1690を参照すること)を形成すべく結合される(例えば、連結される)。そして、このキーは、プライマリテーブル(図16A及び16Cの部材1630を参照すること)をサーチするために使用され、これはブロック1820aに説明される。ブロック1820b及び1820cを参照すると、インデックスI3はセカンダリテーブルのうちの1つをサーチするために使用され、インデックスI4は他方のセカンダリテーブルをサーチするために使用される(図16Aの部材1640a、1640bを参照すること)。繰り返すと、プライマリテーブル1630は、他のフィルタによって集約されない非存在フィルタ(すなわち、インジケータフィルタ)だけでなく、全ての完全指定フィルタ及び完全指定フィルタの複数の共通部分を持つ。セカンダリテーブル1640a、1640bのうちの1つは送信元アドレスにおいてワイルドカードを持つ部分指定フィルタを持ち、セカンダリテーブルの他方は宛先アドレスにおいてワイルドカードを持つ部分指定フィルタを持つが、複数のセカンダリテーブルにはインジケータフィルタは含まれない。一実施形態では、図18に示されるように、プライマリ及びセカンダリテーブル1630、1640a−b上でのサーチはパラレルに実行される。一方で、他の実施形態では、これらのサーチはパラレルに実行されなくてもよい。
【0109】
ブロック1825を参照すると、キー(I1及びI2から形成される)は、プライマリテーブル1630のエントリ1632のそれぞれのキー1637aと比較される(図16Cを参照すること)。1つのマッチが発見されると、ブロック1830に説明されるように、マッチしているエントリ内の複数のビンポインタ(又はポインタ)1637bがアクセスされる。I1及びI2から形成されるキーは、種々の方法でプライマリテーブルをサーチするために使用され得る。例えば、一実施形態では、1つのハッシュ関数がそのキーに適用され、そのハッシュが、ハッシュテーブルとして実装されているプライマリテーブル1630をサーチするために使用される。
【0110】
1つのマッチがプライマリテーブル1630内に発見された場合には、セカンダリテーブル1640a−bは無視される。プライマリテーブル内に1つのマッチが発見されず、セカンダリテーブルのうちの1つの中に1つのマッチが発見された場合には−ブロック1835を参照すること−、そのセカンダリテーブルのマッチしているエントリ内の(複数の)ビンポインタがアクセスされ、これはブロック1840に示される。(実際に、セカンダリテーブル内に1つのマッチが発見された場合には)セカンダリテーブルのうちの1つだけが1つのマッチしているエントリを持つことに注意すること。しかしながら、プライマリテーブル内又はいずれのセカンダリテーブルの中にもマッチが発見されない場合には、ブロック1845に説明されるように、全2次元アドレス空間に一致する1つのデフォルトエントリが使用され、このエントリの関連するビンポインタがアクセスされる。この時点で、受信されたパケットはそのネットワークパスに基づいて分類されており、処理は第2ステージ分類に移行する。
【0111】
ここでブロック1850を参照すると、ビンポインタのうちの1つによって特定される1つのスモールビン(又は、ある実施形態では、1つのラージビン)がアクセスされる。ブロック1855に説明されるように、受信されたパケットのトランスポートレベルフィールドはアクセスされたビンのそれぞれのエントリと比較され(図17を参照すること)、アクセスされたビン内のエントリに1つのマッチしているエントリが存在しているか否かを判断する。ブロック1865に説明されるように、アクセスされたビンが1つのマッチしているエントリを持つ場合−ブロック1860を参照すること−、そのマッチしているエントリと関連するアクションが戻される。ブロック1870を参照すると、その戻されたアクションはその後パケットに適用される。
【0112】
上記のように、プライマリテーブル又はセカンダリテーブルのうちの1つの中の1つのエントリは、それぞれが1つのスモールビンを特定する複数のポインタを持ってよい(すなわち、言い換えると、そのエントリは1つのラージビンに関連する)。したがって、関連するビン内の全てのエントリを検討した後(ブロック1855を参照すること)、1つのマッチしているエントリが特定されない場合(ブロック1860を参照すること)、処理はまだ検討されていない任意の他の複数のビンポインタ(及び複数のビン)に注意を向ける(ブロック1850を参照すること)。問い合わせるべき追加のビンが存在する場合、1つのスモールビンをアクセスするための上記のプロセスが繰り返される(すなわち、ブロック1850、1855、及び1860)。したがって、アクセスされていないビンポインタが残っている限り、1つのスモールビンをアクセスしてサーチするための処理が、1つのマッチが発見されるまで繰り返される。
【0113】
ここで図15に戻ると、前述のように、他のフィルタで集約されないR2のような複数の領域−すなわち"インジケータフィルタ"−が、プライマリテーブル1630に追加される(しかしながら、セカンダリテーブル1640a−b内には配置されない)。完全指定フィルタ又はフィルタ共通部分は、多くのインジケータフィルタを含む。このことは、1つの完全指定フィルタ(又はフィルタ共通部分)1910及び多くの他の"より狭い"完全指定フィルタ(又はフィルタ共通部分)1920を示す図19に図示される。1つの完全指定の狭いフィルタ1920の送信元アドレスを、他の狭いフィルタ1920の宛先アドレスと結合することは−繰り返すと、上記したように、送信元アドレス及び宛先アドレスのルックアップテーブル上での複数の問い合わせが独立に実行されることによって生じる結果である−、フィルタ1910に完全に含まれ、それゆえ他のフィルタでは集約されない多くの非存在フィルタ1930を生成する。したがって、これらのインジケータフィルタ1930は、一実施形態では、プライマリテーブル1630に配置される。一方で、更なる他の実施形態では、任意の完全指定フィルタに関連するインジケータフィルタ数に1つの上限が設けられる。インジケータフィルタのこの指定された上限を超えるいずれの完全指定フィルタ又はフィルタ共通部分については、そのフィルタ及びその関連するインジケータフィルタはプライマリテーブル1630に配置されない。図19の完全指定フィルタ1910のような、比較的多数のインジケータフィルタを囲んでいるフィルタは、そのようなフィルタは典型的には広範囲の送信元及び宛先アドレスにわたるので、"ワイド"フィルタと呼ばれる。
【0114】
上記の実施形態は、図20Aから20Cにさらに図示される。図20A、20B、及び20Cは図16A、16B、及び18にそれぞれ類似しており、類似の構成要素は図20A−20Cにおいて同じ数値表示を持つ。また、上記において既に説明した構成要素の記載は、いくつかの構成要素について以下の本文では繰り返されない。
【0115】
最初に図20Aを参照すると、インジケータフィルタの指定された境界を越えるフィルタ−すなわちワイドフィルタ−は、ここでワイドフィルタテーブル1650と呼ばれる別のデータ構造に配置さられる。ワイドフィルタテーブル1650は、それぞれのワイドフィルタについて1つのエントリを持つ。一実施形態では、ワイドフィルタテーブル1650は、クロス積テーブルに類似するデータ構造を持つ(図15及び19を参照すること)。最も現実的な分類データベースのためには、ワイドフィルタの数は小さいことが期待される。しかしながら、1つのワイドフィルタはプライマリテーブル1630内に多数のエントリを生成する可能性があるので、これらのワイドフィルタを(プライマリ及びセカンダリテーブルでパラレルにサーチされる)別個のデータ構造に移動させることは、分類プロセスの効率を著しく向上させることができる。
【0116】
次に図20Bを参照すると、既に説明したように、分類の第1ステージの間で、4つの異なるインデックス1691、1692、1693、1694(I1からI4)が送信元及び宛先アドレステーブル1610、1620への問い合わせからそれぞれ戻される。上記されたように、第1及び第2インデックス1691、1692は、完全指定フィルタに関連するマッチしている送信元及び宛先プレフィックスに該当し、第3及び第4インデックス1693、1694は、部分指定フィルタに関連するマッチしている送信元及び宛先プレフィックスに該当する。ワイドフィルタを説明するこの実施形態では、送信元及び宛先アドレステーブル1610、1620上の複数の問い合わせは、1つの第5インデックス1695(I5)及び1つの第6インデックス1696(I6)も戻す。第5インデックス1695は、1つのワイドフィルタに関連するマッチしている送信元プレフィックスに該当し、第6インデックス1696は、1つのワイドフィルタに関連するマッチしている宛先プレフィックスに該当する。送信元アドレステーブル1610及び宛先アドレステーブル1620のそれぞれにおいて、フィルタタイプ指定1614b、1624bは、そのエントリが1つの完全指定フィルタ、1つの部分指定フィルタ、又は1つのワイドフィルタに関連しているかを示す。以下に説明されるように、第5インデックス1695及び第6インデックス1696(I5及びI6)は結合されて、ワイドフィルタテーブル1650に問い合わせするために使用される1つのキー2020を形成する。
【0117】
図20Cには、第2ステージパケット分類のための方法1800の他の実施形態が示される。図20Cに示される実施形態は、図18に関連して既に説明された実施形態と略同一の方法で進行する。しかしながら、図20Cに示される方法はワイドフィルタを説明し、上記したように、本実施形態はワイドフィルタテーブル1650並びに第5及び第6ワイドフィルタインデックス1695、1696を利用する。
【0118】
図20Cに転じて、パケットが受信され(ブロック1805を参照すること)、ブロック1810a、1810bに説明されるように、送信元及び宛先アドレス上でルックアップが実行される。ブロック1815aに示されるように、送信元アドレスの問い合わせに基づいて、1つの完全指定フィルタに関連する最長プレフィックスマッチ(LPM)、1つの部分指定フィルタに関連するLPM、及び1つのワイドフィルタに関連するLPMが特定され、インデックスI1、I3、及びI5が戻される(図20B、部材1691、1693、1695を参照すること)。繰り返すと、I1はマッチしている完全指定フィルタに関連し、I3はマッチしている部分指定フィルタに関連し、I5はマッチしているワイドフィルタに関連する。同様に、宛先アドレスでの問い合わせから、1つの完全指定フィルタに関連する最長LPM、1つの部分指定フィルタに関連するLPM、及び1つのワイドフィルタに関連するLPMが特定され−ブロック1815bを参照すること−、そしてマッチしているワイドフィルタに関連する1つのインデックスI6だけでなく、マッチしている完全指定フィルタに関連する1つのインデックスI2、マッチしている部分指定フィルタに関連する1つのインデックスI4が戻される(図20Bの部材1692、1694、1696を参照すること)。
【0119】
ブロック1820a、1820b、及び1820cに説明されるように、前述したようにマッチしている完全指定フィルタに関連する2つのインデックスI1及びI2が、プライマリテーブルをサーチするために使用される1つのキーを形成すべく結合され、インデックスI3及びI4はセカンダリテーブルをサーチするために使用される。さらに、1つのキーを形成すべくインデックスI5及びI6が結合され(図20Bの部材2090を参照すること)、そしてこのキーはワイドフィルタテーブル1650上の1つの問い合わせのために使用され、これはブロック1820dに説明される。一実施形態では、図20Bに示されるように、プライマリテーブル1630、セカンダリテーブル1640a−b、及びワイドフィルタテーブル1650上でのサーチはパラレルに実行される。一方で、他の実施形態では、これらのサーチはパラレルに実行されなくてもよい。
【0120】
ブロック1825を参照すると、キー(I1及びI2から形成される)は、プライマリテーブル1630のエントリ1632のそれぞれのキー1637aと比較され(図16Cを参照すること)、1つのマッチが発見されると、ブロック1830に説明されるように、マッチしているエントリ内の複数のビンポインタ(又はポインタ)1637bがアクセスされる。本実施形態では、一方で、プライマリテーブル内に1つのマッチが発見されない場合、処理はワイドフィルタテーブルへと転じて−ブロック1885を参照すること−、キー(I5及びI6から形成される)がワイドフィルタテーブル内のそれぞれのエントリと比較される。ブロック1890に示されるように、ワイドフィルタテーブル内に1つのマッチが発見された場合、ワイドフィルタテーブルのマッチしているエントリ内の複数のビンポインタがアクセスされる。ブロック1840に示されるように、プライマリテーブルおよびワイドテーブルのいずれの中にも1つのマッチも発見されず、セカンダリテーブルのうちの1つの中に1つのマッチが発見された場合には−ブロック1835を参照すること−、そのセカンダリテーブルのマッチしているエントリ内の(複数の)ビンポインタがアクセスされる。プライマリテーブル、ワイドフィルタテーブル、又はいずれのセカンダリテーブルにもマッチが発見されない場合には、ブロック1845に説明されるように、全2次元アドレス空間に一致する1つのデフォルトエントリが使用され、このエントリの関連するビンポインタがアクセスされる。1つのマッチがプライマリテーブル1630内に発見された場合には、他の複数のテーブルは無視され、プライマリテーブルにマッチが見いだされず、1つのマッチがワイドフィルタテーブル1650内に発見された場合には、セカンダリテーブル1640a−bが無視される。受信されたパケットのネットワークパスに基づく分類は完了し、処理は第2ステージ分類に移行する。第2ステージは前述と同様の方法で進行するので、図20Cにおいては、パケット分類の第2ステージは示されていないことに注意すべきである。
【0121】
ここで、第1及び第2ステージデータ構造を生成及び/又は更新するための方法の実施形態に注意を向ける。図21を参照すると、上記の2ステージパケット分類プロセスのために使用されるデータ構造を生成及び/又は更新するための方法の実施形態が示される。図21で説明されるプロセスは、パケット分類に先立って(又は、一実施形態では、パケット分類の間に)実行される複数のプロセッサリプロセッシングオペレーションの1つのセットを有することに注意すべきである。一方で、開示された2ステージパケット分類スキームに必要なデータ構造(例えば、第1及び第2データ構造1600、1700)を生成及び/又は更新することは、パケットを分類するプロセスと比較して稀にしか実行されないだろう。したがって、開示された分類技術を実行するのに必要なプロセッシングの大部分は、比較的稀にしか実行される必要がない一連のプロセッサリプロセッシングオペレーションに対してずっと前倒しされる。
【0122】
ここで図21のブロック2110を参照すると、分類データベースの複数のルール(図10を参照すること)は複数のルールセットにグループ化され、それぞれのルールセット内の複数のルールは同じ送信元及び宛先アドレスを持つ(図11A及び11Bを参照すること)。上記したように、一実施形態では、1つのルールセットの複数のルールは連続するプライオリティレベルを占めるが、他の実施形態では、1つのルールセットの複数のルールは隣接するプライオリティレベルを占めなくてよい。上記したように、それぞれのルールセットに関連する送信元−宛先ペアはフィルタと呼ばれる。ブロック2120で説明されるように、対応するアクション及び相対的プライオリティだけでなく、それぞれのフィルタに関連するトランスポートレベル(又は他の)フィールドのセットは1つのスモールビンに組織化される。
【0123】
ブロック2130を参照すると、受信されたパケットの送信元及び宛先アドレス上のパラレルLPM問い合わせのために使用される送信元アドレスルックアップデータ構造及び宛先アドレスルックアップデータ構造が生成される(図16A及び16Bの部材1601を参照すること)。送信元アドレスルックアップデータ構造は、データベース内のそれぞれのフィルタ用の1つのエントリを持ち、それぞれのフィルタ用のエントリは1つの送信元プレフィックス、1つのフィルタタイプ指定(例えば、完全指定、部分指定、又はワイドであるか)、及び1つのインデックスを持つ。同様に、宛先アドレスルックアップデータ構造は、データベース内のそれぞれのフィルタ用の1つのエントリを持ち、それぞれのフィルタ用のエントリはそのフィルタのための1つの宛先プレフィックス、1つのフィルタタイプ指定、及び1つのインデックスを持つ。
【0124】
第1ステージデータ構造を完成すべく、フォワーディングテーブルが構築される(図16Aの部材1602を参照すること)。ブロック2140に説明されるように、複数のフィルタ共通部分が決定され(図12A−12Cを参照すること)、それぞれのフィルタ共通部分に関連する複数のスモールビンの集合−すなわち、1つのラージビン−が発見される(図11Bを参照すること)。ブロック2150に説明されるように、複数のインジケータフィルタも決定される。上記したように、複数のインジケータフィルタは、他のフィルタで集約され得ない非存在フィルタである(図15及び付随する本文を参照すること)。複数の完全指定フィルタ、複数の完全指定フィルタ共通部分、及び複数のインジケータフィルタが、プライマリテーブルに配置され(図16A及び16Cを参照すること)、これはブロック2160に説明される。繰り返すと、一実施形態では、完全にオーバーラップしている複数のフィルタ共通部分(図13A−13Cを参照すること)は、プライマリテーブルに配置されない。ブロック2170を参照すると、複数のセカンダリテーブルが生成され、1つのセカンダリテーブルは"X*,*"の形式の複数の部分指定フィルタを持ち、他方のセカンダリテーブルは"*,Y*"の形式の複数の部分指定フィルタを持つ。他の実施形態では、複数のワイドフィルタ−例えば、1つの指定された閾値を超えている多数のインジケータフィルタを持つフィルタ(図19を参照すること)−が他のテーブル−1つのワイドフィルタテーブル(図20Aの部材1650を参照すること)−に配置され、これはブロック2190によって示される。
【0125】
ブロック2180を参照すると、第2ステージデータ構造が生成される。先に説明したように、一実施形態では、第2ステージデータ構造は、それぞれのスモールビンと関連するトリプレットのセットを持つ(図17を参照すること)。スモールビンは、プライマリ及びセカンダリテーブルに含まれるポインタによって特定される。本実施形態では、複数のラージビンは第2ステージデータ構造内に記憶されず、むしろ、複数のラージビンは、2以上のスモールビンへの(1つのプライマリ又はセカンダリテーブルの1つのエントリ内の)複数のポインタの1つのリストによって単に特定される。(例えば連続しないプライオリティレベルの複数のルールをルールセットが持つ)他の実施形態では、複数のラージビンに関連するトリプレットのグループがメモリに記憶される。
【0126】
−2ステージ分類スキームを実装するために使用され得るデータ構造の複数の実施形態だけでなく−最適フィルタマッチング及びトランスポートレベル共有を使用する2ステージパケット分類のための方法の複数の実施形態がここで説明され、当業者は開示された複数の実施形態の利点を理解するだろう。トランスポートレベル共有は、記憶されるべきトリプレットの数を著しく低減することができ、これは、開示された2ステージ分類スキームのメモリ記憶容量要件を低減する。また、TLSから得られる低減された記憶容量要件によって、第2ステージデータ構造は、内容参照可能メモリ(又は他のハードウェアアーキテクチャ)での実装に対して容易に修正可能となる。さらに、最適フィルタマッチングをパケット分類の第1ステージに組み込むことは−TLSの使用と同様に−、パケットを分類するのに必要なメモリアクセス数を低減することができる。さらに、開示された2ステージ分類技術によって要求されるデータプロセッシングの大部分は、多くのプリプロセッシングオペレーション(例えば、第1及び第2ステージデータ構造の生成)に対してずっと前倒しされる。そのようなオペレーションは比較的稀にしか実行されない。
【0127】
上記の詳細な説明及び添付の図面は、単なる実例であり限定的ではない。それらは開示された実施形態の明確で包括的な理解のために主として提供され、それらから本質的でない限定が解釈されるべきではない。開示された実施形態の趣旨及び添付の特許請求の範囲から逸脱することなく、ここで説明された実施形態に多数の追加、削除、及び変更が、他の構成のみならず当業者によって考案され得る。

【特許請求の範囲】
【請求項1】
1つの受信されたパケットの1つのネットワークパスに基づいて1つの結果を決定する段階と、
前記結果に対応する少なくとも1つのビンを複数のビンから特定する段階であって、前記複数のビンのそれぞれは複数のフィールドの複数のセットを有する段階と、
前記少なくとも1つの対応するビンをサーチして、前記パケットにマッチする複数のフィールドの1つのセットを特定する段階と
を備える方法。
【請求項2】
複数のマッチするフィールドの前記セットに関連する1つのアクションを特定する段階と、
前記アクションを前記パケットに適用する段階と
をさらに備える請求項1に記載の方法。
【請求項3】
複数のマッチするフィールドの前記セットは1つのトランスポートレベルフィールドを有する
請求項1に記載の方法。
【請求項4】
前記結果を決定する段階は、前記パケットにマッチする1つの最適フィルタを特定する段階を有する
請求項1に記載の方法。
【請求項5】
前記パケットの前記ネットワークパスは、1つの送信元アドレス及び1つの宛先アドレスで表される
請求項4に記載の方法。
【請求項6】
前記1つの最適マッチングフィルタを特定する段階は、
1つの第1データ構造における1つのルックアップを実行して前記パケットの送信元アドレスにマッチする1つのエントリを発見する段階と、
1つの第2データ構造における1つのルックアップを実行して前記パケットの宛先アドレスにマッチする1つのエントリを発見する段階と
を含む請求項5に記載の方法。
【請求項7】
1つのパケットを受信する段階であって、前記パケットは、1つの送信元アドレス、1つの宛先アドレス、及び複数の他のフィールドを含む1つのヘッダを有する段階と、
1つのデータ構造内の複数のエントリから、前記パケットの前記送信元アドレスにマッチする1つの送信元アドレスプレフィックスを有する1つのエントリを特定する段階であって、前記マッチするエントリは1つの第1識別子を含む段階と、
他のデータ構造内の複数のエントリから、前記パケットの前記宛先アドレスにマッチする1つの宛先アドレスプレフィックスを有する1つのエントリを特定する段階であって、前記マッチするエントリは1つの第2識別子を含む段階と、
複数のビンから前記第1及び第2識別子に対応する1つのビンを特定する段階であって、前記対応するビンは、複数のトランスポートレベルの複数のセットを含む段階と、
前記パケットヘッダの複数の他のフィールドのうちの少なくとも1つを、対応するビン内の複数のトランスポートレベルフィールドのセットのそれぞれと比較して、複数のトランスポートレベルフィールドの1つのマッチするセットを発見する段階と
を備える方法。
【請求項8】
複数のトランスポートレベルフィールドの前記マッチするセットに関連する1つのアクションを前記受信されたパケットに適用する段階
さらに備える請求項7に記載の方法。
【請求項9】
前記パケットヘッダ内の前記複数の他のフィールドは、1つのプロトコル、1つの送信元ポート番号、及び1つの宛先ポート番号の少なくとも1つを有する
請求項7に記載の方法。
【請求項10】
前記パケットヘッダの前記送信元アドレスは1つの送信元IP(インターネットプロトコル)アドレスを有し、前記パケットヘッダの前記宛先アドレスは1つの宛先IPアドレスを有する
請求項9に記載の方法。
【請求項11】
1つのパケットを受信する段階であって、前記パケットは、1つの送信元アドレス、1つの宛先アドレス、及び複数のトランスポートレベルフィールドを含む1つのヘッダを有する段階と、
1つの送信元アドレスデータ構造をサーチして、1つの第1インデックス及び1つの第3インデックスを発見する段階であって、前記第1インデックスは、前記パケットの前記送信元アドレスにマッチする1つの送信元プレフィックスを有する1つの完全指定フィルタと関連し、前記第3インデックスは、前記パケットの前記送信元アドレスにマッチする1つの送信元プレフィックスを有する1つの部分指定フィルタと関連する段階と、
1つの宛先アドレスデータ構造をサーチして、1つの第2インデックス及び1つの第4インデックスを発見する段階であって、前記第2インデックスは、前記パケットの前記宛先アドレスにマッチする1つの宛先プレフィックスを有する1つの完全指定フィルタと関連し、前記第4インデックスは、前記パケットの前記宛先アドレスにマッチする1つの宛先プレフィックスを有する1つの部分指定フィルタと関連する段階と、
前記第1及び第2インデックスから1つのキーを形成する段階と、
前記キーにマッチする1つのエントリについて1つのプライマリテーブルをサーチする段階であって、前記プライマリテーブルは複数のエントリを有し、それぞれのエントリは、1つの完全指定フィルタ、1つの完全指定フィルタの共通部分、及び1つのインジケータフィルタのうちの1つに対応する段階と、
マッチする1つのエントリが前記プライマリテーブルに発見された場合、前記マッチするエントリに関連する複数のビンポインタの1つのリストにアクセスする段階であって、前記リストのそれぞれのビンポインタは、複数のトランスポートレベルフィールドの複数のセットを有する1つのビンを特定する段階と
を備える方法。
【請求項12】
前記プライマリテーブルのマッチするエントリ内の前記複数のビンポインタのうちの1つによって特定される複数のビンのうちの1つにアクセスする段階と、
前記パケットの前記複数のトランスポートレベルフィールドを前記アクセスされたビン内の複数のトランスポートレベルフィールドのセットのそれぞれと比較する段階と、
前記パケットの複数のトランスポートレベルフィールドとマッチする複数のトランスポートレベルフィールドの1つのセットを前記アクセスされたビンが有する場合に、前記マッチする複数のトランスポートレベルフィールドのセットに関連する1つのアクションを前記受信されたパケットに適用する段階と
をさらに備える請求項11に記載の方法。
【請求項13】
前記第3インデックスにマッチする1つのエントリについて2つのセカンダリテーブルのうちの第1セカンダリテーブルをサーチする段階であって、前記第1セカンダリテーブルは複数のエントリを有し、それぞれのエントリは1つの部分指定フィルタに対応する段階と、
前記第4インデックスにマッチする1つのエントリについて2つのセカンダリテーブルのうちの第2セカンダリテーブルをサーチする段階であって、前記第2セカンダリテーブルは複数のエントリを有し、それぞれのエントリは1つの部分指定フィルタに対応する段階と、
前記プライマリテーブルにマッチが発見されず、1つのマッチするエントリが前記2つのセカンダリテーブルのうちの1つに発見された場合に、前記マッチするエントリに関連する複数のビンポインタの1つのリストにアクセスする段階であって、前記リストのビンポインタのそれぞれは、複数のトランスポートレベルフィールドの複数のセットを有する1つのビンを特定する段階と
をさらに備える請求項11に記載の方法。
【請求項14】
前記1つのセカンダリテーブルのマッチしているエントリ内の複数のビンポインタのうちの1つによって特定される複数のビンのうちの1つにアクセスする段階と、
前記パケットの前記複数のトランスポートレベルフィールドを、前記アクセスされたビン内の複数のトランスポートレベルフィールドのセットのそれぞれと比較する段階と、
前記パケットの前記複数のトランスポートレベルフィールドとマッチする複数のトランスポートレベルフィールドの1つのセットを前記アクセスされたビンが有する場合に、前記マッチする複数のトランスポートレベルフィールドのセットに関連する1つのアクションを前記受信されたパケットに適用する段階と
をさらに備える請求項13に記載の方法。
【請求項15】
前記セカンダリテーブルのいずれにもマッチが発見されない場合に、1つのデフォルトエントリに関連する複数のビンポインタの1つのリストにアクセスする段階であって、前記リストのビンポインタのそれぞれは、複数のトランスポートレベルフィールドの複数のセットを有する1つのビンを特定する段階
をさらに備える請求項13に記載の方法。
【請求項16】
前記デフォルトエントリは、2次元アドレス空間全体に対応する
請求項15に記載の方法。
【請求項17】
前記送信元アドレスデータ構造をサーチして、前記パケットの送信元アドレスにマッチする1つの送信元プレフィックスを有する1つのワイドフィルタに関連する1つの第5インデックスを発見する段階と、
前記宛先アドレスデータ構造をサーチして、前記パケットの宛先アドレスにマッチする1つの宛先プレフィックスを有する1つのワイドフィルタに関連する1つの第6インデックスを発見する段階と、
前記第5及び第6インデックスから1つの第2キーを形成する段階と、
前記第2キーとマッチする1つのエントリについて1つのワイドフィルタテーブルをサーチする段階であって、前記ワイドフィルタテーブルは複数のエントリを有し、それぞれのエントリは1つのワイドフィルタに対応する段階と、
前記プライマリテーブルにマッチが発見されず、1つのマッチするエントリが前記ワイドフィルタテーブルに発見された場合に、前記ワイドフィルタテーブル内の前記マッチするエントリに関連する複数のビンポインタの1つのリストにアクセスする段階であって、前記リストのビンポインタのそれぞれは、複数のトランスポートレベルフィールドの複数のセットを有する1つのビンを特定する段階と
をさらに備える請求項11に記載の方法。
【請求項18】
前記ワイドフィルタテーブルのマッチするエントリ内の前記複数のビンポインタのうちの1つによって特定される前記複数のビンのうちの1つにアクセスする段階と、
前記パケットの前記複数のトランスポートレベルフィールドを、前記アクセスされたビン内の複数のトランスポートレベルフィールドのセットのそれぞれと比較する段階と、
前記パケットの前記複数のトランスポートレベルフィールドとマッチする複数のトランスポートレベルフィールドの1つのセットを前記アクセスされたビンが有する場合に、前記マッチする複数のトランスポートレベルフィールドのセットに関連する1つのアクションを前記受信されたパケットに適用する段階と
をさらに備える請求項17に記載の方法。
【請求項19】
前記ワイドフィルタテーブルに含まれるそれぞれのワイドフィルタは、1つの指定された閾値を超える複数のインジケータフィルタを持つ1つの完全指定フィルタを有する
請求項17に記載の方法。
【請求項20】
前記受信されたパケット内の前記複数のトランスポートレベルフィールドは、1つの送信元ポート番号、1つの宛先ポート番号、1つのプロトコルの少なくとも1つを有する
請求項11に記載の方法。
【請求項21】
1つのパケット分類データベースの複数のルールを複数のルールセットにグループ化する段階であって、それぞれのルールセットは、1つの送信元及び宛先アドレスペアを持つ複数のルールを有し、それぞれのルールセットは、前記送信元及び宛先アドレスペアに対応する1つのフィルタに関連する段階と、
1つのスモールビンを前記複数のフィルタのそれぞれと関連づける段階であって、それぞれのスモールビンは複数のトランスポートレベルフィールドの複数のセットの1つのグループを有し、前記グループ内の複数のトランスポートレベルフィールドのセットのそれぞれは、前記関連するルールセット内の前記複数のルールのうちの1つに関連する段階と
を備える方法。
【請求項22】
前記複数のフィルタの少なくとも2つは同じ1つのスモールビンに関連する
請求項21に記載の方法。
【請求項23】
複数のフィルタ共通部分を特定する段階であって、それぞれのフィルタ共通部分は前記複数のフィルタのうちの少なくとも2つのフィルタの1つの共通部分に対応する段階
をさらに備える請求項21に記載の方法。
【請求項24】
1つのラージビンを前記複数のフィルタ共通部分のそれぞれと関連づける段階であって、それぞれのフィルタ共通部分の前記ラージビンは、少なくとも2つの前記共通部分のフィルタのそれぞれに関連する前記複数のスモールビンの1つの集合を有する段階と
をさらに備える請求項23に記載の方法。
【請求項25】
複数のインジケータフィルタを特定する段階であって、それぞれのインジケータフィルタは、前記複数のフィルタのうちの1つのフィルタの1つの送信元アドレス及び前記複数のフィルタのうちの他の1つのフィルタの前記宛先アドレスから形成される段階
をさらに備える請求項24に記載の方法。
【請求項26】
前記分類データベースに関連する前記複数のフィルタは、複数の完全指定フィルタ、送信元アドレス空間の全体に広がる複数の部分指定フィルタ、及び宛先アドレス空間の全体に広がる部分指定フィルタを有する
請求項25に記載の方法。
【請求項27】
複数のエントリを有する1つのプライマリテーブルを生成する段階であって、前記プライマリテーブルのエントリのそれぞれは、前記複数の完全指定フィルタのうちの1つ、前記複数のフィルタ共通部分のうちの1つ、又は前記複数のインジケータフィルタのうちの1つに関連し、前記プライマリテーブルのエントリのそれぞれは、1つのキー及び当該エントリの前記対応するフィルタに関連する前記スモールビンへのポインタの少なくとも1つを有する段階と、
複数のエントリを有する1つの第1セカンダリテーブルを生成する段階であって、前記第1セカンダリテーブルのエントリのそれぞれは、前記送信元アドレス空間の全体に広がる1つの送信元アドレスを持つ前記複数の部分指定フィルタのうちの1つに関連し、前記第1セカンダリテーブルのエントリのそれぞれは、1つのキー及び当該エントリの前記対応するフィルタに関連する前記スモールビンへの1つのポインタを有する段階と、
複数のエントリを有する1つの第2セカンダリテーブルを生成する段階であって、前記第2セカンダリテーブルのエントリのそれぞれは、前記宛先アドレス空間の全体に広がる1つの宛先アドレスを持つ前記複数の部分指定フィルタのうちの1つに関連し、前記第2セカンダリテーブルのエントリのそれぞれは、1つのキー及び当該エントリの前記対応するフィルタに関連する前記スモールビンへの1つのポインタを有する段階と
をさらに備える請求項26に記載の方法。
【請求項28】
前記プライマリテーブルの1つのエントリ内の前記少なくとも1つのポインタは、当該エントリの対応する1つのフィルタ共通部分に関連する1つのラージビンを特定する
請求項27に記載の方法。
【請求項29】
前記プライマリテーブルは、複数のインジケータフィルタの1つのサブセットを有する
請求項27に記載の方法。
【請求項30】
前記分類データベースに関連する前記複数のフィルタは、複数のワイドフィルタをさらに有する
請求項27に記載の方法。
【請求項31】
複数のエントリを有する1つのワイドフィルタテーブルを生成する段階であって、前記ワイドフィルタテーブルのエントリのそれぞれは前記複数のワイドフィルタのうちの1つに関連し、前記ワイドフィルタテーブルのエントリのそれぞれは1つのキー及び当該エントリの前記対応するフィルタに関連する前記スモールビンへの1つのポインタを有する段階
をさらに備える請求項30に記載の方法。
【請求項32】
1つの送信元アドレスデータ構造を生成する段階であって、前記送信元アドレスデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれは、前記複数のフィルタのうちの1つに対応する1つの送信元プレフィックスを含む段階と、
1つの宛先アドレスデータ構造を生成する段階であって、前記宛先アドレスデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれは、前記複数のフィルタのうちの1つに対応する1つの宛先プレフィックスを含む段階と
をさらに備える請求項21に記載の方法。
【請求項33】
複数のフィルタであって、それぞれのフィルタが1つの送信元アドレスプレフィックス及び1つの宛先アドレスプレフィックスを有する複数のフィルタと、
複数のビンであって、それぞれのビンは複数のトリプレットを有し、それぞれのトリプレットが少なくとも1つのトランスポートレベルフィールド、1つのアクション、及び1つのプライオリティを含む複数のビンと
を備え、
複数のフィルタのそれぞれは、前記複数のビンのうちの少なくとも1つに関連するデータ構造。
【請求項34】
前記複数のビンのうちの1つは、前記複数のフィルタの少なくとも2つに関連する
請求項33に記載のデータ構造。
【請求項35】
前記送信元アドレスプレフィックスは1つの送信元IP(インターネットプロトコル)アドレスプレフィックスを含み、前記宛先アドレスプレフィックスは1つの宛先IPアドレスプレフィックスを含む
請求項33に記載のデータ構造。
【請求項36】
前記少なくとも1つのトランスポートレベルフィールドは、1つのプロトコル、1つの送信元ポート番号、及び1つの宛先ポート番号のうちの少なくとも1つを含む
請求項33に記載のデータ構造。
【請求項37】
前記複数のビンの少なくともいくつかのそれぞれは、1つのスモールビンを有する
請求項33に記載のデータ構造。
【請求項38】
前記複数のビンの少なくとも1つは1つのラージビンを有し、前記ラージビンは1つのフィルタ共通部分に関連する前記複数のスモールビンの1つの集合を含む
請求項37に記載のデータ構造。
【請求項39】
1つの送信元アドレスデータ構造であって、前記送信元アドレスデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれが1つの送信元プレフィックス、1つのフィルタタイプ、及び1つのインデックスを含む送信元アドレスデータ構造と、
1つの宛先アドレスデータ構造であって、前記宛先アドレスデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれが1つの宛先プレフィックス、1つのフィルタタイプ、及び1つのインデックスを含む宛先アドレスデータ構造と、
1つのプライマリテーブルであって、前記プライマリテーブルは複数のエントリを有し、前記複数のエントリのそれぞれが1つのキー及び少なくとも1つのビンポインタを含み、前記複数のエントリのそれぞれが1つの完全指定フィルタ、1つの完全指定フィルタ共通部分、及び1つのインジケータフィルタのうちの1つに関連するプライマリテーブルと、
2つのセカンダリテーブルであって、前記セカンダリテーブルのそれぞれは複数のエントリを有し、前記複数のエントリのそれぞれが1つのキー及び少なくとも1つのビンポインタを含み、前記2つのセカンダリテーブルのそれぞれのエントリのそれぞれが1つの部分指定フィルタに関連する2つのセカンダリテーブルと
を備えるデータ構造。
【請求項40】
前記セカンダリテーブルのうちの1つは、1つの送信元アドレス空間の全体に広がる1つの送信元アドレスを有する複数の部分指定フィルタに関連し、前記2つのセカンダリテーブルの他方は、1つの宛先アドレス空間の全体に広がる1つの宛先アドレスを有する複数の部分指定フィルタに関連する
請求項39に記載のデータ構造。
【請求項41】
前記送信元アドレス及び宛先アドレスルックアップテーブルのそれぞれの中の前記フィルタタイプは、1つの完全指定フィルタ及び1つの部分指定フィルタのうちの1つを示す
請求項39に記載のデータ構造。
【請求項42】
1つのワイドフィルタテーブルであって、前記ワイドフィルタテーブルは複数のエントリを有し、前記複数のエントリのそれぞれが1つのキー及び少なくとも1つのビンポインタを含み、前記ワイドフィルタのエントリのそれぞれが1つのワイドフィルタに関連するワイドフィルタテーブル
をさらに備える請求項39に記載のデータ構造。
【請求項43】
前記送信元アドレス及び宛先アドレスルックアップテーブルのそれぞれの中の前記フィルタタイプは、1つの完全指定フィルタ、1つの部分指定フィルタ、及び1つのワイドフィルタのうちの1つを示す
請求項42に記載のデータ構造。
【請求項44】
前記プライマリ及びセカンダリテーブルの前記複数のエントリの中の前記複数のビンポインタのそれぞれは、1つの第2データ構造の複数のビンのうちの1つを特定し、それぞれのビンは複数のトリプレットを有し、それぞれのトリプレットは少なくとも、1つのトランスポートレベルフィールド、1つのアクション、及び1つのプライオリティを含む
請求項39に記載のデータ構造。
【請求項45】
前記送信元アドレスデータ構造の中のそれぞれの送信元アドレスプレフィックスは、1つの送信元IP(インターネットプロトコル)アドレスプレフィックスを含み、前記宛先アドレスデータ構造の中のそれぞれの宛先アドレスプレフィックスは1つの宛先IPアドレスプレフィックスを含む
請求項44に記載のデータ構造。
【請求項46】
前記少なくとも1つのトランスポートレベルフィールドは、1つのプロトコル、1つの送信元ポート番号、及び1つの宛先ポート番号のうちの1つを含む
請求項45に記載のデータ構造。
【請求項47】
前記プライマリテーブルは、全ての起こりうるインジケータフィルタの1つのサブセットのための複数のエントリを有する
請求項39に記載のデータ構造。
【請求項48】
1つのプロセッシングデバイスと、
前記プロセッシングデバイスに結合された1つのメモリであって、前記メモリは記憶された1つの第1データ構造を有するメモリと
を備える装置であって、
前記第1データ構造は、
1つの送信元アドレスルックアップデータ構造であって、前記送信元アドレスルックアップデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれが1つの送信元プレフィックス、1つのフィルタタイプ、及び1つのインデックスを含む1つの送信元アドレスルックアップデータ構造と、
1つの宛先アドレスルックアップデータ構造であって、前記宛先アドレスルックアップデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれが1つの宛先プレフィックス、1つのフィルタタイプ、及び1つのインデックスを含む1つの宛先アドレスルックアップデータ構造と、
1つのプライマリテーブルであって、前記プライマリテーブルは複数のエントリを有し、前記複数のエントリのそれぞれは1つのキー及び少なくとも1つのビンポインタを含み、前記複数のエントリのそれぞれが1つの完全指定フィルタ、1つの完全指定フィルタ共通部分、及び1つのインジケータフィルタのうちの1つに関連する1つのプライマリテーブルと、
2つのセカンダリテーブルであって、前記セカンダリテーブルのそれぞれは複数のエントリを有し、前記複数のエントリのそれぞれは1つのキー及び少なくとも1つのビンポインタを含み、前記2つのセカンダリテーブルのそれぞれのエントリのそれぞれが1つの部分指定フィルタに関連する2つのセカンダリテーブルと
を有する装置。
【請求項49】
前記プロセッシングデバイスに結合された1つの第2メモリであって、前記第2メモリは記憶された1つの第2データ構造を有し、前記第2データ構造が複数のスモールビンを含み、それぞれのスモールビンが複数のトリプレットを持ち、それぞれのトリプレットが少なくとも、1つのトランスポートレベルフィールド、1つのアクション、及び1つのプライオリティを持つ第2メモリ
をさらに備え、
前記プライマリ及びセカンダリテーブルの前記複数のエントリの中の前記複数のビンポインタのそれぞれは、前記第2データ構造の前記複数のスモールビンのうちの1つを特定する
請求項48に記載の装置。
【請求項50】
前記第2メモリは、内容参照可能メモリを有する
請求項49に記載の装置。
【請求項51】
前記少なくとも1つのトランスポートレベルフィールドは、1つのプロトコル、1つの送信元ポート番号、及び1つの宛先ポート番号を持つ
請求項49に記載の装置。
【請求項52】
前記第2メモリに記憶される前記第2データ構造は、少なくとも1つのラージビンを含み、前記ラージビンは、1つのフィルタ共通部分に関連する複数のスモールビンの集合を持つ
請求項51に記載の装置。
【請求項53】
前記メモリは少なくとも、1つのSRAM、DRAM、SDRAM、及び1つのDDRDRAMを有する
請求項48に記載の装置。
【請求項54】
前記メモリは、前記プロセッシングデバイスの一部を構成する
請求項48に記載の装置。
【請求項55】
前記セカンダリテーブルのうちの1つは、1つの送信元アドレス空間の全体に広がる1つの送信元アドレスを有する複数の部分指定フィルタに関連し、前記2つのセカンダリテーブルの他方は、1つの宛先アドレス空間の全体に広がる1つの宛先アドレスを有する複数の部分指定フィルタに関連する
請求項48に記載の装置。
【請求項56】
前記送信元アドレス及び宛先アドレスルックアップテーブルのそれぞれの中の前記フィルタタイプは、1つの完全指定フィルタ及び1つの部分指定フィルタのうちの1つを有する
請求項48に記載の装置。
【請求項57】
前記第1データ構造は、
1つのワイドフィルタテーブルであって、前記ワイドフィルタテーブルは複数のエントリを含み、前記複数のエントリのそれぞれが1つのキー及び少なくとも1つのビンポインタを持ち、前記ワイドフィルタのエントリのそれぞれが1つのワイドフィルタ及び1つのインジケータフィルタのうちの1つに関連するワイドフィルタテーブル
をさらに有する
請求項48に記載の装置。
【請求項58】
前記送信元アドレス及び宛先アドレスルックアップデータ構造のそれぞれの中の前記フィルタタイプは、1つの完全指定フィルタ、1つの部分指定フィルタ、及び1つのワイドフィルタのうちの1つを含む
請求項57に記載の装置。
【請求項59】
前記送信元アドレスルックアップデータ構造の中のそれぞれの送信元アドレスプレフィックスは、1つの送信元IP(インターネットプロトコル)アドレスプレフィックスを含み、前記宛先アドレスルックアップデータ構造の中のそれぞれの宛先アドレスプレフィックスは1つの宛先IPアドレスプレフィックスを含む
請求項48に記載の装置。
【請求項60】
前記プライマリテーブルは、全ての起こりうるインジケータフィルタの1つのサブセットのための複数のエントリを含む
請求項48に記載の装置。
【請求項61】
1つの内容参照可能メモリ(CAM)であって、前記CAMは記憶された複数のビンを有し、前記複数のビンのそれぞれが複数のフィールドの複数のセットを含む内容参照可能メモリと、
CAMに結合された1つのプロセッシングデバイスであって、前記プロセッシングデバイスはパケットのネットワークパスに基づいて1つの結果を決定し、前記複数のビンから、前記結果に対応する少なくとも1つのビンを特定し、前記CAMは、前記少なくとも1つの対応するビンをサーチして、前記パケットにマッチする複数のフィールドの1つのセットを特定するためのものである1つのプロセッシングデバイスと
を備える装置。
【請求項62】
前記CAMはマッチする複数のフィールドの前記セットに関連する1つのアクションを戻し、前記プロセッシングデバイスは前記アクションを実行する
請求項61に記載の装置。
【請求項63】
前記マッチする複数のフィールドのセットは、1つのトランスポートレベルフィールドを含む
請求項61に記載の装置。
【請求項64】
前記プロセッシングデバイスは、前記結果を決定するときに、前記パケットにマッチする1つの最適フィルタを特定する
請求項61に記載の装置。
【請求項65】
1つの装置によってアクセスされた場合に、前記装置に、
1つの受信されたパケットの1つのネットワークパスに基づいて1つの結果を決定させ、
前記結果に対応する少なくとも1つのビンを複数のビンから特定させ、前記複数のビンのそれぞれは複数のフィールドの複数のセットを有し、
前記少なくとも1つの対応するビンをサーチさせ、前記パケットにマッチする複数のフィールドの1つのセットを特定させる
内容を提供する1つの機械可読メディア
を備える製品。
【請求項66】
前記内容は、アクセスされた場合に、前記装置にさらに、
複数のマッチするフィールドの前記セットに関連する1つのアクションを特定させ、
前記アクションを前記パケットに適用させる
請求項65に記載の製品。
【請求項67】
複数のマッチするフィールドの前記セットは1つのトランスポートレベルフィールドを有する
請求項65に記載の製品。
【請求項68】
前記内容は、アクセスされた場合に、前記装置にさらに、
前記結果を決定するときに、前記パケットにマッチする1つの最適フィルタを特定させる
請求項65に記載の製品。
【請求項69】
前記パケットの前記ネットワークパスは、1つの送信元アドレス及び1つの宛先アドレスで表される
請求項68に記載の製品。
【請求項70】
前記内容は、アクセスされた場合に、マッチする前記1つの最適フィルタを特定する場合に、前記装置にさらに、
1つの第1データ構造における1つのルックアップを実行させて、前記パケットの送信元アドレスにマッチする1つのエントリを発見させ、
1つの第2データ構造における1つのルックアップを実行させて、前記パケットの宛先アドレスにマッチする1つのエントリを発見させる
請求項69に記載の製品。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5A】
image rotate

【図5B】
image rotate

【図5C】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11A】
image rotate

【図11B】
image rotate

【図12A】
image rotate

【図12B】
image rotate

【図12C】
image rotate

【図13A】
image rotate

【図13B】
image rotate

【図13C】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16A】
image rotate

【図16B】
image rotate

【図16C】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20A】
image rotate

【図20B】
image rotate

【図20C】
image rotate

【図21】
image rotate


【公表番号】特表2007−509535(P2007−509535A)
【公表日】平成19年4月12日(2007.4.12)
【国際特許分類】
【出願番号】特願2006−535386(P2006−535386)
【出願日】平成16年10月15日(2004.10.15)
【国際出願番号】PCT/US2004/034246
【国際公開番号】WO2005/041503
【国際公開日】平成17年5月6日(2005.5.6)
【出願人】(591003943)インテル・コーポレーション (1,101)
【Fターム(参考)】