JPH04152735A - 迂回パス探索方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概　要〕 任意の構造を有する通信ネットワークにおいてノードま
たはリンクに障害が発生したときに、障害のあるノード
またはリンクを迂回するパスを決定する方法に関し、 ノードの障害にも対処可能であり比較的短時間での被障
害パスの復旧を可能とする迂回パス探索方法を提供する
ことを目的とし、 複数のノードと該ノードを連結する複数のリンクとで構
成される任意の構造のネットワーク上に２つのノード間
のパスを設定することにより該２つのノード間で情報を
伝達する通信ネットワークにおいて障害が発生したとき
に、該設定されたパスのそれぞれについて障害個所を迂
回する迂回路を探索し決定することにより該２っのノー
ド間のパスを修復するための迂回パス探索方法であって
、該設定されたパスに沿って伝達される情報のそれぞれ
に対応してＮ個までの７−ド織別子をパストレーサとし
て収釣るパスオーバーヘッドの区間を設けて情報ととも
に伝達し、ただしＮは２以上の整数であり、ノードに到
達した該パストレーサを記憶し、該パストレーサ内のノ
ード識別子がＮ個であるときは最古のノード識別子を捨
てて到達したノードの識別子を追加し、送出し、ノード
が障害を検知したとき障害を検知したノードを迂回路の
始点ノードと決定し、該始点ノードが記憶しているパス
トレーサのうち被障害パスのすべてについてのパストレ
ーサ内の情報を含む一種類の迂回路探索メツセージを、
該始点ノードに接続されかつ予備パスが残っているすべ
てのリンクに対して発信し、ノードが該迂回路探索メツ
セージを受信したとき、該受信ノードが迂回路の終点ノ
ードの少なくとも候補に該当するか否かを該メツセージ
の内容にもとづき判定し、該判定の結果、該受信ノード
が終点ノードの少なくとも候補に該当しないと判定され
るとき、該メツセージを受けたリンク以外であり、かつ
、予備パスが残っているすべてのリンクに対して迂回路
探索メツセージを送出し、該判定の結果、終点ノードの
少なくとも候補に該当すると判定されたノードに到達し
た迂回路探索メツセージの経路のうち少なくとも一部の
経路を迂回路と決定することを特徴として構成する。

〔産業上の利用分野〕

本発明は、任意の構造を有する通信ネットワークにおい
てノードまたはリンクに障害が発生したときに、障害の
あるノードまたはリンクを迂回するパスを決定する方法
、特に、回線交換網およびパケット交換網を含む広域ネ
ットワークにおいて、各ノードが自律的に迂回路を探索
する分散制御方式により迂回パスを決定する方法に関す
る。

〔従来の技術〕

従来では障害が発生した個所を迂回するパスを探索して
決定するために、集中制御方式が採用されている。この
方式はネットワーク全体の状態を監視するネットワーク
制御センタを設け、障害の発生が通知されたらこのネッ
トワーク制御センタにおいて障害個所を迂回するパスを
探索するというものである。

この方式では、ネットワークの規模が大きくなると迂回
パスを探索する時間が長くなること、また、センタが障
害を起こした場合には機能しないこと等の問題があった
。

そこで、集中的な監視手段を特に設けず、フラッディン
グ（ｆ　１ｏａｄ　ｉｎｇ）の手法を用いて各ノードが
自律して迂回パスの探索を行なう分散制御方式を採用し
て障害復旧時間を短縮し、ネットワーク全体の信頼性を
向上させることが考えられる。

ここでフラッディングとは、始点ノードから経路を指定
することなく終点ノードのみを指定したメツセージを、
そのノードに接続されたすべてのリンクに送出し、この
メツセージを受けたノードは自ノードが終点ノードに該
当しないときは、そのメツセージをそのノードに接続さ
れたすべてのリンクに中継送出する。このような手続き
を繰り返すことによって、メツセージを最終的に終点ノ
ードに到達させようとするものであって、従来、パケッ
ト通信におけるルーティングの方法として知られている
ものであり、非常に高い信頼性を有するルーティングを
行うことができるものである。

〔発明が解決しようとする課題〕

このフラッディングの手法を迂回パスの探索のために採
用するとしても、迂回路の始点および終点をいかに適切
に決定し、いかに効率良く迂回路を決定するかが問題と
なる。

