(57)【要約】  本発明は、ネットワーク内の障害のケースでコントローラからノードが切断される確率が最小化されることを意味するような、重みを最小化するルーティングアルゴリズムの特性である。本発明において使用される第１のアルゴリズムは、ネットワーク内の最大の自己修復性を提供するコントローラルーティングツリーを発見するための近似アルゴリズムである。当該アルゴリズムは、ここでは最大自己修復性（ＭＲ）アルゴリズムと呼ばれる。ヒューリスティックＭＲアルゴリズムは、開始点として最短パスツリーを選択して、当該ツリーを自己修復性を改善するために修正する。ＭＲアルゴリズムの出力は、必ずしも最短パスツリーではないが、初期ツリーと比較するとより高い自己修復性を提供する。ＲＡＳＰアルゴリズムは、他の最短パスツリーの候補と比較して、改善されたネットワーク自己修復性を伴う最短パスツリーを提供する。【選択図】図７
2014526189.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークトポロジー設計システムにより実装される方法であって、
前記ネットワークトポロジー設計システムは、非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体に結合されてコントローラルーティングツリーモジュールとして動作可能なマイクロプロセッサを有するコントローラを含み、
前記方法は、ネットワークグラフＧにより表現されるスプリットアーキテクチャのネットワークの内部での使用のためのコントローラルーティングツリーＴ´を判定するためのものであり、
複数のスイッチにより実行されるデータプレーンコンポーネントから分離された前記コントローラにより、制御プレーンコンポーネントが実行され、
Ｖを前記ネットワーク内のノードのセットとしＥを前記コントローラに向けて各スイッチを横断するノード間の双方向エッジのセットとして、Ｇ＝（Ｖ，Ｅ）であり、
コントローラルーティングツリーＴ´は、スイッチ群及び前記コントローラの間の負荷分散されない制御トラフィックのパスを表現し、
前記制御トラフィックは、各スイッチから前記コントローラへの双方向情報と、前記コントローラから当該スイッチへの転送決定情報とを表現し、
前記方法は、
前記ネットワークトポロジー設計システムにより、Ｇ内の各スイッチから前記コントローラへの全ての距離の候補をグラフ化するステップと、前記各距離はそれぞれＥのサブセットからなることと、
全ての距離の候補に基づいて、前記各スイッチについて前記コントローラへの最短パスを判定するステップと、各スイッチから前記コントローラへの全ての前記最短パスは前記コントローラについての前記最短パスツリーＴを含むことと、
非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に、前記最短パスツリーＴを記憶させるステップと、
各スイッチについての前記コントローラへの前記最短パスに基づいて、Ｇ内の当該スイッチの全ての隣接ノードを、アップストリーム又はダウンストリームのいずれかとして指定するステップと、
前記コントローラのネイバである１つ又は複数の前記スイッチで始まり各直下ダウンストリームスイッチを横断してＧ内の前記スイッチの全てが処理されるまで、前記ネットワークトポロジー設計システムによって、Ｇ内の各スイッチのために重みを判定し及び割り当てるステップと、
各スイッチに割り当てられた前記重みに基づいて、前記最短パスツリーＴを修正して、改善された自己修復性を伴う修正最短パスツリーＴ´を取得するステップと、
非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に、前記修正最短パスツリーＴ´を記憶させるステップと、
を含む方法。
【請求項２】
前記最短パスツリーＴ´内の、前記スイッチから前記コントローラへの前記パスに基づいて、アウトゴーイングプライマリリンクと、もしあればバックアップとして、前記スイッチから直上アップストリームスイッチへの少なくとも１つのアウトゴーイングセカンダリリンクとを、通信し及び各スイッチ内の非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体に記憶させること、をさらに含む、請求項１の方法。
【請求項３】
スイッチにより、アップストリームリンク又はノードにおける障害を検出するステップと、
前記スイッチにより、前記アウトゴーイングプライマリリンクを、もしあればバックアップとして供されるアウトゴーイングセカンダリリンクへ変更することにより、前記コントローラへの自身のルートを変更するステップと、
をさらに含む、請求項２の方法。
【請求項４】
グラフ化する前記ステップは、管理者の入力、自動化されたディスカバリプロセス、又はそれらの任意の組合せによって実装される、請求項１の方法。
【請求項５】
前記ネットワークトポロジー設計システムによって、Ｇ内の各スイッチのために重みを計算し及び割り当てる前記ステップは、
少なくとも１つのアウトゴーイングセカンダリリンク上の前記コントローラへの少なくとも１つの異なるパスが存在する度合いを判定することにより、Ｖ内の各スイッチへ、当該スイッチがアップストリームノードの障害及びリンク障害から保護されているかに基づいて、前記重みを計算し及び割り当てるステップと、
少なくとも１つのアウトゴーイングセカンダリリンクを用いる少なくとも１つの異なるパスが存在する場合に、前記コントローラから当該スイッチへ、前記少なくとも１つのアウトゴーイングセカンダリリンクの前記存在を通信するステップと、
当該スイッチにおいて、前記少なくとも１つのアウトゴーイングセカンダリリンクをバックアップとして構成するステップと、
をさらに含む、請求項１の方法。
【請求項６】
前記最短パスツリーＴを修正する前記ステップは、
第１のスイッチから前記コントローラに向けて横断される他の各スイッチの前記重みを算入して、前記第１のスイッチにおいて、前記コントローラへの異なるパスを用いることにより前記スプリットアーキテクチャのネットワークの自己修復性の改善が得られるかを判定するステップと、
前記第１のスイッチからの直下のダウンストリームの第２のスイッチにおいて、前記コントローラに向けて横断される各スイッチの前記重みを算入して、当該第２のスイッチから前記コントローラへの異なるパスを用いることにより自己修復性の改善が得られるかを判定するステップと、
Ｇ内の全てのスイッチが処理されるまで、Ｇ内の各スイッチにおいて上述した判定ステップ群を実行するステップと、
をさらに含む、請求項１の方法。
【請求項７】
より前記コントローラに近いスイッチに、より多数のダウンストリームスイッチを有する結果として、より大きい重みが割り当てられる、請求項１の方法。
【請求項８】
スイッチに割り当てられる前記重みは、そのダウンストリームスイッチの数に比例し又は当該数のある割合である、請求項１の方法。
【請求項９】
スイッチの前記重みは、ユーザにより割当てられるコストファクタによりスケーリングされる、そのダウンストリームスイッチの数に基づく、請求項１の方法。
【請求項１０】
前記コストファクタは、前記スイッチがそのアウトゴーイングリンク障害及びその直上アップストリームノード障害の双方に対して保護される場合にはゼロであり、前記スイッチがアウトゴーイングリンク障害に対してのみ保護される場合にはαであり、前記スイッチが直上アップストリームノード障害に対してのみ保護される場合にはβであり、それ以外ならα＋βである、請求項９の方法。
【請求項１１】
ルーティングツリーＴ´を、当該ルーティングツリーが最小の累積的な重みを有するように選択するステップ、をさらに含み、それにより、前記ネットワーク内のリンク又はノード障害のケースで前記コントローラからスイッチが切断される確率が最小化される、請求項１０の方法。
【請求項１２】
スプリットアーキテクチャを伴うネットワーク内のコントローラであって、
非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体に結合され、コントローラルーティングツリーＴ´を判定するコントローラルーティングツリーモジュールとして動作可能なマイクロプロセッサ、を備え、
前記コントローラは、
Ｖを前記ネットワーク内のノードのセットとしＥを前記コントローラに向けて各スイッチを横断するノード間の双方向エッジのセットとし、Ｇ＝（Ｖ，Ｅ）として、Ｇ内の各スイッチから前記コントローラへの、それぞれＥのサブセットからなる全ての距離の候補をグラフ化し、
前記距離の候補の全てに基づいて、前記ネットワーク内の各スイッチについて前記コントローラへの最短パスを判定する、
ように動作可能であり、各スイッチから前記コントローラへの全ての前記最短パスは前記コントローラについての前記最短パスツリーＴを含み、
前記コントローラは、
非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に、前記最短パスツリーＴを記憶させ、
各スイッチについての前記コントローラへの前記最短パスに基づいて、Ｇ内の当該スイッチの全ての隣接ノードを、アップストリーム又はダウンストリームのいずれかとして指定し、
前記ネットワークトポロジー設計システムによって、Ｇ内の各スイッチのための重みを判定し及び割り当てるように、前記コントローラのネイバである１つ又は複数の前記スイッチで始まりＧ内の前記スイッチの全てが処理されるまで各直下ダウンストリームスイッチを横断し、
各スイッチの前記重みに基づいて、前記最短パスツリーＴを修正して、改善された自己修復性を伴う修正最短パスツリーＴ´を取得し、
非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に、前記修正最短パスツリーＴ´を記憶させる、
ように動作可能である、コントローラ。
【請求項１３】
前記コントローラルーティングツリーモジュールによる判定される通りの、前記最短パスツリーＴ´内の前記スイッチから前記コントローラへの前記パスに基づいて、アウトゴーイングプライマリリンクと、もしあればバックアップとして、前記スイッチから直上アップストリームスイッチへの少なくとも１つのアウトゴーイングセカンダリリンクとを、前記コントローラはスイッチへ通信し、当該スイッチは非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体に記憶させる、スイッチとの組合せにおける請求項１２のコントローラ。
【請求項１４】
前記スイッチは、アップストリームリンク又はノードにおける障害を検出し、前記スイッチにより、前記アウトゴーイングプライマリリンクを、もしあればバックアップとして供されるアウトゴーイングセカンダリリンクへ変更することにより、前記コントローラへの自身のルートを変更する、ように構成される、請求項１３のコントローラ及びスイッチの組合せ。
【請求項１５】
ネットワークトポロジー設計システムにより実装される方法であって、前記ネットワークトポロジー設計システムは、非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体に結合されてコントローラルーティングツリーモジュールとして動作可能なマイクロプロセッサを有するコントローラを含み、
前記方法は、ネットワークグラフＧにより表現されるスプリットアーキテクチャのネットワークの内部での使用のためのコントローラルーティングツリーＴ´を判定するためのものであり、
複数のスイッチにより実行されるデータプレーンコンポーネントから分離された前記コントローラにより、制御プレーンコンポーネントが実行され、
Ｖを前記ネットワーク内のノードのセットとしＥを前記コントローラに向けて各スイッチを横断するノード間の双方向エッジのセットとして、Ｇ＝（Ｖ，Ｅ）であり、
コントローラルーティングツリーＴ´は、各スイッチと前記コントローラとの間の負荷分散されない制御トラフィックのパスを表現し、
前記制御トラフィックは、各スイッチから前記コントローラへの双方向情報と、前記コントローラから当該スイッチへの転送決定情報とを表現し、
前記方法は、
前記ネットワークトポロジー設計システムにより、Ｇ内の各スイッチから前記コントローラへの全ての距離の候補をグラフ化するステップと、前記各距離はそれぞれＥのサブセットからなることと、
前記距離の候補の全てに基づいて、前記各スイッチについて前記コントローラへの最短パスを判定するステップと、各スイッチから前記コントローラへの前記最短パスの全ては前記コントローラについての前記最短パスツリーＴを含むことと、
非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に、前記最短パスツリーＴを記憶させるステップと、
各スイッチについての前記コントローラへの前記最短パスに基づいて、Ｇ内の当該スイッチの全ての隣接ノードを、アップストリーム又はダウンストリームのいずれかとして指定するステップと、
各スイッチと前記コントローラへの各パスに沿って横断される前記スイッチの各々との間の各リンクについてのエッジ重みパラメータを設定するステップと、
前記コントローラと前記スイッチとの間に１つよりも多くの同じ長さの最短パスが存在するかを判定するステップと、
前記コントローラと前記スイッチとの間に１つよりも多くの同じ長さの最短パスが存在しない場合に、当該最短パスを選択し及びそれを非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に記憶させるステップと、
前記スイッチから前記コントローラへの１つよりも多くの同じ長さの最短パスが存在する場合に、他の最短パスとの比較において最も高い自己修復性を有するパスを最短パスとして選択し、及び選択した当該最短パスを非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に記憶させるステップと、
を含む方法。
【請求項１６】
ベルマン−フォードアルゴリズムを用いて、初期の前記最短パスツリーを計算すること、をさらに含む、請求項１５の方法。
【請求項１７】
スプリットアーキテクチャを伴うネットワーク内のコントローラであって、
非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体に結合され、コントローラルーティングツリーＴ´を判定するコントローラルーティングツリーモジュールとして動作可能なマイクロプロセッサ、を備え、
前記コントローラは、
Ｖを前記ネットワーク内のノードのセットとしＥを前記コントローラに向けて各スイッチを横断するノード間の双方向エッジのセットとし、Ｇ＝（Ｖ，Ｅ）として、Ｇ内の各スイッチから前記コントローラへの、それぞれＥのサブセットからなる全ての距離の候補をグラフ化し、
前記距離の候補の全てに基づいて、前記ネットワーク内の各スイッチについて前記コントローラへの初期の最短パスを判定する、
ように動作可能であり、各スイッチから前記コントローラへの全ての前記最短パスは前記コントローラについての前記最短パスツリーＴを含み、
前記コントローラは、
非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に、前記最短パスツリーＴを記憶させ、
各スイッチについての前記コントローラへの前記最短パスに基づいて、Ｇ内の当該スイッチの全ての隣接ノードを、アップストリーム又はダウンストリームのいずれかとして指定し、
各スイッチと前記コントローラへの各パスに沿って横断される前記スイッチの各々との間の各リンクについてのエッジ重みパラメータを設定し、
前記コントローラと前記スイッチとの間に１つよりも多くの同じ長さの最短パスが存在するかを判定し、
前記コントローラと前記スイッチとの間に１つよりも多くの同じ長さの最短パスが存在しない場合に、当該最短パスを選択し及びそれを非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に記憶させ、
前記スイッチから前記コントローラへの１つよりも多くの同じ長さの最短パスが存在する場合に、他の最短パスとの比較において最も高い自己修復性を有するパスを最短パスとして選択し、
選択した当該最短パスを、非一時的なマシン読取可能な又はコンピュータ読取可能な前記記憶媒体に記憶させる、
ように動作可能である、コントローラ。
【請求項１８】
前記コントローラルーティングツリーモジュールによる判定される通りの、前記最短パスツリー内の前記スイッチから前記コントローラへの前記パスに基づいて、アウトゴーイングプライマリリンクと、もしあればバックアップとして、前記スイッチから直上アップストリームスイッチへの少なくとも１つのアウトゴーイングセカンダリリンクとを、前記コントローラはスイッチへ通信し、当該スイッチは非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体に記憶させる、スイッチとの組合せにおける請求項１７のコントローラ。
【請求項１９】
前記スイッチは、アップストリームリンク又はノードにおける障害を検出し、
前記スイッチにより、前記アウトゴーイングプライマリリンクを、もしあればバックアップとして供されるアウトゴーイングセカンダリリンクへ変更することにより、前記コントローラへの自身のルートを変更する、
ように構成される、請求項１８のコントローラ及びスイッチの組合せ。
【請求項２０】
初期の前記最短パスツリーは、ベルマン−フォードアルゴリズムを用いて計算される、請求項１７のコントローラ。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願への相互参照］
本出願は、２０１１年９月１９日に提出された正規の米国特許出願第１３／２３６，２９６号に関し、２０１１年７月２９日に提出された米国仮特許出願第６１／５１３，１４０号からの優先権を主張する。
【０００２】
［発明の分野］
本発明の実施形態は、ネットワークの運営及び設計に関する。具体的には、本発明の実施形態は、スプリットアーキテクチャネットワークにおいて制御トラフィックのルーティングツリーを計算し、生成し、実装し及び使用するための方法及びシステムに関する。ここで開示されるアルゴリズムには、距離及び自己修復（resilience）のファクタが算入される。本発明の目的は、短い距離と共に、ネットワークトポロジー内の各スイッチとコントローラとの間の接続における高い自己修復性を伴う、コントローラのルーティングツリーを形成することである。“エッジ”及び“リンク”との用語は、ここでは互換可能なように用いられ、ノードを相互接続するネットワークパスへ言及する。
【背景技術】
【０００３】
従来のネットワークアーキテクチャにおいて、転送プレーン及び制御プレーンの結合（coupling）が、制御パケット及びデータパケットの双方が同じリンク上で送信されるという点で存在し、よって、制御トラフィック及びデータトラフィックは障害発生時に同じように影響を受ける。簡潔に言えば、制御トラフィックは、ここでコントローラと呼ばれるネットワークエレメントとここでスイッチと呼ばれる転送エレメントとの間のトラフィックであり、コントローラは、データのフローがどのように処理され転送されるかを制御する。データトラフィックは、ネットワーク内の１つのノードから他のノードへの移送の対象となるデータペイロードである。本出願を通じて、転送エレメントは、スイッチとして言及される。しかしながら、スイッチとの用語の使用は、そうした転送エレメントをイーサネット又はレイヤ２スイッチに限定するものと解釈されるべきではない。
【０００４】
従来のネットワークアーキテクチャにおけるこの転送及び制御プレーンの結合は、通常、複雑すぎる制御プレーンと手間の掛かるネットワーク管理とをもたらす。欠点として、それは、新たなプロトコル及び技術を開発するにあたっての大きな負荷と高い障壁とを生み出すものとして知られている。ラインスピード、ポート密度及びパフォーマンスにおける急速な改善に関わらず、ネットワークの制御プレーンの仕組みは、転送プレーンの仕組みよりも非常に遅いペースで発展してきた。その引用した欠点を克服するために、ＯｐｅｎＦｌｏｗというスプリットアーキテクチャのプロトコルが開発されている。
【０００５】
スプリットアーキテクチャのネットワーク設計は、ネットワークの制御コンポーネントと転送コンポーネントとの間の分離を取り入れる。そうしたアーキテクチャのユースケースには、キャリアグレードネットワーク、エンタープライズネットワーク、ＩＳＰ（Internet  service  provider）ネットワーク、モバイルバックホールネットワーク、クラウドコンピューティング、マルチレイヤ（L3  &  L2  &  L1,  OTN,  WDM）サポートネットワーク及びデータセンタ、のアクセス／アグリゲーションドメインがあり、その全てはネットワークアーキテクチャの主な構成要素（building  blocks）である。従って、それらネットワークの適切な設計、管理、及びパフォーマンス最適化は、非常に重要である。
【０００６】
同じネットワークエレメント内に転送プレーン及び制御プレーンの双方を集積する従来のネットワークアーキテクチャとは異なり、スプリットアーキテクチャのネットワークは、それら２つのプレーンを切り離して、転送エレメントとは異なる物理的なロケーションに存在するであろうサーバ上で制御プレーンを実行する。ネットワークにおけるスプリットアーキテクチャの使用は、転送プレーンのスイッチの実装の簡略化を可能とし、複数のスイッチを監督するある数のコントローラへネットワークの知能部（intelligence）をシフトさせる。スプリットアーキテクチャのネットワークにおいて、（例えば、フローエンティティ、パケット、フレーム、セグメント、プロトコルデータユニットとして送信される）制御トラフィックを、（例えば、パケット、フレーム、セグメント、プロトコルデータユニットとして送信される）データトラフィックとは異なるパス上で、又は別個のネットワーク上ですら送信することができる。従って、これらネットワークにおける制御プレーンの信頼性は、転送プレーンのそれとはもはや直接的にはリンクしない。しかしながら、スイッチが自身のコントローラから切断（disconnect）される場合、スプリットアーキテクチャにおける制御プレーンと転送プレーンとの間の切断は転送プレーンを停止させかねないものであり、スイッチは、新たなフローをどう転送すべきかについての指示を受信できず、実際上オフラインになってしまう。
【０００７】
スプリットアーキテクチャのネットワークにおいて、コントローラは、スイッチから情報を収集し、適切な転送決定を計算してスイッチへ配信する。コントローラ及びスイッチは、情報を通信し及び交換するためのプロトコルを使用する。そうしたプロトコルの一例はＯｐｅｎＦｌｏｗであり（www.openflow.org参照）、ＯｐｅｎＦｌｏｗは、スイッチとコントローラとの間のオープンかつ標準的な通信方法を提供し、学術界及び産業界の双方から多大な興味を集めてきた。
【０００８】
図１は、スイッチ１０９とコントローラ１０１との間のＯｐｅｎＦｌｏｗインタフェースの概略を示す図１００である。スイッチ１０９は、ネットワークエレメント１０５のコンポーネントである。コントローラ１０１は、ＯｐｅｎＦｌｏｗプロトコルを用いて、セキュアチャネル１０３上でスイッチ１０９と通信する。ＯｐｅｎＦｌｏｗスイッチ内のフローあるいは転送テーブル１０７は、コントローラ１０１からのエントリで形成されており、図２から理解されるように、パケットヘッダ内のフィールドについてのマッチングを定義するルール２０１、フローマッチ２０４に関連付けられるアクション２０３、及びフロー２０６上の統計コレクション２０５、からなる。
【０００９】
インカミングのパケットが特定のルールに適合する場合、関連付けられるアクションがそのパケットに対して実行される。図２から理解されるように、ルール２０１は、例えばイーサネットＭＡＣアドレス、ＩＰアドレス、ＩＰプロトコル、ＴＣＰ／ＵＤＰポート番号に加えてインカミングポート番号といった、プロトコルスタック内の複数のヘッダからのキーフィールド２０２を含む。フローを定義するために、利用可能な全てのマッチングフィールドが使用されてよい。但し、望まれないフィールドについてはワイルドカードを使用することで、利用可能なフィールドのサブセットにマッチングルールを制限することも可能である。
【００１０】
スプリットアーキテクチャの分断された（de-coupled）制御プラットフォームは、ネットワーク制御ロジックを修正するタスクを簡易化し、開発者が幅広い多様な新たなプロトコルと管理アプリケーションとを構築することのできる、プログラムのインタフェースを提供する。このモデルにおいて、データプレーン及び制御プレーンは、独立的に進化し及びスケーリングすることができ、一方でデータプレーンのエレメントのコストは低減される。
【００１１】
リンク及びスイッチの障害がネットワークパフォーマンスに悪影響を与え得ることはよく知られている。例えば、数ミリ秒の障害は、高速エッジ上でテラバイト級のデータロスを容易にもたらし得る。ネットワークの自己修復性（resilience）の研究は、歴史的にはインバンド（in-band）制御モデルを前提としており、それは制御プレーンとデータプレーンとが同じ自己修復特性を有することを意味する。スプリットアーキテクチャのネットワークはアウトオブバンド（out-of-band）モデルを用いるものの、スイッチとして動作する各ネットワークエレメントへリンクによって単一のコントローラが直接的に結合されるとすれば、リンク障害及びスイッチ障害は依然として関心事である。そうしたネットワークでは、コントローラとスイッチとの間のリンクが障害を起こすと、スイッチは、自身の転送テーブルを更新できず、最終的に障害に陥る。
【００１２】
従来のネットワークにおいて、制御パケット及びデータパケットの双方は同じリンク上で送信され、障害が起こると制御情報及びデータ情報は同等に影響を受ける。スプリットアーキテクチャにおいて使用されると、スイッチをコントローラから切断した場合にスイッチが新たなフローをどのように転送すべきかの指示を受信できず実際上オフラインになるように、コントローラ及び転送プレーンの間の分断が転送プレーンを停止させる。
【００１３】
既存のスプリットアーキテクチャのネットワーク設計の提案及び予備的な実装において、各スイッチは、コントローラへ到達するためのパスを伴って予めプログラミングされる。リンク又はノードの障害時に、スイッチは、そうした障害を検出し当該スイッチ用の新たなパスを再計算するにあたって、コントローラに依存する。スイッチ又はリンク内のいかなる障害のコントローラによる検出も、例えばＨｅｌｌｏメッセージがコントローラによってスイッチから受信されないことなど、何らかの暗黙的な仕組みに基づかなければならない。これは、障害の正確な場所を検出しコントローラ−スイッチ間の接続を再確立するにあたって、ネットワーク内の大きな遅延をもたらす。あるスイッチについてバックアップパスを構成することができなければ、コントローラへのプライマリパスにおける障害の場合、スイッチからコントローラへの接続は遮断されることになる。
【００１４】
リンク障害は、制御トラフィック、データトラフィック又は双方を輸送するリンク上で生じ得るものであり、リンクを横断するトラフィックをもはや当該リンク上で移送することができないことを示す。障害は、２つのスイッチの間のリンクであるか、又は１つのコントローラとそこに接続されるスイッチとの間のリンクであり得る。多くの場合、それらリンクは独立的に障害を起こす。
【００１５】
スイッチ障害は、ネットワークエレメント又は転送エレメントがパケット又は他のプロトコルデータユニットを発信し、返送し又は転送することができないことを示す。スイッチ障害は、ソフトウェアバグ、ハードウェア障害、設定ミス及び同様の問題によって引き起こされ得る。多くの場合、これらスイッチは独立的に障害を起こす。
【００１６】
特殊な障害のケースは、スイッチとコントローラとの間の接続性喪失を含む。スイッチは、スイッチとコントローラとの間のパスに沿った中間的なリンク又はノード上の障害に起因して、自身のコントローラとの接続性を喪失し得る。スイッチが自身に割り当てられたコントローラと通信できなくなる都度、スイッチは、転送プレーン上のパスが未だ有効であったとしても、コントローラによって管理される転送プレーン上の全てのパケットを破棄するであろう。他の実施形態において、割り当てられたコントローラ又は他のコントローラとの接続が再確立されるまで、トラフィックのサブセットを転送プレーン上で転送することができ、又は、同様の限られた機能性を限られた時間量の間継続することができる。従って、これは、スイッチ障害の特殊ケースであると見なされることができる。
【００１７】
多くの部分について、コントローラ及びスイッチは、ＯＳＰＦ（Open  Shortest  Path  First）などのルーティングプロトコルを用いて、ノード間の距離を最小化するタスクを課せられる。ＯＳＰＦは、現在では最もポピュラーなゲートウェイ内ルーティングプロトコルである。ＯＳＰＦ（ＩＥＴＦ  ＲＦＣ２３２８参照）はリンクステート型プロトコルであり、ルータは、自身のネイバのリンクステート情報をルーティングドメイン内の全てのノードへブロードキャストする。この情報を用いて、あらゆるルータが、ドメイン内のネットワーク全体のトポロジーマップを構築する。各ルータは、ネットワーク全体のトポロジーを反映したリンクステートデータベースを維持する。このトポロジーマップ及びリンクコストメトリックに基づいて、ルータは、ダイクストラのアルゴリズムを用いて他の全てのルータへの最短パスを判定する。そして、その情報は、ＩＰパケットの転送のために使用されるルーティングテーブルを生成するために使用される。
【００１８】
最短パスルーティングプロトコルを用いる主要な欠点は、ネットワークの自己修復性又は保護が考慮されないことである。数ミリ秒の障害は高速リンク上でテラバイト級のデータロスを容易にもたらし得ることから、ネットワーク設計を評価する際、ネットワークの自己修復性は重要なファクタである。ここで使用されるように、自己修復性とは、故障（fault）及び通常の運用への問題（challenges）に直面した場合に許容可能なサービスのレベルを提供し及び維持する能力である。より自己修復性の大きいネットワークエレメント又は転送エレメントは、自己修復性の小さいネットワークエレメント又は転送エレメントよりも、故障及び通常の運用への問題から良好に保護される。ここで使用されるように、障害確率は、エンジニアリングされたシステム又はコンポーネントに障害が起こる頻度であり、時間単位の障害回数として表現され、又は長い時間において各ノードに障害が起こる確率である。
【発明の概要】
【００１９】
望まれるものは、自己修復性ファクタ又は保護ファクタに基づいてコントローラルーティングツリーを生成し、スイッチとコントローラとの間のバックアップリンクを提供する方法及び装置である。そうした望ましいコントローラルーティングツリーは、スイッチとコントローラとの間で通信される情報に基づいてコントローラにおいて生成され、スイッチとコントローラとの間でバックアップパスとして供されるように、スイッチにおいてセカンダリアウトゴーイングリンクを構成するために使用される。当該スイッチは、リンク又はノード障害を検出すると、スイッチからコントローラへのバックアップパスの選択がなされるように動作可能である。
【図面の簡単な説明】
【００２０】
本発明は、添付図面の図において限定ではなく例示の手段で図示され、その中で類似する参照は同様のエレメントを示す。本開示における“一”又は“１つの”実施形態への様々な言及は必ずしも同じ実施形態についてのものではなく、そうした参照は少なくとも１つを意味することに留意すべきである。さらに、特定の特徴、構造又は特性が一実施形態との関連で説明される際、明示的に説明されているかに関わらず、そうした特徴、構造又は特性を他の実施形態との関連で作用させることは、当業者の知識の範囲内であると考える。
【００２１】
【図１】簡易なＯｐｅｎＦｌｏｗネットワークの図である。
【図２】フローテーブルエントリの内容の図である。
【図３】ＯＳＰＦ（Open  Shortest  Path  First）アルゴリズムを用いて生成されるルーティングツリーを示すグラフである。
【図４】貪欲（greedy）ルーティングアルゴリズムを用いて生成されるルーティングツリーを示すグラフである。
【図５】本発明の第１のルーティングアルゴリズムの一実施形態のフローチャートである。
【図６】本発明の第２のルーティングアルゴリズムの一実施形態のフローチャートである。
【図７】本発明のＭＲルーティングアルゴリズムを実装するように構成可能なネットワークエレメントのブロック図である。
【図８】本発明のＲＡＳＰルーティングアルゴリズムを実装するように構成可能なネットワークエレメントのブロック図である。
【発明を実施するための形態】
【００２２】
以下の説明において、多くの特定の詳細が呈示される。しかしながら、それら特定の詳細が無くとも本発明の実施形態は実践され得ることが理解される。他の例において、よく知られた回路、構造及び技法は、本説明の理解を曖昧にしないために、詳細には示されていない。しかしながら、そうした特定の詳細が無くとも本発明は実践され得ることが、当業者には理解されるであろう。過剰な実験をせずとも、包含した説明があれば、当業者は適切な機能性を実装することができるであろう。
【００２３】
図中に示す技法及び請求されるネットワークトポロジー設計システムは、１つ以上の電子デバイス（例えば、端局、ネットワークエレメント、サーバ又は同様の電子デバイス）上で記憶され及び実行されるコード、命令及びデータを用いて実装されることができる。そうした電子デバイスは、非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体（例えば、磁気ディスク、光学ディスク、ランダムアクセスメモリ、リードオンリメモリ、フラッシュメモリデバイス及び相変化メモリ）などの、非一時的なマシン読取可能な又はコンピュータ読取可能な媒体を用いて、コード及びデータを記憶し及び（内部的に、及び／又はネットワーク上で他の電子デバイスとの間で）通信する。加えて、そうした電子デバイスは、典型的には、１つ以上の記憶デバイス、ユーザ入出力デバイス（例えば、キーボード、タッチスクリーン及び／又はディスプレイ）並びにネットワーク接続などの、１つ以上の他のコンポーネントと結合される、１つ以上のマイクロプロセッサのセットを含む。マイクロプロセッサのセットと他のコンポーネントとの間の結合は、典型的には、１つ以上のバス及びブリッジ（バスコントローラともいう）を通じてなされる。ネットワークトポロジー設計システム内の記憶デバイスは、１つ以上の非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体及び非一時的なマシン読取可能な又はコンピュータ読取可能な通信媒体を表現する。よって、所与の電子デバイス又はネットワークトポロジー設計システムの非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体は、典型的には、電子デバイスの１つ以上のプロセッサのセット上での実行のための、コード、命令及び／又はデータを記憶する。当然ながら、本発明の一実施形態の１つ以上の部分が、ソフトウェア、ファームウェア及び／又はハードウェアの異なる組合せを用いて実装されてもよい。
【００２４】
ここで使用されるように、ネットワークエレメント又は転送エレメント（例えば、ルータ、スイッチ、ブリッジ又は同様のネットワーキングデバイス）は、ネットワーク上の他の機器（例えば、他のネットワークエレメント、端局又は同様のネットワーキングデバイス）と通信可能に相互接続するハードウェア及びソフトウェアを含む１つのネットワーキング機器である。いくつかのネットワークエレメントは、マルチネットワーキング機能（例えば、ルーティング、ブリッジング、スイッチング、レイヤ２統合、セッションボーダ制御、マルチキャスティング、及び／若しくは加入者管理）についてのサポートを提供し、並びに／又は、マルチアプリケーションサービス（例えば、データ収集）についてのサポートを提供する、“マルチサービスネットワークエレメント”である。
【００２５】
本発明は、コントローラとスイッチとの間の通信のためのコントローラルーティングツリーを構築するための開示されるアルゴリズムの１つを用いて、コントローラ及び複数のスイッチを有するスプリットアーキテクチャシステムにおいて制御トラフィックをルーティングするためのコントローラルーティングツリーを判定するための方法及び装置を含む。スプリットアーキテクチャシステムにおける使用のために提案された従来のルーティングアルゴリズムがスイッチとコントローラとの間の距離を最小化する目的を有するのみであるのに対し、本発明は、距離及び自己修復性ファクタの双方を考慮する。
【００２６】
より具体的には、本発明は、コントローラルーティングツリーを判定するための開示されるアルゴリズムの１つをコントローラによって使用し、そして、コントローラルーティングツリーはスプリットアーキテクチャシステムのスイッチへ通信される。コントローラルーティングツリーは、各スイッチとコントローラとの間の負荷分散されない（non-load  balanced）制御トラフィックのパスを表現し、制御トラフィックは各スイッチからコントローラへの双方向情報（bi-directional  information）と、コントローラからスイッチへの転送決定情報（forwarding  decision  information）とを表現する。コントローラは、スイッチと同じ物理ネットワーク内にあってもよい。即ち、制御プレーン及び転送プレーンを接続するために別個の基盤（infrastructure）を用いるのとは反対に、ネットワーク内の全てのスイッチにコントローラを接続するために、既存のスプリットアーキテクチャのネットワーク（既存のリンク及びスイッチ）が使用される。他の実施形態において、通信又はその任意の組合せのために、別個のネットワーク基盤が使用される。各アルゴリズムは、自己修復性及び距離の観点で異なる目的を有する。本発明の目的は、スイッチ群及びコントローラの間の接続における自己修復性と距離との所望の組合せを有するコントローラルーティングツリーの生成である。
【００２７】
本発明は、出願人の同時係属中の正規の米国特許出願第１３／２３６，２９６号とは、当該同時係属中の出願において開示される発明がコントローラの配置を対象とし最短パスツリールーティングの使用を前提としている点で異なる。本発明は、コントローラの位置が固定されている場合の、開示されるアルゴリズムを用いたコントローラルーティングツリーの判定を対象とする。
【００２８】
本発明は、同時係属中の正規の米国特許出願第１３／２３６，２９６号における本出願人の発明を拡張するものであり、その発明は、スプリットアーキテクチャ領域のコントローラを、当該領域内のコントローラとスイッチとの間の接続の自己修復性を最適化するように選択される位置に配置する。当該同時係属中の出願においてそうであるように、スプリットアーキテクチャ領域のパーティショニングがどのようになされるかについての前提は無い。パーティショニングは、もし行われるならば、地理的制約などのいかなる任意のメトリックに基づくこともできる。
【００２９】
さらに、出願人の同時係属中の正規の米国特許出願第１３／２３６，２９６号において、出願人は各スイッチにおけるバックアップパスの事前構成を開示しており、それにより、直上アップストリームノード（immediate  upstream  node）へのプライマリアウトゴーイングリンクが適切に作動しなければ、セカンダリアウトゴーイングリンクがバックアップパスとして使用され得る。そうした保護スキームによって、スイッチは、自身のアウトゴーイングリンク又は自身の直上アップストリームノードにおける障害を検出した場合に、自身のコントローラへのルートを即座に変更して、バックアップパス、即ち、スイッチ内に事前にプログラミングされたアウトゴーイングインタフェースを使用して、コントローラに再接続する。これは、コントローラの関与の必要性なく行われ、ネットワーク内のルートの残りへの及びコントローラへのダウンストリームノードの接続へのいかなる影響も無い。言い換えれば、影響のあるスイッチのアウトゴーイングインタフェースにおける局所的な変更のみがあることになる。ネットワーク内の他の全ての接続は、そのまま維持されるであろう。バックアップパスが存在しなければ、スイッチからコントローラへの間の接続は、コントローラへのプライマリパスにおける障害のケースで遮断されることになる。
【００３０】
スプリットアーキテクチャにおいてトラフィックを制御するために使用されるコントローラルーティングツリーを判定するための選択されるルーティングアルゴリズムは、コントローラとスイッチとの間の接続の自己修復性に有意なインパクトを与える。図３及び図４を参照しながら、自己修復性を例示することができる。コントローラとしてのノード３０８を有する図３において見られる通り、最短パスベースのツリーは、ここでさらに定義されるように、３つの未保護ノード（unprotected  node）３０１、３１０及び３０５を有する。貪欲ツリーアルゴリズムを用いる図４の改善されたルーティングツリーは、２つの未保護ノード３０３及び３０７を有する。理解され得るように、自己修復性を最大化することが目的であれば、図３に見られるような最短パスツリーは必ずしもコントローラルーティングツリーとしての最良の選択ではない。
【００３１】
スプリットアーキテクチャシステムでは、より自己修復性の高いネットワークは、バックアップパスを伴うより多くのスイッチを有することになり、最も自己修復性の高いネットワークは、あらゆるスイッチがコントローラへの事前構成されるバックアップパスを有するようなネットワークである。自己修復又は保護メトリックを、次のように記述することができる：Ｖをネットワーク内のノードのセットとし、Ｅをノード間の双方向リンクのセットとして、グラフＧ＝（Ｖ，Ｅ）でネットワークを表記する。コストは、ネットワーク内の各リンクに関連付けられる。割り当てられるリンクコストに基づいて、ネットワーク内の任意の２つのノード間で最短パスルートが計算される。各リンク上のコストは、当該リンクの双方の方向に適用されるものとする。この所与のトポロジーと共に、ノードの１つはコントローラであってノードの残りはスイッチであるものとする。また、スイッチ群及びコントローラの間で送信される制御トラフィックについて負荷分散は行われないものとする。従って、各ノードはコントローラへ到達するための１つのパスのみを有する。言い換えれば、制御トラフィックは、コントローラノードをルートとするツリー上で、コントローラとの間で送信される。このノードは、コントローラルーティングツリーと呼ばれる。このコントローラルーティングツリーは、ネットワーク内の全てのノードをカバーし、リンク群のサブセットである。さらに、コントローラ及びスイッチ群の間で、双方向での通信のために、同じルーティングツリーが使用されることになるものとする。
【００３２】
ネットワークの内部に所与の固定されたコントローラ位置があれば、様々なルーティングアルゴリズムを用いて様々なルーティングツリーを形成することができ、それによって各ノードはコントローラへ制御トラフィックを送信する。コントローラルーティングツリーＴにおいて、ノードｖからノードｕへコントローラに向かうパスがＴ内にあるならば、ノードｕはノードｖのアップストリームノードである。ノードｕからノードｖへコントローラに向かうパスがＴ内にあるならば、ノードｕはノードｖのダウンストリームノードと呼ばれる。コントローラルーティングツリーにおいて、ノードの親とはその直上のアップストリームノードであり、ノードの子とはその直下のダウンストリームノードであり、アップストリーム及びダウンストリームは、初期のコントローラルーティングツリーが生成された後に判定される。
【００３３】
所与の固定されたコントローラ位置とコントローラルーティングツリーＴとがあるものとして、ノードａ及びその直上のアップストリームノードｂを考慮されたい。ｃ∈Ｖ｜｛ａ，ｂ｝であるノードｃ、つまりノードａ及びｂを除いたＶの要素であるノードｃが存在し、以下の条件が満たされる場合、ノードａはそのアウトゴーイングリンク（ａ，ｂ）の障害に対して保護される：
条件１：リンク（ａ，ｃ）がＧ内にある（即ち、ノードａ及びｃの間のリンクがネットワーク内に存在する）。
条件２：ノードｃはＴにおいてノードａのダウンストリームノードではない。
第２の条件は、ノードａをノードｃに接続する結果としてループが生じないことを保証する。
【００３４】
上の条件が満たされる場合、リンク（ａ，ｃ）をリンク（ａ，ｂ）のためのバックアップリンクとして割り当てることができ、このバックアップリンクをコントローラにおいて生成して通信し、ノードａにおいて事前構成することができる。ノードａは、リンク（ａ，ｂ）における障害を検出するや否や、プライマリアウトゴーイングリンク（ａ，ｂ）をセカンダリアウトゴーイングリンク（ａ，ｃ）へ変更することにより、コントローラへの自身のルートを即座に変更するであろう。
【００３５】
ノードｃが上の２つの条件に加えて第３の条件を充足する場合、ノードａは直上のアップストリームノードの障害に対しても保護される：
条件３：ノードｃはＴにおいてノードｂのダウンストリームノードではない。
第３の条件は、障害を起こしたと想定されるノードｂをノードｃのコントローラへ向かう制御トラフィックが通過しないことを保証する。あらためて言うと、ノードａは、ノードｂにおける障害を検出するや否や、自身のアウトゴーイングリンクを（ａ，ｂ）から（ａ，ｃ）へ切り替える。
【００３６】
ネットワークにおいてノード障害に対してリンク障害がどれだけ重大であり又は頻繁であるかに依存して、ネットワークの運用者は、例えばノード障害にはコストα、リンク障害にはコストβなどのように、これら２つの種類の障害に異なるコストを割り当てることができる。例えば、α＝βは、リンク障害及びノード障害が同等に起こり得るか双方の種類の障害に対してネットワークを保護することが同等に重要である場合のシナリオとして解釈され、そのために使用される。この手法で、ノードが全く保護されない場合、ノードにおける保護無しのコストはａ＋ｂ、アウトゴーイングリンク障害に対してのみ保護される場合にはα、アップストリームノード障害に対しても保護される場合にはゼロと評価され得る。当然ながら、コントローラに直接的に接続されるスイッチについては、直上のアップストリームノードがコントローラであるために、アップストリームノードの保護は定義されない。よって、コントローラに直接的に接続されるノードについては、割り当てコストは、アウトゴーイングリンク障害に対して保護されるならばゼロであり、そうでなければα＋βである。
【００３７】
よって、本発明は、例えばコントローラにおいてスプリットアーキテクチャネットワークの内部での使用のためのコントローラルーティングツリーＴ´を判定するように動作可能なネットワークトポロジー設計システムにより実装される方法であって、ネットワークトポロジー設計システムにより、Ｖ内のノードの１つがＧのためのコントローラとして設定され、ネットワークトポロジー設計システムにより、ノードの残りがスイッチとして設定される。そして、ネットワークトポロジー設計システムは、各スイッチからコントローラへの全ての距離の候補（possible  distances）をグラフ化し、当該距離の候補の全てをフィルタリングして、当該各スイッチについてコントローラへの最短パスを判定し、各スイッチからコントローラへの蓄積された最短パスが当該コントローラについての最短パスツリーＴとなる。最短パスツリーは、非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体に記憶される。各スイッチについてのコントローラへの最短パスに基づいて、当該スイッチの全ての隣接ノード（immediate  neighbor  nodes）が、アップストリーム又はダウンストリームのいずれかとして指定される。そして、コントローラのネイバ（neighbor）である１つ又は複数のスイッチで始まり各直下ダウンストリームスイッチを横断してＧ内のスイッチの全てが処理されるまで、ネットワークトポロジー設計システムは、各スイッチのための重みを判定し及び割り当てる。各スイッチの重みに基づいて、最短パスツリーＴは修正され、改善された自己修復性を伴う修正最短パスツリー（modified  shortest-path  tree）Ｔ´が取得されて、非一時的なマシン読取可能な又はコンピュータ読取可能な記憶媒体に記憶される。そして、もしあるならばバックアップパスを含むパスは、コントローラから関係する各スイッチへ通信される。コントローラとスイッチとの間のリンク又はノード障害が起こると、当該スイッチは、自身のアウトゴーイングリンクを、プライマリアウトゴーイングリンクからセカンダリアウトゴーイングリンクへと動かすことができる。
【００３８】
ノードによって自身のダウンストリームノードへ障害を通知するための拡張されたシグナリングの仕組みが存在しないことを意味するような、従来型の管理ツールがスプリットアーキテクチャのネットワークに配備される場合、コントローラからスイッチが切断されると、即ちスイッチ内にバックアップパスがプログラミングされていなければ、当該ダウンストリームノードがそれらのアウトゴーイングリンク又は直上のアップストリームノードにおける障害から局所的には保護されているとしても、それらダウンストリームノードもまた切断されるであろう。これは、最終的なネットワークの自己修復性において、代替的なリンクの度合い（extent）に基づいてノードに重みを提供することに加えて、よりコントローラに近いノードへより多くの重みが割り当てられるべきであることを意味する。コントローラはコントローラルーティングツリーのルートであることを想起されたい。より正確には、各ノードの重みは、そのダウンストリームノードの数に比例すべきである。
【００３９】
よって、ノードの重みは、当該ノードの保護ステータスに関連付けられるコストファクタによりスケーリングされる、そのダウンストリームノードの数に基づき、ノードがそのアウトゴーイングリンク及びその直上アップストリームノードの障害の双方に対して保護されるならばゼロ、ノードがそのアウトゴーイングリンクの障害に対してのみ保護されるならばα、それ以外ならばα＋βである。
【００４０】
さらに、ルーティングツリーの重みを、その全てのノードの重みの合計として定義することができる。この重みは、ネットワークの“非保護度（unprotectability）”を定量化するために使用される。所与のルーティングツリーＴについて、この重みはΓ（Ｔ）と表される。
【００４１】
本発明の目的は、高度なネットワークの保護を提供することである。よって、一実施形態において望まれるのは、重みを最小化するルーティングアルゴリズムの特性であり、それはネットワーク内の障害のケースでコントローラからノードが切断される可能性が最小化されることを意味する。
【００４２】
ここで開示される２つのアルゴリズム（ＭＲ，ＲＡＳＰ）のいずれか１つを、その目的に依存して、スプリットアーキテクチャシステム内の制御トラフィックのためのルーティングツリーを構築するために本発明において使用することができる。ＭＲアルゴリズムでは、それが最短パスツリーのセットのみに制限されないために、コントローラルーティングツリーが高い自己修復性を有することになるが、最短パスツリーは提供されない。ＲＡＳＰアルゴリズムは、コントローラとスイッチとの間で最短プライマリパスが望ましい場合に代替的なアルゴリズムとして使用され得る。ＭＲアルゴリズムとＲＡＳＰアルゴリズムとを比較すると、ＭＲアルゴリズムは、それ自体最短パスツリーのセットのみに制限されないために、ＲＡＳＰアルゴリズムと比較してより良好な自己修復性をもたらす。一方、ＲＡＳＰアルゴリズムはスイッチ群及びコントローラの間のより短いパスをもたらす。
【００４３】
本発明において使用される第１のアルゴリズムは、ネットワーク内の最大の自己修復性を提供するコントローラルーティングツリーを発見するための近似アルゴリズムである。当該アルゴリズムを、ここでは最大自己修復性（ＭＲ：Maximum  Resilience）アルゴリズムという。ここで説明されるように、保護を最大化する最適なツリーの計算は、ＮＰ困難な問題である。従って、ヒューリスティックＭＲアルゴリズムが近似的なアルゴリズムであり、それは、ある最短パスツリーを開始点として選択して、自己修復性を改善するために当該ツリーを修正する。ＭＲアルゴリズムの出力は必ずしも最短パスツリーではなく、但し初期ツリーと比較してより高い自己修復性が提供される。
【００４４】
所与のコントローラ位置について、ＭＲアルゴリズムを参照すると、Γ（Ｔ）を最小化する１つである、ネットワークの保護を最大化する最良のルーティングツリーを発見することは、ＮＰ困難な問題であると示すことができ、それは全ての候補のうち最良なツリーを発見するための多項式時間（polynomial-time）アルゴリズムが知られていないことを意味する。従って、準最適な解のために近似アルゴリズムを使用しなければならない。
【００４５】
ネットワーク内でリンク又はノード障害の可能性が無いとすると、ルーティングのためにプライマリパスのみが必要とされ、その状況では、最短パスツリーが最良のパフォーマンスを提供する。しかしながら、障害の可能性は常に存在するため、望まれるのは、保護を改善したルーティングアルゴリズムのポリシーである。ＭＲアルゴリズムは、コントローラルーティングツリーを作り上げるためのヒューリスティックアルゴリズムであり、最短パスツリーから開始して、ネットワークに自己修復性を提供するルーティングツリーへ収束する。複数回の繰り返しにわたって、ＭＲアルゴリズムは、さらなる改善が見込まれなくなるまで、コントローラルーティングツリーのエッジを変更することにより、自己修復性を改善する。ＭＲアルゴリズムを用いて構築されたコントローラルーティングツリーは、表１において提供された疑似コードの中で、Max_Resilience_RTとして言及されている。
【００４６】
このＭＲアルゴリズムは、図５のフローチャートとの関連において説明される。アルゴリズムを実行する前に、Ｇ内で、コントローラの機能性を有するノードがコントローラとして割り当てられ、他のノードがスイッチとして割り当てられる。ＭＲアルゴリズムは、スプリットアーキテクチャのネットワークのトポロジーグラフＧのトポロジーグラフ化モジュールからの受信に応じて、ネットワークトポロジー設計システム内のコントローラルーティングツリーモジュールにより開始される（ブロック５０１）。処理は、グラフ内のスイッチの各々を通じた繰り返しを開始する（ブロック５０２）。
【００４７】
グラフ内の各スイッチについて、コントローラルーティングツリーは、ツリーのルートとして供されるコントローラで生成される（ブロック５０２）。そして、それらコントローラルーティングツリーの各々について、コントローラのネイバのスイッチから始まってそれらツリー内のスイッチが横断される（ブロック５０３）。各ノードは、コントローラからの距離に基づく初期重みを与えられる。それは、総ルーティングツリー重みの計算のための重みとして供される。各ルーティングツリー内の各スイッチについて、いくつかのアウトゴーイングパスの、その直上のアップストリームネイバからコントローラへの距離を判定することにより、スイッチについての保護又は自己修復性の判定が行われる（ブロック５０５，５０６）。
【００４８】
アルゴリズムの進行中に各スイッチを検査する反復処理を通じて、検査対象のスイッチのアップストリームの各スイッチもまた、当該アップストリームスイッチが複数のアウトゴーイングエッジを有し、よって単一の又はより少ないアウトゴーイングエッジを有するスイッチよりも自己修復性が高いかを判定するために検査される。このアルゴリズムは、グラフ内のノードの全てが横断され検査されるまで実行される（ブロック５０７）。当該スイッチのためのプライマリアウトゴーイングリンクとして、直上のアップストリームにあってより高い自己修復性を有するスイッチが選択される（ブロック５０８）。そのプライマリアウトゴーイングリンク上でノード又はリンク障害が検出されると、スイッチは、セカンダリアウトゴーイングリンクへの変更を行うであろう（ブロック５０９）。
【００４９】
ＭＲアルゴリズムを実装する疑似コードが表１に呈示されている：
【００５０】
【表１】
2014526189.tif 000003
【００５１】
表１において見られるように、v.distanceは、Ｔ内のノードｖとコントローラとの間のエッジの数を意味する距離である。ＭＲアルゴリズムは、コントローラのネイバで開始し、そのいずれかに別のアップストリームノードを割当てることにより何らかの改善を達成することができるかを判定する。これは、ネットワーク内の他の全てのノードをチェックすることにより継続される。なお、ＭＲアルゴリズムの各繰り返しにおいて、アルゴリズムはコントローラから１ステップ離れて動くために、ルーティングツリー内でループは形成されない。
【００５２】
ＭＲアルゴリズムの利点は、それが自己修復性の最適化のための局所最適解を提供することである。但し、一方で、その利点は、表１の第１０行における更新がより長いパスをもたらし得るという、それほど重大ではないトレードオフを有する。従って、最終的なルーティングツリーは、最短パスツリーではないかもしれない。
【００５３】
本発明において使用される第２のアルゴリズムは、自己修復性認識型の（resilience-aware）最短パスルーティングアルゴリズムである。当該アルゴリズムを、ここでは自己修復性認識型最短パス（ＲＡＳＰ）アルゴリズムという。ＲＡＳＰアルゴリズムは、最短パスツリーを構築する目的を有するものの、複数の同じ長さの最短パスツリーが存在する場合には、当該アルゴリズムは、他の最短パスツリーとの比較においてどの最短パスツリーが最も高い自己修復性を有するかを判定する。ＲＡＳＰアルゴリズムは、まず、従来のベルマン−フォードアルゴリズムを用いて、全ての最短パスツリーの候補を判定する。最終的なコントローラルーティングツリーへの収束化において、当該アルゴリズムは、複数の同じ長さの最短パスツリーが存在する場合に自己修復性ファクタを算入し、より高い自己修復性を提供するコントローラルーティングツリーを優遇する。
【００５４】
ＲＡＳＰアルゴリズムは、他の最短パスツリーの候補と比較して、改善されたネットワーク自己修復性を伴う最短パスツリーを提供する。ＲＡＳＰアルゴリズムは、しかしながら、自己修復性において最適なネットワークを必ずしももたらさない。
【００５５】
ＲＡＳＰアルゴリズムを実行する前に、Ｇ内で、コントローラの機能性を有するノードがコントローラとして割り当てられ、他のノードがスイッチとして割り当てられる。図６のフローチャートにおいて見られるように、ＲＡＳＰアルゴリズムは、最初にベルマン−フォードアルゴリズムを用いて初期ルーティングツリーを取得し、そして当該コントローラルーティングツリーを反復的に修正する。ＲＡＳＰアルゴリズムは、スプリットアーキテクチャのネットワークのトポロジーグラフのトポロジーグラフ化モジュールからの受信に応じて、コントローラルーティングツリーモジュールにより開始される（ブロック６０１）。そして、例えばベルマン−フォードアルゴリズムに基づいて、各スイッチについて最短パスツリーが生成される（ブロック６０２及び６０３）。ＲＡＳＰアルゴリズムは、コントローラへの同じ長さの複数のパスが存在するかを判定する（ブロック６０４）。コントローラへの各スイッチからの単一の最短パスが存在することを意味するような、ＮＯの場合、ＲＡＳＰアルゴリズムは、コントローラルーティングツリーの構築における使用のために、当該最短パスを選択する（ブロック６０５）。複数の同じ長さの最短パスが存在する場合、ＲＡＳＰアルゴリズムは、コントローラルーティングツリーのための各パスとして、より高い自己修復性を有する最短パスを選択する（ブロック６０６〜６０８）。
【００５６】
どの最短パスコントローラルーティングツリーがより高い自己修復性を有するかを判定するために、コントローラのネイバのスイッチを起点にスイッチ群が横断される（ブロック６０６）。各ルーティングツリー内の各スイッチについて、スイッチについての保護又は自己修復性の判定は、いくつかのアウトゴーイングパスの直上のアップストリームネイバからコントローラへの距離を算定（review）することにより行われる（ブロック６０７）。各ノードには、あるアウトゴーイングパス重み（等級）が与えられる。
【００５７】
アルゴリズムの進行中に各スイッチを検査する反復処理を通じて、より自己修復的なパスが含まれるように、全てのスイッチが検査され、その全てのアップストリームスイッチが複数のアウトゴーイングリンク（エッジ）を有する度合いが判定される。当該より自己修復的なパス上のスイッチはコントローラへのプライマリリンクとして選択され、バックアップリンクが当該スイッチにおいてバックアップリンクとして記憶される（ブロック６０９）。コントローラへのプライマリパス上のスイッチとコントローラとの間でノード又はリンク障害があると、スイッチは、プライマリアウトゴーイングリンクをセカンダリアウトゴーイングリンクへ変更する（ブロック６１０）。
【００５８】
ＲＡＳＰアルゴリズムを実装する疑似コードが表２に呈示されている：
【００５９】
【表２】
2014526189.tif 000004
【００６０】
表２において見られるように、v.distanceはノードｖとコントローラとの間のパスの長さであり、v.parentはコントローラへのパスに沿ったｖの親ノードであり、edge(u,v)はノードｕとノードｖとの間のエッジの重みである。通常のケースでは、edge(u,v)＝１である。グラフＧ内のノードの総数は、ｎにより表される。ＲＡＳＰアルゴリズムは、まず、第２行から第９行において見られるように、各ノードについて距離と親とを初期化する。そして、当該アルゴリズムは、ｎ回の反復を行う。反復が行われる都度、第１５行において見られるように、各ノードｕについて、当該ノードをそのネイバｖへ接続することで距離の改善が見込まれるかのチェックが行われる。改善が見込まれる場合、ＲＡＳＰアルゴリズムは、第１８行及び第１９行において見られるように、当該ノードの親及び距離を更新する。なお、当該アルゴリズムは、v.childrenにより表される各ノードｖの子という、新たなデータ構造を追加することにより修正される。各繰り返しにおいて、親及び距離フィールドに加えて、当該アルゴリズムは、子フィールドも更新する。自己修復性を改善するために、同じ距離を伴う（即ち、同点（tie）となる）全ての親の候補について、最高の自己修復性を伴うパスが選択される。ノードがより多くのエッジを有し、選択されるルーティングツリー内にそのわずかしか無ければ、そのノードは、より強く保護される−即ち、より高い自己修復性を有する−ものと推定される。この情報は、表２の第２０行に示したように、距離に符号化される。親の距離は、その実際の長さと比較して、1/v.distanceだけ増加される。なお、1/v.distanceは常に１よりも小さいため、v.distanceが何回増加されるとしても、増分の総量は常に１よりも小さくなる。ノードのネイバのうち少なくとも１つは恐らくは親となることから、１ホップ分長いパスを有する他のノードｖ´が存在するとすれば、それはｖの距離に全ての人為的な増分を加えたものよりも、依然として長いであろう。従って、導出されるルーティングツリーは、依然として最短パスツリーであるが、等距離のパスの間で同点となれば、選択されるルーティングツリーは、最も自己修復性の高いパスを伴うものとなる。
【００６１】
図７は、ネットワークに結合されるコントローラ内の設計システムのＭＲの実施形態の図である。同図は、ネットワーク設計システムツールを実行するための一例としてのネットワーク設計システム７０１の図解を提供する。ネットワーク設計システム７０１は、少なくとも１つの非一時的なコンピュータ読取可能なメモリ７０２を含み、メモリ７０２は、少なくとも１つのマイクロプロセッサ７０３により実行される命令を記憶し、マイクロプロセッサ７０３は、ネットワーク設計システムツールのコンポーネントの実行を協調させ、それらコンポーネントは、トポロジーグラフ化モジュール７０５、コントローラルーティングツリーモジュール７０７、及び類似のコンポーネントを含む。他の実施形態において、これらモジュールのいずれか又は全ては、ハードウェアモジュール又はデバイスのセットとして実装され得る。マイクロプロセッサ７０３は、スプリットアーキテクチャのネットワークと通信し及び／又はそれを管理するネットワーク管理モジュール７０９をも実行し得る。
【００６２】
トポロジーグラフ化モジュール７０５は、ネットワークのトポロジーをグラフ表現（representative  graph）に変換し、コントローラルーティングツリーモジュール７０７をサポートするグラフ表現を対象として、グラフ化機能を実行することができる。コントローラルーティングツリーモジュール７０７は、トポロジーグラフ化モジュール７０５により生成されたグラフを対象として動作し、ＭＲアルゴリズムに従ってコントローラルーティングツリーを実装するように、そのグラフ化動作を導く。
【００６３】
ネットワーク管理モジュール７０９は、自動化された処理のためのネットワークトポロジーを発見し及び／又は自動化された処理でルーティングツリーアルゴリズムを実装するために、コントローラルーティングツリーモジュール７０７及び／又はトポロジーグラフ化モジュール７０５と通信することができる。
【００６４】
図示されたスプリットアーキテクチャのネットワークは、ＭＲ又はＲＡＳＰアルゴリズムのいずれかを伴う例示的な実装である。その例において、スイッチ７１７から構成されるドメイン又はスプリットアーキテクチャ領域、を制御するためのコントローラ７１５が存在する。スイッチ７１７は、ＭＲコントローラルーティングツリーを用いて、コントローラ７１５により管理される。
【００６５】
図８は、スイッチ８１７のネットワークに結合されるコントローラ８１５内の設計システムのＲＡＳＰの実施形態の図である。スイッチ８１７の配置及びコントローラ８１５のコンポーネントは図７のそれらに同じように対応し、但し、コントローラルーティングツリーモジュール８０７は、トポロジーグラフ化モジュール８０５により生成されたグラフを対象として動作し、ＲＡＳＰアルゴリズムに従ってコントローラルーティングツリーを実装するように、そのグラフ化動作を導く。
【００６６】
ＭＲ又はＲＡＳＰアルゴリズムのいずれかによって判定される通りにコントローラルーティングツリーを実装した後、スイッチは、そのアウトゴーイングリンク又は直上のアップストリームノードにおける障害を検出すると、コントローラへの自身のルートを変更し、バックアップパス、即ちコントローラへ再接続するためにスイッチ内で事前にプログラミングされたアウトゴーイングインタフェース、を用いる。これは、コントローラの関与の必要性なく行われ、ネットワーク内のルートの残りへの及びコントローラへのダウンストリームノードの接続へのいかなる影響も無い。言い換えれば、影響のあるスイッチのアウトゴーイングインタフェースにおける局所的な変更のみがあることになる。ネットワーク内の他の全ての接続は、そのまま維持されるであろう。
【００６７】
上述した説明は例示的であって限定的ではないものと意図されることが理解されるべきである。上述した説明を読んで理解すれば、当業者には、他の多くの実施形態が明らかとなる。本発明の範囲は、従って、添付の請求項を参照することで、それら請求項に与えられるものと均等な全ての範囲と共に決定される。
【図１】
2014526189.tif 000005
【図２】
2014526189.tif 000006
【図３】
2014526189.tif 000007
【図４】
2014526189.tif 000008
【図５】
2014526189.tif 000009
【図６】
2014526189.tif 000010
【図７】
2014526189.tif 000011
【図８】
2014526189.tif 000012
【国際調査報告】
2014526189.tif 000013
2014526189.tif 000014
2014526189.tif 000015