JP5682442B2 - パケット分類器、パケット分類方法、及びパケット分類プログラム - Google Patents

Description

本発明は、パケット分類（Ｐａｃｋｅｔ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ）に関する。

パケット分類は、ネットワーク上のルータやスイッチにおいて、パケットを「フロー」と呼ばれる一連の属性をもつパケット列に分類するための重要な技術である。パケット分類は、個々のフローに対するＱｏＳ（Ｑｕａｌｉｔｙ ｏｆ Ｓｅｒｖｉｃｅ）の提供や、ファイヤウォール（Ｆｉｒｅｗａｌｌ）等のセキュリティといった、付加的な価値をもつネットワークアプリケーションの実現に重要な役割を果たす。

パケット分類では、パケットのヘッダに含まれている１つ以上のフィールドを用いて、「ルール」が定義される。ルールは、「フィルタ」と呼ばれることもある。ルールは、例えば、パケットのＩＰ（Ｉｎｔｅｒｎｅｔ Ｐｒｏｔｏｃｏｌ）ヘッダに定義されている送信元ＩＰアドレス、宛先ＩＰアドレス、プロトコル番号に加え、ＴＣＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ Ｃｏｎｔｒｏｌ Ｐｒｏｔｏｃｏｌ）／ＵＤＰ（Ｕｓｅｒ Ｄａｔａｇｒａｍ Ｐｒｏｔｏｃｏｌ）ヘッダに定義されている送信ポート番号、宛先ポート番号といった複数のヘッダフィールドによって定義される。このようにルールが複数のヘッダフィールドを用いて定義されている場合のパケット分類は、特に、Ｍｕｌｔｉ−Ｆｉｅｌｄ Ｐａｃｋｅｔ Ｃｌａｓｓｉｆｉｃａｔｉｏｎと呼ばれる。

通常、このようなルールは複数個定義される。パケットが到着すると、そのパケットヘッダからルールの定義に用いられているフィールド値が抽出される。抽出されたフィールド値の組が複数個のルールと比較され、どのルールにマッチするか判定されることにより、パケットがフローに分類される。ここで、到着したパケットのヘッダから抽出されたフィールド値の組を「検索キー」と呼ぶ。また、一般的には、各ルールに対して、優先度（Ｐｒｉｏｒｉｔｙ）とアクション（Ａｃｔｉｏｎ）とが定義される。検索キーが複数個のルールのうち、２つ以上のルールにマッチする場合には、優先度がより高いルールが選択される。また、アクションには、そのルールにマッチした場合に到着パケットをどのように扱うか（例えば、廃棄する、１番のポートに送信する等）が定義される。

また、ルールにおける各フィールドに対しては、ある特定の値として定義されるＥｘａｃｔ Ｍａｔｃｈ、上位の複数ビットは特定されるが下位の数ビットはワイルドカード（ｗｉｌｄｃａｒｄ）‘＊’を用いて不定として定義されるＰｒｅｆｉｘ Ｍａｔｃｈ、２つのある特定の値の範囲として定義するＲａｎｇｅ Ｍａｔｃｈ、個々のビット単位にワイルドカードを指定して定義されるＷｉｌｄｃａｒｄ Ｍａｔｃｈといった手法が用いられる。例えば、８ｂｉｔのフィールドを考えた場合、“００１１０１０１”のように特定値として指定されるものがＥｘａｃｔ Ｍａｔｃｈ、“００１１＊＊＊＊”のように、“００１１”の４ｂｉｔから始まる値として指定されるものがＰｒｅｆｉｘ Ｍａｔｃｈ、［３−６４］のように８ｂｉｔのフィールドが１０進数で考えた際に３から６４の範囲に入っていればよいとするものがＲａｎｇｅ Ｍａｔｃｈ、“０＊＊１０＊０１”のようにビット単位でワイルドカードが使用できるものがＷｉｌｄｃａｒｄ Ｍａｔｃｈである。

このようなＭｕｌｔｉ−Ｆｉｅｌｄ Ｐａｃｋｅｔ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ技術に関して、ルールセットの大容量化とリンク速度の向上により、高速なルータやスイッチにおいてこれをいかに高速に処理させるかが１つの技術的な課題となっている。例えば、単純な手法として、ルールセットに含まれる全てのルールを優先度順にリストで管理し、リストの先頭（優先度が高いルール）から１つずつ順番に比較を行うリニアサーチ（Ｌｉｎｅａｒ Ｓｅａｒｃｈ）が考えられる。しかし、このような手法では、最悪ルールセットに含まれる全てのルールとの一致比較処理が必要となり、パケット分類処理にかかる時間が非常に大きくなってしまうという問題がある。このため、現状、高速なパケット分類処理を実現するためにＴｅｒｎａｒｙ Ｃｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ（ＴＣＡＭ）を基にした手法が用いられることが多い。

しかしながら、ＴＣＡＭはコストが高く、消費電力や回路規模も大きいといった問題が存在する。また、Ｒａｎｇｅ Ｍａｔｃｈを用いた場合には、そのルールをＰｒｅｆｉｘ Ｍａｔｃｈを用いたルールに分割する必要があるため、ルール数が増加してしまうといった問題もある。

その一方で、ＴＣＡＭの高コスト、高消費電力の問題を回避すべく、より低コスト、低消費電力なＳｔａｔｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ（ＳＲＡＭ）やＤｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ（ＤＲＡＭ）を用いた様々なＭｕｌｔｉ−Ｆｉｅｌｄ Ｐａｃｋｅｔ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ手法が提案されている。

例えば、非特許文献１では、「決定木（Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ）」を用いた手法が提案されている。決定木を用いた手法では、全てのルールに対してマッチングを行うのではなく、当該検索キーがマッチする可能性のある少数のルールに対してのみマッチングを行う。これにより、検索処理に要する時間が短縮される。決定木を用いた手法について図１〜図３を用いて簡単に説明する。

図１は、それぞれ４ｂｉｔ長である２つのフィールドＸ、Ｙを用いて定義されたＲ０からＲ１５までの１６個のルールからなるルールセットの例を示している。フィールドＸ、Ｙは、例えば、送信元ＩＰアドレスや送信元ポート番号等、実際のパケットヘッダフィールドに相当する。なお、フィールドＸは、２進数で表記されており、‘＊’はワイルドカードを示している。また、フィールドＹは、Ｒａｎｇｅ Ｍａｔｃｈで表記されており、“［ａ：ｂ］”のａ、ｂはそれぞれ下限値、上限値（１０進数表記）を示している。また、ここでは、各ルールに付与される優先度とアクションについては省略している。

図２は、図１で示されたルールセットを、フィールドＸ、Ｙの２軸から成る２次元空間上で表している。図中のＸ軸、Ｙ軸上の数は、それぞれ１０進数で表記してある。決定木を用いた手法によれば、図２に示されるような多次元空間を複数の次元に着目して分割する。そして、分割領域内に存在するルール数がある閾値以下になるまで領域分割を繰り返すことにより、決定木が構築される。ここで、分割された領域で管理されるルール群を「ルールリスト」と呼ぶ。

図３は、図１で示されたルールセットに対して構築された決定木の一例を示している。なお、図３で示される決定木では、分割領域内のルール数の閾値は２に設定されている。図３に示されるように、まず、全空間がＸ方向とＹ方向のそれぞれに２分割される。つまり、全空間（Ｘ、Ｙ）＝（［０：１５］、［０：１５］）が、領域０（［０：７］、［０：７］）、領域１（［０：７］、［８：１５］）、領域２（［８：１５］、［０：７］）、及び領域３（［８：１５］、［８：１５］）の４つの領域に分割される。また、それぞれの領域で管理されるルールリストは、［Ｒ７、Ｒ８、Ｒ９、Ｒ１１］（領域０）、［Ｒ０、Ｒ６、Ｒ９、Ｒ１０、Ｒ１１、Ｒ１２］（領域１）、［Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５、Ｒ１３、Ｒ１４］（領域２）、［Ｒ１０、Ｒ１４、Ｒ１５］（領域３）となる。各領域には、まだ閾値である２よりも多いルールが管理されているため、それぞれの領域について、閾値以下のルール数になるまでさらに領域分割を行う。図３に示される例では、全空間は最終的に２２の領域に分割されている。なお、決定木を構築するアルゴリズムについては、非特許文献１や非特許文献２に記載されているため、ここでは省略する。

パケット分類を行う場合には、検索キーを参照しながら決定木を辿っていき、辿り着いた葉ノードで管理されている閾値数以下のルールの全てに対してマッチングが行われる。例として、検索キーがＸ＝０１１１、Ｙ＝１００１となるパケットに対するパケット分類を考える。図３に示される決定木では、根ノードにおいて全空間が上記４つの領域に分割されており、当該パケットは、それら４つの領域のうち、領域１（［０：７］、［８：１５］）に属することが分かる。続いて、領域１のノードでは、更に、空間がＸ方向とＹ方向のそれぞれに２分割されている。つまり、領域１が、領域１０（［０：３］、［８：１１］）、領域１１（［０：３］、［１２：１５］）、領域１２（［４：７］、［８：１１］）、及び領域１３（［４：７］、［１２：１５］）に４分割されている。当該パケットは、このうち領域１２に属することが分かる。更にその領域１２は４分割されており、当該パケットは、領域１２２（［６：７］、［８：９］）に属することが分かる。そして、その領域１２２で管理されている２つのルールＲ９、Ｒ１０に対してマッチングが実施され、マッチしたルールが選択される。なお、本例では、当該パケットがルールＲ９、Ｒ１０の両方にマッチするため、図３では省略している各ルールに付与された優先度に応じて、ルールが選択される。

以上に説明されたような決定木を用いた手法によれば、領域分割の結果、同じルールが複数の分割領域で管理される可能性があり、これは以下「ルールの複製」と参照される。例えば、図３では、Ｒ７やＲ９等のルールが複製されている。ルールの複製が発生した場合、複製されたルールそのもの、あるいは、複製されたルールに対するアドレス値を管理するためのメモリ容量が増加し、見た目上、実際のルールセットよりも多くのルールを扱うことになる。つまり、ルールの複製は、決定木におけるデータ量の増加を招く。

ルールの複製を抑制するため、非特許文献３で開示されているような手法が提案されている。非特許文献３では、複数の決定木を用意し、決定木毎に領域分割に用いるフィールド（次元）を使い分けることにより、異なる決定木を構築する。そして、各ルールは、ルールの複製が発生しないいずれかの決定木において管理する。決定木の数には上限があるため、いずれの決定木においても複製が発生しない場合には、例えば最後の決定木にて当該ルールは管理されることになるが、複数の決定木を用いることによってルールの複製を防止することができる。なお、非特許文献３の方式は、非特許文献２と同様、ハードウェアがパイプライン処理を用いてパケット分類を実施する方式として提案されている。

また、特許文献１では、パケットのタイプと、そのパケットタイプに依存して存在する複数のパケットフィールド値から成るルールとの組み合わせを単一の分類規則テーブル（ルールテーブル）で管理するパケット分類器が開示されている。パケットタイプをインデックスとして利用することにより、様々なパケットタイプに対するルールを同一のテーブルを用いて管理することができる。

特開２００６−２０３１７号公報

Ｓｕｍｅｅｔ Ｓｉｎｇｈ、Ｆｌｏｒｉｎ Ｂａｂｏｅｓｃｕ、Ｇｅｏｒｇｅ Ｖａｒｇｈｅｓｅ、Ｊｉａ Ｗａｎｇ、"Ｐａｃｋｅｔ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ Ｕｓｉｎｇ Ｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌ Ｃｕｔｔｉｎｇ"、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ ＳＩＧＣＯＭＭ ２００３ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｐｐｌｉｃａｔｉｏｎｓ、Ｔｅｃｈｎｏｌｏｇｉｅｓ、Ａｒｃｈｉｔｅｃｔｕｒｅｓ、ａｎｄ Ｐｒｏｔｏｃｏｌｓ ｆｏｒ Ｃｏｍｐｕｔｅｒ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、２００３年、ｐｐ．２１３−２２４ Ｗｅｉｒｏｎｇ Ｊｉａｎｇ、 Ｖｉｋｔｏｒ Ｋ． Ｐｒａｓａｎｎａ、"Ｌａｒｇｅ−Ｓｃａｌｅ Ｗｉｒｅ−Ｓｐｅｅｄ Ｐａｃｋｅｔ Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｏｎ ＦＰＧＡｓ"、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＡＣＭ／ＳＩＧＤＡ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙｓ、２００９年、ｐｐ．２１９−２２８ Ｗｅｉｒｏｎｇ Ｊｉａｎｇ、 Ｖｉｋｔｏｒ Ｋ． Ｐｒａｓａｎｎａ、Ｎｏｒｉｏ Ｙａｍａｇａｋｉ、"Ｄｅｃｉｓｉｏｎ Ｆｏｒｅｓｔ： Ａ Ｓｃａｌａｂｌｅ Ａｒｃｈｉｔｅｃｔｕｒｅ ｆｏｒ Ｆｌｅｘｉｂｌｅ Ｆｌｏｗ Ｍａｔｃｈｉｎｇ ｏｎ ＦＰＧＡ"、Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ２０１０ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎ、２０１０年、ｐｐ．３９４−３９９

上記の関連技術に記載されているようなパケット分類器によれば、検索キーに一致するルールの検索が行われる場合に、全ての決定木において検索処理が実行される。しかしながら、このことは、パケット分類器の消費電力の無用な増加を招く。それは、各ノードにおいて領域分割に用いるフィールドは複数の決定木で異なっており、入力された検索キーと一致するルールが存在する可能性が無い決定木においても、検索処理が実行されてしまうからである。検索処理では、必要な情報をメモリから読み出すといった処理が行われるため、パケット分類器の消費電力がいたずらに増加してしまう。

本発明の１つの目的は、パケット分類器において、不要なメモリアクセスの発生を未然に防止し、消費電力を削減することができる技術を提供することにある。

本発明の１つの観点において、パケット分類に用いられるルールを管理するパケット分類器が提供される。各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義される。パケット分類器は、コマンド入力ブロックと、複数のルール比較ブロックとを備える。コマンド入力ブロックは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成する。複数のルール比較ブロックの各々は、１以上のルールを管理し、上記入力コマンドに応じた処理を実行する。複数のルール比較ブロックは、管理下のルールにおける１以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされる。複数のグループのうち、検索キーにマッチするルール、新規ルール、あるいは既存ルールを管理する可能性があるグループは、選択グループである。選択グループに属するルール比較ブロックは、選択ルール比較ブロックである。コマンド入力ブロックは、検索キー、新規ルール、あるいは既存ルールを参照することによって、選択ルール比較ブロックにだけ入力コマンドを入力する。

本発明の他の観点において、パケット分類に用いられるルールを管理するパケット分類器によるパケット分類方法が提供される。各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義される。本発明に係るパケット分類方法は、（Ａ）パケット分類器が、複数のルール比較ブロックを提供するステップ、を含む。ここで、複数のルール比較ブロックの各々は、１以上のルールを管理し、入力コマンドに応じた処理を実行するように構成される。入力コマンドは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドである。複数のルール比較ブロックは、管理下のルールにおける１以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けさる。複数のグループのうち、検索キーにマッチするルール、新規ルール、あるいは既存ルールを管理する可能性があるグループは、選択グループである。選択グループに属するルール比較ブロックは、選択ルール比較ブロックである。本発明に係るパケット分類方法は、更に、（Ｂ）検索キー、新規ルール、あるいは既存ルールを参照することによって、選択ルール比較ブロックにだけ入力コマンドを入力するステップと、（Ｃ）選択ルール比較ブロックにおいて、入力コマンドに応じた処理を実行するステップと、を含む。