すなわち、障害の発生個所をリンクのみに限定すること
ができるならば、障害リンクの両端のノード間で迂回路
を探索すれば良いのであるが、ノードに障害が発生した
場合も含めて対処可能とする場合には、迂回路の始点お
よび終点を適切に定めるのは容易ではなく、また、ノー
ドに障害が発生したときにはリンク障害よりも影響を受
ける回線数が増大するので処理が複雑化し復旧時間が増
大するという問題がある。

したがって本発明の目的は、ノードの障害にも対処可能
であり比較的短時間での被障害パスの復旧を可能とする
迂回パス探索方法を提供することにある。

〔課題を解決するための手段〕

前述の目的を達成する本”発明に係る迂回パス探索方法
は、複数のノードと該ノードを連結する複数のリンクと
で構成される任意の構造のネットワーク上に２つのノー
ド間のパスを設定することにより該２つのノード間で情
報を伝達する通信ネットワークにおいて障害が発生した
ときに、被障害パスのそれぞれについて障害個所を迂回
する迂回路を探索し決定することにより２つのノード間
のパスを修復するための迂回パス探索方法であって、１
）該設定されたパスに沿って伝達される情報のそれぞれ
に対応してＮ個までのノード識別子をパストレーサとし
て収めるパスオーバーヘッドの区間を設けて情報ととも
に伝達し、ただしＮは２以上の整数であり、 ｉｉ）ノードに到達した該パストレーサを記憶し、該パ
ストレーサ内のノード識別子がＮ個であるときは最古の
ノード識別子を捨てて到達ノードの識別子を追加しＮ個
未満であるときは到達ノードの識別子を追加してパスト
レーサを更新し、更新したパストレーサを情報とともに
送出し、１ｉｉ）ノードが障害を検知したとき障害を検
知したノードを迂回路の始点ノードと決定し、ｉｖ）該
始点ノードが記憶しているパストレーサのうち被障害パ
スのすべてについてのパストレーサに含まれる情報を含
む一種類の迂回路探索メツセージを、該始点ノードに接
続されかつ予備パスが残っているすべてのリンクに対し
て発信し、■）ノードが該迂回路探索メツセージを受信
したとき、該受信ノードが迂回路の終点ノードの少なく
とも候補に該当するか否かを該メツセージの内容にもと
づき判定し、 ｖｉ）該判定の結果、該受信ノードが終点ノードの少な
くとも候補に該当しないと判定されるとき、該メツセー
ジを受けたリンク以外であり、かつ、予備パスが残って
いるすべてのリンクに対して迂回路探索メツセージを送
出し、 ｖｉｉ）該判定の結果、終点ノードの少なくとも候補に
該当すると判定されたノードに到達した迂回路探索メツ
セージの経路のうち少なくとも一部の経路を迂回路と決
定することを特徴とするものである。

また、前述の方法において、前記迂回路探索メツセージ
は前記始点ノードが記憶するパストレーサのうち障害パ
スの各々に対応して配憶されたノード識別子のすべてを
その障害パスの迂回路の終点ノードの候補を表わすもの
として含み、前記判定Ｖ〉は、前記受信ノードが該迂回
路探索メツセージ内のノード識別子のいずれかに該当す
るか否かを判定することにより該受信ノードが終点ノー
ドの候補であるか否かを判定することであり、前記迂回
路の決定ｖｉ）は、該判定Ｖ）において前記受信ノード
が終点ノードの候補であると判定されたとき、該終点ノ
ードの候補に到達した迂回路探索メツセージの経路に沿
って逆方向に伝達される迂回路設定メツセージを送出し
、同一の被障害パスに対応する迂回路設定メツセージの
うち最先に始点ノードに到達した迂回路設定メツセージ
を発した終点ノードの候補をその被障害パスの迂回路の
終点と、迂回路設定メツセージの経路をその障害パスの
迂回路と決定することであるのが好適である。

また、前述の方法において、前記迂回路探索メツセージ
は前記始点ノードが記憶するパストレーサのうち被障害
パスの各々に対応して記憶されたパストレーサに含まれ
るノード識別子のうち最古のものをその被障害パスの迂
回路の終点ノードを表わすものとして含み、前記判定Ｖ
）は前記受信ノードが該迂回路探索メツセージ内のノー
ド識別子のいずれかに該当するか否かを判定することに
より該受信ノードが終点ノードであるか否かを判定する
ことであり、前記迂回路の決定ｖｉｉ）は該終点ノード
に最先に到達した迂回路探索メツセージの経路を迂回路
と決定することでもまた好適である。

〔作　用〕

