JP6623939B2 - 情報処理装置、通信手順決定方法、および通信プログラム - Google Patents

Description

本発明は、情報処理装置、通信手順決定方法、および通信プログラムに関する。

従来、ネットワーク内のサーバ、スイッチ等の機器がどのように接続されているかを示すトポロジー構造がある。また、複数の送信元のそれぞれが、トポロジー構造を経由して複数の宛先のいずれとも通信することができる場合、そのトポロジー構造を、全対全通信（Ａｌｌ−ｔｏ−Ａｌｌ通信）が可能なトポロジー構造と呼ぶことがある。さらに、経路競合なく全対全通信が行えるトポロジー構造がある。

関連する先行技術として、例えば、複数のノードとスイッチとを接続する第１のネットワークと、複数のノードを部分的に接続する第２のネットワークとを有するものがある。また、プログラム・タスクは、Ｎ＞１の階層レベルｌ_nを有し、ｎ＝１からＮである、階層型ネットワーク・トポロジを用いる相互接続ネットワークによって接続されるものがある。

特開２００９−０２０７９７号公報 特開２０１４−１６４７５６号公報

しかしながら、従来技術によれば、複数のトポロジー構造を組み合わせてネットワークを形成した際に、そのネットワークで経路競合なく全対全通信を行うことが難しい。例えば、１つのトポロジー構造を１つのスイッチと同一なものとみなすことにより、ネットワーク内の構成要素を減らして、経路競合なく全対全通信を行う通信手順を検討しやすくすることが考えられる。しかし、同数のポートを有する１つのスイッチと１つのトポロジー構造とを比較すると、入力ポートと出力ポートとの組み合わせによっては、スイッチでは競合なく全対全通信が可能であるのに対し、トポロジー構造では経路競合が発生することがある。従って、経路競合なく全対全通信を行う通信方法を検討する上では、１つのトポロジー構造を、１つのスイッチと同一なものとみなすことはできない。

１つの側面では、本発明は、複数のトポロジー構造を組み合わせて形成したネットワークにおいて、経路競合なく全対全通信が行える通信手順を決定することができる情報処理装置、通信手順決定方法、および通信プログラムを提供することを目的とする。

本発明の一側面によれば、出力ポートおよび複数の送信元のそれぞれが接続された入力ポートを第１の数分有する第２の数分の第１の種別の各トポロジー構造と入力ポートおよび複数の宛先のそれぞれが接続された出力ポートを第２の数分有する第１の数分の第２の種別の各トポロジー構造とがそれぞれ接続されたネットワーク内の各トポロジー構造の接続関係を示す接続情報と、第１の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせを示す第１の数分の転送パターンと、第２の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせが示される第２の数分の転送パターンとを記憶する記憶部を参照して、第１の数分の転送パターンのそれぞれと第２の数分の転送パターンのそれぞれとの組み合わせに対応して、接続情報が示すネットワークにおいて当該組み合わせの転送パターンが指定される際に複数の送信元のそれぞれから宛先までの経路を特定し、当該組み合わせに対応して特定した経路に基づいて、ネットワークにおいて複数の送信元のそれぞれから複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンと、ネットワーク内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する情報処理装置、通信手順決定方法、および通信プログラムが提案される。

本発明の一態様によれば、複数のトポロジー構造を組み合わせて形成したネットワークにおいて、経路競合なく全対全通信が行える通信手順を決定することができるという効果を奏する。

図１は、本実施の形態にかかる情報処理装置１０１の動作例を示す説明図である。 図２は、ラテン方陣Ｆａｔ−Ｔｒｅｅの一例を示す説明図である。 図３は、Ａｌｌ−ｔｏ−Ａｌｌ通信を行うためのスイッチの記憶内容の一例を示す説明図である。 図４は、情報処理装置１０１のハードウェア構成例を示す説明図である。 図５は、情報処理装置１０１の機能構成例を示す説明図である。 図６は、転送パターン表１１１の記憶内容の一例を示す説明図である。 図７は、実施例１における接続情報１１０Ｃの作成例を示す説明図である。 図８は、トポロジー構造Ｃの転送パターン表１１１Ｃの作成例を示す説明図である。 図９は、トポロジー構造Ｃ内の各トポロジー構造における出力ポート表１１２の作成例を示す説明図である。 図１０は、実施例２における接続情報１１０Ｃの作成例を示す説明図である。 図１１は、トポロジー構造の接続情報作成処理手順の一例を示す説明図である。 図１２は、転送パターン表および出力ポート表作成処理手順の一例を示す説明図である。 図１３は、実施例３における接続情報１１０Ｃの作成例を示す説明図である。

以下に図面を参照して、開示の情報処理装置、通信手順決定方法、および通信プログラムの実施の形態を詳細に説明する。

図１は、本実施の形態にかかる情報処理装置１０１の動作例を示す説明図である。情報処理装置１０１は、複数のトポロジー構造を組み合わせて形成したネットワークにおいて、経路競合なく全対全通信が行える通信手順を決定するコンピュータである。例えば、情報処理装置１０１は、ネットワークを管理する管理サーバである。

トポロジー構造は、サーバ、スイッチ等の機器がどのように接続されているかを示す。また、複数の送信元のそれぞれが、トポロジー構造を経由して複数の宛先のいずれとも通信することができる場合、そのトポロジー構造を、全対全通信が可能なトポロジー構造と呼ぶことがある。以下、全対全通信を、「Ａｌｌ−ｔｏ−Ａｌｌ通信」と呼称する。さらに、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行えるトポロジー構造がある。例えば、Ｆａｔ−Ｔｒｅｅ、多層ｆｕｌｌ−ｍｅｓｈ、ラテン方陣Ｆａｔ−Ｔｒｅｅは、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行えるトポロジー構造である。ラテン方陣Ｆａｔ−Ｔｒｅｅの一例については、図２を用いて説明する。また、ラテン方陣Ｆａｔ−Ｔｒｅｅについては、下記参考文献１に記載されている。
（参考文献１：Ｍ．Ｖａｌｅｒｉｏ、他２名、「Ｕｓｉｎｇ Ｆａｔ−Ｔｒｅｅｓ ｔｏ Ｍａｘｉｍｉｚｅ ｔｈｅ Ｎｕｍｂ ｅｒ ｏｆ Ｐｒｏｃｅｓｓｏｒｓ ｉｎ ａ Ｍａｓｓｉｖｅｌｙ Ｐａｒａｌｌｅｌ Ｃｏｍｐｕｔｅｒ」、ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ、１９９３）

また、２段Ｆａｔ−Ｔｒｅｅや、ラテン方陣Ｆａｔ−Ｔｒｅｅにおいては、入力サーバから出力サーバへの経路競合がないＡｌｌ−ｔｏ−Ａｌｌ通信が可能である。これを、経路競合なく片方向のＡｌｌ−ｔｏ−Ａｌｌ通信が可能と称する。また、逆の経路をたどることにより、出力サーバから入力サーバへのＡｌｌ−ｔｏ−Ａｌｌ通信が可能であるが、入力サーバ同士、または出力サーバ同士におけるＡｌｌ−ｔｏ−Ａｌｌ通信については、可能でなくてもよい。また、本実施の形態にかかるトポロジー構造は、入力ポートと出力ポートとの数が同一であるとする。

例えば、ＨＰＣ（Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｃｏｍｐｕｔｉｎｇ）において、高速フーリエ変換（ＦＦＴ：Ｆａｓｔ Ｆｏｕｒｉｅｒ Ｔｒａｎｓｆｏｒｍ）の並列分散処理を行う際に、低コストでより効率的にデータのやりとりを行うために、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行えるトポロジー構造が利用される。

ここで、スイッチポート数を増やさず、かつ、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を保ちつつ、より多くのサーバを接続したい場合、複数のトポロジー構造を組み合わせてネットワークを形成することが考えられる。しかしながら、複数のトポロジー構造を組み合わせてネットワークを形成した際に、そのネットワークで経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うことが難しい。例えば、１つのトポロジー構造を１つのスイッチと同一なものとみなすことにより、ネットワーク内の構成要素を減らして、経路競合なく全対全通信を行う通信手順を検討しやすくすることが考えられる。しかし、同数のポートを有する１つのスイッチと１つのトポロジー構造とを比較すると、入力ポートと出力ポートとの組み合わせによっては、スイッチでは競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が可能であるのに、トポロジー構造では経路競合が発生することがある。従って、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行う通信方法を検討する上では、１つのトポロジー構造を、１つのスイッチと同一なものとみなすことはできない。

入力ポートと出力ポートとの組み合わせによっては、スイッチでは競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が可能であるのに対し、トポロジー構造では経路競合が発生する例について説明する。例えば、あるトポロジー構造が、スイッチ１〜４を有し、スイッチ１〜４は、それぞれ、４つのポートを有するものとする。そして、スイッチ１が、スイッチ３、４と接続し、スイッチ２が、スイッチ３、４と接続するものとする。スイッチ１、２同士、スイッチ３、４同士は接続されていないものとする。この場合、スイッチ１〜４のそれぞれは、接続されていない空きポートが２つあるため、あるトポロジー構造は、８つのポートを有する仮想的なスイッチと見立てることができる。

ここで、８つのポートを有するスイッチでは、入力ポートと出力ポートとのいかなる組み合わせであっても、経路競合が発生することはない。しかしながら、前述のトポロジー構造では、スイッチ１の２つの空きポートの一方からスイッチ３の２つの空きポートの一方に通信すると同時に、スイッチ１の２つの空きポートの他方からスイッチ３の２つの空きポートの他方に通信すると、経路競合が発生する。

そこで、本実施の形態では、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を組み合わせて、新たなトポロジー構造の接続方法を提供する。そして、本実施の形態では、新たなトポロジー構造内の各トポロジー構造の転送パターンの組み合わせごとに特定した複数の送信元のそれぞれから宛先までの経路から、新たなトポロジー構造の転送パターンと各トポロジー構造の出力ポートを決定する。図１では、新たなトポロジー構造の転送パターンと各トポロジー構造の出力ポートを決定することについて説明する。

図１を用いて、情報処理装置１０１の動作例について説明する。ネットワーク１０２は、第１の種別のトポロジー構造Ａと、第２の種別のトポロジー構造Ｂとを組み合わせて形成されたネットワークである。ここで、ネットワーク１０２も、トポロジー構造とみなすことができる。以下の説明では、ネットワーク１０２を、「トポロジー構造Ｃ」として説明する。また、情報処理装置１０１は、トポロジー構造Ｃ内の一つのサーバであってもよいし、トポロジー構造Ｃの外部にあるサーバでもよい。トポロジー構造Ｃは、第２の数分のトポロジー構造Ａと、第１の数分のトポロジー構造Ｂとがそれぞれ接続された、２段構造のトポロジー構造である。第１の数と第２の数とは、同一の数でもよいし、異なる数でもよい。また、トポロジー構造Ａ、Ｂは、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行えるトポロジー構造である。また、トポロジー構造Ａ、Ｂは、同一の種別でもよいし、異なる種別でもよい。

ここで、トポロジー構造Ａは、入力ポートおよび出力ポートを第１の数分有する。そして、トポロジー構造Ｃは、トポロジー構造Ａを第２の数分有する。さらに、第２の数分のトポロジー構造Ａの各入力ポートには、入力サーバｓが接続される。従って、入力サーバｓの数は、第１の数に第２の数を乗じた分存在する。

