Top > Search of Japanese Patents > NETWORK DESIGN METHOD AND PROGRAM

NETWORK DESIGN METHOD AND PROGRAM meetings achieved

Patent code P120006803
File No. SHINGI20111202
Posted date Mar 6, 2012
Application number P2010-133364
Publication number P2011-259321A
Patent number P5618268
Date of filing Jun 10, 2010
Date of publication of application Dec 22, 2011
Date of registration Sep 26, 2014
Inventor
  • (In Japanese)上山 憲昭
  • (In Japanese)長谷川 治久
  • (In Japanese)吉野 秀明
  • (In Japanese)巳波 弘佳
Applicant
  • (In Japanese)日本電信電話株式会社
  • (In Japanese)学校法人関西学院
Title NETWORK DESIGN METHOD AND PROGRAM meetings achieved
Abstract PROBLEM TO BE SOLVED: To allow such network design as the number of links to be installed is minimized under the condition which satisfies upper limit in constraint for a degree of node and a diameter of topology, relating to a NW design method in which communication can be continued by utilizing an alternate path even in the case of failure.
SOLUTION: Such entire area tree as meets with a degree (the number of links to be connected to node) constraint is constituted. Then, a graph in which a diameter is suppressed by adding a side to the entire area tree is outputted, and lastly, the side is added so as to suppress an increase rate in a path length. With this configuration, such network can be designed as to minimize the number of links to be installed under the condition in which the upper limit of constraint in the degree of node and the diameter of topology is met, if followings are taken as inputs: a position set capable of installing a link; an upper limit of constraint in the degree of node; an upper limit of constraint in the diameter of topology; and a constraint condition value of the maximum value in increase rate of path length in case of single link failure.
Outline of related art and contending technology (In Japanese)

インターネットをはじめ、通信ネットワーク(以下、「NW」と記す)が社会において必要不可欠なインフラとなった現在、NWには高い信頼性が求められている。しかし、特に大規模なNWでは、様々な要因によるノードやリンクの故障や重い輻輳の発生は避けられないため、そのような障害が発生しても各ノード間の通信を維持し続けるための設計及び制御が必要である。

この観点から、障害時にも代替経路を利用して通信が継続できるようにすることを目的とした、高連結度NW設計に関する研究がある。例えば、同時に故障するリンクは一つだけとする単一リンク故障(SLF)を仮定し、SLF時にも通信が途絶しないために、NWを2辺連結グラフとなるように設計することは、実際にも一般的に行われている。このように、インターネットサービスプロバイダ(以下、「ISP」と記す)のNWトポロジを、高い連結度のグラフとなるように構成することによって高い信頼性を得ることは可能である。

しかし、障害時に通常時の経路から代替経路に変化した際に経路長が大きく延びてしまう可能性があり、影響を受ける膨大な数の通信すべてにおいて通信品質の劣化を引き起こす可能性があることが指摘されている。また、代替経路に切り替わることでトラフィックの流れが変化し、代替経路上で輻輳を起こす可能性がある。これは代替経路の経路長が大幅に増えることで、その可能性がより高くなることが考えられる。したがって、実際のNWトポロジには、単に代替経路が存在するだけではなく、SLF時の経路長増加率が小さいことも必要である。

インターネットにおいては、経路を自由に決定することはできず、OSPF(Open shortest Path First)などルーティングプロトコルによって決定されるため、経路を適切に定めることで経路長増加率を設定するという方法を取ることはできない。したがって、NWトポロジを適切に決定することによって経路長増加率を設定しなければならない。この経路長増加率が小さければ、障害が発生した際も、すべてのノード間に代替経路が存在し、その経路長が大幅に大きくなることはない。このことから、限られたコストで故障時経路長増加率が必要な値以下のNWを構築することがNW設計の目的となる。

これまで、発明者らによって、既存NWに最小限の増設を行うことで条件を満たすネットワーク増設設計法を提案し、その有効性を示した(例えば、非特許文献1参照)。しかし、新規にネットワークを構築する必要がある場合、この方法をそのまま適用することができないため、新規NW設計法が必要である。その際、考慮すべきことは増設設計の場合とは異なり、通常時の通信品質も考慮しなければならない。例えば、コスト最小化のためにリンク数の少ないNWを設計するというだけでは、直径が大きく延びてしまう可能性がある。実際、経路長増加率とリンク数を抑えるだけでは、経路長増加率が定められた値以下になる閉路を直列につなぐだけで最適なNWとなるが、これでは直径が大きいため、通常時においても通信遅延の大きいノード間が現われてしまう。しかし、スター状のグラフの葉を閉路でつないだ車輪グラフであれば、経路長増加率も直径も抑えられるが、中心のノードの次数が大きくなり、ノード負荷が高くなる可能性が増す。したがって、経路長増加率に加えて、直径と次数の両者を抑えたリンク数の少ないNWを設計する必要がある。

Field of industrial application (In Japanese)

本発明は、ネットワーク設計方法及びプログラムに係り、特に、故障時(単一リンク故障時)にも代替経路を利用して通信が継続できるようなネットワークを設計するためのネットワーク設計方法及びプログラムに関する。

詳しくは、リンクを設置可能な位置の集合E、ノード次数の制約上限値δ、トポロジの直径の制約上限値D、単一リンク障害(SLF: single link failure)時の経路長増加率の最大値の制約条件値Kが与えられたときにノード次数とトポロジ直径の制約上限を満たす条件の元で設置するリンク数を最小化するようネットワークトポロジを設計するネットワーク設計方法及びプログラムに関する。

Scope of claims (In Japanese)
【請求項1】
 
単一リンク障害(SLF: single link failure)時の品質劣化基準を満たすリンク数を最小化するためのネットワーク設計方法であって、
入力手段、記憶手段、リンク設置箇所選択手段と、を有する装置において、
前記入力手段が、ノード集合V、リンクを設置可能な位置の集合E、ノード次数(ノードに接続するリンク数)の制約上限値δ、トポロジの直径(ノード間距離の最大値)の制約上限値D、単一リンク障害(SLF: single link failure)時の経路長増加率(元のトポロジにおける最短距離に対するSLF後のトポロジにおける最短距離の比)の最大値の制約条件値K、が与えられると、前記記憶手段に格納する入力過程と、
前記リンク設置箇所選択手段は、前記記憶手段から入力されたデータを読み込んで、前記ノード次数の制約上限値δとトポロジ直径の制約上限Dを満たす条件の元で、設置するリンク数を最小化するようネットワークトポロジを設計する設計過程と、
を行い、
前記設計過程において、
最初に次数制約を満たすよう全域木を構成し、次に、直径制約と次数制約を満たすようリンクを付加し、最後にSLF時の最大経路長増加率の制約条件を満たすよう最小数のリンクを付加するものとし、
次数制約を2以上前記ノード次数の制約上限値δ以下の各整数値に対してネットワークを各々設計し、その中で最も構成リンク数が少ないものを最終的に選択する
ことを特徴とするネットワーク設計方法。

【請求項2】
 
請求項1に記載のネットワーク設計方法の各過程としてコンピュータを機能させるためのネットワーク設計プログラム。
IPC(International Patent Classification)
F-term
Drawing

※Click image to enlarge.

JP2010133364thum.jpg
State of application right Registered
Please contact us by E-mail or facsimile if you have any interests on this patent


PAGE TOP

close
close
close
close
close
close
close