前述の最初に記述した探索方法において、各ノードに記
憶されるパストレーサは、パスに沿って伝達されそのノ
ードに到達した情報が経由してきたノードのうち最新の
Ｎ個までのノードの識別子をパスごとに含んでいる。し
たがって、障害を検知したノードに記憶されるパストレ
ーサのうち、障害を受けたパスについてのパストレーサ
に含まれるＮ個のノード識別子が表わすＮ個のノードの
いずれかを終点とし、障害を検知したノードを始点とす
る経路をフラッディングにより探索する。

Ｎは２以上の整数であるので、たとえノードに障害があ
ってもその前のノードとの間で迂回路を見い出すことが
できる。この場合に、複数の被障害パスがあり、それに
対応するパストレーサの内容が異なっていれば迂回路の
終点が異なる場合がある。しかしながら、その場合であ
ってもそれぞれについて異なるメツセージを発信するよ
りも、すべての被障害パスに関する情報を含む一種類の
迂回路探索メツセージを発信することにより、メツセー
ジの輻輳が軽減され、復旧時間が短縮される。

第２および第３に記述された方法によれば、前述の作用
に加えて各被障害パスについてパストレーサに記憶され
たＮ個のノードのうち適切な１つを選択する方法が提供
される。

すなわち、第２の方法によれば、Ｎ個のノードのすべて
を終点ノードの候補として含む迂回路探索メツセージを
発信し、これを受けたノードがそれらの１つに該当して
いれば受信した迂回路探索メツセージの経路に沿って逆
の方向に迂回路設定メツセージを返し、最先に始点ノー
ドに到達したものを迂回路と決定するというものである
。したがって、Ｎの値を大きくとってもその中で適切な
ノードが自動的に選択され、適切な長さの迂回路が設定
される。ただし、始点と終点との間でメツセージが往復
して始めて迂回路が決定されるために迂回路決定までに
比較的時間を要し、メツセージの数も多くなるので復旧
時間が比較的長くなる。

一方、第３の方法によれば、パストレーサ内のＮ番目の
ノードを終点として迂回路探索メツセージを発信し、そ
の終点に最初に到達したメツセージの経路を迂回路と決
定するものである。したがって、第２の方法よりも復旧
時間が短縮される。

しかし、Ｎの値を大きくとると迂回路が長くなるので、
Ｎの値は小さくとる方が良い。

〔実施例〕

第１図は本発明が適用される通信ネットワークの一例を
表わす図である。図には７つのノードＡ〜Ｅ、Ｘ、Ｙと
それらを結合するリンクＡＢ。

ＢＣ，ＣＤ、ＤＥ、ＣＸ、ＣＹが示されている。

また図に示すような経路でパス１〜４が設定されている
。ノードＡ−Ｅ、Ｘ、Ｙはさらに第１図には図示しない
リンクおよびノードとリンクの組み合わせで結合されて
おり、これらによってパス１〜４を構成するノードまた
はリンクに障害があった時の迂回路が形成される。また
、図示されているリンクに平行にこれらと逆向きのリン
ク（図示せず）も設置されている。

第２図は情報とともに伝達され、各ノードに蓄積される
パストレーサを説明するための図であり、（ａ）欄は第
１図のリンクＡＢにおいて伝送される情報の形式を表わ
し、（ｂ）欄はパス１に沿って伝送され蓄積されるパス
トレーサを表わし、（Ｃ）欄は各ノードに蓄積されたパ
ストレーサを表わす。

（ａ）欄に示されるように１フレームの情報はセクショ
ンオーバーヘッド１０、ハス情報１２−１〜１２−ｎお
よびパス情報１２−１〜１２−ｎの各々に付されたパス
オーバーヘッド１４−１〜１４−ｎの領域からなってい
る。第１図に示すようにリンクＡＢにはパス１およびパ
ス２が設定されており、したがってパス情報１２−１と
１２−２はそれぞれパス１とパス２で占有されそれ以外
のパス情報１２−３〜１２−ｎの領域を予備パスと称す
ることとする。すなわちリンクＡＢには既に使用されて
いる２本のパスとｎ−２本の予備パスとの合計でｎ本ま
でのパスを設定することが可能である。セクションオー
バーヘッド１０の領域は迂回路探索メツセージおよび迂
回路設定メツセージ（後述）等の制御メツセージを伝送
するために確保されている。

