(57)【特許請求の範囲】
【請求項１】
定期的に設備を拡張しながらWDM ネットワークを構築するネットワーク構成方法において、
前年度の推定したトラヒックと収容すべきトラヒックとの誤差をもとに、所定年度に要求されるトラヒックの平均を推定して、複数種類数（P）のトラヒックのデマンドパターンを作成し、
前記複数種類数（P）のデマンドパターンの所定割合（ｘ）を収容してWDM ネットワークがトラヒック変動に対する耐性を備えるまで、光クロスコネクトOXC の追加を行い、そして、光ファイバの追加を行う操作を繰り返して、推定したトラヒックと異なるトラヒックのデマンドパターンがあっても多くのデマンドを収容可能にし、
前記デマンドパターンとして、拡張期間をN 年として、n = 1,2,…,N に対して、予測n 年目のデマンドの総量（Dn）を予測し、かつ該総量（Dn）に対して前記複数種類数（P）のデマンドパターンを発生させ、
前記デマンドの総量（Dn）に前記所定割合（ｘ）及びデマンドのパターン種類数（Ｐ）を乗じた値（xDnP）の光パスを設定できるまで、所定数の光クロスコネクトOXC を追加し、かつ、光ファイバの追加を行う操作を繰り返す、
ことから成るWDM ネットワークを構築するネットワーク構成方法。
【請求項２】
前記光クロスコネクトOXC を追加し、かつ、光ファイバの追加を行う操作を繰り返す手順は、
(a)所定数の光クロスコネクトOXC を追加し、
(b)i = 1,2,…,P に対して、順に、デマンドパターン（Ti） に対して、設定できないパス数（bi） を求めると共に、追加する光ファイバの必要な数及び必要な位置を求め、
(c)それぞれのデマンドパターンにおいて収容できなかったパス数の総計を求め、該総計が、予め定めた耐性では収容できないと計算されたパス数よりも多いならば、再び手順(a) に戻って処理を続け、そうでなければ、次の手順に進んで、集合に含まれている光ファイバを配置する、
ことからなる請求項１に記載のネットワーク構成方法。
【請求項３】
前記所定数の光クロスコネクトOXC の追加をADDアルゴリズムを用いて決定するために、その終了条件として「構築したネットワークがトラヒック変動に対する耐性を備える」ことを用い、かつ、各光クロスコネクトOXC を配置する場所を決定するための基準として「最大流（分子）対トラヒックの予測値（分母）比が最も小さいノードペアの最大流が最も増加する」ことを用いて期間n に配置した光クロスコネクトOXC のコスト（Cn）の最小化を図るように決定する請求項１又は２に記載のネットワーク構成方法。
【請求項４】
前記光ファイバの追加は、(1) 将来どのノードペア間でデマンドが発生しても新たにファイバを追加して空き資源を確保できるよう光クロスコネクトOXC の空きポートを均等に残すよう適切にファイバを追加し、また、(2) すでに配置した資源に対しては、どのノードペア間でデマンドが発生しても空き資源が残るように、なるべく多くの空きがある波長を用いて光パスのルーティングを行なう処理により、収容可能なトラヒック量の最大化を実現する請求項１〜３のいずれかに記載のネットワーク構成方法。
【請求項５】
前記光パスのルーティングを行う処理は、すべての光クロスコネクトOXC と光ファイバが部分的に接続されているネットワークを物理トポロジーとして与えて、該物理トポロジーをもとに階層グラフを作成し、階層グラフ上で求めた最短経路を光パスとする請求項４に記載のネットワーク構成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、定期的に設備を拡張しながら、低コストのWDM ネットワークを構築するネットワーク構成方法に関する。
【０００２】
【従来の技術】
次世代インターネットの基幹における基盤技術としてWDM(Wavelength Division Multiplexing) 技術の適用が有望視されている。WDMは、一本の光ファイバに複数の波長を多重し、並列にデータを伝送することによって大容量通信を実現する光技術である。WDM ネットワークにおいて発生するトラヒックは、光信号に変調され、送受信ノードペア間において設定された光パス上を流れる。光パスとは、トラヒックの送信ノードから受信ノードまで特定の波長を用いて設定される帯域固定のチャネルである。光パスの設定は、中継ノードに配置された光クロスコネクトOXC (Optical Cross Connect) の入出力を適切に切替えることで行える。光パス上では光電気変換は行われず、トラヒックは光信号のまま受信ノードへ到達する（非特許文献１参照）。
【０００３】
トラヒックの発生に対して光パスを設定するためには、十分に波長資源のあるネットワークを予め構築しておく必要がある。構築にかかるファイバ、ノードなどの設備コストを最小化するために、さまざまな研究がなされてきた（非特許文献２〜４参照）。それらの実際の適用方針はいろいろ考えられるが、例えば、(1) 10 年先のトラヒック量を予測し、すべてに光パスを設定するために必要な設備量を求める、(2) 単年ごとにトラヒック量を予測し、段階的に設備を増やす、などが考えられる。ところが、近年のアクセスサービスの高速化、高速アプリケーションの登場などで、インターネットを流れるトラヒックは飛躍的に増加していることはわかっても、サービスの広域化やアプリケーションの使用形態などを把握することは難しい。つまり、ネットワーク内のトラヒック量の伸びは予測できても、各トラヒックの発生場所を正確に予測することは難しい。また、光技術の進展により、ノードコストの減少はじゅうぶん考えられることであり、10 年先のトラヒック収容のために、高価な設備を用意しておくのは現実的ではない。したがって、(1) への適用は難しい。実際には、数倍のトラヒックが発生すると想定して最適化を行うことになる。それでも、すべてのトラヒックを収容できるとは限らない。
【０００４】
最近、光ネットワークを長期にわたり定期的に拡張する設計手法も提案されつつある（非特許文献５及び６参照）。しかし、これらにおいても、将来発生するトラヒック量を予測し、ネットワーク設備コストが最小になるように設備を配置する手法を提案している。しかし、先述のように、トラヒック量の変化／増加を正確に予測することは単年に限っても困難で、すべてのトラヒックを収容できるとは限らない。
【０００５】
一方で、なるべく多くのトラヒックを収容するというアプローチは可能である。その場合には、どんなトラヒックが発生しても、より多くのトラヒックを収容する柔軟なネットワークを低コストで構成することが望ましい。
【０００６】
将来において要求されるトラヒック量が不確定な状況において、将来収容可能なトラヒック量の最大化を目指した経路決定アルゴリズムMIRA (Minimum Interference Routing Algorithm) およびMOCA (Minimum Open Capacity Routing Algorithm) が提案されている（非特許文献７及び８参照）。これらは、将来要求されるトラヒックが未知である状況で、次々と離散的に到着するトラヒック要求に対して最短経路を求めるオンラインアルゴリズムであり、MPLS (Multi-Protocol Label Switching) ネットワーク、GMPLS (Generalized MPLS) ネットワークにおけるLSP (Label Switched Path) の設定などに用いることが可能である。MIRAでは、ある送受信ノードペア間に設定する経路を求める際に、将来他の送受信ノードペアが要求するパスが設定される可能性があるリンクを求め、なるべくそれらの邪魔にならない経路を選択する。その結果、将来において収容可能なトラヒック量の最大化を実現する。例えば、図２のようなネットワークトポロジーにおいて(S1、D1)、(S2、D2)、(S3、D3) の3 送受信ノードペアがあり、各リンクでは1 波長のみが利用可能であるとする。ノードペア(S3、D3) でトラヒック要求が発生した場合、従来の経路決定アルゴリズムの一つであるMIN-HOPアルゴリズム（すべてのリンクコストを1 とした最短経路を解とする方法）を用いると、光パスの経路は1 - 7 - 8 - 5 となる。しかし、(S3、D3) がリンク(7、 8) を用いることにより送受信ノードペア(S1、D1) や(S2、D2) で要求されるトラヒックに対する光パスが設定できなくなる。MIRA はこの問題を解消するために、適切なリンクコストを設定し、ホップ数が大きい経路1 - 2 - 3 - 4 - 5 を選択する。
【０００７】
MIRA は、ある送受信ノードペアでパス設定要求が発生すると、将来他の送受信ノードペアが要求するパスの設定を邪魔しない経路を選択するために、他の送受信ノードペアのCritical Linkをなるべく通らない経路を選択し、パスを設定する。Critical Link とは、他の送受信ノードペアの光パスへの使用により、ある送受信ノードペアの最大流が減少するリンクを指す。Critical Link は送受信ノードペアごとに定義される。ここで、送受信ノードペアの最大流は、その送受信ノードペアが空き資源を用いて設定可能な光パスの集合である。MIRA では各リンクのコストに、そのリンクをCritical Link とする送受信ノードペア数(式(1)) を用いて最短経路を導出し、その最短経路にパスを設定している。
【０００８】
Costij = Aij                    (1)
【０００９】
【数１】
0003677550.tif 000002
【００１０】
Aij : リンクi の波長j をCritical Link とする送受信ノードペアの数
【００１１】
【数２】
0003677550.tif 000003
【００１２】
送受信ノードsd 間の最大流がリンクi の波長j を通っているならば1、そうでなければ0
【００１３】
【数３】
0003677550.tif 000004
【００１４】
送受信ノード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) それぞれのデマンドパターンにおいて収容できなかったパス数の総計、即ち、
【００２８】
【数４】
0003677550.tif 000005
【００２９】
を求める。それぞれのデマンドパターンにおいて収容できなかったパス数の総計が、予め定めた耐性では収容できないと計算されたパス数よりも多いならば、即ち、
【００３０】
【数５】
0003677550.tif 000006
【００３１】
であれば、制約を満たさないので、再びステップ(2-a) に戻り、処理を続ける。そうでなければ、即ち、
【００３２】
【数６】
0003677550.tif 000007
【００３３】
なら次のステップ(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) を生成する。これらＰ個のトラヒックマトリックスの各要素ｔijk (1 ≦ k ≦ ｐ)は正規分布N（μij，σij2）に従う。σは各ノードペア間の要求トラヒックの変動の幅の大きさを表すマトリックスである。各要素σ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.  TL、 α をもとに今期間のトラヒックの予測値μij を求める。
μij = α ×μij’(μij’ はTLの要素)
TL : 前期間のトラヒックパターンを表すトラヒックマトリックス。
α : 今期間のトラヒック量と前期間のトラヒック量の比を表す。
2.  μij，σij をもとにＰ個のトラヒックパターンを生成する。各トラヒックパターンの要素ｔijk（１≦ｋ≦ｎ）の値の範囲は。-∽ < ｔijk < ∽となる。なお、| ｔijk−μij |≦ σij となる確率は68.3%、|ｔijk≦−μij |≦ 2 × σij となる確率は95.5%である。
【００４６】
ネットワーク設計法
前述したネットワーク設計手法において、将来発生するトラヒック量が未知である状況において収容可能なトラヒック量の最大化を目的としたMIRA を光パス設定アルゴリズムとして用いることは可能である。しかし、MIRA はファイバ数も含めた物理トポロジーが与えられた上で、発生したトラヒックを収容する経路を求める方法であるゆえ、予めファイバをノードに接続しておかねばならない。一方、ノード構成を与え、ファイバを適切に追加していけばより多くのトラヒックを収容できると期待されるが、MIRA はそれに適していない。そこで、MIRAを拡張し、光パス経路を決定しつつ光ファイバを適切に追加することによりトポロジーを設計するEMIRA を提案する。
【００４７】
EMIRA では、すべての光クロスコネクトOXC と光ファイバが部分的に接続されているネットワークを物理トポロジーとして与える。光クロスコネクトOXCポートに空きがあれば光ファイバを追加接続できる。EMIRA では(1) 将来どのノードペア間でデマンドが発生しても新たにファイバを追加して空き資源を確保できるよう光クロスコネクトOXC の空きポートを均等に残すよう適切にファイバを追加し、また、(2) すでに配置した資源に対しては、どのノードペア間でデマンドが発生しても空き資源が残るように、なるべく多くの空きがある波長を用いて光パスのルーティングを行っている。そのようなルーティングを行うために、EMIRA では、物理トポロジーをもとに階層グラフ（非特許文献９参照）を作成し、階層グラフ上で求めた最短経路を光パスとする。階層グラフは波長ごとに異なる階層を構成しており、頂点はノードに、辺はそのリンク上の波長に対応している。こうした処理により、収容可能なトラヒック量の最大化を実現する。
【００４８】
階層グラフ自体は周知であるが（非特許文献９参照）、以下、これについて図４及び図５を参照して説明する。図４は物理トポロジーで、Nkはノード、Lkは光ファイバを表す。ノードは実際に複数のクロスコネクトで構成され、また、光ファイバにも波長ごとに異なる信号が流れているので、図４を用いるだけでは、どの経路（通過するクロスコネクトと波長の集合）をとおってデータを送るかを決めることは難しい。そこで、図５のように、ノードと光ファイバを各要素に分解する。これが階層グラフである。
【００４９】
以下に、階層グラフ表記のための記号を導入する。
(1)  階層グラフはＷ層からなる。第ｋ層はｋ番目の波長（λk）に相当する。
(2)  各ノードＮiはＷ個の入力ノード、Ｗ個の出力ノードに分解される。これらは、
【００５０】
【数７】
0003677550.tif 000008
【００５１】
と表される。
(3)もし、波長λkからλiへの変換がノードＮiで許されるならば、第ｋ層と第ｉ層を接続する有向辺Ｗikiが存在する。
(4)有向リンクＬjはＷ本の辺に分解される。これらの辺は、ｅj1，ｅj2，・・・，ｅjW と表される。
【００５２】
上記説明において分解されてできるW個の入力ノード、W個の出力ノードとは、W個のクロスコネクトを示している。以降のコストCostijが、eij のコストに相当する。その際、wiklのコストは0である。
【００５３】
EMIRA におけるリンクのコスト
EMIRA ではリンクコストとして、Critical Link のみでなく空いているポート数および波長数を基にした、以下の式(3) を用いる。
【００５４】
Costij ＝ Aij/(Bi+Cij)                     (3)
Bi: リンクi の上流ノードの空き出力ポート数と、下流ノードの光クロスコネクトOXC の空き入力ポート数の小さい方の値
Cij : リンクi において、既に配置されたファイバ上で利用可能な波長j の数
Bi の導入により、経路を選択する際に空きポート数の多い経路が優先され、空きポート数が少ないリンクへのファイバ追加の可能性を残しやすくなる。後にそのリンクを通るパスを設定できるので、収容可能なトラヒック量が大きくなることが期待できる。また、Cij の導入により、既に設定されたファイバ上で利用可能な波長が多い経路を優先することにより、新たにファイバを設定する経路よりも既存のファイバを用いる経路を選択しやすくなる。すなわち、Bi の導入と同様に、収容可能なトラヒック量が大きくなることが期待できる。このように、空きポート数が多く、かつ既に設定されたファイバ上において利用可能な波長数が多い波長を選択しやすくすることで、さまざまなデマンドの発生に備えることができる。
【００５５】
EMIRA アルゴリズム
EMIRA では、デマンドの集合それぞれに対し、以下のアルゴリズムを適用し、光パス経路および追加するファイバの場所および数を決定する。以下、EMIRA への入出力を示す。
入力
・階層グラフ
・ 送信ノードs、受信ノードd および要求する光パス数
出力
・ s からd へ光パスを設定する経路、および、光パスに用いる波長
・ 光ファイバを追加する場所、および、数
【００５６】
次に、EMIRA のアルゴリズムを以下に述べる。
(1) 送受信ノードペア(s、 d) 以外の送受信ノードペアそれぞれについて最大流（現在のネットワークの空き資源を用いて送受信ノード間に設定できる最大の光パス数）を求める。
(2) 送受信ノードペア(s、 d) 以外の送受信ノードペアそれぞれについてCritical Link を求め、各リンクのAij の値を求める。
(3) 各ノードi の光クロスコネクトOXC の空きポート数(Bi) を求める。
(4) 各リンクi に配置されたファイバ上におけるそれぞれの波長j が空いている数(Cij ) を求める。
(5) Aij、Bi、Cij の値を式(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 とした場合も同様の結果が得られた。
【００６０】
Costij2 ＝ Aij/(Bi+c・Cij)            (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 において最初に呼損がおきるまでの光パス設定要求回数に対して光パスを設定するために用いた光ファイバ数を示す図である。
【図１】
0003677550.tif 000009
【図２】
0003677550.tif 000010
【図３】
0003677550.tif 000011
【図４】
0003677550.tif 000012
【図５】
0003677550.tif 000013
【図６】
0003677550.tif 000014
【図７】
0003677550.tif 000015
【図８】
0003677550.tif 000016
【図９】
0003677550.tif 000017