JP2002335276A - パスルーティング方法及びデータ処理システム - Google Patents

Abstract

(57)【要約】 【課題】 本発明は、ＷＤＭネットワークにおける故障
保護パスの選択方法を提供する。 【解決手段】 本発明の方法は、保護パス内のリンクを
共用する複数のリンクに関して不同時的な故障イベント
によって与えられる波長確保量共用能力を利用する。バ
ケットと呼ばれるリンクメトリック情報が、ネットワー
ク内の各リンクに関して保護パスに対する波長確保量を
追跡するため使用される。バケットは、波長消費量が最
低限に抑えられた保護パスを生成するため使用される。
この方法は、個々のネットワーク接続装置上で分散型で
利用されるか、又は、保護パスを割り付けるため集中ネ
ットワーク管理システムによって使用される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、光通信システムの
分野に係り、特に、波長分割多重化方式（ＷＤＭ）ネッ
トワークによる保護パスの決定方法に関する。

【０００２】

【従来の技術】インターネットの普及によって、データ
トラフィックの氾濫が生じている。データトラフィック
は、サービスプロバイダに爆発的な帯域要求を満たす新
しいインフラストラクチャの検討を余儀なくさせてい
る。単一のファイバによって多数の信号を搬送すること
が可能な波長分割多重化方式（ＷＤＭ）は、インターネ
ット上での帯域不足を解決する有望な候補であると考え
られている。ＷＤＭによって得られる非常に大量の帯域
は、より高速なアクセスを求めて高まる気運を緩和させ
るために役立つと共に、ネットワーク管理における非常
に重要な課題を保護／修復させる。たとえば、最新テク
ノロジーによれば、最大で１２８個の波長を単一ファイ
バで多重化させることができ、各波長は最大で１０Ｇｂ
ｐｓのデータレートを達成する。このデータレートは、
概算すると、単一ファイバが数百万本の電話呼を収容す
ることに相当する。したがって、ファイバの切断が適切
な保護手段を講じることなく発生した場合には、破滅的
な結末が生じることを容易に理解することができる。

【０００３】多種類の保護方式が光ネットワークのため
に開発されている。多数の既存の伝送ネットワークは、
光同期伝送網（ＳＯＮＥＴ）リングを使用する。ＳＯＮ
ＥＴリングは、任意のノード対の間に２本の別個のパス
を含む単純なトポロジーをなし、単一のリンク若しくは
ノードの故障に対する修復力がある。リンクアーキテク
チャをＷＤＭネットワークにそのまま適用することは、
簡単かつ素早い対策であるが、多数の問題点を生じさせ
る。周知の如く、リンク構造型の保護方式は、典型的に
過度な容量冗長性に依拠している。これに対して、メッ
シュ状光ネットワークの場合、実質的により少ない限界
に近い容量で保護を行なうことが可能である。メッシュ
状光ネットワークにおける保護方式は、１９９０年代の
初頭に集中的に研究された。それにもかかわらず、メッ
シュ状ＳＯＮＥＴは、ある種の不適格性があるため、特
に、修復プロセスに時間がかかり、場合によっては２秒
以上を要することがあるので普及していない。

【０００４】伝送ネットワークにおける典型的なデジタ
ル方式クロスコネクトシステム（ＤＣＳ）は、機能が非
常に制限されている。このため、メッシュ状ネットワー
クに対しては、単純な修復アルゴリズムしか開発されて
いない。近年、ＷＤＭネットワーク上で光クロスコネク
ト（ＯＸＣ）を使用され始め、メッシュ状ネットワーク
の生き残りをかけた課題に新たな解決の糸口が与えられ
ている。インテリジェントＯＸＣは、従来のＤＣＳとは
異なり、非同期転送モード（ＡＴＭ）スイッチ、又は、
インターネットプロトコル（ＩＰ）ルーターと非常に類
似した機能がある。ＯＸＣは、光パススイッチングを用
いて動的なコンフィギュレーションを実現し、多数の管
理タスクを分散形式で実行させることが可能である。Ｉ
Ｐトラフィックが支配的であるため、均一（シームレ
ス）のデータ転送が行なえるようにＩＰ指向の制御計画
がＷＤＭベースの光ネットワークに対して検討される。
その目標は、光パスルーティング、シグナリング、及
び、修復のような統合機能を実現することである。これ
により、管理パラダイムは集中制御から分散制御へと大
きく変化する。この管理パラダイムの移行は、ＷＤＭネ
ットワーク用の保護方策の設計に重大な影響を与える。

【０００５】これにより、ネットワークの生存性／修復
性の主要な二つの問題、すなわち、時間及びリソースの
効率は、別々に対処することが可能になる。修復性は、
プランニング（計画）とアクティベーション（進行）の
二つの面で取り扱われる。リソース効率は計画段階で最
適化され、修復速度は進行段階で最適化される。計画段
階で、保護光パスは、予め計算され、故障が起こる前に
ＯＸＣに保持される。実際の故障が生じる進行段階で
は、ＯＸＣは予め定められた保護光パスに切り替る。か
くして、トラフィックは、実時間で直ちに再ルーティン
グされ得る。

【０００６】生き残り可能なメッシュ状ネットワークに
おけるリソース稼働率の最適化を行なうため提案されて
いる従来の解決策の大半は、トラフィック要求に関する
完全な情報が先験的に既知であることを前提としてい
る。したがって、これらの要求に対する保護パスは、集
中的な方式、又は、分散方式アルゴリズムを用いてバッ
チ処理で計算される。バッチ式計算は、トラフィック要
求が比較的に静的である従来型の電気通信ネットワーク
では良好に動作するが、最近、光ドメイン・サービス接
続（ＯＤＳＩ）及びインターネット・エンジニアリング
・タスク・フォース（ＩＥＴＦ）によって検討されてい
る帯域オンデマンド方式のような動的な、データ中心の
環境には不適当である。バッチ式計算の場合、トラフィ
ック要求が増加方向へ変化すると、既存のあらゆるパス
を再計算する必要があるので、望ましくない。

【０００７】パス計算を修復するための従来の方法は、
概ね、パス方式とリンク方式に分類される。パス方式の
場合、コネクションの宛先ノードによる故障イベントの
検出後、バックアップパスが活性化されたトラフィック
のソース側へ通知される。リンク方式の場合、故障イベ
ントが検出され、局所的に処理される。すなわち、迂回
路が故障したリンク／ノードの周辺で設定される。

【０００８】

【発明が解決しようとする課題】一方で、パス方式は、
リソースの効率が良いバックアップパスを生成する能力
を備えているという長所があるが、長い応答時間が課さ
れる。他方で、リンク方式は、最適な保護パスを確立す
ることはできないが、バックアップパスを設定する速度
は非常に速い。

【０００９】したがって、本発明は、リソース効率に優
れた最適な保護パスを高速に生成することができる、保
護パスを決定する方法及びかかる方法を実現するデータ
処理システムの提供を目的とする。

【００１０】

【課題を解決するための手段】本発明によれば、ノード
の集合とノード間のリンクの集合とを含むネットワーク
を通る現用パスにおけるリンクの保護パスは、保護パス
リンクの集合に関して保護されたリンクの集合に対する
波長確保量に対応したリンクメトリック情報の集合を用
いて決定される。幅の集合は、リンクメトリック情報の
集合を用いて計算され、幅の集合の中の各幅は、現用パ
スリンクを保護するため保護パスリンクの容量に対応す
る。幅の集合は、最大幅を有する保護パスリンクを用い
て保護パスを決定するため使用される。

【００１１】本発明の一局面において、データ処理シス
テムは、リンクの集合によって接続されたノードの集合
の光ネットワークにおける故障イベントリンクに対する
保護パスを決定するよう適合する。データ処理システム
は、保護パスリンクの集合に関する保護されたリンクの
集合に対する波長確保量に対応したリンクメトリック情
報の集合を受け取る。データ処理システムは、リンクメ
トリック情報の集合を用いて幅の集合を計算する。各幅
は、故障イベントリンクを保護するための保護パスリン
クの容量に対応する。データ処理システムは、幅の集合
を用いて故障イベントリンクに対する保護パスリンクを
含む保護パスを計算する。

【００１２】本発明の別の局面において、幅は、保護パ
スリンクに関する最大波長確保量と、故障イベントリン
クに対する保護パスリンクに関する波長確保量との間の
正規化された差として計算される。実現可能な保護経路
の集合が計算され、最大幅は実現可能な保護経路の集合
に対して決定される。保護パスの幅は、保護パスに含ま
れた任意の保護パスリンクの最小幅として決定される。
最大幅が０よりも大きい場合、保護経路は、実現可能な
保護経路の集合から無作為に選択される。最大幅が０に
一致する場合、保護パスは、幅が０である保護パスリン
クの数が最も少ない保護パスを決定することによって選
択される。

【００１３】

【発明の実施の形態】本発明の上記並びにその他の特
徴、局面、及び、利点は、実施例の説明、請求項に記載
された事項、及び、添付図面を参照することによってよ
りよく理解されるであろう。

【００１４】本発明は、リンクメトリック情報と、独立
した保護リンクパスの間で波長を最大限に共用する分散
型ルーティング方法の集合とにより構成される。本発明
による分散型ルーティグ方法は、要求に応じたパス計算
を支援するので、トラフィック要求に関する完全な情報
を必要とはしない。リンクメトリック情報及び分散型ル
ーティング方法は、従来のＩＰルーティングプロトコ
ル、たとえば、オープン・ショーティスト・パス・ファ
ースト（ＯＳＰＦ）の拡張として実現される。