パスオーバーヘッド１４−１〜１４−ｎの領域において
は（ｂ）欄に示すようにパス（パス１）に沿ったノード
（ノードＡ−Ｅ）に到達する毎にパストレーサのリード
／ライトが繰り返される。すなわち、ノードＡではノー
ドＡの識別子が書込まれ、ノードＢにおいて読み出され
ノードＢに蓄積されるパストレーサには（Ｃ）欄の５０
で示すように、パス１に対してノードＡの識別子が含ま
れている。

ノードＢからリンクＢＣへ送出されるパストレーサには
ノードＢの識別子が加えられるので、ノードＣで受信さ
れ記憶されるパストレーサには（Ｃ）欄の５１で示すよ
うに、パス１に対してノードＡとノードＢの識別子が含
まれている。この例ではパスオーバーヘッド内には２個
までの識別子が含まれるようになっているので（Ｎ＝２
）、ノードＣからリンクＣＤへ送出されるときはノード
Ａの識別子は捨てられ、ノードＣの識別子が新たに追加
される。したがって、ノードＤで受信され記憶されるパ
ストレーサには（Ｃ）欄の５２に示すようにパス１に対
してノードＢとノードＣの識別子が含まれる。

第３図は本発明の一実施例におけるノードの構成を示し
ている。同図において１８はリンクを示し、リンク１８
を介して太実線で示す複数のパス情報１２、パス情報１
２のそれぞれに対応する結実線で示すパス・オーバヘッ
ド１４、点線で示すセクション・オーバヘッド１０から
なる情報が伝送されることが示されている。２０はマト
リクス・スイッチであって、パス情報１２、パス・オー
バヘッド１４のクロスコネクトを行う。２４はアラーム
発生回路（ＡＬＭ）であって、リンク１８の信号断を検
出して障害のアラームを発生する。２６はセクション・
オーバヘッド・インタフェース（ＳＥＣＯＶＨＩＮＦ）
であって、中央処理装置（ＣＰＬＩ）　３６との間にお
けるセクション・オーバヘッドのインタフェース処理を
行う。２８はパス・オーバヘッド・インタフェース（Ｐ
ＡＴＨＯＶＨＬＮＦ）であって、パス・オーバヘッド１
４とＣＰＩＩ　３６との間におけるインタフェース処理
を行う。３０はマトリクス・スイッチ・インタフェース
（ＳＷ　ＩＮＦ）であって、マトリクス・スイッチ２０
とＣＰｔ１３６との間におけるインタフェース処理を行
う。ＡＬＭ　２４．　ＳＥＣＯＶＨｌＮＦ２８、　ＰＡ
ＴＨＯＶＨＩＮＦ　２６．　　ＳＷ　ＩＮＦ　３０とＣ
Ｐ［Ｊ　３６との間は、パス２２によって接続されてい
る。ＣＰＵ　３６は、ノードにおける動作の全体を制御
する。またパス２２に接続された記憶装置（ＭＥＭ）　
３８には、前述のパス・トレーサの各パスの使用状況等
の情報を蓄積する。

第１図の例を参照して本発明の第１の実施例を説明する
。以下にはＮ＝２の場合について説明するが、Ｎが３以
上である場合も以下の記述にもとづき容易に実施するこ
とが可能である。第１図に示されるように、パス１〜４
は、正常時においてはそれぞれ次のノードを通過してい
る。

パス１：ノードＢ−ノードＣ−ノードＤパス２：ノード
Ｂ−ノードＣ−ノードＤパス３：ノードＸ−ノードＣ−
ノードＤパス４：ノードＹ−ノードＣ−ノードＤ第４図
に表わすように、いまノードＣにおいて障害が発生し、
ノードＤがリンクＣＤにおける信号断としてこれを検出
して、障害アラームが発生したものとする。

ノードＤにおいては、迂回パス探索ソフトウェアがこの
アラームによって起動されて、以下のような処理を実行
する。

（１）まず、アラームが発生しているノードＤを通過す
るリンクＣＤにおけるパスを検索して、障害の影響を受
けているパス（被障害パス）を特定する。この場合の被
障害パスは、パス１〜４である。

（２）ノードＤに蓄積されているパス１〜４のパス・ト
レーサを調べて、同一のパス・トレーサを有するグルー
プに分割し、それぞれのグループに属するパス数を求め
る。この場合のグループと各グループに属するパス数は
、次のようになる。

