JPH0832613A - 経路選択情報の検索装置 - Google Patents

Abstract

(57)【要約】 【目的】 一つのネットワークに対して複数のネットワ
ーク番号が割り当てられている場合でも、ハッシュ方式
を用いて全てのネットワーク番号から対応する経路選択
情報を探し出す。 【構成】 ハッシュ方式によって、経路選択情報テーブ
ル１１内に記憶された経路選択情報の中から所定の経路
選択情報を検索する経路選択情報の検索装置において、
選択キー情報として、割り当てられたネットワーク番号
のうちの先頭のネットワーク番号を含む経路選択情報テ
ーブル１１の他に、検索キー情報として先頭のネットワ
ーク番号以外のネットワーク番号と、先頭のネットワー
ク番号とを含む経路選択情報検索テーブル１２を使用し
て、検索手段１３が２段階のハッシュ検索を行う。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、接続された複数のネッ
トワーク間でデータ転送を行うための経路選択情報を検
索する検索装置に関する。

【０００２】

【従来の技術】従来、この種の検索装置は、複数のネッ
トワークを接続するルータ内に設けられていた。上記検
索装置は、ルーティング可能な個々のネットワーク毎
に、次に転送するルータのアドレスやホップ数等を含ん
だ経路選択情報を有しており、この全ての経路選択情報
の中からデータの宛先ネットワークに対する経路情報を
探し出して、データを適切なネットワークに送信してい
た。この際、検索装置では、ハッシュ方式を使用して、
個々の経路選択情報を、ネットワークのネットワーク番
号をキーとしたハッシュテーブルのハッシュ値のところ
にリンクしておく。そして、あるネットワークに対する
経路選択情報を探し出す時には、ハッシュ値が同じであ
る情報のみを検索するので、全ての情報の中から検索す
る必要がなく、短時間での検索が可能となっていた。上
記検索装置では、一つのネットワークに対して一つのネ
ットワーク番号が割り当てられている場合は、上述の方
法によって経路選択情報の管理・検索が容易に行える。

【０００３】

【発明が解決しようとする課題】上記ルータでは、一つ
のネットワーク番号に対して接続できるノード数の範囲
が規定されているものがあり、このような場合に、一つ
のネットワークに対してその接続可能なノード数以上の
ノードを接続させる時には、一つのネットワークに対し
てネットワーク番号を複数割り当てて、接続できるノー
ド数を増やすことがあった。

【０００４】ところが、このような場合に、上記検索装
置を用いて、個々のネットワーク番号毎に経路選択情報
を持つように設定すると、割り当てられたネットワーク
番号の範囲が広ければ、それに対応した多くの経路選択
情報を持たなければならず、記憶容量が大きくなるとい
う問題点があった。また、あるネットワーク対する情報
の追加・削除も、そのネットワークに割り当てられてい
るネットワーク番号の分だけ、行わなければならないの
で、効率が劣化するという問題点があった。さらに、ネ
ットワーク毎に経路選択情報を持つようにすると、ハッ
シュのキーとして使用できるネットワーク番号は、一つ
だけなので、上述のようなハッシュ方式では、キーとな
っていない、その他のネットワーク番号から対応する経
路選択情報を探し出すことができないという問題点があ
った。

【０００５】本発明は、上記問題点に鑑みなされたもの
で、一つのネットワークに対して複数のネットワーク番
号が割り当てられている場合でも、ハッシュ方式を用い
て全てのネットワーク番号から対応する経路選択情報を
探し出すことができる検索装置を提供することを目的と
する。また、本発明の他の目的は、ネットワーク対する
情報の追加・削除を容易に行うことができる検索装置を
提供することにある。

【０００６】さらに、本発明の他の目的は、経路選択情
報の作成を容易に行うことができる検索装置を提供する
ことを目的とする。

【０００７】