一方、トポロジー構造Ｂは、入力ポートおよび出力ポートを第２の数分有する。そして、トポロジー構造Ｃは、トポロジー構造Ｂを第１の数分有する。さらに、第１の数分のトポロジー構造Ｂの各出力ポートには、出力サーバｔが接続される。従って、出力サーバｔの数は、第１の数に第２の数を乗じた分存在する。そして、入力サーバｓと出力サーバｔとの数は同一となる。

図１の例では、第１の数が２であり、第２の数が３となる場合の例を示す。図１に示すトポロジー構造Ｃには、トポロジー構造Ａ（＊，１）、Ａ（＊，２）、Ａ（＊，３）と、トポロジー構造Ｂ（１，＊）、Ｂ（２，＊）とを含む。以下、トポロジー構造や、トポロジー構造に関するものに付与する符号のうち、括弧内の文字列の部分を、括弧内符号と呼称する。例えば、トポロジー構造Ａ（＊，１）の括弧内符号は、「＊，１」となる。そして、トポロジー構造Ａ（＊，１）〜Ａ（＊，３）の各出力ポートｏｕｔＡ（１，１）〜ｏｕｔＡ（２，３）には、トポロジー構造Ｂ（１，＊）、Ｂ（２，＊）の各入力ポートｉｎＢ（１，１）〜ｉｎＢ（２，３）が接続される。具体的には、ｏｕｔＡ（１，１）〜ｏｕｔＡ（２，３）と、同一の括弧内符号を有するｉｎＢとが接続される。

また、トポロジー構造Ａ（＊，１）〜Ａ（＊，３）の各入力ポートｉｎＡ（１，１）〜ｉｎＡ（２，３）には、複数の送信元として入力サーバｓ（１，１）〜ｓ（２，３）がそれぞれ接続される。同様に、トポロジー構造Ｂ（１，＊）、Ｂ（２，＊）の各出力ポートｉｎＢ（１，１）〜ｉｎＢ（２，３）には、複数の宛先として出力サーバｔ（１，１）〜ｔ（２，３）がそれぞれ接続される。

情報処理装置１０１は、トポロジー構造Ｃ内の各トポロジー構造の接続関係を示す接続情報１１０Ｃと、トポロジー構造Ａの転送パターン表１１１Ａと、トポロジー構造Ｂの転送パターン表１１１Ｂとを記憶する。接続情報１１０Ｃは、具体的には、各トポロジー構造の接続関係として、トポロジー構造Ａの出力ポートｏｕｔＡが、どのトポロジー構造Ｂのどの入力ポートｉｎＢに接続しているか、入力サーバｓ、出力サーバｔがどのポートに接続されているかを示す。また、接続情報１１０Ｃは、トポロジー構造Ｃの管理者によって作成されたものでもよいし、後述するように、情報処理装置１０１が作成したものでもよい。または、トポロジー構造Ｃ内のサーバが、トポロジー構造Ｃ内の構造を検索するコマンドを実行することにより、接続情報１１０Ｃが作成されてもよい。

また、転送パターン表１１１Ａは、トポロジー構造Ａにおいて経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行う入力ポートと出力ポートとの組み合わせを示す第１の数分の転送パターンを有する。同様に、転送パターン表１１１Ｂは、トポロジー構造Ｂにおいて経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行う入力ポートと出力ポートとの組み合わせを示す第２の数分の転送パターンを有する。例えば、転送パターン表１１１Ａは、第１の数となる２つの転送パターンＰ１、Ｐ２を有する。例えば、転送パターンＰ１は、送信元が入力ポート１である場合に出力ポート１に転送し、送信元が入力ポート２である場合に出力ポート２に転送するパターンである。

情報処理装置１０１は、トポロジー構造Ｃで経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行う通信手順として、トポロジー構造Ｃの転送パターンと、トポロジー構造Ｃ内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する。まず、情報処理装置１０１は、転送パターン表１１１Ａの第１の数分の転送パターンのそれぞれと、転送パターン表１１１Ｂの第２の数分の転送パターンのそれぞれとの組み合わせを作成する。図１の場合では、情報処理装置１０１は、（Ｐ１，Ｑ１）、（Ｐ１，Ｑ２）、…、（Ｐ２，Ｑ３）という２・３＝６つの組み合わせを作成する。

そして、情報処理装置１０１は、作成した組み合わせに対応して、トポロジー構造Ｃにおいて、その組み合わせの転送パターンが指定される際に、複数の送信元のそれぞれから宛先までの経路を特定する。図１では、組み合わせとして、（Ｐ１，Ｑ２）に対応する経路を特定する例を示す。

ここで、ある組み合わせが入力サーバｓによって指定された場合、トポロジー構造Ａの全てが同一の転送パターンを実施し、トポロジー構造Ｂの全てが同一の転送パターンを実施する。例えば、（Ｐ１，Ｑ２）であれば、トポロジー構造Ａ（＊，１）〜Ａ（＊，３）は、転送パターンＰ１を実施し、トポロジー構造Ｂ（１，＊）、Ｂ（２，＊）は、転送パターンＰ２を実施する。

経路の特定方法について説明する。情報処理装置１０１は、複数の送信元のそれぞれについて、転送パターンＰ１、Ｐ２が実施される際の経路を特定する。図１では、（１）で示すように、送信元が入力サーバｓ（１，１）の場合の経路１２１を特定する例を示す。まず、情報処理装置１０１は、接続情報１１０Ｃを参照して、入力サーバｓ（１，１）が入力ポートｉｎＡ（１，１）に接続することを確認する。

そして、転送パターン表１１１を参照する際、情報処理装置１０１は、トポロジー構造に付与された括弧内符号のうちの「＊」がある位置の成分に着目する。例えば、トポロジー構造Ａ（＊，１）の場合、第１成分に「＊」があるため、情報処理装置１０１は、ｉｎＡ、ｏｕｔＡの第１成分に着目することになる。すなわち、情報処理装置１０１は、ｉｎＡ（１，１）を第１成分の「１」に着目し、ｉｎＡ（２，１）を第１成分の「２」に着目し、ｏｕｔＡ（１，１）を第１成分の「１」に着目し、ｏｕｔＡ（２，１）を第１成分の「２」に着目することになる。従って、情報処理装置１０１は、ｉｎＡ（１，１）からの送信が、転送パターン表１１１Ａにおける送信元「１」に相当するものと特定して、転送パターンＰ１における転送先「１」を特定する。そして、情報処理装置１０１は、ｉｎＡ（１，１）からの送信が、転送先「１」に相当するｏｕｔＡ（１，１）に転送されると特定する。

次に、情報処理装置１０１は、接続情報１１０Ｃを参照して、ｏｕｔＡ（１，１）と接続する入力ポートが、トポロジー構造Ｂ（１，＊）のｉｎＢ（１，１）であると特定する。そして、情報処理装置１０１は、転送パターン表１１１Ｂを参照して、トポロジー構造Ｂ（１，＊）のｉｎＢ（１，１）からの送信が、ｏｕｔＢ（１，２）に転送されることを特定する。ここで、トポロジー構造Ａ（＊，１）で行った説明と同様の手法により、情報処理装置１０１は、転送パターン表１１１Ｂを参照する際には、ｉｎＢ、ｏｕｔＢの第２成分に着目することになる。そして、情報処理装置１０１は、入力サーバｓ（１，１）からの送信が、最終的に、ｏｕｔＢ（１，２）に接続する出力サーバｔ（１，２）に転送されることを特定する。以上により、情報処理装置１０１は、入力サーバｓ（１，１）からｏｕｔＡ（１，１）、ｏｕｔＢ（１，２）を経由して出力サーバｔ（１，２）までの経路１２１を特定する。情報処理装置１０１は、他の入力サーバ、他の転送パターンについても同様の手法を行って、経路を特定する。

そして、情報処理装置１０１は、転送パターンの組み合わせに対応して特定した経路に基づいて、トポロジー構造Ｃにおける転送パターンと、トポロジー構造Ｃ内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する。トポロジー構造Ｃにおける転送パターンは、複数の送信元のそれぞれから複数の宛先のそれぞれまで経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行う転送パターンである。図１では、トポロジー構造Ｃにおける各転送パターンを、転送パターン表１１１Ｃとして示す。転送パターン表１１１Ｃは、送信元と転送パターンとの組み合わせに対応する宛先が登録される。

また、図１では、トポロジー構造Ａ（＊，１）における送信元と宛先との組み合わせに対応する出力ポートを、出力ポート表１１２Ａ（＊，１）として示す。情報処理装置１０１は、他のトポロジー構造として、トポロジー構造Ａ（＊，２）、Ａ（＊，３）、Ｂ（１，＊）、Ｂ（２，＊）についても、対応する出力ポート表１１２を作成するが、図１では、説明の簡略化のため省略する。

例えば、情報処理装置１０１は、図１の（２）で示すように、経路１２１に基づいて、（Ｐ１，Ｑ２）パターンにおける送信元と宛先の組み合わせとして、ｓ（１，１）とｔ（１，２）の組み合わせを決定する。ｓ（１，１）とｔ（１，２）の組み合わせは、転送パターン表１１１Ｃの一要素となる。従って、情報処理装置１０１は、転送パターン表１１１Ｃの対応する箇所に、「ｔ（１，２）」を登録する。

また、情報処理装置１０１は、経路１２１に基づいて、経路１２１上にあるトポロジー構造の出力ポートが、ｏｕｔＡ（１，１）、ｏｕｔＢ（１，２）であると特定する。従って、情報処理装置１０１は、トポロジー構造Ａ（＊，１）において、図１の（２）で示すように、ｓ（１，１）とｔ（１，２）との組み合わせに対応する出力ポートがｏｕｔＡ（１，１）であると決定する。従って、情報処理装置１０１は、出力ポート表１１２Ａの対応する箇所に、「ｏｕｔＡ（１，１）」を登録する。

特定した経路の全てに対して転送パターン表１１１、出力ポート表１１２の登録を終えた段階で、情報処理装置１０１は、転送パターン表１１１、出力ポート表１１２の作成を終了する。

以上により、入力サーバｓが、転送パターン表１１１に従って通信を行い、トポロジー構造Ｃ内の各トポロジー構造が、出力ポート表１１２に従って動作することにより、トポロジー構造Ｃで、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うことができる。

ここで図１では、トポロジー構造Ｃが構築された後の状態について説明したが、情報処理装置１０１は、接続情報１１０Ｃを作成してもよい。そして、トポロジー構造Ｃの管理者が、作成された接続情報１１０Ｃを閲覧して、トポロジー構造Ｃを構築することができる。具体的には、トポロジー構造Ｃの管理者は、作成された接続情報１１０Ｃから、トポロジー構造Ａの出力ポートを、トポロジー構造Ｂのどの入力ポートに結線すればよいかがわかる。接続情報１１０Ｃの作成例については、図７、図１０、図１３で説明する。なお、図１で説明した経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行う通信手順を決定する装置と、接続情報１１０Ｃを作成する装置とは、別であってもよい。この場合、接続情報１１０Ｃを作成する装置は、例えば、ＰＣ（Ｐｅｒｓｏｎａｌ Ｃｏｍｐｕｔｅｒ）でもよい。次に、ラテン方陣Ｆａｔ−Ｔｒｅｅの一例を、図２を用いて説明する。

