ネットワーク設計方法及びプログラム
【課題】 故障時にも代替経路を利用して通信が継続できるようなNW設計方法において、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化したネットワーク設計を可能にする。
【解決手段】 本発明は、次数（ノードに接続するリンク数）制約を満たす全域木を構成し、次に、全域木に辺を付加することで直径を抑えたグラフを出力し、最後に経路長増加率を抑えるように辺を付加することにより、リンクを設置可能な位置集合、ノード次数の制約上の上限値、トポロジの直径の制約上限値、単一リンク障害時の経路長増加率の最大値の制約条件値を入力とした場合に、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化するようにネットワークを設計できる。
【解決手段】 本発明は、次数（ノードに接続するリンク数）制約を満たす全域木を構成し、次に、全域木に辺を付加することで直径を抑えたグラフを出力し、最後に経路長増加率を抑えるように辺を付加することにより、リンクを設置可能な位置集合、ノード次数の制約上の上限値、トポロジの直径の制約上限値、単一リンク障害時の経路長増加率の最大値の制約条件値を入力とした場合に、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化するようにネットワークを設計できる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク設計方法及びプログラムに係り、特に、故障時（単一リンク故障時）にも代替経路を利用して通信が継続できるようなネットワークを設計するためのネットワーク設計方法及びプログラムに関する。
【０００２】
詳しくは、リンクを設置可能な位置の集合E、ノード次数の制約上限値δ、トポロジの直径の制約上限値D、単一リンク障害(SLF: single link failure)時の経路長増加率の最大値の制約条件値Kが与えられたときにノード次数とトポロジ直径の制約上限を満たす条件の元で設置するリンク数を最小化するようネットワークトポロジを設計するネットワーク設計方法及びプログラムに関する。
【背景技術】
【０００３】
インターネットをはじめ、通信ネットワーク（以下、「NW」と記す)が社会において必要不可欠なインフラとなった現在、NWには高い信頼性が求められている。しかし、特に大規模なNWでは、様々な要因によるノードやリンクの故障や重い輻輳の発生は避けられないため、そのような障害が発生しても各ノード間の通信を維持し続けるための設計及び制御が必要である。
【０００４】
この観点から、障害時にも代替経路を利用して通信が継続できるようにすることを目的とした、高連結度NW設計に関する研究がある。例えば、同時に故障するリンクは一つだけとする単一リンク故障(SLF)を仮定し、SLF時にも通信が途絶しないために、NWを２辺連結グラフとなるように設計することは、実際にも一般的に行われている。このように、インターネットサービスプロバイダ（以下、「ISP」と記す）のNWトポロジを、高い連結度のグラフとなるように構成することによって高い信頼性を得ることは可能である。
【０００５】
しかし、障害時に通常時の経路から代替経路に変化した際に経路長が大きく延びてしまう可能性があり、影響を受ける膨大な数の通信すべてにおいて通信品質の劣化を引き起こす可能性があることが指摘されている。また、代替経路に切り替わることでトラフィックの流れが変化し、代替経路上で輻輳を起こす可能性がある。これは代替経路の経路長が大幅に増えることで、その可能性がより高くなることが考えられる。したがって、実際のNWトポロジには、単に代替経路が存在するだけではなく、SLF時の経路長増加率が小さいことも必要である。
【０００６】
インターネットにおいては、経路を自由に決定することはできず、OSPF(Open shortest Path First)などルーティングプロトコルによって決定されるため、経路を適切に定めることで経路長増加率を設定するという方法を取ることはできない。したがって、NWトポロジを適切に決定することによって経路長増加率を設定しなければならない。この経路長増加率が小さければ、障害が発生した際も、すべてのノード間に代替経路が存在し、その経路長が大幅に大きくなることはない。このことから、限られたコストで故障時経路長増加率が必要な値以下のNWを構築することがNW設計の目的となる。
【０００７】
これまで、発明者らによって、既存NWに最小限の増設を行うことで条件を満たすネットワーク増設設計法を提案し、その有効性を示した（例えば、非特許文献１参照）。しかし、新規にネットワークを構築する必要がある場合、この方法をそのまま適用することができないため、新規NW設計法が必要である。その際、考慮すべきことは増設設計の場合とは異なり、通常時の通信品質も考慮しなければならない。例えば、コスト最小化のためにリンク数の少ないNWを設計するというだけでは、直径が大きく延びてしまう可能性がある。実際、経路長増加率とリンク数を抑えるだけでは、経路長増加率が定められた値以下になる閉路を直列につなぐだけで最適なNWとなるが、これでは直径が大きいため、通常時においても通信遅延の大きいノード間が現われてしまう。しかし、スター状のグラフの葉を閉路でつないだ車輪グラフであれば、経路長増加率も直径も抑えられるが、中心のノードの次数が大きくなり、ノード負荷が高くなる可能性が増す。したがって、経路長増加率に加えて、直径と次数の両者を抑えたリンク数の少ないNWを設計する必要がある。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】片山、藤村、巳波、上山、長谷川、吉野、 "故障時における性能劣化を抑制するネットワーク設計法、" 信学技報NS2008-164
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上記の従来の技術の問題を解決する手法として、直径と次数を抑えた辺数の少ないグラフとして、ムーアグラフが知られているが、ムーアグラフであることが分かっているのは、限られた条件の組に対してのみである。ムーアグラフに近いグラフ構造として、de BruijnグラフやKautzグラフが知られている。これは任意の条件に対してそれを満たすグラフの構成が可能である。しかし、さらに任意の経路長増加率を満たすような構成法はない。また、任意の点対間に辺を張れることを仮定しなければならず、現実的には適用することが難しい。
【００１０】
予めリンクを張れるノード対間が指定されている状況の下で、条件を満たすネットワークを構成するタイプの問題も多い。これは、リンク候補点対を辺集合とするグラフにおいて、全域部分グラフを求めることに対応する。全域部分グラフの辺が実際にリンクが張られるノード対間になる。したがって、グラフにおいて条件を満たす辺数最小の全域部分グラフを求める問題として定式化される。しかし、いずれも経路長増加率に関しては扱われていない。
【００１１】
本発明は、上記の点に鑑みなされたもので、故障時にも代替経路を利用して通信が継続できるようなNW設計方法において、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化したネットワーク設計が可能なネットワーク設計方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の問題を解決するために、本発明（請求項１）は、単一リンク障害(SLF: single link failure)時の品質劣化基準を満たすリンク数を最小化するためのネットワーク設計方法であって、
入力手段、記憶手段、リンク設置箇所選択手段と、を有する装置において、
入力手段が、ノード集合Ｖ、リンクを設置可能な位置の集合Ｅ、ノード次数（ノードに接続するリンク数）の制約上限値δ、トポロジの直径（ノード間距離の最大値）の制約上限値Ｄ、単一リンク障害時の経路長増加率（元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比）の最大値の制約条件値Ｋ、が与えられると、記憶手段に格納する入力過程と、
リンク設置箇所選択手段は、記憶手段から入力されたデータを読み込んで、ノード次数δとトポロジ直径の制約上限Ｄを満たす条件の元で、設置するリンク数を最小化するようネットワークトポロジを設計する設計過程と、を行う。
【００１３】
また、本発明（請求項２）は、設計過程において、
最初に次数制約を満たすよう全域木を構成し、次に、直径制約と次数制約を満たすようリンクを付加し、最後にSLF時の最大経路長増加率の制約条件を満たすよう最小数のリンクを付加する。
【００１４】
また、本発明（請求項３）は、設計過程において、
次数制約を２以上δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する。
【００１５】
また、本発明（請求項４）は、請求項１乃至３のいずれか１項に記載のネットワーク設計方法の各過程としてコンピュータを機能させるためのネットワーク設計プログラムである。
【発明の効果】
【００１６】
上記のように、本発明によれば、リンクを設置可能な位置の集合Ｅ、ノード次数の制約上限値δ、トポロジの直径の制約上限値Ｄ、ＳＬＦ時の経路長増加率の最大値の制約条件値Ｋ、が与えられたときに、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化するよう、ネットワークトポロジを設計することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施の形態におけるネットワーク設計装置の構成図である。
【図２】本発明の一実施の形態で用いられるアルゴリズムSIRPLの処理フローである。
【図３】本発明の一実施の形態におけるアルゴリズムCreateNetworkの処理フローである。
【図４】本発明の一実施の形態における関数i-Tree(i)の処理フローである。
【図５】本発明の一実施の形態における関数Control Diameterの処理フローである。
【図６】本発明の一実施の形態における処理結果の例（その１）である。
【図７】本発明の一実施の形態における処理結果の例（その２）である。
【図８】辺付加後のネットワークと新規編成されたネットワークの各値を示す図（その１）である。
【図９】辺付加後のネットワークと新規編成されたネットワークの各値を示す図（その１）である。
【発明を実施するための形態】
【００１８】
以下図面と共に、本発明の実施の形態を説明する。
【００１９】
図１は、本発明の一実施の形態におけるNW設計装置の構成を示す。
【００２０】
同図に示すNW設計装置は、メモリ１０、入力部１０１、リンク設置箇所選択部１０２、リンク設置箇所出力部１０３から構成される。
【００２１】
入力部１０１は、ノード集合V、リンク設置可能位置集合E、ノード次数（ノードに接続するリンク数）の制約上限値δ、トポロジの直径（ノード間距離の最大値）の制約上限値D、SLF時の最大フロー長増加率(元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比の最大値)の制約上限値K、を入力し、メモリ１０に格納する。
【００２２】
リンク設置箇所選択部１０２は、メモリ１０から上記の入力された値を読み込み、ノード次数の制約上限値δとトポロジを直径の制約上限値Dを満たす条件の下で、設置するリンク数を最小化するようにネットワークトポロジを設計し、メモリ１０に格納する。
【００２３】
詳しくは、設置するリンク数を最小化するために、
（１）最初に次数制約を満たすよう全域木を構成する。
【００２４】
（２）次に、直径制約Ｄと次数制約δを満たすようリンクを付加する。
【００２５】
（３）最後にSLF時の最大経路長増加率の制約条件Ｋを満たすよう最小数のリンクを付加する。このとき、次数制約を２以上δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する。
【００２６】
リンク設置箇所出力部１０３は、メモリ１０からリンク設置箇所情報を読み込んで出力する。
【００２７】
次に、本発明の実施の形態に係るリンク設置箇所選択部１０２における、単一リンク障害時の品質劣化基準を満たすリンク数最小ネットワーク設計法について、詳細を説明する。
【００２８】
［１］定式化
リンク設置箇所選択部１０２は、まず、本発明で扱うネットワーク設計問題を定式化する。
【００２９】
本実施の形態では、次数(ノードに接続するリンク数)制約を満たす全域木をまず構成し、それに辺を付加することで直径を抑えて得られるグラフに、経路長増加率を抑えるように辺を付加するアルゴリズムを適用する。次数制約を満たす全域木を求めることは一般にはNP完全であるが、近似アルゴリズムが存在する。グラフの直径を抑えるように付加リンクを決定する問題もNP完全であるが、こちらには有効な近似アルゴリズムはまだ知られていない。そのため、ここでは、全域木において直径制約を満たさない距離の点対間に辺を付加することを繰り返すことにより直径を小さくする。
【００３０】
新規ネットワーク設計アルゴリズム"CreateNetwork"は、次のアルゴリズム"SIRPL"をサブルーチンとして包含する。アルゴリズム"SIRPL"は次数制約・経路長増加率制約の下で辺を付加するアルゴリズムである。グラフＧにおいて、辺ｅ∈ＥのSLFによる経路長増加率がＫ以下の辺を「充足辺」と呼び、さもなければ「未充足辺」と呼ぶ。未充足辺集合をＵとする。また、
【００３１】
【数１】
を付加することで1辺以上の未充足辺を充足辺にできるとき、辺ｆを「候補辺」と呼び、ｆによって充足辺にできる未充足辺の集合をＳfとする。付加可能点対集合に候補辺集合が含まれると仮定する。また、付加辺は候補辺からのみ選ぶものとする。
【００３２】
以下に、アルゴリズムSIRPLを示す。図２は、本発明の一実施の形態で用いられるアルゴリズムSIRPLの処理フローを示す。
【００３３】
ステップ２０１） リンク設置箇所選択部１０２によりアルゴリズムSIRPLが起動されると、未充足辺集合Ｕ、候補辺集合Ｓ＝｛Ｓ１；Ｓ２；：：：；Ｓｆ；：：：Ｓｈ｝候補辺の各辺ｆによって充足できる未充足辺集合Ｓfを求める。
【００３４】
ステップ２０２） 集合Ｃを０とする（Ｃ＝０）。
【００３５】
ステップ２０３） 未充足辺集合Ｕが空集合である場合は、集合Ｃを出力して処理を終了する。空集合でない場合はステップ２０４に移行する。
【００３６】
ステップ２０４） 候補辺ｆを付加することによって、ｆの両端点の次数がｉを超えないという条件を満たすｆの中で、
｜Ｓf∩Ｕ｜
が最大となるSfを選ぶ。
【００３７】
ステップ２０５） 未充足辺集合ＵをＵ−Ｓfとし、集合ＣをＣＵ｛Ｓｆ｝とする。
【００３８】
ステップ２０６） 集合Ｃを出力する。
【００３９】
ここで得られた集合Ｃは、次数ｉ以下という条件の下で、経路長増加率がＫ以下になるように付加する辺集合である。
【００４０】
なお、上記アルゴリズムSIRPLにおいては、付加辺を選択する際、最大数の未充足辺を充足するような辺を付加辺として選ぶことを反復することにより、付加辺数の抑制を図っている。各候補辺ｆによって充足できる未充足辺集合Ｓfを求め、未充足辺集合ＵとＳf積集合が最大となるｆに対して、ＵからＳfを引き、充足辺集合ＣにＳfを加える。
【００４１】
次に、新規ネットワーク設計アルゴリズムCreateNetworkを以下に挙げる。
【００４２】
図３は、本発明の一実施の形態におけるアルゴリズムCreateNetworkの処理フローを示す。同図のフローにおいて、ステップ３０３，３０４の関数i-Treeは、最大次数ｉの全体木を求めるものであり、その処理フローを図４に示す。同図において関数i-Treeは、点ｒを根とする木Ｔを生成し、根ｒからの距離が最も小さい葉の点ｖを一つ選択し、ｖの隣接点のうちＴに含まれないものからｉ個以下の点を選んでｖの子ノードとし、それらをＴに加える処理をＴが全体木となるまで繰り返す。
【００４３】
ステップ３０５の関数ControlDiameterは、次数ｉ以下という条件の下で、直径がＤ以下になるように辺を付加するものであり、当該関数ControlDiameterの処理フローを図５に示す。ステップ３０６のSIRPLは、上で挙げた経路長増加率制約と次数制約を満たす辺付加アルゴリズムである。ステップ３０７において、以上の処理で得られた辺をすべてＥ´とし、ｉを１インクリメントし、ステップ３０１に移行する。ステップ３０９では、すべてのｉに対してこのようにしてグラフＧi´＝（Ｖ：Ｅi´）を構成し、その中で辺数が最も少ないグラフをメモリ１０に出力する。
【００４４】
なお、Ｇが完全グラフ、つまりどのノード間にもリンクが張れる場合、i-Tree（i）はｉ分木を構成する。ControlDeameter(ｉ, D)に関しては、ここでは、距離が最大である２点間に辺を付加することを直径がD以下になるまで反復するという単純なものを用いる。
【００４５】
図６、図７にCAIDAで公開されているＮＷに本アルゴリズムを適用した場合の処理結果の例を示す。図６は、CAIDA(Cooperative Association for Internet Data Analysis)で公開されているISPバックボーンネットワークを対象としたものであり、各ネットワークにおいて、１行目は元のネットワークの情報であり、２行目は元のネットワークの経路長増加率が４になるように辺付加したものであり、３行目は元のネットワークと同じ点数であって、最大次数と直径が２行目のものを超えないように設計した新規ネットワークを示している。
【００４６】
図７（ａ）は、元のＮＷであり、点数＝４６、辺数＝５５、最大次数＝５、直径＝１３としたものであり、同図（ｂ）は、辺を付加した後の元のＮＷであり、点数＝４６、辺数＝６７、最大次数＝７、直径＝８、経路長増加率＝４としたものである。同図（ｃ）は新規に生成されたＮＷであり、点数＝４６、辺数＝６０、最大次数＝６、直径＝８、経路長増加率＝４としたものである。
【００４７】
図６、図７から、本発明のアルゴリズムCreateNetworkを用いることにより、ＮＷの最大次数、直径、経路長増加率は元のＮＷに辺を付加した後のＮＷのものと尾同じかそれ以下であり、さらに、より少ないリンク数であることがわかる。
【００４８】
（２）性能評価
以下に、本発明の有効性の評価を示す。
【００４９】
ここでは、CAIDAにおいて公開されている３９個の実際のISPバックボーンNWのグラフ構造を利用した。以下では簡単のために、任意のノード間にリンク敷設可能とする。また最大次数δ、直径Ｄ、経路長増加率Ｋの値は、要求されたＫの値を満たすように、SIRPLを用いて辺付加した後のNWにおける値を用いることにした。
【００５０】
図８と図９に、元のNW、辺付加後のNW（Ａ）、点集合から生成されたNW（Ｂ）に対する点数・辺数・最大次数・直径及び経路長増加率を示す。図８、図９中のISP列のＡは、各ISPのNWへ辺付加後のNW、ＢはCreateNetworkによって生成されたNWを表している。また、経路長増加率列の"−"は経路長が無限大（元のNWに閉路が存在せず、故障時に代替経路が存在しない）を表している。
【００５１】
アルゴリズムCreateNetworkを用いて得られたNWの最大次数・直径・経路長増加率は、元のNWに辺付加後のNWのものと同じかそれ以下であり、さらにより少ないリンク数であることがわかる。つまり、元のNWと同じノード数のNWを新たに作る場合、アルゴリズムCreateNetworkを用いることで、信頼性や性能が同レベル以上のNWを、より小さなコストで構成することができることを意味している。
【００５２】
なお、上記のリンク設置箇所選択部１０２の処理をプログラムとして構築し、ネットワーク設計装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５３】
また、構築されたプログラムをハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００５４】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５５】
１０ メモリ
１０１ 入力部
１０２ リンク設置箇所選択部
１０３ リンク設置箇所出力部
【技術分野】
【０００１】
本発明は、ネットワーク設計方法及びプログラムに係り、特に、故障時（単一リンク故障時）にも代替経路を利用して通信が継続できるようなネットワークを設計するためのネットワーク設計方法及びプログラムに関する。
【０００２】
詳しくは、リンクを設置可能な位置の集合E、ノード次数の制約上限値δ、トポロジの直径の制約上限値D、単一リンク障害(SLF: single link failure)時の経路長増加率の最大値の制約条件値Kが与えられたときにノード次数とトポロジ直径の制約上限を満たす条件の元で設置するリンク数を最小化するようネットワークトポロジを設計するネットワーク設計方法及びプログラムに関する。
【背景技術】
【０００３】
インターネットをはじめ、通信ネットワーク（以下、「NW」と記す)が社会において必要不可欠なインフラとなった現在、NWには高い信頼性が求められている。しかし、特に大規模なNWでは、様々な要因によるノードやリンクの故障や重い輻輳の発生は避けられないため、そのような障害が発生しても各ノード間の通信を維持し続けるための設計及び制御が必要である。
【０００４】
この観点から、障害時にも代替経路を利用して通信が継続できるようにすることを目的とした、高連結度NW設計に関する研究がある。例えば、同時に故障するリンクは一つだけとする単一リンク故障(SLF)を仮定し、SLF時にも通信が途絶しないために、NWを２辺連結グラフとなるように設計することは、実際にも一般的に行われている。このように、インターネットサービスプロバイダ（以下、「ISP」と記す）のNWトポロジを、高い連結度のグラフとなるように構成することによって高い信頼性を得ることは可能である。
【０００５】
しかし、障害時に通常時の経路から代替経路に変化した際に経路長が大きく延びてしまう可能性があり、影響を受ける膨大な数の通信すべてにおいて通信品質の劣化を引き起こす可能性があることが指摘されている。また、代替経路に切り替わることでトラフィックの流れが変化し、代替経路上で輻輳を起こす可能性がある。これは代替経路の経路長が大幅に増えることで、その可能性がより高くなることが考えられる。したがって、実際のNWトポロジには、単に代替経路が存在するだけではなく、SLF時の経路長増加率が小さいことも必要である。
【０００６】
インターネットにおいては、経路を自由に決定することはできず、OSPF(Open shortest Path First)などルーティングプロトコルによって決定されるため、経路を適切に定めることで経路長増加率を設定するという方法を取ることはできない。したがって、NWトポロジを適切に決定することによって経路長増加率を設定しなければならない。この経路長増加率が小さければ、障害が発生した際も、すべてのノード間に代替経路が存在し、その経路長が大幅に大きくなることはない。このことから、限られたコストで故障時経路長増加率が必要な値以下のNWを構築することがNW設計の目的となる。
【０００７】
これまで、発明者らによって、既存NWに最小限の増設を行うことで条件を満たすネットワーク増設設計法を提案し、その有効性を示した（例えば、非特許文献１参照）。しかし、新規にネットワークを構築する必要がある場合、この方法をそのまま適用することができないため、新規NW設計法が必要である。その際、考慮すべきことは増設設計の場合とは異なり、通常時の通信品質も考慮しなければならない。例えば、コスト最小化のためにリンク数の少ないNWを設計するというだけでは、直径が大きく延びてしまう可能性がある。実際、経路長増加率とリンク数を抑えるだけでは、経路長増加率が定められた値以下になる閉路を直列につなぐだけで最適なNWとなるが、これでは直径が大きいため、通常時においても通信遅延の大きいノード間が現われてしまう。しかし、スター状のグラフの葉を閉路でつないだ車輪グラフであれば、経路長増加率も直径も抑えられるが、中心のノードの次数が大きくなり、ノード負荷が高くなる可能性が増す。したがって、経路長増加率に加えて、直径と次数の両者を抑えたリンク数の少ないNWを設計する必要がある。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】片山、藤村、巳波、上山、長谷川、吉野、 "故障時における性能劣化を抑制するネットワーク設計法、" 信学技報NS2008-164
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上記の従来の技術の問題を解決する手法として、直径と次数を抑えた辺数の少ないグラフとして、ムーアグラフが知られているが、ムーアグラフであることが分かっているのは、限られた条件の組に対してのみである。ムーアグラフに近いグラフ構造として、de BruijnグラフやKautzグラフが知られている。これは任意の条件に対してそれを満たすグラフの構成が可能である。しかし、さらに任意の経路長増加率を満たすような構成法はない。また、任意の点対間に辺を張れることを仮定しなければならず、現実的には適用することが難しい。
【００１０】
予めリンクを張れるノード対間が指定されている状況の下で、条件を満たすネットワークを構成するタイプの問題も多い。これは、リンク候補点対を辺集合とするグラフにおいて、全域部分グラフを求めることに対応する。全域部分グラフの辺が実際にリンクが張られるノード対間になる。したがって、グラフにおいて条件を満たす辺数最小の全域部分グラフを求める問題として定式化される。しかし、いずれも経路長増加率に関しては扱われていない。
【００１１】
本発明は、上記の点に鑑みなされたもので、故障時にも代替経路を利用して通信が継続できるようなNW設計方法において、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化したネットワーク設計が可能なネットワーク設計方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の問題を解決するために、本発明（請求項１）は、単一リンク障害(SLF: single link failure)時の品質劣化基準を満たすリンク数を最小化するためのネットワーク設計方法であって、
入力手段、記憶手段、リンク設置箇所選択手段と、を有する装置において、
入力手段が、ノード集合Ｖ、リンクを設置可能な位置の集合Ｅ、ノード次数（ノードに接続するリンク数）の制約上限値δ、トポロジの直径（ノード間距離の最大値）の制約上限値Ｄ、単一リンク障害時の経路長増加率（元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比）の最大値の制約条件値Ｋ、が与えられると、記憶手段に格納する入力過程と、
リンク設置箇所選択手段は、記憶手段から入力されたデータを読み込んで、ノード次数δとトポロジ直径の制約上限Ｄを満たす条件の元で、設置するリンク数を最小化するようネットワークトポロジを設計する設計過程と、を行う。
【００１３】
また、本発明（請求項２）は、設計過程において、
最初に次数制約を満たすよう全域木を構成し、次に、直径制約と次数制約を満たすようリンクを付加し、最後にSLF時の最大経路長増加率の制約条件を満たすよう最小数のリンクを付加する。
【００１４】
また、本発明（請求項３）は、設計過程において、
次数制約を２以上δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する。
【００１５】
また、本発明（請求項４）は、請求項１乃至３のいずれか１項に記載のネットワーク設計方法の各過程としてコンピュータを機能させるためのネットワーク設計プログラムである。
【発明の効果】
【００１６】
上記のように、本発明によれば、リンクを設置可能な位置の集合Ｅ、ノード次数の制約上限値δ、トポロジの直径の制約上限値Ｄ、ＳＬＦ時の経路長増加率の最大値の制約条件値Ｋ、が与えられたときに、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化するよう、ネットワークトポロジを設計することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施の形態におけるネットワーク設計装置の構成図である。
【図２】本発明の一実施の形態で用いられるアルゴリズムSIRPLの処理フローである。
【図３】本発明の一実施の形態におけるアルゴリズムCreateNetworkの処理フローである。
【図４】本発明の一実施の形態における関数i-Tree(i)の処理フローである。
【図５】本発明の一実施の形態における関数Control Diameterの処理フローである。
【図６】本発明の一実施の形態における処理結果の例（その１）である。
【図７】本発明の一実施の形態における処理結果の例（その２）である。
【図８】辺付加後のネットワークと新規編成されたネットワークの各値を示す図（その１）である。
【図９】辺付加後のネットワークと新規編成されたネットワークの各値を示す図（その１）である。
【発明を実施するための形態】
【００１８】
以下図面と共に、本発明の実施の形態を説明する。
【００１９】
図１は、本発明の一実施の形態におけるNW設計装置の構成を示す。
【００２０】
同図に示すNW設計装置は、メモリ１０、入力部１０１、リンク設置箇所選択部１０２、リンク設置箇所出力部１０３から構成される。
【００２１】
入力部１０１は、ノード集合V、リンク設置可能位置集合E、ノード次数（ノードに接続するリンク数）の制約上限値δ、トポロジの直径（ノード間距離の最大値）の制約上限値D、SLF時の最大フロー長増加率(元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比の最大値)の制約上限値K、を入力し、メモリ１０に格納する。
【００２２】
リンク設置箇所選択部１０２は、メモリ１０から上記の入力された値を読み込み、ノード次数の制約上限値δとトポロジを直径の制約上限値Dを満たす条件の下で、設置するリンク数を最小化するようにネットワークトポロジを設計し、メモリ１０に格納する。
【００２３】
詳しくは、設置するリンク数を最小化するために、
（１）最初に次数制約を満たすよう全域木を構成する。
【００２４】
（２）次に、直径制約Ｄと次数制約δを満たすようリンクを付加する。
【００２５】
（３）最後にSLF時の最大経路長増加率の制約条件Ｋを満たすよう最小数のリンクを付加する。このとき、次数制約を２以上δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する。
【００２６】
リンク設置箇所出力部１０３は、メモリ１０からリンク設置箇所情報を読み込んで出力する。
【００２７】
次に、本発明の実施の形態に係るリンク設置箇所選択部１０２における、単一リンク障害時の品質劣化基準を満たすリンク数最小ネットワーク設計法について、詳細を説明する。
【００２８】
［１］定式化
リンク設置箇所選択部１０２は、まず、本発明で扱うネットワーク設計問題を定式化する。
【００２９】
本実施の形態では、次数(ノードに接続するリンク数)制約を満たす全域木をまず構成し、それに辺を付加することで直径を抑えて得られるグラフに、経路長増加率を抑えるように辺を付加するアルゴリズムを適用する。次数制約を満たす全域木を求めることは一般にはNP完全であるが、近似アルゴリズムが存在する。グラフの直径を抑えるように付加リンクを決定する問題もNP完全であるが、こちらには有効な近似アルゴリズムはまだ知られていない。そのため、ここでは、全域木において直径制約を満たさない距離の点対間に辺を付加することを繰り返すことにより直径を小さくする。
【００３０】
新規ネットワーク設計アルゴリズム"CreateNetwork"は、次のアルゴリズム"SIRPL"をサブルーチンとして包含する。アルゴリズム"SIRPL"は次数制約・経路長増加率制約の下で辺を付加するアルゴリズムである。グラフＧにおいて、辺ｅ∈ＥのSLFによる経路長増加率がＫ以下の辺を「充足辺」と呼び、さもなければ「未充足辺」と呼ぶ。未充足辺集合をＵとする。また、
【００３１】
【数１】
を付加することで1辺以上の未充足辺を充足辺にできるとき、辺ｆを「候補辺」と呼び、ｆによって充足辺にできる未充足辺の集合をＳfとする。付加可能点対集合に候補辺集合が含まれると仮定する。また、付加辺は候補辺からのみ選ぶものとする。
【００３２】
以下に、アルゴリズムSIRPLを示す。図２は、本発明の一実施の形態で用いられるアルゴリズムSIRPLの処理フローを示す。
【００３３】
ステップ２０１） リンク設置箇所選択部１０２によりアルゴリズムSIRPLが起動されると、未充足辺集合Ｕ、候補辺集合Ｓ＝｛Ｓ１；Ｓ２；：：：；Ｓｆ；：：：Ｓｈ｝候補辺の各辺ｆによって充足できる未充足辺集合Ｓfを求める。
【００３４】
ステップ２０２） 集合Ｃを０とする（Ｃ＝０）。
【００３５】
ステップ２０３） 未充足辺集合Ｕが空集合である場合は、集合Ｃを出力して処理を終了する。空集合でない場合はステップ２０４に移行する。
【００３６】
ステップ２０４） 候補辺ｆを付加することによって、ｆの両端点の次数がｉを超えないという条件を満たすｆの中で、
｜Ｓf∩Ｕ｜
が最大となるSfを選ぶ。
【００３７】
ステップ２０５） 未充足辺集合ＵをＵ−Ｓfとし、集合ＣをＣＵ｛Ｓｆ｝とする。
【００３８】
ステップ２０６） 集合Ｃを出力する。
【００３９】
ここで得られた集合Ｃは、次数ｉ以下という条件の下で、経路長増加率がＫ以下になるように付加する辺集合である。
【００４０】
なお、上記アルゴリズムSIRPLにおいては、付加辺を選択する際、最大数の未充足辺を充足するような辺を付加辺として選ぶことを反復することにより、付加辺数の抑制を図っている。各候補辺ｆによって充足できる未充足辺集合Ｓfを求め、未充足辺集合ＵとＳf積集合が最大となるｆに対して、ＵからＳfを引き、充足辺集合ＣにＳfを加える。
【００４１】
次に、新規ネットワーク設計アルゴリズムCreateNetworkを以下に挙げる。
【００４２】
図３は、本発明の一実施の形態におけるアルゴリズムCreateNetworkの処理フローを示す。同図のフローにおいて、ステップ３０３，３０４の関数i-Treeは、最大次数ｉの全体木を求めるものであり、その処理フローを図４に示す。同図において関数i-Treeは、点ｒを根とする木Ｔを生成し、根ｒからの距離が最も小さい葉の点ｖを一つ選択し、ｖの隣接点のうちＴに含まれないものからｉ個以下の点を選んでｖの子ノードとし、それらをＴに加える処理をＴが全体木となるまで繰り返す。
【００４３】
ステップ３０５の関数ControlDiameterは、次数ｉ以下という条件の下で、直径がＤ以下になるように辺を付加するものであり、当該関数ControlDiameterの処理フローを図５に示す。ステップ３０６のSIRPLは、上で挙げた経路長増加率制約と次数制約を満たす辺付加アルゴリズムである。ステップ３０７において、以上の処理で得られた辺をすべてＥ´とし、ｉを１インクリメントし、ステップ３０１に移行する。ステップ３０９では、すべてのｉに対してこのようにしてグラフＧi´＝（Ｖ：Ｅi´）を構成し、その中で辺数が最も少ないグラフをメモリ１０に出力する。
【００４４】
なお、Ｇが完全グラフ、つまりどのノード間にもリンクが張れる場合、i-Tree（i）はｉ分木を構成する。ControlDeameter(ｉ, D)に関しては、ここでは、距離が最大である２点間に辺を付加することを直径がD以下になるまで反復するという単純なものを用いる。
【００４５】
図６、図７にCAIDAで公開されているＮＷに本アルゴリズムを適用した場合の処理結果の例を示す。図６は、CAIDA(Cooperative Association for Internet Data Analysis)で公開されているISPバックボーンネットワークを対象としたものであり、各ネットワークにおいて、１行目は元のネットワークの情報であり、２行目は元のネットワークの経路長増加率が４になるように辺付加したものであり、３行目は元のネットワークと同じ点数であって、最大次数と直径が２行目のものを超えないように設計した新規ネットワークを示している。
【００４６】
図７（ａ）は、元のＮＷであり、点数＝４６、辺数＝５５、最大次数＝５、直径＝１３としたものであり、同図（ｂ）は、辺を付加した後の元のＮＷであり、点数＝４６、辺数＝６７、最大次数＝７、直径＝８、経路長増加率＝４としたものである。同図（ｃ）は新規に生成されたＮＷであり、点数＝４６、辺数＝６０、最大次数＝６、直径＝８、経路長増加率＝４としたものである。
【００４７】
図６、図７から、本発明のアルゴリズムCreateNetworkを用いることにより、ＮＷの最大次数、直径、経路長増加率は元のＮＷに辺を付加した後のＮＷのものと尾同じかそれ以下であり、さらに、より少ないリンク数であることがわかる。
【００４８】
（２）性能評価
以下に、本発明の有効性の評価を示す。
【００４９】
ここでは、CAIDAにおいて公開されている３９個の実際のISPバックボーンNWのグラフ構造を利用した。以下では簡単のために、任意のノード間にリンク敷設可能とする。また最大次数δ、直径Ｄ、経路長増加率Ｋの値は、要求されたＫの値を満たすように、SIRPLを用いて辺付加した後のNWにおける値を用いることにした。
【００５０】
図８と図９に、元のNW、辺付加後のNW（Ａ）、点集合から生成されたNW（Ｂ）に対する点数・辺数・最大次数・直径及び経路長増加率を示す。図８、図９中のISP列のＡは、各ISPのNWへ辺付加後のNW、ＢはCreateNetworkによって生成されたNWを表している。また、経路長増加率列の"−"は経路長が無限大（元のNWに閉路が存在せず、故障時に代替経路が存在しない）を表している。
【００５１】
アルゴリズムCreateNetworkを用いて得られたNWの最大次数・直径・経路長増加率は、元のNWに辺付加後のNWのものと同じかそれ以下であり、さらにより少ないリンク数であることがわかる。つまり、元のNWと同じノード数のNWを新たに作る場合、アルゴリズムCreateNetworkを用いることで、信頼性や性能が同レベル以上のNWを、より小さなコストで構成することができることを意味している。
【００５２】
なお、上記のリンク設置箇所選択部１０２の処理をプログラムとして構築し、ネットワーク設計装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００５３】
また、構築されたプログラムをハードディスクや、フレキシブルディスク、ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００５４】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５５】
１０ メモリ
１０１ 入力部
１０２ リンク設置箇所選択部
１０３ リンク設置箇所出力部
【特許請求の範囲】
【請求項１】
単一リンク障害(SLF: single link failure)時の品質劣化基準を満たすリンク数を最小化するためのネットワーク設計方法であって、
入力手段、記憶手段、リンク設置箇所選択手段と、を有する装置において、
前記入力手段が、ノード集合Ｖ、リンクを設置可能な位置の集合Ｅ、ノード次数（ノードに接続するリンク数）の制約上限値δ、トポロジの直径（ノード間距離の最大値）の制約上限値Ｄ、単一リンク障害(SLF: single link failure)時の経路長増加率（元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比）の最大値の制約条件値Ｋ、が与えられると、前記記憶手段に格納する入力過程と、
前記リンク設置箇所選択手段は、前記記憶手段から入力されたデータを読み込んで、前記ノード次数δとトポロジ直径の制約上限Ｄを満たす条件の元で、設置するリンク数を最小化するようネットワークトポロジを設計する設計過程と、
を行うことを特徴とするネットワーク設計方法。
【請求項２】
前記設計過程において、
最初に次数制約を満たすよう全域木を構成し、次に、直径制約と次数制約を満たすようリンクを付加し、最後にSLF時の最大経路長増加率の制約条件を満たすよう最小数のリンクを付加する
ことを特徴とする請求項１記載のネットワーク設計方法。
【請求項３】
前記設計過程において、
次数制約を２以上前記δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する
ことを特徴とする請求項２記載のネットワーク設計方法。
【請求項４】
請求項１乃至３のいずれか１項に記載のネットワーク設計方法の各過程としてコンピュータを機能させるためのネットワーク設計プログラム。
【請求項１】
単一リンク障害(SLF: single link failure)時の品質劣化基準を満たすリンク数を最小化するためのネットワーク設計方法であって、
入力手段、記憶手段、リンク設置箇所選択手段と、を有する装置において、
前記入力手段が、ノード集合Ｖ、リンクを設置可能な位置の集合Ｅ、ノード次数（ノードに接続するリンク数）の制約上限値δ、トポロジの直径（ノード間距離の最大値）の制約上限値Ｄ、単一リンク障害(SLF: single link failure)時の経路長増加率（元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比）の最大値の制約条件値Ｋ、が与えられると、前記記憶手段に格納する入力過程と、
前記リンク設置箇所選択手段は、前記記憶手段から入力されたデータを読み込んで、前記ノード次数δとトポロジ直径の制約上限Ｄを満たす条件の元で、設置するリンク数を最小化するようネットワークトポロジを設計する設計過程と、
を行うことを特徴とするネットワーク設計方法。
【請求項２】
前記設計過程において、
最初に次数制約を満たすよう全域木を構成し、次に、直径制約と次数制約を満たすようリンクを付加し、最後にSLF時の最大経路長増加率の制約条件を満たすよう最小数のリンクを付加する
ことを特徴とする請求項１記載のネットワーク設計方法。
【請求項３】
前記設計過程において、
次数制約を２以上前記δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する
ことを特徴とする請求項２記載のネットワーク設計方法。
【請求項４】
請求項１乃至３のいずれか１項に記載のネットワーク設計方法の各過程としてコンピュータを機能させるためのネットワーク設計プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１１−２５９３２１（Ｐ２０１１−２５９３２１Ａ）
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【出願番号】特願２０１０−１３３３６４（Ｐ２０１０−１３３３６４）
【出願日】平成２２年６月１０日（２０１０．６．１０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２２年２月２５日 社団法人電子情報通信学会発行の「信学技報 Ｖｏｌ．１０９ Ｎｏ．４４８ 電子情報通信学会技術研究報告」に発表
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０３０９２１８０）学校法人関西学院 (71)
【Ｆターム（参考）】
【公開日】平成２３年１２月２２日（２０１１．１２．２２）
【国際特許分類】
【出願日】平成２２年６月１０日（２０１０．６．１０）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 平成２２年２月２５日 社団法人電子情報通信学会発行の「信学技報 Ｖｏｌ．１０９ Ｎｏ．４４８ 電子情報通信学会技術研究報告」に発表
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０３０９２１８０）学校法人関西学院 (71)
【Ｆターム（参考）】
[ Back to top ]