グループ１　（ノードＣ−ノードＢ）＝２本グループ２
　（ノードＣ−ノードｘ）＝１本グループ３　（ノード
Ｃ−ノードＹ）：１本（３）ノードＤを迂回パスの始点
とし、パス・トレーサに含まれるノードを迂回パスの終
点ノードの候補とする迂回路探索メツセージを、ノード
Ｄに接続された出力リンクのうち予備パス（第２図（ａ
）欄を参照して既に説明法）が残っている出力リンクの
すべてに対してセクション・オーバヘッド１０の領域を
用いて、隣接ノードへ送信する。予備パスの有無および
その数は、各ノードが常時検索してその情報を記憶装置
に蓄積している。この迂回路探索メツセージには、次の
各情報を書き込んでおく。

■　迂回路探索メツセージ発信元ノードのＩＤ（迂回路
の始点となる） ■　パス・トレーサに書かれている第１のノードのＩＤ
（迂回路の終点の候補となる）■　各グループのパス・
トレーサに書かれている第２のノードのＩＤ（迂回路の
終点の候補となる） ■　■■に書かれたノードＩＤのそれぞれに対応した被
障害パスの数 ■　被障害パスのＩＤ 例えば前述の例の場合は、上記の■〜■の情報は次のよ
うになる。

■　ノードＤ ■　ノードＣ ■　ノードＢ１ノードＸ１ノードＹ ■　４．２．１．１ ■　パス１、パス２、パス３、パス４ （４）迂回路探索メツセージを受信したノードは、迂回
路探索メツセージにおける上述の■、■のフィールドを
読み出して、自ノードが迂回路の終点の候補になってい
るかどうかを調べる。

自ノードが迂回路の終点の候補になっていない場合は、
予備のパスがあるすべての出力リンクにこの迂回路探索
メツセージを中継して送信する。

自ノードが迂回路の終点の候補になっている場合には、
迂回路探索メツセージと逆の経路で、そのメツセージの
発信元（始点ノード）に迂回路設定メツセージを送り返
す。迂回路探索メツセージが通った経路はそれを中継し
たノードに記憶されている。

（５）この迂回路設定メツセージを受信した始点ノード
は、各グループについてそれぞれ最先に到達した迂回路
設定メツセージの経路を迂回路と決定し、この経路に沿
ったノードのマトリックススイッチ２０（第３図）を順
次切り換えるためのメツセージを発信して迂回路を設定
する。

前述のグループ１の場合は、迂回パスの終点となるノー
ドの候補は、ノードＣとノードＢであるが、ノードＣは
障害状態なので、迂回パス設定メツセージを送り返すこ
とはなく、ノードＢのみ迂回パス設定メツセージを送り
返すことができるので、ノードＢが迂回パスの終点とし
て決定され、迂回路７０．７１が設定される。グループ
２．３の場合も同様に、それぞれ、迂回路７２．７３が
設定される。

第５図はリンクＣＤに障害があった場合を示している。

この場合にもノードＤがこの障害を検知するが、このと
きにはノードＤはリンクＣＤの障害であるのかノードＣ
の障害であるのかを区別することができない。そこで前
述したと同じ過程で迂回路の探索が行なわれるのである
が、この場合にはノードＣもメツセージを返すことがで
きる。

したがって、例えばグループ１についてはノードＣから
の迂回路設定メツセージとノードＢからの迂回路設定メ
ツセージとが競合する。仮に、ノードＣからのメツセー
ジがノードＤへ先に到達すると、ノードＣとノードＤと
の間で迂回路７４．７５が設定される。グループ２およ
び３についてはノードＸおよびノードＹからのメツセー
ジがノードＣからよりも先に到達したとすれば、ノード
ＸおよびノードＹとノードＤとの間で、それぞれ、迂回
路７６．７７が設定される。

このように本発明によれば、迂回路の端点の決定と、そ
の端点間の迂回路の探索を同時に行なうことができる。

次に本発明の第２の実施例を説明する。第１の実施例に
おいては迂回路の始点と終点との間でメツセージが往復
して初めて迂回路が決定される。

また、各グループについて複数の終点ノードの候補から
複数のメツセージが返る可能性があり、多数のメツセー
ジが互いに輻奏する可能性が大である。そのため障害復
旧時間がそれだけ多くかかることになる。

それに対して第２の実施例においては各グループ毎に１
つの終点を定めて迂回路探索メツセージを発信し、終点
に到達した時点で迂回路を決定しろるようにする。以下
、具体的な例についてこの方法を説明する。

迂回路探索メツセージの形式は前述の■〜■と同様であ
るが■のフィールドに書かれたノードは終点とはならず
、したがって、それに対応する■■のフィールドの内容
は０となる。前述の例では、迂回路探索メツセージは次
のようになる。