本発明の更に他の観点において、コンピュータによって実行され、当該コンピュータを、パケット分類に用いられるルールを管理するパケット分類器として機能させるパケット分類プログラムが提供される。各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義される。パケット分類器は、コマンド入力ブロックと、複数のルール比較ブロックとを備える。コマンド入力ブロックは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成する。複数のルール比較ブロックの各々は、１以上のルールを管理し、上記入力コマンドに応じた処理を実行する。複数のルール比較ブロックは、管理下のルールにおける１以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされる。複数のグループのうち、検索キーにマッチするルール、新規ルール、あるいは既存ルールを管理する可能性があるグループは、選択グループである。選択グループに属するルール比較ブロックは、選択ルール比較ブロックである。コマンド入力ブロックは、検索キー、新規ルール、あるいは既存ルールを参照することによって、選択ルール比較ブロックにだけ入力コマンドを入力する。

本発明によれば、パケット分類器において、不要なメモリアクセスの発生を未然に防止し、消費電力を削減することが可能となる。

図１は、ルールセットの一例を示す概念図である。 図２は、図１で示されたルールセットがフィールドＸ、Ｙの２軸から成る２次元空間上に配置された場合を示す概念図である。 図３は、図１で示されたルールセットに対する決定木の一例を示す概念図である。 図４は、本発明の第１の実施の形態に係るパケット分類器の構成を示すブロック図である。 図５は、第１の実施の形態に係るパケット分類器の各ルール比較ブロックが管理するルールの概念図である。 図６は、第１の実施の形態に係るパケット分類器の各ルール比較ブロックが決定木で実現される場合の構成を示すブロック図である。 図７は、第１の実施の形態における決定木ノード処理ブロックと決定木の各ノードとの対応関係を示す概念図である。 図８は、第１の実施の形態に係る決定木処理ブロックの決定木ノード処理ブロックの構成を示すブロック図である。 図９は、第１の実施の形態に係る決定木処理ブロックのエントリ数カウントブロックの構成を示すブロック図である。 図１０は、第１の実施の形態におけるルール処理ブロックと決定木の各葉ノードのルールリストに含まれるルールとの対応関係を示す概念図である。 図１１は、第１の実施の形態に係る決定木処理ブロックのルール処理ブロックの構成を示すブロック図である。 図１２は、第１の実施の形態に係るコマンド入力ブロックの構成を示すブロック図である。 図１３は、第１の実施の形態におけるコマンド入力ブロックのコマンド出力情報記憶ブロックが記憶するコマンド出力情報を示す概念図である。 図１４は、第１の実施の形態におけるコマンドの構成例を示す概念図である。 図１５は、第１の実施の形態におけるＬＯＯＫＵＰ処理を示すフローチャートである。 図１６は、ステップＡ２の処理を示すフローチャートである。 図１７は、ステップＢ１の処理を示すフローチャートである。 図１８は、第１の実施の形態におけるノード情報の構成例を示す概念図である。 図１９は、第１の実施の形態におけるアドレス算出方法を説明するための図である。 図２０は、ステップＢ３の処理を示すフローチャートである。 図２１は、第１の実施の形態におけるエントリ情報の構成例を示す概念図である。 図２２は、第１の実施の形態におけるＩＮＳＥＲＴ処理を示すフローチャートである。 図２３は、ステップＡ４の処理を示すフローチャートである。 図２４は、ステップＢ４の処理を示すフローチャートである。 図２５は、ステップＡ５の処理を示すフローチャートである。 図２６は、ステップＡ７の処理を示すフローチャートである。 図２７は、第１の実施の形態におけるＤＥＬＥＴＥ処理を示すフローチャートである。 図２８は、ステップＡ９の処理を示すフローチャートである。 図２９は、ステップＡ１０の処理を示すフローチャートである。 図３０は、ステップＢ８の処理を示すフローチャートである。 図３１は、第１の実施の形態に係るパケット分類器の第２の構成例における各ルール比較ブロックの構成を示すブロック図である。 図３２は、第１の実施の形態の第２の構成例におけるＬＯＯＫＵＰ処理を示すフローチャートである。 図３３は、ステップＡ１２の処理を示すフローチャートである。 図３４は、第１の実施の形態の第２の構成例におけるＩＮＳＥＲＴ処理を示すフローチャートである。 図３５は、ステップＡ１３の処理を示すフローチャートである。 図３６は、第１の実施の形態の第２の構成例におけるＤＥＬＥＴＥ処理を示すフローチャートである。 図３７は、第１の実施の形態の第３の構成例におけるＩＮＳＥＲＴ処理のステップＡ１４の処理を示すフローチャートである。 図３８は、本発明の第２の実施の形態に係るパケット分類器の構成を示すブロック図である。 図３９は、第２の実施の形態に係るコマンド入力ブロックの構成を示すブロック図である。 図４０は、第２の実施の形態におけるコマンド入力ブロックのコマンド出力情報記憶ブロックが記憶するコマンド出力情報を示す概念図である。 図４１は、本発明の第３の実施の形態に係るパケット分類器の構成を示すブロック図である。 図４２は、第３の実施の形態におけるＩＮＳＥＲＴ処理を示すフローチャートである。 図４３は、ステップＡ１５の処理を示すフローチャートである。 図４４は、ステップＡ１８の処理を示すフローチャートである。 図４５は、本発明の第４の実施の形態に係るパケット分類器の構成を示すブロック図である。

添付図面を参照して、本発明の実施の形態を説明する。

１．第１の実施の形態
１−１．概要
図４は、本発明の第１の実施の形態に係るパケット分類器１の構成を示すブロック図である。パケット分類器１は、パケット分類に用いられる複数のルールを管理する。各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義される。更に、本実施の形態に係るパケット分類器１は、入力コマンドに応じて、エントリの動的更新（新規ルールの追加、既存ルールの削除）を自動的に行う。

本実施の形態において、パケット分類器１は、ハードウェア回路により実現される。より詳細には、図４に示されるように、パケット分類器１は、１個以上のルール比較ブロック２（２−１〜２−Ｎ：Ｎは１以上の整数）、エントリ追加対象決定ブロック３、コマンド入力ブロック４、及び結果出力ブロック５を備えている。また、パケット分類器１には入力データ６が入力され、パケット分類器１からは出力データ７が出力される。

入力データ６は、パケット分類器１が実行すべき処理に依存する。パケット分類器１が実行する処理としては、（１）検索キーにマッチするルールを検索する処理（以下、「ＬＯＯＫＵＰ処理」と参照される）、（２）新規ルール（新規エントリ）を追加する処理（以下、「ＩＮＳＥＲＴ処理」と参照される）、及び（３）既存ルール（既存エントリ）を無効化する処理（以下、「ＤＥＬＥＴＥ処理」と参照される）、（４）パケット分類器１に含まれるメモリや設定レジスタ等へ予め設定値を書き込むＣｏｎｆｉｇｕｒａｔｉｏｎ処理、が挙げられる。ここで、Ｃｏｎｆｉｇｕｒａｔｉｏｎ処理は初期化時に行われ、パケット分類器１に含まれる各ブロック内に備えられた設定レジスタやメモリへ構成に関わる値を設定することである。以下では、ＬＯＯＫＵＰ処理、ＩＮＳＥＲＴ処理、ＤＥＬＥＴＥ処理に関してのみ説明する。入力データ６は、処理種別を示す種別データと、当該処理で用いられるデータとを含む。ＬＯＯＫＵＰ処理の場合、入力データ６は、ＬＯＯＫＵＰ処理を示す種別データと、検索キーとを含む。ＩＮＳＥＲＴ処理の場合、入力データ６は、ＩＮＳＥＲＴ処理を示す種別データと、追加すべき新規ルールとを含む。ＤＥＬＥＴＥ処理の場合、入力データ６は、ＤＥＬＥＴＥ処理を示す種別データと、無効化すべき既存ルールとを含む。

コマンド入力ブロック４は、入力データ６を受け取り、その入力データ６に応じた入力コマンドを作成する。入力データ６と同様に、入力コマンドは、処理種別を示す種別データと、当該処理で用いられるデータとを含む。ＬＯＯＫＵＰ処理の実行を指示する検索コマンドは、ＬＯＯＫＵＰ処理を示す種別データと、検索キーとを含む。ＩＮＳＥＲＴ処理の実行を指示する挿入コマンドは、ＩＮＳＥＲＴ処理を示す種別データと、追加すべき新規ルールとを含む。ＤＥＬＥＴＥ処理の実行を指示する削除コマンドは、ＤＥＬＥＴＥ処理を示す種別データと、無効化すべき既存ルールとを含む。

コマンド入力ブロック４は、生成した入力コマンドを、ルール比較ブロック２に入力する。ここで、コマンド入力ブロック４は、入力コマンドを、必ずしも全てのルール比較ブロック２−１〜２−Ｎに入力するわけではなく、複数のルール比較ブロック２−１〜２−Ｎのうち必要なもの（選択ルール比較ブロック）だけに入力する。具体的には、ＬＯＯＫＵＰ処理時には、コマンド入力ブロック４は、検索キーにマッチするルールを管理している可能性があるルール比較ブロック２に対してのみ、入力コマンドを入力する。ＩＮＳＥＲＴ処理時には、コマンド入力ブロック４は、新規ルールを管理する可能性があるルール比較ブロック２に対してのみ、入力コマンドを入力する。ＤＥＬＥＴＥ処理時には、コマンド入力ブロック４は、削除すべき既存ルールを管理している可能性があるルール比較ブロック２に対してのみ、入力コマンドを入力する。より詳細については後述する。

ルール比較ブロック２−１〜２−Ｎは、パケット分類に用いられる複数のルールを、ある方針に従って分散的に管理する。ここでは、単一のルールは、複製が発生しないように、ルール比較ブロック２−１〜２−Ｎのうちいずれか１つによって管理されるとする。例えば、複数のルール比較ブロック２−１〜２−Ｎのそれぞれが、パケット分類に用いられる複数の決定木を構成することが考えられる。この場合、複数の決定木は、非特許文献３に記載されている手法と同様に、ルールの複製が生じないように構成される。つまり、各ルールは、当該ルールの複製が生じない決定木において管理される。言い換えれば、単一のルールは、複数の決定木のうちいずれか１つの決定木における単一の葉ノードでのみ管理される。

各ルール比較ブロック２は、１以上のルールを管理する。そして、各ルール比較ブロック２は、コマンド入力ブロック４から入力された入力コマンドに応じて、ＬＯＯＫＵＰ処理、ＩＮＳＥＲＴ処理、あるいはＤＥＬＥＴＥ処理を実行する。尚、複数のルール比較ブロック２−１〜２−Ｎは、同時並列に各処理を実行することができる。

＜ＬＯＯＫＵＰ処理＞
ルール比較ブロック２は、検索コマンドに応じて、ＬＯＯＫＵＰ処理を実行する。具体的には、ルール比較ブロック２は、自身が管理するルール群に対して、検索キーがいずれかのルールにマッチするか否かを判定する。検索キーにマッチするルール（以下、マッチルールと呼ぶ）が存在する場合、当該ルール比較ブロック２は、当該マッチルールを結果出力ブロック５に通知する。検索キーが複数のルールにマッチする場合、当該ルール比較ブロック２は、複数のマッチルールのうち最も優先度の高いルールを結果出力ブロック５に通知する。一方、検索キーにマッチするルールが存在しない場合、当該ルール比較ブロック２は、マッチルールが存在しなかったことを結果出力ブロック５に通知する。結果出力ブロック５は、各ルール比較ブロック２から検索結果を受け取り、最も優先度の高いマッチルールを選択する。そして、結果出力ブロック５は、その選択結果を示す出力データ７を、ＬＯＯＫＵＰ処理の最終結果として出力する。

＜ＩＮＳＥＲＴ処理＞
ルール比較ブロック２は、挿入コマンドに応じて、ＩＮＳＥＲＴ処理を実行する。具体的には、まず、各ルール比較ブロック２は、新規ルールを自身で管理すべきかを判定する。例えば、ルール比較ブロック２が決定木を用いて構成されている場合、自身の決定木に追加してもルールの複製が発生しないか、つまり、新規ルールが自身の決定木における単一の葉ノードによってのみ管理され得るかどうかを判定する。ルールの複製が発生してしまう場合、当該ルール比較ブロック２は、新規ルールの追加対象とはならない。一方、新規ルールを自身で管理しても良いと判定した場合、当該ルール比較ブロック２は「エントリ追加対象候補」となる。例えば、ルール比較ブロック２が決定木を用いて構成されている場合、新規ルールが自身の決定木における単一の葉ノードによってのみ管理され得ると判定された場合に、当該ルール比較ブロック２は「エントリ追加対象候補」となる。また、この際、当該単一の葉ノードは「追加対象葉ノード」となる。

実際にエントリが追加されるエントリ追加対象のルール比較ブロック２は、上記エントリ追加対象候補の中から選ばれる。そのエントリ追加対象を選ぶのが、エントリ追加対象決定ブロック３である。図４に示されるように、このエントリ追加対象決定ブロック３は、複数のルール比較ブロック２−１〜２−Ｎの各々に接続されている。そして、エントリ追加対象決定ブロック３は、各ルール比較ブロック２から通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。

例えば、各エントリ追加対象候補は、当該ルール比較ブロック２が管理している有効なルールのエントリ数をエントリ追加対象決定ブロック３に通知する。この際、例えば、各エントリ追加対象候補が、ルールを管理するメモリ領域を当該ルール比較ブロック２内でさらに細分化して管理している場合には、新規ルールを追加すべきルール管理エリアで既に管理されている有効なルールのエントリ数を通知しても良い。例えば、ルール比較ブロック２が決定木を用いて構成されている場合、追加対象葉ノードが管理している有効なルールのエントリ数を通知する。そして、エントリ追加対象決定ブロック３は、各エントリ追加対象候補から受け取った有効エントリ数を参照し、所定のポリシーに従って、エントリ追加対象を選択する。例えば、エントリ追加対象決定ブロック３は、当該有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択する。この場合、複数のルール比較ブロック間でのルール数の偏りが抑えられ、好適である。

エントリ追加対象決定ブロック３は、エントリ追加対象の選択結果を各ルール比較ブロック２に通知する。具体的には、エントリ追加対象決定ブロック３は、エントリ追加対象に対して新規ルールの追加を指示し、それ以外の決定木処理ブロック２に対してルール追加処理の不実行を指示する。そして、エントリ追加対象であるルール比較ブロック２は、新規ルールを、自身の管理するルールリストに追加する。

このようにして、ＩＮＳＥＲＴ処理が実行される。結果出力ブロック５は、複数のルール比較ブロック２−１〜２−Ｎから処理結果を受け取り、ＩＮＳＥＲＴ処理の最終結果を示す出力データ７を出力する。

＜ＤＥＬＥＴＥ処理＞
ルール比較ブロック２は、削除コマンドに応じて、ＤＥＬＥＴＥ処理を実行する。具体的には、各ルール比較ブロック２は、削除対象である既存ルールが自身で管理されているか否かを判定する。当該既存ルールが自身で管理されている場合、当該ルール比較ブロック２は「エントリ削除対象」となる。また、ルール比較ブロック２が決定木を用いて構成されている場合、削除対象である既存ルールが管理されている葉ノードは「削除対象葉ノード」となる。エントリ削除対象であるルール比較ブロック２は、当該既存ルールを無効化する。

このようにして、ＤＥＬＥＴＥ処理が実行される。結果出力ブロック５は、複数のルール比較ブロック２−１〜２−Ｎから処理結果を受け取り、ＤＥＬＥＴＥ処理の最終結果を示す出力データ７を出力する。

