(57)【要約】【課題】  ＶＰＮ対応に独立したテーブルを用い、ＶＰＮ毎に並列に検索することにより、１つの宛先アドレスが複数のＶＰＮに属する利用形態を許容することができると共に、検索時間を短縮する。【解決手段】  バイナリツリーを１つ集約し、このバイナリツリーを構成する各ノードには、ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子を備える。バイナリツリーは、ノードの識別番号と、ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子と、読み出されるビット値に対応した次ノードの識別番号とを記録する記憶領域をノード数分含むメモリによりバイナリツリー実装する。【選択図】  図１
2005051649.tif 000002
【特許請求の範囲】
【請求項１】
複数のＶＰＮユーザが、独立したＩＰアドレス体系を用いて、１つのネットワークで、仮想的に独立のネットワークを構成するＶＰＮ(Virtual Private Network)におけるテーブル検索装置において、
ＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値に基づき枝分かれするバイナリツリーを備え、
このバイナリツリーを構成する各ノードには、ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子を備えた
ことを特徴とするＶＰＮ用テーブル検索装置。
【請求項２】
前記ノードの識別番号と、前記ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子と、前記読み出されるビット値に対応した次ノードの識別番号とを記録する記憶領域を前記ノード数分含むメモリと、
このメモリに含まれる前記記憶領域に記録された前記ノードの情報を検索対象として入力ＩＰパケットの宛先アドレスに対応する出力ポートを決定するテーブル検索手段と
を備え、
このテーブル検索手段は、前記記憶領域に記録された１つの前記ノードの情報を検索対象として検索を行い、次ノードへの接続が有るときには、前記入力ＩＰパケットのＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値と前記次ノードの識別番号とを比較して一致した次ノードの識別番号の前記ノードに相応する前記記憶領域に記録された情報に検索対象を拡張させる手段を備えた
請求項１記載のＶＰＮ用テーブル検索装置。
【請求項３】
複数のＶＰＮユーザが、独立したＩＰアドレス体系を用いて、１つのネットワークで、仮想的に独立のネットワークを構成するＶＰＮにおけるテーブル検索装置に適用されるプログラムにおいて、
情報処理装置にインストールすることにより、その情報処理装置に、
ＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値に基づき枝分かれするバイナリツリーに相応する機能を実現させ、
このバイナリツリーを構成する各ノードには、ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子を備えた
ことを特徴とするプログラム。
【請求項４】
前記ノードの識別番号と、前記ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子と、前記読み出されるビット値に対応した次ノードの識別番号とを記録する記憶領域を前記ノード数分含むメモリに相応する機能と、
このメモリに含まれる前記記憶領域に記録された前記ノードの情報を検索対象として入力ＩＰパケットの宛先アドレスに対応する出力ポートを決定するテーブル検索手段に相応する機能と
を実現させ、
このテーブル検索手段に相応する機能として、前記記憶領域に記録された１つの前記ノードの情報を検索対象として検索を行い、次ノードへの接続が有るときには、前記入力ＩＰパケットのＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値と前記次ノードの識別番号とを比較して一致した次ノードの識別番号の前記ノードに相応する前記記憶領域に記録された情報に検索対象を拡張させる機能を実現させる
請求項３記載のプログラム。
【請求項５】
請求項３または４記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はＶＰＮ(Virtual Private Network)における宛先アドレスに対応する出力ポートが記録されたテーブルの検索技術に関する。
【背景技術】
【０００２】
図４に従来のＶＰＮネットワークの構成を、図５に従来のルータの構成を示す。従来ネットワークでは基本的に、ＩＰアドレスを重複無く使用する形でＶＰＮを実現する。また、ルータでもこのＩＰアドレスをベースにルーティングを行う。
【０００３】
ＶＰＮを実現する場合は、あらかじめ登録されているＳＡ（ソース・アドレス）に許されているＤＡ（宛先アドレス）であることも監視され、他のＶＰＮから当該ＶＰＮへパケットが混入することも防いでいる（例えば、特許文献１または２参照）。図８に示すように、宛先アドレス（ＤＡ）に対応する出力ポート番号が記録されたテーブルを用いて、入力ＩＰパケットを所定の出力ポートに振り分ける。
【特許文献１】特開２０００−３５８０６４号公報
【特許文献２】特開２０００−３３２７８６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来は、複数のＶＰＮが一つのテーブルに記録され、ＦＥ（フォワーディングエンジン）は、宛先アドレス（ＤＡ）に基づき出力ポートを決定する。このときに、例えば、記録されている宛先アドレスの最上段から順に検索を行い、入力ＩＰパケットの宛先アドレスと一致したところで出力ポートを決定する。
【０００５】
また、従来のＶＰＮは、図５に示すように、宛先アドレスによってＶＰＮが分類されている。したがって、前述したように、ＩＰアドレスを重複なく使用することが必要である。これは、１つの宛先アドレスが複数のＶＰＮに属することは許されていないことを意味する。
【０００６】
しかし、多種多様なＶＰＮの利用形態が要求される昨今では、１つの宛先アドレスが複数のＶＰＮに属するといったＶＰＮの利用形態も必要となる場合があり得る。例えば、ユーザ＃３はＶＰＮ＃１およびＶＰＮ＃２の双方に属しており、ＶＰＮ＃１のユーザ＃１からのＩＰパケットおよびＶＰＮ＃２のユーザ＃２からのＩＰパケットの双方をユーザ＃３が受け取るというＶＰＮ利用形態を実現しようとしても従来のＶＰＮは、このような要求に対応することは困難だった。
【０００７】
また、ＩＰアドレスの重複を許さないために、必然的に、ＩＰアドレスの一覧からなる１つの大規模なテーブルを用いることになる。このような１つの大規模なテーブルを用いて検索を行うと、テーブルのデータ量が膨大であるため、検索に長い処理時間を要する問題がある。
【０００８】
本発明は、このような背景に行われたものであって、ＶＰＮ対応に独立したテーブルを用い、ＶＰＮ毎に並列に検索することにより、１つの宛先アドレスが複数のＶＰＮに属する利用形態を許容することができると共に、検索時間を短縮することができるＶＰＮ用テーブル検索装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、ＶＰＮ毎に独立したテーブルを用い、ＶＰＮ毎に並列に検索することを特徴とするが、その場合には、図６に示すように、ＶＰＮ毎にそれぞれバイナリツリーを設け、テーブル検索装置は、これらの複数のバイナリツリーに対して検索を行う構成が考えられる。
【００１０】
このように、複数のバイナリツリーに対して検索を行うためには、各バイナリツリーを格納する記憶領域を用意し、また、バイナリツリーの構成が個々に異なるため、バイナリツリーの数分の異なった検索制御手段を用意しなければならない。
【００１１】
そこで、本発明では、バイナリツリーを１つ集約し、それぞれのノードにＶＰＮ毎のネクストホップを示す出力ポート番号等の情報を持つことを主たる特徴とする。これにより、バイナリツリーの検索制御手段が単一で済み、テーブル検索装置の処理負荷を軽減させることができる。
【００１２】
すなわち、本発明は、複数のＶＰＮユーザが、独立したＩＰアドレス体系を用いて、１つのネットワークで、仮想的に独立のネットワークを構成するＶＰＮにおけるテーブル検索装置であって、本発明の特徴とするところは、ＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値に基づき枝分かれするバイナリツリーを備え、このバイナリツリーを構成する各ノードには、ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子を備えたところにある。
【００１３】
これにより、１つのバイナリツリーで複数のＶＰＮ毎のテーブル検索を実現することができる。また、次ノードへの接続の有無を示す識別子を備えることにより、ＶＰＮ毎にバイナリツリーの構成が異なっている場合には、この識別子を用いてツリーの末端位置を可変することができる。すなわち、次ノードへの接続が無いとすれば、そのノードがツリーの末端位置になり、次ノードへの接続が有るとすれば、そのノードよりも下位にツリーの末端位置があることになる。
【００１４】
本発明のバイナリツリーは、例えば、１個のメモリによって簡単かつ経済的に実現することができる。すなわち、前記ノードの識別番号と、前記ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子と、前記読み出されるビット値に対応した次ノードの識別番号とを記録する記憶領域を前記ノード数分含むメモリと、このメモリに含まれる前記記憶領域に記録された前記ノードの情報を検索対象として入力ＩＰパケットの宛先アドレスに対応する出力ポートを決定するテーブル検索手段とを備え、このテーブル検索手段は、前記記憶領域に記録された１つの前記ノードの情報を検索対象として検索を行い、次ノードへの接続が有るときには、前記入力ＩＰパケットのＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値と前記次ノードの識別番号とを比較して一致した次ノードの識別番号の前記ノードに相応する前記記憶領域に記録された情報に検索対象を拡張させる手段を備えることができる。
【００１５】
本発明の他の観点は、複数のＶＰＮユーザが、独立したＩＰアドレス体系を用いて、１つのネットワークで、仮想的に独立のネットワークを構成するＶＰＮにおけるテーブル検索装置に適用されるプログラムであって、本発明の特徴とするところは、情報処理装置にインストールすることにより、その情報処理装置に、ＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値に基づき枝分かれするバイナリツリーに相応する機能を実現させ、このバイナリツリーを構成する各ノードには、ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子を備えたところにある。
【００１６】
さらに具体的には、前記ノードの識別番号と、前記ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子と、前記読み出されるビット値に対応した次ノードの識別番号とを記録する記憶領域を前記ノード数分含むメモリに相応する機能と、このメモリに含まれる前記記憶領域に記録された前記ノードの情報を検索対象として入力ＩＰパケットの宛先アドレスに対応する出力ポートを決定するテーブル検索手段に相応する機能とを実現させ、このテーブル検索手段に相応する機能として、前記記憶領域に記録された１つの前記ノードの情報を検索対象として検索を行い、次ノードへの接続が有るときには、前記入力ＩＰパケットのＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値と前記次ノードの識別番号とを比較して一致した次ノードの識別番号の前記ノードに相応する前記記憶領域に記録された情報に検索対象を拡張させる機能を実現させることができる。
【００１７】
本発明のさらに他の観点は、本発明のプログラムが記録された前記情報処理装置読み取り可能な記録媒体である。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００１８】
これにより、汎用の情報処理装置を用いて、ＶＰＮ対応に独立したテーブルを用い、ＶＰＮ毎に並列に検索することにより、１つの宛先アドレスが複数のＶＰＮに属する利用形態を許容することができると共に、検索時間を短縮することができるＶＰＮ用テーブル検索装置を実現することができる。
【発明の効果】
【００１９】
本発明によれば、ＶＰＮ対応に独立したテーブルを用い、ＶＰＮ毎に並列に検索することにより、１つの宛先アドレスが複数のＶＰＮに属する利用形態を許容することができると共に、検索時間を短縮することができる。
【発明を実施するための最良の形態】
【００２０】
本発明実施形態を図１および図２を参照して説明する。図１は本実施形態のバイナリツリーを示す図である。図２は本実施形態のバイナリツリーを構成するノードでのテーブルの持ち方を示す図である。
【００２１】
本実施形態は、複数のＶＰＮユーザが、独立したＩＰアドレス体系を用いて、１つのネットワークで、仮想的に独立のネットワークを構成するＶＰＮにおけるテーブル検索装置であって、本発明の特徴とするところは、図１に示すように、ＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値に基づき枝分かれするバイナリツリーを備え、このバイナリツリーを構成する各ノードには、図２に示すように、ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子を備えたところにある。
【００２２】
入力パケットは、そのＩＰアドレスの最下位ビットから、１ビットずつ“０”もしくは“１”であることを判別していく。例では“０１”の場合は、その該当するノードに持ったＶＰＮ毎のデータを図２に示している。
【００２３】
“０１”では、ＶＰＮ毎にそのノードで終端した場合のＮＨ（ネクストホップ）の出力ポート番号が記載されている。また、ｅｎｄマークというものがあり、例ではｅｎｄマークが“−”の場合は、次ノードがある可能性があり、ｅｎｄマークがｅｎｄの場合は当該ＶＰＮ−ＩＤにおいては、次ノードが存在しない。そのため、このノードで以降は検索しなくてよい。
【００２４】
例えば、ＶＰＮ＃が＃２の場合、Ｐｏｒｔ＃１７の可能性があるが、次ノードが存在する可能性があり、次ノードの検索を行う。しかし、次ノードが例えば“０１０”はあるが、“０１１”はなく、パケットのＩＰアドレスが“０１１…”であれば、出力ポートはＰｏｒｔ＃１７となる。
【００２５】
次に、本実施形態のバイナリツリーのメモリを用いた実現例を図３に示す。図３はメモリ上でのバイナリツリーの構成例を示す図である。図３に示すように、ノードの識別番号と、ＶＰＮ毎の次出力ポート番号および次ノードへの接続の有無を示す識別子であるｅｎｄマークと、読み出されるビット値に対応した次ノードの識別番号とを記録する記憶領域を前記ノード数分含むメモリを備える。
【００２６】
さらに、このメモリに含まれる前記記憶領域に記録された前記ノードの情報を検索対象として入力ＩＰパケットの宛先アドレスに対応する出力ポートを決定するテーブル検索部１０を備え、このテーブル検索部１０は、前記記憶領域に記録された１つの前記ノードの情報を検索対象として検索を行い、次ノードへの接続が有るときには、前記入力ＩＰパケットのＩＰヘッダの最下位ビットから最上位ビットに向けて順に読み出されるビット値と前記次ノードの識別番号とを比較して一致した次ノードの識別番号の前記ノードに相応する前記記憶領域に記録された情報に検索対象を拡張させる手段を備える。
【００２７】
すなわち、メモリ上に格納されたバイナリツリーは図３のように、“０１０”等のツリーのノードとＶＰＮ毎のＮＨ等が格納される。また、ノード毎のテーブルの最後には、次ビットが“０”の場合と“１”の場合の、次のノードの格納されているアドレスのチェーンがある。つまり、検索部でこのチェーンを辿っていくと、順にバイナリツリーのサーチができる。
【００２８】
本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のＶＰＮ用テーブル検索装置に相応する機能を実現させるプログラムとして実現することができる。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、本実施形態のメモリおよびテーブル検索部１０にそれぞれ相応する機能を実現させることができる。
【産業上の利用可能性】
【００２９】
本発明のテーブル検索装置は、ＶＰＮ対応に独立したテーブルを用い、ＶＰＮ毎に並列に検索することにより、１つの宛先アドレスが複数のＶＰＮに属する利用形態を許容することができると共に、検索時間を短縮することができるので、多種多様なＶＰＮ利用形態に対応することができるため、ユーザの利便性を向上させることができる。また、バイナリツリーを１つに集約することにより、検索制御を簡単化し、また、バイナリツリーを１つのメモリによって実現できるため、装置を経済的に構成することができる。
【図面の簡単な説明】
【００３０】
【図１】本実施形態のバイナリツリーの構成例を示す図。
【図２】本実施形態のバイナリツリーの１つのノードでのデータの維持のしかたを示す図。
【図３】本実施形態のメモリ上でのバイナリツリーの構成例を示す図。
【図４】従来のＶＰＮネットワークを示す図。
【図５】従来のルータの構成を示す図。
【図６】ＶＰＮ毎に分岐されたバイナリツリーの例を示す図。
【符号の説明】
【００３１】
１０  テーブル検索部
【図１】
2005051649.tif 000003
【図２】
2005051649.tif 000004
【図３】
2005051649.tif 000005
【図４】
2005051649.tif 000006
【図５】
2005051649.tif 000007
【図６】
2005051649.tif 000008