【００１５】得られた保護パスは、波長冗長性を減少さ
せるため最適化され、一方、現用光パスは、最小ホップ
・パスを用いてルーティングされ、現用パス選択と保護
パス選択の最適化が分離される。

【００１６】図１は、ＷＤＭ光ネットワークの説明図で
ある。複数のＯＸＣがネットワーク内に接続され、複数
の波長を用いて近くのＯＸＣと通信する。ここで、別々
の通信チャネルは、ネットワーク内の各ＯＸＣによって
サポートされた別々の波長に対応する。第１の始点（ソ
ース）ＯＸＣ８０は、第１の中間ＯＸＣ８４及び第２の
中間ＯＸＣ８６を介して第１の終点ＯＸＣ８２へ動作的
に連結される。第１の始点ＯＸＣ８０は、第１の波長８
８を用いて第１の終点ＯＸＣ８２と通信する。同様に、
第２の始点ＯＸＣ９０は、第１の中間ＯＸＣ８４及び第
２の中間ＯＸＣ８６を介して第２の終点ＯＸＣ９２へ動
作的に連結される。しかし、第２の始点ＯＸＣ９０及び
第２の終点ＯＸＣ９２は、第１の始点ＯＸＣ８０及び第
１の終点ＯＸＣ８２とは異なる波長９４を使用する。

【００１７】これにより、少なくとも一つの波長９６
が、第１の中間ＯＸＣ８４と第２の中間ＯＸＣ８６の間
に未使用のままで残され、保護パス内のリンクとして確
保される。たとえば、第３の始点ＯＸＣ９７は、第３の
中間ＯＸＣ９９を介して第３の終点ＯＸＣ９８へ動作的
に連結される。第３の中間ＯＸＣ９９が故障したとき、
第１及び第２の中間ＯＸＣ８４及び８６は、第３の始点
ＯＸＣ９７と第３の終点ＯＸＣ９８のための代用パスと
して使用できる。なぜならば、第１の中間ＯＸＣ８４と
第２の中間ＯＸＣ８６は、第３の始点ＯＸＣ９７と第３
の終点ＯＸＣ９８が使用するための波長を確保している
からである。

【００１８】図２は、現用パスと、複数の実現可能な保
護パスとを有する例示的なＷＤＭネットワークの説明図
である。本例のネットワークは、Ａノード１００、Ｂノ
ード１０２、Ｃノード１０４、Ｄノード１０６、Ｅノー
ド１０８及びＦノード１１０を含む。ＡノードとＣノー
ドの間の現用経路は、Ｂノードを介してＡノードとＣノ
ードを連結する実線として示されている。現用経路にリ
ンク故障が存在する場合、たとえば、ＢノードからＣノ
ードへのリンク１０５に故障が存在する場合、Ａノード
のＣノードへのトラフィックは、Ｅノード及びＦノード
を経由してＣノードへ達するように再ルーティングされ
る。この再ルーティングされた経路は、一点鎖線で描か
れた、ＡノードとＥノードの間のリンク１１６、Ｅノー
ドとＦノードの間のリンク１１４、及び、ＦノードとＣ
ノードの間のリンク１１２によって図示されている。こ
れは、ＡノードからＣノードまでの全経路が代用経路で
保護されている経路保護の一例である。

【００１９】或いは、ＢノードとＣノードの間のリンク
は、図２に破線で示されているように、Ｄノードを経由
するリンク１２０及びリンク１１８のリンクトラフィッ
クを再ルーティングすることによっても保護される。し
たがって、Ｄノードを通過する代用経路は、Ｂノードか
らＣノードへのリンクに対する保護パスである。これ
は、リンク保護の一例である。

【００２０】ＷＤＭネットワークをＧ（Ｎ，Ｅ）のよう
に表わすことにする。ここで、Ｎはノードの集合を表わ
し、Ｅはリンクの集合を表わす。ネットワークに広がる
光パスを確立させることを求める要求（デマンド）の集
合をＵで表わす。これらのデマンドは、リンク方式の修
復パスによって保護される。たとえば、デマンドｕ∈Ｕ
の現用パス上の各リンク（ｉ，ｊ）は、ノードｉとノー
ドｊを接続する代用パスによって保護される。ここで、
ｘ_{（ｉ，ｊ）} ^ｕが、デマンドｕのトラフィックを搬送す
るため、リンク（ｉ，ｊ）上に確保された波長の量を表
わす、とする。同様に、ｙ
_{（ｍ，ｎ）} ^{（ｉ，ｊ，ｕ）}は、リンク（ｉ，ｊ）が故障
した場合に、デマンドｕのために確保されているリンク
（ｍ，ｎ）上の波長確保量を表わす。したがって、ｘ
_{（ｉ，ｊ）} ^ｕ及びｙ_{（ｍ，ｎ）} ^{（ｉ，ｊ，ｕ）}は、現用
パスのルーティング及び保護パスのルーティングを夫々
示している。

【００２１】この問題の対処法は、デマンド集合Ｕの完
全な知識を利用して、ネットワーク管理システム（ＮＭ
Ｓ）があらゆる保護パスを最適的に構成する集中管理パ
ラダイムに巧く適合する。しかし、このようなオフライ
ン方式アルゴリズムは、光パスに対するデマンドが動的
に到着し、出発する環境では望ましくない。トラフィッ
ク要求が変化する都度、ネットワーク全体を再構成する
にはコストがかかる。これに対して、オンライン保護ル
ーティングアルゴリズムは、動的な環境において好まし
いアルゴリズムである。

【００２２】オンラインアルゴリズムは、既存のネット
ワーク状態に基づいて保護ルーティングを決定する。未
来の全てのデマンドがわかること、或いは、既存のデマ
ンドが再ルーティングされ得ることを前提としない。オ
ンラインアルゴリズムの目的は、新たに到着したデマン
ドｕ^＊による下限に近い波長要求量を最低限に抑えるこ
とである。現用パスｘ_{（ｉ，ｊ）} ^ｕがミニマムホップパ
スによって決定される場合を想定する。最適化問題は、
保護パス、すなわち、ｙ_{（ｍ，ｎ）} ^{（ｉ，ｊ， ｕ）}を決
定するため以下の通り定式化することができる。

【００２３】

【数１】 但し、

【００２４】

【数２】 を条件とする。

【００２５】上記の条件において、ｂ_{（ｍ，ｎ）}
^{（ｉ，ｊ）}は、リンク（ｍ，ｎ）がリンク（ｉ，ｊ）の
故障からの修復のためｕ^＊によって使用される場合、リ
ンク（ｍ，ｎ）に関する付加的な波長要求量である。付
加的な波長要求量は、他の故障との確保量の共用に基づ
く。

【００２６】したがって、ｙ_{（ｍ，ｎ）}
^{（ｉ，ｊ，ｕ＊）}の決定は、ｉからｊまでの最小コスト
代用パスの検出と等価的であり、既存のネットワーク状
態は、ｗ_{（ｍ，ｎ）} ^{（ｉ，ｊ）}及びｗ_{（ｍ，ｎ）}に集め
られる。その結果として、ＷＤＭネットワークにおける
保護ルーティング問題は、データネットワークにおける
最短パスルーティングアルゴリズムを利用する。

【００２７】次に、必要なネットワーク状態情報を統計
的な形式で与えるリンクメトリック情報を説明する。リ
ンクメトリック情報は、最新のインターネットルーティ
ングの枠組みに適合したオンライン保護ルーティング方
法で使用される。リンクメトリック情報は、保護パスが
同時に活性化される必要がないので、保護波長を共用す
ることにより異なるリンク故障に対する保護パスを与え
る。

【００２８】このリンクメトリック情報は、バケット方
式のリンク状態表現を使用する。ネットワークＧ（Ｎ，
Ｅ）において、各リンクｌＥは、バケットの集合、 ｈ_ｌ＝（ｈ_ｌ ^ｋ，ｋ∈Ｅ，ｋ≠ｌ） を保持する。各バケット、ｈ_ｌ ^ｋは、故障イベントｋに
対応し、バケットの高さ、すなわち、ｈ_ｌ ^ｋの値は、こ
の故障イベントｋに対してリンクｌ上に確保された保護
波長を示す。最適化問題の用語で説明すると、リンクｌ
＝（ｍ，ｎ）と故障ｋ＝（ｉ，ｊ）に対し、対応関係 ｈ_ｌ ^ｋ＝ｗ_{（ｍ，ｎ）} ^{（ｉ，ｊ）} が与えられる。確保されるべき波長の数は、バケット高
さの最大値、すなわち、 ｍａｘ_ｋ ｈ_ｌ ^ｋ と一致する。かくして、各リンクによって与えられた共
用能力に関して必要な情報は、故障イベントによって索
引を付けられた値の系列を保持することによって捕捉さ
れる。

