振り分けポリシーを保持する振り分け処理部と、ルールを2つ以上の部分集合に分類して保持する第1のルール比較部と、ルールを分類せずに保持する第2のルール比較部とを具備し、前記振り分け処理部は、前記振り分けポリシーに従って、入力された検索キーを前記部分集合に振り分け、第1のルール比較部は、該振り分け結果に基づいて、対応する部分集合内のルールと比較して、前記振り分けられた検索キーに一致するルールを出力し、第2のルール比較部は、該振り分け結果に関係なく、保持している全てのルールと比較して、前記入力された検索キーに一致するルールを出力するパケット分類システム。請求項1に記載のパケット分類システムであって、前記振り分け処理部は、複数のノードによる木構造を実現し、前記木構造の根ノードが前記検索キーの入力に対応し、前記木構造の葉ノードが前記部分集合の各々と対応しているパケット分類システム。請求項2に記載のパケット分類システムであって、前記第1のルール比較部は、前記部分集合の各々と1対1に対応する複数のルール比較器を有し、該複数のルール比較器の各々は、直列に並べられたパイプライン構造を実現し、前記振り分けられた検索キーを、保持している部分集合内のルールと比較して、前記振り分けられた検索キーに一致するルールを順次出力するパケット分類システム。請求項3に記載のパケット分類システムであって、前記振り分け処理部は、前記木構造の各段と1対1に対応する複数のノードモジュールを有し、前記複数のノードモジュールの各々は、直列に並べられたパイプライン構造を実現し、パイプライン的に前記検索キーの振り分け処理を行い、最終段のノードモジュールから、前記振り分けられた検索キーを前記第1のルール比較部に入力するパケット分類システム。請求項4に記載のパケット分類システムであって、前記第2のルール比較部は、それぞれがルールを1つ保持する複数のルール比較器を有し、該複数のルール比較器の各々は、直列に並べられたパイプライン構造を実現し、前記入力された検索キーを、保持しているルールと比較して、前記入力された検索キーに一致するルールを順次出力するパケット分類システム。請求項1乃至5のいずれか一項に記載のパケット分類システムであって、ルールのプロファイルを保持する記憶部と、前記振り分け処理部の構成を決定する振り分け処理部構成決定部と、前記第1及び第2のルール比較部の構成を決定するルール比較部構成決定部と、前記決定された構成の評価を行う評価部とを更に具備するパケット分類システム。請求項6に記載のパケット分類システムであって、前記記憶部は、前記ルールのプロファイルの1つとして、ルール中のワイルドカード発生確率を保持し、前記ルール比較部構成決定部は、前記第1及び第2のルール比較部の構成を決定する際に、前記ワイルドカード発生確率を基に、前記第1及び第2のルール比較部に格納するルール数を決定するパケット分類システム。請求項6又は7に記載のパケット分類システムであって、前記記憶部は、前記ルールのプロファイルの1つとして、ルール中のワイルドカード発生確率のバラつきに関する指標を保持し、前記ワイルドカード発生確率のバラつきに関する指標は、正規分布で与えられる場合があり、前記ルール比較部構成決定部は、前記第1及び第2のルール比較部の構成を決定する際に、前記ワイルドカード発生確率のバラつきに関する指標を基に、前記第1及び第2のルール比較部に格納するルール数を決定し、前記ワイルドカード発生確率のバラつきが発生した時のルールのあふれの避止を図るパケット分類システム。計算機により実施されるパケット分類方法であって、振り分けポリシーを保持し、前記振り分けポリシーに従って、入力された検索キーを前記部分集合に振り分けることと、ルールを2つ以上の部分集合に分類して保持し、該振り分け結果に基づいて、対応する部分集合内のルールと比較して、前記振り分けられた検索キーに一致するルールを出力することと、ルールを分類せずに保持し、該振り分け結果に関係なく、保持している全てのルールと比較して、前記入力された検索キーに一致するルールを出力することとを含むパケット分類方法。振り分けポリシーを保持し、前記振り分けポリシーに従って、入力された検索キーを前記部分集合に振り分けるステップと、ルールを2つ以上の部分集合に分類して保持し、該振り分け結果に基づいて、対応する部分集合内のルールと比較して、前記振り分けられた検索キーに一致するルールを出力するステップと、ルールを分類せずに保持し、該振り分け結果に関係なく、保持している全てのルールと比較して、前記入力された検索キーに一致するルールを出力するステップとを計算機に実行させるためのパケット分類用プログラム。決定木を用いたパケット分類器の第1の問題点は、決定木の構成によってはルールの複製が発生することである。ルールの複製によって、パケット分類器に求められる記憶容量が増大し、資源を圧迫することになる。決定木を用いたパケット分類器の第2の問題点は、パケット分類ではパケットが入力されてから、検索結果が出力されるまでの遅延時間は短いほうが望ましいことである。また、パケットは連続して入力されるため、パケット分類器ではパケットが連続して処理できる性能が求められる。決定木を用いたパケット分類器の第3の問題点は、ルールセットに対応した決定木の適切な構成手法が必要である点である。事前に与えられた特定のルールセットを解析することにより得られた構成で、別のルールセットを管理しようとしても、所望の性能が達成できない可能性がある。このように、どのようなルールを管理しなければならないかが、予測できない場合にも、求められる性能が達成できる、決定木を用いたパケット分類器の設計手法が存在しなかった。本発明の目的は、ルールの複製を発生させずにルールを管理することが可能な決定木を用いたパケット分類器と、当該パケット分類器の効果的な設計手法を提供することにある。本発明に係るパケット分類システムは、振り分けポリシーを保持する振り分け処理部と、ルールを2つ以上の部分集合に分類して保持する第1のルール比較部と、ルールを分類せずに保持する第2のルール比較部とを具備する。該振り分け処理部は、該振り分けポリシーに従って、入力された検索キーを該部分集合に振り分ける。第1のルール比較部は、該振り分け結果に基づいて、対応する部分集合内のルールと比較して、該振り分けられた検索キーに一致するルールを出力する。第2のルール比較部は、該振り分け結果に関係なく、保持している全てのルールと比較して、該入力された検索キーに一致するルールを出力する。本発明に係るパケット分類方法は、計算機により実施されるパケット分類方法であって、振り分けポリシーを保持し、該振り分けポリシーに従って、入力された検索キーを該部分集合に振り分けることと、ルールを2つ以上の部分集合に分類して保持し、該振り分け結果に基づいて、対応する部分集合内のルールと比較して、該振り分けられた検索キーに一致するルールを出力することと、ルールを分類せずに保持し、該振り分け結果に関係なく、保持している全てのルールと比較して、該入力された検索キーに一致するルールを出力することとを含む。本発明に係るパケット分類用プログラムは、振り分けポリシーを保持し、該振り分けポリシーに従って、入力された検索キーを該部分集合に振り分けるステップと、ルールを2つ以上の部分集合に分類して保持し、該振り分け結果に基づいて、対応する部分集合内のルールと比較して、該振り分けられた検索キーに一致するルールを出力するステップと、ルールを分類せずに保持し、該振り分け結果に関係なく、保持している全てのルールと比較して、該入力された検索キーに一致するルールを出力するステップとを計算機に実行させるためのプログラムである。本発明に係るパケット分類用プログラムは、上記のパケット分類方法における処理を、計算機に実行させるためのプログラムである。なお、本発明に係るパケット分類用プログラムは、記憶装置や記憶媒体に格納することが可能である。パケットを分類するためのルールを検索するパケット分類器を実現できる。<第1実施形態>以下に、本発明の第1実施形態について添付図面を参照して説明する。[パケット分類器の構成例]図1を参照して、本発明の第1実施形態におけるパケット分類器1の構成例について説明する。パケット分類器1は、入力10を受け取る。入力10は、外部からパケット分類器1への入力である。ここでは、パケット分類器1には、入力10として、パケット分類器1において検索を行うための検索キーが入力される。パケット分類器1は、振り分け処理部11と、第1のルール比較部12と、第2のルール比較部13を備えている。振り分け処理部11は、入力10を受け取る。振り分け処理部11は、第1のルール比較部12と接続されており、第1のルール比較部12に、振り分けの結果、及び検索キーを送る出力する。第1のルール比較部12は、振り分け処理部11における振り分けの結果、及び検索キーを受け取り、検索結果を出力する。このとき、第1のルール比較部12は、振り分け処理部11から振り分けの結果のみを受け取り、検索キーについては、直接入力10から受け取っても良い。なお、検索結果の例として、検索キーと一致したルール、該ルールを一意に識別できるルールID、複数のルールに一致した場合に選択すべきルールの順番を示す優先度等が考えられる。第2のルール比較部13は、入力10を受け取り、検索結果を出力する。出力14は、パケット分類器1からの出力である。ここでは、パケット分類器1は、出力14として、第1のルール比較部12及び第2のルール比較部13での検索結果を出力する。[ハードウェアの例示]本発明に係るパケット分類器の例として、オープンフロースイッチ等のネットワークスイッチnetworkswitchを想定している。他にも、ルータrouter、プロキシproxy、ゲートウェイgateway、ファイアウォール、ロードバランサー、帯域制御装置、セキュリティ監視制御装置、基地局、アクセスポイント等の他の中継装置や、PCパソコン、アプライアンスappliance、ワークステーション、メインフレーム、スーパーコンピュータ等の計算機等が考えられる。なお、計算機は、複数の通信ポートを有する場合、中継装置としての機能を持たせることも可能である。或いは、上記の各装置の組み合わせでも良い。また、パケット分類器は、計算機等に搭載される拡張ボードや、物理マシン上に構築された仮想マシンVirtualMachineVMにより実現される仮想スイッチ等でも良い。本発明に係る振り分け処理部、第1のルール比較部、及び第2のルール比較部、その他の構成要素は、プログラムに基づいて駆動し所定の処理を実行するプロセッサと、当該プログラムや各種データを記憶するメモリと、ネットワークとの通信に用いられるインタフェースによって実現される。上記のプロセッサの例として、CPUCentralProcessingUnit、マイクロプロセッサmicroprocessor、マイクロコントローラ、或いは、専用の機能を有する半導体集積回路IntegratedCircuitIC等が考えられる。上記のメモリの例として、RAMRandomAccessMemory、ROMReadOnlyMemory、EEPROMElectricallyErasableandProgrammableReadOnlyMemoryやフラッシュメモリ等の半導体記憶装置、HDDHardDiskDriveやSSDSolidStateDrive等の補助記憶装置、又は、DVDDigitalVersatileDisk等のリムーバブルディスクや、SDメモリカードSecureDigitalmemorycard等の記憶媒体メディア等が考えられる。また、レジスタregister群でも良い。なお、上記のプロセッサ及び上記のメモリは、一体化していても良い。例えば、近年では、マイコン等の1チップ化が進んでいる。したがって、パケット分類器1に搭載される1チップマイコンが、プロセッサ及びメモリを備えている事例が考えられる。上記のインタフェースの例として、ネットワーク通信に対応した基板マザーボード、I/Oボードやチップ等の半導体集積回路、NICNetworkInterfaceCard等のネットワークアダプタや同様の拡張カード、アンテナ等の通信装置、接続口コネクタ等の通信ポート等が考えられる。また、ネットワークの例として、インターネット、LANLocalAreaNetwork、無線LANWirelessLAN、WANWideAreaNetwork、バックボーンBackbone、ケーブルテレビCATV回線、固定電話網、携帯電話網、WiMAXIEEE802.16a、3G3rdGeneration、専用線leaseline、IrDAInfraredDataAssociation、Bluetooth登録商標、シリアル通信回線、データバス等が考えられる。但し、実際には、これらの例に限定されない。[パケット分類器の詳細]振り分け処理部11は、パケット分類器1への入力10として入力された検索キーの分類を行い、分類結果を、第1のルール比較部12に送る。また、パケット分類器1への入力10として入力された検索キーは、第2のルール比較部13にそのまま入力される。第1のルール比較部12及び第2のルール比較部13は、内部にルールを保持している。パケット分類器1への入力10として入力される検索キーとは、0、1の2つの値で示されるビット列である。ルールは、フィールド毎に、0、1、及びの3つの値で定義されている文字列である。ExactMatchを行うフィールドに関しては、0と1で定義される。PrefixMatch、或いは、WildcasrdMatchを行うフィールドに関しては、0、1、の3つの値で定義される。RengeMatchを行うフィールドに関しては、0、1の2つの値で定義され、最大値と最小値がそれぞれ2進表記によって定義される。[振り分け処理部の構成例]図2を参照して、振り分け処理部11の構成例について説明する。振り分け処理部11は、振り分け処理装置111と、振り分けポリシー記憶装置112を備えている。振り分け処理装置111は、振り分け処理に必要な情報振り分けポリシーに従って、実際に振り分け処理を行う。振り分けポリシー記憶装置112は、振り分け処理に必要な情報振り分けポリシーを記憶する。[振り分けポリシー]振り分けポリシーの例として、検索キーの振り分け処理の際に参照するビット列中のビット位置、参照する部分ビット列が表す値の大小によって振り分け先を決定するための閾値、振り分けに使用するフィールドの情報、或いは、前述した振り分けポリシーによって送り先の第1のルール比較部12内で分割されている部分のアドレス等を計算する手法計算ルール等が考えられる。[第1のルール比較部の形態]図3を参照して、第1のルール比較部12の形態について説明する。第1のルール比較部12は、内部が複数に分割され、それぞれの部分でルールを保持している。図3を参照すると、第1のルール比較部12の内部の領域は、ルール管理部121-1からルール管理部121-NまでのN個の領域に分割されている様子が例示されている。ルール管理部121-1からルール管理部121-Nは、ルールを管理するための部分である。以下、部分とは、ルール管理部121-1からルール管理部121-Nのいずれかを示すものとする。ここでは、第1のルール比較部12は、オープンフローにおけるフローテーブルを有するものとする。フローテーブルには、所定のルールと、ルールに適合するパケットに対して行うべきアクション、またそのルールの優先度等を定義したエントリentryが登録される。この場合、ルール管理部121-1から121-Nは、当該フローテーブルに設定されたエントリを管理している。但し、実際には、これらの例に限定されない。第1のルール比較部12は、振り分け処理部11からの検索キーと分類結果を入力し、分類結果で指定されたブロック内のルールと検索キーの比較を行い、結果をパケット分類器の出力14として出力する。第2のルール比較部13は、ルールを保持する。第2のルール比較部13は、入力10として検索キーを入力した時、保持している全てのルールと検索キーの比較を行い、比較した結果をパケット分類器の出力14として出力する。[本実施形態における動作]図4のフローチャートを参照して、本発明の第1実施形態におけるパケット分類器1の動作について説明する。振り分け処理部11は、予め事前に、検索キーを振り分けるための振り分けポリシーを有している。すなわち、振り分け処理部11の振り分けポリシー記憶装置112は、予め振り分けポリシーを記憶している。振り分けポリシーとして、特定の値を用いて大小比較を行って分割する手法や、特定の位置のビットを参照して分割する手法等がある。また、第1のルール比較部12、及び、第2のルール比較部13には、予めルールが分割されて配置されている。第1のルール比較部12は、振り分け処理部11における検索キーの振り分けポリシーによって、検索キーと比較一致処理を行うルールの配置方法も決定する。第1のルール比較部12は、この振り分けポリシーに従って、各部分毎にルールを管理する。振り分け処理部11が有する振り分けポリシーでは、1つの部分に分類が不可能なルールを、第1のルール比較部12内の複数の部分に複製して配置するか、又は、第1のルール比較部12ではなく、第2のルール比較部13に配置するというルールの分割配置の基準を規定している。例えば、全ての部分に複製されるルールを第2のルール比較部13に配置し、それ以外のルールを第1のルール比較部12に配置するというルールの分割配置の基準を規定する。或いは、複製が発生するルールを全て第2のルール比較部13に配置し、それ以外のルールを第1のルール比較部12内の複数の部分に複製して配置するというルールの分割配置の基準を規定する。或いは、ある閾値を設定して、その閾値を超える数分の複製が発生するルールを第2のルール比較部13に配置し、それ以外を第1のルール比較部に配置するというルールの分割配置の基準を規定する。ルールは、振り分け処理部11が有する振り分けポリシーと、ルールの分割配置の基準に従って、第1のルール比較部12内の部分、或いは第2のルール比較部13に配置される。第1のルール比較部12では、振り分け処理部11の振り分け結果に基づいて、振り分けられた検索キーと分割部分内に配置されたルールとの比較処理検索処理が行われる。第2のルール比較部では、振り分け結果に関係なく、保持している全てのルールと検索キーの比較処理が行われる。1ステップA1パケット分類器1は、パケット分類器への入力10から検索キーを受け取る。2ステップA2パケット分類器1は、入力10として入力された検索キーを、振り分け処理部11へ送る。3ステップA3振り分け処理部11は、振り分けポリシーに従って、検索キーの振り分け処理を実行する。4ステップA4振り分け処理部11は、振り分け処理の結果に従って、検索キーを第1のルール比較部12へ渡す。5ステップA5第1のルール比較部12は、振り分けられた検索キーと、分割されたルール管理部121-1~121-Nで保持されるルールとの比較処理を行う。6ステップA6また、パケット分類器1は、入力10として入力された検索キーを、第2のルール比較部13へ送る。ステップA2以降ステップA2~A5と、ステップA6以降ステップA6~A7は、並列に処理を行うことが可能であるので、この例では並列に実行しているが、特に並列処理を限定するものではない。7ステップA7第2のルール比較部13は、振り分けられた検索キーと、第2のルール比較部13で保持されているルールとの比較処理を行う。8ステップA8パケット分類器1は、第1のルール比較部12と第2のルール比較部13での比較処理の結果を、パケット分類器1からの出力14として出力する。なお、本実施形態の図4のフローチャートでは、同期を取って出力がなされているが、必ずしも同期を取る必要はない。[検索キーの振り分け処理]図5は、検索キーの振り分け処理ステップA3からステップA4の様子を表したものである。振り分け処理部11は、検索キーの振り分け処理の結果に従って、第1の比較部12の該当する部分の全てに対して、検索キーを複製して送る。第1のルール比較部12は、図5に示されるように、内部が複数に分割されている構造になっている。このとき、第1のルール比較部12へ入力される検索キーは、振り分け処理部11を経由して送られてきても、振り分け処理部11を経由せずに別の手段で入力されても構わない。[ルール配置の具体例]図6A、図6Bを参照して、第1実施形態における振り分けポリシーによるルール配置の具体例について説明する。パケット振り分け処理部11は、閾値を5とした大小関係でパケットを振り分ける、振り分けポリシーを保持している。図6Aでは、例として振り分け処理を5未満の値を持つ検索キーと5以上の値を持つ検索キーで振り分け処理を行う様子を示している。このとき、振り分け処理部11は、振り分けの軸61より左側にある5未満の値を持つ検索キーと、軸61上及び軸61より右側の5以上の値を持つ検索キーとに振り分ける。振り分け処理部11は、図6Aに示されるように、入力された検索キーの値を用いて検索キーを分類し、分類した結果を第1のルール比較部12に送る。ここでは、ルール比較部12の内部は、図6Bに示されるように、ルール管理部121-Aとルール管理部121-Bの2つに分割されているものとする。振り分け処理部11は、検索キーの振り分け処理を行い、5未満の値を持つ検索キーをルール管理部121-Aに送り、5以上の値を持つ検索キーをルール管理部121-Bに送ることによって、分類結果を第1のルール比較部12へ伝える。一方で、第2のルール比較部13は、検索キーの振り分け処理を行うことがないため、内部も分割されずに、パケット分類器の入力10として入力された全ての値の検索キーを、そのまま入力する。これらの詳細については、後述する第1の実施例において説明する。[本実施形態の効果]本発明の第1実施形態によれば、振り分け処理部は、検索キーの振り分けの際に参照するビット位置と、それに対してルールを配置するルール配置の基準を振り分けポリシーとして保持している。この振り分けポリシーの設定によっては、第1のルール比較部だけでは、複製を生じざるを得ないルールが、第2のルール比較部に配置され、ルールの複製が発生しなくなる。また、複数のルールがパケット分類器内で管理される場合、ルールの複製が発生するルール数を抑制することができる。また、ルールの複製が発生するルールは、全て第2のルール比較部に配置することにすると、ルールの複製は発生しなくなる。<第2実施形態>次に、本発明の第2実施形態について図面を参照して説明する。本発明の第2実施形態は、本発明の第1実施形態における振り分け処理部11が決定木で実現されている点で異なる。[パケット分類器の構成例]図7を参照して、本発明の第2実施形態におけるパケット分類器1の構成例について説明する。入力10、振り分け処理部11、第1のルール比較部12については、図1、図2に示される第1のルール比較部12と同じである。振り分け処理部11は、内部において決定木を有する。決定木は、根ノード71と、葉ノード72を有する。ここでは、振り分け処理部11内において、振り分け処理装置111は、振り分けポリシー記憶装置112と関連付けられている。振り分けポリシー記憶装置112は、決定木を構成するための情報が記憶されている。振り分け処理装置111は、決定木を構成するための情報に基づき、決定木を構成する。すなわち、振り分け処理装置111は、決定木の根ノード71と、決定木の葉ノード72を有する。振り分け処理部11は、パケット分類器1への入力10として入力された検索キーが到達した時には、検索キーを、決定木の根ノード71に入力する。決定木における各ノードは、子ノードを決定するための手段を有し、入力された検索キーの情報と各ノードが保持する送り先子のノードを決定するための情報を用いて、次に検索キーを渡す子ノードを決定する。子ノードの決定には、検索キーの特定の位置にあるビットを参照する手段や、検索キー中のビット列が表す数値と、ノードが保持する閾値との大小比較によって、検索キーを分類する手段等が考えられる。特定のビットを参照する手段では、ノードは、参照するビット位置を保持する。また、特定の値を用いて検索キーを分類する手段では、ノードは、閾値を保持する。振り分けポリシー記憶装置112は、決定木における各ノードにおいて、以上のような子ノードを計算するための情報を保持する。[ノードと記憶装置の構成例]図8を参照して、本発明の第2実施形態におけるノードと記憶装置の構成例について説明する。振り分け処理装置111は、決定木のノード81と、記憶部82を備えている。決定木のノード81は、図7に示す決定木における各ノードである。記憶部82は、送り先の子ノードを計算するための情報を保持する。決定木のノード81は、記憶部82と関連付けられる。このように、各ノードは、それぞれが固有の送り先の子ノードを計算するための情報を保持する手段を有する。各ノードは、保持された情報に従って、決定木を構成する。検索キーは、順次決定木の各ノードを辿り、葉ノードまで到達する。すなわち、各ノードは、葉ノードに到達するまで、検索キーを、順次決定木における次段のノードに送る。[葉ノードと第1のルール比較部の構成例]図9を参照して、本発明の第2実施形態における葉ノードと第1のルール比較部の構成例について説明する。第1のルール比較部12については、図3、図5に示される第1のルール比較部12と同じである。決定木の根ノード71、葉ノード72については、図7に示される根ノード71、葉ノード72と同じである。葉ノード72は、第1のルール比較部12内のルール管理部121-1と関連付けられる。このように、各葉ノードは、それぞれルールを管理する手段を有し、自ノードに到達可能な検索キーについてのみ、ルールとの一致比較処理を行う手段を有する。そのため、葉ノード72は、自ノードに到達可能な検索キーと一致比較処理を行う必要のあるルールのみを管理する。決定木による振り分け処理では、検索キーは、各ノードによる送り先の子ノードを決定する手段により、単一の葉ノードに到達する。このように、決定木による振り分け処理では、検索キーが到達する葉ノードは一意に決定される。但し、異なる検索キーが、それぞれ異なる葉ノードに到達する場合でも、両方の検索キーが同じルールと一致する場合がある。そのような場合には、ルールを2つに複製して、それぞれの葉ノードで管理するようにする。この場合、例えば、ルールは第1のルール比較部12のルール管理部121-1~ルール管理部121-Nに複製される。第1のルール比較部12のルール管理部121-1~ルール管理部121-Nは、複製されたルールをそれぞれ管理する。或いは、第2のルール比較部13でルールを管理する。この場合、第2のルール比較部13では、内部が複数の部分に分割されていないので、ルールの複製が発生することなくルールが管理される。[本実施形態における動作]図10のフローチャートを用いて、本発明の第2実施形態の動作について説明する。本発明の第2実施形態では、図4のステップA3における検索キーの振り分け処理が決定木を用いて実現される。具体的には、以下の通りである。1ステップA3-1振り分け処理部11は、自身に到達した検索キーを、決定木の根ノードに入力する。2ステップA3-2振り分け処理部11は、決定木の根ノードに関連付けられた送り先の子ノードを計算する情報を用いて、検索キーを送る子ノードを計算する。3ステップA3-3振り分け処理部11は、検索キーを、根ノードから送り先の子ノードへ送る。4ステップA3-4振り分け処理部11は、検索キーが葉ノードに到達したか確認するため、この送り先の子ノードが葉ノードであるか確認する。振り分け処理部11は、この送り先の子ノードが葉ノードでなければ、再度、検索キーを送る子ノードを計算する。この場合、振り分け処理部11は、葉ノードに到達するまで、子ノードの計算と子ノードへの検索キーの送信を繰り返す。5ステップA3-5振り分け処理部11は、この送り先の子ノードが葉ノードであれば、振り分け処理部での振り分け処理が終了しているので、振り分け結果を第1のルール比較部12に送信する。このように、振り分け処理部11は、検索キーを、第1のルール比較部12の内部で分割された部分のうち、決定木の葉ノードに関連付けられた部分に送ることで、第1のルール比較部12に振り分け処理の結果を伝えている。その他の動作については、第1実施形態の図4のフローチャートと同様であるため、説明は省略する。[本実施形態の効果]本発明の第2実施形態によれば、振り分け処理は、決定木によって実現されることによって、決定木を用いた振り分け処理を行う振り分け処理部と、第2のルール比較部を備えたパケット分類器が実現される。振り分け処理部は、決定木の各ノードにおいて、検索キーの特定のビット位置を参照することで検索キーを送る子ノードを決定し、順次ノードを辿ることで、振り分け処理を実現する。決定木による振り分け処理では、ルールの複製が発生するルールを第2のルール比較部で管理することで、ルールの複製が抑制される。<第3実施形態>次に、本発明の第3実施形態について図面を参照して説明する。本発明の第3実施形態は、本発明の第2実施形態に対して、振り分け処理部11と第1のルール比較部12とが、それぞれパイプライン構造で実現されているという点で異なる。[パケット分類器の構成例]図11を参照して、本発明の第3実施形態におけるパケット分類器2の構成例について説明する。パケット分類器2は、振り分け処理部21と、第1のルール比較部22と、複数のノードモジュール23と、複数のルール比較器24と、第2のルール比較部25を備えている。振り分け処理部21は、内部に複数のノードモジュール23が直列に接続されており、パイプライン的に検索キーの振り分け処理を行う。第1のルール比較部22は、内部に複数のルール比較器24が直列に接続されており、パイプライン処理で検索キーとルールの比較を行う。ルール比較器24は、図3、図5に示すルール管理部121-1からルール管理部121-Nのいずれかに相当する。第2のルール比較部25は、第1実施形態における第2のルール比較部13と同じである。本実施形態では、1つのノードモジュールが、木構造における同じ高さに位置するノード全てに対応している。[ノードモジュールの構成]図12を参照して、ノードモジュール23の構成例について説明する。ノードモジュール23は、子ノード情報記憶部231と、子ノード決定計算処理部232とを備えている。子ノード情報記憶部231は、当該ノードから検索キーを送る子ノードを計算するための情報を格納する。子ノード決定計算処理部232は、当該情報と検索キーを基に、次に、探索する子ノードを決定する。まず、決定木のノードモジュール23は、入力233として検索キーを入力する。子ノード決定計算処理部232は、記憶部231に格納されている送り先の子ノードを計算するための情報と検索キーから、次に検索キーを送る子ノードを計算し、計算された子ノードに対して検索キーを出力する。送り先の子ノードも、同様のノードモジュール23で構成され、同様の処理がなされることにより、検索キーが決定木を辿る処理を行う。なお、子ノード情報記憶部231は、メモリやレジスタ群で実現される。また、例えば、第3実施形態がプログラムで実現される場合は、ハードディスクで実現されていても良い。[子ノード情報記憶部の形態]図13を参照して、メモリで実現されている子ノード情報記憶部231の形態について説明する。ノードモジュール23の子ノード情報記憶部231内の各アドレスには、子ノードを計算するための情報が格納されている。当該ノードモジュール23の子ノード決定計算処理部232は、複数の子ノードのうち、検索キーの送り先の子ノードを計算して決定し、該当する子ノードのメモリアドレスを出力する。図13では、子ノードが4つ存在しているため、0から3までの4つのアドレス領域が保持され、送り先の子ノードに対応するアドレスを出力する。子ノードモジュール23の子ノード決定計算処理部232は、親ノードから出力されたメモリアドレスを、当該子ノードモジュール23のアドレス線2331を通してメモリ231に入力し、指定されたアドレスに対応するノード情報を読み出す。同時に、親ノードは、検索キーを、ノードモジュール23へ入力2332として入力し、子ノード決定計算処理部232に渡す。子ノード決定計算処理部232は、メモリから読み出されたノード情報と、検索キーを用いて、次の送り先の子ノードを計算し、同様に、アドレス線2341から次の子ノードの情報が格納されているメモリアドレスを出力し、検索キーも出力2342を通して次の子ノードへ送る。決定木の各ノード情報を保持するメモリアドレスの割り振りと、子ノード決定計算処理の仕方手法によって、振り分け処理部21は、内部に、図12のノードモジュールを1個乃至複数用いた決定木を構築する。ここでは、振り分け処理部21は、ノードモジュール23を複数個、直列に連結された構成をしている。[ノードモジュールの割り当て]図14を参照して、決定木の各レベルにノードモジュール23が割り当てられている事例について説明する。ここでは、振り分け処理装置111の振り分け処理部21は、ノードモジュール23として、ノードモジュール23-1と、ノードモジュールノードモジュール23-2と、ノードモジュールノードモジュール23-3とを有する。また、振り分け処理装置111は、決定木を構成する。決定木は、根ノード71と、葉ノード72とを有する。決定木の根ノード71、葉ノード72については、図7に示される根ノード71、葉ノード72と同じである。ここでは、葉ノード72として、葉ノード72-1、葉ノード72-2、葉ノード72-3、葉ノード72-4を示す。根ノードモジュール23-1は、根ノード71に入力された検索キーに対して、根ノードモジュール23-1に付随するメモリからのノード情報に基づいて子ノード決定計算処理を行い、転送先の子ノードを決定する。転送先の子ノードのノード情報は、子ノードのレベルのノードモジュールに関連付けられたメモリに格納されている。例えば、深さ2のノードのノード情報は、2段目のノードモジュール23-2の子ノード情報記憶部231に格納されている。根ノード71からの転送先ノードは、深さ2のノードのうちのいずれかであるので、ノードモジュール23-1で計算された子ノード情報が格納されているメモリアドレスは、ノードモジュール23-2に関連付けられたメモリに入力される。これによって、2段目のノードモジュール23-2の子ノード決定計算処理部232には、決定木の根ノードから検索キーを転送する子ノードの情報が入力されることになる。以降、この処理を決定木の各深さに対応するノードモジュールで繰り返すことにより検索キーは、決定木を辿るのと同様の結果が得られる。第1のルール比較部22もパイプライン的に処理することにより、パケット分類器全体がパイプライン的に処理されることになる。これにより、第1のルール比較部22内の分割数と決定木の葉ノードの数は等しくなる。よって、図14において、決定木の同じ深さのノード情報を1つのノードモジュールのメモリアドレスで区別して、メモリで保持していていたのと同様の方法を用いれば、第1のルール比較部も、メモリを用いて複数のルールを管理できる。[ルール比較器の構成]図15を参照して、第1のルール比較部22内のルール比較器24の構成例について説明する。ルール比較器24は、ルール管理部241と、比較処理部242を備えている。ルール管理部241は、ルールを保持している。比較処理部242は、検索キーとルールの比較処理を行う。なお、ルール管理部241がメモリで構成される場合は、第1のルール比較部22の内部の分割された部分は、ルール管理部241のメモリのアドレス空間に割り当てられる。ルール管理部241のアドレスと決定木の葉ノードは、1対1に対応する。ここでは、第1のルール比較部22は、決定木の各葉ノードと関連付けられているため、検索キーが葉ノードに到達した時には、ルール比較器24のメモリに対して、その葉ノードに対応するアドレスを入力する。決定木による振り分け処理では、検索キーが複数の葉ノードに到達することがなく、1つのルール管理部241から複数のルールを読み出さなくても良いため、図16のように、このようなルール管理部241を備えたルール比較器24を複数直列に接続することで、内部が複数に分割されている第1のルール比較部22が実現される。このルール比較器24による処理を1段ずつパイプライン的に処理することにより、第1のルール比較部22での比較処理がパイプライン構造で実現される。各ルール比較器24内のルール管理部241がメモリで実現される場合、分割された部分であるルール管理部241は、同じ部分に格納されるルールを、各ルール比較器24で同じメモリアドレスに格納することにすると、順次同じアドレスを次段のルール比較器に入力することで、順次同じ内部部分に格納されているルールが各段のルール比較器で読み出される。図15のルール比較器24では、ルール比較処理部242に対して、単一のルール管理部241が関連付けられている。ルール比較処理部242は、ルール管理部241から単一のルールを読み出す。ルール比較処理部242は、1つのルール管理部241から、図11の第1のルール比較部22内の1つの分割された部分で管理されている全てのルール、或いは、複数のルールを読み出しても良い。第2のルール比較部25は、内部が分割されていないので、どのように定義されているルールでも管理できる。パケット分類器1がハードウェアで実現される場合、第2のルール比較部25は、ワイルドカードも含めて一致比較が可能なTCAM等のデバイスで実現される。また、この第2のルール比較部は、検索キーとルールの一致比較処理をパイプライン処理で行うパイプライン比較器で実現されても良い。このとき、図16と同様に、第2のルール比較部25の内部に、ルール比較器15に類似したルール比較器を直列に並べたパイプライン構造のルール比較器が配置され、パイプライン処理でルールと検索キーの一致比較を行う。[本実施形態における動作]図17のフローチャートを用いて、本発明の第3実施形態の動作について説明する。本発明の第3実施形態では、図4のステップA3における検索キーの振り分け処理がパイプライン処理で実現される。具体的には、以下の通りである。1ステップA3-6振り分け処理部11は、自身に到達した検索キーを、決定木の根ノードモジュール23-1に入力する。2ステップA3-7振り分け処理部21は、根ノードモジュール23-1に入力された検索キーに対して、根ノードモジュールのノード情報を基に、送り先の子ノードを計算する。このとき、振り分け処理部21は、子ノードモジュール23-2内に保持されている子ノード情報記憶部231に対するメモリアドレスを計算する。3ステップA3-8振り分け処理部21は、検索キーと、計算された子ノード情報記憶部231のメモリアドレスを、根ノードモジュール23-1から、その子ノードモジュール23-2へ送る。4ステップA3-9振り分け処理部11は、検索キーが葉ノードに到着したか確認するため、この送り先の子ノードモジュールが葉ノードであるか確認する。振り分け処理部11は、この送り先の子ノードモジュールが葉ノードでなければ、再度、検索キーを送る子ノードモジュールを計算する。この場合、振り分け処理部11は、葉ノードに到達するまで、子ノードモジュールの計算と子ノードモジュールへの検索キーの送信を繰り返す。5ステップA3-10振り分け処理部11は、この送り先の子ノードモジュールが葉ノードであれば、葉ノードと第1のルール比較部の分割部分が1対1に対応するため、葉ノードモジュールから、第1のルール比較部に対して、当該葉ノードモジュールと関連付けられているメモリアドレス及び検索キーを送る。このメモリアドレスは、図15におけるルール比較器24のルール管理部241に入力される。ルール比較器24のルール管理部241には、ルールが格納されている。ルール比較器24のルール比較処理部242は、葉ノードから出力される検索キーと、ルール比較器24のルール管理部241で管理されているルールとに対する一致比較処理を行う。第1のルール比較部22も、図16に示されるように、内部で直列に接続されたルール比較器24がパイプライン処理を行うので、各ルール比較器24において、順次検索キーとメモリアドレスを次のルール比較器24に送り、一致比較処理を行う。振り分け処理部11は、子ノードが葉ノードでなければ、そのノードで、次の子ノードアドレスを計算して、次の子ノードにメモリアドレスと検索キーを順次送り、検索キーが葉ノードに到達するまで、この処理を繰り返す。[本実施形態の効果]本発明の第3実施形態によれば、振り分け処理部の決定木をハードウェアで実現することにより、ソフトウェアによって、実現する場合と比較して、低消費電力で、かつ処理性能の向上が期待できるため、遅延時間の短いパケット分類器が実現される。また、パイプライン構造を取ることにより、連続してパケットを処理することが可能になる。<第4実施形態>次に、本発明の第4実施形態について図面を参照して説明する。本発明の第4実施形態は、本発明の第3実施形態に対して、振り分け処理部と第1のルール比較部を複数備えている点で異なる。[パケット分類器の構成例]図18を参照して、本発明の第4実施形態におけるパケット分類器3の構成例について説明する。パケット分類器3は、振り分け処理部3131-i、i=1~Nと、第1のルール比較部3232-i、i=1~Nと、第2のルール比較部33を備えている。パケット分類器1は、入力30を受け取る。入力10は、外部からパケット分類器3への入力である。入力30は、図1に示されるパケット分類器1における入力10に相当する。ここでは、パケット分類器1は、入力30として、パケット分類器1において検索を行うための検索キーを、振り分け処理部3131-i、i=1~Nと、第2のルール比較部33へ入力する。振り分け処理部3131-i、i=1~Nの各々は、図1に示されるパケット分類器1における振り分け処理部11に相当する。第1のルール比較部3232-i、i=1~Nの各々は、図1に示されるパケット分類器1における第1のルール比較部12に相当する。第2のルール比較部33は、図1に示されるパケット分類器1における第2のルール比較部13に相当する。振り分け処理部3131-i、i=1~Nと第1のルール比較部3232-i、i=1~Nは、それぞれ1対1で接続されている。パケット分類器1は、第1のルール比較部32での検索結果と、第2のルール比較部33での検索結果を、それぞれ結果として出力する。この出力を出力34とする。[本実施形態における動作]図19のフローチャートを参照して、本発明の第4実施形態におけるパケット分類器3の動作について説明する。本発明の第4実施形態では、複数の振り分け処理部と複数の第1のルール比較部を備えており、それぞれが並列に実行される。本実施形態では、複数の振り分け処理部と複数の第1のルール比較部の各々において、図4のステップA2~ステップA5が実施される。1ステップB1パケット分類器3は、パケット分類器への入力10から検索キーを受け取る。2ステップB2パケット分類器3は、入力10として入力された検索キーを、振り分け処理部3131-i、i=1~Nの各々へ送る。3ステップB3振り分け処理部3131-i、i=1~Nの各々は、振り分けポリシーに従って、検索キーの振り分け処理を実行する。4ステップB4振り分け処理部3131-i、i=1~Nの各々は、振り分け処理の結果に従って、検索キーを第1のルール比較部3232-i、i=1~Nの各々へ入力する。5ステップB5第1のルール比較部3232-i、i=1~Nの各々は、振り分けられた検索キーと、分割されたルール管理部121-1~121-Nで保持されるルールとの比較処理を行う。6ステップB6また、パケット分類器3は、入力10として入力された検索キーを、第2のルール比較部33へ送る。ステップB2以降ステップB2~A5と、ステップB6以降ステップB6~A7は、並列に処理を行うことが可能であるので、この例では並列に実行しているが、特に並列処理を限定するものではない。7ステップB7第2のルール比較部33は、振り分けられた検索キーと、第2のルール比較部33で保持されているルールとの比較処理を行う。8ステップB8パケット分類器3は、第1のルール比較部3232-i、i=1~Nの各々と第2のルール比較部33での比較処理の結果を、パケット分類器3からの出力14として出力する。なお、本実施形態の図19のフローチャートでは、同期を取って出力がなされているが、必ずしも同期を取る必要はない。[本実施形態の効果]上記のように、本発明の第4実施形態は、複数の振り分け処理部と、それに接続する複数の第1のルール比較部とを備えている。本発明の第4実施形態によれば、振り分け処理部で一意に振り分けることができなかったルールは、複製が発生するか、第2のルール比較部で管理されるが、複数の振り分け処理部を用いることにより、ある振り分け処理部では振り分けられないが、他の振り分け処理部では振り分けが可能なルールも、第1のルール比較部で管理が可能になる。これにより、第2の振り分け処理部を用いずとも、ルールの複製が抑制される。該ルールは、いずれの決定木でも複製が発生する場合にのみ第2のルール比較部に配置される。第2のルール比較部をハードウェアで実現した場合、第2のルール比較部は、内部に保持している全てのルールとの一致比較処理が行われるため、第1のルール比較部と比較して高価で消費電力も大きくなるが、第4実施形態により、決定木を複数用いることで第2のルール比較部の容量を小さくでき、結果としてコストを抑制することができる。<第5実施形態>次に、本発明の第5実施形態について図面を参照して説明する。本発明の第5実施形態では、本発明の第1乃至第4実施形態における、振り分け処理部、第1のルール比較部、及び第2のルール比較部の構成を決定する。[パケット分類器の構成例]図20を参照して、本発明に係るパケット分類器を設計する計算機パケット分類器設計装置の構成例について説明する。当該計算機は、処理装置40と、記憶装置41とを備えている。[記憶装置]記憶装置41は、第1のルールのプロファイル410を予め記憶している。第1のルールのプロファイル410は、ワイルドカード含有率411と、ルール数412とを含む。更に、記憶装置41は、第1の目標性能413を予め記憶している。第1のルールのプロファイル410は、ルールセットの第1のプロファイルである。ワイルドカード含有率411は、ビット位置毎のワイルドカード含有率である。ワイルドカード含有率411は、次のような割合で与えられる。例えば、ビット毎にワイルドカードが指定できるビットのワイルドカード含有率は、ビット位置毎に、ワイルドカードが出現するルールの割合で与えられる。また、例えば、フィールド毎にワイルドカードが指定できるフィールドのワイルドカード含有率は、フィールドにワイルドカードが含まれる割合で与えられる。また、例えば、RangeMatchとExactMatchの両方が指定できるフィールドのワイルドカードの含有率は、当該フィールドのレンジマッチの含有率で与えられる。また、例えば、PrefixMatchとExactMatchの両方が指定できるフィールドのワイルドカードの含有率は、当該フィールドのPrefixMatchの含有率で与えられる。ルール数412は、パケット分類器に格納するルールの総数である。第1の目標性能413の例として、メモリの容量、消費電力、半導体回路で実現した時の回路面積、ソフトウェアで実現した時のプログラムサイズ、単位時間あたりの検索回数、動作周波数、検索キーを入力してから検索結果を得るまでの時間、等が考えられる。[処理装置]処理装置40は、構成の決定部400と、性能の評価部403とを備えている。構成の決定部400は、振り分け処理部構成の決定部401と、ルール比較部構成の決定部402とを備えている。振り分け処理部構成の決定部401は、ワイルドカード含有率411と、パケット分類器内で保持するルール数412から、振り分け処理部の構成を決定する。振り分け処理部の構成の例として、振り分けポリシー、振り分けポリシーを保持する記憶領域の容量、振り分け処理部の決定木の高さ、振り分け処理部の決定木のノードあたりの分岐数、同時に振り分け処理が可能な検索キーの数、等が考えられる。また、振り分け処理部構成の決定部401は、ワイルドカード含有率411と、パケット分類器内で保持するルール数412から、ルールを、第1のルール比較部と第2のルール比較部に分割して配置するためのルールの分割配置の基準も決定する。ルール比較部構成の決定部402は、振り分け処理部の構成とルール数から、第1のルール比較部の構成、並びに、第2のルール比較部の構成を決定する。第1のルール比較部の構成の例として、保持するルール数、内部を分割したブロックの数、同時比較数、パイプラインで構成した時のパイプライン段数、パイプライン1段あたりの比較数、等が考えられる。第2のルール管理部の構成の例として、保持するルール数、パイプラインで構成した時のパイプライン段数、パイプラインの数、同時比較数、等が考えられる。性能の評価部403は、振り分け処理部構成の決定部401及びルール比較部構成の決定部402によって決定された構成から、パケット分類器の評価を行う。性能の評価部403の例として、性能見積もり手段、メモリ容量見積もり手段、消費電力見積もり手段、半導体回路で実現した時の回路面積見積もり手段、ソフトウェアで実現した時のプログラムサイズ見積もり手段、処理時間見積もり手段、動作周波数見積もり手段、単位時間あたりの検索回数の見積もり手段、等が考えられる。記憶装置41で保持されている第1のルールのプロファイル410は、構成の決定部401及びルール比較部構成の決定部402においても、性能の評価部403においても使用されることがある。処理装置40は、性能の評価部403において評価が終了すると、パケット分類器設計データ414を記憶装置41に記憶する。パケット分類器は、このパケット分類器設計データ414を基に構成される。すなわち、パケット分類器を動作させる計算機は、このパケット分類器設計データ414を入力し、このパケット分類器設計データ414を基にパケット分類器を構成する。なお、パケット分類器を設計する計算機と、パケット分類器を動作させる計算機は、同一の計算機でも良い。[本実施形態における動作]図21のフローチャートを参照して、本発明の第5実施形態におけるパケット分類器の構成の決定方法について説明する。1ステップC1処理装置40は、記憶装置41から、第1のルールのプロファイル410を読み出し、入力として振り分け処理部構成の決定部401に与える。2ステップC2振り分け処理部構成の決定部401は、振り分け処理部での振り分けポリシーを決定し、ルール比較部構成の決定部402に渡す。振り分けポリシーの例として、分割に使用するビット位置や、ルール配置の基準分割に使用する閾値、振り分けに使用するフィールド、振り分け分岐数等が考えられる。例えば、振り分け処理部構成の決定部401は、全ての場合を探索する全探索や、ランダムに参照ビット位置、ルール配置の基準を生成することを繰り返すモンテカルロ手法等で、ビット位置や、ルール配置の基準を決定する。3ステップC3ルール比較部構成の決定部402は、決定した振り分けポリシーと、ビット位置毎のワイルドカード含有率411と、ルール数412から、第1のルール比較部、及び、第2のルール比較部に格納するルール数を決定する。例えば、ルール比較部構成の決定部402は、振り分けポリシー、ワイルドカード含有率、及び、ルールの総数から、仮に全てのルールを第1のルール比較部に格納した場合に複製されるルールの数を求める。また、ルール比較部構成の決定部402は、振り分け処理部で参照するビット位置とワイルドカードのビット位置毎の出現率を参照した場合、第1のルール比較部で管理すると複製が発生するルールの割合を求める。ルール比較部構成の決定部402は、この複製が発生するルールの割合と、ルール数と第1のルール比較部22の分割数を参照することによって、複製発生後のルール数を求める。また、ルール比較部構成の決定部402は、ルールの複製を行わないようにルールを配置すると決めると、振り分け処理部で参照するビット位置にワイルドカードが存在するルールを、全て第2のルール比較部で管理することになるため、ビット位置毎のワイルドカード含有率を参照することによって、複製が発生するルールの割合を求める。求められたルールの割合は、第2のルール比較部で管理されるルールの割合でもある。ルール比較部構成の決定部402は、第2のルール比較部で管理されるルールの割合と、ルール数412を参照することにより、第2のルール比較部に格納するルール数を決定する。ルール比較部構成の決定部402は、全体のルール数から第2のルール比較部で管理されるルール数を引くことにより、第1のルール比較部で管理されるルール数を決定する。また、ルール比較部構成の決定部402は、ルールの複製をある閾値以下とするようにルールを配置すると決めて、第1のルール比較部に格納するルール数を決定しても良い。このように、ルール比較部構成の決定部402は、決定された分割に使用するビット位置とルール配置の基準、及び入力されたビット位置毎のワイルドカードの含有率から、第1のルール比較部に配置されるルール、及び第2のルール比較部に配置されるルール、及び第1のルール比較部における複製の発生率を、それぞれ決定する。ルール比較部構成の決定部402は、入力されたルール数を用いて、第1のルール比較部、又は、第2のルール比較部における管理ルール数配置されるルール数を決定する。また、ルール比較部構成の決定部402は、ステップC2で振り分け処理部の振り分けポリシーを決定しているので、第1のルール比較部の内部分割数を併せて決定する。4ステップC4ルール比較部構成の決定部402は、第1のルール比較部と第2のルール比較部の容量サイズを、それぞれ決定する。ルール比較部構成の決定部402は、ステップC3で決定された管理ルール数から、直ちに、ルール比較部に求められる容量を決定する。ステップC2において決定した参照するビット位置やルールを配置する基準では、大きな容量の第2のルール比較部が必要になる場合がある。また、複製が発生して大きな容量の第1のルール比較部が必要になる場合もある。5ステップC5性能の評価部403は、他の構成でも評価処理を行うか確認する。他の構成でも評価処理を行う場合、再度、振り分け処理部での振り分けポリシーを決定する。他の構成では評価処理を行わない場合、処理を終了する。すなわち、性能の評価部403は、ルール比較部構成の決定部402で求められたルール比較部の容量や電力を目的関数として、目的関数を最小化するために、ステップC4で評価処理を行った後に、ステップC2の構成決定処理に戻る。目的関数が最小となれば、処理を終了する。[本実施形態の効果]第5実施形態では、予め定められたルールを解析することにより、構成を決定するのではなく、ルールに含まれるビット位置毎のワイルドカードの含有率とルール数を基に、パケット分類器の構成を決定する。ビット位置毎のワイルドカードの含有率が入力されることにより、具体的なデータセットが存在しなくても入力されたルール数を管理するための、本発明の第1、第2、第3、第4実施形態における振り分け処理部、第1のルール比較部、及び第2のルール比較部の構成、及び容量を決定することが可能となる。これにより、どのようなルールが入力されるかわからない状況でも、ビット位置毎のワイルドカード含有率と、ルール数というルールのプロファイルを入力することによって、パケット分類器を設計することができる。<第6実施形態>次に、本発明の第6実施形態について図面を参照して説明する。[パケット分類器の構成例]図22を参照して、本発明に係るパケット分類器を設計する計算機の構成例について説明する。当該計算機は、処理装置50と、記憶装置51とを備えている。処理装置50は、図20に示される処理装置40と共通の処理装置でも良い。また、記憶装置51は、図20に示される記憶装置41と共通の記憶装置でも良い。[記憶装置]記憶装置51は、第2のルールのプロファイル510を予め記憶している。第2のルールのプロファイル510は、ワイルドカード含有率511と、ルール数512と、バラつき分布、分散具合513を有する。更に、記憶装置51は、制約条件514を予め記憶している。第2のルールのプロファイル510は、ルールセットの第2のプロファイルである。ワイルドカード含有率511は、基本的に、図20に示されるワイルドカード含有率411と同じである。ルール数512は、基本的に、図20に示されるルール数412と同じである。バラつき具合513は、ワイルドカード含有率511のバラつき具合である。制約条件514は、性能を評価する際の制約条件である。[処理装置]処理装置50は、構成の決定部501と、性能の評価部502とを備えている。構成の決定部501は、ビット位置毎のワイルドカード含有率511とパケット分類器内で保持するルール数512から、振り分け処理部11、第1のルール比較部22、及び第2のルール管理部の構成、容量を決定する。構成の決定部501は、図20に示される構成の決定部400に相当する。すなわち、構成の決定部501は、図20に示される振り分け処理部構成の決定部401とルール比較部構成の決定部402を含んでいても良い。性能の評価部502は、構成の決定部501によって決定された各種ハードウェアパラメータから、パケット分類器の容量や、容量から見積もられる電力を計算し、評価を行う。性能の評価部502は、図20に示される性能の評価部403に相当する。性能の評価部502は、評価の際、記憶装置51で保持されている、ワイルドカード含有率のバラつき具合513や制約条件514も使用する。また、構成の決定部501も、これら記憶装置51で保持されているルールのデータを使用することがある。構成の決定部501と性能の評価部502は、制約条件514を満たしながら、目的関数の最適化を行い、所望の性能を達成する構成が決定された場合、パケット分類器設計データ515を出力する。処理装置50は、性能の評価部502において評価が終了すると、パケット分類器設計データ515を記憶装置51に記憶する。パケット分類器は、このパケット分類器設計データ515を基に構成される。すなわち、パケット分類器を動作させる計算機は、このパケット分類器設計データ515を入力し、この設計データを基にパケット分類器を構成する。なお、パケット分類器を設計する計算機と、パケット分類器を動作させる計算機は、同一の計算機でも良い。[本実施形態における動作]図23のフローチャートを参照して、本発明の第6実施形態におけるパケット分類器の構成の決定方法について説明する。1ステップD1処理装置50は、記憶部51から、ビット位置毎のワイルドカードの含有率511と管理ルール数512に加えて、更にワイルドカードのバラつき具合513と制約条件514を読み出し、入力として構成の決定部501に与える。2ステップD2構成の決定部501は、振り分けポリシーとして、分割に使用するビット位置と、ルール配置の基準を決定する。3ステップD3構成の決定部501は、それを基に、バラつきを持ったワイルドカードの含有率を考慮して、管理ルール数を確率的に決定する確率で表す。バラつきを持ったワイルドカードの含有率の詳細については後述する。4ステップD4構成の決定部501は、入力された制約条件514を基にして構成を決定し、性能の評価部502に渡す。このとき、構成の決定部501は、制約条件を容量とすれば、その容量の制限を満たしながら、最良のルール管理成功率を達成する構成を決定する。一方で、制約条件にルール管理成功率を設定することによって、所望のルール管理成功率を達成するルール比較部の容量を決定する。容量の制約条件として、第2のルール比較部の容量だけではなく、第1のルール比較部の容量も制約条件として、設定することも可能である。5ステップD5性能の評価部502は、このサンプリングされたバラつきを持ったワイルドカード含有率を用いて、パケット分類器の性能を評価する。パケット分類器の性能評価の詳細については後述する。また、性能の評価部502は、他の構成でも評価処理を行うか確認する。他の構成でも評価処理を行う場合、再度、振り分け処理部で振り分けポリシー分割に使用するビット位置、及びルール配置の基準を決定する。他の構成では評価処理を行わない場合、処理を終了する。すなわち、性能の評価部502は、構成の決定部501で求められたルール比較部の容量や電力を目的関数として、目的関数を最小化するために、ステップD4で評価処理を行った後に、ステップD2の構成決定処理に戻る。目的関数が最小となれば、処理を終了する。構成の決定部501は、ステップD2で、異なるワイルドカードのバラつき具合や、制約条件を入力することで、異なる構成のパケット分類器の構成を得る。[バラつきを持ったワイルドカードの含有率]図24A、図24Bを参照して、バラつきを持ったワイルドカードの含有率について説明する。図24A、図24Bにおいて、グラフの横軸は、nビット目のワイルドカードの含有率を表している。また、グラフの縦軸は、横軸の値nビット目のワイルドカードの含有率の度数である。1ビット毎図24Aは、ビット毎のワイルドカードの含有率の確率密度関数である。本実施形態では、nビット目のワイルドカードの含有率のみを入力として与えるので、nビット目のワイルドカードの含有率を50として入力すると、50以外にはならない。よって、図24Aでは、nビット目のワイルドカードの含有率が50である確率が100となっている。2バラつきを与えた場合図24Bでは、nビット目のワイルドカードの含有率にバラつきを与えた場合のワイルドカードの含有率の確率密度関数である。nビット目のワイルドカードの含有率を50とし、バラつきを与えた場合、50をピークとして、その左右に広がりを持った分布となる。例として、分布が正規分布である場合、正規分布を決定するパラメータは、一般的に平均値μと標準偏差σである。標準偏差を大きく取れば、その分バラつき具合も大きくなる。ビット位置毎のワイルドカード含有率を平均μとし、ワイルドカード含有率のバラつき具合として標準偏差、或いは、分散の値が入力され、ワイルドカード含有率のバラつき具合が決定される。但し、分布は正規分布に限定されない。[ワイルドカード含有率の決定方法]図25を参照して、ワイルドカード含有率の決定方法について説明する。1ステップE1構成の決定部501は、ビット位置毎のワイルドカード含有率511平均μを入力する。2ステップE2構成の決定部501は、ワイルドカード含有率のバラつき具合513分散σを入力する。3ステップE3構成の決定部501は、入力されたビット位置毎のワイルドカード含有率511平均μと、ワイルドカード含有率のバラつき具合513分散σを用いて、正規分布に従ったバラつきを持つビット位置毎のワイルドカード含有率を得る。構成の決定部501は、この正規分布に従い、複数回サンプリングを行うことによって、ビット位置毎のワイルドカード含有率を得る。構成の決定部501は、サンプリングの回数が多ければ、大数の法則に従って、設定した正規分布に忠実に沿ったバラつきを再現する。4ステップE4構成の決定部501は、バラつきを考慮したワイルドカード含有率のルールセットを、性能の評価部502に渡す。[パケット分類器の性能評価]図26A、図26Bに示されるように、バラつきを持たせたワイルドカード含有率を用いることにより、管理可能なルール数が確率で表される。図26Aに示されるように、図26Aのようなバラつきを持たないワイルドカード含有率と、ルール配置の基準を用いて管理可能なルール数を評価すると、管理可能なルール数は、ある値で決定する。しかしながら、図26Bのようなバラつきを持ったワイルドカード率を用いることにより第1のルール比較部の管理可能なルール数が確率で表される。第1のルール比較部で管理しないルールは、第2のルール比較部で管理されるため、第2のルール比較部の容量を大きくすると、第1のルール比較部で管理できるルール数が少ない時でも、第2のルール比較部で残りのルールを管理できる確率が高くなる。逆に、第2のルール比較部の容量を小さくすると、第2のルール比較部でも管理できないルールの数が発生するため、入力したルール数が管理できる成功率が低くなる。図27に示されるように、第2のルール比較部の容量とルール管理の成功率は、相反する関係にある。[本実施形態の効果]前述した本発明の第5実施形態では、入力としてビット位置毎のワイルドカード含有率のみを入力するため、構成されたパケット分類器に異なるワイルドカード含有率のルールセットが入力された場合、当初の性能が発揮されるかどうかは不明となる。一方、本発明の第6実施形態によれば、入力としてビット位置毎のワイルドカードの含有率と、ワイルドカード含有率のバラつきの度合を入力することにより、バラつきを持ったワイルドカード含有率を用いて管理可能なルール数と容量を評価する。本実施形態によって、構成されたパケット分類器に、当初設定したワイルドカード含有率とは、異なるルールセットが入力された場合にも、確率的に性能を決定することができる。<第7実施形態>次に、本発明の第7実施形態について図面を参照して説明する。[パケット分類器の構成例]本実施形態では、本発明の第6実施形態と同様に、図22に示されるような、パケット分類器を設計する計算機の構成例について説明する。当該計算機は、処理装置50と、記憶装置51とを備えている。[記憶装置]記憶装置51については、基本的に、第6実施形態と同様である。[処理装置]処理装置50は、構成の決定部501と、性能の評価部502を有する。構成の決定部501については、基本的に、第6実施形態と同様である。性能の評価部502は、構成の決定部501とルール比較部構成の決定部502によって決定された各種ハードウェアパラメータから、パケット分類器のバラつき耐性ロバスト性の評価を行う。また、併せてパケット分類器の容量や消費電力の評価を行っても良い。構成の決定部501及び性能の評価部502は、それぞれ、記憶装置51で保持されている第2のルールのプロファイル510を使用することがある。構成の決定部501及び性能の評価部502は、制約条件514として、ロバスト性能や、消費電力やパケット分類器の記憶容量等の条件を満たしながら、目的関数の最適化を行い、所望の性能を達成する構成が決定された場合、パケット分類器設計データ515を出力する。処理装置50は、性能の評価部502において評価が終了すると、パケット分類器設計データ515を記憶装置51に記憶する。パケット分類器は、このパケット分類器設計データ515を基に構成される。すなわち、パケット分類器を動作させる計算機は、このパケット分類器設計データ515を入力し、この設計データを基にパケット分類器を構成する。なお、パケット分類器を設計する計算機と、パケット分類器を動作させる計算機は、同一の計算機でも良い。[本実施形態における動作]図28のフローチャートを参照して、本発明の第7実施形態におけるパケット分類器の構成の決定方法について説明する。1ステップF1処理装置50は、記憶部51から、ビット位置毎のワイルドカードの含有率511と管理ルール数512に加えて、更にワイルドカードのバラつき具合513と制約条件514を読み出し、入力として与える。2ステップF2構成の決定部501は、振り分けポリシーとして、分割の際に参照するビット位置と、ルール配置の基準を決定する。3ステップF3構成の決定部501は、バラつきを持ったワイルドカード含有率511を基に、ステップF2で決定した分割に使用するビット位置とルール配置の基準に従って、第1のルール比較部22と第2のルール管理部に配置されるルール数を計算する。4ステップF4構成の決定部501は、第1のルール比較部22と第2のルール管理部に配置されるルールの数を基に、第1のルール比較部22と第2のルール管理部の容量を決定し、決定された容量で、全てのルールが管理することができる割合を計算し、性能の評価部502に渡す。このとき、決定された容量で、全てのルールが管理することができる割合を計算することにより、ステップF2で決定した振り分けポリシー、及びステップF3で決定した構成について、入力されたワイルドカード率のバラつきに対する耐性を評価することができる。5ステップF5性能の評価部502は、算出された割合を基に、決定された構成の性能の評価を行う。ここでは、入力されたワイルドカード率のバラつきに対する耐性を評価する。また、性能の評価部502は、他の構成でも評価処理を行うか確認する。他の構成でも評価処理を行う場合、再度、振り分け処理部で振り分けポリシー分割の際に参照するビット位置、及びルール配置の基準を決定する。他の構成では評価処理を行わない場合、処理を終了する。[本実施形態の効果]本発明の第7実施形態によれば、本発明の第6実施形態に示された、ルールのプロファイルを用いて設計されたパケット分類器に、バラつきを持たせたワイルドカードを複数入力した場合、どれくらいのルールがパケット分類器の記憶装置に格納することができずにあふれるかを評価することができる。そのため、設計時に入力したルールのプロファイルと、実際には、入力されたルールセットのワイルドカード含有率が異なった場合でも、パケット分類器にルール数が格納できるかどうかを評価することができる。これにより、ロバスト性の高いパケット分類器の設計手法が提供される。以上が、本発明の各実施形態についての説明である。<各実施形態の関係>なお、上記の各実施形態は、組み合わせて実施することも可能である。<第1の実施例>以下、本発明の第1の実施例について説明する。本実施例は、本発明の第1実施形態に対応するものである。[パケット分類器が保持するルール]図29を参照して、第1の実施例におけるパケット分類器1が保持するルールについて説明する。図29に示されるように、振り分け処理部11における振り分けのルールR1、ルールR2、ルールR3の3つのルールが存在するものとする。ルールR1は、1から4までの値を持つ検索キーに対して一致が起こるルールであるとする。同様に、ルールR2は、3から7の値を持つルールに対して一致が起こり、ルールR3は、6から9の値を持つ検索キーに対して一致が起こるルールである。図29に示されているルールは、第1のルール比較部12、及び第2のルール比較部13に配置されており、それぞれ入力された検索キーと内部で保持しているルールと比較される。[ルールの配置方法]次に、第1のルール比較部12と第2のルール比較部13へのルールの配置方法について説明する。ルールの配置は、振り分け処理部の振り分け処理のポリシーによって決定される。ここでは、振り分け処理部11は、5を閾値として、5未満の検索キーと5以上の検索キーで振り分け処理を行う。[ルールがカバーする範囲と振り分けポリシーが重なる例]図30Aを参照して、ルールR1、R2、及びR3がカバーする範囲と、振り分け処理部での振り分けポリシーが重なる例について説明する。振り分け処理部11では、振り分けの軸は5である。図30Aでは、点線でこの振り分けの軸61が示されている。ここでは、図30Bに示されるように、ルール比較部12の内部は、ルール管理部121-Aとルール管理部121-Bの2つの部分に分割されている。振り分け処理部11は、5未満の値を持つ検索キーを第1のルール比較部のルール管理部121-Aに振り分け、5以上の値を持つ検索キーをルール管理部121-Bに振り分ける。ルールR1は、1から4までの値を持つ検索キーに対して一致が起こるので、1から4までの値を持つ検索キーとは一致比較の処理が行われる必要がある。そのため、第1のルール比較部12内においては、ルールR1は、5未満の検索キーが入力されるルール管理部121-Aにおいて保持される。また、同様に、ルールR3は、6から9までの値を持つ検索キーと一致比較の処理が行われる必要があるため、5以上の値を持つ検索キーが入力されるルール管理部121-Bにおいて保持される。一方で、ルールR2は、3から7の値を持つ検索キーとの一致比較が行われる必要がある。しかしながら、振り分け処理部11は、5未満の値を持つ検索キーをルール管理部121-Aに、5以上の値を持つ検索キーをルール管理部121-Bに振り分ける。したがって、ルールR2に対する一致比較処理が行われるためには、部分311に振り分けられる3から5未満の値を持つ検索キーと、部分312に振り分けられる5以上から7までの値を持つ検索キーの両方の部分において一致比較処理が行われる必要がある。このときのルールR2の管理方法として、以下の1乃至3の3つの方法がある。1ルールR1を2つのルールに分割する、すなわち、3から5までの値を持つ検索キーと一致比較を行うルールR2Aと5から7までの値を持つ検索キーと一致比較を行うルールR2Bの2つに分割し、それぞれの部分で保持する方法2ルールR2を複製する、すなわち、3から7までの値を持つ検索キーと一致比較を行うR2のまま、ルール管理部121-Aとルール管理部121-Bの両方の部分にそれぞれ複製して保持する方法3第2のルール比較部に保持する方法図30Bでは、ルールR2を分割せずに第1のルール比較部に保持している様子方法2を示す。図30Bでは、元々3つであったルールが4つに増えている。これをルールの複製と呼ぶ。ルールの複製が起こると、ルールの管理に必要なメモリ量が増えるため、必要メモリ量を圧迫することになる。これに対して、方法3では、第2のルール比較部における振り分け処理を行わずにルールの比較を行うため、方法1や方法2のようなルールの複製は必要ない。そこで、本発明による第1の実施例では、ルールR3のような複製が発生するルールは、第2のルール比較部13で保持を行う。図30Cでは、ルールR2をルール比較部13で管理している様子が示されている。[動作の説明]パケット検索器1は、入力10として検索キーが入力された時に、振り分け処理部11に検索キーを入力すると共に、第2のルール比較部13にも検索キーを入力する。[2の値を持つ検索キーが入力された場合]例えば、ここで、2の値を持つ検索キーが入力された場合の動作を示す。検索キーは、振り分け処理部11と第2のルール比較部13にそれぞれ入力される。振り分け処理部11は、振り分けポリシーに従い、検索キーを振り分ける。キーの値が5未満であるため、検索キーは、ルール管理部121-Aに振り分けられる。第1のルール比較部のルール管理部121-Aは、検索キーとルールを比較する。ルール管理部121-Aに保持されているルールR2は、検索キーの値2と一致する。そのため、ルール管理部121-Aに入力された検索キーについては、ルールR1と一致したという結果が出力される。また、第2のルール比較部13に入力された検索キーについては、ルールR2と一致比較処理が行われるが、ルールR2は、3から7までの検索キーとしか一致しないので、2の値を持つ検索キーとは一致しない。[5の値を持つ検索キーが入力された場合]次に、5の値を持つ検索キーが入力された場合の動作を示す。振り分け処理部11は、5以上の値を持つ検索キーを、ルール管理部121-Bに振り分けるので、当該検索キーについては、ルールR3と一致比較処理が行われる。また、当該検索キーについては、第2のルール比較部13にも入力されるので、ルールR2との一致比較処理も行われる。この場合、ルール管理部121-BのルールR3とは一致しないので、不一致が出力される。また、第2のルール比較部のルールR2とは一致するので、一致したという結果が出力される。最後に、7の値を持つ検索キーが入力された場合の動作を示す。振り分け処理部11では、5以上の値を持つ検索キーは、ルール管理部121-Bに入力されるので、ルールR3と一致比較処理が行われる。また、第2のルール比較部に入力されてルールR2との一致比較処理が行われる。この場合、ルール管理部121-BのルールR3とは、一致するので、一致が出力され、また、第2のルール比較部のルールR2とも一致するので一致したという結果が出力される。<第2の実施例>以下、本発明の第2の実施例について説明する。本実施例は、本発明の第4実施形態に対応するものである。以下、本発明の第2実施形態は、振り分け処理部と第1のルール比較部を複数備えているパケット分類器である。図18によれば、パケット分類器3は、入力30として入力された検索キーを、第2のルール比較部33と、振り分け処理部31-1から振り分け処理部31-Nのそれぞれに入力する。各振り分け処理部振り分け処理部31-1から振り分け処理部31-Nの各々は、振り分けポリシーに従って、検索キーの振り分け処理を行う。各振り分け処理部は、この振り分けポリシーに従って、検索キーと一致比較を行うルールの配置を決定する。各振り分け処理部の保持する振り分けポリシーによっては、第1のルール比較部32-1から22-Nでは管理されずに、第2のルール比較部33で管理されるルールも存在する。このとき、各振り分け処理部は、異なる振り分けポリシーによって、検索キーの振り分け処理を行う。例えば、図31に示されるルールが存在するとする。図31では、振り分けの軸62は、4である。振り分けの軸63は、7である。ルールR1は、1から3の値を持つ検索キーと一致比較を行う必要のあるルールである。ルールR2は、2から5の値を持つ検索キーと一致比較を行う必要のあるルールである。ルールR3は、6から8の値を持つ検索キーと一致比較を行う必要のあるルールである。ルールR4は、9から11の値を持つ検索キーと一致比較を行う必要のあるルールである。ルールR5は、2から10の値を持つ検索キーと一致比較を行う必要のあるルールである。図32に示されるように、本実施例では、パケット分類器は、振り分け処理部31-1と振り分け処理部31-2の2つの振り分け処理部を持ち、第1のルール比較部32-1と第1のルール比較部32-2の2つの第1のルール比較部を持ち、第2のルール比較部33を持つものとする。第1のルール比較部32-1は、内部がルール管理部32-1Aとルール管理部32-1Bに分割されている。また、振り分け処理部31-1は、4未満の値を持つ検索キーと4以上の値を持つ検索キーで振り分け処理を行う振り分けポリシーを保持している。また、振り分け処理部31-1は、4未満の値を持つ検索キーをルール管理部32-1Aに振り分け、4以上の値を持つ検索キーをルール管理部32-1Bに振り分ける。第2のルール比較部32-2は、内部がルール管理部32-2Aとルール管理部32-2Bに分割されている。また、振り分け処理部31-2は、7未満の値を持つ検索キーと7以上の値を持つ検索キーで振り分け処理を行う振り分けポリシーを保持している。また、振り分け処理部31-2は、7未満の値を持つ検索キーをルール管理部32-2Aに振り分け、7以上の値を持つ検索キーをルール管理部32-2Bに振り分ける。このとき、仮に、振り分け処理部31-1だけを用いると、ルールR2とルールR5が複製されるか、又は、第2のルール比較部33に格納される。また、仮に、振り分け処理部31-2だけを用いると、ルールR3とルールR5が複製されるか、又は、第2のルール比較部33に格納される。しかし、上記の2つの振り分け処理部を用いると、図32のように、ルールR1とルールR3を第1のルール比較部32-1に格納し、ルールR2とルールR4を第1のルール比較部32-2に格納することができる。ルールR5は、複製されるか、或いは、第2のルール比較部33に格納される。図32においては、ルールR5は、第2のルール比較部33で管理されている。このように、異なる振り分けポリシーを持つ振り分け処理部を併用することになり、複製されるルール数、又は、第2のルール比較部33に格納するルール数が削減される。[動作の説明]パケット検索器は、入力30として検索キーが入力された時に、振り分け処理部31-1と振り分け処理部31-2の2つの振り分け処理部のそれぞれに検索キーを入力すると共に、第2のルール比較部33にも検索キーを入力する。[2の値を持つ検索キーが入力された場合]例えば、ここで、2の値を持つ検索キーが入力された場合の動作を示す。このとき、2の値を持つ検索キーは、図32に示されるように、第1のルール比較部32-1と、第1のルール比較部32-2と、第2のルール比較部33に入力される。第1のルール比較部32-1は、振り分けポリシーに従い、2の値を持つ検索キーを、ルール管理部32-1Aに振り分け、当該検索キーとルールR1との一致比較処理を行う。第1のルール比較部32-1は、2の値を持つ検索キーとルールR1とが一致するため、一致する旨を出力する。また、第1のルール比較部32-2は、振り分けポリシーに従い、2の値を持つ検索キーを、ルール管理部32-2Aに振り分け、当該検索キーとルールR2との一致比較処理を行う。第1のルール比較部32-2は、2の値を持つ検索キーとルールR2とが一致するため、一致する旨を出力する。第2のルール比較部33も、2の値を持つ検索キーを入力し、当該検索キーとルールR5との一致比較処理を行う。第2のルール比較部33は、2の値を持つ検索キーとルールR5とが一致するため、一致する旨を出力する。<第3の実施例>以下、本発明の第3の実施例について説明する。本実施例は、本発明の第1、第2、第3実施形態に準ずるものである。図33を参照して、第2のルール比較部がパイプライン構造で実現された様子について説明する。パケット分類器2は、振り分け処理部21と、第1のルール比較部22と、第2のルール比較部25を有している。振り分け処理部21は、第3実施形態に従って、内部にノードモジュール23が直列に接続されたパイプライン構造をしており、パイプライン処理を行う。第1のルール比較部21も、第3実施形態に従って、内部にルール比較器24が直列に接続されたパイプライン構造をしており、パイプライン処理を行う。本実施例では、第2のルール比較部25も、第1のルール比較部21と同様に、内部にルール比較器26が直列に接続されたパイプライン構造をしており、パイプライン処理を行う。第2のルール比較部25の内部に配置されるルール比較器26は、それぞれ、ルールを1つだけ保持する。第2のルール比較部25は、振り分け処理部21と接続されていないので、第2のルール比較部25に検索キーが入力された時には、入力された検索キーと、ルール比較器26で管理されている全てのルールとの一致比較を行う。このとき、直列に接続された各ルール比較器は、検索キーが入力された場合、当該ルール比較器内で唯一保持してルールと検索キーの一致比較処理を行う。また、第1のルール比較部21と同様に、第2のルール比較部25の内部にもパイプライン構造のルール比較器を配置し、複数本のルール比較器を用いてルールの管理を行うことにより、個々のルール比較部のパイプライン段数が削減される。この場合は、直列に並べられた複数本のルール比較器のそれぞれに、検索キーが入力される。第1のルール比較部22と第2のルール比較部25は、入力された検索キーに対して一致比較処理を行うルールを格納している。第1のルール比較部22のルール比較器24は、最大で決定木の葉ノード数分のルールを保持している。第2のルール比較部25のルール比較器26は、それぞれ1つのルールを保持している。また、振り分け処理部21は、ハードウェアによる決定木で振り分け処理を行う。振り分け処理部21のノードモジュール23は、振り分けポリシー、振り分け処理の結果を送る子ノード、及び第1のルール比較部の分割された部分の情報を格納する。[動作の説明]パケット分類器2は、入力20から検索キーが入力されると、入力された検索キーを、振り分け処理部21と、第2のルール比較部25にそれぞれ入力する。振り分け処理部21は、入力された検索キーを、根ノードモジュールに入力し、振り分けポリシーに従って、次段のノードモジュールに送る。振り分け処理部21は、決定木の葉ノードモジュールに到達したら、振り分け処理の最終的な結果に従って、第1のルール比較部22に送る。第1のルール比較部22の内部のルール比較器24は、順次、振り分け結果に従って、記憶装置からルールを読み出し、入力された検索キーと、読み出されたルールとの一致比較処理を行う。このとき、第1のルール比較部22の内部で直列に並べられたルール比較器24のそれぞれにおいて、比較処理部242は、ルール管理部241からルールを読み出し、検索キーと当該ルールとの一致比較処理を行った後、次段のルール比較器24に検索結果を渡す。検索結果の例として、検索キーと一致したルール、該ルールを一意に識別できるルールID、複数のルールに一致した場合に選択すべきルールの順番を示す優先度等が考えられる。最終段のルール比較器24は、検索結果を出力する。一方で、第2のルール比較部25の内部のルール比較器26は、順次、入力された検索キーと、読み出されたルールとの一致比較処理を行う。第2のルール比較部25の内部のルール比較器26は、高々1つのルールしか保持されていないため、毎回、保持されている1つのルールを記憶装置から読み出し、到着した検索キーとの一致比較処理を行い、次段のルール比較器26に検索結果を渡す。最終段のルール比較器26は、検索結果を出力する。パケット分類器2は、第1のルール比較部22での検索結果と、第2のルール比較部25での検索結果を、結果として出力する。<第4の実施例>以下、本発明の第4の実施例について説明する。本実施例は、本発明の第5実施形態に対応するものである。[第1のルールのプロファイルの例]図34を参照して、第1のルールのプロファイル341について説明する。第1のルールのプロファイル341は、ワイルドカードの含有率342と、ルール数343とを含む。ワイルドカードの含有率342の値は、フィールド1のワイルドカードの含有率が30であり、フィールド2のワイルドカードの含有率が70であることを示している。ルール数343の値は、ルール総数が100個であることを示している。[パケット分類器の構成例]図35を参照して、本実施例において設計されるパケット分類器の構成例について説明する。パケット分類器は、振り分け処理部351と、第1のルール比較部352と、第2のルール比較部353を備えている。振り分け処理部351は、振り分け処理装置354と、振り分けポリシー記憶装置355を備えている。[振り分けポリシー]振り分け処理部351の振り分けポリシー記憶装置355に保持されている振り分けポリシーの値は、分割に使用するフィールドがフィールド1であり、分割数が4であることを示している。[振り分け処理部構成の決定方法]まず、図20に示される振り分け処理部構成の決定部401は、振り分け処理部の構成、すなわち、分割フィールド、分割数を決定する図21のステップC2。[ルール比較部構成の決定方法]次に、ルール比較部構成の決定部402は、第1のルール比較部352の構成、すなわち、第1のルールの記憶部に記憶するルール総数、ブロック数、ブロック毎のルール数を決定する図21のステップC3。第1のルール比較部352は、総数60個のルールを記憶し、4つのブロックに分かれ、ブロック毎に15個のルールを記憶する。ルールの複製を許さないものとすると、全第1のルール比較部352は、ルールのうち、フィールド1にワイルドカードが出現する30については、記憶することができない。そこで、第1のルール比較部352に記憶するルールの最大数は、70個となる。ルール比較部構成の決定部402は、実際の第1のルール比較部352のルール総数として、該最大数以下の適当な値を採用する。第1のルール比較部352における分割数と、第1のルール比較部のブロックの数は一致する。そのため、ルール比較部構成の決定部402は、第1のルール比較部352を、4つのブロックに分割している。また、ルール比較部構成の決定部402は、ブロック毎のルール数を、総数60個を4つのブロックに均等に割り振った15個としている。ここで、必ずしも、各ブロックの大きさを均等にする必要はない。次に、ルール比較部構成の決定部402は、第2のルール比較部353の構成、すなわち、第2のルール比較部353に記憶するルール総数を決定する図21のステップC3。第2のルール比較部353は、総数40個のルールを記憶する。第2のルール比較部353のルール数の最小数は、ルール総数より第1のルール比較部352のルール総数を減ずることより求められる。したがって、第2のルール比較部353のルール数は、これより大きい適当な値が選ばれる。[性能の評価方法]次に、性能の評価部403は、パケット分類器の評価を行う図21のステップC4。[パケット分類器の評価結果]図36を参照して、パケット分類器の評価結果として、振り分け処理部351、第1のルール比較部352、及び第2のルール比較部353の各々に必要なメモリ量について説明する。振り分け処理部351に必要なメモリ量は、5KBである。第1のルール比較部352に必要なメモリ量は、10MBである。第2のルール比較部353に必要なメモリ量は、4MBである。[評価結果の判定]次に、性能の評価部403は、この評価結果について、要求を満たすかどうかを判定する図21のステップC5。もしも、要求を満たしていれば、性能の評価部403は、パケット分類器の各部の決定する設計パラメータとして出力する。反対に、要求を満たしていない時は、性能の評価部403は、ステップC2に戻り、他の構成を試す。<第5の実施例>以下、本発明の第5の実施例について説明する。本実施例は、本発明の第6実施形態に対応するものである。[第2のルールのプロファイルの例]図37を参照して、第2のルールのプロファイル371について説明する。第2のルールのプロファイル371は、ワイルドカードの含有率372と、ルールのワイルドカードのバラつきの指標373と、ルール数374とを含む。ワイルドカードの含有率372の値は、フィールド1のワイルドカードの含有率が30であり、フィールド2のワイルドカードの含有率が70であることを示している。ルールのワイルドカードのバラつきの指標373の値は、フィールド1に平均が30で標準偏差が10のバラつきがあり、フィールド2に平均が70で標準偏差が10のバラつきがあることを示している。ルール数374の値は、ルール総数が100個であることを示している。[振り分け処理部構成の決定方法]まず、図22に示される構成の決定部501は、振り分け処理部の構成、第1のルール比較部の構成、第2のルール比較部の構成を決定するステップD2。このステップは、第4の実施例におけるステップC2と同じである。構成の決定部501は、該最小数を、ステップD4の手順で決定する。また、構成の決定部501は、記憶できずにあふれるルール数を、該最小数から、各記憶部で管理可能なルール総数を減じて決定する。[最小数と管理可能なルール総数の関係]図38を参照して、該最小数から、各記憶部で管理可能なルール総数を減じた様子について説明する。図38では、第2のルールのプロファイル371が与えられた場合でも、ルールが管理可能な確率が100である第1のルール比較部及び第2のルール比較部の各々の該最小数は、それぞれ80個と40個である。このときに第1のルール比較部で管理可能ルール数を75個、第2のルール比較部で管理可能ルール数を40個とすると、第2のルールのプロファイル371が与えられた場合に、第1のルール比較部では5個のルールが記憶できずにあふれるため、5個のルールが記憶できずにあふれることを示されている。この場合はルールを管理可能な確率は100ではなくなる。このように管理可能なルール数が確率によって表される。第7実施形態に対応する実施例では、構成の決定部501は、図28のステップF2で決定された構成に対して、図25のフローチャートに示される処理によって得られたワイルドカード含有率のセットとルール配置の基準を用いた場合の管理可能なルール数を決定する。構成の決定部501は、バラつき具合を反映したワイルドカードの含有率を求める。ここでは、図39に示されるように、バラつき具合を反映した結果、フィールド1と2のワイルドカードの含有率が、それぞれ、33と64であるものとする。次に、構成の決定部501は、バラつき具合を反映したワイルドカードの含有率より、第1のルール比較部、及び、第2のルール比較部に記憶するルール数の最小数、及び記憶できずにあふれるルール数を決定するステップD3。構成の決定部501は、当該処理を、バラつき具合を反映したワイルドカードの含有率毎に繰り返し、記憶できずにあふれるルール数の最大値を決定する。性能の評価部502は、入力されたビット位置毎のワイルドカード含有率と、ルール配置の基準から決定された構成に対して、サンプリングによって、得られた複数のバラつきを持ったワイルドカード含有率で計算した場合に、全サンプル数のうち管理可能なサンプル数の割合を用いて、バラつき耐性ロバスト性を評価する。性能の評価部502は、ステップF1における入力として、このときは、制約条件として、求めるロバスト性能を入力し、所望のバラつきに対する耐性を備える構成を決定する。例えば、第2のルール比較部で管理可能なルール数を大きい構成を採用して、ワイルドカード含有率のバラつきに対する耐性が高いワイルドカード含有率のバラつきに影響を受けにくい構成を決定する。<まとめ>以上のように、本発明は、到着パケットから抽出した検索キーがどのルールに一致するかを判定するパケット分類器PacketClassificationに関するものである。具体的には、決定木を用いてルールを管理し、予備的なルール管理部を併用したパケット分類器、及びパケット分類器の構成手法に関する。本発明のパケット分類器は、単体の装置に限らず、複数の装置を用いてシステム構成で実現しても良い。この場合、本発明のパケット分類器は、パケット分類システムと読み替えることができる。本発明のパケット分類システムは、振り分け手段と、第1のルール比較手段と、第2のルール比較手段を備える。振り分け手段は、振り分けポリシーを記憶する。第1のルール比較手段は、ルール集合を2つ以上の部分集合に分類して記憶する。第2のルール比較手段は、ルール集合を分類せずに記憶する。振り分け手段は、検索キーを該部分集合に振り分け、第1のルール比較手段は、該振り分け結果に基づいて対応する部分集合内のルールと検索キーを比較して一致するルールを出力する。第2のルール比較手段は、該振り分け結果に関係なく記憶している全てのルールと検索キーを比較して一致するルールを出力するように動作する。このような構成を採用し、第1のルール比較部又は、第2のルール比較部にルールを配置する際に、複製されるルール数が予め与えられた閾値以下になるようにすることにより本発明の目的を達成することができる。本発明のパケット分類器設計装置は、ルールのプロファイル記憶手段と、振り分けポリシー決定手段と、第1のルール比較部の構成決定手段と、第2のルール比較部の構成決定手段と、パケット分類器の評価手段を備え、振り分けポリシー決定手段がルールのプロファイルに基づき振り分けポリシーを決定し、第1のルール比較部の構成決定手段及び第2のルール比較部の構成決定手段が、それぞれルールのプロファイルと振り分けポリシーを基に、第1のルール比較部及び第2のルール比較部の構成を決定し、パケット分類器の評価手段が決定した構成を評価するように動作する。このような構成を採用し、予め与えられた目標性能を満たすまで、構成の決定と評価を繰り返すことにより本発明の目的を達成することができる。本発明では、第1のルール比較部で管理しようとするとルールの複製が発生するルールを第2のルール比較部に配置することで、ルールの複製が発生しなくなるため、ルールの複製を抑制することができる。また、第2のルール比較部を備えたパケット分類器の振り分け処理を決定木で実現できる。また、振り分け処理部と第1のルール比較部をそれぞれハードウェアで実現することにより、処理速度の向上と省電力化が実現できる。更に、それらをパイプライン構造で動作させることにより、連続的に検索キーを処理することができる。これにより、第2のルール比較部を備え、遅延時間の小さく、連続でパケットが処理でき、省電力なパケット分類器を実現できる。本発明では、複数の決定木と複数の第1のルール比較部を用いて、複製を発生させることなく第1のルール比較部に配置されるルールの数を増やすことで、第2のルール比較部に配置されるルールの数を抑制できるため、第2のルール比較部の容量を少なくできる。本発明では、パケット分類器の設計の際に、ルールのプロファイルとして、ビット位置毎のワイルドカードの出現率とルール数を記憶する手段と、そのプロファイルを用いて振り分け処理での振り分けポリシーの決定手段と、第1のルール比較部構成の決定手段と、第2のルール比較部構成の決定手段を備えるため、パケット分類器の設計手法を提供できる。本発明では、ルールのプロファイルとして、ビット位置毎のワイルドカードが出現する確率と、その確率のバラつき具合と、ルール数を記憶する手段と、そのプロファイルを用いて振り分けポリシーの決定手段と、第1のルール比較部構成の決定手段と、第2のルール比較部構成の決定手段を確率的に決定する手段と、制約条件を基に構成を決定する手段を備えるため、確率的なパケット分類器の設計手法を提供できる。本発明では、その理由はルールのプロファイルとして、ビット位置毎のワイルドカードが出現する確率とルール数を記憶する手段と、そのプロファイルを用いて振り分け処理での振り分けポリシーの決定手段と、第1のルール比較部構成の決定手段と、第2のルール比較部構成の決定手段を備える。更に、ビット位置毎のワイルドカードが出現する確率のバラつきを基にして、バラつきが生じた場合に管理可能なルール数を評価する手段を備えるため、ロバスト性を考慮したパケット分類器の設計手法を提供できる。本発明によれば、パケットのヘッダ情報から特定のフィールドの組み合わせによって、パケットが属するフローを識別し、QoS処理や負荷分散等、フロー毎に特定の処理を行わせるスイッチやルータ等のネットワーク装置、及びロードバランサー等のアプライアンス装置といった用途に適用できる。<付記>上記の実施形態の一部又は全部は、以下の付記のように記載することも可能である。但し、実際には、以下の記載例に限定されない。付記1振り分け手段と、ルールを2つ以上に分類して記憶する第一のルール記憶手段と、ルールを分類せずに記憶する第2のルール記憶手段とを備えたことを特徴とするパケット分類システム。付記2前記振り分け手段は、1つ又は2つ以上の木構造で実現されていることを特徴とする。付記3前記振り分け手段は、パイプイラン構造で実現されていることを特徴とする。付記4一部のルールを2つ以上に分類して第1の記憶手段に予め記憶し、残りのルールを分類せずに第2の記憶手段に予め記憶し、入力された検索キーを分類し、分類結果に基づき第1の記憶手段中のルールと比較し、分類結果に関係なく第2の記憶手段中のルールと比較することを特徴とするパケット分類方法。付記5一部のルールを2つ以上に分類して第1の記憶手段に記憶するステップと、残りのルールを分類せずに第2の記憶手段に記憶するステップと、入力された検索キーを分類するステップと、分類結果に基づき第1の記憶手段中のルールと比較するステップと、分類結果に関係なく第2の記憶手段中のルールと比較するステップとをコンピュータに実行させるためのパケット分類用プログラム。付記6ルールのプロファイルを記憶する記憶手段と、振り分け処理部の構成を決定する手段と、ルール比較部の構成を決定する手段と、パケット分類システムの評価を行う評価手段とを備えたことを特徴とするパケット分類システム設計装置。付記7前記ルールのプロファイルには、ルール中のワイルドカード発生確率を含み、ルール比較部の構成を決定する際に、前記ワイルドカード発生確率を基に第1及び第2のルール比較部に格納するルール数を決定することを特徴とする。付記8前記ルールのプロファイルには、ルール中のワイルドカード発生確率のバラつきに関する指標を含み、ルール比較部の構成を決定する際に、前記ワイルドカード発生確率がバラついたとしても、ルールのあふれがないように、第1及び第2のルール記憶手段に格納するルール数を決定することを特徴とする。付記9前記ワイルドカード発生確率のバラつきに関する指標が、正規分布で与えられることを特徴とする。<備考>以上、本発明の実施形態を詳述してきたが、実際には、上記の実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の変更があっても本発明に含まれる。