JPH10173681A

JPH10173681A - 代替ルート決定方法およびネットワーク用ノード

Info

Publication number: JPH10173681A
Application number: JP34588997A
Authority: JP
Inventors: Mark Bentall; マーク・ベンタル; Charles Hargrave Turton Brian; ブライアン・チャールス・ハーグラブ・タートン
Original assignee: Northern Telecom Ltd
Current assignee: Nortel Networks Ltd
Priority date: 1996-11-29
Filing date: 1997-12-01
Publication date: 1998-06-26
Also published as: EP0845919A2; CA2222667A1; US6163525A; GB9625020D0; EP0845919A3

Abstract

(57)【要約】【課題】故障後のネットワークにおける代替ルートを
選択する方法、そのネットワーク、及びそのネットワー
クのノードを提供する。【解決手段】ネットワークの復旧のために、複数の代
替ルートが決定される。代替ルートに沿ったノード間で
メッセージを伝達し、代替ルート中の各リンクの予備容
量を決定する。ネットワークの故障した部分の一方の選
択器ノードで構成される各代替ルートに対するリンク予
備容量のデータべースに基づき、代替ルートが選択され
る。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は故障後のネットワー
クにおける代替ルートを提供する方法に関し、特にネッ
トワーク中で代替ルートを選ぶ方法、ネットワーク、お
よびネットワークのノードに関する。

【０００２】

【従来の技術】メッシュ型ネットワークのようなネット
ワークにおいては、１つのノードと他のノードの間には
通信を行うことができるルートが多数ある。ルーティン
グアルゴリズムの多くの型は、最短ルートを見つけるこ
と、または、利用可能な容量を最大限に用いることが知
られている。ルーティング方法の特別な場合、または適
用は、故障が検出された後、ネットワークを復旧するた
めのものである。そのような故障は、ノードのリンクの
逸失の形、あるいはノードの逸失の形をとることもあ
る。ネットワーク復旧方法は予め計画されたもの、また
は適応的なものとに分類できる。予め計画された方法に
は、ネットワーク・トポロジの知識を要する。適応的方
法は、故障の周辺のネットワークのトポロジをリアルタ
イムで発見することを含む。これはノードでなんらかの
処理能力を用いることを含む。

【０００３】従来の方法はノードで分配された処理を含
むこともあるし、あるいは遠隔処理手段によって中央集
中制御を含むこともある。

【０００４】従来は、復旧方法の評価には３つの主なも
のがあった。まず、代替ルートを用いることで復旧す
る、故障したリンクの容量のパーセンテージが測定され
る。次に代替ルートの長さが測られる（より短いルート
が通常好まれる）。さらに、代替ルートを確認して確立
するための時間が測定される。

【０００５】明らかに復旧方法の実行は、代替ルートに
予備容量がどれだけあるかに強く依存している。代替ル
ートの負荷が大きく、予備容量が少ししかなければ、代
替ルートがより多く必要とされ、代替ルートはより長く
なりがちである。

【０００６】ある既知のアルゴリズム（グローバー・Ｗ
Ｄ著、「自己回復ネットワーク−ｋ最短リンク用の分布
アルゴリズム−リアル・タイムネットワーク復旧中のア
プリケーションを有するマルティグラフのパス解除」、
アルバータ大学博士論文、１９８９年秋季号、第７６頁
から第１０６頁）には、いかなるノードにおいてもネッ
トワーク・トポロジを知ることなくシーケンスを処理す
る完全分布ｋ最短パスを開示している。この処理は図１
のステップ５０からステップ５５に示される。

【０００７】図１のステップ５０においては、リンク故
障が起きた場合、故障リンクの終端側で保護ノードを識
別する。ステップ５１においては、各チャンネル毎に、
タンデムノードを介して保護ノード間にメッセージを送
信することによって予備パスを検索する。ステップ５２
においては、メッセージが伝搬するにつれて、タンデム
ノードは容量を割り当てる。ステップ５３においては、
ホップをカウントすることによって最短のルートを決定
する。ステップ５４においては、各チャンネルの最短ル
ートに対してのみ、確認メッセージがタンデムノードを
介して返送され、タンデムノードは割り当てられている
が確認されていない容量を解放する。ステップ５５にお
いては、どのチャンネルに対してもルートが見つから
ず、確認メッセージの返送がない場合、処理を繰り返
す。

【０００８】図２は処理に含まれるノードの配置を示す
概略図である。図２は比較的簡単な装置を示している。
実際問題、壊れたリンクのまわりには多くのノードがあ
る。

【０００９】リンク故障が生じると、２つの保護ノード
が故障したリンクの終端に割り当てられる。２つの保護
ノードは固有の識別ノード番号を、送信器６３と選択器
６４に送る。送信器は故障したチャネルごとに、送信器
から選択器へ伝播するあふれ箇所を作り、利用可能な予
備のパスを捜す。タンデムノード６５として知られる検
索伝播に含まれるノードは、あふれ例に予備のチャネル
を割り当て、あふれ例が使われるホップ数のカウントを
増やすようにする。選択器があふれ例を受けると、選択
器はホップカウントを読み、最短ルートを識別する。最
短ルートが識別されると、タンデムノードによって割り
当てられる容量は、識別された最短ノード上にない場合
は廃棄される。故障したリンクを用いるチャネルごと
に、同じ方法が実施される。

【００１０】この他に、複数候補選択器の概念を含む基
礎的なアルゴリズムの変形も提案されている。それは、
小峰等による「輸送ネットワークの複数のリンクとノー
ド故障用の分布復旧アルゴリズム」（ＩＥＥＥＧｌｏ
ｂｅｃｏｍ１９９０のプロシーディング、第４５９頁
から第４６３頁）に示されている。さらに「復旧メッセ
ージ移送メカニズムと２重検索自己修復ＡＴＭネットワ
ークの復旧特性」（ＩＥＥＥジャーナル第１２巻、１９
９４年１月、通信における選択領域、第１４９頁から第
１５７頁）において２重検索が開示されている。送信器
と選択器は互いに相手の役割を果たし、両方向の検索を
可能にする。

【００１１】

【発明が解決しようとする課題】しかし、そのような方
法は、多くのチャネルがあるときは、多数の件について
検索することになりかねない。送信器と選択器間で一つ
の検索項だけを用いることは、河村等による「ＡＴＭネ
ットワークの仮想パス概念を利用する自己修復技術」
（日本における電子と通信、第１部、第７５巻、第４
号、１９９２年、第８６頁から第９６頁）によって知ら
れている。しかし、この方法は、チャネルベースで、チ
ャネルのグループの容量に関する情報を得ている検索項
を含む。繰り返して言えば、チャネルが多数あるところ
では、あふれ例も大きく複雑になる。

【００１２】上述した全ての方法に関しては、各タンデ
ムノードによって割り当てられ識別された予備容量やチ
ャネルベースによって、例えばＡＴＭシステムにおける
各仮想パス（ＶＰ）に対して、第１仮想パスは、最短ル
ートが確認されるまで、代替ルートの広い領域に予備容
量を一時的に割当ててもよい。このような一時的な割当
ては、後続する仮想パスをブロックすることもあるし、
または非常に長いルートを強いて捜させることもある。
したがって、このような復旧方法の機能は貧弱となるこ
ともあり、特に負荷が重く予備容量もほとんどない広域
電話通信ネットワークのようなネットワーク上では、特
にそうである。

【００１３】隣接リンクまたはノード上の故障の１００
％復旧を要求された予備容量の最小量を計算するため
に、ネットワーク構成または設計段階で複雑な最大フロ
ー・アルゴリズムを用いることもまた知られている。こ
れらは復旧アルゴリズムの実施試験を可能にして、それ
らがどのくらい最適の復旧に近づいているかが分かる。
本当のネットワークは、１００％の復旧が可能でないほ
どしばしば負荷が重いため、これは非現実的である。し
たがって、このような重い負荷のネットワークにより適
しているアルゴリズムが必要となる。

【００１４】

【課題を解決するための手段】本発明は改善された方法
とシステムを提供するものである。本発明の第１発明に
よれば、複数のノード、ノード間のリンクを有するネッ
トワークの一部が故障した後、ネットワーク中のノード
間で通信を行うための代替ルートを決定する方法におい
て：故障した部分のまわりに複数の代替ルートを決定
し、代替ルートに沿ってメッセージをノード間で伝達
し、上記代替ルート中の各リンクの予備容量を決定し、
少なくとも決定されたリンク予備容量に基づいて、上記
の可能な代替ルートからの通信に対して、１つの代替ル
ートを選択するように構成される。

【００１５】本発明の第２の発明による代替ルート決定
方法は、少なくとも１つのノードを選択器ノードとして
選択し、決定された予備容量に関する情報を選択器ノー
ドへ伝達するステップをさらに含み、その１つの代替ル
ートを選択するステップは選択器ノードが行うように構
成される。。ここで、選択器ノードで代替ルートを選択
することは、復旧プロセスが分布することを意味する。

【００１６】本発明の第３の発明による代替ルート決定
方法は、選択器を用いて、始めに決定されたリンク予備
容量および第１の代替ルートによって占められている容
量に基づいて、通信をするための代替ルートを選択する
ステップをさらに含むように構成される。

【００１７】本発明の第４の発明による代替ルート決定
方法は、選択されたルートによって使用される各リンク
の予備容量の少なくとも１部を選択したルートに割り当
てるステップをさらに含むように構成される。

