TOP > 国内特許検索 > ネットワーク設計方法及びプログラム > 明細書

明細書 :ネットワーク設計方法及びプログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5618268号 (P5618268)
公開番号 特開2011-259321 (P2011-259321A)
登録日 平成26年9月26日(2014.9.26)
発行日 平成26年11月5日(2014.11.5)
公開日 平成23年12月22日(2011.12.22)
発明の名称または考案の名称 ネットワーク設計方法及びプログラム
国際特許分類 H04L  12/753       (2013.01)
H04L  12/707       (2013.01)
H04L  12/24        (2006.01)
FI H04L 12/753
H04L 12/707
H04L 12/24
請求項の数または発明の数 2
全頁数 10
出願番号 特願2010-133364 (P2010-133364)
出願日 平成22年6月10日(2010.6.10)
新規性喪失の例外の表示 特許法第30条第1項適用 平成22年2月25日 社団法人電子情報通信学会発行の「信学技報 Vol.109 No.448 電子情報通信学会技術研究報告」に発表
審査請求日 平成24年12月12日(2012.12.12)
特許権者または実用新案権者 【識別番号】000004226
【氏名又は名称】日本電信電話株式会社
【識別番号】503092180
【氏名又は名称】学校法人関西学院
発明者または考案者 【氏名】上山 憲昭
【氏名】長谷川 治久
【氏名】吉野 秀明
【氏名】巳波 弘佳
個別代理人の代理人 【識別番号】100107766、【弁理士】、【氏名又は名称】伊東 忠重
【識別番号】100070150、【弁理士】、【氏名又は名称】伊東 忠彦
【識別番号】100124844、【弁理士】、【氏名又は名称】石原 隆治
審査官 【審査官】衣鳩 文彦
参考文献・文献 特表2009-531981(JP,A)
川島 潤 他,マルチホームネットワーク環境下での完全k分木型ピアツーピアマルチキャスト経路木探索解法の提案,電子情報通信学会技術研究報告,2004年 1月23日,第103巻,第625号,p.5~8
原井 洋明 他,分散計算環境構築のための光パス構成法,電子情報通信学会技術研究報告,2005年10月 6日,第105巻,第323号,p.7~12
マリンダ ティルミー 他,ノード障害に対する自律分散的回復を可能とするオーバレイ遅延最小木の構築アルゴリズム,情報処理学会研究報告,2003年11月14日,第2003巻,第113号,p.33~38
片山 希 他,故障時における性能劣化を抑制するネットワーク設計法,電子情報通信学会技術研究報告,2009年 2月24日,第108巻,第457号,p.117~122
伊藤 大雄 他,次数制限のある最短路木作成アルゴリズム,情報処理学会研究報告,1999年 1月27日,第99巻,第8号,p.1~7
Thilmee M. BADUGE 他,帯域制約のもとで遅延最小のオーバレイマルチキャスト木を構築する分散アルゴリズム,電子情報通信学会論文誌,2005年11月 1日,第J88-D-I巻,第11号,p.1648~1658
調査した分野 H04L 12/00~12/955
特許請求の範囲 【請求項1】
単一リンク障害(SLF: single link failure)時の品質劣化基準を満たすリンク数を最小化するためのネットワーク設計方法であって、
入力手段、記憶手段、リンク設置箇所選択手段と、を有する装置において、
前記入力手段が、ノード集合V、リンクを設置可能な位置の集合E、ノード次数(ノードに接続するリンク数)の制約上限値δ、トポロジの直径(ノード間距離の最大値)の制約上限値D、単一リンク障害(SLF: single link failure)時の経路長増加率(元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比)の最大値の制約条件値K、が与えられると、前記記憶手段に格納する入力過程と、
前記リンク設置箇所選択手段は、前記記憶手段から入力されたデータを読み込んで、前記ノード次数の制約上限値δとトポロジ直径の制約上限Dを満たす条件の元で、設置するリンク数を最小化するようネットワークトポロジを設計する設計過程と、
を行い、
前記設計過程において、
最初に次数制約を満たすよう全域木を構成し、次に、直径制約と次数制約を満たすようリンクを付加し、最後にSLF時の最大経路長増加率の制約条件を満たすよう最小数のリンクを付加するものとし、
次数制約を2以上前記ノード次数の制約上限値δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する
ことを特徴とするネットワーク設計方法。
【請求項2】
請求項1に記載のネットワーク設計方法の各過程としてコンピュータを機能させるためのネットワーク設計プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、ネットワーク設計方法及びプログラムに係り、特に、故障時(単一リンク故障時)にも代替経路を利用して通信が継続できるようなネットワークを設計するためのネットワーク設計方法及びプログラムに関する。
【0002】
詳しくは、リンクを設置可能な位置の集合E、ノード次数の制約上限値δ、トポロジの直径の制約上限値D、単一リンク障害(SLF: single link failure)時の経路長増加率の最大値の制約条件値Kが与えられたときにノード次数とトポロジ直径の制約上限を満たす条件の元で設置するリンク数を最小化するようネットワークトポロジを設計するネットワーク設計方法及びプログラムに関する。
【背景技術】
【0003】
インターネットをはじめ、通信ネットワーク(以下、「NW」と記す)が社会において必要不可欠なインフラとなった現在、NWには高い信頼性が求められている。しかし、特に大規模なNWでは、様々な要因によるノードやリンクの故障や重い輻輳の発生は避けられないため、そのような障害が発生しても各ノード間の通信を維持し続けるための設計及び制御が必要である。
【0004】
この観点から、障害時にも代替経路を利用して通信が継続できるようにすることを目的とした、高連結度NW設計に関する研究がある。例えば、同時に故障するリンクは一つだけとする単一リンク故障(SLF)を仮定し、SLF時にも通信が途絶しないために、NWを2辺連結グラフとなるように設計することは、実際にも一般的に行われている。このように、インターネットサービスプロバイダ(以下、「ISP」と記す)のNWトポロジを、高い連結度のグラフとなるように構成することによって高い信頼性を得ることは可能である。
【0005】
しかし、障害時に通常時の経路から代替経路に変化した際に経路長が大きく延びてしまう可能性があり、影響を受ける膨大な数の通信すべてにおいて通信品質の劣化を引き起こす可能性があることが指摘されている。また、代替経路に切り替わることでトラフィックの流れが変化し、代替経路上で輻輳を起こす可能性がある。これは代替経路の経路長が大幅に増えることで、その可能性がより高くなることが考えられる。したがって、実際のNWトポロジには、単に代替経路が存在するだけではなく、SLF時の経路長増加率が小さいことも必要である。
【0006】
インターネットにおいては、経路を自由に決定することはできず、OSPF(Open shortest Path First)などルーティングプロトコルによって決定されるため、経路を適切に定めることで経路長増加率を設定するという方法を取ることはできない。したがって、NWトポロジを適切に決定することによって経路長増加率を設定しなければならない。この経路長増加率が小さければ、障害が発生した際も、すべてのノード間に代替経路が存在し、その経路長が大幅に大きくなることはない。このことから、限られたコストで故障時経路長増加率が必要な値以下のNWを構築することがNW設計の目的となる。
【0007】
これまで、発明者らによって、既存NWに最小限の増設を行うことで条件を満たすネットワーク増設設計法を提案し、その有効性を示した(例えば、非特許文献1参照)。しかし、新規にネットワークを構築する必要がある場合、この方法をそのまま適用することができないため、新規NW設計法が必要である。その際、考慮すべきことは増設設計の場合とは異なり、通常時の通信品質も考慮しなければならない。例えば、コスト最小化のためにリンク数の少ないNWを設計するというだけでは、直径が大きく延びてしまう可能性がある。実際、経路長増加率とリンク数を抑えるだけでは、経路長増加率が定められた値以下になる閉路を直列につなぐだけで最適なNWとなるが、これでは直径が大きいため、通常時においても通信遅延の大きいノード間が現われてしまう。しかし、スター状のグラフの葉を閉路でつないだ車輪グラフであれば、経路長増加率も直径も抑えられるが、中心のノードの次数が大きくなり、ノード負荷が高くなる可能性が増す。したがって、経路長増加率に加えて、直径と次数の両者を抑えたリンク数の少ないNWを設計する必要がある。
【先行技術文献】
【0008】

