JP3677550B2 - Network configuration method for regular facility expansion - Google Patents

Description

【００１０】
A_ij : リンクi の波長j をCritical Link とする送受信ノードペアの数
【００１１】
【数２】

【００１２】
送受信ノードsd 間の最大流がリンクi の波長j を通っているならば1、そうでなければ0
【００１３】
【数３】

【００１４】
送受信ノードsd 間の最大流を流した際に、リンクi において波長j が余っているならば0、そうでなければ1 (すなわち、リンクi はCritical Link となる)
【００１５】
【非特許文献１】
I. Chlamtac, A.Ganz, and G.Karmi, “Lightpath communications:An approach to high bandwidth optical WAN’s,”IEEE Transactions on Communications, vol. 40, pp. 1171-1182, July 1992.
【非特許文献２】
N. Nagatsu, S. Okamoto, and K. Sato, “Optical path crossconnect system scale evaluation using path accommodation design for restrictedwavelength multiplexing,”IEEE Journal on Selected Areas inCommunications, vol.14, pp. 893-902, June 1996.
【非特許文献３】
Y. Miyao and H. Saito, “Optimal design and evaluation of survivable WDM transport networks,” IEEE Journal on Selected Areas in Communications, vol. 16, pp. 1190-1198, Sept. 1998.
【非特許文献４】
B. V. Caenegem, W. V. Parys, F. D. Turck, and P. M. Demeester,“Demensioning of survivable WDM networks,”IEEE Journal on SelectedAreas in Communications, vol. 16, pp. 1146-1157, Sept. 1998.
【非特許文献５】
M. Sridharan and A. K. Somani,“Design of upgradability in mesh-restorable optical networks,” Optical Network Magazine,vol. 3, May 2002.
【非特許文献６】
N. Geary, A. Antonopoulos, E. Drakopoulos, and J. O’Reilly,“Analysis of optimization issues in multi-period DWDM networkplanning,” in Proc. of IEEE INFOCOM 2001, pp. 152-158, May 2001.
【非特許文献７】
M. Kodialam and T. V. Lakshman, “Minimum interference routing with applications to MPLS traffic engineering,” in Proceedings of IEEE INFOCOM 2000, pp. 884-893, May 2000.
【非特許文献８】
M. Kodialam and T. V. Lakshman, “Integrated dynamic IP and wavelength routing in IP over WDM networks,” in Proc. of IEEE INFOCOM 2001, pp.
358-366, May 2001.
【非特許文献９】
H. Harai, M. Murata, and H. Miyahara, “Performance analysis of wavelength assignment policies in all-optical networks with limited-range wavelength conversion,” IEEE Journal on Selected Areas in Communications, vol. 16, pp. 1051-1060, September 1998.
【非特許文献１０】
Achille Pattavina, "Switching Theory: Architecture and Performance inBroadband ATM Networks," John Wiley & Sons, 1998.
【非特許文献１１】
A. A. Kuehn and M. J.Hamburger, “A heuristic program for locating warehouses,” Management Science, vol. 9, pp. 643-666, July 1963.
【００１６】
【発明が解決しようとする課題】
本発明は、将来のトラヒック量が不確定な状況で、定期的に設備を拡張しながら、低コストのWDM ネットワークを構築する手法を提供する。先述のように、ノードコストは年を経るごとに減少すると考えられる。したがって、本発明は、単年ごとに、トラヒック量を予測し、それを収容するためのネットワークを構築することを目的としている。
【００１７】
ただし、トラヒック量の予測は、誤差があると考え、前年のトラヒックを基に複数のトラヒックパターンを予測する。さまざまなパターンで発生するトラヒックを収容するために、必要最小限の光クロスコネクトOXC と光ファイバを追加して、WDM ネットワークを構築する。単一期間におけるネットワーク構築は、光クロスコネクトOXC と光ファイバの追加を繰返しながら一定の条件（具体的には、適当な複数種類のトラヒックパターンのx%を収容できるという条件）を満たすまで行う。繰り返しが少なければ少ないほど、低コストのネットワークが構築できると考えられる。
【００１８】
WDM ネットワークは主に、ノード設備である光クロスコネクトOXCと光ファイバにより構成されている。長期間にわたりWDM ネットワークを構築する際には、各期間ごとに各ネットワーク設備を追加する量および場所を決定する必要がある。このような各期間ごとの設備配置問題は、以下の二つの問題に分けられる。
1．光クロスコネクトOXC 配置問題: 今期間に配置するOXC の量および場所を決定
2．光ファイバ配置問題：今期間に配置する光ファイバの量および場所を決定
本発明は、各期間ごとにこれら二つの問題を解くことによりWDMネットワークの構築を行う。
【００１９】
さらに本発明は、WDM ネットワークにおけるデマンドは全体のトラヒック量のみ予測し、送受信ノードごとのトラヒック量が不確定な状況で、与えられた設備に対して適切に光ファイバを追加しつつ、収容可能なトラヒック量を最大にする光パス経路決定アルゴリズムEMIRA (Enhanced Minimum Interference Routing Algorithm) を提供することを目的としている。
【００２０】
EMIRA は、従来の経路決定アルゴリズムであるMIRA（非特許文献７参照）、MOCA (Minimum Open Capacity Routing Algorithm)（非特許文献８参照）を本ネットワーク設計に用いるように拡張したアルゴリズムである。本アルゴリズムを用いることで、収容可能な光パス数を最大化する。また、予め想定した光パスを収容するために必要なファイバ数を減らすことができるので、上述のネットワーク設計手法にEMIRA を導入することで追加するネットワーク設備量を抑えることが期待できる。
【００２１】
【課題を解決するための手段】
WDMネットワークの構築は、以下の手順で行われる。
Step 1： 今年度に要求されるトラヒックの推定： 前年度の推定したトラヒックと前年度の収容すべきトラヒックとの誤差をもとに、今年度要求されるトラヒックの平均を推定し、適当にP種類のトラヒックのデマンドパターンを作成する。
Step 2： P種類のデマンドパターンのｘ×100％を収容可能であるWDM ネットワークを以下の拡張ADD アルゴリズムにより構築する。WDM ネットワークがトラヒック変動に対する耐性を備えるまで、以下の操作を繰り返す。
Step 2.1： 光クロスコネクトOXC の配置を行う。
Step 2.2： 光ファイバの配置を行う。
【００２２】
このように、推定したトラヒックを元にネットワークを設計し、OXCの追加と光ファイバの追加をして構築すれば、将来発生するトラヒック（収容すべきトラヒック）も誤差はわずかだから収容することができる。
【００２３】
【発明の実施の形態】
以下、定期的に設備拡張するネットワーク設計手法について詳細に説明する。図１に光ノード構成を示す。WDMネットワークは光ノードとダークファイバ（配置しただけで他装置との接続がされておらず、信号が流されていない光ファイバ）から構成される。光ノードは、波長多重／分離装置(MUX/DEMUX) と波長多重数と同数の光クロスコネクトOXC から構成される。光ノードにおいて波長変換は許されない。ダークファイバは、波長多重／分離装置にファイバが接続されていなければ、新たに接続可能である。以降では、波長分離装置に空きがある場合、それに接続されている光クロスコネクトOXC の入力ポートはすべて１つ空いているとみなす。同様に、波長多重装置に空きがあれば、光クロスコネクトOXC の出力ポートはすべて１つ空いているとみなす。本ネットワーク設計では、定期的に光クロスコネクトOXC の追加とダークファイバの接続を行う。
【００２４】
ただし、一旦追加した設備の構成変更は考えない。例えば、あるノードに注目すると、同一波長を交換する光クロスコネクトOXC が複数置かれることがありうる。それらの光クロスコネクトOXC がClos 構成（入出力がmn × mn のスイッチと同等の機能を小さな複数のスイッチで提供するには、n個のm×(2n-1)スイッチを1段目に、(2n-1)個のm×mスイッチを2段目に、m個の(2n-1)×m スイッチを配置して、隣接段を接続すれば良いという構成法：非特許文献１０参照）などノンブロッキング構成になっていない場合、光ファイバを接続する光クロスコネクトOXC を変更することで、全体の性能が良くなることがある。しかし、一旦接続された光ファイバは運用中のものであり、物理的な移動を伴う接続先の変更には、サービスの中断が発生する。それを避けるために、一旦追加した設備の構成変更は許されないものとする。
【００２５】
以下に、定期的に設備拡張するネットワーク設計手法を提案する。本手法では、ネットワークの耐性という指標x ［即ち、トラヒックが変動しても割合x（x×100 %）までのパス設定要求を受け付けられる］を導入し（0 ≦x≦1）、その割合のデマンド（ある２地点間に送りたいデータ量。ここでは、光パスを設定すればデータを送れるので光パスと解釈できる）をネットワークが収容できると判断するまで設備追加を行う。
【００２６】
拡張期間をN 年として、n = 1,2,…,N に対して、以下の処理を行う。
(1) （トラヒック量予測ステップ）予測n 年目のデマンドの総量Dn を予測する(ただし、Dn は波長の通信容量で正規化された値)。それに対して適当にP 種類のデマンドパターンT1,T2,…,Tp （その例示については後述参照）を発生する。
なお、正規分布に沿ったパターンをP種類作成するのは、パターンはあくまで推定であり、それに近似したトラヒックが到着しても収容できるような設計にするためである。P種類に対応した設計をすることで冗長性をもたせ、少々異なったパターンが着ても柔軟にパス設定できると期待できる。
【００２７】
(2) (光クロスコネクトOXC 追加ステップ) 以下の処理を、xDnP の光パス、（即ち、先に(1)で発生させたデマンドDnPのx×100%）を設定できるまで繰り返す。
(2-a) 適当な数（後述のADDアルゴリズムを用いて決定することができる。）の光クロスコネクトOXC を追加する。追加する場合には、一箇所のノードに同じ規模のクロスコネクトをW個配置する（Wは波長数で各波長用に一つのOXCを追加する。）。
(2-b) i = 1,2,…,P に対して、順に、デマンドパターンTi に対して、後述のEMIRA を適用して、設定できないパス数bi を求める。また、追加する光ファイバの集合（必要な光ファイバ数と必要な位置）を求める。この集合に含まれる光ファイバはこのステップがi = p で終了するまで、ノードに接続されているとみなす。
(2-c) それぞれのデマンドパターンにおいて収容できなかったパス数の総計、即ち、
【００２８】
【数４】