【００１８】本発明の第５の発明による代替ルート決定
方法は、代替ルートが故障した部分の近隣のノードを使
ったかどうか決定するステップをさらに含み、その選択
ステップは、故障部分の近隣で使用される決定されたノ
ード数に基づいて行われるように構成される。

【００１９】本発明の第６の発明による代替ルート決定
方法は、ルートが仮想パスを含むように構成される。

【００２０】本発明の第７の発明による代替ルート決定
方法は、故障部位の一方において送信器ノードを選択
し、そこからメッセージが送信され、故障部位の他方に
おいて選択器ノードを選択し、メッセージを受信するス
テップをさらに含み、決定された予備容量に関する情報
は選択器ノードに保存され、選択されたステップは選択
器ノードによって実行されるように構成される。

【００２１】本発明の第８の発明による代替ルート決定
方法は、選択器ノードは、故障する前に通信に用いられ
たオリジナルルート上のノードの一つであるように構成
される。

【００２２】本発明の第９の発明による代替ルート決定
方法は、オリジナルルート上で、故障した部分から少な
くとも１つの候補選択器ノードが識別され、メッセージ
は候補選択器にも送信され、選択器を通過していない代
替ルートを決定するように構成される。

【００２３】本発明の第１０の発明による代替ルート決
定方法は、選択された代替ルートを変化させ、最適化さ
せるステップを含むように構成される。

【００２４】本発明の第１１の発明による代替ルート決
定方法は、選択した代替ルートを変更しそれを最適化す
るステップをさらに含むように構成される。

【００２５】本発明の第１２の発明による代替ルート決
定方法は、最適化のステップは選択された代替ルート長
を減少させるステップを含むように構成される。

【００２６】本発明の第１３の発明による代替ルート決
定方法は、最適化のステップは、故障した部分の近隣の
ノードを用いないようにするステップを含むように構成
される。

【００２７】本発明の第１４の発明による代替ルート決
定方法は、代替ルートの１つの予備容量の１部を第１の
通信に割り当て、始めに決定された予備容量と既に割り
当てられた予備容量に基づいて、残りの予備容量を同時
に発生する他の通信に割り当てるステップを含み、複数
の通信を同時に行うための代替ルートを提供するように
構成される。

【００２８】本発明の第１５の発明による代替ルート決
定方法は、選択された代替ルートを通信用に用いるステ
ップをさらに含むように構成される。

【００２９】本発明の第１６の発明による代替ルート供
給方法は、複数のノードおよびノード間のリンクから構
成されるネットワークの一部に複数の通信に影響がでる
故障が起きた後、ネットワークのノード間で同時に発生
する複数の通信を行うために代替ルートを供給する方法
において：ルートのが故障を決定し、故障した部分の周
りの代替ルートを決定し、故障した部分の近隣のノード
の少なくとも１つを選択器ノードとして選択し、代替ル
ート上の予備容量を決定し、選択器ノードを用いて、代
替ルート上で決定された予備容量を複数の同時発生する
通信への割り当てを制御するステップを含むように構成
される。

【００３０】本発明の第１７の発明によるネットワーク
は、ノードを介してネットワーク上で設定されたルート
に沿って情報を伝達するために、ノードを接続する複数
のノードとリンクを含むネットワークにおいて：ネット
ワークの１部が故障した場合、複数の代替ルートを決定
する手段と、代替ルートの沿ってメッセージを伝達し、
代替ルート中の各リンクの予備容量を決定する手段と、
決定されたリンク予備容量に基づいて、代替ルートの１
つを選択する手段とを含むように構成される。

【００３１】本発明の第１８の発明によるネットワーク
用ノードは、リンクで相互接続された複数のノードから
なり、ネットワーク上に設定されたルートに沿って情報
を伝達するネットワーク用ノードにおいて：ネットワー
クの１部が故障した場合、複数の代替ルートを決定する
手段と、代替ルートの沿ってメッセージを伝達し、代替
ルート中の各リンクの予備容量を決定する手段と、各リ
ンクの予備容量に関した情報を受信し、その受信した情
報に基づいて、代替ルートの少なくとも１つを選択する
手段とを含むように構成される。

【００３２】

【発明の実施の形態】図２はネットワークの構成を示す
図である。図２において、終端ノード６１から終端ノー
ド６２の代替ルートは、送信器ノード６３、タンデムノ
ード６５，および選択器ノード６４を介してもよい。

【００３３】図３は本発明の一実施の形態を示す概略図
である。メッセージは代替ルートに沿って送られ、ステ
ップ１００で、ネットワーク破壊部分周辺における代替
ルートの各リンクの予備容量を決定する。このようにし
て、代替ルートはローカルベースで確認され、予備的計
画、検索を集中制御、または代替ルートの計算が必要で
なくなる。ステップ１０１は、リンクの予備容量を基礎
として可能な代替ルートのうちの１つを選択する。ステ
ップ１０２で、選ばれた代替ルートを用いて通信が続け
られる。

【００３４】図４は、本発明の他の側面を示す図であ
る。ステップ１１０において、パスの故障が決定され
る。ステップ１１１において、代替ルートが決定され
る。ステップ１１２では、選択器ノード６４が、図２に
示されるように、故障近傍で選択される。ステップ１１
３では、代替ルート各々の予備容量が決定される。

【００３５】最後にステップ１１４では、代替ルートの
うちの１つ以上が選ばれ、この選ばれた代替ルート上の
予備容量の割当ては、選択器ノード６４によって制御さ
れる。図１の先行技術と比較すると、代替ルート上の予
備容量の割当て上で、予備容量の割り当ては選択器ノー
ドによって局所的に中央制御されれ、これによって、よ
り効率的な割当てが可能になり、タンデムノードによっ
て一時的な割当てが引き起こす障害を避けることができ
る。

【００３６】ネットワークのノードの説明図５は、上述の方法において用いられるノードを示す概
略図である。各ノード７０は終端ノード６１と６２の機
能を実行できることが好ましく、通信をネットワークで
使用されるプロトコルに変換するネットワーク終端装置
を含んでもよい。使用されるネットワーク・プロトコル
のタイプに適した装置は当業者によって実現可能である
ため、このような終端ノードの機能は詳細には説明され
ていない。図５のノード７０もまた、送信器ノード６
３、選択器ノード６４、およびタンデムノード６５の機
能を実施できることが好ましい。これらの機能は、ノー
ド７０中の復旧機能７３で行われる。リンク間の通信を
切り替える機能は、切り替え機能７１によって実行され
る。切り替え機能はルート機能７２によって制御され、
局所的に保持されたデータベース７４を参照する。管理
機能とメンテナンス機能（ＯＡＭ）はＯＡＭ７５で行わ
れる。

【００３７】実際上、切り替え機能７１は、専用のハー
ドウェアによって実行され、動作速度を最大にする。ル
ーティング、復旧機能、ＯＡＭ機能は、１つの従来のプ
ロセッサで実行されてもよいし、複数の従来のプロセッ
サで実行されてもよい。

【００３８】本発明はＳＯＮＥＴに基づく光ハイアラー
キ輸送ネットワークに適用されてもよいが、特にＡＴＭ
ネットワークまたはフレーム・リレー・ネットワークへ
の適用において有利である。これらの後者の２つのタイ
プは、フレーム・リレーの場合には、仮想回路を有する
セル志向であり、仮想接続（ＶＣ）と呼ばれる仮想パス
（ＶＰ）とＶＰのグループは終端ノード間に設定され、
それによって、所定の通信または通信部分の全てのパケ
ットは、同じルートに沿って通過する。通信が電話を含
むときには、仮想パスは、呼の始めに、呼の間の仮想パ
スに沿って通過するセルを両方向に設定する。呼の終わ
りに、仮想パスは取り壊される。このようにリンク上で
は、いつでも多くの仮想パスが確立される。

【００３９】図５におけるノード７０の切り替え機能７
１は、ノードに到着した各ＡＴＭセルから、仮想パス識
別子を読む。切り替え機能は、ルーティング機能７２を
介して、データベース・セクション７４に保持されたル
ーティング・テーブルを参照する。ルーティングテーブ
ルは、どのリンクが適当な仮想パスによって用いられる
かを指示し、そのリンクにパケットを送る。

【００４０】次にルーティング機能について、図６を用
いて説明する。着信セルについては、ステップ８１で、
セルの宛先が決定される。ステップ８２で、セル中のＶ
ＰＩ（仮想パスインジケータ）またはセルの宛先のイン
ジケータに従って、パスルーティング機能は復旧プロセ
スにセルを送る。ステップ８３で、一方、前述のよう
に、ルーティングテーブルに従って他のリンク上へセル
を送る。セルが復旧したパスに属していれば、ステップ
８４で示すようにバッファされる。セルがノード上で動
いているアプリケーションまたはＯＡＭ機能に用いられ
るなら、ステップ８５においてノード内でルーティング
される。

【００４１】ステップ９０において、発信セルは、ルー
ティングテーブルから宛先ノードを決定することによっ
て、ルーティング機能によって扱われる。ルーティング
テーブルの内容に従って、セルは所定のリンク上の前方
送信用の切り替え機能９１の適当な部分に送られる。

【００４２】図５に示されたデータベース７４につい
て、図７を用いて説明する。パスルーティングテーブル
１２０は、確立された仮想パスのトラックを保存する。
全ての宛先用のルーティングテーブルには、同じく１２
０が用いられる。ルーティング機能はノードの通常動作
において、これらのテーブルを使用する。