【００２９】共用能力は、故障イベントの関数である。
たとえば、図３において、第４リンク２００は、第１リ
ンク２０２、第２リンク２０４及び第３リンク２０６に
対する保護パス内のリンクとして役立つ。したがって、
第４リンク２００は、３個のパケット、すなわち、第１
リンク２０２用のバケットｈ_４ ^１と、第２リンク２０４
用のバケットｈ_４ ^２と、第３リンク２０６用のバケット
ｈ_４ ^３とを保持する。本例の場合、第４リンク２００
は、第２リンク２０４のために２個の波長を確保し、第
１リンク２０２及び第３リンク２０６のために１個の波
長を確保している。すなわち、第４リンク２００は、第
２リンク２０４のための保護パスの一部として選択され
た場合に、第２リンク２０４上の付加的な波長を保護す
るため、余分な波長を確保しなければならない。これに
対し、第１リンク又は第３リンク上の付加的な波長を保
護するために、余分な波長を確保しなくてもよい。第４
リンクは、既に、第２リンクのために２個の波長を確保
し、これらの２個の波長の確保は第１リンク若しくは第
３リンクの何れかと共用することができるので、他の波
長を割り当てる必要がない。

【００３０】本発明の一実施例において、予め記述され
たリンクメトリック情報は、特定のリンクのためのネッ
トワークを通る保護パスを決定するため、プロセス内で
「最短・最大幅(shortest-widest)」アルゴリズムと結
合される。リンク故障ｋ^＊に関するリンクｌの幅、 ｌ＿ｗｉｄｔｈ（ｌ，ｋ^＊） は、最大バケット高さ ｍａｘ_ｋ ｈ_ｌ ^ｋ と、リンク故障ｋ^＊に対応したバケットとの正規化され
た差として定義される。この幅は、以下のように計算さ
れる。ｍａｘ_ｋ ｈ_ｌ ^ｋ＞０のとき、

【００３１】

【数３】 それ以外のとき、 ｌ＿ｗｉｄｔｈ（ｌ，ｋ^＊）＝０ である。したがって、幅ｌ＿ｗｉｄｔｈ（ｌ，ｋ^＊）
は、０と１の間に収まり、この値は、リンクｌが故障ｋ
^＊の保護のため提供しなければならない共用能力を表わ
す。すなわち、この幅の値が大きくなるほど、共用能力
が高くなる。幅ｌ＿ｗｉｄｔｈ（ｌ，ｋ^＊）の値が０で
あるならば、このリンクは、「使い尽くされた（消
尽）」と考えられ、保護パス内でリンクとしての役割を
果たすためには、付加的な波長を確保しなければならな
い。

【００３２】本発明の一実施例において、修正型Bellma
n-Fordアルゴリズムが、保護されたリンクの端ノードの
間で最大幅を識別するため、すなわち、最も高い共用能
力を与えるパスを識別するため使用される。ここで、リ
ンク故障ｋ^＊に関するパスｐの幅ｐ＿ｗｉｄｔｈ（ｐ，
ｋ^＊）は、そのリンク成分の最小値になるように定義さ
れる。すなわち、

【００３３】

【数４】 である。

【００３４】この定義によって、パスをトラバースする
ための最低限のコストは、パスに沿った最小幅のリンク
によって表わされる。このようなパス候補が二つ以上で
ある場合、それらの幅は全て０であり（すなわち、これ
らのパスは、最低限の波長消費量が非ゼロであるリンク
を通るパスであり）、トラバースする「使い尽くされ
た」消尽リンク、すなわち、幅が０のリンクの数が最も
少ないパスが選択される。正の値のパス幅と同点決勝に
なる他の全ての場合、すなわち、最低限のコストがゼロ
である場合、最大幅パスが無作為的に選択される。上述
の保護パス選択方法は、効率的な保護パスを決定するた
めに、現在のデマンドだけが必要であり、未来に到着す
る情報についての知識は必要ではない。

【００３５】本発明の一実施例において、上述のリンク
方式パス選択方法は、ノード方式パス選択方法に変更さ
れる。前述のバケット方式リンクメトリック情報及び対
応した最短・最大幅ルーティングアルゴリズムは、リン
ク故障によって生ずる光信号の損失に基づいている。結
果として得られる計算された保護パスは、保護されたリ
ンクの一方の端から他方の端まで到達するように制約さ
れる。異なるノードを宛先としてトラバースするデマン
ドに対しても故障リンクの一方の端から他方の端まで進
むようにされているので、修復パスのグループは、ロー
カル・エリアを意図的ではなく妨害し、ネットワーク内
の潜在的な共用能力を十分に利用しない場合がある。図
４の（ａ）及び（ｂ）には、この状況が示されている。

【００３６】図４の（ａ）は、単一リンクを共用する２
本の現用パスのデマンドを説明する図である。第１の始
点ノード４００は、第１の中間ノード４０２及び第２の
中間ノード４０３を経由して、第１の終点ノード４０１
に動作的に接続され、第１の中間ノード４０２と第２の
中間ノード４０３の間に第１のリンク４０５が生成され
る。第２の始点ノード４０６は、第１及び第２の中間ノ
ード４０２及び４０３を介して、第２の終点ノード４０
７に動作的に接続され、第１の中間ノード４０２と第２
の中間ノード４０３の間に第２のリンク４１０が生成さ
れる。

【００３７】リンク方式修復の場合、第１の始点ノード
及び第２の始点ノードから第１の終点ノード及び第２の
終点ノードまでのデマンドに対する保護パスは、第１の
中間ノードから始まり、第２の中間ノードで終了する。
これにより、第３の中間ノード４１２を経由する２本の
保護パス４１４及び４１６が生成される。これは、第４
の中間ノード４１８を含む代用保護パスを組み込む可能
性を制限する。

【００３８】或いは、第１の中間ノード４０２から始ま
り、第５の中間ノード４０４及び第６の中間ノード４０
８で夫々終了するような保護パスが選択されたとき、第
３の中間ノード４１２を含む全ネットワーク型の共用能
力を利用するチャンスが高くなる。

【００３９】図４の（ｂ）は、図４の（ａ）の修復問題
に対する別の解決法である。以下では、この修復解決法
をノード方式修復法と呼ぶ。第１の始点ノード４００
は、第１の中間ノード４０２及び第２の中間ノード４０
３を介して第１の終点ノード４０１へ動作的に接続さ
れ、これにより、第１の中間ノード４０２と第２の中間
ノード４０３の間に第１のリンク４０５が生成される。
第２の始点ノード４０６は、第１及び第２の中間ノード
４０２及び４０３を介して、第２の終点ノード４０７に
動作的に接続され、第１の中間ノード４０２と第２の中
間ノード４０３の間に第２のリンク４１０が生成され
る。

【００４０】ノード方式修復法の場合、第１の始点ノー
ド及び第２の始点ノードから第１の終点ノード及び第２
の終点ノードまでのデマンドに対する保護パスは、第１
の中間ノードから始まり、第５の中間ノード４０４及び
第６の中間ノード４０８で夫々終了する。これにより、
２本の保護パスが生成される。第１の保護パス４１９は
第３の中間ノード４１２を経由する。第２の保護パス４
２０は、第４の中間ノード４１８を経由する。これらの
代用パスは、リンク方式保護パスの状況では利用できな
い全ネットワーク型共用能力を含む。

【００４１】図５の（ａ）及び（ｂ）は、所与のリンク
に対する保護パスが対応した現用パス上で２ホップ離れ
たノードで終了する別の修復メカニズムを示す図であ
る。この修復メカニズムは、ノード方式修復の形式でも
ある。たとえば、図５の（ａ）において、保護パス５０
５は、始点ノード５０２と第１の中間ノード５０４の間
のリンク５００を保護するリンク方式保護パスである。
或いは、図５の（ｂ）において、リンク５００を保護す
る保護パス５０６は、始点ノード５００を第２の中間ノ
ード５０８へ連結するように構成される。特殊なケース
では、ノード方式保護パスは、第２の中間ノード５０８
を終点ノード５１２へ連結する保護パス５１０である。
この場合、終点ノードは宛先であり、現用パスの下流に
他のノードは存在しないので、ノード方式保護パスはリ
ンク方式の場合と同じ終点ノード５１２を有する。

【００４２】故障したノードは、サービスを中断させる
ことがあり、その場合、故障したノードに隣接した全て
のリンクは、同時に機能しなくなる。このような状況下
で、特定のリンクに対する保護パスを生成するために
は、同時に問題が起こっているリンクを意識的に除外す
る必要がある。しかし、リンクの故障とノードの故障を
区別するには、屡々、時間を要し、サービス修復に望ま
しくない遅れを生じさせる。ある種の場合には、保守的
な対応を取ること、すなわち、故障イベントの一般的モ
デルとしてノード故障を使用し、単一のリンク故障を特
殊ケースとして処理する方が有利である。ノード方式の
上述のジャンプ・アヘッド動作は、このような戦略を実
現するために好適である。

【００４３】図６は、本発明によるパス選択処理の一実
施例を説明するフローチャートである。パス選択処理
は、ステップ６００において、入力として、ネットワー
クの記述をＧ（Ｎ，Ｅ）の形で受け取る。ここで、Ｎは
ノードの集合を表わし、Ｅは集合Ｎの中のノード間のリ
ンクの集合を表わす。ｓは始点ノードを表わし、ｔは終
点ノードを表わし、始点ノードｓから終点ノードｔへの
パスが見つけられる。集合Ｅ内の各リンクと関連した予
め記述されたリンクメトリック情報のベクトルの集合を
ｈ_ｅで表わす。

【００４４】パス選択処理は、始点ノードｓと終点ノー
ドの間のリンクの現用パスｒ（ｓ，ｔ）を決定する（ス
テップ６０２）。現用パスにおける各リンクは、故障
し、故障イベントを発生する可能性がある。したがっ
て、現用パスの各リンクに対し、対応した、起こり得る
リンク故障ｋ^＊が存在する。現用パスにおける起こり得
るリンク故障毎に、パス選択処理は、保護パスを決定す
る（ステップ６０４）。