【非特許文献1】片山、藤村、巳波、上山、長谷川、吉野、 "故障時における性能劣化を抑制するネットワーク設計法、" 信学技報NS2008-164
【発明の概要】
【発明が解決しようとする課題】
【0009】
上記の従来の技術の問題を解決する手法として、直径と次数を抑えた辺数の少ないグラフとして、ムーアグラフが知られているが、ムーアグラフであることが分かっているのは、限られた条件の組に対してのみである。ムーアグラフに近いグラフ構造として、de BruijnグラフやKautzグラフが知られている。これは任意の条件に対してそれを満たすグラフの構成が可能である。しかし、さらに任意の経路長増加率を満たすような構成法はない。また、任意の点対間に辺を張れることを仮定しなければならず、現実的には適用することが難しい。
【0010】
予めリンクを張れるノード対間が指定されている状況の下で、条件を満たすネットワークを構成するタイプの問題も多い。これは、リンク候補点対を辺集合とするグラフにおいて、全域部分グラフを求めることに対応する。全域部分グラフの辺が実際にリンクが張られるノード対間になる。したがって、グラフにおいて条件を満たす辺数最小の全域部分グラフを求める問題として定式化される。しかし、いずれも経路長増加率に関しては扱われていない。
【0011】
本発明は、上記の点に鑑みなされたもので、故障時にも代替経路を利用して通信が継続できるようなNW設計方法において、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化したネットワーク設計が可能なネットワーク設計方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【0012】
上記の問題を解決するために、本発明(請求項1)は、単一リンク障害(SLF: single link failure)時の品質劣化基準を満たすリンク数を最小化するためのネットワーク設計方法であって、
入力手段、記憶手段、リンク設置箇所選択手段と、を有する装置において、
入力手段が、ノード集合V、リンクを設置可能な位置の集合E、ノード次数(ノードに接続するリンク数)の制約上限値δ、トポロジの直径(ノード間距離の最大値)の制約上限値D、単一リンク障害時の経路長増加率(元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比)の最大値の制約条件値K、が与えられると、記憶手段に格納する入力過程と、
リンク設置箇所選択手段は、記憶手段から入力されたデータを読み込んで、ノード次数の制約上限値δとトポロジ直径の制約上限Dを満たす条件の元で、設置するリンク数を最小化するようネットワークトポロジを設計する設計過程と、
を行い、
設計過程において、
最初に次数制約を満たすよう全域木を構成し、次に、直径制約と次数制約を満たすようリンクを付加し、最後にSLF時の最大経路長増加率の制約条件を満たすよう最小数のリンクを付加するものとし、
次数制約を2以上ノード次数の制約上限値δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する。
【0015】
また、本発明(請求項)は、請求項1に記載のネットワーク設計方法の各過程としてコンピュータを機能させるためのネットワーク設計プログラムである。
【発明の効果】
【0016】
上記のように、本発明によれば、リンクを設置可能な位置の集合E、ノード次数の制約上限値δ、トポロジの直径の制約上限値D、SLF時の経路長増加率の最大値の制約条件値K、が与えられたときに、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化するよう、ネットワークトポロジを設計することができる。
【図面の簡単な説明】
【0017】
【図1】本発明の一実施の形態におけるネットワーク設計装置の構成図である。
【図2】本発明の一実施の形態で用いられるアルゴリズムSIRPLの処理フローである。
【図3】本発明の一実施の形態におけるアルゴリズムCreateNetworkの処理フローである。
【図4】本発明の一実施の形態における関数i-Tree(i)の処理フローである。
【図5】本発明の一実施の形態における関数Control Diameterの処理フローである。
【図6】本発明の一実施の形態における処理結果の例(その1)である。
【図7】本発明の一実施の形態における処理結果の例(その2)である。
【図8】辺付加後のネットワークと新規編成されたネットワークの各値を示す図(その1)である。
【図9】辺付加後のネットワークと新規編成されたネットワークの各値を示す図(その1)である。
【発明を実施するための形態】
【0018】
以下図面と共に、本発明の実施の形態を説明する。