■　ノードＤ ■　ノードＣ ■　ノードＢ１ノードＸ１ノードＹ ■　０，２，１．１ ■　０、パス１１パス２、パス３、パス４これを受信し
た終点ノードは直ちにマトリックススイッチ２０の切り
換えのためのメツセージを発し、以後到達した迂回路探
索メツセージは無視される。このようにして、例えば、
前述の第４図に示されるような迂回路が設定される。

■のフィールドは予備パスの使用を必要最小限に抑える
ために設けられる。すなわち、第５図に示すような障害
の場合に、リンクＣに迂回路探索メツセージが到達した
ら、メツセージが入力されたリンク以外のすべてに対し
て予備パスの有無に関係なく迂回路探索メツセージを送
出する。そして、このメツセージが他よりも早く迂回路
の終点ノードすなわちノードＢに到達したら、ノードＣ
とノードＤとの間で迂回路を設定しノードＢとノードＣ
との間では障害発生前の経路を使用する。

したがってこの場合も、例えば、第５図に表わすような
迂回路が設定される場合がある。

これまでに説明してきた方法では、各リンクに予備パス
が充分な数だけ存在するものとして説明されているが、
以下には被障害パスの数に較べて予備パスの数が充分に
多くない場合に、使用可能な予備パスを有効に利用して
迂回路を探索する方法について説明する。

障害を検知したノードから発せられる迂回路探索メツセ
ージには前述の■〜■以外に ■　復旧可能なパス数 が含まれる。始点からメツセージが発せられるときはこ
のフィールド■には被障害パスの総数と各出力リンクご
との予備パスの数とのいずれか小さい方の数が書込まれ
ている。メツセージの中継の際にはこのフィールド内の
値と各出力リンクごとの予備パスの数とを比較し、予備
パスの数の方が小さければその値で■のフィールドを更
新する。

また、メツセージの通過とともに、そのリンクにおける
予備パスの数を暫定的に■のフィールドの値だけ減じて
おく。たとえば、■のフィールドの値が更新される場合
には、そのメツセージの通過後、予備パスの数は暫定的
にゼロとなる。

迂回路探索メツセージが迂回路の終点の候補または終点
に到達したら、■のフィールドの該当個所の数と■のフ
ィールドの復旧可能なパス数とを比較する。前者が後者
より小であれば、そのノードを終点とする迂回路はすべ
て該定可能ということになる。逆に前者が後者よりも大
であれば、■の値を復旧可能な被障害パス数として迂回
路設定メツセージに含めて送出した後、さらに他の経路
で迂回路探索メツセージの到達を待つかく第１の実施例
の場合）あるいは■の値をその迂回路で復旧できた被障
害パスの数とし、さらに他の経路で迂回路探索メツセー
ジが到着するのを待つ（第２の実施例の場合）。そして
、その終点ノードについては復旧可能なパス数の総計が
被障害パス数に等しくなるかそれを超えるまで、迂回路
探索メツセージの到着を待つ処理を続行する。第１の実
施例においてはさらに、始点ノードにおいては、到着し
た迂回路設定メツセージ内の復旧可能な被障害パス数の
グループごとの総計がすべてのグループについて被障害
パス数に等しくなるかそれを超えるまで迂回路設定メツ
セージの到着を待つ処理を続行する。

このような処理は、前述したように迂回路探索メツセー
ジが運んできた復旧可能パス数をそのノードにおいて積
算しその積算値と被障害パス数とを比較するかわりに、
〔課題を解決するための手段〕の項で述べたように、被
障害パス数からメツセージが運んできた復旧可能パス数
を順次差し弓いた値を蓄積し、この値が０または負にな
るかを判定することとしても良い。

１回の探索処理ですべての被障害パスが復旧できなかっ
たら、さらにこれらの処理をすべての被障害パスが復旧
できるまで繰り返す。その際、以前の回の処理で暫定的
に使用された予備パスについては、実際に迂回路として
使用されたものを除き、使用されなかったものとして処
理を行なう。

上記の過程で迂回路探索メツセージが終点の候補または
終点に到達したとき、■のフィールドの値が■のフィー
ルドの該当個所の値よりも大であり、メツセージ内に他
のグループの情報が書き込まれていれば、迂回路探索メ
ツセージ内から自己のノードに関する情報を抜きとり、
予備パスのある出力リンクへさらに迂回路探索メツセー
ジを出力するようにすることもできる。こうすれば、迂
回路の候補または迂回路とされた経路であっても、さら
に余裕のあるものを他の迂回路の一部として利用するこ
とができ、第６図に７８で示すような迂回路の設定も可
能である。

