(57)【要約】  本発明は、複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを検索するパケット分類器に適用される。本発明のパケット分類器は、決定木（Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ）を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込み、検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定し、特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する。
2011108168.tif 000002
【特許請求の範囲】
【請求項１】
複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを、複数種類の予め決められた少数の長さのビット配列を用いて検索するパケット分類器であって、
決定木（Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ）を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込み、
検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定し、
特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する、
ことを特徴とするパケット分類器。
【請求項２】
前記パケット分類器は、
決定木を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込む処理をパイプライン制御によって行うツリーパイプライン処理回路と、
検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定する処理と、特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する処理と、をパイプライン制御によって行うプライオリティパイプライン処理回路と、
を備えることを特徴とする請求項１に記載のパケット分類器。
【請求項３】
前記ツリーパイプライン処理回路は、
決定木の根ノードから開始し、深さ方向に１つノードを辿る処理を実行する複数のツリーパイプライン処理部を備え、
さらに、前記複数のツリーパイプライン処理部の各々は、
当該ツリーパイプライン処理部で処理するノードの領域分割情報を記憶する領域分割情報記憶ブロックと、
領域分割情報を読み出すメモリコントローラと、
領域分割情報を基に、入力された検索キーを用いて領域分割を行い、後段のツリーパイプライン処理部で処理するノードの領域分割情報が記憶された領域分割情報記憶ブロックに対するアドレス値を算出する領域分割回路と、
検索キーの有効ビット長を更新する有効ビット長更新回路と、
当該ツリーパイプライン処理部に入力された検索キーにある一定の遅延を持たせ、他の出力と同期させるための検索キー遅延回路と、を備え、
さらに、前記領域分割回路は、
当該ノードの領域分割情報から領域分割に用いるヘッダフィールド毎にその分割数を切り出す領域分割情報分離回路と、
ヘッダフィールド毎に領域分割処理を行うフィールド分割回路と、
前記領域分割情報分離回路の出力と前記フィールド分割回路の出力とを基に、後段のツリーパイプライン処理部で処理するノードの領域分割情報が記憶されたアドレス値を決定する決定部と、を備え、
前記プライオリティパイプライン処理回路は、
前記ツリーパイプライン処理部で処理したノードのルール識別子リストに対して、そのルール識別子リストと、ルール識別子リストの順序とビット位置とが対応付けられたビット配列と、を参照しながら、適合するルールを特定する処理と、それまでに適合すると判断したルールの中から優先度に応じてその時点で最も適合するルールを決定する処理と、を実行する複数のプライオリティパイプライン処理部を備え、
さらに、前記複数のプライオリティパイプライン処理部の各々は、
検索キーに含まれる各ヘッダフィールドのデータを抽出するフィールド分離回路と、
前記ツリーパイプライン処理部から指定されたアドレス値から実際にルール識別子リストを有するノードであるかを判断するアドレス変換回路と、
当該ノードの前記ビット配列を選択する複数のビット配列選択回路と、
適合ルール候補のうち最も適合するルールを選択する優先度チェック回路と、
ルール識別子リストを記憶するルールＩＤリスト記憶ブロックと、を備え、
さらに、前記ビット配列選択回路は、
検索キーから切り出したヘッダフィールドの値によって適切な前記ビット配列を選択する探索回路と、
ビット配列を記憶するビット配列記憶ブロックと、を備える、
ことを特徴とする請求項２に記載のパケット分類器。
【請求項４】
前記決定木のノードにおける領域分割情報は、
当該ノードが決定木における葉ノードであるか否かを示すフラグと、
決定木の各ノードにおいて領域を分割するために用いる特定数のヘッダフィールドに対する当該ノードにおける分割数と、
当該ノードの子ノードの領域分割情報が格納されている領域分割情報記憶ブロックに対するベースアドレスと、
当該ノードが実ノードではなく仮想ノードであることを示すフラグと、から構成され、
前記分割数は、当該ヘッダフィールドに対して２ｋで分割する場合に、ｋで指定される
ことを特徴とする請求項３に記載のパケット分類器。
【請求項５】
前記複数のツリーパイプライン処理部の各々は、
さらに、各ノードにおける領域分割情報の分割数をフィールド識別子によって識別し、そのフィールド識別子を実際のルールに規定されたヘッダフィールドと対応付け、必要な情報を抽出するフィールド抽出回路を備える、
ことを特徴とする請求項３に記載のパケット分類器。
【請求項６】
前記決定木のノードにおける領域分割情報は、
当該ノードが決定木における葉ノードであるか否かを示すフラグと、
決定木の各ノードにおいて領域を分割するために用いるヘッダフィールドの当該ノードにおける分割数を示すフィールド識別子と分割数の組と、
当該ノードの子ノードの領域分割情報が格納されている領域分割情報記憶ブロックに対するベースアドレスと、
当該ノードが実ノードではなく仮想ノードであることを示すフラグと、から構成され、
前記分割数は、当該ヘッダフィールドに対して２ｋで分割する場合に、ｋで指定される
ことを特徴とする請求項５に記載のパケット分類器。
【請求項７】
前記パケット分類器は、
ヘッダフィールド単位または特定のビット長単位に独立に構成した複数の決定木に対し、それぞれの決定木毎に、検索キーのうち予め決められたデータ毎にルールを絞り込み、決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合する可能性のあるルールを特定し、解候補ルール識別子リストを生成する処理をパイプライン制御によって行う複数の決定木処理回路と、
前記複数の決定木処理回路で特定された解候補ルール識別子リストから優先度の高い最も適合するルールを選択する最適解選択回路と、
各決定木処理回路が処理する決定木に対応する検索キーを抽出する検索キー分離回路と、
を備えることを特徴とする請求項１に記載のパケット分類器。
【請求項８】
前記決定木処理回路は、
決定木を用いて、多数のルールから適合する可能性のあるルールを絞り込む処理をパイプライン制御によって行うツリーパイプライン処理回路と、
解候補選択回路と、を備え、
さらに、前記ツリーパイプライン処理回路は、
決定木の根ノードから開始し、深さ方向に１つノードを辿る処理を実行する複数のツリーパイプライン処理部を備え、
さらに、前記複数のツリーパイプライン処理部の各々は、
当該ツリーパイプライン処理部で処理するノードの領域分割情報を記憶する領域分割情報記憶ブロックと、
領域分割情報を読み出すメモリコントローラと、
領域分割情報を基に、入力された検索キーを用いて領域分割を行い、後段のツリーパイプライン処理部で処理するノードの領域分割情報が記憶された領域分割情報記憶ブロックに対するアドレス値を算出する領域分割回路と、
検索キーの有効ビット長を更新する有効ビット長更新回路と、
当該ツリーパイプライン処理部に入力された検索キーにある一定の遅延を持たせ、他の出力と同期させるための検索キー遅延回路と、を備え、
さらに、前記領域分割回路は、
当該ノードの領域分割情報から領域分割に用いるヘッダフィールド毎にその分割数を切り出す領域分割情報分離回路と、
ヘッダフィールド毎に領域分割処理を行うフィールド分割回路と、
前記領域分割情報分離回路の出力と前記フィールド分割回路の出力とを基に、後段のツリーパイプライン処理部で処理するノードの領域分割情報が記憶されたアドレス値を決定する決定部と、を備え、
前記解候補選択回路は、
検索キーに含まれる各フィールドのデータを抽出するフィールド分離回路と、
前記ツリーパイプライン処理部から指定されたアドレス値から実際にルール識別子リストを有するノードであるかを判断するアドレス変換回路と、
当該ノードの前記ビット配列を選択する複数のビット配列選択回路と、
前記ルール識別子リストを記憶するルールＩＤリスト記憶ブロックと、
前記ビット配列とルール識別子リストを用いて、解候補ルール識別子リストを生成する解候補選択回路と、を備える、
ことを特徴とする請求項７に記載のパケット分類器。
【請求項９】
複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを検索するパケット分類器によるパケット分類方法であって、
決定木を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込み、
検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定し、
特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する、
ことを特徴とするパケット分類方法。
【請求項１０】
複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを検索するコンピュータに、
決定木を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込む処理と、
検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定する処理と、
特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する処理と、
を実行させることを特徴とするパケット分類プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット分類器に関し、特に、複数のパケットヘッダフィールドを検索キーとするパケット分類器に関する。
【背景技術】
【０００２】
パケット分類（Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）は、ネットワーク上のルータやスイッチにおいて、パケットを、フローと呼ぶ一連のパケット列に分類するための重要な技術であり、個々のフローに対するＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）の提供にとって、また、ファイヤウォール（Ｆｉｒｅｗａｌｌ）、ネットワーク侵入検知システム（ＮＩＤＳ：Ｎｅｔｗｏｒｋ  Ｉｎｔｒｕｓｉｏｎ  Ｄｅｔｅｃｔｉｏｎ  Ｓｙｓｔｅｍ）、ネットワーク侵入防止システム（ＮＩＰＳ：Ｎｅｔｗｏｒｋ  Ｉｎｔｒｕｓｉｏｎ  Ｐｒｅｖｅｎｔｉｏｎ  Ｓｙｓｔｅｍ）等のセキュリティ等、付加的な価値をもつネットワークアプリケーションの実現にとって、必要不可欠な技術である。【０００３】
パケット分類では、例えば、パケットのＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ヘッダに定義されている送信元ＩＰアドレス、宛先ＩＰアドレス、プロトコル番号に加え、ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｃｏｌ）／ＵＤＰ（Ｕｓｅｒ  Ｄａｔａｇｒａｍ  Ｐｒｏｔｃｏｌ）ヘッダに定義されている送信ポート番号、宛先ポート番号といった複数のパケットヘッダフィールドを検索キーとする。この検索キーによって特定される一連のパケット列をフローと呼ぶ。なお、上記の５つのパケットヘッダフィールドは一般的に５−ｔｕｐｌｅと呼ばれている。この検索キーは、予めルール（フィルタと呼ばれることもある）として定義されており、特に、このような複数のパケットヘッダフィールドを用いたパケット分類はＭｕｌｔｉ−Ｆｉｅｌｄ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎと呼ばれる。さらに、ルールにおけるマッチング手法として、パケットヘッダフィールドをある特定の値として定義するＥｘａｃｔ  Ｍａｔｃｈ、パケットヘッダフィールドの上位の複数ビットは特定するが下位の数ビットはワイルドカード（ｗｉｌｄｃａｒｄ）‘＊’を用いて不定として定義するＰｒｅｆｉｘ  Ｍａｔｃｈ、２つのある特定の値の範囲としてパケットヘッダフィールドを定義するＲａｎｇｅ  Ｍａｔｃｈ、パケットヘッダフィールドを個々のビット単位でワイルドカードを指定して定義するＷｉｌｄｃａｒｄ  Ｍａｔｃｈといった手法が用いられる。例えば、８ｂｉｔｓのパケットヘッダフィールドを考えた場合、パケットヘッダフィールドを“００１１０１０１”のように特定値として指定するものがＥｘａｃｔ  Ｍａｔｃｈ、パケットヘッダフィールドを、“００１１＊＊＊＊”のように、“００１１”の４ｂｉｔｓから始まる値として指定するものがＰｒｅｆｉｘ  Ｍａｔｃｈ、［３−６４］のようにパケットヘッダフィールドが１０進数で考えた際に３から６４の範囲に入っていればよいとするものがＲａｎｇｅ  Ｍａｔｃｈ、“０＊＊１０＊０１”のようにパケットヘッダフィールドのビット単位でワイルドカードが使用できるものがＷｉｌｄｃａｒｄ  Ｍａｔｃｈとなる。【０００４】
このようなＭｕｌｔｉ−Ｆｉｅｌｄ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ技術においては、ルールセットの大容量化とリンク速度の向上により、ルータやスイッチをいかに高速に処理させるかが１つの技術的な課題となっており、現状、その高速処理を実現するために、Ｔｅｒｎａｒｙ  Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ（ＴＣＡＭ）が用いられることが多い。【０００５】
しかしながら、ＴＣＡＭはコストが高く、消費電力量や回路規模も大きいといった課題が存在する。また、Ｒａｎｇｅ  Ｍａｔｃｈを用いた場合には、そのルールをＰｒｅｆｉｘ  Ｍａｔｃｈを用いたルールに分割する必要があるため、ルール数が増加してしまうといった課題もある。【０００６】
一方、ＴＣＡＭの高コスト、高消費電力の問題を回避すべく、より低コスト、より低消費電力なＳｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＳＲＡＭ）やＤｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ（ＤＲＡＭ）を用いた様々なＭｕｌｔｉ−Ｆｉｅｌｄ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ手法が提案されている。【０００７】
例えば、非特許文献１では、ＨｙｐｅｒＣｕｔｓと呼ばれる、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ（決定木）を用いた手法が提案されている。このようなＤｅｃｉｓｉｏｎ  Ｔｒｅｅをベースにした手法について図１、図２、図３を用いて簡単に説明する。【０００８】
図１は、それぞれ４ｂｉｔｓから構成される２つのフィールドＸ、Ｙを用いて定義されたＲ０からＲ１１までの１２個のルールからなるルールセットの例を示す図である。フィールドＸ、Ｙは、ここではそれぞれ４ｂｉｔｓとしているが、例えば送信元ＩＰアドレスや送信元ポート番号等、実際のパケットヘッダフィールドに相当するものとする。なお、フィールドＸは、２進数で表記しており、‘＊’はその値が０でも１でも良いワイルドカードを示している。また、フィールドＹは、Ｒａｎｇｅ  Ｍａｔｃｈで表記してあり、“［ａ：ｂ］”のａはその下限値（１０進数表記）、ｂはその上限値（１０進数表記）で示している。また、一般的に、各ルールに対しては、優先度（Ｐｒｉｏｒｉｔｙ）とそのルールに該当した場合のパケットの扱い方（Ａｃｔｉｏｎ）が付与されているが、ここではそれらは省略している。【０００９】
このようなルールセットに対して、フィールドＸ、Ｙの２次元から成る空間上にそれぞれのルールを図示したものが図２である。図２は、図１のルールセットを２次元空間（フィールドＸとＹで表された空間）上で示した図である。なお、Ｘ軸、Ｙ軸上の数はそれぞれ１０進数で表記してある。【００１０】
ＨｙｐｅｒＣｕｔｓをはじめとする、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅをベースにした手法では、図２に示すような空間をある複数の次元に着目して分割し、分割された領域内に存在するルール数がある閾値以下になるまで、領域分割を行うことでＤｅｃｉｓｉｏｎ  Ｔｒｅｅを構築する。ここで、分割された領域で管理されるルール群をルールリストと呼ぶ。図３は、図１のルールセットに対して構築した基本的なＤｅｃｉｓｉｏｎ  Ｔｒｅｅの一例を示した図である。なお、図３に示すＤｅｃｉｓｉｏｎ  Ｔｒｅｅでは、分割領域内のルール数である閾値を２としている。図３では、まず、ＸとＹの両方を２分割することで、４つの領域に分割している。この結果、全空間（Ｘ、Ｙ）＝（［０：１５］、［０：１５］）が、領域０（［０：７］、［０：７］）、領域１（［０：７］、［８：１５］）、領域２（［８：１５］、［０：７］）、領域３（［８：１５］、［８：１５］）の４つの領域に分割される。このとき、それぞれの領域で管理されるルールリストは、［Ｒ５、Ｒ６、Ｒ７、Ｒ９］（領域０）、［Ｒ０、Ｒ３、Ｒ５、Ｒ６、Ｒ１１］（領域１）、［Ｒ１、Ｒ２、Ｒ４、Ｒ１０］（領域２）、［Ｒ３、Ｒ４、Ｒ８］（領域３）となる。各領域には、まだ閾値である２よりも多いルールが管理されているため、それぞれの領域について、閾値以下のルール数になるまでさらに領域分割を行っていき、この例では、最終的に１５の領域に分割されている。なお、図３はあくまで一例であり、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅを構築するアルゴリズムについては、非特許文献１に記載されているため、ここでは省略する。【００１１】
一方、パケット分類を行う場合には、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅを辿っていき、辿り着いたノードで管理されている閾値数以下のルールを全て検索する。例えば、Ｘ＝０１１１、Ｙ＝１００１をもつパケットに対してパケット分類を行う場合、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの根ノードからノードを辿っていくことになる。図３に示すＤｅｃｉｓｉｏｎ  Ｔｒｅｅでは、根ノードにおいて上記の４つの領域に分割しており、当該パケットは、上記４つの領域のうち、領域１（［０：７］、［８：１５］）に属することが分かる。続いて、領域１のノードを見ると、さらにＸ方向に２分割、Ｙ方向に２分割し、領域１０（［０：３］、［８：１１］）と領域１１（［０：３］、［１２：１５］）と領域１２（［４：７］、［８：１１］）と領域１３（［４：７］、［１２：１５］）の４分割している。当該パケットはこのうち、領域１２に属していることが分かるため、さらに続くノードを辿る。次のノードでは、Ｙ方向に領域１２０（［４：７］、［８：９］）と領域１２１（［４：７］、［１０：１１］）とに２分割しており、当該パケットは、領域１２０に属することが分かるため、領域１２０で管理されているＲ３とＲ６に対して検索を行い、一致するルールに属すると判断される。なお、この場合、当該パケットはＲ３とＲ６の両方に一致するため、図１では省略している各ルールに付与された優先度に応じて、一致するルールが選択される。【００１２】
このように、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅを用いた手法は、複数の次元に着目して領域を分割し、分割された領域が管理する少数のルールに対して検索を行うことで、検索すべきルール数を削減する手法である。【００１３】
なお、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅを用いた手法では、領域分割の際、ルールによっては複数の分割領域で管理されることがあり、以下では、これをルールの複製と呼ぶ。例えば、図３では、Ｒ３やＲ４等のルールが複数の領域で管理されていることが分かる。このようなルールの複製が多ければ多いほど、複製されたルールへのアドレス値の管理、又はルールそのものの管理が増加し、見た目上、実際のルールセットよりも多くのルールを扱うことになり、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅにおけるデータ量が増加してしまう。これを防ぐために、非特許文献１や非特許文献２では、葉ノードでないノードにもルールリストを持たせ、その子ノード（領域）の間でルールが複製されるような場合には、当該ノードのルールリストにおいて複製されるルールを管理することで、それ以降の子ノードでは当該ルールを管理せず、結果的に、複製されるルール数を削減するための手法が提案されている。【００１４】
また、非特許文献３では、Ｐａｒａｌｌｅｌ  Ｂｉｔ  Ｖｅｃｔｏｒ（以下、Ｐａｒｅｌｌｅｌ  ＢＶと呼ぶ）と呼ばれるＭｕｌｔｉ−Ｆｉｅｌｄ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ手法が提案されている。Ｐａｒｅｌｌｅｌ  ＢＶでは、ルールを構成するそれぞれのフィールドに着目し、各ルールによって分割される、着目したフィールドの区間毎に、ビット配列（これをＢｉｔ  Ｖｅｃｔｏｒ（ＢＶ）と呼ぶ）を用意し、これを用いてＰａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎを行う。このようなＰａｒｅｌｌｅｌ  ＢＶについて、図４を用いて簡単に説明する。【００１５】
図４は、図１に示したルールセットに対するＢＶの一例を示す図である。このＢＶは、ビット位置とルールセットに含まれるルールが１対１に対応付けられており、各ビットには、当該区間の値が対応付けられたルールに一致する場合に‘１’、一致しない場合に‘０’が割り当てられる。なお、図４では、各ＢＶの上位ビットから、Ｒ１１、Ｒ１０、・・・、Ｒ０に割り当てられている。このようなＢＶを、ルールを構成する全てのフィールドに対して準備する。【００１６】
パケット分類を行う場合には、各フィールドの値によって、それぞれのフィールド毎に上記のＢＶを選択し、それらのＢＶのビット毎のＡＮＤ（論理積）を取る。当該パケットは、その結果得られたＢＶに‘１’が立っているビット位置に対応するルールに一致していると判断する。例えば、Ｘ＝０１１１、Ｙ＝１００１をもつパケットに対してパケット分類を行う場合を考える。フィールドＸの値は０１１１、つまり１０進数表記で７であるので、ＢＶとして、“１０００１１００１０００”を選択する（図４からもＲ３、Ｒ６、Ｒ７、Ｒ１１に一致する可能性があることが分かる）。同様に、フィールドＹの値は、１００１、つまり、１０進数表記で９であるので、ＢＶとして、“０００００１１１１０００”を選択する（図４からもＲ３、Ｒ４、Ｒ５、Ｒ６に一致する可能性があることが分かる）。続いて、フィールドＸ、Ｙから得たＢＶのビット単位のＡＮＤをとると、“０００００１００１０００”となる。この結果、当該パケットはＲ３とＲ６の両方に一致することが分かる。最終的には、図１では省略している各ルールに付与された優先度に応じて、一致するルールが選択される。【００１７】
このように、Ｐａｒａｌｌｅｌ  ＢＶは、ルールを構成するフィールド毎に一致する可能性のあるルールを選択し、最後に全フィールドの結果を総合的に判定することにより、一致しているルールを限定するという手法である。【００１８】
上記のＨｙｐｅｒＣｕｔｓやＢＶを、ハードウェアアーキテクチャによって高速処理を行う手法も提案されている。【００１９】
例えば、非特許文献２に、ＨｙｐｅｒＣｕｔｓをはじめとする、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅを用いた手法を、パイプラインによって処理するハードウェアアーキテクチャが提案されている。なお、上述したように、非特許文献２では、葉ノードでないノードにもルールリストを持たせることで、複製されるルール数を削減するための手法を用いている。図５は、図１のルールセットに対して非特許文献２の手法を用いて構築したＤｅｃｉｓｉｏｎ  Ｔｒｅｅの一例を示した図である。Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの構築方法については、非特許文献２に記載されているため、詳細は省略するが、図３と図５を比較しても分かるように、葉ノードでないノードにもルールリストを持たせることで、複製されるルール数が削減できており、かつＤｅｃｉｓｉｏｎ  Ｔｒｅｅの高さも低く抑えることができている。【００２０】
非特許文献２のハードウェアアーキテクチャでは、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅを辿るためのＴｒｅｅ  Ｐｉｐｅｌｉｎｅと、各ノードにおけるルールリストに含まれるルールを全検索するためのＲｕｌｅ  Ｐｉｐｅｌｉｎｅと、の２つのパイプラインを並列に用いることで、パケット分類を行っている。Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅは１つだけ具備され、基本的にはＤｅｃｉｓｉｏｎ  Ｔｒｅｅの深さ（高さ）と等しいパイプラインステージがあり、各ステージを進む毎に１つ深いノードを辿っていくことになる。一方、各ノードに到達すると、そこからルールリストに含まれるルールうちの１つへのアドレス値が指定され、それをＲｕｌｅ  Ｐｉｐｅｌｉｎｅの各ステージで１つずつマッチングする処理が開始される。このため、Ｒｕｌｅ  Ｐｉｐｅｌｉｎｅのステージ数は、ルールリストに含まれるルール数、つまり閾値数と等しく、Ｒｕｌｅ  Ｐｉｐｅｌｉｎｅの数はＴｒｅｅ  Ｐｉｐｅｌｉｎｅのステージ数よりも１つだけ多い数となる。詳細なアーキテクチャについては、非特許文献２に記載されているため、ここでは省略する。【００２１】
しかしながら、非特許文献２の手法では、１つのルールを構成するヘッダフィールド長の総和が大きくなればなるほど、高速アクセスが可能なメモリ、例えばＳＲＡＭの必要容量が大きくなる上、１パケットを処理する際にＳＲＡＭから読み出すデータ量が大きくなるため、メモリの動的電力（Ｄｙｎａｍｉｃ  Ｐｏｗｅｒ）が増加し、結果的に消費電力全体も増加してしまうという課題がある。【００２２】
一方、非特許文献４では、Ｐａｒａｌｌｅｌ  ＢＶを拡張したアルゴリズムと、それをパイプラインによって処理するハードウェアアーキテクチャと、が開示されている。非特許文献３のＰａｒａｌｌｅｌ  ＢＶでは、ＢＶを管理するために必要なメモリ容量は、通常、ルール数Ｎに対してＯ（Ｎ２）で増加するが、非特許文献４で拡張した手法では、各フィールドを複数のサブフィールドに分割し、その少数ビットから構成されるサブフィールドの取り得る値全てに対してＢＶを用意する。例えば、あるフィールドを１ｂｉｔずつのサブフィールドに分割した場合、サブフィールドが取り得る値（０か１）のいずれかで１つのＢＶを用意する。このため、ビット単位のＡＮＤを取るＢＶの数が増加してしまうが、必要なメモリ容量を線形増加に抑えることが可能である。また、Ｐａｒｅｌｌｅｌ  ＢＶでは、ルールそのものを用いてマッチングを行う必要がないため、ルール自体は例えばより大容量で低速なＤＲＡＭ等に保持しておき、ＢＶのみを高速なＳＲＡＭに保持するという形態が可能である。【００２３】
しかしながら、Ｐａｒｅｌｌｅｌ  ＢＶでは、１つのＢＶ長はルール数Ｎに比例するため、ルール数が大きくなればなるほど、ＢＶをメモリから読み出すのに多くのクロックサイクルを消費する上、Ｎ  ｂｉｔｓのＢＶを、一般的にはルールを構成するフィールド数分読み出す必要があるため、Ｄｙｎａｍｉｃ  Ｐｏｗｅｒが増加し、結果的に消費電力が増加してしまうという課題がある。【００２４】
さらに、非特許文献２、非特許文献４で提案されたハードウェアアーキテクチャでは、ルールとして用いるパケットヘッダ情報として、上述した５−ｔｕｐｌｅを想定しており、ルールとして用いるパケットヘッダ情報を変更する場合には、再度ハードウェア回路を変更する必要がある。【００２５】
また、非特許文献５では、ＨｙｐｅｒＣｕｔｓとＰａｒｅｌｌｅｌ  ＢＶを組み合わせることで、両者の欠点を互いに補うことを目指した手法が開示されている。本手法では、メモリから読み出すＢＶが高速処理にとって現実的なビット長になるようなルール数のみをＢＶで処理し、残りはＨｙｐｅｒＣｕｔｓで処理を行う。特に、ＨｙｐｅｒＣｕｔｓで処理を行うと、より多くのコピーが必要となるようなルールをＰａｒｅｌｌｅｌ  ＢＶで処理することで、ＨｙｐｅｒＣｕｔｓで必要となるメモリ容量を削減することが可能である。【００２６】
しかしながら、この手法は、ＨｙｐｅｒＣｕｔｓとＰａｒｅｌｌｅｌ  ＢＶを単純に組み合わせただけであり、上述したそれぞれの課題を根本的に解決しているわけではない。
【先行技術文献】
【非特許文献】
【００２７】
【非特許文献１】Ｓｕｍｅｅｔ  Ｓｉｎｇｈ、Ｆｌｏｒｉｎ  Ｂａｂｏｅｓｃｕ、Ｇｅｏｒｇｅ  Ｖａｒｇｈｅｓｅ、Ｊｉａ  Ｗａｎｇ、“Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  Ｕｓｉｎｇ  Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ  Ｃｕｔｔｉｎｇ”、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ＳＩＧＣＯＭＭ  ２００３  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｐｐｌｉｃａｔｉｏｎｓ、Ｔｅｃｈｎｏｌｏｇｉｅｓ、Ａｒｃｈｉｔｅｃｔｕｒｅｓ、ａｎｄ  Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、２００３年、第２１３−２２４頁
【非特許文献２】Ｗｅｉｒｏｎｇ  Ｊｉａｎｇ、  Ｖｉｋｔｏｒ  Ｋ．  Ｐｒａｓａｎｎａ、“Ｌａｒｇｅ−Ｓｃａｌｅ  Ｗｉｒｅ−Ｓｐｅｅｄ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  ｏｎ  ＦＰＧＡｓ”、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ／ＳＩＧＤＡ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｆｉｅｌｄ  Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙｓ、２００９年、第２１９−２２８頁
【非特許文献３】Ｔ．  Ｖ．  Ｌａｋｓｈｍａｎ、Ｄ．  Ｓｔｉｌｉａｄｉｓ、“Ｈｉｇｈ−Ｓｐｅｅｄ  Ｐｏｌｉｃｙ−ｂａｓｅｄ  Ｐａｃｋｅｔ  Ｆｏｒｗａｒｄｉｎｇ  Ｕｓｉｎｇ  Ｅｆｆｉｃｉｅｎｔ  Ｍｕｌｔｉ−ｄｉｍｅｎｓｉｏｎａｌ  Ｒａｎｇｅ  Ｍａｔｃｈｉｎｇ”、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ＳＩＧＣＯＭＭ  ’９８  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｐｐｌｉｃａｔｉｏｎｓ、Ｔｅｃｈｎｏｌｏｇｉｅｓ、Ａｒｃｈｉｔｅｃｔｕｒｅｓ、ａｎｄ  Ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、１９９８年、第２０３−２１４頁
【非特許文献４】Ｗｅｉｒｏｎｇ  Ｊｉａｎｇ、  Ｖｉｋｔｏｒ  Ｋ．  Ｐｒａｓａｎｎａ、“Ｆｉｅｌｄ−Ｓｐｌｉｔ  Ｐａｒａｌｌｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｍｕｌｔｉ−Ｍａｔｃｈ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ  Ｕｓｉｎｇ  ＦＰＧＡｓ”、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２１ｓｔ  Ａｎｎｕａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｐａｒａｌｌｅｌｉｓｍ  ｉｎ  Ａｌｇｏｒｉｔｈｍｓ  ａｎｄ  Ａｒｃｈｉｔｅｃｔｕｒｅｓ、２００９年、第１８８−１９６頁
【非特許文献５】Ｗｅｉｒｏｎｇ  Ｊｉａｎｇ、  Ｖｉｋｔｏｒ  Ｋ．  Ｐｒａｓａｎｎａ、“Ｓｃａｌａｂｌｅ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ：  Ｃｕｔｔｉｎｇ  ｏｒ  Ｍｅｒｇｉｎｇ？”、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １８ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ａｎｄ  Ｎｅｔｗｏｒｋｓ、２００９年
【発明の概要】
【発明が解決しようとする課題】
【００２８】
上記のようなＳＲＡＭ等のメモリを用いたハードウェアによるＭｕｌｔｉ−Ｆｉｅｌｄ  Ｐａｃｋｅｔ  Ｃｌａｓｓｉｆｉｃａｔｉｏｎ手法には、次のような問題点がある。【００２９】
まず、第１の問題点は、１つのルールを構成するヘッダフィールド長の総和が大きくなればなるほど、また、ルール数が多ければ多いほど、メモリのＤｙｎａｍｉｃ  Ｐｏｗｅｒが増加し、結果的にハードウェア全体の消費電力も増大してしまう点である。【００３０】
その理由は、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅを用いたアルゴリズムでは、ルールリストに含まれるルールの全件検索を行う際に、ルールそのものをメモリから読み出して比較を行う必要があるためである。【００３１】
次に、第２の問題点は、ルール数が多ければ多いほど、メモリからデータを読み出すのに必要なクロックサイクル数が増大してしまう点である。【００３２】
その理由は、Ｐａｒａｌｌｅｌ  ＢＶは、１つのルールがＢＶの１ｂｉｔに対応付けられているためであり、ＢＶは全てのルールに対応させるためのｂｉｔ数が必要であるためである。【００３３】
最後に、第３の問題点は、ルールとして用いるパケットヘッダ情報を自由に変更できないという点である。【００３４】
その理由は、ルールとして用いるパケットヘッダ情報として、例えば、５−ｔｕｐｌｅを想定してハードウェア回路が組まれているため、これを変更する際には、ハードウェア回路の変更が必要であるためである。なお、ここで言うパケットヘッダ情報の変更とは、ルール毎に用いるパケットヘッダ情報を変更するという意味ではなく、各ルールで用いることができるパケットヘッダ情報は予め決められているが、その予め決められたパケットヘッダ情報を、ハードウェア回路を変更することなく、自由に変更できるという意味である。【００３５】
本発明の目的は、上述した課題のいずれかを解決するパケット分類器、パケット分類方法、パケット分類プログラムを提供することにある。
【課題を解決するための手段】
【００３６】
本発明のパケット分類器は、
複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを、複数種類の予め決められた少数の長さのビット配列を用いて検索するパケット分類器であって、
決定木（Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ）を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込み、
検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定し、
特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する、
ことを特徴とする。【００３７】
本発明のパケット分類方法は、
複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを検索するパケット分類器によるパケット分類方法であって、
決定木を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込み、
検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定し、
特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する、
ことを特徴とする。【００３８】
本発明のパケット分類プログラムは、
複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを検索するコンピュータに、
決定木を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込む処理と、
検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定する処理と、
特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する処理と、
を実行させることを特徴とする。
【発明の効果】
【００３９】
本発明によれば、決定木（Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ）とビット配列とを組み合わせることにより、１パケットあたりの処理においてメモリから読み出すデータ量を削減することができ、１つのルールを構成するヘッダフィールド長の総和が大きくなっても、また、ルール数が多くなっても、メモリの動的電力の増加を抑制し、結果的にハードウェア全体の消費電力を増加させないことができるという効果が得られる。【００４０】
また、決定木とビット配列とを組み合わせることにより、ルール数が多くても、決定木によって適合する可能性のあるルール数を絞り込むことができるため、ビット配列のビット長を削減することができ、メモリからデータを読み出すのに必要なクロックサイクル数の増加を抑制できるという効果が得られる。
【図面の簡単な説明】
【００４１】
【図１】ルールセットの例を示す図である。
【図２】図１のルールセットを２次元空間上で表した図である。
【図３】図１のルールセットに対するＤｅｃｉｓｉｏｎ  Ｔｒｅｅの一例を示す図である。
【図４】図１のルールセットに対するＢｉｔ  Ｖｅｃｔｏｒの一例を示す図である。
【図５】図１のルールセットに対して非特許文献２の手法を用いて構築したＤｅｃｉｓｉｏｎ  Ｔｒｅｅの一例を示す図である。
【図６】本発明における基本的なパケット分類方法で用いるＤｅｃｉｓｉｏｎ  Ｔｒｅｅの一例を示す図である。
【図７】本発明における基本的なパケット分類方法で用いるＤｅｃｉｓｉｏｎ  Ｔｒｅｅの各ノードにおける領域分割情報の例を示す図である。
【図８】本発明における基本的なパケット分類方法で用いるＤｅｃｉｓｉｏｎ  Ｔｒｅｅの各ノードにおけるＢｉｔ  Ｖｅｃｔｏｒ情報の例を示す図である。
【図９】本発明における基本的なパケット分類方法の基本動作を示す流れ図である。
【図１０】本発明における基本的なパケット分類方法で用いるルールセットの例を示す図である。
【図１１】図１０に示すルールセットを２次元空間上で表した図である。
【図１２】図１０に示すルールセットに対して、本発明における基本的なパケット分類方法で構築したＤｅｃｉｓｉｏｎ  Ｔｒｅｅの一例を示す図である。
【図１３ａ】図１２のノード０のルールリストを２次元空間上に示し、かつ、フィールドＸ、Ｙの有効ビットに対するＢｉｔ  Ｖｅｃｔｏｒを示した図である。
【図１３ｂ】図１２のノード４のルールリストを２次元空間上に示し、かつ、フィールドＸ、Ｙの有効ビットに対するＢｉｔ  Ｖｅｃｔｏｒを示した図である。
【図１３ｃ】図１２のノード８のルールリストを２次元空間上に示し、かつ、フィールドＸ、Ｙの有効ビットに対するＢｉｔ  Ｖｅｃｔｏｒを示した図である。
【図１３ｄ】図１２のノード８のルールリストを２次元空間上に示し、かつ、フィールドＸ、Ｙの有効ビットに対するＢｉｔ  Ｖｅｃｔｏｒを示した図である。
【図１４】本発明の第１の実施の形態を示すブロック図である。
【図１５】本発明の第１の実施の形態におけるＤｅｃｉｓｉｏｎ  Ｔｒｅｅにおける各ノードのＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅへのマッピング例を示す図である。
【図１６】本発明の第１の実施の形態におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成を示すブロック図である。
【図１７】本発明の第１の実施の形態における領域分割回路の構成を示すブロック図である。
【図１８】本発明の第１の実施の形態におけるフィールド分割回路の構成を示すブロック図である。
【図１９】本発明の第１の実施の形態におけるＶｉｒｔｕａｌ  Ｎｏｄｅの例を示す図である。
【図２０】本発明の第１の実施の形態におけるＶｉｒｔｕａｌ  Ｎｏｄｅの領域分割情報の配置例を示す図である。
【図２１】本発明の第１の実施の形態におけるＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成を示すブロック図である。
【図２２】本発明の第１の実施の形態におけるＢｉｔ  Ｖｅｃｔｏｒ選択回路の構成を示すブロック図である。
【図２３】本発明の第１の実施のＰａｒａｌｌｅｌ  Ｂｉｔ  Ｖｅｃｔｏｒ処理時の動作（ステップＡ２）を示す流れ図である。
【図２４】本発明の第１の実施の領域分割時の動作（ステップＡ６）を示す流れ図である。
【図２５】本発明の第１の実施のＰａｒａｌｌｅｌ  Ｂｉｔ  Ｖｅｃｔｏｒ処理時の動作（ステップＡ２）を示す流れ図である。
【図２６】本発明の第１の実施の形態における複数のＤｅｃｉｓｉｏｎ  ＴｒｅｅノードのＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅへのマッピング例を示す図である。
【図２７】本発明の第２の実施の形態におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成を示すブロック図である。
【図２８】本発明の第２の実施の形態におけるＤｅｃｉｓｉｏｎ  Ｔｒｅｅの各ノードにおける領域分割情報の例を示す図である。
【図２９】本発明の第２の実施の形態における領域分割回路の構成を示すブロック図である。
【図３０】本発明の第２の実施の領域分割時の動作（ステップＡ６）を示す流れ図である。
【図３１】本発明の第３の実施の形態を示すブロック図である。
【図３２】本発明の第３の実施の形態におけるＤｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路の構成を示すブロック図である。
【図３３】本発明の第３の実施の形態におけるＢｉｔ  Ｖｅｃｔｏｒ処理回路の構成を示すブロック図である。
【図３４】本発明の第３の実施の形態におけるルールＩＤリストの構成例を示す図である。
【図３５】本発明の第３の実施の形態におけるパケット分類の動作を示す流れ図である。
【図３６】本発明の第３の実施の形態におけるＰａｒａｌｌｅｌ  Ｂｉｔ  Ｖｅｃｔｏｒ処理時の動作（ステップＡ２）を示す流れ図である。
【図３７】本発明の第４の実施の形態を示すブロック図である。
【発明を実施するための形態】
【００４２】
［発明の概要］
本発明のパケット分類器およびパケット分類方法について説明する前に、まず、本発明における基本的なパケット分類方法の概要について説明する。
【００４３】
図６は、本発明における基本的なパケット分類方法で用いるＤｅｃｉｓｉｏｎ  Ｔｒｅｅの一例を示す図である。図６においては、ノード０はＤｅｃｉｓｉｏｎ  Ｔｒｅｅの根ノードであり、葉ノードでない各ノードにおいてそれぞれ２つ又は４つに領域分割を行っている例を示している。また、各葉ノードには、各分割領域において管理される閾値Ｌ以下のルール群であるルールリスト（図６において実線で示しているルールリスト）が管理されている。さらに、葉ノードでないノードにおいても、非特許文献１や非特許文献２で提案されているようなルールの複製を削減するためのルールリスト（図６において点線で示しているルールリスト）を保持している。なお、このようなＤｅｃｉｓｉｏｎ  Ｔｒｅｅの構築方法については、非特許文献１や非特許文献２で提案されている手法を用いるものとし、ここでは詳細な説明を省略する。
【００４４】
図７は、本発明における基本的なパケット分類方法で用いるＤｅｃｉｓｉｏｎ  Ｔｒｅｅの各ノードにおける領域分割情報を示す図である。本発明におけるパケット分類方法の領域分割情報としては、当該ノードがＤｅｃｉｓｉｏｎ  Ｔｒｅｅにおける葉ノードであるか否かを示す“Ｌｅａｆ  Ｆｌａｇ”と、本パケット分類方法でＤｅｃｉｓｉｏｎ  Ｔｒｅｅの各ノードにおいて領域を分割するために用いるＣ個のフィールドに対する分割数（Ｎｕｍ．  ｏｆ  Ｃｕｔｔｉｎｇ）と、当該ノードの子ノードに対する領域分割情報が格納されているＢａｓｅ  Ａｄｄｒｅｓｓ（ベースアドレス）と、当該ノードが実ノードではなく仮想ノードであることを示す“Ｖｉｒｔｕａｌ  Ｆｌａｇ”と、を含む。ここで、分割数については、非特許文献２と同様の指定方法とし、分割数としてｋを指定した場合、当該フィールドに対する分割数は２ｋであるとする。その他の情報に関する具体的な利用方法については後述する。なお、この領域分割情報はメモリに格納されており、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅを辿る際に、各ノードに到着すると、該当する領域分割情報をメモリから読み出す。
【００４５】
図８は、本発明における基本的なパケット分類方法で用いるＤｅｃｉｓｉｏｎ  Ｔｒｅｅの各ノードにおけるＢｉｔ  Ｖｅｃｔｏｒ（ＢＶ）情報を示す図である。まず、本方法では、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの各ノードにおいて、ＢＶの他にルールＩＤリストを１つ管理する。このルールＩＤリストは、当該ノードにおけるルールリストに相当するものであり、当該ノードの分割領域において管理する最大Ｌ個のルールのルールＩＤと、その優先度を示すものである（図８には、優先度を示していないが、優先度はルールＩＤと共に管理されているものとする）。一方、ＢＶの長さはＬ  ｂｉｔｓであり、図８に示すように、そのビット位置とルールＩＤリストが１対１で対応する。つまり、ＢＶのビット位置を上位からＢＶ［Ｌ−１］、ＢＶ［Ｌ−２］、ＢＶ［Ｌ−３］、・・・、ＢＶ［０］として表すと、ビット位置ＢＶ［ｉ］（ｉ＝Ｌ−１、Ｌ−２、・・・、０）は、ルールＩＤリストのＲｕｌｅ  ＩＤ  ＃ｉに記載されているＩＤを持つルールと対応する。なお、ＢＶの各ビットが表す意味は既存のＰａｒａｌｌｅｌ  ＢＶと同じであるため、説明を省略する。なお、図８では、ＢＶを１つだけ記載しているが、実際には、非特許文献３に記載のように、ルールを構成する各フィールドにおいてその区間毎に用意する、又は、非特許文献４に記載のように、各フィールドをサブフィールドに分割し、そのサブフィールドが取り得る値全てに対して用意することが考えられるが、詳細については後述する実施の形態において説明する。但し、本方法では、検索キーの各フィールドにおいて有効ビット長が管理されており、ＢＶは、有効ビット長で示されたビット長に対してのみ管理される。また、これらのルールＩＤリストとＢＶはメモリにて保持されているものとする。
【００４６】
図９は、本発明における基本的なパケット分類方法の基本動作を示す流れ図である。
【００４７】
本発明における基本的なパケット分類方法では、検索キーとなるパケットのヘッダ情報が入力されると、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの根ノードから処理を開始する（ステップＡ１）。処理ノードにおいて、管理されているルールＩＤリストと検索キーを基に、所定のＰａｒａｌｌｅｌ  ＢＶ処理を実行する（ステップＡ２）。なお、ここでのＰａｒａｌｌｅｌ  ＢＶ処理は、非特許文献３や非特許文献４等に記載の手法をベースとする。次に、当該処理ノードと当該処理ノード以前の各処理ノードからの最適ルールと、を含めたルールの中で、最適ルールを選択する（ステップＡ３）。続いて、当該処理ノードにおける領域分割情報をメモリから読み出す（ステップＡ４）。ここで詳細については後述するが、当該ノードの領域分割情報に対するメモリアドレスは、その親ノードにおける処理時に確定し、子ノードである当該処理ノードに通知され、当該処理ノードはそのアドレス値に格納されている領域分割情報を読み出す。読み出した領域分割情報のＬｅａｆ  Ｆｌａｇから当該ノードがＤｅｃｉｓｉｏｎ  Ｔｒｅｅの葉ノードであるかを確認し（ステップＡ５）、当該ノードが葉ノードでなければ（ステップＡ５のＮｏ）、当該処理ノードの領域分割情報で指定されたフィールドに対する分割数から、次の子ノードの領域分割情報が格納されているメモリアドレス値を決定し（これを、次の子ノードを選択すると言う）、その子ノードを処理ノードとする（ステップＡ６）。なお、次の子ノードの選択方法の詳細については後述するが、領域分割情報で指定された分割フィールドに対し、検索キーの当該フィールドの値のうち、有効ビット長の先頭ｋビットをチェックし、それらを結合した上で、領域分割情報のＢａｓｅ  Ａｄｄｒｅｓｓに加算することで、次の子ノードに対する領域分割情報が格納されているメモリアドレス値を確定することができ、分割領域のうちのどの領域（どの子ノード）であるかを判断できる。ここで、変数ｋは、領域分割情報の分割数で指定されている値である。次に、各フィールドの有効ビット長から、領域分割情報で指定されたｋを減じることで、有効ビット長の更新を行い（ステップＡ７）、ステップＡ２へ戻って処理を繰り返す。なお、有効ビット長は、内部変数として管理されるものであり、当該フィールドのフィールド長で初期化され、根ノードからＤｅｃｉｓｉｏｎ  Ｔｒｅｅを辿ったノードからノードへと受け渡すものとする。一方、当該処理ノードがＤｅｃｉｓｉｏｎ  Ｔｒｅｅの葉ノードであった場合（ステップＡ５のＹｅｓ）、処理を終了し、それまでに選択されている最適ルールを最終解とする。
【００４８】
続いて、図１０に示すフィールドＸ、Ｙから構成されるルールセットにおいて、Ｘ＝１００１、Ｙ＝１１１１をもつパケットに対して、本発明における基本的なパケット分類方法を用いてパケット分類を行う場合について説明する。なお、以下の例では、図９のステップＡ２におけるＰａｒａｌｌｅｌ  ＢＶ処理は、非特許文献２に記載の手法をベースにするものとする。図１０は、図１のルールセットと同様、それぞれ４ｂｉｔｓから構成される２つのフィールドＸ、Ｙを用いて定義されたＲ０からＲ１９までの２０個のルールからなるルールセットの例を示す図である。なお、フィールドＸ、Ｙは、それぞれ４ｂｉｔｓとしているが、例えば送信元ＩＰアドレスや送信元ポート番号等、実際のパケットヘッダフィールドに相当するものであり、フィールドＸ、Ｙの表記方法や優先度、Ａｃｔｉｏｎの取り扱いについては図１と同様であるため、ここではその説明を省略する。また、図１１は、図１０に示すルールセットを、フィールドＸ、Ｙの２次元から成る空間上に示した図であり、図１２は、図１０に示すルールセットを、本発明における基本的なパケット分類方法で構築したＤｅｃｉｓｉｏｎ  Ｔｒｅｅの一例である。但し、図１２のＤｅｃｉｓｉｏｎ  Ｔｒｅｅにおける閾値Ｌ（ルールＩＤリストに含むことが可能なルール数）は２としている。
【００４９】
本発明における基本的なパケット分類方法では、まず、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの根ノードであるノード０を処理ノードとし、処理を開始する（ステップＡ１）。ノード０のルールリストにはＲ７とＲ８が含まれるため、ルールＩＤリストは（Ｒ７、Ｒ８）であり、フィールドＸ、Ｙに対するＢＶは、それぞれ“１０”、“０１”となる。ここで、図１３ａは、ノード０のルールリストを２次元空間上に示し、かつ、フィールドＸ、Ｙに対するＢＶを示した図である。図１３ａより、ノード０におけるフィールドＸ、Ｙに対するＢＶはそれぞれ“１０”、“０１”になることが分かる。続いて、取得した上記のＢＶのビット単位のＡＮＤを取り、処理ノード０における最終ＢＶ“００”を得る（以上、ステップＡ２）。この結果から、本処理ノードまでの最適解は無く、適合ルールは存在しないと判断できる（ステップＡ３）。次に、ノード０における領域分割情報を読み出す（ステップＡ４）。本例では、詳細な領域分割情報を図示しないが、図１２の各ノード内に領域分割に用いるフィールドＸ、Ｙに対する分割数を図示している。また、ノード５からノード７、及びノード９からノード１４のＬｅａｆ  Ｆｌａｇは１、つまり葉ノードであるとし、それ以外のＬｅａｆ  Ｆｌａｇは全て０、つまり葉ノードでないとする。さらに、Ｖｉｒｔｕａｌ  Ｆｌａｇは全て０、つまり、全ノード共に実ノードであるものとする。ノード０の領域分割情報から、ノード０はＤｅｃｉｓｉｏｎ  Ｔｒｅｅの葉ノードではないと判断できるため（ステップＡ５のＮｏ）、領域分割を行い、次の子ノードを選択し、処理ノードとする（ステップＡ６）。この場合、フィールドＸ、Ｙに対する分割数ｋとしてそれぞれ１が指定されており、各フィールドの有効ビット長はそれぞれ４であるため、検索キーのフィールドＸ、Ｙの有効ビットに対する先頭ビットを連結した“１１”にＢａｓｅ  Ａｄｄｒｅｓｓを加算することで、次の処理ノードであるノード４の領域分割情報が格納されているメモリアドレス値を決定する。最後に、有効ビット長をそれぞれ分割数である１ずつ減じることで、有効ビット長の更新を行う（ステップＡ７）。
【００５０】
続いて、次の処理ノードであるノード４のルールリストには、Ｒ１３が含まれるため、ルールＩＤリストは（Ｒ１３、ＮＵＬＬ）であり、フィールドＸ、Ｙの有効ビットである“１１１”と“００１”に対するＢＶは、それぞれ“１０”、“００”となる。ここで、図１３ｂは、ノード４のルールリストを２次元空間上に示し、かつ、フィールドＸ、Ｙに対するＢＶを示した図である。なお、ノード４ではフィールドＸ、Ｙに対する有効ビット長がそれぞれ３であるため、有効ビットである下位３ｂｉｔに対するＢＶが用意されており、有効ビットでない領域部分は塗りつぶしている。図１３ｂより、ノード４におけるフィールドＸ、Ｙに対するＢＶはそれぞれ“１０”、“００”になることが分かる。取得した上記のＢＶのビット単位のＡＮＤを取り、処理ノード４における最終ＢＶ“００”を得る（ステップＡ２）。この結果、ノード４までの処理において適合しているルールは存在しないことが分かる（ステップＡ３）。次に、ノード４の領域分割情報を読み出す（ステップＡ４）。ノード４はＤｅｃｉｓｉｏｎ  Ｔｒｅｅの葉ノードではないため（ステップＡ５のＮｏ）、領域分割を行い、次の処理ノードを選択する（ステップＡ６）。この場合、フィールドＸ、Ｙに対する分割数としてそれぞれ１が指定されており、各フィールドの有効ビット長はそれぞれ３であるため、検索キーのフィールドＸ、Ｙの有効ビットである“００１”、“１１１”に対する先頭ビットを連結した“０１”にＢａｓｅ  Ａｄｄｒｅｓｓを加算することで、次の処理ノードであるノード８の領域分割情報が格納されているメモリアドレス値を決定する。最後に、有効ビット長をそれぞれ１ずつ減じる（ステップＡ７）。
【００５１】
同様に、ノード８のルールリストには、Ｒ１７とＲ１８が含まれるため、ルールＩＤリストは（Ｒ１７、Ｒ１８）であり、フィールドＸ、Ｙの有効ビットである“０１”と“１１”に対するＢＶは、それぞれ“１１”、“１１”となる。ここで、図１３ｃは、ノード８のルールリストを２次元空間上に示し、かつ、フィールドＸ、Ｙに対するＢＶを示した図である。なお、ノード８ではフィールドＸ、Ｙに対する有効ビット長がそれぞれ２であるため、有効ビットである下位２ｂｉｔに対するＢＶが用意されており、有効ビットでない領域部分は塗りつぶしている。取得した上記のＢＶのビット単位のＡＮＤを取り、処理ノード８における最終ＢＶ“１１”を得る（ステップＡ２）。この場合、ノード８において適合するルールはＲ１７とＲ１８であり、それ以前の処理ノード（ノード０とノード４）においては適合ルールが存在しないことから、Ｒ１７とＲ１８の優先度を確認し、高優先度のルールを最適解とする（図１０のルールセットには省略しているが、ルールセットに含まれる各ルールには個別の優先度が設定されているものとする）。次に、ノード８の領域分割情報を読み出し（ステップＡ４）、ノード８はＤｅｃｉｓｉｏｎ  Ｔｒｅｅの葉ノードではないことが分かるため（ステップＡ５のＮｏ）、領域分割を行い、次の処理ノードを選択する（ステップＡ６）。この場合、フィールドＸ、Ｙに対する分割数としてそれぞれ１が指定されており、各フィールドの有効ビット長はそれぞれ２であるため、検索キーのフィールドＸ、Ｙの有効ビットである“０１”、“１１”に対する先頭ビットを連結した“０１”にＢａｓｅ  Ａｄｄｒｅｓｓを加算することで、次の処理ノードであるノード１２の領域分割情報に対するメモリアドレス値を決定する。最後に、有効ビット長をそれぞれ１ずつ減じる（ステップＡ７）。
【００５２】
さらに同様に、ノード１２のルールリストには、Ｒ３が含まれるため、ルールＩＤリストは（Ｒ３、ＮＵＬＬ）であり、フィールドＸ、Ｙの有効ビットである“１”と“１”に対するＢＶは、それぞれ“００”、“００”となる。ここで、図１３ｄは、ノード１２のルールリストを２次元空間上に示し、かつ、フィールドＸ、Ｙに対するＢＶを示した図である。なお、ノード１２ではフィールドＸ、Ｙに対する有効ビット長がそれぞれ１であるため、有効ビットである下位１ｂｉｔに対するＢＶが用意されており、有効ビットでない領域部分は塗りつぶしている。取得した上記のＢＶのビット単位のＡＮＤを取り、処理ノード１２における最終ＢＶ“００”を得る（ステップＡ２）。この結果、ノード１２における適合ルールは存在せず、これまでの処理ノードにおける最適ルールであるＲ１７、もしくはＲ１８が最適ルールであると判断できる（ステップＡ３）。次に、ノード１２の領域分割情報を読み出し（ステップＡ４）、ノード１２はＤｅｃｉｓｉｏｎ  Ｔｒｅｅの葉ノードであることが分かるため（ステップＡ５のＹｅｓ）、処理を終了し、現在の最適ルールであるＲ１７、もしくはＲ１８を最終的な解とする。
【００５３】
なお、上記の図１０のルールセットの例では、ルールはフィールドＸとＹの２つのフィールドを用いてしか定義されていなかったが、本発明における基本的なパケット分類方法では、より多くのフィールドを用いてルールを定義することが可能である。この場合、上述したように、図７のようなデータ構造を用いて、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの各ノードにおいて領域分割するフィールド、及びその分割数を指定する。
［発明の実施の形態］
上記の本発明における基本的なパケット分類方法を踏まえ、下記に本発明の実施の形態とその動作について説明する。
【００５４】
（１）第１の実施の形態
（１−１）第１の実施の形態の構成
まず、本発明の第１の実施の形態について図面を参照して説明する。
【００５５】
図１４は、本発明の第１の実施の形態のパケット分類器を示すブロック図である。図１４を参照すると、本発明の第１の実施の形態のパケット分類器１は、ハードウェア回路として実現されるものであり、入力２として検索キーを入力し、出力３として最適ルールのルールＩＤを出力する。
【００５６】
パケット分類器１は、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ（ツリーパイプライン処理回路）１０と、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ（プライオリティパイプライン処理回路）２０と、を備えている。
【００５７】
Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ１０は、パイプライン構造となっており、本発明のパケット分類を行うにあたり、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅを辿る処理を実行する。Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ１０は、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ（ツリーパイプライン処理部）１０−１、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−２、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−３、・・・、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−ＨのＨ段のパイプラインステージから構成されている。ここで、Ｈは、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅの高さ（深さ）に相当するものであり、本実施の形態では、高さがＨ以下であるＤｉｃｉｓｉｏｎ  Ｔｒｅｅを構成し、用いるものとする。
【００５８】
図１５は、本発明の第１の実施の形態におけるＤｅｃｉｓｉｏｎ  Ｔｒｅｅにおける各ノードのＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅへのマッピング例を示す図である。例えば、ノード０からノード１４の１５個のノードから構成される高さ４のＤｅｃｉｓｉｏｎ  Ｔｒｅｅにおいては、非特許文献２におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅと同様、基本的には同一の深さ（これをレベルと呼ぶ）のノードは、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅにおける同一のステージに配置される。但し、あるレベルのノードは、そのレベル以降のステージに配置されても良く、例えばノード１０は、深さ３であるが、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ＃３ではなく、それ以降のレベルであるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ＃４に配置している。なお、ノードの配置とは、図７に示すような当該ノードの領域分割情報の配置を意味し、各Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに具備されるメモリ等の記憶媒体上に領域分割情報を保持されることを意味する。このような配置方法は、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおける領域分割情報を記憶するメモリのワード数と、後述するＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ（プライオリティパイプライン処理部）において実現できるルールリスト数、つまり、ＢＶを記憶するメモリのワード数と、が一対一に対応しなくても良いという柔軟性を持たせるためであり、詳細については非特許文献２に記載されているため、ここでは説明を省略する。
【００５９】
図１６は、本発明の第１の実施の形態におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成を示すブロック図である。図１６を参照すると、本発明におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１から１０−Ｈの各々は、当該ステージにて処理を行うノードにおける領域分割処理を行い、さらにその結果として、次ノードの領域分割情報が含まれる次ステージのアドレス値を決定する領域分割回路１００と、前ステージから指定されたアドレス値にある当該処理ノードの領域分割情報を読み出すためのＭｅｍｏｒｙ  Ｃｏｎｔｒｏｌｌｅｒ（メモリコントローラ）１０１と、当該ステージに配置されたＤｅｃｉｓｉｏｎ  Ｔｒｅｅのノードの領域分割情報を記憶している、メモリ等の記憶媒体で構成される領域分割情報記憶ブロック１０２と、検索キーの有効ビット長を更新する有効ビット更新長回路１０３と、当該ステージに入力された検索キーに、ある一定の遅延を持たせ、他の出力と同期させるための検索キー遅延回路１０４と、を備える。
【００６０】
各Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅには、前段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅから、被検索対象である検索キーと、その有効ビット長と、当該Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅでの処理対象となるノードの領域分割情報が保持される領域分割情報記憶ブロック１０２のアドレス値が入力される。入力された検索キーは、領域分割回路１００と検索キー遅延回路１０４とに入力される。なお、ここで検索キーは、本パケット分類器が対象とするルールに含まれるパケットヘッダフィールド情報が全て含まれたビット列として構成され、各フィールドが構成されるビット長等の情報は予め回路上に設定されており、本パケット分類器では、一意に当該フィールドを参照したり、切り出したりすることが可能であるものとする。また、入力された有効ビット長は、領域分割回路１００と有効ビット長更新回路１０３に入力される。なお、ここで有効ビット長は、検索キーに含まれるパケットヘッダフィールドのうち、予め設定され、領域分割情報に示される本パケット分類器で領域分割に利用するパケットヘッダフィールドを対象に、そのフィールド毎に、有効ビット長を表したビット列として構成される。最後に、アドレス値は、Ｍｅｍｏｒｙ  Ｃｏｎｔｒｏｌｌｅｒ１０１に入力される。なお、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１では、上述した検索キーは、パケット分類器１への入力２として与えられる。また、有効ビット長は各ヘッダフィールドの長さそのもの、つまり全て有効であるとして指定され、アドレス値は、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの根ノードの領域分割情報が格納されている領域分割情報記憶ブロック１０２のアドレス値が指定されるものとし、これらは入力２として指定されても良いし、パケット分類器１の内部で指定されても良い。
【００６１】
アドレス値が入力されたＭｅｍｏｒｙ  Ｃｏｎｔｒｏｌｌｅｒ１０１は、領域分割情報記憶ブロック１０２に対して指定されたアドレス値に記憶されている図７に示すような領域分割情報を読み出し、それを領域分割回路１００と有効ビット長更新ブロック１０３に出力する。
【００６２】
有効ビット長更新ブロック１０３は、入力された有効ビット長と、領域分割情報から、有効ビット長を更新する。具体的に、領域分割情報には、本パケット分類器で領域分割に利用するヘッダフィールド毎に分割数ｋが指定されているが、有効ビット長更新ブロック１０３は、入力された有効ビット長から、この分割数ｋを減算することで更新し、更新した有効ビット長を後段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅへと出力する。
【００６３】
検索キー遅延回路１０４は、入力された検索キーをレジスタ等を用いてある一定間隔遅延させ、有効ビット長更新回路１０３から出力される有効ビット長や、後述する領域分割回路１００から出力されるアドレス値と同タイミングで検索キーを出力する。
【００６４】
図１７は、本発明の第１の実施の形態における領域分割回路１００の構成を示すブロック図である。図１７を参照すると、領域分割回路１００は、入力された領域分割情報から、領域分割に用いるヘッダフィールド毎にその分割数を切り出す領域分割情報分離回路１０００と、マルチプレクサ１００１と、フィールド分割回路１００−１、１００−２、・・・、１００−Ｃと、ＯＲゲート１００２と、加算器１００３と、を含む。
【００６５】
領域分割回路１００に入力された領域分割情報は、領域分割情報分離回路１０００に入力される。領域分割情報は図７に示すような情報から構成されるが、領域分割情報分離回路１０００では、これらの各種情報をそれぞれ切り出し、各情報を利用する回路へ出力する。例えば、Ｖｉｒｔｕａｌ  Ｆｌａｇはマルチプレクサ１００１へ、Ｃ個のフィールドに対する分割数は、それぞれフィールド分割回路１００−１から１００−Ｃへ、Ｂａｓｅ  Ａｄｄｒｅｓｓは加算器１００３へと出力する。また、領域分割回路１００に入力された検索キーと有効ビット長は、各フィールドに応じて当該フィールドを処理するフィールド分割回路へと入力される。なお、ここでは、複数フィールドが束になっている検索キーや有効ビット長データそのものを各フィールド分割回路に入力し、回路内で担当するフィールドのデータを切り出しても良いし、入力された時点で各フィールドのデータを切り出し、各フィールド分割回路に入力させても良い。
【００６６】
ＯＲゲート１００２は、後述する各フィールド分割回路の出力結果の論理和（ＯＲ）を取り、加算器１００３に入力する。
【００６７】
加算器１００３は、領域分割情報に含まれるＢａｓｅ  ＡｄｄｒｅｓｓとＯＲゲート１００２の出力結果を加算し、それを後段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅで処理する子ノードの領域分割情報のアドレス値として出力する。
【００６８】
図１８は、本発明の第１の実施の形態におけるフィールド分割回路の構成を示すブロック図である。図１８を参照すると、フィールド分割回路は、減算器１００４と、Ｒｉｇｈｔ  Ｓｈｉｆｔｅｒ１００５と、加算器１００６と、Ｌｅｆｔ  Ｓｈｉｆｔｅｒ１００７と、を備える。
【００６９】
フィールド分割回路に入力された有効ビット長と領域分割情報の分割数は、減算器１００４へ入力され、有効ビット長から分割数を減算される。この結果は、Ｒｉｇｈｔ  Ｓｈｉｆｔｅｒ１００５へ出力され、Ｒｉｇｈｔ  Ｓｈｉｆｔｅｒ１００５は、入力された検索キーの当該フィールドを、減算器１００４の結果の値だけ右にシフトさせる。一方、下段のフィールド分割回路から入力された値と、分割数は加算器１００６にて加算され、その結果はＬｅｆｔ  Ｓｈｉｆｔｅｒ１００７、及び上段のフィールド分割回路へと出力される。なお、フィールド分割回路１００−１では、下段から加算器１００６へ入力される値は０である。また、ここでは、各フィールド分割回路の加算器１００６は、下段のフィールド分割回路からの加算結果に、入力された分割数を加算しているが、下段の結果を用いず、それまでに加算すべき分割数を全て加算器１００６で加算しても良い。Ｌｅｆｔ  Ｓｈｉｆｔｅｒ１００７では、Ｒｉｇｈｔ  Ｓｈｉｆｔｅｒ１００５の結果を加算器１００６の結果の値だけ左にシフトさせ、その結果をＯＲゲート１００２へ出力する。
【００７０】
上記の結果、ＯＲゲート１００２で各フィールド分割回路の結果の論理和をとることで、領域分割情報で指定された分割に用いるフィールドに対し、そのフィールドの有効ビットの先頭ｋビットを切り出し、領域分割に用いる各フィールドの分割数に応じて、次ノードの相対的なアドレス値を決定することが可能となる。そして、加算器１００３にてＢａｓｅ  Ａｄｄｒｅｓｓとこの相対的なアドレス値を加算することにより、後段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおける次ノードの領域分割情報が記憶されているアドレス値を指定することが可能となる。
【００７１】
ここで、領域分割情報のＶｉｒｔｕａｌ  Ｆｌａｇの利用について説明する。本パケット分類器では、上述したように、非特許文献２と同様、基本的には同一の深さのノードは、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅにおける同一のステージに配置されるが、あるレベルのノードはそのレベル以降のステージに配置されても良い。本パケット分類器では、このような場合、図１９に示すように仮想ノード（Ｖｉｒｔｕａｌ  Ｎｏｄｅ）を用いてこれを実現する。図１９は、本発明の第１の実施の形態におけるＶｉｒｔｕａｌ  Ｎｏｄｅの例を示す図である。図１９は、ノード４の子ノードであるノード１０は本来ノード４の次のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに配置されるが、ここではさらに１ステージ後段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに配置されている。この場合、ノード４において後段の子ノードであるノード７、８、９、１０のアドレス値が計算されるが、ノード４においては、ノード７の領域分割情報が記憶されたアドレスをＢａｓｅ  Ａｄｄｒｅｓｓとして計算する。一方、ノード１０が実際に配置されているＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおいては、例えばノード１１からノード１４のように、他のノードが配置されているため、ノード４においてＢａｓｅ  Ａｄｄｒｅｓｓから算出したアドレス値として、ノード１０のアドレス値を確定することは困難である。このため、このように本来配置されるべきステージと異なるステージに配置される場合には、Ｖｉｒｔｕａｌ  Ｎｏｄｅを配置する。図１９では、ノード１０のＶｉｒｔｕａｌ  ＮｏｄｅとしてノードＶ０が配置されている。ノードＶ０は実ノードではないため、ルールリストを具備していない。つまり、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  ＳｔａｇｅにてＢＶを記憶する必要がなく、この結果、非特許文献２のように、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおけるメモリワード数を増加させ、より柔軟にＤｅｃｉｓｉｏｎ  Ｔｒｅｅをマッピングさせることが可能となる。この場合、ノード４では、領域分割回路１００において上述したような処理を行うことで、その子ノードであるノード７、８、９、Ｖ０の領域分割情報が記憶されたアドレス値を確定することができる。ノード４の次ノードがノード１０であった場合、ノード４の後段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅでは、ノードＶ０が指定され、その領域分割情報を読み出し、同様の領域分割処理を行う。この際、ノードＶ０の領域分割情報では、Ｖｉｒｔｕａｌ  Ｆｌａｇが‘１’となっているため、マルチプレクサ１００１にて、各フィールド分割回路に入力される分割情報は０となる。この結果、ＯＲゲート１００２の出力は０となり、加算器１００３からの出力はＢａｓｅ  Ａｄｄｒｅｓｓと等しいアドレス値となる。Ｖｉｒｔｕａｌ  Ｎｏｄｅの領域分割情報のＢａｓｅ  Ａｄｄｒｅｓｓには、その子ノードであるノード１０のアドレス値が保持されているため、上述した処理を行うことで問題なくノード１０のアドレス値を指定することが可能となる。なお、あるノードの子ノードが複数のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅをあけて配置される場合も同様であり、途中のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  ＳｔａｇｅではＶｉｒｔｕａｌ  Ｎｏｄｅが配置されることになる。
【００７２】
さらに、Ｖｉｒｔｕａｌ  Ｎｏｄｅを用いて本来配置されるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ以降のステージに配置されるノードについて補足する。図２０は、本発明の第１の実施の形態におけるＶｉｒｔｕａｌ  Ｎｏｄｅの領域分割情報の配置例を示す図である。Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの領域分割情報記憶ブロック１０２のワード数をＷＴ、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  ＳｔａｇｅにおけるＢｉｔ  Ｖｅｃｔｏｒを記憶させることができるワード数をＷＰとする（ここでのワード数とは、ノード数を意味するものとする。つまり、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅには実ノード、仮想ノードを含めてＷＴノード分、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅには、ＷＰノード分のＢＶを記憶することができるものとする）。この場合、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  ＳｔａｇｅにおけるＷＴノードのうち、ＷＰノードが実ノードとなり、ルールＩＤリストを持つことができる。このため、本発明では、あるノードの複数の子ノード毎にアドレス値０から順に詰めて領域分割情報記憶ブロック１０２に記憶させ、ＷＰノードを越えたノードを本来配置されるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ以降のステージに配置する方針を取る。つまり、Ｖｉｒｔｕａｌ  Ｎｏｄｅを子ノードとしてもつノードは、その子ノード全てがＶｉｒｔｕａｌ  Ｎｏｄｅであるか、子ノードのうち、ノードＩＤが小さいいくつかのノードが実ノードであり、ノードＩＤが大きないくつかのノードは全てＶｉｒｔｕａｌ  Ｎｏｄｅであるものとする。
【００７３】
上記のようなＴｒｅｅ  Ｐｉｐｅｌｉｎｅの構成については、非特許文献２にも開示されているが、非特許文献２で開示されている構成では、有効ビットが考慮されていない上、Ｂａｓｅ  Ａｄｄｒｅｓｓに分割した結果のアドレス値を加算していないため、適切なアドレス設定が難しいと考えられる。また、あるノードの子ノードを複数ステージあけて配置した場合、非特許文献２では、Ｄｉｓｔａｎｃｅ  Ｖａｌｕｅと呼ばれるカウンタを用いてそれを把握していたが、本実施の構成では、１ｂｉｔのフラグを用いてこれを構成している点が異なる。
【００７４】
続いて、パケット分類器１に含まれるＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ２０は、パイプライン構造となっており、本発明のパケット分類を行うにあたってのＢＶの選択、及び最適解の選択に関わる処理を実行する。Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ２０は、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−０、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−１、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−２、・・・、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−（Ｈ−１）、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−Ｈの（Ｈ＋１）段のパイプラインステージから構成されている。
【００７５】
図２１は、本発明の第１の実施の形態におけるＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成を示す図である。図２１を参照すると、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅは、フィールド分離回路２００と、アドレス変換回路２０１と、Ｂｉｔ  Ｖｅｃｔｏｒ（ＢＶ）選択回路（ビット配列選択回路）２００−１、２００−２、・・・、２００−Ｆと、ＡＮＤゲート２０２と、優先度チェック回路２０３と、メモリ等の記憶媒体で構成されるルールＩＤリスト記憶ブロック２０４と、を含む。
【００７６】
フィールド分離回路２００は、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅから入力された検索キーと有効ビット長を、検索キーに含まれるＦ個のフィールド毎に分離し、それぞれをＦ個のＢＶ選択回路へ入力する。なお、有効ビット長は、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅにおける領域分割に用いられるフィールドに対してのみ設定されているため、有効ビット長が定義されていないフィールドに対しては、当該フィールドのフィールド長を有効ビット長としてＢＶ選択回路に入力させても良いし、ｄｏｎ’ｔ  ｃａｒｅとして入力せず、ＢＶ選択回路で全て有効であると判断させても良い。
【００７７】
アドレス変換回路２０１は、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅから入力された次ステージでの子ノードの領域分割情報が記憶されるアドレス値が入力される。アドレス変換回路２０１では、入力されたアドレス値が、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  ＳｔａｇｅにおいてルールＩＤリストを保持できるワード数（ノード数）ＷＰよりも大きいか小さいかを判断し、小さければ当該ノードは実ノードであるため、そのルールリストに対するＰａｒａｌｌｅｌ  ＢＶ処理を行うため、当該ノードのＢＶが記憶されたＢａｓｅ  Ａｄｄｒｅｓｓを各ＢＶ選択回路に出力し、また、当該ノードのルールＩＤリスト記憶ブロック２０４のアドレス値として、入力されたアドレス値を出力する。なお、この際、ルールＩＤリスト記憶ブロック２０４には、ＷＰ個のノードに対するルールＩＤリストしか保持していないため、アドレスのビット幅はｌｏｇ２ＷＰ以上の最小の整数値で良い。一方、入力されたアドレス値が、ＷＰよりも大きければ、当該ノードはＶｉｒｔｕａｌ  Ｎｏｄｅであるため、当該Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおける処理を行わないことを示す信号を出力する。
【００７８】
ＢＶ選択回路に関する構成の説明は後述するが、ＢＶ選択回路では、当該フィールドに対するＢＶを選択し、ＡＮＤゲート２０２に出力する。各フィールドに対するＢＶが入力されるＡＮＤゲート２０２では、それらのＢＶのビット単位の論理積（ＡＮＤ）を取り、優先度チェック回路２０３へ出力する。
【００７９】
優先度チェック回路２０３では、アドレス変換回路２０１から指定されたアドレス値にあるルールＩＤリストを読み込み、ＡＮＤゲート２０２から出力されたＢＶの‘１’の値をもつ各ビットに対応するルールＩＤを適合しているルールとして判断し、前段のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅから入力された最適ルールを含めた優先度の比較を行い、その時点での最適ルールＩＤを後段のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに出力する。
【００８０】
図２２は、本発明の第１の実施の形態におけるＢＶ選択回路の構成を示すブロック図である。図２２を参照すると、本実施の形態におけるＢＶ選択回路は、探索回路２０００と、メモリ等の記憶媒体から構成されるＢｉｔ  Ｖｅｃｔｏｒ（ＢＶ）記憶ブロック（ビット配列記憶ブロック）２００１と、を備える。
【００８１】
探索回路２０００は、アドレス変換回路２０１から入力された当該ノードのＢＶが記憶されているＢａｓｅ  Ａｄｄｒｅｓｓと、フィールド分離回路２００から入力された当該ＢＶ選択回路が処理するヘッダフィールドデータと、有効ビット長と、から、当該フィールドデータに対応するＢＶを選択し、ＢＶ記憶ブロック２００１から読み出し、ＡＮＤゲート２０２へ出力する。ここで、本実施の形態では、非特許文献３で開示されているＰａｒａｌｌｅｌ  ＢＶ方式を用いるものとし、ＢＶ記憶ブロック２００１には、ＢａｓｅＡｄｄｒｅｓｓからＢＶをもつ区間の開始位置、又は終了位置と当該区間のＢＶが記憶されており、探索回路２０００はこれらのデータを読み出し、入力されたヘッダフィールドデータと有効ビット長を参照しながら、例えば二分探索を行うことで適切なＢＶを読み出すものとする。なお、二分探索の実現方法については、当事者にとってはよく知られているため、ここでは詳細な説明を省略する。
【００８２】
本実施の形態では、上記のような処理を行い、最終的にＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−Ｈからの出力が最適解となるため、出力３によって出力する。
【００８３】
なお、本実施の形態においては、領域分割情報におけるＬｅａｆ  Ｆｌａｇによって、当該ノードが葉ノードであると判断した場合、構成図では省略したが、当該Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおける領域分割情報は実行せず、その情報を後段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに出力し、以降のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅでは領域分割情報の読み出しや領域分割を実行しないといった処理を行う。なお、この際、当該Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅのすぐ次のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅでは、当該葉ノードのルールＩＤリストに対するＰａｒａｌｌｅｌ  ＢＶ処理は実行する必要があるため、例えば、前段から葉ノードであるという信号を受け取ったＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅから各種信号が入力されるＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ以降では、Ｐａｒａｌｌｅｌ  ＢＶ処理を実行しない等の処理を行う。
【００８４】
（１−２）第１の実施の形態の動作
次に、図９の本発明における基本的なパケット分類方法を示す流れ図と、図１４、図１６、図１７、図１８、図２１、図２２の本実施の形態の構成図を参照しながら、本実施の形態における動作について説明する。なお、本発明における基本的なパケット分類方法、及び本実施の形態における各構成要素の動作概要については、既に説明した通りであるため、ここでは、基本的なパケット分類方法に対する本実施の形態における特徴的な動作に焦点を当てて説明する。
【００８５】
本実施の形態におけるパケット分類器１に被検索対象パケットのヘッダフィールドデータが入力されると、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅの根ノードを処理ノードとし（ステップＡ１）、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−０にて、Ｐａｒａｌｌｅｌ  ＢＶ処理を行う（ステップＡ２）。
【００８６】
図２３は、本発明の第１の実施の領域分割時の動作（ステップＡ２）を示す流れ図である。Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−０では、アドレス変換回路２０１において、入力されたアドレス値から、当該処理ノードのルールＩＤリスト、及びＢＶ情報が記憶されているアドレス値に変換する（ステップＢ１）。続いて、フィールド分離回路２００において、入力された検索キーと有効ビット長から、各フィールドの有効ビットを切り出す（ステップＢ２）。次に、各ＢＶ選択回路２００−１から２００−Ｆにおいて、アドレス変換回路２０１からのアドレス値、及びフィールド分離回路２００からの有効ビットを元に、探索回路２０００によって適切なＢＶをＢＶ記憶ブロック２００１から読み出す（ステップＢ３）。各ＢＶ選択回路から選択されたＢＶは、ＡＮＤゲート２０１によってビット毎の論理積を取り、当該ノードにおける最終的なＢＶとし（ステップＢ４）、ステップＡ２の処理を終了する。
【００８７】
続いて、優先度チェック回路２０３は、アドレス変換回路２０１から指定されたアドレス値を元に、ルールＩＤリスト記憶ブロック２０４から、当該ノードにおけるルールＩＤリストを読み出し、前段のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅまでの最適ルールを含めた最適ルールを選択する。なお、ルールＩＤリストには、当該ルールの優先度も保持されているものとする（ステップＡ３）。
【００８８】
次に、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１にて、根ノードにおける領域分割情報を読み出す（ステップＡ４）。読み出した領域分割情報のＬｅａｆ  Ｎｏｄｅから、当該ノードが葉ノードでないと判断すると（ステップＡ５のＮｏ）、読み出した領域分割情報を用いて、領域分割回路１００において領域分割処理を実行する（ステップＡ６）。
【００８９】
図２４は、本発明の第１の実施の領域分割時の動作（ステップＡ６）を示す流れ図である。領域分割処理は、領域分割回路１００におけるフィールド分割回路１００−１から１００−Ｃにて実行される。なお、各フィールド分割回路への入力データは、上述した通りである。
【００９０】
領域分割処理では、まず、フィールド分割回路１００−１における加算器１００６へ入力されるこれまでの分割数を０とする（ステップＣ１）。続いて、減算器１００４において、入力された有効ビット長から当該フィールドの分割数を減じる（ステップＣ２）。さらに、Ｒｉｇｈｔ  Ｓｈｉｆｔｅｒ１００５において、ステップＣ２で得た結果の値だけ、入力された当該フィールドデータを右にシフトさせる（ステップＣ３）。一方、加算器１００６においてこれまでの分割数と当該フィールドの分割数を加算し（ステップＣ４）、その結果の値だけ、Ｌｅｆｔ  Ｓｈｉｆｔｅｒ１００７においてステップＣ３で得た当該フィールドデータを左シフトさせる（ステップＣ５）。上記の処理はフィールド分割回路１００−１に対する処理であり、他の領域分割を行うフィールドが存在する（ステップＣ６のＹｅｓ）ため、それらに対しても上記と同様の処理（ステップＣ２からステップＣ５）を実行する。なお、フィールド分割回路１００−２における加算器１００６に入力されるこれまでの分割数は、フィールド分割回路１００−１の加算器１００６の加算結果であり、フィールド分割回路１００−３における加算器１００６に入力されるこれまでの分割数は、フィールド分割回路１００−２の加算器１００６の加算結果である。同様に、一般化し、フィールド分割回路１００−ｎ（ｎ＝２、３、・・・、Ｃ）における加算器１００６に入力されるこれまでの分割数は、フィールド分割回路１００−（ｎ−１）の加算器１００６の加算結果である。最終的に、フィールド分割回路１００−Ｃにおいて、ステップＣ５までの処理が終了すると、領域分割情報に含まれる領域分割フィールドに対する処理が全て終了するため（ステップＣ６のＮｏ）、ＯＲゲート１００２において、各フィールド分割回路で得た結果（Ｌｅｆｔ  Ｓｈｉｆｔｅｒ１００７の出力）の論理和を取る（ステップＣ７）。最後に、加算器１００３において、ステップＣ７の結果とＢａｓｅ  Ａｄｄｒｅｓｓを加算し（ステップＣ８）、ステップＡ６の処理を終了する。
【００９１】
一方、有効ビット長更新回路１０３においては、入力された領域分割を行う各フィールドの有効ビット長を、領域分割情報で指定された分割数を元に更新し（ステップＡ７）、ステップＡ２へ戻る。
【００９２】
上記の処理を、全てのＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ、及び全てのＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおいて行う。ここで、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの葉ノードの処理について説明する。Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−Ｈで処理したノードが葉ノードでない場合、つまり、領域分割情報を読み出した結果、Ｌｅａｆ  Ｆｌａｇが‘０’の場合、本パケット分類器で処理するＤｅｃｉｓｉｏｎ  Ｔｒｅｅの制約上、次の処理ノードは必ず葉ノードとなる。このため、最後の葉ノードでは領域分割を行わないため、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−Ｈにて、葉ノードのルールリストに対するＰａｒａｌｌｅｌ  ＢＶ処理を実行し、それまでの結果から最適解を得る。一方、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−Ｈに到達するまでに、読み出した領域分割情報におけるＬｅａｆ  Ｆｌａｇが‘１’、つまり、当該処理ノードが葉ノードであった場合、上述したように、続くＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおいて葉ノードのルールリストに対するＰａｒａｌｌｅｌ  ＢＶ処理のみを実行し、それ以降のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ、及びＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおける処理は実行しない、又は、実行してもそれまでに得られている最適解が変更されないように処理を行うものとする。葉ノードの処理を行った結果、それまでに得られている最適ルールを最終的な解とすることが可能となる（ステップＡ５）。
【００９３】
なお、上記の本実施の形態では、各Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおいて、領域分割情報にＶｉｒｔｕａｌ  Ｆｌａｇを持たせることで、当該処理ノードが実ノードであるか、Ｖｉｒｔｕａｌ  Ｎｏｄｅであるか判断していたが、領域分割情報にＶｉｒｔｕａｌ  Ｆｌａｇを保持せず、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの加算器１００３の後段において、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおけるアドレス変換回路２０１を備えることで、算出したアドレス値と、後段のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅのワード数（ノード数）ＷＰを比較させることで、Ｖｉｒｔｕａｌ  Ｎｏｄｅを判断し、後段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに対してその情報を出力させることで、同様の処理を実現することが可能である。
【００９４】
また、上記の本実施の形態では、各Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおいては、非特許文献３で開示されているＰａｒａｌｌｅｌ  ＢＶ処理をベースとしたが、これを非特許文献４で開示されているＰａｒａｌｌｅｌ  ＢＶ処理をベースに用いても良い。この場合の詳細なＰａｒａｌｌｅｌ  ＢＶ処理は、非特許文献４で開示されているため省略するが、上記ステップＡ２のＰａｒａｌｌｅｌ  ＢＶ処理は、図２５に示すような処理となる。但し、非特許文献３、非特許文献４共に、ルールＩＤリストを用いてＢＶの各ビット位置とルールとを対応付けることは変わらない。
【００９５】
図２５は、非特許文献４で開示されているＰａｒａｌｌｅｌ  ＢＶ処理をベースに用いた場合の本発明の第１の実施の領域分割時の動作（ステップＡ２）を示す流れ図である。この場合、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−０では、ステップＢ１とステップＢ２の処理を行う。なお、ステップＢ１とステップＢ２は、図２３に示した流れ図における動作と同様であることから、その説明を省略する。次に、非特許文献４で開示されるＰａｒａｌｌｅｌ  ＢＶ処理を用いた場合、ＢＶ選択回路２００−１から２００−Ｆにおいて、アドレス変換回路２０１からのアドレス値、及びフィールド分離回路２００からの有効ビットを元に、探索回路２０００によって各フィールドのサブフィールド単位に１つのＢＶをＢＶ記憶ブロック２００１から読み出す（ステップＢ５）。続いて、各ＢＶ選択回路から読み出された複数のＢＶに対して、ＡＮＤゲート２０１によってビット毎の論理積を取り、当該ノードにおける最終的なＢＶとし（ステップＢ６）、ステップＡ２の処理を終了する。なお、非特許文献４で開示されるＰａｒａｌｌｅｌ  ＢＶ処理をベースに用いた場合、ＢＶ選択回路はフィールド毎に分離していなくてもよく、１つのＢＶ選択回路によって複数のＢＶを読み出しても良い。
【００９６】
さらに、上記ではＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１にＤｅｃｉｓｉｏｎ  Ｔｒｅｅの根ノードが配置される例を用いて説明したが、これをＤｅｃｉｓｉｏｎ  Ｔｒｅｅの複数の部分木の根ノードをＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１から配置していく形態でも構わず、本実施の構成を何ら変更せずに構成することができることは明らかである。図２６は、本発明の第１の実施の形態における複数のＤｅｃｉｓｉｏｎ  ＴｒｅｅノードのＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅへのマッピング例を示す図である。図２６では、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの根ノードであるノード０の子ノード（図２６では、ノード１とノード１４）をＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１に配置している。この場合、ノード０のＮ個の子ノードを根ノードとするＮ個の部分木が１つのＴｒｅｅ  Ｐｉｐｅｌｉｎｅ上に配置される。但し、この場合、根ノードであるノード０における領域分割処理に相当する処理ブロックが必要であり、図１４に示す本パケット分類器１の入力２が入力されてすぐにＩｎｄｅｘ  Ｔａｂｌｅに相当するような処理ブロックを配置し、その出力によって、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１、及びＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ２０−０への入力となる検索キーや有効ビット長、アドレス値等を決定する。この処理ブロックについては、上述した本パケット分類器の構成を流用しても良いし、検索キーの先頭数ビットを参照して決定してもよく、当事者にとっては容易に構成できるため、詳細な説明は省略する。
【００９７】
（１−３）第１の実施の形態の作用効果
次に、本発明の第１の実施の形態の作用効果について説明する。
【００９８】
上記のように、本実施の形態において、Ｄｉｃｉｓｉｏｎ  ＴｒｅｅとＰａｒａｌｌｅｌ  Ｂｉｔ  Ｖｅｃｔｏｒを組み合わせることにより、１パケットあたりの処理においてメモリから読み出すデータ量を削減することができ、１つのルールを構成するヘッダフィールド長の総和が大きくなっても、また、ルール数が多くなっても、メモリのＤｙｎａｍｉｃ  Ｐｏｗｅｒの増加を抑制し、結果的にハードウェア全体の消費電力を増加させないパケット分類器を提供することができる。
【００９９】
具体的に、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅベースの手法と、本発明におけるパケット分類器の１パケットあたりの処理においてメモリから読み出すデータ量の比較を以下に行う。
【０１００】
まず、ルールはＦ個のフィールドから構成され、各フィールドのフィールド長をＷｉ［ｂｉｔｓ］（ｉ＝０、１、・・・、Ｆ−１）とし、ルールを構成する全ビット長をＷ［ｂｉｔｓ］とすると、以下の式が成り立つ。
【０１０１】
【数１】
2011108168.tif 000003
本発明におけるパケット分類器が対象とするルールにおけるマッチング手法として、Ｅｘａｃｔ  Ｍａｔｃｈ、Ｐｒｅｆｉｘ  Ｍａｔｃｈ、Ｒａｎｇｅ  Ｍａｔｃｈを想定した場合、ルールを構成するフィールドあたり、２倍のビット長、つまり２Ｗ［ｂｉｔｓ］が必要になる。これは、Ｒａｎｇｅ  Ｍａｔｃｈのように下限値と上限値を指定する必要があるためである。なお、このようにフィールドあたり２Ｗ［ｂｉｔｓ］で指定する場合、最初の第１値であるＷ［ｂｉｔｓ］にて特定値を指定し、次の第２値であるＷ［ｂｉｔｓ］でマスクを指定することで、Ｅｘａｃｔ  ＭａｔｃｈとＰｒｅｆｉｘ  Ｍａｔｃｈとしても指定可能となる。より厳密には、第２値がマスクを示すのか、Ｒａｎｇｅ  Ｍａｔｃｈにおける上限値を示すのかを判別するための１ｂｉｔのフラグ等を用いることが考えられるが、ここでは簡単化のためルールは２Ｗ［ｂｉｔｓ］で指定されるものとする。
【０１０２】
次に、本パケット分類器がサポートする全ルール数をＲとし、各ノードのルールリストに含むことができるルール数をＬとする。ルールリストに含むことができるルール数Ｌは、ノード毎に変更しても良いが、ここでは全ノード共に同一の値を用いるものとする。但し、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅをベースとした手法では、ルールリストを連続的に読み出すのに効率が良いよう、ルールリスト毎にまとまった記憶領域にルールを記憶させるものとする。つまり、領域をまたぐルールはそこで複製されるため、Ｒと、全ノードに対するＬの総和が等しいとは限らない。
【０１０３】
なお、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅ自体を辿る各Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおけるデータ読み出し量は、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅベースの手法でも、本発明におけるパケット分類手法でもほぼ同様であるため省略し、ルールリストに対するマッチング処理におけるデータ読み出し量に焦点を当てて、見積もる。
【０１０４】
まず、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅベースの手法の場合、１つのルールリストに含まれるＬ個のルール全てをメモリから読み出す必要がある。ここで言うルールは上述したように２Ｗ［ｂｉｔｓ］で規定されているため、１ノードあたりに読み出すデータ量ＤＥ［ｂｉｔｓ］は、ルールリストに含まれるルール数Ｌとルールのビット長２Ｗ［ｂｉｔｓ］の積で得られる。
【０１０５】
【数２】
2011108168.tif 000004
一方、非特許文献３で開示されているＰａｒａｌｌｅｌ  ＢＶ処理をベースに用いた場合の本発明のパケット分類手法を用いた場合、探索回路２０００において、ＢＶ記憶ブロック２００１から、フィールド毎に区間の開始値、または終了値と、ルールリストに含まれるＬ個のルールに対するＢＶから構成されるＷｉ＋Ｌ［ｂｉｔｓ］のデータを読み出す必要がある。なお、Ｎ個の要素に対して二分探索を用いた場合、一般的には、［ｌｏｇ２Ｎ］＋１回の比較を行うことで探索を行うことが可能である。ここで、［ｘ］はｘ以上の最小の整数を意味する。また、Ｌ個のルールが存在する場合のＰａｒａｌｌｅｌ  ＢＶにおける区間は、非特許文献２から、高々２Ｌ＋１個である。このことから、１フィールドあたりに読み出すデータ量は（Ｗｉ＋Ｌ）×｛［ｌｏｇ２（２Ｌ＋１）］＋１｝であり、Ｆ個のフィールドに対してこれを行う。また、ルールＩＤリストを１つ読み出すが、ルール数Ｒのとき、ルールＩＤは［ｌｏｇ２Ｒ］［ｂｉｔｓ］で表現でき、ルールＩＤリストにはＬ個のルールＩＤが含まれるため、上記を考慮すると、１ルールリストあたりに読み出すデータ量ＤＰ［ｂｉｔｓ］は、式１から以下の式で得られる。
【０１０６】
【数３】
2011108168.tif 000005
例えば、ルールが送信元ＩＰアドレス（３２ｂｉｔｓ）、宛先ＩＰアドレス（３２ｂｉｔｓ）、プロトコル番号（８ｂｉｔｓ）、送信ポート番号（１６ｂｉｔｓ）、宛先ポート番号（１６ｂｉｔｓ）の５−ｔｕｐｌｅで構成されるとした場合、Ｗ＝１０４［ｂｉｔｓ］、Ｆ＝５であり、ルールリストに含まれるルール数をＬ＝８、全ルール数を１０Ｋ（＝１０×２１０）とすると、ＤＥ＝２×８×１０４＝１６６４［ｂｉｔｓ］であり、ＤＰ＝８×［ｌｏｇ２（１０×２１０）］＋（１０４＋５×８）×（［ｌｏｇ２（２×８＋１）］＋１）＝８×１４＋１４４×６＝１１２＋８６４＝９７６［ｂｉｔｓ］となり、１ルールリストあたり６８８ｂｉｔｓのデータ量を削減することが可能となる。Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの高さＨに対して、処理するルールリストはＨ＋１個存在するため、この差のＨ＋１倍の読み出しデータ量を削減することができる。
【０１０７】
また、例えば、上記でＬ＝１６とすると、ＤＥ＝２×１６×１０４＝３３２８［ｂｉｔｓ］であり、ＤＰ＝１６×［ｌｏｇ２（１０×２１０）］＋（１０４＋５×１６）×（［ｌｏｇ２（２×１６＋１）］＋１）＝１６×１４＋１８４×７＝２２４＋１２８８＝１５１２［ｂｉｔｓ］となり、１ルールリストあたり１８１６ｂｉｔｓのデータ量を削減することが可能であり、ルールリストに含まれるルール数Ｌが増えるほど、その差は大きくなることが分かる。
【０１０８】
同様に、例えば、上記でＩＰｖ６を想定し、送信元ＩＰアドレスと宛先ＩＰアドレスがそれぞれ１２８ｂｉｔｓであるとすると、Ｗ＝２９６［ｂｉｔｓ］となる。この場合、ＤＥ＝２×８×２９６＝４７３６［ｂｉｔｓ］であり、ＤＰ＝８×［ｌｏｇ２（１０×２１０）］＋（２９６＋５×８）×（［ｌｏｇ２（２×８＋１）］＋１）＝８×１４＋３３６×６＝１１２＋２０１２＝２１２４［ｂｉｔｓ］となり、１ルールリストあたり２６１２ｂｉｔｓの読み出しデータ量を削減することが可能であり、ルールのビット長が増加すればするほど、その差は大きくなることが分かる。
【０１０９】
さらに、上記で全ルール数をＲ＝１Ｍ（＝２２０）とすると、ＤＥ＝２×８×１０４＝１６６４［ｂｉｔｓ］であり、ＤＰ＝８×［ｌｏｇ２（２２０）］＋（１０４＋５×８）×（［ｌｏｇ２（２×８＋１）］＋１）＝８×２０＋１４４×６＝１６０＋８６４＝１０２４［ｂｉｔｓ］となり、全ルール数が１Ｍに増加した場合でも１ルールリストあたり６４０ｂｉｔｓの読み出しデータ量を削減することが可能となる。
【０１１０】
また、非特許文献４で開示されているＰａｒａｌｌｅｌ  ＢＶ処理をベースに用いた場合の本発明のパケット分類手法を用いた場合、探索回路２０００において、フィールドの複数ビット単位にＬ［ｂｉｔｓ］のＢＶデータを読み出す。ここで、全フィールドに対して２ｂｉｔｓのサブフィールドを規定、つまり、ＢＶは２ｂｉｔｓ単位に読み出すとすると、ルールのビット長Ｗ［ｂｉｔｓ］に対してＷ／２個のＢＶを読み出すことになる。さらに、１つのルールＩＤリストを読み出すことから、１ルールリストあたりに読み出すデータ量ＤＰ［ｂｉｔｓ］は、以下の式で得られる。
【０１１１】
【数４】
2011108168.tif 000006
例えば、上記と同様、Ｗ＝１０４［ｂｉｔｓ］、Ｆ＝５、Ｌ＝８、Ｒ＝１０Ｋ（＝１０×２１０）とすると、ＤＥ＝１６６４［ｂｉｔｓ］であり、ＤＰ＝８×（［ｌｏｇ２（１０×２１０）］＋１０４／２）＝８×（１４＋５２）＝５２８［ｂｉｔｓ］となり、１ルールリストあたり１１３６ｂｉｔｓのデータ量を削減することが可能となる。Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅの高さＨに対して、処理するルールリストはＨ＋１個存在するため、この差のＨ＋１倍の読み出しデータ量を削減することができる。
【０１１２】
また、例えば、上記でＬ＝１６とすると、ＤＥ＝３３２８［ｂｉｔｓ］であり、ＤＰ＝１６×（［ｌｏｇ２（１０×２１０）］＋１０４／２）＝１６×（１４＋５２）＝１０５６［ｂｉｔｓ］となり、１ルールリストあたり２２７２ｂｉｔｓのデータ量を削減することが可能であり、ルールリストに含まれるルール数Ｌが増えるほど、その差は大きくなることが分かる。
【０１１３】
同様に、例えば、上記でＩＰｖ６を想定し、送信元ＩＰアドレスと宛先ＩＰアドレスがそれぞれ１２８ｂｉｔｓであるとすると、Ｗ＝２９６［ｂｉｔｓ］となる。この場合、ＤＥ＝４７３６［ｂｉｔｓ］であり、ＤＰ＝８×（［ｌｏｇ２（１０×２１０）］＋２９６／２）＝８×（１４＋１４８）＝１２９６［ｂｉｔｓ］となり、１ルールリストあたり３４４０ｂｉｔｓの読み出しデータ量を削減することが可能であり、ルールのビット長が増加すればするほど、その差は大きくなることが分かる。
【０１１４】
さらに、上記で全ルール数をＲ＝１Ｍ（＝２２０）とすると、ＤＥ＝１６６４［ｂｉｔｓ］であり、ＤＰ＝８×（［ｌｏｇ２（２２０）］＋１０４／２）＝８×（２０＋５２）＝５７６［ｂｉｔｓ］となり、全ルール数が１Ｍに増加した場合でも１ルールリストあたり１０８８ｂｉｔｓの読み出しデータ量を削減することが可能となる。
【０１１５】
以上より、本発明のパケット分類器を用いることで、１パケット処理あたりのメモリからの読み出しデータ量が削減できることが分かる。この結果、メモリのＤｙｎａｍｉｃ  Ｐｏｗｅｒを削減することができ、全体の消費電力の削減が見込まれる。
【０１１６】
また、Ｄｉｃｉｓｉｏｎ  ＴｒｅｅとＰａｒａｌｌｅｌ  ＢＶを組み合わせることにより、ルール数が多くても、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅによって適合する可能性のあるルール数を絞り込むことができるため、ＢＶのビット長を削減することができ、メモリからデータを読み出すのに必要なクロックサイクル数の増加を抑制できるパケット分類器を提供することができる。
【０１１７】
（２）第２の実施の形態
（２−１）第２の実施の形態の構成
次に、本発明の第２の実施の形態について図面を参照して説明する。
【０１１８】
本発明の第２の実施の形態におけるパケット分類器では、ルールを構成するヘッダフィールドとして、予め定められたフィールド以外を用いる場合にも、パケット分類器自体を再構成せずとも利用できるような構成になっている点が、第１の実施の形態におけるパケット分類器と異なる。但し、ルール全体のビット長Ｗ［ｂｉｔｓ］やルールを構成するヘッダフィールド数Ｆ、また、各ノードで領域分割に利用するヘッダフィールド数Ｃの値は予め定められており、その条件が許す範囲で自由に設定可能であるとする。
【０１１９】
本発明の第２の実施の形態におけるパケット分類器の全体構成は、第１の実施の形態におけるパケット分類器である図１４と同様であるが、本発明の第２の実施の形態におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成が第１の実施の形態におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成と異なる。
【０１２０】
図２７は、本発明の第２の実施の形態におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成を示すブロック図である。図２７を参照すると、本発明の第２の実施の形態におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅは、図１６に示す本発明の第１の実施の形態におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの領域分割回路１００と有効ビット長更新回路１０３が、領域分割回路１０５と有効ビット長更新回路１０７にそれぞれ置き換わり、さらに、フィールド抽出回路１０６が新たに追加された構成となっている。その他の構成については、第１の実施の形態におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅと同様であるため、詳細な説明は省略する。
【０１２１】
図２８は、本発明の第２の実施の形態におけるＤｅｃｉｓｉｏｎ  Ｔｒｅｅの各ノードにおける領域分割情報を示す図である。本発明の第２の実施の形態においては、領域分割情報において、上述した条件に合う範囲で定義されたルールを構成するヘッダフィールドを、フィールドＩＤを用いて一意に識別するため、図２８に示す領域分割情報を用いる。本領域分割情報は、フィールドＩＤとその分割数の組をＣ個備える以外は、図７に示した本発明の基本的なパケット分類方法における領域分割情報と同様である。フィールドＩＤは、ルールを構成するヘッダフィールドに対して予め定義されるものとする。
【０１２２】
本実施の構成におけるフィールド抽出回路１０６には、Ｍｅｍｏｒｙ  Ｃｏｎｔｒｏｌｌｅｒ１０１が領域分割情報記憶ブロック１０２から読み取った領域分割情報と、検索キーとその有効ビット長が入力される。フィールド抽出回路１０６は、領域分割情報に含まれるフィールドＩＤを参照し、検索キーと有効ビット長から当該処理ノードにおける領域分割に用いられるヘッダフィールドのデータを抽出する。抽出した検索キーと有効ビット長の各フィールドデータ、及び領域分割情報をそれぞれ情報毎に分離した状態で領域分割回路１０５に出力すると共に、抽出した有効ビット長の各フィールドデータと、そのフィールドの分割数を有効ビット長更新回路１０７に出力する。
【０１２３】
有効ビット長更新回路１０７は、入力された領域分割に用いられるヘッダフィールドの有効ビット長に対し、その分割数を減じることで、各有効ビット長を更新する。
【０１２４】
図２９は、本発明の第２の実施の形態における領域分割回路１０５の構成を示すブロック図である。図２９を参照すると、本発明の第２の実施の形態における領域分割回路１０５は、図１７に示す本発明の第１の実施の形態における領域分割回路１００から、領域分割情報分離回路１０００を除いた構成であり、その他の構成は本発明の第１の実施の形態における領域分割回路１００と同様であるため、詳細な説明は省略する。本実施の形態では、フィールド抽出回路１０６において、領域分割情報の各情報データは分離した状態で領域分割回路１０５に入力されるため、同様の機能を果たしていた領域分割情報分離回路１０００が除かれている。
【０１２５】
（２−２）第２の実施の形態の動作
次に、図３０の本発明の第２の実施の領域分割時の動作（ステップＡ６）を示す流れ図を参照しながら、本実施の形態における動作について説明する。なお、本実施の形態における動作は、図９に示す基本的なパケット分類方法の動作を示す流れ図と基本的には同様であり、ステップＡ６の領域分割時の動作のみ異なるため、ここでは、図９に示すステップＡ６の動作についてのみ説明を行い、その他について詳細な説明を省略する。
【０１２６】
本実施の形態における領域分割時の処理では、まず、フィールド抽出回路１０６において、Ｍｅｍｏｒｙ  Ｃｏｎｔｒｏｌｌｅｒ１０１から領域分割情報を、前段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅよりから検索キーと有効ビット長を受け取る。フィールド抽出回路１０６は、領域分割情報に含まれるＣ個のフィールドＩＤを参照し、対応するフィールドの分割数、及び検索キーと有効ビット長から対応するフィールドのデータを抽出し、領域分割回路１０５に出力する（ステップＣ９）。上記のデータを受け取った領域分割回路１０５は、図２４に示す本発明の第１の実施の形態における領域分割時の動作と同様、ステップＣ１からステップＣ８までの処理を実行し、結果として得たアドレス値を次ノードの領域分割情報が記憶されているメモリのアドレス値として出力する（ステップＣ１０）。なお、ステップＣ１からステップＣ８までの処理については、本発明の第１の実施の形態における動作と同様であるため、詳細な説明は省略する。
【０１２７】
なお、本実施の形態では、第１の実施の形態と同様、各Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおいて、領域分割情報にＶｉｒｔｕａｌ  Ｆｌａｇを持たせることで、当該処理ノードが実ノードであるか、Ｖｉｒｔｕａｌ  Ｎｏｄｅであるか判断していたが、領域分割情報にＶｉｒｔｕａｌ  Ｆｌａｇを保持せず、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの加算器１００３の後段において、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおけるアドレス変換回路２０１を備えることで、算出したアドレス値と、後段のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅのワード数（ノード数）ＷＰを比較させることで、Ｖｉｒｔｕａｌ  Ｎｏｄｅを判断し、後段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに対してその情報を出力させることで、同様の処理を実現することが可能である。
【０１２８】
また、本実施の形態では、第１の実施の形態と同様、各Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおいては、非特許文献３で開示されているＰａｒａｌｌｅｌ  ＢＶ処理をベースとしているが、これを非特許文献４で開示されているＰａｒａｌｌｅｌ  ＢＶ処理をベースに用いても良い。
【０１２９】
さらに、本実施の形態においても、第１の実施の形態と同様、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１にＤｅｃｉｓｉｏｎ  Ｔｒｅｅの根ノードが配置される例を用いて説明したが、これをＤｅｃｉｓｉｏｎ  Ｔｒｅｅの複数の部分木の根ノードをＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１から配置していく形態でも構わず、本実施の構成を何ら変更せずに構成することができることは明らかである。
【０１３０】
（２−３）第２の実施の形態の作用効果
次に、本発明の第２の実施の形態の作用効果について説明する。
【０１３１】
本実施の形態では、第１の実施の形態と同様、Ｄｉｃｉｓｉｏｎ  ＴｒｅｅとＰａｒａｌｌｅｌ  Ｂｉｔ  Ｖｅｃｔｏｒを組み合わせることにより、１パケットあたりの処理においてメモリから読み出すデータ量を削減することができ、１つのルールを構成するヘッダフィールド長の総和が大きくなっても、また、ルール数が多くなっても、メモリのＤｙｎａｍｉｃ  Ｐｏｗｅｒの増加を抑制し、結果的にハードウェア全体の消費電力を増加させないパケット分類器を提供することができる。なお、この際のＤｉｃｉｓｉｏｎ  Ｔｒｅｅベースの手法と、本発明におけるパケット分類器の１パケットあたりの処理においてメモリから読み出すデータ量の比較については、第１の実施の形態と同様であるため、省略する。
【０１３２】
また、本実施の形態では、第１の実施の形態と同様、Ｄｉｃｉｓｉｏｎ  ＴｒｅｅとＰａｒａｌｌｅｌ  ＢＶを組み合わせることにより、ルール数が多くても、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅによって適合する可能性のあるルール数を絞り込むことができるため、ＢＶのビット長を削減することができ、メモリからデータを読み出すのに必要なクロックサイクル数の増加を抑制できるパケット分類器を提供することができる。
【０１３３】
さらに、本実施の形態では、第１の実施の形態と異なり、ルールとして用いるパケットヘッダ情報を、ルールのビット長Ｗ、フィールド数Ｆ、領域分割に用いることができるフィールド数Ｃの許す範囲で、ハードウェア回路の変更を行うことなく、自由に変更できるパケット分類器を提供することができる。なお、本実施の形態では、図２８に示す領域分割情報に含まれる、各ノードで領域分割に利用するヘッダフィールド数Ｃや領域分割回路１０５に含まれるフィールド分割回路の数Ｃと、各Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに含まれるＢＶ選択回路の数Ｆ、また、本パケット分類器無いの検索キーを伝える信号線のビット幅Ｗは予め定められているため、上述した条件に合う範囲において自由に変更できるパケット分類器であることは明らかである。
【０１３４】
（３）第３の実施の形態
（３−１）第３の実施の形態の構成
次に、本発明の第３の実施の形態について図面を参照して説明する。
【０１３５】
本発明の第３の実施の形態におけるパケット分類器では、ヘッダフィールド単位等、検索キーを複数に分割し、それぞれの検索キー（これをサブ検索キーと呼ぶ）に対応した複数のＤｅｃｉｓｉｏｎ  Ｔｒｅｅを用いてパケット分類を行う点が、第１、第２の実施の形態と異なる。
【０１３６】
図３１は、本発明の第３の実施の形態におけるパケット分類器の構成を示す図である。図３１を参照すると、本発明の第３の実施の形態におけるパケット分類器４は、Ｐ個のＤｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路（決定木処理回路）３０−１、３０−２、・・・、３０−Ｐと、最適解選択回路４０と、検索キー分離回路５０と、を含む。
【０１３７】
本実施の形態における入力２は、第１、第２の実施の形態と同様、検索キーが入力される。また、本実施の形態における出力３は、第１、第２の実施の形態と同様、適合したルールのうち、最も適切なルールＩＤが結果として出力される。
【０１３８】
検索キー分離回路５０は、入力された検索キーを、Ｐ個のサブ検索キーに分離し、個々のサブ検索キーを、それぞれのサブ検索キーに対応するＤｅｃｉｓｉｏｎ  Ｔｒｅｅを構成しているＤｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路に出力する。
【０１３９】
図３２は、本発明の第３の実施の形態におけるＤｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路の構成を示す図である。本実施の形態におけるＤｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路は、第１、第２の実施の形態におけるパケット分類器１のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ２０を解候補選択回路２１に置き換えた構成であり、解候補選択回路２１から最適解選択回路４０へ解候補となるルールＩＤリストが出力される。その他の構成は第１、第２の実施の形態におけるパケット分類器１と同様の構成であるため、詳細な説明は省略する。
【０１４０】
解候補選択回路２１は、Ｈ＋１個のＢｉｔ  Ｖｅｃｔｏｒ（ＢＶ）処理回路２１−０、２１−１、２１−２、・・・、２１−（Ｈ−１）、２１−Ｈから構成される。図３３は、本実施の形態におけるＢＶ処理回路の構成を示すブロック図である。図３３を参照すると、本実施の形態におけるＢＶ処理回路は、図２１に示す本発明の第１、第２の実施の形態におけるＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成において、優先度チェック回路２０３を、解候補ルールＩＤリスト生成回路２０５に置き換え、前段のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  ＳｔａｇｅからのルールＩＤの入力、及び後段のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに対するルールＩＤの出力が無く、代わりに解候補ルールＩＤリスト生成回路２０５から、解候補となるルールＩＤリストを最適解選択回路４０へ出力する構成であり、その他の構成は、図２１に示す本発明の第１、第２の実施の形態におけるＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの構成と同様であるため、詳細な説明は省略する。
【０１４１】
解候補ルールＩＤリスト生成回路２０５は、ＯＲゲート２０２から入力された本ＢＶ処理回路における最終的なＢＶを受け取ると共に、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅから入力されたアドレス値に従って、ルールＩＤリスト記憶ブロック２０４からルールＩＤリストを読み出す。続いて、ＯＲゲート２０２から受け取ったＢＶの各ビット位置の値が１であれば、それに対応するルールＩＤリストのルールＩＤはそのままの値とし、０であれば、そのルールには適合していないことを示すため、当該ルールＩＤのビットを全て１とする。ルールＩＤのビットが全て１である場合、そのルールＩＤはｄｏｎ’ｔ  ｃａｒｅとし、そのルールＩＤ領域には適合するルールが存在しないことを意味する。上記のようにして生成したルールＩＤリストを最適解選択回路４０に出力する。
【０１４２】
最適解選択回路４０には、Ｐ個のＤｅｃｉｓｉｏｎ  Ｔｒｅｅ回路に含まれるＨ＋１個のＢＶ処理回路から、合計Ｐ×（Ｈ＋１）個のルールＩＤリストが入力される。このうち、同一のＤｅｃｉｓｉｏｎ  Ｔｒｅｅに含まれるＨ＋１個のＢＶ処理回路から入力されたルールＩＤリストは、それらを結合して当該サブ検索キーに対する解候補ルールＩＤリストとなる。図３４は、本発明の第３の実施の形態におけるルールＩＤリストの構成例を示す図である。最適解選択回路４０では、Ｐ個のこれら解候補ルールＩＤリストを比較し、Ｐ個の解候補ルールＩＤリスト全て含まれるルールＩＤを確認した上で、最も優先度が高い解を最適解とし、そのルールＩＤを出力３として出力する。なお、Ｐ個の解候補ルールＩＤリスト全てに含まれるルールＩＤの確認処理については、単なる比較処理であり、当事者にとっては容易に実現できるため、詳細な説明は省略する。
【０１４３】
本実施の形態では、ルールを構成する単一、又は複数のフィールド毎、あるいは、ルールのビット長を固定的に複数に分割する等し、Ｐ個に分割したフィールド、ビット長毎にＤｅｃｉｓｉｏｎ  Ｔｒｅｅを構成する。このようにして構成したＰ個のＤｅｃｉｓｉｏｎ  Ｔｒｅｅは、それぞれＰ個のＤｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路によって構成される。より具体的には、Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路におけるＴｒｅｅ  Ｐｉｐｅｌｉｎｅ１０上にＤｅｃｉｓｉｏｎ  Ｔｒｅｅが構成され、解候補選択回路２１のＢＶ処理回路において、第１、第２の実施の形態におけるＰａｒａｌｌｅｌ  ＢＶ処理が実行される。但し、この場合、各Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路によって処理した解はあくまでその分割したフィールド、又はビット長に対して適合した解であり、ルール、つまり検索キー全体に対して適合しているかは不明である。このため、各Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路で解候補となったルールＩＤを基に最適解選択回路４０にて、再度確認を行い、最適解を選択する。
【０１４４】
（３−２）第３の実施の形態の動作
次に、図３５の本発明の第３の実施の形態における動作を示す流れ図を参照しながら、本実施の形態における動作について説明する。
【０１４５】
本実施の形態におけるパケット分類の動作では、まず、入力２として入力された検索キーを、検索キー分離回路５０にて、Ｐ個のＤｅｃｉｓｉｏｎ  Ｔｒｅｅに対応するサブ検索キーに分離し、それぞれのサブ検索キーを各Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路に出力する（ステップＡ８）。ここで、本実施の形態では、上述したように、ルール、つまり検索キーを構成する単一、又は複数のフィールド毎、あるいは、ルールのビット長を固定的に複数に分割する等し、Ｐ個に分割したフィールド、ビット長毎にＤｅｃｉｓｉｏｎ  Ｔｒｅｅを構成している。サブ検索キーは、このＰ個に分割したそれぞれのフィールド、又はビット群を指す。
【０１４６】
続いて、各Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路では、第１、第２の実施の形態における動作と同様に、図９に示すステップＡ１からＡ７の処理を行う（ステップＡ９）。ここでは、第１、第２の実施の形態におけるＤｅｃｉｓｉｏｎ  Ｔｒｅｅが、検索キー全体に対するＤｅｃｉｓｉｏｎ  Ｔｒｅｅであり、本実施の形態におけるＤｅｃｉｓｉｏｎ  Ｔｒｅｅは、サブ検索キーに対するＴｒｅｅであるという点のみが異なり、本質的には何ら変わりはない。より具体的に、図３６に、ステップＡ２における本実施の形態におけるＰａｒａｌｌｅｌ  ＢＶ処理時の動作を示す流れ図を示す。本実施の形態では、解候補選択回路２１の各ＢＶ処理回路において、図３６に示すＰａｒａｌｌｅｌ  ＢＶ処理を行う。図３６を参照すると、本処理は、基本的に図２３に示す第１、第２の実施の形態におけるＰａｒａｌｌｅｌ  ＢＶ処理と同様である。各ＢＶ処理回路では、各Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅから、アドレス値や検索キー（ここではサブ検索キーとなる）、その有効ビット長が入力され、ステップＢ１からステップＢ４までの処理を、実行する（ステップＢ７）。本ステップＢ７の処理は、第１、第２の実施の形態と同様であるため、詳細な説明は省略する。各ＢＶ処理回路における解候補ルールＩＤリスト生成回路２０５では、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅから入力されたアドレス値に従って、ルールＩＤリスト記憶ブロック２０４からルールＩＤリストを読み出す。この読み出したルールＩＤリストに対し、ＯＲゲート２０２から入力されたＢＶの各ビット位置の値を確認しながら、最適解選択回路４０に出力するルールＩＤリストを生成する。ここで、ＯＲゲート２０２から入力されたＢＶの各ビットに対して、その値が１であれば、そのビット位置に対応するルールは解候補であることを意味するため、ルールＩＤリストの当該ルールＩＤはそのままの値とし、各ビットの値が０であれば、そのルールには適合していないことを示すため、当該ルールＩＤのビットを全て１とする（ステップＢ８）。なお、ルールＩＤのビットが全て１である場合、そのルールＩＤはｄｏｎ’ｔ  ｃａｒｅとし、そのルールＩＤ領域には適合するルールが存在しないことを意味するものとする。
【０１４７】
上記のようにして生成したルールＩＤリストを最適解選択回路４０に出力する。最適解選択回路４０では、Ｐ個のＤｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路に含まれるＨ＋１個のＢＶ処理回路から、それぞれのサブ検索キーに対する適合ルールのルールＩＤリストが入力される。これらのルールＩＤリストのうち、同一のＤｅｃｉｓｉｏｎ  Ｔｒｅｅ処理回路に含まれるＢＶ処理回路からのルールＩＤリストを結合し、解候補ルールＩＤリストを生成する（ステップＡ１０）。
【０１４８】
最後に、最適解選択回路４０では、Ｐ個の解候補ルールＩＤリスト全てに含まれるルールＩＤを確認すると共に、それらのルールのうち最も優先度の高いルールを最適解として、最終的な解とする（ステップＡ１１）。
【０１４９】
なお、上記の本実施の形態では、第１の実施の形態をベースに説明したが、第２の実施の形態をベースに用いても実現可能である。
【０１５０】
また、第１、第２の実施の形態と同様、各Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおいて、領域分割情報にＶｉｒｔｕａｌ  Ｆｌａｇを持たせることで、当該処理ノードが実ノードであるか、Ｖｉｒｔｕａｌ  Ｎｏｄｅであるか判断していたが、領域分割情報にＶｉｒｔｕａｌ  Ｆｌａｇを保持せず、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅの加算器１００３の後段において、Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおけるアドレス変換回路２０１を備えることで、算出したアドレス値と、後段のＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅのワード数（ノード数）ＷＰを比較させることで、Ｖｉｒｔｕａｌ  Ｎｏｄｅを判断し、後段のＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅに対してその情報を出力させることで、同様の処理を実現することが可能である。
【０１５１】
さらに、本実施の形態でも、第１、第２の実施の形態と同様、各Ｐｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅにおいては、非特許文献３で開示されているＰａｒａｌｌｅｌ  ＢＶ処理をベースとしているが、これを非特許文献４で開示されているＰａｒａｌｌｅｌ  ＢＶ処理をベースに用いても良い。
【０１５２】
上記に加え、本実施の形態においても、第１、第２の実施の形態と同様、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１にＤｅｃｉｓｉｏｎ  Ｔｒｅｅの根ノードが配置される例を用いて説明したが、これをＤｅｃｉｓｉｏｎ  Ｔｒｅｅの複数の部分木の根ノードをＴｒｅｅ  Ｐｉｐｅｌｉｎｅ  Ｓｔａｇｅ１０−１から配置していく形態でも構わず、本実施の構成を何ら変更せずに構成することができることは明らかである。
【０１５３】
（３−３）第３の実施の形態の作用効果
次に、本発明の第３の実施の形態の作用効果について説明する。
【０１５４】
本実施の形態では、第１、第２の実施の形態と同様、Ｄｉｃｉｓｉｏｎ  ＴｒｅｅとＰａｒａｌｌｅｌ  ＢＶを組み合わせることにより、１パケットあたりの処理においてメモリから読み出すデータ量を削減することができ、１つのルールを構成するヘッダフィールド長の総和が大きくなっても、また、ルール数が多くなっても、メモリのＤｙｎａｍｉｃ  Ｐｏｗｅｒの増加を抑制し、結果的にハードウェア全体の消費電力を増加させないパケット分類器を提供することができる。なお、この際のＤｉｃｉｓｉｏｎ  Ｔｒｅｅベースの手法と、本発明におけるパケット分類器の１パケットあたりの処理においてメモリから読み出すデータ量の比較については、第１、第２の実施の形態とサブ検索キーに対してＰａｒａｌｌｅｌ  ＢＶ処理を行うか否かの違いだけであり、本質的には同様であるため、省略する。
【０１５５】
また、本実施の形態では、第１、第２の実施の形態と同様、Ｄｉｃｉｓｉｏｎ  ＴｒｅｅとＰａｒａｌｌｅｌ  ＢＶを組み合わせることにより、ルール数が多くても、Ｄｉｃｉｓｉｏｎ  Ｔｒｅｅによって適合する可能性のあるルール数を絞り込むことができるため、ＢＶのビット長を削減することができ、メモリからデータを読み出すのに必要なクロックサイクル数の増加を抑制できるパケット分類器を提供することができる。
【０１５６】
さらに、本実施の形態では、第２の実施の形態と同様、ルールとして用いるパケットヘッダ情報を、ルールのビット長Ｗ、フィールド数Ｆ、領域分割に用いることができるフィールド数Ｃの許す範囲で、ハードウェア回路の変更を行うことなく、自由に変更できるパケット分類器を提供することができる。
【０１５７】
（４）第４の実施の形態
次に、本発明の第４の実施の形態について図面を参照して説明する。
【０１５８】
図３７は、本発明の第４の実施の形態のパケット分類器の構成例を示している。図３７において、パケット分類器は、プログラム処理装置５とネットワークインタフェース装置６と、パケット分類プログラム７と、を備える。
【０１５９】
プログラム処理装置５は、サーバやＰＣを初めとするホストのＣＰＵ等によって実現される。ネットワークインタフェース装置６は、例えば、サーバの拡張カードやオンボードで搭載されるＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。プログラム処理装置７は、サーバやＰＣをはじめとするホストのＣＰＵ等により実現される。
【０１６０】
本実施の形態では、ネットワークインタフェース装置６に、ネットワークから入力されたパケットから、本発明のパケット分類で用いる検索キーを抽出し、プログラム処理装置５に入力する。
【０１６１】
パケット分類プログラム７は、プログラム処理装置５によって実行されるコンピュータプログラムであり、プログラム処理装置５の動作を制御する。
【０１６２】
プログラム処理装置５には、本発明の第１、第２の実施例におけるパケット分類器１、より具体的にはＴｒｅｅ  Ｐｉｐｅｌｉｎｅ１０とＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ２０とを備えており、プログラム処理装置５がパケット分類プログラム７を実行することにより実現される。なお、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ１０とＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ２０の機能は、本発明の第１、第２の実施の形態と同じである。
【０１６３】
本発明の第１、第２の実施の形態では、上述のパケット分類器１はハードウェア回路によって実現しているが、同様の処理をソフトウェアによって実行する。さらに、プログラム処理装置５として、複数のＣＰＵコアを有するマルチコアプロセッサ（さらには、より多くのＣＰＵコアを有するメニーコアプロセッサ）によって構成し、各ＣＰＵコアに、Ｔｒｅｅ  Ｐｉｐｅｌｉｎｅ１０とＰｒｉｏｒｉｔｙ  Ｐｉｐｅｌｉｎｅ２０に具備されているそれぞれのＰｉｐｅｌｉｎｅ  Ｓｔａｇｅの処理を実行させることにより、より高速な処理が可能となる。
【０１６４】
なお、パケット分類プログラム７は、コンピュータ読み取り可能な記録媒体に記録されていてもよく、プログラム処理装置５として、本発明の第３の実施の形態におけるパケット分類器１の処理を実行させてもよい。
【０１６５】
以上、本発明の実施の形態が添付の図面を参照することにより説明された。但し、本発明は、上述の実施の形態に限定されず、要旨を逸脱しない範囲で当業者により適宜変更され得る。
【産業上の利用可能性】
【０１６６】
本発明は、パケットのヘッダ情報から特定のフィールドの組み合わせによって、パケットが属するフローを識別し、ＱｏＳ処理や負荷分散等、フロー毎に特定の処理を行わせるスイッチやルータ等のネットワーク装置、及びロードバランサー等のアプライアンス装置といった用途に適用できる。【０１６７】
本出願は、２０１０年３月５日に出願された日本出願特願２０１０−４９０５１を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2011108168.tif 000007
【図２】
2011108168.tif 000008
【図３】
2011108168.tif 000009
【図４】
2011108168.tif 000010
【図５】
2011108168.tif 000011
【図６】
2011108168.tif 000012
【図７】
2011108168.tif 000013
【図８】
2011108168.tif 000014
【図９】
2011108168.tif 000015
【図１０】
2011108168.tif 000016
【図１１】
2011108168.tif 000017
【図１２】
2011108168.tif 000018
【図１３ａ】
2011108168.tif 000019
【図１３ｂ】
2011108168.tif 000020
【図１３ｃ】
2011108168.tif 000021
【図１３ｄ】
2011108168.tif 000022
【図１４】
2011108168.tif 000023
【図１５】
2011108168.tif 000024
【図１６】
2011108168.tif 000025
【図１７】
2011108168.tif 000026
【図１８】
2011108168.tif 000027
【図１９】
2011108168.tif 000028
【図２０】
2011108168.tif 000029
【図２１】
2011108168.tif 000030
【図２２】
2011108168.tif 000031
【図２３】
2011108168.tif 000032
【図２４】
2011108168.tif 000033
【図２５】
2011108168.tif 000034
【図２６】
2011108168.tif 000035
【図２７】
2011108168.tif 000036
【図２８】
2011108168.tif 000037
【図２９】
2011108168.tif 000038
【図３０】
2011108168.tif 000039
【図３１】
2011108168.tif 000040
【図３２】
2011108168.tif 000041
【図３３】
2011108168.tif 000042
【図３４】
2011108168.tif 000043
【図３５】
2011108168.tif 000044
【図３６】
2011108168.tif 000045
【図３７】
2011108168.tif 000046
【手続補正書】
【提出日】平成24年8月17日(2012.8.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを、木構造をもつデータ構造と複数種類の予め決められた少数の長さのビット配列を用いて検索する、
ことを特徴とするパケット分類器。
【請求項２】
前記パケット分類器は、
決定木（Ｄｅｃｉｓｉｏｎ  Ｔｒｅｅ）を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込み、
検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定し、
特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する、
ことを特徴とする請求項１に記載のパケット分類器。
【請求項３】
前記パケット分類器は、
決定木を用いて、多数のルールから適合する可能性のあるルールを予め決められた個数に絞り込む処理をパイプライン制御によって行うツリーパイプライン処理回路と、
検索キーのうち予め決められたデータ毎に決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合するルールを特定する処理と、特定されたルールの優先度に応じて最終的結果としての適合ルールを決定する処理と、をパイプライン制御によって行うプライオリティパイプライン処理回路と、
を備えることを特徴とする請求項２に記載のパケット分類器。
【請求項４】
前記ツリーパイプライン処理回路は、
決定木の根ノードから開始し、深さ方向に１つノードを辿る処理を実行する複数のツリーパイプライン処理部を備え、
さらに、前記複数のツリーパイプライン処理部の各々は、
当該ツリーパイプライン処理部で処理するノードの領域分割情報を記憶する領域分割情報記憶ブロックと、
領域分割情報を読み出すメモリコントローラと、
領域分割情報を基に、入力された検索キーを用いて領域分割を行い、後段のツリーパイプライン処理部で処理するノードの領域分割情報が記憶された領域分割情報記憶ブロックに対するアドレス値を算出する領域分割回路と、
検索キーの有効ビット長を更新する有効ビット長更新回路と、
当該ツリーパイプライン処理部に入力された検索キーにある一定の遅延を持たせ、他の出力と同期させるための検索キー遅延回路と、を備え、
さらに、前記領域分割回路は、
当該ノードの領域分割情報から領域分割に用いるヘッダフィールド毎にその分割数を切り出す領域分割情報分離回路と、
ヘッダフィールド毎に領域分割処理を行うフィールド分割回路と、
前記領域分割情報分離回路の出力と前記フィールド分割回路の出力とを基に、後段のツリーパイプライン処理部で処理するノードの領域分割情報が記憶されたアドレス値を決定する決定部と、を備え、
前記プライオリティパイプライン処理回路は、
前記ツリーパイプライン処理部で処理したノードのルール識別子リストに対して、そのルール識別子リストと、ルール識別子リストの順序とビット位置とが対応付けられたビット配列と、を参照しながら、適合するルールを特定する処理と、それまでに適合すると判断したルールの中から優先度に応じてその時点で最も適合するルールを決定する処理と、を実行する複数のプライオリティパイプライン処理部を備え、
さらに、前記複数のプライオリティパイプライン処理部の各々は、
検索キーに含まれる各ヘッダフィールドのデータを抽出するフィールド分離回路と、
前記ツリーパイプライン処理部から指定されたアドレス値から実際にルール識別子リストを有するノードであるかを判断するアドレス変換回路と、
当該ノードの前記ビット配列を選択する複数のビット配列選択回路と、
適合ルール候補のうち最も適合するルールを選択する優先度チェック回路と、
ルール識別子リストを記憶するルールＩＤリスト記憶ブロックと、を備え、
さらに、前記ビット配列選択回路は、
検索キーから切り出したヘッダフィールドの値によって適切な前記ビット配列を選択する探索回路と、
ビット配列を記憶するビット配列記憶ブロックと、を備える、
ことを特徴とする請求項３に記載のパケット分類器。
【請求項５】
前記決定木のノードにおける領域分割情報は、
当該ノードが決定木における葉ノードであるか否かを示すフラグと、
決定木の各ノードにおいて領域を分割するために用いる特定数のヘッダフィールドに対する当該ノードにおける分割数と、
当該ノードの子ノードの領域分割情報が格納されている領域分割情報記憶ブロックに対するベースアドレスと、
当該ノードが実ノードではなく仮想ノードであることを示すフラグと、から構成され、
前記分割数は、当該ヘッダフィールドに対して２kで分割する場合に、ｋで指定される
ことを特徴とする請求項４に記載のパケット分類器。
【請求項６】
前記複数のツリーパイプライン処理部の各々は、
さらに、各ノードにおける領域分割情報の分割数をフィールド識別子によって識別し、そのフィールド識別子を実際のルールに規定されたヘッダフィールドと対応付け、必要な情報を抽出するフィールド抽出回路を備える、
ことを特徴とする請求項４に記載のパケット分類器。
【請求項７】
前記決定木のノードにおける領域分割情報は、
当該ノードが決定木における葉ノードであるか否かを示すフラグと、
決定木の各ノードにおいて領域を分割するために用いるヘッダフィールドの当該ノードにおける分割数を示すフィールド識別子と分割数の組と、
当該ノードの子ノードの領域分割情報が格納されている領域分割情報記憶ブロックに対するベースアドレスと、
当該ノードが実ノードではなく仮想ノードであることを示すフラグと、から構成され、
前記分割数は、当該ヘッダフィールドに対して２kで分割する場合に、ｋで指定される
ことを特徴とする請求項６に記載のパケット分類器。
【請求項８】
前記パケット分類器は、
ヘッダフィールド単位または特定のビット長単位に独立に構成した複数の決定木に対し、それぞれの決定木毎に、検索キーのうち予め決められたデータ毎にルールを絞り込み、決定木で絞り込んだルール数と同じ長さのビット配列を利用し、これらのビット配列のビット位置が示すルール識別子をリストとして備えたルール識別子リストを用いて、絞り込んだルールから適合する可能性のあるルールを特定し、解候補ルール識別子リストを生成する処理をパイプライン制御によって行う複数の決定木処理回路と、
前記複数の決定木処理回路で特定された解候補ルール識別子リストから優先度の高い最も適合するルールを選択する最適解選択回路と、
各決定木処理回路が処理する決定木に対応する検索キーを抽出する検索キー分離回路と、
を備えることを特徴とする請求項２に記載のパケット分類器。
【請求項９】
前記決定木処理回路は、
決定木を用いて、多数のルールから適合する可能性のあるルールを絞り込む処理をパイプライン制御によって行うツリーパイプライン処理回路と、
解候補選択回路と、を備え、
さらに、前記ツリーパイプライン処理回路は、
決定木の根ノードから開始し、深さ方向に１つノードを辿る処理を実行する複数のツリーパイプライン処理部を備え、
さらに、前記複数のツリーパイプライン処理部の各々は、
当該ツリーパイプライン処理部で処理するノードの領域分割情報を記憶する領域分割情報記憶ブロックと、
領域分割情報を読み出すメモリコントローラと、
領域分割情報を基に、入力された検索キーを用いて領域分割を行い、後段のツリーパイプライン処理部で処理するノードの領域分割情報が記憶された領域分割情報記憶ブロックに対するアドレス値を算出する領域分割回路と、
検索キーの有効ビット長を更新する有効ビット長更新回路と、
当該ツリーパイプライン処理部に入力された検索キーにある一定の遅延を持たせ、他の出力と同期させるための検索キー遅延回路と、を備え、
さらに、前記領域分割回路は、
当該ノードの領域分割情報から領域分割に用いるヘッダフィールド毎にその分割数を切り出す領域分割情報分離回路と、
ヘッダフィールド毎に領域分割処理を行うフィールド分割回路と、
前記領域分割情報分離回路の出力と前記フィールド分割回路の出力とを基に、後段のツリーパイプライン処理部で処理するノードの領域分割情報が記憶されたアドレス値を決定する決定部と、を備え、
前記解候補選択回路は、
検索キーに含まれる各フィールドのデータを抽出するフィールド分離回路と、
前記ツリーパイプライン処理部から指定されたアドレス値から実際にルール識別子リストを有するノードであるかを判断するアドレス変換回路と、
当該ノードの前記ビット配列を選択する複数のビット配列選択回路と、
前記ルール識別子リストを記憶するルールＩＤリスト記憶ブロックと、
前記ビット配列とルール識別子リストを用いて、解候補ルール識別子リストを生成する解候補選択回路と、を備える、
ことを特徴とする請求項８に記載のパケット分類器。
【請求項１０】
複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを、木構造をもつデータ構造と複数種類の予め決められた少数の長さのビット配列を用いて検索する、
ことを特徴とするパケット分類方法。
【請求項１１】
複数のフィールドを用いて定義された多数のルールから構成されるルールセットから、被検索対象である検索キーが適合するルールを、木構造をもつデータ構造と複数種類の予め決められた少数の長さのビット配列を用いて検索する処理を、
コンピュータに実行させることを特徴とするパケット分類プログラム。
【国際調査報告】
2011108168.tif 000047
2011108168.tif 000048
2011108168.tif 000049