【0019】
図1は、本発明の一実施の形態におけるNW設計装置の構成を示す。

【0020】
同図に示すNW設計装置は、メモリ10、入力部101、リンク設置箇所選択部102、リンク設置箇所出力部103から構成される。

【0021】
入力部101は、ノード集合V、リンク設置可能位置集合E、ノード次数(ノードに接続するリンク数)の制約上限値δ、トポロジの直径(ノード間距離の最大値)の制約上限値D、SLF時の最大フロー長増加率(元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比の最大値)の制約上限値K、を入力し、メモリ10に格納する。

【0022】
リンク設置箇所選択部102は、メモリ10から上記の入力された値を読み込み、ノード次数の制約上限値δとトポロジを直径の制約上限値Dを満たす条件の下で、設置するリンク数を最小化するようにネットワークトポロジを設計し、メモリ10に格納する。

【0023】
詳しくは、設置するリンク数を最小化するために、
(1)最初に次数制約を満たすよう全域木を構成する。

【0024】
(2)次に、直径制約Dと次数制約δを満たすようリンクを付加する。

【0025】
(3)最後にSLF時の最大経路長増加率の制約条件Kを満たすよう最小数のリンクを付加する。このとき、次数制約を2以上δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する。

【0026】
リンク設置箇所出力部103は、メモリ10からリンク設置箇所情報を読み込んで出力する。

