(57)【要約】  局所情報を必要な範囲に高速に伝播させる方法を提供する。ネットワーク内で発生する局所情報を伝播させる部分ネットワークが所定のサイズとなるように当該部分ネットワークを表わした隣接行列の最大固有値を最大化し、かつ、前記部分ネットワークの規格化ラプラシアン行列の第２最小固有値を最大化するような部分ネットワークの構成を算出するステップと、前記部分ネットワーク内のすべてのノードに対し、前記算出した構成情報を通知するステップと、局所情報が発生した場合、前記構成情報を用いて、前記部分ネットワークに前記局所情報を伝播させるステップとを含む。
2012128352.tif 000002
【特許請求の範囲】
【請求項１】
ネットワーク内で発生する局所情報を伝播させる部分ネットワークが所定のサイズとなるように当該部分ネットワークを表わした隣接行列の最大固有値を最大化し、かつ、前記部分ネットワークの規格化ラプラシアン行列の第２最小固有値を最大化するような部分ネットワークの構成を算出するステップと、
前記部分ネットワーク内のすべてのノードに対し、前記算出した構成情報を通知するステップと、
局所情報が発生した場合、前記構成情報を用いて、前記部分ネットワークに前記局所情報を伝播させるステップとを含む、局所情報の伝播方法。
【請求項２】
前記局所情報の伝播に、前記局所情報の伝播用に定めた専用プロトコルを用いる請求項１の局所情報の伝播方法。
【請求項３】
前記部分ネットワークのサイズ上限は、前記局所情報を伝播させる時間の最大許容値を、前記局所情報の伝播用に定めたプロトコルによって任意の２つの通信ノード間で通信を行うために必要な時間で割ることによって求められる請求項１または２の局所情報の伝播方法。
【請求項４】
前記局所情報は、事象の程度、事象が発生したノードの識別情報、発生時刻を含み、
さらに、前記ネットワークのノードが前記局所情報に応じたネットワークの制御を行うステップを含む請求項１から３いずれか一の局所情報の伝播方法。
【請求項５】
局所情報は、輻輳の程度、輻輳が発生したノードの識別情報、発生時刻を含み、
さらに、前記ネットワークのノードが前記局所情報に応じた経路制御を行うステップを含む請求項１から４いずれか一の局所情報の伝播方法。
【請求項６】
ネットワーク内で発生する局所情報を伝播させる部分ネットワークに代えて、システム内で発生する局所情報を伝播させる部分システムの構成を算出し、
前記部分システム内のすべてのノードに対し、前記算出した構成情報を通知し、
局所情報が発生した場合、前記構成情報を用いて、前記部分システムに前記局所情報を伝播させる請求項１から５いずれか一の局所情報の伝播方法。
【請求項７】
ネットワーク内で発生する局所情報を伝播させる部分ネットワークとして、当該ネットワークを表わした隣接行列の最大固有値を最大化し、かつ、前記ネットワークの規格化ラプラシアン行列の第２最小固有値を最大化するような部分ネットワークの構成を算出する手段と、
前記部分ネットワーク内のすべてのノードに対し、前記算出した構成情報を通知する手段と、を備えた計算ノードを含み、
局所情報が発生した場合、前記部分ネットワークに属するノードが、前記局所情報の伝播用に定めたプロトコルを用いて、前記局所情報を伝播するネットワーク。
【請求項８】
ネットワーク内で発生する局所情報を伝播させる部分ネットワークとして、当該ネットワークを表わした隣接行列の最大固有値を最大化し、かつ、前記ネットワークの規格化ラプラシアン行列の第２最小固有値を最大化するような部分ネットワークの構成を算出する手段と、
前記部分ネットワーク内のすべてのノードに対し、前記算出した構成情報を通知する手段と、を備えた計算ノード。
【請求項９】
局所情報が発生した場合、請求項８の計算ノードから通信された構成情報を用いて、予め定めたプロトコルを用いて前記局所情報を伝播するノード。
【請求項１０】
ネットワーク内で発生する局所情報を伝播させる部分ネットワークが所定のサイズとなるように当該部分ネットワークを表わした隣接行列の最大固有値を最大化し、かつ、前記部分ネットワークの規格化ラプラシアン行列の第２最小固有値を最大化するような部分ネットワークの構成を算出する処理と、
前記部分ネットワーク内のすべてのノードに対し、前記算出した構成情報を通知する処理と、を前記ネットワークに接続された計算ノードに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１１−０６５７７６号（２０１１年  ３月２４日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。【０００２】
本発明は、局所情報の伝播方法、ネットワーク、計算ノード、ノードおよびプログラムに関し、特に、ネットワークやシステムに生じた故障や障害等の局所的な情報を伝播させる局所情報の伝播方法、ネットワーク、計算ノード、ノードおよびプログラムに関する。
【背景技術】
【０００３】
ネットワークやシステムを構成する要素が、故障や障害を起こした場合、該故障・障害情報を収集し、原因箇所を特定し、制御を行うことが行われている。この場合、最も負荷が大きく時間を要するのは、情報収集と原因箇所特定である。つまり。この２つの過程を高速に行うことがネットワークやシステムを制御する上で重要になる。【０００４】
上記情報収集と原因箇所特定とを高速に行うためには、故障や障害の発生時に、情報収集や原因箇所特定等の処理を担う制御領域または制御ノードに、これら故障や障害が発生したという情報を高速に伝播させることが必要となる。【０００５】
本発明の先行技術の１つとして非特許文献１がある。この方法は、一般にインターネットで用いられている通信プロトコルであるＴＣＰ／ＩＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）を用いて、ネットワーク内の故障情報をネットワーク内の各ルータに対して、事前に決定されている経路に従って順に故障情報を伝播させることで、各ルータに迂回路を再計算させるものである。その他の先行技術としては、非特許文献２がある。この方式には様々なバリエーションがあるが、その目的は、非特許文献１よりも高速に、故障・障害箇所を通らない迂回路を決定することにある。【０００６】
非特許文献３〜８は、その他本発明の背景技術となる文献である。本発明との関連については、後に詳述する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】“Ｔｈｅ  Ａｄｄｉｔｉｏｎ  ｏｆ  Ｅｘｐｌｉｃｉｔ  Ｃｏｎｇｅｓｔｉｏｎ  Ｎｏｔｉｆｉｃａｔｉｏｎ  （ＥＣＮ）  ｔｏ  ＩＰ”、ＲＦＣ３１６８
【非特許文献２】Ｍｉｎａｓ  Ｇｊｏｋａほか２名、“Ｅｖａｌｕａｔｉｏｎ  ｏｆ  ＩＰ  Ｆａｓｔ  Ｒｅｒｏｕｔｅ  Ｐｒｏｐｏｓａｌｓ”、［online］、［平成23(2011)年3月1日検索］、インターネット〈URL：http://www.Minasgjoka.com/papers/ipfrr06.pdf）
【非特許文献３】生天目  章、“群知能とネットワーク型制御”、防衛大学情報工学科、［online］、［平成23(2011)年3月1日検索］、インターネット〈URL：http://www.nda.ac.jp/~nama/Top/InvitedTalk/10-11-30.pdf〉
【非特許文献４】Ｌｕｃａ  Ｄｏｎｅｔｔｉほか２名、“Ｏｐｔｉｍａｌ  ｎｅｔｗｏｒｋ  ｔｏｐｏｌｏｇｉｅｓ：Ｅｘｐａｎｄｅｒｓ，Ｃａｇｅｓ，Ｒａｍａｎｕｊａｎ  ｇｒａｐｈｓ，Ｅｎｔａｎｇｌｅｄ  ｎｅｔｗｏｒｋｓ  ａｎｄ  ａｌｌ  ｔｈａｔ．”、Ｊｏｕｒｎａｌ  ｏｆ  Ｓｔａｔｉｓｔｉｃａｌ  Ｍｅｃｈａｎｉｃｓ：  Ｔｈｅｏｒｙ  ａｎｄ  Ｅｘｐｅｒｉｍｅｎｔ、Ｖｏｌｕｍｅ  ２００６、Ａｕｇｕｓｔ  ２００６．
【非特許文献５】Ｌｅｓｔｅｒ  Ｉｎｇｂｅｒ、“Ｓｉｍｕｌａｔｅｄ  ａｎｎｅａｌｉｎｇ：Ｐｒａｃｔｉｃｅ  ｖｅｒｓｕｓ  ｔｈｅｏｒｙ”、［online］、［平成23(2011)年3月1日検索］、インターネット〈URL：http://www.ingber.com/asa93_sapvt.pdf〉
【非特許文献６】Ｓａｕｍｉｔｒａ  Ｍ．  Ｄａｓほか２名、“Ｐｅｒｆｏｒｍａｎｃｅ  Ｃｏｍｐａｒｉｓｏｎ  ｏｆ  Ｓｃａｌａｂｌｅ  Ｌｏｃａｔｉｏｎ  Ｓｅｒｖｉｃｅｓ  ｆｏｒ  Ｇｅｏｇｒａｐｈｉｃ  Ａｄ  Ｈｏｃ  Ｒｏｕｔｉｎｇ”、ＩＥＥＥ  ＩＮＦＯＣＯＭ２００５、ｐｐ．１２２８−１２３９
【非特許文献７】ＩＢＭ社、“ＴＣＰ／ＩＰチュートリアルおよび技術解説書”、［online］、［平成23(2011)年3月1日検索］、インターネット〈URL：http://www-06.ibm.com/jp/support/redbooks/TCP_IP/GG88400500.pdf〉
【非特許文献８】「スパニング木」、［online］、［平成23(2011)年3月1日検索］、インターネット〈URL：http://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%91%E3%83%8B%E3%83%B3%E3%82%B0%E6%9C%A8〉
【発明の概要】
【発明が解決しようとする課題】
【０００８】
以下の分析は、本発明によって与えられたものである。【０００９】
上記非特許文献１に記載の技術では、故障・障害情報の伝播領域の制限は無いが、通常の経路制御プロトコルを用いてネットワーク全体に故障・障害情報を通知させ、これら情報が到着したルータから順に経路再計算を行うため、情報の到着時間が遅く、そのため、制御にも時間がかかるという問題点がある。【００１０】
非特許文献２に記載の技術も同様に、故障・障害情報の伝播領域の制限は無く、通常の経路制御プロトコルで構成された経路に従ってネットワーク全体に故障・障害情報を通知させ、該情報が到着したルータから順に経路再計算を行うものであるため、情報の到着時間が遅く、そのため制御にも時間がかかるという問題点がある。【００１１】
本発明は、上記した事情に鑑みてなされたものであって、その目的とするところは、ネットワークにおける局所的な情報（以下、「局所情報」という。）の伝播領域を出来るだけ広範囲かつ必要な部分に制限し、かつ、該情報を高速に伝播させる方法を提供することにある。
【課題を解決するための手段】
【００１２】
本発明の第１の視点によれば、ネットワーク内で発生する局所情報を伝播させる部分ネットワークが所定のサイズとなるように当該部分ネットワークを表わした隣接行列の最大固有値を最大化し、かつ、前記部分ネットワークの規格化ラプラシアン行列の第２最小固有値を最大化するような部分ネットワークの構成を算出するステップと、前記部分ネットワーク内のすべてのノードに対し、前記算出した構成情報を通知するステップと、局所情報が発生した場合、前記構成情報を用いて、前記部分ネットワークに前記局所情報を伝播させるステップとを含む、局所情報の伝播方法が提供される。本方法は、ネットワークに配置されて前記局所情報の伝播範囲等を決定する計算ノードという、特定の機械に結びつけられている。【００１３】
本発明の第２の視点によれば、ネットワーク内で発生する局所情報を伝播させる部分ネットワークとして、当該ネットワークを表わした隣接行列の最大固有値を最大化し、かつ、前記ネットワークの規格化ラプラシアン行列の第２最小固有値を最大化するような部分ネットワークの構成を算出する手段と、前記部分ネットワーク内のすべてのノードに対し、前記算出した構成情報を通知する手段と、を備えた計算ノードを含み、局所情報が発生した場合、前記部分ネットワークに属するノードが、前記局所情報の伝播用に定めたプロトコルを用いて、前記局所情報を伝播するネットワークが提供される。【００１４】
本発明の第３の視点によれば、ネットワーク内で発生する局所情報を伝播させる部分ネットワークとして、当該ネットワークを表わした隣接行列の最大固有値を最大化し、かつ、前記ネットワークの規格化ラプラシアン行列の第２最小固有値を最大化するような部分ネットワークの構成を算出する手段と、前記部分ネットワーク内のすべてのノードに対し、前記算出した構成情報を通知する手段と、を備えた計算ノードが提供される。【００１５】
本発明の第４の視点によれば、局所情報が発生した場合、上記した計算ノードから通信された構成情報を用いて、予め定めたプロトコルを用いて前記局所情報を伝播するノードが提供される。【００１６】
本発明の第５の視点によれば、ネットワーク内で発生する局所情報を伝播させる部分ネットワークが所定のサイズとなるように当該部分ネットワークを表わした隣接行列の最大固有値を最大化し、かつ、前記部分ネットワークの規格化ラプラシアン行列の第２最小固有値を最大化するような部分ネットワークの構成を算出する処理と、前記部分ネットワーク内のすべてのノードに対し、前記算出した構成情報を通知する処理と、を前記ネットワークに接続された計算ノードに実行させるプログラムが提供される。なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記録することができる。即ち、本発明は、コンピュータプログラム製品として具現することも可能である。
【発明の効果】
【００１７】
本発明によれば、局所情報を必要な範囲に高速に伝播させることが可能となる。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１の実施形態のネットワークの構成を示す図である。
【図２】本発明の第１の実施形態の計算サーバの構成を示す図である。
【図３】本発明の第１の実施形態の局所情報の伝播方法（準備段階）を説明するための流れ図である。
【図４】本発明の第１の実施形態の計算サーバにおける計算過程を説明するための図である。
【図５】本発明の第１の実施形態の計算サーバにおける計算過程を説明するための別の図である。
【図６】本発明の第１の実施形態の局所情報の伝播方法（伝播段階）を説明するための流れ図である。
【図７】本発明の第２の実施形態の局所情報の伝播方法（準備段階）を説明するための流れ図である。
【図８】本発明の第２の実施形態の局所情報の伝播方法（伝播段階）を説明するための流れ図である。
【図９】本発明の第３の実施形態の局所情報の伝播方法（準備段階）を説明するための流れ図である。
【図１０】本発明の第３の実施形態の局所情報の伝播方法（伝播段階）を説明するための流れ図である。
【図１１】本発明の第４の実施形態の局所情報の伝播方法（準備段階）を説明するための流れ図である。
【図１２】本発明の第４の実施形態の局所情報の伝播方法（伝播段階）を説明するための流れ図である。
【発明を実施するための形態】
【００１９】
はじめに、本発明の基礎となるネットワーク（以下、「ＮＷ」と記す。）の固有値に関する２つの数学的性質を述べる。
【００２０】
（性質１）ＮＷ内で発生する局所情報を可能な限り、広い領域に伝播させるためにはＮＷの隣接行列の最大固有値を大きくするようなＮＷを構成することが必要である（非特許文献３参照）。
【００２１】
（性質２）ＮＷ内で発生する局所情報を可能な限り高速に、広範囲に伝播させるためには次式［数１］で与えられる、ＮＷ内の任意の２ノードｓ，ｔ間のマルコフ連鎖に従うランダムウォークのｆｉｒｓｔ  ｐａｓｓａｇｅ  ｔｉｍｅ（非特許文献４  ５ページ最上の式）を最小にするようなＮＷ、つまりＮＷの規格化ラプラシアン行列の第２最小固有値を最大化するようなＮＷを構成することが必要である。
【００２２】
【数１】
2012128352.tif 000003
【００２３】
ここで、ＭはＮＷ内のリンクの総数、ｄ（ｓ）、ｄ（ｔ）は、それぞれノードｓ、ノードｔの次数である。また、０≦λ＿ｖ≦２はＮＷの規格化ラプラシアン行列の小さい方からｖ番目（ｖは２以上の自然数）の固有値、ｕ＿（ｌ，ｓ）は、ＮＷの規格化ラプラシアン行列の小さい方からｌ番目の固有値（ｌは２以上の自然数）に対する大きさが１の固有ベクトルの上からｓ行目の値である。
【００２４】
（性質３）上記（性質１）および（性質２）を満たすＮＷは、ＮＷ内の各ノードの次数、ｂｅｔｗｅｅｎｅｓｓ中心性、平均距離、最小ループサイズ、次数相関の分布において一様であるようなＮＷである。例えば、非特許文献４に記載のＥｎｔａｎｇｌｅｄ  ＮＷもその１つである。
【００２５】
以上の性質から、ＮＷ（あるいはシステム）内で発生する局所的な情報の伝播領域をできるだけ広範囲かつ必要な部分に制限し、かつ、該故障・障害情報を高速に伝播させるという互いに相反する２つの目的を実現するためには、ＮＷの規格化ラプラシアン行列の第２最小固有値を大きくし、かつＮＷの隣接行列の最大固有値を大きくするようなＮＷを構成すればよいということが導かれる。
【００２６】
例えば、ノードとリンクで構成されるＮＷにおいて局所的な事象が発生した場合、以下のような準備を行うことで、効率よく該局所情報を伝達することができる。ここでは、局所情報は、事象の程度、事象が発生したノードの識別情報、発生時刻などを含むものとする。また、ＮＷ内のノードは、この局所情報を受信した場合、ＮＷ管理者等によって予め規定された制御を行うＮＷ制御機能を備えているものとする。
【００２７】
（手順１）当該局所情報の通知用の通信プロトコルを準備しておく。この局所情報の伝達用の通信プロトコルは、既存の経路制御プロトコルより高速に通信可能な専用通信プロトコルであることが望ましい。
【００２８】
（手順２）局所情報を伝播させる仮の局所情報通知用のＮＷ範囲を決定する。また、このＮＷ範囲に属する通信ノードの中から固有値の計算用ノードを決定する。ここで決定する「仮の局所情報通知用のＮＷ範囲」は、当該ＮＷに属するすべての通信ノードが有するＮＷ制御機能が、該局所情報が到着した時間を同一時刻であると認識可能な範囲のことである。
【００２９】
（手順３）前記固有値の計算用ノードにおいて、仮の局所情報通知用のＮＷ範囲の隣接行列と規格化ラプラシアン行列を生成する。
【００３０】
（手順４）前記固有値の計算用ノードにおいて、仮の局所情報通知用のＮＷ範囲の隣接行列の最大固有値と、規格化ラプラシアン行列の第２最小固有値を求める。
【００３１】
（手順５）前記固有値の計算用ノードにおいて、任意の最適化アルゴリズムによって、該仮の局所情報通知用のＮＷ範囲の通信ノード数とリンク数とを適当に追加、削除しながら、（手順３）および（手順４）を繰り返すことで、前記隣接行列の最大固有値と、前記規格化ラプラシアン行列の第２最小固有値とをそれぞれ最大化するような、局所通知用のＮＷ範囲を決定する。
【００３２】
（手順６）（手順５）で決定されたＮＷ範囲に属するノードに対して、前記固有値の計算用ノードから、局所情報通知用のＮＷの構成情報を伝達する。なお、前記ＮＷの構成情報の伝達は、任意の通信プロトコルを用いることができる。もちろん、（手順１）で決めた通信プロトコルを用いることもできる。
【００３３】
（手順７）通信ＮＷ内の（手順６）で決定したＮＷ範囲以外の残りのＮＷについても（手順２）から（手順６）を行う。最終的には、ＮＷ全体がいくつかの局所情報の通知用のＮＷ範囲（部分ＮＷ）に分割されることになる。
【００３４】
（手順８）局所情報の通知用のＮＷ範囲において局所情報が発生した場合、当該障害が発生したノードを起点として、（手順１）で準備した通信プロトコルによって局所情報が伝達される。
【００３５】
（手順９）当該局所情報の通知用のＮＷ範囲に属するノードは、局所情報を受信すると、これを他の隣接ノードに伝達するとともに、当該受信した局所情報に対応するＮＷ制御を行う。
【００３６】
以上のように局所情報を必要な範囲に高速に伝達させることで、部分ＮＷを高速に制御することが可能になる。もちろん、部分ＮＷの各所に同時多発的に局所情報を伝達させるようにすれば、ＮＷ全体を大域的に制御することも可能となる。
【００３７】
また、（手順１）で準備する通信プロトコルとして、既存の経路制御プロトコルより高速に通信可能な専用通信プロトコルを用いた場合には、上記経路制御プロトコルによるＮＷとは独立した局所情報の伝達用ＮＷを構築することができ、さらに、ＮＷ専用の通信プロトコルを用いることで高速なＮＷ制御を行うことが可能となる。
【００３８】
［第１の実施形態］
続いて、本発明の第１の実施形態について図面を参照して詳細に説明する。図１は、本発明の第１の実施形態のネットワークの構成を示す図である。図１を参照すると、複数の局所情報の通知用のＮＷ（Ｗ１＿ｘ〜Ｗ９＿ｘ）によって構成された通信ネットワーク（以下、「通信ＮＷ１」と記す。）が示されている。
【００３９】
上記局所情報の通知用のＮＷ（Ｗ１＿ｘ〜Ｗ９＿ｘ）は、それぞれ通信ノード（図１のＣＮ参照）によって構成されている。また、通信ＮＷ１の随所に、局所情報の通知用のＮＷ範囲を計算する計算サーバ（図１のＣＳ参照）が配置されている。なお、通信ノードＣＮのうち、いくつかに計算サーバ（図１のＣＳ参照）としての機能を持たせてもよい。
【００４０】
図２は、本発明の第１の実施形態の計算サーバＣＳの構成を示す図である。図２を参照すると、通信部１１と、ラプラシアン行列計算部１２と、第２最小固有値計算部１３と、隣接行列計算部１４と、最大固有値計算部１５と、初到達時刻算出部１６と、比較部１７と、ＮＷ構成決定部１８とを備えた構成が示されている。
【００４１】
通信部１１は、通信ノードＣＮと各種情報をやり取りするための手段である。具体的には、通信ＮＷ１の構成情報や局所情報通知用ＮＷの構成情報の送受信が行われる。
【００４２】
ラプラシアン行列計算部１２は、通信ノードＣＮから受け取った通信ＮＷ１の構成情報を元に、ＮＷ構成決定部１８から指示されたＮＷ範囲の規格化ラプラシアン行列ＮＬを生成する。
【００４３】
第２最小固有値計算部１３は、ラプラシアン行列計算部１２にて生成された規格化ラプラシアン行列ＮＬの第２最小固有値を計算し、初到達時刻算出部１６に出力する。
【００４４】
隣接行列計算部１４は、通信ノードＣＮから受け取った通信ＮＷ１の構成情報を元に、ＮＷ構成決定部１８から指示されたＮＷ範囲の隣接行列Ａを生成する。
【００４５】
最大固有値計算部１５は、隣接行列計算部１４にて生成された隣接行列Ａの最大固有値を計算し、初到達時刻算出部１６に出力する。
【００４６】
初到達時刻算出部１６は、第２最小固有値計算部１３および最大固有値計算部１５より受信した計算結果と、ＮＷ構成決定部１８から指示されたパラメータとを、上述した［数１］に代入して初到達時刻を計算する。
【００４７】
比較部１７は、初到達時刻算出部１６にて計算された初到達時刻と、ＮＷ構成決定部１８にて決定されたＮｍａｘとを比較する手段である。
【００４８】
ＮＷ構成決定部１８は、後記する故障・障害情報ｉを伝達可能な物理リンク数の最大値を示すＮｍａｘを算出し、初到達時刻算出部１６による初到達時刻がＮｍａｘ未満となるまで、上記計算サーバＣＳの各部を制御し、計算を繰り返させ、局所情報の通知用ＮＷの範囲及び構成を決定する手段である。
【００４９】
なお、図２に示した計算サーバの各部（処理手段）は、計算サーバを構成するコンピュータに、そのハードウェアを用いて、上記した各処理を実行させるコンピュータプログラムにより実現することもできる。
【００５０】
続いて、本実施形態の動作について図面を参照して詳細に説明する。図３は、本発明の第１の実施形態の局所情報の伝播方法（準備段階）を説明するための流れ図である。以下、通信ＮＷ１が既に構成され、経路制御によって論理ネットワークＮＷＬ１が決定されているものとする。この通信ＮＷ１内で発生する局所的な故障・障害情報について、出来るだけ広範囲かつ必要な部分に、その伝播領域を設定し、かつ、高速に伝播させる手順を説明する。また以下の説明では、前記故障・障害情報は、故障・障害の程度、故障・障害が発生したノードの識別情報、発生時刻などを含むものとする。
【００５１】
（手順Ｓ１−１）故障・障害が発生した場合に、故障・障害情報ｉを伝達するための通信プロトコルＰ２を準備しておく。この通信プロトコルＰ２としては、経路制御プロトコルＰ１より高速に通信可能な専用通信プロトコルが選択される。より望ましくは、通信ＮＷの任意の部分ＮＷ（局所情報通知用ＮＷ）上の経路を用いて、故障・障害情報ｉを拡散させるのに適した通信プロトコルが選択される。
【００５２】
（手順Ｓ１−２）次に、ｎ＝１として、以下（手順Ｓ１−２−１）から（手順Ｓ１−２−５）のように、通信ＮＷの故障・障害情報ｉを伝播させる仮の故障・障害情報通知用の範囲Ｗ１＿ｎを決める。ここで範囲Ｗ１＿ｎとは、当該範囲Ｗ１＿ｎに属するすべての通信ノードが有するＮＷ制御機能が、前記故障・障害情報ｉが到着した時間を同一時刻であると認識可能な範囲のことである。以下、この範囲Ｗ１＿ｎにおいて、上記（性質１）および（性質２）を満たすようなＷ１＿ｘを求め、局所情報通知用ＮＷを構成する。
【００５３】
（手順Ｓ１−２−１）まず、通信ＮＷ１の構成済みの局所情報通知用ＮＷに属していない任意の通信ノードＣＮに接続されている固有値計算用の計算サーバＣＳを１つ決定する。図４は、上記通信ノードＣＮに接続されている固有値計算用の計算サーバＣＳを１つ決定した状態を示す図である。この段階では、通信ＮＷ１には局所情報通知用ＮＷが一つも決定されていない状態である。
【００５４】
（手順Ｓ１−２−２）ＮＷ管理者が、故障・障害発生時点からＮＷの制御を開始するまでの所望の所要時間の最大値Ｔｍａｘを決定する。つまり、Ｔｍａｘは、故障・障害情報ｉを伝播させる時間の最大許容値である。
【００５５】
（手順Ｓ１−２−３）前記計算サーバＣＳにおいて、前記所要時間の最大値Ｔｍａｘを、通信プロトコルＰ２によって通信ＮＷ１に属する任意の２つの通信ノード間で通信を行うために必要な時間ＴＰ２で割る。これによって得られた値を超えない最大の自然数をＮｍａｘとする。Ｎｍａｘは、局所情報通知用ＮＷ上の通信ノード間を、プロトコルＰ２を用いて、（手順Ｓ１−２）の意味で同一時間内に、故障・障害情報ｉを伝達可能な物理リンク数の最大値を示している。
【００５６】
（手順Ｓ１−２−４）通信ＮＷ１から適当な通信ノードＮ０を決定し、この通信ノードＮ０から物理リンクを辿って到達できるＮｍａｘ番目までの通信ノードをすべて集める。
【００５７】
（手順Ｓ１−２−５）（手順Ｓ１−２−４）によって集められた通信ノードによって構成された範囲を範囲Ｗ１＿ｎとする。また、このとき範囲Ｗ１＿ｎに含まれる通信ノード数の総数をＮとする。
【００５８】
（手順Ｓ１−３）計算サーバＣＳにおいて、範囲Ｗ１＿ｎの隣接行列Ａと規格化ラプラシアン行列ＮＬを生成する。隣接行列Ａと規格化ラプラシアン行列ＮＬは共にＮ行Ｎ列の行列になる。
【００５９】
（手順Ｓ１−４）計算サーバＣＳにおいて、上記隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２を求める。また、上記［数１］を用いてＬ＝２、次数ｄ（ｓ）＝ｄ（ｔ）＝１とした場合の初到達時刻π＿Ｗ１＿ｎを算出する。
【００６０】
次に、初到達時刻π＿Ｗ１＿ｎとＮｍａｘとを比較し、π＿Ｗ１＿ｎ＜Ｎｍａｘであるか否か、即ち、範囲Ｗ１＿ｎの任意の２ノード間のランダムウォークによるホップ数がＮｍａｘより小さいこと（ＮＷ内に収まっていること）を確認する。ここでもし、π＿Ｗ１＿ｎ≧Ｎｍａｘであれば、通信ノード数を１個ずつ増加させて、手順（１−２−４）以下の処理を繰り返し、π＿Ｗ１＿ｎ＜Ｎｍａｘが満たされるようにする。
【００６１】
（手順Ｓ１−５）計算サーバＣＳにおいて、範囲Ｗ１＿ｎの隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２とが増えているようであれば、（手順Ｓ１−６）に進む。一方、範囲Ｗ１＿ｎの隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２とが増えていない場合には、当該範囲Ｗ１＿ｎを範囲Ｗ１＿ｘとして決定する。図５は、上記範囲Ｗ１＿ｘが決定された状態を示す図である。
【００６２】
（手順Ｓ１−６）計算サーバＣＳにおいて、ｎ＝ｎ＋１として、Ｗ１＿ｎに属する通信ノードＣＮを除く通信ノードまたは／およびリンクを削除し、新しい範囲Ｗ１＿ｎを構成する。なお、上記新しい範囲Ｗ１＿ｎを求める方法としては、非特許文献５の焼きなまし法と呼ばれる最適化アルゴリズムを用いることができる。
【００６３】
（手順Ｓ１−７）（手順Ｓ１−５）にて範囲Ｗ１＿ｘが確定すると、計算サーバＣＳは、範囲Ｗ１＿ｘに属するすべてのノードに対して、通信プロトコルＰ２によって、通信ノードＣＮを起点として、範囲Ｗ１＿ｘによって構成される局所情報通知用ＮＷの構成情報を伝達する。
【００６４】
（手順Ｓ１−８）通信ＮＷ１の構成済みの局所情報通知用ＮＷ（範囲Ｗ１＿ｘ）を除いた、残りのＮＷについても、上記（手順Ｓ１−２−１）から（手順Ｓ１−７）を行い、最終的には、ＮＷ１全体がＷ１＿ｘのような、局所情報通知用ＮＷによって分割されるようにする（図１参照）。
【００６５】
その後、局所情報通知用ＮＷにおいて、故障・障害情報ｉが発生した場合には、（手順Ｓ１−１）で準備した専用通信プロトコルＰ２によって、範囲Ｗ１＿ｘに属するすべてのノードに故障・障害情報ｉを伝達する処理が行われる。
【００６６】
ここで、通信ノードによる故障・障害情報ｉの伝達処理について図面を参照して詳細に説明する。
【００６７】
図６は、本発明の第１の実施形態の局所情報の伝播方法（伝播段階）を説明するための流れ図である。
【００６８】
（手順Ｓ５−１）まず、（手順Ｓ１−８）で構成された複数の部分ＮＷそれぞれにおいて、各部分ＮＷ内のすべてのノードについて、各ノードを根とする最短スパニング木を構成する。最短スパニング木については、非特許文献８参照。
【００６９】
（手順Ｓ５−２）故障・障害が発生した範囲Ｗ１＿ｘに属する通信ノードＮｘは、フラッディングアルゴリズムによって、自身を根とする最短スパニング木上の隣接ノードに故障・障害情報ｉを伝達する。フラッディングアルゴリズムについては、非特許文献６参照。
【００７０】
（手順Ｓ５−３）上記通信ノードＮｘから故障・障害情報ｉを受け取った他の通信ノードは、同様に、自身を根とする最短スパニング木上の隣接ノードに故障・障害情報ｉを伝達する。範囲Ｗ１＿ｘに属するすべての通信ノードに故障・障害情報ｉが伝達されるまで、各通信ノードが上記動作を繰り返す。
【００７１】
（手順Ｓ５−４）なお、（手順Ｓ５−３）において、１つの通信ノードが複数の故障・障害情報ｉを受け取る場合がある。この場合、以下の（手順Ｓ５−４−１）または（手順Ｓ５−４−２）が行われる。
【００７２】
（手順Ｓ５−４−１）複数の故障・障害情報ｉを受け取った通信ノードは、前記複数の故障・障害情報に含まれているノード識別情報または発生時刻情報が異なる場合、最短スパニング木上の隣接ノードに、前記複数の故障・障害情報ｉを伝達する。
【００７３】
（手順Ｓ５−４−２）一方、前記複数の故障・障害情報に含まれているノード識別情報および発生時刻情報が同一である場合、前記複数の故障・障害情報ｉを受け取った通信ノードは、これら複数の故障・障害情報の１つを選択し、最短スパニング木上の隣接ノードに伝達する。
【００７４】
このようにして、故障・障害情報ｉを受け取った通信ノードは、それぞれ事前にＮＷ管理者などによって規定された制御を行う。
【００７５】
以上に説明したように、「ＮＷ内で発生する局所的な故障・障害情報の伝播領域を出来るだけ広範囲かつ必要な部分に設定し、かつ、高速に伝播させる」という互いに相反する２つの目的を実現することが可能となり、それによって「局所的なＮＷ制御を高速に行う」という目的が達成可能になる。なお、上記した実施形態では、ＮＷ内で発生する局所的な故障・障害情報を伝達する例を挙げて説明したが、各種の情報処理システム等で、発生する局所的な故障・障害情報についても、同様の手順により、広域かつ必要な範囲を設定し、高速に伝播させることが可能になる。
【００７６】
また、上記した実施形態の（手順Ｓ１−１）で説明した経路制御プロトコルＰ１は、ＴＣＰ／ＩＰプロトコル（非特許文献７参照）などの既存の経路制御プロトコルであっても良い。
【００７７】
また、上記した実施形態の（手順Ｓ１−６）で挙げた最適化アルゴリズムとしては、焼きなまし法のほか、その他の最適化手法を用いることもできる。さらに、これら最適化手法を用いる際に、新しい範囲Ｗ＿ｎの各ノードの次数、ｂｅｔｗｅｅｎｅｓｓ中心性、平均距離、最小ループサイズ、次数相関の分布（非特許文献５）において、一様になるように、削除する通信ノードまたは／およびリンクを選ぶようにしても良い。
【００７８】
［第２の実施形態］
続いて、上記故障・障害情報ｉに代えて、輻輳情報ｊを伝達させるようにした本発明の第２の実施形態について図面を参照して詳細に説明する。
【００７９】
図７は、本発明の第２の実施形態の局所情報の伝播方法（準備段階）を説明するための流れ図である。以下、本実施形態においても、通信ネットワーク（以下、「通信ＮＷ２」と記す。）が既に構成され、経路制御によって論理ネットワークＮＷＬ１が決定されているものとする。この通信ＮＷ１内で発生する局所的な輻輳情報について、出来るだけ広範囲かつ必要な部分に、その伝播領域を設定し、かつ、高速に伝播させる手順を説明する。また以下の説明では、前記輻輳情報は、輻輳の程度、輻輳が発生したノードの識別情報、発生時刻などを含み、通信ノードは、受信した輻輳情報に基づいて局所的な迂回経路を設定するＮＷ制御機能を有しているものとする。
【００８０】
（手順Ｓ２−１）輻輳が発生した場合に、輻輳情報ｊを伝達するための通信プロトコルＰ２を準備しておく。この通信プロトコルＰ２としては、経路制御プロトコルＰ１より高速に通信可能な専用通信プロトコルが選択される。より望ましくは、通信ＮＷの任意の部分ＮＷ（局所情報通知用ＮＷ）上の経路を用いて、輻輳情報ｊを拡散させるのに適した通信プロトコルが選択される。例えば、非特許文献６のフラッディングアルゴリズムによって輻輳情報の拡散を行うプロトコルであってもよい。
【００８１】
（手順Ｓ２−２）次に、ｎ＝１として、以下（手順Ｓ２−２−１）から（手順Ｓ２−２−５）のように、通信ＮＷの輻輳情報ｊを伝播させる仮の輻輳情報通知用の範囲Ｗ２＿ｎを決める。ここで範囲Ｗ２＿ｎとは、当該範囲Ｗ２＿ｎに属するすべての通信ノードが有するＮＷ制御機能が、前記輻輳情報ｊが到着した時間を同一時刻であると認識可能な範囲のことである。以下、この範囲Ｗ２＿ｎにおいて、上記（性質１）および（性質２）を満たすようなＷ２＿ｘを求め、局所情報通知用ＮＷを構成する。
【００８２】
（手順Ｓ２−２−１）まず、通信ＮＷの構成済みの局所情報通知用ＮＷに属していない任意の通信ノードＣＮに接続されている固有値計算用の計算サーバＣＳを１つ決定する。
【００８３】
（手順Ｓ２−２−２）ＮＷ管理者が、輻輳発生時点からＮＷの制御を開始するまでの所望の所要時間の最大値Ｔｍａｘを決定する。つまり、Ｔｍａｘは、輻輳情報ｊを伝播させる時間の最大許容値である。
【００８４】
（手順Ｓ２−２−３）前記計算サーバＣＳにおいて、前記所要時間の最大値Ｔｍａｘを、通信プロトコルＰ２によって通信ＮＷ２に属する任意の２つの通信ノード間で通信を行うために必要な時間ＴＰ２で割る。これによって得られた値を超えない最大の自然数をＮｍａｘとする。Ｎｍａｘは、局所情報通知用ＮＷ上の通信ノード間を、プロトコルＰ２を用いて、（手順Ｓ２−２）の意味で同一時間内に、輻輳情報ｊを伝達可能な物理リンク数の最大値を示している。
【００８５】
（手順Ｓ２−２−４）通信ＮＷ２から適当な通信ノードＮ０を決定し、この通信ノードＮ０から物理リンクを辿って到達できるＮｍａｘ番目までの通信ノードをすべて集める。
【００８６】
（手順Ｓ２−２−５）（手順Ｓ２−２−４）によって集められた通信ノードによって構成された範囲を範囲Ｗ２＿ｎとする。また、このとき範囲Ｗ２＿ｎに含まれる通信ノード数の総数をＮとする。
【００８７】
（手順Ｓ２−３）計算サーバＣＳにおいて、範囲Ｗ２＿ｎの隣接行列Ａと規格化ラプラシアン行列ＮＬを生成する。隣接行列Ａと規格化ラプラシアン行列ＮＬは共にＮ行Ｎ列の行列になる。
【００８８】
（手順Ｓ２−４）計算サーバＣＳにおいて、上記隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２を求める。また、上記［数１］を用いてＬ＝２、次数ｄ（ｓ）＝ｄ（ｔ）＝１とした場合の初到達時刻π＿Ｗ２＿ｎを算出する。
【００８９】
次に、初到達時刻π＿Ｗ２＿ｎとＮｍａｘとを比較し、π＿Ｗ２＿ｎ＜Ｎｍａｘであるか否か、即ち、範囲Ｗ２＿ｎの任意の２ノード間のランダムウォークによるホップ数がＮｍａｘより小さいこと（ＮＷ内に収まっていること）を確認する。ここでもし、π＿Ｗ２＿ｎ≧Ｎｍａｘであれば、通信ノード数を１個ずつ増加させて、手順（２−２−４）以下の処理を繰り返し、π＿Ｗ２＿ｎ＜Ｎｍａｘが満たされるようにする。
【００９０】
（手順Ｓ２−５）計算サーバＣＳにおいて、範囲Ｗ２＿ｎの隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２とが増えているようであれば、（手順Ｓ２−６）に進む。一方、範囲Ｗ２＿ｎの隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２とが増えていない場合には、当該範囲Ｗ２＿ｎを範囲Ｗ２＿ｘとして決定する。
【００９１】
（手順Ｓ２−６）計算サーバＣＳにおいて、ｎ＝ｎ＋１として、Ｗ２＿ｎに属する通信ノードＣＮを除く通信ノードまたは／およびリンクを削除し、新しい範囲Ｗ２＿ｎを構成する。なお、上記新しい範囲Ｗ２＿ｎを求める方法としては、先の第１の実施形態と同様に、非特許文献５の焼きなまし法やその他最適化アルゴリズムを用いることができる。
【００９２】
（手順Ｓ２−７）（手順Ｓ２−５）にて範囲Ｗ２＿ｘが確定すると、計算サーバＣＳは、範囲Ｗ２＿ｘに属するすべてのノードに対して、通信プロトコルＰ２によって、通信ノードＣＮを起点として、範囲Ｗ２＿ｘによって構成される局所情報通知用ＮＷの構成情報を伝達する。
【００９３】
（手順Ｓ２−８）通信ＮＷ２の構成済みの局所情報通知用ＮＷ（範囲Ｗ２＿ｘ）を除いた、残りのＮＷについても、上記（手順Ｓ２−２−１）から（手順Ｓ２−７）を行い、最終的には、ＮＷ２全体がＷ２＿ｘのような、局所情報通知用ＮＷによって分割されるようにする。
【００９４】
（図８のＳ２−９）その後、局所情報通知用ＮＷにおいて、輻輳情報ｊが発生した場合には、図８に示すように、（手順Ｓ２−１）で準備した専用通信プロトコルＰ２によって、範囲Ｗ２＿ｘに属するすべてのノードに輻輳情報ｊを伝達する処理が行われる。各通信ノードにおける輻輳情報ｊの具体的な伝達処理は第１の実施形態と同様である（図６参照）。
【００９５】
（図８の手順Ｓ２−１０）このようにして、輻輳情報ｊを受け取った通信ノードは、それぞれ事前にＮＷ管理者などによって規定された、輻輳を起こした通信ノードを通らないような迂回経路を構築し、該迂回経路に沿って、通常の通信を行う。
【００９６】
以上のように、本発明は、輻輳情報ｊの伝達と、これを用いた経路の迂回制御にも適用することが可能である。
【００９７】
なお、経路制御プロトコルＰ１が自律的あるいは自律分散的なプロトコルである場合には、図８の（手順Ｓ２−１０）における迂回経路として、事前にＮＷ管理者などによって決定されたものではなく、経路制御プロトコルＰ１によって、輻輳情報ｊ到着後に自律的あるいは自律分散的に構築されるものであっても良い。
【００９８】
［第３の実施形態］
続いて、所与のＮＷを用いるのではなく、上記（性質１）および（性質２）を満たすようなＮＷ（以下、「通信ＮＷ３」と記す。）を設計し、任意の局所情報ｋを伝達させるようにした本発明の第３の実施形態について図面を参照して詳細に説明する。
【００９９】
図９は、本発明の第３の実施形態の局所情報の伝播方法（準備段階）を説明するための流れ図である。また、局所情報ｋは、事象の程度、事象が発生したノードの識別情報、発生時刻などを含むものとする。
【０１００】
（手順Ｓ３−１）局所的な事象が発生した場合に、局所情報ｋを伝達するための通信プロトコルＰ２を準備しておく。この通信プロトコルＰ２としては、経路制御プロトコルＰ１より高速に通信可能な専用通信プロトコルが選択される。より望ましくは、通信ＮＷ３の任意の部分ＮＷ（局所情報通知用ＮＷ）上の経路を用いて、局所情報ｋを拡散させるのに適した通信プロトコルが選択される。例えば、非特許文献６のフラッディングアルゴリズムによって局所情報ｋの拡散を行うプロトコルであってもよい。
【０１０１】
（手順Ｓ３−２）次に、ｎ＝１として、以下（手順Ｓ３−２−１）から（手順Ｓ３−２−６）のように、通信ＮＷ３の局所情報ｋを伝播させる仮の局所情報通知用の範囲Ｗ３＿ｎを決める。ここで範囲Ｗ３＿ｎとは、当該範囲Ｗ３＿ｎに属するすべての通信ノードが有するＮＷ制御機能が、前記局所情報ｋが到着した時間を同一時刻であると認識可能な範囲のことである。以下、この範囲Ｗ３＿ｎにおいて、上記（性質１）および（性質２）を満たすようなＷ３＿ｘを求め、局所情報通知用ＮＷを構成する。
【０１０２】
（手順Ｓ３−２−１）まず、ＮＷ設計者は、ＮＷ設計サーバに、設計すべき通信ＮＷ３のノード数の最大値ｎ＿ｍａｘとリンク数の最大値Ｌ＿ｍａｘとを設定する。
【０１０３】
（手順Ｓ３−２−２）次に、ＮＷ設計者は、局所情報発生時点からＮＷの制御を開始するまでの所望の所要時間の最大値Ｔｍａｘを決定する。つまり、Ｔｍａｘは、局所情報ｋを伝播させる時間の最大許容値である。
【０１０４】
（手順Ｓ３−２−３）前記所要時間の最大値Ｔｍａｘを、通信プロトコルＰ２によって通信ＮＷ３に属する任意の２つの通信ノード間で通信を行うために必要な時間ＴＰ２で割る。これによって得られた値を超えない最大の自然数をＮｍａｘとする。Ｎｍａｘは、局所情報通知用ＮＷ上の通信ノード間を、プロトコルＰ２を用いて、（手順Ｓ３−２）の意味で同一時間内に、局所情報ｋを伝達可能な物理リンク数の最大値を示している。
【０１０５】
（手順Ｓ３−２−４）ＮＷ設計サーバは、ノード数ｎ＿ｍａｘの完全グラフＮＷＣを構成する。
【０１０６】
（手順Ｓ３−２−５）ＮＷ設計サーバは、通信ＮＷ３から適当な通信ノードＮ０を決定し、この通信ノードＮ０から物理リンクを辿って到達できるＮｍａｘ番目までの通信ノードをすべて集める。
【０１０７】
（手順Ｓ３−２−６）（手順Ｓ３−２−５）によって集められた通信ノードによって構成された範囲を範囲Ｗ３＿ｎとする。また、このとき範囲Ｗ３＿ｎに含まれる通信ノード数の総数をＮとする。
【０１０８】
（手順Ｓ３−３）ＮＷ設計サーバにおいて、範囲Ｗ３＿ｎの隣接行列Ａと規格化ラプラシアン行列ＮＬを生成する。隣接行列Ａと規格化ラプラシアン行列ＮＬは共にＮ行Ｎ列の行列になる。
【０１０９】
（手順Ｓ３−４）ＮＷ設計サーバにおいて、上記隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２を求める。また、上記［数１］を用いてＬ＝２、次数ｄ（ｓ）＝ｄ（ｔ）＝１とした場合の初到達時刻π＿Ｗ３＿ｎを算出する。
【０１１０】
次に、ＮＷ設計サーバは、初到達時刻π＿Ｗ３＿ｎとＮｍａｘとを比較し、π＿Ｗ３＿ｎ＜Ｎｍａｘであるか否か、即ち、範囲Ｗ３＿ｎの任意の２ノード間のランダムウォークによるホップ数がＮｍａｘより小さいこと（ＮＷ内に収まっていること）を確認する。ここでもし、π＿Ｗ３＿ｎ≧Ｎｍａｘであれば、通信ノード数を１個ずつ増加させて、手順（３−２−４）以下の処理を繰り返し、π＿Ｗ３＿ｎ＜Ｎｍａｘが満たされるようにする。
【０１１１】
（手順Ｓ３−５）ＮＷ設計サーバは、範囲Ｗ３＿ｎの隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２とが増えているようであれば、（手順Ｓ３−６）に進む。一方、範囲Ｗ３＿ｎの隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２とが増えていない場合には、範囲Ｗ３＿ｎのノード数とリンク数がそれぞれ（手順Ｓ３−２−１）で定めたｎ＿ｍａｘとＬ＿ｍａｘ以下であるかどうかを確認する。
【０１１２】
前記確認の結果、範囲Ｗ３＿ｎのノード数とリンク数がそれぞれ（手順Ｓ３−２−１）で定めた条件を満たしているようであれば、ＮＷ設計サーバは、当該範囲Ｗ３＿ｎを範囲Ｗ３＿ｘとして決定する。また、範囲Ｗ３＿ｎのノード数とリンク数の少なくとも一方が、（手順Ｓ３−２−１）で定めた条件を満たしていない場合、ＮＷ設計サーバは、（手順Ｓ３−６）に進む。
【０１１３】
（手順Ｓ３−６）ＮＷ設計サーバにおいて、ｎ＝ｎ＋１として、Ｗ３＿ｎに属する通信ノードＣＮを除く通信ノードまたは／およびリンクを削除し、新しい範囲Ｗ３＿ｎを構成する。なお、上記新しい範囲Ｗ３＿ｎを求める方法としては、先の第１、第２の実施形態と同様に、非特許文献５の焼きなまし法やその他最適化アルゴリズムを用いることができる。
【０１１４】
（手順Ｓ３−７）（手順Ｓ３−５）にて範囲Ｗ３＿ｘが確定すると、ＮＷ設計サーバは、範囲Ｗ３＿ｘに属するすべてのノードに対して、通信プロトコルＰ２によって、通信ノードＣＮを起点として、範囲Ｗ３＿ｘによって構成される局所情報通知用ＮＷの構成情報を伝達し記憶させる。
【０１１５】
（手順Ｓ３−８）通信ＮＷ３の構成済みの局所情報通知用ＮＷ（範囲Ｗ３＿ｘ）を除いた、残りのＮＷについても、上記（手順Ｓ３−２−４）から（手順Ｓ３−７）を行い、最終的には、全体がＷ３＿ｘのような、局所情報通知用ＮＷによって分割された通信ＮＷ３を構築する。
【０１１６】
（図１０のＳ３−９）このようにして構成されたＮＷ３の局所情報通知用ＮＷにおいて、局所情報ｋが発生した場合には、図１０に示すように、（手順Ｓ３−１）で準備した専用通信プロトコルＰ２によって、範囲Ｗ３＿ｘに属するすべてのノードに局所情報ｋを伝達する処理が行われる。各通信ノードにおける局所情報ｋの具体的な伝達処理は第１の実施形態と同様である（図６参照）。
【０１１７】
（図１０の手順Ｓ３−１０）このようにして、局所情報ｋを受け取った通信ノードは、それぞれ事前にＮＷ管理者などによって決定されたＮＷ制御を行う。
【０１１８】
以上のように、本発明の局所情報の伝達方法を好適に実施できるようにネットワークを設計しておくことで、その後の局所情報ｋの伝播範囲Ｗ３の決定を省略することができる。
【０１１９】
なお、各通信ノードが、自律的あるいは自律分散的なＮＷ制御機能を備えている場合には、図１０の（手順Ｓ３−１０）におけるＮＷ制御として、事前にＮＷ管理者などによって決定されたものではなく、当該ＮＷ制御機能により、局所情報ｋに応じた制御内容を実行するようにしても良い。
【０１２０】
［第４の実施形態］
続いて、あるノードが、当該ＮＷ内の他のノードに仮想的に機能Ｆを提供する機能を備えており、当該機能Ｆの要求情報ｍの伝播を行いうるＮＷ（以下、「通信ＮＷ４」と記す。）の設計を構成する本発明の第４の実施形態について図面を参照して詳細に説明する。
【０１２１】
図１１は、本発明の第４の実施形態の要求情報の伝播方法（準備段階）を説明するための流れ図である。また、要求情報ｍは、要求している機能、要求しているノードの識別情報、要求時刻などを含むものとする。
【０１２２】
（手順Ｓ４−１）機能Ｆの要求情報ｍが発生した場合に、要求情報ｍを伝達するための通信プロトコルＰ２を準備しておく。この通信プロトコルＰ２としては、経路制御プロトコルＰ１より高速に通信可能な専用通信プロトコルが選択される。より望ましくは、通信ＮＷ４の任意の部分ＮＷ（局所情報通知用ＮＷ）上の経路を用いて、要求情報ｍを拡散させるのに適した通信プロトコルが選択される。例えば、非特許文献６のフラッディングアルゴリズムによって要求情報ｍの拡散を行うプロトコルであってもよい。
【０１２３】
（手順Ｓ４−２）次に、ｎ＝１として、以下（手順Ｓ４−２−１）から（手順Ｓ４−２−６）のように、要求情報ｍを伝播させる仮の局所情報通知用の範囲Ｗ４＿ｎを決める。ここで範囲Ｗ４＿ｎとは、当該範囲Ｗ４＿ｎに属するすべての通信ノードが有するＮＷ制御機能が、前記要求情報ｍが到着した時間を同一時刻であると認識可能な範囲のことである。以下、この範囲Ｗ４＿ｎにおいて、上記（性質１）および（性質２）を満たすようなＷ４＿ｘを求め、局所情報通知用ＮＷを構成する。
【０１２４】
（手順Ｓ４−２−１）まず、ＮＷ設計者は、ＮＷ設計サーバに、設計すべき通信ＮＷ４のノード数の最大値ｎ＿ｍａｘとリンク数の最大値Ｌ＿ｍａｘとを設定する。
【０１２５】
（手順Ｓ４−２−２）次に、ＮＷ設計者は、局所情報発生時点からＮＷの制御を開始するまでの所望の所要時間の最大値Ｔｍａｘを決定する。つまり、Ｔｍａｘは、要求情報ｍを伝播させる時間の最大許容値である。
【０１２６】
（手順Ｓ４−２−３）前記所要時間の最大値Ｔｍａｘを、通信プロトコルＰ２によって通信ＮＷ４に属する任意の２つの通信ノード間で通信を行うために必要な時間ＴＰ２で割る。これによって得られた値を超えない最大の自然数をＮｍａｘとする。Ｎｍａｘは、局所情報通知用ＮＷ上の通信ノード間を、プロトコルＰ２を用いて、（手順Ｓ４−２）の意味で同一時間内に、要求情報ｍを伝達可能な物理リンク数の最大値を示している。
【０１２７】
（手順Ｓ４−２−４）ＮＷ設計サーバは、ノード数ｎ＿ｍａｘの完全グラフＮＷＣを構成する。
【０１２８】
（手順Ｓ４−２−５）ＮＷ設計サーバは、通信ＮＷ４から適当な通信ノードＮ０を決定し、この通信ノードＮ０から物理リンクを辿って到達できるＮｍａｘ番目までの通信ノードをすべて集める。
【０１２９】
（手順Ｓ４−２−６）（手順Ｓ４−２−５）によって集められた通信ノードによって構成された範囲を範囲Ｗ４＿ｎとする。また、このとき範囲Ｗ４＿ｎに含まれる通信ノード数の総数をＮとする。
【０１３０】
（手順Ｓ４−３）ＮＷ設計サーバにおいて、範囲Ｗ４＿ｎの隣接行列Ａと規格化ラプラシアン行列ＮＬを生成する。隣接行列Ａと規格化ラプラシアン行列ＮＬは共にＮ行Ｎ列の行列になる。
【０１３１】
（手順Ｓ４−４）ＮＷ設計サーバにおいて、上記隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２を求める。また、上記［数１］を用いてＬ＝２、次数ｄ（ｓ）＝ｄ（ｔ）＝１とした場合の初到達時刻π＿Ｗ４＿ｎを算出する。
【０１３２】
次に、ＮＷ設計サーバは、初到達時刻π＿Ｗ４＿ｎとＮｍａｘとを比較し、π＿Ｗ４＿ｎ＜Ｎｍａｘであるか否か、即ち、範囲Ｗ４＿ｎの任意の２ノード間のランダムウォークによるホップ数がＮｍａｘより小さいこと（ＮＷ内に収まっていること）を確認する。ここでもし、π＿Ｗ４＿ｎ≧Ｎｍａｘであれば、通信ノード数を１個ずつ増加させて、手順（４−２−４）以下の処理を繰り返し、π＿Ｗ４＿ｎ＜Ｎｍａｘが満たされるようにする。
【０１３３】
（手順Ｓ４−５）ＮＷ設計サーバは、範囲Ｗ４＿ｎの隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２とが増えているようであれば、（手順Ｓ４−６）に進む。一方、範囲Ｗ４＿ｎの隣接行列Ａの最大固有値λＮと、規格化ラプラシアン行列ＮＬの第２最小固有値λ２とが増えていない場合には、範囲Ｗ４＿ｎのノード数とリンク数がそれぞれ（手順Ｓ４−２−１）で定めたｎ＿ｍａｘとＬ＿ｍａｘ以下であるかどうかを確認する。
【０１３４】
前記確認の結果、範囲Ｗ４＿ｎのノード数とリンク数がそれぞれ（手順Ｓ４−２−１）で定めた条件を満たしているようであれば、ＮＷ設計サーバは、当該範囲Ｗ４＿ｎを範囲Ｗ４＿ｘとして決定する。また、範囲Ｗ４＿ｎのノード数とリンク数の少なくとも一方が、（手順Ｓ４−２−１）で定めた条件を満たしていない場合、ＮＷ設計サーバは、（手順Ｓ４−６）に進む。
【０１３５】
（手順Ｓ４−６）ＮＷ設計サーバにおいて、ｎ＝ｎ＋１として、Ｗ４＿ｎに属する通信ノードＣＮを除く通信ノードまたは／およびリンクを削除し、新しい範囲Ｗ４＿ｎを構成する。なお、上記新しい範囲Ｗ４＿ｎを求める方法としては、先の第１〜第３の実施形態と同様に、非特許文献５の焼きなまし法やその他最適化アルゴリズムを用いることができる。
【０１３６】
（手順Ｓ４−７）（手順Ｓ４−５）にて範囲Ｗ４＿ｘが確定すると、ＮＷ設計サーバは、範囲Ｗ４＿ｘに属するすべてのノードに対して、通信プロトコルＰ２によって、通信ノードＣＮを起点として、範囲Ｗ４＿ｘによって構成される局所情報通知用ＮＷの構成情報を伝達し記憶させる。
【０１３７】
（手順Ｓ４−８）通信ＮＷ４の構成済みの局所情報通知用ＮＷ（範囲Ｗ４＿ｘ）を除いた、残りのＮＷについても、上記（手順Ｓ４−２−４）から（手順Ｓ４−７）を行い、最終的には、全体がＷ４＿ｘのような、局所情報通知用ＮＷによって分割されたＮＷ４を構築する。
【０１３８】
（図１２のＳ４−９）このようにして構成されたＮＷ４の局所情報通知用ＮＷにおいて、要求情報ｍが発生した場合には、図１２に示すように、（手順Ｓ４−１）で準備した専用通信プロトコルＰ２によって、範囲Ｗ４＿ｘに属するすべてのノードに要求情報ｍを伝達する処理が行われる。各通信ノードにおける要求情報ｍの具体的な伝達処理は第１の実施形態と同様である（図６参照）。
【０１３９】
（図１２の手順Ｓ４−１０）このようにして、要求情報ｍを受け取った通信ノードは、自身が機能Ｆを具備していれば、要求情報ｍを発信したノードに対して機能ＦをＮＷ上で仮想的に提供する。
【０１４０】
以上のように、ＮＷを介して仮想的に機能を提供するノードに対する要求情報の伝達を好適に実施できるようにネットワークを設計しておくことで、その後の要求情報ｍの伝播範囲Ｗ４の決定を省略し、機能Ｆの提供を高速に行うことができる。
【０１４１】
以上、本発明の好適な実施形態を説明したが、本発明は、上記した実施形態に限定されるものではなく、本発明の基本的技術的思想を逸脱しない範囲で、更なる変形・置換・調整を加えることができる。例えば、上記した実施形態では、ＮＷのノード間での局所的な情報の伝達に用いた例を挙げて説明したが、各種の情報処理システム等で、発生する局所的な情報についても、同様の手順により、広域かつ必要な範囲を設定し、高速に伝播させることが可能になる。
【０１４２】
なお、上記の非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１４３】
１１  通信部
１２  ラプラシアン行列計算部
１３  第２最小固有値計算部
１４  隣接行列計算部
１５  最大固有値計算部
１６  初到達時刻算出部
１７  比較部
１８  ＮＷ構成決定部
Ａ          隣接行列
ＮＬ        規格化ラプラシアン行列
λＮ        隣接行列の最大固有値
λ２        規格化ラプラシアン行列の第２最小固有値
ＮＷＣ      ノード数がｎ＿ｍａｘの完全グラフ
Ｐ１        経路制御用のプロトコル
Ｐ２        局所情報を伝播させるための専用プロトコル
ＣＮ        通信ノード
ＣＳ        計算サーバ
ｉ          故障・障害情報
ｊ          輻輳情報
ｋ          局所情報
ｍ          要求情報
【図１】
2012128352.tif 000004
【図２】
2012128352.tif 000005
【図３】
2012128352.tif 000006
【図４】
2012128352.tif 000007
【図５】
2012128352.tif 000008
【図６】
2012128352.tif 000009
【図７】
2012128352.tif 000010
【図８】
2012128352.tif 000011
【図９】
2012128352.tif 000012
【図１０】
2012128352.tif 000013
【図１１】
2012128352.tif 000014
【図１２】
2012128352.tif 000015
【国際調査報告】
2012128352.tif 000016
2012128352.tif 000017
2012128352.tif 000018