(57)【要約】      （修正有）【課題】ネットワークのトポロジ設計における多様な候補トポロジ集合の、現実的な時間内での生成を、効率的に行う。【解決手段】入力処理部は、複数の評価尺度情報と全ノードの位置情報およびノード間のトラヒック量比率情報ならびに単一リンク障害時の接続性喪失トラヒック量比率の許容上限値を記憶装置に格納し、マルチエージェントシステム実行処理部は、複数の評価尺度ごとにエージェントを構成し、各エージェントが、対応する評価尺度の最大化を目的に自律的に行動するマルチエージェントシステムをシミュレートすることにより、全ノードの位置情報とノード間のトラヒック量比率情報を用いて、正常時に全ノード間の接続性を確保できることおよび任意の単一リンク障害時に接続性が喪失するトラヒック量の比率の平均が許容上限値以下に収まることを制約条件に、予め定められた個数の候補トポロジ集合を生成し、候補トポロジ出力処理部を介して出力する。【選択図】図１
2011091751.tif 000002
【特許請求の範囲】
【請求項１】
全ノードの位置が与えられ、任意のノード間にリンクを設置可能なネットワークにおける、予め定められた複数の評価尺度を満足するトポロジを、コンピュータ装置によって生成する方法であって、
上記コンピュータ装置は、プログラムされたコンピュータ処理を実行する手段として、入力処理手段とマルチエージェントシステム実行処理手段および候補トポロジ出力処理手段を有し、
上記入力処理手段は、
入力装置を介して予め入力される上記複数の評価尺度情報と上記全ノードの位置情報およびノード間のトラヒック量比率情報ならびに単一リンク障害時の接続性喪失トラヒック量比率の許容上限値を入力して記憶装置に格納する手順を実行し、
上記マルチエージェントシステム実行処理手段は、
生成するトポロジを環境とし、上記複数の評価尺度ごとにエージェントを構成し、各エージェントが、対応する評価尺度の最大化を目的に自律的に行動するマルチエージェントシステムをシミュレートすることにより、
上記全ノードの位置情報と上記ノード間のトラヒック量比率情報を用いて、正常時に全ノード間の接続性を確保できることおよび上記任意の単一リンク障害時に接続性が喪失するトラヒック量の比率の平均が上記許容上限値以下に収まることを制約条件に、
予め定められた個数の候補トポロジ集合を生成する手順を実行し、
上記候補トポロジ出力処理手段は、
上記マルチエージェントシステム実行処理手段が生成した候補トポロジを出力する手順を実行する
ことを特徴とするマルチエージェントシステムを用いた候補トポロジ生成方法。
【請求項２】
請求項１に記載のマルチエージェントシステムを用いた候補トポロジ生成方法であって、
上記マルチエージェントシステム実行処理手段の各エージェントは、
現在の環境としてのトポロジを構成するリンクの任意の１本を削除することで、もしくは、リンクが存在しない任意の一つのノードに対してリンクを追加することで、現在の環境に対して影響を与えるよう行動する
ことを特徴とするマルチエージェントシステムを用いた候補トポロジ生成方法。
【請求項３】
請求項１もしくは請求項２のいずれかに記載のマルチエージェントシステムを用いた候補トポロジ生成方法であって、
上記コンピュータ装置は、プログラムされたコンピュータ処理を実行する手段として、初期トポロジ生成処理手段を有し、
上記入力処理手段は、
上記評価尺度として、リンク距離を当該リンクの両端のノード間に発生するトラヒック量比率で除した値で定義されるリンクコストを上記記憶装置に格納する手順を実行し、
上記初期トポロジ生成処理手段は、
上記正常時の全ノード間の接続制御確保を条件に、上記全ノードの位置情報を用いて、上記リンクコストの総和を最小とするトポロジである最小木を生成し、生成した最小木を構成する各ノードにリンクを設置する手順と、
生成した最小木における各ノードに、任意の上記単一リンク障害時の接続性喪失トラヒック量比率の平均が上記許容上限値以下に収まるよう最も少数のリンクを付加したトポロジを生成する手順とを実行し、
上記マルチエージェントシステム実行処理手段は、
上記初期トポロジ生成処理手段が生成したトポロジを、上記環境の初期状態として用いる
ことを特徴とするマルチエージェントシステムを用いた候補トポロジ生成方法。
【請求項４】
請求項１から請求項３のいずれかに記載のマルチエージェントシステムを用いた候補トポロジ生成方法であって、
上記マルチエージェントシステム実行処理手段は、
各手番において行動するエージェントを、予め各エージェント毎に定めた確率に従いランダムに選択し、
選択したエージェントが、上記制約条件を満たし且つ未出現のトポロジを作る行動をとることができない場合には、他のエージェントを選択して行動させ、
いずれのエージェントも上記制約条件を満たし且つ未出現のトポロジを作る行動をとることができない場合には、既に出現したトポロジをランダムに選択し、選択したトポロジから再度、手番を進める
ことを特徴とするマルチエージェントシステムを用いた候補トポロジ生成方法。
【請求項５】
請求項４に記載のマルチエージェントシステムを用いた候補トポロジ生成方法であって、
上記マルチエージェントシステム実行処理手段は、
上記選択したエージェントが行動を選択する際に、出現するトポロジが既に出現したトポロジと一致しないか否かの判定を、Bloomfilterを用いて行う
ことを特徴とするマルチエージェントシステムを用いた候補トポロジ生成方法。
【請求項６】
請求項１から請求項５のいずれかに記載のマルチエージェントシステムを用いた候補トポロジ生成方法であって、
上記入力処理手段は、
上記評価尺度情報として、総リンク長と、トラヒック量比率で重み付けた平均ホップ長を入力して記憶装置に格納し、
上記マルチエージェントシステム実行処理手段は、
上記総リンク長に第１のエージェントを、上記平均ホップ長に第２のエージェントを対応付け、
上記第１のエージェントは、上記総リンク長の最大化を目的に自律的に行動し、
上記第２のエージェントは、上記平均ホップ長の最大化を目的に自律的に行動する
ことを特徴とするマルチエージェントシステムを用いた候補トポロジ生成方法。
【請求項７】
請求項６に記載のマルチエージェントシステムを用いた候補トポロジ生成方法であって、
上記マルチエージェントシステム実行処理手段は、
上記トラヒック量比率で重み付けた平均ホップ長に対応付けた上記第２のエージェントの行動を選択する際、人口比率が大きいノード間を優先する
ことを特徴とするマルチエージェントシステムを用いた候補トポロジ生成方法。
【請求項８】
コンピュータに、請求項１から請求項７に記載のマルチエージェントシステムを用いた候補トポロジ生成方法における各手順を実行させるプログラム。
【請求項９】
全ノードの位置が与えられ、任意のノード間にリンクを設置可能なネットワークにおける、予め定められた複数の評価尺度を満足するトポロジを、コンピュータ装置によって生成する方法であって、
上記コンピュータ装置は、プログラムされたコンピュータ処理を実行する手段として、トポロジ生成処理手段を有し、
該トポロジ生成処理手段は、
請求項１から請求項７のいずれかに記載のマルチエージェントシステムを用いた候補トポロジ生成方法における上記マルチエージェントシステム実行処理手段が生成し上記候補トポロジ出力処理手段が出力する候補トポロジを入力する手順と、
該候補トポロジをボトム層、上記予め定められた複数の評価尺度を中央の層、生成する上記トポロジをトップの階層とするAHP（Analytic Hierarchy Process）により、上記予め定められた複数の評価尺度を同時に考慮した上記候補トポロジの評価を行い、各評価尺度に対して予め定められた重要度に応じたトポロジを選択する手順とを実行する
ことを特徴とするトポロジ生成方法。
【請求項１０】
全ノードの位置が与えられ、任意のノード間にリンクを設置可能なネットワークにおける、予め定められた複数の評価尺度を満足するトポロジを、コンピュータ処理によって生成するシステムであって、
該システムは、プログラムされたコンピュータ処理を実行する手段として、入力処理手段と初期トポロジ生成処理手段およびマルチエージェントシステム実行処理手段と候補トポロジ出力処理手段ならびにトポロジ生成処理手段を有し、
上記入力処理手段は、
入力装置を介して予め入力される上記複数の評価尺度情報と上記全ノードの位置情報およびノード間のトラヒック量比率情報ならびに単一リンク障害時の接続性喪失トラヒック量比率の許容上限値を入力して記憶装置に格納すると共に、
上記評価尺度として、リンク距離を当該リンクの両端のノード間に発生するトラヒック量比率で除した値で定義されるリンクコストを上記記憶装置に格納し、
上記初期トポロジ生成処理手段は、
正常時に全ノード間の接続性を確保できることを条件に、上記全ノードの位置情報を用いて、上記リンクコストの総和を最小とするトポロジである最小木を生成して、生成した最小木を構成する各ノードにリンクを設置すると共に、生成した最小木における各ノードに、任意の上記単一リンク障害時の接続性喪失トラヒック量比率の平均が上記許容上限値以下に収まるよう最も少数のリンクを付加したトポロジを生成し、
上記マルチエージェントシステム実行処理手段は、
生成するトポロジを環境とし、上記リンクコストを含む複数の評価尺度ごとにエージェントを構成し、各エージェントが、対応する評価尺度の最大化を目的に自律的に行動するマルチエージェントシステムをシミュレートすることにより、
上記全ノードの位置情報と上記ノード間のトラヒック量比率情報を用いて、正常時に全ノード間の接続性を確保できることおよび上記任意の単一リンク障害時に接続性が喪失するトラヒック量の比率の平均が上記許容上限値以下に収まることを制約条件に、
予め定められた個数の候補トポロジ集合を生成し、
上記候補トポロジ出力処理手段は、
上記マルチエージェントシステム実行処理手段が生成した候補トポロジを出力し、
上記トポロジ生成処理手段は、
上記マルチエージェントシステム実行処理手段が生成し上記候補トポロジ出力処理手段が出力する候補トポロジを入力し、
該候補トポロジをボトム層、
上記予め定められた複数の評価尺度を中央の層、
生成する上記トポロジをトップの階層とするAHP（Analytic Hierarchy Process）により、
上記予め定められた複数の評価尺度を同時に考慮した上記候補トポロジの評価を行い、
各評価尺度に対して予め定められた重要度に応じたトポロジを選択する
ことを特徴とするトポロジ生成システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークのトポロジ設計技術に係り、特に、大規模ネットワークに対する候補トポロジの設計において、全ノードの位置が与えられ、任意のノード間にリンクを設置することが可能である場合に、正常時における全ノード間の接続性を確保すること、および、任意の単一リンク障害時に接続性が喪失するトラヒック量の比率の平均が任意に定められた上限値以下に収まること、を制約条件に、現実的な時間内で、候補トポロジ集合を生成することで、網トポロジの効率的な設計を可能とするのに好適な技術に関するものである。
【背景技術】
【０００２】
光ファイバやルータといったネットワーク（NW）の資源を管理・運営している通信事業者やISP（Internet Service Provider）にとって、NWトポロジ設計は重要な問題である。NWトポロジは、ノードやリンクの設備コスト、NWの管理・保守コスト、障害に対する信頼性、さらに、伝送遅延品質やスループット等のユーザ品質に大きな影響を与える。
【０００３】
例えば、ユーザ品質の観点からは、経由ノードでの輻輳を回避し、経路の総距離が短いことが伝送遅延を抑える意味で望ましく、また、設備コストや管理・保守コストを抑えるためには、設置ノード数やリンク数を減らすことが望ましい。しかし、設置ノード数やリンク数を減らすと、ユーザ品質が劣化し、また、障害時にノード間の接続性が喪失する可能性が高まり信頼性が低下する。
【０００４】
このように、NWトポロジを設計する際には、パスの平均長、NWコスト、信頼性といった、それぞれ単位が異なり、しかも互いに相反する複数の評価尺度を同時に考慮する必要がある。
【０００５】
このような、複数の評価尺度を同時に考慮した、合理的な意思決定を行う技術としてAHP（Analytic Hierarchy Process）が知られている。AHPでは、関連する要素を階層構造によって把握し、評価尺度の重要度といった定性的な尺度を一対比較により定量化し、合理的な意思決定を可能とする。
【０００６】
そこで、本願発明者は、AHPを網トポロジ評価へ適用した技術を、特許文献１において提案している。この技術では、AHPを用いることで、以下のように、設計者の主観的な評価尺度に対する重要度に応じた適切な網トポロジ設計が可能となる。
【０００７】
通常、意思決定においては、「問題P」、「評価尺度V」、「代替案A」の三種類の要素が存在する。AHPでは、これら要素を、図１０に示すような階層構造で把握する。
【０００８】
ただし、互いに関連のある要素間を直線で結び（図１０では便宜上、一部のみ示している）、評価尺度Vは、複数の階層構造（V１，V２，…）をとることも可能である。図１０では２階層構造を示している。
【０００９】
そして、各要素間の関連性の強さ（重み）を算出し、最終的に、各代替案AiのスコアSiを導出する。
【００１０】
評価尺度Vの問題Pに対する重みを計算する場合、定量的な評価値がもともと存在しないため、何らかの方法で定量化する必要がある。AHPでは、以下に説明するように、同一の階層に属する要素集合に対して、全ての要素間の重要度を一対比較することにより定量化を図る。
【００１１】
まず、階層cに属する要素Xiと要素Xjに対して、図１１に示す値を、要素Xiの要素Xjに対する相対的な重要度ai,jに設定する。要素Xiの本来の重みをwi、要素Xjの本来の重みをwjとすると、理想的には、ai,j＝wi/wjという関係を満たす。
【００１２】
重要度ai,jを要素にもつ一対比較行列をAとし、各要素の重みwiを要素にもつベクトルwを、行列Aの右側から乗じると、Aw＝nwが成立する。ただしnは要素の数である。よって、重みベクトルは行列Aの固有ベクトルであり、nは固有値（最大固有値）となる。
【００１３】
実際には、一対比較を完全な整合性を持って行うことは困難なため、行列Aの整合性を判断する必要がある。すなわち、行列Aの最大固有値をλmaxとすると、λmax≧nとなる。そこで、式「Ｃ．Ｉ．＝（λmax−n）/（n−１）」で定義される整合度Ｃ．Ｉ．を用いて整合性を判断する。
【００１４】
整合性が増すほど、行列Aの最大固有値λmaxは減少し、完全に整合性がとれているときには、行列Aの最大固有値λmax＝nとなるので、整合度Ｃ．Ｉ．は小さなほど整合性が高く、一般的には、Ｃ．Ｉ．が０．１以下であれば合格とする。
【００１５】
階層cにおける要素iの、階層c-1の要素jに対する重みをwijcとする。階層c-1の要素のうち、階層cの要素Vicが関係する要素の集合をΦicとすると、階層cの要素Vicの問題Pに対するスコアSicは、下記の数１に示す式（１）により算出できる。
【００１６】
【数１】
2011091751.tif 000003
【００１７】
階層１においては、問題Pに対する各要素の重みがそのままスコアSi1となる。
【００１８】
以下、階層ｃ＝２，３，…の順にスコアSicを算出することができ、最終的に、各代替案AiのスコアSiを得る。そして、スコアが最大の代替案が最適な選択肢となる。
【００１９】
このようなAHPを、NWトポロジ設計に適用すると、トップの階層（階層０）には解くべき問題P（この場合、「最適なNWの選択」）が、中央の階層（階層１）には評価尺度Viが、そしてボトム（階層２）には候補トポロジが並ぶ。
【００２０】
階層１（評価尺度）の問題P（最適なNWの選択）に対するスコア（重み）は、一対比較により求めることができる。また、階層２（候補トポロジ）の階層１の各要素（評価尺度）に対するスコア（重み）は、評価尺度が定量的な評価値をもつ場合、一対比較による評価を行う必要はない。
【００２１】
そこで、AHPを用いてトポロジを評価する際には、事前に候補トポロジ集合を生成する必要がある。以下、候補トポロジ集合の生成について説明する。
【００２２】
ここでは、NWの一般化した構成要素としてノードとリンクを考える。また、ノードの位置とノード間の交流トラヒック行列は予め与えられており、全てのノード間にリンクの設置が可能とする。
【００２３】
すなわち、ノード数をNとすると、リンクの設置可能な位置数Lは、「L＝N（N−１）/２」となる。ただし、設置リンクは双方向であるとし、両端のノード間の両方向にトラヒックが流れることを想定する。
【００２４】
これらL本のリンク設置可能位置に対してリンク設置箇所を選択することで、候補トポロジが構成されるため、生成可能な候補トポロジの全数は２Lとなる。ただし、NWトポロジには全ノード間の接続性が求められるため、全ノードとリンクが正常に稼働している正常時において、全ノード間の接続性を満たすトポロジのみを候補として生成する。
【００２５】
また、日常的に様々なリンクで障害が発生しており、障害時にも大部分のトラヒックに対して接続性を維持する高い信頼性が求められる。例えば、IPバックボーンにおいて、メインテナンスに起因するものを除いた意図しない障害の約７０％は単独リンク障害（SLF:single Link Failure）である。
【００２６】
そこで、NW上のあるリンクeのSLF時に接続性が喪失するノードペアの集合をPｅとするとき、SLF時に接続性が喪失するトラヒック量比率の平均値ξを、次の数２に示す式（２）で定義する。
【００２７】
【数２】
2011091751.tif 000004
【００２８】
ただし、式（２）において、Mはトポロジを構成するリンク数、Ｅはトポロジを構成するリンクの集合、PｅはリンクeのSLF時に接続性が喪失するノードペアの集合、rijはノードiとノードj間の交流トラヒック比率（ノードiを発、ノードjを着とするトラヒック量のNW全体のトラヒック量に対する比率）である。
【００２９】
そして、ξ（SLF時に接続性が喪失するトラヒック量比率の平均値）が任意に与えた設計上限値αξ以下となるトポロジのみを候補として生成する。
【００３０】
ここでは、交流トラヒック比率rijを、両端のノードi，jの人口比の積に設定する。すなわち、ノードkの人口をUk、人口の総和をU、ノードkの人口比率をrk（＝Uk/U）とすると、rij＝rirjとなる。以後、正常時の全ノード間の接続性と、ξ≦αξ（すなわち、SLF時に接続性が喪失するトラヒック量比率の平均値≦設計上限値）という候補トポロジが満たすべき二つの制約条件を、制約条件Cと表記する。
【００３１】
AHPを用いたNWトポロジ評価においては、任意の評価尺度を同時に考慮できる。ただし、大規模NWに対して現実的な時間でトポロジ候補集合を生成するためには、考慮する評価尺度に応じて適切な技術を考える必要がある。
【００３２】
ここでは、（i）総リンク長ζと、（ii）トラヒック量比率で重み付けた平均ホップ長ε、の２つを評価尺度として用いる場合を想定する。
【００３３】
総リンク長ζは、コストに関係する評価尺度（V１）であり、リンクeの距離dｅを用いて、V１＝ζ＝Σe∈Edｅで定義する。
【００３４】
また、平均ホップ長εは、ユーザ品質に関係する評価尺度であり、Vをノード集合、hijをノードiとノードjの間の最短ホップ長とすると、V２＝ε＝Σi,j∈Vrijhijで定義する。ただし、パケットの転送経路としてOSPF（Open Shortest Path First）による最短ホップ経路を想定する。
【００３５】
両評価尺度（V１＝ζ，V２＝ε）とも値が小さいほど望ましいが、一般的に、トポロジを構成するリンクの数が多いほど、総リンク長ζは増加する反面、ノード間の経路設定の多様性が向上するため、平均ホップ長εは減少する。そのため、総リンク長ζと平均ホップ長εには負の相関性があり、両者とも最小値に近い理想的なトポロジを構築することは困難であるため、AHPを用いたトポロジ評価が有効となる。
【００３６】
しかし、このようなAHPを用いたトポロジ評価において、候補トポロジを生成する際の所要計算時間は、リンク設置候補位置数xに対して２xに比例して増加するため、大規模ネットワークに対する候補トポロジを現実的な時間で生成するためには、全設置可能位置数Lと比較して、リンク設置候補位置数xを極めて小さな値に抑える必要がある。
【００３７】
そこで、本願発明者は、特願２００９−０５０２７１号において、接続性の要件を満たす最も少数のリンク設置位置には常にリンクを設置し、さらに、リンク設置可能位置数を少数に限定する技術を検討した。
【００３８】
以下、その技術を説明する。
全ノード間の接続性を満たしコストの総和が最小となるトポロジTaは、最小木（MST:Minimum Spanning Tree）であることから、Primのアルゴリズムを用いて当該トポロジTaを生成する。ただし、ノードij間のリンクコストをdij/rijとする（dijはノードij間の距離、rijはノードij間の交流トラヒック比率）。
【００３９】
そして、このトポロジTaに含まれるリンクの数xa＝N−１本を除いたL−xa本の各リンク設置可能位置の各々に対して、１本だけリンクを追加したトポロジを対象に、ξ（SLF時に接続性が喪失するトラヒック量比率の平均値）を算出し、ξが最小となるリンク設置可能位置に１本だけリンクを追加する。
【００４０】
このような処理を、ξ≦αξ（αξ：予め定められた評価基準の１つである要求水準）が満たされるまで反復し、得られたトポロジをTbとする。
【００４１】
生成する全候補トポロジにおいて、このトポロジTbを構成するリンク数xbのリンク設置位置には必ずリンクを設置する。
【００４２】
このようにトポロジTbを構成する際には、可能な限り少数の箇所にのみリンクを設置しているため、総リンク長（評価尺度V１）が良好なトポロジが生成されるが、平均ホップ長（評価尺度V２）については考慮していない。
【００４３】
そこで、以下のように、トポロジTbから、さらに、リンク設置候補位置を追加することで、平均ホップ長（評価尺度V２）に多様性をもつ候補トポロジ集合を生成する。
【００４４】
トポロジTbに対してリンクの追加を許容するリンク設置位置の数をxとし、これらx本のリンク設置可能位置の集合をＥcとする。
【００４５】
このリンク設置可能位置の集合Ｅcの任意の位置にリンクを設置する全ての組合せによって候補トポロジを生成するため、トポロジTbを構成するリンク位置には、必ず、リンクを有する２x個の候補トポロジ集合Tdが生成される。
【００４６】
追加を許容するリンク本数xを増加させるほど、候補トポロジの多様性が増し、より柔軟なトポロジ設計が可能となるが、候補トポロジ生成に要する時間は爆発的に増大する。
【００４７】
トポロジTbに対して多数のリンクを追加するほど、重み付け平均ホップ長V2は単調に減少するため、生成される候補トポロジにおける重み付け平均ホップ長V2の最大値は、トポロジTbそのものの重み付け平均ホップ長εとなり、リンク設置可能位置の集合Ｅcとは無関係となる。
【００４８】
一方で、平均ホップ長V2の最小値は、リンク設置可能位置の集合Ｅcに依存し、平均ホップ長V2の最小値が小さいほど、平均ホップ長V2の多様性が高い、優れた候補トポロジ集合であると言える。
【００４９】
そのため、可能な限り少数のリンク追加で（候補トポロジ生成に要する時間を少なくし）、生成される候補トポロジ集合における平均ホップ長V2の最小値が小さくなるよう（平均ホップ長V2の多様性が高い、優れた候補トポロジ集合となるよう）、リンク設置可能位置の集合Ｅcを選択することが望ましい。
【００５０】
このように、２x個の候補トポロジ集合Tdが生成されるため、x（リンク設置位置の数）を増加させるほど候補トポロジの多様性が増し、より柔軟なトポロジ設計が可能となるが、候補トポロジ生成に要する時間は２xに比例して増加する。
【００５１】
平均ホップ長V２の最小値は、リンク設置可能位置の集合Ｅcに依存し、平均ホップ長V２の最小値が小さいほど平均ホップ長V２の多様性が高い。そのため、任意のリンク数xに対して、生成される候補トポロジ集合における平均ホップ長V２の最小値が最小となるよう、Ｅc（リンク設置可能位置の集合）を選択する。
【００５２】
すなわち、初期状態では、リンク設置可能位置の集合Ｅcを空集合とし、まず、トポロジTbを構成するxb本のリンクを除いた「全リンク設置可能箇所数L−xb」のリンク設置可能位置の各々に対して、１本だけリンクを追加したときの、重み付けた平均ホップ長εを計算し、このεが最小となるリンク設置可能位置e１を、集合Ｅcに追加する。
【００５３】
さらに、トポロジTbにリンク設置可能位置e１を追加したトポロジに対して、残る「L−xb−1」のリンク設置可能位置の各々に対して１本だけリンクを追加したときの、重み付けた平均ホップ長εを計算し、やはり、この重み付けた平均ホップ長εが最小となるリンク設置可能位置e2を、リンク設置可能位置の集合Ｅcに追加する。
【００５４】
以上の処理を、任意に与えたリンク数x回だけ反復することにより、任意に与えたリンク数xのリンク設置可能位置を追加するという条件で、平均ホップ長V２の最小値を最小化する候補トポロジ集合を生成するリンク設置可能位置集合Ｅcを得ることができる。
【先行技術文献】
【特許文献】
【００５５】
【特許文献１】特開２００８−１６５４６８号公報
【発明の概要】
【発明が解決しようとする課題】
【００５６】
網トポロジの設計においては、コストを重視する場合は、候補トポロジ集合における総リンク長V１（コスト）の平均値が小さく、平均ホップ長V２（品質）の変動係数が大きいことが望ましい。
【００５７】
しかし、上述の技術では、リンク設置可能位置数xに対して２x個の候補が生成されるため、２のべき乗の粒度でのみ候補数を設定しなければならず、生成候補数をパラメタKにより直接、任意の値に設定することができず、候補トポロジ集合における総リンク長V１（コスト）の平均値を小さくすることができない。
【００５８】
また、上述の技術では、リンク設置可能位置数xの増加に伴い、リンクを設置可能な候補位置の数が単調に増加する。その結果、生成される候補集合の平均ホップ長V２の平均値は、生成候補数に対してほぼ一定であるのに対して、総リンク長V１の平均値は、生成候補数の増加に伴い大きく増加する。
【００５９】
このように、上述の技術では、生成する候補数を少数に抑え、かつ、特定のトポロジ形状に偏ることなく、多様なトポロジ候補を生成することができない。
【００６０】
解決しようとする問題点は、従来の技術では、生成する候補トポロジ集合の総リンク長に関する多様性が非常に低く、生成する候補トポロジ数を少なくした場合には、コストを重視する場合および品質を重視する場合のいずれにおいても、多様な候補トポロジの生成ができず、生成候補数を非常に多くした場合に有効なものであり、候補トポロジ集合の生成に非常に多くの時間を要してしまう点である。
【００６１】
本発明の目的は、これら従来技術の課題を解決し、ネットワークのトポロジ設計における多様な候補トポロジ集合の、現実的な時間内での生成を、効率的に行うことを可能とすることである。
【課題を解決するための手段】
【００６２】
上記目的を達成するため、本発明では、（１）全ノードの位置が与えられ、任意のノード間にリンクを設置することが可能である場合に、正常時の全ノード間の接続性確保と、任意の単一リンク障害時に接続性が喪失するトラヒック量の比率の平均が任意に定めた上限値以下に収まることを制約条件に、現実的な時間内で候補トポロジ集合を生成するため、マルチエージェントシステムを用いることを特徴とする。（２）すなわち、構成可能なトポロジを環境とし、トポロジを評価する際の各評価尺度ごとにエージェントを構成し、各エージェントは、対応する評価尺度の最大化を目的に自律的に行動するマルチエージェントシステムを計算機上でシミュレートすることを特徴とする。（３）その際、現在の環境を構成するリンクの任意の１本を削除するか、もしくはリンクが存在しない任意の一つのリンク設置可能位置に対してリンクを追加することで、環境に対して影響を与えることを各エージェントの行動とすることを特徴とする。（４）また、環境（トポロジ）の初期状態として、各リンクのコストを、リンク距離を両端のノード間に発生するトラヒック量比率で除した値で定義したときに構成される最小木に、単一リンク障害時の接続性喪失トラヒック量比率の平均値が許容上限値以下に収まるよう最も少数のリンクを追加したトポロジとすることを特徴とする。（５）また、各手番において行動するエージェントをランダムに、予め定めた確率に従い選択し、選択したエージェントが、制約条件を満たし且つ未出現の状態を作る行動をとることができない場合には他のエージェントに行動させ、いずれのエージェントも当該行動をとれない場合には、既に出現した状態をランダムに選択し、その状態から再度、手番を進めることを特徴とする。（６）また、エージェントが行動を選択する際に、出現する状態が既に出現した状態と一致しないか否かの判定を、Bloomfilterを用いて行うことを特徴とする。（７）また、各トポロジ候補を評価する尺度として、総リンク長とトラヒック量比率で重み付けた平均ホップ長を用いることを特徴とする。（８）また、トラヒック量比率で重み付けた平均ホップ長に対応するエージェントの行動を選択する際には、人口比率が大きいノード間を優先的に行うことを特徴とする。（９）また、生成した候補トポロジをボトム層、予め定められた複数の評価尺度を中央の層、生成するトポロジをトップの階層とするAHP（Analytic Hierarchy Process）により、予め定められた複数の評価尺度を同時に考慮した候補トポロジの評価を行い、各評価尺度に対して予め定められた重要度に応じたトポロジを選択することを特徴とする。
【発明の効果】
【００６３】
本発明によれば、全ノードの位置が与えられ、任意のノード間にリンクを設置することが可能である場合に、正常時の全ノード間の接続性確保と、任意の単一リンク障害時に接続性が喪失するトラヒック量の比率の平均が、任意に定めた上限値以下に収まることを制約条件に、現実的な時間内で候補トポロジ集合を生成でき、網トポロジの効率的な設計が可能となる。
【図面の簡単な説明】
【００６４】
【図１】本発明に係るトポロジ生成システムの構成例を示すブロック図である。
【図２】本発明に係る候補トポロジ生成方法によりリンクを追加した場合の平均ホップ長εと当該リンクの両端ノードの人口比率積との相関係数を示す説明図である。
【図３】本発明に係る候補トポロジ生成方法におけるエージェントの選択確率がＭＡＳに及ぼす第１の影響例を示す説明図である。
【図４】本発明に係る候補トポロジ生成方法におけるエージェントの選択確率がＭＡＳに及ぼす第２の影響例を示す説明図である。
【図５】本発明に係る候補トポロジ生成方法により生成した候補トポロジの有効性の第１の例を示す説明図である。
【図６】本発明に係る候補トポロジ生成方法により生成した候補トポロジの有効性の第２の例を示す説明図である。
【図７】本発明に係る候補トポロジ生成方法と既存技術による候補トポロジ生成方法との第１の比較例を示す説明図である。
【図８】本発明に係る候補トポロジ生成方法と既存技術による候補トポロジ生成方法との第２の比較例を示す説明図である。
【図９】本発明に係る候補トポロジ生成方法と既存技術による候補トポロジ生成方法との第３の比較例を示す説明図である。
【図１０】AHPの階層構造例を示す説明図である。
【図１１】AHPで適用する一致比較値の例を示す説明図である。
【図１２】本発明の評価に用いた各ネットワークの基本特性の具体例を示す説明図である。
【図１３】本発明に係るマルチエージェントシステムを用いた候補トポロジ生成方法における処理動作例を示すフローチャートである。
【発明を実施するための形態】
【００６５】
以下、図を用いて本発明を実施するための形態例を説明する。図１においては、本発明に係るトポロジを生成するシステムの構成例を示しており、本例のシステムは、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）や主メモリ、表示装置、入力装置、外部記憶装置等を具備したコンピュータ構成からなり、光ディスク駆動装置等を介してＣＤ−ＲＯＭ等の記憶媒体に記録されたプログラムやデータを外部記憶装置内にインストールした後、この外部記憶装置から主メモリに読み込みＣPＵで処理することにより、図１に示す各処理部の機能を実行する。
【００６６】
すなわち、本例のシステムでは、図１に示すように、プログラムされたコンピュータ処理を実行する機能として、入力処理部１０１、初期トポロジ生成処理部１０２、マルチエージェントシステム実行処理部（図中「マルチエージェントシステム処理部」と記載）１０３、候補トポロジ出力処理部１０４、トポロジ生成処理部１０５を具備している。
【００６７】
入力処理部１０１は、図示していないキーボードやマウス等を介してのユーザ操作に応じて入力さる情報、例えば、全てのノードの位置と、ノード間のトラヒック量比率と、単一リンク障害時の接続性喪失トラヒック量比率の許容上限値、生成候補トポロジ数K等の情報を入力して図示していない記憶装置に格納する。
【００６８】
初期トポロジ生成処理部１０２は、入力処理部１０１が入力・格納した情報を用いて、最小木を生成し、生成した最小木に対してSLF時（単一リンク障害時）の接続性喪失トラヒック量比率の平均が制約限界を満たすよう付加すべきリンクを選択する。
【００６９】
マルチエージェントシステム処理部１０３は、本発明に係る候補トポロジの生成を行うものであり、エージェントの自律的な行動をシミュレートすることで候補トポロジ集合を生成する。
【００７０】
候補トポロジ出力処理部１０４は、マルチエージェントシステム処理部１０３が生成した候補トポロジを出力する。
【００７１】
トポロジ生成処理部１０５は、マルチエージェントシステム処理部１０３が生成し、候補トポロジ出力処理部１０４が出力した候補トポロジに対して、上述の特許文献１において提案しているAHP（Analytic Hierarchy Process）を網トポロジ評価へ適用した技術を用いて、当該AHPによる評価を行い、最終的なトポロジを生成する。
【００７２】
すなわち、入力処理部１０１は、入力装置を介して予め入力される複数の評価尺度情報と全ノードの位置情報およびノード間のトラヒック量比率情報ならびに単一リンク障害時の接続性喪失トラヒック量比率の許容上限値を入力して記憶装置に格納すると共に、評価尺度として、リンク距離を当該リンクの両端のノード間に発生するトラヒック量比率で除した値で定義されるリンクコストを格納する。
【００７３】
初期トポロジ生成処理部１０２は、正常時に全ノード間の接続性を確保できることを条件に、全ノードの位置情報を用いて、リンクコストの総和を最小とするトポロジである最小木を生成して、生成した最小木を構成する各ノードにリンクを設置すると共に、生成した最小木における各ノードに、任意の単一リンク障害時の接続性喪失トラヒック量比率の平均が許容上限値以下に収まるよう最も少数のリンクを付加したトポロジを生成する。
【００７４】
マルチエージェントシステム実行処理部１０３は、生成するトポロジを環境とし、リンクコストを含む複数の評価尺度ごとにエージェントを構成し、各エージェントが、対応する評価尺度の最大化を目的に自律的に行動するマルチエージェントシステムをシミュレートすることにより、全ノードの位置情報とノード間のトラヒック量比率情報を用いて、正常時に全ノード間の接続性を確保できることおよび任意の単一リンク障害時に接続性が喪失するトラヒック量の比率の平均が許容上限値以下に収まることを制約条件に、予め定められた個数の候補トポロジ集合を生成する。
【００７５】
候補トポロジ出力処理部１０４は、マルチエージェントシステム実行処理部１０３が生成した候補トポロジを出力し、トポロジ生成処理部１０５は、マルチエージェントシステム実行処理部１０３が生成し候補トポロジ出力処理部１０４が出力する候補トポロジを入力し、この候補トポロジをボトム層、予め定められた複数の評価尺度を中央の層、生成するトポロジをトップの階層とするAHPにより、予め定められた複数の評価尺度を同時に考慮した候補トポロジの評価を行い、各評価尺度に対して予め定められた重要度に応じたトポロジを選択する。
【００７６】
以下、このようなマルチエージェントシステム処理部１０３を用いた候補トポロジ生成技術について、詳細を説明する。
【００７７】
まず、『マルチエージェントシステム（MAS：Multi-Agent System）』について説明する。マルチエージェントシステム（MAS）は、多様な生物が作り出す生態系や、人間の集団が作る社会・経済系など、大規模でロバストなシステムにおいて生じる現象を分析する技術として注目されている。
【００７８】
MASは、多数の自律的に動作（行動）するエージェントから構成され、それぞれのエージェントは自身の環境を知覚し、自身の目標を達成するように行動する。
【００７９】
このように、MASは、「環境」と、この「環境」の状態を知覚し行動により環境に対して影響を与える自律的主体である複数の「エージェント」とから構成される。そして、「エージェント」間の相互作用を記述することで、システム全体の振舞いをシミュレーションにより分析する。
【００８０】
MASは、本来、エージェントの自律的な行動の結果、システム全体としてどのような状況が出現するかを解明する場合に用いられる。例えば、複雑系の研究では、MASは、システム全体として思いがけない状態が出現する現象を解明する場合に用いられる。また、工学的には、MASは、主に、ロバスト性や柔軟性といった性質をもつシステムの設計に用いられる。
【００８１】
しかし、MASが主に分析対象とする、生態系や経済系といったシステムは、障害や外部環境の変化に対して高いロバスト性を示すが、これは、エージェント間のダイナミックな相互作用の結果生まれる多様性に起因すると考えられる。
【００８２】
そのため、MASによって生成される各時点の環境の状態から構成される集合は、全てのエージェントの自律的な要求が反映され、かつ、多様性の高い状態の集合であると期待できる。
【００８３】
そこで、本例では、AHPにおけるトポロジ評価で考慮する評価尺度の各々をエージェントと見なし、各エージェントが、自身の評価尺度が最適化するよう、任意のリンク設置可能位置にリンクを追加もしくは削除する処理を行うMASを考えることで、AHPで高く評価され、かつ、多様性の高いトポロジ集合を生成することを図る。
【００８４】
以下、本例における『MASの環境とエージェント』について説明する。
【００８５】
本例では、MASを用いてネットワークにおけるトポロジ候補を生成するために、与えられたノード集合に対して構成可能なトポロジを「環境」と定義する。
【００８６】
すなわち、環境の状態の集合Sは、Q＝２L個の構成可能な各トポロジsqから構成され、S＝{s１,s２,…,sQ}となる。
【００８７】
そして、AHP適用の際に用いる評価尺度の数だけエージェントを構成し、各エージェントAiを、i番目の評価尺度Viに対応付ける。
【００８８】
環境の現在の状態snに対して、各エージェントがとる行動を行動関数として定義することでMASが構成されるが、本例では、各エージェントAiは、対応付けられた評価尺度Viの最適化を目的に行動させる。
【００８９】
MASにおいて、エージェントは、行動により、環境に影響を与えるが、本例では、エージェントの取りえる行動として、現在の環境の状態（トポロジ）を構成するリンクの任意の１本を削除するか、もしくはリンクが存在しない任意の一つのリンク設置可能位置に対してリンクを設置することを考える。
【００９０】
エージェントによる、リンク増減という行動の結果、あるトポロジから他のあるトポロジに環境が変化することになる。
【００９１】
本例では、トポロジの評価尺度として総リンク長ζと、トラヒック量比率で重み付けた平均ホップ長εとの二つを想定する。そのため、エージェントA１とエージェントA２の二つのエージェントを用意し、エージェントA１は、総リンク長ζが最小化するよう、エージェントA２は、平均ホップ長εが最小化するよう行動させる。
【００９２】
総リンク長ζは、トポロジへの任意のリンクの追加に対して常に非減少であり、任意のリンクの削除に対しては常に非増加である。
【００９３】
反対に、平均ホップ長εは、トポロジへの任意のリンクの追加に対して常に非増加であり、任意のリンクの削除に対しては常に非減少である。
【００９４】
従って、エージェントA１は常に一本のリンクを削除し、エージェントA２は常に一本のリンクを追加する。
【００９５】
現在の環境の状態（トポロジ）snを構成するリンクの集合をＥnとすると、エージェントA１は、リンク集合Ｅnを構成するリンクの中でリンク長dｅが最大のリンクを削除する。
【００９６】
また、トポロジsn（現在の環境の状態）においてリンクが設置されていないリンク設置可能位置の集合をＨnとすると、エージェントA２は、集合Ｈnを構成する各リンク設置可能位置に対して一本だけリンクを追加したトポロジにおける平均ホップ長εを各々計算し、その値が最小となる位置にリンクを追加する。
【００９７】
このようなリンクを追加する際には、制約条件C（正常時の全ノード間の接続性と、SLF時に接続性が喪失するトラヒック量比率の平均値ξ≦設計上限値αξという候補トポロジが満たすべき二つの制約条件）を満たすトポロジに対して、任意のリンクを追加した結果で得られるトポロジも、明らかに制約条件Cを満たすことから、エージェントA２の行動を決める際には、制約条件Cを考慮する必要はない。
【００９８】
しかし、リンクを削除する際には、任意のリンクを削除した結果で得られるトポロジは、制約条件Cを満たすとは限らないため、エージェントA１は、削除後も制約条件Cを満たすリンクの中で、リンク長が最大のリンクを一本、削除する必要がある。
【００９９】
制約条件Cを満たし、かつ、リンク長が最大となる削除候補リンクが複数存在する場合には、エージェントA１は、識別番号が最小のものを削除対象として選択する。同様に、エージェントA２がリンク追加場所を選択する際に、平均ホップ長εが最小となるリンク設置可能位置が複数存在する場合には、やはり識別番号が最小のものを選択する。
【０１００】
次に、本例における『MASの実行手順』について説明する。
【０１０１】
制約条件Cを満たすトポロジを、上述の特願２００９−０５０２７１号で述べた技術で構成し、トポロジTbを、手番０における環境の状態s0とする。
【０１０２】
そして、離散的なエージェントの行動と環境の状態変化を想定し、第n番目の手番において、行動を起こすエージェントを各々独立にランダムに選択する。
【０１０３】
本例では、エージェントA２を選択する確率をパラメタθで与える。エージェントが二つであるため、エージェントA１が選択される確率は１−θとなる。
【０１０４】
ただし、各手番において、選択エージェントの行動の結果、制約条件Cを満たし、かつ未出力のトポロジが存在しない場合、他方のエージェントを選択する。
【０１０５】
全てのエージェントが取りえる行動が存在しない場合には、既に出現した環境の状態の一つをランダムに選択し、選択した状態から再度、手番を継続させる。
【０１０６】
エージェントの行動手番を任意に与えた回数K−１だけ反復することで得られる各手番nにおける環境の状態s0，s１，…，sK−１を出力することで、制約条件を満たすK個の候補トポロジ集合を得ることができる。
【０１０７】
ところで、トポロジ候補集合を生成する際には、同一のトポロジを重複して出力しない一意性が求められる。そのため、各エージェントの行動決定の際、過去に出現した状態とならないか確認する必要がある。
【０１０８】
環境の状態（トポロジ）の重複を判定する最も単純な方法は、各手番において生じたトポロジをテーブルに保存しておき、全エントリを調べることで判定する方法である。
【０１０９】
しかし、生成トポロジ数の増加に伴い所要メモリ量と処理時間が線形に増加するため、大量の候補トポロジを生成する場合、適用が困難となる。
【０１１０】
限られたメモリ量とメモリアクセス数で、あるキーがメンバに含まれているか否かを判定する技術としてBloom filter（BF）が知られている。このBFは、bビットのハッシュ空間を持つk個の異なるハッシュ関数hiと、２b（bits）のbitmap（初期状態では全て０にリセットされる）から構成される。
【０１１１】
BFを用いてトポロジの重複を判定する場合、リンク設置位置に対応するビットが１をとり、リンクが設置されない位置に対応するビットが０をとるLビットから構成されるトポロジ構造sから得られるk個のハッシュ値hi（s）（i＝１，…，k）に対応するbitmap上のビットb（hi（s））を調べ、１つ以上０のビットが存在する場合に、未出力のトポロジであると判断する。そして、これらk個のビットを全て１にセットする。
【０１１２】
未出現の環境の状態であっても、偶然、BFのk個のハッシュ値に対応するbitmap中のビットが他の状態の更新によって１にセットされている可能性があるため、新規トポロジを誤って既出現トポロジと判定する可能性がある。
【０１１３】
そこで、新規トポロジを誤判定して出力できない確率の平均が、任意に与えたδとなるよう、次の数３に示す式（３）と式（４）でBFのパラメタkとパラメタbを設計する。
【０１１４】
【数３】
2011091751.tif 000005
【０１１５】
尚、式（３）において、bは当該式（３）を満たす最小の整数に設定し、kは式（４）を満たす最も近い整数に設定する。
【０１１６】
次に、「MASの実行時間を短縮する技術」について説明する。
【０１１７】
計算機上で各エージェントの行動をシミュレートすることで、任意に与えた個数K+１の候補トポロジを生成することができるが、必要となる計算量について以下考察する。
【０１１８】
正常時の全ノード間の接続性判定にはＯ（N2）の計算量が必要となる。
【０１１９】
また、トポロジを構成するリンク数がyであるとき、ξ（SLF時に接続制御が喪失するトラヒック量比率の平均値）の算出にはＯ（yN2）の計算量が必要になる。
【０１２０】
L＝N（N−１）/２であることから、BFを用いた新規トポロジの判定には、Ｏ（N2）の最短経路を得る必要があり、また、ε（トラヒック量比率で重み付けた平均ホップ長）の算出には、全ノードペア間の最短経路を得る必要があることからＯ（N3）の計算量が各々必要になる。
【０１２１】
そのため、各手番において、エージェントA１の行動決定にＯ（y（N2+N2+yN2））＝Ｏ（y2N2）の計算量が必要になり、エージェントA２の行動決定には、Ｏ（N2N3）＝Ｏ（N５）の計算量が必要になる。
【０１２２】
このように、エージェントA２の行動決定には、Ｏ（N５）の計算量が必要となり、NW規模Nの増加に伴い、急激に計算時間が増大する。
【０１２３】
そこで、エージェントA２の行動決定に要する処理時間の短縮技術を検討する。
【０１２４】
トラヒック量比率rijが大きなノードiとノードj間にリンクを設置することで、平均ホップ長εの大きな低減が期待できる。
【０１２５】
このことを確認するため、CAIDAでトポロジが公開されているNWのうち、完全メッシュなNWを除いた３５のNWの各々を対象に、リンクが設置されていない各ノードペア間に一本だけリンクを設置した場合のε（トラヒック量比率で重み付けた平均ホップ長）と、その両端のノードの人口比率積との相関係数を、ノード数Nに対して図２（a）にプロットする。
【０１２６】
図２（a）では、３５の全NWにおいて、両特性値間には、負の相関性が見られる。ただし、N（ノード数）が大きなほどノードの人口比の格差が低減するため、両特性の相関係数は増加し無相関に近づく。ただし、ノード数Nが同程度であっても、NWによって両特性の相関係数は大きく異なる。
【０１２７】
例として、図２（b）に、NW２（Ｂ，ＡＧＩＳ）とNW５（Ｅ，ＡＴ＆Ｔ  ＷｏｒｌｄＮｅｔ）のトポロジを示すが、NW２には高次数のハブノードが存在しないのに対して、NW５には存在する。NW５のようにハブノードが存在するNWにおいては、ハブノードの人口比が高い傾向があり、高次数ノードにリンクを設置することでε（トラヒック量比率で重み付けた平均ホップ長）が大きく低減する。
【０１２８】
このように、MASの実行過程において出現するトポロジによって、効果は異なるが、多くの場合、人口比積の大きなノード間にリンクを設置することで、ε（トラヒック量比率で重み付けた平均ホップ長）の大きな低減が見込める。
【０１２９】
よって、エージェントA２の行動決定の際には、トポロジsn（現在の環境の状態）においてリンクが設置されていないリンク設置可能位置の集合Ｈnに含まれるリンク設置可能位置の中で、交流トラヒック量比率rij（発ノードiと着ノードj間のトラヒック量のＮＷ全体のトラヒック量に対する比率）の値が大きな順にリンクを一本設置した場合のトポロジが既出現か否かを判定し、新規のトポロジを得るまでリンクを設置する試行を反復する。
【０１３０】
この場合、エージェントA２の行動決定に要する処理時間をＯ（N3）に低減でき、候補トポロジのリンク数yをNと同程度と考えれば、本例での総計算時間はＯ（Ky2N2+KN3）＝Ｏ（KN4）となる。
【０１３１】
このような本例の技術による「評価結果」について以下説明する。
【０１３２】
ここでは、αξ（SLF時に接続性が喪失するトラヒック量比率の平均値ξの任意に与えた設計上限値）＝０．０２に設定し、また、δ（新規トポロジを誤判定して出力できない確率の平均の任意の設定値）＝０．０１に設定して行った性能評価結果について述べる。
【０１３３】
まず、「エージェントの選択確率がMASに及ぼす影響」について説明する。
【０１３４】
図１２に示す、CAIDAでトポロジが公開されているネットワークＸ（Nap.Net.LLC）のノード配置とノード人口比率を用いて、各手番におけるエージェントA２の選択確率θが、生成トポロジ集合に与える影響について分析する。
【０１３５】
ネットワークＸ（Nap.Net.LLC）はノード数N＝６であるため、L＝１５のリンク設置可能位置が存在する（L＝N！＝５＋４＋３＋２＋１＝１５）。
【０１３６】
図３に、候補トポロジ数K＝１００とした場合に生成されたトポロジ集合の二つの評価尺度V１とV２の累積分布を、θ（エージェントA２を選択する確率）の値の三つの場合（θ＝０．２５，θ＝０．５，θ＝０．７５）について各々示す。
【０１３７】
また、図３には、制約条件Cを満たす全てのトポロジを総当たりで得た場合の累積分布を同様に示す。L＝１５であるため、組合せとしては、２15＝３２，７６８個のトポロジが構成可能であるが、制約条件Cを満足するトポロジは１４，７１８個存在した。
【０１３８】
候補トポロジ数K＝１００の場合、制約条件Cを満たす全候補の１％未満という限定された数の候補のみを生成するが、評価尺度（総リンク長）V１と評価尺度（平均ホップ長）V２が小さな優れたトポロジが数多く生成される。
【０１３９】
また、エージェントA２を選択する確率θが小さいほど、評価尺度（総リンク長）V１が小さい反面、評価尺度（平均ホップ長）V２が大きいトポロジが生成される傾向がある。これは、エージェントA２を選択する確率θが小さいほど、評価尺度（総リンク長）V１の最適化を図るエージェントA１が行動する機会が増加するためである。
【０１４０】
反対に、エージェントA２を選択する確率θが大きい場合、エージェントA２が行動する機会が増加する結果、評価尺度（平均ホップ長）V２が小さく評価尺度（総リンク長）V１が大きなトポロジが生成される傾向がある。
【０１４１】
次に、図４（a）に、エージェントA２を選択する確率θを様々に変えて、候補トポロジ数K＝１００もしくはK＝１，０００のトポロジ候補を生成したときの、得られた候補集合における各評価尺度の平均値を、当該確率θに対してプロットする。
【０１４２】
また、同様に、図４（b）に、得られた候補集合における各評価尺度の変動係数をプロットする。ただし、エージェントA２を選択する確率θの各値に対して各々１０の候補集合を生成し、その平均値をプロットしている。
【０１４３】
やはり、エージェントA２を選択する確率θの増加に伴い、評価尺度（総リンク長）V１の平均値は増加する反面、評価尺度（平均ホップ長）V２の平均値は減少することが確認できる。その傾向は、特に、生成候補数Kが小さなほど強くなることから、所要時間の観点から、生成可能な候補数が少ない場合ほど、エージェントA２を選択する確率θが生成候補集合に与える影響が大きくなる。
【０１４４】
生成候補集合の評価尺度（平均ホップ長）V２の変動係数は、エージェントA２を選択する確率θを変えてもほとんど一定であるのに対して、評価尺度（総リンク長）V１の変動係数は、エージェントA２を選択する確率θ＝０．５付近で最大となり、エージェントA２を選択する確率θが０や１に近づくにつれて減少する。エージェントA２を選択する確率θ＝０．５のとき、リンクの追加と削除が均等する結果、生成候補集合の評価尺度（総リンク長）V１に関する多様性が最大化する。
【０１４５】
次に、「生成候補集合の有効性」について説明する。
【０１４６】
本例の技術において、生成する候補トポロジ数Kを抑えることで、大規模なNWに対しても、候補集合の生成に要する時間を抑え、現実的な時間で候補集合を得ることが可能となる。
【０１４７】
しかし、AHPの評価結果は候補集合に依存するが、生成される候補集合は、制約条件Cを満たす全トポロジの一部となるため、評価結果に与える影響が懸念される。
【０１４８】
そこで、ここでは、全トポロジを候補とした場合と、本例での生成候補集合にAHPを適用した場合の、それぞれの評価結果を比較する。
【０１４９】
大規模NWに対して全候補トポロジを現実的な時間で生成することは困難であるため、ここでも、図１２に示す、ノード数N＝６の小規模NWであるネットワークＸ（Nap.Net.LLC）のノード配置とノード人口比率を用いる。
【０１５０】
AHPの評価シナリオとして、コストを重視する場合（シナリオ１）と品質を重視する場合（シナリオ２）の二つを考える。
【０１５１】
シナリオ１（コスト重視）における各評価尺度の重みを、S１1＝０．７５、S２1＝０．２５に、シナリオ２（品質重視）においては、各評価尺度の重みを、S１1＝０．２５、S２1＝０．７５に設定した。
【０１５２】
図５（a）に、制約条件Cを満たす１４，７１８の全トポロジを対象に、評価尺度（総リンク長）V１と評価尺度（平均ホップ長）V２の散布図を示す。
【０１５３】
評価尺度（総リンク長）V１と評価尺度（平均ホップ長）V２の二つの評価尺度間には、緩やかな負の相関性が見られるものの、広い領域に散布しており、多様なトポロジが存在する。
【０１５４】
また、図５（b）に、１４，７１８の全トポロジ候補を対象にAHPを適用した際に、各評価シナリオ１，２において、上位１０位までに評価されたトポロジの評価尺度（総リンク長）V１と評価尺度（平均ホップ長）V２の散布図を同様に示す。
【０１５５】
評価尺度（総リンク長）V１を重視するシナリオ１においては、評価尺度（総リンク長）V１は小さいものの、評価尺度（平均ホップ長）V２に関しては様々な値を有するトポロジが高く評価され、評価尺度（平均ホップ長）V２を重視するシナリオ２においては、評価尺度（平均ホップ長）V２は小さいものの、評価尺度（総リンク長）V１に関しては様々な値を有するトポロジが高く評価された。
【０１５６】
従って、限定された候補トポロジ集合を生成する際には、重視する評価尺度が小さく、かつ、もう一方の評価尺度に関しては、幅広い範囲にわたり多様なトポロジを生成することが、AHPの評価結果に与える影響を抑えるためには有効である。
【０１５７】
次に、図６において、本例の技術を用いて生成した候補トポロジ集合に対して、AHPを適用した場合に、上位１０位までに評価された各トポロジの、１４，７１８の全トポロジ候補を対象とした場合の評価順位の平均値を、エージェントA２を選択する確率θの設定値に対してプロットする。ただし、各θ（エージェントA２を選択する確率θ）の値に対して各々１０回の試行を行いその平均値を示す。
【０１５８】
上位１０個のトポロジの評価順位が、全候補を対象とした場合の評価順位に完全に一致する場合、平均順位は、Σi=110＝５．５となることから、理想値y＝５．５をあわせて示す。
【０１５９】
また、「本例のMASの実行時間の短縮技術」で述べたように、本例の技術は、エージェントA２の行動決定の際の所要計算時間を短縮するために、人口比積の大きなノード間に対して優先的にリンクの設置を試みる。
【０１６０】
そのため、AHPの評価結果に与える影響が懸念されるため、全リンク設置候補位置を対象に、トラヒック量比率で重み付けた平均ホップ長εを算出した場合（図６中の「Naive selection」）の結果についても同様にプロットする。
【０１６１】
本例の技術とNaive selectionにおける上位１０個のトポロジの平均順位の差異は小さく、エージェントA２の行動決定の際に、人口比の大きなリンク位置を優先的に用いてリンク設置を試みても、AHPの評価結果に及ぼす影響は小さい。
【０１６２】
また、図６（a），図６（b）に示すように、シナリオ１の場合、エージェントA２を選択する確率θが０．４程度より小さいときの平均順位は、理想値５．５に近く、AHPの評価結果に与える影響が抑えられるが、エージェントA２を選択する確率θが０．４程度より大きい場合には、エージェントA２を選択する確率θの増加に伴い平均順位が急増し、不適切な評価結果となる。
【０１６３】
これは、図５で見たように、エージェントA２を選択する確率θの増加に伴い、生成候補集合の評価尺度（総リンク長）V１の平均値が増加するが、評価尺度（平均ホップ長）V２の変動係数はほとんど一定であるためである。
【０１６４】
シナリオ１の場合、評価尺度（総リンク長）V１が小さいトポロジを、評価尺度（平均ホップ長）V２の広い領域にわたり生成することが有効であるため、エージェントA２を選択する確率θを小さく設定した場合に評価結果が良好となる。
【０１６５】
従って、シナリオ１では、評価尺度（平均ホップ長）V２の重みを０．２５に設定していることから、シナリオ１における候補集合生成時には、以後、エージェントA２を選択する確率θ＝０．２５に設定する。
【０１６６】
他方、図６（c），図６（d）に示すように、シナリオ２の場合、エージェントA２を選択する確率θの広い領域において、平均順位は理想値５．５に近いが、エージェントA２を選択する確率θ＝０．５付近で最小となる。
【０１６７】
これは、図５で見たように、生成候補集合の評価尺度（平均ホップ長）V２の平均値は、エージェントA２を選択する確率θの小さい領域では、エージェントA２を選択する確率θの増加に対して緩やかに減少するが、評価尺度（総リンク長）V１の変動係数はθ＝０．５付近で最大となるためである。
【０１６８】
シナリオ２の場合、評価尺度（平均ホップ長）V２が小さいトポロジを、評価尺度（総リンク長）V１の広い領域にわたり生成することが有効であるため、エージェントA２を選択する確率θを０．５付近に設定した場合に評価結果が良好となる。よってシナリオ２における候補集合生成時には、以後、エージェントA２を選択する確率θ＝０．５に設定する。
【０１６９】
次に、本例の技術と既存の技術との比較を説明する。
【０１７０】
ここでは、本願発明者が特願２００９−０５０２７１号において示したトポロジ候補生成技術（以後、LE（Limit edge）と表記）と、本例のMASを用いたトポロジ生成技術（以後、MASと表記）とを比較し、本例の技術の有効性を確認する。
【０１７１】
図７（a）と図７（b）に、やはり、図１２に示すNap.Net.LLCのノード配置とノード人口比率に対してMAS法とLE法を用いて各々生成されたトポロジ集合の評価尺度（総リンク長）V１と評価尺度（平均ホップ長）V２の平均値を、生成トポロジ数に対してプロットする。ただしMAS法においては、エージェントA２を選択する確率θを０．２５と０．５に設定し、１０回の試行の平均値を示している。
【０１７２】
MAS法では、生成候補数をパラメタKにより直接、任意の値に設定することが可能であるが、LE法では、リンク設置可能位置数xに対して２x個の候補が生成されるため、２のべき乗の粒度でのみ候補数を設定できる。
【０１７３】
MAS法によって生成される候補集合の各評価尺度の平均値は、生成候補数Kとは無関係でほぼ一定であり、生成する候補トポロジ数Kを少数に抑えた場合にも、特定のトポロジ形状に偏ることなく多様なトポロジ候補が生成される。
【０１７４】
一方、LE法は、リンク設置可能位置数xの増加に伴い、リンクを設置可能な候補位置の数が単調に増加する結果、生成される候補集合の評価尺度（平均ホップ長）V２の平均値は生成候補数に対してほぼ一定であるのに対して、評価尺度（総リンク長）V１の平均値は、生成候補数の増加に伴い大きく増加する。
【０１７５】
MAS法によって生成される候補集合は、LE法と比較して、生成候補数の広い領域において、評価尺度（総リンク長）V１の平均値は小さく、評価尺度（平均ホップ長）V２の平均値は大きい。
【０１７６】
また、図７（c）と図７（d）に、生成された各候補集合の評価尺度（総リンク長）V１と評価尺度（平均ホップ長）V２の変動係数を同様に示す。
【０１７７】
MAS法とLE法の両方において、評価尺度（平均ホップ長）V２の変動係数は、生成候補数とほぼ無関係に一定であるが、評価尺度（総リンク長）V１の変動係数は、生成候補数の少ない領域では候補数の増加に伴い急増し、その後、候補数に対してほぼ一定となる。
【０１７８】
MAS法によって生成される候補集合は、LE法によって生成される候補集合と比較して、生成候補数の広い領域において、評価尺度（総リンク長）V１と評価尺度（平均ホップ長）V２の変動係数は大きく、生成候補数が同じである場合、MAS法はLE法よりもより多様な候補集合を生成する。
【０１７９】
次に、MAS法とLE法の二つの方式によって生成されたトポロジ候補集合の有効性を確認するため、図８において、MAS法とLE法の各々によって生成された候補集合に対してAHPを適用した場合に、上位１０位に評価された各トポロジの、１４，７１８の全トポロジ候補を対象とした評価順位の平均値を、生成候補数に対してプロットする。
【０１８０】
ただし、MAS法においては１０回の試行における平均順位の最小値、最大値、平均値の三つの値を各々プロットする。
【０１８１】
図８に示されるように、二つの方式とも、生成候補数の増加に伴い、上位１０個のトポロジの平均順位が減少し、生成候補集合の有効性が向上する。
【０１８２】
ただし、LE法においては、トポロジTbを構成するリンク位置には常にリンクを設置するため、候補数が増加しても、総リンク長（V１）が小さいトポロジを生成することが難しく、総リンク長V１を評価尺度として重視するシナリオ１においては、候補数が増加しても、平均順位はほとんど減少しない。
【０１８３】
コストを重視する場合（シナリオ１）、候補集合における評価尺度（総リンク長）V１の平均値が小さく、評価尺度（平均ホップ長）V２の変動係数が大きいことが望ましいが、図７（a）と図７（d）で示したように、MAS法の生成候補集合は、LE法の生成候補集合と比較して、評価尺度（総リンク長）V１の平均値が小さく評価尺度（平均ホップ長）V２の変動係数が大きい。
【０１８４】
そのため、図８（a）に示すように、生成候補数の広い領域において、MAS法は、LE法よりも、平均順位の小さい優れた候補集合を生成できる。
【０１８５】
また、MAS法のLE法に対する優位性の度合いは高く、LE法の生成候補数がMAS法と比較して大きくできるような場合にも、MAS法の生成候補集合の優位性が高い。
【０１８６】
一方、品質を重視する場合（シナリオ２）、候補集合における評価尺度（平均ホップ長）V２の平均値が小さく、評価尺度（総リンク長）V１の変動係数が大きいことが望ましいが、図７（b）と図７（c）で示したように、MAS法の生成候補集合は、LE法の生成候補集合と比較して、評価尺度（平均ホップ長）V２の平均値と評価尺度（総リンク長）V１の変動係数は共に大きい。
【０１８７】
そのため、両方式の優位性に関しては一貫したことは言えないが、図８（b）に示すように、MAS法は、LE法と比較して平均順位が小さく、シナリオ２においても、より良好な候補集合を生成できる。
【０１８８】
以上、まとめると、LE法では、生成候補集合の総リンク長に関する多様性が非常に低く、コストを重視する場合には、生成候補数がMAS法と比較して多くできる場合にも、MAS法を用いることが有効となる。
【０１８９】
また、品質を重視する場合には、二つの方式の有効性の差異は低減するものの、生成候補数が同程度あれば、やはり、MAS法が有効であり、LE法は、MAS法と比較して、生成候補数を非常に多くできる場合にのみ有効となる。
【０１９０】
次に、本例の技術による、「様々なNWに対する適用結果」を説明する。
【０１９１】
これまでの評価では、図１２に示すCAIDAにおけるNap.Net.LLCのノード配置を用いてMAS法やLE法の性能を評価したが、ここでは、図１２で示すCAIDAでトポロジが公開されている３６のNWのノード配置とノード人口比を対象に、両方式を適用した結果について述べる。
【０１９２】
これら３６のNWには、N＝５の小規模なNWから、N＝１２６の大規模なNWまで含まれるが、Nが６を超えるNWにおいては、制約条件を満たす全候補トポロジを現実的な時間で生成することは困難であるため、全候補に対してAHPを適用した場合の評価順位に関して分析することはできない。
【０１９３】
しかし、前述したように、コストを重視してトポロジを評価する場合には、常に、MAS法は、LE法と比較して有効となり、一方で、品質を重視する場合には、各方式の優位性は、生成可能なトポロジ数に依存する。
【０１９４】
そこで、計算時間の許容上限を６００秒としたときのMAS法とLE法において生成可能な候補トポロジ数の最大値K_{max}を比較する。
【０１９５】
図９において、各NWのノード数Nに対して、MAS法（θ＝０．５に設定）とLE法におけるK_{max}を各々プロットする。
【０１９６】
トポロジ候補の算出は、２．６GHzのPentium(登録商標)４と１GBのメモリを有するPC（パーソナルコンピュータ）上で行った。尚、ノード数N＝１２６のネットワークＧＧ（UUNET）においては、両方式とも初期トポロジTbを構成するだけで、既に６００秒を超過したため評価対象外とした。
【０１９７】
ノード数Nが５のネットワークＱ，Ｕの二つのNW（GetNet International，ipf.net）とノード数Nが６のネットワークＸ（Nap.Net.LLC）に対しては、両方式において制約条件を満たす全てのトポロジを６００秒以内に生成することができた。
【０１９８】
しかし、他の３２のNWに対しては、６００秒で生成できるトポロジは一部の候補に限られ、候補トポロジの生成最大数K_{max}は、ノード数Nの増加に伴い減少する。ノード数Nが小さい場合にはLE法が、Nが大きい場合にはMAS法が、より多数の候補トポロジを生成できる。
【０１９９】
MAS法の総計算量は、上述の「MASの実行時間短縮技術」の説明で述べたように、Ｏ（KN4）であり、一方、LE法の総計算量は、リンク設置候補位置数xに対してＯ（xN５+２xN3）となる。
【０２００】
LE法の生成候補数は２xであるためK＝２xとすると、LE法の総計算量は、Ｏ（lnKN５+KN3）となる。
【０２０１】
ノード数Nが小さいNWに対しては、生成候補トポロジ数Kが大きくなるため、Ｏ（lnKN５+KN3）≒Ｏ（KN3）となり、MAS法の所要計算時間はLE法より大きくなる傾向がある。
【０２０２】
一方、ノード数Nが大きいNWに対しては、生成候補トポロジ数Kが小さくなるため、Ｏ（lnKN５+KN3）≒Ｏ（lnKN５）となり、LE法に所要計算時間は、MAS法より大きくなる傾向がある。
【０２０３】
特に、ノード数Nが大きな大規模NWに対して生成可能な候補トポロジ数が少なくなるため、大規模NWに対して、より多数の候補トポロジを生成可能なMAS法がLE法と比較して有効である。
【０２０４】
次に、図１３を用いて、本発明に係るマルチエージェントシステムを用いた候補トポロジ生成方法について説明する。この図１３に示す例では、図１における入力処理部１０１とマルチエージェントシステム処理部１０３および候補トポロジで処理部１０４からなる処理である。
【０２０５】
図１における入力処理部１０１は、図３に示すように、入力装置１３１を介して予め入力される複数の評価尺度情報と全ノードの位置情報およびノード間のトラヒック量比率情報ならびに単一リンク障害時の接続性喪失トラヒック量比率の許容上限値を入力して図示していない記憶装置に格納する（ステップＳ１３０１）。
【０２０６】
マルチエージェントシステム実行処理部１０３は、生成するトポロジを環境とし、複数の評価尺度ごとにエージェントを構成し、各エージェントが、対応する評価尺度の最大化を目的に自律的に行動するマルチエージェントシステムをシミュレートすることにより、全ノードの位置情報とノード間のトラヒック量比率情報を用いて、正常時に全ノード間の接続性を確保できることおよび任意の単一リンク障害時に接続性が喪失するトラヒック量の比率の平均が許容上限値以下に収まることを制約条件に、予め定められた個数の候補トポロジ集合を生成する（ステップＳ１３０２）。
【０２０７】
候補トポロジ出力処理部１０４は、マルチエージェントシステム実行処理部１０３が生成した候補トポロジを入力して、出力データ１３３として表示装置や記憶装置等に出力する（ステップＳ１３０３）。
【０２０８】
尚、マルチエージェントシステム実行処理部１０３の各エージェントは、現在の環境としてのトポロジを構成するリンクの任意の１本を削除することで、もしくは、リンクが存在しない任意の一つのノードに対してリンクを追加することで、現在の環境に対して影響を与えるよう行動する。
【０２０９】
また、図１における初期トポロジ生成処理部１０２を設けた場合、入力処理日１０１は、評価尺度として、リンク距離を当該リンクの両端のノード間に発生するトラヒック量比率で除した値で定義されるリンクコストを記憶装置に格納し、初期トポロジ生成処理部１０２は、正常時の全ノード間の接続制御確保を条件に、全ノードの位置情報を用いて、リンクコストの総和を最小とするトポロジである最小木を生成し、生成した最小木を構成する各ノードにリンクを設置し、生成した最小木における各ノードに、任意の単一リンク障害時の接続性喪失トラヒック量比率の平均が許容上限値以下に収まるよう最も少数のリンクを付加したトポロジを生成し、マルチエージェントシステム実行処理部１０３は、初期トポロジ生成処理部１０２が生成したトポロジを、環境の初期状態として用いる。
【０２１０】
また、マルチエージェントシステム実行処理部１０３は、各手番において行動するエージェントを、予め各エージェント毎に定めた確率に従いランダムに選択し、選択したエージェントが、制約条件を満たし且つ未出現のトポロジを作る行動をとることができない場合には、他のエージェントを選択して行動させ、いずれのエージェントも制約条件を満たし且つ未出現のトポロジを作る行動をとることができない場合には、既に出現したトポロジをランダムに選択し、選択したトポロジから再度、手番を進める。
【０２１１】
また、マルチエージェントシステム実行処理部１０３は、選択したエージェントが行動を選択する際に、出現するトポロジが既に出現したトポロジと一致しないか否かの判定を、Bloomfilterを用いて行う。
【０２１２】
また、入力処理部１０１は、評価尺度情報として、総リンク長と、トラヒック量比率で重み付けた平均ホップ長を入力して記憶装置に格納し、マルチエージェントシステム実行処理部１０３は、総リンク長に第１のエージェント（エージェントA１）を、平均ホップ長に第２のエージェント（エージェントA２）を対応付け、第１のエージェントは、総リンク長の最大化を目的に自律的に行動し、第２のエージェントは、上記平均ホップ長の最大化を目的に自律的に行動する。
【０２１３】
また、マルチエージェントシステム実行処理部１０３は、トラヒック量比率で重み付けた平均ホップ長に対応付けた第２のエージェント（エージェントA２）の行動を選択する際、人口比率が大きいノード間を優先する。
【０２１４】
以上、各図を用いて説明したように、本例のトポロジ生成システムおよびマルチエージェントシステムを用いた候補トポロジ生成方法では、ネットワークのトポロジを設計する際、特に、大規模ネットワークに対する候補トポロジの設計において、全ノードの位置が与えられ、任意のノード間にリンクを設置することが可能である場合に、正常時における全ノード間の接続性を確保すること、および、任意の単一リンク障害時に接続性が喪失するトラヒック量の比率の平均が任意に定められた上限値以下に収まること、を制約条件に、現実的な時間内で、候補トポロジ集合を生成することができ、網トポロジの効率的な設計が可能となる。
【０２１５】
すなわち、従来の技術では、生成する候補トポロジ集合の総リンク長に関する多様性が非常に低く、生成する候補トポロジ数を少なくした場合には、コストを重視する場合および品質を重視する場合のいずれにおいても、多様な候補トポロジを生成することができず、従来の技術は、生成候補数を非常に多くした場合のみに有効なものであり、生成する候補数を少数に抑え、かつ、特定のトポロジ形状に偏ることなく、多様なトポロジ候補を生成することができなかったのに対し、本例によれば、これら従来技術の課題を解決でき、ネットワークのトポロジ設計における多様な候補トポロジ集合の、現実的な時間内での生成を、効率的に行うことが可能となる。
【０２１６】
尚、本発明は、各図を用いて説明した例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能である。例えば、本例では１つのコンピュータ装置内に設けた図１における初期トポロジ生成処理部１０２とマルチエージェントシステム実行処理部１０３およびトポロジ生成処理部１０５のそれぞれを、別々のコンピュータ装置に設けた構成としても良い。
【０２１７】
また、図１３のステップＳ１３０２においてマルチエージェントシステム実行処理部１０３が生成し、図１３のステップＳ１３０３において図１の候補トポロジ出力処理部１０４が出力する候補トポロジを、図１のトポロジ生成処理部１０５に入力し、このトポロジ生成処理部１０５において、この候補トポロジをボトム層、予め定められた複数の評価尺度を中央の層、生成するトポロジをトップの階層とするAHP（Analytic Hierarchy Process）により、予め定められた複数の評価尺度を同時に考慮した候補トポロジの評価を行い、各評価尺度に対して予め定められた重要度に応じたトポロジを選択する手順を付与することにより、AHPにおけるトポロジ評価で考慮する評価尺度の各々をエージェントとみなし、各エージェントが、自身の評価尺度が最適化するように、任意のリンク設置可能位置に「リンクを追加」する処理、もしくは、「リンクを削除」する処理を行うマルチエージェントシステムを考えることで、AHPで高く評価され、かつ、多様性の高いトポロジ集合の生成を行うことができる。
【０２１８】
また、本例のコンピュータ構成例に関しても、キーボードや光ディスクの駆動装置の無いコンピュータ構成としても良い。また、本例では、光ディスクを記録媒体として用いているが、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）等を記録媒体として用いることでも良い。また、プログラムのインストールに関しても、通信装置を介してネットワーク経由でプログラムをダウンロードしてインストールすることでも良い。
【符号の説明】
【０２１９】
１０１：入力処理部、１０２：初期トポロジ生成処理部、１０３：マルチエージェントシステム実行処理部（「マルチエージェントシステム処理部」）、１０４：候補トポロジ出力処理部、１０５：トポロジ生成処理部、１３１：入力装置、１３２：記憶装置、１３３：出力データ。
【図１】
2011091751.tif 000006
【図２】
2011091751.tif 000007
【図３】
2011091751.tif 000008
【図４】
2011091751.tif 000009
【図５】
2011091751.tif 000010
【図６】
2011091751.tif 000011
【図７】
2011091751.tif 000012
【図８】
2011091751.tif 000013
【図９】
2011091751.tif 000014
【図１０】
2011091751.tif 000015
【図１１】
2011091751.tif 000016
【図１２】
2011091751.tif 000017
【図１３】
2011091751.tif 000018