【0027】
次に、本発明の実施の形態に係るリンク設置箇所選択部102における、単一リンク障害時の品質劣化基準を満たすリンク数最小ネットワーク設計法について、詳細を説明する。

【0028】
[1]定式化
リンク設置箇所選択部102は、まず、本発明で扱うネットワーク設計問題を定式化する。

【0029】
本実施の形態では、次数(ノードに接続するリンク数)制約を満たす全域木をまず構成し、それに辺を付加することで直径を抑えて得られるグラフに、経路長増加率を抑えるように辺を付加するアルゴリズムを適用する。次数制約を満たす全域木を求めることは一般にはNP完全であるが、近似アルゴリズムが存在する。グラフの直径を抑えるように付加リンクを決定する問題もNP完全であるが、こちらには有効な近似アルゴリズムはまだ知られていない。そのため、ここでは、全域木において直径制約を満たさない距離の点対間に辺を付加することを繰り返すことにより直径を小さくする。

【0030】
新規ネットワーク設計アルゴリズム"CreateNetwork"は、次のアルゴリズム"SIRPL"をサブルーチンとして包含する。アルゴリズム"SIRPL"は次数制約・経路長増加率制約の下で辺を付加するアルゴリズムである。グラフGにおいて、辺e∈EのSLFによる経路長増加率がK以下の辺を「充足辺」と呼び、さもなければ「未充足辺」と呼ぶ。未充足辺集合をUとする。また、

【0031】
【数1】
JP0005618268B2_000002t.gif
を付加することで1辺以上の未充足辺を充足辺にできるとき、辺fを「候補辺」と呼び、fによって充足辺にできる未充足辺の集合をSfとする。付加可能点対集合に候補辺集合が含まれると仮定する。また、付加辺は候補辺からのみ選ぶものとする。

【0032】
以下に、アルゴリズムSIRPLを示す。図2は、本発明の一実施の形態で用いられるアルゴリズムSIRPLの処理フローを示す。

【0033】
ステップ201) リンク設置箇所選択部102によりアルゴリズムSIRPLが起動されると、未充足辺集合U、候補辺集合S={S1;S2;:::;Sf;:::Sh}候補辺の各辺fによって充足できる未充足辺集合Sfを求める。

【0034】
ステップ202) 集合Cを0とする(C=0)。

【0035】
ステップ203) 未充足辺集合Uが空集合である場合は、集合Cを出力して処理を終了する。空集合でない場合はステップ204に移行する。

【0036】
ステップ204) 候補辺fを付加することによって、fの両端点の次数がiを超えないという条件を満たすfの中で、
|Sf∩U|
が最大となるSfを選ぶ。

【0037】
ステップ205) 未充足辺集合UをU-Sfとし、集合CをCU{Sf}とする。

【0038】
ステップ206) 集合Cを出力する。

【0039】
ここで得られた集合Cは、次数i以下という条件の下で、経路長増加率がK以下になるように付加する辺集合である。

【0040】
なお、上記アルゴリズムSIRPLにおいては、付加辺を選択する際、最大数の未充足辺を充足するような辺を付加辺として選ぶことを反復することにより、付加辺数の抑制を図っている。各候補辺fによって充足できる未充足辺集合Sfを求め、未充足辺集合UとSf積集合が最大となるfに対して、UからSfを引き、充足辺集合CにSfを加える。

【0041】
次に、新規ネットワーク設計アルゴリズムCreateNetworkを以下に挙げる。

