(57)【要約】  一般化概有向非巡回グラフ（ＧＡＤＡＧ）を計算し、配信する方法およびシステムが開示される。本方法は、ネットワークエレメントにより、ネットワークのＧＡＤＡＧを計算することを含み、ＧＡＤＡＧはネットワークのグラフ抽象化であり、複数のネットワークエレメントはＧＡＤＡＧの頂点でありかつ複数のネットワークエレメントを接続するリンクはＧＡＤＡＧの有向辺である。本方法は、続いて、計算されたＧＡＤＡＧに基づいてＧＡＤＡＧ記述子をアセンブルし、ＧＡＤＡＧ記述子を複数のネットワークエレメントに配信することへ進み、複数のネットワークエレメントの各々はＧＡＤＡＧ記述子を利用して、トラフィックを転送するための最大冗長木を計算する。本方法はまた、レイヤ２デプロイメントにレイヤ２の属性および特徴を活用することと、トポロジ変更イベントの際に、トラフィック停止を回避または最小限に抑えるように冗長木を更新することとを含む。【選択図】図１１
2017510137.tif 000002
【特許請求の範囲】
【請求項１】
パス計算要素（ＰＣＥ）の機能を実装するネットワークエレメントにおいて実装される、最大冗長木をデプロイするための方法であって、ネットワークには複数のネットワークエレメントが含まれており、
前記ネットワークエレメントにより、前記ネットワークの一般化概有向非巡回グラフ（ＧＡＤＡＧ）を計算すること（１１０６）であって、前記ＧＡＤＡＧは前記ネットワークのグラフ抽象化であり、前記複数のネットワークエレメントは前記ＧＡＤＡＧの頂点でありかつ前記複数のネットワークエレメントを接続するリンクは前記ＧＡＤＡＧの有向辺である、計算することと、
前記ネットワークエレメントにより、前記計算されたＧＡＤＡＧに基づいてＧＡＤＡＧ記述子をアセンブルすること（１１０８）と、
前記ネットワークエレメントにより、前記ＧＡＤＡＧ記述子を前記複数のネットワークエレメントに配信すること（１１１０）であって、前記複数のネットワークエレメントの各々は前記ＧＡＤＡＧ記述子を利用して、トラフィックを転送するための最大冗長木を計算する、配信することと
を含む方法。
【請求項２】
前記ＧＡＤＡＧの前記計算はＧＡＤＡＧルート選択にブリッジ識別子を利用することを含み、前記ブリッジ識別子は前記複数のネットワークエレメントを識別し、優先度フィールドを含む、請求項１に記載の方法。
【請求項３】
前記ＧＡＤＡＧ記述子は前記ＧＡＤＡＧの前記有向辺のリストを示す、請求項１に記載の方法。
【請求項４】
前記ＧＡＤＡＧ記述子はサブタイプ／長さ／値（サブ−ＴＬＶ）を含む、請求項１に記載の方法。
【請求項５】
前記サブ−ＴＬＶはタイプフィールドと、長さフィールドと、前記計算されたＧＡＤＡＧの前記頂点の表現とを含む、請求項４に記載の方法。
【請求項６】
前記頂点の各表現にはノードの識別子が含まれている、請求項５に記載の方法。
【請求項７】
前記ノードの識別子はブリッジを識別する、請求項６に記載の方法。
【請求項８】
表現された他のすべての頂点よりも前にある表現された第１の頂点は、前記表現された第１の頂点が前記ＧＡＤＡＧのＧＡＤＡＧルートであることを表す、請求項６に記載の方法。
【請求項９】
前記ＧＡＤＡＧの前記有向辺は有向連鎖（ｄｉｒｅｃｔｅｄ  ｃｈａｉｎ）を形成し、前記有向連鎖は順序付きノードの識別子によって記述される、請求項１に記載の方法。
【請求項１０】
前記ＧＡＤＡＧ記述子の前記配信は、リンク状態パケット（ＬＳＰ）またはリンク状態広告（ＬＳＡ）に含まれる前記ＧＡＤＡＧ記述子を前記複数のネットワークエレメントにフラッディングすることを含む、請求項１に記載の方法。
【請求項１１】
前記ネットワークにはｓｏｆｔｗａｒｅ−ｄｅｆｉｎｅｄ  ｎｅｔｗｏｒｋｉｎｇ  （ＳＤＮ）システムが含まれており、前記ＰＣＥは前記ＳＤＮシステムのＳＤＮコントローラによって実装される、請求項１に記載の方法。
【請求項１２】
前記ネットワークのトポロジ変更を判定すること（１１０２）と、
前記ネットワークの前記ＧＡＤＡＧを計算することに先立ち、ネットワークコンバージェンスの完了を待機すること（１１０４）と
をさらに含む、請求項１に記載の方法。
【請求項１３】
前記ＧＡＤＡＧ記述子の前記配信は前記複数のネットワークエレメントの少なくとも１つに対し、
前記ＰＣＥの前記機能を実装する前記ネットワークエレメントから前記ＧＡＤＡＧ記述子を受信すること（１３０２）と、
ＭＲＴルートに対して第１の最大冗長木（ＭＲＴ−Ｂｌｕｅ）および第２のＭＲＴを計算すること（１３０４）であって、前記ＭＲＴルートは前記ネットワークの１つのネットワークエレメントを表現する、計算することと、
前記計算された第１のＭＲＴおよび前記第２のＭＲＴに基づき、フィルタリングデータベース（ＦＤＢ）エントリをインストールすること（１３０６）と
を実行させる、請求項１に記載の方法。
【請求項１４】
前記ＦＤＢエントリの前記インストールは、
前記第１のＭＲＴに関するＦＤＢエントリの前記インストールが前記ネットワーク全体にわたって完了したときに、前記第２のＭＲＴに対応する前記ＦＤＢエントリをインストールすることを含む、請求項１３に記載の方法。
【請求項１５】
前記ＧＡＤＡＧ記述子はリンク状態パケット（ＬＳＰ）内で保持され、前記ＬＳＰには、前記ＧＡＤＡＧ記述子を検証するための前記ネットワークのトポロジのダイジェストが含まれている、請求項１３に記載の方法。
【請求項１６】
前記ＭＲＴルートは前記受信されたＧＡＤＡＧ記述子内に示されている、請求項１３に記載の方法。
【請求項１７】
前記ＧＡＤＡＧ記述子の前記配信は前記複数のネットワークエレメントの少なくとも１つに対し、
前記ＰＣＥの前記機能を実装する前記ネットワークエレメントから前記ＧＡＤＡＧ記述子を受信すること（１４０２）と、
ＭＲＴルートに対して第１の最大冗長木（ＭＲＴ−Ｂｌｕｅ）および第２のＭＲＴ（ＭＲＴ−Ｒｅｄ）を計算すること（１４０４）であって、前記ＭＲＴルートは前記ネットワークの１つのネットワークエレメントを表現する、計算することと、
前記計算された第１のＭＲＴおよび前記第２のＭＲＴに基づき、ｆｏｒｗａｒｄ  ｉｎｆｏｒｍａｔｉｏｎ  ｂａｓｅ（ＦＩＢ）エントリをインストールすること（１４０６）と
を実行させる、請求項１に記載の方法。
【請求項１８】
ネットワークのパス計算要素（ＰＣＥ）の機能を実装する、最大冗長木をデプロイするためのネットワークエレメントであって、前記ネットワークには複数のネットワークエレメントが含まれており、
プロセッサ（１６１３）および前記プロセッサに結合されたメモリ（１６１４）であって、前記メモリには前記プロセッサによって実行可能なパス計算ソフトウェア（１６１５）が含まれており、前記ネットワークエレメントは、
前記ネットワークの一般化概有向非巡回グラフ（ＧＡＤＡＧ）を計算することであって、前記ＧＡＤＡＧは前記ネットワークのグラフ抽象化であり、前記複数のネットワークエレメントは前記ＧＡＤＡＧの頂点でありかつ前記複数のネットワークエレメントを接続するリンクは前記ＧＡＤＡＧの有向辺である、計算することと、
前記計算されたＧＡＤＡＧに基づいてＧＡＤＡＧ記述子をアセンブルすることと、
前記ＧＡＤＡＧ記述子を前記複数のネットワークエレメントに配信することであって、前記複数のネットワークエレメントの各々は前記ＧＡＤＡＧ記述子を利用して、トラフィックを転送するための最大冗長木を計算する、配信することと
を行うように動作可能である、プロセッサおよびメモリ
を備えるネットワークエレメント。
【請求項１９】
前記ＧＡＤＡＧの前記有向辺は有向連鎖を形成し、前記有向連鎖は順序付きノードの識別子によって記述される、請求項１８に記載のネットワークエレメント。
【請求項２０】
前記ＧＡＤＡＧ記述子はサブ−タイプ／長さ／値（サブ−ＴＬＶ）を含む、請求項１８に記載のネットワークエレメント。
【請求項２１】
前記ネットワークにはｓｏｆｔｗａｒｅ−ｄｅｆｉｎｅｄ  ｎｅｔｗｏｒｋｉｎｇ（ＳＤＮ）システムが含まれており、前記ネットワークエレメントは前記ＳＤＮシステムのＳＤＮコントローラである、請求項１８に記載のネットワークエレメント。
【請求項２２】
前記ネットワークのトポロジ変更を判定することと、
前記ネットワークの前記ＧＡＤＡＧを計算することに先立ち、ネットワークコンバージェンスの完了を待機することと
を行うようにさらに動作可能である、請求項１８に記載のネットワークエレメント。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ネットワーキングの分野に関する。より具体的には、本発明の実施形態は、データネットワークに最大冗長木（ＭＲＴｓ）をデプロイする方法およびシステムに関する。
【背景技術】
【０００２】
データネットワークにおいて、転送パスは、典型的には、フレーム／パケットが転送されるパスを提供するパス制御プロトコルによって制御される。データネットワークの堅牢性を向上させるためには、パス選択に冗長性を組み込むことが望ましい。すなわち、所与のノードにおいて、あるパスに故障が生じた場合に、別のパスを使用してトラフィックのルーティングを行えることである。そのような冗長性は、トポロジ変更の場合にノードが直ちにパスを切り替えられるように、事前に定められているのが望ましい。冗長パスを計算する一つの方法は、ネットワーク接続をグラフと考え、グラフ内で最大冗長木（ＭＲＴｓ）を見つけることである。
【０００３】
インターネットプロトコル（ＩＰ）レイヤ（レイヤ３すなわちＬ３）における最大冗長木の実装に関しては、いくつかの解決策が提案されてきた。例えば、２０１３年７月１２日付の「Ａｎ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  ＩＰ／ＬＤＰ  Ｆａｓｔ−Ｒｅｒｏｕｔｅ  Ｕｓｉｎｇ  Ｍａｘｉｍａｌｌｙ  Ｒｅｄｕｎｄａｎｔ  Ｔｒｅｅｓ」と題するＩＥＴＦドラフトでは、リンク／ノード故障の後でもなお接続されているネットワークトポロジにおいて、リンク保護およびノード保護を実現する方法を開示している。２０１３年１０月１８日付の「Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｓｙｓｔｅｍ  ｔｏ  Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｓｙｓｔｅｍ（ＩＳ−ＩＳ）Ｅｘｔｅｎｓｉｏｎｓ  ｆｏｒ  Ｍａｘｉｍａｌｌｙ  Ｒｅｄｕｎｄａｎｔ  Ｔｒｅｅｓ」と題する別のＩＥＴＦドラフトでは、ＭＲＴの分散化された計算をサポートするＩＳ−ＩＳプロトコルの拡張を開示している。しかしながら、知る限り、ＯＳＩレイヤ２（データリンクレイヤ）（Ｌ２と称する）において最大冗長木を実装する解決策は提案されていない。またレイヤ３における既知の解決策は、最大冗長木の計算の分散化に対応していない。レイヤ３  ＭＲＴの解決策を効率化して、レイヤ２  ＭＲＴの解決策を得ることが望ましい。
【発明の概要】
【０００４】
複数のネットワークエレメントが含まれているネットワークのパス計算要素（ＰＣＥ）の機能を実装するネットワークエレメントに実装される、一般化概有向非巡回グラフ（ｇｅｎｅｒａｌｉｚｅｄ  ａｌｍｏｓｔ  ｄｉｒｅｃｔｅｄ  ａｃｙｃｌｉｃ  ｇｒａｐｈ）（ＧＡＤＡＧ）を計算し、分散するための方法が提案される。このネットワークエレメントがＧＡＤＡＧを計算し、ＧＡＤＡＧ記述子をアセンブルして、ＧＡＤＡＧ記述子を送出する。本方法は、レイヤ２ネットワークまたはレイヤ３ネットワークのいずれかで実行され得る。ＰＣＥは、例えばＳＤＮコントローラの一部としてネットワークエレメントまたはホストに常駐してもよい。
【０００５】
本方法は、ＰＣＥの機能を実装するネットワークエレメントにより、ネットワークのＧＡＤＡＧを計算することを含み、ＧＡＤＡＧはネットワークのグラフ抽象化であり、複数のネットワークエレメントはＧＡＤＡＧの頂点であり、複数のネットワークエレメントを接続するリンクはＧＡＤＡＧの有向辺である。本方法は、続いて、計算されたＧＡＤＡＧに基づいてＧＡＤＡＧ記述子をアセンブルし、ＧＡＤＡＧ記述子を複数のネットワークエレメントに配信することへ進み、複数のネットワークエレメントの各々はＧＡＤＡＧ記述子を利用して、トラフィックを転送するための最大冗長木を計算する。
【０００６】
ＧＡＤＡＧを計算し、配信するためのネットワークエレメントも開示される。このネットワークエレメントは、複数のネットワークエレメントが含まれているネットワークのＰＣＥとして機能する。ネットワークエレメントはネットワークのＧＡＤＡＧを計算し、ＧＡＤＡＧはネットワークのグラフ抽象化であり、複数のネットワークエレメントはＧＡＤＡＧの頂点でありかつ複数のネットワークエレメントを接続するリンクはＧＡＤＡＧの有向辺である。ネットワークエレメントは、計算されたＧＡＤＡＧに基づいてＧＡＤＡＧ記述子をアセンブルし、ＧＡＤＡＧ記述子を複数のネットワークエレメントに配信し、複数のネットワークエレメントの各々はＧＡＤＡＧ記述子を利用して、トラフィックを転送するための最大冗長木を計算する。
【０００７】
本方法を実行する命令が格納された非一時的な（ｎｏｎ−ｔｒａｎｓｉｔｏｒｙ）マシン可読記憶媒体も提案される。
【０００８】
開示される方法の実施形態は、レイヤ２において最大冗長木（ＭＲＴ）をデプロイし、レイヤ３においてさらに効率的にＭＲＴをデプロイできるようにする手法を提案する。開示される方法の実施形態は、トポロジ変更後に冗長木を更新するための手法も提供する。
【０００９】
本発明を限定ではなく例示するために添付図面の各図に示したが、これらの図面中で同様の参照番号は同様の要素を指す。本明細書における「ある」または「一」実施形態への様々な言及は必ずしも同じ実施形態への言及ではなく、そのような言及は少なくとも１つを意味することに留意すべきである。さらに、特定の特徴、構造、または特性がある実施形態に関連して説明されているとき、他の実施形態に関連して、このような特徴、構造、または特性に作用することは、明示されているか否かにかかわらず、当業者の知るところであると思われる。
【図面の簡単な説明】
【００１０】
【図１】データネットワークの例を示す図である。
【図２】概有向非巡回グラフ（ＡＤＡＧ）および有向非巡回グラフ（ＤＡＧ）を示す図である。
【図３】ＡおよびＢは、ＧＡＤＡＧルートとＭＲＴルートとが同じノードにあるような、ＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄのパスを示すブロック図である。
【図４】ＡおよびＢは、ＧＡＤＡＧルートとＭＲＴルートとが異なるノードにあるような、ＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄのパスを示すブロック図である。
【図５】本発明の一実施形態によるＭＲＴ実装の３つのモードを示すブロック図である。
【図６】本発明の一実施形態によるＭＲＴ  ＶＩＤサブ−ＴＬＶを示すブロック図である。
【図７】本発明の一実施形態による等価木（ＥＣＴ）アルゴリズムマッピングを示すブロック図である。
【図８】本発明の一実施形態によるＭＲＴ実装を示すブロック図である。
【図９】本発明の一実施形態によるＭＲＴ実装を示すフロー図である。
【図１０】本発明の一実施形態による別のＭＲＴ実装を示すブロック図である。
【図１１】本発明の一実施形態によるＧＡＤＡＧの計算および配信を示すフロー図である。
【図１２】本発明の一実施形態による、ＧＡＤＡＧ記述を配信するための明示パス（ＥＰ）サブ−ＴＬＶを示す図である。
【図１３】本発明の一実施形態によるＭＲＴペアの計算を示すフロー図である。
【図１４】本発明の一実施形態によるＭＲＴペアの計算を示す別のフロー図である。
【図１５】ＳＤＮネットワークを示すブロック図である。
【図１６】本発明の一実施形態に従い、ＭＲＴをデプロイする方法を実装する２つのネットワークエレメント示すブロック図である。
【図１７】本発明の一実施形態に従い、ＭＲＴをデプロイする方法を実装する１つのネットワークエレメント示すブロック図である。
【図１８】本発明の一実施形態に従い、ＧＡＤＡＧを計算し、配信するための方法を実装する１つのネットワークエレメント示すブロック図である。
【発明を実施するための形態】
【００１１】
以下の説明において、数多くの具体的な詳細を示す。しかしながら、本発明の実施形態はこれらの具体的な詳細なしに実施され得ると理解される。他の例において、周知の回路、構造、および技法は、本説明の理解を曖昧にしないために詳細には示されていない。
【００１２】
しかしながら、当業者であれば、本発明は、このような具体的な詳細なしに実施され得ることを理解するであろう。本発明を不明瞭にするのを避けるため、他の例においては、制御構造、ゲートレベル回路、およびソフトウェア命令シーケンス全体を詳細に示していない。当業者であれば、過度な実験を行わなくても、記載されている説明により適切な機能を実施することができるであろう。
【００１３】
本明細書における「一実施形態」、「ある実施形態」、「例示的な実施形態」などへの言及は、説明される実施形態が特定の機能、構造、または特性を含み得るが、すべての実施形態が必ずしも当該特定の機能、構造、または特性を含まなくてもよいことを示す。また、そのような表現は、必ずしも同じ実施形態に言及しない。さらに、特定の特徴、構造、または特性がある実施形態に関連して説明されているとき、他の実施形態に関連して、このような特徴、構造、または特性に作用することは、明示されているか否かにかかわらず、当業者の知るところであると思われる。
【００１４】
以下の説明および特許請求の範囲において、「結合される（ｃｏｕｐｌｅｄ）」および「接続される（ｃｏｎｎｅｃｔｅｄ）」という用語は、これらの派生語と共に用いられ得る。これらの用語は互いに同義語として意図されたものではないことを理解すべきである。「結合される」は、互いに直接物理的にまたは電気的に接触してもしなくてもよい２つ以上の要素が互いに協調動作しているか、または相互作用していることを示すために用いられる。「接続される」は、互いに結合された２つ以上の要素間における通信の確立を示すために用いられる。本明細書で使用する「セット」は、１項目を含む任意の正の整数個の項目を指す。
【００１５】
用語
【００１６】
本説明では以下の用語が用いられ得る。
【００１７】
ネットワークグラフ：すべてのリンクが厳密に２つのノードを接続しており、ブロードキャストリンクが標準的な疑似ノード表現に変えられているようなネットワークトポロジを反映するグラフ。
【００１８】
冗長木（ＲＴ）：任意のノードＸからルートＲへの第１の木に沿ったパスが、同じノードＸからルートへの第２の木に沿ったパスと点素（ｎｏｄｅ−ｄｉｓｊｏｉｎｔ）であるような、１組の木。これらは２連結グラフにおいて計算可能である。
【００１９】
最大冗長木（ＭＲＴ）：任意のノードＸからルートＲへの第１の木に沿ったパスと、同じノードＸからルートへの第２の木に沿ったパスとが、最小数のノードおよび最小数のリンクを共有しているような、１対の木。このような共有ノードはそれぞれ切断点である。いかなる共有リンクも切断リンクである。いかなるＲＴもＭＲＴだが、多くのＭＲＴはＲＴではない。
【００２０】
最大ディスジョイント木（Ｍａｘｉｍａｌｌｙ  ｄｉｓｊｏｉｎｔ  ｔｒｅｅ）（ＭＤＴ）：ＭＲＴと同じ。
【００２１】
ＭＲＴ−Ｒｅｄ：ＭＲＴ−Ｒｅｄは２つのＭＲＴの一方を記述するのに用いられる。関連付けられた転送トポロジおよびＭＴ−ＩＤを記述するために用いられる。具体的には、ＭＲＴ−Ｒｅｄは、ＧＡＤＡＧにおけるリンクがトポロジ上の上位に順序付けられたノードから下位のノードの方向へ向かうような、逆順の（ｄｅｃｒｅａｓｉｎｇ）ＭＲＴである。ＭＲＴ−Ｒｅｄはレッドツリー（ｒｅｄ  ｔｒｅｅ）と称されることもあることに留意されたい。ＭＲＴ−Ｂｌｕｅ（下記）およびＭＲＴ−Ｒｅｄは合わせて、彩色木（ｃｏｌｏｒｅｄ  ｔｒｅｅ）、独立木、または回復木（ｒｅｃｏｖｅｒｙ  ｔｒｅｅ）とも称される。ＭＲＴ−ＢｌｕｅおよびマッピングＭＲＴ−Ｒｅｄは合わせて、ＭＲＴペアと称されることもある。
【００２２】
ＭＲＴ−Ｂｌｕｅ：ＭＲＴ−Ｂｌｕｅは、２つのＭＲＴの一方を記述するのに用いられる。関連付けられた転送トポロジおよびＭＴ−ＩＤを記述するために用いられる。具体的には、ＭＲＴ−Ｂｌｕｅは、ＧＡＤＡＧにおけるリンクがトポロジ上の下位に順序付けられたノードから上位のノードの方向へ向かうような、正順の（ｉｎｃｒｅａｓｉｎｇ）ＭＲＴである。
【００２３】
明示パス（ＥＰ）：パス内の各ノードが明示的に指定されている、明示的に規定されたパス。
【００２４】
等価木（ＥＣＴ）：等価木は、等価パス代替案から選ぶための特定の方法を用いる、最短パス木（ＳＰＴ）の一意のインスタンシエーション（ｉｎｓｔａｎｔｉａｔｉｏｎ）である。ノード間に複数の多様なパスを有するネットワークにおいて、ルートノードから葉ノードまでの等価パスを持つ、同じルートノードからの異なる最短パス木同士は、等価木と考えられる。ＥＣＴは、等価マルチツリー（ｅｑｕａｌ  ｃｏｓｔ  ｍｕｌｔｉ−ｔｒｅｅ）（ＥＣＭＴ）と称されることもある。一実施形態において、ＥＣＴセットはＥＣＴアルゴリズムによって識別され、ＶＬＡＮは一意のＥＣＴアルゴリズムに関連付けられている。
【００２５】
ＥＣＴアルゴリズム：最短パス木（ＳＰＴ）領域内のすべてのブリッジによって実行されるとき、所与のルートブリッジについて一貫した結果をもたらすＳＰＴアルゴリズム。
【００２６】
パス計算要素（ＰＣＥ）：ネットワークグラフに基づいて転送パスを計算することができるエントリ。ＰＣＥは、ネットワークノードまたは終端局（ホスト、サーバ）における上位層エンティティ（制御プレーンアプリケーション）である。ＰＣＥは、ノード内に埋め込まれたノードローカル計算エンジン（ｎｏｄｅ  ｌｏｃａｌ  ｃｏｍｐｕｔａｔｉｏｎ  ｅｎｇｉｎｅ）（ＮＬＣＥ）よりも複雑な計算タスクを実行することができる。
【００２７】
ローカル修復ポイント：故障イベントの後に、ループなしの代替パスなどのバックアップパスへデータトラフィックをローカルでリダイレクトする、ブリッジ／スイッチといったネットワークノード。
【００２８】
ユニキャスト：一意の個別の媒体アクセス制御（ＭＡＣ）アドレスによって識別される単一の宛先ノードへ、１個のフレームを送信すること。
【００２９】
マルチキャスト：単一の発信元ノードから、一意のグループＭＡＣアドレスによって受信者のセットが識別される複数の宛先ノードへ、１個のフレームを同時に送信すること。
【００３０】
最短パスブリッジング−ＶＬＡＮモード（ＳＰＢＶ）：ＶＬＡＮベースの一種のＳＰＢ。すなわち、各最短パス木が別々のＶＬＡＮ識別子（ＶＩＤ）によって規定される。
【００３１】
最短パスブリッジング−ＭＡＣモード（ＳＰＢＭ）：最短パス木がＭＡＣベースである、別のタイプのＳＰＢ。すなわち、各最短パス木が一意のＭＡＣアドレスまたは短縮形のＭＡＣアドレスによって識別される。ＶＬＡＮは複数パスの変動を表現するために用いられる。
【００３２】
最短パスＶＩＤ（ＳＰＶＩＤ）：ＳＰＶＩＤは、ＶＬＡＮと、ＳＰＢＶにおけるタグフレームの伝送に用いられるＳＰＴの両方を識別する。
【００３３】
２連結：切断点を持たないグラフ。ネットワークを分割するためには２つのノードを削除する必要があるようなグラフである。
【００３４】
２連結クラスタ：２連結であるノードの最大セット。
【００３５】
２辺連結：ネットワークを分割するためには少なくとも２つのリンクを削除する必要があるようなネットワークグラフ。
【００３６】
切断リンク：削除すると、ネットワークが分割されてしまうようなリンク。切断リンクは、規定上、２つの切断点間を連結していなければならない。複数の平行リンクが存在する場合、平行リンクのセットを削除するとネットワークグラフが分割されてしまう場合に、本文書ではこれらの平行リンクを切断リンクと称する。
【００３７】
切断点：削除すると、ネットワークグラフが分割されてしまうような頂点。
【００３８】
ダイグラフ：有向グラフ。
【００３９】
有向非巡回グラフ（ＤＡＧ）：すべてのリンクが有向であり、閉路（ｃｙｃｌｅ）が存在しないグラフ。
【００４０】
概有向非巡回グラフ（ＡＤＡＧ）：ルートに入ってくるすべてのリンクが削除された場合にＤＡＧとなるようなグラフ。
【００４１】
一般化概有向非巡回グラフ（ＧＡＤＡＧ）：すべてのブロックのＡＤＡＧの組合せであるグラフ。
【００４２】
サブ−タイプ／長さ／値（サブ−ＴＬＶ）：ＴＬＶは、タイプ、長さ、および値の連続的なフィールドから成る、情報要素の短い可変長符号である。タイプフィールドは情報のタイプを識別し、長さフィールドは情報フィールドの長さをオクテットで示し、値フィールドには情報そのものが含まれている。サブ−ＴＬＶに用いられている概念はＴＬＶと同じである。違いは、ＴＬＶがパケット／フレームの内部に存在するのに対し、サブ−ＴＬＶはＴＬＶの内部に存在することである。サブ−ＴＬＶは、特定のＴＬＶに余分な情報を追加するために用いられる。各サブ−ＴＬＶは３つのフィールドから成る。１オクテットのタイプフィールド、１オクテットの長さフィールド、およびゼロオクテット以上の値フィールドである。タイプフィールドは、値フィールド内の項目のタイプを示す。長さフィールドは、値フィールドの長さをオクテットで示す。各サブ−ＴＬＶは潜在的に複数の項目を有し得る。サブ−ＴＬＶ内の項目数は、各項目の長さがわかっているとき、サブ−ＴＬＶ全体の長さから計算できる。未知のサブ−ＴＬＶは受信時に無視され、スキップされる。
【００４３】
電子デバイス（例えば、終端局、ネットワークエレメント）は、非一時的なマシン可読媒体（例えば、磁気ディスク、光ディスク、読み出し専用メモリ、フラッシュメモリデバイス、相変化メモリといったマシン可読記憶媒体）および一時的なマシン可読伝送媒体（例えば、搬送波、赤外線信号といった、電気的、光学的、音響的な形態または他の形態の伝搬信号）といったマシン可読媒体を用いて、（ソフトウェア命令から成る）コードおよびデータを格納し、（内部的におよび／または他の電子デバイスとの間でネットワークを介して）伝送する。加えて、そうした電子デバイスは、（コードおよび／もしくはデータを格納する）１つまたは複数の非一時的なマシン可読記憶媒体ならびに（伝播信号を用いてコードおよび／もしくはデータを伝送するための）ネットワーク接続、場合によってはユーザ入力／出力デバイス（例えば、キーボード、タッチスクリーン、および／もしくはディスプレイ）といった、１つまたは複数の他のコンポーネントに結合される１つまたは複数のプロセッサのセットなどのハードウェアを含む。プロセッサのセットと他のコンポーネントとの結合は、典型的には、当該電子デバイス内の１つまたは複数の相互接続（例えば、バスおよび場合によってはブリッジ）を介する。よって、所与の電子デバイスの非一時的なマシン可読媒体は、典型的には、本明細書において以下に詳述する本発明の実施形態の動作を実行する当該電子デバイスの１つまたは複数のプロセッサ上での実行のための命令を格納する。本発明のある実施形態の１つまたは複数の部分は、ソフトウェア、ファームウェア、および／またはハードウェアの様々な組合せを用いて実装され得る。
【００４４】
本明細書において、ネットワークエレメント（例えば、ルータまたはスイッチ）は、ネットワーク上の他の機器（例えば、他のネットワークエレメント、エンドシステム）と通信可能に相互接続する、ハードウェアおよびソフトウェアを含む１つのネットワーキング機器である。いくつかのネットワークエレメントは、複数のネットワーキング機能（例えば、ルーティング、ブリッジング、ＶＬＡＮ（仮想ＬＡＮ）スイッチング、レイヤ２アグリゲーション、セッションボーダ制御、サービス品質および／もしくは加入者管理）のためのサポートを提供し、ならびに／または、複数のアプリケーションサービス（例えば、データ、音声、および動画）のためのサポートを提供する「マルチサービスネットワークエレメント（ｍｕｌｔｉｐｌｅ  ｓｅｒｖｉｃｅｓ  ｎｅｔｗｏｒｋ  ｅｌｅｍｅｎｔｓ）」である。加入者エンドシステム（例えば、サーバ、ワークステーション、ラップトップ、ネットブック、パームトップ、携帯電話、スマートフォン、マルチメディアフォン、Ｖｏｉｃｅ  Ｏｖｅｒ  Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ（ＶＯＩＰ）電話、ユーザ機器、端末、ポータブルメディアプレーヤ、ＧＰＳユニット、ゲーム機、セットトップボックス）は、インターネットを介して提供されるコンテンツ／サービス、および／またはインターネット上に重畳した（例えば、インターネットを通じてトンネリングされる）仮想プライベートネットワーク（ＶＰＮ）上で提供されるコンテンツ／サービスにアクセスする。コンテンツおよび／またはサービスは、典型的には、サービスプロバイダもしくはコンテンツプロバイダに属する１つもしくは複数のエンドシステム（例えば、サーバエンドシステム）またはピアツーピアサービスに参加するエンドシステムによって提供され、例えば、公開ウェブページ（例えば、無料コンテンツ、ストアフロント、検索サービス）、プライベートなウェブページ（例えば、電子メールサービスを提供する、ユーザ名／パスワードによりアクセスされるウェブページ）、および／またはＶＰＮ上の企業ネットワークを含み得る。典型的に、加入者エンドシステムは、（例えば、（有線または無線で）アクセスネットワークに結合される顧客構内機器を介して）エッジネットワークエレメントに結合される。このエッジネットワークエレメントは、（例えば、１つまたは複数のコアネットワークエレメントを介して）他のエッジネットワークエレメントに結合され、他のエッジネットワークエレメントは、他のエンドシステム（例えば、サーバエンドシステム）に結合される。ネットワークエレメントは、通常、その媒体アクセス制御（ＭＡＣ）アドレス、インターネットプロトコル（ＩＰ）アドレス／サブネット、ネットワークソケット／ポート、および／またはＯＳＩ上位層識別子によって識別される。
【００４５】
ネットワークエレメントは、一般に、制御プレーンとデータプレーン（転送プレーンまたは媒体プレーンと称されることもある）とに分かれる。ネットワークエレメントがルータである（またはルーティング機能を実装している）場合、制御プレーンは、典型的には、データ（例えば、パケット）がどのようにルーティングされるべきか（例えば、データのネクストホップおよびそのデータの発信ポート）を判定し、データプレーンは、そのデータの転送を担う。例えば、制御プレーンは、典型的には、他のネットワークエレメントと通信を行い、経路を交換して、１つまたは複数のルーティングメトリックに基づき、これらの経路を選択する１つまたは複数のルーティングプロトコルを含む（ルーティングプロトコルの例としては、ボーダゲートウェイプロトコル（ＢＧＰ）（ＲＦＣ  ４２７１）などの外部ゲートウェイプロトコル、内部ゲートウェイプロトコル（ＩＧＰ）（例えばＯｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔ（ＯＳＰＦ）（ＲＦＣ  ２３２８および５３４０）、Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｓｙｓｔｅｍ  ｔｏ  Ｉｎｔｅｒｍｅｄｉａｔｅ  Ｓｙｓｔｅｍ（ＩＳ−ＩＳ）（ＲＦＣ  １１４２）、ルーティング情報プロトコル（ＲＩＰ）（バージョン１はＲＦＣ  １０５８、バージョン２はＲＦＣ  ２４５３、次世代はＲＦＣ  ２０８０））、Ｌａｂｅｌ  Ｄｉｓｔｒｉｂｕｔｉｏｎ  Ｐｒｏｔｏｃｏｌ（ＬＤＰ）（ＲＦＣ  ５０３６）、リソース予約プロトコル（ＲＳＶＰ）（ＲＦＣ  ２２０５、２２１０、２２１１、２２１２に加え、ＲＳＶＰ−Ｔｒａｆｆｉｃ  Ｅｎｇｉｎｅｅｒｉｎｇ（ＴＥ）：Ｅｘｔｅｎｓｉｏｎｓ  ｔｏ  ＲＳＶＰ  ｆｏｒ  ＬＳＰ  Ｔｕｎｎｅｌｓ  ＲＦＣ  ３２０９、Ｇｅｎｅｒａｌｉｚｅｄ  Ｍｕｌｔｉ−Ｐｒｏｔｏｃｏｌ  Ｌａｂｅｌ  Ｓｗｉｔｃｈｉｎｇ（ＧＭＰＬＳ）Ｓｉｇｎａｌｉｎｇ  ＲＳＶＰ−ＴＥ−ＲＦＣ  ３４７３、ＲＦＣ  ３９３６、４４９５、および４５５８）がある）。加えて、制御プレーンもまた、典型的には、様々な標準化団体によって標準化された（例えば、ＳＰＢはＩＥＥＥ規格８０２．１ａｑ−２０１２において規定されている）Ｒａｐｉｄ  Ｓｐａｎｎｉｎｇ  Ｔｒｅｅ  Ｐｒｏｔｏｃｏｌ（ＲＳＴＰ）、Ｍｕｌｔｉｐｌｅ  Ｓｐａｎｎｉｎｇ  Ｔｒｅｅ  Ｐｒｏｔｏｃｏｌ（ＭＳＴＰ）、およびＳＰＢ（Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｂｒｉｄｇｉｎｇ）などのＩＳＯレイヤ２制御プロトコルを含む。
【００４６】
経路および近隣情報（ａｄｊａｃｅｎｃｙ）は、制御プレーン上の１つまたは複数のルーティング構造（例えばＲｏｕｔｉｎｇ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｂａｓｅ（ＲＩＢ）、Ｌａｂｅｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｂａｓｅ（ＬＩＢ）、１つまたは複数の近隣構造）に格納される。制御プレーンは、ルーティング構造に基づく情報（例えば、近隣および経路情報）でデータプレーンをプログラムする。例えば、制御プレーンは、近隣および経路情報を、データプレーン上の１つまたは複数の転送構造（例えば、Ｆｏｒｗａｒｄｉｎｇ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｂａｓｅ（ＦＩＢ）、Ｌａｂｅｌ  Ｆｏｒｗａｒｄｉｎｇ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｂａｓｅ（ＬＦＩＢ）、および１つまたは複数の近隣構造）にプログラムする。データプレーンは、トラフィックを転送するときにこれらの転送構造および近隣構造を使用する。
【００４７】
ネットワークエレメントは、典型的に、１つまたは複数のラインカードのセットと、１つまたは複数の制御カードのセットと、オプションとして１つまたは複数のサービスカード（リソースカードと称されることもある）のセットとを含む。これらのカードは、１つまたは複数の相互接続メカニズム（例えば、ラインカードを結合する第１のフルメッシュ結合およびすべてのカードを結合する第２のフルメッシュ結合）を通じて互いに結合される。ラインカードのセットは、データプレーンを成す一方、制御カードのセットは、制御プレーンを提供し、ラインカードを通じて外部のネットワークエレメントとパケットを交換する。サービスカードのセットは、特殊な処理（例えば、レイヤ４〜レイヤ７のサービス（例えば、ファイアウォール、Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ  Ｓｅｃｕｒｉｔｙ（ＩＰＳｅｃ）（ＲＦＣ  ４３０１および４３０９）、侵入検知システム（ＩＤＳ）、ピアツーピア（Ｐ２Ｐ）、Ｖｏｉｃｅ  ｏｖｅｒ  ＩＰ（ＶｏＩＰ）セッションボーダコントローラ、モバイルワイヤレスゲートウェイ（Ｇａｔｅｗａｙ  Ｇｅｎｅｒａｌ  Ｐａｃｋｅｔ  Ｒａｄｉｏ  Ｓｅｒｖｉｃｅ  （ＧＰＲＳ）  Ｓｕｐｐｏｒｔ  Ｎｏｄｅ（ＧＧＳＮ）、Ｅｖｏｌｖｅｄ  Ｐａｃｋｅｔ  Ｃｏｒｅ（ＥＰＣ）ゲートウェイ））を提供することができる。一例として、サービスカードは、ＩＰＳｅｃトンネルを終端させ、ならびに付随する認証アルゴリズムおよび暗号化アルゴリズムを実行するために用いられ得る。
【００４８】
本明細書において、ノードは、ＩＰパケット内のＩＰヘッダ情報の一部に基づいてＩＰパケットを転送する。ＩＰヘッダ情報は、発信元ＩＰアドレス、宛先ＩＰアドレス、発信元ポート、宛先ポート（本明細書において、「発信元ポート」および「宛先ポート」は、ネットワークエレメントの物理ポートとは対照的に、プロトコルポートをいう）、トランスポートプロトコル（例えば、ユーザデータグラムプロトコル（ＵＤＰ）（ＲＦＣ  ７６８、２４６０、２６７５、４１１３、および５４０５）、伝送制御プロトコル（ＴＣＰ）（ＲＦＣ  ７９３および１１８０）、ならびにｄｉｆｆｅｒｅｎｔｉａｔｅｄ  ｓｅｒｖｉｃｅｓ（ＤＳＣＰ）値（ＲＦＣ  ２４７４、２４７５、２５９７、２９８３、３０８６、３１４０、３２４６、３２４７、３２６０、４５９４、５８６５、３２８９、３２９０、および３３１７）を含む。ノードは、ネットワークエレメントにおいて実装される。物理ノードは、ネットワークエレメント上に直接実装されるが、仮想ノードはネットワークエレメント上に実装されるソフトウェアの、および場合によってはハードウェアの抽象化である。このため、複数の仮想ノードが単一のネットワークエレメント上に実装されてもよい。
【００４９】
ネットワークインターフェースは、物理的であっても仮想的であってもよく、インターフェースアドレスは、ネットワークインターフェースが物理ネットワークインターフェースであれ、仮想ネットワークインターフェースであれ、ネットワークインターフェースに割り当てられるＩＰアドレス、またはＭＡＣアドレスである。物理ネットワークインターフェースはネットワークエレメント内のハードウェアであり、このインターフェースを通じて、ネットワーク接続が（例えば、無線ネットワークインターフェースコントローラ（ＷＮＩＣ）を通じて無線で、またはネットワークインターフェースコントローラ（ＮＩＣ）へ接続されているポートへのケーブルのプラグインを通じて）行われる。典型的に、１つのネットワークエレメントは、複数の物理ネットワークインターフェースを有している。仮想ネットワークインターフェースは、物理ネットワークインターフェースに関連付けられるか、別の仮想インターフェースに関連付けられるか、または、単独で稼働し得る（例えば、ループバックインターフェース、ポイントツーポイントプロトコルインターフェース）。ネットワークインターフェースは（物理的であれ仮想的であれ）、番号が付されてもよいし（ＩＰアドレスまたはＭＡＣアドレスありのネットワークインターフェース）、番号が付されなくてもよい（ＩＰアドレスもＭＡＣアドレスもなしのネットワークインターフェース）。ループバックインターフェース（およびそのループバックアドレス）は、管理の目的でしばしば使用される（物理的なまたは仮想的な）ノードの特定のタイプの仮想ネットワークインターフェース（およびＩＰアドレスまたはＭＡＣアドレス）であり、こうしたＩＰアドレスは、ノードの（ｎｏｄａｌ）ループバックアドレスと称される。ネットワークエレメントのネットワークインターフェースに割り当てられるＩＰアドレスまたはＭＡＣアドレスは、そのネットワークエレメントのＩＰアドレスまたはＭＡＣアドレスと称される。より精細なレベルで、ネットワークエレメント上に実装されるノードに割り当てられるネットワークインターフェースに割り当てられるＩＰアドレスまたはＭＡＣアドレスは、そのノードのＩＰアドレスと称され得る。
【００５０】
ＧＡＤＡＧおよびＭＲＴ
【００５１】
図１はデータネットワークの例を示す。ネットワーク１００にはノードＡ〜Ｉが含まれている。各ノードは、本明細書で上述したネットワークエレメントとすることができる。ネットワーク１００には、本明細書で上記に規定したＰＣＥも含まれている。いくつかの実施形態において、ＰＣＥもまた、ノードＡ〜Ｉとは別に１つのネットワークエレメントとして実装される。他の実施形態において、ＰＣＥの機能はノードＡ〜Ｉ内で実施される。保護を提供する一つの手法は最大冗長木（ＭＲＴ）をデプロイすることである。ＭＲＴは、当技術分野で周知のように、迅速な再ルーティングによる最短パスの保護に用いることができる。例えば、ネットワークの各リンクについて、所与のリンクまたは自身にアタッチされている近隣ノードがダウンした場合にどのＭＲＴ（ＢｌｕｅまたはＲｅｄ）がノードによって使われるべきかが事前に定められていたとすると、最短パスのリンクがダウンした場合、ローカル修復ポイントにおけるノードは、宛先アドレスをルートとする影響を受けていないＭＲＴ上でフレーム／パケットを送信する。ＭＲＴを計算するためには、まずＧＡＤＡＧを計算する必要がある。
【００５２】
図２は概有向非巡回グラフ（ＡＤＡＧ）および有向非巡回グラフ（ＤＡＧ）を示す。このＡＤＡＧおよびＤＡＧは、図１のネットワーク１００のグラフ抽象化である。グラフにおいて、各ノードはグラフの頂点になり、ノード間の各リンクはグラフの辺になる。これらのグラフは有向グラフである。ネットワーク１００のＤＡＧでは、有向閉路は含まれていない。ＤＡＧは頂点の半順序を表現することができる。例えば、このＤＡＧは頂点ＡおよびＩの半順序をＡ＜Ｂ＜Ｃ＜Ｆ＜Ｈ＜Ｉとして捉える。必ずしもすべての関係がＤＡＧによって規定されるわけではないため、これは単なる半順序である。例えば、図２におけるＤＡＧは、ＦとＤとの関係、ＦとＥとの関係、またはＦとＧとの関係に関する情報を提供していない。
【００５３】
規定されている通り、ネットワーク１００のＡＤＡＧはノードＡ（図中に太線の四角で表す）においてルートを有し、このＡＤＡＧはネットワーク１００のグラフである。ルートＡに入るすべてのリンクが削除されたとすると、図の右側に示したＤＡＧになる。一般化ＡＤＡＧ（ＧＡＤＡＧ）は、２連結ではないグラフを含め、すべてのブロックのＡＤＡＧを含む。
【００５４】
図３Ａ〜図３Ｂは、ＧＡＤＡＧルートとＭＲＴルートとが同じノードにあるような、ＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄのパスを示すブロック図である。図中、ＭＲＴルートであるノードは網掛けで表されており、ＧＡＤＡＧルートおよびＭＲＴルートは両方ともノードＡにある。ＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄは、共通ルート（ノードＡにおけるＭＲＴルート）へ向かう最大ディスジョイントパスを提供する、１組の有向スパニングツリーを表す。
【００５５】
ＭＲＴ−Ｂｌｕｅパスにおいて、参照番号３０２におけるパケット／フレームフローは、すべてのノードからＭＲＴルートへのＧＡＤＡＧ昇順に従っていることに留意されたい。対照的に、ＭＲＴ−Ｒｅｄパスにおいては、参照番号３０４におけるパケット／フレームフローは、すべてのノードからＭＲＴルートへのＧＡＤＡＧ降順に従っている。換言すれば、ノードの順序付けを決定するＧＡＤＡＧの計算とは、所与のＭＲＴルートに対してＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄを計算する最初のステップである。
【００５６】
各ノードにおいて、パケット／フレームは、可能な場合、ＭＲＴルートに到達するために別々のポートを使用する。例えば、ノードＢにおいて、ＭＲＴ−ＢｌｕｅではルートＡに到達するためにポート１が用いられるとする。ポート１はノードＣに連結しているリンクに結合されている。ＭＲＴ−Ｒｅｄでは、ルートＡに到達するために、パケット／フレームフロー３０４には、ノードＡに連結しているリンクに結合された（ポート２と呼ばれる）異なるポートが用いられる。トラフィック用のポートの分離は、ネットワークにおいてＭＲＴ−ＢｌｕｅグラフおよびＭＲＴ−Ｒｅｄグラフを実装するときの素である度合い（ｄｅｇｒｅｅ  ｏｆ  ｄｉｓｊｏｉｎｔｅｄｎｅｓｓ）を表す。
【００５７】
図４Ａ〜図４Ｂは、ＧＡＤＡＧルートとＭＲＴルートとが異なるノードにあるような、ＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄのパスを示すブロック図である。ＧＡＤＡＧルートが決定されれば、ＧＡＤＡＧは計算され得る。ただし、所与のＧＡＤＡＧには、異なるＭＲＴグラフとなる複数のＭＲＴルートがあり得る。図４Ａ〜図４Ｂは、ＧＡＤＡＧルートがノードＡであり、ＭＲＴルートがＨであるシナリオを示している。この場合、ＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄは、図３Ａ〜図３Ｂと異なっている。換言すれば、ルートＡを有する同じＧＡＤＡＧについて、異なるＭＲＴルートに対して異なるＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄがあり得る。よって、所与のＭＲＴアルゴリズムを使用して、ネットワーク内のすべてのＭＲＴルートに対するすべてのＭＲＴを計算するために、同じＧＡＤＡＧを用いることができる。ＭＲＴの計算はＭＲＴルートごとに繰り返す必要があるのに対し、ＧＡＤＡＧが同じであれば、ＧＡＤＡＧの計算は１回のみ行えばよい。したがって、ＭＲＴ計算を配分し、計算効率の向上を達成することが可能である。
【００５８】
ネットワークにおいてＭＲＴをデプロイする方法
【００５９】
本明細書において検討したように、ネットワーク冗長性の向上は、所与のＭＲＴルートに対してＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄを決定することにより達成され得る。このようにすることで、ノードは、トポロジ変更時に、ＭＲＴ−ＢｌｕｅまたはＭＲＴ−Ｒｅｄに沿って選択された経路にトラフィックをルーティングすることができる。例えば、パケット／フレームが伝送される最短パス木（ＳＰＴ）が分断されたとき、そのパケット／フレームは、ＭＲＴ−ＢｌｕｅまたはＭＲＴ−Ｒｅｄのいずれかのパスに直ちに切り替えることができる。
【００６０】
図５は、本発明の一実施形態によるＭＲＴ実装の３つのモードを示すブロック図である。図５のネットワーク１００は、図１に示されたものと同じであり、このネットワークはノードＡ〜ＩおよびＰＣＥを含む。ネットワークがＭＲＴをデプロイする際に、ネットワークはモードＡ、Ｂ、およびＣという３つのモードのいずれか１つで動作し得る。
【００６１】
モードＡにおいて、ＭＲＴの計算には完全に分散化される計算を利用する。完全に分散化される計算では、各ノードがトポロジのＧＡＤＡＧを計算し、次いで各ノードは、１つまたは複数の所与のＭＲＴルートに対して、それぞれのＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄを決定する。モードＡにおいて、各ノードは、それぞれのＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄを計算するのに用いられるＥＣＴアルゴリズムで構成され、計算結果であるＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄをルーティングに使用するように構成されている。
【００６２】
モードＢにおいて、ＭＲＴの計算は２つの部分に分けられ、ＰＣＥとノードとが計算を分担する。具体的には、ＰＣＥがネットワークのＧＡＤＡＧを計算し、次いでＧＡＤＡＧの記述が各ノードに配信され、ノードが１つまたは複数の所与のＭＲＴルートに対するＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄを計算する。共通のＧＡＤＡＧ計算は各ノードで繰り返されないため、モードＢは、モードＡに比べ、計算全体を減少させる可能性がある。
【００６３】
モードＣにおいて、ＭＲＴの計算はネットワークのＰＣＥにおいて集中化される。ＰＣＥは、ネットワークのＧＡＤＡＧと、全ノードの１つまたは複数の所与のＭＲＴルートに対するＭＲＴとの両方を計算する。計算されたＭＲＴの記述は次いで各ノードに配信される。モードＣの利点は、集中化された計算により個々のノードにおける計算の必要性が低減するため、ｓｏｆｔｗａｒｅ−ｄｅｆｉｎｅｄ  ｎｅｔｗｏｒｋｉｎｇ（ＳＤＮ）システムなどのいくつかの実装においては非常に有効であり得ることである。しかしながら、計算されたＭＲＴのすべての記述をあらゆるノードへ配信する必要があることから、かなりの通信量が必要となるため、このモードは過度に「チャッティ（ｃｈａｔｔｙ）」であると見なされ得る。
【００６４】
３つのモード（ＭＲＴデプロイメントモードと称される）は、完全に分散化される計算モード（モードＡ）、集中化して計算されるＧＡＤＡＧモード（モードＢ）、および集中化して計算されるＭＲＴモード（モードＣ）と称される。本発明の実施形態は、これらのモードにおけるＭＲＴのデプロイメントを最適化する手法を開示する。
【００６５】
ＭＲＴをデプロイするためのネットワークのセットアップ
【００６６】
ネットワークがＭＲＴをデプロイするには、ネットワークの各ノードが同じモードで機能する必要がある。加えて、ネットワークはＭＲＴを一貫したやり方で表す必要がある。レイヤ２ネットワークの場合、各々のＭＲＴ−ＢｌｕｅおよびＭＲＴ−ＲｅｄはＶＬＡＮ  ＩＤ（ＶＩＤ）に関連付けることができる。この関連付けは、ネットワーク内で一貫するようにノード間で通信されなければならない。関連付けを通信する一つの手法は、ルーティングプロトコルのサブ−ＴＬＶを、例えばＩＳ−ＩＳにより、交換することにより行う。
【００６７】
図６は、本発明の一実施形態によるＭＲＴ  ＶＩＤサブ−ＴＬＶを示すブロック図である。サブ−ＴＬＶは、ルーティングプロトコル（例えばＨｅｌｌｏ  ＰＤＵ）のＰＤＵに埋め込まれてもよく、各ノードにおいて生成されてもよい（モードＡまたはＢ）。サブ−ＴＬＶは、ＰＣＥにおいて生成されて（モードＢまたはＣ）、リンク状態パケット（ＬＳＰ）またはリンク状態広告（ＬＳＡ）を用いて各ノードに配信されてもよい。
【００６８】
サブ−ＴＬＶには、ＭＲＴ  ＶＩＤマッピング用のサブ−ＴＬＶのタイプを示すタイプフィールド６０２が含まれている。サブ−ＴＬＶには、サブ−ＴＬＶの合計長を示す長さフィールド６０４も含まれている。次いで参照番号６２４に示すサブ−ＴＬＶの値用のフィールドが含まれている。サブ−ＴＬＶの値はいくつかのパラメータを含んでいる。一つは、参照番号６０６に示す、ＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄを決定するためのＭＲＴアルゴリズムを識別する、ＥＣＴアルゴリズムである。事前に規定されたＥＣＴアルゴリズムがいくつか存在し、各々が最短パス木（ＳＰＴ）を発生させる。ネットワークは、各ノード（および／またはＰＣＥ）がＳＰＴを求めるのにどのＥＣＴアルゴリズムを使用すべきかについて一貫している必要がある。本発明の実施形態は、ＥＣＴアルゴリズムを用いて、ＭＲＴＬｏｗｐｏｉｎｔアルゴリズムを識別する。
【００６９】
図７は、本発明の一実施形態による等価木（ＥＣＴ）アルゴリズムマッピングを示すブロック図である。マッピングテーブルにおいて、各ＥＣＴアルゴリズムは値によって識別され、各ＥＣＴアルゴリズムはＭＲＴデプロイメントモードに対応している。この例では、ＥＣＴアルゴリズム００−８０−Ｃ２−２０はＭＲＴデプロイメントモードＣを表し、ＥＣＴアルゴリズム００−８０−Ｃ２−２１はＭＲＴデプロイメントモードＡを表し、ＥＣＴアルゴリズム００−８０−Ｃ２−２３はＭＲＴデプロイメントモードＢを表す。明らかに、１６進値は各モードで用いられるＥＣＴアルゴリズムを表し得るが、示された１６進値は一例に過ぎない。
【００７０】
図７のテーブルは、制約のある明示パスに対してＥＣＴアルゴリズム値が選択されている、本明細書で上記に引用したＩＥＥＥ  Ｐ８０２．１Ｑｃａ／Ｄ０．５のＴａｂｌｅ  ４５−１の拡張または変形であり得ることにも留意されたい。
【００７１】
図６を再び参照すると、サブ−ＴＬＶの値には、様々なＶＩＤ値が含まれている。１つは、参照番号６０８に示す、ＭＲＴ−Ｂｌｕｅを識別するためのＶＩＤ（Ｂｌｕｅ  ＶＩＤと称されることもある）であり、１つは、参照番号６１０に示す、ＭＲＴ−Ｒｅｄを識別するためのＶＩＤ（Ｒｅｄ  ＶＩＤと称されることもある）であり、参照番号６１２に示すもう１つのＶＩＤ（オプション）は、ベースＶＩＤまたはＳＰＶＩＤであり得る最短パスＶＩＤを識別するために用いることができる。ＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄが相互に保護するためではなく、最短パスを保護するために利用されるとき、ＶＩＤ６１２が用いられ得ることに留意されたい。
【００７２】
異なる実施形態において、サブ−ＴＬＶの値内の様々なフィールドの順序は異なっていてもよく、含まれているフィールドは図示されたものより多くても少なくてもよい。いくつかの実施形態において、フィールドの順序は、どのＶＩＤがどの目的にかなうのかを示す（例えば、１番目のＶＩＤはＢｌｕｅ  ＶＩＤ、２番目はＲｅｄ  ＶＩＤ、３番目はＳＰＶＩＤ）。代替的な実施形態において、１つまたは複数のフラグは、どのＶＩＤがどの目的にかなうのかを示す（例えば、フィールド上のフラグはＢｌｕｅ  ＶＩＤを表す）。
【００７３】
新しいＭＲＴ  ＶＩＤサブ−ＴＬＶを使用することは、ＭＲＴをデプロイするためにレイヤ２ネットワークをセットアップする一つの手法であるが、ＳＰＢインスタンスサブ−ＴＬＶを使用して、ＭＲＴをデプロイするためのレイヤ２ネットワークのセットアップに必要な情報を通信することもできる。
【００７４】
ＳＰＢインスタンスサブ−ＴＬＶにおいては、１つまたは２つのＶＬＡＮ  ＩＤタプルが存在し、ＥＣＴアルゴリズムフィールドはＭＲＴアルゴリズムのＩＤを搬送する。１つのＶＬＡＮ  ＩＤタプルが存在する場合、ベースＶＩＤフィールドはＢｌｕｅ  ＶＩＤ値を搬送する一方、ＳＰＶＩＤフィールドはＲｅｄ  ＶＩＤ値を搬送する。２つのＶＬＡＮ  ＩＤタプルが存在する場合、タプル１のベースＶＩＤフィールドはタプル２のベースＶＩＤフィールドと等しくなり、ベースＶＩＤは最短パスに用いられ得る。タプル１のＳＰＶＩＤフィールドはＢｌｕｅ  ＶＩＤを搬送し、タプル２のＳＰＶＩＤフィールドはＲｅｄ  ＶＩＤを搬送する。ＳＰＢインスタンスサブ−ＴＬＶは、同じＥＣＴアルゴリズム、Ｂｌｕｅ  ＶＩＤ、Ｒｅｄ  ＶＩＤ、およびＳＰＶＩＤ値を搬送するために異なる構成をとってもよいことに留意されたい。
【００７５】
レイヤ３ネットワークでは、ＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄの識別にマルチトポロジ識別子（ＭＴ−ＩＤ）が用いられ、この場合、ＭＴ−ＩＤはＯＳＰＦプロトコルまたはＩＳ−ＩＳプロトコルのいずれかを通じて通信される。
【００７６】
モードＡによるネットワークにおけるＭＲＴのデプロイ
【００７７】
本明細書において上述した方法によりネットワークがセットアップされたら、ネットワークにＭＲＴをデプロイすることができる。ＭＲＴはモードＡにより、すなわち完全に分散化されたＭＲＴ計算によりデプロイしてもよく、各ノードは、ネットワークのＧＡＤＡＧ計算と１つまたは複数のＭＲＴルートに対するＭＲＴ計算とを行う。
【００７８】
ネットワークのＧＡＤＡＧを計算するためには、ＧＡＤＡＧルートを識別する必要がある。一実施形態において、ＧＡＤＡＧルートの選択にはブリッジ識別子（ＩＤ）が用いられる。このブリッジＩＤは利用可能な優先度フィールドを有していることに留意されたい。ＧＡＤＡＧルートが識別されると、既知のアルゴリズムの１つを利用して、ネットワークのＧＡＤＡＧを決定することが可能になり、次いでＭＲＴルートに対するＭＲＴを計算することができる。
【００７９】
図８は、本発明の一実施形態によるＭＲＴ実装を示すブロック図である。本方法はレイヤ２ネットワークに実装することができる。本方法はトポロジ変更によってトリガされる。トポロジ変更の原因としては、図示された停止６６などのリンク停止、ノードダウン、ノード追加、またはネットワークのトポロジに影響する他のいかなる状況も考えられる。
【００８０】
図８を参照すると、すべてのノードにおいて各ノードがＰＣＥの関与なしに以下の動作を実行する。まず、各ノードがトポロジ変更を検出すると、トポロジ変更の後に生じるコンバージェンスが完了するのを待機する。ネットワークのコンバージェンスが進行している間、故障イベントの後に可能であれば、データトラフィックがリダイレクトされる。この例では、ノードＦおよび／またはＨ（ローカル修復ポイントすなわちＰＬＲ）が故障を直ちに検出し、ノードＦおよび／またはＨは、ノードについて計算された最大冗長木（ＭＲＴ）が存在する場合、故障に影響されなかった（ｓｕｒｖｉｖｅｄ）現在のＭＲＴへデータトラフィックをリダイレクトする。このＭＲＴは、それぞれがＭＲＴペアに対応する１つまたは複数のＭＲＴルートに対するものである。ノードについて計算されたＭＲＴが存在しない場合、ノードは、最短パスを計算し、対応する転送状態をインストールする。
【００８１】
次に各ノードはネットワークのＧＡＤＡＧを計算し、続いて、各ノードにおける新しいトポロジに基づいたＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄの計算が行われる。計算されたＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄに基づいて、ノードは計算されたＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄのフィルタリングデータベース（ＦＤＢ）エントリをインストールする。ＦＤＢエントリは将来のトポロジ変更における保護に利用されてもよい。
【００８２】
ＧＡＤＡＧおよびＭＲＴのすべての計算が個別のノード単位で行われるため、ノード間の通信およびノードとＰＣＥとの間の通信は最小限に抑えられるが、各ノードがすべての計算を行うことから、モードＢまたはＣの場合に比べ、ノードに高い計算能力が要求される。
【００８３】
図９は、本発明の一実施形態によるＭＲＴ実装を示すフロー図である。方法９００は、レイヤ２ネットワーク内のネットワークノード（または単にノード）おいて実装することができる。レイヤ２ネットワークには、ノード／ブリッジとしてのいくつかのネットワークエレメントが含まれており、パス計算用のスタンドアロンＰＣＥが含まれていても、含まれていなくてもよい。
【００８４】
本方法は、オプションにより、参照番号９０２においてノードがトポロジ変更を判定することから開始してもよい。トポロジ変更の原因としては、図８に示された停止６６などのリンク停止、ノードダウン、ノード追加、またはネットワークのトポロジに影響する他のいかなる状況も考えられる。トポロジ変更が判定されると、フローは参照番号９０３へ進み、ここにおいてノードは最短パスを計算し、対応する転送状態をインストールする。代替的な実施形態においては、最短パスを計算し、対応する転送状態をインストールする代わりに、ノードには計算されたＭＲＴおよび対応するインストール済みの転送状態が含まれており、この場合、ノードは、トポロジ変更に影響されなかったＭＲＴを選択し、影響されなかったＭＲＴへデータトラフィックを然るべくリダイレクトする。次いでノードは、参照番号９０４においてネットワークコンバージェンスの完了を待機する。ノードは、単にある時間、待機（例えば単に「必要な時間（ｌｏｎｇ  ｅｎｏｕｇｈ）」待機）してもよく、またはネットワークコンバージェンスが完了したという指示を受け取ってもよい。ネットワークコンバージェンスが完了したか否かの判定において、さらに高度ないくつかのアプローチを実装してもよいことに留意されたい。
【００８５】
ノードは、参照番号９０６において、ネットワークの一般化概有向非巡回グラフ（ＧＡＤＡＧ）を計算する。一実施形態においては、ブリッジＩＤがＧＡＤＡＧルートの選択に利用される。ルートが選択されると、既知のアルゴリズムの１つを利用して、ネットワークのＧＡＤＡＧを決定することができる。次に参照番号９０８において、ノードは、第１のＭＲＴ（例えばＭＲＴ−Ｂｌｕｅ）および第２のＭＲＴ（例えばＭＲＴ−Ｒｅｄ）を計算する。ＭＲＴルートごとに第１のＭＲＴおよび第２のＭＲＴのペアが存在しており、ノードには１つまたは複数のＭＲＴルートが含まれていてもよい。一実施形態において、ネットワーク内の各ノードはＭＲＴルートであり、したがって、ノードごとにＭＲＴペアを計算する必要がある。別の実施形態においては、ネットワーク内の選択されたノードのみがＭＲＴルートであり、ノードは選択されたノードについてのＭＲＴペアを計算すれば十分である。一実施形態において、ＧＡＤＡＧおよびＭＲＴの計算には、２０１３年１０月２１日付の「Ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  Ｃｏｍｐｕｔｉｎｇ  Ｍａｘｉｍａｌｌｙ  Ｒｅｄｕｎｄａｎｔ  Ｔｒｅｅ  ｆｏｒ  ＩＰ／ＬＤＰ  Ｆａｓｔ  Ｒｅｒｏｕｔｅ」と題するＩＥＴＦドラフトにおいて提案されたアルゴリズムのようなＭＲＴ  ｌｏｗｐｏｉｎｔアルゴリズムが利用される。この場合、ＭＲＴ  ｌｏｗｐｏｉｎｔアルゴリズムが１つまたは複数のＥＣＴアルゴリズムにマッピングされる。
【００８６】
次に参照番号９１０において、ノードは、計算された第１のＭＲＴおよび第２のＭＲＴ（ＭＲＴペア）に基づき、フィルタデータベース（ＦＤＢ）エントリをインストールする。ＦＤＢエントリは、ＶＩＤを特定のＭＡＣアドレスとマッピングする、〈Ｂｌｕｅ  ＶＩＤ，ＭＡＣ〉のタプルおよび〈Ｒｅｄ  ＶＩＤ，ＭＡＣ〉のタプルによって識別されてもよい。ＭＲＴ木は、「ルートから」であっても、または「ルートへ」であってもよいことに留意されたい。例えば、ユニキャストトラフィックの場合、ＭＲＴ木は典型的に「ルートへ」であり、マルチキャストトラフィックの場合、ＭＲＴ木は典型的に「ルートから」であるため、トラフィックタイプに応じて異なるＦＤＢエントリがインストールされ得る。
【００８７】
ＦＤＢエントリのインストールはトラフィック停止を引き起こさないことを目的とすべきであるという点に留意されたい。そのため、木の内の少なくとも１つは、もう一つの木がＦＤＢエントリのインストールによって更新されている間、現在の状態を維持されるべきである。一実施形態においては、３つのタイプの木が関与する。すなわち最短パス木（ＳＰＴ）、ＭＲＴ−Ｂｌｕｅ、およびＭＲＴ−Ｒｅｄである。この場合、最初にＳＰＴ木が計算されており、参照番号９０３において対応するＦＤＢエントリがインストールされる。別の実施形態においては、２つのタイプの木が関与する。すなわちＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄである。両方の実施形態において、参照番号９１０で、ノードは１つの木ずつＦＤＢを更新する。例えば、まずＭＲＴ  ＢｌｕｅのＦＤＢエントリをインストールし、その後、対応するＭＲＴ  ｒｅｄのＦＤＢエントリをインストールする。
【００８８】
参照番号９０２〜９０４は、方法９００のオプションのステップであることに留意されたい。参照番号９０６〜９１０におけるＧＡＤＡＧおよびＭＲＴペアの計算は、ネットワーク開始プロセスといった他のシナリオでトリガされてもよい。方法９００がネットワークのノードにデプロイされるには、使用されるＥＣＴアルゴリズム、ＭＲＴ−Ｂｌｕｅ、ＭＲＴ−Ｒｅｄ、およびＳＰＴ（該当する場合）のＶＩＤ値に関して、ノード間の合意が必要であることにも留意されたい。すなわち、図６〜図７に関連する説明で開示されたプロセスまたはノード間のセットアップ一貫性を提供する別のプロセスが完了していることである。
【００８９】
モードＢによるネットワークにおけるＭＲＴのデプロイ
【００９０】
ＭＲＴデプロイメントモードＢ（集中化して計算されるＧＡＤＡＧモード）は、スタンドアロンＰＣＥを利用してネットワークのＧＡＤＡＧ計算を実行する一方で、ネットワークのノードに個別にＭＲＴペアを計算させる。モードＡと同様、ネットワークのＧＡＤＡＧを計算するためには、ＧＡＤＡＧルートを識別する必要があり、一実施形態において、ＧＡＤＡＧルートの選択にはブリッジＩＤが用いられる。
【００９１】
図１０は、本発明の一実施形態による別のＭＲＴ実装を示すブロック図である。本方法はレイヤ２またはレイヤ３ネットワークに実装することができる。このプロセスはトポロジ変更によってトリガされる。トポロジ変更の原因としては、図示された停止６６などのリンク停止、ノードダウン、ノード追加、またはネットワークのトポロジに影響する他のいかなる状況も考えられる。
【００９２】
図１０を参照すると、タスクボックスＩおよびＩＩは、本発明の一実施形態に従って動作が実行される順序を示している。タスクボックスＩでは、ＰＣＥにトポロジ変更が通知された後、ＰＣＥはネットワークコンバージェンスが完了するのを待機する。次にネットワークのＧＡＤＡＧを計算する。続いて、計算されたＧＡＤＡＧを記述するＧＡＤＡＧ記述子をアセンブルする。ＧＡＤＡＧ記述子は次いでネットワークのノードに配信される。
【００９３】
タスクボックスＩＩでは、各ノードがＧＡＤＡＧ記述子を受信し、１つまたは複数のＭＲＴルートの各々に対してＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄを計算する。次にノードは各自の転送状態を更新する。当該ネットワークがレイヤ２ネットワークである場合、ノードは、ＭＲＴ−ＢｌｕｅおよびＭＲＴ−ＲｅｄのＶＩＤにそれぞれ対応するＦＤＢエントリをインストールする。当該ネットワークがレイヤ３ネットワークである場合、ノードは、ｆｏｒｗａｒｄ  ｉｎｆｏｒｍａｔｉｏｎ  ｂａｓｅ（ＦＩＢ）エントリをインストールする。
【００９４】
ＧＡＤＡＧとＭＲＴの計算とがＰＣＥとノードの間で分散されるため、ノード間で共通であるＧＡＤＡＧの計算はノードにおいて繰り返されることがなく、よって、モードＢでＭＲＴをデプロイするノードでは、モードＡでＭＲＴをデプロイするノードに比べ、計算の負担が緩和される。一方、モードＢは、ＰＣＥで計算されたＧＡＤＡＧをノードに通信する必要があるので、ＰＣＥとノードとの間で必要となる通信が増えるが、ＰＣＥからノードへ単一のＰＤＵを１回のみ送信すれば済む。
【００９５】
図１１は、本発明の一実施形態によるＧＡＤＡＧの計算および配信を示すフロー図である。方法１１００は、レイヤ２またはレイヤ３ネットワークにおいて、いくつかのノードが含まれているネットワークのＰＣＥにおいて実装することができる。
【００９６】
本方法は、オプションにより、参照番号１１０２においてＰＣＥがネットワークのトポロジ変更を判定することから開始してもよい。トポロジ変更の原因としては、図１０に示された停止６６などのリンク停止、ノードダウン、ノード追加、またはネットワークのトポロジに影響する他のいかなる状況も考えられる。トポロジ変更が判定されると、フローは参照番号１１０４へ進み、ここにおいてＰＣＥはネットワークコンバージェンスの完了を待機する。ＰＣＥは、単にある時間、待機（すなわち「必要な時間」待機）してもよく、またはネットワークコンバージェンスが完了したという指示を受け取ってもよい。
【００９７】
ＰＣＥは、参照番号１１０６において、ネットワークの一般化概有向非巡回グラフ（ＧＡＤＡＧ）を計算する。一実施形態においては、ブリッジＩＤがＧＡＤＡＧルートの選択に利用される。ルートが選択されると、既知のアルゴリズムの１つを利用して、ネットワークのＧＡＤＡＧを決定することができる。次に参照番号１１０８において、ＰＣＥは、計算されたＧＡＤＡＧのＧＡＤＡＧ記述をアセンブルする。
【００９８】
計算されたＧＡＤＡＧは、グラフの辺（すなわちネットワークのリンク）のリストによって記述されてもよく、１つの辺がノードの識別子（ＩＤ）およびポート識別子（ＩＤ）によって表現されてもよい。図１２は、本発明の一実施形態による、ＧＡＤＡＧ記述を配信するための明示パス（ＥＰ）サブ−ＴＬＶを示す。ＥＰサブ−ＴＬＶには、サブ−ＴＬＶのタイプを示すタイプフィールド１２０２が含まれており、またサブ−ＴＬＶの長さを示す長さフィールド１２０４も含まれている。さらに、計算されたＧＡＤＡＧの辺の表現も含まれている。計算されたＧＡＤＡＧの辺は、一実施形態によるリストに含まれている。１つの辺は、１つのノードのＩＤおよび１つのポートＩＤが含まれているタプルによって表現することができる。ノードのＩＤは、システムＩＤ、ＩＰアドレス、ＭＡＣアドレス、またはブリッジＩＤとすることができる。ポートＩＤは、レイヤ３  ＩＳ−ＩＳ用語における回路ＩＤ、レイヤ２  ＩＥＥＥ  ８０２．１用語におけるブリッジポート、またはノードにおけるポートを表す他のいかなる表現であってもよい。
【００９９】
図１２を参照すると、参照番号１２１２におけるＧＡＤＡＧの第１の辺は、参照番号１２０６においてＧＡＤＡＧの辺の下位の頂点を識別するノードのＩＤ＃１、および、ＧＡＤＡＧ辺の上位の頂点に連結するポートを識別するポートＩＤ＃１によって表される。上位または下位の頂点は、ＧＡＤＡＧによって提供される半順序に従っている。同様に、参照番号１２１４におけるＧＡＤＡＧの第２の辺は、それぞれ参照番号１２１０におけるノードのＩＤ＃２および参照番号１２１２におけるポートＩＤ＃２によって表される。
【０１００】
ＧＡＤＡＧ記述は、ＧＡＤＡＧルートを表してもよいことに留意されたい。一実施形態において、ＧＡＤＡＧルートは、例えば、ＧＡＤＡＧ記述のＥＰサブ−ＴＬＶの第１の頂点がＧＡＤＡＧルートであるというように、頂点の順序によって表されてもよい。別の実施形態において、ＧＡＤＡＧルートはフラグによって表されてもよい。これに代えて、ＧＡＤＡＧ記述がＧＡＤＡＧルートを表していないとき、各ノードが単独で、例えば、辺のブリッジＩＤに基づいてＧＡＤＡＧルートを決定してもよい。ＧＡＤＡＧ記述のＥＰサブ−ＴＬＶはＧＡＤＡＧ記述子と称されてもよい。本発明の原理によるＥＰサブ−ＴＬＶを使用せずに、他のＧＡＤＡＧ記述も実装され得ることに留意されたい。
【０１０１】
オプションにより、同じリンク状態パケット（ＬＳＰ）内で、ＧＡＤＡＧ記述と共に署名（すなわち計算実行の基礎となったトポロジのダイジェスト）を保持すると有用であろう。このようにすれば、トポロジダイジェストを計算する各ノードは、ＧＡＤＡＧが関連しているか否かを検証することができる。ダイジェストが一致しない場合は、ＰＣＥの把握しているネットワークトポロジがネットワークノードの把握しているものと異なるので、ダイジェストが一致するまで、ネットワークノードはＧＡＤＡＧ記述内で保持されたＧＡＤＡＧを格納するだけでよく、それ以上の対応は行わない。
【０１０２】
図１１を再び参照すると、ＧＡＤＡＧ記述はアセンブルされると、次いで参照番号１１１０においてネットワーク内のノードに配信される。一実施形態において、ＧＡＤＡＧ記述は、図１２に示したようなサブ−ＴＬＶが含まれている１つまたは複数のＬＳＰ内で、ノードにフラッディングされる。
【０１０３】
参照番号１１０２〜１１０４は、方法９００のオプションのステップであることに留意されたい。参照番号１１０６〜１１１０におけるＧＡＤＡＧおよびＭＲＴペアの計算は、ネットワーク開始プロセスといった他のシナリオでトリガされてもよい。方法９００がネットワークのノードにデプロイされるには、使用されるＥＣＴアルゴリズム、ＭＲＴ−Ｂｌｕｅ、ＭＲＴ−Ｒｅｄ、およびＳＰＴ（該当する場合）のＶＩＤ値に関して、ノード間の合意が必要であることにも留意されたい。すなわち、図６〜図７に関連する説明で開示されたプロセスまたはノード間のセットアップ一貫性を提供する別のプロセスが完了していることである。
【０１０４】
ＧＡＤＡＧ記述がネットワーク内のノードに配信された後、ノードは次いでＧＡＤＡＧ記述に基づきＭＲＴペアを計算する。図１３は、本発明の一実施形態によるＭＲＴペアの計算を示すフロー図である。方法１３００は、レイヤ２ネットワーク内のノードにおいて実装することができる。
【０１０５】
参照番号１３０２において、ノードはＧＡＤＡＧ記述を受信する。一実施形態において、ＧＡＤＡＧ記述は、図１２に示すＥＰサブ−ＴＬＶが含まれているＬＳＰ内に埋め込まれてもよい。本明細書において上述したように、オプションにより、ＧＡＤＡＧ記述を保持するＬＳＰと同じＬＳＰで署名（すなわち計算実行の基礎となったトポロジのダイジェスト）も保持してよい。このようにすれば、トポロジダイジェストを計算するノードは、ＧＡＤＡＧが関連しているか否かを検証することができる。ダイジェストが一致しない場合は、ＰＣＥとネットワークノードが把握しているネットワークトポロジが互いに異なるので、ダイジェストが一致するまで、ネットワークノードはＧＡＤＡＧ記述内で保持されたＧＡＤＡＧを格納するだけでよく、それ以上の動作は行わない。
【０１０６】
ＧＡＤＡＧが有効である場合、参照番号１３０４において、ノードは、ＧＡＤＡＧ記述に基づき、１つまたは複数のＭＲＴルートに対するＭＲＴ−ＢｌｕｅおよびＭＲＴ−Ｒｅｄを計算する。一実施形態において、ネットワークの各ノードはＭＲＴルートであり、したがって、ＭＲＴペアの計算はノードごとに実行される。別の実施形態においては、選択されたノードのみがＭＲＴルートであり、ノードは選択されたノードについてのＭＲＴペアを計算すれば十分である。
【０１０７】
一実施形態において、ＭＲＴルートの選択は、例えば、ＭＲＴルートであるネットワークノードにＭＲＴルートフラグを設定することにより、ＧＡＤＡＧ記述内で符号化される。別の実施形態において、ＬＳＰ、ＳＮＭＰ  ＰＤＵ、またはＯｐｅｎＦｌｏｗ制御パケットなどの１つまたは複数のメッセージにおいて、ＭＲＴルート選択が符号化される。別の実施形態において、ＭＲＴルートはネットワークノードにおいてローカルで構成されており、このＭＲＴルートは当該ネットワークノードによって、例えば、ＬＳＰまたはＬＳＡ内でアドバタイズされてもよい。
【０１０８】
参照番号１３０６において、ノードは、計算されたＭＲＴペアに基づき、ＦＤＢエントリをインストールする。ＦＤＢエントリは、ＶＩＤを特定のＭＡＣアドレスとマッピングする、〈Ｂｌｕｅ  ＶＩＤ，ＭＡＣ〉のタプルおよび〈Ｒｅｄ  ＶＩＤ，ＭＡＣ〉のタプルに関連付けられてもよい。ＭＲＴ木は、「ルートから」であっても、または「ルートへ」であってもよいことに留意されたい。例えば、ユニキャストトラフィックの場合、ＭＲＴ木は典型的に「ルートへ」であり、マルチキャストトラフィックの場合、ＭＲＴ木は典型的に「ルートから」であるため、トラフィックタイプに応じて異なるＦＤＢエントリがインストールされ得る。
【０１０９】
モードＡと同様、ＦＤＢエントリのインストールはトラフィック停止を引き起こさないことを目的とすべきであり、木の内の少なくとも１つは、もう一つの木がＦＤＢエントリのインストールによって更新されている間、現在の状態を維持されるべきである。
【０１１０】
方法１３００はレイヤ２ネットワーク内のノードにおいて実装することができるが、図１４は、本発明の別の実施形態によるＭＲＴペアの計算を示す。方法１４００は、レイヤ３ネットワーク内のノードにおいて実装することができる。方法１４００は、方法１４００がレイヤ３で実行されることを除けば、方法１３００に似ている。つまり、参照番号１４０２において受信されるＧＡＤＡＧ記述はレイヤ３通信に最適化された異なるフォーマットであり得る。参照番号１４０４におけるＭＲＴルートに対するＭＲＴペアの計算は参照番号１３０４と同様であってもよい。参照番号１４０６において、ノードは、計算されたＭＲＴペアに基づき、ｆｏｒｗａｒｄ  ｉｎｆｏｒｍａｔｉｏｎ  ｂａｓｅ（ＦＩＢ）エントリをインストールする。ＦＩＢエントリは、各ＭＲＴルートに対するｂｌｕｅ  ＭＴ  ＩＤおよびｒｅｄ  ＭＴ  ＩＤに関連付けられてもよい。
【０１１１】
ＳＤＮまたはＮＦＶにおける実施形態
【０１１２】
ＭＲＴのデプロイについて、統合制御プレーンおよびデータプレーンがネットワークエレメントに含まれているような、従来のネットワークなどの汎用データネットワークを対象として検討してきたが、本発明の実施形態はこれに限定されない。このような検討は、制御機能とデータ転送機能とが分離され得るｓｏｆｔｗａｒｅ  ｄｅｆｉｎｅｄ  ｎｅｔｗｏｒｋｉｎｇ（ＳＤＮ）システムおよびｎｅｔｗｏｒｋ  ｆｕｎｃｔｉｏｎ  ｖｉｒｔｕａｌｉｚａｔｉｏｎ（ＮＦＶ）といった、新しいネットワーキング技術と十分に融合され得る。
【０１１３】
図１５は、ＳＤＮネットワークを示すブロック図である。ＳＤＮネットワーク１５００は、いくつかの転送要素と、転送要素の転送挙動を指示するいくつかのコントローラとを備えている。ＳＤＮネットワークには、はるかに多数のネットワークエレメントが含まれていてもよく、既存のネットワークエレメントはＳＤＮ互換プロトコルで実装されていてもよく、よってＳＤＮネットワークの一部となってもよいことに留意されたい（例えば、既存のＩＰルータがＯｐｅｎＦｌｏｗプロトコルをサポートしてもよく、よってＳＤＮ転送要素またはＳＤＮコントローラとなってもよい）。したがって、ＳＤＮネットワーク１５００は、論理ＳＤＮネットワーク構成のみを示すためのものである。
【０１１４】
転送要素
【０１１５】
ＳＤＮ転送要素（ＳＤＮがＯｐｅｎＦｌｏｗ規格に準拠しているとき、ＯｐｅｎＦｌｏｗ用語ではＯｐｅｎＦｌｏｗスイッチまたは単にスイッチと称される）の主なタスクは、１つまたは複数のＳＤＮコントローラによってプログラムされたフローテーブル内のルールに従い、ＳＤＮ転送要素内のパケットを入口ポートから出口ポートへ転送することである。各フローエントリには、所与のポートへのパケットの転送、パケットヘッダ内の特定のビットの修正、ＳＤＮコントローラに対するパケットのカプセル化、またはパケットのドロップといった動作のセットが含まれている。新しいフローにおける最初のパケットの場合、転送要素は、しばしば、このパケットをＳＤＮコントローラへ転送して新しいフローのプログラミングをトリガする。また、転送要素は、Ｉｎｔｅｒｎｅｔ  Ｃｏｎｔｒｏｌ  Ｍｅｓｓａｇｅ  Ｐｒｏｔｏｃｏｌ（ＩＣＭＰ）パケットなどのスローパスパケットを処理のためにＳＤＮコントローラへ転送するのにも用いられ得る。フローの概念は、例えば、ＴＣＰ接続、または特定のＭＡＣアドレスもしくはＩＰアドレスからのすべてのトラフィックというように、広義に規定され得ることに留意されたい。同様に、ＳＤＮネットワーク内のパケットも広義に規定されており、Ｅｔｈｅｒｎｅｔフレーム、ＩＰネットワークパケット、またはプロプライエタリフォーマットのメッセージであってもよいことに留意されたい。
【０１１６】
ＳＤＮコントローラ
【０１１７】
ＳＤＮコントローラ（しばしばリモートコントローラまたはコントローラと称される）は、フローテーブルのフローエントリの追加および削除を行う。ＳＤＮコントローラは、ＳＤＮ転送要素のセットおよび他のネットワークエレメントの間の相互接続ならびにルーティングを規定する。また、ＳＤＮ転送要素のセットから情報を収集し、ＳＤＮ転送要素に転送／ルーティング命令を配信するといった、ネットワーク状態の配信を取り扱う。ＳＤＮコントローラはまた、新規アドレス指定アプリケーション、ルーティングアプリケーション、および複雑なパケット処理アプリケーションをサポートするようにプログラムすることもできる。ＳＤＮコントローラは、ＳＤＮネットワークのいわば「頭脳」である。転送要素は正しく機能するために少なくとも１つのＳＤＮコントローラに接続する必要がある。
【０１１８】
図１５を参照すると、ＳＤＮネットワーク１５００には、ＳＤＮコントローラ１５５２および転送要素（またはＳＤＮスイッチ、「転送要素」および「ＳＤＮスイッチ」という用語は、本明細書において以降、交換可能に用いられる）Ａ〜Ｇのセットが含まれている。コントローラ１５５２（「コントローラ」および「ＳＤＮコントローラ」という用語は、本明細書において以降、交換可能に用いられる）は、ＳＤＮスイッチＡ〜Ｇを管理し、ＳＤＮスイッチは自身を管理するコントローラに通信チャネルを介して接続しており、ＳＤＮスイッチは必ずしもコントローラへの直接接続を有してはいない（「リモート」コントローラという用語の所以）。
【０１１９】
論理的に、ＳＤＮスイッチには２つの主要コンポーネントが含まれていると考えることができる。片方は制御プレーンエンティティであり、他方は転送プレーンエンティティである。参照番号１５５４におけるＳＤＮスイッチＣの拡大図は、２つのプレーンエンティティを示している。ＳＤＮスイッチＣには、制御プレーンエンティティ１５６２および転送プレーンエンティティ１５６４が含まれている。制御プレーンエンティティ１５６２は、ＳＤＮスイッチＣの管理および構成をコーディネートする。転送プレーンエンティティ１５６４の構成は、ホストプロセッサ１５７２上でアプリケーションを実行することによって達成される。ホストプロセッサ１５７２は、通常、周知の開発環境を提供するためにオペレーティングシステムを実行する。ホストプロセッサ１５７２からのコマンドは、相互接続（例えばｐｅｒｉｐｈｅｒａｌ  ｃｏｍｐｏｎｅｎｔ  ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バス）を使用して、スイッチプロセッサ１５７４へ送信される。例外パケット（例えば、ルーティングおよび管理用のパケット）は、しばしばホストプロセッサ１５７２上で処理される。スイッチプロセッサ１５７４は、ＳＤＮスイッチＣの様々な転送ポート１５７８と情報をやり取りして、着信パケットおよび発信パケットの転送その他の処理を行う。
【０１２０】
転送プレーンエンティティ１５６４は、トラフィックの転送（転送動作はスイッチング、ルーティング、ラーニング（ｌｅａｒｎｉｎｇ）などを含む）を担当する。転送プレーンエンティティには、より複雑で柔軟性に富む開発環境を犠牲にして高スループットを提供するように設計されたスイッチプロセッサ１５７４が含まれている。スイッチプロセッサ１５７４には、高スループットを達成するために、多種多様な高性能のメモリおよびハードウェアアクセラレータがしばしば搭載されている。対照的に、ホストプロセッサ１５７２においては、データパケットよりも制御パケット（しばしばスローパスパケットと称される）を処理することの方が多く、スループットがそれほどミッションクリティカルな要件とはならないため、高スループットの達成を犠牲にすることで複雑性および柔軟性が実現され得る。ＳＤＮスイッチ（例えばＳＤＮスイッチＣ）は、新しいフローに関連付けられたパケットを受信したとき、そのパケットをどこへ転送すべきか知らない。そのため、この例では、自身を管理するＳＤＮコントローラ（ＰＣＥ）１５５２へパケットを送信する。コントローラ１５５２は、パケットを受信すると、新しいフローエントリをプログラムし、ＳＤＮスイッチＣへ送信する。ＳＤＮスイッチＣは次に、新しいフローエントリに従ってそのパケットを転送する。
【０１２１】
ＳＤＮネットワークは、集中化して計算されるＭＲＴモード（モードＣ）を実装するのに理想的なプラットフォームであると考えられる。この場合、ＰＣＥ（ＳＤＮコントローラ）１５５２は、ＧＡＤＡＧとＭＲＴ両方の計算を実行し、計算結果を当該ネットワーク内のすべてのノード（ＳＤＮスイッチ）に配信して、ネットワークトポロジの変更時に、各スイッチがそれぞれのＦＤＢおよびＦＩＢエントリをインストールできるようにする。
【０１２２】
ＳＤＮネットワークはまた、集中化して計算されるＧＡＤＡＧモード（モードＢ）を実装するために用いることもできる。この場合、ＰＣＥ１５５２は、（図１１および図１２に示したように）ＧＡＤＡＧ計算を実行し、ＧＡＤＡＧ記述を配信する。ネットワークトポロジの変更時に、（図１３および図１４に示したように）すべてのノードがＭＲＴペアを計算し、それぞれのＦＤＢおよびＦＩＢエントリをインストールする。
【０１２３】
ＭＲＴデプロイメントをサポートするネットワークエレメント
【０１２４】
図１６は、本発明の一実施形態に従い、ＭＲＴをデプロイする方法を実装する２つのネットワークエレメントを示すブロック図である。すなわち、ネットワークノードとして機能するネットワークエレメントおよびＰＣＥとして機能する別のネットワークエレメントを含む、２つのネットワークエレメントである。図示するように、ネットワークエレメント１６０１とパス制御要素１６１２との間には通信が行われている。図１６に示すネットワークエレメント１６０１の例は、スイッチングファブリック１６０７と、１６０８および１６０９などのいくつかのデータカードと、少なくとも受信機（Ｒｘ）インターフェース１６１０と、少なくとも送信機Ｔｘインターフェース１６１１とを含む、データプレーンを備えている。ＲｘインターフェースおよびＴｘインターフェース１６１０および１６１１はネットワーク上のリンクとインターフェースをとり、データカード１６０８および１６０９は、インターフェース１６１０および１６１１を介して受信したデータに対して機能を実行し、スイッチングファブリック１６０７は、データカード間および類似の入力／出力（Ｉ／Ｏ）カード間でデータを切り替える。
【０１２５】
ネットワークエレメント１６０１はまた制御プレーンを備え、制御プレーンは、ＭＲＴをデプロイするように構成された制御ロジックが含まれている１つまたは複数のプロセッサ１６０２を含む。他のプロセスも同様に制御ロジックに実装されていてもよい。
【０１２６】
ネットワークエレメント１６０１はまたメモリ１６０３を備え、メモリは制御プロトコルのソフトウェア１６０４、プロトコルスタック１６０５、および１つまたは複数のデータベース１６０６を格納している。制御プロトコルのソフトウェア１６０４には、ＭＲＴをデプロイすることに関連付けられたデータおよび命令が含まれていてもよい。プロトコルスタック１６０５は、ネットワークエレメント１６０１によって実装される方法および／またはプロトコルを格納している。データベースは、転送パスエントリを決定して格納するために用いられる。例えば、ＦＤＢまたはＦＩＢエントリはデータベース１６０６に格納されてもよい。
【０１２７】
ネットワークエレメント１６０１には、自身がＭＲＴをデプロイする機能を実行できるようにし、通信ネットワーク上のネットワークエレメントに共通に実装される他の機能を実行できるようにする、他のソフトウェア、プロセス、および情報のストアが含まれていてもよい。
【０１２８】
ネットワークエレメント１６０１に結合されたＰＣＥ１６１２は、メモリ１６１４に結合された１つまたは複数のプロセッサ１６１３を含む。プロセッサ１６１３は、パス計算動作およびネットワークエレメント１６０１の命令に対する動作を実行するロジックを含む。メモリ１６１４は、本明細書で説明したＧＡＤＡＧおよびＭＲＴを計算するために適用可能なパス計算ソフトウェア１６１５を含む。メモリ１６１４はまたデータベース１６１６を含む。データベースは、ネットワークエレメント１６０１によって格納されたデータベースのレプリカを含んでもよく、例えば、ＧＡＤＡＧおよび／またはＭＲＴ計算のためのさらに別のデータベースを含んでもよい。
【０１２９】
一実施形態において、ネットワークエレメント１６０１およびＰＣＥ１６１２は、レイヤ２ネットワークの一部であり、他のネットワークエレメントと通信可能に結合されている。ネットワークエレメント１６０１は、モードＡで動作して、図６に示したＭＲＴ  ＶＩＤサブ−ＴＬＶ６００などのネットワークセットアップをアドバタイズし、受信してもよい。ネットワークエレメント同士は、セットアップフェーズ後に同じネットワークセットアップに合意する。次いでトポロジが変更されると、ネットワークエレメント１６０１は、図９に関連して上記に説明した方法を実行する。ここで最短パス、ＧＡＤＡＧ、およびＭＲＴペアの計算は、プロセッサ１６０２およびメモリ１６０３によって実行されてもよい。
【０１３０】
別の実施形態において、ネットワークエレメント１６０１はモードＢで動作する。ネットワークエレメント、別のネットワークエレメント、またはＰＣＥ１６１２は、図６に示したＭＲＴ  ＶＩＤサブ−ＴＬＶ６００などのネットワークセットアップをアドバタイズし、受信してもよい。ネットワークエレメント同士は、セットアップフェーズ後に同じネットワークセットアップに合意する。ＰＣＥ１６１２は、トポロジ変更を判定すると、図１１および図１２に関連して上記に説明した方法を実行する。ここでＰＣＥ１６１２によってＧＡＤＡＧが計算されてＧＡＤＡＧ記述が配信されるが、ＧＡＤＡＧの計算はプロセッサ１６１３およびメモリ１６１４によって実行されてもよい。次いでネットワークエレメント１６０１は、図１３および図１４に関連して上記に説明した方法を実行してもよい。
【０１３１】
図１７は、本発明の一実施形態に従い、ＭＲＴをデプロイする方法を実装する１つのネットワークエレメント示すブロック図である。図１７が示すように、ネットワークエレメント１７０１は同様にパス計算ソフトウェアをホストしてもよい。よって、図１７に示すネットワークエレメント１７０１の例は、スイッチングファブリック１７０８と、１７０９および１７１０などのいくつかのデータカードと、少なくとも受信機（Ｒｘ）インターフェース１７１１と、少なくとも送信機（Ｔｘ）インターフェース１７１２とを含む、データプレーンを備える。ＲｘインターフェースおよびＴｘインターフェース１７１１および１７１２はネットワーク上のリンクとインターフェースをとり、データカード１７０９および１７１０は、インターフェース１７１１および１７１２を介して受信したデータに対して機能を実行し、スイッチングファブリック１７０８は、データカード間および／または他のＩ／Ｏカード間でデータを切り替える。ネットワークエレメント１７０１はまた制御プレーンを備え、制御プレーンは、ＭＲＴをデプロイするように設定された制御ロジックが含まれている１つまたは複数のプロセッサ１７０２を含む。
【０１３２】
一実施形態において、ネットワークエレメント１７０１は、モードＡで動作して、図６に示したＭＲＴ  ＶＩＤサブ−ＴＬＶ６００などのネットワークセットアップをアドバタイズし、受信してもよい。ネットワークエレメント同士は、セットアップフェーズ後に同じネットワークセットアップに合意する。次いでトポロジが変更されると、ネットワークエレメント１７０１は、図９に関連して上記に説明した方法を実行する。ここで最短パス、ＧＡＤＡＧ、およびＭＲＴペアの計算は、プロセッサ１７０２およびメモリ１７０３によって実行されてもよい。
【０１３３】
図１８は、本発明の一実施形態に従い、ＧＡＤＡＧを計算し、配信するための方法を実装する１つのネットワークエレメント示すブロック図である。ネットワークエレメント１８００は、複数のネットワークエレメントが含まれているネットワークのＰＣＥとして機能する。ＰＣＥ１８００には、計算部１８０２、アセンブル部１８０４、および配信部１８０６が含まれている。オプションにより、ネットワークエレメント１８００にはさらに判定部１８０８および待機部１８１０が含まれている。
【０１３４】
一実施形態において、計算部１８０２はネットワークのＧＡＤＡＧを計算し、ＧＡＤＡＧはネットワークのグラフ抽象化であり、複数のネットワークエレメントはＧＡＤＡＧの頂点でありかつ複数のネットワークエレメントを接続するリンクはＧＡＤＡＧの辺である。アセンブル部１８０４は、計算されたＧＡＤＡＧに基づいてＧＡＤＡＧ記述子をアセンブルし、配信部１８０６はＧＡＤＡＧ記述子を複数のネットワークエレメントに配信し、複数のネットワークエレメントの各々は、ＧＡＤＡＧ記述子を利用して、トラフィックを転送するための最大冗長木を計算する。一実施形態において、ネットワークエレメント１８００の判定部１８０８はネットワークのトポロジ変更を判定し、待機部１８１０は、ネットワークエレメント１８００が計算部１８０２にネットワークのＧＡＤＡＧを計算させることに先立ち、ネットワークコンバージェンスの完了を待機する。
【０１３５】
本明細書において図中のフロー図は本発明のある実施形態によって実行される動作の特定の順序を示すが、そのような順序は例示である（例えば、代替的な実施形態は、当該動作を異なる順序で実行し、ある動作を組み合わせ、ある動作を重複させるなどを成し得る）ことを理解すべきである。
【０１３６】
本発明をいくつかの実施形態の観点から説明してきたが、本発明は説明された実施形態に限定されず、添付の特許請求の範囲の趣旨および範囲の内における変形および代替により実施され得ることを当業者は認識するであろう。したがって、上記の説明は、限定ではなく例示として考えられるべきである。
【図１】
2017510137.tif 000003
【図２】
2017510137.tif 000004
【図３】
2017510137.tif 000005
【図４】
2017510137.tif 000006
【図５】
2017510137.tif 000007
【図６】
2017510137.tif 000008
【図７】
2017510137.tif 000009
【図８】
2017510137.tif 000010
【図９】
2017510137.tif 000011
【図１０】
2017510137.tif 000012
【図１１】
2017510137.tif 000013
【図１２】
2017510137.tif 000014
【図１３】
2017510137.tif 000015
【図１４】
2017510137.tif 000016
【図１５】
2017510137.tif 000017
【図１６】
2017510137.tif 000018
【図１７】
2017510137.tif 000019
【図１８】
2017510137.tif 000020
【国際調査報告】
2017510137.tif 000021
2017510137.tif 000022