(57)【特許請求の範囲】
【請求項１】
到来するパケットのヘッダ情報を抽出する手段と、
当該ヘッダ情報に対応するパケットの扱いルールが記録されたポリシテーブルと、
前記抽出する手段により抽出された前記ヘッダ情報と前記ポリシテーブルとを比較して前記ルールを特定する手段と
を備え、
前記ポリシテーブルは、前記ヘッダ情報に含まれる属性の異なる複数のフィールド情報毎に検索項目がそれぞれ設けられ、
前記特定する手段は、
前記検索項目毎に前記ヘッダ情報に含まれるフィールド情報と前記ポリシテーブルに含まれるフィールド情報とを比較した検索結果が一致した前記ルールについては“１”とし不一致の前記ルールについては“０”とする一致テーブルを作成する手段と、
全ての前記検索項目に対する検索終了後に複数の前記ルールのそれぞれについて前記検索結果の論理積を演算する手段と、
この論理積を演算する手段の演算結果が“１”となる前記ルールを当該パケットの扱いルールとして最終的に特定する手段と
を備えたパケット転送装置において、
前記ポリシテーブルの前記ルールは、検索項目ごとに上位のノードが下位のノードのもつルールを包含する関係を内包関係として、最上位のノードから下位のノードに至るツリー状に形成され、
少なくとも一つの検索項目について、上位のノードに属する下位のルールの集合をあらかじめ複数生成する手段が設けられ、
前記論理積を演算する手段は、前記ヘッダ情報に含まれるフィールド情報とポリシテーブルに含まれるフィールド情報との検索結果が一致したルールが一つでも含まれる前記集合を論理積の演算対象とし、一致したルールが一つも含まれない前記集合を論理積演算の対象から除外する手段を備えた
ことを特徴とするパケット転送装置。
【請求項２】
請求項１記載のパケット転送装置を備えたことを特徴とするネットワーク。
【請求項３】
情報処理装置にインストールすることにより、その情報処理装置に、
到来するパケットのヘッダ情報を抽出する機能と、
当該ヘッダ情報に対応するパケットの扱いルールが記録されたポリシテーブルに相応する機能と、
前記抽出する機能により抽出された前記ヘッダ情報と前記ポリシテーブルとを比較して前記ルールを特定する機能と
を備え、
前記ポリシテーブルは、前記ヘッダ情報に含まれる属性の異なる複数のフィールド情報毎に検索項目がそれぞれ設けられ、
前記特定する機能は、
前記検索項目毎に前記ヘッダ情報に含まれるフィールド情報と前記ポリシテーブルに含まれるフィールド情報とを比較した検索結果が一致した前記ルールについては“１”とし不一致の前記ルールについては“０”とする一致テーブルを作成する機能と、
全ての前記検索項目に対する検索終了後に複数の前記ルールのそれぞれについて前記検索結果の論理積を演算する機能と、
この論理積を演算する機能の演算結果が“１”となる前記ルールを当該パケットの扱いルールとして最終的に特定する機能と
を備えた
パケット転送装置に相応する機能を実現させるプログラムにおいて、
前記ポリシテーブルの前記ルールは、検索項目ごとに上位のノードが下位のノードのもつルールを包含する関係を内包関係として、最上位のノードから下位のノードに至るツリー状に形成されており、
少なくとも一つの検索項目について、上位のノードに属する下位のルールの集合をあらかじめ複数生成する機能を実現させ、
一つの前記検索項目が示すルールの範囲がもう一つの前記検索項目が示すルールの範囲を包含する関係を内包関係と定義し、
少なくとも一つの前記検索項目についてこの内包関係にある前記ルールの集合をあらかじめ複数生成する機能を実現させ、
前記論理積を演算する機能として、前記ヘッダ情報に含まれるフィールド情報とポリシテーブルに含まれるフィールド情報との検索結果が一致したルールが一つでも含まれる前記集合を論理積の演算対象とし、一致したルールが一つも含まれない前記集合を論理積演算の対象から除外する機能を実現させる
ことを特徴とするプログラム。
【請求項４】
請求項３記載のプログラムが記録された前記情報処理装置読取可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はＩＰルータなどのパケット転送装置に利用する。特に、パケット転送処理を行うに当り、パケットヘッダ情報を元にパケットに対する処理を決定する際に検索するテーブルの検索方法に関する。
【０００２】
【従来の技術】
従来のＩＰルータなどのパケット転送装置では、パケットヘッダに搭載された宛先アドレスを元に経路表を検索し、次の方路を決定している。経路表には宛先アドレスと次の方路の関係を保持している。このように従来のインターネットでは宛先アドレスのみを用いた単純な転送処理を行うだけであった。
【０００３】
しかし、近年では、インターネットの広がりに伴い、従来の単純な転送処理だけでは十分でなくなっており、ヘッダに搭載された宛先アドレスだけでなく、送信元アドレスやＴＣＰ／ＵＤＰポート番号などを用いた高度な転送制御が必要となっている。
【０００４】
これらはポリシ制御やＱｏＳ制御に用いられる。例えば、特定のアプリケーションの通信を禁止する場合は、そのアプリケーションに割当てられたＴＣＰ／ＵＤＰポート番号のパケットが転送されないようにフィルタリングすることによりポリシ制御ができる。また、特定のユーザからの特定のアプリケーションのパケット転送のＱｏＳを上げるためには、そのユーザの送信元アドレスとＴＣＰ／ＵＤＰポート番号とを元にパケットの優先制御を行うことでＱｏＳ制御ができる。
【０００５】
これらの処理に必要なのがポリシテーブルの検索である。ポリシテーブルはパケットのヘッダ情報の複数のフィールド情報をキーとして検索し、そのパケットに対する扱いルールを決めるために用いられる。パケットヘッダのフィールド情報としては宛先アドレス（ＤＡ）、送信元アドレス（ＳＡ）、宛先ポート番号（ＤＰ）、送信元ポート番号（ＳＰ）、プロトコル識別子（ＰＩＤ）、サービス差別化符号（ＤＳＣＰ）などの６組が代表的なものである。
【０００６】
図７を参照して従来のポリシテーブルの検索例を示す。図７の符号Ｎ１、Ｎ２、Ｎ３はネットワークであり、符号Ｐはパケット転送装置である。なお、以下においては簡易な記述をするために、各フィールドは２進数で表記し、また＊はポリシテーブル検索時にはそれ以降のビットの値を無視することを示す。例えば、ＩＰｖ４の宛先アドレスは本来３２ｂｉｔｓあるが、宛先アドレスを１０＊と表記した場合には３ｂｉｔｓ目から３２ｂｉｔｓ目は検索時には無視することになる。したがって、ヘッダ情報中のＩＰｖ４の宛先アドレスが１００１００１１０…（全部で３２ｂｉｔｓ）のようなパケットがパケット転送装置に到着した場合には、ポリシテーブル上の宛先アドレスの項目に１０＊があれば、その項目とヘッダ情報の宛先アドレスとは一致したことになる。逆に、ポリシテーブル上に１０１＊というものがあった場合には一致しないことになる。
【０００７】
図７の従来のポリシテーブル検索例はポリシテーブルがパケット転送装置に設定されていて、パケットが入力されたときに、パケットのヘッダ情報とポリシテーブルとを比較し、ポリシテーブルのルールと一致した場合には、そのルールに記述されている処理を行うことを示している。例えば１００＊で示されるネットワークから１１００＊で示されるネットワークへパケットを送信した場合には、送信元アドレスが１００００…（全部で３２ｂｉｔｓ）、宛先アドレスが１１０００００…（全部で３２ｂｉｔｓ）のようなヘッダを持つパケットが送信される。このようなパケットがパケット転送装置に入力されると、ポリシテーブル上のルールＲ２に一致するため、このパケットは優先転送される。
【０００８】
【発明が解決しようとする課題】
ポリシテーブルの検索では、全てのエントリの中から問題のパケットのヘッダ情報に最も一致するものを答えとする必要がある。このような検索を行う一つの方法としてポリシテーブルを上から下まで全検索する方法が考えられる。しかしながらこの方法ではポリシテーブルのエントリの数が多くなると、検索に多大の時間を要する。
【０００９】
また、ツリーを使った検索方法がある。図８を参照して従来のツリーを使った検索方法を説明する。図中の円はツリーのノードを示す。ノードの中には宛先アドレスと次ノードへのポインタ、ルール番号が格納されている。
【００１０】
検索すべき宛先アドレスとノードに格納されている宛先アドレスとを比較しながら、ツリーを下方向へ分岐していく。検索はあるノードに検索すべきＩＰアドレスが到達したとき、そのノードが示す宛先アドレスと検索すべき宛先ＩＰアドレスの上位から必要なビット分（＊の直前のビットまでであり、１００＊ならば上位３ビット分）を比較する。一致しない場合は、検索を終了する。一致した場合は、一致したノード中の処理を記録する。
【００１１】
次に検索すべき宛先ＩＰアドレスで、比較したビットの一番最後の次ビットに注目し、自分よりも下のノード（以下、子ノードと呼ぶ）が存在する場合は子ノードへ移り、検索を続け、子ノードが存在しない場合は、検索を終了し、記録したルール番号からポリシテーブル中の処理を実行する。以下では１００００１０１…というＩＰアドレスを検索する場合の具体例を示す。
【００１２】
最初にＩＰアドレスの最初の１ビット目を見て０であるか１であるかを判断する。本例では、１であるので、ノード１００＊へ移り上位３ビット分を比較する。一致しているので次に検査ビットとなるＩＰアドレスの４ビット目を調べる。検査ビットが０なのでノード１０００１＊へ移るが、ここで一致しないため検索を終了し、ノード＊とノード１００＊の２つが一致したことになる。このように、ツリー構造を利用した方法はポリシテーブルを上から下まで全検索する方法と比べて高速に検索が出来るという利点がある。
【００１３】
次に、ツリー構造を利用した従来のポリシテーブル検索法の一例を示す。まず、図９にポリシテーブルの例を示す。図１０は、図９のポリシテーブルを元に作成したツリー構造を利用したポリシテーブル検索方法の例である。本検索例はフィールド情報毎にツリーを作成し、それぞれのツリーで検索を行うものである。
【００１４】
まず、ポリシテーブルのＤＡだけに着目してツリーを作成し（図１０のＤＡツリー）、同様にＳＡだけに着目してツリーを作成する（図１０のＳＡツリー）。パケットのヘッダ情報を検索するときには、ＤＡツリーにはヘッダ情報のＤＡだけを入れて検索を行い、同様に、ＳＡツリーにはヘッダ情報のＳＡだけを入れて検索を行う。各ツリーでの検索は最も長く一致するまで続ける最長一致検索を行う。
【００１５】
ツリー以外に一致テーブルを用意する。ツリー検索中に一致したルールが存在すれば、一致テーブルの一致したルールに印をつける。本例では一致したものには“１”を、不一致なものには“０”を印とした。各ツリーで独立に検索を行い、一致テーブルに記入していく。全ツリーの検索が終わった時点で一致テーブルを比較し、全フィールド情報で一致したルールを探すために、フィールド情報毎に論理積（ａｎｄ）をとっていく。具体的には、まず、ＤＡとＳＡとで論理積を演算する。その結果と次のフィールド情報（図１０の例ではないが、例えば上位プロトコルのフィールド情報など）と論理積を演算する。これを繰り返す。最終的に、全フィールドで一致したことが分かったルールを回答とする。図１０の例では、論理積を演算することでルールＲ３のみが一致を示し、論理積の結果として“１”が出る。
【００１６】
本方法は、最初に各ツリーを独立に検索して最後に一致テーブルの論理積を演算して最終的な結果を得ることを特徴としている。本方法の大きな課題は論理積を演算する所である。通常、プロセッサが１回の計算で論理積を演算することができるのが１６ｂｉｔ、３２ｂｉｔ、６４ｂｉｔ程度であり、例えば、図１１のように、１０００ルールでフィールド情報数が６個で、かつ論理積を演算することが可能なｂｉｔ数が３２ｂｉｔの場合には、１０００÷３２×５から、１５７回の計算が必要となり、最終的な結果を得るのに時間がかかるという問題がある。
【００１７】
本発明は、このような背景に行われたものであって、ポリシテーブルの検索を高速に実行することができるパケット転送装置およびネットワークおよびプログラムおよび記録媒体を提供することを目的とする。
【００１８】
【課題を解決するための手段】
本発明は、一致テーブルに記録された検索結果を最終的に論理積演算する際に、はじめから演算を行う必要のない部分を除外することにより、演算速度を高めることを特徴とする。
【００１９】
すなわち、本発明の第一の観点は、到来するパケットのヘッダ情報を抽出する手段と、当該ヘッダ情報に対応するパケットの扱いルールが記録されたポリシテーブルと、前記抽出する手段により抽出された前記ヘッダ情報と前記ポリシテーブルとを比較して前記ルールを特定する手段とを備え、前記ポリシテーブルは、前記ヘッダ情報に含まれる属性の異なる複数のフィールド情報毎に検索項目がそれぞれ設けられ、前記特定する手段は、前記検索項目毎に前記ヘッダ情報に含まれるフィールド情報と前記ポリシテーブルに含まれるフィールド情報とを比較した検索結果が一致した前記ルールについては“１”とし不一致の前記ルールについては“０”とする手段と、全ての前記検索項目に対する検索終了後に複数の前記ルールのそれぞれについて前記検索結果の論理積を演算する手段と、この論理積を演算する手段の演算結果が“１”となる前記ルールを当該パケットの扱いルールとして最終的に特定する手段とを備えたパケット転送装置である。
【００２０】
ここで、本発明の特徴とするところは、一つの前記検索項目が示すルールの範囲がもう一つの前記検索項目が示すルールの範囲を包含する関係を内包関係と定義し、少なくとも一つの前記検索項目についてこの内包関係にある前記ルールの集合をあらかじめ複数生成する手段が設けられ、前記論理積を演算する手段は、前記集合に含まれる前記ルールを除く他の前記ルールについては論理積の演算対象からあらかじめ除外する手段を備えたところにある。
【００２１】
ここで、内包関係についてさらに詳細に説明すると、ポリシテーブルで定義されるフィールド情報の多くが下位ビットを無視する＊で表されるためルールは範囲を持つことになる。簡単のためＤＡが４ビットと仮定しＤＡだけのルールしか存在しないとする。例えばＤＡ＝１＊は１０００から１１１１までを表すことになる。内包とは「下位ビットを無視する＊で表される２つのルール間で、１つのルールが示す範囲がもう１つのルールが示す範囲を含む」ということである。例えば１＊（１０００から１１１１）が示す範囲は１１＊（１１００から１１１１）が示す範囲を含むため、１＊は１１＊を内包するということになる。２つ以上のフィールドからなるものでも同様のことがいえる。例えばＤＡとＳＡの組（ＤＡ，ＳＡ）＝（１＊，１＊）が１つのルールＲ１であり、（ＤＡ，ＳＡ）＝（１１＊，１１＊）が１つのルールＲ２である場合には、Ｒ１のＤＡはＲ２のＤＡを内包し、かつＲ１のＳＡはＲ２のＳＡを内包するためルールＲ１はＲ２を内包する。
【００２２】
本発明では、少なくとも一つの検索項目に着目してこのような内包関係に基づく前記ルールの集合（実施例ではマルチヒット群と呼ぶ）をあらかじめ複数生成しておく。例えば最初の検索項目（ＤＡ）を用いて前記集合を生成した場合には、実際にパケットが到着すると、そのヘッダ情報に含まれるフィールド情報の最初の検索項目の検索結果は、前記集合のいずれかに含まれることになる。当該最初の検索項目の検索結果を含む前記集合は複数にわたる場合もある。最終的に論理積を演算するときには、当該最初の検索項目の検索結果が含まれない前記集合については、論理積を演算しても無効であることが既に明らかであるので、そのような無効となる論理積演算を除外することができる。これにより、ポリシテーブルの検索を高速に実行することができる。
【００２３】
本発明の第二の観点は、本発明のパケット転送装置を備えたことを特徴とするネットワークである。
【００２４】
本発明の第三の観点は、情報処理装置にインストールすることにより、その情報処理装置に、到来するパケットのヘッダ情報を抽出する機能と、当該ヘッダ情報に対応するパケットの扱いルールが記録されたポリシテーブルに相応する機能と、前記抽出する機能により抽出された前記ヘッダ情報と前記ポリシテーブルとを比較して前記ルールを特定する機能とを備え、前記ポリシテーブルは、前記ヘッダ情報に含まれる属性の異なる複数のフィールド情報毎に検索項目がそれぞれ設けられ、前記特定する機能は、前記検索項目毎に前記ヘッダ情報に含まれるフィールド情報と前記ポリシテーブルに含まれるフィールド情報とを比較した検索結果が一致した前記ルールについては“１”とし不一致の前記ルールについては“０”とする機能と、全ての前記検索項目に対する検索終了後に複数の前記ルールのそれぞれについて前記検索結果の論理積を演算する機能と、この論理積を演算する機能の演算結果が“１”となる前記ルールを当該パケットの扱いルールとして最終的に特定する機能とを備えたパケット転送装置に相応する機能を実現させるプログラムである。
【００２５】
ここで、本発明の特徴とするところは、一つの前記検索項目が示すルールの範囲がもう一つの前記検索項目が示すルールの範囲を包含する関係を内包関係と定義し、少なくとも一つの前記検索項目についてこの内包関係にある前記ルールの集合をあらかじめ複数生成する機能を実現させ、前記論理積を演算する機能として、前記集合に含まれる前記ルールを除く他の前記ルールについては論理積の演算対象からあらかじめ除外する機能を実現させるところにある。
【００２６】
本発明の第四の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００２７】
これにより、コンピュータ装置等の情報処理装置により、ポリシテーブルの検索を高速に実行することができるパケット転送装置およびネットワークを実現することができる。
【００２８】
【発明の実施の形態】
本発明実施例を図１ないし図６を参照して説明する。図１は本実施例で用いる一致テーブルを示す図である。図２は本実施例のＤＡツリーによる検索方法を示す図である。図３は本実施例のＤＡツリーの検索結果が記録された一致テーブルを示す図である。図４は本実施例のＳＡツリーの検索結果が記録された一致テーブルを示す図である。図５は本実施例の論理的な一致テーブルと物理的メモリ上に展開された一致テーブルとを示す図である。図６は本実施例の具体的な論理積演算を説明するための図である。
【００２９】
本実施例はパケット転送装置の実施例であって、本実施例のパケット転送装置は、到来するパケットのヘッダ情報を抽出し、図１１に示すように、当該ヘッダ情報に対応するパケットの扱いルールが記録されたポリシテーブルを備え、抽出された前記ヘッダ情報と前記ポリシテーブルとを比較して前記ルールを特定する。
【００３０】
前記ポリシテーブルは、前記ヘッダ情報に含まれる属性の異なる複数のフィールド情報毎に検索項目がそれぞれ設けられ、前記検索項目毎に前記ヘッダ情報に含まれるフィールド情報と前記ポリシテーブルに含まれるフィールド情報とを比較した検索結果が一致した前記ルールについては“１”とし不一致の前記ルールについては“０”として図１に示すような一致テーブルを生成し、全ての前記検索項目に対する検索終了後に複数の前記ルールのそれぞれについて前記検索結果の論理積を演算し、この演算結果が“１”となる前記ルールを当該パケットの扱いルールとして最終的に特定する。
【００３１】
ここで、本実施例の特徴とするところは、一つの前記検索項目が示すルールの範囲がもう一つの前記検索項目が示すルールの範囲を包含する関係を内包関係と定義し、少なくとも一つの前記検索項目についてこの内包関係にある前記ルールの集合であるマルチヒット群をあらかじめ複数生成し、前記集合に含まれる前記ルールを除く他の前記ルールについては論理積の演算対象からあらかじめ除外するところにある。本実施例では最初の検索項目であるＤＡを用いてマルチヒット群を生成する例を示すが、他の検索項目の一つまたは複数を用いてマルチヒット群を生成することもできる。図１の例では、３つのマルチヒット群が記されており、到来するパケットのヘッダ情報に応じてこれら３つのマルチヒット群のいずれかが論理積演算対象として選択される。
【００３２】
本実施例のパケット転送装置は、情報処理装置であるコンピュータ装置により実現する。すなわち、コンピュータ装置にインストールすることにより、そのコンピュータ装置に、到来するパケットのヘッダ情報を抽出する機能と、当該ヘッダ情報に対応するパケットの扱いルールが記録されたポリシテーブルに相応する機能と、前記抽出する機能により抽出された前記ヘッダ情報と前記ポリシテーブルとを比較して前記ルールを特定する機能とを備え、前記ポリシテーブルは、前記ヘッダ情報に含まれる属性の異なる複数のフィールド情報毎に検索項目がそれぞれ設けられ、前記特定する機能は、前記検索項目毎に前記ヘッダ情報に含まれるフィールド情報と前記ポリシテーブルに含まれるフィールド情報とを比較した検索結果が一致した前記ルールについては“１”とし不一致の前記ルールについては“０”とする機能と、全ての前記検索項目に対する検索終了後に複数の前記ルールのそれぞれについて前記検索結果の論理積を演算する機能と、この論理積を演算する機能の演算結果が“１”となる前記ルールを当該パケットの扱いルールとして最終的に特定する機能とを備えたパケット転送装置に相応する機能を実現させるプログラムをコンピュータ装置にインストールすることにより、そのコンピュータ装置を本実施例のパケット転送装置に相応する装置とすることができる。
【００３３】
本実施例のプログラムの特徴とするところは、一つの前記検索項目が示すルールの範囲がもう一つの前記検索項目が示すルールの範囲を包含する関係を内包関係と定義し、少なくとも一つの前記検索項目についてこの内包関係にある前記ルールの集合であるマルチヒット群をあらかじめ複数生成する機能を実現させ、前記論理積を演算する機能として、前記集合に含まれる前記ルールを除く他の前記ルールについては論理積の演算対象からあらかじめ除外する機能を実現させるところにある。
【００３４】
本実施例のプログラムは本実施例の記録媒体に記録されることにより、コンピュータ装置は、この記録媒体を用いて本実施例のプログラムをインストールすることができる。あるいは、本実施例のプログラムを保持するサーバからネットワークを介して直接コンピュータ装置に本実施例のプログラムをインストールすることもできる。
【００３５】
これにより、コンピュータ装置により、ポリシテーブルの検索を高速に実行することができる本実施例のパケット転送装置を実現することができる。さらに、本実施例のパケット転送装置をネットワークに備えることにより、本実施例のネットワークを実現することができる。
【００３６】
以下では、本実施例をさらに詳細に説明する。
【００３７】
図１は本実施例を説明するための一致テーブルで、ＤＡフィールド情報上でマルチヒットするルールを集めてマルチヒット群を作成するように図１１で示されたポリシテーブルのルールを並べ替えている。図２は、図１１のポリシテーブルからＤＡツリーを構築し、ＤＡ＝Ｘなるパケットのヘッダ情報を検索し、ルールＲ２５０のＤＡを格納しているノードで最も長く一致したことを示すイメージ図である。
【００３８】
図２の検索終了後に行う動作を図３に示す。ルールＲ２５０のＤＡを格納しているノードは一致情報を持っている。一致情報とは当該ノードが検索時にルールの情報とヘッダ情報とが最も長く一致したノードであった場合の一致テーブルのデータであり、一致テーブルの中で書き込むべきメモリの番地と情報の中身を示す。
【００３９】
図３の例では、ルールＲ２５０のＤＡを格納しているノードは一致情報として、一致テーブルのＲ２５０のマルチヒット群が格納されているメモリ番地とそのメモリ番地に格納すべきルールの一致情報（どのルールが一致したか否かを“１”、“０”で表す。本例では一致したものは“１”、一致しなかったものは“０”）を持っており、これを利用して必要なメモリ番地にルールの一致情報を書込む。
【００４０】
１番目のツリー（本例ではＤＡツリー）の検索が終了後、２番目のツリーの検索を行う。本例では２番目のツリーの検索をＳＡツリーで行うこととし、具体的にＳＡを検索する例が図４である。ＳＡツリーでもヘッダ情報のＳＡとＳＡツリー上のノードに格納されているＳＡとを比較し、最も長く一致するノードが見つかるまで検索を行う。図４では、ルールＲ１５０のＳＡが格納されているノードが最も長く一致したノードである。このノードが最も長く一致した場合の一致情報（どのノードが一致したかの情報で、この場合は書込むべきメモリ番地を含んでいて必要なルールのみの一致情報だけを持っていればよいし、メモリ番地を含まずに全ルールの一致情報を持っていてもよい。本例ではメモリ番地を含まないこととする）をこのノードが持っており、これを一致情報に書込む。以降ＰＩＤといった検索に必要なフィールド情報毎のツリーを検索していき、同様に一致情報を書込んでいく。最後のツリー検索が終了した時点で検索は終了する。
【００４１】
検索終了後、ＤＡツリーで一致したマルチヒット群のみ（本例ではメモリ番地１０）で論理積をとり、最終的に一致したルールを得る。本実施例では最初に検索したツリーで一致したマルチヒット群のみの範囲で論理積をとればよいので、従来のように全ルールで論理積を演算する必要が無いため、論理積の回数を減らすことができる。
【００４２】
なお、図中の一致テーブルは論理的なテーブルを示したが、実際にメモリ上に展開した場合には、横方向に１０００個のルールを並べることはできない。図５は、例えば３２ｂｉｔ分しかメモリの横方向に並べることができない場合に、一致テーブルを実際のメモリに格納した例を示す。
【００４３】
さらに具体的な本実施例の論理積演算について図６を参照して説明する。図６に示すＤＡツリーでは、ルールＲ１、Ｒ１００、Ｒ１２０＝＊となっており、これらのルールＲ１、Ｒ１００、Ｒ１２０が他の全てのルールを内包する関係にある。そこで、図６の例では、まず、ルールＲ１、Ｒ１００、Ｒ１２０により一つのマルチヒット群として＊群を生成する。
【００４４】
次に、ルールＲ１５０＝１＊に着目すると、ルールＲ１５０は、ルールＲ２３０＝１０＊およびＲ２５０＝１１＊およびＲ３１０＝１１１＊を内包する。そこで、図６の例では、ルールＲ１５０、Ｒ２３０、Ｒ２５０、Ｒ３１０により一つのマルチヒット群としてマルチヒット群２を生成する。また、ルールＲ２＝０＊に着目すると、ルールＲ２は、ルールＲ５６０＝００＊およびＲ５９９＝０００＊を内包する。そこで、図６の例では、ルールＲ２、Ｒ５６０、Ｒ５９９により一つのマルチヒット群としてマルチヒット群３を生成する。
【００４５】
このような状況下で、例えば、ヘッダ情報にＤＡ＝１０００というフィールド情報を含むパケットが到着したときには、ＤＡ＝１０００は、ルールＲ１、Ｒ１００、Ｒ１２０＝＊に該当するので、＊群に含まれる。さらに、ＤＡ＝１０００は、ルールＲ２３０＝１０＊に該当するので、マルチヒット群２に含まれる。
【００４６】
このような場合に、最終的に論理積を演算するマルチヒット群は、＊群およびマルチヒット群２である。結果的に２回の論理積を演算する必要があるが、従来例と比較しても十分少なくて済む。
【００４７】
【発明の効果】
以上説明したように、本発明によれば、高速にポリシテーブル検索を行うことができる。
【図面の簡単な説明】
【図１】本実施例で用いる一致テーブルを示す図。
【図２】本実施例のＤＡツリーによる検索方法を示す図。
【図３】本実施例のＤＡツリーの検索結果が記録された一致テーブルを示す図。
【図４】本実施例のＳＡツリーの検索結果が記録された一致テーブルを示す図。
【図５】本実施例の論理的な一致テーブルと物理的メモリ上に展開された一致テーブルとを示す図。
【図６】本実施例の具体的な論理積演算を説明するための図。
【図７】パケット転送装置の概念図。
【図８】従来のツリー検索方法を説明するための図。
【図９】ポリシテーブルを示す図。
【図１０】従来のフィールド情報毎のツリー検索方法を説明するための図。
【図１１】従来の論理積演算を説明するための図。
【符号の説明】
Ｎ１、Ｎ２、Ｎ３  ネットワーク
Ｐ  パケット転送装置
【図１】
0003779619.tif 000002
【図２】
0003779619.tif 000003
【図３】
0003779619.tif 000004
【図４】
0003779619.tif 000005
【図５】
0003779619.tif 000006
【図６】
0003779619.tif 000007
【図７】
0003779619.tif 000008
【図８】
0003779619.tif 000009
【図９】
0003779619.tif 000010
【図１０】
0003779619.tif 000011
【図１１】
0003779619.tif 000012