(57)【特許請求の範囲】
【請求項１】
ｎ３個（ｎは２以上の自然数）のアドレスが連番でそれぞれに与えられているｎ３個の信号送受信装置に対して、最小のアドレスから連番でｎ個のアドレスをそれぞれが有するように分けられた信号送受信装置のｎ２個の組合せのいずれかと１対１に対応するように接続されており、宛先のアドレスをｎで割った余りがそれぞれ異なるｎ個の信号を前記信号送受信装置から受信し、受信した信号の送信先のアドレスが自己に接続された前記信号送受信装置の場合は、該信号送受信装置へ信号を送信し、それ以外の場合は、受信した信号を異なるｎ個の送信先に送信する、ｎ２個の第１信号転送部と、
宛先のアドレスをｎで割った余りが同じであるｎ個の信号をｎ個の異なる第１信号転送部から受信し、受信した信号の送信先のアドレスが自己に接続された前記第１信号転送部の場合は、該第１信号転送部へ信号を送信し、それ以外の場合は、受信した信号の宛先アドレスをｎ２で割った余りに対応する送信先に送信するｎ２個の第２信号転送部と、
前記第２信号転送部との間でファットツリーの構成を有し、宛先のアドレスをｎ２で割った余りが同じであるｎ個の信号をｎ個の異なる前記第２信号転送部から受信し、前記第２信号転送部から受信した信号を宛先のアドレスを有する前記信号送受信装置に接続されている前記第１信号転送部に接続されている前記第２信号転送部へ出力するｎ２個の第３信号転送部と、
前記第３信号転送部とファットツリーを構成する前記第２信号転送部において、前記第１信号転送部との間で、ファットツリーの構成から少なくとも１つの前記第２信号転送部の接続先と他の第２信号転送部の接続先とを交換して接続する下段接続経路とを備え、
前記第２信号転送部と前記第３信号転送部とはｎ対ｎの組にグループｉ（ｉ＝１、２、・・・、ｎ）に分けられ、それぞれの前記グループｉに含まれる各前記第２信号転送部は、そのグループｉに含まれる全ての前記第３信号転送部と接続し、
前記グループｉにおける前記第２信号転送部は、送信先のアドレスをｎ２で割った余りがｉ、ｉ＋ｎ、ｉ＋２ｎ、・・・、ｉ＋（ｎ−１）ｎである信号を、ｎ２で割った余りに対応する前記第３信号転送部へ送信し、ｎ２で割った余りが同じ値になるアドレスを有する前記信号送受信装置から信号を受ける前記第１信号転送部のうちのいずれか異なる前記第１信号転送部から送信先のアドレスをｎで割った余りがｉ、ｉ＋ｎ、ｉ＋２ｎ、・・・、又はｉ＋（ｎ−１）ｎのいずれかになる信号を受信し、且つ少なくとも一つのグループにおける前記第２信号転送部が受信した信号の送信元の前記第１信号転送部に接続されている前記信号送受信装置のアドレスが不連続となる前記第１信号転送部から信号を受信し、さらに、前記第３信号転送部から受信した信号の宛先のアドレスを有する前記信号送受信装置に接続されている第１信号転送部へ送信し、
前記第１信号転送部は、前記第２信号転送部から受信した信号を宛先のアドレスを有する信号送受信装置へ送信する
ことを特徴とするネットワーク装置。
【請求項２】
前記第１信号転送部の一部と前記信号送受信装置の一部とを削除したことを特徴とする請求項１に記載のネットワーク装置。
【請求項３】
前記第１信号転送部を、受信する前記信号送受信装置のアドレスが１〜ｎ２、１＋ｎ２〜２ｎ２、・・・、及び１＋（ｎ−１）ｎ２〜ｎ３となる１段目グループに分け、さらにアドレスが小さい順に１〜ｎまでの番号を振り、前記第２信号転送部のグループ毎に、グループに含まれる各前記第２信号転送部に接続された前記第１信号転送部を含む１段目グループの番号を行に並べて作成したｎ個のｎ×ｎ行列が相互に直交するラテン方格となることを特徴とする請求項１に記載のネットワーク装置。
【請求項４】
前記信号送受信装置は、１〜ｎ３のアドレスが連番でそれぞれに与えられており、
前記第１信号転送部は、前記アドレスの１〜ｎ、ｎ＋１〜２ｎ、２ｎ＋１〜３ｎ、・・・、又は（ｎ２−１）ｎ＋１〜ｎ３の組合せを有する前記信号送受信装置の組合せのいずれかと１対１に対応するように接続されている
ことを特徴とする請求項１〜３のいずれか一つに記載のネットワーク装置。
【請求項５】
ｎ３個のアドレスが連番でそれぞれに与えられているｎ３個の信号送受信装置に対して、最小の前記アドレスから連番でｎ個のアドレスをそれぞれが有するように分けられた信号送受信装置のｎ２個の組合せのいずれかと１対１に対応するように接続されており、宛先のアドレスをｎで割った余りがそれぞれ異なるｎ個の信号を前記信号送受信装置から受信し、受信した信号の送信先のアドレスが自己に接続された前記信号送受信装置の場合は、該信号送受信装置へ信号を送信し、それ以外の場合は、受信した信号を異なるｎ個の送信先に送信する、ｎ２個の第１スイッチと、宛先のアドレスをｎで割った余りが同じであるｎ個の信号をｎ個の異なる前記第１スイッチから受信し、受信した信号の送信先のアドレスが自己に接続された前記第１スイッチの場合は、該第１スイッチへ信号を送信し、それ以外の場合は、受信した信号をｎ２で割った余りに対応する送信先に送信するｎ２個の第２スイッチと、宛先のアドレスをｎ２で割った余りが同じであるｎ個の信号をｎ個の異なる前記第２スイッチから受信し、前記第２スイッチから受信した信号を宛先のアドレスを有する前記信号送受信装置に接続されている前記第１スイッチに接続されている前記第２スイッチへ出力するｎ２個の第３スイッチとを配置図に配置するスイッチ配置部と、
前記第２スイッチと前記第３スイッチとはｎ対ｎの組にグループｉ（ｉ＝１、２、・・・、ｎ）に分けられ、それぞれの前記グループｉにおける各前記第２スイッチは、自己が属するグループｉに含まれる全ての前記第３スイッチと接続し、前記グループｉにおける前記第２スイッチが、送信先のアドレスをｎ２で割った余りがｉ、ｉ＋ｎ、ｉ＋２ｎ、・・・、ｉ＋（ｎ−１）ｎである信号を、ｎ２で割った余りに対応する前記第３スイッチへ送信する配線を求める第１配線部と、
前記グループｉにおける各前記第２スイッチは、ｎ２で割った余りが同じ値になるアドレスを有する前記信号送受信装置から信号を受ける前記第１スイッチのうちのいずれか異なる前記第１スイッチから送信先のアドレスをｎで割った余りがｉ、ｉ＋ｎ、ｉ＋２ｎ、・・・、又はｉ＋（ｎ−１）ｎのいずれかになる信号を受信し、且つ少なくとも一つのグループにおける前記第２スイッチが受信した信号の送信元の前記第１スイッチに接続されている前記信号送受信装置のアドレスが不連続となる前記第１スイッチから信号を受信し、さらに、前記第３スイッチから受信した信号の宛先のアドレスを有する前記信号送受信装置に接続されている第１スイッチへ送信し、前記第１スイッチが、前記第２スイッチから受信した信号を宛先のアドレスを有する信号送受信装置へ送信する配線を求める第２配線部と
を備えたことを特徴とするネットワーク管理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク装置及びネットワーク管理装置に関する。
【背景技術】
【０００２】
近年、ＨＰＣ（High  Performance  Computer）の分野において、多数のノード、例えばサーバなどを高速なネットワークで接続するクラスタシステムが広く用いられている。このようなクラスタシステムでは、並列計算処理が行われることが多い。そして、そのような並列計算処理における通信では、信号伝送における広い帯域の確保と低い遅延が求められる。これを実現するため、特に大規模なクラスタシステムにおいては、ＩｎｆｉｎｉＢａｎｄによるＦａｔ  Ｔｒｅｅ（ファットツリー）接続が広く用いられている。
【０００３】
Ｆａｔ  Ｔｒｅｅは、例えば図１３に示す構成のような、多重化されたツリー型の網構成を有するトポロジーである。図１３は、３段のＦａｔ  Ｔｒｅｅを有するネットワーク装置の構成図である。Ｆａｔ  Ｔｒｅｅでは、最上段を除く各スイッチにおける接続リンク本数は、上側と下側で等しいため、上下いずれの方向に転送する場合にも十分に広い帯域を確保することができる。
【０００４】
ここで、図１３に示すスイッチＢ１〜Ｂ９を１段目のスイッチと言う。また、スイッチＭ１〜Ｍ９を２段目のスイッチと言う。また、スイッチＴ１〜Ｔ９を３段目のスイッチと言う。図１３に表すＦａｔ  Ｔｒｅｅでは、各１段目のスイッチは３つの２段目のスイッチに接続されている。さらに、スイッチＢ１〜Ｂ３は、それぞれ同じ２段目のスイッチに接続されている。また、スイッチＢ４〜Ｂ６は、それぞれ同じ２段目のスイッチに接続されている。さらに、スイッチＢ７〜Ｂ９は、それぞれ同じ２段目のスイッチに接続されている。例えば、スイッチＢ１〜Ｂ３は、それぞれスイッチＭ１、Ｍ４及びＭ７に接続されている。
【０００５】
さらに、スイッチＢ１〜Ｂ９は、それぞれ３つのノードに接続されている。図１３では、スイッチＢ１〜Ｂ９に接続している丸がノードを表している。さらに、各ノードの下に記載した数字は、各ノードのノード番号を表している。このノード番号は、ノード間で信号を送受信する場合のアドレスとなる。例えば、スイッチＢ１には、ノード番号１〜３を有するノードが接続されている。また、スイッチＢ２には、ノード番号４〜６を有するノードが接続されている。以下では、ノード番号Ｐを有するノードをノードＰと言う。
【０００６】
ノード１〜２７は、他のノードへ向けた信号を、自己が接続する１段目のスイッチに対して送信する。ここで、ノード１〜２７は、他のノードへ送信する信号の宛先としてノード番号を指定する。
【０００７】
スイッチＢ１〜Ｂ９は、それぞれ自己に接続されたノードから他のノードへ宛てた信号を受信する。そして、スイッチＢ１〜Ｂ９は、スイッチＭ１〜Ｍ３に対しては１ｍｏｄ３となるノード番号に向けた信号を送信する。また、スイッチＢ１〜Ｂ９は、スイッチＭ４〜Ｍ６に対しては２ｍｏｄ３となるノード番号に向けた信号を送信する。また、スイッチＢ１〜Ｂ９は、スイッチＭ７〜Ｍ９に対しては３（０）ｍｏｄ３となるノード番号に向けた信号を送信する。例えば、スイッチＢ１は、ノード１〜３から受信した信号のうち１ｍｏｄ３となる信号を、矢印９０１で表すようにスイッチＭ１へ送信する。また、スイッチＢ１は、ノード１〜３から受信した信号のうち２ｍｏｄ３となる信号を、矢印９０２で表すようにスイッチＭ４へ送信する。スイッチＢ１は、ノード１〜３から受信した信号のうち３（０）ｍｏｄ３となる信号を、矢印９０３で表すようにスイッチＭ７へ送信する。
【０００８】
スイッチＭ１〜Ｍ９は、それぞれ接続されている１段目のスイッチから信号の送信先のノード番号を３で割った余りが等しくなる信号を受信する。例えば、スイッチＭ１は、スイッチＢ１〜Ｂ３のそれぞれから送信先のノード番号が１ｍｏｄ３である信号を受信する。また、スイッチＭ２は、スイッチＢ４〜Ｂ６のそれぞれから送信先のノード番号が１ｍｏｄ３である信号を受信する。また、スイッチＭ３は、スイッチＢ７〜Ｂ９のそれぞれから送信先のノード番号が２ｍｏｄ３である信号を受信する。さらに、スイッチＭ４は、スイッチＢ１〜Ｂ３のそれぞれから送信先のノード番号が２ｍｏｄ３である信号を受信する。また、スイッチＭ７は、スイッチＢ１〜Ｂ３のそれぞれから送信先のノード番号が３（０）ｍｏｄ３となる信号を受信する。
【０００９】
さらに、スイッチＭ１〜Ｍ３とスイッチＴ１〜Ｔ３とが組みになっており、スイッチＭ４〜Ｍ６とスイッチＴ４〜Ｔ６とが組になっており、スイッチＭ７〜Ｍ９とスイッチＴ７〜Ｔ９と組になっている。そして、スイッチＭ１〜Ｍ３は、スイッチＴ１に対して、例えば矢印９０４のように、送信先のノード番号が１ｍｏｄ９である信号を送信する。また、スイッチＭ１〜Ｍ３は、スイッチＴ２に対して、例えば矢印９０５のように、送信先のノード番号が４ｍｏｄ９である信号を送信する。また、スイッチＭ１〜Ｍ３は、スイッチＴ３に対して、例えば矢印９０６のように、送信先のノード番号が７ｍｏｄ９である信号を送信する。また、スイッチＭ４〜Ｍ６は、スイッチＴ４に送信先のノード番号が２ｍｏｄ９である信号を送信し、スイッチＴ５に送信先のノード番号が５ｍｏｄ９である信号を送信し、スイッチＴ６に送信先のノード番号が８ｍｏｄ９である信号を送信する。また、スイッチＭ７〜Ｍ９は、スイッチＴ７に送信先のノード番号が３ｍｏｄ９である信号を送信し、スイッチＴ８に送信先のノード番号が６ｍｏｄ９である信号を送信し、スイッチＴ９に送信先のノード番号が０ｍｏｄ９（＝９ｍｏｄ９）である信号を送信する。
【００１０】
そして、スイッチＴ１〜Ｔ９は、スイッチＭ１〜Ｍ９から受信した信号の送信先のノード番号を有するノードが接続されている１段目のスイッチに接続している２段目のスイッチに向けて信号を送信する。さらに、スイッチＭ１〜Ｍ９は、スイッチＴ１〜Ｔ９から受信した信号の送信先のノード番号を有するノードに接続している１段目のスイッチに向けて信号を送信する。その後、スイッチＢ１〜Ｂ９は、スイッチＭ１〜Ｍ９から受信した信号の送信先のノード番号を有するノードに向けて信号を送信する。
【００１１】
このようにしてＦａｔ  Ｔｒｅｅでは、あるノードから他のノードに向けて信号が送信される。
【００１２】
さらに、Ｆａｔ  Ｔｒｅｅ接続において全てのノードから全てのノードに対してメッセージの送受信を行う全対全通信において、シフト通信パターンと呼ばれる通信方式が広く用いられている。シフト通信パターンは、ノード数をＮとすると、Ｎ回の通信フェーズから構成される。そして、ｉ番目の通信フェーズでは、自己のノード番号からｉ番先のノード番号に対してメッセージを送信する。したがって、各ノード番号をｐ（ｐ＝１，２，・・・，Ｎ）とすると、ｉ番目の通信フェーズでは、（（ｉ＋ｐ）ｍｏｄＮ）が各ノードのメッセージの送信先となる。すなわち、シフト通信パターンでは、各通信フェーズにおいて、各ノードにおいて送信した信号の送信先が重複しない。
【００１３】
図１４は、シフト通信パターンを説明するための図である。図１４は、図１３と同じ構成でシフト通信パターンを行なった場合の９番目の通信フェーズの状態を表している。枠９１０で囲われた数字は、各ノードにおける送信先のノード番号を表している。９番目の通信フェーズでの各ノードにおける送信先のノード番号は、各ノードのノード番号に９を加えた番号である。そして、シフト通信パターンでは、Ｂ１〜Ｂ９で表される１段目のスイッチが配下のノードから受信する信号のノード番号は連番である。したがって、１段目のスイッチは、送信先のノード番号が１ｍｏｄ３、２ｍｏｄ３及び３（０）ｍｏｄ３である３つの信号を受信する。このため、１段目のスイッチは受信した各信号をそれぞれ異なる２段目のスイッチに送信することになる。２段目のスイッチは、それぞれ９個の連番の送信先のノード番号の中の３で割った余りが等しい信号を受信することになる。そして、９個の連番の送信先のノード番号の中の３で割った余りが等しい番号は、９で割った余りが異なる番号である。例えば、スイッチＭ１は、送信先のノード番号が１ｍｏｄ９、４ｍｏｄ９及び７ｍｏｄ９である３つの信号を受信する。このため、スイッチＭ１は、受信した各信号をそれぞれ異なる３段目のスイッチに送信することになる。同様にして、スイッチＭ２〜Ｍ９においても、受信された各信号はそれぞれ異なる３段目のスイッチに送信されることになる。
【００１４】
このように、いずれの経路においても２以上の信号が流れることが無い。以下では、同じ経路に２つ以上の信号が流れることを経路競合と言う。さらに、ここでは、一例として９番目のフェーズについて説明したが、他のフェーズにおいても各スイッチが受け取る信号の送信先の関係は同様である。すなわち、シフト通信パターンを用いた場合、いずれのフェーズにおいても、経路競合が起こらない。そのため、Ｆａｔ  Ｔｒｅｅにおいてシフト通信パターンを用いた場合、全対全通信において高いスループットを実現でき、信号伝送において広い帯域が確保できる。
【００１５】
ここで、図１３及び図１４の説明では、説明を分かり易くするために、全ての信号を３段目までのスイッチを経由して送信先のノードに送信するように説明した。けれども、実際には、各スイッチにおいてネットワークの接続状態が記憶されており、上段に信号を送信しなくても、送信先のノードに信号を送ることができる場合には、１段目及び２段目のスイッチは、下段のスイッチ又は配下のノードに直接信号を送信する。例えば、ノード番号が１のノードからノード番号が２のノードに信号を送信する場合、１段目のスイッチは、ノード番号が１のノードから受信した信号を直接ノード番号が２のノードに送信する。
【００１６】
このようなＦａｔ  Ｔｒｅｅにおいて、２段のＦａｔ  Ｔｒｅｅでは、他の全てのノードに対して１ホップで信号を送信できるように接続されたＦａｔ  Ｔｒｅｅの従来技術が提案されている。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Using  Fat-Trees  to  Maximize  the  Number  of  Processors  in  a  Massively  Parallel  Computer,  M.Valerio,  L.E.Moser  and  P.M.Melliar-Smith,  Department  of  Electrical  and  Computer  Engineering  University  of  California,  Santa  Barbara
【発明の概要】
【発明が解決しようとする課題】
【００１８】
しかしながら、図１３に示したようなＦａｔ  Ｔｒｅｅの接続形態では、ネットワークの規模が増加すると、ノード間の平均ホップ数が増加してしまう。そのため、信号の送信において発生する遅延を抑えることが困難である。
【００１９】
また、他の全てのノードに対して１ホップで信号を送信できるように接続されたＦａｔ  Ｔｒｅｅでは、シフト通信を用いて全対全の通信を行うことが困難であり、信号を送信するための広い帯域を確保することが困難である。
【００２０】
本発明は、１つの側面では、全対全の信号伝送における帯域の確保、遅延の低減を図ったネットワーク装置及びネットワーク管理装置を提供することを目的とする。
【課題を解決するための手段】
【００２１】
本願の開示するネットワーク装置及びネットワーク管理装置は、一つの態様において、ｎ２個の第１信号転送部は、ｎ３個（ｎは２以上の自然数）のアドレスが連番でそれぞれに与えられているｎ３個の信号送受信装置に対して、最小のアドレスから連番でｎ個のアドレスをそれぞれが有するように分けられた信号送受信装置のｎ２個の組合せのいずれかと１対１に対応するように接続されており、宛先のアドレスをｎで割った余りがそれぞれ異なるｎ個の信号を前記信号送受信装置から受信し、受信した信号の送信先のアドレスが自己に接続されている前記信号送受信装置の場合は、該信号送受信装置へ信号を送信し、それ以外の場合は、受信した信号を異なるｎ個の送信先に送信する。ｎ２個の第２信号転送部は、宛先のアドレスをｎで割った余りが同じであるｎ個の信号をｎ個の異なる第１信号転送部から受信し、受信した信号の送信先のアドレスが自己に接続されている前記第１信号転送部の場合は、該第１信号転送部へ信号を送信し、それ以外の場合は、受信した信号の宛先アドレスをｎ２で割った余りに対応する送信先に送信する。ｎ２個の第３信号転送部は、前記第２信号転送部との間でファットツリーの構成を有し、宛先のアドレスをｎ２で割った余りが同じであるｎ個の信号をｎ個の異なる前記第２信号転送部から受信し、前記第２信号転送部から受信した信号を宛先のアドレスを有する前記信号送受信装置に接続されている前記第１信号転送部に接続されている前記第２信号転送部へ出力する。下段接続経路は、前記第３信号転送部とファットツリーを構成する前記第２信号転送部において、前記第１信号転送部との間で、ファットツリーの構成から少なくとも１つの前記第２信号転送部の接続先と他の第２信号転送部の接続先とを交換して接続する。そして、前記第２信号転送部と前記第３信号転送部とはｎ対ｎの組にグループｉ（ｉ＝１、２、・・・、ｎ）に分けられ、それぞれの前記グループｉに含まれる各前記第２信号転送部は、そのグループｉに含まれる全ての前記第３信号転送部と接続し、前記グループｉにおける前記第２信号転送部は、送信先のアドレスをｎ２で割った余りがｉ、ｉ＋ｎ、ｉ＋２ｎ、・・・、ｉ＋（ｎ−１）ｎである信号を、ｎ２で割った余りに対応する前記第３信号転送部へ送信し、ｎ２で割った余りが同じ値になるアドレスを有する前記信号送受信装置から信号を受ける前記第１信号転送部のうちのいずれか異なる前記第１信号転送部から送信先のアドレスをｎで割った余りがｉ、ｉ＋ｎ、ｉ＋２ｎ、・・・、又はｉ＋（ｎ−１）ｎのいずれかになる信号を受信し、且つ少なくとも一つのグループにおける前記第２信号転送部が受信した信号の送信元の前記第１信号転送部に接続されている前記信号送受信装置のアドレスが不連続となる前記第１信号転送部から信号を受信し、さらに、前記第３信号転送部から受信した信号の宛先のアドレスを有する前記信号送受信装置に接続されている第１信号転送部へ送信し、前記第１信号転送部は、前記第２信号転送部から受信した信号を宛先のアドレスを有する信号送受信装置へ送信する。
【発明の効果】
【００２２】
本願の開示するネットワーク装置及びネットワーク管理装置の一つの態様によれば、全対全の信号伝送における帯域の確保、遅延の低減を図ることができる。
【図面の簡単な説明】
【００２３】
【図１】図１は、実施例１に係るネットワーク装置の構成図である。
【図２】図２は、１段目のスイッチと２段目のスイッチの結線における準備を説明するための図である。
【図３】図３は、実施例２に係るネットワーク装置の構成図である。
【図４】図４は、実施例２の変形例に係るネットワーク装置の構成図である。
【図５】図５は、実施例３に係るネットワーク装置の構成図である。
【図６−１】図６−１は、図４の結線における２段目のスイッチと１段目のスイッチとの接続関係を表す図である。
【図６−２】図６−２は、図４の結線における２段目のスイッチと１段目グループとの接続関係を表す図である。
【図７−１】図７−１は、相互直交ラテン方格による２段目のスイッチと１段目グループとの接続関係を表す図である。
【図７−２】図７−２は、直交ラテン方格による２段目のスイッチと１段目のスイッチとの接続関係を表す図である。
【図８】図８は、スイッチのポート数に対応する近接接続スイッチ数を表す図である。
【図９】図９は、スイッチのポート数に対応する近接接続スイッチの割合を表す図である。
【図１０】図１０は、実施例４に係るネットワーク管理装置のブロック図である。
【図１１】図１１は、１段目のスイッチと２段目のスイッチとの結線の決定のフローチャートである。
【図１２】図１２は、１段目のスイッチと２段目のスイッチとの結線の決定の他の例のフローチャートである。
【図１３】図１３は、３段のＦａｔ  Ｔｒｅｅを有するネットワーク装置の構成図である。
【図１４】図１４は、シフト通信パターンを説明するための図である。
【発明を実施するための形態】
【００２４】
以下に、本願の開示するネットワーク装置及びネットワーク管理装置の実施例を図面に基づいて詳細に説明する。なお、以下の実施例により本願の開示するネットワーク装置及びネットワーク管理装置が限定されるものではない。特に、以下では６ポートスイッチ又は８ポートスイッチを用いた場合を例に説明するが、これに限らず以下のようなスイッチであればよい。すなわち、１段目のスイッチは、ノードと接続するポート数と２段目のスイッチに接続するポート数が一致している。また、２段目のスイッチは、１段目のスイッチに接続するポート数と３段目のスイッチとに接続するポートの数が一致している。さらに、３段目のスイッチは、２段目のスイッチと接続するポート数として、２段目のスイッチが３段目のスイッチと接続するポート数と同数のポート数を有していればよい。
【実施例１】
【００２５】
図１は、実施例１に係るネットワーク装置の構成図である。図１に示すように、本実施例に係るネットワーク装置は、スイッチＢ１〜Ｂ９、スイッチＭ１〜Ｍ９及びスイッチＴ１〜Ｔ９を有している。ここで、スイッチＢ１〜Ｂ９をまとめて、１段目のスイッチと言う場合がある。また、スイッチＭ１〜Ｍ９をまとめて、２段目のスイッチと言う場合がある。さらに、スイッチＴ１〜Ｔ９をまとめて、３段目のスイッチと言う場合がある。また、以下では、１段目、２段目及び３段目の各スイッチに振られている数字をそのスイッチの番号と言う。例えば、スイッチＢ１は、１番目の１段目のスイッチであり、スイッチＭ３は、３番目の２段目のスイッチとなる。
【００２６】
さらに、１段目のスイッチには、それぞれ３つのノードが接続されている。すなわち、図１に示すように、全部で２７個のノードがネットワーク装置に接続されている。各ノードは、１段目のスイッチに接続された丸印で表されている。そして、各ノードの下の番号が、各ノードに振られたノード番号である。以下では、ノード番号ＰのノードをノードＰと言う。本実施形態では、スイッチＢ１にノード１〜３が接続されており、スイッチＢ２にノード４〜６が接続されており、スイッチＢ３にノード７〜９が接続されている。また、スイッチＢ４にノード１０〜１２が接続されており、スイッチＢ５にノード１３〜１５が接続されており、スイッチＢ６にノード１６〜１８が接続されている。また、スイッチＢ７にノード１９〜２１が接続されており、スイッチＢ８にノード２２〜２４が接続されており、スイッチＢ９にノード２５〜２７が接続されている。
【００２７】
次に、１段目のスイッチＢ１〜Ｂ９と２段目のスイッチＭ１〜Ｍ９との結線方法について説明する。図２は、１段目のスイッチと２段目のスイッチの結線における準備を説明するための図である。
【００２８】
まず、図２に示すように、本実施例にかかる１段目のスイッチであるスイッチＢ１〜Ｂ９を３つのグループに分ける。グループ分けは、接続されているノードの最小のノード番号を９で割った余りが等しいものをグループとしていくことで行う。すなわち、スイッチＢ１〜Ｂ９を、スイッチＢ１、Ｂ４、及びＢ７、スイッチＢ２、Ｂ５及びＢ８、並びにスイッチＢ３、Ｂ６及びＢ９の３グループに分ける。図２では、スイッチＢ１、Ｂ４、及びＢ７の枠を実線にすることで同グループであることを示しており、このグループをグループ１−１とする。また、図２では、スイッチＢ２、Ｂ５及びＢ８の枠を点線にすることで同グループであることを示しており、このグループをグループ１−２とする。また、図２では、スイッチＢ３、Ｂ６及びＢ９の枠を一点鎖線にすることで同グループであることを示しており、このグループをグループ１−３とする。このグループ分けは、１段目スイッチのスイッチ番号を３で割った余りによってグループ分けを行なってもよい。
【００２９】
さらに、このグループ分けとは別に、スイッチＢ１〜Ｂ９を、枠２０４で囲われたスイッチＢ１〜Ｂ３、枠２０５で囲われたスイッチＢ４〜Ｂ６、及び枠２０６で囲われたスイッチＢ７〜Ｂ９に分ける。
【００３０】
また、２段目のスイッチであるスイッチＭ１〜Ｍ９を、同じ３段目のスイッチに接続されているグループに分ける。すなわち、スイッチＭ１〜Ｍ９を、枠２０１に囲われたスイッチＭ１〜Ｍ３、枠２０２で囲われたスイッチＭ４〜Ｍ６及び枠２０３で囲われたスイッチＭ７〜Ｍ９の３グループに分ける。ここでは、スイッチＭ１〜Ｍ３、スイッチＭ４〜Ｍ６及びスイッチＭ７〜Ｍ９の順に、グループ２−１、グループ２−２及びグループ２−３とする。
【００３１】
接続の条件として以下の条件を満たす必要がある。条件１は以下の条件である。グループ２−１に含まれるスイッチＭ１〜Ｍ３は、１段目のスイッチから送信先のノード番号が１ｍｏｄ９、４ｍｏｄ９及び７ｍｏｄ９である信号を受ける。グループ２−２に含まれるスイッチＭ４〜Ｍ６は、１段目のスイッチから送信先のノード番号が２ｍｏｄ９、５ｍｏｄ及び８ｍｏｄ９である信号を受ける。グループ２−３に含まれるスイッチＭ７〜Ｍ９は、１段目のスイッチから送信先のノード番号が３ｍｏｄ９、６ｍｏｄ及び０ｍｏｄ９である信号を受ける。
【００３２】
また、条件２は、スイッチＭ１〜Ｍ９はいずれも、９で割った余りが異なる３つの信号を受けるという条件である。
【００３３】
また、条件３は、スイッチＭ１〜Ｍ９とスイッチＢ１〜Ｂ９との接続が、図１３に示す従来のＦａｔ  Ｔｒｅｅにおける接続と異なる接続である。すなわち、グループ２−１、グループ２−２及びグループ２−３のうちいずれか一つは、１段目のスイッチとの接続が図１３の接続と異なる接続である。
【００３４】
まず、グループ２−１のスイッチＭ１〜Ｍ３について考える。スイッチＭ１〜Ｍ３は、条件１から１ｍｏｄ３の信号しか受信できない。１ｍｏｄ３は、スイッチＢ１〜Ｂ９の各スイッチに一つずつしかないので、最終的にはスイッチＢ１〜Ｂ９の全てがスイッチＭ１〜Ｍ３のいずれかと繋がることになる。さらに、条件２からスイッチＭ１〜Ｍ３は、グループ１−１、グループ１−２及びグループ１−３のそれぞれから一つずつ接続する１段目のスイッチを選択することになる。言い換えれば、スイッチＭ１〜Ｍ３は、グループ１−１、グループ１−２及びグループ１−３の中で、同じグループから接続先を選ぶことはできない。
【００３５】
そこでまず、スイッチＭ１はグループ１−１のスイッチＢ１、Ｂ４又はＢ８のいずれか一つを選択する。そして、スイッチＭ２は、グループ１−１のスイッチＢ１、Ｂ４又はＢ７のうちスイッチＭ１が選択したスイッチ以外のスイッチのいずれかを選択する。さらに、スイッチＭ３は、グループ１−１のスイッチＢ１、Ｂ４又はＢ７のうちスイッチＭ１及びＭ２が選択したスイッチ以外のスイッチのいずれかを選択する。そして、スイッチＭ１〜Ｍ３は、選択したスイッチから１ｍｏｄ３となる信号を受信する。ここで、本実施例では、１段目のスイッチからの出力のうち、図における紙面に向かって一番左側の経路に１ｍｏｄ３となる信号が出力される。したがって、図を用いて結線を表す場合には、１段目のスイッチからの一番左側の経路をスイッチＭ１〜Ｍ３と結ぶことで、１ｍｏｄ３となる信号を受信するという条件が満たされる。
【００３６】
同様にして、スイッチＭ１〜Ｍ３は、グループ１−２のスイッチＢ２、Ｂ５及びＢ７に対する接続の組合せを選択する。また、スイッチＭ１〜Ｍ３は、グループ１−３のスイッチＢ３、Ｂ６及びＢ９に対する接続の組合せを選択する。そして、スイッチＭ１〜Ｍ３は、選択したスイッチから１ｍｏｄ３となる信号を受信する。
【００３７】
また、スイッチＭ４〜Ｍ６についても、グループ１−１〜グループ１−３に対して同様の選択を行う。そして、スイッチＭ４〜Ｍ６の場合には、選択したスイッチから２ｍｏｄ３となる信号を受信する。ここで、本実施例では、１段目のスイッチからの出力のうち、図における紙面に向かって中央の経路に１ｍｏｄ３となる信号が出力される。したがって、図を用いて結線を表す場合には、１段目のスイッチからの一番左側の経路をスイッチＭ１〜Ｍ３と結ぶことで、２ｍｏｄ３となる信号を受信するという条件が満たされる。
【００３８】
さらに、スイッチＭ７〜Ｍ９についても、グループ１−１〜グループ１−３に対して同様の選択を行う。そして、スイッチＭ７〜Ｍ９の場合には、選択したスイッチから０ｍｏｄ３となる信号を受信する。ここで、本実施例では、１段目のスイッチからの出力のうち、図における紙面に向かって中央の経路に０ｍｏｄ３となる信号が出力される。したがって、図を用いて結線を表す場合には、１段目のスイッチからの一番左側の経路をスイッチＭ１〜Ｍ３と結ぶことで、２ｍｏｄ３となる信号を受信するという条件が満たされる。
【００３９】
ただし、図１３に示すＦａｔ  Ｔｒｅｅの構成よりも平均ホップ数を抑えるために、グループ２−１、グループ２−２及びグループ２−３のうちいずれか一つは、１段目のスイッチとの接続が図１３の接続と異なる接続とする。すなわち、グループ２−１、グループ２−２及びグループ２−３のうちいずれか一つは、含まれる２段目のスイッチのいずれかにおいて接続している１段目のスイッチに接続されているノードのノード番号が不連続となる。スイッチＢ１〜Ｂ９が、「第１転送部」の一例にあたる。また、スイッチＭ１〜Ｍ９が、「第２転送部」の一例にあたる。
【００４０】
次に、本実施例におけるスイッチＢ１〜Ｂ９とスイッチＭ１〜Ｍ９との結線及び信号の転送について図１を参照してより具体的に説明する。
【００４１】
スイッチＭ１は、スイッチＢ１〜Ｂ３と接続されている。また、スイッチＭ２は、スイッチＢ４〜Ｂ６と接続されている。また、スイッチＭ３は、スイッチＢ７〜Ｂ９と接続されている。すなわち、本実施例におけるスイッチＭ１〜Ｍ３と１段目のスイッチとの接続関係は図１３の場合と同様である。
【００４２】
スイッチＭ４は、スイッチＢ２〜Ｂ４と接続されている。また、スイッチＭ５は、スイッチＢ５〜Ｂ７と接続されている。また、スイッチＭ６は、スイッチＢ８、Ｂ９及びＢ１と接続されている。すなわち、本実施例におけるスイッチＭ４〜Ｍ６と１段目のスイッチとの接続関係は図１３の場合でスイッチＭ４〜Ｍ６に接続されている１段目のスイッチの番号を１つずつ増やしたものである。ただし、スイッチの番号がＢ９を超えた場合、Ｂ１に戻るものとする。
【００４３】
スイッチＭ７は、スイッチＢ３〜Ｂ５と接続されている。また、スイッチＭ８は、スイッチＢ６〜Ｂ８と接続されている。また、スイッチＭ９は、スイッチＢ９、Ｂ１及びＢ２と接続されている。すなわち、本実施例におけるスイッチＭ７〜Ｍ９と１段目のスイッチとの接続関係は図１３の場合でスイッチＭ７〜Ｍ９に接続されている１段目のスイッチの番号を２つずつ増やしたものである。ただし、スイッチの番号がＢ９を超えた場合、Ｂ１に戻るものとする。
【００４４】
ここで、本実施例では、スイッチ番号の小さい順に３つの１段目のスイッチを含む３つのグループに１段目のスイッチを分け、さらに、スイッチ番号の小さい順に３つの２段目のスイッチを含む３つのグループに２段目のスイッチを分ける。そして、図１３のようにグループ分けした１段目のスイッチが同じ２段目のスイッチに接続されている状態から、グループ分けした２段目のスイッチ毎にずらす数を１つずつ増やしながら接続する１段目のスイッチをずらしていくことで結線を行なっている。ここで、他のポート数のスイッチを用いた場合も同様の方法で結線を確定することができる。すなわち、スイッチのポート数の半分の数を含むグループに１段目のスイッチ及び２段目のスイッチを分ける。そして、グループ分けした１段目のスイッチが同じ２段目のスイッチに接続されている状態から、グループ分けした２段目のスイッチ毎に１つずつ数を増やして接続する１段目のスイッチをずらしていくことで結線を行なえばよい。
【００４５】
そして、本実施例に係るネットワーク装置では、シフト通信パターンを用いて全対全の通信が行われる。ここで、本実施例に係るネットワーク装置における信号の送信経路を、シフト通信パターンのフェーズ９の場合を例に、信号の送信について説明する。
【００４６】
フェーズ９の場合、枠１０１で囲われた領域の中に示されるノード番号で各ノードのノード番号の下に記載されたノード番号を有するノードに対して各ノードから信号が送信される。例えば、ノード１は、ノード１０に向けて信号が送信する。また、ノード２は、ノード１１に向けて信号を送信する。
【００４７】
スイッチＢ１〜Ｂ９は、接続された各ノードから他のノードに向けて送信された信号を受信する。そして、スイッチＢ１〜Ｂ９は、自己に接続された２段目のスイッチのうち番号が最小の２段目のスイッチに送信先のノード番号が１ｍｏｄ３である信号を送信する。また、スイッチＢ１〜Ｂ９は、自己に接続された２段目のスイッチのうち番号が２番目に小さい２段目のスイッチに送信先のノード番号が２ｍｏｄ３である信号を送信する。さらに、スイッチＢ１〜Ｂ９は、接続された２段目のスイッチのうち番号が最大の２段目のスイッチに送信先のノード番号が０ｍｏｄ３である信号を送信する。ただし、スイッチＢ１〜Ｂ９は、自己に接続されているノードのノード番号を記憶しており、送信先のノード番号が自己に接続されているノードを示している場合には、２段目のスイッチに信号を送信せずに、対応するノードへ信号を送信する。例えば、スイッチＢ１は、ノード２宛てに送信された信号をノード１から受信した場合、スイッチＭ６に信号を送信することなくノード２に対して受信した信号を送信する。
【００４８】
ここで、スイッチＢ１〜Ｂ９からスイッチＭ１〜Ｍ９への信号の送信について詳細に説明する。スイッチＢ１は、送信先のノード番号が１ｍｏｄ３を満たす場合スイッチＭ１に信号を送信し、２ｍｏｄ３を満たす場合スイッチＭ６に信号を送信し、０ｍｏｄ３を満たす場合スイッチＭ９に信号を送信する。例えば、フェーズ９の場合であれば、スイッチＢ１は、ノード１からノード１０宛ての信号を受信し、ノード２からノード１１宛ての信号を受信し、ノード３からノード１２宛ての信号を受信する。そして、スイッチＢ１は、受信した信号のうち送信先のノード番号が１ｍｏｄ３であるノード１０宛ての信号をスイッチＭ１に送信する。また、スイッチＢ１は、受信した信号のうち送信先のノード番号が２ｍｏｄ３であるノード１１宛ての信号をＭ６に送信する。さらに、スイッチＢ１は、受信した信号のうち送信先のノード番号が０ｍｏｄ３であるノード１２宛ての信号をスイッチＭ９に送信する。
【００４９】
また、スイッチＢ２は、送信先のノード番号が１ｍｏｄ３を満たす場合スイッチＭ１に信号を送信し、２ｍｏｄ３を満たす場合スイッチＭ４に信号を送信し、０ｍｏｄ３を満たす場合スイッチＭ９に信号を送信する。例えば、フェーズ９の場合であれば、スイッチＢ２は、ノード４からノード１３宛ての信号を受信し、ノード５からノード１４宛ての信号を受信し、ノード６からノード１５宛ての信号を受信する。そして、スイッチＢ２は、受信した信号のうち送信先のノード番号が１ｍｏｄ３であるノード１３宛ての信号をスイッチＭ１に送信する。また、スイッチＢ２は、受信した信号のうち送信先のノード番号が２ｍｏｄ３であるノード１４宛ての信号をスイッチＭ４に送信する。さらに、スイッチＢ２は、受信した信号のうち送信先のノード番号が０ｍｏｄ３であるノード１５宛ての信号をスイッチＭ９に送信する。
【００５０】
また、スイッチＢ３は、送信先のノード番号が１ｍｏｄ３を満たす場合スイッチＭ１に信号を送信し、２ｍｏｄ３を満たす場合スイッチＭ４に信号を送信し、０ｍｏｄ３を満たす場合スイッチＭ７に信号を送信する。例えば、フェーズ９の場合であれば、スイッチＢ３は、ノード７からノード１６宛ての信号を受信し、ノード８からノード１７宛ての信号を受信し、ノード９からノード１８宛ての信号を受信する。そして、スイッチＢ３は、受信した信号のうち送信先のノード番号が１ｍｏｄ３であるノード１６宛ての信号をスイッチＭ１に送信する。また、スイッチＢ３は、受信した信号のうち送信先のノード番号が２ｍｏｄ３であるノード１７宛ての信号をスイッチＭ４に送信する。さらに、スイッチＢ３は、受信した信号のうち送信先のノード番号が０ｍｏｄ３であるノード１８宛ての信号をスイッチＭ７に送信する。
【００５１】
また、スイッチＢ４は、送信先のノード番号が１ｍｏｄ３を満たす場合スイッチＭ２に信号を送信し、２ｍｏｄ３を満たす場合スイッチＭ４に信号を送信し、０ｍｏｄ３を満たす場合スイッチＭ７に信号を送信する。例えば、フェーズ９の場合であれば、スイッチＢ４は、ノード１０からノード１９宛ての信号を受信し、ノード１１からノード２０宛ての信号を受信し、ノード１２からノード２１宛ての信号を受信する。そして、スイッチＢ４は、受信した信号のうち送信先のノード番号が１ｍｏｄ３であるノード１９宛ての信号をスイッチＭ２に送信する。また、スイッチＢ４は、受信した信号のうち送信先のノード番号が２ｍｏｄ３であるノード２０宛ての信号をスイッチＭ４に送信する。さらに、スイッチＢ４は、受信した信号のうち送信先のノード番号が０ｍｏｄ３であるノード２１宛ての信号をスイッチＭ７に送信する。
【００５２】
また、スイッチＢ５は、送信先のノード番号が１ｍｏｄ３を満たす場合スイッチＭ２に信号を送信し、１ｍｏｄ２を満たす場合スイッチＭ５に信号を送信し、０ｍｏｄ３を満たす場合スイッチＭ７に信号を送信する。例えば、フェーズ９の場合であれば、スイッチＢ５は、ノード１３からノード２２宛ての信号を受信し、ノード１４からノード２３宛ての信号を受信し、ノード１５からノード２４宛ての信号を受信する。そして、スイッチＢ５は、受信した信号のうち送信先のノード番号が１ｍｏｄ３であるノード２１宛ての信号をスイッチＭ２に送信する。また、スイッチＢ５は、受信した信号のうち送信先のノード番号が２ｍｏｄ３であるノード２３宛ての信号をスイッチＭ５に送信する。さらに、スイッチＢ５は、受信した信号のうち送信先のノード番号が０ｍｏｄ３であるノード２４宛ての信号をスイッチＭ７に送信する。
【００５３】
また、スイッチＢ６は、送信先のノード番号が１ｍｏｄ３を満たす場合スイッチＭ２に信号を送信し、１ｍｏｄ２を満たす場合スイッチＭ５に信号を送信し、０ｍｏｄ３を満たす場合スイッチＭ８に信号を送信する。例えば、フェーズ９の場合であれば、スイッチＢ６は、ノード１６からノード２５宛ての信号を受信し、ノード１７からノード２６宛ての信号を受信し、ノード１８からノード２７宛ての信号を受信する。そして、スイッチＢ６は、受信した信号のうち送信先のノード番号が１ｍｏｄ３であるノード２４宛ての信号をスイッチＭ２に送信する。また、スイッチＢ６は、受信した信号のうち送信先のノード番号が２ｍｏｄ３であるノード２６宛ての信号をスイッチＭ５に送信する。さらに、スイッチＢ６は、受信した信号のうち送信先のノード番号が０ｍｏｄ３であるノード２７宛ての信号をスイッチＭ８に送信する。
【００５４】
また、スイッチＢ７は、送信先のノード番号が１ｍｏｄ３を満たす場合スイッチＭ３に信号を送信し、２ｍｏｄ３を満たす場合スイッチＭ５に信号を送信し、０ｍｏｄ３を満たす場合スイッチＭ８に信号を送信する。例えば、フェーズ９の場合であれば、スイッチＢ７は、ノード１９からノード１宛ての信号を受信し、ノード２０からノード２宛ての信号を受信し、ノード２１からノード３宛ての信号を受信する。そして、スイッチＢ７は、受信した信号のうち送信先のノード番号が１ｍｏｄ３であるノード１宛ての信号をスイッチＭ３に送信する。また、スイッチＢ７は、受信した信号のうち送信先のノード番号が２ｍｏｄ３であるノード２宛ての信号をスイッチＭ５に送信する。さらに、スイッチＢ７は、受信した信号のうち送信先のノード番号が０ｍｏｄ３であるノード３宛ての信号をスイッチＭ８に送信する。
【００５５】
また、スイッチＢ８は、送信先のノード番号が１ｍｏｄ３を満たす場合スイッチＭ３に信号を送信し、１ｍｏｄ２を満たす場合スイッチＭ６に信号を送信し、０ｍｏｄ３を満たす場合スイッチＭ８に信号を送信する。例えば、フェーズ９の場合であれば、スイッチＢ８は、ノード２２からノード４宛ての信号を受信し、ノード２３からノード５宛ての信号を受信し、ノード２４からノード６宛ての信号を受信する。そして、スイッチＢ８は、受信した信号のうち送信先のノード番号が１ｍｏｄ３であるノード４宛ての信号をスイッチＭ３に送信する。また、スイッチＢ８は、受信した信号のうち送信先のノード番号が２ｍｏｄ３であるノード５宛ての信号をスイッチＭ６に送信する。さらに、スイッチＢ８は、受信した信号のうち送信先のノード番号が０ｍｏｄ３であるノード６宛ての信号をスイッチＭ８に送信する。
【００５６】
また、スイッチＢ９は、送信先のノード番号が１ｍｏｄ３を満たす場合スイッチＭ３に信号を送信し、１ｍｏｄ２を満たす場合スイッチＭ６に信号を送信し、０ｍｏｄ３を満たす場合スイッチＭ９に信号を送信する。例えば、フェーズ９の場合であれば、スイッチＢ９は、ノード２５からノード７宛ての信号を受信し、ノード２６からノード８宛ての信号を受信し、ノード２７からノード９宛ての信号を受信する。そして、スイッチＢ９は、受信した信号のうち送信先のノード番号が１ｍｏｄ３であるノード７宛ての信号をスイッチＭ３に送信する。また、スイッチＢ９は、受信した信号のうち送信先のノード番号が２ｍｏｄ３であるノード８宛ての信号をスイッチＭ６に送信する。さらに、スイッチＢ９は、受信した信号のうち送信先のノード番号が０ｍｏｄ３であるノード９宛ての信号をスイッチＭ９に送信する。
【００５７】
ここで、図１におけるスイッチＭ１〜Ｍ９の下に記載された番号は、フェーズ９において、スイッチＭ１〜Ｍ９のそれぞれが１段目のスイッチから受信する信号の送信先のノード番号を示している。このように、各２段目のスイッチは、異なる１段目のスイッチから送信された信号を３つずつ受信する。すなわち、シフト通信パターンを用いた場合に、１段目のスイッチから２段目のスイッチへと信号が送信されるときにおいては、同じ経路に２つ以上の信号が流れることが無いため、信号伝送において広い帯域を確保することができる。
【００５８】
また、スイッチＢ１〜Ｂ９は、スイッチＭ１〜Ｍ９から自己に接続されているノード宛の信号を受信した場合、その送信先のノード番号を有するノードに信号を転送する。ただし、スイッチＭ１〜Ｍ９は、自己に接続している１段目のスイッチに接続されているノードのノード番号を記憶している。そして、スイッチＭ１〜Ｍ９は、受信した信号の送信先のノード番号が自己に接続している１段目のスイッチに接続しているノードのノード番号であれば、そのノード番号を有するノードが接続された１段目のスイッチに信号を送信する。
【００５９】
スイッチＢ１〜Ｂ９から１ホップで届く他の１段目のスイッチは、図１３の場合に比べて増えている。以下では、あるスイッチから１ホップで届くスイッチのことを、そのスイッチに対する「近接接続スイッチ」という場合がある。例えば、図１３では、スイッチＢ１に対する近接接続スイッチは、スイッチＢ２及びスイッチＢ３だけであった。これに対して、図１では、スイッチＢ１は、スイッチＢ２、Ｂ３、Ｂ８及びＢ９という４つのスイッチが近接接続スイッチとなっている。このように、本実施例に係るネットワーク装置は、従来の図１３に示すような構成に比べて、平均ホップ数が削減される。そのため、図１３に示すような構成に比べて、信号伝送の遅延を軽減することができる。
【００６０】
スイッチＭ１〜Ｍ３のそれぞれは、スイッチＴ１〜Ｔ３の全てに接続されている。また、スイッチＭ４〜Ｍ７のそれぞれは、スイッチＴ４〜Ｔ６の全てに接続されている。さらに、スイッチＭ８〜Ｍ９のそれぞれは、スイッチＴ７〜Ｔ９の全てに接続されている。すなわち、２段目のスイッチと３段目のスイッチとは、図１３に示した従来のＦａｔ  Ｔｒｅｅにおける結線と同じように結線されている。
【００６１】
スイッチＭ１〜Ｍ９は、スイッチＢ１〜Ｂ９から信号を受信する。
【００６２】
スイッチＭ１〜Ｍ３は、送信先のノード番号が１ｍｏｄ９の信号をスイッチＴ１へ送信する。また、スイッチＭ１〜Ｍ３は、送信先のノード番号が４ｍｏｄ９の信号をスイッチＴ２へ送信する。また、スイッチＭ１〜Ｍ３は、送信先のノード番号が７ｍｏｄ９の信号をスイッチＴ３へ送信する。
【００６３】
スイッチＭ４〜Ｍ６は、送信先のノード番号が２ｍｏｄ９の信号をスイッチＴ４へ送信する。また、スイッチＭ４〜Ｍ６は、送信先のノード番号が５ｍｏｄ９の信号をスイッチＴ５へ送信する。また、スイッチＭ４〜Ｍ６は、送信先のノード番号が８ｍｏｄ９の信号をスイッチＴ６へ送信する。
【００６４】
スイッチＭ７〜Ｍ９は、送信先のノード番号が３ｍｏｄ９の信号をスイッチＴ７へ送信する。また、スイッチＭ７〜Ｍ９は、送信先のノード番号が６ｍｏｄ９の信号をスイッチＴ８へ送信する。また、スイッチＭ７〜Ｍ９は、送信先のノード番号が０ｍｏｄ９の信号をスイッチＴ９へ送信する。
【００６５】
スイッチＴ１〜Ｔ９は、自己から各ノードまでの経路を記憶している。スイッチＴ１〜Ｔ９は、フェーズ９では送信先のノード番号が１ｍｏｄ９である信号を受信する。そして、スイッチＴ１〜Ｔ９は、受信した信号の送信先のノード番号を有するノードが接続されている１段目のスイッチが接続している２段目のスイッチを特定し、特定した２段目のスイッチに向けて受信した信号を送信する。スイッチＴ１〜Ｔ９が、「第３転送部」の一例にあたる。
【００６６】
このように１段目〜３段目のスイッチを接続することで、シフト通信パターンを用いて通信した場合に、各経路において送信信号の経路競合が起こらない。そのため、信号伝送において広い帯域を確保することができる。
【００６７】
また、このように、１段目〜３段目のスイッチを接続することで、スイッチＢ１〜Ｂ９に対する近接接続スイッチを図１３の場合に比べて増やすことができる。すなわち、本実施例に係るネットワーク装置は、従来の図１３に示すような構成に比べて、平均ホップ数が削減される。そのため、図１３に示すような構成に比べて、信号伝送の遅延を軽減することができる。
【００６８】
次に、本実施例におけるスイッチＭ１〜Ｍ９からスイッチＴ１〜Ｔ９に対する信号の送信について図１を参照してより具体的に説明する。
【００６９】
フェーズ９の場合、スイッチＭ１は、ノード１０、１３及び１６に宛てた信号を受信する。そこで、スイッチＭ１は、ノード１０宛ての信号をスイッチＴ１に送信し、ノード１３宛ての信号をスイッチＴ２に送信し、ノード１６宛ての信号をスイッチＴ３に送信する。また、スイッチＭ２は、ノード１９、２２及び２５に宛てた信号を受信する。そこで、スイッチＭ２は、ノード１９宛ての信号をスイッチＴ１に送信し、ノード２２宛ての信号をスイッチＴ２に送信し、ノード２５宛ての信号をスイッチＴ３に送信する。また、スイッチＭ３は、ノード１、４及び７に宛てた信号を受信する。そこで、スイッチＭ３は、ノード１宛ての信号をスイッチＴ１に送信し、ノード４宛ての信号をスイッチＴ２に送信し、ノード７宛ての信号をスイッチＴ３に送信する。
【００７０】
また、フェーズ９の場合、スイッチＭ４は、ノード２０、１４及び１７に宛てた信号を受信する。そこで、スイッチＭ４は、ノード２０宛ての信号をスイッチＴ４に送信し、ノード１４宛ての信号をスイッチＴ５に送信し、ノード１７宛ての信号をスイッチＴ６に送信する。また、スイッチＭ５は、ノード２、２３及び２６に宛てた信号を受信する。そこで、スイッチＭ５は、ノード２宛ての信号をスイッチＴ４に送信し、ノード２３宛ての信号をスイッチＴ５に送信し、ノード２６宛ての信号をスイッチＴ６に送信する。また、スイッチＭ６は、ノード１１、５及び８に宛てた信号を受信する。そこで、スイッチＭ６は、ノード１１宛ての信号をスイッチＴ４に送信し、ノード５宛ての信号をスイッチＴ５に送信し、ノード８宛ての信号をスイッチＴ６に送信する。
【００７１】
フェーズ９の場合、スイッチＭ７は、ノード２１、２４及び１８に宛てた信号を受信する。そこで、スイッチＭ７は、ノード２１宛ての信号をスイッチＴ７に送信し、ノード２４宛ての信号をスイッチＴ８に送信し、ノード１８宛ての信号をスイッチＴ９に送信する。また、スイッチＭ８は、ノード３、６及び２７に宛てた信号を受信する。そこで、スイッチＭ８は、ノード３宛ての信号をスイッチＴ７に送信し、ノード６宛ての信号をスイッチＴ８に送信し、ノード２７宛ての信号をスイッチＴ９に送信する。また、スイッチＭ９は、ノード１２、１５及び９に宛てた信号を受信する。そこで、スイッチＭ９は、ノード１２宛ての信号をスイッチＴ７に送信し、ノード１５宛ての信号をスイッチＴ８に送信し、ノード９宛ての信号をスイッチＴ９に送信する。
【００７２】
ここで、図１におけるスイッチＴ１〜Ｔ９の下に記載された番号は、フェーズ９において、スイッチＴ１〜Ｔ９のそれぞれが２段目のスイッチから受信する信号の送信先のノード番号を示している。また、スイッチＴ１〜Ｔ９の上に記載されたＭＯＤ関数は、フェーズ９において、スイッチＴ１〜Ｔ９のそれぞれが２段目のスイッチから受信する信号の送信先が満たす条件を表している。このように、各３段目のスイッチは、異なる２段目のスイッチから送信された信号を３つずつ受信する。すなわち、シフト通信パターンを用いた場合に、２段目のスイッチから３段目のスイッチへと信号が送信されるときにおいても、同じ経路に２つ以上の信号が流れることが無いため、信号伝送において広い帯域を確保することができる。
【００７３】
ここで、以上ではシフト通信パターンにおけるフェーズ９の場合について説明したが、他のフェーズの場合でも、同様に、同じ経路に２つ以上の信号が送信されることは無い。そのため、本実施例に係るネットワーク装置においては、シフト通信パターンを用いた通信を行った場合に信号伝送において広い帯域を確保することができる。
【実施例２】
【００７４】
図３は、実施例２に係るネットワーク装置の構成図である。本実施例に係るネットワーク装置は、１段目のスイッチと２段目のスイッチとの結線が実施例１と異なるものである。そこで、以下では、１段目のスイッチと２段目のスイッチとの結線について主に説明する。特に、２段目のスイッチ以降の接続及び信号の流れは実施例１と同様であるので省略する。
【００７５】
そこで、本実施例に係るネットワーク装置における１段目のスイッチと２段目のスイッチとの結線方法について説明する。
【００７６】
先ほどのグループ分けに加えて、図２に示すように１段目のスイッチを番号の小さい順に３つずつ選びグループ分けする。すなわち、スイッチＢ１〜Ｂ９を、実線２０４で囲われたスイッチＢ１〜Ｂ３、点線２０５で囲われたスイッチＢ４〜Ｂ６、及び一点鎖線２０６で囲われたスイッチＢ７〜Ｂ９に分ける。そして、実線２０４で囲われたグループをグループＡ、点線２０５で囲われたグループをグループＢ、及び一点鎖線２０６で囲われたグループをグループＣとする。さらに、グループ１−１〜グループ１−３をまとめて「等余グループ」という。また、グループＡ〜グループＣをまとめて「１段目グループ」という。さらに、グループＡの隣のグループはグループＢであり、グループＢの隣のグループはグループＣであり、グループＣの隣のグループはグループＡであるとする。
【００７７】
まず、スイッチＭ１〜Ｍ３は、図１３で示すＦａｔ  Ｔｒｅｅの構成と同じ接続とする。すなわち、スイッチＭ１は、スイッチＢ１、Ｂ２及びＢ３と接続される。スイッチＭ２は、スイッチＢ４、Ｂ５及びＢ６と接続される。さらに、スイッチＭ３は、スイッチＢ７、Ｂ８及びＢ９と接続される。
【００７８】
次に、スイッチＭ４はグループＡの中のグループ１−１にあたるスイッチＢ１を選択する。また、スイッチＭ４は、グループＡの隣のグループＢからグループ１−２にあたるスイッチＢ５を選択する。さらに、スイッチＭ４は、グループＢの隣のグループＣからグループ１−３にあたるスイッチＢ９を選択する。
【００７９】
そして、スイッチＭ５は、スイッチＭ４が各等余グループに含まれるスイッチを選択した１段目グループの隣の１段目グループからスイッチＭ４が選択したのと同じ等余グループに含まれるスイッチを選択する。また、スイッチＭ６は、スイッチＭ５が各等余グループに含まれるスイッチを選択した１段目グループの隣のグループからスイッチＭ５が選択したのと同じ等余グループに含まれるスイッチを選択する。
【００８０】
次に、スイッチＭ７はグループＡの中のグループ１−１にあたるスイッチＢ１を選択する。また、スイッチＭ７は、グループＡの２つ隣のグループＣからグループ１−２にあたるスイッチＢ８を選択する。さらに、スイッチＭ７は、グループＣの２つ隣のグループＢからグループ１−３にあたるスイッチＢ６を選択する。
【００８１】
そして、スイッチＭ８は、スイッチＭ７が各等余グループに含まれるスイッチを選択した１段目グループの隣の１段目グループからスイッチＭ４が選択したのと同じ等余グループに含まれるスイッチを選択する。また、スイッチＭ９は、スイッチＭ８が各等余グループに含まれるスイッチを選択した１段目グループの隣のグループからスイッチＭ５が選択したのと同じ等余グループに含まれるスイッチを選択する。
【００８２】
このように、接続先を選択すると、図３のような結線状態となる。そこで、図３の接続状態でシフト通信パターンを用いて全対全通信を行った場合のフェーズ９における通信を例に説明する。
【００８３】
スイッチＢ１は、ノード１から受信したノード１０宛ての信号を、送信先のノード番号が１ｍｏｄ３なので、スイッチＭ１へ送信する。また、スイッチＢ１は、ノード２から受信したノード１１宛ての信号を、送信先のノード番号が２ｍｏｄ３なので、スイッチＭ４へ送信する。さらに、スイッチＢ１は、ノード３から受信したノード１２宛ての信号を、送信先のノード番号が０ｍｏｄ３なので、スイッチＭ７へ送信する。
【００８４】
スイッチＢ２は、ノード４から受信したノード１３宛ての信号を、送信先のノード番号が１ｍｏｄ３なので、スイッチＭ１へ送信する。また、スイッチＢ２は、ノード５から受信したノード１４宛ての信号を、送信先のノード番号が２ｍｏｄ３なので、スイッチＭ４へ送信する。さらに、スイッチＢ２は、ノード６から受信したノード１５宛ての信号を、送信先のノード番号が０ｍｏｄ３なので、スイッチＭ８へ送信する。
【００８５】
スイッチＢ３は、ノード７から受信したノード１６宛ての信号を、送信先のノード番号が１ｍｏｄ３なので、スイッチＭ１へ送信する。また、スイッチＢ３は、ノード８から受信したノード１７宛ての信号を、送信先のノード番号が２ｍｏｄ３なので、スイッチＭ５へ送信する。さらに、スイッチＢ３は、ノード９から受信したノード１８宛ての信号を、送信先のノード番号が０ｍｏｄ３なので、スイッチＭ９へ送信する。
【００８６】
スイッチＢ４は、ノード１０から受信したノード１９宛ての信号を、送信先のノード番号が１ｍｏｄ３なので、スイッチＭ２へ送信する。また、スイッチＢ４は、ノード１１から受信したノード２０宛ての信号を、送信先のノード番号が２ｍｏｄ３なので、スイッチＭ５へ送信する。さらに、スイッチＢ４は、ノード１２から受信したノード２１宛ての信号を、送信先のノード番号が０ｍｏｄ３なので、スイッチＭ８へ送信する。
【００８７】
スイッチＢ５は、ノード１３から受信したノード２２宛ての信号を、送信先のノード番号が１ｍｏｄ３なので、スイッチＭ２へ送信する。また、スイッチＢ５は、ノード１４から受信したノード２３宛ての信号を、送信先のノード番号が２ｍｏｄ３なので、スイッチＭ４へ送信する。さらに、スイッチＢ５は、ノード１５から受信したノード２４宛ての信号を、送信先のノード番号が０ｍｏｄ３なので、スイッチＭ９へ送信する。
【００８８】
スイッチＢ６は、ノード１６から受信したノード２５宛ての信号を、送信先のノード番号が１ｍｏｄ３なので、スイッチＭ２へ送信する。また、スイッチＢ６は、ノード１７から受信したノード２６宛ての信号を、送信先のノード番号が２ｍｏｄ３なので、スイッチＭ６へ送信する。さらに、スイッチＢ６は、ノード１８から受信したノード２７宛ての信号を、送信先のノード番号が０ｍｏｄ３なので、スイッチＭ７へ送信する。
【００８９】
スイッチＢ７は、ノード１９から受信したノード１宛ての信号を、送信先のノード番号が１ｍｏｄ３なので、スイッチＭ３へ送信する。また、スイッチＢ７は、ノード２０から受信したノード２宛ての信号を、送信先のノード番号が２ｍｏｄ３なので、スイッチＭ６へ送信する。さらに、スイッチＢ７は、ノード２１から受信したノード３宛ての信号を、送信先のノード番号が０ｍｏｄ３なので、スイッチＭ８へ送信する。
【００９０】
スイッチＢ８は、ノード２２から受信したノード４宛ての信号を、送信先のノード番号が１ｍｏｄ３なので、スイッチＭ３へ送信する。また、スイッチＢ８は、ノード２３から受信したノード５宛ての信号を、送信先のノード番号が２ｍｏｄ３なので、スイッチＭ５へ送信する。さらに、スイッチＢ８は、ノード２４から受信したノード６宛ての信号を、送信先のノード番号が０ｍｏｄ３なので、スイッチＭ７へ送信する。
【００９１】
スイッチＢ９は、ノード２５から受信したノード７宛ての信号を、送信先のノード番号が１ｍｏｄ３なので、スイッチＭ３へ送信する。また、スイッチＢ９は、ノード２６から受信したノード８宛ての信号を、送信先のノード番号が２ｍｏｄ３なので、スイッチＭ４へ送信する。さらに、スイッチＢ９は、ノード２７から受信したノード９宛ての信号を、送信先のノード番号が０ｍｏｄ３なので、スイッチＭ８へ送信する。
【００９２】
また、スイッチＢ１〜Ｂ９は、自己に接続されているノードのノード番号を記憶している。そして、スイッチＭ１〜Ｍ９から自己に接続されているノード宛の信号を受信した場合、その送信先のノード番号を有するノードに信号を転送する。さらに、スイッチＭ１〜Ｍ９は、自己に接続している１段目のスイッチに接続されているノードのノード番号を記憶している。そして、スイッチＭ１〜Ｍ９は、受信した信号の送信先のノード番号が自己に接続している１段目のスイッチに接続しているノードのノード番号であれば、そのノード番号を有するノードが接続された１段目のスイッチに信号を送信する。
【００９３】
ここで、図３におけるスイッチＭ１〜Ｍ９の下に記載された番号は、フェーズ９において、スイッチＭ１〜Ｍ９のそれぞれが１段目のスイッチから受信する信号の送信先のノード番号を示している。図３に示すように、各２段目のスイッチは、異なる１段目のスイッチから送信された信号を３つずつ受信する。すなわち、シフト通信パターンを用いた場合に、１段目のスイッチから２段目のスイッチへと信号が送信されるときにおいては、同じ経路に２つ以上の信号が流れることが無いため、信号伝送において広い帯域を確保することができる。
【００９４】
また、スイッチＭ１〜Ｍ９のそれぞれが受信した信号の送信先は、それぞれ異なる３段目のスイッチに送信するノード番号となっている。そのため、シフト通信パターンを用いた場合に、２段目のスイッチから３段目のスイッチへと信号が送信されるときにおいても、同じ経路に２つ以上の信号が流れることが無いため、信号伝送において広い帯域を確保することができる。
【００９５】
さらに、スイッチＢ１〜Ｂ９に対する近接接続スイッチは、図１３の場合に比べて増えている。例えば、図１３では、スイッチＢ１に対する近接接続スイッチは、スイッチＢ２及びスイッチＢ３だけであった。これに対して、図３では、例えば、スイッチＢ１に対する近接接続スイッチは、スイッチＢ２、Ｂ３、Ｂ５、Ｂ６、Ｂ８及びＢ９の６つである。このように、本実施例に係るネットワーク装置は、従来の図１３に示すような構成に比べて、平均ホップ数が削減される。
【００９６】
なお、この構成例では、ｎ３個全てのノードが揃った構成であるが、従来のＦａｔ  Ｔｒｅｅ構成においてよく用いられる一部のノード及び１段目のスイッチを取り除いた構成でもよい。例えば、従来のＦａｔ  Ｔｒｅｅでは、図１３のような構成において、Ｂ８やＢ９およびその配下のノードを取り除いた構成でも経路競合を避けることができる。
【００９７】
また、さらに、Ｂ７の配下のノード２０と２１とを削除するような構成の場合は、全対全通信時に一部経路競合が生じるものの、競合の程度は従来のＦａｔ  Ｔｒｅｅ構成における同様の構成と同程度であり、実用上問題ない。
【００９８】
（変形例）
図４は、実施例２の変形例に係るネットワーク装置の構成図である。次に、実施例２の変形例として、８ポートスイッチを用いた場合について説明する。本変形例に係るネットワーク装置は、１段目のスイッチとして、１６個のスイッチＢ１〜Ｂ１６を有し、２段目のスイッチとして、１６個のスイッチＭ１〜Ｍ１６を有し、３段目のスイッチとして、１６個のスイッチＴ１〜Ｔ１６を有する。
【００９９】
そして、１〜６４までのノード番号が振られた６４個のノードが配置されている。実線３００で囲まれた領域に記載された数字が、対応する１段目のスイッチに接続されているノードのノード番号を表している。具体的には、スイッチＢｉ（ｉ＝１、２、・・・、１６）には、ノード４（ｉ−１）＋１〜４ｉが接続されている。
【０１００】
ここで、スイッチＢ１〜Ｂ１６を番号が小さい順に４つずつ選んでグループとしていき、４つのグループを作る。そして、スイッチＢ１〜Ｂ４のグループをグループ３０１、スイッチＢ５〜Ｂ８のグループをグループ３０２、スイッチＢ９〜Ｂ１２のグループをグループ３０３、スイッチＢ１３〜Ｂ１６のグループをグループ３０４とする。そして、グループ３０１〜３０４をまとめて「１段目グループ」と呼ぶ。
【０１０１】
スイッチＭ１は、グループ３０１から４つのスイッチを選択する。そして、スイッチＭ２は、スイッチＭ１が各等余グループに含まれるスイッチを選択した１段目グループの隣の１段目グループからスイッチＭ１が選択したのと同じ等余グループに含まれるスイッチを選択する。また、スイッチＭ３は、スイッチＭ２が各等余グループに含まれるスイッチを選択した１段目グループの隣のグループからスイッチＭ２が選択したのと同じ等余グループに含まれるスイッチを選択する。また、スイッチＭ４は、スイッチＭ３が各等余グループに含まれるスイッチを選択した１段目グループの隣の１段目グループからスイッチＭ３が選択したのと同じ等余グループに含まれるスイッチを選択する。
【０１０２】
次に、スイッチＭ５は、グループ３０１を最初として、順次隣のグループを選択しながら、スイッチ番号が１ｍｏｄ４、２ｍｏｄ４、３ｍｏｄ４、０ｍｏｄ４となる１段目のスイッチを順次選択したグループの順番に対応させて選択していく。この場合、スイッチＭ５は、グループ３０１、３０２、３０３、３０４の順にグループを選択することになる。そして、スイッチＭ６〜Ｍ８は、スイッチＭ１に対するスイッチＭ２〜Ｍ４と同様に１段目のスイッチを選択する。
【０１０３】
次に、スイッチＭ９は、グループ３０１を最初として、順次２つ隣のグループを選択しながら、スイッチ番号が１ｍｏｄ４、２ｍｏｄ４、３ｍｏｄ４、０ｍｏｄ４となる１段目のスイッチを順次選択したグループの順番に対応させて選択していく。この場合、スイッチＭ９は、グループ３０１、３０３、３０１、３０３の順にグループ選択することになる。そして、スイッチＭ１０〜Ｍ１２は、スイッチＭ１に対するスイッチＭ２〜Ｍ４と同様に１段目のスイッチを選択する。
【０１０４】
次に、スイッチＭ１３は、グループ３０１を最初として、順次３つ隣のグループを選択しながら、スイッチ番号が１ｍｏｄ４、２ｍｏｄ４、３ｍｏｄ４、０ｍｏｄ４となる１段目のスイッチを順次選択したグループの順番に対応させて選択していく。この場合、スイッチＭ１３は、グループ３０１、３０４、３０３、３０２の順にグループ選択することになる。そして、スイッチＭ１４〜Ｍ１６は、スイッチＭ１に対するスイッチＭ２〜Ｍ４と同様に１段目のスイッチを選択する。
【０１０５】
このように、スイッチＭ１〜Ｍ１６に接続されるスイッチＢ１〜Ｍ１６を選択すると、スイッチＭ１〜Ｍ１６とスイッチＢ１〜Ｂ１６の結線は、図４に示す結線となる。
【０１０６】
ここで、図４のように接続した場合の、シフト通信パターンを用いて全対全通信を行った場合のフェーズ９における信号の流れについて説明する。フェーズ９の場合、各ノードが送信する信号の送信先のノード番号は、実線３０５で囲われた領域に記載されている、各ノードに対応している番号となる。
【０１０７】
そして、実線３０５で囲われたノード番号に対して各ノードから信号が送信されると、スイッチＭ１〜Ｍ１６は、それぞれの下に記載された番号を送信先のノード番号とする信号を受信する。これらの番号は全て異なる番号であり、スイッチＭ１〜Ｍ１６とスイッチＢ１〜Ｂ１６とを結ぶ経路では、信号の経路競合が発生しない。したがって、１段目のスイッチと２段目のスイッチとの間では、信号伝送において広い帯域が確保できている。
【０１０８】
また、スイッチＭ１〜Ｍ１６の下に記載された番号を送信先のノード番号とする信号は、スイッチＭ１〜Ｍ１６のそれぞれ接続された異なる３段目のスイッチに送られる。したがって、スイッチＭ１〜Ｍ１６とスイッチＴ１〜Ｔ１６とを結ぶ経路では、信号の経路競合が発生しない。そのため、２段目のスイッチと３段目のスイッチとの間でも、信号伝送において広い帯域が確保できている。
【０１０９】
さらに、スイッチＢ１〜Ｂ９に対する近接接続スイッチは、従来のＦａｔ  Ｔｒｅｅの構成を用いた場合に比べて増えている。従来のＦａｔ  Ｔｒｅｅの構成の場合、スイッチＢ１に対する近接接続スイッチは、スイッチＢ２〜Ｂ６だけであった。これに対して、図４では、例えば、スイッチＢ１に対する近接接続スイッチは、スイッチＢ２〜Ｂ６だけでなく、Ｂ６、Ｂ８、Ｂ１０〜Ｂ１２、Ｂ１４及びＢ１６も含まれる。このように、本実施例に係るネットワーク装置は、従来の図１３に示すような構成に比べて、平均ホップ数が削減される。
【０１１０】
以上に説明したように、本実施例では、各２段目グループの先頭の２段目のスイッチに接続する１段目のスイッチを選択する１段目グループを１つ隣、２つ隣というように数を順次増やしていく方法で結線を行なっている。そして、２ｎポートのスイッチを用いた３段のネットワーク装置において、ｎが素数であれば、本実施例で説明した同様の結線方法を用いることで、各１段目のスイッチに対する近接接続スイッチの数を最大のｎ（ｎ−１）とすることができる。なぜなら、ｎが素数でない場合、本実施例で説明した結線方法では、１段目のスイッチを選択した場合、それに接続される２段目のスイッチにおいて、一部共通の１段目のスイッチを選択してしまうからである。
【実施例３】
【０１１１】
次に、実施例３に係るネットワーク装置について説明する。図５は、実施例３に係るネットワーク装置の構成図である。本実施例に係るネットワーク装置は、実施例２とは異なる方法を用いることで、ｎが素数以外の場合に１段目のスイッチに対する近接接続スイッチを最大にした構成である。そこで、以下では、ｎが素数以外の場合に１段目のスイッチに対する近接接続スイッチを最大にする結線方法について説明する。
【０１１２】
そこで、実施例１の変形例における８ポートスイッチを用いた３段のネットワーク装置の場合を例に、１段目のスイッチに対する近接接続スイッチを最大にする方法を説明する。
【０１１３】
図６−１は、図４の結線における２段目のスイッチと１段目のスイッチとの接続関係を表す図である。図６−１の方格５０１〜５０４は、方格の紙面に向かって左側に記載した番号を有する２段目のスイッチとその行に並ぶ番号を有する１段目のスイッチとが接続関係にあることを表している。例えば、方格５０１におけるＭ１の行に並ぶＢ１〜Ｂ４は、スイッチＢ１〜Ｂ４がスイッチＭ１と接続関係にあることを表している。また、各方格の列は紙面に向かって左から順にそれぞれ１ｍｏｄ４、２ｍｏｄ４、３ｍｏｄ４、０ｍｏｄ５となるノード番号を有するスイッチであることを表している。
【０１１４】
さらに、図６−２は、図４の結線における２段目のスイッチと１段目グループとの接続関係を表す図である。図６−２は、図４における１段目のスイッチをそのスイッチが属する１段目グループの番号の末尾の数字に変更したものである。
【０１１５】
図６−１における、格子５１１及び５１２からスイッチＢ１及びＢ３がスイッチＭ１に接続していることが分かる。また、格子５３１及び５３２からスイッチＢ１及びＢ３がスイッチＭ９に接続していることが分かる。すなわち、スイッチＢ１及びＢ３は、共通の２段目のスイッチと接続されている経路を２つ有する。この重なりが解消されれば、近接接続スイッチの数がさらに増える。そこで、格子５１１及び５１２と格子５３１及び５３２との重なりを解消するために、Ｍ９の行にＢ３が出現しないようにすればよい。すなわち、方格５０３が、縦方向及び横方向ともに同じ数が存在しない並びとなるラテン方格を構成すればよい。
【０１１６】
次に、方格５０２及び５０４における、格子５２１及び５２２と格子５４１及び５４２との重なりの解消について説明する。図６−２において、方格５０６及び方格５０８は共にラテン方格である。しかし、格子５６１及び５６２と格子５８１及び５８２とにおいて重なりが生じている。そこで、方格５０５〜５０８のそれぞれを、相互に直交するラテン方格（以下では、「相互直交ラテン方格」という。）にすることで重なりが解消される。
【０１１７】
相互直交ラテン方格は、例えば、一辺の長さをｎとすると、ｎが素数のべき乗であるとき、ｎ−１個の相互直交ラテン方格が存在し、それぞれ求めることができる。この算出には、既知の相互直交ラテン方格導出方法を用いればよい。
【０１１８】
そこで、図６−２の各方格は、一辺の長さが４であり、素数２の２乗である。そこで、既知の相互直交ラテン方格導出方法を用いて、図６−２の各方格に対応する相互直交ラテン方格を求めることができる。図７−１は、相互直交ラテン方格による２段目のスイッチと１段目グループとの接続関係を表す図である。方格６０１〜６０４は、図６−２の方格５０５〜５０８を相互直交ラテン方格に変換したものである。方格６０１〜６０４は、相互に直交するラテン方格となっている。
【０１１９】
次に、方格６０１〜６０４に対応する末尾の数の１段目グループに含まれ、且つ各方格の紙面に向かって左から順にそれぞれ１ｍｏｄ４、２ｍｏｄ４、３ｍｏｄ４、０ｍｏｄ５となるノード番号を有するスイッチを割り当てて、図７−２に示す方格６０５〜６０８を生成する。図７−２は、直交ラテン方格による２段目のスイッチと１段目のスイッチとの接続関係を表す図である。すなわち、図７−２に示す接続関係となるように、２段目のスイッチと１段目のスイッチとを結線することで、近接接続スイッチを最大にしたネットワーク装置が生成できる。図７−２に示す接続関係になるように２段目のスイッチと１段目のスイッチとを結線すると、図５に示す接続関係を有するネットワーク装置が生成できる。
【０１２０】
図５に示すネットワーク装置では、いずれの１段目のスイッチに対しても近接接続スイッチの数が１２となり、最大となる。
【０１２１】
以上に説明したように、本実施例に係るネットワーク装置は、縦に２段目グループ毎に各２段目のスイッチに接続される１段目のスイッチを行に並べ、列が４で割った余りが１、２、３、０となる方格を生成した場合、各方格が相互直交ラテン方格となっている。これにより、１段目のスイッチに対する近接接続スイッチの数を最大にすることができ、平均ホップ数を最小にすることができる。
【０１２２】
次に、用いるスイッチのポート数を変化させた場合の、実施例２及び実施例３の結線方法を用いて結線を行った場合の近接接続スイッチの数について説明する。図８は、スイッチのポート数に対応する近接接続スイッチ数を表す図である。また、図９は、スイッチのポート数に対応する近接接続スイッチの割合を表す図である。
【０１２３】
図８は、縦軸を近接接続スイッチの数とし、横軸をスイッチのポート数としている。そして、図８のグラフ７０１が実施例２の結線方法を用いた場合の近接接続スイッチの変化を表している。また、三角の点で表される点が実施例３の結線方法を用いて実施例２の接続方法を修正した場合の近接接続スイッチの数を表している。さらに、グラフ７０２は、従来のＦａｔ  Ｔｒｅｅの結線方法を用いた場合の近接接続スイッチの数の変化を表している。
【０１２４】
図９は、縦軸を任意のスイッチにおける他のスイッチ全てに対する近接接続スイッチの理論上の上限に対する割合とし、横軸をスイッチのポート数としている。そして、図９のグラフ７０３が実施例２の結線方法を用いた場合の近接接続スイッチの割合の変化を表している。また、三角の点で表される点が実施例３の結線方法を用いて実施例２の接続方法を修正した場合の近接接続スイッチの割合を表している。
【０１２５】
図８のグラフ７０２ように、従来の結線方法では、スイッチのポート数が増えても、近接接続スイッチの数の増加は小さく抑えられてしまっている。これに対して、グラフ７０１のように、実施例２の結線方法を用いることで、スイッチのポート数が増えるに従い、近接接続スイッチが大きく増えていることがわかる。また、従来の結線方法では、スイッチのポート数の増加に対する近接接続スイッチの数の増加の割合が低いため、近接接続スイッチの割合は減少していてしまう。これに対して、グラフ７０３のように、実施例２の結線方法を用いることで、いくつかのポート数においては、近接接続スイッチの割合を上げることができる。すなわち、実施例２の結線方法を用いることで、平均ホップ数を従来に比べて大きく低減することができる。
【０１２６】
さらに、図８の三角の点で表されるように、ポート数が素数のべき乗の場合、実施例３の結線方法を用いることで、近接接続スイッチの数を実施例２の場合よりも増やして最大にすることができる。また、図９の三角の点で表されるように、ポート数が素数のべき乗の場合、実施例３の結線方法を用いることで、近接接続スイッチの割合を理論上の上限値まで増やすことができる。
【実施例４】
【０１２７】
次に、実施例４に係るネットワーク管理装置について説明する。図１０は、実施例４に係るネットワーク管理装置のブロック図である。本実施例に係るネットワーク管理装置は、実施例１〜３のいずれかの方法を用いて１段目〜３段目のスイッチの結線を求め、求めた結線状態を操作者に提示する装置である。ここでは、実施例１の方法を用いて結線を求める場合について説明する。
【０１２８】
入力制御部８０１は、操作者からキーボードなどを用いて入力されたスイッチのポート数を受信する。例えば、６ポートスイッチを用いる場合、入力制御部８０１は、ポートするとして６を受信する。そして、入力制御部８０１は、受信したポート数をスイッチ配置部８０２へ出力する。
【０１２９】
スイッチ配置部８０２は、受信したポート数の半分の数を２乗することで、１段目〜３段目のスイッチそれぞれの数を求める。例えば、６ポートスイッチの場合、スイッチ配置部８０２は、１段目〜３段目のスイッチがそれぞれ９個ずつあるとする。そして、スイッチ配置部８０２は、１段目のスイッチを画面の一番下に横に並べて配置するよう表示制御部８０５へ通知する。次に、スイッチ配置部８０２は、２段目のスイッチを画面上の１段目のスイッチの上に横に並べて配置するよう表示制御部８０５へ通知する。さらに、スイッチ配置部８０２は、３段目のスイッチを画面上の２段目のスイッチの上に横に並べて配置するよう表示制御部８０５へ通知する。
【０１３０】
さらに、スイッチ配置部８０２は、画面に並べた１段目のスイッチに対して、画面に向かって左から順にＢ１、Ｂ２、・・・として番号をふっていく。また、スイッチ配置部８０２は、画面に並べた２段目のスイッチに対して、画面に向かって左から順にＭ１、Ｍ２、・・・として番号をふっていく。さらに、スイッチ配置部８０２は、画面に並べた３段目のスイッチに対して、画面に向かって左から順にＴ１、Ｔ２、・・・として番号をふっていく。
【０１３１】
そして、スイッチ配置部８０２は、スイッチのポート数及び各スイッチの番号を第１配線部８０３及び第２配線部８０４へ出力する。
【０１３２】
第１配線部８０３は、スイッチのポート数及びスイッチのポート数及び各スイッチの番号をスイッチ配置部８０２から受信する。
【０１３３】
そして、第１配線部８０３は、２段目のスイッチをポート数の半分の数で番号の小さい順にグループ化する。また、第１配線部８０３は、３段目のスイッチをポート数の半分の数で番号の小さい順にグループ化する。
【０１３４】
そして、第１配線部８０３は、２段目のスイッチの各グループに含まれるスイッチを、画面上で対応する上の位置にある３段目のスイッチのグループに含まれる全てのスイッチと接続する結線を求める。そして、第１配線部８０３は、求めた結線を表示制御部８０５へ出力する。
【０１３５】
第２配線部８０４は、スイッチのポート数及びスイッチのポート数及び各スイッチの番号をスイッチ配置部８０２から受信する。
【０１３６】
そして、第２配線部８０４は、実施例１の結線方法を用いて１段目のスイッチと２段目のスイッチとを接続する結線を求める。そして、第２配線部８０４は、求めた結線を表示制御部８０５へ出力する。
【０１３７】
表示制御部８０５は、スイッチ配置部８０２からの指示に従い、１段目〜３段目のスイッチを画面に表示させる。次に、表示制御部８０５は、第１配線部８０３から受信した結線に従い、２段目のスイッチと３段目のスイッチとの結線を画面に表示させる。次に、表示制御部８０５は、第２配線部８０４から受信した結線に従い、１段目のスイッチと２段目のスイッチとの結線を画面に表示させる。
【０１３８】
次に、図１１を参照して、１段目のスイッチと２段目のスイッチとの結線の決定の流れについて説明する。図１１は、１段目のスイッチと２段目のスイッチとの結線の決定のフローチャートである。ここでは、図１に示した６ポートスイッチを用いた３段の構成を例に説明する。加えて、以下の説明では各スイッチを示す場合、図１に示すスイッチの番号を付加した名前で説明する。すなわち、各スイッチをスイッチＢ１〜Ｂ９、Ｍ１〜Ｍ９、Ｔ１〜Ｔ９として表す。また、各ノードを、図１に示すノード番号を付加した名前で説明する。すなわち、各ノードをノード１〜２７として表す。
【０１３９】
スイッチ配置部８０２は、１段目のスイッチとしてスイッチＢ１〜Ｂ９を配置し、２段目のスイッチとしてスイッチＭ１〜Ｍ９を配置し、３段目のスイッチとしてスイッチＴ１〜Ｔ９を配置する（ステップＳ１）。
【０１４０】
次に、第１配線部８０３は、２段目のスイッチのポート数の半分の数で２段目及び３段目のスイッチを番号順にグループ化していく。そして、第１配線部８０３は、上下に対応する２段目のスイッチのグループのスイッチと３段目のスイッチのグループのスイッチとを全てが相互に接続するように配線する（ステップＳ２）。
【０１４１】
第２配線部８０４は、２段目のスイッチをスイッチ番号順に分け、３つの２段目グループｉ（ｉ＝１、２、３）とする（ステップＳ３）。ここで、２段目グループは、グループ１からグループ番号を増やしていき順にグループ番号３になると、次にグループ１に戻るものとする。すなわち、２段目グループ４は、２段目グループ１である。
【０１４２】
第２配線部８０４は、１段目のスイッチをスイッチ番号順に分け、３つの１段目グループｊ（ｊ＝１、２、３）とする（ステップＳ４）。ここで、１段目グループは、グループ１からグループ番号を増やしていき順にグループ番号３になると、次にグループ１に戻るものとする。すなわち、２段目グループ４は、２段目グループ１である。
【０１４３】
さらに、第２配線部８０４は、接続されているノードの最小のノード番号を９で割った余りが等しいものを同じグループとしていき１段目のスイッチをグループ分けする。すなわち、スイッチＢ１〜Ｂ９を、スイッチＢ１、Ｂ４、及びＢ７、スイッチＢ２、Ｂ５及びＢ８、並びにスイッチＢ３、Ｂ６及びＢ９の３グループに分ける。ここで、スイッチＢ１、Ｂ４、及びＢ７のグループをグループ１−１とする。また、スイッチＢ２、Ｂ５及びＢ８のグループをグループ１−２とする。また、スイッチＢ３、Ｂ６及びＢ９のグループをグループ１−３とする（ステップＳ５）。
【０１４４】
第２配線部８０４は、ｉ＝１とする（ステップＳ６）。
【０１４５】
第２配線部８０４は、２段目グループｉのスイッチ番号が最小である先頭のスイッチに対して、１段目グループ１からグループ１−１のスイッチを選択する（ステップＳ７）。
【０１４６】
次に、第２配線部８０４は、第２グループｉの先頭のスイッチに対して、１段目グループ１＋（ｉ−１）からグループ１−２のスイッチを選択する（ステップＳ８）。
【０１４７】
さらに、第２配線部８０４は、第２グループｉの先頭のスイッチに対して、１段目グループ１＋２（ｉ−１）からグループ１−３のスイッチを選択する（ステップＳ９）。
【０１４８】
第２配線部８０４は、ｉ＝３であるか否かを判定する（ステップＳ１０）。ｉ＝３でなければ（ステップＳ１０：否定）、第２配線部８０４は、ｉ＝ｉ＋１として（ステップＳ１１）、ステップＳ７に戻る。
【０１４９】
これに対して、ｉ＝３の場合（ステップＳ１０：肯定）、第２配線部８０４は、各２段目グループの先頭の隣のスイッチに対して、グループ１−１〜１−３のそれぞれの選択において先頭のスイッチに対して選択した１段目グループの隣のグループを抽出する。そして、第２配線部８０４は、先頭の隣のスイッチ対して、グループ１−１〜１−３の中の先頭のスイッチが選択した同じグループのスイッチを、その抽出した１段目グループから選択する（ステップＳ１２）。
【０１５０】
さらに、第２配線部８０４は、各２段目グループの先頭の２つ隣のスイッチに対して、グループ１−１〜１−３のそれぞれの選択において先頭のスイッチに対して選択した１段目グループの２つ隣のグループを抽出する。そして、第２配線部８０４は、先頭の２つ隣のスイッチ対して、グループ１−１〜１−３の中の先頭のスイッチが選択した同じグループのスイッチを、その抽出した１段目グループから選択する（ステップＳ１３）。
【０１５１】
ここで、本実施例では、実施例１の結線方法の場合について説明したが、実施例２及び実施例３の場合も同様である。
【０１５２】
以上に説明したように、本実施例に係るネットワーク管理装置は、平均ホップ数を抑え且つ信号伝送において広い帯域幅を確保できる結線状態を提示する。これにより、利用者は、平均ホップ数を抑え且つ信号伝送において広い帯域幅を確保できる結線状態を容易に知ることができ、適切なネットワーク構成を迅速に構築することができる。
【０１５３】
さらに、図１２を参照して、１段目のスイッチと２段目のスイッチとの結線の決定の他の例の流れについて説明する。図１２は、１段目のスイッチと２段目のスイッチとの結線の決定の他の例のフローチャートである。ここでも、図１に示した６ポートスイッチを用いた３段の構成を例に説明する。加えて、以下の説明では各スイッチを示す場合、図１に示すスイッチの番号を付加した名前で説明する。すなわち、各スイッチをスイッチＢ１〜Ｂ９、Ｍ１〜Ｍ９、Ｔ１〜Ｔ９として表す。また、各ノードを、図１に示すノード番号を付加した名前で説明する。すなわち、各ノードをノード１〜２７として表す。
【０１５４】
スイッチ配置部８０２は、１段目のスイッチとしてスイッチＢ１〜Ｂ９を配置し、２段目のスイッチとしてスイッチＭ１〜Ｍ９を配置し、３段目のスイッチとしてスイッチＴ１〜Ｔ９を配置する（ステップＳ２１）。
【０１５５】
次に、第１配線部８０３は、２段目のスイッチのポート数の半分の数で２段目及び３段目のスイッチを番号順にグループ化していく。そして、第１配線部８０３は、上下に対応する２段目のスイッチのグループのスイッチと３段目のスイッチのグループのスイッチとを全てが相互に接続するように配線する（ステップＳ２２）。
【０１５６】
次に、第２配線部８０４は、接続されているノードの最小のノード番号を９で割った余りが等しいものを同じグループとしていき１段目のスイッチをグループ分けする。すなわち、スイッチＢ１〜Ｂ９を、スイッチＢ１、Ｂ４、及びＢ７、スイッチＢ２、Ｂ５及びＢ８、並びにスイッチＢ３、Ｂ６及びＢ９の３グループに分ける。ここで、スイッチＢ１、Ｂ４、及びＢ７のグループをグループ１−１とする。また、スイッチＢ２、Ｂ５及びＢ８のグループをグループ１−２とする。また、スイッチＢ３、Ｂ６及びＢ９のグループをグループ１−３とする（ステップＳ２３）。
【０１５７】
さらに、第２配線部８０４は、ｊ＝０とする（ステップＳ２４）。
【０１５８】
また、第２配線部８０４は、ｉ＝１とする（ステップＳ２５）。
【０１５９】
第２配線部８０４は、スイッチＭ（３ｊ＋１）に接続する１段目スイッチをグループ（１−ｉ）から選ぶ（ステップＳ２６）。
【０１６０】
次に、第２配線部８０４は、スイッチＭ（３ｊ＋２）に接続する１段目スイッチをグループ（１−ｉ）の残りのスイッチから選ぶ（ステップＳ２７）。
【０１６１】
次に、第２配線部８０４は、スイッチＭ（３ｊ＋３）に接続する１段目スイッチをグループ（１−ｉ）の残りのスイッチから選ぶ（ステップＳ２８）。
【０１６２】
第２配線部８０４は、ｉ＝３か否かを判定する（ステップＳ２９）。ｉ＝３で無い場合（ステップＳ２９：否定）、第２配線部８０４は、ｉ＝ｉ＋１として（ステップＳ３０）、ステップＳ２６に戻る。
【０１６３】
これに対して、ｉ＝３の場合（ステップＳ２９：肯定）、第２配線部８０４は、３ｊ＋３＝２７か否かを判定する（ステップＳ３１）。３ｊ＋３＝２７でない場合（ステップＳ３１：否定）、第２配線部８０４は、ｊ＝ｊ＋１として（ステップＳ３２）、ステップＳ２５に戻る。
【０１６４】
これに対して、３ｊ＋３＝２７の場合（ステップＳ３１：肯定）、第２配線部８０４は、１段目スイッチに対する近接接続スイッチの平均が３より大きいか否かを判定する（ステップＳ３３）。近接接続スイッチの平均が３つ以下の場合（ステップＳ３３：否定）、第２配線部８０４は、ステップＳ２４に戻る。
【０１６５】
これに対して、近接接続スイッチの平均が３より大きい場合（ステップＳ３３：肯定）、第２配線部８０４は、１段目のスイッチと２段目のスイッチの配線をその接続状態で決定する。そして、表示制御部８０５は、スイッチ配置部８０２により配置された各スイッチを第１配線部８０３及び第２配線部８０４によって決定された配線により結線した状態を表示部に表示させる（ステップＳ３４）。
【０１６６】
ここで、以上では、近接接続スイッチの数が、少なくとも従来のＦａｔ  Ｔｒｅｅ構成よりも多くなる結線を求める場合で説明したが、これは他の方法でも良い。例えば、第２配線部８０２は、ステップＳ４〜ステップ９までの流れを全ての１段目のスイッチの組み合わせに対して行い、それぞれの場合の近接接続スイッチの平均を記憶しておき、平均値が最大となるものを配線として決定してもよい。
【符号の説明】
【０１６７】
Ｂ１〜Ｂ１６  スイッチ（１段目のスイッチ）
Ｍ１〜Ｍ１６  スイッチ（２段目のスイッチ）
Ｔ１〜Ｔ１６  スイッチ（３段目のスイッチ）
８０１  入力制御部
８０２  スイッチ配置部
８０３  第１配線部
８０４  第２配線部
８０５  表示制御部
【図１】
0005849486.tif 000002
【図２】
0005849486.tif 000003
【図３】
0005849486.tif 000004
【図４】
0005849486.tif 000005
【図５】
0005849486.tif 000006
【図６−１】
0005849486.tif 000007
【図６−２】
0005849486.tif 000008
【図７−１】
0005849486.tif 000009
【図７−２】
0005849486.tif 000010
【図８】
0005849486.tif 000011
【図９】
0005849486.tif 000012
【図１０】
0005849486.tif 000013
【図１１】
0005849486.tif 000014
【図１２】
0005849486.tif 000015
【図１３】
0005849486.tif 000016
【図１４】
0005849486.tif 000017