故障時にも代替経路を利用して通信が継続できるようなNW設計方法において、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化したネットワーク設計を可能にする。本発明は、次数(ノードに接続するリンク数)制約を満たす全域木を構成し、次に、全域木に辺を付加することで直径を抑えたグラフを出力し、最後に経路長増加率を抑えるように辺を付加することにより、リンクを設置可能な位置集合、ノード次数の制約上の上限値、トポロジの直径の制約上限値、単一リンク障害時の経路長増加率の最大値の制約条件値を入力とした場合に、ノード次数とトポロジ直径の制約上限を満たす条件の下で、設置するリンク数を最小化するようにネットワークを設計できる。概要インターネットをはじめ、通信ネットワーク(以下、「NW」と記す)が社会において必要不可欠なインフラとなった現在、NWには高い信頼性が求められている。大規模なNWでは、様々な要因によるノードやリンクの故障や重い輻輳の発生は避けられないため、そのような障害が発生しても各ノード間の通信を維持し続けるための設計及び制御が必要である。この観点から、障害時にも代替経路を利用して通信が継続できるようにすることを目的とした、高連結度NW設計に関する研究がある。同時に故障するリンクは一つだけとする単一リンク故障(SLF)を仮定し、SLF時にも通信が途絶しないために、NWを2辺連結グラフとなるように設計することは、実際にも一般的に行われている。このように、インターネットサービスプロバイダ(以下、「ISP」と記す)のNWトポロジを、高い連結度のグラフとなるように構成することによって高い信頼性を得ることは可能である。障害時に通常時の経路から代替経路に変化した際に経路長が大きく延びてしまう可能性があり、影響を受ける膨大な数の通信すべてにおいて通信品質の劣化を引き起こす可能性があることが指摘されている。代替経路に切り替わることでトラフィックの流れが変化し、代替経路上で輻輳を起こす可能性がある。これは代替経路の経路長が大幅に増えることで、その可能性がより高くなることが考えられる。したがって、実際のNWトポロジには、単に代替経路が存在するだけではなく、SLF時の経路長増加率が小さいことも必要である。First)などルーティングプロトコルによって決定されるため、経路を適切に定めることで経路長増加率を設定するという方法を取ることはできない。したがって、NWトポロジを適切に決定することによって経路長増加率を設定しなければならない。この経路長増加率が小さければ、障害が発生した際も、すべてのノード間に代替経路が存在し、その経路長が大幅に大きくなることはない。必要な値以下のNWを構築することがNW設計の目的となる。これまで、発明者らによって、既存NWに最小限の増設を行うことで条件を満たすネットワーク増設設計法を提案し、その有効性を示した(例えば、非特許文献1参照)。新規にネットワークを構築する必要がある場合、この方法をそのまま適用することができないため、新規NW設計法が必要である。その際、考慮すべきことは増設設計の場合とは異なり、通常時の通信品質も考慮しなければならない。リンク数を抑えるだけでは、経路長増加率が定められた値以下になる閉路を直列につなぐだけで最適なNWとなるが、これでは直径が大きいため、通常時においても通信遅延の大きいノード間が現われてしまう。スター状のグラフの葉を閉路でつないだ車輪グラフであれば、経路長増加率も直径も抑えられるが、中心のノードの次数が大きくなり、ノード負荷が高くなる可能性が増す。したがって、経路長増加率に加えて、直径と次数の両者を抑えたリンク数の少ないNWを設計する必要がある。本発明は、ネットワーク設計方法及びプログラムに係り、特に、故障時(単一リンク故障時)にも代替経路を利用して通信が継続できるようなネットワークを設計するためのネットワーク設計方法及びプログラムに関する。failure)時の経路長増加率の最大値の制約条件値Kが与えられたときにノード次数とトポロジ直径の制約上限を満たす条件の元で設置するリンク数を最小化するようネットワークトポロジを設計するネットワーク設計方法及びプログラムに関する。請求項1に記載のネットワーク設計方法の各過程としてコンピュータを機能させるためのネットワーク設計プログラム。failure.※ライセンスをご希望の方、特許の内容に興味を持たれた方は、下記「問合せ先」までお問い合わせください。同じキーワードでJ-STORE内を検索することが出来ます。