【００４３】ノードが選択器として機能しているとき、
特に復旧目的で、復旧機能に用いられる他の２つのデー
タベース１２２と１２３が示される。まず代替ルートデ
ータベースが、送信器によって送信されたメッセージに
よって検索された各代替ルートへのエントリにより保持
される。各エントリはルート上のノード数に関して、所
定の代替ルート用のホップカウントを少なくとも１つは
含む。さらに故障した部分からのノードの距離の指示を
記録する。各々の代替ルートの各々に対する「点数（ス
コア）」について、図８を用いてより詳細に説明する。

【００４４】代替ルートの他のパラメータが記録され、
ストアされ、選択器が故障したパス周辺の最適な代替ル
ートを選ぶのを助ける。

【００４５】図８は復旧機能７３の概略図である。一般
的にＯＡＭ（管理機能とメンテナンス）機能は、ノード
周辺のリンク状態を監視し、リンクが故障したかどうか
を決定する。したがって、復旧機能はステップ１３０
で、ＯＡＭから警報指示を受領する。故障したリンクま
たは故障部分のどちらかのノードが警報を発し、復旧を
始める。故障部分の各側のノードは、保護ノードと呼ば
れる。各ノードはパスルーティングテーブル１２０を維
持するため、保護ノードは故障リンクを用いる仮想パス
に気づく。

【００４６】次のステップは、図８のステップ１３１で
示されるように、保護ノードの一対のうちどちらが送信
器であるべきか、どちらが選択器であるべきかを決定す
る。各保護ノードは、他の保護ノードのノードＩＤを知
っているので、送信器／選択器選択は、ノードＩＤを参
照することによってなされる。例えば、より高いノード
ＩＤを選択器とすることもできる。この点では、代替ル
ートは見つけられず、決定は独立に行われる。残りの動
作中のリンク上のより少ない予備容量を持つノードを、
選択器ノードとして選択をすることはメリットがある。
これは、復旧にとっての最悪のボトルネックは、送信器
または選択器への最終的なホップである可能性が高いた
めである。図１４と図１５を用いて以下に説明されるよ
うに、選択器が候補者選択器を用いてバイパスされるの
で、送信器周辺のボトルネックが送信器と選択器の適当
な選択によって減らされるなら、総体的に、復旧機能は
より良く実行される。

【００４７】図８に示されるように次のステップは、送
信器か選択器の機能を適当に実施すること、すなわち、
図８のステップ１３２、１３３，１３４に示されるよう
に、候補者選択器かタンデムノードの機能を実施するこ
とである。

【００４８】選択器ノード機能の説明図９を用いて、選択器ノードの基礎的な機能の概要を説
明する。選択器ノードはステップ１４０で、送信器から
タンデムノードを介して多くの検索メッセージを受け
る。メッセージのあふれ例は、送信器と選択器間の全て
の予備容量を検索するが、前の方法と違って、容量を特
定のパスに割り当てることはしない。ステップ１４１で
選択器ノードは、少くとも各ルートのホップカウント
と、ルート上の各リンクの予備容量と、選択器が故障リ
ンクによって影響される各仮想パスに最適な代替ルート
を選ぶのを援助する他のパラメータを含む、代替ルート
のデータベースを構築する。影響を受けた仮想パスを復
旧するため、最初の完全なパスが到着するとすぐに、選
択器は容量の割り当てを開始する。割り当ては、使用さ
れる特別な割り当てアルゴリズムによる。予備容量の使
用効率に関する異なる結果から、様々な種類の割り当て
アルゴリズムが考えられる。送信器からあふれメッセー
ジを受けることによって容量が確認されるとすぐに、簡
単なＦＣＦＳ（先入り先出し）アルゴリズムは仮想パス
を、ランダムに予備容量に割り当てる。

【００４９】選択器は図９のステップ１４２で、メッセ
ージを送信器に送り返すことによってパスにとって十分
な容量を持つ各パスの最短ルートを確認する。代替ルー
トのデータベースはステップ１４３で、他の仮想パスに
利用できる減少した予備容量を反映するように修正され
る。選択器はステップ１４４に示すように、すべてが復
旧されるか、すべての残りの仮想パスが代替ルート上の
予備容量不足によってブロックされるまで、影響された
仮想パスのリストを通して続ける。

【００５０】ステップ１４５で、選択器ノードは、全て
のノードに放送し、復旧プロセスのためにまだ取ってあ
る予備容量を廃棄する。影響されたすべての仮想パスが
回復するために、このようなことがただ一度だけ起こ
る。

【００５１】リンクの故障が続く間、設定される新しい
仮想パスは、故障部分を避けるために再ルーティングさ
れる。これは、通常、あふれメッセージによって識別さ
れた代替ルートを用いる復旧プロセスの部分としてでは
なく実行されるが、故障部分近傍およびおそらくはそれ
より広い領域で、ノードのルーティングテーブルを変え
ることによって実行される。

【００５２】他の可能な指定または割り当てアルゴリズ
ムには、ループ消去を含んだＦＣＦＳ（先入り先出
し）、そしてループ消去および遅延を含んだＦＣＦＳが
ある。ループ消去に関しては、図１９および図２２を用
いて後で詳細に説明する。簡単に述べれば、容量を割り
当てる前に（または割り当てた後に）、パスがそれ自身
と交わる交点を識別するために、メッセージがパスに沿
って送信される。これは、パスが３つの部分、すなわ
ち、故障部分の前と後に位置する仮想パスのオリジナル
部分、そして故障した部位の周囲の、２つの壊れた部分
をつなぐ第３のバイパス部分を有している場合は複雑に
なる。ループ消去メッセージは、交点でループをバイパ
スし、バイパスしたループを通過し、ループ中の各リン
クの容量を廃棄しても良い。最後に、ループ消去メッセ
ージを選択器に返し、廃棄された容量を他の仮想パスに
おいて復旧のために使えるよう、廃棄された容量を知ら
せる。

【００５３】ループ消去の効果を増強するには、遅延が
あった場合、現在のホップカウントよりも少ないホップ
カウントを有する他の復旧パスは、一定期間閉鎖され
る。現在の復旧パス長より長いまたは同じ長さの復旧さ
れたパスからすべてのループが消去された場合、現在の
最も短いパスのホップカウントは少なくされる。すべて
のループ消去メッセージが返送されるのに十分な遅延が
あれば、割り当てアルゴリズムは最短ループフリー復旧
パスにおいて継続される。ループ消去処理に用いられる
最大遅延は見積もることができ、ループ消去が失敗した
場合に正確なタイムアウト値が与えられる。これによっ
て、メッセージはが変形したり、失われた場合でも、フ
ェールセーフ動作をさせることができる。

【００５４】タンデムノード動作の説明図１０において、ステップ１４９において、送信器から
のあふれメッセージを受信して初めて、タンデムノード
は故障した部位を知らされる。ステップ１５０におい
て、メッセージがすでにタンデムノードを通っていたら
廃棄される。各ノードから各出力リンクへ通過するあふ
れメッセージの特徴として、ループを巡り、同じタンデ
ムノードに戻ってくるメッセージもある。そのようなメ
ッセージを廃棄するために、各メッセージは通過したノ
ードを記録する。一方、ノードは、どのあふれメッセー
ジを見て、通過させたかを記憶してもよい。

【００５５】ステップ１５１において、タンデムノード
はそのリンクの予備容量に関する情報をメッセージに付
加する。ステップ１５２において、メッセージに含まれ
るホップカウントを１つ歩進する。ステップ１５３に示
すように、ある点でタンデムノードはこの復旧処理用に
すべての予備容量を取っておく。各あふれメッセージ
は、ネットワークの同じ領域で複数の故障が起きた場合
のために、どの復旧処理に関係しているか示すインジケ
ータを有している。以下に説明するように、予備容量は
複数の復旧処理間で共用されることもある。ノードは特
定の復旧処理に用いられる予備容量の量を記録し、同じ
復旧プロセスに属する他のメッセージに同量の予備容量
が与えられるようにする。

【００５６】ステップ１５２において、あふれメッセー
ジは、ホップカウントが一定の閾値を越えない限り、タ
ンデムノードによって他のすべてのリンク上に放送され
る。このようにホップカウントに制限を与えることによ
って、あふれメッセージ幅を制限することができ、ネッ
トワークを妨害しないようにする。このホップカウント
の制限は、代替ルートの望ましい長さに従って選択でき
る。

【００５７】ステップ１５５において、タンデムノード
は選択器からの確認を待ち、確認を受け取ったときにだ
け、仮想パスが必要な分だけ予備容量を割り当てる。

【００５８】割り当てる容量がない場合にも、タンデム
ノードはこれを記録して放送されたあふれメッセージで
伝達し、選択器ノード中のデータベースに予備容量不足
が反映されるようにする。

【００５９】送信器ノード動作の説明図１１において、送信器ノードの機能が示されている。
ステップ１６０において、仮想パスを隣接したノードに
設置する。仮想パスにおけるルートの故障はステップ１
６１で検出される。ステップ１６２において、送信器は
代替ルートを見つけるためにすべての隣接したノードを
介して選択器へメッセージを送り、これら代替ルートの
リンク上にある予備容量に関する情報をこの選択器ノー
ドへ伝達する。ステップ１６３において、ルート確認が
選択器ノードから受信された時にのみ、送信器がルーテ
ィングテーブルを変更することによって、選択されたル
ートに沿って仮想パスを再ルーチングする。送信器中の
ルーティングテーブルも書き換えられ、後続の仮想パス
は、故障した部位から離れたところで設置される。選択
器のように、送信器も、それまで故障したリンクが送信
していた宛先のルーティングテーブルを修正するよう他
のノードに知らせ、後続の仮想パスが故障部分とならな
いようにすることもできる。

