情報中継方法および装置
【課題】 経路制御テーブルに木構造データを用いる経路検索の高速化を実現する。
【解決手段】 コンピュータネットワークで情報中継を行うルータ装置を、経路情報を２分木構造の経路管理テーブルＴＢＬ０で管理する経路管理部Ｆ０と、経路情報を２のｐ乗分木構造の経路検索テーブルＴＢＬ１で持ち、複数のポート５０の一つから受信したパケット５１内の宛先アドレス情報にて検索し転送先（出力すべき一つのポート５０）を決定する経路検索部Ｆ１とで構成し、経路管理部Ｆ０は、経路情報エントリＥの追加等に応じて経路管理テーブルＴＢＬ０の２分木構造の各ノードを更新した後、更新結果を経路検索テーブルＴＢＬ１の２のｐ乗分木構造に反映させるメンテナンス処理を行う。
【解決手段】 コンピュータネットワークで情報中継を行うルータ装置を、経路情報を２分木構造の経路管理テーブルＴＢＬ０で管理する経路管理部Ｆ０と、経路情報を２のｐ乗分木構造の経路検索テーブルＴＢＬ１で持ち、複数のポート５０の一つから受信したパケット５１内の宛先アドレス情報にて検索し転送先（出力すべき一つのポート５０）を決定する経路検索部Ｆ１とで構成し、経路管理部Ｆ０は、経路情報エントリＥの追加等に応じて経路管理テーブルＴＢＬ０の２分木構造の各ノードを更新した後、更新結果を経路検索テーブルＴＢＬ１の２のｐ乗分木構造に反映させるメンテナンス処理を行う。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、情報中継技術に関し、特に、コンピュータネットワークシステム内のパケットを中継するルータ装置等において、受信したパケットの宛先アドレスから、当該パケットを次に送信すべき中継先を決定するために使用する経路情報テーブル作成技術等に適用して有効な技術に関する。
【０００２】
【従来の技術】コンピュータ技術および情報ネットワーク技術の進歩に呼応して、いわゆるインターネット等に代表されるように、複数のコンピュータを情報ネットワークを介して接続したコンピュータネットワークが広く普及してきている。さらにこのコンピュータネットワーク内で授受されるデータとして、映像や音声等のいわゆるマルチメディアデータのように、大容量でかつ実時間性が重要なデータが増えつつあり、コンピュータネットワーク内におけるデータの中継を行うルータ装置等の情報中継装置においても、通信媒体そのものの通信速度並の中継動作の高速化が要求されている。
【０００３】本発明の参考技術である情報中継技術を以下、図２２に従い説明する。参考技術のルータ装置は経路検索部Ｆ１００、制御経路検索部Ｆ２００、付加機構部Ｆ３００を保持する。
【０００４】経路検索部Ｆ１００は次に送信すべき装置のアドレス及びその装置が接続されている回線情報を持つ経路情報エントリＥを登録する経路検索テーブルＴＢＬ１００を保持する。経路情報エントリＥはサブネットワークアドレスとマスク長、及び回線情報、次ホップアドレス、サブネットワークが直接接続されているか否かの情報（以後次ホップ情報と称す）より構成される。経路検索部Ｆ１００はユーザが設定したり、ルーティングプロトコルなどでルータ装置間の接続情報のやりとりによって得られた経路情報エントリＥを経路検索テーブルＴＢＬ１００に追加、削除を行う。また経路検索部Ｆ１００はパケットを受信した場合に経路検索テーブルＴＢＬ１００の経路情報エントリＥのサブネットワークアドレスとマスク長の組を検索キーとして、パケットの宛先アドレスと比較し、一致する経路情報エントリＥが存在するか検索する。
【０００５】制御経路検索部Ｆ２００はパケット中継に必要な経路情報以外の制御経路情報エントリＣＥを登録する制御経路テーブルＴＢＬ２００を保持する。制御経路情報エントリＣＥは付加機構部に転送すべき、制御経路アドレスより構成される。制御経路検索部Ｆ２００は経路検索部Ｆ１００で受信したパケットの検索処理を行った後に、制御経路検索テーブルＴＢＬ２００の制御経路情報エントリＣＥの制御経路アドレスとパケットの宛先アドレスを比較し、一致する制御経路情報エントリＣＥが存在するか検索する。一致する制御経路情報エントリＣＥが存在すれば、パケットを付加機構部Ｆ３００に転送する。一致する制御経路情報エントリＣＥが存在しなければ、経路検索部Ｆ１００の検索結果に従い、パケットを送信する。
【０００６】上記の検索仕様に従った経路検索方法として２分木構成によるＲａｄｉｓｈアルゴリズムがある。Ｒａｄｉｓｈアルゴリズムは、左右にポインタを持つ複数の頂点（ノード）をポインタでつないだ木から構成される木構造の各ノードに経路エントリをマップし、この木を辿るときには、各ノードの左右のどちらかのポインタを辿り次のノードに移動することにより、目的の経路エントリがマップされたノードにたどり着くアルゴリズムである。
【０００７】まず、図２３を用い、木の構造を説明する。考え方はビット長には依存しないので、図２３では、理解し易いようアドレス長を３ビットとして説明する。
【０００８】図２３に示すように、各ノードを、木の上から順に、マスク長０ビット、１ビット、２ビット、３ビットのノードと呼ぶ。
【０００９】マスク長０ビットのノードＮ００００では宛先アドレスの第０ビットが０か１かに従い左／右のポインタを辿ることによりマスク長１ビットのノードＮ０００１，Ｎ１００１に移り、マスク長１ビットのノードでは第１ビットが０か１かに従い左／右のポインタを辿ることによりマスク長２ビットのノードＮ０００２，Ｎ０１０２，Ｎ１００２，Ｎ１１０２に移り、マスク長２ビットのノードでは第２ビットが０か１かに従い左／右のポインタを辿ることによりマスク長３ビットのノードＮ０００３，Ｎ００１３，Ｎ０１０３，Ｎ０１１３，Ｎ１００３，Ｎ１０１３，Ｎ１１０３，Ｎ１１１３に移る。
【００１０】検索したい宛先アドレスについて、この木のマスク長０ビットのノードＮ００００から順に、各ビットが０か１かに従いポインタを辿った場合、マスク長０ビットのノードは宛先アドレスがどの場合にも通過し、マスク長１ビットのノードＮ０００１，Ｎ１００１は左から順に宛先アドレスの各ビットが０ＸＸ，１ＸＸの場合に通過し、マスク長２ビットのノードＮ０００２，Ｎ０１０２，Ｎ１００２，Ｎ１１０２は左から順に宛先アドレスの各ビットが００Ｘ，０１Ｘ，１０Ｘ，１１Ｘの場合に通過し、マスク長３ビットのノードＮ０００３，Ｎ００１３，Ｎ０１０３，Ｎ０１１３，Ｎ１００３，Ｎ１０１３，Ｎ１１０３，Ｎ１１１３は左から順に宛先アドレスの各ビットが０００，００１，０１０，０１１，１００，１０１，１１０，１１１の場合に通過する。ここで、Ｘは、そのビット値が０または１のどちらでも良いことを示す。
【００１１】従って、マスク長０ビットのノードＮ００００は、宛先アドレスがサブネットワークアドレス０００／０に属する場合に通過し、マスク長１ビットのノードＮ０００１，Ｎ１００１は、宛先アドレスがサブネットワークアドレス０００／１，１００／１に属する場合に通過し、マスク長２ビットのノードＮ０００２，Ｎ０１０２，Ｎ１００２，Ｎ１１０２は、宛先アドレスがサブネットワークアドレス０００／２，０１０／２，１００／２，１１０／２に属する場合に通過し、マスク長３ビットのノードＮ０００３，Ｎ００１３，Ｎ０１０３，Ｎ０１１３，Ｎ１００３，Ｎ１０１３，Ｎ１１０３，Ｎ１１１３は、宛先アドレスがサブネットワークアドレス０００／３，００１／３，．．．，１１１／３に属する場合に通過する。ここで、表記法″ｓｓｓ／ｍ″の″ｓｓｓ″はサブネットワークアドレス，ｍはマスク長を表すものとする。
【００１２】上記の通り、この木の各ノードは、サブネットワークアドレスとマスク長が異なる全サブネットに１対１に対応している。
【００１３】そこで、図２４に示す経路情報エントリに対応するノードＮ００００，Ｎ００１３，Ｎ０１０２，Ｎ１００１，Ｎ１１０３に″＊″を付け、検索したい宛先アドレスＤＡ０１１を、この木の上から各ビットが０か１かに従いポインタを辿ったときに通過する″＊″を付けたノードＮ００００，Ｎ０１０２が、マスク付きの検索で一致するエントリに対応することが分かる。そこで、経路情報エントリが複数一致した場合は最もマスク長が長いサブネットワークを選択する、という規則に対応し、一致した″＊″付きノードＮ００００，Ｎ０１０２の内、最も末端に近いノードＮ０１０２に割り付けられた経路情報を、経路テーブルの検索結果とする。
【００１４】上記検索方法から分かるように、″＊″が付いておらず、かつ″＊″付きのノードにたどり着くための途中経路にもなっていないノードＮ０００３，Ｎ０１０３，Ｎ０１１３，Ｎ１００３，Ｎ１０１３，Ｎ１１１３，Ｎ１００２は木から取り除いても、検索結果には影響しない。むしろ、最下のノードに″＊″が付いていないときは最下まで移動せずに検索が終了するために効率的である。そこで、″＊″が付いておらず、かつ″＊″付きのノードにたどり着くための途中経路にもなっていないノードを木から取り除くと図２５のようになる。
【００１５】更に左右の片方のポインタだけに次のノードがつながり、かつ経路情報がマップされていないノードＮ０００２，Ｎ１１０２を木から取り除き、Ｎ０００１，Ｎ１００１の直ぐ下にそれぞれノードＮ００１３，Ｎ１１０３を付ける。その結果、図２６に示す形になる。このように途中のノード列を取り除くことを、以後、木の縮退と呼ぶ。
【００１６】２分木構造をとる経路管理テーブルへ経路情報エントリの追加、削除する方法について説明する。
【００１７】図２７は２分木への経路情報追加例である。図２７（ａ）はエントリ追加前の経路管理テーブル、図２７（ｂ）はエントリ追加後の経路管理テーブルである。図２７を用いて、２分木構造をとる経路管理テーブルに経路情報エントリ及び制御経路情報エントリを追加する方法について説明する。エントリを追加することで発生するノードの追加位置を決定するために初段ノードから下段方向に検索していき、検索の対象となっているノード（以下現在ノードと称す）と追加するエントリのサブネットワークアドレスとマスク長を比較し、４つの判定条件に当てはまる現在ノードを検出する。以下に４つの判定条件を示す。
【００１８】（Ａ−１）現在ノードのサブネットワークアドレスとマスク長が一致した時。
【００１９】（Ａ−２）現在ノードとサブネットワークアドレスが不一致になった時。
【００２０】（Ａ−３）マスク長が現在ノードのマスク長より大きく、現在ノードのサブネットワークアドレスと一致しており、次に検索すべき子ノード方向のポインタがＮＵＬＬである時。
【００２１】（Ａ−４）マスク長が現在ノードのマスク長よりも小さく、サブネットワークアドレスが一致した時。
【００２２】ただし、ネットワークアドレスの比較は、現在ノードと追加ノードのどちらか小さい方のマスク長により比較される。４つの判定条件にそれぞれ当てはまる例を以下に示す。
【００２３】追加するエントリのサブネットワークアドレス、マスク長が１３３．５．１６．０／２１の場合、判定条件（Ａ−１）に当てはまる。図２７（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５と移動していき、ノードＳ５で判定条件（Ａ−１）に当てはまる。判定条件（Ａ−１）に当てはまる場合、図２７（ｂ）に示すように追加する経路情報ノードは分岐ノードであるため、分岐ノードＳ５のエントリに経路情報を書き込み、経路情報ノードＳ５に変更する。
【００２４】追加するエントリのサブネットワークアドレス、マスク長が１３３．５．１９．０／２４の場合、判定条件（Ａ−２）に当てはまる。図２７（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５→Ｓ６と移動していき、ノードＳ６で判定条件（Ａ−２）に当てはまる。判定条件（Ａ−２）に当てはまる場合、図２７（ｂ）に示すように経路情報ノードＳＡ１を追加し、現在ノードＳ６と経路情報ノードＳＡ１を分岐する親ノードが存在しないので分岐ノードＳＡ２を追加し、分岐ノードＳＡ２の親ノードになったノードＳ５の左の子ノード方向のポインタをノードＳ６からノードＳＡ２に変更する。
【００２５】追加するエントリのサブネットワークアドレス、マスク長が１３３．４．１．０／２４の場合、判定条件（Ａ−３）に当てはまる。図２７（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ３と移動していき、ノードＳ３で判定条件（Ａ−３）に当てはまる。判定条件（Ａ−３）に当てはまる場合、図２７（ｂ）に示すように経路情報ノードＳＡ３を追加し、経路情報ノードＳＡ３の親ノードにあたるＳ３の左の子ノード方向のポインタをＮＵＬＬから経路情報ノードＳＡ３に変更する。
【００２６】追加するエントリのサブネットワークアドレス、マスク長が１３３．５．２２．０／２３の場合、判定条件（Ａ−４）に当てはまる。図２７（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５→Ｓ７と移動していき、ノードＳ７で判定条件（Ａ−４）に当てはまる。判定条件（Ａ−４）に当てはまる場合、図２７（ｂ）に示すように経路情報ノードＳＡ４を追加し、経路情報ノードＳＡ４の親ノードにあたるノードＳ５の左の子ノード方向のポインタをノードＳ７から経路情報ノードＳＡ４に変更する。
【００２７】図２８は２分木への経路情報削除例である。図２８（ａ）はエントリ削除前の経路管理テーブル、図２８（ｂ）はエントリ削除後の経路管理テーブルである。図２８を用いて、２分木構造をとる経路管理テーブルから経路情報エントリ及び制御経路情報エントリを削除する方法について説明する。エントリを削除することで発生するノードの削除位置を決定するために初段ノードから下段方向に検索していき、削除するエントリのサブネットワークアドレスとマスク長が一致する現在ノード（以下削除対象ノードと称す）を検出する。現在ノードが以下に示す４つの判定条件のうち、１つに当てはまる。
【００２８】（Ｄ−１）削除対象ノードが２つの子ノードを持つ時。
【００２９】（Ｄ−２）削除対象ノードが子ノードを持たず、親ノードが経路情報を持たない（但し初段ノードは除く）時。
【００３０】（Ｄ−３）削除対象ノードが子ノードを持たず、親ノードが経路情報を持っている時。
【００３１】（Ｄ−４）削除対象ノードが１つの子ノードを持つ時。
【００３２】４つの判定条件にそれぞれ当てはまる例を以下に示す。
【００３３】削除するエントリのサブネットワークアドレス、マスク長が１３３．５．１６．０／２１の場合、判定条件（Ｄ−１）に当てはまる。図２８（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５と移動していき、ノードＳ５で判定条件（Ｄ−１）に当てはまる。判定条件（Ｄ−１）に当てはまる場合、図２８（ｂ）に示すように削除する経路情報ノードＳ５は分岐ノードでもあるため、ノードＳ５のエントリの経路情報を削除し、分岐ノードＳ５に変更する。
【００３４】削除するエントリのサブネットワークアドレス、マスク長が１３３．５．１９．０／２４の場合、判定条件（Ｄ−２）に当てはまる。図２８（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５→ＳＤ２→ＳＤ１と移動していき、ノードＳＤ１で判定条件（Ｄ−２）に当てはまる。判定条件（Ｄ−２）に当てはまる場合、図２８（ｂ）に示すように削除対象ノードＳＤ１とノードＳ６の親ノードにあたる分岐ノードＳＤ２の親ノードにあたるノードＳ５の左の子ノード方向のポインタをノードＳＤ２からノードＳ６に変更する。続いて分岐ノードＳＤ２を削除し、削除対象ノードＳＤ１を削除する。
【００３５】削除するエントリのサブネットワークアドレス、マスク長が１３３．４．１．０／２４の場合、判定条件（Ｄ−３）に当てはまる。図２８（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ３→ＳＤ３と移動していき、ノードＳＤ３で判定条件（Ｄ−３）に当てはまる。判定条件（Ｄ−３）に当てはまる場合、図２８（ｂ）に示すように削除対象ノードＳＤ３は末端ノードのため、削除対象ノードＳＤ３の親ノードにあたるノードＳ３の左の子ノード方向のポインタを削除対象ノードＳＤ３からＮＵＬＬに変更し、削除対象ノードＳＤ３を削除する。
【００３６】削除するエントリのサブネットワークアドレス、マスク長が１３３．５．２２．０／２３の場合、判定条件（Ｄ−４）に当てはまる。図２８（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５→ＳＤ４と移動していき、ノードＳＤ４で判定条件（Ｄ−４）に当てはまる。判定条件（Ｄ−４）に当てはまる場合、図２８２８（ｂ）に示すように削除対象ノードＳＤ４の親ノードにあたるノードＳ５の左の子ノード方向のポインタを削除対象ノードＳＤ４から削除対象ノードの子ノードＳ７に更新し、削除対象ノードＳＤ４を削除する。
【００３７】２分木構成によるＲａｄｉｓｈアルゴリズムを更に高速化する方法として以下に述べる「ネットワークの次転送先高速検索技術」がある。図２９に示すように「ネットワークの次転送先高速検索技術」の経路検索テーブルはマスク長ｍビットの初段ノードを２のｍ乗個保持する２のｐ乗分木構造をとる。参考技術の２分木構成によるＲａｄｉｓｈアルゴリズムは検索を宛先アドレスの上位ビットから１ビットずつ検索していくのに対し、図２９の「ネットワークの次転送先高速検索技術」は２分木のｐ段分を一つの２のｐ乗分木にし、２分木のｐ段を１回の検索で行うことにより、検索処理時間を１／ｐに短縮し、検索処理の高速化を図っている。また、「ネットワークの次転送先高速検索技術」はマスク長ｍビットの初段ノードを２のｍ乗個、記憶手段上の決まった位置に展開し、それぞれのマスク長ｍビットのノードを、それぞれ、宛先アドレスの第０ビットから第（ｍ−１）ビットまでが取りうる値に対応させ、受信パケットの宛先アドレスの第０ビットから第（ｍ−１）ビットの値に従い、マスク長ｍビットの経路情報エントリの一つを選択することにより、最初のｍビット分の検索時間を無くして検索処理の高速化を図っている。
【００３８】
【発明が解決しようとする課題】上述の参考技術のように経路検索テーブルとして、マスク長ｍビットの初段ノードを２のｍ乗個保持する２のｐ乗分木構造を採用した場合には、検索処理の高速化が可能であるが、コンピュータネットワークの構成の変化に応じて動的に経路検索テーブルを更新する場合には、更新処理と検索処理を同一の２のｐ乗分木構造に対して実行する必要があるため、更新処理の間は経路検索が停止され、検索速度が低下するという懸念がある。
【００３９】経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合には、追加、削除、変更の対象となっているノードが木構造から分離されている間に検索を行うと誤検索が懸念され、やはり、経路検索を停止する必要がある。
【００４０】さらに、参考技術では、ブロードキャスト等の特別なパケットについては、通常のパケットとは別の検索テーブルに登録して処理していたため、コンピュータネットワークの機能拡張の作業や検索処理が煩雑になる、という技術的課題もある。
【００４１】本発明の目的は、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に動的に変換して高速化を図ることが可能な情報中継技術を提供することにある。
【００４２】本発明の目的は、経路制御情報の更新に伴う経路検索停止時間を短縮して、中継制御の高速化を実現することが可能な情報中継技術を提供することにある。
【００４３】本発明の他の目的は、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に変換して高速化を図る場合において、２のｐ乗分木構造の動的な更新を、より短い経路検索停止時間で的確に行うことが可能な情報中継技術を提供することにある。
【００４４】本発明の他の目的は、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合において、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を行うことで、検索中断時間を最小化することが可能な情報中継技術を提供することにある。
【００４５】本発明の他の目的は、コンピュータネットワークの特別な機能に割り当てられた制御経路情報を経路検索テーブルに付加することにより、コンピュータネットワークの機能の拡張を容易にすることが可能な情報中継技術を提供することにある。
【００４６】
【課題を解決するための手段】本発明では、ルータ装置等の情報中継装置において、経路検索部を、受信したパケットの転送先を検索する経路検索部と経路情報エントリの追加、削除を行う経路管理部に分離する。経路管理部は経路検索部が保持する２のｐ乗分木構成による経路検索テーブルを生成するための２分木構成による経路管理テーブルを保持する。経路検索テーブルの各々の２のｐ乗分木ノードは経路検索に必要な子ノードの情報のみを保持し、経路管理テーブルの２分木ノードは親ノード、子ノードの情報を保持する。この親ノード、子ノード情報を基に経路管理部は経路情報の追加、削除処理が発生した場合に、経路管理テーブルの２分木ノード間の親子関係から追加、削除、変更をする２分木ノードの位置を決定して２分木構造を更新する。次に該２分木ノードのサブネットワークアドレスとマスク長から該２分木ノードを含む２のｐ乗分木ノードの位置を決定する。次に該２のｐ乗分木ノード内に存在する２分木ノードの保持する親ノードと子ノード情報により、親ノード方向のノードの経路情報よりも、子ノード方向のノードの経路情報を優先させ、子ノード方向のノードが経路情報を持たない時に、親ノード方向のノードが経路情報を持つ時はその経路情報を受け継ぐことで２のｐ乗分木ノードの経路情報を設定する。次に２のｐ乗分木ノード内に存在する２分木ノード数より、２のｐ乗分木の追加、削除、変更を決定する。０個から１個になる時は新規に２のｐ乗分木ノードを追加、１個から０個になる時は２のｐ乗分木ノードを削除、それ以外の個数の変化時は２のｐ乗分木ノードを変更する。
【００４７】２のｍ乗個のマスク長ｍビットを持つ初段ノードをそれぞれ、アドレスの第０ビットから第ｍ−１ビットまでが取りうる値に１対１に対応させた制御機構において、マスク長０ビットから（ｍ−１）ビットまでの経路情報の追加を行う場合、該経路情報のマスク長で初段ノードのアドレスをマスクした値と、経路情報のアドレスが一致する複数個の初段ノードを検索し、一致したノードが経路情報を持たない時に追加する経路情報を設定する。マスク長０ビットから（ｍ−１）ビットまでの経路情報の削除を行う場合、該経路情報を持つ初段ノードの経路情報を削除することにより初段ノードの更新を行う。
【００４８】また、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う制御機構において、１つの経路情報の追加のため親子関係にあるノード間にノードを追加する場合、該追加対象ノードと子ノードを接続後、親ノードと該追加対象ノードを接続する。１つの経路情報の削除のため親と子を持つノードを削除する場合、該削除対象ノードの親ノードを該削除対象ノードの子ノードと接続後、該削除対象ノードを削除する。このノードの追加、削除方式により経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を実現する。
【００４９】経路管理機能と経路探索機能に更に機能を追加する場合、付加機構を新たに追加し、パケット中継に必要な経路情報以外の制御経路情報を経路検索テーブルに追加登録し、受信したパケットの宛先アドレスが制御経路情報と一致すると経路検索機能から付加機構にパケットを転送し、付加機能を実現する。
【００５０】
【発明の実施の形態】以下、本発明の実施の形態を図面を参照しながら詳細に説明する。
【００５１】図１は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置の構成の一例を示す機能ブロック図である。
【００５２】本実施の形態のルータ装置の構成について説明する。本実施の形態のルータ装置は経路管理部Ｆ０、経路検索部Ｆ１、付加機構部Ｆ３を備えている。経路管理部Ｆ０は次に送信すべき他のルータ装置のアドレス及びそのルータ装置が接続されている回線情報を持つ経路情報エントリＥと、パケット中継に必要な経路情報以外の制御経路情報エントリＣＥを登録する経路管理テーブルＴＢＬ０を保持する。経路管理テーブルＴＢＬ０は経路情報を２分木構造に格納し、経路情報を持つノードと分岐が発生するノードを残して縮退した構成をとり、ノードは経路情報及び親ノードと子ノードの情報を保持する。
【００５３】経路検索部Ｆ１は経路管理テーブルＴＢＬ０の経路情報及び制御経路情報を反映する経路検索テーブルＴＢＬ１を保持する。経路検索テーブルＴＢＬ１は経路情報を２分木ノードのｐ段分を１つにまとめた２のｐ乗分木構造に格納し、経路情報を持つノードと分岐が発生するノードを残して縮退した構造をとり、ノードは経路情報及び子ノード情報を保持する。
【００５４】図２に、経路管理テーブルＴＢＬ０の２分木ノードの構成の一例を示す。本実施の形態の場合、経路管理テーブルＴＢＬ０における個々の２分木ノード１００は、上位の親ノードへのポインタ１０１、下位の二つの子ノードをそれぞれ指す子ノードへのポインタ１０２、子ノードへのポインタ１０３、当該子ノードが経路情報を持つか否か、等を示すフラグ１０４、フラグ１０５、および当該子ノードのマスク長１０６、マスク長１０７、さらには当該ノードに設定されたサブネットワークアドレス１０８、経路情報としての次ホップアドレス１０９、複数のポート５０の一つを特定する出力ポート番号１１０、等の情報を持つ。
【００５５】図３に、経路検索テーブルＴＢＬ１の２のｐ乗分木ノードの構成の一例を示す。本実施の形態の場合、経路検索テーブルＴＢＬ１における個々の２のｐ乗分木ノード２００は、２のｐ乗個の子ノードへのポインタ２０１、各々の子ノードにおける経路情報の設定の有無を示す２のｐ乗個のフラグ２０２、当該子ノードのマスク長２０３、さらには当該ノードに設定されたサブネットワークアドレス２０４、経路情報としての次ホップアドレス２０５、複数のポート５０の一つを特定する出力ポート番号２０６、等の情報を持つ。
【００５６】次に本実施の形態のルータ装置の有する機能の一例について説明する。経路管理部Ｆ０は経路情報エントリＥと制御経路情報エントリＣＥを、経路管理テーブルＴＢＬ０および経路検索テーブルＴＢＬ１からなる経路情報テーブルに対して追加、削除を行う。経路管理部Ｆ０はエントリを経路管理テーブルＴＢＬ０における２分木構造に格納するために追加、削除、変更を行うノードの位置をノードの親ノード、子ノード情報より割り出し、２分木を更新する。経路管理部Ｆ０は更新した経路管理テーブルＴＢＬ０を基に経路検索テーブルＴＢＬ１を更新する。エントリの追加の場合は追加または変更した２分木ノードを含む２のｐ乗分木ノードの位置を割り出し、経路検索テーブルＴＢＬ１に割り出した２のｐ乗分木ノードを追加または変更する。エントリの削除の場合は削除または変更した２分木ノードを含む２のｐ乗分木ノードの位置を割り出し、経路検索テーブルＴＢＬ１に割り出した２のｐ乗分木ノードを削除または変更する。
【００５７】経路検索部Ｆ１は、複数のポート５０の一つからパケット５１を受信した場合に経路検索テーブルＴＢＬ１に登録している経路情報エントリＥや制御経路情報エントリＣＥのサブネットワークアドレスを、受信したパケット５１の宛先アドレスと比較し、一致するエントリが存在するかを経路検索テーブルＴＢＬ１の初段２のｐ乗分木ノードからノードの持っている子ノード情報を基に下段方向に検索していく。一致するエントリの中で一番マスク長が長いエントリを検索結果とする。検索結果が経路情報エントリＥの場合はエントリの出力ポート番号、次ホップアドレス情報に従って、複数のポート５０の中で出力ポート番号に対応した一つのポート５０からパケット５１を送信する。検索結果が制御経路情報エントリＣＥの場合はパケット５１を付加機構部Ｆ３に転送する。付加機構部Ｆ３はパケット５１を受け取るとパケット５１の内容に従って処理する。
【００５８】図４のフローチャートに従って、経路情報の追加、削減を契機にした経路管理部の動作を以下で説明する。
【００５９】経路情報の追加、削除が発生すると、上述の図２２以降の参考技術で説明したように、経路情報テーブルの２分木ノードの更新（図４のステップＦＣ０）を行う。
【００６０】次に追加、削除する経路情報のマスク長がｍ以上か否かを判別し（図４のステップＦＣ１）、ｍ以上である場合（図４のステップＦＣ９）、更新した２分木ノードを含む２のｐ乗分木ノードの経路情報を更新（図４のステップＦＣ２）する方法について説明する。図５に４段分の２分木を１６分木へ変換する例を示す。図５（ａ）は４段分の２分木ノードである。２分木には経路情報があるノードと経路情報がないノードが存在する。図５（ｂ）は４段分の２分木を一つにまとめた１６分木ノードである。１６分木ノードは２分木ノードの第４段目だけの大きさにする。２分木ノードの経路情報を１６分木ノードで設定するためには、マスク長が異なる複数の経路情報エントリが一致した場合はマスク長の長い経路情報エントリを採用するという経路検索の仕様に従い行う。この仕様を踏まえた１６分木ノード内に存在する２分木ノードの保持する親ノードと子ノード情報を使った経路情報を設定する規則は２つある。１つ目は親ノード方向のノードの経路情報よりも、子ノード方向のノードの経路情報を優先させることであり、２つ目は子ノード方向のノードが経路情報を持たない時に、親ノード方向のノードが経路情報を持つ時はその経路情報を受け継ぐ（具体的には自分の次ホップアドレス２０５および出力ポート番号２０６のエントリを受け継ぐ先の情報で上書きする）ことである。この規則に従い、図５（ａ）の２分木を１６分木に変換すると図５（ｂ）になる。
【００６１】次に経路情報の追加が発生した場合の経路情報の設定方法を図６を用いて説明する。図６は図５の状態から経路情報を追加した例である。経路情報の追加の場合は子ノード方向のノードに経路情報が存在するか確認するため、子ノードの情報を必要とする。そのため、経路管理テーブルＴＢＬ０の２分木ノード１００は子ノード情報（図２の子ノードへのポインタ１０２、１０３）を保持する。経路情報を追加するノードＡ００の子ノードＡ００１が経路情報を持つ場合は図６（ｂ）の１６分木ノードのＡ００１は＊Ａ００１の経路情報を優先する。経路情報を追加するノードＡ１１の子ノードＡ１１０が経路情報を持たない場合は図６（ｂ）の１６分木ノードのＡ１１０に＊Ａ１１の経路情報を設定する。
【００６２】次に経路情報の削除が発生した場合の経路情報の設定方法を図７を用いて説明する。図７は図５の状態から経路情報を削除した例である。経路情報の削除の場合は親ノード方向のノードに経路情報が存在するか確認するため、親ノードの情報を必要とする。そのため、経路管理テーブルの２分木ノード１００は親ノード情報（図２の親ノードへのポインタ１０１）を保持する。経路情報を削除するノードＡ１の子ノード方向のノードＡ１００が経路情報を持つ場合は図７（ｂ）の１６分木ノードのＡ１００は＊Ａ１００の経路情報をそのまま優先する。経路情報を削除するノードＡ０１０の親ノードＡ０１が経路情報を持っている場合は図７（ｂ）の１６分木ノードのＡ０１０に＊Ａ０１の経路情報を設定する。
【００６３】次に２のｐ乗分木ノード２００に存在する２分木ノードの数の変化（図４のステップＦＣ４）によって、該２のｐ乗分木ノードの追加、削除、変更の内、１つを選択する方法について説明する。
【００６４】２のｐ乗分木ノードの追加と削除について説明する。経路管理部Ｆ０は経路情報エントリの追加、削除によって、経路検索テーブルＴＢＬ１の初段を除いた２のｐ乗分木ノード２００に対して追加、削除、もしくは変更を行う。２のｐ乗分木ノードの追加、削除、変更は更新した後の２のｐ乗分木ノード内に含まれている２分木ノードの数によって決定する。経路情報エントリの追加、削除によって発生する４つのパターンを図８を用いて説明する。
【００６５】図８（ａ）は追加した２分木ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１内に２分木ノードＳＡ１以外にノードが存在しない場合（図４のステップＦＣ１１）である。この場合、新規に２のｐ乗分木ノードＬＡ１を作成し、経路検索テーブルＴＢＬ１に追加する（図４のステップＦＣ５）。
【００６６】図８（ｂ）は追加した２分木ノードＳＡ１を含む２のｐ乗分木ノードＬ１内に２分木ノードＳＡ１以外にノードＳ１が存在する場合（図４のステップＦＣ１３）である。この場合、既に２のｐ乗分木ノードＬ１は存在しているので、２のｐ乗分木ノードＬ１に経路情報を割り当てて、経路検索テーブルＴＢＬ１の２のｐ乗分木ノードＬ１を変更する（図４のステップＦＣ７）。
【００６７】図８（ｃ）は削除した２分木ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１内に２分木ノードが存在しなくなった場合（図４のステップＦＣ１２）である。この場合、２のｐ乗分木ノードＬＤ１は２分木ノードを持たなくなったので、経路検索テーブルＴＢＬ１の２のｐ乗分木ノードＬＤ１を削除する（図４のステップＦＣ６）。
【００６８】図８（ｄ）は削除した２分木ノードＳＤ１を含む２のｐ乗分木ノードＬ１内に２分木ノードが存在する場合（図４のステップＦＣ１３）である。この場合、２のｐ乗分木ノードＬ１は２分木ノードを持っているので、経路検索テーブルＴＢＬ１の２のｐ乗分木ノードＬ１を変更する（図４のステップＦＣ７）。
【００６９】次に経路検索テーブルＴＢＬ１の２のｐ乗分木の更新（図４のステップＦＣ８）方法について説明する。
【００７０】まず、２のｐ乗分木構造をとる経路検索テーブルＴＢＬ１に経路情報エントリＥを追加する方法について説明する。上述の参考技術の説明で２分木構造にエントリを追加すると４つの追加パターンで２分木ノードの更新が発生することを説明したが、２のｐ乗分木にその更新を反映させるためには１つまたは複数の２のｐ乗分木ノードを更新する必要がある。そのため、経路検索テーブルＴＢＬ１に対して２のｐ乗分木ノードを１つずつ追加、削除、変更を行う本実施の形態のルータ装置は、経路情報の追加の時は更新を必要とするノードの中で、親ノードから子ノード方向へ順番に更新することで、ノードの更新と更新の間に経路検索処理を可能にする。
【００７１】図９を用いて、経路検索テーブルＴＢＬ１における２のｐ乗分木ノードの追加方法を示す。図９（ａ）のノードＬ１，Ｌ２はノードＬ１が親ノードでノードＬ２が子ノードの関係である。図９（ｂ）はノードＬ２を子ノードにした追加ノードＬＡ１を経路検索テーブルＴＢＬ１上に書き込んだ状態である。この状態で経路検索処理を実行したとしても、ノードＬ１→Ｌ２の順に検索するので、通常と同様に検索処理を実行できる。図９（ｃ）はノードＬ１の子ノードのポインタをノードＬ２からノードＬＡ１に変更し、ノードの追加処理を完了する。
【００７２】以下にこのノードの追加順番規則に従って、４つの追加パターンの各々毎に更新する２のｐ乗分木ノードと順番について例を示す。
【００７３】図１０は（Ａ−１）における２のｐ乗分木の更新方法について示す。更新したノードはノードＳ１の１つである。図１０は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１を変更する。
【００７４】図１１は（Ａ−２）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＡ１，ＳＡ２の３つである。図１１（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＡ１，ＳＡ２を含む２のｐ乗分木ノードＬ１を変更する。図１１（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳ１，ＳＡ２を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ１を繋げるように変更する。図１１（ｃ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１，ＳＡ２を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ１を繋げるように変更する。図１１（ｄ）は３つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳＡ２を含む２のｐ乗分木ノードＬＡ２を追加し、ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ２を繋げるように変更する。
【００７５】図１２は（Ａ−３）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＡ１の２つである。図１２（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＡ１を含む２のｐ乗分木ノードＬ１を変更する。図１２R>２（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ１を繋げるように変更する。
【００７６】図１３は（Ａ−４）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＡ１の２つである。図１３（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＡ１を含む２のｐ乗分木ノードＬ１を変更する。図１３R>３（ｂ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木Ｌ２を変更し、ノードＳ１を含む２のｐ乗分木Ｌ１は更新しない。図１３R>３（ｃ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ１を繋げるように変更する。
【００７７】次に２のｐ乗分木構造をとる経路検索テーブルＴＢＬ１から経路情報エントリを削除する方法について説明する。上述の参考技術の説明で２分木構造にエントリを削除すると４つの削除パターンで２分木ノードの更新が発生する説明したが、エントリ追加時と同様に、２のｐ乗分木にその更新を反映させるためには１つまたは複数の２のｐ乗分木ノードを更新する必要がある。更新するノードの順番は更新するノードの中で子ノードから親ノードの方向へ更新することで、ノードの更新と更新の間に経路検索処理を可能にする。
【００７８】図１４を用いて、経路検索テーブルＴＢＬ１における２のｐ乗分木ノードの追加方法を示す。図１４R>４（ａ）のノードＬ１，ＬＤ１，Ｌ２はノードＬ１の子ノードがノードＬＤ１、ノードＬＤ１の子ノードがノードＬ２の関係である。図１４（ｂ）はノードＬ１の子ノードのポインタをノードＬＤ１からノードＬ２に変更した状態である。この状態で経路検索処理を実行したとしても、ノードＬ１→Ｌ２の順に検索するので、通常と同様に検索処理を実行できる。図１４（ｃ）はノードＬＤ１を削除し、ノードの削除処理を完了した状態を示す。
【００７９】以下にこのノードの削除順番規則に従って、４つの削除パターンの各々毎に更新する２のｐ乗分木ノードと順番について例を示す。
【００８０】図１５は（Ｄ−１）における２のｐ乗分木の更新方法について示す。更新したノードはノードＳ１の１つである。図１５は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１を変更する。
【００８１】図１６は（Ｄ−２）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＤ１，ＳＤ２の３つである。図１６（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＤ１，ＳＤ２を含む２のｐ乗分木ノードＬ１を変更する。図１６（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＤ２を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ１からノードＬ２に変更し、ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１を削除する。図１６（ｃ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ１からノードＬ２に変更し、ノードＳＤ１，ＳＤ２を含む２のｐ乗分木ノードＬＤ１を削除する。図１６（ｄ）は３つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ２からノードＬ２に変更し、ノードＳＤ２を含む２のｐ乗分木ノードＬＤ２を削除し、ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１を削除する。
【００８２】図１７は（Ｄ−３）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＤ１の２つである。図１７（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＤ１を含む２のｐ乗分木ノードＬ１を変更する。図１７R>７（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ１からＮＵＬＬに変更し、ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１を削除する。
【００８３】図１８は（Ｄ−４）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＤ１の２つである。図１８（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＤ１を含む２のｐ乗分木ノードＬ１を変更する。図１８R>８（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＤ１を含む２のｐ乗分木Ｌ２を変更し、ノードＳ１を含む２のｐ乗分木Ｌ１は更新しない。図１８R>８（ｃ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ１からノードＬ２に変更し、ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１を削除する。
【００８４】次にマスク長０ビットから（ｍ−１）ビットの経路情報を追加、削除する場合（図４のステップＦＣ１０）、更新した２分木ノードの配下に存在する２のｐ乗分木ノードの経路情報を更新（図４のステップＦＣ３）する方法について説明する。経路情報の設定方法は以前に説明したｐ段分の２分木を２のｐ乗分木へ変換する方法で説明した方法と同様に親ノード方向のノードの経路情報よりも、子ノード方向のノードの経路情報を優先させ、子ノード方向のノードが経路情報を持たない時に、親ノード方向のノードが経路情報を持つ時はその経路情報を受け継ぐようにする。
【００８５】図１９を用いて、マスク長０ビットから（ｍ−１）ビットの経路情報を追加する方法について説明する。図１９（ａ）は２分木における初段ノードから第１２段ノードを１６分木における２の１３乗個の初段ノードとしている。図１９（ａ）の状態からノードＳ１に経路情報を追加すると図１９（ｂ）に示すようにＬ１，Ｌ２内で経路情報を設定していなかったノードＡ０００，Ａ１０１，Ａ１１０，Ａ１１１，Ｂ０００，Ｂ００１に経路情報＊Ｓ１を設定する。
【００８６】図２０を用いて、マスク長０ビットから（ｍ−１）ビットの経路情報を削除する方法について説明する。図２０（ａ）は２分木における初段ノードから第１２段ノードを１６分木における２の１３乗個の初段ノードにまとめている。図２０（ａ）の状態からノードＳ１の経路情報を削除すると図２０（ｂ）に示すようにＬ１，Ｌ２内の経路情報に＊Ｓ１を持つノードＡ０００，Ａ１０１，Ａ１１０，Ａ１１１，Ｂ０００，Ｂ００１の経路情報は無くなる。
【００８７】次に受信したパケット５１の宛先アドレスと制御経路情報を比較する処理方法について説明する。従来の経路検索テーブルはパケット中継に必要な経路情報のみを保持しているため、ルータが受信したパケット５１の宛先アドレスに対して、経路検索処理を行った後に、更にパケット中継に必要な経路情報以外の制御経路情報であるか確認する処理を行っていたが、本実施の形態のルータ装置では経路検索テーブルＴＢＬ１に制御経路情報も追加登録し、経路検索処理と制御経路情報であるかの確認を一度にできるようにした。
【００８８】図２１に付加機構部にパケットを転送する例を示す。ブロードキャストアドレスを宛先アドレスとするパケット５１に対して付加機構部Ｆ３で処理を実行したい場合、経路検索テーブルＴＢＬ１に制御経路情報としてブロードキャストアドレスを登録することで受信したパケット５１の宛先アドレスがブロードキャストアドレスである場合、そのパケット５１を経路検索部Ｆ１の経路検索処理でブロードキャストパケットであることを識別し、経路検索部Ｆ１はパケット５１を付加機構部Ｆ３に転送する。
【００８９】以上、詳細に説明したように本実施の形態のルータ装置によれば、初段を２のｍ乗個保持する２のｐ乗分木構造で経路情報を格納する経路検索テーブルＴＢＬ１を保持する経路検索部Ｆ１の前段に、経路情報を２分木構造で格納する経路管理テーブルＴＢＬ０を保持し、経路情報の追加、削除が発生した場合に、経路管理テーブルＴＢＬ０の２分木を、経路検索テーブルＴＢＬ１の２のｐ乗分木に変換する機能を有する経路管理部Ｆ０を設けることで、経路検索テーブルＴＢＬ１のメンテナンスを実現することができる。これにより、参考技術の経路検索方法では、アドレスの上位ビットから１ビットずつ検索していく２分木検索のテーブルで検索していたのに対して、２分木ノードｐ段分を１つの２のｐ乗分木ノードに集約した経路検索テーブルＴＢＬ１を用いて、ｐ段の検索を１回で行うことが可能になり、経路検索の高速化を図るのに効果がある。
【００９０】また、経路情報の追加、削除によって複数の経路情報を保持するノードの更新が発生した場合、図１４１４に例示したようにノードを更新する順番を考慮することで、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を実現することができる。これにより、検索処理中断時間を最小化する効果がある。
【００９１】また、パケット中継に必要な経路情報以外の制御経路情報を経路検索テーブルＴＢＬ１に追加登録することで、付加機構部Ｆ３に転送すべきパケット５１を受信した場合に、受信した経路検索部Ｆ１から付加機構部Ｆ３にパケット５１を転送し、付加機能を実現することができる。この実現により、制御経路情報の検索を経路情報の検索とは別に行わせる場合等に比較して、制御経路情報と経路情報の検索を同時に実行可能になり、検索処理の簡略化を図る効果がある。
【００９２】上記した特許請求の範囲に記載された以外の本発明の特徴を列挙すれば以下の通りである。
【００９３】すなわち、＜１＞ コンピュータネットワークシステム内のパケットを中継するルータ装置において、次に送信すべき装置のアドレス及びその装置が接続されている回線情報（以下経路情報と称す）を保持する経路検索テーブルを持ち、受信したパケットの宛先アドレスから、次に送信すべきルータ装置のアドレス及びそのルータ装置が接続されている回線情報または宛先アドレスが示すホストが接続されている回線情報を経路検索テーブルより検索する経路検索機能と、経路管理テーブルを持ち、経路検索テーブルの経路情報の更新を行う経路管理機能と、を有し、経路管理テーブルは、経路情報をアドレスのマスク長の昇順で２分木構造に格納し、経路情報を持つノードと分岐が発生するノードを残して縮退した構成をとり、経路検索テーブルは、１つの２分木ノードと、その直下につながる（ｐ−１）段分の合計（２のｐ乗―１）個分の２分木ノードを一つの２のｐ乗分木ノードに集約し、集約した最下段の２の（ｐ−１）乗個の２分木ノードに、そのノードより上段のノードに割り付けた経路情報を埋め込み、２のｐ乗分木ノードを、２分木を２の（ｐ−１）乗個分併せた形で構成する２のｐ乗分木構造に、アドレスのマスク長の昇順で格納し、経路情報を持つノードと分岐が発生するノードを残して縮退した構造をとり、経路管理部は、経路情報の追加、削除処理が発生した場合に、経路管理テーブルの２分木構造における２分木ノード間の親子関係から追加、削除、変更をする２分木ノードの位置を決定して２分木構造を更新し、２分木構造の更新結果より経路検索テーブルの２のｐ乗分木構造に対して追加、削除、変更の必要な２のｐ乗分木ノードを更新することを特徴とする経路検索テーブル作成方式。
【００９４】＜２＞ 項目＜１＞に記載の経路検索テーブル作成方式において、マスク長ｍビットの初段ノード２のｍ乗個分をそれぞれ、宛先アドレスの第０ビットから第ｍ−１ビットまでが取りうる値に１対１に対応させるとき、マスク長０ビットから（ｍ−１）ビットまでの経路情報について追加、削除を行う場合、該経路情報のマスク長で初段ノードのアドレスをマスクすると、経路情報のアドレスと一致する複数個の初段ノードが経路情報を持たない時に該経路情報を設定し、マスク長０ビットから（ｍ−１）ビットまでの経路情報について削除を行う場合、該経路情報を持つ初段ノードの経路情報を削除することで初段ノードを更新することを特徴とする経路検索テーブル作成方式。
【００９５】＜３＞ 項目＜１＞に記載の経路検索テーブル作成方式において、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合において、１つの経路情報の追加のため親子関係にあるノード間にノードを追加する場合、追加対象ノードと子ノードとを接続後、親ノードと追加対象ノードを接続し、１つの経路情報の削除のため親と子を持つノードを削除する場合、削除対象ノードの親ノードを削除対象ノードの子ノードと接続後、削除対象ノードを削除することで、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を実現することを特徴とする経路検索テーブル作成方式。
【００９６】＜４＞ 項目＜１＞または＜２＞に記載の経路検索テーブル作成方式において、経路管理機能と経路探索機能に更に機能を追加する場合、付加機構を新たに追加し、パケット中継に必要な経路情報以外の制御経路情報を経路検索テーブルに追加登録し、受信したパケットの宛先アドレスが制御経路情報と一致すると経路検索機能から付加機構にパケットを転送することで付加機能を実現することを特徴とする経路検索テーブル作成方式。
【００９７】以上本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【００９８】
【発明の効果】本発明の情報中継方法によれば、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に動的に変換して高速化を図ることができる、という効果が得られる。
【００９９】本発明の情報中継方法によれば、経路制御情報の更新に伴う経路検索停止時間を短縮して、中継制御の高速化を実現することができる、という効果が得られる。
【０１００】本発明の情報中継方法によれば、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に変換して高速化を図る場合において、２のｐ乗分木構造の動的な更新を、より短い経路検索停止時間で的確に行うことができる、という効果が得られる。
【０１０１】本発明の情報中継方法によれば、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合において、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を行うことで、検索中断時間を最小化することができる、という効果が得られる。
【０１０２】本発明の情報中継方法によれば、コンピュータネットワークの特別な機能に割り当てられた制御経路情報を経路検索テーブルに付加することにより、コンピュータネットワークの機能の拡張を容易にすることができる、という効果が得られる。
【０１０３】また、本発明の情報中継装置によれば、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に動的に変換して高速化を図ることができる、という効果が得られる。
【０１０４】本発明の情報中継装置によれば、経路制御情報の更新に伴う経路検索停止時間を短縮して、中継制御の高速化を実現することができる、という効果が得られる。
【０１０５】本発明の情報中継装置によれば、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に変換して高速化を図る場合において、２のｐ乗分木構造の動的な更新を、より短い経路検索停止時間で的確に行うことができる、という効果が得られる。
【０１０６】本発明の情報中継装置によれば、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合において、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を行うことで、検索中断時間を最小化することができる、という効果が得られる。
【０１０７】本発明の情報中継装置によれば、コンピュータネットワークの特別な機能に割り当てられた制御経路情報を経路検索テーブルに付加することにより、コンピュータネットワークの機能の拡張を容易にすることができる、という効果が得られる。
【図面の簡単な説明】
【図１】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置の構成の一例を示す機能ブロック図である。
【図２】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路管理テーブルの２分木ノードのデータ構造の一例を示す概念図である。
【図３】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルの２のｐ乗分木ノードのデータ構造の一例を示す概念図である。
【図４】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路情報の追加、削減を契機にした動作の一例を示すフローチャートである。
【図５】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路情報の２分木から１６分木への変換例を示す概念図である。
【図６】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加が発生した場合の処理の一例を示す概念図である。
【図７】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の削除が発生した場合の処理の一例を示す概念図である。
【図８】（ａ）〜（ｄ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加、削除によって発生する２のｐ乗分木の追加、削除、変更例を示す概念図である。
【図９】（ａ）〜（ｃ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの２のｐ乗分木ノードの追加方法の一例を示す概念図である。
【図１０】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１１】（ａ）〜（ｄ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１２】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１３】（ａ）〜（ｃ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１４】（ａ）〜（ｃ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの２のｐ乗分木ノードの削除方法の一例を示す概念図である。
【図１５】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの経路情報の削除によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１６】（ａ）〜（ｄ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの経路情報の削除によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１７】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの経路情報の削除によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１８】（ａ）〜（ｃ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの経路情報の削除によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１９】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路情報の追加処理の一例を示す概念図である。
【図２０】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路情報の削除処理の一例を示す概念図である。
【図２１】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における受信パケットの付加機構部への転送手順の一例を示す概念図である。
【図２２】本発明の参考技術であるルータ装置の構成および作用の一例を示す概念図である。
【図２３】本発明の参考技術であるルータ装置における経路制御テーブルで用いられるデータ構造を説明する概念図である。
【図２４】本発明の参考技術であるルータ装置における経路情報テーブルの構成を説明する概念図である。
【図２５】本発明の参考技術であるルータ装置の作用を説明する概念図である。
【図２６】本発明の参考技術であるルータ装置の作用を説明する概念図である。
【図２７】（ａ）および（ｂ）は、本発明の参考技術であるルータ装置の作用を説明する概念図である。
【図２８】（ａ）および（ｂ）は、本発明の参考技術であるルータ装置の作用を説明する概念図である。
【図２９】本発明の参考技術であるルータ装置の作用を説明する概念図である。
【符号の説明】
５０…ポート、５１…パケット、１００…２分木ノード、１０１…親ノードへのポインタ、１０２…子ノードへのポインタ、１０３…子ノードへのポインタ、１０４…フラグ、１０５…フラグ、１０６…子のノードのマスク長、１０７…子のノードのマスク長、１０８…サブネットワークアドレス、１０９…次ホップアドレス、１１０…出力ポート番号、２００…２のｐ乗分木ノード、２０１…子ノードへのポインタ、２０２…フラグ、２０３…子のノードのマスク長、２０４…サブネットワークアドレス、２０５…次ホップアドレス、２０６…出力ポート番号、ＣＥ…制御経路情報エントリ、Ｅ…経路情報エントリ、Ｆ０…経路管理部、Ｆ１…経路検索部、Ｆ３…付加機構部、ＴＢＬ０…経路管理テーブル、ＴＢＬ１…経路検索テーブル。
【０００１】
【発明の属する技術分野】本発明は、情報中継技術に関し、特に、コンピュータネットワークシステム内のパケットを中継するルータ装置等において、受信したパケットの宛先アドレスから、当該パケットを次に送信すべき中継先を決定するために使用する経路情報テーブル作成技術等に適用して有効な技術に関する。
【０００２】
【従来の技術】コンピュータ技術および情報ネットワーク技術の進歩に呼応して、いわゆるインターネット等に代表されるように、複数のコンピュータを情報ネットワークを介して接続したコンピュータネットワークが広く普及してきている。さらにこのコンピュータネットワーク内で授受されるデータとして、映像や音声等のいわゆるマルチメディアデータのように、大容量でかつ実時間性が重要なデータが増えつつあり、コンピュータネットワーク内におけるデータの中継を行うルータ装置等の情報中継装置においても、通信媒体そのものの通信速度並の中継動作の高速化が要求されている。
【０００３】本発明の参考技術である情報中継技術を以下、図２２に従い説明する。参考技術のルータ装置は経路検索部Ｆ１００、制御経路検索部Ｆ２００、付加機構部Ｆ３００を保持する。
【０００４】経路検索部Ｆ１００は次に送信すべき装置のアドレス及びその装置が接続されている回線情報を持つ経路情報エントリＥを登録する経路検索テーブルＴＢＬ１００を保持する。経路情報エントリＥはサブネットワークアドレスとマスク長、及び回線情報、次ホップアドレス、サブネットワークが直接接続されているか否かの情報（以後次ホップ情報と称す）より構成される。経路検索部Ｆ１００はユーザが設定したり、ルーティングプロトコルなどでルータ装置間の接続情報のやりとりによって得られた経路情報エントリＥを経路検索テーブルＴＢＬ１００に追加、削除を行う。また経路検索部Ｆ１００はパケットを受信した場合に経路検索テーブルＴＢＬ１００の経路情報エントリＥのサブネットワークアドレスとマスク長の組を検索キーとして、パケットの宛先アドレスと比較し、一致する経路情報エントリＥが存在するか検索する。
【０００５】制御経路検索部Ｆ２００はパケット中継に必要な経路情報以外の制御経路情報エントリＣＥを登録する制御経路テーブルＴＢＬ２００を保持する。制御経路情報エントリＣＥは付加機構部に転送すべき、制御経路アドレスより構成される。制御経路検索部Ｆ２００は経路検索部Ｆ１００で受信したパケットの検索処理を行った後に、制御経路検索テーブルＴＢＬ２００の制御経路情報エントリＣＥの制御経路アドレスとパケットの宛先アドレスを比較し、一致する制御経路情報エントリＣＥが存在するか検索する。一致する制御経路情報エントリＣＥが存在すれば、パケットを付加機構部Ｆ３００に転送する。一致する制御経路情報エントリＣＥが存在しなければ、経路検索部Ｆ１００の検索結果に従い、パケットを送信する。
【０００６】上記の検索仕様に従った経路検索方法として２分木構成によるＲａｄｉｓｈアルゴリズムがある。Ｒａｄｉｓｈアルゴリズムは、左右にポインタを持つ複数の頂点（ノード）をポインタでつないだ木から構成される木構造の各ノードに経路エントリをマップし、この木を辿るときには、各ノードの左右のどちらかのポインタを辿り次のノードに移動することにより、目的の経路エントリがマップされたノードにたどり着くアルゴリズムである。
【０００７】まず、図２３を用い、木の構造を説明する。考え方はビット長には依存しないので、図２３では、理解し易いようアドレス長を３ビットとして説明する。
【０００８】図２３に示すように、各ノードを、木の上から順に、マスク長０ビット、１ビット、２ビット、３ビットのノードと呼ぶ。
【０００９】マスク長０ビットのノードＮ００００では宛先アドレスの第０ビットが０か１かに従い左／右のポインタを辿ることによりマスク長１ビットのノードＮ０００１，Ｎ１００１に移り、マスク長１ビットのノードでは第１ビットが０か１かに従い左／右のポインタを辿ることによりマスク長２ビットのノードＮ０００２，Ｎ０１０２，Ｎ１００２，Ｎ１１０２に移り、マスク長２ビットのノードでは第２ビットが０か１かに従い左／右のポインタを辿ることによりマスク長３ビットのノードＮ０００３，Ｎ００１３，Ｎ０１０３，Ｎ０１１３，Ｎ１００３，Ｎ１０１３，Ｎ１１０３，Ｎ１１１３に移る。
【００１０】検索したい宛先アドレスについて、この木のマスク長０ビットのノードＮ００００から順に、各ビットが０か１かに従いポインタを辿った場合、マスク長０ビットのノードは宛先アドレスがどの場合にも通過し、マスク長１ビットのノードＮ０００１，Ｎ１００１は左から順に宛先アドレスの各ビットが０ＸＸ，１ＸＸの場合に通過し、マスク長２ビットのノードＮ０００２，Ｎ０１０２，Ｎ１００２，Ｎ１１０２は左から順に宛先アドレスの各ビットが００Ｘ，０１Ｘ，１０Ｘ，１１Ｘの場合に通過し、マスク長３ビットのノードＮ０００３，Ｎ００１３，Ｎ０１０３，Ｎ０１１３，Ｎ１００３，Ｎ１０１３，Ｎ１１０３，Ｎ１１１３は左から順に宛先アドレスの各ビットが０００，００１，０１０，０１１，１００，１０１，１１０，１１１の場合に通過する。ここで、Ｘは、そのビット値が０または１のどちらでも良いことを示す。
【００１１】従って、マスク長０ビットのノードＮ００００は、宛先アドレスがサブネットワークアドレス０００／０に属する場合に通過し、マスク長１ビットのノードＮ０００１，Ｎ１００１は、宛先アドレスがサブネットワークアドレス０００／１，１００／１に属する場合に通過し、マスク長２ビットのノードＮ０００２，Ｎ０１０２，Ｎ１００２，Ｎ１１０２は、宛先アドレスがサブネットワークアドレス０００／２，０１０／２，１００／２，１１０／２に属する場合に通過し、マスク長３ビットのノードＮ０００３，Ｎ００１３，Ｎ０１０３，Ｎ０１１３，Ｎ１００３，Ｎ１０１３，Ｎ１１０３，Ｎ１１１３は、宛先アドレスがサブネットワークアドレス０００／３，００１／３，．．．，１１１／３に属する場合に通過する。ここで、表記法″ｓｓｓ／ｍ″の″ｓｓｓ″はサブネットワークアドレス，ｍはマスク長を表すものとする。
【００１２】上記の通り、この木の各ノードは、サブネットワークアドレスとマスク長が異なる全サブネットに１対１に対応している。
【００１３】そこで、図２４に示す経路情報エントリに対応するノードＮ００００，Ｎ００１３，Ｎ０１０２，Ｎ１００１，Ｎ１１０３に″＊″を付け、検索したい宛先アドレスＤＡ０１１を、この木の上から各ビットが０か１かに従いポインタを辿ったときに通過する″＊″を付けたノードＮ００００，Ｎ０１０２が、マスク付きの検索で一致するエントリに対応することが分かる。そこで、経路情報エントリが複数一致した場合は最もマスク長が長いサブネットワークを選択する、という規則に対応し、一致した″＊″付きノードＮ００００，Ｎ０１０２の内、最も末端に近いノードＮ０１０２に割り付けられた経路情報を、経路テーブルの検索結果とする。
【００１４】上記検索方法から分かるように、″＊″が付いておらず、かつ″＊″付きのノードにたどり着くための途中経路にもなっていないノードＮ０００３，Ｎ０１０３，Ｎ０１１３，Ｎ１００３，Ｎ１０１３，Ｎ１１１３，Ｎ１００２は木から取り除いても、検索結果には影響しない。むしろ、最下のノードに″＊″が付いていないときは最下まで移動せずに検索が終了するために効率的である。そこで、″＊″が付いておらず、かつ″＊″付きのノードにたどり着くための途中経路にもなっていないノードを木から取り除くと図２５のようになる。
【００１５】更に左右の片方のポインタだけに次のノードがつながり、かつ経路情報がマップされていないノードＮ０００２，Ｎ１１０２を木から取り除き、Ｎ０００１，Ｎ１００１の直ぐ下にそれぞれノードＮ００１３，Ｎ１１０３を付ける。その結果、図２６に示す形になる。このように途中のノード列を取り除くことを、以後、木の縮退と呼ぶ。
【００１６】２分木構造をとる経路管理テーブルへ経路情報エントリの追加、削除する方法について説明する。
【００１７】図２７は２分木への経路情報追加例である。図２７（ａ）はエントリ追加前の経路管理テーブル、図２７（ｂ）はエントリ追加後の経路管理テーブルである。図２７を用いて、２分木構造をとる経路管理テーブルに経路情報エントリ及び制御経路情報エントリを追加する方法について説明する。エントリを追加することで発生するノードの追加位置を決定するために初段ノードから下段方向に検索していき、検索の対象となっているノード（以下現在ノードと称す）と追加するエントリのサブネットワークアドレスとマスク長を比較し、４つの判定条件に当てはまる現在ノードを検出する。以下に４つの判定条件を示す。
【００１８】（Ａ−１）現在ノードのサブネットワークアドレスとマスク長が一致した時。
【００１９】（Ａ−２）現在ノードとサブネットワークアドレスが不一致になった時。
【００２０】（Ａ−３）マスク長が現在ノードのマスク長より大きく、現在ノードのサブネットワークアドレスと一致しており、次に検索すべき子ノード方向のポインタがＮＵＬＬである時。
【００２１】（Ａ−４）マスク長が現在ノードのマスク長よりも小さく、サブネットワークアドレスが一致した時。
【００２２】ただし、ネットワークアドレスの比較は、現在ノードと追加ノードのどちらか小さい方のマスク長により比較される。４つの判定条件にそれぞれ当てはまる例を以下に示す。
【００２３】追加するエントリのサブネットワークアドレス、マスク長が１３３．５．１６．０／２１の場合、判定条件（Ａ−１）に当てはまる。図２７（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５と移動していき、ノードＳ５で判定条件（Ａ−１）に当てはまる。判定条件（Ａ−１）に当てはまる場合、図２７（ｂ）に示すように追加する経路情報ノードは分岐ノードであるため、分岐ノードＳ５のエントリに経路情報を書き込み、経路情報ノードＳ５に変更する。
【００２４】追加するエントリのサブネットワークアドレス、マスク長が１３３．５．１９．０／２４の場合、判定条件（Ａ−２）に当てはまる。図２７（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５→Ｓ６と移動していき、ノードＳ６で判定条件（Ａ−２）に当てはまる。判定条件（Ａ−２）に当てはまる場合、図２７（ｂ）に示すように経路情報ノードＳＡ１を追加し、現在ノードＳ６と経路情報ノードＳＡ１を分岐する親ノードが存在しないので分岐ノードＳＡ２を追加し、分岐ノードＳＡ２の親ノードになったノードＳ５の左の子ノード方向のポインタをノードＳ６からノードＳＡ２に変更する。
【００２５】追加するエントリのサブネットワークアドレス、マスク長が１３３．４．１．０／２４の場合、判定条件（Ａ−３）に当てはまる。図２７（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ３と移動していき、ノードＳ３で判定条件（Ａ−３）に当てはまる。判定条件（Ａ−３）に当てはまる場合、図２７（ｂ）に示すように経路情報ノードＳＡ３を追加し、経路情報ノードＳＡ３の親ノードにあたるＳ３の左の子ノード方向のポインタをＮＵＬＬから経路情報ノードＳＡ３に変更する。
【００２６】追加するエントリのサブネットワークアドレス、マスク長が１３３．５．２２．０／２３の場合、判定条件（Ａ−４）に当てはまる。図２７（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５→Ｓ７と移動していき、ノードＳ７で判定条件（Ａ−４）に当てはまる。判定条件（Ａ−４）に当てはまる場合、図２７（ｂ）に示すように経路情報ノードＳＡ４を追加し、経路情報ノードＳＡ４の親ノードにあたるノードＳ５の左の子ノード方向のポインタをノードＳ７から経路情報ノードＳＡ４に変更する。
【００２７】図２８は２分木への経路情報削除例である。図２８（ａ）はエントリ削除前の経路管理テーブル、図２８（ｂ）はエントリ削除後の経路管理テーブルである。図２８を用いて、２分木構造をとる経路管理テーブルから経路情報エントリ及び制御経路情報エントリを削除する方法について説明する。エントリを削除することで発生するノードの削除位置を決定するために初段ノードから下段方向に検索していき、削除するエントリのサブネットワークアドレスとマスク長が一致する現在ノード（以下削除対象ノードと称す）を検出する。現在ノードが以下に示す４つの判定条件のうち、１つに当てはまる。
【００２８】（Ｄ−１）削除対象ノードが２つの子ノードを持つ時。
【００２９】（Ｄ−２）削除対象ノードが子ノードを持たず、親ノードが経路情報を持たない（但し初段ノードは除く）時。
【００３０】（Ｄ−３）削除対象ノードが子ノードを持たず、親ノードが経路情報を持っている時。
【００３１】（Ｄ−４）削除対象ノードが１つの子ノードを持つ時。
【００３２】４つの判定条件にそれぞれ当てはまる例を以下に示す。
【００３３】削除するエントリのサブネットワークアドレス、マスク長が１３３．５．１６．０／２１の場合、判定条件（Ｄ−１）に当てはまる。図２８（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５と移動していき、ノードＳ５で判定条件（Ｄ−１）に当てはまる。判定条件（Ｄ−１）に当てはまる場合、図２８（ｂ）に示すように削除する経路情報ノードＳ５は分岐ノードでもあるため、ノードＳ５のエントリの経路情報を削除し、分岐ノードＳ５に変更する。
【００３４】削除するエントリのサブネットワークアドレス、マスク長が１３３．５．１９．０／２４の場合、判定条件（Ｄ−２）に当てはまる。図２８（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５→ＳＤ２→ＳＤ１と移動していき、ノードＳＤ１で判定条件（Ｄ−２）に当てはまる。判定条件（Ｄ−２）に当てはまる場合、図２８（ｂ）に示すように削除対象ノードＳＤ１とノードＳ６の親ノードにあたる分岐ノードＳＤ２の親ノードにあたるノードＳ５の左の子ノード方向のポインタをノードＳＤ２からノードＳ６に変更する。続いて分岐ノードＳＤ２を削除し、削除対象ノードＳＤ１を削除する。
【００３５】削除するエントリのサブネットワークアドレス、マスク長が１３３．４．１．０／２４の場合、判定条件（Ｄ−３）に当てはまる。図２８（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ３→ＳＤ３と移動していき、ノードＳＤ３で判定条件（Ｄ−３）に当てはまる。判定条件（Ｄ−３）に当てはまる場合、図２８（ｂ）に示すように削除対象ノードＳＤ３は末端ノードのため、削除対象ノードＳＤ３の親ノードにあたるノードＳ３の左の子ノード方向のポインタを削除対象ノードＳＤ３からＮＵＬＬに変更し、削除対象ノードＳＤ３を削除する。
【００３６】削除するエントリのサブネットワークアドレス、マスク長が１３３．５．２２．０／２３の場合、判定条件（Ｄ−４）に当てはまる。図２８（ａ）において現在ノードをノードＳ１→Ｓ２→Ｓ４→Ｓ５→ＳＤ４と移動していき、ノードＳＤ４で判定条件（Ｄ−４）に当てはまる。判定条件（Ｄ−４）に当てはまる場合、図２８２８（ｂ）に示すように削除対象ノードＳＤ４の親ノードにあたるノードＳ５の左の子ノード方向のポインタを削除対象ノードＳＤ４から削除対象ノードの子ノードＳ７に更新し、削除対象ノードＳＤ４を削除する。
【００３７】２分木構成によるＲａｄｉｓｈアルゴリズムを更に高速化する方法として以下に述べる「ネットワークの次転送先高速検索技術」がある。図２９に示すように「ネットワークの次転送先高速検索技術」の経路検索テーブルはマスク長ｍビットの初段ノードを２のｍ乗個保持する２のｐ乗分木構造をとる。参考技術の２分木構成によるＲａｄｉｓｈアルゴリズムは検索を宛先アドレスの上位ビットから１ビットずつ検索していくのに対し、図２９の「ネットワークの次転送先高速検索技術」は２分木のｐ段分を一つの２のｐ乗分木にし、２分木のｐ段を１回の検索で行うことにより、検索処理時間を１／ｐに短縮し、検索処理の高速化を図っている。また、「ネットワークの次転送先高速検索技術」はマスク長ｍビットの初段ノードを２のｍ乗個、記憶手段上の決まった位置に展開し、それぞれのマスク長ｍビットのノードを、それぞれ、宛先アドレスの第０ビットから第（ｍ−１）ビットまでが取りうる値に対応させ、受信パケットの宛先アドレスの第０ビットから第（ｍ−１）ビットの値に従い、マスク長ｍビットの経路情報エントリの一つを選択することにより、最初のｍビット分の検索時間を無くして検索処理の高速化を図っている。
【００３８】
【発明が解決しようとする課題】上述の参考技術のように経路検索テーブルとして、マスク長ｍビットの初段ノードを２のｍ乗個保持する２のｐ乗分木構造を採用した場合には、検索処理の高速化が可能であるが、コンピュータネットワークの構成の変化に応じて動的に経路検索テーブルを更新する場合には、更新処理と検索処理を同一の２のｐ乗分木構造に対して実行する必要があるため、更新処理の間は経路検索が停止され、検索速度が低下するという懸念がある。
【００３９】経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合には、追加、削除、変更の対象となっているノードが木構造から分離されている間に検索を行うと誤検索が懸念され、やはり、経路検索を停止する必要がある。
【００４０】さらに、参考技術では、ブロードキャスト等の特別なパケットについては、通常のパケットとは別の検索テーブルに登録して処理していたため、コンピュータネットワークの機能拡張の作業や検索処理が煩雑になる、という技術的課題もある。
【００４１】本発明の目的は、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に動的に変換して高速化を図ることが可能な情報中継技術を提供することにある。
【００４２】本発明の目的は、経路制御情報の更新に伴う経路検索停止時間を短縮して、中継制御の高速化を実現することが可能な情報中継技術を提供することにある。
【００４３】本発明の他の目的は、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に変換して高速化を図る場合において、２のｐ乗分木構造の動的な更新を、より短い経路検索停止時間で的確に行うことが可能な情報中継技術を提供することにある。
【００４４】本発明の他の目的は、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合において、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を行うことで、検索中断時間を最小化することが可能な情報中継技術を提供することにある。
【００４５】本発明の他の目的は、コンピュータネットワークの特別な機能に割り当てられた制御経路情報を経路検索テーブルに付加することにより、コンピュータネットワークの機能の拡張を容易にすることが可能な情報中継技術を提供することにある。
【００４６】
【課題を解決するための手段】本発明では、ルータ装置等の情報中継装置において、経路検索部を、受信したパケットの転送先を検索する経路検索部と経路情報エントリの追加、削除を行う経路管理部に分離する。経路管理部は経路検索部が保持する２のｐ乗分木構成による経路検索テーブルを生成するための２分木構成による経路管理テーブルを保持する。経路検索テーブルの各々の２のｐ乗分木ノードは経路検索に必要な子ノードの情報のみを保持し、経路管理テーブルの２分木ノードは親ノード、子ノードの情報を保持する。この親ノード、子ノード情報を基に経路管理部は経路情報の追加、削除処理が発生した場合に、経路管理テーブルの２分木ノード間の親子関係から追加、削除、変更をする２分木ノードの位置を決定して２分木構造を更新する。次に該２分木ノードのサブネットワークアドレスとマスク長から該２分木ノードを含む２のｐ乗分木ノードの位置を決定する。次に該２のｐ乗分木ノード内に存在する２分木ノードの保持する親ノードと子ノード情報により、親ノード方向のノードの経路情報よりも、子ノード方向のノードの経路情報を優先させ、子ノード方向のノードが経路情報を持たない時に、親ノード方向のノードが経路情報を持つ時はその経路情報を受け継ぐことで２のｐ乗分木ノードの経路情報を設定する。次に２のｐ乗分木ノード内に存在する２分木ノード数より、２のｐ乗分木の追加、削除、変更を決定する。０個から１個になる時は新規に２のｐ乗分木ノードを追加、１個から０個になる時は２のｐ乗分木ノードを削除、それ以外の個数の変化時は２のｐ乗分木ノードを変更する。
【００４７】２のｍ乗個のマスク長ｍビットを持つ初段ノードをそれぞれ、アドレスの第０ビットから第ｍ−１ビットまでが取りうる値に１対１に対応させた制御機構において、マスク長０ビットから（ｍ−１）ビットまでの経路情報の追加を行う場合、該経路情報のマスク長で初段ノードのアドレスをマスクした値と、経路情報のアドレスが一致する複数個の初段ノードを検索し、一致したノードが経路情報を持たない時に追加する経路情報を設定する。マスク長０ビットから（ｍ−１）ビットまでの経路情報の削除を行う場合、該経路情報を持つ初段ノードの経路情報を削除することにより初段ノードの更新を行う。
【００４８】また、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う制御機構において、１つの経路情報の追加のため親子関係にあるノード間にノードを追加する場合、該追加対象ノードと子ノードを接続後、親ノードと該追加対象ノードを接続する。１つの経路情報の削除のため親と子を持つノードを削除する場合、該削除対象ノードの親ノードを該削除対象ノードの子ノードと接続後、該削除対象ノードを削除する。このノードの追加、削除方式により経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を実現する。
【００４９】経路管理機能と経路探索機能に更に機能を追加する場合、付加機構を新たに追加し、パケット中継に必要な経路情報以外の制御経路情報を経路検索テーブルに追加登録し、受信したパケットの宛先アドレスが制御経路情報と一致すると経路検索機能から付加機構にパケットを転送し、付加機能を実現する。
【００５０】
【発明の実施の形態】以下、本発明の実施の形態を図面を参照しながら詳細に説明する。
【００５１】図１は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置の構成の一例を示す機能ブロック図である。
【００５２】本実施の形態のルータ装置の構成について説明する。本実施の形態のルータ装置は経路管理部Ｆ０、経路検索部Ｆ１、付加機構部Ｆ３を備えている。経路管理部Ｆ０は次に送信すべき他のルータ装置のアドレス及びそのルータ装置が接続されている回線情報を持つ経路情報エントリＥと、パケット中継に必要な経路情報以外の制御経路情報エントリＣＥを登録する経路管理テーブルＴＢＬ０を保持する。経路管理テーブルＴＢＬ０は経路情報を２分木構造に格納し、経路情報を持つノードと分岐が発生するノードを残して縮退した構成をとり、ノードは経路情報及び親ノードと子ノードの情報を保持する。
【００５３】経路検索部Ｆ１は経路管理テーブルＴＢＬ０の経路情報及び制御経路情報を反映する経路検索テーブルＴＢＬ１を保持する。経路検索テーブルＴＢＬ１は経路情報を２分木ノードのｐ段分を１つにまとめた２のｐ乗分木構造に格納し、経路情報を持つノードと分岐が発生するノードを残して縮退した構造をとり、ノードは経路情報及び子ノード情報を保持する。
【００５４】図２に、経路管理テーブルＴＢＬ０の２分木ノードの構成の一例を示す。本実施の形態の場合、経路管理テーブルＴＢＬ０における個々の２分木ノード１００は、上位の親ノードへのポインタ１０１、下位の二つの子ノードをそれぞれ指す子ノードへのポインタ１０２、子ノードへのポインタ１０３、当該子ノードが経路情報を持つか否か、等を示すフラグ１０４、フラグ１０５、および当該子ノードのマスク長１０６、マスク長１０７、さらには当該ノードに設定されたサブネットワークアドレス１０８、経路情報としての次ホップアドレス１０９、複数のポート５０の一つを特定する出力ポート番号１１０、等の情報を持つ。
【００５５】図３に、経路検索テーブルＴＢＬ１の２のｐ乗分木ノードの構成の一例を示す。本実施の形態の場合、経路検索テーブルＴＢＬ１における個々の２のｐ乗分木ノード２００は、２のｐ乗個の子ノードへのポインタ２０１、各々の子ノードにおける経路情報の設定の有無を示す２のｐ乗個のフラグ２０２、当該子ノードのマスク長２０３、さらには当該ノードに設定されたサブネットワークアドレス２０４、経路情報としての次ホップアドレス２０５、複数のポート５０の一つを特定する出力ポート番号２０６、等の情報を持つ。
【００５６】次に本実施の形態のルータ装置の有する機能の一例について説明する。経路管理部Ｆ０は経路情報エントリＥと制御経路情報エントリＣＥを、経路管理テーブルＴＢＬ０および経路検索テーブルＴＢＬ１からなる経路情報テーブルに対して追加、削除を行う。経路管理部Ｆ０はエントリを経路管理テーブルＴＢＬ０における２分木構造に格納するために追加、削除、変更を行うノードの位置をノードの親ノード、子ノード情報より割り出し、２分木を更新する。経路管理部Ｆ０は更新した経路管理テーブルＴＢＬ０を基に経路検索テーブルＴＢＬ１を更新する。エントリの追加の場合は追加または変更した２分木ノードを含む２のｐ乗分木ノードの位置を割り出し、経路検索テーブルＴＢＬ１に割り出した２のｐ乗分木ノードを追加または変更する。エントリの削除の場合は削除または変更した２分木ノードを含む２のｐ乗分木ノードの位置を割り出し、経路検索テーブルＴＢＬ１に割り出した２のｐ乗分木ノードを削除または変更する。
【００５７】経路検索部Ｆ１は、複数のポート５０の一つからパケット５１を受信した場合に経路検索テーブルＴＢＬ１に登録している経路情報エントリＥや制御経路情報エントリＣＥのサブネットワークアドレスを、受信したパケット５１の宛先アドレスと比較し、一致するエントリが存在するかを経路検索テーブルＴＢＬ１の初段２のｐ乗分木ノードからノードの持っている子ノード情報を基に下段方向に検索していく。一致するエントリの中で一番マスク長が長いエントリを検索結果とする。検索結果が経路情報エントリＥの場合はエントリの出力ポート番号、次ホップアドレス情報に従って、複数のポート５０の中で出力ポート番号に対応した一つのポート５０からパケット５１を送信する。検索結果が制御経路情報エントリＣＥの場合はパケット５１を付加機構部Ｆ３に転送する。付加機構部Ｆ３はパケット５１を受け取るとパケット５１の内容に従って処理する。
【００５８】図４のフローチャートに従って、経路情報の追加、削減を契機にした経路管理部の動作を以下で説明する。
【００５９】経路情報の追加、削除が発生すると、上述の図２２以降の参考技術で説明したように、経路情報テーブルの２分木ノードの更新（図４のステップＦＣ０）を行う。
【００６０】次に追加、削除する経路情報のマスク長がｍ以上か否かを判別し（図４のステップＦＣ１）、ｍ以上である場合（図４のステップＦＣ９）、更新した２分木ノードを含む２のｐ乗分木ノードの経路情報を更新（図４のステップＦＣ２）する方法について説明する。図５に４段分の２分木を１６分木へ変換する例を示す。図５（ａ）は４段分の２分木ノードである。２分木には経路情報があるノードと経路情報がないノードが存在する。図５（ｂ）は４段分の２分木を一つにまとめた１６分木ノードである。１６分木ノードは２分木ノードの第４段目だけの大きさにする。２分木ノードの経路情報を１６分木ノードで設定するためには、マスク長が異なる複数の経路情報エントリが一致した場合はマスク長の長い経路情報エントリを採用するという経路検索の仕様に従い行う。この仕様を踏まえた１６分木ノード内に存在する２分木ノードの保持する親ノードと子ノード情報を使った経路情報を設定する規則は２つある。１つ目は親ノード方向のノードの経路情報よりも、子ノード方向のノードの経路情報を優先させることであり、２つ目は子ノード方向のノードが経路情報を持たない時に、親ノード方向のノードが経路情報を持つ時はその経路情報を受け継ぐ（具体的には自分の次ホップアドレス２０５および出力ポート番号２０６のエントリを受け継ぐ先の情報で上書きする）ことである。この規則に従い、図５（ａ）の２分木を１６分木に変換すると図５（ｂ）になる。
【００６１】次に経路情報の追加が発生した場合の経路情報の設定方法を図６を用いて説明する。図６は図５の状態から経路情報を追加した例である。経路情報の追加の場合は子ノード方向のノードに経路情報が存在するか確認するため、子ノードの情報を必要とする。そのため、経路管理テーブルＴＢＬ０の２分木ノード１００は子ノード情報（図２の子ノードへのポインタ１０２、１０３）を保持する。経路情報を追加するノードＡ００の子ノードＡ００１が経路情報を持つ場合は図６（ｂ）の１６分木ノードのＡ００１は＊Ａ００１の経路情報を優先する。経路情報を追加するノードＡ１１の子ノードＡ１１０が経路情報を持たない場合は図６（ｂ）の１６分木ノードのＡ１１０に＊Ａ１１の経路情報を設定する。
【００６２】次に経路情報の削除が発生した場合の経路情報の設定方法を図７を用いて説明する。図７は図５の状態から経路情報を削除した例である。経路情報の削除の場合は親ノード方向のノードに経路情報が存在するか確認するため、親ノードの情報を必要とする。そのため、経路管理テーブルの２分木ノード１００は親ノード情報（図２の親ノードへのポインタ１０１）を保持する。経路情報を削除するノードＡ１の子ノード方向のノードＡ１００が経路情報を持つ場合は図７（ｂ）の１６分木ノードのＡ１００は＊Ａ１００の経路情報をそのまま優先する。経路情報を削除するノードＡ０１０の親ノードＡ０１が経路情報を持っている場合は図７（ｂ）の１６分木ノードのＡ０１０に＊Ａ０１の経路情報を設定する。
【００６３】次に２のｐ乗分木ノード２００に存在する２分木ノードの数の変化（図４のステップＦＣ４）によって、該２のｐ乗分木ノードの追加、削除、変更の内、１つを選択する方法について説明する。
【００６４】２のｐ乗分木ノードの追加と削除について説明する。経路管理部Ｆ０は経路情報エントリの追加、削除によって、経路検索テーブルＴＢＬ１の初段を除いた２のｐ乗分木ノード２００に対して追加、削除、もしくは変更を行う。２のｐ乗分木ノードの追加、削除、変更は更新した後の２のｐ乗分木ノード内に含まれている２分木ノードの数によって決定する。経路情報エントリの追加、削除によって発生する４つのパターンを図８を用いて説明する。
【００６５】図８（ａ）は追加した２分木ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１内に２分木ノードＳＡ１以外にノードが存在しない場合（図４のステップＦＣ１１）である。この場合、新規に２のｐ乗分木ノードＬＡ１を作成し、経路検索テーブルＴＢＬ１に追加する（図４のステップＦＣ５）。
【００６６】図８（ｂ）は追加した２分木ノードＳＡ１を含む２のｐ乗分木ノードＬ１内に２分木ノードＳＡ１以外にノードＳ１が存在する場合（図４のステップＦＣ１３）である。この場合、既に２のｐ乗分木ノードＬ１は存在しているので、２のｐ乗分木ノードＬ１に経路情報を割り当てて、経路検索テーブルＴＢＬ１の２のｐ乗分木ノードＬ１を変更する（図４のステップＦＣ７）。
【００６７】図８（ｃ）は削除した２分木ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１内に２分木ノードが存在しなくなった場合（図４のステップＦＣ１２）である。この場合、２のｐ乗分木ノードＬＤ１は２分木ノードを持たなくなったので、経路検索テーブルＴＢＬ１の２のｐ乗分木ノードＬＤ１を削除する（図４のステップＦＣ６）。
【００６８】図８（ｄ）は削除した２分木ノードＳＤ１を含む２のｐ乗分木ノードＬ１内に２分木ノードが存在する場合（図４のステップＦＣ１３）である。この場合、２のｐ乗分木ノードＬ１は２分木ノードを持っているので、経路検索テーブルＴＢＬ１の２のｐ乗分木ノードＬ１を変更する（図４のステップＦＣ７）。
【００６９】次に経路検索テーブルＴＢＬ１の２のｐ乗分木の更新（図４のステップＦＣ８）方法について説明する。
【００７０】まず、２のｐ乗分木構造をとる経路検索テーブルＴＢＬ１に経路情報エントリＥを追加する方法について説明する。上述の参考技術の説明で２分木構造にエントリを追加すると４つの追加パターンで２分木ノードの更新が発生することを説明したが、２のｐ乗分木にその更新を反映させるためには１つまたは複数の２のｐ乗分木ノードを更新する必要がある。そのため、経路検索テーブルＴＢＬ１に対して２のｐ乗分木ノードを１つずつ追加、削除、変更を行う本実施の形態のルータ装置は、経路情報の追加の時は更新を必要とするノードの中で、親ノードから子ノード方向へ順番に更新することで、ノードの更新と更新の間に経路検索処理を可能にする。
【００７１】図９を用いて、経路検索テーブルＴＢＬ１における２のｐ乗分木ノードの追加方法を示す。図９（ａ）のノードＬ１，Ｌ２はノードＬ１が親ノードでノードＬ２が子ノードの関係である。図９（ｂ）はノードＬ２を子ノードにした追加ノードＬＡ１を経路検索テーブルＴＢＬ１上に書き込んだ状態である。この状態で経路検索処理を実行したとしても、ノードＬ１→Ｌ２の順に検索するので、通常と同様に検索処理を実行できる。図９（ｃ）はノードＬ１の子ノードのポインタをノードＬ２からノードＬＡ１に変更し、ノードの追加処理を完了する。
【００７２】以下にこのノードの追加順番規則に従って、４つの追加パターンの各々毎に更新する２のｐ乗分木ノードと順番について例を示す。
【００７３】図１０は（Ａ−１）における２のｐ乗分木の更新方法について示す。更新したノードはノードＳ１の１つである。図１０は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１を変更する。
【００７４】図１１は（Ａ−２）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＡ１，ＳＡ２の３つである。図１１（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＡ１，ＳＡ２を含む２のｐ乗分木ノードＬ１を変更する。図１１（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳ１，ＳＡ２を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ１を繋げるように変更する。図１１（ｃ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１，ＳＡ２を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ１を繋げるように変更する。図１１（ｄ）は３つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳＡ２を含む２のｐ乗分木ノードＬＡ２を追加し、ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ２を繋げるように変更する。
【００７５】図１２は（Ａ−３）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＡ１の２つである。図１２（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＡ１を含む２のｐ乗分木ノードＬ１を変更する。図１２R>２（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ１を繋げるように変更する。
【００７６】図１３は（Ａ−４）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＡ１の２つである。図１３（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＡ１を含む２のｐ乗分木ノードＬ１を変更する。図１３R>３（ｂ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木Ｌ２を変更し、ノードＳ１を含む２のｐ乗分木Ｌ１は更新しない。図１３R>３（ｃ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＡ１を含む２のｐ乗分木ノードＬＡ１を追加し、ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタにノードＬＡ１を繋げるように変更する。
【００７７】次に２のｐ乗分木構造をとる経路検索テーブルＴＢＬ１から経路情報エントリを削除する方法について説明する。上述の参考技術の説明で２分木構造にエントリを削除すると４つの削除パターンで２分木ノードの更新が発生する説明したが、エントリ追加時と同様に、２のｐ乗分木にその更新を反映させるためには１つまたは複数の２のｐ乗分木ノードを更新する必要がある。更新するノードの順番は更新するノードの中で子ノードから親ノードの方向へ更新することで、ノードの更新と更新の間に経路検索処理を可能にする。
【００７８】図１４を用いて、経路検索テーブルＴＢＬ１における２のｐ乗分木ノードの追加方法を示す。図１４R>４（ａ）のノードＬ１，ＬＤ１，Ｌ２はノードＬ１の子ノードがノードＬＤ１、ノードＬＤ１の子ノードがノードＬ２の関係である。図１４（ｂ）はノードＬ１の子ノードのポインタをノードＬＤ１からノードＬ２に変更した状態である。この状態で経路検索処理を実行したとしても、ノードＬ１→Ｌ２の順に検索するので、通常と同様に検索処理を実行できる。図１４（ｃ）はノードＬＤ１を削除し、ノードの削除処理を完了した状態を示す。
【００７９】以下にこのノードの削除順番規則に従って、４つの削除パターンの各々毎に更新する２のｐ乗分木ノードと順番について例を示す。
【００８０】図１５は（Ｄ−１）における２のｐ乗分木の更新方法について示す。更新したノードはノードＳ１の１つである。図１５は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１を変更する。
【００８１】図１６は（Ｄ−２）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＤ１，ＳＤ２の３つである。図１６（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＤ１，ＳＤ２を含む２のｐ乗分木ノードＬ１を変更する。図１６（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＤ２を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ１からノードＬ２に変更し、ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１を削除する。図１６（ｃ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ１からノードＬ２に変更し、ノードＳＤ１，ＳＤ２を含む２のｐ乗分木ノードＬＤ１を削除する。図１６（ｄ）は３つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ２からノードＬ２に変更し、ノードＳＤ２を含む２のｐ乗分木ノードＬＤ２を削除し、ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１を削除する。
【００８２】図１７は（Ｄ−３）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＤ１の２つである。図１７（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＤ１を含む２のｐ乗分木ノードＬ１を変更する。図１７R>７（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ１からＮＵＬＬに変更し、ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１を削除する。
【００８３】図１８は（Ｄ−４）における２のｐ乗分木の更新方法について示す。更新した２分木ノードはノードＳ１，ＳＤ１の２つである。図１８（ａ）は１つの２のｐ乗分木ノードを更新する場合である。ノードＳ１，ＳＤ１を含む２のｐ乗分木ノードＬ１を変更する。図１８R>８（ｂ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳＤ１を含む２のｐ乗分木Ｌ２を変更し、ノードＳ１を含む２のｐ乗分木Ｌ１は更新しない。図１８R>８（ｃ）は２つの２のｐ乗分木ノードを更新する場合である。ノードＳ１を含む２のｐ乗分木ノードＬ１の子ノードポインタをノードＬＤ１からノードＬ２に変更し、ノードＳＤ１を含む２のｐ乗分木ノードＬＤ１を削除する。
【００８４】次にマスク長０ビットから（ｍ−１）ビットの経路情報を追加、削除する場合（図４のステップＦＣ１０）、更新した２分木ノードの配下に存在する２のｐ乗分木ノードの経路情報を更新（図４のステップＦＣ３）する方法について説明する。経路情報の設定方法は以前に説明したｐ段分の２分木を２のｐ乗分木へ変換する方法で説明した方法と同様に親ノード方向のノードの経路情報よりも、子ノード方向のノードの経路情報を優先させ、子ノード方向のノードが経路情報を持たない時に、親ノード方向のノードが経路情報を持つ時はその経路情報を受け継ぐようにする。
【００８５】図１９を用いて、マスク長０ビットから（ｍ−１）ビットの経路情報を追加する方法について説明する。図１９（ａ）は２分木における初段ノードから第１２段ノードを１６分木における２の１３乗個の初段ノードとしている。図１９（ａ）の状態からノードＳ１に経路情報を追加すると図１９（ｂ）に示すようにＬ１，Ｌ２内で経路情報を設定していなかったノードＡ０００，Ａ１０１，Ａ１１０，Ａ１１１，Ｂ０００，Ｂ００１に経路情報＊Ｓ１を設定する。
【００８６】図２０を用いて、マスク長０ビットから（ｍ−１）ビットの経路情報を削除する方法について説明する。図２０（ａ）は２分木における初段ノードから第１２段ノードを１６分木における２の１３乗個の初段ノードにまとめている。図２０（ａ）の状態からノードＳ１の経路情報を削除すると図２０（ｂ）に示すようにＬ１，Ｌ２内の経路情報に＊Ｓ１を持つノードＡ０００，Ａ１０１，Ａ１１０，Ａ１１１，Ｂ０００，Ｂ００１の経路情報は無くなる。
【００８７】次に受信したパケット５１の宛先アドレスと制御経路情報を比較する処理方法について説明する。従来の経路検索テーブルはパケット中継に必要な経路情報のみを保持しているため、ルータが受信したパケット５１の宛先アドレスに対して、経路検索処理を行った後に、更にパケット中継に必要な経路情報以外の制御経路情報であるか確認する処理を行っていたが、本実施の形態のルータ装置では経路検索テーブルＴＢＬ１に制御経路情報も追加登録し、経路検索処理と制御経路情報であるかの確認を一度にできるようにした。
【００８８】図２１に付加機構部にパケットを転送する例を示す。ブロードキャストアドレスを宛先アドレスとするパケット５１に対して付加機構部Ｆ３で処理を実行したい場合、経路検索テーブルＴＢＬ１に制御経路情報としてブロードキャストアドレスを登録することで受信したパケット５１の宛先アドレスがブロードキャストアドレスである場合、そのパケット５１を経路検索部Ｆ１の経路検索処理でブロードキャストパケットであることを識別し、経路検索部Ｆ１はパケット５１を付加機構部Ｆ３に転送する。
【００８９】以上、詳細に説明したように本実施の形態のルータ装置によれば、初段を２のｍ乗個保持する２のｐ乗分木構造で経路情報を格納する経路検索テーブルＴＢＬ１を保持する経路検索部Ｆ１の前段に、経路情報を２分木構造で格納する経路管理テーブルＴＢＬ０を保持し、経路情報の追加、削除が発生した場合に、経路管理テーブルＴＢＬ０の２分木を、経路検索テーブルＴＢＬ１の２のｐ乗分木に変換する機能を有する経路管理部Ｆ０を設けることで、経路検索テーブルＴＢＬ１のメンテナンスを実現することができる。これにより、参考技術の経路検索方法では、アドレスの上位ビットから１ビットずつ検索していく２分木検索のテーブルで検索していたのに対して、２分木ノードｐ段分を１つの２のｐ乗分木ノードに集約した経路検索テーブルＴＢＬ１を用いて、ｐ段の検索を１回で行うことが可能になり、経路検索の高速化を図るのに効果がある。
【００９０】また、経路情報の追加、削除によって複数の経路情報を保持するノードの更新が発生した場合、図１４１４に例示したようにノードを更新する順番を考慮することで、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を実現することができる。これにより、検索処理中断時間を最小化する効果がある。
【００９１】また、パケット中継に必要な経路情報以外の制御経路情報を経路検索テーブルＴＢＬ１に追加登録することで、付加機構部Ｆ３に転送すべきパケット５１を受信した場合に、受信した経路検索部Ｆ１から付加機構部Ｆ３にパケット５１を転送し、付加機能を実現することができる。この実現により、制御経路情報の検索を経路情報の検索とは別に行わせる場合等に比較して、制御経路情報と経路情報の検索を同時に実行可能になり、検索処理の簡略化を図る効果がある。
【００９２】上記した特許請求の範囲に記載された以外の本発明の特徴を列挙すれば以下の通りである。
【００９３】すなわち、＜１＞ コンピュータネットワークシステム内のパケットを中継するルータ装置において、次に送信すべき装置のアドレス及びその装置が接続されている回線情報（以下経路情報と称す）を保持する経路検索テーブルを持ち、受信したパケットの宛先アドレスから、次に送信すべきルータ装置のアドレス及びそのルータ装置が接続されている回線情報または宛先アドレスが示すホストが接続されている回線情報を経路検索テーブルより検索する経路検索機能と、経路管理テーブルを持ち、経路検索テーブルの経路情報の更新を行う経路管理機能と、を有し、経路管理テーブルは、経路情報をアドレスのマスク長の昇順で２分木構造に格納し、経路情報を持つノードと分岐が発生するノードを残して縮退した構成をとり、経路検索テーブルは、１つの２分木ノードと、その直下につながる（ｐ−１）段分の合計（２のｐ乗―１）個分の２分木ノードを一つの２のｐ乗分木ノードに集約し、集約した最下段の２の（ｐ−１）乗個の２分木ノードに、そのノードより上段のノードに割り付けた経路情報を埋め込み、２のｐ乗分木ノードを、２分木を２の（ｐ−１）乗個分併せた形で構成する２のｐ乗分木構造に、アドレスのマスク長の昇順で格納し、経路情報を持つノードと分岐が発生するノードを残して縮退した構造をとり、経路管理部は、経路情報の追加、削除処理が発生した場合に、経路管理テーブルの２分木構造における２分木ノード間の親子関係から追加、削除、変更をする２分木ノードの位置を決定して２分木構造を更新し、２分木構造の更新結果より経路検索テーブルの２のｐ乗分木構造に対して追加、削除、変更の必要な２のｐ乗分木ノードを更新することを特徴とする経路検索テーブル作成方式。
【００９４】＜２＞ 項目＜１＞に記載の経路検索テーブル作成方式において、マスク長ｍビットの初段ノード２のｍ乗個分をそれぞれ、宛先アドレスの第０ビットから第ｍ−１ビットまでが取りうる値に１対１に対応させるとき、マスク長０ビットから（ｍ−１）ビットまでの経路情報について追加、削除を行う場合、該経路情報のマスク長で初段ノードのアドレスをマスクすると、経路情報のアドレスと一致する複数個の初段ノードが経路情報を持たない時に該経路情報を設定し、マスク長０ビットから（ｍ−１）ビットまでの経路情報について削除を行う場合、該経路情報を持つ初段ノードの経路情報を削除することで初段ノードを更新することを特徴とする経路検索テーブル作成方式。
【００９５】＜３＞ 項目＜１＞に記載の経路検索テーブル作成方式において、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合において、１つの経路情報の追加のため親子関係にあるノード間にノードを追加する場合、追加対象ノードと子ノードとを接続後、親ノードと追加対象ノードを接続し、１つの経路情報の削除のため親と子を持つノードを削除する場合、削除対象ノードの親ノードを削除対象ノードの子ノードと接続後、削除対象ノードを削除することで、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を実現することを特徴とする経路検索テーブル作成方式。
【００９６】＜４＞ 項目＜１＞または＜２＞に記載の経路検索テーブル作成方式において、経路管理機能と経路探索機能に更に機能を追加する場合、付加機構を新たに追加し、パケット中継に必要な経路情報以外の制御経路情報を経路検索テーブルに追加登録し、受信したパケットの宛先アドレスが制御経路情報と一致すると経路検索機能から付加機構にパケットを転送することで付加機能を実現することを特徴とする経路検索テーブル作成方式。
【００９７】以上本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【００９８】
【発明の効果】本発明の情報中継方法によれば、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に動的に変換して高速化を図ることができる、という効果が得られる。
【００９９】本発明の情報中継方法によれば、経路制御情報の更新に伴う経路検索停止時間を短縮して、中継制御の高速化を実現することができる、という効果が得られる。
【０１００】本発明の情報中継方法によれば、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に変換して高速化を図る場合において、２のｐ乗分木構造の動的な更新を、より短い経路検索停止時間で的確に行うことができる、という効果が得られる。
【０１０１】本発明の情報中継方法によれば、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合において、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を行うことで、検索中断時間を最小化することができる、という効果が得られる。
【０１０２】本発明の情報中継方法によれば、コンピュータネットワークの特別な機能に割り当てられた制御経路情報を経路検索テーブルに付加することにより、コンピュータネットワークの機能の拡張を容易にすることができる、という効果が得られる。
【０１０３】また、本発明の情報中継装置によれば、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に動的に変換して高速化を図ることができる、という効果が得られる。
【０１０４】本発明の情報中継装置によれば、経路制御情報の更新に伴う経路検索停止時間を短縮して、中継制御の高速化を実現することができる、という効果が得られる。
【０１０５】本発明の情報中継装置によれば、２分木構造によるＲａｄｉｓｈ Ｔｒｅｅを２のｐ乗分木構造に変換して高速化を図る場合において、２のｐ乗分木構造の動的な更新を、より短い経路検索停止時間で的確に行うことができる、という効果が得られる。
【０１０６】本発明の情報中継装置によれば、経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行う場合において、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を行うことで、検索中断時間を最小化することができる、という効果が得られる。
【０１０７】本発明の情報中継装置によれば、コンピュータネットワークの特別な機能に割り当てられた制御経路情報を経路検索テーブルに付加することにより、コンピュータネットワークの機能の拡張を容易にすることができる、という効果が得られる。
【図面の簡単な説明】
【図１】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置の構成の一例を示す機能ブロック図である。
【図２】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路管理テーブルの２分木ノードのデータ構造の一例を示す概念図である。
【図３】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルの２のｐ乗分木ノードのデータ構造の一例を示す概念図である。
【図４】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路情報の追加、削減を契機にした動作の一例を示すフローチャートである。
【図５】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路情報の２分木から１６分木への変換例を示す概念図である。
【図６】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加が発生した場合の処理の一例を示す概念図である。
【図７】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の削除が発生した場合の処理の一例を示す概念図である。
【図８】（ａ）〜（ｄ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加、削除によって発生する２のｐ乗分木の追加、削除、変更例を示す概念図である。
【図９】（ａ）〜（ｃ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの２のｐ乗分木ノードの追加方法の一例を示す概念図である。
【図１０】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１１】（ａ）〜（ｄ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１２】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１３】（ａ）〜（ｃ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置において、経路情報の追加によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１４】（ａ）〜（ｃ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの２のｐ乗分木ノードの削除方法の一例を示す概念図である。
【図１５】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの経路情報の削除によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１６】（ａ）〜（ｄ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの経路情報の削除によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１７】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの経路情報の削除によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１８】（ａ）〜（ｃ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路検索テーブルでの経路情報の削除によって発生する２のｐ乗分木ノードの更新処理の一例を示す概念図である。
【図１９】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路情報の追加処理の一例を示す概念図である。
【図２０】（ａ）および（ｂ）は、本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における経路情報の削除処理の一例を示す概念図である。
【図２１】本発明の情報中継方法を実施する情報中継装置の一実施の形態であるルータ装置における受信パケットの付加機構部への転送手順の一例を示す概念図である。
【図２２】本発明の参考技術であるルータ装置の構成および作用の一例を示す概念図である。
【図２３】本発明の参考技術であるルータ装置における経路制御テーブルで用いられるデータ構造を説明する概念図である。
【図２４】本発明の参考技術であるルータ装置における経路情報テーブルの構成を説明する概念図である。
【図２５】本発明の参考技術であるルータ装置の作用を説明する概念図である。
【図２６】本発明の参考技術であるルータ装置の作用を説明する概念図である。
【図２７】（ａ）および（ｂ）は、本発明の参考技術であるルータ装置の作用を説明する概念図である。
【図２８】（ａ）および（ｂ）は、本発明の参考技術であるルータ装置の作用を説明する概念図である。
【図２９】本発明の参考技術であるルータ装置の作用を説明する概念図である。
【符号の説明】
５０…ポート、５１…パケット、１００…２分木ノード、１０１…親ノードへのポインタ、１０２…子ノードへのポインタ、１０３…子ノードへのポインタ、１０４…フラグ、１０５…フラグ、１０６…子のノードのマスク長、１０７…子のノードのマスク長、１０８…サブネットワークアドレス、１０９…次ホップアドレス、１１０…出力ポート番号、２００…２のｐ乗分木ノード、２０１…子ノードへのポインタ、２０２…フラグ、２０３…子のノードのマスク長、２０４…サブネットワークアドレス、２０５…次ホップアドレス、２０６…出力ポート番号、ＣＥ…制御経路情報エントリ、Ｅ…経路情報エントリ、Ｆ０…経路管理部、Ｆ１…経路検索部、Ｆ３…付加機構部、ＴＢＬ０…経路管理テーブル、ＴＢＬ１…経路検索テーブル。
【特許請求の範囲】
【請求項１】 コンピュータネットワーク内におけるパケットの中継を行う複数の情報中継装置の各々に、前記パケットを次に送信すべき中継先のアドレスおよび当該中継先に対応した回線情報を含む経路情報を保持する経路制御テーブルを持たせ、個々の前記情報中継装置では、受信した前記パケットの宛先アドレスにて前記経路制御テーブルを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定する情報中継方法であって、前記経路制御テーブルを、前記経路情報を前記アドレスのマスク長の昇順で２分木構造の各２分木ノードに格納し、前記経路情報を持つ２分木ノードと分岐が発生する２分木ノードを残して縮退した構成をとる経路管理テーブルと、１つの２分木ノードと、その直下につながる（ｐ−１）段分の合計（２のｐ乗―１）個分の２分木ノードを１つの２のｐ乗分木ノードに集約し、集約した最下段の２の（ｐ−１）乗個の２分木ノードに、その２分木ノードより上段の２分木ノードに割り付けた前記経路情報を埋め込み、２のｐ乗分木ノードを、２分木を２の（ｐ−１）乗個分併せた形で構成する２のｐ乗分木構造に前記アドレスのマスク長の昇順で格納し、前記経路情報を持つ２のｐ乗分木ノードと分岐が発生する２のｐ乗分木ノードを残して縮退した構造をとる経路検索テーブルと、で構成し、前記経路情報の追加、削除、変更が発生した場合に、前記経路管理テーブルの前記２分木構造における２分木ノード間の親子関係から追加、削除、変更を行うべき２分木ノードの位置を決定して前記２分木構造を更新し、前記２分木構造の更新結果に基づいて、前記経路検索テーブルの前記２のｐ乗分木構造に対して追加、削除、変更の必要な前記２のｐ乗分木ノードを更新し、受信した前記パケットの宛先アドレスにて前記経路検索テーブルの前記２のｐ乗分木ノードを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定することを特徴とする情報中継方法。
【請求項２】 請求項１記載の情報中継方法において、前記経路検索テーブルでは、マスク長ｍビットの初段ノード２のｍ乗個分をそれぞれ、宛先アドレスの第０ビットから第ｍ−１ビットまでが取りうる値に１対１に対応させるとき、マスク長０ビットから（ｍ−１）ビットまでの前記経路情報について追加を行う場合、当該経路情報のマスク長で前記初段ノードのアドレスをマスクすると、当該経路情報のアドレスと一致する複数個の前記初段ノードが経路情報を持たない時に当該経路情報を設定し、マスク長０ビットから（ｍ−１）ビットまでの前記経路情報について削除を行う場合、当該経路情報を持つ前記初段ノードの経路情報を削除することで前記初段ノードを更新する操作、前記経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行うとき、１つの前記経路情報の追加のため親子関係にあるノード間にノードを追加する場合、追加対象ノードと子ノードとを接続後、親ノードと追加対象ノードを接続し、１つの経路情報の削除のため親と子を持つノードを削除する場合、削除対象ノードの親ノードを削除対象ノードの子ノードと接続後、削除対象ノードを削除することで、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を実現する操作、パケット中継に必要な前記経路情報以外の制御経路情報を前記経路情報と等化な形式で経路検索テーブルに追加登録するとともに、前記制御経路情報に対応した特定の付加機能を担う付加機構に前記パケットが転送されるように前記制御経路情報に含まれる前記アドレスおよび回線情報を設定し、受信したパケットの宛先アドレスにて前記経路検索テーブルに登録されている前記経路情報および前記制御経路情報を検索し、前記制御経路情報と一致する場合には前記付加機構にパケットを転送して、前記付加機能を実現する操作、の少なくとも一つの操作を行うことを特徴とする情報中継方法。
【請求項３】 コンピュータネットワーク内のパケットを中継する情報中継装置であって、前記パケットを次に送信すべき中継先のアドレスおよび当該中継先に対応した回線情報を含む経路情報を保持する経路制御テーブルと、前記経路制御テーブルの内容を更新する経路管理部と、受信した前記パケットの宛先アドレスにて前記経路制御テーブルを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定する経路検索部と、を備え、前記経路管理部では、前記経路制御テーブルとして、前記経路情報を前記アドレスのマスク長の昇順で２分木構造の各２分木ノードに格納し、前記経路情報を持つ２分木ノードと分岐が発生する２分木ノードを残して縮退した構成をとる経路管理テーブルを持ち、前記経路検索部では、前記経路制御テーブルとして、１つの２分木ノードと、その直下につながる（ｐ−１）段分の合計（２のｐ乗―１）個分の２分木ノードを１つの２のｐ乗分木ノードに集約し、集約した最下段の２の（ｐ−１）乗個の２分木ノードに、その２分木ノードより上段の２分木ノードに割り付けた前記経路情報を埋め込み、２のｐ乗分木ノードを、２分木を２の（ｐ−１）乗個分併せた形で構成する２のｐ乗分木構造に前記アドレスのマスク長の昇順で格納し、前記経路情報を持つ２のｐ乗分木ノードと分岐が発生する２のｐ乗分木ノードを残して縮退した構造をとる経路検索テーブルを持ち、前記経路管理部は、前記経路情報の追加、削除、変更が発生した場合に、前記経路管理テーブルの前記２分木構造における２分木ノード間の親子関係から追加、削除、変更を行うべき２分木ノードの位置を決定して前記２分木構造を更新し、前記２分木構造の更新結果に基づいて、前記経路検索テーブルの前記２のｐ乗分木構造に対して追加、削除、変更の必要な前記２のｐ乗分木ノードを更新する操作を行い、前記経路検索部は、受信した前記パケットの宛先アドレスにて前記経路検索テーブルを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定する操作を行う、ようにしたことを特徴とする情報中継装置。
【請求項１】 コンピュータネットワーク内におけるパケットの中継を行う複数の情報中継装置の各々に、前記パケットを次に送信すべき中継先のアドレスおよび当該中継先に対応した回線情報を含む経路情報を保持する経路制御テーブルを持たせ、個々の前記情報中継装置では、受信した前記パケットの宛先アドレスにて前記経路制御テーブルを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定する情報中継方法であって、前記経路制御テーブルを、前記経路情報を前記アドレスのマスク長の昇順で２分木構造の各２分木ノードに格納し、前記経路情報を持つ２分木ノードと分岐が発生する２分木ノードを残して縮退した構成をとる経路管理テーブルと、１つの２分木ノードと、その直下につながる（ｐ−１）段分の合計（２のｐ乗―１）個分の２分木ノードを１つの２のｐ乗分木ノードに集約し、集約した最下段の２の（ｐ−１）乗個の２分木ノードに、その２分木ノードより上段の２分木ノードに割り付けた前記経路情報を埋め込み、２のｐ乗分木ノードを、２分木を２の（ｐ−１）乗個分併せた形で構成する２のｐ乗分木構造に前記アドレスのマスク長の昇順で格納し、前記経路情報を持つ２のｐ乗分木ノードと分岐が発生する２のｐ乗分木ノードを残して縮退した構造をとる経路検索テーブルと、で構成し、前記経路情報の追加、削除、変更が発生した場合に、前記経路管理テーブルの前記２分木構造における２分木ノード間の親子関係から追加、削除、変更を行うべき２分木ノードの位置を決定して前記２分木構造を更新し、前記２分木構造の更新結果に基づいて、前記経路検索テーブルの前記２のｐ乗分木構造に対して追加、削除、変更の必要な前記２のｐ乗分木ノードを更新し、受信した前記パケットの宛先アドレスにて前記経路検索テーブルの前記２のｐ乗分木ノードを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定することを特徴とする情報中継方法。
【請求項２】 請求項１記載の情報中継方法において、前記経路検索テーブルでは、マスク長ｍビットの初段ノード２のｍ乗個分をそれぞれ、宛先アドレスの第０ビットから第ｍ−１ビットまでが取りうる値に１対１に対応させるとき、マスク長０ビットから（ｍ−１）ビットまでの前記経路情報について追加を行う場合、当該経路情報のマスク長で前記初段ノードのアドレスをマスクすると、当該経路情報のアドレスと一致する複数個の前記初段ノードが経路情報を持たない時に当該経路情報を設定し、マスク長０ビットから（ｍ−１）ビットまでの前記経路情報について削除を行う場合、当該経路情報を持つ前記初段ノードの経路情報を削除することで前記初段ノードを更新する操作、前記経路検索テーブルの２のｐ乗分木ノードを１エントリ毎に追加、削除、変更を行うとき、１つの前記経路情報の追加のため親子関係にあるノード間にノードを追加する場合、追加対象ノードと子ノードとを接続後、親ノードと追加対象ノードを接続し、１つの経路情報の削除のため親と子を持つノードを削除する場合、削除対象ノードの親ノードを削除対象ノードの子ノードと接続後、削除対象ノードを削除することで、経路検索に必要なノードを木構造から分離すること無くノードの追加、削除を実現する操作、パケット中継に必要な前記経路情報以外の制御経路情報を前記経路情報と等化な形式で経路検索テーブルに追加登録するとともに、前記制御経路情報に対応した特定の付加機能を担う付加機構に前記パケットが転送されるように前記制御経路情報に含まれる前記アドレスおよび回線情報を設定し、受信したパケットの宛先アドレスにて前記経路検索テーブルに登録されている前記経路情報および前記制御経路情報を検索し、前記制御経路情報と一致する場合には前記付加機構にパケットを転送して、前記付加機能を実現する操作、の少なくとも一つの操作を行うことを特徴とする情報中継方法。
【請求項３】 コンピュータネットワーク内のパケットを中継する情報中継装置であって、前記パケットを次に送信すべき中継先のアドレスおよび当該中継先に対応した回線情報を含む経路情報を保持する経路制御テーブルと、前記経路制御テーブルの内容を更新する経路管理部と、受信した前記パケットの宛先アドレスにて前記経路制御テーブルを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定する経路検索部と、を備え、前記経路管理部では、前記経路制御テーブルとして、前記経路情報を前記アドレスのマスク長の昇順で２分木構造の各２分木ノードに格納し、前記経路情報を持つ２分木ノードと分岐が発生する２分木ノードを残して縮退した構成をとる経路管理テーブルを持ち、前記経路検索部では、前記経路制御テーブルとして、１つの２分木ノードと、その直下につながる（ｐ−１）段分の合計（２のｐ乗―１）個分の２分木ノードを１つの２のｐ乗分木ノードに集約し、集約した最下段の２の（ｐ−１）乗個の２分木ノードに、その２分木ノードより上段の２分木ノードに割り付けた前記経路情報を埋め込み、２のｐ乗分木ノードを、２分木を２の（ｐ−１）乗個分併せた形で構成する２のｐ乗分木構造に前記アドレスのマスク長の昇順で格納し、前記経路情報を持つ２のｐ乗分木ノードと分岐が発生する２のｐ乗分木ノードを残して縮退した構造をとる経路検索テーブルを持ち、前記経路管理部は、前記経路情報の追加、削除、変更が発生した場合に、前記経路管理テーブルの前記２分木構造における２分木ノード間の親子関係から追加、削除、変更を行うべき２分木ノードの位置を決定して前記２分木構造を更新し、前記２分木構造の更新結果に基づいて、前記経路検索テーブルの前記２のｐ乗分木構造に対して追加、削除、変更の必要な前記２のｐ乗分木ノードを更新する操作を行い、前記経路検索部は、受信した前記パケットの宛先アドレスにて前記経路検索テーブルを検索して得られた前記経路情報に基づいて次に前記パケットを送出すべき前記中継先を決定する操作を行う、ようにしたことを特徴とする情報中継装置。
【図１】
【図１０】
【図１５】
【図２４】
【図２】
【図３】
【図５】
【図８】
【図１２】
【図１３】
【図１７】
【図４】
【図６】
【図９】
【図１１】
【図１８】
【図７】
【図１４】
【図１６】
【図１９】
【図２０】
【図２１】
【図２６】
【図２２】
【図２３】
【図２５】
【図２９】
【図２７】
【図２８】
【図１０】
【図１５】
【図２４】
【図２】
【図３】
【図５】
【図８】
【図１２】
【図１３】
【図１７】
【図４】
【図６】
【図９】
【図１１】
【図１８】
【図７】
【図１４】
【図１６】
【図１９】
【図２０】
【図２１】
【図２６】
【図２２】
【図２３】
【図２５】
【図２９】
【図２７】
【図２８】
【公開番号】特開２０００−１８８６０８（Ｐ２０００−１８８６０８Ａ）
【公開日】平成１２年７月４日（２０００．７．４）
【国際特許分類】
【出願番号】特願平１０−３６２９８７
【出願日】平成１０年１２月２１日（１９９８．１２．２１）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成１２年７月４日（２０００．７．４）
【国際特許分類】
【出願日】平成１０年１２月２１日（１９９８．１２．２１）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]