図２は、ラテン方陣Ｆａｔ−Ｔｒｅｅの一例を示す説明図である。図２では、競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行えるトポロジー構造の一例として、ラテン方陣Ｆａｔ−Ｔｒｅｅにおける接続例を示す。図２で示す丸はサーバを示し、四角は、スイッチを示す。そして、丸の内部に「ｓ」を付与したサーバは、入力サーバを示す。また、丸の内部に「ｔ」を付与したサーバは、出力サーバを示す。一方、スイッチには、他のスイッチとサーバとを接続するＬｅａｆスイッチと、スイッチ同士を接続するＳｐｉｎｅスイッチとがある。入力サーバｓおよび出力サーバｔは、ＬｅａｆスイッチおよびＳｐｉｎｅスイッチを経由して通信を行う。経由したスイッチ数を「ホップ数」と定義する。

図２に示すラテン方陣Ｆａｔ−Ｔｒｅｅでは、入力サーバｓおよび出力サーバｔは、３ホップで通信可能であり、２段Ｆａｔ−Ｔｒｅｅよりも多くのサーバを接続することができる。

なお、図２に示すラテン方陣Ｆａｔ−ＴｒｅｅのＬｅａｆスイッチは、７つあるＳｐｉｎｅスイッチのうちのいずれか３つのＳｐｉｎｅスイッチと接続する。もし、Ｌｅａｆスイッチが全てのＳｐｉｎｅスイッチに接続する場合、そのトポロジー構造は、Ｆａｔ−Ｔｒｅｅとなる。

図３は、Ａｌｌ−ｔｏ−Ａｌｌ通信を行うためのスイッチの記憶内容の一例を示す説明図である。図３では、入力サーバｓ０〜ｓ８と、出力サーバｔ０〜ｔ８とが、Ｌｅａｆスイッチ１〜６、Ｓｐｉｎｅスイッチ１〜３のいずれか３つを経由して接続する例を示す。そして、図３では、Ｌｅａｆスイッチ１が有する記憶内容の一例を示す。

各スイッチは、送信元サーバおよび宛先サーバの組み合わせに対応した出力ポートを特定する情報を記憶する。Ｌｅａｆスイッチ１は、ポートｐ０〜ｐ５を有する。図３の例では、Ｌｅａｆスイッチ１が有する情報として、出力ポート表３０１を示す。出力ポート表３０１は、競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うために設定されたものである。出力ポート表３０１の縦のフィールドは、送信元サーバを示し、横のフィールドは宛先サーバを示す。また、出力ポート表３０１内の「−」で示した箇所は、該当のスイッチを経由しないので、どのポート番号に指定してもよいことを示す。

図３では、入力サーバｓ０が出力サーバｔ３と通信し、入力サーバｓ１が出力サーバｔ４と通信し、入力サーバｓ２が出力サーバｔ５と通信する例を示す。Ｌｅａｆスイッチ１は、入力サーバｓ０から出力サーバｔ３への通信を受信した場合、出力ポート表３０１を参照して、送信元サーバが入力サーバｓ０であり宛先サーバが出力サーバｔ３であることから、ポートｐ０を特定する。そして、Ｌｅａｆスイッチ１は、特定したポートｐ０を用いて入力サーバｓ０の通信を中継する。

また、Ｌｅａｆスイッチ１は、入力サーバｓ１から出力サーバｔ４への通信を受信した場合、出力ポート表３０１を参照して、送信元サーバが入力サーバｓ１であり宛先サーバが出力サーバｔ４であることから、ポートｐ１を特定する。また、Ｌｅａｆスイッチ１は、入力サーバｓ２から出力サーバｔ５への通信を受信した場合、出力ポート表３０１を参照して、送信元サーバが入力サーバｓ２であり宛先サーバが出力サーバｔ５であることから、ポートｐ２を特定する。Ｌｅａｆスイッチのポートｐ０〜ｐ２のそれぞれに接続するＳｐｉｎｅスイッチ１〜３も、Ｌｅａｆスイッチ１と同様に、自身が有する出力ポート表を参照して、送信元サーバおよび宛先サーバの組み合わせに対応した出力ポートを特定する。

以上により、入力サーバｓ０から出力サーバｔ３への通信経路は、図３に示す太い実線となる。同様に、入力サーバｓ１から出力サーバｔ４への通信経路は、図３に示す太い点線となり、入力サーバｓ２から出力サーバｔ５への通信経路は、図３に示す太い破線となる。このように、図３に示すように、各通信経路は、競合していないことがわかる。

（情報処理装置１０１のハードウェア構成例）
図４は、情報処理装置１０１のハードウェア構成例を示す説明図である。図４において、情報処理装置１０１は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）４０１と、ＲＯＭ（Ｒｅａｄ−Ｏｎｌｙ Ｍｅｍｏｒｙ）４０２と、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）４０３と、を含む。また、情報処理装置１０１は、ディスクドライブ４０４およびディスク４０５と、通信インターフェース４０６と、を含む。また、ＣＰＵ４０１〜ディスクドライブ４０４、通信インターフェース４０６はバス４０７によってそれぞれ接続される。

ＣＰＵ４０１は、情報処理装置１０１の全体の制御を司る演算処理装置である。ＲＯＭ４０２は、ブートプログラムなどのプログラムを記憶する不揮発性メモリである。ＲＡＭ４０３は、ＣＰＵ４０１のワークエリアとして使用される揮発性メモリである。

ディスクドライブ４０４は、ＣＰＵ４０１の制御に従ってディスク４０５に対するデータのリードおよびライトを制御する制御装置である。ディスクドライブ４０４には、例えば、磁気ディスクドライブ、光ディスクドライブ、ソリッドステートドライブなどを採用することができる。ディスク４０５は、ディスクドライブ４０４の制御で書き込まれたデータを記憶する不揮発性メモリである。例えばディスクドライブ４０４が磁気ディスクドライブである場合、ディスク４０５には、磁気ディスクを採用することができる。また、ディスクドライブ４０４が光ディスクドライブである場合、ディスク４０５には、光ディスクを採用することができる。また、ディスクドライブ４０４がソリッドステートドライブである場合、ディスク４０５には、半導体素子によって形成された半導体メモリ、いわゆる半導体ディスクを採用することができる。

通信インターフェース４０６は、トポロジー構造Ｃと内部のインターフェースを司り、他の装置からのデータの入出力を制御する制御装置である。具体的に、通信インターフェース４０６は、通信回線を通じてトポロジー構造Ｃを介して他の装置に接続される。通信インターフェース４０６には、例えば、モデムやＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）アダプタなどを採用することができる。

また、情報処理装置１０１の管理者が、情報処理装置１０１を直接操作する場合、情報処理装置１０１は、ディスプレイ、キーボード、マウスといったハードウェアを有してもよい。

また、情報処理装置１０１が接続情報１１０Ｃを作成する場合には、ユーザからの操作を受け付けるため、情報処理装置１０１は、キーボード、マウス、ディスプレイを有する。さらに、作成した接続情報１１０Ｃを出力するため、情報処理装置１０１は、プリンタを有してもよい。

（情報処理装置１０１の機能構成例）
図５は、情報処理装置１０１の機能構成例を示す説明図である。情報処理装置１０１は、制御部５００と、記憶部５１０とを有する。制御部５００は、複製部５０１と、設定部５０２と、作成部５０３と、特定部５０４と、決定部５０５と、送信部５０６とを含む。制御部５００は、記憶装置に記憶されたプログラムをＣＰＵ４０１が実行することにより、各部の機能を実現する。記憶装置とは、具体的には、例えば、図４に示したＲＯＭ４０２、ＲＡＭ４０３、ディスク４０５などである。また、各部の処理結果は、ＲＡＭ４０３、ＣＰＵ４０１のレジスタ、ＣＰＵ４０１のキャッシュメモリ等に格納される。

図５では、新たなトポロジー構造Ｃの接続情報１１０Ｃを作成する説明と、トポロジー構造Ｃにおいて、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行える通信手順を決定する説明とを行う。

さらに、本実施の形態では、実施例１として、２段のトポロジー構造から形成されるトポロジー構造Ｃに関する説明と、実施例２として、ｎ段のトポロジー構造から形成されるトポロジー構造Ｃに関する説明とを行う。また、実施例３として、双方向の経路競合のないＡｌｌ−ｔｏ−Ａｌｌ通信を提供できるトポロジー構造Ｃに関する説明を行う。実施例１については、図７〜図９でより詳細に説明する。また、実施例２については、図１０でより詳細に説明する。また、実施例３については、図１３でより詳細に説明する。

また、情報処理装置１０１は、記憶部５１０にアクセス可能である。記憶部５１０は、ＲＡＭ４０３、ディスク４０５といった記憶装置に格納される。記憶部５１０は、実施例１として、２段のトポロジー構造から形成されるトポロジー構造Ｃの接続情報１１０Ｃを作成する際には、トポロジー構造Ａを示す構造データ５１１Ａと、トポロジー構造Ｂを示す構造データ５１１Ｂとがあればよい。ここで、構造データ５１１Ａ、Ｂには、少なくとも、構造データ５１１Ａ、Ｂの入力ポートおよび出力ポートの数があればよい。また、実施例２、３でも同様に、記憶部５１０は、ｎを２以上のいずれかの整数として、トポロジー構造Ａ１を示す構造データ５１１Ａ１、トポロジー構造Ａ２を示す構造データ５１１Ａ２、…、トポロジー構造Ａｎを示す構造データ５１１Ａｎとがあればよい。

まず、トポロジー構造Ｃの接続情報１１０Ｃを作成する説明を行う。実施例１について、複製部５０１は、接続情報１１０Ｃの作成要求を受け付けた際に、構造データ５１１Ａを第２の数分複製し、第２の構造データ５１１Ｂを第１の数分複製する。

ここで、複製した構造データ５１１Ａと構造データ５１１Ｂとを接続した接続情報１１０Ｃを作成するが、接続する方法として、第１の方法と第２の方法とがある。

第１の方法として、作成部５０３は、複製した第２の数分の各構造データ５１１Ａの第１の数の出力ポートのそれぞれが、複製した第１の数分の各構造データ５１１Ｂの第２の数の入力ポートのいずれか一つと接続された接続関係を示す接続情報１１０Ｃを作成する。

また、第２の方法として、設定部５０２は、複製した第２の数分の各構造データ５１１Ａの第１の数の出力ポートの各出力ポートの識別情報（ＩＤ：ＩＤｅｎｔｉｆｉｅｒ）を、各構造データ５１１Ａ内で各出力ポートを識別する値と第２の数に基づいた値との順に結合した情報に設定する。さらに、設定部５０２は、複製した第１の数分の構造データ５１１Ｂの各構造データＢの第２の数の入力ポートの各入力ポートｉｎＢのＩＤを、第２の数に基づいた値と各第２の構造データ内で各入力ポートを識別する値との順に結合した情報に設定する。

例えば、設定部５０２の処理について、図１を用いて説明する。まず、複製部５０１が、第２の数として、３つの構造データＡ（＊，１）、Ａ（＊，２）、Ａ（＊，３）を複製する。そして、設定部５０２は、例えば、構造データＡ（＊，１）の各出力ポートのＩＤを、構造データＡ（＊，１）内で各出力ポートを識別する値と、第２の数に基づく１〜３のいずれか一つの値とを結合した情報に設定する。構造データＡ（＊，１）内で各出力ポートを識別する値は、１、２のいずれかとなる。また、第２の数に基づく１〜３のいずれか一つの値は、構造データＡ（＊，１）の第２成分と同一の値となる「１」とする。結果として、設定部５０２は、構造データＡ（＊，１）の各出力ポートｏｕｔＡのＩＤを、それぞれ、ｏｕｔＡ（１，１）、ｏｕｔＡ（１，２）に設定する。

