(57)【要約】      （修正有）【課題】設計者の主観的な評価尺度に対する重要度に応じた適切な網トポロジ設計を可能とする。【解決手段】入力部１０１においては、入力装置から入力される、ネットワークの全リンク長とトラヒック比率で重みづけした平均ホップ長および単一リンク障害時に接続性が喪失するトラヒック量比率の平均値を含む条件情報を入力して記憶装置に記憶し、候補トポロジ集合生成部１００においては、記憶装置から条件情報を読み出し、予め定められた時間内で候補トポロジ集合を生成し、出力部１０３においては、候補トポロジ集合生成部１００が生成した候補トポロジ集合を出力装置を介して出力する。【選択図】図６
2010206581.tif 000002
【特許請求の範囲】
【請求項１】
全ノードの位置が与えられ、任意のノード間にリンクを設置可能なネットワークにおけるトポロジを、プログラムされたコンピュータ処理によって生成するシステムであって、
プログラムされたコンピュータの処理を実行する手段として、
上記ネットワークにおける全ノード間の接続性を満たすリンクコストが最小のトポロジを生成する第１の手段と、
該第１の手段が生成したトポロジに対して、単一リンク障害時の接続性が予め定められた水準を維持するよう最小限のリンクを付加したトポロジを生成する第２の手段と、
該第２の手段が生成したトポロジに対して、ノード間の経路選択の多様性が増加するよう予め定められた数のリンクを付加したトポロジを生成する第３の手段と
を有することを特徴とする候補トポロジ生成システム。
【請求項２】
プログラムされたコンピュータ処理によって、
ネットワークのトポロジを生成するシステムであって、
プログラムされたコンピュータの処理を実行する手段として、
入力装置から入力される、上記ネットワークの全リンク長とトラヒック比率で重みづけした平均ホップ長および単一リンク障害時に接続性が喪失するトラヒック量比率の平均値を含む条件情報を入力して記憶装置に記憶する入力手段と、
上記記憶装置から上記条件情報を読み出し、予め定められた時間内で候補トポロジ集合を生成する候補トポロジ集合生成手段と、
該候補トポロジ集合生成手段が生成した候補トポロジ集合を出力装置を介して出力する出力手段と
を有することを特徴とするトポロジ生成システム。
【請求項３】
請求項２に記載のトポロジ生成システムであって、
上記条件情報としてリンクコストを含み、
上記候補トポロジ集合生成手段は、
正常時の全ノード間の接続性確保を条件に、全リンクコストの総和を最小とするトポロジである最小木を生成し、生成した最小木を構成するノードをリンク設置可能位置として特定する最小木生成手段を具備し、
該最小木生成手段が特定したリンク設置可能位置にリンクを設置した候補トポロジ集合を生成することを特徴とするトポロジ生成システム。
【請求項４】
請求項３に記載のトポロジ生成システムであって、
上記リンクコストとして、リンク距離を当該ノード間のトラヒック量比率で除した値を用いることを特徴とするトポロジ生成システム。
【請求項５】
請求項３もしくは請求項４のいずれかに記載のトポロジ生成システムであって、
上記候補トポロジ集合生成手段は、
上記最小木生成手段が生成した最小木において上記リンク設置可能位置として含まれない各々のノードに対して、一本だけリンクを設置したトポロジの、単一リンク障害時の平均接続性喪失トラヒック量比率を算出し、該算出した比率が最小となるノードをリンク設置可能位置として特定してリンクを設置する処理を、当該比率が予め定められた値以下となるまで反復する常設リンク付加手段を具備し、
該常設リンク付加手段が特定した全てのリンク設置可能位置にもリンクを設置した候補トポロジ集合を生成することを特徴とするトポロジ生成システム。
【請求項６】
請求項５に記載のトポロジ生成システムであって、
上記候補トポロジ集合生成手段は、
上記常設リンク付加手段が特定したリンク設置可能位置として含まれない任意のノードの各々に対して、一本だけリンクを設置したトポロジのトラヒック量で重みづけた平均ホップ長を算出し、
該算出した平均ホップ長が最小となるリンク設置可能位置をリンク設置候補位置として選択する処理を、予め定められたリンク本数ｘだけ反復するリンク設置候補位置選択手段を具備し、
該リンク設置候補位置選択手段が選択した全てのリンク設置可能位置にもリンクを設置した候補トポロジ集合を生成することを特徴とするトポロジ生成システム。
【請求項７】
請求項６に記載のトポロジ生成システムであって、
上記候補トポロジ集合生成手段は、
上記リンク設置候補位置選択手段が選択したｘ本のリンク設置可能位置の各々に対して、リンクを設置する場合としない場合の組み合わせてとして構成可能な２ｘ個のトポロジを候補として生成する候補トポロジ生成手段を具備することを特徴とするトポロジ生成システム。
【請求項８】
プログラムされたコンピュータ処理によって、
ネットワークのトポロジを生成するシステムのトポロジ生成方法であって、
プログラムされたコンピュータ処理による実行手順として、
請求項１から請求項７のいずれかに記載のトポロジ生成システムにおける各手段が実行する処理手順を含むことを特徴とするトポロジ生成方法。
【請求項９】
コンピュータを、請求項１から請求項７のいずれかに記載のトポロジ生成システムにおける各手段として機能させるためのプログラム。
【請求項１０】
プログラムされたコンピュータ処理によって、
ネットワークのトポロジの設計を行うシステムであって、
プログラムされたコンピュータ処理を実行する手段として、
請求項１から請求項７のいずれかに記載のトポロジ生成システムにおける各手段を具備し、
上記出力手段が出力した候補トポロジ集合に含まれる各トポロジを用いて、上記ネットワークのトポロジの設計を行うことを特徴とする網トポロジ設計システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおけるトポロジの構成技術に係り、特に、複数のトポロジ候補を効率的に選定し、網トポロジの効率的な設計を可能とするのに好適な技術に関するものである。
【背景技術】
【０００２】
光ファイバやルータといったネットワークの物理的な資源を管理・運営している通信事業者やＩＳＰ（Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｃｅ  Ｐｒｏｖｉｄｅ）にとって、物理的な網トポロジをどのように構成するかという物理トポロジ設計は重要な問題である。
【０００３】
物理トポロジは、ノードやリンクの設備コスト、網の管理・保守コスト、障害に対する信頼性、などを決める要因となる。また物理トポロジは、リンク負荷やパケットの経路に影響を与え、伝送遅延品質やスループットといったユーザ品質を定める１つの要因となる。
【０００４】
ユーザにとっては、経由ノードでの輻輳を回避し、経路の総距離が短いことが伝送遅延を抑える意味で望ましい。伝送資源の利用効率や信頼性の観点からも、特定のリンクへのトラヒック集中を避け、可能な限り全てのリンクにトラヒック負荷を分散させることが望ましい。
【０００５】
また、設備コストや管理・保守コストを抑えるために、設置ノード数やリンク数を減らすと、特定のリンクに負荷が集中する可能性や、リンクやノードの障害時にノード間の接続性が喪失する可能性が高まり、信頼性が低下する。
【０００６】
このように、網トポロジを設計する際には、トラヒックの分散度合い、パスの平均長、網コスト、信頼性、といった、それぞれ単位が異なり、しかも互いに相反する複数の評価尺度を同時に考慮する必要がある。
【０００７】
このような、複数の評価尺度を同時に考慮した合理的な意思決定を行う技術として、ＡＨＰ（Ａｎａｌｙｔｉｃ  Ｈｉｅｒａｒｃｈｙ  Ｐｒｏｃｅｓｓ）が知られている。ＡＨＰでは、関連する要素を階層構造によって把握し、評価尺度の重要度といった定性的な尺度を一対比較により定量化し、合理的な意思決定を可能とする。
【０００８】
そこで、本願発明者は、ＡＨＰを網トポロジ評価へ適用した技術を、特許文献１において提案している。この技術では、ＡＨＰを用いることで、以下のように、設計者の主観的な評価尺度に対する重要度に応じた適切な網トポロジ設計が可能となる。
【０００９】
通常、意思決定においては、「問題Ｐ」、「評価尺度Ｖ」、「代替案Ａ」の三種類の要素が存在する。ＡＨＰでは、これら要素を、図１に示すような階層構造で把握する。
【００１０】
ただし、互いに関連のある要素間を直線で結び（図１では便宜上、一部のみ示している）、評価尺度Ｖは、複数の階層構造（Ｖ１，Ｖ２，…）をとることも可能である。図１では２階層構造を示している。
【００１１】
そして、各要素間の関連性の強さ（重み）を算出し、最終的に、各代替案ＡｉのスコアＳｉを導出する。
【００１２】
評価尺度Ｖの問題Ｐに対する重みを計算する場合、定量的な評価値がもともと存在しないため、何らかの方法で定量化する必要がある。ＡＨＰでは、以下に説明するように、同一の階層に属する要素集合に対して、全ての要素間の重要度を一対比較することにより定量化を図る。
【００１３】
まず、階層ｃに属する要素Ｘｉと要素Ｘｊに対して、図２に示す値を、要素Ｘｉの要素Ｘｊに対する相対的な重要度ａｉｊに設定する。要素Ｘｉの本来の重みをｗｉ、要素Ｘｊの本来の重みをｗｊとすると、理想的には、ａｉｊ＝ｗｉ／ｗｊという関係を満たす。
【００１４】
重要度ａｉｊを要素にもつ一対比較行列をＡとし、各要素の重みｗｉを要素にもつベクトルｗを、行列Ａの右側から乗じると、Ａｗ＝ｎｗが成立する。ただしｎは要素の数である。よって、重みベクトルは行列Ａの固有ベクトルであり、ｎは固有値（最大固有値）となる。
【００１５】
実際には、一対比較を完全な整合性を持って行うことは困難なため、行列Ａの整合性を判断する必要がある。すなわち、行列Ａの最大固有値をλｍａｘとすると、λｍａｘ≧ｎとなる。そこで、式「Ｃ．Ｉ．＝（λｍａｘ−ｎ）／（ｎ−１）」で定義される整合度Ｃ．Ｉ．を用いて整合性を判断する。
【００１６】
整合性が増すほど、行列Ａの最大固有値λｍａｘは減少し、完全に整合性がとれているときには、行列Ａの最大固有値λｍａｘ＝ｎとなるので、整合度Ｃ．Ｉ．は小さなほど整合性が高く、一般的には、Ｃ．Ｉ．が０．１以下であれば合格とする。
【００１７】
階層ｃにおける要素ｉの、階層ｃ−１の要素ｊに対する重みをｗｉｊｃとする。階層ｃ−１の要素のうち、階層ｃの要素Ｖｉｃが関係する要素の集合をΦｉｃとすると、階層ｃの要素Ｖｉｃの問題Ｐに対するスコアＳｉｃは、次の数１の式より算出できる。
【００１８】
【数１】
2010206581.tif 000003
【００１９】
階層１においては、問題Ｐに対する各要素の重みがそのままスコアＳｉ１となる。
【００２０】
以下、階層ｃ＝２，３，…の順にスコアＳｉｃを算出することができ、最終的に、各代替案ＡｉのスコアＳｉを得る。そして、スコアが最大の代替案が最適な選択肢となる。
【００２１】
このようなＡＨＰをネットワークにおけるトポロジ設計に適用すると、トップの階層（階層０）には解くべき問題Ｐ（この場合、“最適なネットワークの選択”）が、中央の階層（階層１）には評価尺度Ｖｉが、そしてボトム（階層２）には候補トポロジが並ぶ。
【００２２】
階層１（評価尺度）の問題Ｐに対するスコア（重み）は、一対比較により求めることができる。また、階層２（候補トポロジ）の階層１の各要素（評価尺度）に対するスコア（重み）は、評価尺度が定量的な評価値をもつ場合、一対比較による評価を行う必要はない。
【００２３】
ＡＨＰは、スコアが高い要素を高く評価する。そのため、各評価尺度が小さな値をとるほど良好である場合には、候補トポロジｉの評価尺度ｊの値Ｖｉｊの逆数をＸｉｊ（Ｘｉｊ＝１／Ｖｉｊ）とし、この逆数Ｘｉｊに基づいて重みを算出する。
【００２４】
階層２の要素の重みｗｉｊ２は、正規化条件「Σｉ＝１Ｎ２（ｗｉｊ２）＝１」（Ｎ２は階層２の要素数）を満たす必要があるが、通常、ＡＨＰでは、Ｘｉｊを単に全候補中で正規化した値を重みと見なすため、階層２の要素の重みｗｉｊ２は、「ｗｉｊ２＝Ｘｉｊ／Σｋ＝１Ｎ２（Ｘｋｊ）」となる。
【００２５】
しかし、網トポロジ候補数は非常に多数となるため、分母が大きくなり、候補間のＸｉｊの値の差異が、評価尺度間のスコア差と比べて遥かに小さな値となる。その結果、単に重要視した評価尺度が良好な候補を選択する傾向が強くなり、他の評価尺度の値がほとんど考慮されなくなる。
【００２６】
この問題を解決するために本願発明者は、以前、評価尺度の値Ｘｉｊそのものを用いるのではなく、Ｘｉｊを線形変換した値Yｉｊを正規化したものを重みとすることを提案した。すなわち、ａとｂを任意の実数とし、Yｉｊ＝ａ（Ｘｉｊ＋ｂ）とする。この場合、重みｗｉｊ２は、次の数２の式のようになる。
【００２７】
【数２】
2010206581.tif 000004
【００２８】
正規化するため、重みｗｉｊ２は、実数ａとは無関係となる。また、ここでは全ての重みが０（ゼロ）以上の値をとるよう、評価尺度の値Ｘｉｊの全候補中の最小値を「−１」倍した値をｂに設定する（ｂ＝−ｍｉｎｉ｛Ｘｉｊ｝）。
【００２９】
このように線形変換を施すことにより、候補間で重みの格差を拡大することができ、特に、評価値の大きな（Ｘｉｊの小さな）候補に対する重みを大きく低減することが可能であり、評価値の非常に悪い評価尺度を含むトポロジを、誤って高く評価する問題を避けることができる。
【００３０】
しかし、ＡＨＰを用いた網トポロジ（ネットワークトポロジ）評価を行うに際しては、事前に評価対象となる「候補トポロジの集合」を生成する必要がある。以下、このような「候補トポロジの集合」の生成に関して説明する。
【００３１】
ネットワーク（ＮＷ）の一般化した構成要素としてノードとリンクを考える。ノードの位置とノード間の交流トラヒック行列は与えられており、全てのノード間にリンクの設置が可能とする。
【００３２】
すなわち、ノード数をＮとすると、リンクの設置可能な箇所数Ｌは、「Ｌ＝Ｎ（Ｎ−１）／２」となる。ただし、設置リンクは双方向であるとし、両端のノード間の両方向にトラヒックが流れることを想定する。
【００３３】
これらＬ本のリンク設置可能位置に対して、リンクを設置する箇所を選択することで候補トポロジが生成されるため、構成可能な候補トポロジの全数は２Ｌとなる。
【００３４】
一般に、ある条件を満たす候補を、重複なく、全て出力する問題は、「列挙問題」と呼ばれ、列挙アルゴリズムの一つとして、以下に説明する「分割法」が従来から知られている。
【００３５】
分割法は、問題の解集合を分割し、それぞれを子問題として再帰的に解く列挙手法であり、分割を繰り返した結果、子問題に含まれる解の数が唯一つになった段階でその解を出力する。
【００３６】
そのため、分割法を適用するためには、問題が再帰的に解けることが必要である。上述の候補トポロジに関しては、Ｌ本のリンク設置可能位置の各々に対し、１からＬの番号を任意に割り当て、各々のリンク設置可能位置を「ｌ１，ｌ２，…，ｌＬ」と表記する。
【００３７】
リンク設置可能位置ｌｅにリンクを設置する場合に「１」を、しない場合に「０」をとる２値変数をｘｅと定義すると、ｘｅを要素に持つＬ次元ベクトルＸを用いて任意のトポロジを表すことができる。
【００３８】
リンク設置可能位置ｌｅの各々に対して、部分的にリンクの設置の有無を決めたとき、残るリンク設置可能位置ｌｅに対するリンクの設置の有無の組み合わせを解集合に持つ子問題に再帰的に分割していくことが可能であり、「分割法の網トポロジ列挙への適用」が可能である。
【００３９】
分割法では、分割で生成された子問題が、条件を満たす解を持たないことが判断できる場合に、その子問題の分割を中断して引き返すことで計算時間を短縮する。
【００４０】
そのため、計算時間を短縮するためには、複数の候補を含む子問題に対して、条件を満たす解が存在しないことが判断できる必要がある。このことは、複数の解を含む子問題において、候補トポロジ集合の各々が条件Ｃを満たすか否かの判定をすることなく、全候補が条件Ｃを満たさないことの判定を行う必要がある。
【００４１】
しかし、条件Ｃを満たす解集合は単調性を持たないため、条件Ｃのみでは計算時間の短縮が図れない。
【００４２】
そこで、本願発明者は、特願２００８−１７０３５９号において、総リンク長に制約上限値Ｄを新たに設ける技術を提案している。この技術では、既にリンクの設置の有無が確定している範囲で、総リンク長が制約上限値Ｄを超えている場合、この子問題に含まれる全ての候補トポロジは必ず総リンク長の制約上限を超過するため、以後の分割処理を行う必要がなく、計算時間の短縮が期待できる。
【００４３】
しかし、この技術によっても、大規模なネットワークに対しては、網トポロジ候補の生成を、現実的な時間内で行うことができない場合がある。
【００４４】
以下、このようなケースについて、ＣＡＩＤＡのＷｅｂページで公開されている３６の商用ＩＳＰバックボーンＮＷのノード配置を用いて説明する。
【００４５】
図３に、これら３６のＮＷのノード数Ｎ、リンク数Ｍ、平均ノード次数Ａｒ、最大ノード次数Ｍａｘをまとめる。
【００４６】
各々のリンク設置可能位置ｅのリンク距離ｄｅをノード間の直線距離に設定する。また、ノード間の交流トラヒック比率ｒｉｊ（ノードｉを発、ノードｊを着とするトラヒック量のＮＷ全体のトラヒック量に対する比率）を、両端のノードの人口比の積に設定する。
【００４７】
すなわち、ノードｋの人口をＵｋ、人口の総和をＵ、ノードｋの人口比率をｒｋ（＝Ｕｋ／Ｕ）とすると、「ｒｉｊ＝ｒｉｒｊ」となる。
【００４８】
パケットの転送経路としてＯＳＰＦ（Ｏｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ）による最短ホップ経路が設定されることを想定し、各候補トポロジを評価するための１番目の評価尺度Ｖ１として総リンク長を考え（Ｖ１＝Σｅ∈Ｅ（ｄｅ））、２番目の評価尺度Ｖ２としてトラヒック量比率で重み付けた平均ホップ長（ホップ数）εを考える（Ｖ２＝ε＝Σｉ，ｊ∈Ｖ（ｒｉｊｈｉｊ））。ただし，ＶとＥは各々、ノードとリンクの集合であり、ｈｉｊはノードｉとノードｊの間の最短ホップ長（ホップ数）である。
【００４９】
また、ＮＷ上のあるリンクｅのＳＬＦ（Ｓｉｎｇｌｅ  Ｌｉｎｋ  Ｆａｉｌｕｒｅ、単一リンク故障：同時に故障するリンクは一つだけと仮定）時に接続性が喪失するノードペアの集合をＰｅとするとき、ＳＬＦ時に接続性が喪失するトラヒック量比率の平均値ξを次の数３の式で定義し、このＳＬＦ時に接続性が喪失するトラヒック量比率の平均値ξを、３番目の評価尺度として用いる。
【００５０】
【数３】
2010206581.tif 000005
【００５１】
図４（ａ）に、図３に示した３６の各ＮＷにおける、ＳＬＦ時に接続性が喪失するトラヒック量比率の平均値ξを、ノード数Ｎに対してプロットした結果を示す。３６のＮＷの中でＳＬＦ時に完全に接続性が維持される（ξ＝０）ＮＷは７つのみであり、大部分のＮＷにおいては２％程度未満ではあるものの、僅かな比率のトラヒックに対する接続性が平均的には喪失することが確認できる。
【００５２】
しかも、７つのＮＷのうち４つは、ノード数Ｎが１０未満の小規模ＮＷであり、多くの、特に、中規模以上のＮＷにおいては、ＳＬＦ時に完全な接続性を保てるＮＷは稀である。
【００５３】
これは、現実的なコストでＮＷを構築するためには、ただ１つのノードにのみ接続する次数が１のノードが、ある程度、存在せざるを得ないことが理由であると思われる。
【００５４】
分割法を用いた候補トポロジ列挙法では、総リンク長Ｖ１に制約上限Ｄを設けることで、所要計算時間を短縮するが、Ｄの値をどの程度に設定するかが問題となる。例えば、制約上限Ｄを小さく設定するほど所要計算時間が短くなるが、生成される候補トポロジが、より制約上限Ｄが小さな少数のものに限定される。
【００５５】
ＡＨＰを用いて適切なトポロジを選出する際、評価対象とする候補トポロジの各評価尺度の値のレンジが広いほど、より柔軟な評価を行うことができ、制約上限Ｄが大きな方が望ましい。
【００５６】
そこで、実際のＮＷで総リンク長がどの程度の値になっているかを確認するため、図４（ｂ）において、図３における３６の各ＮＷの総リンク長を、Ｌ個の全リンク設置可能位置にリンクを設置した場合（フルメッシュ）の総リンク長Ｄｍａｘで除した値を、各々、ノード数Ｎに対してプロットした結果を示す。
【００５７】
ノード数Ｎが小さい場合、フルメッシュ状に全設置可能位置にリンクを設置することも可能であり、実際、小規模ＮＷのいくつかはフルメッシュに近い形状となっている。
【００５８】
しかし、ノード数Ｎの増加に伴いリンク設置可能位置が爆発的に増加するため、ノード数Ｎの増加に伴い、現実のＮＷにおける総リンク長は、フルメッシュの場合の総リンク長と比較して遥かに小さくなる。
【００５９】
そこで、実際のＮＷにおける総リンク長の規模のトポロジが候補に含まれるように、総リンク長比率の上限Ｄ／Ｄｍａｘの値を、Ｎ＜１０のＮＷに対しては「１」、１０≦Ｎ＜３０のＮＷに対しては「０．２」、３０≦Ｎ＜４０のＮＷに対しては「０．０７」、４０≦Ｎ＜６０のＮＷに対しては「０．０３」、６０≦ＮのＮＷに対しては「０．０２」に、おおまかに設定する。図４（ｂ）において、設定したＤ／Ｄｍａｘの値を合わせて示す。
【００６０】
Ｌ（＝Ｎ（Ｎ−１）／２）のリンク設置可能位置から距離の短い順にｘ本を選び出したときの、これらｘ本のリンク長の総和をＧ（ｘ）とし、Ｇ（ｘ）≦Ｄを満たすｘの最大値をｘ’とする。
【００６１】
これらｘ’本のリンク設置可能位置の全てにリンクを設置した場合も、制約条件Ｖ１≦Ｄを満足することから、ｘ’本の各々について、リンクを設置する場合としない場合の組み合わせから生成される２ｘ’個のトポロジは、全て、総リンク長の制約上限を満足する。
【００６２】
実際には、これらｘ’本以外のリンク設置可能位置にリンクを設置したトポロジの中には、Ｖ１≦Ｄを満足するものが多数存在するため、列挙すべき候補トポロジ数は２ｘ’個より遥かに大きくなるが、大規模ＮＷに対して、分割法を用いて候補トポロジを生成する場合の所要計算時間の次元を把握するため、ここでは、最低限、列挙する必要のある２ｘ’個のトポロジの生成に要する時間を評価する。
【００６３】
図５（ａ）に、図３に示す３６のＮＷにおける、「リンク長の総和Ｇ（ｘ）≦制約上限Ｄ」を満たすリンク設置可能位置ｘの最大値ｘ’の値を、ノード数Ｎに対してプロットした結果を示す。ノード数Ｎの増加に伴い、リンク設置可能位置の、フルメッシュ総リンク長Ｄｍａｘに対して距離の短いリンク設置可能位置の数が増加する。
【００６４】
そのため、ノード数Ｎが大きなほど、総リンク長Ｖの制約上限ＤのＤｍａｘに対する比率を抑えているものの、ノード数Ｎの増加に伴い、リンク長の総和Ｇ（ｘ）≦制約上限Ｄを満たす、リンク設置可能位置ｘの最大値ｘ’の値は急増する。
【００６５】
所要計算時間は、考慮する制約条件や評価尺度に依存するため、ここでは、分割法に固有の処理であり、必ず必要となる、再帰演算により２ｘ’個のトポロジに対するリンク設置状態ベクトルＸを生成するのに要する時間のみを評価する。
【００６６】
実際には、制約条件の判定や評価尺度の算出に要する時間が加わることから、ここで評価する計算時間よりも、実際の所要計算時間は遥かに大きい。
【００６７】
３ＧＨzのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｃｅｓｓｉｎｇ  Ｕｎｉｔ）を２つと、８ＧBのメモリを実装したＰＣ（パーソナルコンピュータ）で、リンク長の総和Ｇ（ｘ）≦制約上限Ｄを満たす、リンク設置可能位置ｘの最大値ｘ’＝２８の場合について計算したところ約４１秒を要した。
【００６８】
図５（ｂ）に、理論的な所要計算時間の下限である「４１×２ｘ’−２８」の値を、ノード数Ｎに対してプロットした結果を示す。ただし、ノード数Ｎ≧７４の４つのＮＷについては、所要計算時間の下限が１０１００を超えたため省いている。
【００６９】
ノード数Ｎが１０程度以上のＮＷでは、総リンク長に現実的な値の制約上限を設け分割法を用いた場合も、３時間（１０４秒）程度の現実的な時間では、候補トポロジの集合を生成できないことが確認される。
【００７０】
以上、説明したように、ＡＨＰは、複数の候補が与えられたときに、複数の評価尺度を同時に考慮して、各候補を総合的に評価する技術であるが、評価対象となる候補の生成技術については何ら規定していない。
【００７１】
また、分割法は、ある条件を満たす解の候補を、再帰的な処理で全て重複することなく出力する技術であるが、条件を満たす解の候補を全て出力するため、それら条件を満たす候補の数が膨大な場合には、やはり分割法を用いても現実的な時間で候補を生成することができない。
【先行技術文献】
【特許文献】
【００７２】
【特許文献１】特開２００６−３５３９２６号公報
【発明の概要】
【発明が解決しようとする課題】
【００７３】
解決しようとする問題点は、従来の技術では、例えば、（１）ＡＨＰでの評価対象となる候補の生成技術については何ら開示されていない点と、（２）分割法では、条件を満たす候補の数が膨大な場合には、現実的な時間で候補トポロジを生成することができない点である。
【００７４】
本発明の目的は、これら従来技術の課題を解決し、大規模ＮＷに対しても現実的な時間で候補トポロジを生成可能とし、生成した候補トポロジを用いて網トポロジ設計を行うシステムの性能の向上を図ることである。
【課題を解決するための手段】
【００７５】
上記目的を達成するため、本発明では、条件を満たす解の候補を全て列挙するのではなく、望ましい性質を持つと思われる解の候補のみを効率的に生成する。具体的には、全リンク長と、トラヒック比率で重みづけた平均ホップ長（ホップ数）、および、単一リンク障害時（ＳＬＦ）に接続性が喪失するトラヒック量比率の平均値、の３つを評価尺度として、まず、ネットワークに求められる最低限度の要件である全ノード間の接続性を満たすトポロジを生成し、生成したこのトポロジに対して、単一リンク障害（ＳＬＦ）時に接続性が維持されるレベルを現状のネットワークと同等程度の水準となるよう最小限のリンクを付加したトポロジを基本トポロジとして生成し、さらに、この基本トポロジに対して、総リンク長のバリエーションが最大になるよう、多様なトポロジ候補が生成されるよう、最少数のリンク設置可能位置を選出する。
【発明の効果】
【００７６】
本発明によれば、大規模ネットワークに対し、現実的な時間で、候補トポロジの集合を生成することができ、生成した候補トポロジを用いて当該大規模ネットワークにおけるトポロジ設計を行うシステムの性能を向上させることができる。
【図面の簡単な説明】
【００７７】
【図１】ＡＨＰの階層構造例を示す説明図である。
【図２】ＡＨＰで適用する一致比較値の例を示す説明図である。
【図３】本発明の評価に用いた各ネットワークの基本特性の具体例を示す説明図である。
【図４】ノード数に対応するＳＬＦ時の接続性喪失トラヒック量比率の平均値と総リンク長比率の具体例を示す説明図である。
【図５】ノード数に対応するリンク設置可能数の下限と理論上の所要計算時間の下限の具体例を示す説明図である。
【図６】本発明に係るシステムの構成例を示すブロック図である。
【図７】ノード数に対応するトポロジＴｂの構成リンク数とトポロジＴｂを得るのに要した計算時間の具体例を示す説明図である。
【図８】本例のシステムの第１の評価結果例を示す説明図である。
【図９】本例のシステムの第２の評価結果例を示す説明図である。
【図１０】本発明に係るシステムの処理例を示すフローチャートである。
【発明を実施するための形態】
【００７８】
以下、図を用いて本発明を実施するための形態例を説明する。図６においては、本発明に係るトポロジを生成するシステムの構成例を示しており、本システムは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ等を具備したコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣＰＵで処理することにより、各処理部の機能を実行する。
【００７９】
本例のシステムでは、プログラムされたコンピュータ処理を実行する各処理部として、候補トポロジ集合生成部１００と入力部１０１（図中「ノード情報，トラヒック比率情報，リンク設置個所候補数，入力部」と記載）および出力部１０６（図中「候補トポロジ出力部」と記載）を具備している。
【００８０】
入力部１０１は、図示していないキーボードやマウス等の入力装置を用いた操作者の入力操作により、例えば、外部記憶媒体、あるいは、ネットワークを介したオンラインで入力される、処理対象のネットワークにおける全ノードの位置情報や各ノード間のトラヒック量比率、単一リンク障害（ＳＬＦ）時の平均接続制御喪失トラヒック量比率の要求水準ξ’、リンク設置個所候補数ｘ等の条件情報を入力して、図示していない記憶装置に格納する。
【００８１】
候補トポロジ集合生成部１００は、記憶装置から条件情報を読み出し、この条件情報を用いて、本発明に係る処理、すなわち、正常時の全ノード間の接続性確保を条件とした、現実的な時間内での候補トポロジ集合の生成を行う。
【００８２】
出力部１０６は、候補トポロジ集合生成部１００が生成した候補トポロジ集合を、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｌａｙ  Ｔｕｂｅ）やＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）等の表示装置に表示する、もしくは、プリンタで印字する、あるいは、記憶媒体に記録する、オンライン上の他のコンピュータ装置等に送信する等の出力処理を行う。
【００８３】
また、候補トポロジ集合生成部１００は、プログラムされたコンピュータ処理を実行する機能として、最小木生成部１０２と常設リンク付加部１０３、リンク設置候補位置選択部１０４、候補トポロジ生成部１０５を有する。
【００８４】
このような構成により、本例のシステムでは、全ノードの位置が与えられ、任意のノード間にリンクを設置することが可能である場合に、正常時の全ノード間の接続性確保を条件に、現実的な時間内で候補トポロジ集合を生成する。
【００８５】
本例では、全リンク長Ｖ１とトラヒック比率で重みづけた平均ホップ長（ホップ数）Ｖ２および単一リンク障害時に接続性が喪失するトラヒック量比率の平均値ξ’、の３つを評価尺度とし、候補トポロジを生成する。
【００８６】
この際、与えられたリンクコストに対して、正常時の全ノード間の接続性を有し、全リンクコストの総和を最小とするトポロジである最小木を構成するリンク設置可能位置には、常にリンクを設置する。尚、リンクコストとしてリンク距離をノード間のトラヒック量比率で除した値を用いる。
【００８７】
また、生成された最小木に対して、最小木に含まれない各々のリンク設置可能位置に対して、一本だけリンクを設置したトポロジの、単一リンク障害時の平均接続性喪失トラヒック量比率を算出し、この値が最小となるリンク設置可能位置にリンクを設置する処理を、単一リンク障害時の平均接続性喪失トラヒック量比率が任意に与えた値以下となるまで反復し、これら最小木に追加された全てのリンク設置可能位置にも、常にリンクを設置する。
【００８８】
さらに、生成したトポロジに含まれない任意のリンク設置可能位置の各々に対して、一本だけリンクを設置したトポロジのトラヒック量で重みづけた平均ホップ長（ホップ数）を算出し、この値が最小となるリンク設置可能位置をリンク設置候補位置として選択する処理を、任意に与えた本数ｘだけ反復する。また、この選択したｘ本のリンク設置可能位置の各々に対して、リンクを設置する場合としない場合を考え、組み合わせてとして構成可能な２ｘ個のトポロジを候補として生成する。
【００８９】
以下、このような処理動作について、より詳細に説明する。図６において、本例では、入力部１０１により、全てのノードの位置とノード間のトラヒック量比率、ＳＬＦ時の平均接続性喪失トラヒック量比率の要求水準ξ’、リンク設置個所候補数ｘを入力する。
【００９０】
例えば、ノード位置として、各ノードが存在する地理的な座標が例えば（１２３，４５）といった座標データが、また、ノード間のトラヒック量比率として、例えばノード３，４間のトラヒック量比率０．００３が、また、ＳＬＦ時の平均接続性喪失トラヒック量比率の要求水準ξ’として例えば「ξ’＝０．０５」が、そして、リンク設置個所候補数ｘとして例えば「ｘ＝５」が入力パラメタとして入力される。
【００９１】
最小木生成部１０２は、各入力パラメタを用いて当該ネットワークに対する最小木を生成し、この生成した生成木に対して、常設リンク付加部１０３が、ＳＬＦ時の接続性喪失トラヒック量比率の平均が制約限界を満たすよう、付加すべき常設リンクを選択する。
【００９２】
リンク設置候補位置選択部１０４は、重みづけ平均ホップ長（ホップ数）の低減効果が高い位置に、リンク設置候補位置を選択し、候補トポロジ生成部１０５は、構成可能な候補トポロジの集合を生成する。生成した候補トポロジ集合を、出力部１０６が出力する。
【００９３】
候補トポロジのデータ形式としては、各リンク設置可能位置に対してリンクを設置する場合に「１」、しない場合に「０」をとる２値変数として、ｘ本の全てのリンク設置可能位置に対して生成されるリンク設置情報ベクトル（例：（０，０，１，０，１，１，０，１，０））、各評価尺度の値（例：１００．５６，１．４３，０．００３）が考えられるが、これらトポロジデータを各候補に対して出力することになる。
【００９４】
本例の最小木生成部１０２は、Ｐｒｉｍのアルゴリズム（プリム法：最小全域木問題）を用いて最小木を生成する。本アルゴリズムは、最初にランダムに１つノードを選択し、選択したノードとリンクコストが最小のノード間にリンクを設置する。そして得られた部分木に属する任意のノードと、部分木以外の任意のノード間でリンクコストが最小となる位置にリンクを１本ずつ追加する処理を、全てのノードが木に含まれるまで反復する。
【００９５】
常設リンク付加部１０３は、最小木生成部１０２が選択した各リンク設置可能位置に対して、１本だけリンクを追加したトポロジを対象に、ＳＬＦ時の平均接続性喪失トラヒック量比率ξを算出し、算出した比率ξが最小となるリンク設置可能位置に１本だけリンクを追加する。そして、この処理を、ξ≦ξ’が満たされるまで反復する。
【００９６】
リンク設置候補位置選択部１０４は、初期状態では、ｘ本のリンク設置可能位置の集合Ｅｃを空集合とし、最小木生成部１０２が選択し、常設リンク付加部１０３が追加したリンク設置可能位置の各々に対して１本だけリンクを追加したときの、トラヒック量比率で重み付けた平均ホップ長（ホップ数）εを計算し、この重み付けた平均ホップ長εが最小となるリンク設置可能位置ｅ１を、リンク設置可能位置の集合Ｅｃに追加する。
【００９７】
また、リンク設置候補位置選択部１０４は、リンク設置可能位置ｅ１を追加したトポロジに対して、さらに、残るリンク設置可能位置の各々に対して１本だけリンクを追加した場合の、トラヒック量比率で重み付けた平均ホップ長εを計算し、やはり、このεが最小となるリンク設置可能位置ｅ２を、集合Ｅｃに追加する。
【００９８】
同様の処理を、任意に与えたｘ回だけ反復する。この結果、「ｘ」本のリンク設置可能位置を追加するという条件で、重み付け平均ホップ長（Ｖ２）の最小値を最小化する候補トポロジ集合を生成し、リンク設置可能位置集合Ｅｃを得ることができる。
【００９９】
候補トポロジ生成部１０５は、得られたリンク設置可能位置集合Ｅｃの各々に対してリンクを設置する場合と、しない場合の全ての組合せを対象に、候補トポロジデータを生成する。
【０１００】
以下、図１０を用いて、図６における候補トポロジ集合生成部１００による、このような本発明に係る網トポロジ候補の列挙手順について、詳細を説明する。尚、最小木生成部１０２と常設リンク付加部１０３による［リンク常設箇所の選定］、リンク設置候補位置選択部１０４と候補トポロジ生成部１０５による［リンク設置候補箇所の選定］の順で説明する。
【０１０１】
［リンク常設箇所の選定］
各リンクのコストが与えられたときに、全ノード間の接続性を満たしつつ、リンクコストの総和が最小となるトポロジは、最小木（ＭＳＴ：Ｍｉｎｉｍｕｍ  Ｓｐａｎｎｉｎｇ  Ｔｒｅｅ）として知られ、貪欲法に基づく最小木の生成法としてＫｒｕｓｋａｌやＰｒｉｍのアルゴリズムが知られている。
【０１０２】
本例の候補トポロジ集合生成部１００においては、Ｐｒｉｍのアルゴリズムを用いて最小木を生成する（ステップＳ１０１）。
【０１０３】
本アルゴリズムは、最初にランダムに１つのノードを選択し、選択したノードと、リンクコストが最小のノードとの間にリンクを設置する。そして、得られた部分木に属する任意のノードと、部分木以外の任意のノード間で、リンクコストが最小となる位置にリンクを１本ずつ追加する処理を、全てのノードが木に含まれるまで反復する。
【０１０４】
本アルゴリズムを用いることで、Ｏ（Ｎ３）の多項式時間で、Ｎ−１本のリンクから構成されるトポロジＴａを得ることができる。ここでは、リンクコストに、ｓｉｊの逆数である「ｄｉｊ／ｒｉｊ」を用いる。
【０１０５】
このようにして得たトポロジＴａは、正常時の全ノード間の接続性を満たすが、ＳＬＦ時の接続性については考慮されていない。そこで、ＳＬＦ時の平均接続性喪失トラヒック量比率ξが、３６個の実際のＮＷにおける各々の比率ξの値ξ’以下となるよう、トポロジＴａに最少数のリンクを追加することを考える。
【０１０６】
まず、Ｔｂ＝Ｔａに設定し（ステップＳ１０２）、このトポロジＴｂに含まれない各リンク設置可能位置に対して１本だけリンクを追加したトポロジにおける平均接続性喪失トラヒック量比率ξを各々算出し、算出したξが最小と案留リンク設置可能位置をトポロジＴｂに追加する処理（ステップＳ１０３）を、算出したξが予め定められた評価基準の１つである要求水準ξ’を越えるまで繰り返す（ステップＳ１０４）。
【０１０７】
すなわち、トポロジＴａに含まれる「ｘａ＝Ｎ−１」本を除いた「全リンク設置可能箇所数Ｌ−ｘａ」本の各リンク設置可能位置に対して、１本だけリンクを追加したトポロジを対象に、平均接続性喪失トラヒック量比率ξを算出し、このξが最小となるリンク設置可能位置に１本だけリンクを追加する。このような処理を、「ξ≦ξ’」が満たされるまで反復し、得られたトポロジをＴｂとする。
【０１０８】
このようにして、３６個の各ＮＷにおいて得られたトポロジＴｂの構成リンク数ｘｂを、ノード数Ｎに対してプロットした結果を、図７（ａ）に示す。図７（ａ）において示すように、最小木の構成に要するｘａの値を実線で示しているが、ＳＬＦ時の平均接続性喪失トラヒック量比率ξの条件を満たすために追加する必要のあるリンク数は、ｘａの３０％程度未満であり、少数のリンクを追加するだけで当該ξを十分に低減できることが確認される。
【０１０９】
また、図７（ｂ）に、各ＮＷにおいてトポロジＴａとトポロジＴｂを各々得るのに要した合計時間ｔｂを、ノード数Ｎに対してプロットした結果を示す。ただし、ノード数Ｎが５もしくは６の３つのＮＷにおいては、所要計算時間が非常に短く計測できなかったため省略している。
【０１１０】
トポロジＴａからトポロジＴｂを構成するのに要する計算量はＯ（ｘａｘｂＮ４）であるため、ノードＮの増加に伴いトポロジＴａからトポロジＴｂを構成するのに要する計算量ｔｂは急増する。それでも、ノードＮが１００程度以下であれば、数１０分程度の現実的な時間で、トポロジＴｂを構成することが可能である。
【０１１１】
［リンク設置候補箇所の選定］
生成する全候補トポロジにおいて、トポロジＴｂを構成するｘｂ本のリンク設置位置には、必ずリンクを設置する。すなわち、生成する候補トポロジを、これらｘｂ本の位置にリンクを設置したものに限定する。
【０１１２】
トポロジＴｂを構成する際には、リンクコスト「ｄｉｊ／ｒｉｊ＝１／ｓｉｊ」の値が小さな、可能な限り少数の箇所にのみリンクを設置しているため、上述した３つの評価尺度のうちの総リンク長Ｖ１が良好なトポロジが生成されることになる。
【０１１３】
また、生成されるトポロジは、平均接続性喪失トラヒック量比率ξが、現実のＮＷの値以下となるものに限定されるため、上述した３つの評価尺度のうちのＳＬＦ時の平均接続性喪失トラヒック量比率Ｖ３についても良好なトポロジが生成される。
【０１１４】
ただし、残る評価尺度である重みづけ平均ホップ長Ｖ２については考慮していない。以下、このような重みづけ平均ホップ長Ｖ２については考慮した候補トポロジの選定手順を説明する。
【０１１５】
一般的に、設置するリンクの数が増加するほど、ノード間の経路の多様性が増加し、重みづけ平均ホップ長Ｖ２が減少する。そのため、設置リンク数を抑えたトポロジＴｂは、構成可能なトポロジの中でも比較的に重みづけ平均ホップ長Ｖ２が大きいトポロジであると言える。そこで、トポロジＴｂから更にリンクを追加設置することで、重みづけ平均ホップ長Ｖ２に多様性をもつ、候補トポロジ集合を生成することを考える。
【０１１６】
ここでは、トポロジＴｂに対してリンクの追加を許容するリンク設置位置の数をｘとし、これらｘ本のリンク設置可能位置の集合をＥｃとする。
【０１１７】
このリンク設置可能位置の集合Ｅｃの任意の位置にリンクを設置する全ての組合せによって候補トポロジを生成するため、トポロジＴｂを構成するリンク位置には、必ず、リンクを有する２ｘ個の候補トポロジ集合Ｔｄが生成される。
【０１１８】
追加を許容するリンク本数ｘを増加させるほど、候補トポロジの多様性が増し、より柔軟なトポロジ設計が可能となるが、候補トポロジ生成に要する時間は爆発的に増大する。
【０１１９】
トポロジＴｂに対して多数のリンクを追加するほど、重みづけ平均ホップ長Ｖ２は単調に減少するため、生成される候補トポロジにおける重みづけ平均ホップ長Ｖ２の最大値は、トポロジＴｂそのものの重み付け平均ホップ長εとなり、リンク設置可能位置の集合Ｅｃとは無関係となる。
【０１２０】
一方で、平均ホップ長Ｖ２の最小値は、リンク設置可能位置の集合Ｅｃに依存し、平均ホップ長Ｖ２の最小値が小さいほど、平均ホップ長Ｖ２の多様性が高い、優れた候補トポロジ集合であると言える。
【０１２１】
そのため、可能な限り少数のリンク追加で、生成される候補トポロジ集合における平均ホップ長Ｖ２の最小値が小さくなるよう、リンク設置可能位置の集合Ｅｃを選択することが望ましい。
【０１２２】
ここでは、以下に示す貪欲法による生成法を考える。
【０１２３】
まず、初期状態では、リンク設置可能位置の集合Ｅｃを空集合とする（ステップＳ１０５）。そして、トポロジＴｂを構成するｘｂ本のリンクを除いた「全リンク設置可能箇所数Ｌ−ｘｂ」のリンク設置可能位置の各々に対して、１本だけリンクを追加したときの、重み付けた平均ホップ長εを計算し、εが最小となるリンク設置可能位置ｅ１を、リンク設置可能位置の集合Ｅｃに追加し、さらに、トポロジＴｂにリンク設置可能位置ｅ１を追加したトポロジに対して、残る「Ｌ−ｘｂ−１」のリンク設置可能位置の各々に対して１本だけリンクを追加したときの、重み付けた平均ホップ長εを計算し、やはり、この重み付けた平均ホップ長εが最小となるリンク設置可能位置ｅ２を、リンク設置可能位置の集合Ｅｃに追加する処理（ステップＳ１０６）を、任意に与えたｘ回だけ反復する（ステップＳ１０７）。
【０１２４】
この結果、ｘ本のリンク設置可能位置を追加するという条件で、平均ホップ長Ｖ２の最小値を最小化する候補トポロジ集合を生成するリンク設置可能位置集合Ｅｃを得ることができる。
【０１２５】
以下、このような本例のシステムの「評価結果」について、図８を用いて説明する。
【０１２６】
平均ホップ長Ｖ２が最小となるトポロジは、Ｌ本の全リンク設置可能位置にリンクを設置したフルメッシュの場合で、発着ノードが同一のノードであるトラヒックの経由ホップ長が「０」（ゼロ）で、発着ノードが異なる全てのトラックの経由ホップ長が「１」となることに注意すると、重み付けた平均ホップ長εの最小値εｍｉｎは、「εｍｉｎ＝１−Σｎ＝１Ｎ（ｒｉｉ）」となる。
【０１２７】
図８に、生成されたトポロジ集合における、平均ホップ長Ｖ２の最小値を、達成可能な最小値であるεｍｉｎで除して正規化した値を、３６のＮＷごとに、リンク設置可能位置ｘの設定値（本数）に対してプロットした結果を示す。
【０１２８】
図８（ａ）には、ノード数Ｎが２７未満の１８のＮＷの結果を、また、図８（ｂ）には、ノード数Ｎが２７以上の１８のＮＷの結果を各々示している。ただし、ノード数Ｎが７４以上の４つのＮＷにおいては、リンク設置可能位置集合Ｅｃの生成に要する時間が１時間を超えた時点で評価を打ち切ったため、リンク設置可能位置ｘの小さい領域における結果のみを示している。
【０１２９】
図８（ａ），（ｂ）に示すように、横軸が対数、縦軸が線形のグラフにおいて、リンク設置可能位置ｘの増加に伴い、ほぼ直線状に、平均ホップ長Ｖ２は減少する。そのため、リンク設置可能位置ｘの小さい領域では、ｘの増加に伴い急激に平均ホップ長Ｖ２の最小値が減少するが、リンク設置可能位置ｘの大きな領域では、平均ホップ長Ｖ２の最小値は緩やかに減少して、最小値εｍｉｎに達することが確認できる。
【０１３０】
そのため、リンク設置可能位置ｘを小さい値に設定しても、比較的、平均ホップ長Ｖ２が小さく多様な候補を有するトポロジ集合Ｔｄを得ることが期待できる。
【０１３１】
１つのトポロジに対して、重み付けた平均ホップ長εを算出するのに要する計算量はＯ（Ｎ３）であるため、リンク設置可能位置集合Ｅｃの生成に要する時間ｔｃは「Ｏ（ｘＬＮ３）＝Ｏ（ｘＮ５）」となる。
【０１３２】
また、得られたトポロジ集合Ｔｂとリンク設置可能位置集合Ｅｃを用いて、２ｘ個の候補トポロジ集合Ｔｄを生成する際には、各候補トポロジに対して３つの評価尺度の値を算出する必要がある。
【０１３３】
すなわち、総リンク長Ｖ１にはＯ（ｘ）の、平均ホップ長Ｖ２にはＯ（Ｎ３）の、ＳＬＦ時の平均接続性喪失トラヒック量比率Ｖ３にはＯ（（ｘ２＋ｘ）Ｎ２）の計算量が各々必要となる。ここで、下記の数４の式とみなすと、各候補トポロジに対しておおよそＯ（Ｎ３）程度の計算量が必要になる。
【０１３４】
【数４】
2010206581.tif 000006
【０１３５】
そのため、トポロジ集合Ｔｂとリンク設置可能位置集合Ｅｃから、２ｘ個の候補トポロジを生成するのに要する時間ｔｄは、Ｏ（２ｘＮ３）となる。このような、２ｘ個の候補トポロジを生成するのに要する時間ｔｄとノード数との関連を、図９において示す。
【０１３６】
図９（ａ）においては、追加リンク数ｘ＝２０としたときの、３６の各ＮＷにおけるリンク設置可能位置集合Ｅｃの生成に要した時間ｔｃを、ノード数Ｎに対してプロットした結果を示している。
【０１３７】
また、図９（ｂ）においては、追加リンク数ｘ＝２０としたときの、候補トポロジ集合Ｔｄの生成に要した時間ｔｄを、同様に、ノード数Ｎに対してプロットした結果を示す。ただし、ノード数Ｎが５もしくは６の３つのＮＷにおいては、やはり、所要計算時間が非常に短く計測できなかったため省略している。
【０１３８】
これらの結果と、図７（ｂ）で示した候補トポロジ集合の生成に要した時間ｔｂの結果を用いて、任意のリンク設置候補位置数ｘに対して、ＭＳＴ（最小木）の生成から候補トポロジの生成に至る総所要計算時間の概算値τを式「τ＝ｔｂ＋（ｘ／２０）×ｔｃ＋２ｘ−２０ｔｄ」で見積もる。
【０１３９】
総所要計算時間の概算値τは、リンク設置候補位置数ｘの増加に伴い増加するが、現実的な許容計算時間τｍａｘに対して、τ≦τｍａｘを満たすリンク設置候補位置数ｘの最大値をｘｍａｘとする。
【０１４０】
図９（ｃ）に、τｍａｘ＝３６００秒に設定したときの各ＮＷのリンク設置候補位置数の最大値ｘｍａｘを、ノード数Ｎに対してプロットして結果を示す。ただし、図３に示したノード本数Ｎ＝１２６のネットワーク「ＧＧ」は、候補トポロジ集合Ｔｂの生成に要した時間ｔｂのみで既に、現実的な許容計算時間τｍａｘを超過していたため評価対象外とした。
【０１４１】
図９（ｃ）に示すように、ノード数Ｎが１０程度未満の場合は、リンク設置候補位置数の最大値ｘｍａｘは、「ｘｍａｘ＝全リンク設置可能箇所数Ｌ−ｘｂ」となり、全てのリンク設置可能位置を候補とすることができるが、ノード数Ｎが１０程度以上のＮＷにおいては、リンク設置可能位置が限定され、その許容最大数は、ノード数Ｎの増加に伴い緩やかに減少する。  
【０１４２】
図９（ｄ）においては、「リンク設置候補位置数ｘ」＝「総所要計算時間の概算値τ≦現実的な許容計算時間τｍａｘを満たすリンク設置候補位置数の最大値ｘｍａｘ」としたときに生成された候補トポロジ集合における重みづけ平均ホップ長Ｖ２の最大値と最小値を、各々、重み付け平均ホップ長の最小値εｍｉｎで除して正規化した値を、ノード数Ｎに対してプロットした結果を示している。
【０１４３】
図９（ｃ）に示すように、ノード数Ｎの増加に伴い、現実的な時間で得ることのできる候補トポロジ集合の、重み付け平均ホップ長Ｖ２の最小値は緩やかに増加する。そして、ノード数Ｎが３０程度未満のＮＷでは、達成可能な下限値の４割増し程度以下、ノード数Ｎが３０から６０程度のＮＷでは、約５割増し程度、ノード数Ｎが６０から１００程度のＮＷでは、６割から８割増し程度となる。
【０１４４】
また、得られる候補トポロジ集合の、重み付け平均ホップ長Ｖ２の最小値と最大値の差であるレンジ幅は、ノード数Ｎが２０程度以上のＮＷにおいては、全候補を列挙した場合と比較して、おおよそ半分になることが確認できる。
【０１４５】
以上の評価をまとめると、本例での候補トポロジ生成技術を用いることで、ノード数Ｎが２０程度未満のＮＷ（ネットワーク）に対しては、全候補を列挙する場合と同等の時間での候補トポロジの生成となるが、ノード数Ｎが２０〜１００程度のＮＷに対しては、重み付け平均ホップ長Ｖ２のレンジ幅が、全列挙する場合の半分程度になるものの、現実的な時間で候補トポロジを生成可能である。ただし、ノード数Ｎが１００程度以上のＮＷに対しては、本方式を用いても、現実的な時間で候補トポロジを生成することが困難である。
【０１４６】
以上、図１〜図１０を用いて説明したように、本例の候補トポロジ生成技術では、条件を満たす解の候補を全て列挙するのではなく、望ましい性質を持つと思われる解の候補のみを効率的に生成する。
【０１４７】
すなわち、全リンク長と、トラヒック比率で重みづけた平均ホップ長、および、単一リンク障害時（ＳＬＦ）に接続性が喪失するトラヒック量比率の平均値、の３つを評価尺度として、まず、ネットワークに求められる最低限度の要件である全ノード間の接続性を満たすリンクコストが最小のトポロジを生成し、生成したこのトポロジに対して、単一リンク障害（ＳＬＦ）時に接続性が予め定められたレベル（水準）を維持するよう（例えば現状のネットワークと同等程度の水準となるよう）最小限のリンクを付加したトポロジ（基本トポロジ）を生成し、さらに、生成した基本トポロジに対して、総リンク長のバリエーションが最大になるよう、多様なトポロジ候補が生成されるよう、最少数のリンク設置可能位置を選出する、すなわち、ノード間の経路選択の多様性が増加するよう予め定められた数のリンクを付加したトポロジを生成し、このトポロジを候補トポロジとすて出力する。
【０１４８】
より詳細には、本例の候補トポロジを生成するシステムは、プログラムされたコンピュータ処理によって、ネットワークのトポロジを生成するものであって、プログラムされたコンピュータの処理を実行する処理部として、候補トポロジ集合生成部１００と入力部１０１および出力部１０３を具備し、入力部１０１においては、入力装置から入力される、ネットワークの全リンク長とトラヒック比率で重みづけした平均ホップ長および単一リンク障害時に接続性が喪失するトラヒック量比率の平均値を含む条件情報を入力して記憶装置に記憶し、候補トポロジ集合生成部１００は、記憶装置から条件情報を読み出し、予め定められた時間内で候補トポロジ集合を生成し、出力部１０３においては、候補トポロジ集合生成部１００が生成した候補トポロジ集合を出力装置を介して出力する。
【０１４９】
また、候補トポロジ集合生成部１００は最小木生成部１０２を具備し、また、入力部１０１が記憶装置に記憶する条件情報として、入力装置から入力されるリンクコストを含み、最小木生成部１０２においては、正常時の全ノード間の接続性確保を条件に、全リンクコストの総和を最小とするトポロジである最小木を生成し、生成した最小木を構成するノードをリンク設置可能位置として特定し、候補トポロジ集合生成部１００は、最小木生成部１０２が特定したリンク設置可能位置にリンクを設置した候補トポロジ集合を生成する。
【０１５０】
尚、リンクコストとしては、リンク距離を当該ノード間のトラヒック量比率で除した値を用いる。
【０１５１】
また、候補トポロジ集合生成部１００は、常設リンク付加部１０３を具備し、常設リンク付加部１０３においては、最小木生成部１０２が生成した最小木においてリンク設置可能位置として含まれない各々のノードに対して、一本だけリンクを設置したトポロジの、単一リンク障害時の平均接続性喪失トラヒック量比率を算出し、算出した比率が最小となるノードをリンク設置可能位置として特定してリンクを設置する処理を、当該比率が予め定められた値以下となるまで反復し、候補トポロジ集合生成部１００は、常設リンク付加部１０３が特定した全てのリンク設置可能位置にもリンクを設置した候補トポロジ集合を生成する。
【０１５２】
さらに、候補トポロジ集合生成部１００は、リンク設置候補位置選択１０４を具備し、リンク設置候補位置選択１０４においては、常設リンク付加部１０３が特定したリンク設置可能位置として含まれない任意のノードの各々に対して、一本だけリンクを設置したトポロジのトラヒック量で重みづけた平均ホップ長を算出し、算出した平均ホップ長が最小となるリンク設置可能位置をリンク設置候補位置として選択する処理を、予め定められたリンク本数ｘだけ反復し、候補トポロジ集合生成部１００は、リンク設置候補位置選択部１０４が選択した全てのリンク設置可能位置にもリンクを設置した候補トポロジ集合を生成する。
【０１５３】
そして、候補トポロジ集合生成部１００は、候補トポロジ生成部１０５を具備し、候補トポロジ生成部１０５において、リンク設置候補位置選択部１０４が選択したｘ本のリンク設置可能位置の各々に対して、リンクを設置する場合としない場合の組み合わせてとして構成可能な２ｘ個のトポロジを候補として生成する。
【０１５４】
このように、本例では、全リンク長と、トラヒック比率で重みづけた平均ホップ長、および、単一リンク障害時（ＳＬＦ）に接続性が喪失するトラヒック量比率の平均値、の３つを評価尺度として用いることにより、大規模ネットワークに対して、現実的な時間で、候補トポロジの集合を生成することができる。
【０１５５】
尚、本発明は、図１〜図１０を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では、候補トポロジの集合を生成する技術に限定した説明を行っているが、この技術により生成した候補トポロジ集合を、例えばＡＨＰを用いた網トポロジ設計システムにおいて利用することにより、高性能な網トポロジ設計システムを構築することができる。
【符号の説明】
【０１５６】
１００：候補トポロジ集合生成部、１０１：入力部、１０２：最小木生成部、１０３：常設リンク付加部、１０４：リンク設置候補位置選択、１０５：候補トポロジ生成部、１０６：出力部。
【図１】
2010206581.tif 000007
【図２】
2010206581.tif 000008
【図３】
2010206581.tif 000009
【図４】
2010206581.tif 000010
【図５】
2010206581.tif 000011
【図６】
2010206581.tif 000012
【図７】
2010206581.tif 000013
【図８】
2010206581.tif 000014
【図９】
2010206581.tif 000015
【図１０】
2010206581.tif 000016