【００６０】複数リンクの故障についてすべての予備容量はその復旧場所に割り当てられるの
で、このアルゴリズムでは複数のリンク故障を処理する
のは複雑となる。一つの処理がある場合は、すべての容
量が一つの処理に割り当てられるべきである。しかしな
がら、複数の処理が同時に、または別の時に行われて
も、デッドロックは避けなければならない。

【００６１】２つ以上の故障が起きた場合、利用できる
予備容量の量が復旧アルゴリズムを制限する。他の復旧
作業を行っていると検出された場合には、一定期間後、
復旧した部分を再試行する機能があるとよいとされてい
る。この処理が終了した段階で再び復旧検索を行うこと
ができるが、アルゴリズムが初期の復旧検索を試みる妨
げにはならない。

【００６２】２つのアルゴリズムが同時に開始した場
合、双方のアルゴリズムを引き戻し、故障部位間で容量
を分割して復旧を行うか、片方が復旧を終了させるまで
もう一方を後戻りさせるような機能があるとよい。第１
の方法では、２つのアルゴリズムが、タンデムノードを
制限する別々のあふれ検索を行い、予備容量の一組の部
分を各アルゴリズムに割り当てることができる。第２の
方法では、遅延した復旧作業にかかる時間を増やすこと
ができる。

【００６３】ノードの故障ノードの故障を処理する第１のステップでは、隣接ノー
ドに対して、リンクの故障ではなく、ノードの故障であ
ると決定する。この処理は、フジイＨ．およびヨシカ
イＮ．等の「復旧メッセージ転送メカニズムおよびダ
ブルサーチ自己治癒ネットワークの特徴」、ＩＥＥＥ
Ｊ．セレクト．エリアズ通信、Ｖｏｌ．１２、第１号、
第１４９頁〜第１５７頁、１９９４年１月号、により詳
細に記載されている。一旦、故障がノードで起きたとノ
ードが認識したときに、どのＶＰが「エンド・ホップ」
ノードを宛先としているか決定するのに十分な情報をノ
ードが含んでいることが望ましい。「第２の」という言
葉は、２ホップ前、または２（先入り先出し）ホップ後
ろのノードを指す。保護ノード間に幾つかの送信器／選
択器箇所を設け、全てのノードがお互い１つの送信器／
選択器箇所を有するようにするのは都合がよい。これは
以下に説明する方法で実行可能である。以下の説明中、
故障したノードは容疑ノードと呼ぶ。

【００６４】保護ノードは、容疑ノードが動作不可能で
あると認識したら、他の保護ノード、すなわち、そのノ
ードの第２のホップテーブル・エントリ中の他の全ての
ノードに指示を出す。各ノードは、ノードＩＤに対して
「保護ノード・シーケンスリスト」中に相対的な位置を
占めている。このシーケンスは、最も高いＩＤを有する
保護ノードが第１のノードになり、最も低いＩＤを有す
るノードを最後のノードとなる。例えば、保護ノード・
シーケンスリストが、図１２に示すようにＣ，Ｄ，Ｈ，
Ｌであるとすると、各保護ノードはそのシーケンスリス
ト中でより低い他の保護ノードに対する送信器状態を有
している。同様に、各保護ノードはシーケンスリスト中
でより高い他の各ノードに対する選択器状態を有してい
る。この例では、表１において送信器／選択器状態が示
されている。

【００６５】

【表１】

【００６６】従って、すべての送信器状態は、この表中
に各選択状態にあふれ検索例を作成する。検索の間、各
タンデムノードは送信器／選択器の組の数に対して、容
量の部分を確保する。この情報は検索メッセージ中に保
管され、式１によって示される。

【００６７】

【数１】

【００６８】ここでは、Ｎは保護ノードの数である。容
量を確認し、ループ消去を行う処理は、以上に述べた通
りである。図１３は、各送信器／選択器対に対する様々
な復旧処理に対して、管理ノードがどのように選択器お
よび送信器として動作できるかを示したものであり、た
とえば、保護ノード「Ｈ」１７１の場合について図示し
たものである。

【００６９】図１３において、送信器状態をノード
「Ｌ」にし、選択器状態をノード「ＣおよびＤ」にし、
メッセージを検索し、タンデムノードに各送信器および
選択器の組に予備容量の一部を予約する要求を放送す
る。

【００７０】候補選択器図１４に示されているように、選択ノード６４の周りの
ボトルネックを防ぐため、一部の機能は、候補選択ノー
ド１８０に委任される。選択された他のパスは、選択ノ
ードをバイパスする。その動作は図１５で説明する。図
１５は候補選択ノードを説明するためにフローチャート
である。図１５のステップ１８１において、選択ノード
６４は送信器からあふれメッセージをタンデムノードを
介して受信する。ステップ１８２において、このような
候補選択器の終端、または故障した部分をバイパス・パ
スを示すメッセージは主選択器６４へ送られる。

【００７１】ステップ１８３において、候補選択器は、
選択器から確認を受信し、送信器へパスバックを戻す。
ステップ１８４において、候補選択器は、主選択器から
送信器への要求の確認を受領し、バイパス・パスおよび
もとの故障したパスを接続する。最後に、ステップ１８
５において、確認は選択器に送信され、主選択器・候補
選択器間の古いパスは破棄され、他の復旧パス用に使え
るようにする。

【００７２】候補選択器によって避けられたボトルネッ
クは、カットセットを用いて説明する。カットセットと
は２つのリンクでり、除去されたとき、グラフを２つに
分割する。復旧処理において、ループ消去がネットワー
クで行われない場合、最小限の容量を有する送信器と選
択器を分離するカットセットは、制限要素（最小カット
セット）となる。最小のカットセットは、１ホップ中
に、保護ノードの周りに最小カットセット容量を有して
存在することが多い。どちらの保存ノードを主選択器に
してもよいことを考えると、最小カットセット容量を有
するノードを主選択器として選択し、候補選択器を主選
択器に割り当てることによって、最小カットセットは増
加する。復旧処理の間、主選択器は復旧に関する情報の
データベースを保持する。

【００７３】候補選択器の概念は、従来の方法と比べ、
送信器が各候補選択器と主選択器の間に、１つのあふれ
例を作る点が異なる。これを行うには、送信器がすべて
の第２ホップノードのノード識別が要求される。すべて
の検索例に対して、タンデムノードは選択器（候補、ま
たは主）に同じ予備容量を通報する。候補選択器は自分
宛のメッセージを受信すると、受信した情報を主選択器
に通報する。データベースから、主選択器は、その候補
選択器を通過する故障したＶＰと、その復旧に用いるこ
とのできる予備容量の量を識別する。主選択器は候補選
択器に復旧処理があったら知らせる。この処理が終了し
たら、候補選択器がループ消去を開始し、破棄された容
量を選択器に知らせる。

【００７４】選択器が最小数の隣接するノードを有する
よう選択された場合、候補選択器の概念は、一番起こり
やすそうな最小カットセットを消去する。原理的には、
送信器側でも同じ概念が予見できる。

【００７５】最適化図１６は、復旧容量が最適化によってどのように向上す
るか示すフローチャートである。図１６において、ステ
ップ１９０において、復旧ルートを選択した後、ステッ
プ１９１において、できるだけ早く現存する仮想パスを
復旧するため、容量が割り当てられる。ステップ１９２
において、ルートが最適化されているかどうか決定す
る。最適化されている場合は、ルートを変更し、ステッ
プ１９４で、用いられていない容量を破棄する。

【００７６】以上で述べたように、適当な割り当てアル
ゴリズムを選択することによって、容量が割り当てられ
る前に最適化を行うこともできる。以下に述べる最適化
方法は、容量の割り当て前でも、後でも使用できる。

【００７７】図１７は、ルートを最適化する３つのオプ
ションを示す図である。図１８において説明されるよう
に、ステップ２００で、故障した部位からの距離を評価
し、対的な点数が各ルートに与えられる。ステップ２０
１で、相非ループパス長減少を行ってもよく、これは図
２３を用いて後で説明する。ステップ２０２で、ループ
消去され、これは図１９〜２２を用いて説明する。

【００７８】故障したパスからの距離の評価点数システムの概念は、故障部位に最も近い輻輳したリ
ンクから復旧パスを離すことである。そのような技術
は、復旧量を増加させるかもしれないが、もっと長いパ
スを用いる。このパスはすでに存在するが、復旧処理に
対しては関係がないため、「サイレントパス」と呼ばれ
る。

【００７９】図１８はサイレントパスと現在復旧された
パスと差違を示す。このようなサイレントパスを評価す
るために、各サイレントパスは故障したリンクからの距
離に基づいた点数が与えられる。最適パスはその点数に
基づいて他のパラメータと共に選択される。

【００８０】距離点数決定最初のタスクは、故障したリンクからの距離をノードに
知らせ、点数を割り当てる。これは、送信器と選択器間
の２パス放送によって行う。故障が検出されたとき、保
護ノードは１つのメッセージを他の保護ノードへ放送す
る。メッセージがネットワーク上を広がるにつれ、ホッ
プカウントが維持される。受信した最も低いホップカウ
ントに基づいて、故障したリンクからの距離を中間ノー
ドに供給する。受信した最小カウントより大きいホップ
カウントを有していると、ノードがメッセージを終了す
るので、検索は破棄される。

