(57)【要約】【課題】二段パケット分類の方法と装置である。【解決手段】ソフトウェア実装ができる第一段においては、パケットを該パケットのネットワーク経路、およびもしかするとそのプロトコルに基づいて分類する。ハードウェア実装ができる第二段においては、該パケットを該パケットの一以上の移送レベルフィールドに基づいて分類する。二段パケット分類装置は第一段コード実行のための処理システム、分類の第二段を実行するための分類回路、および幾つかのビンを記憶するためのメモリを含むことができ、各ビンには一以上の規則が含まれる。【選択図】図２２
2007533207.tif 000002
【特許請求の範囲】
【請求項１】
方法であって、
メモリに記憶された複数のビンを提供する工程であって、前記ビンの各々は幾つかの規則を含み、各規則は送信元ポート範囲と送信先ポート範囲とを指定している工程と、
前記複数のビンから、受信パケットのネットワーク経路とプロトコルとに対応するビンを特定する工程と、
前記受信パケットの送信元ポートと送信先ポートとを、前記対応するビンの前記幾つかの規則と比較する工程と、
前記受信パケットの前記送信元ポートが規則の送信元ポート範囲に在り、前記受信パケットの前記送信先ポートが該規則の送信先ポート範囲に在る場合、該規則に対応付けられた動作を前記受信パケットに適用する工程とを含む、方法。
【請求項２】
前記受信パケットの前記送信元・送信先ポートに整合する前記規則は最高優先度規則を含む、請求項１に記載の方法。
【請求項３】
各規則の前記送信元ポート範囲は送信元ポートの下限と送信元ポートの上限とにより指定され、
各規則の前記送信先ポート範囲は送信先ポートの下限と送信先ポートの上限とにより指定される、請求項１に記載の方法。
【請求項４】
前記パケットの送信元ポートが規則の前記送信元ポートの下限より大きいまたは等しく、前記規則の前記送信元ポートの上限よりも小さいまたは等しい場合に、前記受信パケットの前記送信元ポートは前記規則の前記送信元ポート範囲内にあり、
前記パケットの送信先ポートが前記規則の前記送信先ポートの下限よりも大きいまたは等しく、前記規則の前記送信先ポートの上限よりも小さいまたは等しい場合に、前記受信パケットの前記送信先ポートは前記規則の前記送信先ポート範囲内にある、請求項３に記載の方法。
【請求項５】
受信パケットのネットワーク経路とプロトコルとに対応するビンを特定する工程は、
データ構成のうちの幾つかの入力の中から、前記受信パケットの送信元アドレスに整合する送信元アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第一識別子を含むことと、
別のデータ構成のうちの幾つかの入力の中から、前記受信パケットの送信先アドレスに整合する送信先アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第二識別子を含むことと、
前記幾つかのビンの中から、前記第一および第二識別子と前記プロトコルとに対応するビンを特定することとを含む、請求項１に記載の方法。
【請求項６】
受信パケットのネットワーク経路とプロトコルとに対応するビンを特定する工程は、
第一インデックスと第三インデックスとを探すべく送信元アドレスデータ構成を検索することであって、前記第一インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ完全指定フィルタと関連付けられており、前記第三インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ部分指定フィルタと関連付けられていることと、
第二インデックスと第四インデックスとを探すべく送信先アドレスデータ構成を検索することであって、前記第二インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ完全指定フィルタと関連付けられており、前記第四インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ部分指定フィルタと関連付けられていることと、
前記第一インデックス、前記第二インデックス、及び前記プロトコルから鍵を形成することと、
前記鍵に整合する入力を探すべく第一表を検索することであって、前記第一表は幾つかの入力を含み、各入力は完全指定フィルタ、完全指定フィルタ交差部、および指標フィルタのうちの一つと対応していることとを含み、
前記鍵に整合する前記第一表の入力は前記対応するビンを特定している、請求項１に記載の方法。
【請求項７】
前記第三インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく第二表のうちの第一のものを検索する工程であって、前記第一の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応している工程と、
前記第四インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく前記第二表のうちの第二のものを検索する工程であって、前記第二の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応する工程とをさらに含み、
前記第一表に整合が見つからない場合、前記二つの第二表のうち一つの整合する入力が前記対応するビンを特定する、請求項６に記載の方法。
【請求項８】
前記第一表あるいは前記第二表のうちのいずれにも整合が見つからない場合、前記対応するビンは二次元アドレス空間全体に関連付けられているデフォルトビンを含む、請求項７に記載の方法。
【請求項９】
前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つワイドフィルタに関連付けられた第五インデックスを探すべく前記送信元アドレスデータ構成を検索する工程と、
前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つワイドフィルタに関連付けられた第六インデックスを探すべく前記送信先アドレスデータ構成を検索する工程と、
前記第五インデックス、前記第六インデックス、および前記プロトコルとから第二の鍵を形成する工程と、
前記第二の鍵に整合する入力を探すべくワイドフィルタ表を検索する工程であって、前記ワイドフィルタ表は幾つかの入力を含み、各入力がワイドフィルタに対応している工程とをさらに含み、
前記第一表に整合が見つからない場合、前記ワイドフィルタ表の整合する入力が前記対応するビンを特定する、請求項６に記載の方法。
【請求項１０】
前記ワイドフィルタ表に含まれる各ワイドフィルタは、指定された閾値を越える幾つかの指標フィルタを持つ完全指定フィルタを含む、請求項９に記載の方法。
【請求項１１】
方法であって、
メモリに記憶されている複数のビンから、受信パケットのネットワーク経路に対応するビンを特定する工程であって、前記複数のビンの各々は幾つかの規則を含む工程と、
前記対応するビンを特定する命令を分類回路に発行する工程と、
前記対応するビンの前記規則を前記メモリから前記分類回路へコピーする工程であって、前記分類回路は前記受信パケットの少なくとも一つの移送レベルフィールドを前記規則の各々と比較し、一つの規則が前記パケットの前記少なくとも一つの移送レベルフィールドと整合している場合に整合信号を提供する工程と、
前記整合信号に応じて、前期整合している規則と関連付けられている動作を前記受信パケットに適応する工程とを含む、方法。
【請求項１２】
前記整合している規則には最高優先度整合規則が含まれる、請求項１１に記載の方法。
【請求項１３】
前記受信パケットの前記少なくとも一つの移送レベルフィールドは、送信元ポートと送信先ポートとを含む、請求項１１に記載の方法。
【請求項１４】
ビンの各規則は送信元ポートの下限と、送信元ポートの上限と、送信先ポートの下限と、送信先ポートの上限とを含む、請求項１３に記載の方法。
【請求項１５】
一つの規則が前記パケットの前記少なくとも一つの移送レベルフィールドに整合する場合は、
前記受信パケットの前記送信元ポートが前記規則の前記送信元ポートの下限より大きいまたは等しく、前記規則の前記送信元ポートの上限よりも小さいまたは等しく、
前記受信パケットの前記送信先ポートが前記規則の前記送信先ポートの下限より大きいまたは等しく、前記規則の前記送信先ポートの上限よりも小さいまたは等しい場合である、請求項１４に記載の方法。
【請求項１６】
前記対応するビンは前記受信パケットに関連付けられたプロトコルとさらに対応している、請求項１１に記載の方法。
【請求項１７】
受信パケットのネットワーク経路に対応するビンを特定する工程は、
データ構成のうちの幾つかの入力の中から、前記受信パケットの前記送信元アドレスに整合する送信元アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第一識別子を含むことと、
別のデータ構成のうちの幾つかの入力の中から、前記受信パケットの前記送信先アドレスに整合する送信先アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第二識別子を含むことと、
前記幾つかのビンの中から、前記第一および第二識別子と前記プロトコルとに対応するビンを特定することとを含む、請求項１６に記載の方法。
【請求項１８】
受信パケットのネットワーク経路に対応するビンを特定する工程は、
第一インデックスと第三インデックスとを探すべく送信元アドレスデータ構成を検索することであって、前記第一インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ完全指定フィルタと関連付けられており、前記第三インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ部分指定フィルタと関連付けられていることと、
第二インデックスと第四インデックスとを探すべく送信先アドレスデータ構成を検索することであって、前記第二インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ完全指定フィルタと関連付けられており、前記第四インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ部分指定フィルタと関連付けられていることと、
前記第一インデックス、前記第二インデックス、及び前記プロトコルから鍵を形成することと、
前記鍵に整合する入力を探すべく第一表を検索することであって、前記第一表は幾つかの入力を含み、各入力は完全指定フィルタ、完全指定フィルタ交差部、および指標フィルタのうちの一つと対応していることとを含み、
前記鍵に整合する前記第一表の入力は前記対応するビンを特定している、請求項１６に記載の方法。
【請求項１９】
前記第三インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく第二表のうちの第一のものを検索する工程であって、前記第一の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応している工程と、
前記第四インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく前記第二表のうちの第二のものを検索する工程であって、前記第二の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応する工程とをさらに含み、
前記第一表に整合が見つからない場合、前記二つの第二表のうち一つの整合する入力が前記対応するビンを特定する、請求項１８に記載の方法。
【請求項２０】
前記第一表あるいは前記第二表のうちのいずれにも整合が見つからない場合、前記対応するビンは二次元アドレス空間全体に関連付けられているデフォルトビンを含む、請求項１９に記載の方法。
【請求項２１】
前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つワイドフィルタに関連付けられた第五インデックスを探すべく前記送信元アドレスデータ構成を検索する工程と、
前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つワイドフィルタに関連付けられた第六インデックスを探すべく前記送信先アドレスデータ構成を検索する工程と、
前記第五インデックス、前記第六インデックス、および前記プロトコルとから第二の鍵を形成する工程と、
前記第二の鍵に整合する入力を探すべくワイドフィルタ表を検索する工程であって、前記ワイドフィルタ表は幾つかの入力を含み、各入力がワイドフィルタに対応している工程とをさらに含み、
前記第一表に整合が見つからない場合、前記ワイドフィルタ表の整合する入力が前記対応するビンを特定する、請求項１８に記載の方法。
【請求項２２】
前記ワイドフィルタ表に含まれる各ワイドフィルタは、指定された閾値を越える幾つかの指標フィルタを持つ完全指定フィルタを含む、請求項２１に記載の方法。
【請求項２３】
装置であって、
メモリであって、複数のビンを記憶しており、各ビンが幾つかの規則を含むメモリと、
前記複数のビンから、受信パケットのネットワーク経路に対応するビンを特定するようプログラムされた処理システムと、
前記メモリと前記処理システムとに連結された分類回路であって、前記対応するビンの前記幾つかの規則のなかから、前記パケットの少なくとも一つの移送レベルフィールドに整合する規則を特定するための分類回路とを含む、装置。
【請求項２４】
前記少なくとも一つの移送レベルフィールドに整合する前記規則には最高優先度整合規則が含まれる、請求項２３に記載の装置。
【請求項２５】
前記パケットの前記少なくとも一つの移送レベルフィールドは、送信元ポートと送信先ポートとを含み、
ビンの各規則は送信元ポートの下限と、送信元ポートの上限と、送信先ポートの下限と、送信先ポートの上限とを含む、請求項２３に記載の装置。
【請求項２６】
前記分類回路は、
前記受信パケットの前記送信元ポートを、前記幾つかの規則のうち一つの前記送信元ポートの下限と上限と比較するための第一比較回路と、
前記受信パケットの前記送信先ポートを、前記規則の前記送信先ポートの下限と上限と比較するための第二比較回路と、
前記対応するビンの規則が前記受信パケットの前記送信元ポートおよび送信先ポートに整合する場合、整合信号を出力する出力回路とを含む、請求項２５に記載の装置。
【請求項２７】
前記規則が前記受信パケットの前記送信元ポート及び送信先ポートに整合する場合は、
前記受信パケットの前記送信元ポートが前記規則の前記送信元ポートの下限より大きいまたは等しく、前記規則の前記送信元ポートの上限よりも小さいまたは等しく、
前記受信パケットの前記送信先ポートが前記規則の前記送信先ポートの下限より大きいまたは等しく、前記規則の前記送信先ポートの上限よりも小さいまたは等しい場合である、請求項２６に記載の装置。
【請求項２８】
前記対応するビンは前記受信パケットに関連付けられたプロトコルとさらに対応している、請求項２３に記載の装置。
【請求項２９】
受信パケットのネットワーク経路に対応するビンを特定するべく、前記処理システムは、
データ構成のうちの幾つかの入力の中から、前記受信パケットの前記送信元アドレスに整合する送信元アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第一識別子を含むことと、
別のデータ構成のうちの幾つかの入力の中から、前記受信パケットの前記送信先アドレスに整合する送信先アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第二識別子を含むことと、
前記幾つかのビンの中から、前記第一および第二識別子と前記プロトコルとに対応するビンを特定することとを含む操作を行うようプログラムされている、請求項２８に記載の装置。
【請求項３０】
受信パケットのネットワーク経路に対応するビンを特定するべく、前記処理システムは、
第一インデックスと第三インデックスとを探すべく送信元アドレスデータ構成を検索することであって、前記第一インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ完全指定フィルタと関連付けられており、前記第三インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ部分指定フィルタと関連付けられていることと、
第二インデックスと第四インデックスとを探すべく送信先アドレスデータ構成を検索することであって、前記第二インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ完全指定フィルタと関連付けられており、前記第四インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ部分指定フィルタと関連付けられていることと、
前記第一インデックス、前記第二インデックス、及び前記プロトコルから鍵を形成することと、
前記鍵に整合する入力を探すべく第一表を検索することであって、前記第一表は幾つかの入力を含み、各入力は完全指定フィルタ、完全指定フィルタ交差部、および指標フィルタのうちの一つと対応していることとを含む操作を行うようプログラムされており、
前記鍵に整合する前記第一表の入力は前記対応するビンを特定している、請求項２８に記載の装置。
【請求項３１】
受信パケットのネットワーク経路に対応するビンを特定するべく、前記処理システムは、
前記第三インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく第二表のうちの第一のものを検索することであって、前記第一の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応していることと、
前記第四インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく前記第二表のうちの第二のものを検索することであって、前記第二の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応することとをさらに含む操作を行うようプログラムされており、
前記第一表に整合が見つからない場合、前記二つの第二表のうち一つの整合する入力が前記対応するビンを特定する、請求項３０に記載の装置。
【請求項３２】
前記第一表あるいは前記第二表のうちのいずれにも整合が見つからない場合、前記対応するビンは二次元アドレス空間全体に関連付けられているデフォルトビンを含む、請求項３１に記載の装置。
【請求項３３】
受信パケットのネットワーク経路に対応するビンを特定するべく、前記処理システムは、
前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つワイドフィルタに関連付けられた第五インデックスを探すべく前記送信元アドレスデータ構成を検索することと、
前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つワイドフィルタに関連付けられた第六インデックスを探すべく前記送信先アドレスデータ構成を検索することと、
前記第五インデックス、前記第六インデックス、および前記プロトコルとから第二の鍵を形成することと、
前記第二の鍵に整合する入力を探すべくワイドフィルタ表を検索することであって、前記ワイドフィルタ表は幾つかの入力を含み、各入力がワイドフィルタに対応していることとをさらに含む操作を行うようプログラムされており、
前記第一表に整合が見つからない場合、前記ワイドフィルタ表の整合する入力が前記対応するビンを特定する、請求項３０に記載の装置。
【請求項３４】
前記ワイドフィルタ表に含まれる各ワイドフィルタは、指定された閾値を越える幾つかの指標フィルタを持つ完全指定フィルタを含む、請求項３３に記載の装置。
【請求項３５】
前記メモリ、前記処理システム、および前記分類回路は単一の処理機器を含む、請求項２３に記載の装置。
【請求項３６】
システムであって、
バスと、
前記バスと連結された処理機器であって、
メモリであって、複数のビンを記憶しており、各ビンが幾つかの規則を含むメモリと、
前記複数のビンから、受信パケットのネットワーク経路に対応するビンを特定するようプログラムされた処理エンジンと、
前記メモリと前記処理エンジンとに連結された分類回路であって、前記対応するビンの前記幾つかの規則のなかから、前記パケットの少なくとも一つの移送レベルフィールドに整合する規則を特定するための分類回路とを含む処理機器と、
前記バスに連結され、前記システムを光リンクに連結するためのネットワークインターフェースとを含む、システム。
【請求項３７】
前記少なくとも一つの移送レベルフィールドに整合する前記規則には最高優先度整合規則が含まれる、請求項３６に記載のシステム。
【請求項３８】
前記パケットの前記少なくとも一つの移送レベルフィールドは、送信元ポートと送信先ポートとを含み、
ビンの各規則は送信元ポートの下限と、送信元ポートの上限と、送信先ポートの下限と、送信先ポートの上限とを含む、請求項３６に記載のシステム。
【請求項３９】
前記分類回路は、
前記受信パケットの前記送信元ポートを、前記幾つかの規則うち一つの前記送信元ポートの下限と上限と比較するための第一比較回路と、
前記受信パケットの前記送信先ポートを、前記規則の前記送信先ポートの下限と上限と比較するための第二比較回路と、
前記対応するビンの規則が前記受信パケットの前記送信元ポートおよび送信先ポートに整合する場合、整合信号を出力する出力回路とを含む、請求項３８に記載のシステム。
【請求項４０】
前記規則が前記受信パケットの前記送信元ポート及び送信先ポートに整合する場合は、
前記受信パケットの前記送信元ポートが前記規則の前記送信元ポートの下限より大きいまたは等しく、前記規則の前記送信元ポートの上限よりも小さいまたは等しく、
前記受信パケットの前記送信先ポートが前記規則の前記送信先ポートの下限より大きいまたは等しく、前記規則の前記送信先ポートの上限よりも小さいまたは等しい場合である、請求項３９に記載のシステム。
【請求項４１】
前記対応するビンは前記受信パケットに関連付けられたプロトコルとさらに対応している、請求項３６に記載のシステム。
【請求項４２】
受信パケットのネットワーク経路に対応するビンを特定するべく、前記処理システムは、
データ構成のうちの幾つかの入力の中から、前記受信パケットの前記送信元アドレスに整合する送信元アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第一識別子を含むことと、
別のデータ構成のうちの幾つかの入力の中から、前記受信パケットの前記送信先アドレスに整合する送信先アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第二識別子を含むことと、
前記幾つかのビンの中から、前記第一および第二識別子と前記プロトコルとに対応するビンを特定することとを含む操作を行うようプログラムされている、請求項４１に記載のシステム。
【請求項４３】
受信パケットのネットワーク経路に対応するビンを特定するべく、前記処理エンジンは、
第一インデックスと第三インデックスとを探すべく送信元アドレスデータ構成を検索することであって、前記第一インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ完全指定フィルタと関連付けられており、前記第三インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ部分指定フィルタと関連付けられていることと、
第二インデックスと第四インデックスとを探すべく送信先アドレスデータ構成を検索することであって、前記第二インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ完全指定フィルタと関連付けられており、前記第四インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ部分指定フィルタと関連付けられていることと、
前記第一インデックス、前記第二インデックス、及び前記プロトコルから鍵を形成することと、
前記鍵に整合する入力を探すべく第一表を検索することであって、前記第一表は幾つかの入力を含み、各入力は完全指定フィルタ、完全指定フィルタ交差部、および指標フィルタのうちの一つと対応していることとを含む操作を行うようプログラムされており、
前記鍵に整合する前記第一表の入力は前記対応するビンを特定している、請求項４１に記載のシステム。
【請求項４４】
受信パケットのネットワーク経路に対応するビンを特定するべく、前記処理エンジンは、
前記第三インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく第二表のうちの第一のものを検索することであって、前記第一の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応していることと、
前記第四インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく前記第二表のうちの第二のものを検索することであって、前記第二の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応することとをさらに含む操作を行うようプログラムされており、
前記第一表に整合が見つからない場合、前記二つの第二表うち一つの整合する入力が前記対応するビンを特定する、請求項４３に記載のシステム。
【請求項４５】
前記第一表あるいは前記第二表のうちのいずれにも整合が見つからない場合、前記対応するビンは二次元アドレス空間全体に関連付けられているデフォルトビンを含む、請求項４４に記載のシステム。
【請求項４６】
受信パケットのネットワーク経路に対応するビンを特定するべく、前記処理エンジンは、
前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つワイドフィルタに関連付けられた第五インデックスを探すべく前記送信元アドレスデータ構成を検索することと、
前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つワイドフィルタに関連付けられた第六インデックスを探すべく前記送信先アドレスデータ構成を検索することと、
前記第五インデックス、前記第六インデックス、および前記プロトコルとから第二の鍵を形成することと、
前記第二の鍵に整合する入力を探すべくワイドフィルタ表を検索することであって、前記ワイドフィルタ表は幾つかの入力を含み、各入力がワイドフィルタに対応していることとをさらに含む操作を行うようプログラムされており、
前記第一表に整合が見つからない場合、前記ワイドフィルタ表の整合する入力が前記対応するビンを特定する、請求項４３に記載のシステム。
【請求項４７】
前記ワイドフィルタ表に含まれる各ワイドフィルタは、指定された閾値を越える幾つかの指標フィルタを持つ完全指定フィルタを含む、請求項４６に記載のシステム。
【請求項４８】
前記メモリは静的ランダム・アクセス・メモリ（ＳＲＡＭ）を備える、請求項３６に記載のシステム。
【請求項４９】
製品であって、
コンテンツ提供を行う機械アクセス可能な媒体であって、機械にアクセスされると前記機械に、
メモリに記憶されている複数のビンから、受信パケットのネットワーク経路に対応するビンを特定する工程であって、前記複数のビンの各々は幾つかの規則を含む工程と、
前記対応するビンを特定する命令を分類回路に発行する工程と、
前記対応するビンの前記規則を前記メモリから前記分類回路へコピーする工程であって、前記分類回路は前記受信パケットの少なくとも一つの移送レベルフィールドを前記規則の各々と比較し、一つの規則が前記パケットの前記少なくとも一つの移送レベルフィールドと整合している場合に整合信号を提供する工程と、
前記整合信号に応じて、前期整合している規則と関連付けられている動作を前記受信パケットに適応する工程とを行わせる、製品。
【請求項５０】
前記整合している規則には最高優先度整合規則が含まれる、請求項４９の製品。
【請求項５１】
前記受信パケットの前記少なくとも一つの移送レベルフィールドは、送信元ポートと送信先ポートとを含み、
ビンの各規則は送信元ポートの下限と、送信元ポートの上限と、送信先ポートの下限と、送信先ポートの上限とを含む、請求項４９に記載の製品。
【請求項５２】
一つの規則が前記パケットの前記少なくとも一つの移送レベルフィールドに整合する場合は、
前記受信パケットの前記送信元ポートが前記規則の前記送信元ポートの下限より大きいまたは等しく、前記規則の前記送信元ポートの上限よりも小さいまたは等しく、
前記受信パケットの前記送信先ポートが前記規則の前記送信先ポートの下限より大きいまたは等しく、前記規則の前記送信先ポートの上限よりも小さいまたは等しい場合である、請求項５１に記載の製品。
【請求項５３】
前記対応するビンは前記受信パケットに関連付けられたプロトコルとさらに対応している、請求項４９に記載の製品。
【請求項５４】
前記コンテンツは、アクセスされると、受信パケットのネットワーク経路に対応するビンを特定する際に、前記機械にさらに、
データ構成のうちの幾つかの入力の中から、前記受信パケットの前記送信元アドレスに整合する送信元アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第一識別子を含むことと、
別のデータ構成のうちの幾つかの入力の中から、前記受信パケットの前記送信先アドレスに整合する送信先アドレス接頭辞を持つ入力を特定することであって、前記整合入力が第二識別子を含むことと、
前記幾つかのビンの中から、前記第一および第二識別子と前記プロトコルとに対応するビンを特定することとを行わせる、請求項５３に記載の製品。
【請求項５５】
前記コンテンツは、アクセスされると、受信パケットのネットワーク経路に対応するビンを特定する際に、前記機械にさらに、
第一インデックスと第三インデックスとを探すべく送信元アドレスデータ構成を検索することであって、前記第一インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ完全指定フィルタと関連付けられており、前記第三インデックスは前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つ部分指定フィルタと関連付けられていることと、
第二インデックスと第四インデックスとを探すべく送信先アドレスデータ構成を検索することであって、前記第二インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ完全指定フィルタと関連付けられており、前記第四インデックスは前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つ部分指定フィルタと関連付けられていることと、
前記第一インデックス、前記第二インデックス、及び前記プロトコルから鍵を形成することと、
前記鍵に整合する入力を探すべく第一表を検索することであって、前記第一表は幾つかの入力を含み、各入力は完全指定フィルタ、完全指定フィルタ交差部、および指標フィルタのうちの一つと対応していることとを行わせ、
前記鍵に整合する前記第一表の入力は前記対応するビンを特定している、請求項５３に記載の製品。
【請求項５６】
前記コンテンツは、アクセスされると、前記機械にさらに、
前記第三インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく第二表のうちの第一のものを検索することであって、前記第一の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応していることと、
前記第四インデックスと前記プロトコルとから形成される鍵に整合する入力を探すべく前記第二表のうちの第二のものを検索することであって、前記第二の第二表は幾つかの入力を含み、各入力が部分指定フィルタに対応することとをさらに行わせ、
前記第一表に整合が見つからない場合、前記二つの第二表うち一つの整合する入力が前記対応するビンを特定する、請求項５５に記載の製品。
【請求項５７】
前記第一表あるいは前記第二表のうちのいずれにも整合が見つからない場合、前記対応するビンは二次元アドレス空間全体に関連付けられているデフォルトビンを含む、請求項５６に記載の製品。
【請求項５８】
前記コンテンツは、アクセスされると、前記機械にさらに、
前記パケットの前記送信元アドレスに整合する送信元接頭辞を持つワイドフィルタに関連付けられた第五インデックスを探すべく前記送信元アドレスデータ構成を検索することと、
前記パケットの前記送信先アドレスに整合する送信先接頭辞を持つワイドフィルタに関連付けられた第六インデックスを探すべく前記送信先アドレスデータ構成を検索することと、
前記第五インデックス、前記第六インデックス、および前記プロトコルとから第二の鍵を形成することと、
前記第二の鍵に整合する入力を探すべくワイドフィルタ表を検索する工程であって、前記ワイドフィルタ表は幾つかの入力を含み、各入力がワイドフィルタに対応していることとをさらに行わせ、
前記第一表に整合が見つからない場合、前記ワイドフィルタ表の整合する入力が前記対応するビンを特定する、請求項５５に記載の製品。
【請求項５９】
前記ワイドフィルタ表に含まれる各ワイドフィルタは、指定された閾値を越える幾つかの指標フィルタを持つ完全指定フィルタを含む、請求項５８に記載の製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は米国特許出願シリアルＮｏ．１０／６９０，３０１、「モストスペシフィックフィルタ整合と移送レベル共有とを用いる二段パケット分類のための方法と装置」、出願日２００３年１０月２０日に関している。
【０００２】
本発明は一般的にコンピュータネットワーキングに関しており、より詳しくは、パケット分類のための方法と装置に関している。
【背景技術】
【０００３】
伝統的に、コンピュータネットワークにおけるパケットルーティングはパケットの送信先アドレスだけに基づいている。このルーティング技術は一般的に「ベスト・エフォート」配信と関連しており、同じアドレスに向かうトラフィックはすべて同等に扱われる。しかし、帯域の増加、セキュリティの高度化、一層の柔軟性およびサービスの差別化への高まる需要を満たすべくは、送信先アドレスだけに基づくパケットルーティングでは不十分である。この目的を達成する目的から、機器ベンダおよびサービスプロバイダは、より差別化された形のファイアウォールによるルーティング、サービス品質（ＱｏＳ）に基づく転送、および帯域および／または資源留保を提供している。
【０００４】
一般的に、ファイアウォールはある種のクラスのトラフィック（「不要な」あるいは「疑わしい」トラフィック）を阻むことができる任意の部材、あるいは部材の組み合わせを含んでいる。ファイアウォールはしばしば法人ネットワークおよびその他の企業ネットワークにおいて使用されており、ファイアウォールは通常、ネットワークの入口点および／または出口点（つまり、「信用境界」）に実装される。典型的なファイアウォールは望ましいセキュリティ規定を実行するように設計された一連の規則あるいはフィルタを含む。
【０００５】
ネットワーク・サービスプロバイダは、各々が異なるサービス、サービス優先度、および価格体系を要求する、幅広い顧客層を持つことがある。様々な顧客に対して差別化されたサービスを提供するべく、あるいはより一般的に言い換えると、ネットワークトラフィック上のある種のクラスを優先待遇するべく、機器ベンダはＱｏＳに基づく転送および帯域／資源保留を含む、様々な機構を実装してきた。ＱｏＳに基づく転送の目的は、様々な顧客および／または様々な種類のトラフィックに対するサービスの差別化である。ＱｏＳに基づく転送は、例えばサービスクラスに基づく転送、特別な待ち処理（フロー毎の待ち処理）、および公正なスケジュール方法を含むことができる。ＱｏＳ転送と一体結合されているのが、帯域あるいは資源保留である。一般的に帯域保留はある種のトラフィックに対して特化帯域を保留することを含む。例えば、帯域保留を二点間のトラフィックに適用したり、帯域保留をあるアプリケーション（例えば、マルチメディア、ビデオなど）に関するトラフィックに適用することができる。
【０００６】
他の規定に基づくパケット転送技術実行とともに、ネットワークトラフィックをより差別化する上述のルーティング法（例えばファイアウォール、ＱｏＳ転送、帯域保留）を実現するべくは、パケットを分類することが必要になる。一般的に、パケット分類には、異なるフローに属すパケット間、あるいは異なる種類のトラフィックに関連付けられたパケット間を差別化する、ことが含まれる。ここで使用する「フロー」は少なくとも幾つかのヘッダ特性を共有する一連のパケットのことである（例えば、二つの特定アドレス間を流れるパケット）。パケットは通常、該パケットヘッダ内の一以上のフィールドに基づき分類がなされる。このヘッダ情報には一以上の規則が適用されて、これにより該パケットが対応するフロー、あるいは該パケットが関連付けられているトラフィックの種類を特定される。
【０００７】
パケット分類規則には一般的に、受信パケットのヘッダ中の対応する幾つかのフィールドと比較される幾つかのフィールドが、関連付けられた優先度と動作とともに、含まれている。分類データベースを構成する規則の組を優先一覧としてアレンジすることもでき、より高い優先度を持つ規則がより低い優先度のものよりも優先される。パケットが受信されると、該パケットの中身（例えば、あるヘッダフィールド）が分類データベースの各規則と比較され、該パケットに適用すべき一番高い優先度の動作が決定される。
【０００８】
ハッシュ体系、ビット並行技術、および内容参照可能メモリ（ＣＡＭ）を使用した実装を含む、ヘッダデータに基づき行われる幾つかの方法（ハードウェアおよびソフトウェア実装の両方）が、当技術分野ではよく知られている。ハッシュ法は各規則フィールドで使用されるビットマスクに従って規則群を作成し、各規則群は一または複数のハッシュ表で表される。受信されたパケットに整合する規則を特定するには、該ハッシュ表に対する一連の検索（ルックアップ）が要求される。
【０００９】
ビット並行技術は、ｎ次元の分類問題をそれぞれ一次元の多数段に分割する。一次元における各整合はビットベクターを戻す。該ビットベクターはシステムに記憶されている規則の数に等しい長さを持ち、ビットベクター内のビットは、そのビットに対応する規則が受信パケットの適切なフィールドに整合する値の範囲を規定している場合に設定される。それらのビットが戻されたビットベクター全てに設定されている規則がその受信パケットに整合する。標準ビット並行体系を超える改良は、集約ビットベクター（ＡＢＶ）法である。ＡＢＶ法においては、各「完全な」ビットベクターが圧縮されてより小さな大きさのビットの組で（「集約ビットベクターと呼ばれる」）表される。集約ビットベクター内の各ビットは完全なビットベクターのうちのビット群を表し、集約ビットベクター内の一ビットは、（完全なビットベクター内の）関連ビット群の中の少なくとも一つのビットが設定されている場合に設定される。
【００１０】
ＣＡＭ実装においては、ＣＡＭの各一入力が値とビットマスクと関連付けられている。該値は規則の一以上のフィールドを含んでおり、該ビットマスクは鍵を値と比較する際に検索鍵のどのビットを考慮すべきかを指定する。ＣＡＭ部は、検索鍵を多数の入力と同時に比較することができるのだが、最高優先度の整合入力と関連付けられたインデックスを戻し、このインデックスを使用してパケットの動作を特定する。
【００１１】
要求されるメモリアクセスの数が多いこと、記憶要件が高いこと、および（少なくともＣＡＭ実装についての）大幅な電力消費など、幾つかの要素が上述の分類規則の実行に影響を与える。他の要素とともに、帯域及びメモリオーバーヘッドの理由から、これらパケット分類技術は分類データベースの規模増加とともにリンク速度の進歩に歩調を合わせるべく苦労することもあり、パケット分類は、高速リンク（例えば、ギガビット容量）を支援するルータ内のボトルネックであってもよい。
【図面の簡単な説明】
【００１２】
【図１】ルータを持つネットワークの一実施形態を図示する概略図である。
【００１３】
【図２】図１に示すルータの一実施形態を図示する概略図である。
【００１４】
【図３】図２に示す処理装置の一実施形態を図示する概略図である。
【００１５】
【図４】パケットの一例の構成を図示する概略図である。
【００１６】
【図５Ａ−５Ｃ】概略図であって、各図はパケット分類規則の一実施形態を図示している。
【００１７】
【図６】二段パケット分類器の一実施形態を図示する概略図である。
【００１８】
【図７】二段パケット分類法の一実施形態を図示するブロック図である。
【００１９】
【図８】分類データベースの一例のうちの一部を図示する概略図である。
【００２０】
【図９】二段パケット分類法の他の実施形態を図示するブロック図である。
【００２１】
【図１０】幾つかの規則からなる分類データベースの一実施形態を図示する概略図である。
【００２２】
【図１１Ａ−１１Ｂ】一つの分類データベースを幾つかの規則に組織化しなおした一実施形態を図示する概略図である。
【００２３】
【図１２Ａ−１２Ｃ】二つの部分的に重なり合っているフィルタの一実施形態を図示する概略図である。
【００２４】
【図１３Ａ−１３Ｃ】二つの完全に重なり合っているフィルタの一実施形態を図示する概略図である。
【００２５】
【図１４】送信元・送信先アドレス空間内の二つの並行ルックアップの一実施形態を図示する概略図である。
【００２６】
【図１５】分類データベースのフィルタのうち不存在フィルタの構成を図示する概略図である。
【００２７】
【図１６Ａ】第一分類段データ構成の一実施形態を図示する概略図である。
【００２８】
【図１６Ｂ】並行最長接頭辞整合ルックアップ表の一実施形態を図示する概略図である。
【００２９】
【図１６Ｃ】図１６Ａの第一ルックアップ表の一実施形態を図示する概略図である。
【００３０】
【図１７】第二分類段データ構成の一実施形態を図示する概略図である。
【００３１】
【図１８】モストスペシフィックフィルタ整合と移送レベル共有とを使用する二段パケット分類法の一実施形態を図示するブロック図である。
【００３２】
【図１９】ワイドフィルタを含むフィルタデータベースの一実施形態を図示する概略図である。
【００３３】
【図２０Ａ】第一分類段データ構成の別の実施形態を図示する概略図である。
【００３４】
【図２０Ｂ】並行最長接頭辞整合ルックアップ表の別の実施形態を図示する概略図である。
【００３５】
【図２０Ｃ】モストスペシフィックフィルタ整合と移送レベル共有とを使用する二段パケット分類法の別の実施形態を図示するブロック図である。
【００３６】
【図２１】二段分類データ構成の作成および／または更新方法の一実施形態を図示するブロック図である。
【００３７】
【図２２】二段パケット分類を行うシステムの一実施形態を図示する概略図である。
【００３８】
【図２３】ビンの入力の一実施形態を図示する概略図である。
【００３９】
【図２４】図１６Ｂの並行最長接頭辞整合ルックアップ表の別の実施形態を図示する概略図である。
【００４０】
【００４１】
【図２５】二段パケット分類を行うシステムの別の実施形態を図示する概略図である。
【００４２】
【図２６】図２５に示した処理機器の一実施形態を図示する概略図である。
【００４３】
【図２７】分類エンジンの一実施形態を図示する概略図である。
【００４４】
【図２８】モストスペシフィックフィルタ整合と移送レベル共有とを使用する二段パケット分類法のさらに別の実施形態を図示するブロック図である。
【発明を実施するための最良の形態】
【００４５】
パケット分類器の実施形態をここに開示する。開示のパケット分類器の実施形態は、以下ではパケット転送器（例としては、ファイアウォール、ＱｏＳに基づく転送器など）を実装するルータの文脈で開示されている。しかし、開示の実施形態が実際の利用においてはそのように限定されず、さらに、以下の本文及び図面で開示されるパケット分類器の実施形態は一般的に、パケットその他通信の分類が必要な、任意の機器、システム、および／または状況に対して利用できることが理解されるべきである。
【００４６】
図１に図示しているのは、ネットワーク１００の一実施形態である。ネットワーク１００はパケット転送器２０１を持つルータ２００を含む。ルータ２００（及びパケット転送器２０１）は、その他の望ましい規定に基づく転送体系とともに、特定のセキュリティ規定、ＱｏＳ転送、および／または資源留保を実装することができる。異なるフローに属すパケット同士の差別化、および／または異なる種類のトラフィックに関連付けられたパケット同士の差別化の目的から、ルータ２００はさらに、望ましい転送規定を実装するよう設計された一組の規則を含むパケット分類器６００を含む。パケット分類器６００の実施形態を以下でさらに詳述する。ルータ２００（およびパケット転送器２０１とパケット分類器６００）は任意の適切な演算システムあるいは機器（あるいは機器の組み合わせ）上に実装されてもよく、ルータ２００の一つの実施形態を、図２と付随する本文の観点から以下に記載する。ルータ２００は他の部材（例えばスケジューラ、トラフィック管理機など）を含むこともできるが、そうした部材については図１からは明瞭化および理解の促進の観点から省いている。
【００４７】
ルータ２００は、リンク１３０ａ、１３０ｂ、...、１３０ｎを含む複数のリンク１３０を通じて、幾つかのノード１１０および／または幾つかのサブネット１２０と連結されている。ノード１１０は任意のアドレス可能な機器を備えている。例えば、ノード１１０はサーバ、デスクトップコンピュータ、ラップトップコンピュータ、ハンドヘルド演算機器（例としては、携帯情報端末あるいはＰＤＡ）などの、コンピュータシステムあるいはその他の演算機器を備えることもできる。サブネット１２０は他のノードの集合体であり、サブネット１２０もまた、他のルータ及びスイッチを含むこともできる。リンク１３０ａ−ｎはそれぞれ、ＴＣＰ／ＩＰ（送信制御プロトコル／インターネットプロトコル）、ＨＴＴＰ（ハイパーテキスト送信プロトコル）、およびその他の、任意の適切なプロトコル経由の情報交換を支援する、無線、銅線、繊維光、あるいはそれらの組み合わせなどを例とする、任意の適切な媒体上に設置することができる。
【００４８】
ネットワーク１００は、ローカルエリアネットワーク（ＬＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、広範ネットワーク（ＷＡＮ）、無線ＬＡＮ（ＷＬＡＮ）、その他のネットワークなど、いかなる種類のネットワークを備えていても構わない。ルータ２００はさらにネットワーク１００を、インターネットおよび／または他のＬＡＮ、ＭＡＮ、ＬＡＮ、あるいはＷＬＡＮによって他の一あるいは複数のネットワーク５に連結してもよい。ルータ２００は、任意の適切なプロトコル（ＴＣＰ／ＩＰ、ＨＴＴＰなど）を用いる無線、銅線、および／または繊維光接続を含む、任意の適切な媒体経由でその他のネットワーク５と連結していてもよい。
【００４９】
なお、図１に示したネットワーク１００はこのようなシステムの一実施形態例を表すことを意図しており、さらには、ネットワーク１００は任意の適切な構成を持つことができることを理解されるべきである。例えば、ネットワーク１００は、図１からは理解の促進のために省いてはいるが、さらなるノード１１０、サブネット１２０、および／またはその他の機器（スイッチ、ルータ、ハブなど）を含むことができる。さらに、ネットワーク１００が図１に図示した要素の全てを含まなくてもよいことも理解されるべきである。
【００５０】
一つの実施形態においては、ルータ２００は、パケット分類器６００を実装可能な任意の適切な演算機器を備える（ハードウェア、ソフトウェア、あるいはハードウェアとソフトウェアの組み合わせの形で）。このような演算システムの一実施形態を図２に図示する。
【００５１】
図２を参照すると、ルータ２００は、様々な部材が連結されるバス２０５を含む。バス２０５は、ルータ２００の部材を相互接続する一以上のバスの集合体（例えば、システムバス、周辺部材インターフェース（ＰＣＩ）バス、小規模演算システムインターフェース（ＳＣＳＩ）バスなど）を表すことを意図している。理解を促進する目的でこれらバスは一つのバス２０５として表現されているが、ルータ２００はこれに限られないことは理解されるべきである。当業者であれば、ルータ２００がいかなる適切なバスアーキテクチャであってもよく、またいかなる数、および組み合わせからなるバスを含んでも構わないことは理解されるところである。
【００５２】
バス２０５に連結されているのは、一または複数の処理機器３００である。処理機器３００は、マイクロプロセッサ、ネットワークプロセッサ、アプリケーション特定集積回路（ＡＳＩＣ）、あるいはフィールドプログラム可能なゲートアレー（ＦＰＧＡ）、あるいは類似した機器を含む、任意の適切な処理機器あるいはシステムを含むことができる。処理機器３００の一実施形態を以下に図３と付随する本文により示す。ここで、図２には一つの処理機器３００しか図示されていないが、ルータ２００は二以上の処理機器を含むことができることは理解されるべきである。
【００５３】
ルータ２００はさらに、バス２０５に連結されたシステムメモリ２１０を含み、システムメモリ２１０は例えば、静的ランダム・アクセス・メモリ（ＳＲＡＭ）、動的ランダム・アクセス・メモリ（ＤＲＡＭ）、同期ＤＲＡＭ（ＳＤＲＡＭ）、ダブル・データ・レートＤＲＡＭ（ＤＤＲＤＲＡＭ）などの、任意の適切な種類のおよび任意の数のランダム・アクセス・メモリを備えることができる。ルータ２００の操作中、一つまたは一組のオペレーティングシステム２１４、パケット分類器６００は、他のプログラム２１８とともに、システムメモリ２１０中に駐在してもよい。図２の実施形態においては、以下に記載するとおり、パケット分類器の一部が、つまり、パケット分類器の第一段６００ａ（段１ＰＣＫＴＣＬＳＳＦＲ）が、システムメモリ２１０中に駐在していてもよい一組のソフトウェアルーチンを備えており、一方パケット分類器のほかの部分は、つまりパケット分類器の第二段６００ｂ（段２ＰＣＫＴＣＬＳＳＦＲ）がハードウェア実装されている。しかしながらここで、図２の実施形態は開示のパケット分類器の一実装例を表しているのにすぎず、さらに開示のパケット分類器はいかなるほかの適切なソフトウェアおよび／またはハードウェア構成において実装されることもできる、ということは理解されるべきである。例えば、別の実施形態においては、第二分類段６００ｂもまたソフトウェア実装でき、その場合には第二段６００ｂがシステムメモリ２１０内に常駐する（さらに記憶機器２３０内に記憶されているかもしれない）一組のソフトウェアルーチンを備えてもよい。
【００５４】
ルータ２００はさらにバス２０５に連結されたリード・オンリ・メモリ（ＲＯＭ）２２０を含むこともできる。操作中、ＲＯＭ２２０は処理機器３００のための暫定命令および変数を記憶してもよい。またルータ２００は、バス２０５に連結された一または複数の記憶機器２３０を含んでもよい。記憶機器２３０は、例えばハードディスクドライブなどの任意の適切な不揮発性メモリを備える。パケット分類器６００は（例えばパケット分類器６００の第一段６００ａ）、オペレーティングシステム２１４その他のプログラム２１８（例えば、パケット転送器２０１のソフトウェア実装）とともに記憶機器２３０内に記憶されてもよい。さらに、取り外し可能な記憶媒体にアクセスするための機器２４０（例えばフロッピディスクドライブあるいはＣＤ  ＲＯＭドライブ）がバス２０５に連結されてもよい。
【００５５】
ルータ２００は、バス２０５に連結される一以上の入力機器２５０を含むこともできる。よく見かける入力機器２５０には、キーボード、マウスなどの指示機器、およびその他のデータ入力機器が含まれる。さらに一以上の出力機器２６０がバス２０５と連結されていてもよい。よく見かける出力機器２６０には、ビデオディスプレイ、印刷機器、音声出力機器、および状態指示器（ＬＥＤｓなど）が含まれる。
【００５６】
ルータ２００はさらに、バス２０５に連結されたネットワーク／リンク・インターフェース２７０を備える。ネットワーク／リンク・インターフェース２７０はルータ２００を他の一または複数のネットワークと連結することができ、さらにルータ２００をリンク１３０ａ−ｎの各々と連結できる、任意の適切なハードウェア、ソフトウェア、あるいはハードウェアとソフトウェアの組み合わせを含むことができる。
【００５７】
ここで、図２に図示したルータ２００はこのような機器の実施形態の一例を表すことを意図しているのであって、さらに、このシステムが明瞭化と理解の促進の目的から示してはいない多くの部材を追加的に含むことができる、ということは理解されるべきである。例としては、ルータ２００はＤＭＡ（ダイレクトメモリアクセス）制御機、処理機器３００と関連付けられたチップ組、および追加的メモリ（例えばキャッシュメモリ）などを、更なる信号線およびバスとともに含むこともできる。さらに、ルータ２００は図２に示した部材の全てを含まなくてもよいことも理解されるべきである。
【００５８】
一つの実施形態においては、パケット分類器６００、あるいはパケット分類器の一部は、演算機器（この例としては、図２のルータ２００その他適切な演算機器）上で実行される一組の命令（つまりソフトウエアアプリケーション）を備えている。該命令組は記憶機器２３０（あるいはその他の適切なプログラムメモリ）中にローカルに記憶されていてもよい。代わりに、該命令は遠隔記憶機器（不図示）に記憶されていてもよく、ネットワーク経由で（あるいは他のネットワーク５から）アクセスされてもよい。操作中、該命令組は処理機器３００上で実行されてもよく、このとき該命令（あるいはその一部）はシステムメモリ２１０中に駐在していてもよい。
【００５９】
別の実施形態においては、パケット分類器６００（あるいはパケット分類器の一部）は機械アクセス可能な媒体上（例えば磁気媒体（フロッピディスク）、光アクセス可能ディスク（例えばＣＤ−ＲＯＭディスク）、フラッシュメモリ機器など）に記憶されている一組の命令を備えている。パケット分類器６００を例えば図２のルータ２００上で実行する目的で、取り外し可能な記憶媒体にアクセスするための機器２４０は機械アクセス可能な媒体上の命令にアクセスして、該命令がその後、処理機器３００で実行されることもできる。この実施形態においては、該命令（あるいはその一部）は繰り返しになるが、システムメモリ２１０にダウンロードされることとしてもよい。
【００６０】
さらなる実施形態においては、パケット分類器６００、あるいは該パケット分類器の一部がハードウェア実装されている。例えば、パケット分類器６００は（あるいはその一部）は内容参照可能メモリ（ＣＡＭ）を用いて実装されてもよい。またさらなる実施形態においては、パケット分類器６００はソフトウェア・ハードウェアの組み合わせを用いて実装されてもよい。
【００６１】
一つの特定の実施形態においては、以下に詳細する通り、パケット分類器６００が二段パケット分類システムを備えており、この二段分類体系がハードウェアおよびソフトウェア両方で実装されていてもよい。二段パケット分類器は第一段６００ａ、および第二段６００ｂ（図２参照）を備える。一つの実施形態においては、第一段６００ａがソフトウェア実装され、第二段６００ｂがハードウェア実装されている。
【００６２】
先に記したとおり、処理機器３００の一実施形態を図３と付随する本文で図示する。しかしながら、図３に示した処理機器３００はパケット分類器６００の開示の実施形態が実装されてもよい処理機器の一つの実施形態にすぎないということは理解されるべきである。当業者であれば、パケット分類器６００の開示の実施形態は他の多くの種類の処理システムおよび／またはプロセッサアーキテクチャ上へ実装できることは理解されるところである。
【００６３】
図３を参照すると処理機器３００は、様々な機能部が連結されたローカルバス３０５を含む。バス３０５は処理機器３００の様々な機能部を相互接続する一以上のチップ上バスの集合体を表すことを意図している。理解を促進する目的でこれらローカルバスは一つのバス３０５として表現されているが、処理機器３００はこれに限られないことは理解されるべきである。当業者であれば、処理機器３００がいかなる適切なバスアーキテクチャを持っていてもよく、またいかなる数、および組み合わせからなるバスを含んでも構わないことは理解されるところである。
【００６４】
コア３１０および幾つかの処理エンジン３２０（例えば処理エンジン３２０ａ、３２０ｂ、...、３２０ｋ）はローカルバス３０５と連結されている。一つの実施形態においては、コア３１０は、オペレーティングシステム２１４を実行することのできる汎用目的の処理システムを備えている。コア３１０はさらに、処理エンジン３２０へ実行のための命令を施すなど、処理機器３００の動作を制御することおよび様々な管理機能を発揮することができる。処理エンジン３２０ａ−ｋの各々は、任意の処理システムを含み、各々が算出・論理部（ＡＬＵ）、制御機、および幾つかのレジスタ（読み出し・書き込み操作中のデータ記憶の目的で）を含むことができる。さらに、一つの実施形態においては、各処理エンジン３２０ａ−ｋは多数の（例としては４つの）実行スレッドを提供する。
【００６５】
ローカルバス３０５とさらに連結されているのはチップ上メモリ・サブシステム３３０である。これは一つの部材として示されているが、チップ上メモリ・サブシステム３３０は、他と区別できる幾つかのメモリ部および／または幾つかの種類のメモリを備えることができるし、実際上は備えている可能性が高い。例えば、このようなチップ上メモリはＳＤＲＡＭ、ＳＲＡＭ、および／またはフラッシュメモリ（例としてはＦｌａｓｈＲＯＭ）を含むことができる。チップ上メモリに加えて、処理機器３００はチップ外メモリ（例としてはＲＯＭ２２０、チップ外キャッシュメモリなど）と連結することができる。
【００６６】
処理機器３００はさらに、ローカルバス３０５と連結されたバスインターフェース３４０を含む。バスインターフェース３４０は、ルータ２００の他の部材（バス２０５を含む）との間にインターフェース接続を提供する。簡略化の目的から、バスインターフェース３４０は一つの機能部として示しているが、実際には処理機器３００は多数のバスインターフェースを含むことができることは理解されるべきである。例えば、処理機器３００はＰＣＩバスインターフェース、ＩＸ（インターネット交換）バスインターフェースおよびその他を含むことができ、バスインターフェース３４０は一以上のそのようなインターフェースの集合体を表すことを意図している。
【００６７】
図３に関連して図示、記載した処理機器３００の実施形態はパケット分類器の開示の実施形態とともに利用可能な処理装置の一例にすぎず、さらには処理機器３００は図３に図示したものに加えて他の部材を持つこともできるが、これら他の部材は明確化および理解の促進の目的から省かれている、ということは理解されるべきである。例えば、処理機器３００は他の機能部（例えば命令デコーダ部、アドレス解釈部など）、熱管理システム、クロック回路、追加的メモリ、およびレジスタを含むこともできる。さらには、処理機器は図３に示した要素の全てを含む必要はないことも理解されるべきである。
【００６８】
図４を参照すると、ルータ２００が（他のネットワーク５から）受信するようなパケット４００の一例が図示されている。パケット４００はヘッダ４１０とペイロード（あるいはデータ）４５０とを含む。ヘッダ４１０はいかなる適切なフォーマットでも構わなく、図４に図示したパケット４００はＴＣＰ／ＩＰプロトコルと関連づけられたヘッダの一例を示している。「コメントのためのインターネット工学タスク要求"Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｒｅｑｕｅｓｔ  ｆｏｒ  Ｃｏｍｍｅｎｔ"（ＩＥＴＦ  ＲＦＣ）７９１、インターネットプロトコル（１９８１）、およびＩＥＴＦ  ＲＦＣ７９３、送信制御プロトコル（１９８１）」参照。図４において、ヘッダ４１０はフィールド４２０ａ、４２０ｂ、...４２０ｘを含む幾つかのフィールドを含む。一般的に、フィールド４２０ａ−ｘはパケット４００の識別情報を含む。例によると、ヘッダ４１０はプロトコル４２０ｉ（例としてはＴＣＰ）、送信元アドレス４２０ｋ、送信先アドレス４２０ｊ、送信元ポート４２０ｍ、及び送信先ポート４２０ｎを含むこともできる。各送信元・送信先アドレス４２０ｋ、４２０ｉは三十二（３２）ビットを含んでもよく、各送信元・送信先ポート４２０ｍ、４２０ｎは十六（１６）ビットを含んでもよく、プロトコル４２０ｉは八（８）ビットを含んでもよい。当業者にとっては理解される通り、これらはパケットのヘッダに含むことのできる種類の情報の幾つかの例にすぎず、パケットヘッダ４１０はこれ以外にも、手元の特定のハードウェアおよび／またはアプリケーションの要請によって、いかなる情報を含むことができる。さらに、パケットの形式は図４に関して表示および記載したものに限られない（例えば、ヘッダフィールドの幅を変化させたり、フィールドの種類と数を変化させることができる）。
【００６９】
一般的に通信はここにおいて「パケット」と称される。しかし、開示される実施形態は、形式あるいは内容如何によらず、いかなる種類の通信（パケット、セル、フレームなど）にも適用できる。
【００７０】
図５Ａを参照すると、パケット分類規則５００の一実施形態が図示されている。一般的に、規則５００は、その基準を満たすパケットが属す特定のフローを示す一組の基準を特定している。規則５００はフィールド５１０ａ（フィールド１）、５１０ｂ（フィールド２）、...、５１０ｎ（フィールドＮ）を含む幾つかのフィールドを含んでいる。規則は任意の適切な数のフィールド５１０ａ−ｎを含むことができ、一つの規則内のフィールド数をここで次元と称する（つまり、規則５００はＮの次元を持つ）。一つの実施形態においては、各フィールド５１０ａ−ｎが、送信元・送信先アドレスなどの、パケットのヘッダの一フィールドに対応している。しかし、他の実施形態においては、一つの規則の部材５１０ａ−ｎは、アプリケーションヘッダフィールド、リンク識別情報、時刻などの他の情報を含むこともできる。一般的には、パケットが規則５００に整合するのは、各フィールド５１０ａ−ｎについて、パケットヘッダの対応フィールドが該規則のフィールドに整合するときである（分類規則のフィールドは、普通、値の範囲として表され、ある値が該規則のフィールドに整合するのは、その値がその該フィールドに対応する範囲に含まれる場合である）。規則５００はさらに該規則に整合する任意のパケットに適用される関連動作５２０（例えば、アクセプト、ブロックなど）を含む。規則５００はさらに優先度５３０と関連付けられている。
【００７１】
図５Ｂを参照すると、パケット分類規則５０１の別の実施形態が図示されている。規則５０１は送信元アドレスフィールド５１０ａと送信先アドレスフィールド５１０ｂとを、幾つかの移送レベルフィールド５１０ｃとともに含んでいる。移送レベルフィールド５１０ｃは例によると、プロトコル５１５ａ、送信元ポート５１５ｂ、送信先ポート５１５ｃを含んでいる。移送レベルフィールド５１０ｃは上述のフィールドに限らず、移送レベルフィールド５１０ｃは他のフィールド５１５ｄ−ｋを含んでいてもよい（あるいはこれより少ない数のフィールドを含んでいてもよい）。他の可能性のある移送レベルフィールドには、例えばＴＣＰ  ＳＹＮフラグ及びＲＳＶＰヘッダフィールド（例としては、ＩＥＴＦ  ＲＦＣ２２０５、資源ＲｅＳｅｒＶａｔｉｏｎプロトコル（ＲＳＶＰ）第一版機能仕様（１９９７年）参照）その他のプロトコルフィールドが含まれる。規則５０１はさらに関連動作５２０と優先度５３０とを含む。
【００７２】
図５Ｃに図示されているのは、図５Ｂに示した規則の一例である。図５Ｃの規則５０２は、「１２８．１２８．＊」に等しい送信元ＩＰ（インターネットプロトコル）アドレス５１０ａ、「１２８．６７．１２０．８４」に等しい送信先ＩＰアドレス５１０ｂ、「ＴＣＰ」に等しいプロトコル５１０ｃ、「８０」に等しい送信元ポート５１０ｄ、および「＊」に等しい送信先ポート５１０ｅを示しており、ここで「＊」という記号は「ワイルドカード」を表している（ワイルドカードには任意の値が整合する）。動作５４０は「ブロック」であり（つまり、本規則を満たすいかなるパケットも許可されない）、規則５０２は「２」に等しい優先度５４０を持つ。もちろん、図５Ｃは規則の一例を提示しているのにすぎず、さらに一つの規則が任意の適切な数および種類のヘッダフィールドを含んでもよいことは理解されるべきである（つまり、規則が任意の次元であってよい、ということである）。
【００７３】
各規則フィールドは完全な一致により表現されても（例えば「８０」に等しい送信元ポート）、接頭辞（例えば、「１２８．１２８．＊」という送信元アドレス）により表現されても、あるいは範囲指定（例えば、送信元ポート「＜＝１０２３」）により表現されてもよい。しかし、範囲の中には（例えば、送信元ポートが「＞１０２３」である）、接頭辞では表せないものもあり、このようなものに関しては、一組の接頭辞に分割することで表現してもよい。例えば、「＞１０２３」という範囲は以下のような一連の接頭辞（バイナリ形式）に区分することができる、つまり「０００００１＊＊＊＊＊＊＊＊＊＊」「００００１＊＊＊＊＊＊＊＊＊＊＊」「０００１＊＊＊＊＊＊＊＊＊＊＊＊」「００１＊＊＊＊＊＊＊＊＊＊＊＊＊」「０１＊＊＊＊＊＊＊＊＊＊＊＊＊＊」および「１＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊」というように区分することができる。従って、フィールド「＞１０２３」を持つ規則は６つの異なる規則に拡張することができ、その一つ一つが「＞１０２３」という範囲指定を持つ６つの異なる接頭辞の各々に対応している。ここで一般的にはＫ−ビットの範囲が最大（２Ｋ−２）個の接頭辞に分割できることに注意を喚起する。
【００７４】
図６に図示するのは、パケット分類器６００の一実施形態である。パケット分類器６００は分類工程を二段に分割する。パケット分類器６００は第一段６００ａ（第二段）よび第二段６００ｂ（第二段）を含む。第一段６００ａにおいては、パケットはそのネットワーク経路を基に分類され、第二段６００ｂにおいては、パケットは一以上の他のフィールド（例えば、移送レベルフィールド）を基に分類される。第一段６００ａと関連付けられているのは論理６１０とデータ構成１６００であり、第二段６００ｂと関連付けられているのは論理６２０とデータ構成１７００である。
【００７５】
第一段論理６１０は、受信パケットを該パケットのネットワーク経路に基づき分類できる任意の適切なソフトウェア、ハードウェア、あるいはソフトウェア・ハードウェアの組み合わせを含む。一つの実施形態においては、第一段論理６１０は受信パケットの送信元・送信先アドレスに基づく結果を判断して、この結果が分類器の第二段６００ｂに提供される。パケットを該パケットのネットワーク経路に基づき分類する方法の様々な実施形態を以下に記載する。ネットワーク経路は通例、送信元・送信先アドレス（例えば、送信元ＩＰアドレスおよび送信先ＩＰアドレス）により表現される。しかし、ネットワーク経路の表現は送信元・送信先アドレスの対に限ったものではなく、さらに、マルチプロトコルラベル切り替え（ＭＰＬＳ）ラベル（例えば、ＩＥＴＦ  ＲＦＣ３０３１、多数プロトコルラベル切り替えアーキテクチャ（２００１年）参照）、送信元ＩＰアドレスと送信先マルチキャスト群との組み合わせなどの、他の別の基準を使用してネットワーク経路を特定することもできることは理解されるべきである。第一段データ構成１６００に関してはさらに以下で詳述するが、ＳＲＡＭ、ＤＲＡＭ、ＳＤＲＡＭ、ＤＤＲＤＲＡＭ、その他の種類のメモリなどを含む、任意の適切なメモリに記憶されていてもよい。
【００７６】
第二段論理６２０は、受信パケットを該パケットのヘッダに含まれる移送レベルフィールド（あるいはその他のフィールド）に基づき分類することのできる任意の適切なソフトウェア、ハードウェア、あるいはソフトウェア・ハードウェアの組み合わせを含む。一つの実施形態においては、第二段論理６２０は分類の第一段から結果を受け取り、この結果と受信パケットのその他のフィールド（例えば移送レベルフィールド）に基づき、該パケットに適用される、あるいは、さもなくば実行される動作を決定する。パケットを該パケットのヘッダに含まれる一以上の移送レベルフィールド（あるいはその他のフィールド）に基づき分類する方法の様々な実施形態を以下に記載する。第二段データ構成１７００は、ＣＡＭ、ＳＲＡＭ、ＤＲＡＭ、ＳＤＲＡＭ、あるいは他の種類のメモリなどの、任意の適切なメモリに記憶されていてもよい。第二段データ構成１７００も以下でさらに詳述する。
【００７７】
一つの特定の実施形態においては、上で示唆したように、パケット分類器６００がソフトウェア・ハードウェアの組み合わせで実装されている。より詳しくは、第一分類段６００ａはソフトウェア実装されており、第二段分類段６００ｂはハードウェア実装されている。本実施形態においては、第一段分類段６００ａはメモリ（例えば、図２に示したシステムメモリ２１０、および／または図３に示したチップ上メモリサブシステム３３０）に記憶された一組の命令を含むこともでき、処理機器（例えば図３の処理機器３００）上で実行することができるが、第二段６００ｂはＣＡＭ（あるいはその他のハードウェア構成）を用いて実装ができる。
【００７８】
上述の二段分類体系に関しては、図６の二段パケット分類器６００上に実装できるが、さらに図７に図示されており、図７は二段パケット分類のための方法７００の一実施形態を示している。図７のブロック７１０でパケットが受信され、ブロック７２０にて該パケットは初めに該パケットのネットワーク経路を基に分類される。一般的にはパケットのネットワーク経路は該パケットのヘッダに含まれる送信元・送信先アドレスに表現される。その後、パケットは受信パケットのヘッダに含まれている一以上の他のフィールドに基づき分類される（ブロック７３０参照）。二段分類（ブロック７２０、７３０参照）の結果に基づき、最高優先度の動作が特定され、この動作を該パケットに適用する（ブロック７４０参照）。
【００７９】
他の多くの大型ネットワーク同様、インターネットにおいても通例、該ネットワークを横切る多くの可能なルートが存在するが、これと比較するアプリケーション数は少ない。ゆえに、異なるネットワーク経路の数は一般的にアプリケーション数よりもかなり多いことになる。これらの考察は実際の分類データベースの研究により生まれたものであり、一組の分類規則に存在する送信元・送信先アドレスの対の数は一般的に他のフィールド（例としてはポート数及びプロトコルなどの移送レベルフィールド）の数よりもかなり多いことを示している。これら研究はさらに、多くの異なる送信元・送信先アドレスの対が同一の移送レベルフィールド（あるいはその他のフィールド）の組を使用しており、さらには、一般的にこの組の中の各要素に関連付けられた相対優先度及び動作は該組の各発生について同一であることも示している。加えて、各組における入力数は一般的に少ない。
【００８０】
分類データベースにおいて送信元・送信先アドレスの対が同一の移送レベルフィールドの組を使用するという事実が図８に図示されている。この図を参照すると、分類データベース８００の一例が示されている。分類データベース８００は幾つかの分類規則を含んでおり、各規則は送信元ＩＰアドレス８１０ａ、送信先ＩＰアドレス８１０ｂ、プロトコル８１０ｃ、送信元ポート８１０ｄ、および送信先ポート８１０ｅを、関連動作８２０と絶対優先度８３０ａとともに含んでいる。二つの規則群８０１、８０２が図８に示されており、送信元・送信先ＩＰアドレス８１０ａ−ｄに示されている通り、第一群の各規則は同一のネットワーク経路を持っており、第二群の各規則は同一のネットワーク経路を持っている（が、第一群のネットワーク経路とは異なる）。規則の組（８０１あるいは８０２）における各規則の相対優先度８３０ｂも図８に示されている。二つの規則群８０１、８０２は各々異なる送信元・送信先アドレスの対を持つが、これら規則群は同じ移送レベルフィールド、動作、及び相対優先度レベルの組を共有している（つまり、規則群８０１のプロトコル、ポート仕様、動作、および優先度が規則群８０２に対しても繰り返されるということ）。（一以上の）移送レベルフィールドの一組、動作、および相対優先度の組み合わせをここでは「トリプレット」と称する。
【００８１】
図６に戻ると、パケット分類の第一段６００ａにおいて、第一段の分類は送信元アドレスと送信先アドレスとに基づき行われるので、Ｎ次元の分類課題が二次元課題に減らされており、これにより分類段が格段に簡略化されている。第二段６００ｂは任意のフィールド数に基づく分類に関していても構わないが（例えば三以上）、この分類課題の複雑性は実際世界の分類データベースの上述の特徴を利用することで格段に減らすことができる。特に、多くの送信元・送信先アドレスの対に同一のトリプレット群（移送レベルフィールドの一組、動作、および相対優先度）を共有させることにより、チェックが必要な入力数は、そしてメモリアクセス数は、相当減らすことができる。ここで、多数の送信元・送信先アドレスの対を、様々な移送レベル（あるいは他の）フィールドの一群と関連付ける構想は、つまりこれら送信元・送信先の対の各々がこの同一トリプレットの組を使用するので、「移送レベル共有（ＴＬＳ）」と称される。一つの移送レベルフィールド群は潜在的に多数の送信元・送信先アドレスの対に共有されることができるが、各移送レベルフィールド群はそれぞれ一度しか記憶できないので、パケット分類システムの記憶要件は減少することとなる。
【００８２】
上述の通り、二段分類体系の第一段６００ａは、多数次元分類課題を二次元課題に減らすことで簡略化される。しかし、一つのパケットが分類データベースの幾つかの規則に整合することもあり得、実際上は十分起こり得ることなので、第一段６００ａは多数整合に戻ることになる。多数整合は、少なくとも一部には、分類データベースの全規則の送信元・送信先の対が重複する性質を持つことに起因しており、第二には、送信元・送信先の対が任意の優先度と関連付けられていることに起因している。全ての可能性のある整合規則を見つけるべくは第一分類段で必要なメモリアクセス数をかなり増やすことがありえる。さらには、分類の第一・第二段６００ａ、６００ｂ間の結果を融合することは、多数整合が第一分類段から戻されると難しくなる。従って、別の実施形態においては、パケット分類の第一段６００ａを簡略化して効率を上げるべく、単一のモストスペシフィック整合を第一段から戻すことにしている。一つの実施形態においては、「モストスペシフィック整合」は一つのパケットのネットワーク経路についての最大情報量を提供するような整合である（例えば、ＩＰネットワークに対しては、モストスペシフィック整合は該パケットを網羅する全てのフィルタの交差点である）。ここでは、単一の整合フィルタを第一分類段６００ａから決定し、戻す工程を「モストスペシフィックフィルタ整合」（あるいはＭＳＦＭ）と称する。
【００８３】
図９へ進むと、二段パケット分類の方法９００に関する別の実施形態が図示されている。二段パケット分類のための方法９００は、移送レベル共有とモストスペシフィックフィルタ整合の両方を実装する。図９のブロック９１０でパケットが受信される。ブロック９２０にて分類の第一段において、単一のモストスペシフィック整合を見つける目的で該パケットが該パケットの送信元・送信先アドレスに基づき分類される。分類の第二段において、パケットは移送レベル共有を用いて一以上の移送レベルフィールドに基づき分類される（ブロック９３０参照）。二分類段の結果に基づき、最高優先度の動作が特定され、この動作を該パケットに適用する（ブロック９４０参照）。なお、他の実施形態においては、第一段でモストスペシフィックフィルタ整合を使用して、第二段では移送レベル共有を行わないこともあり、また別の実施形態においては、第二段で移送レベル共有を行い、第一段ではモストスペシフィックフィルタ整合を行わないこともある。
【００８４】
モストスペシフィックフィルタ整合（ＭＳＦＭ）と移送レベル共有（ＴＬＳ）の両方を以下に詳述する。説明はＴＬＳの説明から初め、次にＭＳＦＭの説明を行うことにする。
【００８５】
典型的な分類データベースは規則の一覧からなる。これは図１０に図示されており、図１０は、規則１００５ａ、１００５ｂ、...、１００５ｙを含む幾つかの規則１００５を含む分類データベース１０００を示している。各規則１００５ａ−ｙは、例えば送信元アドレス１０１０ａ、送信先アドレス１０１０ｂ、及び一以上の移送レベルフィールド１０１０ｃ（あるいは他のフィールド）を、関連動作１０２０と優先度１０３０とともに含む。前に述べたように、各規則１００５について、移送レベルフィールド１０１０ｃ、動作１０２０、及び優先度１０３０を「トリプレット」１０４０と称すことができる。上述の通り、典型的な分類データベースにおいては、送信元・送信先の対の数に比べて、移送レベルフィールドの組の数は比較的少なくなっており、さらには、典型的なデータベースにおいて移送レベルフィールド組の同一グループは、多数の送信元・送信先の対により共有されていることがしばしばある（図８と付随する本文参照）。この分類データベースの特徴を活用する目的で、データベース１０００の規則１００５を規則の組にグループ分けする。一組の規則は同一の送信元・送信先アドレスの対を持つデータベースの規則を含んでいる。例えば、図８に戻ると、グループ８０１の規則は第一規則組を持つことがあり（つまり、送信元アドレス「１２８．１２８．１０．５」と送信先アドレス「１７２．１２８．＊」とを共有しており）、グループ８０２のこれら規則は第二規則組をもつことがある（つまり、送信元アドレス「１２８．１２８．１０．７」と、送信先アドレス「１７２．１２８．＊」とを共有している）。
【００８６】
分類データベースを幾つかの規則組に仕切る一例が図１１Ａに図示されている。この図を参照すると、分類データベース１１００は、規則組１１５０ａ、１１５０ｂ、...、１１５０ｑを含む幾つかの規則組１１５０に組織化されている。各規則組１１５０ａ−ｑは一以上の規則を含んでおり、任意の規則組１１５０の各規則は該規則組内の他の全ての規則との間で同一の送信元・送信先アドレスを共有している。一つの実施形態においては、図１１Ａに示すように、データベース１１００の規則は各規則組１１５０ａ−ｑの規則がデータベース内で連続した空間を占有するように整列されている。加えて、一組の規則１１５０内の規則は連続的な優先度を占有していることもあるが、別の実施形態においては、一組の規則が連続的な優先度を占有していない規則により形成されていることもある。規則組１１５０ａ−ｑは各々フィルタ１１６０と関連付けられていると考えてよく（規則組１１５０ａはフィルタ１１６０ａと関連付けられており、規則組１１５０ｂはフィルタ１１６０ｂと関連付けられている、など）、一つの規則組１１５０のフィルタ１１６０は該規則組の送信元・送信先の対を含む。なお、図１１Ａの実施形態は、分類データベースの規則が規則組を形成する態様の一例にすぎないことは理解されるべきである。
【００８７】
図１１Ａの各規則組１１５０（および各対応フィルタ１１６０）は関連トリプレットの一群を持ち、各トリプレットは幾つかの移送レベル（あるいは他の）フィールド、動作、相対優先度を含む。図８に再度戻ると、各規則組８０１、８０２は関連付けられた三つのトリプレットのグループを持ち、図８の例では、各規則組８０１、８０２が同一のトリプレットのグループを持っている（つまり、規則組８０１、８０２の送信元・送信先の対がそれぞれ同一のトリプレットの組を共有している、ということ）。任意の規則組とフィルタと関連付けられたトリプレットはここで「ビン」、及びこの場合（下で説明する「大きなビン」と区別して）「小さなビン」と称されるグループを形成している。従って、図１１Ａに示すように、各規則組１１５０と、それと対応するフィルタ１１６０は、トリプレットの小さなビン１１７０と関連付けられている（つまり、規則組１１５０ａとフィルタ１１６０ａが小さなビン１１７０ａと関連付けられている、など）。この様々な移送レベルフィールド（つまり小さなビン）の組のグループが、一つの規則セットに含まれる幾つかの規則間で共有されることが、移送レベル共有の概念に繋がる。
【００８８】
図１１Ａのデータベース１１００と関連付けられた小さなビン１１７０をさらに図１１Ｂに図示する。図１１Ｂを参照すると、データベース１１００は小さなビン１１７０の集合体と関連付けられている。各小さなビン１１７０は一以上の入力１１７２を含み、各入力１１７２は一以上の移送レベル（あるいは他の）フィールド１１７４、相対優先度１１７５、および動作１１７６を含む（つまりトリプレットである）。図１１Ｂにも示すように、小さなビン１１７０はさらに論理的に「大きなビン」１１８０へと組織化されてもよく、ここで各大きなビン１１８０は二つ以上の小さなビン１１７０の集合体を含んでいる。大きなビン１１８０の生成について下記で説明する。
【００８９】
パケットを移送レベルフィールドに基づき分類するのに使用される第二段データ構成１７００について以下に説明する。ここでモストスペシフィックフィルタ整合に話題を変える。
【００９０】
前述の通り、パケットを該パケットのネットワーク経路に基づき分類する際には、パケットは分類データベースの多数の規則に整合することが起こり得る。（例えば要求されるメモリアクセス数を減らすなどして）第一分類段６００ａの効率を上げる目的から、さらに、第一段の結果を第二分類段６００ｂと融合させるのを簡略化させる目的から、第一段から単一のモストスペシフィック整合を戻すことが望ましい。
【００９１】
なお、説明の目下の段階においては、「フィルタ」という用語はここでは規則組と関連付けられた送信元・送信先アドレスの対のことを示すべく使用されているので（図１１Ａ−１１Ｂと、上述の付随する本文参照）、「規則」という用語よりも「フィルタ」という用語を使用する。しかし、「フィルタ」という用語と「規則」という用語はしばしば殆ど同じ意味で用いられることは理解されるべきである。
【００９２】
その送信元・送信先アドレスを基に分類されるパケットが多数フィルタに整合することは、少なくとも一部には、分類データベースのフィルタのもつ重複する性質に起因している。このことは概略的に図１２Ａ−１２Ｃ、及び図１３Ａ−１３Ｃに図示されている。まず図１２Ａを参照すると、規則の送信元・送信先アドレスは二次元空間の一領域（つまり、矩形、線、あるいは点）として捕らえることができる。図１２Ａにおいては、分類データベースの第一フィルタ１２１０はＦ１と銘打たれた矩形で示されている二次元空間を占有している。フィルタＦ１はトリプレットの小さなビン１２１５（Ｂ１）と関連付けられている。図１２Ｂに進むと、データベースの第二フィルタ１２２０（Ｆ２）もまた送信元・送信先アドレス空間内の一領域を占有しており、このフィルタＦ２も移送レベルフィールドの小さなビン１２２５（Ｂ２）と関連付けられている。
【００９３】
フィルタＦ１とＦ２両方が図１２Ｃに示されており、これら二つのフィルタにより定義される領域が重複、あるいは交差していることが観察でき、Ｆ１とＦ２の交差部は参照番号１２９０で示されている。図１２Ａ−１２Ｃに示すフィルタＦ１とＦ２とは「部分的に重複している」といわれる。パケット（Ｐ）１２０５が、フィルタＦ１・Ｆ２の交差部１２９０内に在る送信元・送信先アドレスの対を持っている場合、このパケットは両方のフィルタに整合することになる（つまり、フィルタＦ１・Ｆ２は少なくともパケットＰが定義する点を共有する、ということである）。加えて、パケットＰは、フィルタＦ１・Ｆ２の交差部１２９０内に在る他の任意のパケット同様、フィルタＦ１・Ｆ２と関連付けられた小さなビンＢ１・Ｂ２の和集合とそれぞれ関連付けられることになる。この、二つ以上のフィルタの交差部と関連付けられた小さなビンの和集合を、「大きなビン」とここで称することにする。ビンＢ１・Ｂ２の和集合からなる大きなビンは図１２Ｃでは参照番号１２９５で示されている。
【００９４】
フィルタは「完全に重複する」こともあり、この場合を図１３Ａ−１３Ｃに図示する。第一フィルタ１３１０（Ｆ１）が図１３Ａに示す二次元空間内の領域を占有しており、第二フィルタ１３２０（Ｆ２）が図１３Ｂに示すこの空間内の領域を占有している。フィルタＦ１は関連する小さなビン１３１５（Ｂ１）を持ち、フィルタＦ２は関連する小さなビン１３２５（Ｂ２）を持つ。次に図１３Ｃを参照すると、フィルタＦ１・Ｆ２両方が示されており、これらフィルタは交差部１３９０で重複している（この場合は交差部１３９０はＦ２で定義される領域と同等である）。Ｆ２により定義される領域（および交差部１３９０）はフィルタＦ１の二次元空間に完全に含まれているので、フィルタＦ１・Ｆ２は「完全に重複している」と言われる。交差部１３９０内に在るパケット（Ｐ）１３０５はフィルタＦ１・Ｆ２両方に整合し、このパケットＰが（この交差部１３９０内に在るほかの全てのパケット同様に）、小さなビンＢ１・Ｂ２の和集合からなる大きなビン１３９５と関連付けられることになる。
【００９５】
図１２Ａ−１２Ｃおよび１３Ａ−１３Ｃから観察されることは、送信元アドレスと送信先アドレスが二つ（或いはそれ以上）のフィルタの交差部内に在るパケットは両方のフィルタに整合する、ということである。分類の第一段から単一の整合だけを戻す目的を達成する目的上、全てのフィルタの交差部をフィルタデータベースに含ませている（つまり、第一段データ構成１６００）。さらに、各フィルタ交差部は該交差部を構成する各フィルタの移送レベルフィールドの和集合と関連付けられている。つまり、上述の通り、各フィルタ交差部は、二つ以上の小さなビンの和集合からなる大きなビンと関連付けられている。全てのフィルタ交差部をルックアップ表に加えるべくは、理論上、とても大きな記憶容量が必要となる。しかし、実際の分類データベースに関する研究によると、実際にはフィルタ交差部を記憶するのに必要な追加的容量は理論上の最大境界値よりもかなり小さいことが示唆されている。
【００９６】
パケットをその送信元・送信先アドレスに基づいて分類するにあたっては、パケットが位置するフィルタの最小交差部（あるいは、パケットが交差部にない場合には、単にフィルタ）を探すことが問題となってくる。このフィルタの最小交差部を探す目的で、分類の第一段（二次元分類課題）を二つの一次元ルックアップに分割する。これを図１４に概略的に図示しており、ここでは第一次元１４１０と第二次元１４２０とが示されている。この第一次元１４１０においては、受信パケットの送信元アドレスが送信元アドレスルックアップデータ構成１４１２の入力と比較され、整合するものが見つかれば、インデックス１４１４（Ｉ１）が戻される。同様に、第二次元１４２０において、パケットの送信先アドレスが送信先アドレスルックアップデータ構成１４２２の入力と比較され、整合するものが見つかれば第二インデックス１４２４（Ｉ２）が戻される。二つのインデックス１４１４、１４２４（Ｉ１とＩ２）はその後、一つの鍵１４３０に組み合わせられて、この鍵１４３０は別のルックアップデータ構成（例えば、ハッシュ表）にクエリを行うのに用いることができる。一つの実施形態においては、第一および第二次元１４１０、１４２０それぞれのルックアップデータ構成１４１２、１４２２に行われるルックアップは最長接頭辞整合（ＬＰＭ）を用いて実行される。さらなる実施形態においては、二つの次元１４１０、１４２０のルックアップは並行して行われる。送信元・送信先次元における二つの並行の独立したルックアップを使用するべくは比較的少ない回数のメモリアクセスが要求され、かつ合理的な記憶要件が発揮される。
【００９７】
図１４が図示する並行ＬＰＭルックアップ体系は、パケットが在るフィルタの最小交差部を戻すか、あるいはこの体系は「不在」フィルタを戻す。不在フィルタはあるフィルタの送信元アドレスと、別のフィルタの送信先アドレスとを含む。不在フィルタは、送信元・送信先アドレスにおいてルックアップが独立して行われることに起因している（しかし、一つの実施形態においてはこれらルックアップは並行して行われる）。
【００９８】
不在フィルタの構想は例をとって説明することで理解が容易になると思われる。図１５を参照すると、データベースは文字Ａ、Ｂ、Ｃ、Ｄ、およびＥで示される５つのフィルタを含んでおり、これらフィルタは二次元アドレス空間１５００に示されている。フィルタＡは送信元・送信先アドレス空間全体を網羅しており、このフィルタは「＊，＊」で示すことができる（つまり、これは、ワイルドカード文字「＊」を送信元アドレス、送信先アドレスの両方に含んでいる）。フィルタＢは「＊，Ｙ＊」という形式をとっており、この形式のフィルタは（つまり、「＊，Ｙ＊」あるいは「Ｘ＊，＊」）は、「部分指定フィルタ」と称される。フィルタＣ、Ｄ、Ｅは「完全指定フィルタ」と称され、これらフィルタは「Ｘ＊，Ｙ＊」という形式をとる。例として、フィルタ「ＳＲＣ  ＡＤＤ１２８．１７２．＊／ＤＳＴ  ＡＤＤ＊」は部分指定フィルタであり、フィルタ「ＳＲＣ  ＡＤＤ１２８．１７２．＊／ＤＳＴ  ＡＤＤ１２８．１２８．＊」は完全指定フィルタである。フィルタＡ、Ｂ、Ｃ、Ｄ、およびＥの送信元・送信先アドレスの組み合わせは２次元空間に１２個の異なる領域を形成する。最初の５つの領域はフィルタＡ、Ｂ、Ｃ、Ｄ、Ｅに対応している。他の７つの領域は、Ｒ１〜Ｒ７として示されているが（ダッシュ記号で示す）、不在フィルタに対応している。Ｒ１〜Ｒ７の領域は、一つのフィルタの送信先アドレスと別のフィルタの送信元アドレスとから形成されており、これら領域は上述のように、送信元・送信先アドレスにおけるルックアップが独立して実行される理由から作成される。例えば、領域Ｒ４はフィルタＥの送信元アドレスとフィルタＤの送信先アドレスとを組み合わせることにより作成され、この結果、存在しないフィルタが生まれる。図１５に示す図面は一般にクロス生成表と称される。
【００９９】
図１４の並行ルックアップ体系が結果を戻すことを保証する目的で、全ての不在フィルタＲ１〜Ｒ７がフィルタデータベースに入力されることが必要となる。従来技術の幾つかは（例えば、クロス生成表体系）は、全ての不在フィルタをフィルタデータベースに加えることを示唆している。しかし、実際の分類データベースを調べてみると、不在フィルタの数はかなり多く、ゆえに、フィルタデータベースに加える不在フィルタの数は最小限に減らすことが望ましいであろうと示唆されている。従って、一つの実施形態においては、全ての可能性ある不在フィルタのうちのサブセットだけを分類データ構成中に含ませる。可能性ある不在フィルタを分類データ構成に全部は追加しない（及び、全ての可能性ある不在フィルタの代わりに不在フィルタのサブセットをデータ構成に配置する）方法を下に詳述する。
【０１００】
図１５を参照すると、領域Ｒ１〜Ｒ７までの多くの領域が少ない数の別のフィルタに統合されることが観察できる。特に、領域Ｒ１、Ｒ３、およびＲ４を完全に網羅することのできる最小フィルタはフィルタＡであり、これは二次元空間全体である。Ｒ１、Ｒ３、Ｒ４のうちの一領域に在る任意のパケットの送信元・送信先パケットのうちいずれかについての検索は、領域Ａに含まれるフィルタの送信元・送信先アドレスを戻す。従って、フィルタ「＊，＊」への別個の入力の存在を条件に、不在フィルタＲ１、Ｒ３、Ｒ４はフィルタＡに統合でき、Ｒ１、Ｒ３、Ｒ４の別個の入力をフィルタデータベースから削除することができる。同様に、領域Ｒ５、Ｒ６、Ｒ７は完全にフィルタＢに網羅されており、これら不在フィルタはフィルタＢへの入力と統合することができる。Ｒ５、Ｒ６、Ｒ７のうちの一領域内にある任意のパケットについて、このパケットの送信先アドレスに関する調査はフィルタＢの送信先アドレスを戻すことになる。従って、部分指定フィルタＢへの別個の入力が分類データ構成内に提供されている限り、Ｒ５、Ｒ６、Ｒ７への別個のデータベース入力は必要とされない。
【０１０１】
しかし、領域Ｒ２はいかなる他のフィルタとも融合することができない。この領域は、フィルタＤの送信元アドレスとフィルタＥの送信先アドレスとから形成されているが、完全指定フィルタ、つまりフィルタＣに完全に網羅されている。不在フィルタＲ２は、唯一、完全指定フィルタに完全に含まれているので、他の不在フィルタから区別される。不在フィルタＲ２はフィルタＣ、あるいは他のいかなる入力とも統合することができず、このフィルタへの入力はフィルタデータベースに配置されるべきである。Ｒ２のような不在フィルタもまた、ここでは「指標フィルタ」と称される。指標フィルタは、完全に指標フィルタを網羅するフィルタの最小可能性の交差部に対応する交差移送レベルフィールドの組に関連している。例によると、図１５に示すフィルタの組については、領域Ｒ２を完全に網羅するフィルタはフィルタＡとＣであり、これら二つのフィルタの交差部は単純にフィルタＣである。従って、指標フィルタＲ２はフィルタＣと同じ移送レベルフィールドの組に関連付けられる。
【０１０２】
幾つかの追加的観察が第一段データ構成１６００の発展に寄与する。一般的に分類データベースにおけるフィルタの部分重複には以下の三つの原因が考えられる、（１）部分指定フィルタ間に形成される部分重複（つまり、形式「Ｘ＊，＊」あるいは「＊，Ｙ＊」）、（２）完全指定フィルタ間に形成される部分重複（つまり、形式「Ｘ＊，Ｙ＊」）、及び（３）部分指定フィルタ・完全指定フィルタ間に形成される部分重複。なお、送信元次元にワイルドカードを持つ部分指定フィルタの各々は、送信先次元にワイルドカードを持つ全ての部分指定フィルタとの部分重複を持つことになるので、このような部分指定フィルタの交差部により形成される部分重複の数は、それぞれ、各送信元・送信先次元の部分指定フィルタの数の積に等しくなる。部分指定フィルタの交差部による部分重複の数は、理論上は非常に多くなる。一方、完全指定フィルタ間の部分重複の数は大した数ではないが、それは、実際には殆どの完全指定フィルタは、二次元アドレス空間における直線あるいは点の断片であるからである。
【０１０３】
先行する段落で示したとおり、典型的な分類データベースにおいては、部分指定フィルタが典型的な部分重複の主な原因となっている。しかし、普通の場合においてはネットワーク管理者が特定のアドレスドメイン間で交換されるトラフィックに規則を適用するので、部分指定フィルタはしばしば分類データベースの全フィルタ数のうち、ほんの一部にすぎない。従って、部分指定フィルタがもたらす部分フィルタ重複の数は実際上は理論上の最悪の場合に比べると大いに少なくなる。さらに、上述のように、完全指定フィルタがもたらすフィルタ間の部分重複の数は取るに足らない。これにより、実際の分類データベースに存在する部分重複の数は一般的に発生が理論上予期される数よりもずっと少ない。
【０１０４】
この時点で注意を喚起したいのは、図１３Ａ−１３Ｃで図示したような完全重複フィルタに関しては気にしてこなかったということである。上で述べたように、一つの実施形態においては、最長接頭辞整合（ＬＰＭ）をＭＳＦＭで行われる二つの一次元検索のそれぞれに使用している。フィルタが完全に重複する際には、これらフィルタの交差部はこれらフィルタの一つに等しくなり、ＬＰＭ検索はこのフィルタを特定する。ゆえに、一つの実施形態においては、第一段データ構成１６００は完全重複フィルタを計上する必要がない。
【０１０５】
上述の観察と説明（図６−１５とそれに付随する本文）により、第一段データ構成１６００、および第二段データ構成１７００を構築する際に使用することのできる「ブロック構築」が提示されたが、これら二つのデータ構成の実施形態を以下に説明する。パケット分類に使用される（つまり、パケットに適用する動作の特定に使用される）第一・第二段データ構成１６００、１７００の検索方法の実施形態を以下に説明する。
【０１０６】
図１６Ａを参照すると、第一段データ構成１６００の一実施形態が図示されている。第一段データ構成１６００は並行ＬＰＭデータ構成１６０１と転送表１６０２とを含んでいる。上でも記載したように、ＭＳＦＭ体系は、図１４に関して上で示し及び記載したように、送信元・送信先アドレスに対して二つの一次元検索をそれぞれ用いる。従って、並行ＬＰＭデータ構成は送信元アドレスルックアップデータ構成１６１０と送信先アドレスルックアップデータ構成１６２０とを含む。一つの実施形態においては、送信元・送信先アドレスルックアップデータ構成１６１０、１６２０は三つのデータ構成として実現される。しかしながら当業者には理解されるように、送信元・送信先アドレスルックアップデータ構成１６１０、１６２０の実現のためには代わりに別のデータ構成を使用することもできる。
【０１０７】
並行ＬＰＭデータ構成１６０１の一実施形態をさらに図１６Ｂに概略的に図示する。送信元アドレスルックアップデータ構成１６１０は幾つかの入力１６１２を含み、各入力１６１２は送信元接頭辞１６１４ａ、フィルタ種別１６１４ｂ、及びインデックス値１６１４ｃ（あるいは他の識別子）を示している。同様に、送信先アドレスルックアップデータ構成１６２０は幾つかの入力１６２２を含み、各入力１６２２は送信先接頭辞１６２４ａ、フィルタ種別１６２４ｂ、及びインデックス値１６２４ｃ（あるいは他の識別子）を示している。ルックアップデータ構成１６１０、１６２０両方において、フィルタ種別１６１４ｂ、１６２４ｂは入力１６１２、１６２２が完全指定フィルタあるいは部分指定フィルタのいずれに関連しているかを示している。検索が並行ＬＰＭデータ構成１６０１に行われると、四つのインデックス（あるいは他の識別子）が戻されるが、この中には、送信元アドレスルックアップデータ構成１６１０の整合する完全指定フィルタに関連付けられた第一インデックス１６９１（Ｉ１）、送信先アドレスルックアップデータ構成１６２０の整合する完全指定フィルタに関連付けられた第二インデックス１６９２（Ｉ２）、送信元アドレスルックアップデータ構成の整合する部分指定フィルタに関連付けられた第三インデックス１６９３（Ｉ３）、および送信先アドレスルックアップデータ構成の整合する部分指定フィルタに関連付けられた第四インデックス１６９４（Ｉ４）が含まれている。上で記載したように、一つの実施形態においては、送信元・送信先アドレス次元における検索は並行して行われる。
【０１０８】
完全指定フィルタと関連付けられた最初の二つのインデックス１６９１、１６９２（Ｉ１とＩ２）は、組み合わせられて鍵１６９０を作成する。鍵１６９０は完全指定フィルタと関連付けられており、部分指定フィルタと関連付けられている第三、第四インデックス１６９３、１６９４同様、下記に記すように転送表１６０２を検索する目的で使用される。ここで完全・部分指定フィルタを区別する理由は、整合するフィルタが部分指定フィルタであった場合に分類の第一段で最長接頭辞整合を使用すると、探している部分指定フィルタが特定できないことがあるからである（つまり、特定する整合する送信元・送信先接頭辞が、実際に整合するフィルタの対応接頭辞よりも「長い」ことがあるからである）。
【０１０９】
一つの実施形態においては、図１６Ａに示すように、転送表１６２０は第一表１６３０と二つの第二表１６４０ａ、１６４０ｂを含んでいる。第一表１６３０は完全指定フィルタ、完全指定フィルタ交差部、および指標フィルタの入力を含む。ここで繰り返すが、指標フィルタとは、お互いに異なる送信元・送信先の対の送信元・送信先接頭辞から形成される領域であり、完全指定フィルタあるいはフィルタ交差部とは統合できない（例えば、上で説明した図１５の領域Ｒ２を参照）。第二表１６４０ａ−ｂのうちの一方は送信元次元にワイルドカードを持つ部分指定フィルタの入力を含んでおり、第二表１６４０ａ−ｂのうちの他方は送信先次元にワイルドカードを持つ部分指定フィルタの入力を含んでいる。第二表１６４０ａ、１６４０ｂは指標フィルタを含まない。上述のように、一つのフィルタの送信元（あるいは送信先）接頭辞と他のフィルタの送信先（あるいは送信元）接頭辞とから生成される領域のなかには、部分指定フィルタと統合できるものもあり(図１５、領域Ｒ５、Ｒ６、及びＲ７参照)、このような領域の入力は第一表に加える必要はない。
【０１１０】
第一表１６３０の一実施形態を図１６Ｃに示す。この図を参照すると、第一表１６３０は幾つかの入力１６３２を含み、各入力は鍵１６３７ａ、一以上のビンポインタ１６３７ｂを含んでいる。並行ＬＰＭ検索で特定される（図１６Ｂ参照）第一・第二インデックス１６９１、１６９２（Ｉ１とＩ２）から形成される鍵１６９０を使用して第一表１６３０を検索する。鍵１６９０が第一表中任意の入力１６３２の鍵１６３７ａと整合すると、その入力中のビンポインタ１６３７ｂが特定するビンにアクセスして、受信パケットに適用すべき動作（例えば、最高優先度の動作）を探すが、この工程を以下に詳述する。入力１６３２は一つの小さなビン１６７０あるいは代わりに小さなビンのグループ、つまりフィルタ交差部に対応する小さなビンの和集合を含む「大きなビン」１６８０を指摘してもよい。なお、幾つかの実施形態においては、例えば規則組が備える規則が連続する優先度レベルを占有しているような場合に起こる結果として、第一表の対応入力がその大きなビンに含まれる全ての小さなビンのポインタを含むので、大きなビン１６８０を記憶する必要はない。しかしながら他の実施形態においては、大きなビンを記憶してもよい（例えば、規則組の規則が連続していない優先度を占有している場合）。さらに、図１６Ｃに図示されるように、多数の入力１６３２は同一の、一または複数の小さなビン１６７０を指摘、あるいは共有することもできるが、これは移送レベル共有の結果である。
【０１１１】
第二表１６４０ａ、１６４０ｂの各々は第一表１６３０と類似している。しかし、第二表の一方にアクセスする鍵は第三インデックス１６９３（Ｉ３）を含み、他方の第二表にアクセスする鍵は第四インデックス１６９４（Ｉ４）を含む。第一表１６３０へのクエリが整合を戻すと、第二表１６４０ａ−ｂは無視され、第一表の整合入力はモストスペシフィック整合フィルタに対応する。しかし、第一表で整合が見つからない場合、第二表１６４０ａ−ｂのうちの一つへのクエリが整合を戻す場合もあり、この整合入力がモストスペシフィック整合フィルタに対応することになる。第一、第二表１６３０、１６４０ａ−ｂが整合を戻さない場合には、二次元フィルタ空間全体（つまり「＊，＊」）に対応するデフォルトフィルタをモストスペシフィックフィルタとして使用する。
【０１１２】
一つの実施形態においては、第一表１６３０と第二表１６４０ａ、１６４０ｂとがハッシュ表として実装される。この実施形態においては、ハッシュ関数を鍵に適用して（鍵１６９０あるいは第三、第四インデックス１６９３、１６９４）、第一、第二ハッシュ表を検索するのに使用する検索鍵を作成することもできる。もちろん、ハッシュ表が第一、第二表１６３０、１６４０ａ−ｂを実装可能な方法の一例を表しているのにすぎず、他の代わりのデータ構成を使用することもできることは理解されるべきである。
【０１１３】
今度は、図１７に図示している実施形態である、第二段データ構成１７００に注意を向ける。第二段データ構成１７００の構成は、上で説明した幾つかの構想から導かれる。初めに、そして最も重要なことは、移送レベル共有は第一段データ構成の多数の入力に対して、様々な移送レベルフィールドの組からなる幾らかのグループ、あるいはより正確には、１グループのトリプレットの共有を許す、ということであり、各トリプレットは一以上の移送レベルフィールド、動作、および相対優先度（ある規則の絶対優先度と区別される、規則組における相対優先度のこと）を含む。従って、各トリプレットグループは、つまり各小さなビンは、一度だけ記憶が必要となる。第二に、フィルタ交差部と関連付けられる二つ以上の小さなビンの和集合は論理的には大きなビンとして考えられるが、この大きなビンは記憶の必要はない、なぜなら第一段データ構成１６００の第一、第二表１６３０、１６４０ａ−ｂが一つのエントリに関連付けられた全ての小さなビンへのポインタを含んでいるからである。繰り返しになるが、別の実施形態においては、大きなビンを記憶してもよい場合もある。移送レベル共有を経て、第二段データ構成１７００は単に小さなビンに組織化されたトリプレットの一覧となり、さらに、移送レベル共有により提供される入力の減少により、第二段データ構成１７００のメモリ記憶要件は他の分類技術に比べると比較的少なくなる。
【０１１４】
図１７を参照すると、第二段データ構成１７００は幾つかのトリプレット１７１０を含み、各トリプレット１７１０は一以上の移送レベル（あるいは他の）フィールド１７１９ａ、動作１７１９ｂ、および相対優先度１７１９ｃを含んでいる。各トリプレット１７１０は小さなビン１７２０（つまり、小さなビン１７２０ａ，１７２０ｂ，...，１７２０ｋのうちの一つ）と関連付けられている。小さなビン１７２０ａ−ｋはトリプレット１７１０の幾つかのグループを含み、小さなビンが記憶されているメモリの位置は対応するポインタ１７２５により特定されてもよい（つまり、小さなビン１７２０ａは対応するポインタ１７２５ａにより特定され、小さなビン１７２０ｂは対応するポインタ１７２５ｂにより特定される、など）。上述のように、ビンポインタ１７２５ａ−ｋは転送表１６０２（図１６Ａ参照）に記憶される。小さなビン１７２５（あるいは、大きなビンが記憶されている場合は大きなビン）と関連付けられたポインタ１７２５が、第一段データ構成１６００へのクエリで特定されると、対応する小さなビンの全てのトリプレットが受信パケットと比較される。少なくとも一つの整合が見つかると、整合するトリプレットと関連付けられた動作を受信パケットに適用する。一つの実施形態においては、この動作が遭遇したもののなかで最も高い優先度を持つ。
【０１１５】
一つの実施形態においては、第二段データ構成１７００が、三値ＣＡＭのような、内容参照可能メモリ（ＣＡＭ）に実装されている。この実施形態においては、ＣＡＭは幾つかの入力を含み、各入力は第二段データ構成１７００のトリプレット１７１０の一つに関連付けられている。第二段データ構成１７００がＣＡＭに実装されている、さらなる実施形態においては、ＣＡＭへの入力（例えば、一以上の小さなビン１７２０と関連付けられたトリプレット１７１０）の数は並行して検索されることもある。
【０１１６】
図１８を参照すると、図示されているのはパケット分類法の一実施形態であり、これは図１〜１７と付随する上述の本文に示している二段パケット分類器を使用して行うことができる。この図のブロック１８０５でパケットが受信される。ブロック１８１０ａと１８１０ｂに記載の通り、ルックアップを送信元アドレスと送信先アドレスとに実行する（図１４の項目１４１０、１４２０、及び図１６Ａの項目１６１０、１６２０参照）。一つの実施形態においては、図１８に示すとおり、送信元・送信先アドレス上のクエリは並行して実行される。しかし、他の実施形態においては、これらクエリが並行して行われない場合もあることは理解されるべきである。送信元アドレスクエリに基づき、完全指定フィルタに関連付けられた最長接頭辞整合（ＬＰＭ）と、部分指定フィルタに関連付けられたＬＰＭが特定される（ブロック１８１５ａ参照）。整合する完全指定フィルタに関連付けられたインデックスＩ１と、整合する部分指定フィルタに関連付けられたインデックスＩ３が戻される（図１６Ｂの項目１６９１、１６９３参照）。同様に、送信先アドレス上のクエリから、完全指定フィルタに関連付けられた最長ＬＰＭと部分指定フィルタに関連付けられたＬＰＭとが特定され（ブロック１８１５ｂ参照）、整合する完全指定フィルタと関連付けられたインデックスＩ２と、整合する部分指定フィルタと関連付けられたインデックスＩ４とが戻される（図１６Ｂの項目１６９２、１６９４参照）。
【０１１７】
整合する完全指定フィルタと関連付けられた二つのインデックスＩ１とＩ２はその後組み合わせられて（例えば連結されて）鍵が形成され（図１６Ｂの項目１６９０参照）、この鍵を使用して第一表を検索する（図１６Ａと１６Ｃの項目１６３０参照）が、これはブロック１８２０ａに記載されている。ブロック１８２０ｂと１８２０ｃで、インデックスＩ３を使用して第二表のうちの一方を検索して、インデックスＩ４を使用して他方の第二表を検索する（図１６Ａの項目１６４０ａ、１６４０ｂ参照）。繰り返しになるが、第一表１６３０は全ての完全指定フィルタと完全指定フィルタ交差部と、他のフィルタとの間で統合できない全ての不在フィルタ（指標フィルタ）とを含んでいる。第二表１６４０ａ、１６４０ｂのうちの一方は送信元アドレスにワイルドカードを持つ部分指定フィルタを含み、第二表の他方は送信先アドレスにワイルドカードを持つ部分指定フィルタを含んでいるが、第二表には指標フィルタは含まれていない。一つの実施形態においては、図１８に示すように第一・第二表１６３０、１６４０ａ−ｂに対する検索を並行して行っている。しかし、他の実施形態においては、これら検索を並行して行わないこともある。
【０１１８】
ブロック１８２５を参照すると、鍵（Ｉ１とＩ２とから形成される）を第一表１６３０の各入力１６３２の鍵１６３７ａと比較する（図１６Ｃ参照）。整合が見つかった場合には、整合入力の中の一つあるいは複数のビンポインタ１６３７ｂにアクセスする（ブロック１８３０参照）。第一表を様々な方法で検索するべく、Ｉ１とＩ２とから形成される鍵を使用することができる。例えば、一つの実施形態においては、ハッシュ関数を鍵に適用して、該ハッシュを使用して、ハッシュ表として実装される第一表１６３０を検索する。
【０１１９】
第一表１６３０に整合が見つかった場合、第二表１６４０ａ−ｂは無視される。整合が第一表に見つからなかった場合、整合が第二表のうちの一方に見つかった場合には（ブロック１８３５参照）、その第二表の整合する入力のビンポインタにアクセスする（ブロック１８４０参照）。ここで、第二表のうちの片方しか整合入力を持たない（もし実際に整合が第二表に見つかるとした場合）ことに注意を喚起する。しかしもしも第一表、あるいは第二表のいずれにも整合が見つからなかったら、二次元アドレス空間全体に対応するデフォルト入力が使用され、この入力に関連するビンポインタにアクセスする（ブロック１８４５参照）。このとき、受信パケットはそのネットワーク経路に基づき分類されているので、工程は分類の第二段に移動する。
【０１２０】
今度はブロック１８５０を参照すると、ビンポインタのうちの一つにより特定される小さなビン（幾つかの実施形態においては、大きなビン）にアクセスする。受信パケットの移送レベルフィールドをアクセスされたビンの各入力と比較して（図１７参照）、アクセスされたビンが、整合する入力を持つか判断する（ブロック１８５５参照）
該アクセスされたビンが、整合する入力を含むときには（ブロック１８６０参照）、整合する入力に関連する動作を戻す（ブロック１８６５参照）。ブロック１８７０を参照すると、戻された動作はその後パケットに適用することができる。
【０１２１】
上述のように、第一表、あるいは第二表のうちいずれかへの入力は多数のポインタを含んでおり、各ポインタは小さなビンを特定している（つまり言い換えると、該入力は大きなビンと関連付けられているということである）。従って、アクセスされたビン内の全ての入力を考慮した後で（ブロック１８５５参照）、整合する入力が特定されなかった場合には（ブロック１８６０参照）、工程はその後、まだ考慮されていない他の別のポインタ（およびビン）に注意を向ける（ブロック１８５０参照）。クエリの対象となるビンがまだあれば、小さなビンにアクセスする上述の工程を繰り返す（ブロック１８５０、１８５５、１８６０参照）。従って、アクセスされていないビンポインタが残っている限りは、整合が見つかるまで小さなビンをアクセス、検索する工程を繰り返す。
【０１２２】
図１５に戻ると、前に記載した通り、Ｒ２などのほかのフィルタと統合できない領域（つまり指標フィルタ）を第一表１６３０に加える（第二表１６４０ａ−ｂには何も配置されていないが）。完全指定フィルタあるいはフィルタ交差部は幾多の指標フィルタを含むことができる。これは図１９に図示されており、ここでは、完全指定フィルタ（あるいはフィルタ交差部）１９１０と幾つかの他の「より狭い」完全指定フィルタ（あるいはフィルタ交差部）１９２０が示されている。一つの狭い完全指定フィルタ１９２０の送信元アドレスを他の狭いフィルタ１９２０の送信先アドレスを組み合わせると、繰り返しになるが、その結果は、送信元アドレスと送信先アドレスのルックアップ表へのクエリが独立して行われるという理由から、フィルタ１９１０に完全に含まれる幾つかの不在フィルタ１９３０を生成することになり、従って、他のフィルタとは統合できないことになる。従ってこれら指標フィルタ１９３０は、一つの実施形態においては、第一表１６３０に配置される。しかし、また別の実施形態においては、任意の完全指定フィルタと関連付けられた幾つかの指標フィルタには上限が設定されている。この指標フィルタの設定上限を超える完全指定フィルタあるいはフィルタ交差部のいかなるものに対して、フィルタとそれに関連付けられた指標フィルタは第一表１６３０に配置されない。図１９の完全指定フィルタ１９１０のようなフィルタは、設定された上限を超える指標フィルタを比較的多数網羅しており、「ワイド」フィルタ（通常比較的幅広い範囲の送信元・送信先アドレスに及ぶフィルタ）と称されることもある。
【０１２３】
上述の実施形態をさらに図２０Ａ〜２０Ｃに図示する。図２０Ａ、２０Ｂ、２０Ｃは図１６Ａ、１６Ｂ、１８とそれぞれ類似しており、同様の要素に関しては図２０Ａ−２０Ｃにおいても同一の数字記載をしていることに注意を喚起する。さらに、以下の本文で、幾つかの要素については上述の要素の説明を繰り返さない。
【０１２４】
図２０Ａを最初に参照すると、指標フィルタの特定の限界点を超えるフィルタは（ワイドフィルタ）、別個のデータ構成に配置されるがこれはワイドフィルタ表１６５０と称される。ワイドフィルタ表１６５０は各ワイドフィルタについて一つの入力を含む。一つの実施形態においては、ワイドフィルタ表１６５０はクロス生成表（図１５、１９参照）と類似したデータ構成を含む。殆どの実際の分類データベースにおいては、ワイドフィルタ数は少ないことが予期される。しかしワイドフィルタは潜在的に第一表１６３０に多数の入力を作成することがあるので、これらワイドフィルタを別個のデータ構成（第一・第二表と並行して検索できる）へ移動することで分類工程の効率を格段に向上させることができる。
【０１２５】
次に図２０Ｂを参照すると、分類の第一段中には、上述の通り、四つの異なるインデックス１６９１、１６９２、１６９３、１６９４（Ｉ１−Ｉ４）を送信元・送信先アドレス表１６１０、１６２０のクエリからそれぞれ戻す。上述の通り、第一・第二インデックス１６９１、１６９２は、完全指定フィルタに関連付けられた整合する送信元・送信先接頭辞に対応しており、一方またこれも上述の通り、第三・第四インデックス１６９３、１６９４は、部分指定フィルタに関連付けられた整合する送信元・送信先接頭辞に対応している。ワイドフィルタを計上する本実施形態においては、送信元・送信先アドレス表１６１０、１６２０のクエリはまた第五インデックス１６９５（Ｉ５）および第六インデックス１６９６（Ｉ６）を戻す。第五インデックス１６９５はワイドフィルタに関連付けられた整合送信元接頭辞に対応しており、第六インデックス１６９６はワイドフィルタに関連付けられた整合送信先接頭辞に対応している。なお、送信元アドレス表１６１０と送信先アドレス表１６２０との各々において、フィルタ種別指定１６１４ｂ、１６２４ｂはこの場合、入力が完全指定フィルタ、部分指定フィルタ、あるいはワイドフィルタのいずれと関連付けられているのかを示す。以下に記すように、第五インデックス１６９５と第六インデックス１６９６と（Ｉ５とＩ６）はその後組み合わせられて、ワイドフィルタ表１６５０のクエリに使用される鍵２０９０を形成する。
【０１２６】
図２０Ｃに図示されているのは二段パケット分類方法１８００の別の実施形態である。図２０Ｃに示す実施形態は先に図１８との関連で記載された実施形態と大体同じ態様で進められる。しかし、図２０Ｃに示した方法はワイドフィルタを計上に入れており、上述の通り、本実施形態はワイドフィルタ表１６５０、第五・第六ワイドフィルタインデックス１６９５、１６９６を使用する。
【０１２７】
図２０Ｃへ進むと、パケットが受信され（ブロック１８０５）、ルックアップを送信元・送信先アドレスに行う（ブロック１８１０ａ、１８１０ｂ）。ブロック１８１５ａに示すように、送信元アドレスクエリに基づき、完全指定フィルタに関連付けられた最長接頭辞整合（ＬＰＭ）と、部分指定フィルタに関連付けられたＬＰＭ、ワイドフィルタに関連付けられたＬＰＭと、及びインデックスＩ１、Ｉ３、Ｉ５とが戻される（図２０Ｂ、項目１６９１、１６９３、１６９５参照）。繰り返しになるが、Ｉ１は整合している完全指定フィルタと関連付けられており、Ｉ３は整合している部分指定フィルタと関連付けられており、Ｉ５は整合しているワイドフィルタと関連付けられている。同様に、送信先アドレスのクエリから、完全指定フィルタと関連付けられている最長ＬＰＭと、部分指定フィルタと関連付けられているＬＰＭと、ワイドフィルタと関連付けられているＬＰＭとを特定して（ブロック１８１５ｂ）、整合している完全指定フィルタと関連付けられているインデックスＩ２と、整合している部分指定フィルタと関連付けられているインデックスＩ４と、整合しているワイドフィルタと関連付けられているインデックスＩ６とを戻す（図２０Ｂの項目１６９２、１６９４、１６９６参照）。
【０１２８】
整合している完全指定フィルタと関連付けられている二つのインデックスＩ１とＩ２とはその後組み合わされて、第一表を検索するのに使用される鍵を形成し、インデックスＩ３とＩ４とを使用して第二表を検索する（ブロック１８２０ａ、１８２０ｂ、１８２０ｃ参照）。さらに、インデックスＩ５とＩ６とを組み合わせて鍵を形成して（図２０Ｂの項目２０９０参照）、この鍵を使用してワイドフィルタ表１６５０のクエリに使用する（ブロック１８２０ｄ参照）。一つの実施形態においては、第一表１６３０、第二表１６４０ａ−ｂ、及びワイドフィルタ表１６５０の検索を並行して行う（図２０Ｂ参照）。しかし、他の実施形態においては、これら検索を並行して行わない場合もある。
【０１２９】
ブロック１８２５を参照すると、鍵（Ｉ１とＩ２とから形成される）を第一表１６３０の各入力１６３２の鍵１６３７ａと比較して（図１６Ｃ）、整合が見つかったら、整合入力内の複数あるいは一つのビンポインタ１６３７ｂにアクセスする（ブロック１８３０参照）。しかし、本実施形態においては、第一表に整合が見つからなかったら、工程はワイドフィルタ表に進み（ブロック１８８５参照）、鍵（Ｉ５とＩ６とから形成される）をワイドフィルタ表内の各入力と比較する。ワイドフィルタ表で整合が見つかれば、ワイドフィルタ表の整合入力内のビンポインタにアクセスする（ブロック１８９０参照）。整合が第一表にもワイド表にも見つからなくて、第二表のうちの一方に見つかれば（ブロック１８３５参照）、第二表の整合入力内のビンポインタにアクセスする（ブロック１８４０）。もしも第一表、ワイドフィルタ表、あるいは第二表のうちのいずれにも整合が見つからなければ、二次元アドレス空間の全体に対応するデフォルト入力を使用して、この入力に関連するビンポインタにアクセスする（ブロック１８４５参照）。第一表１６３０に整合が見つかったら、他の表は無視し、第一表に整合が起こらなくて、ワイドフィルタ表１６５０に整合が見つかれば、第二表１６４０ａ−ｂを無視する。受信パケットのネットワーク経路に基づく分類は完成し、工程は分類の第二段へ進む。なお、第二段は前述の通りに進むので、図２０Ｃにはパケット分類の第二段を示していない。
【０１３０】
さて、第一・第二段データ構成を作成および／または更新する方法の実施形態に注意を移すことにする。図２１を参照すると、図示されているのは上述の二段パケット分類工程に使用されるデータ構成の作成および／または更新方法２１００の実施形態である。なお、図２１に記載の工程はパケット分類前に（あるいは一実施形態においてはその間に）行われる一組の前処理を含んでいる。しかし、開示された二段パケット分類体系に必要なデータ構成（第一段・第二段データ構成１６００、１７００）の作成および／または更新はパケット分類工程に比べると殆ど行われない。従って、開示されている分類技術を実行するのに必要な処理の大半は、比較的まれにしか行う必要のない一連の前処理にかなり前倒しにされる。
【０１３１】
図２１のブロック２１１０に関して、分類データベースの規則（図１０）は規則組にグループ分けされるが、各規則組の規則は同じ送信元・送信先アドレスを持っている（図１１Ａおよび１１Ｂ参照）。一つの実施形態においては、一つの規則組の規則は連続する優先度レベルを占有しており、他の実施形態においては、一つの規則組の規則は隣接する優先度レベルを占有してはいないことは上述の通りである。上述の通り、各規則組と関連付けられている送信元・送信先の対をフィルタとして言及する。ブロック２１２０に記載の通り、各フィルタと関連付けられた、移送レベル（あるいは他の）フィールドの組と、対応する動作と相対優先度とを、小さなビンに組織化する。
【０１３２】
ブロック２１３０を参照すると、受信パケットの送信元・送信先アドレス上の並行ＬＰＭクエリで使用される、送信元アドレスルックアップデータ構成と送信先アドレスルックアップデータ構成とが作成される（図１６Ａ、１６Ｂの項目１６０１参照）。送信元アドレスルックアップデータ構成はデータベース内の各フィルタの入力を含み、各フィルタの入力は送信元接頭辞、フィルタ種別指定（例えば、完全指定、部分指定、あるいはワイドといった）、およびインデックスを含んでいる。同様に、送信先アドレスルックアップデータ構成は各データベースフィルタの入力を含み、各入力はそのフィルタの送信先接頭辞、フィルタ種別指定、およびインデックスを含んでいる。
【０１３３】
第一段データ構成を完成する目的で転送表が構築される（図１６Ａの項目１６０２参照）。フィルタの交差部を決定し（図１２Ａ−１２Ｃ参照）、ブロック２１４０に記載の通り、各フィルタ交差部と関連付けられた小さなビンの和集合を、つまり大きなビンを見つける（図１１Ｂ参照）。指標フィルタも決定する（ブロック２１５０参照）。上述の通り、指標フィルタは、別のフィルタとは統合できない不在フィルタである（図１５と付随する本文参照）。ブロック２１６０に記載の通り、完全指定フィルタ、完全指定フィルタ交差部、及び指標フィルタをその後第一表に配置する（図１６Ａと１６Ｃ）。繰り返しになるが、一つの実施形態においては、完全に重複するフィルタ交差部（図１３Ａ−１３Ｃ）は第一表には配置しない。ブロック２１７０で、第二表が作成され、この第二表とは、「Ｘ＊，＊」の形式の部分指定フィルタを含む一つの第二表と、「＊，Ｙ＊」の形式の部分指定フィルタを含む他の第二表である。代替の実施形態においては、ワイドフィルタを、例えば特定の閾値を超える幾つかの指標フィルタを持つフィルタ（図１９参照）を、他の表（つまりワイドフィルタ表）に配置する（図２０Ａの項目１６５０参照）が、これがブロック２１９０に図示されている。
【０１３４】
ブロック２１８０を参照すると、第二段データ構成が作成される。前述のように、一つの実施形態においては、第二段データ構成は、各小さなビンと関連付けられたトリプレットの組を含んでいる（図１７参照）。小さなビンは第一・第二表に含まれるポインタにより特定される。本実施形態においては、大きなビンは第二段データ構成には記憶されず、大きなビンは単に二つ以上の小さなビンを示すポインタ一覧（第一あるいは第二表の入力）で特定されるだけである。別の実施形態においては（例えば、規則組が不連続な優先度レベルの規則を含むような場合）、大きなビンに関連付けられたトリプレットのグループはメモリに記憶される。
【０１３５】
上で示した通り、一つの実施形態においては、パケット分類の第一段はソフトウェアを用いて実現され、第二分類段はハードウェアで実現される。図２２〜２８に図示されているのは、第一段がソフトウェアで実装され、第二段がハードウェアで実装されている、二段分類システムの一つの実施形態である。本実施形態は一つのパケットヘッダの様々なフィールド間の整合スタイルの違いを利用する。例えば、送信元・送信先アドレスは一般的に接頭辞であるいは完全に指定された値として表現されるが、ポート数は範囲として表現されることがある。接頭辞あるいは完全に指定された値に基づく整合はソフトウェアを基にする解決を用いて実行できるが、ハードウェア解決が範囲整合には適切なことがあり、図２２〜２８の実施形態においては、分類の問題はこれらに倣って分岐している。この時点では、プロトコルは一般的に完全に指定された値であり、一つの実施形態においては、第二段でパケットをプロトコルの基づき分類する（前述のように）のではなく、下記で詳述するように、プロトコルに基づく分類を第一段で行う。
【０１３６】
さて図２２を参照すると、図示されているのはパケット分類システム２２００である。分類システム２２００は第一段コード実行の処理システム２２１０と分類の第二段実行を目的とする分類回路２２２０とを含む。分類回路２２２０と連結されているのは、ビン（例えば、上述のように小さなビンおよび／または大きなビン）を記憶するためのメモリ２２３０である。メモリ２２３０は、ビン２２４０ａ、２２４０ｂ、...、２２４０ｉを含む幾つかのビンを記憶できる任意の適切なメモリを含んでもよく、ここで各ビン２２４０ａ−ｉは一以上の入力２３００を含む（例えばビン２２４０ａは入力２３００ａ−ｂを含み、ビン２２４０ｂは入力２３００ｃ−ｇを含む、など）。例えば、メモリ２２３０はＳＲＡＭ、ＤＲＡＭ、ＤＤＲＤＲＡＭ、ＳＤＲＡＭ、および／または、フラッシュメモリを、ローカルな形あるいはチップ外に含んでもよい。一つの実施形態においては、メモリ２２３０はローカルあるいはチップ上のＳＲＡＭ（例えば「スクラッチ」メモリ）を含む。
【０１３７】
第一分類段は一連のソフトウェア命令（図２２に示したような、第一段コード２２５０）として実装され、処理システム２２１０はこれら命令を実行できる任意の適切な処理システムあるいは機器を含む。一つの実施形態においては、処理システム２２１０は、処理機器（例えばネットワークプロセッサ）の処理エンジン（例えばマイクロエンジン）を含み、該処理エンジンは、そのような処理エンジン上の幾つかのなかの一つが処理機器上に搭載されたようなものであってもよい。別の実施形態においては、処理システムはマイクロプロセッサあるいは他の処理機器を含む。上でも示したように、第二分類段はハードウェア実装することができ、分類回路２２２０は、分類の第二段を実行できる任意の適切なハードウェアあるいは回路を含む。処理システム２２１０と分類回路２２２０、およびメモリ２２３０の様々な実施形態を以下に記載する（例えば、図２５〜２７と以下の付随する本文参照）。
【０１３８】
図２２に示すように、メモリ２２３０は幾つかのビン２２４０ａ−ｉを記憶しており、各ビンは一以上の入力２３００を含んでいる。入力２３００のうち一つの一実施形態を図２３に図示する。この図を参照すると、入力２３００は幾つかの移送レベルフィールド２３１０、関連動作２３２０、及び相対優先度２３３０（例えば、前述のような、トリプレット）を含む。一つの実施形態においては、移送レベルフィールド２３１０は送信元ポートの下限（ＳＲＣＰＲＴＬＢ）２３１１、送信元ポートの上限（ＳＲＣＰＲＴＵＢ）２３１２、送信先ポートの下限（ＤＳＴＰＲＴＬＢ）２３１３、及び送信先ポートの上限（ＤＳＴＰＲＴＵＢ）２３１４を含む。受信パケットがビンの入力２３００に整合するか否かを判断する目的で、該パケットの送信元ポート（ＳＲＣＰＲＴＰＣＫＴ）を送信先ポートの上下限２３１１、２３１２と比較し、該パケットの送信先ポート（ＤＳＴＰＲＴＰＣＫＴ）を送信先ポートの上下限２３１３、２３１４と比較する。もし該パケットの送信元ポートが送信元ポートの下限２３１１より大きいか等しく、送信元ポートの上限２３１２より小さいか等しく、またもし該パケットの送信先ポートが送信先ポートの下限２３１３より大きいか等しく、送信先ポートの上限２３１４より小さいか等しい場合には、該パケットは該入力２３００と整合している。なお上述のように、この範囲整合方式は多数接頭辞へ範囲を拡大する必要を削減する。
【０１３９】
ＳＲＣＰＲＴＬＢ、ＳＲＣＰＲＴＵＢ、ＤＳＴＰＲＴＬＢ、ＤＳＴＰＲＴＵＢ、動作、および優先度を含む、入力２３００の各々を、ここでは「規則」と称する。従って、図２２〜２８の実施形態に関して使用される、「規則」という用語は、上述の一つの規則組と関連付けられた送信元・送信先アドレスの対のことを示す「フィルタ」という用語とは区別される。しかし、他の文脈においては「規則」および「フィルタ」という用語を同じ意味で使うこともできることは理解されるべきである。
【０１４０】
一つの実施形態においては、第二段の分類はプロトコルを計上に入れていないが、第一段では考慮に入れられる。従って、例えば、図２３の実施形態においては、規則２３００はプロトコルを移送レベルフィールド２３１０の中には含まない。しかし他の実施形態においては、前述のように、プロトコルに基づく分類が第二段で発生する（その場合、各ビンの規則２３００は移送レベルフィールド２３１０の一つとしてプロトコルを含むことがある）。
【０１４１】
第一段においてパケットをプロトコルに基づいて分類する目的で、プロトコル（これは繰り返しになるが通常、完全に指定される値であるが）、第一表、第二表を検索するのに用いられる検索鍵と連結されていてもよい。このことが図２４に図示されており、この図では並行ＬＰＭ表１６０１（図１６Ａ参照）の一実施形態が示されている。図２４においては、第一および第二インデックスＩ１、Ｉ２から形成される鍵１６９０がプロトコル（ＰＲＴＣＬ）２４５０と組み合わされて（例えば連結されて）、転送表１６０２（図１６Ａ参照）を検索するのに用いられる新たな検索鍵２４９０が形成される。同様に、第三インデックスＩ３がプロトコル２４５０と組み合わせられて、検索鍵２４９１が形成され、第四インデックスＩ４がプロトコル２４５０と組み合わせられて、検索鍵２４９２が形成される。ワイドフィルタ表を使用する場合には（図２０Ａ参照）、第五、第六インデックスＩ５、Ｉ６（図２０Ｂ）から形成される検索鍵２０９０が同様の方法でプロトコルと組み合わせられる。なお、様々な転送表（第一表、第二表、およびもしかすると、ワイドフィルタ表）の各入力に含まれる鍵もまたプロトコルを含むことがある（図１６Ｃの項目１６３７ａ）。
【０１４２】
今度は図２５を参照すると、図示されているのは、図２２〜２４において上述の二段パケット分類体系を実装できるシステム２５００の一実施形態である。一つの実施形態においては、システム２５００は図２と付随する本文に関して上述したものに類似したルータを備えており、同様の要素に関する説明はここでは繰り返さない。しかし、図２５の実施形態については、第二段ハードウェアは処理機器２６００の一部を含む。さらに、第一段コード２２５０がシステムメモリ２１０および／または記憶機器２３０に（あるいは別の実施形態においては処理機器２６００のメモリに）記憶されていてもよい。
【０１４３】
次に図２６へ進むと、処理機器２６００の一実施形態が示されている。処理機器２６００は、様々な機能部が連結されるローカルバス２６０５を含む。バス２６０５は、処理機器２６００の様々な機能部を相互接続する一以上のチップ上バスの集合体を表すことを意図している。ローカルバスを単一のバス２６０５で表して理解を促進しているが、処理機器２６００はこれに限られないことは理解されるべきである。当業者であれば、処理機器２６００がいかなる適切なバスアーキテクチャであってもよく、またいかなる数、および組み合わせのバスを含んでも構わないことは理解されるところである。
【０１４４】
コア２６１０および幾つかの処理エンジン２６２０（例えば処理エンジン２６２０ａ、２６２０ｂ、...、２６２０ｋ）はローカルバス２６０５と連結される。一つの実施形態においては、コア２６１０は、オペレーティングシステム２１４を実行することのできる汎用目的の処理システムを備えている。コア２６１０はさらに、処理エンジン２６２０へ実行のための命令を施すなど、処理機器２６００の操作を制御すること、および様々な管理機能を発揮することができる。処理エンジン２６２０ａ−ｋの各々は、任意の適切な処理システムを含み、各々が算出・論理部（ＡＬＵ）、制御機、および幾つかのレジスタ（読み出し・書き込み操作中のデータ記憶の目的で）を含むことができる。さらに、一つの実施形態においては、各処理エンジン２６２０ａ−ｋは多数の（例としては４つの）実行スレッドを提供する。
【０１４５】
さらにローカルバス２６０５と連結されているのは、幾つかのビンを記憶するためのメモリ２６３０である。メモリ２６３０は幾つかのビン（例えば、小さなビンおよび／または大きなビン）を記憶できる、任意の種類のメモリ、あるいはメモリの組み合わせを含むことができる。一つの実施形態においては、メモリ２６３０はＳＲＡＭ（例えば、「スクラッチ」メモリ）を含んでいる。他の実施形態においては、メモリ２６３０はＳＤＲＡＭ、ＤＤＲＤＲＡＭ、および／またはフラッシュメモリ（例としてはＦｌａｓｈＲＯＭ）を含んでいる。
【０１４６】
処理機器２６００はさらに、ローカルバス２６０５と連結されたバスインターフェース２６４０を含む。バスインターフェース２６４０は、システム２５００の他の部材間（バス２０５を含む）にインターフェース接続を提供する。簡略化の目的から、バスインターフェース２６４０は単一の機能部として図示しているが、実際には処理機器２６００は多数のバスインターフェースを含むことができることは理解されるべきである。例えば、処理機器２６００はＰＣＩバスインターフェース、ＩＸ（インターネット交換）バスインターフェースおよびその他を含むことができ、バスインターフェース２６４０は一以上のそのようなインターフェースの集合体を表すことを意図している。
【０１４７】
一つの実施形態においては、第一段コードが実行される処理システムは処理エンジン２６２０ａ−ｋのうちの一つ（例えば、処理エンジン２６２０ｂ）を含む。上で記載したように、一つの実施形態においては、第一段コード（あるいはこれら命令の一部）を処理機器２６００のメモリに記憶することもできる。一つの実施形態においては、第一段コードはチップ上メモリ（例えば、メモリ２６３０あるいはバス２６０５と連結された別のメモリ）に記憶することができる。別の実施形態においては、第一段コードあるいはこのコードの一部は処理エンジンのうち一つのメモリに（例えば、処理エンジン２６２０ｂのメモリ２６２５に）記憶することもできる。
【０１４８】
パケット分類の第二段を実行する目的で、処理機器２６００は、バス２６０５に連結された分類回路２７００を含む。分類回路２７００はパケットを一以上の移送レベルフィールド（あるいはその他のフィールド）に基づき分類することのできる任意の適切な回路あるいは論理を含む。分類回路の一実施形態を図２７に関連して以下に指示、記載する。
【０１４９】
図２６に関連して図示および記載される処理機器２６００の実施形態は、パケット分類器に関して開示された実施形態とともに使用できる処理機器の一例にすぎず、さらには、処理機器２６００は図２６に示されたもの以外の部材を持つこともできるが、そうした部材については明瞭化および理解の促進の観点から省いている。例えば、処理機器２６００は他の機能部（例えば、命令デコーダ部、アドレス翻訳部など）、熱管理システム、クロック回路、追加的メモリ、及びレジスタを含むことができる。さらに、処理機器は図２６に示した要素の全てを含まなくてもよいことも理解されるべきである。
【０１５０】
今度は図２７へ進むと、上述のような分類回路２７００の一実施形態が示されている。しかしながら、図２７に図示されている分類回路２７００の実施形態は第二分類段を実装できるハードウェアの一例にすぎない。この図を参照すると、分類回路２７００は第一比較回路２７１０、第二比較回路２７２０、出力回路２７３０を含む。第一比較回路２７１０は、受信パケットの送信元ポートと、ビンの規則の送信元ポート下限・上限との間の比較を行うことのできる任意の回路を含む。第二比較回路２７２０は該受信パケットの送信先ポートと、該規則の送信先ポート下限・上限との間の比較を行うことのできる任意の回路を含む。
【０１５１】
第一比較回路２７１０は受信パケットの送信元ポートが規則の送信元ポート下限より大きいか等しいか、および該規則の送信元ポート上限より小さいか等しいかどうかを判断する。この条件が真である場合、第一比較回路は信号２７１３（例えば、論理「高」信号）を出力回路２７３０に提供する。同様に、第二比較回路２７２０は、受信パケットの送信先ポートが該規則の送信先ポート下限よりも大きいか等しいか、および送信先ポート上限より小さいか等しいかどうかを判断して、もしこの条件が偽である場合、前記第二比較回路２７２３は信号２７２３（例えば、論理高信号）を出力回路２７３０に提供する。なお、比較回路２７１０、２７２０の比較結果のいずれかが偽である場合、比較回路はまた、条件が偽であることを示す信号（例えば、論理「低」信号）を提供する。
【０１５２】
任意の規則について、出力回路２７３０は各比較回路２７１０、２７２０から、それぞれ比較の結果が真であることを示す信号を受信すると、出力回路２７３０は整合信号２７３７（例えば論理高信号）を提供する。逆に、もしも第一・第二比較回路２７１０、２７２０のいずれかがそれぞれの比較の結果が真であることを示す信号を提供できない場合には、出力回路２７３０は整合失敗信号２７３９（例えば、論理低信号）を提供する。この整合信号および整合失敗信号２７３７、２７３９は第一段コードを実行する処理エンジンに提供することができる。従って、出力回路２７３０は本質的に、「ＡＮＤ」操作を第一・第二比較回路２７１０、２７２０の出力について行う。
【０１５３】
図２８を参照すると、図示されているのは、図２２〜２７に図示されている二段パケット分類システムを使用して実行できる、パケットの分類方法の一実施形態である。ブロック２６０５でパケットが受信される。その後、送信元アドレスと送信先アドレスとにルックアップを行う（ブロック２６１０ａ、２６１０ｂ参照）。一つの実施形態においては、図２６に示すように、送信元・送信先アドレスへのクエリは並行して行われる。しかし、他の実施形態においては、これらクエリは並行して行われない場合もあることは理解されるべきである。
【０１５４】
送信元アドレスクエリに基づき、完全指定フィルタに関連付けられた最長接頭辞整合（ＬＰＭ）と部分指定フィルタに関連付けられたＬＰＭとを特定する（ブロック２６１５ａ）。整合する完全指定フィルタに関連付けられたインデックスＩ１と、整合する部分特定フィルタに関連付けられたインデックスＩ３とを戻す（図２４の項目１６９１、１６９３参照）。送信先アドレスへのクエリに基づき、完全指定フィルタに関連付けられた最長ＬＰＭと部分指定フィルタに関連付けられたＬＰＭとを特定して（ブロック２６１５ｂ）、整合する完全指定フィルタに関連付けられているインデックスＩ２と、整合する部分指定フィルタに関連付けられているインデックスＩ４とを戻す（図２４の項目１６９２、１６９４参照）。
【０１５５】
一つの実施形態においては、ブロック２６２０ａで、第一インデックスＩ１、第二インデックスＩ２、およびプロトコルがその後組み合わせられて（例えば連結されて）、鍵が形成され（図２４の項目２４９０）、この鍵を使用して第一表を検索する。ブロック２６２０ｂにて、第三インデックスＩ３がプロトコルと組み合わせられて、検索鍵が作成され（図２４の項目２４９１参照）、この鍵を使用して第二表のうちの一方を検索する。同様に、ブロック２６２０ｃにて、第四インデックスＩ４がプロトコルと組み合わせられて、検索鍵が作成され（図２４の項目２４９２参照）、この鍵を使用して第二表のうちの他方を検索する。一つの実施形態においては、図２６に示すように、第一・第二表に対する検索は並行して行われるが、他の実施形態においては、これら検索は並行して行われなくてもよい。
【０１５６】
図２６の実施形態については、プロトコルに基づく分類は第一段で発生していたが、他の実施形態においては、プロトコルは第二分類段中に考慮されても構わない（例えば、プロトコルが、ビンに含まれる各規則に含まれるフィールドのうちの一つとして含まれていても構わない）。さらに、図２６の実施形態では、転送表がワイドフィルタ表を含まないことを前提としていたが、他の実施形態においては、転送表がワイドフィルタ表（図２０Ａ〜２０Ｃ参照）を含むこともできることは理解されるべきである。転送表がワイドフィルタ表を含む場合には、並行ＬＰＭ表から戻されるインデックスＩ５とＩ６とを上述と同様の方法で取り扱うことができる（例えば、ワイドフィルタ表を検索するのに使用される鍵を形成するプロトコルと組み合わせられる、ここでワイドフィルタ表に整合がもしあれば、この整合を第二表の整合よりも優先させる）。
【０１５７】
ブロック２６２５にて、Ｉ１と、Ｉ２と、及びプロトコルとから形成された鍵を第一表の入力と比較する。Ｉ１と、Ｉ２と、及びプロトコルとから形成された鍵は、第一表を様々な方法で検索するのに使用することができる。例えば、一つの実施形態においては、ハッシュ関数を該鍵に適用して、該ハッシュを使用して、ハッシュ表として実装される第一表を検索する。第一表に整合が見つかった場合、第一表の整合入力のために分類回路に命令を発行する（ブロック２６３０参照）。第一表の整合入力は検索が必要な一以上のビンを特定する。
【０１５８】
同様のやり方で、ブロック２６３５において、Ｉ３とプロトコルとから形成される鍵と、Ｉ４とプロトコルとから形成される鍵とが各々第二表の適切な方の入力と比較される。繰り返しになるが、これら鍵は任意の適切な技術によって第二表を検索するのに使用することができる（例えば、鍵にハッシュ関数を適用して、その結果を使用して、ハッシュ表として実装される第二表を検索する）。第二表のうちの一方に整合が見つかったら（繰り返しになるが、整合がもしあるとしたら、第二表の一方だけが整合を提供すべきである）、整合する入力を含む第二表の整合する入力に対応する命令を分類回路に発行する（ブロック２６４０参照）。この第二表の整合する入力は一以上の検索が必要なビンを特定する。なお、第一表に整合が見つかると、第二表は無視される。
【０１５９】
ブロック２６４５を参照すると、第一表には整合が見つからず、さらには、第二表のいずれにも整合が見つからない場合（ブロック２６２５、２６３５参照）、分類エンジンにデフォルト入力（例えば、二次元アドレス空間全体「＊，＊」に対応する入力）に対応する命令を発行する。デフォルト入力は一以上の検索が必要な関連ビンを持つ。
【０１６０】
一つの実施形態においては、分類回路に発行された命令はビンの（あるいはビンのうち一つの）起点の基アドレスと、該ビンに含まれる幾つかの入力または規則とを含む。例えば、戻って図２２を参照すると、命令はビン２４４０ａ−ｉのうち一起点の基アドレスと、そのビン内に含まれる幾つかの入力２３００を指定することができる。なお、幾つかの実施形態においては、命令中参照できる入力の最大数は限られている場合があり（例えば１６に限られている）、全ての規則および／あるいはビンを検索する目的からは、多数の命令を発行する必要がある場合があり、このことを以下で詳述する。分類回路に発行される命令は、特定されたビンを検索するのに使用される値をさらに含むことができる。一つの実施形態においては、検索値は受信パケットの送信元ポートと該パケットの送信先ポートとを含む。
【０１６１】
受信パケットの分類は第二分類段へ進む。ブロック２６５０を参照すると、分類回路に発行された命令中特定される規則は、例えば転送表の整合する入力に関連付けられた一つあるいは複数のビンの規則は、ビンメモリから分類回路へコピーされる。分類回路はこれら規則と検索値とを（例えば、受信パケットの送信元・送信先ポートを）比較する（ブロック２６５５参照）。一つの実施形態においては、図２３と図２７とに示されているように、各規則が送信元ポートの下・上限と、送信先ポートの下・上限とを指定する。受信パケットの送信元ポート（ＳＲＣＰＲＴＰＣＫＴ）を送信元ポートの下限（ＳＲＣＰＲＴＬＢ）と送信元ポートの上限（ＳＲＣＰＲＴＵＢ）と比較して、ＳＲＣＰＲＴＰＣＫＴがＳＲＣＰＲＴＬＢとＳＲＣＰＲＴＵＢとが規定する範囲内に在るか否かを判断する（例えば、ＳＲＣＰＲＴＬＢ＜＝ＳＲＣＰＲＴＰＣＫＴ＜＝ＳＲＣＰＲＴＵＢであるか否か）。同様に、受信パケットの送信先ポート（ＤＳＴＰＲＴＰＣＫＴ）を送信先ポートの下限（ＤＳＴＰＲＴＬＢ）と送信先ポートの上限（ＤＳＴＰＲＴＵＢ）と比較して、ＤＳＴＰＲＴＰＣＫＴがＤＳＴＰＲＴＬＢとＤＳＴＰＲＴＵＢとが定義する範囲内に在るか否かを判断する（例えば、ＤＳＴＰＲＴＬＢ＜＝ＤＳＴＰＲＴＰＣＫＴ＜＝ＤＳＴＰＲＴＵＢであるか否か）。
【０１６２】
ブロック２６６０を参照すると、もし整合が規則のうちの一つに見つかったら、該整合する規則に関連付けられた動作が分類回路により戻される（ブロック２６６５参照）。一つの実施形態においては、整合規則は特定された第一整合規則を備える。この時点では、分類の第二段は完成しており、受信パケットに動作を適用してもよい（ブロック２６７０参照）。
【０１６３】
上で記した通り、転送表（例えば、第一表、第二表のなかの一方、デフォルト入力、および、もしかするとワイドフィルタ表）の中の整合する入力は、分類回路に発行される任意の命令が取り扱うことのできる最大値以上の規則を含むビン（あるいは多数のビン）を特定することがある。従って、戻ってブロック２６６０において、検索されていない追加的な規則があり、さらに分類回路にコピーされた規則に整合が見つからない場合（ブロック２６５０）、他のビンおよび／または規則に対応する、追加的な命令を分類回路に発行することができる（ブロック２６７５）。これら追加的な規則はその後分類回路にコピーされ（ブロック２６５５）、上記工程をこの追加的規則組のために繰り返す。転送表中、整合する入力が特定する全てのビンおよび／または規則を検索する目的上必要な量の命令は幾らでも分類回路に発行することができる。
【０１６４】
上で詳述した明細書と付随する図面は全て例示的であり、限定的ではない。それらは開示の実施形態の明瞭で包括的な理解を第一の目的として提供されており、そこから不要な限定を解釈すべきものではない。当業者であれば、ここに記載された実施形態に対する多数の追加、削除、および変形を、構成の代替とともに、開示された実施形態の精神と付随請求項の範囲から逸脱することなく行うことができるであろう。
【図１】
2007533207.tif 000003
【図２】
2007533207.tif 000004
【図３】
2007533207.tif 000005
【図４】
2007533207.tif 000006
【図５Ａ】
2007533207.tif 000007
【図５Ｂ】
2007533207.tif 000008
【図５Ｃ】
2007533207.tif 000009
【図６】
2007533207.tif 000010
【図７】
2007533207.tif 000011
【図８】
2007533207.tif 000012
【図９】
2007533207.tif 000013
【図１０】
2007533207.tif 000014
【図１１Ａ】
2007533207.tif 000015
【図１１Ｂ】
2007533207.tif 000016
【図１２Ａ】
2007533207.tif 000017
【図１２Ｂ】
2007533207.tif 000018
【図１２Ｃ】
2007533207.tif 000019
【図１３Ａ】
2007533207.tif 000020
【図１３Ｂ】
2007533207.tif 000021
【図１３Ｃ】
2007533207.tif 000022
【図１４】
2007533207.tif 000023
【図１５】
2007533207.tif 000024
【図１６Ａ】
2007533207.tif 000025
【図１６Ｂ】
2007533207.tif 000026
【図１６Ｃ】
2007533207.tif 000027
【図１７】
2007533207.tif 000028
【図１８】
2007533207.tif 000029
【図１９】
2007533207.tif 000030
【図２０Ａ】
2007533207.tif 000031
【図２０Ｂ】
2007533207.tif 000032
【図２０Ｃ】
2007533207.tif 000033
【図２１】
2007533207.tif 000034
【図２２】
2007533207.tif 000035
【図２３】
2007533207.tif 000036
【図２４】
2007533207.tif 000037
【図２５】
2007533207.tif 000038
【図２６】
2007533207.tif 000039
【図２７】
2007533207.tif 000040
【図２８】
2007533207.tif 000041
【国際調査報告】
2007533207.tif 000042
2007533207.tif 000043
2007533207.tif 000044