そして、作成部５０３は、同一のＩＤを有する出力ポートと入力ポートとが接続された接続関係を示す接続情報１１０Ｃを作成する。具体的には、接続情報１１０Ｃは、第２の数分の各構造データ５１１Ａの第１の数の出力ポートの各出力ポートと、第１の数分の各構造データ５１１Ｂの第２の数の入力ポートのうち当該各出力ポートと同一のＩＤを有する入力ポートとが接続されることを示す。

次に、実施例２について説明する。複製部５０１は、ｎを２以上のいずれかの自然数とし、ｎ種類のトポロジー構造を有するトポロジー構造Ｃ内の各トポロジー構造の接続関係を示す接続情報１１０Ｃの作成要求を受け付ける。この際、複製部５０１は、ｉを１からｎまでのいずれかの自然数として、第ｉの種別のトポロジー構造を示す第ｉの構造データを、第１の数から第ｎの数までを乗じた値から第ｉの数で除した数分複製する。

設定部５０２は、まず、複製した第ｉの構造データの各入力ポートと各出力ポートとに対応する、ＩＤとなる数列を生成する。その数列は、第１の数から第ｎの数までの数群のうち第ｉの数を除く数に基づいた（ｎ−１）桁の数列のｉ番目に、第ｉの構造データ内で各入力ポートまたは各出力ポートを識別する値を挿入した数列である。そして、設定部５０２は、複製した第ｉの構造データの各入力ポートと各出力ポートとのＩＤを、生成した数列に設定する。

ここで、設定部５０２の処理について説明する。設定部５０２は、第１の数から第ｎの数までの数群のうち第ｉの数を除く数に基づいて、複製した第ｉの構造データのそれぞれを識別する数列を生成する。例えば、設定部５０２は、（１から第１の数までのいずれかの自然数，…，１から第（ｉ−１）の数までのいずれかの自然数，１から第（ｉ＋１）の数までのいずれかの自然数，…，１から第ｎの数までのいずれかの自然数）というｎ−１桁の数列を生成する。この数列が取り得る値の個数は、ちょうど第ｉの構造データを複製した数に一致するため、生成した数列を複製した第ｉの構造データのそれぞれに設定することにより、複製した第ｉの構造データのそれぞれを識別することができる。そして、設定部５０２は、生成した数列のｉ番目に、第ｉの構造データ内で各入力ポートまたは各出力ポートを識別する値として、１から第１の数までのいずれかの数を挿入した数列を生成し、各入力ポートまたは各出力ポートに設定する。以上により、複製した第１の構造データから第ｎの構造データの各入力ポートは、全て異なるＩＤが設定されることになる。出力ポートについても同様である。

作成部５０３は、同一のＩＤを有する出力ポートと入力ポートとが接続された接続関係を示す接続情報１１０Ｃを作成する。具体的には、接続情報１１０Ｃは、第ｊの構造データの各第ｊの構造データの第ｊの数の各出力ポートが、第（ｊ＋１）の構造データの第（ｊ＋１）の数の入力ポートのうち当該各出力ポートと同一のＩＤを有する入力ポートと接続されることを示す。ここで、ｊは、１から（ｎ−１）までのいずれかの自然数とする。

次に、実施例３について説明する。実施例３では、複製部５０１〜作成部５０３が行う処理については実施例２と変わらないが、トポロジー構造Ｃの各トポロジー構造が、以下に示す３つの条件の全てを満たすものとなる。１つ目の条件は、トポロジー構造Ｃの段数を３以上のいずれかの奇数とすることである。２つ目の条件は、ｉを１から（（ｎ−１）／２）までのいずれかの自然数とし、トポロジー構造Ｃに含まれる第ｉの種別のトポロジー構造が、第（ｎ−ｉ＋１）種別のトポロジー構造を逆さにしたトポロジー構造であることである。ここで、逆さにしたトポロジー構造とは、あるトポロジー構造と、他のトポロジー構造を、ある直線を介して並べた際に、ある直線を軸として線対称となる関係にあるトポロジー構造である。例えば、ｎ＝５である場合、第１の種別のトポロジー構造と第５の種別のトポロジー構造とが逆さの関係にあり、かつ、第２の種別のトポロジー構造と第４の種別のトポロジー構造とが逆さの関係にある。３つ目の条件は、第（（ｎ＋１）／２）種別のトポロジー構造が、スイッチ同士を接続する複数のスイッチを有し、かつ、複数のスイッチのそれぞれを結ぶ線を軸として線対称となる構造となることである。この複数のスイッチは、図２で示したＳｐｉｎｅスイッチである。

次に、トポロジー構造Ｃにおいて、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行える通信手順を決定する説明を行う。経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行う際には、記憶部５１０は、接続情報１１０Ｃと、転送パターン表１１１Ａ、Ｂがあればよい。

実施例１〜３について、特定部５０４は、第１の数分の転送パターンのそれぞれと第２の数分の転送パターンのそれぞれとの組み合わせを生成する。そして、特定部５０４は、生成した組み合わせに対応して、接続情報１１０Ｃが示すトポロジー構造Ｃにおいて当該組み合わせの転送パターンが指定される際に複数の送信元のそれぞれから宛先までの経路を特定する。実施例１、２では、特定部５０４は、１つの組み合わせに対して、送信元の数分の経路を特定する。

さらに、実施例３では、第（（ｎ＋１）／２）種別のトポロジー構造に含まれる複数のスイッチで複数の送信元のそれぞれからの通信が折り返される場合における複数の送信元のそれぞれから宛先までの経路を特定する。従って、実施例３では、１つの組み合わせに対して、送信元の数の２倍の分の経路を特定する。

決定部５０５は、組み合わせに対応して特定した経路に基づいて、トポロジー構造Ｃにおいて複数の送信元のそれぞれから複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンを決定する。また、決定部５０５は、組み合わせに対応して特定した経路に基づいて、トポロジー構造Ｃ内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する。

送信部５０６は、トポロジー構造Ｃにおいて複数の送信元のそれぞれから複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンを、複数の送信元のそれぞれに送信する。また、送信部５０６は、トポロジー構造Ｃ内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートを示す情報を、各トポロジー構造に含まれるスイッチ群に送信する。

図６は、転送パターン表１１１の記憶内容の一例を示す説明図である。図６では、一例として、入力ポートおよび出力ポートをそれぞれ２つ有するトポロジー構造Ａの転送パターン表１１１Ａを示す。また、図６では、トポロジー構造Ａの２つの入力ポートを、それぞれｉｎＡ（１）、ｉｎＡ（２）とし、トポロジー構造Ａの２つの出力ポートを、それぞれｏｕｔＡ（１）、ｏｕｔＡ（２）とする。

転送パターン表１１１Ａは、転送パターンＰ１、Ｐ２を有する。転送パターンＰ１は、ｉｎＡ（１）から受信したデータを、ｏｕｔＡ（１）を用いて転送し、ｉｎＡ（２）から受信したデータを、ｏｕｔＡ（２）を用いて転送するパターンである。また、転送パターンＰ２は、ｉｎＡ（２）から受信したデータを、ｏｕｔＡ（１）を用いて転送し、ｉｎＡ（１）から受信したデータを、ｏｕｔＡ（２）を用いて転送するパターンである。図６では、転送パターンＰ１に従ったデータ転送の流れを、実線の矢印で示し、転送パターンＰ２に従ったデータ転送の流れを、破線の矢印で示す。

（実施例１）
実施例１では、送信元サーバ、宛先サーバがともにａ台のトポロジー構造Ａと、送信元サーバ、宛先サーバがともにｂ台のトポロジー構造Ｂとが与えられており、それぞれ競合のない転送パターンＰｉ（１≦ｉ≦ａ）、Ｑｊ（１≦ｊ≦ｂ）が与えられているとする。この場合に、情報処理装置１０１は、新たなトポロジー構造Ｃであって、次の３つの条件を満たすものを作成する。１つ目の条件は、トポロジー構造Ｃで用いる各スイッチが、トポロジー構造Ａ、Ｂと同じであることである。２つ目の条件は、トポロジー構造Ｃにおける送信元サーバから宛先サーバまでのホップ数が、トポロジー構造Ａ、Ｂのホップ数を合計した値となることである。３つ目の条件は、トポロジー構造Ｃでは、経路競合なく片方向のＡｌｌ−ｔｏ−Ａｌｌ通信が可能であることである。

図７は、実施例１における接続情報１１０Ｃの作成例を示す説明図である。まず、情報処理装置１０１は、構造データ５１１Ａを、ｂ個複製する。そして、情報処理装置１０１は、複製した構造データ５１１ＡのＩＤを、それぞれＡ（＊，１）、Ａ（＊，２）、…、Ａ（＊，ｂ）に設定する。また、情報処理装置１０１は、Ａ（＊，ｊ）（１≦ｊ≦ｂ）のａ個の入力ポート、出力ポートを、それぞれ、ｉｎＡ（１，ｊ）、ｏｕｔＡ（１，ｊ）、ｉｎＡ（２，ｊ）、ｏｕｔＡ（２，ｊ）、…、ｉｎＡ（ａ，ｊ）、ｏｕｔＡ（ａ，ｊ）と設定する。

同様に、情報処理装置１０１は、構造データ５１１Ｂを、ａ個複製する。そして、情報処理装置１０１は、複製した構造データ５１１ＢのＩＤを、それぞれＢ（１，＊）、Ｂ（２，＊）、…、Ｂ（ａ，＊）に設定する。また、情報処理装置１０１は、Ｂ（ｉ，＊）（１≦ｊ≦ｂ）のｂ個の入力ポート、出力ポートを、それぞれ、ｉｎＢ（ｉ，１）、ｏｕｔＢ（ｉ，１）、ｉｎＢ（ｉ，２）、ｏｕｔＢ（ｉ，２）…、ｉｎＢ（ｉ，ｂ）、ｏｕｔＢ（ｉ，ｂ）と設定する。

そして、情報処理装置１０１は、同一の括弧内符号となるｏｕｔＡ（ｉ，ｊ）、ｉｎＢ（ｉ，ｊ）を同一のリンクとして接続する。または、情報処理装置１０１は、Ａ（＊，ｊ）の「＊，ｊ」と一致する括弧内符号を有する構造データ５１１Ｂを、Ａ（＊，ｊ）と接続する構造データ５１１Ｂとして特定してもよい。ここで、「＊」は、どの数値でも一致とみなす記号であるとする。実施例１の場合、Ａ（＊，１）、Ａ（＊，２）、…、Ａ（＊，ｂ）それぞれが、Ｂ（１，＊）、Ｂ（２，＊）、…、Ｂ（ａ，＊）それぞれに接続することになる。

次に、情報処理装置１０１は、Ａ（＊，ｊ）（１≦ｊ≦ｂ）の上位リンクに、入力サーバｓ（ｉ，ｊ）を接続する。また、情報処理装置１０１は、Ｂ（ｉ，＊）（１≦ｉ≦ａ）の下位リンクに、出力サーバｔ（ｉ，ｊ）を接続する。