＜グループ選択処理＞
上述の通り、本実施の形態によれば、コマンド入力ブロック４は、入力コマンドを、複数のルール比較ブロック２−１〜２−Ｎのうち必要なもの（選択ルール比較ブロック）だけに入力する。図５を参照して、この処理について説明する。

本実施の形態によれば、複数のルール比較ブロック２−１〜２−Ｎは、複数のグループにグループ分けされる。ここで、グループ分けの基準は、ルールを管理するために着目するパケットヘッダフィールドの組み合わせの種類である。より具体的に、例えば、各ルール比較ブロック２が決定木によって構成されている場合、それぞれのルール比較ブロック２を構成する決定木の領域分割に用いているヘッダフィールドの組み合わせの種類である。また、それ以外に、ワイルドカードが含まれないパケットヘッダフィールドの組み合わせの種類でも良い。このような管理を行うことで、一般的にルールは全て同じパケットヘッダフィールドの組み合わせで定義されるが、異なる複数の組み合わせで定義されるルールを同一のパケット分類器で管理することも可能となる。

例えば、Ｔｙｐｅフィールドが０ｘ０８００（ＩＰ ｖｅｒｓｉｏｎ４を意味する）の場合、ルールには、送信元ＭＡＣアドレス、宛先ＭＡＣアドレス、ＴｙｐｅといったＬａｙｅｒ２（以下、Ｌ２）までのプロトコルに関するヘッダフィールドに加え、送信元ＩＰアドレス、宛先ＩＰアドレス、プロトコル番号等の上位レイヤのヘッダフィールドが用いられるものとする。尚、各ルールで参照しないフィールドにはワイルドカードが付与されていてもよい。このようなヘッダフィールドの組み合わせを用いて、各ルールを管理するルール比較ブロック２は、第１グループに分類される。図５の例では、第１グループは、ルール比較ブロック２−６〜２−Ｎを含んでいる。

また、Ｔｙｐｅフィールドが０ｘ８１００（ＩＥＥＥ ８０２．１Ｑ ＶＬＡＮタグフレームを意味する）の場合、ルールには、送信元ＭＡＣアドレス、宛先ＭＡＣアドレス、ＴｙｐｅといったＬ２までのプロトコルに関するヘッダフィールドに加え、ＶＬＡＮ ＩＤやＶＬＡＮ ＰｒｉｏｒｉｔｙといったＶＬＡＮまでのヘッダフィールドが用いられるものとする。尚、各ルールで参照しないフィールドにはワイルドカードが付与されていてもよい。このようなヘッダフィールドの組み合わせを用いて、各ルールを管理するルール比較ブロック２は、第２グループに分類される。図５の例では、第２グループは、ルール比較ブロック２−４、２−５を含んでいる。

また、Ｔｙｐｅフィールドが上記のもの以外の場合、ルールには、送信元ＭＡＣアドレス、宛先ＭＡＣアドレス、ＴｙｐｅといったＬ２までのプロトコルに関するヘッダフィールドが用いられるものとする。尚、各ルールで参照しないフィールドにはワイルドカードが付与されていてもよい。この場合、この場合、このようなヘッダフィールドの組み合わせを用いて、各ルールを管理するルール比較ブロック２は、第３グループに分類される。図５の例では、第３グループは、ルール比較ブロック２−１〜２−３を含んでいる。

このように、複数のルール比較ブロック２−１〜２−Ｎは、ルールを管理するために着目するヘッダフィールドの組み合わせの種類に応じて、複数のグループにグループ分けされる。例えば、Ｌ２までのプロトコルに関するヘッダフィールド、送信元ＩＰアドレス、宛先ＩＰアドレス、プロトコル番号等の上位レイヤのヘッダフィールドで定義されたルールが、Ｌ２までのプロトコルに関するヘッダフィールドを用いて管理される場合、第３グループに分類される。同様に、例えば、Ｌ２までのプロトコルに関するヘッダフィールド、ＶＬＡＮ ＩＤやＶＬＡＮ ＰｒｉｏｒｉｔｙといったＶＬＡＮまでのヘッダフィールドで定義されたルールが、Ｌ２までのプロトコルに関するヘッダフィールドを用いて管理される場合も、第３グループに分類される。このような複数のグループのうち入力コマンドが入力されるべきグループは、「選択グループ」である。ＬＯＯＫＵＰ処理の場合、選択グループは、検索キーにマッチするルールを管理している可能性があるグループである。ＩＮＳＥＲＴ処理の場合、選択グループは、新規ルールを管理する可能性があるグループである。ＤＥＬＥＴＥ処理の場合、削除対象の既存ルールを管理している可能性があるグループである。

本実施の形態によれば、コマンド入力ブロック４は、選択グループに属するルール比較ブロック２（以下、「選択ルール比較ブロック２」と参照される）にだけ入力コマンドを入力し、それ以外のルール比較ブロック２には入力コマンドを入力しない。従って、入力コマンドに応じた処理は、選択ルール比較ブロック２においてのみ実行されることになる。その結果、パケット分類器１における不要な電力消費が削減される。

尚、コマンド入力ブロック４は、複数のグループのうちどれが選択グループかを、検索キーやルール（新規ルール、削除ルール）を参照することによって判定可能である。例えば、ＭＡＣヘッダに含まれるＴｙｐｅフィールドや、ＩＰヘッダに含まれるプロトコルフィールド等、パケットの構成が判断できるヘッダフィールドに基づいて、選択グループを識別することができる。図５で示された例では、ＭＡＣヘッダに含まれるＴｙｐｅフィールドがグループ毎に異なっている。従って、コマンド入力ブロック４は、検索キーあるいはルールから抽出されるＴｙｐｅフィールドを「識別情報」として用いることによって、選択グループを識別することができる。

例えば、図５で示された例において、検索キーのＴｙｐｅフィールドが０ｘ８１００である場合、選択グループは第２グループと第３グループであり、コマンド入力ブロック４は、選択ルール比較ブロック２−１〜２−５だけに検索コマンドを入力する。検索キーのＴｙｐｅフィールドが０ｘ０８００である場合、選択グループは第１グループと第３グループであり、コマンド入力ブロック４は、選択ルール比較ブロック２−１〜２−３、２−６〜２−Ｎだけに検索コマンドを入力する。検索キーのＴｙｐｅフィールドがそれ以外の場合、選択グループは第３グループであり、コマンド入力ブロック４は、選択ルール比較ブロック２−１〜２−３だけに検索コマンドを入力する。

以上に説明されたように、本実施の形態によれば、コマンド入力ブロック４は、検索キーやルール（新規ルール、削除ルール）を参照することによって、選択グループを識別する。そして、コマンド入力ブロック４は、選択グループに属する選択ルール比較ブロック２にだけ入力コマンドを入力し、それ以外のルール比較ブロック２には入力コマンドを入力しない。従って、入力コマンドに応じた処理は、選択ルール比較ブロック２においてのみ実行されることになる。その結果、パケット分類器１における不要なメモリアクセスの発生が未然に防止され、消費電力が削減される。

なお、本実施の形態に係るパケット分類器１は、例えば、スイッチやルータ等のネットワーク装置内や、サーバの拡張カードやオンボードで搭載されるＮＩＣ（Ｎｅｔｗｏｒｋ Ｉｎｔｅｒｆａｃｅ Ｃａｒｄ）内に配備される。この場合、パケット分類器１は、制御ブロックと接続される。その制御ブロックは、到着したパケットのヘッダを解析する機能、当該パケットヘッダから検索キーを抽出する機能、その検索キーを用いたＬＯＯＫＵＰ処理をパケット分類器１に実行させる機能を有する。更に、制御ブロックは、外部から指定される新規ルールを追加するＩＮＳＥＲＴ処理をパケット分類器１に実行させる機能、及び外部から指定される既存ルールを削除するＤＥＬＥＴＥ処理をパケット分類器１に実行させる機能を有する。パケット分類器１は、処理に応じた入力データ６を制御ブロックから受け取り、出力データ７を制御ブロックに出力する。

１−２．第１の構成例
次に、本実施の形態に係るパケット分類器１の構成例を更に詳しく説明する。上記のルールの管理ができれば、ルール比較ブロック２はどのようなルール管理機構、及び検索処理を実行しても良い。以下では、典型的な例として、各ルール比較ブロック２が決定木を用いて実現される場合の構成を説明する。

図６は、本実施の形態に係るパケット分類器１の各ルール比較ブロック２の構成を示すブロック図である。以下では、この場合のルール比較ブロックを決定木処理ブロックとも参照する。図６に示されるように、決定木処理ブロック２は、決定木パイプラインブロック２０、エントリ数カウントブロック２１、及びルールパイプラインブロック２２を備えている。コマンド入力ブロック４から決定木処理ブロック２に入力されるデータは、入力データ２３である。決定木処理ブロック２から結果出力ブロック５に出力されるデータは、出力データ２４である。決定木処理ブロック２とエントリ追加対象決定ブロック３との間でやりとりされるデータは、入出力データ２５である。

決定木パイプラインブロック２０は、パイプライン処理により決定木の探索を行う。具体的には、決定木パイプラインブロック２０は、決定木の深さ（段数）Ｈと同じ段数の決定木ノード処理ブロック２００−１〜２００−Ｈを備えている。図７に示されるように、決定木ノード処理ブロック２００−ｉ（ｉ＝１、２、・・・、Ｈ）は、決定木の根ノードから深さｊ（ｊ＝０、１、・・・、Ｈ−１）のノードに対応しており、当該ノードに関する処理を行う。これら決定木ノード処理ブロック２００−１〜２００−Ｈを用いることによって、決定木パイプラインブロック２０は、決定木の根ノードから葉ノードに向けて１ノードずつ探索処理を実行していく。好適には、１クロックサイクル毎に、決定木の１つのノードを辿る処理が実行される。

図８は、本実施の形態に係る決定木ノード処理ブロック２００の構成を示すブロック図である。図８に示されるように、決定木ノード処理ブロック２００は、子ノード決定ブロック２０００及びノード情報記憶ブロック２００１を備えている。

ノード情報記憶ブロック２００１は、メモリやレジスタ等の記憶媒体により構成され、ノード情報を記憶する。ノード情報は、根ノードから見て同じ深さにある全てのノードの各々に関して、当該ノードにおける領域分割情報、つまり当該ノードによって管理される子ノード（分割領域）に対する情報を示す。

決定木ノード処理ブロック２００は、前段の決定木ノード処理ブロック２００から入力データ２００２を受け取る。但し、決定木ノード処理ブロック２００−１は、コマンド入力ブロック４から入力データ２００２（＝入力データ２３）を受け取る。入力データ２００２は、各処理に応じたコマンドと、ノード情報記憶ブロック２００１へのアクセスに用いられるアドレス値を含んでいる。前段の決定木ノード処理ブロック２００からの入力データ２００２は、更に、後述される「有効ビット長」の情報も含んでいる。

子ノード決定ブロック２０００は、入力データ２００２を受け取り、その入力データ２００２で指定されているアドレス値を参照してノード情報記憶ブロック２００１からノード情報を読み出す。そして、子ノード決定ブロック２０００は、ノード情報、有効ビット長及びコマンドに基づいて、当該ノードの子ノードのノード情報が記憶されているアドレス値を算出する。また、子ノード決定ブロック２０００は、有効ビット長を更新する。アドレス値の算出や有効ビット長の更新に関しては、後に詳しく説明される。出力データ２００３は、入力データ２００２に含まれていたコマンド、算出された新しいアドレス値、及び更新後の有効ビット長を含む。子ノード決定ブロック２０００は、その出力データ２００３を、次段の決定木ノード処理ブロック２００に出力する。

最終段の決定木ノード処理ブロック２００−Ｈに関しては、次の通りである。ＬＯＯＫＵＰ処理あるいはＤＥＬＥＴＥ処理の場合、子ノード決定ブロック２０００によって算出されるアドレス値は、ルールパイプラインブロック２２のルール処理ブロック２２０のエントリ記憶ブロック２２０１（後述される）へのアクセスに用いられるアドレス値である。決定木ノード処理ブロック２００−Ｈは、出力データ２００３をルール処理ブロック２２０−１に出力する。また、ＩＮＳＥＲＴ処理の場合、子ノード決定ブロック２０００によって算出されるアドレス値は、エントリ数カウントブロック２１のエントリ数記憶ブロック２１１（後述される）へのアクセスに用いられるアドレス値である。出力データ２００４は、入力データ２００２に含まれていたコマンドと算出されたアドレス値を含む。子ノード決定ブロック２０００は、その出力データ２００４を、エントリ数カウントブロック２１に出力する。

エントリ数カウントブロック２１は、決定木の全ての葉ノードに関して、管理されている有効なルールのエントリ数を葉ノード毎に管理する。尚、エントリ数カウントブロック２１による処理は、決定木の深さＨに相当する処理サイクルにおいて実行される。

図９は、本実施の形態に係るエントリ数カウントブロック２１の構成を示すブロック図である。図９に示されるように、エントリ数カウントブロック２１は、カウント処理ブロック２１０及びエントリ数記憶ブロック２１１を備えている。

エントリ数記憶ブロック２１１は、メモリやレジスタ等の記憶媒体により構成され、エントリ数情報を記憶する。エントリ数情報は、決定木の各葉ノードによって管理されている有効なルールのエントリ数を示す。

ＩＮＳＥＲＴ処理の場合、カウント処理ブロック２１０は、決定木パイプラインブロック２０の決定木ノード処理ブロック２００−Ｈから入力データ２１２（＝上述の出力データ２００４）を受け取る。その入力データ２１２は、挿入コマンド、及びエントリ数記憶ブロック２１１へのアクセスに用いられるアドレス値を含む。カウント処理ブロック２１０は、そのアドレス値を参照して、エントリ数記憶ブロック２１１から追加対象葉ノードに関するエントリ数情報（有効エントリ数）を読み出す。そして、カウント処理ブロック２１０は、読み出した有効エントリ数を示す出力データ２１６を、上述のエントリ追加対象決定ブロック３に出力する。

また、カウント処理ブロック２１０は、エントリ追加対象決定ブロック３から入力データ２１６を受け取る。その入力データ２１６が「決定木への新規ルールの追加」を指定している場合、カウント処理ブロック２１０は、上記追加対象葉ノードに関する有効エントリ数に“１”を加算し、エントリ数記憶ブロック２１１に書き込む。これにより、エントリ数記憶ブロック２１１が最新状態に更新される。更に、カウント処理ブロック２１０は、出力データ２１４を、ルールパイプラインブロック２２のルール処理ブロック２２０−１に出力する。その出力データ２１４は、挿入コマンドと、ルール処理ブロック２２０−１のエントリ記憶ブロック２２０１（後述される）へのアクセスに用いられるアドレス値を含む。

ＤＥＬＥＴＥ処理の場合、カウント処理ブロック２１０は、ルールパイプラインブロック２２のルール処理ブロック２２０−Ｂから入力データ２１３を受け取る。カウント処理ブロック２１０は、その入力データ２１３で指定されるアドレス値を参照して、エントリ数記憶ブロック２１１から削除対象葉ノードに関するエントリ数情報（有効エントリ数）を読み出す。そして、カウント処理ブロック２１０は、当該有効エントリ数から“１”を減算し、エントリ数記憶ブロック２１１に書き込む。これにより、エントリ数記憶ブロック２１１が最新状態に更新される。更に、カウント処理ブロック２１０は、ＤＥＬＥＴＥ処理の完了を示す出力データ２１５を、出力データ２４として結果出力ブロック５に出力する。