これらの方法に従って探索して決定された迂回路が例え
ば第７図の７９．８０で示すように設定される可能性が
ある。この場合に、ノードＤとノードＺとの間のリンク
ＤＺに予備パスが２本以上あったときは問題はないが、
予備パスが１本しかなかったときは、実際には迂回路を
設定し得ないにもかかわらず、このように決定される可
能性がある。

この問題に対処するた約には、始点ノード（ノードＤ）
から迂回路探索メツセージを出力する際に、出力リンク
のボード識別子を付して発信し、終点ノードの候補また
は終点ノードにおいてこのポート識別子を蓄積し、新た
に到着したメツセージ内のポー）８ａ別子が蓄積されて
いるポート識別子のいずれかに一致する場合、たとえ前
述したように復旧可能なパス数の総計が被障害パス数に
達していなくてもこれを無視するようにすることにより
、この問題を回避することができる。

〔発明の効果〕

以上説明したように本発明によれば、障害リンりまたは
障害ノードを迂回する最適な迂回路を短時間で探索し設
定することが可能となる。

【図面の簡単な説明】

第１図は本発明が適用される通信ネットワークの一例を
表わす図、 第２図は本発明におけるパストレーサの一例を説明する
ための図、 第３図は本発明におけるノードの構成の一例を表わす図
、 第４図〜第７図は本発明のいくつかの実施例を説明する
ための図。 図において、 Ａ−Ｅ　、　　Ｘ−Ｚ　、　１６・／−ド、ＡＢ−ＤＥ
、ＣＸ、ＣＹ、ＤＺ、１８・・・リンク、１〜４・・・
パス、１４・・・パスオーバーヘッド。

Claims (1)

