(57)【特許請求の範囲】
【請求項１】
複数のノードが相互接続されるネットワークにおいて、情報の伝送を行う通信経路を各ノードが自律的に選択して通信を行うルーチング方法であって、 
伝送するべき信号を持つノードが、経路を探索するためのメッセージをブロードキャスト送信し、経路の終端に位置するべきノードが該メッセージを受信したときに、該メッセージの経由した経路を逆にたどって応答メッセージを返信することにより通信経路を確定するステップと、 
前記応答メッセージには少なくとも経路を構成するノードの数及び、それぞれのノードの位置を示す情報を含み、前記応答メッセージを受信したノードは、該メッセージに含まれる情報を元に、それぞれ２以上のノードからなるグループを構成するステップと、 
前記構成された各グループが、隣接するグループ間の境界に位置するノードを共有し、少なくとも前記グループ間の境界に位置するノードにあっては、少なくとも自ノードの属するグループ内における経路情報を蓄積するステップと、 
グループ間の境界に位置するノードにおいては、伝送されるべき情報に、グループ内における経路情報を表示する情報を付加し、又は置き換える動作を繰り返すことによって、経路の終端に位置するノードにまで情報を伝達するステップと 
を有するルーチング方法。 
【請求項２】
隣接するグループ間の境界に位置するノードにおいて、該ノードの属する２つのグループの両方における経路情報を蓄積するステップを有する請求項１記載のルーチング方法。
【請求項３】
前記経路を構成する全ノード数の平方根の整数倍の数、または前記全ノード数の平方根の整数倍に平方根の２分の１を加えた数に最も近い番号を持つノードをグループ境界ノードとすることによって、グループを構成するステップを有する請求項１記載のルーチング方法。 
【請求項４】
伝送されるべき情報のあて先となりうるノードにのみグループを構成するための算出を行うステップと、 
前記算出を行うノードは、経路を探索するためのメッセージに対する応答メッセージ、又は前記応答メッセージと近接したタイミングで前記経路を探索するためのメッセージを送出したノードに宛てて送信するメッセージによって、算出したグループ構成を表示する情報を通知するステップと、 
グループを構成する手段を備えないノードは、該表示されたグループ構成に従ってルーチング動作を行うステップとを有する請求項１記載のルーチング方法。 
【請求項５】
伝送するべき信号のあて先ノードから該信号を持つノードに宛てて伝送される、算出したグループ構成を表示する情報を含むメッセージを伝送する際に、 
前記表示されたグループ構成においてグループ境界ノードに指定されたノードにおいて前記メッセージを送信する前に、前記グループ境界ノードよりあて先ノードに近い方向の経路に関するグループ構成情報を削除するステップを有する請求項４記載のルーチング方法。 
【請求項６】
経路を探索するためのメッセージに対する応答メッセージ、又は前記応答メッセージと近接したタイミングで前記経路を探索するためのメッセージを送出したノードに宛てて送信するメッセージに含まれる情報に加えて、 
前記メッセージを受信したノードが蓄積、算出、測定、もしくは取得した情報を加味することによってグループの構成を決定するステップを有する請求項１記載のルーチング方法。 
【請求項７】
経路を構成するノード間のリンクのうち、１つ以上のリンクにおいて情報の伝送が不可能となった場合において、 
前記情報の伝送が不可能であることを検知したノードは、経路が使用不能であることを表示するメッセージを、自ノードの属するグループの、伝送しようとする情報が送られてきた方向のグループ境界ノードに向けて送信するステップと、 
前記メッセージを受信したグループ境界ノードにおいては、該グループの他端に位置するグループ境界ノードに到達可能な代替経路を、その蓄積している経路情報から検索するステップと、 
前記代替経路を発見できた場合には、以前に利用していた経路に代えて、以後該代替経路を利用するステップとを有する請求項１記載のルーチング方法。 
【請求項８】
経路を構成するノード間のリンクのうち、１つ以上のリンクにおいて情報の伝送が不可能となった場合において、 
前記情報の伝送が不可能であることを検知したノードは、経路が使用不能であることを表示するメッセージを、自ノードの属するグループの、伝送しようとする情報が送られてきた方向のグループ境界ノードに向けて送信するステップと、 
前記メッセージを受信したグループ境界ノードにおいては、該グループの他端に位置するグループ境界ノードに到達可能な代替経路を探索するためのメッセージをブロードキャスト送信するステップと、 
前記他端に位置するグループ境界ノードが前記経路を探索するためのメッセージを受信したときに、該メッセージの経由した経路を逆にたどって応答メッセージを返信するステップと、 
前記応答メッセージを受信したグループ境界ノードは、以前に利用していた経路に代えて、以後該代替経路を利用するステップとを有する請求項１記載のルーチング方法。 
【請求項９】
グループを構成するノードの数をあらかじめ記憶するステップと、 
代替経路を探索するためにブロードキャスト送信するメッセージに、該記憶されたノードの数を基準として規定の算出方法によって算出した限界ホップ数を設定するステップとを有する請求項８記載のルーチング方法。 
【請求項１０】
代替経路を探索するためにブロードキャスト送信されたメッセージに対する応答メッセージが、あらかじめ規定されたタイムアウト時間以内に受信されない場合に、 
あらかじめ規定された回数のブロードキャスト送信を繰り返すステップを有する請求項８記載のルーチング方法。 
【請求項１１】
代替経路を探索するためにブロードキャスト送信を繰り返す場合に、送信の繰り返し回数に応じて該ブロードキャスト送信する情報の限界ホップ数をあらかじめ規定した割合で増加させるステップを有する請求項１０記載のルーチング方法。 
【請求項１２】
グループ境界ノードを共有しない、二種以上のオーバラップされたグループを経路上に構成するステップと、 
前記二種以上のグループのうち、少なくとも一つを情報の伝送のために使用し、 
前記情報の伝送のために使用するグループ以外のグループを、代替経路を探索する手順においてのみ使用するステップとを有する請求項７記載のルーチング方法。 
【請求項１３】
代替経路を探索する手順においてのみ使用するグループにおいて新たな経路の構成に成功した場合、 
前記代替経路を探索する手順においてのみ使用するグループを包含する、情報の伝送のために使用するグループにおいて、 
前記代替経路を探索する手順においてのみ使用するグループに含まれない２つのグループ境界ノードに対して代替経路を通知するメッセージを送信するステップと、 
前記２つのグループ境界ノードの間の経路において、情報の伝送のために使用する２つのグループを構成するステップとを有する請求項１２記載のルーチング方法。 
【請求項１４】
経路を構成するノード間のリンクのうち、１つ以上のリンクにおいて情報の伝送が不可能となった場合において、 
前記情報の伝送が不可能であることを検知したノードは、経路が使用不能であることを表示するメッセージを、自ノードの属するグループの、伝送しようとする情報が送られてきた方向のグループ境界ノードに向けて送信するステップと、 
前記メッセージを受信したグループ境界ノードにおいては、前記グループに隣接した、情報の伝送されるべき方向に位置するグループの、情報の伝送されるべき方向の端に位置するグループ境界ノードに到達可能な代替経路を、その蓄積している経路情報から検索するステップと、 
該代替経路を発見できた場合には、以前に利用していた経路に代えて、以後該代替経路を利用するステップとを有する請求項１記載のルーチング方法。 
【請求項１５】
経路を構成するノード間のリンクのうち、１つ以上のリンクにおいて情報の伝送が不可能となった場合において、 
前記情報の伝送が不可能であることを検知したノードは、経路が使用不能であることを表示するメッセージを、自ノードの属するグループの、伝送しようとする情報が送られてきた方向のグループ境界ノードに向けて送信するステップと、 
前記メッセージを受信したグループ境界ノードにおいては、前記グループに隣接した、情報の伝送されるべき方向に位置するグループの、情報の伝送されるべき方向の端に位置するグループ境界ノードに到達可能な代替経路を探索するためのメッセージをブロードキャスト送信するステップと、 
前記隣接グループの境界ノードが前記経路を探索するためのメッセージを受信したときに、該メッセージの経由した経路を逆にたどって応答メッセージを返信するステップと、
前記応答メッセージを受信したグループ境界ノードは、以前に利用していた経路に代えて、以後該代替経路を利用するステップとを有する請求項１記載のルーチング方法。 
【請求項１６】
代替経路の構成に成功した場合、 
２つのグループ境界ノードの間に構成された代替経路において、２つのグループを構成するステップを有する請求項１５記載のルーチング方法。 
【請求項１７】
隣接する２つのグループを構成するノードの数の合計をあらかじめ記憶するステップと、 
代替経路を探索するためにブロードキャスト送信するメッセージに、該記憶されたノードの数の合計を基準として規定の算出方法によって算出した限界ホップ数を設定するステップとを有する請求項１５記載のルーチング方法。 
【請求項１８】
代替経路を探索するためにブロードキャスト送信されたメッセージに対する応答メッセージが、あらかじめ規定されたタイムアウト時間以内に受信されない場合に、
あらかじめ規定された回数のブロードキャスト送信を繰り返すステップを有する請求項１５記載のルーチング方法。 
【請求項１９】
代替経路を探索するためにブロードキャスト送信を繰り返す場合に、 
送信の繰り返し回数に応じて該ブロードキャスト送信する情報の限界ホップ数をあらかじめ規定した割合で増加させるステップを有する請求項１８記載のルーチング方法。 
【請求項２０】
前記２つのグループは、含まれるノードの数の差が１以下である請求項１６記載のルーチング方法。 
【請求項２１】
経路を構成するノード間のリンクのうち、１つ以上のリンクにおいて情報の伝送が不可能となった場合において、
前記情報の伝送が不可能であることを検知したノードは、経路が使用不能であることを表示するメッセージを、自ノードの属するグループの、伝送しようとする情報が送られてきた方向のグループ境界ノードに向けて送信するステップと、 
前記メッセージを受信したグループ境界ノードにおいては、伝送しようとする情報のあて先ノードに到達可能な代替経路を、その蓄積している経路情報から検索するステップと、 
前記代替経路を発見できた場合には、以前に利用していた経路に代えて、以後該代替経路を利用するステップとを有する請求項１記載のルーチング方法。
【請求項２２】
経路を構成するノード間のリンクのうち、１つ以上のリンクにおいて情報の伝送が不可能となった場合において、 
前記情報の伝送が不可能であることを検知したノードは、経路が使用不能であることを表示するメッセージを、自ノードの属するグループの、伝送しようとする情報が送られてきた方向のグループ境界ノードに向けて送信するステップと、 
該メッセージを受信したグループ境界ノードにおいては、伝送しようとする情報のあて先ノードに到達可能な代替経路を探索するためのメッセージをブロードキャスト送信するステップと、 
前記あて先ノードが前記経路を探索するためのメッセージを受信したときに、該メッセージの経由した経路を逆にたどって応答メッセージを返信するステップと、 
前記応答メッセージを受信したグループ境界ノードは、以前に利用していた経路に代えて、以後該代替経路を利用するステップとを有する請求項１記載のルーチング方法。 
【請求項２３】
グループを構成するノードの数をあらかじめ記憶するステップと、 
代替経路の構成に成功した場合、代替経路において、前記記憶されたノード数±１の数のノードからなるグループを構成するステップとを有する請求項２２記載のルーチング方法。 
【請求項２４】
グループ境界ノードからあて先ノードに至る経路を構成するノードの数をあらかじめ記憶するステップと、 
代替経路を探索するためにブロードキャスト送信するメッセージに、該記憶されたノードの数を基準として規定の算出方法によって算出した限界ホップ数を設定するステップとを有する請求項２２記載のルーチング方法。 
【請求項２５】
代替経路を探索するためにブロードキャスト送信されたメッセージに対する応答メッセージが、あらかじめ規定されたタイムアウト時間以内に受信されない場合に、 
あらかじめ規定された回数のブロードキャスト送信を繰り返すステップを有する請求項２２記載のルーチング方法。 
【請求項２６】
代替経路を探索するためにブロードキャスト送信を繰り返す場合に、 
送信の繰り返し回数に応じて該ブロードキャスト送信する情報の限界ホップ数をあらかじめ規定した割合で増加させるステップを有する請求項２５記載のルーチング方法。 
【請求項２７】
経路を構成する全ノードの数を、あらかじめ規定する数と比較し、前記ノードの数が所定数以上の場合に、ルーチングを行う請求項１記載のルーチング方法。 
【請求項２８】
請求項７、請求項８乃至請求項１４、及び請求項２１のうちの一つのステップ、請求項１５乃至請求項２０のうちの一つのステップ、請求項２２乃至請求項２６のうちの一つのステップのうち、いずれか２つ以上の複数のステップを備え、 
前記複数のステップのうち、一つのステップによる経路の再構築動作が失敗した場合に限って、前記複数のステップのうちの別のステップを起動し、又は起動したステップを繰り返すルーチング方法。 
【請求項２９】
請求項１乃至請求項２８にいずれかに記載のルーチング方法を実現する機能を備えるノード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードが相互接続されるネットワークにおいて、情報の伝送を行う通信経路を各ノードが自律的に選択して通信を行うルーチング方法及びノード装置に関し、詳細には、複数のノードが相互接続されたネットワークにおいて、遅延時間、スループット、誤り率等のサービス品質等に応じて最適な通信経路を選択して通信を行うルーチンググループの自律構成方法の改良に関する。
【背景技術】
【０００２】
無線通信を利用してノード間でパケットの交換を行うネットワークにおいて、ノード間の接続形態が固定されておらず、伝播環境その他の条件によって適応的にネットワーク構成の変化するネットワークはアドホックネットワークと呼ばれる。
【０００３】
アドホックネットワークにおいて、複数のノードを経由してパケットを伝送するマルチホップ伝送をする場合には、パケットを生成するノードから、伝送パケットの目的地となるノードまでの経路を構成するノードにおけるパケット伝送の順番を決定する、すなわちルーチング動作を行う必要がある。ノード間の伝播環境が時間的に固定されているか、その変化が一連のパケットの生成及び伝送のための時間に比して十分に長い時間をかけてなされるものである場合には、ルーチング機能は確実性及び最適性の性能を満たすものであれば実際に使用されるネットワークに対するアプリケーションとして十分である。しかし、ノードが移動するなどの理由により、ノード間の伝播環境が時間的に短い間隔で大きく変化する環境においては、アドホックネットワークに備えられるルーチング機能に対しては、ルーチングの決定までの時間が短いことと、環境の変化に対して高速に適切な経路の再構築を行う機能が求められる。
【０００４】
上記のような機能を備えることを目的として考案されたルーチング方法として、The Internet Engineering Task Force Mobile Ad-hoc Netwok （manet）Working Groupで標準化作業中のDynamic Source Routing （ＤＳＲ）Protocol（以下、ＤＳＲプロトコルと呼ぶ）が提案されている。同提案の詳細規定は、The Internet Engineering Task ForceのMobile Ad-hoc Netwok （manet）Workig GroupインターネットWEBサイトhttp:／／www.ietf.org／html.charters／manet-charter.htmlにおいて公開されている非特許文献１、The Dynamic Source Routing Protocol （ＤＳＲ）for Mobile Ad Hoc Networks for IPv４ （RFC ４７２８）に記載されている。
【０００５】
以下、非特許文献１に記載されている従来技術であるＤＳＲプロトコルを使用してルーチング機能を実現するネットワークの動作の概要を説明する。
【０００６】
図１０は、従来のネットワークにおける経路の再構成動作を説明するネットワーク構成図である。
【０００７】
図１０において、ノード９００は、ノード９０１をあて先とするパケットを生成する送出元ノードである。初期状態において、ノード９００はパケットを送出する際、非特許文献１の８．２章に記述される経路発見手順（“Route Discovery Processing”）に従ってあて先ノード９０１までの経路を探索するためのメッセージ（Route Request）９３０乃至９３３をブロードキャスト送信する。Route Requestメッセージは、送出元ノード９００によってあらかじめ規定された数のホップ数を限度としてネットワーク内を中継再送される（図示せず）。Route Requestメッセージがあて先ノード９０１に到達すると、あて先ノード９０１は送出元ノード９００に向けて経路９５０を伝達するメッセージ（Route Reply:９４０）を送信する。Route Replyメッセージ９４０は、Route Requestメッセージ９３２がたどった経路９５０を逆向きにたどって送出ノード９００へ転送される。このRoute Replyメッセージ９４０を受信した送出元ノード９００は、あて先ノード９０１に到達できる経路９５０を蓄積し、伝送するべきパケットにこの経路９５０を付加して送出することにより、このパケットを中継するべき各ノードに対して経路を表示して、あて先ノード９０１にパケットを伝送することができる。また、上記Route Replyメッセージ９４０が伝送される際に経由する、経路９５０を構成する全てのノード、並びに、上記Route Replyメッセージ９４０を傍受することのできる全ての近傍ノードにおいても、経路９５０が蓄積される。これによって、あて先ノード９０１のみならず、経路９５０を構成するノードのいずれかをあて先とする新たなパケットが生成された際には、上記経路発見手順を起動することなく、蓄積された経路情報の一部を利用することによって、新たなあて先ノードにパケットを伝送することができる。さらに、経路９５０を構成するノードのみならず、これらのノードから送出される信号が受信可能である全てのノードを送出元として、経路９５０を構成するいずれかのノードをあて先ノードとするパケットが新たに生成されたときにも、蓄積された経路情報の一部を利用することによって、上記経路発見手順を起動することなくパケットを伝送することができる。
【０００８】
次に、非特許文献１の８．３章に記述される経路維持手順（“Route Maintenance Processing”）について説明する。
【０００９】
図１１は、従来のネットワークにおける経路の再構成動作を説明するネットワーク構成図である。
【００１０】
図１１において、初期状態において配置されているノード及び設定された経路は上記経路発見手順の説明において参照される図１０におけるものと同一である。いま、初期状態においてノード１００７−Ａに位置するノードが、ノード１００７−Ｂの位置に移動し、通信到達範囲から外れて経路を構成することができなくなった場合のネットワークの動作について述べる。
【００１１】
送出元ノード１０００からあて先ノード１００１に向けて経路１０５０をたどって転送されるパケットが、ノード１００６に到達したとき、ノード１００６はパケット中に格納されている経路１０５０を参照して、次に転送するべきノード１００７−Ａに向けてパケットを送信する。しかし、ノード１００７−Ａはすでにノード１００７−Ｂの位置に移動しており、ノード１００６の送信する信号の到達範囲外にあるため、このパケットを受信することができない。各ノードは、パケットの次段の転送先であるノードがパケットを受信できたこと（あるいはできなかったこと）を検出する手段を有しており、この手段を用いてノード１００７−Ａ（あるいは１００７−Ｂ）がこのパケットを受信できないことを検出し、経路１０５０が利用不能であることを表すメッセージ（Route Error）を送出元ノード１０００に向けて送信する。このRoute Errorメッセージには、あて先ノード１００１に向けて転送されていた元のパケットに含まれている経路１０５０と同じ経路情報を含んでおり、この経路上で、送出元ノード１０００から、Route Errorメッセージの送出元ノード１００６までの間にある各ノードは、この経路情報を参照しつつ、経路１０５０を逆にたどってRoute Errorメッセージを転送する。加えて、このRoute Errorメッセージを転送する経路上の各ノードは、蓄積されている経路情報から、このRoute Errorメッセージに含まれる経路情報と同一の情報を無効とする。
【００１２】
送出元ノード１０００が前記Route Errorメッセージを受信したとき、蓄積されている経路情報から、あて先ノード１００１に到達する経路情報を検索する。有効なこの経路情報が蓄積されている場合には、以後、あて先ノード１００１に宛てて送出されるパケットに含まれる経路情報として、この蓄積経路情報を使用する。蓄積経路情報中に、あて先ノード１００１に到達できる有効な経路情報が発見できなかったときであって、あて先ノード１００１に宛てて送出されるべきパケットが存在する場合には、前記経路発見手順に従って経路を発見した後でなければパケットを送出することはできない。
【００１３】
なお、非特許文献１の８．３．６章の規定によれば、送出元ノード１０００に向けてRoute Errorメッセージが転送されているとき、このRoute Errorメッセージを生成したノード１００６から送出元ノード１０００の間に位置するノード１００５が、このRoute Errorメッセージに含まれる経路情報の目的地ノードと同一の目的地ノードを持つ経路情報１０５１を蓄積している場合であって、このRoute Errorメッセージを含むパケット中にあて先ノード１００１に向けて転送されていた元のパケットの情報を含んでいる場合には、パケットからこのRoute Errorメッセージを取り除き、パケットに含まれる経路情報をこの蓄積経路情報に置き換えたメッセージを生成して、経路１００１に従って転送する。但し、この場合であっても、Route Errorメッセージは同時に送出元ノード１０００に向けて転送され続け、送出元ノード１０００において前記別の有効な蓄積経路情報の検索又は経路発見手順によって新たな経路を発見した後でなければ、送出元ノード１０００はあて先ノード１００１に宛てたパケットを送出することができない。
【００１４】
上述した非特許文献１記載のＤＳＲプロトコル技術によれば、アドホックネットワークにおいてパケットの伝送経路を決定し、経路を構成するノードの移動などに起因する伝送状態の変化に対して伝送経路を再構成する機能を実現することができる。
【非特許文献１】Request for Comments （RFC）4728: The Dynamic Source Routing Protocol （DSR）for Mobile Ad Hoc Networks for IPv4,2007年2月，The Internet Engineering Task Force
【発明の開示】
【発明が解決しようとする課題】
【００１５】
しかしながら、このような従来のＤＳＲプロトコルにあっては、経路を構成するノード間リンクが断絶した場合には、リンクの断絶を検知したノードから送出元ノードにRoute Errorメッセージを返送し、このメッセージを受信した送出元ノードが蓄積経路情報中に同一あて先ノードに到達できる有効な経路情報を持たない場合には、再び経路発見手順に従って経路の全長にわたって再構築を行う必要があった。特に、前記経路の全長にわたる経路再構築手順にあっては、少なくとも有効な経路を成すに必要な最短のホップ数以上のホップ数にわたって再送信されるべきRoute Requestメッセージをブロードキャスト送信する必要があり、このRoute Requestメッセージのフラッディングによってネットワーク全体のトラフィックを占有してしまうという問題があった。さらに、リンクの断絶を検出した後、少なくとも送出元ノードへのRoute Errorメッセージの返送、送出元ノードからあて先ノードへのRoute Requestメッセージのブロードキャスト送信、あて先ノードから送出元ノードへのRoute Replyメッセージの返送の各手順を経た後でなければ、経路の再構築が完成しないため、経路の再構築のために必要な時間が大きくなり、よってネットワークのスループットが劣化してしまうという問題があった。加えて、送出元ノードからあて先ノードにいたる経路を構成する全てのノード情報が、各ノードに蓄積される必要があるため、経路長が長くなるに従って、ノードに必要とされる記憶容量が大きくなり、ノードの回路規模が大きくなってしまうという問題もあった。
【００１６】
本発明は、上記に鑑みてなされたものであり、ネットワーク全体のトラフィックに対する影響を小さくすることができ、各メッセージの伝達されるべき経路を制限することによって経路の再構築に必要な時間を短くすることができ、ネットワークのスループットの劣化を抑えることができるルーチング方法及びノード装置を提供することを目的とする。
【００１７】
また、本発明は、各ノードに蓄積されるべき経路情報を削減することができ、ノードの回路規模を小さくすることができるルーチング方法及びノード装置を提供することを別の目的とする。
【課題を解決するための手段】
【００１８】
本発明のルーチング方法は、複数のノードが相互接続されるネットワークにおいて、情報の伝送を行う通信経路を各ノードが自律的に選択して通信を行うルーチング方法であって、伝送するべき信号を持つノードが、経路を探索するためのメッセージをブロードキャスト送信し、経路の終端に位置するべきノードが該メッセージを受信したときに、該メッセージの経由した経路を逆にたどって応答メッセージを返信することにより通信経路を確定するステップと、前記応答メッセージには少なくとも経路を構成するノードの数及び、それぞれのノードの位置を示す情報を含み、前記応答メッセージを受信したノードは、該メッセージに含まれる情報を元に、それぞれ２以上のノードからなるグループを構成するステップと、前記構成された各グループが、隣接するグループ間の境界に位置するノードを共有し、少なくとも前記グループ間の境界に位置するノードにあっては、少なくとも自ノードの属するグループ内における経路情報を蓄積するステップと、グループ間の境界に位置するノードにおいては、伝送されるべき情報に、グループ内における経路情報を表示する情報を付加し、又は置き換える動作を繰り返すことによって、経路の終端に位置するノードにまで情報を伝達するステップとを有する。
【００１９】
本発明のノード装置は、上記ルーチング方法を実現する機能を備えるノード装置である。
【発明の効果】
【００２０】
本発明によれば、各ノードに蓄積されるべき経路情報を大幅に削減して、ノードを構成する回路規模を削減することができる。
【００２１】
具体的には、経路を構成するリンクの断絶を検知した場合に、この断絶したリンクを迂回する最小限の範囲に対してのみ経路発見手順を適用することにより、Route Requestメッセージをブロードキャスト送信する範囲を小さく制限することができる。これにより、ネットワーク全体のトラフィックに対する影響を小さくすることができ、各メッセージの伝達されるべき経路を制限することによって経路の再構築に必要な時間を短くすることができる。その結果、ネットワークのスループットの劣化を抑えることができる。
【００２２】
また、各ノードに蓄積されるべき経路情報を削減することができるため、ノードの回路規模を小さくすることができる。
【発明を実施するための最良の形態】
【００２３】
以下、本発明の実施の形態について図面を参照して詳細に説明する。
【００２４】
（実施の形態１）
図１は、本発明の実施の形態１に係るルーチング方法によって経路を構成したネットワーク図である。
【００２５】
図１において、ノード１００はノード１０１をあて先とするパケットを生成する送出元ノードである。初期状態において、ノード１００はパケットを送出する際、非特許文献１の８．２章に記述される経路発見手順（Route Discovery Processing）に従ってあて先ノード１０１までの経路を探索するためのメッセージ（Route Request）１３０乃至１３３をブロードキャスト送信する。Route Requestメッセージは、送出元ノード１００によってあらかじめ規定され、メッセージ中に表示された数のホップ数を限度としてネットワーク内を中継再送される（図示せず）。Route Requestメッセージがあて先ノード１０１に到達すると、あて先ノード１０１は送出元ノード１００に向けて応答メッセージ（Route Reply）１４０を送信する。Route Replyメッセージ１４０に含まれる情報要素の一覧を〔表１〕に示す。
【００２６】
【表１】
0004927658.tif 000002
Route Replyメッセージ１４０は、Route Requestメッセージ１３２がたどった経路１５０を逆向きにたどって送出ノード１００へ転送される。あて先ノード１０１は、前記あらかじめ規定されたホップ数の限度内で伝達されたRoute Requestメッセージのすべてに対して、それぞれのメッセージがたどった経路（図示せず）を逆向きにたどって、この経路を表す情報要素を含むRoute Replyメッセージ（図示せず）をそれぞれ返送する。
【００２７】
以下、本実施の形態によってなされる、従来技術に対する拡張機能について説明する。
【００２８】
図２は、Route Replyメッセージを受信した際に各ノードで行う処理を示すフローチャートである。図中、Ｓはフローの各ステップを示す。
【００２９】
経路１５０を構成する各ノードは、Route Replyメッセージを受信すると（ステップＳ２００）、ステップＳ２０１でメッセージに含まれる情報要素を参照して、自ノードよりも送出元ノード１００に近い方向（以後、上流と呼ぶ）に隣接したノードに向けて受信したRoute Replyメッセージを転送する。
【００３０】
次いで、ステップＳ２０２で経路を構成するノード数を取得し、ステップＳ２０３で経路中の自ノード位置ｋを取得する。ステップＳ２０４では、経路グループ化手段は、経路を構成するノード数と、あらかじめ規定された算出方法（示さず）に従って、経路上のノードを一定数のグループに分割する。上記グループはそれぞれ２以上のノードからなり、それぞれのグループの端に位置するノード（以下、グループ境界ノードと呼ぶ）を隣接するグループで共有するように構成される。
【００３１】
ステップＳ２０５では、ステップＳ２０４の経路グループ化手段の算出結果及び、受信したRoute Replyメッセージにより取得した自ノードの位置から、自ノードはグループ境界か否かを判別する。上記ステップＳ２０５で自ノードがグループ境界ノードであることを知った場合には、ステップＳ２０６でこのノードは自ノードの重複して属する２つのグループのうち、上流側グループ内の経路を蓄積する。上記ステップＳ２０５で自ノードがグループ境界ノードでないことを知った場合、上記ステップＳ２０６は実行されずにステップＳ２０７に進む。
【００３２】
ステップＳ２０７では、自ノードの属するグループ（グループ境界ノードにあっては自ノードの属する２つのグループのうち、あて先ノード１０１に近い方向（以下、下流と呼ぶ）のグループ）内の経路を蓄積して本フローを終了する。
【００３３】
例として、前記経路グループ化手段におけるあらかじめ規定された算出方法として、送出元ノードを０として、あて先ノードにいたる経路上の各ノードに対して、ホップごとに１ずつ増やした番号付けを行い、経路を構成する全ノード数「１１」の平方根（約３．３２）の整数倍（すなわち、約３．３２と約６．６４）に最も近い番号（すなわち、３と７）を持つノードをグループ境界ノードとする３つのグループを構成する手段をとった場合のグループの構成を図３に示す。
【００３４】
図３は、望ましい算出方法の例を適用したときのグループの構成を示すネットワーク図である。図３中、送出元ノード３００から送出されるパケットは、経路３５０に沿ってあて先ノード３０１に向けて転送されるものとする。
【００３５】
グループ３６０に属するノード３００及び３０２乃至３０４において蓄積される経路情報を〔表２〕に示す。また、グループ３６１に属するノード３０４乃至３０８において蓄積される経路情報を〔表３〕に示す。
【００３６】
【表２】
0004927658.tif 000003
【００３７】
【表３】
0004927658.tif 000004
このとき、グループ境界ノードにあっては、自ノードがともに属する、接して存在する２つのグループ内の経路をともに蓄積する。すなわち、ノード３０４においては、〔表２〕及び〔表３〕の内容をともに蓄積する。
【００３８】
以上説明した手段により、各ノードに蓄積されるべき経路情報を従来技術に比べて大幅に削減することができ、よってノードを構成する回路規模を削減することが可能となる。
【００３９】
次に、送出元ノード３００からあて先ノード３０１にパケットを転送する動作について説明する。
【００４０】
送出元ノード３００は、経路３５０において、自ノードの属するグループ３６０内の経路のみを蓄積する。また、あて先ノード３０１に宛てて伝送しようとするパケットに、蓄積したこのグループ３６０内の経路のみを付加して送出する。このパケットは、経路３５０を構成する、グループ３６０内の各ノードに経路を表示し、これに従って各ノードはグループ境界ノード３０４までパケットを転送する。グループ境界ノード３０４は、受信したパケットの経路情報に含まれるあて先ノードのアドレスを参照して、この該当するグループ３６１内の経路情報を蓄積経路情報から取り出し、受信パケットに含まれる経路情報を前記取り出した蓄積経路情報に置き換えて送出する。同様の操作を、グループ３６１とグループ３６２の境界に位置するグループ境界ノード３０８においても行うことにより、このパケットを目的のあて先ノード３０１に転送することができる。
【００４１】
これにより、従来技術に比べてパケットに含まれる経路情報をも大幅に削減することができ、よって伝送されるパケット全体の情報量に占める伝送するべき情報の割合を大きくすることができるため、一定の物理伝送速度を実現する環境においては、システムスループットを改善することが可能となるという効果をも有する。
【００４２】
なお、以上の説明では、経路グループ化手段を全てのノードに備えるように構成されているが、あて先ノードとなりうるノードにのみこの手段を備え、Route Replyメッセージを含むパケット、又はRoute Replyメッセージを伝送するために送出されるパケットと近接したタイミングで同一の経路上に送出される別のパケットにグループ構成情報を持たせて送出し、このパケットを受信した経路上の各ノードはパケット中のグループ構成情報を参照して蓄積すべき経路情報を選択できるように構成することにより、あて先ノードとなりうるノード以外のノードには経路グループ化手段を備えないように構成することもできる。この構成により、あて先ノードとなりうるノード以外のノードの回路規模を削減することができ、Route Replyメッセージの転送に必要な処理時間を削減することができる上、グループ境界ノードとなるべきノードを通過する際に下流グループの経路情報を削除したRoute Replyメッセージを転送することが可能となる。このため、Route Replyメッセージのサイズを小さくすることができ、よってシステム伝送能力に占める制御情報の伝送負荷を小さくできることから、システムスループットを改善することができるという効果をも有する。さらに、前記経路グループ化手段の変更を行う場合、あるいはこの手段の動的な変更を行うシステムを構築する際にも、ネットワーク内の全ノードに対して処理手順の更新を行う必要がなく、あて先ノードとなりうるノードに対してのみこの更新を行うことによってシステム全体の処理手順を更新することができるという効果も有する。
【００４３】
また、以上の説明では、上記経路グループ化手段におけるあらかじめ規定された算出方法として、経路を構成する全ノード数のみを基準としてグループの構成を決定する手順を示しているが、ノードを構成するハードウェアの処理能力、ノード間の通信品質、通信速度、ノードの配置密度などのパラメータを算出根拠に加えることにより、通信信頼性、通信速度、経路確定に要する時間、システムスループットに占める制御情報の伝送負荷などの条件を最適とするようにグループの構成を決定するように構成することもできる。またさらに、これら根拠とするパラメータを、ノード自身が測定あるいは推定し、又は、別に備える測定手段あるいは推定手段から指示されるパラメータに従って、前記算出方法を動的に変更するように構成することもできる。
【００４４】
ところで、上記Route Replyメッセージが伝送される際に経由する、経路３５０を構成するノードから送信されるRoute Replyメッセージを傍受することのできる近傍ノードにおいては、傍受したRoute Replyメッセージに含まれる経路３５０及び、傍受したメッセージを直接送信したノードのアドレスを知ることができる。近傍ノードにあっても、経路グループ化手段を適用することにより、経路３５０に対して成されたグループ構成を知ることができる。これによって、傍受したメッセージを送信したノードの属するグループ内の経路のみを選択的に蓄積し、このグループ内経路を構成するノードのいずれかをあて先とする新たなパケットが生成された際には、上記経路発見手順を起動することなく、蓄積された経路情報の一部を利用することによって、新たなあて先ノードにパケットを伝送することができる。さらに、あて先ノード１０１をあて先とするパケットが新たに生成されたときにも、蓄積された経路情報を利用することによって、上記経路発見手順におけるブロードキャスト送信手段をとることなく、グループ境界ノードにおける経路情報の置き換え手順を援用して、ユニキャスト通信によってRoute Requestメッセージに相当するパケットをあて先ノードに伝送することができる。これにより、あて先ノードから返送されるRoute Replyメッセージに相当するパケットを受信する、経路上の各ノードが、新たに付加された経路に対する最適なグループを構成することができる。
【００４５】
このように、従来技術を利用した場合と同様に、パケットの伝送経路上のみならず、その伝送パケットを傍受することのできるノードから送出されるパケットの経路をも決定することができる。
【００４６】
以上詳細に説明したように、本実施の形態のルーチング方法によれば、Route Replyメッセージを受信したときに図２に示す処理手順を実行する機能をノードに備え、グループ境界に位置するノードにあっては伝送パケット中に包含される経路情報の置き換えを行う機能を備える。これにより、ノードに蓄積するべき情報を削減して回路規模を小さくすることができ、さらに、伝送パケット中に包含されるべき情報を削減してシステムスループットを改善することができる。
【００４７】
すなわち、伝送するべき情報とともに送出されるべき経路情報として、経路の全長にわたる情報ではなく、その一部のみを含むことが可能となり、さらに、経路を構成するノードにおいて蓄積されるべき経路情報も削減することができるため、ノードを構成するハードウェアの回路規模を削減することができるという効果を有する。
【００４８】
また、本実施の形態では、経路を構成するノード間のリンクのうち、１つ以上のリンクにおいて情報の伝送が不可能となった場合において、上記情報の伝送が不可能であることを検知したノードは、経路が使用不能であることを表示するメッセージを、自ノードの属するグループの、伝送しようとする情報が送られてきた方向のグループ境界ノードに向けて送信する。このメッセージを受信したグループ境界ノードにおいては、このグループの他端に位置するグループ境界ノードに到達可能な代替経路を、その蓄積している経路情報から検索する。代替経路を発見できた場合には、以前に利用していた経路に代えて、以後この代替経路を利用する。これにより、経路の再構築を行う場合において、その全長にわたる再構築を行う必要がなく、一部のみを再構築することによって情報の伝送を行うことができるため、再構築に必要な時間及びシステムスループットへの負荷を小さくできるという効果を有する。
【００４９】
以下、上述した効果を列記する。
【００５０】
効果をリンク状態の変化ごとに経路全体に対する再ルーチングを行う従来のＤＳＲ プロトコルに対して、<効果１>制御パケットのトラフィック量を増大させることがない。
【００５１】
<効果２>大規模（多くのホップを含む経路）ネットワークに対して適用することができる。
【００５２】
<効果３>ルーチングの再構成に必要な時間を短縮することが可能である。
【００５３】
<効果４>各々のノードの保持するべき経路情報テーブルの容量を小さくすることができる。
【００５４】
<効果５>従来のＤＳＲ ルーチングに対して必要とされる制御パケットのサイズ、送出数ともに同等以下とすることができる。
【００５５】
（実施の形態２）
図４は、本発明の実施の形態２に係るルーチング方法によって経路を再構成したネットワーク図である。
【００５６】
図４は、実施の形態１において示されたものと同等の手順で構成された経路４５０において、送出元ノード４００からあて先ノード４０１に向けてパケットを伝送するネットワークの構成を示している。
【００５７】
以下、経路の構成時にノード４０７−Ａに位置するノードが、ノード４０７−Ｂの位置に移動し、通信到達範囲から外れて経路を構成することができなくなった場合のネットワークの動作について説明する。
【００５８】
送出元ノード４００からあて先ノード４０１に向けて経路４５０をたどって転送されるパケットが、ノード４０６に到達したとき、ノード４０６は、実施の形態１で説明した通り、パケット中に格納されているグループ４６１内の経路を参照して、次に転送するべきノード４０７−Ａに向けてパケットを送信する。ところが、ノード４０７−Ａはすでにノード４０７−Ｂの位置に移動しており、ノード４０６の送信する信号の到達範囲外にあるため、このパケットを受信することができない。各ノードは、非特許文献１の８．３．１章乃至８．３．３章に記載の従来技術と同等の手段により、パケットの次段の転送先であるノードがパケットを受信できたこと（あるいはできなかったこと）を検出する手段を有しており、この手段を用いてノード４０７−Ａ（あるいは４０７−Ｂ）がこのパケットを受信できないことを検出する。しかる後、ノード４０６は、非特許文献１の８．３．４章に示される手順に従って、経路４５０が利用不能であることを表すメッセージ（Route Error）を送信する。
【００５９】
実施の形態１で説明した、本発明によってなされる従来技術に対する拡張機能を利用することにより、このRoute Errorメッセージには、あて先ノード４０１に向けて転送されていた元のパケットに含まれているグループ４６１内の経路と同じ経路情報を含んでおり、この経路上で、上流グループ境界ノード４０４から、Route Errorメッセージの送出元ノード４０６までの間にある各ノードは、この経路情報を参照しつつ、グループ４６１内経路を逆にたどってRoute Errorメッセージを転送する。加えて、このRoute Errorメッセージを転送する経路上の各ノードは、蓄積されている経路情報から、このRoute Errorメッセージに含まれる経路情報と同一の情報を取り除く。
【００６０】
以下、本発明によってなされる、従来技術に対する拡張機能について説明する。
【００６１】
図５は、上記グループ境界ノード４０４がRoute Errorメッセージを受信したときに行う処理を示すフローチャートである。
【００６２】
上流グループ境界ノード４０４は、Route Errorメッセージを受信すると（ステップＳ５００）、ステップＳ５０１でRoute Errorメッセージを受信した上流グループ境界ノード４０４は、蓄積されている経路情報から、グループ４６１の下流グループ境界ノード４０８に到達する経路情報を検索する。
【００６３】
ステップＳ５０２では、有効な経路情報があるか否かを判別し、有効な経路情報が蓄積されている場合には、ステップＳ５０３で経路情報を書き換えて本フローを終了する。経路情報の書き換えは、具体的には、以後、あて先ノード４０１に宛てて送出されるパケットに含まれるグループ４６１内経路情報として、この蓄積グループ内経路情報を使用することである。
【００６４】
蓄積グループ内経路情報中に、下流グループ境界ノード４０８に到達できる有効な経路情報が発見できなかった場合には、ステップＳ５０４でグループ境界ノード４０８をあて先とするRoute Requestメッセージに相当するメッセージをブロードキャスト送信して経路を探索する。以下、このRoute Requestメッセージに相当するメッセージをRoute Request２メッセージと呼ぶ。
【００６５】
ステップＳ５０５では、Route Reply２を受信したか否かを判別し、Route Reply２を受信していなければステップＳ５０６でタイムアウトか否かを判別する。タイムアウトでなければ、上記ステップＳ５０５に戻ってRoute Reply２受信を継続する。
【００６６】
上記ステップＳ５０５でRoute Reply２を受信した場合は、ステップＳ５０７で蓄積グループ内経路を置き換えて本フローを終了する。
【００６７】
上記ステップＳ５０６でタイムアウトの場合は、ステップＳ５０８で規定回数の再試行を行い、ステップＳ５０９でRoute Errorメッセージを送信して本フローを終了する。
【００６８】
例えば、Route Request２メッセージを含むパケットの最大伝送ホップ数を、元のグループ内経路のホップ数（ここでは４）を基準として、規定の割合で増加させた数に制限することにより、ブロードキャストされたパケットがネットワークの広い範囲にフラッディングされることを防ぎ、よって制御パケットによるシステムスループットの低下を防ぐ効果を備えることができる。さらに、制限された最大伝送ホップ数に応じたタイムアウト時間を設定することにより、Route Request２メッセージに対する返答として受信されるべきRoute Replyメッセージに相当するメッセージ（以下、Route Reply２メッセージと呼ぶ）が受信されなかった場合（ステップＳ５０６のＮＯ参照）、すなわち経路の探索に失敗した場合であっても、再探索手段をとるまでの時間を短くすることができ、これにより経路の再構築に必要とされる時間を短くすることができるため、パケットの伝送に必要とされる総時間を短縮することによってシステムスループットを改善することができるという効果をも有する。
【００６９】
グループ４６１の下流グループ境界ノード４０８から経路４５１に沿ってRoute Reply２メッセージが返送されるとき、経路４５１上の各ノードは、このRoute Reply２メッセージ中に含まれる経路情報を参照して、このメッセージをノード４０４に転送する。このとき、実施の形態１の記載に関わらず、各ノードにおいてグループの構成動作並びに経路の選択的蓄積は行わず、非特許文献１の８．２．６章記載の従来技術に従って、このメッセージ中の全経路情報を蓄積する。前記Route Reply２メッセージを受信した上流グループ境界ノード４０４は、蓄積されているグループ４６１内経路情報を、新たに発見した経路情報に置き換えして（ステップＳ５０７参照）、以後、あて先ノード４０１に向けて転送するべきパケットの経路情報として、前記蓄積された経路情報に置き換える。
【００７０】
なお、本実施の形態に挙げるグループ内における経路再構築手段が失敗したとき、すなわち、図４においてグループ４６１の下流グループ境界ノード４０８から返送されるRoute Replyメッセージを既定のタイムアウト時間以内に受信することができなかった場合（ステップＳ５０６のＹＥＳ参照）については、あらかじめ規定した回数の試行を繰り返すこと（ステップＳ５０８参照）によって発見の確率を高めることができるほか、前記規定回数の試行によっても経路の発見に至らなかった場合には、パケットの送出元ノード４００に向けてRoute Errorメッセージを含むパケットを送信（ステップＳ５０９参照）することにより、非特許文献１の８．３．４章乃至８．３．５章に記載の従来技術の手順に従って経路全体の再構築を開始することもできる。この場合、Route Errorメッセージがグループ境界ノード４０４によって受信されたとき、パケットの転送手順とは逆に、パケットに包含されるグループ４６１内の経路情報をグループ４６０内の経路情報に置き換えることによって送出元ノード４００までパケットを転送することができる。
【００７１】
以上のように、実施の形態２によれば、パケットを伝送する経路中のリンクの到達性が確保できなくなった場合、経路の再構築を行うときに、経路全体の再構築の試行に対してグループ内の経路の再構築の試行を前置する。これにより、最適な最大ホップ数制限を設定することができるため、システムスループットの低下を防ぐことができるのみならず、タイムアウト時間を短く設定できることから経路の再構築に必要な時間を短縮することができ、システムスループットを改善することができる。
【００７２】
（実施の形態３）
実施の形態３は、実施の形態１の図２に示す処理フローチャートにおいて、経路グループ化手段として新たな基準を持って経路のグループ化を行う第２の経路グループ化手段を備える。第２の経路グループ化手段は、実施の形態１における経路グループ化手段（以下、第１の経路グループ化手段と呼ぶ）によって形成されたグループとは異なるグループ境界ノードを持つ、同程度のノード数からなるグループ（以下、第２の経路グループと呼ぶ）を形成する。
【００７３】
図６は、本発明の実施の形態３に係るルーチング方法の望ましい算出方法の例を適用したときのグループの構成を示すネットワーク図であり、２つの経路グループ化手段によって構成されたグループからなる経路を持つネットワークを示す。
【００７４】
図６において、グループ６６０乃至６６２は、実施の形態１の図３により説明した算出方法を備える経路グループ化手段によって形成されたグループ（以下、第１の経路グループと呼ぶ）である。
【００７５】
第２の経路グループ化手段におけるあらかじめ規定された算出方法としては、送出元ノードを０として、あて先ノードにいたる経路上の各ノードに対して、ホップごとに１ずつ増やした番号付けを行い、経路を構成する全ノード数「１１」の平方根（約３．３２）の整数倍（０を含む、すなわち、０と約３．３２と約６．６３）に、前記平方根値の２分の１（約１．６６）を加えた数に最も近い番号（すなわち、２と５と８）を持つノードをグループ境界ノードとする、送出元ノード及びあて先ノードを含まない２つのグループを構成するように規定する。
【００７６】
また、グループ６７０及びグループ６７１は、第２の経路グループ化手段によって形成された第２の経路グループである。第２の経路グループにおいては、グループ境界ノードのみがグループ内の経路を蓄積しており、かつ、下流側グループにおける経路のみを蓄積するものとする。
【００７７】
以下、グループ内経路再構築試行が失敗した場合における動作を説明する。
【００７８】
送出元ノード６００からあて先ノード６０１に向けて経路６５０をたどって転送されるパケットが、ノード６０６に到達したとき、ノード６０６は、実施の形態１で説明した通り、パケット中に格納されているグループ６６１内の経路を参照して、次に転送するべきノード６０７−Ａに向けてパケットを送信する。ここで、ノード６０７−Ａはすでに６０７−Ｂで示す位置に移動しており、ノード６０６の送信する信号の到達範囲外にあるため、このパケットを受信することができない。これを検知したノード６０６は、実施の形態２で説明したグループ内経路再構築動作を起動するが、グループ６６１の下流グループ境界ノード６０９への経路を再構築することに失敗する。
【００７９】
以下、本実施の形態によってなされる、従来技術に対する拡張機能について説明する。
【００８０】
グループ内経路再構築試行が失敗したことを検知したグループ境界ノード６０４は、グループ内経路再構築の試行を開始する原因となったRoute Errorメッセージを生成したノード６０６に宛ててグループ内経路再構築が失敗したことを表示するメッセージを送信する。以下、このメッセージをReroute Failureメッセージと呼ぶ。
【００８１】
このReroute Failureメッセージを受信したノード６０６は、上記第２のグループにおいて自ノードの属するグループの上流境界ノードに宛ててRoute Errorメッセージに相当するメッセージを送信する。以下、本メッセージをRoute Error３メッセージと呼ぶ。図６においては、ノード６０６は第２のグループにおけるグループ境界ノードであるため、Route Error３メッセージを送信することなく以下の手順を実行する。
【００８２】
グループ境界ノード６０６が前記Reroute FailureメッセージあるいはRoute Error３メッセージを受信したとき、ノード６０６は蓄積されている経路情報から、第２のグループ６７１の下流グループ境界ノード６０９に到達する経路情報を検索する。有効なこの経路情報が蓄積されている場合には、送出元ノード６００から第２グループの上流グループ境界ノードこの経路を含む経路の一部再構築を要求するメッセージをノード６０９に宛てて送信する。以下、このメッセージをReroute Requestメッセージと呼ぶ。
【００８３】
蓄積グループ内経路情報中に、ノード６０９に到達できる有効な経路情報が発見できなかったときには、ノード６０９をあて先とする実施の形態２において説明したRoute Request２メッセージをブロードキャスト送信して経路を探索する。
【００８４】
このとき、Route Request２メッセージを含むパケットの最大伝送ホップ数を、元のグループ内経路のホップ数（ここでは４）を基準として、規定の割合で増加させた数に制限することにより、ブロードキャストされたパケットがネットワークの広い範囲にフラッディングされることを防ぎ、よって制御パケットによるシステムスループットの低下を防ぐ効果を備えることができる。さらに、制限された最大伝送ホップ数に応じたタイムアウト時間を設定することにより、Route Request２メッセージに対する応答としてRoute Reply２メッセージが受信されなかった場合、すなわち経路の探索に失敗した場合であっても、再探索手段をとるまでの時間を短くすることができ、これにより経路の再構築に必要とされる時間を短くすることができるため、パケットの伝送に必要とされる総時間を短縮してシステムスループットを改善することができるという効果をも有する。
【００８５】
ノード６０９から経路６５１に沿ってRoute Reply２メッセージが返送されるとき、経路６５１上の各ノードは、このRoute Reply２メッセージ中に含まれる経路情報を参照して、このメッセージをノード６０６に転送する。このとき、上記実施の第１の形態の記載、並びに非特許文献１の８．２．６章記載の従来技術の記載に関らず、このメッセージ中の経路情報は一切蓄積しない。
【００８６】
ノード６０６がノード６０９に到達できる有効な経路情報をその蓄積情報から発見した場合、又は、ノード６０９から返信された前記Route Reply２メッセージを受信した場合、ノード６０６は、前記蓄積情報から発見した経路情報又は前記Route Reply２メッセージによって通知された、ノード６０６からノード６０９に至る経路情報に、自ノードに蓄積されている、上流グループ境界ノード６０４から自ノードに至る経路情報を継ぎ足した経路情報を含むReroute Requestメッセージをノード６０９に宛てて送信する。このReroute Requestメッセージを受信したノード６０９は、蓄積されている経路情報から、自ノードの属するグループの下流グループ境界ノードまでの経路情報を前記受信したReroute Requestメッセージに含まれるノード６０４からノード６０９に至る経路情報に継ぎ足して、ノード６０４からノード６０１に至る経路を完成する。次に、ノード６０９は、完成した前記経路情報を含むメッセージをノード６０６に宛てて送信する。以下、このメッセージをReroute Replyメッセージと呼ぶ。
【００８７】
Reroute Replyメッセージを受信する各ノードは、このメッセージに含まれる、ノード６０６からノード６０１に至る経路情報を参照して、このメッセージをノード６０６に転送する。このとき、各ノードはグループ２経路再構築手段をもって経路のグループ化を行い、実施の形態１における前記図２の処理フローチャートに従って処理を行う。このとき、経路グループ化手段はグループ２経路再構築手段と読み替えるものとし、その算出方法は同一のものである必要はない。
【００８８】
例えば、前記グループ２経路再構築手段における算出方法として、送出元ノードを０として、あて先ノードにいたる経路上の各ノードに対して、ホップごとに１ずつ増やした番号付けを行い、経路を構成する全ノード数「１０」の２分の１に最も近い番号（すなわち、５）を持つノードをグループ境界ノードとする２つのグループを構成する手段をとった場合のグループの構成を図６のグループ６８０及びグループ６８１に示す。
【００８９】
以上のように、実施の形態３によれば、パケットを伝送する経路中のリンクの到達性が確保できなくなった場合、経路の再構築を行うときに、経路全体の再構築の試行に対して、あらかじめ設定された第２グループ内の経路の再構築の試行を前置する。これにより、最適な最大ホップ数制限を設定することができるため、システムスループットの低下を防ぐことができるのみならず、タイムアウト時間を短く設定できることから経路の再構築に必要な時間を短縮することができ、システムスループットを改善することができる。
【００９０】
また、第１グループにおけるグループ境界ノードとは異なるノードになるように設定された第２グループにおけるグループ境界ノードに蓄積されている経路情報に、同一第２グループ内の下流グループ境界ノードへ到達可能な経路が蓄積されている場合には、ブロードキャスト送信による経路探索手順をとることなく新たな経路の構築が可能となる。これにより、経路全体の再構築を行う場合に比べて短時間に、かつ、システムスループットに極めて小さい影響のみを与えることによって経路の再構築を実現することができる。
【００９１】
（実施の形態４）
実施の形態４は、実施の形態１の図２に示す処理フローチャートにおいて、自ノード位置がグループ境界であることを知った場合（ステップＳ２０５のＹＥＳ参照）に、上流グループ内経路を蓄積（ステップＳ２０６参照）するとともに、自ノードの属する２つの隣接グループのうちの下流グループに、さらに下流隣接グループが存在する場合には、この下流隣接グループの下流グループ境界ノードのアドレスを蓄積する手段を加えて備える。このアドレス蓄積手段を加えた処理フローチャートを図７に示す。
【００９２】
図７は、本発明の実施の形態４に係るルーチング方法のRoute Replyメッセージを受信した際に各ノードで行う処理を示すフローチャートである。図２に示す処理ステップと同一処理を行うステップには同一符号を付して重複部分の説明を省略する。
【００９３】
ステップＳ２０６で上流側グループ内の経路を蓄積すると、ステップＳ７１０で下流隣接グループ内の下流グループ境界ノードアドレスを蓄積してステップＳ２０７に進む。前記アドレス蓄積手段は、上記ステップＳ７１０で示す位置で処理される。
【００９４】
図８は、本発明の実施の形態４に係るルーチング方法の望ましい算出方法の例を適用したときのグループの構成を示すネットワーク図である。
【００９５】
以下、実施の形態２に記述したグループ内経路再構築試行が失敗した場合における実施の形態４の動作を説明する。
【００９６】
送出元ノード８００からあて先ノード８０１に向けて経路８５０をたどって転送されるパケットが、ノード８０６に到達したとき、ノード８０６は、上記第１の実施例において説明したとおり、パケット中に格納されているグループ８６１内の経路を参照して、次に転送するべきノード８０７−Ａに向けてパケットを送信する。ここで、ノード８０７−Ａはすでに８０７−Ｂで示す位置に移動しており、ノード８０６の送信する信号の到達範囲外にあるため、このパケットを受信することができない。これを検知したノード８０６は、実施の形態２で説明したグループ内経路再構築動作を起動するが、グループ８６１の下流グループ境界ノード８０８への経路を再構築することに失敗する。
【００９７】
以下、本実施の形態によってなされる、従来技術に対する拡張機能について説明する。
【００９８】
グループ内経路再構築試行が失敗したことを検知したグループ境界ノード８０４は、あらかじめ蓄積してあった、自ノードの属する下流グループ８６１に隣接するグループ８６２の下流グループ境界ノード（図８にあってはあて先ノード）８０１のアドレスを取り出す。
【００９９】
次に、ノード８０４は、前記取り出したノード８０１をあて先とする、Route Requestメッセージに相当するメッセージをブロードキャスト送信して経路を探索する。以下、このRoute Requestメッセージに相当するメッセージをRoute Request４メッセージと呼ぶ。
【０１００】
ここで、前記自ノードの属する下流グループに隣接するグループの下流グループ境界ノードのアドレスを蓄積する手段に加えて、自ノードからこの下流グループ境界ノードまでのホップ数を合わせて蓄積する手段を設けることにより、Route Request４メッセージを含むパケットの最大伝送ホップ数を、この蓄積されたホップ数（図８においては７）を基準として、規定の割合で増加させた数に制限することにより、ブロードキャストされたパケットがネットワークの広い範囲にフラッディングされることを防ぎ、よって制御パケットによるシステムスループットの低下を防ぐ効果を備えることができる。さらに、制限された最大伝送ホップ数に応じたタイムアウト時間を設定することにより、Route Request４メッセージに対する応答としてノード８０１が送信するRoute Replyメッセージに相当するメッセージ（以下、Route Reply４メッセージと呼ぶ）が受信されなかった場合、すなわち経路の探索に失敗した場合であっても、再探索手段をとるまでの時間を短くすることができ、これにより経路の再構築に必要とされる時間を短くすることができるため、パケットの伝送に必要とされる総時間を短縮してシステムスループットを改善することができるという効果をも有する。
【０１０１】
ノード８０１から、発見された新たな経路８５１に沿ってRoute Reply４メッセージが返送されるとき、経路８５１上の各ノードは、このRoute Reply４メッセージ中に含まれる、ノード８０４からノード８０１に至る経路情報を参照して、このメッセージをノード８０４に転送する。また、Route Reply４を受信する各ノードは、前記図７に示すフローチャートに従って処理を行い、前記経路グループ化手段に従って自ノードの属するグループ内の経路のみを蓄積する。
【０１０２】
前記図７に示すフローチャートの処理内容のうち、前記経路グループ化手段の参照する算出方法としては、実施の形態１において例示した算出方法とは異なる方法をとることが可能であり、望ましくは、前記新たに発見した経路８５１を構成する全ノード数をおよそ等分するように構成した２つのグループを構成するように算出する方法もとることができる。
【０１０３】
上記Route Reply４メッセージをノード８０４が受信したとき、有効でなくなった経路８５０に代わって新たに発見された経路８５１が蓄積され、以後、送出元ノード８００からあて先ノード８０１に宛てて転送されるパケットの伝送されるべき経路として前記経路８５１が使用される。
【０１０４】
以上のように、実施の形態４によれば、グループ境界ノードにおいて、グループ内の経路情報に加えて下流隣接グループの下流グループ境界ノードのアドレスと、望ましくは自ノードからこの下流グループ境界ノードまでのホップ数を蓄積し、パケットの伝送に使用していた経路が利用不能になったことを検出したときに、ブロードキャストパケットの送信によって新たな経路を探索する。これにより、従来の技術に比べて経路を発見する時間を短くすることができる。
【０１０５】
また、前記ブロードキャストパケットの送信範囲を、前記蓄積されたホップ数を基準として決定した範囲に限定することにより、システムスループットに与える影響を小さくすることができる。
【０１０６】
さらに、従来の技術における経路の再構築動作を完了するためには、Route Replyメッセージは送出元ノードまで伝送されなければならないのに対して、上記Route Request４メッセージはリンクの断絶を検知したノードの属するグループ境界ノードまで伝送されることによって経路の再構築動作を完了することができるため、必要な時間を短縮する効果がある上、制御パケットの伝送によりシステムスループットに与える負荷を軽減することができる。
【０１０７】
（実施の形態５）
実施の形態５は、実施の形態４と同様に、送出元ノード８００からあて先ノード８０１に向けて経路８５０をたどって転送されるパケットが、ノード８０６に到達したとき、ノード８０６は、実施の形態１で説明した通り、パケット中に格納されているグループ８６１内の経路を参照して、次に転送するべきノード８０７−Ａに向けてパケットを送信する。ここで、ノード８０７−Ａはすでに８０７−Ｂで示す位置に移動しており、ノード８０６の送信する信号の到達範囲外にあるため、このパケットを受信することができない。これを検知したノード８０６は、実施の形態２で説明したグループ内経路再構築動作を起動するが、グループ８６１の下流グループ境界ノード８０９への経路を再構築することに失敗する。
【０１０８】
以下、本実施の形態によってなされる、従来技術に対する拡張機能について説明する。
【０１０９】
グループ内経路再構築試行が失敗したことを検知したグループ境界ノード８０４は、あらかじめ蓄積してあった経路情報のうち、あて先ノード８０１のアドレスを取り出す。
【０１１０】
次に、ノード８０４は、前記取り出したノード８０１をあて先とする、Route Requestメッセージに相当するメッセージをブロードキャスト送信して経路を探索する。以下、このRoute Requestメッセージに相当するメッセージをRoute Request５メッセージと呼ぶ。
【０１１１】
この場合、実施の第１の形態において説明した、図２に挙げるRoute Replyメッセージの受信の際に各ノードにおいて行われるべき処理のフローチャートにおいて、上流グループ内経路を蓄積する処理（図７のステップＳ２０６）と同時に、自ノードからあて先ノード８０１までのホップ数を合わせて蓄積する手段を設けることにより、Route Request５メッセージを含むパケットの最大伝送ホップ数を、この蓄積されたホップ数（図８においては７）を基準として、規定の割合で増加させた数に制限することにより、ブロードキャストされたパケットがネットワークの広い範囲にフラッディングされることを防ぎ、よって制御パケットによるシステムスループットの低下を防ぐ効果を備えることができる。さらに、制限された最大伝送ホップ数に応じたタイムアウト時間を設定することにより、Route Request５メッセージに対する応答としてノード８０１が送信するRoute Replyメッセージに相当するメッセージ（以下、Route Reply５メッセージと呼ぶ）が受信されなかった場合、すなわち経路の探索に失敗した場合であっても、再探索手段をとるまでの時間を短くすることができ、これにより経路の再構築に必要とされる時間を短くすることができるため、パケットの伝送に必要とされる総時間を短縮してシステムスループットを改善することができるという効果をも有する。
【０１１２】
あて先ノード８０１から、発見された新たな経路８５１に沿ってRoute Reply５メッセージが返送されるとき、経路８５１上の各ノードは、このRoute Reply５メッセージ中に含まれる、ノード８０４からノード８０１に至る経路情報を参照して、このメッセージをノード８０４に転送する。また、Route Reply５を受信する各ノードは、図７に示すフローチャートに従って処理を行い、前記経路グループ化手段に従って自ノードの属するグループ内の経路のみを蓄積する。
【０１１３】
前記図７に示すフローチャートの処理内容のうち、前記経路グループ化手段の参照する算出方法としては、実施の形態１において例示した算出方法とは異なる方法をとることが可能であり、望ましくは、経路８５０において自ノード８０４からあて先ノード８０１までの間に存在したグループ数（図８においては２）と等しいか、もしくは、グループあたりに含まれる平均のノード数（図８においては４）に近い数のノードからなるグループを新たに発見した経路８５１上に構成するように算出する方法もとることができる。また、上記算出方法として、実施の形態１におけると同じ方法をとる場合にあっては、Route Request５メッセージ及びRoute Reply５メッセージの構造は、それぞれ従来技術のRoute Requestメッセージ及びRoute Replyメッセージの構造と同一の構造をとることができ、各ノードにおける処理に対しても特段の追加機能を必要としない。
【０１１４】
上記Route Reply５メッセージをノード８０４が受信したとき、有効でなくなった経路８５０に代わって新たに発見された経路８５１が蓄積され、以後、送出元ノード８００からあて先ノード８０１に宛てて転送されるパケットの伝送されるべき経路として前記経路８５１が使用される。
【０１１５】
以上のように、実施の形態５によれば、パケットの伝送に使用していた経路が利用不能になったことを検出したときに、前記経路が利用不能であることを検出したノードの属するグループの上流グループ境界ノードを起点としたブロードキャストパケットの送信によって新たな経路を探索する。これにより、従来の技術に比べて経路を発見する時間を短くすることができる。
【０１１６】
また、経路の構築を行う際に転送されるRoute Replyメッセージの処理を行う際に、グループ境界ノードからあて先ノードまでのホップ数を蓄積するようにノードを構成することにより、前記ブロードキャストパケットの送信範囲を、前記蓄積されたホップ数を基準として決定した範囲に限定することにより、システムスループットに与える影響を小さくすることができる。
【０１１７】
さらに、従来の技術における経路の再構築動作を完了するためには、Route Replyメッセージは送出元ノードまで伝送されなければならないのに対して、上記Route Request５メッセージはこのメッセージを送信したグループ境界ノードまで伝送されることによって経路の再構築動作を完了することができるため、必要な時間を短縮する効果がある上、制御パケットの伝送によりシステムスループットに与える負荷を軽減することができる。
【０１１８】
（実施の形態６）
上記各実施の形態では、経路に含まれる全ノードをグループ化し、グループ内においてのみルーチングの再構成を行う。グループ内において解決できない場合、グループの上流ノードから目的ノードまでの経路の探索を行い、グループの再構成を行う。グループはＤＳＲにおけるRoute Reply オプションヘッダの内容にしたがって自律的に構成する。この構成によって、伝送するべき情報とともに送出されるべき経路情報として、経路の全長にわたる情報ではなく、その一部のみを含むこうとが可能となり、さらに、経路を構成するノードにおいて蓄積されるべき経路情報も削減することができるため、ノードを構成するハードウェアの回路規模を削減することができる。しかし、グループの境界地点で切断した場合には、従来例が良いことも考えられる。
【０１１９】
実施の形態６は、仮想的に他のグループを作り、境界地点で切断した場合、仮想グループに切り替える例について説明する。
【０１２０】
図９は、本発明の実施の形態６に係るルーチング方法によって経路を構成したネットワーク図である。
【０１２１】
図９において、経路の断絶が起こった場合（α）に対して、以下の方法を採る。
i）グループ内の経路再探索が失敗した場合（β）には、
ii）ルーチング用のグループ内のホップ数の約１／２だけずらして、あらかじめ構成されている経路再探索専用グループ（甲、乙）においてグループ内再探索（γ）を行い、
iii）再び失敗した場合に限って送出元ノードからの全体経路の再探索（従来技術）を行う。
【０１２２】
これにより、経路再探索専用グループにおいては、以下の効果を得ることができる。
i）ルーチング用グループと同時に自律的に構成できるため、実施の形態１で述べた<効果１><効果２><効果５>を損なわない。
ii）実施の形態１で述べた<効果４>の経路情報テーブルサイズにおいては、実施の形態１には劣るものの従来技術に対する優位性は保持したままである。
iii）実施の形態１で述べた<効果３>の再構成時間を短縮できる条件を大幅に拡大できる。
【０１２３】
以上の説明は本発明の好適な実施の形態の例証であり、本発明の範囲はこれに限定されることはない。例えば、非特許文献１に記載されているＤＳＲプロトコルを使用してルーチング機能を実現するネットワークに適用することもできるが、複数のノードが相互接続されるネットワークにおいて、情報の伝送を行う通信経路を各ノードが自律的に選択して通信を行うルーチング方法であればよく、上位バージョンが策定された場合はこれも包含するものである。
【０１２４】
また、本実施の形態ではルーチング方法及びノード装置という名称を用いたが、これは説明の便宜上であり、ルーチンググループの自律構成方法等であってもよいことは勿論である。
【０１２５】
さらに、上記ルーチング方法及びノード装置を構成する各部、例えば暗号鍵生成部の種類、その数及び接続方法などはどのようなものでもよい。
【０１２６】
以上説明したルーチング方法は、このルーチング方法を機能させるためのプログラムでも実現される。このプログラムはコンピュータで読み取り可能な記録媒体に格納されている。
【産業上の利用可能性】
【０１２７】
以上のように、本発明にかかるルーチング方法は、ノードに蓄積するべき経路情報を削減できることからノードを構成するハードウェアの回路規模を削減することができ、転送するべきパケットに含まれる経路情報を削減できることから伝送スループットを改善することができる上、伝送状態の変化によって構成した経路が使用不能となった場合であっても、高速に、必要な制御パケットの送信量を削減しつつ経路の再構築を行うことができるため、システムスループットに与える影響を小さくできるという効果を有し、最適な通信経路を選択して通信を行う通信システムに使用するルーチング方法等として有用である。
【図面の簡単な説明】
【０１２８】
【図１】本発明の実施の形態１に係るルーチング方法によって経路を構成したネットワーク図
【図２】本実施の形態１に係るルーチング方法のRoute Replyメッセージを受信した際に各ノードで行う処理を示すフロー図
【図３】本実施の形態１に係るルーチング方法の望ましい算出方法の例を適用したときのグループの構成を示すネットワーク図
【図４】本発明の実施の形態２に係るルーチング方法によって経路を再構成したネットワーク図
【図５】本実施の形態２に係るルーチング方法のグループ境界ノードがRoute Errorメッセージを受信したときに行う処理を示すフロー図
【図６】本発明の実施の形態３に係るルーチング方法の望ましい算出方法の例を適用したときのグループの構成を示すネットワーク図
【図７】本発明の実施の形態４に係るルーチング方法のRoute Replyメッセージを受信した際に各ノードで行う処理を示すフロー図
【図８】本実施の形態４に係るルーチング方法の望ましい算出方法の例を適用したときのグループの構成を示すネットワーク図
【図９】本発明の実施の形態６に係るルーチング方法によって経路を構成したネットワーク図
【図１０】従来のネットワークにおける経路の再構成動作を説明するネットワーク構成図
【図１１】従来のネットワークにおける経路の再構成動作を説明するネットワーク構成図
【符号の説明】
【０１２９】
１００，１０１〜１１０，３００，３０１〜３１０，４００，４０１〜４１０，６００，６０１〜６１０，６２０，６２１，６２２，６２３，８００，８０１〜８１０，  ノード
１５０，３５０，４５０，４５１，６５０，６５１，８５０，８５１  経路
【図１】
0004927658.tif 000005
【図２】
0004927658.tif 000006
【図３】
0004927658.tif 000007
【図４】
0004927658.tif 000008
【図５】
0004927658.tif 000009
【図６】
0004927658.tif 000010
【図７】
0004927658.tif 000011
【図８】
0004927658.tif 000012
【図９】
0004927658.tif 000013
【図１０】
0004927658.tif 000014
【図１１】
0004927658.tif 000015