(57)【要約】【課題】リンク利用率のオーバーフローを抑制し、通常時および故障時のトポロジにおける各最大リンク利用率を低減するＩＰ網ルーチング設計を行う技術を提供する。【解決手段】ＩＰ網ルーチング設計装置１０は、故障パターンを生成する故障パターン生成部２１と、ＩＰ網トポロジ情報３２を用いてリンクコストを算出するリンクコスト計算部２２と、交流トラヒック情報３１とリンク容量情報３２１とを用いてリンク利用率（＝トラヒック量／リンク容量）を算出するリンク利用率計算部２３と、故障パターン生成部２１によって生成された故障パターンについて、リンク利用率計算部２３によって算出されたリンク利用率が所定の値を超える超過分の合計を算出し、その超過分の合計を指標として、リンクコスト計算部２２において算出されたリンクコストを選択するか否かを判定するリンクコスト選択判定部２４と、を備える。【選択図】 図３
2010130382.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワークにおけるリンク故障時のルーチング設計を行う故障を考慮したルーチング設計装置であって、
リンク故障の発生していないときの前記通信ネットワークのトポロジおよびリンクのリンク容量を含むトポロジ情報と、リンクを流れるトラヒック量に係る交流トラヒック情報とを記憶する記憶部と、
前記通信ネットワークのリンク故障時のトポロジを表す故障パターンを生成する故障パターン生成部と、
前記トポロジ情報におけるトポロジに基づいて各リンクのリンクコストを算出するリンクコスト計算部と、
前記交流トラヒック情報を参照して、前記リンクコスト計算部によって算出された各リンクのリンクコストに基づいて設定される経路を構成するリンクに収容されるトラヒック量を算出し、当該リンクごとに、そのリンクに収容されるトラヒック量を前記記憶部に記憶されているそのリンクのリンク容量で除算して求められる各リンクのリンク利用率を、前記トポロジ情報におけるトポロジおよび前記故障パターンについて算出するリンク利用率計算部と、
前記リンク利用率計算部によって算出された前記各リンクのリンク利用率が所定の値を超える超過分の合計を算出し、その超過分の合計に基づいて、前記リンクコスト計算部において算出された各リンクのリンクコストを選択するか否かを判定するリンクコスト選択判定部と、を備え、
前記リンクコスト選択判定部は、前記超過分の合計を記憶部に記憶し、
前記リンクコスト計算部は、前記トポロジ情報におけるトポロジから取得される２つのノードについて、そのノード間の経路を構成する各リンクのリンクコストの合計が等しくなる経路を２以上生成するようにリンクの新たなリンクコストを算出し、
前記リンク利用率計算部は、当該リンクの新たなリンクコストに基づいて設定される経路を構成するリンクのリンク利用率を、前記トポロジ情報におけるトポロジおよび前記故障パターンについてリンクの新たなリンク利用率として算出し、
前記リンクコスト選択判定部は、当該リンクの新たなリンク利用率に基づいて、当該リンクの新たなリンク利用率が所定の値を超える超過分の合計を新たな超過分の合計として算出し、当該新たな超過分の合計が前記記憶部に記憶しておいた超過分の合計以下の場合に、前記記憶部の前記超過分の合計を当該新たな超過分の合計に更新し、前記リンクコスト計算部において算出された各リンクのリンクコストを選択すること
を特徴とする故障を考慮したルーチング設計装置。
【請求項２】
前記リンクコスト選択判定部は、
前記トポロジ情報におけるトポロジについて算出された各リンクのリンク利用率の最大値を記憶部に記憶し、
前記トポロジ情報におけるトポロジについて前記リンクの新たなリンクコストに基づいて設定される経路を構成するリンクについて算出した前記リンクの新たなリンク利用率の最大値が、前記記憶部に記憶しておいた前記リンクのリンク利用率の最大値より小さいときに、
当該リンクの新たなリンク利用率に基づいて、当該リンクの新たなリンク利用率が所定の値を超える超過分の合計を新たな超過分の合計として算出し、当該新たな超過分の合計が前記記憶部に記憶しておいた超過分の合計以下の場合に、前記記憶部の前記超過分の合計を当該新たな超過分の合計に更新し、前記リンクコスト計算部において算出された各リンクのリンクコストを選択すること
を特徴とする請求項１に記載の故障を考慮したルーチング設計装置。
【請求項３】
前記リンクコスト選択判定部は、
前記選択された各リンクのリンクコストを記憶部に記憶し、
前記リンクの新たなリンク利用率に基づいて算出した超過分の合計と前記記憶部に記憶しておいた超過分の合計との比較を行った回数をカウントし、その回数が所定の回数に達したときに、前記記憶部に記憶してあった各リンクのリンクコストを解として決定すること
を特徴とする請求項１または請求項２に記載の故障を考慮したルーチング設計装置。
【請求項４】
前記故障パターン生成部は、同時に故障が発生しうる前記通信ネットワークのリンクの集合情報であるＳＲＬＧ（Shared Risk Link Group）情報を用いて同時に故障が発生しうるリンクについての故障パターンを生成すること、ノードを構成する部品の故障発生確率の高さに基づいて選択されるリンクに故障が発生したと見做して同時に１以上のリンク故障が発生したものとする故障パターンを生成すること、前記リンク利用率の大きさに基づいて選択されるリンクをリンクに故障が発生したと見做して同時に１以上のリンク故障が発生したものとする故障パターンを生成すること、および、発生した乱数を各リンクに付与して、その乱数の大きさに基づいて選択されるリンクに故障が発生したと見做して同時に１以上のリンク故障が発生したものとする故障パターンを生成すること、のいずれか一つまたはそれらの組み合わせを実行すること
を特徴とする請求項１ないし請求項３のいずれか一項に記載の故障を考慮したルーチング設計装置。
【請求項５】
通信ネットワークにおけるリンク故障時のルーチング設計を行う故障を考慮したルーチング設計装置に用いられる故障を考慮したルーチング設計方法であって、
前記故障を考慮したルーチング設計装置が、
リンク故障の発生していないときの前記通信ネットワークのトポロジおよびリンクのリンク容量を含むトポロジ情報と、リンクを流れるトラヒック量に係る交流トラヒック情報とを記憶する記憶部と、
前記通信ネットワークのリンク故障時のトポロジを表す故障パターンを生成する故障パターン生成部と、
前記トポロジ情報におけるトポロジに基づいて各リンクのリンクコストを算出するリンクコスト計算部と、
前記交流トラヒック情報を参照して、前記リンクコスト計算部によって算出された各リンクのリンクコストに基づいて設定される経路を構成するリンクに収容されるトラヒック量を算出し、当該リンクごとに、そのリンクに収容されるトラヒック量を前記記憶部に記憶されているそのリンクのリンク容量で除算して求められる各リンクのリンク利用率を、前記トポロジ情報におけるトポロジおよび前記故障パターンについて算出するリンク利用率計算部と、
前記リンク利用率計算部によって算出された前記各リンクのリンク利用率が所定の値を超える超過分の合計を算出し、その超過分の合計に基づいて、前記リンクコスト計算部において算出された各リンクのリンクコストを選択するか否かを判定するリンクコスト選択判定部と、を備え、
前記リンクコスト選択判定部は、前記超過分の合計を記憶部に記憶し、
前記リンクコスト計算部は、前記トポロジ情報におけるトポロジから取得される２つのノードについて、そのノード間の経路を構成する各リンクのリンクコストの合計が等しくなる経路を２以上生成するようにリンクの新たなリンクコストを算出し、
前記リンク利用率計算部は、当該リンクの新たなリンクコストに基づいて設定される経路を構成するリンクのリンク利用率を、前記トポロジ情報におけるトポロジおよび前記故障パターンについてリンクの新たなリンク利用率として算出し、
前記リンクコスト選択判定部は、当該リンクの新たなリンク利用率に基づいて、当該リンクの新たなリンク利用率が所定の値を超える超過分の合計を新たな超過分の合計として算出し、当該新たな超過分の合計が前記記憶部に記憶しておいた超過分の合計以下の場合に、前記記憶部の前記超過分の合計を当該新たな超過分の合計に更新し、前記リンクコスト計算部において算出された各リンクのリンクコストを選択すること
を特徴とする故障を考慮したルーチング設計方法。
【請求項６】
コンピュータを請求項１ないし請求項４のいずれか一項に記載の故障を考慮したルーチング設計装置を構成する各部として、コンピュータを機能させるための故障を考慮したルーチング設計プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークのリンク故障時を含むＩＰ（Internet Protocol）網における最適なルーチング設計を行うための故障を考慮したＩＰ網ルーチング設計装置、ＩＰ網ルーチング設計方法、およびそのプログラムに関する。
【背景技術】
【０００２】
ネットワーク事業者は、ネットワークのルーチング設計によって、ネットワーク全体にわたる資源の利用効率の平準化を行って、資源の利用効率の向上およびネットワークの品質の向上を目指しつつ、ネットワークコストの低減を図っている。ネットワークのルーチング設計の代表的な方法に、ＦＴ（考案者２名の名前Fortz&Thorupの頭文字を合わせたもの）法（非特許文献１）およびＲｏｂｕｓｔ−ＦＴ法（リンク故障が起きた場合も考慮するようにＦＴ法を改変したもの）（非特許文献２）がある。ＦＴ法およびＲｏｂｕｓｔ−ＦＴ法は、ネットワーク全体の交流トラヒック情報と網トポロジ情報とが与えられた状態において、各リンクに付与されるリンクコストを算出する方法である。なお、リンクコストの算出の前提として、発信ノードから着信ノードに至る経路の各リンクに付与されたリンクコストの合計が最小となる経路をルートとして選択し、選択されたルートが複数ある場合には、当該発信ノードから当該着信ノードに至るトラヒック量がルートごとに均等に流れるものとしている。
【０００３】
ＦＴ法（非特許文献１ではHeurOSPFと称されている）は、リンク故障が起きていない状態の（通常時の）ネット−ワークのトポロジにおいて、発信ノードと着信ノードとの間に出来るだけ多くのルートが選択されるような各リンクのリンクコストを算出する。具体例を、図１０を用いて説明する。図１０は、ＦＴ法の概念を説明する図である。図１０に示すネットワークでは、丸はノードを表し、ノード間の線はリンクを表し、リンクを表す線の上方近傍の数字はリンクコストを表している。また、表には、経路とその経路を構成する各リンクのリンクコストの合計を表している。
【０００４】
図１０の上側図のネットワークでは、ノードＳ−Ｔ間の経路において、リンクコストの合計が２の場合が最小となるルートである。すなわち、そのルートは、Ｓ→Ｘ２→Ｔの１つである。ＦＴ法では、ノードＳ（発信ノード）とノードＴ（着信ノード）と間に出来るだけ多くのルートが選択されるような各リンクのリンクコストを算出するために、ノードＳと隣接ノードＸｉとの間のリンクのリンクコストを変更する。具体的には、図１０の下側図に示すように、リンクコストをＷ１＝３、Ｗ２＝４、Ｗ３＝１と変更する。このことによって、ノードＳからノードＴに至る経路において、リンクコストの合計が５の場合が最小となる。すなわち、ノードＳからノードＴに至るルートが３つ生成される。このようにして、ＦＴ法では、発信ノードと着信ノードとの間に出来るだけ多くのルートが選択されるような各リンクのリンクコストを算出している。
【０００５】
次に、発信ノードと着信ノードとの間に出来るだけ多くのルートが選択されるような各リンクのリンクコストを算出するＦＴ法の効果について、図１１を用いて説明する。図１１は、ＦＴ法の効果を説明する図である。なお、トラヒック量および各リンク容量についてのネットワーク条件は図１１に示す通りである。また、図中に示したリンク利用率は、リンクごとにリンクに収容されるトラヒック量をそのリンクの容量で割った値の百分率で表している。
【０００６】
図１１の比較例１は、ＦＴ法を用いたリンクコストの算出途中（最終結果に至る前）において各リンクのリンクコストが与えられた場合とする。この比較例１では、ノードＢからノードＦに至る経路については、ノードＢからノードＦに至る経路の各リンクのリンクコストの合計が５の場合が最小となるルートとなり、４つのルートが形成されている。しかし、ノードＡからノードＤに至る経路については、ノードＡからノードＤに至る経路の各リンクのリンクコストの合計が４の場合が最小となるルートとなり、１つのルートしか形成されない。そして、リンクごとに算出されるリンク利用率の中で最大となる最大リンク利用率は１００％（ノードＢ−Ｃ間）となる。すなわち、ノードＢ−Ｃ間のリンクに収容されるトラヒック量は、１００（Mbps）＝（１００（Mbps）／４）×２＋５０（Mbps）として算出され、リンク容量は１００（Mbps）であるので、リンク利用率は１００％となる。
【０００７】
比較例１の時点からさらにリンクコスト算出の過程の進んだ図１１の比較例２では、比較例１に比べて、発信ノードと着信ノードとの間に出来るだけ多くのルートが選択されるような各リンクのリンクコストが与えられている。すなわち、ノードＡ−Ｂ間のリンクのリンクコストが２から３に変更され、ノードＡ−Ｆ間のリンクのリンクコストが３から２に変更されている。その結果、ノードＢからノードＦに至る経路については、ノードＢからノードＦに至る経路の各リンクのリンクコストの合計が５の場合が最小となるルートとなり、比較例１と同様に４つのルートが形成されている。また、ノードＡからノードＤに至る経路については、ノードＡからノードＤに至る経路の各リンクのリンクコストの合計が５の場合が最小となるルートとなり、２つのルートが形成される。そして、リンクごとに算出されるリンク利用率の中で最大となる最大リンク利用率は７５％（ノードＢ−Ｃ間）となる。すなわち、ノードＢ−Ｃ間のリンクに収容されるトラヒック量は、７５（Mbps）＝（１００（Mbps）／４）×２＋５０（Mbps）／２として算出され、リンク容量は１００（Mbps）であるので、リンク利用率は１００％となる。
【０００８】
そして、ＦＴ法では、比較例１ではなく、比較例２の方の各リンクのリンクコストを解として選択する。その結果、最大リンク利用率も低減され、ネットワーク全体にわたる資源の利用効率の平準化が達成される。
【０００９】
また、Ｒｏｂｕｓｔ−ＦＴ法は、通常時のトポロジを対象としているＦＴ法を改変し、単一のリンクが故障した場合を含めて各リンクのリンクコストを算出できるようにしたものである。具体的には、Ｒｏｂｕｓｔ−ＦＴ法は、リンクの故障がない通常時およびネットワーク内のいずれか一つ（以降、「単一」と称す。）のリンクが故障した場合の各トポロジにおいて共通に用いる、各リンクのリンクコストを算出する。そして、Ｒｏｂｕｓｔ−ＦＴ法は、リンクの故障がない通常時のトポロジおよび単一のリンクが故障した場合のトポロジごとにそれぞれ最大リンク利用率を算出し、それらの最大リンク利用率の平均値を最小にするリンクコストを選択する。
【非特許文献１】Bernard Fortz，Mikkel Thorup，“Internet Traffic Engineering by Optimizing OSPF Weights”，IEEE INFOCOM 2000，p.519-528 (2000)
【非特許文献２】Bernard Fortz，Mikkel Thorup，“Robust optimization of OSPF/IS-IS Weights”，Proc. INOC 2003，p.225-230 (2003)
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ここで、リンクの故障によって変化したトポロジにおける最適なリンクコストを計算する場合に、ＦＴ法を用いて計算していのでは時間が掛かりすぎるため、即座に故障に対応することができないという問題がある。また、計算時間を省くために、事前にすべての故障パターンについて最適なリンクごとのリンクコストを計算して記憶しておいたとしても、記憶容量が莫大になるという問題がある。
【００１１】
また、Ｒｏｂｕｓｔ−ＦＴ法では、通常時のトポロジと単一リンク故障時のネットワークのトポロジのパターンである故障パターンごとに算出された最大リンク利用率の平均値が最小になる場合の、各リンクのリンクコストを算出するため、ネットワークのトポロジのパターンによっては最大リンク利用率が１００％を超えてしまう（オーバーフロー）場合があるという問題がある。この理由は、Ｒｏｂｕｓｔ−ＦＴ法は、最大リンク利用率の平均値を最小にすることを指標とすることによって、一部の最大リンク利用率がオーバーフローしている場合があったとしても、大多数の故障パターンにおいて最大リンク利用率が小さくなることを選択する手法となっているためである。なお、最大リンク利用率がオーバーフローするということは、リンクが輻輳状態となって、サービス品質を低下させるという問題を生じる。
【００１２】
そこで、本発明の課題は、このような問題を解決するために、ＦＴ法を用いてリンクコストを算出することを前提として、リンク故障時のリンク利用率のオーバーフローを抑制するＩＰ網ルーチング設計を行う技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
前記課題を解決するために、請求項１に記載の発明は、通信ネットワークにおけるリンク故障時のルーチング設計を行う故障を考慮したルーチング設計装置が、リンク故障の発生していないときの前記通信ネットワークのトポロジおよびリンクのリンク容量を含むトポロジ情報と、リンクを流れるトラヒック量に係る交流トラヒック情報とを記憶する記憶部と、前記通信ネットワークのリンク故障時のトポロジを表す故障パターンを生成する故障パターン生成部と、前記トポロジ情報におけるトポロジに基づいて各リンクのリンクコストを算出するリンクコスト計算部と、前記交流トラヒック情報を参照して、前記リンクコスト計算部によって算出された各リンクのリンクコストに基づいて設定される経路を構成するリンクに収容されるトラヒック量を算出し、当該リンクごとに、そのリンクに収容されるトラヒック量を前記記憶部に記憶されているそのリンクのリンク容量で除算して求められる各リンクのリンク利用率を、前記トポロジ情報におけるトポロジおよび前記故障パターンについて算出するリンク利用率計算部と、前記リンク利用率計算部によって算出された前記各リンクのリンク利用率が所定の値を超える超過分の合計を算出し、その超過分の合計に基づいて、前記リンクコスト計算部において算出された各リンクのリンクコストを選択するか否かを判定するリンクコスト選択判定部と、を備え、前記リンクコスト選択判定部が、前記超過分の合計を記憶部に記憶し、前記リンクコスト計算部が、前記トポロジ情報におけるトポロジから取得される２つのノードについて、そのノード間の経路を構成する各リンクのリンクコストの合計が等しくなる経路を２以上生成するようにリンクの新たなリンクコストを算出し、前記リンク利用率計算部が、当該リンクの新たなリンクコストに基づいて設定される経路を構成するリンクのリンク利用率を、前記トポロジ情報におけるトポロジおよび前記故障パターンについてリンクの新たなリンク利用率として算出し、前記リンクコスト選択判定部が、当該リンクの新たなリンク利用率に基づいて、当該リンクの新たなリンク利用率が所定の値を超える超過分の合計を新たな超過分の合計として算出し、当該新たな超過分の合計が前記記憶部に記憶しておいた超過分の合計以下の場合に、前記記憶部の前記超過分の合計を当該新たな超過分の合計に更新し、前記リンクコスト計算部において算出された各リンクのリンクコストを選択すること、を特徴とする。
【００１４】
また、請求項５に記載の発明は、通信ネットワークにおけるリンク故障時のルーチング設計を行う故障を考慮したルーチング設計装置に用いられる故障を考慮したルーチング設計方法であって、  通信ネットワークにおけるリンク故障時のルーチング設計を行う故障を考慮したルーチング設計装置に用いられる故障を考慮したルーチング設計方法であって、前記故障を考慮したルーチング設計装置が、リンク故障の発生していないときの前記通信ネットワークのトポロジおよびリンクのリンク容量を含むトポロジ情報と、リンクを流れるトラヒック量に係る交流トラヒック情報とを記憶する記憶部と、前記通信ネットワークのリンク故障時のトポロジを表す故障パターンを生成する故障パターン生成部と、前記トポロジ情報におけるトポロジに基づいて各リンクのリンクコストを算出するリンクコスト計算部と、前記交流トラヒック情報を参照して、前記リンクコスト計算部によって算出された各リンクのリンクコストに基づいて設定される経路を構成するリンクに収容されるトラヒック量を算出し、当該リンクごとに、そのリンクに収容されるトラヒック量を前記記憶部に記憶されているそのリンクのリンク容量で除算して求められる各リンクのリンク利用率を、前記トポロジ情報におけるトポロジおよび前記故障パターンについて算出するリンク利用率計算部と、前記リンク利用率計算部によって算出された前記各リンクのリンク利用率が所定の値を超える超過分の合計を算出し、その超過分の合計に基づいて、前記リンクコスト計算部において算出された各リンクのリンクコストを選択するか否かを判定するリンクコスト選択判定部と、を備え、前記リンクコスト選択判定部が、前記超過分の合計を記憶部に記憶し、前記リンクコスト計算部が、前記トポロジ情報におけるトポロジから取得される２つのノードについて、そのノード間の経路を構成する各リンクのリンクコストの合計が等しくなる経路を２以上生成するようにリンクの新たなリンクコストを算出し、前記リンク利用率計算部が、当該リンクの新たなリンクコストに基づいて設定される経路を構成するリンクのリンク利用率を、前記トポロジ情報におけるトポロジおよび前記故障パターンについてリンクの新たなリンク利用率として算出し、前記リンクコスト選択判定部が、当該リンクの新たなリンク利用率に基づいて、当該リンクの新たなリンク利用率が所定の値を超える超過分の合計を新たな超過分の合計として算出し、当該新たな超過分の合計が前記記憶部に記憶しておいた超過分の合計以下の場合に、前記記憶部の前記超過分の合計を当該新たな超過分の合計に更新し、前記リンクコスト計算部において算出された各リンクのリンクコストを選択すること、を特徴とする。
【００１５】
このような構成によれば、任意のノード間についてＦＴ法によって新たなリンクコストを算出し、その新たなリンクコストに基づいて設定されるリンクのリンク利用率の超過分の大きさが、前回の超過分の大きさより小さい場合に、その新たなリンクコストを選択している。したがって、リンク利用率のオーバーフローを低減するリンクコストを選択することが可能となる。
【００１６】
請求項２に記載の発明は、請求項１に記載の故障を考慮したルーチング設計装置において、前記リンクコスト選択判定部が、前記トポロジ情報におけるトポロジについて算出された各リンクのリンク利用率の最大値を記憶部に記憶し、前記トポロジ情報におけるトポロジについて前記リンクの新たなリンクコストに基づいて設定される経路を構成するリンクについて算出した前記リンクの新たなリンク利用率の最大値が、前記記憶部に記憶しておいた前記リンクのリンク利用率の最大値より小さいときに、当該リンクの新たなリンク利用率に基づいて、当該リンクの新たなリンク利用率が所定の値を超える超過分の合計を新たな超過分の合計として算出し、当該新たな超過分の合計が前記記憶部に記憶しておいた超過分の合計以下の場合に、前記記憶部の前記超過分の合計を当該新たな超過分の合計に更新し、前記リンクコスト計算部において算出された各リンクのリンクコストを選択すること、を特徴とする。
【００１７】
このような構成によれば、リンク利用率の超過分の合計の比較処理を行う前に、通常時の最大リンク利用率を低減する処理を追加している。したがって、通常時の最大リンク利用率を減少させつつ、リンク利用率のオーバーフローの低減を図ることが可能となる。
【００１８】
請求項３に記載の発明は、請求項１または請求項２に記載の故障を考慮したルーチング設計装置において、前記リンクコスト選択判定部が、前記選択された各リンクのリンクコストを記憶部に記憶し、前記リンクの新たなリンク利用率に基づいて算出した超過分の合計と前記記憶部に記憶しておいた超過分の合計との比較を行った回数をカウントし、その回数が所定の回数に達したときに、前記記憶部に記憶してあった各リンクのリンクコストを解として決定すること、を特徴とする。
【００１９】
このような構成によれば、所定の回数をカウントする簡単な処理によって、通常時の最大リンク利用率を抑制し、リンク利用率のオーバーフローを抑制するリンクコストを決定することが可能となる。
【００２０】
請求項４に記載の発明は、請求項１ないし請求項３のいずれか一項に記載の故障を考慮したルーチング設計装置において、前記故障パターン生成部が、同時に故障が発生しうる前記通信ネットワークのリンクの集合情報であるＳＲＬＧ（Shared Risk Link Group）情報を用いて同時に故障が発生しうるリンクについての故障パターンを生成すること、ノードを構成する部品の故障発生確率の高さに基づいて選択されるリンクに故障が発生したと見做して同時に１以上のリンク故障が発生したものとする故障パターンを生成すること、前記リンク利用率の大きさに基づいて選択されるリンクをリンクに故障が発生したと見做して同時に１以上のリンク故障が発生したものとする故障パターンを生成すること、および、発生した乱数を各リンクに付与して、その乱数の大きさに基づいて選択されるリンクに故障が発生したと見做して同時に１以上のリンク故障が発生したものとする故障パターンを生成すること、のいずれか一つまたはそれらの組み合わせを実行すること、を特徴とする。
【００２１】
ノードや伝送路の仕様に基づいて故障の発生する確率の高いリンク故障およびリンク利用率の高いリンクにおけるリンク故障等に限定したルーチング設計を行うことが可能である。また、乱数を用いてリンク故障を設定することは、例えば、リンク故障の発生する確率がどのリンクにおいてもほぼ等しい場合に有効である。さらに、請求項１ないし請求項４に記載した処理は、リンク利用率の超過分を判定の指標としているため、多重のリンク故障に対しても適用することが可能である。
【００２２】
請求項６に記載の発明は、コンピュータを請求項１ないし請求項４のいずれか一項に記載の故障を考慮したルーチング設計装置を構成する各部として、コンピュータを機能させるための故障を考慮したルーチング設計プログラムとした。
【００２３】
このような経路計算プログラムをインストールされたコンピュータは、このプログラムに基づいた機能を実現することができる。
【発明の効果】
【００２４】
本発明によれば、ネットワーク内のリンク故障時のリンク利用率のオーバーフローを抑制するＩＰ網ルーチング設計を行うことを可能にする。
【発明を実施するための最良の形態】
【００２５】
次に、本実施形態を実施するための最良の形態（以降「実施形態」と称す）について、適宜図面を参照しながら詳細に説明する。
【００２６】
初めに、本実施形態の概要について、説明する。
本実施形態では、ＦＴ法の特徴である、発信ノードと着信ノードとの間に出来るだけ多くのルートが設定されるような各リンクのリンクコストを算出する手法を用いる。そして、Ｒｏｂｕｓｔ−ＦＴ法では用いられていないリンク利用率のオーバーフローの発生を抑制する手法を新たに導入する。具体的には、通常時のネットワークのトポロジについて、ＦＴ法を用いて、各リンクのリンクコストが算出される。その算出した各リンクのリンクコストを用いて、リンクが故障したときの故障パターンの中で考慮すべき故障パターンについて、各リンクのリンク利用率を算出する。そして、考慮すべき故障パターンすべてに対して、各リンクのリンク利用率が所定の値を超える超過分を算出して、その超過分の合計を求める。次に、任意の発信ノードと着信ノードの組を選択して、そのノード間にＦＴ法を適用して、各リンクのリンクコストを変更しつつ、超過分の合計を減少するように、繰り返し演算を行う。最終的に、所定の回数を繰り返した後、最も超過分の合計が小さくなったときの各リンクのリンクコストが、解として求められる。
【００２７】
ここで、本実施形態の特徴である、超過分の合計を減少する処理の流れの具体例を、図１を用いて説明する。図１は、本実施形態の特徴である、超過分の合計を減少する処理の流れの例を説明する図である。なお、図１には、算出途中の例および最終結果の例を示している。
【００２８】
図１に示すように、ネットワーク条件は、実線矢印で示したノードＣからノードＤへのトラヒック量が４６(Mbps)、ノードＢからノードＦへのトラヒック量が１０８(Mbps)であるものとする。また、各リンクのリンク容量は、すべて１００(Mbps)とする。また、ネット−ワーク内に記載の数値は、各リンクのリンクコストを表している。なお、トラヒックは、発信ノードから着信ノードに至る経路の各リンクのリンクコストの合計が最小となる経路をルートとして、流れるものとする。したがって、算出途中の例の故障前（通常時）のネット−ワークでは、ノードＢからノードＦに至るルートは、そのルートの経路となる各リンクのリンクコストの合計が３の場合であって、破線に示すＢ→Ｃ→Ｅ→ＦとＢ→Ａ→Ｆとの２つである。なお、発信ノードから着信ノードに至るルートが複数存在する場合は、そのノード間に流れるトラヒックは各ルートに均等に分散して流れるものとする。
【００２９】
そして、算出途中の例において、故障前（通常時）の場合では、各リンクのリンク利用率はそれぞれ０％，４６％，または５４％となる。同様にして、ノードＢ−Ｆ間のリンクが故障した場合の故障パターンａでは、各リンクのリンク利用率はそれぞれ０％，４６％，または５４％となる。また、ノードＣ−Ｅ間のリンクが故障した場合の故障パターンｂでは、各リンクのリンク利用率はそれぞれ０％，４６％，または１０８％となる。
【００３０】
ここで、各リンクのリンク利用率が所定の値を超える超過分の算出について説明する。図１に示す算出途中の例では、所定の値を１００％に設定したとすると、ノードＢ−Ａ間およびノードＡ−Ｆ間のリンク利用率が１０８％となっているので、超過分の合計は１６％（＝８％×２）として算出される。
【００３１】
そして、最終結果の例では、超過分の合計を減少させる繰り返し演算を行った結果、超過分の合計が０％となる各リンクのリンクコストが算出される。このようにして、本実施形態では、故障パターンを考慮したルーチング設計が行われる。
【００３２】
次に、本実施形態に係るＩＰ網ルーチング設計装置を含むＩＰ網ルーチング設計システムの構成を、図２を用いて説明する。図２は、本実施形態に係るＩＰ網ルーチング設計装置を含むＩＰ網ルーチング設計システムの構成の一例を示す図である。図２に示すように、ＩＰ網ルーチング設計システム１は、ＩＰ網である通信ネットワーク２内に配置されている各ノード９１，９２，９３，９４，９５，９６と、ノードと通信可能に接続される各端末８１，８２，８３およびネットワーク情報取得装置７０と、ネットワーク情報取得装置７０に通信可能に接続されるＩＰ網ルーチング設計装置１０とで構成される。
【００３３】
通信ネットワーク２は、複数のノード９１〜９６および各ノード９１〜９６間を接続するリンクによって構成されている。ネットワーク情報取得装置７０は、通信ネットワーク２内に配置されているノード９４と通信可能に接続されている。そして、ネットワーク情報取得装置７０は、ノード９４から通信ネットワーク２全体のＩＰ網トポロジ情報（リンク容量を含む）および発信ノードから着信ノードに流れるトラヒック量に係る交流トラヒック情報を取得する。また、ネットワーク情報取得装置７０は、ノード９４を介して各ノード９１〜９６の仕様を取得して、取得した仕様に基づいて、同時に故障が発生しうるリンクの集合情報であるＳＲＬＧ（Shared Risk Link Group）情報を生成する。
【００３４】
ＩＰ網ルーチング設計装置１０は、ネットワーク情報取得装置７０から交流トラヒック情報、ＩＰ網トポロジ情報、およびＳＲＬＧ情報等を取得し、通信ネットワーク２内のリンク故障時を考慮してルーチング設計を行う。
各端末８１〜８３は、通信ネットワーク２を介して、相互に情報を送受信する。
各ノード９１〜９６は、ルータ等のネットワーク機器であって、ルーチング設計によって決められたルートに基づいて情報を転送する。
なお、端末の数およびノードの数は、図２に示された数に限られなくとも良い。
【００３５】
次に、ＩＰ網ルーチング設計装置１０の機能について、図３を用いて説明する。図３は、ＩＰ網ルーチング設計装置の機能を示す図である。
図３に示すように、ＩＰ網ルーチング設計装置１０は、処理部２０、記憶部３０、入出力部４０、および通信部５０によって構成される。
【００３６】
まず、処理部２０について説明する。
処理部２０は、故障パターン生成部２１、リンクコスト計算部２２、リンク利用率計算部２３、およびリンクコスト選択判定部２４を含む。
故障パターン生成部２１は、ＩＰ網トポロジ情報やＳＲＬＧ情報等を用いて、ＩＰ網トポロジ情報やＳＲＬＧ情報等から生成される救済対象のリンク構成（バックアップ用のリンク）を加味して、リンク故障時の通信ネットワーク２のトポロジである故障パターンを生成する。なお、故障パターンの生成の詳細については、後記する。
【００３７】
リンクコスト計算部２２は、ＦＴ法を用いて、リンク故障がないとき（通常時）の通信ネットワーク２のトポロジについて、各リンクのリンクコストを算出する。具体的には、リンクコスト計算部２２は、任意の発信ノードと着信ノードの組について、その発信ノードからその着信ノードに至る経路上にあるその発信ノードとその隣接ノードとの間のリンクのリンクコストを変更して、その発信ノードとその着信ノードとの間に出来るだけ多くのルート（その発信ノードとその着信ノードとの間の経路を構成するリンクのリンクコストの合計が最小となる経路）を形成するように、リンクのリンクコストを変更する。
【００３８】
リンク利用率計算部２３は、リンクごとに、リンクに収容されるトラヒック量をそのリンク容量で除算した値の百分率をリンク利用率として算出する。ここで、リンクに収容されるトラヒック量とは、ある一つのリンクについて着目した場合、そのリンクを同じ方向に流れるトラヒックであって、発信ノードと着信ノードの組すべてについて、そのリンクを流れるトラヒック量を合計したものである。すなわち、図１の故障前（通常時）の最終結果の例を用いて具体的に説明すると、例えば、ノードＣ−Ｄ間のリンクには、ノードＢ−Ｆ間のトラヒック量３６（Mbps）（＝１０８（Mbps）／３）とノードＣ−Ｄ間のトラヒック量４６（Mbps）とが流れるので、合計８２（Mbps）のトラヒック量と算出される。
【００３９】
リンクコスト選択判定部２４は、考慮すべき故障パターンについて、リンク利用率計算部２３によって算出された各リンクのリンク利用率が、所定の値を超えた超過分の合計を算出し、その超過分の合計を指標として、リンクコスト計算部２２において算出されたリンクコストを選択するか否かを判定する。
【００４０】
なお、処理部２０は、演算処理等を実行する図示しないＣＰＵ（Central Processing Unit）と、このＣＰＵが演算処理等に用いる図示しないメインメモリとによって構成される。そして、処理部２０は、アプリケーションプログラムがメインメモリに展開され、ＣＰＵが、それを実行することにより、各部（符号２１〜２４）の機能を具現化する。メインメモリは、ＲＡＭ（Random Access Memory）等により実現される。
【００４１】
次に、記憶部３０について説明する。
記憶部３０は、交流トラヒック情報３１、ＩＰ網トポロジ情報３２、ＳＲＬＧ情報３３、および故障パターン情報３４を含む情報を記憶している。また、記憶部３０は、処理部２０が機能するためのアプリケーションプログラムも記憶している。
なお、記憶部３０は、ＨＤＤ（Hard Disk Drive）等の記憶装置によって実現される。
【００４２】
交流トラヒック情報３１は、ネットワーク情報取得装置７０から取得されるものであって、通信ネットワーク２内に配置されているノード９１〜９６間で発生するトラヒック量に係る情報を記憶している。なお、図４は、交流トラヒック情報の一例を示している。図４に示すように、発信ノードと着信ノードとトラヒック量（Mbps）とが関連付けられて記憶されている。
【００４３】
ＩＰ網トポロジ情報３２は、ネットワーク情報取得装置７０から取得されるものであって、通信ネットワーク２のトポロジに係る情報およびリンクごとのリンク容量に係る情報（リンク容量情報３２１）を記憶している。なお、図５は、ＩＰトポロジ情報の一例を示している。図５に示すように、リンクＩＤごとに、発信ノードと着信ノードとリンク容量（Mbps）とが関連付けられて記憶されている。
【００４４】
ＳＲＬＧ情報３３は、図６に示すように、リンクＩＤとＳＲＬＧ識別情報とが関連付けられて記憶されている。なお、図６は、ＳＲＬＧ情報の一例を示している。そして、ＳＲＬＧ識別情報が同じ場合、同時に故障が発生しうるリンクであることを表している。例えば、同一ノードや同一回線カードに収容されるリンクや、下位レイヤの同一回線に収容されるリンク等は、それらのノードや回線等の故障によって同時に故障する。
【００４５】
故障パターン情報３４は、故障パターン生成部２１によって生成され、通信ネットワーク２のトポロジの中から、特定のリンクに故障が発生した場合に生成される故障パターンのトポロジを記憶している。なお、図７は、故障パターン情報の一例を示している。図７に示すように、故障パターンを識別する故障パターンＩＤと故障パターンのトポロジとが関連付けられて記憶されている。
【００４６】
入出力部４０は、ＩＰ網ルーチング設計装置１０に接続されるキーボードやマウス等の図示しない入力装置、液晶モニタ等の図示しない出力装置とのインタフェースである。入出力部４０は、入力装置から入力された情報を処理部２０に伝達し、処理部２０によって処理された情報を出力装置に出力する機能を有する。
通信部５０は、ネットワーク情報取得装置７０と通信するときの通信インタフェースである。
【００４７】
次に、ＩＰ網ルーチング設計装置１０の処理の流れについて、図８を用いて説明する（適宜図３参照）。図８は、ＩＰ網ルーチング設計装置の処理の流れを示す図である。
まず、ステップＳ３０１では、ＩＰ網ルーチング設計装置１０の故障パターン生成部２１は、故障パターンに係る情報を生成し、生成した故障パターンに係る情報を記憶部３０の故障パターン情報３４に格納する。
【００４８】
ここで、故障パターン生成部２１において生成される故障パターンの詳細について、以下に説明する。
（１）全リンクのいずれかに故障が発生したときの故障パターン
通信ネットワーク２内において、故障しうるリンクについてすべての組み合わせが生成される。
（２）単一リンクに故障が発生したときの故障パターン
通信ネットワーク２内において、任意の１つのリンクに故障が発生するものと見做して、故障パターンが生成される。
（３）同時に複数リンクに故障が発生したときの故障パターン
ＳＲＬＧ情報３３に基づいて、同時に故障となる可能性の高いリンクに故障が発生したものと見做して、多重リンク故障パターンが生成される。なお、ＳＲＬＧ情報３３に、あるリンクの故障発生時に、その故障したリンクのバックアップ用のリンクが設定されている場合、そのバックアップ用のリンクを考慮して、多重リンク故障パターンを生成してもよい。または、乱数を発生させて、発生させた乱数を各リンクに対応付けて、乱数の大きさに基づいて選択された数値に対応付けられたリンクを故障と見做して、多重リンク故障パターンが生成される。例えば、同時に２つのリンクに故障が発生すると見做す二重リンク故障パターンの場合、乱数の大きさの上位（または下位や特定の数値）２つに対応付けられたリンクに故障が発生するものと見做す。同時に３つのリンクに故障が発生すると見做す三重故障パターンの場合、乱数の大きさの上位（または下位や特定の数値）３つに対応付けられたリンクに故障が発生するものと見做す。
（４）リンク利用率およびリンクの故障発生確率等に基づいて生成される故障パターン
交流トラヒック情報３１を用いて、各リンクのリンク利用率を算出し、リンク利用率の高いリンクに故障が発生したと見做して、故障パターンが生成される。または、ルータや回線カードの仕様に記載されている故障発生確率に基づいて、故障発生確率の高いリンクに故障が発生したと見做して故障パターンが生成される。
【００４９】
図８に戻って、ステップＳ３０２では、リンクコスト計算部２２が、通信ネットワーク２内の各リンクのリンクコストの初期値（Ｗ０）を設定する。なお、各リンクのリンクコストの初期値は、例えば、リンク容量の逆数等である。
ステップＳ３０３では、リンクコスト計算部２２が、Ｗ０を繰り返し演算用の変数Ｗａに代入する。
ステップＳ３０４では、リンク利用率計算部２３が、変数Ｗａに示されるリンクコストに基づいて、通常時（故障がない時）の通信ネットワーク２のトポロジにおける各リンクのリンク利用率を算出し、その算出した各リンクのリンク利用率の中から最大値となる最大リンク利用率ＭＵ（Ｗａ）を抽出する。そして、リンク利用率計算部２３は、抽出した最大リンク利用率ＭＵ（Ｗａ）を記憶部３０に記憶する。
【００５０】
ステップＳ３０５では、リンクコスト選択判定部２４が、故障パターン情報３４に示される故障パターンのうち、リンク故障として考慮すべき故障パターンについて、変数Ｗａに示されるリンクコストに基づいて算出された各リンクのリンク利用率を算出し、その算出した各リンクのリンク利用率が所定の値を超える超過分の合計を算出する。なお、超過分の合計は、Ｗａ超過分と表記する。また、超過分を算出するときは、例えば、所定の値を１００％とした場合、各リンクのリンク利用率の内の１つだけが１０８％のときには、超過分を８％と算出する。そして、リンクコスト選択判定部２４は、算出したＷａ超過分を記憶部３０に記憶する。
【００５１】
ステップＳ３０６では、リンクコスト計算部２２が、任意の発信ノードと着信ノードとの組を一つ選択して、その選択したノード間に形成される経路に対して、ＦＴ法を適用して、出来る限り多くの複数のルート（経路となる各リンクのリンクコストが最小となる経路）を形成するように、新たなリンクコストを算出する。なお、任意の発信ノードと着信ノードとの組は、発生させた乱数を各ノードに対応付けて、乱数の大きさの上位２つ、下位２つ、または指定された数字２つに対応付けられた乱数に対応づけられたノードを選択することによって決定される。
【００５２】
ステップＳ３０７では、リンクコスト計算部２２が、ステップＳ３０６において算出した新たなリンクコスト（実行結果）を変数Ｗｂに代入する。
ステップＳ３０８では、リンク利用率計算部２３が、変数Ｗｂに示されるリンクコストに基づいて、通常時（故障がない時）の通信ネットワーク２のトポロジにおける各リンクのリンク利用率を算出し、その算出した各リンクのリンク利用率の中から最大値となる最大リンク利用率ＭＵ（Ｗｂ）を抽出する。
【００５３】
ステップＳ３０９では、リンクコスト選択判定部２４が、最大リンク利用率ＭＵ（Ｗｂ）が最大リンク利用率ＭＵ（Ｗａ）より小さいか否かを判定する。そして、最大リンク利用率ＭＵ（Ｗｂ）が最大リンク利用率ＭＵ（Ｗａ）以上の場合（ステップＳ３０９でＮｏ）は、処理はステップＳ３１３へ進む。また、最大リンク利用率ＭＵ（Ｗｂ）が最大リンク利用率ＭＵ（Ｗａ）より小さい場合（ステップＳ３０９でＹｅｓ）は、処理はステップＳ３１０へ進む。
【００５４】
ステップＳ３１０では、リンクコスト選択判定部２４が、考慮すべき故障パターンすべてについて、変数Ｗｂに示されるリンクコストに基づいて算出された各リンクのリンク利用率が所定の値を超える超過分の合計を算出する。なお、超過分の合計は、Ｗｂ超過分と表記する。また、超過分を算出するときは、例えば、所定の値を１００％とした場合、各リンクのリンク利用率の内の２つが１０４％および１０６％であったときには、超過分を１０％と算出する。そして、リンクコスト選択判定部２４は、算出したＷｂ超過分を記憶部３０に記憶する。
【００５５】
ステップＳ３１１では、リンクコスト選択判定部２４が、Ｗｂ超過分がＷａ超過分以下か否かを判定する。そして、Ｗｂ超過分がＷａ超過分以下の場合（ステップＳ３１１でＹｅｓ）、処理はステップＳ３１２へ進む。
ステップＳ３１２では、リンクコスト選択判定部２４が、ＷｂをＷａに代入し、ＭＵ（Ｗｂ）をＭＵ（Ｗａ）に代入し、Ｗｂ超過分をＷａ超過分に代入し、代入されたＷａ超過分を記憶部３０に記憶する。そして、処理はステップＳ３１３へ進む。
なお、ステップＳ３１１において、Ｗｂ超過分がＷａ超過分より大きい場合（ステップＳ３１１でＮｏ）、処理はステップＳ３１３へ進む。
【００５６】
ステップＳ３１３では、リンクコスト計算部２２が、所定の回数を実行したか否かを判定する。なお、所定の回数のカウントは、判定を行うごとにカウンタの数値を＋１増加することによって行われる。そして、所定の回数を実行していない場合（ステップＳ３１３でＮｏ）、処理はステップＳ３０６へ戻る。また、所定の回数を実行している場合（ステップＳ３１３でＹｅｓ）、処理はステップＳ３１４へ進む。
ステップＳ３１４では、リンクコスト計算部２２が、変数Ｗａに格納されている値を最終的な解としてリンクコストに決定する。
【００５７】
なお、本実施形態では、ステップＳ３１３において、所定の回数によって、処理を打ち切る構成としている。この理由は、シミュレーションを行った結果、繰り返し演算を所定の回数行えば、変数Ｗａに格納されるリンクコストの値が変化しない状態に収束することが分かったためである。なお、ノード数が多くなるに従って大きな所定の回数を用いることによって、変数Ｗａに格納されるリンクコストの値が変化しない状態に収束させることができる。
【００５８】
（Ｒｏｂｕｓｔ−ＦＴ法および本実施形態に記載の提案法の検証結果）
ここで、Ｒｏｂｕｓｔ−ＦＴ法および本実施形態に記載の提案法のシミュレーションによる検証結果について、図９を用いて説明する。図９は、Ｒｏｂｕｓｔ−ＦＴ法および本実施形態に記載の提案法の検証結果を説明する図である。
【００５９】
図９には、第１のルーチング例および第２のルーチング例を示している。第１のルーチング例は、Ｒｏｂｕｓｔ−ＦＴ法を用いた場合の結果を示している。そして、第２のルーチング例は、本実施形態に記載の提案法を用いた場合の結果を示している。そして、図９に示した例は、シミュレーションから明らかになった現象を模式化して表したものである。
【００６０】
図９に示すように、ネットワーク条件は、実線矢印で示したノードＣからノードＤに至るトラヒック量が４６(Mbps)、ノードＢからノードＦに至るトラヒック量が１０８(Mbps)であるものとする。また、各リンクのリンク容量は、すべて１００(Mbps)とする。また、ネット−ワーク内に記載の数値は、それぞれの方法によって決定された各リンクのリンクコストを表している。
【００６１】
なお、トラヒックは、発信ノードから着信ノードに至る経路の各リンクのリンクコストの合計が最小となるルートに流れるものとする。したがって、第１のルーチング例の故障前（通常時）のネット−ワークでは、ノードＢからノードＦに至るルートは、そのルートの経路となる各リンクのリンクコストの合計が３の場合であって、破線に示すＢ→Ｃ→Ｅ→ＦとＢ→Ａ→Ｆの２つである。なお、発信ノードから着信ノードに至るルートが複数存在する場合は、そのノード間に流れるトラヒックは各ルートに均等に分散して流れるものとする。
したがって、故障前（通常時）のネット−ワークについて、第１のルーチング例では、最大リンク利用率は５４％となり、第２のルーチング例では、最大リンク利用率は８２％となる。
【００６２】
次に、単一リンク故障が発生したパターンにおける最大リンク利用率について説明する。
故障パターンａは、ノードＢ−Ｆ間のリンクに故障が発生したと見做した場合である。この故障パターンａの場合、第１のルーチング例における最大リンク利用率は５４％となり、第２のルーチング例における最大リンク利用率は８２％となる。
次に、故障パターンｂは、ノードＣ−Ｅ間のリンクに故障が発生したと見做した場合である。この故障パターンｂの場合、第１のルーチング例における最大リンク利用率は１０８％となり、第２のルーチング例における最大リンク利用率は１００％となる。
【００６３】
ここで、Ｒｏｂｕｓｔ−ＦＴ法と本実施形態に記載の提案法との効果の比較について説明する。
Ｒｏｂｕｓｔ−ＦＴ法では、故障前（通常時）のネット−ワークおよび単一リンク故障が発生したネット−ワークのそれぞれの最大リンク利用率の平均値を算出して、その平均値が最小となるときのリンクコストが採用される。そのため、Ｒｏｂｕｓｔ−ＦＴ法では、解として、最大リンク利用率の平均値が８８％となる第２のルーチング例は採用されず、最大リンク利用率の平均値が７２％となる第１のルーチング例が採用される。しかし、第１のルーチング例の故障パターンｂに示されるように、最大リンク利用率が１００％を超えてしまう場合が起きるという問題がある。
それに対して、本実施形態に記載の提案法では、超過分の合計を減少させる処理を行っているので（図のステップＳ３１１）、第２のルーチング例の故障パターンｂに示すように、最大リンク利用率を１００％以内に収めることが可能となる。また、本実施形態に記載の提案法では、さらに、ステップＳ３０９によって、通常時のネットワークにおける最大リンク利用率も低減することが可能である。
【００６４】
以上、本実施形態のＩＰ網ルーチング設計装置１０によれば、リンク利用率のオーバーフローを抑制しつつ、通常時および１以上のリンクの故障時のネットワークのトポロジにおける各最大リンク利用率を低減するＩＰ網ルーチング設計を行うことが可能となる。
【００６５】
なお、本実施形態は、これらに限定されるものではなく、その趣旨を変えない範囲で実施することができる。
例えば、図８に示すステップＳ３１３において、所定の回数によって、処理を打ち切る構成としているが、変数Ｗａに格納されるリンクコストの値の変化が所定の値以下となったときに処理を打ち切ってもよい。
また、図８に示すステップＳ３０４，Ｓ３０８，Ｓ３０９が省略されても、故障時の最大リンク利用率を１００％以内に収めることは可能である。
【００６６】
また、本実施形態において、ＩＰ網ルーチング設計装置１０（図３参照）の各部の処理について説明したが、これらの処理は、ＩＰ網ルーチング設計装置１０をコンピュータで実現したときに搭載されるプログラムによって実現されてもよい。このプログラムは、通信回線を介して提供することもできるし、ＣＤ−ＲＯＭ等の記録媒体に書き込んで配布することも可能である。
【図面の簡単な説明】
【００６７】
【図１】本実施形態の特徴である、超過分の合計を減少する処理の流れの例を説明する図である。
【図２】本実施形態に係るＩＰ網ルーチング設計装置を含むＩＰ網ルーチング設計システムの構成の一例を示す図である。
【図３】ＩＰ網ルーチング設計装置の機能を示す図である。
【図４】交流トラヒック情報の一例を示す図である。
【図５】ＩＰトポロジ情報の一例を示す図である。
【図６】ＳＲＬＧ情報の一例を示す図である。
【図７】故障パターン情報の一例を示す図である。
【図８】ＩＰ網ルーチング設計装置の処理の流れを示す図である。
【図９】Ｒｏｂｕｓｔ−ＦＴ法および本実施形態に記載の提案法の検証結果を説明する図である。
【図１０】ＦＴ法の概念を説明する図である。
【図１１】ＦＴ法の効果を説明する図である。
【符号の説明】
【００６８】
１      ＩＰ網ルーチング設計システム
１０    ＩＰ網ルーチング設計装置
２０    処理部
２１    故障パターン生成部
２２    リンクコスト計算部
２３    リンク利用率計算部
２４    リンクコスト選択判定部
３０    記憶部
３１    交流トラヒック情報
３２    ＩＰ網トポロジ情報
３３    ＳＲＬＧ情報
３４    故障パターン情報
３２１  リンク容量情報
【図１】
2010130382.tif 000003
【図２】
2010130382.tif 000004
【図３】
2010130382.tif 000005
【図４】
2010130382.tif 000006
【図５】
2010130382.tif 000007
【図６】
2010130382.tif 000008
【図７】
2010130382.tif 000009
【図８】
2010130382.tif 000010
【図９】
2010130382.tif 000011
【図１０】
2010130382.tif 000012
【図１１】
2010130382.tif 000013