(57)【要約】【課題】計算処理のスループットを改善可能にした計算機システムを提供する。【解決手段】メッシュ状に接続された複数のルータ装置によって計算資源クラスタが相互接続され、ルータ装置間のデータパケットのホップ先を次元順ルーティングにより決定する計算機システムであって、データパケットのディスティネーションからソースに対する制御パケットが発生すると、複数のルータ装置は、制御パケットのホップ先を、データパケットの転送経路とは異なる経路の隣接する他のルータ装置に決定する構成である。【選択図】図１
2014241474.tif 000002
【特許請求の範囲】
【請求項１】
メッシュ状に接続された複数のルータ装置によって計算資源クラスタが相互接続され、ルータ装置間のデータパケットのホップ先を次元順ルーティングにより決定する計算機システムであって、
前記データパケットのディスティネーションからソースに対する制御パケットが発生すると、前記複数のルータ装置は、該制御パケットのホップ先を、前記データパケットの転送経路とは異なる経路の隣接する他のルータ装置に決定する、計算機システム。
【請求項２】
請求項１記載の計算機システムにおいて、
前記複数のルータ装置のそれぞれは、
前記制御パケットのソースとディスティネーションのＸ座標またはＹ座標のいずれか一方が等しく、かつ自装置が該制御パケットのソースのルータ装置である場合に、所定の条件にしたがって該制御パケットのホップ先を決定し、前記制御パケットのソースとディスティネーションのＸ座標およびＹ座標の両方が異なる場合および自装置が前記制御パケットのソースのルータ装置でない場合の少なくともいずれかの場合に、該制御パケットのホップ先を前記次元順ルーティングにより決定する、計算機システム。
【請求項３】
請求項２記載の計算機システムにおいて、
前記複数のルータ装置によるメッシュ構成のＸ座標の最大値をｎ＿ｘとし、Ｙ座標の最大値をｎ＿ｙとし、前記制御パケットのディスティネーションのＸ座標をＤ＿ｘ、Ｙ座標をＤ＿ｙとし、該制御パケットのソースのＸ座標をＳ＿ｘ、Ｙ座標をＳ＿ｙとすると、
前記所定の条件は、
「Ｄ＿ｙ＝Ｓ＿ｙかつＳ＿ｙ＞ｎ＿ｙ／２」からなる第１の条件と、
「Ｄ＿ｙ＝Ｓ＿ｙかつＳ＿ｙ≦ｎ＿ｙ／２」からなる第２の条件と、
「Ｄ＿ｘ＝Ｓ＿ｘかつＳ＿ｘ＞ｎ＿ｘ／２」からなる第３の条件と、
「Ｄ＿ｘ＝Ｓ＿ｘかつＳ＿ｘ≦ｎ＿ｘ／２」からなる第４の条件と、を有し、
前記制御パケットのソースのルータ装置は、前記制御パケットのホップ先として、
前記第１の条件を満たす場合、Ｙ軸の負の方向に隣接するルータ装置に決定し、
前記第２の条件を満たす場合、Ｙ軸の正の方向に隣接するルータ装置に決定し、
前記第３の条件を満たす場合、Ｘ軸の負の方向に隣接するルータ装置に決定し、
前記第４の条件を満たす場合、Ｘ軸の正の方向に隣接するルータ装置に決定する、計算機システム。
【請求項４】
メッシュ状に接続された複数のルータ装置によって計算資源クラスタが相互接続され、ルータ装置間のデータパケットのホップ先を次元順ルーティングにより決定する計算機システムにおける、前記複数のルータ装置のうちの１つのルータ装置であって、
自装置で発生または前記計算資源クラスタから入力されたパケットが前記データパケットのディスティネーションからソースに対する制御パケットであるか否かを判定する入力制御部と、
前記発生または入力されたパケットが前記制御パケットであると前記入力制御部が判定すると、該制御パケットのホップ先を、前記データパケットの転送経路とは異なる経路の隣接する他のルータ装置に決定する調停部と、
を有するルータ装置。
【請求項５】
メッシュ状に接続された複数のルータ装置によって計算資源クラスタが相互接続され、ルータ装置間のデータパケットのホップ先を次元順ルーティングにより決定する計算機システムによるパケット転送方法であって、
前記複数のルータ装置が前記データパケットを前記次元順ルーティングにしたがって転送し、
前記複数のルータ装置は、前記データパケットのディスティネーションからソースに対する制御パケットが発生すると、該制御パケットのホップ先を、前記データパケットの転送経路とは異なる経路の隣接する他のルータ装置に決定する、パケット転送方法。
【請求項６】
コンピュータを請求項４に記載のルータ装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機アーキテクチャにおける処理装置間のデータ転送技術に関する。
【背景技術】
【０００２】
バス型トポロジや、スイッチによるスター型トポロジを用いた小規模な計算資源クラスタが複数設けられ、それぞれの計算資源クラスタがルータによって相互接続された計算機システムとして、オンチップネットワークや大規模並列計算機などが知られている。このようなシステムのアーキテクチャにおいては、ハードウェア資源の制約や転送遅延の削減を目的としてカットスルーと静的ルーティングによるデータ転送が主流となっている。
【０００３】
オンチップネットワークにおけるパケットスイッチシステムの一例が非特許文献１に開示されている。非特許文献１には、パケット転送方法に関する従来方法の一例として、次元順ルーティングが開示されている。例えば、Ｘ−Ｙ次元順ルーティングでは、ルータによる転送網において、はじめにＸ軸方向に宛先（ディスティネーション）ルータとＸ座標が等しくなるまでパケットが転送された後、Ｙ軸方向にディスティネーションルータまでパケットが転送される。オンチップネットワークの改善方法に関する文献として、非特許文献２や特許文献１が知られている。これらの文献を見てわかるように、通信遅延を抑制するために、予測によるルーティング処理を行うものが多い。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１１−１３９４１３号公報
【非特許文献】
【０００５】
【非特許文献１】T. T. Ye, L. Benini, and G. De Micheli, "Packetization and routing analysis of on-chip multiprocessor networks," Journal of Systems Architecture, vol. 50, pp. 81-104, 2004.
【非特許文献２】吉永努、外２名、「２−Ｄトーラスネットワークにおける動的通信予測の効果」、ＳＡＣＳＩＳ０７論文集、先進的計算基盤システムシンポジウム、ｐｐ．２１９−２２６、（２００７年）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ルータ装置はワームホールルーティングやカットスルーを用いてパケットを順次転送しているが、これらの転送方法では経路上にパケットをストアするバッファが十分に用意されていない。そのため、エラー訂正機構の不備やバッファオーバーフロー、ルータ配下のスイッチやバスにおける衝突などの現象によってパケット落ちが発生することがある。
【０００７】
パケット落ちが発生すると、データパケットを受け取る側のルータによって、受信できなかったパケットの再送要求を通知するためのパケットが生成され、生成されたパケットはデータパケットのソースとディスティネーションを逆にして転送される。従来の静的ルーティング方式では、このような場合、再送要求を通知するためのパケットが、データパケットと同一経路を逆行することになる。
【０００８】
この現象を、Ｘ−Ｙ次元順ルーティングを２次元メッシュの転送網に適用した場合で、図６を参照して説明する。図６は従来方法の課題を説明するための図である。図６は複数のルータ装置がメッシュ状に配置された転送網の一構成例を示す。
【０００９】
図６では、ルータ装置２００のアドレスを示す座標として、図の左上を基準に左右方向をＸ軸方向とし、上下方向をＹ軸方向として定義している。そして、各ルータ装置にその座標を（ｘ，ｙ）で表している。
【００１０】
今、座標（１，１）のルータ装置２００が座標（４，１）のルータ装置２００に接続された計算資源クラスタ（不図示）宛にデータパケットを送信し、そのデータパケットに関連して発生したパケットを座標（４，１）のルータ装置２００が座標（１，１）のルータ装置２００宛に返信する場合を考える。以下では、データパケットに関連して発生したパケットを「制御パケット」と称する。
【００１１】
この場合、実線矢印で示すデータパケットは座標（１，１）のルータ装置２００から座標（４，１）のルータ装置２００に転送され、破線矢印で示す制御パケットはデータパケットと同一経路を逆行して座標（４，１）のルータ装置２００から座標（１，１）のルータ装置２００に転送される。
【００１２】
制御パケットがデータパケットと同一経路を逆行すると、同一経路にあるルータ装置のパケット転送処理の負荷が増大し、制御パケットの転送処理が遅れることになる。その結果、発生した制御パケットに対する適切な応答処理が完了するまでの時間が増大し、計算処理のスループットが低下してしまうという問題がある。
【００１３】
本発明は上述したような技術が有する問題点を解決するためになされたものであり、計算処理のスループットを改善可能にした計算機システム、ルータ装置、パケット転送方法、およびコンピュータに実行させるためのプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
上記目的を達成するための本発明の計算機システムは、メッシュ状に接続された複数のルータ装置によって計算資源クラスタが相互接続され、ルータ装置間のデータパケットのホップ先を次元順ルーティングにより決定する計算機システムであって、
前記データパケットのディスティネーションからソースに対する制御パケットが発生すると、前記複数のルータ装置は、該制御パケットのホップ先を、前記データパケットの転送経路とは異なる経路の隣接する他のルータ装置に決定する構成である。
【００１５】
また、本発明のルータ装置は、メッシュ状に接続された複数のルータ装置によって計算資源クラスタが相互接続され、ルータ装置間のデータパケットのホップ先を次元順ルーティングにより決定する計算機システムにおける、前記複数のルータ装置のうちの１つのルータ装置であって、
自装置で発生または前記計算資源クラスタから入力されたパケットが前記データパケットのディスティネーションからソースに対する制御パケットであるか否かを判定する入力制御部と、
前記発生または入力されたパケットが前記制御パケットであると前記入力制御部が判定すると、該制御パケットのホップ先を、前記データパケットの転送経路とは異なる経路の隣接する他のルータ装置に決定する調停部と、
を有する構成である。
【００１６】
また、本発明のパケット転送方法は、メッシュ状に接続された複数のルータ装置によって計算資源クラスタが相互接続され、ルータ装置間のデータパケットのホップ先を次元順ルーティングにより決定する計算機システムによるパケット転送方法であって、
前記複数のルータ装置が前記データパケットを前記次元順ルーティングにしたがって転送し、
前記複数のルータ装置は、前記データパケットのディスティネーションからソースに対する制御パケットが発生すると、該制御パケットのホップ先を、前記データパケットの転送経路とは異なる経路の隣接する他のルータ装置に決定するものである。
【００１７】
さらに、本発明のプログラムは、コンピュータを上記本発明のルータ装置として機能させるためのものである。
【発明の効果】
【００１８】
本発明によれば、制御パケットがデータパケットと同じ経路を逆行することを防ぐことができ、制御パケットの転送遅れによる動作効率の低下を防ぎ、計算処理のスループットを改善することが可能となる。
【図面の簡単な説明】
【００１９】
【図１】本実施形態の計算機システムの一構成例を示すブロック図である。
【図２】図１に示したルータ装置の一構成例を示すブロック図である。
【図３】図２に示したルータ装置の動作手順を示すフローチャートである。
【図４】本実施形態のパケット転送方法の具体例を説明するための図である。
【図５】パケット転送方法について従来方法と本実施形態の違いを示す表である。
【図６】従来方法の課題を説明するための図である。
【発明を実施するための形態】
【００２０】
本実施形態の計算機システムは、ルータによる転送網において、パケットの種類によってその転送経路が異なるように転送制御することを特徴とする。
【００２１】
本実施形態の計算機システムの構成を説明する。図１は本実施形態の計算機システムの一構成例を示すブロック図である。
【００２２】
図１に示すように、計算機システムは、複数のＰＥ（Processing Element）によってバス型トポロジが構成される計算資源クラスタと、複数のＰＥおよびスイッチ３０によってスター型トポロジが構成される計算資源クラスタと、複数のルータ装置１０がメッシュ状に配置された転送網（以下では、ネットワークと称する）と、計算資源クラスタとネットワーク間のパケット転送を中継するネットワークインタフェース（Network Interface：ＮＩＦ）２１、２２とを有する。図１に示すように、複数の計算資源クラスタがネットワークを介して相互接続されている。本実施形態では、ＩＰ（Internet Protocol）に基づいてパケットが装置間で送受信される。
【００２３】
ＮＩＦ ２１に接続される計算資源クラスタのバスにはアービタ（調停）装置４０が接続されている。また、ＮＩＦ ２２に接続されるスイッチ３０には、バス型トポロジを構成するＰＥ群が２つ接続されている。一方のＰＥ群をグループＡとし、他方のＰＥ群をグループＢとすると、グループＡとグループＢのそれぞれにアービタ装置４０が接続されている。
【００２４】
ＮＩＦ ２１、２２は、データのパケット化やエラーチェックを行う。各アービタ装置４０は、複数のＰＥが接続されているバスの調停を行い、複数のＰＥのうち、どのタイミングでどのＰＥに通信処理をさせるかを決定する。スイッチ３０は、データの経路選択を行うが、ルータ装置ほどの高度な経路制御を行わず、例えば、ＮＩＦ ２２から受け取るパケットの転送先をグループＡまたはグループＢにスイッチする等の単純な経路制御を行う。
【００２５】
図１には、データ転送経路の一例として、計算資源クラスタ内の１つのＰＥから送出されたパケットが、ＮＩＦ ２１、ネットワーク、ＮＩＦ ２２およびスイッチ３０を経由して、グループＡ内の１つのＰＥに至る経路を破線矢印で示す。
【００２６】
次に、本実施形態のルータ装置１０の構成を説明する。図２は図１に示したルータ装置の一構成例を示すブロック図である。
【００２７】
図２に示すように、ルータ装置１０は、入力制御部１２−１〜１２−ｍ（ｍは２以上の整数）と、出力部１３−１〜１３−ｍと、クロスバスイッチ１４と、調停部１５とを有する。
【００２８】
入力制御部１２−１〜１２−ｍは、ルーティング対象のパケットの種類を判別するためのプロトコル情報ならびにルーティング対象のパケットのソースアドレスおよびディスティネーションアドレスの情報を格納するためのメモリ（不図示）と、受信するパケットを一時的に保存するバッファ（不図示）とを有する。
【００２９】
入力制御部１２−１〜１２−ｍは、ルーティング対象のパケットのヘッダからソースアドレスおよびディスティネーションアドレスと、プロトコル番号を含むヘッダ情報を取得してメモリ（不図示）に格納する。また、入力制御部１２−１〜１２−ｍは、ルーティング対象のパケットの種類が制御パケットであるか否かをヘッダ情報から判定し、その結果を調停部１５に通知する。制御パケットは、例えば、肯定応答（acknowledgement：Ａｃｋ）である。パケットの種類を判定するための情報はプロトコル番号に限らないが、プロトコル番号が「１」である場合、入力制御部１２−１〜１２−ｍは、パケットがＩＣＭＰ（Internet Control Message Protocol）の種類であると認識できる。
【００３０】
なお、パケットを一時的に保存するバッファは、入力制御部１２−１〜１２−ｍに限らず、出力部１３−１〜１３−ｍに設けられていてもよい。制御パケットは、ルータ装置１０に接続される計算資源クラスタで発生する場合に限らず、ルータ装置１０自身が生成する場合もある。
【００３１】
調停部１５は、ネットワーク内における自ルータのアドレスを示す座標であるアドレス座標の情報と、ネットワークを構成する複数のルータ装置によるメッシュ構成の大きさを示す（ｎ＿ｘ，ｎ＿ｙ）の情報とが予め格納されたメモリ（不図示）を有する。ｎ＿ｘ、ｎ＿ｙはメッシュ構成のＸ座標、Ｙ座標の最大値を表し、本実施形態では、図１に示すように、ｎ＿ｘ＝４、ｎ＿ｙ＝３である。図１に示すメッシュ構成では、直鎖状のルータ装置１０の列がＸ軸方向に４列設けられ、Ｙ軸方向に３列設けられている。
【００３２】
調停部１５は、入力制御部１２−ｋ（ｋは１〜ｍの任意の整数）から判定結果を受け取り、受信したパケットの種類が制御パケットである旨の判定結果である場合、入力制御部１２−ｋがパケットのヘッダから取得した情報を参照する。そして、調停部１５は、自ルータのアドレス座標が制御パケットのソースの座標（データパケットのディスティネーションの座標に相当）と一致するか否かを判定する。判定の結果、自ルータのアドレス座標が制御パケットのソースの座標と一致する場合、調停部１５は、以下の条件１〜条件４にしたがってホップ先を決定し、自ルータのアドレス座標が制御パケットのソースの座標と一致しない場合、次元順ルーティングによりホップ先を決定する。
【００３３】
次元順ルーティングは、Ｘ→Ｙ順に限らず、元の軸上に戻らないように、ルーティングがＹ軸方向から始まった場合には、Ｙ→Ｘ順でルーティングを行うものである。
【００３４】
条件１〜４を説明する。ただし、各条件に示す「Ｄ＿  」は制御パケットのディスティネーションの座標を表し、「Ｓ＿  」は制御パケットのソースの座標を表す。例えば、Ｄ＿ｙは制御パケットのディスティネーションのＹ座標を意味する。
【００３５】
条件１：「Ｄ＿ｙ＝Ｓ＿ｙかつＳ＿ｙ＞ｎ＿ｙ／２」を満たすとき、調停部１５は、ホップ先を、自ルータのアドレス座標からＹ軸方向に「−１」を付加した座標のルータ装置にスイッチングする。つまり、Ｙ軸の負の方向に隣接するルータ装置がホップ先となる。
条件２：「Ｄ＿ｙ＝Ｓ＿ｙかつＳ＿ｙ≦ｎ＿ｙ／２」を満たすとき、調停部１５は、ホップ先を、自ルータのアドレス座標からＹ軸方向に「＋１」を付加した座標のルータ装置にスイッチングする。つまり、Ｙ軸の正の方向に隣接するルータ装置がホップ先となる。
条件３：「Ｄ＿ｘ＝Ｓ＿ｘかつＳ＿ｘ＞ｎ＿ｘ／２」を満たすとき、調停部１５は、ホップ先を、自ルータのアドレス座標からＸ軸方向に「−１」付加した座標のルータ装置にスイッチングする。つまり、Ｘ軸の負の方向に隣接するルータ装置がホップ先となる。
条件４：「Ｄ＿ｘ＝Ｓ＿ｘかつＳ＿ｘ≦ｎ＿ｘ／２」を満たすとき、調停部１５は、ホップ先を、自ルータのアドレス座標からＸ軸方向に「＋１」付加した座標のルータ装置にスイッチングする。つまり、Ｘ軸の正の方向に隣接するルータ装置がホップ先となる。
【００３６】
なお、条件１〜４のいずれにも該当しない条件５：「Ｄ＿ｘ≠Ｓ＿ｘかつＤ＿ｙ≠Ｓ＿ｙ」に該当するとき、調停部１５は、ホップ先を次元順ルーティングにしたがって決定する。条件５に該当する場合、従来方法の次元順ルーティングで処理しても、制御パケットがデータパケットと同一の経路を逆行することはない。
【００３７】
このようにして、調停部１５は、条件１〜４に当てはまるか否かにしたがって、各条件に対応してスイッチングをクロスバスイッチ１４および出力部１３−１〜１３−ｍに指示する。
【００３８】
また、調停部１５は、受信したパケットの種類が制御パケットでない旨の判定結果を入力制御部１２−ｋから受け取った場合、対象のパケットのホップ先を、次元順ルーティングにしたがってクロスバスイッチ１４および出力部１３−１〜１３−ｍに指示する。
【００３９】
本実施形態では、ネットワーク内の初回のホップで、データパケットの転送経路と異なるように制御パケットの転送経路の列をずらすためのターンを行うと、初回のホップ以降ではデータパケットの転送経路と重ならないように、Ｙ軸方向に制御パケットの転送を開始すればＹ→Ｘ順でルーティングを行い、Ｘ軸方向に制御パケットの転送を開始すればＸ→Ｙ順でルーティングを行う。
【００４０】
次に、本実施形態のルータ装置１０の動作を説明する。図３は図２に示したルータ装置の動作手順を示すフローチャートである。
【００４１】
計算資源クラスタからパケットがルータ装置１０の入力制御部１２−ｋに入力されると、入力制御部１２−ｋは、パケットのヘッダからソースおよびディスティネーションのそれぞれのアドレスを取得し（ステップ１０１）、これらの情報をメモリ（不図示）に格納する。続いて、入力制御部１２−ｋは、パケットのヘッダ情報からパケットの種類を調べ（ステップ１０２）、パケットの種類がＡｃｋや衝突検知などの制御パケットであるか否かを判定する（ステップ１０３）。そして、入力制御部１２−ｋは、ステップ１０３の判定結果を調停部１５に通知する。
【００４２】
調停部１５は、入力制御部１２−ｋから判定結果を受け取り、判定結果がパケットの種類が制御パケットであることを示していると、入力制御部１２−ｋが保持している情報を参照し、自ルータのアドレス座標が制御パケットのソースの座標と一致するか否かを判定することで、自ルータが制御パケットの初回ホップを処理するルータであるか否かを判定する（ステップ１０４）。
【００４３】
ステップ１０４で自ルータが制御パケットの初回ホップを処理するルータである場合、調停部１５は、条件１を満たすか否かを判定し（ステップ１０５）、条件１を満たす場合、Ｙ軸の負の方向に隣接するルータ装置をホップ先に決定する（ステップ１０６）。ステップ１０５の判定で条件１を満たさない場合、調停部１５は、ステップ１０７の処理に進む。
【００４４】
ステップ１０７において、調停部１５は、条件２を満たすか否かを判定し、条件２を満たす場合、Ｙ軸の正の方向に隣接するルータ装置をホップ先に決定する（ステップ１０８）。ステップ１０７の判定で条件２を満たさない場合、調停部１５は、ステップ１０９の処理に進む。
【００４５】
ステップ１０９において、調停部１５は、条件３を満たすか否かを判定し、条件３を満たす場合、Ｘ軸の負の方向に隣接するルータ装置をホップ先に決定する（ステップ１１０）。ステップ１０９の判定で条件３を満たさない場合、調停部１５は、ステップ１１１の処理に進む。
【００４６】
ステップ１１１において、調停部１５は、条件４を満たすか否かを判定し、条件４を満たす場合、Ｘ軸の正の方向に隣接するルータ装置をホップ先に決定する（ステップ１１２）。ステップ１１１の判定で条件４を満たさない場合、条件１〜４のいずれも満たさないため、調停部１５は、従来方法と同様に、次元順ルーティングを適用して、ホップ先を決定する（ステップ１１３）。
【００４７】
一方、ステップ１０３の判定結果がパケットの種類が制御パケットでないことを示している場合、また、ステップ１０４の判定の結果、自ルータが制御パケットの初回ホップを処理するルータでない場合、調停部１５は、ステップ１１３の処理に進む。
【００４８】
なお、ステップ１０５、１０７、１０９および１１１の判定処理は図３に示す順番に限定されず、いずれの判定処理が先であってもよい。
【００４９】
従来方法では、制御パケットのディスティネーションとなる座標（データパケットのソース（送信元）となるルータの座標）に対してＸ→Ｙの順で次元順にルーティングされる。本実施形態では、制御パケットが発生すると、ネットワーク内の初回のホップで、データパケットの転送経路と重ならないように制御パケットの転送経路が隣接する列にずらされ、初回のホップ以降は次元順ルーティングによって処理される。
【００５０】
これにより、単一のデータ送信におけるデータパケットと制御パケットの経路を分断することができ、データフローが自身のデータパケットによって制御への応答時間が増大することを防ぐことができる。
【００５１】
また、迂回経路を隣接した列にとることによって、動的ルーティングによる迂回などで発生し得る、ホップ数のいたずらな増大を防ぐことができる。
【００５２】
次に、本実施形態のパケット転送方法の具体例を説明する。
【００５３】
図４は本実施形態のパケット転送方法の具体例を説明するための図である。図３および図４を参照して、図６に示した従来方法と対比して説明する。
【００５４】
ここでは、図６と同様に、ルータ装置１０の配置を示す座標として、図の左上を基準に左右方向をＸ軸方向とし、上下方向をＹ軸方向として定義している。そして、各ルータ装置の座標を（ｘ，ｙ）で表している。
【００５５】
座標（１，１）のルータ装置１０が座標（４，１）のルータ装置１０宛にデータパケットを送信し、そのデータパケットに関連する制御パケットを座標（４，１）のルータ装置１０が座標（１，１）のルータ装置１０宛に返信する場合を考える。ここでは、図３に示したフローチャートにおける、入力制御部１２−ｋの処理の説明を省略し、調停部１５による処理を説明する。
【００５６】
座標（４，１）のルータ装置１０は、図３に示すステップ１０４の判定によりステップ１０５に進み、条件１を満たすか否かを判定する。ここでは、条件１：「Ｄ＿ｙ＝Ｓ＿ｙかつＳ＿ｙ＞１．５」に対して、Ｄ＿ｙ＝Ｓ＿ｙ＝１であるが、Ｓ＿ｙ＜１．５なので、条件１を満たさない。
【００５７】
座標（４，１）のルータ装置１０は、条件１を満たさないと判定すると、ステップ１０７に進み、条件２を満たすか否かを判定する。ここでは、条件２：「Ｄ＿ｙ＝Ｓ＿ｙかつＳ＿ｙ≦１．５」に対して、Ｄ＿ｙ＝Ｓ＿ｙ＝１、Ｓ＿ｙ＜１．５なので、条件２を満たす。
【００５８】
ステップ１０７の判定の結果、座標（４，１）のルータ装置１０は、条件２を満たすと判定すると、制御パケットのホップ先を、自ルータの座標（４，１）に対してＹ軸方向に「＋１」を付加した座標（４，２）のルータ装置１０にスイッチングする。つまり、座標（４，１）のルータ装置１０は、Ｙ軸の正の方向に隣接するルータ装置１０に制御パケットを転送する。これにより、制御パケットの転送経路がデータパケットの転送経路の隣の列にずれる。座標（４，２）のルータ装置１０は、自ルータが制御パケットの初回ホップを処理するルータではないので、座標（４，１）のルータ装置１０から受け取った制御パケットを次元順ルーティングにしたがって転送する。ここでは、Ｘ−Ｙ次元順ルーティングとなる。それ以降の座標（３，２）、（２，２）、（１，２）のそれぞれのルータ装置１０も制御パケットを次元順ルーティングにしたがって転送する。
【００５９】
データパケットは、図４の実線矢印に示すように、座標（１，１）のルータ装置１０から座標（２，１）、（３，１）、（３，１）のルータ装置１０を経由して、座標（４，１）のルータ装置１０に転送される。一方、制御パケットは、図４の破線矢印に示すように、座標（４，１）のルータ装置１０から座標（４，２）、（３，２）、（２，２）、（１，２）のそれぞれのルータ装置１０を経由して、座標（１，１）のルータ装置１０に転送される。従来方法では、図６に示したように、制御パケットはデータパケットと同一経路を逆行していたが、本実施形態では、図４に示すように、制御パケットはデータパケットとは異なる経路で転送されることがわかる。
【００６０】
図５はパケット転送方法について従来方法と本実施形態の違いを示す表である。図５に示す表では、データパケットの経路を実線矢印で示し、制御パケットの経路を破線矢印で示している。
【００６１】
図５を参照すると、従来方法では、条件１〜４のいずれの場合も、データパケットと制御パケットが同一経路で互いに逆方向に転送されることがわかる。これに対し、本実施形態のパケット転送方法では、条件１〜４のいずれの場合も、制御パケットの経路がデータパケットの経路とは異なる迂回経路になっている。初回ホップ以降の次元順ルーティングについて、条件１および２ではＸ−Ｙ次元順ルーティングが適用され、条件３および４ではＹ−Ｘ次元順ルーティングが適用されている。
【００６２】
本実施形態によれば、次元順ルーティングにおいて、ソースとディスティネーションが逆転するようなパケットが発生した場合（制御・フィードバックループ系など）に、そのパケットがデータパケットの転送経路とは異なる経路で転送される。そのため、例えば、データパケットに関連して制御パケットが発生した際、制御パケットがデータパケットの転送経路と同一経路をたどって逆行することを防げる。そして、経路分散を図ることで、ルータ装置のパケット転送処理の負荷が分散され、制御パケットの転送遅れによる動作効率の低下を防ぎ、計算処理のスループットを改善することが可能となる。
【００６３】
本発明は、特定のルータまたはその配下の計算資源クラスタにおいて、データパケットのソースに対する制御パケットが発生した際に有効である。
【００６４】
なお、本実施形態では、図２を参照して、パケットの種類の特定を入力制御部が行い、制御パケットのホップ先の決定を調停部が行う場合で説明したが、ルータ装置にＣＰＵ（Central Processing Unit）（不図示）とプログラムを記憶するメモリ（不図示）とが予め設けられ、ＣＰＵがプログラムにしたがって処理を実行することで、入力制御部および調停部の情報処理が行われるようにしてもよい。
【００６５】
また、本発明のルータ装置はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。
【００６６】
さらに、本発明のパケット転送方法を、バス構造と複数のルータを含む転送網との組み合わせによる階層型データ処理アーキテクチャに適用することが可能である。
【符号の説明】
【００６７】
１０    ルータ装置
１２−１〜１２−ｍ    入力制御部
１３−１〜１３−ｍ    出力部
１４    クロスバスイッチ
１５    調停部
【図１】
2014241474.tif 000003
【図２】
2014241474.tif 000004
【図３】
2014241474.tif 000005
【図４】
2014241474.tif 000006
【図５】
2014241474.tif 000007
【図６】
2014241474.tif 000008