図７の例では、ａ＝２、ｂ＝３となる場合のトポロジー構造Ｃを示す。図７で示すように、Ａ（＊，１）、Ａ（＊，２）、Ａ（＊，３）それぞれが、Ｂ（１，＊）、Ｂ（２，＊）それぞれに接続する。情報処理装置１０１は、トポロジー構造Ａ、Ｂそれぞれの接続関係を示す接続情報１１０Ｃを出力する。トポロジー構造Ｃの管理者は、出力された結線表に従って、トポロジー構造Ｃの構築を行う。

次に、構築されたトポロジー構造Ｃにおいて経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うために作成する表の作成例について、図８、図９を用いて説明する。図８では、トポロジー構造Ｃの転送パターン表を作成する例を説明し、図９では、トポロジー構造Ｃに含まれる各スイッチの出力ポート表を作成する例を説明する。

図８は、トポロジー構造Ｃの転送パターン表１１１Ｃの作成例を示す説明図である。情報処理装置１０１は、トポロジー構造Ｃの接続情報１１０Ｃと、トポロジー構造Ａの転送パターン表１１１Ａと、トポロジー構造Ｂの転送パターン表１１１Ｂとを用いて、トポロジー構造Ｃの転送パターン表を作成する。ここで、転送パターン表１１１Ａは、ａ個の転送パターンを有し、転送パターン表１１１Ｂは、ｂ個の転送パターンを有する。以下、転送パターン表１１１Ａが有するａ個の転送パターンを、Ｐ１、Ｐ２、…、Ｐａとする。同様に、転送パターン表１１１Ｂが有するｂ個の転送パターンを、Ｑ１、Ｑ２、…、Ｑｂとする。

情報処理装置１０１は、全部でａ×ｂの転送パターンがあるため、接続情報１１０Ｃに従って、（Ｐｉ，Ｑｊ）（ｉ＝１，２，…，ａ、ｊ＝１，２，…，ｂ）パターンを実施し、各パターンに対応する入力サーバｓの宛先となる出力サーバｔを特定する。ここで、（Ｐｉ，Ｑｉ）パターンとは、トポロジー構造Ｃ内の全てのＡ（＊，ｊ）（ｊ＝１，２，…，ｂ）では、転送パターンＰｉを実施し、全てのＢ（ｉ，＊）（ｉ＝１，２，…，ａ）では、転送パターンＱｊを実施するパターンである。そして、情報処理装置１０１は、特定した出力サーバｔから、転送パターンと送信元との組み合わせに対応した出力サーバｔを示す、トポロジー構造Ｃの転送パターン表１１１Ｃを作成する。以下、図８を用いて、（Ｐｉ，Ｑｊ）パターンの一例を示し、転送パターン表１１１Ｃの作成例を示す。

図８で示すトポロジー構造Ｃが有する全ての転送パターンは、ａ＝２、ｂ＝３であるから、６つの転送パターンが生成される。図８では、６つの転送パターンのうち、（Ｐ１，Ｑ２）パターンについて説明する。まず、送信元が入力サーバｓ（１，１）の例を示す。情報処理装置１０１は、転送パターンＰ１の場合、転送パターン表１１１Ａを参照して、トポロジー構造Ａ（＊，１）のｉｎＡ（１，１）からの送信が、ｏｕｔＡ（１，１）に転送されることを特定する。

ここで、図１で説明したように、転送パターン表１１１を参照する際、情報処理装置１０１は、トポロジー構造に付与された括弧内符号のうちの「＊」がある位置の成分に着目する。従って、情報処理装置１０１は、ｉｎＡ（１，１）からの送信が、転送パターン表１１１Ａにおける送信元「１」に相当するものと特定して、転送パターンＰ１における転送先「１」を特定する。そして、情報処理装置１０１は、ｉｎＡ（１，１）からの送信が、転送先「１」に相当するｏｕｔＡ（１，１）に転送されると特定する。

次に、情報処理装置１０１は、接続情報１１０Ｃを参照して、ｏｕｔＡ（１，１）と接続する入力ポートが、トポロジー構造Ｂ（１，＊）のｉｎＢ（１，１）であると特定する。そして、情報処理装置１０１は、転送パターン表１１１Ｂを参照して、トポロジー構造Ｂ（１，＊）のｉｎＢ（１，１）からの送信が、ｏｕｔＢ（１，２）に転送されることを特定する。ここで、トポロジー構造Ａ（＊，１）で行った説明と同様の手法により、情報処理装置１０１は、転送パターン表１１１Ｂを参照する際には、ｉｎＢ、ｏｕｔＢの第２成分に着目することになる。そして、情報処理装置１０１は、入力サーバｓ（１，１）からの送信が、最終的に、ｏｕｔＢ（１，２）に接続する出力サーバｔ（１，２）に転送されることを特定する。

以上の処理により、情報処理装置１０１は、（Ｐ１，Ｑ２）パターンにおける、ｓ（１，１）からｔ（１，２）までの経路８０１を特定する。

経路８０１が特定できたため、情報処理装置１０１は、経路８０１に基づいて、（Ｐ１，Ｑ２）パターンにおけるｓ（１，１）とｔ（１，２）の組み合わせを決定する。ｓ（１，１）とｔ（１，２）の組み合わせは、転送パターン表１１１Ｃの一要素となる。従って、情報処理装置１０１は、転送パターン表１１１Ｃの対応する箇所に、「ｔ（１，２）」を登録する。同様に、図８では、情報処理装置１０１は、送信元が入力サーバｓ（２，２）であれば宛先は出力サーバｔ（２，３）となることを特定する。従って、情報処理装置１０１は、（Ｐ１，Ｑ２）パターンにおける、ｓ（２，２）からｔ（２，３）までの経路８０２を特定する。経路８０２が特定できたため、情報処理装置１０１は、転送パターン表１１１Ｃの対応する箇所に、「ｔ（２，３）」を登録する。情報処理装置１０１は、他の送信元、他の転送パターンについても同様な手順を行い、転送パターン表１１１Ｃの各宛先を全て登録する。

転送パターン表１１１Ｃの各宛先を全て登録した際に、情報処理装置１０１は、６つの入力サーバｓに、転送パターン表１１１Ｃを送信する。

図９は、トポロジー構造Ｃ内の各トポロジー構造における出力ポート表１１２の作成例を示す説明図である。情報処理装置１０１は、転送パターン表１１１Ｃの各宛先を設定する処理と併せて、各スイッチの出力ポート表を作成する処理を実行する。図９では、トポロジー構造Ａ（＊，１）の出力ポート表１１２Ａ（＊，１）と、トポロジー構造Ｂ（１，＊）の出力ポート表１１２Ｂ（１，＊）との作成例について示す。

図９の例では、情報処理装置１０１が、経路８０１を特定した後の状態である。この場合、情報処理装置１０１は、経路８０１上にあるトポロジー構造の出力ポートを特定する。例えば、情報処理装置１０１は、トポロジー構造Ａ（＊，１）について、経路８０１上にあるトポロジー構造の出力ポートが、ｏｕｔＡ（１，１）であることを特定する。従って、情報処理装置１０１は、出力ポート表１１２Ａ（＊，１）に、「ｏｕｔＡ（１，１）」を、送信元ｓ（１，１）と宛先ｔ（１，２）との組み合わせに対応付けて登録する。同様に、情報処理装置１０１は、トポロジー構造Ｂ（１，＊）について、経路８０１上にあるトポロジー構造の出力ポートが、ｏｕｔＢ（１，２）であることを特定する。従って、情報処理装置１０１は、出力ポート表１１２Ｂ（１，＊）に、「ｏｕｔＢ（１，２）」を、送信元ｓ（１，１）と宛先ｔ（１，２）との組み合わせに対応付けて登録する。

同様に、情報処理装置１０１は、トポロジー構造Ｃ内の各トポロジー構造について、送信元と宛先との組み合わせに対応する出力ポートが特定できた際に、各トポロジー構造の出力ポート表１１２Ｂにおける対応する箇所に、特定した出力ポートを設定する。そして、各トポロジー構造の各出力ポートの全てを設定した際に、情報処理装置１０１は、各トポロジー構造に対応する出力ポート表１１２を、各トポロジー構造に送信する。

６つの入力サーバｓに転送パターン表１１１Ｃを送信し、各トポロジー構造に対応する出力ポート表１１２を各トポロジー構造に送信することにより、６つの入力サーバｓは、経路競合のないＡｌｌ−ｔｏ−Ａｌｌ通信を行うことができる。

次に、実施例１で説明したトポロジー構造Ｃが、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行えることの証明について説明する。ここで、送信元サーバｓ（ｘ，ｙ）から宛先サーバｔ（ｚ，ｗ）へ送信される回数を数える。まず、送信元サーバｓ（ｘ，ｙ）から送信されるトポロジー構造は、トポロジー構造Ｃ内のトポロジー構造Ａ（＊，ｙ）に限られる。同様に、宛先サーバｔ（ｚ，ｗ）へ送信されるトポロジー構造は、トポロジー構造Ｃ内のトポロジー構造Ｂ（ｚ，＊）に限られる。そして、トポロジー構造Ａ（＊，ｙ）と、トポロジー構造Ｂ（ｚ，＊）とは、ｏｕｔＡ（ｚ，ｙ）＝ｉｎＢ（ｚ，ｙ）という、ただ一つのリンクにより結ばれる。よって、送信元サーバｓ（ｘ，ｙ）から宛先サーバｔ（ｚ，ｗ）へ送信される回数は、１回に限られる。

（実施例２）
実施例１では、トポロジー構造Ａ、Ｂという２段から形成されるトポロジー構造Ｃの例を説明したが、実施例２では、３段以上のトポロジー構造から形成されるトポロジー構造の例について説明する。

図１０は、実施例２における接続情報１１０Ｃの作成例を示す説明図である。実施例２では、送信元サーバ、宛先サーバがともにａ１台のトポロジー構造Ａ１、送信元サーバ、宛先サーバがともにａ２台のトポロジー構造Ａ２、…、送信元サーバ、宛先サーバがともにａｎ台のトポロジー構造Ａｎが与えられているとする。また、ｎは、２以上の整数である。ｎが２の場合には、実施例１と同様のトポロジー構造が得られることになる。

まず、情報処理装置１０１は、ｎ段のトポロジー構造から形成される新たなトポロジー構造Ｃの入力サーバ、出力サーバの台数Ｐを、ａ１・ａ２・…・ａｎとする。そして、情報処理装置１０１は、トポロジー構造Ａｉを示す構造データ５１１Ａｉ（ｉ＝１，２，…，ｎ）を、Ｐ／Ａｉ個複製する。

そして、情報処理装置１０１は、複製した構造データ５１１ＡｉのＩＤを、Ａｉ（ｊ１，ｊ２，…，ｊ（ｉ−１），＊，ｊ（ｉ＋１），…，ｊｎ）に設定する。「ｊ１，ｊ２，…，ｊ（ｉ−１），＊，ｊ（ｉ＋１），…，ｊｎ」という数列は、ｉ番目の成分が「＊」であり、他の成分が、ｊｋ（ｋ＝１，２，…，ｎ）は、１≦ｊｋ≦ａｋを満たす。ｊの取り得る個数を計算すると、Ｐ／Ａｉに一致することになる。