【００８１】距離点数値各リンクに割り当てられた点数は、短いパス上にある故
障したリンクからより近いリンクの代わりに、選択され
るべき故障リンクからより遠い１組の数のリンクが許可
されるように設計される。例えば、リンクの数が最大３
と設定される場合、１つだけ大きい点数を有するリンク
よりも、１つだけ小さい点数を有する３つのリンクを含
むことができる。

【００８２】リンクの点数を決定するには、その点で点
数が無関係になる所定の距離、例えば０となるべきであ
る。この例では、故障部分から４ホップを越えるリンク
が点数０を有しているものとする。従って、設定された
リンクの数が３であれば、点数は以下のようになる。・故障したリンクから４ホップ離れたリンクの点数は
２、・故障したリンクから３ホップ離れたリンクの点数は
（４ホップ離れたリンク×３）＋１＝７、・故障したリンクから２ホップ離れたリンクの点数（３
ホップ離れたリンク×３）＋１＝２２、・故障したリンクから１ホップ離れた、つまり送信器ま
たは選択器に接続されたリンクの点数（２ホップ離れた
リンク×３）＋１＝６７。

【００８３】距離点数を用いた最適パスこの点数が最小になると、パスの長さは制御されるが、
パスは最短ルートの故障についてのさらなるルートを取
る。これは、次の復旧アルゴリズムのいずれかかに従っ
て、またはその２つを組み合わせることによって実行可
能である。

【００８４】案１：選択器は、最も小さい点数を有する
復旧ルートを選ぶ。通常、候補選択器を介したルートは
低い点数を有するため、最初に選ばれる。

【００８５】案２：最適化アルゴリズムは、選択器を用
いることによって、またはパスが確立された時に、パス
上で行われる。確立されたパスを用いる場合は、廃棄さ
れた容量はすぐには選択器に割り当てることができな
い。選択器または候補選択器によって初期化された最適
化は、選択器に知らせる能力を有している。

【００８６】案２で用いられた最適化アルゴリズムは、
最適化されたパスに割り当てようとする容量を選択器に
知らせなくてはならない。最適化アルゴリズムは、復旧
されたパスの終端間で検索方法を用いることによって、
サイレントパスを決定することができる。一旦この点が
見つかったら、以下に述べる復旧アルゴリズムとの互換
性を確保するために、以下の１組のルールがその後に続
く。・サイレントパス用に選択器からの容量を要求し、・サイレントパスを設定し、・復旧パス上の冗長容量を廃棄し、・選択器へ成功／故障および廃棄容量の確認を返送す
る。

【００８７】図１８において、アルゴリズムが最短パス
に第１の割り当て案を実行するため、最初の復旧ルート
が選択される。リンク上の容量が他のパスに割り当てら
れるか、故障したリンクからさらに他のリンクへ移さ
れ、特に送信器から主選択器へ移される。点数システム
は、各リンクに与えられた点数を最小化することによっ
て、どのようにして故障したリンクからのサイレントパ
スが見つけられるかを示す。

【００８８】サイレントパスの確立は、全体の割り当て
アルゴリズムに用いられる制御方法に依存する。案２で
説明された技術は、ここで説明する復旧アルゴリズムに
適している。他の復旧方法との互換性を確実にするに
は、変更の必要がある場合もある。

【００８９】ループ消去オリジナルパスから選択器（主または候補）へのパスと
送信器から選択器へのパスは、独立し、ループを含まな
い。この２つが連結するとループが生じる。図１９Ａ、
１９Ｂ、１９Ｃはどんなに簡単にループが生じるかを示
す図である。特に、高いネットワーク負荷で動作し、遅
延検知トラヒックを送っている場合は、ループに含まれ
ている容量をすべて廃棄し、故障したパスの復旧用に再
割り当てするのが好ましい。

【００９０】この復旧アルゴリズムに対してループ消去
アルゴリズムを行うには、主選択器をデータベース保持
者として考える必要がある。従ってループ消去アルゴリ
ズムは、１つの解決策に収束し、候補／主選択器に知ら
せなければならない。分布的にループ消去を行うと、選
択器において必要な処理電力を減少させ、フェールセー
フの解決策を設計するのに役立つ。ＶＣループ消去が実
行可能であるにもかかわらず、アルゴリズムはＶＰを用
いて示される。

【００９１】図２０は復旧パスを示し、それぞれｅ_sか
らｓへのＡ、またｅ_cからｃへのＢ、ｓからｃへのＲが
すべてのノードの通路になる。ここでｓおよびｃは送信
器および選択器ノード、ｅ_sおよびｅ_cは、それぞれ送信
器と選択器側のオリジナルパスの終端を示す。オリジナ
ルパスはループを含んでいないため、ＡおよびＢは共通
なノードを有していない。ノードＡ‖Ｒ‖Ｂ（ここで‖
は並列を示す）の通路によって形成された復旧パス中で
は、ループができる。グラフ理論から生じる基礎的な結
果によれば、通路Ａ‖Ｒ‖Ｂはループのないパスを含
む。このパスが、Ａ’‖Ｒ’‖Ｂ’であるとすると
（Ａ’は終端ｅ_sとｓ’を有するＡのサブ通路）、Ｒ’
は終端ｅ_cとｃを有するＲのサブ通路であり、Ｂ’は終
端ｓ’とｃ’を有するＢのサブ通路である。このアルゴ
リズムはｓ’およびｃ’を見つけ、解決策を送信する機
能を有する。

【００９２】ノードｓ’およびｃ’において、ループが
消去される前にバイパスされるような、また予備容量が
実際に廃棄された後にのみ選択器のデータベースを更新
するようなフェールセーフの方法で、アルゴリズムを変
化させる必要がある。独立した交点は２つしか存在しな
いため、復旧したパス中には、リンクのはずれたループ
は最大２つまで、１つはｓ’を、他はｃ’を有するルー
プがあってもよい。

【００９３】復旧パスが割り当てられた時、選択器がこ
のアルゴリズムを開始する。以上の理論に基づき、復旧
パスとオリジナルパスとの交点が決定されなければなら
ないことが分かる。そうするには、送信器／選択器間の
パス、およびその対応する終端ｅ_s、ｅ_cは、Ａ，Ｂおよ
びＲの印が付けられている。３つのパスの部分は、各ノ
ードのルーティングテーブル内でパス型フィールドを用
いて記されている。この処理を行うには、いくつかのフ
ィールドを有するメッセージＭが用いられる。このフィ
ールドは、インデックス値、パスタイプ、ループ廃棄通
知（ｒｅｌ）、ｓ’検出（Ｓ’）、ｃ’検出（Ｃ’）お
よび廃棄容量のテーブルを含む。

【００９４】１つのインデックスＭは、選択器からＶＰ
を通ってｅ_cへ送信される。パスタイプ＝ＢおよびＳ’
であり、Ｃ’およびｒｅｌはクリアされる。ここで、パ
ス中の各ノードは、そのＶＰに対するインデックスおよ
びパスタイプ値を記録する。メッセージは、ｅ_cからセ
ットＢノードの識別を示した選択器へ反映される。Ａお
よびＲに属するノードの識別はその後処理される。選択
器は、パスタイプ＝Ｒを有する復旧ルートを介してＭを
送信器へ送信し、送信器に届くまで各ノードはそのイン
デックスおよびパスタイプを記録する。送信器とｅ_sと
の間において、パスタイプ＝Ａでその処理は繰り返され
る。Ａ，ＢおよびＲが識別され、ｓ’およびｃ’の有効
ノードを発見し、ＶＰは交差接続する必要がある。ｅ_s
は、Ｓ’ビットセットを有するＭを反映し、Ａ中の各ノ
ードは、Ｒ、例えば、同一のインデックスパスタイプの
Ｒ・ＶＰ中に記録された同一のインデックスをチェック
する。

【００９５】そのような記録が存在する場合、パスは交
差し、Ｍは復旧パス上をＣ’ビットセットを有する選択
器の方向に送られる。この点から最初に現れた、同一の
インデックスパスタイプＢ・ＶＰがＲとＢの交点ノー
ド、例えばｃ’を示し、結果としてＭを受信したとき、
ノードはパスタイプＢを有する同一のインデックスＶＰ
をチェックする。もし、そのようなパスが見つかった
ら、ｃ’も見つかり、タイプＢおよびＲを有するＶＰ間
を接続することができる。ノードは、ｃ’の状態を記録
し、Ｓ’をセットし、Ｃ’をクリアし、ｓ’を位置づけ
るため、Ｍを送信器へ返送する。ｓ’は、タイプＡの、
同じインデックスパスを位置づけるための第１のノード
（これはｃ’と同じノードであってもよい）である。従
って、ＡとＲの交点、例えば、ｓ’を位置づける。Ｒタ
イプおよびＡタイプのＶＰは、点ｓ’で接続され、通路
Ａ’はＡ’‖Ｒ’‖Ｂ’、すなわち、ループなしパスを
完成する。

