(57)【要約】【課題】本発明は、ランダム化された負荷バランシングを使用して、トラヒックをルーティングするための方法および装置を提供することを目的とする。【解決手段】本発明の１つの態様によれば、本発明は、動的に変化するトラヒック条件下においてコミュニケーション・ネットワーク上でコスト効率的にトラヒックをルーティングするための方法であって、各々のノードが、ランダム化された負荷バランシングを実行するように動作可能なルーティング・ハブをさらに含む、複数の中間ノードにトラヒックをルーティングする工程であって、前記トラヒックのルーティングが、前記ネットワークリリースのほぼ最適化された使用を達成する工程を含む、方法である。【選択図】図１Ａ
2006270967.tif 000002
【特許請求の範囲】
【請求項１】
最も安価なマルチ・ハブ構造に関連する１つまたは複数のノードを特定する工程を含む、ランダム化された負荷バランシングのために、ネットワークの１つまたは複数のノードを特定する方法。
【請求項２】
前記特定されるノードは、前記ネットワークの中心附近で相互にクラスター化されている、請求項１に記載の方法。
【請求項３】
前記特定されるノードは、中間ルーティング・ノードを含む、請求項１に記載の方法。
【請求項４】
最小の数の前記特定されるノードで、ランダム化された負荷バランシングを実施する工程をさらに含む、請求項１に記載の方法。
【請求項５】
最も遅延拡散が少ないマルチ・ハブ構造に関連する１つまたは複数のノードを特定する工程を含む、ランダム化された負荷バランシングのために、ネットワークの１つまたは複数のノードを特定する方法。
【請求項６】
動的に変化するトラヒック条件下においてコミュニケーション・ネットワーク上でコスト効率的にトラヒックをルーティングするための方法であって、
各々のノードが、ランダム化された負荷バランシングを実行するように動作可能なルーティング・ハブをさらに含む、複数の中間ノードにトラヒックをルーティングする工程であって、前記トラヒックのルーティングが、前記ネットワークリリースのほぼ最適化された使用を達成する工程を含む、方法。
【請求項７】
最も安価なマルチ・ハブ構造に関連する１つまたは複数のノードを特定するように動作可能な、ランダム化された負荷バランシングのために、ネットワークの１つまたは複数のノードを特定するための装置。
【請求項８】
前記特定されるノードは、前記ネットワークの中心附近で相互にクラスター化されている、請求項７に記載の装置。
【請求項９】
前記特定されるノードは、中間ルーティング・ノードを含む、請求項７に記載の装置。
【請求項１０】
最も遅延拡散が少ないマルチ・ハブ構造に関連する、１つまたは複数のノードを特定するように動作可能な、ランダム化された負荷バランシングのために、ネットワークの１つまたは複数のノードを特定するための装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ランダム化された負荷バランシングを使用してトラヒックをルーティングする方法及び装置に関する。
【背景技術】
【０００２】
本出願は、「選択的なランダム化された負荷調整および要求の変更を伴うメッシュ・ネットワーク」と題された、その開示全体がここでの参照により本明細書に組み込まれる、米国特許仮出願６０／６６４，１８９号に関連する。
【０００３】
新興のデータ・コミュニケーション・サービスは、キャリア・ネットワーク全体にわたるトラヒックの分配に、不確定性とダイナミズムを次第に生じさせている。そのようなサービスの２つの例は、バーチャル・プライベート・ネットワーク（ＶＰＮ）と、リモート・ストレージ・コンピューティング・アプリケーションである。ネットワーク・デザインの目的のために、そのようなサービスはホース・モデル（ｈｏｓｅ  ｍｏｄｅｌ）により最もよくモデル化され、それはノードの入口／出口のキャパシティを既知の定数として扱うが、ポイントツーポイントの要求を特定することはない。例えば、キャリア・ネットワークを経由して、いくつかのビジネス・サイトを相互に連結しようとする、ＶＰＮの顧客に対するサービス・レベル・アグリーメント（ＳＬＡ）は、各々の出口ノードでピークのレートを特定するが、各々のノード同士のペアにどのようにトラヒックが分配されるかという問題は残されたままである。即ち、そのネットワーク全体にわたって、トラヒックをどのように最も効率的にルーティングするかを決定するのはキャリア次第である。
【特許文献１】米国特許仮出願６０／６６４，１８９号
【発明の開示】
【発明が解決しようとする課題】
【０００４】
現存するキャリア・ネットワークは、しばしば回線交換コア技術（例えば、「ＩＰ−ｏｖｅｒ−ＳＯＮＥＴ」）上に構築されており、それは高い信頼性と高速度の保護スキームを提供する。しかしながら、トラヒックの要求が変化すると、これらの技術を用いて構築されたネットワークは、バンド幅が非効率的になる。これは、ネットワーク資源の深刻な利用不足につながることがある。日中の要求の変動などの適度なトラヒックの動態は、現存するコントロール・プレーン技術（例えば、ａｕｔｏｍａｔｉｃａｌｌｙ  ｓｗｉｔｃｈｅｄ  ｏｐｔｉｃａｌ  ｎｅｔｗｏｒｋ即ち「ＡＳＯＮ」）により取り扱われることが潜在的に可能であるが、急速に変化する要求パターンは取り扱われることができない。
【０００５】
対称的に、パケット交換バックボーン・ネットワーク（例えば、「ＩＰ−ｏｖｅｒ−ＳＯＮＥＴ」）は、ダイナミックなコントロール・プレーンの必要性なしで、ネットワーク資源のより良い利用を可能にする統計的多重化を用いている。しかしながら、純粋なパケット交換構造の使用により生じる顕著な欠点が存在する。
【０００６】
第１に、パケット交換ネットワークは、発信局から宛先局までの経路沿いの各々のノードを検査し、トラヒックをルーティングする。より大きいネットワークの場合、これは、パケット・ルータのスケーリングの難しさに起因するノードのスケーラビリティ問題と、パケット・ルータ・ポートが回線交換クロスコネクトの等価なポートよりも実質的により高価なことによるコストに関する問題との双方を発生する。
【０００７】
第２に、パケット・ベースのネットワークは、それらの性質から、各々のノードにおけるバッファリングを使用している。これは、パケット損失と遅延ジッターをもたらし、サービスの品質（ＱｏＳ）保証を達成することを困難にする。
【０００８】
第３に、パケット交換ネットワークは、回線交換ネットワークにより通常は適合されている信頼性と復旧の制約に適合しない。
【課題を解決するための手段】
【０００９】
本発明は、回線交換ネットワーク全体にわたってランダム化された負荷バランシングを適用する方法および装置を提供する。結果としてのネットワークは、ＳＯＮＥＴグレードの信頼性を提供するにもかかわらず、動的なトラヒックの変化用にデザインされた従来の構造よりも安価な配備コストを約束する。さらに、全てのパケットが単一の段階のルーティングのみしか経験しないので、遅延ジッターおよびＱｏＳ保証は、純粋なパケット交換構造よりも適合される傾向がある。
【００１０】
トラヒック要求パターンにおける急速な変化に充分適合するロバスト性（強靱性）を保ちながら、コスト効率的であるネットワークのデザインを決定するために、本発明の発明者らは、ランダム化された負荷バランシングに必要とされるネットワーク容量および展開コストを、ホースの制約（ｈｏｓｅ  ｃｏｎｓｔｒａｉｎｔ）に従う動的なトラヒック・パターンのためのその他のデータ・ネットワーク構造のネットワーク容量および展開コストと比較した。特に本発明の発明者らは、ランダム化された負荷バランシングを、ＩＰ−ｏｖｅｒ−ＷＤＭネットワークと同様に、従来のＩＰ−ｏｖｅｒ−ＳＯＮＥＴネットワークに対してベンチマークした。
【００１１】
簡潔化されたネットワークの運営のために、本発明の発明者らは、ルーティングが時間に先立って決定されることができる（いわゆる「オブリビアス・ルーティング（ｏｂｌｉｖｉｏｕｓ  ｒｏｕｔｉｎｇ）」という意味で静的であり、ルーティングされるトラヒック・パターンの変化からの、発信局から宛先局までの経路の独立性を維持するルーティングを要求した。特に本発明の発明者らは、最短経路ルーティング、ＶＰＮ−ツリー上のルーティング、およびハブ・ルーティングを研究した。
【００１２】
その結果として、本発明の発明者らは、ハブ・ルーティングをランダム化された負荷バランシングと組合せることが、それら２つのアプローチの利点を結合したオブリビアス・ルーティング戦略を生み出し、急速に変化するトラヒック要求条件の下で効率的に動作することができる、高度に魅力的なネットワーク構造に帰結することを認識した。
【発明を実施するための最良の形態】
【００１３】
オプチカル・ネットワーク全体にわたるＩＰトラヒックの搬送が望ましいことに動機付けされて、本発明の発明者らは、ネットワークが如何に不確定性または変化するトラヒック・パターンをサポートする（即ち、その下で効率的に動作する）かの問題を研究した。
【００１４】
この目的のために、あるネットワーク回線は、物理ネットワークにおける、２つのエンド・ノードと、いくつかの予め定められた専用の容量により定義されることができる。この容量は、回線の指定されたエンド・ノードの間で、影響されずにトラヒックを搬送するポイントツーポイントの「パイプ」として見なすことができる。全てのトラヒックは、そのような回線またはホップのシーケンスを追跡することにより、その目的地に到着する。ホップのシーケンスの特定の選択は、「トラヒックのルーティング」または「ルート」として言及される。トラヒックがいくつかのホップを追跡する場合には、ルーティング・ノードと呼称される中間に介在するノードは、その目的地に向かう次のホップ上に、トラヒックをルーティングすることができなければならない。例えばこれは、あるＩＰルータを使用して、ホップの間の各々のパケットを検査することにより、あるＩＰネットワーク内で実行されることができる。
【００１５】
ネットワーク内で用いられる、他の型式のトラヒック・フロー・マネジメントは、回線のプロビジョニングである。これは、物理ネットワーク内部で、個々の回線が如何にセットアップされるかに関係する。
【００１６】
ネットワークの構造（デザイン）は、ネットワーク内で如何に回線が実施されることができ、これらの回線が如何にエンド−ツー−エンド・ルーティングを実現するために用いられることができるかを決定するために用いられる制約の集成に基づいて決定される。
【００１７】
第１のクラスのホップの制約は、その３つの主要なカテゴリが、シングル−ホップ・ルーティング（ソース・ルーティング）、デュアル−ホップ・ルーティング（中間媒介ノードのルーティング）およびマルチ−ホップ・ルーティング（ホップ−バイ−ホップ・ルーティング）である複数の回線をトラヒックが横断することができる程度に制御する。第２のクラスの回線のプロビジョニングの制約は、物理ネットワーク内で回線が如何に実現されるかを決定する。一般的にある回線は、そのエンド・ポイントの間の「容量化された」経路（即ち、容量を割り当てられた経路）の存在により特定される。しかしながら、部分フロー（ｆｌａｃｔｉｏｎａｌ  ｆｌｏｗ）として実施された回線も同様に、回線として特定されることができる。これはしばしばマルチ−パス・ルーティングと呼称され、例えば、リンク容量調整スキームにより実施される。
第３のクラスは、回線を動的または静的にプロビジョニングする。
【００１８】
しかしながら１つの構造が与えられると、例えばスイッチング（ノード）装置の選択に依存して、あるネットワークをデザインする、いくつかの方法が依然として存在することがある。以下は、可能なネットワークの構造のいくつかの具体的な実現化である。
【００１９】
図１（ａ）は、シングル−ホップのネットワーク構造を示している。これはソース・ルート型であるので、この型式のネットワークにおけるトラヒックは、例えばＩＰルータである入口ルーティング・ノードによって予め定義された回線上に配置され、その目的地に向かってネットワークを横断する。静的な回線のプロビジョニングが用いられている場合には、ホースの制約を満足する全てのトラヒックの要求をサポートするために、各々のノード同士のペア（ｉ，ｊ）は容量（Ｄｉ，Ｄｊ）の回線により接続されていなければならない。ここで、Ｄｉはノードｉの入口／出口容量であり、Ｄｊはノードｊの入口／出口容量である。全ての回線が再構成なしに、ノードで生成された全てのトラヒックの要求を取り扱うことができるので、制御プレーンは必要とされない。即ち、トラヒック・パターンが変化することが可能である場合には、この構造はネットワーク資源の、巨大なオーバー・プロビジョニングに帰着する。これは、動的にプロビジョニングする回線により、軽減されることができる。そのようなプロビジョニングは、動的な制御プレーンの使用と、ネットワークの資源をトラヒックに共有させることが必要とされる場合に、回線を設定し解除することを含んでいる。しかしながらそのようなプロビジョニングが、高速度で変化するトラヒック条件を調整することが可能な度合いは、現在利用可能な制御プレーンの技術が中程度の速度であるので、制限されている。
【００２０】
図１（ｂ）は、各々のノードが回線上のノードに到来するトラヒックを検査し、局所的に実施されたルーティング戦略に従って、異なる回線上にトラヒックを配置する、マルチ−ホップ・ネットワーク構造を示している。この構造についての最もよく知られた例は、ノードがＩＰルータであり、回線はそれらの間のポイントツーポイント・ライン・システム（例えば、波長分割多重アクセスを使用した）である、ＩＰネットワークである。容量解析の観点からは、マルチ−ホップ・ネットワーク構造は、急速に変化するトラヒック要求の条件をサポートするための、充分に高速度の制御プレーンを使用するシングル−ホップ構造と等価である。マルチ−ホップ・ネットワークでは、グローバルに作用する制御プレーンを使用する代わりに、各々のノードにおけるローカルなルーティングを通して、統計的な多重化が用いられる。
【００２１】
図１（ｃ）および図１（ｄ）は、そのトラヒックの最終目的地とは無関係に、予め設定された回線を用いて、トラヒックがまず一組の中間に介在するルーティング・ノードに送られる、デュアル・ホップ・ネットワーク構造の２つの場合を示している。トラヒックの受信に際して、中間に介在するノードは局所的なルーティングの決定を実行し、その最終目的地にトラヒックを送信するために、回線交換コアを使用する。図１（ｃ）に示された、単一の中間に介在するルーティング・ノードのみを使用する、ネットワーク構造は、ハブ構造と呼称される。単一のハブを使用することは、しばしばネットワーク全体の最小コストに帰着するにもかかわらず、実際にはそれは最も望ましい構造ではない。なぜならば、（ｉ）ハブが、単一障害点を表わし、かつ（ｉｉ）直ちにネットワークのスケーラビリティの問題となることがある、ネットワーク全体のトラヒックの価値をルーティングしなければならないからである。図１（ｄ）に示されるネットワーク構造は、並列演算の状況で導入された、バリアントのランダム化された負荷の均衡戦略により触発されるようにルーティングするために、到来するトラヒックを複数の（および極端な場合には全ての）ノードにわたって最初に分配する。このスキームは、最近では高容量のインターネット・パケット・ルータのための構造として考えられ、バックボーン・ネットワークをデザインする効率的な方法として提案されている。
【００２２】
ネットワーク・デザイナーは、ポイントツーポイント・トラヒックの要求の正確な見積もりが、回線をレイアウトする前に作成されているべきであるとの観点を、従来は採用してきた。しかしながら、（ＶＰＮまたはリモート記憶／演算などの）フレキシブルなサービスの増大する使用と高まる重要性は、トラヒック・パターンが、事前によく知られていないかまたは急速に変化する状況に対してデザインされたネットワークにおいて、関心を高めてきた。これらの設定においては、ネットワークは、ただ１つのトラヒック・マトリックスではなく、特定のアプリケーションにより決定されるより大きなマトリックスのクラスをサポートするようにデザインされ、そのような大きさにされるべきである。
【００２３】
そのようなネットワークをデザインするために、ロバスト最適化問題は、要求マトリックスのユニバースＵ（普通は凸領域として特定される）を与えられられると、そのゴールは、可能な最小のコストで、Ｕにおける全ての要求マトリックスをサポートする、ネットワークをデザインすることである。最近ＮＰハード（非決定論的困難）であることが示された、この問題の最も単純な形式は、全ての要求をサポートするのに充分な部分リンク容量を割り当てることである。単に単一のトラヒック・パターンではなく要求マトリックスの全てのクラスをサポートできるようにするためには、より多くの出費が必要となる。この超過のコストは、「ロバスト・プレミアム」と呼称されることができる。本発明の一実施形態では、ロバスト・プレミアムをある程度制御するために、アルゴリズム技術が用いられることができる。
【００２４】
１つ（または多く）のトラヒック・マトリックスをサポートするに必要なネットワーク内部のノードのスイッチング装置と同様に、リンクの容量も、関係するネットワーク装置の機能性に依存することを留意されたい。なぜならば、代わりにこれが、トラヒックが如何にルーティングされるかを決定するからである。例えば、要求マトリックス（即ち、ルーティングされるべき分配されたトラヒック）のルーティングは、コスト効率的なルーティングの決定において、ネットワーク・トポロジーとネットワーク資源の現在の利用に関する情報をしばしば使用する。現在の目的のために、以下に続く議論は、ネットワークのトポロジーのみに依存し、ネットワークの利用パラメーターや現在のトラヒックの分配状況を使用しない、オブリビアス（しばしば静的と呼称される）・ルーティング戦略の使用を仮定している。この方法では、ルーティング経路は、トラヒック・パターンの変化には独立に、前もって、一度計算される。これは、安定的なネットワークの動作を簡潔化する。
【００２５】
ロバストなネットワークのデザインのために、効率的な要求オブリビアス・ルーティングの発見に注意を払ってきた現存する技術は、ホース・モデルから発生するマトリックスであるＵの選択に特に注意を払ってきた。これらは、あるノードに到来する（またはそれから出ていく）全ての要求が、その入口（または出口）容量に与えられた限度以下であるとの特性を有する。
【００２６】
本明細書で議論される本発明の実施形態では、等しい入口を有するホース・モデルが適用されると仮定している。従って各々のノードｉは、そのノードにおける最大の入口容量および最大の出口容量である、限度Ｄｉを有する。対称的な要求は、必ずしも必要とされない。この理由により、マトリックスの結果のクラスは、
Ｕ＝｛ｄｉｊ≧０：Σｊｄｉｊ≦Ｄｉ，Σｊｄｊｉ≦Ｄｉ，∀ｉ｝である。
【００２７】
ホースの制約を有する、（一方向性／双方向性の）ＶＰＮをサポートする、最適なツリーのサブ・ネットワークを選択する１つの方法は、以下の通りである。
【００２８】
固定されたツリーＴを与えられると、ＶＰＮトラヒックをサポートするために必要とされる容量が計算されることができる。各々のエッジｅ∈Ｔに対して、そのエッジｅを削除した後に得られる、２つのツリーを考察する。ｅの容量は、それら２つのツリーにおける全てのノードの総限界容量（即ち、総計の入口／出口容量）より、少なくとも小さくなければならない。これらの計算から得られるリンク容量化ツリーＴ＾は、Ｔに関連するＶＰＮ−ツリーとして言及される。ダイレクト・ルーティング・テンプレート（例えば、トラヒック要求が如何にルーティングされるかを特定する計画）が用いられる場合には、これらの容量は、全てのホース・トラヒック要求をルーティングするためには充分であり、ここで、あるノードのペアｉ、ｊの間の要求は、Ｔ内のそれらの間の唯一の経路に沿ってルーティングされる。
【００２９】
そのようなＴと固定ノードνに関連する、他の容量化ツリーＴ，ν￣も同様に考慮されることができる。即ち、ハブ・ルーティングがハブとして動作するνとともに実行されることができるように、Ｔ，ν￣は充分なエッジ容量を有している。これらの容量は、各々のノードｉが２Ｄｉのトラヒックをノードνにルーティングした後に得られるエッジ負荷を得ることにより得られることができる。Ｔがνにルーティングされる最短経路ツリーである場合でさえも、一般的にＴ，ν￣がＴ＾よりも多い容量を有することができることに留意されたい。
【００３０】
ある最適のＶＰＮ−ツリーが、いくつかのノードｒにルーティングされる最短経路ツリーＴｒとして生成されることは、すでに示されている。さらに、そのようなツリーに対して、Ｔｒ＾が正確にＴｒ，ｒ￣と同じであることも、以前に示されている。この１つの結論は、最適のＶＰＮ−ツリーが、各々のノードνから最短経路ツリーＴνを求めることおよび最も安価なものを得ることにより、形成されることができるということである。より重要な結論は、ダイレクト・ルーティング・テンプレートまたはハブ・ルーティング・テンプレートのどちらかを使用するのに充分な容量が、そのようなツリーの上に存在することである。各々のノードとハブの間の静的にプロビジョニングされた回線を使用して、ハブ・ルーティング・テンプレートが埋め込まれることができるので、これは意味のあることである。これは、デュアル−ホップ構造内部での、オーバー・プロビジョニングを防止する。
【００３１】
ランダム化された負荷バランシングは、静的にプロビジョニングされた回線交換コアに基づく２工程（デュアル−ホップ）ルーティング・スキームである。第１の（負荷バランシング）工程では、Ｎ個のノードのネットワークのいずれかのノードで生成されたトラヒックは、全てのＮ個のノード間で均一に分配される。（より少ない部分集合Ｍ≦Ｎのノード全体にわたる負荷バランシングは、後で議論される。）例えば、ノードの入口／出口の容量が等しい場合では、各々のノードは、互いのノードに、その１／Ｎのトラヒックを分配（かつそれ自身が１／Ｎを保持）する。この第１の工程におけるトラヒックの分配は、それが要求マトリックスを使用せず、入口でのルーティングの決定をなんら必要としないという意味で、ランダムである。第２の工程では各々のノードは、第１の工程の間に受領したトラヒックに対して、局所的なルーティングの決定を実行し、その最終目的地に導く回線上にトラヒックを統計的に多重化する。第１の工程におけるランダムかつ均一なトラヒックの分配に起因して、第２の工程におけるトラヒックの分配も平均的に均一であり、変動は、ルーティングするノード内部でのバッファリングにより収容される。
【００３２】
この２つの工程を実行するために必要とされるリンク容量は、以下のようにして解析される。ノードにおけるトラヒックの限界Ｄｉに対しては、各々の段階で分配されるトラヒックは、Ｄｉにより誘導される、いわゆるプロダクト多種フロー、即ち、ノードｉとｊの間のトラヒックは、ＤｉＤｊ／ΣｌＤｌである（ここで、Ｄｉは、ノードの容量の合計である）。このプロダクト多種フローは、それ自体がホースの制約に対する許容可能な要求マトリックスであることに留意されたい。従って、負荷バランシングに必要とされる総リンク容量は、全ての適法な要求マトリックスをサポートすることができる最適のものの多くとも２倍であることがわかる。
【００３３】
ランダム化された負荷バランシングの利点は、以下のように要約することができる。第１に、各々のノードｊが、Ｎ個のノード（それ自体を含む）全てから、全部でΣｉＤｉＤｊ／（ΣｌＤｌ＝Ｄｊ）を受領するので、第２の工程に対して必要とされるノード・ルーティング容量は、総ノード入口容量に等しい。これは、ソース・ルーティト型の回線交換構造に対して必要とされるルーティング容量に対応する。動的に変化する要求パターンの完全なサポートは、局所的なルーティングを通して維持され、グローバル制御プレーンは必要とされない。第２に、ランダム化された負荷バランシングは、厳密にデュアル・ホップ・ルーティングを実行する、即ち、全てのトラヒックは（例えば、第２の工程の始めに）一度だけバッファされる。各々のノードでトラヒックをバッファする、マルチ−ホップ・ネットワーク構造と比較した場合、これはランダム・バッファリング遅延を低減する。第３に、第１および第２の工程におけるトラヒックの均一な性質は、ルーティングされるべき実際の要求マトリックスとは無関係に、ネットワークのデザインを劇的に簡潔化する、静的なネットワーク回線の事前の割り当てを可能にする。
【００３４】
（マルチ−パス・ルーティング・テンプレートを使用する任意の他の構造と同様に）ランダム化された負荷バランシングの１つの欠点は、トラヒックが顕著な飛行時間差を有する経路をルーティングされ、パケットが再度オーダーされる潜在的な必要性が要求されることである。しかしながら、これらの飛行時間差は、ランダムな遅延ジッターには寄与せず、ルーティング・テンプレートの知識に基づいて完全に予知可能であり、従って、入口、中間点、または出口のノードにおける決定論的遅延により、影響を弱めることができることに留意されたい。同様に、ランダム化された負荷バランシングにおける最大伝搬遅延は、負荷バランシングされたネットワークの地理的な大きさを制限するルーティング・テンプレートにおける最長経路の飛行時間の約２倍である。
【００３５】
負荷バランシングの第２の欠点は、ハブ・ルーティングの主要な利点と同時に発生する。最適ハブ（ＶＰＮ−ツリー）を使用している場合に、ハブ・ルーティングに必要とされる全リンク／ノード容量が、負荷バランシングに対する全リンク／ノード容量よりも常に少ないことを確かめるために、これら２つのデュアル・ホップ構造を比較することは容易なことである。これを確かめるために、第１工程において、各々のｉから、各々のノードν∈［１；Ｎ］に対する最短経路ツリーＴνのルートへのルーティングＤｉのフローから発生する、Ｎ個の容量化されたツリーの１／Ｎの凸状の組合せとして、負荷バランシング中のトラヒック（第２工程のトラヒックと同様に）が記述されることができることに留意されたい。従って、負荷バランシングにより必要とされる総容量は、容量化されたツリーＴν，ν￣の、１／Ｎの凸状の組合せである。さらに、任意のＴν，ν￣上の容量が、Ｔν＾内のそれらと少なくとも同程度であるので、任意のＴν＾上の総容量は、少なくとも最適ＶＰＮ−ツリーと同程度である。従って、負荷バランシングの容量は、その各々の容量が少なくともある最適ＶＰＮ−ツリーと同程度である、ツリーの凸状の組合せである。
【００３６】
以下の節で議論されるように、２つのデュアル−ホップ構造の組合せが、以下のように考察されることができる。前で概説されたように、負荷バランシングは、「ハブ」がネットワーク全体にわたって分配される、ハブ・ルーティングとして略式に考察されることができる。実験による解析は、Ｍ＜Ｎ個のこれらのハブに関連する最短経路ツリーが、コストにおいて最適ＶＰＮ−ツリーにかなり近接することができることを示している。従って、Ｍ個のノードの部分集合全体の負荷バランシングは、その総リンク容量が最適ＶＰＮ−ツリーのそれに近接している一方で、ハブ・ルーティングが影響を受けやすいノードの不具合に対する回復力を依然としてもたらしている。ネットワークのコストの削減および不具合の軽減と拡張性に関わることから離れると、ネットワークのノードの最適部分集合全体のランダム化された負荷バランシングはまた、伝搬遅延および遅延の拡散を低減する。これは、従来のマルチ−ホップ構造の代替として、選択的なランダム化された負荷バランシングを非常に魅力的にする。
【００３７】
次に、図２の３つの例のネットワークを使用して導入される、当該の構造およびルーティング戦略に対する容量の要求が比較される。以下の議論では、対称的な要求（ｄｉｊ＝ｄｊｉ）および等しいノード入口／出口トラヒック（Σｉｄｉｊ＝Ｄ／Ｎ）が、仮定されている。要求パターンはホースの制約の下で変化することが許されており、全ての構造がブロックすることなく全ての法的に許可される要求マトリックスを収容するように容量化されている。
【００３８】
第１に、全てのネットワーク構造が、Ｎ個のネットワーク・ノード全てにわたってランダム化された負荷バランシングと比較される、即ち、全てのトラヒックがネットワーク全体にわたって分配され、全てのノードが総ネットワーク・トラヒックの１／Ｎに対する、局所的なルーティング・ハブとして動作する。その結果は、表１〜表３に要約されている。これらの表は、ＶＰＮ−ツリー・ルーティングと同様に、異なるネットワーク構造および最短パス（ＳＰ）に対する、総必要回線交換容量（例えば、ＳＯＮＥＴクロスコネクト）、総パケット交換容量（例えば、ＩＰルータ）、およびトランスポート容量（例えば、ＷＤＭライン・システム）をリストしている。最も右の列は、最適ＶＰＮ−ツリーを使用して、ハブ構造に対して正規化された、ネットワーク全体のコストを示す。ネットワークの全体コストに到達するために、商業的に入手可能なネットワークのハードウェアに対して、以下のコスト・モデルが仮定されている。
ＣＩＰ−ｐｏｒｔ：Ｃｓｏｎｅｔ−ｐｏｒｔ：ＣＷＤＭ／ｋｍ＝３７０：１３０：１
ここで、ＣＩＰ−ｐｏｒｔは、ＩＰルータ・ポートのコスト、Ｃｓｏｎｅｔ−ｐｏｒｔは、ＳＯＮＥＴクロスコネクト・ポートのコスト、ＣＷＤＭ／ｋｍは、全て同じデータ・レートに対するリンク距離の１ｋｍ当たりのＷＤＭトランスポートのコストである。全ての容量の数字はコストの数字と同様に表示されているので、関心のある読者がこれらの結果に、適切な他の任意のコスト比を挿入することが可能である。
【表１】
2006270967.tif 000003
【表２】
2006270967.tif 000004
【表３】
2006270967.tif 000005
【００３９】
ランダム化された負荷バランシングされる構造に対しては、ＳＯＮＥＴクロスコネクト・ハンドリング・ノードの入口／出口トラヒック上の、それらのライン・カードが、パケット（またはフロー）を分離および再シーケンス化するための手段を備えていることがさらに仮定されている。標準的な回線交換ライン・カードのコストの半分の追加コストが、この機能に割り当てられている。従って、負荷バランシングされる構造における入口／出口ライン・カードのポート当たりのコストは、１．５ＣＳＯＮＥＴ−ｐｏｒｔに等しくなる。
【００４０】
動的制御プレーン構造を有する回線交換ネットワーク構造の場合、高度に動的な制御プレーンがまだ存在せず、それらのコストの意味のある数量化が与えられることができないので、追加のコストは割り当てられていない。
表１〜表３から明らかであるように、高いオーバー・プロビジョニングに対する必要性を有する、静的なシングル−ホップ構造は、過度に高価なネットワーク・コストに帰着する。その利用可能性がないために、動的な制御プレーン構造を無視すると、動的なネットワーク化への最も重要な候補は、下記のように特定される。
・ＶＰＮ−ツリー・ルーティングを用いるマルチ−ホップ構造
・最短経路ルーティングを用いる負荷バランシングされる構造
・ＶＰＮ−ツリー・ルーティングを用いるハブ構造
これら３つの構造では、ハブ構造（最適ネットワーク・ノードをルーティング・ハブとして用いる）が、ＶＰＮ−ツリー・ルーティング戦略に合致する全てのネットワークにおいて、最も安価なことがわかる。しかしながら、全てのトラヒックは、全体のネットワーク・トラヒックＤを取り扱うことができなければならない、単一のルーティング・ノード内で処理される。従って、この構造は単一障害点を内在しており、そのためにしばしば信頼できないと考えられている。
【００４１】
ネットワークのサイズに応じて、ランダム化された負荷バランシングが、全てのネットワーク・ノード（ＪＡＮＥＴ）にわたり地理的なサイズがより小さいネットワークに対して最も安価であるように思われる一方で、マルチ−ホップＶＰＮ−ツリー・ルーティングは、より大きいネットワーク（ＡＢＩＬＥＮＥおよびＧＥＡＮＴ）上でより良く動作する。ランダム化された負荷バランシングは（一般的に）ＶＰＮ−ツリーをベースとする構造を上回るトランスポート容量を使用し、従ってそのために、ルーティングのコストがトランスポートのコストを支配する場合にのみ証明することができるので、これは前の議論から（例えば、表２から）予想されることである。実際に、ＡＢＩＬＥＮＥトポロジーがその平均リンク距離１３１７ｋｍから８３１ｋｍにスケール・ダウンされ、またＧＥＡＮＴトポロジーがその平均リンク距離７９７ｋｍから３１９ｋｍにスケール・ダウンされたならば、ランダム化される負荷バランシングはＶＰＮ−ツリー上のマルチ−ホップ・ルーティングと等しいコストを示す。比較として、ＪＡＮＥＴは１８４ｋｍの平均リンク距離を有し、ランダム化される負荷バランシングは、このトポロジー上では１０３０ｋｍの平均リンク距離まで、マルチ−ホップＩＰルーティングよりも優っている。
【００４２】
ネットワーク全体にわたる負荷バランシングは、より小さいネットワークにおいてのみ実証されることを理解したことにより、本発明者らは新しい技術が必要とされることを認識した。本発明の一実施形態では、そのような技術は、まず特定し、次いでＮ個のノードのネットワーク（例えば、大きいネットワーク）のうちＭ個のノードの部分集合全体にランダム化された負荷バランシングを実行する。ランダム化された負荷バランシングのための中間ルーティング・ノードとして動作することができる最適のＭ個のノードを特定するために、本発明者らは以上から、（ｉ）１≦Ｍ≦Ｎ個の中間ノードを使用する、ランダム化された負荷バランシングは、各々が全部のネットワークのトラヒックＤの１／Ｍを処理する、ハブがルート化されたＭ個のネットワークの凸状の組合せとして見なされることができ、また（ｉｉ）ハブがルート化されたネットワークのコストは、ルーティング・ハブとして動作するノードの選択に依存する。即ち、最適ハブの選択は、ＶＰＮ−ツリー・ルーティング戦略に帰着する。
【００４３】
図２の３つのネットワークの例の場合、選択されたハブに応じて、ハブ・ルーティングのコストは、ＪＡＮＥＴ、ＡＢＩＬＥＮＥ、およびＧＥＡＮＴについて、２２％、５７％、および９０％変化する。Ｍ個の最もコストが安価なハブ構造に帰着するＭ個の中間ノードに基づくランダム化された負荷バランシングの実施は、従って負荷バランシングされたネットワークのコストを、実質的に、ＶＰＮ−ツリー・ルーティングを使用するマルチ−ホップＩＰネットワークのコストよりも下に削減することができる。図３は、この戦略をビジュアル化している。この図は、ハブ・ルーティングに正規化され、Ｍ個の最も安価な中間ノードの関数として、かつトラヒック分離と再シーケンス化するハードウェアのコストを考慮した、負荷バランシングされたネットワークのコストを示している。この曲線を、表１〜表３からの、マルチ−ホップＶＰＮ−ツリー・ルーティングに対するコストの数字と比較すると、Ｍ≦８個の中間ノードが選択された場合、ＡＢＩＬＥＮＥネットワークでの負荷バランシングは、マルチ−ホップＶＰＮ−ツリー・ルーティングより良好に実行されることがわかる。ＧＥＡＮＴネットワークでは、マルチ−ホップＶＰＮ−ツリー・ルーティングに対して比較するために、Ｍ≦１３個の中間ノードが選択される必要がある。
【００４４】
驚くまでもなく、Ｍ個の最も安価なツリーに関連する全てのハブは、ネットワークのセンター近くで共にクラスター化されている。そのセンターは、ＶＰＮツリーの構造を直接反映して、当該のセンターに接続された全てのエッジ上に集合したトラヒックが、可能な最良のバランスとなっているとの概念により特徴付けられている。全ての最も安価なノードが共にクラスター化されているので、ルーティング・ハブとしてこれらのノードのいずれかを使用する、任意の要求についてのトランスポート距離の間の差異は、最少である。これは、ランダム化された負荷バランシングの最も厳しい欠点の１つ、異なる中間ノードに分配されたパケットの異なる遅延（遅延拡散）およびその結果としてのパケットの再シーケンス化の必要性という欠点を軽減する。１つの例として、ＪＡＮＥＴネットワーク上の最悪の遅延の拡散は、ネットワーク全体にわたる負荷バランシングの代わりに、５つの中間ノードのみを使用することにより半減される。ＡＢＩＬＥＮＥネットワークでは、６個のルーティング・ノードを使用する場合に、ＧＥＡＮＴネットワークでは１６個のノードを使用した場合に同じ削減が得られる。その場合、最も安価なマルチ・ハブ構造を、最も低い遅延の拡散（例えば、１つのルーティング経路と他のルーティング経路との間の遅延における差異）を有する構造と類推することができる結果となる。本発明の一代替実施形態では、ランダム化された負荷バランシングを実行するために、最も低い遅延の拡散に関連する１つまたは複数のノードが特定され、用いられることができる。
【００４５】
以上の議論は、本発明を実行するための方法に焦点を当ててきたが、これらの方法が１つまたは複数の装置によって実行されることできることを認識されるべきである。例えば、ネットワーク計画ツールまたはソフトウェア・アプリケーションを使用するようにプログラムされたネットワーク装置またはコンピューターが、ランダム化された負荷バランシングを実行するために用いられることができるこれらのノードを特定するために用いられてもよい。
【００４６】
以上の議論は、本発明のいくつかの例を説明するために試みられてきた。しかしながら、本発明の真実の範囲は、添付の特許請求の範囲により与えられることが理解されるべきである。
【図面の簡単な説明】
【００４７】
【図１Ａ】ネットワーク構造を示す図である。
【図１Ｂ】ネットワーク構造を示す図である。
【図１Ｃ】ネットワーク構造を示す図である。
【図１Ｄ】ネットワーク構造を示す図である。
【図２Ａ】本発明のアプリケーションで言及されるネットワークの例を示す図である。
【図２Ｂ】本発明のアプリケーションで言及されるネットワークの例を示す図である。
【図２Ｃ】本発明のアプリケーションで言及されるネットワークの例を示す図である。
【図３】コスト比対中間ルーティング・ノード数を示すグラフである。
【図１Ａ】
2006270967.tif 000006
【図１Ｂ】
2006270967.tif 000007
【図１Ｃ】
2006270967.tif 000008
【図１Ｄ】
2006270967.tif 000009
【図２Ａ】
2006270967.tif 000010
【図２Ｂ】
2006270967.tif 000011
【図２Ｃ】
2006270967.tif 000012
【図３】
2006270967.tif 000013