(57)【要約】【課題】単位の異なる複数の評価尺度を同時に考慮した上で、最適な網トポロジを得ることである。【解決手段】エッジノードの位置、コアノードの設置可能位置、およびリンクの設置可能位置が入力されるトポロジ情報・デマンド行列入力装置１０１と、初期トポロジを生成する初期トポロジ生成装置１０２と、初期トポロジに対していくつかのリンクとコアノードを追加した複数の候補トポロジを生成するトポロジ候補生成装置１０３と、候補トポロジ間の優劣を評価するＡＨＰ適用装置１０４と、得られた最適トポロジの集合を出力する最適トポロジ出力装置１０５とを具備する。【選択図】図１
2008165468.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ制御により、ＡＨＰを複数の評価尺度を考慮したトポロジ設計に適用するトポロジ設計方法であって、
トポロジ情報デマンド行列入力装置が、ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、該エッジノード集合および該コアノード集合を結ぶリンクの候補の集合とを与え、
初期トポロジおよびトポロジ候補生成装置が、ＡＨＰ適用装置により複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択し、
最適トポロジ出力装置が、選択された最適のトポロジを出力することを特徴とするＡＨＰを用いた網トポロジ設計方法。
【請求項２】
請求項１に記載の網トポロジ設計方法において、
前記ＡＨＰ適用装置による選択は、ＡＨＰの手法に従って、評価尺度間の一対比較を行うことで各評価尺度の重みを計算し、
さらに各候補トポロジの各評価尺度に対するスコア値として、該評価尺度の値から全候補中の最小値を引いたものを正規化したものを用い、
最終的に算出される各候補のスコア値で各候補の優劣を判断することを特徴とするＡＨＰを用いた網トポロジ設計方法。
【請求項３】
請求項１または２に記載の網トポロジ設計方法において、
前記ＡＨＰ適用装置による同時に考慮する評価尺度の例として、総ノード数、総リンク長、各パスの長さとトラヒック量の積を全パスについて足し合わせたもの、最大負荷リンクのトラヒック量、の四つを用いることを特徴とするＡＨＰを用いた網トポロジ設計方法。
【請求項４】
コンピュータ制御により、ＡＨＰを複数の評価尺度を考慮したトポロジ設計に適用するトポロジ設計装置であって、
エッジノードの位置、コアノードの設置可能位置、およびリンクの設置可能位置が入力されるトポロジ情報・デマンド行列入力装置と、
初期トポロジを生成する初期トポロジ生成装置と、
初期トポロジに対していくつかのリンクとコアノードを追加した複数の候補トポロジを生成するトポロジ候補生成装置と、
候補トポロジ間の優劣を評価するＡＨＰ適用装置と、
得られた最適トポロジの集合を出力する最適トポロジ出力装置と
を具備することを特徴とするＡＨＰを用いた網トポロジ設計システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、網トポロジ設計問題において、ＡＨＰ（Ａｎａｌｙｔｉｃ  Ｈｉｅｒａｃｈｙ  Ｐｒｏｃｅｓｓ：多段階意思決定法）で評価することにより、単位の異なる複数の評価尺度を同時に考慮して、最適な網トポロジを求めるＡＨＰを用いた網トポロジ設計方法および網トポロジ設計システムに関する。
【背景技術】
【０００２】
光ファイバやルータといったネットワークの物理的な資源を管理・運営している通信事業者や一部のＩＳＰ（Ｉｎｔｅｒｎｅｔ  Ｓｅｒｖｉｓｅ  Ｐｒｏｖｉｄｅｒ）にとっては、物理的な網トポロジをどのように構成するかという物理トポロジ設計は、重要な問題である。物理トポロジは、ノードやリンクの設備コスト、網の管理・保守コスト、障害に対する信頼性、などを決める要因となる。また、ＬＳＰ（Ｌａｂｅｌ  Ｓｗｉｔｃｈｅｄ  Ｐａｔｈ）や波長パス等の論理パスの設置ができず、パケットが転送される経路を明示的に設定できない場合には、物理トポロジがリンク負荷やパケットの経路に直接影響を与え、伝送遅延品質やスループットといったユーザ品質を定める要因となる。
【０００３】
一方、ＭＰＬＳ（Ｍｕｌｔｉ  Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ）網や波長パス網といった，物理網上に論理的なパスを設置し、対地間のパスの経路を明示的に設計できる場合には、論理トポロジ設計により物理トポロジのユーザ品質に対する影響をある程度、排除することができる。この場合、物理トポロジの設計に加えて、論理トポロジの設計を適切に行う必要がある。このように、網トポロジ設計問題は、物理トポロジ設計問題と論理トポロジ設計問題に大別できる。以下、各々の概略を説明する。
【０００４】
（物理トポロジ設計問題）
ネットワークの一般化した構成要素として、エッジノード，コアノード，リンクの３種類を考える。エッジノードは交換トラヒックの発着ノードであり、直接もしくは下位のネットワークを介してエンドホストを収容する。一方、コアノードは中継機能のみを有するノードであり、ユーザを収容しない。リンクは、エッジノードやコアノード間を繋ぐ役割を果たす。任意のエッジノード間の交流トラヒック行列は与えられるものとする。通信事業者は、既に地理的特性を考慮して配置された管路や局舎といった土木インフラを保有しており、これらを再設計することは現実的ではない。そのため、エッジノードの位置と、コアノードやリンクの設置可能な位置は与えられるものとする。
【０００５】
ネットワークに求められる要件の変化に合わせて、これら既存の管路や局舎を選別し、どこに光ファイバやルータといった設備を配置するかを検討することが、現実的な問題である。そこで、ここでは物理トポロジ設計を、「与えられたコアノードとリンクの設置候補位置に対して、実際に設置する候補位置を選択する行為」と定義する。ただし、全てのエッジノード設置位置には、エッジノードを設置する。
【０００６】
（論理トポロジ設計問題）
ＭＰＬＳルータやＯＸＣ（Ｏｐｔｉｃａｌ  Ｃｒｏｓｓ  Ｃｏｎｎｅｃｔ）を用いると、物理ネットワーク上に仮想的なパス（ＬＳＰや波長パス）を設置することが可能となり、各対地間のトラヒックが流れる経路を明示的に設計できる。物理トポロジは一旦構築されると変更することが困難であり、設計周期は１年から数年に及ぶが、論理トポロジは容易に変更することが可能であり、交流トラヒックの変化に応じて数年から数時間といった周期で動的にパスを張り替えるといった柔軟な運用が可能となる。与えられた物理トポロジとエッジノード間の交流トラヒック行列に対して、どのような経路で仮想的なパスを設置するかが論理トポロジ設計となる。物理的な網資源が与えられた上での設計となるため、通常、リンク容量といった様々な制約条件を考慮して設計を行う必要がある。
【０００７】
論理パスを物理トポロジ上に設置できる場合、物理トポロジ設計時に論理トポロジを同時に設計することもできる。論理トポロジの設計周期は物理トポロジのそれと比較して遥かに短いため、運用開始後は、論理トポロジの設計のみが実施される。
ユーザにとっては経由ノードでの輻輳を回避し、経路の総距離が短いことが伝送遅延を抑える意味で望ましい。伝送資源の利用効率や信頼性の観点からも、特定のリンクにトラヒックが集中することを避け、できるだけ全リンクに均等に分散することが望ましい。しかし、設備コストや管理・保守コストを抑えるために設置ノード数やリンク数を減らすと、パス設定の柔軟性が低下し、トラヒックを適切に分散させることやパス長を抑えることが困難となる。このように、網トポロジを設計する際には、トラヒックの分散度合い、パスの平均長、網コスト、といった、単位が異なり、しかも互いに相反する複数の評価尺度を同時に考慮する必要がある。
【０００８】
複数の評価尺度を同時に考慮する方法としては、ミクロ経済学の分野で用いられるパレード最適の概念が代表的であり、論理トポロジ設計に応用した例も見られる。Ｍ個の評価尺度ＶＩ〜ＶＭが存在し、候補ｘのｍ番目の評価尺度値をＶｍ，ｘとすると、任意のｍに対してＶｍ，ｘ≦Ｖｍ，ｙであり、かつ、Ｖｍ，ｘ＜Ｖｍ，ｙとなるｍが存在するとき、候補ｘは候補ｙをパレート的に支配しているという（ただし、全ての評価尺度は小さいほど優れていると仮定）。そして、他に支配される候補が存在しない候補を全てパレート最適であるとする。
【０００９】
他に複数の評価尺度を同時に考慮する方法として、ＤＥＡ（Ｄａｔａ  Ｅｎｖｅｌｏｐｍｅｎｔ  Ａｎａｌｙｓｉｓ）が知られている。ＤＥＡは、主として投資先の事業体を評価する手法として開発されてきた評価法であり、各々の事業体の得意な分野（評価尺度）を評価するという姿勢で効率性を求めることができ、ＤＥＡを網トポロジ設計に適用した検討もなされている。
また、各候補トポロジに対して、各評価尺度の全候補集合中の順位を算出し、それらの全評価尺度中の平均値で候補トポロジの優劣を評価する方法も検討されている。
以上の技術については、非特許文献１（“複数の評価尺度を考慮した網トポロジ設計”（電子情報通信学会  信学技報，ｖｏｌ．１０６，ｎｏ．１１８，ＩＮ２００６−３１，ｐｐ．８５−９０，２００６年６月）
【００１０】
【非特許文献１】“複数の評価尺度を考慮した網トポロジ設計”（電子情報通信学会  信学技報，ｖｏｌ．１０６，ｎｏ．１１８，ＩＮ２００６−３１，ｐｐ．８５−９０，２００６年６月）
【発明の開示】
【発明が解決しようとする課題】
【００１１】
パレート最適により網設計を行った場合、最適であると判断される候補は多数に及ぶことから、候補を効果的に絞り込むことが困難である。
また、ＤＥＡは効率性の概念が直感的に難しく、得られた解の最適性の判断が困難である。また、効率性の計算には線形計画問題を解く必要があり、スケーラビリティに問題がある。
また、平均順位を用いる方法は、評価尺度間で重視する度合いに差をつけることができず、また各評価尺度の全候補中の分布の形を考慮できないという問題がある。
【００１２】
（目的）
本発明の目的は、評価尺度間で重視する度合いに差をつけ、評価尺度の分布形の差異を結果に反映させ、直感的に理解可能な、単位の異なる複数の評価尺度を同時に考慮した上で、最適な網トポロジを得ることが可能なＡＨＰを用いた網トポロジ設計方法および設計システムを提供することにある。
【課題を解決するための手段】
【００１３】
本発明によるＡＨＰを用いた網トポロジ設計方法は、ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択することを特徴としている。
また、上記の網トポロジ設計方法において、ＡＨＰの手法に従い評価尺度間の一対比較を行うことで、各評価尺度の重みを計算し、さらに各候補トポロジの各評価尺度に対するスコア値として、その評価尺度の値から全候補中の最小値を引いたものを正規化したものを用い、最終的に算出される各候補のスコア値で各候補の優劣を判断することも特徴としている。
さらに、上記の網トポロジ設計方法において、同時に考慮する評価尺度の例として、総ノード数、総リンク長、各パスの長さとトラヒック量の積を全パスについて足し合わせたもの、最大負荷リンクのトラヒック量、の四つを用いることも特徴としている。
【００１４】
本発明によるＡＨＰを用いた網トポロジ設計システムは、エッジノードの位置、コアノードの設置可能位置、およびリンクの設置可能位置が入力されるトポロジ情報・デマンド行列入力装置と、初期トポロジを生成する初期トポロジ生成装置と、初期トポロジに対していくつかのリンクとコアノードを追加した複数の候補トポロジを生成するトポロジ候補生成装置と、候補トポロジ間の優劣を評価するＡＨＰ適用装置と、得られた最適トポロジの集合を出力する最適トポロジ出力装置とを具備することも特徴としている。
【発明の効果】
【００１５】
本発明によれば、コアノードやリンクが設置可能な場所と、エッジノード、エッジノード間の交流トラヒック行列が与えられているときに、複数の評価尺度を考慮した上で最適な網トポロジを、ＡＨＰにより評価することにより求められる、という効果がある。
【発明を実施するための最良の形態】
【００１６】
以下、図面により本発明の実施形態を説明する。
図１は、本発明の一実施形態に係る網トポロジ設計装置のシステム構成図である。
図１において、１０１はトポロジ情報・デマンド行列入力装置、１０２は初期トポロジ生成装置、１０３はトポロジ候補生成装置、１０４はＡＨＰ適用装置、１０５最適トポロジ出力装置である。これらの装置は、いづれもコンピュータの制御により動作する。
トポロジ情報・デマンド行列入力装置１０１によりエッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置がそれぞれ入力される。初期トポロジ生成装置１０２により初期トポロジが生成される。また、トポロジ候補生成装約１０３により初期トポロジに対していくつかのリンクとコアノードを追加した複数の候補トポロジが生成され、ＡＨＰ適用装置１０４により候補トポロジ間の優劣が評価される。
そして、得られた最適トポロジの集合が、最適トポロジ出力装置１０５によって出力される。
【００１７】
次に、本発明の実施の形態に係るＡＨＰを用いた網トポロジ設計方法について、詳細に説明する。
一例として、物理トポロジ設計を対象に検討を進めるが、論理パスを上位に設置することを想定し、物理トポロジ設計時に論理パスの設置も同時に行う（ただし、リンク容量等の制約条件は考慮しない）。
しかしながら、本発明の網トポロジ設計法は、複数の評価尺度をどのように同時に考慮するかに主眼を置いており、制約条件については汎用性が高く、様々な制約条件が生じる運用開始後の論理トポロジ設計にも応用が可能である。
【００１８】
（評価尺度）
物理トポロジ設計を行う際に考慮すべき評価尺度について考える。設計対象として、特にバックボーンネットワークを考えると、物理トポロジには全エッジノード間の接続性と障害発生時にも接続性を維持できる冗長性が求められる。そこで、ここでは物理トポロジ設計時の制約条件として、（イ）全エッジノード間の接続性、（ロ）リンク障害時にも全エッジノード間の接続性が迂回経路により維持されること、の二つを考える。
評価尺度としては様々なものが考えられるが、ここでは次の四つを例として考える（ｉ番目の評価尺度をＶｉと表記する）。
【００１９】
（１）総ノード数：設置されたエッジノードとコアノードを合わせた総数であり、Ｎｅをエッジノード数、Ｎｃを設置コアノード数とすると、
【００２０】
【数１】
2008165468.tif 000003
とする。Ｎｃは全ての候補トポロジで同一であるため、Ｎｃの差異がそのままＶ１の差異となる。Ｖ１は小さい方が望ましい。
【００２１】
（２）総リンク距離：設置されたリンクの距離の総和であり、ｄｌをリンクｌの距離、Ｅａを設置リンクの集合とすると、
【００２２】
【数２】
2008165468.tif 000004
とする。Ｖ２も小さい方が望ましい。
【００２３】
（３）パスの距離をトラヒック量で重み付けした総和：伝送遅延の観点からはパス長が短いことが望ましく、パス長をパスのトラヒック量で重み付けした総和ζ＝Σｓ，ｄ∈Ｎｅ，ｓ≠ｄＤｓｄＴｓｄを評価尺度として考える。ただし、エッジノードｓからｄに向かうトラヒックが流れるパスをＰｓｄ，パスＰｓｄのトラヒック量をＴｓｄ，パスＰｓｄが経由するリンクの集合をΦｓｄ，パスＰｓｄの長さをＤｓｄ（Ｄｓｄ＝Σｌ∈Φｓｄｄｌ）とする。ｔｌをリンクｌの総トラヒック量とすると、ζはリンク距離ｄｌとトラヒック量ｔｌの積の総和に一致するため、
ζ＝ΣｌｅＥａｄｌ×ｔｌとなる。よって、
【００２４】
【数３】
2008165468.tif 000005
とする。Ｖ３も小さい方が望ましい。
【００２５】
（４）最大リンク負荷：トラヒックが特定のリンクに集中した場合、ボトルネックリンクを通るパスの伝送品質は大きく悪化する。また、リンクの伝送帯域は光ファイバや波長といった離散的な単位で増設されるため、伝送資源を有効に活用するためにはリンク負荷の偏りを抑え、分散させることが望ましい。そこで、最大負荷リンクのトラヒック量を評価尺度として考え、
【００２６】
【数４】
2008165468.tif 000006
とする。Ｖ４も小さい方が望ましい。
【００２７】
（候補トポロジの作成）
与えられた設置可能位置に対して全く自由にリンクとコアノードを配置した場合、得られたトポロジ候補には制約条件を満たさないものも含まれる。そのため、最初に制約条件を満たす物理トポロジを初期解として作成し、初期解に対して更に任意のコアノードやリンクを追加配備することによって作成された物理トポロジの集合を解の候補とする。この結果、初期解を作成した段階で既に制約条件を満足しているので、任意の候補トポロジを採用することが可能となる。
【００２８】
初期トポロジで配置されたリンクを除きた残るリンク設置可能位置の数をｚとする。任意の設置可能位置にリンクを設置した結果、得られるトポロジの総数は２ｚ個となる。このようにして作成された各トポロジにおいて、次数が３以上となったコアノード設置可能位置にはコアノードを配置するが、次数が２となったコアノード設置可能位置には交換機能が不要であるため、コアノードを設置せず、２本の配置リンクを直結する。また、次数が１となるコアノード設置可能位置が存在するトポロジは不適切なトポロジであるため、検討候補からは除く。
【００２９】
次に、候補として作成した各トポロジに対して、与えられた交流トラヒック行列を用いて各エッジノード間に論理パスを設定する。ここでは、ノードｓからｄに流れるトラヒックに対しては１本のパスＰｓｄのみが設置され、パスＰｓｄを要求トラヒック量Ｔｓｄの大きな順に構築法（一旦設置したパスを変更しない）によりパスを設置する。個々のパスの経路を決める際に、Ｄｓｄ＝Σｌ∈Φｓｄｄｌ×ｔ’ｌが最小となる経路を選択する。ただし、該当パスを設置する時点のリンクｌのトラヒック量をｔ’ｌとする。パス設置時にリンク容量制約は考慮しない。全てのパスを設置した結果、１本もパスが通らないリンクが存在するトポロジは、やはり不適切なトポロジであるため、検討候補から除く。
【００３０】
（ＡＨＰによるトポロジ評価）
図２は、本発明におけるＡＨＰ適用モデルのブロック図である。
ＡＨＰを網トポロジ設計に適用すると、図２に示すように、トップの階層（階層０）には解くべき問題Ｐ（この場合、“最適なネットワークの選択”）が、中央の階層（階層１）には評価尺度Ｖｉが、そしてボトム（階層２）には候補トポロジが並ぶ。ここで、階層ｃ（ｃ＝１，２）における要素ｉの階層ｃ−１における要素ｊに対する重みをｗｃｉｊと表記する。各候補ｉの最終的なスコアＳｉの導出を考える。
図２では、評価尺度Ｖｉとして、Ｖ１〜Ｖ４（例えば、総ノード数、総リンク距離、パスの距離をトラヒック量で重み付けした総和、および最大リンク負荷）が示され、候補トポロジＡｉとして、Ａ１〜Ａ８３８６８が示されている。
【００３１】
図３は、本発明における一対比較値とその意味を示す図である。
階層１（評価尺度）間の優劣は網設計者の意思に左右されるため、問題Ｐに対する重みを何等かの方法で定量化する必要がある。ＡＨＰでは、評価尺度ｉに対する評価尺度ｊの重要度ａｉｊを、一対比較を行うことにより、図３に示す値で設定する。重みｗｃｉｊを要素にもつベクトルは、ａｉｊを要素にもつ行列Ａの最大固有値λｍａｘに対応する固有ベクトルに一致する。ここで、一対比較の整合性を図る尺度として整合度Ｃ．Ｉ．（ｃｏｎｓｉｓｔｅｎｃｙ  ｉｎｄｅｘ）を用いる。Ｃ．Ｉ．＝（λｍａｘ−Ｎｃ）／（Ｎｃ−１）である（Ｎｃは階層ｃの要素数）。Ｃ．Ｉ．は０．１以下であれば、整合性は通常、合格と判断できる。
図３では、一例として、重要度ａｉｊとしての一対比較値が１のときは、ある評価尺度が他の評価尺度と同じぐらい重要、３のときは、前者が後者より若干重要、５のときは、前者が後者より重要、７のときは、前者が後者よりかなり重要、９のときは、前者が後者より絶対的に重要であることを、それぞれ示している。なお、２，３，６，８は、それぞれ１，３，５，７，９の中間に位置する重要度とする。また、１〜９の逆数である１〜１／９は、上記の意味を後者から前者を見た場合に使用している。
【００３２】
要素Ｖｉｃの問題Ｐに対するスコアＳｉｃは、階層ｃ−１のＶｉｃが関係する全ての要素のスコアＳｉｃ−１を用いて次式で得られる。
【００３３】
【数５】
2008165468.tif 000007
ただし、ΦｉｃはＶｉｃが関係する要素の集合である。階層１においては、Ｐに対する重みがそのままスコアとなる。以下、ｃ＝２についてスコアが算出できる。
【００３４】
候補ｉの評価尺度ｊの値をＶｉｊと表記する。評価尺度ｊにおける候補トポロジｉの重みは、Ｖｉｊが定量的な値をもつことから、通常、ＡＨＰではＶｉｊを単に全候補中で正規化した値Ｘｉｊを用いる。従って、スコアＳｉｃを得る場合には、この値Ｘｉｊを上記〔数５〕の式中のωｉｊｃに代入すればよい。
【００３５】
【数６】
2008165468.tif 000008
しかし、網トポロジの候補は、通常、非常に多数となるため、このままでは上式中の分母が大きくなり、候補間のＸｉｊの値の差異が僅かとなる。その結果、単に重視された評価尺度が良好な候補を選択する傾向が強くなる。
【００３６】
本発明では、この問題を解決するため、次式で定義されるＺｉｊを重みに用いる。
【００３７】
【数７】
2008165468.tif 000009
ただし、ｍｉｎ｛Ｖｊ｝は全候補中のＶｉｊの最小値である。この値Ｚｉｊも正規化されているので、スコアＳｉｃを得る場合には、この値Ｚｉｊを上記〔数５〕の式中のωｉｊｃに代入すればよい。
【００３８】
このように、本発明による網トポロジ設計方法における第一の特徴は、ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択すること（前述の段落〔００１６〕および図１参照）である。
第二の特徴は、上記の網トポロジ設計方法において、ＡＨＰの手法に従い評価尺度間の一対比較（図３参照）を行うことで、各評価尺度の重みを計算し、さらに各候補トポロジの各評価尺度に対するスコア値として、その評価尺度の値から全候補中の最小値を引いたものを正規化したもの（〔数６〕〔数７〕の各式参照）を用い、最終的に算出される各候補のスコア値（〔数５〕の式参照）で各候補の優劣を判断することである。
さらに、第三の特徴は、上記の網トポロジ設計方法において、同時に考慮する評価尺度の例として、総ノード数、総リンク長、各パスの長さとトラヒック量の積を全パスについて足し合わせたもの、最大負荷リンクのトラヒック量、の四つ（前述の段落〔００１８〕（評価尺度）の（１）〜（４）参照）を用いることである。
【００３９】
それ以外の評価方法として、下記のトポロジ評価がある。
（平均順位によるトポロジ評価）
各候補トポロジｉに対して、各評価尺度のＮの候補集合中の順位を算出する。全ての評価尺度は小さいほど望ましいので、順位は単に各評価尺度Ｖｋ，ｉを小さな順にソートすることで計算できる（ｋ＝１，２，３，４）。
こうしてトポロジｉの各評価尺度Ｖｋ，ｉに対して得られた順位ｒ（ｋ，ｉ）を用いて、下記（８）式により、トポロジｉの平均順位（ＡＲ）を算出し、単純に平均順位（ＡＲ）の値が小さな候補トポロジを優れたトポロジであると評価する。すなわち、Ｎの全候補トポロジ中、平均順位（ＡＲ）の値が最小となったトポロジを最適な網トポロジであると判断する。
【００４０】
【数８】
2008165468.tif 000010
通常、単位の異なる複数の評価尺度を単純に足し合わせて評価することはできない。しかし、各評価尺度を全候補中の順位という相互比較が可能な同一の尺度に置き換えることにより、単純にそれらの平均値で最終的な優劣が評価できる。
平均順位法は、任意数Ｍ個の評価尺度を同時に考慮することができ、その場合、トポロジｉの平均順位（ＡＲ）は下記（９）式となる。
【００４１】
【数９】
2008165468.tif 000011
評価値である平均味位の計算は非常に簡易である。各評価尺度の順位を求めるのにソート処理が必要であるが、ＭｅｒｇｅソートやＱｕｉｃｋソートといったソートアルゴリズムを用いれば０（ＮｌｏｇＮ）の処理量で済むことから、ＤＥＡと比較して遥かに短い時間で網トポロジ設計が可能である。
【図面の簡単な説明】
【００４２】
【図１】本発明の一実施形態に係るＡＨＰを用いた網トポロジ設計システムの構成図である。
【図２】本発明におけるＡＨＰ適用モデルを示す図である。
【図３】本発明における一対比較値とその意味を示す図である。
【符号の説明】
【００４３】
１０１  トポロジ情報・デマンド行列入力装置
１０２  初期トポロジ生成装置
１０３  トポロジ候補生成装置
１０４  ＡＨＰ適用装置
１０５  最適トポロジ出力装置
【図１】
2008165468.tif 000012
【図２】
2008165468.tif 000013
【図３】
2008165468.tif 000014