(57)【特許請求の範囲】
【請求項１】
複数のノードと、該ノード間ｋを結ぶリンクと、該複数のリンクにより形成された複数の仮想リングｒと、該仮想リング毎に割り当てられる波長λとを有する光波長多重網の波長割当方法であって、
前記多重網で必要とされる前記波長λの数を最小にするために、
前記仮想リングを点とし、該点の重みを該仮想リングに収容されるコネクション数ｘrとし、該仮想リング間のリンクの共有を枝とするグラフを導出し、該グラフの各クリークｃに属する点の重みの総和Ｄの最大値Ｄmaxを最小化するために、線形計画法を用いて、全ての前記クリークの重みＤが、前記クリークの重みの最大値Ｄmax以下であるという資源制約と、前記ノード間ｋのコネクション数ｘkrが、全てのノード間ｋの需要コネクション数ｄk以上であるという需要制約と、の条件を満たすコネクション数ｘkrを導出する第１の段階と、
前記コネクション数ｘkrを用いて、前記コネクションを収容した前記仮想リングに対して使用する波長の数を最小化するために、線形計画法を用いて、前記リンクを経由する複数の前記仮想リングのうち同一波長を割り当て可能な仮想リングは高々１個であるという資源制約と、各仮想リングに収容されたコネクションに対して波長を割り当てなければならないという需要制約と、波長λの利用可否制約と、の条件を満たす波長が割り当てられる第２の段階とを有することを特徴とする光波長多重網の波長割当方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、仮想リングを有する光波長多重網の波長割当方法に関する。
【０００２】
【従来の技術】
従来、ギガからテラビットクラスの伝送容量を持つ広帯域な光波長多重網の構築にあたっては、ノード又はリングで発生する障害が問題となっていた。そのために、広帯域な光波長多重網の設計方式として、障害発生時のレストレーション・光クロスコネクトを必要としない網構成の簡易さの点から、リング構成に基づくセルフヒーリング(Self-Healing Ring : SHR)網が実用化されている。
【０００３】
大規模な光波長多重網の構築にあたっては、単一リング構成ではなく、任意のノード間に光ファイバリンクが接続される網構成が多数である。このような構成の網では、障害発生時の対策として、クロスコネクト装置による電気段又は光段におけるパス切り替えが主流である。
【０００４】
しかし、最近では、設備コストの最小化の点から、仮想リング(Virtual Multi Self-healing Ring：VM-SHR)を用いて耐障害性を備える方法が提案されている。
【０００５】
仮想リングを有する光波長多重網とは、複数のノードと、該ノード間を結ぶリンクと、該複数のリンクにより形成された複数の仮想リングと、該仮想リング毎に割り当てられている波長とを有する通信網をいう。また、仮想リングとは、ノードの始点と終点とが等しく、連続するノード間のリンクを経由し、始点及び終点以外では同一ノードが現われないリストをいう。
【０００６】
図１は、仮想リング構成に基づくセルフヒーリングを説明する構成図である。大規模な光波長多重網について、ノード間を結ぶコネクションが与えられ、そのコネクションに需要コネクションを収容する場合を考える。
【０００７】
コネクションとは、１個の波長によって提供される光コネクションを単位としたものである。従って、いずれのコネクションも、与えられた仮想リングのいずれかに収容可能であるとする。
【０００８】
通常、最初に、この多重網の顧客を募り、各ノード間に要求される需要コネクションを調べる。次に、このネットワークトポロジと需要コネクションに対し、仮想リングを用いた最適な収容を検討する。ネットワーク制御センタの下で、コネクションが収容された仮想リング上を、割り当てられた波長を用いて伝送が行われる。
【０００９】
図１の上図のように、仮想リング上の可能な２つの経路の一方又は両方を用いて伝送が行われる。障害発生時は、図１の下図のように、障害リンクを経由しない経路を用いて伝送が行われる。従って、最初に最適な需要コネクションの収容を行うことにより、障害発生時においても、収容状態を変更する必要はなく、またネットワーク資源が新たに要求されることもない。IP over WDM等の光波長多重技術を用いたネットワークが急速な発展を続けていることから、耐障害性を備える仮想リングの手法の適用範囲は、ますます広がっている。
【００１０】
【発明が解決しようとする課題】
しかしながら、大規模な光波長多重網においては、物理層における有限な資源である波長を、効率的に割り当てるように設計する必要がある。これまで、多重網について効率的なコネクションの収容を提案する設計方法は提案されていなかった。また、障害発生時には、需要コネクションを収容する経路の変更と、波長の再割当との計算に膨大な時間がかかり、迅速なコネクション及び波長の再配置が期待できなかった。
【００１１】
また、ノードにおいて波長変換を行うことにより、網全体のコネクションの収容と波長の割り当てとの問題を回避することもできるが、その方法は、ノードにおけるコストの増大を招くことになる。
【００１２】
そこで、本発明は、簡易な障害レストレーション機能を実現し、且つノードにおけるコストの増大を避けるために、仮想リングを有する光波長多重網について、１個のコネクションには同一の波長を割り当て、最適なコネクションの収容と波長の割り当てとを実現する方法を提供することを目的とする。
【００１３】
【課題を解決するための手段】
そこで、本発明の光波長多重網の波長割当方法は、多重網で必要とされる波長λの数を最小にするために、
仮想リングを点とし、該点の重みを該仮想リングに収容されるコネクション数ｘrとし、該仮想リング間のリンクの共有を枝とするグラフを導出し、該グラフの各クリークｃに属する点の重みの総和Ｄの最大値Ｄmaxを最小化するために、線形計画法を用いて、全てのクリークの重みＤが、クリークの重みの最大値Ｄmax以下であるという資源制約と、ノード間ｋのコネクション数ｘkrが、全てのノード間ｋの需要コネクション数ｄk以上であるという需要制約と、の条件を満たすコネクション数ｘkrを導出する第１の段階と、
コネクション数ｘkrを用いて、コネクションを収容した仮想リングに対して使用する波長の数を最小化するために、線形計画法を用いて、リンクを経由する複数の仮想リングのうち同一波長を割り当て可能な仮想リングは高々１個であるという資源制約と、各仮想リングに収容されたコネクションに対して波長を割り当てなければならないという需要制約と、波長λの利用可否制約と、の条件を満たす波長が割り当てられる第２の段階とを有することを特徴とする。即ち、本発明は、需要コネクションの収容効率の評価値として、使用する波長の総数を考慮し、その最小化を図るものである。光波長多重の前提条件として、互いにリンクを共有する異なる仮想リングにはそれぞれ異なる波長を割り当てなければならない。
【００１６】
【発明の実施の形態】
以下では、図面を用いて、本発明の実施形態を詳細に説明する。
【００１７】
図２は、対象となる光波長多重網におけるネットワークトポロジの構成図である。そのネットワークトポロジは、８個のノードと、各ノード間を結ぶ１０個のリンクと、該リンクにより形成された６個の仮想リングとを有する。各リンクは、１対の光ファイバペア（順方向にデータを送信する光ファイバと、逆方向にデータを送信する光ファイバのペア）のみで構成されている。また、リンクを共有する複数の仮想リングには、それぞれ異なる波長が割り当てられなければならない。
【００１８】
また、障害レストレーションの簡易性のため、障害発生時の迂回経路でも波長を変えずに元の経路と同じ波長を割り当てるため、１個のコネクションは、1個の仮想リングの１波長を占有する。従って、ある仮想リングに収容されたコネクションにある波長が割り当てられた場合、その仮想リングとリンクを共有する他の仮想リングに収容されたコネクションは、その波長を使用することができない。
【００１９】
本発明は、仮想リングへのコネクション収容及び波長割当の問題を、グラフの彩色問題に対応させて定式化し、線形計画法を用いて解くものである。従って、本発明は、多重網で必要とされる波長λの数を最小にするために、ネットワークトポロジからグラフを導出し、該グラフの各クリークｃに属する点の重みの総和Ｄの最大値Ｄmaxが最小となるようにコネクションを収容し、仮想リングｒに収容されるノード間ｋのコネクション数ｘkrを導出する第１の段階と、コネクション数ｘkrを用いて、コネクションを収容した仮想リングに対して使用する波長の数を最小化するように波長割当を行う第２の段階とを有する。
【００２０】
各段階を説明するために、以下のパラメータを用いる。
ネットワークトポロジ：Ｇ＝（Ｖ，Ｅ）
ｉ：ノードIndex
Ｖ：ノード集合
ｊ：リンクIndex
λ：波長Index
Λ：波長集合
ノード間需要
ｋ：ＳＤペアIndex（Source-Destinationペアとはノード間を意味）
Ｋ：ＳＤペア集合
ｄk：ＳＤペアｋに与えられた需要（コネクション数）
仮想リング集合
ｒ：仮想リングIndex
Ｒ：候補仮想リング集合
Ｒk：ＳＤペアｋの需要に対する候補仮想リング集合
Ａjr：候補仮想リングｒとリンクｊの収容関係
Ａjr＝１：候補仮想リングｒにリンクｊが含まれる
Ａjr＝０：候補仮想リングｒにリンクｊが含まれない
ｃ：クリークIndex
Ｃ：クリーク集合
Ｉcr：クリークｃと仮想リングｒに対応する点の収容関係
Ｉcr＝１：クリークｃに仮想リングｒの点が含まれる
Ｉcr＝０：クリークｃに仮想リングｒの点が含まれない
【００２１】
そして、以下の決定変数を導き出す。
Ｄmax：使用波長数の最大値、即ち必要波長数の下限値（最大クリークの重み）
ｘkr：コネクションのルーティング、即ち仮想リングｒに収容される、ＳＤペアｋのコネクションの数
ｙrλ：コネクションへの波長割当、即ち仮想リングｒに収容されたコネクションのうち波長λの割り当てを行うコネクション数
Ｚλ：波長の既使用又は未使用の判定
Ｚλ＝１：網の１ヶ所以上で波長λが使用されている
Ｚλ＝０：網のどこでも波長λが使用されていない
【００２２】
最初に、コネクションを収容する第１の段階について説明する。
【００２３】
１個の仮想リングに割り当てる波長数は、その仮想リングに収容されるコネクション数以上にしなければならない。従って、１個の仮想リングに収容されるコネクション数の最大値が、波長割当において必要となる波長数の下限値となる。必要となる波長数を最小化するために、波長割当の前に、１個の仮想リングに収容されるコネクション数が最小となるように、コネクションの収容を行う。即ちＤmaxの値を最小化にするようなｘkrを求める。
【００２４】
図３は、図２のネットワークトポロジに対応する彩色問題のグラフである。図２のトポロジと、図３のグラフとの間には、以下のような関係がある。
【００２５】
図３は、図２の仮想リングを点とし、該点の重みを該仮想リングに収容されるコネクション数とし、該仮想リング間のリンクの共有を枝とするグラフである。図３では、以下の８個のクリークが存在することが分かる。
点１−点２−点３、点１−点３−点５、点１−点５−点６、点１−点６−点２、点４−点２−点３、点４−点３−点５、点４−点５−点６、点４−点６−点２
【００２６】
１個のクリークｃを構成する点（仮想リング）の重み（収容コネクション数）の総和は、このクリークの点を塗り分ける（波長割当する）のに最低限必要な色数（波長数）を示す。各クリークについてそのクリークを構成する点の重みの総和（以下、「クリークの重み」と称す）を求め、その値が最大となるクリーク（以下、「最大クリーク」と称す）の塗り分けに必要な色数（波長数）が、グラフＧ全体で最低限必要な色数（必要波長数の下限値）である。そこで、必要な色数を最小化するために、最大クリークの重みを最小化するように、グラフＧの各点の重み付け（コネクション収容）を行う。
【００２７】
第１の段階は、全てのクリークの重みＤが、クリークの重みの最大値Ｄmax以下であるという資源制約と、ノード間ｋのコネクション数ｘkrが、全てのノード間ｋの需要コネクション数ｄk以上であるという需要制約との条件を満たすコネクション数ｘkrを導出する。第１の段階で定式化された線形計画問題を以下に示す。
【００２８】
最小化：Ｄmax
（各クリークｃに属する点の重みの総和Ｄの最大値Ｄmaxを最小にする）
資源制約：
【数１】
0003671804.tif 000002
資源制約：
【数２】
0003671804.tif 000003
【００２９】
次に、波長を割り当てる第２の段階について説明する。
【００３０】
第２の段階は、コネクションを収容した仮想リングに対し使用波長数を最小化する波長割当を行い、各仮想リングで使用する波長を求める。この段階は、リンクを経由する複数の仮想リングのうち同一波長を割り当て可能な仮想リングは高々１個であるという資源制約と、各仮想リングに収容されたコネクションに対して波長を割り当てなければならないという需要制約と、波長λの利用可否制約との条件を満たすように、波長が割り当てられる。第２の段階で定式化されたこの線形計画問題を以下に示す。
【００３１】
最小化：
【数３】
0003671804.tif 000004
（使用する波長の数を最小にする）
資源制約：
【数４】
0003671804.tif 000005
資源制約：
【数５】
0003671804.tif 000006
波長λの利用可否制約：
【数６】
0003671804.tif 000007
【００３２】
このように、本発明は、仮想リングへのコネクション収容及び波長割当の問題を、グラフの彩色問題に対応させて定式化し、線形計画法を用いて解く方法を提案している。
【００３３】
以上、詳細に説明した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【００３４】
【発明の効果】
従って、本発明の仮想リングを有する光波長多重網によれば、最適なコネクションの収容と波長の割り当てとが実現できる。また、１個のコネクションには同一の波長を割り当てることによってノードにおけるコストの増大を避けることもできる。更に、仮想リングによって簡易な障害レストレーション機能が実現されており、障害時にも再度のコネクション収容又は波長割当を行う必要もない。
【図面の簡単な説明】
【図１】仮想リング構成に基づくセルフヒーリングを説明する構成図である。
【図２】対象となる光波長多重網におけるネットワークトポロジの構成図である。
【図３】図２のネットワークトポロジに対応する彩色問題のグラフである。
【図１】
0003671804.tif 000008
【図２】
0003671804.tif 000009
【図３】
0003671804.tif 000010