綱トポロジ設計方法および綱トポロジ設計装置
【課題】直感的で、シンプルで、スケーラビリティにも優れており、しかも、単位の異なる複数の評価尺度を同時に考慮した上で、最適な網トポロジを得る。
【解決手段】ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計方法であって、各々のトポロジ候補に対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断する。同時に考慮する評価尺度は、総ノード数、総リンク長、各パスの長さとトラヒック量の積を全パスについて足し合わせたもの、最大負荷リンクのトラヒック量の四つを用いる。
【解決手段】ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計方法であって、各々のトポロジ候補に対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断する。同時に考慮する評価尺度は、総ノード数、総リンク長、各パスの長さとトラヒック量の積を全パスについて足し合わせたもの、最大負荷リンクのトラヒック量の四つを用いる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、綱トポロジ設計方法および綱トポロジ設計装置に係り、特に、網トポロジ設計問題において、平均順位で評価することにより、単位の異なる複数の評価尺度を同時に考慮して、最適な網トポロジを求める方法に関する。
【背景技術】
【０００２】
光ファイバやルータといったネットワークの物理的な資源を管理・運営している通信事業者や一部のインターネット・プロバイダ（ＩＳＰ；Internet Service Provider）にとっては、物理的な網トポロジをどのように構成するかという物理トポロジ設計は重要な問題である。
物理トポロジは、ノードやリンクの設計コスト、網の管理・保守コスト、障害に対する信頼性、などを決める要因となる。
また、ＬＳＰ（Label Switched Path）や波長パス等の論理パスの設置ができず、パケットが転送される経路を明示的に設定できない場合には、物理トポロジがリンク負荷やパケットの経路に直接影響を与え、伝送遅延品質やスループットといったユーザ品質を定める要因となる。
一方、ＭＰＬＳ（Multiprotocol Label Switching）網や波長パス網といった、物理網上に論理的なパスを設置し対地間のパスの経路を明示的に設計できる場合には、論理トポロジ設計により物理トポロジのユーザ品質に対する影響をある程度、排除することが可能である。
この場合、物理トポロジの設計に加え、論理トポロジの設計を適切に行う必要がある。このように網トポロジ設計問題は、物理トポロジ設計問題と論理トポロジ設計問題に大別できる。以下に各々の概略をまとめる。
【０００３】
［物理トポロジ設計問題］
ネットワークの一般化した構成要素として、エッジノード、コアノード、リンクの３種類を考える。エッジノードは交流トラヒックの発着ノードであり、直接もしくは下位のネットワークを介してエンドホストを収容する。
一方、コアノードは中継機能のみを有するノードであり、ユーザを収容しない。リンクはエッジノードやコアノード間を繋ぐ役割を果たす。任意のエッジノード間の交流トラヒック行列は与えられるとする。
通信事業者は、既に地理的特性を考慮して配置された管路や局舎といった土木インフラを保有しており、これらを再設計することは現実的ではない。そのため、エッジノードの位置と、コアノードやリンクの設置可能な位置は与えられるとする。
ネットワークに求められる要件の変化に合わせ、これら既存の管路や局舎を選別し、どこに光ファイバやルータといった設備を配置するかを検討することが、現実的な問題である。そこで、ここでは、物理トポロジ設計を、「与えられたコアノードとリンクの設置候補位置に対して、実際に設置する候補位置を選択する行為」と定義する。但し、全てのエッジノード設置位置にはエッジノードを設置する。
【０００４】
［論理トポロジ設計問題 ］
ＭＰＬＳルータやＯＸＣ（光クロスコネクトシステム）を用いると、物理ネットワーク上に仮想的なパス（ＬＳＰや波長パス）を設置することが可能となり、各対地間のトラヒックが流れる経路を明示的に設計できる。
物理トポロジは一旦構築されると変更することが困難であり、設計周期は１年から数年に及ぶが、論理トポロジは容易に変更することが可能であり、交流トラヒックの変化に応じて数分から数時間といった周期で動的にパスを張り替えるといった柔軟な運用が可能となる。
与えられた物理トポロジとエッジノード間の交流トラヒック行列に対して、どのような経路で仮想的なパスを設置するかが論理トポロジ設計となる。物理的な網資源が与えられた上での設計となるため、通常、リンク容量といった様々な制約条件を考慮して設計を行う必要がある。
【０００５】
論理パスを物理トポロジ上に設置できる場合、物理トポロジ設計時に論理トポロジを同時に設計することもできる。論理トポロジの設計周期は、物理トポロジのそれと比較して遙かに短いため、運用開始後は、論理トポロジの設計のみが実施される。
ユーザにとっては、経由ノードでの輻輳を回避し、経路の総距離が短いことが伝送遅延を抑える意味で望ましい。
さらに、伝送資源の利用効率や信頼性の観点からも、特定のリンクにトラヒックが集中することを避け、できるだけ全リンクに均等に分散することが望ましい。
しかし、設備コストや管理・保守コストを抑えるために設置ノード数やリンク数を減らすと、パス設定の柔軟性が低下し、トラヒックを適切に分散させることやパス長を抑えることが困難になる。
このように、網トポロジを設計する際には、トラヒックの分散度合い、パスの平均長、網コストといった、単位が異なり、しかも互いに相反する複数の評価尺度を同時に考慮する必要がある。
【０００６】
複数の評価尺度を同時に考慮する方法としては、ミクロ経済学の分野で用いられるパレート最適の概念が代表的であり、論理トポロジ設計に応用した例も見られる。
Ｍ個の評価尺度Ｖ１〜ＶＭが存在し、ｍを任意の値、候補ｘのｍ番目の評価尺度値をＶｍ，ｘとするとき、全てのｍに対してＶｍ，ｘ≦Ｖｍ，ｙ であり、かつ、Ｖｍ，ｘ＜Ｖｍ，ｙとなる少なくとも１つのｍが存在するとき、候補ｘは候補ｙをパレート的に支配しているという。但し、全ての評価尺度は小さいほど優れていると仮定する。そして、他に支配される候補が存在しない候補を全てパレート最適であるとする。
他に複数の評価尺度を同時に考慮する方法として、ＤＥＡ（Data Envelopment Analysis）が知られている。ＤＥＡは、主として投資先の事業体を評価する手法として開発されてきた評価法であり、各々の事業体の得意な分野（評価尺度）を評価するという姿勢で効率性を求めることができ、ＤＥＡを網トポロジ設計に適用した検討もなされている。なお、以上の技術については、下記非特許文献１を参照されたい。
【０００７】
なお、本願発明に関連する先行技術文献としては以下のものがある。
【非特許文献１】G.Huiban,and G.R.Mateus, "A multiobjective approach of the virtual topology design and routing problem in WDM networks," ICT International Conference on Telecommunications,2005.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、パレート最適により網設計を行った場合、最適であると判断される候補は多数に及ぶ事から、候補を効果的に絞り込むことが困難である。
また、ＤＥＡは、効率性の概念が直感的に難しく、得られた解の最適性の判断が困難である。さらに、効率性の計算には線形計画問題を解く必要があり、スケーラビリティに問題がある。
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、綱トポロジ設計方法および綱トポロジ設計装置において、直感的で、シンプルで、スケーラビリティにも優れており、しかも、単位の異なる複数の評価尺度を同時に考慮した上で、最適な網トポロジを得ることが可能となる技術を提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【課題を解決するための手段】
【０００９】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
前述の目的を達成するために、本発明は、ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計方法であって、各々のトポロジ候補に対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断する。
また、本発明では、同時に考慮する評価尺度は、総ノード数、総リンク長、各パスの長さとトラヒック量の積を全パスについて足し合わせたもの、最大負荷リンクのトラヒック量の四つを用いる。
また、本発明は、ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計装置であって、エッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置が入力されるトポロジ情報・デマンド行列入力装置と、前記トポロジ情報・デマンド行列入力装置により入力されたエッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置に基づき、初期トポロジを生成する初期トポロジ生成装置と、前記初期トポロジ生成装置により生成された初期トポロジに対して、いくつかのリンクとコアノードを追加して複数の候補トポロジを生成するトポロジ候補生成装置と、前記トポロジ候補生成装置により生成された複数の候補トポロジに対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、各評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断する平均順位算出装置と、前記平均順位算出装置での評価結果に基づき最適トポロジの集合を出力する最適トポロジ出力装置とを有する。
【発明の効果】
【００１０】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、直感的で、シンプルで、スケーラビリティにも優れており、しかも、単位の異なる複数の評価尺度を同時に考慮した上で、最適な網トポロジを得ることが可能となる。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照して本発明の実施例を詳細に説明する。
なお、実施例を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
図１は、本発明の実施例の平均順位を用いた網トポロジ設計装置の概略構成を示すブロック図である。図１において、１０１はトポロジ情報・デマンド行列入力装置、１０２は初期トポロジ生成装置、１０３はトポロジ候補生成装置、１０４は平均順位算出装置、１０５は最適トポロジ出力装置である。
トポロジ情報・デマンド行列入力装置１０１により、エッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置が入力される。
初期トポロジ生成装置１０２は、トポロジ情報・デマンド行列入力装置１０１により入力されたエッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置に基づき初期トポロジを生成する。
トポロジ候補生成装置１０３は、初期トポロジ生成装置１０２により生成された初期トポロジに対して、幾つかのリンクとコアノードを追加して複数の候補トポロジを生成する。 平均順位算出装置１０４は、トポロジ候補生成装置１０３により生成された複数の候補トポロジ間の優劣を評価する。
最適トポロジ出力装置１０５は、平均順位算出装置１０４での評価結果に基づき最適トポロジの集合を出力する。
【００１２】
次に、本発明の実施例の平均順位を用いた網トポロジ設計方法について、詳細を説明する。なお、ここでは、例として、物理トポロジ設計を対象に検討を進めるが、論理パスを上位に設置することを想定し、物理トポロジ設計時に論理パスの設置も同時に行う（但し、リンク容量等の制約条件は考慮しない）。
しかし、本発明の網トポロジ設計法は、複数の評価尺度をどのように同時に考慮するかに主眼を置いており、制約条件については汎用性が高く、様々な制約条件が生じる運用開始後の論理トポロジ設計にも応用が可能である。
［評価尺度］
物理トポロジ設計を行う際に考慮すべき評価尺度について考える。設計対象として、特にバックボーンネットワークを考えると、物理トポロジには全エッジノード間の接続性と障害発生時にも接続性を維持できる冗長性が求められる。
そこで、ここでは、物理トポロジ設計時の制約条件として、（ｉ）全エッジノード間の接続性、（ｉｉ）１リンク障容時にも全エッジノード間の接続性が迂回経路により維持されることの二つを考える。
【００１３】
評価尺度としては様々なものが考えられるが、ここでは次の四つを例として考える。なお、ｉ番目の評価尺度をＶｉと表記する。
（１）総ノード数：
設置されたエッジノードとコアノードを合わせた総数であり、Ｎｅをエッジノード数、Ｎｃを設置コアノード数とすると、１番目の評価尺度（Ｖ１）は、下記（１）式で表される。
Ｖ１＝Ｎｅ＋Ｎｃ ・・・・・・・・・・・・・・・・・ （１）
エッジノード数（Ｎｅ）は、全ての候補トポロジで同一なので、設置コアノード数（Ｎｃ）の差異がそのまま、１番目の評価尺度（Ｖ１）の差異となる。なお、１番目の評価尺度（Ｖ１）は小さい方が望ましい。
（２）総リンク距離：
設置されたリンクの距離の総和であり、ｄｌをリンクｌの距離、Εαを設置リンクの集合とすると、２番目の評価尺度（Ｖ２）は、下記（２）式で表される。２番目の評価尺度（Ｖ２）も小さい方が望ましい。
【００１４】
【数１】
【００１５】
（３）パスの距離をトラヒック量で重み付けした総和：
伝送遅延の観点からはパス長が短いことが望ましく、下記（３）式に示す、パス長をパスのトラヒック量で重み付けした総和（ζ）を評価尺度として考える。但し、エッジノードｓからエッジノードｄに向かうトラヒックが流れるパスをＰｓｄ、パスＰｓｄのトラヒック量をＴｓｄ、パスＰｓｄが経由するリンクの集合をΦｓｄ、パスＰｓｄの長さを下記（４）式に示すＤｓｄとする。
ｔｌをリンクｌの総トラヒック量とすると、ζはリンク距離ｄｌとトラヒック量ｔｌの積の総和に一致するため、総和（ζ）は下記（５）式となる。
よって、３番目の評価尺度（Ｖ３）は、下記（６）式で表される。３番目の評価尺度（Ｖ３）も小さい方が望ましい。
【００１６】
【数２】
【００１７】
（４）最大リンク負荷：
トラヒックが特定のリンクに集中した場合、ボトルネックリンクを通るパスの伝送品質は大きく悪化する。また、リンクの伝送帯域は光ファイバや波長といった離散的な単位で増設されるため、伝送資源を有効に活用するためにはリンク負荷の偏りを抑え、分散させることが望ましい。そこで、最大負荷リンクのトラヒック量を評価尺度として考えると、４番目の評価尺度（Ｖ４）は、下記（７）式で表される。４番目の評価尺度（Ｖ４）も小さい方が望ましい。
【００１８】
【数３】
【００１９】
［候補トポロジの作成］
与えられた設置可能位置に対して全く自由にリンクとコアノードを配置した場合、得られたトポロジ候補には制約条件を満たさないものも含まれる。そのため、最初に制約条件を満たす物理トポロジを初期解として作成し、初期解に対して更に任意のコアノードやリンクを追加配備することによって作成された物理トポロジの集合を解の侯補とする。
この結果、初期解を作成した段階で既に制約条件を満足しているので、任意の候補トポロジを採用することが可能となる。
初期トポロジで配置されたリンクを除いた残るリンク設置可能位置の数をｚとする。任意の設置可能位置にリンクを配置した結果得られるトポロジの総数は２ｚ個となる。
こうして作成された各トポロジにおいて、次数が３以上となったコアノード設置可能位置にはコアノードを配置するが、次数が２となったコアノード設置可能位置には交換機能が不要であるためコアノードを設置せず、２本の配置リンクを直結する。また、次数が１となるコアノード設置可能位置が存在するトポロジは不適切なトポロジであるため検討候補からは除く。
【００２０】
次に、候補として作成した各トポロジに対して、与えられた交流トラヒック行列を用いて各エッジノード間に論理パスを設定する。ここでは、ノードｓからノードｄに流れるトラヒックに対しては、１本のパスＰｓｄのみが設置され、パスＰｓｄを要求トラヒック量Ｔｓｄの大きな順に構築法（一旦、配置したパスを変更しない）によりパスを設置する。
個々のパスの経路を決める際、下記（８）式に示すトラヒック量（ζ’）が最小となる経路を選択する。但し、該当パスを設置する時点のリンクｌのトラヒック量をｔｌとする。パス設置時にリンク容量制約は考慮しない。全ての世パスを設置した結果、１本もパスから通らないリンクが存在するトポロジは、やはり不適切なトポロジであるため検討候補から除く。
【００２１】
【数４】
【００２２】
［平均順位によるトポロジ評価］
各候補トポロジｉに対して、各評価尺度のΝの候補集合中の順位を算出する。全ての評価尺度は小さいほど望ましいので、順位は単に各評価尺度Ｖｋ，ｉを小さな順にソートすることで計算できる（ｋ=１，２，３，４）。
こうしてトポロジｉの各評価尺度Ｖｋ，ｉに対して得られた順位Ｒ（ｋ，ｉ）を用いて、下記（９）式により、トポロジｉの平均順位（ＡＲ）を算出し、単純に平均順位（ＡＲ）の値が小さな侯補トポロジを優れたトポロジであると評価する。即ち、Ｎの全候補トポロジ中、平均順位（ＡＲ）の値が最小となったトポロジを最適な網トポロジであると判断する。
ＡＲｉ＝｛Ｒ（１，ｉ）＋Ｒ（２，ｉ）＋Ｒ（３，ｉ）＋Ｒ（４，ｉ）｝／４
・・・・・・・・・・・・・・・・・ （９）
通常、単位の異なる複数の評価尺度を単純に足し合わせて評価することはできない。しかし、各評価尺度を全侯補中の順位という相互比較が可能な同一の尺度に置き換えることにより、単純にそれらの平均値で最終的な優劣が評価できる。
平均順位法は、任意数Μ個の評価尺度を同時に考慮することができ、その場合、トポロジｉの平均順位（ＡＲ）は下記（１０）式となる。
評価値である平均順位の計算は非常に簡易である。各評価尺度の順位を求めるのにソート処理が必要であるが、MergeソートやQuickソートといったソートアルゴリズムを用いればＯ（ΝlogΝ）の処理量で済むことから、ＤＥＡと比較して遥かに短い時間で網トポロジ設計が可能である。
【００２３】
【数５】
【００２４】
［数値評価］
次に、具体的なネットワークモデルを用いて、平均順位法による網トポロジ設計を行った数値評価結果について述べる。
計算は全て、３．２ＧＨｚのＣＰＵ、１ＧＢのメモリのパーソナルコンピュータ（ＰＣ）で行った。
［評価ネットワークモデル］
図２に、本実施例において、評価に用いたネットワークモデル（日本列島モデル）を示す。但し、黒丸がエッジノードを表し、点線で描かれた丸と線がコアノードとリンクの設置可能位置を表す。
また、図２には、各々のエッジノードｋが収容する人口Ｕｋを示す。エッジノードｓからエッジノードｄに流れるトラヒック量Ｔｓｄは、両端のエッジノードの人口の積に比例させ、下記（１１）式で求める値とした。但し、Ｔはネットワーク全体のトラヒック量であり、ここでは、Ｔ=１０Ｔｂｐｓとした。
【００２５】
【数６】
【００２６】
１リンク障害に対して迂回路を確保でき、全エッジノード間の接続性を確保できる初期トポロジとしてループ型トポロジを考え、図２の実線で示すリンク設置可能位置には必ずリンクを配置した。
ループが経由するコアノード設置可能位置の次数は２となり交換機能が不要であることから、これら設置可能位置にコアノードを配置する必要はない。
初期トポロジで採用されたリンクを除くと、１７本のリンク設置可能位置が残るため２１７個の物理トポロジを構成可能であるが、次数が１となるコアノードや未使用リンクが存在するトポロジを候補から除外した結果、８３，８６８個の侯補トポロジが得られた。なお、これらの候補トポロジを得るのに要した計算時間は７５秒程度であった。
【００２７】
［平均順位法の適用結果］
平均順位（ＡＲ）の算出に要する計算量は僅かであり、８３，８６８個の全ての侯補トポロジを対象に平均順位（ＡＲ）を算出しても要した時間は１秒未満であった。
平均順位（ＡＲ）が小さなトポロジほど望ましいトポロジであるため、候補トポロジの最終評価順位は平均順位（ＡＲ）の小さな順となる。
図３は、８３，８６８個の候補トポロジを対象に、前述の（５）式より算出した平均順位（ＡＲ）を最終評価の順にプロットしたグラフである。
８３，８６８個の候補トポロジにおける、平均順位（ＡＲ）の最小値、最大値、平均は各々、３８１３．２５、７５２９５．２５、３９９１５．０であった。
４つの評価尺度のいくつかは相反するため、全ての評価尺度が非常に優れた候補トポロジや、反対に全ての評価尺度が非常に悪い候補トポロジは存在しない。そのため、平均順位（ＡＲ）の最小値は１より大きく、平均順位（ＡＲ）の最大値は候補トポロジ数８３，８６８より小さな値となっている。
【００２８】
大多数の候補トポロジの平均順位（ＡＲ）は２０，０００〜６０，０００の範囲に存在し、平均順位（ＡＲ）が最小値（３６１３．２５）に近いトポロジは少数に限定されることがわかる。
このことは、これら平均順位（ＡＲ）が小さな少数のトポロジのみに選択候補を絞ることにより、少数の優れた網トポロジを選択できることを意味する。
図４は、図３に示すグラフの平均順位（ＡＲ）が小さな上位１０位のトポロジについて、平均順位（ＡＲ）、４つの評価尺度の値と、それらの全候補トポロジ中の順位をまとめた表である。また、これら上位１０のトポロジを図５に示す。４つの全ての評価尺度が良好なバランスのいい侯補トポロジが、平均順位法では高く評価されることがわかる。
【００２９】
図６は、平均順位（ＡＲ）の小さい最終評価順位の高い候補トポロジの順に、４つの評価尺度を各々プロットしたグラフである。１つの点が１つの候補トポロジに対応する。但し、平均順位（ＡＲ）が１０位以内の侯補トポロジについては大きな点でプロットしている。
全ての評価尺度が良好な候補トポロジが、平均順位法では上位に評価されることが確認できる。また、Ｖ１、Ｖ２、およびＶ４の評価尺度が極めて良好な物理トポロジの平均順位（ＡＲ）は大きく、平均順位法での評価は低いことが確認できる。
このことは、単一の評価尺度のみを考慮して綱トポロジ設計を行った場合、他の評価尺度が悪化することを意味し、平均順位法の有効性が確認できる。
以上説明したように、本実施例によれば、コアノードやリンクが設置可能な場所と、エッジノード、エッジノード間の交流トラヒック行列が与えられているときに、複数の評価尺度を考慮した上で最適な綱トポロジを、平均順位法により評価して求めることができる。
以上、本発明者によってなされた発明を、前記実施例に基づき具体的に説明したが、本発明は、前記実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００３０】
【図１】本発明の実施例の平均順位を用いた網トポロジ設計装置の概略構成を示すブロック図である。
【図２】本発明の実施例において、評価に用いたネットワークモデルを示す図である。
【図３】図２に示すネットワークモデルから生成された候補トポロジの最終評価順位を示すグラフである。
【図４】図３に示すグラフの平均順位（ＡＲ）が小さな上位１０位のトポロジについて、平均順位（ＡＲ）、４つの評価尺度の値と、それらの全候補トポロジ中の順位をまとめた表である。
【図５】図３に示すグラフの上位１０のトポロジを示す図である。
【図６】図２に示すネットワークモデルから生成された候補トポロジの最終評価順位の順でプロットした各評価尺度値を示すグラフである。
【符号の説明】
【００３１】
１０１ トポロジ情報・デマンド行列入力装置
１０２ 初期トポロジ生成装置
１０３ トポロジ候補生成装置
１０４ 平均順位算出装置
１０５ 最適トポロジ出力装置
【技術分野】
【０００１】
本発明は、綱トポロジ設計方法および綱トポロジ設計装置に係り、特に、網トポロジ設計問題において、平均順位で評価することにより、単位の異なる複数の評価尺度を同時に考慮して、最適な網トポロジを求める方法に関する。
【背景技術】
【０００２】
光ファイバやルータといったネットワークの物理的な資源を管理・運営している通信事業者や一部のインターネット・プロバイダ（ＩＳＰ；Internet Service Provider）にとっては、物理的な網トポロジをどのように構成するかという物理トポロジ設計は重要な問題である。
物理トポロジは、ノードやリンクの設計コスト、網の管理・保守コスト、障害に対する信頼性、などを決める要因となる。
また、ＬＳＰ（Label Switched Path）や波長パス等の論理パスの設置ができず、パケットが転送される経路を明示的に設定できない場合には、物理トポロジがリンク負荷やパケットの経路に直接影響を与え、伝送遅延品質やスループットといったユーザ品質を定める要因となる。
一方、ＭＰＬＳ（Multiprotocol Label Switching）網や波長パス網といった、物理網上に論理的なパスを設置し対地間のパスの経路を明示的に設計できる場合には、論理トポロジ設計により物理トポロジのユーザ品質に対する影響をある程度、排除することが可能である。
この場合、物理トポロジの設計に加え、論理トポロジの設計を適切に行う必要がある。このように網トポロジ設計問題は、物理トポロジ設計問題と論理トポロジ設計問題に大別できる。以下に各々の概略をまとめる。
【０００３】
［物理トポロジ設計問題］
ネットワークの一般化した構成要素として、エッジノード、コアノード、リンクの３種類を考える。エッジノードは交流トラヒックの発着ノードであり、直接もしくは下位のネットワークを介してエンドホストを収容する。
一方、コアノードは中継機能のみを有するノードであり、ユーザを収容しない。リンクはエッジノードやコアノード間を繋ぐ役割を果たす。任意のエッジノード間の交流トラヒック行列は与えられるとする。
通信事業者は、既に地理的特性を考慮して配置された管路や局舎といった土木インフラを保有しており、これらを再設計することは現実的ではない。そのため、エッジノードの位置と、コアノードやリンクの設置可能な位置は与えられるとする。
ネットワークに求められる要件の変化に合わせ、これら既存の管路や局舎を選別し、どこに光ファイバやルータといった設備を配置するかを検討することが、現実的な問題である。そこで、ここでは、物理トポロジ設計を、「与えられたコアノードとリンクの設置候補位置に対して、実際に設置する候補位置を選択する行為」と定義する。但し、全てのエッジノード設置位置にはエッジノードを設置する。
【０００４】
［論理トポロジ設計問題 ］
ＭＰＬＳルータやＯＸＣ（光クロスコネクトシステム）を用いると、物理ネットワーク上に仮想的なパス（ＬＳＰや波長パス）を設置することが可能となり、各対地間のトラヒックが流れる経路を明示的に設計できる。
物理トポロジは一旦構築されると変更することが困難であり、設計周期は１年から数年に及ぶが、論理トポロジは容易に変更することが可能であり、交流トラヒックの変化に応じて数分から数時間といった周期で動的にパスを張り替えるといった柔軟な運用が可能となる。
与えられた物理トポロジとエッジノード間の交流トラヒック行列に対して、どのような経路で仮想的なパスを設置するかが論理トポロジ設計となる。物理的な網資源が与えられた上での設計となるため、通常、リンク容量といった様々な制約条件を考慮して設計を行う必要がある。
【０００５】
論理パスを物理トポロジ上に設置できる場合、物理トポロジ設計時に論理トポロジを同時に設計することもできる。論理トポロジの設計周期は、物理トポロジのそれと比較して遙かに短いため、運用開始後は、論理トポロジの設計のみが実施される。
ユーザにとっては、経由ノードでの輻輳を回避し、経路の総距離が短いことが伝送遅延を抑える意味で望ましい。
さらに、伝送資源の利用効率や信頼性の観点からも、特定のリンクにトラヒックが集中することを避け、できるだけ全リンクに均等に分散することが望ましい。
しかし、設備コストや管理・保守コストを抑えるために設置ノード数やリンク数を減らすと、パス設定の柔軟性が低下し、トラヒックを適切に分散させることやパス長を抑えることが困難になる。
このように、網トポロジを設計する際には、トラヒックの分散度合い、パスの平均長、網コストといった、単位が異なり、しかも互いに相反する複数の評価尺度を同時に考慮する必要がある。
【０００６】
複数の評価尺度を同時に考慮する方法としては、ミクロ経済学の分野で用いられるパレート最適の概念が代表的であり、論理トポロジ設計に応用した例も見られる。
Ｍ個の評価尺度Ｖ１〜ＶＭが存在し、ｍを任意の値、候補ｘのｍ番目の評価尺度値をＶｍ，ｘとするとき、全てのｍに対してＶｍ，ｘ≦Ｖｍ，ｙ であり、かつ、Ｖｍ，ｘ＜Ｖｍ，ｙとなる少なくとも１つのｍが存在するとき、候補ｘは候補ｙをパレート的に支配しているという。但し、全ての評価尺度は小さいほど優れていると仮定する。そして、他に支配される候補が存在しない候補を全てパレート最適であるとする。
他に複数の評価尺度を同時に考慮する方法として、ＤＥＡ（Data Envelopment Analysis）が知られている。ＤＥＡは、主として投資先の事業体を評価する手法として開発されてきた評価法であり、各々の事業体の得意な分野（評価尺度）を評価するという姿勢で効率性を求めることができ、ＤＥＡを網トポロジ設計に適用した検討もなされている。なお、以上の技術については、下記非特許文献１を参照されたい。
【０００７】
なお、本願発明に関連する先行技術文献としては以下のものがある。
【非特許文献１】G.Huiban,and G.R.Mateus, "A multiobjective approach of the virtual topology design and routing problem in WDM networks," ICT International Conference on Telecommunications,2005.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、パレート最適により網設計を行った場合、最適であると判断される候補は多数に及ぶ事から、候補を効果的に絞り込むことが困難である。
また、ＤＥＡは、効率性の概念が直感的に難しく、得られた解の最適性の判断が困難である。さらに、効率性の計算には線形計画問題を解く必要があり、スケーラビリティに問題がある。
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、綱トポロジ設計方法および綱トポロジ設計装置において、直感的で、シンプルで、スケーラビリティにも優れており、しかも、単位の異なる複数の評価尺度を同時に考慮した上で、最適な網トポロジを得ることが可能となる技術を提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【課題を解決するための手段】
【０００９】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
前述の目的を達成するために、本発明は、ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計方法であって、各々のトポロジ候補に対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断する。
また、本発明では、同時に考慮する評価尺度は、総ノード数、総リンク長、各パスの長さとトラヒック量の積を全パスについて足し合わせたもの、最大負荷リンクのトラヒック量の四つを用いる。
また、本発明は、ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計装置であって、エッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置が入力されるトポロジ情報・デマンド行列入力装置と、前記トポロジ情報・デマンド行列入力装置により入力されたエッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置に基づき、初期トポロジを生成する初期トポロジ生成装置と、前記初期トポロジ生成装置により生成された初期トポロジに対して、いくつかのリンクとコアノードを追加して複数の候補トポロジを生成するトポロジ候補生成装置と、前記トポロジ候補生成装置により生成された複数の候補トポロジに対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、各評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断する平均順位算出装置と、前記平均順位算出装置での評価結果に基づき最適トポロジの集合を出力する最適トポロジ出力装置とを有する。
【発明の効果】
【００１０】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、直感的で、シンプルで、スケーラビリティにも優れており、しかも、単位の異なる複数の評価尺度を同時に考慮した上で、最適な網トポロジを得ることが可能となる。
【発明を実施するための最良の形態】
【００１１】
以下、図面を参照して本発明の実施例を詳細に説明する。
なお、実施例を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
図１は、本発明の実施例の平均順位を用いた網トポロジ設計装置の概略構成を示すブロック図である。図１において、１０１はトポロジ情報・デマンド行列入力装置、１０２は初期トポロジ生成装置、１０３はトポロジ候補生成装置、１０４は平均順位算出装置、１０５は最適トポロジ出力装置である。
トポロジ情報・デマンド行列入力装置１０１により、エッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置が入力される。
初期トポロジ生成装置１０２は、トポロジ情報・デマンド行列入力装置１０１により入力されたエッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置に基づき初期トポロジを生成する。
トポロジ候補生成装置１０３は、初期トポロジ生成装置１０２により生成された初期トポロジに対して、幾つかのリンクとコアノードを追加して複数の候補トポロジを生成する。 平均順位算出装置１０４は、トポロジ候補生成装置１０３により生成された複数の候補トポロジ間の優劣を評価する。
最適トポロジ出力装置１０５は、平均順位算出装置１０４での評価結果に基づき最適トポロジの集合を出力する。
【００１２】
次に、本発明の実施例の平均順位を用いた網トポロジ設計方法について、詳細を説明する。なお、ここでは、例として、物理トポロジ設計を対象に検討を進めるが、論理パスを上位に設置することを想定し、物理トポロジ設計時に論理パスの設置も同時に行う（但し、リンク容量等の制約条件は考慮しない）。
しかし、本発明の網トポロジ設計法は、複数の評価尺度をどのように同時に考慮するかに主眼を置いており、制約条件については汎用性が高く、様々な制約条件が生じる運用開始後の論理トポロジ設計にも応用が可能である。
［評価尺度］
物理トポロジ設計を行う際に考慮すべき評価尺度について考える。設計対象として、特にバックボーンネットワークを考えると、物理トポロジには全エッジノード間の接続性と障害発生時にも接続性を維持できる冗長性が求められる。
そこで、ここでは、物理トポロジ設計時の制約条件として、（ｉ）全エッジノード間の接続性、（ｉｉ）１リンク障容時にも全エッジノード間の接続性が迂回経路により維持されることの二つを考える。
【００１３】
評価尺度としては様々なものが考えられるが、ここでは次の四つを例として考える。なお、ｉ番目の評価尺度をＶｉと表記する。
（１）総ノード数：
設置されたエッジノードとコアノードを合わせた総数であり、Ｎｅをエッジノード数、Ｎｃを設置コアノード数とすると、１番目の評価尺度（Ｖ１）は、下記（１）式で表される。
Ｖ１＝Ｎｅ＋Ｎｃ ・・・・・・・・・・・・・・・・・ （１）
エッジノード数（Ｎｅ）は、全ての候補トポロジで同一なので、設置コアノード数（Ｎｃ）の差異がそのまま、１番目の評価尺度（Ｖ１）の差異となる。なお、１番目の評価尺度（Ｖ１）は小さい方が望ましい。
（２）総リンク距離：
設置されたリンクの距離の総和であり、ｄｌをリンクｌの距離、Εαを設置リンクの集合とすると、２番目の評価尺度（Ｖ２）は、下記（２）式で表される。２番目の評価尺度（Ｖ２）も小さい方が望ましい。
【００１４】
【数１】
【００１５】
（３）パスの距離をトラヒック量で重み付けした総和：
伝送遅延の観点からはパス長が短いことが望ましく、下記（３）式に示す、パス長をパスのトラヒック量で重み付けした総和（ζ）を評価尺度として考える。但し、エッジノードｓからエッジノードｄに向かうトラヒックが流れるパスをＰｓｄ、パスＰｓｄのトラヒック量をＴｓｄ、パスＰｓｄが経由するリンクの集合をΦｓｄ、パスＰｓｄの長さを下記（４）式に示すＤｓｄとする。
ｔｌをリンクｌの総トラヒック量とすると、ζはリンク距離ｄｌとトラヒック量ｔｌの積の総和に一致するため、総和（ζ）は下記（５）式となる。
よって、３番目の評価尺度（Ｖ３）は、下記（６）式で表される。３番目の評価尺度（Ｖ３）も小さい方が望ましい。
【００１６】
【数２】
【００１７】
（４）最大リンク負荷：
トラヒックが特定のリンクに集中した場合、ボトルネックリンクを通るパスの伝送品質は大きく悪化する。また、リンクの伝送帯域は光ファイバや波長といった離散的な単位で増設されるため、伝送資源を有効に活用するためにはリンク負荷の偏りを抑え、分散させることが望ましい。そこで、最大負荷リンクのトラヒック量を評価尺度として考えると、４番目の評価尺度（Ｖ４）は、下記（７）式で表される。４番目の評価尺度（Ｖ４）も小さい方が望ましい。
【００１８】
【数３】
【００１９】
［候補トポロジの作成］
与えられた設置可能位置に対して全く自由にリンクとコアノードを配置した場合、得られたトポロジ候補には制約条件を満たさないものも含まれる。そのため、最初に制約条件を満たす物理トポロジを初期解として作成し、初期解に対して更に任意のコアノードやリンクを追加配備することによって作成された物理トポロジの集合を解の侯補とする。
この結果、初期解を作成した段階で既に制約条件を満足しているので、任意の候補トポロジを採用することが可能となる。
初期トポロジで配置されたリンクを除いた残るリンク設置可能位置の数をｚとする。任意の設置可能位置にリンクを配置した結果得られるトポロジの総数は２ｚ個となる。
こうして作成された各トポロジにおいて、次数が３以上となったコアノード設置可能位置にはコアノードを配置するが、次数が２となったコアノード設置可能位置には交換機能が不要であるためコアノードを設置せず、２本の配置リンクを直結する。また、次数が１となるコアノード設置可能位置が存在するトポロジは不適切なトポロジであるため検討候補からは除く。
【００２０】
次に、候補として作成した各トポロジに対して、与えられた交流トラヒック行列を用いて各エッジノード間に論理パスを設定する。ここでは、ノードｓからノードｄに流れるトラヒックに対しては、１本のパスＰｓｄのみが設置され、パスＰｓｄを要求トラヒック量Ｔｓｄの大きな順に構築法（一旦、配置したパスを変更しない）によりパスを設置する。
個々のパスの経路を決める際、下記（８）式に示すトラヒック量（ζ’）が最小となる経路を選択する。但し、該当パスを設置する時点のリンクｌのトラヒック量をｔｌとする。パス設置時にリンク容量制約は考慮しない。全ての世パスを設置した結果、１本もパスから通らないリンクが存在するトポロジは、やはり不適切なトポロジであるため検討候補から除く。
【００２１】
【数４】
【００２２】
［平均順位によるトポロジ評価］
各候補トポロジｉに対して、各評価尺度のΝの候補集合中の順位を算出する。全ての評価尺度は小さいほど望ましいので、順位は単に各評価尺度Ｖｋ，ｉを小さな順にソートすることで計算できる（ｋ=１，２，３，４）。
こうしてトポロジｉの各評価尺度Ｖｋ，ｉに対して得られた順位Ｒ（ｋ，ｉ）を用いて、下記（９）式により、トポロジｉの平均順位（ＡＲ）を算出し、単純に平均順位（ＡＲ）の値が小さな侯補トポロジを優れたトポロジであると評価する。即ち、Ｎの全候補トポロジ中、平均順位（ＡＲ）の値が最小となったトポロジを最適な網トポロジであると判断する。
ＡＲｉ＝｛Ｒ（１，ｉ）＋Ｒ（２，ｉ）＋Ｒ（３，ｉ）＋Ｒ（４，ｉ）｝／４
・・・・・・・・・・・・・・・・・ （９）
通常、単位の異なる複数の評価尺度を単純に足し合わせて評価することはできない。しかし、各評価尺度を全侯補中の順位という相互比較が可能な同一の尺度に置き換えることにより、単純にそれらの平均値で最終的な優劣が評価できる。
平均順位法は、任意数Μ個の評価尺度を同時に考慮することができ、その場合、トポロジｉの平均順位（ＡＲ）は下記（１０）式となる。
評価値である平均順位の計算は非常に簡易である。各評価尺度の順位を求めるのにソート処理が必要であるが、MergeソートやQuickソートといったソートアルゴリズムを用いればＯ（ΝlogΝ）の処理量で済むことから、ＤＥＡと比較して遥かに短い時間で網トポロジ設計が可能である。
【００２３】
【数５】
【００２４】
［数値評価］
次に、具体的なネットワークモデルを用いて、平均順位法による網トポロジ設計を行った数値評価結果について述べる。
計算は全て、３．２ＧＨｚのＣＰＵ、１ＧＢのメモリのパーソナルコンピュータ（ＰＣ）で行った。
［評価ネットワークモデル］
図２に、本実施例において、評価に用いたネットワークモデル（日本列島モデル）を示す。但し、黒丸がエッジノードを表し、点線で描かれた丸と線がコアノードとリンクの設置可能位置を表す。
また、図２には、各々のエッジノードｋが収容する人口Ｕｋを示す。エッジノードｓからエッジノードｄに流れるトラヒック量Ｔｓｄは、両端のエッジノードの人口の積に比例させ、下記（１１）式で求める値とした。但し、Ｔはネットワーク全体のトラヒック量であり、ここでは、Ｔ=１０Ｔｂｐｓとした。
【００２５】
【数６】
【００２６】
１リンク障害に対して迂回路を確保でき、全エッジノード間の接続性を確保できる初期トポロジとしてループ型トポロジを考え、図２の実線で示すリンク設置可能位置には必ずリンクを配置した。
ループが経由するコアノード設置可能位置の次数は２となり交換機能が不要であることから、これら設置可能位置にコアノードを配置する必要はない。
初期トポロジで採用されたリンクを除くと、１７本のリンク設置可能位置が残るため２１７個の物理トポロジを構成可能であるが、次数が１となるコアノードや未使用リンクが存在するトポロジを候補から除外した結果、８３，８６８個の侯補トポロジが得られた。なお、これらの候補トポロジを得るのに要した計算時間は７５秒程度であった。
【００２７】
［平均順位法の適用結果］
平均順位（ＡＲ）の算出に要する計算量は僅かであり、８３，８６８個の全ての侯補トポロジを対象に平均順位（ＡＲ）を算出しても要した時間は１秒未満であった。
平均順位（ＡＲ）が小さなトポロジほど望ましいトポロジであるため、候補トポロジの最終評価順位は平均順位（ＡＲ）の小さな順となる。
図３は、８３，８６８個の候補トポロジを対象に、前述の（５）式より算出した平均順位（ＡＲ）を最終評価の順にプロットしたグラフである。
８３，８６８個の候補トポロジにおける、平均順位（ＡＲ）の最小値、最大値、平均は各々、３８１３．２５、７５２９５．２５、３９９１５．０であった。
４つの評価尺度のいくつかは相反するため、全ての評価尺度が非常に優れた候補トポロジや、反対に全ての評価尺度が非常に悪い候補トポロジは存在しない。そのため、平均順位（ＡＲ）の最小値は１より大きく、平均順位（ＡＲ）の最大値は候補トポロジ数８３，８６８より小さな値となっている。
【００２８】
大多数の候補トポロジの平均順位（ＡＲ）は２０，０００〜６０，０００の範囲に存在し、平均順位（ＡＲ）が最小値（３６１３．２５）に近いトポロジは少数に限定されることがわかる。
このことは、これら平均順位（ＡＲ）が小さな少数のトポロジのみに選択候補を絞ることにより、少数の優れた網トポロジを選択できることを意味する。
図４は、図３に示すグラフの平均順位（ＡＲ）が小さな上位１０位のトポロジについて、平均順位（ＡＲ）、４つの評価尺度の値と、それらの全候補トポロジ中の順位をまとめた表である。また、これら上位１０のトポロジを図５に示す。４つの全ての評価尺度が良好なバランスのいい侯補トポロジが、平均順位法では高く評価されることがわかる。
【００２９】
図６は、平均順位（ＡＲ）の小さい最終評価順位の高い候補トポロジの順に、４つの評価尺度を各々プロットしたグラフである。１つの点が１つの候補トポロジに対応する。但し、平均順位（ＡＲ）が１０位以内の侯補トポロジについては大きな点でプロットしている。
全ての評価尺度が良好な候補トポロジが、平均順位法では上位に評価されることが確認できる。また、Ｖ１、Ｖ２、およびＶ４の評価尺度が極めて良好な物理トポロジの平均順位（ＡＲ）は大きく、平均順位法での評価は低いことが確認できる。
このことは、単一の評価尺度のみを考慮して綱トポロジ設計を行った場合、他の評価尺度が悪化することを意味し、平均順位法の有効性が確認できる。
以上説明したように、本実施例によれば、コアノードやリンクが設置可能な場所と、エッジノード、エッジノード間の交流トラヒック行列が与えられているときに、複数の評価尺度を考慮した上で最適な綱トポロジを、平均順位法により評価して求めることができる。
以上、本発明者によってなされた発明を、前記実施例に基づき具体的に説明したが、本発明は、前記実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００３０】
【図１】本発明の実施例の平均順位を用いた網トポロジ設計装置の概略構成を示すブロック図である。
【図２】本発明の実施例において、評価に用いたネットワークモデルを示す図である。
【図３】図２に示すネットワークモデルから生成された候補トポロジの最終評価順位を示すグラフである。
【図４】図３に示すグラフの平均順位（ＡＲ）が小さな上位１０位のトポロジについて、平均順位（ＡＲ）、４つの評価尺度の値と、それらの全候補トポロジ中の順位をまとめた表である。
【図５】図３に示すグラフの上位１０のトポロジを示す図である。
【図６】図２に示すネットワークモデルから生成された候補トポロジの最終評価順位の順でプロットした各評価尺度値を示すグラフである。
【符号の説明】
【００３１】
１０１ トポロジ情報・デマンド行列入力装置
１０２ 初期トポロジ生成装置
１０３ トポロジ候補生成装置
１０４ 平均順位算出装置
１０５ 最適トポロジ出力装置
【特許請求の範囲】
【請求項１】
ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計方法であって、
各々のトポロジ候補に対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、
評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断することを特徴とする網トポロジ設計方法。
【請求項２】
同時に考慮する評価尺度は、総ノード数、総リンク長、各パスの長さとトラヒック量の積を全パスについて足し合わせたもの、最大負荷リンクのトラヒック量の四つを用いることを特徴とする請求項１に記載の網トポロジ設計方法。
【請求項３】
ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計装置であって、
エッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置が入力されるトポロジ情報・デマンド行列入力装置と、
前記トポロジ情報・デマンド行列入力装置により入力されたエッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置に基づき、初期トポロジを生成する初期トポロジ生成装置と、
前記初期トポロジ生成装置により生成された初期トポロジに対して、いくつかのリンクとコアノードを追加して複数の候補トポロジを生成するトポロジ候補生成装置と、
前記トポロジ候補生成装置により生成された複数の候補トポロジに対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、各評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断する平均順位算出装置と、
前記平均順位算出装置での評価結果に基づき最適トポロジの集合を出力する最適トポロジ出力装置とを有することを特徴とする網トポロジ設計装置。
【請求項１】
ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計方法であって、
各々のトポロジ候補に対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、
評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断することを特徴とする網トポロジ設計方法。
【請求項２】
同時に考慮する評価尺度は、総ノード数、総リンク長、各パスの長さとトラヒック量の積を全パスについて足し合わせたもの、最大負荷リンクのトラヒック量の四つを用いることを特徴とする請求項１に記載の網トポロジ設計方法。
【請求項３】
ユーザを収容するエッジノードの集合と、中継機能のみを有するコアノードの候補の集合と、それらを結ぶリンクの候補の集合とが与えられたときに、複数の評価尺度を同時に考慮しながら、使用するコアノードとリンクの集合を選択する網トポロジ設計装置であって、
エッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置が入力されるトポロジ情報・デマンド行列入力装置と、
前記トポロジ情報・デマンド行列入力装置により入力されたエッジノードの位置、コアノードの設置可能位置、リンクの設置可能位置に基づき、初期トポロジを生成する初期トポロジ生成装置と、
前記初期トポロジ生成装置により生成された初期トポロジに対して、いくつかのリンクとコアノードを追加して複数の候補トポロジを生成するトポロジ候補生成装置と、
前記トポロジ候補生成装置により生成された複数の候補トポロジに対して、同時に考慮する評価尺度ごとに全候補中の順位を計算し、各評価尺度ごとに得られた順位の平均値を計算し、平均順位で候補間の優劣を判断する平均順位算出装置と、
前記平均順位算出装置での評価結果に基づき最適トポロジの集合を出力する最適トポロジ出力装置とを有することを特徴とする網トポロジ設計装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２００７−３３６０２１（Ｐ２００７−３３６０２１Ａ）
【公開日】平成１９年１２月２７日（２００７．１２．２７）
【国際特許分類】
【出願番号】特願２００６−１６２９７６（Ｐ２００６−１６２９７６）
【出願日】平成１８年６月１３日（２００６．６．１３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成１８年度 総務省 「次世代バックボーンに関する研究開発」、産業活力再生特別措置法第３０条の適用を受ける特許出願）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成１９年１２月２７日（２００７．１２．２７）
【国際特許分類】
【出願日】平成１８年６月１３日（２００６．６．１３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成１８年度 総務省 「次世代バックボーンに関する研究開発」、産業活力再生特別措置法第３０条の適用を受ける特許出願）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]