ルールパイプラインブロック２２は、パイプライン制御によりルール処理（ＬＯＯＫＵＰ、ＩＮＳＥＲＴ、ＤＥＬＥＴＥ）を行う。具体的には、ルールパイプラインブロック２２は、各葉ノードにおいて管理可能な最大ルール数（ルールリストのサイズ）Ｂと同じ段数のルール処理ブロック２２０−１〜２２０−Ｂを備えている。図１０に示されるように、ルール処理ブロック２２０−ｉ（ｉ＝１、２、・・・、Ｂ）は、当該葉ノードのルールリストに含まれるルールｊ（ｊ＝１、２・・・、Ｂ）に対応付けられており、当該ルールｊに関するルール処理を実行する。これらルール処理ブロック２２０−１〜２２０−Ｂを用いることによって、ルールパイプラインブロック２２は、葉ノードのルールリストに含まれる各ルールに対してルール処理を実行する。好適には、１クロックサイクル毎に、１つのルールに対するルール処理が実行される。

図１１は、本実施の形態に係るルール処理ブロック２２０の構成を示すブロック図である。図１１に示されるように、ルール処理ブロック２２０は、比較更新処理ブロック２２００及びエントリ記憶ブロック２２０１を備えている。

エントリ記憶ブロック２２０１は、メモリやレジスタ等の記憶媒体により構成され、エントリ情報を記憶する。エントリ情報は、当該ルールが有効か無効かを示す有効フラグ、ルールＩＤ、ルール等を含む。

ＬＯＯＫＵＰ処理あるいはＤＥＬＥＴＥ処理の場合、ルール処理ブロック２２０−１は、決定木パイプラインブロック２０の決定木ノード処理ブロック２００−Ｈから入力データ２２０２（＝上述の出力データ２００３）を受け取る。入力データ２２０２は、各処理に応じたコマンドと、エントリ記憶ブロック２２０１へのアクセスに用いられるアドレス値を含んでいる。

ＩＮＳＥＲＴ処理の場合、ルール処理ブロック２２０−１は、エントリ数カウントブロック２１から入力データ２２０３（＝上述の出力データ２１４）を受け取る。入力データ２２０３は、挿入コマンドと、エントリ記憶ブロック２２０１へのアクセスに用いられるアドレス値を含んでいる。入力データ２２０３は、これ以降、上記入力データ２２０２と同様に扱われる。

比較更新処理ブロック２２００は、入力データ２２０２を受け取り、その入力データ２２０２で指定されているアドレス値を参照してエントリ記憶ブロック２２０１からエントリ情報を読み出す。そして、比較更新処理ブロック２２００は、読み出したエントリ情報に基づいて、コマンドに応じたルール処理を実行する。ルール処理の詳細は後述される。また、比較更新処理ブロック２２００は、受け取った入力データ２２０２を出力データ２２０４として、次段のルール処理ブロック２２０に出力する。

ルール処理ブロック２２０−２〜２２０−Ｂの各々は、前段のルール処理ブロック２２０から入力データ２２０２（＝上述の出力データ２２０４）を受け取る。比較更新処理ブロック２２００による処理は、上記と同じである。尚、ＤＥＬＥＴＥ処理の場合、最終段のルール処理ブロック２２０−Ｂの比較更新処理ブロック２２００は、出力データ２２０４の代わりに出力データ２２０５（＝上述の入力データ２１３）をエントリ数カウントブロック２１に出力する。出力データ２２０５の内容は、出力データ２２０４と同じである。

図１２は、本実施の形態に係るパケット分類器１のコマンド入力ブロック４の構成を示すブロック図である。図１２に示されるように、コマンド入力ブロック４は、出力先分析ブロック４０、コマンド出力情報記憶ブロック４１、コマンド出力ブロック４２、及びルール比較ブロック２−１〜２−Ｎのそれぞれへ入力コマンドを出力するための出力４３−１〜４３−Ｎを備えている。

コマンド出力情報記憶ブロック４１は、「識別情報」と「選択ルール比較ブロック」との対応関係を示すコマンド出力情報を保持している。図１３は、そのコマンド出力情報の一例を概念的に示している。「識別情報」は、例えば、ＭＡＣヘッダのＴｙｐｅフィールドである。出力先データはＮビットデータ（Ｎ＝ルール比較ブロック２−１〜２−Ｎの数）であり、それぞれのビットがルール比較ブロック２−１〜２−Ｎと対応付けられている。ビット値が‘０’であれば、当該ルール比較ブロック２は選択ルール比較ブロックではない。一方、ビット値が‘１’であれば、当該ルール比較ブロック２は選択ルール比較ブロックである。つまり、「選択ルール比較ブロック」は、Ｎビットの出力先データの中のビット‘１’で表されている。なお、ＩＮＳＥＲＴ処理時の新規ルールや、ＤＥＬＥＴＥ処理時の削除ルール等では、ルールの定義上、Ｔｙｐｅフィールドといったヘッダフィールドがワイルドカードで定義されていたりする場合がある。その場合には、全てのルール比較ブロック２が選択ルール比較ブロックとなる。

出力先分析ブロック４０は、外部からパケット分類器１に入力された上述の入力データ６を受け取る。出力先分析ブロック４０は、ＬＯＯＫＵＰの場合は検索キー、ＩＮＳＥＲＴの場合は新規ルール、ＤＥＬＥＴＥの場合は削除ルールから、「識別情報」を抽出する。この識別情報は、例えば、ＭＡＣヘッダのＴｙｐｅフィールドである。そして、出力先分析ブロック４０は、抽出された識別情報とコマンド出力情報（図１３）を参照することによって、選択ルール比較ブロック２を認識する。出力先分析ブロック４０は、コマンドと当該処理で用いるデータ、及びコマンド出力先の情報をコマンド出力ブロック４２に出力する。

コマンド出力ブロック４２は、受け取ったコマンド情報に、内部処理で用いるフラグ等のデータを付与したものを、装置内コマンドとする。そして、コマンド出力ブロック４２は、コマンド出力先の情報に従って、その装置内コマンドを選択ルール比較ブロック２に出力する。この際、コマンド出力ブロック４２は、コマンド情報とそのコマンド情報が有効であるかを示すイネーブル信号を各ルール比較ブロック２に出力する方法が考えられる。この場合、コマンド出力ブロック４２は、全てのルール比較ブロック２にコマンド情報を出力しながら、コマンド出力情報記憶ブロック４１から読み出した出力先データの各ビットを、各ルール比較ブロック２に対するイネーブル信号として利用することもできる。

図１４は、装置内コマンドの構成例を示す概念図である。コマンド部分は、処理種別、終了フラグ、及び結果フラグを含んでいる。例えば、２ビットデータである処理種別は、“００”であればＬＯＯＫＵＰ処理、“０１”であればＩＮＳＥＲＴ処理、“１０”であればＤＥＬＥＴＥ処理を示す。終了フラグは、‘０’であれば未終了、‘１’であれば終了を示す。結果フラグは、エントリの追加、削除を行った場合に、‘１’に設定される。尚、終了フラグと結果フラグについては、ＩＮＳＥＲＴ処理及びＤＥＬＥＴＥ処理においてのみ参照され、それらの利用方法については後述する。また、装置内コマンドの後半部分には、検索キー（ＬＯＯＫＵＰ処理）、追加される新規エントリ（ＩＮＳＥＲＴ処理）、あるいは、削除される既存エントリ（ＤＥＬＥＴＥ処理）が格納される。なお、装置内コマンドの構成例はこれに限定されることはない。特に、終了フラグや結果フラグといった内部処理用のデータのビット幅をより多く用いることで、内部の処理状況を柔軟に把握することが可能となる。

ここで、上記新規エントリや削除エントリ等のエントリ（ルール）は、Ｐｒｅｆｉｘ Ｍａｔｃｈ、Ｒａｎｇｅ Ｍａｔｃｈ、Ｗｉｌｄｃａｒｄ Ｍａｔｃｈを考慮すると様々な表現形態が考えられる。例えば、検索キー長と同じ長さのデータ列Ａ、Ｂを用意し、Ｐｒｅｆｉｘ ＭａｔｃｈやＷｉｌｄｃａｒｄ Ｍａｔｃｈの場合には、Ａに対象データ、Ｂにマスクビットデータを割り当て、Ｒａｎｇｅ Ｍａｔｃｈの場合には、Ａに下限値、Ｂに上限値を割り当てる方法が考えられる。この場合、ルールのエントリ長は検索キー長の２倍となる。これらを考慮し、装置内コマンドの後半部分においては、ＬＯＯＫＵＰ処理時の検索キーと、ＩＮＳＥＲＴ、ＤＥＬＥＴＥ処理時の追加・削除エントリの長さが異なることを許容する。なお、追加エントリの場合には、その優先度も指定される。

次に、本実施の形態に係るパケット分類器１の動作を詳しく説明する。

＜ＬＯＯＫＵＰ処理＞
まず、ＬＯＯＫＵＰ処理を説明する。図１５は、本実施の形態におけるＬＯＯＫＵＰ処理を示すフローチャートである。

ステップＡ１：
パケット分類器１に、入力データ６が入力される。その入力データ６は、ＬＯＯＫＵＰ処理を示す種別データと、被検索対象パケットから抽出された検索キーとを含む。コマンド入力ブロック４は、その入力データ６を受け取る。コマンド入力ブロック４は、その入力データ６に基づいて、上述したように選択ルール比較ブロック２を決定し、装置内コマンド（ここでは、検索コマンド）を生成する。そして、コマンド入力ブロック４は、生成した装置内コマンドを、選択ルール比較ブロック２に対して一斉に出力する。

ステップＡ２：
コマンド入力ブロック４から検索コマンドを受け取ると、ルール比較ブロック２は、ルール一致比較処理を実行する。具体的に、ルール比較ブロック２が決定木で実現された決定木処理ブロック２の場合、図１６に示すルール一致比較処理を行う。図１６は、決定木処理ブロック２におけるステップＡ２の処理を示すフローチャートである。

ステップＢ１：
決定木処理ブロック２は、ルール一致比較処理として、指定された検索キーを用いて、自身の決定木を辿る処理を実行する。図１７は、ステップＢ１の処理を示すフローチャートである。

ステップＣ１：
決定木を辿る処理は、決定木の根ノードから開始する。そのため、まず、現在の処理ノードが、決定木の根ノードに設定される。具体的には、挿入コマンドが、決定木パイプラインブロック２０の初段の決定木ノード処理ブロック２００−１に入力される。

ステップＣ２：
子ノード決定ブロック２０００は、処理種別がＬＯＯＫＵＰであることを確認した上で、ノード情報記憶ブロック２００１からノード情報を読み出す。

図１８は、ノード情報の構成例を示す概念図である。ノード情報は、当該ノードにおける領域分割情報である。図１８に示されるように、ノード情報は、フィールド識別子（フィールドＩＤ）とその分割数（ｋ）のＣ個のペア、及びベースアドレスを含んでいる。ここで、Ｃは決定木の１ノードにおける領域分割に用いることができるフィールドの最大数である。フィールドＩＤは、検索キーやルールを構成するフィールド毎に予め決められている。また、各フィールドの範囲は、２^ｋ分割されるとし（ｋは自然数）、分割数ｋはその指数を表す。例えば、既出の図１〜図３の例のように、フィールドＸ、Ｙの各々の範囲が２分割される場合、フィールドＸの分割数ｋは１であり、フィールドＹの分割数ｋも１である。尚、ｋの最大数は予め決められている。ベースアドレスは、当該ノードの子ノードのノード情報が格納されている記憶領域の最小アドレス値を示す。より詳細には、ベースアドレスは、当該ノードの子ノードのノード情報が格納されている次段の決定木ノード処理ブロック２００のノード情報記憶ブロック２００１における最小アドレス値であり、当該ノードの全ての子ノードのノード情報は、このベースアドレスから連続する記憶領域に格納されている。

ステップＣ３：
子ノード決定ブロック２０００は、読み出したノード情報、検索キーの各フィールドのビット列、及び有効ビット長に基づいて、次段の子ノードのノード情報が格納されている記憶領域のアドレス値を算出する。具体的には、次のようにして次段のアドレス値は算出される（図１９も参照されたい）。

例えば、ノード情報として、２つのフィールドに関する分割情報（フィールドＩＤ、分割数）＝（０００１、０１）、（０１００、１１）とベースアドレス＝００００１０００が設定されているとする。検索キーにおいては、フィールドＩＤ＝０００１のフィールド値が“０１０１”、フィールドＩＤ＝０１００のフィールド値が“０１１０”であり、それぞれの有効ビット長が３、４であったとする。ここで、有効ビット長とは、各フィールドのビット列に対し、領域分割に用いる下位ビットからの長さに相当する。つまり、フィールド値のうち、有効ビット長で指定された長さをもつ下位ビットからのビット列が参照される。フィールドＩＤ＝０００１に関して説明する。有効ビット長が３であることから、フィールド値の下位３ビット“１０１”を参照する。そして、分割数ｋ＝１であるため、有効ビットの上位１ビットを参照し、‘１’を得る（図１９参照）。同様に、フィールドＩＤ＝０１００に関しては、有効ビット長が４、分割数ｋが３であることから、“０１１”を得る。これらを連結した“１０１１”に対して、ベースアドレス“００００１０００”が加算される。その結果得られる“０００１００１１”が、次段の子ノードのノード情報が格納されている記憶領域のアドレス値である。

ステップＣ４：
続いて、子ノード決定ブロック２０００は、入力された有効ビット長から分割数ｋを減算することによって、有効ビット長を更新する。上記の例では、フィールドＩＤ＝０００１の有効ビット長が３−１＝２に、フィールドＩＤ＝０１００の有効ビット長が４−３＝１に更新される。尚、決定木ノード処理ブロック２００−１には有効ビット長が入力されないが、その場合の有効ビット長は、予め各フィールドのフィールド長として設定されているものとする。それ以降の決定木ノード処理ブロック２００に対しては、前段の決定木ノード処理ブロック２００から有効ビット長が入力される。

ステップＣ５、Ｃ６：
次に、子ノードが葉ノードであるか否かが判定される。具体的には、決定木ノード処理ブロック２００−Ｈが処理するノードの子ノードが葉ノードであるため（図７参照）、処理する決定木ノード処理ブロック２００が自動的に判別すればよい。

次ノードが葉ノードではない場合（ステップＣ５；Ｎｏ）は、決定木ノード処理ブロック２００−ｉ（ｉ＝１、２、・・・、Ｈ−１）の場合に相当する。その決定木ノード処理ブロック２００−ｉは、次段の決定木ノード処理ブロック２００−（ｉ＋１）に出力データ２００３を出力する（ステップＣ６）。その出力データ２００３は、入力データ２００２に含まれていたコマンド、算出された新しいアドレス値、及び更新後の有効ビット長を含む。そして、処理はステップＣ２に戻り、次段のノードが処理ノードとなる。

次ノードが葉ノードである場合（ステップＣ５；Ｙｅｓ）は、決定木ノード処理ブロック２００−Ｈの場合に相当する。この場合、ステップＢ１が終了する。

ステップＢ２：
ステップＢ１が終了すると、決定木ノード処理ブロック２００−Ｈは、ルールパイプラインブロック２２のルール処理ブロック２２０−１に、算出したアドレス値とコマンドを含む出力データ２００３を出力する。

ステップＢ３：
続いて、ルールパイプラインブロック２２が、検索キーとルールリスト中の各ルールとの比較（マッチング処理）を行う。図２０は、ステップＢ３の処理を示すフローチャートである。

ステップＤ１：
マッチング処理は、ルールリスト中の１番目のルールから開始する。具体的には、初段のルール処理ブロック２２０−１から処理を開始する。