【課題を解決するための手段】上記目的を達成するた
め、本発明では、ハッシュ方式によって、経路選択情報
テーブル内に記憶された経路選択情報の中から所定の経
路選択情報を検索する経路選択情報の検索装置におい
て、一つのネットワークに対して複数のネットワーク番
号が割り当てられている場合に、選択キー情報として前
記割り当てられたネットワーク番号のうちの一つのネッ
トワーク番号を含む経路選択情報テーブルと、検索キー
情報として前記選択キー情報となっていないネットワー
ク番号と、該選択キー情報となっているネットワーク番
号とを含む経路選択情報検索テーブルと、経路選択を行
うネットワーク番号を、前記選択キー情報として、経路
選択情報テーブルを検索し、該当する経路選択情報がな
い場合には、前記ネットワーク番号を、検索キー情報と
して経路選択情報検索テーブル内の前記選択キー情報と
なっているネットワーク番号を探し出す検索手段とを備
えた検索装置が提供される。

【０００８】請求項３では、検索手段は、前記経路選択
を行うネットワーク番号に対応する経路選択情報を検索
できない場合には、前記経路選択情報テーブルを全て検
索し、該当する経路選択情報を検索できた場合には、当
該ネットワーク番号に対応する経路選択情報検索テーブ
ルを作成し、対応するハッシュ値に該作成した経路選択
情報検索テーブルをリンクさせる。

【０００９】

【作用】上記検索装置では、経路選択情報テーブル及び
経路選択情報検索テーブルを有し、経路選択情報テーブ
ル内に、経路選択を行うネットワーク番号に対応する経
路選択情報がない場合には、経路選択情報検索テーブル
からネットワーク番号に対応する選択キー情報としての
ネットワーク番号を探し出すので、対応する経路選択情
報を容易に検索できる。経路選択情報テーブルは、一つ
のネットワークに対して一つなので、経路選択情報の追
加・削除が容易に行える。

【００１０】請求項３では、経路選択情報の検索ができ
ない場合には、経路選択情報テーブルを全て検索し、検
索できた場合には、経路選択情報検索テーブルを作成
し、対応するハッシュ値にリンクさせるので、一度検索
を行ったネットワーク番号に対しては、次から経路選択
情報テーブル及び経路選択情報検索テーブルを検索して
選択キーとなっているネットワーク番号を取得すること
ができる。

【００１１】

【実施例】本発明の実施例を図１乃至図４の図面に基づ
いて説明する。図１は、本発明に係る検索装置の概略構
成を示す構成図である。図において、検索装置は、従来
例と同様に、複数のネットワークを接続する各ルータ内
に設けられている。上記検索装置は、ハッシュ構造から
なるとともに、経路選択情報を有する経路選択情報テー
ブル１１と、ハッシュ構造からなるとともに、検索情報
を有する経路選択情報検索テーブル１２と、ハッシュ方
式によって、入力するネットワーク番号に対して、経路
選択情報及び検索情報を検索する検索手段１３とから構
成されている。

【００１２】経路選択情報テーブル１１は、任意に設定
された複数個のハッシュ値からなる経路選択情報ハッシ
ュテーブル１１ａと、上記ハッシュ値にそれぞれ対応し
て設けられた経路選択情報とから構成されている。な
お、本実施例では、上記経路選択情報ハッシュテーブル
１１ａのハッシュ値は、［０］から任意の個数あり、ま
た、経路選択情報は、上記ハッシュ値に対応して複数個
設けられているが、ここでは、説明の都合上、ハッシュ
値［ａ］に対応した経路選択情報Ａ1，Ａ2と、ハッシュ
値［ｂ］に対応した経路選択情報Ａ3，Ａ4とを示す。

【００１３】すなわち、本実施例では、一つのネットワ
ークに複数のネットワーク番号が割り当てられている場
合、上記ネットワークに割り当てられているネットワー
ク番号の割り当て範囲の先頭のネットワーク番号Ｘ1〜
Ｘ4と、最終のネットワーク番号Ｙ1〜Ｙ4及びルーティ
ング可能な個々のネットワーク毎に、次に転送するルー
タのアドレスやホップ数等（図示せず）を含んだ経路選
択情報Ａ1〜Ａ4を、ネットワーク毎に一つ持っている。

