(57)【要約】【課題】スケーラビリティが高く、性能の不均一性が少なく、かつ、耐障害性が高いストレージシステムのアーキテクチャ及びその制御方法を提供する。【解決手段】ホスト計算機に接続されるストレージシステムにおいて、前記ストレージシステムは、四つ以上のノードを備え、前記各ノードは、前記ホスト計算機に接続され、前記ホスト計算機と通信するホストインターフェース部と、前記ホストインターフェース部と通信するスイッチと、を備え、前記スイッチは、さらに、他の四つ以内の前記ノード内の前記スイッチと接続され、前記他のノード内のスイッチと通信することによって、前記ノードは二次元の格子状に接続される。【選択図】      図１
2006243967.tif 000002
【特許請求の範囲】
【請求項１】
ホスト計算機に接続されるストレージシステムにおいて、
前記ストレージシステムは、複数のノードと、前記ノードに接続された複数のディスクドライブと、を備え、
前記各ノードは、
前記ホスト計算機に接続され、前記ホスト計算機と通信するホストインターフェース部と、
前記ディスクドライブに接続され、前記ディスクドライブにアクセスするドライブインターフェース部と、
前記ホストインターフェース部及び前記ドライブインターフェース部と通信するスイッチと、を備え、
前記スイッチが他の四つ以内の前記ノード内の前記スイッチと接続されることによって前記各ノードが二次元の格子状に接続され、
前記各ディスクドライブは、異なる前記ノードに備わる二つの前記ドライブインターフェース部に接続され、
前記ノードは、
二次元のアドレスを有し、
少なくとも、行き先の前記ノードの前記アドレス、迂回マーク、逆探索マーク及び探索カウントを含むパケットを他の前記ノードとの間で送受信し、
前記パケットを受信すると、自ノードの前記アドレスと、前記受信したパケットに含まれる前記行き先のノードのアドレスとを比較し、
前記自ノードのアドレスと前記行き先のノードのアドレスとが一致しない場合、前記自ノードから前記行き先のノードまでの間の最短経路上にあり、かつ、前記自ノードに隣接するノードを決定し、
前記最短経路上にあり、かつ、前記自ノードに隣接するノードが二つ決定された場合、当該決定された二つのノードの通信量を比較し、
当該決定された二つのノードのうち、前記通信量が小さい一方の前記ノードに前記パケットを送信し、
当該送信に失敗した場合、当該決定された二つのノードのうち、他方の前記ノードに前記パケットを送信し、
前記最短経路上にあり、かつ、前記自ノードに隣接するノードが一つのみ決定された場合、当該決定されたノードに前記パケットを送信し、
当該送信に失敗した場合、前記行き先のノードが前記自ノードに隣接するか否かを判定し、
前記行き先のノードが前記自ノードに隣接しないと判定された場合、前記迂回マークを有効にすると共に、前記自ノードから前記行き先のノードまでの間の２番目に短い経路上にあり、かつ、前記自ノードに隣接する二つのノードを決定し、
前記決定された２番目に短い経路上にあり、かつ、前記自ノードに隣接するノードの通信量を測定し、
前記通信量が小さい一方の前記２番目に短い経路上にあり、かつ、前記自ノードに隣接するノードに前記パケットを送信し、
当該送信に失敗した場合、他方の前記２番目に短い経路上にあり、かつ、前記自ノードに隣接するノードに前記パケットを送信し、
前記迂回マークが有効にされた前記パケットを受信した前記ノードは、当該パケットを送信したノードに当該パケットを送信せず、
前記行き先のノードが前記自ノードに隣接すると判定された場合であって、前記逆探索マークが無効である場合、前記探索カウントを１増加すると共に、当該パケットを所定の第１方向の前記ノードに送信し、
当該送信に失敗した場合、前記逆探索マークを有効とし、前記探索カウントを１に設定し、当該パケットを所定の第２方向の前記ノードに送信し、
前記行き先のノードが前記自ノードに隣接すると判定された場合であって、前記逆探索マークが有効である場合、前記探索カウントを１増加すると共に、当該パケットを所定の第２方向の前記ノードに送信し、
前記逆探索マークが有効であるときに前記パケットの送信に失敗した場合、及び、前記探索カウントが８を超えた場合、障害を報告することを特徴とするストレージシステム。
【請求項２】
ホスト計算機に接続されるストレージシステムにおいて、
前記ストレージシステムは、四つ以上のノードを備え、
前記それぞれのノードは、
前記ホスト計算機に接続され、前記ホスト計算機と通信するホストインターフェース部と、
前記ホストインターフェース部と通信するスイッチと、を備え、
前記スイッチは、前記他の四つ以内のノードが備える前記スイッチと互いに接続されることによって、前記それぞれのノードは二次元の格子状に接続されることを特徴とするストレージシステム。
【請求項３】
前記ストレージシステムは、第１のスイッチを備える第１のノードと、第２のスイッチを備える第２のノードと、第３のスイッチを備える第３のノードと、第４のスイッチを備える第４のノードを備え、
前記第１のスイッチは、前記第２のスイッチ及び前記第３のスイッチに接続され、
前記第２のスイッチは、前記第１のスイッチ及び前記第４のスイッチに接続され、
前記第３のスイッチは、前記第１のスイッチ及び前記第４のスイッチに接続され、
前記第４のスイッチは、前記第２のスイッチ及び前記第３のスイッチに接続されることによって、
前記第１乃至第４のノードは二次元の格子状に接続されることを特徴とする請求項２に記載のストレージシステム。
【請求項４】
前記ストレージシステムは、ディスクドライブを備え、
少なくとも一つの前記ノードは、ドライブインターフェース部を備え、
前記ドライブインターフェース部は、前記ディスクドライブに接続され、前記ディスクドライブ及び前記それぞれのノードのぞれぞれのスイッチと通信することを特徴とする請求項２に記載のストレージシステム。
【請求項５】
前記ディスクドライブが、前記ノードのうちの異なる２個のノードに備わる各々の前記ドライブインターフェース部に接続されることを特徴とする請求項４に記載のストレージシステム。
【請求項６】
前記ストレージシステムは、ディスクドライブを備え、
前記それぞれのノードは、
第１のスイッチと、第２のスイッチと、
前記ディスクドライブに接続され、前記ディスクドライブと通信するドライブインターフェース部と、を備え、
前記第１及び第２のスイッチは、前記それぞれのノードのそれぞれの前記ホストインターフェース部及び前記ドライブインターフェース部と通信し、前記それぞれのノードは前記それぞれの第１のスイッチどうし及びそれぞれの第２のスイッチどうしを接続することによって二次元の格子状の第１の接続と第２の接続を備えることを特徴とする請求項２に記載のストレージシステム。
【請求項７】
前記ストレージシステムにおいて、更に、前記第１のスイッチと前記第４のスイッチとが接続され、前記第２のスイッチと前記第３のスイッチとが接続されることを特徴とする請求項３に記載のストレージシステム。
【請求項８】
少なくともホスト計算機又はディスクドライブに接続される四つ以上のノードを備え、
前記それぞれのノードは、他の四つ以内の前記ノードと隣接して接続されることによって二次元の格子状に接続され、二次元のアドレスを有するストレージシステムにおける、前記それぞれのノードがアクセス要求又は応答のパケットを伝送する方法であって、
前記四つ以上のノードのうちの第１のノードが前記パケットを受信する手順と、
前記第１のノードの前記アドレスを取得する手順と、
前記取得したアドレスと、受信したアクセス要求又は応答の行き先である第２のノードの前記アドレスとを比較する手順と、
前記第１のノードのアドレスと、前記第２のノードのアドレスとが一致しない場合、前記第１のノードから前記第２のノードへの最短経路上にあり、かつ、前記第１のノードに隣接する第３のノードを決定する手順と、
前記第３のノードに前記パケットを送信する手順と、を含むことを特徴とする方法。
【請求項９】
前記第２のノードへの最短経路が二つ存在する場合、
当該二つの最短経路上にあり、かつ、前記第１のノードに隣接するそれぞれ第３と第４のノードを決定する手順と、
前記第１のノードから前記第３及び第４の二つの隣接ノードへの通信量を比較する手順と、
前記比較結果に基づいて、前記第３及び第４の二つの隣接ノードのうち前記通信量が小さい一方の隣接ノードに前記パケットを送信する手順と、をさらに含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記通信量が小さい一方の前記最短経路上の第３または第４の隣接ノードに前記パケットを送信する手順において、当該送信に失敗した場合、残りの他方の前記最短経路の第３または第４のノードに前記パケットを送信する手順をさらに含むことを特徴とする請求項９に記載の方法。
【請求項１１】
前記第２のノードへの最短経路が一つのみ存在し、かつ、前記第３のノードに前記パケットを送信する手順において、当該送信に失敗した場合、
前記第２のノードが前記第１のノードに隣接するか否かを判定する手順と、
前記第２のノードが前記第１のノードに隣接しないと判定された場合、前記最短経路の次に短い二つの経路上にあり、かつ、前記第１ノードに隣接するそれぞれ第４と第５のノードを決定する手順と、
前記第１のノードから前記第４及び第５の二つの隣接ノードへの通信量を比較する手順と、
前記比較結果に基づいて、前記第４及び第５の二つの隣接ノードのうち前記通信量が小さい一方の隣接ノードに前記パケットを送信する手順と、
当該送信に失敗した場合、前記第４及び第５の隣接ノードのうち残りの他方の隣接ノードに前記パケットを送信する手順と、をさらに含むことを特徴とする請求項８に記載の方法。
【請求項１２】
前記第２のノードが前記第１のノードに隣接しないと判定された場合、前記パケットに含まれる第１の情報を有効とする手順と、
前記第１のノードに隣接する第４または第５のノードにおいて、前記第１のノードから送信された前記パケットの前記第１の情報が有効である場合、当該パケットを送信した前記第１のノードを含む経路以外の経路を通して当該パケットをさらに送信する手順と、をさらに含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記第２のノードへの前記最短経路が一つのみ存在し、かつ、前記第３のノードに前記パケットを送信する手順において、当該送信に失敗した場合、
前記第２のノードが前記第１のノードに隣接するか否かを判定する手順と、
前記第２のノードが前記第１のノードに隣接すると判定され、かつ、前記パケットに含まれる第２の情報が無効である場合、当該パケットの送信経路を所定の第１方向に探索し、当該パケットを当該探索された経路に送信する手順と、
当該探索に失敗した場合、前記第２の情報を有効とする手順と、
前記第２のノードが前記第１のノードに隣接すると判定され、かつ、前記第２の情報が有効である場合、当該パケットの送信経路を前記第１方向と異なる方向に探索し、当該パケットを当該探索された経路に送信する手順と、をさらに含むことを特徴とする請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージシステムのスケーラビリティ及び耐障害性の向上に関する。
【背景技術】
【０００２】
現在のデータストレージ市場では、多数のホスト計算機が接続される非常に大規模なストレージシステムが要求される。このように大規模なストレージシステムは、例えば、大企業のデータセンター等で用いられるため、高い性能及び信頼性が要求される。
【０００３】
一方、オープン市場の拡大等によって、大規模なストレージシステムと同等の性能及び信頼性を備える小規模なストレージシステムへの要求も高まっている。
【０００４】
これらの要求に応えるためには、小規模な構成から非常に大規模な構成までを共通のアーキテクチャによってサポートする、スケーラビリティの高いストレージシステムを実現することが望ましい。このため、ホスト計算機への接続を制御する任意の数のホスト接続制御部、及び、ディスクドライブへのデータアクセスを制御する任意の数のドライブ制御部を結合することによって、任意の規模のストレージシステムを実現する各種の構成が提案されている。
【０００５】
集中スイッチ結合は、複数のホスト接続制御部及び複数のドライブ制御部が、一つのスイッチを介して結合された構成である（例えば、特許文献１参照）。
【０００６】
クラスタスイッチ結合は、複数のクラスタが結合された構成である。ここで、クラスタとは、複数のホスト接続制御部及び複数のドライブ制御部が一つのスイッチを介して結合されたものである（例えば、特許文献２参照）。
【０００７】
分散スイッチ結合は、複数のホスト接続制御部及び複数のドライブ制御部が、各制御部に設けられたスイッチを介して結合された構成である（例えば、非特許文献１参照）。
【特許文献１】特開２０００−９９２８１号公報
【特許文献２】特開２００３−９９２０６号公報
【非特許文献１】“EMC Symmetrix DMXシリーズ”、［ｏｎｌｉｎｅ］、ＥＭＣジャパン株式会社ホームページ、製品、［平成１７年１月７日検索］、インターネット＜ＵＲＬ：http://japan.emc.com/products/systems/symmetrix/DMX_series/pdf/DMX_series_ds.pdf＞
【発明の開示】
【発明が解決しようとする課題】
【０００８】
集中スイッチ結合によれば、構成されるストレージシステムの規模は、スイッチの規模によって制限される。すなわち、大規模なストレージシステムを構成するためには、大規模なスイッチを用いる必要がある。この大規模なスイッチを、小規模なストレージシステムにも使用すれば、小規模なストレージシステムのコストが上昇する。
【０００９】
クラスタスイッチ結合は、集中スイッチ結合において、大規模なスイッチがコストを上昇させる問題を緩和するものである。すなわち、大規模でないスイッチを用いたクラスタが構成され、さらに大規模なスイッチを要するような大規模なシステムは、複数のクラスタどうしを接続することによって実現される。しかし、スイッチのコストの上昇を抑える目的のため、クラスタ間のデータ伝送能力は制限せざるを得ない。このため、データがクラスタを跨って伝送される場合、データがクラスタ内で伝送される場合と比較して、性能が大きく低下する。このように、クラスタスイッチ結合では、データの伝送経路による性能の不均一性が存在する。
【００１０】
分散スイッチ結合によれば、大規模なストレージシステムを構成する場合、スイッチ間の接続が極めて多く複雑になり、配線のコストが増大し、スイッチも大規模になる。
【００１１】
本発明は上記の課題に鑑みてなされたものであり、小規模な構成から非常に大規模な構成まで任意の規模のストレージシステムを、規模に応じた妥当なコストで構成することができ（すなわち、スケーラビリティが高い）、性能の不均一性が少なく、かつ、耐障害性が高いストレージシステムのアーキテクチャ及びその制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本発明は、ホスト計算機に接続されるストレージシステムにおいて、前記ストレージシステムは、四つ以上のノードを備え、前記各ノードは、前記ホスト計算機に接続され、前記ホスト計算機と通信するホストインターフェース部と、前記ホストインターフェース部と通信するスイッチと、を備え、前記スイッチは、他の四つ以内の前記ノードが備える前記スイッチと互いに接続されることによって、前記ノードは二次元の格子状に接続されることを特徴とする。
【発明の効果】
【００１３】
本発明によれば、制限なく、任意の規模のストレージシステムを、規模に応じた妥当なコストで構成することができる。また、本発明によれば、データの伝送経路による性能の不均一性が緩和される。さらに、本発明によれば、データの伝送経路が複数存在するので耐障害性も高い。
【発明を実施するための最良の形態】
【００１４】
以下、本発明の実施の形態を図面を参照して説明する。
【００１５】
図１は、本発明の第１の実施の形態のストレージシステムの構成を示すブロック図である。
【００１６】
本実施の形態のストレージシステムは、複数のストレージ制御部１０及び複数のディスクドライブ１０４によって構成される。
【００１７】
図１には、８個のストレージ制御部１０Ａ〜１０Ｈを示すが、本実施の形態のストレージシステムは、任意の数のストレージ制御部１０を含むことができる。
【００１８】
ストレージ制御部１０は、ホスト計算機（図示省略）、ディスクドライブ１０４及び他のストレージ制御部１０と接続され、ホスト計算機からディスクドライブ１０４へのアクセス要求を受信すると、そのアクセスを実行する。あるストレージ制御部１０が、そのストレージ制御部１０に接続されていないディスクドライブ１０４へのアクセス要求を受信した場合、そのストレージ制御部１０は、そのアクセス要求を他のストレージ制御部１０に転送する。また、あるストレージ制御部１０が、そのストレージ制御部１０に接続されていないホスト計算機への応答を受信した場合、そのストレージ制御部１０は、その応答を他のストレージ制御部１０に転送する。これらの手順については、後で詳細に説明する。
【００１９】
ストレージ制御部１０は、ホスト接続制御部１０１、６ポートスイッチ１０２及びドライブ制御部１０３を備える。
【００２０】
ホスト接続制御部１０１は、ホスト計算機と接続され、それらのホスト計算機との通信を制御する。ホスト接続制御部１０１とホスト計算機との間で使用される通信プロトコルは、例えば、ＳＣＳＩ又はファイバーチャネル（ＦＣ）プロトコルである。あるいは、インターネットプロトコル（ＩＰ）又はｉＳＣＳＩ等のプロトコルが使用されてもよい。ホスト接続制御部１０１の構成については、後で詳細に説明する（図２参照）。
【００２１】
６ポートスイッチ１０２は、ホスト接続制御部１０１、ドライブ制御部１０３及び他のストレージ制御部１０内の６ポートスイッチ１０２と接続され、これらの間の接続を切り替えるスイッチである。６ポートスイッチ１０２は、６個のポート（図示省略）を備え、各ポートが接続線１１０を介してそれぞれ一つのホスト接続制御部１０１、ドライブ制御部１０３又は他の６ポートスイッチ１０２と接続される。
【００２２】
例えば、ストレージ制御部１０Ｂ内の６ポートスイッチ１０２Ｂの各ポートには、それぞれ、接続線１１０Ａ〜１１０Ｆが接続される。
【００２３】
接続線１１０Ａは、ストレージ制御部１０Ａ内の６ポートスイッチ１０２Ａに接続される。
【００２４】
接続線１１０Ｂは、ストレージ制御部１０Ｂ内のホスト接続制御部１０１Ｂに接続される。
【００２５】
接続線１１０Ｃは、図１に示さない他のストレージ制御部１０内の６ポートスイッチ１０２に接続される。
【００２６】
接続線１１０Ｄは、ストレージ制御部１０Ｃ内の６ポートスイッチ１０２Ｃに接続される。
【００２７】
接続線１１０Ｅは、ストレージ制御部１０Ｆ内の６ポートスイッチ１０２Ｆに接続される。
【００２８】
接続線１１０Ｆは、ストレージ制御部１０Ｂ内のドライブ制御部１０３Ｂに接続される。
【００２９】
ドライブ制御部１０３は、ディスクドライブ１０４と接続され、それらのディスクドライブ１０４へのアクセスの実行を制御する。ドライブ制御部１０３とディスクドライブ１０４との間で使用される通信プロトコルは、例えば、ＳＣＳＩ又はファイバーチャネル（ＦＣ）プロトコルである。またはＳＡＴＡ（Serial ATA）やＳＡＳ（Serial Attached SCSI）等のプロトコルでもよい。ドライブ制御部１０３の構成については、後で詳細に説明する（図３参照）。
【００３０】
ディスクドライブ１０４は、ハードディスクドライブである。ドライブ制御部１０３には、図１に示すように、複数のディスクドライブ１０４を接続することができる。これらの複数のディスクドライブ１０４は、データの信頼性向上のためにＲＡＩＤを構成してもよい。また、ディスクドライブ１０４は、ハードディスクドライブ以外の記憶装置（例えば、光磁気ディスク装置又は半導体記憶装置等）によって構成されてもよい。
【００３１】
本実施の形態の各ディスクドライブ１０４は、耐障害性を高めるため、二つのインターフェース（図示省略）を備え、各インターフェースがそれぞれ別のドライブ制御部１０３（例えば、ドライブ制御部１０３Ａ及び１０３Ｂ）に接続される。
【００３２】
図２は、本発明の第１の実施の形態のホスト接続制御部１０１の構成を示すブロック図である。
【００３３】
ホスト接続制御部１０１は、ホストインターフェース（Ｉ／Ｆ）部２０１、プロセッサ２０２、メモリ２０３及びローカル接続スイッチ部２０４によって構成される。
【００３４】
ホストＩ／Ｆ部２０１は、ホスト計算機と接続され、図１において説明した所定のプロトコルによる通信を実行するインターフェースである。各ホスト接続制御部１０１は、任意の個数のホストＩ／Ｆ部２０１を備えることができる。本実施の形態では、各ホスト接続制御部１０１が４個のホストＩ／Ｆ部２０１を備える。
【００３５】
プロセッサ２０２は、メモリ２０３に格納された制御プログラムを実行して、ホスト接続制御部１０１の動作を制御する。具体的には、プロセッサ２０２は、各ホストＩ／Ｆ部２０１によるホスト計算機との通信を制御する。また、ローカル接続スイッチ部２０４を制御して、ホストＩ／Ｆ部２０１と６ポートスイッチ１０２との間の接続を切り替える。
【００３６】
メモリ２０３には、プロセッサ２０２によって実行される制御プログラムが格納される。また、プロセッサ２０２が制御プログラムを実行する際に必要なデータが格納されてもよい。
【００３７】
ローカル接続スイッチ部２０４は、各ホストＩ／Ｆ部２０１、プロセッサ２０２、メモリ２０３及び６ポートスイッチ１０２と接続され、これらの間の接続を切り替えるスイッチである。スイッチ１０２は、ローカル接続スイッチ部２０４を介して各ホストＩ／Ｆ部２０１と通信する。
【００３８】
本実施の形態では、ストレージ制御部１０が６ポートスイッチ１０２を備えるため、ローカル接続スイッチ部２０４は、６ポートスイッチ１０２に接続されるポートを一つ備えればよい。また、ストレージ制御部が１０ポートスイッチを備える場合（本発明第３の実施の形態参照）も、ローカル接続スイッチ部２０４は、１０ポートスイッチに接続されるポートを一つ備えればよい。しかし、ストレージ制御部が８ポートスイッチを備える場合（本発明の第２の実施の形態参照）、ローカル接続スイッチ部２０４は、８ポートスイッチに接続されるポートを二つ備える必要がある。
【００３９】
図３は、本発明の第１の実施の形態のドライブ制御部１０３の構成を示すブロック図である。
【００４０】
ドライブ制御部１０３は、ドライブＩ／Ｆ部３０１、プロセッサ３０２、メモリ３０３及びローカル接続スイッチ部３０４によって構成される。
【００４１】
ドライブＩ／Ｆ部３０１は、ディスクドライブ１０４と接続され、それらのディスクドライブにアクセスするための通信を実行するインターフェースである。この通信には、図１において説明した所定のプロトコルが使用される。各ドライブ制御部１０３は、任意の個数のドライブＩ／Ｆ部３０１を備えることができる。本実施の形態では、各ドライブ制御部１０３が４個のドライブＩ／Ｆ部３０１を備える。
【００４２】
プロセッサ３０２は、メモリ３０３に格納された制御プログラムを実行して、ドライブ制御部１０３の動作を制御する。具体的には、プロセッサ３０２は、各ドライブＩ／Ｆ部３０１によるディスクドライブ１０４との通信を制御する。また、ローカル接続スイッチ部３０４を制御して、ドライブＩ／Ｆ部３０１と６ポートスイッチ１０２との間の接続を切り替える。
【００４３】
メモリ３０３には、プロセッサ３０２によって実行される制御プログラムが格納される。また、プロセッサ３０２が制御プログラムを実行する際に必要なデータが格納されてもよい。
【００４４】
ローカル接続スイッチ部３０４は、各ドライブＩ／Ｆ部３０１、プロセッサ３０２、メモリ３０３及び６ポートスイッチ１０２と接続され、これらの間の接続を切り替えるスイッチである。スイッチ１０２は、ローカル接続スイッチ部３０４を介して各ドライブＩ／Ｆ部３０１と通信する。
【００４５】
本実施の形態では、ストレージ制御部１０が６ポートスイッチ１０２を備えるため、ローカル接続スイッチ部３０４は、６ポートスイッチ１０２に接続されるポートを一つ備えればよい。また、ストレージ制御部が１０ポートスイッチを備える場合（本発明第３の実施の形態参照）も、ローカル接続スイッチ部３０４は、１０ポートスイッチに接続されるポートを一つ備えればよい。しかし、ストレージ制御部が８ポートスイッチを備える場合（本発明の第２の実施の形態参照）、ローカル接続スイッチ部３０４は、８ポートスイッチに接続されるポートを二つ備える必要がある。
【００４６】
次に、本実施の形態において、ホスト計算機からディスクドライブ１０４へのアクセス及びそれに対する応答が伝送される経路を決定するアルゴリズム（ルーティングアルゴリズム）を、図を参照して説明する。
【００４７】
図４は、本発明の第１の実施の形態のストレージシステムの接続の説明図である。
【００４８】
図４は、図１のストレージ制御部１０が、接続線１１０によって二次元の格子状に接続された状態を示す。本実施の形態では、一つのノード４０（ストレージノード）が一つのストレージ制御部１０に相当する。また、一つのリンク４１が一つの接続線１１０に相当する。ホスト計算機及びディスクドライブ１０４については、図示を省略する。また、ストレージ制御部１０内の構成についても、図示を省略する。
【００４９】
図４の各ノード４０に表示された値（０、０）等は、各ノード４０の二次元のアドレス（座標）である。二次元の格子状に配置された各ノード４０は、二次元のアドレスによって識別される。図４において、あるノード４０のアドレスを（ｘ、ｙ）とすると、ｘの値は、その左側に隣接するノード４０のｘの値より１だけ大きい。また、あるノード４０のｙの値は、その下側に隣接するノード４０のｙの値より１だけ大きい。以下の説明において、各ノード４０をアドレスによって識別する必要がある場合は、ノード４０（０、０）のようにアドレスを付けて表示する。図４には、ノード４０（０、０）からノード４０（２、２）まで、９個のノード４０を示す。しかし、本実施の形態のストレージシステムは、任意の数のノード４０をふくむことができる。
【００５０】
例えば、図４のノード４０（１、１）がストレージ制御部１０Ｂである場合、リンク４１Ａ、４１Ｂ、４１Ｃ及び４１Ｄは、それぞれ、接続線１１０Ａ、１１０Ｃ、１１０Ｄ及び１１０Ｅである。
【００５１】
なお、以下の説明では、便宜上、二次元の格子状に配置されたノード４０の横方向の並びを「行」、縦方向の並びを「列」と記載する。例えば、図４において、ノード４０（０、１）、（１、１）及び（２、１）は、一つの行を構成し、ノード４０（０、０）、（０、１）及び（０、２）は、一つの列を構成する。
【００５２】
また、便宜上、ｘの値が大きくなる方向を「右側」、ｘの値が小さくなる方向を「左側」、ｙの値が大きくなる方向を「上側」、ｙの値が小さくなる方向を「下側」と記載する。例えば、ノード４０（１、０）はノード４０（０、０）の右側にあり、ノード４０（０、１）はノード４０（０、２）の下側にある。
【００５３】
図５は、本発明の第１の実施の形態のストレージシステムにおいて使用されるパケットの説明図である。
【００５４】
本実施の形態において、アクセス要求（読み出し要求又は書き込み要求）及び応答は、パケット５０として、ノード４０によってリンク４１を介して送受信される。
【００５５】
図５Ａ及び図５Ｂは、アクセス要求（読み出し要求及び書き込み要求）のパケット５０の説明図であり、図５Ｃ及び図５Ｄは、応答のパケット５０の説明図である。
【００５６】
図５Ａは、読み出し要求のパケット５０の説明図である。
【００５７】
読み出し要求のパケット５０は、行き先アドレス５０１、迂回マーク５０２、逆探索マーク５０３、探索カウント５０４、要求種別５０５、タグ５０６、返送アドレス５０７、ボリューム番号５０８、ブロックアドレス５０９及びデータ長５１０の領域を含む。
【００５８】
行き先アドレス５０１は、パケット５０の行き先のノード４０の二次元のアドレス（ａ、ｂ）である。具体的には、読み出し要求の対象のデータが格納されたディスクドライブ１０４が接続されたノード４０のアドレスである。
【００５９】
迂回マーク５０２は、迂回が実行されているか否かを示すフラグである。迂回とは、障害が発生したノード４０又はリンク４１を避けるようにパケット５０を送信する処理である。迂回については、後で詳細に説明する。
【００６０】
迂回マーク５０２の値は、迂回が実行されているときに「有効」、迂回が実行されていないときに「無効」となる。例えば、迂回マーク５０２が１ビットの領域であり、その値「１」が「有効」に、値「０」が「無効」に対応してもよい。以下の説明において、迂回マーク５０２を「有効」にすることを、「迂回マークを付与する」と記載する。また、迂回マーク５０２を「無効」にすることを、「迂回マークを消去する」と記載する。
【００６１】
逆探索マーク５０３は、実行されている探索の方向を示すフラグである。探索とは、行き先のノード４０に至るリンク４１に障害が発生した場合に、行き先のノード４０に至る他のリンク４１を介してパケット５０の送信を試みる処理である。探索については、後で詳細に説明する。
【００６２】
逆探索マーク５０３の値は、時計回りの探索が実行されているときに「有効」、反時計回りの探索が実行されているときに「無効」となる。例えば、逆探索マーク５０３が１ビットの領域であり、その値「１」が「有効」に、値「０」が「無効」に対応してもよい。以下の説明において、逆探索マーク５０３を「有効」にすることを、「逆探索マークを付与する」と記載する。また、逆探索マーク５０３を「無効」にすることを、「逆探索マークを消去する」と記載する。
【００６３】
探索カウント５０４は、探索が開始されてからパケット５０が送信された回数を示す。探索が開始されていないとき、探索カウント５０４の値は「０」となる。探索カウント５０４の値が「８」より大きくなってもなおパケット５０が行き先のノード４０に到達していない場合、行き先のノード４０又はそこに至る全てのリンク４１に障害が発生している。
【００６４】
要求種別５０５は、パケット５０が読み出し要求又は書き込み要求のいずれであるかを示す。パケット５０が読み出し要求である場合、要求種別５０５は、読み出し要求を示す値となる。
【００６５】
タグ５０６は、パケット５０に関するアクセス要求を発行したホスト計算機のアクセス要求を識別する一意の識別子である。読み出し要求のパケット５０において、タグ５０６は、読み出し要求を発行したホスト計算機の読出し要求を識別する一意の識別子である。
【００６６】
返送アドレス５０７は、アクセス要求のパケット５０に対する応答のパケット５０の返送先のノード４０の二次元のアドレス（ｃ、ｄ）である。読み出し要求のパケット５０において、返送アドレス５０７は、読み出し要求を発行したホスト計算機が接続されたノード４０のアドレスである。
【００６７】
ボリューム番号５０８は、アクセス要求の対象のデータが格納されたディスクドライブ１０４の番号である。ボリューム番号５０８は、アクセス要求の対象のデータが格納された論理ボリュームの番号であってもよい。論理ボリュームとは、ホスト計算機によって論理的な一つのディスクドライブとして認識される記憶領域である。読み出し要求のパケット５０において、ボリューム番号５０８は、読み出し要求の対象のデータが格納されたディスクドライブ１０４の番号又は論理ボリュームの番号である。
【００６８】
ブロックアドレス５０９は、アクセス要求の対象のデータが格納されたディスクドライブ１０４上または論理ボリューム内の記憶領域（例えば、論理ブロック）を示すアドレスである。読み出し要求のパケット５０において、ブロックアドレス５０９は、読み出し要求の対象のデータが格納されたディスクドライブ１０４上または論理ボリューム内の論理ブロックのアドレスである。
【００６９】
データ長５１０は、アクセス要求の対象のデータの長さ（サイズ）である。例えば論理ブロックの数で示してもよい。読み出し要求のパケット５０において、データ長５１０は、読み出し要求の対象のデータの長さである。
【００７０】
図５Ｂは、書き込み要求のパケット５０の説明図である。
【００７１】
書き込み要求のパケット５０は、行き先アドレス５０１、迂回マーク５０２、逆探索マーク５０３、探索カウント５０４、要求種別５０５、タグ５０６、返送アドレス５０７、ボリューム番号５０８、ブロックアドレス５０９、データ長５１０及び書き込みデータ５１１の領域を含む。以下、書き込み要求のパケット５０の各領域について説明する。ただし、読み出し要求のパケット５０と同様の部分については、説明を省略する。
【００７２】
行き先アドレス５０１は、書き込み要求の対象のデータが格納されるディスクドライブ１０４が接続されたノード４０の二次元のアドレスである。
【００７３】
要求種別５０５は、パケット５０が書き込み要求のパケット５０であることを示す。
【００７４】
タグ５０６は、書き込み要求を発行したホスト計算機の書き込み要求を識別する一意の識別子である。
【００７５】
返送アドレス５０７は、書き込み要求を発行したホスト計算機が接続されたノード４０のアドレスである。
【００７６】
ボリューム番号５０８は、書き込み要求の対象のデータが格納されるディスクドライブ１０４の番号又は論理ボリュームの番号である。
【００７７】
ブロックアドレス５０９は、書き込み要求の対象のデータが格納されるディスクドライブ１０４の番号上または論理ボリューム内の論理ブロックのアドレスである。
【００７８】
データ長５１０は、書き込み要求の対象のデータの長さである。
【００７９】
書き込みデータ５１１は、書き込み要求の対象のデータ、すなわち、書き込み要求によって書き込まれるデータである。
【００８０】
図５Ｃは、読み出し応答のパケット５０の説明図である。
【００８１】
読み出し応答のパケット５０は、要求された読み出しを実行したノード４０（すなわち、読み出し要求の対象のデータをディスクドライブ１０４から読み出したノード４０）によって作成され、要求元のノード４０に返送される。
【００８２】
読み出し応答のパケット５０は、行き先アドレス５０１、迂回マーク５０２、逆探索マーク５０３、探索カウント５０４、応答種別５１２、タグ５０６、アクセス結果５１３、データ長５１０及び読み出しデータ５１４の領域を含む。以下、読み出し応答のパケット５０の各領域について説明する。ただし、アクセス要求のパケット５０と同様の部分については、説明を省略する。
【００８３】
行き先アドレス５０１は、読み出し応答のパケット５０に対応する読み出し要求を発行したホスト計算機が接続されたノード４０の二次元のアドレスである。具体的には、行き先アドレス５０１の値は、対応する読み出し要求のパケット５０の返送アドレス５０７の値と同じである。
【００８４】
応答種別５１２は、応答のパケット５０が読み出し応答のパケット５０であるか書き込み応答のパケット５０であるかを示す。
【００８５】
タグ５０６は、応答の返送先のホスト計算機の読出し要求を識別する一意の識別子である。具体的には、タグ５０６の値は、読み出し応答のパケット５０に対応する読み出し要求のパケット５０のタグ５０６の値と同じである。
【００８６】
アクセス結果５１３は、要求されたアクセスが成功したか否かを示す。アクセスが失敗した場合、アクセス結果５１３は、失敗の状態（エラーの種類）に関する情報を含んでもよい。
【００８７】
読み出しデータ５１４は、読み出し要求によって読み出されたデータである。
【００８８】
図５Ｄは、書き込み応答のパケット５０の説明図である。
【００８９】
書き込み応答のパケット５０は、要求された書き込みを実行したノード４０（すなわち、書き込み要求の対象のデータをディスクドライブ１０４に書き込んだノード４０）によって作成され、要求元のノード４０に返送される。
【００９０】
書き込み応答のパケット５０は、行き先アドレス５０１、迂回マーク５０２、逆探索マーク５０３、探索カウント５０４、応答種別５１２、タグ５０６及びアクセス結果５１３の領域を含む。以下、書き込み応答のパケット５０の各領域について説明する。ただし、読み出し応答のパケット５０と同様の部分については、説明を省略する。
【００９１】
行き先アドレス５０１は、書き込み応答のパケット５０に対応する書き込み要求を発行したホスト計算機が接続されたノード４０の二次元のアドレスである。具体的には、行き先アドレス５０１の値は、対応する書き込み要求のパケット５０の返送アドレス５０７の値と同じである。
【００９２】
タグ５０６は、応答の返送先のホスト計算機の書き込み要求を識別する一意の識別子である。具体的には、タグ５０６の値は、書き込み応答のパケット５０に対応する書き込み要求のパケット５０のタグ５０６の値と同じである。
【００９３】
図６は、本発明の第１の実施の形態の基本的なルーティングアルゴリズムのフローチャートである。
【００９４】
図６のフローチャートは、ノード４０が自ノードと接続するホスト計算機からいずれかのディスクドライブ１０４内のデータへのアクセス要求を受信したとき（６０１）、ノード４０が隣接する他のノード４０からいずれかのディスクドライブ１０４内のデータへのアクセス要求を受信したとき（６０５）、又は、ノード４０が隣接する他のノード４０からいずれかのホスト計算機への応答を受信したとき（６０５）、それらの要求又は応答を受信したノード４０によって実行される処理の手順である。この処理は、ノード４０及びリンク４１に障害が発生していないことを前提とする。
【００９５】
なお、この処理は、ノード４０（すなわち、ストレージ制御部１０）内のプロセッサによって実行される。具体的には、ホスト接続制御部１０１のプロセッサ２０１、ドライブ制御部１０３のプロセッサ３０２、６ポートスイッチ１０２のプロセッサ（図示省略）又は他のプロセッサ（図示省略）のいずれによって実行されてもよい。また、ノード４０間のパケット５０の送受信は、各ノード内の６ポートスイッチ１０２によって実行される。
【００９６】
ノード４０は、自ノードと接続するホスト計算機からいずれかのディスクドライブ１０４内のデータへのアクセス（書き込み又は読み出し）要求を受信すると、図６の処理を開始する（６０１）。この処理が開始すると、ノード４０は、アクセス要求の行き先のノード４０（すなわち、アクセス要求の対象のデータが格納されている（又は、そのデータが書き込まれる）ディスクドライブ１０４に接続されたノード４０）を特定し、そのノード４０のアドレス（ａ、ｂ）をアクセス要求に付与する（６０２）。具体的には、そのアクセス要求のパケット５０の行き先アドレス５０１をアドレス（ａ、ｂ）とする。
【００９７】
次に、ノード４０は、自ノード４０（すなわち、図６の処理を実行しているノード４０自身）のアドレス（Ａ、Ｂ）を取得し、そのアドレス（Ａ、Ｂ）を、応答の返送先として、アクセス要求に付与する（６０３）。具体的には、アクセス要求のパケット５０の返送アドレス５０７をアドレス（Ａ、Ｂ）とする。
【００９８】
次に、応答を返答するために要求元のホスト計算機を記録する（６０４）。具体的には、アクセス要求のパケット５０のタグ５０６を、要求元のホスト計算機のアクセス要求を一意に識別する値とする。
【００９９】
次に、ステップ６０８に進む。
【０１００】
一方、ノード４０は、隣接する他のノード４０からいずれかのディスクドライブ１０４内のデータへのアクセス要求を受信したとき、又は、隣接する他のノード４０からいずれかのホスト計算機への応答を受信したときにも、図６の処理を開始する（６０５）。この処理が開始されると、ノード４０は、受信した要求又は応答の行き先のノード４０のアドレス（ａ、ｂ）を取得する（６０６）。具体的には、受信した要求又は応答のパケット５０の行き先アドレス５０１を参照して、その値を取得する。
【０１０１】
次に、ノード４０は、自ノード４０のアドレス（Ａ、Ｂ）を取得する（６０７）。
【０１０２】
次に、ステップ６０８に進む。
【０１０３】
ステップ６０８において、ノード４０は、行き先のノード４０のアドレス（ａ、ｂ）と、自ノード４０のアドレス（Ａ、Ｂ）とを比較する。具体的には、Ａ＝ａかつＢ＝ｂであるか否かを判定する。
【０１０４】
ステップ６０８において、Ａ＝ａかつＢ＝ｂでない（すなわち、Ａ＝ａでないか、又は、Ｂ＝ｂでない）と判定された場合、自ノード４０は、行き先のノード４０ではない。このため、受信した要求又は応答の送信先を決定するために、図７のステップ７０１に進む（１）。
【０１０５】
一方、ステップ６０８において、Ａ＝ａかつＢ＝ｂであると判定された場合、自ノード４０は、行き先のノード４０である。
【０１０６】
このため、次に、ノード４０は、応答を受信したか、要求を受信したかを判定する（６０９）。具体的には、ノード４０が、ホスト計算機又は隣接する他のノード４０からディスクドライブ１０４内のデータへのアクセス要求を受信した場合（６０１、６０５）、ステップ６０９において、ノード４０が要求を受信したと判定される。一方、ノード４０が隣接する他のノード４０からホスト計算機への応答を受信した場合（６０５）、ステップ６０９において、ノード４０が応答を受信したと判定される。
【０１０７】
ステップ６０９において、ノード４０が応答を受信したと判定された場合、応答の返送先のホスト計算機が自ノード４０に接続されている。このため、ノード４０は、自ノード４０に接続されたホスト計算機から、応答の返送先のホスト計算機を特定する（６１４）。具体的には、応答のパケット５０のタグ５０６の値を参照して、その値に対応するホスト計算機を特定する。
【０１０８】
次に、ノード４０は、特定されたホスト計算機に応答を返送して（６１５）、処理を終了する（６１６）。
【０１０９】
一方、ステップ６０９において、ノード４０が要求を受信したと判定された場合、受信したアクセス要求の対象のデータは、自ノード４０に接続されたディスクドライブ１０４に含まれる。このため、ノード４０は、受信したアクセス要求に従って、自ノード４０に接続されたディスクドライブ１０４にアクセスする（６１０）。
【０１１０】
次に、ノード４０は、実行したアクセス結果にしたがって、応答のパケット５０を作成する（６１１）。
【０１１１】
次に、ノード４０は、作成した応答のパケット５０の返送先のノード４０を特定し、そのノード４０のアドレスを新たな行き先のノード４０のアドレス（ａ、ｂ）として、応答のパケット５０に付与する（６１２）。具体的には、実行したアクセスに関するアクセス要求のパケット５０の返送アドレス５０７の値を参照する。そして、その返送アドレス５０７の値を、作成した応答のパケット５０の行き先アドレス５０１として付与する。このとき、同様にして、アクセス要求のパケット５０のタグ５０６の値を、応答のパケット５０のタグ５０６として付与する。
【０１１２】
次に、ノード４０は、作成した応答の行き先のノード４０のアドレス（ａ、ｂ）と、自ノード４０のアドレス（Ａ、Ｂ）とを比較する。具体的には、Ａ＝ａかつＢ＝ｂであるか否かを判定する（６１３）。
【０１１３】
ステップ６１３において、Ａ＝ａかつＢ＝ｂでないと判定された場合、自ノード４０は、応答の行き先のノード４０ではない。このため、当該応答の送信先を決定するために、図７のステップ７０１に進む（１）。
【０１１４】
一方、ステップ６１３において、Ａ＝ａかつＢ＝ｂであると判定された場合、自ノード４０は、応答の行き先のノード４０である。このため、次に、ステップ６１４に進む。
【０１１５】
ステップ６１４以降の処理は、既に説明した通りである。
【０１１６】
図７は、本発明の第１の実施の形態の基本的なルーティングアルゴリズムにおいて、自ノード４０が行き先のノード４０でない場合に実行される処理のフローチャートである。
【０１１７】
図６のステップ６０８又はステップ６１３において、Ａ＝ａかつＢ＝ｂでないと判定された場合（１）、ノード４０は、Ａ＝ａであるか否かを判定する（７０１）。
【０１１８】
Ａ＝ａ又はＢ＝ｂのいずれかを満たす場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ列又は同じ行にある。この場合、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路は、一つのみ存在する。
【０１１９】
ステップ７０１において、Ａ＝ａであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ列にある。このため、ノード４０は、Ｂ＜ｂであるか否かを判定する（７０２）。
【０１２０】
ステップ７０２において、Ｂ＜ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側にある。このとき、自ノード４０の上側に隣接するノード４０（Ａ、Ｂ＋１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にある。すなわち、要求又は応答を自ノード４０の上側に隣接するノード４０（Ａ、Ｂ＋１）に送信すれば、その要求又は応答は、行き先のノード４０に最も近づく。そこで、ノード４０は、要求又は応答を隣接するノード４０（Ａ、Ｂ＋１）に送信する（７０３）。そして、処理を終了する（７０４）。
【０１２１】
一方、ステップ７０２において、Ｂ＜ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の下側にある。このとき、自ノード４０の下側に隣接するノード４０（Ａ、Ｂ−１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にある。すなわち、要求又は応答を自ノード４０の下側に隣接するノード４０（Ａ、Ｂ−１）に送信すれば、その要求又は応答は、行き先のノード４０に最も近づく。そこで、ノード４０は、要求又は応答を隣接するノード４０（Ａ、Ｂ−１）に送信する（７０５）。そして、処理を終了する（７０６）。
【０１２２】
ステップ７０１において、Ａ＝ａでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ列にない。このため、ノード４０は、Ｂ＝ｂであるか否かを判定する（７０７）。
【０１２３】
ステップ７０７において、Ｂ＝ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ行にある。このため、ノード４０は、Ａ＜ａであるか否かを判定する（７０８）。
【０１２４】
ステップ７０８において、Ａ＜ａであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側にある。このとき、自ノード４０の右側に隣接するノード４０（Ａ＋１、Ｂ）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にある。すなわち、要求又は応答を自ノード４０の右側に隣接するノード４０（Ａ＋１、Ｂ）に送信すれば、その要求又は応答は、行き先のノード４０に最も近づく。そこで、ノード４０は、要求又は応答を隣接するノード４０（Ａ＋１、Ｂ）に送信する（７０９）。そして、処理を終了する（７１０）。
【０１２５】
一方、ステップ７０８において、Ａ＜ａでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左側にある。このとき、自ノード４０の左側に隣接するノード４０（Ａ−１、Ｂ）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にある。すなわち、要求又は応答を自ノード４０の左側に隣接するノード４０（Ａ−１、Ｂ）に送信すれば、その要求又は応答は、行き先のノード４０に最も近づく。そこで、ノード４０は、要求又は応答を隣接するノード４０（Ａ−１、Ｂ）に送信する（７１１）。そして、処理を終了する（７１２）。
【０１２６】
ステップ７０７において、Ｂ＝ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ行又は同じ列のいずれにもない。このとき、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路は、二つ存在する。この場合、ノード４０は、Ａ＜ａであるか否かを判定する（７１３）。
【０１２７】
ステップ７１３において、Ａ＜ａであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側（右上側又は右下側）にある。すなわち、右側に隣接するノード４０（Ａ＋１、Ｂ）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路の一方の上にある。このため、ノード４０は、右側に隣接するノード４０（Ａ＋１、Ｂ）との間の通信量αを測定する（７１４）。
【０１２８】
次に、ノード４０は、Ｂ＜ｂであるか否かを判定する（７１５）。
【０１２９】
ステップ７１５において、Ｂ＜ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側（右上側又は左上側）にある。すなわち、上側に隣接するノード４０（Ａ、Ｂ＋１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路のもう一方の上にある。このため、ノード４０は、上側に隣接するノード４０（Ａ、Ｂ＋１）との間の通信量γを測定する（７１６）。
【０１３０】
このとき、ステップ７１３及び７１５の判定の結果を合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右上側にある。
【０１３１】
このとき、要求又は応答を自ノード４０の右側に隣接するノード４０（Ａ＋１、Ｂ）又は上側に隣接するノード４０（Ａ、Ｂ＋１）のいずれに送信しても、その要求又は応答は、行き先のノード４０に最も近づく。したがって、ノード４０は、要求又は応答を右側に隣接するノード４０又は上側に隣接するノード４０のいずれに送信してもよい。
【０１３２】
しかし、上記の測定された通信量α及びγに差がある場合、通信量が少ない方のノード４０に送信した方が、データ伝送速度が向上する。このため、ノード４０は、通信量を比較して、通信量が少ない方のノード４０を送信先として選択する。
【０１３３】
なお、行き先のノード４０が自ノード４０の右下側、左上側又は左下側にある場合も、同様にして、通信量の少ない方のノード４０が送信先として選択される。
【０１３４】
ノード４０は、通信量α＜通信量γであるか否かを判定する（７１７）。
【０１３５】
ステップ７１７において、α＜γであると判定された場合、ノード４０は、要求又は応答を、右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（７１８）。そして、処理を終了する（７１９）。
【０１３６】
一方、ステップ７１７において、α＜γでない（すなわち、γがα以下である）と判定された場合、ノード４０は、要求又は応答を、上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（７２０）。そして、処理を終了する（７２１）。
【０１３７】
ステップ７１５において、Ｂ＜ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の下側（右下側又は左下側）にある。すなわち、下側に隣接するノード４０（Ａ、Ｂ−１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路のもう一方の上にある。このため、ノード４０は、下側に隣接するノード４０（Ａ、Ｂ−１）との間の通信量δを測定する（７２２）。
【０１３８】
このとき、ステップ７１３及び７１５の判定の結果を合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右下側にある。
【０１３９】
このため、ノード４０は、通信量α＜通信量δであるか否かを判定する（７２３）。
【０１４０】
ステップ７２３において、α＜δであると判定された場合、ノード４０は、要求又は応答を、右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（７１８）。そして、処理を終了する（７１９）。
【０１４１】
一方、ステップ７２３において、α＜δでない（すなわち、δがα以下である）と判定された場合、ノード４０は、要求又は応答を、下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（７２４）。そして、処理を終了する（７２５）。
【０１４２】
ステップ７１３において、Ａ＜ａでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左側（左上側又は左下側）にある。すなわち、左側に隣接するノード４０（Ａ−１、Ｂ）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路の一方の上にある。このため、ノード４０は、左側に隣接するノード４０（Ａ−１、Ｂ）との間の通信量βを測定する（７２６）。
【０１４３】
次に、ノード４０は、Ｂ＜ｂであるか否かを判定する（７２７）。
【０１４４】
ステップ７２７において、Ｂ＜ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側（右上側又は左上側）にある。すなわち、上側に隣接するノード４０（Ａ、Ｂ＋１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路のもう一方の上にある。このため、ノード４０は、上側に隣接するノード４０（Ａ、Ｂ＋１）との間の通信量γを測定する（７２８）。
【０１４５】
このとき、ステップ７１３及び７２７の判定の結果を合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左上側にある。
【０１４６】
このため、ノード４０は、通信量β＜通信量γであるか否かを判定する（７２９）。
【０１４７】
ステップ７２９において、β＜γであると判定された場合、ノード４０は、要求又は応答を、左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（７３０）。そして、処理を終了する（７３１）。
【０１４８】
一方、ステップ７２９において、β＜γでない（すなわち、γがβ以下である）と判定された場合、ノード４０は、要求又は応答を、上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（７２０）。そして、処理を終了する（７２１）。
【０１４９】
ステップ７２７において、Ｂ＜ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の下側（右下側又は左下側）にある。すなわち、下側に隣接するノード４０（Ａ、Ｂ−１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路のもう一方の上にある。このため、ノード４０は、下側に隣接するノード４０（Ａ、Ｂ−１）との間の通信量δを測定する（７３２）。
【０１５０】
このとき、ステップ７１３及び７２７の判定の結果を合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左下側にある。
【０１５１】
このため、ノード４０は、通信量β＜通信量δであるか否かを判定する（７３３）。
【０１５２】
ステップ７３３において、β＜δであると判定された場合、ノード４０は、要求又は応答を、左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（７３０）。そして、処理を終了する（７３１）。
【０１５３】
一方、ステップ７３３において、β＜δでない（すなわち、δがβ以下である）と判定された場合、ノード４０は、要求又は応答を、下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（７２４）。そして、処理を終了する（７２５）。
【０１５４】
なお、ステップ７０３、７０５、７０９、７１１、７１８、７２０、７２４又は７３０において要求又は応答が送信されたとき、その要求又は応答を受信したノード４０は、ステップ６０５から図６の処理を開始する。
【０１５５】
次に、図６及び図７に示したルーティングアルゴリズムを適用した例を、図８及び図９を参照して説明する。
【０１５６】
図８は、本発明の第１の実施の形態の基本的なルーティングアルゴリズムの適用例の説明図である。
【０１５７】
図８は、行き先のノード４０（ａ、ｂ）が、自ノード４０（Ａ、Ｂ）と同じ行の右側にある場合を示す。
【０１５８】
この場合、ステップ６０８において、Ａ＝ａかつＢ＝ｂでない（すなわち、Ａ＝ａでないか、又は、Ｂ＝ｂでない）と判定される。
【０１５９】
ステップ７０１では、Ａ＝ａでないと判定される。
【０１６０】
ステップ７０７では、Ｂ＝ｂであると判定される。
【０１６１】
ステップ７０８では、Ａ＜ａであると判定される。
【０１６２】
このとき、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路は、一つのみ存在する。そして、自ノード４０（Ａ、Ｂ）の右側に隣接するノード４０（Ａ＋１、Ｂ）は、その最短経路上にある。
【０１６３】
このため、ノード４０（Ａ、Ｂ）は、右側に隣接するノード４０（Ａ＋１、Ｂ）に要求又は応答を送信する（７０９）。そして、処理を終了する（７１０）。
【０１６４】
図９は、本発明の第１の実施の形態の基本的なルーティングアルゴリズムの別の適用例の説明図である。
【０１６５】
図９は、行き先のノード４０（ａ、ｂ）が、自ノード４０（Ａ、Ｂ）の右上側にある場合を示す。
【０１６６】
この場合、ステップ６０８において、Ａ＝ａかつＢ＝ｂでない（すなわち、Ａ＝ａでないか、又は、Ｂ＝ｂでない）と判定される。
【０１６７】
ステップ７０１では、Ａ＝ａでないと判定される。
【０１６８】
ステップ７０７では、Ｂ＝ｂでないと判定される。
【０１６９】
ステップ７１３では、Ａ＜ａであると判定される。このため、右側に隣接するノード４０（Ａ＋１、Ｂ）との間の通信量αが計測される（７１４）。
【０１７０】
ステップ７１５では、Ｂ＜ｂであると判定される。このため、上側に隣接するノード４０（Ａ、Ｂ＋１）との間の通信量γが計測される（７１６）。
【０１７１】
このとき、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路は、二つ存在する。そして、自ノード４０（Ａ、Ｂ）の右側に隣接するノード４０（Ａ＋１、Ｂ）及び上側に隣接するノード４０（Ａ、Ｂ＋１）は、それぞれ、二つの最短経路上にある。
【０１７２】
ステップ７１７では、α＜γであるか否かが判定される。図９の例では、α＜γであると仮定する。したがって、ステップ７１７では、α＜γであると判定される。
【０１７３】
このため、ノード４０（Ａ、Ｂ）は、右側に隣接するノード４０（Ａ＋１、Ｂ）に要求又は応答を送信する（７１８）。そして、処理を終了する（７１９）。
【０１７４】
次に、ノード４０又はリンク４１の障害を考慮したルーティングアルゴリズムについて、図１０〜図１８を参照して説明する。
【０１７５】
図１０は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムのフローチャートである。
【０１７６】
図１０のフローチャートに示す処理は、図６及び図７の処理と同様に、ノード４０が自ノードに接続するホスト計算機からいずれかのディスクドライブ１０４内のデータへのアクセス要求を受信したとき（１００１）、ノード４０が隣接する他のノード４０からいずれかのディスクドライブ１０４内のデータへのアクセス要求を受信したとき（１００５）、又は、ノード４０が隣接する他のノード４０からいずれかのホスト計算機への応答を受信したとき（１００５）、それらの要求又は応答を受信したノード４０によって実行される。
【０１７７】
なお、この処理は、図６及び図７の処理と同様、ノード４０（すなわち、ストレージ制御部１０）内のプロセッサによって実行される。具体的には、ホスト接続制御部１０１のプロセッサ２０１、ドライブ制御部１０３のプロセッサ３０２、６ポートスイッチ１０２のプロセッサ（図示省略）又はその他のプロセッサ（図示省略）のいずれによって実行されてもよい。また、ノード４０間のパケット５０の送受信は、各ノード内の６ポートスイッチ１０２によって実行される。
【０１７８】
図１０以降の説明において、本実施の形態の基本的なルーティングアルゴリズム（図６〜図９）と同様の部分については、詳細な説明を省略する。
【０１７９】
ノード４０は、ホスト計算機からディスクドライブ１０４内のデータへのアクセス（書き込み又は読み出し）要求を受信すると、図１０の処理を開始する（１００１）。この処理が開始すると、ノード４０は、アクセス要求の行き先のノード４０（すなわち、アクセス要求の対象のデータが格納されている（又は、そのデータが書き込まれる）ディスクドライブ１０４に接続されたノード４０）を特定し、そのノード４０のアドレス（ａ、ｂ）をアクセス要求に付与する（１００２）。具体的には、そのアクセス要求のパケット５０の行き先アドレス５０１をアドレス（ａ、ｂ）とする。
【０１８０】
次に、ノード４０は、自ノード４０（すなわち、図１０の処理を実行しているノード４０自身）のアドレス（Ａ、Ｂ）を取得し、そのアドレス（Ａ、Ｂ）を、応答の返送先として、アクセス要求に付与する（１００３）。具体的には、アクセス要求のパケット５０の返送アドレス５０７をアドレス（Ａ、Ｂ）とする。
【０１８１】
次に、応答を返答するために要求元のホスト計算機を記録する（１００４）。具体的には、アクセス要求のパケット５０のタグ５０６の値を、要求元のホスト計算機のアクセス要求を一意に識別する値とする。
【０１８２】
次に、ステップ１００９に進む。
【０１８３】
一方、ノード４０は、隣接する他のノード４０からいずれかのディスクドライブ１０４内のデータへのアクセス要求を受信したとき、又は、隣接する他のノード４０からいずれかのホスト計算機への応答を受信したときにも、図１０の処理を開始する（１００５）。
【０１８４】
この処理が開始されると、ノード４０は、受信した要求又は応答の送信元の隣接ノード４０のアドレス（Ｃ、Ｄ）を記録する（１００６）。アドレス（Ｃ、Ｄ）は、メモリ２０３、メモリ３０３又はその他のメモリに記録されてもよい。
【０１８５】
次に、ノード４０は、受信した要求又は応答の行き先のノード４０のアドレス（ａ、ｂ）を取得する（１００７）。具体的には、受信した要求又は応答のパケット５０の行き先アドレス５０１を参照して、その値を取得する。
【０１８６】
次に、ノード４０は、自ノード４０のアドレス（Ａ、Ｂ）を取得する（１００８）。
【０１８７】
次に、ステップ１００９に進む。
【０１８８】
ステップ１００９において、ノード４０は、行き先のノード４０のアドレス（ａ、ｂ）と、自ノード４０のアドレス（Ａ、Ｂ）とを比較する。具体的には、Ａ＝ａかつＢ＝ｂであるか否かを判定する。
【０１８９】
ステップ１００９において、Ａ＝ａかつＢ＝ｂでない（すなわち、Ａ＝ａでないか、又は、Ｂ＝ｂでない）と判定された場合、自ノード４０は、行き先のノード４０ではない。このため、ノード４０は、受信した要求又は応答に迂回マーク５０２が付与されているか否かを判定する（１０１０）。具体的には、受信した要求又は応答のパケット５０を参照し、迂回マーク５０２が付与されているか否か（すなわち、迂回マーク５０２の値が有効であるか否か）を判定する。ノード４０又はリンク４１に発生した障害のため、要求又は応答のパケット５０の送信に失敗したとき、その障害を迂回するようにパケット５０が再送信される。このとき、再送信されたパケット５０に迂回マーク５０２が付与される。迂回マーク５０２が付与された場合の処理については、後で詳細に説明する。
【０１９０】
ステップ１０１０において、受信した要求又は応答に迂回マーク５０２が付与されていると判定された場合、当該要求又は応答は、障害を迂回するように送信されている。ノード４０は、このような要求又は応答の送信先を、通常とは異なる方法で決定する必要がある。このため、図１８のステップ１８０１に進む（２）。
【０１９１】
一方、ステップ１０１０において、受信した要求又は応答に迂回マーク５０２が付与されていないと判定された場合、その要求又は応答の送信先を決定するため、図１１のステップ１１０１に進む（３）。
【０１９２】
ステップ１００９において、Ａ＝ａかつＢ＝ｂであると判定された場合、自ノード４０は、行き先のノード４０である。
【０１９３】
このため、次に、ノード４０は、応答を受信したか、要求を受信したかを判定する（１０１１）。具体的には、ノード４０が、自ノードと接続するホスト計算機又は隣接する他のノード４０からディスクドライブ１０４内のデータへのアクセス要求を受信した場合（１００１、１００５）、ステップ１０１１において、ノード４０が要求を受信したと判定される。一方、ノード４０が隣接する他のノード４０からホスト計算機への応答を受信した場合（１００５）、ステップ１０１１において、ノード４０が応答を受信したと判定される。
【０１９４】
ステップ１０１１において、ノード４０が応答を受信したと判定された場合、応答の返送先のホスト計算機が自ノード４０に接続されている。このため、ノード４０は、自ノード４０に接続されたホスト計算機から、応答の返送先のホスト計算機を特定する（１０１６）。具体的には、応答のパケット５０のタグ５０６の値を参照して、その値に対応するホスト計算機を特定する。
【０１９５】
次に、ノード４０は、特定されたホスト計算機に応答を返送して（１０１７）、処理を終了する（１０１８）。
【０１９６】
一方、ステップ１０１１において、ノード４０が要求を受信したと判定された場合、受信したアクセス要求の対象のデータは、自ノード４０に接続されたディスクドライブ１０４に含まれる。このため、ノード４０は、受信したアクセス要求に従って、自ノード４０に接続されたディスクドライブ１０４にアクセスする（１０１２）。
【０１９７】
次に、ノード４０は、実行したアクセス結果にしたがって、応答のパケット５０を作成する（１０１３）。
【０１９８】
次に、ノード４０は、作成した応答のパケット５０の返送先のノード４０を特定し、そのノード４０のアドレスを新たな行き先のノード４０のアドレス（ａ、ｂ）として、応答のパケット５０に付与する（１０１４）。具体的には、実行したアクセスに関するアクセス要求のパケット５０の返送アドレス５０７の値を参照する。そして、その返送アドレス５０７の値を、作成した応答のパケットに行き先アドレス５０１として付与する。このとき、同様にして、アクセス要求のパケット５０のタグ５０６の値を、応答のパケット５０のタグ５０６として付与する。
【０１９９】
次に、ノード４０は、行き先のノード４０のアドレス（ａ、ｂ）と、自ノード４０のアドレス（Ａ、Ｂ）とを比較する。具体的には、Ａ＝ａかつＢ＝ｂであるか否かを判定する（１０１５）。
【０２００】
ステップ１０１５において、Ａ＝ａかつＢ＝ｂでないと判定された場合、自ノード４０は、行き先のノード４０ではない。このため、当該応答の送信先を決定するために、図１１のステップ１１０１に進む（３）。
【０２０１】
一方、ステップ１０１５において、Ａ＝ａかつＢ＝ｂであると判定された場合、自ノード４０は、行き先のノード４０である。このため、次に、ステップ１０１６に進む。
【０２０２】
ステップ１０１６以降の処理は、既に説明した通りである。
【０２０３】
図１１は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、自ノード４０が行き先のノード４０でない場合に実行される処理のフローチャートである。
【０２０４】
図１０のステップ１０１０において、迂回マーク５０２が付与されていないと判定された場合、又は、図１０のステップ１０１５において、Ａ＝ａかつＢ＝ｂでないと判定された場合（３）、ノード４０は、Ａ＝ａであるか否かを判定する（１１０１）。
【０２０５】
ステップ１１０１において、Ａ＝ａであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ列にある。このため、ノード４０は、要求又は応答を上側又は下側のいずれのノード４０に送信するか決定するために、図１５のステップ１５０１に進む（４）。
【０２０６】
一方、ステップ１１０１において、Ａ＝ａでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ列にない。このため、ノード４０は、Ｂ＝ｂであるか否かを判定する（１１０２）。
【０２０７】
ステップ１１０２において、Ｂ＝ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ行にある。このため、ノード４０は、要求又は応答を右側又は左側のいずれのノード４０に送信するか決定するために、図１６のステップ１６０１に進む（５）。
【０２０８】
一方、ステップ１１０２において、Ｂ＝ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ行又は同じ列のいずれにもない。このため、ノード４０は、探索カウント＞０であるか否かを判定する（１１０３）。
【０２０９】
探索とは、行き先のノード４０に至るリンク４１に障害が発生したときに、他の使用可能なリンク４１を探す動作である。探索カウントは、探索が開始されてから要求又は応答が送信された回数を示す。探索カウント＝０のときは、探索が実行されていない。
【０２１０】
後で説明するように、要求又は応答に逆探索マーク５０３が付与されていない場合、使用可能なリンク４１を反時計回りに探索する。一方、要求又は応答に逆探索マーク５０３が付与されている場合、使用可能なリンク４１を時計回りに探索する。
【０２１１】
例えば、行き先のノード４０（ａ、ｂ）及び自ノード４０（Ａ、Ｂ）の関係が、ａ＝Ａ、ｂ＝Ｂ＋１である場合、行き先のノード４０は、自ノード４０の上側に隣接している。これらのノード４０の間のリンク４１に障害が発生した場合であって逆探索マーク５０３が付与されてない場合、自ノード４０は、要求又は応答を右側に隣接するノード４０に送信する。この要求又は応答を受信したノード４０は、その要求又は応答を上側に隣接するノード４０に送信する。これを受信したノード４０は、行き先のノード４０に右側に隣接しているため、受信した要求又は応答を左側に隣接するノード４０に送信する。この送信が成功すれば、要求又は応答が行き先のノード４０に到達する。この送信が失敗した場合、行き先のノード４０に到達する残りのリンク４１を、反時計回りに探索する。
【０２１２】
また、後で説明するように、要求又は応答が行き先のノード４０に到達しないまま、探索カウントの値が「８」より大きくなった場合、行き先のノード４０に至る全てのリンク４１において、送信が失敗している。この場合、障害が報告され、探索が終了する。
【０２１３】
ステップ１１０３において、探索カウント＞０であると判定された場合、探索が実行されている。この場合、図１３のステップ１３０１に進む（６）。
【０２１４】
一方、ステップ１１０３において、探索カウント＞０でないと判定された場合、探索が実行されていない。このとき、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路は、二つ存在する。この場合、ノード４０は、Ａ＜ａであるか否かを判定する（１１０４）。
【０２１５】
ステップ１１０４において、Ａ＜ａであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側（右上側又は右下側）にある。すなわち、右側に隣接するノード４０（Ａ＋１、Ｂ）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路の一方の上にある。この場合、さらに詳細に行き先のノード４０（ａ、ｂ）の位置を特定するため、図１２のステップ１２０１に進む（７）。
【０２１６】
一方、ステップ１１０４において、Ａ＜ａでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左側（左上側又は左下側）にある。すなわち、左側に隣接するノード４０（Ａ−１、Ｂ）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路の一方の上にある。このため、ノード４０は、左側に隣接するノード４０（Ａ−１、Ｂ）との間の通信量βを測定する（１１０５）。
【０２１７】
次に、ノード４０は、Ｂ＜ｂであるか否かを判定する（１１０６）。
【０２１８】
ステップ１１０６において、Ｂ＜ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側（右上側又は左上側）にある。すなわち、上側に隣接するノード４０（Ａ、Ｂ＋１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路のもう一方の上にある。このため、ノード４０は、上側に隣接するノード４０（Ａ、Ｂ＋１）との間の通信量γを測定する（１１０７）。
【０２１９】
このとき、ステップ１１０４及び１１０６の判定の結果を合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左上側にある。
【０２２０】
すなわち、要求又は応答を自ノード４０の左側に隣接するノード４０（Ａ−１、Ｂ）又は上側に隣接するノード４０（Ａ、Ｂ＋１）のいずれに送信しても、その要求又は応答は、行き先のノード４０に最も近づく。したがって、ノード４０は、要求又は応答を左側に隣接するノード４０又は上側に隣接するノード４０のいずれに送信してもよい。
【０２２１】
しかし、上記の測定された通信量β及びγに差がある場合、通信量が少ない方のノード４０に送信した方が、データ伝送速度が向上する。このため、ノード４０は、通信量を比較して、通信量が少ないほうのノード４０を送信先として選択する。
【０２２２】
ただし、ノード４０又はリンク４１の障害等のため、選択されたノード４０に要求又は応答を送信することができなかった場合、通信量が多い方のノード４０に要求又は応答が送信される。
【０２２３】
なお、行き先のノード４０が自ノード４０の右下側、右上側又は左下側にある場合も、同様にして、通信量の少ない方のノード４０が送信先として選択される。また、障害等のため、選択されたノード４０に要求又は応答を送信することができなかった場合、通信量が多い方のノード４０に要求又は応答が送信される。
【０２２４】
このため、ノード４０は、通信量β＜通信量γであるか否かを判定する（１１０８）。
【０２２５】
ステップ１１０８において、β＜γであると判定された場合、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１１０９）。
【０２２６】
次に、ノード４０は、送信が成功したか否かを判定する（１１１０）。
【０２２７】
ステップ１１１０において、送信が成功したと判定された場合、処理を終了する（１１１１）。
【０２２８】
一方、ステップ１１１０において、送信が成功しなかったと判定された場合、左側に隣接するノード４０（Ａ−１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１１１２）。ノード４０（Ａ、Ｂ＋１）は、ノード４０（Ａ−１、Ｂ）と同様、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にあるためである。
【０２２９】
次に、ノード４０は、送信が成功したか否かを判定する（１１１３）。
【０２３０】
ステップ１１１３において、送信が成功したと判定された場合、処理を終了する（１１１４）。
【０２３１】
一方、ステップ１１１３において、送信が成功しなかったと判定された場合、上側に隣接するノード４０（Ａ、Ｂ＋１）又はそこに至るリンク４１に障害が発生した可能性がある。すなわち、ノード４０は、要求又は応答を行き先のノード４０に近づく方向に送信することができない。送信も２回失敗している二重障害であり、迂回して伝達可能経路を他に探索することは困難である。このため、ノード４０は、伝送不能障害を報告し（１１１５）、処理を終了する（１１１６）。
【０２３２】
なお、伝送不能障害の報告先は、例えば、ストレージシステム全体の障害を管理する障害管理端末（図示省略）である。あるいは、伝送不能障害は、いずれかのホスト計算機又は全てのホスト計算機であってもよい。
【０２３３】
ステップ１１０８において、β＜γでない（すなわち、γがβ以下である）と判定された場合、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１１１７）。
【０２３４】
次に、ノード４０は、送信が成功したか否かを判定する（１１１８）。
【０２３５】
ステップ１１１８において、送信が成功したと判定された場合、処理を終了する（１１１９）。
【０２３６】
一方、ステップ１１１８において、送信が成功しなかったと判定された場合、上側に隣接するノード４０（Ａ、Ｂ＋１）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１１２０）。ノード４０（Ａ−１、Ｂ）は、ノード４０（Ａ、Ｂ＋１）と同様、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にあるためである。
【０２３７】
次に、ノード４０は、送信が成功したか否かを判定する（１１１３）。
【０２３８】
ステップ１１１３において、送信が成功したと判定された場合、処理を終了する（１１１４）。
【０２３９】
一方、ステップ１１１３において、送信が成功しなかったと判定された場合、先と同様に、左側に隣接するノード４０（Ａ−１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。すなわち、ノード４０は、要求又は応答を行き先のノード４０に近づく方向に送信することができない。このため、ノード４０は、伝送不能障害を報告し（１１１５）、処理を終了する（１１１６）。
【０２４０】
ステップ１１０６において、Ｂ＜ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の下側（右下側又は左下側）にある。すなわち、下側に隣接するノード４０（Ａ、Ｂ−１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路のもう一方の上にある。このため、ノード４０は、下側に隣接するノード４０（Ａ、Ｂ−１）との間の通信量δを測定する（１１２１）。
【０２４１】
このとき、ステップ１１０４及び１１０６の判定の結果を合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左下側にある。
【０２４２】
このため、ノード４０は、通信量β＜通信量δであるか否かを判定する（１１２２）。
【０２４３】
ステップ１１２２において、β＜δであると判定された場合、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１１２３）。
【０２４４】
次に、ノード４０は、送信が成功したか否かを判定する（１１２４）。
【０２４５】
ステップ１１２４において、送信が成功したと判定された場合、処理を終了する（１１２５）。
【０２４６】
一方、ステップ１１２４において、送信が成功しなかったと判定された場合、左側に隣接するノード４０（Ａ−１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１１２６）。ノード４０（Ａ、Ｂ−１）は、ノード４０（Ａ−１、Ｂ）と同様、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にあるためである。
【０２４７】
次に、ノード４０は、送信が成功したか否かを判定する（１１１３）。
【０２４８】
ステップ１１１３において、送信が成功したと判定された場合、処理を終了する（１１１４）。
【０２４９】
一方、ステップ１１１３において、送信が成功しなかったと判定された場合、下側に隣接するノード４０（Ａ、Ｂ−１）又はそこに至るリンク４１に障害が発生した可能性がある。すなわち、ノード４０は、要求又は応答を、行き先のノード４０に近づく方向に送信することができない。このため、ノード４０は、伝送不能障害を報告し（１１１５）、処理を終了する（１１１６）。
【０２５０】
ステップ１１２２において、β＜δでない（すなわち、δがβ以下である）と判定された場合、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１１２７）。
【０２５１】
次に、ノード４０は、送信が成功したか否かを判定する（１１２８）。
【０２５２】
ステップ１１２８において、送信が成功したと判定された場合、処理を終了する（１１２９）。
【０２５３】
一方、ステップ１１２８において、送信が成功しなかったと判定された場合、下側に隣接するノード４０（Ａ、Ｂ−１）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１１３０）。ノード４０（Ａ−１、Ｂ）は、ノード４０（Ａ、Ｂ−１）と同様、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にあるためである。
【０２５４】
次に、ノード４０は、送信が成功したか否かを判定する（１１１３）。
【０２５５】
ステップ１１１３において、送信が成功したと判定された場合、処理を終了する（１１１４）。
【０２５６】
一方、ステップ１１１３において、送信が成功しなかったと判定された場合、左側に隣接するノード４０（Ａ−１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。すなわち、ノード４０は、要求又は応答を行き先のノード４０に近づく方向に送信することができない。このため、ノード４０は、伝送不能障害を報告し（１１１５）、処理を終了する（１１１６）。
【０２５７】
図１２は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、行き先のノード４０が自ノード４０の右上側又は右下側にある場合に実行される処理のフローチャートである。
【０２５８】
図１１のステップ１１０４において、Ａ＜ａであると判定された場合（７）、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側（右上側又は右下側）にある。すなわち、右側に隣接するノード４０（Ａ＋１、Ｂ）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路の一方の上にある。このとき、ノード４０は、右側に隣接するノード４０（Ａ＋１、Ｂ）との間の通信量αを測定する（１２０１）。
【０２５９】
次に、ノード４０は、Ｂ＜ｂであるか否かを判定する（１２０２）。
【０２６０】
ステップ１２０２において、Ｂ＜ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側（右上側又は左上側）にある。すなわち、上側に隣接するノード４０（Ａ、Ｂ＋１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路のもう一方の上にある。このため、ノード４０は、上側に隣接するノード４０（Ａ、Ｂ＋１）との間の通信量γを測定する（１２０３）。
【０２６１】
このとき、ステップ１１０４及び１２０２の判定の結果を合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右上側にある。
【０２６２】
次に、ノード４０は、通信量α＜通信量γであるか否かを判定する（１２０４）。
【０２６３】
ステップ１２０４において、α＜γであると判定された場合、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１２０５）。
【０２６４】
次に、ノード４０は、送信が成功したか否かを判定する（１２０６）。
【０２６５】
ステップ１２０６において、送信が成功したと判定された場合、処理を終了する（１２０７）。
【０２６６】
一方、ステップ１２０６において、送信が成功しなかったと判定された場合、右側に隣接するノード４０（Ａ＋１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１２０８）。ノード４０（Ａ、Ｂ＋１）は、ノード４０（Ａ＋１、Ｂ）と同様、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にあるためである。
【０２６７】
次に、ノード４０は、送信が成功したか否かを判定する（１２０９）。
【０２６８】
ステップ１２０９において、送信が成功したと判定された場合、処理を終了する（１２１０）。
【０２６９】
一方、ステップ１２０９において、送信が成功しなかったと判定された場合、上側に隣接するノード４０（Ａ、Ｂ＋１）又はそこに至るリンク４１に障害が発生した可能性がある。すなわち、ノード４０は、要求又は応答を行き先のノード４０に近づく方向に送信することができない。このため、ノード４０は、伝送不能障害を報告し（１２１１）、処理を終了する（１２１２）。
【０２７０】
ステップ１２０４において、α＜γでない（すなわち、γがα以下である）と判定された場合、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１２１３）。
【０２７１】
次に、ノード４０は、送信が成功したか否かを判定する（１２１４）。
【０２７２】
ステップ１２１４において、送信が成功したと判定された場合、処理を終了する（１２１５）。
【０２７３】
一方、ステップ１２１４において、送信が成功しなかったと判定された場合、上側に隣接するノード４０（Ａ、Ｂ＋１）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１２１６）。ノード４０（Ａ＋１、Ｂ）は、ノード４０（Ａ、Ｂ＋１）と同様、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にあるためである。
【０２７４】
次に、ノード４０は、送信が成功したか否かを判定する（１２０９）。
【０２７５】
ステップ１２０９において、送信が成功したと判定された場合、処理を終了する（１２１０）。
【０２７６】
一方、ステップ１２０９において、送信が成功しなかったと判定された場合、右側に隣接するノード４０（Ａ＋１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。すなわち、ノード４０は、要求又は応答を行き先のノード４０に近づく方向に送信することができない。このため、ノード４０は、伝送不能障害を報告し（１２１１）、処理を終了する（１２１２）。
【０２７７】
ステップ１２０２において、Ｂ＜ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の下側（右下側又は左下側）にある。すなわち、下側に隣接するノード４０（Ａ、Ｂ−１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二つの最短経路のもう一方の上にある。このため、ノード４０は、下側に隣接するノード４０（Ａ、Ｂ−１）との間の通信量δを測定する（１２１７）。
【０２７８】
このとき、ステップ１１０４及び１２０２の判定の結果を合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右下側にある。
【０２７９】
このため、ノード４０は、通信量α＜通信量δであるか否かを判定する（１２１８）。
【０２８０】
ステップ１２１８において、α＜δであると判定された場合、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１２１９）。
【０２８１】
次に、ノード４０は、送信が成功したか否かを判定する（１２２０）。
【０２８２】
ステップ１２２０において、送信が成功したと判定された場合、処理を終了する（１２２１）。
【０２８３】
一方、ステップ１１２４において、送信が成功しなかったと判定された場合、右側に隣接するノード４０（Ａ＋１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１２２２）。ノード４０（Ａ、Ｂ−１）は、ノード４０（Ａ＋１、Ｂ）と同様、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にあるためである。
【０２８４】
次に、ノード４０は、送信が成功したか否かを判定する（１２０９）。
【０２８５】
ステップ１２０９において、送信が成功したと判定された場合、処理を終了する（１２１０）。
【０２８６】
一方、ステップ１２０９において、送信が成功しなかったと判定された場合、下側に隣接するノード４０（Ａ、Ｂ−１）又はそこに至るリンク４１に障害が発生した可能性がある。すなわち、ノード４０は、要求又は応答を行き先のノード４０に近づく方向に送信することができない。このため、ノード４０は、伝送不能障害を報告し（１２１１）、処理を終了する（１２１２）。
【０２８７】
ステップ１２１８において、α＜δでない（すなわち、δがα以下である）と判定された場合、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１２２３）。
【０２８８】
次に、ノード４０は、送信が成功したか否かを判定する（１２２４）。
【０２８９】
ステップ１２２４において、送信が成功したと判定された場合、処理を終了する（１２２５）。
【０２９０】
一方、ステップ１２２４において、送信が成功しなかったと判定された場合、下側に隣接するノード４０（Ａ、Ｂ−１）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１２２６）。ノード４０（Ａ＋１、Ｂ）は、ノード４０（Ａ、Ｂ−１）と同様、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にあるためである。
【０２９１】
次に、ノード４０は、送信が成功したか否かを判定する（１２０９）。
【０２９２】
ステップ１２０９において、送信が成功したと判定された場合、処理を終了する（１２１０）。
【０２９３】
一方、ステップ１２０９において、送信が成功しなかったと判定された場合、右側に隣接するノード４０（Ａ＋１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。すなわち、ノード４０は、要求又は応答を行き先のノード４０に近づく方向に送信することができない。このため、ノード４０は、伝送不能障害を報告し（１２１１）、処理を終了する（１２１２）。
【０２９４】
図１３は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて実行される探索の処理のフローチャートである。
【０２９５】
図１１のステップ１１０３において、探索カウント＞０であると判定された場合（６）、探索が実行されている。この場合、ノード４０は、探索カウントの値を「１」増加させる（１３０１）。
【０２９６】
次に、ノード４０は、Ａ＜ａであるか否かを判定する（１３０２）。
【０２９７】
ステップ１３０２において、Ａ＜ａであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側（右上側又は右下側）にある。この場合、図１４のステップ１４０１に進む（８）。
【０２９８】
一方、ステップ１３０２において、Ａ＜ａでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左側（左上側又は左下側）にある。このため、ノード４０は、Ｂ＜ｂであるか否かを判定する（１３０３）。
【０２９９】
Ｂ＜ｂである場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側（右上側又は左上側）にある。すなわち、ステップ１３０３においてＢ＜ｂであると判定された場合、ステップ１３０２の判定の結果と合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左上側にある。
【０３００】
次に、ノード４０は、要求又は応答に逆探索マーク５０３が付与されているか否かを判定する（１３０４）。具体的には、受信したアクセス要求又は応答のパケット５０の逆探索マーク５０３の値が有効になっているか否かを判定する。
【０３０１】
逆探索マーク５０３とは、探索の方向を指定する標識である。要求又は応答に逆探索マーク５０３が付与されていない場合、ノード４０は、行き先のノード４０に至る使用可能なリンク４１を反時計回りに探索するように要求又は応答を送信する。一方、要求又は応答に逆探索マーク５０３が付与されている場合、ノード４０は、行き先のノード４０に至る使用可能なリンク４１を時計回りに探索するように要求又は応答を送信する。
【０３０２】
なお、逆探索マーク５０３は、探索が開始された時点では付与されていない。反時計回りに探索する過程で、リンク４１等の障害のためそれ以上の探索ができなくなった場合に、逆探索マーク５０３が付与され、時計回りの探索が開始される。
【０３０３】
ステップ１３０４において、逆探索マーク５０３が付与されていないと判定された場合、反時計回りの探索が実行されている。このため、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１３０５）。行き先のノード４０が自ノード４０の左上側に位置するため、要求又は応答は、行き先のノード４０を反時計回りに周回する方向に送信される。
【０３０４】
次に、ノード４０は、送信が成功したか否かを判定する（１３０６）。
【０３０５】
ステップ１３０６において、送信が成功したと判定された場合、処理を終了する（１３０７）。
【０３０６】
一方、ステップ１３０７において、送信が成功しなかったと判定された場合、上側に隣接するノード４０（Ａ、Ｂ＋１）又はそこに至るリンク４１に障害が発生した可能性がある。したがって、ノード４０は、それ以上反時計回りの探索をすることができない。そこで、ノード４０は、探索カウントの値を「１」とし、逆探索マーク５０３を付与して（１３０８）、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１３０９）。行き先のノード４０が自ノード４０の左上側に位置するため、要求又は応答は、行き先のノード４０を時計回りに周回する方向に送信される。このように、時計回りの探索が開始される。
【０３０７】
ステップ１３０４において、逆探索マーク５０３が付与されていると判定された場合、時計回りの探索が実行されている。このため、ノード４０は、ステップ１３０５からステップ１３０８までを実行せず、ステップ１３０９を実行する。
【０３０８】
次に、ノード４０は、送信が成功したか否かを判定する（１３１０）。
【０３０９】
ステップ１３１０において、送信が成功したと判定された場合、処理を終了する（１３１１）。
【０３１０】
一方、ステップ１３１０において、送信が成功しなかったと判定された場合、反時計回り又は時計回りのいずれの方向の探索も、それ以上することができない。このため、ノード４０は、伝送不能障害を報告し（１３１２）、処理を終了する（１３１３）。
【０３１１】
ステップ１３０３において、Ｂ＜ｂでないと判定された場合、ステップ１３０２の判定の結果と合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左下側にある。
【０３１２】
次に、ノード４０は、要求又は応答に逆探索マーク５０３が付与されているか否かを判定する（１３１４）。具体的には、受信したアクセス要求又は応答のパケット５０の逆探索マーク５０３の値が有効になっているか否かを判定する。
【０３１３】
ステップ１３１４において、逆探索マーク５０３が付与されていないと判定された場合、反時計回りの探索が実行されている。このため、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１３１５）。行き先のノード４０が自ノード４０の左下側に位置するため、要求又は応答は、行き先のノード４０を反時計回りに周回する方向に送信される。
【０３１４】
次に、ノード４０は、送信が成功したか否かを判定する（１３１６）。
【０３１５】
ステップ１３１６において、送信が成功したと判定された場合、処理を終了する（１３１７）。
【０３１６】
一方、ステップ１３１６において、送信が成功しなかったと判定された場合、左側に隣接するノード４０（Ａ−１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。したがって、ノード４０は、それ以上反時計回りの探索をすることができない。そこで、ノード４０は、探索カウントの値を「１」とし、逆探索マーク５０３を付与して（１３１８）、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１３１９）。行き先のノード４０が自ノード４０の左下側に位置するため、要求又は応答は、行き先のノード４０を時計回りに周回する方向に送信される。このように、時計回りの探索が開始される。
【０３１７】
ステップ１３１４において、逆探索マーク５０３が付与されていると判定された場合、時計回りの探索が実行されている。このため、ノード４０は、ステップ１３１５からステップ１３１８までを実行せず、ステップ１３１９を実行する。
【０３１８】
次に、ノード４０は、送信が成功したか否かを判定する（１３１０）。以後、上記の説明の通り、ステップ１３１０からステップ１３１３までを実行する。
【０３１９】
図１４は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて実行される探索の処理のうち、行き先のノード４０（ａ、ｂ）が自ノード４０（Ａ、Ｂ）の右上側又は右下側にある場合に実行される処理のフローチャートである。
【０３２０】
図１３のステップ１３０２において、Ａ＜ａであると判定された場合（８）、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側（右上側又は右下側）にある。この場合、ノード４０は、Ｂ＜ｂであるか否かを判定する（１４０１）。
【０３２１】
Ｂ＜ｂである場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側（右上側又は左上側）にある。すなわち、ステップ１４０１においてＢ＜ｂであると判定された場合、ステップ１３０２の判定の結果と合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右上側にある。
【０３２２】
次に、ノード４０は、要求又は応答に逆探索マーク５０３が付与されているか否かを判定する（１４０２）。具体的には、受信したアクセス要求又は応答のパケット５０の逆探索マーク５０３の値が有効になっているか否かを判定する。
【０３２３】
ステップ１４０２において、逆探索マーク５０３が付与されていないと判定された場合、反時計回りの探索が実行されている。このため、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１４０３）。行き先のノード４０が自ノード４０の右上側に位置するため、要求又は応答は、行き先のノード４０を反時計回りに周回する方向に送信される。
【０３２４】
次に、ノード４０は、送信が成功したか否かを判定する（１４０４）。
【０３２５】
ステップ１４０４において、送信が成功したと判定された場合、処理を終了する（１４０５）。
【０３２６】
一方、ステップ１４０４において、送信が成功しなかったと判定された場合、右側に隣接するノード４０（Ａ＋１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。したがって、ノード４０は、それ以上反時計回りの探索をすることができない。そこで、ノード４０は、探索カウントの値を「１」とし、逆探索マーク５０３を付与して（１４０６）、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１４０７）。行き先のノード４０が自ノード４０の右上側に位置するため、要求又は応答は、行き先のノード４０を時計回りに周回する方向に送信される。このようにして、時計回りの探索が開始される。
【０３２７】
ステップ１４０２において、逆探索マーク５０３が付与されていると判定された場合、時計回りの探索が実行されている。このため、ノード４０は、ステップ１４０３からステップ１４０６までを実行せず、ステップ１４０７を実行する。
【０３２８】
次に、ノード４０は、送信が成功したか否かを判定する（１４０８）。
【０３２９】
ステップ１４０８において、送信が成功したと判定された場合、処理を終了する（１４０９）。
【０３３０】
一方、ステップ１４０８において、送信が成功しなかったと判定された場合、反時計回り又は時計回りのいずれの方向の探索も、それ以上することができない。このため、ノード４０は、伝送不能障害を報告し（１４１０）、処理を終了する（１４１１）。
【０３３１】
ステップ１４０１において、Ｂ＜ｂでないと判定された場合、ステップ１３０２の判定の結果と合わせると、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右下側にある。
【０３３２】
次に、ノード４０は、要求又は応答に逆探索マーク５０３が付与されているか否かを判定する（１４１２）。具体的には、受信したアクセス要求又は応答のパケット５０の逆探索マーク５０３の値が有効になっているか否かを判定する。
【０３３３】
ステップ１４１２において、逆探索マーク５０３が付与されていないと判定された場合、反時計回りの探索が実行されている。このため、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１４１３）。行き先のノード４０が自ノード４０の右下側に位置するため、要求又は応答は、行き先のノード４０を反時計回りに周回する方向に送信される。
【０３３４】
次に、ノード４０は、送信が成功したか否かを判定する（１４１４）。
【０３３５】
ステップ１４１４において、送信が成功したと判定された場合、処理を終了する（１４１５）。
【０３３６】
一方、ステップ１４１４において、送信が成功しなかったと判定された場合、下側に隣接するノード４０（Ａ、Ｂ−１）又はそこに至るリンク４１に障害が発生した可能性がある。したがって、ノード４０は、それ以上反時計回りの探索をすることができない。そこで、ノード４０は、探索カウントの値を「１」とし、逆探索マーク５０３を付与して（１４１６）、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１４１７）。行き先のノード４０が自ノード４０の右下側に位置するため、要求又は応答は、行き先のノード４０を時計回りに周回する方向に送信される。このように、時計回りの探索が開始される。
【０３３７】
ステップ１４１２において、逆探索マーク５０３が付与されていると判定された場合、時計回りの探索が実行されている。このため、ノード４０は、ステップ１４１３からステップ１４１６までを実行せず、ステップ１４１７を実行する。
【０３３８】
次に、ノード４０は、送信が成功したか否かを判定する（１４０８）。以後、上記の説明の通り、ステップ１４０８からステップ１４１１までを実行する。
【０３３９】
図１５は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、行き先のノード４０（ａ、ｂ）が自ノード４０（Ａ、Ｂ）と同じ列にある場合に実行される処理のフローチャートである。
【０３４０】
図１１のステップ１１０１において、Ａ＝ａであると判定された場合（４）、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ列にある。この場合、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路は、一つのみ存在する。ノード４０は、要求又は応答を上側又は下側のいずれのノード４０に送信するか決定するために、Ｂ＜ｂであるか否かを判定する（１５０１）。
【０３４１】
ステップ１５０１において、Ｂ＜ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側にある。この場合、上側に隣接するノード４０（Ａ、Ｂ＋１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にある。このため、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１５０２）。
【０３４２】
次に、ノード４０は、送信が成功したか否かを判定する（１５０３）。
【０３４３】
ステップ１５０３において、送信が成功したと判定された場合、処理を終了する（１５０４）。
【０３４４】
一方、ステップ１５０３において、送信が成功しなかったと判定された場合、上側に隣接するノード４０（Ａ、Ｂ＋１）又はそこに至るリンク４１に障害が発生した可能性がある。この場合、ノード４０は、Ｂ＋１＝ｂであるか否かを判定する（１５０５）。
【０３４５】
ステップ１５０５において、Ｂ＋１＝ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側に隣接する。この場合、行き先のノード４０に至る他のリンク４１を探索するために、図１７のステップ１７０１に進む（９）。
【０３４６】
一方、ステップ１５０５において、Ｂ＋１＝ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側にあるが、隣接しない。この場合、ノード４０は、障害が発生したノード４０又はリンク４１を迂回して要求又は応答を送信するため、ステップ１５２２に進む。
【０３４７】
ステップ１５０１において、Ｂ＜ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の下側にある。この場合、下側に隣接するノード４０（Ａ、Ｂ−１）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にある。このため、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１５０６）。
【０３４８】
次に、ノード４０は、送信が成功したか否かを判定する（１５０７）。
【０３４９】
ステップ１５０７において、送信が成功したと判定された場合、処理を終了する（１５０８）。
【０３５０】
一方、ステップ１５０７において、送信が成功しなかったと判定された場合、下側に隣接するノード４０（Ａ、Ｂ−１）又はそこに至るリンク４１に障害が発生した可能性がある。この場合、ノード４０は、Ｂ−１＝ｂであるか否かを判定する（１５０９）。
【０３５１】
ステップ１５０９において、Ｂ−１＝ｂであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の下側に隣接する。この場合、ノード４０は、行き先のノード４０に至る他のリンク４１を探索するために、探索カウントの値を１増加させる（１５１０）。
【０３５２】
次に、ノード４０は、探索カウントの値が８より大きいか否かを判定する（１５１１）。
【０３５３】
ステップ１５１１において、探索カウントの値が８より大きいと判定された場合、行き先のノード４０（ａ、ｂ）に至る全てのリンク４１において送信が失敗している。このため、伝送不能障害を報告して（１５２０）、処理を終了する（１５２１）。
【０３５４】
一方、ステップ１５１１において、探索カウントの値が８より大きくないと判定された場合、行き先のノード４０（ａ、ｂ）に至る送信可能なリンク４１が残っている可能性がある。このため、ノード４０は、要求又は応答に逆探索マーク５０３が付与されているか否かを判定する（１５１２）。
【０３５５】
ステップ１５１２において、逆探索マーク５０３が付与されていないと判定された場合、反時計回りの探索が実行されている。このため、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１５１３）。行き先のノード４０が自ノード４０の下側に隣接するため、要求又は応答は、行き先のノード４０を反時計回りに周回する方向に送信される。
【０３５６】
次に、ノード４０は、送信が成功したか否かを判定する（１５１４）。
【０３５７】
ステップ１５１４において、送信が成功したと判定された場合、処理を終了する（１５１５）。
【０３５８】
一方、ステップ１５１４において、送信が成功しなかったと判定された場合、左側に隣接するノード４０（Ａ−１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。したがって、ノード４０は、それ以上反時計回りの探索をすることができない。そこで、ノード４０は、探索カウントの値を「１」とし、逆探索マーク５０３を付与して（１５１６）、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１５１７）。行き先のノード４０が自ノード４０の下側に隣接するため、要求又は応答は、行き先のノード４０を時計回りに周回する方向に送信される。このようにして、時計回りの探索が開始される。
【０３５９】
ノード４０（Ａ−１、Ｂ）及びノード４０（Ａ＋１、Ｂ）は、共に、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二番目に短い経路（すなわち、最短経路の次に短い経路）上にある。
【０３６０】
ステップ１５１２において、逆探索マーク５０３が付与されていると判定された場合、時計回りの探索が実行されている。このため、ノード４０は、ステップ１５１３からステップ１５１６までを実行せず、ステップ１５１７を実行する。
【０３６１】
次に、ノード４０は、送信が成功したか否かを判定する（１５１８）。
【０３６２】
ステップ１５１８において、送信が成功したと判定された場合、処理を終了する（１５１９）。
【０３６３】
一方、ステップ１５１８において、送信が成功しなかったと判定された場合、反時計回り又は時計回りのいずれの方向の探索も、それ以上することができない。このため、ノード４０は、伝送不能障害を報告し（１５２０）、処理を終了する（１５２１）。
【０３６４】
ステップ１５０９においてＢ−１＝ｂでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の下側にあるが、隣接しない。この場合、ノード４０は、障害が発生したノード４０又はリンク４１を迂回して要求又は応答を送信する。ステップ１５０５においてＢ＋１＝ｂでないと判定された場合も同様である。
【０３６５】
迂回とは、行き先のノード４０が自ノード４０と同じ列又は同じ行にあり、かつ、自ノード４０と隣接しない場合であって、自ノード４０と行き先のノード４０との間のノード４０又はリンク４１に障害が発生した場合に、その障害を避けるために、自ノード４０から行き先のノード４０に至る二番目に短い経路上のノード４０に要求又は応答を送信する処理である。この場合、ノード４０は、自ノード４０から行き先のノード４０に至る最短経路上のノード４０にパケット５０を送信することができないためである。例えば、行き先のノード４０が自ノード４０と同じ列の上側にあり、かつ、自ノード４０と隣接しない場合であって、自ノード４０の上側に隣接するノード４０に障害が発生した場合、迂回が開始される。
【０３６６】
ステップ１５０９においてＢ−１＝ｂでないと判定された場合、及び、ステップ１５０５においてＢ＋１＝ｂでないと判定された場合、自ノード４０の右側に隣接するノード４０（Ａ＋１、Ｂ）及び自ノード４０の左側に隣接するノード４０（Ａ−１、Ｂ）は、自ノード４０から行き先のノード４０に至る二番目に短い経路上にある。したがって、要求又は応答のパケット５０は、自ノード４０の右側又は左側に隣接するノード４０に送信される。パケット５０は、これらのうちいずれのノード４０に送信されてもよいが、例えば、通信量が少ない方に送信される。このとき、パケット５０に迂回マーク５０２が付与される。右側又は左側に隣接するノード４０は、次に、受信したパケット５０を上側に隣接するノード４０に送信する。このとき、迂回マーク５０２が消去され、迂回が終了する。
【０３６７】
ノード４０は、まず、要求又は応答に迂回マーク５０２を付与する（１５２２）。具体的には、ノード４０は、要求又は応答のパケット５０の迂回マーク５０２の値を有効にする。
【０３６８】
ノード４０は、次に、自ノード４０（Ａ、Ｂ）と右側に隣接するノード４０（Ａ＋１、Ｂ）との間の通信量αを計測する（１５２３）。
【０３６９】
次に、ノード４０は、自ノード４０（Ａ、Ｂ）と左側に隣接するノード４０（Ａ−１、Ｂ）との間の通信量βを計測する（１５２４）。
【０３７０】
ノード４０（Ａ＋１、Ｂ）及びノード４０（Ａ−１、Ｂ）は、共に、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二番目に短い経路上にある。
【０３７１】
次に、ノード４０は、通信量αが通信量βより小さいか否かを判定する（１５２５）。
【０３７２】
ステップ１５２５において、通信量αが通信量βより小さいと判定された場合、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１５２６）。
【０３７３】
次に、ノード４０は、送信が成功したか否かを判定する（１５２７）。
【０３７４】
ステップ１５２７において、送信が成功したと判定された場合、処理を終了する（１５２８）。
【０３７５】
一方、ステップ１５２７において、送信が成功しなかったと判定された場合、右側に隣接するノード４０（Ａ＋１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１５２９）。
【０３７６】
次に、ノード４０は、送信が成功したか否かを判定する（１５１８）。ステップ１５１８以降の処理は、上記で説明した通りである。
【０３７７】
ステップ１５２５において、通信量αが通信量βより小さくないと判定された場合、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１５３０）。
【０３７８】
次に、ノード４０は、送信が成功したか否かを判定する（１５３１）。
【０３７９】
ステップ１５３１において、送信が成功したと判定された場合、処理を終了する（１５３２）。
【０３８０】
一方、ステップ１５３１において、送信が成功しなかったと判定された場合、左側に隣接するノード４０（Ａ−１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１５３３）。
【０３８１】
次に、ノード４０は、送信が成功したか否かを判定する（１５１８）。ステップ１５１８以降の処理は、上記で説明した通りである。
【０３８２】
図１６は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、行き先のノード４０（ａ、ｂ）が自ノード４０（Ａ、Ｂ）と同じ行にある場合に実行される処理のフローチャートである。
【０３８３】
図１１のステップ１１０２において、Ｂ＝ｂであると判定された場合（５）、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）と同じ行にある。この場合、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路は、一つのみ存在する。ノード４０は、要求又は応答を右側又は左側のいずれのノード４０に送信するか決定するために、Ａ＜ａであるか否かを判定する（１６０１）。
【０３８４】
ステップ１６０１において、Ａ＜ａであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側にある。この場合、右側に隣接するノード４０（Ａ＋１、Ｂ）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にある。このため、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１６０２）。
【０３８５】
次に、ノード４０は、送信が成功したか否かを判定する（１６０３）。
【０３８６】
ステップ１６０３において、送信が成功したと判定された場合、処理を終了する（１６０４）。
【０３８７】
一方、ステップ１６０３において、送信が成功しなかったと判定された場合、右側に隣接するノード４０（Ａ＋１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。この場合、ノード４０は、Ａ＋１＝ａであるか否かを判定する（１６０５）。
【０３８８】
ステップ１６０５において、Ａ＋１＝ａであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側に隣接する。この場合、行き先のノード４０に至る他のリンク４１を探索するために、図１７のステップ１７１３に進む（１０）。
【０３８９】
一方、ステップ１６０５において、Ａ＋１＝ａでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側にあるが、隣接しない。この場合、ノード４０は、障害が発生したノード４０又はリンク４１を迂回して要求又は応答を送信するため、ステップ１６２２に進む。
【０３９０】
ステップ１６０１において、Ａ＜ａでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左側にある。この場合、左側に隣接するノード４０（Ａ−１、Ｂ）は、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る最短経路上にある。このため、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１６０６）。
【０３９１】
次に、ノード４０は、送信が成功したか否かを判定する（１６０７）。
【０３９２】
ステップ１６０７において、送信が成功したと判定された場合、処理を終了する（１６０８）。
【０３９３】
一方、ステップ１６０７において、送信が成功しなかったと判定された場合、左側に隣接するノード４０（Ａ−１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。この場合、ノード４０は、Ａ−１＝ａであるか否かを判定する（１６０９）。
【０３９４】
ステップ１６０９において、Ａ−１＝ａであると判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左側に隣接する。この場合、ノード４０は、行き先のノード４０に至る他のリンク４１を探索するために、探索カウントの値を１増加させる（１６１０）。
【０３９５】
次に、ノード４０は、探索カウントの値が８より大きいか否かを判定する（１６１１）。
【０３９６】
ステップ１６１１において、探索カウントの値が８より大きいと判定された場合、行き先のノード４０（ａ、ｂ）に至る全てのリンク４１において送信が失敗している。このため、伝送不能障害を報告して（１６２０）、処理を終了する（１６２１）。
【０３９７】
一方、ステップ１６１１において、探索カウントの値が８より大きくないと判定された場合、行き先のノード４０（ａ、ｂ）に至る送信可能なリンク４１が残っている可能性がある。このため、ノード４０は、要求又は応答に逆探索マーク５０３が付与されているか否かを判定する（１６１２）。
【０３９８】
ステップ１６１２において、逆探索マーク５０３が付与されていないと判定された場合、反時計回りの探索が実行されている。このため、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１６１３）。行き先のノード４０が自ノード４０の左側に隣接するため、要求又は応答は、行き先のノード４０を反時計回りに周回する方向に送信される。
【０３９９】
次に、ノード４０は、送信が成功したか否かを判定する（１６１４）。
【０４００】
ステップ１６１４において、送信が成功したと判定された場合、処理を終了する（１６１５）。
【０４０１】
一方、ステップ１６１４において、送信が成功しなかったと判定された場合、上側に隣接するノード４０（Ａ、Ｂ＋１）又はそこに至るリンク４１に障害が発生した可能性がある。したがって、ノード４０は、それ以上反時計回りの探索をすることができない。そこで、ノード４０は、探索カウントの値を「１」とし、逆探索マーク５０３を付与して（１６１６）、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１６１７）。行き先のノード４０が自ノード４０の左側に隣接するため、要求又は応答は、行き先のノード４０を時計回りに周回する方向に送信される。このようにして、時計回りの探索が開始される。
【０４０２】
ノード４０（Ａ、Ｂ＋１）及びノード４０（Ａ、Ｂ−１）は、共に、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二番目に短い経路上にある。
【０４０３】
ステップ１６１２において、逆探索マーク５０３が付与されていると判定された場合、時計回りの探索が実行されている。このため、ノード４０は、ステップ１６１３からステップ１６１６までを実行せず、ステップ１６１７を実行する。
【０４０４】
次に、ノード４０は、送信が成功したか否かを判定する（１６１８）。
【０４０５】
ステップ１６１８において、送信が成功したと判定された場合、処理を終了する（１６１９）。
【０４０６】
一方、ステップ１６１８において、送信が成功しなかったと判定された場合、反時計回り又は時計回りのいずれの方向の探索も、それ以上することができない。このため、ノード４０は、伝送不能障害を報告し（１６２０）、処理を終了する（１６２１）。
【０４０７】
ステップ１６０９においてＡ−１＝ａでないと判定された場合、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の左側にあるが、隣接しない。この場合、ノード４０は、障害が発生したノード４０又はリンク４１を迂回して要求又は応答を送信する。ステップ１６０５においてＡ＋１＝ａでないと判定された場合も同様である。
【０４０８】
ステップ１６０９においてＡ−１＝ａでないと判定された場合、及び、ステップ１６０５においてＡ＋１＝ａでないと判定された場合、自ノード４０の上側に隣接するノード４０（Ａ、Ｂ＋１）及び自ノード４０の下側に隣接するノード４０（Ａ、Ｂ−１）は、自ノード４０から行き先のノード４０に至る二番目に短い経路上にある。したがって、要求又は応答のパケット５０は、自ノード４０の上側又は下側に隣接するノード４０に送信される。
【０４０９】
ノード４０は、まず、要求又は応答に迂回マーク５０２を付与する（１６２２）。具体的には、ノード４０は、要求又は応答のパケット５０の迂回マーク５０２の値を有効にする。
【０４１０】
次に、ノード４０は、自ノード４０（Ａ、Ｂ）と上側に隣接するノード４０（Ａ、Ｂ＋１）との間の通信量γを計測する（１６２３）。
【０４１１】
次に、ノード４０は、自ノード４０（Ａ、Ｂ）と下側に隣接するノード４０（Ａ、Ｂ−１）との間の通信量δを計測する（１６２４）。
【０４１２】
ノード４０（Ａ、Ｂ＋１）及びノード４０（Ａ、Ｂ−１）は、共に、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二番目に短い経路上にある。
【０４１３】
次に、ノード４０は、通信量γが通信量δより小さいか否かを判定する（１６２５）。
【０４１４】
ステップ１６２５において、通信量γが通信量δより小さいと判定された場合、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１６２６）。
【０４１５】
次に、ノード４０は、送信が成功したか否かを判定する（１６２７）。
【０４１６】
ステップ１６２７において、送信が成功したと判定された場合、処理を終了する（１６２８）。
【０４１７】
一方、ステップ１６２７において、送信が成功しなかったと判定された場合、右側に隣接するノード４０（Ａ、Ｂ＋１）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１６２９）。
【０４１８】
次に、ノード４０は、送信が成功したか否かを判定する（１６１８）。ステップ１６１８以降の処理は、上記で説明した通りである。
【０４１９】
ステップ１６２５において、通信量γが通信量δより小さくないと判定された場合、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１６３０）。
【０４２０】
次に、ノード４０は、送信が成功したか否かを判定する（１６３１）。
【０４２１】
ステップ１６３１において、送信が成功したと判定された場合、処理を終了する（１６３２）。
【０４２２】
一方、ステップ１６３１において、送信が成功しなかったと判定された場合、下側に隣接するノード４０（Ａ、Ｂ−１）又はそこに至るリンク４１に障害が発生した可能性がある。このため、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１６３３）。
【０４２３】
次に、ノード４０は、送信が成功したか否かを判定する（１６１８）。ステップ１６１８以降の処理は、上記で説明した通りである。
【０４２４】
図１７は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、行き先のノード４０（ａ、ｂ）が自ノード４０（Ａ、Ｂ）と同じ行又は同じ列にある場合に実行される探索の処理のフローチャートである。
【０４２５】
図１５のステップ１５０５において、Ｂ＋１＝ｂであると判定された場合（９）、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の上側に隣接する。この場合、ノード４０は、行き先のノード４０に至る他のリンク４１を探索するために、探索カウントの値を１増加させる（１７０１）。
【０４２６】
次に、ノード４０は、探索カウントの値が８より大きいか否かを判定する（１７０２）。
【０４２７】
ステップ１７０２において、探索カウントの値が８より大きいと判定された場合、行き先のノード４０（ａ、ｂ）に至る全てのリンク４１において送信が失敗している。このため、伝送不能障害を報告して（１７１１）、処理を終了する（１７１２）。
【０４２８】
一方、ステップ１７０２において、探索カウントの値が８より大きくないと判定された場合、行き先のノード４０（ａ、ｂ）に至る送信可能なリンク４１が残っている可能性がある。このため、ノード４０は、要求又は応答に逆探索マーク５０３が付与されているか否かを判定する（１７０３）。
【０４２９】
ステップ１７０３において、逆探索マーク５０３が付与されていないと判定された場合、反時計回りの探索が実行されている。このため、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１７０４）。行き先のノード４０が自ノード４０の上側に隣接するため、要求又は応答は、行き先のノード４０を反時計回りに周回する方向に送信される。
【０４３０】
次に、ノード４０は、送信が成功したか否かを判定する（１７０５）。
【０４３１】
ステップ１７０５において、送信が成功したと判定された場合、処理を終了する（１７０６）。
【０４３２】
一方、ステップ１７０５において、送信が成功しなかったと判定された場合、右側に隣接するノード４０（Ａ＋１、Ｂ）又はそこに至るリンク４１に障害が発生した可能性がある。したがって、ノード４０は、それ以上反時計回りの探索をすることができない。そこで、ノード４０は、探索カウントの値を「１」とし、逆探索マーク５０３を付与して（１７０７）、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１７０８）。行き先のノード４０が自ノード４０の上側に隣接するため、要求又は応答は、行き先のノード４０を時計回りに周回する方向に送信される。このようにして、時計回りの探索が開始される。
【０４３３】
ノード４０（Ａ＋１、Ｂ）及びノード４０（Ａ−１、Ｂ）は、共に、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二番目に短い経路上にある。
【０４３４】
ステップ１７０３において、逆探索マーク５０３が付与されていると判定された場合、時計回りの探索が実行されている。このため、ノード４０は、ステップ１７０４からステップ１７０７までを実行せず、ステップ１７０８を実行する。
【０４３５】
次に、ノード４０は、送信が成功したか否かを判定する（１７０９）。
【０４３６】
ステップ１７０９において、送信が成功したと判定された場合、処理を終了する（１７１０）。
【０４３７】
一方、ステップ１７０９において、送信が成功しなかったと判定された場合、反時計回り又は時計回りのいずれの方向の探索も、それ以上することができない。このため、ノード４０は、伝送不能障害を報告し（１７１１）、処理を終了する（１７１２）。
【０４３８】
図１６のステップ１６０５において、Ａ＋１＝ａであると判定された場合（１０）、行き先のノード４０（ａ、ｂ）は、自ノード４０（Ａ、Ｂ）の右側に隣接する。この場合、ノード４０は、行き先のノード４０に至る他のリンク４１を探索するために、探索カウントの値を１増加させる（１７１３）。
【０４３９】
次に、ノード４０は、探索カウントの値が８より大きいか否かを判定する（１７１４）。
【０４４０】
ステップ１７１４において、探索カウントの値が８より大きいと判定された場合、行き先のノード４０（ａ、ｂ）に至る全てのリンク４１において送信が失敗している。このため、伝送不能障害を報告して（１７１１）、処理を終了する（１７１２）。
【０４４１】
一方、ステップ１７１４において、探索カウントの値が８より大きくないと判定された場合、行き先のノード４０（ａ、ｂ）に至る送信可能なリンク４１が残っている可能性がある。このため、ノード４０は、要求又は応答に逆探索マーク５０３が付与されているか否かを判定する（１７１５）。
【０４４２】
ステップ１７１５において、逆探索マーク５０３が付与されていないと判定された場合、反時計回りの探索が実行されている。このため、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１７１６）。行き先のノード４０が自ノード４０の右側に隣接するため、要求又は応答は、行き先のノード４０を反時計回りに周回する方向に送信される。
【０４４３】
次に、ノード４０は、送信が成功したか否かを判定する（１７１７）。
【０４４４】
ステップ１７１７において、送信が成功したと判定された場合、処理を終了する（１７１８）。
【０４４５】
一方、ステップ１７１７において、送信が成功しなかったと判定された場合、下側に隣接するノード４０（Ａ、Ｂ−１）又はそこに至るリンク４１に障害が発生した可能性がある。したがって、ノード４０は、それ以上反時計回りの探索をすることができない。そこで、ノード４０は、探索カウントの値を「１」とし、逆探索マーク５０３を付与して（１７１９）、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１７２０）。行き先のノード４０が自ノード４０の右側に隣接するため、要求又は応答は、行き先のノード４０を時計回りに周回する方向に送信される。このようにして、時計回りの探索が開始される。
【０４４６】
ノード４０（Ａ、Ｂ＋１）及びノード４０（Ａ、Ｂ−１）は、共に、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二番目に短い経路上にある。
【０４４７】
ステップ１７１５において、逆探索マーク５０３が付与されていると判定された場合、時計回りの探索が実行されている。このため、ノード４０は、ステップ１７１６からステップ１７１９までを実行せず、ステップ１７２０を実行する。
【０４４８】
次に、ノード４０は、送信が成功したか否かを判定する（１７２１）。
【０４４９】
ステップ１７２１において、送信が成功したと判定された場合、処理を終了する（１７２２）。
【０４５０】
一方、ステップ１７２１において、送信が成功しなかったと判定された場合、反時計回り又は時計回りのいずれの方向の探索も、それ以上することができない。このため、ノード４０は、伝送不能障害を報告し（１７１１）、処理を終了する（１７１２）。
【０４５１】
図１８は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、要求又は応答に迂回マーク５０２が付与されていた場合に実行される処理のフローチャートである。
【０４５２】
迂回マーク５０２が付与された要求又は応答は、障害を回避するように送信されている。しかし、このような要求又は応答を受信したノード４０が、通常の処理によって送信先を決定すると、この要求又は応答が、再び元のノード４０（迂回マーク５０２が付与された要求又は応答の送信元のノード４０）に戻されてしまう場合がある。したがって、迂回マーク５０２が付与された要求又は応答を受信したノード４０が、受信した要求又は応答を、送信元のノード４０に送信しないために、図１８の処理が実行される。
【０４５３】
図１０のステップ１０１０において、受信した要求又は応答に迂回マーク５０２が付与されていると判定された場合、当該要求又は応答は、障害を迂回するように送信されている。この場合、ノード４０は、付与されている迂回マーク５０２を消去する（１８０１）。具体的には、受信した要求又は応答のパケット５０の迂回マーク５０２の値を「無効」にする。
【０４５４】
次に、ノード４０は、Ａ＝ａであるか否かを判定する（１８０２）。
【０４５５】
ステップ１８０２において、Ａ＝ａであると判定された場合、行き先のノード４０は、自ノード４０と同じ列にある。しかし、図１５のステップ１５２６、１５２９、１５３０及び１５３３に示すように、迂回マーク５０２が付与された要求又は応答は、行き先のノード４０と異なる列のノード４０に送信される。従って、ステップ１８０２においてＡ＝ａであると判定された場合、付与された迂回マーク５０２は不正なものである。このため、ノード４０は、不正な迂回マーク５０２を報告して（１８０３）、処理を終了する（１８０４）。この場合の報告先は、伝送不能障害の報告先と同じであってもよい。
【０４５６】
一方、ステップ１８０２において、Ａ＝ａでないと判定された場合、行き先のノード４０は、自ノード４０と異なる列にある。この場合、ノード４０は、Ｂ＝ｂであるか否かを判定する（１８０５）。
【０４５７】
ステップ１８０５において、Ｂ＝ｂであると判定された場合、行き先のノード４０は、自ノード４０と同じ行にある。しかし、図１６のステップ１６２６、１６２９、１６３０及び１６３３に示すように、迂回マーク５０２が付与された要求又は応答は、行き先のノード４０と異なる行のノード４０に送信される。従って、ステップ１８０５においてＢ＝ｂであると判定された場合、付与された迂回マーク５０２は不正なものである。このため、ノード４０は、不正な迂回マーク５０２を報告して（１８０３）、処理を終了する（１８０４）。
【０４５８】
一方、ステップ１８０５において、Ｂ＝ｂでないと判定された場合、行き先のノード４０は、自ノード４０と異なる行にある。この場合、ノード４０は、Ａ＜ａであるか否かを判定する（１８０６）。
【０４５９】
ステップ１８０６において、Ａ＜ａであると判定された場合、行き先のノード４０は、自ノード４０の右側にある。この場合、図１９のステップ１９０１に進む（１１）。
【０４６０】
一方、ステップ１８０６において、Ａ＜ａでないと判定された場合、行き先のノード４０は、自ノード４０の左側にある。この場合、ノード４０は、Ｂ＜ｂであるか否かを判定する（１８０７）。
【０４６１】
Ｂ＜ｂである場合、行き先のノード４０は、自ノード４０の上側にある。ステップ１８０７においてＢ＜ｂであると判定された場合、ステップ１８０６でＡ＜ａでないと判定されていることから、行き先のノード４０は、自ノード４０の左上側にある。
【０４６２】
この場合、ノード４０は、受信した要求又は応答の送信元のノード４０を特定する。まず、受信した要求又は応答が自ノード４０の左側に隣接するノード４０から送信されたか否かを判定する（１８０８）。具体的には、送信元のノード４０のアドレスを（Ｃ、Ｄ）としたとき、（Ｃ、Ｄ）＝（Ａ−１、Ｂ）であるか否かを判定する。
【０４６３】
ステップ１８０８において、（Ｃ、Ｄ）＝（Ａ−１、Ｂ）であると判定された場合、受信した要求又は応答が自ノード４０の左側に隣接するノード４０から送信されている。この場合、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１８０９）。その結果、ノード４０は、要求又は応答を、送信元のノード４０（Ａ−１、Ｂ）に送信しない。
【０４６４】
次に、ノード４０は、送信が成功したか否かを判定する（１８１０）。
【０４６５】
ステップ１８１０において、送信が成功したと判定された場合、処理を終了する（１８１１）。
【０４６６】
一方、ステップ１８１０において、送信が成功しなかったと判定された場合、迂回をすることができないため、伝送不能障害を報告して（１８１２）、処理を終了する（１８１３）。
【０４６７】
ステップ１８０８において、（Ｃ、Ｄ）＝（Ａ−１、Ｂ）でないと判定された場合、ノード４０は、受信した要求又は応答が自ノード４０の上側に隣接するノード４０から送信されたか否かを判定する（１８１４）。具体的には、送信元のノード４０のアドレスを（Ｃ、Ｄ）としたとき、（Ｃ、Ｄ）＝（Ａ、Ｂ＋１）であるか否かを判定する。
【０４６８】
ステップ１８１４において、（Ｃ、Ｄ）＝（Ａ、Ｂ＋１）であると判定された場合、受信した要求又は応答が自ノード４０の上側に隣接するノード４０から送信されている。この場合、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１８１５）。その結果、ノード４０は、要求又は応答を、送信元のノード４０（Ａ、Ｂ＋１）に送信しない。
【０４６９】
次に、ノード４０は、送信が成功したか否かを判定する（１８１０）。ステップ１８１０以降の処理は、上記で説明した通りであるので、説明を省略する。
【０４７０】
ステップ１８１４において、（Ｃ、Ｄ）＝（Ａ、Ｂ＋１）でないと判定された場合、受信した要求又は応答が自ノード４０の上側に隣接するノード４０から送信されていない。
【０４７１】
迂回マーク５０２が付与された要求又は応答は、行き先のノード４０と同一の行又は同一の列のノード４０から、行き先のノード４０と異なる行かつ異なる列のノード４０に送信される（図１５及び図１６参照）。したがって、迂回マーク５０２が付与された要求又は応答を受信した自ノード４０が、行き先のノード４０の右下側にある（すなわち、行き先のノード４０が自ノード４０の左上側にある）場合、その要求又は応答を送信したノード４０は、受信した自ノード４０の左側又は上側に隣接するはずである。
【０４７２】
しかし、ステップ１８１４において（Ｃ、Ｄ）＝（Ａ、Ｂ＋１）でないと判定された場合、受信した要求又は応答は、自ノード４０の上側に隣接するノード４０又は左側に隣接するノード４０のいずれから送信されたものでもない。このため、ノード４０は、不正な迂回マーク５０２を報告して（１８１６）、処理を終了する（１８１７）。
【０４７３】
ステップ１８０７において、Ｂ＜ｂでないと判定された場合、行き先のノード４０は、自ノード４０の左下側にある。
【０４７４】
この場合、ノード４０は、受信した要求又は応答の送信元のノード４０を特定する。まず、受信した要求又は応答が自ノード４０の下側に隣接するノード４０から送信されたか否かを判定する（１８１８）。具体的には、送信元のノード４０のアドレスを（Ｃ、Ｄ）としたとき、（Ｃ、Ｄ）＝（Ａ、Ｂ−１）であるか否かを判定する。
【０４７５】
ステップ１８１８において、（Ｃ、Ｄ）＝（Ａ、Ｂ−１）であると判定された場合、受信した要求又は応答が自ノード４０の下側に隣接するノード４０から送信されている。この場合、ノード４０は、要求又は応答を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１８１９）。その結果、ノード４０は、要求又は応答を、送信元のノード４０（Ａ、Ｂ−１）に送信しない。
【０４７６】
次に、ノード４０は、送信が成功したか否かを判定する（１８１０）。ステップ１８１０以降の処理は、上記で説明した通りであるので、説明を省略する。
【０４７７】
ステップ１８１８において、（Ｃ、Ｄ）＝（Ａ、Ｂ−１）でないと判定された場合、ノード４０は、受信した要求又は応答が自ノード４０の左側に隣接するノード４０から送信されたか否かを判定する（１８２０）。具体的には、送信元のノード４０のアドレスを（Ｃ、Ｄ）としたとき、（Ｃ、Ｄ）＝（Ａ−１、Ｂ）であるか否かを判定する。
【０４７８】
ステップ１８２０において、（Ｃ、Ｄ）＝（Ａ−１、Ｂ）であると判定された場合、受信した要求又は応答が自ノード４０の左側に隣接するノード４０から送信されている。この場合、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１８２１）。その結果、ノード４０は、要求又は応答を、送信元のノード４０（Ａ−１、Ｂ）に送信しない。
【０４７９】
次に、ノード４０は、送信が成功したか否かを判定する（１８１０）。ステップ１８１０以降の処理は、上記で説明した通りであるので、説明を省略する。
【０４８０】
ステップ１８２０において、（Ｃ、Ｄ）＝（Ａ−１、Ｂ）でないと判定された場合、受信した要求又は応答が自ノード４０の左側に隣接するノード４０から送信されていない。
【０４８１】
迂回マーク５０２が付与された要求又は応答を受信した自ノード４０が、行き先のノード４０の右上側にある（すなわち、行き先のノード４０が自ノード４０の左下側にある）場合、その要求又は応答を送信したノード４０は、受信した自ノード４０の左側又は下側に隣接するはずである。しかし、ステップ１８２０において（Ｃ、Ｄ）＝（Ａ−１、Ｂ）でないと判定された場合、受信した要求又は応答は、自ノード４０の左側に隣接するノード４０又は下側に隣接するノード４０のいずれから送信されたものでもない。このため、ノード４０は、不正な迂回マーク５０２を報告して（１８２２）、処理を終了する（１８２３）。
【０４８２】
図１９は、本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、要求又は応答に迂回マーク５０２が付与されていた場合であって、行き先のノード４０が自ノード４０の右側にある場合に実行される処理のフローチャートである。
【０４８３】
図１８のステップ１８０６において、Ａ＜ａであると判定された場合、行き先のノード４０は、自ノード４０の右側にある。この場合、ノード４０は、Ｂ＜ｂであるか否かを判定する（１９０１）。
【０４８４】
Ｂ＜ｂである場合、行き先のノード４０は、自ノード４０の上側にある。ステップ１９０１においてＢ＜ｂであると判定された場合、ステップ１８０６でＡ＜ａであると判定されていることから、行き先のノード４０は、自ノード４０の右上側にある。
【０４８５】
この場合、ノード４０は、受信した要求又は応答の送信元のノード４０を特定する。まず、受信した要求又は応答が自ノード４０の右側に隣接するノード４０から送信されたか否かを判定する（１９０２）。具体的には、送信元のノード４０のアドレスを（Ｃ、Ｄ）としたとき、（Ｃ、Ｄ）＝（Ａ＋１、Ｂ）であるか否かを判定する。
【０４８６】
ステップ１９０２において、（Ｃ、Ｄ）＝（Ａ＋１、Ｂ）であると判定された場合、受信した要求又は応答が自ノード４０の右側に隣接するノード４０から送信されている。この場合、ノード４０は、要求又は応答を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１９０３）。その結果、ノード４０は、要求又は応答を、送信元のノード４０（Ａ＋１、Ｂ）に送信しない。
【０４８７】
次に、ノード４０は、送信が成功したか否かを判定する（１９０４）。
【０４８８】
ステップ１９０４において、送信が成功したと判定された場合、処理を終了する（１９０５）。
【０４８９】
一方、ステップ１９０４において、送信が成功しなかったと判定された場合、迂回をすることができないため、伝送不能障害を報告して（１９０６）、処理を終了する（１９０７）。
【０４９０】
ステップ１９０２において、（Ｃ、Ｄ）＝（Ａ＋１、Ｂ）でないと判定された場合、ノード４０は、受信した要求又は応答が自ノード４０の上側に隣接するノード４０から送信されたか否かを判定する（１９０８）。具体的には、送信元のノード４０のアドレスを（Ｃ、Ｄ）としたとき、（Ｃ、Ｄ）＝（Ａ、Ｂ＋１）であるか否かを判定する。
【０４９１】
ステップ１９０８において、（Ｃ、Ｄ）＝（Ａ、Ｂ＋１）であると判定された場合、受信した要求又は応答が自ノード４０の上側に隣接するノード４０から送信されている。この場合、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１９０９）。その結果、ノード４０は、要求又は応答を、送信元のノード４０（Ａ、Ｂ＋１）に送信しない。
【０４９２】
次に、ノード４０は、送信が成功したか否かを判定する（１９０４）。ステップ１９０４以降の処理は、上記で説明した通りであるので、説明を省略する。
【０４９３】
ステップ１９０８において、（Ｃ、Ｄ）＝（Ａ、Ｂ＋１）でないと判定された場合、受信した要求又は応答が自ノード４０の上側に隣接するノード４０から送信されていない。
【０４９４】
迂回マーク５０２が付与された要求又は応答を受信した自ノード４０が、行き先のノード４０の左下側にある（すなわち、行き先のノード４０が自ノード４０の右上側にある）場合、その要求又は応答を送信したノード４０は、受信した自ノード４０の右側又は上側に隣接するはずである。
【０４９５】
しかし、ステップ１９０８において（Ｃ、Ｄ）＝（Ａ、Ｂ＋１）でないと判定された場合、受信した要求又は応答は、自ノード４０の上側に隣接するノード４０又は右側に隣接するノード４０のいずれから送信されたものでもない。このため、ノード４０は、不正な迂回マーク５０２を報告して（１９１０）、処理を終了する（１９１１）。
【０４９６】
ステップ１９０１において、Ｂ＜ｂでないと判定された場合、行き先のノード４０は、自ノード４０の右下側にある。
【０４９７】
この場合、ノード４０は、受信した要求又は応答の送信元のノード４０を特定する。まず、受信した要求又は応答が自ノード４０の下側に隣接するノード４０から送信されたか否かを判定する（１９１２）。具体的には、送信元のノード４０のアドレスを（Ｃ、Ｄ）としたとき、（Ｃ、Ｄ）＝（Ａ、Ｂ−１）であるか否かを判定する。
【０４９８】
ステップ１９１２において、（Ｃ、Ｄ）＝（Ａ、Ｂ−１）であると判定された場合、受信した要求又は応答が自ノード４０の下側に隣接するノード４０から送信されている。この場合、ノード４０は、要求又は応答を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１９１３）。その結果、ノード４０は、要求又は応答を、送信元のノード４０（Ａ、Ｂ−１）に送信しない。
【０４９９】
次に、ノード４０は、送信が成功したか否かを判定する（１９０４）。ステップ１９０４以降の処理は、上記で説明した通りであるので、説明を省略する。
【０５００】
ステップ１９１２において、（Ｃ、Ｄ）＝（Ａ、Ｂ−１）でないと判定された場合、ノード４０は、受信した要求又は応答が自ノード４０の右側に隣接するノード４０から送信されたか否かを判定する（１９１４）。具体的には、送信元のノード４０のアドレスを（Ｃ、Ｄ）としたとき、（Ｃ、Ｄ）＝（Ａ＋１、Ｂ）であるか否かを判定する。
【０５０１】
ステップ１９１４において、（Ｃ、Ｄ）＝（Ａ＋１、Ｂ）であると判定された場合、受信した要求又は応答が自ノード４０の右側に隣接するノード４０から送信されている。この場合、ノード４０は、要求又は応答を下側に隣接するノード４０（Ａ、Ｂ−１）に送信する（１９１５）。その結果、ノード４０は、要求又は応答を、送信元のノード４０（Ａ＋１、Ｂ）に送信しない。
【０５０２】
次に、ノード４０は、送信が成功したか否かを判定する（１９０４）。ステップ１９０４以降の処理は、上記で説明した通りであるので、説明を省略する。
【０５０３】
ステップ１９１４において、（Ｃ、Ｄ）＝（Ａ＋１、Ｂ）でないと判定された場合、受信した要求又は応答が自ノード４０の右側に隣接するノード４０から送信されていない。
【０５０４】
迂回マーク５０２が付与された要求又は応答を受信した自ノード４０が、行き先のノード４０の左上側にある（すなわち、行き先のノード４０が自ノード４０の右下側にある）場合、その要求又は応答を送信したノード４０は、受信した自ノード４０の右側又は下側に隣接するはずである。しかし、ステップ１９１４において（Ｃ、Ｄ）＝（Ａ＋１、Ｂ）でないと判定された場合、受信した要求又は応答は、自ノード４０の右側に隣接するノード４０又は下側に隣接するノード４０のいずれから送信されたものでもない。このため、ノード４０は、不正な迂回マーク５０２を報告して（１９１６）、処理を終了する（１９１７）。
【０５０５】
図２０は、本発明の第１の実施の形態において実行される探索の例の説明図である。
【０５０６】
図２０は、例として、探索カウント５０４の値が０より大きく、迂回マーク５０２が付与されておらず、行き先のノード４０（ａ、ｂ）と自ノード４０（Ａ、Ｂ）の位置関係がＡ＝ａ＋１かつＢ＝ｂ−１（ａ＝Ａ−１かつｂ＝Ｂ＋１）である場合のパケット５０の送信先を示す。以下の説明において、図１０、図１１及び図１３が参照される。
【０５０７】
ノード４０（Ａ、Ｂ）が隣接するノード４０からパケット５０を受信すると（１００５）、Ａ＝ａかつＢ＝ｂを満たさず（１００９）、迂回マーク５０２が付与されていないため（１０１０）、処理は図１１のステップ１１０１に進む。
【０５０８】
探索カウント＞０であるため（１１０３）、処理は図１３のステップ１３０１に進む。
【０５０９】
Ａ＜ａではなく（１３０２）、Ｂ＜ｂである（１３０３）ため、処理はステップ１３０４に進む。
【０５１０】
パケット５０に逆探索マーク５０３が付与されていない場合（１３０４）、ノード４０（Ａ、Ｂ）は、パケット５０を上側に隣接するノード４０（Ａ、Ｂ＋１）に送信する（１３０５）。
【０５１１】
一方、パケット５０に逆探索マーク５０３が付与されている場合（１３０４）、ノード４０（Ａ、Ｂ）は、パケット５０を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１３０９）。
【０５１２】
また、ステップ１３０５の送信に失敗した場合（１３０６）、ノード４０（Ａ、Ｂ）は、パケット５０に逆探索マーク５０３を付与し（１３０８）、そのパケット５０を左側に隣接するノード４０（Ａ−１、Ｂ）に送信する（１３０９）。
【０５１３】
図２１は、本発明の第１の実施の形態において実行される探索の別の例の説明図である。
【０５１４】
図２１は、例として、探索カウント５０４の値が０より大きく、迂回マーク５０２が付与されておらず、行き先のノード４０（ａ、ｂ）と自ノード４０（Ａ、Ｂ）の位置関係がＡ＝ａかつＢ＝ｂ＋１（ｂ＝Ｂ−１）である場合のパケット５０の送信先を示す。さらに、図２１の例では、行き先のノード４０（ａ、ｂ）と自ノード４０（Ａ、Ｂ）の間のリンク４１に障害が発生している。以下の説明において、図１０、図１１及び図１５が参照される。
【０５１５】
なお、自ノード４０（Ａ、Ｂ）の左側に隣接するノード４０（Ａ−１、Ｂ）及び右側に隣接するノード４０（Ａ＋１、Ｂ）は、共に、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二番目に短い経路上にある。
【０５１６】
ノード４０（Ａ、Ｂ）が隣接するノード４０からパケット５０を受信して図１０の処理が開始すると（１００５）、Ａ＝ａかつＢ＝ｂを満たさず（１００９）、迂回マーク５０２が付与されていないため（１０１０）、処理は図１１のステップ１１０１に進む。
【０５１７】
Ａ＝ａであるため（１１０１）、処理は図１５のステップ１５０１に進む。
【０５１８】
Ｂ＜ｂでないため（１５０１）、ノード４０（Ａ、Ｂ）は、パケット５０を下側に隣接ずるノード４０（Ａ、Ｂ−１）に送信する（１５０６）。
【０５１９】
ステップ１５０６の送信に成功すれば処理が終了するが（１５０７、１５０８）、図２１の例では、リンク４１の障害のため、送信に失敗する。
【０５２０】
Ｂ−１＝ｂであるため（１５０９）、探索カウント５０４の値を１増加させる（１５１０）。
【０５２１】
探索カウント５０４の値が８より大きい場合（１５１１）、行き先のノード４０（ａ、ｂ）に至る全てのリンク４１において送信が失敗したため、伝送不能障害が報告され（１５２０）、処理が終了する（１５２１）。
【０５２２】
探索カウント５０４の値が８以下であり（１５１１）、逆探索マーク５０３が付与されていない場合（１５１２）、ノード４０（Ａ、Ｂ）は、左側に隣接するノード４０（Ａ−１、Ｂ）にパケット５０を送信する（１５１３）。
【０５２３】
一方、逆探索マーク５０３が付与されている場合（１５１２）、ノード４０（Ａ、Ｂ）は、右側に隣接するノード４０（Ａ＋１、Ｂ）にパケット５０を送信する（１５１７）。
【０５２４】
ステップ１５１３の送信に失敗した場合（１５１４）、ノード４０（Ａ、Ｂ）は、パケット５０に逆探索マーク５０３を付与し（１５１６）、右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１５１７）。
【０５２５】
図２２は、本発明の第１の実施の形態において、ノード４０がパケット５０に迂回マーク５０２を付与する処理の説明図である。
【０５２６】
図２２の例は、行き先のノード４０（ａ、ｂ）が自ノード４０（Ａ、Ｂ）と同じ行にあり、かつ、隣接しない場合（すなわち、Ｂ＝ｂ、Ａ＜ａであり、かつ、Ａ＋１＝ａでない場合）を示す。また、自ノード４０（Ａ、Ｂ）とその右側に隣接するノード４０（Ａ＋１、Ｂ）の間のリンク４１に障害が発生している。さらに、ノード４０（Ａ、Ｂ）とノード４０（Ａ、Ｂ＋１）との間の通信量γは、ノード４０（Ａ、Ｂ）とノード４０（Ａ、Ｂ−１）との間の通信量δより小さい。以下の説明において、図１０、図１１及び図１６が参照される。
【０５２７】
なお、自ノード４０（Ａ、Ｂ）の上側に隣接するノード４０（Ａ、Ｂ＋１）及び下側に隣接するノード４０（Ａ、Ｂ−１）は、共に、自ノード４０（Ａ、Ｂ）から行き先のノード４０（ａ、ｂ）に至る二番目に短い経路上にある。
【０５２８】
図１０の処理が開始すると、Ａ＝ａかつＢ＝ｂを満たさず（１００９）、迂回マーク５０２が付与されていないため（１０１０）、処理は図１１のステップ１１０１に進む。
【０５２９】
Ａ＝ａでないが、Ｂ＝ｂであるため、処理は図１６のステップ１６０１に進む。
【０５３０】
Ａ＜ａであるため、ノード４０（Ａ、Ｂ）は、パケット５０を右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１６０２）。
【０５３１】
ステップ１６０２の送信に成功すれば処理が終了するが（１６０３、１６０４）、図２２の例では、リンク４１の障害のため、送信に失敗する。
【０５３２】
Ａ＋１＝ａでないため（１６０５）、ノード４０（Ａ、Ｂ）は、パケット５０に迂回マーク５０２を付与する（１６２２）。
【０５３３】
通信量γが通信量δより小さいため（１６２５）、ノード４０（Ａ、Ｂ）は、上側に隣接するノード４０（Ａ、Ｂ＋１）にパケット５０を送信する（１６２６）。図２２の例では、ステップ１６２６の送信に成功して（１６２７）、処理が終了する（１６２８）。
【０５３４】
図２３は、本発明の第１の実施の形態において、迂回マーク５０２が付与されたパケット５０を受信したノード４０が実行する処理の説明図である。
【０５３５】
図２３の例は、図２２の例において送信されたパケット５０を受信したノード４０によって実行される処理を示す。図２３のノード４０（Ａ、Ｂ）は、図２２のノード４０（Ａ、Ｂ＋１）に相当する。以下の説明において、図１０、図１８及び図１９が参照される。
【０５３６】
ノード４０（Ａ、Ｂ）が下側に隣接するノード４０（Ａ、Ｂ−１）からパケット５０を受信して図１０の処理が開始すると（１００５）、Ａ＝ａかつＢ＝ｂを満たさず（１００９）、迂回マーク５０２が付与されているため（１０１０）、処理は図１８のステップ１８０１に進む。
【０５３７】
ノード４０（Ａ、Ｂ）は、パケット５０に付与された迂回マーク５０２を消去する（１８０１）。
【０５３８】
Ａ＝ａでなく（１８０２）、Ｂ＝ｂでなく（１８０５）、Ａ＜ａである（１８０６）ため、処理は図１９のステップ１９０１に進む。
【０５３９】
Ｂ＜ｂでなく（１９０１）、パケット５０はノード４０（Ａ、Ｂ）の下側に隣接するノード４０（Ａ、Ｂ−１）から送信されている（１９１２）。このため、ノード４０（Ａ、Ｂ）は、パケット５０を送信元のノード４０（Ａ、Ｂ−１）に送信せず、右側に隣接するノード４０（Ａ＋１、Ｂ）に送信する（１９１３）。
【０５４０】
以上の本発明の第１の実施の形態によれば、ホスト計算機及びディスクドライブ１０４が接続されたノード４０が、リンク４１によって二次元の格子状に接続される。このため、任意の数のノード４０を接続することによって任意の規模のストレージシステムを構成することができる。
【０５４１】
図２４は、本発明の第２の実施の形態のストレージシステムの構成を示すブロック図である。
【０５４２】
本実施の形態のストレージシステムは、複数のストレージ制御部２４００及び複数のディスクドライブ１０４によって構成される。
【０５４３】
ストレージ制御部２４００は、６ポートスイッチ１０２の代わりに８ポートスイッチ２４０１を備えることを除いて、本発明の第１の実施の形態のストレージ制御部１０（図１参照）と同じである。このため、本実施の形態において、本発明の第１の実施の形態と同様の部分については、説明を省略する。
【０５４４】
図２４には、８個のストレージ制御部２４００Ａ〜２４００Ｈを示すが、本実施の形態のストレージシステムは、任意の数のストレージ制御部２４００を含むことができる。
【０５４５】
ストレージ制御部２４００は、ホスト接続制御部１０１、８ポートスイッチ２４０１及びドライブ制御部１０３を備える。
【０５４６】
８ポートスイッチ２４０１は、同じストレージ制御部２４００内のホスト接続制御部１０１、同じストレージ制御部２４００内のドライブ制御部１０３、隣接するストレージ制御部２４００内のホスト接続制御部１０１、隣接するストレージ制御部２４００内のドライブ制御部１０３及び他のストレージ制御部２４００内の８ポートスイッチ２４０１と接続され、これらの間の接続を切り替えるスイッチである。８ポートスイッチ２４０１は、８個のポート（図示省略）を備え、各ポートがそれぞれ一つのホスト接続制御部１０１、ドライブ制御部１０３又は他の８ポートスイッチ２４０１と接続される。
【０５４７】
例えば、ストレージ制御部２４００Ｂ内の８ポートスイッチ２４０１Ｂの各ポートには、それぞれ、接続線２４１０Ａ〜２４１０Ｈが接続される。
【０５４８】
接続線２４１０Ａは、図２４に示さない他のストレージ制御部２４００内の８ポートスイッチ２４０１に接続される。
【０５４９】
接続線２４１０Ｂは、ストレージ制御部２４００Ａ内のホスト接続制御部１０１Ａに接続される。
【０５５０】
接続線２４１０Ｃは、ストレージ制御部２４００Ｂ内のホスト接続制御部１０１Ｂに接続される。
【０５５１】
接続線２４１０Ｄは、図２４に示さない他のストレージ制御部２４００内の８ポートスイッチ２４０１に接続される。
【０５５２】
接続線２４１０Ｅは、ストレージ制御部２４００Ｄ内の８ポートスイッチ２４０１Ｄに接続される。
【０５５３】
接続線２４１０Ｆは、ストレージ制御部２４００Ｆ内の８ポートスイッチ２４０１Ｆに接続される。
【０５５４】
接続線２４１０Ｇは、ストレージ制御部２４００Ｂ内のドライブ制御部１０３Ｂに接続される。
【０５５５】
接続線２４１０Ｈは、ストレージ制御部２４００Ａ内のドライブ制御部１０３Ａに接続される。
【０５５６】
同様にして、ストレージ制御部２４００Ａ内の８ポートスイッチ２４０１Ａの各ポートには、それぞれ、接続線２４１０Ｊ〜２４１０Ｎ、２４１０Ｐ〜２４１０Ｒが接続される。
【０５５７】
接続線２４１０Ｊは、図２４に示さない他のストレージ制御部２４００内の８ポートスイッチ２４０１に接続される。
【０５５８】
接続線２４１０Ｋは、図２４に示さない他のストレージ制御部２４００内の８ポートスイッチ２４０１に接続される。
【０５５９】
接続線２４１０Ｌは、ストレージ制御部２４００Ａ内のホスト接続制御部１０１Ａに接続される。
【０５６０】
接続線２４１０Ｍは、ストレージ制御部２４００Ｂ内のホスト接続制御部１０１Ｂに接続される。
【０５６１】
接続線２４１０Ｎは、ストレージ制御部２４００Ｃ内の８ポートスイッチ２４０１Ｃに接続される。
【０５６２】
接続線２４１０Ｐは、ストレージ制御部２４００Ｂ内のドライブ制御部１０３Ｂに接続される。
【０５６３】
接続線２４１０Ｑは、ストレージ制御部２４００Ａ内のドライブ制御部１０３Ａに接続される。
【０５６４】
接続線２４１０Ｒは、ストレージ制御部２４００Ｅ内の８ポートスイッチ２４０１Ｅに接続される。
【０５６５】
本実施の形態では、一つのノード４０（図４参照）が二つのストレージ制御部２４００に相当する。また、一つのリンク４１が二つの接続線２４１０に相当する。
【０５６６】
例えば、図４のノード４０（１、１）がストレージ制御部２４００Ａ及び２４００Ｂに相当する場合、リンク４１Ａは、接続線２４１０Ａ及び２４１０Ｊに相当する。リンク４１Ｂは、接続線２４１０Ｄ及び２４１０Ｋに相当する。リンク４１Ｃは、接続線２４１０Ｅ及び２４１０Ｎに相当する。リンク４１Ｄは、接続線２４１０Ｆ及び２４１０Ｒに相当する。
【０５６７】
この場合、図４のノード４０（２、１）は、ストレージ制御部２４００Ｃ及び２４００Ｄに相当する。このとき、ノード４０（１、１）の８ポートスイッチ２４０１Ａは、接続線２４１０Ｎによって、ノード４０（２、１）の８ポートスイッチ２４０１Ｃと接続される。一方、ノード４０（１、１）の８ポートスイッチ２４０１Ｂは、接続線２４１０Ｅによって、ノード４０（２、１）の８ポートスイッチ２４０１Ｄと接続される。
【０５６８】
本実施の形態のノード４０は、本発明の第１の実施の形態と同様、パケット５０（図５参照）を送受信する。本実施の形態には、本発明の第１の実施の形態と同じルーティングアルゴリズム（図６〜図２３参照）が適用される。
【０５６９】
本実施の形態によれば、各ノード４０及びリンク４１が二重化されるため、本発明の第１の実施の形態と比較して、耐障害性が向上する。
【０５７０】
図２５は、本発明の第３の実施の形態のストレージシステムの構成を示すブロック図である。
【０５７１】
本実施の形態のストレージシステムは、複数のストレージ制御部２５００及び複数のディスクドライブ１０４によって構成される。
【０５７２】
ストレージ制御部２５００は、６ポートスイッチ１０２の代わりに１０ポートスイッチ２５０１を備えることを除いて、本発明の第１の実施の形態のストレージ制御部１０（図１参照）と同じである。このため、本実施の形態において、本発明の第１の実施の形態と同様の部分については、説明を省略する。
【０５７３】
図２５には、８個のストレージ制御部２５００Ａ〜２５００Ｈを示すが、本実施の形態のストレージシステムは、任意の数のストレージ制御部２５００を含むことができる。
【０５７４】
ストレージ制御部２５００は、ホスト接続制御部１０１、１０ポートスイッチ２５０１及びドライブ制御部１０３を備える。
【０５７５】
１０ポートスイッチ２５０１は、同じストレージ制御部２５００内のホスト接続制御部１０１、同じストレージ制御部２５００内のドライブ制御部１０３及び他のストレージ制御部２５００内の１０ポートスイッチ２５０１と接続され、これらの間の接続を切り替えるスイッチである。１０ポートスイッチ２５０１は、１０個のポート（図示省略）を備え、各ポートがそれぞれ一つのホスト接続制御部１０１、ドライブ制御部１０３又は他の１０ポートスイッチ２５０１と接続される。
【０５７６】
例えば、ストレージ制御部２５００Ｂ内の１０ポートスイッチ２５０１Ｂの各ポートには、それぞれ、接続線２５１０Ａ〜２５１０Ｈ、２５１０Ｊ及び２５１０Ｋが接続される。
【０５７７】
接続線２５１０Ａは、ストレージ制御部２５００Ａ内の１０ポートスイッチ２５０１Ａに接続される。
【０５７８】
接続線２５１０Ｂは、図２５に示さない他のストレージ制御部２５００内の１０ポートスイッチ２５０１に接続される。
【０５７９】
接続線２５１０Ｃは、ストレージ制御部２５００Ｂ内のホスト接続制御部１０１Ｂに接続される。
【０５８０】
接続線２５１０Ｄは、図２５に示さない他のストレージ制御部２５００内の１０ポートスイッチ２５０１に接続される。
【０５８１】
接続線２５１０Ｅは、図２５に示さない他のストレージ制御部２５００内の１０ポートスイッチ２５０１に接続される。
【０５８２】
接続線２５１０Ｆは、ストレージ制御部２５００Ｃ内の１０ポートスイッチ２５０１Ｃに接続される。
【０５８３】
接続線２５１０Ｇは、ストレージ制御部２５００Ｇ内の１０ポートスイッチ２５０１Ｇに接続される。
【０５８４】
接続線２５１０Ｈは、ストレージ制御部２５００Ｆ内の１０ポートスイッチ２５０１Ｆに接続される。
【０５８５】
接続線２５１０Ｊは、ストレージ制御部２５００Ｂ内のドライブ制御部１０３Ｂに接続される。
【０５８６】
接続線２５１０Ｋは、ストレージ制御部２５００Ｅ内の１０ポートスイッチ２５０１Ｅに接続される。
【０５８７】
本実施の形態では、一つのノード４０（図４参照）が一つのストレージ制御部２５００に相当する。また、一つのリンク４１が一つの接続線２５１０に相当する。
【０５８８】
例えば、図４のノード４０（１、１）がストレージ制御部２５００Ｂに相当する場合、リンク４１Ａ、４１Ｂ、４１Ｃ及び４１Ｄは、それぞれ、接続線２５１０Ａ、２５１０Ｄ、２５１０Ｆ及び２５１０Ｈに相当する。
【０５８９】
さらに、図４には示さないが、接続線２５１０Ｂは、ノード４０（１、１）とノード４０（０、２）とを接続する斜め方向のリンクである。同様に、接続線２５１０Ｅはノード４０（１、１）とノード４０（２、２）とを接続する斜め方向のリンク、接続線２５１０Ｇはノード４０（１、１）とノード４０（２、０）とを接続する斜め方向のリンク、接続線２５１０Ｋはノード４０（１、１）とノード４０（０、０）とを接続する斜め方向のリンクである。
【０５９０】
本実施の形態のノード４０は、本発明の第１の実施の形態と同様、パケット５０（図５参照）を送受信する。
【０５９１】
本実施の形態には、本発明の第１の実施の形態と同じルーティングアルゴリズム（図６〜図２３参照）が適用されてもよいが、上記の斜め方向のリンクを利用した別のアルゴリズムが適用されてもよい。
【０５９２】
本実施の形態によれば、上記の斜め方向のリンクを利用することによって、本発明の第１の実施の形態と比較して、耐障害性が向上する。さらに、斜め方向のノード４０が直接接続されることによって、これらのノード４０間のデータ転送性能が向上する。
【０５９３】
図２６は、本発明の第４の実施の形態のストレージシステムの構成を示すブロック図である。
【０５９４】
図２６の構成は、本発明の第２の実施の形態のストレージ制御部２４００の一部をフロントエンド制御部２６００によって置き換えたものである。
【０５９５】
フロントエンド制御部２６００は、ストレージ制御部２４００内のドライブ制御部１０３をホスト接続制御部１０１によって置き換えたものである。すなわち、フロントエンド制御部２６００には、ホスト計算機のみが接続され、ディスクドライブ１０４は接続されない。
【０５９６】
本実施の形態では、各ストレージ制御部２４００及び各フロントエンド制御部２６００が８ポートスイッチ２４０１を備える。このため、本発明の第２の実施の形態（図２４参照）と同様、二つのストレージ制御部２４００が一つのノード４０（ストレージノード）を構成する。同様にして、二つのフロントエンド制御部２６００が一つのノード４０（フロントエンドノード）を構成する。ノード４０間の接続の形態は、図４に示す通りである。
【０５９７】
本実施の形態のノード４０は、本発明の第１の実施の形態と同様、パケット５０（図５参照）を送受信する。本実施の形態には、本発明の第１の実施の形態と同じルーティングアルゴリズム（図６〜図２３参照）が適用される。
【０５９８】
本実施の形態のストレージシステムは、第１の実施の形態と比較して、より多くのホスト計算機と接続することができる。通常、大規模なストレージシステムには多くのホスト計算機が接続されるため、要求されるホストＩ／Ｆ２０１の数は、要求されるドライブＩ／Ｆの数よりずっと多い。本実施の形態によれば、ストレージノードを備えることによって、多くのホスト計算機と容易に接続することができる。
【０５９９】
図２７は、本発明の第５の実施の形態のストレージシステムの構成を示すブロック図である。
【０６００】
図２７の構成は、本発明の第１の実施の形態のストレージ制御部１０の全部をフロントエンド制御部２７００によって置き換えたものである。
【０６０１】
フロントエンド制御部２７００は、ストレージ制御部１０内のドライブ制御部１０３をホスト接続制御部１０１によって置き換えたものである。すなわち、フロントエンド制御部２７００には、ホスト計算機のみが接続され、ディスクドライブ１０４は接続されない。
【０６０２】
すなわち、本実施の形態のストレージシステム１は、ディスクドライブ１０４を含まない。ディスクドライブ１０４は、フロントエンド制御部２７００に接続されたホスト計算機２７０１に接続される。また、本実施の形態のストレージシステム１には、他のストレージシステム１を接続することもできる。
【０６０３】
本実施の形態では、各フロントエンド制御部２７００が６ポートスイッチ１０２を備える。このため、二つのフロントエンド制御部２７００が一つのノード４０（フロントエンドノード）を構成する。ノード４０間の接続の形態は、図４に示す通りである。
【０６０４】
本実施の形態のノード４０は、本発明の第１の実施の形態と同様、パケット５０（図５参照）を送受信する。本実施の形態には、本発明の第１の実施の形態と同じルーティングアルゴリズム（図６〜図２３参照）が適用される。
【０６０５】
本実施の形態のストレージシステム１は、例えば、ＳＡＮ（ストレージエリアネットワーク）スイッチとして使用することができる。
【０６０６】
本実施の形態のストレージシステム１によれば、ディスクドライブと多数のホスト計算機とを自由に接続することができる。本実施の形態のストレージシステム１は、他のホスト計算機又は他のストレージシステム１のディスクドライブを各ホスト計算機に提供する際に、それらのディスクドライブを各ホスト計算機の論理ボリュームに変換する。このため、各ホスト計算機は、物理的なディスクドライブの位置や構成に関らず、それぞれの論理ボリュームを自由かつ独立に運用することができる。
【０６０７】
以上の本発明によれば、ホスト接続制御部及びドライブ制御部がスイッチによって接続された比較的小規模なノードが構成される。そして、任意の数のノードを二次元に数珠つなぎに接続することによって、任意の規模のストレージシステムが構成される。このため、構成されるストレージシステムの規模に制限がない。また、小規模な構成において大規模なスイッチを用意する必要がないため、小規模構成のコストが上昇しない。さらに、大規模な構成においても大規模なスイッチを必要とせず、配線が比較的単純であるため、大規模構成時の配線コストの上昇が抑制される。その結果、記憶容量あたりのコストは、規模に関らず、概ね一定に抑制される。
【０６０８】
さらに、多数のノードが二次元の格子状に接続される構成となるため、データ転送が多数のノード間の多数のデータ転送に分散される。このため、データがノード間を伝送される場合の性能の低下が抑制される。また、ホスト計算機が接続されるノードと、アクセスされるドライブが接続されるノードが離れる場合、離れた距離（間に入るノード数）が大きいほどデータの伝達に時間がかかるが，この伝達時間は間に入ってデータ転送を経由するノードの数で決まり、急激に増大することはないため、伝達時間に急激な変化のある不均一性はなく、使い易い。
【０６０９】
さらに、各ノードは二次元の格子状に接続されるため、データの伝送経路の冗長性が高。すなわち、伝送経路に障害が発生した場合にも交代経路が多数存在するため、耐障害性が高い。
【図面の簡単な説明】
【０６１０】
【図１】本発明の第１の実施の形態のストレージシステムの構成を示すブロック図である。
【図２】本発明の第１の実施の形態のホスト接続制御部の構成を示すブロック図である。
【図３】本発明の第１の実施の形態のドライブ制御部の構成を示すブロック図である。
【図４】本発明の第１の実施の形態のストレージシステムの接続の説明図である。
【図５】本発明の第１の実施の形態のストレージシステムにおいて使用されるパケットの説明図である。
【図６】本発明の第１の実施の形態の基本的なルーティングアルゴリズムのフローチャートである。
【図７】本発明の第１の実施の形態の基本的なルーティングアルゴリズムにおいて、自ノードが行き先のノードでない場合に実行される処理のフローチャートである。
【図８】本発明の第１の実施の形態の基本的なルーティングアルゴリズムの適用例の説明図である。
【図９】本発明の第１の実施の形態の基本的なルーティングアルゴリズムの別の適用例の説明図である。
【図１０】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムのフローチャートである。
【図１１】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、自ノードが行き先のノードでない場合に実行される処理のフローチャートである。
【図１２】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、行き先のノードが自ノードの右上側又は右下側にある場合に実行される処理のフローチャートである。
【図１３】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて実行される探索の処理のフローチャートである。
【図１４】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて実行される探索の処理のうち、行き先のノードが自ノードの右上側又は右下側にある場合に実行される処理のフローチャートである。
【図１５】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、行き先のノードが自ノードと同じ列にある場合に実行される処理のフローチャートである。
【図１６】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、行き先のノードが自ノードと同じ行にある場合に実行される処理のフローチャートである。
【図１７】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、行き先のノードが自ノードと同じ行又は同じ列にある場合に実行される探索の処理のフローチャートである。
【図１８】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、要求又は応答に迂回マークが付与されていた場合に実行される処理のフローチャートである。
【図１９】本発明の第１の実施の形態の障害を考慮したルーティングアルゴリズムにおいて、要求又は応答に迂回マークが付与されていた場合であって、行き先のノードが自ノードの右側にある場合に実行される処理のフローチャートである。
【図２０】本発明の第１の実施の形態において実行される探索の例の説明図である。
【図２１】本発明の第１の実施の形態において実行される探索の別の例の説明図である。
【図２２】本発明の第１の実施の形態において、ノードがパケットに迂回マークを付与する処理の説明図である。
【図２３】本発明の第１の実施の形態において、迂回マークが付与されたパケットを受信したノードが実行する処理の説明図である。
【図２４】本発明の第２の実施の形態のストレージシステムの構成を示すブロック図である。
【図２５】本発明の第３の実施の形態のストレージシステムの構成を示すブロック図である。
【図２６】本発明の第４の実施の形態のストレージシステムの構成を示すブロック図である。
【図２７】本発明の第５の実施の形態のストレージシステムの構成を示すブロック図である。
【符号の説明】
【０６１１】
１０、２４００、２５００  ストレージ制御部
１０１  ホスト接続制御部
１０２  ６ポートスイッチ
１０３  ドライブ制御部
１０４  ディスクドライブ
１１０、２４１０、２５１０  接続線
２０１  ホストＩ／Ｆ部
２０２、３０２  プロセッサ
２０３、３０３  メモリ
２０４、３０４  ローカル接続スイッチ部
３０１  ドライブＩ／Ｆ部
４０  ノード
４１  リンク
５０  パケット
２６００、２７００  フロントエンド制御部
２４０１  ８ポートスイッチ
２５０１  １０ポートスイッチ
２７０１  ホスト計算機
【図１】
2006243967.tif 000003
【図２】
2006243967.tif 000004
【図３】
2006243967.tif 000005
【図４】
2006243967.tif 000006
【図５】
2006243967.tif 000007
【図６】
2006243967.tif 000008
【図７】
2006243967.tif 000009
【図８】
2006243967.tif 000010
【図９】
2006243967.tif 000011
【図１０】
2006243967.tif 000012
【図１１】
2006243967.tif 000013
【図１２】
2006243967.tif 000014
【図１３】
2006243967.tif 000015
【図１４】
2006243967.tif 000016
【図１５】
2006243967.tif 000017
【図１６】
2006243967.tif 000018
【図１７】
2006243967.tif 000019
【図１８】
2006243967.tif 000020
【図１９】
2006243967.tif 000021
【図２０】
2006243967.tif 000022
【図２１】
2006243967.tif 000023
【図２２】
2006243967.tif 000024
【図２３】
2006243967.tif 000025
【図２４】
2006243967.tif 000026
【図２５】
2006243967.tif 000027
【図２６】
2006243967.tif 000028
【図２７】
2006243967.tif 000029