(57)【要約】【課題】入力データとして与えられた検索キーにおいて、複数のデータ要素を格納しているデータベースから検索キーの最長接頭辞となるデータ要素をデータベース領域の少ない検索回数で見つけ、かつ、データ要素を格納するために要するデータベース領域を小さくする。【解決手段】データ要素を表すビット列を部分列に分割し、分割した部分列での連結関係をリスト構造により保持し、かつ、複数のデータ要素の接頭辞が同一である場合において共通のデータ領域に格納されている部分列の連なりによって、複数のデータ要素の接頭辞を集約するデータベース構造と検索キーをデータ要素を分割したときと同じ条件で分割し、検索キーの上位に位置する部分列を先に述べたデータベース構造で格納されたデータベースにおいて検索することにより、最長接頭辞検索に要するデータベース検索回数を少なく、かつ、データベースでの格納領域を小さくする。【選択図】図２
2004304495.tif 000002
【特許請求の範囲】
【請求項１】
ビット列で表現できるデータ要素を複数個、格納でき、アドレスを与えることで一意に決定されるデータベース領域に対するデータの読出し、および、書込みを可能とするデータベース構造において、１つのデータ要素を表すビット列を複数の部分列に分割し、データベースの複数の領域に格納し、かつ、１つのデータ要素を表す分割されたビット列において連続する２つの部分ビット列の間において、互いに格納されているデータベース領域のアドレスを参照できる機能を有するリスト構造を備え、かつ、異なるデータ要素のビット列の先頭からの部分ビット列である接頭辞が同一である場合に、同一のデータベース領域に格納した部分列の連なりをもって、複数のデータ要素の接頭辞を表すことを特徴としたデータベース構造。
【請求項２】
請求項１において、各データ要素を部分列に分割した後の元のデータ要素のビット列の最後のビットを含む最後の部分列においてのみ、該部分列が格納されているデータベース領域に誘導するためポインタ情報を備えたマーカーとなる部分列を格納することを特徴とする請求項１のデータベース構造。
【請求項３】
請求項２によるデータベース構造に従って格納されている複数のデータ要素から入力データとして与えられる検索キーに対して最も長いビット列長をもつ最長接頭辞を検索することを目的として、検索キーを部分列に分割し、検索キーの部分列において逐次的に検索キーの各部分列と同一の内容をもつデータ要素の部分列がメモリ上に存在するかどうかをデータベースをアクセスすることにより判定し、存在しないと判定された場合、または、検索キーと一致する接頭辞が検索された場合に検索を終了することを特徴とする請求項２のデータベース構造をもつデータベースでの最長接頭辞検索方法。
【請求項４】
請求項３において、入力された検索キーの最長接頭辞を高々、該検索キーのデータベースに属する最長接頭辞であるデータ要素のデータベース構造での格納ために生じた分割数、および、該データ要素のデータベースに格納されている最終部分列の長さの対数値の和に比例する回数のデータベース領域へのアクセスによって検索キーの最長接頭辞を検索する機能を特徴とした請求項４の最長接頭辞検索方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ビット列長の大きいデータ要素の集合から、与えられた検索キーの最長接頭辞検索を高速に行うものである。特に、ネットワークのルーティングにおけるＩＰｖ６プロトコルに対応可能なＩＰアドレスの最長接頭辞検索に関する。
【０００２】
【従来の技術】
従来の技術では、検索キーが３２ビットで表現される場合に対応する最長接頭辞検索において接頭辞の長さをＷビットとすると１つの接頭辞に対して約ｌｏｇ  Ｗ個のマーカーと呼ばれる補助情報を格納することにより高々ｌｏｇ  Ｗ回のハッシュ検索により検索キーの最長接頭辞検索を実現するＷａｌｄｖｏｇｅｌらの手法が存在する。また、専用ハードウェア化を行っているｃｏｎｔｅｎｔ−ａｄｄｒｅｓｓａｂｌｅ−ｍｅｍｏｒｙ（ＣＡＭ）と呼ばれる商用の高価なメモリを使用する方法（例えば、特許文献１参照）やハードウェアによってマスク処理を行う方法（例えば、特許文献２参照）が存在する。
【０００３】
【特許文献１】特開２０００−３２２８９２
【特許文献２】特開２００１−５２００６
【０００４】
【発明が解決しようとする課題】
以上に述べた従来技術では検索キー、および、データ要素のビット列長が高々３２ビットである場合に対応している。しかし、ＩＰｖ６プロトコル等に対応するＩＰルータでのルーティングテーブルの最長接頭辞検索では、１２８ビットのＩＰアドレス長への拡大に伴う検索時間の増大とともにルーティング可能パスの増加によるルーティングテーブルの増大も問題となる。したがって、ＩＰｖ６プロトコルに対応可能なＩＰルータでは、１２８ビット程度のビット長をもつ検索キー、および、データ要素において、高速に最長接頭辞を検索でき、かつ、データベースのサイズを小さく維持することが可能なデータ要素の格納が課題となっている。また、データ要素の格納、および、検索に算術演算を用いるハッシュ関数を使用する場合、データ要素を整数表現しなければならない。そこで、ＩＰｖ６アドレスにおける最長接頭辞検索では、大きなビット長をもつデータ要素を整数表現しなければならないという課題がある。
【０００５】
本発明は大きなビット長をもつデータ要素の整数表現の問題を解決し、検索キーに関する高速な最長接頭辞検索、および、データベースでの格納領域の縮小を実現することを目的とするものである。
【０００６】
【課題を解決するための手段】
本発明は上述したビット列長の長いデータ要素の整数表現の問題を解決するために、検索キーを整数表現が可能な長さとなるようにｘ個に分割して、その分割された検索キーの部分ビット列のそれぞれの長さにしたがってデータ要素も同様に高々ｘ個に分割して別々のハッシュテーブルへ格納し、分割され別々に格納された１つデータ要素はそれぞれポインタによって関係を保たせておくため、本来のデータ要素としての意味は失わずにデータ要素を格納することができるということを特徴とする。ｘ分割したデータ要素の上位ビットに１を加えることですべてのデータ要素を異なる整数として表現することができ、つまり、例えばデータ要素０とデータ要素００の整数表現を区別することが可能となり、ｘ個のハッシュテーブルにすべてのデータ要素を格納することができる。また、本発明により、分割したデータ要素に関係を保たせるポインタがマーカーと同じ働きになるため、ビット長Ｌの検索キーをｘ分割した中で最も長いビット長の部分をｄｍａｘとすると、１つのデータ要素を格納することに対して、マーカーの個数を高々約（ｌｏｇｄｍａｘ）個に縮小することが可能で、データ要素の数をｐとするとデータベースに格納されるデータ要素とマーカーの総数は高々約ｐ＋ｐ（ｌｏｇｄｍａｘ）個となるためデータベースの縮小が可能であるということを特徴とする。
【０００７】
検索キーの最長接頭辞の検索に関しては、データ要素をｘ分割してハッシュテーブルに格納した場合、１つのアドレスに対して分割された部分アドレスを上位ビット列より逐次的に高々（ｘ＋ｌｏｇｄｍａｘ）回のハッシュ検索で最長接頭辞を検索する。また、データベースの中の最長接頭辞が小さいほどこの最悪の場合のハッシュ検索回数を縮小することができることを特徴とする。上述したように、分割した接頭辞に関係を保たせるポインタがマーカーと同じ働きになるという特徴をもつため、段階的に検索を行うという接頭辞の検索に対してこの接頭辞格納手法は適している。
【０００８】
【発明の実施の形態】以下、本発明の実施の形態を図１、図２に基づいて説明する。図１は本発明におけるＬビット検索キーをｘ分割した場合の概要を図にしたものである。図１のようにＬビットの検索キーを整数表現が可能な長さｄ１ビット，ｄ２ビット，…，ｄｘビットにｘ分割する。
【０００９】
次にその検索キーの分割にしたがったデータ要素のデータベース格納構造について説明する。図２は図１のようにデータ要素を分割した場合のデータ要素の格納の概要を図にしたものである。図２のようにＬビット以下のｐビットの長さをもつデータ要素をデータベースに格納する場合、分割した検索キーの長さｄ１ビット，ｄ２ビット，…，ｄｘビットにしたがってデータ要素を上位ビットから分割する。それから、分割したデータ要素の各先頭ビットに１を付けて整数とみなすことで、すべての長さのデータ要素を区別することができ、１つのハッシュテーブルへまとめて格納することができる。そして別々に分けられてハッシュテーブルに格納された１つのデータ要素はポインタによって関係を保たせておく。検索方法に関しては、Ｌビットの検索キーＡに対する最長接頭辞を検索する場合、まずＡの上位ｄ１ビットを取り出して、上位に１を付けて整数に変換し、ｄ１ビット接頭辞に対応するハッシュテーブルを検索する。一致するものがあれば、そのセルが指すｄ２ビット接頭辞に対応するハッシュテーブルへのポインタに従い、そこでＡのｄ１＋１ビット目からｄ２ビット分だけ取り出し、同様に検索を行う。これを繰り返し一致するものがあればｄｘビットデータ要素まで同様の検索を行う。もしｄ１ビットデータ要素の検索で一致するものがなかった場合、それ以上長く一致するデータ要素はないため、ｄ１ビットデータ要素に対応するハッシュテーブルの中で最も長く一致するデータ要素を見つけるために２分探索を行う。
【００１０】
そこで、本実施形態の動作におけるデータ要素のデータベースでの格納方法について、具体例を用いて説明する。図３は１２ビットの検索キーに対して１０個のデータ要素を３ビットごとに４等分割して格納した場合の例である。まず図２のようにデータ要素を３ビットずつに４分割し、それぞれ上位ビットに１を加えて整数表現し、同じ構造ですべてのデータ要素を格納する。ここで、それぞれを整数にした場合、図のように同じ整数が表れる。これらはまとめて１つのデータ要素とし、元々のデータ要素の意味を失わないように図のようにポインタを使用してそれぞれ関係を保たせて格納する。
【００１１】
次に最長接頭辞検索方法に関して説明する。図３の一実施例において、検索キー０００１１１００００１１の最長接頭辞を検索する場合、はじめにハッシュテーブルＴａｂｌｅ１でデータ要素０００、つまり、１０００を整数表現した８を検索する。ここで、Ｔａｂｌｅ１で８が見つかったため、ポインタにしたがってＴａｂｌｅ２のＢのテーブルでデータ要素１１１、つまり、１１１１を整数表現した１５を検索し、１５を見つける。同様にそのポインタにしたがってＴａｂｌｅ３のＣのテーブルでデータ要素０００、つまり、１０００を整数表現した８を検索し、８があるのでＴａｂｌｅ４のＢでデータ要素０１１、つまり、１０１１を整数表現した１１を検索し、１１を見つけたため、この検索キーの最長接頭辞は０００１１１００００１１となる。また、検索キー  １０１０１１１００００１の最長接頭辞を検索する場合、Ｔａｂｌｅ１でデータ要素１０１、つまり、１１０１を整数表現した１３を検索し、Ｔａｂｌｅ１で１３を見つける。しかし、そこが指すポインタがないのでこれより長いデータ要素はないことになりこの検索キーの最長接頭辞は１０１となる。
【００１２】
【発明の効果】以上説明したように、本発明によれば、分割したデータ要素に関係を持たせるために使用するポインタがマーカーと同じ働きにもなるため、ビット長Ｌの検索キーをｘ分割した中で最も長いビット長の部分をｄｍａｘとすると、１つのデータ要素をデータベースに格納するのに対して使用するマーカーの個数を多くて約（ｌｏｇｄｍａｘ）個に削減することができる。データ要素の検索に関しては検索キーのビット列長をＬビットとし、検索キーをｘ分割したとすると多くて（ｌｏｇｄｍａｘ）＋ｘ回のハッシュ検索で行うことができる。また、データ要素を格納するデータベースの各セルの大きさは（ｄｍａｘ  ＋１）ビットであり、データ要素の数をｐとすると、データベースに格納されるデータ要素とマーカーの総数は多くて約ｐ＋ｐ（ｌｏｇｄｍａｘ）個となる。
【図面の簡単な説明】
【図１】本発明におけるＬビット検索キーをｘ分割した場合の概要図である。
【図２】図１のように検索キーを分割した場合のｐビットのデータ要素を格納する概要図である。
【図３】１２ビット検索キーを３ビットごとに４等分割して格納した場合の図である。
【図１】
2004304495.tif 000003
【図２】
2004304495.tif 000004
【図３】
2004304495.tif 000005