【００１４】なお、本実施例では、各経路選択情報Ａ1
〜Ａ4は、先頭のネットワーク番号Ｘ1〜Ｘ4を選択キー
情報として、ハッシュ計算された値の一致するものが、
上記ハッシュ値のところにリンクされているが、本発明
はこれに限らず、例えばネットワークに割り当てられて
いるネットワーク番号のうちで使用頻度がもっとも多い
ネットワーク番号を選択キー情報としたハッシュ値のと
ころにリンクさせることも可能である。

【００１５】経路選択情報検索テーブル１２は、任意に
設定された複数個のハッシュ値からなる経路選択情報検
索ハッシュテーブル１２ａと、上記ハッシュ値にそれぞ
れ対応して設けられた検索情報とから構成されている。
なお、本実施例では、上記経路選択情報検索ハッシュテ
ーブル１２ａのハッシュ値は、［０］から任意の個数あ
り、また、検索情報は、上記ハッシュ値に対応して複数
個設けられているが、ここでは、説明の都合上、ハッシ
ュ値［ａａ］に対応した検索情報Ｂ1，Ｂ2と、ハッシュ
値［ｂｂ］に対応した検索情報Ｂ3，Ｂ4とを示す。

【００１６】すなわち、本実施例では、上記ネットワー
ク番号の範囲の先頭のネットワーク番号Ｘ1〜Ｘ4以外の
ネットワーク番号Ｚ1〜Ｚ4と、上記先頭のネットワーク
番号Ｘ1〜Ｘ4等をそれぞれ含んだ検索情報Ｂ1〜Ｂ4を、
上記先頭でないネットワーク番号毎に一つ持っている。
なお、本実施例では、各検索情報Ｂ1〜Ｂ4は、先頭でな
いネットワーク番号Ｚ1〜Ｚ4を検索キー情報として、ハ
ッシュ計算された値と一致するものが、上記ハッシュ値
のところにリンクされているが、本発明はこれに限ら
ず、例えば使用頻度が多いネットワーク番号を選択キー
情報とした場合には、上記使用頻度が多いネットワーク
番号以外のネットワーク番号を検索キー情報としたハッ
シュ値のところにリンクさせることも可能である。

【００１７】検索手段１３は、ハッシュ検索のアルゴリ
ズムを用いて、ネットワーク番号をキーとしてハッシュ
計算された経路選択情報ハッシュテーブル１１ａのハッ
シュ値でリンクされている経路選択情報を検索する。検
索手段１３は、このリンクされた経路選択情報の中から
データの宛先ネットワークに対する経路情報を探し出し
ており、これにより、ルータは、データを適切なネット
ワークに送信することができる。

【００１８】また、上記検索手段１３は、該当する経路
選択情報がない場合には、経路選択情報検索ハッシュテ
ーブル１２ａの上記ハッシュ値でリンクされている検索
情報を検索する。ここで、検索手段１３は、このリンク
された検索情報の中から、該当するネットワーク番号に
対応する先頭のネットワーク番号を検索する。そして、
上記検索した先頭のネットワーク番号を選択キー情報と
して、ハッシュ計算を行う。そして、検索手段１３は、
計算された経路選択情報ハッシュテーブル１１ａのハッ
シュ値でリンクされている経路選択情報を検索する。

【００１９】また、検索手段１３は、該当する検索情報
がない場合には、経路選択情報テーブルを検索して、該
当する検索情報がある場合には、経路選択情報を検索す
る際に対象となっているネットワーク番号の経路選択情
報検索テーブルを生成する。なお、この経路選択情報検
索テーブルの生成は、検索手段１３によって行われ、一
度検索を行った同一のネットワーク番号の検索に際して
は、次からは、上記経路選択情報検索テーブル及び経路
選択情報検索テーブルを検索して、経路選択キーとなっ
ている先頭のネットワーク番号を、取得することがで
き、経路選択情報テーブルを全て検索する手順がなくな
る。

