(57)【要約】【課題】  ＩＰルータなどのパケット転送装置において、ＶＰＮのルーティングテーブルの検索が遅く、また、更新が遅く、経済的かつ大規模なエントリを実現できないという課題を解決する。【解決手段】  入力ＩＰパケットの属するＶＰＮを識別するためのＶＰＮ識別子をもつＶＰＮテーブル検索ツリーと、この入力ＩＰパケットの次ホップを決定するための次ホップ識別子を持つルーティングテーブル検索用ツリーとをＶＰＮ毎にそれぞれ生成する手段を備え、前記ＶＰＮテーブル検索ツリーには、入力ＩＰパケットが属するＶＰＮを識別するためのＶＰＮ識別子と、このＶＰＮに対応するルーティングテーブル検索用ツリーへのポインタとが格納され、前記ルーティングテーブル検索用ツリーには、入力ＩＰパケットの次ホップを決定するための識別子が次ホップ情報に対応して格納される。【選択図】  図１
2005051650.tif 000002
【特許請求の範囲】
【請求項１】
入力回線から入力されたＩＰ(Internet Protocol)パケットを識別し、このパケットの次ホップ（パケットを次に転送するルータのアドレス）を決定するためにツリーを用いるテーブル検索装置において、
入力ＩＰパケットの属するＶＰＮ(Virtual Private Network)を識別するためのＶＰＮ識別子と、このＶＰＮに対応するルーティングテーブル検索用ツリーへのポインタとを持つＶＰＮテーブル検索ツリーを保持する手段と、
この入力ＩＰパケットの次ホップを決定するための次ホップ識別子を持つルーティングテーブル検索用ツリーをＶＰＮ毎にそれぞれ保持する手段と
を備えた
ことを特徴とするテーブル検索装置。
【請求項２】
ＩＰパケットが入力された際にはこのＩＰパケットのＶＰＮの識別に用いる情報とルーティングテーブル検索に用いる情報とをそれぞれ抽出する手段と、
抽出した前記ＶＰＮの識別に用いる情報と前記ＶＰＮテーブル検索ツリーに格納されたＶＰＮ識別子とを比較する手段と、
この比較する手段の比較結果として得られた前記ルーティングテーブル検索用ツリーへのポインタに対応する前記ルーティングテーブル検索用ツリーを選択する手段と、
抽出した前記ルーティングテーブル検索に用いる情報と前記選択する手段により選択された前記ルーティングテーブル検索用ツリーに格納された次ホップ識別子とを比較して次ホップを検索する手段と
を備えた請求項１記載のテーブル検索装置。
【請求項３】
入力回線から入力されたＩＰパケットを識別し、このパケットの次ホップを決定するためにツリーを用いるテーブル検索装置において、
入力ＩＰパケットの属するＶＰＮを識別するためのＶＰＮ識別子をもつＶＰＮテーブル検索ツリーと、このツリーの末端ノードにそれぞれ接続されたこの入力ＩＰパケットの次ホップを決定するための次ホップ識別子を持つルーティングテーブル検索用ツリーとを保持する手段を備えた
ことを特徴とするテーブル検索装置。
【請求項４】
ＩＰパケットが入力された際にはこのＩＰパケットのＶＰＮの識別に用いる情報とルーティングテーブル検索に用いる情報とをそれぞれ抽出する手段と、
抽出した前記ＶＰＮの識別に用いる情報と前記ＶＰＮテーブル検索ツリーに格納されたＶＰＮ識別子とを比較する手段と、
この比較する手段の比較結果として到達した前記末端ノードに接続された前記ルーティングテーブル検索用ツリーを用いて、抽出した前記ルーティングテーブル検索に用いる情報と当該末端ノードに接続された前記ルーティングテーブル検索用ツリーに格納された次ホップ識別子とを比較して次ホップを検索する手段と
を備えた請求項３記載のテーブル検索装置。
【請求項５】
情報処理装置にインストールすることにより、その情報処理装置に、請求項１ないし４のいずれかに記載のテーブル検索装置の各手段または各ツリーに相応する機能を実現させることを特徴とするプログラム。
【請求項６】
請求項５記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＩＰルータなどのパケット転送装置に利用する。特に、パケット転送処理を行うに当たり、入力回線から入力されたパケットのヘッダ情報からパケットの次ホップを決定する際に使用するテーブル検索装置に関する。
【背景技術】
【０００２】
従来は、ＩＰルータなどのパケット転送装置では、パケットヘッダに搭載された宛先アドレスを元にルーティングテーブルを検索し、次ホップを決定していた。ルーティングテーブルには宛先アドレスと次ホップの関係を保持している。このように従来のインターネットでは宛先アドレスのみを用いた単純な転送処理を行うだけであった。
【０００３】
近年、インターネットの広がりに伴い、従来の単純な転送処理だけでは十分でなくなってきた。特に、最近ＶＰＮサービスが広がりを見せている。ＶＰＮはキャリアがキャリアの顧客に対して仮想的なネットワークを提供するサービスである。仮想的なネットワークは顧客から見ると専用のプライベートなネットワークとして見える。専用なネットワークに見せることで、顧客に対しセキュリティの確保、ＩＰアドレスの自由な付与、顧客のニーズにあったサービスをキャリアは提供可能となる。
【０００４】
図９にＶＰＮサービスの実現例を示す。パケット転送装置には複数ＶＰＮが接続されている。異なるＶＰＮ間は独立として扱うことができるように、パケット転送装置にはＶＰＮを識別するための識別子とそのＶＰＮのルーティングテーブルをＶＰＮ毎に設定する。このため、同じＶＰＮ内での転送はＶＰＮ内に閉じた形で行うことができる。図９ではＶＰＮ識別子として入力回線とＩＰパケットの送信元アドレスを使用している例を示している。ＶＰＮ識別子としては、これだけでなくＬ２のアドレス（Ｅｔｈｅｒｎｅｔ（登録商標）ならばＭＡＣアドレス）等も使用することが考えられる。
【０００５】
パケット転送装置で宛先アドレスを検索する規則を説明する。パケット転送装置においては、パケットヘッダに搭載された宛先アドレスを元にルーティングテーブルを検索し、次ホップを決定する。ルーティングテーブルには宛先アドレスと次ホップの関係を保持している。インターネットではＣＩＤＲ(Classless Inter Domain Routing)の機構が導入されており、ルーティングテーブルの宛先アドレスは３２ビットのＩＰアドレスとそれに対するプレフィクス長の組み合わせで表現される。ルーティングテーブルの宛先アドレスは“ＩＰアドレス／プレフィクス長”の形式で表される。
【０００６】
宛先アドレスのうち、プレフィクス長で指定された長さ以降のビットに関してはＤｏｎ‘ｔ  Ｃａｒｅである。例えば１２９．１３１．１７５．１２９／３２は３２ビット全てのビットがＤｏｎ’ｔ  Ｃａｒｅでない宛先アドレスであり、１２９．６０．８３／２４は先頭の２４ビットが有効な宛先アドレスである。パケットヘッダの宛先アドレスが１２９．６０．８３．１も１２９．６０．８３．１１１も同じ宛先アドレス１２９．６０．８３／２４に一致する。
【０００７】
ルーティングテーブルはパケットヘッダの宛先アドレスをキーとして用いて検索する。ルーティングテーブルを検索する際に、ＣＩＤＲでは最長一致と呼ばれるルーティングテーブル検索規則に基づく。最長一致とはキーに用いる宛先アドレスが最も長く一致するものを正解とするものである。例えば、ルーティングテーブルに宛先アドレス１２９．３８．１１１／２４と宛先アドレス１２９．３８／１６の二つの宛先アドレスがある場合に、１２９．３８．１１１．２という宛先アドレスを持つパケットが到着した場合は、宛先アドレス１２９．３８．１１１／２４の方がより長い範囲で一致するので、それを正解とする。
【０００８】
宛先アドレスを検索する従来例としてツリーを用いた方式とＴＣＡＭ(Ternary
Content Addressable Memory)を用いた方式を紹介する。図１０にツリーの中でもパトリシアツリーを用いて宛先アドレスを検索する例を示す。図中の円はツリーのノードを示す。ノードの中には宛先アドレスと次ノードへのポインタ、ルール番号が格納されている。なお、図は簡易な表記をするために、宛先アドレスは２進数で表記し、また＊は検索時にはそれ以降のビットの値を無視することを示す。例えば、ＩＰｖ４の宛先アドレスは本来３２ｂｉｔｓあるが、宛先アドレスを１０＊と表記した場合には３ｂｉｔｓ目から３２ｂｉｔｓ目は検索時には無視することになる（有効ビット長をプレフィック長と呼ぶ）。従ってパケットヘッダの中のＩＰｖ４の宛先アドレスが１００００１０１…（全部で３２ｂｉｔｓ）のようなパケットがパケット転送装置に到着した場合には、ルーティングテーブル上の宛先アドレスの項目に１０＊があれば、その項目とパケットヘッダの宛先アドレスは一致したことになる。逆にルーティングテーブル上に１０１＊というものがあった場合には一致しないことになる。
【０００９】
パトリシアツリーを利用した検索は、検索すべき宛先アドレスとノードに格納されている宛先アドレスとを比較しながら、ツリーを下方向へ分岐していく。検索はあるノードに検索すべきＩＰアドレスが到達したとき、そのノードが示す宛先アドレスと検索すべき宛先ＩＰアドレスの上位から必要なビット分（＊の直前のビット）までであり、１００＊ならば上位３ビット分を比較する。一致しない場合は、検索を終了する。一致した場合は、一致したノード中の処理を記録する。
【００１０】
次に検索すべき宛先ＩＰアドレスで、比較したビットの一番最後の次ビットに注目し、自分よりも下のノード（以下、子ノードと呼ぶ）が存在する場合は子ノードへ移り、検索を続け、子ノードが存在しない場合は、検索を終了し、記録したルール番号からポリシテーブル中の処理を実行する。以下では１００００１０１…という宛先アドレスを検索する場合の具体例を図１０を用いて示す。
【００１１】
最初に宛先アドレスの最初の１ビット目を見て“０”であるか“１”であるかを判断する。本例では、“１”であるので、ノード１００＊へ移り上位３ビット分を比較する。一致しているので次に検査ビットとなるＩＰアドレスの４ビット目を調べる。検査ビットが０なのでノード１０００１＊へ移るが、ここで一致しないため検索を終了し、ノード＊とノード１００＊の２つが一致したことになる（例えば、特許文献１参照）。
【特許文献１】特開２０００−３５８０６４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１２】
このようなツリーを用いた方式は、ＳＲＡＭやＤＲＡＭといった汎用のメモリを用いることで実現可能であるため、経済的な装置を構築することが可能であり、大規模なエントリをサポートすることが可能であるという特徴を持つが、ＶＰＮ識別子には送信元アドレスのようにＤｏｎ‘ｔ  Ｃａｒｅを含むようなものがあるので、単純にパトリシアツリーの検索ビット幅を増やすだけではＶＰＮのルーティングテーブル検索を実現することができないという課題がある。
【００１３】
ルーティングテーブル検索にＴＣＡＭ(Ternary-Content-Addressable-Memory)を使う方法がある。ＴＣＡＭとはアドレスをキーとしてアクセスするのではなく、各番地に記録された値をキーとしてアクセスすることができる記憶素子である。ＴＣＡＭの各番地には“０”と“１”のバイナリ（Ｂｉｎａｒｙ）の値だけでなく、“Ｄｏｎ‘ｔ  Ｃａｒｅ”も格納することができる。このようなＴＣＡＭを用いることで高速なルーティングテーブルの検索が可能となる。ＴＣＡＭでは複数のものが同時にキーとして入力されたものに一致する場合は、最も若い番地にいるものが選ばれる。ＴＣＡＭを用いて最長一致検索を行う場合はプレフィクス長が長い順番にＴＣＡＭの若番地に格納する必要がある。
【００１４】
最低条件は同じプレフィクス部分を共有する経路同士はプレフィクス長が長いものより若い番地に格納される必要がある。ＴＣＡＭの格納領域をプレフィクス長毎に分割するのが簡便なやり方である。図１１はそのような領域の分け方を示すものである。１２９．６０．８３．１２１／３１はプレフィクス長が３１の領域に格納し、１２９．６０．８３．１２１／３０は３０の領域に格納する。ＴＣＡＭを用いる場合は、このように並べ替えが必要となり、更新に時間がかかるという問題がある。また商用のＴＣＡＭの多くは“０”と“１”と“Ｄｏｎ‘ｔ  Ｃａｒｅ”をどの位置にでも配置することが可能で、単純にＶＰＮ識別子とルーティングテーブルのエントリを並べるだけで検索することは可能であるが、ＴＣＡＭの容量には限界がありＴＣＡＭ自体の構造が複雑で大規模にはできない。また原理的にアドレスを同時に多く探すので、非常に大きな消費電力を要し、かつ高価であるため経済的ではない。
【００１５】
本発明は、このような背景に行われたものであって、ＩＰルータなどのパケット転送装置において、ＶＰＮのルーティングテーブルの検索が遅く、また、更新が遅く、経済的かつ大規模なエントリを実現できないという課題を解決することを目的とする。
【課題を解決するための手段】
【００１６】
本発明は、入力回線から入力されたＩＰパケットを識別し、このパケットの次ホップを決定するためにツリーを用いるテーブル検索装置であって、本発明の特徴とするところは、入力ＩＰパケットの属するＶＰＮを識別するためのＶＰＮ識別子と、このＶＰＮに対応するルーティングテーブル検索用ツリーへのポインタとを持つＶＰＮテーブル検索ツリーを保持する手段と、この入力ＩＰパケットの次ホップを決定するための次ホップ識別子を持つルーティングテーブル検索用ツリーをＶＰＮ毎にそれぞれ保持する手段とを備えたところにある。
【００１７】
このように、ＶＰＮ毎に個別に検索を実行するために、従来のように、ＶＰＮ毎に分かれていない一つの大規模なツリーを一括検索する場合と比較して検索速度を高速化することができる。
【００１８】
さらに、ＶＰＮテーブル検索ツリーとルーティングテーブル検索用ツリーとを別個に持つことにより、ＶＰＮ識別子が更新された場合と、次ホップ識別子が更新された場合とで、それぞれ個別に識別子の更新を実行することができるため、更新速度を高速化することができる。
【００１９】
このように、ポインタを用いてＶＰＮテーブル検索ツリーとルーティングテーブル検索用ツリーとを接続する構成では、これら二つのツリーを物理的あるいは論理的に別個のメモリ領域に格納して実装することができる。
【００２０】
また、ＩＰパケットが入力された際にはこのＩＰパケットのＶＰＮの識別に用いる情報とルーティングテーブル検索に用いる情報とをそれぞれ抽出する手段と、抽出した前記ＶＰＮの識別に用いる情報と前記ＶＰＮテーブル検索ツリーに格納されたＶＰＮ識別子とを比較する手段と、この比較する手段の比較結果として得られた前記ルーティングテーブル検索用ツリーへのポインタに対応する前記ルーティングテーブル検索用ツリーを選択する手段と、抽出した前記ルーティングテーブル検索に用いる情報と前記選択する手段により選択された前記ルーティングテーブル検索用ツリーに格納された次ホップ識別子とを比較して次ホップを検索する手段とを備えることができる。
【００２１】
一方、これら二つのツリーが物理的あるいは論理的に別個のメモリ領域に格納されていない場合には、ポインタを用いてこれら二つのツリーを接続する必要はなく、直接、ＶＰＮテーブル検索ツリーの末端ノードに、ＶＰＮ毎にルーティングテーブル検索用ツリーを接続してもよい。
【００２２】
すなわち、本発明のテーブル検索装置は、入力ＩＰパケットの属するＶＰＮを識別するためのＶＰＮ識別子をもつＶＰＮテーブル検索ツリーと、このツリーの末端ノードにそれぞれ接続されたこの入力ＩＰパケットの次ホップを決定するための次ホップ識別子を持つルーティングテーブル検索用ツリーとを保持する手段を備えたことを特徴とする。
【００２３】
また、ＩＰパケットが入力された際にはこのＩＰパケットのＶＰＮの識別に用いる情報とルーティングテーブル検索に用いる情報とをそれぞれ抽出する手段と、抽出した前記ＶＰＮの識別に用いる情報と前記ＶＰＮテーブル検索ツリーに格納されたＶＰＮ識別子とを比較する手段と、この比較する手段の比較結果として到達した前記末端ノードに接続された前記ルーティングテーブル検索用ツリーを用いて、抽出した前記ルーティングテーブル検索に用いる情報と当該末端ノードに接続された前記ルーティングテーブル検索用ツリーに格納された次ホップ識別子とを比較して次ホップを検索する手段とを備えることができる。
【００２４】
本発明の他の観点は、情報処理装置にインストールすることにより、その情報処理装置に、本発明のテーブル検索装置の各手段あるいは各ツリーに相応する機能を実現することを特徴とするプログラムである。
【００２５】
また、本発明のさらに他の観点は、本発明のプログラムが記録された前記情報処理装置読取可能な記録媒体である。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００２６】
これにより、汎用の情報処理装置を用いて、ＩＰルータなどのパケット転送装置においてツリーを用いたＶＰＮのルーティングテーブルの検索を高速に、更新を高速に、経済的かつ大規模なエントリを実現することができるテーブル検索装置を実現することができる。
【発明の効果】
【００２７】
本発明は、ＩＰルータなどのパケット転送装置においてツリーを用いたＶＰＮのルーティングテーブルの検索を高速に、更新を高速に、経済的かつ大規模なエントリを実現することができる。
【発明を実施するための最良の形態】
【００２８】
以下本発明の実施例２つを説明する。
【実施例１】
【００２９】
図１は第一実施例のテーブル検索装置の構成図である。図１のように検索処理や各ツリーの更新処理を行う処理部１と、ＶＰＮを識別するためのＶＰＮテーブル検索ツリーを格納するＲＡＭ２−１とＶＰＮ毎のルーティングテーブル検索用ツリーを格納するＲＡＭ２−２から成る。処理部１にパケットが入力されるとパケットのヘッダから、ＶＰＮ識別をするための情報（例えば入力回線番号と送信元アドレス）と宛先パケットを抜き出す。
【００３０】
まず初めにＶＰＮ識別をするための情報を検索キーとし、ＲＡＭ２−１のＶＰＮテーブル検索ツリーを用いて検索を行う。検索結果としてＶＰＮ毎のルーティングテーブル検索用ツリーのポインタを得る。
【００３１】
次に、このポインタによってＶＰＮ毎のルーティングテーブル検索用ツリーを識別し、抜き出した宛先アドレスをキーとしてＲＡＭ２−２のＶＰＮ毎のルーティングテーブル検索用ツリーを用いて検索を行う。検索結果として次ホップを得る。得られた次ホップに向けてパケットを送出する。図２にＶＰＮテーブル検索ツリーを格納するＲＡＭ２−１に入れるべき情報を示す。なお、本例ではツリーとしてパトリシアツリーを採用した場合の例を示す。
【００３２】
また、本例ではＶＰＮ識別をするための情報として入力回線番号と送信元アドレスを採用している。０Ｅ、１Ｅとは次ビットが０あるいは１の子ノードが存在するか否かを示すビットである。例えば図９の１００＊のノードには次ビットが０のノードが存在するので０Ｅは存在することを示すビットが立ち、同様に次ビットが１のノードが存在するので１Ｅは存在することを示すビットが立つ。
【００３３】
０−Ａｄｄｒｅｓｓ、１−Ａｄｄｒｅｓｓは、子ノードが格納されているＲＡＭの物理アドレスを示す。ＶＰＮＥはＶＰＮ毎のルーティングテーブル検索用ツリーのポインタがそのノードに存在するかしないかを示す。Ｐｏｉｎｔｅｒ  ｏｆ  ＶＰＮはＶＰＮ毎のルーティングテーブル検索用ツリーへのポインタであり、具体的にはＶＰＮ毎のルーティングテーブル検索用ツリーが格納されているＲＡＭ２−２の物理アドレスである。これらの情報を利用してパトリシアツリーの検索を行う。
【００３４】
検索キーとして回線番号と送信元アドレスで各ノードで検索を行い、子ノードへとさらに検索を進めるために０−Ａｄｄｒｅｓｓ、１−Ａｄｄｒｅｓｓを利用して子ノードが格納されているＲＡＭの物理アドレスを得る。物理アドレスを元に子ノードへと検索を進め、最終的に検索結果として、ポインタを得ることが可能となる。
【００３５】
図３はＶＰＮ毎のルーティングテーブル検索用ツリーを格納するＲＡＭ２−２に入れるべき情報を示す。なお、本例ではツリーとしてパトリシアツリーを採用した場合の例を示す。ＯＵＴＥは次ホップがそのノードに存在するかしないかを示す。検索方法は図２の説明と変わらない。最終的な結果として次ホップを得ることができる。
【００３６】
図４は本実施例の検索の論理的なイメージを図にしたものである。ＶＰＮテーブル検索ツリーを検索後、ＶＰＮ毎のポインタを利用して各ＶＰＮのルーティングテーブル検索用ツリーを検索するというものである。ＶＰＮを識別するためのＶＰＮテーブル検索ツリーを格納するＲＡＭ２−１とＶＰＮ毎のルーティングテーブル検索用ツリーを格納するＲＡＭ２−２とを分けるので、ＶＰＮ内でのルーティングテーブルの更新はＶＰＮに閉じて行うことが出来るので高速に更新を行うことが可能となる。また、ツリーを用いているので経済的な装置を構築が可能であり、大規模なエントリをサポートすることが可能であるという利点も持つ。
【実施例２】
【００３７】
図５は第二実施例のテーブル検索装置の構成図である。図５のように検索処理や各ツリーの更新処理を行う処理部１と、ＶＰＮルーティングテーブル一括検索用ツリーを格納するＲＡＭ３から成る。処理部１にパケットが入力されるとパケットのヘッダから、ＶＰＮ識別をするための情報（例えば入力回線番号と送信元アドレス）と宛先アドレスを抜き出す。ＶＰＮ識別をするための情報と宛先アドレスを繋げて、一つの検索キーとしてＶＰＮルーティングテーブル一括検索用ツリーを利用し検索を行う。図６はＶＰＮルーティングテーブル一括検索用ツリーの一例を示す図である。図６に示すように、ＶＰＮルーティングテーブル一括検索用ツリーは、図４に示したＶＰＮテーブル検索ツリーの末端ノードに、さらに、図４に示したルーティングテーブル検索用ツリーがＶＰＮ毎に直接に接続された構成である。
【００３８】
ＶＰＮを識別するための情報の種別として２種類ある。１つ目は入力回線番号などのように一意の値であるような情報である。２つ目は送信元アドレスのようにＤｏｎ‘ｔ  Ｃａｒｅの部分が存在し値が一意でない情報である。第二実施例では、ＶＰＮ検索と次ホップ検索とを一本のツリーで行うため、Ｄｏｎ’ｔ  Ｃａｒｅ部分が存在すると、その部分でツリーの接続が途切れてしまう。したがって、第二実施例では、このＤｏｎ‘ｔ  Ｃａｒｅ部分を回避する対策が必要になる。なお、第一実施例では、ＶＰＮ検索のためのツリーがＤｏｎ’ｔ  Ｃａｒｅ部分で途切れたら、その時点でＶＰＮ検索を終了し、次ホップ検索のためのポインタを取得することができるので、Ｄｏｎ‘ｔ  Ｃａｒｅ部分が存在してもよい。
【００３９】
ここで、Ｄｏｎ‘ｔ  Ｃａｒｅ部分を回避するために、Ｄｏｎ’ｔ  Ｃａｒｅの部分が存在し値が一意でない情報を一意な情報に変換する方法を述べる。例えば、３ｂｉｔの値で１０＊は１００と１０１の２つと等価である。図７に一意でない送信元アドレスを増やすことで一意の情報にし、ＶＰＮ用のルーティングテーブルを構築した例を示す。
【００４０】
すなわち、図７の例では、元々は送信元アドレスが１９２．１６８．１．１８０／３０であり、３０ビット目から３２ビット目まではＤｏｎ‘ｔ  Ｃａｒｅ部分である。これを回避するためには、１９２．１６８．１．１８０／３２、１９２．１６８．１．１８１／３２、１９２．１６８．１．１８２／３２、１９２．１６８．１．１８３／３２という複数の送信元アドレスを生成して対応する。つまり、Ｄｏｎ’ｔ  Ｃａｒｅ部分とは、言い換えると「なんでもよい」部分ということである。したがって、このように、複数の送信元アドレスを適宜生成することによってツリー検索上で不都合が発生しないように対応することができる。
【００４１】
この例のようにＶＰＮを識別するための情報の種別として一意でない情報が含まれていても、一意な情報の集合にすることが可能である。図８にＶＰＮルーティングテーブル一括検索用ツリーを格納するＲＡＭ３に入れるべき情報を示す。このＶＰＮ用のルーティングテーブルを利用して、ＶＰＮルーティングテーブル一括検索用ツリーを構築することで一度にＶＰＮの識別に用いる情報とルーティングテーブル検索に用いる情報を検索することが可能となる。一度に検索を行うことが可能であるため高速な検索が可能となる。ツリーを用いているので経済的な装置を構築が可能であり、大規模なエントリをサポートすることが可能であるという利点を持つ。
【実施例３】
【００４２】
本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のテーブル検索装置に相応する機能を実現させるプログラムとして実現することができる。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、処理部１に相応する機能を実現させることができる。
【産業上の利用可能性】
【００４３】
本発明は、ＩＰルータなどのパケット転送装置においてツリーを用いたＶＰＮのルーティングテーブルの検索を高速に、更新を高速に、経済的かつ大規模なエントリを実現することができる。これにより、今後共、大きな需要が見込まれるＶＰＮの運営に際し、ユーザあるいは管理者の利便性を向上させることができる。
【図面の簡単な説明】
【００４４】
【図１】第一実施例の装置構成例を示す図。
【図２】ＶＰＮテーブル検索ツリーを格納するＲＡＭに入れるべき情報を示す図。
【図３】ＶＰＮ毎のルーティングテーブル検索用ツリーを格納するＲＡＭに入れるべき情報を示す図。
【図４】第一実施例の検索の論理イメージを示す図。
【図５】第二実施例のテーブル検索装置の構成例を示す図。
【図６】ＶＰＮルーティングテーブル一括検索用ツリーの一例を示す図。
【図７】一意でない送信元アドレスを増やすことで一意の情報にし、ＶＰＮ用のルーティングテーブルを構築することを説明するための図。
【図８】ＶＰＮルーティングテーブル一括検索用ツリーを格納するＲＡＭに入れるべき情報を示す図。
【図９】ＶＰＮサービスの実現例を説明するための図。
【図１０】パトリシアツリーを説明するための図。
【図１１】ＴＣＡＭを用いて最長一致検索を行う場合にエントリをプリフィックス長に分けて格納することを説明するための図。
【符号の説明】
【００４５】
１  処理部
２−１、２−２、３  ＲＡＭ
【図１】
2005051650.tif 000003
【図２】
2005051650.tif 000004
【図３】
2005051650.tif 000005
【図４】
2005051650.tif 000006
【図５】
2005051650.tif 000007
【図６】
2005051650.tif 000008
【図７】
2005051650.tif 000009
【図８】
2005051650.tif 000010
【図９】
2005051650.tif 000011
【図１０】
2005051650.tif 000012
【図１１】
2005051650.tif 000013