(57)【要約】  所定の範囲の値から選択されたVIDのようなリンク識別子は、リンクステートプロトコル制御のEthernetネットワークの各ノードにより、そのリンク又は隣接関係のそれぞれにローカルで割り当てられる。リンク識別子は、ノードの各リンク又は隣接関係が異なるリンク識別子により一意に識別されるように、ノードにより割り当てられる。リンクステートプロトコルの隣接関係通知機構又は他のフラッディング機構は、ローカルで割り当てられたリンク識別子をリンクステートプロトコル制御のEthernetネットワークの他のノードに配布するために使用される。リンク識別子は、ノードによりトポロジデータベースに追加され、迂回路ルートがネットワークのノードにより分散してローカルで計算されることを可能にする。障害の発生時に、トラヒックがリンクステートプロトコル制御のEthernetネットワークを横断し続け得るように、リンク識別子は、障害の周囲のトラヒックをソースルーティングするために使用される。
2013524557.tif 000002
【特許請求の範囲】
【請求項１】
リンクステートプロトコル制御のEthernetネットワークでの障害回復方法であって、
前記リンクステートプロトコル制御のEthernetネットワークの各ノードにより、リンクステートルーティングプロトコルを実施するステップと、
前記リンクステートプロトコル制御のEthernetネットワークのノードにより、リンク識別子を隣接関係又は出力リンクのそれぞれに割り当てるステップと、
前記リンクステートプロトコル制御のEthernetネットワークの各ノードにより、隣接関係又はリンクのリストと、対応する割り当てられたリンク識別子とを含むリンクステートルーティングプロトコルのリンクステート広告を送信するステップと、
前記リンクステートプロトコル制御のEthernetネットワークの前記ノードにより、前記ネットワークでの障害の際に使用する隣接関係の周囲の１ホップの迂回路を判定するために、隣接ノードのリンク識別子を使用して迂回路ルートを計算するステップと
を有する方法。
【請求項２】
前記割り当てられたリンク識別子は、仮想ローカルエリアネットワーク識別子（VID：Virtual  Local  Area  Network  Identifier）である、請求項１に記載の方法。
【請求項３】
前記VIDは、前記リンクステートプロトコル制御のEthernetネットワークの分散した障害回復に関して使用されるために確保されたVIDの範囲から割り当てられる、請求項２に記載の方法。
【請求項４】
前記VIDの範囲は、前記リンクステートプロトコル制御のEthernetネットワークにおける各ノードの想定される隣接関係のほぼ最大数を包含する、請求項２に記載の方法。
【請求項５】
前記VIDの範囲は、前記リンクステートプロトコル制御のEthernetネットワークにおける各ノードの想定される隣接関係の最大数のほぼ２倍を包含する、請求項２に記載の方法。
【請求項６】
前記リンクステートプロトコル制御のEthernetネットワークの前記ノードは、２つのリンク識別子を隣接関係又は出力リンクのそれぞれに割り当て、等価コストマルチパストラヒックが前記迂回路ルートで区別されることを可能にする、請求項５に記載の方法。
【請求項７】
前記ノードのうち１つにより、MACヘッダを有し、前記リンクステートプロトコル制御のEthernetネットワークで転送されるデータを含むプロトコルデータユニットを受信するステップと、
前記MACヘッダからのアプリケーションVIDを、前記リンク識別子のうち１つに置換するステップと、
前記迂回路ルートで前記プロトコルデータユニットを転送するステップと
を更に有する、請求項１に記載の方法。
【請求項８】
前記アプリケーションVIDを置換するステップは、前記プロトコルデータユニットを前記ネットワークを通じた意図したパスに戻させる前記迂回路ルートの第１のノードの第１の出力リンクを判定し、前記アプリケーションVIDを、前記第１のノードにより前記第１の出力リンクに割り当てられた第１のリンク識別子に置換し、前記プロトコルデータユニットを前記第１のノードに転送することを有する、請求項７に記載の方法。
【請求項９】
迂回路パスの前記第１のノードにより、前記迂回路ルートの第２のノードの入力リンクの第２のリンク識別子を判定するステップと、
前記第１のリンク識別子を前記第２のリンク識別子に置換するステップと、
前記プロトコルデータユニットを前記第２のノードに転送するステップと
を更に有する、請求項８に記載の方法。
【請求項１０】
前記第２のノードにより前記プロトコルデータユニットを受信するステップと、
前記第２のノードにより、前記プロトコルデータユニットが、前記第２のノードにより前記入力リンクに割り当てられたVIDに一致する第２のVIDを有することを判定するステップと、
前記第２のVIDを前記アプリケーションVIDに置換するステップと
を更に有する、請求項９に記載の方法。
【請求項１１】
ネットワークでトラヒックを転送する方法であって、
前記ネットワークの障害を検出するステップと、
データトラヒックが前記ネットワークの障害を通じて送信されることを必要とする、前記ネットワークの宛先に転送されるデータトラヒックを受信するステップであり、前記データトラヒックは、プロトコルデータユニットにフォーマットされ、前記プロトコルデータユニットのそれぞれは、少なくとも１つの仮想ローカルエリアネットワーク識別子（VID：Virtual  Local  Area  Network  Identifier）を有するMACヘッダを含むステップと、
前記VIDを、迂回路ノードにより前記迂回路ノードを前記障害を越えて前記宛先の方のノードに接続する出力リンクに割り当てられたVIDに置換するステップと、
前記データトラヒックを前記迂回路ノードに転送するステップと
を有する方法。
【請求項１２】
ルーティングされるEthernetネットワークでトラヒックを転送する方法であって、
前記ルーティングされるEthernetネットワークの第１のノードにより、前記ネットワークで宛先に転送されるデータトラヒックを受信するステップであり、前記データトラヒックは、プロトコルデータユニットにフォーマットされ、前記プロトコルデータユニットのそれぞれは、少なくとも１つの仮想ローカルエリアネットワーク識別子（VID：Virtual  Local  Area  Network  Identifier）を有するMACヘッダを含むステップと、
前記VIDを読み取るステップと、
前記VIDが前記ルーティングされるEthernetネットワークで分散した障害回復のために確保されたVID値の範囲内の値を有することを判定するステップと、
前記第１のノードにより前記VIDの値に関連付けられた出力リンクを判定するステップと、
前記出力リンクで前記データトラヒックを第２のノードに転送するステップと
を有する方法。
【請求項１３】
前記第２のノードにより前記出力リンクに割り当てられた第２のVIDの値を判定するステップと、
前記出力リンクで前記データトラヒックを前記第２のノードに転送する前に、前記VIDを前記第２のVIDに置換するステップと
を更に有する、請求項１２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この出願は、2010年3月26日に出願された“Source  Routed  VID  Tunnels  for  Ethernet  Packet  Steering”という題の米国仮特許出願第61/318,123号の優先権を主張する。この内容を援用する。
【０００２】
本発明は、ルーティングされるEthernetネットワークに関し、特に、ルーティングされるEthernetネットワークにおける分散した迂回路生成に関する。
【背景技術】
【０００３】
データ通信ネットワークは、様々なコンピュータ、サーバ、ノード、ルータ、スイッチ、ブリッジ、ハブ、プロキシ及び結合されてデータを相互に渡すように構成された他のネットワークデバイスを含むことがある。これらのデバイスは、ここでは“ネットワークエレメント”と呼ばれる。データは、ネットワークエレメントを相互接続する通信リンクでプロトコルデータユニットを渡すことにより、データ通信ネットワークを通じて通信される。複数のデータストリームが通信ネットワークのリソースを共有し得るように、データは、通信ネットワークでの送信のために別個の部分に構成されることがある。データを分割する一般的な方法は、通信ネットワークを通じて個々に転送され得るインターネットプロトコル（IP：Internet  Protocol）パケット又はEthernetフレームの生成を含む。特定のプロトコルデータユニットは、複数のネットワークエレメントにより処理され、ネットワーク上でソース（送信元）と宛先との間を移動する際に複数の通信リンクを横断することがある。
【０００４】
通信ネットワークの様々なネットワークエレメントは、ここではプロトコルと呼ばれる所定のセットのルールを使用して相互に通信する。どのような信号がネットワークエレメント間の通信のために形成されるべきか、プロトコルデータユニットがどのようになるべきかの様々な態様、どのようにプロトコルデータユニットがネットワークエレメントにより処理されるべきか又はネットワークを通じてルーティングされるべきか、及びネットワークエレメントがネットワークで相互運用可能にするためにどのように相互に情報を交換すべきかのように、通信の異なる態様を管理するために異なるプロトコルが使用される。
【０００５】
Ethernetは、物理レイヤを指定する標準802.3及びネットワークレイヤを指定する802.1としてIEEE（Institute  of  Electrical  and  Electronics  Engineers）により規定された周知のネットワーキングプロトコルである。この出願は、ネットワークレイヤの側面に焦点を当てており、ここで使用される“Ethernetネットワーク”という用語は、例えば、802.1、802.1Q、802.1ad、802.1ah、802.1Qay又は802.1aqを含む802.1ファミリーのプロトコルのうち１つ以上を実装するネットワークを示す。一般的には、802.1ファミリーのプロトコルは、ネットワークのノードがパケットを目的の宛先に転送し得るように、Ethernetヘッダがパケットに適用されることを指定する。ネットワークで使用される特定のプロトコルに応じて、このEthernetヘッダは、ソースMACアドレス、宛先MACアドレス、１つ以上の仮想ローカルエリアネットワーク識別子（VID：Virtual  Local  Area  Network  Identifier）、及び任意選択の他のフィールドを含んでもよい。複数のヘッダが同様に含まれてもよい。例えば、第１のヘッダは、クライアントのMACアドレス空間を使用して適用されてもよく、ネットワークサービスプロバイダのMACアドレス空間を使用した第２の外部ヘッダが含まれてもよい。
【０００６】
Ethernetネットワークアーキテクチャでは、ネットワークに接続されたデバイスは、いずれかの所与の時点で共有された通信パスを使用する能力を競合する。複数のブリッジ又はノードがネットワークセグメントを相互接続するために使用される場合、同じ宛先への複数の潜在的なパスがしばしば存在する。このアーキテクチャの利点は、ブリッジ間にパスの冗長性を提供し、容量（capacity）が更なるリンクの形式でネットワークに追加されることを可能にする点にある。しかし、ループが形成されることを妨げるため、一般的には、トラヒックがネットワークでブロードキャスト又はフラッディング（flood）される方法を制限するために、スパニングツリーが使用されている。スパニングツリーの特徴は、ネットワークの宛先のいずれかの対の間に唯一のパスが存在する点にある。従って、パケットがどこから来たかを監視することにより、所与のスパニングツリーに関連する接続を“学習”することが可能になる。802.1Q、802.1ad及び802.1ahの全ては、どのリンクがアクティブであるべきか、及びどれがループの形成を妨げるためにブロックされるべきかを判定するために、制御プレーンで１つ以上のスパニングツリーインスタンス（spanning  tree  instance）を使用する。
【０００７】
スパニングツリーを実装するEthernetネットワークに固有の制限の幾つかを克服するため、ネットワークでEthernetフレームの転送を制御するためにネットワークのノードがリンクステートルーティングプロトコルを実装することを可能にするIEEE802.1aqが策定されている。リンクステートルーティングプロトコルの２つの例は、OSPF（Open  Shortest  Path  First）と、IS-IS（Intermediate  System  to  Intermediate  System）とを含む。ここで使用される“リンクステートプロトコル制御のEthernetネットワーク”という用語は、ネットワークでデータトラヒックを転送するためにノードにより使用される転送状態の設定（導入）を制御するためにリンクステートルーティングプロトコルを使用する802.1Ethernetネットワークを示す。
【０００８】
トランスペアレントなブリッジング（transparent  bridging）と結合してスパニングツリープロトコル（STP：Spanning  Tree  Protocol）アルゴリズムを使用することにより各ノードで学習したネットワークビュー（network  view）を使用するのではなく、リンクステートプロトコルがEthernetネットワークを制御するために使用される場合、ネットワークを形成するブリッジは、リンクステート広告（link  state  advertisement）を交換し、各ノードがネットワークトポロジの同期したビューを有することを可能にする。これは、リンクステートルーティングプロトコルの良く理解された機構を介して実現される。ネットワークのブリッジは、ネットワークトポロジの同期したビューを有し、必要なユニキャスト及びマルチキャスト接続を認識しており、ネットワークのブリッジのいずれかの対の間で最短パスの接続を計算することができ、ネットワークの計算されたビューに従って転送情報ベース（FIB：forwarding  information  base）を個々に生成することができる。
【０００９】
全てのノードが同期したビューで役目を計算し、FIBを生成した場合、ネットワークは、一式のピアブリッジ（peer  bridge）（何らかの理由でブリッジへの通信を必要とするもの）からいずれかの所与のブリッジへのループのないユニキャストツリーと、ブリッジでホストされたサービスインスタンス毎にいずれかの所与のブリッジから同じ一式のピアブリッジ又は一部のピアブリッジへの一致したループのないポイント・ツー・マルチポイント（p2mp）マルチキャストツリーとを有する。結果は、所与のブリッジの対の間のパスがスパニングツリーのリンクを使用することに制限されず、全体の結果は、メッシュで相互接続された一式のノードの接続の幅をより良く利用できるようになる。基本的には、各ブリッジは、そのブリッジへのユニキャスト接続及びそのブリッジからのマルチキャスト接続を規定する１つ以上のツリーのルートになる。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
Ethernetネットワークでは、他のネットワークと同様に、障害の対処は、ネットワークの継続した可用性を確保するために重要である。典型的には、ネットワークは、50msec以内にネットワークを障害から回復させることを目的としている。また、実装の観点からは、理想的には、更なるトンネルがネットワークでシグナリングされることを必要とせず、また、更なるカプセル化を必要とせず、障害回復を実装することが望まれる。例えば、MPLSネットワークでは、障害の発生時にトラヒックがネットワークを通じた別のパスに配置されることを可能にする高速再ルート（fast  re-route）が策定されている。しかし、高速再ルートの対策は、シグナリングを必要とし、MPLSネットワークのノードがトンネルの状態を維持管理することを必要とし、２ホップの再ルートトンネルですらカプセル化を必要とする。更に、MPLS再ルートは、Ethernetに適用可能ではない。この理由は、Ethernetには本来存在しないIPアドレッシングを必要とするからである。従って、ルーティングされるEthernetネットワークにおいて分散した障害回復を実装する方法及び装置を提供することが望まれる。
【課題を解決するための手段】
【００１１】
発明の概要及び要約は、以下の詳細な説明で議論される幾つかの概念を紹介するために提供されている。発明の概要及び要約の部分は包括的ではなく、提示される特許請求の範囲により示される保護対象の範囲を記述することを意図しない。
【００１２】
リンク識別子は、リンクステートプロトコル制御のEthernetネットワークの各ノードにより、そのリンク又は隣接関係（adjacency）のそれぞれにローカルで割り当てられる。リンク識別子は、仮想ローカルエリアネットワーク識別子（VID：Virtual  Local  Area  Network  Identifier）でもよく、ノードの各リンク又は隣接関係が異なるリンク識別子により一意に識別されるようにノードにより割り当てられる。ネットワークのノードがネットワークの他のトラヒックからローカルで割り当てられたリンク識別子に関連するトラヒックを区別することを可能にするために、指定された範囲のリンク識別子が使用される。
【００１３】
リンクステートプロトコル隣接関係通知機構又は他のフラッディング機構は、ローカルで割り当てられたリンク識別子をリンクステートプロトコル制御のEthernetネットワークの他のノードに配布するために使用される。リンク識別子は、ノードによりトポロジデータベースに追加され、迂回路ルートが分散的にネットワークのノードによりローカルで計算されることを可能にする。障害の発生時に、トラヒックがリンクステートプロトコル制御のEthernetネットワークを横断し続け得るように、リンク識別子は、障害の周囲にトラヒックをルーティングするために使用される。一実施例では、リンク識別子の順序付きリストがソースルートとして使用されてもよい。他の実施例では、障害の発生時に、トラヒックが障害の周囲に迂回してネットワークを通じて元のデータパスに再結合することを可能にするために、障害の上流のノードは障害の周囲の迂回路ルートを計算し、トラヒックが元のデータパスのノードに送信されることを可能にする出力リンクに割り当てられた下流ノードのリンク識別子を含める。ノードがローカルで割り当てられたリンク識別子のために確保された値の範囲内の値を備えたリンク識別子（例えば、VID）を含むフレームを受信した場合、フレームがリンク識別子によりローカルで識別された出力リンクに渡されるようにするように、フレームを処理する。ノードがノードの入力リンクに割り当てられたリンク識別子に一致する確保された範囲内のリンク識別子を含むフレームを受信した場合、ノードは、これを迂回路の終端点であるという指示として解釈し、リンク識別子をアプリケーションVIDに置換し、通常の最短パス転送を使用してフレームを転送する。
【図面の簡単な説明】
【００１４】
【図１】例示的なEthernetネットワークの機能ブロック図
【図２】図１の例示的なネットワークにおける障害の発生時のトラヒックの再ルーティングを示す機能ブロック図
【図３】ノード間でのリンクステート広告の配布を示す、例示的なリンクステートルーティングされるEthernetネットワークの一部の機能ブロック図
【図４】VID割り当て及びノード間でのリンクステート広告の配布を示す、図３のネットワークの一部の機能ブロック図
【図５】リンク又は隣接関係毎のVID割り当てを示す、例示的なリンクステートルーティングされるEthernetネットワークの一部の機能ブロック図
【図６】図５のネットワークにおいてソースルーティングを実装するためのVID割り当ての使用を示す機能ブロック図
【図７】図５のネットワークでの障害を迂回するためのVID割り当ての使用を示す機能ブロック図
【図８】ネットワークでの障害を迂回するためのVID割り当ての使用の更なる詳細を提供する、図７に類似する機能ブロック図
【図９】ネットワークでの障害を迂回するための等価コストマルチパス（ECMP：equal  cost  multi  path）に関するVID割り当ての使用の更なる詳細を提供する、図７に類似する機能ブロック図
【図１０】VID割り当てがネットワークでの障害を迂回するために使用されることを可能にするように実装され得る処理のフローチャート
【図１１】VID割り当てがネットワークでの障害を迂回するために使用されることを可能にするように実装され得る処理のフローチャート
【図１２】VID割り当てがネットワークでの障害を迂回するために使用されることを可能にするように実装され得る処理のフローチャート
【図１３】VID割り当てがネットワークでの障害を迂回するために使用されることを可能にするように実装され得る処理のフローチャート
【図１４】図１〜９に示すリンクステートルーティングされるEthernetネットワークの１つで使用され得る例示的なEthernetノードの機能ブロック図
【発明を実施するための形態】
【００１５】
本発明の態様は、特に特許請求の範囲に示されている。本発明は、一例として図面に例示される。図面において、同様の参照符号は同様の要素を示す。図面は、例示のみの目的で本発明の様々な実施例を開示しており、本発明の範囲を限定することを意図しない。明瞭にするために、必ずしも全ての構成要素が各図面でラベル付けされているとは限らない。
【００１６】
図１は、ノード12（ラベルA〜K）を含む例示的なEthernetネットワーク10を示している。ノード12は、リンク14により相互接続されている。ネットワークのノードは、隣接関係（adjacency）情報を交換するために、IS-IS（Intermediate  System  to  Intermediate  System）又は他のリンクステートルーティングプロトコルのようなリンクステートルーティングプロトコルを実装する。ネットワークのノードは、隣接するノードについての隣接関係情報を学習する際に、ノードは、リンクステート広告（LSA：Link  State  Advertisements）を生成し、フラッディング（flood）する。ノードは、LSAからのネットワークトポロジについての情報を使用し、ネットワークを通じた最短パス又は他のルートを計算するために使用され得るリンクステートデータベースを構築する。
【００１７】
図１に示す例示的な通信ネットワークでは、ノードAは、ネットワーク10をクライアント16に相互接続する。クライアントネットワークのEthernetトラヒックは、ペイロード29と、クライアント宛先MACアドレス（C-DA：Client  Destination  MAC  Address）22、ソースMACアドレス（C-SA：Source  MAC  Address）24及び少なくとも１つの仮想ローカルエリアネットワークID（VID：Virtual  Local  Area  Network  ID）を含むクライアント（C）ヘッダ20とを有する。図１に示す例では、クライアントヘッダは、IEEE802.1adにより提供されるS-VID26及びC-VID28の双方を含む。或いは、クライアントヘッダは、802.1Qで提供されるC-VIDのみを含んでもよく、クライアントネットワーク16で使用される802.1プロトコルにより指定された特定のEthernetフレームフォーマットによってはVLAN  IDを含まなくてもよい。
【００１８】
クライアントフレームがプロバイダネットワークに渡される場合、アクセスノードAは、クライアントトラヒックをプロバイダヘッダ30でカプセル化する。このことにより、ノード（ノードB〜K）は、ノードがクライアントのMACアドレス空間に基づく転送を実行することを必要とするのではなく、プロバイダに基づくMACアドレス空間に基づいて転送を実装することが可能になる。
【００１９】
図１に示す例では、プロバイダヘッダ30は、プロバイダ（B）宛先MACアドレス（B-DA：provider  Destination  MAC  Address）32と、プロバイダソースMACアドレス（B-SA：provider  Source  MAC  Address）34と、プロバイダVLAN  ID（B-VID：provider  VLAN  ID）36と、サービス識別子（ISID：Service  Identifier）38とを含む。このようなカプセル化は、802.1ahで指定されている。Ethernetネットワークでトラヒックの転送を制御するためにリンクステートプロトコルを使用することは、IEEE802.1aqで指定されている。物理（IEEE802.3）Ethernetヘッダ40もまた、特定の実装に応じて適用されてもよい。
【００２０】
本発明の実施例は、リンクステートルーティングプロトコルがEthernetネットワークでトラヒックの転送を制御するために使用される場合には常に、多くの形式のEthernetネットワークで利用されてもよい。従って、クライアントネットワークがこのように構成される場合、本発明の実施例は、以下に詳細に説明するように、分散した方法で迂回路を生成するためにC-VID又はS-VIDの値を使用してクライアントネットワーク内で利用されてもよい。同様に、プロバイダネットワークがリンクステートルーティングプロトコルを使用して実装される場合、本発明の実施例は、以下に詳細に説明するように、分散した方法で迂回路を生成するためにB-VID又はISIDの値を使用してプロバイダネットワークで利用されてもよい。しかし、一般的には、ISID値は、ネットワークでの転送判定を行うことに関して使用されないため、好ましくは、ここで詳細に説明する迂回路の分散した生成を実装するためにVIDフィールドが使用される。
【００２１】
図１において、ノードAからノードEへの最短パスは、太線18により示されている。この例での最短パスは、ノードA、F、G、H及びEを含む。ノードF及びGの間のリンクのように、ノードA及びEの間のパスに障害が存在する場合、障害に隣接するノードがローカルの障害保護を実行することを可能にし、トラヒックが障害の周囲にルーティングされることを可能にすることが望まれる。障害に対するローカルのノードに対してノードに含まれる情報を使用させることにより、迂回路の生成が分散した方法で実装されることが可能になる。この理由は、迂回路の中央での判定及び迂回路のシグナリングが必要ないからである。例えば、図２に示すように、ノードFは、トラヒックをノードCに迂回させてもよい。ノードCは、トラヒックをノードEに転送されるようにノードHに転送する。理想的には、障害の周囲にトラヒックを迂回させることは、代わりのルートのシグナリング又はノード間の調整（協調）なしに行われるべきである。
【００２２】
本発明の実施例によれば、ネットワークのノードは、ネットワークのリンク又は隣接関係にリンク識別子を割り当てる。リンク識別子は、C-VID28、S-VID26又はB-VID36のようなVLAN  ID（VID）を使用して実装されてもよい。VIDは、選択された範囲のVID値から選択される。或いは、特定のB-VIDがローカルの再ルートのために使用されてもよく、ISID値がネットワークのリンクに割り当てられてもよい。ここでは、“リンク識別子”という用語は、ネットワークのノードにより、ノードを接続するリンク又はノードの隣接関係に割り当てられた値を示すために使用される。各ノードは、リンク識別子とノードのリンクとの間又はリンク識別子とノードの隣接関係との間に１対１の対応関係が存在するように、異なるリンク識別子をそのリンクのそれぞれに割り当てる。リンク識別子は、グローバルでは一意でない（すなわち、ネットワーク内では一意ではない）。この理由は、ネットワークの複数のノードが、確保された範囲のリンク識別子の中からリンク識別子をそのリンクにそれぞれ割り当てるためである。
【００２３】
割り当てられたリンク識別子は、リンクステートルーティングプロトコル（例えば、IS-IS）のリンクステート広告を使用して、ネットワークの他のノードに通信される。リンクステートルーティングプロトコルを使用することにより、ノードは、隣接関係情報と共にリンク識別子割り当て情報を通信することが可能になる。これにより、ネットワークの隣接ノードは、リンク割り当て情報をトポロジデータベースに含めることが可能になる。
【００２４】
図３は、４つのノードA〜Dを含むEthernetネットワークの小さい部分を示している。図３はまた、どのように通常のリンクステート広告がIS-ISのようなリンクステートルーティングプロトコルで使用されるかを示している。具体的には、IS-ISは、ノードが隣接ノードを検出するために受信（listen）すべきことを指定する。ノードがリンク上に見える隣接ノードを有する場合、これは、そのノードとの“隣接関係（adjacency）”を有すると言われる。そのリンクの隣接関係について受信することに加えて、ネットワークの各ノードは、ネットワークの全てのノードにフラッディングされるリンクステート広告を使用して、その隣接関係のリストを送信する。
【００２５】
例えば、図３に示すように、ネットワークの各ノードは、リンクステート広告31を生成して送信し、どのノードを見ることができるかをネットワークの他のノードに通知する。図３において、ノードAは、ノードB及びDを見ることができるため、ノードB及びDと隣接関係を有することを示すリンクステート広告31を送信する。このLSA｛B,Dが見える｝は、LSAを全てのアクティブなリンク上でネットワークの全ての他のノードに送信することにより、ネットワークにフラッディングされる。従って、このLSAは、ノードD及びBにより受信され、これらのノードの一方又は双方によりノードCに転送される。同様に、図３に示すように、ノードDは、ノードA及びCを見ることができることを示すLSAを生成して送信する。同様に、ノードCは、LSA｛D,Bが見える｝を送信する。この理由は、ノードCがノードB及びDに接続されているからである。ノードBは、ノードDと同様のLSAを生成する。リンクステート広告のフラッディングは周知であり、当該技術分野において知られている。
【００２６】
図４は、ノードにより送信されるLSAがVLAN  IDのようなリンク識別子を含むように変更された実施例を示している。リンク識別子は、ノードにより、隣接ノードが見えるリンク又は隣接関係に割り当てられている。以下の説明では、リンク識別子がVIDである実施例について説明する。前述のように、他の種類のリンク識別子が同様に使用されてもよい。
【００２７】
一実施例では、ノードにより隣接関係（又はリンク）に割り当てられたVIDは、全て比較的小さい範囲のVID番号から選択される。例えば、フルメッシュの通信ネットワークでは、所与のノードは、せいぜい30のオーダの他のノードに接続されることが想定される。IEEE802.1aqのような他のネットワークでは、ノードは、64までの隣接に接続されてもよい。従って、VIDの範囲は、想定される隣接関係の最大数について、所与のノードによる隣接毎に１つのVIDの一意の割り当てに対応できるほど十分に少なくとも大きくなるべきである。等価コストマルチパス（Equal  Cost  Multi-Path）が問題である場合、範囲内のVIDの数は、異なるVIDが異なるパスに割り当てられることが可能になるように増加するべきである。従って、128のオーダまでのVIDでの一式のVIDが取り分けられ、ノードによりネットワークのリンク（又は隣接関係）を指定するために使用されてもよい。各ノードはこの範囲からVIDをその隣接関係／リンクに割り当てるため、隣接関係／リンクに割り当てられたVIDがネットワークで一意にならなくなることが想定される。
【００２８】
図４に戻ると、ノードAは、ノードAをノードBに接続するリンクにVID#36を割り当てている。或いは、ノードAは、ノードBとの隣接関係にVID#36を割り当てていると考えられてもよい。同様に、ノードAは、ノードAをノードDに接続するリンク（又はノードDとの隣接関係）にVID#22を割り当てている。従って、図３に関して前述したようにLSA｛B,Dが見える｝を送信する代わりに、ノードAは、ノードIDと共に、ノードに到達できるリンクに割り当てられたVIDを含むLSA41を送信する。従って、図４に示すように、ノードAは、LSA｛B#36,D#22が見える｝を送信する。他のノードのそれぞれも、指定された範囲のVIDからVIDを割り当てる。これにより、図４では、ノードBは、LSA｛A#1,C#9が見える｝を送信し、ノードCは、LSA｛D#28,B#22が見える｝を送信し、ノードDはLSA｛A#41,C#18が見える｝を送信する。各ノードは、特定のリンク識別子がそのノードでリンク／隣接関係を一意に識別するように、一意のVIDをそのリンク又は隣接関係のそれぞれに割り当てている点に留意すべきである。しかし、ネットワークのノードの全ては、同じ小さい範囲のリンク識別子を使用してリンク識別子を割り当てるため、異なるノードが同じリンク識別子を使用する可能性がある。例えば、図４では、ノードA及びCの双方は、これらのノードで特定のリンク／隣接関係を識別するために、リンク識別子#22を使用している。従って、リンク識別子は、ネットワークでグローバルに一意である必要はない。ノードによるVIDの割り当てはまた、ネットワークのノード間で調整されない。この理由は、各ノードは、どのVIDがネットワークの他のノードによりリンク／隣接関係に割り当てられたかを考慮せずに、VIDを割り当てるからである。
【００２９】
LSAを受信した場合、各ノードは、隣接関係情報と共にVID情報をリンクステートデータベースに含める。従って、各ノードがVIDをそのリンク（又は隣接関係）のそれぞれに割り当て、リンク識別子割り当てをネットワークで広告すると、各ノードは、そのリンクステートデータベース内に、ネットワークを通じてトラヒックエンジニアリングされたパスを計算するために使用できる情報を有する。トラヒックエンジニアリングされたパスは、ローカルの迂回路がネットワークの障害を迂回するために計算されることを可能にする１ホップのパスでもよく、ネットワークを通じて各ホップのトラヒックを転送するために使用される一連のリンク識別子を指定することにより、トラヒックがネットワークを通じてソースルーティングされることを可能にする長いパスでもよい。
【００３０】
図５及び６は、各ノードがそのリンク又は隣接関係のそれぞれにVIDを割り当て、LSAを介して割り当てられた値をネットワークで広告している例示的なネットワークを示している。ノードAがトラヒックをノードCに送信する場合、通常の最短パスの転送を使用してもよく、或いは、ネットワークのノードにより広告されたVIDから形成されたソースルートを指定してもよい。
【００３１】
例えば、図６に示すように、ノードAは、VIDの順序付きリストを含み、各VIDは、ネットワークの特定のノードでの意図した出力リンクに対応する。トラヒックがノードA→ノードB→ノードE→ノードD→ノードB→ノードCに進み、ノードCから太字の矢印で示すリンクに出るように、トラヒックを太線の矢印により示すパスに従わせるために、VIDに基づくソースルート｛#2,#3,#2,#2,#1,#1｝が使用されてもよい。具体的には、ノードAは、ノードAからノードBに延びるリンクにVID#2をローカルで割り当てている。従って、ソースルートの最初のエントリは#2である。同様に、ノードBは、ノードBからノードEに延びるリンクにVID#3を割り当てている。各ノードはソースルートを読み取るため、ソースルートの先頭のVIDを判定し、出力リンクを識別するためにそのVIDを使用する。従って、ノードAがソースルート｛#2,#3,#2,#2,#1,#1｝を備えたフレームを受信した場合、リストの最初のエントリ“#2”を使用し、ノードBへの出力リンクを識別するためにそのVIDを使用する。従って、ノードAは、フレームをノードBに転送する。ソースルートで最初のエントリを読み取った場合、ノードAは、最初のエントリを削除し、これにより、次のノードは、新たな最初のエントリを読み取り、フレームの転送判定を行うためにその新たな最初のエントリを使用することができる。図６に示すように、ノードAへの入力時のソースルートは６つの値を含んでいる。ノードAが最初の値“#2”を読み取った場合、その値をソースルートから削除し、これにより、ノードBに渡されるソースルートは５つのVID値のみを含む。ノードBはソースルートから最初のVID値を読み取り、その値を削除し、指定されたVID値により識別されるリンクにフレームを転送する。図６に示すように、ノードがネットワークでトラヒックを転送するためにソースルートからVIDを使用すると、ソースルートはサイズが減少することが明らかである。リンクステートデータベースに格納されたVID情報を使用して適切なソースルートを選択することにより、ノードは、ネットワークを通じてトラヒックをソースルーティングすることが可能になる。
【００３２】
図７及び８は、どのようにVID情報がリンクステートプロトコル制御のEthernetネットワーク内でローカルの迂回路を実装するために使用され得るかの例を示している。具体的には、図７及び８に示す例示的なネットワークでは、この場合も同様に、各ノードがVID割り当て情報及び通常のノード隣接関係情報を含むリンクステートデータベースを有するように、各ノードがリンクステート広告を使用してそのVID／リンク又はVID／隣接関係の割り当てを広告していることを仮定する。図７に示すように障害が発生した場合、障害に隣接するノードは、図７〜８に示すように、障害の周囲にローカルの迂回路を実装するために、このVID割り当て情報を使用する。具体的には、障害から上流のノードは、障害の周囲にトラヒックを転送することができるトラヒックを送信する。しかし、これを行う前に、ノードは、次のホップノードがどこにトラヒックを転送して元のパスに戻させるかを認識するように、次のホップノードの出力リンクのリンクIDを挿入する。
【００３３】
図８は、ネットワークのノードがネットワークの障害の周囲に迂回路を実装するために、どのようにローカルで割り当てられて広告されたVIDを使用し得るかを示している。具体的には、図８では、まずフレームがノードAからノードBに送信される場合、フレームは、宛先MACアドレス（DA）、ソースMACアドレス（SA）及びアプリケーションVLAN  ID（App-VID）を含むヘッダを有する。アプリケーション特有のVIDは、802.1ahヘッダのB-VIDフィールドで伝達される。MACヘッダの他のフィールドも使用されてもよい。例えば、ネットワークで使用される802.1Ethernetのバージョンに応じて、C-VID、S-VID又は他のVIDフィールドが使用されてもよい。
【００３４】
ノードBによる障害の検出時に、ノードBは、アプリケーションVIDをローカルで割り当てられたVIDの１つに置換し、フレームがローカルの迂回路にあることをネットワークの次のノードに示す。前述のように、ローカルで割り当てられたVIDの全ては一式のVID範囲から割り当てられるため、ネットワークのノードがこの範囲内に含まれるB-VID値を備えたフレームを受信すると常に、ノードは、フレームがネットワークを通じた迂回路ルートにあることを認識する。これは、ノードがフレームを転送するために最短パスの転送を使用すべきではなく、どのようにフレームを転送するかを判定するためにB-VID値を見るべきであることをノードに示す。
【００３５】
ノードBが障害を検出した場合、障害の周囲のルートを判定する。図８では、障害の周囲に２つの別のルート（ノードCを介した第１のルート及びノードDを介した第２のルート）が存在する。まず、ノードBが障害の発生時に回復を実装するために、ノードCを介したルートを選択することを仮定する。
【００３６】
従って、ノードBは、リンクステートデータベースから、ノードCがフレームをノードDを介して通常のパスに戻して送信させるために使用する必要のある出力リンクを判定する。ノードCはノードDへのリンクを識別するために（又はノードDとの隣接関係を識別するために）VID#2を使用することを広告しているため、ノードBは、ヘッダのB-VID部分に“#2”を挿入し、フレームをノードCに転送する。図８に示すように、フレームがノードBを離れるときのヘッダのフォーマットは、｛DA,SA,#2｝であり、#2は、ノードCからノードDへの出力リンクを識別する。
【００３７】
ノードCは、ノードBからフレームを受信した場合、B-VIDを読み取り、B-VIDの値から、フレームが障害の周囲のローカルの迂回路にあることを判定する。転送判定を行うことに関してB-VIDを読み取ることは、IEEE802.1Qayの通常の部分にあるため、ノードが転送判定を行うことに関してB-VIDを読み取ることを必要とすることは、ネットワークがこのバージョンのEthernet標準を使用して実装されている場合には更なる処理は必要ない点に留意すべきである。
【００３８】
ノードCは、B-VIDを読み取った場合、B-VID値がネットワークでリンク／隣接関係を識別するためにノードにより使用される範囲内に含まれることを判定する。従って、ノードは、どの出力リンクがフレームを転送するために使用されるべきかを判定するために、その値を読み取る。図８に示す例では、B-VID値“#2”は、ノードEへのリンクを識別するためにノードCにより使用される。従って、ノードCはフレームをノードEに転送する。
【００３９】
ネットワークのノードが、いつフレームが迂回路パスから離れて通常の転送に戻されるべきかを判定可能にすることが必要である。ノードが迂回路パスの終了を自分で検討すべきであることを伝達するために、ネットワークでフレームを転送するために使用される出力リンクの割り当てられたVIDを挿入する代わりに、上流ノードは、次のノードの入力リンクの割り当てられたVIDを挿入する。これは、フレームが迂回ルートから除去され、再びネットワークを通じた通常の転送パスに配置されるべきことを、受信ノードに示す。
【００４０】
例えば、図８に示すように、ノードCは、ノードEが障害の周囲の迂回路の終了であることを認識する。ノードEに対してフレームを通常の転送に戻るべきであることを示すために、ノードCは、フレームのB-VID値を、ノードEによりノードC及びEを接続するリンクに割り当てられたVIDに置換する。従って、図８では、ノードEは、ノードEをノードCに接続するリンクに#4を割り当てている。CがフレームをノードEに転送する場合、ノードCは、B-VID値を“#4”に置換し、フレームをノードEに転送する。
【００４１】
ノードEがフレームを受信した場合、ノードEは、B-VIDを読み取り、B-VIDの値がノードによりネットワークのリンクにローカルで割り当てられたVID値の範囲内にあることを判定する。従って、ノードEは、フレームがネットワークを通じた迂回路パスにあることを認識する。ノードEはまた、B-VIDの値がノードEによりフレームが到達したリンクに割り当てられた値と同じであることを判定する。従って、ノードEは、迂回路パスの終了であり、フレームが通常の転送に切り戻されるべきであることを認識する。従って、ノードEは、アプリケーションVIDをフレームに再挿入し、その通常の転送データベースを使用してフレームを宛先MACアドレスに転送する。これに関して、ネットワークのノードは、各ノードが最短パス転送状態を備えたリンクステートデータベースを生成することを可能にするリンクステートルーティングプロトコルを実行していることに留意すべきである。ノードEがフレームを受信した場合、通常の方法で転送判定を行うために、この転送データベースを使用する。
【００４２】
或るネットワークでは、ネットワークのノードは、パケットが想定されたポート以外のポートで受信された場合にパケットが破棄されるように、逆パス転送検査（RPFC：reverse  path  forwarding  check）を実装する。例えば、ノードEは、特定のSA,DAの対を有するフレームがノードBからのリンクで到達することを学習してもよい。ノードEがノードCからのリンクでそのSA,DAの対を有するフレームを受信した場合、RPFC処理は、ループの形成を回避するためにフレームをドロップさせてもよい。フレームが迂回路パスから離れることを最後のノードに示すために入力リンクのVIDを使用することは、この潜在的なRPFCの問題を解決する。この理由は、フレームがループバックされているように見えるからである。具体的には、VIDに対して出力リンクを識別させることは、フレームがループバックされたかのように見えさせる。これは、特別の動作を識別するために一般的に使用される古いUターン・トリック（old  U-turn  trick）である。ノードがこの性質のフレーム（ループに見えるインデックスのVIDを備える）を受信した場合、RPFCを行わないことを認識し、VIDをアプリケーションVIDに入れ替え、通常通り転送する。或いは、ノードは、ノードによりネットワークのリンク／隣接関係を識別するために割り当てられたVIDの範囲に関連するVIDを含むフレームについては、RPFCを実行しないように構成されてもよい。
【００４３】
RPFCがネットワークで使用されていない場合、中間ノードに終端ノードの入力ポートのリンクIDを挿入させるのではなく、中間ノードは、単にアプリケーションVIDをフレームに挿入してもよい。RPFCが終端ノードで使用されていないため、終端ノードがフレームを受信した場合、フレームは、単にネットワークのその意図した宛先に転送する。前述のように、RPFCはこの動作を妨げるため、RPFCが終端ノードで使用されている場合、この実装は動作しない。この理由は、RPFCは、不正確なポートで受信されたいずれかのパケットを終端ノードでドロップさせるからである。
【００４４】
前述のように、実施例によれば、VID値の範囲（例えば、64から128のVIDの値）は、ローカルの迂回路の実装のために確保される。各ノードは、この範囲からのVID値の１つをそのリンクのそれぞれ又はネットワークの隣接関係のそれぞれに割り当てる。
【００４５】
これらの特別なVID値の１つを含むパケット又はフレームが受信された場合、ネットワークのノードは、パケット／フレームをその隣接の対応するものに転送させる、或いは、そのリンクの対応するもので転送させる。ノードは、DA検査（DA  lookup）を実装せずに、パケットでRPFCを実行せずにこれを行い、単に、特別なVID値に関連するリンクでフレームを転送する。
【００４６】
パケットを転送する前に、ノードは、VIDを、次のノードによりパケットが受信されるリンクに関連するVIDに入れ替える。次のホップがリンクでパケットを受信し、パケットに関連するVIDがノードによりパケットが受信されたリンクに割り当てられたVIDに一致することを判定すると、ノードは、ネットワークの迂回路の終了であることを判定する。RPFCはノードにより実施されず、VIDはアプリケーションVIDに入れ替えられる。ノードは、通常のDA検査を実行し、ネットワークでその宛先にパケットを転送する。
【００４７】
リンクステートプロトコル制御のEthernetネットワークでは、ネットワークのノードは、転送状態を判定するためにリンクステートデータベースを使用し、転送状態を転送データベースに設定する。実施例によれば、Ethernetネットワークのノードは、宛先毎に１つの迂回路を計算するために、ネットワークのエラーを仮定して別の転送状態を判定し、また、この別の転送状態を出力インタフェースの転送テーブルに設定してもよい。この別の転送状態は、ネットワークを通じて別の（迂回路）ルートでパケットを転送する場合にパケットに含まれるVIDを含み、これにより、出力ポート及びVIDの値の計算が障害の発生前に判定され、ノードの転送テーブルに設定される。障害時に使用される情報（出力ポート及びVID）を設定することにより、ノードは、制御プレーンがその情報を生成して設定することを待たずに、トラヒックを障害の周囲に非常に迅速に再ルーティングさせ得る。更に、ネットワークの各ノードはリンクステートルーティングプロトコルに関連する交換から取得された情報に基づいてこの計算をローカルで実行するため、ネットワークで迂回路を確立するためにシグナリングは必要なく、明示的な状態がノード間で交換される必要はない。これにより、ノード間の調整が最小に維持される。
【００４８】
１つの実装では、IS-IS隣接ハローメッセージ（IS-IS  neighbor  hello  message）が隣接（通信ネットワークにある隣接のみではなく、ノードによりネットワーク外で到達可能な隣接）のリストを含むように拡張される。例えば、図１に戻ると、ノードAは、プロバイダネットワーク10の他のノードとハローメッセージを交換する場合、ノードAを介して到達可能なクライアントノードからの隣接を含める。更に、ハローメッセージは、その隣接のそれぞれに到達するためにノードにより割り当てられた特別なVIDを含むように拡張される。任意選択で、IS-ISハローメッセージの拡張された隣接情報フィールドは、ノードにより割り当てられたリンク識別子／VIDを含めるために使用されてもよい。
【００４９】
或るネットワークの実装では、宛先への２つ以上の等価なコストのパスが存在してもよい。これが生じた場合、ノードは、全てのトラヒックを転送するために使用されるためにパスの１つを選択してもよく、トラヒックの一部を転送するためにパスのそれぞれを使用してもよい。一般的には、複数の等価なコストのパスは、等価コストマルチパス（ECMP：Equal  Cost  MultiPath）と呼ばれる。
【００５０】
図９は、ECMPが使用されるネットワークを示している。ECMPがネットワークで使用されている場合、トラヒックを一方又は他方の等価なコストのパスに属するものとして指定する１つの方法は、パスの一方のトラヒックを奇数として示し、他方のパスを偶数として示すことである。異なるトラヒックは異なるパスで転送されるため、迂回路パスの終了のノードに対してどのようにトラヒックを転送するかを命令することが有利である。すなわち、宛先ノードがトラヒックの等価なコストのパスのうち１つを適切に選択することを可能にすることが有利である。
【００５１】
迂回路の宛先ノードがネットワークでの更なる送信のために正確な（偶数又は奇数の）アプリケーションVIDをパケットに割り当てることを可能にするために、ネットワークを通じて迂回路でパケットを伝送するために使用されるリンク識別子は、元のアプリケーションVIDが偶数であったか奇数であったかを迂回路パスの終了の終端ノードに示すことができるべきである。例えば、VIDの最下位ビットが確保され、迂回路を通じて元のVIDの偶数／奇数の性質を伝達するために使用されてもよい。
【００５２】
従って、ECMPがネットワークで使用されている場合、一実施例では、ネットワークの各ノードは、リンク識別子として使用されるために２つのVIDを各リンクに割り当てる。例えば、20ビットのVIDが使用されている場合、ノードは、19の最上位の同じ値を有するVIDの対をリンクに割り当て、20番目のビット（最下位ビット）は、パケットが奇数のECMPパスに配置されるべきか偶数のECMPパスに配置されるべきかを示すために使用されてもよい。ローカルで割り当てられたリンク識別子の双方は、ノードの同じ出力リンクを識別するために使用される。しかし、ローカルで割り当てられたリンク識別子の一方は、奇数のECMPルートに元々関連したトラヒックを伝達するために使用され、ローカルで割り当てられたリンク識別子の他方は、偶数のECMPルートに元々関連したトラヒックを伝達するために使用される。ノードがVIDのいずれかを含むパケットを受信した場合、ノードは、正確な出力リンクを識別する。更に、ノードは、ネットワークでの送信前にパケットに挿入される次のリンク識別子の最下位ビットを設定するために、最下位ビットを使用する。このように、ECMPトラヒックの偶数／奇数の性質は、ネットワークを通じて迂回路で伝達されてもよい。これにより、パケットがネットワークで転送される場合に、迂回路の宛先ノードはトラヒックを正確なECMPに戻してもよい。
【００５３】
図１０は、ルーティングされるEthernetネットワークでリンク識別子をローカルで割り当てて広告する処理を示している。図１０に示すように、Ethernetネットワークの各ノードは、ノードでリンク識別子をリンク又は隣接関係に割り当てる（100）。一実施例では、リンク識別子は、ネットワークの全てのネットワークエレメントにより使用される特定の合意された範囲内から割り当てられる。如何なるリンク識別子が使用されてもよいが、Ethernetヘッダのフィールドが他の目的で使用される場合、ノードによりローカルで割り当てられたリンク識別子は、ネットワークの他のノードにより他の目的で使用されるべきではない。従って、確保された範囲内からリンク識別子を割り当てることは、トラヒックがローカルの迂回路にあることをノードの１つに伝達し得るフィールドの値をネットワークの通常のトラヒックが偶然に含まないことを確保する便利な方法である。例えば、ネットワークのノードがリンク識別子としてB-VIDを割り当てる場合を検討する。ノードがアプリケーションB-VID値と重複するB-VID値を割り当てた場合、通常のトラヒックは、１つ以上のノードにとってローカルの迂回路に関連するトラヒックとして見える可能性がある。従って、リンク識別子として使用するB-VID値の範囲を確保することは、ネットワークで迂回路のトラヒックと通常のトラヒックとのいずれかの衝突を回避する。しかし、この種類の衝突を同様に回避する他の方法も存在し得る。
【００５４】
ノードがローカルのリンク／隣接関係にリンク識別子を割り当てた場合、ノードは、リンクステートルーティングプロトコルを使用して、リンク／隣接関係と共にリンク識別子をネットワークの他のノードに広告する（110）。具体的には、ノードは、リンクステートプロトコルのリンクステート広告パケットを生成して送信する。これらのリンクステート広告は、ルーティングされるEthernetネットワークの全てのノードにフラッディングされる。
【００５５】
ルーティングされるEthernetネットワークのノードは、ネットワークの他のノードからリンクステート広告からの情報を収集し（120）、更新されたトポロジデータベースを生成するためにこの情報を使用する（130）。更新されたトポロジデータベースは、ネットワークのトポロジ（すなわち、どのノードがどの他のノードに接続されているか）を含むだけでなく、リンク又は隣接関係を識別するためにノードにより割り当てられたローカルで割り当てられたリンク識別子をも含む。トポロジデータベースは、ネットワークを通じて最短パスの転送パス及び／又はトラヒックエンジニアリングされたパスを計算するために、通常通りに使用されてもよい。この転送状態は、ノードがネットワークでトラヒックを効率的に転送することを可能にするように、ノードによりそのデータプレーンにプログラミングされる。
【００５６】
図１１は、ネットワーク内で隣接の障害を想定して、一式のローカルの迂回路を計算するためにノードにより使用され得る例示的な処理を示している。具体的には、ネットワークでの障害の発生前に、ネットワークの各ノードは、下流ノードの接続のロスを仮定し、接続のロスの発生時に障害を迂回するために利用され得るローカルの迂回路を計算する。説明の目的で、ノードがネットワークへの２ホップのノードの様々なパスを検索することに焦点を当てることを仮定する。このことは、ノードとその隣接との間のリンク障害及び隣接の障害にとって十分である。
【００５７】
具体的には、図１１に示すように、各ノードは、その隣接のそれぞれについて繰り返し、その隣接で隣接の障害を想定する（200）。ノードは、隣接の障害の周囲の別のパス（迂回路パス）を計算し、障害と想定されるノードの周囲のトラヒックを特定の宛先への最短パスにルーティングするために、どの一式のリンクが利用可能な隣接を介して使用されるべきかを判定する（210）。ノードは、隣接を通過する最短パスを有する全ての宛先についてこれを行う。この目的は、ノードが障害の周囲の迂回路パスにトラヒックを渡し、トラヒックを元の最短パスに再結合させることであるため、異なる宛先は、１つの想定された障害について異なる迂回路ルートを有してもよい。例えば、図２を参照すると、ノードFがノードGの障害を想定した場合、その障害は、ノードFからノードD、H及びKへの最短パスのトラヒックに影響を与える可能性がある。ノードFは、ノードD、H及びKのそれぞれに到達する迂回路ルートを計算する。この理由は、これらのノードのそれぞれについて最短パスの転送がノードGの障害により影響を受けるからである。同様に、ノードFは、ノードGに渡す必要がある宛先ノードCへのトラヒックエンジニアリングされたパスを有してもよい。従って、ノードFは、ネットワークのトラヒックエンジニアリングされたパスの迂回路を検索する（トラヒックエンジニアリングされたパスの定義が、障害時に使用される別のパスを指定しない場合）。
【００５８】
別のパスを計算することに関して、ノードは、障害の周囲の迂回路を規定するリンク識別子の割り当てを判定する（220）。トラヒックが迂回路パスに配置される場合に使用されるリンク識別子は、障害がネットワークで検出された場合にノードがネットワークのトラヒックのフローを迅速に調整することを可能にするために、転送プレーンにプログラムされる（230）。前述のように、この処理は、各隣接関係の障害を仮定して、ネットワークの各ノードにより実行される。次に、隣接関係毎に、ノードは、どのトラヒックのフローが影響を受けているかを判定するように調べ、トラヒックのフロー毎にローカルで判定された迂回路が計算され、障害時に冗長の転送パスを提供するために設定される。設定された迂回路は、そのトラヒックのフローに（トラヒックを選択された隣接関係に転送させるために）使用される出力ポートと、トラヒックが選択された隣接関係により正確に転送されることを可能にするように挿入される迂回路VIDとを含む。
【００５９】
図１２は、ネットワークで検出されたエラーの周囲にトラヒックを転送するために迂回路パスを使用する処理のフローチャートである。図１２に示すように、ノードがネットワークで障害を検出し（300）、障害が検出されたリンクを通じて転送されるパケットを受信した場合（310）、元のアプリケーションVIDを、迂回路パスの最初のノードにより使用されるリンク識別子に置換する（320）。リンク識別子は、中間ノードで出力ポートを識別するために中間ノードにより使用される。迂回路パスの最初のノードで出力リンクのリンク識別子を挿入することにより、迂回路パスの開始ノードは、中間ノードに対して、どのようにパケットを転送するかを命令することができる。具体的には、中間ノードは、パケットを受信し、パケットが迂回路トラヒックに確保されたVIDの範囲内のVIDを含むことを判定し、VIDにより識別されたリンクでパケットを転送する。
【００６０】
図１３は、迂回路パスからネットワークの通常の転送にトラヒックを遷移させるために終端ノードにより使用され得る処理のフローチャートである。図１３に示すように、ノードが迂回路トラヒックに確保されたVIDの範囲内のVIDを含むパケットを受信した場合（400）、VIDが入力リンクに割り当てられたリンク識別子に一致するか否かを判定するように検査する（410）。この検査の目的は、ノードが迂回路の中間ノードであるか、ノードが迂回路の終端ノードであるかを判定することである。ノードが迂回路の中間ノードである場合、パケットヘッダに含まれるリンク識別子は、ノードにより入力リンクに割り当てられたリンク識別子に一致しない（ブロック410のNO）。この場合、ノードは、リンク識別子を使用して出力リンクを識別し、トラヒックが終端ノードに配置されるリンクに関連するリンク識別子を判定し、VIDを、終端ノードの入力リンクに割り当てられたリンク識別子に置換する（420）。次に、中間ノードは、トラヒックを終端ノードに転送する（430）。
【００６１】
入来するパケットが受信ノードにより入力リンクに割り当てられたリンク識別子に一致するリンク識別子を含む場合、すなわち、パケットがノードで受信され、パケットヘッダ内に含まれるリンク識別子がそのノードの入力リンクのリンク識別子に一致する場合、ノードは、迂回路パスの終端ノードであることを判定する（ブロック410のYES）。そうである場合、ノードは、リンク識別子をアプリケーションVIDに置換し（440）、通常の方法で受信されたかのようにパケットを転送する。例えば、最短パスの転送がネットワークで使用されている場合、終端ノードは、迂回路のリンク識別子VIDをアプリケーションVIDに置換し、パケットを最短パスでその宛先に転送する。
【００６２】
図１４は、ネットワークの迂回路の分散した計算及び実装を実施するために使用され得るノード12の機能ブロック図である。図１４に示すように、ネットワークエレメントは、ネットワークでのトラヒックの受信及び転送を処理するデータプレーン142を含む。一般的には、データプレーンは、１つ以上のポート144と、ネットワークでトラヒックを転送するためのネットワーク処理ユニット146のような処理回路とを含む。パケットが受信された場合、ネットワーク処理ユニットは、図１に関して説明したB-DA及びB-VIDのようなヘッダの１つ以上のフィールドを使用してパケットを転送するために使用される。実施例によれば、パケットがリンク識別子の確保された範囲内のリンク識別子で受信された場合、ネットワークエレメントが前述のようにパケットの転送を処理するように、ネットワーク処理ユニットは、出力ポートの割り当て及びリンク識別子の指示を含む。
【００６３】
具体的には、パケットが確保されたリンク識別子の値の範囲内にあるVIDを有する場合、ネットワーク処理ユニットは、パケットが到達したリンクに関連するリンク識別子を判定するための検査を実行する。パケットのリンク識別子がパケットが到達したリンク識別子に一致しない場合、ネットワーク処理ユニットは、パケットをリンク識別子に対応する出力リンクで転送させる。リンク識別子がパケットが受信された入力リンクのリンク識別子に一致する場合、ネットワーク処理ユニットは、リンク識別子を通常のアプリケーション指定のVLAN  ID値に置換し、パケットが迂回路パスではなく通常パスでネットワークエレメントに到達したかのように、B-VID及びVIDの組み合わせに基づいてパケットを転送する。
【００６４】
ネットワークエレメント12はまた、Ethernetネットワークでのネットワークエレメントの動作を制御するように構成された制御プレーン148を含む。例えば、ネットワークエレメントの動作に関連してここに記載した機能は、コンピュータ可読メモリ150に格納されてネットワークエレメントの１つ以上のプロセッサ152で実行されるプログラム命令の１つ以上のセットを使用して実装されてもよい。例えば、図１４に示すように、ネットワークエレメントは、リンクステートルーティングプロトコルソフトウェア154を含むメモリを含み、リンクステートルーティングプロトコルソフトウェア154は、プロセッサ環境にロードされた場合、ネットワークエレメントがリンクステートルーティング処理156を実施することを可能にする。ルーティング更新（例えば、リンクステート広告）の交換を通じて、リンクステートルーティング処理は、メモリ又は他の記憶デバイスに格納されてもよいリンクステートデータベース158を生成する。他のソフトウェアも同様にメモリに格納され、必要に応じてプロセッサ環境にロードされ、ネットワークエレメントがネットワークで機能することを可能にしてもよい。
【００６５】
ルーティング処理は、リンクステートデータベースを生成することに加えて、例えば、ネットワークの宛先への一式の最短パスのツリーを計算することにより、どのようにトラヒックがネットワークで転送されるべきかを判定するために使用されてもよい。最短パスのツリー及びトラヒックエンジニアリングされたパスは、ネットワーク処理ユニットがネットワークでトラヒックの転送判定を実装することを可能にするようにネットワーク処理ユニット146にプログラミングされる転送テーブルを生成するために使用される。
【００６６】
実施例によれば、ルーティング処理はまた、ネットワークで想定された障害の周囲の迂回路を予め計算し、ネットワークトポロジデータベースに格納されたリンク割り当てから、どのリンク識別情報の値が迂回路を実装するために使用されるべきかを判定する。リンク識別情報の値はまた、ネットワーク処理ユニットに渡され、ネットワークでの障害の発生前に別の転送状態がネットワーク処理ユニットの転送テーブル160で利用可能になることを可能にするために、転送テーブルに含まれる。障害の検出時に、この別の転送状態がネットワーク処理ユニットにより使用され、トラヒックがその通常パスから迂回路パスにシフトされる。別の転送状態をデータプレーンに予めプログラミングさせることにより、フェイルオーバが制御プレーンの介入なしに非常に迅速に生じることが可能になる。
【００６７】
場合によってはルーティングされるEthernetネットワーク（特に、802.1aqを使用して実装されたルーティングされるEthernetネットワーク）に特有の実施例について説明したが、他の種類のルーティングされるEthernetネットワークもこれらの概念を同様に利用してもよい。例えば、本発明の実施例は、RBRIDGEネットワーク又はTRILLネットワークに実装されてもよい。
【００６８】
ここに記載した機能は、ソフトウェア、特定用途向け集積回路（ASIC：Application  Specific  Integrated  Circuit）のような集積回路、フィールドプログラマブルゲートアレイ（FPGA：Field  Programmable  Gate  Array）若しくはマイクロプロセッサのようなプログラム可能論理デバイスと共に使用されるプログラム可能ロジック、又はこれらのいずれかの組み合わせを含む他のデバイスに実装されてもよい。プログラム可能ロジックは、ハードウェアロジック、読み取り専用メモリチップ、コンピュータメモリ、ディスク又は他の記憶媒体のような有形の媒体に一時的又は永続的に固定されてもよい。全てのこのような実施例は、本発明の範囲内に入ることを意図する。
【００６９】
図面に図示して明細書に記載する実施例の様々な変更及び変形が本発明の要旨及び範囲内で行われてもよいことが分かる。従って、前述の説明に含まれる全ての事項及び図面に示す全ての事項は、限定的ではなく例示的に解釈されることを意図する。本発明は、特許請求の範囲及びその均等に規定された通りにのみ限定される。
【図１】
2013524557.tif 000003
【図２】
2013524557.tif 000004
【図３】
2013524557.tif 000005
【図４】
2013524557.tif 000006
【図５】
2013524557.tif 000007
【図６】
2013524557.tif 000008
【図７】
2013524557.tif 000009
【図８】
2013524557.tif 000010
【図９】
2013524557.tif 000011
【図１０】
2013524557.tif 000012
【図１１】
2013524557.tif 000013
【図１２】
2013524557.tif 000014
【図１３】
2013524557.tif 000015
【図１４】
2013524557.tif 000016
【国際調査報告】
2013524557.tif 000017
2013524557.tif 000018