(57)【要約】【課題】  ネットワークを構成するデバイスの効率的な見合わせを選択する。【解決手段】  本発明は、ネットワークファームの論理仕様およびそのファームの通信モデルに応じて、ツリートポロジーネットワーク仕様をフィルタリングするコンピュータ実施される方法であって、それによって、フィルタリングされたツリートポロジーネットワーク仕様を取得する、コンピュータ実施される方法に関する。このフィルタリングされたツリートポロジーネットワーク仕様は、その内部に、ツリートポロジーネットワーク仕様に対してより少ないデバイスを有し、ファームを構築するのに必要とされるデバイスは、フィルタリングされたツリートポロジーネットワーク仕様において利用可能である。【選択図】図４
2004208296.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークファームの論理仕様（４０２）および前記ファームの通信モデル（４０２）に応じて、ツリートポロジーネットワーク仕様をフィルタリングするコンピュータ実施される方法であり、それによって、フィルタリングされたツリートポロジーネットワーク仕様を取得し、該フィルタリングされたツリートポロジーネットワーク仕様は、その内部に、前記ツリートポロジーネットワーク仕様に対してより少ないデバイスを有し、前記ファームを構築するのに必要とされるデバイスは、前記フィルタリングされたツリートポロジーネットワーク仕様において利用可能であるコンピュータ実施される方法であって、
第１のデバイスの組であって、該第１のデバイスの組の各デバイスが、冗長なデバイス、前記ファームによって必要とされないタイプを有するデバイス、および前記ファームを構築するのに利用可能でないデバイスのうちの１つを表す第１のデバイスの組と、
第１のスイッチング素子の組であって、該第１のスイッチング素子の組の各スイッチング素子が、その子供のデバイスがすべて前記第１のデバイスの組の構成要素であるスイッチング素子を表す第１のスイッチング素子の組と
を、
前記ツリートポロジーネットワーク仕様の最も低いレベル（３０２）から開始し前記ツリートポロジーネットワーク仕様のルートノード（３０８）に向かって作用して、前記ツリートポロジーネットワーク仕様から除去すること
を含むコンピュータ実施される方法。
【請求項２】
前記除去することは、前記ツリートポロジーネットワーク仕様に対してデバイスごとのフィルタ（３０２）を実行することであって、それによって、前記ツリートポロジーネットワーク仕様の最も低いレベルにおいて、第２のデバイスの組を取り除き、
該第２のデバイスの組の各デバイスは、前記ファームによって必要とされないタイプを有するデバイスおよび前記ファームを構築するのに利用可能でないデバイスのうちの１つを表し、これによって、デバイスごとのフィルタ後のツリートポロジーネットワーク仕様を取得する、デバイスごとのフィルタを実行すること
を含む請求項１に記載のコンピュータ実施される方法。
【請求項３】
前記除去することは、
前記デバイスごとのフィルタ後のツリートポロジーネットワーク仕様のスイッチング素子に対して、スイッチング素子ごとのフィルタ（３０４）を実行することであって、それによって、前記デバイスごとのフィルタ後のツリートポロジーネットワーク仕様の各スイッチング素子において、直接接続された冗長なデバイスを取り除き、これによって、スイッチング素子ごとのフィルタ後のツリートポロジーネットワーク仕様を取得する、スイッチング素子ごとのフィルタを実行すること
をさらに含む
請求項２に記載のコンピュータ実施される方法。
【請求項４】
前記除去することは、
前記スイッチング素子ごとのフィルタ後のツリートポロジーネットワーク仕様のルータに対して、ルータごとのフィルタ（３０６）を実行することであって、それによって、前記スイッチング素子ごとのフィルタ後のツリートポロジーネットワーク仕様の各ルータにおいて、冗長なスイッチを取り除き、これによって、ルータごとのフィルタ後のツリートポロジーネットワーク仕様を取得する、ルータごとのフィルタを実行すること
をさらに含む
請求項３に記載のコンピュータ実施される方法。
【請求項５】
前記ルータごとのフィルタを実行することは、
考慮中のルータに関連付けられた２つのスイッチの双方が、該２つのスイッチの該双方の下に、所与のタイプのデバイスのみを有し、かつ、該２つのスイッチを個別に考慮したときに、該２つのスイッチのいずれも、前記所与のタイプに対する前記ファームのニーズを満足するのに十分な個数の前記所与のタイプのデバイスを所有しない場合には、該２つのスイッチを論理的に組み合わせること（８６４）
をさらに含む
請求項４に記載のコンピュータ実施される方法。
【請求項６】
前記除去することは、
前記ルータごとのフィルタ後のツリートポロジーネットワーク仕様のハブに対して、ハブごとのフィルタ（３０８）を実行することであって、それによって、冗長なルータを取り除き、これにより、前記フィルタリングされたツリートポロジーネットワーク仕様を取得する、ハブごとのフィルタ（３０８）を実行すること
をさらに含む
請求項４に記載のコンピュータ実施される方法。
【請求項７】
第２のルータが、該第２のルータの下に、第１のルータが該第１のルータの下に有する少なくともすべてのデバイスを有する場合に（１１１２）、該第１のルータは、該第２のルータにとって冗長にみなされる
請求項６に記載のコンピュータ実施される方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ツリートポロジーネットワークのデバイスの高速選択用のニーズベースフィルタリングに関する。
【背景技術】
【０００２】
コンピュータネットワークは、今日、広く普及している。
通常のコンピュータネットワークでは、異なるタイプのさまざまなデバイスが、例えばルータ、スイッチ、およびハブといったスイッチング素子を介して相互接続され、それによって、デバイスが、予め定められた通信モデルに従って互いに通信することを可能にする。
【０００３】
ネットワークを、それらのネットワークを使用するアプリケーションによって必要とされるトポロジーに構成できるさまざまな方法が存在する。
最も簡単なネットワークは、適切なスイッチング素子および相互接続媒体（例えば、導電性ケーブル、光ファイバケーブル、無線媒体など）を使用して、さまざまなデバイスを共に結線することを伴う傾向がある。
結線アプローチは、比較的小さい静的なネットワーク構成についてはうまく機能するけれども、うまく拡張しないので、その結果、管理およびアップグレードが困難なネットワークになりがちである。
【０００４】
最近、コンピュータネットワークを構築するためのより柔軟性のあるアプローチが提案された。
デバイスを共に結線することにより、各ネットワークトポロジーを断片的に構築するのではなく、デバイスは、リソースの共通プールに所属するとみなされる。
このリソースの共通プールは、階層的なツリートポロジーに配置される。
ツリー内のデバイスは、決定論的な通信路に沿ってそれら自身の間で通信を行うので、階層的なツリートポロジーが選択される。
これにより、タスクのプロビジョニングおよびアップグレードが簡単になる。
階層的なツリートポロジー内では、デバイスは、スイッチング素子のプールを使用して相互接続される。
スイッチング素子をどのように構成するかに応じて、さまざまな論理ネットワークを、例えば仮想ローカルエリアネットワーク（ＶＬＡＮ）技術を使用して、デバイスおよびスイッチング素子（例えばスイッチ、ルータ、およびハブ）のこの共通プールから構築することができる。
１つの例示的なＶＬＡＮ技術の議論は、ＩＥＥＥ  ８０２．１Ｑ作業部会から得ることができる（非特許文献１；http://grouper.ieee.org/groups/802/1/、２００２年9月）。
【０００５】
このアプローチのもとでは、ツリーのデバイスおよびスイッチング素子（例えばスイッチ、ルータ、およびハブ）の共通プールに十分なリソースが存在すれば、任意の個数の論理ネットワークトポロジーを物理ネットワークから構築することができる。
例えば、ある組織が、２つのデータベースサーバと、５つのアプリケーションサーバと、４つのウェブサーバと、インターネットアクセス用の１つのファイアウォールとを有する３段のアプリケーショントポロジーの作成、またはそのトポロジーへのアップグレードを望んでいるとする。
この仕様および通信モデルから、必要なデバイス（例えば、データベースサーバ、アプリケーションサーバ、ウェブサーバ、およびファイアウォール）は、デバイスの共通プールから選択することができ、ツリーのスイッチング素子を使用して相互接続することができる。
なお、通信モデルは、そのアプリケーションに必要とされる各デバイスの通信ポリシー（予想される帯域幅使用量を含む）を統制する。
したがって、論理ネットワークトポロジーの構築は、ツリー階層に存在する利用可能なデバイスのプールから必要なデバイスを選択して、スイッチング素子を適切に構成して、通信モデルおよび論理仕様によって指定されたようにデバイスを相互接続することの実践になる。
このようなネットワーク（所与の通信モデルに従うような種々のデバイスおよびネットワーク素子を含む）は、本明細書では、「ファーム（farm）」と呼ばれる。
【０００６】
考察を容易にするために、図１は、大規模共通プールを表す例示的なデータセンター１００を示している。
この大規模共通プールは、１０種類の異なるタイプのほぼ５００個のネットワーク接続されるデバイスと、スイッチング素子とからなり、このプールからさまざまなファームを構築することができる。
データセンター１００は、階層的なツリーのルートレベルにハブ１１０１（合計４０９６Ｍｂｐｓの８つのネットワークポートを収容する）を含む。
ハブ１１０１は、９つのルータ２００１、２００２、２０１１、２０１２、２０１３、２０２１、２０２２、２０２３、および２０２４と接続される。
これらのルータは、ツリーのレベル１（ハブはレベル０である）に配置される。
【０００７】
ルータ２００１は、１５個のＮ４０００  Ｎクラスサーバ（これらのサーバは図１では「ｃｐｕ」という用語で表記される）および４つのスイッチ８０１１、８０２１、８０３１、および８０６１と接続される。
これらのサーバおよびスイッチは、ツリーのレベル２に配置される。
スイッチ８０１１、８０２１、８０３１、および８０６１のそれぞれは、１０個のＪ６０００サーバに接続される。
Ｊ６０００サーバは、ツリーのレベル３に配置される。
【０００８】
ルータ２００２は、２５個のＬ３０００サーバに接続され、Ｌ３０００サーバは、ツリーのレベル２に配置される。
図１に示すように、ルータ２０１１、２０１２、および２０１３のそれぞれは、１０個のＡ５００サーバに接続され、Ａ５００サーバは、ツリーのレベル２に配置される。
【０００９】
ルータ２０２１は、１０個の負荷分散装置（ｌｂ（load balancer））および９個のスイッチ８０４１、８０５１、８０４５、８０８１、８００１、８１３５、８９９１、８９８１、および８９７１に接続される。
これらの負荷分散装置およびスイッチは、ツリーのレベル２に配置される。
スイッチ８０４１、８０５１、および８０４５のそれぞれは、１２個のＬＰ１０００Ｒサーバに接続される。
スイッチ８０８１、８００１、および８１３５のそれぞれは、１２個のＬＰ２０００Ｒサーバに接続される。
スイッチ８９９１、８９８１、および８９７１のそれぞれは、８個のファイアウォールに接続される。
ルータ２０２１に関連付けられたＬＰ１０００Ｒサーバ、ＬＰ２０００Ｒサーバ、およびファイアウォールは、ツリーのレベル３に配置される。
【００１０】
ルータ２０２２は、１０個の負荷分散装置（ｌｂ）および９個のスイッチ８０４２、８０５２、８０４６、８０８２、８０８３、８０８４、８９９２、８９８２、および８９７２に接続される。
これらの負荷分散装置およびスイッチは、ツリーのレベル２に配置される。
スイッチ８０４２、８０５２、および８０４６のそれぞれは、１２個のＬＰ１０００Ｒサーバに接続される。
スイッチ８０８２、８０８３、および８０８４のそれぞれは、１２個のＬＰ２０００Ｒサーバに接続される。
スイッチ８９９２、８９８２、および８９７２のそれぞれは、８個のファイアウォールに接続される。
ルータ２０２２に関連付けられたＬＰ１０００Ｒサーバ、ＬＰ２０００Ｒサーバ、およびファイアウォールは、ツリーのレベル３に配置される。
【００１１】
ルータ２０２３は、１０個の負荷分散装置（ｌｂ）および５個のスイッチ８０４３、８０５３、８０５５、８０８５、および８００３に接続される。
これらの負荷分散装置およびスイッチは、ツリーのレベル２に配置される。
スイッチ８０４３、８０５３、および８０５５のそれぞれは、１２個のＬＰ１０００Ｒサーバに接続される。
スイッチ８０８５および８００３のそれぞれは、１２個のＬＰ２０００Ｒサーバに接続される。
ルータ２０２３に関連付けられたＬＰ１０００ＲサーバおよびＬＰ２０００Ｒサーバは、ツリーのレベル３に配置される。
【００１２】
ルータ２０２４は、１０個の負荷分散装置（ｌｂ）および７個のスイッチ８０４４、８０５４、８００４、８００５、８００６、８１００、および８１０１に接続される。
これらの負荷分散装置およびスイッチは、ツリーのレベル２に配置される。
スイッチ８０４４および８０５４のそれぞれは、１２個のＬＰ１０００Ｒサーバに接続される。
スイッチ８００４、８００５、および８００６のそれぞれは、１２個のＬＰ２０００Ｒサーバに接続される。
スイッチ８１００は、６つの仮想プライベートネットワーク（ＶＰＮ）ゲートウェイ（図１ではバックホール（backhauls）と表記）に接続される。
スイッチ８１０１は、４つのネットワーク接続型ストレージ（ＮＡＳ）機器(facility)および２つのＶＰＮゲートウェイに接続される。
ルータ２０２４に関連付けられたＬＰ１０００Ｒサーバ、ＬＰ２０００Ｒサーバ、ならびにＮＡＳゲートウェイおよびＶＰＮゲートウェイは、ツリーのレベル３に配置される。
【００１３】
２つのＡ５００データベースサーバと、１つのＮＡＳと、１３個のＬＰ２０００Ｒアプリケーションサーバからなるクラスタと、１つのＶＰＮゲートウェイ（バックホール）とを有する３段アーキテクチャを図１のデータセンター１００から指定する論理仕様に基づいてファームを構築したいものと仮定する。
さらに、ＬＰ２０００Ｒアプリケーションサーバ同士は互いに通信せず、また、Ａ５００データベースサーバ同士も、それら自身の間で通信しないものとする。
このファームの論理仕様を図２Ａに示す。
通信モデルを図２Ｂに示す。
データセンター１００のすべてのデバイスが、使用のために利用可能であると仮定すると、データセンター１００には、必要なファームを構築するのに十分過ぎるほどのリソースが存在する。
【００１４】
効率性が関係しない場合には、データセンター１００の利用可能なデバイスからデバイス（例えば、データベースサーバ、ＬＰ２０００Ｒアプリケーションサーバ、およびファイアウォール）をランダムに選択して、その可能な通信路に沿って配置されるスイッチング素子を適切に構成することによって、ファームを構築することができる。
しかしながら、このようなランダムなアプローチは、データセンター１００の帯域幅使用量を最適化せず、ファームのデバイス間のデータが、必要以上に多くのホップ数を巡回しなければならないことになり得る。
例えば、ＶＰＮゲートウェイとＬＰ２０００Ｒアプリケーションサーバとの間の通信を考察する。
ＶＰＮゲートウェイおよびＬＰ２０００Ｒアプリケーションサーバの双方が、スイッチ８１０１の下のＶＰＮゲートウェイおよびスイッチ８００４の下のＬＰ２０００Ｒサーバのような、ルータ２０２４の下にあるものから選択されると、ＶＰＮゲートウェイとＬＰ２０００Ｒサーバとの間の通信は、４ホップ（スイッチ８１０１、ルータ２０２４、およびスイッチ８００４を介する）しか必要としない。
他方、ＶＰＮゲートウェイが、ルータ２０２４のスイッチ８１００の下のものから選択され、ＬＰ２０００Ｒサーバが、ルータ２０２２のスイッチ８０８３の下のものから選択されると、ＶＰＮゲートウェイとＬＰ２０００Ｒサーバとの間の通信は、６ホップ（スイッチ８１００、ルータ２０２４、ハブ１１０１、ルータ２０２２、スイッチ８０８３を介する）を必要とする。
ランダムなアプローチは、構成デバイスを選択する際に、帯域幅容量も考慮しないし、輻輳も考慮しない。
【非特許文献１】http://grouper.ieee.org/groups/802/1/
【発明の開示】
【発明が解決しようとする課題】
【００１５】
先着順方式（ＦＣＦＳ（first-come-first-served））として知られている別のアプローチは、ツリーを所与の方向に巡回して、すべてのリソースの要件が満たされるまで、進路に沿ったリソースの可能な限り多くを収集するように指令する。
このアプローチのもとでは、例えば、ルータ２００１、その子ノードおよびその孫ノードを巡回し、その後、ルータ２００２、その子ノードおよびその孫ノードを巡回する（もし必要なリソースがすべて得られたならば、途中で停止する）際に遭遇したリソースを使用して、上記ファームを構築することができる。
ランダムなアプローチと同様に、帯域幅効率に関して、ファームの構成デバイスの選択にほとんどインテリジェンスがない。
したがって、デバイス選択に先着順パラダイムを使用して構築されるファームも、結果として、帯域幅が非効率的になり、性能が劣化する。
【００１６】
ツリートポロジーネットワークからファームを構築する最も効率的な構成デバイスの組は、すべての可能な置換を評価し、最も帯域幅効率の良い置換を選択した後に得ることができる。
しかしながら、このアプローチは、任意の大きなサイズ（例えば、１００を越えるデバイスを有する）のほとんどのツリートポロジーネットワークには実際的ではない。
あるサイズを越えると、ツリートポロジーネットワークに存在するデバイスの純粋な個数は、膨大な数の可能な置換の組を生み出し、これに対応して、膨大な量の計算パワーおよび時間が評価を行うのに必要となる。
【００１７】
いくつかの知的なデバイス選択アルゴリズムを使用して、ファームを構築する構成デバイスの効率的な組を選択するのに必要な時間量を削減することができる。
これらの知的なデバイス選択アルゴリズムは、ツリートポロジーネットワークのすべての可能な組み合わせの徹底的な評価を必要とはしないが、それにもかかわらず、解を見つけ出すのに必要な時間量は、ツリーネットワークトポロジーの複雑さの増加と共に拡大する。
ツリートポロジーネットワークが、デバイス選択の前に知的に簡単化されるならば、これらのデバイス選択アルゴリズムは、より一層効率的に機能することができるか、あるいは、効率的な解を見つけ出すのに全く必要とされないこともあり得る。
【課題を解決するための手段】
【００１８】
本発明は、一実施の形態において、ネットワークファームの論理仕様およびそのファームの通信モデルに応じて、ツリートポロジーネットワーク仕様をフィルタリングするコンピュータ実施される方法であって、それによって、フィルタリングされたツリートポロジーネットワーク仕様を取得する、コンピュータ実施される方法に関する。
このフィルタリングされたツリートポロジーネットワーク仕様は、その内部に、ツリートポロジーネットワーク仕様に対してより少ないデバイスを有し、ファームを構築するのに必要とされるデバイスは、フィルタリングされたツリートポロジーネットワーク仕様において利用可能である。
【００１９】
この方法は、第１のデバイスの組と、第１のスイッチング素子の組とを、ツリートポロジーネットワーク仕様の最も低いレベルから開始しツリートポロジーネットワーク仕様のルートノードに向かって作用して、ツリートポロジーネットワーク仕様から除去することを含む。
第１のデバイスの組の各デバイスは、冗長なデバイス、ファームによって必要とされないタイプを有するデバイス、およびファームを構築するのに利用可能でないデバイスのうちの１つを表す。
第１のスイッチング素子の組の各スイッチング素子は、その子供のデバイスがすべて第１のデバイスの組の構成要素であるスイッチング素子を表す。
【００２０】
別の実施の形態によると、本発明は、当該実施の形態に具現化されたコンピュータ読み取り可能コードを有するプログラム記憶媒体を備えた製品に関する。
このコンピュータ読み取り可能コードは、ネットワークファームの論理仕様およびそのファームの通信モデルに応じて、ツリートポロジーネットワーク仕様をフィルタリングするように構成され、それによって、フィルタリングされたツリートポロジーネットワーク仕様を取得する。
このフィルタリングされたツリートポロジーネットワーク仕様は、その内部に、ツリートポロジーネットワーク仕様に対してより少ないデバイスを有する。
ファームを構築するのに必要とされるデバイスは、フィルタリングされたツリートポロジーネットワーク仕様において利用可能である。
第１のデバイスの組と、第１のスイッチング素子の組とを、ツリートポロジーネットワーク仕様の最も低いレベルから開始しツリートポロジーネットワーク仕様のルートノードに向かって作用して、ツリートポロジーネットワーク仕様から除去するコンピュータ読み取り可能コードが含まれる。
第１のデバイスの組の各デバイスは、冗長なデバイス、ファームによって必要とされないタイプを有するデバイス、およびファームを構築するのに利用可能でないデバイスのうちの１つを表す。
第１のスイッチング素子の組の各スイッチング素子は、その子供のデバイスがすべて第１のデバイスの組の構成要素であるスイッチング素子を表す。
【００２１】
さらに別の実施の形態では、本発明は、ネットワークファームの論理仕様およびそのファームの通信モデルに応じて、ツリートポロジーネットワーク仕様をフィルタリングするコンピュータ実施される方法であって、それによって、フィルタリングされたツリートポロジーネットワーク仕様を取得する、コンピュータ実施される方法に関する。
このフィルタリングされたツリートポロジーネットワーク仕様は、その内部に、ツリートポロジーネットワーク仕様に対してより少ないデバイスを有する。
ファームを構築するのに必要とされるデバイスは、フィルタリングされたツリートポロジーネットワーク仕様において利用可能である。
この方法は、ツリートポロジーネットワーク仕様に対してデバイスごとのフィルタを実行することであって、それによって、ツリートポロジーネットワーク仕様の最も低いレベルにおいて、第１のデバイスの組の各デバイスを取り除き、この第１のデバイスの組の各デバイスは、ファームによって必要とされないタイプを有するデバイスおよびファームを構築するのに利用可能でないデバイスのうちの１つを表し、これによって、デバイスごとのフィルタ後のツリートポロジーネットワーク仕様を取得する、デバイスごとのフィルタを実行することをさらに含む。
この方法は、デバイスごとのフィルタ後のツリートポロジーネットワーク仕様のスイッチング素子に対して、スイッチング素子ごとのフィルタを実行することであって、それによって、デバイスごとのフィルタ後のツリートポロジーネットワーク仕様の各スイッチング素子において、直接接続された冗長なデバイスを取り除き、これによって、スイッチング素子ごとのフィルタ後のツリートポロジーネットワーク仕様を取得する、スイッチング素子ごとのフィルタを実行することをさらに含む。
なお、少なくとも１つのスイッチング素子は、スイッチ、ルータ、およびハブのうちの１つを表す。
この方法は、スイッチング素子ごとのフィルタ後のツリートポロジーネットワーク仕様のルータに対して、ルータごとのフィルタを実行することであって、それによって、スイッチング素子ごとのフィルタ後のツリートポロジーネットワーク仕様の各ルータにおいて、冗長なスイッチを取り除き、これによって、ルータごとのフィルタ後のツリートポロジーネットワーク仕様を取得する、ルータごとのフィルタを実行することも含む。
この方法は、ルータごとのフィルタ後のツリートポロジーネットワーク仕様のハブに対して、ハブごとのフィルタを実行することであって、それによって、冗長なルータを取り除き、これにより、フィルタリングされたツリートポロジーネットワーク仕様を取得する、ハブごとのフィルタを実行することをさらに含む。
【００２２】
またさらに別の実施の形態では、本発明は、提供された論理仕様および提供されたファームの通信モデルと一致するネットワークファームを作成する装置に関する。
論理仕様は、ファームによって必要とされるデバイスのタイプ、および、ファームによって必要とされるデバイスのタイプのそれぞれのデバイスの個数を指定する。
通信モデルは、ファームの各タイプのデバイスの帯域幅使用量を指定する。
この装置は、ツリートポロジーに配置されたデバイスおよびスイッチング素子をその内部に有するツリートポロジーネットワークを含む。
この装置は、論理仕様およびファームの通信モデルに応じて、ツリートポロジーネットワークのツリートポロジーネットワーク仕様をフィルタリングするコンピュータ読み取り可能コードであって、それによって、フィルタリングされたツリートポロジーネットワーク仕様を取得する、コンピュータ読み取り可能コード、を実行するコンピュータ装置をさらに含む。
このフィルタリングされたツリートポロジーネットワーク仕様は、その内部に、ツリートポロジーネットワーク仕様に対してより少ないデバイスを有する。
ファームを構築するのに必要とされるデバイスは、フィルタリングされたツリートポロジーネットワーク仕様において利用可能である。
フィルタリングするコンピュータ読み取り可能コードは、第１のデバイスの組と、第１のスイッチング素子の組とを、ツリートポロジーネットワーク仕様の最も低いレベルから開始しツリートポロジーネットワーク仕様のルートノードに向かって作用して、ツリートポロジーネットワーク仕様から除去するコンピュータ読み取り可能コードを含む。
第１のデバイスの組の各デバイスは、冗長なデバイス、ファームによって必要とされないタイプを有するデバイス、およびファームを構築するのに利用可能でないデバイスのうちの１つを表す。
第１のスイッチング素子の組の各スイッチング素子は、その子供のデバイスがすべて第１のデバイスの組の構成要素であるスイッチング素子を表す。
【００２３】
本発明のこれらの特徴および他の特徴は、本発明の詳細な説明において図面と共に、以下においてさらに詳細に説明される。
【００２４】
本発明を、添付図面の図の例によって説明するが、この例は、本発明を限定するものではない。
添付図面において、同じ参照符号は、同様の構成要素を参照する。
【発明を実施するための最良の形態】
【００２５】
ここで、本発明を、添付図面に示すような本発明のいくつかの好ましい実施の形態を参照して詳細に説明する。
以下の説明では、本発明の十分な理解を提供するために、多数の具体的な詳細を述べる。
しかしながら、これらの具体的な詳細のいくつかまたはすべてがなくても本発明を実施できることが、当業者には明らかである。
他の例では、本発明を不必要に分かりにくくすることがないように、周知のプロセスのステップおよび／または構造は、詳細に説明されていない。
【００２６】
本発明の一実施の形態によると、デバイス選択の前に、ツリートポロジーネットワークのデバイスの個数およびスイッチング素子（すなわち、ハブ、ルータ、またはスイッチ）の個数を削減するフィルタリング技法が提供される。
このフィルタリング技法は、ファームのニーズ、すなわちデバイスの帯域幅要件、１つまたは２つ以上のデバイスがそれを通じて通信するスイッチング素子の帯域幅を考慮して、冗長なデバイスおよびスイッチング素子をツリートポロジーネットワークから除去する。
好都合なことに、フィルタリングされたツリートポロジーネットワーク（ＦＴＴＮ（filtered tree topology network））は、ファームが必要とするすべてのリソースを有し、ＦＴＴＮにより利用可能な最良の解は、フィルタリングされていないＴＴＮ（ＵＴＴＮ（unfiltered TTN））により利用可能な最良の解と実質的に同程度に効率的である。
このように、問題の組は削減され、効率的な解を見つけ出すために評価する必要のある置換は少なくなる。
【００２７】
図３は、本発明にかかるアルゴリズムを、ソフトウェアにより実現するコンピュータを示す。
以下に示すアルゴリズムは、図３に示すコンピュータにおいて動作するソフトウェアにより実現される。
図４は、本発明の一実施の形態によるニーズベースフィルタリングアルゴリズムを示している。
高いレベルにおいて、このフィルタリングアルゴリズムは、トポロジーツリーネットワークまたはそのコピーを下から上にフィルタリングすること、およびフィルタリングの進行につれて余分なものを取り除くことを含む。
したがって、ブロック３０２では、デバイスがフィルタリングされて、不要なタイプのデバイスが除去される。
一般的に言うと、各デバイスタイプについて、次の２つのパラメータが保持される。
１）ＳＥＬＦＴＡＬＫ。
これは、特定のデバイスタイプのデバイスが、互いの間でデータ伝送できるかどうかを示す。
２）ＷＯＲＳＴＣＡＳＥ帯域幅。
これは、特定のタイプのデバイスの最悪の場合の帯域幅要件を表す。
本明細書の図５は、デバイスごとのフィルタプロセスの一実施の形態をより詳細に説明している。
【００２８】
ブロック３０４では、それぞれのスイッチング素子（スイッチ、ルータおよびハブ）のレベルで、フィルタリングが実行される。
一般的に言うと、この段階では、不要なデバイスは、先のブロック３０２ですでに除去されており、ブロック３０４のスイッチング素子ごとのフィルタプロセスは、スイッチング素子から直接接続された冗長なデバイスを除去することを含む。
本明細書の図７は、スイッチング素子ごとのフィルタプロセスの一実施の形態をより詳細に説明している。
【００２９】
ブロック３０６では、ルータのレベルでフィルタリングが実行される。
一般的に言うと、冗長なスイッチはこのプロセスで削除される。
さらに、スイッチが、特定のデバイスタイプに関するファームのニーズを満たすために「組み合わされる」ことが有利な場合には、そうされる。
本明細書の図９Ａ、図９Ｂおよび図１０は、ルータごとのフィルタプロセスの一実施の形態をより詳細に説明している。
【００３０】
ブロック３０８では、ハブのレベルでフィルタリングが実行される。
一般的に言うと、冗長なルータはこのプロセスで削除される。
本明細書の図１２は、ハブごとのフィルタプロセスの一実施の形態をより詳細に説明している。
【００３１】
図４のそれぞれのブロックには、さらに別の複雑さ、ニュアンスおよび最適化が存在する。
これらは、以下に続く図を参照することによって、より良く理解することができる。
【００３２】
図５は、本発明の一実施の形態による、図４のブロック３０２のデバイスごとのフィルタプロセスを示している。
ブロック４０２では、ファームによって要求される各デバイスタイプの個数、通信モデルおよびツリートポロジーネットワークのハードウェアモデルが受け取られる。
ハードウェアモデルには、利用可能な帯域幅が含まれる。
ブロック４０４では、配列ＳＥＬＦＴＡＬＫが偽（false）に初期化される。
この配列ＳＥＬＦＴＡＬＫの要素は、同じ所与のタイプのデバイスからなる複数のデバイスがそれらデバイスの間で通信できるかどうかを追跡するために使用される。
配列ＷＯＲＳＴＣＡＳＥが０に初期化される。
この配列ＷＯＲＳＴＣＡＳＥの要素は、各デバイスタイプの最悪の場合の帯域幅を追跡するために使用される。
ツリートポロジーネットワークのハブのオーバレイ画像（例えばコピー）も４０４で作成され、フィルタ操作を容易にする。
このフィルタ操作は、ＯＶＥＲＬＡＹ（オーバレイ）ツリーに対して行われる。
【００３３】
ブロック４０６では、処理すべきさらに別のデバイスタイプが存在するかどうかが確認される。
処理すべきさらに別のデバイスタイプが存在する場合には、本方法はブロック４０８に進み、ブロック４０８において、一時変数Ｄが、次のデバイスタイプとなるように設定される。
ブロック４１０では、ブロック４０２で提供された通信モデルに対して簡単なチェックが行われ、タイプＤのデバイスが互いにデータ伝送できるかどうかが決定される。
タイプＤのデバイスが互いにデータ伝送できる場合には、配列ＳＥＬＦＴＡＬＫの対応する配列要素が、この特性を反映するためにブロック４１２で真（true）に設定される。
【００３４】
ブロック４１４では、デバイスタイプＤの最悪の場合の帯域幅要件を追跡するために使用される配列ＷＯＲＳＴＣＡＳＥの配列要素が、デバイスタイプＤの通信モデルによって示される最大帯域幅要件に設定される。
ブロック４１６では、タイプＤのすべての自由なデバイスがＯＶＥＲＬＡＹに追加される。
この自由なデバイスには、それらの親のスイッチおよびルータが含まれる。
ブロック４１６の作用は、自由で、かつファームにとって必要なタイプを有するデバイスのみを、ツリーネットワークからＯＶＥＲＬＡＹに加えることである。
これにより、ファームによって必要とされないすべてのデバイス、またはその探索における考慮事項から、自由でないデバイスが削除される。
【００３５】
その後、本方法はブロック４０６に戻り、次のデバイスタイプを処理する。
このプロセスは、すべてのデバイスタイプが処理されるまで続く。
すべてのデバイスタイプが処理されると、本方法はブロック４２０で終了する。
【００３６】
図６は、図５のフィルタリングプロセスが図１のツリーネットワークに対して完了した後のＯＶＥＲＬＡＹツリーを示している。
本実施例では、元の図１に示すすべてのデバイスが自由であり、かつファームの構築の使用に対して利用可能であると仮定される。
図１の元のツリートポロジーネットワークと比較すると、不要なデバイスが削除されている。
例えば、ルータ２００１およびルータ２００２を参照すると、これらのルータは、ファームによって必要とされるデバイスを全く持っていない。
これらの不要なデバイスは、ブロック４１６によってＯＶＥＲＬＡＹツリーに加えられず、その結果図６には存在しないので、それらの親のスイッチおよびルータもＯＶＥＲＬＡＹツリーに加えられない。
ルータ２０１１、２０１２、２０１３はすべて、１０個のａ５００サーバをそれぞれ有する。
本実施例では、これらのａ５００サーバが必要とされ、したがって、すべてのａ５００サーバがＯＶＥＲＬＡＹツリーに加えられる。
図６から分かるように、それらの親のスイッチおよびルータも加えられる。
【００３７】
ルータ２０２１を参照すると、図１に示す負荷分散装置、ＬＰ１０００Ｒサーバおよびファイアウォールは必要とされず、したがって、ＯＶＥＲＬＡＹツリーに加えられていない。
しかし、ＬＰ２０００Ｒサーバはファームによって必要とされ、したがってＯＶＥＲＬＡＹツリーに加えられている。
図６から分かるように、それらの親のスイッチおよびルータも加えられる。
【００３８】
図７は、本発明の一実施の形態による、図４のブロック３０４のプロセスを示している。
ブロック６０４では、ＯＶＥＲＬＡＹツリーに任意の別のスイッチング素子が存在するかどうかが確認される。
処理されるさらに別のスイッチング素子が存在する場合には、本方法はブロック６０６に進み、ブロック６０６において、一時変数Ｓが次のスイッチング素子に設定され、Ｓによって表されるこのスイッチング素子のＷＯＲＳＴＣＡＳＥが０に設定される。
ブロック６０８では、処理すべきスイッチング素子Ｓの下にさらにデバイスタイプが存在するかどうかが確認される。
存在する場合には、本方法はブロック６１０に進み、一時変数Ｄを次のデバイスタイプに設定し、一時変数ＮをデバイスタイプＤのニーズ（このニーズは論理仕様から得られる）に設定する。
【００３９】
ブロック６１２では、スイッチング素子Ｓが、一時変数Ｎによって表されるニーズよりも多くの直接接続されたタイプＤのデバイスを有するかどうかが確認される。
スイッチング素子Ｓが、一時変数Ｎによって表されるニーズよりも多くの直接接続されたタイプＤのデバイスを有する場合には、ブロック６１４において、過剰なすべてのタイプＤのデバイスがＯＶＥＲＬＡＹツリーから取り除かれる。
したがって、ブロック６１４の作用は、スイッチング素子から、冗長な直接接続されたデバイスを除去することである。
【００４０】
ブロック６１５では、スイッチング素子Ｓの最悪の場合の帯域幅を追跡するＷＯＲＳＴＣＡＳＥ配列の要素が、ＯＶＥＲＬＡＹのそのスイッチング素子Ｓに接続されるこのデバイスタイプＤの残りの個数と、このデバイスタイプの最悪の場合の帯域幅（この帯域幅は、図５のブロック４１４のＷＯＲＳＴＣＡＳＥ（タイプ）によって追跡されたものである）とを乗算した値を、ＷＯＲＳＴＣＡＳＥ配列のこの要素の現在存在する値に加算した値に等しくなるように設定される。
好ましくは、両方向の最悪の場合のシナリオがスイッチング素子Ｓに対して追跡される（すなわち、それぞれスイッチング素子Ｓの上方向および下方向を通る）。
この状況は、そのスイッチング素子に接続されたタイプＤのデバイスからそのスイッチング素子を通って流れることができる最大帯域幅を追跡するために使用される。
さらに、ブロック６０７では、親のスイッチング素子（例えば、スイッチ８０８２が考慮中の場合にはルータ２０２２）に関連付けられた変数ＦＲＥＥが、タイプＤのデバイスの個数分、（最大でＮＥＥＤまで）インクリメントされる。
【００４１】
その後、プロセスはブロック６０８に戻り、スイッチング素子Ｓの下の次のデバイスタイプを処理する。
スイッチング素子Ｓの下のすべてのデバイスタイプが処理されると、本方法は、ブロック６０８からブロック６１８に進み、スイッチング素子Ｓが２つ以上のデバイスタイプを有するかどうかをチェックする（ブロック６１８）。
スイッチング素子Ｓが１つしかデバイスタイプを有しない場合には、プロセスはブロック６２０に進み、ブロック６２０において、スイッチング素子ＳはＭＯＮＯＣＨＲＯＭＥ（モノクロ）とラベル付けされ、以下の変数が設定される。
【００４２】
ＵＰ＝ａｖａｉｌＵＰＢＷ／ＷＯＲＳＴＣＡＳＥｕｐ（Ｄ）
ＤＯＷＮ＝ａｖａｉｌＤＯＷＮＢＷ／ＷＯＲＳＴＣＡＳＥｄｏｗｎ（Ｄ）
ＵＳＡＢＬＥ＝ｍｉｎ（ＮＥＥＤ、ＵＰ、ＤＯＷＮ）
【００４３】
変数ＵＰは、スイッチング素子Ｓに利用可能な上りの帯域幅と、タイプＤのデバイスの上り方向の最悪の場合の帯域幅要件とを与えられたＭＯＮＯＣＨＲＯＭＥのスイッチング素子ＳがサポートできるタイプＤのデバイスの個数を追跡する。
変数ＤＯＷＮは、スイッチング素子Ｓに利用可能な下りの帯域幅と、タイプＤのデバイスの下り方向の最悪の場合の帯域幅要件とを与えられたＭＯＮＯＣＨＲＯＭＥのスイッチング素子ＳがサポートできるタイプＤのデバイスの個数を追跡する。
変数ＵＳＡＢＬＥは、このＭＯＮＯＣＨＲＯＭＥのスイッチング素子がサポートできるタイプＤのデバイスの最大個数を追跡する。
次に、プロセスはブロック６０４に進み、さらにスイッチング素子が存在するかどうかをチェックする。
ブロック６１８において、デバイスのタイプが２つ以上存在する場合には、そのスイッチはＭＯＮＯＣＨＲＯＭＥとラベル付けすることができず、プロセスはブロック６０４に直接進む。
【００４４】
他方、ブロック６０４において、ＯＶＥＲＬＡＹツリーにスイッチング素子がもはや存在しない場合には、プロセスはブロック６２６で終了する、と確認される。
【００４５】
図８は、図７のスイッチング素子ごとのフィルタプロセスの完了後のＯＶＥＲＬＡＹツリーを示している。
冗長な直接接続されたデバイスが、スイッチング素子から削除されていることに留意されたい。
例えば、ルータ２０２４のスイッチ８１０１の下では、図２Ａの論理仕様が１つのＮＡＳのみを要求していることから、ＮＡＳの個数が図６の４つから図８では１つに削減されている。
同様に、ルータ２０２４のスイッチ８１００の下では、図２Ａの論理仕様が１つのＶＰＮゲートウェイのみを要求していることから、ＶＰＮゲートウェイ（バックホール）の個数が、図６の６つから図８では１つに削減されている。
明らかに冗長な多くのスイッチが存在するものの、それらのいくつかは、それ以外のスイッチよりもファームを構築するのにより適している。
これらの冗長な多くのスイッチは、図７のスイッチング素子ごとのフィルタプロセスでは削除されない。
これらのスイッチは、本明細書では、次のフィルタリングプロセスで削除されることになる。
さらに、ルータ（およびハブ）の次にある括弧内の符号は、そのルータ（およびハブ）に関連付けられたＦＲＥＥのデバイスを反映する。
例えば、ルータ２０２１は、１３個のＬＰ２０００Ｒサーバを提供できる一方、ルータ２０２４は、１３個のＬＰ２０００Ｒサーバ、１つのＮＡＳデバイスおよび１つのバックホールデバイスを提供できる。
【００４６】
図９Ａおよび図９Ｂは、本発明の一実施の形態による、図４のブロック３０６のルータごとのフィルタプロセスを示している。
一般的に言うと、図９Ａおよび図９Ｂは、ルータの下の１つまたは２つ以上のスイッチを除去すること（図９Ａ）、または特定のデバイスタイプのニーズを満たすルータの下のスイッチを組み合わせること（図９Ｂ）のいずれかを目的とする。
図９Ａでは、ブロック８０２において、ＯＶＥＲＬＡＹツリーに処理すべきルータがさらに存在するかどうかが確認される。
処理すべきルータがさらに存在する場合には、本方法はブロック８０４に進み、１つずつルータの処理を開始する。
したがって、ブロック８０４では、一時変数Ｒが次のルータとなるように設定され、ルータＲの子供上のパス１が開始される。
図９Ａおよび図９Ｂの状況において、パス１は、冗長なスイッチを削除する図９Ａの処理を表す。
パス２は、必要に応じてスイッチを組み合わせる図９Ｂの処理を表す。
【００４７】
ブロック８０６では、ルータＲの下に、処理すべきスイッチの子供がさらに存在するかどうかが確認される。
ルータＲの下に、処理すべきスイッチの子供がさらに存在する場合には、本方法はブロック８０８に進み、ブロック８０８において、一時変数ＳがＲの次の子供スイッチに設定される。
ステップ８１０では、スイッチＳが、最悪の場合の帯域幅要求に対処する帯域幅を有するかどうかが、図７のブロック６１６で計算されたＷＯＲＳＴＣＡＳＥ（Ｓ）に基づいて確認される。
このチェックは、最悪の場合の帯域幅要求に対処できないスイッチは、冗長なスイッチを削除する目的での他のスイッチとの比較において「勝つ」ことができないことを確実にする。
したがって、スイッチＳが、最悪の場合の帯域幅要求に対処する帯域幅を有しない場合には、プロセスはブロック８０６に戻り、ルータＲの次の子供スイッチを処理する。
【００４８】
他方、最悪の場合の帯域幅要求に対処する帯域幅がスイッチＳに残っている場合には、本方法はブロック８１２に進み、ブロック８１２において、ルータＲの他のすべてのスイッチの子供がリストＢに記憶される。
その後、リストＢのそれぞれの子供はスイッチＳと比較される。
この比較は、比較されるリストＢの子供が安全に削除可能かどうかを判断するために行われる。
したがって、ブロック８１４では、処理すべきスイッチが、リストＢにさらに存在するかどうかが確認される。
処理すべきスイッチがリストＢにもはや存在しない場合には、本方法はブロック８０６に戻り、ルータＲの次の子供のスイッチを処理する。
【００４９】
他方、処理すべきスイッチがリストＢにさらに存在する場合には、本方法はブロック８１６に進みに、ブロック８１６において、一時変数ＴがリストＢの次のスイッチとなるように設定される。
ブロック８１８では、スイッチＴが削除可能かどうかを確認する試験が実行される。
一実施の形態では、スイッチＴは、以下の２つの条件が満たされる場合に削除可能である。
第１の条件は、スイッチＳまたはスイッチＴが、それぞれが有するすべてのデバイスタイプについてのすべてのニーズを満足する場合に満たされることである。
第２の条件は、スイッチＳの下の自由なデバイスの個数が、スイッチＴのすべてのデバイスタイプについてスイッチＴの下の自由なデバイスの個数以上である場合に満たされることである。
例えば、スイッチ８０８１は、（それに接続されたシステムの点で）スイッチ８００１およびスイッチ８１３５と同一である。
しかしながら、それらのいずれも、１３個のＬＰ２０００Ｒサーバの要求を満たさないので、他のものを削除できない。
【００５０】
ブロック８１８の双方の条件が満たされない場合には、本方法はブロック８１４に戻り、リストＢの次のスイッチを処理する。
他方、ブロック８１８の双方の条件が満たされる場合には、本方法はブロック８２０に進み、ブロック８２０において、スイッチＴがＯＶＥＲＬＡＹツリーから除去される。
その後、本方法はまた、ブロック８１４に戻り、リストＢの次のスイッチを処理する。
【００５１】
ブロック８０６において、ルータＲの処理すべきスイッチの子供がもはや存在しないと判断されると、本方法は図９に進み、ルータＲの残りの子供スイッチのパス２の処理を開始する。
【００５２】
図９Ｂでは、ファームのニーズを満たすルータの下のスイッチを組み合わせることが有利な場合に、そうすることがその目的である。
したがって、ブロック８５２では、リストＬｉｓｔｓｂｙＴｙｐｅ（タイプごとのリスト）がヌルに初期化される。
各リストＬｉｓｔｓｂｙＴｙｐｅは、特定のルータについて、ある特定のタイプのデバイスを供給するＭＯＮＯＣＨＲＯＭＥスイッチを追跡する。
例えば、ルータ２０２３の下では、スイッチ８０８５および８００３は、ともにＬＰ２０００Ｒサーバを供給するＭＯＮＯＣＨＲＯＭＥスイッチである。
さらに、変数Ｕｓａｂｌｅｂｙｔｙｐｅ（タイプごとの使用可能）がゼロに設定される。
この変数Ｕｓａｂｌｅｂｙｔｙｐｅは、所与のスイッチが実際にサービスを提供することができる特定のタイプのデバイスの個数を追跡するために使用される。
自由（free）と使用可能（usable）との間の相違を明確にするために、以下の例を考察する。
スイッチは、その下に、１２個の自由なＬＰ２０００Ｒサーバを有するが、１０個にしかサービスを提供する帯域幅を有しない場合がある。
その場合、そのスイッチの下には、１２個の自由なＬＰ２０００Ｒサーバが存在するにもかかわらず、そのスイッチのＬＰ２０００ＲのＵｓａｂｌｅｂｙｔｙｐｅは１０である。
Ｕｓａｂｌｅｂｙｔｙｐｅの数は、特定のデバイスタイプに関して、より現実的なスイッチの能力の評価値である。
【００５３】
ブロック８５４では、ルータＲの下に、処理すべきＭＯＮＯＣＨＲＯＭＥスイッチがさらに残っているかどうかが確認される。
例えば、図８のルータ２０２４に関しては、３つのＭＯＮＯＣＨＲＯＭＥスイッチ８００４、８００５および８００６が存在する。
残っている場合には、ブロック８５４からブロック８５６へのループにより、ＭＯＮＯＣＨＲＯＭＥスイッチの下のタイプごとの使用可能なすべてのデバイスが合計され、それらは変数Ｕｓａｂｌｅｂｙｔｙｐｅに割り当てられる。
したがって、この例では、ルータ２０２４の下のＬＰ２０００ＲサーバのＵｓａｂｌｅｂｙｔｙｐｅの数は、３０になる（スイッチ８００４，８００５および８００６のそれぞれは、１０個の使用可能なＬＰ２０００Ｒサーバを有するため）。
さらに、リストＬｉｓｔｓｂｙＴｙｐｅは、ルータ２０２４について、３つのスイッチ８００４、８００５および８００６を、ＬＰ２０００Ｒサーバを供給するＭＯＮＯＣＨＲＯＭＥスイッチとして追跡することになる。
このことは、ブロック８５６に示されている。
【００５４】
ブロック８５４によって判断されるように、処理すべきＭＯＮＯＣＨＲＯＭＥスイッチが残っていない場合には、本方法はブロック８５８に進む。
ブロック８５８は、残りのステップが、ＭＯＮＯＣＨＲＯＭＥスイッチのフィルタリングを主として取り扱うことを示すラベルまたはコメントである。
ブロック８６０では、処理すべき非空のＬｉｓｔｓｂｙＴｙｐｅがさらに存在するかどうかが確認される。
処理すべき非空のＬｉｓｔｓｂｙＴｙｐｅがさらに存在する場合には、本方法はブロック８６２に進む。
【００５５】
ルータ２０２４を取り扱う例を参照すると、１つの非空のＬｉｓｔｓｂｙＴｙｐｅ（すなわち、ＬＰ２０００Ｒサーバを供給する３つのＭＯＮＯＣＨＲＯＭＥスイッチ８００４、８００５および８００６を追跡する１つの非空のＬｉｓｔｓｂｙＴｙｐｅ）が存在する。
したがって、ブロック８６２では、一時変数Ｌが次のＭＯＮＯＣＨＲＯＭＥリストとなるように設定される。
本実施例では、一時変数Ｌは、ＬＰ２０００Ｒサーバを供給する３つのＭＯＮＯＣＨＲＯＭＥスイッチ８００４、８００５および８００６を追跡する１つの非空のＬｉｓｔｓｂｙＴｙｐｅに設定される。
ブロック８６４では、プロセスＣＯＭＢＩＮＥ（組み合わせ）が呼び出されて、適切な場合にはデバイスを組み合わせる。
ブロック８６４のＣＯＭＢＩＮＥプロセスは、本明細書の図１０との関連において説明される。
図１０のＣＯＭＢＩＮＥプロセスが完了した後、本方法はブロック８６０に戻り、処理すべき非空のＬｉｓｔｓｂｙＴｙｐｅがさらに存在するかどうかを確認する。
処理すべき非空のＬｉｓｔｓｂｙＴｙｐｅがもはや存在しない場合には、本方法は、図９Ｂのブロック８６０から図９Ａのブロック８０２に進み、次のルータが存在すれば、そのルータをブロック８０６で処理する。
【００５６】
図１０は、本発明の一実施の形態による、図９Ｂのブロック８６４によって呼び出されるＣＯＭＢＩＮＥプロセスを示している。
図１０では、各ルータにおいて、ある特定のデバイスタイプを提供するＭＯＮＯＣＨＲＯＭＥスイッチが組み合わされて、そのタイプの複数のデバイスにサービスを提供するさらに大きな論理スイッチを作成することが目的である。
ブロック９０２では、デバイスタイプが、セルフトーク（self talk）可能なものであるかどうか、すなわち、このタイプのデバイスが互いに通信できるかどうかが確認される。
このパラメータは通信モデルによって供給され、セルフトークが可能かどうかを示す前述の図５のブロック４１２の変数ＳＥＬＦＴＡＬＫによって追跡される。
本実施例のＬＰ２０００Ｒサーバの場合のように、このデバイスタイプがセルフトーク可能なものでない場合には、ブロック９０４は、現在考慮中のタイプのすべてのデバイスを、ファームによって必要とされるこのタイプのデバイスの個数に至るまで、より大きな論理スイッチの下に一緒にまとめる。
【００５７】
一実施の形態では、これは、デバイスへのポインタをコピーして、スイッチの１つの下にそれらを統合することにより達成される（どのスイッチにするかの正確な選択は任意である。
その理由は、同じルータの下のすべての同様のデバイスは、およそ同じ通信コストを有するとみなされるからである）。
また、ブロック９０４では、このタイプのそれ以外のすべてのデバイスが、それらの親スイッチと共に除去される。
図８の例に関して見ると、例えば、ルータ２０２４の下の３６個のセルフトークできないＬＰ２０００Ｒが、ファームによって必要とされる最大１３個のＬＰ２０００Ｒサーバまでは、論理スイッチ８００４の下に統合される。
また、それ以外のすべてのＬＰ２０００Ｒデバイスは、それらの親スイッチ（すなわち、スイッチ８００５および８００６）と共に除去される。
その後、図１０のプロセスは終了し、呼び出し側プロセスに戻る。
【００５８】
他方で、このデバイスタイプのデバイスがセルフトーク可能である場合には、本方法はブロック９０６に進む。
ブロック９０６では最小のスイッチの組が構築される。
この構築は、最大のＵｓａｂｌｅｂｙｔｙｐｅを有するスイッチを当該組に追加することから開始して、タイプごとに必要なデバイスの個数が満たされるまで、次に大きなＵｓａｂｌｅｂｙｔｙｐｅのスイッチを当該組に繰り返し追加して行くことにより行われる。
まず、図９のＬｉｓｔｓｂｙＴｙｐｅのＭＯＮＯＣＨＲＯＭＥスイッチを取り除くことができることを確実にするために、簡単なチェックが行われる。
したがって、ブロック９０６では、ＬｉｓｔｓｂｙＴｙｐｅリストのＭＯＮＯＣＨＲＯＭＥスイッチの個数が少なくとも３つであるかどうかが確認される。
これは、この時点で、単一のＭＯＮＯＣＨＲＯＭＥスイッチが、そのタイプに対するニーズを満足する、当該タイプのすべてのデバイスを有しているとは限らず、ＭＯＮＯＣＨＲＯＭＥスイッチが２つ、または、それより少ない個数しかリストに存在しない場合、それらＭＯＮＯＣＨＲＯＭＥスイッチは取り除くことができないからである。
３つ以上のＭＯＮＯＣＨＲＯＭＥスイッチが存在し、リストのタイプに関連付けられたすべてのＭＯＮＯＣＨＲＯＭＥスイッチのＵｓａｂｌｅｂｙｔｙｐｅの値（すなわち、そのタイプに関連付けられたすべてのＭＯＮＯＣＨＲＯＭＥスイッチのＵｓａｂｌｅｂｙｔｙｐｅパラメータの集合）が、そのタイプのデバイスの必要な個数より大きい場合には、取り除くことが可能である。
ブロック９０６の検査により、取り除くことが可能ではないと確認された場合には、本方法はブロック９４８に進み、呼び出し側プロセスに戻る。
【００５９】
ブロック９０６の検査により、取り除くことが可能であると確認された場合には、本方法は、ブロック９０６からブロック９０８に進む。
ブロック９０８では、一時リストＳＥＴ（設定）がヌルに初期化され、Ｕｓａｂｌｅｂｙｔｙｐｅの値のＳＵＭ（総和）が、この一時ＳＥＴ用に０にされる。
ブロック９１０では、Ｕｓａｂｌｅｂｙｔｙｐｅの現在のＳＵＭが、そのタイプのデバイスの必要な個数より小さいかどうかが確認される。
Ｕｓａｂｌｅｂｙｔｙｐｅの現在のＳＵＭが、デバイスの必要な個数より小さい場合には、一時ＳＥＴにはまだ存在しない最大のＵｓａｂｌｅｂｙｔｙｐｅの値を有するスイッチＧが、一時ＳＥＴに追加される。
そして、ＵｓａｂｌｅｂｙｔｙｐｅのＳＵＭは、現在のＳＵＭの値に、新しく追加されたスイッチＧのＵｓａｂｌｅｂｙｔｙｐｅの値を追加することにより更新される。
その後、本方法はブロック９１０に戻り、Ｕｓａｂｌｅｂｙｔｙｐｅの現在のＳＵＭが、そのタイプのデバイスの必要な個数よりもまだ小さいかどうかを確認する。
そして、本方法は、ブロック９１０において、Ｕｓａｂｌｅｂｙｔｙｐｅの現在のＳＵＭが、そのタイプのデバイスの必要な個数よりもまだ小さいと確認された場合には、次に大きなＵｓａｂｌｅｂｙｔｙｐｅの値を有するスイッチを一時ＳＥＴに追加する。
【００６０】
このようにして、本方法は、最大のＵｓａｂｌｅｂｙｔｙｐｅの値を有するスイッチからまず開始して、一時ＳＥＴのＵｓａｂｌｅｂｙｔｙｐｅの総計ＳＵＭが、タイプごとのデバイスの必要な個数以上になるまでスイッチを累積していくことにより、一時ＳＥＴを増加させる。
一時ＳＥＴのＵｓａｂｌｅｂｙｔｙｐｅの総計ＳＵＭが、デバイスの必要な個数以上になるとすぐに、本方法はブロック９１２に進み、このルータについて、一時ＳＥＴに追加されなかった、このタイプに関連付けられたすべてのＭＯＮＯＣＨＲＯＭＥスイッチを除去する。
したがって、組み合わせが、そのタイプのデバイスに対するファームのニーズを満足するのに十分な個数のＵｓａｂｌｅｂｙｔｙｐｅを有するとすぐに、ブロック９１２はすべての冗長なスイッチを取り除く。
【００６１】
図１１は、図９Ａおよび図９Ｂならびに図１０のルータごとのフィルタプロセスの完了後のＯＶＥＲＬＡＹツリーを示している。
冗長なスイッチの単純な削除を介して、または、タイプごとのニーズを満たすスイッチを組み合わせて、その組み合わせに含まれないタイプに関連付けられたＭＯＮＯＣＨＲＯＭＥスイッチを削除することを介して、多くのスイッチがルータから削除されていることに留意されたい。
例えば、ルータ２０２４の下では、スイッチ８１００が完全に削除されている。
その理由は、スイッチ８１００が提供できるもの（すなわち、１つのＶＰＮゲートウェイ）以上のすべてを、スイッチ８１０１がすでに提供できるからである。
スイッチ８１０１はさらに別のＮＡＳも提供できるので、スイッチ８１００よりも好ましく、かつ残される。
別の例として、ＭＯＮＯＣＨＲＯＭＥスイッチ８００５および８００６が削除されている。
その理由は、ＬＰ２０００Ｒサーバが、スイッチ８００４'の下に論理的に統合可能であるからである。
この時点で、いくつかの冗長なルータが存在することに留意されたい（例えば、ルータ２０１１、２０１２および２０１３のそれぞれは、必要とされる２つのＡ５００サーバを提供でき、ＯＶＥＲＬＡＹツリーには、これら３つのルータすべてに対するニーズは存在しない）。
冗長なルータを取り除くことは、本明細書の図１２Ａおよび図１２Ｂのハブごとのフィルタプロセスで着手されることになる。
【００６２】
図１２Ａおよび図１２Ｂは、本発明の一実施の形態による、図４のブロック３０８のハブごとのフィルタプロセスを示している。
一般的に言うと、図１２Ａおよび図１２Ｂは、ハブの下の１つまたは２つ以上のルータを除去すること（図１２Ａ）、または特定のデバイスタイプのニーズを満たすハブの下のルータを組み合わせること（図１２Ｂ）のいずれかを目的とする。
図１２Ａでは、ブロック１１０２において、処理すべきルータがＯＶＥＲＬＡＹツリーにさらに存在するかどうかが確認される。
処理すべきルータがさらに存在する場合には、本方法はブロック１１０４に進み、１つずつルータの処理を開始する。
したがって、ブロック１１０４では、ハブの子供であるルータの処理を開始するために、一時変数Ｒが次のルータとなるように設定される。
また、リストＺが、ハブのそれ以外の残っているすべてのルータに等しくなるように設定される。
さらに、ルータＲのすべての子供が、直接接続されたデバイスおよびＭＯＮＯＣＨＲＯＭＥスイッチだけである場合には、フラグＳＩＭＰＬＥ（Ｒ）（シンプル）が、ルータＲ用のＳＩＭＰＬＥ配列内に設定される。
例えば、図１１を参照して、スイッチ８１０１はＭＯＮＯＣＨＲＯＭＥスイッチではないので、ルータ２０２４はそのＳＩＭＰＬＥフラグを設定されない。
しかし、ハブ１１０１の下のそれ以外のルータは全て、それらのそれぞれのＳＩＭＰＬＥフラグを設定される資格を有する。
ルータのＳＩＭＰＬＥフラグは、後の図１２Ｂとの関連で使用される。
【００６３】
ブロック１１０６では、リストＺに、処理すべきルータがさらに存在するかどうかが確認される。
処理すべきルータがリストＺにさらに存在する場合には、本方法はブロック１１０８に進む。
ブロック１１０８では、一時変数Ｙが、リストＺの次のルータに設定される。
ステップ１１１０では、ルータＲまたはルータＹが、それぞれが有するすべてのデバイスタイプに対するすべてのニーズを満足できるかどうかが確認される。
いずれも満足できない場合には、ルータＹを安全に削除できないので、本方法はブロック１１０６に戻り、リストＺの次のルータを処理する。
他方、ルータＲまたはルータＹのいずれかが、それぞれが有するすべてのデバイスタイプに対するすべてのニーズを満足できる場合には、本方法はブロック１１１２に進み、ルータＹが削除可能かどうかを確認する。
【００６４】
ブロック１１１２では、以下の２つの条件の双方が満たされる場合に、ルータＹが、ＯＶＥＲＬＡＹツリーからの削除候補として確認される。
第１の条件は、ルータＲにおけるファームの構築に自由に利用可能なデバイスの個数が、ルータＹにおけるファームの構築に自由に利用可能なデバイスの個数以上であることが満たされることである。
第２の条件は、ルータＲが、ルータＹのあらゆるデバイスおよびスイッチング素子の複製を含むことが満たされることである。
双方の条件が満たされると、プロセスはブロック１１１２からブロック１１１４に進み、ブロック１１４において、ルータＹはＯＶＥＲＬＡＹネットワークから除去される。
その後、プロセスはブロック１１０６に戻り、リストＺの次のルータを処理する。
他方、２つの条件の双方が満たされない場合には、プロセスは、ルータＹを削除することなしにブロック１１１２からブロック１１０６に戻り、リストＺの次のルータを処理する。
【００６５】
リストＺのすべてのルータが処理されると、本方法はブロック１１０２に戻り、ハブの下の次のルータを処理する。
ハブの下のすべてのルータが処理されるとすぐに、本方法は図１２Ｂに進む。
図１２Ｂでは、不要なＳＩＭＰＬＥルータが取り除かれ、ＯＶＥＲＬＡＹツリーの冗長性が削減される。
【００６６】
したがって、図１１の例示的なＯＶＥＲＬＡＹツリーを参照すると、ブロック１１１０および１１１２の検査は満たされるので、ルータ２０１１によって、ルータ２０１２および２０１３がＯＶＥＲＬＡＹツリーから除去される。
さらに、ルータ２０２１により、ルータ２０２２および２０２３がＯＶＥＲＬＡＹツリーから削除される。
さらにまた、ルータ２０２１は、ルータ２０２２および２０２３との先の比較において勝ち残ったルータではあるが、ルータ２０２４によってＯＶＥＲＬＡＹツリーから削除される。
最後に、ルータ２０１１およびルータ２０２４のみが残る。
この結果は、フィルタリングされたツリートポロジーネットワークを表す図１３に示されている。
【００６７】
図１２Ｂは、本発明の一実施の形態による、不要なＳＩＭＰＬＥルータが取り除かれ、ＯＶＥＲＬＡＹツリーの冗長性が削減される、ハブごとのフィルタプロセスを示している。
図１２Ｂは、例えば、図１２Ａのハブごとのフィルタプロセス後に、ＯＶＥＲＬＡＹツリーが依然として５つのルータ有し、それらのルータのそれぞれが１つのＡ５００サーバを有する場合に、起動することができる。
この選択された例の状況に限らず、このような状況は、いくつかのツリートポロジーネットワークには非常によく存在する。
Ａ５００サーバに対するファームのニーズは２つであり、この特定の例の単一ルータは２つのＡ５００サーバを供給できないので、これら冗長なルータを削除する必要がある。
【００６８】
ブロック１１５０は、図１２Ｂで行われるプロセスがＳＩＭＰＬＥルータを取り除くことを含むものであることを示すラベルブロックまたはコメントブロックである。
ルータの子供のすべてが、直接接続されたデバイスおよびＭＯＮＯＣＨＲＯＭＥスイッチのみである場合（例えば、非ＭＯＮＯＣＨＲＯＭＥのスイッチの子供を持たない場合）、そのルータは、図１２Ａのブロック１１０４でＳＩＭＰＬＥとみなされることが想起されるべきである。
ブロック１１５２では、図１２Ａのフィルタリングプロセスが完了した後のＯＶＥＲＬＡＹツリーに、任意のＳＩＭＰＬＥルータが残っているかどうかが確認される。
本実施の形態では、ＳＩＭＰＬＥルータのみが取り除かれるので、ＳＩＭＰＬＥルータが存在しない場合には、図１２Ｂのプロセスは終了する。
【００６９】
ブロック１１５２において、取り除かれる可能性のあるＳＩＭＰＬＥルータが残っていることが確認されると、設定されたＬＯＳＥＲがヌルに初期化され、一時リスト変数Ｗが、ハブの下に依然として存在するすべてのルータになるように設定される。
さらに、ブロック１１５４では、解に到達するのに必要とされるあらゆるルータ（１つまたは複数のルータ）が、フラグＶＩＴＡＬ（不可欠）によってマーク付けされる。
例えば、ルータ２０２４は、ＮＡＳおよびバックホールにとって必要とされるので、ＶＩＴＡＬとしてフラグを付けられる。
【００７０】
その後、リストＷのルータは１つずつ処理される。
ブロック１１５６では、ブロック１１５８および１１６０の論理を使用して、処理される別のルータがリストＷに存在するかどうかが確認される。
ブロック１１５６において、処理される別のルータが存在すると確認されると、本方法はブロック１１５８に進み、ブロック１１５８において、一時変数ＲがリストＷの次のルータとなるように設定される。
ブロック１１６０では、ルータＲはチェックされて、ＳＩＭＰＬＥであり、かつＶＩＴＡＬでないかどうかが確認される。
ルータＲがＳＩＭＰＬＥであり、かつＶＩＴＡＬでないことの双方が確認されない（すなわち、ブロック１１６０の検査が失敗に終わる）と、本方法はブロック１１５６に戻り、リストＷの次のルータを処理する。
【００７１】
他方、ルータＲがＳＩＭＰＬＥであり、かつＶＩＴＡＬでないと確認されると、本方法はブロック１１６２に進む。
ブロック１１６２では、パラメータＬＯＳＳＥＲ（Ｒ）（ルーザ）が、ＷＯＲＳＴＣＡＳＥよりも大きな帯域幅と、ルータＲよりも多くのデバイスとの双方を有する、リストＷのそれ以外のすべてのルータのカウントとなるように設定される。
変数ＬＯＳＥＲは、現段階で、ＬＯＳＳＥＳにとって最も大きな値を有するルータに等しくなるように設定される。
本質的には、リストＷのルータが順に処理されるので、ブロック１１６０および１１６２は、最小の値を有するルータを確認し、そのルータを、後に除去されるＬＯＳＥＲとして提供し、かつマーク付けする。
その後、本方法はブロック１１５６に戻り、リストＷの他のルータを処理する。
【００７２】
リストＷのすべてのルータが、ブロック１１５８、１１６０および／または１１６２によって処理されると、本方法は、ブロック１１５６からブロック１１６６に進み、ＬＯＳＥＲが確かに存在するかどうかを確認する。
ルーザ（loser）が存在しない（すなわち、ＬＯＳＥＲ＝ヌル）場合には、ルータを削除できず、したがって、プロセスはブロック１１６４で終了する。
他方、ブロック１５６６が、確かにＬＯＳＥＲが存在すると判断すると、ＬＯＳＥＲによって表されたルータは、ブロック１１６８でＯＶＥＲＬＡＹツリーから除去される。
その後、本方法はブロック１１５２に戻り、ＯＶＥＲＬＡＹツリーを再び繰り返し処理して、かつさらに取り除くことが可能かどうかを判断する。
【００７３】
一旦すべてのＳＩＭＰＬＥルータが処理されると、本方法はブロック１１６４で終了する。
本実施例の状況では、図１２Ｂのプロセスの結果、２つのルータが残り、各ルータは１つのＡ５００サーバを有する。
１つのＡ５００サーバを有するそれ以外の３つのルータは、それぞれ、必要とされる１７個のデバイスおよび４つのスイッチのみを残して取り除かれる。
【００７４】
前記内容から十分に理解できるように、本発明は、元のツリートポロジーネットワークを効率的にフィルタリングして、フィルタリングされたツリートポロジーネットワーク（ＦＴＴＮ）を取得する。
このＦＴＴＮは、依然としてオプションの解、または少なくともフィルタリングされていないツリートポロジーネットワークから取得可能なベストの解に実質的に等しい解を含んでいる。
しかしながら、その結果のＯＶＥＲＬＡＹイメージのルータ、スイッチおよびデバイスは、はるかに少なくなっている。
多くの場合、フィルタリングされたツリートポロジーネットワークは、それ自体が解であるので（本明細書の図１３の場合のように）、それ以上の処理は必要とされない。
【００７５】
一実施の形態では、本明細書に開示されたニーズベースフィルタリング技法は、同一出願人による同時係属中の「SYSTEMS AND METHODS FOR RAPID SELECTION OF DEVICES IN A TREE TOPOLOLGY NETWORK」という発明の名称の特許出願に開示された選択デバイス用の独創的技法と共に使用される。
この特許出願は、本明細書の発明者によって同日付で出願され、かつ参照により本明細書に援用される。
このような組み合わせによって、大量の時間を要することもなく、また、過度な計算リソースを要することもなく、所与のツリートポロジーネットワークから効率性の高いファームを選択することが可能になる。
また、上記同時係属中の特許出願に開示されたデバイス選択技法を利用しない場合であっても、本出願に開示されたニーズベースフィルタリング技法は、評価すべきルータ、スイッチおよびデバイスが少なくなるので、任意のデバイス選択技法をより効率的なものにもする。
これは、デバイス選択方法が、通常、考慮中のデバイスの個数の２乗または３乗に比例して変化する計算を必要とするからである。
したがって、任意のデバイス選択方法が適用される前に、考慮中のデバイスの個数が、本ニーズベースフィルタリング方法を使用して１０分の１に削減できると、デバイス選択アルゴリズムに必要とされる計算は、１００分の１から１０００分の１に削減できる。
【００７６】
本発明を、いくつかの好ましい実施の形態の観点から説明してきたが、本発明の範囲内に入る変更形態、置換形態および均等物が存在する。
また、本発明の方法および装置を実施する多くの代替的な方法が存在することにも留意すべきである。
したがって、特許請求の範囲は、本発明の真の精神および範囲内に入るようなすべての変更形態、置換形態および均等物を含むものとして解釈されることが意図される。
【図面の簡単な説明】
【００７７】
【図１】異なるタイプのネットワーク接続されたデバイスおよびスイッチング素子からなる大規模共通プールであって、当該大規模共通プールからさまざまなファームを構築できる大規模共通プールを表す例示的なデータセンターを示す。
【図２Ａ】ファームの例示的な論理仕様を示す。
【図２Ｂ】ファームの例示的な通信モデルを示す。
【図３】本発明にかかるアルゴリズムを、ソフトウェアにより実現するコンピュータを示す。
【図４】本発明の一実施の形態による、ニーズベースのフィルタリングアルゴリズムを示す。
【図５】デバイスごとのフィルタプロセスの一実施の形態をさらに詳細に説明する図である。
【図６】図５のフィルタリングプロセスが図１のツリーネットワークに対して完了した後の例示的なＯＶＥＲＬＡＹツリーを示す。
【図７】本発明の一実施の形態による、スイッチング素子ごとのフィルタリングプロセスを示す。
【図８】図７のスイッチング素子ごとのフィルタプロセスの完了後の例示的なＯＶＥＲＬＡＹツリーを示す。
【図９Ａ】本発明の一実施の形態による、ルータごとのフィルタプロセスを示す。
【図９Ｂ】本発明の一実施の形態による、ルータごとのフィルタプロセスを示す。
【図１０】本発明の一実施の形態による、図９Ｂによって呼び出されるＣＯＭＢＩＮＥプロセスを示す。
【図１１】図９Ａ、図９Ｂおよび図１０のルータごとのフィルタプロセスの完了後の例示的なＯＶＥＲＬＡＹツリーを示す。
【図１２Ａ】本発明の一実施の形態による、ハブごとのフィルタプロセスを示す。
【図１２Ｂ】本発明の一実施の形態による、ハブごとのフィルタプロセスを示す。
【図１３】図１２Ａおよび図１２Ｂのハブごとのフィルタプロセスの完了後の例示的なＯＶＥＲＬＡＹツリーを示す。
【符号の説明】
【００７８】
１００・・・データセンター
【図１】
2004208296.tif 000003
【図２Ａ】
2004208296.tif 000004
【図２Ｂ】
2004208296.tif 000005
【図３】
2004208296.tif 000006
【図４】
2004208296.tif 000007
【図５】
2004208296.tif 000008
【図６】
2004208296.tif 000009
【図７】
2004208296.tif 000010
【図８】
2004208296.tif 000011
【図９Ａ】
2004208296.tif 000012
【図９Ｂ】
2004208296.tif 000013
【図１０】
2004208296.tif 000014
【図１１】
2004208296.tif 000015
【図１２Ａ】
2004208296.tif 000016
【図１２Ｂ】
2004208296.tif 000017
【図１３】
2004208296.tif 000018