【００４５】パス選択処理は、起こり得るリンク故障ｋ
^＊に対し、開始ノードｓ＿ｎｏｄｅと、宛先ノードｄ＿
ｎｏｄｅを決定する（ステップ６０６）。

【００４６】開始ノードから、ネットワーク内の各リン
クに対し（ステップ６０８）、そのリンクの幅がｈ_ｅか
ら得られたリンクメトリック情報を用いて上述のように
計算される（ステップ６１０）。故障リンク自体へ戻る
リンク故障の幅ｌ＿ｗｉｄｔｈ（ｋ^＊，ｋ^＊）は、保護
パスとしての検討範囲から除外される（ステップ６１
４）。

【００４７】ステップ６０８で計算された幅の集合を用
いて、パス選択処理は、実現可能な保護パスの集合ｗｉ
ｄｅｓｔ＿ｐａｔｈｓを決定し、予め計算された幅を用
いて最大幅保護パスの幅ｗｉｄｅｓｔ＿ｗｉｄｔｈを決
定する（ステップ６１６）。全ての実現可能な保護パス
を通じて、最大幅の実現可能な保護パスの幅が０である
場合、集合ｗｉｄｅｓｔ＿ｐａｔｈｓ内の全ての実現可
能な保護パスが、上述の少なくとも一つの消尽リンクを
含むことを意味する。

【００４８】集合ｗｉｄｅｓｔ＿ｐａｔｈｓ内の実現可
能な保護パスの数が１よりも大きく、かつ、最大幅ｗｉ
ｄｅｓｔ＿ｗｉｄｔｈがゼロに一致するかどうかを判定
し（ステップ６１８）、そうであるならば、パス選択処
理は、含まれる消尽パスの個数が最も少ない実現可能な
保護パスの集合内で保護パスを選択することにより、起
こり得るリンク故障ｋ^＊に対する保護パスｐ［ｋ^＊］を
選択する（ステップ６２０、６２２及び６２６）。

【００４９】集合ｗｉｄｅｓｔ＿ｐａｔｈｓ内の実現可
能な保護パスの数が１よりも大きく、かつ、最大幅ｗｉ
ｄｅｓｔ＿ｗｉｄｔｈが１よりも大きい場合（ステップ
６２８）、パス選択処理は、実現可能な保護パスの集合
から無作為的に、起こり得るリンク故障ｋ^＊に対する保
護パスｐ［ｋ^＊］を選択する（ステップ６３０）。

【００５０】実現可能な保護パスの集合に唯一の実現可
能な保護パスが存在する場合、実現可能な保護パスの集
合におけるこの単一の実現可能な保護パスは、起こり得
るリンク故障ｋ^＊に対する保護パスｐ［ｋ^＊］としてパ
ス選択処理によって選択され（ステップ６３２）。

【００５１】パス選択処理は、現用パス６３４内の各起
こり得るリンク故障に対する保護パスを選択するまで、
保護パスを選択し続ける（ステップ６３４）。

【００５２】パス選択処理は、現用パスｒ（ｓ，ｔ）
と、現用パス内の起こり得るリンク故障の全てに対する
保護パスの集合とを返す。

【００５３】本発明の他の実施例において、図６に示さ
れた処理はネットワーク全体に分散され、経路内の各ノ
ードは経路内の次のノードへのリンクに対する保護パス
を決定する。図７は、ネットワークを用いて経路全体へ
配分された図６の処理を示す。

【００５４】図７は、例示的なネットワークへ適用され
るような本発明による分散型保護パス選択処理の一実施
例のシーケンスチャートである。ネットワークを通る光
パスを確立する要求に応じて、始点ノード７００は、図
６のステップ６０２に関して既に説明したように、端か
ら端までの現用パスを計算する（ステップ７０２）。本
例において、現用パスは、始点ノード７００から、Ｎ１
ノード７０６とＮ２ノード７１６を経由して、終端ノー
ド７２４へ至るパスである。

【００５５】始点ノードは、セットアップメッセージを
Ｎ１ノードへ送信する（ステップ７０４）。セットアッ
プメッセージは現用パスを含むので、Ｎ１ノードは現用
パス内での次のノードを知ることができる。Ｎ１ノード
は、そのノード自体を、現用パスの一部分として構成す
る（ステップ７０７）。

【００５６】始点ノードは、図６のステップ６０６〜６
３４を参照して説明したように、始点ノードのＮ１ノー
ドへのリンクに対する保護パスを決定する。始点ノード
は、関連した全ノードへ、適切なコンフィギュレーショ
ンを実行するように通知する。本例の場合、Ｓ−Ｎ１ノ
ード７１２は、始点ノードとＮ１ノードの間のリンクに
対する保護パス内のノードとして選択される（ステップ
７０８）。始点ノードは、Ｓ−Ｎ１ノードに対し、始点
ノードとＮ１ノードの間のリンクの保護のため波長を確
保するように通知する（ステップ７１０）。

【００５７】Ｎ１ノードは、セットアップメッセージを
経路内の次のノードであるＮ２ノードへ転送する（ステ
ップ７１４）。始点ノードがセットアップメッセージ内
に経路を組み込んでいるので、Ｎ１ノードは経路内の次
のノードを決定しなくてもよい。しかし、Ｎ１ノード
は、Ｎ１ノードとＮ２ノードの間のリンクを保護するた
め、保護パスを選択する役割を担う。Ｎ１ノードは、図
６のステップ６０６〜６３４に関して説明したように、
Ｎ１ノートとＮ２ノードの間のリンクに対する保護パス
を計算する（ステップ７１８）。

【００５８】本例の場合、Ｎ１−Ｎ２ノード７２２は、
Ｎ１ノードとＮ２ノードの間のリンクに対する保護パス
内のノードとして選択される。Ｎ１ノードは、Ｎ１−Ｎ
２ノードがそれ自体を保護パス内のノードとして構成で
きるように、Ｎ１−Ｎ２ノードへ通知メッセージを送信
する（ステップ７２０）。

【００５９】現用経路内の各ノードは、そのノード自体
を現用パスの一部として構成する処理を繰り返す。すな
わち、現用経路内の各ノードは、現用パス内の次のノー
ドへ通知し、現用パス内の次のノードへのリンクに対す
る保護パスを決定し、保護パスに沿ったノードに対し、
保護パス内で用いることができるようにそのノード自体
をコンフィギュレーションするように通知する。

【００６０】図８は、光クロスコネクト（ＯＸＣ）の一
実施例の構成図である。本実施例のＯＸＣ８００は、複
数の光出力８０５の間で複数の光入力８０３を切り替え
る光スイッチ・ファブリック８０２と、複数の光入力へ
動作的に接続され、入力多重波長信号８０８中の別々の
波長を分離する波長デマルチプレクサ８０４と、複数の
光出力へ動作的に接続され、光出力を単一の多重波長出
力信号８１０に合成する波長マルチプレクサ８０６と、
を含む。

【００６１】光スイッチ・ファブリック８０２は、コン
トローラ８１２へ動作的に接続される。コントローラ
は、複数の光入力を、複数の光出力の間でどのように切
り替えるかを決定し、適切なスイッチング制御信号８２
４を光スイッチ・ファブリック８１２へ送る。

【００６２】コントローラ８１２は、上述の分散型保護
パス選択方法を実現するコントローラ命令８１４を実行
するプロセッサ（ＣＰＵ）８１８を含む。コントローラ
８１２は、保護パスを計算している間の中間結果を保持
し、かつ、上述のバケットデータを保持するランダム・
アクセス・メモリ（ＲＡＭ）８１６を含む。

【００６３】コントローラ８１２は、ネットワーク内の
他のＯＸＣから入力されたネットワーク管理信号８２０
を受け取る。ネットワーク管理信号は、ネットワーク内
の他のＯＸＣのコンフィギュレーションに関する情報を
含み、たとえば、上述のバケット情報も含まれる。入力
されたネットワーク管理信号は、さらに、上述の他のＯ
ＸＣからのセットアップメッセージと、通知メッセージ
とを含む。セットアップメッセージは、本例のＯＸＣに
対し、現用パス内のノードになるようにそのＯＸＣ自体
を再構成することを要求する。通知メッセージは、本例
のＯＸＣに対し、保護経路内のノードになるようにその
ＯＸＣ自体を再構成することを要求する。

【００６４】コントローラ８１２は、出力されたネット
ワーク管理信号をネットワーク内の他のノードへ送る。
出力されたネットワーク管理信号は、本例におけるＯＸ
Ｃのコンフィギュレーションに関する情報を含み、たと
えば、上述のように、本例のＯＸＣによって使用され、
かつ、確保された波長の数に関するバケット情報を含
む。出力されたネットワーク管理信号は、他のノードに
対し、現用経路内のノードとしてそのノード自体を再構
成するように要求するセットアップメッセージを含む。
出力されたネットワーク管理信号は、更に、他のノード
に対し、保護経路内のノードとしてそのノード自体を再
構成するように要求する通知メッセージを含む。

【００６５】以上の通り、本発明は、特定の実施例に関
して説明されているが、多数の付加的な変形及び変更が
当業者にとって明白であろう。したがって、本発明は、
上記の実施例に限定されることなく、それ以外の態様で
も実施されることが理解されるべきである。このよう
に、本発明の実施例は、あらゆる観点において、例示的
であり、本発明を制限するものでなく、本発明の範囲
は、この明細書の詳細な説明によってサポートされた請
求項に記載された事項と、それらの均等物とによって定
められる。

