(57)【要約】【課題】ソースルーティングにおいて必要なデータのサイズを抑える。【解決手段】ネットワークの経路情報を保持しない、ネットワーク中のノードを管理する管理装置により実行される経路決定方法は、パケットの送信元ノードと宛先ノードとを特定するノード特定ステップと、ネットワークにおいて予め定められた基点ノードについての最短経路データを格納する経路データ格納部から、送信元ノードから基点ノードへの最短経路である第１の経路と宛先ノードから基点ノードへの最短経路である第２の経路とを特定する部分経路特定ステップと、第１の経路及び第２の経路の末尾からの重複部分を第１の経路及び第２の経路から削除すると共に削除後の第２の経路を逆順にして削除後の第１の経路及び重複部分において最も先頭に近いノードに連結することにより、送信元ノードから宛先ノードへの第３の経路を特定するステップとを含む。【選択図】図１
2010199646.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークの経路情報を保持しない、前記ネットワーク中のノードを管理する管理装置により実行される経路決定プログラムであって、
パケットの送信元ノードと宛先ノードとを特定するノード特定ステップと、
前記ネットワークにおいて予め定められた基点ノードについての最短経路データを格納する経路データ格納部から、前記送信元ノードから前記基点ノードへの最短経路である第１の経路と前記宛先ノードから前記基点ノードへの最短経路である第２の経路とを特定する部分経路特定ステップと、
前記第１の経路及び前記第２の経路の末尾からの重複部分を前記第１の経路及び前記第２の経路から削除すると共に削除後の前記第２の経路を逆順にして削除後の前記第１の経路及び前記重複部分において最も先頭に近いノードに連結することにより、前記送信元ノードから前記宛先ノードへの第３の経路を特定するステップと、
を前記管理装置に実行させるための経路決定プログラム。
【請求項２】
前記ネットワーク中の隣接ノード間の接続データを格納する二地点間接続データ格納部から、前記第３の経路において前記送信元ノードから順番に連続する２ノードの各組み合わせについて、該当する接続データを読み出し、前記送信元ノードに通知するステップ
をさらに実行させるための請求項１記載の経路決定プログラム。
【請求項３】
前記送信元ノード又は前記宛先ノードが前記基点ノードと一致しているか判断するステップと、
一致していないと判断された場合には前記部分経路特定ステップ以降を実施させるステップと、
一致していると判断された場合には前記経路データ格納部から前記送信元ノードから前記基点ノードへの最短経路又は前記基点ノードから前記宛先ノードへの最短経路を前記第３の経路として特定するステップと、
をさらに含む請求項１又は２記載の経路決定プログラム。
【請求項４】
前記ノード特定ステップが、
前記送信元ノードから送信先ＩＰアドレスを受信するステップと、
前記ネットワーク中の各ノードのＩＰアドレスに対応付けてノードＩＤが格納されているノードＩＤデータ格納部から、前記送信先ＩＰアドレスに対応するノードＩＤを特定するステップと、
を含む請求項１乃至３のいずれか１つ記載の経路決定プログラム。
【請求項５】
ネットワークの経路情報を保持しない、前記ネットワーク中のノードを管理する管理装置であって、
パケットの送信元ノードと宛先ノードとを特定する手段と、
前記ネットワークにおいて予め定められた基点ノードについての最短経路データを格納する経路データ格納部と、
前記経路データ格納部から、前記送信元ノードから前記基点ノードへの最短経路である第１の経路と前記宛先ノードから前記基点ノードへの最短経路である第２の経路とを特定する手段と、
前記第１の経路及び前記第２の経路の末尾からの重複部分を前記第１の経路及び前記第２の経路から削除すると共に削除後の前記第２の経路を逆順にして削除後の前記第１の経路及び前記重複部分において最も先頭に近いノードに連結することにより、前記送信元ノードから前記宛先ノードへの第３の経路を特定する手段と、
を有する管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、コンピュータ・ネットワークにおけるソースルーティング技術に関する。
【背景技術】
【０００２】
ソースルーティングを行う際には、ルーティングに必要な情報（以下、事前に準備する必要がある情報なので事前情報と呼ぶ）をメモリに格納しておく必要がある。この事前情報のサイズは、ネットワークの規模が大きくなると共に大きくなり、その増加に比例して消費電力が増加する。
【０００３】
一般的に、ソースルーティングの事前情報としては、ダイクストラの最短経路グラフの情報などが用いられるが、このサイズはルータ数の二乗に比例する。ルータ数が多い大規模ネットワークでは大量のメモリが必要となる。そして、ネットワーク規模が大きくなると、ホップバイホップ（Hop-by-Hop）という周知のルーティング方法よりも事前情報のサイズが大きくなってしまう。
【０００４】
また、ソースルーティングで経路決定処理の計算量を削減する方式には以下のようなものがある。すなわち、ルーティングプロトコルのエリア内において、あるソースノードから上記エリア内の各宛先ノードまでの候補経路を計算する際に、まず、上記エリアを複数の仮想的なサブエリアに分割し、各サブエリア内の候補経路を計算する。そして、ソースノードを含まないサブエリア内の宛先ノードに対してサブエリア間の境界ノードにおいて各サブエリア内の候補経路の関連付けを行ってソースノードから各宛先ノードまでの候補経路を作成する。但し、宛先ノード及びソースノードが変更されれば、ダイクストラの計算を再度行わなければならないので、計算量を十分に少なくできているわけではない。また、経路情報を各ノードに保持しており、上で述べたようなデータサイズの問題は解決されていない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００２−１５２２５２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
以上のように、従来技術ではソースルーティングにおいて必要な事前情報のサイズが大きくなってしまうという問題を解決するものはない。
【０００７】
従って、本技術の目的は、ソースルーティングにおいて必要なデータのサイズを抑えるための技術を提供することである。
【課題を解決するための手段】
【０００８】
ネットワークの経路情報を保持しない、ネットワーク中のノードを管理する管理装置により実行される経路決定方法は、パケットの送信元ノードと宛先ノードとを特定するノード特定ステップと、ネットワークにおいて予め定められた基点ノードについての最短経路データを格納する経路データ格納部から、送信元ノードから基点ノードへの最短経路である第１の経路と宛先ノードから基点ノードへの最短経路である第２の経路とを特定する部分経路特定ステップと、第１の経路及び第２の経路の末尾からの重複部分を第１の経路及び第２の経路から削除すると共に削除後の第２の経路を逆順にして削除後の第１の経路及び重複部分において最も先頭に近いノードに連結することにより、送信元ノードから宛先ノードへの第３の経路を特定するステップとを含む。
【図面の簡単な説明】
【０００９】
【図１】図１は、ネットワーク構成の一例を示す図である。
【図２】図２は、エッジルータの機能ブロック図である。
【図３】図３は、中継ルータの機能ブロック図である。
【図４】図４は、管理サーバの機能ブロック図である。
【図５】図５は、ノードデータ格納部に格納されるデータの一例を示す図である。
【図６】図６は、最短経路データテーブル格納部に格納されるデータの一例を示す図である。
【図７】図７（ａ）乃至（ｄ）は、従来必要となった最短経路データテーブル格納部に格納されるデータについて説明する図である。
【図８】図８は、二地点間接続データ格納部に格納されるデータの一例を示す図である。
【図９】図９は、ネットワークにおける処理フローを示す図である。
【図１０】図１０は、経路計算処理の処理フローを示す図である。
【図１１】図１１は、第１の事例の経路について説明するための模式図である。
【図１２】図１２は、第２の事例の経路について説明するための模式図である。
【図１３】図１３は、第２の事例の経路の処理について説明するための模式図である。
【図１４】図１４は、経路計算処理の処理フローを示す図である。
【図１５】図１５は、経路の具体例を示す模式図である。
【図１６】図１６は、全体の接続データの一例を示す図である。
【図１７】図１７は、ネットワークにおける処理フローを示す図である。
【図１８】図１８は、エッジルータ「３」から中継ルータ「６」に送信されるパケットの一例を示す図である。
【図１９】図１９は、中継ルータ「６」からエッジルータ「４」に送信されるパケットの一例を示す図である。
【図２０】図２０は、エッジルータ「４」からユーザ端末に送信されるパケットの一例を示す図である。
【図２１】図２１は、コンピュータの機能ブロック図である
【発明を実施するための形態】
【００１０】
図１に本技術の実施の形態に係るシステム概要図を示す。本実施の形態では、説明をわかりやすくするため、図１に示すように、ルータ１０１がルータ１０２及び１０５と接続され、ルータ１０５がルータ１０６と接続され、ルータ１０６がルータ１０３及び１０４に接続されるようなネットワークを想定する。当然ながらこれは簡単なネットワークの一例であるから、ネットワーク構成はこのようなものに限定されるものではない。ここで、ルータ１０１乃至１０４は、ユーザ端末１５１乃至１５４に接続されている。このようにユーザ端末１５１乃至１５４などの他のＩＰネットワークに接続されるルータ１０１乃至１０４をエッジルータ又はエッジノードと呼び、他のＩＰネットワークに接続されないルータ１０５及び１０６を中継ルータと呼ぶ。また、ルータについてはノードとも呼ぶことにする。
【００１１】
本実施の形態では、これらのエッジルータ１０１乃至１０４は、制御線（図１では点線）によって、本実施の形態における主要な処理、すなわち経路を決定する処理を実施する管理サーバ１１１に接続されている。
【００１２】
エッジルータの構成について図２を用いて説明する。例えばエッジルータ１０１は、例えばユーザ端末１５１から受信したパケットを一旦保存するためのパケットバッファ１０１２と、管理サーバ１１１から以前に受信した経路についての具体的データを表す接続データ（以下で詳細に説明するが、出力すべきインタフェースのデータ及び宛先アドレスの１又は複数の組み合わせ）を保存しておくための取得済み接続データ格納部１０１３と、受信したパケットの接続データを管理サーバ１１１等から取得する処理、送出するパケットに必要な接続データを付加する処理、パケットを出力すべきインタフェースを特定する処理等を実施する接続データ処理部１０１１とを有する。接続データ処理部１０１１は、取得した接続データのうち、送出するパケットに必要な接続データを付加する接続データ付加部１０２１と、パケットを出力すべきインタフェースを特定する処理を実施する自ノードデータ取得部１０２２とを有する。このように管理サーバ１１１において一回取得された接続データについては再利用のために蓄積されるが、ルータ間の接続関係及び当該ノードへの経路データというものは、エッジルータには保持されない。
【００１３】
また、中継ルータの構成について図３を用いて説明する。例えば中継ルータ１０５は、接続データ処理部１０５１を有し、接続データ処理部１０５１は、受信したパケットを出力すべきインタフェースを特定する処理を実施する自ノードデータ取得部１０５２を有する。なお、中継ルータであってもエッジルータとしても用いられるようなものであれば、図２に示すようなエッジルータの機能を有するようにする。このように、ルータ間の接続関係及び当該ノードへの経路データというものは、中継ルータにも保持されない。
【００１４】
次に、管理サーバ１１１の構成について図４を用いて説明する。管理サーバ１１１は、エッジルータからの要求に応じて送信元ノードから宛先ノードまでの経路を特定し、当該経路のための接続データを抽出する処理を実施する経路算出部１１１１と、所定の基点ノード（ネットワーク中の任意のノードでよいが、最も接続の多いノードが好ましい）への最短経路を決定するための最短経路データテーブルを格納する最短経路データテーブル格納部１１１２と、特定の２ノード間の接続データを格納する二地点間接続データ格納部１１１３と、ＩＰアドレスの範囲とノード番号（ノードＩＤとも呼ぶ）との対応関係を格納するノードデータ格納部１１１４とを有する。経路算出部１１１１は、送信元ノード及び宛先ノードを特定するノード特定処理部１１２１と、送信元ノードから宛先ノードまでの経路を特定する経路特定処理部１１２２と、特定された経路についての接続データを抽出する接続データ抽出部１１２３とを有する。
【００１５】
ノードデータ格納部１１１４には、例えば図５に示すようなデータが格納されている。図５の例では、宛先ＩＰアドレス範囲（例えば６４ビット）と宛先ノード番号（例えば１６ビット）との対応関係が登録されている。例えば、宛先ＩＰアドレスが１０．０．１．０／２４の範囲であれば、宛先ノード番号は「１」であることが分かる。本実施の形態では、以下の説明をわかりやすくするために、ルータ１０１のノード番号は「１」であり、ルータ１０２のノード番号は「２」であり、ルータ１０３のノード番号は「３」であり、ルータ１０４のノード番号は「４」であり、ルータ１０５のノード番号は「５」であり、ルータ１０６のノード番号は「６」であるものとする。
【００１６】
また、最短経路データテーブル格納部１１１２に格納されるデータの一例を図６に示す。最短経路データテーブル格納部１１１２は、ダイクストラ法などによりネットワーク中の任意のノードから基点ノードに至るまでの最短経路を特定するためのデータを格納しており、任意のノードのためのノード番号の列（例えば１６ビット）と、最短経路上当該任意のノードの基点ノード寄りのノード番号である前ノード番号の列（例えば１６ビット）とを有する。本実施の形態では、ノード番号「１」のノードを基点ノードとしている。例えば、ノード「６」から基点ノード「１」への経路は、ノード番号の列においてノード番号「６」の行を特定して、対応する前ノード番号「５」を取得し、次にノード番号の列においてノード番号「５」の行を特定して、対応する前ノード番号「１」を取得する。このように、ノード「６」からノード「１」への最短経路は、ノード番号系列「６−５−１」というものになる。すなわち、最短経路を得るためには、目的ノードのノード番号から順次最短経路データテーブル格納部１１１２のテーブルを基点ノードに至るまで辿る処理を行う。なお、基点ノードのノード番号については、管理サーバ１１１の図示しないデータ記憶装置に格納されており、処理において用いられる。
【００１７】
なお、一般的なソースルーティングでは、図７（ａ）乃至（ｄ）に示すように、各エッジノードにおいて、図６と同様のデータを保持する必要がある。すなわち、エッジノード１０１（ノード番号「１」）には、図７（ａ）左側に示すようなデータを保持し、右側に示すように、任意のノードからノード番号「１」のノードに向かうような探索を可能としている。同様に、エッジノード１０２（ノード番号「２」）には、図７（ｂ）左側に示すようなデータを保持し、右側に示すように、任意のノードからノード番号「２」のノードに向かうような探索を可能としている。さらに、エッジノード１０３（ノード番号「３」）には、図７（ｃ）左側に示すようなデータを保持し、右側に示すように、任意のノードからノード番号「３」のノードに向かうような探索を可能としている。また、エッジノード１０４（ノード番号「４」）には、図７（ｄ）左側に示すようなデータを保持し、右側に示すように、任意のノードからノード番号「４」のノードに向かうような探索を可能としている。このように、図６の４倍（エッジノード数）のデータが必要となる。
【００１８】
さらに、二地点間接続データ格納部１１１３には、図８に示すようなデータが格納されている。図８のテーブル例では、出力元ノードＡの列（例えば１６ビット）と、出力先ノードＢの列（例えば１６ビット）と、出力元ノードＡから出力先ノードＢへパケットを出力する際のインタフェース（Ｉ／Ｆ）・データの列（例えば３２ビット）と、出力元ノードＡから出力先ノードＢへパケットを出力する際の宛先アドレスの列（例えば３２ビット）とを有する。例えば、ノード「１」からノード「２」へパケットを出力する際には、「２０．０．０．１」というインタフェース・データ（ポート番号などでもよい）及び「２０．０．０．２」という宛先アドレスとの組み合わせである接続データが抽出される。なお、各ルータは、インタフェース・データ及び宛先アドレスを与えれば、いずれのポート（すなわちインタフェース）に対してどのような宛先（例えばＭＡＣアドレス）で送出すればよいのかを特定するための周知の機構を有しているものとする。また、図８のテーブル中、「（ｄｅｓｔ）」は、パケットの宛先アドレスを用いることを表している。
【００１９】
次に、図９乃至図２０を用いて図１に示したネットワーク・システムの処理内容について説明する。まず、例えばエッジルータに接続されているユーザ端末は、送信元ＩＰアドレスと宛先ＩＰアドレスとをパケットヘッダに含むパケットを、接続されているエッジルータに送信する（ステップＳ１）。エッジルータは、ユーザ端末からパケットを受信し、パケットバッファ１０１２に格納する（ステップＳ３）。そして、エッジルータの接続データ処理部１０１１は、宛先ＩＰアドレスで取得済み接続データ格納部１０１３を検索して該当する接続データが登録されているか否かを判断することによって、経路生成済みであるか判断する（ステップＳ５）。経路生成済みである場合には、接続データ処理部１０１１は、該当する接続データを取得済み接続データ格納部１０１３から読み出す（ステップＳ９）。そして処理は端子Ａを介して図１７の処理に移行する。
【００２０】
一方、経路生成済みではない、すなわち該当する接続データが取得済み接続データ格納部１０１３に格納されていない場合には、接続データ処理部１０１１は、メモリなどに保持している自ルータＩＤとパケットの宛先ＩＰアドレスとを含む経路生成要求を管理サーバ１１１に送信する（ステップＳ７）。管理サーバ１１１の経路算出部１１１１は、自ルータＩＤとパケットの宛先ＩＰアドレスとを含む経路生成要求を受信し、例えばメインメモリなどの記憶装置に格納する（ステップＳ１１）。そして、経路算出部１１１１は、経路計算処理を実施する（ステップＳ１３）。経路計算処理については、図１０乃至図１６を用いて説明する。
【００２１】
経路算出部１１１１のノード特定処理部１１２１は、ノードデータ格納部１１１４から、パケットの宛先ＩＰアドレスに対応する宛先ノード番号を読み出す（ステップＳ２１）。そして、経路特定処理部１１２２は、宛先ノード番号又は送信元ノード番号が基点ノード番号と等しいか判断する（ステップＳ２３）。
【００２２】
宛先ノード番号又は送信元ノード番号が基点ノード番号と等しい場合には、特別な処理は必要ない。すなわち、経路特定処理部１１２２は、送信元ノードから宛先ノードへの最短経路Ｘを、最短経路データテーブル格納部１１１２を用いて特定し、例えばメインメモリなどの記憶装置に格納する（ステップＳ２５）。宛先ノード番号が基点ノード番号に等しい場合には、送信元ノード番号から順次最短経路データテーブル格納部１１１２を探索して基点ノード番号までたどり着けば、最短経路Ｘが得られる。送信元ノード番号が基点ノード番号に等しい場合には、送信元ノード番号を終点ノード番号とし、宛先ノード番号を起点ノード番号として、起点ノード番号から最短経路データテーブル格納部１１１２を探索して終点ノード番号までたどり着いたら、順番を逆順に入れ替えれば、基点ノードから宛先ノードへの最短経路Ｘを得ることができる。処理は端子Ｂを介して図１４の処理に移行する。
【００２３】
一方、宛先ノード番号又は送信元ノード番号が基点ノード番号と等しくない場合には、経路特定処理部１１２２は、送信元ノードから基点ノードへの最短経路Ａを、最短経路データテーブル格納部１１１２を送信元ノード番号から基点ノード番号まで探索してゆくことによって特定し、例えばメインメモリなどの記憶装置に格納する（ステップＳ２７）。さらに、経路特定処理部１１２２は、宛先ノードから基点ノードへの最短経路Ｂを、最短経路データテーブル格納部１１１２を宛先ノード番号から基点ノード番号まで探索してゆくことによって特定し、例えばメインメモリなどの記憶装置に格納する（ステップＳ２９）。
【００２４】
例えば、図１のネットワークにおいて、送信元ノードがノード「２」であり、宛先ノードがノード「３」である場合には、図１１に示すように、経路Ａ１としては「２−１」というノード系列が得られ、経路Ｂ１としては「３−６−５−１」というノード系列が得られる。一方、送信元ノードがノード「３」であり、宛先ノードがノード「４」である場合には、図１２に示すように、経路Ａ２としては「３−６−５−１」というノード系列が得られ、経路Ｂ２としては「４−６−５−１」というノード系列が得られる。
【００２５】
そして、経路特定処理部１１２２は、経路Ａ及びＢの末尾から未処理の１ノードを取り出す（ステップＳ３１）。そして、取り出した２つのノードの番号が等しいか判断する（ステップＳ３３）。図１１の事例では、ノード番号「１」が取り出され、一致していると判断される。図１２の事例では、ノード番号「１」が取り出され、一致していると判断される。取り出した２つのノードのノード番号が等しい場合には、共通のノードを経路Ａ及びＢから削除し、共通ノード番号Ｃに代入して保持する（ステップＳ３５）。そしてステップＳ３１に戻る。
【００２６】
図１１の事例では、ノード番号「１」が経路Ａ１及びＢ１から削除され、共通ノード番号Ｃに代入される。それ以降は一致するノード番号が得られないので、共通ノード番号Ｃには「１」が代入されており、経路Ａ１は「２」、経路Ｂ１は「３−６−５」となる。一方、図１２の事例では、次のノード「５」も共通するのでノード「５」は経路Ａ２及びＢ２から削除され、共通ノード番号Ｃは「５」に変更される。さらに、次のノード「６」も共通するのでノード「６」は経路Ａ２及びＢ２から削除され、共通ノード番号Ｃは「６」に変更される。次のノードは不一致となるので、経路Ａ２は「３」、経路Ｂ２は「４」、共通ノード番号Ｃは「６」という状態になる。
【００２７】
そして、取り出した２つのノードのノード番号が不一致となった場合には、経路特定処理部１１２２は、削除後の経路Ｂを逆順に並べ替える（ステップＳ３７）。すなわち、図１１の事例では、削除後の経路Ｂ１を逆順の経路Ｂ１ａ「５−６−３」に並び替える。図１２の事例では、削除後の経路Ｂ２は既に１ノードで構成されるので並び替えても逆順の経路Ｂ２ａ「４」のままである。さらに、経路特定処理部１１２２は、削除後の経路Ａ−共通ノード番号Ｃのノード−逆順の削除後の経路Ｂの順番に並べて経路Ｘを生成し、例えばメインメモリなどの記憶装置に格納する（ステップＳ３９）。図１１の事例の場合には、削除後の経路Ａ１「２」−共通ノード番号Ｃのノード「１」−逆順の削除後の経路Ｂ１ａ「５−６−３」であるから、「２−１−５−６−３」という経路Ｘが得られる。一方、図１２の事例の場合には、図１３に示すように、削除後の経路Ａ２ａ「３」−共通ノード番号Ｃのノード「６」−逆順の削除後の経路Ｂ２ａ「４」であるから、「３−６−４」という経路Ｘが得られる。処理は端子Ｂを介して図１４の処理に移行する。
【００２８】
このような処理を実施することによって、基点ノードを１つ任意に決定してしまい、最短経路データテーブルを管理サーバ１１１のみに保持するようにしても、問題なく経路を決定することができるようになる。なお、このように決定された経路は、必ずしも最適とは言えない場合もあるが、実用の範囲で大きな問題はない。
【００２９】
図１４の処理の説明に移行して、接続データ抽出部１１２３は、経路Ｘの先頭を処理ターゲットに設定する（ステップＳ４１）。そして、処理ターゲット及び経路Ｘ上当該処理ターゲットの次のノードを特定する（ステップＳ４３）。その後、二地点間接続データ格納部１１１３から、処理ターゲット及び次のノードに該当する二地点間接続データを読み出す（ステップＳ４５）。例えば図１２の事例の場合、経路を直線的に且つ模式的に示すと図１５に示すような状態となる。このような場合、最初に処理ターゲットはノード「３」であり次のノードはノード「６」である。従って、二地点間接続データ格納部（図８）の８行目のデータを読み出す。すなわち、インタフェース・データは「２１．０．０．３」であり宛先アドレスが「２１．０．０．６」である。
【００３０】
そして、接続データ抽出部１１２３は、ステップＳ４３で特定した次のノードが経路Ｘの末尾ノードであるか判断する（ステップＳ４７）。末尾ノードではない場合には、処理ターゲットを１つ後ろのノードに設定して（ステップＳ４９）、ステップＳ４３に戻る。図１５の例では、処理ターゲットはノード「６」であり、次のノードはノード「４」である。従って、二地点間接続データ格納部１１１３の１７行目のデータを読み出す。すなわち、インタフェース・データは「２１．０．０．６」であり、宛先アドレスが「２１．０．０．４」である。ここで、ノード「４」は経路Ｘの末尾ノードであるので、ステップＳ４９に移行しなくなる。
【００３１】
ステップＳ４３で特定した次のノードが経路Ｘの末尾ノードである場合には、接続データ抽出部１１２３は、ステップＳ４３で特定した次のノード及び「ｅ」に該当する行のデータを、二地点間接続データ格納部１１１３から読み出す（ステップＳ５１）。図１５の例では、ノード「４」と「ｅ」の１２行目を読み出す。すなわち、インタフェース・データは「１０．０．４．４」であり、宛先アドレスはないが、エッジルータから受信した宛先ＩＰアドレスが設定される。
【００３２】
そして、接続データ抽出部１１２３は、読み出した接続データを経路Ｘの順に並べて全体の接続データを生成し、例えばメインメモリなどの記憶装置に格納する（ステップＳ５３）。図１５の例では、図１６のような接続データが生成されることになる。上で述べたデータが連結されている。
【００３３】
以上のような処理を行うことで、最短経路データテーブルを保持しない各ルータでもパケットの送出先を容易に特定できるようにするための接続データが得られるようになる。
【００３４】
図９の処理の説明に戻って、管理サーバ１１１の経路算出部１１１１は、生成された接続データを、要求元のエッジルータに送信する（ステップＳ１５）。要求元のエッジルータは、管理サーバ１１１から接続データを受信し、取得済み接続データ格納部１０１３に格納する（ステップＳ１７）。処理は端子Ａを介して、図１７の処理に移行する。
【００３５】
エッジルータの接続データ処理部１０１１の接続データ付加部１０２１は、自ノード用の接続データ以外をパケットヘッダに付加し、接続データ処理部１０１１の自ノードデータ取得部１０２２は、自ノード用の接続データを取得して、当該接続データに従ってパケットを送信する（図１７：ステップＳ６１）。図１６の例では、先頭がエッジルータ「３」のための接続データであるから、それ以外の接続データについてはパケットヘッダに付加される。すなわち、図１８に示すようなデータが、図１６の例では、エッジルータ「３」から中継ルータ「６」へ送信される。本実施の形態では、自ノード用の接続データは切り取るような例を示すが、無効化ビットを付加するなどして、そのままパケットヘッダに付加してしまう場合もある。なお、接続データから具体的にどのポートにどのような宛先のパケットを送信するかということは、従来技術と同じであるから、説明を省略する。
【００３６】
中継ルータは、エッジルータからパケットを受信し（ステップＳ６３）、中継ルータの接続データ処理部１０５１における自ノードデータ取得部１０５２は、自ノード用の接続データをパケットから切り出し、当該接続データに従ってパケットを送信する（ステップＳ６５）。すなわち、図１９に示すようなデータが、図１６の例では、中継ルータ「６」からエッジルータ「４」に送信される。経路によっては中継ルータにさらに送信される場合もある。
【００３７】
図１６の例では、エッジルータ「４」は、中継ルータ「６」からパケットを受信し（ステップＳ６７）、接続データ処理部１０１１の自ノードデータ取得部１０２２が自ノード用の接続データを切り出し、当該接続データに従ってパケットを送信する（ステップＳ６９）。図２０のように、接続データが無くなったパケットが送信される。ここでは、ユーザ端末１５４が、エッジルータ「４」からパケットを受信する（ステップＳ７１）。
【００３８】
以上のように、各エッジルータ又は中継ルータにおいては、最短経路データテーブル（すなわちルーティングテーブル）を保持せずとも、パケットを目的のノードまで送信することができるようになる。すなわち、データ保持のための消費電力を削減することができている。
【００３９】
具体的には、例えば従来のHop-by-Hopについては、平均ルーティングテーブル数を２．７３で、例えば総ルータ台数１５台、エッジルータ台数９台（６０％）、総リンク数３７（２４６％）とすると、サブネットマスク情報は４１×６４ビットで次ホップ情報は４１×６４ビットで、合計５２４８ビット必要となる。このような構成がそのまま大きくなるとすると、サブネットマスク情報は総ルータ台数ｘ＊２．７３＊６４ビットで、次ホップ情報は総ルータ台数ｘ＊２．７３＊６４ビットで、合計ｘ＊３４９．４ビットとなる。
【００４０】
また、従来のソースルーティング手法を採用した場合には、同様の構成であれば、サブネット−ノード対応情報（例えば図５）は９×８０ビットで、経路探索用テーブル（例えば図６）が７２×３２ビットで、次ホップ情報（例えば図８）は３７×９６ビットで、合計６５７６ビット必要となる。このような構成がそのまま大きくなるとすると、サブネットマスク−ノード対応情報は、総ルータ台数ｘ＊０．６×８０ビットで、経路探索用テーブル総数はｘ（ｘ−１）＊０．６＊３２ビットで、次ホップ情報は、総ルータ台数ｘ＊２．４６＊９６ビットで、合計ｘ2＊１９．２＋ｘ＊２６５．０ビットとなる。すなわち、総ルータ台数の二乗に比例して増加してしまう。
【００４１】
一方、本実施の形態であれば、同様の構成の場合、サブネットマスク−ノード対応情報が９×８０ビットで、経路探索用テーブル総数が８×３２ビットで、次ホップ情報が３７×９６ビットであり、合計４５２８ビットとなる。すなわち、最も少なくて済んでいる。さらに、このような構成がそのまま大きくなるとすると、サブネットマスク−ノード対応情報が総ルータ台数ｘ＊０．６×８０ビット、経路探索用テーブルが総ルータ台数ｘ＊０．６×３２ビット、次ホップ情報が総ルータ台数ｘ＊２．４６＊９６ビットで、合計ｘ＊３０３．４ビットとなる。このように、データ量は総ルータ台数に比例して増加するだけで済むので、データ量の削減がなされている。すなわち、その分の電力消費量を削減することができている。
【００４２】
以上本実施の形態を説明したが、本技術はこれに限定されるわけではない。例えば図１に示したようなネットワーク構成は一例であって他のネットワーク構成であっても良い。さらに、処理フローについても処理結果が変わらない限り順番を入れ替えたり、並列に実行することも可能である。さらに、機能ブロック図については一例であって、必ずしも実際のプログラムモジュール構成と一致しない場合もある。また、機能ブロックは専用の回路又はハードウエアとソフトウエアの組み合わせにて実施される。
【００４３】
ノードデータ格納部１１１４を各ルータに保持させて、ルータから宛先ＩＰアドレスではなく、宛先ノード番号を送信するようにしても良い。但し、その分全体のデータ量が増加してしまう。
【００４４】
なお、管理サーバ１１１は、コンピュータ装置であって、図２１に示すように、メモリ２５０１とＣＰＵ２５０３とハードディスク・ドライブ（ＨＤＤ）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。必要に応じてＣＰＵ２５０３は、表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、必要な動作を行わせる。また、処理途中のデータについては、メモリ２５０１に格納され、必要があればＨＤＤ２５０５に格納される。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及び必要なアプリケーション・プログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【００４５】
なお、ルータも、図２１に示すようなコンピュータで実現される場合もある。
【００４６】
以上本実施の形態をまとめると以下のようになる。
【００４７】
ネットワークの経路情報を保持しない、ネットワーク中のノードを管理する管理装置により実行される経路決定方法は、パケットの送信元ノードと宛先ノードとを特定するノード特定ステップと、ネットワークにおいて予め定められた基点ノードについての最短経路データを格納する経路データ格納部（例えば最短経路データテーブル格納部）から、送信元ノードから基点ノードへの最短経路である第１の経路と宛先ノードから基点ノードへの最短経路である第２の経路とを特定する部分経路特定ステップと、第１の経路及び第２の経路の末尾からの重複部分を第１の経路及び第２の経路から削除すると共に削除後の第２の経路を逆順にして削除後の第１の経路及び重複部分において最も先頭に近いノードに連結することにより、送信元ノードから宛先ノードへの第３の経路を特定するステップとを含む。
【００４８】
管理装置に任意の基点ノードをベースにした最短経路データを格納する経路データ格納部を保持させて、各ノードにおいては保持しないようにしても、上で述べたような処理を実施すれば、送信元ノードから宛先ノードへの経路を特定することができる。すなわち、ルータの保持データ量が削減され、消費電力の削減が達成される。
【００４９】
また、本経路決定方法において、ネットワーク中の隣接ノード間の接続データを格納する二地点間接続データ格納部から、第３の経路において送信元ノードから順番に連続する２ノードの各組み合わせについて、該当する接続データを読み出し、送信元ノードに通知するステップをさらに含むようにしても良い。このようにすれば、各ルータでは簡単に従来の機構を用いてパケットの送出先を特定できるようになる。
【００５０】
さらに、本経路決定方法において、送信元ノード又は宛先ノードが基点ノードと一致しているか判断するステップと、一致していないと判断された場合には部分経路特定ステップ以降を実施させるステップと、一致していると判断された場合には経路データ格納部から送信元ノードから基点ノードへの最短経路又は基点ノードから宛先ノードへの最短経路を第３の経路として特定するステップとをさらに含むようにしても良い。上で述べたような条件を満たす場合には、第１の経路と第２の経路を連結するような処理が不要で、経路データ格納部に格納されたデータから容易に経路を特定できる。
【００５１】
また、上で述べたノード特定ステップが、送信元ノードから送信先ＩＰアドレスを受信するステップと、ネットワーク中の各ノードのＩＰアドレスに対応付けてノードＩＤが格納されているノードＩＤデータ格納部から、送信先ＩＰアドレスに対応するノードＩＤを特定するステップとを含むようにしてもよい。このようにすれば、エッジルータの保持データ量をさらに削減することができる。
【００５２】
なお、上で述べたような処理をハードウエアに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭ、光磁気ディスク、半導体メモリ、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、コンピュータのメモリ等の記憶装置に一時保管される。
【００５３】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【００５４】
（付記１）
ネットワークの経路情報を保持しない、前記ネットワーク中のノードを管理する管理装置により実行される経路決定プログラムであって、
パケットの送信元ノードと宛先ノードとを特定するノード特定ステップと、
前記ネットワークにおいて予め定められた基点ノードについての最短経路データを格納する経路データ格納部から、前記送信元ノードから前記基点ノードへの最短経路である第１の経路と前記宛先ノードから前記基点ノードへの最短経路である第２の経路とを特定する部分経路特定ステップと、
前記第１の経路及び前記第２の経路の末尾からの重複部分を前記第１の経路及び前記第２の経路から削除すると共に削除後の前記第２の経路を逆順にして削除後の前記第１の経路及び前記重複部分において最も先頭に近いノードに連結することにより、前記送信元ノードから前記宛先ノードへの第３の経路を特定するステップと、
を前記管理装置に実行させるための経路決定プログラム。
【００５５】
（付記２）
前記ネットワーク中の隣接ノード間の接続データを格納する二地点間接続データ格納部から、前記第３の経路において前記送信元ノードから順番に連続する２ノードの各組み合わせについて、該当する接続データを読み出し、前記送信元ノードに通知するステップ
をさらに実行させるための付記１記載の経路決定プログラム。
【００５６】
（付記３）
前記送信元ノード又は前記宛先ノードが前記基点ノードと一致しているか判断するステップと、
一致していないと判断された場合には前記部分経路特定ステップ以降を実施させるステップと、
一致していると判断された場合には前記経路データ格納部から前記送信元ノードから前記基点ノードへの最短経路又は前記基点ノードから前記宛先ノードへの最短経路を前記第３の経路として特定するステップと、
をさらに含む付記１又は２記載の経路決定プログラム。
【００５７】
（付記４）
前記ノード特定ステップが、
前記送信元ノードから送信先ＩＰアドレスを受信するステップと、
前記ネットワーク中の各ノードのＩＰアドレスに対応付けてノードＩＤが格納されているノードＩＤデータ格納部から、前記送信先ＩＰアドレスに対応するノードＩＤを特定するステップと、
を含む付記１乃至３のいずれか１つ記載の経路決定プログラム。
【００５８】
（付記５）
ネットワークの経路情報を保持しない、前記ネットワーク中のノードを管理する管理装置であって、
パケットの送信元ノードと宛先ノードとを特定する手段と、
前記ネットワークにおいて予め定められた基点ノードについての最短経路データを格納する経路データ格納部と、
前記経路データ格納部から、前記送信元ノードから前記基点ノードへの最短経路である第１の経路と前記宛先ノードから前記基点ノードへの最短経路である第２の経路とを特定する手段と、
前記第１の経路及び前記第２の経路の末尾からの重複部分を前記第１の経路及び前記第２の経路から削除すると共に削除後の前記第２の経路を逆順にして削除後の前記第１の経路及び前記重複部分において最も先頭に近いノードに連結することにより、前記送信元ノードから前記宛先ノードへの第３の経路を特定する手段と、
を有する管理装置。
【００５９】
（付記６）
ネットワークの経路情報を保持しない複数のノードと、
前記ルータと通信可能な管理装置と、
を有し、
前記複数のノードのうち第１のノードは、
前記ネットワークを経由して送信すべきパケットを受信した場合、自ノードＩＤである送信元ノードのＩＤと、前記パケットの宛先ＩＰアドレスとを前記管理装置に送信し、
前記管理装置は、
前記特定のノードから前記送信元ノードのＩＤと前記宛先ＩＰアドレスとを受信し、前記宛先ＩＰアドレスに対応する宛先ノードのＩＤを特定する手段と、
前記ネットワークにおいて予め定められた基点ノードについての最短経路データを格納する経路データ格納部と、
前記経路データ格納部から、前記送信元ノードから前記基点ノードへの最短経路である第１の経路と前記宛先ノードから前記基点ノードへの最短経路である第２の経路とを特定する手段と、
前記第１の経路及び前記第２の経路の末尾からの重複部分を前記第１の経路及び前記第２の経路から削除すると共に削除後の前記第２の経路を逆順にして削除後の前記第１の経路及び前記重複部分において最も先頭に近いノードに連結することにより、前記送信元ノードから前記宛先ノードへの第３の経路を特定する手段と、
前記ネットワーク中の隣接ノード間の接続データを格納する二地点間接続データ格納部と、
前記二地点間接続データ格納部から、前記第３の経路において前記送信元ノードから順番に連続する２ノードの各組み合わせについて、該当する接続データを読み出し、前記送信元ノードに通知する手段と、
を有し、
前記特定のノードは、前記接続データを前記管理装置から受信し、受信した前記パケットの送出に用いると共に、前記接続データのうち少なくとも前記第３の経路上の他の前記ノードが用いる接続データを前記パケットに付加して送出し、
前記第３の経路上の他の前記ノードは、受信した前記接続データのうち自ノード用の接続データを用いて受信パケットを送出する
ネットワーク・システム。
【符号の説明】
【００６０】
１１１  管理サーバ    １１１１  経路算出部
１１２１  ノード特定処理部    １１２２  経路特定処理部
１１２３  接続データ抽出部    １１１４  ノードデータ格納部
１１１２  最短経路データテーブル格納部    １１１３  二地点間接続データ格納部
【図１】
2010199646.tif 000003
【図２】
2010199646.tif 000004
【図３】
2010199646.tif 000005
【図４】
2010199646.tif 000006
【図５】
2010199646.tif 000007
【図６】
2010199646.tif 000008
【図７】
2010199646.tif 000009
【図８】
2010199646.tif 000010
【図９】
2010199646.tif 000011
【図１０】
2010199646.tif 000012
【図１１】
2010199646.tif 000013
【図１２】
2010199646.tif 000014
【図１３】
2010199646.tif 000015
【図１４】
2010199646.tif 000016
【図１５】
2010199646.tif 000017
【図１６】
2010199646.tif 000018
【図１７】
2010199646.tif 000019
【図１８】
2010199646.tif 000020
【図１９】
2010199646.tif 000021
【図２０】
2010199646.tif 000022
【図２１】
2010199646.tif 000023