JP3570606B2 - データ検索装置および方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、データの検索技術に係わり、特に、通信網でのアドレス解決のように、新たなデータの発生に対応して古いデータの削除が必要となる大量のデータを扱うシステムにおけるデータの検索を効率的に行うのに好適なデータ検索装置および方法に関するものである。
【０００２】
【従来の技術】
一般に、インタネットにおけるＩＰアドレスの解決等では、与えられたＩＰアドレス等のデータ（数値）に対し、自装置内のテーブルの検索を行い、そのテーブルに所望のデータが登録されている場合は、対応するデータを取りだし、登録されていない場合には、他の装置に問い合わせてデータを取得することにより実行される。
【０００３】
このようにして他装置から得たデータは、一時的なテーブル（キャッシュテーブル）に登録され、以降の検索に用いられる。また、この一時的なテーブルに登録されたデータは、所定の基準により、ある時間の後に削除される。
一方、このようなデータを固定的なテーブルに半永久的に保持する場合もある。この場合、テーブルはＣＡＭ（Ｃｏｎｔｅｎｔｓ Ａｓｓｏｃｉａｔｉｏｎ ＭｅｍｏｒｙまたはＣｏｎｔｅｎｔ Ａｄｄｒｅｓｓａｂｌｅ Ｍｅｍｏｒｙ）と呼ばれる機構や、ツリー状のデータ構造によって実現される場合がある。特に、データが数値で２進整数の場合、パトリシアツリーと呼ばれるデータ構造を用いることがある。
【０００４】
このようなＩＰアドレスの解決のためなどに一時的なテーブルを構築する際に、一次元的なデータ構造を用いると、データ（数値）の追加や、記載された時刻が最も古いデータ（数値）の削除を高速に行うことができる。しかし、一次元的なデータ構造では、検索の効率が悪いため、大規模な検索テーブルの構築は困難である。
【０００５】
一方、固定的なテーブルに用いられるＣＡＭやツリー構造では、データ（数値）の追加、および、与えられたデータ（数値）の削除が容易で、また、検索も効率的である。しかし、登録された時刻が最も古い等の条件に合うデータ（数値）を探して削除する等の処理を行なうには、非常に多くの処理量を要する。このため、ＣＡＭやツリー構造を、一時的なテーブルに適用するのは現実的ではなかった。
【０００６】
【発明が解決しようとする課題】
解決しようとする問題点は、従来の技術では、データ検索の効率化と、削除および追加の対象となるデータの特定の効率化とを両立させることができない点である。
本発明の目的は、これら従来技術の課題を解決し、ＩＰアドレスの解決等、大規模な検索テーブルを要すると共に、検索テーブルを構成する要素の削除、追加が頻発する場合にも、効率的なデータの検索を行うことを可能とするデータ検索装置および方法を提供することである。
【０００７】
【課題を解決するための手段】
上記目的を達成するため、本発明のデータ検索装置および方法は、検索テーブルに加えて、一次元のデータ構造などを有する履歴管理テーブルを設け、この履歴管理テーブルを用いて、データの検索された順番を登録、更新して検索履歴を管理することにより、両者の組合せによる効率的なデータ検索を行う。このことにより、ＩＰアドレスの解決等、桁数の多い数値等の検索を高速に行なうことができ、かつ、検索テーブルに数値等の追加、削除を高速に行うことができる。
【０００８】
【発明の実施の形態】
以下、本発明の実施例を、図面により詳細に説明する。
図１は、本発明のデータ検索装置の本発明に係る構成の一実施例を示すブロック図であり、図２は、図１におけるデータ検索装置を用いたネットワークの構成例を示すブロック図である。
図２におけるネットワークは、リダイレクション機構２３ａ，２４ａと集線装置２３ｂ，２４ｂからなるアクセス網２３にハブ２１ｂ，２２ｂを介して接続されたユーザ網２１，２２内のホスト２１ａ，２２ａへ、コア網２５ｄ内のコアノード２５ｅによるインタネットワーキングサービスを提供するものであり、そのサービスを効率良く実現するためのシェル網２５におけるプラットフォーム上には、データ検索装置を具備したエッジノード（加入者収容ノード）２５ａ，２５ｂおよび代表フォワーダ２５ｃが設置されている。
【０００９】
通信初期のパケットは、エッジノード２５ａ，２５ｂによって代表フォワーダ２５ｃヘ転送し、２回目以降は、リダイレクション機構２３ａ，２４ａを用いて直接相手に転送（ショートカット転送）する。その際、エッジノード２５ａ，２５ｂの転送管理テーブルは、少数の固定エントリで到達性を確保する一方で、リダイレクション機構２３ａ，２４ａによるショートカット転送のためのキャッシュエントリ（一時的な登録情報）をホスト２１ａ，２２ａ単位に多数保有する。
【００１０】
ネットワーク全体で高いスループットを得るためには、エッジノード２５ａ，２５ｂの高速転送が可能で、かつ、代表フォワーダ２５ｃの負担軽減が必要である。そのためには、エッジノード２５ａ，２５ｂに、かなりの規模のアドレステーブル（キャッシュテーブル）を持つ必要がある。また、事前に多数のＥＮへのアドレス配布の防止、ユーザのエントリの変更、および、不使用時アドレスの削除などにも対処するために、動的な運用が必要となる。
【００１１】
大規模なキャッシュテーブルの検索の高速化には、通常の１次元テーブルの検索ではなく、ツリー検索やＣＡＭなどの利用が考えられるが、動的な運用に必要なエージング処理（データの書換え）は、ツリー検索、ＣＡＭ単独では効率的に行なうことはできない。
そこで、本例では、ツリー検索を行うデータ検索装置に、エージング処理用のテーブルを新たに付加することで、効率的なエージング処理を可能としている。
【００１２】
すなわち、ツリー状のデータ構造もしくはＣＡＭ構成等の検索テーブル内の各エントリに、エージング処理用の１次元のデータ構造のテーブル（履歴管理テーブル）へのリンクを張り、新規エントリの更新時等に履歴管理テーブルを参照することにより、効率的なエージング処理を可能としている。具体的には、あるエントリがヒットすると、リンク先の履歴管理テーブルの内容が更新される。また、エントリを更新する必要がある際には、履歴管理テーブルの内容を参照し、古いものから削除する。尚、この時、検索用テーブルの該当する内容も削除する。
【００１３】
以下、このようなデータ検索を行うデータ検索装置の構成とその動作を詳しく説明する。
図１に示す本例のデータ検索装置１は、ＩＰアドレスに対応するデータを検索するものであり、送受信部２、検索部３、パトリシアツリー構造の検索テーブル４、問合部５、テーブル制御部６、１次元のデータ構造の履歴管理テーブル７を有している。
【００１４】
送受信部２でＩＰアドレスを受信すると、検索部３は、このＩＰアドレスをキーに検索テーブル４から対応するデータを検索し、有ればそのデータを抽出して送受信部２を介して所定の宛先に送出する。
このようにしてＩＰアドレスに基づく検索が行われると、その検索履歴が、テーブル制御部６により、履歴管理テーブル７に登録される。テーブル制御部６は、新たな検索が行われる度に、最新の検索履歴として履歴管理テーブル７に登録すると共に、登録済みの検索履歴の登録順位付けを更新する。
【００１５】
また、ＩＰアドレスに基づく検索時、対応するデータが検索テーブル４に無ければ、問合部５により、他の装置にＩＰアドレスを渡して対応するデータを取得する。そして、このようにして他の装置から取得したデータを、テーブル制御部６により、ＩＰアドレスに対応付けて検索テーブル４に追加登録する。また同時に、テーブル制御部６は、最新の検索履歴としての履歴管理テーブル７への登録と他の検索履歴の順序付けの更新を行なう。
【００１６】
この時、検索テーブル４に、新たデータを追加登録する空き領域が無い場合には、テーブル制御部６は、履歴管理テーブル７を検索して、最も古い検索履歴を検出し、この最古の検索履歴のデータおよびＩＰアドレスの組からなるテーブルを構成する要素を検索テーブル４から削除し、この削除した後の空き領域に、他装置に問い合わせて取得したデータおよびＩＰアドレスの組からなる要素を追加登録する。
【００１７】
このように、本例のデータ検索装置１では、検索テーブルをパトリシアツリー構造としているので、ＩＰアドレスと対応するデータの組の追加や削除が容易で、検索も効率的に行うことができ、大規模な検索テーブルを構築できる。また、１次元のデータ構造を有する履歴管理テーブル７を用いて検索履歴を管理しているので、検索履歴の登録、更新が容易であり、削除対象のデータを効率的に検索することもできる。
次の図３および図４を用いて検索テーブル４と履歴管理テーブル７の構成を説明する。
【００１８】
図３は、図１における検索テーブルの構成例を示す説明図であり、図４は、図１における履歴管理テーブルの構成例を示す説明図である。
図３において、検索テーブル４を構成する各要素は、検索の対象となる数値（ＩＰアドレス等）、履歴管理テーブル上の対応する要素の位置を示すポインタ、検索結果として得られるデータ（またはそれの格納位置を示すポインタ）、ツリー上で隣接する上位のノードを示すポインタ、および、下位のノード（ここでは２つ）を示すポインタ（１，２）を持つ。
【００１９】
図４において、履歴管理テーブル７を構成する各要素は、検索の対象となる数値（ＩＰアドレス等）、正順に次の要素を示すポインタ、逆順に次の要素を示すポインタを持ち、さらに、履歴管理テーブル７には、履歴管理テーブル７上で最も昔に記載された要素を示すポインタと、履歴管理テーブル７上で最も新しく記載された要素を示すポインタが設けられている。
【００２０】
このような構成の検索テーブル４と履歴管理テーブル７を有するデータ検索装置に、検索対象の数値（ＩＰアドレス）が与えられた場合、次の３つの内のいずれか１つのケースとなる。
第１のケースは、検索テーブル上に該当する要素が無く、しかも、データ検索装置のデータ容量に余裕がある場合、第２のケースは、検索テーブルに該当する要素が無く、さらに、データ検索装置のデータ容量にも余裕が無い場合、そして、第３のケースは、検索テーブルに該当する要素がある場合である。
【００２１】
まず、第１のケースの動作を、図６を用いて説明する。
図６は、図１におけるデータ検索装置の第１のケースでの検索動作例を示す説明図である。
受信した数値（ＩＰアドレス）に基づき検索テーブルを検索した結果、検索テーブルに該当する要素が無い場合は、他の装置または機構へ問い合わせを行い、他装置／機構から対応するデータを、回答として受け取り、検索テーブルに追加する。
【００２２】
この時、この問い合わせた数値は、最新の要素として履歴管理テーブルの空き領域に新たに登録し、かつ、正順ポインタと逆順ポインタの設定の更新と、履歴管理テーブルの最新要素を示すポインタの更新を行う。
また、問い合わせの結果得られたデータと履歴管理テーブル上の位置の検索テーブルへの登録は、通常の検索テーブル操作の手順で行う。その具体的な操作は、検索テーブルの実現手段により異なり、ここでは説明しない。
【００２３】
次に、第２のケースの動作を、図７および図８を用いて説明する。
図７および図８は、図１におけるデータ検索装置の第２のケースでの検索動作例を示す説明図である。
受信した数値（ＩＰアドレス）に基づき検索テーブルを検索した結果、検索テーブルに該当する要素が無い場合は、まず、履歴管理テーブル上の最古の要素に記載されている数値を履歴管理テーブル上から消去し、空きを作り、かつ、最古の要素を示すポインタを、次ぎに古い要素を指すよう更新する。
【００２４】
そして、履歴管理テーブル上消去した最古の要素に対応して、検索テーブル上の最古の要素を削除した後、他装置への問い合わせを行う。
この問い合わせに対する他装置からの回答に基づき検索テーブルへの新たな要素の追加を行ない、さらに、履歴管理テーブルを更新する。すなわち、空きとなった領域に、新たな要素を最新の要素として登録し、この要素を指すように、最新の要素を示すポインタ、および、正順ポインタと逆順ポインタを更新する。
【００２５】
次に、第３のケースの動作を、図９を用いて説明する。
図９は、図１におけるデータ検索装置の第３のケースでの検索動作例を示す説明図である。
受信した数値（ＩＰアドレス）に該当する要素が検索テーブルにあるので検索した後、履歴管理テーブルの更新を行う。すなわち、検索した要素のポインタが示す履歴管理テーブル上の要素を、最新の要素として更新し、最新の要素を示すポインタを、この要素を指すよう更新し、さらに、正順ポインタと逆順ポインタの設定を更新する。
【００２６】
図５は、図１におけるデータ検索装置の本発明に係わる処理動作手順を示すフローチャートである。
ＩＰアドレスによるデータの検索要求が有れば（ステップ５０１）、検索テーブルを検索する（ステップ５０２）。要求されたデータが検索テーブル内に有れば（ステップ５０３）、図９で説明した手順で、データを抽出して送出し（ステップ５０４）、履歴管理テーブルを更新する（ステップ５０５）。
【００２７】
ステップ５０３において、要求されたデータが検索テーブル内に無ければ、この検索テーブルに新たなデータを追加登録する空き容量が有るか否かを判別する（ステップ５０６）。有れば、図６で説明した手順の通り、他の装置に問い合わせを行い（ステップ５０７）、該当するデータを取得し（ステップ５０８）、検索テーブルに追加登録する（ステップ５０９）。その後、ステップ５０４，５０５の処理を行う。
【００２８】
さらに、ステップ５０６において、検索テーブルに空き容量が無ければ、図７および図８で説明した手順に従い、履歴管理テーブルの最古の検索履歴情報（要素）の削除（ステップ５１０）と検索テーブルの対応するデータ（要素）の削除（ステップ５１１）を行う。そして、その後、ステップ５０７〜５０９，５０４，５０５の処理を行う。
【００２９】
以上、図１〜図９を用いて説明したように、本実施例のデータ検索装置および方法では、パトリシアツリー構造等の検索テーブルに加えて、一次元のデータ構造を有する履歴管理テーブルを設け、この履歴管理テーブルを用いて、データの検索された履歴を登録、更新して管理することにより、両者の組合せによる効率的なデータ検索を行う。
【００３０】
このことにより、ＩＰアドレスの解決等、各要素に何らかのデータが対応する桁数の多い数値の集合に対しても、検索を高速に行なうことができ、かつ、検索テーブルに数値の追加、削除を高速に行うことができる。そして、大規模で高速なデータ検索装置が構成できるので、通信網のＩＰアドレス検索を行う際に、他装置へのＩＰアドレスの問い合わせが必要となる確率が下がり、通信網を効率化することができる。
【００３１】
尚、本発明は、図１〜図９を用いて説明した実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、ＩＰアドレス等の数値に基づくデータ検索を例として説明したが、文字によるデータ検索等、数値に限定されることなく、適用することができる。また、履歴管理テーブルに１次元のデータ構造のものを用いたが、ツリー構造のものでも良い。さらに、検索テーブルに関してもパトリシアツリー構造に限定されない。
【００３２】
【発明の効果】
本発明によれば、データ検索の効率化と、削除および追加の対象となるデータの特定の効率化とを両立させることができ、ＩＰアドレスの解決等、大規模な検索テーブルを要すると共に、検索テーブルを構成する要素の削除、追加が頻発する場合にも、効率的なデータの検索を行うことが可能である。
【図面の簡単な説明】
【図１】本発明のデータ検索装置の本発明に係る構成の一実施例を示すブロック図である。
【図２】図１におけるデータ検索装置を用いたネットワークの構成例を示すブロック図である。
【図３】図１における検索テーブルの構成例を示す説明図である。
【図４】図１における履歴管理テーブルの構成例を示す説明図である。
【図５】図１におけるデータ検索装置の本発明に係わる処理動作手順を示すフローチャートである。
【図６】図１におけるデータ検索装置の第１のケースでの検索動作例を示す説明図である。
【図７】図１におけるデータ検索装置の第２のケースでの検索動作例の１／２部分を示す説明図である。
【図８】図１におけるデータ検索装置の第２のケースでの検索動作例の２／２部分を示す説明図である。
【図９】図１におけるデータ検索装置の第３のケースでの検索動作例を示す説明図である。
【符号の説明】
１：データ検索装置、２：送受信部、３：検索部、４：検索テーブル、５：問合部、６：テーブル制御部、７：履歴管理テーブル、２１，２２：ユーザ網、２１ａ，２２ａ：ホスト、２１ｂ，２２ｂ：ハブ、２３：アクセス網、２３ａ，２４ａ：リダイレクション機構、２３ｂ，２４ｂ：集線装置、２５：シェル網、２５ａ，２５ｂ：エッジノード（加入者収容ノード）、２５ｃ：代表フォワーダ、２５ｄ：コア網、２５ｅ：コアノード。