【００９６】ｓ’およびｃ’が識別され、パスが減少し
た時点で、ループは廃棄される。選択器は廃棄された容
量を知らされる必要があるので、ｓ’に関するループが
まず廃棄されなければならない。この処理は、ｒｅｌビ
ットセットを有する復旧されたルート上で、単にＭを送
信器に向けて送信することによって行う。各ノードは着
信ＶＰを廃棄し、その情報をＭのテーブルに記録する。
ｓ’が処理を終了し、Ｍがループを完了した時点でｒｅ
ｌビットをクリアし、Ｍをｃ’に向けて送信する。点
ｃ’において、Ｍ’が生成され、ＭおよびＭ’はそれぞ
れＲタイプおよびＢタイプパスに沿って、ｒｅｌビット
セットと共に選択器に向けて送られる。廃棄された容量
は記録され、選択器において双方のメッセージが終了す
る。選択器は、ＭおよびＭ’からのデータをデータベー
スに含むようにしてもよい。

【００９７】パスがループのない形に変更されるまでル
ープは削除されないため、ＭまたはＭ’のどちらかが失
われた場合には、アルゴリズムはフェールセーフとな
る。すべてのループが削除されたとき、選択器は廃棄さ
れた容量だけを知らされ、容量の割り当ての重複がない
ようにしている。この方法では、送信器または選択器を
含んでいるループを検索し、従って、故障部分の近くの
最も輻輳した領域で容量を再利用を容易にする。

【００９８】図２１Ａおよび２１Ｂは、この処理の主な
ステップをまとめている。ステップ１３０において、選
択器はループ消去を開始し、まだ選択器に接続されてい
るオリジナルパスの終端へメッセージを送信する。ステ
ップ１３１では、パスタイプＢのセグメントを位置を決
めるために、メッセージは選択器へ返送される。次に、
ステップ１３２では、選択器から送信器へ復旧パスを介
してメッセージが送られ、パスタイプＲセグメントの位
置を決める。ステップ１３３において、第３のセグメン
トタイプＡは、送信器からオリジナルパスを介して、ま
だ送信器に接続されている終端ノードへ送られたメッセ
ージによって識別される。ステップ１３４において、パ
スタイプＡセグメントがパスタイプＲセグメントと交わ
るまで、メッセージは、終端からオリジナルパスを介し
て送信される。

【００９９】図２１Ｂのステップ１３５において、メッ
セージはパスタイプＲセグメントがパスタイプＢセグメ
ント（ノードＣ）と交差するまで、復旧パスを介してノ
ードｎから選択器へ送られる。ここで、送信器の周りの
第１のループは切断される。ステップ１３６において、
メッセージはパスタイプＲセグメントがパスタイプＡセ
グメント（ノードＳ’）と交差するまで復旧パスを介し
てＣ’から送信器へ送信される。ここで、第２のループ
が切断される。ステップ１３７において、メッセージは
第２のループを介してＳ’からＳ’へ送信される。容量
は各ノードで廃棄されメッセージ中に記録される。最後
に、ステップ１３８において、メッセージはＳ’から
Ｃ’へ送信される。メッセージはＣ’において、２重化
され、双方は第１のループの半分を介して選択器へ送信
される。各ノードにおいて、容量は廃棄されたメッセー
ジ中に記録され、選択器へ伝達されて廃棄された容量を
再利用できるようにする。

【０１００】図２２は、ループ消去を行っているメッセ
ージの状態を示す図である。以下に示す状態遷移表で
は、ループ消去メッセージを伝達するノードに対して、
現在のおよび次の状態が示され、各遷移に対して現在の
ノードによって受信されるメッセージが示され、さら
に、現在のノードが取るべき動作が示される。

【０１０１】

【表２】

【０１０２】次に、図２２および表２を用いてメッセー
ジの遷移について説明する。まず、状態がＳｔａｒｔに
あるとき、表２に示すように受信メッセージが「ｒｅｌ
＝１、ｏｒ、ｓ’＝１、ｏｒ、ｃ’＝１」であると、そ
のメッセージＭを削除し、Ｓｔａｒｔに戻る。Ｓｔａｒ
ｔの実施の形態において、メッセージのパスタイプがＡ
であると、状態Ａに遷移し、メッセージのパスタイプが
Ｂであると、状態Ｂに遷移し、メッセージのパスタイプ
がＲであると、状態Ｒに遷移する。状態Ａ，Ｂ，Ｒにお
いて、それぞれメッセージが「ｒｅｌ＝１」であると、
着信ＶＰを廃棄し状態Ｅｎｄに遷移する。状態Ｒにおい
て、メッセージのパスタイプがＡであると、状態ＡＲに
遷移する。状態ＢＲにおいて、メッセージが「ｃ’＝
１，ｒｅｌ＝０」であると、状態ｃ’に遷移し、メッセ
ージが「ｒｅｌ＝１」であると、着信ＶＰを廃棄し状態
Ｅｎｄに遷移する。状態ＡＲにおいて、メッセージが
「ｓ’＝１，ｒｅｌ＝０」であると、状態ｓ’に遷移
し、メッセージが「ｒｅｌ＝１」であると、着信ＶＰを
廃棄し状態Ｅｎｄに遷移する。本発明にとって重要でな
い他の遷移部分は図示されているが説明を省略した。

【０１０３】非ループパス長減少以下に、他の分布最適化処理を説明する。この処理は他
の処理と併用してもよい。図２３では、ループを含まな
い復旧されたリンクが、どのようにしてリンク上で不必
要な容量を占めてしまうかを示している。与えられた容
量は、パスを移動するのに用いられる。現在、このよう
なパスを決定するには、グローバル復旧アルゴリズムが
必要であるが、これには時間がかかり、かなりの量のデ
ータ処理が必要になる。復旧能力を高めるために、高ス
ピード復旧技術用の、ローカルに制御される最適化方法
を以下に説明する。

【０１０４】この最適化処理では、単に、１つしかリン
クを用いていないパスの減少を決定して行われる。以下
の説明における基本的処理は、単純化された例である。
このアルゴリズムでは、復旧パスによって占められた複
数のリンクに置き換えることのできる１つのリンクを探
すので、処理が簡単で済む。従って、その１つのリンク
の終端は、復旧パス上になければならない。この最適化
処理は、その１つのリンクがパス上にないとき、そのリ
ンクによって分離されたパス上にすでにあるノードの簡
単なテストとなる。これは、１つのメッセージを終端の
１つから他方へ送信することによって行われる。メッセ
ージはパス上の各ノードを通過するたび、リンクに特有
なＩＤをマークする。その後、各ノードは、隣接ノード
が（パス上にあると分かっているノードは除く）同じＩ
Ｄを有しているかどうかテストする。もし、ノードが見
つかった場合は、そのノードが同じパス上に存在し、以
前に隣接していたノードについては終端に近いことを示
している。従って、パスは減少され、要求のあったリン
クで十分な予備容量を用いることができる。

【０１０５】結論、および実施時の考慮本発明は、特に、ノード複雑予備容量割り当てを用い
た、高負荷ネットワークの復旧に適している。従来のア
ルゴリズムでは、平均６０％のネットワークが用いられ
ていなければならず、予備容量は約４０％であった。そ
のときでさえも、十分な予備容量を得られるよう、あら
かじめ容量の割り当てを計画せねばならず、そうでなけ
れば１００％の復旧は望めなかった。しかしながら、現
在用いられているネットワークの多くは、コスト削減の
ため、９０％以上の負荷を有している。本発明は、予備
容量が約１０％しかない場合に、復旧作業を向上させる
のに適している。復旧作業は、変化し続けるネットワー
ク構成に動的に適応する分布方法を用いる。また、ネッ
トワーク計画を援助するのに用いてもよい。

【０１０６】仮想パスを用いたＡＴＭネットワークに使
用いる場合、ＶＰを最低保障容量レベルに下げることに
よって予備容量を増やすことができる。また、優先付け
することによって、また選択的にトラヒックを削除する
ことによって負荷を減らし、予備容量を増やすことも可
能である。

【０１０７】ＶＰの容量は、接続セットアップ時に決定
される。ネットワークのパスがＶＰに対して見つからな
い場合は、ＶＰを小さな単位に分割してもかまわない。
この処理は、仮想接続（ＶＣ）スイッチにおいてのみ行
うことができ、そうでないときはＶＰが全体として復旧
されなければならない。これは、最良な結果をけるため
に用いることのできるＡＴＭネットワークの利点の１つ
である。

【０１０８】復旧アルゴリズムを実行するとき、ネット
ワーク中の全てのノードは、送信器、主選択器、候補選
択器またはタンデムノードの機能を実行する能力を有し
ていなければならない。ループ消去アルゴリズムは、こ
れらの機能と並行して行なわれなければならない。復旧
の間、送信器から主選択器へ、また各候補選択器へ続く
全てのパスに関するデータベースを統合し、保持する必
要があるため、主選択器の機能は大方プロセッサおよび
メモリを内包している。

【０１０９】メモリの平均使用度はネットワークの平均
度合いに依存し、式（２）を用いて求められる。

【０１１０】

【式２】

【０１１１】ここで、ＮＤは平均ネットワーク度合い、
ＨＣは制限あふれ検索ホップカウントを示す。式（２）
において、（ＮＤ＋１）は候補選択器に対するものであ
り、候補選択器が１つしかない場合には、式（２）から
取り除く必要がある。候補選択器を用いるとエントリ数
が増えるが、候補選択器を用いないと、制限ホップカウ
ントが急激に増加し、エントリがさらに必要となる。

