(57)【要約】【課題】  検索に要する時間を均等に保ち、境界値テーブルを簡単な手順により生成し、エントリの削除または追加に要する処理負荷を軽減させる。【解決手段】  総検索データ数を同一エントリの登録を許容することにより２のべき乗個含む検索テーブルを備える。全ての最長プレフィクス指定値を、プレフィクス指定が表す範囲間の包含関係のリンクと隣接独立関係のリンクの２種類のリンク構造を持つツリー型データ構造として保持し、このツリー型データ構造のリンクをたどることにより境界値テーブル全体を生成する。最長プレフィクス指定値の削除に際し、前記境界値テーブル上の該当する削除エントリの検索結果データ値を、直前のエントリの検索結果データと同じ値に更新する。また、追加に際しては、既存の重複エントリを更新することにより対応する。【選択図】  図２
2005117211.tif 000002
【特許請求の範囲】
【請求項１】
プレフィクス指定を所定の範囲に分解する手段と、
この分解された範囲に基づくプレフィクス指定の包含関係によりプレフィクス指定間に生ずる区間も１つの独立した範囲とする手段と、
全ての各範囲の先頭値を昇順にソートした境界値テーブルと、
この境界値テーブルを２分検索して入力データの最長プレフィクス一致検索を行う手段と
を備えたデータ検索装置において、
総検索データ数を同一エントリの登録を許容することにより２のべき乗個含む前記境界値テーブルを備えた
ことを特徴とするデータ検索装置。
【請求項２】
全ての最長プレフィクス指定値を、プレフィクス指定が表す範囲間の包含関係のリンクと隣接独立関係のリンクの２種類のリンク構造を持つツリー型データ構造として保持する手段と、
このツリー型データ構造のリンクをたどることにより境界値テーブル全体を生成する手段と
を備えた請求項１記載のデータ検索装置。
【請求項３】
最長プレフィクス指定値の削除に際し、前記境界値テーブル上の該当する削除エントリの検索結果データ値を、直前のエントリの検索結果データと同じ値に更新する手段を備えた請求項１記載のデータ検索装置。
【請求項４】
最長プレフィクス指定値の追加に際し、前記境界値テーブル上の同一エントリの登録を許容することにより生じた重複したエントリまたは前記更新する手段により直前のエントリの検索結果データと同じ値に更新されたエントリの検索結果データ値を、追加されるエントリの検索結果データと同じ値に更新する手段を備えた請求項１または３記載のデータ検索装置。
【請求項５】
情報処理装置にインストールすることにより、その情報処理装置に、
プレフィクス指定を所定の範囲に分解する機能と、
この分解された範囲に基づくプレフィクス指定の包含関係によりプレフィクス指定間に生ずる区間も１つの独立した範囲とする機能と、
全ての各範囲の先頭値を昇順にソートした境界値テーブルに相応する機能と、
この境界値テーブルを２分検索して入力データの最長プレフィクス一致検索を行う機能と
を備えたデータ検索装置に相応する機能を実現させるプログラムにおいて、
総検索データ数を同一エントリの登録を許容することにより２のべき乗個含む前記境界値テーブルに相応する機能を実現させる
ことを特徴とするプログラム。
【請求項６】
全ての最長プレフィクス指定値を、プレフィクス指定が表す範囲間の包含関係のリンクと隣接独立関係のリンクの２種類のリンク構造を持つツリー型データ構造として保持する機能と、
このツリー型データ構造のリンクをたどることにより境界値テーブル全体を生成する機能と
を実現させる請求項５記載のプログラム。
【請求項７】
最長プレフィクス指定値の削除に際し、前記境界値テーブル上の該当する削除エントリの検索結果データ値を、直前のエントリの検索結果データと同じ値に更新する機能を実現させる請求項５記載のプログラム。
【請求項８】
最長プレフィクス指定値の追加に際し、前記境界値テーブル上の同一エントリの登録を許容することにより生じた重複したエントリまたは前記更新する機能により直前のエントリの検索結果データと同じ値に更新されたエントリの検索結果データ値を、追加されるエントリの検索結果データと同じ値に更新する機能を実現させる請求項５または７記載のプログラム。
【請求項９】
請求項５ないし８のいずれかに記載のプログラムが記録された前記情報処理装置読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はＩＰルータなどのパケット転送装置に利用する。特に、パケット転送処理を行うにあたり、入力回線から入力されたパケットの宛先アドレスからパケットの次ホップルータを決定する際に使用するテーブル検索装置に関する。
【背景技術】
【０００２】
従来は、ＩＰルータなどのパケット転送装置においては、パケットヘッダに搭載された宛先アドレスを元にルーティングテーブルを検索し、次ホップルータを決定している。ルーティングテーブルは宛先アドレスと次ホップルータの関係とを保持している。
【０００３】
パケット転送装置で宛先アドレスを検索する規則を説明する。パケット転送装置においては、パケットヘッダに搭載された宛先アドレスを元にルーティングテーブルを検索し、次のホップ先を決定する。インターネットではＣＩＤＲ(Classless Inter Domain Routing)の機構が導入されており、ルーティングテーブルの宛先アドレスは３２ビットのＩＰアドレスとそれに対するプレフィクス長の組み合わせで表現される。ルーティングテーブルの宛先アドレスは“ＩＰアドレス／プレフィクス長”の形式で表される。
【０００４】
宛先アドレスのうち、プレフィクス長で指定された長さ以降のビットに関してはＤｏｎ‘ｔ  Ｃａｒｅである。例えば、１２９．１３１．１７５．１２９／３２は３２ビット全てのビットがＤｏｎ’ｔ  Ｃａｒｅでない宛先アドレスであり、１２９．６０．８３／２４は先頭の２４ビットが有効な宛先アドレスである。パケットヘッダの宛先アドレスが１２９．６０．８３．１も１２９．６０．８３．１１１も同じ宛先アドレス１２９．６０．８３／２４に一致する。
【０００５】
ルーティングテーブルはパケットヘッダの宛先アドレスをキーとして用いて検索する。ルーティングテーブルを検索する際に、ＣＩＤＲでは最長一致と呼ばれるルーティングテーブル検索規則に基づく。最長一致とはキーに用いる宛先アドレスが最も長く一致するものを正解とするものである。例えば、ルーティングテーブルに宛先アドレス１２９．３８．１１１／２４と宛先アドレス１２９．３８／１６の二つの宛先アドレスがある場合に、１２９．３８．１１１．２という宛先アドレスを持つパケットが到着した場合は、宛先アドレス１２９．３８．１１１／２４の方がより長い範囲で一致するので、それを正解とする。
【０００６】
ツリーを用いて宛先アドレスを検索する例として境界値テーブルを用いた方式を紹介する。境界値テーブルを用いたツリー検索方式とは、最長一致検索を範囲検索の問題に変換して、昇順にソートされた境界値テーブルからツリーを作成し検索を行うという方式である。図１０にルーティングテーブルの例を示す。ルーティングテーブルのエントリは、ＩＰアドレスとプレフィクス長とで指定され、それに対応する次ホップルータを表す値が存在する。
【０００７】
図１１に、図１０のルーティングテーブルを元にした宛先アドレス空間を示す。ルーティングテーブルのエントリは、ＩＰアドレスとプレフィクス長とで指定されるため、１つのエントリは範囲で示すことができる。例えば１．２．３．＊は１．２．３．０〜１．２．３．２５５と等価である。
【０００８】
図１２に図１０のルーティングテーブルを元にした境界値テーブルを示す。境界値テーブルでは、ルーティングテーブルの１つのエントリを始まりと終わりの２つの境界値で表し、この範囲に入った場合にルーティングテーブルの当該エントリに一致したと判断する。したがって、境界値テーブルの境界値の数は、最大でルーティングテーブルのエントリ数の２倍になる。また、ルーティングアドレス指定におけるプレフィクスの仕組みにより、各範囲はお互いに独立しているか、どちらかが相手を包含しているかの２種類の関係のみで、一部の範囲が重なるような関係はない。
【０００９】
図１３に図１２の境界値テーブルを元にした２分探索(binary search)のツリーを示す。境界値テーブルを用いたツリー検索方式は、２入力されたパケットの宛先アドレスから２分探索のツリーを用いて次ホップルータを決定するというものである。ツリーのノード上には境界値と次ホップルータを表す値とが格納されている。ツリーの検索はツリーのルート（頂点）から行い、各ノードではパケットの宛先アドレスとノードに格納されている境界値の大小の比較を行う。大小の比較によって次のノードへ順々に移っていく。ツリーの検索が終了した時点でパケットの宛先アドレスがどの範囲に入っているかを調査することで検索の回答結果となる次ホップルータが決定できる。
【００１０】
具体的な検索方法について図１４を用いて説明する。検索すべきパケットの宛先アドレスが１．２．３．２０の場合、まずツリーのルート（ｒｏｏｔ：頂点）のノードで境界値と比較をする。この場合は、
１．２．３．２０＜１．２．３．２６
なので次ノードとして左下のノードへ移る。このノードでも境界値と比較する。
１．２．３．２０＞１．２．３．０
なので、今度は右下のノードへ移る。ここでも同様に比較を行うと
１．２．３．２０＜１．２．３．２５
であり、ここで検索を終了する。
【００１１】
パケットの宛先アドレスが含まれる範囲は、
１．２．３．０（ＮＨ＝Ｂ）＜１．２．３．２０＜１．２．３．２５（ＮＨ＝Ｃ）
となることがわかり、１．２．３．２０の次ホップルータはＢとなる。
【００１２】
ここで、注意すべきことは、ノードの境界値は「その境界値以上の場合、宛先アドレスの次ホップルータを表す値がそのノードが格納している次ホップルータを表す値となる」ということである。すなわち
１．２．３．０（ＮＨ＝Ｂ）≦Ｘ＜１．２．３．２５（ＮＨ＝Ｃ）
の場合、Ｘの次ホップルータはＣではなくＢである。したがって、「以上」で前ノードから１．２．３．２５（ＮＨ＝Ｃ）のノードに到着した場合、１．２．３．２５以外の値が宛先ＩＰアドレスであれば前ノード（ここでは１．２．３．０（ＮＨ＝Ｂ））に格納されている次ホップルータを表す値が解となる。
【００１３】
図１５に具体的な検索例をもう１つ示す。今度はパケットの宛先アドレスが１．２．３．３０の場合である。図１４と同様に検索を行うと、
１．２．３．２６（ＮＨ＝Ｂ）＜１．２．３．３０＜１．２．４．０（ＮＨ＝Ａ）
となることが分かり、パケットの宛先アドレス１．２．３０の次ホップルータはＢとなる。宛先アドレスが含まれる範囲を見つけるので、「未満」で前ノードから到着した場合には、１．２．４．０以外の値が宛先ＩＰアドレスであれば、前々ノードに格納されている次ホップルータを表す値が解となる（例えば特許文献１または２参照）。
【００１４】
【特許文献１】特開２０００−３３２７８６号公報
【特許文献２】特開２０００−３５８０６４号公報
【発明の開示】
【発明が解決しようとする課題】
【００１５】
このような従来のテーブル検索では、異なる方路によって、検索に要する時間にバラツキがある。例えば、図１０に示すように、ツリーの枝の長さにはバラツキがあり、これにより検索に要する時間のバラツキを生じる。このような検索時間のバラツキは、複数経路のパケット転送を均等な処理時間で処理しようとしたときに問題となる。
【００１６】
また、従来の境界値テーブルの生成では、宛先アドレス空間を生成し、これに基づき境界値テーブルを生成していたが、さらに簡単な手順による境界値テーブルの生成が望まれる。
【００１７】
また、ルーティングテーブルからエントリを１件削除する際には、境界値テーブルでは始まりと終わりの２つの境界値を削除する他に、当該範囲に包含されていたエントリの隙間部分の次ホップルータ値も修正する必要が生じ、大きな処理負荷を要する問題がある。
【００１８】
また、ルーティングテーブルにエントリを１件追加する際には、当該追加されるエントリ以降の他のエントリを１つずつずらす必要があり、大きな処理負荷を要する問題がある。
【００１９】
本発明は、このような背景に行われたものであって、検索に要する時間を均等に保つことができ、境界値テーブルを簡単な手順により生成することができ、エントリの削除または追加に要する処理負荷を軽減させることができるテーブル検索装置を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明は、プレフィクス指定を所定の範囲に分解する手段と、この分解された範囲に基づくプレフィクス指定の包含関係によりプレフィクス指定間に生ずる区間も１つの独立した範囲とする手段と、全ての各範囲の先頭値を昇順にソートした境界値テーブルと、この境界値テーブルを２分検索して入力データの最長プレフィクス一致検索を行う手段とを備えたデータ検索装置である。
【００２１】
ここで、本発明の特徴とするところは、総検索データ数を同一エントリの登録を許容することにより２のべき乗個含む前記境界値テーブルを備えたところにある。
【００２２】
これにより、検索ツリーの枝の長さを均等にすることができるため、全ての方路について、検索回数を同じにして検索時間を均等に保つことができる。
【００２３】
また、全ての最長プレフィクス指定値を、プレフィクス指定が表す範囲間の包含関係のリンクと隣接独立関係のリンクの２種類のリンク構造を持つツリー型データ構造として保持する手段と、このツリー型データ構造のリンクをたどることにより境界値テーブル全体を生成する手段とを備えることができる。
【００２４】
例えば、プレフィクス指定が表す範囲間の包含関係のリンクでは、単に包含関係について判定すればよく、宛先アドレス空間を生成するときに必要となる包含されるもの同士の大小関係まで考慮する必要はない。また、隣接独立関係のリンクでは、単に、個々の宛先アドレスがとる境界値について判定すればよく、それらの包含関係については判定する必要はない。このようにして生成されたツリー型データ構造のリンクをたどることにより境界値テーブルが生成されるので、境界値テーブル生成に要する手順を簡単化することができる。
【００２５】
また、最長プレフィクス指定値の削除に際し、前記境界値テーブル上の該当する削除エントリの検索結果データ値を、直前のエントリの検索結果データと同じ値に更新する手段を備えることができる。
【００２６】
このように、境界値テーブルからはデータを削除するのではなく、データを無効化して更新することにより、エントリの削除に対応することができるため、エントリ削除に伴い発生する処理負荷を軽減させることができる。
【００２７】
また、最長プレフィクス指定値の追加に際し、前記境界値テーブル上の同一エントリの登録を許容することにより生じた重複したエントリまたは前記更新する手段により直前のエントリの検索結果データと同じ値に更新されたエントリの検索結果データ値を、追加されるエントリの検索結果データと同じ値に更新する手段を備えることができる。
【００２８】
このように、追加エントリがあるときには、既に境界値テーブル上に存在するエントリの中から、重複したエントリを探し、これを更新することによってエントリの追加を行うことができる。これによれば、従来、エントリの追加の度に、全てのエントリをずらして更新する必要があったが、そのような必要はなく、エントリ追加に伴い発生する処理負荷を軽減させることができる。
【００２９】
また、本発明はプログラムとして実現することができる。すなわち、本発明は、情報処理装置にインストールすることにより、その情報処理装置に、プレフィクス指定を所定の範囲に分解する機能と、この分解された範囲に基づくプレフィクス指定の包含関係によりプレフィクス指定間に生ずる区間も１つの独立した範囲とする機能と、全ての各範囲の先頭値を昇順にソートした境界値テーブルに相応する機能と、この境界値テーブルを２分検索して入力データの最長プレフィクス一致検索を行う機能とを備えたデータ検索装置に相応する機能を実現させるプログラムである。
【００３０】
ここで、本発明の特徴とするところは、総検索データ数を同一エントリの登録を許容することにより２のべき乗個含む前記境界値テーブルに相応する機能を実現させるところにある。
【００３１】
また、全ての最長プレフィクス指定値を、プレフィクス指定が表す範囲間の包含関係のリンクと隣接独立関係のリンクの２種類のリンク構造を持つツリー型データ構造として保持する機能と、このツリー型データ構造のリンクをたどることにより境界値テーブル全体を生成する機能とを実現させることができる。
【００３２】
また、最長プレフィクス指定値の削除に際し、前記境界値テーブル上の該当する削除エントリの検索結果データ値を、直前のエントリの検索結果データと同じ値に更新する機能を実現させることができる。
【００３３】
また、最長プレフィクス指定値の追加に際し、前記境界値テーブル上の同一エントリの登録を許容することにより生じた重複したエントリまたは前記更新する機能により直前のエントリの検索結果データと同じ値に更新されたエントリの検索結果データ値を、追加されるエントリの検索結果データと同じ値に更新する機能を実現させることができる。
【００３４】
本発明は、本発明のプログラムが記録された前記情報処理装置読み取り可能な記録媒体として実現することができる。本発明のプログラムは本発明の記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００３５】
これにより、汎用の情報処理装置を用いて、検索に要する時間を均等に保つことができ、境界値テーブルを簡単な手順により生成することができ、エントリの削除または追加に要する処理負荷を軽減させることができるテーブル検索装置を実現することができる。
【発明の効果】
【００３６】
本発明によれば、検索に要する時間を均等に保つことができ、境界値テーブルを簡単な手順により生成することができ、エントリの削除または追加に要する処理負荷を軽減させることができる。
【発明を実施するための最良の形態】
【００３７】
本発明実施例のデータ検索装置の構成を図１を参照して説明する。図１は本実施例のデータ検索装置の構成図である。
【００３８】
本実施例のデータ検索装置は、図１に示すように、プレフィクス指定を所定の範囲に分解する手段と、この分解された範囲に基づくプレフィクス指定の包含関係によりプレフィクス指定間に生ずる区間も１つの独立した範囲とする手段とを含むテーブル作成部２を備え、このテーブル作成部２により、全ての各範囲の先頭値を昇順にソートした境界値テーブルをテーブル格納部３に生成する。また、パケットフォワーディング部１は、この境界値テーブルを２分検索して入力データの最長プレフィクス一致検索を行う手段を備える。
【００３９】
（検索テーブルの構成）
ＩＰルータにおいて、到着パケットのネクストホップを決定するためのルーティング情報は、ＩＰアドレス、プレフィクス長、ネクストホップアドレスの３つのデータの組で表される。
【００４０】
本発明では、プレフィクス指定をアドレス範囲検索として２分検索するために、ルーティングテーブルから検索用のテーブルを作成する。このテーブルを境界値テーブルと呼ぶ。
【００４１】
境界値テーブルでは、ルーティングテーブルの１つのエントリーを始まりと終わりの２つの境界値で表す。図２にＩＰｖ４での境界値テーブルの例を示す。例えば、図２に示すＩＰｖ４の例として、ＩＰアドレスが１．２．３．＊でプレフィクス長が２４ビットのルーティングテーブル要素があった場合、境界値テーブルの要素としては、範囲の始まりのアドレス１．２．３．０と、範囲の終わりのアドレスの次のアドレス１．２．４．０の２つの要素に変換される。
【００４２】
入力ＩＰアドレスが、この範囲に入った場合にルーティングテーブルの当該エントリーに一致したと判断する。従って、境界値テーブルの境界値の数は、最大でルーティングテーブルのエントリー数の２倍になる。また、ルーティングアドレス指定におけるプレフィクスの仕組みにより、各範囲はお互いに独立しているか、どちらかが相手を包含しているかの２種類の関係のみで、一部の範囲が重なるような関係はない。
【００４３】
包含された範囲間の隙間の範囲では、包含する範囲のネクストホップ値が適用されるので、包含された範囲の終端側の境界値要素のネクストホップ値には、包含する範囲のネクストホップ値を指定する。
【００４４】
（境界値テーブルのＮｅｘｔＨｏｐ欄の値）
境界値に対応するＮｅｘｔＨｏｐ値の欄には、入力ＩＰアドレスが境界値に等しいか、あるいは、入力ＩＰアドレスの方が大きい場合のＮｅｘｔＨｏｐ値を記述しておく。ただし、２分検索最終段階での比較で、
ＩＰアドレス＜境界値
の場合、１つ上の境界値テーブルエントリのＮｅｘｔＨｏｐ値を参照する必要がある。また、ルーティングテーブル上でのプレフィクス長が全ビット幅に等しい完全一致条件のエントリも２つの境界値に分解される。
【００４５】
（境界値が重なった場合の境界値テーブルの構成方法）
境界値が重なった場合、最長一致優先のルールにより、プレフィクス長の長いエントリーから領域を占有するように、ネクストホップ値を選択する。図３に境界値が重なった場合の境界値テーブルの構成例を示す。
【００４６】
（デフォルトネクストホップ値用の境界値テーブル要素）
デフィルトネクストホップ値用の境界値テーブル要素は、プレフィクス長ゼロのルーティングテーブルエントリーとして境界値テーブルに展開する。
【００４７】
開始側境界値は、全ビット“０”として、ネクストホップ値はデフォルトネクストホップ値とする。終端境界値は、範囲の終わりのアドレスの次のアドレスとした場合、アドレスビット幅の範囲を超えることになるので、全ビット“１”として、ネクストホップ値はデフォルトネクストホップ値とすることにより、代用することができる。ただし、全アドレス空間内で独立する範囲の中で、最もアドレス値の大きい範囲の終端側の境界値要素のネクストホップ値は、デフォルトネクストホップ値となるので、これを範囲テーブルの最終要素とすることにより、デフォルトネクストホップ値用の境界値テーブル要素の終端側要素を省略することができる。
【００４８】
（境界値テーブルにおける冗長エントリ）
あらかじめ境界値で昇順にソートされた境界値テーブル上を、入力ＩＰアドレスで２分検索して、入力ＩＰアドレスが属する範囲を検索して、ルーティング表のプレフィクス最長一致検索を実現する場合、以下のような境界値テーブルエントリは検索結果に影響を与えない。
１）境界値とＮｅｘｔＨｏｐ値の両方が、１つ上のエントリと同じ。
２）境界値とＮｅｘｔＨｏｐ値の両方が、１つ下のエントリと同じ。
３）境界値は任意の昇順値で、ＮｅｘｔＨｏｐ値が１つ上のエントリと同じ。
【００４９】
これらの冗長エントリを境界値テーブルに追加して、境界値テーブルの大きさを２のべき乗個にすることで、あらかじめ決まった検索回数で、ルーティング表のプレフィクス最長一致検索を実現することができる。すなわち、本実施例のデータ検索装置は、総検索データ数を同一エントリの登録を許容することにより２のべき乗個含む境界値テーブルをテーブル作成部２により生成してテーブル格納部３に備える（請求項１）。
【００５０】
図４に、境界値テーブルの大きさを２のべき乗個にした例を示す。図中の１）、２）、３）は上記説明の１）、２）、３）に対応する。また、図中※マークを付したエントリが冗長エントリである。これら冗長エントリは、ルーティング表の更新に対応して、境界値テーブルの動的更新にも利用することができる。
【００５１】
（境界値テーブルの生成方法）
ルーティングテーブルデータは、１件毎に、ＩＰアドレス、プレフィクス長、ネクストホップアドレスの３つのデータの組で表される。プレフィクスの仕組みにより、各範囲はお互いに独立しているか、どちらかが相手を包含しているかの２種類の関係のみである性質を利用して、包含関係を親子のリンクで接続し、同一の親に包含される独立関係の各範囲はＩＰアドレスの昇順で線形リスト構造にリンクする。この木構造を辿ることで、境界値テーブルを生成することができる。
【００５２】
この境界値テーブル生成手順を図５および図６を参照して説明する。図５はルーティングテーブルのエントリを昇順に並べたツリーを示す図である。図６は図５のツリーを辿ることにより境界値テーブルが生成される過程を示す図である。まず、図５に示すように、ルーティングテーブルのエントリを昇順に並べ、エントリの上から順番にツリーを作成する。このツリーの横方向は、左から右にプレフィクスの昇順である。まず、最初に＊．＊．＊．＊を置く（１）。次に、１．＊．＊．＊／８を置く。これは、＊．＊．＊．＊に内包されるのでその横に並べて置く（２）。次に１．２．３．＊／２４を置く。これは１．＊．＊．＊に内包されるのでその横に並べて置く（３）。次に１．２．３．２５／３２を置く。これは１．２．３．＊に内包されるのでその横に置く（４）。次に１．２．５．＊／２４を置く。これは１．＊．＊．＊に内包され、１．２．３．＊とプレフィクスが同じなので、１．２．３．＊／２４と縦（並列）に並べて置く（４）。これでプレフィクスを昇順に並べたツリーが完成する。
【００５３】
次に、図６を参照して、図５のツリーを辿ることにより境界値テーブルを生成する手順を説明する。最初に０．０．０．０を作成しておく。ツリーを左から右に辿り、突き当たったら右に戻る。このときに、下への分岐があれば、一段下がってから右に戻る。この繰り返しによりツリーを全て辿る。このとき、左から右に辿る際には、＊を０にしたエントリを追加する。右から左に戻る場合は、その場所の範囲の上の値と（１．２．３．＊の場合、１．２．３．４未満で１．２．４．０を追加）、ツリーの辿った先の範囲の上限値の２つを追加する。これにより境界値テーブルが生成される。
【００５４】
すなわち、本実施例のテーブル検索装置のテーブル作成部２は、全ての最長プレフィクス指定値を、プレフィクス指定が表す範囲間の包含関係のリンク（図５の横並びの関係）と隣接独立関係のリンク（図５の縦並びの関係）の２種類のリンク構造を持つツリー型データ構造として保持する手段と、図６に示すように、このツリー型データ構造のリンクをたどることにより境界値テーブル全体を生成する手段とを備える（請求項２）。
【００５５】
（テーブル削除）
ルーティングテーブルからエントリを１件削除する場合、境界値テーブルでは始まりと終わりの２つの境界値を削除する他に、当該範囲に包含されていたエントリの隙間部分のＮｅｘｔＨｏｐ値も修正する必要が生じる。この様子を図７に示す。
【００５６】
（ルーティングテーブルエントリの削除と冗長エントリ）
削除の際に、境界値テーブルのエントリを以下の方法で無効化することができる。
１）境界値とＮｅｘｔＨｏｐ値の両方を１つ上のエントリと同じにする。
２）境界値とＮｅｘｔＨｏｐ値の両方を１つ下のエントリと同じにする。
３）境界値は変更しないで、ＮｅｘｔＨｏｐ値を１つ上のエントリと同じにする。
【００５７】
図８に、境界値を変更しないでＮｅｘｔＨｏｐ値を１つ上のエントリと同じに変更する例を示す。図８の例では、Ｎｏ．４のエントリを削除した。これに対し、境界値テーブルでは、Ｎｏ．４に対応するＮｅｘｔＨｏｐ値をｄからｃに書き換えるだけでエントリの削除が完了している。
【００５８】
すなわち、本実施例のテーブル検索装置のテーブル作成部２は、最長プレフィクス指定値の削除に際し、境界値テーブル上の該当する削除エントリの検索結果データ値を、直前のエントリの検索結果データと同じ値に更新する手段を備える（請求項３）。
【００５９】
（ルーティングテーブルエントリの追加）
本実施例のデータ検索装置のテーブル作成部２は、最長プレフィクス指定値の追加に際し、前記境界値テーブル上の同一エントリの登録を許容することにより生じた重複したエントリまたはエントリ削除のために直前のエントリの検索結果データと同じ値に更新されたエントリの検索結果データ値を、追加されるエントリの検索結果データと同じ値に更新することによって、ルーティングテーブルエントリの追加を行う手段を備える（請求項４）。
【００６０】
図９に、エントリの追加例を示す。図９の例では、Ｎｏ．６のエントリが追加になっている。Ｎｏ．６のエントリの境界値は１．２．＊．＊であり、ＮｅｘｔＨｏｐ値はｆであり、２つある境界値１．１．０．０よりも大きいので、そのうちの一つを１．２．０．０とし、また、２つある境界値１．３．０．０よりも小さく、また、境界値１．２．５．０よりも大きい場合も含むので、そのうちの１つを１．２．６．０とする。また、これらのＮｅｘｔＨｏｐ値をｂからｆに変更する。
【００６１】
本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に本発明のテーブル検索装置に相応する機能を実現させるプログラムとして実現することができる（請求項５〜８）。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ（請求項９）、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に、本発明のテーブル検索装置のパケットフォワーディング部１、テーブル作成部２、テーブル格納部３にそれぞれ相応する機能を実現させることができる。
【産業上の利用可能性】
【００６２】
本発明によれば、検索に要する時間を均等に保つことができ、境界値テーブルを簡単な手順により生成することができ、エントリの削除または追加に要する処理負荷を軽減させることができる。これにより、ルータなどのパケット転送装置におけるパケット転送処理を高速化、簡単化することができ、ネットワーク管理者およびユーザの利便性を向上させることができる。
【図面の簡単な説明】
【００６３】
【図１】本実施例のデータ検索装置の構成図。
【図２】ＩＰｖ４での境界値テーブルの例を示す図。
【図３】境界値が重なった場合の境界値テーブルの構成方法を示す図。
【図４】本実施例の境界値テーブルの大きさを２のべき乗個にした例を示す図。
【図５】本実施例のルーティングテーブルのエントリを昇順に並べたツリーを示す図。
【図６】図５のツリーを辿ることにより境界値テーブルが生成される過程を示す図。
【図７】本実施例のエントリ削除を説明するための図。
【図８】本実施例の冗長エントリを用いたエントリ削除を説明するための図。
【図９】本実施例の冗長エントリを用いたエントリ追加を説明するための図。
【図１０】ルーティングテーブルの一例を示す図。
【図１１】宛先アドレス空間を示す図。
【図１２】ルーティングテーブルと境界値テーブルとの関係を示す図。
【図１３】図１２の境界値テーブルを元にした２分探索(binary search)のツリーを示す図。
【図１４】ツリー検索手順を説明するための図。
【図１５】ツリー検索手順を説明するための図。
【符号の説明】
【００６４】
１  パケットフォワーディング部
２  テーブル作成部
３  テーブル格納部
【図１】
2005117211.tif 000003
【図２】
2005117211.tif 000004
【図３】
2005117211.tif 000005
【図４】
2005117211.tif 000006
【図５】
2005117211.tif 000007
【図６】
2005117211.tif 000008
【図７】
2005117211.tif 000009
【図８】
2005117211.tif 000010
【図９】
2005117211.tif 000011
【図１０】
2005117211.tif 000012
【図１１】
2005117211.tif 000013
【図１２】
2005117211.tif 000014
【図１３】
2005117211.tif 000015
【図１４】
2005117211.tif 000016
【図１５】
2005117211.tif 000017