(57)【要約】  ２ステージパケット分類のための方法及び装置であり、その２ステージパケット分類スキームは、第１ステージ及び第２ステージを有する。第１分類ステージでは、１つのパケットがパケットのネットワークパスに基づいて分類される。第２分類ステージでは、パケットは、パケットの１以上のトランスポート（又は他の）フィールドに基づいて分類される。最適フィルタマッチング及びトランスポートレベル共有の実施形態も開示され、これらの技術の１つ又は両方が２ステージ分類方法に実装される。
2007509535.tif 000002
【特許請求の範囲】
【請求項１】
１つの受信されたパケットの１つのネットワークパスに基づいて１つの結果を決定する段階と、
前記結果に対応する少なくとも１つのビンを複数のビンから特定する段階であって、前記複数のビンのそれぞれは複数のフィールドの複数のセットを有する段階と、
前記少なくとも１つの対応するビンをサーチして、前記パケットにマッチする複数のフィールドの１つのセットを特定する段階と
を備える方法。
【請求項２】
複数のマッチするフィールドの前記セットに関連する１つのアクションを特定する段階と、
前記アクションを前記パケットに適用する段階と
をさらに備える請求項１に記載の方法。
【請求項３】
複数のマッチするフィールドの前記セットは１つのトランスポートレベルフィールドを有する
請求項１に記載の方法。
【請求項４】
前記結果を決定する段階は、前記パケットにマッチする１つの最適フィルタを特定する段階を有する
請求項１に記載の方法。
【請求項５】
前記パケットの前記ネットワークパスは、１つの送信元アドレス及び１つの宛先アドレスで表される
請求項４に記載の方法。
【請求項６】
前記１つの最適マッチングフィルタを特定する段階は、
１つの第１データ構造における１つのルックアップを実行して前記パケットの送信元アドレスにマッチする１つのエントリを発見する段階と、
１つの第２データ構造における１つのルックアップを実行して前記パケットの宛先アドレスにマッチする１つのエントリを発見する段階と
を含む請求項５に記載の方法。
【請求項７】
１つのパケットを受信する段階であって、前記パケットは、１つの送信元アドレス、１つの宛先アドレス、及び複数の他のフィールドを含む１つのヘッダを有する段階と、
１つのデータ構造内の複数のエントリから、前記パケットの前記送信元アドレスにマッチする１つの送信元アドレスプレフィックスを有する１つのエントリを特定する段階であって、前記マッチするエントリは１つの第１識別子を含む段階と、
他のデータ構造内の複数のエントリから、前記パケットの前記宛先アドレスにマッチする１つの宛先アドレスプレフィックスを有する１つのエントリを特定する段階であって、前記マッチするエントリは１つの第２識別子を含む段階と、
複数のビンから前記第１及び第２識別子に対応する１つのビンを特定する段階であって、前記対応するビンは、複数のトランスポートレベルの複数のセットを含む段階と、
前記パケットヘッダの複数の他のフィールドのうちの少なくとも１つを、対応するビン内の複数のトランスポートレベルフィールドのセットのそれぞれと比較して、複数のトランスポートレベルフィールドの１つのマッチするセットを発見する段階と
を備える方法。
【請求項８】
複数のトランスポートレベルフィールドの前記マッチするセットに関連する１つのアクションを前記受信されたパケットに適用する段階
さらに備える請求項７に記載の方法。
【請求項９】
前記パケットヘッダ内の前記複数の他のフィールドは、１つのプロトコル、１つの送信元ポート番号、及び１つの宛先ポート番号の少なくとも１つを有する
請求項７に記載の方法。
【請求項１０】
前記パケットヘッダの前記送信元アドレスは１つの送信元ＩＰ（インターネットプロトコル）アドレスを有し、前記パケットヘッダの前記宛先アドレスは１つの宛先ＩＰアドレスを有する
請求項９に記載の方法。
【請求項１１】
１つのパケットを受信する段階であって、前記パケットは、１つの送信元アドレス、１つの宛先アドレス、及び複数のトランスポートレベルフィールドを含む１つのヘッダを有する段階と、
１つの送信元アドレスデータ構造をサーチして、１つの第１インデックス及び１つの第３インデックスを発見する段階であって、前記第１インデックスは、前記パケットの前記送信元アドレスにマッチする１つの送信元プレフィックスを有する１つの完全指定フィルタと関連し、前記第３インデックスは、前記パケットの前記送信元アドレスにマッチする１つの送信元プレフィックスを有する１つの部分指定フィルタと関連する段階と、
１つの宛先アドレスデータ構造をサーチして、１つの第２インデックス及び１つの第４インデックスを発見する段階であって、前記第２インデックスは、前記パケットの前記宛先アドレスにマッチする１つの宛先プレフィックスを有する１つの完全指定フィルタと関連し、前記第４インデックスは、前記パケットの前記宛先アドレスにマッチする１つの宛先プレフィックスを有する１つの部分指定フィルタと関連する段階と、
前記第１及び第２インデックスから１つのキーを形成する段階と、
前記キーにマッチする１つのエントリについて１つのプライマリテーブルをサーチする段階であって、前記プライマリテーブルは複数のエントリを有し、それぞれのエントリは、１つの完全指定フィルタ、１つの完全指定フィルタの共通部分、及び１つのインジケータフィルタのうちの１つに対応する段階と、
マッチする１つのエントリが前記プライマリテーブルに発見された場合、前記マッチするエントリに関連する複数のビンポインタの１つのリストにアクセスする段階であって、前記リストのそれぞれのビンポインタは、複数のトランスポートレベルフィールドの複数のセットを有する１つのビンを特定する段階と
を備える方法。
【請求項１２】
前記プライマリテーブルのマッチするエントリ内の前記複数のビンポインタのうちの１つによって特定される複数のビンのうちの１つにアクセスする段階と、
前記パケットの前記複数のトランスポートレベルフィールドを前記アクセスされたビン内の複数のトランスポートレベルフィールドのセットのそれぞれと比較する段階と、
前記パケットの複数のトランスポートレベルフィールドとマッチする複数のトランスポートレベルフィールドの１つのセットを前記アクセスされたビンが有する場合に、前記マッチする複数のトランスポートレベルフィールドのセットに関連する１つのアクションを前記受信されたパケットに適用する段階と
をさらに備える請求項１１に記載の方法。
【請求項１３】
前記第３インデックスにマッチする１つのエントリについて２つのセカンダリテーブルのうちの第１セカンダリテーブルをサーチする段階であって、前記第１セカンダリテーブルは複数のエントリを有し、それぞれのエントリは１つの部分指定フィルタに対応する段階と、
前記第４インデックスにマッチする１つのエントリについて２つのセカンダリテーブルのうちの第２セカンダリテーブルをサーチする段階であって、前記第２セカンダリテーブルは複数のエントリを有し、それぞれのエントリは１つの部分指定フィルタに対応する段階と、
前記プライマリテーブルにマッチが発見されず、１つのマッチするエントリが前記２つのセカンダリテーブルのうちの１つに発見された場合に、前記マッチするエントリに関連する複数のビンポインタの１つのリストにアクセスする段階であって、前記リストのビンポインタのそれぞれは、複数のトランスポートレベルフィールドの複数のセットを有する１つのビンを特定する段階と
をさらに備える請求項１１に記載の方法。
【請求項１４】
前記１つのセカンダリテーブルのマッチしているエントリ内の複数のビンポインタのうちの１つによって特定される複数のビンのうちの１つにアクセスする段階と、
前記パケットの前記複数のトランスポートレベルフィールドを、前記アクセスされたビン内の複数のトランスポートレベルフィールドのセットのそれぞれと比較する段階と、
前記パケットの前記複数のトランスポートレベルフィールドとマッチする複数のトランスポートレベルフィールドの１つのセットを前記アクセスされたビンが有する場合に、前記マッチする複数のトランスポートレベルフィールドのセットに関連する１つのアクションを前記受信されたパケットに適用する段階と
をさらに備える請求項１３に記載の方法。
【請求項１５】
前記セカンダリテーブルのいずれにもマッチが発見されない場合に、１つのデフォルトエントリに関連する複数のビンポインタの１つのリストにアクセスする段階であって、前記リストのビンポインタのそれぞれは、複数のトランスポートレベルフィールドの複数のセットを有する１つのビンを特定する段階
をさらに備える請求項１３に記載の方法。
【請求項１６】
前記デフォルトエントリは、２次元アドレス空間全体に対応する
請求項１５に記載の方法。
【請求項１７】
前記送信元アドレスデータ構造をサーチして、前記パケットの送信元アドレスにマッチする１つの送信元プレフィックスを有する１つのワイドフィルタに関連する１つの第５インデックスを発見する段階と、
前記宛先アドレスデータ構造をサーチして、前記パケットの宛先アドレスにマッチする１つの宛先プレフィックスを有する１つのワイドフィルタに関連する１つの第６インデックスを発見する段階と、
前記第５及び第６インデックスから１つの第２キーを形成する段階と、
前記第２キーとマッチする１つのエントリについて１つのワイドフィルタテーブルをサーチする段階であって、前記ワイドフィルタテーブルは複数のエントリを有し、それぞれのエントリは１つのワイドフィルタに対応する段階と、
前記プライマリテーブルにマッチが発見されず、１つのマッチするエントリが前記ワイドフィルタテーブルに発見された場合に、前記ワイドフィルタテーブル内の前記マッチするエントリに関連する複数のビンポインタの１つのリストにアクセスする段階であって、前記リストのビンポインタのそれぞれは、複数のトランスポートレベルフィールドの複数のセットを有する１つのビンを特定する段階と
をさらに備える請求項１１に記載の方法。
【請求項１８】
前記ワイドフィルタテーブルのマッチするエントリ内の前記複数のビンポインタのうちの１つによって特定される前記複数のビンのうちの１つにアクセスする段階と、
前記パケットの前記複数のトランスポートレベルフィールドを、前記アクセスされたビン内の複数のトランスポートレベルフィールドのセットのそれぞれと比較する段階と、
前記パケットの前記複数のトランスポートレベルフィールドとマッチする複数のトランスポートレベルフィールドの１つのセットを前記アクセスされたビンが有する場合に、前記マッチする複数のトランスポートレベルフィールドのセットに関連する１つのアクションを前記受信されたパケットに適用する段階と
をさらに備える請求項１７に記載の方法。
【請求項１９】
前記ワイドフィルタテーブルに含まれるそれぞれのワイドフィルタは、１つの指定された閾値を超える複数のインジケータフィルタを持つ１つの完全指定フィルタを有する
請求項１７に記載の方法。
【請求項２０】
前記受信されたパケット内の前記複数のトランスポートレベルフィールドは、１つの送信元ポート番号、１つの宛先ポート番号、１つのプロトコルの少なくとも１つを有する
請求項１１に記載の方法。
【請求項２１】
１つのパケット分類データベースの複数のルールを複数のルールセットにグループ化する段階であって、それぞれのルールセットは、１つの送信元及び宛先アドレスペアを持つ複数のルールを有し、それぞれのルールセットは、前記送信元及び宛先アドレスペアに対応する１つのフィルタに関連する段階と、
１つのスモールビンを前記複数のフィルタのそれぞれと関連づける段階であって、それぞれのスモールビンは複数のトランスポートレベルフィールドの複数のセットの１つのグループを有し、前記グループ内の複数のトランスポートレベルフィールドのセットのそれぞれは、前記関連するルールセット内の前記複数のルールのうちの１つに関連する段階と
を備える方法。
【請求項２２】
前記複数のフィルタの少なくとも２つは同じ１つのスモールビンに関連する
請求項２１に記載の方法。
【請求項２３】
複数のフィルタ共通部分を特定する段階であって、それぞれのフィルタ共通部分は前記複数のフィルタのうちの少なくとも２つのフィルタの１つの共通部分に対応する段階
をさらに備える請求項２１に記載の方法。
【請求項２４】
１つのラージビンを前記複数のフィルタ共通部分のそれぞれと関連づける段階であって、それぞれのフィルタ共通部分の前記ラージビンは、少なくとも２つの前記共通部分のフィルタのそれぞれに関連する前記複数のスモールビンの１つの集合を有する段階と
をさらに備える請求項２３に記載の方法。
【請求項２５】
複数のインジケータフィルタを特定する段階であって、それぞれのインジケータフィルタは、前記複数のフィルタのうちの１つのフィルタの１つの送信元アドレス及び前記複数のフィルタのうちの他の１つのフィルタの前記宛先アドレスから形成される段階
をさらに備える請求項２４に記載の方法。
【請求項２６】
前記分類データベースに関連する前記複数のフィルタは、複数の完全指定フィルタ、送信元アドレス空間の全体に広がる複数の部分指定フィルタ、及び宛先アドレス空間の全体に広がる部分指定フィルタを有する
請求項２５に記載の方法。
【請求項２７】
複数のエントリを有する１つのプライマリテーブルを生成する段階であって、前記プライマリテーブルのエントリのそれぞれは、前記複数の完全指定フィルタのうちの１つ、前記複数のフィルタ共通部分のうちの１つ、又は前記複数のインジケータフィルタのうちの１つに関連し、前記プライマリテーブルのエントリのそれぞれは、１つのキー及び当該エントリの前記対応するフィルタに関連する前記スモールビンへのポインタの少なくとも１つを有する段階と、
複数のエントリを有する１つの第１セカンダリテーブルを生成する段階であって、前記第１セカンダリテーブルのエントリのそれぞれは、前記送信元アドレス空間の全体に広がる１つの送信元アドレスを持つ前記複数の部分指定フィルタのうちの１つに関連し、前記第１セカンダリテーブルのエントリのそれぞれは、１つのキー及び当該エントリの前記対応するフィルタに関連する前記スモールビンへの１つのポインタを有する段階と、
複数のエントリを有する１つの第２セカンダリテーブルを生成する段階であって、前記第２セカンダリテーブルのエントリのそれぞれは、前記宛先アドレス空間の全体に広がる１つの宛先アドレスを持つ前記複数の部分指定フィルタのうちの１つに関連し、前記第２セカンダリテーブルのエントリのそれぞれは、１つのキー及び当該エントリの前記対応するフィルタに関連する前記スモールビンへの１つのポインタを有する段階と
をさらに備える請求項２６に記載の方法。
【請求項２８】
前記プライマリテーブルの１つのエントリ内の前記少なくとも１つのポインタは、当該エントリの対応する１つのフィルタ共通部分に関連する１つのラージビンを特定する
請求項２７に記載の方法。
【請求項２９】
前記プライマリテーブルは、複数のインジケータフィルタの１つのサブセットを有する
請求項２７に記載の方法。
【請求項３０】
前記分類データベースに関連する前記複数のフィルタは、複数のワイドフィルタをさらに有する
請求項２７に記載の方法。
【請求項３１】
複数のエントリを有する１つのワイドフィルタテーブルを生成する段階であって、前記ワイドフィルタテーブルのエントリのそれぞれは前記複数のワイドフィルタのうちの１つに関連し、前記ワイドフィルタテーブルのエントリのそれぞれは１つのキー及び当該エントリの前記対応するフィルタに関連する前記スモールビンへの１つのポインタを有する段階
をさらに備える請求項３０に記載の方法。
【請求項３２】
１つの送信元アドレスデータ構造を生成する段階であって、前記送信元アドレスデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれは、前記複数のフィルタのうちの１つに対応する１つの送信元プレフィックスを含む段階と、
１つの宛先アドレスデータ構造を生成する段階であって、前記宛先アドレスデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれは、前記複数のフィルタのうちの１つに対応する１つの宛先プレフィックスを含む段階と
をさらに備える請求項２１に記載の方法。
【請求項３３】
複数のフィルタであって、それぞれのフィルタが１つの送信元アドレスプレフィックス及び１つの宛先アドレスプレフィックスを有する複数のフィルタと、
複数のビンであって、それぞれのビンは複数のトリプレットを有し、それぞれのトリプレットが少なくとも１つのトランスポートレベルフィールド、１つのアクション、及び１つのプライオリティを含む複数のビンと
を備え、
複数のフィルタのそれぞれは、前記複数のビンのうちの少なくとも１つに関連するデータ構造。
【請求項３４】
前記複数のビンのうちの１つは、前記複数のフィルタの少なくとも２つに関連する
請求項３３に記載のデータ構造。
【請求項３５】
前記送信元アドレスプレフィックスは１つの送信元ＩＰ（インターネットプロトコル）アドレスプレフィックスを含み、前記宛先アドレスプレフィックスは１つの宛先ＩＰアドレスプレフィックスを含む
請求項３３に記載のデータ構造。
【請求項３６】
前記少なくとも１つのトランスポートレベルフィールドは、１つのプロトコル、１つの送信元ポート番号、及び１つの宛先ポート番号のうちの少なくとも１つを含む
請求項３３に記載のデータ構造。
【請求項３７】
前記複数のビンの少なくともいくつかのそれぞれは、１つのスモールビンを有する
請求項３３に記載のデータ構造。
【請求項３８】
前記複数のビンの少なくとも１つは１つのラージビンを有し、前記ラージビンは１つのフィルタ共通部分に関連する前記複数のスモールビンの１つの集合を含む
請求項３７に記載のデータ構造。
【請求項３９】
１つの送信元アドレスデータ構造であって、前記送信元アドレスデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれが１つの送信元プレフィックス、１つのフィルタタイプ、及び１つのインデックスを含む送信元アドレスデータ構造と、
１つの宛先アドレスデータ構造であって、前記宛先アドレスデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれが１つの宛先プレフィックス、１つのフィルタタイプ、及び１つのインデックスを含む宛先アドレスデータ構造と、
１つのプライマリテーブルであって、前記プライマリテーブルは複数のエントリを有し、前記複数のエントリのそれぞれが１つのキー及び少なくとも１つのビンポインタを含み、前記複数のエントリのそれぞれが１つの完全指定フィルタ、１つの完全指定フィルタ共通部分、及び１つのインジケータフィルタのうちの１つに関連するプライマリテーブルと、
２つのセカンダリテーブルであって、前記セカンダリテーブルのそれぞれは複数のエントリを有し、前記複数のエントリのそれぞれが１つのキー及び少なくとも１つのビンポインタを含み、前記２つのセカンダリテーブルのそれぞれのエントリのそれぞれが１つの部分指定フィルタに関連する２つのセカンダリテーブルと
を備えるデータ構造。
【請求項４０】
前記セカンダリテーブルのうちの１つは、１つの送信元アドレス空間の全体に広がる１つの送信元アドレスを有する複数の部分指定フィルタに関連し、前記２つのセカンダリテーブルの他方は、１つの宛先アドレス空間の全体に広がる１つの宛先アドレスを有する複数の部分指定フィルタに関連する
請求項３９に記載のデータ構造。
【請求項４１】
前記送信元アドレス及び宛先アドレスルックアップテーブルのそれぞれの中の前記フィルタタイプは、１つの完全指定フィルタ及び１つの部分指定フィルタのうちの１つを示す
請求項３９に記載のデータ構造。
【請求項４２】
１つのワイドフィルタテーブルであって、前記ワイドフィルタテーブルは複数のエントリを有し、前記複数のエントリのそれぞれが１つのキー及び少なくとも１つのビンポインタを含み、前記ワイドフィルタのエントリのそれぞれが１つのワイドフィルタに関連するワイドフィルタテーブル
をさらに備える請求項３９に記載のデータ構造。
【請求項４３】
前記送信元アドレス及び宛先アドレスルックアップテーブルのそれぞれの中の前記フィルタタイプは、１つの完全指定フィルタ、１つの部分指定フィルタ、及び１つのワイドフィルタのうちの１つを示す
請求項４２に記載のデータ構造。
【請求項４４】
前記プライマリ及びセカンダリテーブルの前記複数のエントリの中の前記複数のビンポインタのそれぞれは、１つの第２データ構造の複数のビンのうちの１つを特定し、それぞれのビンは複数のトリプレットを有し、それぞれのトリプレットは少なくとも、１つのトランスポートレベルフィールド、１つのアクション、及び１つのプライオリティを含む
請求項３９に記載のデータ構造。
【請求項４５】
前記送信元アドレスデータ構造の中のそれぞれの送信元アドレスプレフィックスは、１つの送信元ＩＰ（インターネットプロトコル）アドレスプレフィックスを含み、前記宛先アドレスデータ構造の中のそれぞれの宛先アドレスプレフィックスは１つの宛先ＩＰアドレスプレフィックスを含む
請求項４４に記載のデータ構造。
【請求項４６】
前記少なくとも１つのトランスポートレベルフィールドは、１つのプロトコル、１つの送信元ポート番号、及び１つの宛先ポート番号のうちの１つを含む
請求項４５に記載のデータ構造。
【請求項４７】
前記プライマリテーブルは、全ての起こりうるインジケータフィルタの１つのサブセットのための複数のエントリを有する
請求項３９に記載のデータ構造。
【請求項４８】
１つのプロセッシングデバイスと、
前記プロセッシングデバイスに結合された１つのメモリであって、前記メモリは記憶された１つの第１データ構造を有するメモリと
を備える装置であって、
前記第１データ構造は、
１つの送信元アドレスルックアップデータ構造であって、前記送信元アドレスルックアップデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれが１つの送信元プレフィックス、１つのフィルタタイプ、及び１つのインデックスを含む１つの送信元アドレスルックアップデータ構造と、
１つの宛先アドレスルックアップデータ構造であって、前記宛先アドレスルックアップデータ構造は複数のエントリを有し、前記複数のエントリのそれぞれが１つの宛先プレフィックス、１つのフィルタタイプ、及び１つのインデックスを含む１つの宛先アドレスルックアップデータ構造と、
１つのプライマリテーブルであって、前記プライマリテーブルは複数のエントリを有し、前記複数のエントリのそれぞれは１つのキー及び少なくとも１つのビンポインタを含み、前記複数のエントリのそれぞれが１つの完全指定フィルタ、１つの完全指定フィルタ共通部分、及び１つのインジケータフィルタのうちの１つに関連する１つのプライマリテーブルと、
２つのセカンダリテーブルであって、前記セカンダリテーブルのそれぞれは複数のエントリを有し、前記複数のエントリのそれぞれは１つのキー及び少なくとも１つのビンポインタを含み、前記２つのセカンダリテーブルのそれぞれのエントリのそれぞれが１つの部分指定フィルタに関連する２つのセカンダリテーブルと
を有する装置。
【請求項４９】
前記プロセッシングデバイスに結合された１つの第２メモリであって、前記第２メモリは記憶された１つの第２データ構造を有し、前記第２データ構造が複数のスモールビンを含み、それぞれのスモールビンが複数のトリプレットを持ち、それぞれのトリプレットが少なくとも、１つのトランスポートレベルフィールド、１つのアクション、及び１つのプライオリティを持つ第２メモリ
をさらに備え、
前記プライマリ及びセカンダリテーブルの前記複数のエントリの中の前記複数のビンポインタのそれぞれは、前記第２データ構造の前記複数のスモールビンのうちの１つを特定する
請求項４８に記載の装置。
【請求項５０】
前記第２メモリは、内容参照可能メモリを有する
請求項４９に記載の装置。
【請求項５１】
前記少なくとも１つのトランスポートレベルフィールドは、１つのプロトコル、１つの送信元ポート番号、及び１つの宛先ポート番号を持つ
請求項４９に記載の装置。
【請求項５２】
前記第２メモリに記憶される前記第２データ構造は、少なくとも１つのラージビンを含み、前記ラージビンは、１つのフィルタ共通部分に関連する複数のスモールビンの集合を持つ
請求項５１に記載の装置。
【請求項５３】
前記メモリは少なくとも、１つのＳＲＡＭ、ＤＲＡＭ、ＳＤＲＡＭ、及び１つのＤＤＲＤＲＡＭを有する
請求項４８に記載の装置。
【請求項５４】
前記メモリは、前記プロセッシングデバイスの一部を構成する
請求項４８に記載の装置。
【請求項５５】
前記セカンダリテーブルのうちの１つは、１つの送信元アドレス空間の全体に広がる１つの送信元アドレスを有する複数の部分指定フィルタに関連し、前記２つのセカンダリテーブルの他方は、１つの宛先アドレス空間の全体に広がる１つの宛先アドレスを有する複数の部分指定フィルタに関連する
請求項４８に記載の装置。
【請求項５６】
前記送信元アドレス及び宛先アドレスルックアップテーブルのそれぞれの中の前記フィルタタイプは、１つの完全指定フィルタ及び１つの部分指定フィルタのうちの１つを有する
請求項４８に記載の装置。
【請求項５７】
前記第１データ構造は、
１つのワイドフィルタテーブルであって、前記ワイドフィルタテーブルは複数のエントリを含み、前記複数のエントリのそれぞれが１つのキー及び少なくとも１つのビンポインタを持ち、前記ワイドフィルタのエントリのそれぞれが１つのワイドフィルタ及び１つのインジケータフィルタのうちの１つに関連するワイドフィルタテーブル
をさらに有する
請求項４８に記載の装置。
【請求項５８】
前記送信元アドレス及び宛先アドレスルックアップデータ構造のそれぞれの中の前記フィルタタイプは、１つの完全指定フィルタ、１つの部分指定フィルタ、及び１つのワイドフィルタのうちの１つを含む
請求項５７に記載の装置。
【請求項５９】
前記送信元アドレスルックアップデータ構造の中のそれぞれの送信元アドレスプレフィックスは、１つの送信元ＩＰ（インターネットプロトコル）アドレスプレフィックスを含み、前記宛先アドレスルックアップデータ構造の中のそれぞれの宛先アドレスプレフィックスは１つの宛先ＩＰアドレスプレフィックスを含む
請求項４８に記載の装置。
【請求項６０】
前記プライマリテーブルは、全ての起こりうるインジケータフィルタの１つのサブセットのための複数のエントリを含む
請求項４８に記載の装置。
【請求項６１】
１つの内容参照可能メモリ（ＣＡＭ）であって、前記ＣＡＭは記憶された複数のビンを有し、前記複数のビンのそれぞれが複数のフィールドの複数のセットを含む内容参照可能メモリと、
ＣＡＭに結合された１つのプロセッシングデバイスであって、前記プロセッシングデバイスはパケットのネットワークパスに基づいて１つの結果を決定し、前記複数のビンから、前記結果に対応する少なくとも１つのビンを特定し、前記ＣＡＭは、前記少なくとも１つの対応するビンをサーチして、前記パケットにマッチする複数のフィールドの１つのセットを特定するためのものである１つのプロセッシングデバイスと
を備える装置。
【請求項６２】
前記ＣＡＭはマッチする複数のフィールドの前記セットに関連する１つのアクションを戻し、前記プロセッシングデバイスは前記アクションを実行する
請求項６１に記載の装置。
【請求項６３】
前記マッチする複数のフィールドのセットは、１つのトランスポートレベルフィールドを含む
請求項６１に記載の装置。
【請求項６４】
前記プロセッシングデバイスは、前記結果を決定するときに、前記パケットにマッチする１つの最適フィルタを特定する
請求項６１に記載の装置。
【請求項６５】
１つの装置によってアクセスされた場合に、前記装置に、
１つの受信されたパケットの１つのネットワークパスに基づいて１つの結果を決定させ、
前記結果に対応する少なくとも１つのビンを複数のビンから特定させ、前記複数のビンのそれぞれは複数のフィールドの複数のセットを有し、
前記少なくとも１つの対応するビンをサーチさせ、前記パケットにマッチする複数のフィールドの１つのセットを特定させる
内容を提供する１つの機械可読メディア
を備える製品。
【請求項６６】
前記内容は、アクセスされた場合に、前記装置にさらに、
複数のマッチするフィールドの前記セットに関連する１つのアクションを特定させ、
前記アクションを前記パケットに適用させる
請求項６５に記載の製品。
【請求項６７】
複数のマッチするフィールドの前記セットは１つのトランスポートレベルフィールドを有する
請求項６５に記載の製品。
【請求項６８】
前記内容は、アクセスされた場合に、前記装置にさらに、
前記結果を決定するときに、前記パケットにマッチする１つの最適フィルタを特定させる
請求項６５に記載の製品。
【請求項６９】
前記パケットの前記ネットワークパスは、１つの送信元アドレス及び１つの宛先アドレスで表される
請求項６８に記載の製品。
【請求項７０】
前記内容は、アクセスされた場合に、マッチする前記１つの最適フィルタを特定する場合に、前記装置にさらに、
１つの第１データ構造における１つのルックアップを実行させて、前記パケットの送信元アドレスにマッチする１つのエントリを発見させ、
１つの第２データ構造における１つのルックアップを実行させて、前記パケットの宛先アドレスにマッチする１つのエントリを発見させる
請求項６９に記載の製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広くコンピュータネットワーキングに関し、特に、パケットを分類する方法及び装置に関する。
【背景技術】
【０００２】
従来、コンピュータネットワークにおけるパケットルーティングは、パケットの宛先アドレスだけに基づいている。このルーティング技術は、一般的に"ベストエフォート"配送であり、同一アドレスに向かう全てのトラフィックは同様に扱われる。しかしながら、宛先アドレスだけに基づいたパケットルーティングは、より広い帯域幅、高められたセキュリティ、並びに増大する柔軟性及びサービス差別化に対する増大する要求に応えるには不十分である。これらの目的に応えることを目的として、機器ベンダ及びサービスプロバイダは、ファイアウォールを通過するルーティング、サービス品質（ＱｏＳ）ベース転送、及び帯域及び／又はリソース予約を含む、より差別化したルーティング形式を提供している。
【０００３】
一般的に、ファイアウォールは、トラフィックの特定のクラス（例えば、"望ましくない"又は"疑わしい"トラフィック）をブロックすることができる、いくつかのコンポーネント、又は複数のコンポーネントの組み合わせを有する。ファイアウォールは、組織ネットワーク及び他の企業ネットワークでしばしば利用され、ファイアウォールは通常、ネットワークの入口及び／又は出口ポイント、すなわち"信頼境界"において実装される。典型的なファイアウォールは、望ましいセキュリティポリシーを実行すべく設計された一連のルール又はフィルタを有する。
【０００４】
ネットワークサービスプロバイダは、それぞれが異なるサービス、サービスプライオリティ、及び価格を必要とする多様な顧客を持つ。異なる顧客に差別化されたサービスを提供することを目的として、すなわち、より一般的には、ネットワークトラフィックの特定のクラスへの望ましい処理を提供することを目的として、機器ベンダは、ＱｏＳベースフォワーディング及び帯域／リソース予約を含む多様なメカニズムを実装してきている。ＱｏＳベースフォワーディングの目標は、異なる顧客及び／又はトラフィックタイプに対するサービス差別化を提供することである。ＱｏＳベースフォワーディングは、例えば、サービスクラスに基づくフォワーディング、特別なキューイングプロシージャ（例えば、プレフローキューイング）、及びフェアスケジューリングメソッドを含んでよい。帯域幅又はリソース予約は、ＱｏＳフォワーディングに密接に関係している。帯域予約は、特定のタイプのトラフィックに対する指定されたバンド幅の予約を含む。例えば、帯域予約は２点間のトラフィックに適用されてよいし、帯域予約は特定のアプリケーション（例えば、マルチメディア、ビデオ等）に関連するトラフィックに適用されてよい。
【０００５】
他のポリシーベースのパケットフォワーディング技術を実行するだけでなく、ネットワークトラフィックのより差別化されたルーティングを提供する上記のルーティング手法（例えば、ファイアウォール、ＱｏＳフォワーディング、帯域予約）を実装することを目的として、パケットを分類する必要がある。全般的に、パケット分類は、異なるフローに属するパケットの間、又は異なるトラフィックタイプに関するパケットの間で弁別する段階を持つ。ここで用いられたように、"フロー"は、少なくともいくつかの共通するヘッダ特性（例えば、２つの特定のアドレスの間を流れる複数のパケット）を共有する一連のパケットである。パケットは、通常、パケットのヘッダ内の１以上のフィールドに基づいて分類される。そのパケットがいずれのフローに一致するか、又はそのパケットがいずれのトラフィックタイプに関するかを特定すべく、１以上のルールがヘッダ情報に適用される。
【０００６】
パケット分類ルールは、多くは、関連するプライオリティ及びアクションだけでなく受信したパケットのヘッダ内の多くの対応する複数のフィールドに対して比較される、いくつかのフィールドを含む。分類データベースを形成する複数のルールのセットは優先順位づけされたリストで編成されてよく、より高いプライオリティを持つルールがより低いプライオリティを持つルールより優先される。パケットが受信されたとき、当該パケットに適用されるべき最もプライオリティの高いアクションを決定すべく、当該パケットの複数の内容（例えば、特定の複数のヘッダフィールド）が分類データベースの中の各ルールと比較される。
【０００７】
ハッシュ方式、ビットパラレズム技術、及び内容参照可能メモリ（ＣＡＭ）を用いた実装を含む、ヘッダデータに基づいてパケット分類を実行するための多くの方法−ハードウェア及びソフトウェア実装の両方−は、当業者に知られている。ハッシュ法は、ルールのそれぞれのフィールドにおいて用いられるビットマスクに応じたルールのグループを生成し、ルールのグループのそれぞれは１つのハッシュテーブル（又は複数のハッシュテーブル）によって表現される。受信されたパケットとマッチしている１つのルールを特定することは、ハッシュテーブル上の一連のルックアップを要する。
【０００８】
ビットパラレリズムは、n次元分類問題を、それぞれ１次元の複数のステージに分割する。それぞれは、ビットベクトルは、システムに記憶されたルールの数に等しい長さを持ち、ビットベクトルにおける１つのビットは、当該ビットに対応するルールが受信されたパケットの適切なフィールドとマッチする値の範囲を示す場合にセットされる。全ての戻されたビットベクトルにおいてセットされたそれらのビットを持つルールは受信されたパケットとマッチする。標準的なビットパラレリズムスキームにおける改良は、集合ビットベクトル（ＡＢＶ）法である。ＡＢＶ法において、それぞれの"フル"ビットベクトルは圧縮されて、より小サイズのビットセット（"集合ビットベクトル"と呼ぶ）として表される。集合ビットベクトルにおけるそれぞれのビットは、フルビットベクトルからのビットのグループを表し、集合ビットベクトルにおける１つのビットは、（フルビットベクトルにおける）関連するビットのグループの中の少なくとも１つのビットがセットされた場合にセットされる。
【０００９】
ＣＡＭ実装においては、ＣＡＭエントリのそれぞれは、１つの値及び１つのビットマスクに関連する。当該値は１つのルールの１以上のフィールドを含み、当該ビットマスクは、サーチキーのビットのいずれが、そのキーが当該値に対して比較されるときに考慮されるかを指定する。ＣＡＭユニット−サーチキーを複数のエントリに対して同時に比較する能力を有してよい−は、最も高いプライオリティでマッチしているエントリに関連する１つのインデックスを戻し、このインデックスはパケットに対するアクションを特定するために使用される。
【００１０】
ファクタの数は、要求される多数のメモリアクセス、大きい記憶容量要件、及び（少なくともＣＡＭ実装について）著しい電力消費を含む、上記の分類スキームのパフォーマンスにインパクトを与える。他のファクタだけでなく帯域幅及びメモリオーバヘッドによって、これらのパケット分類技術は、分類データベースサイズの増大だけでなくリンク速度の進歩に追随すべく取り組み、パケット分類は高速リンク（例えば、ギガビット容量）をサポートしているルータにおけるボトルネックになり得る。
【図面の簡単な説明】
【００１１】
【図１】１つのルータを備えるネットワークの一実施形態を示す概略図である。
【００１２】
【図２】図１に示されたルータの一実施形態を示す概略図である。
【００１３】
【図３】図２に示されたプロセッシングデバイスの一実施形態を示す概略図である。
【００１４】
【図４】１つの典型的なパケットの構成を示す概略図である。
【００１５】
【図５Ａ】パケット分類ルールの一実施形態を示す概略図である。
【図５Ｂ】パケット分類ルールの一実施形態を示す概略図である。
【図５Ｃ】パケット分類ルールの一実施形態を示す概略図である。
【００１６】
【図６】２ステージパケット分類部の一実施形態を示す概略図である。
【００１７】
【図７】２ステージパケット分類のための方法の一実施形態を示すブロック図である。
【００１８】
【図８】分類データベースの具体例の一部を示す概略図である。
【００１９】
【図９】２ステージパケット分類のための方法の他の一実施形態を示すブロック図である。
【００２０】
【図１０】複数のルールを持つ分類データベースの一実施形態を示す概略図である。
【００２１】
【図１１Ａ】複数のルールセットへの分類データベースの構成の一実施形態を示す概略図である。
【図１１Ｂ】複数のルールセットへの分類データベースの構成の一実施形態を示す概略図である。
【００２２】
【図１２Ａ】２つの部分的に重なるフィルタの一実施形態を示す概略図である。
【図１２Ｂ】２つの部分的に重なるフィルタの一実施形態を示す概略図である。
【図１２Ｃ】２つの部分的に重なるフィルタの一実施形態を示す概略図である。
【００２３】
【図１３Ａ】２つの完全に重なるフィルタの一実施形態を示す概略図である。
【図１３Ｂ】２つの完全に重なるフィルタの一実施形態を示す概略図である。
【図１３Ｃ】２つの完全に重なるフィルタの一実施形態を示す概略図である。
【００２４】
【図１４】送信元及び宛先アドレス空間内の２つのパラレルなルックアップの一実施形態を示す概略図である。
【００２５】
【図１５】分類データベースのフィルタからの非存在フィルタの構成を示す概略図である。
【００２６】
【図１６Ａ】第１分類ステージデータ構造の一実施形態を示す概略図である。
【００２７】
【図１６Ｂ】パラレル最長プレフィックスマッチルックアップテーブルの一実施形態を示す概略図である。
【００２８】
【図１６Ｃ】図１６Ａのプライマリルックアップテーブルの一実施形態を示す概略図である。
【００２９】
【図１７】第２分類ステージデータ構造の一実施形態を示す概略図である。
【００３０】
【図１８】最適フィルタママッチング及びトランスポートレベル共有を使用した２ステージパケット分類のための方法の一実施形態を示すブロック図である。
【００３１】
【図１９】ワイドフィルタを含むフィルタデータベースの一実施形態を示す概略図である。
【００３２】
【図２０Ａ】第１分類ステージデータ構造の他の一実施形態を示す概略図である。
【００３３】
【図２０Ｂ】パラレル最長プレフィックスマッチルックアップテーブルの他の一実施形態を示す概略図である。
【００３４】
【図２０Ｃ】最適フィルタママッチング及びトランスポートレベル共有を使用した２ステージパケット分類に係る方法の一実施形態を示すブロック図である。
【００３５】
【図２１】２ステージパケット分類データ構造を生成及び更新する方法の一実施形態を示すブロック図である。
【発明を実施するための最良の形態】
【００３６】
パケット分類部の複数の実施形態がここに開示される。開示されたパケット分類部の複数の実施形態は、パケット転送部（例えば、ファイアウォール、ＱｏＳベースのフォワーダ）を実装しているルータに関連して以下に記載される。一方で、開示された複数の実施形態は用途において制限されず、さらには、続く本文及び図面で記載されるパケット分類部の実施形態は一般的に、パケットの分類又は他の通信が必要とされるデバイス、システム、及び／又は環境のいずれにも適用可能であるということが理解されるべきである。
【００３７】
ネットワーク１００の一実施形態を図１に示す。ネットワーク１００は、パケット転送部２０１を有するルータ２００を備える。ルータ２００（及びパケット転送部２０１）は、他の望ましいセキュリティベースのフォワーディングスキームだけでなく、特定のセキュリティポリシー、ＱｏＳフォワーディング、及び／又はリソース予約を実装してよい。ルータ２００は、異なるフローに属するパケット及び／又は異なるトラフィックタイプに関連するパケットを区別すべく、望ましいフォワーディングポリシーを実装すべく設計されたルールセットを持つ１つのパケット分類部６００も有してよい。パケット分類部６００の実施形態は以下により詳細に説明される。（パケット転送部２０１及びパケット分類部６００だけでなく）ルータ２００は、適切な任意のコンピューティングシステム或いはデバイス（又はデバイスの組み合わせ）上に実装されてよい。ルータ２００の一実施形態は、図２及び添付の本文に関連して以下に説明される。ルータ２００は、明確さ及び理解し易さを目的として図１から省略された他のコンポーネント（例えば、スケジューラ、トラフィックマネージャ等）を有してよいことが理解されるべきである。
【００３８】
ルータ２００は、複数のリンク１３０−リンク１３０ａ、１３０ｂ、・・・１３０ｎ−を介して、多くのノード１１０及び／又は多くのサブネット１２０と結合されている。ノード１１０は任意のアドレス可能なデバイスを有する。例えば、ノード１１０は、サーバ、デスクトップコンピュータ、ラップトップコンピュータ、又はハンドヘルドコンピューティングデバイス（例えば、情報携帯端末、すなわちＰＤＡ）のような、コンピュータシステム又は他のコンピューティングデバイスを有してよい。サブネット１２０は、他のノードの集合を有してよく、サブネット１２０は、他のルータ又はスイッチも有してよい。リンク１３０ａ−ｎのそれぞれは、任意の適切なプロトコル−例えばＴＣＰ／ＩＰ（トランスミッション・コントロール・プロトコル／インターネットプロトコル）、ＨＴＴＰ（ハイパーテクスト転送プロトコル）、その他−を通じた情報交換をサポートしている任意の適切な媒体−例えば、無線、銅線、光ファイバ、又はそれらの組み合わせ−を通じて確立される。
【００３９】
ネットワーク１００は、ローカルエリアネットワーク（ＬＡＮ）、大都市圏ネットワーク（ＭＡＮ）、広域ネットワーク（ＷＡＮ）のような任意のタイプのネットワークを有してよい。ルータ２００は、例えばインターネット及び／又は他のＬＡＮ、ＭＡＮ、ＬＡＮ、又はＷＬＡＮを介して、ネットワーク１００を他のネットワーク（又は複数のネットワーク）５に結合してもよい。ルータ２００は、任意の適切なプロトコル（例えば、ＴＣＰ／ＩＰ、ＨＴＴＰ等）を用いた、無線、銅線、及び／又は光ファイバ接続を含む任意の適切な媒体を介して他のネットワーク５に接続されてよい。
【００４０】
図１に示されたネットワーク１００は、そのようなシステムの実施形態の一例を示すことが目的とされており、さらには、ネットワーク１００は任意の適切な構成を有してよいことが理解されるべきである。例えば、ネットワーク１００は、理解し易さのために図１から省略された追加のノード１１０、サブネット１２０、及び／又は他のデバイス（例えば、スイッチ、ルータ、ハブ等）を備えてよい。さらに、ネットワーク１００は、図１に示されたコンポーネントの全てを含まなくてよいことが理解されるべきである。
【００４１】
他の実施形態では、ルータ２００は、パケット分類部６００が（ハードウェア、ソフトウェア、或いはハードウェア及びソフトウェアの組み合わせで）実装され得る任意の適切なコンピューティングデバイスを有してよい。そのようなコンピューティングシステムの一実施形態が図２に示される。
【００４２】
図２を参照すると、ルータ２００は、様々なコンポーネントが結合されたバス２０５を有する。バス２０５は、ルータ２００のコンポーネントを相互に接続する１以上のバス−例えば、システムバス、ペリフェラルコンポーネントインタフェース（ＰＣＩ）バス、スカジー（ＳＣＳＩ）バス等−の集合を示すことが意図されている。これらのバスを１つのバス２０５として表すことは理解し易くすることを目的として提供されており、ルータ２００はそのように限定されないことが理解されるべきである。当業者は、ルータ２００が任意の適切なバスアーキテクチャを有し、任意の数及び組み合わせのバスを有してよいことを理解し得る。
【００４３】
プロセッシングデバイス（又は複数のデバイス）３００がバス２０５に結合されている。プロセッシングデバイス３００は、マイクロプロセッサ、ネットワークプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールド・プログラマブル・ゲートアレイ（ＦＰＧＡ）、又は類似のデバイスを含む任意の適切なプロセッシングデバイス又はシステムを含んでよい。プロセッシングデバイス３００の一実施形態は、図３及び付随する本文で以下に説明される。図２は１つのプロセッシングデバイス３００を示すが、ルータ２００は２以上のプロセッシングデバイスを含み得ることが理解されるべきである。
【００４４】
ルータ２００は、バス２０５に結合されたシステムメモリ２１０も含んでよい。システムメモリ２１０は、例えば、スタティックランダムアクセスメモリ（ＳＲＡＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、シンクロナスＤＲＡＭ（ＳＤＲＡＭ）、又はダブルデータレートＤＲＡＭ（ＤＤＲＤＲＡＭ）のような任意の適切なタイプ及び数のランダムアクセスメモリを含む。ルータ２００が動作している間、他のプログラム２１８だけでなくオペレーティングシステム（又は複数のオペレーティングシステムのセット）２１４、パケット分類部６００はシステムメモリ２１０に常駐してよい。図２の実施形態においては、以下に説明されるが、パケット分類部の一部−すなわち、パケット分類部の第１ステージ６００ａ（ＳＴＡＧＥ１  ＰＣＫＴ  ＣＬＳＳＦＲ）−は、システムメモリ２１０に常駐し得る複数のソフトウェアルーチンを含むが、パケット分類部の他の部分−すなわち、パケット分類部の第２ステージ６００ｂ（ＳＴＡＧＥ  ２  ＰＣＫＴ  ＣＬＳＳＦＲ）−はハードウェアで実装される。一方で、図２の実施形態は開示されたパケット分類部の単なる１つの実装を表し、さらに、開示されたパケット分類部は任意の他の適切なソフトウェア及び／又はハードウェア構成で実装されてよいことが理解されるべきである。例えば、他の実施形態では、第２分類ステージ６００ｂもソフトウェアで実装されてよく、その場合、第２ステージ６００ｂはシステムメモリ２１０に常駐する（及び場合によっては記憶装置２３０に記憶される）ソフトウェアルーチンのセットを含んでよい。
【００４５】
ルータ２００はさらに、バス２０５に結合された読み出し専用メモリ（ＲＯＭ）２２０を有してよい。動作している間、ＲＯＭ２２０は、プロセッシングデバイス３００のための一時的な命令及び変数を記憶してよい。ルータ２００はバス２０５に結合された記憶装置（又は複数の記憶装置）２３０を有してもよい。記憶装置２３０は、例えばハードディスクドライブのような任意の適切な不揮発性メモリを含んでよい。オペレーティングシステム２１４及び他のプログラム２１８（例えば、パケット転送部２０１のソフトウェア実装）だけでなくパケット分類部６００（例えば、パケット分類部６００の第１ステージ６００ａ）も記憶装置２３０に記憶されてよい。さらに、取り外し可能な記憶メディアにアクセスするためのデバイス２４０（例えば、フレキシブルディスクドライブ又はＣＤ−ＲＯＭドライブ）がバス２０５に結合されてよい。
【００４６】
ルータ２００は、バス２０５に結合された１以上の入力デバイス２５０を有してよい。共通の入力デバイス２５０は、他のデータ入力デバイスだけでなく、マウスのようなポインティングデバイス、キーボードを含む。１以上の出力デバイス２６０がバス２０５に結合されてよい。共通の出力デバイス２６０は、ビデオディスプレイ、プリンティングデバイス、オーディオ出力デバイス、及びステータスインジケータ（例えばＬＥＤ）を含む。
【００４７】
ルータ２００は、バス２０５に結合されたネットワーク／リンクインタフェース２７０をさらに有してよい。ネットワーク／リンクインタフェース２７０は、ルータ２００を他のネットワーク（又は複数のネットワーク）５と結合することができ、さらにルータ２００をリンク１３０ａ−ｎのそれぞれと結合することができる、任意の適切なハードウェア、ソフトウェア、或いはハードウェア及びソフトウェアの組み合わせを含む。
【００４８】
図２に示されたルータ２００は、そのようなデバイスの実施形態の一例を表すことを目的としており、さらに、このシステムが明快さ及び理解し易さのために省略された多くの追加のコンポーネントを含んでよいことが理解されるべきである。例として、ルータ２００は、信号線及びバスだけでなく、ＤＭＡ（ダイレクトメモリアクセス）コントローラ、プロセッシングデバイス３００に関するチップセット、追加のメモリ（例えばキャッシュメモリ）を有してよい。また、ルータ２００は、図２に示されたコンポーネントの全ては有しなくてよいことが理解されるべきである。
【００４９】
一実施形態では、パケット分類部６００又はパケット分類部の一部は、コンピューティングデバイス−例えば図２のルータ２００又は他の適切なコンピューティングデバイス−上で実行される命令のセット（すなわち、ソフトウェアアプリケーション）を含んでよい。命令のセットは、記憶装置２３０（又は他の適切なプログラムメモリ）内にローカルに記憶されてよい。他にも、当該命令はリモートの記憶装置（図示せず）に記憶され、ネットワーク１００（又は他のネットワーク５）を介してアクセスされてよい。動作している間、命令のセットはプロセッシングデバイス３００上で実行されてよく、その命令（又はそれらの一部）はシステムメモリ２１０に常駐してよい。
【００５０】
他の実施形態では、パケット分類部６００（又はパケット分類部の一部）は、例えば磁気メディア（例えばフレキシブルディスク又は磁気テープ）、光アクセス可能ディスク（例えばＣＤ−ＲＯＭディスク）、フラッシュメモリデバイス等のような機械アクセス可能メディアに記憶された命令のセットを含んでよい。パケット分類部６００を実行し続けることを目的として、例えば、図２のルータ２００、取り外し可能な記憶メディアにアクセスするデバイス２４０は、機械アクセス可能メディア上の命令にアクセスしてよく、それから当該命令はプロセッシングデバイス３００で実行されてよい。本実施形態では、命令（又はそれらの一部）は、システムメモリ２１０に再びダウンロードされてよい。
【００５１】
さらなる実施形態では、パケット分類部６００又はパケット分類部の一部はハードウェアで実装されてよい。例えば、パケット分類部６００（又はそれらの一部）は内容参照可能メモリ（ＣＡＭ）を用いて実装されてよい。また、さらなる実施形態では、パケット分類部６００はソフトウェア及びハードウェアの組み合わせを用いて実装されてよい。
【００５２】
以下に詳細に説明される特別な一実施形態では、パケット分類部６００は２ステージパケット分類システムを持ち、この２ステージ分類スキームはハードウェア及びソフトウェアの両方で実装される。２ステージパケット分類部は、第１ステージ６００ａ及び第２ステージ６００ｂを持つ（図２を参照）。一実施形態では、第１ステージ６００ａはソフトウェアで実装され、第２ステージ６００ｂはハードウェアで実装される。
【００５３】
前述したように、プロセッシングデバイス３００の一実施形態は図３及び付随する本文に示される。一方で、図３に示されたプロセッシングデバイス３００は、パケット分類部６００の開示された実施形態が実装され得るプロセッシングデバイスの単なる一実施形態であることを理解すべきである。当業者は、パケット分類部６００の開示された実施形態が多くの他のタイプのプロセッシングシステム及び／又はプロセッサアーキテクチャで実装され得ることを理解するだろう。
【００５４】
図３に転じると、プロセッシングデバイス３００は、種々の機能ユニットが結合されるローカルバス３０６を持つ。バス３０５は、プロセッシングデバイス３００の種々の機能ユニットを相互に接続する１以上のオンチップバスの集合を表すことを目的とする。１つのバス３０５としてのこれらローカルバスの表現は理解し易さのために提供されており、プロセッシングデバイス３００がそのように限定されないことを理解すべきである。当業者は、プロセッシングデバイス３００が任意の適切なバスアーキテクチャを有してよく、任意の数及び任意の組み合わせのバスを有してよいことを理解するだろう。
【００５５】
１つのコア３１０及び複数のプロセッシングエンジン３２０（例えば、プロセッシングエンジン３２０ａ、３２０ｂ、・・・、３２０ｋ）がローカルバス３０５に結合される。一実施形態では、コア３１０は、オペレーティングシステム２１４を実行し得る汎用プロセッシングシステムを持ってよい。コア３１０は、プロセッシングデバイス３００のオペレーションを制御し、実行のためにプロセッシングエンジン３２０への命令の供給のような種々の管理機能を実行してよい。プロセッシングエンジン３２０ａ−ｋは、任意の適切なプロセッシングシステムを持ち、それぞれが１つの整数演算ユニット（ＡＬＵ）、１つのコントローラ、及び（リード／ライトオペレーションの間にデータを記憶するための）複数のレジスタを持ってよい。また、一実施形態では、それぞれのプロセッシングエンジン３２０ａ−ｋは、複数（例えば４個）の実行スレッドを提供する。
【００５６】
また、オンチップメモリサブシステム３３０がローカルバス３０５に結合される。１つのユニットとして示されているが、オンチップメモリサブシステム３３０は、多くの別個のメモリユニット及び／又はメモリタイプを持ってよい−実際には持つことが見込まれる−。例えば、そのようなオンチップメモリは、ＳＤＲＡＭ、ＳＲＡＭ、及び／又はフラッシュメモリ（例えば、ＦｌａｓｈＲＯＭ）を持つ。オンチップメモリに加えて、プロセッシングデバイス３００はオフチップメモリ（例えば、ＲＯＭ２２０、オフチップキャッシュメモリ等）と結合されてよいことが理解されるべきである。
【００５７】
プロセッシングデバイス３００は、ローカルバス３０５と結合されたバスインタフェース３４０をさらに持つ。バスインタフェース３４０は、バス２０５を含む、ルータ２００の他のコンポーネントとのインタフェースを提供する。簡単のために、バスインタフェース３４０は１つの機能ユニットとして示されている。しかしながら実際には、プロセッシングデバイス３００が複数のバスインタフェースを持ってよいことが理解されるべきである。例えば、プロセッシングデバイス３００は、他のインタフェースだけでなくＰＣＩバスインタフェース、ＩＸ（インターネット・エクスチェンジ）バスインタフェースを持ってよく、バスインタフェース３４０は１以上のそのようなインタフェースの集合を表すことが意図されている。
【００５８】
図３に関連して図示され説明されたプロセッシングデバイス３００の実施形態は、パケット分類部の開示された実施形態とともに用いられることが考えられるプロセッシングデバイスの単なる一例に過ぎず、さらに、プロセッシングデバイス３００は、図３に示されたコンポーネントに加えて、明確さ及び理解し易さのために省略された他のコンポーネントを持ってよいことが理解されるべきである。例えば、プロセッシングデバイス３００は他の機能ユニット（例えば、命令デコーダユニット、アドレス変換ユニット等）、熱管理システム、クロック回路、追加のメモリ、及びレジスタを持ってよい。また、プロセッシングデバイスは、図３に示された要素の全ては持たなくてよいことが理解されるべきである。
【００５９】
図４を参照すると、ルータ２００で（例えば他のネットワーク５から）受信され得るパケット４００の一例が示される。パケット４００は、ヘッダ４１０及びペイロード（又はデータ）４５０を有する。ヘッダ４１０は、任意の適切なフォーマットを有してよく、図４に示されたパケット４００はＴＣＰ／ＩＰプロトコルに関するヘッダの一例を示す。例えば、インターネット・エンジニアリング・タスクフォース標準勧告文章（ＩＥＴＦ  ＲＦＣ）７９１、インターネットプロトコル（１９８１）、及びＩＥＴＦ  ＲＦＣ  ７９３、トランスミッションコントロールプロトコル（１９８１）を参照すること。図４では、ヘッダ４１０は、フィールド４２０ａ、４２０ｂ、・・・、４２０ｘを含む複数のフィールドを有する。概して、フィールド４２０ａ−ｘは、パケット４００についての特定情報を含む。例として、ヘッダ４１０は、プロトコル４２０ｉ（例えばＴＣＰ）、発信元アドレス４２０ｋ、宛先アドレス４２０ｊ、発信元ポート番号４２０ｍ、及び宛先ポート番号４２０ｎを含む。発信元及び宛先アドレス４２０ｋ、４２０ｉのそれぞれは３２ビットを持ち、発信元ポート番号及び宛先ポート番号４２０ｍ、４２０ｎのそれぞれは８ビットを持つ。これらはパケットのヘッダ内に含まれ得る情報のタイプの単なる少数の例であり、さらに、パケットヘッダ４１０は特定のハードウェア及び／又はアプリケーションで近い将来に必要とされる任意の情報を含み得ることが、当業者によって理解されるだろう。また、パケットのフォーマットは、図４に関連して示され説明されたフォーマットに限定されないことが理解されるべきである（例えば、ヘッダフィールドの幅が変更可能であり、フィールドのタイプ及び数が変更可能、等）。
【００６０】
通信はここでは一般的に"パケット"として呼ばれる。しかしながら、開示された実施形態は、任意のタイプの通信（例えば、パケット、セル、フレーム等）に、フォーマット又は内容に関係なく適用可能であることが理解されるべきである。
【００６１】
図５Ａに転じると、パケット分類ルール５００の一実施形態が示される。概して、ルール５００は、基準を満たしているパケットが属する特定のフローを表す基準のセットを規定する。ルール５００は、フィールド５１０ａ（ＦＩＥＬＤ  １）、５１０ｂ（ＦＩＥＬＤ  ２）、・・・、５１０ｎ（ＦＩＥＬＤ  Ｎ）を含むいくつかのフィールドを有する。１つのルールは任意の適切な数のフィールド５１０ａ−ｎを有してよく、１つのルール内のフィールドの数はここでは次元と呼ばれる（すなわち、ルール５００はＮ次元を有する）。一実施形態では、フィールド５１０ａ−ｎのそれぞれは、発信元又は宛先アドレスのような、１つのパケットのヘッダにおける１つのフィールドに対応する。しかしながら、他の実施形態では、ルールのコンポーネント５１０ａ−ｎは、アプリケーションヘッダフィールド、リンク識別情報、時刻等のような、他の情報を含んでよい。概して、それぞれのフィールド５１０ａ−ｎについて、パケット内の対応するフィールドがルールのそのフィールドとマッチ場合に、パケットはルール５００と"マッチ"する（典型的には分類ルール内の１つのフィールドは値の範囲として表され、１つの値は、当該値がそのフィールドに対応する範囲に含まれる場合に、ルール内のフィールドとマッチする）。ルール５００は、そのルールとマッチするいずれのパケットにも適用されるべき対応づけられたアクション５２０（例えば、アクセプト、ブロック等）をさらに含む。ルール５００は、プライオリティ５３０にも対応づけられている。
【００６２】
図５Ｂを参照すると、パケット分類ルール５０１の他の実施形態が示される。ルール５０１は、いくつかのトランスポートレベルフィールド５１０ｃだけでなく、発信元アドレスフィールド５１０ａ及び宛先アドレスフィールド５１０ｂを有する。トランスポートレベルフィールド５１０ｃは、例えば、プロトコル５１５ａ、送信元ポート番号５１５ｂ、及び宛先ポート番号５１５ｃを含む。トランスポートレベルフィールド５１０ｃは前述のフィールドに限られず、トランスポートレベルフィールド５１０ｃは他のフィールド５１５ｄ−ｋを含んでよい（又はより少ないフィールドを含んでよい）。他の考えられるトランスポートレベルフィールドは、他のフィールドだけでなく、例えばＴＣＰ  ＳＹＮフラグ及びＲＳＶＰヘッダフィールド（例えば、ＩＥＴＦ  ＲＦＣ  ２２０５、リソース・リザベーション・プロトコル（ＲＳＶＰ）−機能仕様書バージョン１（１９９７）を参照すること）のような複数のプロトコルフィールドを含む。ルール５０１は、関連するアクション５２０及びプライオリティ５３０も含む。
【００６３】
図５Ｃは、図５Ｂに示されたルールの一例を示す。図５Ｃのルール５０２は、"１２８．１２８．＊"である発信元ＩＰ（インターネットプロトコル）アドレス５１０ａ、"１２８．６７．１２０．８４"である宛先ＩＰアドレス５１０ｂ、"ＴＣＰ"であるプロトコル５１０ｃ、"８０"である発信元ポート番号５１０ｄ、"＊"である宛先ポート番号５１０ｅを指定する。ここで、文字"＊"はワイルドカードを示す（すなわち、任意の値がワイルドカードにマッチし得る）。アクション５４０は"ブロック"（すなわち、当該ルールを満たす任意のパケットが許可されない）であり、ルール５０２は"２"を示すプライオリティ５４０を含む。勿論、図５Ｃがルールの単なる一例を表し、さらに、ルールは任意の適切な数及びタイプのヘッダフィールドを含んでよい（すなわち、ルールは任意の次元を持ってよい）ことが理解されるべきである。
【００６４】
１つのルールのフィールドのそれぞれは、完全一致（例えば"８０"に一致する発信元ポート番号）、プレフィックス（例えば"１２８．１２８．＊"の発信元アドレス）、範囲指定（例えば、発信元ポート番号"−１０２３"）として表現されてよい。一方で、いくつかの範囲（例えば、"＞１０２３"である発信元ポート番号）は、プレフィックスによって表することができず、そのような表現はプレフィックスのセットに分解されてよい。例えば、"＞１０２３"の範囲は、以下の一連の（バイナリ形式での）プレフィックス、すなわち、"000001**********"、"00001***********"、"0001************"、"001*************"、"01**************"、及び"1***************"で表され得る。このように、フィールド"＞１０２３"を持つルールは、６つの異なるルールに展開され、６つの別個のプレフィックスのそれぞれが範囲指定"＞１０２３"を形成する。Ｋビットの範囲は一般的に最大（２Ｋ−２）個のプレフィックスに分解されることに注意すべきである。
【００６５】
図６には、パケット分類部６００の一実施形態が示されている。パケット分類部６００は、分類プロセスを２ステージに分割する。パケット分類部６００は、第１ステージ６００a（ＳＴＡＧＥ  １）及び第２ステージ６００ｂ（ＳＴＡＧＥ  ２）を含む。第１ステージ６００ａにおいて、パケットはそのネットワークパスに基づいて分類され、第１ステージ６００ａにおいて、パケットは１以上の他のフィールド（例えば、トランスポートレベルフィールド）に基づいて分類される。ロジック６１０及びデータ構造１６００は第１ステージ６００ａに関連し、ロジック６２０及びデータ構造１７００は第２ステージ６００ｂに関連する。
【００６６】
第１ステージロジック６１０は、受信したパケットをそのパケットのネットワークパスに基づいて分類することができる、任意の適切なソフトウェア、ハードウェア、或いはフトウェア及びハードウェアの組み合せを持つ。一実施形態では、第１ステージロジック６１０は、受信したパケットの送信元及び宛先アドレスに基づいて１つの結果を決定し、この結果は分類部の第２ステージ６００ｂに供給される。パケットのネットワークパスに基づいてパケットを分類する方法の様々な実施形態が以下に記載される。複数のネットワークパスは、通常、送信元及び宛先アドレス（例えば、送信元ＩＰアドレス及び宛先ＩＰアドレス）によって表される。しかしながら、１つのネットワークパスの表現は、送信元−宛先アドレスのペアに限定されず、さらに、マルチプロトコルラベルスイッチング（ＭＰＬＳ）ラベル（例えばＩＥＴＦ  ＲＦＣ  ３０３１  Multiprotocol Label Switching Architecture （２００１）を参照すること）、１つの送信元ＩＰアドレスと１つの宛先アドレスマルチキャストグループとの組み合わせ等のような、別の代替の基準が１つのネットワークパスを特定すべく用いられ得ることが理解されるべきである。第１ステージデータ構造１６００は、以下においてもより詳細に説明されるが、他のメモリタイプだけでなくＳＲＡＭ、ＤＲＡＭ、ＳＤＲＡＭ、ＤＤＲＤＲＡＭを含む任意の適切なメモリ内に記憶されてよい。
【００６７】
第２ステージロジック６２０は、受信されたパケットのヘッダに含まれる複数のトランスポートレベルフィールド（又は他のフィールド）に基づいて、受信されたパケットを分類することができる、任意の適切なソフトウェア、ハードウェア、或いはフトウェア及びハードウェアの組み合せを持つ。一実施形態では、第２ステージロジック６２０は、分類の第１ステージからの結果を受信して、この結果及び受信したパケットの他の複数のフィールド（例えば、複数のトランスポートレベルフィールド）に基づいて、パケットに適用されるべき又は実行されるべきアクションを決定する。パケットのヘッダに含まれる１以上のトランスポートレベルフィールド（又は他の複数のフィールド）に基づいてパケットを分類する方法の多様な実施形態が以下に記載される。第２ステージデータ構造１７００は、他のメモリタイプだけでなくＣＡＭ、ＳＲＡＭ、ＤＲＡＭ、ＳＤＲＡＭのような任意の適切なタイプのメモリ内に記憶されてよい。第２ステージデータ構造１７００は、以下により詳細に説明される。
【００６８】
１つの特有な実施形態では、上記で触れられたように、パケット分類部６００はソフトウェア及びハードウェアの組み合わせに実装される。より具体的には、第１分類ステージ６００ａはソフトウェアに実装され、第２分類ステージ６００ｂはハードウェアに実装される。本実施形態では、第１分類ステージ６００ａは、メモリ（例えば、図２に示されたシステムメモリ２１０及び／又は図３に示されたオンチップメモリサブシステム３３０）に記憶されて、プロセッシングデバイス（例えば、図３のプロセッシングデバイス３００）上で実行される命令のセットを持ち、一方で第２ステージ６００ｂはＣＡＭ（又は他のハードウェア構成）を用いて実装され得る。
【００６９】
後述の２ステージ分類スキームは、図６の２ステージパケット分類部６００に実装されるように、２ステージパケット分類のための方法７００の一実施形態を示す図７にさらに図示される。図７のブロック７１０を参照すると、パケットが受信され、そして、ブロック７２０に記載のように、パケットは、パケットのネットワークパスに基づいて最初に分類される。一般的に、パケットのネットワークパスは、パケットのヘッダに含まれる送信元及び宛先アドレスで表される。その後、パケットは、受信されたパケットのヘッダに含まれる１以上の他のフィールドに基づいて分類され、それはブロック７３０に示される。２ステージ分類（ブロック７２０、７３０を参照）の結果に基づいてプライオリティの最も高いアクションが特定されて、ブロック７４０に示されるようにこのアクションがパケットに適用される。
【００７０】
通常、インターネットには、多くの他の巨大ネットワークと同様に、ネットワークにわたる多くの考え得るルートが存在するが、比較的少数のアプリケーションしか存在しない。したがって、別個のネットワークパスの数は、一般的にアプリケーションの数よりはるかに大きいということになる。これらの考えは、分類ルールのセットにある送信元−宛先アドレスのペアの数が一般的に他のフィールド（例えば、ポート番号及びプロトコルのようなトランスポートレベルフィールド）の数よりはるかに大きいことを示唆する、実際の分類データベースの分析によって実証される。これらの分析は、多くの異なる送信元−宛先アドレスのペアがトランスポートレベルフィールド（又は他のフィールド）の同じセットを使用しているということ、さらに、セットのそれぞれのメンバーに関連する相対的プライオリティ及びアクションが、セットのそれぞれの出現において概して同じであるということも示唆する。その上、それぞれのセット内のエントリの数は一般的に小さい。
【００７１】
分類データベース内の送信元−宛先アドレスのペアがルーチン的にトランスポートレベルフィールドの同じセットを使用しているという事実が、図８に示される。本図を参照すると、分類データベース８００の一例が示されている。この分類データベース８００は、いくつかの分類ルールを持ち、それぞれのルールは、関連する１つのアクション８２０及び１つの絶対的プライオリティ８３０ａだけでなく、１つの送信元ＩＰアドレス８１０ａ、１つの宛先ＩＰアドレス８１０ｂ、１つのプロトコル８１０ｃ、１つの送信元ポート番号８１０ｄ、及び１つの宛先ポート番号８１０ｅを含む。ルールの２つのグループ８０１、８０２が図８に示され、第１グループのルールのそれぞれは、送信元及び宛先ＩＰアドレス８１０ａ−ｂによって表されるように同じネットワークパスを持ち、第２グループのルールのそれぞれは同じネットワークパスを持つ（しかし、第１グループのネットワークパスとは異なる）。ルールのセット（８０１又は８０２）内のそれぞれのルールの相対的なプライオリティ８３０ｂも、図８に示されている。２つのルールグループ８０１、８０２はそれぞれ異なる送信元−宛先アドレスのペアを持つが、これらのルールグループは同じトランスポートレベルフィールド、相対的プライオリティレベル（すなわち、ルールグループ８０１用のプロトコル、ポート番号指定、アクション、及びプライオリティは、グループ８０２用に反復される）の同じセットを共有する（１以上の）トランスポートレベルフィールド、１つのアクション、及び１つの相対的プライオリティのセットの組み合わせは、ここでは"トリプレット"として呼ばれる。
【００７２】
図６に戻ると、パケット分類の第１ステージ６００ａにおいて、この分類ステージを著しく簡略化する第１ステージにおける分類が送信元及び宛先アドレスに基いて実行され得るので、Ｎ次元分類問題は２次元問題に変えられる。第２ステージ６００ｂはいくつかのフィールド（例えば、３つ以上のフィールド）に基づく分類を含むが、この分類問題の複雑さは、後に述べる実際の分類データベースの特性を利用することによって著しく低減され得る。特に、多くの送信元−宛先アドレスのペアがトリプレット（すなわち、トランスポートレベルフィールドの１つのセット、１つのアクション、及び１つの相対的プライオリティ）の同じグループを共有するということを理解することによって、チェックされるべきエントリの数−そしてメモリアクセスの数−は実質的に低減される。複数の送信元−宛先アドレスのペアをトランスポートレベル（又は他の）フィールドの様々なセットの１グループと関係づけるという概念は−すなわち、これらの送信元−宛先アドレスのペアのそれぞれがトリプレットの同じセットを使用するので−ここでは"トランスポート共有"（"ＴＬＳ"）と呼ばれる。トランスポートレベルフィールドの１グループは送信元−宛先アドレスの複数のペアによって潜在的に共有され得るが、トランスポートレベルフィールドの一意のグループのそれぞれは一度記憶され、それによりパケット分類システムのストレージ要件を低減する。
【００７３】
２ステージ分類スキームの第１ステージ６００ａは、上記のように、多次元分類問題を２次元分類問題に変えることによって簡略化される。しかしながら、パケットが分類データベース内のいくつかのルールにマッチする可能性があり−そして実際にはマッチしそうである−、したがって、第１ステージ６００ａは複数のマッチを戻すだろう。複数のマッチは、少なくとも部分的には、分類データベース内の全ルールの送信元−宛先アドレスのペアのオーバーラップ性によって、そして第２には、送信元−宛先アドレスのペアは任意のプライオリティに関連し得るという事実によって生じ得る。考えられる全てのマッチングルールを見つけることは、第１分類ステージにおいて必要とされるメモリアクセスの数を著しく増加させ得る。さらに、複数のマッチが第１分類ステージから戻されたとき、分類の第１及び第２ステージ６００ａ、６００ｂ間での結果のマージが困難となる。したがって、他の実施形態では、簡略化してパケット分類の第１ステージ６００ａの効率を向上させるべく、１つの最適なマッチが第１ステージから戻される。一実施形態では、"最適マッチ（most specific match）"は、パケットのネットワークパスについての最大量の情報を提供するマッチである（例えば、ＩＰネットワークでは、最適マッチは、パケットをカバーしている全てのフィルタの共通集合である）。第１分類ステージ６００ａから１つのマッチングフィルタを決定して戻すプロセスは、ここで"最適フィルタマッチング（most specific filter matching）"（又は、"ＭＳＦＭ"）と呼ばれる。
【００７４】
図９に転じて、２ステージパケット分類のための方法９００の他の実施形態が示される。２ステージパケット分類のための方法９００は、トランスポートレベル共有及び最適フィルタマッチングの双方を実装する。図９のブロック９１０を参照すると、パケットが受信される。ブロック９２０で説明するように、分類の第１ステージにおいて、パケットはパケットの送信元及び宛先アドレスに基づいて、１つの最適マッチを発見すべく分類される。ブロック９３０で説明される分類の第２ステージにおいて、パケットは、トランスポートレベル共有を用いて、１以上のトランスポートレベルフィールドに基づいて分類される。ブロック９４０で説明されるように、その分類の２つのステージの結果に基づいて、最も高いプライオリティのアクションが決定されてパケットに適用される。他の実施形態では、第２ステージにおけるトランスポートレベル共有なしで最弱フィルタマッチングが第１ステージにおいて使用され、さらなる実施形態では、第１ステージにおける最適フィルタマッチングなしでトランスポートレベル共有が第２ステージにおいて使用されるということが理解されるべきである。
【００７５】
最適フィルタマッチング（ＭＳＦＭ）及びトランスポートレベル共有（ＴＬＳ）の双方が、以下により詳細に説明される。この議論は、ＴＬＳの説明から始まり、ＭＳＦＭの説明が続く。
【００７６】
典型的な分類データベースは、複数のルールの１つのリストを持つ。このことは、ルール１００５ａ、１００５ｂ、・・・、１００５ｙを含むいくつかの複数のルール１００５を持つ分類データベース１０００を示す図１０に示される。ルール１００５ａ−ｙのそれぞれは、例えば、関連するアクション１０２０及びプライオリティ１０３０だけでなく、１つの送信元アドレス１０１０ａ、１つの宛先アドレス１０１０ｂ、及び１以上のトランスポートレベルフィールド１０１０ｃ（又は他のフィールド）を持つ。ルール１００５のそれぞれについて、トランスポートレベルフィールド１０１０ｃ、アクション１０２０、及びプライオリティ１０３０の組合せは、前述したように"トリプレット"１０４０と呼ばれる。前に議論したように、典型的な分類データベースは、送信元−宛先ペアの数に比べて比較的少ない一意のトランスポートレベルフィールドセットを持ち、さらに、典型的なデータベースにおけるトランスポートレベルフィールドセットの同じグループは、複数の送信元−宛先ペアによって共有される（図８及び付随する本文を参照すること）。分類データベースのこの特性を利用すべく、データベース１０００の複数のルール１００５は複数のルールセットにグループ化される。１つのルールセットは、同じ送信元及び宛先アドレスのペアを持つデータベースのルールを含む。例えば、図８に戻って、グループ８０１内の複数のルールは、第１ルールセットを有し（すなわち、それらは送信元アドレス"１９２．１２８．１０．５"及び宛先アドレス"１７２．１２８．＊"を共有する）、グループ８０２内の複数のルールは、第２ルールセットを有する（すなわち、それらは送信元アドレス"１２８．１２８．１０．７"及び宛先アドレス"１７２．１２８．＊"を共有する）。
【００７７】
いくつかのルールセットへの分類データベースのパーティショニングの一例が、図１１Ａに示される。本図を参照すると、分類データベース１１００は、ルールセット１１５０ａ、１１５０ｂ、・・・、１１５０ｑを含むいくつかのルールセット１１５０に組織化される。それぞれのルールセット１１５０ａ−ｑは１以上のルールを含み、任意のルールセット１１５０内のそれぞれのルールは、ルールセット内の他の全てのルールと同じ送信元及び宛先アドレスのペアを共有する。一実施形態では、図１１Ａに示されるように、データベース１１００のルールは、それぞれのルールセット１１５０ａ−ｑのルールがデータベース内の連続的な空間を占めるよう配列される。また、１つのルールセット１１５０内のルールは、連続するプライオリティレベルを占める。しかしながら、他の実施形態では、１つのルールセットは連続するプライオリティレベルを占めないルールによって形成されてよい。ルールセット１１５０ａ−ｑは、それぞれフィルタ１１６０と関連していると考えられる（すなわち、ルールセット１１５０ａはフィルタ１１６０ａと関連し、ルールセット１１５０ｂはフィルタ１１６０ｂと関連する、等）。１つのルールセット１１５０のためのフィルタ１１６０は、そのルールセットのための送信元−宛先ペアを含む。図１１Ａの実施形態は、１つの分類データベースの複数のルールが複数のルールセットを形成する方法の一例に過ぎないことが理解されるべきである。
【００７８】
図１１Ａにおけるそれぞれのルールセット１１５０（及び対応するそれぞれのフィルタ１１６０）は、関連するトリプレットのグループを持っており、それぞれのトリプレットは、複数のトランスポートレベル（又は他の）フィールド、１つのアクション、及び１つの相対的プライオリティを持つ。図８に再び戻ると、ルールセット８０１、８０２のそれぞれは、それに関連する３つのトリプレットの１つのグループを持つ。そして、図８の例において、それぞれのルールセット８０１、８０２はトリプレットの同じグループを偶然に持つ（すなわち、ルールセット８０１、８０２送信元−宛先ペアがそれぞれ、トリプレットの同じセットを共有する）。任意のルールセット及びフィルタに関連するトリプレットは、ここで"複数のビン"、そして、（以下に説明される"ラージビン"と区別されるよう）ここにおいて"複数のスモールビン"と呼ばれる複数のグループを形成する。したがって、図１１Ａに示されるように、それぞれのルールセット１１５０及び対応するフィルタ１１６０は、トリプレットのスモールビン１１７０に関連する（すなわち、ルールセット１１５０ａ及びフィルタ１１６０ａはスモールビン１１７０ａと関連する、等）。トランスポートレベル共有の概念に導くのは、トランスポートレベルフィールドの種々のセットの１つのグループ（すなわち、スモールビン）を、１つのルールセットに含まれる複数のルールの間で共有することである。
【００７９】
図１１Ａのデータベース１１００に関連するスモールビン１１７０は、図１１Ｂにさらに示される。図１１Ｂを参照すると、データベース１１００は、スモールビン１１７０の集合に関連づけられている。それぞれのスモールビン１１７０は、１以上のエントリ１１７２を含み、それぞれのエントリ１１７２は、１以上のトランスポートレベル（又は他の）フィールド１１７４、１つの相対的プライオリティ１１７５、及び１つのアクション１１７６（すなわち、トリプレット）を持つ。図１１Ｂに示されるように、スモールビン１１７０は、"複数のラージビン"にさらに論理的に組織化されてよく、それぞれのラージビン１１８０は、２以上のスモールビン１１７０の集合を含む。ラージビン１１８０の生成は以下に説明される。
【００８０】
トランスポートレベルフィールドに基づいてパケットを分類するために使用される第２ステージデータ構造１７００が、以下に説明される。以下に最適フィルタマッチングの議論に着目する。
【００８１】
前に示唆したように、パケットのネットワークパスに基づいてパケットを分類するとき、パケットは分類データベース内の複数のルールにマッチする可能性がある。第１分類ステージ６００ａの効率を向上すべく−例えば、要求されるメモリアクセス数を低減すべく−、さらに、第１ステージの結果を第２分類ステージ６００ｂとマージすることを簡略化すべく、第１ステージから１つの最適マッチを戻すことが望ましい。
【００８２】
"フィルタ"という用語は、ここでは１つのルールセットに関連する送信元−宛先アドレスのペアを参照するために用いられるので、この議論におけるこの時点では、"ルール"ではなく"フィルタ"という用語が用いられる（図１１Ａ−１１Ｂ及び付随する上の本文を参照すること）。しかしながら、"フィルタ"及び"ルール"という用語が、多くの場合区別なく使用されることが理解されるべきである。
【００８３】
送信元及び宛先アドレスに基づいて分類されるパケットが複数のフィルタにマッチすることは、少なくとも部分的には、分類データベース内のフィルタのオーバーラップ性による。これは図１２Ａから１２Ｃ及び図１３Ａから１３Ｃにおいて概略的に図示される。まず図１２Ａを参照すると、１つのルールの送信元及び宛先アドレスは、２次元空間内の１つの領域（すなわち、矩形、線、又は点）として考えられる。図１２Ａでは、分類データベースの第１フィルタ１２１０は、Ｆ１とラベル付けされた矩形によって示される２次元空間を占める。フィルタＦ１は、トリプレットのスモールビン１２１５（Ｂ１）に関連する。図１２Ｂに転じて、データベースの第２フィルタ１２２０（Ｆ２）も、送信元及び宛先アドレス空間における領域を占めており、このフィルタＦ２は、トランスポートレベルフィールドのスモールビン１２２５（Ｂ２）に関連する。
【００８４】
フィルタＦ１及びＦ２は共に図１２Ｃに示され、これら２つのフィルタによって定義された領域はオーバーラップ又は交わっていることがわかり、Ｆ１及びＦ２の共通集合は参照番号１２９０によって示されている。図１２Ａ−１２Ｃに示されたフィルタＦ１及びＦ２は、"部分的にオーバーラップ"しているといえる。パケット（Ｐ）１２０５がフィルタＦ１及びＦ２の共通部分１２９０に含まれる送信元−宛先アドレスペアを持っている場合、このパケットは両方のフィルタにマッチする（すなわち、フィルタＦ１及びＦ２がパケットＰによって定義される少なくとも点を共通して持つ）。また、パケットＰは、フィルタＦ１及びＦ２の共通部分１２９０に含まれる任意の他のパケットだけでなく、Ｆ１及びＦ２に関連するスモールビンＢ１及びＢ２の集合(union)に関連するだろう。２以上のフィルタの共通部分に関連するスモールビンのこの集合は、ここでは"ラージビン"と呼ばれる。ビンＢ１及びＢ２の集合を持つラージビンは、図２Ｃにおける参照数字１２９５によって示される。
【００８５】
フィルタは、"完全にオーバーラップ"していてもよく、このシナリオは図１３Ａ−１３Ｃに示される。第１フィルタ１３１０（Ｆ１）は、図１３Ａに示される２次元空間内の領域を占め、第２フィルタ１３２０（Ｆ２）は図１３Ｂに示されるこの空間内の領域占める。フィルタＦ１は関連するスモールビン１３１５（Ｂ１）を持ち、フィルタＦ２は関連するスモールビン１３２５（Ｂ２）を持つ。次に図１３Ｃを参照すると、双方のフィルタＦ１及びＦ２が示され、これらのフィルタは共通部分１３９０でオーバーラップする（この場合、共通部分１３９０はＦ２によって定義される領域と等価である）。Ｆ２によって定義される領域（及び共通部分１３９０）は、フィルタＦ１の２次元空間に完全に含まれ、フィルタＦ１及びＦ２は、"完全にオーバーラップ"していると言える。この共通部分１３９０に含まれるパケット（Ｐ）１３０５は両方のフィルタＦ１及びＦ２にマッチし、このパケットＰ（及びこの共通部分１３９０に含まれる任意の他のパケット）は、スモールビンＢ１及びＢ２の集合を持つラージビン１３９５と関連するだろう。
【００８６】
図１２Ａ−１２Ｃ及び１３Ａ−１３Ｃから分かるように、２つ（又はさらに多く）のフィルタの共通部分内にある送信元アドレス及び宛先アドレスを持つパケットは両方のフィルタにマッチするだろう。分類の第１ステージから１つのマッチのみを戻すという目標を達成すべく、全てのフィルタの共通部分がフィルタデータベース内に含まれる（すなわち、第１ステージデータ構造１６００）。さらに、それぞれのフィルタ共通部分は、その共通部分を形成する個々のフィルタのトランスポートレベルフィールドの集合に関連している。言い換えると、上記したように、それぞれのフィルタ共通部分は、２以上のスモールビンの集合を持つラージビンに関連している。全てのフィルタ共通部分をルックアップテーブルに加えることは、理論的には極めて大きな記憶容量を必要とする。しかしながら、実際の分類データベースの検討は、実際上、フィルタ共通部分を記憶するために必要とされる追加の容量は、理論的な上限より著しく小さいことを示唆する。
【００８７】
パケットをその送信元及び宛先アドレスに基づいて分類すべく、問題は、パケットが位置する複数のフィルタの最小の共通部分（又は、パケットが共通部分に含まれない場合は、単にそのフィルタ）を発見することの１つになる。複数のフィルタのこの最小の共通部分を発見すべく、第１分類ステージ（２次元分類問題）は２つの１次元ルックアップに分けられる。これは、第１次元１４１０及び第２次元１４２０を示す図１４に概略的に示される。第１次元１４１０において、受信されたパケットの送信元アドレスが送信元アドレスルックアップデータ構造１４１２のエントリと比較され、１つのマッチが発見された場合に、１つのインデックス１４１４（Ｉ１）が戻される。同様に、第２次元１４２０において、そのパケットの宛先アドレスが宛先アドレスルックアップデータ構造１４２２のエントリと比較され、１つのマッチが発見された場合に、１つの第２インデックス１４２４（Ｉ２）が戻される。そして、その２つのインデックス１４１４、１４２４（Ｉ１及びＩ２）は、他のルックアップデータ構造（例えば、ハッシュテーブル）に問い合わせるために用いられるキー１４３０を形成すべく結合される。一実施形態では、それぞれ第１及び第２次元１４１０、１４２０のルックアップデータ構造１４１２、１４２２上で実行されるルックアップは、最長プレフィックスマッチ（ＬＰＭ）を用いて実行される。さらなる実施形態では、２つの次元１４１０、１４２０における複数のルックアップはパラレルに実行される。送信元及び宛先の次元において２つのパラレルで独立したルックアップを利用することは、比較的少数のメモリアクセスしか必要とせず、リーズナブルな記憶要件しか提示しないと考えられる。
【００８８】
図１４に示されたパラレルなＬＰＭルックアップスキームは、パケットが含まれるフィルタの最小の共通部分、又はこのスキームは１つの"非存在"フィルタを戻す。１つの非存在フィルタは、１つのフィルタの送信元アドレス及び異なるフィルタの宛先アドレスを持つ。非存在フィルタは、送信元及び宛先アドレスにおけるルックアップが独立に実行される（しかしながら、一実施形態では、これらのルックアップはパラレルに実行される）という事実に起因する。
【００８９】
非存在フィルタの概念は、１つの例を参照することで最もよく理解されるだろう。図１５を参照すると、データベースは文字Ａ、Ｂ、Ｃ、Ｄ、及びＥによって示される５つのフィルタを含み、これらのフィルタは２次元アドレス空間１５００内で示される。フィルタＡは、送信元及び宛先アドレス空間の全体をカバーし、このフィルタは"＊"によって示される（すなわち、これは送信元及び宛先アドレスの両方においてワイルドカード文字"＊"を持つ）。フィルタＢは"＊，Ｙ＊"の形式を持ち、この形式のフィルタ（すなわち、"＊，Ｙ＊"又は"Ｘ＊，＊"）は"部分指定フィルタ"と呼ばれる。フィルタＣ、Ｄ、及びＥは、"完全指定フィルタ"と呼ばれ、これらのフィルタは"Ｘ＊，Ｙ＊"の形式を持つ。例として、フィルタ"送信元アドレス  １２８．１７２．＊／宛先アドレス  ＊"は１つの部分指定フィルタであり、フィルタ"送信元アドレス  １２８．１７２．＊／宛先アドレス  １２８．１２８．＊"は１つの完全指定フィルタである。フィルタＡ、Ｂ、Ｃ、Ｄ、及びＥの送信元及び宛先アドレスの組合せは、２次元空間内の１２個の異なる領域を形成する。最初の５つの領域はフィルタＡ、Ｂ、Ｃ、Ｄ、及びＥに一致する。Ｒ１からＲ７で示される（破線により示される）他の７つの領域は、非存在フィルタに該当する。領域Ｒ１からＲ７は１つのフィルタの宛先アドレス及び他のフィルタの送信元アドレスから形成され、これらの領域は、上記のように送信元及び宛先アドレスにおけるルックアップが独立に実行されることによって生成される。例えば、領域Ｒ４は、フィルタＥの送信元アドレス及びフィルタＤの宛先アドレスを結合することによって生成され、これは存在しないフィルタをもたらす。図１５に示される図は、通常、クロス積テーブルとして呼ばれる。
【００９０】
図１４のパラレルルックアップスキームが１つの結果を戻すことを保証すべく、非存在フィルタＲ１からＲ７の全てがフィルタデータベース内に入れられる必要があるように思われる。いくつかの従来技術（例えば、クロス積テーブルスキーム）は、全ての非存在フィルタをフィルタデータベースに加えることを提案している。しかしながら、実際の分類データベースの分析は、非存在フィルタの数が非常に大きくなり得ること示唆しており、したがってフィルタデータベースに加えられる非存在フィルタの数を最小化することが望ましい。したがって、一実施形態では、全ての可能な非存在フィルタの１つのサブセットのみが、分類データ構造に含まれる。分類データ構造への全ての考えられる非存在フィルタの追加が避けられる方法（及び全ての考えられる非存在フィルタの代わりにデータ構造に配置された非存在フィルタの１つのサブセット）は、以下により詳細に説明される。
【００９１】
図１５を参照すると、領域Ｒ１からＲ７の多くが、少数の他のフィルタにまとめられることがわかる。特に、Ｒ１、Ｒ３、及びＲ４を完全にカバーする最小のフィルタは、全２次元空間であるフィルタＡである。領域Ｒ１、Ｒ３、及びＲ４の１つに入る任意のパケットの送信元又は宛先アドレスの一方におけるサーチは、領域Ａに含まれるフィルタの送信元又は宛先アドレスを戻す。したがって、フィルタ"＊，＊"への別個のエントリが存在すれば、非存在フィルタＲ１、Ｒ３、及びＲ４はフィルタＡに集約され、Ｒ１、Ｒ２、及びＲ４への別個のエントリはフィルタデータベースから除かれる。同様に、領域Ｒ５、Ｒ６、及びＲ７は、フィルタＢによって完全にカバーされ、これらの非存在フィルタはフィルタＢへのエントリに集約される。領域Ｒ５、Ｒ６、又はＲ７の１つにある任意のパケットについて、このパケットの宛先アドレスにおけるサーチは、フィルタＢの宛先アドレスを戻すだろう。したがって、部分的に指定されたフィルタＢへの別個のエントリが分類データ構造内に用意されているかぎり、Ｒ５、Ｒ６、及びＲ７の別個のデータベースエントリは必要とされない。
【００９２】
領域Ｒ２は、しかしながら、任意の他のフィルタとマージされる。フィルタＤの送信元アドレス及びフィルタＥの宛先アドレスから形成されるこの領域は、１つの完全指定フィルタ−すなわち、フィルタＣによって完全にカバーされる。非存在フィルタＲ２は、１つの完全指定フィルタ内に完全に含まれるただ１つのものであるという点で、他の非存在フィルタと区別される。非存在フィルタＲ２は、フィルタＣ又は他のエントリに集約されることができず、このフィルタへの１つのエントリはフィルタデータベースに配置される。Ｒ２のような非存在フィルタは、ここでは"インジケータフィルタ"と呼ばれる。インジケータフィルタは、そのインジケータフィルタを完全にカバーするフィルタの考えられる最小の共通部分に相当するトランスポートレベルフィールドのセットと関連づけられる。例として、図１５に示されたフィルタのセットについて、領域Ｒ２を完全にカバーするフィルタはフィルタＡ及びＣであり、これらの２つのフィルタの共通部分はフィルタＣに簡略化される。したがって、インジケータフィルタＲ２は、フィルタＣと同じトランスポートレベルフィールドのセットに関連づけられるだろう。
【００９３】
いくつかの追加の観察が、第１ステージデータ構造１６００の開発の助けとなる。全般的に、分類データベース内のフィルタの間で部分的にオーバーラップする３つの送信元、すなわち、（１）部分指定フィルタ（すなわち、"Ｘ＊，＊"又は"＊，Ｙ＊"形式のフィルタ）の間で生成された部分的なオーバーラップ、（２）完全指定フィルタ（すなわち、"Ｘ＊，Ｙ＊"形式のフィルタ）の間で生成された部分的なオーバーラップ、及び（３）部分指定フィルタ及び完全指定フィルタの間で生成された部分的なオーバーラップが存在する。送信元次元においてワイルドカードを持つ部分指定フィルタのそれぞれは、宛先次元においてワイルドカードを持つ部分指定フィルタの全てと部分的なオーバーラップを生成し、そのような部分指定フィルタの共通部分によって生成される部分的なオーバーラップの数は、送信元及び宛先次元のそれぞれにおける部分指定フィルタの数の積に一致する。部分指定フィルタの共通部分による部分的なオーバーラップの数は、理論的にはかなり大きくなる。一方、完全指定フィルタは、わずかな数の互いの部分的オーバーラップを生成する。この結果は、実際上、殆どの完全指定フィルタが２次元アドレス空間における直線セグメント又は点であることによる。
【００９４】
先の段落において示唆されたように、典型的には、部分指定フィルタが、典型的な分類データベース内のフィルタ間での部分的オーバーラップの主原因である。しかしながら、部分指定フィルタは、多くの場合、分類データベース内の全フィルタ数の小さな割合を占める。なぜなら、ネットワーク管理者は通常、特定のアドレスドメインの間で交換されるトラフィックに適用されるルールを指定するからである。したがって、部分指定フィルタによってもたらされる部分的フィルタオーバーラップの数は、実際には理論的な最悪のケースより著しく小さい。また、上記したように、完全指定フィルタは、フィルタ間の部分的オーバーラップをわずかな数生成する。したがって、実際の分類データベースに存在する部分的オーバーラップの数は、概して、理論上発生することが期待されるより著しく小さい。
【００９５】
ここでは、図１３Ａ−１３Ｃに示したような、完全にオーバーラップするフィルタについて考慮していないことに注意すべきである。先に説明したように、一実施形態では、最長プレフィックスマッチ（ＬＰＭ）が、ＭＳＦＭで実行される２つの１次元サーチのそれぞれにおいて使用される。フィルタが完全にオーバーラップする場合、これらのフィルタの共通部分はこれらのフィルタの１つに等しく、ＬＰＭサーチがそのフィルタを特定する。したがって、第１ステージデータ構造１６００は、一実施形態では、完全にオーバーラップするフィルタについて説明する必要がない。
【００９６】
上記の観察及び議論（図６−１５及び付随する本文を参照すること）は、第２ステージデータ構造１７０だけでなく第１ステージデータ構造１６００を構築するために使用することができる"基本要素"を提供し、これらの２つのデータ構造の実施形態が以下に説明される。パケットを分類するための（すなわち、パケットに適用すべき１つのアクションを特定するための）第１及び第２ステージデータ構造１６００、１７００をサーチする方法の実施形態が、以下に提示される。
【００９７】
ここで図１６Ａを参照すると、第１ステージデータ構造１６００の一実施形態が示される。第１ステージデータ構造１６００は、パラレルＬＰＭデータ構造１６０１及びフォワーディングテーブル１６０２を有する。先に説明したように、ＭＳＦＭスキームは、図１４に関連して先に提示及び説明されたような、送信元及び宛先アドレス上でそれぞれ実行される２つの１次元サーチを用いる。したがって、パラレルＬＰＭデータ構造は、１つの送信元アドレスルックアップデータ構造１６１０及び１つの宛先アドレスルックアップデータ構造１６２０を含む。一実施形態では、送信元及び宛先アドレスルックアップデータ構造１６１０、１６２０は、トライデータ構造として実現される。しかしながら、送信元及び宛先アドレスルックアップデータ構造１６１０、１６２０を実現するために他の代替のデータ構造を使用し得ることが当業者に理解されるだろう。
【００９８】
さらに図１６Ｂに、パラレルＬＰＭデータ構造１６０１の一実施形態が概略的に示される。送信元アドレスルックアップデータ構造１６１０は、複数のエントリ１６１２を含み、それぞれのエントリ１６１２は、１つの送信元プレフィックス１６１４ａ、１つのフィルタタイプ１６１４ｂ、及び１つのインデックス値１６１４ｃ（又は他の識別子）を指定する。同様に、宛先アドレスルックアップデータ構造１６２０は複数のエントリ１６２２を含み、それぞれのエントリ１６２２は、１つの宛先プレフィックス１６２４ａ、１つのフィルタタイプ１６２４ｂ、及び１つのインデックス値１６２４ｃ（又は他の識別子）を指定する。ルックアップデータ構造１６１０、１６２０の双方において、フィルタタイプ１６１４ｂ、１６２４ｂは、エントリ１６１２、１６２２が１つの完全指定フィルタ又は１つの部分指定フィルタのいずれに関連しているかを示す。パラレルＬＰＭデータ構造１６０１上でサーチが実行されたとき、送信元アドレスルックアップデータ構造１６１０内のマッチする完全指定フィルタに関連する１つの第１インデックス１６９１（Ｉ１）、宛先アドレスルックアップデータ構造１６２０内のマッチする完全指定フィルタに関連する１つの第２インデックス１６９２（Ｉ２）、送信元アドレスルックアップデータ構造内のマッチする部分指定フィルタに関連する１つの第３インデックス１６９３（Ｉ３）、及び宛先アドレスルックアップデータ構造内のマッチする部分指定フィルタに関連する１つの第４インデックス１６９４（Ｉ４）を含む、４つのインデックス（又は他の識別子）が戻される。先に説明したように、送信元及び宛先アドレス次元におけるサーチは、一実施形態において、パラレルに実行される。
【００９９】
完全指定フィルタに関連する最初の２つのインデックス１６９１及び１６９２（Ｉ１及びＩ２）は、１つのキー１６９０を生成すべく結合される。完全指定フィルタに関連するキー１６９０は、部分指定フィルタに関連する第３及び第４インデックス１６９３、１６９４だけでなく、以下に説明されるようにフォワーディングテーブル１６０２をサーチするために使用される。この時点において完全及び部分指定フィルタの間を区別する理由は、マッチしているフィルタは部分指定フィルタであり、最長プレフィックスマッチは分類の第１ステージにおいて使用されるからであり、期待される部分指定フィルタは特定されない（すなわち、特定すべきマッチしている送信元又は宛先プレフィックスは、実際のマッチングフィルタの対応するプレフィックスより"長い"）。
【０１００】
一実施形態では、図１６Ａに示されるように、フォワーディングテーブル１６２０は、プライマリテーブル１６３０及び２つのセカンダリテーブル１６４０ａ、１６４０ｂを有する。プライマリテーブル１６３０は、複数の完全指定フィルタ、複数の完全指定フィルタ共通部分、及び複数のインジケータフィルタのための複数のエントリを含む。繰り返すと、１つのインジケータフィルタは、異なる送信元−宛先ペアの送信元及び宛先プレフィックスから形成された１つの領域であり、完全指定フィルタ又はフィルタ共通部分で集約されることができない（例えば、上記で議論したように、図１５の領域Ｒ２を参照すること）。セカンダリテーブル１６４０ａ−ｂの一方は、送信元次元においてワイルドカードを持っている部分指定フィルタのための複数のエントリを含み、セカンダリテーブル１６４０a−ｂの他方は、宛先次元においてワイルドカードを持っている部分指定フィルタのための複数のエントリを含む。セカンダリテーブル１６４０ａ、１６４０ｂは、インジケータフィルタを含まない。上記したように、１つのフィルタの送信元(又は宛先）プレフィックス及び他のフィルタの宛先（又は送信元）プレフィックスから生成される同じ領域は部分指定フィルタで集約され（図１５、領域Ｒ５、Ｒ６、及びＲ７を参照すること）、そのような領域のための複数のエントリはプライマリテーブルに追加される必要はない。
【０１０１】
プライマリテーブル１６３０の一実施形態が、図１６Ｃに示される。本図を参照すると、プライマリテーブル１６３０はいくつかのエントリ１６３２を含み、それぞれのエントリは１つのキー１６３７ａ及び１以上のビンポインタ１６３７ｂを持つ。パラレルＬＰＭサーチ（図１６Ｂを参照すること）において特定された第１及び第２インデックス１６９１、１６９２（Ｉ１及びＩ２）から生成されたキー１６９０は、プライマリテーブル１６３０をサーチするために使用される。キー１６９０がプライマリテーブルのエントリ１６３２のいずれかのキー１６３７ａとマッチする場合、そのエントリ内のビンポインタ１６３７ｂによって識別されるビンは、受信されたパケットに適用されるべき１つのアクション（例えば、プライオリティの最も高い１つのアクション）を発見すべくアクセスされる。プロセスは以下により詳細に説明される。１つのエントリ１６３２は、１つのスモールビン１６７０、又はそれに代えて複数のスモールビンの１つのグループ−すなわち、１つのフィルタ共通部分に対応する複数のスモールビンの１つの共通集合を持つ１つの"ラージビン"１６８０を指す。いくつかの実施形態では、例えばルールセットが連続するプライオリティレベルを占める複数のルールから成る場合に生じる結果として、プライマリテーブルの対応するエントリはラージビンに含まれる全てのスモールビンへのポインタを含むので、１つのラージビン１６８０が記憶されている必要はないということに注意すること。他の実施形態では、一方で、複数のラージビンが記憶されてよい（例えば、ルールセット内の複数のルールが非連続なプライオリティレベルを占める場合）。また、図１６Ｃに示されるように、トランスポートレベル共有の結果、複数のエントリ１６３２が、同じスモールビン（又は複数のビン）１６７０を示す又は共有してよい。
【０１０２】
セカンダリテーブル１６４０ａ、１６４０ｂのそれぞれは、プライマリテーブル１６３０と類似している。一方で、セカンダリテーブルの一方にアクセスするためのキーは、第３インデックス１６９３（Ｉ３）を含み、他方のセカンダリテーブルにアクセスするためのキーは第４インデックス１６９４（Ｉ４）を含む。プライマリテーブル１６３０上での問い合わせが１つのマッチを戻した場合、セカンダリテーブル１６４０ａ−ｂは無視され、プライマリテーブルのマッチしているエントリが最適マッチングフィルタに該当する。一方で、プライマリテーブルでマッチが発見されない場合、セカンダリテーブル１６４０ａ−ｂのうちの１つにおける１つの問い合わせが１つのマッチを戻し、このマッチしているエントリが最適マッチングフィルタに該当するだろう。プライマリ及びセカンダリテーブル１６３０上の複数のクエリが１つのマッチを戻さない場合には、全２次元フィルタ空間（すなわち"＊．＊"）に該当する１つのデフォルトフィルタが最適フィルタとして使用される。
【０１０３】
一実施形態では、プライマリテーブル１６３０及びセカンダリテーブル１６４０ａ、１６４０ｂは、ハッシュテーブルとして実装される。この実施形態では、プライマリ及びセカンダリハッシュテーブルをサーチするために用いられる１つのサーチキーを生成すべく、１つのハッシュ関数がキー（すなわち、キー１６９０或いは第３及び第４インデックス１６９３、１６９４）に適用されてよい。もちろん、ハッシュテーブルは、プライマリ及びセカンダリテーブル１６３０、１６４０ａ−ｂが実装される方法の単なる一例を表し、さらに他の代替のデータ構造が利用され得ることが理解されるべきである。
【０１０４】
ここで、一実施形態は図１７に示される第２ステージデータ構造１７００に着目する。第２ステージデータ構造１７００の構築は、上記のいくつかの概念によって導かれる。最初に最も重要なことには、トランスポートレベル共有は、第１ステージデータ構造内の複数のエントリに、トランスポートレベルフィールドの別個のセットのグループ、より厳密には、それぞれが１以上のトランスポートレベルフィールド、１つのアクション、及び１つの相対的プライオリティ（すなわち、ルールの絶対的プライオリティと区別される、１つのルールセット内の１つの相対的プライオリティ）を持つトリプレットのグループを共有させることを可能にする。したがって、トリプレットのグループのそれぞれ−すなわち、それぞれのスモールビン−は、一度記憶されさえすればよい。第２に、１つのフィルタ共通部分に関連する２以上のスモールビンの集合（union)は論理的には１つのラージビンとして考えられるが、第１ステージデータ構造１６００のプライマリ及びセカンダリテーブル１６３０、１６４０ａ−ｂは１つのエントリに関連する全てのスモールビンへのポインタを持つので、ラージビンは記憶される必要はない。繰り返すと、他の実施形態では、複数のラージビンは記憶されてもよい。トランスポートレベル共有により、第２ステージデータ構造１７００は、単に複数のスモールビンに組織化された複数のトリプレットの１つのリストになり、トランスポートレベル共有によって提供されるエントリの低減によって、第２ステージデータ構造１７００のためのメモリ記憶容量要件は他の分類技術と比較して相対的に小さい。
【０１０５】
図１７を参照すると、第２ステージデータ構造１７００はいくつかのトリプレット１７１０を持ち、それぞれのトリプレット１７１０は、１以上のトランスポートレベル（又は他の）フィールド１７１９ａ、１つのアクション１７１９ｂ、及び相対的プライオリティ１７１９ｃを持つ。それぞれのトリプレット１７１０は、１つのスモールビン１７２０（複数のスモールビン１７２０ａ、１７２０ｂ、・・・、７２０ｋのうちの１つ）と関係づけられている。スモールビン１７２０ａ−ｋは、トリプレット１７１０の複数のグループを持ち、１つのスモールビンが記憶されるメモリロケーションは、対応するポインタ１７２５によって特定され得る（すなわち、スモールビン１７２０ａは対応するポインタ１７２５ａによって特定され、スモールビン１７２０ｂは対応するポインタ１７２５ｂによって特定される等）。前述のように、ビンポインタ１７２５ａ−ｋは、フォワーディングテーブル１６０２に記憶される（図１６Ａを参照すること）。１つのスモールビン１７２０（又は、ラージビンが記憶されている場合には１つのラージビン）に関連するポインタ１７２５が第１ステージデータ構造１６００上の１つの問い合わせで特定された場合、対応するスモールビン１７２０内の全てのトリプレットは受信されたパケットに対して比較される。少なくとも１つのマッチが発見された場合、そのマッチしているトリプレットに関連するアクションが、受信されたパケットに適用され得る。一実施形態では、このアクションは生じた最も高いプライオリティを持つ。
【０１０６】
一実施形態では、この第２ステージデータ構造１７００は、ternary CAMのような内容参照可能メモリ（ＣＡＭ）に実装されてよい。この実施形態では、ＣＡＭは、それぞれが第２ステージデータ構造１７００のトリプレット１７１０のうちの１つと関連するいくつかのエントリを含む。第２ステージデータ構造１７００がＣＡＭに実装されたさらなる実施形態では、多くのＣＡＭエントリ（例えば、１以上のスモールビン１７２０に関連するトリプレット１７１０）はパラレルにサーチされてよい。
【０１０７】
図１８を参照すると、図１から１７及び上記の付随する本文において示された２ステージパケット分類を用いて実行されるような、パケット分類方法の一実施形態が示される。本図のブロック１８０５を参照すると、１つのパケットが受信される。ブロック１８１０ａ及び１８１０ｂで説明されるように、送信元アドレス上及び宛先アドレス上で１つのルックアップが実行される（図１４の部材１４１０、１４２０、及び図１６Ａの部材１６１０、１６２０を参照すること）。一実施形態では、図１８に示されるように、送信元及び宛先アドレス上で複数の問い合わせがパラレルに実行される。一方で、他の実施形態では、これらの問い合わせがパラレルに実行されなくてもよい。送信元アドレスでの問い合わせに基づいて、１つの完全指定フィルタに関連する最長プレフィックスマッチ（ＬＰＭ）及び１つの部分指定フィルタに関連するＬＰＭが特定され、これはブロック１８１５ａに示される。マッチしている完全指定フィルタに関連する１つのインデックスＩ１及びマッチしている部分指定フィルタに関連する１つのインデックスＩ３が戻される（図１６Ｂの部材１６９１、１６９３を参照すること）。同様に、宛先アドレスでの問い合わせから、１つの完全指定フィルタに関連する最長ＬＰＭ及び１つの部分指定フィルタに関連するＬＰＭが特定され−ブロック１８１５ｂを参照すること−、そしてマッチしている部分指定フィルタに関連する１つのインデックスＩ４だけでなくマッチしている完全指定フィルタに関連する１つのインデックスＩ２が戻される（図１６Ｂの部材１６９２、１６９４を参照すること）。
【０１０８】
そして、マッチしている完全指定フィルタに関連する２つのインデックスＩ１及びＩ２が、１つのキー（図１６Ｂの部材１６９０を参照すること）を形成すべく結合される（例えば、連結される）。そして、このキーは、プライマリテーブル（図１６Ａ及び１６Ｃの部材１６３０を参照すること）をサーチするために使用され、これはブロック１８２０ａに説明される。ブロック１８２０ｂ及び１８２０ｃを参照すると、インデックスＩ３はセカンダリテーブルのうちの１つをサーチするために使用され、インデックスＩ４は他方のセカンダリテーブルをサーチするために使用される（図１６Ａの部材１６４０ａ、１６４０ｂを参照すること）。繰り返すと、プライマリテーブル１６３０は、他のフィルタによって集約されない非存在フィルタ（すなわち、インジケータフィルタ）だけでなく、全ての完全指定フィルタ及び完全指定フィルタの複数の共通部分を持つ。セカンダリテーブル１６４０ａ、１６４０ｂのうちの１つは送信元アドレスにおいてワイルドカードを持つ部分指定フィルタを持ち、セカンダリテーブルの他方は宛先アドレスにおいてワイルドカードを持つ部分指定フィルタを持つが、複数のセカンダリテーブルにはインジケータフィルタは含まれない。一実施形態では、図１８に示されるように、プライマリ及びセカンダリテーブル１６３０、１６４０ａ−ｂ上でのサーチはパラレルに実行される。一方で、他の実施形態では、これらのサーチはパラレルに実行されなくてもよい。
【０１０９】
ブロック１８２５を参照すると、キー（Ｉ１及びＩ２から形成される）は、プライマリテーブル１６３０のエントリ１６３２のそれぞれのキー１６３７ａと比較される（図１６Ｃを参照すること）。１つのマッチが発見されると、ブロック１８３０に説明されるように、マッチしているエントリ内の複数のビンポインタ（又はポインタ）１６３７ｂがアクセスされる。Ｉ１及びＩ２から形成されるキーは、種々の方法でプライマリテーブルをサーチするために使用され得る。例えば、一実施形態では、１つのハッシュ関数がそのキーに適用され、そのハッシュが、ハッシュテーブルとして実装されているプライマリテーブル１６３０をサーチするために使用される。
【０１１０】
１つのマッチがプライマリテーブル１６３０内に発見された場合には、セカンダリテーブル１６４０ａ−ｂは無視される。プライマリテーブル内に１つのマッチが発見されず、セカンダリテーブルのうちの１つの中に１つのマッチが発見された場合には−ブロック１８３５を参照すること−、そのセカンダリテーブルのマッチしているエントリ内の（複数の）ビンポインタがアクセスされ、これはブロック１８４０に示される。（実際に、セカンダリテーブル内に１つのマッチが発見された場合には）セカンダリテーブルのうちの１つだけが１つのマッチしているエントリを持つことに注意すること。しかしながら、プライマリテーブル内又はいずれのセカンダリテーブルの中にもマッチが発見されない場合には、ブロック１８４５に説明されるように、全２次元アドレス空間に一致する１つのデフォルトエントリが使用され、このエントリの関連するビンポインタがアクセスされる。この時点で、受信されたパケットはそのネットワークパスに基づいて分類されており、処理は第２ステージ分類に移行する。
【０１１１】
ここでブロック１８５０を参照すると、ビンポインタのうちの１つによって特定される１つのスモールビン（又は、ある実施形態では、１つのラージビン）がアクセスされる。ブロック１８５５に説明されるように、受信されたパケットのトランスポートレベルフィールドはアクセスされたビンのそれぞれのエントリと比較され（図１７を参照すること）、アクセスされたビン内のエントリに１つのマッチしているエントリが存在しているか否かを判断する。ブロック１８６５に説明されるように、アクセスされたビンが１つのマッチしているエントリを持つ場合−ブロック１８６０を参照すること−、そのマッチしているエントリと関連するアクションが戻される。ブロック１８７０を参照すると、その戻されたアクションはその後パケットに適用される。
【０１１２】
上記のように、プライマリテーブル又はセカンダリテーブルのうちの１つの中の１つのエントリは、それぞれが１つのスモールビンを特定する複数のポインタを持ってよい（すなわち、言い換えると、そのエントリは１つのラージビンに関連する）。したがって、関連するビン内の全てのエントリを検討した後（ブロック１８５５を参照すること）、１つのマッチしているエントリが特定されない場合（ブロック１８６０を参照すること）、処理はまだ検討されていない任意の他の複数のビンポインタ（及び複数のビン）に注意を向ける（ブロック１８５０を参照すること）。問い合わせるべき追加のビンが存在する場合、１つのスモールビンをアクセスするための上記のプロセスが繰り返される（すなわち、ブロック１８５０、１８５５、及び１８６０）。したがって、アクセスされていないビンポインタが残っている限り、１つのスモールビンをアクセスしてサーチするための処理が、１つのマッチが発見されるまで繰り返される。
【０１１３】
ここで図１５に戻ると、前述のように、他のフィルタで集約されないＲ２のような複数の領域−すなわち"インジケータフィルタ"−が、プライマリテーブル１６３０に追加される（しかしながら、セカンダリテーブル１６４０ａ−ｂ内には配置されない）。完全指定フィルタ又はフィルタ共通部分は、多くのインジケータフィルタを含む。このことは、１つの完全指定フィルタ（又はフィルタ共通部分）１９１０及び多くの他の"より狭い"完全指定フィルタ（又はフィルタ共通部分）１９２０を示す図１９に図示される。１つの完全指定の狭いフィルタ１９２０の送信元アドレスを、他の狭いフィルタ１９２０の宛先アドレスと結合することは−繰り返すと、上記したように、送信元アドレス及び宛先アドレスのルックアップテーブル上での複数の問い合わせが独立に実行されることによって生じる結果である−、フィルタ１９１０に完全に含まれ、それゆえ他のフィルタでは集約されない多くの非存在フィルタ１９３０を生成する。したがって、これらのインジケータフィルタ１９３０は、一実施形態では、プライマリテーブル１６３０に配置される。一方で、更なる他の実施形態では、任意の完全指定フィルタに関連するインジケータフィルタ数に１つの上限が設けられる。インジケータフィルタのこの指定された上限を超えるいずれの完全指定フィルタ又はフィルタ共通部分については、そのフィルタ及びその関連するインジケータフィルタはプライマリテーブル１６３０に配置されない。図１９の完全指定フィルタ１９１０のような、比較的多数のインジケータフィルタを囲んでいるフィルタは、そのようなフィルタは典型的には広範囲の送信元及び宛先アドレスにわたるので、"ワイド"フィルタと呼ばれる。
【０１１４】
上記の実施形態は、図２０Ａから２０Ｃにさらに図示される。図２０Ａ、２０Ｂ、及び２０Ｃは図１６Ａ、１６Ｂ、及び１８にそれぞれ類似しており、類似の構成要素は図２０Ａ−２０Ｃにおいて同じ数値表示を持つ。また、上記において既に説明した構成要素の記載は、いくつかの構成要素について以下の本文では繰り返されない。
【０１１５】
最初に図２０Ａを参照すると、インジケータフィルタの指定された境界を越えるフィルタ−すなわちワイドフィルタ−は、ここでワイドフィルタテーブル１６５０と呼ばれる別のデータ構造に配置さられる。ワイドフィルタテーブル１６５０は、それぞれのワイドフィルタについて１つのエントリを持つ。一実施形態では、ワイドフィルタテーブル１６５０は、クロス積テーブルに類似するデータ構造を持つ（図１５及び１９を参照すること）。最も現実的な分類データベースのためには、ワイドフィルタの数は小さいことが期待される。しかしながら、１つのワイドフィルタはプライマリテーブル１６３０内に多数のエントリを生成する可能性があるので、これらのワイドフィルタを（プライマリ及びセカンダリテーブルでパラレルにサーチされる）別個のデータ構造に移動させることは、分類プロセスの効率を著しく向上させることができる。
【０１１６】
次に図２０Ｂを参照すると、既に説明したように、分類の第１ステージの間で、４つの異なるインデックス１６９１、１６９２、１６９３、１６９４（Ｉ１からＩ４）が送信元及び宛先アドレステーブル１６１０、１６２０への問い合わせからそれぞれ戻される。上記されたように、第１及び第２インデックス１６９１、１６９２は、完全指定フィルタに関連するマッチしている送信元及び宛先プレフィックスに該当し、第３及び第４インデックス１６９３、１６９４は、部分指定フィルタに関連するマッチしている送信元及び宛先プレフィックスに該当する。ワイドフィルタを説明するこの実施形態では、送信元及び宛先アドレステーブル１６１０、１６２０上の複数の問い合わせは、１つの第５インデックス１６９５（Ｉ５）及び１つの第６インデックス１６９６（Ｉ６）も戻す。第５インデックス１６９５は、１つのワイドフィルタに関連するマッチしている送信元プレフィックスに該当し、第６インデックス１６９６は、１つのワイドフィルタに関連するマッチしている宛先プレフィックスに該当する。送信元アドレステーブル１６１０及び宛先アドレステーブル１６２０のそれぞれにおいて、フィルタタイプ指定１６１４ｂ、１６２４ｂは、そのエントリが１つの完全指定フィルタ、１つの部分指定フィルタ、又は１つのワイドフィルタに関連しているかを示す。以下に説明されるように、第５インデックス１６９５及び第６インデックス１６９６（Ｉ５及びＩ６）は結合されて、ワイドフィルタテーブル１６５０に問い合わせするために使用される１つのキー２０２０を形成する。
【０１１７】
図２０Ｃには、第２ステージパケット分類のための方法１８００の他の実施形態が示される。図２０Ｃに示される実施形態は、図１８に関連して既に説明された実施形態と略同一の方法で進行する。しかしながら、図２０Ｃに示される方法はワイドフィルタを説明し、上記したように、本実施形態はワイドフィルタテーブル１６５０並びに第５及び第６ワイドフィルタインデックス１６９５、１６９６を利用する。
【０１１８】
図２０Ｃに転じて、パケットが受信され（ブロック１８０５を参照すること）、ブロック１８１０ａ、１８１０ｂに説明されるように、送信元及び宛先アドレス上でルックアップが実行される。ブロック１８１５ａに示されるように、送信元アドレスの問い合わせに基づいて、１つの完全指定フィルタに関連する最長プレフィックスマッチ（ＬＰＭ）、１つの部分指定フィルタに関連するＬＰＭ、及び１つのワイドフィルタに関連するＬＰＭが特定され、インデックスＩ１、Ｉ３、及びＩ５が戻される（図２０Ｂ、部材１６９１、１６９３、１６９５を参照すること）。繰り返すと、Ｉ１はマッチしている完全指定フィルタに関連し、Ｉ３はマッチしている部分指定フィルタに関連し、Ｉ５はマッチしているワイドフィルタに関連する。同様に、宛先アドレスでの問い合わせから、１つの完全指定フィルタに関連する最長ＬＰＭ、１つの部分指定フィルタに関連するＬＰＭ、及び１つのワイドフィルタに関連するＬＰＭが特定され−ブロック１８１５ｂを参照すること−、そしてマッチしているワイドフィルタに関連する１つのインデックスＩ６だけでなく、マッチしている完全指定フィルタに関連する１つのインデックスＩ２、マッチしている部分指定フィルタに関連する１つのインデックスＩ４が戻される（図２０Ｂの部材１６９２、１６９４、１６９６を参照すること）。
【０１１９】
ブロック１８２０ａ、１８２０ｂ、及び１８２０ｃに説明されるように、前述したようにマッチしている完全指定フィルタに関連する２つのインデックスＩ１及びＩ２が、プライマリテーブルをサーチするために使用される１つのキーを形成すべく結合され、インデックスＩ３及びＩ４はセカンダリテーブルをサーチするために使用される。さらに、１つのキーを形成すべくインデックスＩ５及びＩ６が結合され（図２０Ｂの部材２０９０を参照すること）、そしてこのキーはワイドフィルタテーブル１６５０上の１つの問い合わせのために使用され、これはブロック１８２０ｄに説明される。一実施形態では、図２０Ｂに示されるように、プライマリテーブル１６３０、セカンダリテーブル１６４０ａ−ｂ、及びワイドフィルタテーブル１６５０上でのサーチはパラレルに実行される。一方で、他の実施形態では、これらのサーチはパラレルに実行されなくてもよい。
【０１２０】
ブロック１８２５を参照すると、キー（Ｉ１及びＩ２から形成される）は、プライマリテーブル１６３０のエントリ１６３２のそれぞれのキー１６３７ａと比較され（図１６Ｃを参照すること）、１つのマッチが発見されると、ブロック１８３０に説明されるように、マッチしているエントリ内の複数のビンポインタ（又はポインタ）１６３７ｂがアクセスされる。本実施形態では、一方で、プライマリテーブル内に１つのマッチが発見されない場合、処理はワイドフィルタテーブルへと転じて−ブロック１８８５を参照すること−、キー（Ｉ５及びＩ６から形成される）がワイドフィルタテーブル内のそれぞれのエントリと比較される。ブロック１８９０に示されるように、ワイドフィルタテーブル内に１つのマッチが発見された場合、ワイドフィルタテーブルのマッチしているエントリ内の複数のビンポインタがアクセスされる。ブロック１８４０に示されるように、プライマリテーブルおよびワイドテーブルのいずれの中にも１つのマッチも発見されず、セカンダリテーブルのうちの１つの中に１つのマッチが発見された場合には−ブロック１８３５を参照すること−、そのセカンダリテーブルのマッチしているエントリ内の（複数の）ビンポインタがアクセスされる。プライマリテーブル、ワイドフィルタテーブル、又はいずれのセカンダリテーブルにもマッチが発見されない場合には、ブロック１８４５に説明されるように、全２次元アドレス空間に一致する１つのデフォルトエントリが使用され、このエントリの関連するビンポインタがアクセスされる。１つのマッチがプライマリテーブル１６３０内に発見された場合には、他の複数のテーブルは無視され、プライマリテーブルにマッチが見いだされず、１つのマッチがワイドフィルタテーブル１６５０内に発見された場合には、セカンダリテーブル１６４０ａ−ｂが無視される。受信されたパケットのネットワークパスに基づく分類は完了し、処理は第２ステージ分類に移行する。第２ステージは前述と同様の方法で進行するので、図２０Ｃにおいては、パケット分類の第２ステージは示されていないことに注意すべきである。
【０１２１】
ここで、第１及び第２ステージデータ構造を生成及び／又は更新するための方法の実施形態に注意を向ける。図２１を参照すると、上記の２ステージパケット分類プロセスのために使用されるデータ構造を生成及び／又は更新するための方法の実施形態が示される。図２１で説明されるプロセスは、パケット分類に先立って（又は、一実施形態では、パケット分類の間に）実行される複数のプロセッサリプロセッシングオペレーションの１つのセットを有することに注意すべきである。一方で、開示された２ステージパケット分類スキームに必要なデータ構造（例えば、第１及び第２データ構造１６００、１７００）を生成及び／又は更新することは、パケットを分類するプロセスと比較して稀にしか実行されないだろう。したがって、開示された分類技術を実行するのに必要なプロセッシングの大部分は、比較的稀にしか実行される必要がない一連のプロセッサリプロセッシングオペレーションに対してずっと前倒しされる。
【０１２２】
ここで図２１のブロック２１１０を参照すると、分類データベースの複数のルール（図１０を参照すること）は複数のルールセットにグループ化され、それぞれのルールセット内の複数のルールは同じ送信元及び宛先アドレスを持つ（図１１Ａ及び１１Ｂを参照すること）。上記したように、一実施形態では、１つのルールセットの複数のルールは連続するプライオリティレベルを占めるが、他の実施形態では、１つのルールセットの複数のルールは隣接するプライオリティレベルを占めなくてよい。上記したように、それぞれのルールセットに関連する送信元−宛先ペアはフィルタと呼ばれる。ブロック２１２０で説明されるように、対応するアクション及び相対的プライオリティだけでなく、それぞれのフィルタに関連するトランスポートレベル（又は他の）フィールドのセットは１つのスモールビンに組織化される。
【０１２３】
ブロック２１３０を参照すると、受信されたパケットの送信元及び宛先アドレス上のパラレルＬＰＭ問い合わせのために使用される送信元アドレスルックアップデータ構造及び宛先アドレスルックアップデータ構造が生成される（図１６Ａ及び１６Ｂの部材１６０１を参照すること）。送信元アドレスルックアップデータ構造は、データベース内のそれぞれのフィルタ用の１つのエントリを持ち、それぞれのフィルタ用のエントリは１つの送信元プレフィックス、１つのフィルタタイプ指定（例えば、完全指定、部分指定、又はワイドであるか）、及び１つのインデックスを持つ。同様に、宛先アドレスルックアップデータ構造は、データベース内のそれぞれのフィルタ用の１つのエントリを持ち、それぞれのフィルタ用のエントリはそのフィルタのための１つの宛先プレフィックス、１つのフィルタタイプ指定、及び１つのインデックスを持つ。
【０１２４】
第１ステージデータ構造を完成すべく、フォワーディングテーブルが構築される（図１６Ａの部材１６０２を参照すること）。ブロック２１４０に説明されるように、複数のフィルタ共通部分が決定され（図１２Ａ−１２Ｃを参照すること）、それぞれのフィルタ共通部分に関連する複数のスモールビンの集合−すなわち、１つのラージビン−が発見される（図１１Ｂを参照すること）。ブロック２１５０に説明されるように、複数のインジケータフィルタも決定される。上記したように、複数のインジケータフィルタは、他のフィルタで集約され得ない非存在フィルタである（図１５及び付随する本文を参照すること）。複数の完全指定フィルタ、複数の完全指定フィルタ共通部分、及び複数のインジケータフィルタが、プライマリテーブルに配置され（図１６Ａ及び１６Ｃを参照すること）、これはブロック２１６０に説明される。繰り返すと、一実施形態では、完全にオーバーラップしている複数のフィルタ共通部分（図１３Ａ−１３Ｃを参照すること）は、プライマリテーブルに配置されない。ブロック２１７０を参照すると、複数のセカンダリテーブルが生成され、１つのセカンダリテーブルは"Ｘ＊，＊"の形式の複数の部分指定フィルタを持ち、他方のセカンダリテーブルは"＊，Ｙ＊"の形式の複数の部分指定フィルタを持つ。他の実施形態では、複数のワイドフィルタ−例えば、１つの指定された閾値を超えている多数のインジケータフィルタを持つフィルタ（図１９を参照すること）−が他のテーブル−１つのワイドフィルタテーブル（図２０Ａの部材１６５０を参照すること）−に配置され、これはブロック２１９０によって示される。
【０１２５】
ブロック２１８０を参照すると、第２ステージデータ構造が生成される。先に説明したように、一実施形態では、第２ステージデータ構造は、それぞれのスモールビンと関連するトリプレットのセットを持つ（図１７を参照すること）。スモールビンは、プライマリ及びセカンダリテーブルに含まれるポインタによって特定される。本実施形態では、複数のラージビンは第２ステージデータ構造内に記憶されず、むしろ、複数のラージビンは、２以上のスモールビンへの（１つのプライマリ又はセカンダリテーブルの１つのエントリ内の）複数のポインタの１つのリストによって単に特定される。（例えば連続しないプライオリティレベルの複数のルールをルールセットが持つ）他の実施形態では、複数のラージビンに関連するトリプレットのグループがメモリに記憶される。
【０１２６】
−２ステージ分類スキームを実装するために使用され得るデータ構造の複数の実施形態だけでなく−最適フィルタマッチング及びトランスポートレベル共有を使用する２ステージパケット分類のための方法の複数の実施形態がここで説明され、当業者は開示された複数の実施形態の利点を理解するだろう。トランスポートレベル共有は、記憶されるべきトリプレットの数を著しく低減することができ、これは、開示された２ステージ分類スキームのメモリ記憶容量要件を低減する。また、ＴＬＳから得られる低減された記憶容量要件によって、第２ステージデータ構造は、内容参照可能メモリ（又は他のハードウェアアーキテクチャ）での実装に対して容易に修正可能となる。さらに、最適フィルタマッチングをパケット分類の第１ステージに組み込むことは−ＴＬＳの使用と同様に−、パケットを分類するのに必要なメモリアクセス数を低減することができる。さらに、開示された２ステージ分類技術によって要求されるデータプロセッシングの大部分は、多くのプリプロセッシングオペレーション（例えば、第１及び第２ステージデータ構造の生成）に対してずっと前倒しされる。そのようなオペレーションは比較的稀にしか実行されない。
【０１２７】
上記の詳細な説明及び添付の図面は、単なる実例であり限定的ではない。それらは開示された実施形態の明確で包括的な理解のために主として提供され、それらから本質的でない限定が解釈されるべきではない。開示された実施形態の趣旨及び添付の特許請求の範囲から逸脱することなく、ここで説明された実施形態に多数の追加、削除、及び変更が、他の構成のみならず当業者によって考案され得る。
【図１】
2007509535.tif 000003
【図２】
2007509535.tif 000004
【図３】
2007509535.tif 000005
【図４】
2007509535.tif 000006
【図５Ａ】
2007509535.tif 000007
【図５Ｂ】
2007509535.tif 000008
【図５Ｃ】
2007509535.tif 000009
【図６】
2007509535.tif 000010
【図７】
2007509535.tif 000011
【図８】
2007509535.tif 000012
【図９】
2007509535.tif 000013
【図１０】
2007509535.tif 000014
【図１１Ａ】
2007509535.tif 000015
【図１１Ｂ】
2007509535.tif 000016
【図１２Ａ】
2007509535.tif 000017
【図１２Ｂ】
2007509535.tif 000018
【図１２Ｃ】
2007509535.tif 000019
【図１３Ａ】
2007509535.tif 000020
【図１３Ｂ】
2007509535.tif 000021
【図１３Ｃ】
2007509535.tif 000022
【図１４】
2007509535.tif 000023
【図１５】
2007509535.tif 000024
【図１６Ａ】
2007509535.tif 000025
【図１６Ｂ】
2007509535.tif 000026
【図１６Ｃ】
2007509535.tif 000027
【図１７】
2007509535.tif 000028
【図１８】
2007509535.tif 000029
【図１９】
2007509535.tif 000030
【図２０Ａ】
2007509535.tif 000031
【図２０Ｂ】
2007509535.tif 000032
【図２０Ｃ】
2007509535.tif 000033
【図２１】
2007509535.tif 000034
【国際調査報告】
2007509535.tif 000035
2007509535.tif 000036
2007509535.tif 000037