リンク増設箇所最適選択システムと方法およびプログラム
【課題】ネットワークにおける単一リンク障害時の最大経路長増加率を抑制する最適なリンク増設箇所の選択を行うことを可能にする。
【解決手段】入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを記憶装置に格納する入力部１０１と、単一リンク障害による経路長の増加率を全て上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、記憶装置に記憶したネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択するリンク増設箇所選択部１０２と、リンク増設箇所選択部１０２が選択したリンク増設箇所を出力装置に出力する出力部とを有し、最小限のリンク増設でネットワークにおける所望の連結度での対障害性と経路長増加率を満たすことを可能とし、ネットワークの高信頼化および高品質化を図る。
【解決手段】入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを記憶装置に格納する入力部１０１と、単一リンク障害による経路長の増加率を全て上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、記憶装置に記憶したネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択するリンク増設箇所選択部１０２と、リンク増設箇所選択部１０２が選択したリンク増設箇所を出力装置に出力する出力部とを有し、最小限のリンク増設でネットワークにおける所望の連結度での対障害性と経路長増加率を満たすことを可能とし、ネットワークの高信頼化および高品質化を図る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークで発生したリンク障害時に代替えの経路を選択する技術に係り、特に、単一リンク障害時に対応して増設するリンクの増設箇所の選択を、経路長の増加率を抑えて行うことで、高信頼かつ高品質なネットワークを構成するのに好適な技術に関するものである。
【背景技術】
【０００２】
インターネットをはじめ、通信ネットワーク（ＮＷ）が社会において必要不可欠なインフラとなった現在、ＮＷには高い信頼性が求められている。特に、大規模なＮＷでは、様々な要因によるノードやリンクの故障や重い輻輳の発生は避けられないため、そのような障害が発生しても各ノード間の通信を維持し続けるための設計および制御が必要である。
【０００３】
このような観点から、障害時には代替経路を利用できるようにするために、後述するグラフ理論を用いた高い連結度のＮＷの設計に関する研究がなされている。例えば、同時に故障するリンクは一つだけとする単一リンク故障（ＳＬＦ：Ｓｉｎｇｌｅ Ｌｉｎｋ Ｆａｉｌｕｒｅ）を仮定し、ＳＬＦ時にも通信が途絶しないようにするために、ＮＷを２辺連結グラフとなるように設計することが、実際にも一般的に行われている。尚、２辺連結グラフとは、連結度が２であるグラフのことである。
【０００４】
このように、インターネットサービスプロバイダ（ＩＳＰ）のＮＷトポロジを、高い連結度のグラフとなるように構成することによって高い信頼性を得ることが可能である。
【０００５】
しかし、この場合、障害時に通常時の経路から代替経路に変化した際に、経路長（フロー長）が大きく延びてしまう可能性があり、影響を受ける膨大な数の通信の全てにおいて、通信品質の劣化を引き起こす可能性があることが指摘されている。
【０００６】
従って、実際のＮＷトポロジには、単に代替経路が存在するだけではなく、ＳＬＦ時の経路長の増加率が小さいことも必要である。
【０００７】
インターネットにおいては、経路を自由に決定することはできず、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）などルーティングプロトコルによって決定されるため、経路を適切に定めることで経路長の増加率を設定するという技術を取ることはできない。従って、ＮＷトポロジを変更することによって経路長増加率を設定しなければならない。
【０００８】
通常、大規模なＮＷは、最初から構築することはなく、既に構築・運用されている場合が多い。従って、既設ＮＷ全体を再構築し直すことは非現実的であり、そのため、既存のネットワークに最小限の増設を行うことで条件を満たすようにすることが必要となる。
【０００９】
すなわち、最小限のリンク増設によって、所望の連結度とＳＬＦ時の経路長増加率を満たすＮＷを構成することがＮＷ設計の目的となる。
【００１０】
以上の技術については、例えば非特許文献１等に記載されている。
【００１１】
ＮＷ設計に関しては、通信分野だけではなく、グラフ理論や最適化理論の研究分野も含め、これまで膨大な研究がなされてきている。その中には、上述したように、辺を付加することにより連結度に関する条件を満たすグラフを構成するタイプの問題がある。
【００１２】
連結度とは、全ての２点間で辺を共有しない経路の本数の最大値であり、辺連結度（点連結度）がｋであれば、グラフの任意の２点間に辺独立（点独立）なｋ本の路が存在する。辺独立な路とは、辺を共有しない経路のことである。
【００１３】
所望の連結度にするために最小本数の辺を付加する箇所を決定することによって、リンクやノードの障害時でも代替経路を利用して通信を継続できるようにすることが目的である。
【００１４】
辺連結度を増加させる問題に関しては多項式時間アルゴリズムが知られているが、点連結度増加問題に関してはＮＰ完全であることが知られている。尚、連結度増加問題においては、経路長についての制約も含めて考えられているものはない。
【００１５】
また、辺付加によって直径を抑制する問題についての検討も見られる。直径とは、グラフの任意の２点間の最短路長の最大値のことである。グラフの直径が小さくなるように設計することで、ＮＷ上での任意の２点間の通信遅延を小さくすることができる。
【００１６】
この問題は一般にＮＰ完全であり、グラフが木である場合など限られた場合についての多項式時間アルゴリズムが知られている。
【００１７】
この問題では経路長を考慮しているものの、連結度についても同時に考慮しているものはない。従って、１本のリンクが故障しただけで通信が途絶えてしまう可能性があり、耐故障性については必ずしも高くできるとは限らない。
【００１８】
他にも、与えられたグラフに辺を付加することによって、区間グラフやコーダルグラフ、ハミルトングラフにする問題などが知られている。いずれも経路長の変化に関する制約は含まれていない。尚、これらは全てＮＰ完全である。
【００１９】
以上から、これまでの問題は、経路長の増加率を抑制するという観点から辺付加を行う問題にそのまま適用することはできず、新たに検討する必要がある。
【００２０】
尚、このようなＮＷ設計に関してのグラフ理論や最適化理論に関しては、例えば、非特許文献２に記載されている。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】Ｎ．Ｋａｍｉｙａｍａ ａｎｄ Ｈ．Ｍｉｗａ，“Ｃｏｎｎｅｃｔｉｖｉｔｙ ａｎｄ Ｓｔａｂｉｌｉｔｙ Ａｎａｌｙｓｉｓ ａｇａｉｎｓｔ Ｆａｉｌｕｒｅｓ ｆｏｒ ＩＳＰ Ｂａｃｋｂｏｎｅ Ｎｅｔｗｏｒｋｓ”，ＩＥＥＥ ＧＬＯＢＥＣＯＭ ０８．
【非特許文献２】茨木俊秀，“情報学のための離散数学”，昭晃堂，２００４．
【発明の概要】
【発明が解決しようとする課題】
【００２２】
解決しようとする問題点は、従来の技術では、ネットワークにおける単一リンク障害時の最大経路長増加率を抑制する最適なリンク増設箇所の選択を行うことができない点である。
【００２３】
本発明の目的は、これら従来技術の課題を解決し、最小限のリンク増設で、ネットワークにおける所望の連結度での対障害性と経路長増加率を満たすことを可能とし、ネットワークの高信頼化および高品質化を図ることである。
【課題を解決するための手段】
【００２４】
上記目的を達成するため、本発明では、（１）ネットワークのトポロジＧと単一リンク障害時の最大経路長増加率の設計上限Ｋが与えられたときに、最小数のリンク増設箇所を選択する。また、（２）ネットワークのトポロジＧと単一リンク障害時の最大経路長増加率の設計上限Ｋおよびリンクを増設可能な箇所の集合が与えられたときに、最小数のリンク増設箇所を選択する。より具体的には、（３）グラフＧに対して辺ｅ∈Ｅの単一リンク障害による経路長増加率がＫ以下の辺を充足辺と呼び、さもなければ未充足辺と呼び、未充足辺集合をＵとし、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺にできるとき、辺ｆを候補辺と呼び、辺ｆによって充足辺にできる未充足辺の集合をＳｆとし、付加が可能な点の対の集合（付加可能点対集合）に候補辺集合が含まれると仮定し、付加辺は候補辺からのみ選ぶものとするとき、未充足辺集合Ｕと、この集合Ｕの部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合が得られることから、集合被覆問題に対する近似アルゴリズムを利用することで、付加辺集合Ｃを得て、この付加辺集合Ｃを最小数のリンク増設箇所として選択する。尚、（４）付加可能点対集合に候補辺集合Ｓが含まれ、付加辺は候補辺集合からのみ選ぶものと仮定するとき、後述のＰＬＥＡＰの経路長増加率制約を満たす付加辺集合を出力する。また、（５）このアルゴリズムで付加される辺の本数は、最小の本数のｌｏｇ|Ｕ|＋１倍以下であり、計算量は、未充足辺数|Ｕ|、候補辺数|Ｓ|の時、Ｏ（|Ｕ|×|Ｓ|）である。
【発明の効果】
【００２５】
本発明によれば、ネットワークのトポロジ情報（グラフＧ）と単一リンク障害時の最大経路長増加率の設計上限値（Ｋ）が与えられたときに、最大経路長増加率の設計上限値（Ｋ）を満足する最小数のリンク増設箇所を選択することができ、高信頼かつ高品質なネットワークを構成することが可能である。
【図面の簡単な説明】
【００２６】
【図１】図１は、本発明に係るリンク増設箇所最適選択システムの構成例を示すブロック図である。
【図２】図２は、図１におけるリンク増設箇所最適選択システムの本発明に係るリンク増設箇所最適選択方法例を示すフローチャートである。
【図３】図３は、図１におけるリンク増設箇所最適選択システムの処理対象となるネットワークの特性例を示す説明図である。
【図４】図４は、図１におけるリンク増設箇所最適選択システムの処理効果例を示す説明図である。
【発明を実施するための形態】
【００２７】
以下、図を用いて本発明を実施するための形態例を説明する。図１は、本発明に係るリンク増設箇所最適選択システムの構成例を示すブロック図であって、本例のリンク増設箇所最適選択システムは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリを具備したコンピュータ構成からなり、プログラムされたコンピュータ処理によって、ネットワークのトポロジＧと単一リンク障害時の最大経路長増加率の設計上限Ｋとが与えられたときに、最小数のリンク増設箇所を選択するものであって、プログラムされたコンピュータ処理を実行する機能として、トポロジ情報・最大経路長増加率の許容上限値入力部１０１と、リンク増設箇所選択部１０２、リンク増設箇所出力部１０３を有する。
【００２８】
トポロジ情報・最大経路長増加率の許容上限値入力部１０１は、図示していないキーボードやマウス等の入力装置を用いた操作者の入力操作により、例えば、外部記憶媒体、あるいは、ネットワークを介したオンラインで入力される、処理対象のネットワークのトポロジ情報（グラフＧ）と単一リンク障害時の最大経路長増加率の許容上限値（許容上限Ｋ）等の設計パラメタを入力し、図示していない記憶装置に格納する。
【００２９】
リンク増設箇所選択部１０２は、記憶装置から、トポロジ情報・最大経路長増加率の許容上限値入力部１０１が入力した、トポロジ情報（グラフＧ）と設計上限値情報（許容上限Ｋ）を読み出し、このトポロジ情報（グラフＧ）と設計上限値情報（許容上限Ｋ）を用いて、本発明に係る処理、例えば、集合被覆問題に対する近似アルゴリズムにより、許容上限Ｋを満足する付加辺集合（Ｃ）を算出し、最小数のリンク増設箇所として選択する処理を実行する。
【００３０】
リンク増設箇所出力部１０３は、リンク増設箇所選択部１０２によるリンク増設箇所の選択結果を、ＣＲＴ（Ｃａｔｈｏｄｅ Ｌａｙ Ｔｕｂｅ）やＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）等の表示装置に表示する、もしくは、プリンタで印字する、あるいは、記憶媒体に記録する、オンライン上の他のコンピュータ装置等に送信する等の出力処理を行う。
【００３１】
また、リンク増設箇所選択部１０２は、プログラムされたコンピュータ処理を実行する機能として、第１の未充足辺集合取得部１０２ａと、第２の未充足辺集合取得部１０２ｂ、第１の付加辺集合算出部１０２ｃ、および、第２の付加辺集合算出部１０２ｄを有する。
【００３２】
第１の未充足辺集合取得部１０２ａは、グラフＧに対して辺ｅ∈Ｅの単一リンク障害による経路長の増加率が、設計上限Ｋ以下の辺（充足辺）と設計上限Ｋ以上の辺（未充足辺）を算出して、未充足辺の集合Ｕを求める。
【００３３】
第２の未充足辺集合取得部１０２ｂは、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺にできる辺候補辺ｆを算出して、この辺候補辺ｆによって充足辺にできる未充足辺の集合Ｓｆを求める。
【００３４】
第１の付加辺集合算出部１０２ｃは、付加可能点対集合に候補辺集合が含まれると仮定し、付加辺は候補辺からのみ選ぶとの条件で、未充足辺の集合Ｕと部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合が得られることから、集合被覆問題に対する近似アルゴリズムを利用することで、付加辺集合Ｃを算出する。
【００３５】
第２の付加辺集合算出部１０２ｄは、
付加可能点対集合に候補辺集合Ｓが含まれ、付加辺は候補辺集合からのみ選ぶものと仮定するとき、後述のＰＬＥＡＰの経路長増加率制約を満たす付加辺集合を算出する。
【００３６】
以下、このような構成からなるリンク増設箇所最適選択システムによる、本発明に係る、単一リンク障害時の最大経路長増加率を抑制するのに最適な、リンク増設箇所の選択技術について説明する。
【００３７】
上述したように、トポロジ情報・最大経路長増加率の許容上限値入力部１０１は、処理対象のネットワークのトポロジ情報（グラフＧ）と設計パラメタ（許容上限Ｋ）を入力する。トポロジ情報の例としては、ノードｉとノードｊ間にリンクが存在する場合には「１」を、しない場合には「０」をとる２値変数を要素に持つ行列が考えられ、単一リンク障害時の経路長増加率の許容最大値Ｋとしては、任意の整数が考えられる（例：Ｋ＝５）。
【００３８】
リンク増設箇所選択部１０２は、トポロジ情報・最大経路長増加率の許容上限値入力部１０１が入力した、トポロジ情報（グラフＧ）と設計パラメタ（許容上限Ｋ）を用いて、効果的なリンク増設箇所を選択する。
【００３９】
そして、リンク増設箇所出力部１０３は、リンク増設箇所選択部１０２により得られた増設箇所が出力する。
【００４０】
リンク増設箇所出力部１０３が出力するデータは、リンクを追加する場所の集合であり、データフォーマットとしては、例えば、ノードｉとノードｊ間にリンクを追加する場合に「１」を、しない場合に「０」をとる２値変数を要素にもつ行列が考えられる。
【００４１】
リンク増設箇所選択部１０２は、第１の未充足辺集合取得部１０２ａにより、グラフＧにおいて、辺ｅ∈ＥのＳＬＦによる経路長増加率がＫ以下の辺（充足辺）と、Ｋ以上の辺（未充足辺）を特定し、未充足辺の集合Ｕを求める。
【００４２】
また、リンク増設箇所選択部１０２は、第２の未充足辺集合取得部１０２ｂにより、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺にできる、辺（候補辺ｆ）を特定し、この候補辺ｆの付加によって充足辺にできる未充足辺の集合Ｓｆを求める。
【００４３】
そして、第１の付加辺集合算出部１０２ｃにより、付加可能点対集合に候補辺ｆの集合が含まれると仮定し、また、付加辺は、候補辺ｆからのみ選ぶものとし、未充足辺集合Ｕと部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合Ｃを得る。
【００４４】
また、第２の付加辺集合算出部１０２ｄにより、集合被覆問題に対する近似アルゴリズムを利用することで、付加辺集合Ｃを得る。
【００４５】
以下、このような、本発明に係る単一リンク障害時の最大経路長増加率を抑制するリンク増設箇所の選択技術について、［（１）経路長増加率抑制リンク付加問題］、［（２）経路長増加率抑制リンク付加問題（ＰＬＥＡＰ）］の順で、詳細を説明する。
【００４６】
［（１）経路長増加率抑制リンク付加問題］
【００４７】
まず、ＮＷ（ネットワーク）を無向グラフＧ＝（Ｖ,Ｅ）…（Ｖは点集合、Ｅは辺集合）で表し、２つの点ｖ,ｗ∈Ｖを両端点とする経路の長さ（経路長）を、それに含まれる辺の本数とする。
【００４８】
２つの点ｖ,ｗ間の経路のうち、長さ（経路長）が最も短いものを、無効グラフＧにおけるｖ,ｗ間の最短路と定義し、その長さをｄＧ（ｖ,ｗ）で表す。また、辺ｅ∈Ｅを含む最短閉路（経路長が最短の閉路）の長さをＣ（ｅ）とする。
【００４９】
ＮＷ上の２つのノードの間の通信には、それらの間の最短路が用いられるものとする。これは、ＯＳＰＦなど一般的なルーティングアルゴリズムで最短経路が採られていることを反映している。
【００５０】
ＮＷの単一リンク故障（ＳＬＦ）とは、同時に障害を起こすリンクは高々一つということを意味する。これは、ＮＷを表すグラフにおいて、障害リンクに対応する辺をｅとした時、グラフＧからグラフＧ−｛ｅ｝＝（Ｖ,Ｅ−｛ｅ｝）へと変化することを意味する。
【００５１】
辺ｅのＳＬＦによって、２点ｐ，ｑ（∈Ｖ）間のグラフＧにおける最短路から、グラフＧ−｛ｅ｝における最短路へと変化する。従って、経路長の増加率は、「ｄＧ−｛ｅ｝（ｐ，ｑ）／ｄＧ（ｐ，ｑ）」となる。
【００５２】
このように、辺ｅのＳＬＦによって、２点ｐ，ｑ間の最短距離が変化するならば、点ｐ，ｑは、辺ｅを含む閉路上に存在するが、そのような閉路における増加率の最大値は、点ｐ，ｑが辺ｅの両端点である場合である。
【００５３】
よって、辺ｅのＳＬＦによる経路長増加率の最大値は「Ｃ（ｅ）−１」であり、ｍａｘｅ∈Ｅ｛Ｃ（ｅ）−１｝を、グラフＧの経路長増加率と定義する。これは、任意のＳＬＦに対する最悪の経路長増加率を意味している。
【００５４】
ここで、付加可能な箇所にＢ本以下のリンクを付加することによって、所望の経路長増加率Ｋ以下になるようにできるか否かを問う決定問題として、「経路長増加率抑制リンク付加問題」を、以下のようにして定義する。
【００５５】
［（２）経路長増加率抑制リンク付加問題（ＰＬＥＡＰ）］
『ＩＮＳＴＡＮＣＥ：無向グラフＧ，付加可能点対集合Ａ，正の定数Ｋ，Ｂ.』
『ＱＵＥＳＴＩＯＮ：Ｇ’＝（Ｖ,Ｅ∪Ｅ’）…（ただし|Ｅ’|≦Ｂ）の経路長増加率をＫ以下にするＥ’は存在するか？』
【００５６】
ここでは、集合Ｅ’が、付加するリンクの集合に対応する。現実的には、任意のノード間にリンクが付加できることはないため、このように、付加可能点対集合を指定することは自然である。
【００５７】
上述の［（２）経路長増加率抑制リンク付加問題（ＰＬＥＡＰ）］の定理に示したように、「経路長増加率抑制リンク付加問題」はＮＰ完全であるため、厳密解を得るための多項式オーダのアルゴリズムの存在は期待できない。
【００５８】
そのため、実際のネットワーク設計に適用させるためには、近似アルゴリズムを利用した設計が必要である。そこで、本例では、次の、集合被覆問題の近似アルゴリズムを利用したアルゴリズムを提案する。
【００５９】
集合被覆問題とは、集合Ｕと、その部分集合族Ｓ＝｛Ｓ１,Ｓ２,…,Ｓｍ｝を入力とし、集合Ｕの要素を全て含む最小個数の部分集合の集合を選択・決定する問題である。
【００６０】
ここでは、グラフＧにおいて、辺ｅ∈ＥのＳＬＦによる経路長増加率がＫ以下の辺を充足辺と呼び、経路長増加率がＫ以上の辺を未充足辺と呼ぶ。そして、未充足辺集合をＵとする。
【００６１】
また、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺にできるとき、辺ｆを候補辺と呼び、この候補辺ｆによって充足辺にできる未充足辺の集合をＳｆとする。
【００６２】
付加可能点対集合（グラフＧにおいて辺を新たに付加することが可能な２つの点の組（対）の集合）に候補辺ｆの集合が含まれると仮定する。また、付加辺は候補辺ｆからのみ選ぶものとする。
【００６３】
このとき、未充足辺集合Ｕと部分集合族Ｓ＝｛Ｓ１,Ｓ２,…,Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合が得られる。
【００６４】
そこで、下記のように、集合被覆問題に対する近似アルゴリズムを利用してコンピュータ処理を実行することで、付加辺集合Ｃを得ることができる。
【００６５】
［Ａｌｇｏｒｉｔｈｍ ＡｕｇｍｅｎｔＥｄｇｅｓ］
１：Ｃ＝φ…（φ：空集合）
２：ｗｈｉｌｅ Ｕ≠φ
３： ｄｏ ｂｅｇｉｎ
４： |Ｓｆ∩Ｕ|が最大となるＳｆを選ぶ
５： Ｕ＝Ｕ−Ｓｆ，Ｃ＝Ｃ∪｛Ｓｆ｝
６： ｅｎｄ ｄｏ
７：ｅｎｄ ｗｈｉｌｅ
８：ｏｕｔｐｕｔ Ｃ
【００６６】
この集合被覆問題に対する近似アルゴリズムを利用してコンピュータ処理を実行することで付加辺集合Ｃを得る動作を図２を用いて説明する。
【００６７】
図２において、まず、付加辺集合Ｃに含まれる要素を空に初期化し（ステップＳ２０１）、以下、未充足辺集合Ｕに１本以上の辺も残らないようになるまで（ｗｈｉｌｅ Ｕ≠φ）、ステップＳ２０３〜Ｓ２０５の処理を繰り返す（ステップＳ２０２）。
【００６８】
ステップＳ２０３では、各候補辺ｆに対して、候補辺ｆをグラフＧ（ネットワークトポロジ）に追加することで充足辺となる辺の集合（充足辺集合）Ｓｆを計算し、この充足辺集合Ｓｆに含まれる辺の中で、未充足辺集合Ｕに含まれる辺の数（｜Ｓｆ∩Ｕ｜）が最大となる充足辺集合Ｓｆを選択する。
【００６９】
ステップＳ２０４では、ステップＳ１０３で選択した充足辺集合Ｓｆに含まれる辺を、未充足辺集合Ｕから除き（Ｕ＝Ｕ−Ｓｆ）、ステップＳ２０５では、付加辺集合Ｃに充足辺集合Ｓｆを追加する（Ｃ＝Ｃ∪｛Ｓｆ｝）。
【００７０】
ステップＳ２０３〜Ｓ２０５の処理を繰り返して、ステップＳ２０４での処理（Ｕ＝Ｕ−Ｓｆ）の結果、未充足辺集合Ｕに１本以上の辺も残らないようになれば（ステップＳ２０２）、ステップＳ２０５で求めた付加辺集合Ｃを出力する（ステップＳ２０６）。
【００７１】
また、付加可能点対集合に候補辺集合Ｓが含まれ、付加辺は候補辺集合Ｓからのみ選ぶものと仮定する。このとき、上述のアルゴリズムＡｕｇｍｅｎｔＥｄｇｅｓは、ＰＬＥＡＰの経路長増加率制約を満たす付加辺集合Ｃを出力する。
【００７２】
このアルゴリズムで付加される辺の本数は、最小の本数の「ｌｏｇ|Ｕ|＋１」倍以下である。また、計算量Ｏは、未充足辺の数が|Ｕ|、候補辺の数が|Ｓ|の場合、Ｏ（|Ｕ|×|Ｓ|）である。
【００７３】
この［（２）経路長増加率抑制リンク付加問題（ＰＬＥＡＰ）］の定理は、集合被覆問題に対する近似アルゴリズムの性質より得られる。
【００７４】
以下、図３，４を用いて、本例のシステムの性能評価結果を説明する。ここでは、ＣＡＩＤＡ（Ｃｏｏｐｅｒａｔｉｖｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｉｎｔｅｒｎｅｔ Ｄａｔａ Ａｎａｌｙｓｉｓ）において公開されている３９個の実際のＩＳＰバックボーンＮＷのグラフ構造を利用した。
【００７５】
図３では、対象としたＮＷの一覧を示している。図３中の「次数１のリンク数」とは、ＮＷに対応するグラフにおいて、「次数１」の点とそれに接続する辺を削除し、それにより、また次数１の点が出現すれば、同様に点と辺を削除するということを繰り返した際、削除される辺の総数のことである。
【００７６】
元のＮＷにおいて、このようにして削除される点に対応するノードと、他の任意のノードとの間の辺連結度は「１」であるため、そもそも信頼性があまり求められていないノードおよびそれにつながるリンクと言える。
【００７７】
また、図３中の「辺ｅを含む閉路長Ｃ（ｅ）」の列中にある「ｎａｎ」は、ＮＷ中に閉路を１つも持たないことを示している。
【００７８】
図４においては、経路長増加率の上限値Ｋの値を「２」から「７」まで変化させ評価を行った結果を示している。尚、ここでは、付加可能点対集合は、全ての点対集合とした。
【００７９】
この図４では、元のＮＷで未充足辺の辺数と、各経路長増加率に対する付加辺数を挙げる。この図４から、元の現実ＮＷには、経路長増加率が大きいものや、無限大（元のＮＷに閉路が存在せず、故障時に代替経路が存在しない）の割合が高いものも少なくないことがわかる。
【００８０】
つまり、現実ＮＷは、連結度や経路長増加率の観点からの性能は決して良いとは言えない。しかし、そのようなＮＷでも、本例の技術を用いて、それほど多くないリンク付加で改善することができることもわかる。
【００８１】
例えば、増加率を「５」以下に抑えるために付加するリンク数は全体のリンク数と比べて小さく、増設は現実的な範囲で収めることができている。
【００８２】
以上、図１〜図４を用いて説明したように、本例では、ネットワークにおける単一リンク障害時に対応して増設するリンクの増設箇所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行う際に、入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを記憶装置に格納し、単一リンク障害による経路長の増加率を全て上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、記憶装置に記憶したネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択して出力装置に出力する。
【００８３】
あるいは、入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋおよびリンクを増設可能な箇所の集合情報（付加可能点対集合）を記憶装置に格納し、単一リンク障害による経路長の増加率を全て上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、記憶装置に記憶したネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋおよび付加可能点対集合を用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択して出力する。
【００８４】
リンク増設箇所を選択する際、ネットワークのトポロジ情報Ｇに対して辺ｅ∈Ｅの単一リンク障害による経路長増加率が上限値Ｋ以下の辺（充足辺）と上限値Ｋ以上の辺（未充足辺）を求め、未充足辺の集合Ｕを求めると共に、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺とする候補辺ｆを求め、さらに、この候補辺ｆによって充足辺となる未充足辺の集合Ｓｆを求め、そして、付加可能点対集合に候補辺集合が含まれ、且つ、付加辺は候補辺からのみ選ぶとの条件で、未充足辺の集合Ｕと、この集合Ｕの部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合Ｃを求め、この求めた付加辺集合Ｃを、リンクの増設箇所として選択する。
【００８５】
具体的には、リンク増設箇所の選択では、下記の近似アルゴリズムに従い、集合Ｓｆに含まれる辺の中で、未充足辺集合Ｕに含まれる辺の数が最大となる集合Ｓｆを選択する処理と、未充足辺集合Ｕから、選択した集合Ｓｆに含まれる辺を除くと共に、選択した集合Ｓｆを付加辺集合Ｃとして追加する処理とを、未充足辺集合Ｕに１本以上の辺が残っている限り反復して行い、未充足辺集合Ｕに含まれる全ての辺に対する反復処理結果で得られる付加辺集合Ｃを、リンクの増設箇所として選択する。
【００８６】
［Ａｌｇｏｒｉｔｈｍ ＡｕｇｍｅｎｔＥｄｇｅｓ］
１：Ｃ＝φ…（φ：空集合）
２：ｗｈｉｌｅ Ｕ≠φ
３： ｄｏ ｂｅｇｉｎ
４： |Ｓｆ∩Ｕ|が最大となるＳｆを選ぶ
５： Ｕ＝Ｕ−Ｓｆ，Ｃ＝Ｃ∪｛Ｓｆ｝
６： ｅｎｄ ｄｏ
７：ｅｎｄ ｗｈｉｌｅ
８：ｏｕｔｐｕｔ Ｃ
【００８７】
また、リンク増設箇所選択では、近似アルゴリズムで付加する辺の本数は、最小の本数のｌｏｇ|Ｕ|＋１倍以下である。
【００８８】
このように、本例によれば、ネットワークのトポロジと設計パラメタを入力し、入力データから最適な代替え経路を算出し、算出した代替え経路を出力することで、ネットワークのトポロジＧと単一リンク障害時の最大経路長増加率の設計上限Ｋが与えられたときに、最大経路長増加率の設計上限値Ｋを満足する最小数のリンク増設箇所を選択することができ、リンク障害発生時での代替え経路の選択において、経路長の増加率を予め定められた値以下に抑えることができる。すなわち、最小限のリンク増設で、所望の連結度と経路長増加率を満たすことができ、高信頼かつ高品質なネットワークを構成することが可能である。
【００８９】
尚、本発明は、図１〜図４を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。
【符号の説明】
【００９０】
１０１：トポロジ情報・最大経路長増加率の許容上限値入力部、１０２：リンク増設箇所選択部、１０２ａ：第１の未充足辺集合取得部、１０２ｂ：第２の未充足辺集合取得部、１０２ｃ：第１の付加辺集合算出部、１０２ｄ：第２の付加辺集合算出部、１０３：リンク増設箇所出力部。
【技術分野】
【０００１】
本発明は、ネットワークで発生したリンク障害時に代替えの経路を選択する技術に係り、特に、単一リンク障害時に対応して増設するリンクの増設箇所の選択を、経路長の増加率を抑えて行うことで、高信頼かつ高品質なネットワークを構成するのに好適な技術に関するものである。
【背景技術】
【０００２】
インターネットをはじめ、通信ネットワーク（ＮＷ）が社会において必要不可欠なインフラとなった現在、ＮＷには高い信頼性が求められている。特に、大規模なＮＷでは、様々な要因によるノードやリンクの故障や重い輻輳の発生は避けられないため、そのような障害が発生しても各ノード間の通信を維持し続けるための設計および制御が必要である。
【０００３】
このような観点から、障害時には代替経路を利用できるようにするために、後述するグラフ理論を用いた高い連結度のＮＷの設計に関する研究がなされている。例えば、同時に故障するリンクは一つだけとする単一リンク故障（ＳＬＦ：Ｓｉｎｇｌｅ Ｌｉｎｋ Ｆａｉｌｕｒｅ）を仮定し、ＳＬＦ時にも通信が途絶しないようにするために、ＮＷを２辺連結グラフとなるように設計することが、実際にも一般的に行われている。尚、２辺連結グラフとは、連結度が２であるグラフのことである。
【０００４】
このように、インターネットサービスプロバイダ（ＩＳＰ）のＮＷトポロジを、高い連結度のグラフとなるように構成することによって高い信頼性を得ることが可能である。
【０００５】
しかし、この場合、障害時に通常時の経路から代替経路に変化した際に、経路長（フロー長）が大きく延びてしまう可能性があり、影響を受ける膨大な数の通信の全てにおいて、通信品質の劣化を引き起こす可能性があることが指摘されている。
【０００６】
従って、実際のＮＷトポロジには、単に代替経路が存在するだけではなく、ＳＬＦ時の経路長の増加率が小さいことも必要である。
【０００７】
インターネットにおいては、経路を自由に決定することはできず、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）などルーティングプロトコルによって決定されるため、経路を適切に定めることで経路長の増加率を設定するという技術を取ることはできない。従って、ＮＷトポロジを変更することによって経路長増加率を設定しなければならない。
【０００８】
通常、大規模なＮＷは、最初から構築することはなく、既に構築・運用されている場合が多い。従って、既設ＮＷ全体を再構築し直すことは非現実的であり、そのため、既存のネットワークに最小限の増設を行うことで条件を満たすようにすることが必要となる。
【０００９】
すなわち、最小限のリンク増設によって、所望の連結度とＳＬＦ時の経路長増加率を満たすＮＷを構成することがＮＷ設計の目的となる。
【００１０】
以上の技術については、例えば非特許文献１等に記載されている。
【００１１】
ＮＷ設計に関しては、通信分野だけではなく、グラフ理論や最適化理論の研究分野も含め、これまで膨大な研究がなされてきている。その中には、上述したように、辺を付加することにより連結度に関する条件を満たすグラフを構成するタイプの問題がある。
【００１２】
連結度とは、全ての２点間で辺を共有しない経路の本数の最大値であり、辺連結度（点連結度）がｋであれば、グラフの任意の２点間に辺独立（点独立）なｋ本の路が存在する。辺独立な路とは、辺を共有しない経路のことである。
【００１３】
所望の連結度にするために最小本数の辺を付加する箇所を決定することによって、リンクやノードの障害時でも代替経路を利用して通信を継続できるようにすることが目的である。
【００１４】
辺連結度を増加させる問題に関しては多項式時間アルゴリズムが知られているが、点連結度増加問題に関してはＮＰ完全であることが知られている。尚、連結度増加問題においては、経路長についての制約も含めて考えられているものはない。
【００１５】
また、辺付加によって直径を抑制する問題についての検討も見られる。直径とは、グラフの任意の２点間の最短路長の最大値のことである。グラフの直径が小さくなるように設計することで、ＮＷ上での任意の２点間の通信遅延を小さくすることができる。
【００１６】
この問題は一般にＮＰ完全であり、グラフが木である場合など限られた場合についての多項式時間アルゴリズムが知られている。
【００１７】
この問題では経路長を考慮しているものの、連結度についても同時に考慮しているものはない。従って、１本のリンクが故障しただけで通信が途絶えてしまう可能性があり、耐故障性については必ずしも高くできるとは限らない。
【００１８】
他にも、与えられたグラフに辺を付加することによって、区間グラフやコーダルグラフ、ハミルトングラフにする問題などが知られている。いずれも経路長の変化に関する制約は含まれていない。尚、これらは全てＮＰ完全である。
【００１９】
以上から、これまでの問題は、経路長の増加率を抑制するという観点から辺付加を行う問題にそのまま適用することはできず、新たに検討する必要がある。
【００２０】
尚、このようなＮＷ設計に関してのグラフ理論や最適化理論に関しては、例えば、非特許文献２に記載されている。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】Ｎ．Ｋａｍｉｙａｍａ ａｎｄ Ｈ．Ｍｉｗａ，“Ｃｏｎｎｅｃｔｉｖｉｔｙ ａｎｄ Ｓｔａｂｉｌｉｔｙ Ａｎａｌｙｓｉｓ ａｇａｉｎｓｔ Ｆａｉｌｕｒｅｓ ｆｏｒ ＩＳＰ Ｂａｃｋｂｏｎｅ Ｎｅｔｗｏｒｋｓ”，ＩＥＥＥ ＧＬＯＢＥＣＯＭ ０８．
【非特許文献２】茨木俊秀，“情報学のための離散数学”，昭晃堂，２００４．
【発明の概要】
【発明が解決しようとする課題】
【００２２】
解決しようとする問題点は、従来の技術では、ネットワークにおける単一リンク障害時の最大経路長増加率を抑制する最適なリンク増設箇所の選択を行うことができない点である。
【００２３】
本発明の目的は、これら従来技術の課題を解決し、最小限のリンク増設で、ネットワークにおける所望の連結度での対障害性と経路長増加率を満たすことを可能とし、ネットワークの高信頼化および高品質化を図ることである。
【課題を解決するための手段】
【００２４】
上記目的を達成するため、本発明では、（１）ネットワークのトポロジＧと単一リンク障害時の最大経路長増加率の設計上限Ｋが与えられたときに、最小数のリンク増設箇所を選択する。また、（２）ネットワークのトポロジＧと単一リンク障害時の最大経路長増加率の設計上限Ｋおよびリンクを増設可能な箇所の集合が与えられたときに、最小数のリンク増設箇所を選択する。より具体的には、（３）グラフＧに対して辺ｅ∈Ｅの単一リンク障害による経路長増加率がＫ以下の辺を充足辺と呼び、さもなければ未充足辺と呼び、未充足辺集合をＵとし、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺にできるとき、辺ｆを候補辺と呼び、辺ｆによって充足辺にできる未充足辺の集合をＳｆとし、付加が可能な点の対の集合（付加可能点対集合）に候補辺集合が含まれると仮定し、付加辺は候補辺からのみ選ぶものとするとき、未充足辺集合Ｕと、この集合Ｕの部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合が得られることから、集合被覆問題に対する近似アルゴリズムを利用することで、付加辺集合Ｃを得て、この付加辺集合Ｃを最小数のリンク増設箇所として選択する。尚、（４）付加可能点対集合に候補辺集合Ｓが含まれ、付加辺は候補辺集合からのみ選ぶものと仮定するとき、後述のＰＬＥＡＰの経路長増加率制約を満たす付加辺集合を出力する。また、（５）このアルゴリズムで付加される辺の本数は、最小の本数のｌｏｇ|Ｕ|＋１倍以下であり、計算量は、未充足辺数|Ｕ|、候補辺数|Ｓ|の時、Ｏ（|Ｕ|×|Ｓ|）である。
【発明の効果】
【００２５】
本発明によれば、ネットワークのトポロジ情報（グラフＧ）と単一リンク障害時の最大経路長増加率の設計上限値（Ｋ）が与えられたときに、最大経路長増加率の設計上限値（Ｋ）を満足する最小数のリンク増設箇所を選択することができ、高信頼かつ高品質なネットワークを構成することが可能である。
【図面の簡単な説明】
【００２６】
【図１】図１は、本発明に係るリンク増設箇所最適選択システムの構成例を示すブロック図である。
【図２】図２は、図１におけるリンク増設箇所最適選択システムの本発明に係るリンク増設箇所最適選択方法例を示すフローチャートである。
【図３】図３は、図１におけるリンク増設箇所最適選択システムの処理対象となるネットワークの特性例を示す説明図である。
【図４】図４は、図１におけるリンク増設箇所最適選択システムの処理効果例を示す説明図である。
【発明を実施するための形態】
【００２７】
以下、図を用いて本発明を実施するための形態例を説明する。図１は、本発明に係るリンク増設箇所最適選択システムの構成例を示すブロック図であって、本例のリンク増設箇所最適選択システムは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）や主メモリを具備したコンピュータ構成からなり、プログラムされたコンピュータ処理によって、ネットワークのトポロジＧと単一リンク障害時の最大経路長増加率の設計上限Ｋとが与えられたときに、最小数のリンク増設箇所を選択するものであって、プログラムされたコンピュータ処理を実行する機能として、トポロジ情報・最大経路長増加率の許容上限値入力部１０１と、リンク増設箇所選択部１０２、リンク増設箇所出力部１０３を有する。
【００２８】
トポロジ情報・最大経路長増加率の許容上限値入力部１０１は、図示していないキーボードやマウス等の入力装置を用いた操作者の入力操作により、例えば、外部記憶媒体、あるいは、ネットワークを介したオンラインで入力される、処理対象のネットワークのトポロジ情報（グラフＧ）と単一リンク障害時の最大経路長増加率の許容上限値（許容上限Ｋ）等の設計パラメタを入力し、図示していない記憶装置に格納する。
【００２９】
リンク増設箇所選択部１０２は、記憶装置から、トポロジ情報・最大経路長増加率の許容上限値入力部１０１が入力した、トポロジ情報（グラフＧ）と設計上限値情報（許容上限Ｋ）を読み出し、このトポロジ情報（グラフＧ）と設計上限値情報（許容上限Ｋ）を用いて、本発明に係る処理、例えば、集合被覆問題に対する近似アルゴリズムにより、許容上限Ｋを満足する付加辺集合（Ｃ）を算出し、最小数のリンク増設箇所として選択する処理を実行する。
【００３０】
リンク増設箇所出力部１０３は、リンク増設箇所選択部１０２によるリンク増設箇所の選択結果を、ＣＲＴ（Ｃａｔｈｏｄｅ Ｌａｙ Ｔｕｂｅ）やＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）等の表示装置に表示する、もしくは、プリンタで印字する、あるいは、記憶媒体に記録する、オンライン上の他のコンピュータ装置等に送信する等の出力処理を行う。
【００３１】
また、リンク増設箇所選択部１０２は、プログラムされたコンピュータ処理を実行する機能として、第１の未充足辺集合取得部１０２ａと、第２の未充足辺集合取得部１０２ｂ、第１の付加辺集合算出部１０２ｃ、および、第２の付加辺集合算出部１０２ｄを有する。
【００３２】
第１の未充足辺集合取得部１０２ａは、グラフＧに対して辺ｅ∈Ｅの単一リンク障害による経路長の増加率が、設計上限Ｋ以下の辺（充足辺）と設計上限Ｋ以上の辺（未充足辺）を算出して、未充足辺の集合Ｕを求める。
【００３３】
第２の未充足辺集合取得部１０２ｂは、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺にできる辺候補辺ｆを算出して、この辺候補辺ｆによって充足辺にできる未充足辺の集合Ｓｆを求める。
【００３４】
第１の付加辺集合算出部１０２ｃは、付加可能点対集合に候補辺集合が含まれると仮定し、付加辺は候補辺からのみ選ぶとの条件で、未充足辺の集合Ｕと部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合が得られることから、集合被覆問題に対する近似アルゴリズムを利用することで、付加辺集合Ｃを算出する。
【００３５】
第２の付加辺集合算出部１０２ｄは、
付加可能点対集合に候補辺集合Ｓが含まれ、付加辺は候補辺集合からのみ選ぶものと仮定するとき、後述のＰＬＥＡＰの経路長増加率制約を満たす付加辺集合を算出する。
【００３６】
以下、このような構成からなるリンク増設箇所最適選択システムによる、本発明に係る、単一リンク障害時の最大経路長増加率を抑制するのに最適な、リンク増設箇所の選択技術について説明する。
【００３７】
上述したように、トポロジ情報・最大経路長増加率の許容上限値入力部１０１は、処理対象のネットワークのトポロジ情報（グラフＧ）と設計パラメタ（許容上限Ｋ）を入力する。トポロジ情報の例としては、ノードｉとノードｊ間にリンクが存在する場合には「１」を、しない場合には「０」をとる２値変数を要素に持つ行列が考えられ、単一リンク障害時の経路長増加率の許容最大値Ｋとしては、任意の整数が考えられる（例：Ｋ＝５）。
【００３８】
リンク増設箇所選択部１０２は、トポロジ情報・最大経路長増加率の許容上限値入力部１０１が入力した、トポロジ情報（グラフＧ）と設計パラメタ（許容上限Ｋ）を用いて、効果的なリンク増設箇所を選択する。
【００３９】
そして、リンク増設箇所出力部１０３は、リンク増設箇所選択部１０２により得られた増設箇所が出力する。
【００４０】
リンク増設箇所出力部１０３が出力するデータは、リンクを追加する場所の集合であり、データフォーマットとしては、例えば、ノードｉとノードｊ間にリンクを追加する場合に「１」を、しない場合に「０」をとる２値変数を要素にもつ行列が考えられる。
【００４１】
リンク増設箇所選択部１０２は、第１の未充足辺集合取得部１０２ａにより、グラフＧにおいて、辺ｅ∈ＥのＳＬＦによる経路長増加率がＫ以下の辺（充足辺）と、Ｋ以上の辺（未充足辺）を特定し、未充足辺の集合Ｕを求める。
【００４２】
また、リンク増設箇所選択部１０２は、第２の未充足辺集合取得部１０２ｂにより、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺にできる、辺（候補辺ｆ）を特定し、この候補辺ｆの付加によって充足辺にできる未充足辺の集合Ｓｆを求める。
【００４３】
そして、第１の付加辺集合算出部１０２ｃにより、付加可能点対集合に候補辺ｆの集合が含まれると仮定し、また、付加辺は、候補辺ｆからのみ選ぶものとし、未充足辺集合Ｕと部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合Ｃを得る。
【００４４】
また、第２の付加辺集合算出部１０２ｄにより、集合被覆問題に対する近似アルゴリズムを利用することで、付加辺集合Ｃを得る。
【００４５】
以下、このような、本発明に係る単一リンク障害時の最大経路長増加率を抑制するリンク増設箇所の選択技術について、［（１）経路長増加率抑制リンク付加問題］、［（２）経路長増加率抑制リンク付加問題（ＰＬＥＡＰ）］の順で、詳細を説明する。
【００４６】
［（１）経路長増加率抑制リンク付加問題］
【００４７】
まず、ＮＷ（ネットワーク）を無向グラフＧ＝（Ｖ,Ｅ）…（Ｖは点集合、Ｅは辺集合）で表し、２つの点ｖ,ｗ∈Ｖを両端点とする経路の長さ（経路長）を、それに含まれる辺の本数とする。
【００４８】
２つの点ｖ,ｗ間の経路のうち、長さ（経路長）が最も短いものを、無効グラフＧにおけるｖ,ｗ間の最短路と定義し、その長さをｄＧ（ｖ,ｗ）で表す。また、辺ｅ∈Ｅを含む最短閉路（経路長が最短の閉路）の長さをＣ（ｅ）とする。
【００４９】
ＮＷ上の２つのノードの間の通信には、それらの間の最短路が用いられるものとする。これは、ＯＳＰＦなど一般的なルーティングアルゴリズムで最短経路が採られていることを反映している。
【００５０】
ＮＷの単一リンク故障（ＳＬＦ）とは、同時に障害を起こすリンクは高々一つということを意味する。これは、ＮＷを表すグラフにおいて、障害リンクに対応する辺をｅとした時、グラフＧからグラフＧ−｛ｅ｝＝（Ｖ,Ｅ−｛ｅ｝）へと変化することを意味する。
【００５１】
辺ｅのＳＬＦによって、２点ｐ，ｑ（∈Ｖ）間のグラフＧにおける最短路から、グラフＧ−｛ｅ｝における最短路へと変化する。従って、経路長の増加率は、「ｄＧ−｛ｅ｝（ｐ，ｑ）／ｄＧ（ｐ，ｑ）」となる。
【００５２】
このように、辺ｅのＳＬＦによって、２点ｐ，ｑ間の最短距離が変化するならば、点ｐ，ｑは、辺ｅを含む閉路上に存在するが、そのような閉路における増加率の最大値は、点ｐ，ｑが辺ｅの両端点である場合である。
【００５３】
よって、辺ｅのＳＬＦによる経路長増加率の最大値は「Ｃ（ｅ）−１」であり、ｍａｘｅ∈Ｅ｛Ｃ（ｅ）−１｝を、グラフＧの経路長増加率と定義する。これは、任意のＳＬＦに対する最悪の経路長増加率を意味している。
【００５４】
ここで、付加可能な箇所にＢ本以下のリンクを付加することによって、所望の経路長増加率Ｋ以下になるようにできるか否かを問う決定問題として、「経路長増加率抑制リンク付加問題」を、以下のようにして定義する。
【００５５】
［（２）経路長増加率抑制リンク付加問題（ＰＬＥＡＰ）］
『ＩＮＳＴＡＮＣＥ：無向グラフＧ，付加可能点対集合Ａ，正の定数Ｋ，Ｂ.』
『ＱＵＥＳＴＩＯＮ：Ｇ’＝（Ｖ,Ｅ∪Ｅ’）…（ただし|Ｅ’|≦Ｂ）の経路長増加率をＫ以下にするＥ’は存在するか？』
【００５６】
ここでは、集合Ｅ’が、付加するリンクの集合に対応する。現実的には、任意のノード間にリンクが付加できることはないため、このように、付加可能点対集合を指定することは自然である。
【００５７】
上述の［（２）経路長増加率抑制リンク付加問題（ＰＬＥＡＰ）］の定理に示したように、「経路長増加率抑制リンク付加問題」はＮＰ完全であるため、厳密解を得るための多項式オーダのアルゴリズムの存在は期待できない。
【００５８】
そのため、実際のネットワーク設計に適用させるためには、近似アルゴリズムを利用した設計が必要である。そこで、本例では、次の、集合被覆問題の近似アルゴリズムを利用したアルゴリズムを提案する。
【００５９】
集合被覆問題とは、集合Ｕと、その部分集合族Ｓ＝｛Ｓ１,Ｓ２,…,Ｓｍ｝を入力とし、集合Ｕの要素を全て含む最小個数の部分集合の集合を選択・決定する問題である。
【００６０】
ここでは、グラフＧにおいて、辺ｅ∈ＥのＳＬＦによる経路長増加率がＫ以下の辺を充足辺と呼び、経路長増加率がＫ以上の辺を未充足辺と呼ぶ。そして、未充足辺集合をＵとする。
【００６１】
また、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺にできるとき、辺ｆを候補辺と呼び、この候補辺ｆによって充足辺にできる未充足辺の集合をＳｆとする。
【００６２】
付加可能点対集合（グラフＧにおいて辺を新たに付加することが可能な２つの点の組（対）の集合）に候補辺ｆの集合が含まれると仮定する。また、付加辺は候補辺ｆからのみ選ぶものとする。
【００６３】
このとき、未充足辺集合Ｕと部分集合族Ｓ＝｛Ｓ１,Ｓ２,…,Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合が得られる。
【００６４】
そこで、下記のように、集合被覆問題に対する近似アルゴリズムを利用してコンピュータ処理を実行することで、付加辺集合Ｃを得ることができる。
【００６５】
［Ａｌｇｏｒｉｔｈｍ ＡｕｇｍｅｎｔＥｄｇｅｓ］
１：Ｃ＝φ…（φ：空集合）
２：ｗｈｉｌｅ Ｕ≠φ
３： ｄｏ ｂｅｇｉｎ
４： |Ｓｆ∩Ｕ|が最大となるＳｆを選ぶ
５： Ｕ＝Ｕ−Ｓｆ，Ｃ＝Ｃ∪｛Ｓｆ｝
６： ｅｎｄ ｄｏ
７：ｅｎｄ ｗｈｉｌｅ
８：ｏｕｔｐｕｔ Ｃ
【００６６】
この集合被覆問題に対する近似アルゴリズムを利用してコンピュータ処理を実行することで付加辺集合Ｃを得る動作を図２を用いて説明する。
【００６７】
図２において、まず、付加辺集合Ｃに含まれる要素を空に初期化し（ステップＳ２０１）、以下、未充足辺集合Ｕに１本以上の辺も残らないようになるまで（ｗｈｉｌｅ Ｕ≠φ）、ステップＳ２０３〜Ｓ２０５の処理を繰り返す（ステップＳ２０２）。
【００６８】
ステップＳ２０３では、各候補辺ｆに対して、候補辺ｆをグラフＧ（ネットワークトポロジ）に追加することで充足辺となる辺の集合（充足辺集合）Ｓｆを計算し、この充足辺集合Ｓｆに含まれる辺の中で、未充足辺集合Ｕに含まれる辺の数（｜Ｓｆ∩Ｕ｜）が最大となる充足辺集合Ｓｆを選択する。
【００６９】
ステップＳ２０４では、ステップＳ１０３で選択した充足辺集合Ｓｆに含まれる辺を、未充足辺集合Ｕから除き（Ｕ＝Ｕ−Ｓｆ）、ステップＳ２０５では、付加辺集合Ｃに充足辺集合Ｓｆを追加する（Ｃ＝Ｃ∪｛Ｓｆ｝）。
【００７０】
ステップＳ２０３〜Ｓ２０５の処理を繰り返して、ステップＳ２０４での処理（Ｕ＝Ｕ−Ｓｆ）の結果、未充足辺集合Ｕに１本以上の辺も残らないようになれば（ステップＳ２０２）、ステップＳ２０５で求めた付加辺集合Ｃを出力する（ステップＳ２０６）。
【００７１】
また、付加可能点対集合に候補辺集合Ｓが含まれ、付加辺は候補辺集合Ｓからのみ選ぶものと仮定する。このとき、上述のアルゴリズムＡｕｇｍｅｎｔＥｄｇｅｓは、ＰＬＥＡＰの経路長増加率制約を満たす付加辺集合Ｃを出力する。
【００７２】
このアルゴリズムで付加される辺の本数は、最小の本数の「ｌｏｇ|Ｕ|＋１」倍以下である。また、計算量Ｏは、未充足辺の数が|Ｕ|、候補辺の数が|Ｓ|の場合、Ｏ（|Ｕ|×|Ｓ|）である。
【００７３】
この［（２）経路長増加率抑制リンク付加問題（ＰＬＥＡＰ）］の定理は、集合被覆問題に対する近似アルゴリズムの性質より得られる。
【００７４】
以下、図３，４を用いて、本例のシステムの性能評価結果を説明する。ここでは、ＣＡＩＤＡ（Ｃｏｏｐｅｒａｔｉｖｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｉｎｔｅｒｎｅｔ Ｄａｔａ Ａｎａｌｙｓｉｓ）において公開されている３９個の実際のＩＳＰバックボーンＮＷのグラフ構造を利用した。
【００７５】
図３では、対象としたＮＷの一覧を示している。図３中の「次数１のリンク数」とは、ＮＷに対応するグラフにおいて、「次数１」の点とそれに接続する辺を削除し、それにより、また次数１の点が出現すれば、同様に点と辺を削除するということを繰り返した際、削除される辺の総数のことである。
【００７６】
元のＮＷにおいて、このようにして削除される点に対応するノードと、他の任意のノードとの間の辺連結度は「１」であるため、そもそも信頼性があまり求められていないノードおよびそれにつながるリンクと言える。
【００７７】
また、図３中の「辺ｅを含む閉路長Ｃ（ｅ）」の列中にある「ｎａｎ」は、ＮＷ中に閉路を１つも持たないことを示している。
【００７８】
図４においては、経路長増加率の上限値Ｋの値を「２」から「７」まで変化させ評価を行った結果を示している。尚、ここでは、付加可能点対集合は、全ての点対集合とした。
【００７９】
この図４では、元のＮＷで未充足辺の辺数と、各経路長増加率に対する付加辺数を挙げる。この図４から、元の現実ＮＷには、経路長増加率が大きいものや、無限大（元のＮＷに閉路が存在せず、故障時に代替経路が存在しない）の割合が高いものも少なくないことがわかる。
【００８０】
つまり、現実ＮＷは、連結度や経路長増加率の観点からの性能は決して良いとは言えない。しかし、そのようなＮＷでも、本例の技術を用いて、それほど多くないリンク付加で改善することができることもわかる。
【００８１】
例えば、増加率を「５」以下に抑えるために付加するリンク数は全体のリンク数と比べて小さく、増設は現実的な範囲で収めることができている。
【００８２】
以上、図１〜図４を用いて説明したように、本例では、ネットワークにおける単一リンク障害時に対応して増設するリンクの増設箇所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行う際に、入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを記憶装置に格納し、単一リンク障害による経路長の増加率を全て上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、記憶装置に記憶したネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択して出力装置に出力する。
【００８３】
あるいは、入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋおよびリンクを増設可能な箇所の集合情報（付加可能点対集合）を記憶装置に格納し、単一リンク障害による経路長の増加率を全て上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、記憶装置に記憶したネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋおよび付加可能点対集合を用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択して出力する。
【００８４】
リンク増設箇所を選択する際、ネットワークのトポロジ情報Ｇに対して辺ｅ∈Ｅの単一リンク障害による経路長増加率が上限値Ｋ以下の辺（充足辺）と上限値Ｋ以上の辺（未充足辺）を求め、未充足辺の集合Ｕを求めると共に、辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺とする候補辺ｆを求め、さらに、この候補辺ｆによって充足辺となる未充足辺の集合Ｓｆを求め、そして、付加可能点対集合に候補辺集合が含まれ、且つ、付加辺は候補辺からのみ選ぶとの条件で、未充足辺の集合Ｕと、この集合Ｕの部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合Ｃを求め、この求めた付加辺集合Ｃを、リンクの増設箇所として選択する。
【００８５】
具体的には、リンク増設箇所の選択では、下記の近似アルゴリズムに従い、集合Ｓｆに含まれる辺の中で、未充足辺集合Ｕに含まれる辺の数が最大となる集合Ｓｆを選択する処理と、未充足辺集合Ｕから、選択した集合Ｓｆに含まれる辺を除くと共に、選択した集合Ｓｆを付加辺集合Ｃとして追加する処理とを、未充足辺集合Ｕに１本以上の辺が残っている限り反復して行い、未充足辺集合Ｕに含まれる全ての辺に対する反復処理結果で得られる付加辺集合Ｃを、リンクの増設箇所として選択する。
【００８６】
［Ａｌｇｏｒｉｔｈｍ ＡｕｇｍｅｎｔＥｄｇｅｓ］
１：Ｃ＝φ…（φ：空集合）
２：ｗｈｉｌｅ Ｕ≠φ
３： ｄｏ ｂｅｇｉｎ
４： |Ｓｆ∩Ｕ|が最大となるＳｆを選ぶ
５： Ｕ＝Ｕ−Ｓｆ，Ｃ＝Ｃ∪｛Ｓｆ｝
６： ｅｎｄ ｄｏ
７：ｅｎｄ ｗｈｉｌｅ
８：ｏｕｔｐｕｔ Ｃ
【００８７】
また、リンク増設箇所選択では、近似アルゴリズムで付加する辺の本数は、最小の本数のｌｏｇ|Ｕ|＋１倍以下である。
【００８８】
このように、本例によれば、ネットワークのトポロジと設計パラメタを入力し、入力データから最適な代替え経路を算出し、算出した代替え経路を出力することで、ネットワークのトポロジＧと単一リンク障害時の最大経路長増加率の設計上限Ｋが与えられたときに、最大経路長増加率の設計上限値Ｋを満足する最小数のリンク増設箇所を選択することができ、リンク障害発生時での代替え経路の選択において、経路長の増加率を予め定められた値以下に抑えることができる。すなわち、最小限のリンク増設で、所望の連結度と経路長増加率を満たすことができ、高信頼かつ高品質なネットワークを構成することが可能である。
【００８９】
尚、本発明は、図１〜図４を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。
【符号の説明】
【００９０】
１０１：トポロジ情報・最大経路長増加率の許容上限値入力部、１０２：リンク増設箇所選択部、１０２ａ：第１の未充足辺集合取得部、１０２ｂ：第２の未充足辺集合取得部、１０２ｃ：第１の付加辺集合算出部、１０２ｄ：第２の付加辺集合算出部、１０３：リンク増設箇所出力部。
【特許請求の範囲】
【請求項１】
ネットワークにおける単一リンク障害時に対応して増設するリンクの増設箇所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うリンク増設箇所最適選択システムであって、
プログラムされたコンピュータ処理を実行する手段として、
入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを記憶装置に格納する入力手段と、
上記単一リンク障害による経路長の増加率を全て上記上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、上記記憶装置に記憶した上記ネットワークのトポロジ情報Ｇと上記経路長増加率の上限値Ｋを用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択するリンク増設箇所選択手段と、
該リンク増設箇所選択手段が選択したリンク増設箇所を出力装置に出力する出力手段と
を有することを特徴とするリンク増設箇所最適選択システム。
【請求項２】
ネットワークにおける単一リンク障害時に対応して増設するリンクの増設箇所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うリンク増設箇所最適選択システムであって、
プログラムされたコンピュータの処理実行手段として、
入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋおよび上記リンクを増設可能な箇所の集合情報（付加可能点対集合）を記憶装置に格納する入力手段と、
上記単一リンク障害による経路長の増加率を全て上記上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、上記記憶装置に記憶した上記ネットワークのトポロジ情報Ｇと上記経路長増加率の上限値Ｋおよび上記付加可能点対集合を用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択するリンク増設箇所選択手段と、
該リンク増設箇所選択手段が選択した上記リンクの増設箇所を出力装置に出力する出力手段と
を有することを特徴とするリンク増設箇所最適選択システム。
【請求項３】
請求項２に記載のリンク増設箇所最適選択システムであって、
上記リンク増設箇所選択手段は、
上記ネットワークのトポロジ情報Ｇに対して辺ｅ∈Ｅの単一リンク障害による経路長増加率が上記上限値Ｋ以下の辺（充足辺）と上限値Ｋ以上の辺（未充足辺）を求め、未充足辺の集合Ｕを求める第１の手段と、
辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺とする候補辺ｆを求め、該候補辺ｆによって充足辺となる未充足辺の集合Ｓｆを求める第２の手段と、
上記付加可能点対集合に上記候補辺集合が含まれ、且つ、付加辺は候補辺からのみ選ぶとの条件で、上記未充足辺の集合Ｕと該集合Ｕの部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する上記集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合Ｃを求める第３の手段と
を有し、
上記求めた付加辺集合Ｃを、上記リンクの増設箇所として選択することを特徴とするリンク増設箇所最適選択システム。
【請求項４】
請求項３に記載のリンク増設箇所最適選択システムであって、
上記リンク増設箇所選択手段は、
下記の近似アルゴリズムに従い、
上記集合Ｓｆに含まれる辺の中で、上記未充足辺集合Ｕに含まれる辺の数が最大となる集合Ｓｆを選択する処理と、
上記未充足辺集合Ｕから上記選択した集合Ｓｆに含まれる辺を除くと共に、上記選択した集合Ｓｆを上記付加辺集合Ｃとして追加する処理とを、
上記未充足辺集合Ｕに１本以上の辺が残っている限り反復し、
上記未充足辺集合Ｕに含まれる全ての辺に対する上記反復処理結果で得られる上記付加辺集合Ｃを、上記リンクの増設箇所として選択することを特徴とするリンク増設箇所最適選択システム。
記
［Ａｌｇｏｒｉｔｈｍ ＡｕｇｍｅｎｔＥｄｇｅｓ］
１：Ｃ＝φ…（φ：空集合）
２：ｗｈｉｌｅ Ｕ≠φ
３： ｄｏ ｂｅｇｉｎ
４： |Ｓｆ∩Ｕ|が最大となるＳｆを選ぶ
５： Ｕ＝Ｕ−Ｓｆ，Ｃ＝Ｃ∪｛Ｓｆ｝
６： ｅｎｄ ｄｏ
７：ｅｎｄ ｗｈｉｌｅ
８：ｏｕｔｐｕｔ Ｃ
【請求項５】
請求項４に記載のリンク増設箇所最適選択システムであって、
上記リンク増設箇所選択手段が、上記近似アルゴリズムで付加する辺の本数は、最小の本数のｌｏｇ|Ｕ|＋１倍以下であることを特徴とするリンク増設箇所最適選択システム。
【請求項６】
ネットワークにおける単一リンク障害時に対応して増設するリンクの増設箇所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うシステムのリンク増設箇所最適選択方法であって、
プログラムされたコンピュータの処理実行手順として、
請求項１から請求項５のいずれかに記載のリンク増設箇所最適選択システムにおける各手段が実行する処理手順を含むことを特徴とするリンク増設箇所最適選択方法。
【請求項７】
コンピュータを、請求項１から請求項５のいずれかに記載のリンク増設箇所最適選択システムにおける各手段として機能させるためのプログラム。
【請求項１】
ネットワークにおける単一リンク障害時に対応して増設するリンクの増設箇所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うリンク増設箇所最適選択システムであって、
プログラムされたコンピュータ処理を実行する手段として、
入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋを記憶装置に格納する入力手段と、
上記単一リンク障害による経路長の増加率を全て上記上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、上記記憶装置に記憶した上記ネットワークのトポロジ情報Ｇと上記経路長増加率の上限値Ｋを用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択するリンク増設箇所選択手段と、
該リンク増設箇所選択手段が選択したリンク増設箇所を出力装置に出力する出力手段と
を有することを特徴とするリンク増設箇所最適選択システム。
【請求項２】
ネットワークにおける単一リンク障害時に対応して増設するリンクの増設箇所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うリンク増設箇所最適選択システムであって、
プログラムされたコンピュータの処理実行手段として、
入力装置を介して入力されるネットワークのトポロジ情報Ｇと経路長増加率の上限値Ｋおよび上記リンクを増設可能な箇所の集合情報（付加可能点対集合）を記憶装置に格納する入力手段と、
上記単一リンク障害による経路長の増加率を全て上記上限値以下にするために増設するリンクの数を最小とするリンクの増設箇所を、上記記憶装置に記憶した上記ネットワークのトポロジ情報Ｇと上記経路長増加率の上限値Ｋおよび上記付加可能点対集合を用いた集合被覆問題に対する近似アルゴリズムに従った処理を実行して選択するリンク増設箇所選択手段と、
該リンク増設箇所選択手段が選択した上記リンクの増設箇所を出力装置に出力する出力手段と
を有することを特徴とするリンク増設箇所最適選択システム。
【請求項３】
請求項２に記載のリンク増設箇所最適選択システムであって、
上記リンク増設箇所選択手段は、
上記ネットワークのトポロジ情報Ｇに対して辺ｅ∈Ｅの単一リンク障害による経路長増加率が上記上限値Ｋ以下の辺（充足辺）と上限値Ｋ以上の辺（未充足辺）を求め、未充足辺の集合Ｕを求める第１の手段と、
辺ｆ（∈Ｅ）を付加することで１辺以上の未充足辺を充足辺とする候補辺ｆを求め、該候補辺ｆによって充足辺となる未充足辺の集合Ｓｆを求める第２の手段と、
上記付加可能点対集合に上記候補辺集合が含まれ、且つ、付加辺は候補辺からのみ選ぶとの条件で、上記未充足辺の集合Ｕと該集合Ｕの部分集合族Ｓ＝｛Ｓ１，Ｓ２，…，Ｓｍ｝に対する上記集合被覆問題の解から、全ての未充足辺を充足辺にする最小本数の付加辺集合Ｃを求める第３の手段と
を有し、
上記求めた付加辺集合Ｃを、上記リンクの増設箇所として選択することを特徴とするリンク増設箇所最適選択システム。
【請求項４】
請求項３に記載のリンク増設箇所最適選択システムであって、
上記リンク増設箇所選択手段は、
下記の近似アルゴリズムに従い、
上記集合Ｓｆに含まれる辺の中で、上記未充足辺集合Ｕに含まれる辺の数が最大となる集合Ｓｆを選択する処理と、
上記未充足辺集合Ｕから上記選択した集合Ｓｆに含まれる辺を除くと共に、上記選択した集合Ｓｆを上記付加辺集合Ｃとして追加する処理とを、
上記未充足辺集合Ｕに１本以上の辺が残っている限り反復し、
上記未充足辺集合Ｕに含まれる全ての辺に対する上記反復処理結果で得られる上記付加辺集合Ｃを、上記リンクの増設箇所として選択することを特徴とするリンク増設箇所最適選択システム。
記
［Ａｌｇｏｒｉｔｈｍ ＡｕｇｍｅｎｔＥｄｇｅｓ］
１：Ｃ＝φ…（φ：空集合）
２：ｗｈｉｌｅ Ｕ≠φ
３： ｄｏ ｂｅｇｉｎ
４： |Ｓｆ∩Ｕ|が最大となるＳｆを選ぶ
５： Ｕ＝Ｕ−Ｓｆ，Ｃ＝Ｃ∪｛Ｓｆ｝
６： ｅｎｄ ｄｏ
７：ｅｎｄ ｗｈｉｌｅ
８：ｏｕｔｐｕｔ Ｃ
【請求項５】
請求項４に記載のリンク増設箇所最適選択システムであって、
上記リンク増設箇所選択手段が、上記近似アルゴリズムで付加する辺の本数は、最小の本数のｌｏｇ|Ｕ|＋１倍以下であることを特徴とするリンク増設箇所最適選択システム。
【請求項６】
ネットワークにおける単一リンク障害時に対応して増設するリンクの増設箇所の選択を、プログラムされたコンピュータのグラフ理論を用いた処理によって行うシステムのリンク増設箇所最適選択方法であって、
プログラムされたコンピュータの処理実行手順として、
請求項１から請求項５のいずれかに記載のリンク増設箇所最適選択システムにおける各手段が実行する処理手順を含むことを特徴とするリンク増設箇所最適選択方法。
【請求項７】
コンピュータを、請求項１から請求項５のいずれかに記載のリンク増設箇所最適選択システムにおける各手段として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１０−１９９７３７（Ｐ２０１０−１９９７３７Ａ）
【公開日】平成２２年９月９日（２０１０．９．９）
【国際特許分類】
【出願番号】特願２００９−３９７１７（Ｐ２００９−３９７１７）
【出願日】平成２１年２月２３日（２００９．２．２３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０３０９２１８０）学校法人関西学院 (71)
【Ｆターム（参考）】
【公開日】平成２２年９月９日（２０１０．９．９）
【国際特許分類】
【出願日】平成２１年２月２３日（２００９．２．２３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（５０３０９２１８０）学校法人関西学院 (71)
【Ｆターム（参考）】
[ Back to top ]