【００６６】以上の説明に関して更に以下のような態様
が考えられる。

【００６７】（付記１） リンクの集合によって接続さ
れたノードの集合を含む光ネットワークにおいて、故障
イベントリンクに対する保護パスを決定する方法であっ
て、保護パスリンクの集合に関して保護されたリンクの
集合に対する波長確保量に対応したリンクメトリック情
報の集合を受ける手順と、リンクメトリック情報の集合
を用いて、故障イベントリンクを保護するため保護パス
リンクの容量に対応した幅情報の集合を計算する手順
と、幅情報の集合を用いて、故障イベントリンクに対す
る保護パスリンクを含む保護パスを計算する手順と、を
有するパスルーティング方法。・・・（１）。

【００６８】（付記２） 保護パスリンクの幅情報は、
保護パスリンクに関する最大波長確保量と、故障イベン
トリンクに対する保護パスリンクに関する波長確保量と
の間の正規化された差である、付記１記載のパスルーテ
ィング方法。

【００６９】（付記３） 保護パスを計算する手順は、
実現可能な保護パスの集合を決定する手順と、実現可能
な保護パスの集合に対する保護パス最大幅情報を決定す
る手順と、保護パス最大幅情報を用いて実現可能な保護
パスの集合から保護パスを選択する手順と、を有する、
付記２記載のパスルーティング方法。

【００７０】（付記４） 保護パス最大幅情報を決定す
る手順は、実現可能な保護パスの集合から実現可能な保
護パス幅情報の集合を決定する手順と、実現可能な保護
パス幅情報の集合から実現可能性な保護パス幅情報の最
大値を選択する手順と、を有する、付記３記載のパスル
ーティング方法。

【００７１】（付記５） 実現可能な保護パスの幅情報
は、実現可能な保護パスに含まれる保護パスリンクの幅
情報のうちの最小値である、付記４記載のパスルーティ
ング方法。

【００７２】（付記６） 保護パス最大幅情報は、実現
可能な保護パスに含まれる保護パスリンクのうちの最小
幅情報である、付記３記載のパスルーティング方法。

【００７３】（付記７） 実現可能な保護パスの集合か
ら保護パスを選択する手順は、保護パス最大幅情報がゼ
ロよりも大きい場合に、保護パスを無作為的に選択する
手順を更に有する、付記３記載のパスルーティング方
法。

【００７４】（付記８） 実現可能な保護パスの集合か
ら保護パスを選択する手順は、各実現可能な保護パスに
含まれる幅情報がゼロである保護パスリンクの数を決定
する手順と、幅情報がゼロである保護パスリンクの数が
最も少ない実現可能な保護パスを選択する手順と、を更
に有する、付記３記載のパスルーティング方法。

【００７５】（付記９） リンクの集合によって接続さ
れたノードの集合を含む光ネットワークにおいて、始点
ノードから終端ノードへの保護された現用パスを確立す
る方法であって、始点ノードが、現用パスノードの集合
及び現用パスリンクの集合を含む現用パスを決定する手
順と、始点ノードから第１の現用パスノードへ、保護さ
れた現用パスを含むセットアップメッセージを送る手順
と、始点ノードと第１の現用パスノードを連結する現用
パスリンクを決定する手順と、保護パスリンクの集合に
関して保護されたリンクの集合に対する波長確保量に対
応したリンクメトリック情報の集合を受ける手順と、リ
ンクメトリック情報の集合を用いて、現用パスリンクを
保護するため保護パスリンクの容量に対応した幅情報の
集合を計算する手順と、幅情報の集合を用いて、現用パ
スリンクに対する保護パスリンクを含む保護パスを計算
する手順と、を有するパスルーティング方法。・・・
（２）。

【００７６】（付記１０） 保護パスリンクの幅情報
は、保護パスリンクに関する最大波長確保量と、現用パ
スリンクに対する保護パスリンクに関する波長確保量と
の間の正規化された差である、付記９記載のパスルーテ
ィング方法。

【００７７】（付記１１） 保護パスを計算する手順
は、実現可能な保護パスの集合を決定する手順と、実現
可能な保護パスの集合に対する保護パス最大幅情報を決
定する手順と、保護パス最大幅情報を用いて実現可能な
保護パスの集合から保護パスを選択する手順と、を更に
有する、付記１０記載のパスルーティング方法。

【００７８】（付記１２） 保護パス最大幅情報を決定
する手順は、実現可能な保護パスの集合において実現可
能な保護パスに対する実現可能な保護パス幅情報を決定
する手順と、実現可能性な保護パス幅情報の最大値を選
択する手順と、を有する、付記１１記載のパスルーティ
ング方法。

【００７９】（付記１３） 実現可能な保護パスの幅情
報は、実現可能な保護パスに含まれる保護パスリンクの
幅情報のうちの最小値である、付記１２記載のパスルー
ティング方法。

【００８０】（付記１４） 保護パス最大幅情報を決定
する手順は、実現可能な保護パスに含まれる保護パスリ
ンクのうちの最小幅情報を決定する手順を更に有する、
付記１１記載のパスルーティング方法。

【００８１】（付記１５） 実現可能な保護パスの集合
から保護パスを選択する手順は、保護パス最大幅情報が
ゼロよりも大きい場合に、保護パスを無作為的に選択す
る手順を更に有する、付記１１記載のパスルーティング
方法。

【００８２】（付記１６） 実現可能な保護パスの集合
から保護パスを選択する手順は、各実現可能な保護パス
に含まれる幅情報がゼロである保護パスリンクの数を決
定する手順と、幅情報がゼロである保護パスリンクの数
が最も少ない実現可能な保護パスを選択する手順と、を
更に有する、付記１１記載のパスルーティング方法。

【００８３】（付記１７） リンクの集合によって接続
されたノードの集合を含む光ネットワークにおいて、始
点ノードから終端ノードへの保護された現用パスを確立
する方法であって、始点ノードが先行のノードから、現
用パスノードの集合及び現用パスリンクの集合を含む現
用パスを収容した第１のセットアップメッセージを受け
る手順と、ノードから現用パスノードへ、保護された現
用パスを収容した第２のセットアップメッセージを送る
手順と、ノードと現用パスノードを連結する現用パスリ
ンクを決定する手順と、保護パスリンクの集合に関して
保護されたリンクの集合に対する波長確保量に対応した
リンクメトリック情報の集合を受ける手順と、リンクメ
トリック情報の集合を用いて、現用パスリンクを保護す
るため保護パスリンクの容量に対応した幅情報の集合を
計算する手順と、幅情報の集合を用いて、現用パスリン
クに対する保護パスリンクを含む保護パスを計算する手
順と、を有するパスルーティング方法。・・・（３）。

【００８４】（付記１８） 保護パスリンクの幅情報
は、保護パスリンクに関する最大波長確保量と、現用パ
スリンクに対する保護パスリンクに関する波長確保量と
の間の正規化された差である、付記１７記載のパスルー
ティング方法。

【００８５】（付記１９） 保護パスを計算する手順
は、実現可能な保護パスの集合を決定する手順と、実現
可能な保護パスの集合に対する保護パス最大幅情報を決
定する手順と、保護パス最大幅情報を用いて実現可能な
保護パスの集合から保護パスを選択する手順と、を更に
有する、付記１８記載のパスルーティング方法。

【００８６】（付記２０） 保護パス最大幅情報を決定
する手順は、実現可能な保護パスの集合において実現可
能な保護パス毎に実現可能な保護パス幅情報を決定する
手順と、実現可能性な保護パス幅情報の最大値を選択す
る手順と、を更に有する、付記１９記載のパスルーティ
ング方法。

【００８７】（付記２１） 実現可能な保護パスの幅情
報は、実現可能な保護パスに含まれる保護パスリンクの
幅情報のうちの最小値である、付記２０記載のパスルー
ティング方法。

【００８８】（付記２２） 保護パス最大幅情報を決定
する手順は、実現可能な保護パスに含まれる保護パスリ
ンクのうちの最小幅情報を決定する手順を更に有する、
付記１９記載のパスルーティング方法。

【００８９】（付記２３） 実現可能な保護パスの集合
から保護パスを選択する手順は、保護パス最大幅情報が
ゼロよりも大きい場合に、実現可能な保護パスの集合か
ら保護パスを無作為的に選択する手順を更に有する、付
記１９記載のパスルーティング方法。

【００９０】（付記２４） 実現可能な保護パスの集合
から保護パスを選択する手順は、各実現可能な保護パス
に含まれる幅情報がゼロである保護パスリンクの数を決
定する手順と、幅情報がゼロである保護パスリンクの数
が最も少ない実現可能な保護パスを選択する手順と、を
更に有する、付記１９記載のパスルーティング方法。

【００９１】（付記２５） リンクの集合によって接続
されたノードの集合を含む光リンクにおいて、故障イベ
ントリンクに対する保護パスを決定するよう適合したデ
ータ処理システムであって、プロセッサと、プロセッサ
へ動作的に接続され、上記プロセッサが実行可能なプロ
グラム命令を保持したメモリと、を具備し、プログラム
命令は、保護パスリンクの集合に関して保護されたリン
クの集合に対する波長確保量に対応したリンクメトリッ
ク情報の集合を受けるプログラム命令と、リンクメトリ
ック情報の集合を用いて、故障イベントリンクを保護す
るため保護パスリンクの容量に対応した幅情報の集合を
計算するプログラム命令と、幅情報の集合を用いて、故
障イベントリンクに対する保護パスリンクを含む保護パ
スを計算するプログラム命令と、を有する、データ処理
システム。・・・（４）。

