(57)【特許請求の範囲】
【請求項１】
複数のネットワークノードを有するソフトウェア・デファインド・ネットワーク(SDN)のためのネットワークのゾーニングの方法であって、
少なくとも1つのゾーン量パラメータに従ってゾーンの数Kを決定するステップと、
ヒューリスティックなアルゴリズムに従って前記SDNの前記複数のネットワークノードをK個のゾーンにパーティショニングするステップと、
前記K個のゾーンにK個のSDNコントローラをそれぞれ割り当てるステップであって、前記K個のコントローラの各々が、トラフィックエンジニアリングの判断を行い、それぞれのゾーンにパーティショニングされたネットワークノードのための分散型ネットワーク最適化を実行するように構成される、ステップと
を含む方法。
【請求項２】
K個のSDNコントローラの第1のグループを選択するステップをさらに含む、請求項1に記載の方法。
【請求項３】
選択する前記ステップが、それぞれ割り当てる前記ステップと同時に実行される、請求項2に記載の方法。
【請求項４】
選択する前記ステップが、パーティショニングする前記ステップよりも前、かつ、それぞれ割り当てる前記ステップよりも前に実行される、請求項2または3に記載の方法。
【請求項５】
それぞれ割り当てる前記ステップと同時にK個のSDNコントローラの第2のグループを再選択して、K個のSDNコントローラの前記第1のグループを置き換えるステップをさらに含む、請求項2から4のいずれか一項に記載の方法。
【請求項６】
選択する前記ステップが、複数の候補SDNコントローラに対するそれぞれのコントローラ間の距離に従って、前記複数の候補SDNコントローラからK個のSDNコントローラの前記第1のグループを選択するステップを含み、
選択する前記ステップが、K個のSDNコントローラの前記第1のグループに対して前記それぞれのコントローラ間の距離を最大化するステップをさらに含む、請求項2から4のいずれか一項に記載の方法。
【請求項７】
前記それぞれのコントローラ間の距離が、ホップ数を含む、請求項6に記載の方法。
【請求項８】
前記それぞれのコントローラ間の距離が、重み付けされる、請求項6に記載の方法。
【請求項９】
前記少なくとも1つのゾーン量パラメータが、トラフィックエンジニアリング(TE)の複雑さ、ネットワークサイズ、トラフィック負荷、およびトラフィックフロー情報のうちの少なくとも1つを含む、請求項1から8のいずれか一項に記載の方法。
【請求項１０】
パーティショニングする前記ステップが、前記ヒューリスティックなアルゴリズムに従って前記SDNを地理的ゾーンに分割するステップを含み、
前記ヒューリスティックなアルゴリズムは、物理的トポロジー情報を使用して、前記地理的ゾーンを形成する、請求項1から9のいずれか一項に記載の方法。
【請求項１１】
パーティショニングする前記ステップが、クラスタリングのヒューリスティックなアルゴリズムに従って前記地理的ゾーンを形成するステップをさらに含む、請求項10に記載の方法。
【請求項１２】
パーティショニングする前記ステップが、パーティショニングのヒューリスティックなアルゴリズムに従って前記地理的ゾーンを形成するステップをさらに含む、請求項10に記載の方法。
【請求項１３】
パーティショニングする前記ステップが、タスク割り当てのヒューリスティックなアルゴリズムに従って前記地理的ゾーンを形成するステップをさらに含む、請求項10に記載の方法。
【請求項１４】
パーティショニングする前記ステップが、前記ヒューリスティックなアルゴリズムに従って前記SDNを論理的ゾーンに分割するステップを含み、
前記ヒューリスティックなアルゴリズムは、データフロー情報を使用して、前記論理的ゾーンを形成する、請求項1から9のいずれか一項に記載の方法。
【請求項１５】
パーティショニングする前記ステップが、タスク割り当てのヒューリスティックなアルゴリズムに従って前記論理的ゾーンを形成するステップをさらに含む、請求項14に記載の方法。
【請求項１６】
パーティショニングする前記ステップが、グラフパーティションのヒューリスティック
なアルゴリズムに従って前記論理的ゾーンを形成するステップをさらに含む、請求項14に記載の方法。
【請求項１７】
パーティショニングする前記ステップが、それぞれ割り当てる前記ステップよりも前に実行される、請求項1から9のいずれか一項に記載の方法。
【請求項１８】
パーティショニングする前記ステップが、それぞれ割り当てる前記ステップと同時に実行される、請求項1から9のいずれか一項に記載の方法。
【請求項１９】
複数のトラフィックフローがリンクを介して横断する、トラフィックエンジニアリング(TE)の問題が定義される複数のネットワークノードと、
ゾーンコントローラの部分集合を選択可能な複数のコントローラと、
ゾーニングコントローラと、
マスタコントローラと
を含み、
前記ゾーニングコントローラは、
ゾーンコントローラの前記部分集合のサイズを決定し、
ゾーンコントローラの前記部分集合を選択し、
前記複数のネットワークノードをゾーンにヒューリスティックにパーティショニングし、
ゾーンコントローラの前記部分集合を前記ゾーンにそれぞれ割り当てるように構成され、
前記マスタコントローラは、前記TEの問題を前記ゾーンに対応するTEの下位の問題に分解するように構成され、
ゾーンコントローラの前記部分集合は、前記ゾーンに対する前記TEの下位の問題をそれぞれ解くように構成される、通信システム。
【請求項２０】
ゾーンコントローラの前記部分集合が、前記TEの下位の問題のそれぞれの解に従って、前記複数のネットワークノードのためのネットワークリソースを提供するように構成される、請求項19に記載の通信システム。
【請求項２１】
前記マスタコントローラが、ゾーンコントローラの前記部分集合と通信して、前記TEの下位の問題の状態を調整するようにさらに構成される、請求項19または20に記載の通信システム。
【請求項２２】
制御プレーンによって複数のソフトウェア・デファインド・ネットワーク(SDN)コントローラおよび複数のネットワークノードに結合可能なネットワーク・インターフェース・コントローラ(NIC)であって、前記複数のネットワークノードが、データプレーンによってリンクを介してトラフィックフローにより横断可能であり、トラフィックエンジニアリング(TE)の問題が、前記複数のネットワークノード、前記トラフィックフロー、および前記リンクに対して定義可能である、NICと、
プロセッサと
を含み、
前記プロセッサは、
予測されるTEの複雑さ、前記複数のネットワークノードを含むネットワークのサイズ、および前記トラフィックフローを含むトラフィック負荷に従って、ゾーンコントローラの部分集合のサイズを決定し、
コントローラのトポロジー、ネットワークのトポロジー、および前記トラフィック負荷に従って、前記複数のSDNコントローラからゾーンコントローラの前記部分集合を選択し、
複数のネットワークノードをゾーンにパーティショニングし、
ゾーンコントローラの前記部分集合を前記ゾーンにそれぞれ割り当てるように構成され、
前記複数のネットワークノードをゾーンにパーティショニングすることが、ヒューリスティックなアルゴリズムを用いて実行される、ゾーニングコントローラ。
【請求項２３】
前記複数のネットワークノードをゾーンにパーティショニングすることが、前記TEの下位の問題を解決することに関連するオーバーヘッドのコストを最小化することを含む、請求項22に記載のゾーニングコントローラ。
【請求項２４】
前記複数のネットワークノードをゾーンにパーティショニングすることが、物理的トポロジー情報に従って地理的ゾーンを形成することを含む、請求項22に記載のゾーニングコントローラ。
【請求項２５】
前記複数のネットワークノードをゾーンにパーティショニングすることが、複数のトラフィックフローについての情報に従って論理的ゾーンを形成することを含む、請求項22に記載のゾーニングコントローラ。
【請求項２６】
ゾーンコントローラの前記部分集合が、前記ゾーンコントローラのそれぞれのゾーン内の前記複数のネットワークノードおよび前記リンクに対する状態を収集するように構成される、請求項22または25に記載のゾーニングコントローラ。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、Liらによる、2014年3月31日に出願された、「Creating Logical Zones for Hierarchical Traffic Engineering in Software Defined Networks」と題された米国仮出願第61/973,013号およびLiらによる、2014年1月10日に出願された、「System and Method for Zoning in a Software Defined Network」と題された米国仮出願第61/926,099号の利益を主張する、Liらによる、2014年10月31日に出願された、「System and Method for Zoning in Software Defined Networks」と題された米国特許出願第14/530,332号の優先権を主張するものであり、これらの米国出願は、参照により本明細書に組み込まれる。
【０００２】
本出願は、本出願の譲受人に譲渡された、2013年12月27日に出願された、「Traffic Behavior Driven Dynamic Zoning for Distributed Traffic Engineering in SDN」と題された、同時係属中の米国特許出願第14/142,344号と、本出願の譲受人に譲渡された、2013年12月26日に出願された、「Hierarchical Software-Defined Network Traffic Engineering Controller」と題された、同時係属中の米国特許出願第14/141,077号とに関するものであり、これらの米国出願は、参照により本明細書に組み込まれる。
【０００３】
本発明は、一般に、ソフトウェア・デファインド・ネットワーク(SDN)におけるゾーニングの手法に関し、特定の実施形態においては、ゾーニングのためのシステムおよび方法に関する。
【背景技術】
【０００４】
ワイヤレスネットワークによって扱われるワイヤレスデータの量は、主としてスマートフォン、タブレット、およびビデオストリーミングによって促されて著しく増え、増加し続けることを継続すると予測される。データの増加する量に加えて、ワイヤレスネットワークに接続するデバイスの数が急激に増え続け、おそらく数十億のデバイスに達すると予測される。異なる応用は、将来のワイヤレスネットワークの性能に異なる要件を課すことになる。将来のワイヤレスネットワークは、柔軟性が高く、効率が良く、オープンであり、顧客および消費者のためにカスタマイズ可能であることが期待される。
【発明の概要】
【課題を解決するための手段】
【０００５】
複数のネットワークノードを有するソフトウェア・デファインド・ネットワーク(SDN)のためのネットワークのゾーニングの方法の一実施態様は、少なくとも1つのゾーン量パラメータに従ってゾーンの数Kを決定するステップを含む。Kが与えられると、SDNの複数のネットワークノードが、K個のゾーンにパーティショニングされる。K個のゾーンは、K個のSDNコントローラをそれぞれ割り当てられる。K個のSDNコントローラの各々は、トラフィックエンジニアリングの判断を行い、それぞれのゾーンにパーティショニングされたネットワークノードのための分散型ネットワーク最適化を実行するように構成される。
【０００６】
通信システムの一実施態様は、複数のネットワークノード、複数のコントローラ、ゾーニングコントローラ、およびマスタコントローラを含む。複数のトラフィックフローが、リンクを介して複数のネットワークノードの間を横断する。トラフィックエンジニアリング(TE)の問題が、トラフィックフロー、リンク、およびネットワークノードに対して定義される。ゾーニングコントローラは、複数のコントローラから選択され得るゾーンコントローラの部分集合のサイズを決定するように構成される。ゾーニングコントローラは、ゾーンコントローラの部分集合を選択するようにさらに構成される。ゾーニングコントローラは、複数のネットワークノードをゾーンにヒューリスティックにパーティショニングし、ゾーンコントローラの部分集合をゾーンにそれぞれ割り当てるようにさらに構成される。マスタコントローラは、TEの問題をゾーンに対応するTEの下位の問題に分解するように構成される。ゾーンコントローラの部分集合は、ゾーンに対するTEの下位の問題をそれぞれ解くように構成される。
【０００７】
ゾーニングコントローラの一実施態様は、ネットワーク・インターフェース・コントローラ(NIC)およびプロセッサを含む。NICは、制御プレーンによって複数のSDNコントローラおよび複数のネットワークノードに結合され得る。複数のネットワークノードは、データプレーンによってリンクを介してトラフィックフローにより横断され得る。TEの問題が、複数のネットワークノード、トラフィックフロー、およびリンクに対して定義され得る。プロセッサは、予測されるTEの複雑さ、複数のネットワークノードを含むネットワークのサイズ、およびトラフィックフローを含むトラフィック負荷に従って、ゾーンコントローラの部分集合のサイズを決定するように構成される。プロセッサは、コントローラのトポロジー、ネットワークのトポロジー、およびトラフィック負荷に従って、複数のSDNコントローラからゾーンコントローラの部分集合を選択するようにさらに構成される。プロセッサは、複数のネットワークノードをゾーンにパーティショニングし、ゾーンコントローラの部分集合をゾーンにそれぞれ割り当てるようにさらに構成され、一部の実施態様において、パーティショニングすることは、ヒューリスティックに行われる。
【０００８】
本発明およびその利点のより完全な理解のために、明細書中では、添付の図面と併せて考慮される以下の説明に対する参照がなされる。
【図面の簡単な説明】
【０００９】
【図１】ゾーニングされたネットワークの一実施形態の図である。
【図２】トポロジーグラフの一実施形態の図である。
【図３】フローグラフの一実施形態の図である。
【図４】SDNをゾーニングする方法の一実施形態の流れ図である。
【図５】コンピューティングシステムの一実施形態のブロック図である。
【図６】トポロジーグラフの別の実施形態の図である。
【図７】クラスタリングのヒューリスティックな手法を用いる地理的ゾーニングの結果の図である。
【図８】パーティショニングのヒューリスティックな手法を用いる地理的ゾーニングの結果の図である。
【図９】タスク割り当てのヒューリスティックな手法を用いる地理的ゾーニングの結果の図である。
【図１０】ゾーンに基づくTE最適化問題の図である。
【図１１】フローグラフの構築の図である。
【発明を実施するための形態】
【００１０】
実施形態の作製および使用が、以下で詳細に検討される。しかしながら、本発明は、多種多様な特定の文脈で具現化され得る多くの応用可能な発明の概念を提供することを理解されたい。検討される特定の実施形態は、本発明を作製および使用する特定の方法を例示するに過ぎず、本発明の範囲を限定しない。
【００１１】
将来のワイヤレスネットワークは、より高いスループット、より低いレイテンシー、より少ないエネルギー、より少ないコスト、およびより多くの接続の需要を満たすことが期待される。ネットワーク機能仮想化(network function virtualization，NFV)およびソフトウェア・デファインド・ネットワーキング(software defined networking，SDN)などのテクノロジーが、将来のワイヤレスネットワークを構築する際にますます重要になった。NFVは、専用のハードウェアにこれまでは結びつけられているネットワーク機能がデータセンターのクラウドコンピューティングインフラストラクチャで実行されることを可能にする。データプレーン、制御プレーン、および管理プレーンのネットワーク機能を専用のハードウェアインフラストラクチャから分離することは、将来のワイヤレスネットワークアーキテクチャの当たり前の機能になる可能性が高い。1つの利点は、ネットワークの機能の需要を弾力的にサポートする能力である。SDNは、インテリジェントでプログラミング可能なネットワークを生み出すためのアーキテクチャのフレームワークであり、制御プレーンおよびデータプレーンが分離され、ネットワークのインテリジェンスおよび状態が論理的に集中化され、基礎を成すネットワークインフラストラクチャがアプリケーションから抽象化される。
【００１２】
トラフィックエンジニアリング(TE)の問題は、様々なトラフィックフローに関するルーティング経路を決定し、ネットワークの有用性が最大化されるようにそれぞれのサービス品質(QoS)の要件に従って経路に沿ってリソース、たとえば、帯域幅を割り振ることである。TEは、ネットワークが大きくなるにつれてより複雑化する複雑な問題である。SDNの特徴は、ワイヤレスネットワークが性能を高めるためにゾーンに動的に分割され得ることである。より詳細には、ワイヤレスネットワークをゾーンに分割すること、つまり、ネットワークをゾーニングすることが、ネットワークのサイズまたは負荷が原因で集中的な制御が現実的でなくなるかまたは実行不可能になるTEの問題の分散型の最適化を可能にすることが本明細書において理解される。ゾーンは、そのゾーンのゾーンコントローラ、すなわち、SDNコントローラと、そのゾーンのノードおよびリンクを含むそのゾーンの関連するネットワーク要素とを含む。ワイヤレスネットワークが地理的ゾーンまたは論理的ゾーンに分割され得ることが、本明細書においてさらに理解される。地理的ゾーンは、とりわけ、ユーザ機器(UE)、無線ノード、およびルータの位置、ならびにそれらの密度などの地域的な考慮事項に応じて形成される。たとえば、ゾーンは、10マイル以内のすべてのネットワーク要素にサービスを提供する単一のSDNコントローラによって定義される可能性がある。代替的に、論理的なネットワークのゾーンが、ネットワークトラフィックフローに応じて形成される。たとえば、特定のトラフィックフローに関連するネットワーク要素が、単一の論理的ゾーンおよび単一のSDNコントローラに割り振られる可能性がある。地理的ゾーニングは、アークフローモデル(arc-flow model)を用いて定式化されるTEの最適化になじみやすい。論理的ゾーニングは、パスフローモデル(path-flow model)を用いて定式化されるTEの最適化になじみやすい。ローカルゾーンコントローラがマスタゾーンコントローラまたはマスタコントローラによってさらに制御および調整される可能性があることが、本明細書においてさらに理解される。ワイヤレスネットワークは、ゾーニングコントローラによって周期的に再ゾーニングされ、トラフィックが変動し、ユーザが1つのゾーンから別のゾーンにマイグレーションするときにマスタゾーンコントローラによって再最適化される可能性がある。
【００１３】
ゾーニングの問題の最適化は、ネットワーク要素をゾーンにグループ分けすることと、分散型のゾーンに基づくTEの最適化のオーバーヘッドを最小化することとバランスである。TEの問題の分散型の最適化によって、TEの問題は、様々なゾーンのためのローカルゾーンコントローラ、すなわち、SDNコントローラに課される下位の問題に分解される可能性がある。制御プレーンにあるSDNコントローラは、ネットワーク要素からTEの問題を定式化するためにステータス情報およびトラフィックの要件を収集する。SDNコントローラは、ネットワークの動作を指示するためにデータプレーンのハードウェアに制御の判断を与える。
【００１４】
制御プレーンのオーバーヘッドは、いくつかの根源がある。これらの根源は、TEの問題の初期化、ネットワークステータスの報告、ネットワークのプロビジョニングコマンド、およびSDNコントローラの間のインタラクションを含む。TEの問題の初期化のオーバーヘッドは、マスタコントローラが送信元、送信先、需要などのトラフィックフロー情報を選択されたゾーンコントローラに配信することが原因である。ネットワークステータスは、ノードに入るリンクのステータスおよびノードのステータスに対応する。ゾーン内のノードを接続するリンクは、内部リンクであり、異なるゾーンのノードを接続するリンクは、境界リンクである。異なるゾーンにSDNコントローラを分散させることは、ネットワークステータスの報告およびネットワークのプロビジョニングを所与のゾーンにとどめることができるが、様々なゾーンを調整する際のオーバーヘッドのコストをもたらす可能性がある。最適でない少ない数のゾーンは、調整のオーバーヘッドを減らす一方、個々のSDNコントローラに対するネットワークステータスの報告およびネットワークのプロビジョニングの負荷を増やし、最適でない多数のゾーンは、個々のSDNコントローラのネットワークステータスの報告およびネットワークのプロビジョニングの負荷を減らす一方、調整のオーバーヘッドを増やす。したがって、ゾーンの数を決定することは、ゾーニングの最適化の中でバランスを取るタスクである。ゾーンの数の決定は、概して時間で表される予測されるゾーンのTEの複雑さ、ネットワークサイズ、およびトラフィック負荷に応じてゾーニングコントローラによってなされる。予測されるゾーンのTEの複雑さの構成要素は、特定のSDNコントローラの処理能力である。予測されるゾーンのTEの複雑さの別の構成要素は、TEの最適化がどれだけ速く行われるべきかということである。TEの問題の解は、少なくとも部分的に、トラフィック負荷およびスループットによって決定される期間内に到達される。TEの問題が十分に速く解かれ得ない場合、ノードがどのようにしてトラフィックをルーティングするかを知らないために輻湊が引き起こされる。したがって、特定のSDNコントローラがそのSDNコントローラの予測されるTEの下位の問題を解決するのに不十分な処理能力を有する場合、ゾーンの数が増やされ、それによって、処理負荷をさらに分散させるべきである。TEの複雑さと、ネットワークサイズと、トラフィック負荷との関係は、様々なシステム測定およびデータ点を通じて経験的に観測され得る。これらの測定およびデータ点は、たとえば、管理情報ベース(MIB)に集中化される可能性がある。ゾーンの必要とされる数が知られると、ネットワークは、ゾーンに分割されるかまたはパーティショニングされ得る。ピースまたはパーティションとも称されるゾーンは、特定の実施形態においては重なり合う可能性があり、その他の実施形態においては重なり合わない可能性がある。パーティショニングは、パーティショニングの問題またはゾーニングの問題の解に従って行われる。パーティショニングの問題の解は、いくつかの手法を用いて発見される可能性があり、それらの手法の一部は、地理的ゾーンのために使用され、その他の手法は、論理的ゾーンのために使用される。
【００１５】
ワイヤレスネットワークは、多くのSDNコントローラを含み得る。実際、任意のネットワーク要素が、SDNコントローラを実装し得る。ワイヤレスネットワークをゾーニングする際、ゾーンコントローラは、ネットワーク内の利用可能なSDNコントローラから選択され、潜在的に、一部のSDNコントローラを選択されないまま残す。たとえば、いかなるその他のネットワーク要素またはトラフィックフローにも関連付けられないSDNコントローラは、選択されない可能性がある。同様に、一部のネットワーク要素は、いかなるSDNコントローラにも関連付けられない可能性がある。ゾーンコントローラとして選択するSDNコントローラの数は、ゾーンの数に依存する可能性がある。たとえば、ネットワークは、ゾーン毎に1つのSDNコントローラを割り当てるように構成される可能性がある。ゾーンの数は、概して、利用可能なSDNコントローラの数以下である。
【００１６】
ゾーンコントローラは、概してホップ数で表される最小のコントローラ間の距離を最大化することを目標として選択される。代替的な実施形態においては、ユークリッド距離、通信遅延、および当業者に明らかであろうその他のものを含む距離のその他の測定値が使用され得る。ゾーンコントローラは、コントローラの負荷分散を容易にするコントローラの一様な分布を得るようにやはり選択される。コントローラ間の距離は、所与の領域内のノードの密度によって影響される可能性がある。密なエリアに多くのSDNコントローラを持つことは有利であるが、短いコントローラ間の距離を有する傾向があり、短いコントローラ間の距離は、最小のコントローラ間の距離を最大化するという目標に対して対抗する効果を有する。この傾向のバランスを取るために、SDNコントローラに関するコントローラ間の距離は、特定のSDNコントローラがノードの所与の分布に対してどれだけ中心にあるかまたは中心から外れているかに応じて重み付けされる可能性がある。SDNコントローラの数が少ないとき、選択は、基本的にSDNコントローラのあらゆるあり得る組合せを評価する網羅的探索によって行われる可能性がある。そうでない場合、選択は、ヒューリスティックに行われる可能性がある。SDNコントローラが選択されると、各SDNコントローラがゾーンにディスパッチされ、そのSDNコントローラのTEの下位の問題を解くためにそのSDNコントローラを効果的に使う。SDNコントローラをディスパッチすることは、ディスパッチの問題に対する解に対して行われる。
【００１７】
N個のノードのネットワークに関して、N個のノードのすべてがそれらのノードをその他のノードに接続するリンクを介してデータプレーンのパケットを転送する。ノードの部分集合Sが、コントローラとして働くように構成される。ゾーニングプロセスは、データプレーンのノードの部分集合をコントローラノードに結びつけることによって|S|個のゾーンを生成する。それぞれのデータプレーンのノードは、一意のコントローラに関連付けられ、そのコントローラは、そのデータプレーンのノードのネットワークステータスを収集し、そのデータプレーンのノードのフォワーディングテーブルをプロビジョニングする。ネットワークステータスは、ノードに入るリンクのステータスに対応する。コントローラは、制御プレーンにおいて互いにインタラクションし、分散型ネットワーク最適化(distributed network optimization，DNO)に参加する。コントローラは、DNOの問題を解くために一緒に働き、DNOの問題は、各ゾーンに対応する複数の下位の問題と調整するマスタの問題とに分解され得る。分散型の最適化は、反復的に解かれる可能性がある。それぞれの反復において、ゾーンの下位の問題が、ゾーンに関する収集されたネットワークステータス情報および境界リンクを使用するオーバーヘッドのコストに応じてゾーンのためのリソースの割り振りを得るために解かれる。境界リンクのためのリソースの割り振りは、マスタのTEの問題を解くマスタSDNコントローラによって調整される可能性がある。
【００１８】
パーティショニングの問題は、以下のように、地理的ゾーニングのために定式化され、TEの問題の初期化のオーバーヘッドは無視される。
【００１９】
【数１】
0006323733.tif 000002
【００２０】
ここで、
Nは、ネットワーク内のノードの集合であり、
Sは、コントローラの集合であり、S⊆Nであり、
mは、マスタコントローラであり、m∈Sであり、
αは、ノードの報告毎のデータユニットの数であり、
βは、リンクの報告毎のデータユニットの数であり、
γは、リンク毎の補助的データユニットの数であり、
ηは、分散型ネットワーク最適化の反復の回数であり、
μは、ノードのプロビジョニング毎のデータユニットの数であり、
νは、リンクのプロビジョニング毎のデータユニットの数であり、
τは、ゾーン不均衡許容因子であり、
lijは、iおよびjの接続性インジケータであり、∀i,j∈Nであり、
hijは、jからjまでのホップの距離であり、∀i,j∈Nである。
【００２１】
定式化の第1の条件は、ゾーン毎の収集のオーバーヘッド
【数２】
0006323733.tif 000003
を定義する。各ノードは、そのノード自体およびそのノードに入るリンクについての情報をそのノードのコントローラに報告する。報告は、個々のゾーンにおいて行われ、送信される総ビットが、収集のオーバーヘッドとして数えられる。第2の条件は、各スレーブコントローラがマスタコントローラに報告し、マスタコントローラから受信する総ビットを含むゾーン毎の調整のオーバーヘッド
【数３】
0006323733.tif 000004
を示す。これらの各々は、個々のゾーンの共有されるリンクの数および調整の反復の回数に適用される。第3の条件は、ゾーン毎の収集のオーバーヘッドと同様に数えられるゾーン毎のプロビジョニングのオーバーヘッド
【数４】
0006323733.tif 000005
を定義する。プロビジョニングは、ノードおよびリンクのために実行される。各リンクは、それぞれの末端のノードのために1回ずつ、2回プロビジョニングされる。第4の条件は、ゾーンのバランスを取る制約であり、τは、問題の実行可能性を保証するように選択される。第5の条件は、ノード-コントローラの関連付けに関する判断を2値に拘束する。最後の制約は、各ノードが単一のコントローラに関連付けられることを示す。aisは、iがsに関連付けられるかどうかを示す決定変数である。
【００２２】
上で定式化されたように、クラスタリング、パーティショニング、タスク割り当てを含む、地理的ゾーンに関するパーティショニング、すなわち、ゾーニングの問題を解くいくつかのヒューリスティックな手法が存在する。クラスタリングは、ホップの距離または所与の距離の尺度に基づいて各ノードを最も近いコントローラに関連付ける。パーティショニングは、ネットワークをS個の接続された構成要素にパーティショニングし、それから、コントローラを割り当てる。タスク割り当ては、MinMinの方針を適用する。これらのヒューリスティックな手法は、物理的トポロジーの情報を用いて地理的ゾーンを形成する。物理的トポロジーの情報は、制御プレーンのトポロジーおよびデータプレーンのトポロジーを含む。制御プレーンのトポロジーの情報は、SDNコントローラ、ルータ、およびUE、SDNコントローラ間の接続、各ネットワーク構成要素/SDNコントローラのペアの間の接続、各UE/SDNコントローラのペアの間の接続、ならびにノードおよび接続に関連するパラメータについての情報を含む。パラメータは、接続のコスト、ノードの能力などを含み得る。接続は、実際のものであるかまたは仮想的なものである可能性がある。データプレーンのトポロジーの情報は、ルータおよびUE、有線およびワイヤレスを含む物理的リンク、ならびにノードおよびリンクに関連するパラメータについての情報を含む。これらのパラメータは、TEの問題にもたらされる計算負荷を含み得る。
【００２３】
クラスタリングによって、各コントローラは、ゾーンの内部のノードのうちの1つへの直接リンクを有する外部のノードを徐々に合併することによってサイズが大きくなるゾーンを最初に形成する。ノードは、複数のゾーンによって合併され得るとき、ホップの距離が最も近いゾーンによって合併される。複数のゾーンがノードとコントローラとの間の同じホップの距離を有するとき、判断は、無作為に行われる可能性がある。コントローラは、この手法においては、ゾーン内に概して地理的に含まれる。
【００２４】
パーティショニングによって、ネットワークは、最小の合計のリンクの重みによるカットを用いてバランスの取れたサイズのk個の接続された構成要素にパーティショニングされるネットワークグラフとしてモデル化され得る。これは、バランスの取れた最小kカット(balanced minimum k-cut)問題とも称される。パーティショニングのヒューリスティックは、ネットワークグラフのバランスの取れた最小kカットを見つけることに基づき、ここで、k=|S|である。これは、2つのステップで実行される。第1は、各ノードiがα+βΣj∈Nlijによって重み付けされ、すべてのリンクが等しい重みγを有する元々重み付けされているネットワークグラフ上でバランスの取れた最小kカット問題を解くことである。解は、多レベルパーティショニングなどの知られているヒューリスティックを取り入れることによって発見される。そして、コントローラが、ノードとコントローラとの間およびマスタコントローラとスレーブコントローラとの間の総通信コストを最小化することを目標として各パーティションにディスパッチされる。
【００２５】
ディスパッチの問題は、タスク割り当ての問題としてモデル化される。Πが、パーティショニングの解法の第1のステップにおいて得られたパーティションの集合を表すものとする。Πは、コントローラと一致する数のパーティションを含み、つまり、|Π|=|S|である。B(P)が、パーティションP∈Πの境界であるものとし、この境界は、P内に一端を有し、P'内に他端を有する辺の集合で構成され、P'≠Pである。ePによって表記される各辺e∈Pに関して、P内に存在する末端の頂点。コントローラのディスパッチの問題は、以下のように定式化される。
【００２６】
【数５】
0006323733.tif 000006
【００２７】
ここで、cs,Pは、コントローラsがパーティションPにディスパッチされるかどうかを示す決定変数である。最初の3つの条件は、それぞれのコントローラをパーティションにディスパッチすることによって引き起こされる収集のオーバーヘッド、調整のオーバーヘッド、およびプロビジョニングのオーバーヘッドを定義する。第4の制約は、判断が2値であることを要求する。第5の制約は、パーティションが厳密に1つのコントローラにディスパッチされることを強制する。第6の制約は、各コントローラが2つ以上のパーティションにディスパッチされ得ないことを要求する。第6の制約は、パーティションよりも多くのコントローラを許容し、柔軟性を提供する。コントローラは、それらのコントローラの割り当てられた地理的ゾーン内に必ずしも制約されない。
【００２８】
タスク割り当てによって、ゾーニングの問題は、総コストを最小化するために各ノードが一意のコントローラに割り当てられたタスクであるように構築される。ゾーニングの構成ZのコストC(Z)は、以下、すなわち、
【００２９】
【数６】
0006323733.tif 000007
【００３０】
によって記述され、ここで、
【数７】
0006323733.tif 000008
は、ゾーン内の情報収集のコスト、マスタ-スレーブの調整のコスト、およびプロビジョニングのコストである。コストは、上の元の問題の定式化によって計算される。pは、元の問題の第4のゾーンのサイズのバランスを取る制約に関連して計算されるゾーンの不均衡のコストであり、ωは、重み係数である。
【００３１】
割り当てのヒューリスティックによれば、Zsは、コントローラsを割り当てられたゾーンであり、ここで、s∈Sである。最初のゾーニングの構成Z0においては、各コントローラが、それ自体をその唯一のメンバーとして含むゾーンに割り当てられる。すべてのコントローラでないノードは、関連付けられていなノードの集合Uに属する。UのフロンティアFsが、ゾーンZsに対して定義され、すべてのゾーンに関して繰り返される。フロンティアFsは、Zs内のノードへのリンクを有するU内のノードの集合を含む。各反復において、フロンティアノードiが、Uから境界を接するゾーンZsに移される。移動は、2つのステップでなされる。第1のステップにおいて、各フロンティアFsの各ノードiに関して、コストの増加Δ(i,s)が、フロンティアノードiを加えたそれぞれの境界のゾーンZsについて計算される。新しいゾーニングの構成Zt(i,s)のコストが、式Δ(i,s)=C(Zt(i,s))-C(Zt)によってそのゾーニングの構成の前のゾーニングの構成Ztに対して計算される。第2のステップにおいては、最小のコストの増加があるフロンティアノードが特定され、そのノードが移される。集合Uが空であるとき、手順は停止する。
【００３２】
論理的ゾーンは、メンバーのフローの候補ルーティング経路の和集合である。複数の論理的ゾーンは、フロー経路の間のリンクの共有が原因で物理的に重なり合う可能性がある。上で定式化されたように、タスク割り当てのヒューリスティックおよびグラフパーティションのヒューリスティックを含む、論理的ゾーンに関するゾーニングの問題を解くいくつかの手法が存在する。ヒューリスティックなアルゴリズムは、データフロー情報を用いて論理的ゾーンを形成する。データフロー情報は、フロー毎のルーティング経路の候補および各フローに関連するパラメータを含む。パラメータは、TEの問題にもたらされる計算負荷、関連する仮想ネットワークなどを含み得る。グラフパーティションの手法は、フローの間のリンクの共有をモデル化するフローグラフを使用し、グラフ理論を用いて問題を解く。論理的ゾーンに関して、ネットワークは、ノードの集合Nおよびリンクの集合Lを有するものとしてモデル化される。ノードの部分集合Sが、コントローラとして構成され、コントローラのうちの1つが、マスタコントローラmである。トラフィックフローの集合Fが、TEの問題に関して与えられる。個々のフローに関するルーティング経路は知られていると仮定される。ゾーニングプロセスは、フローの部分集合をコントローラノードに結びつけることによってk個のゾーンを生成する。各フローは、そのフローのルーティング経路に沿ったノードおよびリンクのネットワークステータスを収集する一意のコントローラに関連付けられる。コントローラは、フローの送信元にそれらのTEの判断を知らせる。論理的ゾーンのサイズは、ゾーン内のフローの候補の経路の総数として定義される。論理的ゾーンは、オーバーヘッドのコストを最小化し、ゾーンのサイズのバランスを取ることを目標として形成される。
【００３３】
論理的ゾーニングのためのゾーニングの構成Zは、フロー-コントローラ関連付け行列によって記述され、
【数８】
0006323733.tif 000009
であり、各列ベクトルZsは、スレーブSDNコントローラsによって制御されるゾーンを定義する。フローf∈Fおよびスレーブコントローラs∈Sに関して、fがsに関連付けられる場合、afs=1であり、そうでない場合は0である。定義によって、ゾーンZsのサイズ|Zs|は、|Zs|=Σf∈Fafs|f|として計算され、ここで、|f|は、フローfのサイズであり、これは、フローfに関する候補の経路の数である。
【００３４】
ゾーンの構成Zが与えられる場合、オーバーヘッドのコストC(Z)は、C(Z)=Cinit(Z)+Ccoll(Z)+Cprov(Z)+Ccoor(Z)であるような初期化のコストCinit(Z)、収集のコストCcoll(Z)、プロビジョニングのコストCprov(Z)、および調整のコストCcoor(Z)を含む。調整のコストは、最適化の反復全体にわたって発生し、一方、その他の3つのコストは、最適化の初めまたは終わりに一回かかる。
【００３５】
初期化のコストは、マスタコントローラがフローの送信元、送信先、需要などを含むフロー情報をスレーブコントローラに配信することが原因である。所与のスレーブコントローラに配信される情報は、スレーブコントローラに関連するフローの情報に制限される。初期化のコストは、Cinit(Zs)=μΣf∈Fafshmsによって与えられ、μは、フローの記述毎のデータユニットの数であり、hmsは、マスタコントローラからスレーブコントローラへの通信のためのデータユニットごとのオーバーヘッドのコストである。
【００３６】
収集のコストは、各スレーブコントローラがそのスレーブコントローラのゾーン内のノードおよびリンクの状態を集めることによる。収集コストは、
【数９】
0006323733.tif 000010
によって与えられ、ノードiまたはリンクlがスレーブコントローラsに関連付けられるかどうかをそれぞれ示し、αは、ノードの状態の報告毎のデータユニットの数であり、βは、リンクの状態の報告毎のデータユニットの数であり、hisは、ノードからスレーブコントローラへの通信に関するデータユニット毎のオーバーヘッドのコストであり、
【数１０】
0006323733.tif 000011
は、末端のノードとスレーブコントローラとの間のリンクに関するデータユニット毎のオーバーヘッドのコストである。
【００３７】
プロビジョニングのコストは、スレーブコントローラがそれらのスレーブコントローラのゾーン全体にTEの判断を配信することによる。プロビジョニングのコストは、
【数１１】
0006323733.tif 000012
によって与えられ、ここで、νは、フロー経路毎のTEの判断のデータユニットの数であり、
【数１２】
0006323733.tif 000013
は、スレーブコントローラからフローの送信元ノードへの通信に関するデータユニット毎のオーバーヘッドのコストである。
【００３８】
調整のコストは、マスタコントローラがスレーブコントローラのTEの下位の問題の状態を収集し、更新することによる。やりとりされるデータの量は、ゾーンによって共有されるリンクの数に比例する。調整のコストは、
【数１３】
0006323733.tif 000014
によって与えられ、fおよびgの1つだけがゾーンZsに属するかどうかを示し、ηは、TEの最適化の反復の回数であり、γは、ゾーンの間の共有されたリンク毎のデータユニットの数であり、hsmおよびhmsは、スレーブコントローラとマスタコントローラとの間の通信に関するオーバーヘッドのコストであり、nfgは、fおよびgにおいて共有されるリンクの数であり、ここで、f,g∈Fである。
【００３９】
上述のように、パーティショニングの問題は、以下であるような、オーバーヘッドのコストC(Z)の最小化の実践である。
【００４０】
【数１４】
0006323733.tif 000015
【００４１】
ここで、εは、負荷不均衡許容因子である。
【００４２】
論理的ゾーンに関するタスク割り当ての手法を用いてパーティショニングの問題を解くために、不均衡コスト因子(imbalance cost factor，ICF)ωが与えられると、ゾーニングの問題は、サイズのバランスを取る制約を削除し、罰則項p(Z)を追加することによって緩められる。新しいコストの式および罰則項は、以下によって与えられる。
【００４３】
【数１５】
0006323733.tif 000016
【００４４】
したがって、ゾーニングの問題は、
【数１６】
0006323733.tif 000017
であるような
【数１７】
0006323733.tif 000018
になる。タスク割り当ての手法を用いて、各フロー、すなわち、タスクが、目的関数の値を最小化するために一意のコントローラ、すなわち、プロセッサに割り当てられる。MinMinヒューリスティックなどのアルゴリズムは反復し、ゾーンの構成Zを徐々に構築する。
【００４５】
タスク割り当ての手法においては、割り当ての判断がなされないフローの集合が、Uによって表される。最初に、ゾーンの構成Zは、空集合であり、U=Fである。それぞれの反復において、割り当ての判断は、1つのフローに関して行われ、そのフローfをスレーブコントローラsに割り当てる。これは、afs=1と設定することによって表される。それから、フローは、Uから取り除かれる。
【００４６】
グラフパーティションのヒューリスティックな手法においては、同じ送信元から生じ、同じ送信先に宛てられたフローが単一のフローと考えられるように、フローがそれらのフローの送信元および送信先に応じて集約される。そして、フローグラフが、各フローを頂点として表し、頂点の部分集合を頂点によって共有されるそれぞれの異なるネットワークリンクに接続することによって構築される。各頂点は、重みt×|f|を与えられ、ここで、tは、頂点が表す元の、すなわち、集約の前のフローの数であり、|f|は、フローのサイズである。辺も、通過する異なるフロー経路の数に応じた重みを与えられる。結果として得られるフローグラフは、ハイパーグラフであり、各辺は、リンクの共有を示唆し、一意のネットワークリンクに対応する。フローグラフは、k=|S|に対してk個の接続された構成要素にパーティショニングされ、各構成要素は、論理的ゾーンを定義し、一意のコントローラをディスパッチされる。
【００４７】
図1は、ゾーニングされたネットワーク100の一実施形態の図である。ゾーニングされたネットワーク100は、4つのコントローラ110-1から110-4、マスタコントローラ120、ゾーニングコントローラ150、および複数のネットワークノード140を含む。複数のネットワークノード140は、ゾーニングされたネットワーク100全体にさまざまに分散される。ネットワークノードは、アクセスポイント、NodeB、または進化型NodeB(eNB)とも称される。コントローラ110-1から110-4およびマスタコントローラ120は、コントローラとして働くための追加の能力および構成を有するネットワークノードでもある。概して、任意のネットワークノードが、コントローラを具現化し得る。コントローラ110-1から110-4は、SDNコントローラ、ゾーンコントローラ、またはスレーブコントローラとも称される。マスタコントローラ120も、SDNコントローラとも称される。
【００４８】
ゾーニングコントローラ150は、ゾーニングされたネットワーク100を4つのゾーン130-1から130-4にパーティショニングする。4つのゾーンの各々は、コントローラ110-1から110-4のうちの1つを割り当てられる。ゾーン130-1は、中の3つのネットワークノードにサービスを提供するコントローラ110-1を割り当てられる。ゾーン130-2は、中の4つのネットワークノードにサービスを提供するコントローラ110-2を割り当てられる。ゾーン130-3は、中の4つのネットワークノードにサービスを提供するコントローラ110-3を割り当てられる。ゾーン130-4は、中の3つのネットワークノードにサービスを提供するコントローラ110-4を割り当てられる。マスタコントローラ120は、コントローラ110-1から110-4の間のTEの最適化を調整する。マスタコントローラ120およびゾーニングコントローラ150は、別個の論理的ネットワーク要素である。マスタコントローラ120およびゾーニングコントローラ150は、単一のコンピューティングシステムまたは別個のコンピューティングシステムにおいて具現化される可能性がある。
【００４９】
図2は、トポロジーグラフ200の一実施形態である。トポロジーグラフ200は、400個のネットワークノード220を含み、ネットワークノード220のうちの10個は、コントローラ210である。ネットワークノード220は、トポロジーグラフ200内で白丸によって表され、一方、コントローラ210は、黒丸によって表される。コントローラ210のいずれかが、マスタコントローラとしてやはり指定され得る。ネットワークノード220は、リンクまたはホップを表す辺230によって接続される。
【００５０】
図3は、フローグラフ300の一実施形態である。フローグラフ300は、白い四角によって表されるトラフィックフロー310、灰色の丸によって表されるハイパーエッジ320、および線330を含む。トラフィックフロー310は、それぞれの重みを有する。トラフィックフローの重みは、そのトラフィックフローのフローのサイズとそのトラフィックフローのフローの数との積として計算される。フローのサイズは、フローのための候補の経路の数を指す。フローの数は、集約されていないフローの数を指し、集約は、共通の送信元と共通の送信先との間のフローを1つの集約フローとして扱うことである。たとえば、フローグラフ300において、フローのより下の行は、左から右に向かって4.0、5.0、10.0、8.0、9.0、および1.0の重みを有する。単に辺とも称されるハイパーエッジ320は、物理的リンクを表す。線330は、トラフィックフロー310をハイパーエッジ320にさまざまに接続し、特定のトラフィックフローが物理的リンクを共有することを示す。ハイパーエッジ320も、通過するフロー経路の数を示すそれぞれの重みを割り当てられる。
【００５１】
図4は、SDNをゾーニングする方法の一実施形態の流れ図である。SDNは、複数のネットワークノードおよび複数のSDNコントローラを含む。方法は、開始ステップ410において始まる。ゾーン量ステップ420において、ネットワークがいくつのゾーンにパーティショニングされるべきかについての決定がなされる。この量Kは、少なくとも1つのゾーン量パラメータに従って決定される。ゾーン量パラメータは、予測されるゾーンのTEの複雑さ、ネットワークサイズ、トラフィック負荷、およびフロー情報を含む。より詳細には、決定は、TEの複雑さとネットワークサイズとの間の関係、トラフィック負荷、およびフロー情報を考慮する。TEの複雑さは、コントローラの処理能力と、TEの最適化がどれだけ速く行われるべきかに関する動作要件との関数である。
【００５２】
特定の実施形態において、方法は、少なくともK個のゾーンコントローラが利用可能なSDNコントローラから選択される選択ステップをも含む。ゾーンコントローラは、最小のコントローラ間の距離が最大化されるように選択される。概して、コントローラ間の距離は、ホップ数として表される。ゾーンコントローラを選択することは、ゾーンコントローラの一様な分布を達成することを目的とする。一様な分布は、負荷分散を容易にする。加えて、特定の実施形態においては、コントローラ間の距離が、ネットワークノードの密度に大きな相違があるときに適切にゾーンのバランスを取るように重み付けされる。コントローラの数Kが小さいとき、選択は、網羅的に行われる可能性があり、すべてのあり得る組合せを効果的に評価する。そうでない場合、K個のコントローラを選択するためにヒューリスティックな方法が使用され得る。
【００５３】
図4の実施形態について続けると、ゾーニングステップ430において、複数のネットワークノードが、K個のゾーンにパーティショニングされる。一部の実施形態において、K個のゾーンは、地理的ゾーンである。その他の実施形態において、K個のゾーンは、論理的ゾーンである。パーティショニングの目的は、TE最適化プロセスのオーバーヘッドのコストを最小化することである。TEの最適化のオーバーヘッドのコストは、ノードのステータスおよびリンクのステータスを収集する通信コスト、プロビジョニングの通信のコスト、ならびにコントローラの間の調整をする通信のコストを含む。パーティショニングは、ヒューリスティックな方法によって実行される。地理的ゾーンのためのクラスタリング、パーティショニング、およびタスク割り当ての手法、ならびに論理的ゾーンのためのタスク割り当ておよびグラフパーティショニングを含むいくつかのヒューリスティックな手法が使用され得る。ディスパッチステップ440において、コントローラが、それぞれのゾーンに割り当てられる。方法は、終了ステップ450において終了する。
【００５４】
図5は、本明細書において開示されるデバイスおよび方法を実装するために使用され得るコンピューティングシステム500のブロック図である。特定のデバイスは、示される構成要素のすべてまたは構成要素の部分集合のみを利用する可能性があり、統合のレベルは、デバイス毎に変わる可能性がある。さらに、デバイスは、複数の処理ユニット、プロセッサ、メモリ、送信機、受信機などの構成要素の複数のインスタンスを含む可能性がある。コンピューティングシステム500は、スピーカ、マイクロフォン、マウス、タッチスクリーン、キーパッド、キーボード、プリンタ、ディスプレイなどの1つまたは複数の入力/出力デバイスを備えた処理ユニット502を含み得る。処理ユニットは、バス520に接続された中央演算処理装置(CPU)514、メモリ508、大容量ストレージデバイス504、ビデオアダプタ510、およびI/Oインターフェース512を含む可能性がある。
【００５５】
バス520は、メモリバスまたはメモリコントローラ、周辺バス、ビデオバスなどを含む任意の種類のいくつかのバスアーキテクチャのうちの1つまたは複数である可能性がある。CPU 514は、任意の種類の電子データプロセッサを含み得る。メモリ508は、スタティックランダムアクセスメモリ(SRAM)、ダイナミックランダムアクセスメモリ(DRAM)、同期DRAM(SDRAM)、読み出し専用メモリ(ROM)、これらの組合せなどの任意の種類の非一時的システムメモリを含み得る。一実施形態において、メモリ508は、ブートアップで使用するためのROMと、プログラムを実行している間に使用するためのプログラムおよびデータストレージのためのDRAMとを含み得る。
【００５６】
大容量ストレージ504は、データ、プログラム、およびその他の情報を記憶し、データ、プログラム、およびその他の情報をバス520を介してアクセス可能にするように構成された任意の種類の非一時的ストレージデバイスを含み得る。大容量ストレージ504は、たとえば、ソリッドステートドライブ、ハードディスクドライブ、磁気ディスクドライブ、光ディスクドライブなどのうちの1つまたは複数を含み得る。
【００５７】
ビデオアダプタ510およびI/Oインターフェース512は、外部入力および出力デバイスを処理ユニット502に結合するためのインターフェースを提供する。示されるように、入力および出力デバイスの例は、ビデオアダプタ510に結合されたディスプレイ518およびI/Oインターフェース512に結合されたマウス/キーボード/プリンタ516を含む。その他のデバイスが処理ユニット502に結合される可能性があり、追加的なまたはより少ないインターフェースカードが利用される可能性がある。たとえば、ユニバーサルシリアルバス(USB)(図示せず)などのシリアルインターフェースが、プリンタのためのインターフェースを提供するために使用される可能性がある。
【００５８】
また、処理ユニット502は、アクセスノードまたは異なるネットワークへのイーサネット(登録商標)ケーブルなどの有線リンクおよび/またはワイヤレスリンクを含む可能性がある1つまたは複数のネットワークインターフェース506を含む。ネットワークインターフェース506は、処理ユニット502がネットワークを介してリモートユニットと通信することを可能にする。たとえば、ネットワークインターフェース506は、1つまたは複数の送信機/送信アンテナおよび1つまたは複数の受信機/受信アンテナを介したワイヤレス通信を提供し得る。一実施形態において、処理ユニット502は、その他の処理ユニット、インターネット、リモートストレージ設備などのリモートデバイスとのデータ処理および通信のためにローカルエリアネットワーク522または広域ネットワークに結合される。
【００５９】
図6は、トポロジーグラフ600の別の実施形態である。トポロジーグラフ600は、ネットワークノード610を含み、ネットワークノード610のうちの8つが、コントローラ620として指定される。図2に示されたように、ネットワークノード610は、白丸によって表され、コントローラ620は、黒丸によって表される。線630は、様々なネットワークノードの間のリンクを表す。
【００６０】
図7は、実施形態のクラスタリングのヒューリスティックな手法を用いて生成された地理的ゾーニングの結果700の図である。ゾーニングの結果700は、8つの地理的ゾーン710、720、730、740、750、760、770、および780を含む。8つのゾーンは、図6のトポロジーグラフのネットワークノードのすべてを包含する。やはり図6のコントローラ620が、8つの地理的ゾーンに割り当てられる。ゾーンは、ネットワークノードを表す様々に網掛けされた丸のグループおよびそれらの入ってくるリンクによって示される。ゾーニングの結果700は、コントローラ620とそれらのコントローラ620のそれぞれのゾーン内のそれらのコントローラ620のそれぞれのネットワークノードの各々との間の破線も含む。
【００６１】
図8は、実施形態のパーティショニングのヒューリスティックな手法を用いて生成された地理的ゾーニングの結果の図である。ゾーニングの結果800は、8つの地理的ゾーン810、820、830、840、850、860、870、および880を含む。8つのゾーンは、図6のトポロジーグラフのネットワークノードのすべてを包含する。やはり図6のコントローラ620が、8つの地理的ゾーンに割り当てられる。ゾーンは、ネットワークノードを表す様々に網掛けされた丸のグループおよびそれらの入ってくるリンクによって示される。ゾーニングの結果800は、コントローラ620とそれらのコントローラ620のそれぞれのゾーン内のそれらのコントローラ620のそれぞれのネットワークノードの各々との間の破線も含む。
【００６２】
図9は、実施形態のタスク割り当てのヒューリスティックな手法を用いて生成された地理的ゾーニングの結果の図である。ゾーニングの結果900は、8つの地理的ゾーン910、920、930、940、950、960、970、および980を含む。8つのゾーンは、図6のトポロジーグラフのネットワークノードのすべてを包含する。やはり図6のコントローラ620が、8つの地理的ゾーンに割り当てられる。ゾーンは、ネットワークノードを表す様々に網掛けされた丸のグループおよびそれらの入ってくるリンクによって示される。ゾーニングの結果900は、コントローラ620とそれらのコントローラ620のそれぞれのゾーン内のそれらのコントローラ620のそれぞれのネットワークノードの各々との間の破線も含む。
【００６３】
図10は、SDN 1000に関するゾーンに基づくTE最適化問題の図である。SDN 1000は、マスタコントローラ1010、スレーブコントローラ1020、およびネットワークノード1030を含む。マスタコントローラ1010がTE最適化問題を解くのではなく、TE最適化問題が、スレーブコントローラ1020によって解かれ得る下位の問題に分解される。スレーブコントローラ1020の各々が、ゾーン1040に割り当てられる。ゾーン1040は、オーバーヘッドのコストが最小化されるように形成される。特定のコストが、特定のゾーンにとどめられる。たとえば、破線1050によって表されるノードおよびリンクのステータスの収集およびプロビジョニングが、各ゾーンによって閉じ込められる。さらなるゾーンおよびスレーブコントローラはそれらのコストを薄く拡げるが、実線1060によって表されるマスタ-スレーブの調整に関連するオーバーヘッドのコストは、スレーブコントローラの追加によって増える。
【００６４】
図11は、トポロジー1100-Aによるフローグラフ1100-Bの構築の図である。トポロジー1100-Aは、3つのトラフィックフロー1110、1120、および1130を含む。トラフィックフローは、1〜9を付番される9つのネットワークノード1140をさまざまに横切る。第1のフロー1110は、ノード1において生じ、ノード8に宛てられる。トラフィックフロー1110は、2つのルーティング経路、1-2-5-7-8および1-3-5-7-8を有する。第2のフロー1120は、ノード4において生じ、やはりノード8に宛てられる。トラフィックフロー1120は、単一のルーティング経路、4-5-7-8を有する。第3のフロー1130は、ノード6において生じ、ノード9に宛てられる。トラフィックフロー1130は、2つのルーティング経路、6-7-8-9および6-8-9を有する。
【００６５】
フローグラフ1100-Bは、トラフィックフロー1110、1120、および1130を白い長方形として示す。トラフィックフローの各々は、括弧内に示される重みを割り当てられる。重みは、候補のルーティング経路の数、すなわち、フローのサイズとフローの数との積である。この例において、フローの数は、トラフィックフロー1110、1120、および1130の各々について1つである。結果として、トラフィックフローのそれぞれの重みは、候補のルーティング経路の数を反映する。フローグラフ1100-Bは、ハイパーエッジ1150およびハイパーエッジ1160も示す。ハイパーエッジ1150は、3つのトラフィックフローのすべての間で共有される、ノード7とノード8との間の物理的リンクを表す。ハイパーエッジ1160は、トラフィックフロー1110とトラフィックフロー1120との間で共有される、ノード5とノード7との間の物理的リンクを表す。この例において、他の物理的リンクが共有されておらず、それらの物理的リンクはフローグラフ1100-Bに示されてもいない。また、ハイパーエッジ1150および1160は、表された物理的リンクを通過する候補のルーティング経路の数を表す重みを割り当てられる。ハイパーエッジ1150は、トラフィックフロー1110のための2つのルーティング経路、トラフィックフロー1120のための1つのルーティング経路、およびトラフィックフロー1130のための6-7-8-9ルーティング経路に対応する重み4を有する。同様に、ハイパーエッジ1160は、トラフィックフロー1110のための2つのルーティング経路およびトラフィックフロー1120のための1つのルーティング経路に対応する重み3を有する。
【００６６】
例示的な実施形態を参照して本発明が説明されたが、これらの説明は、限定する意味に取られるように意図されていない。例示的な実施形態の様々な修正および組合せならびに本発明のその他の実施形態は、説明を参照することによって当業者に明らかとなろう。したがって、添付の特許請求の範囲はすべてのそのような修正形態または実施形態を包含することが意図される。
【符号の説明】
【００６７】
100  ゾーニングされたネットワーク
110-1，100-2，110-3，110-4  コントローラ
120  マスタコントローラ
130-1，130-2，130-3，130-4  ゾーン
140  ネットワークノード
150  ゾーニングコントローラ
200  トポロジーグラフ
210  コントローラ
220  ネットワークノード
230  辺
300  フローグラフ
310  トラフィックフロー
320  ハイパーエッジ
330  線
500  コンピューティングシステム
502  処理ユニット
504  大容量ストレージデバイス
506  ネットワークインターフェース
508  メモリ
510  ビデオアダプタ
512  I/Oインターフェース
514  中央演算処理装置(CPU)
516  マウス/キーボード/プリンタ
518  ディスプレイ
520  バス
522  ローカルエリアネットワーク
600  トポロジーグラフ
610  ネットワークノード
620  コントローラ
630  線
700  地理的ゾーニングの結果
710，720，730，740，750，760，770，780  地理的ゾーン
800  地理的ゾーニングの結果
810，820，830，840，850，860，870，880  地理的ゾーン
900  地理的ゾーニングの結果
910，920，930，940，950，960，970，980  地理的ゾーン
1000  ソフトウェア・デファインド・ネットワーク(SDN)
1010  マスタコントローラ
1020  スレーブコントローラ
1030  ネットワークノード
1040  ゾーン
1050  破線
1060  実線
1100-A  トポロジー
1100-B  フローグラフ
1110，1120，1130  トラフィックフロー
1140  ネットワークノード
1150，1160  ハイパーエッジ
【図１】
0006323733.tif 000019
【図２】
0006323733.tif 000020
【図３】
0006323733.tif 000021
【図４】
0006323733.tif 000022
【図５】
0006323733.tif 000023
【図６】
0006323733.tif 000024
【図７】
0006323733.tif 000025
【図８】
0006323733.tif 000026
【図９】
0006323733.tif 000027
【図１０】
0006323733.tif 000028
【図１１】
0006323733.tif 000029