また、情報処理装置１０１は、Ａ（ｊ１，ｊ２，…，ｊ（ｉ−１），＊，ｊ（ｉ＋１），…，ｊｎ）の入力ポートを、ｉｎＡｉ（ｊ１，ｊ２，…，ｊ（ｉ−１），ｋ，ｊ（ｉ＋１），…，ｊｎ）（ｋ＝１，２，…，ａｉ）と設定する。同様に、情報処理装置１０１は、Ａ（ｊ１，ｊ２，…，ｊ（ｉ−１），＊，ｊ（ｉ＋１），…，ｊｎ）の出力ポートを、ｏｕｔＡｉ（ｊ１，ｊ２，…，ｊ（ｉ−１），ｋ，ｊ（ｉ＋１），…，ｊｎ）（ｋ＝１，２，…，ａｉ）と設定する。

次に、情報処理装置１０１は、同一の括弧内符号となるｏｕｔＡｉと、ｉｎＡ（ｉ＋１）とを同一のリンクとして接続する。または、情報処理装置１０１は、Ａｉの括弧内符号と一致する括弧内符号を有する構造データ５１１Ａ（ｉ＋１）を、Ａｉと接続する構造データ５１１として特定してもよい。

ここで、図１０を用いて、入力ポートと出力ポートとの接続処理の具体例について示す。図１０では、ｎ＝３であり、ａ１＝ａ２＝ａ３＝２であるとする。従って、Ｐ＝２・２・２＝８となる。次に、情報処理装置１０１は、構造データ５１１Ａ１〜Ａ３について、それぞれ４つ複製する。情報処理装置１０１は、複製した４つのＡ１のＩＤを、Ａ１（＊，１，１）、Ａ１（＊，１，２）、Ａ１（＊，２，１）、Ａ１（＊，２，２）と設定する。同様に、情報処理装置１０１は、複製した４つのＡ２のＩＤを、Ａ２（１，＊，１）、Ａ２（１，＊，２）、Ａ２（２，＊，１）、Ａ２（２，＊，２）と設定する。また、情報処理装置１０１は、複製した４つのＡ３のＩＤを、Ａ３（１，１，＊）、Ａ３（１，２，＊）、Ａ３（２，１，＊）、Ａ２（２，２，＊）と設定する。また、情報処理装置１０１は、Ａ１（＊，１，１）の入力ポート、出力ポートを、それぞれ、ｉｎＡ１（１，１，１）、ｉｎＡ１（２，１，１）、ｏｕｔＡ１（１，１，１）、ｏｕｔＡ１（２，１，１）、と設定する。情報処理装置１０１は、他の入力ポート、出力ポートについても同様の命令ルールによりＩＤを設定する。

そして、情報処理装置１０１は、同一の括弧内符号となるｏｕｔＡｉと、ｉｎＡ（ｉ＋１）とを同一のリンクとして接続する。例えば、ｏｕｔＡ１（１，１、１）と、ｉｎＡ２（１，１，１）とを同一のリンクとして接続する。または、情報処理装置１０１は、Ａｉの括弧内符号と一致する括弧内符号を有する構造データ５１１Ａ（ｉ＋１）を、Ａｉと接続する構造データ５１１として特定してもよい。例えば、Ａ１（＊，１，１）と同一の括弧内符号を有するＡ２は、Ａ２（１，＊，１）と、Ａ２（２，＊，１）とになる。このように、３段以上のトポロジー構造では、隣接する段同士で接続しないトポロジー構造も含まれる。

他の構造データ５１１同士も接続することにより、情報処理装置１０１は、図１０で示すトポロジー構造Ｃを得る。トポロジー構造Ｃが得られた後、構築されたトポロジー構造Ｃにおいて経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うために、情報処理装置１０１は、転送パターン表と、出力ポート表とを作成する。この２つの表の作成方法は、実施例１と同様の処理であるから、説明を省略する。

また、実施例２において、入力サーバｓ（ｊ１，ｊ２，…，ｊｎ）が出力サーバｔ（ｋ１，ｋ２，…，ｋｎ）に送信する際に、各トポロジー構造で、「ｊ１，ｊ２，…，ｊｎ」が１成分ずつ修正される。従って、全ての入力サーバｓが、全ての出力サーバｔに送信することが可能である。

次に、実施例１、２におけるトポロジー構造Ｃの接続情報作成処理と、転送パターン表および出力ポート表とのそれぞれのフローチャートを、図１１、図１２を用いて説明する。

図１１は、トポロジー構造の接続情報作成処理手順の一例を示す説明図である。情報処理装置１０１は、情報処理装置１０１のユーザによる操作によって、新たなトポロジー構造の構造データの作成要求を受け付ける（ステップＳ１１０１）。作成要求には、新たなトポロジー構造が、何段のトポロジー構造で構築されるのかという指示と、各段におけるトポロジー構造を指定する情報とが含まれる。ここでは、２以上の自然数であるｎ段のトポロジー構造で構築され、各段のトポロジー構造が、トポロジー構造Ａ１、Ａ２、…、Ａｎであるとする。

そして、情報処理装置１０１は、作成要求に従って、記憶部５１０から、構造データＡ１（ａ１台）、Ａ２（ａ２台）、…、Ａｎ（ａｎ台）を取得する（ステップＳ１１０２）。次に、情報処理装置１０１は、ａ１・ａ２・…・ａｎを算出して得られた値をＰに代入する（ステップＳ１１０３）。そして、情報処理装置１０１は、構造データＡｉ（ｉ＝１，２，…ｎ）を、Ｐ／ａｉ分複製する（ステップＳ１１０４）。次に、情報処理装置１０１は、複製した構造データのＩＤを設定する（ステップＳ１１０５）。

そして、情報処理装置１０１は、複製した構造データの入力ポートｉｎＡｉと出力ポートｏｕｔＡｉとのＩＤを生成する（ステップＳ１１０６）。次に、情報処理装置１０１は、生成したＩＤを、複製した構造データの入力ポートｉｎＡｉと出力ポートｏｕｔＡｉに設定する（ステップＳ１１０７）。そして、情報処理装置１０１は、設定した入力ポートｉｎＡｉと出力ポートｏｕｔＡｉのＩＤに基づいて、同一の括弧内符号を有するｏｕｔＡｉ（ｉ＝１，２，…，ｎ）と、ｉｎＡ（ｉ＋１）とを接続する（ステップＳ１１０８）。

次に、情報処理装置１０１は、Ｐ台分の入力サーバｓと出力サーバｔとのＩＤを設定する（ステップＳ１１０９）。そして、情報処理装置１０１は、ＩｎＡ１と入力サーバｓとを接続する（ステップＳ１１１０）。また、情報処理装置１０１は、ＯｕｔＡｎと出力サーバとを接続する（ステップＳ１１１１）。そして、情報処理装置１０１は、複製したトポロジー構造Ａ１、Ａ２、…、Ａｎと、入力サーバｓと、出力サーバｔと、各トポロジー構造およびサーバの接続関係を含む接続情報１１０Ｃを作成する（ステップＳ１１１２）。ステップＳ１１１２の処理終了後、情報処理装置１０１は、トポロジー構造の接続情報作成処理を終了する。

図１２は、転送パターン表および出力ポート表作成処理手順の一例を示す説明図である。情報処理装置１０１は、記憶部５１０から、トポロジー構造Ａ１、Ａ２、…、Ａｎの転送パターン表１１１を取得する（ステップＳ１２０１）。ここで、トポロジー構造Ａ１の転送パターン表１１１は、Ｐ１個の転送パターンを含み、トポロジー構造Ａ２の転送パターン表１１１は、Ｐ２個の転送パターンを含み、…、トポロジー構造Ａｎの転送パターン表１１１には、Ｐｎ個の転送パターンがあるとする。

次に、情報処理装置１０１は、取得した転送パターン表から、Ｐ１，Ｐ２，…，Ｐｎ個の転送パターンを作成する（ステップＳ１２０２）。そして、情報処理装置１０１は、作成した転送パターンのうちのいずれか一つの転送パターンを選択する（ステップＳ１２０３）。次に、情報処理装置１０１は、選択した転送パターンに従って、各入力サーバｓの宛先となる出力サーバｔまでの経路を特定する（ステップＳ１２０４）。そして、情報処理装置１０１は、新たなトポロジー構造の転送パターン表に、特定した経路における出力サーバｔを、選択した転送パターンと入力サーバｓとの組み合わせに対応付けて登録する（ステップＳ１２０５）。

また、情報処理装置１０１は、特定した経路上にあるトポロジー構造Ａ１、Ａ２、…、Ａｎの出力ポートを特定する（ステップＳ１２０６）。そして、情報処理装置１０１は、新たなトポロジー構造内のトポロジー構造Ａ１、Ａ２、…、Ａｎの出力ポート表に、特定した出力ポートを、入力サーバと出力サーバとの組み合わせに対応付けて登録する（ステップＳ１２０７）。

次に、情報処理装置１０１は、作成した転送パターンの全てを選択したか否かを判断する（ステップＳ１２０８）。作成した転送パターンのうち選択していない転送パターンがある場合（ステップＳ１２０８：Ｎｏ）、情報処理装置１０１は、ステップＳ１２０３の処理に移行する。一方、作成した転送パターンの全てを選択した場合（ステップＳ１２０８：Ｙｅｓ）、情報処理装置１０１は、新たなトポロジー構造の転送パターン表を、入力サーバｓに送信する（ステップＳ１２０９）。また、情報処理装置１０１は、新たなトポロジー構造内のトポロジー構造Ａ１、Ａ２、…、Ａｎの出力ポート表を、対応するトポロジー構造Ａ１、Ａ２、…、Ａｎに送信する（ステップＳ１２１０）。ステップＳ１２１０の処理終了後、情報処理装置１０１は、転送パターン表および出力ポート表作成処理を終了する。

（実施例３）
実施例１、２では、片方向における経路競合のないＡｌｌ−ｔｏ−Ａｌｌ通信を提供できるトポロジー構造について説明したが、実施例３では、双方向における経路競合のないＡｌｌ−ｔｏ−Ａｌｌ通信を提供できるトポロジー構造について説明する。ここで、双方向における経路競合のＡｌｌ−ｔｏ−Ａｌｌ通信は、片方向の経路競合のないＡｌｌ−ｔｏ−Ａｌｌ通信が行えることに加えて、入力サーバ群から入力サーバ群への通信および出力サーバ群から出力サーバ群への経路競合のない通信が行えることである。

図１３は、実施例３における接続情報１１０Ｃの作成例を示す説明図である。あるトポロジー構造において、あるトポロジー構造の中段のＳｐｉｎｅスイッチを境に線対称となる場合、あるトポロジー構造を、「線対称トポロジー構造」と称する。例えば、Ｆａｔ−Ｔｒｅｅやラテン方陣Ｆａｔ−Ｔｒｅｅは、線対称トポロジー構造となる。線対称トポロジー構造で、片方向において経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が可能であるならば、Ｓｐｉｎｅスイッチで折り返すようにすることにより、双方向において経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うトポロジー構造を作成することができる。

図１３では、双方向において経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うトポロジー構造Ｃの一例を示す。トポロジー構造Ｃは、トポロジー構造Ａ群、Ｂ群、Ａ’群を有する。ここで、トポロジー構造Ａ’は、Ａを逆さにしたトポロジー構造である。また、トポロジー構造Ｂは、線対称トポロジー構造である。例えば、トポロジー構造Ｂは、図１３で示したように、ラテン方陣Ｆａｔ−Ｔｒｅｅである。ラテン方陣Ｆａｔ−Ｔｒｅｅは、図１３で示すように、Ｓｐｉｎｅスイッチ同士を繋げた点線１３０１を軸として線対称となる。

