パケット分類に用いられる複数の決定木のそれぞれを構成する複数の決定木処理ブロックと、前記複数の決定木処理ブロックに対してコマンドを一斉に入力するコマンド入力ブロックと、前記複数の決定木処理ブロックに接続されたエントリ追加対象決定ブロックとを備え、1つのルールは、前記複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理され、前記コマンドが検索コマンドである場合、前記複数の決定木処理ブロックの各々は、自身の決定木を用いることによって、検索キーがいずれかのルールにマッチするか否かを判定し、前記コマンドが新たなルールを決定木に追加するための挿入コマンドである場合、前記複数の決定木処理ブロックの各々は、前記新たなルールが自身の決定木における単一の葉ノードによって管理され得るかどうかを判定し、前記新たなルールが単一の葉ノードによって管理され得る場合、当該決定木処理ブロックはエントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、前記エントリ追加対象決定ブロックは、前記新たなルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択し、前記選択されたエントリ追加対象は、前記新たなルールを、自身の決定木における前記追加対象葉ノードが管理するルールリストに追加するパケット分類器。請求項1に記載のパケット分類器であって、前記エントリ追加対象候補は、前記追加対象葉ノードが管理している有効なルールのエントリ数を、前記エントリ追加対象決定ブロックに通知し、前記エントリ追加対象決定ブロックは、前記エントリ数に基づいて、前記エントリ追加対象を選択するパケット分類器。請求項2に記載のパケット分類器であって、前記エントリ追加対象決定ブロックは、前記エントリ数が最小である前記エントリ追加対象候補を、前記エントリ追加対象として選択するパケット分類器。請求項2又は3に記載のパケット分類器であって、前記複数の決定木処理ブロックの各々は、自身の決定木の各葉ノードによって管理されている有効なルールのエントリ数を記憶するエントリ数記憶ブロックを備え、前記エントリ追加対象候補は、前記追加対象葉ノードに関する前記エントリ数を前記エントリ数記憶ブロックから読み出し、前記読み出したエントリ数を前記エントリ追加対象決定ブロックに通知し、前記エントリ追加対象は、前記追加対象葉ノードに関する前記エントリ数に1を加算することにより、前記エントリ数記憶ブロックを更新するパケット分類器。請求項4に記載のパケット分類器であって、前記コマンドが既存ルールを削除するための削除コマンドである場合、前記複数の決定木処理ブロックの各々は、前記既存ルールが自身の決定木における単一の葉ノードによって管理されているか否かを判定し、前記既存ルールが単一の葉ノードによって管理されている場合、当該決定木処理ブロックはエントリ削除対象であり、当該単一の葉ノードは削除対象葉ノードであり、前記エントリ削除対象は、前記既存ルールを無効化し、また、前記削除対象葉ノードに関する前記エントリ数から1を減算することにより、前記エントリ数記憶ブロックを更新するパケット分類器。請求項2又は3に記載のパケット分類器であって、前記エントリ追加対象候補の各々は、前記追加対象葉ノードが管理するルールリストに前記新たなルールを一時的に追加する一時追加処理を行い、また、前記一時追加処理の最中に、当該ルールリスト中の有効なルールのエントリ数をカウントし、前記エントリ追加対象候補の各々は、前記一時追加処理において得られた前記エントリ数を、前記エントリ追加対象決定ブロックに通知し、前記選択されたエントリ追加対象以外の前記エントリ追加対象候補の各々は、前記一時的に追加された新たなルールを無効化する追加エントリ無効化処理を行うパケット分類器。請求項6に記載のパケット分類器であって、前記一時追加処理において、前記エントリ追加対象候補の各々は、前記ルールリスト中で前記新たなルールが追加された位置を示す位置情報を前記挿入コマンドに書き込み、前記選択されたエントリ追加対象以外の前記エントリ追加対象候補の各々は、前記位置情報を参照することによって、ルールマッチングを行うことなく、前記追加エントリ無効化処理を行うパケット分類器。請求項1乃至7のいずれか一項に記載のパケット分類器であって、前記複数の決定木処理ブロックの各々は、各決定木の段数と同じ段数の決定木ノード処理ブロックを備え、前記決定木ノード処理ブロックを用いることによって決定木の探索をパイプライン処理で行う決定木パイプラインブロックと、各葉ノードにおいて管理可能なルール数と同じ段数のルール処理ブロックを備え、前記ルール処理ブロックを用いることによってルールの検索、追加及び削除をパイプライン処理で行うルールパイプラインブロックとを備えるパケット分類器。複数の決定木を用いたパケット分類方法であって、1つのルールは、前記複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理され、前記パケット分類方法は、前記複数の決定木に対してコマンドを一斉に入力するステップと、前記コマンドが検索コマンドである場合、前記複数の決定木の各々において、検索キーがいずれかのルールにマッチするか否かを判定するステップと、前記コマンドが新たなルールを決定木に追加するための挿入コマンドである場合、前記複数の決定木の各々において、前記新たなルールが単一の葉ノードによって管理され得るかどうかを判定するステップと、ここで、前記新たなルールが単一の葉ノードによって管理され得る場合、当該決定木はエントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、前記新たなルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択するステップと、前記新たなルールを、前記エントリ追加対象の前記追加対象葉ノードが管理するルールリストに追加するステップとを含むパケット分類方法。複数の決定木を用いたパケット分類処理をコンピュータに実行させるためのパケット分類プログラムであって、1つのルールは、前記複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理され、前記パケット分類処理は、前記複数の決定木に対してコマンドを一斉に入力するステップと、前記コマンドが検索コマンドである場合、前記複数の決定木の各々において、検索キーがいずれかのルールにマッチするか否かを判定するステップと、前記コマンドが新たなルールを決定木に追加するための挿入コマンドである場合、前記複数の決定木の各々において、前記新たなルールが単一の葉ノードによって管理され得るかどうかを判定するステップと、ここで、前記新たなルールが単一の葉ノードによって管理され得る場合、当該決定木はエントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、前記新たなルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択するステップと、前記新たなルールを、前記エントリ追加対象の前記追加対象葉ノードが管理するルールリストに追加するステップとを含むパケット分類プログラム。決定木を用いたパケット分類では、その決定木に対して新たなルールを追加したり、その決定木から既存ルールを削除したりすることも重要である。そのようなルールの追加/削除処理は、以下、エントリの動的更新と参照される。非特許文献3では、エントリの動的更新を行うための具体的な手順については述べられていない。従って、どの決定木のどのノードにおけるルールを更新するのか、あらかじめ決定しておく必要があると考えられる。すなわち、エントリの動的更新を行うために、前処理が別途必要になるという問題がある。特に、非特許文献3では、予め与えられたルールセットに対して最適な決定木を構成することを前提としているため、最悪の場合には、決定木の構成自体を全て変更する必要があると考えられる。そのような場合には、エントリの動的更新の前処理に必要な時間と、エントリ更新に必要な時間が共に増大してしまうという問題がある。本発明の1つの目的は、決定木を用いたパケット分類において、前処理を行うことなく、エントリの動的更新を実現することができる技術を提供することにある。本発明の1つの観点において、パケット分類器が提供される。そのパケット分類器は、パケット分類に用いられる複数の決定木のそれぞれを構成する複数の決定木処理ブロックと、複数の決定木処理ブロックに対してコマンドを一斉に入力するコマンド入力ブロックと、複数の決定木処理ブロックに接続されたエントリ追加対象決定ブロックと、を備える。1つのルールは、複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理される。コマンドが検索コマンドである場合、複数の決定木処理ブロックの各々は、自身の決定木を用いることによって、検索キーがいずれかのルールにマッチするか否かを判定する。コマンドが新たなルールを決定木に追加するための挿入コマンドである場合、複数の決定木処理ブロックの各々は、新たなルールが自身の決定木における単一の葉ノードによって管理され得るかどうかを判定する。新たなルールが単一の葉ノードによって管理され得る場合、当該決定木処理ブロックはエントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードである。この場合、エントリ追加対象決定ブロックは、新たなルールを追加する対象であるエントリ追加対象を、エントリ追加対象候補の中から選択する。そして、選択されたエントリ追加対象は、新たなルールを、自身の決定木における追加対象葉ノードが管理するルールリストに追加する。本発明の他の観点において、複数の決定木を用いたパケット分類方法が提供される。1つのルールは、複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理される。本発明に係るパケット分類方法は、A複数の決定木に対してコマンドを一斉に入力するステップと、Bコマンドが検索コマンドである場合、複数の決定木の各々において、検索キーがいずれかのルールにマッチするか否かを判定するステップと、Cコマンドが新たなルールを決定木に追加するための挿入コマンドである場合、複数の決定木の各々において、新たなルールが単一の葉ノードによって管理され得るかどうかを判定するステップと、ここで、新たなルールが単一の葉ノードによって管理され得る場合、当該決定木はエントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、D新たなルールを追加する対象であるエントリ追加対象を、エントリ追加対象候補の中から選択するステップと、E新たなルールを、エントリ追加対象の追加対象葉ノードが管理するルールリストに追加するステップと、を含む。本発明の更に他の観点において、複数の決定木を用いたパケット分類処理をコンピュータに実行させるためのパケット分類プログラムが提供される。1つのルールは、複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理される。本発明に係るパケット分類処理は、A複数の決定木に対してコマンドを一斉に入力するステップと、Bコマンドが検索コマンドである場合、複数の決定木の各々において、検索キーがいずれかのルールにマッチするか否かを判定するステップと、Cコマンドが新たなルールを決定木に追加するための挿入コマンドである場合、複数の決定木の各々において、新たなルールが単一の葉ノードによって管理され得るかどうかを判定するステップと、ここで、新たなルールが単一の葉ノードによって管理され得る場合、当該決定木はエントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、D新たなルールを追加する対象であるエントリ追加対象を、エントリ追加対象候補の中から選択するステップと、E新たなルールを、エントリ追加対象の追加対象葉ノードが管理するルールリストに追加するステップと、を含む。本発明によれば、決定木を用いたパケット分類において、前処理を行うことなく、エントリの動的更新を実現することが可能となる。添付図面を参照して、本発明の実施の形態を説明する。1.第1の実施の形態1-1.概要図4は、本発明の第1の実施の形態に係るパケット分類器1の構成を示すブロック図である。パケット分類器1は、決定木を用いることによりパケット分類を行う。つまり、パケット分類器1は、パケットヘッダから抽出された検索キーがどのルールにマッチするかを、決定木を用いることにより判定する。更に、本実施の形態に係るパケット分類器1は、入力コマンドに応じて、エントリの動的更新新規ルールの追加、既存ルールの削除を自動的に行う。本実施の形態において、パケット分類器1は、ハードウェア回路により実現される。より詳細には、図4に示されるように、パケット分類器1は、1個以上の複数の決定木処理ブロック22-1~2-N:Nは2以上の整数、エントリ追加対象決定ブロック3、コマンド入力ブロック4、及び結果出力ブロック5を備えている。また、パケット分類器1には入力データ6が入力され、パケット分類器1からは出力データ7が出力される。入力データ6は、パケット分類器1が実行すべき処理に依存する。パケット分類器1が実行する処理としては、1検索キーにマッチするルールを検索する処理以下、LOOKUP処理と参照される、2新規ルール新規エントリを決定木に追加する処理以下、INSERT処理と参照される、及び3既存ルール既存エントリを無効化する処理以下、DELETE処理と参照される、4パケット分類器1に含まれるメモリや設定レジスタ等へ予め設定値を書き込むConfiguration処理、が挙げられる。ここで、Configuration処理は初期化時に行われ、パケット分類器1に含まれる各ブロック内に備えられた設定レジスタやメモリへ構成に関わる値を設定することである。以下では、LOOKUP処理、INSERT処理、DELETE処理に関してのみ説明する。入力データ6は、処理種別を示す種別データと、当該処理で用いられるデータとを含む。LOOKUP処理の場合、入力データ6は、LOOKUP処理を示す種別データと、検索キーとを含む。INSERT処理の場合、入力データ6は、INSERT処理を示す種別データと、追加すべき新規ルールとを含む。DELETE処理の場合、入力データ6は、DELETE処理を示す種別データと、無効化すべき既存ルールとを含む。コマンド入力ブロック4は、入力データ6を受け取り、その入力データ6に応じたコマンドを作成する。入力データ6の場合と同様に、コマンドは、処理種別を示す種別データと、当該処理で用いられるデータとを含む。LOOKUP処理の実行を指示する検索コマンドは、LOOKUP処理を示す種別データと、検索キーとを含む。INSERT処理の実行を指示する挿入コマンドは、INSERT処理を示す種別データと、追加すべき新規ルールとを含む。DELETE処理の実行を指示する削除コマンドは、DELETE処理を示す種別データと、無効化すべき既存ルールとを含む。コマンド入力ブロック4は、生成したコマンドを、複数の決定木処理ブロック2-1~2-Nに対して一斉に入力する。複数の決定木処理ブロック2-1~2-Nのそれぞれは、パケット分類に用いられる複数の決定木を構成する。ここで、複数の決定木は、非特許文献3に記載されている手法と同様に、ルールの複製が生じないように構成される。つまり、各ルールは、当該ルールの複製が生じない決定木において管理される。言い換えれば、1つのルールは、複数の決定木のうちいずれか1つの決定木における単一の葉ノードでのみ管理される。各決定木処理ブロック2は、コマンド入力ブロック4から入力されたコマンドに応じて、LOOKUP処理、INSERT処理、あるいはDELETE処理を実行する。尚、複数の決定木処理ブロック2-1~2-Nは、同時並列に各処理を実行することができる。<LOOKUP処理>複数の決定木処理ブロック2-1~2-Nは、検索コマンドに応じて、LOOKUP処理を同時並列に実行する。具体的には、各決定木処理ブロック2は、自身の決定木を用いることによって、検索キーがいずれかの葉ノードで管理されているいずれかのルールにマッチするか否かを判定する。検索キーにマッチするルールが存在する場合、当該決定木処理ブロック2は、当該マッチルールを結果出力ブロック5に通知する。検索キーが当該葉ノードにおけるルールリストに含まれるルールの複数にマッチする場合、当該決定木処理ブロック2は、複数のマッチルールのうち最も優先度の高いルールを結果出力ブロック5に通知する。一方、検索キーにマッチするルールが存在しない場合、当該決定木処理ブロック2は、マッチルールが存在しなかったことを結果出力ブロック5に通知する。結果出力ブロック5は、複数の決定木処理ブロック2-1~2-Nから検索結果を受け取り、最も優先度の高いマッチルールを選択する。そして、結果出力ブロック5は、その選択結果を示す出力データ7を、LOOKUP処理の最終結果として出力する。<INSERT処理>複数の決定木処理ブロック2-1~2-Nは、挿入コマンドに応じて、INSERT処理を同時並列に実行する。具体的には、まず、各決定木処理ブロック2は、新規ルールを自身の決定木に追加してもルールの複製が発生しないかどうか判定する。言い換えれば、各決定木処理ブロック2は、新規ルールが自身の決定木における単一の葉ノードによってのみ管理され得るかどうかを判定する。ルールの複製が発生してしまう場合、当該決定木処理ブロック2は、新規ルールの追加対象とはならない。一方、ルールの複製が発生しない場合、すなわち、新規ルールが自身の決定木における単一の葉ノードによってのみ管理され得る場合、当該決定木処理ブロック2はエントリ追加対象候補となり、当該単一の葉ノードは追加対象葉ノードとなる。新規ルールが追加される対象である決定木処理ブロック2は、エントリ追加対象である。エントリ追加対象は、上記エントリ追加対象候補の中から選ばれる。そのエントリ追加対象を選ぶのが、エントリ追加対象決定ブロック3である。図4に示されるように、このエントリ追加対象決定ブロック3は、複数の決定木処理ブロック2-1~2-Nの各々に接続されている。そして、エントリ追加対象決定ブロック3は、複数の決定木処理ブロック2-1~2-Nから通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。例えば、各エントリ追加対象候補は、追加対象葉ノードが管理している有効なルールのエントリ数を、エントリ追加対象決定ブロック3に通知する。そして、エントリ追加対象決定ブロック3は、各エントリ追加対象候補から受け取った有効エントリ数を参照し、所定のポリシーに従って、エントリ追加対象を選択する。例えば、エントリ追加対象決定ブロック3は、当該有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択する。この場合、複数の決定木間でのルール数の偏りが抑えられ、好適である。エントリ追加対象決定ブロック3は、エントリ追加対象の選択結果を各決定木処理ブロック2に通知する。例えば、エントリ追加対象決定ブロック3は、エントリ追加対象に対して新規ルールの追加を指示し、それ以外の決定木処理ブロック2に対してルール追加処理の不実行を指示する。そして、エントリ追加対象である決定木処理ブロック2は、新規ルールを、自身の決定木における追加対象葉ノードが管理するルールリストに追加する。このようにして、INSERT処理が実行される。結果出力ブロック5は、複数の決定木処理ブロック2-1~2-Nから処理結果を受け取り、INSERT処理の最終結果を示す出力データ7を出力する。<DELETE処理>複数の決定木処理ブロック2-1~2-Nは、削除コマンドに応じて、DELETE処理を同時並列に実行する。具体的には、各決定木処理ブロック2は、削除対象である既存ルールが自身の決定木における単一の葉ノードによって管理されているか否かを判定する。当該既存ルールが単一の葉ノードによって管理されている場合、当該決定木処理ブロック2はエントリ削除対象となり、当該単一の葉ノードは削除対象葉ノードとなる。エントリ削除対象である決定木処理ブロック2は、削除対象葉ノードが管理していた当該既存ルールを無効化する。このようにして、DELETE処理が実行される。結果出力ブロック5は、複数の決定木処理ブロック2-1~2-Nから処理結果を受け取り、DELETE処理の最終結果を示す出力データ7を出力する。以上に説明されたように、本実施の形態によれば、ルールの複製が発生しない。特に、エントリの動的更新においても、ルールの複製が発生しないようにINSERT処理が実行される。比較例として、ルールの複製が許容された決定木に対してエントリの動的更新が実施される場合を考える。エントリの動的更新では、更新するエントリのメモリ上のデータ保存領域のデータを書き換える必要がある。ルールの複製が存在する場合には、その複製回数だけデータ書き換えが必要になる。従って、INSERT処理やDELETE処理において、その処理時間が毎回一定ではなくなり、場合によっては処理時間が非常に増大してしまう。本実施の形態によれば、このような問題が解決される。すなわち、INSERT処理やDELETE処理といったエントリの動的更新に要する処理時間が一定となる。更に、本実施の形態によれば、INSERT処理時、複数の決定木処理ブロック2-1~2-Nの各々が、挿入コマンドを受け取り、その挿入コマンドに応じて、自身がエントリ追加対象候補か否かを自動的に判定する。エントリ追加対象決定ブロック3は、少なくともエントリ追加対象候補から通知される情報に基づいて、適切なエントリ追加対象を自動的に決定する。そして、エントリ追加対象は、新規ルールを追加対象葉ノードに自動的に追加する。また、DELETE処理時、複数の決定木処理ブロック2-1~2-Nの各々が、削除コマンドを受け取り、その削除コマンドに応じて、自身がエントリ削除対象か否かを自動的に判定する。そして、エントリ削除対象は、削除対象葉ノード中の指定されたルールを自動的に無効化する。このように、エントリの動的更新は、コマンドに応じて自動的に実施される。どの決定木のどのノードにおけるルールを更新するのか予め決定しておくといった前処理は不要である。すなわち、本実施の形態によれば、決定木を用いたパケット分類において、前処理を行うことなく、エントリの動的更新を実現することが可能となる。尚、本実施の形態に係るパケット分類器1は、例えば、スイッチやルータ等のネットワーク装置内や、サーバの拡張カードやオンボードで搭載されるNICNetworkInterfaceCard内に配備される。この場合、パケット分類器1は、制御ブロックと接続される。その制御ブロックは、到着したパケットのヘッダを解析する機能、当該パケットヘッダから検索キーを抽出する機能、その検索キーを用いたLOOKUP処理をパケット分類器1に実行させる機能を有する。更に、制御ブロックは、外部から指定される新規ルールを追加するINSERT処理をパケット分類器1に実行させる機能、及び外部から指定される既存ルールを削除するDELETE処理をパケット分類器1に実行させる機能を有する。パケット分類器1は、処理に応じた入力データ6を制御ブロックから受け取り、出力データ7を制御ブロックに出力する。1-2.構成例次に、本実施の形態に係るパケット分類器1の構成例を更に詳しく説明する。図5は、本実施の形態に係るパケット分類器1の各決定木処理ブロック2の構成を示すブロック図である。図5に示されるように、決定木処理ブロック2は、決定木パイプラインブロック20、エントリ数カウントブロック21、及びルールパイプラインブロック22を備えている。コマンド入力ブロック4から決定木処理ブロック2に入力されるデータは、入力データ23である。決定木処理ブロック2から結果出力ブロック5に出力されるデータは、出力データ24である。決定木処理ブロック2とエントリ追加対象決定ブロック3との間でやりとりされるデータは、入出力データ25である。1-2-1.決定木パイプラインブロック20決定木パイプラインブロック20は、パイプライン処理により決定木の探索を行う。具体的には、決定木パイプラインブロック20は、決定木の深さ段数Hと同じ段数の決定木ノード処理ブロック200-1~200-Hを備えている。図6に示されるように、決定木ノード処理ブロック200-ii=1、2、、Hは、決定木の根ノードから深さjj=0、1、、H-1のノードに対応しており、当該ノードに関する処理を行う。これら決定木ノード処理ブロック200-1~200-Hを用いることによって、決定木パイプラインブロック20は、決定木の根ノードから葉ノードに向けて1ノードずつ探索処理を実行していく。好適には、1クロックサイクル毎に、決定木の1つのノードを辿る処理が実行される。図7は、本実施の形態に係る決定木ノード処理ブロック200の構成を示すブロック図である。図7に示されるように、決定木ノード処理ブロック200は、子ノード決定ブロック2000及びノード情報記憶ブロック2001を備えている。ノード情報記憶ブロック2001は、メモリやレジスタ等の記憶媒体により構成され、ノード情報を記憶する。ノード情報は、根ノードから見て同じ深さにある全てのノードの各々に関して、当該ノードにおける領域分割情報、つまり当該ノードによって管理される子ノード分割領域に対する情報を示す。決定木ノード処理ブロック200は、前段の決定木ノード処理ブロック200から入力データ2002を受け取る。但し、決定木ノード処理ブロック200-1は、コマンド入力ブロック4から入力データ2002=入力データ23を受け取る。入力データ2002は、各処理に応じたコマンドと、ノード情報記憶ブロック2001へのアクセスに用いられるアドレス値を含んでいる。前段の決定木ノード処理ブロック200からの入力データ2002は、更に、後述される有効ビット長の情報も含んでいる。子ノード決定ブロック2000は、入力データ2002を受け取り、その入力データ2002で指定されているアドレス値を参照してノード情報記憶ブロック2001からノード情報を読み出す。そして、子ノード決定ブロック2000は、ノード情報、有効ビット長及びコマンドに基づいて、当該ノードの子ノードのノード情報が記憶されているアドレス値を算出する。また、子ノード決定ブロック2000は、有効ビット長を更新する。アドレス値の算出や有効ビット長の更新に関しては、後に詳しく説明される。出力データ2003は、入力データ2002に含まれていたコマンド、算出された新しいアドレス値、及び更新後の有効ビット長を含む。子ノード決定ブロック2000は、その出力データ2003を、次段の決定木ノード処理ブロック200に出力する。最終段の決定木ノード処理ブロック200-Hに関しては、次の通りである。LOOKUP処理あるいはDELETE処理の場合、子ノード決定ブロック2000によって算出されるアドレス値は、ルールパイプラインブロック22のルール処理ブロック220のエントリ記憶ブロック2201後述されるへのアクセスに用いられるアドレス値である。決定木ノード処理ブロック200-Hは、出力データ2003をルール処理ブロック220-1に出力する。また、INSERT処理の場合、子ノード決定ブロック2000によって算出されるアドレス値は、エントリ数カウントブロック21のエントリ数記憶ブロック211後述されるへのアクセスに用いられるアドレス値である。出力データ2004は、入力データ2002に含まれていたコマンドと算出されたアドレス値を含む。子ノード決定ブロック2000は、その出力データ2004を、エントリ数カウントブロック21に出力する。1-2-2.エントリ数カウントブロック21エントリ数カウントブロック21は、決定木の全ての葉ノードに関して、管理されている有効なルールのエントリ数を葉ノード毎に管理する。尚、エントリ数カウントブロック21による処理は、決定木の深さHに相当する処理サイクルにおいて実行される。図8は、本実施の形態に係るエントリ数カウントブロック21の構成を示すブロック図である。図8に示されるように、エントリ数カウントブロック21は、カウント処理ブロック210及びエントリ数記憶ブロック211を備えている。エントリ数記憶ブロック211は、メモリやレジスタ等の記憶媒体により構成され、エントリ数情報を記憶する。エントリ数情報は、決定木の各葉ノードによって管理されている有効なルールのエントリ数を示す。INSERT処理の場合、カウント処理ブロック210は、決定木パイプラインブロック20の決定木ノード処理ブロック200-Hから入力データ212=上述の出力データ2004を受け取る。その入力データ212は、挿入コマンド、及びエントリ数記憶ブロック211へのアクセスに用いられるアドレス値を含む。カウント処理ブロック210は、そのアドレス値を参照して、エントリ数記憶ブロック211から追加対象葉ノードに関するエントリ数情報有効ルールエントリ数を読み出す。そして、カウント処理ブロック210は、読み出した有効ルールエントリ数を示す出力データ216を、上述のエントリ追加対象決定ブロック3に出力する。また、カウント処理ブロック210は、エントリ追加対象決定ブロック3から入力データ216を受け取る。その入力データ216が決定木への新規ルールの追加を指定している場合、カウント処理ブロック210は、上記追加対象葉ノードに関する有効ルールエントリ数に1を加算し、エントリ数記憶ブロック211に書き込む。これにより、エントリ数記憶ブロック211が最新状態に更新される。更に、カウント処理ブロック210は、出力データ214を、ルールパイプラインブロック22のルール処理ブロック220-1に出力する。その出力データ214は、挿入コマンドと、ルール処理ブロック220-1のエントリ記憶ブロック2201後述されるへのアクセスに用いられるアドレス値を含む。DELETE処理の場合、カウント処理ブロック210は、ルールパイプラインブロック22のルール処理ブロック220-Bから入力データ213を受け取る。カウント処理ブロック210は、その入力データ213で指定されるアドレス値を参照して、エントリ数記憶ブロック211から削除対象葉ノードに関するエントリ数情報有効ルールエントリ数を読み出す。そして、カウント処理ブロック210は、当該有効ルールエントリ数から1を減算し、エントリ数記憶ブロック211に書き込む。これにより、エントリ数記憶ブロック211が最新状態に更新される。更に、カウント処理ブロック210は、DELETE処理の完了を示す出力データ215を、出力データ24として結果出力ブロック5に出力する。1-2-3.ルールパイプラインブロック22ルールパイプラインブロック22は、パイプライン制御によりルール処理検索キーにマッチするルールの検索、新規ルールの追加、既存ルールの削除を行う。具体的には、ルールパイプラインブロック22は、各葉ノードにおいて管理可能な最大ルール数ルールリストのサイズBと同じ段数のルール処理ブロック220-1~220-Bを備えている。図9に示されるように、ルール処理ブロック220-ii=1、2、、Bは、当該葉ノードのルールリストに含まれるルールjj=1、2、Bに対応付けられており、当該ルールjに関するルール処理を実行する。これらルール処理ブロック220-1~220-Bを用いることによって、ルールパイプラインブロック22は、葉ノードのルールリストに含まれる各ルールに対してルール処理を実行する。好適には、1クロックサイクル毎に、1つのルールに対するルール処理が実行される。図10は、本実施の形態に係るルール処理ブロック220の構成を示すブロック図である。図10に示されるように、ルール処理ブロック220は、比較更新処理ブロック2200及びエントリ記憶ブロック2201を備えている。エントリ記憶ブロック2201は、メモリやレジスタ等の記憶媒体により構成され、エントリ情報を記憶する。エントリ情報は、当該ルールが有効か無効かを示す有効フラグ、ルールID、ルール等を含む。LOOKUP処理あるいはDELETE処理の場合、ルール処理ブロック220-1は、決定木パイプラインブロック20の決定木ノード処理ブロック200-Hから入力データ2202=上述の出力データ2003を受け取る。入力データ2202は、各処理に応じたコマンドと、エントリ記憶ブロック2201へのアクセスに用いられるアドレス値を含んでいる。INSERT処理の場合、ルール処理ブロック220-1は、エントリ数カウントブロック21から入力データ2203=上述の出力データ214を受け取る。入力データ2203は、挿入コマンドと、エントリ記憶ブロック2201へのアクセスに用いられるアドレス値を含んでいる。入力データ2203は、これ以降、上記入力データ2202と同様に扱われる。比較更新処理ブロック2200は、入力データ2202を受け取り、その入力データ2202で指定されているアドレス値を参照してエントリ記憶ブロック2201からエントリ情報を読み出す。そして、比較更新処理ブロック2200は、読み出したエントリ情報に基づいて、コマンドに応じたルール処理を実行する。ルール処理の詳細は後述される。また、比較更新処理ブロック2200は、受け取った入力データ2202を出力データ2204として、次段のルール処理ブロック220に出力する。ルール処理ブロック220-2~220-Bの各々は、前段のルール処理ブロック220から入力データ2202=上述の出力データ2204を受け取る。比較更新処理ブロック2200による処理は、上記と同じである。尚、DELETE処理の場合、最終段のルール処理ブロック220-Bの比較更新処理ブロック2200は、出力データ2204の代わりに出力データ2205=上述の入力データ213をエントリ数カウントブロック21に出力する。出力データ2205の内容は、出力データ2204と同じである。1-3.動作次に、本実施の形態に係るパケット分類器1の動作を詳しく説明する。1-3-1.LOOKUP処理まず、LOOKUP処理を説明する。図11は、本実施の形態におけるLOOKUP処理を示すフローチャートである。ステップA1:パケット分類器1に、入力データ6が入力される。その入力データ6は、LOOKUP処理を示す種別データと、被検索対象パケットから抽出された検索キーとを含む。コマンド入力ブロック4は、その入力データ6を受け取る。コマンド入力ブロック4は、その入力データ6に基づいて装置内コマンドここでは、検索コマンドを生成し、その装置内コマンドを決定木処理ブロック2-1~2-Nに一斉に出力する。図12は、装置内コマンドの構成例を示す概念図である。コマンド部分は、処理種別、終了フラグ、及び結果フラグを含んでいる。例えば、2ビットデータである処理種別は、00であればLOOKUP処理、01であればINSERT処理、10であればDELETE処理を示す。終了フラグは、‘0’であれば未終了、‘1’であれば終了を示す。結果フラグは、エントリの追加、削除を行った場合に、‘1’に設定される。尚、終了フラグと結果フラグについては、INSERT処理及びDELETE処理においてのみ参照され、それらの利用方法については後述する。また、装置内コマンドの後半部分には、検索キーLOOKUP処理、追加される新規エントリINSERT処理、あるいは、削除される既存エントリDELETE処理が格納される。ここで、エントリルールは、PrefixMatch、RangeMatch、WildcardMatchを考慮すると様々な表現形態が考えられる。例えば、検索キー長と同じ長さのデータ列A、Bを用意し、PrefixMatchやWildcardMatchの場合には、Aに対象データ、Bにマスクビットデータを割り当て、RangeMatchの場合には、Aに下限値、Bに上限値を割り当てる方法が考えられる。この場合、ルールのエントリ長は検索キー長の2倍となる。これらを考慮し、装置内コマンドの後半部分においては、LOOKUP処理時の検索キーと、INSERT、DELETE処理時の追加削除エントリの長さが異なることを許容する。なお、追加エントリの場合には、その優先度も指定される。ステップA2:コマンド入力ブロック4から検索コマンドを受け取ると、各決定木処理ブロック2は、指定された検索キーを用いて、自身の決定木を辿る処理を実行する。図13は、本ステップA2の処理を示すフローチャートである。ステップB1:決定木を辿る処理は、決定木の根ノードから開始する。そのため、まず、現在の処理ノードが、決定木の根ノードに設定される。具体的には、挿入コマンドが、決定木パイプラインブロック20の初段の決定木ノード処理ブロック200-1に入力される。ステップB2:子ノード決定ブロック2000は、処理種別がLOOKUPであることを確認した上で、ノード情報記憶ブロック2001からノード情報を読み出す。図14は、ノード情報の構成例を示す概念図である。ノード情報は、当該ノードにおける領域分割情報である。図14に示されるように、ノード情報は、フィールド識別子フィールドIDとその分割数kのC個のペア、及びベースアドレスを含んでいる。ここで、Cは決定木の1ノードにおける領域分割に用いることができるフィールドの最大数である。フィールドIDは、検索キーやルールを構成するフィールド毎に予め決められている。また、各フィールドの範囲は、2k分割されるとしkは自然数、分割数kはその指数を表す。例えば、既出の図1~図3の例のように、フィールドX、Yの各々の範囲が2分割される場合、フィールドXの分割数kは1であり、フィールドYの分割数kも1である。尚、kの最大数は予め決められている。ベースアドレスは、当該ノードの子ノードのノード情報が格納されている記憶領域の最小アドレス値を示す。より詳細には、ベースアドレスは、当該ノードの子ノードのノード情報が格納されている次段の決定木ノード処理ブロック200のノード情報記憶ブロック2001における最小アドレス値であり、当該ノードの全ての子ノードのノード情報は、このベースアドレスから連続する記憶領域に格納されている。ステップB3:子ノード決定ブロック2000は、読み出したノード情報、検索キーの各フィールドのビット列、及び有効ビット長に基づいて、次段の子ノードのノード情報が格納されている記憶領域のアドレス値を算出する。具体的には、次のようにして次段のアドレス値は算出される図15も参照されたい。例えば、ノード情報として、2つのフィールドに関する分割情報フィールドID、分割数=0001、01、0100、11とベースアドレス=00001000が設定されているとする。検索キーにおいては、フィールドID=0001のフィールド値が0101、フィールドID=0100のフィールド値が0110であり、それぞれの有効ビット長が3、4であったとする。ここで、有効ビット長とは、各フィールドのビット列に対し、領域分割に用いる下位ビットからの長さに相当する。つまり、フィールド値のうち、有効ビット長で指定された長さをもつ下位ビットからのビット列が参照される。フィールドID=0001に関して説明する。有効ビット長が3であることから、フィールド値の下位3ビット101を参照する。そして、分割数k=1であるため、有効ビットの上位1ビットを参照し、‘1’を得る図15参照。同様に、フィールドID=0100に関しては、有効ビット長が4、分割数kが3であることから、011を得る。これらを連結した1011に対して、ベースアドレス00001000が加算される。その結果得られる00010011が、次段の子ノードのノード情報が格納されている記憶領域のアドレス値である。ステップB4:続いて、子ノード決定ブロック2000は、入力された有効ビット長から分割数kを減算することによって、有効ビット長を更新する。上記の例では、フィールドID=0001の有効ビット長が3-1=2に、フィールドID=0100の有効ビット長が4-3=1に更新される。尚、決定木ノード処理ブロック200-1には有効ビット長が入力されないが、その場合の有効ビット長は、予め各フィールドのフィールド長として設定されているものとする。それ以降の決定木ノード処理ブロック200に対しては、前段の決定木ノード処理ブロック200から有効ビット長が入力される。ステップB5、B6:次に、子ノードが葉ノードであるか否かが判定される。具体的には、決定木ノード処理ブロック200-Hが処理するノードの子ノードが葉ノードであるため図6参照、処理する決定木ノード処理ブロック200が自動的に判別すればよい。次ノードが葉ノードではない場合ステップB5;Noは、決定木ノード処理ブロック200-ii=1、2、、H-1の場合に相当する。その決定木ノード処理ブロック200-iは、次段の決定木ノード処理ブロック200-i1に出力データ2003を出力するステップB6。その出力データ2003は、入力データ2002に含まれていたコマンド、算出された新しいアドレス値、及び更新後の有効ビット長を含む。そして、処理はステップB2に戻り、次段のノードが処理ノードとなる。次ノードが葉ノードである場合ステップB5;Yesは、決定木ノード処理ブロック200-Hの場合に相当する。この場合、ステップA2が終了する。ステップA3:ステップA2が終了すると、決定木ノード処理ブロック200-Hは、ルールパイプラインブロック22のルール処理ブロック220-1に、算出したアドレス値とコマンドを含む出力データ2003を出力する。ステップA4:続いて、ルールパイプラインブロック22が、検索キーとルールリスト中の各ルールとの比較マッチング処理を行う。図16は、本ステップA4の処理を示すフローチャートである。ステップC1:マッチング処理は、ルールリスト中の1番目のルールから開始する。具体的には、初段のルール処理ブロック220-1から処理を開始する。ステップC2:比較更新処理ブロック2200は、処理種別がLOOKUPであることを確認した上で、入力されたアドレス値を用いてエントリ記憶ブロック2201からエントリ情報を読み出す。そして、比較更新処理ブロック2200は、有効フラグを確認する。図17は、エントリ情報の構成例を示す概念図である。エントリ情報は、当該ルールが有効であるかを示す有効フラグ、ルールID、ルール、優先度を含んでいる。ルールに対応するアクションを同時に記憶する場合には、アクションを加えても良い。ここでは、アクションは本パケット分類器1とは異なる場所で管理されており、本パケット分類器1によって検索を行った後に、当該ルールIDを用いることによりアクションが取得されるとする。なお、図17のエントリ情報の構成例では、ルールIDを含んでいたが、これをエントリ情報には含まず、例えば、処理を行った決定木処理ブロックのID、葉ノードのID、ルールリストの順序等からルールIDを生成しても良い。より具体的には、処理を行った決定木処理ブロック2-ii=1、2、、Nのi、決定木処理ブロック2-iで辿り着いた葉ノードのIDであるj、ルール処理ブロック220-kk=1、2、、Bのkを2進数で連結したものをルールIDとして参照することが可能である。ステップC4:ルールが有効である場合ステップC3;Yes、比較更新処理ブロック2200は、検索キーと読み出したルールとの比較を行う。この比較方法については、例えば、非特許文献2に開示されている。ステップC6:検索キーがルールにマッチした場合ステップC5;Yes、比較更新処理ブロック2200は、当該ルールの優先度と現在のマッチルールの優先度を比較する。ここで、現在のマッチルールとは、前段のルール処理ブロック220までにマッチしたルールのうち、最も優先度が高いルールを意味する。一方、現在のルール処理ブロック220において比較に用いられたルールは、比較ルールと参照される。ステップC8:比較ルールの優先度の方が大きかった場合ステップC7;Yes、比較更新処理ブロック2200は、比較ルールを新たな現在のマッチルールに設定する。その後、処理は、ステップC9に進む。ステップC9、C10、C11:現在のルールが、ルールリスト中の最後のルールか否かが判定される。具体的には、ルール処理ブロック220-ii=1、2、、B-1が処理を実行している場合、それは最後のルールではないステップC9;No。この場合、そのルール処理ブロック220-iは、次段のルール処理ブロック220-i1に、アドレス値とコマンドを含む出力データ2204を出力するステップC10。そして、処理はステップC2に戻り、ルールリスト中の次のルールに対するマッチング処理が実行される。尚、読み出したルールが有効で無い場合ステップC3;No、及び、検索キーがルールにマッチしない場合ステップC5;No、更に、比較ルールの優先度がマッチルールの優先度よりも小さかった場合ステップC7;Noにも、処理はステップC9に進む。現在のルールがルールリスト中の最後のルールである場合、つまり、処理がルール処理ブロック220-Bで行われた場合ステップC9;Yes、ルール処理ブロック220-Bは、マッチルールのルールIDと優先度、及びコマンドを、結果出力ブロック5に出力するステップC11。そして、ステップA4が終了する。尚、マッチルールが存在しない場合には、例えば、ルールIDのビット値が全て1であるような特値を出力することで、マッチルールが存在しなかったことを示す。ステップA5:結果出力ブロック5は、複数の決定木処理ブロック2-1~2-Nから検索結果を受け取る。結果出力ブロック5は、マッチルールの優先度同士を比較し、最も優先度の高いマッチルールを選択する。そして、結果出力ブロック5は、その選択結果を示す出力データ7として、例えば、最高優先度であったマッチルールのルールIDを、LOOKUP処理の最終結果として出力する。このとき、マッチルールが存在しなかった場合には、上述した特値のルールIDを出力することで、マッチルールが存在しなかったことを示すことができる。1-3-2.INSERT処理次に、INSERT処理を説明する。図18は、本実施の形態におけるINSERT処理を示すフローチャートである。ステップA1:パケット分類器1に、入力データ6が入力される。その入力データ6は、INSERT処理を示す種別データと、追加される新規ルールとを含む。コマンド入力ブロック4は、その入力データ6を受け取る。コマンド入力ブロック4は、その入力データ6に基づいて装置内コマンドここでは、挿入コマンドを生成し、その装置内コマンドを決定木処理ブロック2-1~2-Nに一斉に出力する。ステップA6:コマンド入力ブロック4から挿入コマンドを受け取ると、各決定木処理ブロック2は、指定された新規ルールを用いて、自身の決定木を辿る処理を実行する。図19は、本ステップA6の処理を示すフローチャートである。ステップB1:まず、LOOKUP処理の場合と同様に、現在の処理ノードが、決定木の根ノードに設定される。ステップB7:子ノード決定ブロック2000は、処理種別がINSERTであることを確認した上で、コマンド内の終了フラグを参照する。終了フラグが‘1’である場合ステップB7;Yes、処理はステップB5に進む。一方、終了フラグが‘0’である場合ステップB7;No、処理はステップB2に進む。ステップB2:LOOKUP処理の場合と同様に、子ノード決定ブロック2000は、ノード情報記憶ブロック2001からノード情報を読み出す。ステップB8:子ノード決定ブロック2000は、読み出したノード情報、新規ルールの各フィールドのビット列、及び有効ビット長に基づいて、ルールの複製が発生するか否か判定する。ルールの複製が発生するか否かは、アドレス値の算出を行う際に、ワイルドカードが含まれるか否かで判断することができる。例えば、ノード情報として、2つのフィールドに対する領域分割情報フィールドID、分割数=0001、01、0100、11とベースアドレス=00001000が設定されていたとする。追加対象ルールにいては、フィールドID=0001、フィールドID=0100の各フィールドに対して、フィールド値、マスクビット列が、0101、1111、0110、1111のように設定されており、それぞれの有効ビット長が3、4であったとする。なお、マスクビット列は各ビットが‘1’であれば有効、‘0’であれば無効、つまり、ワイルドカードとして扱うものとする。この場合、両フィールドともに、ワイルドカードは含まれていないため、ルールの複製は発生しないことが分かり、LOOKUP時のステップB3と同様に、次の子ノードのアドレス値を算出することができる。一方、同様のノード情報、有効ビット長に対して、追加対象ルールにおけるフィールドID=0001、フィールドID=0100の各フィールドのフィールド値、マスクビット列が、0101、1111、0110、1100のように設定されている場合を考える。この場合、マスクビット列を考慮すると、各フィールド値はそれぞれ、0101、01となる。ノード情報を元に子ノードのアドレス値を算出しようとすると、それぞれの有効ビット長が3、4であることから、フィールドID=0001に対して、下位3ビット101の上位1ビットを参照し、‘1’を得る。一方、フィールドID=0100のフィールドに対しては、有効ビット長が4、分割数が3であることから、01を得る。この結果、子ノードの分割領域を示すビット列にワイルドカードが含まれ、これは、ルールの複製が発生することを意味する。なお、フィールド値がRangeMatchとして設定されている場合、下限値と上限値の有効ビット長に相当するビット列に対し、参照するビット列が共に同じ値であるか否かで判断できる。例えば、上記の例において、フィールドID=0001が下限値0000、上限値0011として設定されていたとする。有効ビット長が3であることから、下限値、上限値の下位3ビットの000と011を参照する。分割数が1であることから、各有効ビット長の先頭ビットを参照し、共に‘0’であることから、領域分割を行ってもルールの複製が発生しないと判断できる。一方、フィールドID=0001が下限値0000、上限値0111が設定されている場合には、参照ビットが‘0’と‘1’であるため、ルールの複製が発生すると判断できる。ステップB10:ルールの複製が発生する場合ステップB9;Yes、当該決定木処理ブロック2は、エントリ追加対象候補とはならない。この場合、子ノード決定ブロック2000は、コマンドの終了フラグを‘1’に設定する。その後、処理はステップB5に進む。ステップB3、B4:一方、ルールの複製が発生しない場合ステップB9;No、LOOKUP処理の場合と同様に、次段のアドレス値の算出ステップB3及び有効ビット長の更新ステップB4が行われる。その後、処理はステップB5に進む。ステップB5、B6:LOOKUP処理の場合と同様に、ステップB5、B6が実施される。つまり、次ノードが葉ノードではない場合ステップB5;Noは、決定木ノード処理ブロック200-ii=1、2、、H-1は、次段の決定木ノード処理ブロック200-i1に出力データ2003を出力するステップB6。そして、処理はステップB7に戻り、次段のノードが処理ノードとなる。一方、次ノードが葉ノードである場合ステップB5;Yesは、ステップA6が終了する。ステップA7:ステップA6が終了すると、決定木ノード処理ブロック200-Hは、算出したアドレス値とコマンドを含む出力データ2004を、エントリ数カウントブロック21に出力する。ステップA8:エントリ数カウントブロック21のカウント処理ブロック210は、決定木ノード処理ブロック200-Hから入力データ212=上述の出力データ2004を受け取る。カウント処理ブロック210は、処理種別がINSERTであることを確認した上で、終了フラグを参照する。終了フラグが‘0’の場合、当該決定木処理ブロック2は、エントリ追加対象候補である。この場合、カウント処理ブロック210は、入力されたアドレス値を用いて、エントリ数記憶ブロック211から追加対象葉ノードに関するエントリ数情報有効ルールエントリ数を読み出す。そして、カウント処理ブロック210は、読み出した有効ルールエントリ数を示す出力データ216を、エントリ追加対象決定ブロック3に出力する。一方、終了フラグが‘1’の場合、当該決定木処理ブロック2は、エントリ追加対象候補ではない。この場合、カウント処理ブロック210は、処理終了信号をエントリ追加対象決定ブロック3に出力する。あるいは、カウント処理ブロック210は、有効ルールエントリ数を最大値に設定し、その有効ルールエントリ数をエントリ追加対象決定ブロック3に通知してもよい。ステップA9:エントリ追加対象決定ブロック3は、複数の決定木処理ブロック2-1~2-Nから通知される情報に基づいて、エントリ追加対象候補を認識し、エントリ追加対象候補の中からエントリ追加対象を選択する。図20は、本ステップA9の処理を示すフローチャートである。ステップD1、D2、D3:エントリ追加対象決定ブロック3は、エントリ追加対象候補から有効ルールエントリ数を示す情報を受け取るステップD1。次に、エントリ追加対象決定ブロック3は、有効ルールエントリ数がルールリストの最大数Bリストサイズを下回っているものがあるか否か確認するステップD2。有効ルールエントリ数がリストサイズを下回っているものが無い場合ステップD2;No、エントリ追加対象決定ブロック3は、エントリ追加対象は存在しないと判断するステップD3。ステップD4、D5:一方、有効ルールエントリ数がリストサイズを下回っているものがある場合ステップD2;Yes、エントリ追加対象決定ブロック3は、有効エントリ数が最小であるエントリ追加対象候補を、エントリ追加対象として選択するステップD4。その後、エントリ追加対象決定ブロック3は、各決定木処理ブロック2にエントリ追加の可否を通知するステップD5。例えば、エントリ追加対象決定ブロック3は、エントリ追加対象に対して新規ルールの追加を指示し、それ以外の決定木処理ブロック2に対してルール追加処理の不実行を指示する。なお、ここでは有効ルールエントリ数が最小であるエントリ追加対象候補をエントリ追加対象として選択しているが、その他のポリシーに従ってエントリ追加対象を選択しても良い。ステップA10:エントリ追加対象である決定木処理ブロック2のエントリ数カウントブロック21は、追加対象葉ノードに関する有効ルールエントリ数に1を加算し、エントリ数記憶ブロック211に書き込む。これにより、エントリ数記憶ブロック211が最新状態に更新される。それ以外の決定木処理ブロック2のエントリ数カウントブロック21は、コマンドの終了フラグを‘1’に設定する。ステップA11:また、各決定木処理ブロック2のエントリ数カウントブロック21は、アドレス値と挿入コマンドを含む出力データ214を、ルールパイプラインブロック22のルール処理ブロック220-1に出力する。ステップA12:ルールパイプラインブロック22は、ルールの追加処理を行う。図21は、本ステップA12の処理を示すフローチャートである。ステップC12:ステップA12は、ルールリスト中の1番目のルールから開始する。具体的には、初段のルール処理ブロック220-1から処理を開始する。ステップC13:比較更新処理ブロック2200は、処理種別がINSERTであることを確認した上で、コマンド内の終了フラグを参照する。終了フラグが‘1’である場合ステップC13;Yes、処理はステップC9に進む。一方、終了フラグが‘0’である場合ステップC13;No、処理はステップC2に進む。ステップC2:LOOKUP処理の場合と同様に、比較更新処理ブロック2200は、入力されたアドレス値を用いてエントリ記憶ブロック2201からエントリ情報を読み出す。そして、比較更新処理ブロック2200は、有効フラグを確認する。ステップC15:ルールが有効である場合ステップC3;Yes、当該エントリに新規ルールを書き込むことは許されない。この場合、そのルール処理ブロック220-iは、次段のルール処理ブロック220-i1に、アドレス値とコマンドを含む出力データ2204を出力する。そして、処理はステップC13に戻り、ルールリスト中の次のルールに対する処理が実行される。ステップC14:一方、ルールが有効ではない場合ステップC3;No、当該エントリすなわち、空きエントリに新規ルールを書き込むことができる。この場合、比較更新処理ブロック2200は、エントリ情報中のルール情報を新規ルールのものに書き換え、且つ、有効フラグを‘1’に設定し、エントリ記憶ブロック2201に書き込む。更に、比較更新処理ブロック2200は、コマンド内の終了フラグを‘1’に設定し、結果フラグを‘1’追加成功に設定する。その後、処理はステップC9に進む。ステップC9:LOOKUP処理の場合と同様に、現在のルールが、ルールリスト中の最後のルールか否かが判定される。現在のルールが最後のルールではない場合ステップC9;No、処理は上記ステップC15に進む。一方、最後のルールの場合ステップC9;Yes、ルール処理ブロック220-Bは、現在のコマンドを、結果出力ブロック5に出力するステップC16。そして、ステップA12が終了する。ステップA13:結果出力ブロック5は、複数の決定木処理ブロック2-1~2-Nからコマンドを受け取る。結果出力ブロック5は、受け取ったコマンド内の結果フラグを参照して、新規ルールが追加されたか、又は追加されなかったかを確認する。そして、結果出力ブロック5は、その結果を示す出力データ7を、INSERT処理の最終結果として出力する。ここで、INSERT処理の最終結果として、新規ルールを追加した箇所を示すエントリIDを出力することが挙げられる。エントリIDは、上述したエントリ情報にルールIDを含まない場合のルールID生成手法と同様、エントリ追加対象となった決定木処理ブロックのID、葉ノードのID、ルールリスト順序等からエントリIDを生成することができる。このとき、新規ルールを追加できる空き領域が無く、新規ルールを追加できなかった場合には、それを示す信号を出力することでルールの追加ができなかったことを示すことができるが、例えば、エントリIDを全て‘1’とした特値として出力することで、ルールの追加ができなかったことを示す信号を省くこともできる。また、INSERT処理では、各々1ビットから成る終了フラグと結果フラグを用いて処理を行ったが、終了フラグのビット幅を増やし、例えば、ルールの複製が発生したことが要因で処理を終了したことや、当該葉ノードのルールリストに空きが無かったことが要因で処理を終了したこと等、処理を終了した要因を表現させることができる。このような終了フラグを参照することで、INSERT処理の最終結果として、新規ルールを追加できなかった場合にその要因も最終結果として出力することができる。1-3-3.DELETE処理次に、DELETE処理を説明する。図22は、本実施の形態におけるDELETE処理を示すフローチャートである。ステップA1:パケット分類器1に、入力データ6が入力される。その入力データ6は、DELETE処理を示す種別データと、削除される既存ルールとを含む。コマンド入力ブロック4は、その入力データ6を受け取る。コマンド入力ブロック4は、その入力データ6に基づいて装置内コマンドここでは、削除コマンドを生成し、その装置内コマンドを決定木処理ブロック2-1~2-Nに一斉に出力する。ステップA6:INSERT処理の場合と同様に、各決定木処理ブロック2は、指定された既存ルールを用いて、自身の決定木を辿る処理を実行する。ステップA3:ステップA6が終了すると、決定木ノード処理ブロック200-Hは、ルールパイプラインブロック22のルール処理ブロック220-1に、算出したアドレス値とコマンドを含む出力データ2003を出力する。ステップA14:ルールパイプラインブロック22は、ルールの削除処理を行う。図23は、本ステップA14の処理を示すフローチャートである。ステップC1:ステップA14は、ルールリスト中の1番目のルールから開始する。具体的には、初段のルール処理ブロック220-1から処理を開始する。ステップC13:比較更新処理ブロック2200は、処理種別がDELETEであることを確認した上で、コマンド内の終了フラグを参照する。終了フラグが‘1’である場合ステップC13;Yes、処理はステップC9に進む。一方、終了フラグが‘0’である場合ステップC13;No、処理はステップC2に進む。ステップC2、C3:LOOKUP処理の場合と同様に、比較更新処理ブロック2200は、入力されたアドレス値を用いてエントリ記憶ブロック2201からエントリ情報を読み出す。そして、比較更新処理ブロック2200は、有効フラグを確認する。ルールが無効である場合ステップC3:No、当該エントリは削除対象ではない。この場合、処理はステップC9に進む。一方、ルールが有効である場合ステップC3;Yes、処理はステップC17に進む。ステップC17:比較更新処理ブロック2200は、読み出したルールと、削除対象として指定されたルールとを比較する。つまり、比較更新処理ブロック2200は、削除対象として指定されているルールが、読み出したルールにマッチするか否かを判定する。ここでは、両者が完全に一致するか否かが判定される。不一致の場合ステップC5;No、処理はステップC9に進む。一方、完全一致の場合ステップC5;Yes、処理はステップC18に進む。ステップC18:比較更新処理ブロック2200は、エントリ情報中の有効フラグを‘0’に設定し、エントリ記憶ブロック2201に書き込む。これにより、当該エントリルールは無効化される。この処理が既存ルールの削除に相当する。更に、比較更新処理ブロック2200は、コマンド内の終了フラグを‘1’に設定し、結果フラグを‘1’削除成功に設定する。その後、処理はステップC9に進む。ステップC9、C15:LOOKUP処理の場合と同様に、現在のルールが、ルールリスト中の最後のルールか否かが判定される。現在のルールが最後のルールではない場合ステップC9;No、ルール処理ブロック220-iは、次段のルール処理ブロック220-i1に、アドレス値とコマンドを含む出力データ2204を出力するステップC15。そして、処理はステップC13に戻り、ルールリスト中の次のルールに対する処理が実行される。一方、現在のルールがルールリスト中の最後のルールである場合ステップC9;Yes、ステップA14は終了する。ステップA15:ステップA14が完了すると、ルール処理ブロック220-Bは、アドレス値とコマンドを含む出力データ2205を、エントリ数カウントブロック21に出力する。ステップA16:エントリ数カウントブロック21のカウント処理ブロック210は、ルール処理ブロック220-Bから入力データ213=上述の出力データ2005を受け取る。カウント処理ブロック210は、処理種別がDELETEであることを確認した上で、終了フラグ及び結果フラグを参照する。終了フラグ及び結果フラグが共に‘1’である場合、カウント処理ブロック210は、入力されたアドレス値を用いて、エントリ数記憶ブロック211から削除対象葉ノードに関するエントリ数情報有効ルールエントリ数を読み出す。そして、カウント処理ブロック210は、当該有効ルールエントリ数から1を減算し、エントリ数記憶ブロック211に書き込む。これにより、エントリ数記憶ブロック211が最新状態に更新される。ステップA17:最後に、カウント処理ブロック210は、コマンドを含む出力データ215を結果出力ブロック5に出力する。結果出力ブロック5は、決定木処理ブロック2-1~2-Nのそれぞれから受け取ったコマンド内の結果フラグを参照して、ルールが削除されたか、又は削除されなかったかを確認する。そして、結果出力ブロック5は、その結果を示す出力データ7を、DELETE処理の最終結果として出力する。ここで、DELETE処理の最終結果として、INSERT処理時の新規ルール追加箇所のエントリIDと同様、削除ルールを追加した箇所を示すエントリIDを出力することが挙げられる。この際、削除ルールが何らかの理由で管理ルールに存在しなかった場合には、削除ルールが存在しなかったことを示す信号や、エントリIDを全て‘1’とした特値として出力することで、削除ルールが存在しなかったことを示すことができる。1-3-4.補足尚、本実施の形態における動作では、INSERT、DELETE処理時に、決定木パイプラインブロック20にて決定木を辿る処理や、ルールパイプラインブロック22にてルールの追加、削除処理を行う場合に、処理が完了していても、各パイプラインを順に処理していく。しかし、各パイプライン内の処理ブロックは、処理が完了した時点で何ら処理を実行しない。そのため、処理が完了した時点で、当該処理ブロックは、エントリ数カウントブロック21や結果出力ブロック5に、処理が完了した信号とコマンドを直接出力してもよい。そして、それぞれのブロックで各決定木処理ブロックの処理タイミングが合うように待ち合わせを行っても構わない。また、INSERT処理時には、ルールは複数の決定木のうち必ず1つだけに追加され、DELETE処理時にも、削除対象ルールが必ず1つだけ削除されることを想定している。本実施の形態における動作では、既に追加されているエントリと同一エントリを追加しようとする場合の処理については、詳細には述べていない。しかし、INSERT処理時に、追加対象木以外の決定木も含めて、有効エントリに対して新規追加エントリとの比較を行うことで、既に追加済みのエントリとの重複追加を防止することが可能である。このような処理は、上記のLOOKUP処理と組み合わせることで実現可能である。なお、INSERT時に追加しようとしているエントリと既に追加済みのエントリとの確認を行うことによって、DELETE時に、削除しようとしているルールが複数の箇所から削除されてしまうようなことは発生しない。更に、コマンド入力ブロック4は、外部から入力データ6として、処理種別や検索キー、追加/削除対象エントリを受け取り、装置内コマンドを生成していた。しかし、入力データ6として到着パケット、又は到着パケットのヘッダ情報データを直接受け取り、ヘッダ解析、検索キーの抽出を行い、装置内コマンドを生成しても構わない。1-4.効果本実施の形態によれば、決定木を用いたパケット分類において、前処理を行うことなく、エントリの動的更新を実現することが可能となる。また、本実施の形態によれば、INSERT処理において、有効ルールエントリ数が最小であるエントリリストに新規ルールが追加される。これにより、複数の決定木間でのルール数の偏りが抑えられ、好適である。更に、本実施の形態によれば、INSERT処理やDELETE処理といったエントリの動的更新に要する処理時間が一定となる。具体的に、各処理に要するサイクル数、及びパケット分類器1に対する次のコマンド入力までのサイクル数の概算値を見積もる。尚、ここでの見積もりは、コマンド入力ブロック4、エントリ追加対象決定ブロック3、結果出力ブロック5、決定木ノード処理ブロック200、エントリ数カウントブロック21、ルール処理ブロック220においては、読み出し処理とそれに関連する処理、あるいは、書き込み処理とそれに関連する処理を、それぞれ1単位サイクルで実行できるとした場合の概算値である。ここで、1単位サイクルは望ましくは1クロックサイクルである。また、次のコマンド入力までのサイクル数は、厳密にはLOOKUP処理、INSERT処理、DELETE処理それぞれに対して次にどの処理コマンドを入力するかによって変わってくるが、ここでは次の処理コマンドを入力するまでサイクル数が最も大きい場合についての見積もり値である。LOOKUP処理の場合、パケット分類器1内の各メモリ領域に対しては、読み出ししか実行しない。そのため、コマンド入力ブロック4の処理、決定木処理ブロック2のH段の決定木パイプラインブロック20における処理、B段のルールパイプラインブロック22における処理、結果出力ブロック5の処理を、合計HB2単位サイクルで実行することが可能である。また、メモリ内の情報は更新されないため、LOOKUPコマンドを入力したすぐ次のサイクルにて、次のコマンドを入力することができる。INSERT処理の場合、パケット分類器1内の各メモリ領域に対して、読み出し、書き込みが実行される。このため、コマンド入力ブロック4の処理、決定木処理ブロック2のH段の決定木パイプラインブロック20の処理、エントリ数カウントブロック21の読み出し処理、エントリ追加対象決定ブロック3の処理、エントリ数カウントブロック21の書き込み処理、B段のルールパイプラインブロック22における読み出し処理と1回の書き込み処理、結果出力ブロック5の処理を、HB6単位サイクルで実行することが可能である。また、エントリ数カウントブロック21のエントリ数記憶ブロック211の書き込み処理が完了した後で無ければ、次のコマンド、特にINSERT処理を正しく実行できない。このため、INSERTコマンドを入力後3単位サイクル経過すれば、次のコマンドを入力することができる。DELETE処理の場合、INSERT処理の場合と同様、本パケット分類器内の各メモリ領域に対して、読み出し、書き込みが実行される。このため、コマンド入力ブロック4の処理、決定木処理ブロック2のH段の決定木パイプラインブロック20の処理、B段のルールパイプラインブロック22における読み出し処理と1回の書き込み処理、エントリ数カウントブロック21における1回の読み出しと1回の書き込み処理、結果出力ブロック5の処理を、HB5単位サイクルで実行することが可能である。また、エントリ数カウントブロック21のエントリ数記憶ブロック211の書き込み処理が完了した後で無ければ、次のコマンド、特にINSERT処理を正しく実行できない。このため、INSERTコマンドを入力後B3単位サイクル経過すれば、次のコマンドを入力することができる。このように、本実施の形態では、例えば、LOOKUP処理はHB2単位サイクル、INSERT処理はHB6単位サイクル、DELETE処理はHB5単位サイクルといった固定時間で処理可能である。従来例のように、ルールの複製が要因で処理時間が変動するようなことはない。また、LOOKUP処理の場合は次の単位サイクルで、INSERT処理の場合は3単位サイクル経過後、DELETE処理の場合はB3単位サイクル経過後に、次のコマンドを入力することができる。従って、わずかな処理オーバーヘッドで、各処理を実行することが可能である。2.第2の実施の形態次に、本発明の第2の実施の形態を説明する。尚、第1の実施の形態と重複する説明は適宜省略される。2-1.構成及び概要図24は、第2の実施の形態に係るパケット分類器1の構成を示すブロック図である。図4で示された第1の実施の形態の構成と比較して、決定木処理ブロック2-1~2-Nが、それぞれ、決定木処理ブロック9-1~9-Nによって置き換えられている。図25は、第2の実施の形態に係る決定木処理ブロック9の構成を示すブロック図である。図5で示された決定木処理ブロック2の構成と比較して、エントリ数カウントブロック21が省かれている。また、ルールパイプラインブロック22のルール処理ブロック220-Bは、出力データ26をエントリ追加対象決定ブロック3に出力する。また、ルール処理ブロック220-1は、エントリ追加対象決定ブロックから入力データ27を受け取る。本実施の形態によれば、INSERT処理時、エントリ追加対象候補の全てが、一旦、新規ルールを決定木に追加する。この処理は、以下一時追加処理と参照される。より詳細には、一時追加処理において、エントリ追加対象候補の各々のルールパイプラインブロック22が、追加対象葉ノードによって管理されるルールリストに新規ルールを一時的に追加する。この一時追加処理の最中に、ルールパイプラインブロック22は、当該ルールリスト中の有効ルールエントリ数をカウントする。そして、ルールパイプラインブロック22が、エントリ数カウントブロック21の代わりに、有効ルールエントリ数をエントリ追加対象決定ブロック3に通知する。具体的には、ルールパイプラインブロック22の最終段のルール処理ブロック220-Bが、一時追加処理を通して得られた有効ルールエントリ数を示す出力データ26を、エントリ追加対象決定ブロック3に出力する。エントリ追加対象決定ブロック3は、第1の実施の形態と同様に、エントリ追加対象候補の中から1つのエントリ追加対象を選択する。そして、エントリ追加対象決定ブロック3は、選択結果を示す情報入力データ27を、全てのエントリ追加対象候補に送る。選択されたエントリ追加対象以外のエントリ追加対象候補の各々は、追加エントリ無効化処理を行う。この追加エントリ無効化処理では、当該エントリ追加対象候補は、上記一時追加処理によって一時的に追加された新規ルールを無効化する。追加エントリ無効化処理は、DELETE処理と同様に実現可能である。このように、本実施の形態によれば、エントリ数カウントブロック21を用いることなく、第1の実施の形態と同じ処理結果を得ることができる。エントリ数カウントブロック21が省かれるため、全体のメモリ容量を削減することが可能である。2-2.動作次に、本実施の形態に係るパケット分類器1の動作を詳しく説明する。2-2-1.LOOKUP処理LOOKUP処理は、第1の実施の形態の場合と同様である。2-2-2.INSERT処理次に、INSERT処理を説明する。図26は、本実施の形態におけるINSERT処理を示すフローチャートである。ステップA1、A6、A13は、第1の実施の形態のINSERT処理の場合と同じである。ステップA3:ステップA6が終了すると、ステップA7の代わりに、LOOKUP処理の場合と同様にステップA3が実行される。すなわち、決定木ノード処理ブロック200-Hは、ルールパイプラインブロック22のルール処理ブロック220-1に、算出したアドレス値とコマンドを含む出力データ2003を出力する。ステップA18:ルールパイプラインブロック22は、上述の一時追加処理を実行する。図27は、本ステップA18の処理を示すフローチャートである。ステップC12:ステップA18は、ルールリスト中の1番目のルールから開始する。具体的には、初段のルール処理ブロック220-1から処理を開始する。ここで、有効ルールエントリ数は、初期値0に設定される。ステップC2、C3、C19:第1の実施の形態と同様に、ルール処理ブロック220は、エントリ情報を読み出し、有効フラグを確認するステップC2。ルールが有効である場合ステップC3;Yes、ルール処理ブロック220は、有効ルールエントリ数に1を加算するステップC19。その後、処理はステップC15に進む。ステップC15:ルール処理ブロック220-iは、次段のルール処理ブロック220-i1に、アドレス値及びコマンドに加えて有効ルールエントリ数を含む出力データ2204を出力する。そして、処理はステップC2に戻り、ルールリスト中の次のルールに対する処理が実行される。ステップC13:一方、ルールが有効ではない場合ステップC3;No、ルール処理ブロック220は、コマンド内の終了フラグを参照する。終了フラグが‘1’である場合ステップC13;Yes、処理は上記ステップC15に進む。一方、終了フラグが‘0’である場合ステップC13;No、処理はステップC14に進む。ステップC14:第1の実施の形態と同様に、ルール処理ブロック220は、当該エントリすなわち、空きエントリに新規ルールを書き込み、有効フラグを‘1’に設定する。更に、ルール処理ブロック220は、コマンド内の終了フラグを‘1’に設定し、結果フラグを‘1’追加成功に設定する。その後、処理はステップC9に進む。ステップC9、C20:第1の実施の形態と同様に、現在のルールが、ルールリスト中の最後のルールか否かが判定される。現在のルールが最後のルールではない場合ステップC9;No、処理は上記ステップC15に進む。一方、最後のルールの場合ステップC9;Yes、ルール処理ブロック220-Bは、現在のコマンド及び有効ルールエントリ数を、エントリ追加対象決定ブロック3に出力するステップC20。そして、ステップA18が終了する。ステップA9:次に、エントリ追加対象決定ブロック3は、第1の実施の形態と同様に、エントリ追加対象候補の中からエントリ追加対象を選択する。そして、エントリ追加対象決定ブロック3は、選択結果を示す情報を、全てのエントリ追加対象候補に送る。ステップA14:ルールパイプラインブロック22は、上述の追加エントリ無効化処理を実行する。この追加エントリ無効化処理は、DELETE処理と同様に行われる。ここで、削除対象のルールは、一時追加処理によって追加された新規ルールである。尚、追加エントリ無効化処理を実施する際のコマンドの処理種別として、第1の実施の形態で使用されなかった11を用いることが考えられる。また、このときの終了フラグ、結果フラグについては、初期化しておく。2-2-3.DELETE処理図28は、本実施の形態におけるDELETE処理を示すフローチャートである。本実施の形態によれば、エントリ数カウントブロック21が省かれている。従って、図22で示された第1の実施の形態におけるDELETE処理と比較して、エントリ数カウントブロック21に関連するステップA15、A16を省略することができる。その他は、第1の実施の形態と同様である。2-3.効果本実施の形態によれば、第1の実施の形態と同じ効果が得られる。更に、メモリ領域が削減される。第1の実施の形態の場合と同様に、各処理に要するサイクル数、及びパケット分類器1に対する次のコマンド入力までのサイクル数の概算値を見積もる。LOOKUP処理は、第1の実施の形態と同じである。INSERT処理は、コマンド入力ブロック4の処理、決定木処理ブロック2のH段の決定木パイプラインブロック20の処理、B段のルールパイプラインブロック22における読み出し処理と1回の書き込み処理、エントリ追加対象決定ブロック3の処理、さらに、B段のルールパイプラインブロック22における読み出し処理と1回の書き込み処理、結果出力ブロック5の処理を含む。従って、全体で、H2B5単位サイクルで実行することが可能である。また、追加対象木以外の決定木に対する追加エントリの無効化を完了しなければ、その後の処理を待ち合わせ無く行うことができない。このため、INSERTコマンドを入力後B3単位サイクル経過すれば、次のコマンドを入力することができる。DELETE処理は、コマンド入力ブロック4の処理、決定木処理ブロック2のH段の決定木パイプラインブロック20の処理、B段のルールパイプラインブロック22における読み出し処理と1回の書き込み処理、結果出力ブロック5の処理を含む。従って、全体で、HB3単位サイクルで実行することが可能である。一方、削除対象エントリは順次削除されるため、エントリの削除を行うルールパイプラインブロック22における1回の書き込み処理を考慮し、DELETEコマンドを入力後1単位サイクル経過すれば、次のコマンドを入力することができる。このように、本実施の形態では、例えば、LOOKUP処理はHB2単位サイクル、INSERT処理はH2B5単位サイクル、DELETE処理はHB3単位サイクルといった固定時間で処理可能である。従来例のように、ルールの複製が要因で処理時間が変動するようなことはない。また、LOOKUP処理の場合は次の単位サイクルで、INSERT処理の場合はB3単位サイクル経過後、DELETE処理の場合は1単位サイクル経過後に次のコマンドを入力することができる。従って、わずかな処理オーバーヘッドが必要になるものの、各処理を順次実行することが可能である。3.第3の実施の形態本発明の第3の実施の形態は、コマンドの構成及びそのコマンドを用いたINSERT処理が、第2の実施の形態と異なる。構成、LOOKUP処理及びDELETE処理は第2の実施の形態と同様であり、重複する説明は適宜省略される。図29は、第3の実施の形態におけるコマンドの構成例を示す概念図である。図29に示されるように、本実施の形態によれば、コマンド部に更にエントリ追加リストIDのフィールドが追加されている。このエントリ追加リストIDは、上述の一時追加処理において新規ルールが追加された位置段数を示す位置情報である。つまり、ルール処理ブロック220-ii=1、2、、Bにおいて新規ルールが追加された場合、エントリ追加リストIDにはiが設定される。図30は、本実施の形態におけるINSERT処理を示すフローチャートである。本実施の形態では、一時追加処理として、第2の実施の形態でのステップA18の代わりに、ステップA19が実行される。また、追加エントリ無効化処理として、第2の実施の形態でのステップA14の代わりに、ステップA20が実行される。その他は、第2の実施の形態と同様である。ステップA19:図31は、ステップA19の処理を示すフローチャートである。第2の実施の形態でのステップA18図27参照と比較して、ステップC14とステップC9との間にステップC21が追加されている。ステップC21において、ルール処理ブロック220-iは、コマンドのエントリ追加リストIDを、当該ルール処理ブロックのID=iに設定する。その他は、ステップA18と同様である。ステップA20:図32は、ステップA20の処理を示すフローチャートである。ステップC1:ステップA20は、ルールリスト中の1番目のルールから開始する。具体的には、初段のルール処理ブロック220-1から処理を開始する。ステップC22:ルール処理ブロック220は、自身のIDが、入力されたコマンドのエントリ追加リストIDと一致するか否か判定する。一致の場合ステップC22;Yes、処理はステップC2に進む。一方、不一致の場合ステップC22;No、処理はステップC9に進む。ステップC2、C18:ルール処理ブロック220は、入力されたアドレス値を用いてエントリ記憶ブロック2201からエントリ情報を読み出すステップC2。更に、ルール処理ブロック220は、エントリ情報中の有効フラグを‘0’に設定し、エントリ記憶ブロック2201に書き込む。これにより、当該エントリルールは無効化される。更に、ルール処理ブロック220は、コマンド内の終了フラグを‘1’に設定し、結果フラグを‘1’削除成功に設定する。その後、処理はステップC9に進む。ステップC9、C15:既出の実施の形態の場合と同様に、現在のルールが、ルールリスト中の最後のルールか否かが判定される。現在のルールが最後のルールではない場合ステップC9;No、ルール処理ブロック220-iは、次段のルール処理ブロック220-i1に、アドレス値とコマンドを含む出力データ2204を出力するステップC15。そして、処理はステップC22に戻り、ルールリスト中の次のルールに対する処理が実行される。一方、現在のルールがルールリスト中の最後のルールである場合ステップC9;Yes、ステップA20は終了する。本実施の形態によれば、第2の実施の形態と同じ効果が得られる。更に、追加エントリ無効化処理において、無効化しないルールに関するルールマッチング処理読み出し/比較処理をスキップすることができる。従って、処理時間及び消費電力が低減される。4.第4の実施の形態図33は、本発明の第4の実施の形態に係るパケット分類器の構成を示すブロック図である。第4の実施の形態では、コンピュータがソフトウェアプログラムを実行することによりパケット分類処理が実現される。具体的には、本実施の形態に係るパケット分類器は、プログラム処理装置10とパケット分類プログラム11を備えている。プログラム処理装置10は、サーバやPC等のホストのCPUにより実現される。パケット分類プログラム11は、プログラム処理装置10によって実行されるコンピュータプログラムであり、プログラム処理装置10の動作を制御する。プログラム処理装置10は、パケット分類プログラム11を実行することにより、既出の実施の形態で説明されたパケット分類器1の機能を備えることができる。尚、パケット分類プログラム11は、コンピュータ読み取り可能な記録媒体に記録されていてもよい。プログラム処理装置10として、複数のCPUコアを有するマルチコアプロセッサさらには、より多くのCPUコアを有するメニーコアプロセッサを用いてもよい。その場合、それぞれのCPUコアに、コマンド入力ブロック4、決定木処理ブロック2-1~2-N、エントリ追加対象決定ブロック3、結果出力ブロック5、さらには、決定木処理ブロック2を構成する各決定木ノード処理ブロック200、エントリ数カウントブロック21、ルール処理ブロック220の処理を実行させることにより、より高速な処理が可能となる。以上、本発明の実施の形態が添付の図面を参照することにより説明された。但し、本発明は、上述の実施の形態に限定されず、要旨を逸脱しない範囲で当業者により適宜変更され得る。上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。付記1パケット分類に用いられる複数の決定木のそれぞれを構成する複数の決定木処理ブロックと、前記複数の決定木処理ブロックに対してコマンドを一斉に入力するコマンド入力ブロックと、前記複数の決定木処理ブロックに接続されたエントリ追加対象決定ブロックとを備え、1つのルールは、前記複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理され、前記コマンドが検索コマンドである場合、前記複数の決定木処理ブロックの各々は、自身の決定木を用いることによって、検索キーがいずれかのルールにマッチするか否かを判定し、前記コマンドが新たなルールを決定木に追加するための挿入コマンドである場合、前記複数の決定木処理ブロックの各々は、前記新たなルールが自身の決定木における単一の葉ノードによって管理され得るかどうかを判定し、前記新たなルールが単一の葉ノードによって管理され得る場合、当該決定木処理ブロックはエントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、前記エントリ追加対象決定ブロックは、前記新たなルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択し、前記選択されたエントリ追加対象は、前記新たなルールを、自身の決定木における前記追加対象葉ノードが管理するルールリストに追加するパケット分類器。付記2付記1に記載のパケット分類器であって、前記エントリ追加対象候補は、前記追加対象葉ノードが管理している有効なルールのエントリ数を、前記エントリ追加対象決定ブロックに通知し、前記エントリ追加対象決定ブロックは、前記エントリ数に基づいて、前記エントリ追加対象を選択するパケット分類器。付記3付記2に記載のパケット分類器であって、前記エントリ追加対象決定ブロックは、前記エントリ数が最小である前記エントリ追加対象候補を、前記エントリ追加対象として選択するパケット分類器。付記4付記2又は3に記載のパケット分類器であって、前記複数の決定木処理ブロックの各々は、自身の決定木の各葉ノードによって管理されている有効なルールのエントリ数を記憶するエントリ数記憶ブロックを備え、前記エントリ追加対象候補は、前記追加対象葉ノードに関する前記エントリ数を前記エントリ数記憶ブロックから読み出し、前記読み出したエントリ数を前記エントリ追加対象決定ブロックに通知し、前記エントリ追加対象は、前記追加対象葉ノードに関する前記エントリ数に1を加算することにより、前記エントリ数記憶ブロックを更新するパケット分類器。付記5付記4に記載のパケット分類器であって、前記コマンドが既存ルールを削除するための削除コマンドである場合、前記複数の決定木処理ブロックの各々は、前記既存ルールが自身の決定木における単一の葉ノードによって管理されているか否かを判定し、前記既存ルールが単一の葉ノードによって管理されている場合、当該決定木処理ブロックはエントリ削除対象であり、当該単一の葉ノードは削除対象葉ノードであり、前記エントリ削除対象は、前記既存ルールを無効化し、また、前記削除対象葉ノードに関する前記エントリ数から1を減算することにより、前記エントリ数記憶ブロックを更新するパケット分類器。付記6付記2又は3に記載のパケット分類器であって、前記エントリ追加対象候補の各々は、前記追加対象葉ノードが管理するルールリストに前記新たなルールを一時的に追加する一時追加処理を行い、また、前記一時追加処理の最中に、当該ルールリスト中の有効なルールのエントリ数をカウントし、前記エントリ追加対象候補の各々は、前記一時追加処理において得られた前記エントリ数を、前記エントリ追加対象決定ブロックに通知し、前記選択されたエントリ追加対象以外の前記エントリ追加対象候補の各々は、前記一時的に追加された新たなルールを無効化する追加エントリ無効化処理を行うパケット分類器。付記7付記6に記載のパケット分類器であって、前記一時追加処理において、前記エントリ追加対象候補の各々は、前記ルールリスト中で前記新たなルールが追加された位置を示す位置情報を前記挿入コマンドに書き込み、前記選択されたエントリ追加対象以外の前記エントリ追加対象候補の各々は、前記位置情報を参照することによって、ルールマッチングを行うことなく、前記追加エントリ無効化処理を行うパケット分類器。付記8付記1乃至7のいずれか一項に記載のパケット分類器であって、前記複数の決定木処理ブロックの各々は、各決定木の段数と同じ段数の決定木ノード処理ブロックを備え、前記決定木ノード処理ブロックを用いることによって決定木の探索をパイプライン処理で行う決定木パイプラインブロックと、各葉ノードにおいて管理可能なルール数と同じ段数のルール処理ブロックを備え、前記ルール処理ブロックを用いることによってルールの検索、追加及び削除をパイプライン処理で行うルールパイプラインブロックとを備えるパケット分類器。付記9複数の決定木を用いたパケット分類方法であって、1つのルールは、前記複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理され、前記パケット分類方法は、前記複数の決定木に対してコマンドを一斉に入力するステップと、前記コマンドが検索コマンドである場合、前記複数の決定木の各々において、検索キーがいずれかのルールにマッチするか否かを判定するステップと、前記コマンドが新たなルールを決定木に追加するための挿入コマンドである場合、前記複数の決定木の各々において、前記新たなルールが単一の葉ノードによって管理され得るかどうかを判定するステップと、ここで、前記新たなルールが単一の葉ノードによって管理され得る場合、当該決定木はエントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、前記新たなルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択するステップと、前記新たなルールを、前記エントリ追加対象の前記追加対象葉ノードが管理するルールリストに追加するステップとを含むパケット分類方法。付記10複数の決定木を用いたパケット分類処理をコンピュータに実行させるためのパケット分類プログラムであって、1つのルールは、前記複数の決定木のうちいずれか1つの決定木における単一の葉ノードによって管理され、前記パケット分類処理は、前記複数の決定木に対してコマンドを一斉に入力するステップと、前記コマンドが検索コマンドである場合、前記複数の決定木の各々において、検索キーがいずれかのルールにマッチするか否かを判定するステップと、前記コマンドが新たなルールを決定木に追加するための挿入コマンドである場合、前記複数の決定木の各々において、前記新たなルールが単一の葉ノードによって管理され得るかどうかを判定するステップと、ここで、前記新たなルールが単一の葉ノードによって管理され得る場合、当該決定木はエントリ追加対象候補であり、当該単一の葉ノードは追加対象葉ノードであり、前記新たなルールを追加する対象であるエントリ追加対象を、前記エントリ追加対象候補の中から選択するステップと、前記新たなルールを、前記エントリ追加対象の前記追加対象葉ノードが管理するルールリストに追加するステップとを含むパケット分類プログラム。本出願は、2010年12月15日に出願された日本国特許出願2010-279693を基礎とする優先権を主張し、その開示の全てをここに取り込む。