(57)【特許請求の範囲】
【請求項１】
ネットワークに接続され互いに情報を送受可能なノードであって、
少なくとも１ホップ先のノードのいずれかが故障して異常が発生した場合、その異常が発生した隣接ノードを検出する隣接ノード異常検出手段と、
前記ネットワークを復旧させるために、前記隣接ノード異常検出手段で検出された隣接ノードに代わる新しい接続先のノードを決定するリカバリー先ノード決定手段と、
前記リカバリー先ノード決定手段で決定された前記新しい接続先のノードとの接続を確立するコネクション確立手段と、
を備え、
前記リカバリー先ノード決定手段は、前記隣接ノードまでの平均メトリックス値を計算する計算手段を備え、当該計算手段で計算された平均メトリックス値を比較して当該メトリックス値が最小のノードを前記新しい接続先のノードとし、前記コネクション確立手段は、前記平均メトリックス値が最小のノードにコネクションを張り、ネットワークトポロジーを生成することを特徴とするノード。
【請求項２】
請求項１のノードにおいて、
前記少なくとも１ホップ先のノードが持っている隣接ノード情報を取得する隣接ノード情報取得手段と、前記隣接ノード情報を所定の場所に格納する隣接ノード情報記憶手段と、をさらに備え、前記リカバリー先ノード決定手段は、前記隣接ノード異常検出手段で検出された隣接ノードについての前記隣接ノード情報を参照して、前記新しい接続先のノードを決定することを特徴とするノード。
【請求項３】
請求項２のノードにおいて、
前記隣接ノード情報は、前記隣接ノードと、当該隣接ノードが隣接するノードとの親子関係を含み、当該隣接ノードに対して当該隣接ノードが隣接ずるノードが親の場合、前記リカバリー先ノード決定手段は、当該隣接ノードが隣接するノードを前記新しい接続先のノードの候補とすることを特徴とするノード。
【請求項４】
ネットワークに接続され互いに情報を送受可能なノードの少なくとも１ホップ先のノードのいずれかが故障して異常が発生した場合、前記ネットワークを復旧させるネットワークリカバリーシステムであって、
前記ノードの各々が、
当該異常が発生した隣接ノードを検出する隣接ノード異常検出手段と、
前記隣接ノード異常検出手段で検出された隣接ノードに代わる新しい接続先のノードを決定するリカバリー先ノード決定手段と、
前記少なくとも１ホップ先のノードが持っている隣接ノード情報を取得する隣接ノード情報取得手段と、
前記隣接ノード情報を所定の場所に格納する隣接ノード情報記憶手段と、
を備え、前記リカバリー先ノード決定手段は、
前記隣接ノード異常検出手段で検出された隣接ノードについての前記隣接ノード情報を参照して、前記新しい接続先のノードを決定し、当該新しい接続先のノードとの接続を確立し、
前記隣接ノードまでの平均メトリックス値を計算する計算手段を備え、当該計算手段で計算された平均メトリックス値を比較して当該メトリックス値が最小のノードを前記新しい接続先のノードとし、前記平均メトリックス値が最小のノードにコネクションを張り、ネットワークトポロジーを生成することを特徴とするネットワークリカバリーシステム。
【請求項５】
ネットワークに接続され互いに情報を送受可能なノードの少なくとも１ホップ先のノードのいずれかが故障して異常が発生した場合、前記ネットワークを復旧させるネットワークリカバリー方法であって、
当該異常が発生した隣接ノードを検出する隣接ノード異常検出ステップと、
前記隣接ノード異常検出手段で検出された隣接ノードに代わる新しい接続先のノードを決定するリカバリー先ノード決定ステップと、
前記少なくとも１ホップ先のノードが持っている隣接ノード情報を取得する隣接ノード情報取得ステップと、
前記隣接ノード情報を所定の場所に格納する隣接ノード情報記憶ステップと、
を含み、前記リカバリー先ノード決定ステップにおいて、
前記隣接ノード異常検出ステップで検出された隣接ノードについての前記隣接ノード情報を参照して、前記新しい接続先のノードを決定し、当該新しい接続先のノードとの接続を確立し、
前記隣接ノードまでの平均メトリックス値を計算する計算手段を備え、当該計算手段で計算された平均メトリックス値を比較して当該メトリックス値が最小のノードを前記新しい接続先のノードとし、前記平均メトリックス値が最小のノードにコネクションを張り、ネットワークトポロジーを生成することを特徴とするネットワークリカバリー方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ネットワークを構成する複数のノードのうち任意のノードの故障や離脱などによって分断されたネットワークを復旧させるネットワークリカバリーシステム及びネットワークリカバリー方法並びにノードに関する。
【背景技術】
【０００２】
インターネット環境の普及に伴ってＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ネットワークの利用範囲が広がり、あらゆる環境にグローバルなＩＰアドレスが提供されるようになってきている。この傾向は、ＩＰｖ６（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  Ｖｅｒｓｉｏｎ  ６）の普及によって益々高まり、家電製品やＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）等の様々な電子機器に対してＩＰアドレスが付与されることになる。
【０００３】
例えば、音声等の高品質を要求するリアルタイムアプリケーションをＩＰネットワークの環境下で動作させるためには、任意のノード間での品質を確保する必要があり、このような必要性から、広域に分散した多ノード環境下では一方のノードが故障する場合あるいは経路が切断される場合も多々あり、従って、任意の２ノード間の経路を選択し、所望の経路を選択したいという要求が生じている。
この場合、例えば、特許文献１に記載のネットワークにおける経路選択方法では、リンクが切断されたときに、送信意図ノードは、送信相手先ノードとの間のリンクを中継できる適当なノードを検索し、中継可能なノードを発見できれば当該ノードを中継ノードとして選択し、当初の送信相手先ノードにデータを送信している。
【０００４】
また、特許文献２に記載の分散障害回復装置では、通常時に設定されるコネクションの経路として、負荷分散経路計算手段が、候補経路データベースより負荷分散効果の高い経路を選んでコネクション設定を行うことで、高負荷のリンクが偏在しないようにリンク資源を利用する装置であり、障害によって切断されたコネクションのための復旧用コネクションの経路として、負荷分散復旧経路計算手段が、候補経路データベースより負荷分散効率の高い経路を選んで復旧用コネクション設定を行うことで、復旧用コネクションがあるリンクに集中することを防止している。
【特許文献１】特開２００３−２９８５９４号公報
【特許文献２】特開２００１−２９８４８２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した特許文献１記載の発明は、リンクが遮断されたときに、送信意図ノードが中継ノードを選択することによって、当初の送信相手先にデータを送信するが、この発明は、中継ノードが、送信意図ノードと同格のいずれかのノードから選択され、送信意図ノードの情報を一度その中継ノードに渡した後、再度所望のノードに送信する必要があり、コネクションを確立し直すものではないので、その場限りの応急処置であり分断されたネットワークを復旧することはできないという問題がある。
【０００６】
また、特許文献２に記載の発明は、通常時に設定されるコネクションの経路として負荷分散効果の高い経路を選んでコネクション設定を行い、高負荷リンクが偏在しないように、リンク資源を利用して復旧用コネクションがあるリンクに集中することを防止するものであり、表面上では、ネットワーク内で各ノードが自律的にネットワークトポロジ情報を交換し、障害により切断されたコネクションを再接続するように構成されているが、この発明も、計算で得られた経路に沿って負荷分散効果の高い経路を選択するものであり、、障害ノードを迂回する必要があり、コネクションを確立し直すものではないので分断されたネットワークを復旧することはできないという問題がある。
【０００７】
また、従来のピアツーピア（Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ；Ｐ２Ｐ）システムでは、ノードの離脱や故障などによるネットワークの分断をリカバリーする機能を有していない。すなわち、ピアツーピアネットワークトポロジー構成方式においては、新規ノードは、ＰｉｎｇとＰｏｎｇメッセージでネットワークに参加し、ランダム的にネットワークトポロジーを生成する。従って、物理層のネットワーク状況を考慮していないために、論理層において、ノード間が隣接しても、実際に目的ノードに達するのにネットワーク遅延が相当大きい可能性があり、目的ノードにデータ転送する効率が低くなり、通信品質も劣化するという問題がある。
この発明は、上記事情を鑑みてなされたものであって、隣接ノードの離脱や故障等が生じた場合に、ネットワークを速やかに回復させ、通信品質の向上を図ったネットワークリカバリーシステム及び方法並びにノードを提供することを目的としている。
【課題を解決するための手段】
【０００８】
上記目的を達成するために、請求項１に記載のノードは、
ネットワークに接続され互いに情報を送受可能なノードであって、
少なくとも１ホップ先のノードのいずれかが離脱又は故障等して異常が発生した場合、その異常が発生した隣接ノードを検出する隣接ノード異常検出手段と、
前記ネットワークを復旧させるために、前記隣接ノード異常検出手段で検出された隣接ノードに代わる新しい接続先のノードを決定するリカバリー先ノード決定手段と、
前記リカバリー先ノード決定手段で決定された前記新しい接続先のノードとの接続を確立するコネクション確立手段と、
を備えたことを特徴とする。
【０００９】
この構成によれば、隣接ノード異常検出手段により、少なくとも１ホップ先のノードのいずれかが離脱又は故障等して異常が発生した場合、その異常が発生した隣接ノードを検出し、リカバリー先ノード決定手段により、ネットワークを復旧させるために、隣接ノード異常検出手段で検出された隣接ノードに代わる新しい接続先のノードを決定し、コネクション確立手段により、リカバリー先ノード決定手段で決定された新しい接続先のノードとの接続を確立するので、あるノードに異常が発生し、ネットワークが中断した場合、ノード間の情報によりその異常が発生したノードを介さずに新しいノードと情報を送受可能になり、隣接ノードまでのネットワーク遅延を極力抑制することができ、ネットワークを速やかに回復させることができ、かつ通信品質を保持することができるという効果が得られる。
【００１０】
請求項２に記載のノードは、請求項１において、
前記少なくとも１ホップ先のノードが持っている隣接ノード情報を取得する隣接ノード情報取得手段と、前記隣接ノード情報を所定の場所に格納する隣接ノード情報記憶手段と、をさらに備え、前記リカバリー先ノード決定手段は、前記隣接ノード異常検出手段で検出された隣接ノードについての前記隣接ノード情報を参照して、前記新しい接続先のノードを決定することを特徴とする。
【００１１】
この構成によれば、隣接ノード情報取得手段により、少なくとも１ホップ先のノードが持っている隣接ノード情報を取得し、隣接ノード情報記憶手段により、隣接ノード情報を所定の場所に格納するので、隣接ノードが離脱したり又は故障したりして異常が発生した場合、リカバリー先ノード決定部が、隣接ノード情報情報記憶手段に記憶されている隣接ノード情報を参照して、ネットワークをリカバリーするための新しい接続先のノードを決定することができ、ネットワークを速やかに回復させることができるという効果が得られる。
【００１２】
請求項３に記載のノードは、請求項２において、
前記隣接ノード情報は、前記隣接ノードと、当該隣接ノードが隣接するノードとの親子関係を含み、当該隣接ノードに対して当該隣接ノードが隣接ずるノードが親の場合、前記リカバリー先ノード決定手段は、当該隣接ノードが隣接するノードを前記新しい接続先のノードの候補とすることを特徴とする。
この構成によれば、隣接ノード情報は、隣接ノードと、隣接ノードが隣接するノードとの親子関係を含み、隣接ノードに対して隣接ノードが隣接するノードが親の場合、リカバリー先ノード決定手段は、当該隣接ノードが隣接するノードを新しい接続先のノードの候補とするので、ネットワークを速やかに回復させることができ、かつ通信品質を保持することができるという効果が得られる。
【００１３】
請求項４に記載のノードは、請求項１〜３のいずれか１項において、
前記リカバリー先ノード決定手段は、前記隣接ノードまでの平均メトリックスを計算する計算手段を備え、当該計算手段で計算された平均メトリックス値が最小のノードを前記新しい接続先のノードとすることを特徴とする。
この構成によれば、リカバリー先ノード決定手段は、隣接ノードまでの平均メトリックスを計算する計算手段を備え、当該計算手段で計算された平均メトリックス値が最小のノードをリカバリー先ノードに決定するので、ネットワーク遅延を最小に抑制することができ、データ転送の効率を向上させることができるという効果が得られる。
【００１４】
請求項５に記載のネットワークリカバリーシステムは、
ネットワークに接続され互いに情報を送受可能なノードの少なくとも１ホップ先のノードのいずれかが離脱又は故障等して異常が発生した場合、前記ネットワークを復旧させるネットワークリカバリーシステムであって、
前記ノードの各々が、
当該異常が発生した隣接ノードを検出する隣接ノード異常検出手段と、
前記隣接ノード異常検出手段で検出された隣接ノードに代わる新しい接続先のノードを決定するリカバリー先ノード決定手段と、
前記少なくとも１ホップ先のノードが持っている隣接ノード情報を取得する隣接ノード情報取得手段と、
前記隣接ノード情報を所定の場所に格納する隣接ノード情報記憶手段と、
を備え、前記リカバリー先ノード決定手段は、前記隣接ノード異常検出手段で検出された隣接ノードについての前記隣接ノード情報を参照して、前記新しい接続先のノードを決定し、当該新しい接続先のノードとの接続を確立することを特徴とする。
【００１５】
この構成によれば、隣接ノード異常検出手段により、少なくとも１ホップ先のノードのいずれかが離脱又は故障等して異常が発生した場合、その異常が発生した隣接ノードを検出し、リカバリー先ノード決定手段により、ネットワークを復旧させるために、隣接ノード異常検出手段で検出された隣接ノードに代わる新しい接続先のノードを決定し、コネクション確立手段により、リカバリー先ノード決定手段で決定された新しい接続先のノードとの接続を確立するので、あるノードに異常が発生し、ネットワークが中断した場合、ノード間の情報によりその異常が発生したノードを介さずに新しいノードと情報を送受可能になり、隣接ノードまでのネットワーク遅延を極力抑制することができ、ネットワークを速やかに回復させることができ、かつ通信品質を保持することができるという効果が得られる。
【００１６】
請求項６に記載のネットワークリカバリー方法は、
ネットワークに接続され互いに情報を送受可能なノードの少なくとも１ホップ先のノードのいずれかが離脱又は故障等して異常が発生した場合、前記ネットワークを復旧させるネットワークリカバリー方法であって、
当該異常が発生した隣接ノードを検出する隣接ノード異常検出ステップと、
前記隣接ノード異常検出手段で検出された隣接ノードに代わる新しい接続先のノードを決定するリカバリー先ノード決定ステップと、
前記少なくとも１ホップ先のノードが持っている隣接ノード情報を取得する隣接ノード情報取得ステップと、
前記隣接ノード情報を所定の場所に格納する隣接ノード情報記憶ステップと、
を含み、前記リカバリー先ノード決定ステップにおいて、前記隣接ノード異常検出ステップで検出された隣接ノードについての前記隣接ノード情報を参照して、前記新しい接続先のノードを決定し、当該新しい接続先のノードとの接続を確立することを特徴とする。
【００１７】
この構成によれば、隣接ノード異常検出ステップにおいて、少なくとも１ホップ先のノードのいずれかが離脱又は故障等して異常が発生した場合、その異常が発生した隣接ノードを検出し、リカバリー先ノード決定ステップにおいて、ネットワークを復旧させるために、隣接ノード異常検出手段で検出された隣接ノードに代わる新しい接続先のノードを決定し、コネクション確立ステップにおいて、リカバリー先ノード決定ステップにおいて決定された新しい接続先のノードとの接続を確立するので、あるノードに異常が発生し、ネットワークが中断した場合、ノード間の情報によりその異常が発生したノードを介さずに新しいノードと情報を送受可能になり、隣接ノードまでのネットワーク遅延を極力抑制することができ、ネットワークを速やかに回復させることができ、かつ通信品質を保持することができるという効果が得られる。
【発明の効果】
【００１８】
以上説明したように、ノードにリカバリー機能を導入することによって、ノードの離脱や故障などによるネットワークの分断を回復し、ノード間の通信品質を向上させる効果が得られる。
例えば、Ｐ２Ｐ内の各ノードが自分の情報を２ホップ先の隣接ノードにブロードキャストし、隣接ノードはその情報をキャッシュする。隣接ノードの離脱や故障などが生じた場合、キャッシュした隣接ノード情報に基づいて、リカバリー先のノードを決定し、コネクションを接続し直すことによって、ネットワークの分断を速やかに回復することができる。
【発明を実施するための最良の形態】
【００１９】
以下、図面を参照して、本発明のノードの実施形態について詳細に説明する。
〔第１実施形態〕
図１は、本発明の第１実施形態に係るノードの構成の一例を示すブロック図である。
このノード１は、隣接ノード情報取得部２，隣接ノード情報記憶部３，隣接ノード異常検出部４，リカバリー先ノード決定部５，コネクション確立部６で構成される。
隣接ノード情報取得部２は、隣接するノードとの親子関係等を含むノード情報を取得する。
隣接ノード情報記憶部３は、隣接ノード情報取得部２で取得した隣接ノードのノード情報を所定の場所に格納する。
隣接ノード異常検出部４は、隣接ノードが離脱したり故障したりして異常が発生した場合、その離脱又は故障した隣接ノードを検出する。
【００２０】
リカバリー先ノード決定部５は、隣接ノード異常検出部４で検出した異常が発生した隣接ノード以外の隣接ノードについて、隣接ノード情報記憶部３に保持されている隣接ノード情報を元に、リカバリー先の隣接ノードを決定する。
コネクション確立部６は、リカバリー先ノード決定部５で決定された隣接ノードとのコネクションを確立する。
ノード１は、隣接ノード情報取得部２より、ホップ先の隣接ノードに関するノード情報を獲得し、それを隣接ノード情報記憶部３に記憶する。隣接ノード異常検出部４で隣接ノードの離脱，故障等の異常を検出すると、隣接ノード情報記憶部３に保持されている隣接ノード情報を元に、リカバリー先ノード決定部４でリカバリー先のノードを検出し、コネクション確立部５でノード１とリカバリー先のノードとのコネクションを確立する。
【００２１】
図２は、ノードがリカバリーを行う手順を示すフローチャートである。
まず、ノード１の隣接ノード異常検出部４が、隣接ノードの離脱，故障等の異常を検出する（ステップＳ１）。
次に、リカバリー先ノード決定部５が、隣接ノード異常検出部４が検出した離脱又は故障した隣接ノードと、隣接ノード情報記憶部３が持っている隣接ノード情報とを参照して、リカバリー先のノードを決定する（ステップＳ２）。
そして、リカバリー先ノード決定部５からコネクション確立部６にリカバリー先のノードが通知され、ノード１からそのノードに対してコネクションを確立する（ステップＳ３）。
このように、ノード１にリカバリー機能を導入することにより、ノードの離脱，故障等の異常によって分断されたネットワークを回復し、ノード間の通信品質の向上を図ることができる。
【００２２】
なお、図２のフローチャートに示す処理を実行するにあたっては、いずれも、ＲＯＭに予め格納されている制御プログラムを実行するものであるが、これに限らず、これらの手順を示したプログラムが記録された記憶媒体から、そのプログラムをＲＡＭに組み込んで実行するようにしても良い。あるいは、そのプログラムをネットワークから取得しても良い。
ここで、記憶媒体とは、ＲＡＭ、ＲＯＭ等の半導体記憶媒体、ＦＤ、ＨＤ等の磁気記憶型記憶媒体、ＣＤ、ＣＤＶ、ＬＤ、ＤＶＤ等の光学的読取方式記憶媒体、ＭＯ等の磁気記憶型／光学的読取方式記憶媒体であって、電子的、磁気的、光学的等の読み取り方法のいかんにかかわらず、コンピュータで読み取り可能な記憶媒体であれば、あらゆる記憶媒体を含むものである。
【００２３】
図３は、ノードが１ホップ先の隣接ノードに対してブロードキャストする自己のノード情報を示す図である。
ここで、自己のノードをノードＸとし、ノードＸがブロードキャストするノード情報は、ノードＩＤ（Ｎｏｄｅ  ＩＤ）１１、ノードアドレス（Ｎｏｄｅ  Ａｄｄｒｅｓｓ）１２、隣接ノードＩＤ（Ｎｅｉｇｈｂｏｒ  ＩＤ）１３、及び隣接ノードとの間の親子関係（Ｒｅｌａｔｉｏｎ）１４である。
この例では、ノードＩＤ１１は「Ｘ」、ノードアドレス１２は「ｘｘｘｘ」、隣接ノードＩＤは「Ａ」，「Ｂ」，「Ｃ」、隣接ノードとの親子関係は、隣接ノードＡはノードＸに対して「親（Ｐａｒｅｎｔ）」、隣接ノードＢはノードＸに対して「子（Ｃｈｉｌｄ）」、隣接ノードＣはノードＸに対して「子（Ｃｈｉｌｄ）」である。これらが、ノードＸが１ホップ先の隣接ノードＡ，Ｂ，Ｃにブロードキャストする自己のノード情報を示す。
【００２４】
図４は、図３で示したノードＸの１ホップ先の隣接ノードとの関係を模式的に示す概略図である。
この例では、ノードＸを中心に配置し、ノードＸの周囲には、隣接するノードＡ，Ｂ，Ｃが配置されている。隣接ノードＢはノードＸに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｂで示すように隣接ノードＢからノードＸの方向へ、隣接ノードＣはノードＸに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｃで示すように隣接ノードＣからノードＸの方向へ、隣接ノードＡはノードＸに対して「親（Ｐａｒｅｎｔ）」であるので、図の矢印ａで示すようにノードＸから隣接ノードＡの方向へ情報が移動する。
【００２５】
図５は、各ノードが自己のノード情報を交換することによって得られた２ホップ先の隣接ノードの情報を示す図である。この図は、図３で示したノード情報を１ホップ先の隣接ノードの情報と、１ホップ先の隣接ノードに送った後の次のホップ先の隣接ノードの情報とを示している。
この例では、隣接ノードＡに隣接するノードをＡ１，Ａ２、隣接ノードＢに隣接するノードをＢ１，Ｂ２，Ｂ３、隣接ノードＣに隣接するノードをＣ１，Ｃ２としている。また、ブロードキャストするノード情報は、図１と同様に、ノードＩＤ２１、ノードアドレス２２、隣接ノードＩＤ２３、及び隣接ノードとの間の親子関係２４である。
【００２６】
まず最上段において、ノードＩＤ「Ｘ」の場合は、図１で説明したように、ノードアドレス「ｘｘｘｘ」、隣接ノードＩＤ「Ａ」，「Ｂ」，「Ｃ」、隣接ノードとの親子関係は、隣接ノードＡはノードＸに対して「親（Ｐａｒｅｎｔ）」、隣接ノードＢはノードＸに対して「子（Ｃｈｉｌｄ）」、隣接ノードＣはノードＸに対して「子（Ｃｈｉｌｄ）」である。
【００２７】
次に、第２段において、ノードＩＤ「Ａ」の場合は、ノードアドレス「ｘｘｘｘ」、隣接ノードＩＤは「Ａ１」，「Ｂ２」，「Ｘ」であり、隣接ノードとの親子関係は、隣接ノードＡ１は隣接ノードＡに対して「子（Ｃｈｉｌｄ）」、隣接ノードＡ２は隣接ノードＡに対して「子（Ｃｈｉｌｄ）」、ノードＸは隣接ノードＡに対して「子（Ｃｈｉｌｄ）」である。
第３段，第４段のノードＩＤ「A１」，「Ａ２」の場合は、３ホップ先の隣接ノードが様々であるので省略する。
【００２８】
次に、第５段において、ノードＩＤ「Ｂ」の場合は、ノードアドレス「ｘｘｘｘ」、隣接ノードＩＤは「Ｘ」，「Ｂ１」，「Ｂ２」，「Ｂ３」であり、隣接ノードとの親子関係は、ノードＸは隣接ノードＢに対して「親（Ｐａｒｅｎｔ）」、隣接ノードＢ１は隣接ノードＢに対して「子（Ｃｈｉｌｄ）」、隣接ノードＢ２は隣接ノードＢに対して「子（Ｃｈｉｌｄ）」、隣接ノードＢ３は隣接ノードＢに対して「子（Ｃｈｉｌｄ）」である。
第６段，第７段，第８段のノードＩＤ「Ｂ１」，「Ｂ２」，「Ｂ３」の場合は、３ホップ先の隣接ノードが様々であるので省略する。
【００２９】
次に、第９段において、ノードＩＤ「Ｃ」の場合は、ノードアドレス「ｘｘｘｘ」、隣接ノードＩＤは「Ｘ」，「Ｃ１」，「Ｃ２」であり、隣接ノードとの親子関係は、隣接ノードＸはノードＣに対して「親（Ｐａｒｅｎｔ）」、隣接ノードＣ１はノードＣに対して「子（Ｃｈｉｌｄ）」、隣接ノードＣ２はノードＣに対して「子（Ｃｈｉｌｄ）」である。
第１０段，第１１段のノードＩＤ「C１」，「Ｃ２」の場合は、３ホップ先の隣接ノードが様々であるので省略する。
【００３０】
図６は、図５で示した２ホップ先の隣接ノードとの関係を模式的に示す概略図である。
この例では、ノードＸを中心に配置し、ノードＸの周囲には、隣接するノードＡ，Ｂ，Ｃが配置され、隣接ノードＡに隣接するノードとして、Ａ１，Ａ２、隣接ノードＢに隣接するノードとして、Ｂ１，Ｂ２，Ｂ３、隣接ノードCに隣接するノードとして、C１，C２が配置されている。隣接ノードＢはノードＸに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｂで示すように隣接ノードＢからノードＸの方向へ、隣接ノードＣはノードＸに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｃで示すように隣接ノードＣからノードＸの方向へ、隣接ノードＡはノードＸに対して「親（Ｐａｒｅｎｔ）」であるので図の矢印ａで示すように、ノードＸから隣接ノードＡの方向へ情報が移動する。
【００３１】
また、隣接ノードＡ１は隣接ノードＡに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ａ１で示すように、隣接ノードＡ１から隣接ノードＡへ、隣接ノードＡ２は隣接ノードＡに対して子（Ｃｈｉｌｄ）」であるので、図の矢印ａ２で示すように、隣接ノードＡ２から隣接ノードＡへ情報が移動する。
また、隣接ノードＢ１は隣接ノードＢに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｂ１で示すように隣接ノードＢ１から隣接ノードＢへ、隣接ノードＢ２は隣接ノードＢに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｂ２で示すように隣接ノードＢ２から隣接ノードＢへ、隣接ノードＢ３はノードＢに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｂ３で示すように隣接ノードＢ３から隣接ノードＢへ、ノードＸは隣接ノードＢに対して「親（Ｐａｒｅｎｔ）」であるので、図の矢印ｂで示すように隣接ノードＢからノードＸの方向へ情報が移動する。
【００３２】
また、隣接ノードＣ１は隣接ノードＣに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｃ１で示すように隣接ノードＣ１から隣接ノードＣへ、隣接ノードＣ２は隣接ノードＣに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｃ２で示すように隣接ノードＣ２から隣接ノードＣへ情報が移動する。
以上のようにして、ノード間の情報を交換することによって、２ホップ先のノードのノード情報を入手することになる。
なお、ノードＸは、２ホップ先の隣接ノードＡ１，Ａ２，Ｂ１，Ｂ２，Ｂ３，Ｃ１，Ｃ２のノードＩＤ、ノードアドレス、及び隣接ノードとの間の親子関係をキャッシュメモリに記憶しておく。
【００３３】
図７は、ノード離脱前のノード間の関係を示す図である。
ブロードキャストするノード情報は、ノードＩＤ３１，ノードアドレス３２，隣接ノードＩＤ３３，隣接ノードとの間の親子関係３４である。
この例では、ノードＩＤは「Ｂ」，「Ａ」，「Ｘ」，「Ｃ」であり、ノードアドレス１２は全て「ｘｘｘ」、ノードＩＤ「Ｂ」の隣接ノードＩＤは「Ｘ」、ノードＩＤ「Ａ」の隣接ノードＩＤは「Ｘ」、ノードＩＤ「Ｘ」の隣接ノードのＩＤは「Ａ」、ノードＩＤ「Ｃ」の隣接ノードのＩＤは「Ｘ」であり、隣接ノードとの親子関係は、隣接ノードＩＤ「Ｘ」はノードＩＤ「Ｂ」に対して「親（Ｐａｒｅｎｔ）」、隣接ノードＩＤ「Ｘ」はノードＩＤ「Ａ」に対して「子（Ｃｈｉｌｄ）」、隣接ノードＩＤ「Ａ」はノードＩＤ「Ｘ」に対して「親（Ｐａｒｅｎｔ）」、隣接ノードＩＤ「Ｘ」はノードＩＤ「Ｃ」に対して「親（Ｐａｒｅｎｔ）」である。
【００３４】
図８は、本発明のノードの実施形態において離脱ノードが発生した場合のリカバリー方法を示す模式図である。（ａ）は離脱前、（ｂ）は離脱後の状態を示す。
図８（ａ）に示すように、離脱するノード（Ｄｅｐａｒｔｕｒｅ  Ｎｏｄｅ）はノードＸであり、離脱前は、ノードＸを中心にしてノードＸの周囲に隣接ノードＡ，Ｂ，Ｃが配置されている。隣接ノードＢはノードＸに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｂで示すように隣接ノードＢからノードＸの方向へ、隣接ノードＣはノードＸに対して「子（Ｃｈｉｌｄ）」であるので、図の矢印ｃで示すように、隣接ノードＣからノードＸの方向へ、ノードＸは隣接ノードＡに対しては「子（Ｃｈｉｌｄ）」であるので、図の矢印ａで示すように、ノードＸから隣接ノードＡの方向へ、情報が移動するように構成されている。
【００３５】
ここで、図８（ｂ）に示すように、ノードＸが離脱すると、離脱ノードの子ノードが自分が保持した２ホップ先の隣接ノード情報を元に、離脱ノードの親ノードにコネクションを張り直し、分断されたネットワークを回復する。
すなわち、ノードＸが離脱すると、ノードＸの子ノードB，Cは、ノード情報獲得によって獲得したノードの親ノードのノードアドレスを用いて、矢印ｂａで示すようにノードＢからノードＡに、矢印ｃａで示すようにノードＣからノードＡに情報を移動させ、ノードＢ及びノードＣとノードＡとの間のコネクションを確立する。
【００３６】
次に、コネクションを確立する方法について説明する。
ネットワークトポロジーを生成する際、新規ノードは、バーチャルコネクションを確立している隣接ノードまでの物理層のネットワーク状況を考慮している平均メトリックス値を比較し、平均メトリックス値の最小のノードにコネクションを張り、ネットワークトポロジーを生成することによって、各隣接ノードまでのネットワーク遅延を平均的に最小限に抑制することができる。すなわち、（１）物理層ネットワーク状況を反映するメトリックス値を持つネットワーク構成管理装置と、（２）隣接ノードまでの平均メトリックスを計算する機能を持つネットワーク構成管理装置と、（３）隣接ノードの中から平均メトリックス値の最小のコネクションを「張る」ことを特徴とするネットワークトポロジー生成装置とによって達成できる。
【００３７】
これにより、新規ノードは、ネットワーク中の各ノードまでのネットワーク遅延が平均的に小さい場所に位置し、データ転送の効率を向上させることができる。従って、あるノードに異常が発生し、ネットワークが中断した場合、ノード間の情報によりその異常が発生したノードを介さずに新しいノードと情報を送受可能になり、隣接ノードまでのネットワーク遅延を極力抑制することができ、ネットワークを速やかに回復させることができ、かつ通信品質を保持することができる。
【００３８】
〔第２実施形態〕
図９及び図１０は、本発明の第２実施形態に係るノード間の関係を示す図である。
図９は、ノード離脱前のノード間の関係（離脱ノードがルートノードである場合）を示す図である。この図は、ノードＡＢＣＸ間の関係を示す図である。
ノードＩＤ４１は「Ｂ」「Ａ」「Ｘ」「Ｃ」、ノードアドレス４２は全て「ｘｘｘ」、ノードＩＤ「Ｂ」の隣接ノードＩＤは「Ｘ」、ノードＩＤ「Ａ」の隣接ノードＩＤは「Ｘ」、ノードＩＤ「Ｘ」の隣接ノードＩＤは「Ａ，Ｂ，Ｃ」、ノードＩＤ「Ｃ」の隣接ノードＩＤは「Ｘ」である。隣接ノードＩＤ「Ｘ」はノードＩＤ「Ｂ」に対して「親」の関係にあり、ノードＩＤ「Ａ」に対しても「親」の関係にあり、ノードＩＤ「Ｃ」に対しても「親」の関係にある。また、隣接ノードＩＤ「Ａ，Ｂ，Ｃ」は、ノードＩＤ「Ｘ」に対して「子」の関係にある。
【００３９】
図１０は、本発明のノードの第２実施形態において離脱ノードが発生した場合（離脱ノードがルートノードである場合）のリカバリー方法を示す模式図である。（ａ）は離脱前、（ｂ）は離脱後の状態を示す。
図１０（ａ）に示すように、離脱するノード（Ｄｅｐａｒｔｕｒｅ  Ｎｏｄｅ）はノードＸであり、離脱前は、ノードＸを中心にしてノードＸの周囲に隣接ノードＡ，Ｂ，Ｃが配置されている。このように、離脱ノードＸがルートノードである場合、その離脱ノードＸの子ノードＡ，Ｂ，Ｃの間で処理応力に応じて新しい親ノードを決定し、お互いにコネクションを設立することによって、ネットワークの分断をリカバリーすることができる。この例では、ルートノードをノード「Ｘ」とし、ノード「Ｘ」は隣接ノードに「Ａ」，「Ｂ」，「Ｃ」に対して「親」であるので、隣接ノード「Ａ」，「Ｂ」，「Ｃ」からノードＸへ情報が集中している。
【００４０】
また、図１０（ｂ）に示すように、ノード「Ｘ」が離脱すると、子ノード「Ａ」，「Ｂ」，「Ｃ」の間で処理能力の最も大きいノード「Ｂ」を親ノードに決定し、ノード「Ｂ」に対してコネクションを確立する。すなわち、ノード「Ａ」からはノード「Ｂ」に向かって矢印ａｂで示すような経路を、ノード「Ｃ」からノード「Ｂ」に向かって矢印ｃｂで示すような経路ができる。
これにより、あるルートノードに異常が発生し、ネットワークが中断した場合にも、ノード間の情報によりその異常が発生したノードを介さずに新しいノードと情報を送受可能になり、隣接ノードまでのネットワーク遅延を極力抑制することができ、ネットワークを速やかに回復させることができる。
【００４１】
〔第３実施形態〕
図１１及び図１２は、本発明の第３実施形態に係るノード間の関係を示す図である。
図１１は、ノード離脱前のノード間の関係（離脱ノードが複数の親ノードが存在する場合）を示す図である。
離脱ノードＸが複数の親ノードＢ，C，A１，A２を持つ場合、そのノードの子ノードは保持している２ホップ先のノード情報を参照し、離脱ノードＸの全ての親ノードB，C，A１，A２に対してコネクションを設立し、ネットワークの分断およびリカバリーを行う。
【００４２】
ノードＩＤ５１は「Ｂ」，「Ａ１，Ａ２」，「Ｘ」，「Ｃ」、ノードアドレス５２は全て「ｘｘｘ」、隣接ノードＩＤ５３は、ノードＩＤ「Ｂ」の隣接ノードＩＤは「Ｘ」、ノードＩＤ「Ａ１，Ａ２」の隣接ノードＩＤは「Ｘ」、ノードＩＤ「Ｘ」の隣接ノードＩＤは「Ａ１，Ａ２」、ノードＩＤ「Ｃ」の隣接ノードＩＤは「Ｘ」である。親子関係５４は、隣接ノードＩＤ「Ｘ」はノードＩＤ「Ｂ」に対して「親」の関係にあり、ノードＩＤ「Ａ１，Ａ２」に対しても「親」の関係にあり、ノードＩＤ「Ｃ」に対しても「親」の関係にある。また、隣接ノードＩＤ「Ａ１，Ａ２」は、ノードＩＤ「Ｃ」に対して「親」の関係にある。
【００４３】
図１２は、本発明のノードの第３実施形態において離脱ノードが発生した場合（離脱ノードに複数の親ノードが存在する場合）のリカバリー方法を示す模式図である。（ａ）は離脱前、（ｂ）は離脱後の状態を示す。
図１２（ａ）に示すように、ノード「Ｘ」は、隣接ノード「Ａ１」，「Ａ２」に対しては親ノードで、矢印ｂ，ｃで示すように情報が移動するが、隣接ノード「Ｂ」，「Ｃ」に対しては子ノードであるため、矢印ｘａ１，ｘａ２で示すように情報が移動する。
【００４４】
ここで、図１２（ｂ）に示すように、ノードＸが離脱すると、子ノード「Ｂ」，「C」は、その親ノード「Ａ１」，「Ａ２」に対してコネクションを確立することができる。すなわち、子ノード「Ｂ」から親ノード「Ａ１」，「Ａ２」に対して矢印ｂａ１，ｂａ２で示すように情報が移動し、子ノード「Ｃ」から親ノード「Ａ１」，「Ａ２」に対して矢印ｃａ１，ｃａ２で示すように情報が移動する。
これにより、離脱ノードに複数の親ノードが存在する場合にも、あるノードに異常が発生し、ネットワークが中断した場合、ノード間の情報によりその異常が発生したノードを介さずに新しいノードと情報を送受可能になり、隣接ノードまでのネットワーク遅延を極力抑制することができ、ネットワークを速やかに回復させることができる。
【００４５】
以上、本発明のノードの実施形態について説明したが、この実施形態に限定されず、本発明の趣旨を逸脱しない範囲で種々の変更が可能である。
例えば、上述の実施形態では、隣接ノード情報記憶部３は、２ホップ先のノード情報を記憶するとしたが、これに限定されず、３ホップ先、４ホップ先等の情報を記憶しておくこともできる。
また、上述の実施形態では、ネットワークに新規参入するノードが、バーチャルコネクションを確立している隣接ノードまでの平均メトリックスを比較し、平均メトリックスの最小のノードにコネクションを張り、ネットワークトポロジーを生成する方法について説明したが、平均メトリックスの最小のノードに限定されず、次に小さいノードにコネクションを張ることができる。
【００４６】
また、上述の実施形態では、ノード１は、隣接ノード情報記憶部３を備えるように構成したが、これに限定されず、他の場所に隣接ノード情報を記憶させ、必要に応じてノード１が取り出すように構成することもできる。
また、上述の実施形態では、隣接ノード異常検出部４は、隣接ノードの離脱，故障等の異常を検出するとしたが、これ限定されず、経路の不良，切断等の異常も検出するように構成することができる。
【図面の簡単な説明】
【００４７】
【図１】本発明の第１実施形態に係るノードの内部構成を示すブロック図である。
【図２】本発明の第１実施形態に係るノードがリカバリーする手順を示すフローチャートである。
【図３】ノードがブロードキャストする１ホップ先のノード情報を示す図である。
【図４】ノードの１ホップ先の隣接関係を模式的に示す概略図である。
【図５】ノードがブロードキャストする２ホップ先のノード情報を示す図である。
【図６】ノードの２ホップ先の隣接関係を模式的に示す概略図である。
【図７】離脱前のノード間の関係を示す図である。
【図８】離脱ノードが発生した場合のリカバリー方法を模式的に示す概略図である。（ａ）は離脱前、（ｂ）は離脱後の状態を示す。
【図９】本発明の第２実施形態に係る離脱ノードがルートノードである場合の離脱前のノード間の関係を示す図である。
【図１０】離脱ノードがルートノードである場合のリカバリー方法を模式的に示す概略図である。（ａ）は離脱前、（ｂ）は離脱後の状態を示す。
【図１１】本発明の第３実施形態に係る離脱ノードが複数存在する場合の離脱前のノード間の関係を示す図である。
【図１２】離脱ノードが複数存在する場合のリカバリー方法を模式的に示す概略図である。（ａ）は離脱前、（ｂ）離脱後の状態を示す。
【符号の説明】
【００４８】
１…ノード、  ２…隣接ノード情報取得部、  ３…隣接ノード情報記憶部、  ４…隣接ノード異常検出部、  ５…リカバリー先ノード決定部、  ６…コネクション確立部、  １１，２１，３１，４１，５１…ノードＩＤ、  １２，２２，３２，４２，５２…ノードアドレス、  １３，２３，３３，４３，５３…隣接ノードＩＤ、  １４，２４，３４，４４，５４…親子関係
【図１】
0004824914.tif 000002
【図２】
0004824914.tif 000003
【図３】
0004824914.tif 000004
【図４】
0004824914.tif 000005
【図５】
0004824914.tif 000006
【図６】
0004824914.tif 000007
【図７】
0004824914.tif 000008
【図８】
0004824914.tif 000009
【図９】
0004824914.tif 000010
【図１０】
0004824914.tif 000011
【図１１】
0004824914.tif 000012
【図１２】
0004824914.tif 000013