(57)【要約】【課題】検索対象のフィールドが固定化されていない場合にも、パケット検索を高速化することである。【解決手段】パケット検索装置１０は、二分木作成部１１とビット位置決定部１２とハッシュテーブル作成部１３とを有する。二分木作成部１１は、所定の枝分かれを有する二分木を作成する。ビット位置決定部１２は、作成された上記二分木の一部に対するハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する。ハッシュテーブル作成部１３は、決定された上記開始ビット位置から上記終了ビット位置までを対象として、上記二分木の一部のハッシュテーブルを作成する。【選択図】図１
2020017147.tif 000002
【特許請求の範囲】
【請求項１】
所定の枝分かれを有する二分木を作成する二分木作成部と、
作成された前記二分木の一部に対するハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する決定部と、
決定された前記開始ビット位置から前記終了ビット位置までを対象として、前記二分木の一部のハッシュテーブルを作成するテーブル作成部と
を有することを特徴とするパケット検索装置。
【請求項２】
前記二分木は、ＡＮＹ値を含むことを特徴とする請求項１に記載のパケット検索装置。
【請求項３】
前記二分木作成部は、前記所定の枝分かれが０、１、ＡＮＹ値の順になる様に、前記二分木を作成し、
前記決定部は、前記二分木の開始点または前記ＡＮＹ値の次に、０または１、あるいは０と１の双方が続く場合、そのビット位置を、前記開始ビット位置に決定すると共に、その後に別のＡＮＹ値または終端点が現れた場合、該ＡＮＹ値の手前または前記終端点のビット位置を、前記終了ビット位置に決定することを特徴とする請求項２に記載のパケット検索装置。
【請求項４】
前記決定部は、前記ハッシュテーブル化の対象部分となる二分木の一部の枝分かれ数が、所定数以下の場合には、前記二分木の一部を、前記ハッシュテーブル化の対象から除外することを特徴とする請求項１に記載のパケット検索装置。
【請求項５】
パケット検索装置が、
所定の枝分かれを有する二分木を作成する二分木作成工程と、
作成された前記二分木の一部に対するハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する決定工程と、
決定された前記開始ビット位置から前記終了ビット位置までを対象として、前記二分木の一部のハッシュテーブルを作成するテーブル作成工程と
を含むことを特徴とするパケット検索方法。
【請求項６】
所定の枝分かれを有する二分木を作成する二分木作成ステップと、
作成された前記二分木の一部に対するハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する決定ステップと、
決定された前記開始ビット位置から前記終了ビット位置までを対象として、前記二分木の一部のハッシュテーブルを作成するテーブル作成ステップと
をコンピュータに実行させるためのパケット検索プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケット検索装置、パケット検索方法、及びパケット検索プログラムに関する。
【背景技術】
【０００２】
従来、パケットの検索技術として、主にハードウェアを用いたＴＣＡＭ（Ternary  Content  Addressable  Memory）検索と、主にソフトウェア処理を用いた二分木法やハッシュ（Ｈａｓｈ）法による検索がある。これらの検索技術のうち、ハッシュ法は、通常の変数値取得処理と同様の動作であり、比較処理を行わないため、一般的には二分木法よりも高速である。しかしながら、ハッシュ法の場合、全てのルール（ｒｕｌｅ）についてマッチフィールド（Ｍａｔｃｈ  Ｆｉｅｌｄ）が固定されなければならい（ＡＮＹ値等が許容されない）ことや、ハッシュ衝突の問題があることから、二分木法が用いられることが多い。
【０００３】
例えば、非特許文献１の第３１頁には、ハッシュ方式と二分木方式との長所と短所が比較されているが、機能拡張性の項目において、ハッシュ方式はＬＰＭ（Longest  Prefix  Match）検索ができないと記載されている。すなわち、ハッシュ方式では、全てのルール間で、検索対象のフィールドが同じでなければならないとう、厳しい適用条件が課される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“パケットフォワーディングを支える技術（２）ハードウェア処理ルータの内部詳解”、［online］、［平成３０年７月１７日検索］、インターネット＜https://www.nic.ad.jp/ja/materials/iw/2012/proceedings/d1/d1-uchiya.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した従来技術では、以下の様な問題点があった。ハッシュ法では、全てのルール間で、検索対象フィールドが同じでなければならないことから、複数のフィールドの内、何れかのフィールドでＡＮＹ等が許容される場合には、パケット検索に際して、ハッシュ法が適用できないという問題点があった。換言すれば、検索対象フィールドが固定化されていない場合（例えば、ルールにＡＮＹを許容する場合）には、ハッシュ法の高速性を活かすことは困難であった。
【０００６】
以下、図８を参照しながら、従来技術の課題について、より詳細に説明する。図８は、従来技術の課題を説明するための図である。ハッシュ法の適用は、検索対象フィールドが５ｔｕｐｌｅの様に予め固定されており、値としてＡＮＹ等の変数が許容されていない場合が典型例である。すなわち、各ルールの検索対象フィールドが、完全長方形型の様に完全に一致していないと、ハッシュ法は原則として適用できない。
【０００７】
より具体的には、図８に示す様に、ハッシュ法は、入力パケットの対象フィールドとルールのマッチフィールドとを、それぞれハッシュ値化して比較する方法であるため、マッチフィールドにＡＮＹやｐｒｅｆｉｘ、ｓｕｆｆｉｘが許容され、ルールの検索対象フィールドがまちまちになると、パケットによりハッシュ化する対象領域が固定化されず、ハッシュ法の適用は困難となる。なぜなら、ハッシュを成立させるためには、入力パケット側の対象フィールドとルール側の対象フィールドとが一致している必要があるが、ルール内のフィールドにＡＮＹやｐｒｅｆｉｘ、ｓｕｆｆｉｘが含まれることにより、ルール側の対象フィールドが定まらない場合には、上記一致が困難となるからである。
【０００８】
開示の技術は、上記に鑑みてなされたものであって、検索対象のフィールドが固定化されていない場合にも、パケット検索を高速化することができるパケット検索装置、パケット検索方法、及びパケット検索プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述した課題を解決し、目的を達成するために、本願の開示するパケット検索装置は、一つの態様において、所定の枝分かれを有する二分木を作成する二分木作成部と、作成された前記二分木の一部に対するハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する決定部と、決定された前記開始ビット位置から前記終了ビット位置までを対象として、前記二分木の一部のハッシュテーブルを作成するテーブル作成部とを有する。
【００１０】
また、本願の開示するパケット検索方法は、一つの態様において、パケット検索装置が、所定の枝分かれを有する二分木を作成する二分木作成工程と、作成された前記二分木の一部に対するハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する決定工程と、決定された前記開始ビット位置から前記終了ビット位置までを対象として、前記二分木の一部のハッシュテーブルを作成するテーブル作成工程とを含む。
【００１１】
更に、本願の開示するパケット検索プログラムは、一つの態様において、所定の枝分かれを有する二分木を作成する二分木作成ステップと、作成された前記二分木の一部に対するハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する決定ステップと、決定された前記開始ビット位置から前記終了ビット位置までを対象として、前記二分木の一部のハッシュテーブルを作成するテーブル作成ステップとをコンピュータに実行させる。
【発明の効果】
【００１２】
本願の開示するパケット検索装置、パケット検索方法、及びパケット検索プログラムは、検索対象のフィールドが固定化されていない場合にも、パケット検索を高速化することができるという効果を奏する。
【図面の簡単な説明】
【００１３】
【図１】図１は、パケット検索装置の構成を示す図である。
【図２】図２は、本実施例に係るパケット検索処理を説明するための図である。
【図３】図３は、従来技術及び本実施例に係るハッシュ法の適用対象となるフィールドを示す図である。
【図４】図４は、本実施例に係るハッシュテーブル化アルゴリズムの概要を示す図である。
【図５】図５は、本実施例に係るハッシュテーブル化アルゴリズムの具体例を示す図である。
【図６】図６は、本実施例に係る二分木のハッシュテーブル化アルゴリズムを説明するための図である。
【図７】図７は、本実施例に係るパケット検索プログラムによる情報処理がコンピュータを用いて具体的に実現されることを示す図である。
【図８】図８は、従来技術の課題を説明するための図である。
【発明を実施するための形態】
【００１４】
以下に、本願の開示するパケット検索装置、パケット検索方法、及びパケット検索プログラムの実施例を、図面を参照しながら詳細に説明する。なお、以下の実施例により本願の開示するパケット検索装置、パケット検索方法、及びパケット検索プログラムが限定されるものではない。
【００１５】
まず、本願の開示する一実施例に係るパケット検索装置１０の構成を説明する。図１は、パケット検索装置１０の構成を示す図である。図１に示す様に、パケット検索装置１０は、二分木作成部１１とビット位置決定部１２とハッシュテーブル作成部１３とを有する。これら各構成部分は、一方向又は双方向に、信号やデータの入出力が可能な様に接続されている。
【００１６】
詳細な構成については後述するが、二分木作成部１１は、所定の枝分かれを有する二分木を作成する。ビット位置決定部１２は、作成された上記二分木の一部に対するハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する。ハッシュテーブル作成部１３は、決定された上記開始ビット位置から上記終了ビット位置までを対象として、上記二分木の一部のハッシュテーブルを作成する。
【００１７】
図２は、本実施例に係るパケット検索処理を説明するための図である。図２に示す様に、本実施例に係るパケット検索装置１０は、二分木の一部（破線枠Ａ１の部分）をハッシュテーブル化することにより、該当部分の比較検索処理に対し、ハッシュ法を適用する。ハッシュ法では、ハッシュテーブルを配列変数で作成し、検索値（ハッシュ値）を配列変数のインデックスにする。ハッシュ法による検索は、このインデックス値の指定により行うが、本動作は、機械語レベルでは、メモリのアドレス指定処理となるため、通常の変数値取得処理と同様の動作になる。すなわち、ハッシュ法では、パケット検索装置１０は、上記比較検索処理を、メモリアドレス指定処理に変更することにより、比較処理を行わずに検索を実行することができる。このため、高速処理が実現される。
【００１８】
図２に示す例では、破線枠Ａ１内の３つの情報（０１１、１０１、１１１）に対する検索が、ハッシュテーブル化により高速化されることとなる。但し、この例とは異なり、ハッシュテーブル化する部分の情報が１つしかない（枝分かれが無い）場合には、元の二分木法でも比較検索処理が実行されないため、ハッシュテーブル化による効果は得られない。このため、かかる場合には、必ずしもハッシュテーブル化を行う必要は無い。反対に、ハッシュテーブル化する部分の枝分かれの数が多い程、ハッシュテーブル化により得られる高速化の効果は高くなる。
【００１９】
図３は、従来技術及び本実施例に係るハッシュ法の適用対象となるフィールドを示す図である。図３では、横軸方向にはビットが規定され、縦軸方向にはルールが規定されている。図３に示す様に、従来技術においてハッシュ法の適用対象となるフィールドは、完全長方形型であるため、全てのルール間で対象フィールドが一致している。これに対して、本実施例においてハッシュ法の適用対象となるフィールドは、ＡＮＹ値（ｐｒｅｆｉｘ、ｓｕｆｆｉｘを含む）を伴うため、各ルールの対象フィールドは、必ずしも一致していない。このため、従来の方法では、ハッシュ法の適用による高速化を図ることは困難である。そこで、本実施例に係るパケット検索装置１０は、ＡＮＹを伴う二分木テーブルを前提とし、ルール状況（例えば、トリー状況）に応じて動的に、部分的なハッシュテーブル化を行う。
【００２０】
以下、図４及び図５を参照しながら、本実施例に係るハッシュテーブル化アルゴリズムについて、説明する。図４は、本実施例に係るハッシュテーブル化アルゴリズムの概要を示す図である。図４は前述の図３に対応し、横軸方向にはビットが規定され、縦軸方向にはルールが規定されている。図５は、本実施例に係るハッシュテーブル化アルゴリズムの具体例を示す図である。前提として、ルールの並び順は、ＡＮＹを伴う二分木を作成する際に、各ノードを上から０、１、Ａ（ＡＮＹ）として二分木を作成した場合に、その上下の順に従って上からルールを並べる（Ｓ０）。
【００２１】
次のＳ１では、パケット検索装置１０は、開始ビット位置が同じであるルールの中で、終了ビット位置が最短のルール（最短長ルール）Ｒ１に合わせて、破線枠Ａ２に対応するハッシュテーブルＴ１を作成する。ここで、開始ビット位置とは、文字通りの開始位置（例えば、図４の（１））のみならず、ＡＮＹ値直後のビット位置（例えば、図４の（２））を含む。同様に、終了ビット位置とは、文字通りの終了位置（例えば、図４の（３））のみならず、ＡＮＹ値直前のビット位置（例えば、図４の（４））を含む。
【００２２】
上記最短のルールの終了ビット位置以降については、パケット検索装置１０は、当該位置から、その次に短いルールまで、ハッシュテーブルを作成する。図５に示す例では、破線枠Ａ３に対応するハッシュテーブルが引き続き作成される（Ｓ２）。以降、同様の処理が繰り返し、実行される。
【００２３】
このとき、破線枠Ａ４に対応するハッシュテーブルについては、ハッシュテーブル化する部分の元の二分木の枝分かれ数が２であり、２以下であるので、作成されない。従って、そのまま二分木法が採られる（Ｓ３）。
【００２４】
なお、ハッシュテーブル化せずにそのまま二分木法が採られる条件として、枝分かれ数が２以下であることを例示したが、これに限らず、所定値Ｎ（例えば、３）以下であってもよい。上記Ｓ１の場合、枝分かれ数が１１であるので、所定値Ｎが１１以上でない限り、ハッシュテーブル化が実行される。反対に、枝分かれ数が２以下であっても、枝分かれが存在する場合には、ハッシュテーブル化を行ってもよい。
【００２５】
以下、図６を参照しながら、二分木のハッシュテーブル化アルゴリズムについて、より詳細に説明する。通常の検索ルールでは、ＡＮＹ値やｐｒｅｆｉｘ、ｓｕｆｆｉｘを伴うのが一般的である。この様な場合にも、以下の手順によりハッシュテーブル化することで、パケット検索の効率化が実現される。
【００２６】
図６は、本実施例に係る二分木のハッシュテーブル化アルゴリズムを説明するための図である。図６に示す様に、（１）では、ｓｔａｒｔ  ｎｏｄｅを起点として、枝分かれが、上から０、１、Ａ（ａｎｙ  ｎｏｄｅ）の順になる様に、二分木構成が作成される。
【００２７】
次の（２）では、二分木のｓｔａｒｔ  ｎｏｄｅまたはＡの次に、０または１のノード、あるいは０と１双方のノードが続く場合、そのビット位置を、ハッシュテーブルの開始ビット位置とし、その後、Ａまたは終端点が現れた場合、Ａの手前または終端点のビット位置を、ハッシュテーブルの終了ビット位置とする。図６に示す例では、左端のｓｔａｒｔ  ｎｏｄｅに０と１双方のノードが続くため、このビット位置Ｂ１が、破線枠Ａ５に対応するハッシュテーブルの開始ビット位置となる。その後、ビット位置Ｂ１から４ビット後のビット位置Ｂ２にＡが現れるため、その手前のビット位置Ｂ３が、破線枠Ａ５に対応するハッシュテーブルの終了ビット位置となる。
【００２８】
次の（３）では、上記（２）に引き続き、ハッシュテーブルの終了ビット位置から、０または１のノード、あるいは０と１双方のノードが続く場合、そのビット位置を、新たなハッシュテーブルの開始ビット位置とする。その後は、上記（２）と同様に、Ａまたは終端点が現れた場合、Ａの手前または終端点のビット位置を、ハッシュテーブルの終了ビット位置とする。これにより、図６に示す例では、破線枠Ａ６〜Ａ９に対応する４つのハッシュテーブルが新たに作成されることとなる。
【００２９】
なお、図６の（４）の様に、ハッシュテーブル化する部分に枝分かれが無い場合には、ハッシュテーブル化は行われない。これにより、高速化に寄与しない部分にまで、不要なハッシュ法が適用されることが抑制され、より効率的なパケット検索が可能となる。
【００３０】
ハッシュテーブル化の評価に関し、二分木法による検索回数をｌｏｇ２（Ｎ）（Ｎはルール数）とすると、図６に示す例では、ルール数（終端ノードの数）が１９であるので、検索回数はｌｏｇ２（１９）≒４．２となる。一方、図６の破線枠Ａ５〜Ａ９に示す部分をハッシュテーブル化した場合には、１ハッシュテーブル内において１ＮＵＬＬ判定を行うとすると、１０１１０１ＡＡ１のルールヒット時に、最大３回の検索で済むことになる。従って、パケット検索の効率化が実現される。
【００３１】
以上説明した様に、パケット検索装置１０は、二分木作成部１１とビット位置決定部１２とハッシュテーブル作成部１３とを有する。二分木作成部１１は、所定の枝分かれを有する二分木を作成する。ビット位置決定部１２は、作成された上記二分木の一部に対するハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する。ハッシュテーブル作成部１３は、決定された上記開始ビット位置から上記終了ビット位置までを対象として、上記二分木の一部のハッシュテーブルを作成し、該一部にハッシュ法を適用する。ハッシュ法は、二分木法と比較して一般的に高速であるため、パケット検索装置１０によれば、ハッシュ法を適用可能な範囲内で、パケット検索の高速化を図ることができる。
【００３２】
パケット検索装置１０において、上記二分木は、ＡＮＹ値、ｐｒｅｆｉｘ、ｓｕｆｆｉｘのうち、少なくとも１つを含むものとしてもよい。また、パケット検索装置１０において、二分木作成部１１は、上記所定の枝分かれが上から０、１、ＡＮＹ値の順になる様に、上記二分木を作成し、ビット位置決定部１２は、上記二分木の開始点または上記ＡＮＹ値の次に、０または１のノード、あるいは０と１の双方のノードが続く場合、そのビット位置を、上記開始ビット位置に決定すると共に、その後に別のＡＮＹ値または終端点が現れた場合、該ＡＮＹ値の手前または上記終端点のビット位置を、上記終了ビット位置に決定するものとしてもよい。
【００３３】
換言すれば、ビット位置決定部１２は、二分木内のＡＮＹ値を回避しつつ、部分的なハッシュテーブル化の対象範囲が極力広くなる様に、二分木の構成に合わせて動的に、ハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する。これにより、検索対象フィールドが固定化されていない場合（例えば、ルールにＡＮＹを許容する場合）にも、可能な限り、ハッシュ法の高速性を活かすことができる。
【００３４】
また、パケット検索装置１０において、ビット位置決定部１２は、上記ハッシュテーブル化の対象部分となる二分木の一部の枝分かれ数が、所定数（例えば、２）以下の場合には、上記二分木の一部を、上記ハッシュテーブル化の対象から除外して、そのまま二分木法を適用するものとしてもよい。
【００３５】
なお、ビット位置決定部１２は、二分木にハッシュテーブル化を適用する部分に同期する様に、パケットによりハッシュ値を求める、ルール側の対象フィールドも変更する。これにより、二分木において高速化を所望する部分を、正確かつ継続的に、ハッシュテーブル化の対象とすることができる。
【００３６】
上述した様に、本実施例に係るパケット検索技術は、二分木法に対して、部分的にハッシュ法を適用することで、ルールのマッチフィールドが固定化されていない（例えば、マッチフィールドにＡＮＹやｐｒｅｆｉｘ、ｓｕｆｆｉｘなどが存在する）場合にも、パケット検索を高速化することができる。換言すれば、本実施例に係るパケット検索技術は、ＡＮＹやｐｒｅｆｉｘ、ｓｕｆｆｉｘを伴う二分木テーブルを前提とし、ルール状況に応じて動的に、部分的なハッシュテーブル化を行う。これにより、検索ルールの仕様が、マッチフィールドにＡＮＹ値やｐｒｅｆｉｘ、ｓｕｆｆｉｘを含む柔軟な仕様の場合にも、ハッシュテーブルを部分的に適用し、高速化を実現することが可能となる。また、本実施例に係るパケット検索技術は、二分木を部分的にハッシュテーブル化するため、ＡＮＹ値のみならず、ｐｒｅｆｉｘやｓｕｆｆｉｘがマッチフィールドに許容される場合にも対応することができる。
【００３７】
（パケット検索プログラム）
図７は、本実施例に係るパケット検索プログラムによる情報処理がコンピュータ１００を用いて具体的に実現されることを示す図である。図７に示す様に、コンピュータ１００は、例えば、メモリ１０１と、ＣＰＵ（Central  Processing  Unit）１０２と、ハードディスクドライブインタフェース１０３と、ディスクドライブインタフェース１０４と、シリアルポートインタフェース１０５と、ビデオアダプタ１０６と、ネットワークインタフェース１０７とを有し、これらの各部はバスＣによって接続される。
【００３８】
メモリ１０１は、図７に示す様に、ＲＯＭ（Read  Only  Memory）１０１ａ及びＲＡＭ（Random  Access  Memory）１０１ｂを含む。ＲＯＭ１０１ａは、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３は、図７に示す様に、ハードディスクドライブ１０８に接続される。ディスクドライブインタフェース１０４は、図７に示す様に、ディスクドライブ１０９に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１０９に挿入される。シリアルポートインタフェース１０５は、図７に示す様に、例えばマウス１１０、キーボード１１１に接続される。ビデオアダプタ１０６は、図７に示す様に、例えばディスプレイ１１２に接続される。
【００３９】
ここで、図７に示す様に、ハードディスクドライブ１０８は、例えば、ＯＳ（Operating  System）１０８ａ、アプリケーションプログラム１０８ｂ、プログラムモジュール１０８ｃ、プログラムデータ１０８ｄ、二分木データ、ハッシュテーブルを記憶する。すなわち、開示の技術に係るパケット検索プログラムは、コンピュータ１００によって実行される指令が記述されたプログラムモジュール１０８ｃとして、例えばハードディスクドライブ１０８に記憶される。具体的には、上記実施例で説明した二分木作成部１１、ビット位置決定部１２、ハッシュテーブル作成部１３の各々と同様の情報処理を実行する各種手順が記述されたプログラムモジュール１０８ｃが、ハードディスクドライブ１０８に記憶される。また、パケット検索プログラムによる情報処理に用いられるデータは、プログラムデータ１０８ｄとして、例えばハードディスクドライブ１０８に記憶される。そして、ＣＰＵ１０２が、ハードディスクドライブ１０８に記憶されたプログラムモジュール１０８ｃやプログラムデータ１０８ｄを必要に応じてＲＡＭ１０１ｂに読み出し、上記各種手順を実行する。
【００４０】
なお、パケット検索プログラムに係るプログラムモジュール１０８ｃやプログラムデータ１０８ｄは、ハードディスクドライブ１０８に記憶される場合に限られず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１０９等を介してＣＰＵ１０２によって読み出されてもよい。あるいは、パケット検索プログラムに係るプログラムモジュール１０８ｃやプログラムデータ１０８ｄは、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７を介してＣＰＵ１０２によって読み出されてもよい。
【００４１】
また、上述したパケット検索装置１０の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的態様は、図示のものに限らず、その全部又は一部を、各種の負荷や使用状況等に応じて、任意の単位で機能的又は物理的に分散・統合して構成することもできる。例えば、ビット位置決定部１２とハッシュテーブル作成部１３を１つの構成要素として統合してもよい。反対に、ビット位置決定部１２に関し、ハッシュテーブル化の開始ビット位置と終了ビット位置とを決定する部分と、ルール側の対象フィールドを変更する部分とに分散してもよい。更に、二分木データ、ハッシュテーブルを格納するハードディスクドライブ１０８を、パケット検索装置１０の外部装置として、ネットワークやケーブル経由で接続する様にしてもよい。
【符号の説明】
【００４２】
１０  パケット検索装置
１１  二分木作成部
１２  ビット位置決定部
１３  ハッシュテーブル作成部
１００  コンピュータ
１０１  メモリ
１０１ａ  ＲＯＭ
１０１ｂ  ＲＡＭ
１０２  ＣＰＵ
１０３  ハードディスクドライブインタフェース
１０４  ディスクドライブインタフェース
１０５  シリアルポートインタフェース
１０６  ビデオアダプタ
１０７  ネットワークインタフェース
１０８  ハードディスクドライブ
１０８ａ  ＯＳ
１０８ｂ  アプリケーションプログラム
１０８ｃ  プログラムモジュール
１０８ｄ  プログラムデータ
１０９  ディスクドライブ
１１０  マウス
１１１  キーボード
１１２  ディスプレイ
Ｂ１、Ｂ２、Ｂ３  ビット位置
Ｃ  バス
Ｔ１  ハッシュテーブル
【図１】
2020017147.tif 000003
【図２】
2020017147.tif 000004
【図３】
2020017147.tif 000005
【図４】
2020017147.tif 000006
【図５】
2020017147.tif 000007
【図６】
2020017147.tif 000008
【図７】
2020017147.tif 000009
【図８】
2020017147.tif 000010