(57)【要約】通信網制御システム１は、複数のノードＮｉを複数のリンク２を介して接続された通信網Ｇ内において、障害を有するノードＮｘを除去し、通信網Ｇの再接続を行う。ノードＮｉは、隣接ノードＮｘに障害が生じたときの通信網Ｇにおける経路情報を算出する経路情報算出手段３と、再接続する相手先候補ノード集合Ｎｉについて、経路情報算出手段３により算出された経路情報上のノード間距離順に順位付けした順位情報を算出する順位情報算出手段４と、順位情報算出手段４により算出された順位情報に基づいて、再接続後の通信網Ｇ全体における経路情報上のノード間距離が大きくなるような組み合わせを算出し、算出した組合せを自ノードＮｉの再接続先ノードとして決定する決定情報算出手段５と、を備える。
2014108944.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードを複数のリンク介して相互に接続された通信網内において、故障した、または障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムであって、
前記複数のノードのうちの少なくとも１つのノードは、
隣接ノードに障害が生じたときの前記通信網における経路情報を算出する経路情報算出手段と、
前記再接続する相手先候補ノード集合について、前記経路情報算出手段により算出された経路情報上のノード間距離順に順位付けした順位情報を算出する順位情報算出手段と、
前記順位情報算出手段により算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報上のノード間距離が大きくなるような組み合わせを算出し、該算出した組合せを自ノードの再接続先ノードとして決定する決定情報算出手段と、
を備える、ことを特徴とする通信網制御システム。
【請求項２】
請求項１記載の通信網制御システムであって、
前記決定情報算出手段は、前記順位情報算出手段により算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報上のノード間距離の平均値が所定閾値以上となる組合せを算出する、ことを特徴とする通信網制御システム。
【請求項３】
請求項１又は２記載の通信網制御システムであって、
前記決定情報算出手段は、前記順位情報算出手段により算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報上のノード間距離の平均値が最大となる組み合わせを算出する、ことを特徴とする通信網制御システム。
【請求項４】
請求項１乃至３のうちいずれか１項記載の通信網制御システムであって、
前記複数のノードのうちの各ノードは、夫々、
前記経路情報算出手段、前記順位情報算出手段、及び前記決定情報算出手段を備え、
前記経路情報算出手段は、自ノードを起点とする最短経路情報を算出する、ことを特徴とする通信網制御システム。
【請求項５】
請求項４記載の通信網制御システムであって、
前記順位情報算出手段は、故障・障害が生じた隣接ノードが存在する場合に、再接続する全相手先候補ノードと、前記算出した順位情報を相互に交換する、ことを特徴とする通信網制御システム。
【請求項６】
請求項１乃至５のうちいずれか１項記載の通信網制御システムであって、
前記再接続先ノードから前記決定の情報を取得し、かつ、前記経路情報上における他ノードから前記決定の情報を取得しない場合、前記自ノードの決定情報算出手段で決定した再接続先ノードを再接続先として確定する決定情報比較手段を更に備える、ことを特徴とする通信網制御システム。
【請求項７】
請求項６記載の通信網制御システムであって、
前記決定情報比較手段は、隣接するノードに故障・障害が生じ通信不可能となった場合に、その次ホップのノードを再接続先として再設定し、経路制御を行う、ことを特徴とする通信網制御システム。
【請求項８】
請求項１乃至７のうちいずれか１項記載の通信網制御システムであって、
前記経路情報算出手段により算出された経路情報及び前記順位情報算出手段により算出された順位情報のうち少なくとも一方を記憶する記憶手段を更に備える、ことを特徴とする通信網制御システム。
【請求項９】
請求項１乃至８のうちいずれか１項記載の通信網制御システムであって、
前記ノードは自律分散的に前記再接続を行う、ことを特徴とする通信網制御システム。
【請求項１０】
請求項１乃至３のうちいずれか１項記載の通信網制御システムであって、
前記複数のノードのうちの予め設定された代表ノードは、
前記経路情報算出手段、前記順位情報算出手段、及び前記決定情報算出手段を備え、
前記経路情報算出手段は、隣接ノードが故障した各ノード集合について、該ノード集合内の各ノードを起点とする最短経路情報を算出する、ことを特徴とする通信網制御システム。
【請求項１１】
請求項１０記載の通信網制御システムであって、
前記決定情報算出手段は、前記通信網内において前記ノードに故障・障害が生じ通信不可能となった場合に、前記再接続先のノードとして決定した情報に基づいて再経路制御を行う、ことを特徴とする通信網制御システム。
【請求項１２】
請求項１乃至１１のうちいずれか１項記載の通信網制御システムであって、
前記通信網には、ラマヌジャングラフが適用されている、ことを特徴とする通信網制御システム。
【請求項１３】
複数のノードを複数のリンク介して相互に接続された通信網内において、故障した、または障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムの制御方法であって、
隣接ノードに障害が生じたときの前記通信網における経路情報を算出するステップと、
前記再接続する相手先候補ノードについて、前記算出された経路情報上の距離順に順位付けした順位情報を算出するステップと、
前記算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報の距離が大きくなるような組み合わせを算出し、該算出した組合せを自ノードの再接続先ノードとして決定するステップと、
を含む、ことを特徴とする通信網制御システムの制御方法。
【請求項１４】
複数のノードを複数のリンク介して相互に接続された通信網内において、故障した、または障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムの制御プログラムを格納する非一時的なコンピュータ可読媒体であって、
隣接ノードに障害が生じたときの前記通信網における経路情報を算出する処理と、
前記再接続する相手先候補ノードについて、前記算出された経路情報上のノード間距離順に順位付けした順位情報を算出する処理と、
前記算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報のノード間距離が大きくなるような組み合わせを算出し、該算出した組み合わせを自ノードの再接続先ノードとして決定する処理と、
をコンピュータに実行させる、ことを特徴とする通信網制御システムの制御プログラムを格納する非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードがリンクを介して相互に接続された通信網を制御する通信網制御システム、その制御方法及び制御プログラムに関するものである。
【背景技術】
【０００２】
近年、網トポロジの分野では「通信網に適用するグラフとしての良さ」が研究テーマの一つとなっており、例えば、ラマヌジャングラフの優位性が明らかになっている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００７−０１４０３０号公報
【特許文献２】特開平０９−２８４３２４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
例えば、このラマヌジャングラフは、通信網や電力網などの物理的／論理的トポロジとして適用されている。一方で、ノードやリンク障害（故障など）によってノードやリンクが元のグラフから削除されても、元のグラフと同程度の効率性とロバスト性を維持できるかという点が問題となっている。
なお、ノード等に故障が生じた場合に通信網の再構成を行う通信網制御システムが知られている（例えば、特許文献１及び２）。また、上述したラマヌジャングラフを部分的に解決した、例えば、ZigZag法が知られている。ZigZag法は，元のラマヌジャングラフからそれより大きなサイズのラマヌジャングラフを構成する手法であり、元のラマヌジャングラフのサイズのｍ倍（ｍは３以上の整数）のラマヌジャングラフを繰り返し的に構成することが可能である。【０００５】
本発明は、このような問題点を解決するためになされたものであり、通信網内のノードやリンクに障害が生じた場合でも、元のグラフの特徴を維持して通信網を最適に再構築できる通信網制御システム、その制御方法及び制御プログラムを提供することを主たる目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するための本発明の一態様は、複数のノードを複数のリンクを介して相互に接続された通信網内において、障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムであって、前記複数のノードのうちの少なくとも１つのノードは、隣接ノードに障害が生じたときの前記通信網における経路情報を算出する経路情報算出手段と、前記再接続する相手先候補ノード集合について、前記経路情報算出手段により算出された経路情報上の距離順に順位付けした順位情報を算出する順位情報算出手段と、前記順位情報算出手段により算出された順位情報に基づいて、前記再接続後の通信網全体における再接続を行う候補ノード集合の経路情報上のノード間距離が大きくなるような組み合わせを算出し、該算出した組合せを自ノードの再接続先ノードとして決定する決定情報算出手段と、を備える、ことを特徴とする通信網制御システムである。
他方、上記目的を達成するための本発明の一態様は、複数のノードを複数のリンク介して相互に接続された通信網内において、障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムの制御方法であって、隣接ノードに障害が生じたときの前記通信網における経路情報を算出するステップと、前記再接続する相手先候補ノードについて、前記算出された経路情報上の距離順に順位付けした順位情報を算出するステップと、前記算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報上のノード間距離が大きくなるような組み合わせを算出し、該算出した組合せを自ノードの再接続先ノードとして決定するステップと、を含む、ことを特徴とする通信網制御システムの制御方法であってもよい。
さらに、上記目的を達成するための本発明の一態様は、複数のノードを複数のリンク介して相互に接続された通信網内において、障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムの制御プログラムであって、隣接ノードに障害が生じたときの前記通信網における経路情報を算出する処理と、前記再接続する相手先候補ノードについて、前記算出された経路情報上の距離順に順位付けした順位情報を算出する処理と、前記算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報の距離が大きくなるような組み合わせを算出し、該算出した組合せを自ノードの再接続先ノードとして決定する処理と、をコンピュータに実行させる、ことを特徴とする通信網制御システムの制御プログラムであってもよい。
【発明の効果】
【０００７】
本発明によれば、通信網内のノードやリンクに障害が生じた場合でも、元のグラフの特徴を維持して通信網を最適に再構築できる通信網制御システム、その制御方法及び制御プログラムを提供することができる。
【図面の簡単な説明】
【０００８】
【図１】本発明の一実施の形態に係る通信網制御システムの機能ブロック図である。
【図２】本発明の実施の形態１に係る通信網の一例を示す図である。
【図３】本発明の実施の形態１に係る通信網制御システムにおける各ノードの概略的なシステム構成を示すブロック図である。
【図４】順位情報及び最短経路の距離情報の一例を示す図である。
【図５】本発明の実施の形態１に係る通信網制御方法のフローを示すフローチャートである。
【図６】本発明の実施の形態２に係る通信網の一例を示す図である。
【図７】本発明の実施の形態２に係る通信網制御システムにおける代表ノードの概略的なシステム構成を示すブロック図である。
【図８】順位情報及び最短経路の距離情報の一例を示す図である。
【図９】本発明の実施の形態２に係る通信網制御方法のフローを示すフローチャートである。
【発明を実施するための形態】
【０００９】
以下、図面を参照して本発明の実施の形態について説明する。図１は、本発明の一実施の形態に係る通信網制御システムの機能ブロック図である。
【００１０】
本実施の形態に係る通信網制御システム１は、複数のノードＮｉ（ｉ＝０〜ｎ−１）を複数のリンク２介して相互に接続された通信網Ｇ内において、障害を有するノードＮｉを除去し、通信網Ｇの再接続を行うものである。通信網制御システム１の複数のノードＮｉのうちの少なくとも１つのノードＮｉは、通信網Ｇにおける経路情報を算出する経路情報算出手段３と、再接続する相手先候補ノードＮｉについての順位情報を算出する順位情報算出手段４と、自ノードＮｉの再接続先ノードＮｉを決定する決定情報算出手段５と、を備える。経路情報算出手段３は、隣接ノードＮｉに障害が生じたときの通信網Ｇにおける経路情報を算出する。順位情報算出手段４は、再接続する相手先候補ノード集合について、経路情報算出手段３により算出された経路情報上の距離順に順位付けした順位情報を算出する。決定情報算出手段５は、順位情報算出手段４により算出された順位情報に基づいて、再接続後の通信網Ｇ全体における経路情報上のノード間距離が大きくなるような組み合わせを算出し、算出した組合せを自ノードＮｉの再接続先候補ノードＮｊ（ただし，ｊ≠ｉかつｊ＝０〜ｎ−１）として決定する。これにより、通信網Ｇ内のノードやリンクに障害が生じた場合でも、元のグラフの特徴を維持して通信網Ｇを最適に再構築できる。
【００１１】
実施の形態１．
図２は、本発明の実施の形態１に係る通信網の一例を示す図である。図２に示すように、本実施の形態１に係る通信網Ｇにおいては、複数のノードＮｉがリンク２を介して相互に接続されている。ここで、例えば、ノードＮｉはルータであり、リンク２は通信用媒体である光ファイバや同軸ケーブルである。また、通信網Ｇ内は、例えばｎ個のノードＮｉ（ｉ＝０〜ｎ−１）で構成されている。
【００１２】
なお、本実施の形態１において、例えば、ラマヌジャングラフを通信網Ｇの物理的／論理的トポロジとして適用している。このラマヌジャングラフは、（１）任意の２ノードＮｉ，Ｎｊ間の通信時間が短いこと、（２）任意の２ノードＮｉ，Ｎｊ間に複数の経路があること、（３）ノードＮｉ間のリンク数が通信網サイズ(＝ノード数)増加に対し線形オーダ以下でしか増加しない、という要求を満たすグラフとして、Ｅｘｐａｎｄｅｒと呼ばれるクラスのグラフに属している。本実施の形態１において、ラマヌジャングラフのノード次数は、例えば４の自然数倍となっているが、これに限らず、任意の次数であってよい。
【００１３】
さらに、上記ラマヌジャングラフの定義に以下に詳細に説明する。
通信網Ｇをノード数ｎ個のｋ−正則グラフとし、通信網Ｇの隣接行列Ａの固有値を大きい方から順に並べると下記式（１−１）が成立する（例えば、Alexander Lubotzky; R. Phillips, Peter Sarnak (1988). "Ramanujan graphs," Combinatorica 8: 261-277参照）。
【数１】
2014108944.tif 000003
λ１以外の自明でない固有値のうち、絶対値が最大のものをλ（Ｇ）とする。
【数２】
2014108944.tif 000004
【００１４】
このとき、下記式（１−３）の不等式を満たす固有値を持つグラフをラマヌジャングラフという。
【数３】
2014108944.tif 000005
【００１５】
次に、ラマヌジャングラフの特徴について述べる。
第１特徴として、ｋ−正則グラフである。つまり、全てのノードＮｉの次数がｋである。第２特徴として、拡大定数が大きい。ここで，拡大定数は下記式（１−４）で定義される。さらに、λ２（Ｌ（Ｇ））はグラフＧのラプラシアン行列の第２最小固有値である。
【数４】
2014108944.tif 000006
【００１６】
第３特徴として内周が大きい。ここで、内周とはグラフ内同じリンクを通らないループ（閉路）のうち、最短のものの長さを言う（例えば、平松豊一、知念宏司 共著."有限数学入門  有限上半平面とラマヌジャングラフ"牧野書店,2003.ISBN4-434-03407-3参照）。第４特徴として直径が小さい。ここで、直径とはグラフ内の任意の２点間の最小距離のうち、最大のものを言う。
【００１７】
本実施の形態１に係る通信網制御システム１によれば、通信網Ｇを構成するノードＮｉの一部を除去した際に、除去したノードＮｉに接続していたリンク２を他のノードＮｉに再接続するだけで、上述したラマヌジャングラフまたはラマヌジャングラフに順ずるグラフを維持可能となる。すなわち、任意の２ノードＮｉ間の通信時間が短く、任意の２ノードＮｉ間に複数の経路が存在し、ノードＮｉ間のリンク数が通信網サイズの増加に対し線形オーダ以下でしか増加しない、というラマヌジャングラフの有利な特徴を維持できる。
【００１８】
本実施の形態１に係る通信網制御システム１においては、通信網Ｇ内のノード／リンク障害などによってノード／リンクがそのような元のラマヌジャングラフから削除されても、元のラマヌジャングラフと同程度の効率性とロバスト（robust）性を維持できる。
【００１９】
換言すると、「サイズがｎのラマヌジャングラフから、障害ノード（故障ノード）Ｎｉを除き、かつその障害ノードＮｉに接続していたリンク２の接続を替えるだけで、サイズｎのラマヌジャングラフと略同一特徴を有するサイズ（ｎ−１）のラマヌジャングラフを再構成できる。
【００２０】
次に、本実施の形態１に係る通信網システムの構成について詳細に説明する。本実施の形態１に係る通信網制御システム１においては、通信網Ｇ内において任意の障害ノードＮｉを除去したときに、残りの各ノードＮｉが自律分散的に再接続を行う。ここでは，ノード次数ｋ＝４の場合について示す。
【００２１】
図３は、本実施の形態１に係る通信網制御システムにおける各ノードの概略的なシステム構成を示すブロック図である。
【００２２】
通信網制御システム１における各ノードＮｉは、通信機能部１１と、経路情報計算部１２と、順位情報計算部１３と、決定情報計算部１４と、決定情報比較部１５と、記憶部１６と、を備えている。
【００２３】
なお、各ノードＮｉは、例えば、制御処理、演算処理等と行うＣＰＵ（Central Processing Unit）、ＣＰＵによって実行される制御プログラム、演算プログラム等が記憶されたＲＯＭ（Read Only Memory）、処理データ等を一時的に記憶するＲＡＭ（Random Access Memory）等からなるマイクロコンピュータを、中心にしてハードウェア構成されている。ＣＰＵ、ＲＯＭ、及びＲＡＭは、データバスなどを介して相互に接続されている。
【００２４】
各ノードＮｉの通信機能部１１は、他のノード（以下、他ノードと称す）Ｎｉとの通信情報の授受を行う通信インターフェイスとしての機能を有している。
【００２５】
各ノードＮｉの経路情報計算部１２は、経路情報算出手段の一具体例であり、通信網Ｇにおいて経路制御が完了した時点で、経路制御プロトコルなどに基づいて自身のノード（以下、自ノードと称す）Ｎｉから２ホップ（hop）の距離）にある全ノードＮｉへの最短経路情報Ｍｉ（ｉ＝０〜ｎ−1）を算出する。
【００２６】
さらに、各ノードＮｉの経路情報計算部１２は、通信網Ｇ内の各ノードＮｉのうち、自ノードＮｉに直接接続されているノード（以下、隣接ノードと称す）Ｎｘが故障した場合、自ノードＮｉを起点とする最短経路情報Ｍｉを算出する。経路情報計算部１２は、算出した最短経路情報Ｍｉを記憶部１６に記憶させる。
【００２７】
各ノードＮｉの順位情報計算部１３は、順位情報算出手段の一具体例であり、再接続する相手先候補ノード候補Ｎｉを経路情報計算部１２により算出された最短経路情報Ｍｉ上のノード間距離が遠い順に順位付けした順位情報Ｌｉ（ｉ＝０〜ｎ−１）を算出する。
【００２８】
各ノードＮｉの順位情報計算部１３は、再接続（故障した隣接ノードＮｘに接続していたリンク２を再接続）する各相手先候補ノード候補Ｎj，Ｎｋ，Ｎｌ（ただし,ｊ≠ｋ≠ｌ≠ｉ≠ｘかつｊ，ｋ，ｌ＝０〜ｎ−１）を、最短経路情報Ｍｉ上のノード間距離が遠い順に順位付けした順位情報Ｌｉを算出する。順位情報計算部１３は、算出した順位情報Ｌｉを最短経路情報Ｍｉの距離情報と共に記憶部１６に記憶させる（図４）。
【００２９】
各ノードＮｉの順位情報計算部１３は、故障した隣接ノードＮｘが存在する場合に、再接続する全相手先ノード候補Ｎj，Ｎｋ，Ｎｌと、算出した順位情報Ｌｉを通信機能部１１を介して相互に交換する。
【００３０】
各ノードＮｉの決定情報計算部１４は、決定情報算出手段の一具体例であり、順位情報計算部１３により算出された順位情報Ｌｉに基づいて、自ノードＮｉの再接続先を決定する。各ノードＮｉの決定情報計算部１４は、順位情報計算部１３により算出された順位情報Ｌｉに基づいて、再接続後の通信網Ｇ全体における最短経路情報Ｍｉのノード間距離の平均値が最大となる接続の組合せを算出する。そして、決定情報計算部１４は、算出した接続の組合せを自ノードＮｉの再接続先ノードとして決定し、その決定情報Ｄｉ（ｉ＝０〜ｎ−1）を記憶部１６に記憶させる。
【００３１】
各ノードＮｉの決定情報計算部１４は、決定した決定情報Ｄｉを、再接続する相手先ノード候補Ｎｊ，Ｎｋ，Ｎｌに対して通信機能部１１を介して送信する。
【００３２】
各ノードＮｉの決定情報比較部１５は、決定情報比較手段の一具体例であり、再接続先ノードＮｋから通信機能部１１を介して決定情報Ｄｉを受信し、かつ、経路情報計算部１２により算出された最短経路情報Ｍｉ上におけるその他ノードＮｊ，Ｎｌから決定情報Ｄｉを受信しない場合、その決定した再接続先ノードＮｋを再接続先として確定する。各ノードＮｉの決定情報比較部１５は、確定した再接続先ノードＮｋを確定情報Ｆｉ（ｉ＝０〜ｎ−１）として記憶部１６に記憶させる。
【００３３】
各ノードＮｉの決定情報比較部１５は、ノードＮｘが故障や障害などで通信不可能となった場合に、その次ホップのノードＮｉを確定情報Ｆｉの再接続先ノードＮｉとして再設定し、通信網Ｇの経路制御を行う。
【００３４】
各ノードＮｉの記憶部１６は、記憶手段の一具体例であり、例えば、上記ＲＯＭやＲＡＭで構成されている。
【００３５】
図５は、本実施の形態１に係る通信網制御方法のフローを示すフローチャートである。
各ノードＮｉの経路情報計算部１２は、通信網Ｇにおいて経路制御が完了した時点で、経路制御プロトコルなどに基づいて自ノードＮｉから２ホップの距離にある全ノードＮｊ，Ｎｋ，Ｎｌへの最短経路情報Ｍｉを算出する。さらに、経路情報計算部１２は、通信網Ｇ内の各ノードＮｉのうち、自ノードＮｉに直接接続されている隣接ノードＮｘが故障した場合、自ノードＮｉを起点とする最短経路情報Ｍｉを算出し、算出した最短経路情報Ｍｉを記憶部１６に記憶させる（ステップＳ１０１）。
【００３６】
各ノードＮｉの順位情報計算部１３は、再接続する相手先候補ノードＮｊ，Ｎｋ，Ｎｌを経路情報計算部１２により算出された最短経路情報Ｍｉ上の距離が遠い順に順位付けした順位情報Ｌｉを算出する（ステップＳ１０２）。
【００３７】
各ノードＮｉの順位情報計算部１３は、故障した隣接ノードＮｉが存在する場合に、再接続する全相手先候補ノードＮｊ，Ｎｋ，Ｎｌと、算出した順位情報Ｌｉを通信機能部１１を介して相互に交換する（ステップＳ１０３）。
【００３８】
各ノードＮｉの決定情報計算部１４は、順位情報計算部１３により算出された順位情報Ｌｉに基づいて、再接続後の通信網Ｇ全体における最短経路情報Ｍｉの距離の平均値が最大となる接続の組合せを算出する。決定情報計算部１４は、算出した再接続の組合せを自ノードＮｉの再接続先ノードとして決定し、その決定情報Ｄｉを記憶部１６に記憶させる（ステップＳ１０４）。
【００３９】
各ノードＮｉの決定情報計算部１４は、決定した決定情報Ｄｉを、再接続する相手先ノードに対して通信機能部１１を介して送信する（ステップＳ１０５）。
【００４０】
各ノードＮｉの決定情報比較部１５は、再接続先ノードＮｋから通信機能部１１を介して決定情報Ｄｉを受信し、かつ、最短経路情報Ｍｉ上におけるその他の再接続先候補ノードＮｊ，Ｎｌから決定情報Ｄｉを受信しない場合（ステップＳ１０６のＮＯ）、その決定した再接続先ノードＮｋを再接続先として確定する（ステップＳ１０７）。決定情報比較部１５は、確定した再接続先ノードＮｋを確定情報Ｆｉとして記憶部１６に記憶させる。
【００４１】
一方、各ノードＮｉの決定情報比較部１５は、再接続先候補ノードＮｊ，Ｎｌから通信機能部１１を介して決定情報Ｄｉを受信した場合（ステップＳ１０６のＹＥＳ）、上記（ステップＳ１０３）又は（ステップＳ１０４）の処理に戻る。
【００４２】
各ノードＮｉの決定情報比較部１５は、隣接ノードＮｘが障害などで通信不可能となった場合に、その次ホップのノードＮｋを確定情報Ｆｉの再接続先ノードとして再設定し、通信網Ｇの経路制御を行う（ステップＳ１０８）。
【００４３】
以上、本実施の形態１に係る通信網制御システム１によれば、サイズがｎのラマヌジャングラフから、障害ノードＮｘを除き、かつその障害ノードＮｘに接続していたリンク２の接続を替えるだけで、サイズｎのラマヌジャングラフと略同一特徴を有するサイズ（ｎ−１）のラマヌジャングラフを再構成できる。すなわち、通信網Ｇ内のノードやリンクに障害が生じた場合でも、元のグラフの特徴を維持して通信網Ｇを最適に再構築できる。
【００４４】
実施の形態２．
上記実施の形態１においては、各ノードＮｉが自律分散的に再接続を行っているが、本実施の形態２においては、代表ノードＮ０が集中制御的に再接続を行うことを特徴としている。図６は、本発明の実施の形態２に係る通信網の一例を示す図である。通信網Ｇ内において中心となる代表ノードＮ０が予め設定され、代表ノードＮ０にリンク２を介して複数のノードＮｉが相互接続されている。
【００４５】
図７は、本実施の形態２に係る通信網制御システムにおける代表ノードの概略的なシステム構成を示すブロック図である。通信網制御システム１における代表ノードＮ０は、通信機能部１１と、経路情報計算部１２と、順位情報計算部１３と、決定情報計算部１４と、記憶部１６と、を備えている。
【００４６】
代表ノードＮ０の経路情報計算部１２は、通信網Ｇにおいて経路制御が完了した時点で、経路制御プロトコルなどに基づいて，通信網Ｇ内の全ノードＮｉについて,それぞれ自身のノードから２ホップの距離にあるノードへの最短経路情報Ｍｉ（ｉ＝０〜ｎ−１）を算出する。さらに、代表ノードＮ０の経路情報計算部１２は、通信網Ｇ内のノードＮｉが故障した各ノード集合について、そのノード集合内の各ノードＮｉを起点とする最短経路情報Ｍｉを算出する。経路情報計算部１２は、算出した最短経路情報Ｍｉを記憶部１６に記憶させる。
【００４７】
代表ノードＮ０の順位情報計算部１３は、再接続する相手先候補ノードＮｉについて、最短経路情報Ｍｉ上における順位情報Ｌｉ（ｉ＝０〜ｎ−１）を算出する。より具体的には、通信網Ｇ内のノードＮｘが故障した場合，代表ノードＮ０の順位情報計算部１３は、その故障ノードＮｘの隣接ノードＮｉに接続していたリンク２を再接続する相手先候補ノードＮｊ，Ｎｋ，Ｎｌについて、経路情報計算部１２により算出された最短経路情報Ｍｉ上における距離が遠い順に順位付けした順位情報Ｌｉを算出する。そして、順位情報計算部１３は、算出した順位情報Ｌｉを最短経路情報Ｍｉの距離情報と共に記憶部１６に記憶させる（図８）。
【００４８】
代表ノードＮ０の決定情報計算部１４は、順位情報計算部１３により算出された順位情報Ｌｉに基づいて、各ノードＮｉの再接続先を決定する。決定情報計算部１４は、例えば、順位情報計算部１３により算出された順位情報Ｌｉに基づいて再接続後の通信網Ｇ全体の最短経路情報Ｍｉの距離の平均値が最大となる接続の組み合わせを算出する。そして、決定情報計算部１４は、算出した接続の組合せを各ノードＮｉの再接続先ノードとして決定し、その確定情報Ｆi（ｉ＝０〜ｎ−１）を記憶部１６に記憶させる。
【００４９】
代表ノードＮ０の決定情報計算部１４は、実際の通信網Ｇ内においてノードＮｘが故障や障害などで通信不可能となった場合に、確定情報Ｆｉに基づいて再経路制御を行う。
【００５０】
図９は、本実施の形態２に係る通信網制御方法のフローを示すフローチャートである。
代表ノードＮ０の経路情報計算部１２は、通信網Ｇにおいて経路制御が完了した時点で、経路制御プロトコルなどに基づいて通信網Ｇ内の全ノードＮｉへの最短経路情報Ｍｉ（ｉ＝０〜ｎ−１）を算出する。さらに、代表ノードＮ０の経路情報計算部１２は、通信網Ｇ内のノードＮｘが故障した場合，その故障ノードＮｘの隣接ノード集合について、そのノード集合内の各ノードＮｉを起点とする最短経路情報Ｍｉを算出し、算出した最短経路情報Ｍｉを記憶部１６に記憶させる（ステップＳ２０１）。
【００５１】
代表ノードＮ０の順位情報計算部１３は、その故障したノードＮｘに接続していたリンク２を再接続する相手先ノード候補Ｎｊ，Ｎｋ，Ｎｌについて、経路情報計算部１２により算出された最短経路情報Ｍｉ上における距離が遠い順に順位付けした順位情報Ｌｉを算出する。そして、順位情報計算部１３は、算出した順位情報Ｌｉを最短経路情報Ｍｉのノード間距離情報と共に記憶部１６に記憶させる（ステップＳ２０２）。
【００５２】
ここで、例えば、通信網Ｇが大きくかつ階層的に構成されている場合、代表ノードＮ０が管理できる範囲は限られ、下位階層のノードＮｉについて管理ができない場合が存在する。この場合、その下位階層のノードＮｉに障害が生じたときに、そのノードＮｉから代表ノードＮ０に順位情報Ｌｉを送信するようにしてもよい。代表ノードＮ０は、後述の確定情報Ｆｉをその下位階層のノードＮｉに送信する。これにより、通信網Ｇが大きい場合でも、通信網Ｇを最適に再構築できる。
【００５３】
代表ノードＮ０の決定情報計算部１４は、順位情報計算部１３により算出された順位情報Ｌｉに基づいて再接続後の通信網Ｇ全体の最短経路情報Ｍｉのノード間距離の平均値が最大となる接続の組合せを算出する。そして、決定情報計算部１４は、算出した接続の組合せを各ノードＮｉの再接続先ノードとして決定し、その確定情報Ｆｉ（ｉ＝０〜ｎ−１）を記憶部１６に記憶させる（ステップＳ２０３）。
【００５４】
代表ノードＮ０の決定情報計算部１４は、実際の通信網Ｇ内においてノードＮｉが故障や障害などで通信不可能となった場合に、確定情報Ｆｉに基づいて再経路制御を行う（ステップＳ２０４）。
【００５５】
以上、本実施の形態２に係る通信網制御システム１において、サイズがｎのラマヌジャングラフから、故障・障害ノードＮｘを除き、かつその故障・障害ノードＮｘに接続していたリンク２の接続を替えるだけで、サイズｎのラマヌジャングラフと略同一特徴を有するサイズ（ｎ−１）のラマヌジャングラフを再構成できる。すなわち、通信網Ｇ内のノードやリンクに障害が生じた場合でも、元のグラフの特徴を維持して通信網Ｇを最適に再構築できる。
【００５６】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【００５７】
例えば、上記実施の形態１及び２において、通信網Ｇに、ラマヌジャングラフが適用されているが、これに限らず、通信網Ｇに、例えば、Ｃａｙｌｅｙグラフ、Ｐｅｔｅｒｓｅｎグラフが適用されてもよく、Ｅｘｐａｎｄｅｒに属する任意のグラフに適用されてもよい。
【００５８】
上記実施の形態１及び２において、経路情報計算部１２は、最短経路情報Ｍｉを算出しているが、これに限らず、例えば、帯域、遅延、若しくは帯域と遅延両方に基づいた経路情報を算出してもよい。この場合、順位情報計算部１３は、経路情報計算部１２により算出された経路情報Ｍｉ上の距離が遠い順に順位付けした順位情報Ｌｉを算出する。
【００５９】
上記実施の形態１及び２において、決定情報計算部１４は、順位情報計算部１３により算出された順位情報Ｌｉに基づいて、再接続後の通信網Ｇ全体における最短経路情報Ｍｉのノード間距離の平均値が最大となる組み合わせを算出しているが、これに限らず、例えば、最短経路情報Ｍｉのノード間距離の平均値が所定閾値以上となる組み合わせを算出してもよい。
【００６０】
また、本発明は、図５及び図９に示す処理を、ＣＰＵにコンピュータプログラムを実行させることにより実現することも可能である。
【００６１】
プログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、ＣＤ−ＲＯＭ（Read Only Memory）、ＣＤ−Ｒ、ＣＤ−Ｒ／Ｗ、半導体メモリ（例えば、マスクＲＯＭ、ＰＲＯＭ（Programmable ROM）、ＥＰＲＯＭ（Erasable PROM）、フラッシュＲＯＭ、ＲＡＭ（random access memory））を含む。
【００６２】
また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００６３】
上記実施の形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６４】
（付記１）
複数のノードを複数のリンクを介して相互に接続された通信網内において、故障または障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムであって、
前記複数のノードのうちの少なくとも１つのノードは、
隣接ノードに障害が生じたときの前記通信網における経路情報を算出する経路情報算出手段と、
前記再接続する相手先候補ノードについて、前記経路情報算出手段により算出された経路情報上の距離順に順位付けした順位情報を算出する順位情報算出手段と、
前記順位情報算出手段により算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報の距離が大きくなるような組み合わせを算出し、該算出した組合せを自ノードの再接続先ノードとして決定する決定情報算出手段と、
を備える、ことを特徴とする通信網制御システム。
（付記２）
（付記１）記載の通信網制御システムであって、
前記決定情報算出手段は、前記順位情報算出手段により算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報のノード間距離の平均値が所定閾値以上となる組合せを算出する、ことを特徴とする通信網制御システム。
（付記３）
（付記１）又は（付記２）記載の通信網制御システムであって、
前記決定情報算出手段は、前記順位情報算出手段により算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報のノード間距離の平均値が最大となる組み合わせを算出する、ことを特徴とする通信網制御システム。
（付記４）
（付記１）乃至（付記３）のうちいずれか記載の通信網制御システムであって、
前記複数のノードのうちの各ノードは、夫々、
前記経路情報算出手段、前記順位情報算出手段、及び前記決定情報算出手段を備え、
前記経路情報算出手段は、自ノードを起点とする最短経路情報を算出する、ことを特徴とする通信網制御システム。
（付記５）
（付記４）記載の通信網制御システムであって、
前記順位情報算出手段は、障害が生じた隣接ノードが存在する場合に、再接続する全相手先候補ノードと、前記算出した順位情報を相互に交換する、ことを特徴とする通信網制御システム。
（付記６）
（付記１）乃至（付記５）のうちいずれか記載の通信網制御システムであって、
前記再接続先ノードから前記決定の情報を取得し、かつ、前記経路情報上における他ノードから前記決定の情報を取得しない場合、前記自ノードの決定情報算出手段で決定した再接続先ノードを再接続先として確定する決定情報比較手段を更に備える、ことを特徴とする通信網制御システム。
（付記７）
（付記６）記載の通信網制御システムであって、
前記決定情報比較手段は、隣接するノードに障害が生じ通信不可能となった場合に、その次ホップのノードを再接続先として再設定し、経路制御を行う、ことを特徴とする通信網制御システム。
（付記８）
（付記１）乃至（付記７）のうちいずれか記載の通信網制御システムであって、
前記経路情報算出手段により算出された経路情報及び前記順位情報算出手段により算出された順位情報のうち少なくとも一方を記憶する記憶手段を更に備える、ことを特徴とする通信網制御システム。
（付記９）
（付記１）乃至（付記８）のうちいずれか記載の通信網制御システムであって、
前記ノードは自律分散的に前記再接続を行う、ことを特徴とする通信網制御システム。
（付記１０）
（付記１）乃至（付記３）のうちいずれか記載の通信網制御システムであって、
前記複数のノードのうちの予め設定された代表ノードは、
前記経路情報算出手段、前記順位情報算出手段、及び前記決定情報算出手段を備え、
前記経路情報算出手段は、隣接ノードが故障した各ノード集合について、該ノード集合内の各ノードを起点とする最短経路情報を算出する、ことを特徴とする通信網制御システム。
（付記１１）
（付記１０）記載の通信網制御システムであって、
前記決定情報算出手段は、前記通信網内において前記ノードに障害が生じ通信不可能となった場合に、前記再接続先のノードとして決定した情報に基づいて再経路制御を行う、ことを特徴とする通信網制御システム。
（付記１２）
（付記１）乃至（付記１１）のうちいずれか記載の通信網制御システムであって、
前記通信網には、ラマヌジャングラフが適用されている、ことを特徴とする通信網制御システム。
（付記１３）
複数のノードを複数のリンク介して相互に接続された通信網内において、障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムの制御方法であって、
隣接ノードに障害が生じたときの前記通信網における経路情報を算出するステップと、
前記再接続する相手先候補ノードについて、前記算出された経路情報上の距離順に順位付けした順位情報を算出するステップと、
前記算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報の距離が大きくなるような組み合わせを算出し、該算出した組合せを自ノードの再接続先ノードとして決定するステップと、
を含む、ことを特徴とする通信網制御システムの制御方法。
（付記１４）
複数のノードを複数のリンク介して相互に接続された通信網内において、障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムの制御プログラムであって、
隣接ノードに障害が生じたときの前記通信網における経路情報を算出する処理と、
前記再接続する相手先候補ノードについて、前記算出された経路情報上の距離順に順位付けした順位情報を算出する処理と、
前記算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報の距離が大きくなるような組み合わせを算出し、該算出した組合せを自ノードの再接続先ノードとして決定する処理と、
をコンピュータに実行させる、ことを特徴とする通信網制御システムの制御プログラム。
【００６５】
この出願は、２０１３年１月８日に出願された日本出願特願２０１３−００１３０８を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００６６】
１    通信網制御システム
２    リンク
３    経路情報算出手段
４    順位情報算出手段
５    決定情報算出手段
１１    通信機能部
１２    経路情報計算部
１３    順位情報計算部
１４    決定情報計算部
１５    決定情報比較部
１６    記憶部
Ｇ    通信網
Ｎｉ    ノード
Ｎ０    代表ノード
Ｎｘ    故障・障害ノード
Ｎｊ，Ｎｋ，Ｎｌ    故障・障害ノードの隣接ノード
【図１】
2014108944.tif 000007
【図２】
2014108944.tif 000008
【図３】
2014108944.tif 000009
【図４】
2014108944.tif 000010
【図５】
2014108944.tif 000011
【図６】
2014108944.tif 000012
【図７】
2014108944.tif 000013
【図８】
2014108944.tif 000014
【図９】
2014108944.tif 000015
【手続補正書】
【提出日】平成27年6月11日(2015.6.11)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１４
【補正方法】変更
【補正の内容】
【請求項１４】
複数のノードを複数のリンク介して相互に接続された通信網内において、故障した、または障害を有する前記ノードを除去し、前記通信網の再接続を行う通信網制御システムの制御プログラムであって、
隣接ノードに障害が生じたときの前記通信網における経路情報を算出する処理と、
前記再接続する相手先候補ノードについて、前記算出された経路情報上のノード間距離順に順位付けした順位情報を算出する処理と、
前記算出された順位情報に基づいて、前記再接続後の通信網全体における経路情報のノード間距離が大きくなるような組み合わせを算出し、該算出した組み合わせを自ノードの再接続先ノードとして決定する処理と、
をコンピュータに実行させる、ことを特徴とする通信網制御システムの制御プログラム。
【国際調査報告】
2014108944.tif 000016
2014108944.tif 000017