【００２９】
を求める。それぞれのデマンドパターンにおいて収容できなかったパス数の総計が、予め定めた耐性では収容できないと計算されたパス数よりも多いならば、即ち、
【００３０】
【数５】

【００３１】
であれば、制約を満たさないので、再びステップ(2-a) に戻り、処理を続ける。そうでなければ、即ち、
【００３２】
【数６】

【００３３】
なら次のステップ(3) へ。
(3) (光ファイバ接続ステップ) 集合に含まれている光ファイバを実際に配置する。
(4) (運用開始ステップ) 新たに追加した設備への光パスの設定を許す。なお、以前より配置されている設備への光パスの設定は、上記ステップ中でも可能である。
【００３４】
将来の要求トラヒック量が不確定かつ、ノードコストが年の経過とともに減少する状況で、最小コストのネットワークを構築するには、1 度（1 年）の手続きで設備の追加を最小限にすることが有効である。そのためには、トポロジー構築手続きの反復を最小限に抑えることが有効で、上記ステップ(2-b) において、さまざまなデマンドの集合に対して、多くのデマンド(x = 1 ではすべてのデマンド) を収容できるようにファイバを追加することが望ましい。あるデマンドの集合を収容するときに追加するファイバ数を抑えておくと、別のデマンドの集合を収容するために新たなファイバが必要になっても、ファイバを追加する余地が残されている可能性が高い。その結果、少ない反復で制約を満たす数のデマンドを収容できるようになる。
【００３５】
次に、追加するファイバの数を小さく抑えつつ、より多くの光パスを収容するトポロジーを構築することを目的とした経路決定アルゴリズム（EMIRA）について説明する。EMIRA は、ネットワークに追加するファイバの数量および場所を決定するために、上記ステップ（2-b）において適用される。前述のMIRAのステップ（2-b）への適用もノード間の光ファイバ数を予め決め、設定しておけば可能である。しかし、ファイバを自由に設定することで、よりさまざまなトラヒックパターンに適したトポロジーを構築できるため、EMIRA を適用している。
【００３６】
本例示の適用は、ノードを自ら整備し、ダークファイバを通信事業者から借りてネットワークを構築するサービスプロバイダであると想定している。上記のステップ(3) において、適切な数量のダークファイバを通信事業者より借り、ノードに接続する。即ち、何度も反復するステップ(2-b)のEMIRAで必要と判断した光ファイバの和を記憶しておき、ステップ(3)でまとめて借りることができる。ダークファイバは現在大量に敷設されているので、接続するファイバの枯渇はないものとする。なお、本例示の手法では、ファイバを効率的に追加するだけでなく、光クロスコネクトOXC を追加する必要がある。以下、その追加方法について説明する。
【００３７】
光クロスコネクトOXC の配置問題を解くために、ADD アルゴリズム（非特許文献１１参照）を用いる。ADD アルゴリズムは、倉庫の配置問題を解くために提案されたヒューリスティックアルゴリズムである。ADD アルゴリズムは、配置するものを一つずつ追加するという操作を、終了条件が満たされるまで繰り返し行う。従来のADD アルゴリズムは、終了条件として「倉庫を配置することにより削減される輸送コストが倉庫を配置するコストを下回る」ことを用いている。倉庫を配置する場所としては、「削減されるコストが最も大きい」場所を選択する。
【００３８】
本実施例では、ADD アルゴリズムの終了条件としては、「構築したWDM ネットワークがトラヒック変動に対する耐性を備える」ことを用いる。また、ADDアルゴリズムにおいて各光クロスコネクトOXC を配置する場所を決定するための基準としては、「トラヒックの予測値と最大流の比（即ち、最大流（分子）対トラヒックの予測値（分母）比）が最も小さいノードペアの最大流が最も増加する」ことを用いる。最大流は各ノードペアごとに求められる指標であり、あるノードペアの最大流は、すべての空き資源をそのノードペアのみが用いることにより収容可能なトラヒック量を意味する。トラヒックの予測値に対する最大流の比が最も小さいノードペアの最大流の増加を目指しているのは、トラヒックが予測と異なる際に、そのノードペアにおいて資源が不足し、ネットワークのスループットを制限する可能性が高いためである。
【００３９】
ADD アルゴリズムを拡張した本OXC配置アルゴリズムは、終了条件RTC1およびOXC配置場所の決定基準3Mを用いて、期間n に配置したOXC のコストCnの最小化を図るように決定する。一定の耐性を満たしたらすぐOXCの追加をやめることで、余分なコスト増を抑えることができる。また、上記の比が小さいノードのOXCを増やすと、空き資源をトラヒックの予測値に傾斜して均等に残すことができ、耐性が備わりやすい。要するに適材適所にOXCを配置していくので、少ない反復でOXCの追加をやめることができ、コスト最小化につながる。
RTC1 : Ｐ個のトラヒックマトリックス(T1 からTp) により要求される光パスがすべて収容可能である。 RTC は、Robustness against Traffic Changes の略。3M: min(Mij/μij)の値が最も増加するようなノードにOXC を一つ配置する。 3MはMaxmize the Minimum Max-flow の略。
Mij : ノードij 間の最大流。 あるノードペアの最大流は、「すべての空き資源をそのノードペアが用いることにより収容可能なトラヒック量」を表す。
平均値μ_ij は前期間のトラヒックマトリックスを元に予測される。
Ｐ: ネットワーク設計のために用いるトラヒックパターンの数。
【００４０】
本OXC配置アルゴリズムの内容
入力(一年ごと)：物理トポロジー: 前期間までに構築されたもの。ノード数:N、リンク数:L。
【００４１】
出力：物理トポロジー（新たに導入するOXC およびファイバの数、種類、場所）
1. Ｐ個のトラヒックマトリックス(T1 からTp) を生成する。これらＰ個のトラヒックマトリックスの各要素ｔ_ij ^k (1 ≦ k ≦ ｐ)は正規分布N（μ_ij，σ_ij ²）に従う。σは各ノードペア間の要求トラヒックの変動の幅の大きさを表すマトリックスである。各要素σ_ij は、ノードペアij 間で許容すべきトラヒック変動の幅を示す。
2. T1 からTp までを順番に入力として与え、それらを収容できるような物理トポロジーをADDアルゴリズムにより構築する。詳細は次ステップに示す。
3. T1，T2，…，Tp のＰ個のトラヒックパターンそれぞれにより要求される光パスの設定を試みる。要求されたすべての光パスを設定できればネットワーク設計を終了する。光パスを設定するためにEMIRA を用い、必要なファイバは随時追加を行う。OXC のポートが不足すれば、以下の操作によりOXC の追加を行う。
・N 個のノードから、OXC を配置した際にmin （Mij/μij）の値が最も増加するようなノードを１つ選択し、OXC の配置を行う。
【００４２】
本OXC配置アルゴリズムは、トラヒック変動に対する耐性を備えるための条件として、「Ｐ個のトラヒックマトリックス(T1 からTp) をすべて収容可能であること」を用いる。 Tk (1 ≦ k ≦ ｐ) の各要素は正規分布Nに従う確率変数である。標準偏差σ_ij は、アルゴリズムに対して入力として与えられるパラメータであり、ネットワーク設備コストおよびトラヒック変動に対する耐性と以下のような関係がある。
【００４３】
σ の値が小さいと、ネットワーク設備コストは小さいが、トラヒック変動に対する耐性は小である。σ の値が大きいと、ネットワーク設備コストは大きいが、トラヒック変動に対する耐性は大である。
【００４４】
本アルゴリズムの制約条件は、以下の通りである。
（１）各年度において各ノードの各波長に配置されるOXC の数は１つずつのみ(新たに7 ポート必要となったとき、4 ポートのOXC を二つ配置するのではなく、8 ポートのOXC を一つ配置する。OXC 数が大きくなると、階層化グラフにおけるノード数が大きくなり、最短経路を求める際の計算時間が大きくなるため)。
（２）OXC は波長単位ではなく、ノード単位で配置する(OXC を拡張する際には、全ての波長で同時に行うほうが容易である)。
（３）前期間までに既に導入されている光ファイバとOXC の接続を変更することはできない(光ファイバの接続を変更している間に通信が行えなくなることをさけるため)。
【００４５】
Ｐ個のトラヒックパターンの生成方法
トラヒック変動に対する耐性を備えるために収容するべきＰ個のトラヒックパターンの生成手順を以下に示す。
1. T_L、 α をもとに今期間のトラヒックの予測値μ_ij を求める。
μ_ij = α ×μ_ij’(μ_ij’ はT_Lの要素)
T_L : 前期間のトラヒックパターンを表すトラヒックマトリックス。
α : 今期間のトラヒック量と前期間のトラヒック量の比を表す。
2. μ_ij，σ_ij をもとにＰ個のトラヒックパターンを生成する。各トラヒックパターンの要素ｔ_ij ^k（１≦ｋ≦ｎ）の値の範囲は。-∽ < ｔ_ij ^k < ∽となる。なお、| ｔ_ij ^k−μ_ij |≦ σ_ij となる確率は68.3%、|ｔ_ij ^k≦−μ_ij |≦ 2 × σ_ij となる確率は95.5%である。
【００４６】
ネットワーク設計法
前述したネットワーク設計手法において、将来発生するトラヒック量が未知である状況において収容可能なトラヒック量の最大化を目的としたMIRA を光パス設定アルゴリズムとして用いることは可能である。しかし、MIRA はファイバ数も含めた物理トポロジーが与えられた上で、発生したトラヒックを収容する経路を求める方法であるゆえ、予めファイバをノードに接続しておかねばならない。一方、ノード構成を与え、ファイバを適切に追加していけばより多くのトラヒックを収容できると期待されるが、MIRA はそれに適していない。そこで、MIRAを拡張し、光パス経路を決定しつつ光ファイバを適切に追加することによりトポロジーを設計するEMIRA を提案する。
【００４７】
EMIRA では、すべての光クロスコネクトOXC と光ファイバが部分的に接続されているネットワークを物理トポロジーとして与える。光クロスコネクトOXCポートに空きがあれば光ファイバを追加接続できる。EMIRA では(1) 将来どのノードペア間でデマンドが発生しても新たにファイバを追加して空き資源を確保できるよう光クロスコネクトOXC の空きポートを均等に残すよう適切にファイバを追加し、また、(2) すでに配置した資源に対しては、どのノードペア間でデマンドが発生しても空き資源が残るように、なるべく多くの空きがある波長を用いて光パスのルーティングを行っている。そのようなルーティングを行うために、EMIRA では、物理トポロジーをもとに階層グラフ（非特許文献９参照）を作成し、階層グラフ上で求めた最短経路を光パスとする。階層グラフは波長ごとに異なる階層を構成しており、頂点はノードに、辺はそのリンク上の波長に対応している。こうした処理により、収容可能なトラヒック量の最大化を実現する。
【００４８】
階層グラフ自体は周知であるが（非特許文献９参照）、以下、これについて図４及び図５を参照して説明する。図４は物理トポロジーで、N_kはノード、L_kは光ファイバを表す。ノードは実際に複数のクロスコネクトで構成され、また、光ファイバにも波長ごとに異なる信号が流れているので、図４を用いるだけでは、どの経路（通過するクロスコネクトと波長の集合）をとおってデータを送るかを決めることは難しい。そこで、図５のように、ノードと光ファイバを各要素に分解する。これが階層グラフである。
【００４９】
以下に、階層グラフ表記のための記号を導入する。
(1) 階層グラフはＷ層からなる。第ｋ層はｋ番目の波長（λ_k）に相当する。
(2) 各ノードＮiはＷ個の入力ノード、Ｗ個の出力ノードに分解される。これらは、
【００５０】
【数７】