Claims (2)

1. 第１のデータに基づき、該第１のデータに予め応付けられた第２のデータを検索し、検索対象の上記第１のデータと上記第２のデータの組が検索テーブルに登録されていない場合、他装置に問い合わせて取得し上記検索テーブルに追加登録するデータ検索装置において、
   上記第１のデータに基づく検索履歴の登録および更新を、上記検索テーブルとは別に新たに付加した履歴管理テーブルを用いて行う第１の手段と、
   上記他装置に問い合わせて検索する第１，第２のデータを追加登録する空き領域が上記検索テーブルに無い場合、上記履歴管理テーブルの検索履歴を参照して最古の検索履歴を検出し、検出した最古の検索履歴に対応する第１，第２のデータの組を上記検索テーブルから削除し、該削除した後の空き領域に、上記他装置に問い合わせて検索した第１，第２のデータを追加登録する第２の手段とを有し、
   さらに、上記履歴管理テーブルは、１次元のデータ構造で上記第１のデータおよび正順で次の要素を指す正順ポインタと逆順で次の要素を指す逆順ポインタからなる要素を有し、上記検索テーブルは、ＣＡＭもしくはツリー状のデータ構造で上記第１，第２のデータの組および上記履歴管理テーブルの要素へのポインタからなる要素を有し、
   上記履歴管理テーブルには該履歴管理テーブル内の最新の要素を指す第１のポインタと最古の要素を指す第２のポインタを設け、
   上記第２の手段は、該第２のポインタに基づき、上記履歴管理テーブルの最古の要素に対応する上記検索テーブル上の第１，第２のデータからなる要素を特定して削除し、
   上記第１の手段は、上記第２の手段が上記検索テーブルから削除した最古の要素を上記履歴管理テーブルから削除すると共に該最古の要素の次に古い要素を指すよう上記第２のポインタを更新し、かつ上記検索テーブルで検索されたもしくは上記検索テーブルに追加登録された第１のデータを含む要素を新たな最新の要素として上記履歴管理テーブルに登録し、該要素を指すよう上記第１のポインタおよび正順ポインタと逆順ポインタを更新
   することを特徴とするデータ検索装置。
