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

ネットワーク設計方法及びプログラム 新技術説明会 実績あり

国内特許コード P120006803
整理番号 SHINGI20111202
掲載日 2012年3月6日
出願番号 特願2010-133364
公開番号 特開2011-259321
登録番号 特許第5618268号
出願日 平成22年6月10日(2010.6.10)
公開日 平成23年12月22日(2011.12.22)
登録日 平成26年9月26日(2014.9.26)
発明者
  • 上山 憲昭
  • 長谷川 治久
  • 吉野 秀明
  • 巳波 弘佳
出願人
  • 日本電信電話株式会社
  • 学校法人関西学院
発明の名称 ネットワーク設計方法及びプログラム 新技術説明会 実績あり
発明の概要 【課題】 故障時にも代替経路を利用して通信が継続できるようなNW設計方法において、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化したネットワーク設計を可能にする。
【解決手段】 本発明は、次数(ノードに接続するリンク数)制約を満たす全域木を構成し、次に、全域木に辺を付加することで直径を抑えたグラフを出力し、最後に経路長増加率を抑えるように辺を付加することにより、リンクを設置可能な位置集合、ノード次数の制約上の上限値、トポロジの直径の制約上限値、単一リンク障害時の経路長増加率の最大値の制約条件値を入力とした場合に、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化するようにネットワークを設計できる。
【選択図】 図1
従来技術、競合技術の概要



インターネットをはじめ、通信ネットワーク(以下、「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を設計する必要がある。

産業上の利用分野



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





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

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

【請求項2】
請求項1に記載のネットワーク設計方法の各過程としてコンピュータを機能させるためのネットワーク設計プログラム。
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2010133364thum.jpg
出願権利状態 登録
参考情報 (研究プロジェクト等) 2011年12月2日(金) 関西学院大学 新技術説明会
ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記「問合せ先」までお問い合わせください。


PAGE TOP

close
close
close
close
close
close
close