【００５１】
と表される。
(3)もし、波長λ_kからλ_iへの変換がノードＮ_iで許されるならば、第ｋ層と第ｉ層を接続する有向辺Ｗ_i ^kiが存在する。
(4)有向リンクＬ_jはＷ本の辺に分解される。これらの辺は、ｅ_j1，ｅ_j2，・・・，ｅ_jW と表される。
【００５２】
上記説明において分解されてできるW個の入力ノード、W個の出力ノードとは、W個のクロスコネクトを示している。以降のコストCost_ijが、e_ij のコストに相当する。その際、w_i ^klのコストは0である。
【００５３】
EMIRA におけるリンクのコスト
EMIRA ではリンクコストとして、Critical Link のみでなく空いているポート数および波長数を基にした、以下の式(3) を用いる。
【００５４】
Cost_ij ＝ A_ij/(B_i+C_ij) (3)
B_i: リンクi の上流ノードの空き出力ポート数と、下流ノードの光クロスコネクトOXC の空き入力ポート数の小さい方の値
C_ij : リンクi において、既に配置されたファイバ上で利用可能な波長j の数
B_i の導入により、経路を選択する際に空きポート数の多い経路が優先され、空きポート数が少ないリンクへのファイバ追加の可能性を残しやすくなる。後にそのリンクを通るパスを設定できるので、収容可能なトラヒック量が大きくなることが期待できる。また、C_ij の導入により、既に設定されたファイバ上で利用可能な波長が多い経路を優先することにより、新たにファイバを設定する経路よりも既存のファイバを用いる経路を選択しやすくなる。すなわち、Bi の導入と同様に、収容可能なトラヒック量が大きくなることが期待できる。このように、空きポート数が多く、かつ既に設定されたファイバ上において利用可能な波長数が多い波長を選択しやすくすることで、さまざまなデマンドの発生に備えることができる。
【００５５】
EMIRA アルゴリズム
EMIRA では、デマンドの集合それぞれに対し、以下のアルゴリズムを適用し、光パス経路および追加するファイバの場所および数を決定する。以下、EMIRA への入出力を示す。
入力
・階層グラフ
・ 送信ノードs、受信ノードd および要求する光パス数
出力
・ s からd へ光パスを設定する経路、および、光パスに用いる波長
・ 光ファイバを追加する場所、および、数
【００５６】
次に、EMIRA のアルゴリズムを以下に述べる。
(1) 送受信ノードペア(s、 d) 以外の送受信ノードペアそれぞれについて最大流（現在のネットワークの空き資源を用いて送受信ノード間に設定できる最大の光パス数）を求める。
(2) 送受信ノードペア(s、 d) 以外の送受信ノードペアそれぞれについてCritical Link を求め、各リンクのA_ij の値を求める。
(3) 各ノードi の光クロスコネクトOXC の空きポート数(B_i) を求める。
(4) 各リンクi に配置されたファイバ上におけるそれぞれの波長j が空いている数(C_ij ) を求める。
(5) A_ij、B_i、C_ij の値を式(3) に代入し、階層グラフにおける各リンクのコストを求める。
(6) 階層グラフにおいてDijkstra のアルゴリズム［ネットワークのリンク（辺）にコストを与えた時にあるノード（頂点）から任意のノードへの最短コスト（通過する辺が持つコストの総和）経路を求めるアルゴリズム］を用いて光パスを設定する経路および用いる波長を求める。
【００５７】
EMIRA の評価
EMIRA の性能を、非特許文献７の論文で用いられているランダムに生成された15 ノードネットワーク(図3) を対象として、評価する。光クロスコネクトOXC のポート数を16、32 とする。光パス設定要求はすべてのノードペア間でランダムに発生し、その総数を4、000 とする。波長多重数はW = 2、 4、 8、 16 とする。比較のため、MIRA を用いる。MIRA には、各リンクに一様にファイバを設定して構成される物理トポロジーを予め用意する。一方EMIRA にはノードのみが与えられ、ファイバはアルゴリズムに従って追加される。
【００５８】
図６、図７に、W = 16 とした時の、光パス設定要求数に対する呼損発生数を示す。横軸は光パス設定要求回数を示し、縦軸はその回までの呼損発生数を示す。図中、傾きが1 になると、常に呼損が発生していることを表す。本稿では、最初に呼損が起きるまでに収容した光パス設定要求数を尺度とした評価を行う。
【００５９】
図６、図７より、MIRA と比較してEMIRAが最初に呼損が発生するまでに収容可能な光パス数が大きいことがわかる。これは、EMIRAでは各リンクに設定するファイバ数は、ノード規模を超えない限り自由に設定できるので、光パス設定要求が多い場所に多くのファイバを設定しているためである。その経路選択の際、空きポート数が多い光クロスコネクトOXC がある経路を優先して用い、どのリンクにも後からファイバを追加できる可能性を残すことも有効と考えられる。一方、MIRA では光パス設定要求がある場所に関係なく、予めファイバを設定していることからEMIRA に比べて早く呼損が発生している。詳細は省略するが、波長数W = 2、 4、 8 とした場合も同様の結果が得られた。
【００６０】
Cost_ij ² ＝ A_ij/(B_i+c・C_ij) (4)
図８に、波長数W = 16、光クロスコネクトOXC のポート数を16としたときの、10 通りのデマンドパターンにおいて、初めて呼損が発生するまでに収容した光パス数を示す。図の横軸は試行回数を示し、縦軸には初めて呼損が発生するまでに収容した光パス数を示す。この図より、様々なトラヒックパターンにおいても、EMIRA がMIRA よりもより多くの光パスを収容できていることがわかる。
【００６１】
最後に、図９に、異なる10 通りのデマンドパターンにおいて、MIRA において最初に呼損がおきるまでの光パス設定要求回数に対して光パスを設定するために用いた光ファイバ数を示す。MIRA については、予めファイバを配置するため、ファイバ数は常に一定である。EMIRA は、MIRA よりも必要としたファイバ数が少ないことがわかる。これは、EMIRA が各リンクに対して必要なだけのファイバを配置しているためである。これは、経路を決定する際に既に配置されたファイバ上の波長を、新たにファイバを配置することにより利用可能となる波長よりも優先して用いるためである。このように、必要最小限のファイバのみを用意し、光クロスコネクトOXC のポートに空きを残しておくことで、別のデマンドパターンに対する光パスの設定にファイバが必要になっても、ファイバを追加できる可能性がある。
【００６２】
なお、予めファイバ数を変えた構成にしてMIRA を適用すれば、例示した結果より良好な性能を示す可能性がある。しかし、その構成を見つけるためには試行錯誤が必要である。また、その構成はデマンドパターンに依存する。一方、EMIRA はその必要はなく、EMIRA が不確定なデマンドを受け付けやすいネットワークの構築に適していると考えられる。
【００６３】
【発明の効果】
本発明によれば、将来のトラヒック量が不確定な状況で、定期的に設備を拡張しながら、WDM ネットワークを構築することができる。その実現のために、ノード構成が予め決められている時に、収容可能な光パス数を最大にする光パス経路決定アルゴリズムEMIRA を用いることができる。シミュレーションにより提案アルゴリズムを従来のアルゴリズムと比較し、EMIRA は従来手法よりも多くの光パスが収容可能なことを示した。さらに、同数の光パスを収容するために必要とする光ファイバ数も小さく抑えられることを明らかにした。後者の結果は、定期的に設備の拡張を行うネットワーク構成手法に有効であることを示している。
【図面の簡単な説明】
【図１】光ノード構成を例示する図である。
【図２】ネットワークトポロジーを例示する図である。
【図３】 EMIRA の性能を評価するためのネットワークを例示する図である。
【図４】階層グラフを説明するための物理トポロジーを例示する図である。
【図５】図４に例示の物理トポロジーにおけるノードと光ファイバを各要素に分解した階層グラフモデルを例示する図である。
【図６】図３に例示のネットワークを用いてEMIRA の性能をMIRA と比較して評価するために、W = 16 とした時の、光パス設定要求数に対する呼損発生数を示す図である。
【図７】 OXCのポート数を異にする図６と同様な図である。
【図８】波長数W = 16、光クロスコネクトOXC のポート数を16としたときの、10 通りのデマンドパターンにおいて、初めて呼損が発生するまでに収容した光パス数を示す図である。
【図９】異なる10 通りのデマンドパターンにおいて、EMIRA 及びMIRA において最初に呼損がおきるまでの光パス設定要求回数に対して光パスを設定するために用いた光ファイバ数を示す図である。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a network configuration method for constructing a low-cost WDM network while regularly expanding facilities.
[0002]
[Prior art]
The application of WDM (Wavelength Division Multiplexing) technology is considered promising as a fundamental technology in the backbone of the next generation Internet. WDM is an optical technology that realizes high-capacity communication by multiplexing a plurality of wavelengths on a single optical fiber and transmitting data in parallel. Traffic generated in a WDM network is modulated into an optical signal and flows on an optical path set between a transmission / reception node pair. An optical path is a channel with a fixed band set by using a specific wavelength from a traffic transmission node to a reception node. The optical path can be set by appropriately switching the input / output of the optical cross connect (OXC) arranged at the relay node. No photoelectric conversion is performed on the optical path, and the traffic reaches the receiving node as an optical signal (see Non-Patent Document 1).
[0003]
In order to set an optical path for the occurrence of traffic, it is necessary to construct a network having sufficient wavelength resources in advance. Various studies have been made in order to minimize the cost of equipment such as fibers and nodes for construction (see Non-Patent Documents 2 to 4). There are various actual application policies.For example, (1) Estimate the traffic volume in 10 years and find the necessary equipment to set up the optical path for all. (2) Every year Predicting the traffic volume and increasing the equipment step by step can be considered. However, even with the recent increase in access service speeds and the emergence of high-speed applications, it can be understood that the traffic flowing through the Internet has increased dramatically, but it is not possible to grasp the wide area of services and the usage pattern of applications. difficult. In other words, even if the increase in traffic volume in the network can be predicted, it is difficult to accurately predict where the traffic occurs. In addition, due to advances in optical technology, node costs can be expected to decrease, and it is not realistic to prepare expensive facilities to accommodate traffic 10 years ahead. Therefore, application to (1) is difficult. In practice, the optimization is performed assuming that several times as much traffic occurs. Still, not all traffic can be accommodated.
[0004]
Recently, a design method for periodically extending an optical network over a long period of time has also been proposed (see Non-Patent Documents 5 and 6). However, even in these cases, a method for predicting the amount of traffic generated in the future and arranging the equipment so that the network equipment cost is minimized is proposed. However, as described above, it is difficult to accurately predict a change / increase in traffic volume even in a single year, and not all traffic can be accommodated.
[0005]
On the other hand, an approach of accommodating as much traffic as possible is possible. In that case, it is desirable to construct a flexible network that accommodates more traffic at low cost regardless of what traffic occurs.
[0006]
Proposed routing algorithms MIRA (Minimum Interference Routing Algorithm) and MOCA (Minimum Open Capacity Routing Algorithm) aiming to maximize the amount of traffic that can be accommodated in the future when the traffic volume required in the future is uncertain (See Non-Patent Documents 7 and 8). These are online algorithms for finding the shortest path for traffic requests that arrive discretely one after another in a situation where traffic demanded in the future is unknown, MPLS (Multi-Protocol Label Switching) network, GMPLS (Generalized MPLS ) It can be used to set LSP (Label Switched Path) in the network. In MIRA, when a route to be set between a certain transmitting / receiving node pair is obtained, a link that may set a path required by another transmitting / receiving node pair in the future is obtained, and a route that does not interfere with them is selected as much as possible. As a result, the amount of traffic that can be accommodated in the future is maximized. For example, in the network topology as shown in FIG. 2, there are three transmission / reception node pairs (S1, D1), (S2, D2), and (S3, D3), and only one wavelength can be used in each link. When a traffic request occurs in a node pair (S3, D3), using the MIN-HOP algorithm (a method in which the shortest route with all link costs as 1) is one of the conventional route determination algorithms, The path is 1-7-8-5. However, when (S3, D3) uses the link (7, 8), it becomes impossible to set an optical path for the traffic required by the transmission / reception node pair (S1, D1) or (S2, D2). In order to solve this problem, MIRA sets an appropriate link cost and selects route 1-2-3-4-5 with a large number of hops.
[0007]
When a path setting request occurs in a certain sending / receiving node pair, MIRA selects a route that does not pass through the critical link of another sending / receiving node pair as much as possible in order to select a route that does not interfere with the setting of the path required by another sending / receiving node pair in the future. Set the path. Critical Link refers to a link in which the maximum flow of a certain transmission / reception node pair is reduced by use of another transmission / reception node pair in the optical path. Critical Link is defined for each sending / receiving node pair. Here, the maximum flow of a transmission / reception node pair is a set of optical paths that can be set by the transmission / reception node pair using free resources. In MIRA, the shortest route is derived for the cost of each link using the number of transmission / reception node pairs (Equation (1)) with the link as a critical link, and a path is set for the shortest route.
[0008]
      Cost_ij = A_ij                    (1)