【００９２】（付記２６） 保護パスリンクの幅情報
は、保護パスリンクに関する最大波長確保量と、故障イ
ベントリンクに対する保護パスリンクに関する波長確保
量との間の正規化された差である、付記２５記載のデー
タ処理システム。

【００９３】（付記２７） 保護パスを計算するプログ
ラム命令は、実現可能な保護パスの集合を決定するプロ
グラム命令と、実現可能な保護パスの集合に対する保護
パス最大幅情報を決定するプログラム命令と、保護パス
最大幅情報を用いて実現可能な保護パスの集合から保護
パスを選択するプログラム命令と、を更に有する、付記
２６記載のデータ処理システム。

【００９４】（付記２８） 保護パス最大幅情報を決定
するプログラム命令は、実現可能な保護パスの集合から
実現可能な保護パス幅情報の集合を決定するプログラム
命令と、実現可能な保護パス幅情報の集合から実現可能
性な保護パス幅情報の最大値を選択するプログラム命令
と、を有する、付記２７記載のデータ処理システム。

【００９５】（付記２９） 実現可能な保護パスの幅情
報は、実現可能な保護パスに含まれる保護パスリンクの
幅情報のうちの最小値である、付記２８記載のデータ処
理システム。

【００９６】（付記３０） 保護パス最大幅情報は、実
現可能な保護パスに含まれる保護パスリンクのうちの最
小幅情報である、付記２７記載のデータ処理システム。

【００９７】（付記３１） 実現可能な保護パスの集合
から保護パスを選択するプログラム命令は、保護パス最
大幅情報がゼロよりも大きい場合に、保護パスを無作為
的に選択するプログラム命令を更に有する、付記２７記
載のデータ処理システム。

【００９８】（付記３２） 実現可能な保護パスの集合
から保護パスを選択するプログラム命令は、各実現可能
な保護パスに含まれる幅情報がゼロである保護パスリン
クの数を決定するプログラム命令と、幅情報がゼロであ
る保護パスリンクの数が最も少ない実現可能な保護パス
を選択するプログラム命令と、を更に有する、付記２７
記載のデータ処理システム。

【００９９】（付記３３） リンクの集合によって接続
されたノードの集合を含む光ネットワークにおいて、始
点ノードから終端ノードへの保護された現用パスを確立
するよう適合したデータ処理システムであって、プロセ
ッサと、プロセッサへ動作的に接続され、上記プロセッ
サが実行可能なプログラム命令を保持したメモリと、を
具備し、プログラム命令は、始点ノードが、現用パスノ
ードの集合及び現用パスリンクの集合を含む現用パスを
決定するプログラム命令と、始点ノードから第１の現用
パスノードへ、保護された現用パスを含むセットアップ
メッセージを送るプログラム命令と、始点ノードと第１
の現用パスノードを連結する現用パスリンクを決定する
プログラム命令と、保護パスリンクの集合に関して保護
されたリンクの集合に対する波長確保量に対応したリン
クメトリック情報の集合を受けるプログラム命令と、リ
ンクメトリック情報の集合を用いて、現用パスリンクを
保護するため保護パスリンクの容量に対応した幅情報の
集合を計算するプログラム命令と、幅情報の集合を用い
て、現用パスリンクに対する保護パスリンクを含む保護
パスを計算するプログラム命令と、を有する、データ処
理システム。・・・（５）。

【０１００】（付記３４） 保護パスリンクの幅情報
は、保護パスリンクに関する最大波長確保量と、現用パ
スリンクに対する保護パスリンクに関する波長確保量と
の間の正規化された差である、付記３３記載のデータ処
理システム。

【０１０１】（付記３５） 保護パスを計算するプログ
ラム命令は、実現可能な保護パスの集合を決定するプロ
グラム命令と、実現可能な保護パスの集合に対する保護
パス最大幅情報を決定するプログラム命令と、保護パス
最大幅情報を用いて実現可能な保護パスの集合から保護
パスを選択するプログラム命令と、を更に有する、付記
３４記載のデータ処理システム。

【０１０２】（付記３６） 保護パス最大幅情報を決定
するプログラム命令は、実現可能な保護パスの集合にお
いて実現可能な保護パスに対する実現可能な保護パス幅
情報を決定するプログラム命令と、実現可能性な保護パ
ス幅情報の最大値を選択するプログラム命令と、を更に
有する、付記３５記載のデータ処理システム。

【０１０３】（付記３７） 実現可能な保護パスの幅情
報は、実現可能な保護パスに含まれる保護パスリンクの
幅情報のうちの最小値である、付記３６記載のデータ処
理システム。

【０１０４】（付記３８） 保護パス最大幅情報を決定
するプログラム命令は、実現可能な保護パスに含まれる
保護パスリンクのうちの最小幅情報を決定するプログラ
ム命令を更に有する、付記３５記載のデータ処理システ
ム。

【０１０５】（付記３９） 実現可能な保護パスの集合
から保護パスを選択するプログラム命令は、保護パス最
大幅情報がゼロよりも大きい場合に、実現可能な保護パ
スの集合から保護パスを無作為的に選択するプログラム
命令を更に有する、付記３５記載のデータ処理システ
ム。

【０１０６】（付記４０） 実現可能な保護パスの集合
から保護パスを選択するプログラム命令は、各実現可能
な保護パスに含まれる幅情報がゼロである保護パスリン
クの数を決定するプログラム命令と、幅情報がゼロであ
る保護パスリンクの数が最も少ない実現可能な保護パス
を選択するプログラム命令と、を更に有する、付記３５
記載のデータ処理システム。

【０１０７】（付記４１） リンクの集合によって接続
されたノードの集合を含む光ネットワークにおいて、始
点ノードから終端ノードへの保護された現用パスを確立
するよう適合したデータ処理システムであって、プロセ
ッサと、プロセッサへ動作的に接続され、上記プロセッ
サが実行可能なプログラム命令を保持したメモリと、を
具備し、プログラム命令は、始点ノードが先行のノード
から、現用パスノードの集合及び現用パスリンクの集合
を含む現用パスを収容した第１のセットアップメッセー
ジを受けるプログラム命令と、ノードから現用パスノー
ドへ、保護された現用パスを収容した第２のセットアッ
プメッセージを送るプログラム命令と、ノードと現用パ
スノードを連結する現用パスリンクを決定するプログラ
ム命令と、保護パスリンクの集合に関して保護されたリ
ンクの集合に対する波長確保量に対応したリンクメトリ
ック情報の集合を受けるプログラム命令と、リンクメト
リック情報の集合を用いて、現用パスリンクを保護する
ため保護パスリンクの容量に対応した幅情報の集合を計
算するプログラム命令と、幅情報の集合を用いて、現用
パスリンクに対する保護パスリンクを含む保護パスを計
算するプログラム命令と、を有する、データ処理システ
ム。・・・（６）。

【０１０８】（付記４２） 保護パスリンクの幅情報
は、保護パスリンクに関する最大波長確保量と、現用パ
スリンクに対する保護パスリンクに関する波長確保量と
の間の正規化された差である、付記４１記載のデータ処
理システム。

【０１０９】（付記４３） 保護パスを計算するプログ
ラム命令は、実現可能な保護パスの集合を決定するプロ
グラム命令と、実現可能な保護パスの集合に対する保護
パス最大幅情報を決定するプログラム命令と、保護パス
最大幅情報を用いて実現可能な保護パスの集合から保護
パスを選択するプログラム命令と、を更に有する、付記
４２記載のデータ処理システム。

【０１１０】（付記４４） 保護パス最大幅情報を決定
するプログラム命令は、実現可能な保護パスの集合にお
いて実現可能な保護パス毎に実現可能な保護パス幅情報
を決定するプログラム命令と、実現可能性な保護パス幅
情報の最大値を選択するプログラム命令と、を更に有す
る、付記４３記載のデータ処理システム。

【０１１１】（付記４５） 実現可能な保護パスの幅情
報は、実現可能な保護パスに含まれる保護パスリンクの
幅情報のうちの最小値である、付記４４記載のデータ処
理システム。

【０１１２】（付記４６） 保護パス最大幅情報を決定
するプログラム命令は、実現可能な保護パスに含まれる
保護パスリンクのうちの最小幅情報を決定するプログラ
ム命令を更に有する、付記４３記載のデータ処理システ
ム。

【０１１３】（付記４７） 実現可能な保護パスの集合
から保護パスを選択するプログラム命令は、保護パス最
大幅情報がゼロよりも大きい場合に、実現可能な保護パ
スの集合から保護パスを無作為的に選択するプログラム
命令を更に有する、付記４３記載のデータ処理システ
ム。

【０１１４】（付記４８） 実現可能な保護パスの集合
から保護パスを選択するプログラム命令は、各実現可能
な保護パスに含まれる幅情報がゼロである保護パスリン
クの数を決定するプログラム命令と、幅情報がゼロであ
る保護パスリンクの数が最も少ない実現可能な保護パス
を選択するプログラム命令と、を更に有する、付記４３
記載のデータ処理システム。