1. 【特許請求の範囲】 １、複数のノードと該ノードを連結する複数のリンクと
   で構成される任意の構造のネットワーク上に２つのノー
   ド間のパスを設定することにより該２つのノード間で情
   報を伝達する通信ネットワークにおいて障害が発生した
   ときに、被障害パスのそれぞれについて障害個所を迂回
   する迂回路を探索し決定することにより２つのノード間
   のパスを修復するための迂回パス探索方法であって、ｉ
   ）該設定されたパスに沿って伝達される情報のそれぞれ
   に対応してＮ個までのノード識別子をパストレーサとし
   て収めるパスオーバーヘッドの区間を設けて情報ととも
   に伝達し、ただしＮは２以上の整数であり、 ｉｉ）ノードに到達した該パストレーサを記憶し、該パ
   ストレーサ内のノード識別子がＮ個であるときは最古の
   ノード識別子を捨てて到達ノードの識別子を追加しＮ個
   未満であるときは到達ノードの識別子を追加してパスト
   レーサを更新し、更新したパストレーサを情報とともに
   送出し、 ｉｉｉ）ノードが障害を検知したとき障害を検知したノ
   ードを迂回路の始点ノードと決定し、 ｉｖ）該始点ノードが記憶しているパストレーサのうち
   被障害パスのすべてについてのパストレーサに含まれる
   情報を含む一種類の迂回路探索メッセージを、該始点ノ
   ードに接続されかつ予備パスが残っているすべてのリン
   クに対して発信し、ｖ）ノードが該迂回路探索メッセー
   ジを受信したとき、該受信ノードが迂回路の終点ノード
   の少なくとも候補に該当するか否かを該メッセージの内
   容にもとづき判定し、 ｖｉ）該判定の結果、該受信ノードが終点ノードの少な
   くとも候補に該当しないと判定されるとき、該メッセー
   ジを受けたリンク以外であり、かつ、予備パスが残って
   いるすべてのリンクに対して迂回路探索メッセージを送
   出し、 ｖｉｉ）該判定の結果、終点ノードの少なくとも候補に
   該当すると判定されたノードに到達した迂回路探索メッ
   セージの経路のうち少なくとも一部の経路を迂回路と決
   定することを特徴とする迂回パス探索方法。 ２、前記迂回路探索メッセージは前記始点ノードが記憶
   するパストレーサのうち障害パスの各々に対応して記憶
   されたノード識別子のすべてをその障害パスの迂回路の
   終点ノードの候補を表わすものとして含み、 前記判定ｖ）は、前記受信ノードが該迂回路探索メッセ
   ージ内のノード識別子のいずれかに該当するか否かを判
   定することにより該受信ノードが終点ノードの候補であ
   るか否かを判定することであり、 前記迂回路の決定ｖｉｉ）は、 該判定ｖ）において前記受信ノードが終点ノードの候補
   であると判定されたとき、該終点ノードの候補に到達し
   た迂回路探索メッセージの経路に沿って逆方向に伝達さ
   れる迂回路設定メッセージを送出し、 同一の被障害パスに対応する迂回路設定メッセージのう
   ち最先に始点ノードに到達した迂回路設定メッセージを
   発した終点ノードの候補をその被障害パスの迂回路の終
   点と、迂回路設定メッセージの経路をその障害パスの迂
   回路と決定することである請求項１記載の方法。 ３、前記迂回路探索メッセージは前記始点ノードが記憶
   するパストレーサのうち被障害パスの各々に対応して記
   憶されたパストレーサに含まれるノード識別子のうち最
   古のものをその被障害パスの迂回路の終点ノードを表わ
   すものとして含み、前記判定ｖ）は前記受信ノードが該
   迂回路探索メッセージ内のノード識別子のいずれかに該
   当するか否かを判定することにより該受信ノードが終点
   ノードであるか否かを判定することであり、前記迂回路
   の決定ｖｉｉ）は該終点ノードに最先に到達した迂回路
   探索メッセージの経路を迂回路と決定することである請
   求項１記載の方法。 ４、前記Ｎは２であり、 前記迂回路探索メッセージは前記最古のノード識別子以
   外のノード識別子を迂回路の中途ノードを表わすものと
   してさらに含み、 ノードが該迂回路探索メッセージを受信したとき、該受
   信ノードが該中途ノードを表わす識別子のいずれかに該
   当するか否かを判定し、 該判定の結果、該受信ノードが中途ノードであると判定
   されるとき該迂回路探索メッセージを受けたリンク以外
   のすべてのリンクへ該迂回路探索メッセージを送出し、 前記終点ノードに最先に到達した迂回路探索メッセージ
   の経路が該中途ノードを含むとき始点ノードと中途ノー
   ドとの間に迂回路を設定する請求項３記載の方法。 ５、前記発信ｉｖ）において、始点から発信される迂回
   路探索メッセージは、メッセージを発信するリンクの予
   備パスの数と被障害パスの総数とのいずれか小さい数を
   復旧可能パス数として含み、前記送出ｖｉ）において、
   受信した迂回路探索メッセージ内の該復旧可能パス数と
   メッセージを送出するリンクの予備パスの数とのいずれ
   か小さい数を復旧可能パス数として更新して送出し、前
   記判定ｖ）において終点ノードの候補または終点ノード
   であると判定されるとき、受信した迂回路探索メッセー
   ジ内の復旧可能パス数が該ノードを終点とする被障害パ
   スの迂回路に要する経路の数より大であり、該メッセー
   ジ内に該ノードを終点とする被障害パス以外の被障害パ
   スに関する情報が残っていれば、該メッセージを受けた
   リンク以外の予備パスが残っているすべてのリンクに対
   して、受信したメッセージ内の復旧可能パス数から必要
   経路数を差し引いた数とメッセージを送出するリンクに
   残っている予備パスの数とのいずれか小さい数を復旧可
   能パス数とし、該ノードの識別子を抜き取った迂回路探
   索メッセージをさらに送出する請求項２、３または４記
   載の方法。 ６、前記発信ｉｖ）において、始点から発信される迂回
   路探索メッセージはメッセージを発信するリンクを区別
   するためのポート識別子をさらに含み、 前記判定ｖ）において終点ノードの候補または終点ノー
   ドであると判定される条件が満たされるとき、該ノード
   で受信された迂回路探索メッセージが最初のものであり
   かつメッセージ内の復旧可能パス数が該ノードを終点と
   する迂回路の必要数より小であればそれらの差を残りパ
   ス数としてメッセージ内のポート識別子とともに該ノー
   ドに記憶し小でなければ残りパス数として０を記憶する
   とともに該ノードを終点ノードの候補または終点ノード
   と判定し、該メッセージが最初のものでなければ該ノー
   ドに記憶された残りパス数が０でなくかつメッセージ内
   のポート識別子が記憶されたポート識別子のいずれとも
   一致しないときのみ該ノードを終点ノードの候補または
   終点ノードと判定するとともにメッセージ内のポート識
   別子を該ノードに記憶し残りパス数を更新する請求項５
   記載の方法。