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