【００２０】次に、あるネットワーク番号に対する経路
選択情報を探し出すための検索動作を図２乃至図４の図
面に基づいて説明する。図２は、本実施例に係る検索装
置を内部に設けたルータを用いて、複数のネットワーク
を接続させたシステムの一例を示す図である。図におい
て、ルータ２０は、ネットワーク１，２，５とそれぞれ
接続されている。ルータ２１は、ネットワーク３，５と
それぞれ接続されている。ルータ２２は、ネットワーク
２，６とそれぞれ接続されている。ルータ２３は、ネッ
トワーク４，６，７とそれぞれ接続されている。ルータ
２４は、ネットワーク１，８とそれぞれ接続されてい
る。ルータ２５は、ネットワーク６，９とそれぞれ接続
されている。また、ルータ２６は、ネットワーク７，１
０とそれぞれ接続されている。

【００２１】ここで、例えばネットワーク１は、「１０
０１」〜「２０００」の範囲のネットワーク番号を、ネ
ットワーク２は、「１０１」〜「１８０」の範囲のネッ
トワーク番号を、ネットワーク３は、「１１」〜「５
０」の範囲のネットワーク番号を、また、ネットワーク
４は、「１０００１」〜「１０００５」の範囲のネット
ワーク番号を有しているものとする。

【００２２】このような状態において、各ルータは、例
えばハッシュ構造の図３に示すような経路選択情報テー
ブル１１と、図４に示すような経路選択情報検索テーブ
ル１２とを有している。すなわち、経路選択情報テーブ
ル１１において、経路選択情報Ａ1には、ネットワーク
１の先頭のネットワーク番号「１００１」と最終のネッ
トワーク番号「２０００」が含まれており、経路選択情
報Ａ2には、ネットワーク２の先頭のネットワーク番号
「１０１」と最終のネットワーク番号「１８０」が含ま
れている。上記経路選択情報Ａ1，Ａ2は、上記先頭のネ
ットワーク番号を選択キー情報として、ハッシュ計算さ
れた経路選択情報ハッシュテーブル１１ａのハッシュ値
［ａ］のところにリンクされている。

【００２３】経路選択情報Ａ3には、ネットワーク３の
先頭のネットワーク番号「１１」と最終のネットワーク
番号「５０」が含まれており、経路選択情報Ａ4には、
ネットワーク４の先頭のネットワーク番号「１０００
１」と最終のネットワーク番号「１０００５」が含まれ
ている。上記経路選択情報Ａ3，Ａ4は、上記先頭のネッ
トワーク番号を選択キー情報として、ハッシュ計算され
た経路選択情報ハッシュテーブル１１ａのハッシュ値
［ｂ］のところにリンクされている。

【００２４】また、経路選択情報検索テーブル１２にお
いて、検索情報Ｂ1には、上記ネットワーク２の番号範
囲のネットワーク番号「１５６」と、先頭のネットワー
ク番号「１０１」が含まれており、検索情報Ｂ2には、
上記ネットワーク１の番号範囲の例えばネットワーク番
号「１０００５」と、先頭のネットワーク番号「１００
１」が含まれている。上記検索情報Ｂ1，Ｂ2は、上記先
頭のネットワーク番号以外のネットワーク番号「１５
６」、「１０００５」を検索キー情報として、ハッシュ
計算された経路選択情報検索ハッシュテーブル１２ａの
ハッシュ値［ａａ］のところにリンクされている。

【００２５】検索情報Ｂ3には、上記ネットワーク３の
番号範囲の例えばネットワーク番号「３０」と、先頭の
ネットワーク番号「１１」が含まれており、検索情報Ｂ
4には、上記ネットワーク４の番号範囲の例えばネット
ワーク番号「１６０」と、先頭のネットワーク番号「１
０１」が含まれている。上記検索情報Ｂ3，Ｂ4は、上記
先頭のネットワーク番号以外のネットワーク番号「３
０」、「１６０」を検索キー情報として、ハッシュ計算
された経路選択情報検索ハッシュテーブル１２ａのハッ
シュ値［ｂｂ］のところにリンクされている。

