JPH11511618A - 電気通信ネットワークにおける最適復旧ルートの決定論的選択 - Google Patents

Abstract

(57)【要約】 センダノード（８）は、故障を検出すると加重識別子を含む復旧メッセージをタンデム・ノード（２、４、６、１２）へブロードキャストする。タンデム・ノード（２、４、６、１２）は、到来する復旧メッセージを検出するとその復旧メッセージの加重識別子を検索し、その復旧メッセージを受信したスペア・リンクに関するウェイト（１００、２００）でその加重識別子を修正する。修正された加重識別子は復旧メッセージに再挿入され、そのメッセージは下流へブロードキャストされる。チューザノード（１０）は受信した復旧メッセージの加重識別子を比較し、最良の加重識別子を有する代替ルートを選択する。

Description

【発明の詳細な説明】 電気通信ネットワークにおける最適復旧ルートの決定論的選択技術分野 本発明は、複数の通信回路を形成するための複数のスパンによって相互接続さ れた複数のインテリジェント・ノード又はスイッチを有する電気通信ネットワー クに関し、詳しく言うと、２つの隣接するノード間で中断したトラヒックを復旧 させるための代替ルートを最適に選択する方法に関する。本発明は、また、この 最適の代替ルートの選択方法を実行するためのシステム、及びこの進歩性のある 方法を達成するために用いられる流出する（フラッディング(flooding)）サイン 及び逆リンク結合するサインの特定のプロトコルに関する。 まず、関連出願について記載する。 本発明は次の出願に開示された発明に関係する。１９９５年６月７日付で出願 された出願番号第・・・号の「スペア・キャパシティの実質的同時双方向リクエ ストを解決するためのシステム及び方法（System and Method for Resolving Su bstantially Simultaneous Bi-derectional Requests of Spare Capacity）」（ ＲＩＣ−９５−００９）と題するダブリュー・ラス（W．Russ）による出願、１ ９９５年６月７日付で出願された出願番号第・・・号の「ＳＨＮベースの復旧に 対する自動化されたパスの検証（Automated Path Verification for SHN-Based Restoration）」（ドケット番号ＲＩＣ−９５−０１０）と題するラス（Russ） 達による出願、１９９５年６月７日付で出願された出願番号第・・・号の「未復 旧リンク及びノード故障の自動化された復旧（Automated Restoration of Unres tored Link and Nodal Failures）」（ドケット番号ＲＩＣ−９５−０５９）と 題するダブリュー・ラス（W．Russ）による出願、１９９５年６月６日付で出願 された出願番号第・・・号の「電気通信ネットワークのスペア・キャパシティ回 路の競合を解決するための方法及びシステム（Method and System for Resolvin g Contention of Spare Capacity Circuits of a Telecommunications Network ）」（ドケット番号ＲＩＣ−９５−００５）と題するラス（Russ）達に よる出願、１９９５年６月７日付で出願された出願番号第・・・号の「通信ネッ トワークにおける故障位置を識別するための方法及びシステム（Method and Sys tem for Identifying Fault Locations in a Communications Network)」（ドケ ット番号ＲＩＣ−９５−０２２）と題するジェイ・シャー（Ｊ．Shah）による出 願、１９９５年６月２２付で出願された出願番号第・・・号の「分散復旧スキー ムに対する最適のスペア・キャパシティを見積るためのシステム及び方法（Syst em and Method Therefor of Estimating Optimal Spare Capacity for a Distri buted Restoration Scheme）」（ドケット番号ＲＩＣ−９５−００８）と題する ラス（Russ）達による出願、１９９５年６月２２付で出願された出願番号第 号の「故障修理後に電気通信ネットワークをその正常状態に再構成するための システム及び方法（System and Method for Reconfiguring a Telecommunicatio ns Network to its Normal State After Repair of Fault）」（ドケット番号Ｒ ＩＣ−９５−０１３）と題するシース（Sees）達による出願、１９９５年６月２ ２日付で出願された出願番号第・・・号の「分散ネットワークの復旧に対する知 識ベースのパス設定及びスペア・キャパシティの割り当て（Knowledge Based Pa th Set Up and Spare Capacity Assignment for Distributed Network Restorat ion）」（ドケット番号ＲＩＣ−９５−０２１）と題するシャー（Shah）達によ る出願である。それらの開示内容が本出願に参照として組み入れられている上述 の関連出願は全て本発明と同一の譲受人に譲渡されることになっている。背景技術 ネットワークにおけるサービスの喪失は、たとえ短時間であっても、ネットワ ークの操作性に大きく影響し、大きな収入損失となるため、ネットワークの生存 性は電気通信ネットワークにおいて最も重要である。米国特許第４，９５６，８ ３５号に開示されている自己回復ネットワーク（ＳＨＮ）の分散復旧アルゴリズ ム（ＤＲＡ）は隣接ノード間で中断したトラヒックに関するＫ最短パス（経路） の選択を教示している。この’８３５の方法は、しかし、機能休止が生じる特定 の時間にネットワーク内に存在する様々なダイナミック遅延特性に従う非確定論 的アプローチに基づいている。従って、’８３５の方法は、ネットワーク内の所 定の故障に対して最適復旧パス、即ち、代替ルートが選択されることを保証して いない。 詳しく述べれば、’８３５の方法は、分散的に並行して動作して利用可能なス ペア・キャパシティの中から復旧接続、即ち、スペア・リンクを選択することに よって理論的に網目状のネットワークにおけるトラヒックを復旧させる。’８３ ５の分散的方法は理論上常にＫ最短パスを選択して影響されたトラヒックを復旧 させるけれども、実際には、この方法はネットワークの全ノードを横切って流出 される（フラッドされる）復旧サインによって生じる遅延によって影響される。 これは主として、ネットワークの様々なノードの不均一なノード処理遅延による ものである。言い換えれば、異なる代替ルートを通じての送出及び逆リンク結合 の順序の双方に対する復旧サイン（又はメッセージ）の伝搬（又は伝送及び再伝 送）は、様々な代替ルートに沿う様々なノードがそのメッセージを検出し、処理 する速度によって制約される。別の言い方をすれば、ネットワークに設けられた スペア・キャパシティは、中断したトラヒックの復旧が最短パス規則に従って機 能するという前提に基づいている。もしこの最短パス規則に従わなければ、ネッ トワークのある部分についてはスペア・キャパシテイがないために復旧が可能で なくなるかも知れない。従って、この前提は、ネットワークの全ての機器がネッ トワーク中で均一にしかも同一に機能することである。さらに、ネットワークを 通り抜けるメッセージを処理するのに、ある装置は他の装置より長時間かかると いう事実は、’８３５特許で支持されている理論的最短パス規則が、常に真に最 適な復旧ルートを作り出して中断したトラヒックを復旧させるとは限らないこと を意味する。発明の開示 本発明は、１つの分散網（ネットワーク）のノードのそれぞれに、それぞれが そのノードに対する入力の接続により識別される複数の重み（ウェイト）を格納 するためのメモリ・テーブルを設けることによって、決定論的（確定論的）アプ ローチを実行して分散ネットワークにおいて中断したトラヒックを復旧させる。 これらウェイトは時間依存性ではなく、以下に論ぜられる実施例では、例えば、 そのノードをそれと隣接するノードへ接続するそれぞれのスペア・リンクの長さ のような距離測定値である。１つのノードをその隣接するノードの１つに接続す る各スペア・リンクには１つのウェイト、即ち、固定の、従って、決定論的であ るマイル数が割り当てられる。リンクが接続されるそれぞれのポートに検出器が 組み込まれても良く、これによって到来信号、即ち、メッセージは検出される。 ２つの隣接するノードを接続している動作中のリンクにおいて故障が生じると 、今までのようにその故障を検出すると、そのノードの中の１つがセンダ（送信 装置）ノードとして指定され、他のノードがチューザ（選択装置）ノードとして 指定される。センダノードは、流出サイン（又は復旧メッセージ）を構築してＳ ＨＮ処理を始めることによって復旧処理を開始する。本発明では、復旧メッセー ジは、復旧メッセージが到着する各ノードによって更新される加重識別子を格納 する追加フィールドを持つように構築される。この加重識別子は、例えばセンダ ノードにおいて０に設定される距離値でも良い。 復旧メッセージがタンデム・ノードにルーチングされると、この加重識別子は そのタンデム・ノードのプロセッサによって検索される。復旧メッセージがタン デム・ノードに到着してくるスペア・リンクに対応するタンデム・ノードのテー ブルに格納されたウェイトが検索され、既に検索された加重識別子に加算される 。この加重識別子が距離値である場合は、スペア・リンクの長さの値が既存の距 離値に加えられる。増分された距離値は復旧メッセージの加重識別子フィールド に戻されて挿入される。新しく加重された復旧メッセージは、下流のノードへ伝 搬させられ、チューザノードに至る代替ノードを探求する。 この処理は、復旧メッセージがタンデム・ノードに到着する度に繰り返される 。従って、復旧タイム・アウトが起こらず、復旧メッセージが十分大きなホップ ・カウント（hop count）を持っていると仮定すると、復旧メッセージは最終的 にチューザノードに到着したとき、その加重識別子フィールドに、その復旧メッ セージが通過した代替ルートの全区間の合計である値を持つことになる。加重識 別子が距離値である場合には、この距離値は、センダノードからチューザノード に至る代替ルートの合計距離を表す。距離が時間に依存しないとすると、代替ル ー トを見つける決定論的アプローチは達成されることになる。 最適加重識別子を有する復旧メッセージは、そのルート復旧メッセージが通過 した代替ルートが中断したトラヒックを復旧させるために用いられるようにチュ ーザノードによって選択される。加重識別子が距離値である場合には、所定の復 旧タイム・アウト時間内にチューザノードに到着した復旧メッセージの中から最 短距離値を有する復旧メッセージが選択される。 この選択された代替ルートが本当に最適の代替ルートであることを確かめるた めに、逆復旧メッセージ、即ち、逆リンク結合サインがチューザノードによって 構築され、選択された代替ルート上に送信される。この逆復旧メッセージは、選 択された代替ルートの合計距離値としてチューザノードによって設定された値を 有する例えば逆距離フィールドでも良い逆識別子フィールドを有する。この逆復 旧メッセージがタンデム・ノードに到着すると逆処理が行われ、タンデム・ノー ドはそのストア・テーブルから逆メッセージを受信したスペア・リンクに関する ウェイト検索する。格納されているウェイトは、逆復旧メッセージが引き続くタ ンデム・ノードを通過するとき、その逆加重された逆識別子の値が引き続いて減 分されるようにして加重識別子の値から減分される。逆復旧メッセージがセンダ ノードに到着する時までに、加重識別子は、センダノードによって送信された復 旧メッセージの加重識別子フィールドと同一の値を持つであろう。加重識別子フ ィールドが距離フィールドの場合には、逆復旧メッセージに対する距離値はセン ダノードに到着したとき、センダノードによって送信された復旧メッセージの距 離フィールドと同一の値例えば０となるであろう。 本発明は、従ってネットワーク内で中断したトラヒックを復旧させるために代 替ルートを見つけようとして復旧メッセージが通過する分散ネットワークにおい て、様々な時間、即ち、異なったノードのノード処理遅延に影響されない決定論 的アプローチを提供する。 本発明の上述の、並びに他の特徴、目的及び利点は、添付図面を参照してなさ れるこの発明の実施例に言及している以下の記載からより一層明らかになるであ ろう。図面の簡単な説明 図１は電気通信ネットワークの典型的部分及び様々なノードの相互接続を示す 図である。 図２Ａは復旧メッセージの構造を示す図である。 図２Ｂは逆復旧メッセージの構造を示す図である。 図３Ａは２つの隣接ノード間の故障に応答して代替ルートが見つかった場合の 図１の典型的ネットワークを示す図である。 図３Ｂ〜３Ｅはそれぞれ、図３Ａに示す代替ルートの１つを示す図である。 図４Ａ〜４Ｄは組み合わせて本発明の動作を示すフローチャートである。発明を実施するための最良の形態 本発明を説明するための電気通信ネットワークの典型的部分が図１に示されて いる。図示の通り、複数のインテリジェント・ノード２、４、６、８、１０及び １２はスパン、具体的にはリンクを介して互いに相互接続されている。各リンク は非同期ディジタル・レベル３（ＤＳ−３）接続又は同期伝送レベル（ＳＴＳ− ｎ）接続又は光搬送信号レベル（ＯＣ−ｎ）接続の何れであっても良い。図１の 実施例では、ノード２〜１２はそれぞれ、例えばアルカテル・ネットワーク・シ ステムズ（Alcatel Network Systems)社製の製造モデル番号１６３３−ＳＸを有 するディジタル交差接続スイッチ（ＤＣＳ）である。勿論、同等の或いは類似の 交差接続スイッチを使用しても良い。 説明を容易にするために、各ノード２〜１２にはプロセッサＰ及びメモリＭが 示されており、このメモリＭは他の記憶域に加えて本発明特有のストア・テーブ ルを含む。さらに、各ノード内には、それぞれ動作中のポート及びスペア・ポー トを示すＷ及びＳで識別される複数のポートが設けられている。これらのポート は各ノードとその隣接ノードの間の入出力接続を提供する。例えば、ノード２は その隣接ノード８に接続するための３つのリンクつまり２Ｗ１，２Ｗ２及び２Ｓ を有するように示されている。リンク２Ｗ１及び２Ｗ２はそれぞれノード２及び ８の対応する動作中のポートを接続する動作中のリンクである。リンク２Ｓは対 応するスペア・ポートを介してノード２をノード８に接続するスペア・リンクで ある。ノード２はさらに、２つのスペア・リンク４Ｓ１及び４Ｓ２によってノー ド４に接続されているように示されている。 同様に、ノード４は２つのスペア・リンク６Ｓ１及び６Ｓ２によってノード６ に接続されているように示されている。スペア・リンク１２Ｓ１及び１２Ｓ２は ノード６をノード１２に接続し、スペア・リンク１０Ｓ２及び１０Ｓ３はノード １２をノード１０に接続している。さらにノード８をノード４に接続するスペア ・リンク８Ｓ及びノード１０をノード４に接続するスペア・リンク１０Ｓ１が示 されている。最後に、動作中のリンク８Ｗはノード８をノード１０に接続するよ うに示されている。 図１の実施例では、スペア・リンクの他に様々なノードを相互接続する複数の 動作中のリンクがあると仮定する。しかし、単純にするために、ノード８をノー ド１０に接続する１つの動作中のリンク８Ｗ及びノード２をノード８に接続する ２つの動作中のリンク２Ｗ１及び２Ｗ２だけが示されている。 上で述べたように、各ノードはストア・テーブルを備えたメモリＭを有する。 このテーブルはそのノードのスペア・ポートの特定の１つに接続されたスペア・ リンクにそれぞれ対応する様々なウェイトを記憶している。例えば、ノード２を 例に取る。図示の通り、ノード２の対応するスペア・ポートにそれぞれ接続され た３つのスペア・リンクつまり２Ｓ，４Ｓ１及び４Ｓ２がある。従って、ストア ・テーブルはこのスペア・リンクの１つにそれぞれ対応する３つのウェイトを有 する。これらのウェイトはスペア・リンクに関連する特定の決定論的特性を反映 しても良い。このような加重特性の一例は距離値であり、例えばノード２をその 隣接ノードから離間しているスペア・リンクの長さによって表されるマイル数の 値である。従って、ノード２がノード８から１００マイル離れているど仮定する と、ノード２のテーブルにはスペア・リンク２Ｓに関して１００の距離値が記憶 される。 同様にノード２のテーブルにはスペア・リンク４Ｓ１及び４Ｓ２に対する距離 値が記憶されており、これらは両スペア・リンクがノード２をノード４に接続す る限りでは偶然同じ値を有する。図１の実施例では、ノード２はノード４から１ ００マイル離れていると仮定する。従って、図１の実施例では、ノード２のテー ブルは３つの値を有し、これらはそれぞれ対応するスペア・リンクに関連した１ ００である。図１の実施例に関する他のスペア・リンクのそれぞれの距離は図１ のカッコ内に示されている。 図１にはまた、様々なノードに接続し、様々なノードの全体的オペレーション を監督するオペレーション・サポート・システム（ＯＳＳ）１４が示されている 。単純にするために、ノード８、１０及び１２だけがＯＳＳ１４に接続されてい るように示されている。本発明では、様々なノード間で相互接続が変更されたと き、ＯＳＳ１４は各ノードのストア・テーブルに更新した値を供給することが出 来る点に留意されたい。ＯＳＳ１４の他の機能及びネットワークの様々なノード との相互接続については上記参照の同時係属中の出願から探り出しても良い。 さらに、図１の実施例の各インテリジェント・ノードに存在するが具体的には ノード１０だけに示されているのはタイマＴである。このタイマはチューザノー ドが異なった流出サイン、即ち、復旧メッセージをセンダノードから受信するこ とが出来る所定の復旧時間間隔を与える。この所定時間間隔の終わりではチュー ザノードが追加復旧メッセージを受信できなくなるタイム・アウトとなる。タイ マについてのより詳細な論考は上述参照のＲＩＣ−９５−００５の出願に提供さ れている。 ２つの隣接ノードを接続する動作中のリンクで故障が生ずると、例えば図３Ａ に示す光ファイバ・リンクの不良又は切断が８Ｗで生ずると、ＳＨＮ ＤＲＡの アプローチによれば、その故障をサンドイッチにしている、即ち、挟んでいる隣 接ノードの１つがセンダノードと指定され、他がチューザノードと指定される。 図２Ａに示されるような流出サイン、即ち、復旧メッセージがセンダノードによ って構築され、その隣接ノードに送られる。タンデム・ノードとしても知られて いるこれらの中間ノードは、それぞれ復旧メッセージを受信すると、そのメッセ ージの最終到達地点であるチューザノードでなければそのメッセージをさらに送 信するであろう。復旧メッセージのこのような再送信を伝搬と呼んでも良い。適 正な伝搬が行われ、復旧タイム・アウトがなければ、その復旧メッセージは最終 的にはチューザノードに到着する。 図２Ａに示すように、復旧メッセージの具体的構成は複数のフィールドを含む 。 サインタイプ・フィールド１６はメッセージに対する識別子、即ち、復旧メッセ ージであることを示す識別子を与える。センダノードＩＤフィールド１８はセン ダノードを識別する。チューザノードＩＤフィールド２０は復旧メッセージの到 着先であるチューザノードを識別する。本発明の実施例に関するインデックス・ フィールド２２はポートを識別し、従ってセンダノードが復旧メッセージを送出 するスペア・リンクを識別する固有の整数である。このインデックスは、センダ ノード識別子及びチューザノード識別子と共にタンデム・ノード及びチューザノ ードに対して復旧メッセージの識別を与える。復旧メッセージ内にある次のもの は復旧メッセージが下流に送られるノード数を指定する値を有するホップ・カウ ント・フィールド２４である。例えばホップ・カウントが１０であることは、復 旧メッセージが下流にある１０のノードにブロード・キャストされることを意味 し、ホップ・カウントの１０は下流のノードによって受信される毎に減分される 。本発明の復旧メッセージにとって重要な最後のフィールドは、図２Ａに距離フ ィールド２６として示されている加重識別子フィールドである。ここでは、例え ば距離値のような決定論的加重値が格納される。センダノードによって構築され るとき加重識別子として本当に距離値が用いられる場合には、その値はセンダノ ードによって０に設定される。 図２Ａの復旧メッセージの各フィールドは実際複数のビットを有する。例えば 、サインタイプ・フィールド１６は４ビットを有しても良く、センダノード識別 子フィールド及びチューザノード識別子フィールドはそれぞれ８ビットでよく、 インデックス・フィールド及びホップ・カウント・フィールドはそれぞれ１５ビ ットを有しても良い。距離フィールド２６については、ネットワーク内で可能性 のある最長の代替ルートの値が記憶できるように十分大きなビット数例えば１５ ビットが用意される。 図３Ａを参照すると、例えば動作中のリンク８Ｗで故障が検出されると、隣接 ノード８及び１０はどちらがセンダノードになり、どちらがチューザノードにな るかを自分たちの間で決めるであろう事がわかる。従来のＳＨＮのやり方では低 い番号のノードがセンダノードに指定され、高い番号のノードがチューザノード に指定される。従って図３Ａの実施例では、センダノードはノード８であり、チ ューザノードはノード１０である。図示のように、図２Ａに示すような復旧メッ セージはセンダノード８からスペア・リンク２Ｓを介して隣接ノード２へ送られ る。さらに、ノード８はノード４にも急行スペア・リンク８Ｓによって接続され ているので、複製の復旧メッセージが同様にノード８からノード４へ送出される 。 センダノード８からの復旧メッセージはチューザノード１０に到達するまでネ ットワークの様々なノードを通して伝搬される。実際図３Ａに示すように、セン ダノード８からチューザノード１０への復旧メッセージによって見つけられた４ つの異なった代替ルートがある。図３の実施例では、タイム・アウトになる前に 複数の復旧メッセージがチューザノード１０によって受信されるように、ノード １０に所定時間のタイマＴが設定されている。ノード１０で受信された復旧メッ セージはそれぞれ代替ルートを表す。これら受信した代替ルートのどれがリンク ８Ｗで中断したトラヒックを復旧されるのに最適なルートとして指定されるべき かを決定するために、チューザノード１０は受信した復旧メッセージのそれぞれ から距離フィールド２６の値を検索する。後で論ずるように、チューザノード１ ０は、最も低い距離値を有する復旧メッセージを選択する。これは復旧メッセー ジが通過したその代替ルートが最短なためである。このように、復旧メッセージ が通過したスペア・リンクを表す選択された復旧メッセージによって伝送された データに基づいて、代替復旧ルートは確立される。 図３Ｂ〜図３Ｅはそれぞれ復旧メッセージの１つが通過した代替パスを示す。 図３Ｂに示すように、復旧メッセージはノード８からスペア・リンク２Ｓを介し てノード２へ送られる。ノード２はノード４へ接続するためのスペア・リンクを 有するので、自分がチューザノードでないことを認識するとノード２はその復旧 メッセージをスペア・リンク４Ｓ１を介してノード４へブロードキャストする。 その復旧メッセージはさらにノード４からノード１０へスペア・リンク１０Ｓを 介してブロードキャストされる。チューザノード１０は、その復旧メッセージが 自分宛のものであることを認識すると、第１の代替パスが見つかったと判定する 。この第１の代替パスに関する情報はその復旧メッセージによって伝送される。 本発明についてさらに論ずるためにノード２に戻る。復旧メッセージの到着が スペア・ポート２ＳＰ１の検出器によって検出されると、ノード２のプロセッサ Ｐは復旧メッセージの距離フィールド２６に格納されている値を検索する。さら に、プロセッサＰはスペア・ポート２ＳＰ１に接続されたスペア・リンク２Ｓに 関する距離値についてそのストア・テーブルを参照する。そのテーブルに格納さ れている距離値は１００（スペア・リンク２Ｓについて）であるので、プロセッ サＰはこの距離値を距離フィールド２６に存在する値、即ち、０に加算する。更 新された距離フィールドの値、即ち、１００は距離フィールド２６に挿入され、 その復旧メッセージは次ぎに、スペア・ポート２ＳＰ１から２ＳＰ２へルーチン グされてスペア・リンク４Ｓ１へ送られる。 同様に、ノード２からの復旧信号がノード４へ到着すると、例えば具体的には スペア・ポート４ＳＰ１に到着すると、この信号は検出器によって検出され、ノ ード４のプロセッサＰへ報告される。復旧メッセージの距離フィールド２６の値 が再び検索され、スペア・リンク４Ｓ１に関するノード４のテーブルに格納され ている距離値と加算される。更新された距離値２００（１００＋１００）が距離 フィールド２６に挿入され、更新された復旧メッセージは次ぎにスペア・ポート ４ＳＰ２へルーチングされて、ノード１０へルーチングされるようにスベア・リ ンク１０Ｓ１上にブロードキャストされる。 ノード１０では、距離値２００（スペア・リンク１０Ｓ１に対する）がノード １０のストア・テーブルから検索され、距離フィールド２６の既存の値に加えら れる。８−２−４−１０によって表される代替ルートは、従って距離値４００を 有する。この値は例えば第１の代替ルートが４００マイルであることを示しても 良い。 見つけられた第２の代替ルートは図３Ｃに示されている。ここでは、復旧メッ セージは、ノード４のポート４ＳＰ３によって受信されるようにセンダノード８ からスペア・リンク８Ｓへ送られる。ノード４で距離値を０から２００へ更新し た後、更新された復旧メッセージは、ノード４からそのスペア・ポート４ＳＰ４ 経由でチューザノード１０へ向かってスペア・リンク１０Ｓ１上にブロードキャ ストされる。ノード１０では、その復旧メッセージによって識別されたチューザ ノードであると認識し、スペア・リンク１０Ｓに関する距離値２００が既存の距 離値に加えられる。従って、図３Ｃに示す代替ルートは、図３Ｂに示す代替ルー ト同様距離値４００を有する。図３Ｃに示す代替ルートは８−４−１０と表され ても良い。 動作中のリンク８Ｗでの故障によって中断したトラヒックを復旧させるために チューザノード１０によって受信された第３の代替ルートは図３Ｄに示されてい る。この代替ルートでは、復旧メッセージはノード８からノード４、ノード６、 ノード１２を通って最終的にノード１０へ到着した。従って、この代替ルートは ８−２−４−６−１２−１０と表されても良い。距離値については、隣接ノード のそれぞれの対を離間している距離（即ち、隣接ノードを接続している対応する スペア・リンクのそれぞれのリンク）を加算することによって、図３Ｄの代替ル ートは距離値６００を有することがわかる。 図３Ｅは、動作中のリンク８Ｗでの故障によって中断されたトラヒックを復旧 させるために見つけられた最後の代替ルートを示す。この最後の代替ルートは、 ノード８からノード４、ノード６、ノード１２を通ってノード１０へ到着しなけ ればならない復旧メッセージによって示される。この代替ルート８−４−６−１ ２−１０の組み合わされた距離値は６００である。 チューザノード１０に到着する４つの復旧メッセージで示されるようにこの見 つけられた４つの代替ルートのうち、２つ（図３Ｄの８−２−４−６−１２−１ ０及び図３Ｅの８−４−６−１２−１０）は、それぞれ距離値６００を有するた めに明らかに考慮されないであろう。距離値４００をそれぞれ有する残りの２つ 、即ち、図３Ｄの８−２−４−１０及び図３Ｃの８−４−１０については、これ ら２つの代替パスは受容可能であることは明確である。ただ１つの代替ルートが 最短距離を有するものとして見つけられた場合には、そのパスは勿論、トラヒッ クが復旧されても良い代替ルートとしてチューザノード１０によって選択される 。しかし、同一で最良の最適識別子値、即ち、距離値を有する２つ以上の代替ル ートが見つけられた場合には、これらの代替ルートのどちらが最適ルートである かを決定するためにさらに別のステップを取る必要がある。 本発明では、復旧メッセージの異なった属性を利用しても良い。復旧メッセー ジのこのような典型的属性の１つは、フィールド２４に示すようにホップ・カウ ントである。図３Ｂ及び図３Ｃの代替ルートについては、代替ルート４−２−４ −１０はホップ・カウント４を使用し、一方図３Ｃの代替ルート８−４−１０は ホップ・カウント３を使用していることがわかる。従って、最適の代替ルートは 、それぞれの復旧メッセージの距離フィールドの値が同一の場合には、各復旧メ ッセージによって用いられたホップの数をホップ・カウント・フィールドを通し て検査することによって決定することが出来る。従って、図３Ａ〜３Ｅに示す実 施例では、チューザノード１０によって選択された最適の代替ルートは代替ルー ト８−４−１０である。このようにして選択された最適の代替ルートは最小のマ イル数を有するだけでなく、ノード間の最小のホップ数が必要である。 選択された代替ルート８−４−１０力填に最適ルートであることを確かめるた めに、この決定が一旦なされると、チューザノード1０は図２Ｂに示すように逆 復旧メッセージ、即ち、逆リンク・メッセージを構築する。逆復旧メッセージは 図２Ａに示す復旧メッセージに類似しているが、１つの例外として距離フィール ド２６が逆距離フィールド２８で置き換えられている。図２Ａの復旧メッセージ の距離フィールド２６にセンダノード８によって置かれる値とは対照的に、チュ ーザノード１０は、到来する復旧メッセージに対して前に計算した合計距離値を 図２Ｂの逆復旧メッセージの逆距離フィールド２８に挿入する。逆復旧メッセー ジは、以前に復旧メッセージを受信したポート１０ＳＰ１へ送信され、次ぎにノ ード４に向かってスペア・リンク１０Ｓ上にブロードキャストされる。 ノード４は、サインタイプ・フィールド１６によって、到来する逆復旧メッセ ージを検出し、同時にこれを逆復旧メッセージであると識別すると、スペア・リ ンク１０Ｓ１に関する距離値をそのストア・テーブルから検索する。この関連ス ペア・リンクの値は逆距離フィールド２８から検索された値から減分、即ち、減 算される。残りの逆距離値、即ち、２００（４００−２００）が逆距離フィール ド２８に挿入され、更新された逆復旧メッセージはスペア・ポート４ＳＰ３を介 してセンダノード８に向かってスペア・リンク８Ｓ上に送信される。 センダノード８は、スペア・ポート８ＳＰ２の検出器によって到来する復旧メ ッセージを検出すると、その逆復旧メッセージから逆距離値を検索する。次ぎに スペア・リンク８Ｓに関する距離値がそのストア・テーブルから検索され、検索 された逆距離値から減算する。その結果距離値が０であれば、センダノード８は 、 代替ルート８−４−１０が動作中の８リンクＷで発生した故障によってノード８ とノード１０の間で中断したトラヒックを復旧させても良い真の代替ルートであ ると確認する。 前に述べたように、チューザノードによって受信される復旧メッセージの数は 、上記参照のＲＩＣ−９５−００５の出願において述べられた競合問題に従って タイマＴによって設定された所定の復旧時間によって制限されても良い。 本発明の動作は、図４Ａ〜４Ｄに体系化されたフローチャートを参照して示さ れる。 ブロック３０に示すように、ネットワークの各ノードには先ずウェイト・テー ブルが設けられる。このウェイト・テーブルは例えばそのノードに接続された様 々なスペア・リンクに対する標識を有する距離テーブルである。ネットワークの 各ノードの動作中のポートには、検出器も設けられていて、接続された動作中の リンクで発生するかも知れないいかなる不良又は故障も検知する。言い換えれば 、動作中のリンクで故障が発生すると、その故障リンクが接続されている各隣接 するノードはこの故障をそれぞれの動作中のリンクのポートで検知する。これは 決定ブロック３２に示されている。各ノードは故障検知のために絶えず監視をし 続ける。故障が検出されると、ブロック３４において、その故障を挟む隣接ノー ドは両者間でどちらがセンダノードになり、どちらがチューザノードになるかを 決定する。 このように指定が行われると、ブロック３６においてセンダノードは図２Ａの 復旧メッセージを構築する。次ぎにブロック３８において、復旧メッセージの距 離値、即ち、加重識別子フィールドの値が０又は任意の値にセットされる。その 後、ブロック４０において、センダノードは復旧メッセージを伝搬させるために その隣接ノードへ送出する。 復旧メッセージを受信すると各タンデム・ノードはブロック４２において、そ の復旧メッセージの距離フィールドを読み出す。復旧メッセージを受信したポー トに基づいて、タンデム・ノードはブロック４４において、そのストア・テーブ ルから入スペア・リンクに関する距離値をルック・アップする。距離値が復旧メ ッセージ及びストア・テーブルの両方から検索されると、ブロック４６において タンデム・ノードは距離フィールドの値をルック・アップした値で更新する。次 のステップ４８では、新しく更新された距離値が復旧メッセージの距離フィール ドに挿入される。その後、更新された復旧メッセージはブロック５０においてそ のタンデム・ノードから下流のノードへマルチキャストされる。 チューザノードは、故障を検出し、チューザノードとして指定されると、ブロ ック５２において到来する復旧メッセージを待つ。復旧メッセージを受信すると 、ブロック５４においてタイマＴがタイム・アウトになったかどうかの判定が行 われる。タイム・アウトでなければ、ブロック５６においてチューザノードは他 の復旧メッセージを待つ。もしタイマがタイム・アウトになると、チューザノー ドはブロック５８において復旧メッセージのそれぞれの距離フィールドを読み出 す。最後に受信した復旧メッセージの読み出された距離フィールドの値は、ブロ ック６０において全ての（もし有れば）受信した復旧メッセージの距離フィール ドの値と比較される。その後ブロック６２において、チューザノードは最短の代 替ルートを示す復旧メッセージを例えば距離フィールドの最小値に基づいて選択 する。最小の値を有する代替ルートが１つだけなら、その代替ルートが復旧のた めの最適の代替ルートとなる。これは決定ブロック６４及びブロック６８に示さ れている。しかし最小の距離フィールドの値を有する復旧メッセージが２つ以上 存在すると、これら最小の距離フィールド値を有する復旧メッセージの少なくと ももう１つの共通パラメータ（即ち、特性）が比較される。これはブロック６６ に示されている。本発明では、前に述べたようにこのもう１つのパラメータはホ ップ．カウントでも良い。 チューザノードは、ブロック７０において逆距離フィールド値を有する逆復旧 メッセージを構築する。この逆復旧メッセージは選択された代替ルートに沿って センダノードへ向かって送られる。この逆復旧メッセージがセンダノードに到着 したとき、逆距離フィールド値が０であれば、センダノードはチューザノードに よって選択された代替ルートが真に最適の代替ルートであることを確認するであ ろう。これはブロック７２に示されている。 本発明の好ましい実施例が説明の目的でここに開示されたけれど、上記実施例 の全体又は一部分について、様々な変更、変形、修正、置き換え及びこれらと等 価のことをなし得ることは、本発明が属する分野の技術者には明白な筈である。 従って、本発明は請求の範囲の精神と範囲によってのみ限定されることを意図す るものである。

