ネットワークのリンク増設箇所またはリンク容量増設箇所特定方法
【課題】単一リンク障害時の迂回トラヒックを考慮し、品質の安定性の観点から、適切なリンク増設・リンク容量増設箇所を求めることを可能にする。
【解決手段】ネットワークのトポロジとリンク容量とがＮＷ条件入力装置１０１に与えられたときに、この情報を受け取り、ネットワーク構造分析装置１０２が投資コストを抑えながら、ネットワークの障害時の接続性と安定性を効率性に向上させるために、適切なリンク増設箇所とリンク容量増設箇所を絞り込む。絞り込まれたリンク増設箇所情報をリンク増設・リンク容量増設箇所出力装置１０３から出力する。ネットワーク分析装置１０２は、単一リンク障害時にフローのホップ長が最も増加する場所は最大最短閉路（任意の二つのノードを含む経路で経路コストが最小のものを最短閉路と定義し、最短閉路の中でホップ長が最大のものを最大最短閉路と定義）であることから、最大最短閉路のホップ長が小さくなるようにバイパスリンクを設置する。
【解決手段】ネットワークのトポロジとリンク容量とがＮＷ条件入力装置１０１に与えられたときに、この情報を受け取り、ネットワーク構造分析装置１０２が投資コストを抑えながら、ネットワークの障害時の接続性と安定性を効率性に向上させるために、適切なリンク増設箇所とリンク容量増設箇所を絞り込む。絞り込まれたリンク増設箇所情報をリンク増設・リンク容量増設箇所出力装置１０３から出力する。ネットワーク分析装置１０２は、単一リンク障害時にフローのホップ長が最も増加する場所は最大最短閉路（任意の二つのノードを含む経路で経路コストが最小のものを最短閉路と定義し、最短閉路の中でホップ長が最大のものを最大最短閉路と定義）であることから、最大最短閉路のホップ長が小さくなるようにバイパスリンクを設置する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トポロジとリンク容量が与えられたネットワークを対象として、投資コストを抑えながら効果的に信頼性を向上させるように、リンク増設を行う際に、過剰増設とならないよう、リンク増設箇所またはリンク容量増設箇所を特定する方法に関し、特に、特定方法として、単一のリンク故障時に最大最短閉路のホップ長が小さくなるようにバイパスリンクを増設する手法に関する。
【背景技術】
【０００２】
従来、電子メール、Ｗｅｂアクセス、ファイル交換などの利用が主であったインターネットには、近年、電話サービスのマイグレーションが急速に進みつつある。日常的に利用される機会は今後ますます増加していくことが予想され、社会インフラ化に伴って信頼性に対する要求はますます増大している。
特に、バックボーンは大量のトラヒックを中継する役目を担っており、特に高い信頼性が求められる。ファイバ切断や光伝送装置の故障、ルータの設定ミスやソフトウェアのバグ、処理装置の過剰負荷といった様々な要因で、インターネットでは日常的に様々なリンクやルータで障害が発生することを前提とし、障害発生時にもノード間の接続性を維持し、サービスを継続する堅牢性が求められている。
【０００３】
インターネットの単一ＡＳ（自律システム）内では、ルーティングプロトコルとしてＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）が用いられているが、障害発生時、ルータは障害発生箇所を避けるようにフロー（発着ノード間を流れるパケットの集合と定義）の迂回経路を自律的に設定する。そのため、障害発生時にも高い接続性を維持することができる反面、フローの経路が迂回される結果、フローのホップ長が大きく増加する可能性や、迂回フローが特定のリンクに集中し負荷が大はく増加する可能性がある。
このことは、パケット転送時間の増大、フローのスループット低下を意味するため、音声や動画といった即時性の高いサービスの品質劣化を招く。そのため、ネットワーク（ＮＷ）の信頼性を議論する際には、接続性の維持の観点だけでは不十分であり、フロー長やリンク負荷の安定性の維持の観点からも評価することが重要である。
【０００４】
障害時の接続性と安定性を向上させる最も単易な方法は、大容量のリンクを数多く敷設することであるが、設備投資コストと管理・運営コストが増大する。ＩＳＰ（インターネットサービスプロバイダ）が競争力を保つためには、信頼性の高いサービスを低料金でユーザに提供することが重要であり、限られた投資コストで効果的に信頼性を向上させる必要がある。
一つの方法は、静的な交流トラヒック行列に対して障害発生時の迂回を考慮した上で総コストが最小化するように網トポロジとリンク容量を設計することである。しかし、交流量を精度よく推定することは容易でなく、またトラヒック量は日々変化するため、時間の経過に伴って最適性が低下する。そのため、ＩＳＰにとっての現実的な方法は、長期的な交流需要行列の変化に応じて、既に保有するＮＷに対し部分的にリンクを設置し、リンク容量を増設することである。そのためには、障害発生時に接続性や安定性を低下させる主な要因を分析し、設備増設箇所を効果的に絞り込む必要がある。
以上の技術については、上山憲昭，吉野秀明“リンク障害時の迂回トラヒックを考慮した網トポロジ設計”信学技報，ＩＮ２００７−８９．（非特許文献１）を参照されたい。
【０００５】
【非特許文献１】上山憲昭，吉野秀明“リンク障害時の迂回トラヒックを考慮した網トポロジ設計”信学技報，ＩＮ２００７−８９．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
リンクの重要度を図る尺度としてＢｅｔｗｅｅｎｅｓｓがよく知られている。ノードｉからノードｊの間の最短コスト経路数をσｉｊとし、そのうちリンクｌを通るものの本数をσｉｊ（ｌ）とすると、リンクＩのＢｅｔｗｅｅｎｅｓｓはΣｉｊσｉｊ（ｌ）／σｉｊ／ｎ／（ｎ−１）で定義される。ただし、ｎはノード数である。Ｂｅｔｗｅｅｎｅｓｓが大きなリンクほど、ＳＬＦ時に影響を受け、経路が迂回されるフロー数が多くなる。そのため、ＢｅｔｗｅｅｎｅｓｓはＳＬＦ（スランプフロー値）時の迂回フロー数の大小を測る尺度として用いることができるが、経路の迂回に関しては何等考慮されておらず、ＳＬＦ時の接続性や品質の安定性を図る尺度として用いることはできない。
【０００７】
各リンクの接続性に関する重要度を評価する方法として、Ｒｅｌｉａｂｉｌｉｔｙ Ｐｏｌｙｎｏｍｉａｌ（ＲＰ）（信頼多項式）が知られている。これは、障害発生確率が全リンクで同一であると仮定し、各リンクに対して、ＳＬＦ時に任意に定めたＫ個（全ノード数ｎでもよい）のノード間の接続性が維持される確率として定義される。そして、任意の２本のリンクに対してＮＷ全体の接続性に関する相対的な重要度の大小関係をＲＰにより評価する。ＲＰが接続性に関する重要度を任意に選んだ２本のリンクの相対的な大小関係として評価するのに対して、各リンクに対して、そのリンクを除去することで減少するＳｐａｎｎｉｎｇ Ｔｒｅｅ（データがループを循環し続けることを防止する制御手法）の本数を算出することで、個々のリンクに接続性に関する重要度を表す尺度を直接定義する方法も存在する。
【０００８】
すなわち、Ｓｐａｎｎｉｎｇ Ｔｒｅｅを構成するリンクが消失すると接続性が失われるノードが発生するため、構成するＳｐａｎｎｉｎｇ Ｔｒｅｅの個数が多いリンクほど接続性に関して重要である。同様に、リンクコストとして任意の値が設定されている場合を対象に、個々のリンクに対して構成するＭｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅ（ＭＳＴ）の個数で重要度を定義する方法もある。ところで、次数が１のノードが存在する場合、そのノードを発着とするフローは必ずそのノードに接続するリンクを通るため、Ｂｅｔｗｅｅｎｅｓｓは大きくなるが、そのリンクはＮＷ全体の接続性に対しては大きな貢献を果していない。
【０００９】
このようなバイアスを排除するため、各リンクに対して最小コストの経路が通るノードペア集合をＴｒａｖｅｒｓａｌ ｓｅｔとして定義し、さらにそのようなノードペアのうち少なくとも一方のノードを除去するために除去する必要のあるノード数でリンクの重要度を評価する方法もある。これらの方法を用いることで、障害時の接続性の観点からＮＷの信頼性に対する各リンクの重要度を測ることが可能である。しかし、障害時のフロー長やリンク負荷の増大といった品質の安定性の観点からは重要度を測ることができない。
【００１０】
（目的）
本発明の目的は、このような従来の課題を解決し、単一リンク障害時の迂回トラヒックを考慮し、品質の安定性の観点から、適切なリンク増設・リンク容量増設箇所を求めることが可能なネットワークの増設箇所特定方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明のネットワークの増設箇所特定方法は、ネットワークのトポロジとリンク容量とが与えられたときに、投資コストを抑えながら、ネットワークの障害時の接続性と安定性を効率性に向上させるために、適切なリンク増設箇所とリンク容量増設箇所を絞り込む方法である。
また、単一リンク障害時にフローのホップ長が最も増加する場所は最大最短閉路（任意の二つのノードを含む経路で経路コストが最小のものを最短閉路と定義し、最短閉路の中でホップ長が最大のものを最大最短閉路と定義）であることから、最大最短閉路のホップ長が小さくなるようにバイパスリンクを設置する方法である。
【００１２】
また、単一リンク障害時にリンクの負荷が最も増加する場所は、容量格差の大きなリンクから構成される複数のハブノードを含むか、ホップ長の長い最短閉路上の小容量リンクであることから、容量格差の大きな最短閉路が存在するかを調べ、存在する場合には、その小容量リンクの容量を増設する方法である。
さらに、単一リンク障害時にボトルネックリンク容量が大きく悪化するフローは、容量格差の大きい最短閉路上の小容量リンクを経由するフローであることから、やはり容量格差の大きな最短閉路上の小容量リンクの容量を増設する方法である。
【発明の効果】
【００１３】
本発明によれば、ネットワークのトポロジとリンク容量が与えられているときに、単一リンク障害時において、フローのホップ長の増加、リンクの負荷の増加、フローのボトルネックリンク容量の減少、の三つを効果的に抑えるためのリンク増設・リンク容量の増設箇所を絞り込むことができる、という効果がある。
【発明を実施するための最良の形態】
【００１４】
本発明の網トポロジ・リンク容量設計方法の実施の形態に係るシステム構成図である。
図１において、１０１はトポロジ情報とリンク容量情報（ネットワーク条件）を入力するＮＷ条件入力装置、１０２は入力装置１０１から情報を受取り、ネットワーク構造の分析を実行するネットワーク構造分析装置、１０３はネットワーク構造分析装置１０２から情報を受取り、リンク増設・リンク容量増設箇所を特定して、それを出力するリンク増設・リンク容量増設箇所出力装置である。
【００１５】
まず、ＮＷ条件入力装置１０１により、ネットワークのトポロジとリンク容量が入力される。ネットワーク構造分析装置１０２により、効果的なリンク増設箇所・リンク容量増設箇所が特定される。そして、得られた増設箇所が、リンク増設・リンク容量増設箇所出力装置１０３によって出力される。
【００１６】
次に、本発明の実施の形態に係るネットワークの効果的な信頼性向上のためのネットワークの増設箇所特定方法について、図面により詳細に説明する。
【００１７】
（１）ネットワークの分類と構造分析
本発明における評価には、ＣＡＩＤＡのＷｅｂページでトポロジとリンク容量が公開されている３９の商用ＩＳＰのバックボーンＮＷを用いる。ただし、Ｃａｂｌｅ ＩｎｔｅｒｎｅｔとＲＩＳＱ（Ｒｅｖｉｅｗ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｏｃｉａｌ Ｑｕｅｓｔｉｏｎｓ）Ｎｅｔｗｏｒｋはトポロジが単一のＳｐａｎｎｉｎｇ Ｔｒｅｅであり、任意のＳＬＦ時に障害フローの迂回が全くできないことから、評価には用いない。
また、Ｕｎｉｌａｔ Ｉｎｃ．は全体が４つと２つのノードの集合に分断されているため、やはり評価には用いない。また、ＰＳＩＮｅｔ，Ｑｗｅｓｔ，Ｔｅｌｓｔｒａ Ｉｎｔｅｒｎｅｔ，ＵＵＮＥＴにおいて、各々、３，２，６，２個のノードが孤立しているため、これらのノードは除外する。
【００１８】
図１４は、評価に用いた３６のＮＷの性能をまとめた図である。
これは、３６のＮＷについて、名称（Ｎａｍｅ）、ノード数（ｎ）、（双方向）リンク数（ｍ）、ノード次数の平均と最大値（Ａｖ，Ｍａｘ）、リンク容量の最小値と最大値（Ｍｉｎ，Ｍａｘ）をまとめたものである。
【００１９】
図２は、評価に用いた３６のＮＷの平均ノード次数と最大ノード次数の散布図である。
図２により、ＮＷを下記１）〜３）の３つのグループに分類する。
１）Ｆｕｌｌ ｍｅｓｈ・・・各ノードがほとんど他の全てのノードと接続しているトポロジで、平均次数と最大次数の差が小さく、平均次数が大きい。平均次数をＥ（ｄ），最大次数をＭａｘ（ｄ）とすると、ここではＥ（ｄ）≧Ｍａｘ（ｄ）−１を満たすＮＷと定義する。２つのＮＷ（ノード次数６および８）が該当する。
【００２０】
２）Ｈ＆Ｓ・・・次数の高いノード（ハブノード）が存在し最大次数が大きい。ハブ＆スポーク型と呼ばれるトポロジ構造であり、航空路線のトポロジが本形態となることが知られている。ハブノードを経由して多数のノードに到達することができるため、フローはホップ長が短くなる特徴がある反面、ハブノードに多数のフローが経由するため、負荷がハブノードに集中し易い。ここでは、ｍａｘ（ｄ）≧１０，Ｅ（ｄ）＜Ｍａｘ（ｄ）−１を満たすＮＷと定義する。１２のＮＷが該当する。
【００２１】
３）Ｌａｄｄｅｒ・・・高次数ノードが存在せず、ループを組み合わせたトポロジ構造となる。平均次数と最大次数が共に小さい。リンク総延長を抑えられる反面、遠方のノードに到達するためには、多数のノードを経由する必要があり、フローのホップ長が長くなる傾向がある。高速道路網が本形態となることが知られている。ここでは、Ｍａｘ（ｄ）＜１０，Ｅ（ｄ）＜Ｍａｘ（ｄ）−１を満たすＮＷと定義する。２２のＮＷが該当する。
【００２２】
図３は、各々の種別に属するＮＷの例を示す図である。
これら３つのＮＷは、全て米国のＩＳＰであるが、種別ごとに大きく形態が異なることが確認される。図３（ａ）のＦｕｌｌ ｍｅｓｈは、各ノード毎に網目のように接続されている。横軸は順位をノード数ｎで除した値である。図３（ｂ）のＨ＆Ｓは、リンク数は多くはないが、次数の高いノードであるハブノードが多く存在している。図３（ｃ）のＬａｄｄｅｒは、高次数ノードが少なく、リンク数もそれほど多くない。
【００２３】
図４は、Ｈ＆Ｓ型ネットワークの特性を示す図である。
Ｈ＆Ｓ型のＮＷは、次数の大きく異なるノードから構成されているため、ノードの接続構造を考察する。図４（ａ）には、Ｈ＆Ｓ型の１２のＮＷの各々に対して、次数の大きな順に正規化ノード次数（ノード次数を最大次数で除した値）をプロットする。横軸は、順位をノード数ｎで除した値である。ＮＷ１６，２９を除く他の１０のＨ＆Ｓ型ＮＷでは、全て全体の５％〜２０％程度の少数のノードが高次数である。
【００２４】
次に、ハブノードが相互に接続されている度合いを調べるため、図４（ｂ）に、ＲＣＣ（ｒｉｃｈ ｃｌｕｂ ｃｏｎｎｅｃｔｉｖｉｔｙ）をプロットする。ＲＣＣは、ノードを次数の大きな順に並べたときの上位ρ個のノード間に存在するリンク数を、可能な総数ρ（ρ−１）／２で除した値で定義され、図ではρをｎで正規化した値に対してプロットしている。ＲＣＣも正規化ノード次数と同様の傾向を示しており、高次数ノードのＲＣＣは高く、多くの高次数ノード間にはリンクが設置されている。
【００２５】
高次数ノード間に設置されたリンクには多数のフローが経由することから、そのような場所には大容量リンクが設置されることが予想される。リンク容量が均一なＮＷ１３を除いた１１のＮＷを対象に、各リンクの正規化リンク容量（リンク容量を最大リンク容量で除した値）を正規化ノード次数積に対して図４（ｃ）にプロットする。正規化ノード次数積を、各リンクの両端のノードの次数の積を、各ＮＷにおける次数積の最大値で除した値で定義する。次数の高いノード間に設置されたリンクほど、正規化ノード次数積が大きくなるが、予想に反して、リンク容量とノード次数積との間には明確な正の相関は見られない。
【００２６】
（２）正常時のフローとリンク負荷特性
障害が発生していない正常時の、フローホップ長、フローのボトルネット（ＢＮ）容量、リンク負荷について考察する。これら特性は、フローの経路設定法に依存するが、本発明においては、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）を想定し、リンクコストとして、シスコ社の推将するリンク容量の逆数に設定する場合（ｉｎｖ．ｃａｐ）と、全リンクで同一の値を設定する場合（ｍｉｎ．ｈｏｐ）の二つを考える。ある発着ノード間に同じコストの経路が複数存在する場合には、全ての最小コスト経路にトラヒックが均一に分散されると仮定する。
【００２７】
各ＮＷに対して、平均フロー長ｈを次式で定義する。
【００２８】
【数１】
ただし、Ｖはノード集合、ｈｓｄはノードｓとｄの間のフロー（フローｓｄと表記）の平均フロー長、σｓｄはフローｓｄの本数、Ｆｓｄはフローｓｄの集合、ｈｓｄ，ｆはｓｄ間のフローｆのホップ長である。
【００２９】
図５は、正常時のフロー特性を示す図である。
図５（ａ）には、３６の各ＮＷに対して、ｉｎｖ．ｃａｐにおけるｈをｍｉｎ．ｈｏｐにおけるｈに対してプロットする。ｍｉｎ．ｈｏｐでは最短ホップ経路が設定されるため、ｉｎｖ．ｃａｐはｍｉｎ．ｈｏｐよりｈが増加し、全てのＮＷは直線ｙ＝ｘ上か右下の領域に存在する。特に、ＮＷ２，４，８，１５，２６のｈが大きいが、これらは全てＬａｄｄｅｒ型である。Ｌａｄｄｅｒ型ＮＷにはハブノードが存在せず、遠方のノードに到達するためには多数のノードを経由する必要があり、ｈが大きくなる傾向がある。
【００３０】
１１のＨ＆Ｓ型ＮＷ、１つのＦｕｌｌ ｍｅｓｈ型ＮＷ、２２のＬａｄｄｅｒ型ＮＷはリンク容量が不均一である。これら２４のＮＷでは、フローが小容量リンクを経由する可能性がある。フローのスループットは経由リンクの最小容量（ＢＮ容量と表記）で抑えられるため、フローのＢＮ容量が重要な性能指標となる。
そこで、図５（ｂ）に、２４のＮＷに対して、ｉｎｖ．ｃａｐにおける平均正規化ＢＮ容量ζをｍｉｎ．ｈｏｐにおけるζに対してプロットする。ただし、ＮＷごとに、フローのＢＮ容量の平均値ｚを平均リンク容量ｃで除したものをζと定義し、
【００３１】
【数２】
【００３２】
【数３】
とする。ｚｓｄはフローｓｄのＢＮ容量、Ｐｓｄ，ｆはｓｄ間のフローｆの経路、ｃｌはリンクｌの容量である。平均正規化ＢＮ容量ζが大きなほどＮＷの資源を有効に活用できていることを意味するが、ｉｎｖ．ｃａｐが良好な特性を示している。また、Ｈ＆Ｓ型ＮＷは他の種別と比較してＢＮ容量が小い傾向が見られる。これはハブノード間に設置されたリンクの一部は図４（ｃ）で見たように小容量リンクであるが、ハブノードを経由することで短いホップ数で多数のノードに到達できるため、多くのフローが経由する結果、ＢＮとなるためである。例えば、ＮＷ５の場合、１５４本のリンクのうち３１本が２．３３３Ｇｂｐｓ、２７本が１５５Ｍｂｐｓ、９６本が４５Ｍｂｐｓであるが、二つのハブノード、シカゴ（次数１６）とダラス（次数１５）間に設置されたリンクの容量は４５Ｍｂｐｓと小さい。そのため、例えばシアトル・アトランタ間のｍｉｎ．ｈｏｐにおける経由はシアトル−シカゴ−ダラス−アトランタとなるが、シカゴ−ダラス間のリンク容量がＢＮとなっている。
【００３３】
次に、正常時に各リンクを経由するフロー数について考慮する。リンクｌの平均フロー数υｌをＢｅｔｗｅｅｎｅｓｓと同様、
【００３４】
【数４】
と定義し、各ＮＷに対して平均フロー数υｌと最大フロー数υｍａｘを、ｍ本の全リンクにわたるυｌの相加平均と最大値により求める。
【００３５】
図６は、正常時のリンク負荷特性を示す図である。
図６（ａ）に、ｉｎｖ．ｃａｐとｍｉｎ．ｈｏｐにおけるυｍａｘをυで除した値の散布図を３６のＮＷに対してプロットする。殆んどのＮＷは直線ｙ＝ｘの右下の領域に存在し、ｉｎｖ．ｃａｐを用いることで大容量リンクにフローが集中し、各リンクを経由するフロー数の格差が拡大することが確認できる。リンク容量の格差が大きく迂回経路を見つけ易いＨ＆Ｓ型のＮＷで、特にこの傾向が強い。
【００３６】
また、図６（ｂ）に、リンク容量が不均一な２４の各ＮＷに対して、リンク容量ｃｌとフロー数υｌとの間の相関係数を、ｉｎｖ．ｃａｐとｍｉｎ．ｈｏｐの各々の場合について散布図としてプロットする。ＮＷによって、ｃｌとυｌとの間の相関係数のばらつきが大きく、ＮＷ種別による明確な傾向が見られない。
ｉｎｖ．ｃａｐを用いることでリンク容量の大きなリンクにフローが集中し、ｃｌとυｌとの間の相関性が向上すること、リンク容量の有効な活用の観点からはｉｎｖ．ｃａｐを用いることが望ましいこと、がそれぞれ確認できる。
【００３７】
また、図６（ｃ）（ｄ）に、ｉｎｖ．ｃａｐとｍｉｎ．ｈｏｐにおける，２４のＮＷの各リンクに対して、正規化リンク容量（ｃｌを各ＮＷの最大リンク容量ｃｍａｘで除した値）と正規化フロー数（υｌをｖｍａｘで除した値）間の散布図を各々示す。ｉｎｖ．ｃａｐを用いることで、リンク容量の小さいリンクを経由するフロー数が抑えられることが確認できる。
【００３８】
（３）接続性に関する評価
ＳＬＦ時の接続性喪失率Ｐｄｃを、一つ以上のＳＬＦ発生パタンにおいて接続性が失われるフローの割合と定義する。すなわち、ｘｓｄ，ｌをリンクｌのＳＬＦ時にフローｓｄの接続性が維持される場合に１、損なわれる場合に０をとる２値変数と定義すると、
【００３９】
【数５】
である。次数ｄが１のノードを発着とするフローは、そのノードが接続するリンクの障害時に必ず接続性が失われる。
【００４０】
図７は、次数１のノード数比率を示す図である。
図７（ａ）に、次数１のノード数のｎに対する割合をｎに対してプロットする。ただし、ＮＷ１１，１８（Ｆｕｌｌ ｍｅｓｈ型）とＮＷ７，１７（Ｌａｄｄｅｒ型）は、次数１のノードが存在しないため、省いている。次数１のノード割合はＮＷによって大きく異なり、ｎやＮＷ種別による明確な傾向は見られない。
【００４１】
また、図７（ｂ）には、ＮＷごとに次数１ノード数比率に対して、Ｐｄｃをプロットする。
これら二つの尺度間には正の相関が見られ、ＳＬＦ時に接続性が失われるフローの大部分は次数１のノードを発着とするものであることが予想される。ただし、次数１ノードに接続するリンクのＳＬＦ時、影響を受けるフローはそのノードを発着とするフローに限定され、ＮＷ全体の信頼性に与える影響は小さい。そこで、Ｐｄｃから次数１ノードに起因するものを除いたＳＬＦ時の接続性喪失率Ｐｄｃ’を算出したところ、２３のＮＷでＰｄｃ’が０．０５を超えたのはＮＷ２，１２，１５，２０のＬａｄｄｅｒ型の４つのＮＷのみであった。これら４つのＮＷのトポロジ形状を調べたところ、ＮＷ２は８２ノード中１７ノードが１本のリンクによって他の部分に接続しており、ＮＷ１２，１５は１本のリンクのＳＬＦにより、ＮＷ全体が二つに分断される形状であり、ＮＷ２０は１５ノード中３ノードが１本のリンクによって他の部分に接続している。
よって、これら４つのＮＷにおいては、ＳＬＦに対して脆弱なアキレス腱となるリンクが存在するが、他の３２のＮＷにはそのようなリンクは存在せず、接続性については堅牢であると言える。以後、ＳＬＦ時の安定性に関する性能指標を算出する際には、接続性が喪失したフローについては全て除いて考える。
【００４２】
（４）フロー長の増加に関する分析
図８は、各フローやリンクに影響を与える障害パタン数比率を示す図である。
ホップ数がｙのフローがＳＬＦ時に影響を受ける障害発生パタン数の全リンク数ｍに対する割合をＲｆ（ｙ）とすると、Ｒｆ（ｙ）＝ｙ／ｍであるので、ＮＷ全体で各フローが平均的に影響を受ける障害発生パタン数のｍに対する比率Ｒｆは、
【００４３】
【数６】
より算出できる。
図８（ａ）には、３６のＮＷに対して、ｉｎｖ．ｃａｐにおけるＲｆとｍｉｎ．ｈｏｐ
におけるＲｆの散布図を示す。ｉｎｖ．ｃａｐを用いると、ｍｉｎ．ｈｏｐと比較してフローの平均ホップ長が増加するため、Ｒｆは若干大きくなる。また、Ｌａｄｄｅｒ型のＮＷはフローのホップ長が長くなる傾向があるため、Ｒｆが大きい。殆んどのＮＷはＲｆが０．１５程度より小さいため、ＳＬＦ時の平均的なフロー長増加特性を評価するに際し、各フローに対して影響を受けるリンク障害パタンのみを考慮する。すなわち、ＳＬＦ時のフローｓｄの平均フロー長ｈ’ｓｄを、
【００４４】
【数７】
で定義する。ただし、ｍｓｄはＳＬＦ時にフローｓｄが影響を受けるリンク数、Ｅｓｄはそのリンク集合、ｈｓｄ，ｌはリンクｌのＳＬＦ時のノードｓ，ｄ間のフローの平均ホップ長、σｓｄ，ｌはリンクｌのＳＬＦ時にノードｓ，ｄ間に設置されるフロー数、Ｆｓｄ，ｌはそのフロー集合、ｈｓｄ，ｌ，ｆはＦｓｄ，ｌに属するフローｆのホップ長である。そして、ＳＬＦ時の平均フロー長倍率ξを、ξ＝Σｓｄ∈Ｖｈ’ｓｄ／ｈｓｄ／ｎ／（ｎ−１）で算出する。また、ＳＬＦ時の最大フロ長倍率ξｍａｘを、
【００４５】
【数８】
で定義する。ただし、ｈｍｉｎ，ｓｄは正常時にノードｓ，ｄ間に設置されるフローの最小ホップ長である。
【００４６】
図９は、ＳＬＦ時のフロー長増加率を示す図である。
図９では、３６のＮＷを対象にξｍａｘとξの散布図を、（ａ）ｉｎｖ．ｃａｐと（ｂ）ｍｉｎ．ｈｏｐの各々について示している。ｍｉｎ．ｈｏｐとｉｎｖ．ｃａｐとでは大きな差異は見られない。Ｌａｄｄｅｒ型ＮＷは全体的にフロー長が長いため、ＳＬＦ時の増加の度合いも大きくなる傾向が見られる。特に、５つのＮＷはξｍａｘが突出して大きいが、これらは正常時の平均フロー長が大きい５つのＮＷである（図５（ａ）参照）。
次に、これらのＮＷで、ξｍａｘが大きな要因を考察する。
【００４７】
正常時のトポロジにおいて、任意のノードＡから出発して同じリンクを逆方向も含めて２回以上経由することなく、任意の他のノードＢを経由し、さらに元のノードＡに戻ることのできる経路の中で、最小コストのものをノードＡとＢの最短閉路と定義する。最短経路の存在しない二つのノード間フローは、どのように経路を設定しても必ず経由する必要のあるリンクが存在することになり、そのリンクのＳＬＦ時には接続性が失われるため、ＳＬＦ時の安定性の評価の対象外となる。従って、最短閉路が存在するノードペアについてのみ考える。
【００４８】
ノードＡ，Ｂの最短閉路上にはリンクを共有しない二つの経路がＡとＢの間に存在するが、そのうちコストの小さい方がＡＢ間の最小コスト経路となり、もう一方が、次にコストの小さい経路となる。そのため、正常時には最短閉路上のコストの小さい経路が用いられ、この経路上のリンクのＳＬＦ時には最短閉路上のもう一方の経路にフローが迂回される。そのため、最短閉路上の迂回経路のホップ数を正常時経路のホップ数で除したものがＡＢ間のフロー長倍率となる。よって、各ＮＷにおいて、隣接する二つのノードに対して定義される最短閉路の中でホップ数が最大のものを最大最短閉路と定義すると、最大最短閉路を導く二つの隣接ノード間のリンクのＳＬＦ時に、これら二つのノード間のフローのフロー長倍率がξｍａｘを与え、最大最短閉路のホップ数をθとすると、ξｍａｘ＝θ−１となる。
【００４９】
図１０は、Ａｔ Ｈｏｍｅ ｎｅｔｗｏｒｋのトポロジを示す図である。
図１０では、ξｍａｘが突出して大きかった５つのＮＷの例として、ＮＷ４のトポロジを示している。このＮＷには、θ＝１４の最大最短閉路が２つ存在し、隣接ノードペア７，９などの最短閉路（７−９−１５−１８−２１−３９−４０−４１−３６−３８−１４−１２−１０−８−７）と、隣接ノードペア３３，３４などの最短閉路（１８−２０−２８−２９−３０−３１−３２−３３−３４−３５−３７−４０−３９−２１−１８）が該当する。例えば、ノード７，９間のリンクのＳＬＦ時、これらのノード間のフローのホップ長が１から１３に増加し、ξｍａｘ＝１３となる。
【００５０】
ξｍａｘの大きなＮＷはξも大きな傾向があり、ξｍａｘの突出して大きな５つのＮＷのうちＮＷ２６を除く４つは、１．８を超えていた。また、ＮＷ１１，１７，１８，２０，２１の５つのＮＷは、ξｍａｘは小さいもののξが大きい。このうち、ＮＷ１１と１８はＦｕｌｌ ｍｅｓｈ型であり、正常時には殆んどのノード間のフローが１ホップであるのに対して、ＳＬＦ時には影響を受けたフローが２ホップとなり、ξが２に近くなる。また、ＮＷ１７，２０，２１はループトポロジに近く、θの総リンク数ｍに対する比率が大きく、多数のフローのフロー長倍率が大きくなる結果、ξが大きい。
【００５１】
（５）リンク負荷の増加に関する分析
各リンクを経由するフロー数が正常時のフロー数と比較して、増加するＳＬＦのパタン数の全リンクにわたる平均を、リンク数ｍで除した値をＲｌと定義する。図８（ｂ）に３６のＮＷに対して、ｉｎｖ．ｃａｐにおけるＲｌの散布図を示す。ｉｎｖ．ｃａｐを用いると、特定のリンクにフローが集中するため、多くのリンクに対しては障害時にフローが迂回されず、ｍｉｎ．ｈｏｐと比較してＲｆが小さい。
【００５２】
殆んどのＮＷは、Ｒｆが０．５程度より小さいため、ＳＬＦ時の平均的な経由フロー数増加特性を評価するに際し、やはり各リンクの経由フロー数が増加するリンク障害パタンのみを考慮する。ＳＬＦ時のリンクの平均経由フロー数倍率εを次式で定義する。
【００５３】
【数９】
ただし、εｌはＳＬＦにおけるリンクｌの平均フロー数倍率、υ’ｌ，ｅはリンクｅのＳＬＦ時におけるリンクｌのフロー数（算出方法は（４）に順じる）。ｍε，ｌはυ’ｌ，ｅ＞υｌとなるＳＬＦパタン数、Ｅε，ｌはそのＳＬＦリンク集合、ｍεはｍε，ｌ＞０のリンク数、Ｅｅはそのリンク集合である。また、ＳＬＦ時の最大フロー数倍率εｍａｘを次式で定義する。
【００５４】
【数１０】
ただし、εｌεｍａｘの算出において、υｌ＝０のリンクはυｌ＝１と置換える。
【００５５】
図１１は、ＳＬＦ時のフロー数増加率を示す図である。
図１１では、３６のＮＷを対象にεｍａｘとεの散布図を、（ａ）ｉｎｖ．ｃａｐと（ｂ）ｍｉｎ．ｈｏｐの各々について示している。ｍｉｎ．ｈｏｐを用いると、リンク間で経由フロ−数の格差が大きいため、ＳＬＦ時のフロー数倍率も高くなる。
リンクごとにＳＬＦ時のフロー数倍率の格差が大きく、εｌの大きなリンクが存在するＮＷはεも大きい。ｉｎｖ．ｃａｐの場合、８つのＮＷで特にこれらの値が大きいが、その要因を考察する。
【００５６】
ＳＬＦ時のフロー数倍率が高いリンクは正常時に経由するフロー数が少なく、かつＳＬＦ時に大量のフローが迂回される障害パタンが存在するリンクである。そのようなリンクは、（イ）二つ以上のハブノードを含む最短閉路、（ロ）ホップ数の長い最短閉路、のいずれかに存在すると考えられる。そのような最短閉路を構成するリンクの容量の格差が大きく一部のリンク容量が極端に小さい場合、小容量リンクの両端のノードＡ，Ｂ間のフローはｉｎｖ．ｃａｐにおいては、正常時にはそのリンクを用いず、最短閉路上を周回する経由を用いる。このようなリンクは、正常時には経由するフロー数がゼロとなるが、最短閉路上に存在する少なくとも一方がＡ，Ｂとは異なる２個のノードのうち、やはり同一の最短閉路を構成するものの間の任意のリンクのＳＬＦ時には、大量のフローがＡ，Ｂ間を接続するリンクに迂回される結果、フロー数倍率が高くなる。
【００５７】
図１２は、ａｂｏｖｅ．ｎｅｔのトポロジを示す図である。
図１２では、εの大きいＮＷの例として、ＮＷ１のトポロジを示している。
ノードペア０，１および１，２の最短閉路は（０−１−２−０）であるが、リンク（０，１）と（０，２）の容量が６２２Ｍｂｐｓであるのに対して、リンク（１，２）の容量１５５Ｍｂｐｓである。そのため、正常時、ノード１，２間のフローも含め、リンク（１，２）には全くフローが経由しないが、二つのハブノード０と１の間のリンクのＳＬＦ時、大量のフローが（０−２−１）の経路に迂回される結果、リンク（１，２）のフロー数倍率が高くなる。
【００５８】
最短閉路長が短い場合に、単一のリンクを通るコストが最短閉路上を周回するコストより大きくなり易いため、εｌが大きなリンクは３本のリンクから構成される最短閉路において生じ易い。実際、εｍａｘの大きな８つのＮＷのうち、ＮＷ１，３，５，３３は２つ以上のハブノードを含み、リンク容量格差の大きな３本のリンクから構成される最短閉路において、εｌが最大となった。また、ＮＷ８，２３，２６は、各々、６，５，６ホップの最短閉路上においてεｌが最大となった。ただし、ＮＷ２は１７のノードが１本のリンクで接続する特殊な形状となっており、例外的に、接続点からＮＷの他の部分に接続する容量の異なる２本のリンクでεｌが最大となった。
【００５９】
このように、容量格差の大きいリンクで最短閉路を構成した場合、ＳＬＦ時に一部のリンクで経由フロー数が非常に増加する場合がある。特に、リンク容量の小さなリンクで、フロー数倍率が高くなる場合、ＳＬＦ時にリンク輻輳を生じる要因となる。
【００６０】
図１３は、ＳＬＦ時の正規化平均迂回フロー数を示す図である。
上記段落〔００５９〕に記載したことを確認するため、各リンクのＳＬＦ時の平均迂回フロー数を最大迂回フロー数で正規化した値ψを、正規化リンク容量に対して図１３にプロットする。ただし、リンク容量が不均一な２４のＮＷの各リンクに対して、（ａ）ｉｎｖ．ｃａｐ、（ｂ）ｍｉｎ．ｈｏｐの場合について示している。
ψは、次式で定義する。
【００６１】
【数１１】
ただし、ψｌはＳＬＦにおけるリンクｌの平均フロー数倍率、υ’ｌ，ｅはリンクｅのＳＬＦ時におけるリンクｌのフロー数（算出方法は（４）に順じる）。ｍψ，ｌはυｌ，ｅ＞０のＳＬＦパタン数、Ｅψ，ｌはそのＳＬＦリンク集合、ｍψはｍψ，ｌ＞０のリンク数、Ｅψはそのリンク集合である。最大リンク容量の０．１〜０．０１倍を下回る小容量リンクの多くに、最大迂回フロー数に近い大量のフローが迂回されることが確認できる。
【００６２】
（６）フローのＢＮ容量の低下に関する分析
ＳＬＦ時のフローのＢＮ容量最大低下倍率ηを、次式で定義する。
【００６３】
【数１２】
ただし、ｚ’ｓｄ，ｅは、フローｓｄのリンクｅのＳＬＦ時のＢＮ容量である。
ｉｎｖ．ｃａｐにおいて、リンク容量の不均一な２４のＮＷを対象にＢＮ容量最大低下倍率ηを算出したところ、８つのＮＷでη＝１であり、７つのＮＷで０．２５〜０．４であり、５つのＮＷで０．０５〜０．１であり、ＮＷ５，２６，３１，３３の４つのＮＷで０．０２未満となった。η＜０．０２の４つのＮＷについてＢＮ容量低下倍率が最大となったフローを調べたところ、ＮＷ５，２６，３３では平均フロー数倍率εｌが最大となったリンクを経由するフローであった。
【００６４】
また、ＮＷ３１においても、容量格差の大きなリンクで構成される最短閉路において、容量の小さなリンクのＳＬＦ時にこのリンクを経由するフローのＢＮ容量低下倍率が最大となった。以上のことから、やはり容量格差の大きなリンクで構成されたハブノードを含むか、ホップの長い最短閉路を有するＮＷにおいて、ＳＬＦ時のフローのＢＮ容量低下倍率が大きくなることが確認できる。
【００６５】
（７）分析のまとめと設計指針
公開されている３６の商用ＩＳＰのバックボーンＮＷを対象に、単一リンク障害（ＳＬＦ）に対する信頼性を接続性と品質の安定性の観点から評価し、信頼性が劣化する要因について分析した結果、以下のことが明らかとなった。
イ）ＳＬＦによりＮＷが分断されるリンクを有するＮＷは４つのみであり、大部分のＮＷは接続性の観点からは堅牢である。
ロ）ＳＬＦ時のフロー長の最大増加量は、最大最短閉路によって決まり、最大最短閉路長が長いＬａｄｄｅｒ型のＮＷがＳＬＦ時のフロー長の増加度合いが高くなる傾向がある。
ハ）容量格差の大きなリンクから構成される，２個以上のハブノードを含むか、ホップ長の長い最短閉路上の小容量リンクが、ＳＬＦ時に経由するフロー数の増加度合いが大きい。ハブノードを多く含むＨ＆Ｓ型のＮＷにおいて、ＳＬＦ時のリンクのフロー数増加度合いが高くなる傾向がある。
ニ）容量格差の大きい最短閉路上の小容量リンクを経由するフローのＢＮ容量がＳＬＦ時に大きく低下する傾向にある。
【００６６】
以上のことから、Ｈ＆Ｓ型のＮＷにおいては容量格差の大きな最短閉路が存在するか調べ、存在する場合には最短閉路上の小容量リンクの容量を増設することが、またＬａｄｄｅｒ型のＮＷにおいてはホップ長が大きな最大最短閉路が存在するか調べ、存在する場合には、最大最短閉路のホップ長が小さくなるよう、バイパスリンクを設置することが、ＩＳＰにとって投資コストを抑えながら信頼性を効果的に向上させるために有効である。
【００６７】
図１５は、本発明のリンク増設箇所またはリンク容量増設箇所特定処理の動作フローチャートである。
本発明では、ネットワーク構造分析装置１０２のコンピュータにおけるプログラムの動作により、リンク増設またはリンク容量増設の箇所が絞られ、バイパスリンクの設置またはリンクの容量の増設の指示を出力装置から出力される。
コンピュータは、ステップ２０２〜２０４の３つの手順のうちの１つないし３つを実施して、リンク増設またはリンク容量増設の箇所を絞る。１つ目は、フローのホップ長が最も増加する場所は最大最短閉路（任意の二つのノードを含む経路で経路コストが最小のものの中で、ホップ長が最大のもの）であることから、最大最短閉路が存在するか否かを判別する（ステップ２０２）。存在すると判別されれば、その経路のホップ長を小さくするため、バイパスリンクを設置するか、または、小容量リンクの容量を増設する指示情報を出力する（ステップ２０６）。
【００６８】
２つ目は、ボトルネットリンク容量が大きく悪化するフローとして、最大最短閉路で、容量格差の大きい経路上の小容量リンクを経由するフローがあるか否かを判別する（ステップ２０３）。あると判別されれば、その経路上の小容量リンクの容量を増設する指示情報を出力する（ステップ２０７）。
３つ目は、容量格差の大きなリンクからなる複数のハブノード、または、ホップ長の長い経路上の小容量リンクを含むか否かを判別する（ステップ２０４）。含むと判別されれば、それら複数のハブノード間のリンクの増設、または、小容量リンクの容量リンクの容量を増設する指示情報を出力する（ステップ２０８）。
【００６９】
このようにして、本発明によれば、ネットワークのトポロジとリンク容量が入力されたとき、コンピュータの制御により、投資コストを抑えながら、ネットワークの障害時の接続性と安定性を効率的に向上させるため、適切なリンク増設箇所とリンク容量増設箇所を絞り込むことが可能である。
【図面の簡単な説明】
【００７０】
【図１】本発明の一実施形態に係るシステム構成図である。
【図２】平均次数と最大次数の散布図である。
【図３】ネットワークトポロジの例を示す図である。
【図４】Ｈ＆Ｓ型ネットワークの特性を示す図である。
【図５】正常時のフロー特性を示す図である。
【図６】正常時のリンク負荷特性を示す図である。
【図７】次数１のノード数比率を示す図である。
【図８】各フローやリンクに影響を与える障害パタン数比率を示す図である。
【図９】ＳＬＦ時のフロー長増加率を示す図である。
【図１０】Ａｔ Ｈｏｍｅ ｎｅｔｗｏｒｋのトポロジを示す図である。
【図１１】ＳＬＦ時のフロー数増加率を示す図である。
【図１２】ａｂｏｖｅ．ｎｅｔのトポロジを示す図である。
【図１３】ＳＬＦ時の正規化平均迂回フロー数を示す図である。
【図１４】３６のＩＳＰバックボーンネットワークの基本特性を示す図である。
【図１５】本発明の一実施形態に係るリンク増設箇所またはリンク容量増設箇所特定処理のフローチャートである。
【符号の説明】
【００７１】
１０１ ＮＷ条件入力装置
１０２ ネットワーク構造分析装置
１０３ リンク増設・リンク容量増設箇所出力装置
【技術分野】
【０００１】
本発明は、トポロジとリンク容量が与えられたネットワークを対象として、投資コストを抑えながら効果的に信頼性を向上させるように、リンク増設を行う際に、過剰増設とならないよう、リンク増設箇所またはリンク容量増設箇所を特定する方法に関し、特に、特定方法として、単一のリンク故障時に最大最短閉路のホップ長が小さくなるようにバイパスリンクを増設する手法に関する。
【背景技術】
【０００２】
従来、電子メール、Ｗｅｂアクセス、ファイル交換などの利用が主であったインターネットには、近年、電話サービスのマイグレーションが急速に進みつつある。日常的に利用される機会は今後ますます増加していくことが予想され、社会インフラ化に伴って信頼性に対する要求はますます増大している。
特に、バックボーンは大量のトラヒックを中継する役目を担っており、特に高い信頼性が求められる。ファイバ切断や光伝送装置の故障、ルータの設定ミスやソフトウェアのバグ、処理装置の過剰負荷といった様々な要因で、インターネットでは日常的に様々なリンクやルータで障害が発生することを前提とし、障害発生時にもノード間の接続性を維持し、サービスを継続する堅牢性が求められている。
【０００３】
インターネットの単一ＡＳ（自律システム）内では、ルーティングプロトコルとしてＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）が用いられているが、障害発生時、ルータは障害発生箇所を避けるようにフロー（発着ノード間を流れるパケットの集合と定義）の迂回経路を自律的に設定する。そのため、障害発生時にも高い接続性を維持することができる反面、フローの経路が迂回される結果、フローのホップ長が大きく増加する可能性や、迂回フローが特定のリンクに集中し負荷が大はく増加する可能性がある。
このことは、パケット転送時間の増大、フローのスループット低下を意味するため、音声や動画といった即時性の高いサービスの品質劣化を招く。そのため、ネットワーク（ＮＷ）の信頼性を議論する際には、接続性の維持の観点だけでは不十分であり、フロー長やリンク負荷の安定性の維持の観点からも評価することが重要である。
【０００４】
障害時の接続性と安定性を向上させる最も単易な方法は、大容量のリンクを数多く敷設することであるが、設備投資コストと管理・運営コストが増大する。ＩＳＰ（インターネットサービスプロバイダ）が競争力を保つためには、信頼性の高いサービスを低料金でユーザに提供することが重要であり、限られた投資コストで効果的に信頼性を向上させる必要がある。
一つの方法は、静的な交流トラヒック行列に対して障害発生時の迂回を考慮した上で総コストが最小化するように網トポロジとリンク容量を設計することである。しかし、交流量を精度よく推定することは容易でなく、またトラヒック量は日々変化するため、時間の経過に伴って最適性が低下する。そのため、ＩＳＰにとっての現実的な方法は、長期的な交流需要行列の変化に応じて、既に保有するＮＷに対し部分的にリンクを設置し、リンク容量を増設することである。そのためには、障害発生時に接続性や安定性を低下させる主な要因を分析し、設備増設箇所を効果的に絞り込む必要がある。
以上の技術については、上山憲昭，吉野秀明“リンク障害時の迂回トラヒックを考慮した網トポロジ設計”信学技報，ＩＮ２００７−８９．（非特許文献１）を参照されたい。
【０００５】
【非特許文献１】上山憲昭，吉野秀明“リンク障害時の迂回トラヒックを考慮した網トポロジ設計”信学技報，ＩＮ２００７−８９．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
リンクの重要度を図る尺度としてＢｅｔｗｅｅｎｅｓｓがよく知られている。ノードｉからノードｊの間の最短コスト経路数をσｉｊとし、そのうちリンクｌを通るものの本数をσｉｊ（ｌ）とすると、リンクＩのＢｅｔｗｅｅｎｅｓｓはΣｉｊσｉｊ（ｌ）／σｉｊ／ｎ／（ｎ−１）で定義される。ただし、ｎはノード数である。Ｂｅｔｗｅｅｎｅｓｓが大きなリンクほど、ＳＬＦ時に影響を受け、経路が迂回されるフロー数が多くなる。そのため、ＢｅｔｗｅｅｎｅｓｓはＳＬＦ（スランプフロー値）時の迂回フロー数の大小を測る尺度として用いることができるが、経路の迂回に関しては何等考慮されておらず、ＳＬＦ時の接続性や品質の安定性を図る尺度として用いることはできない。
【０００７】
各リンクの接続性に関する重要度を評価する方法として、Ｒｅｌｉａｂｉｌｉｔｙ Ｐｏｌｙｎｏｍｉａｌ（ＲＰ）（信頼多項式）が知られている。これは、障害発生確率が全リンクで同一であると仮定し、各リンクに対して、ＳＬＦ時に任意に定めたＫ個（全ノード数ｎでもよい）のノード間の接続性が維持される確率として定義される。そして、任意の２本のリンクに対してＮＷ全体の接続性に関する相対的な重要度の大小関係をＲＰにより評価する。ＲＰが接続性に関する重要度を任意に選んだ２本のリンクの相対的な大小関係として評価するのに対して、各リンクに対して、そのリンクを除去することで減少するＳｐａｎｎｉｎｇ Ｔｒｅｅ（データがループを循環し続けることを防止する制御手法）の本数を算出することで、個々のリンクに接続性に関する重要度を表す尺度を直接定義する方法も存在する。
【０００８】
すなわち、Ｓｐａｎｎｉｎｇ Ｔｒｅｅを構成するリンクが消失すると接続性が失われるノードが発生するため、構成するＳｐａｎｎｉｎｇ Ｔｒｅｅの個数が多いリンクほど接続性に関して重要である。同様に、リンクコストとして任意の値が設定されている場合を対象に、個々のリンクに対して構成するＭｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅ（ＭＳＴ）の個数で重要度を定義する方法もある。ところで、次数が１のノードが存在する場合、そのノードを発着とするフローは必ずそのノードに接続するリンクを通るため、Ｂｅｔｗｅｅｎｅｓｓは大きくなるが、そのリンクはＮＷ全体の接続性に対しては大きな貢献を果していない。
【０００９】
このようなバイアスを排除するため、各リンクに対して最小コストの経路が通るノードペア集合をＴｒａｖｅｒｓａｌ ｓｅｔとして定義し、さらにそのようなノードペアのうち少なくとも一方のノードを除去するために除去する必要のあるノード数でリンクの重要度を評価する方法もある。これらの方法を用いることで、障害時の接続性の観点からＮＷの信頼性に対する各リンクの重要度を測ることが可能である。しかし、障害時のフロー長やリンク負荷の増大といった品質の安定性の観点からは重要度を測ることができない。
【００１０】
（目的）
本発明の目的は、このような従来の課題を解決し、単一リンク障害時の迂回トラヒックを考慮し、品質の安定性の観点から、適切なリンク増設・リンク容量増設箇所を求めることが可能なネットワークの増設箇所特定方法を提供することにある。
【課題を解決するための手段】
【００１１】
本発明のネットワークの増設箇所特定方法は、ネットワークのトポロジとリンク容量とが与えられたときに、投資コストを抑えながら、ネットワークの障害時の接続性と安定性を効率性に向上させるために、適切なリンク増設箇所とリンク容量増設箇所を絞り込む方法である。
また、単一リンク障害時にフローのホップ長が最も増加する場所は最大最短閉路（任意の二つのノードを含む経路で経路コストが最小のものを最短閉路と定義し、最短閉路の中でホップ長が最大のものを最大最短閉路と定義）であることから、最大最短閉路のホップ長が小さくなるようにバイパスリンクを設置する方法である。
【００１２】
また、単一リンク障害時にリンクの負荷が最も増加する場所は、容量格差の大きなリンクから構成される複数のハブノードを含むか、ホップ長の長い最短閉路上の小容量リンクであることから、容量格差の大きな最短閉路が存在するかを調べ、存在する場合には、その小容量リンクの容量を増設する方法である。
さらに、単一リンク障害時にボトルネックリンク容量が大きく悪化するフローは、容量格差の大きい最短閉路上の小容量リンクを経由するフローであることから、やはり容量格差の大きな最短閉路上の小容量リンクの容量を増設する方法である。
【発明の効果】
【００１３】
本発明によれば、ネットワークのトポロジとリンク容量が与えられているときに、単一リンク障害時において、フローのホップ長の増加、リンクの負荷の増加、フローのボトルネックリンク容量の減少、の三つを効果的に抑えるためのリンク増設・リンク容量の増設箇所を絞り込むことができる、という効果がある。
【発明を実施するための最良の形態】
【００１４】
本発明の網トポロジ・リンク容量設計方法の実施の形態に係るシステム構成図である。
図１において、１０１はトポロジ情報とリンク容量情報（ネットワーク条件）を入力するＮＷ条件入力装置、１０２は入力装置１０１から情報を受取り、ネットワーク構造の分析を実行するネットワーク構造分析装置、１０３はネットワーク構造分析装置１０２から情報を受取り、リンク増設・リンク容量増設箇所を特定して、それを出力するリンク増設・リンク容量増設箇所出力装置である。
【００１５】
まず、ＮＷ条件入力装置１０１により、ネットワークのトポロジとリンク容量が入力される。ネットワーク構造分析装置１０２により、効果的なリンク増設箇所・リンク容量増設箇所が特定される。そして、得られた増設箇所が、リンク増設・リンク容量増設箇所出力装置１０３によって出力される。
【００１６】
次に、本発明の実施の形態に係るネットワークの効果的な信頼性向上のためのネットワークの増設箇所特定方法について、図面により詳細に説明する。
【００１７】
（１）ネットワークの分類と構造分析
本発明における評価には、ＣＡＩＤＡのＷｅｂページでトポロジとリンク容量が公開されている３９の商用ＩＳＰのバックボーンＮＷを用いる。ただし、Ｃａｂｌｅ ＩｎｔｅｒｎｅｔとＲＩＳＱ（Ｒｅｖｉｅｗ ｏｆ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｏｃｉａｌ Ｑｕｅｓｔｉｏｎｓ）Ｎｅｔｗｏｒｋはトポロジが単一のＳｐａｎｎｉｎｇ Ｔｒｅｅであり、任意のＳＬＦ時に障害フローの迂回が全くできないことから、評価には用いない。
また、Ｕｎｉｌａｔ Ｉｎｃ．は全体が４つと２つのノードの集合に分断されているため、やはり評価には用いない。また、ＰＳＩＮｅｔ，Ｑｗｅｓｔ，Ｔｅｌｓｔｒａ Ｉｎｔｅｒｎｅｔ，ＵＵＮＥＴにおいて、各々、３，２，６，２個のノードが孤立しているため、これらのノードは除外する。
【００１８】
図１４は、評価に用いた３６のＮＷの性能をまとめた図である。
これは、３６のＮＷについて、名称（Ｎａｍｅ）、ノード数（ｎ）、（双方向）リンク数（ｍ）、ノード次数の平均と最大値（Ａｖ，Ｍａｘ）、リンク容量の最小値と最大値（Ｍｉｎ，Ｍａｘ）をまとめたものである。
【００１９】
図２は、評価に用いた３６のＮＷの平均ノード次数と最大ノード次数の散布図である。
図２により、ＮＷを下記１）〜３）の３つのグループに分類する。
１）Ｆｕｌｌ ｍｅｓｈ・・・各ノードがほとんど他の全てのノードと接続しているトポロジで、平均次数と最大次数の差が小さく、平均次数が大きい。平均次数をＥ（ｄ），最大次数をＭａｘ（ｄ）とすると、ここではＥ（ｄ）≧Ｍａｘ（ｄ）−１を満たすＮＷと定義する。２つのＮＷ（ノード次数６および８）が該当する。
【００２０】
２）Ｈ＆Ｓ・・・次数の高いノード（ハブノード）が存在し最大次数が大きい。ハブ＆スポーク型と呼ばれるトポロジ構造であり、航空路線のトポロジが本形態となることが知られている。ハブノードを経由して多数のノードに到達することができるため、フローはホップ長が短くなる特徴がある反面、ハブノードに多数のフローが経由するため、負荷がハブノードに集中し易い。ここでは、ｍａｘ（ｄ）≧１０，Ｅ（ｄ）＜Ｍａｘ（ｄ）−１を満たすＮＷと定義する。１２のＮＷが該当する。
【００２１】
３）Ｌａｄｄｅｒ・・・高次数ノードが存在せず、ループを組み合わせたトポロジ構造となる。平均次数と最大次数が共に小さい。リンク総延長を抑えられる反面、遠方のノードに到達するためには、多数のノードを経由する必要があり、フローのホップ長が長くなる傾向がある。高速道路網が本形態となることが知られている。ここでは、Ｍａｘ（ｄ）＜１０，Ｅ（ｄ）＜Ｍａｘ（ｄ）−１を満たすＮＷと定義する。２２のＮＷが該当する。
【００２２】
図３は、各々の種別に属するＮＷの例を示す図である。
これら３つのＮＷは、全て米国のＩＳＰであるが、種別ごとに大きく形態が異なることが確認される。図３（ａ）のＦｕｌｌ ｍｅｓｈは、各ノード毎に網目のように接続されている。横軸は順位をノード数ｎで除した値である。図３（ｂ）のＨ＆Ｓは、リンク数は多くはないが、次数の高いノードであるハブノードが多く存在している。図３（ｃ）のＬａｄｄｅｒは、高次数ノードが少なく、リンク数もそれほど多くない。
【００２３】
図４は、Ｈ＆Ｓ型ネットワークの特性を示す図である。
Ｈ＆Ｓ型のＮＷは、次数の大きく異なるノードから構成されているため、ノードの接続構造を考察する。図４（ａ）には、Ｈ＆Ｓ型の１２のＮＷの各々に対して、次数の大きな順に正規化ノード次数（ノード次数を最大次数で除した値）をプロットする。横軸は、順位をノード数ｎで除した値である。ＮＷ１６，２９を除く他の１０のＨ＆Ｓ型ＮＷでは、全て全体の５％〜２０％程度の少数のノードが高次数である。
【００２４】
次に、ハブノードが相互に接続されている度合いを調べるため、図４（ｂ）に、ＲＣＣ（ｒｉｃｈ ｃｌｕｂ ｃｏｎｎｅｃｔｉｖｉｔｙ）をプロットする。ＲＣＣは、ノードを次数の大きな順に並べたときの上位ρ個のノード間に存在するリンク数を、可能な総数ρ（ρ−１）／２で除した値で定義され、図ではρをｎで正規化した値に対してプロットしている。ＲＣＣも正規化ノード次数と同様の傾向を示しており、高次数ノードのＲＣＣは高く、多くの高次数ノード間にはリンクが設置されている。
【００２５】
高次数ノード間に設置されたリンクには多数のフローが経由することから、そのような場所には大容量リンクが設置されることが予想される。リンク容量が均一なＮＷ１３を除いた１１のＮＷを対象に、各リンクの正規化リンク容量（リンク容量を最大リンク容量で除した値）を正規化ノード次数積に対して図４（ｃ）にプロットする。正規化ノード次数積を、各リンクの両端のノードの次数の積を、各ＮＷにおける次数積の最大値で除した値で定義する。次数の高いノード間に設置されたリンクほど、正規化ノード次数積が大きくなるが、予想に反して、リンク容量とノード次数積との間には明確な正の相関は見られない。
【００２６】
（２）正常時のフローとリンク負荷特性
障害が発生していない正常時の、フローホップ長、フローのボトルネット（ＢＮ）容量、リンク負荷について考察する。これら特性は、フローの経路設定法に依存するが、本発明においては、ＯＳＰＦ（Ｏｐｅｎ Ｓｈｏｒｔｅｓｔ Ｐａｔｈ Ｆｉｒｓｔ）を想定し、リンクコストとして、シスコ社の推将するリンク容量の逆数に設定する場合（ｉｎｖ．ｃａｐ）と、全リンクで同一の値を設定する場合（ｍｉｎ．ｈｏｐ）の二つを考える。ある発着ノード間に同じコストの経路が複数存在する場合には、全ての最小コスト経路にトラヒックが均一に分散されると仮定する。
【００２７】
各ＮＷに対して、平均フロー長ｈを次式で定義する。
【００２８】
【数１】
ただし、Ｖはノード集合、ｈｓｄはノードｓとｄの間のフロー（フローｓｄと表記）の平均フロー長、σｓｄはフローｓｄの本数、Ｆｓｄはフローｓｄの集合、ｈｓｄ，ｆはｓｄ間のフローｆのホップ長である。
【００２９】
図５は、正常時のフロー特性を示す図である。
図５（ａ）には、３６の各ＮＷに対して、ｉｎｖ．ｃａｐにおけるｈをｍｉｎ．ｈｏｐにおけるｈに対してプロットする。ｍｉｎ．ｈｏｐでは最短ホップ経路が設定されるため、ｉｎｖ．ｃａｐはｍｉｎ．ｈｏｐよりｈが増加し、全てのＮＷは直線ｙ＝ｘ上か右下の領域に存在する。特に、ＮＷ２，４，８，１５，２６のｈが大きいが、これらは全てＬａｄｄｅｒ型である。Ｌａｄｄｅｒ型ＮＷにはハブノードが存在せず、遠方のノードに到達するためには多数のノードを経由する必要があり、ｈが大きくなる傾向がある。
【００３０】
１１のＨ＆Ｓ型ＮＷ、１つのＦｕｌｌ ｍｅｓｈ型ＮＷ、２２のＬａｄｄｅｒ型ＮＷはリンク容量が不均一である。これら２４のＮＷでは、フローが小容量リンクを経由する可能性がある。フローのスループットは経由リンクの最小容量（ＢＮ容量と表記）で抑えられるため、フローのＢＮ容量が重要な性能指標となる。
そこで、図５（ｂ）に、２４のＮＷに対して、ｉｎｖ．ｃａｐにおける平均正規化ＢＮ容量ζをｍｉｎ．ｈｏｐにおけるζに対してプロットする。ただし、ＮＷごとに、フローのＢＮ容量の平均値ｚを平均リンク容量ｃで除したものをζと定義し、
【００３１】
【数２】
【００３２】
【数３】
とする。ｚｓｄはフローｓｄのＢＮ容量、Ｐｓｄ，ｆはｓｄ間のフローｆの経路、ｃｌはリンクｌの容量である。平均正規化ＢＮ容量ζが大きなほどＮＷの資源を有効に活用できていることを意味するが、ｉｎｖ．ｃａｐが良好な特性を示している。また、Ｈ＆Ｓ型ＮＷは他の種別と比較してＢＮ容量が小い傾向が見られる。これはハブノード間に設置されたリンクの一部は図４（ｃ）で見たように小容量リンクであるが、ハブノードを経由することで短いホップ数で多数のノードに到達できるため、多くのフローが経由する結果、ＢＮとなるためである。例えば、ＮＷ５の場合、１５４本のリンクのうち３１本が２．３３３Ｇｂｐｓ、２７本が１５５Ｍｂｐｓ、９６本が４５Ｍｂｐｓであるが、二つのハブノード、シカゴ（次数１６）とダラス（次数１５）間に設置されたリンクの容量は４５Ｍｂｐｓと小さい。そのため、例えばシアトル・アトランタ間のｍｉｎ．ｈｏｐにおける経由はシアトル−シカゴ−ダラス−アトランタとなるが、シカゴ−ダラス間のリンク容量がＢＮとなっている。
【００３３】
次に、正常時に各リンクを経由するフロー数について考慮する。リンクｌの平均フロー数υｌをＢｅｔｗｅｅｎｅｓｓと同様、
【００３４】
【数４】
と定義し、各ＮＷに対して平均フロー数υｌと最大フロー数υｍａｘを、ｍ本の全リンクにわたるυｌの相加平均と最大値により求める。
【００３５】
図６は、正常時のリンク負荷特性を示す図である。
図６（ａ）に、ｉｎｖ．ｃａｐとｍｉｎ．ｈｏｐにおけるυｍａｘをυで除した値の散布図を３６のＮＷに対してプロットする。殆んどのＮＷは直線ｙ＝ｘの右下の領域に存在し、ｉｎｖ．ｃａｐを用いることで大容量リンクにフローが集中し、各リンクを経由するフロー数の格差が拡大することが確認できる。リンク容量の格差が大きく迂回経路を見つけ易いＨ＆Ｓ型のＮＷで、特にこの傾向が強い。
【００３６】
また、図６（ｂ）に、リンク容量が不均一な２４の各ＮＷに対して、リンク容量ｃｌとフロー数υｌとの間の相関係数を、ｉｎｖ．ｃａｐとｍｉｎ．ｈｏｐの各々の場合について散布図としてプロットする。ＮＷによって、ｃｌとυｌとの間の相関係数のばらつきが大きく、ＮＷ種別による明確な傾向が見られない。
ｉｎｖ．ｃａｐを用いることでリンク容量の大きなリンクにフローが集中し、ｃｌとυｌとの間の相関性が向上すること、リンク容量の有効な活用の観点からはｉｎｖ．ｃａｐを用いることが望ましいこと、がそれぞれ確認できる。
【００３７】
また、図６（ｃ）（ｄ）に、ｉｎｖ．ｃａｐとｍｉｎ．ｈｏｐにおける，２４のＮＷの各リンクに対して、正規化リンク容量（ｃｌを各ＮＷの最大リンク容量ｃｍａｘで除した値）と正規化フロー数（υｌをｖｍａｘで除した値）間の散布図を各々示す。ｉｎｖ．ｃａｐを用いることで、リンク容量の小さいリンクを経由するフロー数が抑えられることが確認できる。
【００３８】
（３）接続性に関する評価
ＳＬＦ時の接続性喪失率Ｐｄｃを、一つ以上のＳＬＦ発生パタンにおいて接続性が失われるフローの割合と定義する。すなわち、ｘｓｄ，ｌをリンクｌのＳＬＦ時にフローｓｄの接続性が維持される場合に１、損なわれる場合に０をとる２値変数と定義すると、
【００３９】
【数５】
である。次数ｄが１のノードを発着とするフローは、そのノードが接続するリンクの障害時に必ず接続性が失われる。
【００４０】
図７は、次数１のノード数比率を示す図である。
図７（ａ）に、次数１のノード数のｎに対する割合をｎに対してプロットする。ただし、ＮＷ１１，１８（Ｆｕｌｌ ｍｅｓｈ型）とＮＷ７，１７（Ｌａｄｄｅｒ型）は、次数１のノードが存在しないため、省いている。次数１のノード割合はＮＷによって大きく異なり、ｎやＮＷ種別による明確な傾向は見られない。
【００４１】
また、図７（ｂ）には、ＮＷごとに次数１ノード数比率に対して、Ｐｄｃをプロットする。
これら二つの尺度間には正の相関が見られ、ＳＬＦ時に接続性が失われるフローの大部分は次数１のノードを発着とするものであることが予想される。ただし、次数１ノードに接続するリンクのＳＬＦ時、影響を受けるフローはそのノードを発着とするフローに限定され、ＮＷ全体の信頼性に与える影響は小さい。そこで、Ｐｄｃから次数１ノードに起因するものを除いたＳＬＦ時の接続性喪失率Ｐｄｃ’を算出したところ、２３のＮＷでＰｄｃ’が０．０５を超えたのはＮＷ２，１２，１５，２０のＬａｄｄｅｒ型の４つのＮＷのみであった。これら４つのＮＷのトポロジ形状を調べたところ、ＮＷ２は８２ノード中１７ノードが１本のリンクによって他の部分に接続しており、ＮＷ１２，１５は１本のリンクのＳＬＦにより、ＮＷ全体が二つに分断される形状であり、ＮＷ２０は１５ノード中３ノードが１本のリンクによって他の部分に接続している。
よって、これら４つのＮＷにおいては、ＳＬＦに対して脆弱なアキレス腱となるリンクが存在するが、他の３２のＮＷにはそのようなリンクは存在せず、接続性については堅牢であると言える。以後、ＳＬＦ時の安定性に関する性能指標を算出する際には、接続性が喪失したフローについては全て除いて考える。
【００４２】
（４）フロー長の増加に関する分析
図８は、各フローやリンクに影響を与える障害パタン数比率を示す図である。
ホップ数がｙのフローがＳＬＦ時に影響を受ける障害発生パタン数の全リンク数ｍに対する割合をＲｆ（ｙ）とすると、Ｒｆ（ｙ）＝ｙ／ｍであるので、ＮＷ全体で各フローが平均的に影響を受ける障害発生パタン数のｍに対する比率Ｒｆは、
【００４３】
【数６】
より算出できる。
図８（ａ）には、３６のＮＷに対して、ｉｎｖ．ｃａｐにおけるＲｆとｍｉｎ．ｈｏｐ
におけるＲｆの散布図を示す。ｉｎｖ．ｃａｐを用いると、ｍｉｎ．ｈｏｐと比較してフローの平均ホップ長が増加するため、Ｒｆは若干大きくなる。また、Ｌａｄｄｅｒ型のＮＷはフローのホップ長が長くなる傾向があるため、Ｒｆが大きい。殆んどのＮＷはＲｆが０．１５程度より小さいため、ＳＬＦ時の平均的なフロー長増加特性を評価するに際し、各フローに対して影響を受けるリンク障害パタンのみを考慮する。すなわち、ＳＬＦ時のフローｓｄの平均フロー長ｈ’ｓｄを、
【００４４】
【数７】
で定義する。ただし、ｍｓｄはＳＬＦ時にフローｓｄが影響を受けるリンク数、Ｅｓｄはそのリンク集合、ｈｓｄ，ｌはリンクｌのＳＬＦ時のノードｓ，ｄ間のフローの平均ホップ長、σｓｄ，ｌはリンクｌのＳＬＦ時にノードｓ，ｄ間に設置されるフロー数、Ｆｓｄ，ｌはそのフロー集合、ｈｓｄ，ｌ，ｆはＦｓｄ，ｌに属するフローｆのホップ長である。そして、ＳＬＦ時の平均フロー長倍率ξを、ξ＝Σｓｄ∈Ｖｈ’ｓｄ／ｈｓｄ／ｎ／（ｎ−１）で算出する。また、ＳＬＦ時の最大フロ長倍率ξｍａｘを、
【００４５】
【数８】
で定義する。ただし、ｈｍｉｎ，ｓｄは正常時にノードｓ，ｄ間に設置されるフローの最小ホップ長である。
【００４６】
図９は、ＳＬＦ時のフロー長増加率を示す図である。
図９では、３６のＮＷを対象にξｍａｘとξの散布図を、（ａ）ｉｎｖ．ｃａｐと（ｂ）ｍｉｎ．ｈｏｐの各々について示している。ｍｉｎ．ｈｏｐとｉｎｖ．ｃａｐとでは大きな差異は見られない。Ｌａｄｄｅｒ型ＮＷは全体的にフロー長が長いため、ＳＬＦ時の増加の度合いも大きくなる傾向が見られる。特に、５つのＮＷはξｍａｘが突出して大きいが、これらは正常時の平均フロー長が大きい５つのＮＷである（図５（ａ）参照）。
次に、これらのＮＷで、ξｍａｘが大きな要因を考察する。
【００４７】
正常時のトポロジにおいて、任意のノードＡから出発して同じリンクを逆方向も含めて２回以上経由することなく、任意の他のノードＢを経由し、さらに元のノードＡに戻ることのできる経路の中で、最小コストのものをノードＡとＢの最短閉路と定義する。最短経路の存在しない二つのノード間フローは、どのように経路を設定しても必ず経由する必要のあるリンクが存在することになり、そのリンクのＳＬＦ時には接続性が失われるため、ＳＬＦ時の安定性の評価の対象外となる。従って、最短閉路が存在するノードペアについてのみ考える。
【００４８】
ノードＡ，Ｂの最短閉路上にはリンクを共有しない二つの経路がＡとＢの間に存在するが、そのうちコストの小さい方がＡＢ間の最小コスト経路となり、もう一方が、次にコストの小さい経路となる。そのため、正常時には最短閉路上のコストの小さい経路が用いられ、この経路上のリンクのＳＬＦ時には最短閉路上のもう一方の経路にフローが迂回される。そのため、最短閉路上の迂回経路のホップ数を正常時経路のホップ数で除したものがＡＢ間のフロー長倍率となる。よって、各ＮＷにおいて、隣接する二つのノードに対して定義される最短閉路の中でホップ数が最大のものを最大最短閉路と定義すると、最大最短閉路を導く二つの隣接ノード間のリンクのＳＬＦ時に、これら二つのノード間のフローのフロー長倍率がξｍａｘを与え、最大最短閉路のホップ数をθとすると、ξｍａｘ＝θ−１となる。
【００４９】
図１０は、Ａｔ Ｈｏｍｅ ｎｅｔｗｏｒｋのトポロジを示す図である。
図１０では、ξｍａｘが突出して大きかった５つのＮＷの例として、ＮＷ４のトポロジを示している。このＮＷには、θ＝１４の最大最短閉路が２つ存在し、隣接ノードペア７，９などの最短閉路（７−９−１５−１８−２１−３９−４０−４１−３６−３８−１４−１２−１０−８−７）と、隣接ノードペア３３，３４などの最短閉路（１８−２０−２８−２９−３０−３１−３２−３３−３４−３５−３７−４０−３９−２１−１８）が該当する。例えば、ノード７，９間のリンクのＳＬＦ時、これらのノード間のフローのホップ長が１から１３に増加し、ξｍａｘ＝１３となる。
【００５０】
ξｍａｘの大きなＮＷはξも大きな傾向があり、ξｍａｘの突出して大きな５つのＮＷのうちＮＷ２６を除く４つは、１．８を超えていた。また、ＮＷ１１，１７，１８，２０，２１の５つのＮＷは、ξｍａｘは小さいもののξが大きい。このうち、ＮＷ１１と１８はＦｕｌｌ ｍｅｓｈ型であり、正常時には殆んどのノード間のフローが１ホップであるのに対して、ＳＬＦ時には影響を受けたフローが２ホップとなり、ξが２に近くなる。また、ＮＷ１７，２０，２１はループトポロジに近く、θの総リンク数ｍに対する比率が大きく、多数のフローのフロー長倍率が大きくなる結果、ξが大きい。
【００５１】
（５）リンク負荷の増加に関する分析
各リンクを経由するフロー数が正常時のフロー数と比較して、増加するＳＬＦのパタン数の全リンクにわたる平均を、リンク数ｍで除した値をＲｌと定義する。図８（ｂ）に３６のＮＷに対して、ｉｎｖ．ｃａｐにおけるＲｌの散布図を示す。ｉｎｖ．ｃａｐを用いると、特定のリンクにフローが集中するため、多くのリンクに対しては障害時にフローが迂回されず、ｍｉｎ．ｈｏｐと比較してＲｆが小さい。
【００５２】
殆んどのＮＷは、Ｒｆが０．５程度より小さいため、ＳＬＦ時の平均的な経由フロー数増加特性を評価するに際し、やはり各リンクの経由フロー数が増加するリンク障害パタンのみを考慮する。ＳＬＦ時のリンクの平均経由フロー数倍率εを次式で定義する。
【００５３】
【数９】
ただし、εｌはＳＬＦにおけるリンクｌの平均フロー数倍率、υ’ｌ，ｅはリンクｅのＳＬＦ時におけるリンクｌのフロー数（算出方法は（４）に順じる）。ｍε，ｌはυ’ｌ，ｅ＞υｌとなるＳＬＦパタン数、Ｅε，ｌはそのＳＬＦリンク集合、ｍεはｍε，ｌ＞０のリンク数、Ｅｅはそのリンク集合である。また、ＳＬＦ時の最大フロー数倍率εｍａｘを次式で定義する。
【００５４】
【数１０】
ただし、εｌεｍａｘの算出において、υｌ＝０のリンクはυｌ＝１と置換える。
【００５５】
図１１は、ＳＬＦ時のフロー数増加率を示す図である。
図１１では、３６のＮＷを対象にεｍａｘとεの散布図を、（ａ）ｉｎｖ．ｃａｐと（ｂ）ｍｉｎ．ｈｏｐの各々について示している。ｍｉｎ．ｈｏｐを用いると、リンク間で経由フロ−数の格差が大きいため、ＳＬＦ時のフロー数倍率も高くなる。
リンクごとにＳＬＦ時のフロー数倍率の格差が大きく、εｌの大きなリンクが存在するＮＷはεも大きい。ｉｎｖ．ｃａｐの場合、８つのＮＷで特にこれらの値が大きいが、その要因を考察する。
【００５６】
ＳＬＦ時のフロー数倍率が高いリンクは正常時に経由するフロー数が少なく、かつＳＬＦ時に大量のフローが迂回される障害パタンが存在するリンクである。そのようなリンクは、（イ）二つ以上のハブノードを含む最短閉路、（ロ）ホップ数の長い最短閉路、のいずれかに存在すると考えられる。そのような最短閉路を構成するリンクの容量の格差が大きく一部のリンク容量が極端に小さい場合、小容量リンクの両端のノードＡ，Ｂ間のフローはｉｎｖ．ｃａｐにおいては、正常時にはそのリンクを用いず、最短閉路上を周回する経由を用いる。このようなリンクは、正常時には経由するフロー数がゼロとなるが、最短閉路上に存在する少なくとも一方がＡ，Ｂとは異なる２個のノードのうち、やはり同一の最短閉路を構成するものの間の任意のリンクのＳＬＦ時には、大量のフローがＡ，Ｂ間を接続するリンクに迂回される結果、フロー数倍率が高くなる。
【００５７】
図１２は、ａｂｏｖｅ．ｎｅｔのトポロジを示す図である。
図１２では、εの大きいＮＷの例として、ＮＷ１のトポロジを示している。
ノードペア０，１および１，２の最短閉路は（０−１−２−０）であるが、リンク（０，１）と（０，２）の容量が６２２Ｍｂｐｓであるのに対して、リンク（１，２）の容量１５５Ｍｂｐｓである。そのため、正常時、ノード１，２間のフローも含め、リンク（１，２）には全くフローが経由しないが、二つのハブノード０と１の間のリンクのＳＬＦ時、大量のフローが（０−２−１）の経路に迂回される結果、リンク（１，２）のフロー数倍率が高くなる。
【００５８】
最短閉路長が短い場合に、単一のリンクを通るコストが最短閉路上を周回するコストより大きくなり易いため、εｌが大きなリンクは３本のリンクから構成される最短閉路において生じ易い。実際、εｍａｘの大きな８つのＮＷのうち、ＮＷ１，３，５，３３は２つ以上のハブノードを含み、リンク容量格差の大きな３本のリンクから構成される最短閉路において、εｌが最大となった。また、ＮＷ８，２３，２６は、各々、６，５，６ホップの最短閉路上においてεｌが最大となった。ただし、ＮＷ２は１７のノードが１本のリンクで接続する特殊な形状となっており、例外的に、接続点からＮＷの他の部分に接続する容量の異なる２本のリンクでεｌが最大となった。
【００５９】
このように、容量格差の大きいリンクで最短閉路を構成した場合、ＳＬＦ時に一部のリンクで経由フロー数が非常に増加する場合がある。特に、リンク容量の小さなリンクで、フロー数倍率が高くなる場合、ＳＬＦ時にリンク輻輳を生じる要因となる。
【００６０】
図１３は、ＳＬＦ時の正規化平均迂回フロー数を示す図である。
上記段落〔００５９〕に記載したことを確認するため、各リンクのＳＬＦ時の平均迂回フロー数を最大迂回フロー数で正規化した値ψを、正規化リンク容量に対して図１３にプロットする。ただし、リンク容量が不均一な２４のＮＷの各リンクに対して、（ａ）ｉｎｖ．ｃａｐ、（ｂ）ｍｉｎ．ｈｏｐの場合について示している。
ψは、次式で定義する。
【００６１】
【数１１】
ただし、ψｌはＳＬＦにおけるリンクｌの平均フロー数倍率、υ’ｌ，ｅはリンクｅのＳＬＦ時におけるリンクｌのフロー数（算出方法は（４）に順じる）。ｍψ，ｌはυｌ，ｅ＞０のＳＬＦパタン数、Ｅψ，ｌはそのＳＬＦリンク集合、ｍψはｍψ，ｌ＞０のリンク数、Ｅψはそのリンク集合である。最大リンク容量の０．１〜０．０１倍を下回る小容量リンクの多くに、最大迂回フロー数に近い大量のフローが迂回されることが確認できる。
【００６２】
（６）フローのＢＮ容量の低下に関する分析
ＳＬＦ時のフローのＢＮ容量最大低下倍率ηを、次式で定義する。
【００６３】
【数１２】
ただし、ｚ’ｓｄ，ｅは、フローｓｄのリンクｅのＳＬＦ時のＢＮ容量である。
ｉｎｖ．ｃａｐにおいて、リンク容量の不均一な２４のＮＷを対象にＢＮ容量最大低下倍率ηを算出したところ、８つのＮＷでη＝１であり、７つのＮＷで０．２５〜０．４であり、５つのＮＷで０．０５〜０．１であり、ＮＷ５，２６，３１，３３の４つのＮＷで０．０２未満となった。η＜０．０２の４つのＮＷについてＢＮ容量低下倍率が最大となったフローを調べたところ、ＮＷ５，２６，３３では平均フロー数倍率εｌが最大となったリンクを経由するフローであった。
【００６４】
また、ＮＷ３１においても、容量格差の大きなリンクで構成される最短閉路において、容量の小さなリンクのＳＬＦ時にこのリンクを経由するフローのＢＮ容量低下倍率が最大となった。以上のことから、やはり容量格差の大きなリンクで構成されたハブノードを含むか、ホップの長い最短閉路を有するＮＷにおいて、ＳＬＦ時のフローのＢＮ容量低下倍率が大きくなることが確認できる。
【００６５】
（７）分析のまとめと設計指針
公開されている３６の商用ＩＳＰのバックボーンＮＷを対象に、単一リンク障害（ＳＬＦ）に対する信頼性を接続性と品質の安定性の観点から評価し、信頼性が劣化する要因について分析した結果、以下のことが明らかとなった。
イ）ＳＬＦによりＮＷが分断されるリンクを有するＮＷは４つのみであり、大部分のＮＷは接続性の観点からは堅牢である。
ロ）ＳＬＦ時のフロー長の最大増加量は、最大最短閉路によって決まり、最大最短閉路長が長いＬａｄｄｅｒ型のＮＷがＳＬＦ時のフロー長の増加度合いが高くなる傾向がある。
ハ）容量格差の大きなリンクから構成される，２個以上のハブノードを含むか、ホップ長の長い最短閉路上の小容量リンクが、ＳＬＦ時に経由するフロー数の増加度合いが大きい。ハブノードを多く含むＨ＆Ｓ型のＮＷにおいて、ＳＬＦ時のリンクのフロー数増加度合いが高くなる傾向がある。
ニ）容量格差の大きい最短閉路上の小容量リンクを経由するフローのＢＮ容量がＳＬＦ時に大きく低下する傾向にある。
【００６６】
以上のことから、Ｈ＆Ｓ型のＮＷにおいては容量格差の大きな最短閉路が存在するか調べ、存在する場合には最短閉路上の小容量リンクの容量を増設することが、またＬａｄｄｅｒ型のＮＷにおいてはホップ長が大きな最大最短閉路が存在するか調べ、存在する場合には、最大最短閉路のホップ長が小さくなるよう、バイパスリンクを設置することが、ＩＳＰにとって投資コストを抑えながら信頼性を効果的に向上させるために有効である。
【００６７】
図１５は、本発明のリンク増設箇所またはリンク容量増設箇所特定処理の動作フローチャートである。
本発明では、ネットワーク構造分析装置１０２のコンピュータにおけるプログラムの動作により、リンク増設またはリンク容量増設の箇所が絞られ、バイパスリンクの設置またはリンクの容量の増設の指示を出力装置から出力される。
コンピュータは、ステップ２０２〜２０４の３つの手順のうちの１つないし３つを実施して、リンク増設またはリンク容量増設の箇所を絞る。１つ目は、フローのホップ長が最も増加する場所は最大最短閉路（任意の二つのノードを含む経路で経路コストが最小のものの中で、ホップ長が最大のもの）であることから、最大最短閉路が存在するか否かを判別する（ステップ２０２）。存在すると判別されれば、その経路のホップ長を小さくするため、バイパスリンクを設置するか、または、小容量リンクの容量を増設する指示情報を出力する（ステップ２０６）。
【００６８】
２つ目は、ボトルネットリンク容量が大きく悪化するフローとして、最大最短閉路で、容量格差の大きい経路上の小容量リンクを経由するフローがあるか否かを判別する（ステップ２０３）。あると判別されれば、その経路上の小容量リンクの容量を増設する指示情報を出力する（ステップ２０７）。
３つ目は、容量格差の大きなリンクからなる複数のハブノード、または、ホップ長の長い経路上の小容量リンクを含むか否かを判別する（ステップ２０４）。含むと判別されれば、それら複数のハブノード間のリンクの増設、または、小容量リンクの容量リンクの容量を増設する指示情報を出力する（ステップ２０８）。
【００６９】
このようにして、本発明によれば、ネットワークのトポロジとリンク容量が入力されたとき、コンピュータの制御により、投資コストを抑えながら、ネットワークの障害時の接続性と安定性を効率的に向上させるため、適切なリンク増設箇所とリンク容量増設箇所を絞り込むことが可能である。
【図面の簡単な説明】
【００７０】
【図１】本発明の一実施形態に係るシステム構成図である。
【図２】平均次数と最大次数の散布図である。
【図３】ネットワークトポロジの例を示す図である。
【図４】Ｈ＆Ｓ型ネットワークの特性を示す図である。
【図５】正常時のフロー特性を示す図である。
【図６】正常時のリンク負荷特性を示す図である。
【図７】次数１のノード数比率を示す図である。
【図８】各フローやリンクに影響を与える障害パタン数比率を示す図である。
【図９】ＳＬＦ時のフロー長増加率を示す図である。
【図１０】Ａｔ Ｈｏｍｅ ｎｅｔｗｏｒｋのトポロジを示す図である。
【図１１】ＳＬＦ時のフロー数増加率を示す図である。
【図１２】ａｂｏｖｅ．ｎｅｔのトポロジを示す図である。
【図１３】ＳＬＦ時の正規化平均迂回フロー数を示す図である。
【図１４】３６のＩＳＰバックボーンネットワークの基本特性を示す図である。
【図１５】本発明の一実施形態に係るリンク増設箇所またはリンク容量増設箇所特定処理のフローチャートである。
【符号の説明】
【００７１】
１０１ ＮＷ条件入力装置
１０２ ネットワーク構造分析装置
１０３ リンク増設・リンク容量増設箇所出力装置
【特許請求の範囲】
【請求項１】
ネットワークのトポロジとリンク容量の各情報をコンピュータに入力し、該コンピュータの制御により、投資コストを抑えながら、ネットワークの障害時の接続性と安定性を効率性に向上させるために、リンク増設箇所またはリンク容量増設箇所を絞り込む特定方法であって、
該コンピュータは、単一りンクの障害時にフローのホップ長が最も増加する場所として、任意の二つのノードを含む経路で経路コストが最小のものの中から、ホップ長が最大の経路を算出することで検出し、
該コンピュータは、検出された経路のホップ長が小さくなるように、該当ノード間にバイパスリンクを設置するか、あるいは、該当ノード間の小容量リンクの容量を増設するか、いずれかの指示情報を出力することを特徴とするネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【請求項２】
前記コンピュータは、単一リンク障害時に、リンクの負荷が最も増加する場所として、任意の二つのノードを含む経路で経路コストが最小のものの中から、容量格差の大きなリンクから構成される複数のハブノードを含むか、あるいは、ホップ長の長い経路上の小容量リンクを含むかを、それぞれ算出することにより、判別し、
該コンピュータは、判別の結果、容量格差の大きなリンクからなるハブノード、あるいは、前記小容量リンクを含むことが判別された場合には、容量格差の大きなリンクからなる複数のハブノード間のリンク、あるいは、前記小容量リンクの容量を増設する指示情報を出力することを特徴とする請求項１に記載のネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【請求項３】
前記コンピュータは、単一リンク障害時にボトルネックリンク容量が大きく悪化するフローとして、任意の二つのノードを含む経路で経路コストが最小のものの中から、ホップ長が最大の経路の中で、容量格差の大きい経路上の小容量リンクを経由するフローを算出することにより検出し、
該コンピュータは、検出された容量格差の大きな経路上の小容量リンクの容量を増設することを特徴とする請求項１に記載のネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【請求項４】
前記コンピュータは、Ｈ＆Ｓ型のネットワークに対して、任意の二つのノードを含む経路で経路コストが最小のものの中から、ホップ長が最大の経路の中で、容量格差の大きな経路が存在するかを、算出することにより判別し、判別の結果、存在する場合には、小容量リンクの容量を増設する指示情報を出力することを特徴とする請求項１に記載のネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【請求項５】
前記コンピュータは、Ｌａｄｄｅｒ型のネットワークに対して、任意の二つのノードを含む経路で経路コストが最小のものの中から、ホップ長が最大の経路が存在するかを、算出することにより判別し、判別の結果、存在する場合には、該ホップ長が最大の経路のホップ長が小さくなるように、該当ノード間にバイパスリンクを設置する指示情報を出力することを特徴とする請求項１記載のネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【請求項１】
ネットワークのトポロジとリンク容量の各情報をコンピュータに入力し、該コンピュータの制御により、投資コストを抑えながら、ネットワークの障害時の接続性と安定性を効率性に向上させるために、リンク増設箇所またはリンク容量増設箇所を絞り込む特定方法であって、
該コンピュータは、単一りンクの障害時にフローのホップ長が最も増加する場所として、任意の二つのノードを含む経路で経路コストが最小のものの中から、ホップ長が最大の経路を算出することで検出し、
該コンピュータは、検出された経路のホップ長が小さくなるように、該当ノード間にバイパスリンクを設置するか、あるいは、該当ノード間の小容量リンクの容量を増設するか、いずれかの指示情報を出力することを特徴とするネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【請求項２】
前記コンピュータは、単一リンク障害時に、リンクの負荷が最も増加する場所として、任意の二つのノードを含む経路で経路コストが最小のものの中から、容量格差の大きなリンクから構成される複数のハブノードを含むか、あるいは、ホップ長の長い経路上の小容量リンクを含むかを、それぞれ算出することにより、判別し、
該コンピュータは、判別の結果、容量格差の大きなリンクからなるハブノード、あるいは、前記小容量リンクを含むことが判別された場合には、容量格差の大きなリンクからなる複数のハブノード間のリンク、あるいは、前記小容量リンクの容量を増設する指示情報を出力することを特徴とする請求項１に記載のネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【請求項３】
前記コンピュータは、単一リンク障害時にボトルネックリンク容量が大きく悪化するフローとして、任意の二つのノードを含む経路で経路コストが最小のものの中から、ホップ長が最大の経路の中で、容量格差の大きい経路上の小容量リンクを経由するフローを算出することにより検出し、
該コンピュータは、検出された容量格差の大きな経路上の小容量リンクの容量を増設することを特徴とする請求項１に記載のネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【請求項４】
前記コンピュータは、Ｈ＆Ｓ型のネットワークに対して、任意の二つのノードを含む経路で経路コストが最小のものの中から、ホップ長が最大の経路の中で、容量格差の大きな経路が存在するかを、算出することにより判別し、判別の結果、存在する場合には、小容量リンクの容量を増設する指示情報を出力することを特徴とする請求項１に記載のネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【請求項５】
前記コンピュータは、Ｌａｄｄｅｒ型のネットワークに対して、任意の二つのノードを含む経路で経路コストが最小のものの中から、ホップ長が最大の経路が存在するかを、算出することにより判別し、判別の結果、存在する場合には、該ホップ長が最大の経路のホップ長が小さくなるように、該当ノード間にバイパスリンクを設置する指示情報を出力することを特徴とする請求項１記載のネットワークのリンク増設箇所またはリンク容量増設箇所特定方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【公開番号】特開２００９−２０６７１８（Ｐ２００９−２０６７１８Ａ）
【公開日】平成２１年９月１０日（２００９．９．１０）
【国際特許分類】
【出願番号】特願２００８−４５９０６（Ｐ２００８−４５９０６）
【出願日】平成２０年２月２７日（２００８．２．２７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２１年９月１０日（２００９．９．１０）
【国際特許分類】
【出願日】平成２０年２月２７日（２００８．２．２７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]