【０１１５】（付記４９） リンクの集合によって接続
されたノードの集合を含む光ネットワークにおいて、故
障イベントリンクに対する保護パスを決定させる機能を
コンピュータに実現させるプログラムであって、上記機
能は、保護パスリンクの集合に関して保護されたリンク
の集合に対する波長確保量に対応したリンクメトリック
情報の集合を受ける機能と、リンクメトリック情報の集
合を用いて、故障イベントリンクを保護するため保護パ
スリンクの容量に対応した幅情報の集合を計算する機能
と、幅情報の集合を用いて、故障イベントリンクに対す
る保護パスリンクを含む保護パスを計算する機能と、を
含む、プログラム。・・・（７）。

【０１１６】（付記５０） 保護パスリンクの幅情報
は、保護パスリンクに関する最大波長確保量と、故障イ
ベントリンクに対する保護パスリンクに関する波長確保
量との間の正規化された差である、付記４９記載のプロ
グラム。

【０１１７】（付記５１） 保護パスを計算する機能
は、実現可能な保護パスの集合を決定する機能と、実現
可能な保護パスの集合に対する保護パス最大幅情報を決
定する機能と、保護パス最大幅情報を用いて実現可能な
保護パスの集合から保護パスを選択する機能と、を更に
有する、付記５０記載のプログラム。

【０１１８】（付記５２） 保護パス最大幅情報を決定
する機能は、実現可能な保護パスの集合から実現可能な
保護パス幅情報の集合を決定する機能と、実現可能な保
護パス幅情報の集合から実現可能な保護パス幅情報の最
大値を選択する機能と、を有する、付記５１記載のプロ
グラム。

【０１１９】（付記５３） 実現可能な保護パスの幅情
報は、実現可能な保護パスに含まれる保護パスリンクの
幅情報のうちの最小値である、付記５２記載のプログラ
ム。

【０１２０】（付記５４） 保護パス最大幅情報は、実
現可能な保護パスに含まれる保護パスリンクのうちの最
小幅情報である、付記５２記載のプログラム。

【０１２１】（付記５５） 実現可能な保護パスの集合
から保護パスを選択する機能は、保護パス最大幅情報が
ゼロよりも大きい場合に、保護パスを無作為的に選択す
る機能を更に有する、付記５１記載のプログラム。

【０１２２】（付記５６） 実現可能な保護パスの集合
から保護パスを選択する機能は、各実現可能な保護パス
に含まれる幅情報がゼロである保護パスリンクの数を決
定する機能と、幅情報がゼロである保護パスリンクの数
が最も少ない実現可能な保護パスを選択する機能と、を
更に有する、付記５１記載のプログラム。

【０１２３】（付記５７） リンクの集合によって接続
されたノードの集合を含む光ネットワークにおいて、始
点ノードから終端ノードへの保護された現用パスを確立
する方法であって、始点ノードが、現用パスノードの集
合及び現用パスリンクの集合を含む現用パスを決定する
手順と、始点ノードから第１の現用パスノードへ、保護
された現用パスを含むセットアップメッセージを送る手
順と、始点ノードと第１の現用パスノードを連結する現
用パスリンクを決定する手順と、保護パスリンクの集合
に関して保護されたリンクの集合に対する波長確保量の
集合を受ける手順と、保護パスリンクに関する最大波長
確保量と、現用パスリンクに対する保護パスリンクに関
する波長確保量との間の正規化された差の集合を計算す
る手順と、現用パスリンクに対する実現可能な保護パス
の集合を決定する手順と、実現可能な保護パスの集合か
ら実現可能な保護パス幅情報の集合を決定する手順と、
実現可能な保護パス幅情報の集合から実現可能な保護パ
ス幅情報の最大値を選択する手順と、実現可能な保護パ
スの数が１よりも大きく、かつ、実現可能な保護パス幅
情報の最大値が０よりも大きい場合に、保護パスを無作
為的に選択する手順と、実現可能な保護パスの数が１よ
りも大きく、かつ、実現可能な保護パス幅情報の最大値
が０である場合には、各実現可能な保護パスに含まれる
幅情報がゼロである保護パスリンクの数を決定し、幅情
報がゼロである保護パスリンクの数が最も少ない実現可
能な保護パスを選択する手順と、実現可能な保護パスの
数が１である場合に、該実現可能な保護パスを選択する
手順と、を有するパスルーティング方法。・・・
（８）。

【０１２４】（付記５８） リンクの集合によって接続
されたノードの集合を含む光リンクにおいて、始点ノー
ドから終端ノードへの保護された現用パスを確立するよ
う適合したデータ処理システムであって、プロセッサ
と、プロセッサへ動作的に接続され、上記プロセッサが
実行可能なプログラム命令を保持したメモリと、を具備
し、プログラム命令は、始点ノードが、現用パスノード
の集合及び現用パスリンクの集合を含む現用パスを決定
するプログラム命令と、始点ノードから第１の現用パス
ノードへ、保護された現用パスを含むセットアップメッ
セージを送るプログラム命令と、始点ノードと第１の現
用パスノードを連結する現用パスリンクを決定するプロ
グラム命令と、保護パスリンクの集合に関して保護され
たリンクの集合に対する波長確保量の集合を受けるプロ
グラム命令と、保護パスリンクに関する最大波長確保量
と、現用パスリンクに対する保護パスリンクに関する波
長確保量との間の正規化された差の集合を計算するプロ
グラム命令と、現用パスリンクに対する実現可能な保護
パスの集合を決定するプログラム命令と、実現可能な保
護パスの集合から実現可能な保護パス幅情報の集合を決
定するプログラム命令と、実現可能な保護パス幅情報の
集合から実現可能な保護パス幅情報の最大値を選択する
プログラム命令と、実現可能な保護パスの数が１よりも
大きく、かつ、実現可能な保護パス幅情報の最大値が０
よりも大きい場合に、保護パスを無作為的に選択するプ
ログラム命令と、実現可能な保護パスの数が１よりも大
きく、かつ、実現可能な保護パス幅情報の最大値が０で
ある場合には、各実現可能な保護パスに含まれる幅情報
がゼロである保護パスリンクの数を決定し、幅情報がゼ
ロである保護パスリンクの数が最も少ない実現可能な保
護パスを選択するプログラム命令と、実現可能な保護パ
スの数が１である場合に、該実現可能な保護パスを選択
するプログラム命令と、を有する、データ処理システ
ム。・・・（９）。

【０１２５】（付記５９） 付記４９乃至５６のうちい
ずれか一項記載のプログラムを記録したコンピュータ読
み取り可能な記録媒体。・・・（１０）。

【０１２６】

【発明の効果】本発明によれば、波長分割多重化方式
（ＷＤＭ）ネットワークにおいて、リソース効率に優れ
た最適な保護パスを高速に生成することができるように
なる。

【図面の簡単な説明】

【図１】ＷＤＭ光ネットワークの説明図である。

【図２】現用パス及び複数の実現可能な保護パスを有す
るＷＤＭネットワークの一例の説明図である。

【図３】本発明による波長確保量を蓄えるバケットを含
むリンクメトリック情報の一実施例の説明図である。

【図４】（ａ）はネットワーク内に稼働過多及び稼働不
足を生じるリンク方式修復の説明図であり、（ｂ）は修
復後にネットワークの稼働状態がより効率的になるノー
ド方式修復の説明図である。

【図５】（ａ）及び（ｂ）はネットワークにおける多数
の中間ノードに対するノード方式修復の説明図である。

【図６】本発明によるパス選択処理のフローチャートで
ある。

【図７】例示的なネットワークに適用された本発明によ
る分散型保護パス選択処理の一実施例のタイミングチャ
ートである。

【図８】ＷＤＭ方式ＯＸＣの一実施例の構成図である。

【符号の説明】

８０２ 光スイッチ・ファブリック ８０４ 波長デマルチプレクサ ８０６ 波長マルチプレクサ ８０８ 多重波長信号 ８１０ 多重波長信号 ８１２ コントローラ ８１４ 命令 ８１６ プロセッサ ８１８ ランダム・アクセス・メモリ ８２０ ネットワーク管理信号 ８２２ ネットワーク管理信号