【０１１２】典型的には、ループ消去を伴う候補選択器
を用いる方法では、通常６ホップしか必要とされない。
従って、平均度合いのネットワークには、約４百万のエ
ントリが必要となる。候補選択器を有しないオリジナル
ＦＣＦＳアルゴリズムでは、１３までのホップが必要と
なり、約６７百万のエントリが必要となる。

【０１１３】処理電力はソフトウエアの設計によって変
わるので、見積もりが困難である。処理能力を測定する
ために、３２Ｍバイトのメモリを有するサンＳＰＡＲＣ
ステーション１０においてシミュレーションを行った。
遅延を付加し、候補選択器を有するループ消去アルゴリ
ズムでは、処理には１秒以下しかかからなかった。これ
には、復旧パスを決定するフラッディング処理や、ルー
プ消去アルゴリズムの分散処理にかかった時間も含まれ
ている。処理電力は、メモリの使用状況以外に、ネット
ワーク上の予備容量とその分布によっても異なる。現在
の交換機は、このようなアルゴリズムを行うのに十分な
処理能力を有しているはずである。

【０１１４】このアルゴリズムは、ネットワーク内のサ
ービスの品質を種々のレベルにすることができる。これ
は、ＶＰに対して注文のＱｏＳを作成するだけでなく、
ネットワーク内の異なるリンクに品質を割り当てること
を意味する。従って、ＶＰルーティングは、ＶＰ長、リ
ンクＱｏＳおよびサービスＱｏＳのパラメータによって
決定される。低い優先順位のパスを削除し、高い優先順
位のパスと入れ替えるバンピングと呼ばれる技術を用い
ることも可能である。

【０１１５】さらに、候補ノードの概念を広げることに
よって多くのバリエーションが可能である。候補選択器
セットは選択器に隣接する全てのノードを含む。候補選
択器セットの概念を用いることによって、ノード故障、
例えば、選択器ノードの故障に対する復旧作業を向上さ
せる。ノードの候補選択器セットをリンク故障に用いる
と、候補選択器に関するカットセット容量を増やすこと
ができ、従って、アルゴリズムの効率が良くなる。この
概念を送信器に隣接した全てのノードまで広げると、最
小カットセット容量が増え、復旧処理の効率がさらに向
上する結果となる。

【０１１６】以上に述べてきたように、送信器が各候補
選択器と「主」選択器の間に１つのあふれ例を生成する
ことを提案する。これを行うには、送信器は各ＶＰに対
するすべての候補ノードのノード識別を要求する。これ
は、ノード復旧に必要であるため、それなりの理由があ
る。すべての検索例に対して、タンデムノードは選択器
（候補または主）に同量の予備容量を知らせる。候補選
択器が自分宛のメッセージを受信すると、受信した情報
を主選択器に知らせる。データベースに基づき、主選択
器は候補選択器を通過した故障ＶＰ、およびその復旧に
利用できる予備容量の量を識別する。主選択器は、復旧
処理すべてを候補選択器に通知する。その通知が終了し
たら、候補選択器はループ消去処理を開始し、廃棄され
た容量があればその旨主選択器に知らせる。このメッセ
ージ伝達構成は、候補選択器という概念を導入するとき
さらに複雑になり、適切な構成を作るには注意が必要と
なる場合もある。

【０１１７】従来のアルゴリズムに対して、本発明の復
旧処理の向上は、候補選択器を用いる場合に最も発揮さ
れる。従って、適用時に候補送信器を候補選択器に割り
当てるなど、候補送信器の概念を拡大することによって
さらに復旧処理の効率が向上する。候補ノード復旧を完
全に行うには、送信器と選択器の間には１つのあふれ例
しか必要でない。さらなる処理が選択器ノードに導入さ
れる。選択器は、候補選択器から候補送信器への各ＶＰ
のルート、例えば、３ホップを知っておく必要がある。
選択器が復旧パスを受信すると、送信器／選択器放送検
索処理を介して、候補ノード復旧に対するパスをテスト
することもできる。すべての復旧パスに対して、隣接す
る各送信器を候補送信器と呼ぶ。同様に、隣接する各選
択器を候補選択器と呼ぶ。候補送信器ノードが候補選択
器ノードである場合もある。

【０１１８】各復旧パスの詳細が主選択器に着くと、選
択器は、候補送信器および候補選択器へのリンク、例え
ば、パス中の第１のリンクと最後のリンク、を無視する
ことによって、容量を増やすことができるかどうか決定
する。もし、容量を増やすことが可能であるならば、こ
の復旧パスにおける復旧容量は、両候補ノードを含んだ
すべての故障ＶＰに対して増加する。このようなＶＰ
は、候補送信器／選択器ＶＰ（ＣＳＣＶＰ）として知ら
れている。これ以上のＣＳＣＶＰが復旧できなくなった
ときには、復旧パスは、候補送信リンクと候補選択器リ
ンクを含むように考慮される。各考慮において、アルゴ
リズムは、それぞれ、候補送信器ＶＰ（ＣＳＶＰ）およ
び候補選択器ＶＰ（ＣＣＶＰ）を復旧しようとする。Ｃ
ＳＶＰは、候補送信器と実際の選択器の間に延びるよう
に定義され、ＣＣＶＰは候補選択器と実際の送信器の間
に延びるように定義される。

【０１１９】復旧パスを変更する度に、パスの容量は変
更された復旧パスの最小値、例えば、候補ノードリンク
の最小量、またはパスの変更されていない部分に残って
いる容量に設定される。ＣＳＣＶＰがもう無いときに、
ＣＳＶＰおよびＣＣＶＰが存在し、復旧パス容量は、再
設定された両方の候補ノードリンクを有する復旧パスの
最小値に設定される。全ての他の故障したＶＰは、復旧
パス全体で処理される。この方法を用いると、送信器お
よび選択器に関するカットセット容量を、より頻繁に増
やすことができる。すべてのＶＰを最初にフィットした
アルゴリズムを用いて復旧パスに割り当てると、一見、
アルゴリズムの効率を悪くすると思えるかもしれない。
しかしながら、計算時間を短くしたい場合に有用であ
る。最悪のまたは最良のケースに対しては、さらに処理
が必要となり、処理の向上は望めない。他のバリエーシ
ョンも、クレームの範囲内で当業界の技術者には自明で
ある。

【０１２０】

【発明の効果】本発明の第１の発明によれば、各リンク
の予備容量を決定することは、チャネルまたは仮想パス
ベースで容量を割り当てるより、予備容量の不十分な一
時的割り当てを減少できる。

【０１２１】本発明の第２の発明によれば、選択器ノー
ドは、メッセージ伝達量を減らしたり、応答を早めた
り、各ノードにおける既存の処理能力をより経済的に使
用したりことができるため、集中制御器は必要なくな
る。

【０１２２】本発明の第３の発明によれば、要求された
容量を単に割り当てるよりも、リンク予備容量を決定す
ることによって、ネットワーク故障に影響された各ルー
ト毎に代替ルートに対して検索メッセージを送出する必
要はない。このようにして検索メッセージの数は減少さ
れ、応答時間も減り、代替ルートの容量割り当ての効率
も向上する。後者の利点は、検索メッセージによって故
障部分の周辺により長い代替ルートの特定のパスに対し
ても、一時的な容量の割り当てをする必要がなくなるこ
とである。

【０１２３】本発明の第４の発明によれば、代替ルート
が選択された後にのみ予備容量を割り当てることもま
た、上記の長所を可能にする。選択ステップは、上述の
ように代替ルートが最適化されるまで遅延できる。

【０１２４】本発明の第５の発明によれば、故障部分の
近隣で用いられるノードの数に基づいて選択することに
よって、選択は、故障部分に近いノードを用いない代替
ルートに重み付けできる。多くのルートが故障部分で交
差するところでは、復旧のための予備容量は故障部分近
隣で制限される。したがって、代替ルートの付加的な長
さを制限するものではあるが、故障部分近隣を回避する
代替ルートは、予備容量の全体的な利用状態を向上させ
る。

【０１２５】本発明の第６の発明によれば、ＡＴＭネッ
トワーク中の仮想パスは、ネットワークを介して通過す
る情報によってルートを決定されてもよいが、そのよう
なパスまたは回路は、ハードウエアよりむしろソフトウ
エアの動作によって作られたり壊されたりするため、一
時的に多くのパスまたは回路を作るほうが、より簡単で
より迅速に行われる。これによって復旧がより困難にな
ることもある。本発明は特にこのようなネットワークに
適している。

【０１２６】本発明の第７の発明によれば、故障部位の
一方送信器ノードからメッセージを送信し、故障部位の
他方の選択器ノードで選択ステップを実行することによ
って、ローカル的な中央集中処理の形態が復旧のために
用いられるので、複雑で維持が困難な全体的な中央集中
制御器を用いる必要が無くなる。処理はノード間に完全
に分布され、その処理は他の目的のための処理能力も持
ち合わせることができる。その処理においては、ネット
ワーク構成を前もって知る必要がなく、処理はネットワ
ーク構成における変化に完全に適応できる。それにも関
わらず、選択器ノードは故障部分周辺のネットワークに
関する情報を集め、単にその近隣の情報のみでなく、故
障部分周辺のネットワークに関する情報を考慮して選択
ステップを行うため、ローカル的な中央集中制御器が必
要となる。

【０１２７】本発明の第８の発明によれば、選択器ノー
ドが通信のためのオリジナルルートの一つである場合
は、選択器ノードは、オリジナルル−トの部分を選択さ
れた代替ルート中に簡単に収容できる。