新たなトポロジー構造Ｃの接続情報Ｃが得られた後、構築されたトポロジー構造Ｃにおいて経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うために、情報処理装置１０１は、転送パターン表と、出力ポート表とを作成する。この２つの表の作成方法は、実施例１とほぼ同様の処理であるから、説明を省略する。異なる処理として、ステップＳ１２０４の処理で、情報処理装置１０１は、各入力サーバｓの宛先となる出力サーバｔまでの経路１３０２を特定するとともに、図１３で示した点線で複数の送信元のそれぞれからの通信が折り返される場合の経路１３０３を特定する。ここで、通信が折り返される箇所は、点線１３０１上のＳｐｉｎｅスイッチとなる。また、ステップＳ１２０５、Ｓ１２０７では、転送パターン表１１１、出力ポート表１１２に登録することになるが、情報処理装置１０１は、通信を折り返さない場合と、通信を折り返す場合とのそれぞれの転送パターン表、出力ポート表を用意すればよい。

以上説明したように、情報処理装置１０１は、トポロジー構造Ｃ内の各トポロジー構造の転送パターンの組み合わせごとに特定した複数の送信元のそれぞれから宛先までの経路から、トポロジー構造Ｃの転送パターンと各トポロジー構造の出力ポートを決定する。これにより、複数の送信元のそれぞれは、トポロジー構造Ｃにおいて、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うことができる。

また、情報処理装置１０１は、第２の数分複製した各構造データ５１１Ａの各出力ポートのそれぞれが、第１の数分複製した各構造データ５１１Ｂの第２の数の入力ポートのいずれか一つと接続された接続関係を示す接続情報１１０Ｃを作成してもよい。また、情報処理装置１０１は、複製した各構造データ５１１Ａの出力ポートと複製した各構造データ５１１Ｂの入力ポートとにＩＤを設定し、同一のＩＤ同士が接続された接続関係を示す接続情報１１０Ｃを作成してもよい。これにより、情報処理装置１０１は、サーバに対するスイッチの数を増やさずに経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行える２段のトポロジー構造Ｃの接続方法となる接続情報１１０Ｃを、トポロジー構造Ｃの管理者に示すことができる。そして、トポロジー構造Ｃの管理者は、示された接続情報１１０に従うことにより、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うことができるトポロジー構造Ｃを構築することができる。

ここで、サーバに対するスイッチの数を増やしていない証明として、図７で示すように、トポロジー構造Ｃには、トポロジー構造Ａ、Ｂに元々含まれるスイッチ以外のスイッチを新たに必要としていない。また、情報処理装置１０１は、異なるトポロジー構造をベースとして、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うことができるトポロジー構造を拡張することができる。

また、情報処理装置１０１は、複製した構造データＡｉ（ｉ＝１，２，…，ｎ）の各出力ポートと各入力ポートとにＩＤを設定し、隣の段同士において同一のＩＤ同士が接続された接続関係を示す接続情報１１０を作成してもよい。これにより、情報処理装置１０１は、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行えるｎ段のトポロジー構造Ｃの接続方法を、トポロジー構造Ｃの管理者に示すことができる。

また、情報処理装置１０１は、ｎを３以上の奇数とし、第ｉの種別のトポロジー構造が、第（ｎ−ｉ＋１）種別のトポロジー構造を逆さにしたトポロジー構造であり、第（（ｎ＋１）／２）種別のトポロジー構造が、線対称となる接続情報１１０を作成してもよい。これにより、情報処理装置１０１は、双方向の経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信が行えるトポロジー構造の接続方法を、トポロジー構造Ｃの管理者に示すことができる。

また、情報処理装置１０１は、トポロジー構造Ｃ内の各トポロジー構造の転送パターンの組み合わせごとに特定した複数の送信元のそれぞれから宛先までの経路と、第（（ｎ＋１）／２）種別のトポロジー構造内のＳｐｉｎｅスイッチで折り返した経路とを特定する。これにより、複数の送信元のそれぞれは、トポロジー構造Ｃにおいて、経路競合なく双方向のＡｌｌ−ｔｏ−Ａｌｌ通信を行うことができる。

また、情報処理装置１０１は、転送パターン表１１１を入力サーバｓに送信するとともに、出力ポート表１１２をトポロジー構造Ｃの各トポロジー構造のスイッチに送信してもよい。これにより、転送パターン表１１１や出力ポート表１１２を手動で設定しなくとも、複数の送信元のそれぞれは、トポロジー構造Ｃにおいて、経路競合なくＡｌｌ−ｔｏ−Ａｌｌ通信を行うことができる。また、トポロジー構造Ｃの管理者は、転送パターン表１１１や出力ポート表１１２を閲覧して、複数の送信先のそれぞれと、トポロジー構造Ｃの各トポロジー構造のスイッチとの設定を手動で割り当ててもよい。

なお、本実施の形態で説明した通信手順決定方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本通信プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｃ−Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本通信プログラムは、インターネット等のネットワークを介して配布してもよい。

上述した実施の形態に関し、さらに以下の付記を開示する。

（付記１）出力ポートおよび複数の送信元のそれぞれが接続された入力ポートを第１の数分有する第２の数分の第１の種別の各トポロジー構造と入力ポートおよび複数の宛先のそれぞれが接続された出力ポートを前記第２の数分有する前記第１の数分の第２の種別の各トポロジー構造とがそれぞれ接続されたネットワーク内の各トポロジー構造の接続関係を示す接続情報と、前記第１の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせを示す前記第１の数分の転送パターンと、前記第２の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせが示される前記第２の数分の転送パターンとを記憶する記憶部と、
前記第１の数分の転送パターンのそれぞれと前記第２の数分の転送パターンのそれぞれとの組み合わせに対応して、前記接続情報が示す前記ネットワークにおいて当該組み合わせの転送パターンが指定される際に前記複数の送信元のそれぞれから宛先までの経路を特定し、当該組み合わせに対応して特定した前記経路に基づいて、前記ネットワークにおいて前記複数の送信元のそれぞれから前記複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンと、前記ネットワーク内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する制御部と、
を有することを特徴とする情報処理装置。

（付記２）前記記憶部は、
前記第１の種別のトポロジー構造を示す第１の構造データと、前記第２の種別のトポロジー構造を示す第２の構造データとを記憶し、
前記制御部は、
前記第１の種別のトポロジー構造と前記第２の種別のトポロジー構造とを有するネットワーク内の各トポロジー構造の接続関係を示す接続情報の作成要求を受け付けた際に、前記第１の構造データを前記第２の数分複製し、前記第２の構造データを前記第１の数分複製し、
複製した前記第２の数分の第１の構造データの各第１の構造データの前記第１の数の出力ポートのそれぞれと、複製した前記第１の数分の第２の構造データの各第２の構造データの前記第２の数の入力ポートのいずれか一つとが接続された接続関係を示す前記接続情報を作成する、
ことを特徴とする付記１に記載の情報処理装置。

（付記３）前記制御部は、
複製した前記第２の数分の第１の構造データの各第１の構造データの前記第１の数の出力ポートの各出力ポートの識別情報を、前記各第１の構造データ内で前記各出力ポートを識別する値と前記第２の数に基づいた値との順に結合した情報に設定し、
複製した前記第１の数分の第２の構造データの各第２の構造データの前記第２の数の入力ポートの各入力ポートの識別情報を、前記第１の数に基づいた値と前記各第２の構造データ内で前記各入力ポートを識別する値との順に結合した情報に設定し、
複製した前記第２の数分の第１の構造データの各第１の構造データの前記第１の数の出力ポートの各出力ポートと、複製した前記第１の数分の第２の構造データの前記第２の数の入力ポートのうち当該各出力ポートと同一の識別情報を有する入力ポートとが接続された接続関係を示す前記接続情報を作成する、
ことを特徴とする付記２に記載の情報処理装置。

（付記４）前記記憶部は、
ｎを２以上のいずれかの自然数とし、前記第１の種別のトポロジー構造を示す第１の構造データから第ｎの種別のトポロジー構造を示す第ｎの構造データまでを記憶し、
前記制御部は、
ｉを１からｎまでのいずれかの自然数とし、入力ポートおよび出力ポートを前記第１の数分有する前記第１の種別のトポロジー構造から入力ポートおよび出力ポートを第ｎの数分有する第ｎの種別のトポロジー構造までのｎ種類のトポロジー構造を有するネットワーク内の各トポロジー構造の接続関係を示す接続情報の作成要求を受け付けた際に、第ｉの種別のトポロジー構造を示す第ｉの構造データを、前記第１の数から前記第ｎの数までを乗じた値から第ｉの数で除した数分複製し、
複製した前記第ｉの構造データの各入力ポートと各出力ポートとに対応して、前記第１の数から前記第ｎの数までの数群のうち前記第ｉの数を除く数に基づいた（ｎ−１）桁の数列のｉ番目に、前記第ｉの構造データ内で前記各入力ポートまたは前記各出力ポートを識別する値を挿入した数列を生成し、
複製した前記第ｉの構造データの各入力ポートと各出力ポートとの識別情報を、生成した前記数列に設定し、
ｊを１から（ｎ−１）までのいずれかの自然数とし、複製した第ｊの構造データの各第ｊの構造データの第ｊの数の出力ポートの各出力ポートと、複製した第（ｊ＋１）の構造データの第（ｊ＋１）の数の入力ポートのうち当該各出力ポートと同一の識別情報を有する入力ポートとが接続された接続関係を示す前記接続情報を作成する、
ことを特徴とする付記３に記載の情報処理装置。

（付記５）前記ｎを３以上のいずれかの奇数とし、ｉを１から（（ｎ−１）／２）までのいずれかの自然数とし、前記ネットワークに含まれる第ｉの種別のトポロジー構造が、第（ｎ−ｉ＋１）種別のトポロジー構造を逆さにしたトポロジー構造であり、第（（ｎ＋１）／２）種別のトポロジー構造が、スイッチ同士を接続する複数のスイッチを有し、かつ、前記複数のスイッチのそれぞれを結ぶ線を軸として線対称となる構造であることを特徴とする付記４に記載の情報処理装置。

（付記６）前記記憶部は、
前記ネットワーク内の各トポロジー構造の接続関係を示す接続情報と、前記第１の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせを示す前記第１の数分の転送パターンから前記第ｎの種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせが示される前記第ｎの数分の転送パターンまでを記憶し、
前記制御部は、
前記第１の数分の転送パターンのそれぞれから前記第ｎの数分の転送パターンのそれぞれまでの組み合わせに対応して、前記接続情報が示す前記ネットワークにおいて当該組み合わせの転送パターンが指定される際に、前記複数の送信元のそれぞれから宛先までの経路を特定し、さらに、前記第（（ｎ＋１）／２）種別のトポロジー構造に含まれる前記複数のスイッチで前記複数の送信元のそれぞれからの通信が折り返される場合における前記複数の送信元のそれぞれから宛先までの経路を特定する、
ことを特徴とする付記５に記載の情報処理装置。

