(57)【特許請求の範囲】
【請求項１】
ノードOに接続する回線束部分と、前記回線束部分に束ねられ、複数のノードkに接続する複数の個別回線部分とを含むネットワークについて、前記回線束部分に関する経路候補である複数の回線束部分経路候補と、前記回線束部分経路候補ごと、かつ、前記ノードkごとに、前記個別回線部分に関する経路候補である複数の個別回線部分経路候補との入力を受け付ける入力部と、
前記回線束部分経路候補ごと、かつ、前記ノードｋごとに、当該回線束部分経路候補及び当該ノードｋに係る複数の個別回線部分経路候補に関する接続確率を評価し、前記接続確率の最小値を特定する接続確率最大化部と、
複数の前記回線束部分経路候補の中から、前記ノードｋごとに評価された前記最小値のうちの最大値、又は前記ノードｋごとに評価された前記最小値の和、が最小である回線束部分経路候補を選択する経路選択部と、
を有することを特徴とするネットワーク設計装置。
【請求項２】
ノードOに接続する回線束部分と、前記回線束部分に束ねられ、複数のノードkに接続する複数の個別回線部分とを含むネットワークについて、前記回線束部分に関する経路候補である複数の回線束部分経路候補と、前記回線束部分経路候補ごと、かつ、前記ノードkごとに、前記個別回線部分に関する経路候補である複数の個別回線部分経路候補との入力を受け付ける入力部と、
前記回線束部分経路候補ごと、かつ、前記ノードｋごとに、当該回線束部分経路候補及び当該ノードｋに係る複数の個別回線部分経路候補に関する凸集合の外周長を評価し、前記外周長の最小値を特定する接続確率最大化部と、
複数の前記回線束部分経路候補の中から、前記ノードｋごとに評価された前記最小値のうちの最大値、又は前記ノードｋごとに評価された前記最小値の和、が最小である回線束部分経路候補を選択する経路選択部と、
を有することを特徴とするネットワーク設計装置。
【請求項３】
ノードOに接続する回線束部分と、前記回線束部分に束ねられ、複数のノードkに接続する複数の個別回線部分とを含むネットワークについて、前記回線束部分に関する経路候補である複数の回線束部分経路候補と、前記回線束部分経路候補ごと、かつ、前記ノードkごとに、前記個別回線部分に関する経路候補である複数の個別回線部分経路候補との入力を受け付ける入力手順と、
前記回線束部分経路候補ごと、かつ、前記ノードｋごとに、当該回線束部分経路候補及び当該ノードｋに係る複数の個別回線部分経路候補に関する接続確率を評価し、前記接続確率の最小値を特定する接続確率最大化手順と、）
複数の前記回線束部分経路候補の中から、前記ノードｋごとに評価された前記最小値のうちの最大値、又は前記ノードｋごとに評価された前記最小値の和、が最小である回線束部分経路候補を選択する経路選択手順と、
をコンピュータが実行することを特徴とするネットワーク設計方法。
【請求項４】
ノードOに接続する回線束部分と、前記回線束部分に束ねられ、複数のノードkに接続する複数の個別回線部分とを含むネットワークについて、前記回線束部分に関する経路候補である複数の回線束部分経路候補と、前記回線束部分経路候補ごと、かつ、前記ノードkごとに、前記個別回線部分に関する経路候補である複数の個別回線部分経路候補との入力を受け付ける入力手順と、
前記回線束部分経路候補ごと、かつ、前記ノードｋごとに、当該回線束部分経路候補及び当該ノードｋに係る複数の個別回線部分経路候補に関する凸集合の外周長を評価し、前記外周長の最小値を特定する接続確率最大化手順と、
複数の前記回線束部分経路候補の中から、前記ノードｋごとに評価された前記最小値のうちの最大値、又は前記ノードｋごとに評価された前記最小値の和、が最小である回線束部分経路候補を選択する経路選択手順と、
をコンピュータが実行することを特徴とするネットワーク設計方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク設計装置及び方法に係り、特に、面的被災に対して頑健な物理媒体ネットワークを設計するためのネットワーク設計装置及び方法に関する。
【背景技術】
【０００２】
これまでは、ネットワークの信頼性は、主に、独立に生じる故障を前提として、あるノード間の接続確率が一定値以上となるよう、方策を講じることによって確保されてきた。しかしながら、面的被災によるネットワーク機能の喪失は、独立な故障という前提と大きく乖離するため、このような信頼性対策では不十分となる。信頼性工学においては、相関がある故障という概念によって、既存理論を高度化する試みもあるが、面的被災のような地理的概念によって、故障が生じ得るということまでは考慮できない。
【０００３】
一方、積分幾何によって、直線上に被災エリアが生じた場合に、２ノード間の接続確率を求めるアルゴリズムが示されている（例えば、非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】S. Neumayer and E. Modiano, Network Reliability With Geographically Correlated Failures, INFOCOM 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の非特許文献１の技術では、
（１）直線上の被災だけで、地震や津波に整合する面的被害になっていない；
（２）設計法にならない；
といった課題がある。
【０００６】
本発明は、上記の点に鑑みなされたもので、面的被災によるネットワーク機能の喪失時において、面的な被災に対応したモデルに基づいて、物理媒体の経路設計が可能なネットワーク設計装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
一態様によれば、面的被災時に対応可能なネットワーク設計装置であって、
ネットワーク上のノードO，ノードkの間が接続可能である確率（以下、「接続確率」と記す）の評価方法及び回線束部分経路候補と個別回線部分経路候補を含む物理媒体経路候補が入力されると、面的被災時に、前記ネットワーク上の前記ノードOと前記ノードｋの接続確率の最悪値、または、該接続確率の和を求め、経路候補と共に記憶手段に格納する接続確率最大化手段と、
前記記憶手段の前記経路候補から、前記接続確率の最悪値が最大となる、または、前記接続確率の和が最大となる経路を選択する経路選択手段と、を有するネットワーク設計装置が提供される。
【発明の効果】
【０００８】
一態様によれば、物理媒体経路を決めるネットワーク設計において、面的な被災に対応したモデルに基づいて、候補の経路の中から、ルートノードOとその他の各ノードk間の接続確率が最悪となるO−k間の接続確率が最良化するネットワーク設計が可能となる。
【図面の簡単な説明】
【０００９】
【図１】本発明の一実施の形態におけるネットワーク設計装置の構成例である。
【図２】被災エリアモデルである。
【図３】本発明の一実施の形態における回線束の例である。
【図４】本発明の一実施の形態における回線束経路候補と個別回線部分経路候補の例である。
【図５】本発明の一実施の形態におけるネットワーク設計装置の動作のフローチャートである。
【発明を実施するための形態】
【００１０】
以下、図面と共に本発明の実施の形態を説明する。
【００１１】
図１は、本発明の一実施の形態におけるネットワーク設計装置の構成を示す。
【００１２】
同図に示すネットワーク設計装置１００は、入力部１１０、接続確率最大化処理部１２０、経路・接続確率記憶部１３０、経路選択部１４０、出力部１５０を有する。
【００１３】
上記の各構成を説明する前に、背景となる理論を示す。なお、ある平面図形Xに対して｜X|をXの外周長、
【００１４】
【数１】
0005876860.tif 000002
をXのconvex hull（与えられた集合を含む最小の凸集合）とする。
【００１５】
凸領域のA0内に光ファイバケーブルなどの物理媒体ネットワークがあり、ネットワーク内の２つのノードi,j間に経路p(i,j)があるとし、ここに災害が生じたとする。被災エリアに含まれるネットワーク部分は、全て壊れるとする。被災エリアモデルを図２に示す。被災エリア境界は、幅ｗの帯状領域Bに含まれるとする。被災エリアをこの帯状領域Bと半平面RBの和集合である半平面で近似する。被災エリアはA0を含む平面上で、角度を含めてランダムに生じるとする。
【００１６】
このとき、積分幾何の解析により、式（1）を得る。
【００１７】
【数２】
0005876860.tif 000003
但し、
【００１８】
【数３】
0005876860.tif 000004
は、i，j間が接続可能であることを示す。式（1）は、被災エリアがA0に掛かる条件下で、i，jが接続可能である確率を与えている。そこで、ルートノードOとその他の各ノードｋ間のこの確率を最大化するネットワークを設計することにする。
【００１９】
式（１）から、この確率の最大化は、O−k間経路のconvex hullの外周長
【００２０】
【数４】
0005876860.tif 000005
を最小化すればよいことがわかる。そこで、本発明では、各kについて、O−k間経路のconvex hullの外周長を最小化するネットワークを設計することにする。
【００２１】
なお、
【００２２】
【数５】
0005876860.tif 000006
の代わりに、ルートノードOとその他の各ノードk間の接続確率をそのまま使ってもよい。
【００２３】
図１の入力部１１０には、パラメータとして、回線束経路候補、策定された個別回線経路候補を含む物理媒体経路候補、及び、確率の評価方法として、上記のノードi，j間の接続確率を求める式（１）が入力される。
【００２４】
物理媒体は、図３に示すように、回線束部分ａと個別回線部分ｂからなるとする。簡単のため、２段階構成としたが、多段階の構成でも本発明を同様に適用できる。図４に示すように、既存手法によりコスト等の条件を考慮して得られた回線束の経路候補（以下、「回線束部分経路候補」と記す）が１〜ｎまであり、同回線束部分経路候補ｉに対し、既存手法によりコスト等の条件を考慮して得られた個別回線ｋ（ノードｋ向けの回線）に関する個別回線部分経路候補集合をS(i,k)とする。
【００２５】
接続確率最大化処理部１２０は、各個別回線部分経路候補kについて、まず、ある回線束部分経路候補iを固定して、個別回線部分経路候補集合S(i,k)の各経路について、O−k間経路のconvex hullの外周長
【００２６】
【数６】
0005876860.tif 000007
を評価し、その最小値をf(i,k)とし、その時の経路をr(i,k)とし、当該最小値とr(i,k)を経路・接続確率記憶部１３０に格納する。
【００２７】
個別回線部分経路候補についての経路の選択は、他の個別回線に影響を与えないので、回線束部分経路候補iが採用される場合は、r(i,k)を採用すべきである。
【００２８】
経路選択部１４０は、回線束部分経路候補１〜ｎについて、max_k f(i,k)が最小となる経路を経路・接続確率記憶部１３０から選択する。ここで、max_k f(i,k)は、回線束部分経路候補iを採用時に、最悪となるノードkに対する
【００２９】
【数７】
0005876860.tif 000008
であるので、これが最小となるよう経路選択を行うものである。なお、max_k f(i,k)の代わりに、f(i,k)の和を最大化する
【００３０】
【数８】
0005876860.tif 000009
を用いることもできる。
【００３１】
出力部１５０は、経路選択部１４０で選択された経路を出力する。
【００３２】
図５は、本発明の一実施の形態におけるネットワーク設計装置の動作のフローチャートである。
【００３３】
入力部１１０は、策定された回線束経路候補と個別回線経路候補が入力されると、それらを接続確率最大化処理部１２０に渡す（ステップ１０１）。
【００３４】
接続確率最大化処理部１２０は、処理する回線束部分経路候補の処理対象カウンタiと、処理する個別回線部分経路候補の処理対象カウンタkを１に初期化する（ステップ１０２，１０３）。
【００３５】
接続確率最大化処理部１２０は、上記の
【００３６】
【数９】
0005876860.tif 000010
を評価し、その最小値f(i,k)と、その時の経路r(i,k)を経路・接続確率記憶部１３０に格納する（ステップ１０４）。
【００３７】
全ての個別回線部分経路候補ｋについてステップ１０４の処理を行った場合は（ステップ１０５,Yes）、ステップ１０７に移行し、未処理の個別回線部分経路候補ｋがある場合には（ステップ１０５,No）、kの値をk=k+1とし（ステップ１０６）、ステップ１０４に戻る。
【００３８】
全ての回線束部分経路候補ｉについての処理が終わった場合には（ステップ１０７,Yes）、ステップ１０９に移行し、未処理の回線束部分経路候補iがある場合には（ステップ１０７,No）、iの値をi=i+1とし（ステップ１０８）、ステップ１０３に戻る。
【００３９】
経路選択部１４０は、経路・接続確率記憶部１３０から、最悪値の最大値max_k f(i,k)となる経路iを選択し、経路i_optと名付けて、当該経路i_optと、経路・接続確率記憶部１３０に保持している経路r(i,k)の中でi=i_optとなる個別回線部分経路候補r(i_opt,k)(k=1,2,…)を経路・接続確率記憶部１３０に格納する（ステップ１０９）。
【００４０】
出力部１５０は、経路・接続確率記憶部１３０からi_optとr(i_opt,k)を読み出して出力する（ステップ１１０）。
【００４１】
また、ルートノードOとその他の各ノードk間の経路のconvex hullの外周長が最小となる経路を選択することも可能である。O，k間の経路のconvex hullの外周長を最小化する際には、全個別回線部分経路候補及び全回線束部分経路候補について、経路のconvex hullの外周長を経路・接続確率記憶部１３０に保持しておき、接続確率最大化処理部１２０は、経路のconvex hullの外周長の最大値の最小化する。
【００４２】
なお、上記の図１に示すネットワーク設計装置の各構成要素の動作をプログラムとして構築し、ネットワーク設計装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【符号の説明】
【００４３】
１００  ネットワーク設計装置
１１０  入力部
１２０  接続確率最大化処理部
１３０  経路・接続確率記憶部
１４０  経路選択部
１５０  出力部
【図１】
0005876860.tif 000011
【図２】
0005876860.tif 000012
【図３】
0005876860.tif 000013
【図４】
0005876860.tif 000014
【図５】
0005876860.tif 000015