[0009]
[Expression 1]

[0010]
A_ij : Number of transmission / reception node pairs in which wavelength j of link i is critical link
[0011]
[Expression 2]

[0012]
1 if the maximum flow between the transmitting and receiving nodes sd passes through the wavelength j of link i, 0 otherwise
[0013]
[Equation 3]

[0014]
When the maximum flow between the transmitting and receiving nodes sd flows, 0 if the wavelength j is left in the link i, 1 otherwise (that is, the link i becomes a critical link)
[0015]
[Non-Patent Document 1]
I. Chlamtac, A. Ganz, and G. Karmi, “Lightpath communications: An approach to high bandwidth optical WAN ’s,” IEEE Transactions on Communications, vol. 40, pp. 1171-1182, July 1992.
[Non-Patent Document 2]
N. Nagatsu, S. Okamoto, and K. Sato, “Optical path crossconnect system scale evaluation using path accommodation design for restrictedwavelength multiplexing,” IEEE Journal on Selected Areas in Communications, vol.14, pp. 893-902, June 1996.
[Non-Patent Document 3]
Y. Miyao and H. Saito, “Optimal design and evaluation of survivable WDM transport networks,” IEEE Journal on Selected Areas in Communications, vol. 16, pp. 1190-1198, Sept. 1998.
[Non-Patent Document 4]
B. V. Caenegem, W. V. Parys, F. D. Turck, and P. M. Demeester, “Demensioning of survivable WDM networks,” IEEE Journal on Selected Areas in Communications, vol. 16, pp. 1146-1157, Sept. 1998.
[Non-Patent Document 5]
M. Sridharan and A. K. Somani, “Design of upgradability in mesh-restorable optical networks,” Optical Network Magazine, vol. 3, May 2002.
[Non-Patent Document 6]
N. Geary, A. Antonopoulos, E. Drakopoulos, and J. O’Reilly, “Analysis of optimization issues in multi-period DWDM networkplanning,” in Proc. Of IEEE INFOCOM 2001, pp. 152-158, May 2001.
[Non-Patent Document 7]
M. Kodialam and T. V. Lakshman, “Minimum interference routing with applications to MPLS traffic engineering,” in Proceedings of IEEE INFOCOM 2000, pp. 884-893, May 2000.
[Non-Patent Document 8]
M. Kodialam and T. V. Lakshman, “Integrated dynamic IP and wavelength routing in IP over WDM networks,” in Proc. Of IEEE INFOCOM 2001, pp.
358-366, May 2001.
[Non-patent document 9]
H. Harai, M. Murata, and H. Miyahara, “Performance analysis of wavelength assignment policies in all-optical networks with limited-range wavelength conversion,” IEEE Journal on Selected Areas in Communications, vol. 16, pp. 1051-1060 , September 1998.
[Non-Patent Document 10]
Achille Pattavina, "Switching Theory: Architecture and Performance in Broadband ATM Networks," John Wiley & Sons, 1998.
[Non-Patent Document 11]
A. A. Kuehn and M. J. Hamburger, “A heuristic program for locating warehouses,” Management Science, vol. 9, pp. 643-666, July 1963.
[0016]
[Problems to be solved by the invention]
The present invention provides a method for constructing a low-cost WDM network while periodically expanding facilities in a situation where future traffic volume is uncertain. As described above, the node cost is considered to decrease with age. Accordingly, an object of the present invention is to construct a network for predicting the traffic volume every year and accommodating it.
[0017]
However, it is considered that there is an error in predicting the traffic volume, and a plurality of traffic patterns are predicted based on the previous year's traffic. In order to accommodate traffic generated in various patterns, a WDM network is constructed by adding the minimum required optical cross-connect OXC and optical fiber. The network construction in a single period is repeated until a certain condition (specifically, a condition that x% of appropriate plural kinds of traffic patterns can be accommodated) is satisfied while repeating the addition of the optical cross-connect OXC and the optical fiber. The smaller the number of repetitions, the lower the cost network can be constructed.
[0018]
The WDM network is mainly composed of optical cross-connect OXC, which is node equipment, and optical fiber. When building a WDM network over a long period of time, it is necessary to determine the amount and location of each network facility to be added for each period. Such a facility placement problem for each period can be divided into the following two problems.
1． Optical cross-connect OXC placement issue: Decide how much and where to place OXC in this period
2． Optical fiber placement problem: Decide how much and where to place optical fiber in this period
The present invention constructs a WDM network by solving these two problems for each period.
[0019]
Furthermore, the present invention predicts only the total traffic volume in a WDM network, and can accommodate an optical fiber appropriately added to a given facility in a situation where the traffic volume for each transmission / reception node is uncertain. The objective is to provide an EMIRA (Enhanced Minimum Interference Routing Algorithm) that determines the optical path routing that maximizes the amount of traffic.
[0020]
EMIRA is an algorithm that has been extended to use MIRA (see Non-Patent Document 7) and MOCA (Minimum Open Capacity Routing Algorithm) (see Non-Patent Document 8), which are conventional routing algorithms, in this network design. By using this algorithm, the number of optical paths that can be accommodated is maximized. In addition, since the number of fibers required to accommodate the optical path assumed in advance can be reduced, it is expected that the amount of network equipment to be added can be suppressed by introducing EMIRA into the above network design method.
[0021]
[Means for Solving the Problems]
The construction of a WDM network is performed according to the following procedure.
Step 1: Estimate the traffic required in the current year: Based on the error between the traffic estimated in the previous year and the traffic that should be accommodated in the previous year, the average of the traffic required in the current year is estimated. Create demand patterns for different types of traffic.
Step 2: Build a WDM network capable of accommodating x × 100% of P types of demand patterns using the following extended ADD algorithm. Repeat the following steps until the WDM network is immune to traffic fluctuations.
Step 2.1: Place the optical cross-connect OXC.
Step 2.2: Place the optical fiber.
[0022]
In this way, if the network is designed based on the estimated traffic and constructed by adding OXC and adding optical fiber, traffic generated in the future (traffic to be accommodated) can be accommodated because there is little error. .
[0023]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, a network design method for periodically expanding equipment will be described in detail. FIG. 1 shows an optical node configuration. A WDM network is composed of optical nodes and dark fibers (optical fibers that are simply placed but not connected to other devices and do not carry signals). The optical node includes a wavelength multiplexing / demultiplexing device (MUX / DEMUX) and the same number of optical cross-connects OXC as the number of wavelength multiplexing. Wavelength conversion is not allowed at the optical node. The dark fiber can be newly connected if the fiber is not connected to the wavelength multiplexing / demultiplexing device. In the following, if there is a vacancy in the wavelength demultiplexer, it is considered that all the input ports of the optical cross-connect OXC connected to it are vacant. Similarly, if there is a vacancy in the wavelength division multiplexing apparatus, it is considered that all the output ports of the optical cross connect OXC are vacant. In this network design, optical cross-connect OXC is added and dark fiber is connected periodically.
[0024]
However, we will not consider changing the configuration of equipment once added. For example, when paying attention to a certain node, there may be a plurality of optical cross-connects OXC that exchange the same wavelength. These optical cross-connects OXC have a Clos configuration (in order to provide the same function as a switch with input / output mn x mn with a plurality of small switches, n m x (2n-1) switches in the first stage, (2n-1) m × m switches are arranged in the second stage, m (2n-1) × m switches are arranged, and adjacent stages may be connected: see Non-Patent Document 10) If the non-blocking configuration is not used, the overall performance may be improved by changing the optical cross-connect OXC that connects the optical fibers. However, the optical fiber once connected is in operation, and service interruption occurs when the connection destination is changed due to physical movement. To avoid this, it is not allowed to change the configuration of equipment once added.
[0025]
Below, we propose a network design method that periodically expands equipment. This method introduces an index x [that is, it can accept path setting requests up to a ratio x (x x 100%) even if the traffic fluctuates] (0 ≤ x ≤ 1). Equipment is added until it is determined that the network can accommodate demand (the amount of data to be sent between two points. In this case, data can be sent if an optical path is set, so it can be interpreted as an optical path).
[0026]
The following processing is performed for n = 1, 2,..., N, where the extension period is N years.
(1) (Traffic amount prediction step) The total amount Dn of demand in the prediction n year is predicted (where Dn is a value normalized by the communication capacity of the wavelength). On the other hand, P kinds of demand patterns T1, T2,..., Tp (see below for examples) are generated appropriately.
The reason why the P types of patterns along the normal distribution are created is that the patterns are only estimates and can be accommodated even when traffic approximating them arrives. By design corresponding to P type, redundancy can be provided, and it can be expected that a path can be set flexibly even if a slightly different pattern is worn.
[0027]
(2) (Optical cross-connect OXC addition step) The following processing is repeated until the xDnP optical path (that is, x × 100% of the demand DnP generated in (1) above) can be set.
(2-a) Add an appropriate number of optical cross-connects OXC (which can be determined using the ADD algorithm described later). When adding, place W cross-connects of the same scale in one node (W is the number of wavelengths, and one OXC is added for each wavelength).
(2-b) For i = 1, 2,..., P, in order, the EMIRA described later is applied to the demand pattern Ti to obtain the number of paths bi that cannot be set. Further, a set of optical fibers to be added (the number of necessary optical fibers and the necessary positions) is obtained. The optical fibers included in this set are considered connected to the node until this step ends with i = p.
(2-c) The total number of paths that could not be accommodated in each demand pattern, that is,
[0028]
[Expression 4]