（付記７）前記制御部は、
前記ネットワークにおいて前記複数の送信元のそれぞれから前記複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンを、前記複数の送信元のそれぞれに送信し、
前記ネットワーク内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートを示す情報を、前記各トポロジー構造に含まれるスイッチ群に送信する、
ことを特徴とする付記１〜６のいずれか一つに記載の情報処理装置。

（付記８）コンピュータが、
出力ポートおよび複数の送信元のそれぞれが接続された入力ポートを第１の数分有する第２の数分の第１の種別の各トポロジー構造と入力ポートおよび複数の宛先のそれぞれが接続された出力ポートを前記第２の数分有する前記第１の数分の第２の種別の各トポロジー構造とがそれぞれ接続されたネットワーク内の各トポロジー構造の接続関係を示す接続情報と、前記第１の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせを示す前記第１の数分の転送パターンと、前記第２の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせが示される前記第２の数分の転送パターンとを記憶する記憶部を参照して、前記第１の数分の転送パターンのそれぞれと前記第２の数分の転送パターンのそれぞれとの組み合わせに対応して、前記接続情報が示す前記ネットワークにおいて当該組み合わせの転送パターンが指定される際に前記複数の送信元のそれぞれから宛先までの経路を特定し、
当該組み合わせに対応して特定した前記経路に基づいて、前記ネットワークにおいて前記複数の送信元のそれぞれから前記複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンと、前記ネットワーク内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する、
処理を実行することを特徴とする通信手順決定方法。

（付記９）コンピュータに、
出力ポートおよび複数の送信元のそれぞれが接続された入力ポートを第１の数分有する第２の数分の第１の種別の各トポロジー構造と入力ポートおよび複数の宛先のそれぞれが接続された出力ポートを前記第２の数分有する前記第１の数分の第２の種別の各トポロジー構造とがそれぞれ接続されたネットワーク内の各トポロジー構造の接続関係を示す接続情報と、前記第１の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせを示す前記第１の数分の転送パターンと、前記第２の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせが示される前記第２の数分の転送パターンとを記憶する記憶部を参照して、前記第１の数分の転送パターンのそれぞれと前記第２の数分の転送パターンのそれぞれとの組み合わせに対応して、前記接続情報が示す前記ネットワークにおいて当該組み合わせの転送パターンが指定される際に前記複数の送信元のそれぞれから宛先までの経路を特定し、
当該組み合わせに対応して特定した前記経路に基づいて、前記ネットワークにおいて前記複数の送信元のそれぞれから前記複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンと、前記ネットワーク内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する、
処理を実行させることを特徴とする通信プログラム。

Ａ、Ｂ、Ｃ トポロジー構造
１０１ 情報処理装置
１０２ ネットワーク
１１０ 接続情報
１１１ 転送パターン表
１１２ 出力ポート表
５００ 制御部
５０１ 複製部
５０２ 設定部
５０３ 作成部
５０４ 特定部
５０５ 決定部
５０６ 送信部
５１０ 記憶部
５１１ 構造データ

Claims (8)

1. 出力ポートおよび複数の送信元のそれぞれが接続された入力ポートを第１の数分有する第２の数分の第１の種別の各トポロジー構造と入力ポートおよび複数の宛先のそれぞれが接続された出力ポートを前記第２の数分有する前記第１の数分の第２の種別の各トポロジー構造とがそれぞれ接続されたネットワーク内の各トポロジー構造の接続関係を示す接続情報と、前記第１の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせを示す前記第１の数分の転送パターンと、前記第２の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせが示される前記第２の数分の転送パターンとを記憶する記憶部と、
   前記第１の数分の転送パターンのそれぞれと前記第２の数分の転送パターンのそれぞれとの組み合わせに対応して、前記接続情報が示す前記ネットワークにおいて当該組み合わせの転送パターンが指定される際に前記複数の送信元のそれぞれから宛先までの経路を特定し、当該組み合わせに対応して特定した前記経路に基づいて、前記ネットワークにおいて前記複数の送信元のそれぞれから前記複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンと、前記ネットワーク内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する制御部と、
   を有することを特徴とする情報処理装置。
2. 前記記憶部は、
   前記第１の種別のトポロジー構造を示す第１の構造データと、前記第２の種別のトポロジー構造を示す第２の構造データとを記憶し、
   前記制御部は、
   前記第１の種別のトポロジー構造と前記第２の種別のトポロジー構造とを有するネットワーク内の各トポロジー構造の接続関係を示す接続情報の作成要求を受け付けた際に、前記第１の構造データを前記第２の数分複製し、前記第２の構造データを前記第１の数分複製し、
   複製した前記第２の数分の第１の構造データの各第１の構造データの前記第１の数の出力ポートのそれぞれと、複製した前記第１の数分の第２の構造データの各第２の構造データの前記第２の数の入力ポートのいずれか一つとが接続された接続関係を示す前記接続情報を作成する、
   ことを特徴とする請求項１に記載の情報処理装置。
3. 前記制御部は、
   複製した前記第２の数分の第１の構造データの各第１の構造データの前記第１の数の出力ポートの各出力ポートの識別情報を、前記各第１の構造データ内で前記各出力ポートを識別する値と前記第２の数に基づいた値との順に結合した情報に設定し、
   複製した前記第１の数分の第２の構造データの各第２の構造データの前記第２の数の入力ポートの各入力ポートの識別情報を、前記第１の数に基づいた値と前記各第２の構造データ内で前記各入力ポートを識別する値との順に結合した情報に設定し、
   複製した前記第２の数分の第１の構造データの各第１の構造データの前記第１の数の出力ポートの各出力ポートと、複製した前記第１の数分の第２の構造データの前記第２の数の入力ポートのうち当該各出力ポートと同一の識別情報を有する入力ポートとが接続された接続関係を示す前記接続情報を作成する、
   ことを特徴とする請求項２に記載の情報処理装置。
4. 前記記憶部は、
   ｎを２以上のいずれかの自然数とし、前記第１の種別のトポロジー構造を示す第１の構造データから第ｎの種別のトポロジー構造を示す第ｎの構造データまでを記憶し、
   前記制御部は、
   ｉを１からｎまでのいずれかの自然数とし、入力ポートおよび出力ポートを前記第１の数分有する前記第１の種別のトポロジー構造から入力ポートおよび出力ポートを第ｎの数分有する第ｎの種別のトポロジー構造までのｎ種類のトポロジー構造を有するネットワーク内の各トポロジー構造の接続関係を示す接続情報の作成要求を受け付けた際に、第ｉの種別のトポロジー構造を示す第ｉの構造データを、前記第１の数から前記第ｎの数までを乗じた値から第ｉの数で除した数分複製し、
   複製した前記第ｉの構造データの各入力ポートと各出力ポートとに対応して、前記第１の数から前記第ｎの数までの数群のうち前記第ｉの数を除く数に基づいた（ｎ−１）桁の数列のｉ番目に、前記第ｉの構造データ内で前記各入力ポートまたは前記各出力ポートを識別する値を挿入した数列を生成し、
   複製した前記第ｉの構造データの各入力ポートと各出力ポートとの識別情報を、生成した前記数列に設定し、
   ｊを１から（ｎ−１）までのいずれかの自然数とし、複製した第ｊの構造データの各第ｊの構造データの第ｊの数の出力ポートの各出力ポートと、複製した第（ｊ＋１）の構造データの第（ｊ＋１）の数の入力ポートのうち当該各出力ポートと同一の識別情報を有する入力ポートとが接続された接続関係を示す前記接続情報を作成する、
   ことを特徴とする請求項３に記載の情報処理装置。
5. 前記ｎを３以上のいずれかの奇数とし、ｉを１から（（ｎ−１）／２）までのいずれかの自然数とし、前記ネットワークに含まれる第ｉの種別のトポロジー構造が、第（ｎ−ｉ＋１）種別のトポロジー構造を逆さにしたトポロジー構造であり、第（（ｎ＋１）／２）種別のトポロジー構造が、スイッチ同士を接続する複数のスイッチを有し、かつ、前記複数のスイッチのそれぞれを結ぶ線を軸として線対称となる構造であることを特徴とする請求項４に記載の情報処理装置。
6. 前記記憶部は、
   前記ネットワーク内の各トポロジー構造の接続関係を示す接続情報と、前記第１の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせを示す前記第１の数分の転送パターンから前記第ｎの種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせが示される前記第ｎの数分の転送パターンまでを記憶し、
   前記制御部は、
   前記第１の数分の転送パターンのそれぞれから前記第ｎの数分の転送パターンのそれぞれまでの組み合わせに対応して、前記接続情報が示す前記ネットワークにおいて当該組み合わせの転送パターンが指定される際に、前記複数の送信元のそれぞれから宛先までの経路を特定し、さらに、前記第（（ｎ＋１）／２）種別のトポロジー構造に含まれる前記複数のスイッチで前記複数の送信元のそれぞれからの通信が折り返される場合における前記複数の送信元のそれぞれから宛先までの経路を特定する、
   ことを特徴とする請求項５に記載の情報処理装置。
7. コンピュータが、
   出力ポートおよび複数の送信元のそれぞれが接続された入力ポートを第１の数分有する第２の数分の第１の種別の各トポロジー構造と入力ポートおよび複数の宛先のそれぞれが接続された出力ポートを前記第２の数分有する前記第１の数分の第２の種別の各トポロジー構造とがそれぞれ接続されたネットワーク内の各トポロジー構造の接続関係を示す接続情報と、前記第１の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせを示す前記第１の数分の転送パターンと、前記第２の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせが示される前記第２の数分の転送パターンとを記憶する記憶部を参照して、前記第１の数分の転送パターンのそれぞれと前記第２の数分の転送パターンのそれぞれとの組み合わせに対応して、前記接続情報が示す前記ネットワークにおいて当該組み合わせの転送パターンが指定される際に前記複数の送信元のそれぞれから宛先までの経路を特定し、
   当該組み合わせに対応して特定した前記経路に基づいて、前記ネットワークにおいて前記複数の送信元のそれぞれから前記複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンと、前記ネットワーク内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する、
   処理を実行することを特徴とする通信手順決定方法。
8. コンピュータに、
   出力ポートおよび複数の送信元のそれぞれが接続された入力ポートを第１の数分有する第２の数分の第１の種別の各トポロジー構造と入力ポートおよび複数の宛先のそれぞれが接続された出力ポートを前記第２の数分有する前記第１の数分の第２の種別の各トポロジー構造とがそれぞれ接続されたネットワーク内の各トポロジー構造の接続関係を示す接続情報と、前記第１の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせを示す前記第１の数分の転送パターンと、前記第２の種別のトポロジー構造において経路競合なく全対全通信を行う入力ポートと出力ポートとの組み合わせが示される前記第２の数分の転送パターンとを記憶する記憶部を参照して、前記第１の数分の転送パターンのそれぞれと前記第２の数分の転送パターンのそれぞれとの組み合わせに対応して、前記接続情報が示す前記ネットワークにおいて当該組み合わせの転送パターンが指定される際に前記複数の送信元のそれぞれから宛先までの経路を特定し、
   当該組み合わせに対応して特定した前記経路に基づいて、前記ネットワークにおいて前記複数の送信元のそれぞれから前記複数の宛先のそれぞれまで経路競合なく全対全通信を行う転送パターンと、前記ネットワーク内の各トポロジー構造における送信元と宛先との組み合わせに対応する出力ポートとを決定する、
   処理を実行させることを特徴とする通信プログラム。

Images