(57)【特許請求の範囲】
【請求項１】
複数のノードが互いに光パスにより接続される光ネットワークの物理的なトポロジーを与える手段と、
前記複数のノードの各ノードペアについて、整数計画法を用いて、互いにノードを共有しないルートの最大数を求める手段と、
前記各ノードペアについて、前記整数計画法を用いて、前記最大数の互いにノードを共有しない、距離の総和が最小になるルート候補を求める手段と、
前記各ノードペア間の前記ルート候補について、障害発生時に迂回用として利用できるルートの数と満足すべき品質基準に応じて、各ノードペア間の要求光パス数の補正をする手段と、
前記補正された要求光パス数を入力として、どのような障害が発生した場合でも、障害を受けていない現用光パスによって決められた数以上の迂回用パスが確保できるような制約を含む線形計画法を用いて、前記各ノードペアを接続する前記各ルート候補上に配備すべき光パス数を、光ネットワークのコストが最小になるように求める手段とを具備したことを特徴とする光ネットワークの設計方式。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は光ネットワークの設計方式に関し、特に、専用の迂回用光パスを設けず、障害が発生した光パスに流れていたトラヒックを他の現用光パスを用いて迂回させるようにした方式の光ネットワークにおいて、障害発生時に、予め決められた品質基準を満足するために必要となる光パス数を確実に減らすことができ、また、予め決められた品質基準を満足しつつ、光ネットワークのコストが最小となるように、各ルート候補上の各波長面に配備すべき光パス数を決定できる光ネットワークの設計方式に関する。
【０００２】
【従来の技術】
従来から、光ネットワークの信頼性を確保するために、光パスに障害が発生した時には、該障害が発生した光パスに流れていたトラヒックを、専用の光パスを用いて迂回させる方式が提案されている。
【０００３】
この方式において、コストを最小化するような光パスの配備を実現するために、(1)現用の光パスに１対１に対応させて迂回用の光パスを設ける方式（専用プロテクション方式）、(2)１対のノードペア間で迂回用の光パスを共用する方式（共用プロテクション方式）、(3)任意のノードペア間で迂回用の光パスを共用する方式（レストレーション方式）等が知られている。
【０００４】
しかしながら、前記した従来方式では、障害が発生した光パスに流れていたトラヒックを、専用の光パスを用いて迂回させるようにしているので、全体として光パス数が増加して、コストが大きいネットワークしか設計できないという問題があった。
【０００５】
本発明の目的は、前記した従来技術の問題を解消し、専用の迂回用光パスを設けず、障害が発生した光パスに流れていたトラヒックを他の現用光パスを用いて迂回させるようにした方式の光ネットワークにおいて、該光ネットワークのコストを小さく抑えることのできる光ネットワークの設計方式を提供することにある。
【０００６】
【課題を解決するための手段】
前記した目的を達成するために、本発明は、複数のノードが互いに光パスにより接続される光ネットワークの物理的なトポロジーを与える手段と、前記複数のノードの各ノードペアについて、整数計画法を用いて、互いにノードを共有しないルートの最大数を求める手段と、前記各ノードペアについて、前記整数計画法を用いて、前記最大数の互いにノードを共有しない、距離の総和が最小になるルート候補を求める手段と、前記各ノードペア間の前記ルート候補について、障害発生時に迂回用として利用できるルートの数と満足すべき品質基準に応じて、各ノードペア間の要求光パス数の補正をする手段と、前記補正された要求光パス数を入力として、どのような障害が発生した場合でも、障害を受けていない現用光パスによって決められた数以上の迂回用パスが確保できるような制約を含む線形計画法を用いて、前記各ノードペアを接続する前記各ルート候補上に配備すべき光パス数を、光ネットワークのコストが最小になるように求める手段とを具備した点に特徴がある。
【０００７】
この特徴によれば、各ノードペア（ｓ，ｄ）について、整数計画法を２回実行して、距離の総和が最小となる互いにノードを共有しない最大数のルートを確実に求めることができ、障害発生時に予め決められた品質基準を満足するために必要となる光パス数を確実に減らすことができる。
【０００９】
また、コストを最小化するように、各ノードペアを接続する各ルート上の各波長面上に配備すべき光パス数を求めることができる。
【００１０】
【発明の実施の形態】
以下に、本発明を図面を参照して詳細に説明する。図１は、本発明が適用される光ネットワークの一例の概念図である。
【００１１】
図１の光ネットワークでは、複数のノード１〜４が、光スイッチング素子５〜９を介して、光ファイバーからなる光パス１０〜１７によって互いに接続されている。該光ネットワークの障害回復は、専用の迂回用光パスを設けず、障害が発生した光パスに流れていたトラヒックを他の現用光パスを用いて迂回させることにより行われる。例えば、図２に示されているように、発信ノード(s)１から光スイッチング素子５、光パス１０、光スイッチング素子８、光パス１３、光スイッチング素子７および着信ノード（ｄ）３へ流れるトラヒックがあり、光パス１０に障害２０が発生した場合には、該トラヒックは、他の現用の光パス、例えば、光スイッチング素子５、光パス１１、光スイッチング素子６、迂回ノード２、光スイッチング素子６、光パス１２、光スイッチング素子７からなる光パスを通って迂回される。
【００１２】
次に、本発明の光ネットワークの設計方式の一実施形態について、以下に説明する。本実施形態は、前記したように、複数のノードが互いに光パスによって接続されており、光パスに障害が発生した時には、障害が発生した光パスに流れていたトラヒックを他のパスを使って迂回させるような光ネットワークにおいて、障害発生時にも予め決められた品質基準を満足しつつコストを最小化するような光パスの配備を決定することを目標とする。
【００１３】
図３は、本発明の要点を示すフローチャートであり、ステップＳ１では、各ノードペアについて、距離の総和が最小となる互いにノードを共有しない最大数のルートを得る。次に、ステップＳ２では、予め決められた品質基準を満足しつつ、光ネットワークのコストを最小とする、各ルート上の各波長面上に配備すべき光パス数を求める。
【００１４】
以下に、図４を参照して、前記ステップＳ１、Ｓ２の詳細を説明する。なお、図４のステップＳ１１〜Ｓ１５は、前記ステップＳ１に相当する処理であり、ステップＳ１６〜Ｓ１９は、前記ステップＳ２に相当する手順である。
【００１５】
図４のステップＳ１１では、光ネットワークの物理的なトポロジー情報、すなわちノード集合Ｎとリンク集合Linkが与えられる。
【００１６】
ステップＳ１２では、各ノードペア（ｓ、ｄ）について、整数計画法を用いて、互いにノードを共有しないルートの最大数Ｒｓ、ｄを求める。該整数計画法における制約式は次の通りであり、最大とすべき目的関数は、Ｒｓ、ｄである。
0004565483.tif 000002
【００１７】
ここで、上記の式中の各シンボルの意味は、次の通りである。
Ｎ：ネットワークを構成するノードの集合、
Link：ネットワークを構成するリンクの集合、
ｎ：ネットワークを構成するノード、
ｌ：ネットワークを構成するリンク、
ｓ：発信ノード、
ｄ：着信ノード、
ｎｉｎ：ノードｎを終点とするリンクの集合、
ｎｏｕｔ：ノードｎを始点とするリンクの集合、
ａｌ：リンクｌがルートに含まれる時１、含まれない時０となるバイナリー変数。
ステップＳ１３では、 上記の演算により、互いにノードを共有しないルートの最大数Ｒｓ、ｄ が求まる。
【００１８】
次に、ステップＳ１４では、各ノードペア（ｓ、ｄ）について、整数計画法を用いて、距離の総和が最小となるように、前記の演算で求められた数Ｒｓ、ｄ の互いにノードを共有しないルートを求める。整数計画法における制約式は次の通りである。
0004565483.tif 000003
最小とすべき目的関数は、次の式で与えられる。
0004565483.tif 000004
ここで、distｌはリンクｌの距離を表す。
【００１９】
ステップＳ１５では、上記の整数計画法を実行して得られたａｌ の値が、距離の総和が最小になる互いにノードを共有しない最大数のルートを示す。
【００２０】
次に、前記ステップＳ２の処理に移る。以下の処理では、障害発生時に満足すべき品質基準から要求光パス数の補正を行い、この補正された要求光パス数を入力として、線形計画法を用いて、コストを最小化するように、各ノードペアを接続する各ルート上の各波長面上に配備すべき光パス数を求める。
【００２１】
すなわち、ステップＳ１６では、各ノードペア間のルート候補の数が与えられた時に、障害発生時にも予め決められた品質基準を満足するように、必要な発信ノードｓから着信ノードｄまでの補正された要求光パス数Ｄ'ｓ，ｄを次の式を用いて計算する。
Ｄ'ｓ，ｄ  ＝Ｄｓ，ｄ×Ｌｓ，ｄ     ∀ｓ∈Ｎ、∀ｄ∈Ｎ−ｓ
ただし、
Ｌｓ，ｄ＝（Ｒ'ｓ，ｄ＋１）／（Ｒ'ｓ，ｄ×Ｕｓ，ｄ）      ∀ｓ∈Ｎ、∀ｄ∈Ｎ−ｓ
【００２２】
ここで、上記の式中の各シンボルの意味は、次の通りである。
Ｄｓ，ｄ：発信ノードｓから着信ノードｄまでの要求光パス数、
Ｌｓ，ｄ：障害発生時にも予め決められた品質基準を満足するために必要な発信ノードｓから着信ノードｄまでの要求光パス数の増加率、
Ｕｓ，ｄ：障害時に、発信ノードｓから着信ノードｄまでの光パスについて許容される使用率の上昇率、
Ｒ'ｓ，ｄ：発信ノードｓから着信ノードｄまでのあるルートが障害になった時に利用できる迂回用ルート数、発信ノードｓから着信ノードｄまでのノードを共有しないルートの数（Ｒｓ，ｄ）から１を減じた数に相当。
なお、前記Ｕｓ，ｄの値は、発信ノードｓから着信ノードｄ間で障害発生時に満足すべき品質基準から求めることができる。
【００２３】
ステップＳ１７では、ステップＳ１６の演算により、各ノードペア間の補正された要求光パス数Ｄ'ｓ，ｄを得る。
【００２４】
ステップＳ１８では、補正された要求光パス数Ｄ'ｓ，ｄを入力とし、線形計画法を用いて、コストを最小化するように、各ノードペアを接続する各ルート上の各波面上に配備すべき光パス数を求める。ここで、どのような障害が発生した場合でも、障害を受けていない現用光パスによって、Ｒ'ｓ，ｄ倍以上の迂回用パスが確保できるような条件を表す制約式は、以下のようになる。
0004565483.tif 000005
【００２５】
ここで、上記の式中の各シンボルの意味は、次の通りである。
ｔ：迂回ノード、
ＲＴｓ，ｄ：発信ノードｓから着信ノードｄまでのルートの集合、
Ｆ：障害状態の集合、
ＦＲｆ，ｓ，ｄ：障害状態ｆにおいて、障害となる発信ノードｓから着信ノードｄまでのルートの集合、
Ｐｓ，ｄ，ｒ，ｗ：発信ノードｓから着信ノードｄまでのルートｒ上の波長ｗを使用した光パス数、
ＡＰｆ，ｓ，ｄ，ｔ：障害状態ｆにおいて、迂回ノードｔを経由する発信ノードｓから着信ノードｄまでの迂回用パス数。
【００２６】
ここでは、１つまでの迂回ノードを経由する迂回用光パスのみを考える。ｔ＝ｄの時は、ＡＰｆ，ｓ，ｄ，ｔは、迂回ノードを経由しない、発信ノードｓと着信ノードｄを直接接続する迂回用光パス数を表す。ｔ＝ｓの時は、ＡＰｆ，ｓ，ｄ，ｔは常に０であるとみなす。Ｐｓ，ｄ，ｒ，ｗおよびＡＰｆ，ｓ，ｄ，ｔは、本来整数であるが、値の範囲が十分広い場合には、実数として扱うことにより、解精度の劣化を抑えつつ、高速に解を求めることができる。
【００２７】
最小とすべきコストCostは、例えば以下の式で表される。
0004565483.tif 000006
【００２８】
ここで、上記の式中の各シンボルの意味は、次の通りである。
ＵＦｌ：リンクｌにおける使用ファイバー数、
ＵＣｌ：リンクｌにおける使用チャンネル数、
Ｍｎ：ノードｎにおける使用スイッチサイズ、
ＵＷｎ：ノードｎにおける使用スイッチプレーン数、
ＰＲｎ：ノードｎにおけるコストの固定分、
ＵＰｎ：ノードｎを端点とする光パス数、
ＲＦｌ：リンクｌの単位距離当たりの故障率、
ＲＦｎ：ノードｎの故障率、
ＬＲｓ，ｄ，ｒ：発信ノードｓから着信ノードｄまでのルートｒに含まれるリンクの集合、
ＲＬｌ：リンクｌを含むルート（ｓ，ｄ，ｒ）の集合、
ＮＲｓ，ｄ，ｒ：発信ノードｓから着信ノードｄまでのルートｒに含まれる中継ノードの集合、
ＲＮｎ：ノードｎを中継ノードとするルート（ｓ，ｄ，ｒ）の集合、
ＭＡＸｗ：波長ｗについての最大値、
Card｛  ｝：集合｛  ｝の要素数、
α１：単位距離当たりのケーブルコスト、
α２：単位距離当たりのファイバーコスト、
α３：ファイバーコストの固定分、
α４：チャンネルコスト、
β：ポート当たりのノードコスト、
γ：光パスを終端するために必要なコストの２分の１、
δ：光パス当たりの障害コスト。
【００２９】
ステップＳ１９では、前記線形計画法を解いてＰｓ，ｄ，ｒ，ｗを得る。この値が、コストを最小化する、各ノードペアを接続する各ルート上の各波長面上に配備すべき光パス数である。
【００３０】
以上のように、本実施形態によれば、前記ステップＳ１において、各ノードペア（ｓ，ｄ）について、整数計画法を２回実行して、距離の総和が最小となる互いにノードを共有しない最大数のルートを確実に求めることができる。
【００３１】
また、前記ステップＳ２によれば、障害発生時に満足すべき品質基準から要求光パス数の補正を行い、この補正された要求光パス数を入力として、線形計画法を用いて、コストを最小化するように、各ノードペアを接続する各ルート上の各波長面上に配備すべき光パス数を求めることができる。
【００３２】
【発明の効果】
以上の説明から明らかなように、本発明によれば、各ノードペアについて、距離の総和が最小になるような互いにノードを共有しない最大数のルートを確実に求めることができるので、障害発生時にも予め決められた品質基準を満足するために必要となる光パス数を確実に減らすことができ、ひいては、必要となる光ネットワークの容量を小さくすることができる。
【００３３】
また、障害発生時にも、予め決められた品質基準を満足しつつ、光ネットワークのコストが最小となるように、各ルート候補上の各波面上に配備すべき光パス数を決定することができる。
【図面の簡単な説明】
【図１】  本発明が適用される光ネットワークの一例の回路図を示す。
【図２】  光パスに障害が起きた時の迂回光パスを示す図である。
【図３】  本発明の一実施形態の要点を示すフローチャートである。
【図４】  該一実施形態の詳細を示す説明図である。
【符号の説明】
１〜４・・・ノード、５〜９・・・光スイッチング素子、１０〜１７・・・光パス。
【図１】
0004565483.tif 000007
【図２】
0004565483.tif 000008
【図３】
0004565483.tif 000009
【図４】
0004565483.tif 000010