(57)【要約】【課題】通信ネットワークのルーティングを行うための検索テーブルへのアドレスの追加や削除を容易にすること。【解決手段】アドレス検索装置３１０は、分割ビット列の各階層のテーブルを備えた検索テーブル３１１と、分割ビット列検索ブロック３１２と、これから得られた検索結果情報３１３を基にしてデータ信号の振り分けのための情報を取得する出力先振り分け情報取得ブロック３１４と、出力先振り分け情報テーブル３１５とで構成されている。ＩＰアドレス３１６は複数の階層の分割ビット列に順次分解され、先頭から一意に定まるビット列となる階層の検索テーブル３１１とそのときの分割ビット列との組み合わせによって出力先振り分け情報が読み出される。【選択図】　　　　図４
2004056639.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワークから次のルートに振り分けるべきデータ信号を入力し、そのデータ信号の最終的な宛先に至るルートを表わしたビット列からなるルート情報を予め定めたビット列ずつ先頭から区切ってそれぞれの階層の分割ビット列として順に取り出す分割ビット列取り出し手段と、
各ルート情報に対応した前記データ信号の振り分け先を示す出力先振り分け情報を記憶した出力先振り分け情報記憶手段と、
前記分割ビット列取り出し手段によって取り出す可能性のある分割ビット列をそれぞれ対応する階層に配置したときに形成される木構造の各節に相当する位置にそれぞれ検索テーブルノードを配置し、これらの検索テーブルノードの各々に、対応する分割ビット列から次の検索テーブルノードを指示する次検索テーブルノード指示情報あるいは次の検索テーブルノードが存在しないときには前記出力先振り分け情報記憶手段における前記データ信号の振り分け先を示す出力先振り分け情報が記載されている前記出力先振り分け情報記憶手段の該当箇所を指示する出力先振り分け情報格納箇所指示情報を記憶した検索テーブルと、
前記分割ビット列取り出し手段によって取り出した分割ビット列を用いて、第１の階層の検索テーブルノードから次検索テーブルノード指示情報が読み出される間、分割ビット列を順に取り出しながら検索テーブルノードを１階層ずつ階層を高めて検索を行い、出力先振り分け情報格納箇所指示情報が検索された時点でこの階層の移動を停止して検索する階層を確定する階層確定手段と、
この階層確定手段によって確定した検索テーブルノードから読み出された出力先振り分け情報格納箇所指示情報を用いて前記出力先振り分け情報記憶手段から前記データ信号についての出力先振り分け情報を読み出す出力先振り分け情報読み出し手段
とを具備することを特徴とするアドレス検索装置。
【請求項２】
前記検索テーブルノードのうちで次検索テーブルノード指示情報を格納しているもののみが、前記次検索テーブルノード指示情報を格納する領域を配置していることを特徴とする請求項１記載のアドレス検索装置。
【請求項３】
各階層の検索テーブルノードは、そのテーブルノードに連結する次の階層の検索テーブルノードが存在するか否かを示す有効情報有無情報を配置していることを特徴とする請求項１記載のアドレス検索装置。
【請求項４】
前記出力先振り分け情報格納箇所指示情報は、出力先振り分け情報記憶手段における出力先振り分け情報が記憶されている領域と、その領域における出力先振り分け情報の格納箇所を示す番地とで構成されていることを特徴とする請求項１記載のアドレス検索装置。
【請求項５】
前記出力先振り分け情報記憶手段における出力先振り分け情報が記憶されている領域は、対応する分割ビット列を構成するビット数の二乗の数の番地を備えていることを特徴とする請求項４記載のアドレス検索装置。
【請求項６】
前記分割ビット列取り出し手段が順に取り出す分割ビット列は、それぞれ互いに等しいビット数で構成されていることを特徴とする請求項１記載のアドレス検索装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は通信ネットワークでパケット信号等のデータ信号の送出先としてのアドレスを検索するアドレス検索装置に係わり、たとえばインターネットでパケット信号の振り分けを行うルータにおける振り分け先の検索処理に好適なアドレス検索装置に関する。
【０００２】
【従来の技術】
インターネットに代表される通信ネットワークを使用した各種通信が広範囲に行われている。このような通信ネットワークで複数のネットワークを接続するための装置の１つとしてルータがある。ルータは、ＩＰ（Ｉｎｔｅｒｎｅｔ　Ｐｒｏｔｏｃｏｌ）パケット信号等のデータ信号の送出先を示すルート情報を検索することで、その受信したデータ信号をどの出力ポートから出力させるかを決定するようになっている。そして、ネットワーク上に複数配置されたそれぞれのルータがこのように受信したデータ信号の出力先を次々と決定し出力先を振り分けていくことで経路が設定されていき、そのデータ信号がその経路に沿って最終的な宛先に転送されることになる。
【０００３】
このルーティングの様子は、ちょうど電話番号の最初の数字から順にそれぞれ対応する交換機が出力先を振り分けていき、最終的にその電話番号の全桁と一致する相手先が発呼されるのと似ている。
【０００４】
このため、インターネット等の通信ネットワークでデータ信号の振り分けを行う各ルータは、入力されたデータ信号のルート情報を基にして、そのデータ信号がそのルータの複数の出力ポートの中のいずれから出力されるべきかを決定し、決定した出力ポートからデータ信号を送出することになる。このような出力ポートの選択動作を可能にするために、個々のルータは検索テーブルを備えており、この検索結果に応じて出力ポートの選択を行っている。
【０００５】
ところで通信ネットワークでは、データ信号を受信する端末が追加されたり削除されるといった変化が生じる場合がある。たとえば今までＡという送出先を示すルート情報がきたときにそのルータが第１の出力ポートを選択してデータ信号を転送していたのに、第１の出力ポート側のある端末が削除されて、そのルートを辿っても送出先に行き着かないような場合である。このような場合には、たとえば第３の出力ポートを経て、迂回するような形で相手先にデータ信号を送信するといったようなルートの変更が行われるような場合がある。このような場合に対処するために、ネットワークの構成に変更が生じたときには、個々のルータに備えられている検索テーブルに新たなデータを登録したり、既存のデータの削除あるいは変更が行われる。
【０００６】
データ信号がＩＰパケット信号である場合を例にとって説明することにする。ルータに備えられる検索テーブルには、ＩＰパケット信号の次の転送先としての「出力インタフェースまたは次の中継先であるルータのＩＰアドレス」といった出力ポートを選択するための出力先振り分け情報が、データ信号の有する「ＩＰサブネットアドレス」および「プレフィックス長」として登録されている。
【０００７】
ここでサブネットとは、ネットワークを複数のネットワークに分割したものをいう。たとえばＩＰアドレスはネットワークアドレスとホスト番号から構成されており、ホスト番号の上位の所定ビットがサブネット番号としてネットワークを分割するために用いられている。プレフィックス（Ｐｒｅｆｉｘ）長とは、アドレスのうち有効ビット列の長さをビット数で表わしたもの（有効ビット列長）である。
【０００８】
検索テーブルの検索を行うにあたっては、検索テーブルに登録されたもの中から、最終的にロンゲストプレフィックスマッチ（Ｌｏｎｇｅｓｔ　Ｐｒｅｆｉｘ　Ｍａｔｃｈ）法により、ＩＰアドレスと最も長く一致する「ＩＰサブネットアドレス」を決定するようにしている。すなわち、ロンゲストプレフィックスマッチ法では、登録されているＩＰアドレスのうち、検索キーのＩＰアドレスと一致する有効ビット列が最も長いものを選択する。たとえばビット長が３ビットのＩＰアドレスとして、ビット列“０＊＊”および“００＊”の２つが登録されているものとする。ここでビット列“０＊＊”は、先頭ビットの“０”のみが有効ビット値で、２番目以降の“＊＊”は、“０”または“１”の任意の値を表わしている。また、ビット列“００＊”は、１ビット目および２ビット目の“００”が有効ビット値で、３番目の“＊”は、“０”または“１”の任意の値を表わしている。
【０００９】
検索テーブルによる検索では、転送されてきたＩＰパケットの最終的な送信先を示す、検索キーとしてのＩＰアドレスと、登録されているこれら２つの登録ＩＰアドレスとをそれぞれ照合する。検索キーのＩＰアドレスを“０００１…”とした場合、ビット列“００＊”の方が“０＊＊”よりも、登録ＩＰアドレスと一致するプレフィックス長が長い。したがって、この場合、次の転送先のＩＰアドレスとしてビット列“００＊”が選択されることになる。
【００１０】
ところで、ＩＰアドレスのビット数が、この例のように３ビット程度と短い場合には、その検索も容易である。しかしながら実際に使用されるＩＰアドレスのビット数は、これよりも遥かに長い。例えば、ＩＰプロトコルとしてのＩＰｖ４（Ｉｎｔｅｒｎｅｔ　Ｐｒｏｔｏｃｏｌ　ｖｅｒｓｉｏｎ　４）におけるアドレス長は、３２ビットとなっている。近年標準化された他のＩＰプロトコルとしてのＩＰｖ６（Ｉｎｔｅｒｎｅｔ　Ｐｒｏｔｏｃｏｌ　ｖｅｒｓｉｏｎ　６）では、アドレス長が１２８ビットと一層長くなっている。このため、ルータでＩＰアドレスを基にして出力先振り分け情報を得るための検索処理の効率化が問題となる。
【００１１】
従来のこのような検索手法としては、バイナリ・ツリー（Ｂｉｎａｒｙ　Ｔｒｅｅ）検索方法とプレフィックス拡張（Ｐｒｅｆｉｘ　Ｅｘｐａｎｓｉｏｎ）検索方法が存在している。バイナリ・ツリー検索方法は、２分木データ構造を利用した手法である。
【００１２】
図１７および図１８は、バイナリ・ツリー検索法の概念を説明するためのものである。このうち図１７は８つのＩＰアドレスＰ１〜Ｐ８のビットパターンを表わしている。先に説明したように符号“＊”は、“０”または“１”の任意の値を表わしているものとする。
【００１３】
図１８はバイナリ・ツリー検索法を示している。この例では、登録ＩＰアドレスＰ１〜Ｐ８がルートの起点１０１を基にツリー構造を構成している。バイナリ・ツリー検索方法では、先頭から１ビット単位でビット列のビット値の比較を順番に行う。このため、ツリーを構成する各ノードは、この図に示すようにビット列の各ビット値（“０”または“１”）にそれぞれ対応している。
【００１４】
特開平１１−１９１７８１号公報には、ハードウェア回路でバイナリ・ツリーの検索を実現するようにしたアドレス検索装置が開示されている。この提案のバイナリ・ツリー検索方法では、検索を高速化するために必要のない枝を除去した木構造で経路テーブルを構成するようにしている。更にこの検索テーブルをハードウェアを用いて検索することで高速な経路検索を可能にしている。
【００１５】
しかしながら特開平１１−１９１７８１号公報に開示されたバイナリ・ツリー検索方法では、木構造の形態によって最大アドレスのビット数の分岐が発生することがあり得る。たとえばＩＰｖ４の場合には、図１８に示した８ビット構成のＩＰアドレスとは異なり、３２ビットのＩＰアドレスを採用している。このため、図１８よりも複雑な木構造となって、最大で３２回の分岐が発生することになる。このように最大で３２回の分岐が発生すると、最大でこの分岐の数だけノードへのアクセスが必要になる。このため、バイナリ・ツリー検索方法はノードへのアクセス数が多くなる可能性があって、検索の効率が悪いという欠点を持つ。特開平１１−１９１７８１号公報では、アドレス検索装置あるいはアドレス検索方法をソフトウェアで実現するのではなく高速処理に適したハードウェアで実現している。しかしながら、たとえハードウェアで回路構成を行ったとしても、ノードへのアクセスが多ければ検索の効率はソフトウェアと手法の違いによる差ということになって、本質的な改善にはならない。そこで、分岐の回数自体を減少させるためにプレフィックス拡張検索方法を使用したアドレス検索装置あるいはアドレス検索方法が提案されている。
【００１６】
図１９は、プレフィックス拡張検索方法を説明するためのものである。特開２０００−３０７６４１号公報等で提案されているプレフィックス拡張検索方法では、ＩＰアドレスのビット列を複数の分割ビット列に分割する。そして、分割後のこれら分割ビット列を階層化して、階層化された分割ビット列ごとに検索テーブル１１１〜１１４を設けるようにしている。そして、各検索テーブル１１１〜１１４では、各分割ビット列をそれぞれエントリアドレスとしている。すなわち、図１９に示した例では、合計７ビット分のビット列を、１番上の階層では２ビット分、次の階層では３ビット分、一番下の階層では２ビット分の３階層の分割ビット列に分割している。そして、１段目の検索テーブル１１１および３段目の検索テーブル１１４では、“００”〜“１１”の４つの分割ビット列をそれぞれエントリアドレスとしている。また、２段目の検索テーブル１１２、１１３では、“０００”〜“１１１”の８つの分割ビット列をエントリアドレスとしている。
【００１７】
このプレフィックス拡張検索方法では、検索テーブルの登録アドレスを更新する際に、そのアドレスがあるテーブルの位置で終了するか次のテーブルに継続するかを表わすための終了・継続フラグ、次の転送先のＩＰアドレスなどを示す次テーブルポインタや送信インタフェースの情報そのものを、その検索テーブルの各エントリの中の、登録し得るすべてのエントリにそれぞれ重複して設定している。また、ＩＰアドレスの登録にあたっては、各検索テーブルにおいて、各分割ビット列のビット長に満たないエントリのビット列を各分割ビット列の末端まで拡張している。たとえばある階層での分割ビットが３ビットであるにもかかわらず、エントリのビット列が１ビットあるいは２ビットである場合には、これらをそれぞれ３ビットに拡張している。このようにビット列を共通の長さのビット列にまで拡張すると、拡張前のビット列を共有する複数のエントリが、共通の登録ＩＰアドレスに対応することになる。
【００１８】
図２０は、図１７に示した元となる（Ｏｒｉｇｉｎａｌ）ＩＰアドレスと３つのレベルに拡張された（Ｅｘｐａｎｄｅｄ）ＩＰアドレスを対比して示したものである。この図２０に示した例では、ＩＰアドレスＰ１〜Ｐ８の登録ＩＰアドレスをそれぞれ、各分割ビット列の最下位ビットまで拡張するようにしている。例えば、有効ビット列長としてのプレフィックス長が“１”であるＩＰアドレスＰ５のビット列“０＊”（図２０（Ｏｒｉｇｉｎａｌ））は、１ビット分だけ拡張されて、２ビットのビット列“００”および“０１”となる（図２０（Ｅｘｐａｎｄｅｄ））。そして、１段目の検索テーブル１１１（図１９）では、エントリアドレスがビット列“００”および“０１”の両方のエントリに、ＩＰアドレスＰ５がそれぞれ重複する形で登録される。
【００１９】
また、例えば、プレフィックス長が“３”であるＩＰアドレスＰ２のビット列“１１１＊”（図２０（Ｏｒｉｇｉｎａｌ））は、２ビット分だけ拡張されて、５ビットのビット列“１１１００”、“１１１０１”、“１１１１０”および“１１１１１”の４つのエントリとなる（図２０（Ｅｘｐａｎｄｅｄ））。２段目の検索テーブル１１２、１１３（図１９）では、３ビット目〜５ビット目として得られた分割ビット列がエントリアドレスとなる。したがって、エントリアドレスが、“１００”、“１０１”、“１１０”および“１１１”の４つのエントリに、ＩＰアドレスＰ２がそれぞれ登録されることになる。更に、他の登録ＩＰアドレスも同様に拡張して登録される。
【００２０】
このように、ビット列を拡張して登録することにより、登録ＩＰアドレスを検索テーブルの特定のエントリアドレスと対応付けることができる。その結果、各段の検索テーブルの検索にあたり、登録ＩＰアドレスの分割ビット列をそのままフルに対応付けて一致検索処理を行うことができる。したがって、プレフィックス拡張検索方法を採用すると、検索回数は、最大でも、検索テーブルの段数（階層数）で済むことになり、ＩＰアドレスの構成ビット数を最大検索回数とする先の例よりも検索回数を大幅に減少させることができる。例えば、図１９に示した例では、３段の検索テーブル（１１１）、（１１２、１１３）、（１１４）を設けているので、検索回数は最大でも３回で済む。このように、プレフィックス拡張検索方法によれば、検索回数を大幅に減らすことができる。
【００２１】
このプレフィックス拡張検索方法を使用したアドレス検索装置の検索テーブル１１１〜１１４には、先に説明した終了・継続フラグの他に、出力先振り分け情報、出力先振り分け情報のポインタが有効か無効かを示すフラグ、次に検索するビット列の検索テーブルへのポインタ等のエントリ情報が設定されている。これらの情報は、登録可能なすべてのエントリに書きこまれる。たとえばビット列“０＊”の場合には、１ビット分だけ拡張された後の２ビットのビット列“００”および“０１”の双方についてエントリ情報が設定されることになる。
【００２２】
また、分割ビット列のビット長に満たないビット列を登録するときは、ビット列を末端まで拡張して登録することは先に説明した。ビット列を拡張すると、拡張前のビット列で包含されるすべての分割ビット列のテーブルに、拡張前のビット列に対応するエントリ情報をすべて書き込む。ただし、ここで書き込みについて問題が生じる。ビット列を拡張して登録する場合には、複数のビット列がそれぞれを拡張した結果として１つの拡張後のビット列に共通して対応してしまう場合があるからである。これについては次に説明するが、拡張前のビット列におけるその中の１つが拡張後のビット列と対応するような選別が行われる。したがって、このような場合にはその選別されたビット列に対応させてエントリ情報を書き込むことになる。
【００２３】
図２１および図２２は、拡張前のあるビット列の長さよりも長い他の拡張前のビット列が存在する場合の例を説明するためのものである。ここで図２１は先の例とは異なる４つのＩＰアドレスＰ１〜Ｐ４のビットパターンを表わしている。ここで例えばＩＰアドレスＰ１はビット列“０”（１ビット長）であり、これを４ビットのビット列に拡張するとするとビット例“０＊＊＊”となる。具体的には“００００”、“０００１”、“００１０”、“００１１”、“０１００”、“０１０１”、“０１１０”、“０１１１”の８種類となる。
【００２４】
ＩＰアドレスＰ２はビット列“０１０”（３ビット長）であり、これを４ビットのビット列に拡張するとするとビット例“０１０＊”となる。具体的には“０１００”、“０１０１”の２種類となる。ＩＰアドレスＰ３はビット列“１０１０”（４ビット長）であるので、このままで４ビットのビット列となる。ビット列の拡張は必要ない。
【００２５】
ＩＰアドレスＰ４はビット列“１０”（２ビット長）であり、これを４ビットのビット列に拡張するとするとビット例“１０＊＊”となる。具体的には“１０００”、“１００１”、“１０１０”、“１０１１”の４種類となる。
【００２６】
図２２は、拡張後の４ビットのビット列と、拡張されたＩＰアドレスを対応付けたものである。４ビットのビット列の組み合わせはこの図に示すように１６通り存在する。ところが、図２１に示した４つのＩＰアドレスＰ１〜Ｐ４のビット列からは生じえないビット列が図２２には含まれている。すなわち、第１のビットが“１”で第２のビットも“１”のものは図２１では存在しない。対象とするルータではそのようなビット列のルート情報が到来することが想定されないからである。そこで、図２２では４つのビット列“１１００”、“１１０１”、“１１１０”、“１１１１”はＩＰアドレスとして登録しない（ＮＵＬＬ）。このため、残りの１２通りのビット列をＩＰアドレスＰ１〜Ｐ４と対応付けて登録することになる。たとえばビット列“００００”はＩＰアドレスＰ１として登録することになる。
【００２７】
ここで、拡張後の複数のＩＰアドレスが４ビットのビット列に重複して対応する場合がある。そこで、これらのいずれを対応付けるかが問題となる。たとえばビット列“０１００”は、元のビット列“０”のＩＰアドレスＰ１と、元のビット列“０１０”のＩＰアドレスＰ２と競合することになる。同様にビット列“０１０１”についてもＩＰアドレスＰ１およびＩＰアドレスＰ２の間で、いずれを対応付けるかが問題となる。
【００２８】
このように拡張後の複数のＩＰアドレスが４ビットの所定のビット列に重複して対応する場合には、それぞれの拡張前のビット列の長い方を優先させて対応させる。すなわち長い方の拡張前のビット列に対応するエントリ情報を書き込むようにしている。これら２つの例の場合には、元のビット列“０”のＩＰアドレスＰ１よりも元のビット列“０１０”のＩＰアドレスＰ２の方が拡張前のビット列が長い。そこで、図２２に示すようにこれらについてはＩＰアドレスＰ２が対応付けられることになる。ビット列“１０１０”についてのＩＰアドレスＰ３とＩＰアドレスＰ４の場合にも、同様の約束でＩＰアドレスＰ３が採択される。
【００２９】
図２３は、従来の検索テーブルの内容を表わしたものである。出力先振り分け情報を「ＮＨＰ情報」と表示すると、この図に示す従来のプレフィックス拡張方法では、拡張したビット列“０００”〜“１１１”とこれら「ＮＨＰ情報」を対応付けると共に、それぞれのビット列“０００”〜“１１１”に対応させて次の階層の検索テーブルのノードへのポインタを用意していた。ここで、「次の階層のノードへのポインタ」を「ＬＰＴＲ」と略称することにする。
【００３０】
図２４は、図２３に対応するもので、従来における分割ビット列を管理するアドレス検索装置の構成の概要を表わしたものである。従来のアドレス検索装置１２０は、検索テーブル１２１とビット列管理テーブル１２２とがＩＰアドレス管理処理ブロック１２３と接続された構成となっている。このように従来のアドレス検索装置１２０は、ビット列管理テーブル１２２が必須のものとなっている。
【００３１】
図２５は、図２４に示した従来のアドレス検索装置で検索テーブルにおけるビット列の登録、削除あるいは更新を行う際のビット更新の処理の流れを表わしたものである。この場合、まず、対象となるビット列をビット列管理テーブル１２２（図２４）に登録したり、ビット列管理テーブル１２２から削除したり、あるいは更新処理を行う（ステップＳ２０１）。次に、ビット列管理テーブル１２２から拡張前のビット列を取得する（ステップＳ２０２）。そして、先に説明したような処理でこれらのビット列を所定のビット数の列に拡張する（ステップＳ２０３）。次に、検索テーブル１２１に書き込むビット列を計算する（ステップＳ２０４）。この計算に際して、ビット列が同一のものがあった場合には、図２１で説明したように拡張前のビット列が長い方を選択する。以上のようにして求めたビット列を検索テーブル１２１（図２４）に書き込んで（ステップＳ２０５）、更新が終了する（エンド）。
【００３２】
【発明が解決しようとする課題】
このように図２４に示した従来のアドレス検索装置１２０では、検索テーブル１２１の他にビット列を管理するビット列管理テーブル１２２を持ち、ビット列を検索テーブル１２１に対して登録あるいは削除、更新を行うたびに分割ビット列を所定のビット数まで拡張する必要があった。
【００３３】
またプレフィックス拡張検索方法では、以上説明したようにエントリ情報の書き込み規則が必要なため、検索テーブルに拡張前のビット列がどのような構成となっていたかを示す拡張前の情報を残すことができない。このため、ビット列の登録や削除を行う際に、拡張前のビット列の情報が必要になり、そのために検索テーブルを管理するためのテーブルが余計に必要になる。例えば、図２１において、ＩＰアドレスＰ２を削除するものとする。この場合、対応する２つのビット列“０１００”と“０１０１”を削除することになるが、この検索テーブルの２つのビット列“０１００”、“０１０１”の位置に何を書き込めばよいのか、書き残せばよいのかの情報は、このテーブル自体では判断できない。たとえばＡというビット構成とＢというビット構成が存在したとして、Ａの方がビット構成が長いのでこれが検索テーブルに登録されていたものとする。ところが、通信ネットワークの変更によってあるルータではＡの方が必要でなくなったものとする。このとき、Ａというビット構成とこれについての出力先振り分け情報を検索テーブルから削除することになる。ところが、この削除を行う際に、Ａというビット構成に対してどのビット構成が競合したかを示す情報が検索テーブルに登録されていない。したがって、Ａというビット構成を削除したときにどのビット列を代わりに登録するかを検索テーブル自体で判断することができない。
【００３４】
また、プレフィックス拡張検索方法を使用すると、登録したビット列に一致する数だけの出力先振り分け情報を検索テーブルに記録しておく必要がある。これらの出力先振り分け情報は、分割した分割ビット列を検索する各階層ごとに、保持しておく必要がある。このため、この方法を使用したアドレス検索装置は、保持するメモリサイズが大きくなるといった問題点があった。
【００３５】
そこで本発明の目的は、通信ネットワークのルーティングを行うための検索テーブルへのアドレスの追加や削除を容易にし、しかも検索テーブルを管理するためのメモリを小型化することのできるアドレス検索装置を提供することにある。
【００３６】
【課題を解決するための手段】
請求項１記載の発明では、（イ）通信ネットワークから次のルートに振り分けるべきデータ信号を入力し、そのデータ信号の最終的な宛先に至るルートを表わしたビット列からなるルート情報を予め定めたビット列ずつ先頭から区切ってそれぞれの階層の分割ビット列として順に取り出す分割ビット列取り出し手段と、（ロ）各ルート情報に対応したデータ信号の振り分け先を示す出力先振り分け情報を記憶した出力先振り分け情報記憶手段と、（ハ）分割ビット列取り出し手段によって取り出す可能性のある分割ビット列をそれぞれ対応する階層に配置したときに形成される木構造の各節に相当する位置にそれぞれ検索テーブルノードを配置し、これらの検索テーブルノードの各々に、対応する分割ビット列から次の検索テーブルノードを指示する次検索テーブルノード指示情報あるいは次の検索テーブルノードが存在しないときには出力先振り分け情報記憶手段におけるデータ信号の振り分け先を示す出力先振り分け情報が記載されている出力先振り分け情報記憶手段の該当箇所を指示する出力先振り分け情報格納箇所指示情報を記憶した検索テーブルと、（ニ）分割ビット列取り出し手段によって取り出した分割ビット列を用いて、第１の階層の検索テーブルノードから次検索テーブルノード指示情報が読み出される間、分割ビット列を順に取り出しながら検索テーブルノードを１階層ずつ階層を高めて検索を行い、出力先振り分け情報格納箇所指示情報が検索された時点でこの階層の移動を停止して検索する階層を確定する階層確定手段と、（ホ）この階層確定手段によって確定した検索テーブルノードから読み出された出力先振り分け情報格納箇所指示情報を用いて出力先振り分け情報記憶手段からデータ信号についての出力先振り分け情報を読み出す出力先振り分け情報読み出し手段とをアドレス検索装置に具備させる。
【００３７】
すなわち請求項１記載の発明では、ＩＰアドレス等のルーティングのためのルート情報を、分割ビット列取り出し手段が予め定めたビット列ずつ先頭から区切ってそれぞれの階層の分割ビット列として順に取り出すようにしている。そして、ルーティングの際のデータ信号の出力先の振り分けのための出力先振り分け情報を得ることができるまで先頭の分割ビット列から順に分割ビット列を使用するようにしている。本発明で使用する検索テーブルは、分割ビット列取り出し手段によって取り出す可能性のある分割ビット列をそれぞれ対応する階層に配置したときに形成される木構造の各節に相当する位置にそれぞれ検索テーブルノードを配置した構成となっている。ここで、これらの検索テーブルノードの各々には、対応する分割ビット列から次の検索テーブルノードを指示する次検索テーブルノード指示情報あるいは次の検索テーブルノードが存在しないときには出力先振り分け情報記憶手段におけるデータ信号の振り分け先を示す出力先振り分け情報が記載されている出力先振り分け情報記憶手段の該当箇所を指示する出力先振り分け情報格納箇所指示情報を記憶している。そして、分割ビット列取り出し手段によって取り出した分割ビット列を用いて、第１の階層の検索テーブルノードから次検索テーブルノード指示情報が読み出される間、分割ビット列を順に取り出しながら検索テーブルノードを１階層ずつ階層を高めて検索を行い、出力先振り分け情報格納箇所指示情報が検索された時点でこの階層の移動を停止して、検索する階層を確定するようにしている。確定した階層の該当する検索テーブルノードから読み出される出力先振り分け情報格納箇所指示情報を用いて出力先振り分け情報記憶手段からデータ信号についての出力先振り分け情報を読み出すことで、そのデータ信号を出力する先を決定することができる。
【００３８】
このように請求項１記載の発明では、アドレス検索装置に次々入力されるルート情報を、各分割ビット列をそれぞれ枝とする木構造に沿って対応付けていき、他のルート情報と共通の枝（階層）となっている状態では、１つずつ階層を上げて行って次の分割ビット列を追加的に使用するようにしている。このようにして分割ビット列を次々と使用して階層を上げていくと、遂にはそのアドレス検索装置が振り分け先を確定できるだけのルートに関する情報が得られる。このときの検索テーブルノードに示している出力先振り分け情報格納箇所指示情報を用いて出力先振り分け情報記憶手段からデータ信号についての出力先振り分け情報を読み出すようにすることで、出力先振り分け情報記憶手段という１つのまとまった記憶手段から、ルート情報に対応した出力先振り分け情報を読み出して、データ信号の出力先の振り分けに用いることができる。本発明では木構造の各節に対応する位置に検索テーブルノードを配置しているので、最大でも階層の数だけの検索テーブルノードの検索を行えば足り、ルート情報を分割して得られた分割ビット列の総数に相当する検索テーブルノードの検索は必要としないので、処理が迅速である。また、それぞれのルート情報に対応する出力先振り分け情報は、出力先振り分け情報記憶手段に一括して記憶しておくので、記憶領域の有効活用を行うことができるだけでなく、検索テーブルの変更や登録削除が容易になる。
【００３９】
請求項２記載の発明では、請求項１記載のアドレス検索装置で、検索テーブルノードのうちで次検索テーブルノード指示情報を格納しているもののみが、次検索テーブルノード指示情報を格納する領域を配置していることを特徴としている。
【００４０】
すなわち請求項２記載の発明では、木構造の枝のそれぞれ先端（最上層）の検索テーブルノードでは、次検索テーブルノード指示情報を格納する必要がないので、次検索テーブルノード指示情報を格納する領域をこれらについて省略することができ、この点でも記憶領域の有効活用を図ることができる。
【００４１】
請求項３記載の発明では、請求項１記載のアドレス検索装置で、各階層の検索テーブルノードは、そのテーブルノードに連結する次の階層の検索テーブルノードが存在するか否かを示す有効情報有無情報を配置していることを特徴としている。
【００４２】
すなわち請求項３記載の発明では、各階層の検索テーブルノードは、１つ上の階層の検索テーブルノードが存在するかどうかを判別させるための有効情報有無情報を配置しており、これによって木構造のそれぞれの枝が先端であるかどうかを簡単に判別することができる。
【００４３】
請求項４記載の発明では、請求項１記載のアドレス検索装置で、出力先振り分け情報格納箇所指示情報は、出力先振り分け情報記憶手段における出力先振り分け情報が記憶されている領域と、その領域における出力先振り分け情報の格納箇所を示す番地とで構成されていることを特徴としている。
【００４４】
すなわち請求項４記載の発明では、出力先振り分け情報記憶手段から該当するルート情報の出力先振り分け情報を読み出す際に出力先振り分け情報記憶手段における出力先振り分け情報が記憶されている領域と、その領域における出力先振り分け情報の格納箇所を示す番地を用いてこの読み出しを行うようになっている。これは、あるルート情報に基づく分割ビット列を順次使用することで検索テーブルノードを上位の階層に向けて順次辿っていき、データ信号を振り分けるのに必要な情報が得られた時点の最終の検索テーブルノードが、出力先振り分け情報記憶手段における出力先振り分け情報が記憶されている複数の領域の１つを指示する場合には、この領域内におけるそのルート情報に対応した番地も最終の検索テーブルノードから読み出していくことで、目的とする出力先振り分け情報の格納箇所を特定することができるからである。
【００４５】
請求項５記載の発明では、請求項４記載のアドレス検索装置で、出力先振り分け情報記憶手段における出力先振り分け情報が記憶されている領域は、対応する分割ビット列を構成するビット数の二乗の数の番地を備えていることを特徴としている。
【００４６】
すなわち請求項５記載の発明では、出力先振り分け情報が記憶されている領域のそれぞれは対応する分割ビット列を構成するビット数の二乗の数の番地を備え、それぞれに出力先振り分け情報を登録できるようになっている。したがって、分割ビット列を構成するビット数を多くすると、それだけ該当領域が大きくなることになる。
【００４７】
請求項６記載の発明では、請求項１記載のアドレス検索装置で、分割ビット列取り出し手段が順に取り出す分割ビット列は、それぞれ互いに等しいビット数で構成されていることを特徴としている。
【００４８】
すなわち請求項６記載の発明では、分割ビット列取り出し手段が順に取り出す分割ビット列は、それぞれ互いに等しいビット数で構成されることが一例であることを示している。たとえばルート情報を３ビット単位で区切ってそれぞれを分割ビット列とすることができ、これにより分割処理を単純化すると共に前記した出力先振り分け情報が記憶されている領域のサイズの均一化を図ることができる。もちろん、分割ビット列は階層に応じて構成ビット数を変えるようにすることも自由である。
【００４９】
【発明の実施の形態】
【００５０】
【実施例】
以下実施例につき本発明を詳細に説明する。
【００５１】
図１は本発明の一実施例のアドレス検索装置で使用する検索テーブルの要部を表わしたものである。本実施例の階層別の検索テーブル３００には、ビット列を拡張せずに拡張前のビット列を記録するフィールドとしての出力先振り分け情報テーブル３０１と、次の階層のノードへのポインタ３０２が配置されている。この図１では図２３と同様に分割ビット列が３ビットの場合を示している。図１でＶＢＩＴフィールド３０３は、出力先振り分け情報を表わした出力先振り分け情報テーブル３０１のエントリが有効か否かを示すビット情報である。また、出力先振り分け情報テーブル３０１内の出力先振り分け情報ＮＨＰ１〜ＮＨＰ１４は「次に転送するルータのＩＰアドレスまたは転送先のポート番号」、すなわちそのルータの出力の振り分け先（出力ポート）を示す情報を表わしている。
【００５２】
本実施例の場合には、この図１にも示されているように検索テーブル３００におけるビット列を拡張していない。その代わりに、拡張していないこのようなビット列に対応する出力先振り分け情報が検索テーブル３００のどの位置に存在するかを示す情報を表わしたＶＢＩＴフィールド３０３を持っている。ＶＢＩＴフィールド３０３の詳細については後に説明する。
【００５３】
図２は、図２５に対応するもので本実施例のアドレス検索装置の検索テーブルでのビット更新の処理の様子を表わしたものである。この処理では、まず更新するビット列に対応するＶＢＩＴフィールド３０３（図１）のビットを更新する（ステップＳ４０１）。次に、更新がルートの新設等に基づいた出力先振り分け情報（ＮＨＰ情報）の登録の場合には、登録する拡張していないビット列に対応する出力先振り分け情報を、検索テーブル３００（図１）に書き込んで（ステップＳ４０２）、ビット更新処理を終了させる（エンド）。
【００５４】
本実施例では、図２に示したように、更新する分割ビット列に対応するＶＢＩＴフィールド３０３の１ビットを更新し、検索テーブル３００に出力先振り分け情報を書き込むだけでよい。また、同じくルートの変更等によって所定のビット列に対応する出力先振り分け情報を削除するときはＶＢＩＴフィールド３０３のそれに対応する１ビットをビット“０”に設定すればよい。ただし、この前提としてビット“０”を未登録を表わす状態のものとし、ビット“１”を登録を表わす状態のものとする。
【００５５】
図３は、分割ビット列のビット数が“３”の場合のＶＢＩＴフィールドを表わしたものである。ＶＢＩＴフィールド３０３のビット列が１ビットから３ビットまでの各ビットの組み合わせで構成されているものとする。本実施例では各ビット列を拡張する処理を行わないので、ビット列が１ビット構成の場合はビット“０”とビット“１”の２種類である。また、２ビット構成の場合には、“００”、“０１”、“１０”、“１１”の４種類である。３ビット構成の場合には“０００”、“００１”、“０１０”、“０１１”、“１００”、“１０１”、“１１０”、“１１１”の８種類である。したがって、これらの合計の１４種類のビットの組み合わせが存在することになり、それぞれのビット列に１ビットを割り振るものとすると、ＶＢＩＴフィールド３０３全体で１４ビットが必要になる。
【００５６】
たとえば、このうちのビット列“００”に対応する位置に出力先振り分け情報を登録したいときには、ＶＢＩＴフィールド３０３の“００”のビット（図３で左から３番目のビット）を“１”にして、対応する検索テーブルの“００”のエントリに出力先振り分け情報を書き込む。また、削除したいときは、ＶＢＩＴの削除した分割ビット列に対応するＶＢＩＴフィールド３０３のビットを“０”にする。このような処理だけで階層別の検索テーブル３００への登録や変更、削除が終了する。
【００５７】
図４は、本実施例におけるアドレス検索装置の構成を示したもので、従来の図２４に対応するものである。このアドレス検索装置３１０は、分割ビット列のすべての階層の検索テーブルを保持した検索テーブル３１１と、分割ビット列の各階層の検索処理を行う分割ビット列検索ブロック３１２と、分割ビット列検索ブロック３１２で得られた最終的な検索結果情報３１３を基にして出力先振り分け情報を取得する出力先振り分け情報取得ブロック３１４と、出力先振り分け情報取得ブロック３１４が参照する出力先振り分け情報テーブル３１５とで構成されている。アドレス検索装置３１０の分割ビット列検索ブロック３１２にはＩＰアドレス３１６が供給され、出力先振り分け情報取得ブロック３１４は出力先振り分け情報テーブル３１５を検索して出力先振り分け情報３１７を出力するようになっている。ここで、分割ビット列検索ブロック３１２から出力される検索結果情報３１３は、ビット列ＥＢＩＴ、ポインタＮＮ−ＰＴＲ、ＳＴＡＧＥ、および入力ＩＰアドレスから構成されている。これらについては後に説明する。
【００５８】
すなわち、図４に示す本実施例のアドレス検索装置３１０は、図２４に示した従来のアドレス検索装置１２０と対比すると、検索テーブル１２１（図２４）を検索テーブル３１１と出力先振り分け情報テーブル３１５に分け、分割ビット列を検索する各階層では検索テーブル３１１をアクセスし、全階層の検索が終了したあとに出力先振り分け情報テーブル３１５をアクセスするといった手法を採っている。これによって、従来の検索テーブル１２１で必要だった出力先振り分け情報テーブル３１５に対応するサイズを大幅に削除することができる。
【００５９】
図５は図４に示した検索テーブルの１つのノードを示したものである。すなわち図４に示した検索テーブル３１１は、図５で示される検索テーブルノード３２１で構成されている。検索テーブルノード３２１は、分割ビット列をポインタを利用した木構造で管理するためのテーブル構成となっている。検索テーブルノード３２１は、次の階層の検索テーブルへのポインタＬＰＴＲが有効（Ｅｎａｂｌｅ）か否かを識別するビット列ＥＢＩＴ（有効情報有無情報）と、出力先振り分け情報テーブル３１５ノードへのポインタＮＮ−ＰＴＲと、このノードにビット列が登録されている場合にどのようなビット列が登録されているかを示すビットＶＢＩＴと、それぞれ次の階層の検索テーブルのノードへのポインタＬＰＴＲ１〜ＬＰＴＲＭの各フィールドで構成されている。ここで、値Ｍは分割したビット列のビット数により異なり、例えば、３ビットで分割した前記した例の場合は、これらのビットの組み合わせの数として値Ｍは“８”となる。
【００６０】
図６は、検索テーブルノードの構成例を示したものである。この図で検索テーブルノード３２１のビット列ＥＢＩＴ３２２は、分割ビット列のビット長が３ビットの場合を具体的に表わしたものであり、各ビットＬ１〜Ｌ８はポインタＬＰＴＲ１〜ＬＰＴＲ８が有効であるか否かを示している。検索テーブルノード３２１のＶＢＩＴフィールド３０３は、具体的にはビット“０”、“１”、“００”、…、“１１１”として記述してある。このビット“０”、“１”、“００”、…、“１１１”は、この検索テーブルノード３２１に分割ビット列“０”、“１”、“００”、“０１”、…、“１１０”、“１１１”が登録されているか否かを識別するためのものである。たとえば、分割ビット列“１１”（ビット長が“２”）が登録されているときは、ＶＢＩＴフィールド３０３におけるビット“１１”のビットが“１”になり、ポインタＮＮ−ＰＴＲで示される出力先振り分け情報テーブル３１５のノードには、ビット列“１１”に対応する出力先振り分け情報が格納されるようになっている。
【００６１】
一方、図７は、図４に示した出力先振り分け情報テーブルの１つのノードを示したものである。出力先振り分け情報テーブルノード３２５には、分割ビット列の出力先振り分け情報が登録される。分割ビット列が３ビット構成の場合には、“０”、“１”、“００”、“０１”、“１０”、“１１”、“０００”、…、“１１０”、“１１１”の１４種類のビット列の出力先振り分け情報（ＮＨＰ１、ＮＨＰ２……ＮＨＰ１４）が最大で登録されることになる。
【００６２】
図４に戻って説明を続ける。出力先振り分け情報テーブル３１５は、図７で示される出力先振り分け情報テーブルノード３２５の複数個から構成されていて、検索テーブル３１１の中にあるポインタＮＮ−ＰＴＲにより参照される。出力先振り分け情報テーブルノード３２５（図７）は、分割ビット列に対応するＮ個の出力先振り分け情報ＮＨＰ１〜ＮＨＰＮで構成され、ビット拡張前のビット列すべてに対応する出力先振り分け情報を持つ。例えば、３ビットで分割したときは、ビット列“０”、“１”、“００”、“０１”、“１０”、“１１”、“０００”、…、“１１０”、“１１１”の１４種類が考えられるので、パラメータＮは“１４”になる。図７の出力先振り分け情報ＮＨＰＮに対応するビット列が“ｘｘｘｘｘ”として表わされているが、これは分割したビット列のビット長により異なる。３ビットで分割したときはビット列“１１１”となり、４ビットで分割したときはビット列“１１１１”となる。
【００６３】
分割ビット列検索ブロック３１２は、これに入力されるＩＰアドレス（以下入力ＩＰアドレスという）３１６を、あらかじめ決められたビット長ごとに分割し、分割したビット列を用いてビット列ＥＢＩＴとポインタＮＮ−ＰＴＲの値を検索する処理を行うものである。
【００６４】
出力先振り分け情報取得ブロック３１４は、分割ビット列検索ブロック３１２の処理で検索した、ビット列ＥＢＩＴとポインタＮＮ−ＰＴＲの値を最終的な検索結果情報３１３として受け取り、対応する出力先振り分け情報を出力する処理を行う。出力先振り分け情報テーブル３１５からポインタＮＮ−ＰＴＲをアドレスとするノードを計算し、ビット列ＥＢＩＴから最長一致する出力先振り分け情報３１７を、アドレス検索装置３１０から出力するようになっている。
【００６５】
図４に示した本実施例のアドレス検索装置３１０ではＩＰアドレスのビット長、分割数、分割ビット列を検索する階層数に制限は無いが、説明を簡単にするためにＩＰアドレスのビット長を“９”、分割数を“３”ならびに分割ビット列の長さを“３”とした場合を次に具体的に説明する。この場合、図５に示した検索テーブルノード３２１のポインタＬＰＴＲの数は、値Ｍが“８”となり、ポインタＬＰＴＲ１からポインタＬＰＴＲ８までの８個となる。
【００６６】
このようにポインタＬＰＴＲが８個のため、ポインタＬＰＴＲ１〜ポインタＬＰＴＲ８までのテーブルの有効あるいは無効を示すために必要なビット数としてのビット列ＥＢＩＴは“８”となる。ビット長が“３”であるときに考えられるすべてのビット列は“０”、“１”、“００”、“０１”、“１０”、“１１”、“０００”、…、“１１０”、“１１１”の１４種類あるので、ＶＢＩＴは１４ビットになる。
【００６７】
次に、最長一致するプレフィックスを求めたい９ビットからなるＩＰアドレスが、図４に示したアドレス検索装置３１０の分割ビット列検索ブロック３１２に入力した後の動作を説明する。
【００６８】
図８は、検索したいＩＰアドレスを基にして、図４の出力先振り分け情報取得ブロックへ渡す検索結果情報を求める処理の流れを表わしたものである。具体的には、検索結果情報３１３（図４参照）として出力先振り分け情報取得ブロック３１４に渡されるＶＢＩＴフィールド、ポインタＮＮ−ＰＴＲ、ＳＴＡＧＥを保持しているパラメータとしてのＲＥＧ＿ＶＢＩＴ、ＲＥＧ＿ＮＮ−ＰＴＲ、ＲＥＧ＿ＳＴＡＧＥを求める処理である。本実施例では階層数を“３”としたので、変数Ｎは“１”から“３”まで採りうる。
【００６９】
入力ＩＰアドレス３１６が図４の分割ビット列検索ブロック３１２に入力されたものとする。分割ビット列検索ブロック３１２では、まず検索のための初期化処理を行う（図８ステップＳ４２１）。この初期化処理では、まず、処理を行う階層を表わすパラメータｎを“１”にする。また、検索テーブル３１１（図４）の次の階層への検索テーブルノードのポインタをポインタＮＸＴＬＰＴＲとし、「初期値」は検索テーブルの第１階層のノードへのポインタアドレスとする。第１階層は最初のビット列の検索なのでノードは１つしかない。
【００７０】
ポインタＲＥＧ＿ＶＢＩＴとポインタＲＥＧ＿ＮＮ−ＰＴＲは、それぞれ最長一致した分割ビット列の検索テーブルノードのＶＢＩＴフィールドと、出力先振り分け情報テーブルへのノード（以下出力先振り分け情報テーブルノードと呼ぶ。）へのポインタ情報を表わしている。パラメータＲＥＧ＿ＳＴＡＧＥはポインタＲＥＧ＿ＶＢＩＴとポインタＲＥＧ＿ＮＮ−ＰＴＲを更新したときの階層を保持する変数である。図８に示す処理では、ポインタＲＥＧ＿ＶＢＩＴとポインタＲＥＧ＿ＮＮ−ＰＴＲを更新したときに、パラメータＮが示す階層の値が代入される。パラメータＲＥＧ＿ＳＴＡＧＥの初期値は、一致している検索テーブルノードを見つける前なので、無効とする。例えばプログラム言語等で実現するときは、負の値を入れるか、別の変数を用いて、ポインタＲＥＧ＿ＶＢＩＴとポインタＲＥＧ＿ＮＮ−ＰＴＲ、およびパラメータＲＥＧ＿ＳＴＡＧＥが無効であることを表わすことができる。
【００７１】
終了フラグは、全階層の検索を終えたか、途中の階層でも次に検索すべき検索テーブルノードが無いときに終了フラグが“ｏｎ（オン）”（有効）になる。初期値は“ｏｆｆ（オフ）”である。
【００７２】
初期化が終了すると、次に階層ｎの検索を行う（ステップＳ４２２）。初期化のすぐ後に、変数ｎは“１”になっている。このため、第１階層の検索テーブル３１１の処理を行う。
【００７３】
図９は、ステップＳ４２２での検索テーブルの検索処理の流れを表わしたものである。まず、符号ＮＸＴＬＰＴＲをアドレスとして１個の検索テーブルノードをリードする（Ｓ４４１）。次に、リードしたノードのＶＢＩＴフィールドに“１”になるビットがあるか調べる（Ｓ４４２）。１つでも“１”になるビットが存在した場合には、この検索テーブルノードに入力ＩＰアドレス３１６の分割ビット列が登録されている。そこでこの場合には、Ｓ４４３の手順を行う。ＶＢＩＴフィールドの中に１つも“１”になっているビットが無いときには（Ｎ）、Ｓ４４３の処理を行わずに、ステップＳ４４４の処理を行う。
【００７４】
ところでＶＢＩＴフィールドの中で１つでも“１”になっているビットがある場合には（ステップＳ４４２：Ｙ）、この検索テーブルノードに分割ビット列が登録されている。そこでポインタＲＥＧ＿ＶＢＩＴとポインタＲＥＧ＿ＮＮ−ＰＴＲを、リードした検索テーブルノードのＶＢＩＴフィールドとポインタＮＮ−ＰＴＲに更新し、パラメータＲＥＧ＿ＳＴＡＧＥをパラメータｎで書き込む。登録されている分割ビット列に対応する出力先振り分け情報テーブルノードは、検索テーブル３１１の中にはなく、出力先振り分け情報テーブル３１５の中に存在する。出力先振り分け情報テーブルノードへのポインタとしてポインタＮＮ−ＰＴＲが検索テーブルノードにある。したがって、分割ビット列検索ブロック３１２の処理が終了後、ポインタＲＥＧ＿ＮＮ−ＰＴＲを利用し、出力先振り分け情報取得ブロック３１４で出力先振り分け情報３１７を取得する。
【００７５】
次に、検索している階層が最後の階層であるかどうかを判別する（ステップＳ４４４）。本実施例では階層数を“３”にしたので、検索している階層が“３”のときは次の階層が存在しない（Ｙ）。そこでこの場合には、終了フラグを“ｏｎ”するためにＳ４４５の手順を行う。
【００７６】
検索している階層が最後の階層ではない場合（ステップＳ４４４：Ｎ）、リードした検索テーブルノードの次の階層の検索テーブルノードの有無をビット列ＥＢＩＴのビットで調べる。そして、現在の階層で検索している入力ＩＰアドレスの分割ビット列、つまり、この例では３ビットから構成されるビット列で、その３ビットで表わされる“１”〜“８”の数値に対応するポインタＬＰＴＲ１〜ＬＰＴＲ８が有効であるか否かを、ビット列ＥＢＩＴのビットＬ１〜Ｌ８（図６参照）から判別する（Ｓ４４６）。有効（“１”）であればステップＳ４４７に進み、無効（“０”）であればＳ４４５の処理を行う。例えば、現在の階層で検索している入力ＩＰアドレス３１６の分割ビット列が“０１０”であるとする。この場合、ビット列ＥＢＩＴのＬ２ビットが“１”になっていて有効であることを示していれば、次の階層の検索テーブルのノードが存在するので、ステップＳ４４７の処理を行い、検索テーブルノードからポインタＬＰＴＲ２をリードし、次のステップＳ４４８でアドレスＮＸＴＬＰＴＲをポインタＬＰＴＲ２で書き換える。
【００７７】
ビット列検索ブロックの処理が終了した後に、図４に示した出力先振り分け情報取得ブロック３１４で、検索したポインタＲＥＧ＿ＶＢＩＴとポインタＲＥＧ＿ＮＮ−ＰＴＲ、パラメータＲＥＧ＿ＳＴＡＧＥと入力ＩＰアドレス３１６から出力先振り分け情報３１７を取得する。
【００７８】
図９に示した所定の階層についての検索処理が行われたら（図８ステップＳ４２２）、すべての階層の検索処理が終了したかどうかの判別が行われる（ステップＳ４２３）。そして、まだ検索が終了していない場合には（Ｎ）、次の階層の検索を行うためにパラメータ“ｎ”を“１”だけ加算する（ステップＳ４２４）。そして、ステップＳ４２２に戻って、その加算後のパラメータ“ｎ”で示される階層についての検索を行うことになる。
【００７９】
このようにしてすべての階層についての検索が終了したら（ステップＳ４２３：Ｙ）、入力ＩＰアドレス３１６の分割ビット列検索処理が終了することになる（エンド）。
【００８０】
図１０は、この出力先振り分け情報を取得する処理の流れを表わしたものである。まず、ポインタＲＥＧ＿ＶＢＩＴおよびポインタＲＥＧ＿ＮＮ−ＰＴＲが更新されたかどうかがチェックされる（ステップＳ４７１）。前段の分割ビット列検索ブロック３１２でポインタＲＥＧ＿ＶＢＩＴおよびポインタＲＥＧ＿ＮＮ−ＰＴＲが更新されなかったとき（Ｎ）、すなわち図９におけるステップＳ４４３で分割ビット列検索処理中に更新が一度も行われなかったとき、入力ＩＰアドレス３１６に一致するビット列が登録されていないことになる。そこで、この場合には、エラーあるいはビット列一致無しの結果を出力する（ステップＳ４７２）。
【００８１】
ポインタＲＥＧ＿ＶＢＩＴおよびポインタＲＥＧ＿ＮＮ−ＰＴＲが更新された場合には（ステップＳ４７１：Ｙ）、更新したポインタＲＥＧ＿ＶＢＩＴには、分割ビット列検索ブロックの処理で最後に分割ビット列が一致した検索テーブルノードのＶＢＩＴフィールドが格納されている。このＶＢＩＴフィールドは図６のＶＢＩＴフィールド３０３のように表わされる。入力ＩＰアドレス３１６のビット列から階層ＲＥＧ＿ＳＴＡＧＥに相当するビット列を取り出し、取り出したビット列とＶＢＩＴで表わされるビット列を比較し、より長いビット列を選択する（図１０ステップＳ４７３）。
【００８２】
そして、選択したビット列に対応する出力先振り分け情報３１７を、ポインタＲＥＧ＿ＮＮ−ＰＴＲと選択したビット列の位置から計算する。ポインタＲＥＧ＿ＮＮ−ＰＴＲは図７の出力先振り分け情報テーブルノード３２５の先頭を表わし、選択したビット列により出力先振り分け情報ＮＨＰ１〜ＮＨＰ１４のいずれかを選択する（図１３のステップＳ４７４）。例えば、ビット列“０１０”を選択した場合は、図６よりビット列“０１０”は９番目に位置するので、出力先振り分け情報ＮＨＰ９を出力先振り分け情報３１７として取り出すことになる。
【００８３】
次にＩＰアドレスのビット長を“９”、分割数を“３”ならびに分割ビット列の長さを“３”とした場合について、本実施例のアドレス検索装置３１０の動作を具体的に説明する。
【００８４】
図１１は、検索テーブルに登録されているＩＰアドレスを示したものである。図４に示した検索テーブル３１１には、ＩＰアドレスＰ１〜Ｐ５が登録されているものとする。ＩＰアドレスＰ１はビット長が“２”で、ＩＰアドレスＰ２のビット長は“５”である。ＩＰアドレスＰ１〜Ｐ５に対応する出力先振り分け情報３１７を、出力先振り分け情報ＮＨＰ（Ｐ１）、ＮＨＰ（Ｐ２）、…、ＮＨＰ（Ｐ５）とする。これら５つのＩＰアドレスＰ１〜Ｐ５を、検索テーブル３１１および出力先振り分け情報テーブル３１５に登録する。
【００８５】
図１２は、ＩＰアドレスＰ１〜Ｐ５を登録した場合の第１階層から第３階層までのＩＰ検索テーブルを表わしたものであり、図１３は同じくＩＰアドレスＰ１〜Ｐ５を登録した場合の出力先振り分け情報テーブルを表わしたものである。図１２に示す第１階層〜第３階層のＩＰ検索テーブル３４１〜３４３のうち第３階層のＩＰ検索テーブル３４３は分割したビット列の一番最後の階層のテーブルである。したがって、次の階層の検索テーブルノードへのポインタは不要である。このため、第１階層と第２階層のＩＰ検索テーブル３４１、３４２で必要な検索テーブルノードにあるビット列ＥＢＩＴと出力先振り分け情報ＮＨＰ１〜ＮＨＰ８は、第３階層のＩＰ検索テーブル３４３では不要のため、図示していない。
【００８６】
ＩＰアドレスＰ１のビット列“０１”はビット長が“２”であるので、第１階層のＩＰ検索テーブル３４１に登録される。図１２の検索テーブルノード３５１のＶＢＩＴフィールドの“０１”に相当するビット（左から４番目のビット）が“１”になる。この検索テーブルノード３５１に対応する出力先振り分け情報テーブルノードはポインタＮＮ−ＰＴＲによって示されている。本例ではアドレス“５０５０（ｈ）”を用い、図１３の出力先振り分け情報テーブルノード３６１になる。また、出力先振り分け情報はビット列“０１”のテーブル３６２（図１３）に登録されている出力先振り分け情報ＮＨＰ（Ｐ１）になる。
【００８７】
ＩＰアドレスＰ２のビット列“００１１０”はビット長が“５”であるので、第２階層のＩＰ検索テーブル３４２に登録される。第１階層のＩＰ検索テーブル３４１には、第２階層の検索テーブルノードへのポインタを記録しておく必要がある。そこで、第１階層の検索テーブルノード３５１のビット列“００１”に対応するテーブルに、第２階層の検索テーブルノードへのポインタとして“２０００（ｈ）”を記録し、かつ、ビット列“００１”に対応するビット列ＥＢＩＴのビットを“１”にする。このポインタが示す検索テーブルノード３５２は図１２のようになる。
【００８８】
ＩＰアドレスＰ２の第２階層のビット列は、ＩＰアドレスＰ２ビット列“００１１０”のうちの最初から３ビットまでのビット列“００１”を除いた２ビットのビット列“１０”となる。そこで、ＶＢＩＴフィールドの“１０”に相当するビット（左から５番目のビット）が“１”になる。このノードに対応する出力先振り分け情報テーブルノードはポインタＮＮ−ＰＴＲによって示されている。本例では“５２５０（ｈ）”を用い、図１３の出力先振り分け情報テーブルノード３７１になる。出力先振り分け情報はビット列“１０”のテーブル３７２（図１３）に登録されている出力先振り分け情報ＮＨＰ（Ｐ２）になる。
【００８９】
ＩＰアドレスＰ３のビット列“００１１０１”はビット長が“６”であるので、同様に第２階層のＩＰ検索テーブルに登録される。第１階層のＩＰ検索テーブルには、第２階層の検索テーブルノードへのポインタを記録しておく必要があるが、ＩＰアドレスＰ２と同じ分割ビット列を第１階層に持つ。したがって、第１階層テーブル３５１のビット列“００１”に対応するテーブルと、第２階層の検索テーブルノード３５２はＩＰアドレスＰ２と共有される。ＩＰアドレスＰ３の第２階層のビット列は“１０１”となるので、ＶＢＩＴフィールドの“１０１”（左から１２番目のビット）が“１”になる（図１２の検索テーブルノード３５２）。出力先振り分け情報テーブルノードは、ＩＰアドレスＰ２と同じ場所に持つ。出力先振り分け情報はビット列“１０１”のテーブル３７３（図１３）に登録されている出力先振り分け情報ＮＨＰ（Ｐ３）になる。
【００９０】
ＩＰアドレスＰ４とＩＰアドレスＰ５はそれぞれビット長が“８”であるので、第３階層のＩＰ検索テーブル３４３（図１２）に登録される。第１階層のＩＰ検索テーブル３４１には、第２階層の検索テーブルノードへのポインタを記録しておく必要がある。そこで、第１階層の検索テーブルノード３５１のビット列“１０１”に対応するテーブルに、第２階層のＩＰ検索テーブル３４２のへのポインタとして“２０２０（ｈ）”を記録し、かつ、ビット列“１０１”に対応するビット列ＥＢＩＴのビットを“１”にする。このポインタが示す検索テーブルノード３５３は図１２のようになる。
【００９１】
同様に、第２階層のＩＰ検索テーブル３４２に、第３階層のＩＰ検索テーブル３４３へのポインタを記録しておく必要がある。そこで、第２階層のビット列“１００”に対応するポインタに“３０３０（ｈ）”を記録し、かつ、ビット列“１００”に対応するビット列ＥＢＩＴのビットを“１”にする。第１階層のビット列が“１０１”で、かつ、ビット長が“４”から“６”のＩＰアドレスは本例では登録していない（図１１参照）。そこでＶＢＩＴフィールドのビットはすべて“０”になり、ポインタＮＮ−ＰＴＲはどの出力先振り分け情報テーブルノードも示さない。ＩＰアドレスＰ４とＩＰアドレスＰ５に対応する第３階層の検索テーブルノード３５４は図１２のようになる。本実施例の説明では、階層数を“３”としたので、第３階層までしか存在しない。そのため次の階層の検索テーブルノードへのポインタが不要であるので、第３階層の検索テーブルノード３５４ではビット列ＥＢＩＴ、ポインタＬＰＴＲ１〜ＬＰＴＲ８までのテーブルを削除することができる。
【００９２】
このように図１１に示した５つのＩＰアドレスが検索テーブル３１１の第１〜第３の階層のＩＰ検索テーブル３４１〜３４３（図１２）に登録されているときに、図４に示す検索対象としての入力ＩＰアドレス３１６が入力されたものとする。このときの動作を次に説明する。
【００９３】
まず、入力ＩＰアドレス３１６がビット列“００１１０１１１１”であるときのアドレス検索装置３１０の動作を説明する。ＩＰアドレス３１６が図４の分割ビット列検索ブロック３１２に入力されると、まず最初に図８で説明したステップＳ４２１の処理で変数の初期設定が行われる。次に、アドレスＮＸＴＬＰＴＲが示す検索テーブルノードをリードする。ここで、第１検索テーブルノードをアドレス“１０００（ｈ）”としたときは、アドレスＮＸＴＬＰＴＲの初期値は“１０００（ｈ）”である。そこで、“１０００（ｈ）”とする図１２の検索テーブルノード３５１をリードする（図９ステップＳ４４１）。
【００９４】
次に、入力ＩＰアドレスの第１階層の長さが１、２、３のすべてのビット長のビット列“０”、“００”、“００１”に、ＶＢＩＴフィールドが一致するかを調べる。ＶＢＩＴフィールドのビットは“０”、“１”、“００”、“０１”、…、“１１１”に対応するビット列が存在するときに“１”になる。検索テーブルノード３５１には“０”、“００”、“００１”に対応するビットが“１”になっているものがないので（ステップＳ４４２：Ｎ）、ステップＳ４４３をスキップしてステップＳ４４４に進む。
【００９５】
現在、入力ＩＰアドレス３１６の第１階層の分割ビット列の検索処理をしているので、最後の階層の検索処理ではない（パラメータｎは“３”未満）（ステップＳ４４４：Ｎ）。そこでステップＳ４４６に進む。ステップＳ４４６では、分割ビット列“００１”に対応するビット列ＥＢＩＴのビットを調べると“１”になっている。したがって、次の階層の検索テーブルノードへのポインタが存在する（ステップＳ４４６：Ｙ）。そこでステップＳ４４７へ進む。ステップＳ４４７では、検索テーブルノードから、分割ビット列“００１”に対応するポインタＬＰＴＲをリードする。この値は２０００（ｈ）であるので、アドレスＮＸＴＬＰＴＲを２０００（ｈ）に更新する（ステップＳ４４８）。以上の手順で第１階層の検索は終了になり、終了フラグが“ｏｆｆ”のままであるので検索は終了しておらず（図８ステップＳ４２３：Ｎ）、ステップＳ４２４に進み、パラメータｎに“１”を加算する。そして、パラメータを“２”に設定した状態でステップＳ４２２で再度処理を行うことになる。
【００９６】
更新されたアドレスＮＸＴＬＰＴＲは“２０００（ｈ）”である。そこで、図１２の検索テーブルノード３５２をリードする（図９ステップＳ４４１）。入力ＩＰアドレス３１６の第２階層の分割ビット列のすべての長さのビット列“１”、“１０”、“１０１”に一致するＶＢＩＴフィールドが示すビットが“１”になっているビットが存在する（ステップＳ４４２）。そこで、リードしたポインタＮＮ−ＰＴＲとＶＢＩＴフィールドをそれぞれポインタＲＥＧ＿ＮＮ−ＰＴＲとポインタＲＥＧ＿ＶＢＩＴで書き込み、パラメータＲＥＧ＿ＳＴＡＧＥにパラメータ“Ｎ”を書き込む（ステップＳ４４３）。パラメータ“ｎ”は“２”であるのでステップＳ４４４では最後の階層とはされない（Ｎ）。そこで、ステップＳ４４６に進む。ステップＳ４４６で、入力ＩＰアドレス３１６の第２階層の分割ビット列“１０１”に対応するビット列ＥＢＩＴのビットは“０”になっている。したがって、次の階層の検索ノードを示すポインタＬＰＴＲは１つも無い（Ｎ）。そこでステップＳ４４５に進み、終了フラグを“ｏｎ”にする。図８のステップＳ４２３で、終了フラグの比較が行われ、“ｏｎ”になっているので（Ｙ）、入力ＩＰアドレス３１６の分割ビット列検索処理は終了する（エンド）。
【００９７】
このようにして分割ビット列検索処理が終了すると、図４に示されている分割ビット列検索ブロック３１２は、ポインタＲＥＧ＿ＶＢＩＴとポインタＲＥＧ＿ＮＮ−ＰＴＲ、パラメータＲＥＧ＿ＳＴＡＧＥおよび入力ＩＰアドレス３１６を、検索結果情報３１３として出力先振り分け情報取得ブロック３１４に渡す。
【００９８】
出力先振り分け情報取得ブロック３１４の処理を先に示した図１０を用いて説明する。まず、ポインタＲＥＧ＿ＶＢＩＴおよびポインタＲＥＧ＿ＮＮ−ＰＴＲについて見てみる。図９のステップＳ４４３で、ポインタＲＥＧ＿ＶＢＩＴは“００００１００００００１００”で、ポインタＲＥＧ＿ＮＮ−ＰＴＲは“５２５０（ｈ）”と更新されており、有効となっている（図１０ステップＳ４７１）。したがって、次のステップＳ４７３に処理が進む。ステップＳ４７３では、パラメータＲＥＧ＿ＳＴＡＧＥは“２”である。そこで、第２階層の入力ＩＰアドレスビット列“１０１”から、これに一致するポインタＲＥＧ＿ＶＢＩＴのＶＢＩＴフィールドが示すビット列を調べる。これにより、ビット列“１０”とビット列“１０１”が存在することが分かる。最も長く一致するビット列を選択するので、ビット列“１０１”を選択する（ステップＳ４７３）。ポインタＲＥＧ＿ＮＮ−ＰＴＲは“５２５０（ｈ）”であるので図１３の出力先振り分け情報テーブルノード３７１を指している。ポインタＲＥＧ＿ＶＢＩＴ列と入力ＩＰアドレスの比較により、一致する分割ビット列は“１０１”となる。したがって、ステップＳ４７４では、“５２５０（ｈ）”で指される出力先振り分け情報テーブルノード３７３（図１３）のビット列“１０１”の出力先振り分け情報をリードする。この場合、出力先振り分け情報は出力先振り分け情報ＮＨＰ（Ｐ３）となる。
【００９９】
図１４は、図１２および図１３の検索テーブルおよび出力先振り分け情報テーブルに、ビット列“１０１０１”を登録するときの処理を説明するためのものである。テーブルを更新する場合はＶＢＩＴフィールドの該当するビットの状態を反転させて、削除（“０”にする。）あるいは登録（“１”にする。）の操作を行うことができる。図１２の第２階層の検索テーブルノード３５２には、ビット列“１０”（図１２で左から５番目のビットが“１”。）とビット列“１０１”（同図で右から３番目のビットが“１”。）が登録されている。この検索テーブルノード３５２に新たにビット列“０１”を登録するものとする。このときは、まず図１４の第２階層の検索テーブルノード３６４における、ビット列“０１”に対応するＶＢＩＴフィールド３０３のビットの位置３６５（左から４番目のビット）を“１”にする。次に、出力先振り分け情報テーブル３１５の検索テーブルノード３６６（図１４）のビット列“０１”に出力先振り分け情報ＮＨＰ＊を書き込む。図１４では、図１２および図１３で表わされるＩＰ検索テーブルに、ビット列“０１”とそれに対応する出力先振り分け情報ＮＨＰ＊を登録した後の状態を示している。
【０１００】
以上説明したように、従来の検索テーブル更新処理では、展開したビット列を検索テーブルに書き込むようにしているので、この検索テーブルには展開前のビット列の情報は残らない。このため、図２４のビット列管理テーブル１２２の展開前のビット列を含んだ検索テーブル１２１を保持しておかなければいけない。この従来のアドレス検索装置１２０では、検索テーブル１２１の更新を行う場合には図２５に示した処理を実施しなければならず、更新手順が複雑化し、更新のための検索テーブルを多く実装しておかなければいけない。
【０１０１】
これに対して図４に示した本実施例のアドレス検索装置３１０では、図２の処理で示すように、展開前のビット列に対応するＶＢＩＴフィールド３０３および出力先振り分け情報を書き換えればよく、更新処理の手順が少なくなり、かつ、検索テーブル３１１以外のテーブルを別途持つ必要がなくなる。この結果、余計なメモリは必要なくなる。
【０１０２】
従来では、特開平１１−１９１７８１号公報で開示しているように、次の階層のテーブルノードへのポインタと、出力先振り分け情報テーブルの両方を検索テーブルの全階層に必要としていた。これに対して本実施例の検索テーブルは、次の階層のテーブルノードへのポインタのみ持つテーブル（図５）と、出力先振り分け情報を持つテーブル（図７）に分けている。これにより、たとえば実施例で説明した図１２における第２階層のＩＰ検索テーブル３４２あるいは第３階層のＩＰ検索テーブル３４３内に、図示していないがビット列が登録されない検索テーブルノードがあるような場合には、これらの検索テーブルノードを省略し、テーブル量を減らすことができる効果がある。
【０１０３】
本発明の第１の変形例
【０１０４】
先の実施例では検索テーブルは各階層の検索テーブルノードを束ねた形で１組で構成されていたが、これに限るものではない。検索テーブルを階層ごとに独立させることで、各階層の検索処理を並列に動作させ、検索性能を向上させることができる。
【０１０５】
図１５は、本発明の第１の変形例におけるアドレス検索装置を示したものである。このアドレス検索装置３１０Ａは、第１〜第３階層分割ビット列検索ブロック３１２１〜３１２３が縦続接続された構成となっており、第３階層分割ビット列検索ブロック３１２３の後段に出力先振り分け情報取得ブロック３１４Ａが配置されている。第１階層分割ビット列検索ブロック３１２１は、第１階層検索テーブル３１１１を参照するようになっている。同様に第２階層分割ビット列検索ブロック３１２２は、第２階層検索テーブル３１１２を参照し、第３階層分割ビット列検索ブロック３１２３は、第３階層検索テーブル３１１３を参照するようになっている。入力ＩＰアドレス３１６は第１階層分割ビット列検索ブロック３１２１に入力されるようになっており、出力先振り分け情報取得ブロック３１４Ａは出力先振り分け情報テーブル３１５Ａを参照して出力先振り分け情報３１７を取得し、外部に出力するようになっている。
【０１０６】
この第１の変形例のアドレス検索装置３１０Ａも、ＩＰアドレスのビット長、分割する階層数、分割ビット列の長さに制限はないが、先の実施例と同様に、ＩＰアドレスのビット長が“９”、分割数か“３”ならびに分割ビット列の長さが“３”の場合を示している。分割する階層数がこれ以外の値の場合には、これに応じて分割ビット列検索ブロック３１２および検索テーブル３１１の総数が加減されることになる。
【０１０７】
この変形例のアドレス検索装置３１０Ａで第１階層分割ビット列検索ブロック３１２１は、図８に示したステップＳ４２１の初期化手順で、パラメータｎを“１”としたときの、図９に示した第１階層の検索処理（ステップＳ４４１〜ステップＳ４４８）を行う。このようにして第１階層分割ビット列検索ブロック３１２１の処理が終了すると、第１階層分割ビット列検索ブロック３１２１から第２階層分割ビット列検索ブロック３１２２に、検索後の終了フラグ、ＮＸＴＬＰＴＲ、ポインタＲＥＧ＿ＶＢＩＴ、ポインタＲＥＧ＿ＮＮ−ＰＴＲ、パラメータＲＥＧ＿ＳＴＡＧＥならびにＩＰアドレスビット列のパラメータからなる第１階層検索結果情報３１３１を引き渡す。
【０１０８】
第２階層分割ビット列検索ブロック３１２２は、第１階層分割ビット列検索ブロック３１２１から引き渡された第１階層検索結果情報３１３１を用い、パラメータｎを“２”としたときの第２階層の検索処理を図９に示す各ステップＳ４４１〜Ｓ４４８で実行する。第２階層分割ビット列検索ブロック３１２２も同様に、検索後の終了フラグ、ＮＸＴＬＰＴＲ、ポインタＲＥＧ＿ＶＢＩＴ、ポインタＲＥＧ＿ＮＮ−ＰＴＲ、パラメータＲＥＧ＿ＳＴＡＧＥならびにＩＰアドレスビット列のパラメータからなる第２階層検索結果情報３１３２を第３階層分割ビット列検索ブロック３１２３に引き渡す。ただし、第１階層分割ビット列検索ブロック３１２１から引き渡された第１階層検索結果情報３１３１の終了フラグが“ｏｎ”になっているときには、図９に示した第２階層の検索処理（ステップＳ４４１〜Ｓ４４８）を行うことなく、引き渡されたパラメータとしての第２階層検索結果情報３１３２を第３階層分割ビット列検索ブロック３１２３にそのまま引き渡す。
【０１０９】
第３階層分割ビット列検索ブロック３１２３では、第２階層分割ビット列検索ブロック３１２２から引き渡された第２階層検索結果情報３１３２を用い、パラメータｎを“３”としたときの、第３階層の検索処理を図９に示す各ステップＳ４４１〜Ｓ４４８で実行する。ステップＳ４４５あるいはステップＳ４４８の処理が終了したあとは、出力先振り分け情報取得ブロック３１４Ａに、検索後の終了フラグ、ＮＸＴＬＰＴＲ、ポインタＲＥＧ＿ＶＢＩＴ、ポインタＲＥＧ＿ＮＮ−ＰＴＲ、パラメータＲＥＧ＿ＳＴＡＧＥならびにＩＰアドレスビット列のパラメータからなる第２階層検索結果情報３１３２を引き渡す。ただし、第２階層分割ビット列検索ブロック３１２３から引き渡された第２階層検索結果情報３１３２の終了フラグが“ｏｎ”になっているときには、第３階層の検索処理（ステップＳ４４１〜Ｓ４４８）を行うことなく、引き渡されたパラメータとしての第３階層検索結果情報３１３３を出力先振り分け情報取得ブロック３１４Ａにそのまま引き渡す。
【０１１０】
この第１の変形例における出力先振り分け情報取得ブロック３１４Ａの処理は、先の実施例の出力先振り分け情報取得ブロック３１４の処理と同じである。そこでその処理は図１０をそのまま用いることができる。
【０１１１】
本発明の第２の変形例
【０１１２】
図１６は本発明の第２の変形例におけるアドレス検索装置の出力先振り分け情報取得ブロックの要部を表わしたものである。この変形例では、図４に示した出力先振り分け情報取得ブロック３１４において、パラメータＲＥＧ＿ＳＴＡＧＥと入力ＩＰアドレス、ポインタＲＥＧ＿ＶＢＩＴから出力先振り分け情報３１７を求めるためのオフセットポインタを計算するようになっている。
【０１１３】
ここでオフセットポインタとは、出力先振り分け情報テーブルノード内の各ビット列の位置を表わすものである。たとえば、図１３の出力先振り分け情報テーブルノード３７１におけるビット列“１０１”は、先頭のビット列“０”から数えて１２番目のビット列である。そこでこの場合のオフセットポインタは“１２”となる。
【０１１４】
第２の変形例のオフセットポインタ計算部５００は、パラメータＲＥＧ＿ＳＴＡＧＥ５０１と入力ＩＰアドレス５０２を入力するビット列取り出し手段５０３と、ＲＥＧ＿ＶＢＩＴ５０４を入力するＲＥＧ＿ＶＢＩＴ分配手段５０５を備えている。ビット列取り出し手段５０３は、パラメータＲＥＧ＿ＳＴＡＧＥ５０１で表わされる階層に対応する入力ＩＰアドレス５０２のビット列を取り出す。取り出されたパラメータ５０７は入力ＩＰアドレス分配手段５０８に引き渡されるようになっている。入力ＩＰアドレス分配手段５０８は入力ＩＰアドレス５０９を第１〜第Ｍのビット列サーチ手段５１１１〜５１１Ｍに分配する。
【０１１５】
一方、ＲＥＧ＿ＶＢＩＴ分配手段５０５は、ＲＥＧ＿ＶＢＩＴ５０４を各ビット長に分割して、それぞれのビット長ごとに第１〜第Ｍのビット列サーチ手段５１１１〜５１１Ｍに引き渡すようになっている。第１〜第Ｍのビット列サーチ手段５１１１〜５１１Ｍの後段には最長一致検索手段５１３が設けられており、入力されたオフセットポインタ５１４１〜５１４Ｍを基にして、出力先振り分け情報へのオフセットポインタ５１５を出力するようになっている。
【０１１６】
ここでビット列取り出し手段５０３は、パラメータＲＥＧ＿ＳＴＡＧＥ５０１で表わされる階層に対応する入力ＩＰアドレスのビット列を取り出し、入力ＩＰアドレス分配手段５０８にパラメータを引き渡す。先の実施例を例に採ると、入力ＩＰアドレス５０２のビット列を３ビットずつに分割し階層数を“３”にし、各階層のビット長は“３”である。この場合、パラメータＲＥＧ＿ＳＴＡＧＥ５０１の値が“１”の場合には、第１階層であるのでビット“１”からビット“３”までを取り出して、入力ＩＰアドレス分配手段５０８に引き渡す。パラメータＲＥＧ＿ＳＴＡＧＥ５０１の値が“２”の場合には第２階層であるので、ビット“４”からビット“６”までを取り出し、“３”の場合はビット“７”からビット“８”までを取り出し、それぞれ入力ＩＰアドレス分配手段５０８に引き渡すことになる。
【０１１７】
第１〜第Ｍのビット列サーチ手段５１１１〜５１１Ｍは入力ＩＰアドレス５０２のビット列の一部とＲＥＧ＿ＶＢＩＴ５０４を比較して、入力ＩＰアドレス分配手段５０８から引き渡される入力ＩＰアドレス５０２のビット列の一部がＲＥＧ＿ＶＢＩＴ５０４で表わされるビット列と一致しているかを調べる。そして、これらが一致している場合には、最長一致検索手段５１３にオフセットポインタ５１４１〜５１４Ｍを引き渡す。分割した階層のビット長が“３”の場合には、値Ｍは“３”であり、第１〜第３のビット列サーチ手段５１１１〜５１１３が配置されている。これら第１〜第３のビット列サーチ手段５１１１〜５１１３は、特定のビット長のビット列を比較するために用いられる。
【０１１８】
例えば、第１のビット列サーチ手段５１１１は、入力ＩＰアドレス５０２のビット列の一部であるビット長“１”のビット列と、ビット長が“１”であるビット列が登録されているか否かを示すＲＥＧ＿ＶＢＩＴ５０４の最初の２ビットを比較し、一致している場合は、出力先振り分け情報テーブルノードのビット列“０”あるいはビット列“１”のオフセットポインタ５１４１を、最長一致検索手段５１３に引き渡す。
【０１１９】
入力ＩＰアドレス分配手段５０８は、ビット列取り出し手段５０３から引き渡されたビット列を、第１のビット列サーチ手段５１１１から第Ｍのビット列サーチ手段５１１Ｍまでに分配する。例えば第１の実施例を例にすると、第１のビット列サーチ手段５１１１には取り出したビット列の上位１ビットを渡す、第２のビット列サーチ手段５１１２には取り出したビット列の上位１ビットから２ビット目までのビット列を渡す。第Ｍのビット列サーチ手段５１１Ｍには取り出したすべてのビット列を引き渡す。
【０１２０】
ＲＥＧ＿ＶＢＩＴ分配手段５０５は、ＲＥＧ＿ＶＢＩＴ５０４を各ビット長に分割して、それぞれのビット長ごとに第１〜第Ｍのビット列サーチ手段５１１１〜５１１Ｍへ引き渡す。第１のビット列サーチ手段５１１１にはポインタＲＥＧ＿ＶＢＩＴの１ビット目から２ビット目の２ビットを引き渡す。第２のビット列サーチ手段５１１２にはポインタＲＥＧ＿ＶＢＩＴの３ビット目から６ビット目までの４ビットを引き渡す。第Ｍのビット列サーチ手段５１１Ｍには、ポインタＲＥＧ＿ＶＢＩＴの右から２のＭ乗ビットを、引き渡す。例えば、階層のビット長が“３”の場合は、値Ｍは“３”となる。このときのＲＥＧ＿ＶＢＩＴ５０４は図３に示された通りである。すなわち、最初の２ビットが１ビット長で、３ビット目から６ビット目までが２ビット長、７ビット目から１４ビット目までが３ビットとなる。値Ｍが“３”のこの場合、これらのビット列がそれぞれ第１〜第３のビット列サーチ手段５１１１〜５１１３へ引き渡される。
【０１２１】
最長一致検索手段５１３は、第１〜第Ｍのビット列サーチ手段５１１１〜５１１Ｍからそれぞれ引き渡されるオフセットポインタ５１４１〜５１４Ｍのうち、ビット長が最長のビット列サーチ手段（これをビット列サーチ手段５１１Ｘとする。）のオフセットポインタ５１４Ｘを採用する。そして、出力先振り分け情報３１７（図４）へのオフセットポインタとして取り出す。例えば、第２のビット列サーチ手段５１１２と第３のビット列サーチ手段５１１３の両方からオフセットポインタを渡されたときは、ビット長の長い第３のビット列サーチ手段５１１３から受け取ったオフセットポインタを採用することになる。
【０１２２】
この変形例では、図１６に示すような構成としたので、ビット列の比較を並行して処理することができる。このため、ハードウェアや並列プロセッシング可能な回路や装置でアドレス検索装置を実現することが容易になり、単位時間あたりの検索数の性能を向上させることができる。
【０１２３】
なお、以上説明した実施例では分割ビット列を３ビットずつ等分割されたビット列として示したが、３ビット以外のビット数で分割するものであってもよい。また、分割ビット列は互いに等しいビット列である必要はなく、異なったビット列構成となっていてもよい。
【０１２４】
また、実施例ではＩＰアドレスの検索について説明したが、これ以外に分岐した経路を順に辿っていくようなルート情報を有するすべての検索に本発明を適用することができることは当然である。
【０１２５】
【発明の効果】
以上説明したように請求項１記載の発明によれば、アドレス検索装置に次々入力されるルート情報を、各分割ビット列をそれぞれ枝とする木構造に沿って対応付けていき、他のルート情報と共通の枝（階層）となっている状態では、１つずつ階層を上げて行って次の分割ビット列を追加的に使用するようにすると共に、木構造の各節に対応する位置に検索テーブルノードを配置しているので、最大でも階層の数だけの検索テーブルノードの検索を行えば足り、ルート情報を分割して得られた分割ビット列の総数に相当する検索テーブルノードの検索は必要としないので、検索処理が迅速となる。また、それぞれのルート情報に対応する出力先振り分け情報は、出力先振り分け情報記憶手段に一括して記憶しておくので、記憶領域の有効活用を行うことができるだけでなく、検索テーブルの変更や登録削除が容易になるという利点がある。
【０１２６】
また請求項２記載の発明によれば、検索テーブルノードのうちで次検索テーブルノード指示情報を格納しているもののみが、次検索テーブルノード指示情報を格納する領域を配置することができ、これにより検索テーブル全体のメモリ容量を削減することができる。
【０１２７】
更に請求項３記載の発明によれば、各階層の検索テーブルノードは、１つ上の階層の検索テーブルノードが存在するかどうかを判別させるための有効情報有無情報を配置しているので、これによって木構造のそれぞれの枝が先端であるかどうかを簡単に判別することができる。
【０１２８】
更に請求項６記載の発明によれば、分割ビット列取り出し手段が順に取り出す分割ビット列は、それぞれ互いに等しいビット数で構成されるので、分割処理を単純化すると共に前記した出力先振り分け情報が記憶されている領域のサイズの均一化を図ることができる。
【図面の簡単な説明】
【図１】本発明の一実施例のアドレス検索装置で使用する検索テーブルの要部を表わした説明図である。
【図２】本実施例のアドレス検索装置の検索テーブルでのビット更新の処理の様子を表わした流れ図である。
【図３】本実施例で分割ビット列のビット数が“３”の場合のＶＢＩＴフィールドを表わした説明図である。
【図４】本実施例におけるアドレス検索装置の構成を示したブロック図である。
【図５】図４に示した検索テーブルの１つのノードを示した説明図である。
【図６】分割ビット列を３ビットとした場合の検索テーブルノードの構成例を示した説明図である。
【図７】図４に示した出力先振り分け情報テーブルの１つのノードを示した説明図である。
【図８】本実施例で出力先振り分け情報取得ブロックへ渡す検索結果を求める処理の流れを表わした流れ図である。
【図９】本実施例で検索テーブルの検索処理の流れを表わした流れ図である。
【図１０】本実施例で出力先振り分け情報を取得する処理の流れを表わした流れ図である。
【図１１】本実施例で検索テーブルに登録されているＩＰアドレスを示した説明図である。
【図１２】本実施例でＩＰアドレスＰ１〜Ｐ５を登録した場合の第１階層から第３階層までのＩＰ検索テーブルを表わした説明図である。
【図１３】本実施例でＩＰアドレスＰ１〜Ｐ５を登録した場合の出力先振り分け情報テーブルを表わした説明図である。
【図１４】図１２および図１３のＩＰ検索テーブルおよび出力先振り分け情報テーブルに、ビット列“１０１０１”を登録するときの処理を示した説明図である。
【図１５】本発明の第１の変形例におけるアドレス検索装置を示したブロック図である。
【図１６】本発明の第２の変形例におけるアドレス検索装置の出力先振り分け情報取得ブロックの要部を表わしたブロック図である。
【図１７】８つのＩＰアドレスＰ１〜Ｐ８のビットパターンを表わした説明図である。
【図１８】従来のバイナリ・ツリー検索法を示した説明図である。
【図１９】従来のプレフィックス拡張検索方法を示した説明図である。
【図２０】図１７に示した元となるＩＰアドレスと３つのレベルに拡張されたＩＰアドレスを対比して示した説明図である。
【図２１】４つのＩＰアドレスＰ１〜Ｐ４のビットパターンを表わした説明図である。
【図２２】拡張後の４ビットのビット列とこれに拡張されたＩＰアドレスを対比した説明図である。
【図２３】従来の検索テーブルの内容を表わした説明図である。
【図２４】従来における分割ビット列を管理するアドレス検索装置の構成の概要を表わしたブロック図である。
【図２５】従来のアドレス検索装置のビット更新の処理の流れを表わした流れ図である。
【符号の説明】
３００　検索テーブル
３０１、３１５　出力先振り分け情報テーブル
３０２　ポインタ
３０３　ＶＢＩＴフィールド
３１０、３１０Ａ　アドレス検索装置
３１１　検索テーブル
３１２　分割ビット列検索ブロック
３１４、３１４Ａ　出力先振り分け情報取得ブロック
３１６　ＩＰアドレス
３２１、３５１〜３５４　検索テーブルノード
３２２　ビット列ＥＢＩＴ
３４１　第１階層のＩＰ検索テーブル
３４２　第２階層のＩＰ検索テーブル
３４３　第３階層のＩＰ検索テーブル
５０８　入力ＩＰアドレス分配手段
５１３　最長一致検索手段
【図１】
2004056639.tif 000003
【図２】
2004056639.tif 000004
【図３】
2004056639.tif 000005
【図４】
2004056639.tif 000006
【図５】
2004056639.tif 000007
【図６】
2004056639.tif 000008
【図７】
2004056639.tif 000009
【図８】
2004056639.tif 000010
【図９】
2004056639.tif 000011
【図１０】
2004056639.tif 000012
【図１１】
2004056639.tif 000013
【図１２】
2004056639.tif 000014
【図１３】
2004056639.tif 000015
【図１４】
2004056639.tif 000016
【図１５】
2004056639.tif 000017
【図１６】
2004056639.tif 000018
【図１７】
2004056639.tif 000019
【図１８】
2004056639.tif 000020
【図１９】
2004056639.tif 000021
【図２０】
2004056639.tif 000022
【図２１】
2004056639.tif 000023
【図２２】
2004056639.tif 000024
【図２３】
2004056639.tif 000025
【図２４】
2004056639.tif 000026
【図２５】
2004056639.tif 000027