(57)【特許請求の範囲】
【請求項１】
複数の計算ノードと、
前記複数の計算ノード間を接続するトポロジが可変のネットワークとを有し、
第１のルーティング規則に基づいて前記ネットワークのトポロジを決定し、
決定したトポロジに対して、前記第１のルーティング規則を含む複数のルーティング規則の候補から、適用するルーティング規則を選択する情報処理システム。
【請求項２】
請求項１に記載の情報処理システムにおいて、
前記適用するルーティング規則を選択する際に、初期集団の遺伝子に前記第１のルーティング規則を含む遺伝的アルゴリズムによる探索でルーティング規則を選択することを特徴とする情報処理システム。
【請求項３】
請求項２に記載の情報処理システムにおいて、
前記第１のルーティング規則は、最短経路探索に基づいて決定されることを特徴とする情報処理システム。
【請求項４】
請求項１に記載の情報処理システムにおいて、
前記ネットワークは光スイッチを有することを特徴とする情報処理システム。
【請求項５】
請求項１に記載の情報処理システムにおいて、
前記計算ノードはサーバ装置であることを特徴とする情報処理システム。
【請求項６】
複数の計算ノードと、
前記複数の計算ノード間を接続するトポロジが可変のネットワークとを準備し、
第１のルーティング規則に基づいて前記ネットワークのトポロジを決定し、
決定したトポロジに対して、前記第１のルーティング規則を含む複数のルーティング規則の候補から、適用するルーティング規則を選択する情報処理システムの構成方法。
【請求項７】
請求項６に記載の情報処理システムの構成方法において、
前記適用するルーティング規則を選択する際に、初期集団の遺伝子に前記第１のルーティング規則を含む遺伝的アルゴリズムによる探索でルーティング規則を選択することを特徴とする情報処理システムの構成方法。
【請求項８】
請求項７に記載の情報処理システムの構成方法において、
前記第１のルーティング規則は、最短経路探索に基づいて決定されることを特徴とする情報処理システムの構成方法。
【請求項９】
請求項６に記載の情報処理システムの構成方法において、
前記ネットワークは光スイッチを有することを特徴とする情報処理システムの構成方法。
【請求項１０】
請求項６に記載の情報処理システムの構成方法において、
前記計算ノードはサーバ装置であることを特徴とする情報処理システムの構成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理システム及び情報処理システムの構成方法に関し、特に、計算機間のデータ通信の効率化を図る技術に関する。
【背景技術】
【０００２】
一般に、並列計算機システムではサーバの並列度の増加に伴い通信性能が低下する傾向にある。これは、実装やコストの面で、サーバ規模に見合うネットワークを構成することが難しくなるからである。このため、実装やコストの制約下で効率の良いネットワークを如何に構築するかが非常に重要な課題となっている。【０００３】
通信コスト最小化を目的としたネットワークトポロジを設計する技術として特許文献１に記載の技術がある。特許文献１に記載の技術は、遺伝的アルゴリズムと局所探索法を組み合わせ、拠点間の通信コストが最小となるようネットワークトポロジを探索するものである。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許第６９１２２０７号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ネットワークトポロジはサーバ間の接続関係を表すものであり、サーバ間の通信がネットワークトポロジ内のどのパスを介して行われるか（ルーティング）についてはルーティングアルゴリズムで決まる。つまり、ネットワークトポロジの良し悪しを判定するにはそのルーティングパスも合わせて考える必要がある。【０００６】
特許文献１に記載のネットワークトポロジ設計技術ではルーティングアルゴリズムとして最短経路探索を用いている。しかしながら、最短経路探索ではパスの混雑度を考慮しないため、そのルーティングパスは必ずしも最適とはならない。その一方で、最適なネットワークトポロジの探索と最適なルーティングパスの探索を同時に行った場合、各々の探索がＮＰ困難な問題に属することから、現実的な時間で有用な解を求めることができなくなってしまう。【０００７】
本発明は、ネットワークトポロジとルーティングパスの両方を効率良く探索する技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明では、計算ノード間を接続するネットワークトポロジを可変とし、第１のルーティング規則に基づいてネットワークトポロジを決定し、決定したネットワークトポロジに対して、第１のルーティング規則を含む複数のルーティング規則の候補から、適用するルーティング規則を選択することで上述の課題を解決する。
【発明の効果】
【０００９】
本発明によれば、現実的な時間でデータ転送時間最小化に対する準最適な解を求めることができ、ネットワークトポロジとルーティングパスの両方を効率良く探索することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施例に係る並列計算機システムを示す図である。
【図２】図１の処理サーバ装置１００及び管理サーバ装置１０１の内部構成を示すブロック図である。
【図３】図１のスイッチ２００の内部構成及びスイッチ２００内におけるパケットの転送経路の例を示す図である。
【図４】図１の光スイッチ３００の内部構成及び光スイッチ３００内における光パスの例を示す図である。
【図５】本発明の実施例に係る並列計算機システムにおけるネットワークトポロジ変更及びアプリケーション実行を示すフロー図である。
【図６】グラフの例を示す図である。
【図７】図６のグラフを示すグラフデータの例である。
【図８】図６のグラフを８個のクラスタに分割したクラスタリングデータの例である。
【図９】図８のクラスタリング結果に対するトラフィックテーブルの例である。
【図１０】ネットワークトポロジを示すトポロジテーブルの例である。
【図１１】図１０のトポロジテーブルに基づいて光スイッチ３００を制御した場合の光パスを示した図である。
【図１２】ネットワークトポロジ探索及びルーティングパス探索に用いる遺伝的アルゴリズムの処理を示すフロー図である。
【図１３】ネットワークトポロジ探索に用いるトポロジ遺伝子１０００の例を示す図である。
【図１４】ルーティングパス探索に用いるルーティング遺伝子１１００の例を示す図である。
【発明を実施するための形態】
【実施例１】
【００１１】
図１に、本発明の実施の形態に係る情報処理システムとして、並列計算機システム２０００を示す。本実施例では、並列計算機システム２０００の処理対象の例として、最短経路探索などのグラフ解析を用いて説明する。図１に示されるように、並列計算機システム２０００は、処理サーバ装置１００、管理サーバ装置１０１、これらサーバ装置群を接続するスイッチ２００、及びスイッチ２００間を接続する光スイッチ３００を有している。並列計算機システム２０００は、スイッチ２００間で接続があってもかまわないし、光スイッチ３００は複数の光スイッチを接続して構成してもかまわないが、以降、代表して図１の構成について説明する。【００１２】
図２は、図１に示される処理サーバ装置１００及び管理サーバ装置１０１の内部構成を示すブロック図である。処理サーバ装置１００や管理サーバ装置１０１は、図２に示す内部構成と同等の機能を有していれば良く、例えば、サーバ装置毎に異なるメーカや性能であってもかまわない。各処理サーバ装置１００は、計算ノードとして働き、並列計算を実現する。管理サーバ装置１０１は、管理ノードとして働く。処理サーバ装置１００及び管理サーバ装置１０１は、ＣＰＵ１１０、メモリ１２０、ストレージ１３０、入力装置１４０、出力装置１５０、ネットワークインタフェース１６０、及びバス１７０を備える。【００１３】
処理サーバ装置１００及び管理サーバ装置１０１内の構成要素間のデータ転送は主にバス１７０を介して行われる。処理サーバ装置１００では、ＣＰＵ１１０がメモリ１２０を使用してグラフ解析プログラムを実行するとともに処理サーバ装置１００内部の動作を制御する。管理サーバ装置１０１では、ＣＰＵ１１０がメモリ１２０を使用して処理対象のグラフ頂点のクラスタリング、ネットワークトポロジの探索、及びルーティングパスの探索の各種プログラムを実行するとともに、スイッチ２００、光スイッチ３００、管理サーバ装置１０１内部の動作を制御する。【００１４】
メモリ１２０は、ＳＤＲＡＭなどの１次記憶であり、ＣＰＵ１１０がプログラムを実行する際に必要な命令やデータを保持する。ストレージ１３０は、ＨＤＤやＳＳＤといった２次記憶であり、プログラムやデータを長期間保持する他、メモリ１２０のスワップ領域としても利用される。後述のグラフデータ、クラスタリングデータ、トラフィックテーブル、トポロジテーブル、及びルーティングテーブルはストレージ１３０に保持される代表的なデータである。入力装置１４０は、マウスやキーボードなどであり、出力装置１５０は液晶パネルなどの表示装置やスピーカーなどである。ネットワークインタフェース１６０は他のサーバ装置との通信に利用されるものであり，Ｅｔｈｅｒｎｅｔ（登録商標）やＩｎｆｉｎｉＢａｎｄなどを用いることができる。【００１５】
図３は、スイッチ２００のブロック図である。スイッチ２００は、複数のポート２０１を備え、各ポート２０１を介して、処理サーバ装置１００、管理サーバ装置１０１、及び光スイッチ３００と接続される。スイッチ２００は、処理サーバ装置１００及び管理サーバ装置１０１が出力したパケットを受け付け、パケットのヘッダ中に含まれる宛先アドレスを読み出す。その後、読み出した宛先アドレスとルーティングテーブルから転送すべきポート２０１を決定し、クロスバスイッチ２０２の接続を切り替えてパケットを転送、出力する。破線２１０や１点鎖線２１１はパケット転送経路の例を示している。【００１６】
図４は、光スイッチ３００のブロック図である。光スイッチ３００は複数のポート３０１を備え、ポート３０１を介してスイッチ２００と接続される。光スイッチ３００は、ＭＥＭＳミラー３０２で光路を変更することで、ポート３０１間の接続を変更する。本実施例の光スイッチ３００は、パケットをルーティングする機能は持たないが、例えばＭＥＭＳミラー３０２をソフトウェア制御することでポート３０１間の接続の組み合わせを任意に設定可能な機能を持つスイッチである。破線３１０、１点鎖線３１１、点線３１２は光パスの例である。本実施例では、スイッチ２００間のネットワークトポロジの切り替えに光スイッチ３００を用いている。そして、並列計算機システム２０００では、スイッチ２００と光スイッチ３００とで、計算ノードである処理サーバ装置１００間を接続するネットワークトポロジを可変としている。【００１７】
次に、本実施例の並列計算機システム２０００におけるネットワークトポロジ変更フローについて説明する。図５は、並列計算機システム２０００のネットワークを後続のグラフ解析に適したトポロジへ変更させ、その後に解析を行うという一連の動作を示したフローチャートである。【００１８】
まず、管理サーバ装置１０１は、解析対象であるグラフデータをストレージ１３０から読み出す（Ｓ１００）。ここで指すグラフとは頂点及び辺からなる集合であり、例えば図６のように視覚的に表現できる。図６の円は頂点を意味し、円内の数字は頂点の番号を示している。また、辺は頂点を結ぶ線で表わされている。このグラフをデータ構造として表現したものがグラフデータであり、例えば、ある頂点（接続元頂点）に対して接続する頂点（接続先頂点）を並べた図７のようなデータである。【００１９】
次に、管理サーバ装置１０１は、読み出したグラフデータを基に各頂点をクラスタに割り当てるクラスタリング処理を行い、クラスタリング結果を示すクラスタリングデータを作成する（Ｓ１０１）。クラスタリングは、複数の処理サーバ装置１００でグラフ解析を並列に実行するためのグラフデータの割り当てを決めるものであり、並列処理を行う処理サーバ装置１００の数のクラスタを生成する。クラスタリングデータは、例えば、図８のような各クラスタに属する頂点番号を並べたものである。図８には、図６のグラフを８個のクラスタに分割した結果を示している。クラスタリング手法は、クラスタに対する頂点のランダムな割り当てでもよいし、より望ましくはクラスタを跨ぐ辺の数が少なくなるような割り当てを適用できる。【００２０】
クラスタリング処理では、管理サーバ装置１０１は、さらにクラスタ間のトラフィック量の見積もり結果であるトラフィックテーブルを作成する。グラフ解析では、頂点間で辺に沿ってトラフィックが発生するため、クラスタ間を跨ぐ辺の数をカウントし、１トラフィックのデータサイズを掛けることでトラフィックテーブルを容易に作成することができる。図９には、図８のクラスタリング結果に対するトラフィックテーブルを示している。ここでは、トラフィックのデータサイズを２４バイトとして計算している。２４バイトの内訳は、転送元頂点番号の情報が８バイト、転送先頂点番号の情報が８バイト、演算用の数値データが８バイトである。なお、入力データからトラフィックテーブルを作成することが可能ならば、あるいは、アプリケーションを複数回実行する場合に実測値からトラフィックテーブルを作成することが可能ならば、並列計算機システム２０００の処理対象はグラフ解析に限らない。【００２１】
次に、管理サーバ装置１０１は、トラフィックテーブルを入力としてネットワークトポロジの探索を行い、トポロジテーブルを作成する（Ｓ１０２）。この探索における目的関数は並列処理に関係する全処理サーバ装置１００間での最大のデータ転送時間を最小化することであり、制約条件はスイッチ２００と光スイッチ３００で利用するリンク数（＝コスト）である。この問題はＮＰ困難なクラスに属しており、現実的な時間で良い解を求めるために、本実施例では遺伝的アルゴリズムを利用しているが、他の手法を用いてもかまわない。遺伝的アルゴリズムによるネットワークトポロジ探索の詳細は後述する。トポロジテーブルは、例えば図１０のようなクラスタ間の接続を示すテーブルとなる。テーブル内の数値はクラスタ間のリンク数を意味する。参考として、図１０のトポロジテーブルで示されるトポロジを、スイッチ２００が８台、各スイッチ２００に処理サーバ装置１００が１台ずつ接続するシステムで構成した場合の光スイッチ３００内のパスを図１１に示す。ここで、処理サーバ装置１００内の数値は各処理サーバ装置１００へ割り当てたクラスタ番号を意味する。【００２２】
次に、管理サーバ装置１０１は、トラフィックテーブルとトポロジテーブルを入力として、ルーティングパスの探索を行い、ルーティングテーブルを作成する（Ｓ１０３）。この探索における目的関数は並列処理に関係する全処理サーバ装置１００間での最大のデータ転送時間を最小化することである。この問題もネットワークトポロジ探索と同様にＮＰ困難なクラスに属しており、現実的な時間で良い解を求めるために、本実施例では遺伝的アルゴリズムを利用しているが、他の手法を用いてもかまわない。遺伝的アルゴリズムによるルーティングパス探索の詳細は後述する。図示しないがルーティングテーブルは、スイッチ２００毎にポート番号と宛先アドレスを並べたテーブルであり、これにより、各スイッチ２００が、受け取ったパケットをどのポート２０１へ出力するかを一意に決定できる。【００２３】
次に、管理サーバ装置１０１は、トポロジテーブルで示されるトポロジを構成するように光スイッチ３００の制御を行うとともに、ルーティングテーブルを各スイッチ２００へ配布する（Ｓ１０４）。【００２４】
光スイッチ３００と各スイッチ２００の設定変更完了後、管理サーバ装置１０１の指示を受け、クラスタが割当てられている各処理サーバ装置１００は、グラフ解析などのアプリケーションを実行する（Ｓ１０５）。この際、各処理サーバ装置１００はクラスタリングデータを読み出すことで、どの処理サーバ装置１００でどの頂点が処理されるかを特定でき、複数の処理サーバ装置１００による並列処理が可能になる。【００２５】
以上が、所望のグラフ解析に適するようにネットワークトポロジを変更させ、その後に解析を行うという一連の動作フローであるが、同じグラフを用いてグラフ解析を複数回実行する場合は、二度目以降のグラフ解析はネットワークトポロジを変更する必要がないため、グラフ解析のみを繰り返して実行すれば良い。また、対象となるグラフデータがあればルーティングパス探索までの処理を事前に実施しておくことが可能であるため、グラフ解析の実行に先立ってその結果を参照し、光スイッチの制御とルーティングテーブルの配布のみを実行するようにしてもかまわない。【００２６】
ネットワークトポロジ探索とルーティングパス探索で利用する遺伝的アルゴリズムの処理フローを図１２に示す。始めにネットワークトポロジ探索について説明する。【００２７】
まず、管理サーバ装置１０１は、初期集団としてｎ個の遺伝子の作成を行う（Ｓ２００）。この際、ネットワークトポロジを効率良く探索できるようにスイッチ２００間のリンク情報を表す遺伝子を設計する必要がある。図１３にトポロジ遺伝子１０００の構成例を示す。トポロジ遺伝子１０００は、リンクの張られているスイッチ２００の識別番号のペアを染色体１００１として持ち、リンクの本数を染色体の長さで表現する。例えば、識別番号１のスイッチ２００の３つのポートは、それぞれ、識別番号２、３、６のスイッチ２００に接続されることが表現されている。初期集団の遺伝子はランダムに生成されるが、スイッチ２００に接続可能なリンク本数を超えるといったような、システム上実装できない遺伝子が生成された場合には、ネットワークトポロジ探索の効率の悪化を防ぐため、管理サーバ装置１０１は実装可能な遺伝子となるように修正を行う。【００２８】
次に、管理サーバ装置１０１は、遺伝子の適応度の計算を行う（Ｓ２０１）。まず、管理サーバ装置１０１は、トポロジ遺伝子１０００で表現されるネットワークトポロジに対し、各処理サーバ装置１００への最短経路探索でルーティングパスを決定する。次に、管理サーバ装置１０１は、そのルーティングパスに従いトラフィックテーブルに示されたデータ量を転送した場合の転送時間を見積もる。そして、管理サーバ装置１０１は、全処理サーバ装置１００間のデータ転送における最大の転送時間の逆数を適応度として求める。適応度をこのように定義することで、適応度を高くすることが、処理サーバ装置１００間のデータ転送時間のばらつきを抑え、かつ転送時間を削減することにつながる。このため、適応度の高いトポロジ遺伝子１０００は優秀なネットワークトポロジを表していることになる。【００２９】
次に、管理サーバ装置１０１は、現世代のｎ個の遺伝子と後述する交叉で生成した次世代候補のｎ個の遺伝子から次世代に残すｎ個の遺伝子の選択を行う（Ｓ２０２）。はじめてこの処理を行う場合は、次世代候補の遺伝子は存在しないため、現世代の遺伝子を選択することになる。遺伝子の選択は、適応度の高いものから残すエリート選択と適応度の高いものほど確率的に選ばれやすいルーレット選択を組み合わせて行うが、これらの選択を単体で用いる、あるいは他の選択を用いてもかまわない。【００３０】
次に、管理サーバ装置１０１は、ネットワークトポロジ探索の終了チェックを行う（Ｓ２０３）。終了条件は、最も適応度の高い個体が一定の世代以上更新されなかった場合、もしくは遺伝子の世代が一定以上となった場合であるが、適応度が閾値よりも高くなった場合など他の条件で終了してもかまわない。【００３１】
ステップＳ２０３で終了条件を満たさなかった場合、管理サーバ装置１０１は、次世代の遺伝子の候補を生成するために、遺伝子の交叉を行う（Ｓ２０４）。遺伝子の交叉は、染色体の交叉点を２箇所とする２点交叉で行うが、１点交叉や一様交叉などの他の交叉方法でもかまわない。本処理では、管理サーバ装置１０１は、次世代の候補となる遺伝子をｎ個生成する。なお、交叉によりシステム上実装できない遺伝子が生成された場合は、ネットワークトポロジ探索の効率の悪化を防ぐため、管理サーバ装置１０１は、実装可能な遺伝子となるように修正を行う。【００３２】
次に、管理サーバ装置１０１は、現世代の遺伝子と次世代候補の遺伝子に対し、染色体の値を一定の確率で変更する突然変異の処理を行う（Ｓ２０５）。但し、管理サーバ装置１０１は、現世代の遺伝子の中で適応度が最も高かった遺伝子には突然変異の処理を行わない。本実施例では、この処理と前述の遺伝子の選択（Ｓ２０２）でエリート選択を用いることで、世代を進めても最も適応度の高い個体が悪化することはない。【００３３】
突然変異（Ｓ２０５）後は、管理サーバ装置１０１は、再び適応度の計算（Ｓ２０１）へ処理を進める。なお、交叉と同様に、突然変異によりシステム上実装できない遺伝子が生成された場合は、ネットワークトポロジ探索の効率の悪化を防ぐために、管理サーバ装置１０１は、実装可能な遺伝子となるように修正を行う。【００３４】
次にルーティングパス探索の処理について説明する。ルーティングパス探索も、図１２に示したフローに従う。すなわち、管理サーバ装置１０１は、遺伝的アルゴリズムによる探索でルーティング規則の選択を行う。【００３５】
まず、管理サーバ装置１０１は、初期集団としてｎ個の遺伝子の作成を行う（Ｓ２００）。ある処理サーバ装置１００に対するルーティングパスはスイッチ２００間を接続するスパニングツリーとなるため、スパニングツリーを効率良く探索できるよう遺伝子を設計する必要がある。図１４にルーティング遺伝子１１００の構成例を示す。ルーティング遺伝子１１００は、染色体１１０１の位置とその値でスイッチ２００間のルーティングパスの存在を表現する。これにより、ルーティング遺伝子１１００にはルーティング規則が表現される。例えば、図１４の位置「１」にある「３」の値を持つ染色体は、識別番号１と識別番号３のスイッチ２００間でルーティングパスが存在することを示している。スイッチ２００の数をｌ個とすると、スパニングツリーはｌ−１本のパスで表現されるため、ルーティング遺伝子１１００の長さはｌ−１となる。また、転送先の各スイッチ２００に対し異なるスパニングツリーによってルーティングパスを決める場合、スイッチ２００の数をｍ個とすると、ルーティング遺伝子１１００の長さは（ｌ−１）×ｍとなる。【００３６】
初期集団の遺伝子として、１個はネットワークトポロジ探索で用いたルーティングパスとし、残りｎ−１個はランダムに生成する。本実施例では、ネットワークトポロジ探索で用いたルーティングパスは、最短経路探索で決定したルーティングパスである。なお、ランダムに生成する際、スパニングツリーとならない遺伝子が生成された場合には、ルーティングパス探索の効率の悪化を防ぐため、管理サーバ装置１０１は、実装可能な遺伝子となるように修正を行う。【００３７】
次に、管理サーバ装置１０１は、遺伝子の適応度の計算を行う（Ｓ２０１）。ルーティング遺伝子１１００が示すルーティングパスに従いトラフィックテーブルに示されたデータ量を転送した場合の転送時間を見積もる。そして、全処理サーバ装置１００間のデータ転送における最大の転送時間の逆数を適応度とする。適応度をこのように定義することで、適応度を高くすることが、処理サーバ装置１００間のデータ転送時間のばらつきを抑え、かつ転送時間を削減することにつながる。このため、適応度の高いルーティング遺伝子１１００は優秀なルーティングパスを表していることになる。【００３８】
次に、管理サーバ装置１０１は、現世代のｎ個の遺伝子と後述する交叉で生成した次世代候補のｎ個の遺伝子から次世代に残すｎ個の遺伝子の選択を行う（Ｓ２０２）。はじめてこの処理を行う場合は、次世代候補の遺伝子は存在しないため、現世代の遺伝子を選択することになる。遺伝子の選択は、適応度の高いものから残すエリート選択と適応度の高いものほど確率的に選ばれやすいルーレット選択を組み合わせて行うが、これらの選択を単体で用いる、あるいは他の選択を用いてもかまわない。【００３９】
次に、管理サーバ装置１０１は、ルーティングパス探索の終了チェックを行う（Ｓ２０３）。終了条件は、最も適応度の高い個体が一定の世代以上更新されなかった場合、もしくは遺伝子の世代が一定以上となった場合であるが、適応度が閾値よりも高くなった場合など他の条件で終了してもかまわない。【００４０】
ステップＳ２０３で終了条件を満たさなかった場合、管理サーバ装置１０１は、次世代の遺伝子の候補を生成するために、遺伝子の交叉を行う（Ｓ２０４）。遺伝子の交叉は、染色体の交叉点を２箇所とする２点交叉で行うが、１点交叉や一様交叉などの他の交叉方法でもかまわない。本処理では、管理サーバ装置１０１は、次世代の候補となる遺伝子をｎ個生成する。なお、交叉によりシステム上実装できない遺伝子が生成された場合には、ルーティング探索の効率の悪化を防ぐため、管理サーバ装置１０１は、実装可能な遺伝子となるように修正を行う。【００４１】
次に、管理サーバ装置１０１は、現世代の遺伝子と次世代候補の遺伝子に対し、染色体の値を一定の確率で変更する突然変異の処理を行う（Ｓ２０５）。但し、管理サーバ装置１０１は、現世代の遺伝子の中で適応度が最も高かった遺伝子には突然変異の処理を行わない。本実施例では、この処理と前述の遺伝子の選択（Ｓ２０２）でエリート選択を用いることで、世代を進めても最も適応度の高い個体が悪化することはない。【００４２】
突然変異後は、管理サーバ装置１０１は、再び適応度の計算（Ｓ２０１）へ処理を進める。なお、交叉と同様に、突然変異によりシステム上実装できない遺伝子が生成された場合には、ルーティング探索の効率の悪化を防ぐため、管理サーバ装置１０１は、実装可能な遺伝子となるように修正を行う。【００４３】
本実施例のルーティングパス探索では、初期集団の遺伝子としてネットワークトポロジ探索で用いたルーティングパスを含んでいること、遺伝子の選択でエリート選択を用いること、適応度が最も高い遺伝子に対しては突然変異を行わないことから、ネットワークトポロジ探索後にルーティングパス探索を行っても結果が悪化することはない。【００４４】
以上のように、本実施例のネットワークトポロジ探索方法では、サーバ装置間のトラフィック量を用いてデータ転送時間の最小化を目的としたネットワークトポロジの探索を行うことができる。さらに、決定したネットワークトポロジに対し、サーバ装置間のトラフィック量を用いてデータ転送時間の最小化を目的としたルーティングパスの探索を行うことで、ネットワークトポロジとルーティングパスの両方を効率良く探索することができ、現実的な時間でデータ転送時間最小化に対する準最適な解を求めることが可能になる。また、ネットワークトポロジの探索時に利用したルーティングアルゴリズムの結果をルーティングパス探索の評価基準として利用するため、ルーティングパス探索後のデータ転送時間は必ず探索前以下の数値となることを保証できる。
【符号の説明】
【００４５】
１００：処理サーバ装置、１０１：管理サーバ装置、１１０：ＣＰＵ、１２０：メモリ、１３０：ストレージ、１４０：入力装置、１５０：出力装置、１６０：ネットワークインタフェース、バス：１７０、２００：スイッチ、２０１：ポート、２０２：クロスバスイッチ、２１０、２１１：パケット転送経路、３００：光スイッチ、３０１：ポート、３０２：ＭＥＭＳミラー、３１０、３１１、３１２：光パス、１０００：トポロジ遺伝子、１００１：染色体、１１００：ルーティング遺伝子、１１０１：染色体。
【図１】
0005909595.tif 000002
【図２】
0005909595.tif 000003
【図３】
0005909595.tif 000004
【図４】
0005909595.tif 000005
【図５】
0005909595.tif 000006
【図６】
0005909595.tif 000007
【図７】
0005909595.tif 000008
【図８】
0005909595.tif 000009
【図９】
0005909595.tif 000010
【図１０】
0005909595.tif 000011
【図１１】
0005909595.tif 000012
【図１２】
0005909595.tif 000013
【図１３】
0005909595.tif 000014
【図１４】
0005909595.tif 000015