【００２６】このような状態において、例えばネットワ
ーク番号「１００１」を経路選択情報を検索する場合に
は、上記「１００１」は、ネットワーク番号の範囲の先
頭であるので、検索手段１３は、経路選択情報ハッシュ
テーブル１１ａのハッシュ値［ａ］のリンクをたどって
いけば、対応する経路選択情報Ａ1を探し出すことがで
きる。

【００２７】また、例えばネットワーク番号「１６０」
を経路選択情報を検索する場合には、まず上記ネットワ
ーク番号でハッシュ計算された経路選択情報ハッシュテ
ーブル１１ａのハッシュ値のリンクをたどる。しかし、
上記ネットワーク番号は、ネットワーク番号の範囲の先
頭でないので、検索手段１３は、対応する経路選択情報
を探し出すことができない。そこで、次に、検索手段１
３は、上記ネットワーク番号でハッシュ計算された経路
選択情報検索ハッシュテーブル１２ａのハッシュ値［ｂ
ｂ］のリンクをたどっていけば、対応する検索情報Ｂ4
を探し出すことができる。そして、上記検索情報Ｂ4内
に格納されている先頭のネットワーク番号である「１０
１」から、ハッシュ計算された経路選択情報ハッシュテ
ーブル１１ａのハッシュ値［ａ］のリンクをたどってい
けば、対応する経路選択情報Ａ2を探し出すことができ
る。

【００２８】また、新たなネットワーク番号に対応する
経路選択情報を検索する場合、すなわち上記経路選択情
報テーブル１１及び経路選択情報検索テーブル１２の検
索でも、経路選択情報及び経路選択情報の取得ができな
い場合には、検索手段１３で、経路選択情報テーブル１
１に格納されている全ての経路選択情報を順に検索し
て、該当するものを探し出す。次に、検索したネットワ
ーク番号でハッシュ計算された経路選択情報検索ハッシ
ュテーブル１２ａのハッシュ値に検索情報をリンクさせ
て、経路選択情報検索テーブルを作成する。

【００２９】上述したごとく、各ルータでは、最初は、
どのネットワーク番号に対する経路選択情報検索テーブ
ルも持っていないが、一度経路選択情報の検索を行う
と、そのネットワーク番号に対して経路選択情報検索テ
ーブルが存在することになる。従って、本実施例では、
一つのネットワークに複数の連続したネットワーク番号
が割り当てられている場合も、経路選択情報テーブルの
他に、経路選択情報検索テーブルを使用して、２段階の
ハッシュ検索を行うので、ルーティング可能な全てのネ
ットワークのネットワーク番号に対する経路選択情報を
管理することなく、該当するハッシュ値にリンクされた
一部の検索情報と経路選択情報を検索するだけでよく、
短時間で対応する経路選択情報を探し出すことができ
る。

【００３０】また、本実施例では、経路選択情報テーブ
ルが、一つのネットワークに対して一つなので、ネット
ワーク対する情報の追加・削除を容易に行うことができ
る。さらに、本実施例では、検索手段によって、ネット
ワーク番号に対応する経路選択情報検索テーブルを作成
し、対応するハッシュ値に該作成した経路選択情報検索
テーブルをリンクさせるので、経路選択情報の作成を容
易に行うことができる。

【００３１】これにより、本実施例では、上記経路選択
情報の中からデータの宛先ネットワークに対する経路選
択情報を正確、かつ、容易に探し出して、上記データを
適切なネットワークに送信することが可能となり、転送
の信頼性を向上させることができる。

【００３２】