───────────────────────────────────────────────────── フロントページの続き (72)発明者 中条 孝文 アメリカ合衆国，カリフォルニア州 95014，クパティーノ，バブ・ロード 11061番 Ｆターム(参考） 5K002 DA02 DA09 EA33 5K030 GA12 HA08 JA14 JL03 KX23 LB08 MA01 MD02

Claims (10)

【特許請求の範囲】
1. 【請求項１】 リンクの集合によって接続されたノード
   の集合を含む光ネットワークにおいて、故障イベントリ
   ンクに対する保護パスを決定する方法であって、 保護パスリンクの集合に関して保護されたリンクの集合
   に対する波長確保量に対応したリンクメトリック情報の
   集合を受ける手順と、 リンクメトリック情報の集合を用いて、故障イベントリ
   ンクを保護するため保護パスリンクの容量に対応した幅
   情報の集合を計算する手順と、 幅情報の集合を用いて、故障イベントリンクに対する保
   護パスリンクを含む保護パスを計算する手順と、を有す
   るパスルーティング方法。
2. 【請求項２】 リンクの集合によって接続されたノード
   の集合を含む光ネットワークにおいて、始点ノードから
   終端ノードへの保護された現用パスを確立する方法であ
   って、 始点ノードが、現用パスノードの集合及び現用パスリン
   クの集合を含む現用パスを決定する手順と、 始点ノードから第１の現用パスノードへ、保護された現
   用パスを含むセットアップメッセージを送る手順と、 始点ノードと第１の現用パスノードを連結する現用パス
   リンクを決定する手順と、 保護パスリンクの集合に関して保護されたリンクの集合
   に対する波長確保量に対応したリンクメトリック情報の
   集合を受ける手順と、 リンクメトリック情報の集合を用いて、現用パスリンク
   を保護するため保護パスリンクの容量に対応した幅情報
   の集合を計算する手順と、 幅情報の集合を用いて、現用パスリンクに対する保護パ
   スリンクを含む保護パスを計算する手順と、を有するパ
   スルーティング方法。
3. 【請求項３】 リンクの集合によって接続されたノード
   の集合を含む光ネットワークにおいて、始点ノードから
   終端ノードへの保護された現用パスを確立する方法であ
   って、 始点ノードが先行のノードから、現用パスノードの集合
   及び現用パスリンクの集合を含む現用パスを収容した第
   １のセットアップメッセージを受ける手順と、 ノードから現用パスノードへ、保護された現用パスを収
   容した第２のセットアップメッセージを送る手順と、 ノードと現用パスノードを連結する現用パスリンクを決
   定する手順と、 保護パスリンクの集合に関して保護されたリンクの集合
   に対する波長確保量に対応したリンクメトリック情報の
   集合を受ける手順と、 リンクメトリック情報の集合を用いて、現用パスリンク
   を保護するため保護パスリンクの容量に対応した幅情報
   の集合を計算する手順と、 幅情報の集合を用いて、現用パスリンクに対する保護パ
   スリンクを含む保護パスを計算する手順と、を有するパ
   スルーティング方法。
4. 【請求項４】 リンクの集合によって接続されたノード
   の集合を含む光リンクにおいて、故障イベントリンクに
   対する保護パスを決定するよう適合したデータ処理シス
   テムであって、 プロセッサと、 プロセッサへ動作的に接続され、上記プロセッサが実行
   可能なプログラム命令を保持したメモリと、を具備し、 プログラム命令は、 保護パスリンクの集合に関して保護されたリンクの集合
   に対する波長確保量に対応したリンクメトリック情報の
   集合を受けるプログラム命令と、 リンクメトリック情報の集合を用いて、故障イベントリ
   ンクを保護するため保護パスリンクの容量に対応した幅
   情報の集合を計算するプログラム命令と、 幅情報の集合を用いて、故障イベントリンクに対する保
   護パスリンクを含む保護パスを計算するプログラム命令
   と、 を有する、データ処理システム。
5. 【請求項５】 リンクの集合によって接続されたノード
   の集合を含む光ネットワークにおいて、始点ノードから
   終端ノードへの保護された現用パスを確立するよう適合
   したデータ処理システムであって、 プロセッサと、 プロセッサへ動作的に接続され、上記プロセッサが実行
   可能なプログラム命令を保持したメモリと、を具備し、 プログラム命令は、 始点ノードが、現用パスノードの集合及び現用パスリン
   クの集合を含む現用パスを決定するプログラム命令と、 始点ノードから第１の現用パスノードへ、保護された現
   用パスを含むセットアップメッセージを送るプログラム
   命令と、 始点ノードと第１の現用パスノードを連結する現用パス
   リンクを決定するプログラム命令と、 保護パスリンクの集合に関して保護されたリンクの集合
   に対する波長確保量に対応したリンクメトリック情報の
   集合を受けるプログラム命令と、 リンクメトリック情報の集合を用いて、現用パスリンク
   を保護するため保護パスリンクの容量に対応した幅情報
   の集合を計算するプログラム命令と、 幅情報の集合を用いて、現用パスリンクに対する保護パ
   スリンクを含む保護パスを計算するプログラム命令と、
   を有する、データ処理システム。
6. 【請求項６】 リンクの集合によって接続されたノード
   の集合を含む光ネットワークにおいて、始点ノードから
   終端ノードへの保護された現用パスを確立するよう適合
   したデータ処理システムであって、 プロセッサと、 プロセッサへ動作的に接続され、上記プロセッサが実行
   可能なプログラム命令を保持したメモリと、を具備し、 プログラム命令は、 始点ノードが先行のノードから、現用パスノードの集合
   及び現用パスリンクの集合を含む現用パスを収容した第
   １のセットアップメッセージを受けるプログラム命令
   と、 ノードから現用パスノードへ、保護された現用パスを収
   容した第２のセットアップメッセージを送るプログラム
   命令と、 ノードと現用パスノードを連結する現用パスリンクを決
   定するプログラム命令と、 保護パスリンクの集合に関して保護されたリンクの集合
   に対する波長確保量に対応したリンクメトリック情報の
   集合を受けるプログラム命令と、 リンクメトリック情報の集合を用いて、現用パスリンク
   を保護するため保護パスリンクの容量に対応した幅情報
   の集合を計算するプログラム命令と、 幅情報の集合を用いて、現用パスリンクに対する保護パ
   スリンクを含む保護パスを計算するプログラム命令と、
   を有する、データ処理システム。
7. 【請求項７】 リンクの集合によって接続されたノード
   の集合を含む光ネットワークにおいて、故障イベントリ
   ンクに対する保護パスを決定させる機能をコンピュータ
   に実現させるプログラムであって、 上記機能は、 保護パスリンクの集合に関して保護されたリンクの集合
   に対する波長確保量に対応したリンクメトリック情報の
   集合を受ける機能と、 リンクメトリック情報の集合を用いて、故障イベントリ
   ンクを保護するため保護パスリンクの容量に対応した幅
   情報の集合を計算する機能と、 幅情報の集合を用いて、故障イベントリンクに対する保
   護パスリンクを含む保護パスを計算する機能と、を含
   む、プログラム。
8. 【請求項８】 リンクの集合によって接続されたノード
   の集合を含む光ネットワークにおいて、始点ノードから
   終端ノードへの保護された現用パスを確立する方法であ
   って、 始点ノードが、現用パスノードの集合及び現用パスリン
   クの集合を含む現用パスを決定する手順と、 始点ノードから第１の現用パスノードへ、保護された現
   用パスを含むセットアップメッセージを送る手順と、 始点ノードと第１の現用パスノードを連結する現用パス
   リンクを決定する手順と、 保護パスリンクの集合に関して保護されたリンクの集合
   に対する波長確保量の集合を受ける手順と、 保護パスリンクに関する最大波長確保量と、現用パスリ
   ンクに対する保護パスリンクに関する波長確保量との間
   の正規化された差の集合を計算する手順と、 現用パスリンクに対する実現可能な保護パスの集合を決
   定する手順と、 実現可能な保護パスの集合から実現可能な保護パス幅情
   報の集合を決定する手順と、 実現可能な保護パス幅情報の集合から実現可能な保護パ
   ス幅情報の最大値を選択する手順と、 実現可能な保護パスの数が１よりも大きく、かつ、実現
   可能な保護パス幅情報の最大値が０よりも大きい場合
   に、保護パスを無作為的に選択する手順と、 実現可能な保護パスの数が１よりも大きく、かつ、実現
   可能な保護パス幅情報の最大値が０である場合には、 各実現可能な保護パスに含まれる幅情報がゼロである保
   護パスリンクの数を決定し、 幅情報がゼロである保護パスリンクの数が最も少ない実
   現可能な保護パスを選択する手順と、 実現可能な保護パスの数が１である場合に、該実現可能
   な保護パスを選択する手順と、を有するパスルーティン
   グ方法。
9. 【請求項９】 リンクの集合によって接続されたノード
   の集合を含む光リンクにおいて、始点ノードから終端ノ
   ードへの保護された現用パスを確立するよう適合したデ
   ータ処理システムであって、 プロセッサと、 プロセッサへ動作的に接続され、上記プロセッサが実行
   可能なプログラム命令を保持したメモリと、を具備し、 プログラム命令は、 始点ノードが、現用パスノードの集合及び現用パスリン
   クの集合を含む現用パスを決定するプログラム命令と、 始点ノードから第１の現用パスノードへ、保護された現
   用パスを含むセットアップメッセージを送るプログラム
   命令と、 始点ノードと第１の現用パスノードを連結する現用パス
   リンクを決定するプログラム命令と、 保護パスリンクの集合に関して保護されたリンクの集合
   に対する波長確保量の集合を受けるプログラム命令と、 保護パスリンクに関する最大波長確保量と、現用パスリ
   ンクに対する保護パスリンクに関する波長確保量との間
   の正規化された差の集合を計算するプログラム命令と、 現用パスリンクに対する実現可能な保護パスの集合を決
   定するプログラム命令と、 実現可能な保護パスの集合から実現可能な保護パス幅情
   報の集合を決定するプログラム命令と、 実現可能な保護パス幅情報の集合から実現可能な保護パ
   ス幅情報の最大値を選択するプログラム命令と、 実現可能な保護パスの数が１よりも大きく、かつ、実現
   可能な保護パス幅情報の最大値が０よりも大きい場合
   に、保護パスを無作為的に選択するプログラム命令と、 実現可能な保護パスの数が１よりも大きく、かつ、実現
   可能な保護パス幅情報の最大値が０である場合には、 各実現可能な保護パスに含まれる幅情報がゼロである保
   護パスリンクの数を決定し、 幅情報がゼロである保護パスリンクの数が最も少ない実
   現可能な保護パスを選択するプログラム命令と、 実現可能な保護パスの数が１である場合に、該実現可能
   な保護パスを選択するプログラム命令と、を有する、デ
   ータ処理システム。
10. 【請求項１０】 請求項７記載のプログラムを記録した
    コンピュータ読み取り可能な記録媒体。