【０１２８】本発明の第９の発明によれば、候補選択器
は選択器を通過していない代替ルートを選択するための
選択処理要求を引き継ぐことができ、従って、選択器に
よって実行される処理量を減少させることができ、故障
部分から離れた代替ルートを選択することができる。

【０１２９】本発明の第１０の発明によれば、選択され
たルートの最適化によって予備容量がより良く使われる
ようにすることができる。特に代替ルートの選択が、３
つのセクション、すなわち、故障部分の前のオリジナル
ルートと、故障部分の後のオリジナルルートと、故障ル
ート周辺の迂回セクションからなる場合には、迂回部分
はオリジナルルートの部分に沿って、または近くに、戻
ることもある。このように、全体的なルートを最適化し
て、そのような無駄なバックトラックを除去することが
可能となる。

【０１３０】本発明の第１６の発明によれば、選択器ノ
ードを用いて割り当てを制御することによって、復旧処
理を能率的に分配することができる。リンク容量を決定
するために同一の検索メッセージを用いることによっ
て、容量を一時的に割り当てることなく、多数のルート
の復旧改善ができる。

【図面の簡単な説明】

【図１】従来の復旧方法を示すフローチャートであ
る。

【図２】一般的なネットワークの概略図である。

【図３】本発明の復旧方法を示すフローチャートであ
る。

【図４】本発明の復旧方法を示すフローチャートであ
る。

【図５】図２のネットワークに用いられるノードの内
部の構造を示す概略図である。

【図６】図５のノードのルーティング機能を示す概略
図である。

【図７】図５のノードのデータベースを示す概略図で
ある。

【図８】図５のノードの復旧機能を示すフローチャー
トである。

【図９】本発明の方法における選択器ノードの動作を
示すフローチャートである。

【図１０】本発明の方法におけるタンデムノードの機
能を示すフローチャートである。

【図１１】本発明の方法の送信器ノードの機能を示す
フローチャートである。

【図１２】故障ノードを含むネットワークを示す図で
ある。

【図１３】図１２の保護ノード「Ｈ」を示す概略図で
ある。

【図１４】候補選択器ノードと主選択器ノードを含む
ネットワークを示す図である。

【図１５】候補選択器のいくつかの機能を示すフロー
チャートである。

【図１６】本発明の最適化を用いた復旧方法を示すフ
ローチャートである。

【図１７】図１６におけるルートが最適化されたかど
うかを決定する詳細ステップである。

【図１８】故障箇所からの距離の評価を行うネットワ
ークを示す図である。

【図１９】ネットワーク中にノードおよび、ループ消
去処理を示す図である。

【図２０】ノードのネットワークおよび、ループ消去
メッセージが後続するパスを示す図である。

【図２１Ａ】ループ消去メッセージの動作を示すフロ
ーチャートである。

【図２１Ｂ】ループ消去メッセージの動作を示すフロ
ーチャートである。

【図２２】ループ消去実行メッセージ用の状態図を示
す図である。

【図２３】非ループパス長の減少を示す概略図であ
る。

【符号の説明】

６１終端６２終端６３送信器ノード６４選択器ノード６５タンデムノード７０ノード７１切り替え７２ルーティング機能７３復旧７４データベース７５ＯＡＭ１７０保護ノード「Ｃ」１７１保護ノード「Ｈ」１７２故障したノード１７３保護ノード「Ｄ」１７４保護ノード「Ｌ」１８０候補選択器ノード

【数２】

───────────────────────────────────────────────────── フロントページの続き (72)発明者マーク・ベンタルイギリス国，エヌピー２１エスエヌ，グエント，ブラックウッド，ブランデュー 29 (72)発明者ブライアン・チャールス・ハーグラブ・タートンイギリス国，シーエフ64 ５ティーティー，サウスグラム，ペナース，サリー, エルワーシークロース 14

Claims

【特許請求の範囲】

【請求項１】複数のノード、ノード間のリンクを有す
るネットワークの一部が故障した後、ネットワーク中の
ノード間で通信を行うための代替ルートを決定する方法
において：故障した部分のまわりに複数の代替ルートを
決定し、代替ルートに沿ってメッセージをノード間で伝達し、上
記代替ルート中の各リンクの予備容量を決定し、少なくとも決定されたリンク予備容量に基づいて、上記
の可能な代替ルートからの通信に対して、１つの代替ル
ートを選択することを特徴とする代替ルート決定方法。
【請求項２】少なくとも１つのノードを選択器ノード
として選択し、決定された予備容量に関する情報を選択器ノードへ伝達
するステップをさらに含み、前記１つの代替ルートを選択するステップは選択器ノー
ドが行うことを特徴とする請求項１記載の代替ルート決
定方法。
【請求項３】選択器を用いて、始めに決定されたリン
ク予備容量および第１の代替ルートによって占められて
いる容量に基づいて、通信をするための代替ルートを選
択するステップをさらに含むことを特徴とする請求項２
記載の代替ルート決定方法。
【請求項４】選択されたルートによって使用される各
リンクの予備容量の少なくとも１部を選択したルートに
割り当てるステップをさらに含むことを特徴とする請求
項１乃至３のいづれかに記載の代替ルート決定方法。
【請求項５】代替ルートが故障した部分の近隣のノー
ドを使ったかどうか決定するステップをさらに含み、前記選択ステップは、故障部分の近隣で使用される決定
されたノード数に基づいて行われることを特徴とする請
求項１乃至４のいづれかに記載の代替ルート決定方法。
【請求項６】ルートが仮想パスを含むことを特徴とす
る上記請求項１乃至５のいづれかに記載の代替ルート決
定方法。
【請求項７】故障部位の一方において送信器ノードを
選択し、そこからメッセージが送信され、故障部位の他方において選択器ノードを選択し、メッセ
ージを受信するステップをさらに含み、決定された予備容量に関する情報は選択器ノードに保存
され、選択されたステップは選択器ノードによって実行
されることを特徴とする請求項１乃至６のいづれかに記
載の代替ルート決定方法。
【請求項８】前記選択器ノードは、故障する前に通信
に用いられたオリジナルルート上のノードの一つである
ことを特徴とする請求項７記載の代替ルート決定方法。
【請求項９】オリジナルルート上で、故障した部分か
ら少なくとも１つの候補選択器ノードが識別され、メッ
セージは候補選択器にも送信され、選択器を通過してい
ない代替ルートを決定することを特徴とする請求項８記
載の代替ルート決定方法。
【請求項１０】通信用のオリジナルルート上で、故障
した部分から少なくとも１つの候補送信器ノードが識別
され、メッセージが候補送信器ノードから送信され、送
信器を通過していない代替ルートを決定することを特徴
とする請求項８または９記載の代替ルート決定方法。
【請求項１１】選択した代替ルートを変更しそれを最
適化するステップをさらに含むことを特徴とする請求項
１乃至１０のいづれかに記載の代替ルート決定方法。
【請求項１２】最適化のステップは選択された代替ル
ート長を減少させるステップを含むことを特徴とする請
求項１１記載の代替ルート決定方法。
【請求項１３】最適化のステップは、故障した部分の
近隣のノードを用いないようにするステップを含んだこ
とを特徴とする請求項１１または１２記載の代替ルート
決定方法。
【請求項１４】代替ルートの１つの予備容量の１部を
第１の通信に割り当て、始めに決定された予備容量と既に割り当てられた予備容
量に基づいて、残りの予備容量を同時に発生する他の通
信に割り当てるステップを含み、複数の通信を同時に行うための代替ルートを提供するこ
とを特徴とする請求項１乃至１３のいづれかに記載の代
替ルート決定方法。
【請求項１５】選択された代替ルートを通信用に用い
るステップをさらに含むことを特徴とする請求項１乃至
１４のいづれかに記載の代替ルート決定方法。
【請求項１６】複数のノードおよびノード間のリンク
から構成されるネットワークの一部に複数の通信に影響
がでる故障が起きた後、ネットワークのノード間で同時
に発生する複数の通信を行うために代替ルートを供給す
る方法において：ルートのが故障を決定し、故障した部分の周りの代替ルートを決定し、故障した部分の近隣のノードの少なくとも１つを選択器
ノードとして選択し、代替ルート上の予備容量を決定
し、選択器ノードを用いて、代替ルート上で決定された
予備容量を複数の同時発生する通信への割り当てを制御
するステップを含むことを特徴とする代替ルート供給方
法。
【請求項１７】ノードを介してネットワーク上で設定
されたルートに沿って情報を伝達するために、ノードを
接続する複数のノードとリンクを含むネットワークにお
いて：ネットワークの１部が故障した場合、複数の代替
ルートを決定する手段と、代替ルートの沿ってメッセージを伝達し、代替ルート中
の各リンクの予備容量を決定する手段と、決定されたリンク予備容量に基づいて、代替ルートの１
つを選択する手段とを含むことを特徴とするネットワー
ク。
【請求項１８】リンクで相互接続された複数のノード
からなり、ネットワーク上に設定されたルートに沿って
情報を伝達するネットワーク用ノードにおいて：ネット
ワークの１部が故障した場合、複数の代替ルートを決定
する手段と、代替ルートの沿ってメッセージを伝達し、代替ルート中
の各リンクの予備容量を決定する手段と、各リンクの予備容量に関した情報を受信し、その受信し
た情報に基づいて、代替ルートの少なくとも１つを選択
する手段とを含むことを特徴とするネットワーク用ノー
ド。