(57)【要約】      （修正有）【課題】データセンターネットワークにおいて、故障などのリスクを軽減するオーバーレイ（分割）フレームワークを提供する。【解決手段】リソース組織化アルゴリズムを使用する方法で、物理ネットワークを表現するオーバーレイネットワークを利用して、Ｋ接続耐障害性を保証するために必要な最小数の動作データセンター（ＤＣ）を特定する。オーバーレイネットワークは、物理ネットワークのトポロジカル特性の一部を含まない場合がある。リスクに基づくアルゴリズムは、Ｋ接続耐障害性に対してより少ない動作ＤＣを実現できる可能性がある。遅延に基づくアルゴリズムは、遅延に敏感なクラウドアプリケーションに対してより適切である。【選択図】図１
2014216012.tif 000002
【特許請求の範囲】
【請求項１】
Ｋ接続耐障害性のために最小のＭ個のデータセンター（ＤＣ）を識別するための方法であって、
オーバーレイネットワークに含まれる集合ＤＣに関連付けられたリスクマトリクスを作成するステップであって、前記リスクマトリクスは、Ｎ個のＤＣ接続対のうちのいずれが前記オーバーレイネットワークにおけるＬ個の割り当てリスクグループ（ＳＲＧ）のいずれに関連付けられるかを示し、ＤＣ接続対が前記集合ＤＣからＤＣへと前記オーバーレイネットワークにおける接続を表す、ステップと、
リスク基準に従って、前記複数のＤＣ接続対をソートするステップと、
ＭをＫ＋１（Ｍ＝Ｋ＋１）に等しく設定するステップと、
Ｍの各値にわたって、
ＤＣ接続対が選択されたか否かを決定するために、前記リスク基準の増加するソートされた順序で、前記複数のＤＣ接続対の各々に対して、リスクベクトルを評価するステップであって、前記リスクベクトルは、前記リスクマトリクスおよび予め選択された複数のＤＣ接続対に基づくステップと、
Ｍ個よりも少ない複数のＤＣ接続対が選択されるとき、Ｍをインクリメントするステップと、
を繰り返すステップと、
選択された前記Ｍ個のＤＣ接続対に含まれる前記Ｍ個のＤＣを識別するステップと、
を含み、
Ｋが前記集合ＤＣにアクセス可能なままである最小数のＤＣを表し、
前記オーバーレイネットワークは物理ネットワークを表す、
ことを特徴とする方法。
【請求項２】
前記リスク基準は、
前記複数のＤＣ接続対の各々に関連付けられたネットワーク遅延値を含む、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記リスク基準は、
前記複数のＤＣ接続対の各々に関連付けられたリスク周波数を含み、第一のＤＣ接続対の前記リスク周波数は、前記第一のＤＣ接続対に其々関連付けられた各ＳＲＧに累積的に関連付けられたＤＣ接続対の総数として定義される、
ことを特徴とする請求項１に記載の方法。
【請求項４】
前記リスクマトリクスは、任意のＤＣ接続対に関連付けられた各ＳＲＧに対して１の値を、それ以外には０の値を含み、
Ｍの各値に対して繰り返す前に、Ｌ個のゼロ値を有するように前記リスクベクトルを初期化するステップをさらに含み、
前記リスクベクトルを評価する前記ステップは、
次のＤＣ接続対用の各ＳＲＧにわたって、
前記リスクベクトルに、前記次のＤＣ接続対用の次のＳＲＧに関連付けられた前記リスクマトリクスにおける複数の値を、全ての予め選択されたＤＣ接続対に対して加算するステップと、
前記リスクベクトルにおける全ての値がＭマイナスＫ（Ｍ−Ｋ）以下であるとき、前記次のＤＣ接続対を選択するステップと、
を繰り返すステップを含む、
ことを特徴とする請求項１に記載の方法。
【請求項５】
ＭがＮよりも大きい（Ｍ＞Ｎ）とき、前記集合ＤＣに対してＫ接続耐障害性を満足する前に前記方法を終了するステップをさらに含む、
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記物理ネットワークに関連付けられたネットワークトポロジの少なくとも一部は、前記オーバーレイネットワークによって定義を消される、
ことを特徴とする請求項１に記載の方法。
【請求項７】
前記物理ネットワークの複数の属性を照会するために、前記オーバーレイネットワークに関連付けられたアプリケーションプログラミングインターフェイス（ＡＰＩ）を使用するステップをさらに含み、前記物理ネットワークの前記複数の属性は、
ＳＲＧの個数Ｌ、
前記複数のＤＣ接続対の各々に関連付けられたネットワーク遅延値、
前記複数のＤＣ接続対の各々に関連付けられたネットワーク帯域幅、
から選択される、
ことを特徴とする請求項６に記載の方法。
【請求項８】
Ｋ接続耐障害性のために最小のＭ個のデータセンター（ＤＣ）を識別するための製造物であって、
非一時的コンピュータ可読媒体と、
前記コンピュータ可読媒体に格納されたコンピュータで実行可能な複数の命令であって前記複数の命令は、実行されたとき、プロセッサに、
オーバーレイネットワークに含まれる集合ＤＣに関連付けられたリスクマトリクスを作成させ、前記リスクマトリクスは、Ｎ個のＤＣ接続対のうちのいずれが前記オーバーレイネットワークにおけるＬ個の割り当てリスクグループ（ＳＲＧ）のいずれに関連付けられるかを示し、ＤＣ接続対が前記集合ＤＣからＤＣへの前記オーバーレイネットワークにおける接続を表し、
リスク基準に従って、前記複数のＤＣ接続対をソートさせ、
ＭをＫ＋１（Ｍ＝Ｋ＋１）に等しく設定させ、
Ｍの各値にわたって、
ＤＣ接続対が選択されたか否かを決定するために、前記リスク基準の増加するソートされた順序で、前記複数のＤＣ接続対の各々に対して、リスクベクトルを評価することであって、前記リスクベクトルは、前記リスクマトリクスおよび予め選択された複数のＤＣ接続対に基づく、ことと、
Ｍ個よりも少ない複数のＤＣ接続対が選択されるとき、Ｍをインクリメントすることと、
を繰り返させ、
選択された前記Ｍ個のＤＣ接続対に含まれる前記Ｍ個のＤＣを識別させる、
ために前記プロセッサによって読み出し可能であり、
Ｋが前記集合ＤＣにアクセス可能なままである最小数のＤＣを表す、
ことを特徴とする製造物。
【請求項９】
前記リスク基準は、
前記複数のＤＣ接続対の各々に関連付けられたネットワーク遅延値を含む、
ことを特徴とする請求項８に記載の製造物。
【請求項１０】
前記リスク基準は、
前記複数のＤＣ接続対の各々に関連付けられたリスク周波数を含み、第一のＤＣ接続対の前記リスク周波数は、前記第一のＤＣ接続対に其々関連付けられた各ＳＲＧに累積的に関連付けられたＤＣ接続対の総数として定義される、
ことを特徴とする請求項８に記載の製造物。
【請求項１１】
前記リスクマトリクスは、任意のＤＣ接続対に関連付けられた各ＳＲＧに対して１の値を、それ以外には０の値を含み、
Ｍの各値にわたって繰り返すための複数の命令を実行する前に、Ｌ個のゼロ値を有するように前記リスクベクトルを初期化するための前記複数の命令をさらに含み、
前記リスクベクトルを評価するための前記複数の命令は、
次のＤＣ接続対用の各ＳＲＧにわたって、
前記リスクベクトルに、前記次のＤＣ接続対用の次のＳＲＧに関連付けられた前記リスクマトリクスにおける複数の値を、存在するときには、全ての予め選択された複数のＤＣ接続対に対して加算することと、
前記リスクベクトルにおける全ての値がＭマイナスＫ（Ｍ−Ｋ）以下であるとき、前記次のＤＣ接続対を選択することと、
を繰り返すための複数の命令を含む、
ことを特徴とする請求項８に記載の製造物。
【請求項１２】
ＭがＮよりも大きい（Ｍ＞Ｎ）とき、前記集合ＤＣに対してＫ接続耐障害性を満足する前に前記複数の命令を終了するための複数の命令をさらに含む、
ことを特徴とする請求項８に記載の製造物。
【請求項１３】
前記オーバーレイネットワークは物理ネットワークを表し、前記物理ネットワークに関連付けられたネットワークトポロジの少なくとも一部は、前記オーバーレイネットワークによって定義を消される、
ことを特徴とする請求項８に記載の製造物。
【請求項１４】
前記物理ネットワークの複数の属性を照会するために、前記オーバーレイネットワークに関連付けられたアプリケーションプログラミングインターフェイス（ＡＰＩ）を使用するための複数の命令をさらに含み、前記物理ネットワークの前記複数の属性は、
ＳＲＧの個数Ｌ、
前記複数のＤＣ接続対の各々に関連付けられたネットワーク遅延値、
前記複数のＤＣ接続対の各々に関連付けられたネットワーク帯域幅、
から選択される、
ことを特徴とする請求項１３に記載の製造物。
【請求項１５】
Ｋ接続耐障害性のために最小のＭ個のデータセンター（ＤＣ）を識別するための管理システムであって、
メモリと、
前記メモリに結合されたプロセッサと、
前記メモリに格納されたプロセッサで実行可能な複数の命令であって、前記複数の命令は、実行されたとき、プロセッサに、
オーバーレイネットワークに含まれる集合ＤＣに関連付けられたリスクマトリクスを作成させ、前記リスクマトリクスは、Ｎ個のＤＣ接続対のうちのいずれが前記オーバーレイネットワークにおけるＬ個の割り当てリスクグループ（ＳＲＧ）のいずれに関連付けられるかを示し、ＤＣ接続対が前記集合ＤＣからＤＣへの前記オーバーレイネットワークにおける接続を表し、
リスク基準に従って、前記複数のＤＣ接続対をソートさせ、
ＭをＫ＋１（Ｍ＝Ｋ＋１）に等しく設定させ、
Ｍの各値にわたって、
ＤＣ接続対が選択されたか否かを決定するために、前記リスク基準の増加するソートされた順序で、前記複数のＤＣ接続対の各々に対して、リスクベクトルを評価することであって、前記リスクベクトルは、前記リスクマトリクスおよび予め選択された複数のＤＣ接続対に基づく、ことと、
Ｍ個よりも少ない複数のＤＣ接続対が選択されるとき、Ｍをインクリメントすることと、
を繰り返させ、
選択された前記Ｍ個のＤＣ接続対に含まれる前記Ｍ個のＤＣを識別させる、
ために前記プロセッサによって読み出し可能であり、
Ｋが前記集合ＤＣにアクセス可能なままである最小数のＤＣを表す、
ことを特徴とする管理システム。
【請求項１６】
前記リスク基準は、
前記複数のＤＣ接続対の各々に関連付けられたネットワーク遅延値を含む、
ことを特徴とする請求項１５に記載の管理システム。
【請求項１７】
前記リスク基準は、
前記複数のＤＣ接続対の各々に関連付けられたリスク周波数を含み、第一のＤＣ接続対の前記リスク周波数は、前記第一のＤＣ接続対に其々関連付けられた各ＳＲＧに累積的に関連付けられたＤＣ接続対の総数として定義される、
ことを特徴とする請求項１５に記載の管理システム。
【請求項１８】
前記リスクマトリクスは、任意のＤＣ接続対に関連付けられた各ＳＲＧに対して１の値を、それ以外には０の値を含み、
Ｍの各値にわたって繰り返すための複数の命令を実行する前に、Ｌ個のゼロ値を有するように前記リスクベクトルを初期化するための前記複数の命令をさらに含み、
前記リスクベクトルを評価するための前記複数の命令は、
次のＤＣ接続対用の各ＳＲＧにわたって、
前記リスクベクトルに、前記次のＤＣ接続対用の次のＳＲＧに関連付けられた前記リスクマトリクスにおける複数の値を、存在するときには、全ての予め選択されたＤＣ接続対に対して加算することと、
前記リスクベクトルにおける全ての値がＭマイナスＫ（Ｍ−Ｋ）以下であるとき、前記次のＤＣ接続対を選択することと、
を繰り返すための複数の命令を含む、
ことを特徴とする請求項１５に記載の管理システム。
【請求項１９】
ＭがＮよりも大きい（Ｍ＞Ｎ）とき、前記集合ＤＣに対してＫ接続耐障害性を満足する前に前記複数の命令を終了するための複数の命令をさらに含む、
ことを特徴とする請求項１５に記載の管理システム。
【請求項２０】
前記オーバーレイネットワークは物理ネットワークを表し、前記物理ネットワークに関連付けられたネットワークトポロジの少なくとも一部は、前記オーバーレイネットワークによって定義を消される、
ことを特徴とする請求項１５に記載の管理システム。
【請求項２１】
前記物理ネットワークの複数の属性を照会するために、前記オーバーレイネットワークに関連付けられたアプリケーションプログラミングインターフェイス（ＡＰＩ）を使用するための複数の命令をさらに含み、前記物理ネットワークの前記複数の属性は、
ＳＲＧの個数Ｌ、
前記複数のＤＣ接続対の各々に関連付けられたネットワーク遅延値、
前記複数のＤＣ接続対の各々に関連付けられたネットワーク帯域幅、
から選択される、
ことを特徴とする請求項１５に記載の管理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願に対する相互参照］
本出願は、２０１３年４月２２日に出願された米国仮出願番号６１／８１４，５３２による優先権を享受する権利を主張し、米国仮出願番号６１／８１４，５３２は、本明細書に参照によって組み入れられる。
【０００２】
本開示は、概してデータセンターネットワークに関し、より詳細には、データセンターネットワークにおけるリスク軽減に関する。
【背景技術】
【０００３】
より多くのアプリケーションおよび負荷がオンラインネットワークコンピューティングリソースに移るにつれて、概して“クラウド”とも称されるが、地理的に分散されたデータセンター（ＤＣ）が光ネットワークを含むワイドエリアネットワークにわたって発達してきた。このようなデータセンターは、例えば、サーバオペレーティングシステムなどのコンピューティング環境を個々にインスタンス化しうる仮想マシン（ＶＭ）の種々のインスタンスを提供することがある。クラウドアプリケーションは、ユーザの経験を改善するために、分散型ＤＣに依存しうる。しかしながら、幾つかのクラウドサービスプロバイダは、光ネットワークインフラストラクチャを所有せず、分散型ＤＣを光学的に相互接続するためにネットワークプロバイダに頼っていることがある。幾つかのネットワークプロバイダは、クラウドサービスプロバイダに対して、その完全なネットワークトポロジ情報を明らかにすることを望まない、および／もしくは明らかにすることができない可能性がある。
【０００４】
分散型ＤＣにおける多くのクラウドアプリケーションは、集合通信パターンで集合化され、それによって、集合ＤＣは、分散型ＤＣにおいて処理されたデータを収集し、ユーザに最終結果を出力する。クラウドアプリケーションは、物理的に分散型ＶＭを集合ＤＣにおける分散形ＶＭからの結果を収集することによって、一つのＤＣとして論理的に動作させることができる。クラウドサーチおよびデータバックアップなどの他のアプリケーションは、例えば、分散型ＤＣに格納されたデータに近いＶＭを割り当て、ユーザによるアクセスのための集合ＤＣにおける結果を提供することができる。あるインスタンスにおいては、複雑な通信パターンが、一連のデータ集合をスケジューリングすることによって構成することができる。
【０００５】
分散型ＤＣおよび集合ＤＣに対する依存によって、とりわけ、ネットワーク提示、（複数の）ＤＣ故障および／もしくは設備故障などの種々のリスクに直面した時の耐障害性は、クラウドアプリケーションにとって重要な問題となる。したがって、クラウドサービスプロバイダがクラウドネットワーク接続を制御し、リソース組織化を最適化することを可能にするが、ネットワークオペレータが詳細なネットワークトポロジ情報を保持しながらネットワークサービスを提供することを可能にするオーバーレイ（分割）フレームワーク用の技術の必要性が存在する。
【発明の概要】
【０００６】
ある態様においては、Ｋ接続耐障害性のために最小のＭ個のデータセンター（ＤＣ）を識別するための開示された方法は、オーバーレイネットワークに含まれる集合ＤＣに関連付けられたリスクマトリクスを作成するステップと、リスク基準に従ってＤＣ接続対をソートするステップと、ＭをＫ＋１に等しく（Ｍ＝Ｋ＋１）なるように設定するステップとを含む。リスクマトリクスは、Ｎ個のＤＣ接続対のうちの何れがオーバーレイネットワークにおける割り当てリスクグループ（ＳＲＧ）のＬ個のうちの何れと関連付けられるかを示してもよい。ＤＣ接続対は、集合ＤＣからＤＣへのオーバーレイネットワークにおける接続を表してもよい。本方法は、Ｍの各値にわたる繰り返しにおいて、ＤＣ接続対が選択されたか否かを決定するためにリスク基準のソートされた増加する順序でＤＣ接続対の各々に対するリスクベクトルを評価するステップと、Ｍ個より少ないＤＣ接続対が選択されるときにはＭをインクリメントするステップとを含んでもよい。リスクベクトルは、リスクマトリクスおよび／もしくは予め選択されたＤＣ接続対に基づいてもよい。本方法は、選択されたＭ個のＤＣ接続対に含まれるＭ個のＤＣを識別するステップをさらに含んでもよい。Ｋは、集合ＤＣにアクセス可能なままである最小数のＤＣを表してもよい。オーバーレイネットワークは、物理ネットワークを表してもよい。
【０００７】
Ｋ接続耐障害性のために最小のＭ個のデータセンター（ＤＣ）を識別するためのさらに開示された態様は、非一時的、コンピュータ可読媒体と、コンピュータ可読媒体に格納されたコンピュータで実行可能な命令と、を含む製造物を含む。さらなる態様は、メモリと、メモリに結合されたプロセッサと、メモリに格納されたコンピュータで実行可能な命令とを含む管理システムを含む。
【０００８】
実施形態の目的および利点は、少なくとも請求項で特に指摘された構成要素、特徴および組み合わせによって実現され達成されるであろう。前述された概略的記述および以下の詳細な説明の双方は、例示的かつ説明的なものであって、請求項におけるように、本発明を限定するものではないことを理解されたい。
【図面の簡単な説明】
【０００９】
本発明およびその特徴と利点をより完全に理解するために、添付の図面と併せて以下の説明に対して参照がなされる。
【図１】オーバーレイフレームワークの一実施形態の選択された構成要素のブロック図である。
【図２Ａ】集合要求の一実施形態の選択された構成要素のブロック図である。
【図２Ｂ】集合データセンターの個別の保護の一実施形態の選択された構成要素のブロック図である。
【図２Ｃ】集合データセンターの連結保護の一実施形態の選択された構成要素のブロック図である。
【図３】Ｋ接続耐障害性を実現するための方法の一実施形態の選択された構成要素を示すフローチャートである。
【図４】Ｋ接続耐障害性を実現するための方法の一実施形態の選択された構成要素を示すフローチャートである。
【図５】管理システムの一実施形態の選択された構成要素のブロック図である。
【図６Ａ】Ｋ接続耐障害性を実現するための選択された方法の一実施形態のシミュレーション結果である。
【図６Ｂ】Ｋ接続耐障害性を実現するための選択された方法の一実施形態のシミュレーション結果である。
【図６Ｃ】Ｋ接続耐障害性を実現するための選択された方法の一実施形態のシミュレーション結果である。
【図６Ｄ】Ｋ接続耐障害性を実現するための選択された方法の一実施形態のシミュレーション結果である。
【発明を実施するための形態】
【００１０】
以下の記述においては、開示された本発明の主題の議論を容易にするために、例示の目的のために詳細が説明される。しかしながら、開示された実施形態は例示的なものであって、全ての可能性のある実施形態を網羅するものではないことが当業者には明らかなことに留意されたい。
【００１１】
本開示を通して、参照番号のハイフンの付加された形式は、ある構成要素の具体例を称し、参照番号のハイフンの付加されていない形式は、集合的要素もしくは総称的要素を称する。したがって、（図面に示されていない）一実施例として、ウィジェット“１２−１”はウィジェットクラスの一例を称し、ウィジェット“１２”として集合的に称されてもよいし、そのうちの任意の一つは、ウィジェット“１２”として総称的に称されてもよい。図面および説明においては、類似の参照番号は類似の構成要素を表すことを意図される。
【００１２】
本明細書でさらに詳細に記述されるように、Ｋ接続耐障害性概念は、クラウドアプリケーションに対する広範囲のリスク下でのリソース使用可能性を保証しうるように開示される。二つのリソース組織化スキームは、光ネットワーク仮想化用のオーバーレイフレームワークにおいてＫ接続耐障害性概念を実現しうるように開示される。リソース組織化スキームは、Ｋ接続耐障害性を保証するための最小数のデータセンターを識別し、Ｋは集合ＤＣからアクセス可能なままである最小数のＤＣを表す。表１における以下のパラメータは、ゼロよりも大きな整数であるが、Ｋ接続耐障害性に関連して本明細書で使用される。
【表１】
2014216012.tif 000003
【００１３】
Ｋ接続耐障害性（ＫＣＳ）は、ネットワークの停止、（複数の）ＤＣ故障および／もしくは他のタイプの設備故障などを含むがそのいずれにも限定されない任意のリスク（本明細書では、集合的に“リスクイベント”とも称される）に対して、（Ｍ個の元の動作ＤＣのうちの）少なくともＫ個のＤＣが集合ＤＣから到達可能であるシナリオによって定義されてもよい。本開示の目的のために、ＤＣａは故障していないと仮定する。リスクイベントは、（停電、自然災害および／もしくはシステムメンテナンスによって）ＤＣサイトもしくは（ファイバ切断によって）ネットワークにおいて生じうる複数の故障を結果としてもたらすことがある。固定数のＶＭを要求するクラウドアプリケーションに対して、さらなるＶＭは、通常動作と同一数の仮想マシンをリスクイベントシナリオ中に維持するために、残存するＫ個のＤＣで割り当てることができる。
【００１４】
本明細書で記述されるように、オーバーレイフレームワークは、仮想化された光ネットワークによって分散型データセンターを相互接続するように提示される。割り当てリスクグループ（ＳＲＧ）および遅延などの仮想化された光ネットワークによって提供されたネットワーク情報に基づいた、耐障害性のあるリソース組織化アルゴリズムが開示される。開示されたリソース組織化アルゴリズムは、Ｋ接続耐障害性を保証するために、最小数の動作ＤＣを見出すことがある。物理ネットワークトポロジが利用可能でなく、接続用のルーティングが可能ではない場合、本明細書で開示されたリソース組織化アルゴリズムは、オーバーレイネットワークに対して提供されたＳＲＧ情報に基づいて、最小数の動作ＤＣを供給してもよい。
【００１５】
ここで図面に関連して、図１は、光ネットワーク仮想化に基づくオーバーレイフレームワーク１００の例示的な一実施形態を示す。図１においては、オーバーレイフレームワーク１００は、オーバーレイネットワーク１０６、ソフトウェア確定ネットワーク（ＳＤＮ）アプリケーションプログラミングインターフェイス（ＡＰＩ）１０８および物理ネットワーク１１０を含むように示される。示されるように、オーバーレイネットワーク１０６は、ＤＣ１０２間の接続１０４を含み、接続１０４の帯域幅は、光ネットワーク仮想化を利用して調整可能であってもよい。図１においては、物理ネットワーク１１０によって表される下層の光ネットワークは、接続の帯域幅を調整するように構成された光伝送ネットワーク（ＯＴＮ）および／もしくはフレキシブル光データ平面（例えば、フレキシブル送信機）であってもよい。
【００１６】
図１においては、オーバーレイネットワーク１０６は、仮想化されたＤＣ１０２および接続１０４を含むように示される。ある実施形態においては、ＤＣ１０２は、物理ＤＣ１１２に対応し、例えば、ＤＣ＿１  １０２−１は、ＤＣ＿Ａ  １１２−１を表し、ＤＣ＿２  １０２−２はＤＣ＿Ｆ１１２−６を表し、ＤＣ＿３  １０２−３はＤＣ＿Ｅ  １１２−５を表し、ＤＣ＿４  １０２−４はＤＣ＿Ｃ１１２−３を表すが、ＤＣ＿Ｂ  １１２−２およびＤＣ＿Ｄ  １１２−４は、オーバーレイネットワーク１０６に明確に含まれなくてもよい。他の実施形態においては、ＤＣ１０２は、一つ以上の物理ＤＣ１１２からのコンピューティングリソースを含み、仮想化されたＤＣを表してもよい。例えば、ＤＣ＿１  １０２−１は、ＤＣ＿Ａ  １１２−１およびＤＣ＿Ｂ１１２−２などのうちの少なくとも一部を表してもよい。オーバーレイネットワーク１０６における物理ネットワーク１１０におけるＤＣ１１２のＤＣ１０２に対するマッピングの他の配置および構成が異なる実施形態においては実現されてもよいことを理解されたい。さらには、接続１０４は、データを伝送するための任意の容量を有する仮想化された接続を表してもよい。示されるように、接続１０４−１および１０４−２は、低容量接続を表し、接続１０４−３および１０４−４は中容量接続を表し、接続１０４−５および１０４−６は、高容量接続を表してもよい。接続１０４は、二つのＤＣ１０２を接続するオーバーレイネットワークにおいて示されるが、接続１０４は、種々のネットワークトポロジを利用して物理的に実現され、異なるノードおよび／もしくはネットワークセグメントを含む物理接続を実際には表してもよい。しかしながら、動作可能なネットワークプラットフォームとしてオーバーレイネットワーク１０６を利用するクラウドサービスプロバイダに対して、実際の物理トポロジは、隠されたままである、ならびに／または時間の経過につれて変化してもよい。
【００１７】
クラウドサービスプロバイダは、オーバーレイネットワーク１０６によって相互接続されたＤＣにおけるＶＭを管理する（図面には示されていない）集中型コントローラを有してもよい。集中型コントローラ（本明細書では単に“コントローラ”とも称される）は、遅延および接続のＳＲＧなどのネットワーク情報を獲得し、ソフトウェア確定ネットワーク（ＳＤＮ）などのネットワーク制御および管理ツールの助けによって、ネットワークアプリケーションプログラミングインターフェイス（ＡＰＩ）を通して接続の帯域幅を要求してもよい。オーバーレイフレームワーク１００に示されるように、ＳＤＮ  ＡＰＩ１０８は、オーバーレイネットワーク１０６のユーザ（例えば、クラウドプロバイダ）がネットワーク情報を照会することを可能にするためのソフトウェアツールを表してもよい。オーバーレイフレームワーク１００は、物理ネットワーク１１０のネットワークプロバイダが詳細な物理ネットワークトポロジ情報を隠したままにすることを可能にし、クラウドサービスプロバイダがクラウドサービスを容易に設定し、リソース組織化を実施し、接続の帯域幅を柔軟に増減することを可能にすることに留意されたい。クラウドプロバイダは、物理ネットワーク１１０の特定のネットワークトポロジの知識を有することなく、および／もしくは、オーバーレイネットワーク１０６に含まれていない接続経路１０４に沿った中間ネットワークデバイスなどの、物理ネットワーク１１０において隠されたコンポーネントとの直接の相互作用なく、オーバーレイネットワーク１０６におけるＤＣ１０２および／もしくは接続１０４に対するある特定の属性を照会するためにＳＤＮ  ＡＰＩ１０８を利用してもよい。
【００１８】
ここで図２Ａ、図２Ｂおよび図２Ｃに関連して、集合要求２００の例示的な実施形態および対応する保護スキームが図として示される。コントローラは、クラウド要求を受信して、リソース組織化を実施してもよい。例示的な一実施形態においては、図２Ａに示されるように、集合要求２００−１はＤＣｉ２０２−２、ＤＣｊ２０２−３、ＤＣｋ２０２−４からのデータを集合させることによって、例えば、コントローラを介して、集合ＤＣａ２０２−１が基本要求を如何に処理するかを示してもよい。より複雑な要求は基本要求の組み合わせおよび／もしくは基本要求のセットを利用して作成されてもよい。要求は、Ｋ接続耐障害性を満足し、リスクイベントに対して任意の数のＶＭ（Ｖ）に関連付けられてもよい。リスクイベントが起きたとき、Ｋ接続耐障害性の要求は、Ｖ個のＶＭを維持するために、Ｍ個の動作ＤＣのうちの残存するＫ個のＤＣにさらなるＶＭを割り当ててもよい。各ＤＣが要求に対して同一数のＶＭを割り当てられると仮定すると、Ｋ接続耐障害性の要求に対する合計ＶＭは、Ｖ＊Ｍ／Ｋで与えられる可能性がある。したがって、Ｋ接続耐障害性を満足する最小のＭ個のＤＣを見つけることは、結果として、要求に対して必要とされる最少のＶＭをもたらす。
【００１９】
Ｋ接続耐障害性を保証することは、物理ネットワークおよびＤＣからの情報をともに考慮することによってネットワークコストを低下させる可能性がある。図２Ｂにおいては、個別（ブラインド）保護（２００−２）は、ｓｉがリスクｉを示し、ネットワーク接続が集合ＤＣａ２０２−１から経路分離接続（点線）を提供することによってブラインド保護されうる一実施例を示す。図２Ｂにおいては、Ｋ＝２に対するＫ接続耐障害性（即ち、２−接続耐障害性）は、ネットワーク接続から分離して、ＤＣにおけるリスクイベントに対する保護によって保証され、結果として、分離保護２００−２における６個の接続をもたらすことがある。図２Ｃにおいては、連結保護２００−３は、下層光ネットワークからの割り当てリスクグループ（ＳＲＧ）情報を利用することによって、２−接続耐障害性が如何にして、ネットワーク接続およびともに保護することができるＤＣを見つけることによって保証されうるかを示す。例えば、リスクＳ１およびＳ６は、第一のＳＲＧで連結され、リスクＳ２およびＳ５は第二のＳＲＧで連結され、リスクＳ３およびＳ４は第三のＳＲＧで連結されてもよい。連結保護２００−３においては、ネットワークリソースにおける顕著な節約が３接続を有することによって達成され、図２Ｂと比較して３保護接続の節約を表す。
【００２０】
ＳＤＮ  ＡＰＩ１０８（図１参照）を利用して、最小の遅延を有するＤＣのサブセットは、Ｋ接続耐障害性を満足する複数のＤＣのサブセットが存在するときに識別可能であってもよい。要求の遅延は、ＤＣのサブセットと集合ＤＣ（ＤＣａ）との間の接続の遅延の合計によって与えられることがある。ＤＣａは、特定のアプリケーションに依存して、比較的ユーザの近傍にあるか、または比較的特定のＤＣのサブセットに近傍にあるＤＣに対して割り当てられてもよい。
【００２１】
図２Ａ、図２Ｂおよび図２Ｃに基づいて、以下の問題記述が、集合および保護スキーム２００に基づいてＫ接続耐障害性用の方法に適用されてもよい。
仮定：オーバーレイネットワークはＮ個のＤＣサイトおよびリスクＳ＝｛ｓ１，ｓ２，・・・，Ｓｌ，．．．，ｓＬ｝に対するＬ組の割り当てリスクグループ（ＳＲＧ）を有する。オーバーレイネットワークにおいては、ＤＣｉとＤＣｊとの間の各接続Ｅｉｊは、遅延ｄｉｊを含むネットワーク情報を有し、関連付けられたＳＲＧのベクトルＡｉｊ＝｛αｉｊ，αｉｊ２，．．．，αｉｊｌ，．．．，αｉｊＬ｝（ここでαｉｊｌ＝１）は、ｓｌがＥｉｊに関連付けられ、そうでない場合にはαｉｊｌ＝０であることを示す。同様に、各ＤＣｉは、ＳＲＧの組Ａｉに関連付けられる。また、リスクイベント中であっても、集合ＤＣａに接続されるＫ個のＤＣを必要とする要求が受信される。
解法
少なくともＭ個の動作ＤＣは以下のとおりである。
ｍｉｎΣ（ｄａｊ）、ここで１≦ｊ≦Ｍであり、要求に関連付けられた合計遅延を最小化し、
Ｋ個のＤＣがリスクイベント中にＤＣａに接続されたままであり、Ｋ接続耐障害性を（ＫＣＳ）を保証する。
【００２２】
以下にさらに詳細に記述されるように、二つの発見的アルゴリズムが光学的に相互接続された分散型ＤＣネットワークにおけるＫＣＳ問題を解決するために開示される。双方のアルゴリズムにおいては、リスクマトリクスは各集合ＤＣａに対して構成されてもよい。各ｓｌに対して、もし、接続ＥｉｊおよびＤＣｊで構成される対（ｐｉｊ）がリスクｓｌに関連付けられる場合、リスクマトリクスは１を記録する。以下に記述される双方のアルゴリズムにおいては、表２は、仮定される（図示されていない）オーバーレイネットワークに関連付けられたパラメータに対する値を示す。
【表２】
2014216012.tif 000004
【００２３】
表３は、表２の実施例に対応する任意のＤＣ１に対して構成される例示的なリスクマトリクスを示す。ｐｉｊの遅延はｄｉｊであり、ｐｉｊに関連付けられたリスクの組は、ＡｉｊおよびＡｉの和集合である。表３における値は、対応する（図示されていない）オーバーレイネットワークに基づいて、例えば、ＳＤＮ  ＡＰＩ１０８（図１参照）を利用して照会されてもよい。
【表３】
2014216012.tif 000005
リスクベクトル（＃ｐｌ）は、ｓ１に関連付けられ、ゼロに初期化されることがある現在選択された対の数を記録するためにさらに使用されてもよい。
【００２４】
アルゴリズムＡ１−遅延に基づく：少なくともＭ個の動作ＤＣを見つけるために、ＭはＫ＋１からインクリメントされる。各Ｍに対して、集合ＤＣとしてＤＣａとともに、遅延が増大する順序でｐａｊをソートする。ｐａｊが選択され、αａｊｌ＝１である場合、リスクベクトル＃ｐｌは１ずつインクリメントされる。αａｊｌ＝１の全てのリスクｓ１に対して、リスクベクトル＃ｐｌ≦（Ｍ−Ｋ）である場合にのみ、ｐａｊを選択することができる。Ｍ組が見つけられた場合、Ｍのインクリメントを停止する。最後に、最も高いＭがＫ接続耐障害性を満足する動作ＤＣの最小数を表す。
【００２５】
上記の表２および表３における値に対応するアルゴリズムＡ１の例示的な一実施形態がここで詳細に記述される。遅延に基づくアルゴリズムＡ１に対して、対ｐｉｊに対して、遅延ｄｉｊは、｛ｐ１２、ｐ１４，ｐ１３，ｐ１５｝によって与えられた遅延順序で増加し、対ｐｉｊが処理用に選択された順序を表すと仮定される。アルゴリズムＡ１はプロセッサによって実行可能な命令にほぼ対応する擬似コードを利用して以下に記述されるが、人が読解できるように散文体のテキストを組み込む。
【表４】
2014216012.tif 000006
【００２６】
アルゴリズムＡ１は、最初に対が選択されないでＭ回繰り返すメインループを有する、ラインＡ１−１００で開始する。ラインＡ１−１１０において、ＭはＫ＝２に対して３に設定され、したがって（Ｍ−Ｋ）＝１である。ラインＡ１−１２０において、対の評価は遅延順序に基づいて、ｐ１２で開始する。ラインＡ１−１３０において、リスクベクトル＃ｐｌ［１］は、ｐ１２のみに対して表３で与えられたリスクマトリクスを利用して評価される。なぜなら、まだ対が選択されておらず、結果として、リスクベクトル＃ｐｌ［１］における全ての値が（Ｍ−Ｋ）以下であるためである。ラインＡ１−１４０において、ｐ１２は第一の対として選択される。ラインＡ１−１５０において、対の評価は、遅延順序に基づいてｐ１４で継続する。ラインＡ１−１６０において、リスクベクトル＃ｐｌ［２］は、ｐ１２およびｐ１４に対して、表３に与えられたリスクマトリクスを利用して評価される。なぜなら、ｐ１２のみが選択され、結果として、リスクベクトル＃ｐｌ［２］における全ての値が（Ｍ−Ｋ）以下であるためである。ラインＡ１−１７０においては、ｐ１４は第二の対として選択される。ラインＡ１−１８０において、対の評価は遅延順序に基づいてｐ１３で継続する。ラインＡ１−１９０において、リスクベクトル＃ｐｌ［３］は、ｐ１２、ｐ１４およびｐ１３に対して、表３に与えられたリスクマトリクスを利用して評価される。なぜなら、ｐ１２およびｐ１４の双方が選択され、結果として、リスクベクトル＃ｐｌ［３］における全ての値が（Ｍ−Ｋ）以下ではないためである。ラインＡ１−２００において、ｐ１３はスキップされる。ラインＡ１−２１０において、対の評価は遅延順序に基づいてｐ１５で継続する。ラインＡ１−２２０においては、リスクベクトル＃ｐｌ［４］は、ｐ１２、ｐ１４およびｐ１５に対して、表３に与えられたリスクマトリクスを利用して評価される。なぜなら、ｐ１２およびｐ１４の双方が選択され、結果として、リスクベクトル＃ｐｌ［４］における全ての値が（Ｍ−Ｋ）以下であるためである。ラインＡ１−２３０において、ｐ１５は、第三の対として選択される。ラインＡ１−２４０において、Ｍ個の対が選択されたことが決定され、従ってＭはインクリメントされず、メインループは終了し、アルゴリズムＡ１は、Ｋ接続耐障害性に対して｛ｐ１２，ｐ１４，ｐ１５｝を選択して終了する。
【００２７】
アルゴリズムＡ２−リスクに基づく：遅延に基づくアルゴリズムＡ１においては、初期に選択された対が多くのリスクに関連付けられる可能性があり、結果として、Ｋ接続制約条件を満足するためにより多くの動作ＤＣをもたらす。したがって、リスクに基づくアルゴリズムＡ２は、ｐａｊに関連付けられたリスクの総頻度の増加する順序でｐａｊをソートする。リスクの周波数は、リスクに関連付けられたｐａｊ対の数として定義される。リスクに基づくアルゴリズムＡ２における他のステップは、遅延に基づくアルゴリズムＡ１の一部に類似してもよい。
【００２８】
表３に作成されたリスクマトリクスに基づいて、以下のリスクの周波数は各対ｐｉｊに対して確立される可能性がある：
ｐ１２は、ｓ１（１リスク）とｓ２（２リスク）に関連付けられるため、ｐ１２リスク周波数は、２＋１＝３であり、
ｐ１３は、ｓ２、ｓ３、ｓ４に関連付けられるため、ｐ１３リスク周波数は、２＋１＋２＝５であり、
ｐ１４は、Ｓ２に関連付けられるため、リスク周波数ｐ１４＝２であり、
ｐ１５はｓ５に関連付けられるため、リスク周波数ｐ１５＝１である。
したがって、アルゴリズムＡ２のリスク順序は、｛ｐ１５，ｐ１４，ｐ１２，ｐ１３｝によって与えられ、これは対ｐｉｊが処理用に選択される順序を表す。
【表５】
2014216012.tif 000007
【００２９】
アルゴリズムＡ２は、最初に対が選択されないでＭ回繰り返すメインループを有する、ラインＡ２−１００で開始する。ラインＡ２−１００において、ＭはＫ＝２に対して３に設定され、したがって（Ｍ−Ｋ）＝１である。ラインＡ２−１２０において、対の評価はリスク順序に基づいて、ｐ１５で開始する。ラインＡ２−１３０において、リスクベクトル＃ｐｌ［１］は、ｐ１５のみに対して表３で与えられたリスクマトリクスを利用して評価される。なぜなら、まだ対が選択されておらず、結果として、リスクベクトル＃ｐｌ［１］における全ての値が（Ｍ−Ｋ）以下であるためである。ラインＡ２−１４０において、ｐ１５は第一の対として選択される。ラインＡ２−１５０において、対の評価は、リスク順序に基づいてｐ１４で継続する。ラインＡ２−１６０において、リスクベクトル＃ｐｌ［２］は、ｐ１５およびｐ１４に対して、表３に与えられたリスクマトリクスを利用して評価される。なぜなら、ｐ１５のみが選択され、結果として、リスクベクトル＃ｐｌ［２］における全ての値が（Ｍ−Ｋ）以下であるためである。ラインＡ２−１７０においては、ｐ１４は第二の対として選択される。ラインＡ２−１８０において、対の評価はリスク順序に基づいてｐ１２で継続する。ラインＡ２−１９０において、リスクベクトル＃ｐｌ［３］は、ｐ１５、ｐ１４およびｐ１２に対して、表３に与えられたリスクマトリクスを利用して評価される。なぜなら、ｐ１５およびｐ１４の双方が選択され、結果として、リスクベクトル＃ｐｌ［３］における全ての値が（Ｍ−Ｋ）以下であるためである。ラインＡ２−２００において、ｐ１２は第三の対として選択される。ラインＡ２−２１０において、Ｍ個の対が選択されたことが決定され、従ってＭはインクリメントされず、メインループは終了し、アルゴリズムＡ２は、Ｋ接続耐障害性に対して｛ｐ１５，ｐ１４，ｐ１２｝を選択して終了する。
【００３０】
アルゴリズムＡ１およびアルゴリズムＡ２の双方は、上述された構成の実施例において同一の結果に到達するが、アルゴリズムＡ１およびアルゴリズムＡ２は、対ｐｉｊが評価される順序が異なり、したがって、任意の構成に対して評価の反復回数が異なってもよい。Ｍをインクリメントするためのメインループのさらなる繰り返しは、記述を明瞭にするために記述されていないが、より大きなネットワーク構成において、その後の繰り返しが、より大きなＭの値に対するＫ接続耐障害性を見つけるために実施されてもよいことを理解されたい。
【００３１】
図３に関連して、本明細書で記述されるようなＫ接続耐障害性を実現するための方法３００の一実施形態の選択された構成要素がフローチャート形式で示される。ある実施形態においては、方法３００は、ＫＣＳ識別５３０（図５参照）を利用して実現されてもよい。方法３００に示されたある動作は、所望の場合には並べ替えられたり、省略されたりしてもよいことに留意されたい。
【００３２】
方法３００は、オーバーレイネットワークに含まれる集合ＤＣに関連付けられたリスクマトリクスを作成するステップ（動作３０２）によって開始し、リスクマトリクスは、Ｎ個のＤＣ接続対のうちのいずれがＬ個のＳＲＧのうちの何れに関連付けられているかを示す。ＤＣ接続対は、リスク基準に従ってソートされてもよい（動作３０４）。リスク基準は、リスクに基づいてもよいし、遅延に基づいてもよい。その後、方法３００は、Ｍ＝Ｋ＋１とし（動作３０６）、リスクベクトルをＬ個のゼロ値を有するように初期化してもよい。その後、Ｍ＞Ｎか否かの決定がなされてもよい（動作３０８）。動作３０８の結果が「はい」であるとき、方法３００は終了してもよい（動作３９０）。動作３０８の結果が「いいえ」であるとき、ＤＣ接続対が選択されたか否かを決定するため各ＤＣ接続対に対してリスク基準の増加する順序で、リスクベクトルは評価されてもよい（動作３１０）。リスクベクトルは、リスクマトリクスおよび予め選択されたＤＣ接続対に基づく。その後、Ｍ個より少ないＤＣ接続対が選択されたか否かの決定がなされてもよい（動作３１２）。動作３１２の結果が「はい」であるとき、Ｍはインクリメントされ（動作３１４）、方法３００は動作３０８へと戻ってもよい。動作３１２の結果が「いいえ」であるとき、選択されたＭ個のＤＣ接続対に含まれるＭ個のＤＣが識別されてもよい（動作３１６）。その後、方法３００は終了してもよい（動作３９０）。
【００３３】
ここで図４に関連して、本明細書で記述されるような、Ｋ接続耐障害性を実現するための方法３１０の一実施形態の選択された構成要素がフローチャート形式で示される。種々の実施形態においては、方法３１０は、ＫＣＳ識別５３０（図５参照）を利用して実現され、方法３００（図３参照）における動作３１０を表してもよい。方法３１０に示されたある動作は、所望の場合、並べ替えられたり、省略されたりしてもよいことに留意されたい。方法３１０は、反復ループコンテキストで示されて、以下の説明に記述されているが、“次の”という語は、ループコンテキスト内で使用される反復値を示すために使用される。
【００３４】
方法３１０は、次のＤＣ接続対を評価するために進行する（動作４０２）ステップによって開始してもよい。方法３１０は、次のＳＲＧを評価するために、その後進行してもよい（動作４０４）。次のＤＣ接続対用、ならびに存在するときには、全ての予め選択されたＤＣ接続対用の次のＳＲＧに関連付けられたリスクマトリクスにおける値は、リスクベクトルに加算されてもよい（動作４０６）。その後、全てのＬ個のＳＲＧが次のＤＣ接続対に対して評価されたか否かの決定がなされてもよい（動作４０８）。動作４０８の結果が「いいえ」であるとき、方法３１０は、動作４０４へと戻ってもよい。動作４０８の結果が「はい」であるとき、リスクベクトルにおける全ての値が（Ｍ−Ｋ）以下であるか否かの決定がなされてもよい（動作４１０）。動作４１０の結果が「はい」であるとき、次のＤＣ接続対が選択されてもよい（動作４１２）。動作４１０の結果が「いいえ」であるか、動作４１２の後で、全てのＮ個のＤＣ接続対が評価されたか否かの決定がなされてもよい（動作４１４）。動作４１２の結果が「いいえ」であるとき、方法３１０は動作４０２へと戻ってもよい。動作４１２の結果が「はい」であるとき、方法３１０は動作３１２へと継続してもよい（図３参照）。
【００３５】
ここで、図５に関連して、管理システム５００の一実施形態の選択された構成要素のブロック図が示される。図５においては、管理システム５００は、本明細書で記述されたようなＫ接続耐障害性を実現するための物理および論理コンポーネントを含むコンピュータシステムとして表され、したがって、プロセッサ５０１、メモリ５１０、ネットワークインターフェイス５２０を含んでもよい。プロセッサ５０１は、一つ以上の個々のプロセシングユニットを表し、メモリ５１０および／もしくは管理システム５００によって格納されたプログラム命令を実行し、データを解釈し、ならびに／またはデータを処理してもよい。
【００３６】
図５においては、メモリ５１０は、プロセッサ５０１に通信可能なように結合され、ある期間にプログラム命令および／もしくはデータを保持するために適切なシステム、デバイスもしくは装置（例えば、コンピュータ可読媒体）を含んでもよい。メモリ５１０は、ランダムアクセスメモリ（ＲＡＭ）、電気的消去可能プログラマブルリードオンリーメモリ（ＥＥＰＲＯＭ）、ＰＣＭＣＩＡカード、フラッシュメモリ、ソリッドステートディスク、ハードディスクドライブ、磁気テープライブラリ、光ディスクドライブ、光磁気ディスクドライブ、コンパクトディスクドライブ、コンパクトディスクアレイ、ディスクアレイコントローラおよび／もしくは揮発性もしくは不揮発性メモリの任意の適切な選択もしくはアレイなどの種々のタイプのコンポーネントおよびデバイスを含んでもよい。不揮発性メモリは、電源を切った後データを保持するメモリのことを称する。メモリ５１０は、種々の実施形態においては、異なる数の物理記憶デバイスを含んでもよいことに留意されたい。
【００３７】
図５に示されるように、メモリ５１０は、Ｋ接続耐障害性（ＫＣＳ）識別５３０を含み、プロセッサ５０１などのプロセッサで実行されたときに、リスクに基づくアルゴリズムＡ１および／もしくは遅延に基づくアルゴリズムＡ２を含むがそのいずれにも限定はされないＫ接続耐障害性を満足するために、ＤＣおよび／もしくはＳＲＧを識別するための種々のアルゴリズムを実行しうる、其々のコンピュータ可読命令のセットを表してもよい。情報記憶装置５４０は、ＫＣＳ識別５３０に関連付けられたデータおよびパラメータなどの種々のデータおよびパラメータを格納してもよい。
【００３８】
ここで図６Ａ−図６Ｄに関連して、Ｋ接続耐障害性を実現するために選択された方法の実施形態のシミュレーション結果がデータプロットとして示される。図６Ａ−図６Ｄにおいては、発見的アルゴリズムＡ１およびＡ２の選択された実施形態のシミュレーション結果が、比較のために示される。図６Ａ−図６Ｄに示されたシミュレーション結果においては、７５個のＤＣおよび９９個の接続を有し、完全にメッシュ接続されたオーバーレイネットワークであって、オーバーレイネットワーク１００（図１参照）に類似する物理ネットワークがランダムに選択されたノードに配置されたＤＣで作成されると仮定する。オーバーレイネットワークにおける接続用の最短経路は０．１と１０の任意の時間単位の間にランダムに割り当てられた、接続遅延で使用され、総数６０のＳＲＧリスクが使用される。各接続および各ＤＣにおけるリスクの組は、ランダムに接続され、接続毎もしくはＤＣ毎のＳＲＧ数は、Ｒで表されると、図６Ａ−図６Ｄに与えられる。クラウド要求に対して、集合ＤＣはランダムに割り当てられてもよい。シミュレーション結果は、割り当てに成功した総数１０５個の要求で平均化され、帯域幅の任意量は、下層の物理ネットワークインフラストラクチャからの任意の制限なしで要求されうるＶＭに対して仮定され、最小数の動作ＤＣおよび遅延が具体的に評価されてもよい。
【００３９】
図６Ａにおいては、Ｋ値の増加に対する性能は、アルゴリズムＡ１（遅延に基づく）およびアルゴリズムＡ２（リスクに基づく）に対して、Ｍ対Ｋの最小値の平均に対するプロットとして示される。図６Ｂにおいては、Ｋ値の増加に対する性能は、アルゴリズムＡ１（遅延に基づく）およびアルゴリズムＡ２（リスクに基づく）に対して、要求毎の平均遅延対Ｋに対するプロットとして示される。図６Ａおよび図６Ｂは、Ｋが増加するにつれての最小のＭと要求の平均遅延とを示し、オーバーレイネットワークにおけるＤＣの総数は、１０である（Ｎ＝１０）。図６Ａは、リスクに基づくアルゴリズムＡ１は遅延に基づくアルゴリズムＡ２よりも１２％少ない動作ＤＣを結果としてもたらすことがあることを示す。増加するＫ接続の制約条件を満足するために、最小数の動作ＤＣが増加することに留意されたい。ＫがＲ＝１（もしくはＲ＝２）に対して６（もしくは４）に等しいとき、必要とされる最少の動作ＤＣは、総ＤＣ１０のうちのほぼ９に到達する。したがって、より高いＫに対して解法は見つけられない。図６Ｂは、Ｋが増加するにつれて、要求毎の平均遅延が、より多い動作ＤＣの必要性によって増加し、遅延における差が減少することを示す。より低い総リスク周波数で選択された接続がより長い遅延を有しうるため、リスクに基づくアルゴリズムＡ１が結果としてより少ない動作ＤＣをもたらすときでさえも、Ｋが（Ｎ／（２Ｒ））より低いとき、接続の高いリスク多様性を示すが、リスクに基づくアルゴリズムＡ１の遅延は、遅延に基づくアルゴリズムＡ２の遅延よりも高いことがある。Ｋが（Ｎ／（２Ｒ））よりも高いとき、接続のリスク多様性は限定される可能性があり、したがって、動作ＤＣの組の選択を制限する。したがって、リスクに基づくアルゴリズムＡ１は、より少ない動作ＤＣ、したがって、より低い遅延で、遅延に基づくアルゴリズムＡ２よりもわずかに性能が優れている可能性がある。
【００４０】
図６Ｃにおいては、Ｎ値の増加に対する性能は、アルゴリズムＡ１（遅延に基づく）およびアルゴリズムＡ２（リスクに基づく）に対して、Ｍの最小値の平均値対Ｎに対するプロットとして示される。図６Ｄにおいては、Ｎ値の増加に対する性能は、アルゴリズムＡ１（遅延に基づく）およびアルゴリズムＡ２（リスクに基づく）に対して、要求毎の平均遅延対Ｎに対するプロットとして示される。図６Ｃおよび図６Ｄにおいては、Ｋは４に固定される。リスクに基づくアルゴリズムＡ１は、遅延に基づくアルゴリズムＡ２と比較して、Ｎが増加するにつれてより少ない動作ＤＣおよびより高い要求の遅延を結果としてもたらすことがある。図６Ｃにおいては、Ｒ＝２に対して、Ｎが１６よりも低いとき、接続の多様性が制限され（Ｎ／（２Ｒ）＜Ｋ＝４）、したがって、双方のアルゴリズムはＮが増加するにつれてより多くの動作ＤＣを必要とする。Ｎが１６よりも高いとき、接続の多様性は改善し、動作ＤＣの必要数は、Ｎが増加するにつれて減少する。
【００４１】
本明細書の主題は、一つ以上の例示的な実施形態に関連して記述されてきたが、任意の請求項を説明された特定の形式に限定することを意図するものではない。それどころか、本開示向けの任意の請求項は、その趣旨および範囲内に含まれうるような代替物、改変物および均等物を包含することを意図される。
【図１】
2014216012.tif 000008
【図２Ａ】
2014216012.tif 000009
【図２Ｂ】
2014216012.tif 000010
【図２Ｃ】
2014216012.tif 000011
【図３】
2014216012.tif 000012
【図４】
2014216012.tif 000013
【図５】
2014216012.tif 000014
【図６Ａ】
2014216012.tif 000015
【図６Ｂ】
2014216012.tif 000016
【図６Ｃ】
2014216012.tif 000017
【図６Ｄ】
2014216012.tif 000018