2. 第１のデータに基づき、該第１のデータに予め対応付けられた第２のデータの検索を行い、検索対象の上記第１のデータと上記第２のデータの組が検索テーブルに登録されていない場合、他装置に問い合わせて取得し上記検索テーブルに追加登録するデータ検索装置のデータ検索方法であって、
   上記検索テーブルはＣＡＭもしくはツリー状のデータ構造からなり、
   上記第１のデータに基づく検索の履歴を、該検索テーブルとは別に新たに付加された１次元のデータ構造の履歴管理テーブルを用いて登録および更新するステップと、
   上記他装置に問い合わせて検索する第１，第２のデータを追加登録する空き領域の上記検索テーブルにおける有無を判別するステップと、
   有れば、上記他装置に問い合わせて上記第２のデータを取得して上記検索テーブルへの追加登録を行い、最新の検索履歴として上記履歴管理テーブルに登録し、他の検索履歴の順位を順次繰り下げて更新するステップと、
   無ければ、上記履歴管理テーブルにおける最古の検索履歴を検出し、検出した最古の検索履歴に対応する第１，第２のデータの組を上記検索テーブルから削除した後、上記他装置に問い合わせを行なうステップと、
   上記他装置に問い合わせて取得した第１，第２のデータを、上記削除した後の空き領域に追加登録し、最新の検索履歴として上記履歴管理テーブルに登録し、他の検索履歴の順位を順次繰り下げて更新するステップとを有することを特徴とするデータ検索方法。

Images