【0042】
図3は、本発明の一実施の形態におけるアルゴリズムCreateNetworkの処理フローを示す。同図のフローにおいて、ステップ303,304の関数i-Treeは、最大次数iの全体木を求めるものであり、その処理フローを図4に示す。同図において関数i-Treeは、点rを根とする木Tを生成し、根rからの距離が最も小さい葉の点vを一つ選択し、vの隣接点のうちTに含まれないものからi個以下の点を選んでvの子ノードとし、それらをTに加える処理をTが全体木となるまで繰り返す。

【0043】
ステップ305の関数ControlDiameterは、次数i以下という条件の下で、直径がD以下になるように辺を付加するものであり、当該関数ControlDiameterの処理フローを図5に示す。ステップ306のSIRPLは、上で挙げた経路長増加率制約と次数制約を満たす辺付加アルゴリズムである。ステップ307において、以上の処理で得られた辺をすべてE´とし、iを1インクリメントし、ステップ301に移行する。ステップ309では、すべてのiに対してこのようにしてグラフGi´=(V:Ei´)を構成し、その中で辺数が最も少ないグラフをメモリ10に出力する。

【0044】
なお、Gが完全グラフ、つまりどのノード間にもリンクが張れる場合、i-Tree(i)はi分木を構成する。ControlDeameter(i, D)に関しては、ここでは、距離が最大である2点間に辺を付加することを直径がD以下になるまで反復するという単純なものを用いる。

【0045】
図6、図7にCAIDAで公開されているNWに本アルゴリズムを適用した場合の処理結果の例を示す。図6は、CAIDA(Cooperative Association for Internet Data Analysis)で公開されているISPバックボーンネットワークを対象としたものであり、各ネットワークにおいて、1行目は元のネットワークの情報であり、2行目は元のネットワークの経路長増加率が4になるように辺付加したものであり、3行目は元のネットワークと同じ点数であって、最大次数と直径が2行目のものを超えないように設計した新規ネットワークを示している。

【0046】
図7(a)は、元のNWであり、点数=46、辺数=55、最大次数=5、直径=13としたものであり、同図(b)は、辺を付加した後の元のNWであり、点数=46、辺数=67、最大次数=7、直径=8、経路長増加率=4としたものである。同図(c)は新規に生成されたNWであり、点数=46、辺数=60、最大次数=6、直径=8、経路長増加率=4としたものである。

【0047】
図6、図7から、本発明のアルゴリズムCreateNetworkを用いることにより、NWの最大次数、直径、経路長増加率は元のNWに辺を付加した後のNWのものと尾同じかそれ以下であり、さらに、より少ないリンク数であることがわかる。

【0048】
(2)性能評価
以下に、本発明の有効性の評価を示す。

【0049】
ここでは、CAIDAにおいて公開されている39個の実際のISPバックボーンNWのグラフ構造を利用した。以下では簡単のために、任意のノード間にリンク敷設可能とする。また最大次数δ、直径D、経路長増加率Kの値は、要求されたKの値を満たすように、SIRPLを用いて辺付加した後のNWにおける値を用いることにした。

【0050】
図8と図9に、元のNW、辺付加後のNW(A)、点集合から生成されたNW(B)に対する点数・辺数・最大次数・直径及び経路長増加率を示す。図8、図9中のISP列のAは、各ISPのNWへ辺付加後のNW、BはCreateNetworkによって生成されたNWを表している。また、経路長増加率列の"-"は経路長が無限大(元のNWに閉路が存在せず、故障時に代替経路が存在しない)を表している。

【0051】
アルゴリズムCreateNetworkを用いて得られたNWの最大次数・直径・経路長増加率は、元のNWに辺付加後のNWのものと同じかそれ以下であり、さらにより少ないリンク数であることがわかる。つまり、元のNWと同じノード数のNWを新たに作る場合、アルゴリズムCreateNetworkを用いることで、信頼性や性能が同レベル以上のNWを、より小さなコストで構成することができることを意味している。

【0052】
なお、上記のリンク設置箇所選択部102の処理をプログラムとして構築し、ネットワーク設計装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。

【0053】
また、構築されたプログラムをハードディスクや、フレキシブルディスク、CD-ROM等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。

【0054】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【0055】
10 メモリ
101 入力部
102 リンク設置箇所選択部
103 リンク設置箇所出力部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8