Claims (1)

1. 【特許請求の範囲】 １．複数の動作中のリンクとスペア・リンクによって相互接続された複数のノー ドを有する電気通信ネットワークにおいて、第１及び第２の隣接したノード間で 中断したトラヒックを復旧させるためにこれら第１及び第２の隣接したノード間 に最適の代替ルートを突き止める方法であって、 （ａ）前記ネットワークの各ノードに、それぞれが前記各ノードとそれに隣接 する他の１つのノードとを接続するスペア・リンクに対応するそれぞれのウェイ トを格納するテーブルを設けるステップと、 （ｂ）前記第１のノードから前記ネットワークの様々なノードを接続する様々 なスペア・リンクを介して前記第２のノードへ複数の復旧メッセージを送出し、 前記第１及び第２のノード間のトラヒックを復旧させるための代替ルートを見つ けるステップであって、各復旧メッセージはそれが通過する様々なノードを接続 する様々なスペア・リンクを表す加重識別子を格納するためのフィールドを含ん でいるステップと、 （ｃ）前記各復旧メッセージが通過する前記様々なノードのそれぞれにおける テーブルに与えられた適当なウェイトを用いて、前記各復旧メッセージが前記第 １のノードから様々なスペア・リンク及び様々なノードを介して前記第２のノー ドへ通過する際に前記各復旧メッセージの前記フィールドに格納されている識別 子を再加重するステップと、 （ｄ）前記第２のノードで受信した復旧メッセージの中から、前記最適の代替 ルートを確立するための最良の加重識別子を有する復旧メッセージを選択して前 記第１及び第２のノード間で中断したトラヒックを復旧させるステップ とを含むことを特徴とする方法。 ２．前記ステップ（ａ）はさらに、対応するスペア・リンクのウェイトを、前記 各ノードと前記対応するスペア・リンクによって前記各ノードに接続された隣接 する他のノードとを離間する距離と同等にするステップを含み、 前記各復旧メッセージの前記フィールドに格納された識別子は、前記各ノード と前記隣接する他のノードとを離間する距離を前記フィールドにすでに格納され ている任意の距離に加えることによって再加重され、 さらに、前記再加重された距離を有する前記各復旧メッセージをその下流のノ ードへブロードキャストして前記第２のノードへの代替ルートを見つけるステッ プを含む 請求の範囲第１項に記載の方法。 ３．前記第１のノードからの復旧メッセージが前記第２のノードによって受信さ れるべきであるあらかじめ定められた時間期間を確率するステップと、 前記あらかじめ定められた時間期間の終了時点で前記ステップ（ｄ）を続行す るステップ とをさらに含む請求の範囲第１項に記載の方法。 ４．前記第２のノードが同一で最良の加重識別子を有する復旧メッセージを２つ 以上受信した場合、前記各復旧メッセージに別のフィールドを追加して前記第２ のノードによって用いられる加重属性を格納し、前記各復旧メッセージが通過し た代替ルートが最適の代替ルートであるかどうかを決定するステップをさらに含 む請求の範囲第１項に記載の方法。 ５．逆復旧メッセージを前記第２のノードから前記最適の代替ルートを介して前 記第１のノードへ送るステップをさらに含み、前記逆復旧メッセージは、前記第 １のノードから前記第２のノードに至る様々なノードを接続して前記最適の代替 ルートを確立する様々なスペア・リンクを表す逆識別子を有する別のフィールド を含み、前記逆識別子は前記逆復旧メッセージが通過する前記最適の代替ルート の各スペア・リンクに関連する量だけ変更され、前記逆復旧メッセージがそれぞ れ引き続くスペア・リンク及びノードを通じて前記第２のノードから前記第１の ノードへルーチングされる際、前記逆識別子の引き続く量が前記別のフィールド において変更されるようにする請求の範囲第１項に記載の方法。 ６．前記逆復旧メッセージの逆識別子力、前記第１のノードに到着した際、前記 最適の代替ルートを確立するために前記第２のノードによって選択された復旧メ ッセージの前記第１のノードによって送り出される前の識別子と同一の時、前記 最適の代替ルートを前記第１及び第２のノード間で中断したトラヒックを再ルー チングさせるルートであると確認するステップをさらに含む請求の範囲第５項に 記載の方法。 ７．前記最適の代替ルートの距離を表す識別子を格納するために十分なビットを 有するように前記フィールドのサイズを設定するステップをさらに含む請求の範 囲第２項に記載の方法。 ８．複数の動作中のリンク及びスペア・リンクによって相互接続された複数のノ ードを有する電気通信ネットワークにおいて、２つの隣接するノード間で故障が 発生してこの隣接ノード間を通過するトラヒックを中断した際に、前記隣接ノー ド間の中断したトラヒックを再ルーチングする最適の代替ルートを見つける方法 であって、 （ａ）前記隣接ノードの１つをセンダと指定し、前記隣接ノードの他の１つを チューザと指定するステップと、 （ｂ）前記ネットワークの各ノードのメモリに、前記各ノードと対応するスペ ア・リンクによって各ノードに接続された他のノードとを離間するそれぞれの距 離を格納するステップと、 （ｃ）前記センダから前記チューザへ前記ネットワークの様々なノードを接続 する様々なスペア・リンクを介して、前記センダにおいて所定の値を有する距離 フィールドをそれぞれ含む複数の復旧メッセージを送り、前記センダと前記チュ ーザ間で中断したトラヒックを復旧させるための少なくとも１つの代替ルートを 見つけるステップと、 （ｄ）前記各復旧メッセージが前記チューザへ向かって様々なスペア・リンク を介してノードからノードへ通過する際に、前記各復旧メッセージに対する距離 フィールドの値を、前記各復旧メッセージが前記通過したノードのそれぞれに到 着するスペア・リンクに対応する格納された距離で更新するステップと、 （ｅ）前記センダと前記チューザ間の前記最適の代替ルートを確立するための 最小更新距離値をその距離フィールドに有する復旧メッセージを、前記チューザ で受信された復旧メッセージの中から選択するステップ とを含むことを特徴とする方法。 ９．前記センダからの復旧メッセージが前記選択メッセージによって受信される べきであるあらかじめ定められた時間期間を設定するステップと、 前記あらかじめ定められた時間期間の終了時点で前記ステップ（ｅ）を続行す るステップ とをさらに含む請求の範囲第８項に記載の方法。 １０．前記チューザが同一の更新された最小距離を有する復旧メッセージを２つ 以上受信した場合に、前記各復旧メッセージに、前記チューザによって用いられ るべき属性を格納するための別のフィールドを追加して、前記最適の代替ルート を確立する復旧メッセージを選択するステップをさらに含む請求の範囲第８項に 記載の方法。 １１．前記属性はホップ・カウントであり、 前記チューザによって受信された復旧メッセージの中から最小のホップ・カウ ントを有する復旧メッセージを選択して前記最適の代替ルートを確立するステッ プをさらに含む 請求の範囲第１０項に記載の方法。 １２．逆復旧メッセージを前記チューザから前記最適の代替ルートを介して前記 センダへ送るステップをさらに含み、前記逆復旧メッセージは、前記センダから 前記チューザに至る様々なノードを接続して前記最適の代替ルートを確立するた めの様々なスペア・リンクの組み合わされた距離を表す逆距離値を有する別のフ ィールドを含み、前記逆距離値は、前記逆復旧メッセージが前記最適の代替ルー トに沿って移動する際、前記逆復旧メッセージが通過する前記最適の代替ルート の各スペア・リンクの距離に対応する量だけ減算され、前記逆復旧メッセージが それぞれ前記最適の代替ルートの引き続くスペア・リンク及びノードを通じてル ーチングされる際、前記逆距離値から前記引き続くスペア・リンクの距離が減算 されるようにする請求の範囲第８項に記載の方法。 １３．前記逆復旧メッセージが前記センダに到着した際、前記逆復旧メッセージ の逆距離値が、前記最適の代替ルートを確立するために前記チューザによって選 択された復旧メッセージの前記センダによって送り出される前の距離フィールド に与えられている値と同一の時、前記最適の代替ルートを前記センダと前記チュ ーザ間で中断したトラヒックを再ルーチングさせるルートであると確認するステ ップをさらに含む請求の範囲第１２項に記載の方法。 １４．複数の動作中のリンク及びスペア・リンクによって相互接続された複数の ノードと、 電気通信ネットワークの各ノード内に設けられ、それぞれが前記各ノードを隣 接する他の１つのノードに接続するスペア・リンクに対応するそれぞれのウェイ トを格納するテーブルと、 動作中の１つのリンクにおいて故障が発生したときに、複数の復旧メッセージ を前記ネットワークの様々なノードを接続する様々なスペア・リンクを介して第 ２のノードへ送り、前記動作中のリンクを通じて前記第１及び第２のノード間を 流れるトラヒックを復旧させるための代替ルートを見つけるために設けられた第 １のノード とを備え、 各復旧メッセージは、この各復旧メッセージが通過する様々なノードを接続す る様々なスペア・リンクを表す加重識別子を格納するフィールドを含み、前記各 復旧メッセージが前記第１のノードから前記第２のノードへ通過する際、前記各 復旧メッセージが通過する様々なノードのそれぞれに設けられた適当なウェイト を用いて前記加重識別子を再加重し、 前記第２のノードは、受信した復旧メッセージの中から、前記故障によって前 記第１及び第２のノード間で中断したトラヒックを再ルーチングする最適の代替 ルートを確立するための最良に加重された識別子を有する復旧メッセージを選択 するためにに設けられている ことを特徴とする電気通信ネットワーク。 １５．対応するスペア・リンクのウェイトは、前記各ノードと前記対応するスペ ア・リンクによって前記各ノードに接続されている隣接する他のノードとを離間 する距離と同等にされ、 前記各復旧メッセージの前記フィールドに格納された識別子は、前記各ノード と前記隣接する他のノードとを離間する距離を前記各復旧メッセージの前記フィ ールドにすでに格納されている任意の距離に加えることによって再加重され、 ノードに対する前記加算距離を有する前記各復旧メッセージは下流へブロード キャストされて、前記第２のノードへの代替ルートを見つける 請求の範囲第１４項に記載の電気通信ネットワーク。 １６．前記第１のノードからの復旧メッセージが前記第２のノードによって受信 されるべきであるあらかじめ定められた時間期間を確立するためのタイマ手段を さらに備えており、前記あらかじめ定められた時間期間の終了時に、前記第２の ノードは受信した復旧メッセージの中から、前記最適の代替ルートを確立するた めの最良に加重された識別子を有する復旧メッセージを選択する動作を続行する 請求の範囲第１４項に記載の電気通信ネットワーク。 １７．前記各復旧メッセージは、前記第２のノードが最良に加重された同一の識 別子を有する２つ以上の復旧メッセージを受信する場合に、前記各復旧メッセー ジが通過した代替ルートが最適の代替ルートであるか否かを決定するために前記 第２のノードによって用いられるべき加重属性を格納するための別のフィールド をさらに含む請求の範囲第１４項に記載の電気通信ネットワーク。 １８．前記第２のノードは逆復旧メッセージを前記最適の代替ルートを介して前 記第１のノードへ送るために設けられており、前記逆復旧メッセージは前記最適 の代替ルートを確立するために前記第１のノードから前記第２のノードに至る様 々なノードを接続する様々なスペア・リンクを表す逆識別子を有する別のフィー ルドを含み、前記逆識別子は前記最適の代替ルートの各スペア・リンクに関連し た量だけ変更されて、前記逆復旧メッセージがそれぞれ引き続くスペア・リンク 及びノードを通じて前記第２のノードから前記第１のノードへルーチングされる 際、前記逆識別子の引き続く量が前記別のフィールドにおいて変更されるように し、前記最適の代替ルートは、前記逆復旧メッセージが前記第１のノードに到着 したときに、前記逆復旧メッセージの逆識別子が、前記第１のノードによって送 出される前に、前記最適の代替ルートを確立するために前記第２のノードによっ て選択された復旧メッセージの識別子と同一であれば、前記第１及び第２のノー ド間で中断したトラヒックを再ルーティングするためのルートであると確認され る請求の範囲第１４項に記載の電気通信ネットワーク。 １９．前記フィールドのサイズは最適の代替ルートの距離を表す識別子を格納す るのに十分なビット数を含む請求の範囲第１５項に記載の電気通信ネットワーク 。 ２０．ネットワークの各ノードの前記テーブルにある前記識別子は、前記各ノー ドを、各ノードが１つ以上のスペア・リンクによって少なくとも接続されている 全ての隣接するノードから離間する対応する距離をそれぞれ具備している請求の 範囲第１４項に記載の電気通信ネットワーク。 ２１．複数の動作中のリンク及びスペア・リンクによって相互接続された複数の ノードを有する電気通信ネットワークにおいて、２つの隣接するノード間で故障 が発生してこれら隣接ノード間を通過するトラヒックを中断した際に、前記隣接 ノード間の中断したトラヒックを再ルーチングするために最適の代替ルートを見 つけるシステムであって、 前記隣接するノードの１つがセンダと指定され、前記隣接するノードの他方が チューザと指定されている、前記ネットワークの前記ノードのそれぞれに設けら れた処理手段と、 前記ネットワークの各ノードに設けられ、前記各ノードと対応するスペア・リ ンクによって各ノードに接続された他のノードとを離間するそれぞれの距離値を 格納するためのメモリと、 前記センダから前記ネットワークの様々なノードを接続する様々なスペア・リ ンクを介して前記チューザに送られ、前記センダと前記チューザ間の中断したト ラヒックを復旧させるための少なくとも１つの代替ルートを見つける複数の復旧 メッセージ とを備え、 前記復旧メッセージのそれぞれは、センダで与えられた所定の値を有する距離 フィールドを含み、前記各復旧メッセージの距離フィールドの値は、前記各復旧 メッセージが様々なスペア・リンクを介してノードからノードを通過する際、前 記各復旧メッセージが前記通過したノードのそれぞれに到達するスペア・リンク に対応する格納された距離で更新され、 前記チューザは、受信した復旧メッセージの中から、前記センダと前記チュー ザ間の前記最適の代替ルートを確立するための、最小の更新された距離値をその 距離フィールドに有する復旧メッセージを選択する ことを特徴とするシステム。 ２２．前記センダからの復旧メッセージが前記チューザによって受信されるべき であるあらかじめ定められた時間期間を確立するためのタイマ手段をさらに備え ており、前期チューザは、前記あらかじめ定められた時間期間の終了時に、受信 した復旧メッセージの中から最小の更新された距離をその距離フィールドに有す る復旧メッセージを選択する動作を続行する請求の範囲第２１項に記載のシステ ム。 ２３．前記各復旧メッセージは、前記センダが同一の更新された最小距離値を有 する２つ以上の復旧メッセージを受信すると、前記最適の代替ルートを確立する ための復旧メッセージを選択するために前記センダによって用いられるべき属性 を格納する別のフィールドを含む請求の範囲第２１項に記載のシステム。 ２４．前記属性はホップ・カウントであり、前記チューザは、同一の更新された 最小距離値を有する復旧メッセージの中から最小のホップ・カウントを有する復 旧メッセージを選択して前記最適の代替ルートを確立する請求の範囲第２３項に 記載のシステム。 ２５．前記チューザから前記最適の代替ルートを介して前記センダへ送られる逆 復旧メッセージをさらに含み、この逆復旧メッセージは、前記最適の代替ノード を確立するために前記センダから前記チューザまでの様々なノードを接続する様 々なスペア・リンクの組み合わされた距離を表す逆距離値を有する別のフィール ドを含み、前記逆距離値は、前記逆復旧メッセージが前記最適の代替ルートに沿 って通過するとき、前記逆復旧メッセージが通過した前記最適の代替ルートのス ペア・リンクの距離に対応する量だけ減算され、それによって前記逆復旧メッセ ージがそれぞれ前記最適の代替ルートの引き続くスペア・リンク及びノードを通 じてルーチングされる際、引き続くスペア・リンクの距離量が前記逆距離値から 減算され、前記逆復旧メッセージが前記センダに到着したときに、前記逆復旧メ ッセージの逆距離値が、それが前記センダによって送出される前に、前記最適の 代替ルートを確立するために前記チューザによって選択された復旧メッセージの 所定の距離と同一であるならば、前記最適の代替ルートが前記センダと前記チュ ーザ間の中断したトラヒックを再ルーチングするためのルートであると確認され る請求の範囲第２１項に記載のシステム。 ２６．複数の動作中のリンク及びスペア・リンクによって相互接続された複数の ノードを有し、２つの隣接するノードの一方がセンダと指定され、前記隣接する ノードの他方がチューザと指定されるこれら隣接する２つのノードを接続する動 作中のリンクで故障が発生してこの２つの隣接ノード間を通過するトラヒックが 中断され、前記各ノードと対応するスペア・リンクによって各ノードに接続され ている他のノードとを離間するそれぞれの距離値を格納するためのメモリが電気 通信ネットワークの各ノードに設けられており、復旧メッセージが前記センダに よってその隣接するノードに送られ、必要ならばさらに前記隣接するノードによ って前記チューザに到達するまで前記ネットワークの種々のノードに伝播され、 前記センダと前記チューザ間で中断したトラヒックを再ルーチングする最適の代 替ルートを見つけるための電気通信ネットワークにおいて、前記復旧メッセージ は、 前記センダを識別するためのセンダ識別子と、 前記チューザを識別するためのチューザ識別子と、 故障した動作中のリンクを識別するためのインデックスと、 前記センダで所定の値にプリセットされた復旧メッセージの距離値 とを備えており、 前記復旧メッセージが様々なスペア・リンクを介してノードからノードへ通過 し、各ノードが、前記復旧メッセージの受信時に、前記復旧メッセージが到着す るスペア・リンクに対応する格納された距離値をそのメモリから検索し、その検 索した距離値を現存する復旧メッセージの距離値に加算するときに、前記距離値 は更新され、前記復旧メッセージの距離値は前記復旧メッセージが前記チューザ に到着するまで更新され続ける ことを特徴とする復旧メッセージ。 ２７．前記センダでも前記チューザでもない前記ネットワークのノードはタンデ ム・ノードと指定され、 前記復旧メッセージがチューザへ向かってタンデム・ノードを通過する度に値 が１ずつデクリメントされるホップ・カウントをさらに含む 請求の範囲第２６項に記載の復旧メッセージ。 ２８．前記センダ識別子、チューザ識別子、インデックス、復旧メッセージの距 離値及びホップ・カウントのそれぞれは複数のビットをそれぞれ含む対応するフ ィールドに存在し、各対応するフィールドのそれぞれのサイズは異なっており、 前記復旧メッセージの距離値を含むフィールドは任意の代替ルートの最大距離値 を収容するのに十分大きい請求の範囲第２７項に記載の復旧メッセージ。 ２９．複数の動作中のリンク及びスペア・リンクによって相互接続された複数の ノードを有し、２つの隣接するノードを接続している動作中のリンクで故障が発 生してこの２つの隣接ノード間を通過するトラヒックが中断され、前記各ノード と対応するスペア・リンクによって各ノードに接続されている他のノードとを離 間するそれぞれの距離値を格納するためのメモリが前記ネットワークの各ノード に設けられており、前記隣接ノードの一方がセンダと指定され、前記隣接ノード の他方がチューザと指定され、逆復旧メッセージが前記チューザからその隣接ノ ードへ送られ、その逆復旧メッセージは、必要ならば、前記隣接ノードから前記 ネットワークの様々なノードへ伝搬され、さらに前記センダに到着するまで伝搬 されて、前記センダと前記チューザ間で中断したトラヒックを再ルーチングする ために前記センダからの復旧メッセージによって見つけられた代替ルートが最適 の代替ルートであると確認する電気通信ネットワークにおいて、 前記センダを識別するためのセンダ識別子と、 前記チューザを識別するためのチューザ識別子と、 故障した動作中のリンクを識別するためのインデックスと、 前記復旧メッセージが前記センダから前記チューザへ通過した前記代替ルート に沿うノードを接続している全てのスペア・リンクの組み合わせられた距離値を 有する逆距離値 とを備え、 前記逆距離値は、前記逆復旧メッセージが前記代替ルートの様々なスペア・リ ンクを介してノードからノードを通過し、各ノードが、前記逆復旧メッセージの 受信時に、前記逆復旧メッセージが到着するスペア・リンクに対応する格納され た距離値をそのメモリから検索し、この検索された格納距離値を現存する逆距離 値からデクリメントするときに、デクリメントされ、前記逆距離値は前記逆復旧 メッセージがセンダに到着するまでデクリメントされ続け、 前記逆復旧メッセージは、この逆復旧メッセージが前記センダに到着したとき に、その逆距離値が０である場合に、通過した代替ルートを前記最適の代替ルー トであると確認する ことを特徴とする逆復旧メッセージ。