ステップＤ２：
比較更新処理ブロック２２００は、処理種別がＬＯＯＫＵＰであることを確認した上で、入力されたアドレス値を用いてエントリ記憶ブロック２２０１からエントリ情報を読み出す。そして、比較更新処理ブロック２２００は、有効フラグを確認する。

図２１は、エントリ情報の構成例を示す概念図である。エントリ情報は、当該ルールが有効であるかを示す有効フラグ、ルールＩＤ、ルール、優先度を含んでいる。ルールに対応するアクションを同時に記憶する場合には、アクションを加えても良い。ここでは、アクションは本パケット分類器１とは異なる場所で管理されており、本パケット分類器１によって検索を行った後に、当該ルールＩＤを用いることによりアクションが取得されるとする。なお、図２１のエントリ情報の構成例では、ルールＩＤを含んでいるが、これをエントリ情報には含まず、例えば、処理を行った決定木処理ブロックのＩＤ、葉ノードのＩＤ、ルールリストの順序等からルールＩＤを生成しても良い。より具体的には、処理を行った決定木処理ブロック２−ｉ（ｉ＝１、２、・・・、Ｎ）のｉ、決定木処理ブロック２−ｉで辿り着いた葉ノードのＩＤであるｊ、ルール処理ブロック２２０−ｋ（ｋ＝１、２、・・・、Ｂ）のｋを２進数で連結したものをルールＩＤとして参照することが可能である。

ステップＤ３、Ｄ４：
ルールが有効である場合（ステップＤ３；Ｙｅｓ）、比較更新処理ブロック２２００は、検索キーと読み出したルールとの比較を行う。この比較方法については、例えば、非特許文献２に開示されている。

ステップＤ５、Ｄ６：
検索キーがルールにマッチした場合（ステップＤ５；Ｙｅｓ）、比較更新処理ブロック２２００は、当該ルールの優先度と現在のマッチルールの優先度を比較する。ここで、現在のマッチルールとは、前段のルール処理ブロック２２０までにマッチしたルールのうち、最も優先度が高いルールを意味する。一方、現在のルール処理ブロック２２０において比較に用いられたルールは、比較ルールと参照される。

ステップＤ７、Ｄ８：
比較ルールの優先度の方が大きかった場合（ステップＤ７；Ｙｅｓ）、比較更新処理ブロック２２００は、比較ルールを新たな現在のマッチルールに設定する。その後、処理は、ステップＤ９に進む。

ステップＤ９、Ｄ１０、Ｄ１１：
現在のルールが、ルールリスト中の最後のルールか否かが判定される。具体的には、ルール処理ブロック２２０−ｉ（ｉ＝１、２、・・・、Ｂ−１）が処理を実行している場合、それは最後のルールではない（ステップＤ９；Ｎｏ）。この場合、そのルール処理ブロック２２０−ｉは、次段のルール処理ブロック２２０−（ｉ＋１）に、アドレス値とコマンドを含む出力データ２２０４を出力する（ステップＤ１０）。そして、処理はステップＤ２に戻り、ルールリスト中の次のルールに対するマッチング処理が実行される。

尚、読み出したルールが有効で無い場合（ステップＤ３；Ｎｏ）、及び、検索キーがルールにマッチしない場合（ステップＤ５；Ｎｏ）、更に、比較ルールの優先度がマッチルールの優先度よりも小さかった場合（ステップＤ７；Ｎｏ）にも、処理はステップＤ９に進む。

現在のルールがルールリスト中の最後のルールである場合、つまり、処理がルール処理ブロック２２０−Ｂで行われた場合（ステップＤ９；Ｙｅｓ）、ルール処理ブロック２２０−Ｂは、マッチルールのルールＩＤと優先度、及びコマンドを、結果出力ブロック５に出力する（ステップＤ１１）。そして、ステップＢ３が終了する。なお、マッチルールが存在しない場合には、マッチルールが存在しなかったことを示す信号を出力するが、例えば、ルールＩＤのビット値が全て１であるような特値を出力することで、マッチルールが存在しなかったことを示すこともできる。

ステップＡ３：
結果出力ブロック５は、複数の決定木処理ブロック２−１〜２−Ｎから検索結果を受け取る。結果出力ブロック５は、マッチルールの優先度同士を比較し、最も優先度の高いマッチルールを選択する。そして、結果出力ブロック５は、その選択結果を示す出力データ７として、例えば、最高優先度であったマッチルールのルールＩＤを、ＬＯＯＫＵＰ処理の最終結果として出力する。このとき、マッチルールが存在しなかった場合には、上述した特値のルールＩＤを出力することで、マッチルールが存在しなかったことを示すことができる。

＜ＩＮＳＥＲＴ処理＞
次に、ＩＮＳＥＲＴ処理を説明する。図２２は、本実施の形態におけるＩＮＳＥＲＴ処理を示すフローチャートである。

ステップＡ１：
パケット分類器１に、入力データ６が入力される。その入力データ６は、ＩＮＳＥＲＴ処理を示す種別データと、追加される新規ルールとを含む。コマンド入力ブロック４は、その入力データ６を受け取る。コマンド入力ブロック４は、その入力データ６に基づいて、上述したように選択ルール比較ブロック２を決定し、装置内コマンド（ここでは、検索コマンド）を生成する。そして、コマンド入力ブロック４は、生成した装置内コマンドを、選択ルール比較ブロック２に対して一斉に出力する。

ステップＡ４：
コマンド入力ブロック４から検索コマンドを受け取ると、ルール比較ブロック２は、当該ブロックにおいてルールの複製が発生するかを確認する。具体的には、ルール比較ブロック２が決定木で実現された決定木処理ブロック２の場合、図２３に示すルールの複製有無確認処理を行う。図２３は、決定木処理ブロック２におけるステップＡ４の処理を示すフローチャートである。

ステップＢ４：
コマンド入力ブロック４から挿入コマンドを受け取ると、決定木処理ブロック２は、指定された新規ルールを用いて、自身の決定木を辿る処理を実行する。図２４は、ステップＢ４の処理を示すフローチャートである。

ステップＣ１：
まず、ＬＯＯＫＵＰ処理の場合と同様に、現在の処理ノードが、決定木の根ノードに設定される。

ステップＣ７：
子ノード決定ブロック２０００は、処理種別がＩＮＳＥＲＴであることを確認した上で、コマンド内の終了フラグを参照する。終了フラグが‘１’である場合（ステップＣ７；Ｙｅｓ）、処理はステップＣ５に進む。一方、終了フラグが‘０’である場合（ステップＣ７；Ｎｏ）、処理はステップＣ２に進む。

ステップＣ２：
ＬＯＯＫＵＰ処理の場合と同様に、子ノード決定ブロック２０００は、ノード情報記憶ブロック２００１からノード情報を読み出す。

ステップＣ８：
子ノード決定ブロック２０００は、読み出したノード情報、新規ルールの各フィールドのビット列、及び有効ビット長に基づいて、ルールの複製が発生するか否か判定する。ルールの複製が発生するか否かは、アドレス値の算出を行う際に、ワイルドカードが含まれるか否かで判断することができる。

例えば、ノード情報として、２つのフィールドに対する領域分割情報（フィールドＩＤ、分割数）＝（０００１、０１）、（０１００、１１）とベースアドレス＝００００１０００が設定されていたとする。追加対象ルールにおいては、フィールドＩＤ＝０００１、フィールドＩＤ＝０１００の各フィールドに対して、（フィールド値、マスクビット列）が、（“０１０１”、“１１１１”）、（“０１１０”、“１１１１”）のように設定されており、それぞれの有効ビット長が３、４であったとする。なお、マスクビット列は各ビットが‘１’であれば有効、‘０’であれば無効、つまり、ワイルドカードとして扱うものとする。この場合、両フィールドともに、ワイルドカードは含まれていないため、ルールの複製は発生しないことが分かり、ＬＯＯＫＵＰ時のステップＣ３と同様に、次の子ノードのアドレス値を算出することができる。一方、同様のノード情報、有効ビット長に対して、追加対象ルールにおけるフィールドＩＤ＝０００１、フィールドＩＤ＝０１００の各フィールドの（フィールド値、マスクビット列）が、（“０１０１”、“１１１１”）、（“０１１０”、“１１００”）のように設定されている場合を考える。この場合、マスクビット列を考慮すると、各フィールド値はそれぞれ、“０１０１”、“０１＊＊”となる。ノード情報を元に子ノードのアドレス値を算出しようとすると、それぞれの有効ビット長が３、４であることから、フィールドＩＤ＝０００１に対して、下位３ビット“１０１”の上位１ビットを参照し、‘１’を得る。一方、フィールドＩＤ＝０１００のフィールドに対しては、有効ビット長が４、分割数が３であることから、“０１＊”を得る。この結果、子ノードの分割領域を示すビット列にワイルドカードが含まれ、これは、ルールの複製が発生することを意味する。なお、フィールド値がＲａｎｇｅ Ｍａｔｃｈとして設定されている場合、下限値と上限値の有効ビット長に相当するビット列に対し、参照するビット列が共に同じ値であるか否かで判断できる。例えば、上記の例において、フィールドＩＤ＝０００１が下限値００００、上限値００１１として設定されていたとする。有効ビット長が３であることから、下限値、上限値の下位３ビットの“０００”と“０１１”を参照する。分割数が１であることから、各有効ビット長の先頭ビットを参照し、共に‘０’であることから、領域分割を行ってもルールの複製が発生しないと判断できる。一方、フィールドＩＤ＝０００１が下限値００００、上限値０１１１が設定されている場合には、参照ビットが‘０’と‘１’であるため、ルールの複製が発生すると判断できる。

ステップＣ９、Ｃ１０：
ルールの複製が発生する場合（ステップＣ９；Ｙｅｓ）、当該決定木処理ブロック２は、エントリ追加対象候補とはならない。この場合、子ノード決定ブロック２０００は、コマンドの終了フラグを‘１’に設定する。その後、処理はステップＣ５に進む。

ステップＣ３、Ｃ４：
一方、ルールの複製が発生しない場合（ステップＣ９；Ｎｏ）、ＬＯＯＫＵＰ処理の場合と同様に、次段のアドレス値の算出（ステップＣ３）及び有効ビット長の更新（ステップＣ４）が行われる。その後、処理はステップＣ５に進む。

ステップＣ５、Ｃ６：
ＬＯＯＫＵＰ処理の場合と同様に、ステップＣ５、Ｃ６が実施される。つまり、次ノードが葉ノードではない場合（ステップＣ５；Ｎｏ）は、決定木ノード処理ブロック２００−ｉ（ｉ＝１、２、・・・、Ｈ−１）は、次段の決定木ノード処理ブロック２００−（ｉ＋１）に出力データ２００３を出力する（ステップＣ６）。そして、処理はステップＣ７に戻り、次段のノードが処理ノードとなる。一方、次ノードが葉ノードである場合（ステップＣ５；Ｙｅｓ）は、ステップＢ４が終了する。

ステップＢ５：
ステップＢ４が終了すると、決定木ノード処理ブロック２００−Ｈは、算出したアドレス値とコマンドを含む出力データ２００４を、エントリ数カウントブロック２１に出力する。

ステップＢ６：
エントリ数カウントブロック２１のカウント処理ブロック２１０は、決定木ノード処理ブロック２００−Ｈから入力データ２１２（＝上述の出力データ２００４）を受け取る。カウント処理ブロック２１０は、処理種別がＩＮＳＥＲＴであることを確認した上で、終了フラグを参照する。終了フラグが‘０’の場合、当該決定木処理ブロック２は、エントリ追加対象候補である。この場合、カウント処理ブロック２１０は、入力されたアドレス値を用いて、エントリ数記憶ブロック２１１から追加対象葉ノードに関するエントリ数情報（有効エントリ数）を読み出す。そして、カウント処理ブロック２１０は、読み出した有効エントリ数を示す出力データ２１６を、エントリ追加対象決定ブロック３に出力する。

一方、終了フラグが‘１’の場合、当該決定木処理ブロック２は、エントリ追加対象候補ではない。この場合、カウント処理ブロック２１０は、処理終了信号をエントリ追加対象決定ブロック３に出力する。あるいは、カウント処理ブロック２１０は、有効エントリ数を最大値に設定し、その有効エントリ数をエントリ追加対象決定ブロック３に通知してもよい。

ステップＡ５：
エントリ追加対象決定ブロック３は、決定木処理ブロック２から通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。図２５は、ステップＡ５の処理を示すフローチャートである。

ステップＥ１、Ｅ２、Ｅ３：
エントリ追加対象決定ブロック３は、エントリ追加対象候補から有効エントリ数を示す情報を受け取る（ステップＥ１）。次に、エントリ追加対象決定ブロック３は、有効エントリ数がルールリストの最大数Ｂ（リストサイズ）を下回っているものがあるか否か確認する（ステップＥ２）。有効エントリ数がリストサイズを下回っているものが無い場合（ステップＥ２；Ｎｏ）、エントリ追加対象決定ブロック３は、エントリ追加対象は存在しないと判断する（ステップＥ３）。

ステップＥ４、Ｅ５：
一方、有効エントリ数がリストサイズを下回っているものがある場合（ステップＥ２；Ｙｅｓ）、エントリ追加対象決定ブロック３は、有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択する（ステップＥ４）。その後、エントリ追加対象決定ブロック３は、各決定木処理ブロック２にエントリ追加の可否を通知する（ステップＥ５）。例えば、エントリ追加対象決定ブロック３は、エントリ追加対象に対して新規ルールの追加を指示し、それ以外の決定木処理ブロック２に対してルール追加処理の不実行を指示する。なお、ここでは有効エントリ数が最小であるエントリ追加対象候補をエントリ追加対象として選択しているが、その他のポリシーに従ってエントリ追加対象を選択しても良い。

ステップＡ６：
エントリ追加対象である決定木処理ブロック２のエントリ数カウントブロック２１は、追加対象葉ノードに関する有効エントリ数に“１”を加算し、エントリ数記憶ブロック２１１に書き込む。これにより、エントリ数記憶ブロック２１１が最新状態に更新される。それ以外の決定木処理ブロック２のエントリ数カウントブロック２１は、コマンドの終了フラグを‘１’に設定する。

ステップＡ７：
続いて、ルールパイプラインブロック２２は、ルールの追加処理を行う。図２６は、ステップＡ７の処理を示すフローチャートである。

ステップＤ１２：
各決定木処理ブロック２のエントリ数カウントブロック２１は、アドレス値と挿入コマンドを含む出力データ２１４を、ルールパイプラインブロック２２のルール処理ブロック２２０−１に出力する。

ステップＤ１３：
ルールの追加処理は、ルールリスト中の１番目のルールから開始する。具体的には、初段のルール処理ブロック２２０−１から処理を開始する。

ステップＤ１４：
比較更新処理ブロック２２００は、処理種別がＩＮＳＥＲＴであることを確認した上で、コマンド内の終了フラグを参照する。終了フラグが‘１’である場合（ステップＤ１４；Ｙｅｓ）、処理はステップＤ９に進む。一方、終了フラグが‘０’である場合（ステップＤ１４；Ｎｏ）、処理はステップＤ２に進む。

ステップＤ２：
ＬＯＯＫＵＰ処理の場合と同様に、比較更新処理ブロック２２００は、入力されたアドレス値を用いてエントリ記憶ブロック２２０１からエントリ情報を読み出す。そして、比較更新処理ブロック２２００は、有効フラグを確認する。

