(57)【特許請求の範囲】
【請求項１】
複数のノードを接続して構成される通信ネットワークの各ノードに迂回経路情報を予め設定しておき、単一リンク障害または単一ノード障害が発生した場合、障害検知ノードが障害箇所情報を含む障害通知メッセージを各ノードに転送し、障害通知メッセージを受信したノードが並列に経路を切り替える通信ネットワークの迂回経路設計方法であって、
障害検出ノードから障害通知メッセージを転送する時間が最小の迂回経路を探索し、
ついで、前記探索されたメッセージを転送する時間が最小の迂回経路に対し、異なる障害に対して予備通信容量の共有が可能であり、且つ与えられた時間上限以内で経路切り替えが可能な迂回経路に更新する
ことを特徴とする迂回経路設計方法。
【請求項２】
請求項１において、
前記障害検出ノードから障害通知メッセージを転送する時間は、転送される障害通知メッセージが通信リンクを通過する際の伝送遅延時間と、転送される障害通知メッセージが各ノードにおいて入出力処理される時間との和から計算することを特徴とする迂回経路設計方法。
【請求項３】
請求項１又は２において、
ある１つのノードに関して与えられた復旧時間上限と障害通知メッセージ転送時間との差から、迂回経路への切替え時間を計算することを特徴とする迂回経路設計方法。
【請求項４】
請求項１乃至３のいずれかにおいて、
各ノードへの障害通知メッセージ転送時間と迂回経路への切替え時間の和を求め、迂回経路上の全てのノードに関する最大値から、迂回経路の復旧時間を計
算することを特徴とする迂回経路設計方法。
【請求項５】
請求項１において、
経路端ノード間で予備通信容量の共有が不可能なリンクを経由しない別の迂回経路を探索することを特徴とする迂回経路設計方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信経路障害時に障害から通信を高速に復旧させることを可能とするとともに、通信予備容量を増大させない通信ネットワークの迂回経路設計方法に関する。
【０００２】
【従来の技術】
インターネットのサービス多様化と需要拡大に伴い、基幹網を流れる通信トラフィック量は、劇的に増加し続けている。このため、基幹網では、波長分割多重(ＷＤＭ：:Wave1ength Division Mu1tip1exing)技術を基盤として、大容量化、高速化が進められている。
【０００３】
また、メッシュ型ネットワークのフレキシブルな制御や予備波長の共有による効率的な運用のために、光クロスコネクト(ＯＸＣ：Optical Cross Connect)及び、光分岐システム(ＯＡＤＭ：Optical Add-Drop Mu1tiplexer)の開発も進んでおり、新しい通信インフラの構築とサービスの導入が期待されている。
【０００４】
大容量のＷＤＭネットワークにおいて、システムが収容するサービスが多くなるに伴い、障害が発生した場合の被害も同時に大きくなっている。このため、ネットワークの信頼度を高める高度な管理システムの開発が課題となる。特に、光レイヤでリンク障害やノード障害から高速にサービスを復旧させる技術が重要となる。
【０００５】
本発明者らは、ＷＤＭネットワークにおいて高速な障害復旧を実現するプリプラン型障害復旧方式の検討を進めている（文献：藤井泰希、宮崎啓二、伊勢田衡平、「プリプラン型障害復旧方式の検討」信学技報TM2000-60、 pp.67-72、 Nov2000参照）。
【０００６】
かかるプリプラン型障害復旧方式では、予め迂回経路情報が設定されたノードに対して、順次障害を検知したノードから隣接ノードに障害情報を通知していく（フラッディングという）ことにより、各ノードは設定されている迂回経路情報に従い経路を並列に切り替える。これにより迂回経路を動的に探索する時間を短縮でき、高速なサービス復旧が期待できる。
【０００７】
しかし、並列な経路切り替えが可能だとしても、切り替える迂回経路上のノードが障害通知を受信するまでの時間が長ければ、高速なサービス復旧は実現できないという問題が残されている。
【０００８】
また、従来の迂回経路設計方法では、予め設計する迂回経路に関しては、総予備波長数(リソース)最小化の目的しか与えられていない。
【０００９】
【発明が解決しようとする課題】
したがって、本発明の目的は、プリプラン型障害復旧方式における迂回経路設計時に、各ノードヘの障害通知メッセージ転送時間の制約を設けることにより、フラッディング時間を短縮し、高速なサービス復旧を可能とし、且つ予備波長数容量を最小とする通信ネットワークの迂回経路設計方法を提供することにある。
【００１０】
【課題を解決するための手段】
上記の課題を解決する本発明に従う通信ネットワークの迂回経路設計方法は、複数のノードを接続して構成される通信ネットワークの各ノードに迂回経路情報を予め設定しておき、単一リンク障害または単一ノード障害が発生した場合、障害検知ノードが障害箇所情報を含む障害通知メッセージを各ノードに転送し、障害通知メッセージを受信したノードが並列に経路を切り替える通信ネットワークの迂回経路設計方法であって、障害検出ノードから障害通知メッセージを転送する時間が最小の迂回経路を探索し、ついで、前記探索されたメッセージを転送する時間が最小の迂回経路に対し、異なる障害に対して予備通信容量の共有が可能であり、且つ与えられた時間上限以内で経路切り替えが可能な迂回経路に更新することを特徴とする。
【００１１】
また、上記の課題を解決する本発明に従う通信ネットワークの迂回経路設計方法の実施の形態として、前記障害検出ノードから障害通知メッセージを転送する時間は、転送される障害通知メッセージが通信リンクを通過する際の伝送遅延時間と、転送される障害通知メッセージが各ノードにおいて入出力処理される時間との和から計算することを特徴とする。
【００１２】
さらに、上記の課題を解決する本発明に従う通信ネットワークの迂回経路設計方法の実施の形態として、ある１つのノードに関して与えられた復旧時間上限と障害通知メッセージ転送時間との差から、迂回経路への切替え時間を計算することを特徴とする。
【００１３】
さらにまた、上記の課題を解決する本発明に従う通信ネットワークの迂回経路設計方法の実施の形態として、各ノードへの障害通知メッセージ転送時間と迂回経路への切替え時間の和を求め、迂回経路上の全てのノードに関する最大値から、迂回経路の復旧時間を計算することを特徴とする。
【００１４】
さらに、上記の課題を解決する本発明に従う通信ネットワークの迂回経路設計方法の実施の形態として、経路端ノード間で予備通信容量の共有が不可能なリンクを経由しない別の迂回経路を探索することを特徴とする。
【００１５】
また、上記の課題を解決する本発明に従う通信ネットワークの迂回経路設計方法の実施の形態として、経路端ノード間で、共有可能な予備通信容量が大きなリンクを優先し、別の迂回経路を探索することを特徴とする。
【００１６】
さらにまた、上記の課題を解決する本発明に従う通信ネットワークの迂回経路設計方法の実施の形態として、前記共有可能な予備通信容量が大きなリンクを優先し、別の迂回経路を探索する時、一時的に現用経路上のリンクへ、他の全てのリンクの共有可能な予備通信容量を越える値を設定し、障害検知ノードから迂回経路上のノードへの障害通知メッセージ転送時間を短く抑えることを特徴とする。
【００１７】
さらに、上記の課題を解決する本発明に従う通信ネットワークの迂回経路設計方法の実施の形態として、迂回経路を更新する際、障害通知メッセージ転送時間が所定の復旧時間上限を越えるノードを経由しない別の迂回経路を探索することにより、経路探索時間を短縮することを特徴とする。
【００１８】
また、上記の課題を解決する本発明に従う通信ネットワークの迂回経路設計方法の実施の形態として、対象とする通信ネットワークのトポロジーまたは規模、ノードの装置仕様、通信方式に応じて、前記障害検出ノードから障害通知メッセージを転送する時間の計算、迂回経路への切替え時間を計算あるいは、迂回経路の復旧時間を計算を選択可能とすることを特徴とする。
【００１９】
本発明の更なる特徴は以下の図面を参照して説明される発明の実施の形態から明らかになる。
【００２０】
【発明の実施の形態】
以下に本発明の実施例を説明する前に理解を容易にするべく、本発明の対象とする光ネットワークにおけるプリプラン型障害復旧方式ついて説明する。
【００２１】
図１は、端局間で光信号を送受信する光パスを基本とするネットワーク例を示す図である。特に、ＷＤＭ技術を用いて、光ファイバ内に複数の光信号を多重化し、中継に光クロスコネクト(ＯＸＣ)を用い、端局間で光信号を送受信する光パスを基本とするネットワークである。
【００２２】
図１において、光クロスコネクト（ＯＸＣ）１、２間をノード１７、１０、１２、１４の現用通信経路で通信が行われていると想定する。ここで、例えばノード１０、１２間で、障害１１が発生すると、ノード１２がこの障害発生を検知する。
【００２３】
そして、障害を検知したノード１２が障害箇所情報を含む障害通知メッセージ１３を隣接ノード１４に転送し、隣接ノード１４は更に隣接ノード１５に通知するというように、順次隣接ノードに通知する。
【００２４】
迂回経路中継ノード１５、１６と、経路切り替えノード１４、１７は、障害通知メッセージを初めて受信した場合のみ、受信したノードを除く全ての隣接ノードに対して障害通知メッセージを転送する。
【００２５】
ついで、予め与えた迂回経路情報に従い、並列に通信経路を切り替える。このとき、かかるプリプラン型障害復旧方式では、障害通知メッセージ数の削減と並列な経路切り替えにより、障害からの復旧時間の高速化を図っていた。
【００２６】
かかる従来のプリプラン型復旧方式では、あらかじめノードに設定している迂回経路に制約が存在していない。そして、切り替えるべき迂回通信経路上の全てのノードが障害通知メッセージを受け取らなければ、並列に経路を切り替えたとしても通信経路は復旧できない。
【００２７】
このため、設定した迂回通信経路上の迂回経路中継ノード又は経路切り替えノードが、障害検知ノードから距離が離れていて、障害通知メッセージを受信するまでに時間がかかってしまうと、通信経路の復旧が遅れる大きな原因となる。
【００２８】
たとえば、迂回通信経路と障害通知メッセージ転送時間を示す図２において、図２Ａは現用通信経路上の障害２１に対する迂回通信経路２２であり、図２Ｂは、同様に、現用通信経路上の障害２１に対する迂回経路２３である。
【００２９】
障害２１に関する情報は、障害検知ノード２４から障害通知メッセージ２５により伝えられる。両者を比較すると、図２Ｂの迂回経路２３は、障害通知メッセージ転送時間が短いために、障害からの復旧時間が早くなる。
【００３０】
一方、従来型の通信ネットワーク設計の目的である総予備通信容量の最小化、総リンク距離の最小化、総経路ホップ数の最小化なども重要であるが、障害通知メッセージ転送時間とのバランスを考慮する必要がある。
【００３１】
たとえば、迂回通信経路と予備通信容量を示す図３を参照すると、図３Ａでは、現用通信経路上の障害３１、３２、３３、３４を回避するのは迂回経路３５であるが、図３Ｂでは、現用通信経路上の同様の障害を回避するためには、障害３１に対して迂回通信経路３６、障害３２に対して迂回通信経路３７、障害３３に対して迂回通信経路３８、障害３４に対しては迂回通信経路３９をそれぞれ設定する必要がある。このとき、図３Ｂでは、図３Ａの場合よりも障害通知時間が短いが、より多くの予備通信容量を必要とする。
【００３２】
したがって、本発明は、従来型の通信ネットワークの迂回経路設計方法において、上記の考察における障害復旧までの時間と、予備通信容量を考慮した処理を提案するものである。
【００３３】
図４は、本発明の通信ネットワークの迂回経路設計方法を適用する光ネットワークの障害管理を説明する図である。光コアネットワークＮＷは、複数の光クロスコネクト１〜５を有し、これらが、光パスで接続されている。
【００３４】
ＩＰルータ等７，８を通して他のネットワークと接続される。さらに、共通のネットワーク管理装置（ＮＭＳ）１０を有し、各ノードの迂回経路テーブル１１４に迂回経路情報を設定する。
【００３５】
また、ネットワーク管理装置（ＮＭＳ）１０は、迂回経路設計のために、各ノードからトポロジー、ノード処理遅量及び、リンク伝送遅延量情報を吸収する。
【００３６】
図５は、ノードの構成例ブロック図であり、図４のノード１〜５の各々に共通である。入力インタフェース部（入力ＩＦ）１０３、スイッチ部１００、スイッチ制御テーブル１０１，出力インタフェース部（出力ＩＦ）１０４及び、メッセージ制御部１０２を含んで構成される。
【００３７】
入力インタフェース部１０３は、１又は複数個備わっており、対応するノードに接続されたリンクを構成する１あるいは複数の伝送媒体（例えば光ファイバ）を終端し、この終端したリンクに含まれる各通信パスを通して入力される各種のデータを受信する。
【００３８】
スイッチ部１００は、入力インタフェース部１０３側のポートと、出力インタフェース側のポートとの間の接続状態を切り替える。例えば、複数の入力インタフェース部１０３のポートと、複数の出力インタフェース部１０４のポートのそれぞれには、ノード内で重複しないチャネル番号が割り当てられている。
【００３９】
入力インタフェース部１０３側のポートのチャネル番号と出力インタフェース部１０４側のポートのチャネル番号との組合わせをスイッチ制御テーブル１０１に格納しておく。これによりスイッチ部１００において、この組合せに応じた通信パスのルーティング処理が行われる。
【００４０】
したがって、リンクや通信パスに障害が発生して迂回パスを設定する場合には、スイッチ制御テーブル１０１の内容を変更して、スイッチ部１００における通信パスの設定状態を切り替えればよい。
【００４１】
出力インタフェース部１０４は、入力インタフェース部１０３と同様に複数個備わっており、該当のノードに接続されたリンクを構成する１あるいは複数本の伝送媒体を終端し、この終端したリンクに含まれる各通信パスに各種のデータを出力する。
【００４２】
メッセージ制御部１０２は、リンクや通信パスが発生した時、リンク単位の障害箇所情報を含む障害復旧メッセージを作成する。作成された障害復旧メッセージは、他のノードにフラッディングにより通知する。
【００４３】
また、メッセージ制御部１０２は、隣接する他のノードからメッセージを受け取った時に、ネットワーク管理装置１０により予め迂回経路テーブル１１４に設定されている迂回経路情報に基づき、必要に応じて迂回パスへ切り替える処理を行う。
【００４４】
図６は、メッセージ制御部１０２の詳細構成を示す図である。図６に示すように、メッセージ制御部１０２は、メッセージ受信部１１０，受信メッセージテーブル１１１，メッセージ処理部１１２，迂回経路テーブル１１４、経路切替処理部１１５及び、メッセージ送信部１１３を有する。
【００４５】
メッセージ受信部１１０は、隣接するノードから送られてくるメッセージを受信する。このメッセージには障害が発生したリンクを特定する障害箇所情報が含まれている。受信メッセージテーブル１１１は、メッセージ受信部１１０によって受信したメッセージを格納する。同じメッセージが異なるノードからそれぞれ送られた場合は、最初に受信したメッセージのみが格納される。
【００４６】
メッセージ処理部１１２は受信メッセージテーブル１１１に格納された受信済みのメッセージを探索することにより、メッセージ受信部１１０によって新たに受信したメッセージがそれまでに受信済みのメッセージと重複しないか否かの確認を行う。
【００４７】
新規なメッセージに対してはメッセージ処理部１１２は、メッセージを送信する指示をメッセージ送信部１１３に送る。これとともに、スイッチ部１００による通信パスの接続状態を切り替える指示を経路切替処理部１１５に送る。
【００４８】
経路切替処理部１１５は、受信メッセージに含まれている障害箇所情報に基づき、該当ノードが、迂回パスに含まれているか否かを判定する。含まれている場合は、スイッチ制御テーブル１０１の内容を書き換えることにより迂回パスの設定を行う。
【００４９】
ここで、スイッチ制御テーブル１０１の内容の書き換えは、ネットワーク管理装置１０により予め迂回経路テーブル１１４に設定されている障害箇所に対応する迂回パスの設定情報に基づく。
【００５０】
設定情報は、例えば、リンクＬＸで障害が発生した時に設定される迂回パスに該当のノードが含まれている場合は、リンクＬＸに対応して迂回パスを設定するに必要なスイッチ部１００の入力ポートのチャネル番号と、出力ポートのチャネル番号との組合わせである。
【００５１】
メッセージ送信部１１３は、メッセージ処理部１１２から入力されるメッセージをこのメッセージを受信した隣接ノードを除く他の隣接ノードに送信する。
【００５２】
図７は、本発明の通信ネットワークの迂回経路設計方法の実施例動作フローであって、図４のネットワーク管理装置１０内で実行される。
【００５３】
図７において、通信ネットワークの迂回経路設計処理が開始されると、ネットワーク管理装置１０は、各ノードから次の情報を吸い上げる（処理工程Ｐ１）。
【００５４】
・ネットワークトポロジー
・各通信リンクの距離
・現用通信経路の分布（現用されている通信の経路状態である）
・各現用通信経路の通信容量
次に、ユーザーによって、障害復旧時間の上限値が入力される（処理工程Ｐ２）。
【００５５】
これらの情報を基にネットワーク管理装置１０は、先ず更新対象とするリンクを決める（処理工程Ｐ３）。この時、更新対象とする決める基準として、予備波長数最大のリンクＬＭを選ぶ。
【００５６】
予備波長数は、図８に示すように、障害が起きた際に現用波長に対し予備波長が通信に利用されるが、この時最悪の障害の場合を想定して用意される容量が予備波長数となる。
【００５７】
したがって、予め設定されている予備波長を有するリンクのうち予備波長数最大のリンクＬＭを更新対象とする。
【００５８】
ここで、各リンクには、上記のように全ての障害に対して被害が最も大きい場合を想定して予備波長が設定されている。しかし、設定する予備波長数はリンクによって様々である。
【００５９】
１つだけ更新対象とするリンクを決める時、いずれのリンクを選ぶことも可能であるが、ネットワーク全体でリンクの予備波長数が均等になる方が良いと考えられる。このために１実施例として、波長数最大のリンクを更新対象としている。
【００６０】
ネットワーク管理装置１０は、処理工程Ｐ３において、更に選ばれた予備波長数最大のリンクＬＭの予備波長数の要因となる障害Ｆを特定する。図８の例では、障害Ｆ１が予備波長数最大のリンクＬＭの予備波長数要因である。
【００６１】
ついで、予備波長数要因として特定された障害Ｆに対する迂回経路リストplistを作成する。
【００６２】
ネットワーク管理装置１０は、作成したplistから１つの迂回経路path1（始まりノードsrcと終わりノードdestで特定される。）を取り出す（処理工程Ｐ４）。
【００６３】
ついで、障害ノードから各ノードまでの障害通知時間を計算する。ここで、障害時に障害検出ノードから送信される通知メッセージが各ノードに到達するまでの時間を算出するためにリンクおよびノードにおける障害通知メッセージの通過時間をモデル化する。
【００６４】
図９は、そのモデル化の一例である。障害通知メッセージが転送される際、リンク（link）の障害通知メッセージ伝送時間delay(link)▲１▼とノード（node）の障害通知メッセージ処理時間mproc(node)▲２▼を考慮する。
【００６５】
そして、障害通知メッセージ伝送時間delay(link)▲１▼はリンク距離dist(link)に比例し、その比例定数は、光通信の物理的な伝送遅延時間（sec/km）と、通信速度（bit/sec）により決まる下記式で表される値( とする。
【００６６】
delay(link) = ( * dist(link)
定数( の具体的な値は、例えば、通信速度を155.52e6（bit/sec）とした時、光の物理的な伝送遅延時間4.833e-6（sec/km）とから，約5.0e-6となる。
【００６７】
一方、障害通知メッセージ処理時間mproc(node)▲２▼に含まれるノードのメッセージ受信／送信処理に関しては、１メッセージ当りの処理時間を考慮するが、障害時にフラッディングされるメッセージが任意の順序で処理されることから，設計段階では最悪時間で取り扱う。
【００６８】
すなわち、障害通知メッセージは任意の順で、１つずつ逐次的に処理されるために、設計の段階では何番目に処理されるかは不明である。そこで、ノードを通過する際の時間は、どんな場合でもメッセージが一番最後に処理されると仮定して、これを上記の最悪時間としている。
【００６９】
すなわち、メッセージ受信リンクと送信リンクの総数は，ノード（node）に接続するリンク数deg(node)となるため，障害通知メッセージ処理時間mproc(node)▲２▼はリンク数deg(node)に比例する下記式で表される。
【００７０】
mproc(node) = ( * deg(node)
定数( の具体的な値は、本発明者のシミュレーション結果では１メッセージ当り1.0e-3（sec）程度である。上記の式から得られる
上記の算式の障害通知メッセージ伝送時間delay(link)▲１▼と、障害通知メッセージ処理時間mproc(node)▲２▼の値から得られる各ノードまでの障害通知時間が求められる。
【００７１】
求められた障害通知時間の内、現用経路上を除き、先にユーザー要求として入力された復旧時間上限を越えるノードを削除する。
【００７２】
さらに、先に、前記の特定した迂回経路path1と予備波長が共有不可能なリンクを削除する。ここで、予備波長の共有について説明する。
【００７３】
例えば、図８において、ある障害Ｆに対するリンクｌを経由しない迂回経路pｌをリンクｌを経由する別の迂回経路に更新する際、リンクｌに設定された予備波長が共有可能かどうか判定する。
【００７４】
まず、リンクｌに設定されている予備波長数の要因となる障害をＦ１とする時、もし障害Ｆが障害Ｆ１ならば、リンクp1はリンクlの予備波長を共有不可能であり、障害Ｆが障害Ｆ２や障害Ｆ３ならば、リンクp1はリンクlの予備波長を共有可能と考える。
【００７５】
ついで、障害検知ノードを始点とする最短経路アルゴリズム（Dijkstra法など）を実行する。これにより、障害検出ノードから各ノードまでの最短経路path2が求まる。
【００７６】
ここで、上記処理工程Ｐ４において、障害通知時間が上限を越えるノードの削除及び、波長の共有が不可能なリンクの削除を行っているので、処理工程Ｐ１で得られたトポロジー情報に戻す再生処理を行っておく。
【００７７】
ついで、plistから取り出されたpath1を求められた最短経路path2が求められる場合（処理工程Ｐ５，Ｙｅｓ）、求められたpath2に更新する（処理工程Ｐ６）。
【００７８】
上記の処理を plistから取り出された全ての迂回経路について実行する（処理工程Ｐ７）。処理結果が最適解である場合（処理工程Ｐ８，Ｙｅｓ）、処理を終了する。
【００７９】
上記の様に、本発明は、処理工程Ｐ４において、復旧時間上限を越えるノードの削除と、予備波長の共有が不可能なリンクを排除している。これにより、サービス復旧時間の短縮と予備波長の最小化を図っている。
【００８０】
なお、上記処理工程Ｐ４において、全ての迂回通信経路に対して１回だけ更新処理を行うが、さらに繰り返して処理を行うことにより総予備通信容量を更に最小化することが可能である。
【００８１】
すなわち、図８において、ネットワークリソースの効率化を図るため、割り当てる予備波長数を最小化する際、迂回経路の更新を繰返す。この時、予備波長の共有が可能なリンクから構成される迂回経路を更新対象とすることにより、総予備波長数を単調減少させることができる。
【００８２】
図１０は、実施例としてのデータ構造図であり、図７の処理工程Ｐ４における処理通知時間が上限を越えるノードの削除の際の判定処理のために、図１１に示すネットワークトポロジー６６のノードＮ８が所持する障害からの復旧時間を示すテーブルである。
【００８３】
図１０において、障害箇所６１、この障害を検知可能なノード６２、入力された復旧時間の上限値６３、通信リンクの図９で説明したメッセージ伝送遅延とノードのメッセージ処理時間から算出される最短の障害通知メッセージの受信時間６４及び、入力された復旧時間の上限値６３と最短の障害通知メッセージの受信時間６４との差から求まる経路切り替え（スイッチング）に費やせる時間６５が示されている。
【００８４】
先の説明では、各光クロスコネクトにおけるスイッチ部１００における１つの通信経路を切り替える時間は固定値として考えている。したがって、通信経路切替時間６５からノードＮ８を経由できる通信経路数が算出可能である。たとえば、迂回通信経路更新の際に、ノードＮ８が復旧時間上限検証の対象ノードとなるならば、通信経路切替時間６５を参照して判定できる。
【００８５】
図１２は、予備通信波長容量を小さくする処理の実施例を示す図である。図１２では、ノード１〜Ｎ９を有するネットワークにおいて、障害８１によって被害を受ける現用経路８２の迂回経路８３、既に設定されている障害８４に対する迂回経路８５と障害８６に対する迂回経路８７を示し（図１２Ａ）、図１２Ｂは、迂回経路８３を迂回経路８８に更新した図を示している。
【００８６】
通信ネットワーク設計目的の一つである予備通信容量の最小化のために、迂回経路８３から迂回経路８８へ更新し、予備通信容量を共通化させる。このとき、ノードＮ８とノードＮ９が新たに迂回経路に加わる。このため、たとえば、図１１の復旧時間検証テーブルを利用して現用経路８２上の障害８１を検知するノードＮ６からの障害通知メッセージ転送時間と迂回経路切替時間から迂回通信経路８８の復旧時間条件を検証する。
【００８７】
上記の様に、迂回通信経路のノードに関する障害通知メッセージ転送時間と経路切替時間の計算により、要求する障害復旧時間上限を越えない条件の下で、通信ネットワークの迂回経路設計の目的を果たすことができる。
【００８８】
図１３は、図１２に示す如くして更新された結果の迂回通信経路情報を示す情報テーブルの例である。図１３において、例えば、図１２を参照しながら説明すると、ノードＮ１とＮ４を結ぶリンクＬ１における障害によって被害を受ける発信ノード７２と受信ノード７３が示される。さらに、被害を受ける発信ノード７２と受信ノード７３の組合せに対応して迂回通信経路７４が示されている。
【００８９】
一例として、被害を受ける発信ノード７２がＮ４であり、被害を受ける受信ノード７３がＮ１である時（データは、ノードＮ４からＮ１に向けて流れる経路である）、障害８４に対して、Path141とPath412が設定されている。
【００９０】
この図１３に示す迂回通信経路情報テーブルに基づき、ネットワーク管理装置１０により、先に図５、図６で説明した対応する光クロスコネクトのメッセージ制御部１０２の迂回経路テーブル１１４に、障害に対応した経路切替情報が設定される。
【００９１】
図１４は、別の実施例として、始ノードｓから終ノードｔへの現用パスに関して、予備通信容量の共有が可能な迂回パスの探索を示したものである。各リンクの数字は、共有可能な予備通信容量を表す。
【００９２】
例えば、‘０’は他の障害に関する迂回パスと予備通信容量の共有不可能であることを示す。この数値が大きいリンクを優先的に選び、始ノードｓから終ノードｔまでの迂回パスを計算する。
【００９３】
プリプラン型障害復旧方式で求める迂回パスは、予備通信容量の共有ができ、かつ、障害検知ノードからのメッセージ転送時間が短いものが望ましい。即ち、図１４中で、なるべく数字の大きいリンクを通り、かつ、障害検知ノードｕから近い迂回パスを選ぶ必要がある。
【００９４】
しかし、現用パス上に予備通信容量は確保しないため、現用パス上のリンクの共有可能な予備通信容量は全て０となる。このため、図１４Ａの迂回パスＳＲのように障害検知ノードから遠くなってしまう可能性がある。
【００９５】
そこで、図１４Ｂに示すように迂回パスを探索する時だけ、一時的に、現用パス上のリンクに大きな予備通信容量例えば、予備通信容量（１００）を与える。この状態で、始ノードｓから終ノードｔへの迂回パスを探索すれば、予備通信容量の数値が大きいリンクを優先的に選ぶため、現用パスと重なるリンクが多くなり、迂回区間（迂回パス実線部）は短くなる。結果として、予備通信容量を共有しつつ、障害検知ノードｕからの障害通知時間を短縮することができる。
【００９６】
但し、予備通信容量０のリンクは経由しない迂回パスを探索している。また、迂回パスを決定した後は、現用パス上のリンクに割当てた予備通信容量（１００）を削除する。
【００９７】
ここで、本発明では、障害通知メッセージの転送時間を、光の通信遅延時間、ノードの経路切替時間、ノードの入出力メッセージ処理時間などから計算する。各時間パラメータは、対象とするネットワークの規模や、ノードを構成する装置能力に強く依存する。
【００９８】
また、方式などの違いにより、その数値差は小さくても１桁、大きくて６桁も変わってくる。このため、常に全てのパラメータを取り入れて計算する必要は無く、対象通信ネットワークの種別に応じて、妥当な範囲内で、いくつかのパラメータを無視した設計が可能となる。この結果、設計に要する計算時間を大幅に削減できる。
【００９９】
図１５に示す表は、迂回経路設計の対象とする通信ネットワークの項目と、具体的なパラメータの事例である。光の通信遅延に関しては、単位距離あたりの遅延時間は、4．833μsec/kmと固定されている。
【０１００】
また、図１６に示す表では、特にネットワーク規模とノードの切替方式に注目して関係を示している。
【０１０１】
もし、ネットワーク規模が都市部程度のパス長３０kmだとすると、メッセージ伝送時間は１４５μsec程度かかるが、光信号をそのまま切替えるならば５msec程度必要であるため、メッセージ伝送時間（通信遅延）は無視できる。
【０１０２】
一方、ネットワーク規模が北米でパス長３０００kmだとすると、通信遅延は14.5msecかかるが、電気信号を切替えるにはその３００万分の1の時間で可能となるため、切替時間は十分無視できる。
ノードにおけるメッセージの処理時間も、ノードに実装されるＣＰＵの処理能力によって小さくなる。
【０１０３】
さらに、本発明者は、上記に説明した本発明に従う通信ネットワークの迂回経路設計方法を評価するために、一般的な設計評価で使用される５×５格子型(２５ノード)のネットワークトポロジーでシミュレーションを行った。
【０１０４】
各パラメータに関して、リンク長は５００km以下のランダム値(平均347．2km)、ノードのメッセージ処理時間１．０msec、リンク伝送遅延５．０μsec／km、６０００現用光パスとした。
【０１０５】
まず、図１７に与えられる障害通知時間の上限が、予備率へどのような影響を及ぼすかを示す。ここで予備率とは、現用波長数に対する予備波長数の比率であり、この値が低いほど設計効率が良いことを示す。
【０１０６】
与える時間上限が大きくなり、条件が緩くなると共に予備率は低下し、３０msec程度で予備率は収束する。従来型のＳＯＮＥＴ／ＳＤＨにおける１＋１やリングプロテクション方式では、１００％の予備率が必要であった。
【０１０７】
しかし、本発明の方法により、サービス復旧時間の目標である５０msecに対して、半分の２５msec経路切替の時間に充てたとしても、ノード障害に対して４７．２％、リンク障害に対して４１．３％と、予備率を５０％以下に抑えることができる。
【０１０８】
次に、同様の環境で時間制約"有り"と"無し"で設計した場合の予備率と障害通知時間を図１８に示す。時間制約が"無し"の場合は、パス端で迂回する経路が設定され、最大３７msec程度の時間が要求される。一方、時間制約(２５msec) "有りの場合は、多くの障害に対して予備波長の十分な共有が可能であり、"無し”の場合と比べても予備率の増加は３.５％未満と大きな差は現れなかった。
【０１０９】
（付記１）
複数のノードを接続して構成される通信ネットワークの各ノードに迂回経路情報を予め設定しておき、単一リンク障害または単一ノード障害が発生した場合、障害検知ノードが障害箇所情報を含む障害通知メッセージを各ノードに転送し、障害通知メッセージを受信したノードが並列に経路を切り替える通信ネットワークの迂回経路設計方法であって、
障害検出ノードから障害通知メッセージを転送する時間が最小の迂回経路を探索し、
ついで、前記探索されたメッセージを転送する時間が最小の迂回経路に対し、異なる障害に対して予備通信容量の共有が可能であり、且つ与えられた時間上限以内で経路切り替えが可能な迂回経路に更新する
ことを特徴とする迂回経路設計方法。
【０１１０】
（付記２）付記１において、
前記障害検出ノードから障害通知メッセージを転送する時間は、転送される障害通知メッセージが通信リンクを通過する際の伝送遅延時間と、転送される障害通知メッセージが各ノードにおいて入出力処理される時間との和から計算することを特徴とする迂回経路設計方法。
【０１１１】
（付記３）付記１又は２において、
ある１つのノードに関して与えられた復旧時間上限と障害通知メッセージ転送時間との差から、迂回経路への切替え時間を計算することを特徴とする迂回経路設計方法。
【０１１２】
（付記４）付記１において、
各ノードへの障害通知メッセージ転送時間と迂回経路への切替え時間の和を求め、迂回経路上の全てのノードに関する最大値から、迂回経路の復旧時間を計
算することを特徴とする迂回経路設計方法。
【０１１３】
（付記５）付記１において、
経路端ノード間で予備通信容量の共有が不可能なリンクを経由しない別の迂回経路を探索することにより、総予備通信容量を削減し、経路探索時間を短縮することを特徴とする迂回経路設計方法。
【０１１４】
（付記６）付記１において、
経路端ノード間で、共有可能な予備通信容量が大きなリンクを優先し、別の迂回経路を探索することにより、総予備通信容量を削減し、「ｋじぇいろ探索時間を短縮することを特徴とする迂回経路設計方法。
【０１１５】
（付記７）付記６において、
前記共有可能な予備通信容量が大きなリンクを優先し、別の迂回経路を探索する時、一時的に現用経路上のリンクへ、他の全てのリンクの共有可能な予備通信容量を越える値を設定し、障害検知ノードから迂回経路上のノードへの障害通知メッセージ転送時間を短く抑えることを迂回経路設計方法。
【０１１６】
（付記８）付記１において、
迂回経路を更新する際、障害通知メッセージ転送時間が所定の復旧時間上限を越えるノードを経由しない別の迂回経路を探索することにより、経路探索時間を短縮することを特徴とする迂回経路設計方法。
【０１１７】
（付記９）
対象とする通信ネットワークのトポロジーまたは規模、ノードの装置仕様、通信方式に応じて、付記２に記載の前記障害検出ノードから障害通知メッセージを転送する時間の計算、付記３に記載の迂回経路への切替え時間を計算あるいは、付記４に記載の迂回経路の復旧時間を計算を選択可能とすることを特徴とする迂回経路設計方法。
【０１１８】
【発明の効果】
以上図面に従い説明したように、本発明の迂回経路設計方法により、通信ネットワークにおいて、単一通信リンク障害又はノード障害発生時に、予め各ノードに設定された迂回通信経路情報に従って切り替える障害復旧システムにおいて、復旧処理の高速化と総予備通信容量の最小化ができる。これにより、通信ネットワーク資源の効率化が得られる。
【図面の簡単な説明】
【図１】端局間で光信号を送受信する光パスを基本とするネットワーク例を示す図である。
【図２】迂回通信経路と障害通知メッセージ転送時間を示す図である。
【図３】迂回通信経路と予備通信容量を示す図である。
【図４】本発明の通信ネットワーク設計方法を適用する光ネットワークの障害管理を説明する図である。
【図５】ノードの構成例ブロック図である。
【図６】メッセージ制御部１０２の詳細構成を示す図である。
【図７】本発明の通信ネットワークの迂回経路設計方法の実施例動作フローである。
【図８】予備波長数説明する図である。
【図９】障害ノードから各ノードまでの障害通知時間を計算するモデルを示す図である。
【図１０】実施例としてのデータ構造図であり、障害からの復旧時間を示すテーブルである。
【図１１】ネットワークトポロジー示す図である。
【図１２】予備通信波長容量を小さくする処理の実施例を示す図である。
【図１３】図１２に示す如くして更新された結果の迂回通信経路情報を示す情報テーブルの例である。
【図１４】別の実施例として、始ノードｓから終ノードｔへの現用パスに関して、予備通信容量の共有が可能な迂回パスの探索を示す図である。
【図１５】迂回経路設計の対象とする通信ネットワークの項目と、具体的なパラメータの事例である。
【図１６】ネットワーク規模とノードの切替方式に注目して関係を示す図である。
【図１７】与えられる障害通知時間の上限が、予備率へどのような影響を及ぼすかを示す図である。
【図１８】時間制約"有り"と"無し"で設計した場合の予備率と障害通知時間を示す図である。
【符号の説明】
１〜５  光クロスコネクト
７，８ルータ
１１４  迂回経路テーブル
１１  障害
１３  障害メッセージ
１０、１２、１４−１７  ノード
【図１】
0004149680.tif 000002
【図２】
0004149680.tif 000003
【図３】
0004149680.tif 000004
【図４】
0004149680.tif 000005
【図５】
0004149680.tif 000006
【図６】
0004149680.tif 000007
【図７】
0004149680.tif 000008
【図８】
0004149680.tif 000009
【図９】
0004149680.tif 000010
【図１０】
0004149680.tif 000011
【図１１】
0004149680.tif 000012
【図１２】
0004149680.tif 000013
【図１３】
0004149680.tif 000014
【図１４】
0004149680.tif 000015
【図１５】
0004149680.tif 000016
【図１６】
0004149680.tif 000017
【図１７】
0004149680.tif 000018
【図１８】
0004149680.tif 000019