【発明の効果】以上説明したように、本発明では、ハッ
シュ方式によって、経路選択情報テーブル内に記憶され
た経路選択情報の中から所定の経路選択情報を検索する
経路選択情報の検索装置において、一つのネットワーク
に対して複数のネットワーク番号が割り当てられている
場合に、選択キー情報として前記割り当てられたネット
ワーク番号のうちの一つのネットワーク番号を含む経路
選択情報テーブルと、検索キー情報として前記選択キー
情報となっていないネットワーク番号と、該選択キー情
報となっているネットワーク番号とを含む経路選択情報
検索テーブルと、経路選択を行うネットワーク番号を、
前記選択キー情報として、経路選択情報テーブルを検索
し、該当する経路選択情報がない場合には、前記ネット
ワーク番号を、検索キー情報として経路選択情報検索テ
ーブル内の前記選択キー情報となっているネットワーク
番号を探し出す検索手段とを備えたので、一つのネット
ワークに対して複数のネットワーク番号が割り当てられ
ている場合でも、ハッシュ方式を用いて全てのネットワ
ーク番号から対応する経路選択情報を探し出すことがで
きるとともに、経路選択情報テーブルが、一つのネット
ワークに対して一つなので、ネットワーク対する情報の
追加・削除を容易に行うことができる。

【００３３】請求項３では、検索手段は、前記経路選択
を行うネットワーク番号に対応する経路選択情報を検索
できない場合には、前記経路選択情報テーブルを全て検
索し、該当する経路選択情報を検索できた場合には、当
該ネットワーク番号に対応する経路選択情報検索テーブ
ルを作成し、対応するハッシュ値に該作成した経路選択
情報検索テーブルをリンクさせるので、経路選択情報の
作成を容易に行うことができる。

【図面の簡単な説明】

【図１】本発明に係る検索装置の概略構成を示す構成図
である。

【図２】本実施例に係る検索装置を内部に設けたルータ
を用いて、複数のネットワークを接続させたシステムの
一例を示す図である。

【図３】図１に示した経路選択情報テーブルの具体例を
示す図である。

【図４】図１に示した経路選択情報検索テーブルの具体
例を示す図である。

【符号の説明】

１１ 経路選択情報テーブル １１ａ 経路選択情報ハッシュテーブル １２ 経路選択情報検索テーブル １２ａ 経路選択情報検索ハッシュテーブル １３ 検索手段 Ａ1〜Ａ4 経路選択情報 Ｂ1〜Ｂ4 検索情報 Ｘ1〜Ｘ4 先頭のネットワーク番号 Ｙ1〜Ｙ4 最終のネットワーク番号 Ｚ1〜Ｚ4 先頭のネットワーク番号以外のネットワーク
番号

───────────────────────────────────────────────────── フロントページの続き (72)発明者 斉藤 秀一 東京都千代田区丸の内２丁目６番１号 古 河電気工業株式会社内

Claims (3)

【特許請求の範囲】
1. 【請求項１】 ハッシュ方式によって、記憶された経路
   選択情報の中から所定の経路選択情報を検索する経路選
   択情報の検索装置において、 一つのネットワークに対して複数のネットワーク番号が
   割り当てられている場合に、選択キー情報として前記割
   り当てられたネットワーク番号のうちの一つのネットワ
   ーク番号を含む経路選択情報テーブルと、 検索キー情報として前記選択キー情報となっていないネ
   ットワーク番号と、該選択キー情報となっているネット
   ワーク番号とを含む経路選択情報検索テーブルと、 前記経路選択情報テーブル及び経路選択情報検索テーブ
   ルから、当該ネットワークに対する経路選択情報を検索
   する検索手段とを備えたことを特徴とする検索装置。
2. 【請求項２】 前記検索手段は、経路選択を行うネット
   ワーク番号を、前記選択キー情報として、経路選択情報
   テーブルを検索し、該当する経路選択情報がない場合に
   は、前記ネットワーク番号を、検索キー情報として経路
   選択情報検索テーブルを検索して、該経路選択情報検索
   テーブル内の前記選択キー情報となっているネットワー
   ク番号を探し出すことを特徴とする請求項１記載の検索
   装置。
3. 【請求項３】 前記検索手段は、前記経路選択を行うネ
   ットワーク番号に対応する経路選択情報を検索できない
   場合には、前記経路選択情報テーブルを全て検索し、該
   当する経路選択情報を検索できた場合には、当該ネット
   ワーク番号に対応する経路選択情報検索テーブルを作成
   し、対応するハッシュ値に該作成した経路選択情報検索
   テーブルをリンクさせることを特徴とする請求項２記載
   の検索装置。