ステップＤ３、Ｄ１５：
ルールが有効ではない場合（ステップＤ３；Ｎｏ）、当該エントリ（すなわち、空きエントリ）に新規ルールを書き込むことができる。この場合、比較更新処理ブロック２２００は、エントリ情報中のルール情報を新規ルールのものに書き換え、且つ、有効フラグを‘１’に設定し、エントリ記憶ブロック２２０１に書き込む。さらに、比較更新処理ブロック２２００は、コマンド内の終了フラグを‘１’に設定し、結果フラグを‘１’（追加成功）に設定する。その後、処理はステップＤ９に進む。

ステップＤ１６：
ルールが有効である場合（ステップＤ３；Ｙｅｓ）、当該エントリに新規ルールを書き込むことは許されない。この場合、そのルール処理ブロック２２０−ｉは、次段のルール処理ブロック２２０−（ｉ＋１）に、アドレス値とコマンドを含む出力データ２２０４を出力する。そして、処理はステップＤ１４に戻り、ルールリスト中の次のルールに対する処理が実行される。

ステップＤ９：
ＬＯＯＫＵＰ処理の場合と同様に、現在のルールが、ルールリスト中の最後のルールか否かが判定される。現在のルールが最後のルールではない場合（ステップＤ９；Ｎｏ）、処理は上記ステップＤ１６に進む。一方、最後のルールの場合（ステップＤ９；Ｙｅｓ）、ルール処理ブロック２２０−Ｂは、現在のコマンドを、結果出力ブロック５に出力する（ステップＤ１７）。そして、ステップＡ７が終了する。

ステップＡ８：
結果出力ブロック５は、複数の決定木処理ブロック２−１〜２−Ｎからコマンドを受け取る。結果出力ブロック５は、受け取ったコマンド内の結果フラグを参照して、新規ルールが追加されたか、又は追加されなかったかを確認する。そして、結果出力ブロック５は、その結果を示す出力データ７を、ＩＮＳＥＲＴ処理の最終結果として出力する。

ここで、ＩＮＳＥＲＴ処理の最終結果として、新規ルールを追加した箇所を示すエントリＩＤを出力することが挙げられる。エントリＩＤは、上述したエントリ情報にルールＩＤを含まない場合のルールＩＤ生成手法と同様、エントリ追加対象となった決定木処理ブロックのＩＤ、葉ノードのＩＤ、ルールリスト順序等からエントリＩＤを生成することができる。このとき、新規ルールを追加できる空き領域が無く、新規ルールを追加できなかった場合には、それを示す信号を出力することでルールの追加ができなかったことを示すことができるが、例えば、エントリＩＤを全て‘１’とした特値として出力することで、ルールの追加ができなかったことを示す信号を省くこともできる。また、ＩＮＳＥＲＴ処理では、各々１ビットから成る終了フラグと結果フラグを用いて処理を行ったが、終了フラグのビット幅を増やし、例えば、ルールの複製が発生したことが要因で処理を終了したことや、当該葉ノードのルールリストに空きが無かったことが要因で処理を終了したこと等、処理を終了した要因を表現させることができる。このような終了フラグを参照することで、ＩＮＳＥＲＴ処理の最終結果として、新規ルールを追加できなかった場合にその要因も最終結果として出力することができる。

＜ＤＥＬＥＴＥ処理＞
次に、ＤＥＬＥＴＥ処理を説明する。図２７は、本実施の形態におけるＤＥＬＥＴＥ処理を示すフローチャートである。

ステップＡ１：
パケット分類器１に、入力データ６が入力される。その入力データ６は、ＤＥＬＥＴＥ処理を示す種別データと、削除される既存ルールとを含む。コマンド入力ブロック４は、その入力データ６を受け取る。コマンド入力ブロック４は、その入力データ６に基づいて、上述したように選択ルール比較ブロック２を決定し、装置内コマンド（ここでは、検索コマンド）を生成する。そして、コマンド入力ブロック４は、生成した装置内コマンドを、選択ルール比較ブロック２に対して一斉に出力する。

ステップＡ９：
コマンド入力ブロック４から削除コマンドを受け取ると、各ルール比較ブロック２は、当該ブロックにおいてルールの複製が発生するかを確認する。具体的には、ルール比較ブロック２が決定木で実現された決定木処理ブロック２の場合、図２８に示すルールの複製有無確認処理を行う。図２８は、決定木処理ブロック２におけるステップＡ９の処理を示すフローチャートである。

ステップＢ４：
ＩＮＳＥＲＴ処理時と同様、コマンド入力ブロック４から削除コマンドを受け取ると、決定木処理ブロック２は、指定された削除ルールを用いて、自身の決定木を辿る処理を実行する。

ステップＢ７：
ステップＢ４が終了すると、決定木ノード処理ブロック２００−Ｈは、ルールパイプラインブロック２２のルール処理ブロック２２０−１に、算出したアドレス値とコマンドを含む出力データ２００３を出力し、ステップＡ９を終了する。

ステップＡ１０：
ルールパイプラインブロック２２は、ルールの削除処理を行う。図２９は、ステップＡ１０の処理を示すフローチャートである。

ステップＢ８：
ルールパイプラインブロック２２は、ルールの削除処理として、対象エントリの削除を行う。図３０は、ステップＢ８の処理を示すフローチャートである。

ステップＤ１：
ステップＢ８は、ルールリスト中の１番目のルールから開始する。具体的には、初段のルール処理ブロック２２０−１から処理を開始する。

ステップＤ１８：
比較更新処理ブロック２２００は、処理種別がＤＥＬＥＴＥであることを確認した上で、コマンド内の終了フラグを参照する。終了フラグが‘１’である場合（ステップＤ１８；Ｙｅｓ）、処理はステップＤ９に進む。一方、終了フラグが‘０’である場合（ステップＤ１８；Ｎｏ）、処理はステップＤ２に進む。

ステップＤ２、Ｄ３：
ＬＯＯＫＵＰ処理の場合と同様に、比較更新処理ブロック２２００は、入力されたアドレス値を用いてエントリ記憶ブロック２２０１からエントリ情報を読み出す。そして、比較更新処理ブロック２２００は、有効フラグを確認する。ルールが無効である場合（ステップＤ３：Ｎｏ）、当該エントリは削除対象ではない。この場合、処理はステップＤ９に進む。一方、ルールが有効である場合（ステップＤ３；Ｙｅｓ）、処理はステップＤ１９に進む。

ステップＤ１９：
比較更新処理ブロック２２００は、読み出したルールと、削除対象として指定されたルールとを比較する。つまり、比較更新処理ブロック２２００は、削除対象として指定されているルールが、読み出したルールにマッチするか否かを判定する。ここでは、両者が完全に一致するか否かが判定される。不一致の場合（ステップＤ５；Ｎｏ）、処理はステップＤ９に進む。一方、完全一致の場合（ステップＤ５；Ｙｅｓ）、処理はステップＤ２０に進む。

ステップＤ２０：
比較更新処理ブロック２２００は、エントリ情報中の有効フラグを‘０’に設定し、エントリ記憶ブロック２２０１に書き込む。これにより、当該エントリ（ルール）は無効化される。この処理が既存ルールの削除に相当する。更に、比較更新処理ブロック２２００は、コマンド内の終了フラグを‘１’に設定し、結果フラグを‘１’（削除成功）に設定する。その後、処理はステップＤ９に進む。

ステップＤ９、Ｄ１６：
ＬＯＯＫＵＰ処理の場合と同様に、現在のルールが、ルールリスト中の最後のルールか否かが判定される。現在のルールが最後のルールではない場合（ステップＤ９；Ｎｏ）、ルール処理ブロック２２０−ｉは、次段のルール処理ブロック２２０−（ｉ＋１）に、アドレス値とコマンドを含む出力データ２２０４を出力する（ステップＤ１６）。そして、処理はステップＤ１８に戻り、ルールリスト中の次のルールに対する処理が実行される。一方、現在のルールがルールリスト中の最後のルールである場合（ステップＤ９；Ｙｅｓ）、ステップＢ８は終了する。

ステップＢ９：
ステップＢ８が完了すると、ルール処理ブロック２２０−Ｂは、アドレス値とコマンドを含む出力データ２２０５を、エントリ数カウントブロック２１に出力する。

ステップＢ１０：
エントリ数カウントブロック２１のカウント処理ブロック２１０は、ルール処理ブロック２２０−Ｂから入力データ２１３（＝上述の出力データ２００５）を受け取る。カウント処理ブロック２１０は、処理種別がＤＥＬＥＴＥであることを確認した上で、終了フラグ及び結果フラグを参照する。終了フラグ及び結果フラグが共に‘１’である場合、カウント処理ブロック２１０は、入力されたアドレス値を用いて、エントリ数記憶ブロック２１１から削除対象葉ノードに関するエントリ数情報（有効エントリ数）を読み出す。そして、カウント処理ブロック２１０は、当該有効エントリ数から１を減算し、エントリ数記憶ブロック２１１に書き込む。これにより、エントリ数記憶ブロック２１１が最新状態に更新される。

ステップＡ１１：
最後に、カウント処理ブロック２１０は、コマンドを含む出力データ２１５を結果出力ブロック５に出力する。結果出力ブロック５は、決定木処理ブロック２−１〜２−Ｎのそれぞれから受け取ったコマンド内の結果フラグを参照して、ルールが削除されたか、又は削除されなかったかを確認する。そして、結果出力ブロック５は、その結果を示す出力データ７を、ＤＥＬＥＴＥ処理の最終結果として出力する。

ここで、ＤＥＬＥＴＥ処理の最終結果として、ＩＮＳＥＲＴ処理時の新規ルール追加箇所のエントリＩＤと同様、削除ルールを追加した箇所を示すエントリＩＤを出力することが挙げられる。この際、削除ルールが何らかの理由で管理ルールに存在しなかった場合には、削除ルールが存在しなかったことを示す信号や、エントリＩＤを全て‘１’とした特値として出力することで、削除ルールが存在しなかったことを示すことができる。

１−３．第２の構成例
次に、本実施の形態に係るパケット分類器１の第２の構成例を説明する。第２の構成例では、各ルール比較ブロック２が、決定木ではなく、リスト形式でルールを管理する。それ以外の構成は第１の構成例と同じであり、重複する説明は適宜省略される。

図３１は、第２の構成例における各ルール比較ブロック２の構成を示すブロック図である。以下では、この場合のルール比較ブロック２をリニアサーチブロックとも参照する。図３１に示されるように、リニアサーチブロック２は、エントリ数カウントブロック２１及びルールパイプラインブロック２２を備えている。つまり、リニアサーチブロック２は、図６で示された決定木処理ブロック２から決定木パイプラインブロック２０が省かれた構成を有している。コマンド入力ブロック４からリニアサーチブロック２に入力されるデータは、入力データ２３である。リニアサーチブロック２から結果出力ブロック５に出力されるデータは、出力データ２４である。リニアサーチブロック２とエントリ追加対象決定ブロック３との間でやりとりされるデータは、入出力データ２５である。

エントリ数カウントブロック２１の構成は、図９で示されたものと同一であるため詳細な説明を省略する。但し、エントリ数記憶ブロック２１１には、決定木の各葉ノードによって管理されている有効なルールのエントリ数ではなく、当該リニアサーチブロック２で管理されている有効なルールのエントリ数を保持している。ここで、後述するが、リニアサーチブロック２のルールパイプラインブロック２２内の各ルール処理ブロック２２０は、１つのルールを保持する。従って、ルールリストはＢ個のルールをリスト（ルール処理ブロック２２０）で接続した構成になるため、このルールリストに含まれる有効なルールのエントリ数としては１つの値を保持すれば良い。なお、各ルール処理ブロック２２０において、複数のルールを管理することで、１つのリニアサーチブロック２で複数のルールリストを管理するように見せることも可能であるが、それらは１つのルールリストを管理するリニアサーチブロック２が複数存在する場合と何ら変わりない。このため、以降では、各リニアサーチブロック２は１つのルールリストのみを管理することを前提とする。

ルールパイプラインブロック２２の構成及びルール処理ブロック２２０の構成も、第１の構成例の場合と同じである。但し、上述したように、エントリ記憶ブロック２２０１では、１つのルールのみが管理される。

上述したように、エントリ数カウントブロック２１のエントリ数記憶ブロック２１１、及びルール処理ブロック２２０のエントリ記憶ブロック２２０１は、第１の構成例とは異なり、１つの有効エントリ数、及び１つのルールのみを管理できれば良い。このため、メモリで実現することも可能ではあるが、ワード数等の制約により記憶媒体が無駄になるような場合には、レジスタで実現することが望ましい。

なお、本構成の場合も第１の構成例と同様に、例えば、ＭＡＣヘッダのＴｙｐｅフィールドの値によって、装置内コマンドの出力先を決定することになる。

次に、本構成におけるパケット分類器１の動作について説明する。但し、以下では、第１の構成例における動作と異なる点のみを説明し、同じ動作を行う点については詳細な説明を省略する。

＜ＬＯＯＫＵＰ処理＞
まず、ＬＯＯＫＵＰ処理を説明する。図３２は、第２の構成例におけるＬＯＯＫＵＰ処理を示すフローチャートである。図３２を参照すると、第２の構成例におけるＬＯＯＫＵＰ処理は、第１の構成例の動作におけるステップＡ２がステップＡ１２に置き換わったものである。その他の動作は全て第１の構成例における動作と変わりないため、詳細な説明を省略する。

ステップＡ１２：
コマンド入力ブロック４から検索コマンドを受け取るとルール比較ブロック２は、ルール一致比較処理を実行する。図３３は、リニアサーチブロック２におけるステップＡ１２の処理を示すフローチャートである。

図３３を参照すると、ステップＡ１２は、第１の構成例におけるステップＢ３を実行することが分かる。本構成例では、ルール比較ブロック２が単一のルールリストで構成されるため、ＬＯＯＫＵＰ処理時には、直接先頭のルール処理ブロック２２０−１から順に検索キーとルールとの比較処理を実行していけば良い。また、第１の構成例における動作時と異なり、決定木を辿る際のアドレス計算等も不要である。本構成例におけるＬＯＯＫＵＰ処理時では、アドレスは明示的に指定可能である。

＜ＩＮＳＥＲＴ処理＞
次に、ＩＮＳＥＲＴ処理を説明する。図３４は、第２の構成例におけるＩＮＳＥＲＴ処理を示すフローチャートである。図３４を参照すると、第２の構成例におけるＩＮＳＥＲＴ処理は、第１の構成例の動作におけるステップＡ４がステップＡ１３に置き換わったものである。その他の動作は全て第１の構成例における動作と変わりないため、詳細な説明を省略する。

ステップＡ１３：
コマンド入力ブロック４からＩＮＳＥＲＴコマンドを受け取ると、ルール比較ブロック２は、当該ブロックにおいてルールの複製が発生するかを確認する。本構成例の場合、ルール比較ブロックは決定木で構成されていないため、ルールの複製は発生しない。このため、図３５に示すルールの複製有無確認処理を行う。図３５は、リニアサーチブロック２におけるステップＡ１３の処理を示すフローチャートである。

ステップＢ１１：
エントリ数カウントブロック２１のカウント処理ブロック２１０は、コマンド入力ブロック４からコマンドを受け取る。カウント処理ブロック２１０は、エントリ数記憶ブロック２１１から当該リニアサーチブロック２の有効エントリ数を読み出す。そして、カウント処理ブロック２１０は、読み出した有効エントリ数を示す出力データ２１６を、エントリ追加対象決定ブロック３に出力する。

本ステップ以降は、第１の構成例と同様の動作であるため、詳細な説明は省略する。

＜ＤＥＬＥＴＥ処理＞
次に、ＤＥＬＥＴＥ処理を説明する。図３６は、第２の構成例におけるＤＥＬＥＴＥ処理を示すフローチャートである。図３６を参照すると、第２の構成例におけるＤＥＬＥＴＥ処理は、第１の構成例の動作におけるステップＡ９が除かれたものである。その他の動作は全て第１の構成例における動作と変わりないため、詳細な説明を省略する。

