(57)【要約】  格納に必要なメモリの増大を抑えつつ、目的とするデータを高速に検索するデータ検索装置を提供するため、データ検索装置１０１において、第１のデータ２７１ｂと、この第１のデータに対する第２のデータ２７１ｃとの組２７１が格納される、この組２７１の第１のデータ２７１ｂが変換されるキーデータと同一のキーデータに変換される別の第１のデータ２７２ｂを有する別の組２７２の格納場所を示すインデクス２７１ａもこの組に付属して格納される組格納部２２０と、組格納部の先頭の組２７１の格納場所を取得し、この格納場所に格納されている組２７１が有する第１のデータ２７１ｂを比較する検索部２１１と、比較の結果、非同一であった場合には、格納場所を取得した組を、その組を先頭にして並んだ列の末尾に移し、検索部に比較をやり直させる列変更部２３０とを備えた。
2009063545.tif 000002
【特許請求の範囲】
【請求項１】
所定数の値のうちのいずれかの値を取り得る第１のデータが供給され、該第１のデータを、該所定数よりも少ない数の値のうちいずれかの値を取り得るキーデータに所定の変換関係で変換するデータ変換部と、
前記第１のデータと、該第１のデータに対する第２のデータとの組が格納される、該組の第１のデータが変換されるキーデータと同一のキーデータに変換される別の第１のデータを有する別の組の格納場所を示すインデクスも該組に付属して格納される組格納部と、
互いに同一のキーデータに変換される複数の第１のデータそれぞれを有する複数の組のうち、前記インデクスによって順番付けられてなる列の先頭の組の格納場所が該キーデータの値順に配列されて記憶される格納場所記憶部と、
前記データ変換部によって変換されたキーデータに基づいて前記格納場所記憶部を検索することで前記先頭の組の格納場所を取得し、該格納場所に格納されている組が有する第１のデータと、該キーデータへの変換に用いられた第１のデータとを比較する検索部と、
前記検索部による比較の結果、第１のデータが同一であった場合には、該第１のデータを有する組の第２のデータを取得する取得部と、
前記検索部による比較の結果、第１のデータが非同一であった場合には、前記検索部が格納場所を取得した組を、前記インデクスと前記格納場所記憶部に記憶された格納場所とを書き換えることで、その組を先頭にして並んだ列の末尾に移し、前記検索部に、前記格納場所記憶部の検索と前記第１のデータの比較とをやり直させる列変更部とを備えたことを特徴とするデータ検索装置。
【請求項２】
前記格納場所記憶部は、前記列の先頭の組の格納場所に付随して該列の末尾の組の格納場所も記憶されたものであり、
前記列変更部は、前記第１のデータが非同一であった場合には、前記格納場所記憶部に記憶された該列の末尾の組の格納場所を取得し、該格納場所に格納されている組が有するインデクスを書き換えることで、前記検索部が格納場所を取得した組を、該列の末尾に移すものであることを特徴とする請求項１記載のデータ検索装置。
【請求項３】
ＩＰパケットが供給されるＩＰパケット供給部と、
供給されたＩＰパケットを複数のポートのうちのいずれかのポートから出力するＩＰパケット出力部とをさらに備え、
前記データ変換部は、前記ＩＰパケット供給部に供給されたＩＰパケットに含まれたＩＰアドレスを前記第１のデータとしてキーデータに変換するものであり、
前記組格納部は、前記第２のデータとして、前記ＩＰパケット出力部が前記ＩＰパケット供給部に供給されたＩＰパケットを出力するポートを表したデータが格納されたものであることを特徴とする請求項１または２記載のデータ検索装置。
【請求項４】
前記データ変換部が、ＩＰアドレスを構成するホスト部およびネットワーク部のうち、該ネットワーク部をマスクする過程を経て前記キーデータに変換するものであることを特徴とする請求項３記載のデータ検索装置。
【請求項５】
前記ＩＰパケットは、該ＩＰパケットのＩＰアドレスに対応した優先度を含むものであり
前記列変更部は、前記組格納部に格納された組のうち、所定の基準レベルより高い優先度が対応したＩＰアドレスを有する組を、その組を含めて並んだ列の先頭に移すものであることを特徴とする請求項３または４記載のデータ検索装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ検索装置に関する。
【背景技術】
【０００２】
互いに対応付けられたデータの組が多数記憶されており、供給された一方のデータに対応する他方のデータを検索する検索装置が知られている。例えば、複数の入出力ポートを通じてＩＰパケットを送受信するＩＰネットワーク伝送装置は、外部から一つの入出力ポートを通じて受信したＩＰパケットを、このＩＰパケットが有する宛先ＩＰアドレスに応じた別の入出力ポートから送信するため、宛先ＩＰアドレスを用いた検索処理を行っている。【０００３】
図１は、ＩＰネットワーク伝送装置が含まれたネットワークの概略を示す図である。【０００４】
図１に示すネットワーク８００では、情報端末８７０，８８０がアクセスポイント装置８５０，８６０を介し、ＩＰネットワーク伝送装置としてのアクセスルータ８１０と接続されている。アクセスルータ８１０は、さらにインターネット８２０を介してコンテンツサーバ８３０やＳＩＰ（Ｓｅｓｓｉｏｎ  Ｉｎｉｔｉａｔｉｏｎ  Ｐｒｏｔｏｃｏｌ）サーバ８４０といった情報提供サーバと接続されている。アクセスルータ８１０は、情報端末８７０，８８０、および情報提供サーバ８３０，８４０の間でＩＰパケットの中継を行っており、供給されてくるＩＰパケットに含まれた宛先ＩＰアドレスから、適切なポートを選択してＩＰパケットを出力する。アクセスルータ８１０は、ＩＰパケットをイーサネット（登録商標）フレームの形式で送受信しており、ＩＰパケットをイーサネット（登録商標）フレームの形式で送信する際に、ＩＰパケットに含まれた宛先ＩＰアドレスに応じたＭＡＣアドレスをイーサネット（登録商標）フレームのヘッダに挿入する。【０００５】
図２は、ＩＰパケットに含まれるヘッダの構成を示す図である。【０００６】
ＩＰのプロトコルとしては、ＩＰｖ４（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｖｅｒｓｉｏｎ  ４）とＩＰｖ６（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  ｖｅｒｓｉｏｎ  ６）の２つのバージョンが利用されている。図２のパート（Ａ）には、ＩＰｖ４におけるヘッダの構成が示されており、パート（Ｂ）には、ＩＰｖ６におけるヘッダの構成が示されている。【０００７】
ＩＰｖ４およびＩＰｖ６の双方とも、ヘッダの末尾に宛先アドレス（Ｄｅｓｔｉｎａｔｉｏｎ  Ａｄｄｒｅｓｓ）としてＩＰアドレスが配置されている。ＩＰアドレスの大きさは、ＩＰｖ４で３２ビットであり、ＩＰｖ６で１２８ビットである。また、ヘッダには、ＩＰパケットの優先度を表すＴｙｐｅ  ｏｆ  Ｓｅｒｖｉｃｅ（ＴｏＳ）も含まれている。ＴｏＳはＩＰアドレスに対応して設定されており、同一の宛先ＩＰアドレスを有する複数のＩＰパケットには同一のＴｏＳが設定されている。【０００８】
図３は、ＩＰアドレスの構成を示す図である。図３のパート（Ａ）にはＩＰｖ４におけるＩＰアドレスの構成が示されており、パート（Ｂ）にはＩＰｖ６におけるＩＰアドレスの構成が示されている。ＩＰｖ４におけるＩＰアドレスは３２ビットであり、３種類の形式がある。クラスＡではＩＰアドレスが、ネットワークを識別する８ビットのネットワーク部と、一のネットワーク内のホストを識別する２４ビットのホスト部とからなる。クラスＢでは、ＩＰアドレスが１６ビットのネットワーク部と１６ビットのホスト部とからなり、クラスＣでは、ＩＰアドレスが２４ビットのネットワーク部と８ビットのホスト部とからなる。ＩＰｖ６では、１２８ビットのＩＰアドレスが、６４ビットのネットワーク部と６４ビットのホスト部とからなる。【０００９】
ＩＰネットワーク装置における宛先ＩＰアドレスの検索としては、ＣＡＭ（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｍｅｍｏｒｙ）を用いたハードウェアによる方法が、最も高速な検索方法として知られている。しかし、ＣＡＭは格納内容に対し検索を並列に行うため、検索用の入力データとメモリ内のデータとを比較する回路がビットごとに必要となり、また比較結果を全部まとめて処理する回路も必要である。このため、検索可能なデータの数が増加するとＣＡＭの回路が肥大化し、装置のコストが増大してしまう。現状では、ＣＡＭの利用は、特に高速検索が必要とされる大規模な装置に限定されている。【００１０】
中小規模のＩＰネットワーク装置では、コストを抑えるためソフトウェアによる検索処理が行われている。例えば、このような検索処理として、検索対象の情報と組でメモリに格納されたＩＰアドレスを、２分木検索によって検索する手法が知られている（例えば、特許文献１参照。）。【００１１】
また、ソフトウェアによるより高速な検索方法として、ハッシュ法を用いた高速検索アルゴリズムも広く用いられている。ハッシュ法による検索は、検索対象データをハッシュ関数の演算によってハッシュ値に変換し、このハッシュ値に応じた位置に検索対象データが格納された検索テーブルを作成しておく。そして検索時には、供給されたデータをハッシュ値に変換し、このハッシュ値をインデクスとして用い、検索対象データを検索テーブルからダイレクトに読み出す。ハッシュ法は冗長な比較判定処理を極力抑えつつ、目的とするデータを見つけ出す方法であり、ソフトウェアによる高速な検索に広く用いられている。
【特許文献１】特開平１０−２２２５３５号公報
【００１２】
ハッシュ法に用いられる代表的なハッシュ関数としては、ＭＤ５関数やＳＨＡ１関数が規定されている。ＭＤ５関数は１２８ｂｉｔのビット幅のハッシュ値が得られ、ＳＨＡ１関数では１６０ｂｉｔのビット幅のハッシュ値が得られる。得られたハッシュ値を検索テーブルのインデクスとしてそのまま用いようとすると、検索対象データの配列構造である検索テーブルのメモリ空間が膨大となり、実装が困難となる。そこで実際には、変換で得られたハッシュ値は、マスク演算やモジュロ演算を施し、ビットの切捨てによる数値の丸め込みを実施してからインデクスとして使用する。この場合、ハッシュ値を丸め込むが故に、同一インデクスに対して複数の検索対象データが重複することが避けられない。検索データの重複を処理するため、空き番地法や分離連鎖法と呼ばれる手法が用いられる。【００１３】
空き番地法は、あるインデクスの値に対し対応する検索対象データが複数ある場合、一方の検索対象データを、検索テーブル内のこのインデクスに対応するエリアの次の空きエリアに格納する方法である。この方法では、読み出しごとに格納されたデータの比較確認を行う必要があり検索効率が低下する。さらに、ある範囲のインデクスに多数の検索対象データが重複競合して対応する場合には、検索対象データが格納される場所がインデクスで表される場所から隔たるとともに配置が複雑となり、配置効率が著しく低下する。一方の分離連鎖法は、検索テーブルにおける競合が発生したエリアで、検索対象データを連鎖リストとして管理するので、空き番地法のような検索テーブルの配置効率低下の欠点を解消できるが、連鎖リストで管理された検索対象データの比較確認を読み出しごとに行うことには変わりない。検索効率を高める方法として、インデクスのビット幅を大きく確保して、１つの値に対応する検索対象データの数を減少させる方法があるが、この場合には、検索テーブルが増大する。【００１４】
また、ハッシュ関数で得られたハッシュ値をインデクスに変換するときに、ビットの切捨て等により丸め込みを実施すると、インデクスの値に対応する検索対象データの数に偏りが生じやすくなる。インデクスの値によっては多数の検索データを比較確認するため、検索時間が長時間に亘る場合が生じ、また、検索データによって検索時間に偏りが生じる。【００１５】
本発明は、格納に必要なメモリの増大を抑えつつ、目的とするデータを高速に検索するデータ検索装置を提供することを目的とする。
【発明の開示】
【００１６】
上記目的を達成する本発明のデータ検索装置は、所定数の値のうちのいずれかの値を取り得る第１のデータが供給され、この第１のデータを、この所定数よりも少ない数の値のうちいずれかの値を取り得るキーデータに所定の変換関係で変換するデータ変換部と、
上記第１のデータと、この第１のデータに対する第２のデータとの組が格納される、この組の第１のデータが変換されるキーデータと同一のキーデータに変換される別の第１のデータを有する別の組の格納場所を示すインデクスもこの組に付属して格納される組格納部と、
互いに同一のキーデータに変換される複数の第１のデータそれぞれを有する複数の組のうち、上記インデクスによって順番付けられてなる列の先頭の組の格納場所がこのキーデータの値順に配列されて記憶される格納場所記憶部と、
上記データ変換部によって変換されたキーデータに基づいて上記格納場所記憶部を検索することで上記先頭の組の格納場所を取得し、この格納場所に格納されている組が有する第１のデータと、このキーデータへの変換に用いられた第１のデータとを比較する検索部と、
上記検索部による比較の結果、第１のデータが同一であった場合には、この第１のデータを有する組の第２のデータを取得する取得部と、
上記検索部による比較の結果、第１のデータが非同一であった場合には、上記検索部が格納場所を取得した組を、上記インデクスと上記格納場所記憶部に記憶された格納場所とを書き換えることで、その組を先頭にして並んだ列の末尾に移し、上記検索部に、上記格納場所記憶部の検索と上記第１のデータの比較とをやり直させる列変更部とを備えたことを特徴とする。
【００１７】
このデータ検索装置では、第１のデータと第２のデータを有する組は、第１のデータが変換されたキーデータの値が互いに同一のもの同士で列を構成し、格納場所記憶部には、列の先頭の組の格納場所がキーデータの値順に配列されている。キーデータは、供給される第１のデータよりも取り得る数が少ないので、例えば、取り得る値の数が多い第１のデータの値順に配列された場合に比べ、格納場所記憶部の容量が小さくてすむ。また、１つのキーデータの値には、１つの列を構成する複数の組が対応するが、比較の結果、第１のデータが非同一であった場合には、格納場所が取得した組が列の末尾に移される。この結果、第１のデータが同一となった組が列の先頭に配置されることとなる。このため、同一となった第１のデータが、次回供給された場合には、比較が１回で完了するため検索時間が短縮する。
【００１８】
ここで、上記本発明のデータ検索装置において、上記格納場所記憶部は、上記列の先頭の組の格納場所に付随してこの列の末尾の組の格納場所も記憶されたものであり、
上記列変更部は、上記第１のデータが非同一であった場合には、上記格納場所記憶部に記憶されたこの列の末尾の組の格納場所を取得し、この格納場所に格納されている組が有するインデクスを書き換えることで、上記検索部が格納場所を取得した組を、この列の末尾に移すものであることが好ましい。
【００１９】
格納場所記憶部に列の末尾の組の格納場所が記憶されていることにより、第１のデータが非同一で、列の末尾の組を探す場合に、列の先頭から末尾までインデクスを順次たどる必要が無いため、検索時間がより短縮する。
【００２０】
また、上記本発明のデータ検索装置において、ＩＰパケットが供給されるＩＰパケット供給部と、
供給されたＩＰパケットを複数のポートのうちのいずれかのポートから出力するＩＰパケット出力部とをさらに備え、
上記データ変換部は、上記ＩＰパケット供給部に供給されたＩＰパケットに含まれたＩＰアドレスが上記第１のデータとしてキーデータに変換するものであり、
上記組格納部は、上記第２のデータとして、上記ＩＰパケット出力部が上記ＩＰパケット供給部に供給されたＩＰパケットを出力するポートを表したデータが格納されたものであることが好ましい。
【００２１】
このデータ検索装置は、ＩＰパケットに含まれたＩＰアドレスから、このＩＰパケットを出力するポートを決定する、例えばＩＰルータ等のＩＰネットワーク伝送装置に好適である。
【００２２】
また、上記本発明のデータ検索装置において、上記データ変換部が、上記ＩＰアドレスを構成するホスト部およびネットワーク部のうち、このネットワーク部をマスクする過程を経て上記キーデータに変換するものであることが好ましい。
【００２３】
例えば、ＩＰネットワーク伝送装置に供給されてくるＩＰパケットのＩＰアドレスのうち、互いに異なる値を持つ複数のＩＰアドレス同士については、ホスト部の値が同一である確立よりもネットワーク部の値が同一である確率が低い。したがって、データ変換部では、第１のデータとしてのＩＰアドレスのうちネットワーク部をマスクすることで、キーデータの値が取り得る数を減少させつつ、同一のキーデータの値に複数のＩＰアドレスが重複して対応する確率を減少させることができる。また、第１のデータの一部をマスクすることによって、例えばハッシュ関数の演算によらず、簡単な構成で短時間にキーデータを生成することができる。
【００２４】
また、上記本発明のデータ検索装置において、上記組格納部は、ＩＰアドレスに対するＩＰパケットの優先度も上記組に付随して格納されるものであり、
上記列変更部が、上記組格納部に格納された組のうち、所定の基準レベルより高い優先度が付随した組を、その組を含めて並んだ列の先頭に移すものであることが好ましい。
【００２５】
供給されてくるＩＰパケットの中には、例えば遅延の許容度が低い音声情報のように、高い優先度で伝送を行う必要のあるものがある。ＩＰパケットの優先度を表す優先度をデータの組に格納するとともに、高い優先度が付随した組を列の先頭に移すことによって、優先度の高いＩＰパケットについては、検索をより高速に行うことができる。
【００２６】
以上説明したように、本発明によれば、格納に必要なメモリの増大を抑えつつ、目的とするデータを高速に検索するデータ検索装置が実現する。
【図面の簡単な説明】
【００２７】
【図１】ＩＰネットワーク伝送装置が含まれたネットワークの概略を示す図である。
【図２】ＩＰパケットに含まれるヘッダの構成を示す図である。
【図３】ＩＰアドレスの構成を示す図である
【図４】本発明のデータ検索装置の一実施形態であるＩＰネットワーク伝送装置を示すブロック図である。
【図５】図４に示すデータ検索処理部、検索テーブル、キュー管理部、および検索データ管理部をより詳細に示すブロック図である。
【図６】ＩＰアドレス変換部２１２による宛先ＩＰアドレスの変換を説明する図である。
【図７】図５に示す検索管理テーブルおよびバッファキューのデータ構造を説明する図である。
【図８】ルーチングデータの登録および削除の処理を示すフローチャートである。
【図９】ルーチングデータの検索処理を示すフローチャートである。
【図１０】キューの繋ぎ換え処理を示すフローチャートである。
【図１１】キューの切断処理を示すフローチャートである。
【図１２】キューの切断処理における検索管理テーブルおよびバッファキューのデータ構造の一例を説明する図である。
【図１３】キューの接続処理を示すフローチャートである
【図１４】キューの接続処理における検索管理テーブルおよびバッファキューのデータ構造の一例を説明する図である。
【図１５】ハッシュ関数による検索キーの値が同一となる宛先ＩＰアドレスの数を、検索キーの値ごとに示したグラフである。
【図１６】ハッシュ関数による検索キーの値が同一となる図１５とは別の範囲の宛先ＩＰアドレスの数を、検索キーの値ごとに示したグラフである。
【図１７】本実施形態のＩＰアドレス変換部と同一の変換による検索キーの値が同一となる宛先ＩＰアドレスの数を、検索キーの値ごとに示したグラフである。
【発明を実施するための最良の形態】
【００２８】
以下図面を参照して本発明の実施形態について説明する。【００２９】
図４は、本発明のデータ検索装置の一実施形態であるＩＰネットワーク伝送装置を示すブロック図である。【００３０】
図４に示すＩＰネットワーク伝送装置１０１は、ＩＰパケット通信機器１００とともにＩＰネットワーク１０を形成している。【００３１】
ＩＰパケット通信機器１００は、ＩＰネットワーク伝送装置１０１の対向通信機器であり、具体的には、各種のＩＰ通信端末、及び、ルータやゲートウェイ装置等によって構成されている。ＩＰネットワーク伝送装置１０１には、複数のＩＰパケット通信機器１００が通信可能に接続されるが、図１では、ＩＰパケット通信機器１００を１つだけ示している。ＩＰネットワーク伝送装置１０１は、複数のＩＰパケット通信機器１００の間で、通信情報としてのＩＰパケットを中継するＩＰルータとして機能する。より詳細には、ＩＰネットワーク伝送装置１０１は、複数の入出力ポートにそれぞれ接続された複数のＩＰパケット通信機器１００からＩＰパケットの供給を受け、供給されたＩＰパケットに含まれた宛先ＩＰアドレスを読み出し、ＩＰネットワーク伝送装置１０１が有している経路情報を参照して、複数の入出力ポートのうちの宛先ＩＰアドレスに応じた入出力ポートから別のＩＰパケット通信機器１００に送信する。ＩＰパケットは、イーサネット（登録商標）フレーム形式で受送信されている。ＩＰネットワーク伝送装置１０１は、イーサネット（登録商標）フレーム形式でＩＰパケットを送信する際に、上記の経路情報を参照して、宛先ＩＰアドレスに応じたＭＡＣアドレスをイーサネット（登録商標）フレームのヘッダに挿入する。【００３２】
ＩＰネットワーク伝送装置１０１は、パケット受信部２００、データ検索処理部２１０、検索テーブル２２０、キュー管理部２３０、ルート選択部２４０、ルーチングデータ管理部３００、ルーチングデータテーブル３１０、および、検索データ管理部３２０を有している。【００３３】
パケット受信部２００は、ＩＰパケット通信機器１００より送信されるＩＰパケットを受信する。ＩＰパケットは、イーサネット（登録商標）フレームの形式で送信されてくる。パケット受信部２００は、イーサネット（登録商標）フレームからのＩＰパケットを取出し、データ検索処理部２１０に送信する。【００３４】
データ検索処理部２１０は、パケット受信部２００より送信されてきたパケットデータ中のＩＰヘッダから宛先ＩＰアドレスを読み出すとともに、検索テーブル２２０を参照して宛先ＩＰアドレスに対応するルーチング情報を読み出し、読み出したルーチング情報およびＩＰパケットをルート選択部２４０に送信する。データ検索処理部２１０は、パケットデータ中のＩＰヘッダ（図４参照）から、ＩＰパケットの優先度を表すＴｏＳも値を読み出してキュー管理部２３０に送信する。また、データ検索処理部２１０は、キュー管理部２３０に、検索テーブル２２０に格納されたデータの更新も行わせる。更新の詳細については後述する。【００３５】
ルート選択部２４０は、ルーチングデータテーブル３１０を参照して、データ検索処理部２１０から送信されたルーチング情報に対応した送信パラメータを読み出し、パケット送信部２５０に送信する。送信パラメータには、ポート番号およびＭＡＣアドレスが含まれている。【００３６】
パケット送信部２５０は、ルート選択部２４０より供給されたＩＰパケット及び送信パラメータから、ＩＰパケットを含んだイーサネット（登録商標）フレーム形式のデータを作成し、ポート番号に対応した入出力ポートからＩＰパケット通信機器１００に向けて送信を行う。パケット受信部２００に供給されてきたＩＰパケットは、上述したデータ検索処理部２１０、ルート選択部２４０、パケット送信部２５０を経由して出力される。【００３７】
ルーチングデータテーブル３１０には、宛先ＩＰアドレスに対応した送信パラメータが格納されている。ただし、ルーチングデータテーブル３１０には、宛先ＩＰアドレスは格納されておらず、ポート番号およびＭＡＣアドレスを含む送信パラメータのみが格納されている。送信パラメータは、ルーチングデータ管理部３００によって格納される。【００３８】
ルーチングデータ管理部３００は、ルーチングデータテーブル３１０の所定のメモリアドレスに、宛先ＩＰアドレスに対応した送信パラメータを書き込む。送信パラメータは、ＩＰパケットを送信すべき出力ポートを識別するポート番号、および、ＩＰパケットを送信する相手となるＩＰパケット通信機器１００のＭＡＣアドレスを含んでいる。宛先ＩＰアドレスと送信パラメータとの組み合わせは経路情報に基づいて決定される。経路情報は、ＩＰネットワーク１０内におけるＩＰパケット通信機器１００との通信の解析結果や、ＩＰパケット通信機器１００から供給された情報に基づいて生成される。ルーチングデータ管理部３００は、宛先ＩＰアドレスに応じた送信パラメータをルーチングデータテーブル３１０に例えば登録の順に配列して格納するとともに、格納したメモリアドレスと宛先ＩＰアドレスを検索データ管理部３２０に送信する。宛先ＩＰアドレスとメモリアドレスとの関係は検索テーブル２２０に記憶され、データ検索処理部２１０によって読み出されることとなる。【００３９】
検索テーブル２２０は、データ検索処理部２１０より参照されるテーブルであり、宛先ＩＰアドレスとルーチング情報を保持している。検索テーブル２２０の宛先ＩＰアドレスとメモリアドレスは、検索データ管理部３２０およびキュー管理部２３０によって登録及び削除が行われる。【００４０】
検索データ管理部３２０は、検索テーブル２２０に対するデータの登録および削除を管理する。検索データ管理部３２０は、キュー管理部２３０を制御し、ルーチングデータ管理部３００から送信されてきた宛先ＩＰアドレスとルーチング情報とを対応付けて検索テーブル２２０に格納させる。【００４１】
キュー管理部２３０は、データ検索処理部２１０の制御によって検索テーブル２２０に格納されたデータの並び替え、および、検索テーブル２２０の登録・削除を行う。また、キュー管理部２３０は、データ検索処理部２１０から送信されてきたＴｏＳが基準レベルよりも高い場合に、ＴｏＳと宛先ＩＰアドレスおよびＩＰパケットのパケット受信時刻を対応付けて検索テーブル２２０に記憶する。【００４２】
パケット受信部２００が本発明にいうＩＰパケット供給部の一例に相当し、パケット送信部２５０が本発明にいうＩＰパケット出力部の一例に相当する。【００４３】
ＩＰネットワーク伝送装置１０１内でのデータの基本的な流れを説明する。【００４４】
ルーチングデータ管理部３００は、宛先ＩＰアドレスと送信パラメータとを対応付けて記憶するにあたり、検索を高速に行うため、まず、送信パラメータをルーチングデータテーブル３１０に格納する。そして、送信パラメータが格納されたメモリアドレスと宛先ＩＰアドレスとを検索テーブル２２０に格納する。この検索テーブル２２０に対する格納は、検索データ管理部３２０およびキュー管理部２３０によって行われる。以降、送信パラメータが格納されたルーチングデータテーブル３１０のメモリアドレスを、ルーチング情報と称する。【００４５】
一方、データ検索処理部２１０は、パケット受信部２００から送信されてきたＩＰパケットに含まれる宛先ＩＰアドレスを取出すとともに、検索テーブル２２０を参照して宛先ＩＰアドレスに対応するルーチング情報を読み出す。データ検索処理部２１０は、読み出したルーチング情報をＩＰパケットとともにルート選択部２４０に送信する。ルーチング情報は、ルーチングデータテーブル３１０におけるメモリアドレスである。ルート選択部２４０は、ルーチングデータテーブル３１０を参照して、データ検索処理部２１０から送信されてきたルーチング情報すなわちメモリアドレスから、送信パラメータを読み出す。ルート選択部２４０は、データ検索処理部２１０から送信されてきたＩＰパケットを、データ検索処理部２１０から読み出した送信パラメータとともにパケット送信部２５０に送信する。パケット送信部２５０は、ＩＰパケットを有するイーサネット（登録商標）フレームを生成し、送信パラメータに含まれたに含まれたＭＡＣアドレスをフレームヘッダに挿入し、送信パラメータに含まれたポート番号が表す出力ポートから送信を行う。【００４６】
なお、図１に示す、ＩＰネットワーク伝送装置１０１は、ハードウェアとしてのパケット受信部２００およびパケット送信部２５０に加え、プログラムを実行する制御装置としてのＣＰＵ、およびプログラムとデータを格納するメモリで構成されており、ＣＰＵがメモリに格納されたプログラムを実行することによって、上述した、データ検索処理部２１０、キュー管理部２３０、ルート選択部２４０、ルーチングデータ管理部３００、および、検索データ管理部３２０の機能が実現する。また、メモリの一部が、検索テーブル２２０、およびルーチングデータテーブル３１０として機能する。【００４７】
図５は、図４に示すデータ検索処理部２１０、検索テーブル２２０、キュー管理部２３０、および検索データ管理部３２０をより詳細に示すブロック図である。【００４８】
図５に示すデータ検索処理部２１０は、検索受付部２１１、ＩＰアドレス変換部２１２、およびメモリアドレス取得部２１３を有している。データ検索処理部２１０は、パケット受信部２００（図４参照）から宛先ＩＰアドレスを伴ったデータ検索の依頼を受け、検索テーブル２２０から宛先ＩＰアドレスを読み出して、検索依頼の宛先ＩＰアドレスと比較する。メモリアドレス取得部２１３は、データ検索処理部２１０による比較の結果、宛先ＩＰアドレスが同一であった場合にこの宛先ＩＰアドレスに対応するルーチング情報を取得し、取得したルーチング情報をデータ検索結果としてルート選択部２４０（図４参照）に出力する。ＩＰアドレス変換部２１２は、検索に際し、宛先ＩＰアドレスが供給され、この宛先ＩＰアドレスを次に説明する所定の変換関係で検索キーに変換する。【００４９】
この検索キーが本発明にいうキーデータの一例に相当する。また、ＩＰアドレス変換部２１２が、本発明にいうデータ変換部の一例に相当し、検索受付部２１１が、本発明にいう取得部の一例に相当し、メモリアドレス取得部２１３が本発明にいう取得部の一例に相当する。【００５０】
図６は、ＩＰアドレス変換部２１２による宛先ＩＰアドレスの変換を説明する図である。図６のパート（Ａ）にはＩＰｖ４における宛先ＩＰアドレスの変換が示されており、パート（Ｂ）には、ＩＰｖ６における宛先ＩＰアドレスの変換が示されている。【００５１】
宛先ＩＰアドレスは、ＩＰｖ４の場合３２ビット長を有し約４３億個の値のうちのいずれかの値を取り得る。また、ＩＰｖ６の場合１２８ビットを有し約３．４×１０の３８乗個の値のうちのいずれかの値を取り得る。ＩＰアドレス変換部２１２は、ネットワーク部とホスト部からなる宛先ＩＰアドレス（図３参照）のうち、上位ビットに位置するネットワーク部をマスクすることによってホスト部の値のみを取り出す。また、さらにホスト部のうち下位６ビットを残し上位のビットをマスクして検索キーとする。６ビット長の検索キーは、０から６３まで６４個の値のうちいずれかの値を取ることとなる。これによって、宛先ＩＰアドレスが、宛先ＩＰアドレスよりも少ない数の値を取り得る検索キーに変換される。【００５２】
図６のパート（Ａ）に示す例では、１６進数で０ｘＣ０Ａ８０１４Ｄの値を取るＩＰｖ４の宛先ＩＰアドレスが、ＩＰアドレス変換部２１２による下位６ビットを除いた部分のマスクによって０ｘ０Ｄ（１０進数で１３）の値を取る検索キーに変換される。また、パート（Ｂ）に示す例では、１６進数で０ｘ２０００００８０００００４０００２０Ｂ５ＤＦＦＦＥＣＣ９ＢＣＤの値を取るＩＰｖ６の宛先ＩＰアドレスが、ＩＰアドレス変換部２１２による下位６ビットを除いた部分のマスクによって０ｘ０Ｄの値を取る検索キーに変換される。【００５３】
検索テーブル２２０は、１つの検索管理テーブル２２１と、複数のバッファキュー２２２，２２３，２２４，２２５とが格納されている。バッファキュー２２２〜２２５は、検索キーが取り得る数と同一の数だけ存在しているが、図では、見易さのためバッファキュー２２２〜２２５を４つ示している。宛先ＩＰアドレスとこの宛先ＩＰアドレスに対するルーチング情報とのデータ組は、バッファキュー２２２，２２３，２２４，２２５に格納されている。ＩＰアドレス変換部２１２によって変換される検索キーが同一の値となる宛先ＩＰアドレスを有するデータ組が１つのバッファキューを形成している。バッファキュー２２２〜２２５には、１あるいは複数のデータ組が含まれている場合もあり、データ組が含まれていない場合もある。【００５４】
検索管理テーブル２２１が本発明にいう格納場所記憶部の一例に相当し、検索テーブル２２０のうちバッファキュー２２２，２２３，２２４，２２５が格納された部分が本発明にいう組格納部の一例に相当する。【００５５】
図７は、図５に示す検索管理テーブルおよびバッファキューのデータ構造を説明する図である。図７には、図５に示す複数のバッファキュー２２２〜２２５のうち、キーデータの値として０ｘ０Ｄすなわち１０進法で１３に変換される値の宛先ＩＰアドレスを有するデータ組からなるバッファキュー２２２が一例として示されている。図７のパート（Ａ）には、バッファキュー２２２に含まれるデータ組が０個の状態が示され、パート（Ｂ）には、バッファキュー２２２に含まれるデータ組が１個の状態が示され、パート（Ｃ）には、バッファキュー２２２に含まれるデータ組が３個の状態が示されている。【００５６】
例えば図７のパート（Ｃ）に示すように、バッファキュー２２２には３個のデータ組２７１，２７２，２７３が含まれており、データ組２７１，２７２，２７３のそれぞれには、宛先ＩＰアドレス２７１ｂ，２７２ｂ，２７３ｂと宛先ＩＰアドレスに対するルーチング情報２７１ｃ，２７２ｃ，２７３ｃが含まれ、さらに、別のデータ組の格納場所を示すインデクスとしての次格納ポインタ２７１ａ，２７２ａ，２７３ａが付属して含まれている。データ組２７１，２７２，２７３のそれぞれに含まれる宛先ＩＰアドレス２７１ｂ，２７２ｂ，２７３ｂは、上述したように互いに同一値（この例では１３）の検索キーに変換されるものである。次格納ポインタ２７１ａ，２７２ａ，２７３ａは、バッファキュー２２２内の他のデータ組の格納場所を示している。これによって、次格納ポインタ２７１ａ，２７２ａ，２７３ａによって順番付けられた列としてのバッファキュー２２２が形成されている。【００５７】
一方の検索管理テーブル２２１には、バッファキュー２２２〜２２５の先頭のデータ組（ここで先頭とは、格納された場所ではなく、次格納ポインタによって順番付けられた順番の先頭を意味する。）の格納場所が検索キーの値順に配列されて記憶されている。より詳細には、検索管理テーブル２２１には、検索キーが取り得る数、すなわち６４個のキュー管理テーブル２２＿０〜２２＿６３が配列されており、キュー管理テーブル２２＿０〜２２＿６３のそれぞれは、先頭情報格納ポインタ２２ａおよび末尾情報ポインタ２２ｂからなる。先頭情報格納ポインタ２２ａにはバッファキュー２２２〜２２５のそれぞれの先頭のデータ組の格納場所が記憶されており、末尾情報ポインタ２２ｂには、バッファキュー２２２〜２２５の末尾のデータ組の格納場所が記憶されている。なお、バッファキュー２２２で末尾のデータ組２７３の次格納ポインタ２７３ａには、対応するキュー管理テーブルの格納場所が記憶されている。図７のパート（Ｃ）の例を参照すると、キュー管理テーブル２２＿１３の先頭情報格納ポインタ２２ａには、バッファキュー２２２の先頭のデータ組２７１の格納場所が記憶されており、末尾情報ポインタ２２ｂには、バッファキュー２２２の末尾のデータ組２７３の格納場所が記憶されている。【００５８】
ここで図５に戻って、ＩＰアドレス変換部２１２、検索受付部２１１、およびメモリアドレス取得部２１３の詳細を説明する。【００５９】
ＩＰアドレス変換部２１２は、パケット受信部２００（図４参照）から供給された宛先ＩＰアドレスを、ネットワーク部のマスクおよびホスト部の上位ビットのマスクによって、検索キーに変換する。【００６０】
検索受付部２１１は、検索キーに基づいて検索管理テーブル２２１を検索することで、バッファキュー２２２〜２２５のいずれか（例えばバッファキュー２２２）に格納されたデータ組のうちバッファキュー２２２の先頭のデータ組（例えば図７パート（Ｃ）に示すデータ組２７１）の格納場所を取得する。そして、先頭のデータ組２７１が有する宛先ＩＰアドレス２７１ｂと、データ検索処理部２１０に供給されてきた宛先ＩＰアドレスとを比較する。【００６１】
メモリアドレス取得部２１３は、検索受付部２１１による宛先ＩＰアドレスの比較が同一であった場合、この宛先ＩＰアドレス２７１ｂを有するデータ組２７１のルーチング情報を、データ検索結果としてルート選択部２４０（図４参照）に出力する。【００６２】
続いて図５に示すキュー管理部２３０について説明する。【００６３】
キュー管理部２３０は、検索受付部２１１による宛先ＩＰアドレスの比較が非同一であった場合、検索受付部２１１が格納場所を取得したデータ組２７１（図７参照）を、そのデータ組２７１を先頭にして並んだバッファキューの末尾に移し、検索受付部２１１に、検索管理テーブル２２１の検索と宛先ＩＰアドレスの比較とをやり直させる。【００６４】
キュー管理部２３０が本発明にいう列変更部の一例に相当する。【００６５】
キュー管理部２３０は、バッファキューの先頭にあったデータ組２７１を末尾に移すため、キュー接続処理部２３１とキュー切断処理部２３２とを有している。キュー切断処理部２３２は、検索受付部２１１が格納場所を取得したデータ組２７１の次格納ポインタ２７１ａの値を、キュー管理テーブル２２＿１３の格納場所を示すアドレスに変更する。これによって、列が切断される。また、キュー接続処理部２３１は、キュー管理テーブル２２＿１３の先頭情報格納ポインタ２２ａの値を、先頭にあったデータ組２７１の次格納ポインタ２７１ａに上述した変更の前に格納されていた値を格納する。また、バッファキューの先頭にあったデータ組２７１の格納場所を、末尾情報格納ポインタ２２ｂと、それまでバッファキューの末尾にあったデータ組２７３の次格納ポインタ２７１ｂとに格納する。これによって、バッファキューの先頭にあったデータ組２７１が末尾に移り、バッファキューの２番目にあったデータ組２７２がバッファキューの先頭に移る。なお、ここで「移る」とは、データ組の格納位置が変わることでなく、順序が変わることを意味する。この後、検索受付部２１１が検索管理テーブル２２１の検索を行うと、前回はバッファキューの２番目にあったデータ組２７２の格納場所が取得され、このデータ組２７１が有する宛先ＩＰアドレス２７２ｂを用いた比較が行われる。上述したキュー管理部２３０の動作が繰り返されることで、宛先ＩＰアドレスの比較結果が一致するまで、バッファキュー２２２のすべてのデータ組２７１〜２７３について比較が行われる。【００６６】
なお、比較がすべてのデータ組２７１〜２７３について一巡すると、この検索に関する宛先ＩＰアドレスについては、ルーチング情報が格納されていなかったと判断する。この場合、データ検索処理部２１０はＩＰパケットを破棄する。【００６７】
図５に示す検索データ管理部３２０は、データ登録部３２１、データ削除部３２２、およびＩＰアドレス変換部３２３を有している。【００６８】
検索データ管理部３２０が、ルーチングデータ管理部３００から登録依頼として、宛先ＩＰアドレスとこの宛先ＩＰアドレスに対応したルーチング情報を受け取ると、ＩＰアドレス変換部３２３が宛先ＩＰアドレスを検索キーに変換する。ＩＰアドレス変換部３２３は、データ検索処理部２１０のＩＰアドレス変換部２１２における変換関係と同一の変換関係で変換を行う。データ登録部３２１は、宛先ＩＰアドレスと、ルーチング情報と、ＩＰアドレス変換部３２３で変換された検索キーとをキュー管理部２３０のキュー接続処理部２３１に送信してエンキュー依頼を行う。キュー接続処理部２３１は、検索管理テーブル２２１を参照して、バッファキュー２２２〜２２５のうち検索キーに対応するものに、データ登録部３２１から供給された宛先ＩＰアドレスとルーチング情報とのデータ組を追加する。新たなデータ組は、検索キーに対応したデータ組の末尾に追加される。例えば、図７のパート（Ａ）には、検索キーが１３の場合に対応するデータ組が存在しない場合を示し、図７のパート（Ｂ）には、１つめのデータ組２７１が登録された状態を示し、図７のパート（Ｃ）には、３つめのデータ組２７３が登録された状態を示している。【００６９】
検索データ管理部３２０がルーチングデータ管理部３００から、削除依頼として宛先ＩＰアドレスを受け取った場合にも、ＩＰアドレス変換部３２３が宛先ＩＰアドレスを検索キーに変換する。データ削除部３２２は、検索管理テーブル２２１を参照して、バッファキュー２２２〜２２５のうち、検索キーに対応するものに、宛先ＩＰアドレスを有するデータ組を検索し、キュー切断処理部２３２に検索キーおよび宛先ＩＰアドレスを送信し、この宛先ＩＰアドレスを含むデータ組を削除させる。【００７０】
このように検索データ管理部３２０によって、検索管理テーブル２２１、およびバッファキュー２２２〜２２５のデータ組が管理されている。【００７１】
続いて、フローチャートも参照して、宛先ＩＰアドレスとこの宛先ＩＰアドレスに対応するルーチング情報の登録、削除、および検索について説明する。【００７２】
図８は、ルーチングデータの登録および削除の処理を示すフローチャートである。【００７３】
ルーチングデータの登録および削除は、ルーチングデータ管理部３００が、宛先ＩＰアドレスに対応した送信パラメータをルーチングデータテーブル３１０に格納した後、検索データ管理部３２０に、登録または削除の依頼を表すデータを送信することにより開始する。登録では、依頼を表すデータに伴って、宛先ＩＰアドレスと、送信パラメータの格納されたメモリアドレスがルーチング情報として送信されてくる。削除では、依頼を表すデータに伴って宛先ＩＰアドレスのみ送信されてくる。【００７４】
検索データ管理部３２０が登録または削除の依頼を表すデータを受信すると、ＩＰアドレス変換部３２３が、宛先ＩＰアドレスを規定のビット幅でマスクする（Ｓ１１）。ここでは、例えば図６のパート（Ａ）で示すように、宛先ＩＰアドレスのネットワーク部をマスクし、さらに、ホスト部の下位６ビットを除いた上位ビットをマスクすることによって、３２ビットの宛先ＩＰアドレスを６ビットの検索キーに変換する。このとき、検索管理テーブル２２１を参照して変換された検索キーに対応するバッファキューを確定する。【００７５】
次に、ルーチングデータ管理部３００から受けた処理の種別が判定され（Ｓ１２）、処理が登録の場合、キュー接続処理部２３１が、検索テーブル２２０に宛先ＩＰアドレスとルーチング情報とのデータ組を書き込み（Ｓ１３）、次いで、キュー接続処理部２３１が、書き込まれたデータ組を、検索キーに応じたバッファキューの末尾に接続する（Ｓ１４）。キュー接続（Ｓ１４）の詳細については後述する。【００７６】
一方、上述した処理種別の判定（Ｓ１２）で処理が削除であった場合には、データ登録部３２１が検索管理テーブル２２１を参照し、キュー管理テーブル２２＿０〜２２＿６３のうちの（図７参照）検索キーに対応する先頭情報格納ポインタ２２ａに格納された値を読み出して別の場所に記憶する（Ｓ１５）。先頭情報格納ポインタ２２ａには、バッファキューの先頭のデータ組の格納場所が記憶されている。次に、先頭情報格納ポインタ２２ａに格納された値、すなわち格納場所に格納された、バッファキューの先頭のデータ組（例えば、図７に示すデータ組２７１）の宛先ＩＰアドレス２７１ｂと、削除しようとする宛先ＩＰアドレスとを比較する。宛先ＩＰアドレスが一致する場合には（Ｓ１７ではい）、キュー切断処理部２３２が、宛先ＩＰアドレスを有するデータ組、すなわちバッファキューの先頭のデータ組を切断する（Ｓ１８）。また、キュー切断処理部２３２は、データ組が格納されていた検索テーブル２２０内のバッファを開放する。切断処理の詳細については後述する。【００７７】
宛先ＩＰアドレスの比較結果が非同一の場合には（Ｓ１７でいいえ）、キュー切断処理部２３２およびキュー接続処理部２３１がキューの繋ぎ換えを行う（Ｓ２０）。【００７８】
図１０は、キューの繋ぎ換え処理を示すフローチャートである。図１０に示すように、キューの切断（Ｓ５１）とそれに続くキューの接続（Ｓ５２）とによってキューの繋ぎ換えが行われる。キューの繋ぎ換えによって、バッファキューの先頭にあったデータ組がバッファキューの末尾に移され、先頭のデータ組の次のデータ組がバッファキューの先頭になる。【００７９】
図８に戻って説明を続けると、宛先ＩＰアドレスの比較（Ｓ１７）と、キューの繋ぎ換え（Ｓ２０）とは、先の処理Ｓ１５で記憶しておいたバッファキューの先頭のデータ組の格納場所を表す値と、現在において、バッファキューの先頭のデータ組の格納場所を示す値（ポインタの値）が一致するまで繰り返される（Ｓ１６〜Ｓ２２）。先頭情報が一致する場合には（Ｓ２１ではい）、宛先ＩＰアドレスの検査をバッファキューの中のすべてのデータ組について行ったことになるので、処理を終了する。【００８０】
図９は、ルーチングデータの検索処理を示すフローチャートである。【００８１】
ルーチングデータの検索は、パケット受信部２００（図４参照）が、ＩＰパケットを受信し、受信したＩＰパケットから取り出した宛先ＩＰアドレスおよびＴｏＳを、データ検索処理部２１０に供給することより開始する。【００８２】
データ検索処理部２１０が宛先ＩＰアドレスを受信すると、ＩＰアドレス変換部２１２が、宛先ＩＰアドレスを規定のビット幅でマスクする（Ｓ３１）。データ検索処理部２１０のＩＰアドレス変換部２１２は、検索データ管理部３２０のＩＰアドレス変換部３２３と同様のビット幅でマスクする。例えば図６のパート（Ａ）で示すように、宛先ＩＰアドレスのネットワーク部をマスクし、さらに、ホスト部の下位６ビットを除いた上位ビットをマスクすることによって、３２ビットの宛先ＩＰアドレスを６ビットの検索キーに変換する。このとき、検索管理テーブル２２１を参照して変換された検索キーに対応するバッファキューを確定する。【００８３】
次に、検索受付部２１１が、検索管理テーブル２２１を参照し、キュー管理テーブル２２＿０〜２２＿６３のうちの（図７参照）変換された検索キーに対応する先頭情報格納ポインタ２２ａに格納された値を読み出して別の場所に記憶する（Ｓ３２）。先頭情報格納ポインタ２２ａには、バッファキューの先頭のデータ組の格納場所が記憶されている。次に、検索受付部２１１は、先頭情報格納ポインタ２２ａに格納された値、すなわち格納場所に格納された、バッファキューの先頭のデータ組（例えば、図７に示すデータ組２７１）の宛先ＩＰアドレス２７１ｂと、ＩＰパケットの宛先ＩＰアドレスとを比較する。【００８４】
宛先ＩＰアドレスの比較において非同一の場合には（Ｓ３４でいいえ）、キュー管理部２３０がキューの繋ぎ換えを行う（Ｓ３８）。キューの繋ぎ換えは、キューの切断（図１０のＳ５１）とそれに続くキューの接続（図１０のＳ５２）により実行される。キューの繋ぎ換えによって、バッファキューの先頭にあったデータ組がバッファキューの末尾に移され、先頭のデータ組の次のデータ組がバッファキューの先頭になる。【００８５】
宛先ＩＰアドレスの比較（Ｓ３４）と、キューの繋ぎ換え（Ｓ３９）とは、先の処理Ｓ３２で記憶しておいたバッファキューの先頭のデータ組の格納場所を表す値と、現在において、バッファキューの先頭にあるデータ組の格納場所（ポインタ）を示す値が一致するまで繰り返される（Ｓ３３〜Ｓ４１）。先頭情報が一致する場合には（Ｓ３９ではい）、宛先ＩＰアドレスの検査をバッファキューの中のすべてのデータ組について行ったことになるので、ルーチング情報は記憶されていないことを通知して処理を終了する。【００８６】
一方、宛先ＩＰアドレスが一致する場合（Ｓ３４ではい）、キュー管理部２３０は、データ検索処理部２１０から送信されてきたＴｏＳが所定の基準レベルよりも高い場合に、ＴｏＳ、宛先ＩＰアドレス、およびＩＰパケットのパケット受信時刻を対応付けて検索テーブル２２０に記憶する（Ｓ３５）。次に、キュー管理部２３０は、検索テーブル２２０にこれまで記憶されたＴｏＳ、宛先ＩＰアドレス、およびパケット受信時刻を読み出し、、読み出した宛先ＩＰアドレスを有するデータ組がバッファキューに含まれている場合には、キューの繋ぎ換えを実行し、記憶された宛先ＩＰアドレスを有するデータ組をバッファキューの先頭に移す（Ｓ３６）。これによって、基準レベルより高いＴｏＳが対応したＩＰアドレスを有するデータ組がバッファキューの先頭に移され、このＩＰアドレスについてのルーチング情報が次回検索以降も高速に検索される。このステップにおけるキューの繋ぎ換えは、参照されたパケット受信時刻から所定の期間に限り実行される。この後、メモリアドレス取得部２１３が、宛先ＩＰアドレスを有するデータ組、すなわちバッファキューの先頭のデータ組が有するルーチング情報を読み出し、ルート選択部２４０（図４参照）に出力する（Ｓ３７）。これによって、ルート選択部２４０は、ルーチングデータテーブル３１０（図４参照）を参照して宛先ＩＰアドレスに応じた送信パラメータを得る。また、このとき、宛先ＩＰアドレスを有するデータ組がバッファキューの先頭にあり、次回以降、同一値の宛先ＩＰアドレスについて検索が行われた場合には、先頭のデータ組が最初に参照されるので、比較処理（Ｓ３４）が一度で完了する。【００８７】
続いて、キューの切断処理およびキューの接続処理を説明する。【００８８】
図１１は、キューの切断処理を示すフローチャートであり、図１２は、キューの切断処理における検索管理テーブルおよびバッファキューのデータ構造の一例を説明する図である。図１２の（１）および（２）は、図１１のフローチャート中の（１）（２）に対応する。【００８９】
キューの切断処理では、キュー切断処理部２３２（図５参照）が、現在対象となっているバッファキューの先頭データがあることを確認すると（Ｓ６１ではい）、列の先頭のデータ組が有する次格納ポインタを変更する（Ｓ６２）。図１２に示す例では、検索データが１３の場合を想定しており、検索管理テーブル２２１のうち１３に対応するキュー管理テーブル２２＿１３の先頭情報格納ポインタ２２ａには、バッファキューの先頭のデータ組２７１の格納場所が記憶されている。そして、バッファキューの先頭のデータ組２７１の次格納ポインタ２７１ａには、バッファキューにおける次のデータ組２７２の格納場所が記憶されているが、上記ステップＳ６２では、バッファキューの先頭のデータ組２７１の次格納ポインタ２７１ａに、自分自身すなわちバッファキューの先頭のデータ組２７１の格納場所を記憶させる。【００９０】
次に、キュー切断処理部２３２は、キュー管理テーブルの先頭情報格納ポインタを更新する（Ｓ６３）。図１２に示す例では、キュー管理テーブル２２＿１３先頭情報格納ポインタ２２ａに、バッファキューの次のデータ組２７２の格納場所を記憶させる。これによって、バッファキューの先頭のデータ組２７１は切り離された状態となる。【００９１】
この後、バッファキューの先頭のデータ組がなくなったか否かを確認する（Ｓ６４）。切り離しによって、バッファキューの先頭のデータ組がなくなった場合、すなわち先頭情報格納ポインタ２２ａにキュー管理テーブル２２＿１３の格納場所が記憶された場合には、検索データ（図１２の例では１３）に対応するデータ組がまったくない状態である（Ｓ６４ではい）。この場合には、末尾情報格納ポインタ２２ｂにもキュー管理テーブル２２＿１３の格納場所を記憶させる。この場合には、図７のパート（Ａ）に示す状態となる。【００９２】
図１３は、キューの接続処理を示すフローチャートであり、図１４は、キューの接続処理における検索管理テーブルおよびバッファキューのデータ構造の一例を説明する図である。図１４の（１）、（２）、および（３）は、図１３のフローチャート中の（１）、（２）、および（３）に対応する。図１３には、図１２に示す例では、検索データが１３の場合を想定しており、２つのデータ組からなるバッファキューの末尾に１つのデータ組を接続する例が示されている。【００９３】
キューの接続処理では、キュー接続処理部２３１（図５参照）が、現在対象となっているバッファキューの末尾のデータ組が有する次格納ポインタを更新する（Ｓ７１）。図１４の例では、キュー管理テーブル２２＿１３の末尾情報格納ポインタ２２ｂが示す格納場所に格納されたデータ組２７２の次格納ポインタ２７１ａに、新たに加えるデータ組２７３の格納場所を記憶させる。【００９４】
次に、キュー管理テーブルの末尾情報格納ポインタを更新する（Ｓ７３）。図１４の例では、末尾情報格納ポインタ２２ｂに新たに加えるデータ組２７３の格納場所を記憶させる。【００９５】
最後に、末尾データの次格納ポインタを更新する。図１４の例では、新たに加えるデータ組２７３の次格納ポインタ２７３ａに、キュー管理テーブル２２＿１３の格納場所を記憶させる。これによって、新たなデータ組２７３がバッファキューの末尾に加わる。【００９６】
図１０のフローチャートで示したように、キューの切断とキューの接続をデータ組み合わせることにより、先頭情報格納ポインタによって示されるデータ組を、このデータ組を先頭にして並んだバッファキューの末尾に移すことができる。【００９７】
本実施形態では、検索管理テーブル２２１が、先頭情報格納ポインタ２２ａと末尾情報格納ポインタ２２ｂの双方を有しており、先頭のデータ組７２１の格納場所に付随して末尾のデータ組７２３の格納場所も記憶されている。したがって、バッファキューの末尾のデータ組に対し記憶内容の更新を行う際に、バッファキューの先頭のデータ組から順に次格納ポインタをたどっていく必要がないので検索時に必要な処理が高速に行える。【００９８】
また、本実施形態では、宛先ＩＰアドレスから検索キーを得る場合に、ハッシュ関数を用いずに、宛先ＩＰアドレスの一部のビットをマスクしている。このため、検索キーを短時間で生成することができ検索時間が短縮する。【００９９】
ここで、ハッシュ関数を用いた場合と、マスクによる場合について、宛先ＩＰアドレスに対する分布を比較した。【０１００】
まず、ＩＰｖ４における宛先ＩＰアドレスの値の例として、１９２．１６８．１．ｘを選び、ｘを０〜２５５までのすべての値にした場合のハッシュ値を計算により求めた。ハッシュ関数としてＭＤ５を用いた。得られたハッシュ値の上記のビットをマスクし、残りの下位６ビットを検索キーとした。【０１０１】
図１５は、１９２．１６８．１．ｘの範囲を取る宛先ＩＰアドレスからハッシュ関数を用いて検索キーを得た場合に、検索キーの値が同一となる宛先ＩＰアドレスの数を、検索キーの値ごとに示したグラフである。グラフの横軸は、検索キーの値を表し、縦軸は、検索キーの値が同一となる宛先ＩＰアドレスの数を表す。縦軸の０は、その値の検索キーが得られないことを表している。【０１０２】
図１５に示す例では、検索キーの値として１４および４１は得られない一方で、検索キーの値として５１は、１０個の宛先ＩＰアドレスが重複して対応している。重複する１０個の宛先ＩＰアドレスは、192.168.1.21、192.168.1.25、192.168.1.70、192.168.1.77、192.168.1.103、192.168.1.145、192.168.1.182、192.168.1.194、192.168.1.233、192.168.1.243である。【０１０３】
次に、宛先ＩＰアドレスの値の例として、１７２．２７．１００．ｘを選び、ｘを０〜２５５までのすべての値にした場合のハッシュ値を計算により求めた。【０１０４】
図１６は、１７２．２７．１００．ｘの範囲を取る宛先ＩＰアドレスからハッシュ関数を用いて検索キーを得た場合に、検索キーの値が同一となる宛先ＩＰアドレスの数を、検索キーの値ごとに示したグラフである。【０１０５】
次に、宛先ＩＰアドレスの値の例として、１９２．１６８．１．ｘを選び、ｘを０〜２５５までのすべての値にした場合に、上述した実施形態におけるＩＰアドレス変換部２１２（図５参照）と同一の変換によって検索キーを求めた。具体的には、宛先ＩＰアドレスのネットワーク部およびホスト部の上位ビットをマスクし、ホスト部の下位６ビットを検索キーとした。【０１０６】
図１７は、１９２．１６８．１．ｘの範囲を取る宛先ＩＰアドレスから本実施形態のＩＰアドレス変換部と同一の変換によって検索キーを得た場合に、検索キーの値が同一となる宛先ＩＰアドレスの数を、検索キーの値ごとに示したグラフである。【０１０７】
図１７のグラフに示すように、検索キーに重複して対応する宛先ＩＰアドレスの数は、平均と同じ４個となる。【０１０８】
図１５および図１６のグラフに示したように、ハッシュ関数を用いて検索キーを得た場合には、検索キーの値が同一となる宛先ＩＰアドレスの数には、検索キーごとに偏りがある。したがって、宛先ＩＰアドレスとルーチング情報を有する複数のデータ組を有するバッファキューは、バッファキューによって含まれるデータ組の数に偏りがあり、検索時間にも偏りが生じる。空き番地法を用いた場合に全体的な検索効率の低下を抑えるには、検索キーのビット数を増やし、検索キーが取り得る値の数を増やすとともに、検索テーブルの容量を増加する必要がある。しかし、検索キーの値が同一となる宛先ＩＰアドレスの数の最大値を、本実施形態における宛先ＩＰアドレスのマスクによる方法と同様に行う場合には、検索管理テーブルの容量を２倍程度にする必要がある。また、空き番地法ではなく分離連鎖法を用いる場合でも、ハッシュ関数を用いた場合には、検索テーブルの値によってデータの比較回数が極端に増加する。【０１０９】
一方、本実施形態のＩＰアドレス変換部２１２は、宛先ＩＰアドレスのうち、重複が生じやすいネットワーク部およびホスト部の上位ビットをマスクし、ホスト部の下位ビットを検索キーとしているので、検索キーごとに対応する宛先ＩＰアドレスの数が均一となるため、検索キーの取り得る値の数を増加させる必要がなく、検索管理テーブルの容量を増加させることなく、検索時間を均一化することができる。【０１１０】
また、ハッシュ関数であるＭＤ５関数、およびＳＨＡ１関数では、複雑な演算処理を行うのに対し、本実施形態のＩＰアドレス変換部２１２は、マスク演算を行うだけであり、検索キーの生成時間が短時間で済む。例えば、テストプログラムによるＣＰＵカウンタレジスタの２点間測定で計測した場合、本実施形態のマスク演算に要する動作時間は、４クロック要するのに対し、ＭＤ５関数は、およそ、２０００倍の８０００クロックとなる。したがって、本実施形態によれば、ハッシュ関数を使わない分の検索時間を短縮できる。【０１１１】
また、本実施形態のＩＰネットワーク伝送装置１０１では、宛先ＩＰアドレスを有するデータ組の検索を実行するたびに、検索されたデータ組がバッファキューの先頭に移されるされることから、同一の宛先ＩＰアドレスを有するＩＰパケットを２回以上連続して受信する場合、次回以降の検索が１回の比較判定で済むようになり検索時間が短縮される。【０１１２】
特に、イーサネット（登録商標）によるＩＰパケット通信では、ＩＰパケットによる通信の準備段階として、ＡＲＰ解決を行う必要があるため、ＩＰパケットの送信元が、送信先のＭＡＣアドレスを把握していない場合には、ＩＰパケット送信直前にＡＲＰを含んだＩＣＭＰパケットが送信される。本実施形態のＩＰネットワーク伝送装置１０１がＩＣＭＰパケットを受信した際に、宛先ＩＰアドレスの検索を行うと、検索されたデータ組がバッファキューの先頭に移されるので、次回以降の検索時間が短縮する。【０１１３】
仮に、同一の検索キーに変換される、異なる宛先ＩＰアドレスを有するＩＰパケットが交互に供給される場合、データ組の再配置が毎度実施される。しかし、データ組の配置処理はプログラムにおける数ステップの処理であり、従来の逐次比較とほとんど変わらない時間で実行される。また、特に中小規模のＩＰネットワーク伝送装置では、大規模のＩＰネットワーク伝送装置に比べて、異なる宛先ＩＰアドレスを有するＩＰパケットが交互に供給される場合よりも、同一の宛先ＩＰアドレスを有するＩＰパケットを連続して受信する場合の頻度が高く、バッファキューの先頭のデータ組が有する宛先ＩＰアドレスが位置する確率がより高い。【０１１４】
また、上述した実施形態では、ＩＰパケットの優先度を表すパラメータとしてＴｏＳを用いたが、本発明はこれに限られるものではなく、例えば、優先度としてはＩＰヘッダ内のクラス情報等を用いてもよい。
【図１】
2009063545.tif 000003
【図２】
2009063545.tif 000004
【図３】
2009063545.tif 000005
【図４】
2009063545.tif 000006
【図５】
2009063545.tif 000007
【図６】
2009063545.tif 000008
【図７】
2009063545.tif 000009
【図８】
2009063545.tif 000010
【図９】
2009063545.tif 000011
【図１０】
2009063545.tif 000012
【図１１】
2009063545.tif 000013
【図１２】
2009063545.tif 000014
【図１３】
2009063545.tif 000015
【図１４】
2009063545.tif 000016
【図１５】
2009063545.tif 000017
【図１６】
2009063545.tif 000018
【図１７】
2009063545.tif 000019
【国際調査報告】
2009063545.tif 000020
2009063545.tif 000021