(57)【要約】  さまざまな実施形態が、コスト（たとえば、ネットワークリンクの数）を削減し、同時に障害に対する回復力を提供してＱｏＳ要件（たとえば、ネットワークアーキテクチャをトラバースすることに起因したネットワーク遅延）を満たす、オーバーラップしないリング−メッシュネットワークトポロジを提供する方法および装置を提供する。とりわけ、クラスタに属するターゲットノードの集合が、Ｎ個のリングを通して接続される。各ノードは、全Ｎ個のリングのメンバであり、リングにおけるノード間のいずれのリンクも、別のリングにおいて重複しない。
2015529026.tif 000002
【特許請求の範囲】
【請求項１】
データストレージと、
データストレージに通信可能に接続されたプロセッサと
を含む、
スイッチクラスタを提供するための装置であって、
プロセッサが、
ターゲットノードの集合を決定し、
リングカウントを決定し、
リングカウントと等しい複数のオーバーラップしないリングを形成するように通信可能に接続されたターゲットノードの集合を含むネットワークアーキテクチャを、ターゲットノードの集合およびリングカウントに基づいて決定するように
構成されている、
装置。
【請求項２】
リングカウントが、ターゲットノードの集合におけるメンバの数、および性能基準に基づく、請求項１に記載の装置。
【請求項３】
ネットワークアーキテクチャの決定が、
ターゲットノードの集合およびリングカウントに基づいて、複数の候補ネットワークアーキテクチャを決定し、
性能基準に基づいて、ネットワークアーキテクチャとして、複数の候補ネットワークアーキテクチャのうちの１つを選択するように
プロセッサを構成することを含む、
請求項１に記載の装置。
【請求項４】
ネットワークアーキテクチャの決定が、
新しいオーバーラップしないリングを、少なくとも１つの他のオーバーラップしないリングに基づいて構築するように
プロセッサを構成することを含み、
複数のオーバーラップしないリングが、新しいオーバーラップしないリングと、少なくとも１つの他のオーバーラップしないリングとを含み、
新しいオーバーラップしないリングの構築が、
ターゲットノードのうちの第１のターゲットノードで、一部だけのオーバーラップしないリングを初期化し、
一部だけのオーバーラップしないリングにおける第２のターゲットノードと第２のターゲットノードの近傍ターゲットノードとの間の接続が、少なくとも１つの他のオーバーラップしないリングにおいて重複しないという判定に基づいて、ターゲットノードのうちの第２のターゲットノードを、一部だけのオーバーラップしないリングに付加し、
一部だけのオーバーラップしないリングにおける第３のターゲットノードと第３のターゲットノードの近傍ターゲットノードとの間の接続が、少なくとも１つの他のオーバーラップしないリングにおいて重複しないという判定に基づいて、ターゲットノードのうちの第３のターゲットノードを、一部だけのオーバーラップしないリングに挿入するように、
プロセッサを構成することを含む、
請求項１に記載の装置。
【請求項５】
第２のターゲットノードが、ターゲットノードのサブセットからランダムに選択され、一部だけのオーバーラップしないリングにおける最初のノードおよび最後のノードによる接続が少なくとも１つの他のオーバーラップしないリングにおいて重複しないように、サブセットが、一部だけのオーバーラップしないリングの中にはないターゲットノードのメンバを含む、請求項４に記載の装置。
【請求項６】
第３のターゲットノードの挿入が、一部だけのオーバーラップしないリングにまだ追加されないでいるターゲットノードのいずれも、一部だけのオーバーラップしないリングに付加され得ないという判定に基づく、請求項４に記載の装置。
【請求項７】
スイッチクラスタ
を含む、データを交換するためのシステムであって、
スイッチクラスタが、複数のオーバーラップしないリングを形成するように通信可能に接続された複数のノードを含む、
システム。
【請求項８】
スイッチクラスタを提供するための方法であって、
データストレージに通信可能に接続されたプロセッサにおいて、ターゲットノードの集合を決定するステップと、
データストレージと協働するプロセッサによって、リングカウントを決定するステップと、
データストレージと協働するプロセッサによって、ターゲットノードの集合およびリングカウントに基づいて、ネットワークアーキテクチャを決定するステップであって、ネットワークアーキテクチャが、リングカウントと等しい複数のオーバーラップしないリングを形成するように通信可能に接続されたターゲットノードの集合を含む、決定するステップと
を含む、方法。
【請求項９】
データストレージと協働するプロセッサによって、ネットワーク成長閾値に基づいて、ネットワークアーキテクチャに新しいリングを追加するステップ
をさらに含み、
新しいリングを追加するステップが、ターゲットノードのうちの第２のターゲットノードに第１のターゲットノードを通信可能に接続するように、ターゲットノードのうちの第１のターゲットノードのポートをリダイレクトするステップを含む、
請求項８に記載の方法。
【請求項１０】
ネットワークアーキテクチャを決定するステップが、
データストレージと協働するプロセッサによって、少なくとも１つの他のオーバーラップしないリングに基づいて、新しいオーバーラップしないリングを構築するステップ
を含み、
複数のオーバーラップしないリングが、新しいオーバーラップしないリングと、少なくとも１つの他のオーバーラップしないリングとを含む、
請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、スイッチクラスタネットワークアーキテクチャを提供するための方法および装置に関する。
【背景技術】
【０００２】
本項では、本発明のよりよい理解を促進する助けとなり得る態様を紹介する。したがって、本項の記述は、この観点から読まれるべきであり、先行技術に何が含まれ、または先行技術に何が含まれないかに関する承認として理解されるべきではない。
【０００３】
いくつかの知られているネットワークトポロジにおいて、ノードは、バストポロジに配置されてよく、この場合、共通のバックボーンがノードのすべてを接続する。他の知られているネットワークトポロジにおいて、ノードは、リングトポロジに配置されてよく、この場合、チェーンの中の各ノードは２つの近傍を有し、最後のノードが最初のノードに戻って接続する。さらに他の知られているネットワークトポロジにおいて、ノードは、スタートポロジに配置されてよく、この場合、子ノードの各々が１つの親ノードに直接戻って接続する。さらに他の知られているネットワークトポロジにおいて、ノードは、ツリートポロジに配置されてよく、この場合、根ノードが１つまたは複数のノードのレベルを生み、より低いレベルの各子ノードが、ツリーのより高いレベルのその親に直接接続する。さらに他の知られているネットワークトポロジにおいて、ノードは、メッシュトポロジに配置されてよく、この場合、ノードの１つまたは複数が、ネットワークを通して複数のパスを提供する他のノードの１つまたは複数に接続する。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
さまざまな実施形態が、コスト（たとえば、ネットワークリンクの数）を削減し、同時に障害に対する回復力を提供してＱｏＳ要件（たとえば、ネットワークアーキテクチャをトラバースすることに起因したネットワーク遅延）を満たす、オーバーラップしないリング−メッシュネットワークトポロジを提供する方法および装置を提供する。
【課題を解決するための手段】
【０００５】
一実施形態において、スイッチクラスタを提供するための装置が提供される。装置は、データストレージと、データストレージに通信可能に接続されたプロセッサとを含む。プロセッサは、以下のようにプログラムされる：ターゲットノードの集合を決定し、リングカウントを決定し、リングカウントと等しい複数のオーバーラップしないリングを形成するように通信可能に接続されたターゲットノードの集合を含むネットワークアーキテクチャを、ターゲットノードの集合およびリングカウントに基づいて決定する。
【０００６】
上の実施形態のいくつかにおいて、リングカウントは、ターゲットノードの集合におけるメンバの数に基づく。
【０００７】
上の実施形態のいくつかにおいて、リングカウントは、性能基準に基づく。
【０００８】
上の実施形態のいくつかにおいて、ネットワークアーキテクチャの決定は、プロセッサを以下のようにプログラムすることを含む：ターゲットノードの集合およびリングカウントに基づいて、複数の候補ネットワークアーキテクチャを決定し、性能基準に基づいて、ネットワークアーキテクチャとして、複数の候補ネットワークアーキテクチャのうちの１つを選択する。
【０００９】
上の実施形態のいくつかにおいて、性能基準は、平均ホップカウントおよび最大ホップカウントのうちの少なくとも１つである。
【００１０】
上の実施形態のいくつかにおいて、ネットワークアーキテクチャの決定は、プロセッサを以下のようにプログラムすることを含む：新しいオーバーラップしないリングを、少なくとも１つの他のオーバーラップしないリングに基づいて構築する。ここで、複数のオーバーラップしないリングは、新しいオーバーラップしないリングと、少なくとも１つの他のオーバーラップしないリングとを含む。
【００１１】
上の実施形態のいくつかにおいて、新しいオーバーラップしないリングの構築は、プロセッサを以下のようにプログラムすることを含む：ターゲットノードのうちの第１のターゲットノードで、一部だけのオーバーラップしないリングを初期化し、一部だけのオーバーラップしないリングにおける第２のターゲットノードと第２のターゲットノードの近傍ターゲットノードとの間の接続が、少なくとも１つの他のオーバーラップしないリングにおいて重複しないという判定に基づいて、ターゲットノードのうちの第２のターゲットノードを、一部だけのオーバーラップしないリングに付加し、一部だけのオーバーラップしないリングにおける第３のターゲットノードと第３のターゲットノードの近傍ターゲットノードとの間の接続が、少なくとも１つの他のオーバーラップしないリングにおいて重複しないという判定に基づいて、ターゲットノードのうちの第３のターゲットノードを、一部だけのオーバーラップしないリングに挿入する。
【００１２】
上の実施形態のいくつかにおいて、第２のターゲットノードは、ターゲットノードのサブセットからランダムに選択され、一部だけのオーバーラップしないリングにおける最初のノードおよび最後のノードによる接続が少なくとも１つの他のオーバーラップしないリングにおいて重複しないように、サブセットは、一部だけのオーバーラップしないリングの中にはないターゲットノードのメンバを含む。
【００１３】
上の実施形態のいくつかにおいて、第３のターゲットノードの挿入は、一部だけのオーバーラップしないリングにまだ追加されないでいるターゲットノードのいずれも、一部だけのオーバーラップしないリングに付加され得ないという判定に基づく。
【００１４】
上の実施形態のいくつかにおいて、ネットワークアーキテクチャの決定は、顧客サービスレベルの同意またはサービス品質の制約のうちの、少なくとも１つにさらに基づく。
【００１５】
第２の実施形態において、データを交換するためのスイッチングシステムが提供される。システムは、複数のオーバーラップしないリングを形成するように通信可能に接続された複数のノードを含むスイッチクラスタを含む。
【００１６】
上の実施形態のいくつかにおいて、スイッチクラスタは、実質的に３ホップネットワークを提供する。
【００１７】
上の実施形態のいくつかにおいて、システムは、さらに以下を含む：スイッチクラスタに通信可能に接続された第２のスイッチクラスタ。第２のスイッチクラスタは、第２の複数のオーバーラップしないリングを形成するように通信可能に接続された第２の複数のノードを含む。
【００１８】
上の実施形態のいくつかにおいて、システムは、さらに以下を含む：スイッチクラスタに通信可能に接続された第２のスイッチクラスタ。第２のスイッチクラスタは、フルメッシュトポロジを形成するように通信可能に接続された第２の複数のノードを含む。
【００１９】
上の実施形態のいくつかにおいて、システムは、第２の複数のオーバーラップしないリングを形成するように通信可能に接続された第２の複数のノードを含む、第２のスイッチクラスタをさらに含む。ここで、スイッチクラスタおよび第２の複数のノードは、ツリートポロジに配置される。
【００２０】
第３の実施形態において、スイッチクラスタを提供するための方法が提供される。方法は以下を含む：ターゲットノードの集合を決定するステップ、リングカウントを決定するステップ、ならびにターゲットノードの集合およびリングカウントに基づいて、ネットワークアーキテクチャを決定するステップであって、ネットワークアーキテクチャが、リングカウントと等しい複数のオーバーラップしないリングを形成するように通信可能に接続されたターゲットノードの集合を含む、決定するステップ。
【００２１】
上の実施形態のいくつかにおいて、方法は、ネットワーク成長閾値に基づいて、ネットワークアーキテクチャに新しいリングを追加するステップをさらに含む。
【００２２】
上の実施形態のいくつかにおいて、新しいリングを追加するステップは、ターゲットノードのうちの第２のターゲットノードに第１のターゲットノードを通信可能に接続するように、ターゲットノードのうちの第１のターゲットノードのポートをリダイレクトするステップを含む。
【００２３】
上の実施形態のいくつかにおいて、リングカウントは、性能基準に基づく。
【００２４】
上の実施形態のいくつかにおいて、ネットワークアーキテクチャを決定するステップは、以下を含む：少なくとも１つの他のオーバーラップしないリングに基づいて、新しいオーバーラップしないリングを構築するステップ。ここで、複数のオーバーラップしないリングは、新しいオーバーラップしないリングと、少なくとも１つの他のオーバーラップしないリングとを含む。
【００２５】
上の実施形態のいくつかにおいて、ネットワークアーキテクチャの決定は、顧客サービスレベルの同意またはサービス品質の制約のうちの、少なくとも１つにさらに基づく。
【００２６】
さまざまな実施形態は、添付の図面において示される。
【図面の簡単な説明】
【００２７】
【図１】例示的なデータセンタ１００Ａと、ネットワーク１００Ｂとを含む、データセンタネットワークアーキテクチャ１００Ａの一実施形態を示す図である。
【図２Ａ】柔軟なデータセンタネットワークアーキテクチャ２００Ａにおける例示的なスイッチクラスタ２６０のブロック図である。
【図２Ｂ】図２Ａのスイッチクラスタ２６０の一実施形態である、例示的なスイッチクラスタ２００Ｂの機能ブロック図である。
【図３Ａ】ノードにおける必要なコネクタの数および必要なネットワークリンクの数を、スーパークラスタとスイッチクラスタとで比較した図である。
【図３Ｂ】４つのオーバーラップしないリングに配置された６４ノードネットワークの考え得る構築の編集データを示す図である。
【図３Ｃ】４つのオーバーラップしないリングに配置された８０ノードネットワークの考え得る構築の編集データを示す図である。
【図４】図２Ｂのスイッチクラスタ２００Ｂを設計するための方法４００の一実施形態を示す流れ図である。
【図５】図４のステップ４６０に示されるような、新しいリングを構築するための方法５００の一実施形態を示す流れ図である。
【図６】図５のステップ５６０に示されるような、新しいノードを新しいリングに追加するための方法６００の一実施形態を示す流れ図である。
【図７】方法４００、５００、もしくは６００を実施するようにプログラムされた、図２Ｂのノードのうちの１つ、または汎用コンピュータなどの、さまざまな装置７００の一実施形態を概略的に示す図である。
【発明を実施するための形態】
【００２８】
理解を促進するために、同一の参照番号が、実質的に同じもしくは同様の構造、または実質的に同じもしくは同様の機能を有する要素を示すために使用されている。
【００２９】
本説明および図面は、本発明の原理を例証するにすぎない。したがって、当業者は、たとえ本明細書に明示的に説明されない、または示されなくても、本発明の原理を具体化し、本発明の範囲内に含まれる、さまざまな仕組みを考案できることが認識されるだろう。さらに、本明細書に列挙されるすべての例は、主に、読者が本発明の原理およびさらなる技術に対して本発明者によって貢献される概念を、理解するのを支援するための教育的な目的のためのみであることがはっきりと意図されており、それらの例は、そのような特に列挙された例および条件に限定されないものとして解釈されるべきである。追加的に、用語「または（ｏｒ）」は、本明細書で使用されるとき、別段そうでないと指示されていない限り（たとえば、「さもなければ（ｏｒ  ｅｌｓｅ）」または「あるいは、代替的に（ｏｒ  ｉｎ  ｔｈｅ  ａｌｔｅｒｎａｔｉｖｅ）」）、非排他的なｏｒを指す。また、いくつかの実施形態が１つまたは複数の他の実施形態と組み合わされて、新しい実施形態を形成できることから、本明細書で説明されるさまざまな実施形態は、必ずしも互いに排他的ではない。
【００３０】
さまざまな実施形態は、コスト（たとえば、ネットワークリンクの数）を削減し、同時に障害に対する回復力を提供してＱｏＳ要件（たとえば、ネットワークアーキテクチャをトラバースすることに起因したネットワーク遅延）を満たす、オーバーラップしないリング−メッシュネットワークトポロジを提供する方法および装置を提供する。とりわけ、クラスタに属するターゲットノードの集合が、Ｎ個のリングを通して接続される。各ノードは、全Ｎ個のリングのメンバであり、リングにおけるノード間のいずれのリンクも、別のリングにおいて重複しない。有利なことに、オーバーラップしないリング−メッシュトポロジは、障害に対する回復力、高い接続性、ならびに、メッシュトポロジおよびクラスタトポロジなどの他の知られたネットワークトポロジの２つのノード間の最短パスに匹敵するホップカウントを提供するために、各ノードにおけるコネクタおよび全体のネットワーク接続を、より少ない数しか要さない。
【００３１】
説明および図面では、データセンタのスイッチクラスタにおけるオーバーラップしないリング−メッシュトポロジの実施形態を示すが、オーバーラップしないリング−メッシュトポロジは、任意の好適なネットワークでノード間に接続性を提供するために使用されてもよいことが認識されるだろう。
【００３２】
図１は、例示的なデータセンタ１００Ａと、ネットワーク１００Ｂとを含む、データセンタネットワークアーキテクチャ１００Ａの一実施形態を示す。データセンタ１００Ａは、リソース１２０−１−１−１から１２０−ｙ−ｚ−５（総称して、リソース１２０）を含む。リソース１２０は、「ｙ」行に配置され、ここで各行には、通信パスを通してアクセスされるリソースのラック（たとえば、ラック１０５）の番号（たとえば、例証として「ｘ」または「ｙ」）が入っている。通信パスは、トップオブラックスイッチ１１０−１−１から１１０−ｙ−ｚ（総称して、ＴＯＲスイッチ１１０）のうちの適切な１つ、エンドオブロースイッチ１４０−１から１４０−ｎ（総称して、ＥＯＲスイッチ１４０）のうちの適切な１つ、レイヤ２アグリゲーションスイッチ１５０−１から１５０−ｎ（総称して、アグリゲーションスイッチ１５０）のうちの適切な１つ、および適切なリンク１３０−１から１３０−２（総称して、リンク１３０）（残りのリンクラベルは、明瞭にする目的のために省略されている）を介して、リソース１２０をネットワーク１００Ｂに通信可能に接続する。データセンタ１００Ａとネットワーク１００Ｂとの通信は、アグリゲーションスイッチ１５０のうちの１つ、ルータ１６０−１から１６０−３（総称して、ルータ１６０）のうちの適切な１つ、および適切なリンク１３０を介している。データセンタは、任意の好適な構成にアーキテクトされてよく、データセンタ１００Ａは、例証目的のために使用されている１つの例示的なアーキテクチャにすぎないことを認識されたい。たとえば、通信パスは、リソース１２０とネットワーク１００Ｂとの間でデータを交換するためのデバイス（たとえば、スイッチ、ルータ、ハブなど）の任意の好適な構成を含むことができる。
【００３３】
ＴＯＲスイッチ１１０は、関連付けられたラックのリソースと、適切なＥＯＲスイッチとの間で、データを交換する。たとえば、ＴＯＲスイッチ１１０−１−１は、適切なＥＯＲスイッチ（たとえば、ＥＯＲスイッチ１４０−１）を介して、ラック１０５のリソースからネットワーク１００Ｂへとデータを交換する。
【００３４】
リソース１２０は、プロセッサ、メモリ、ストレージ、またはネットワーキングなどの任意の好適なデバイスであってよい。各ラック（たとえば、ラック１０５）には５つのリソースが示されているが、各ラックは、より少ない、またはより多いリソースを含むことができ、各ラックが、異なるタイプの、または異なる数のリソースを収容することができることを認識されたい。いくつかの実施形態において、アプリケーションは、仮想マシン（ＶＭ）または仮想化されたストレージなどの、複数のコンポーネントインスタンスによってサポートされてよい。これらのコンポーネントインスタンスは、データセンタネットワークアーキテクチャ１００Ａ内で接続された多様なリソースを含むことができる。
【００３５】
示されるように、各リソース１２０は、行−列−リソース番号による命名法を使用してラベル付けされている。たとえば、リソース１２０−２−３−４は、第２の行および第３の列に存するラックにおける４番目のリソースとなる。
【００３６】
ＥＯＲスイッチ１４０は、関連付けられたＴＯＲスイッチと、適切なアグリゲーションスイッチとの間で、データを交換する。たとえば、ＥＯＲスイッチ１４０−１は、適切なアグリゲーションスイッチ（たとえば、アグリゲーションスイッチ１５０−１または１５０−２）を介して、ＴＯＲスイッチ１１０−１−１より２１０−１−ｘからネットワーク１００Ｂへとデータを交換する。
【００３７】
アグリゲーションスイッチ１５０は、関連付けられたＥＯＲスイッチと、適切なルータとの間で、データを交換する。たとえば、ＴＯＲスイッチ１１０−１−１は、適切なＥＯＲスイッチ（たとえば、ＥＯＲスイッチ１４０−１）および適切なアグリゲーションスイッチ（たとえば、アグリゲーションスイッチ１５０−１または１５０−２）を介して、ラック１０５のリソースからネットワーク１００Ｂへとデータを交換する。
【００３８】
ルータ１６０は、適切なアグリゲーションスイッチを介して、ネットワーク１００Ｂと、データセンタ１００Ａとの間で、データを交換する。たとえば、ルータ１６０−１は、アグリゲーションスイッチ１５０−１を介して、ネットワーク１００Ｂからデータセンタ１００Ａへとデータを交換することができる。
【００３９】
ネットワーク１００Ｂは、任意の数のアクセスノードとエッジノード、およびネットワークデバイス、ならびに任意の数および構成のリンク（明瞭にする目的のために示されていない）を含む。さらに、ネットワーク１００Ｂは、任意の組合せおよび任意の数の、以下を含んだワイヤレスまたはワイヤ線ネットワークを含むことができることを認識されたい：ＬＴＥ、ＧＳＭ（登録商標）、ＣＤＭＡ、ローカルエリアネットワーク（ＬＡＮ）、ワイヤレスローカルエリアネットワーク（ＷＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、など。
【００４０】
いくつかの実施形態において、ＴＯＲスイッチ１２０またはＥＯＲスイッチ１４０は、イーサネット（登録商標）スイッチである。
【００４１】
いくつかの実施形態において、ＴＯＲスイッチ１２０またはＥＯＲスイッチ１４０は、冗長するように配置されてよい。たとえば、ラック１０５は、２つまたはそれ以上のＴＯＲスイッチ１１０によって供給されてよい。
【００４２】
いくつかの実施形態において、アグリゲーションスイッチ１５０は、レイヤ２イーサネットスイッチである。
【００４３】
図２Ａは、柔軟なデータセンタネットワークアーキテクチャ２００Ａにおける例示的なスイッチクラスタ２６０のブロック図を示す。柔軟なデータセンタネットワークアーキテクチャ２００Ａは、図１で上述されたような、リソース１２０と、アグリゲーションスイッチ１５０とを含む。スイッチクラスタ２６０は、本明細書で説明するように、リソース１２０とアグリゲーションスイッチ１５０との間でデータを交換する、いくつかのターゲットノードを含む。
【００４４】
スイッチクラスタ２６０は、任意の好適な構成にアーキテクトされてよく、スイッチクラスタ２６０は、例証目的のために使用されている１つの例示的なアーキテクチャにすぎないことを認識されたい。いくつかの実施形態において、スイッチクラスタ２６０は、図１からのＴＯＲスイッチ１１０を含む（すなわち、かつ図２Ａに示されるように、ＥＯＲスイッチ１４０を含まない）ことができる。いくつかの実施形態において、スイッチクラスタ２６０は、図１からのＥＯＲスイッチ１４０を含むことができる。
【００４５】
いくつかの実施形態において、柔軟なデータセンタネットワークアーキテクチャ２００Ａは、より多くのスイッチクラスタ２６０を収容することができる。これらの実施形態のいくつかにおいて、ＴＯＲスイッチまたはＥＯＲスイッチは、複数のスイッチクラスタに配置されてよい。これらの実施形態のいくつかにおいて、複数のスイッチクラスタのうちの１つまたは複数は、特定のサービス品質（ＱｏＳ）基準をサポートするように設計されてよい。たとえば、仮想マシンまたは仮想化されたストレージが、それらのＱｏＳ要件またはそれらのピアの場所に応じて、作成時に、適切なクラスタに設置されてもよい。
【００４６】
いくつかの実施形態において、スイッチクラスタは、ツリーネットワークトポロジなどの従来のネットワークトポロジに加えて配備されてもよい。有利なことに、スイッチクラスタの配置は、ツリーネットワークの縦方向リンクからのトラフィックをオフロードさせることができる。
【００４７】
図２Ｂは、図２Ａのスイッチクラスタ２６０の一実施形態である、例示的なスイッチクラスタ２００Ｂの機能ブロック図を示す。スイッチクラスタ２００Ｂは、ノードの集まり、ノード１からノード１７（総称して、ノード）を含み、ノードは、リンク、Ｌｉｎｋ  Ｒｉｎｇ１−１からＬｉｎｋ  Ｒｉｎｇ３−１（総称して、リンク）を介して、リングネットワーク、Ｒｉｎｇ１、Ｒｉｎｇ２、およびＲｉｎｇ３（総称して、リング）の中で相互接続されている。
【００４８】
ノードは、任意のタイプの、または任意の数の好適なスイッチを含むことができる。とりわけ、スイッチクラスタ２００Ｂのノードは、Ｎ個の「オーバーラップしないリング」を通して接続され、各ノードは、リングの全Ｎのメンバである。たとえば、実施形態または図２Ｂにおいて、ノードは、ＴＯＲスイッチ１２０の一部もしくは全部、またはＥＯＲスイッチ１４０の一部もしくは全部を含むことができる。本明細書で言及されるとき、「オーバーラップしないリング」とは、１つのリングにおけるノード間のいずれのリンクも、別のリングにおいて重複しないことを意味する。ここでは１７個のノードが示されているが、スイッチクラスタ２００Ｂは、それよりも少ない、またはそれよりも多いノードを含むことができることを認識されたい。ノードは、スイッチクラスタを構成するターゲットノード以外のコンポーネントへの接続を含むことができることを認識されたい。たとえば、ノードは、（ｉ）リソース（たとえば、図２のリソース１２０）、（ｉｉ）アグリゲーションスイッチ（たとえば、図２のアグリゲーションスイッチ１５０）、（ｉｉｉ）他のスイッチングノード（たとえば、図１のＴＯＲスイッチ１１０が複数のスイッチクラスタにおいてクラスタ化される場合）、または（ｉｖ）その他、に接続することができる。
【００４９】
リンクは、以下のような、１つまたは複数の通信チャネル上の通信をサポートする：ワイヤレス通信（たとえば、ＬＴＥ、ＧＳＭ、ＣＤＭＡ、ｂｌｕｅｔｏｏｔｈ）、フェムトセル通信（たとえば、ＷｉＦｉ）、パケットネットワーク通信（たとえば、ＩＰ）、ブロードバンド通信（たとえば、ＤＯＣＳＩＳおよびＤＳＬ）、ストレージ通信（たとえば、Ｆｉｂｒｅ  Ｃｈａｎｎｅｌ、ｉＳＣＳＩ）など。単一接続として表されているが、リンクは、任意の数の、または任意の組合せの通信チャネルであってよいことを認識されたい。
【００５０】
示されるように、スイッチクラスタ２００Ｂは、３つの「オーバーラップしないリング」に配置された１７のノードを含む、３ホップネットワークである。３つのリング、Ｒｉｎｇ１、Ｒｉｎｇ２、およびＲｉｎｇ３は、実線リンク（たとえば、Ｌｉｎｋ  Ｒｉｎｇ１−１）、破線リンク（たとえば、Ｌｉｎｋ  Ｒｉｎｇ２−１）、および点線リンク（たとえば、Ｌｉｎｋ  Ｒｉｎｇ３−１）のそれぞれを使用して示されている。示された「オーバーラップしないリング」は以下である：
ＲＩＮＧ１＝｛１，２，３，４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，１６，１７｝
ＲＩＮＧ２＝｛１，１４，３，８，２，９，７，１６，４，１７，１２，６，１１，５，１３，１０，１５｝
ＲＩＮＧ３＝｛１，７，２，４，９，１６，１１，１３，６，１４，１０，５，１７，３，１２，１５，８｝
ここで、ノード１−１７は、数字で１−１７としてそれぞれ参照され、表記｛ｎ１，ｎ２，ｎ３，ｎ４，．．．，ｎｋ｝はリングを表し、ここで、近傍するノードは、二方向で接続され、ｎｋは、ｎ１に戻って二方向で接続される。
【００５１】
有利なことに、オーバーラップしないリングの配置においてノードを接続することは、ルート多様性、回復力、および高い接続性を提供する。
【００５２】
図３Ａを参照すると、スイッチクラスタ２００Ｂは、有利なことに、従来のスーパークラスタ配置に比べて、ノードにおける少ないコネクタと、少ないネットワークリンクしか収容せず、しかも同時に、単一の障害（たとえば、ノードまたはリンク）に対する保護を提供し、匹敵するスループット（たとえば、匹敵するホップカウント）を提供する。
【００５３】
本明細書で言及されるとき、「Ｎホップ」ネットワークは、スイッチクラスタにおいて、実質的にノードのあらゆる結合の間にＮホップまたはそれ以下の接続性を提供し、ここで実質的とは、９９パーセントよりも大きいことを意味する。言い換えれば、ｎホップスイッチクラスタの構築は、ノードペアの１つまたは複数の間の通信が、Ｎ個のホップよりも多いホップを要する、可能なスイッチクラスタ構築を含んでよい。たとえば、図３Ｂを参照すると、４つのオーバーラップしないリングを使用して構築された、３ホップ６４ノードネットワークについての１０００の考え得るリング構築のコンピュータシミュレーションでは、全体の考え得るノード結合のうち、４ホップを要するノード結合のパーセンテージが、わずかに０．００％から０．１５％の範囲であったことが推定された。２つ目の例において、図３Ｃを参照すると、４つのオーバーラップしないリングを使用して構築された、３ホップ８０ノードネットワークについての１０００の考え得るリング構築のコンピュータシミュレーションでは、全体の考え得るノード結合のうち、４ホップを要するノード結合のパーセンテージが、わずかに０．００％から０．４７％の範囲であったことが推定された。
【００５４】
スイッチクラスタ２００Ｂは、３ホップネットワークとして示されているが、スイッチクラスタ２００Ｂは、それよりも少ない、またはそれよりも多いホップであってもよいことを認識されたい。いくつかの実施形態において、スイッチクラスタ２００Ｂは、コストまたは性能基準に基づいて設計される。より大きなホップサイズのネットワークでは、ノードにおけるコネクタの数およびネットワークにおけるリンクの数はより少なくなる（すなわち、よりよいコスト効率）が、性能はより劣ることになることを認識されたい。
【００５５】
いくつかの実施形態において、ネットワークのトポロジを決定し、データ（たとえば、パケット）を転送する際に２つのノード間の最短パスを使用するために、ノードは、ＩＳＩＳ（ＩＳＯ１０５８９）などのルーティングプロトコルを含む。
【００５６】
いくつかの実施形態において、新しいリングは、確立された要件を満たすよう、ノード間のホップカウントを維持するために、ネットワーク成長がある閾値（たとえば、ノードの数）を超えてから追加されてよい。これらの実施形態のいくつかにおいては、リングの最大数が設定されてよい。これらの実施形態において、ノードは、リングの最大数の設定値までアップグレードをサポートするように構成される。
【００５７】
いくつかの実施形態において、ノードは、ピアスイッチまたはサーバのいずれかへの接続性をサポートするように構成される（たとえば、ポート）。これらの実施形態のいくつかにおいて、（たとえば、新しいオーバーラップしないリングをスイッチクラスタの中に追加するために）サーバに対するポートがリダイレクトされ、ピアスイッチへの接続性をサポートすることができる。
【００５８】
図４は、図２Ｂのスイッチクラスタ２００Ｂを設計するための方法４００の一実施形態を示す流れ図を表す。方法は、スイッチクラスタを初期化するステップ（ステップ４２０）と、ステップ４２０の初期化に基づいて「オーバーラップしないリング」を構築するステップ（ステップ４６０）と、スイッチクラスタ構築が完了されていないことを判定するステップ（ステップ４４０）とを含む。
【００５９】
方法４００において、ステップ４２０は、スイッチクラスタを初期化するステップを含む。とりわけ、「オーバーラップしないリング」の数（すなわち、ＲｉｎｇＣｏｕｎｔ）が決定される。いくつかの実施形態において、最初のリングもまた決定される。これらの実施形態のいくつかにおいて、構築された最初のリングは、｛１，２，．．．，ｋ｝となる。ここで、ｋは、ノードの数である。
【００６０】
方法４００において、ステップ４４０は、スイッチクラスタの構築が完了しているかどうかを判定するステップを含む。とりわけ、方法を実施する装置は、構築されたリングの数（すなわち、ＲｉｎｇｓＣｏｎｓｔｒｕｃｔｅｄ）が、ＲｉｎｇＣｏｕｎｔと等しいかどうかを判定する。ＲｉｎｇｓＣｏｎｓｔｒｕｃｔｅｄ≧ＲｉｎｇＣｏｕｎｔである場合、方法は、ステップ４９５へと進み、そうでない場合、方法は、ステップ４６０へと進む。
【００６１】
方法４００において、ステップ４６０は、新しい「オーバーラップしないリング」を構築するステップを含む。完了時、方法は、ステップ４４０に戻る。
【００６２】
ステップ４２０のいくつかの実施形態において、ＲｉｎｇＣｏｕｎｔの値は、ユーザによって設定される。
【００６３】
ステップ４２０のいくつかの実施形態において、ＲｉｎｇＣｏｕｎｔの値は、スイッチクラスタにおけるターゲットノードの数に基づく。これらの実施形態のいくつかにおいて、ＲｉｎｇＣｏｕｎｔの値はさらに、性能基準に基づく。たとえば、図３Ｃを参照して、最小数の４ホップノード間結合（たとえば、許可される４ホップ結合なし）を満たす、または平均ホップ閾値（たとえば、２．２５よりも少ない）を満たす、リング構築が満たされ得ない場合、ＲｉｎｇＣｏｕｎｔは（たとえば、図３Ｂの例では、４から５に）増加してよい。
【００６４】
ステップ４２０のいくつかの実施形態において、ＲｉｎｇＣｏｕｎｔの値は、以下の式に基づく：
［Ｅ．１］ＲｉｎｇＣｏｕｎｔ≦ＩＮＴ（ｋ／８＋１）
ここで、ｋはノードの数であり、ＩＮＴ（）は、演算の整数値を戻す関数である。有利なことに、制限［Ｅ．１］が、重複リンクを作成せずにリングの作成を可能にすることを確実にする。
【００６５】
いくつかの実施形態において、スイッチクラスタアーキテクチャは、ネットワーク成長の結果として変更される。これらの実施形態において、ネットワークに追加されるノードは、本明細書で説明された方法を使用して、既存のスイッチクラスタの中に挿入されてよい。これらの実施形態のいくつかにおいて、新しいノードは、リング１から開始して１リングずつ、既存のリングに挿入されることになる。これらの実施形態のいくつかにおいて、最初のリングの場合、新しいノードは、リングの最後に付加されてよい。
【００６６】
いくつかの実施形態において、方法は、ノード間の最短パスを決定するステップをさらに含む。とりわけ、方法を実施する装置が、ステップ４４０でスイッチクラスタが構築されたと判定した場合に、ノード間の最短パスまたはホップカウントが計算され得る。
【００６７】
いくつかの実施形態において、方法を実施する装置は、方法を複数回実行する。これらの実施形態のいくつかにおいて、既定の閾値カウントが、方法が行われることになる回数を定義する。これらの実施形態のいくつかにおいて、方法が行われる回数は、既定の性能閾値に基づく（たとえば、性能基準閾値が満たされるまで方法を実行する）。これらの実施形態のいくつかにおいて、回数は、既定の閾値カウントまたは性能基準閾値に基づく（たとえば、性能基準閾値が満たされるまで、または行われる既定の閾値数が満たされるまで、方法を実行する）。性能基準は、以下のような任意の好適な測定基準であってよい：（ｉ）（たとえば、ネットワークのための平均ホップカウントを最小限にするための、またはノード間の総計最大ホップカウントを最小限にするための）ホップカウント、（ｉｉ）アクセス遅延、（ｉｉｉ）コスト、（ｉｖ）顧客サービスレベルの同意またはサービス品質の制約（たとえば、リソースへの１つまたは複数のノードの間のノード間接続が、より少ないホップカウントで固定されるよう要求されることがある）、（ｖ）リソーストポロジ（たとえば、１つのリソースラックの中のリソースが、好ましくはより少ないホップを介して、別のリソースラックに接続されてよい）、（ｖｉ）Ｎホップネットワークの性能特性（たとえば、Ｎ個よりも多いホップを要求するノードペアがない厳密なＮホップネットワーク、または、＞Ｎ個のホップを要求できるノードペアの許可される最大パーセンテージ）、または（ｖｉｉ）その他。たとえば、方法を１０００回実行して、図３Ｂに示された結果を達成する方法を実施する装置は、最も少ない平均ホップによる配置、または３またはそれ以上のホップを要求する最小量のノード間結合による配置を選ぶことができる。別の例においては、スイッチクラスタの選択を、指定ノードと別のノードとの間の接続が最小ホップカウント（たとえば、図２Ｂのノード１とノード７との間の１ホップ）を満たす配置に制限する、制約が課されてもよい。
【００６８】
いくつかの実施形態において、入力パラメータ（たとえば、リングの数もしくはノードの数）、またはプログラミングパラメータ（たとえば、プログラムの繰り返しの数）が選択される、または調整されてよい。たとえば、厳密なＮホップネットワークを要求する性能特性を満たすために、リングの数が増やされてもよい。
【００６９】
いくつかの実施形態において、ステップ４６０は、次のリングを構築するために、従来の古典的な最適化技法を使用するステップを含む。従来の古典的な最適化技法は、所望の目標または目的を最もよく達成する措置を決定するステップを伴う。目標または目的を最もよく達成する措置は、目的関数の値を最大化する、または最小化することによって決定されてよい。いくつかの実施形態において、目的関数の目標または基準は、コストを最小限にすること、または遅延を最小限にすること（たとえば、ホップカウント、またはアクセス遅延を最小限にすること）であってよい。
【００７０】
問題は、以下のように表現されてよい：
最適化：
［Ｅ．２］ｙ＝ｆ（ｘ１，ｘ２，．．．，ｘｎ）
以下を条件として：
【００７１】
【数１】
2015529026.tif 000003
【００７２】
ここで、式Ｅ．２は、目的関数であり、式Ｅ．３は、解決策に課される制約の集合を構成する。ｘｉ変数、ｘ１，ｘ２，．．．，ｘｎは、決定変数の集合を表現し、ｙ＝ｆ（ｘ１，ｘ２，．．．，ｘｎ）は、これらの決定変数によって表された目的関数である。目的関数は、最大化または最小化されてよいことを認識されたい。
【００７３】
図５は、図４のステップ４６０に示されるような、新しいリングを構築するための方法５００の一実施形態を示す流れ図を表す。方法は、新しいリングを初期化するステップ（ステップ５２０）と、ステップ５２０の初期化に基づいて、新しいノードをリングに追加するステップ（ステップ５６０）と、リング構築が完了されていないという判定（ステップ５４０）とを含む。
【００７４】
方法５００において、ステップ５２０は、新しいリングを初期化するステップを含む。とりわけ、部分的に形成されるリングを作成するためにノードが選択される。いくつかの実施形態において、ノード１が選択される。
【００７５】
方法５００において、ステップ５４０は、新しい「オーバーラップしないリング」の構築が完了しているかどうかを判定するステップを含む。とりわけ、方法を実施する装置は、ノードのすべてが新しいリングに追加されているかどうかを判定する。すべてのノードが新しいリングに追加されている場合、方法は、ステップ５９５へと進み、そうでない場合、方法は、ステップ５６０へと進む。
【００７６】
方法５００において、ステップ５６０は、新しいノードをリングに追加するステップを含む。とりわけ、方法を実施する装置は、新しいノードを一部だけのリングに挿入するとき、または付加するとき、新しく追加されるノードとその近傍ノードとの間に作成された新しいリンクが、それ以前に形成された「オーバーラップしないリング」のいずれにおいても、リンクの重複でないことを確実にする。
【００７７】
ステップ５６０のいくつかの実施形態において、ノードは、新しいノードが付加され得なくなる（たとえば、新しいリンクの１つまたは双方が、スイッチクラスタの別のオーバーラップしないリングにおいて重複となる）まで、付加される。
【００７８】
図６は、図５のステップ５６０に示されるような、新しいノードを新しいリングに追加するための方法６００の一実施形態を示す流れ図を表す。方法は、候補ノードの集合「Ｃ」を決定するステップ（ステップ５）と、候補ノードが利用可能であるという判定（ステップ６２０）に基づいて、一部だけのリングに付加されてよいノードの集合「Ａ」を決定するステップ（ステップ６３０）とを含む。集合「Ａ」が空でない場合、集合「Ａ」からノードのうちの１つが選択されて、リングに付加される。集合「Ａ」が空である場合、方法は、集合「Ｃ」から第１のノード（ｆｉｒｓｔ  ｎｏｄｅ）を選択し、Ｆｉｒｓｔ  Ｎｏｄｅが他の構築されたリングの近傍であるノードの排除リスト「Ｅｘ（Ｆｉｒｓｔ  Ｎｏｄｅ）」を決定し（ステップ６６０）、方法は、構築中の一部だけのリングにおけるノードの集合「Ｐ」から、集合Ｅｘ（Ｆｉｒｓｔ  Ｎｏｄｅ）のメンバではない２つの近傍ノードを選択し、（ステップ６７０）、選択された近傍ノードの間に、Ｆｉｒｓｔ  Ｎｏｄｅが挿入される（ステップ６８０）。
【００７９】
方法６００において、ステップ６１０は、候補ノードの集合「Ｃ」を決定するステップを含む。とりわけ、集合「Ｃ」は、一部だけのリングにまだ追加されていないノードのすべてからなる。
【００８０】
方法６００において、ステップ６２０は、集合「Ｃ」が空であるかどうかを判定するステップを含む。集合「Ｃ」が空である場合、全リングが構築されており、方法は、ステップ６９５へと進み、そうでない場合、方法は、ステップ６３０へと進む。
【００８１】
方法６００において、ステップ６３０は、構築中の「オーバーラップしないリング」に付加されてよいノードの集合「Ａ」を決定するステップを含む。とりわけ、方法を実施する装置は、構築中のリング（すなわち、構築されたリングは「オーバーラップしないリングとなる）に付加されてよい集合「Ｃ」のメンバを決定する。
【００８２】
方法６００において、ステップ６４０は、集合「Ａ」が空であるかどうかを判定するステップを含む。集合「Ａ」が空である場合、方法は、ステップ６６０へと進み、そうでない場合、方法は、ステップ６５０へと進む。
【００８３】
方法６００において、ステップ６５０は、集合「Ａ」から付加ノードを選択するステップと、付加ノードを構築中のリングに付加するステップとを含む。
【００８４】
方法６００において、ステップ６６０は、集合「Ｃ」から第１のノードを選択するステップと、集合「Ｅｘ（ｆｉｒｓｔ  ｎｏｄｅ）」を決定するステップとを含む：ここで、Ｅｘ（）は、ＴａｒｇｅｔＮｏｄｅを引数として取り、かつ他の構築された「オーバーラップしないリング」においてＴａｒｇｅｔＮｏｄｅの近傍であるノードのリストを戻す関数である。
【００８５】
方法６００において、ステップ６７０は、構築中の一部だけのリングにおけるノードであって、集合Ｅｘ（ｆｉｒｓｔ  ｎｏｄｅ）のメンバではない、集合「Ｐ」からの２つの近傍ノードを選択するステップを含む。
【００８６】
方法６００において、ステップ６８０は、２つの選択された近傍ノードの間に、第１のノードを挿入するステップを含む。
【００８７】
ステップ６３０のいくつかの実施形態において、式［Ｅ．４］が、集合「Ａ」を形成するために使用される。
【００８８】
［Ｅ．４］ｓｅｔ“Ａ”＝“Ｃ”−Ｅｘ（ＦｉｒｓｔＮｏｄｅＩｎＲｉｎｇ）−Ｅｘ（ＬａｓｔＮｏｄｅＩｎＲｉｎｇ）
ここで、「Ｃ」は、候補ノードの集合であり、Ｅｘ（）は、ＴａｒｇｅｔＮｏｄｅを引数として取り、かつ他の構築された「オーバーラップしないリング」におけるＴａｒｇｅｔＮｏｄｅの近傍であるノードのリストを戻す関数であり、ＦｉｒｓｔＮｏｄｅＩｎＲｉｎｇは、構築中のリングにおける第１のノードであり、ＬａｓｔＮｏｄｅＩｎＲｉｎｇは、構築中のリングにおける最後のノードである。
【００８９】
これらの実施形態のいくつかにおいて、第２のノードが、集合「Ｐ」から選択される。いくつかのさらなる実施形態において、Ｅｘ（ｆｉｒｓｔ  ｎｏｄｅ）のメンバではない２つの連続したノードを見つけるために、「Ｐ」のメンバノードは、第２のノードを開始ポイントとして使用してトラバースされる。
【００９０】
ステップ６５０、６６０、または６７０のいくつかの実施形態において、ノードはランダムに選択される。とりわけ、ステップ６５０で、付加ノードが、集合「Ａ」からランダムに選択されてよく、ステップ６６０で、第１のノードが、集合「Ｃ」からランダムに選択されてよく、またはステップ６７０で、第２のノードが、集合「Ｐ」からランダムに選択されてよい。
【００９１】
いくつかの実施形態において、ステップ６３０、６４０、および６５０は、同時に実施されてよい。これらの実施形態のいくつかにおいて、集合「Ｃ」におけるランダムノードが、集合「Ｃ」におけるノードをトラバースして、ノードが付加されてもよいかどうかを判定するために、開始ポイントとして選ばれてよい。方法を実施するための装置は、付加されることが可能であると判定された第１のノードで停止して、そのノードを一部だけのリング「Ｐ」に付加することができる。集合「Ｃ」をトラバースした後にもノードが発見されない場合、方法は、ステップ６７０へと進むことができる。これらの実施形態のいくつかにおいて、ステップ６１０および６２０もまた同時に実施されてよい。とりわけ、完全な集合「Ｃ」は、集合「Ｃ」に追加されるノードがステップ６５０で付加されてもよいかどうかを判定するために、ステップ６３０に進むより前に構築されることはできない。
【００９２】
方法３００および４００で示されたステップが、主に、特定のシーケンスで表され、説明されたが、ステップは任意の好適なシーケンスで実施されてよいことを認識されたい。さらに、１つのステップによって識別された複数のステップはまた、そのシーケンスの１つまたは複数の他のステップにおいて実施されてもよく、または２つ以上のステップの共通の措置が、一度のみ実施されてもよい。
【００９３】
上述されたさまざまな方法のステップは、プログラムされたコンピュータによって実施され得ることを認識されたい。本明細書では、いくつかの実施形態はまた、プログラムストレージデバイス、たとえば、データストレージ媒体を含むよう意図され、これらは、マシン可読もしくはコンピュータ可読であり、マシン実行可能な、もしくはコンピュータ実行可能なプログラムの命令を符号化し、ここで、前記命令は、前記上述された方法のステップのうちのいくつか、または全部を実施する。プログラムストレージデバイスは、たとえば、デジタルメモリ、磁気ディスクおよび磁気テープなどの磁気ストレージ媒体、ハードドライブ、また光学的に可読なデータストレージ媒体であってよい。実施形態はまた、上述された方法の前記ステップを実施するようにプログラムされたコンピュータを含むよう意図される。
【００９４】
図２Ｂおよび図４−図６に戻って参照すると、リングを構築し、構築中のリングの中にノードを追加する例が、以下で与えられる。
【００９５】
図６で示されるように、スイッチクラスタ２００Ｂは、１７のノードを含む。Ｒｉｎｇ１およびＲｉｎｇ２は、図２Ｂで示されたように既に構築されたものと想定して、以下で説明される。
【００９６】
２つの構築されたリングは、以下である：
ＲＩＮＧ１＝｛１，２，３，４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，１６，１７｝
ＲＩＮＧ２＝｛１，１４，３，８，２，９，７，１６，４，１７，１２，６，１１，５，１３，１０，１５｝
【００９７】
図４のステップ４２０を参照すると、方法を実施する装置は、［Ｅｑ．１］：ＲｉｎｇＣｏｕｎｔ＝ＩＮＴ（１７／８＋１）＝３を使用して、ＲｉｎｇＣｏｕｎｔが３であることを決定することができる。
【００９８】
図４のステップ４４０で、方法を実施する装置は、新しいリングが構築されるべきであると判定することになり、ステップ４６０へと進む。
【００９９】
図５のステップ５２０を参照すると、方法を実施する装置は、集合「Ｐ」（一部だけのリング）を｛１｝として初期化することによって、構築中の新しいリング（たとえば、Ｒｉｎｇ３）を初期化することができる。Ｒｉｎｇ３に追加されるべきノードは１７個あるので、すべてのノードが追加されているというわけではなく（ステップ５４０）、方法はステップ５６０へと進む。
【０１００】
図６のステップ６１０を参照すると、方法を実施する装置は次いで、候補ノードの集合「Ｃ」を決定することができる。この例で、「Ｃ」＝｛２，３，４，５，６，７，８，９，１０，１１，１２，１３，１４，１５，１６，１７｝（すなわち、この段階でノード１からなる集合「Ｐ」に既にあったノードを除く、ノードのすべて）である。集合「Ｃ」は空ではないので（ステップ６２０）、装置は、集合「Ａ」（集合「Ｐ」に付加されてよいノード）を決定する。式２を使用して、集合「Ａ」が、｛３，４，５，６，７，８，９，１０，１１，１２，１３，１６｝であると決定される。集合「Ａ」は空ではないので（ステップ６４０）、方法は、ステップ６５０へと進み、Ｒｉｎｇ３に付加するための集合「Ａ」からノードを選択する。集合「Ａ」からのランダムな選択が行われ、ノード７が選択されたものと想定する。したがって、一部だけのリング３は、現在｛１，７｝である。
【０１０１】
図６（ステップ６９５）から戻って、方法を実施する装置は、すべてのノードが追加されているわけではないことを判定し（図５のステップ５４０）、別のノードを追加するためにステップ５６０へと進む。ここで、方法を実施する装置は、集合「Ｐ」が｛１，７，４，９，１６，１１，１３，６，１０，５，３，１２，８｝になるまで、いくつかの同様のステップを通して同じように動作し、別のノードを追加するために、図６のステップ６１０に戻ったものと想定する。
【０１０２】
図６のステップ６１０を参照すると、方法を実施する装置は次いで、候補ノードの集合「Ｃ」を決定することができる。本例におけるこの時点では、「Ｃ」＝｛２，１４，１５，１７｝（すなわち、１７の候補ノード（集合「Ｐ」のメンバであるノード）のメンバ集合）である。集合「Ｃ」は空ではないので（ステップ６２０）、装置は、集合「Ｐ」に付加されてよいノードである、集合「Ａ」を決定する。式２を使用して、集合「Ａ」は、空であると判定される。集合「Ａ」は空なので（ステップ６４０）、方法は、ステップ６６０へと進み、集合「Ｃ」からノードを選択し、Ｅｘ（選択されたノード）を決定する。集合「Ｃ」からのランダムな選択が行われ、ノード１４が選択されたものと想定する。ノード１４について、Ｅｘ（１４）＝｛１，３，１３，１５｝である。方法を実施する装置は、ステップ６７０へと進む。この例において、Ｅｘ（１４）のメンバではない、「Ｐ」における２つの近傍ノードを選択するために、ノード１１が、開始ポイントとしてランダムに選択されたものと想定する。ノード１１から集合「Ｐ」を（ラップアラウンドで）トラバースすると、装置は、ノード６およびノード１０が、Ｅｘ（１４）にはない、集合「Ｐ」の近傍ノードであることを判定する。したがって、ノード１４は、ノード６とノード１０との間に挿入され、集合「Ｐ」は、｛１，７，４，９，１６，１１，１３，６，１４，１０，５，１２，８｝となる。
【０１０３】
図６（ステップ６９５）から戻ると、方法を実施する装置は、すべてのノードが追加されているわけではないことを判定し（図５のステップ５４０）、別のノードを追加するためにステップ５６０へと進む。上記と同様に、方法を実施する装置は、図２Ｂに示されたようなＲｉｎｇ３、すなわち｛１，７，２，４，９，１６，１１，１３，６，１４，１０，５，１７，３，１２，１５，８｝を生じるように、Ｒｉｎｇ３の構築が完了するまで続行する。
【０１０４】
図７は、方法４００、５００、もしくは６００を実施するようにプログラムされた、図２Ｂのノードのうちの１つ、または汎用コンピュータなどの、さまざまな装置７００の一実施形態を概略的に示す。装置７００は、プロセッサ７１０、データストレージ７１１、およびオプションで、Ｉ／Ｏインターフェース７３０を含む。
【０１０５】
プロセッサ７１０は、装置７００の動作を制御する。プロセッサ７１０は、データストレージ７１１と協働する。
【０１０６】
データストレージ７１１は、ネットワークトポロジなどのプログラムデータを適宜格納することができる。データストレージ７１１はまた、プロセッサ７１０によって実行可能なプログラム７２０を格納する。
【０１０７】
プロセッサ実行可能なプログラム７２０は、スイッチクラスタ決定プログラム７２１、新リング決定プログラム７２３、新ノード決定プログラム７２５、またはオプションで、Ｉ／Ｏインターフェースプログラム７２７を含むことができる。プロセッサ７１０は、プロセッサ実行可能プログラム７２０と協働する。
【０１０８】
Ｉ／Ｏインターフェース７３０は、プロセッサ７１０およびＩ／Ｏインターフェースプログラム７２７と協働して、任意の好適な通信チャネル上での通信をサポートする。たとえば、Ｉ／Ｏインターフェース７３０は、決定されたスイッチクラスタまたはその一部分を、ネットワーク管理システムまたは図２Ｂのノードのうちの１つまたは複数に伝えるために使用されてよい。
【０１０９】
スイッチクラスタ決定プログラム７２１は、上で説明したような、図４の方法４００のステップを実施する。
【０１１０】
新リング決定プログラム７２３は、上で説明したような、図５の方法５００のステップを実施する。
【０１１１】
新ノード決定プログラム７２５は、上で説明したような、図６の方法６００のステップを実施する。
【０１１２】
いくつかの実施形態において、プロセッサ７１０は、プロセッサ／ＣＰＵコアなどのリソースを含むことができ、Ｉ／Ｏインターフェース７３０は、任意の好適なネットワークインターフェースを含むことができ、またはデータストレージ７１１は、メモリもしくはストレージデバイスを含むことができる。さらに、装置７００は、以下のような任意の好適な物理ハードウェア構成であってよい：１つまたは複数のサーバ、プロセッサ、メモリ、ネットワークインターフェース、またはストレージデバイスなどのコンポーネントからなるブレード。これらの実施形態のいくつかにおいて、装置７００は、リソースが互いにリモートであるクラウドネットワークリソースを含むことができる。
【０１１３】
いくつかの実施形態において、装置７００は、仮想マシンであってよい。これらの実施形態のいくつかにおいて、仮想マシンは、異なるマシンからのコンポーネントを含んでも、または地理的に分散されていてもよい。たとえば、データストレージ７１１およびプロセッサ７１０は、異なる２つの物理マシンにあってもよい。
【０１１４】
いくつかの実施形態において、装置７００は、方法４００、５００、または６００を実施するようにプログラムされた汎用コンピュータであってよい。
【０１１５】
プロセッサ実行可能なプログラム７２０がプロセッサ７１０上で実装されるとき、プログラムコードセグメントがプロセッサと結合して、特定の論理回路に類似して動作する独自のデバイスを提供する。
【０１１６】
本明細書では、たとえば、プログラムおよび論理がデータストレージ内に格納され、メモリがプロセッサに通信可能に接続された実施形態に関して表され、説明されたが、そのような情報は、任意の他の好適なやり方で（たとえば、任意の好適な数のメモリ、ストレージ、またはデータベースを使用して）、任意の好適な配置のデバイスに通信可能に接続された任意の好適な配置のメモリ、ストレージ、またはデータベースを使用して、メモリ、ストレージ、または内部データベースもしくは外部データベースの任意の好適な組合せで情報を記憶して、あるいは、任意の好適な数のアクセス可能な外部メモリ、ストレージ、またはデータベースを使用して、記憶されてもよいことを認識されたい。したがって、本明細書で言及された用語データストレージは、メモリ、ストレージ、およびデータベースのすべての好適な組合せを包含することを意味する。
【０１１７】
本説明および図面は、本発明の原理を例証するにすぎない。したがって、当業者は、たとえ本明細書に明示的に説明されない、または示されなくても、本発明の原理を具体化し、本発明の趣旨および範囲内に含まれる、さまざまな仕組みを考案できることが認識されるだろう。さらに、本明細書に列挙されるすべての例は、主に、読者が本発明の原理およびさらなる技術に対して本発明者によって貢献される概念を、理解するのを支援するための教育的な目的のためのみであることがはっきりと意図されており、それらの例は、そのような特に列挙された例および条件に限定されないものとして解釈されるべきである。さらに、本明細書において、本発明の原理、態様、および実施形態、ならびにその特定の例を列挙するすべての記述は、その均等物を包含することが意図される。
【０１１８】
「プロセッサ」とラベル付けされた任意の機能ブロックを含む、図に示されたさまざまな要素の機能は、専用ハードウェア、ならびに適切なソフトウェアに関連してソフトウェアを実行することができるハードウェアの使用によって提供されてよい。プロセッサにより提供されるとき、機能は、単一の専用プロセッサにより、単一の共有プロセッサにより、または、そのうちのいくつかが共有され得る複数の個々のプロセッサにより提供されてもよい。さらに、用語「プロセッサ」または「コントローラ」の明示的な使用は、ソフトウェアを実行することができるハードウェアを排他的に指すよう解釈されるべきでなく、限定はせずに、デジタル信号プロセッサ（ＤＳＰ）ハードウェア、ネットワークプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、ソフトウェアを記憶するための読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、および不揮発性ストレージを暗黙的に含むことができる。従来のまたはカスタムの、他のハードウェアもまた含まれてよい。同様に、図に示された任意のスイッチは、概念上にすぎない。スイッチの機能は、プログラム論理の演算によって、専用論理によって、プログラム制御と専用論理の相互作用によって、または手動でさえ実行されてよく、特定の技法は、コンテキストからより具体的に理解されるように、実装者によって選択可能である。
【０１１９】
本明細書における任意のブロック図は、本発明の原理を具体化する説明のための回路の概念図を表現することを認識されたい。同様に、任意の流れ図（ｆｌｏｗ  ｃｈａｒｔ）、フロー図（ｆｌｏｗ  ｄｉａｇｒａｍ）、状態遷移図、擬似コード、その他は、コンピュータまたはプロセッサが明示的に示されていてもいなくても、コンピュータ可読媒体において実質的に表現され得る、かつそのようなコンピュータまたはプロセッサによってそのように実行され得る、さまざまなプロセスを表現することを認識されたい。
【図１】
2015529026.tif 000004
【図２Ａ】
2015529026.tif 000005
【図２Ｂ】
2015529026.tif 000006
【図３Ａ】
2015529026.tif 000007
【図３Ｂ】
2015529026.tif 000008
【図３Ｃ】
2015529026.tif 000009
【図４】
2015529026.tif 000010
【図５】
2015529026.tif 000011
【図６】
2015529026.tif 000012
【図７】
2015529026.tif 000013
【国際調査報告】
2015529026.tif 000014
2015529026.tif 000015
2015529026.tif 000016