１−４．第３の構成例
次に、本実施の形態に係るパケット分類器１の第３の構成例について説明する。第３の構成例では、第１の構成例におけるルール比較ブロック２（決定木処理ブロック２）と、第２の構成例におけるルール比較ブロック２（リニアサーチブロック２）が混在する。この場合、ルール比較ブロック２−１〜２−ＮにおけるＭ個が第１の構成例におけるルール比較ブロック２（決定木処理ブロック２）であり、残りＮ−Ｍ個が第２の構成例におけるルール比較ブロック２（リニアサーチブロック２）である。

但し、本実施の形態に係るパケット分類器１は、パイプライン処理によるハードウェア実装を想定している。そのため、第１の構成におけるルール比較ブロック２のパイプライン段数と、第２の構成におけるルール比較ブロック２のパイプライン段数を合わせておいた方がより効率的である。第１の構成におけるルール比較ブロック２は、Ｈ個の決定木ノード処理ブロック２００と、１個のエントリ数カウントブロック２１、Ｂ個のルール処理ブロック２２０を備えている。一方、第２の構成におけるルール比較ブロック２は、１個のエントリカウントブロック２１と、Ｂ個のルール処理ブロック２２０を備えている。例えばＬＯＯＫＵＰ処理の場合、第１の構成におけるルール比較ブロック２のパイプライン段数がＨ＋Ｂ段になるのに対し、第２の構成におけるルール比較ブロック２のパイプライン段数はＢ段となる。この不一致を防ぐため、第３の構成においては、第２の構成におけるルール比較ブロック２を用いる際には、Ｈ＋Ｂ個のルール処理ブロック２２０を備えることが望ましい。これにより、ＬＯＯＫＵＰ処理を基準として考えた場合に、パイプライン段数が一致することになり、より効率的な処理が可能となる。

上記以外の構成については、第１、第２の構成例と同様であるため、詳細な説明は省略する。

次に、本構成におけるパケット分類器１の動作について説明する。但し、ＬＯＯＫＵＰ処理、ＤＥＬＥＴＥ処理については、各ルール処理ブロック２において、第１の構成における動作、あるいは、第２の構成における動作を実行すれば良いため、詳細な説明を省略する。以下では、より効率的なルール管理が可能となるよう、ＩＮＳＥＲＴ処理における動作について説明する。

＜ＩＮＳＥＲＴ処理＞
第３の構成例におけるＩＮＳＥＲＴ処理は、第１及び第２の構成例の動作とほぼ同様である。ルール比較ブロック２、エントリ追加対象決定ブロック３以外のブロックについては、全く変わりはないため、詳細な説明を省略する。

ルール比較ブロック２は、その構成が第１の構成例におけるルール比較ブロック２である場合、第１の構成例における動作を実行する。ルール比較ブロック２は、その構成が第２の構成例におけるルール比較ブロック２である場合、第２の構成例における動作を実行する。

第３の構成例におけるＩＮＳＥＲＴ処理においては、上記の第１及び第２の構成例におけるステップＡ５（エントリ追加対象のルール比較ブロック２を決定する処理）が、次に説明されるステップＡ１４に置き換えられる。

ステップＡ１４：
エントリ追加対象決定ブロック３は、ルール比較ブロック２から通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。図３７は、ステップＡ１４の処理を示すフローチャートである。

ステップＥ１、Ｅ６：
エントリ追加対象決定ブロック３は、エントリ追加対象候補から有効エントリ数を示す情報を受け取る（ステップＥ１）。次に、エントリ追加対象決定ブロック３は、第１の構成例のルール比較ブロック２のうち、有効エントリ数がルールリストの最大数Ｂ（リストサイズ）を下回っているものがあるか否か確認する（ステップＥ６）。有効エントリ数がリストサイズを下回っているものが無い場合（ステップＥ６；Ｎｏ）、処理はステップＥ８に進む。一方、有効エントリ数がリストサイズを下回っているものが有る場合（ステップＥ６；Ｙｅｓ）、処理はステップＥ７に進む。

ステップＥ７：
エントリ追加対象決定ブロック３は、第１の構成例のルール比較ブロック２のうち、有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択する。その後、処理は、ステップＥ５に進む。

ステップＥ８：
エントリ追加対象決定ブロック３は、第２の構成例を用いているルール比較ブロック２のうち、有効エントリ数がルールリストの最大数Ｈ＋Ｂ（リストサイズ）を下回っているものがあるか否か確認する。有効エントリ数がリストサイズを下回っているものが無い場合（ステップＥ８；Ｎｏ）、処理はステップＥ３に進む。一方、有効エントリ数がリストサイズを下回っているものが有る場合（ステップＥ８；Ｙｅｓ）、処理はステップＥ９に進む。

ステップＥ３：
エントリ追加対象決定ブロック３は、エントリを追加できるルール比較ブロック２は存在しないと判断する。その後、処理は、ステップＥ５に進む。

ステップＥ９：
エントリ追加対象決定ブロック３は、第２の構成例のルール比較ブロック２のうち、有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択する。その後、処理は、ステップＥ５に進む。

ステップＥ５：
エントリ追加対象決定ブロック３は、各ルール比較ブロック２にエントリ追加の可否を通知する。例えば、エントリ追加対象決定ブロック３は、エントリ追加対象に対して新規ルールの追加を指示し、それ以外のルール比較ブロック２に対してルール追加処理の不実行を指示する。なお、ここでは有効エントリ数が最小であるエントリ追加対象候補をエントリ追加対象として選択しているが、その他のポリシーに従ってエントリ追加対象を選択しても良い。

本ステップ以降は、第１、第２の構成例と同様の動作であるため、詳細な説明は省略する。

なお、上記の動作からも分かるように、ＩＮＳＥＲＴ処理の場合には、第２の構成例のルール比較ブロック２は、ステップＡ１４を実行するまで、パイプラインが停止した状態になり、ステップＡ１４を実行後にパイプラインが再開する。第１の構成例のルール比較ブロック２は、ステップＡ１４を実行するまでに、既にパイプライン段数としてＨ段を実行し終わっているため、ＩＮＳＥＲＴ処理時にのみ、各ルール比較ブロック２におけるパイプラインの処理タイミングが異なってしまう。しかしながら、第１の構成例のルール比較ブロック２にルールを追加する場合は、第２の構成例のルール比較ブロック２にはルールは決して追加されないため、第２の構成例のルール比較ブロック２のステップＡ１４以降の動作は無視しても良い。一方、第２の構成例のルール比較ブロック２にルールを追加する場合は、第１の構成例のルール比較ブロック２におけるステップＡ１４以降の動作は無視しても良い。どちらの動作を無視しても良いかは、結果出力ブロック５に各ルール比較ブロック２からの処理結果が入力された際に、判断することできる。

また、本構成例におけるＩＮＳＥＲＴ処理では、第１の構成例のルール比較ブロック２にルールを追加することを優先している。これは、第２の構成例のルール比較ブロックは単なるルールリストであるため、有効エントリ数がルールリストに満たない場合、必ずルールを追加することが可能となる。一方、第１の構成例のルール比較ブロック２は、決定木を用いているため、ルールの複製が生じる可能性がある。このため、可能な限り第１の構成例のルール比較ブロック２へのルール追加を優先することによって、効率的なルール管理を実現している。

２．第２の実施の形態
図３８は、本発明の第２の実施の形態に係るパケット分類器８の構成を示すブロック図である。図３８を参照すると、第２の実施の形態におけるパケット分類器８は、第１の実施の形態におけるパケット分類器１におけるコマンド入力ブロック４をコマンド入力ブロック９に、入力データ６を入力データ１０に置き換えたものである。その他の構成は、第１の実施の形態におけるパケット分類器１と同様であるため、詳細な説明は省略する。

図３９は、コマンド入力ブロック９の構成を示すブロック図である。図３９を参照すると、コマンド入力ブロック９は、第１の実施の形態におけるコマンド入力ブロック４における出力先分析ブロック４０を出力先分析ブロック４４に、コマンド出力情報記憶ブロック４１をコマンド出力情報記憶ブロック４５に置き換えたものである。出力先分析ブロック４４には、外部からパケット分類器８への入力データ１０が入力される。本構成の場合、各ルール比較ブロック２においては、ワイルドカードを含むヘッダフィールドの種類によって、装置内コマンドの出力先を決定することになる。

図４０は、コマンド出力情報記憶ブロック４５が記憶するコマンド出力情報を示す概念図である。本実施の形態によれば、「識別情報」は、フィールド分析データである。より詳細には、フィールド分析データは、ルールを構成するヘッダフィールド数と等しいビット幅で構成されており、各ビットが各フィールドと対応付けられている。フィールドにワイルドカードが含まれる場合、当該フィールドに対応づけられたビットは‘０’となる。一方、フィールドにワイルドカードが含まれない場合、当該フィールドに対応付けられたビットは‘１’となる。すなわち、本実施の形態では、「識別情報」は、複数のフィールドのそれぞれがワイルドカードを含んでいるか否かを示す情報である。出力先データは、第１の実施の形態の場合と同じである。

出力先分析ブロック４４は、外部からパケット分類器１に入力された入力データ１０を受け取る。出力先分析ブロック４４は、ＬＯＯＫＵＰの場合は検索キー、ＩＮＳＥＲＴの場合は新規ルール、ＤＥＬＥＴＥの場合は削除ルールから、上記の「識別情報」を抽出する。そして、出力先分析ブロック４４は、抽出された識別情報とコマンド出力情報を参照することによって、選択ルール比較ブロック２を認識する。その他は、第１の実施の形態と同じである。

ここで、新規ルールや削除ルールについては、第１の実施の形態と同様の表現形式で表現することによって、各フィールドにワイルドカードが含まれるか否かを判断することができる。一方、ＬＯＯＫＵＰ時の検索キーの場合は、到着パケットによっては、ルールで定義されたフィールドが存在しない場合が考えられる。これに対応するため、入力データ１０としては、検索キーの各フィールドが定義されていない、すなわち、到着パケットには当該フィールド値が存在しないことを示すための１ビットの信号を用いる。これは、すなわち、コマンド出力情報におけるフィールド分析データと同様のものであり、外部の制御ブロック等で生成されるものとする。

あるいは、ルールの表現形式と同様、マスクビットを用いて検索キーを定義しても構わない。この場合、出力先分析ブロック４４は、入力データ１０として検索キーを受け取った場合、マスクビットを基にフィールド分析データと同様のものを生成する。

その他の構成は、第１の実施の形態におけるコマンド入力ブロック４と同様であるため、詳細な説明は省略する。

尚、第２の実施の形態には、第１の実施の形態におけるパケット分類器１のルール比較ブロック２の３種類の構成例が適用できる。

本実施の形態によれば、第１の実施の形態と同じ効果が得られる。

３．第３の実施の形態
図４１は、本発明の第３の実施の形態に係るパケット分類器１１の構成を示すブロック図である。図４１を参照すると、第３の実施の形態におけるパケット分類器１１は、第１の実施の形態におけるパケット分類器１におけるエントリ追加対象決定ブロック３をエントリ追加対象ブロック１２、結果出力ブロック５を結果出力ブロック１３に置き換え、さらにエントリ追加対象ブロック１２から結果出力ブロック１３へ出力信号を加えたものである。その他の構成は、第１の実施の形態におけるパケット分類器１と同様であるため、詳細な説明は省略する。

尚、第３の実施の形態には、第１の実施の形態におけるパケット分類器１のルール比較ブロック２の３種類の構成例が適用できる。

次に、本実施の形態に係るパケット分類器１１の動作を説明する。

本実施の形態におけるパケット分類器１１の動作は、ＩＮＳＥＲＴ時の動作のみ第１の実施の形態と異なる。このため、以下ではＩＮＳＥＲＴ時の動作において、第１の実施の形態と異なる点のみを説明し、その他については詳細な説明を省略する。なお、ＬＯＯＫＵＰ時の動作、及びＤＥＬＥＴＥ時の動作については、第１の実施の形態における動作と同様であるため、こちらも詳細な説明は省略する。

図４２は、本実施の形態におけるＩＮＳＥＲＴ時の処理を示すフローチャートである。図４２を参照すると、本実施の形態におけるＩＮＳＥＲＴ時の処理は、第１の実施の形態におけるＩＮＳＥＲＴ時の処理（図２２）におけるステップＡ５をステップＡ１５に、ステップＡ８をステップＡ１７に置き換え、ステップＡ１５とステップＡ６の間にステップＡ１６を加えた点が異なる。これ以外の動作については、全て第１の実施の形態におけるＩＮＳＥＲＴ時の処理と同様であるため、以下では、ステップＡ１５、ステップＡ１６、ステップＡ１７の動作について説明する。

ステップＡ１５：
エントリ追加対象決定ブロック１２は、ルール処理ブロック２から通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。図４３は、ステップＡ１５の処理を示すフローチャートである。

ステップＥ１、Ｅ２：
エントリ追加対象決定ブロック１２は、エントリ追加対象候補から有効エントリ数を示す情報を受け取る（ステップＥ１）。次に、エントリ追加対象決定ブロック１２は、各エントリ追加対象候補のうち、有効エントリ数がルールリストの最大数Ｂ（リストサイズ）を下回っているものがあるか否か確認する（ステップＥ２）。有効エントリ数がリストサイズを下回っているものが無い場合（ステップＥ２；Ｎｏ）、処理はステップＥ３に進む。一方、有効エントリ数がリストサイズを下回っているものが有る場合（ステップＥ２；Ｙｅｓ）、処理はステップＥ４に進む。

ステップＥ３、Ｅ１０：
エントリ追加対象決定ブロック１２は、エントリを追加できるルール比較ブロック２は存在しないと判断する（ステップＥ３）。この場合、エントリ追加対象決定ブロック１２は、エントリ追加対象のルール比較ブロック２が存在しなかったことを意味する信号を、結果出力ブロック１３に通知する（ステップＥ１０）。そして、ステップＡ１５の処理は終了する。

ステップＥ４、Ｅ１１：
エントリ追加対象決定ブロック１２は、有効エントリ数がリストサイズを下回っているものの中で、有効エントリ数が最小のものをエントリ追加対象ルール比較ブロックとして決定する（ステップＥ４）。その後、エントリ追加対象決定ブロック１２は、エントリ追加対象ルール比較ブロックにのみ、エントリ追加許可を出力する（ステップＥ１１）。この時、エントリ追加対象以外のルール比較ブロック２には、何ら信号は出力されない。そして、ステップＡ１５の処理は終了する。

ステップＡ１６：
ステップＡ１５において、エントリ追加対象のルール比較ブロック２が存在したかによって以降の処理が異なる。エントリ追加対象のルール比較ブロック２が存在した場合（ステップＡ１６；Ｙｅｓ）、エントリ追加許可を受け取ったエントリ追加対象のルール比較ブロック２は、第１の実施の形態におけるＩＮＳＥＲＴ時の動作と同様に、ステップＡ６、ステップＡ７の処理を実行する。その後、処理はステップＡ１７に進む。一方、エントリ追加対象のルール比較ブロック２が存在しなかった場合（ステップＡ１６；Ｎｏ）、処理はそのままステップＡ１７に進む。

ステップＡ１７：
結果出力ブロック１３がエントリ追加対象のルール比較ブロック２からコマンドを受け取った場合、結果出力ブロック１３は、受け取ったコマンド内の結果フラグを参照して、新規ルールが追加されたか、又は追加されなかったかを確認する。そして、結果出力ブロック１３は、その結果を示す出力データ７を、ＩＮＳＥＲＴ処理の最終結果として出力する。

