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