[0029]
Ask for. If the total number of paths that could not be accommodated in each demand pattern is greater than the number of paths calculated that cannot be accommodated with a predetermined tolerance, that is,
[0030]
[Equation 5]

[0031]
If so, the constraint is not satisfied, so the process returns to step (2-a) and continues. Otherwise, that is,
[0032]
[Formula 6]

[0033]
Then go to the next step (3).
(3) (Optical fiber connection step) The optical fibers included in the set are actually arranged.
(4) (Operation start step) The setting of the optical path to the newly added equipment is permitted. In addition, the setting of the optical path to the equipment arrange | positioned from before is also possible in the said step.
[0034]
In order to build a minimum cost network in a situation where future demand traffic is indeterminate and the node cost decreases with the passage of time, the addition of equipment should be minimized in one (1 year) procedure. Is effective. For this purpose, it is effective to minimize the iteration of the topology construction procedure, and in step (2-b) above, many demands (all demands when x = 1) are applied to various demand sets. It is desirable to add fibers so that they can be accommodated. Limiting the number of fibers added when accommodating a set of demands may leave room for additional fibers when new fibers are needed to accommodate a set of other demands High nature. As a result, the number of demands that satisfy the constraints can be accommodated with a small number of iterations.
[0035]
Next, a routing algorithm (EMIRA) for the purpose of constructing a topology that accommodates more optical paths while keeping the number of added fibers small will be described. EMIRA is applied in step (2-b) above to determine the quantity and location of fiber added to the network. Application to the above-mentioned MIRA step (2-b) is also possible if the number of optical fibers between nodes is determined and set in advance. However, EMIRA is applied because the topology suitable for various traffic patterns can be constructed by setting the fiber freely.
[0036]
The application of this example is assumed to be a service provider that maintains a node itself and borrows dark fiber from a telecommunications carrier to construct a network. In step (3) above, an appropriate amount of dark fiber is borrowed from the carrier and connected to the node. That is, it is possible to store the sum of the optical fibers determined to be necessary by EMIRA in step (2-b) that is repeated many times and borrow them collectively in step (3). Since dark fibers are currently laid in large quantities, it is assumed that there is no exhaustion of connected fibers. In this example method, it is necessary to add not only the fiber efficiently but also the optical cross-connect OXC. Hereinafter, the addition method will be described.
[0037]
In order to solve the optical cross-connect OXC placement problem, an ADD algorithm (see Non-Patent Document 11) is used. The ADD algorithm is a heuristic algorithm proposed to solve the warehouse placement problem. The ADD algorithm repeats the operation of adding one to be arranged one by one until the end condition is satisfied. The conventional ADD algorithm uses “the transportation cost reduced by placing a warehouse is lower than the cost of placing a warehouse” as an end condition. As a place where the warehouse is arranged, a place having the “largest cost to be reduced” is selected.
[0038]
In the present embodiment, as the termination condition of the ADD algorithm, it is used that “the constructed WDM network has resistance against traffic fluctuation”. In addition, the criteria for determining where to place each optical cross-connect OXC in the ADD algorithm is “the ratio of the predicted traffic to the maximum flow (ie the ratio of the maximum flow (numerator) to the predicted traffic (denominator) ratio”. The maximum flow of the node pair with the smallest) increases the most. The maximum flow is an index obtained for each node pair, and the maximum flow of a certain node pair means the amount of traffic that can be accommodated by using only all the free resources by that node pair. The goal is to increase the maximum flow of the node pair with the smallest ratio of the maximum flow to the predicted traffic value, when the traffic is different from the prediction, there is a possibility that the node pair will run out of resources and limit the network throughput. This is because it is expensive.
[0039]
This OXC placement algorithm, which is an extension of the ADD algorithm, decides to minimize the cost Cn of the OXC placed in period n using the termination condition RTC1 and the OXC placement location decision criterion 3M. By adding OXC as soon as a certain level of resistance is met, the extra cost increase can be suppressed. In addition, increasing the OXC of nodes with a small ratio can leave free resources evenly in proportion to the predicted traffic value, making it easier to withstand. In short, since OXC is placed in the right place for the right material, it is possible to stop adding OXC with fewer iterations, leading to cost minimization.
RTC1: All optical paths required by P traffic matrices (T1 to Tp) can be accommodated. RTC stands for Robustness against Traffic Changes. 3M: One OXC is placed at a node where the value of min (Mij / μij) increases most. 3M stands for Maximize the Minimum Max-flow.
Mij: Maximum flow between nodes ij. The maximum flow of a certain node pair represents “the amount of traffic that can be accommodated by using all free resources by that node pair”.
Average value μ_ij Is predicted based on the traffic matrix of the previous period.
P: Number of traffic patterns used for network design.
[0040]
Contents of this OXC placement algorithm
Input (every year): Physical topology: constructed by the previous period. Number of nodes: N, number of links: L.
[0041]
Output: Physical topology (number, type and location of newly installed OXC and fiber)
1. Generate P traffic matrices (T1 to Tp). Each element t of these P traffic matrices_ij ^k (1 ≤ k ≤ p) is the normal distribution N (μ_ij, Σ_ij ²) σ is a matrix that represents the magnitude of the fluctuation width of the requested traffic between each node pair. Each element σ_ij Indicates the range of traffic fluctuation to be allowed between node pairs ij.
2. T1 to Tp are given as inputs in order, and a physical topology that can accommodate them is constructed by the ADD algorithm. Details are shown in the next step.
3. Attempt to set the optical path required by each of the P traffic patterns T1, T2, ..., Tp. If all the required optical paths can be set, the network design is completed. Use EMIRA to set up the optical path and add the required fiber as needed. If there are not enough OXC ports, add OXC by the following operation.
・ From N nodes, select one node whose min (Mij / μij) value increases most when OXC is placed, and then place OXC.
[0042]
The present OXC placement algorithm uses “that all P traffic matrices (T1 to Tp) can be accommodated” as a condition for providing resistance to traffic fluctuations. Each element of Tk (1 ≦ k ≦ p) is a random variable according to the normal distribution N. Standard deviation σ_ij Is a parameter given as an input to the algorithm and has the following relationship with network equipment cost and resistance to traffic fluctuations.
[0043]
When the value of σ is small, the network equipment cost is small, but the resistance to traffic fluctuation is small. If the value of σ is large, the network equipment cost is large, but the resistance to traffic fluctuation is large.
[0044]
The constraints of this algorithm are as follows.
(1) In each fiscal year, only one OXC is allocated to each wavelength of each node (when 7 ports are newly required, instead of allocating two 4-port OXCs, an 8-port One OXC is placed because the number of nodes in the hierarchical graph increases as the number of OXCs increases, and the calculation time for finding the shortest path increases.
(2) OXC is placed in units of nodes, not in units of wavelengths (when expanding OXC, it is easier to do it at all wavelengths simultaneously).
(3) It is not possible to change the connection between the optical fiber and OXC that have already been introduced by the previous period (to prevent communication from being disabled while changing the optical fiber connection).
[0045]
Method for generating P traffic patterns
A procedure for generating P traffic patterns to be accommodated in order to provide resistance to traffic fluctuation is shown below.
1. T_L, Α is the predicted traffic value for the current period μ_ij Ask for.
μ_ij = α × μ_ij’(Μ_ij’Is T_LElement)
T_L : A traffic matrix representing the traffic pattern of the previous period.
α: Indicates the ratio of the traffic volume in the current period to the traffic volume in the previous period.
2.μ_ij, Σ_ij Based on the above, P traffic patterns are generated. Element t of each traffic pattern_ij ^kWhat is the range of values for (1 ≦ k ≦ n)? -∽ <t_ij ^k <Become a trap. T_ij ^k−μ_ij | ≦ σ_ij Probability of 68.3%, | t_ij ^k≤ -μ_ij | ≦ 2 × σ_ij The probability of being 95.5%.
[0046]
Network design method
In the network design method described above, it is possible to use MIRA as an optical path setting algorithm for the purpose of maximizing the traffic volume that can be accommodated in a situation where the traffic volume generated in the future is unknown. However, since MIRA is a method for obtaining a path for accommodating generated traffic after a physical topology including the number of fibers is given, it is necessary to connect the fibers to the nodes in advance. On the other hand, it is expected that more traffic can be accommodated by providing a node configuration and adding appropriate fibers, but MIRA is not suitable for it. Therefore, we propose EMIRA that expands MIRA and designs topology by adding optical fiber appropriately while determining optical path route.
[0047]
In EMIRA, a network in which all optical cross-connects OXC and optical fibers are partially connected is given as a physical topology. If there is a free space in the optical cross-connect OXC port, additional optical fibers can be connected. In EMIRA, (1) regardless of future node pair demands, fiber should be added appropriately so that the unused ports of the optical cross-connect OXC are left evenly so that new resources can be added to secure free resources. (2) For resources that have already been arranged, optical path routing is performed using wavelengths with as many vacancies as possible so that vacant resources remain even if demand occurs between any pair of nodes. In order to perform such routing, EMIRA creates a hierarchical graph (see Non-Patent Document 9) based on the physical topology, and uses the shortest path obtained on the hierarchical graph as an optical path. The hierarchical graph configures a different hierarchy for each wavelength, with vertices corresponding to nodes and edges corresponding to wavelengths on the link. By such processing, the traffic volume that can be accommodated is maximized.
[0048]
Although the hierarchical graph itself is well known (see Non-Patent Document 9), this will be described below with reference to FIGS. Figure 4 shows the physical topology, N_kIs the node, L_kRepresents an optical fiber. Since a node is actually composed of a plurality of cross-connects, and different signals for each wavelength also flow through the optical fiber, any route (a set of cross-connects passing through and a set of wavelengths) can be reached using only FIG. It is difficult to decide whether to send data. Therefore, as shown in FIG. 5, the node and the optical fiber are disassembled into respective elements. This is a hierarchical graph.
[0049]
The following introduces symbols for hierarchical graph notation.
(1) The hierarchical graph consists of W layers. The kth layer is the kth wavelength (λ_k).
(2) Each node Ni is decomposed into W input nodes and W output nodes. They are,
[0050]
[Expression 7]

[0051]
It is expressed.
(3) If wavelength λ_kTo λ_iConversion to node N_i, The directed side W connecting the kth layer and the ith layer._i ^kiExists.
(4) Directed link L_jIs broken down into W edges. These sides are e_j1, E_j2, ..., e_jW It is expressed.
[0052]
The W input nodes and W output nodes generated by disassembling in the above description indicate W cross-connects. Cost after Cost_ijBut e_ij Equivalent to the cost of In that case, w_i ^klThe cost is 0.
[0053]
Link cost in EMIRA
EMIRA uses the following formula (3) as the link cost based on the number of available ports and wavelengths as well as the critical link.
[0054]
Cost_ij = A_ij/ (B_i+ C_ij(3)
B_i: The smaller of the number of empty output ports of the upstream node of link i and the number of empty input ports of the optical cross-connect OXC of the downstream node
C_ij : Number of wavelengths j available on already placed fiber in link i
B_i With the introduction of, a route with a large number of free ports is given priority when selecting a route, and it is easy to leave a possibility of adding a fiber to a link with a small number of free ports. Since a path passing through the link can be set later, it can be expected that the amount of traffic that can be accommodated increases. C_ij By giving priority to a path with many wavelengths that can be used on an already set fiber, it becomes easier to select a path using an existing fiber than a path for setting a new fiber. In other words, it can be expected that the amount of traffic that can be accommodated will increase as with the introduction of Bi. In this way, it is possible to prepare for the generation of various demands by making it easy to select wavelengths with a large number of free ports and a large number of wavelengths that can be used on already set fibers.
[0055]
EMIRA algorithm
In EMIRA, for each set of demands, the following algorithm is applied to determine the location and number of optical paths and additional fibers. The input / output to EMIRA is shown below.
input
・ Hierarchy graph
-Transmitting node s, receiving node d, and the number of requested optical paths
output
・ Path to set optical path from s to d, and wavelength used for optical path
・ Where and how many optical fibers are added
[0056]
Next, the EMIRA algorithm is described below.
(1) The maximum flow (the maximum number of optical paths that can be set between the transmitting and receiving nodes using available resources of the current network) is determined for each transmitting and receiving node pair other than the transmitting and receiving node pair (s, d).
(2) Obtain a critical link for each transmitting / receiving node pair other than the transmitting / receiving node pair (s, d), and_ij Find the value of.
(3) Number of free ports of optical cross-connect OXC of each node i (B_i)
(4) The number of vacant wavelengths j on the fiber placed on each link i (C_ij )
(5) A_ij, B_i, C_ij Is substituted into equation (3) to determine the cost of each link in the hierarchical graph.
(6) Dijkstra's algorithm in a hierarchical graph [algorithm for finding the shortest cost (sum of the costs of passing edges) path from any node (vertex) to any node when a cost is given to a network link (edge)] Is used to determine the path for setting the optical path and the wavelength to be used.
[0057]
EMIRA rating
The performance of EMIRA is evaluated for a randomly generated 15-node network (Fig. 3) used in the paper of Non-Patent Document 7. The number of optical cross-connect OXC ports is 16, 32. The optical path setting request is randomly generated between all node pairs, and the total number is 4,000. The number of wavelength divisions is W = 2, 4, 8, and 16. MIRA is used for comparison. MIRA prepares in advance a physical topology that is configured by uniformly setting fibers on each link. On the other hand, only nodes are given to EMIRA, and fibers are added according to the algorithm.
[0058]
FIGS. 6 and 7 show the number of lost calls with respect to the number of optical path setting requests when W = 16. The horizontal axis indicates the number of optical path setting requests, and the vertical axis indicates the number of call loss occurrences up to that time. In the figure, a slope of 1 indicates that call loss has always occurred. In this paper, we evaluate the number of optical path setup requests accommodated before the first call loss.
[0059]
6 and 7, it can be seen that the number of optical paths that can be accommodated by EMIRA before the first call loss occurs is larger than MIRA. This is because, in EMIRA, the number of fibers set for each link can be set freely as long as it does not exceed the node scale, so a large number of fibers are set in places where there are many requests for optical path setting. When selecting the route, it is also effective to preferentially use a route that has an optical cross-connect OXC with a large number of free ports and to add a fiber to any link later. On the other hand, in MIRA, regardless of the location where the optical path setting request is made, the fiber is set in advance, so call loss occurs earlier than EMIRA. Although details are omitted, similar results were obtained when the number of wavelengths was set to W = 2, 4, and 8.
[0060]
Cost_ij ² = A_ij/ (B_i+ c ・ C_ij) (Four)
FIG. 8 shows the number of optical paths accommodated until the first call loss in 10 different demand patterns when the number of wavelengths is W = 16 and the number of ports of the optical cross-connect OXC is 16. The horizontal axis in the figure indicates the number of trials, and the vertical axis indicates the number of optical paths accommodated until the first call loss occurs. This figure shows that EMIRA can accommodate more optical paths than MIRA in various traffic patterns.
[0061]
Finally, FIG. 9 shows the number of optical fibers used to set an optical path with respect to the number of optical path setting requests until the first call loss in MIRA in 10 different demand patterns. For MIRA, the number of fibers is always constant because fibers are arranged in advance. It can be seen that EMIRA requires fewer fibers than MIRA. This is because EMIRA places as many fibers as needed for each link. This is because the wavelength on the fiber that has already been arranged when determining the route is used in preference to the wavelength that can be used by newly arranging the fiber. In this way, by preparing only the minimum required fiber and leaving a space in the port of the optical cross-connect OXC, even if a fiber is required for setting the optical path for another demand pattern, the fiber is added. There is a possibility.
[0062]
Note that if MIRA is applied with a configuration in which the number of fibers is changed in advance, there is a possibility that better performance than the exemplified results may be exhibited. However, trial and error are necessary to find the configuration. Further, the configuration depends on the demand pattern. On the other hand, EMIRA is not necessary, and it is considered suitable for building a network where EMIRA can easily accept uncertain demand.
[0063]
【The invention's effect】
According to the present invention, it is possible to construct a WDM network while regularly expanding facilities in a situation where the future traffic volume is uncertain. To realize this, an optical path routing algorithm EMIRA that maximizes the number of optical paths that can be accommodated when the node configuration is predetermined can be used. Simulations compare the proposed algorithm with the conventional algorithm and show that EMIRA can accommodate more optical paths than the conventional method. Furthermore, it was clarified that the number of optical fibers required to accommodate the same number of optical paths can be kept small. The latter result shows that it is effective for a network configuration method that periodically expands facilities.
[Brief description of the drawings]
FIG. 1 is a diagram illustrating an optical node configuration.
FIG. 2 is a diagram illustrating a network topology.
FIG. 3 is a diagram illustrating a network for evaluating EMIRA performance;
FIG. 4 is a diagram illustrating a physical topology for explaining a hierarchical graph.
FIG. 5 is a diagram illustrating a hierarchical graph model in which nodes and optical fibers in the physical topology illustrated in FIG. 4 are decomposed into respective elements.
FIG. 6 is a diagram illustrating the number of call loss occurrences with respect to the number of optical path setting requests when W = 16 in order to evaluate the performance of EMIRA compared to MIRA using the network illustrated in FIG. 3; .
7 is a view similar to FIG. 6 in which the number of OXC ports is different.
FIG. 8 is a diagram showing the number of optical paths accommodated until call loss occurs for the first time in 10 demand patterns when the number of wavelengths is W = 16 and the number of ports of the optical cross-connect OXC is 16.
FIG. 9 is a diagram illustrating the number of optical fibers used to set an optical path with respect to the number of optical path setting requests until the first call loss occurs in EMIRA and MIRA in ten different demand patterns.

Claims (5)

In a network configuration method for constructing a WDM network while regularly expanding facilities,
Based on the error between the traffic estimated in the previous year and the traffic that should be accommodated, the average of the traffic required in a given year is estimated to create a demand pattern for multiple types (P) of traffic,
Add an optical cross-connect OXC until the WDM network is resistant to traffic fluctuations by accommodating a predetermined ratio (x) of the multiple types (P) of demand patterns, and then add an optical fiber. Repeatedly, even if there is a traffic demand pattern different from the estimated traffic, it can accommodate many demands ,
As the demand pattern, assuming that the expansion period is N years, for n = 1, 2, ... , N , the total amount ( Dn ) of demand in the predicted n year is predicted, and the total amount ( Dn ) is Generate multiple types of demand patterns ( P ),
A predetermined number of optical cross-connects OXC are added until an optical path of a value ( xDnP ) obtained by multiplying the total amount of demand ( Dn ) by the predetermined ratio (x) and the number of types of demand patterns (P) can be set ; Repeat the operation to add an optical fiber.
Network configuration method for constructing a WDM network which consists. The procedure for adding the optical cross connect OXC and repeating the operation of adding an optical fiber is as follows.
(a) Add a specified number of optical cross-connects OXC,
(b) For i = 1,2, ..., P, the number of paths (bi) that cannot be set for the demand pattern (Ti) is determined in order, and the required number and position of additional optical fibers. Seeking
(c) Obtain the total number of paths that could not be accommodated in each demand pattern, and if the total is greater than the number of paths calculated that cannot be accommodated with the predetermined tolerance, return to step (a) again. Continue processing, otherwise proceed to the next step to place the optical fibers included in the set,
The network configuration method according to claim 1 , comprising: In order to determine the addition of the predetermined number of optical cross-connects OXC using the ADD algorithm, the termination condition is that “the constructed network has resistance against traffic fluctuation” and that each optical cross-connect OXC is arranged. Of the optical cross-connect OXC placed in the period n using the “maximum flow of the node pair with the smallest predicted value (denominator) ratio of the maximum flow (numerator) vs. traffic” as the criterion for determining the location to be 3. The network configuration method according to claim 1, wherein the network configuration method is determined so as to minimize the cost (Cn). The addition of the optical fiber is as follows: (1) If there is demand between any pair of nodes in the future, add the fiber appropriately so as to leave the unused ports of the optical cross-connect OXC evenly so that new resources can be added to secure free resources. (2) For resources that have already been placed, route the optical path using wavelengths that have as much free space as possible so that free resources remain even if demand occurs between any pair of nodes. The network configuration method according to claim 1 , wherein a maximum amount of traffic that can be accommodated is realized by processing. The optical path routing processing is performed by providing a network in which all optical cross-connects OXC and optical fibers are partially connected as a physical topology, and creating a hierarchical graph based on the physical topology. The network configuration method according to claim 4 , wherein the shortest path obtained above is an optical path.

Images