一方、結果出力ブロック１３がエントリ追加対象決定ブロック１２から、エントリ追加対象のルール比較ブロック２が存在しなかったことを意味する信号を受け取る場合もある（ステップＥ１０）。この場合、結果出力ブロック１３は、新規ルールの追加に失敗したことを示す出力データ７を、ＩＮＳＥＲＴ処理の最終結果として出力する。

なお、第１の実施の形態におけるＩＮＳＥＲＴ処理時の動作と同様、新規ルールを追加できた場合の最終結果として、ルールを追加した箇所を示すエントリＩＤを出力することが挙げられる。エントリＩＤやその他の情報を最終結果として出力する方法については、第１の実施の形態におけるＩＮＳＥＲＴ処理時の動作と同様であるため、説明を省略する。

また、上記では有効エントリ数が最小であるエントリ追加対象候補をエントリ追加対象として選択しているが、その他のポリシーに従ってエントリ追加対象を選択しても良い。

上記では、第１の実施の形態における第１の構成例のＩＮＳＥＲＴ処理に対する変更点を説明した。但し、第１の実施の形態における第２の構成例のＩＮＳＥＲＴ処理に対しても、本実施の形態を適用可能である。具体的には、図３４で示された第２の構成例のＩＮＳＥＲＴ処理において、ステップＡ５をステップＡ１５に、ステップＡ８をステップＡ１７に置き換え、ステップＡ１５とステップＡ６の間にステップＡ１６を加える。

同様に、第１の実施の形態における第３の構成例のＩＮＳＥＲＴ処理に対しても、本実施の形態を適用可能である。この場合は、ステップＡ１４をステップＡ１８に、ステップＡ８をステップＡ１７に置き換え、ステップＡ１８とステップＡ６の間にステップＡ１６を加える。図４４は、ステップＡ１８の処理を示すフローチャートである。上記と同様に、エントリ追加対象のルール比較ブロック２が存在しなかった場合、ステップＥ３の後にステップＥ１０が実行される。一方、エントリ追加対象のルール比較ブロック２として、第１あるいは第２の構成例のルール比較ブロック２が選択された場合、ステップＥ１１が実行される。

また、本実施の形態と第２の実施の形態の組み合わせも可能である。

本実施の形態によれば、既出の実施の形態と同じ効果が得られる。更に、次のような効果も得られる。

第１、第２の実施の形態では、エントリ追加対象のルール比較ブロック２でないブロックに対しても、エントリ追加対象決定ブロック１２からエントリ追加不可の返信がある。この場合、メモリアクセスは行われないが、コマンドだけは順次パイプラインを受け渡されていく。つまり、パイプラインレジスタが起動するため、この電力は消費される。しかし、本実施の形態では、エントリ追加対象のルール比較ブロック２以外のブロックに対しては、何らコマンドを返信しない。従って、エントリ追加対象以外のルール比較ブロック２のパイプラインレジスタは起動しない。よって、その分だけ消費電力を削減することが可能となる。

４．第４の実施の形態
次に、本発明の第４の発明を実施するための最良の形態について図面を参照して詳細に説明する。

図４５は、本発明の第４の実施の形態に係るパケット分類器の構成を示すブロック図である。第４の実施の形態では、コンピュータがソフトウェアプログラムを実行することによりパケット分類処理が実現される。具体的には、本実施の形態に係るパケット分類器は、プログラム処理装置１４とパケット分類プログラム１５を備えている。プログラム処理装置１４は、サーバやＰＣ等のホストのＣＰＵにより実現される。パケット分類プログラム１５は、プログラム処理装置１４によって実行されるコンピュータプログラムであり、プログラム処理装置１４の動作を制御する。プログラム処理装置１４は、パケット分類プログラム１５を実行することにより、既出の実施の形態で説明されたパケット分類器１、あるいは、パケット分類器８、あるいは、パケット分類器１１の機能を備えることができる。

なお、パケット分類プログラム１５は、コンピュータ読み取り可能な記録媒体に記録されていてもよい。

プログラム処理装置１４として、複数のＣＰＵコアを有するマルチコアプロセッサ（さらには、より多くのＣＰＵコアを有するメニーコアプロセッサ）を用いてもよい。その場合、それぞれのＣＰＵコアに、コマンド入力ブロック４、ルール比較ブロック２−１〜２−Ｎ、エントリ追加対象決定ブロック３、結果出力ブロック５、さらには、ルール比較ブロック２を構成する各決定木ノード処理ブロック２００、エントリ数カウントブロック２１、ルール処理ブロック２２０等の処理を実行させることにより、より高速な処理が可能となる。

本実施の形態によれば、既出の実施の形態と同じ効果が得られる。

以上、本発明の実施の形態が添付の図面を参照することにより説明された。但し、本発明は、上述の実施の形態に限定されず、要旨を逸脱しない範囲で当業者により適宜変更され得る。

上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。

（付記１）
パケット分類に用いられるルールを管理するパケット分類器であって、
各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義され、
前記パケット分類器は、
検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成するコマンド入力ブロックと、
各々が１以上のルールを管理し、前記入力コマンドに応じた処理を実行するように構成された複数のルール比較ブロックと
を備え、
前記複数のルール比較ブロックは、管理下のルールにおける前記１以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを入力する
パケット分類器。

（付記２）
付記１に記載のパケット分類器であって、
前記選択グループは、前記検索キー及びルールから抽出される識別情報に基づいて識別可能であり、
前記コマンド入力ブロックは、前記識別情報と前記選択ルール比較ブロックとの対応関係を示すコマンド出力情報を保持し、
前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールから前記識別情報を抽出し、前記抽出された識別情報と前記コマンド出力情報を参照することによって、前記選択ルール比較ブロックを識別する
パケット分類器。

（付記３）
付記２に記載のパケット分類器であって、
前記識別情報は、前記検索キー及びルールに含まれる所定のフィールドの値である
パケット分類器。

（付記４）
付記２に記載のパケット分類器であって、
前記検索キー及びルールは、複数のフィールドを含み、
前記識別情報は、前記複数のフィールドのそれぞれがワイルドカードを含んでいるか否かを示す情報である
パケット分類器。

（付記５）
付記１乃至４のいずれか一項に記載のパケット分類器であって、
前記複数のルール比較ブロックに接続されたエントリ追加対象決定ブロックを更に備え、
単一のルールは、複製が発生しないように、前記複数のルール比較ブロックのうちいずれか１つによって管理され、
前記入力コマンドが前記挿入コマンドである場合、前記選択ルール比較ブロックの各々は、前記新規ルールが自身によって管理され得るかどうかを判定し、
前記新規ルールが自身によって管理され得る場合、当該選択ルール比較ブロックはエントリ追加対象候補であり、
前記エントリ追加対象決定ブロックは、前記新規ルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択し、
前記選択されたエントリ追加対象は、前記新規ルールを、自身が管理するルールリストに追加する
パケット分類器。

（付記６）
付記５に記載のパケット分類器であって、
前記複数のルール比較ブロックは、パケット分類に用いられる複数の決定木のそれぞれを構成し、
単一のルールは、前記複数の決定木のうちいずれか１つの決定木における単一の葉ノードによって管理され、
前記入力コマンドが前記挿入コマンドである場合、前記選択ルール比較ブロックの各々は、前記新規ルールが自身の決定木における単一の葉ノードによって管理され得るかどうかを判定し、
前記新規ルールが単一の葉ノードによって管理され得る場合、当該選択ルール比較ブロックは前記エントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、
前記エントリ追加対象は、前記新規ルールを、自身の決定木における前記追加対象葉ノードが管理するルールリストに追加する
パケット分類器。

（付記７）
付記６に記載のパケット分類器であって、
前記エントリ追加対象候補は、前記追加対象葉ノードが管理している有効なルールのエントリ数を、前記エントリ追加対象決定ブロックに通知し、
前記エントリ追加対象決定ブロックは、前記エントリ数に基づいて、前記エントリ追加対象を選択する
パケット分類器。

（付記８）
付記５に記載のパケット分類器であって、
前記複数のルール比較ブロックの各々は、リスト形式でルールを管理する
パケット分類器。

（付記９）
パケット分類に用いられるルールを管理するパケット分類器によるパケット分類方法であって、
各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義され、
前記パケット分類方法は、
（Ａ）前記パケット分類器が、複数のルール比較ブロックを提供するステップと、
ここで、
前記複数のルール比較ブロックの各々は、１以上のルールを管理し、入力コマンドに応じた処理を実行するように構成され、
前記入力コマンドは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドであり、
前記複数のルール比較ブロックは、管理下のルールにおける前記１以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
（Ｂ）前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを出力するステップと、
（Ｃ）前記選択ルール比較ブロックにおいて、前記入力コマンドに応じた処理を実行するステップと
を含む
パケット分類方法。

（付記１０）
コンピュータによって実行され、前記コンピュータを、パケット分類に用いられるルールを管理するパケット分類器として機能させるパケット分類プログラムであって、
各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義され、
前記パケット分類器は、
検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成するコマンド入力ブロックと、
各々が１以上のルールを管理し、前記入力コマンドに応じた処理を実行するように構成された複数のルール比較ブロックと
を備え、
前記複数のルール比較ブロックは、管理下のルールにおける前記１以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを入力する
パケット分類プログラム。

１ パケット分類器
２ ルール比較ブロック
３ エントリ追加対象決定ブロック
４ コマンド入力ブロック
５ 結果出力ブロック
８ パケット分類器
９ コマンド入力ブロック
１１ パケット分類器
１２ エントリ追加対象決定ブロック
１３ 結果出力ブロック
１４ プログラム処理装置
１５ パケット分類プログラム
２０ 決定木パイプラインブロック
２１ エントリ数カウントブロック
２２ ルールパイプラインブロック
４０ 出力先分析ブロック
４１ コマンド出力情報記憶ブロック
４２ コマンド出力ブロック
４４ 出力先分析ブロック
４５ コマンド出力情報記憶ブロック
２００ 決定木ノード処理ブロック
２１０ カウント処理ブロック
２１１ エントリ数記憶ブロック
２２０ ルール処理ブロック
２０００ 子ノード決定ブロック
２００１ ノード情報記憶ブロック
２２００ 比較更新処理ブロック
２２０１ エントリ記憶ブロック

Claims (10)

1. パケット分類に用いられるルールを管理するパケット分類器であって、
   各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義され、
   前記パケット分類器は、
   検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成するコマンド入力ブロックと、
   各々が１以上のルールを管理し、前記入力コマンドに応じた処理を実行するように構成された複数のルール比較ブロックと
   を備え、
   前記複数のルール比較ブロックは、管理下のルールにおける前記１以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
   前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
   前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
   前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを入力する
   パケット分類器。
2. 請求項１に記載のパケット分類器であって、
   前記選択グループは、前記検索キー及びルールから抽出される識別情報に基づいて識別可能であり、
   前記コマンド入力ブロックは、前記識別情報と前記選択ルール比較ブロックとの対応関係を示すコマンド出力情報を保持し、
   前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールから前記識別情報を抽出し、前記抽出された識別情報と前記コマンド出力情報を参照することによって、前記選択ルール比較ブロックを識別する
   パケット分類器。
3. 請求項２に記載のパケット分類器であって、
   前記識別情報は、前記検索キー及びルールに含まれる所定のフィールドの値である
   パケット分類器。
4. 請求項２に記載のパケット分類器であって、
   前記検索キー及びルールは、複数のフィールドを含み、
   前記識別情報は、前記複数のフィールドのそれぞれがワイルドカードを含んでいるか否かを示す情報である
   パケット分類器。
5. 請求項１乃至４のいずれか一項に記載のパケット分類器であって、
   前記複数のルール比較ブロックに接続されたエントリ追加対象決定ブロックを更に備え、
   単一のルールは、複製が発生しないように、前記複数のルール比較ブロックのうちいずれか１つによって管理され、
   前記入力コマンドが前記挿入コマンドである場合、前記選択ルール比較ブロックの各々は、前記新規ルールが自身によって管理され得るかどうかを判定し、
   前記新規ルールが自身によって管理され得る場合、当該選択ルール比較ブロックはエントリ追加対象候補であり、
   前記エントリ追加対象決定ブロックは、前記新規ルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択し、
   前記選択されたエントリ追加対象は、前記新規ルールを、自身が管理するルールリストに追加する
   パケット分類器。
6. 請求項５に記載のパケット分類器であって、
   前記複数のルール比較ブロックは、パケット分類に用いられる複数の決定木のそれぞれを構成し、
   単一のルールは、前記複数の決定木のうちいずれか１つの決定木における単一の葉ノードによって管理され、
   前記入力コマンドが前記挿入コマンドである場合、前記選択ルール比較ブロックの各々は、前記新規ルールが自身の決定木における単一の葉ノードによって管理され得るかどうかを判定し、
   前記新規ルールが単一の葉ノードによって管理され得る場合、当該選択ルール比較ブロックは前記エントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、
   前記エントリ追加対象は、前記新規ルールを、自身の決定木における前記追加対象葉ノードが管理するルールリストに追加する
   パケット分類器。
7. 請求項６に記載のパケット分類器であって、
   前記エントリ追加対象候補は、前記追加対象葉ノードが管理している有効なルールのエントリ数を、前記エントリ追加対象決定ブロックに通知し、
   前記エントリ追加対象決定ブロックは、前記エントリ数に基づいて、前記エントリ追加対象を選択する
   パケット分類器。
8. 請求項５に記載のパケット分類器であって、
   前記複数のルール比較ブロックの各々は、リスト形式でルールを管理する
   パケット分類器。
9. パケット分類に用いられるルールを管理するパケット分類器によるパケット分類方法であって、
   各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義され、
   前記パケット分類方法は、
   （Ａ）前記パケット分類器が、複数のルール比較ブロックを提供するステップと、
   ここで、
   前記複数のルール比較ブロックの各々は、１以上のルールを管理し、入力コマンドに応じた処理を実行するように構成され、
   前記入力コマンドは、検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドであり、
   前記複数のルール比較ブロックは、管理下のルールにおける前記１以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
   前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
   前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
   （Ｂ）前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを出力するステップと、
   （Ｃ）前記選択ルール比較ブロックにおいて、前記入力コマンドに応じた処理を実行するステップと
   を含む
   パケット分類方法。
10. コンピュータによって実行され、前記コンピュータを、パケット分類に用いられるルールを管理するパケット分類器として機能させるパケット分類プログラムであって、
    各ルールは、パケットヘッダに含まれる１以上のフィールドの組み合わせにより定義され、
    前記パケット分類器は、
    検索キーにマッチするルールの検索を指示する検索コマンド、新規ルールの追加を指示する挿入コマンド、あるいは既存ルールの削除を指示する削除コマンドを入力コマンドとして作成するコマンド入力ブロックと、
    各々が１以上のルールを管理し、前記入力コマンドに応じた処理を実行するように構成された複数のルール比較ブロックと
    を備え、
    前記複数のルール比較ブロックは、管理下のルールにおける前記１以上のフィールドの組み合わせの種類に着目して、複数のグループにグループ分けされ、
    前記複数のグループのうち、前記検索キーにマッチするルール、前記新規ルール、あるいは前記既存ルールを管理する可能性があるグループは、選択グループであり、
    前記選択グループに属するルール比較ブロックは、選択ルール比較ブロックであり、
    前記コマンド入力ブロックは、前記検索キー、前記新規ルール、あるいは前記既存ルールを参照することによって、前記選択ルール比較ブロックにだけ前記入力コマンドを入力する
    パケット分類プログラム。

Images