JP3671804B2

JP3671804B2 - Wavelength allocation method for optical wavelength division multiplexing network with virtual ring

Info

Publication number: JP3671804B2
Application number: JP2000060848A
Authority: JP
Inventors: 彰夫石川; 洋司岸
Original assignee: KDDI Corp
Current assignee: KDDI Corp
Priority date: 2000-03-06
Filing date: 2000-03-06
Publication date: 2005-07-13
Anticipated expiration: 2020-03-06
Also published as: JP2001251315A

Description

【０００１】
【発明の属する技術分野】
本発明は、仮想リングを有する光波長多重網の波長割当方法に関する。
【０００２】
【従来の技術】
従来、ギガからテラビットクラスの伝送容量を持つ広帯域な光波長多重網の構築にあたっては、ノード又はリングで発生する障害が問題となっていた。そのために、広帯域な光波長多重網の設計方式として、障害発生時のレストレーション・光クロスコネクトを必要としない網構成の簡易さの点から、リング構成に基づくセルフヒーリング(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を最小にする）
資源制約：
【数１】

資源制約：
【数２】

【００２９】
次に、波長を割り当てる第２の段階について説明する。
【００３０】
第２の段階は、コネクションを収容した仮想リングに対し使用波長数を最小化する波長割当を行い、各仮想リングで使用する波長を求める。この段階は、リンクを経由する複数の仮想リングのうち同一波長を割り当て可能な仮想リングは高々１個であるという資源制約と、各仮想リングに収容されたコネクションに対して波長を割り当てなければならないという需要制約と、波長λの利用可否制約との条件を満たすように、波長が割り当てられる。第２の段階で定式化されたこの線形計画問題を以下に示す。
【００３１】
最小化：
【数３】

（使用する波長の数を最小にする）
資源制約：
【数４】

資源制約：
【数５】

波長λの利用可否制約：
【数６】

【００３２】
このように、本発明は、仮想リングへのコネクション収容及び波長割当の問題を、グラフの彩色問題に対応させて定式化し、線形計画法を用いて解く方法を提案している。
【００３３】
以上、詳細に説明した本発明の種々の実施形態について、本発明の技術思想及び見地の範囲の種々の変更、修正及び省略は、当業者によれば容易に行うことができる。前述の説明はあくまで例であって、何ら制約しようとするものではない。本発明は、特許請求の範囲及びその均等物として限定するものにのみ制約される。
【００３４】
【発明の効果】
従って、本発明の仮想リングを有する光波長多重網によれば、最適なコネクションの収容と波長の割り当てとが実現できる。また、１個のコネクションには同一の波長を割り当てることによってノードにおけるコストの増大を避けることもできる。更に、仮想リングによって簡易な障害レストレーション機能が実現されており、障害時にも再度のコネクション収容又は波長割当を行う必要もない。
【図面の簡単な説明】
【図１】仮想リング構成に基づくセルフヒーリングを説明する構成図である。
【図２】対象となる光波長多重網におけるネットワークトポロジの構成図である。
【図３】図２のネットワークトポロジに対応する彩色問題のグラフである。[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a wavelength allocation method for an optical wavelength division multiplexing network having a virtual ring.
[0002]
[Prior art]
Conventionally, in the construction of a broadband optical wavelength division multiplexing network having a transmission capacity of giga to terabit class, a failure occurring in a node or ring has been a problem. For this reason, as a design method for a broadband optical wavelength division multiplexing network, self-healing ring (SHR) based on a ring configuration is used because of the simplicity of network configuration that does not require restoration and optical cross-connect in the event of a failure. ) The net is put into practical use.
[0003]
In the construction of a large-scale optical wavelength division multiplexing network, there are many network configurations in which optical fiber links are connected between arbitrary nodes instead of a single ring configuration. In a network with such a configuration, path switching at the electrical stage or optical stage by a cross-connect device is the mainstream as a countermeasure when a failure occurs.
[0004]
However, recently, from the viewpoint of minimizing the equipment cost, a method having fault tolerance using a virtual ring (Virtual Multi Self-healing Ring: VM-SHR) has been proposed.
[0005]
An optical wavelength division multiplexing network having a virtual ring includes a plurality of nodes, links connecting the nodes, a plurality of virtual rings formed by the plurality of links, and wavelengths assigned to the virtual rings. It means a communication network. A virtual ring is a list in which the start point and end point of a node are equal, and the same node does not appear except for the start point and end point via a link between successive nodes.
[0006]
FIG. 1 is a configuration diagram illustrating self-healing based on a virtual ring configuration. Consider a case where a connection between nodes is given for a large-scale optical wavelength division multiplexing network, and a demand connection is accommodated in the connection.
[0007]
A connection is a unit of optical connection provided by one wavelength. Accordingly, it is assumed that any connection can be accommodated in any given virtual ring.
[0008]
Usually, first, customers of this multiple network are recruited, and demand connections required between the nodes are examined. Next, we consider the optimal accommodation using virtual rings for this network topology and demand connections. Under the network control center, transmission is performed using the assigned wavelength on the virtual ring in which the connection is accommodated.
[0009]
As shown in the upper diagram of FIG. 1, transmission takes place using one or both of the two possible paths on the virtual ring. When a failure occurs, transmission is performed using a route that does not go through the failure link as shown in the lower diagram of FIG. Therefore, by accommodating the optimal demand connection first, it is not necessary to change the accommodation state even when a failure occurs, and no new network resources are required. As networks using optical wavelength multiplexing technologies such as IP over WDM continue to develop rapidly, the scope of application of virtual ring methods with fault tolerance is expanding.
[0010]
[Problems to be solved by the invention]
However, in a large-scale optical wavelength division multiplexing network, it is necessary to design so that wavelengths, which are finite resources in the physical layer, are efficiently allocated. So far, no design method has been proposed for proposing efficient connection accommodation for multiple networks. In addition, when a failure occurs, it takes an enormous amount of time to calculate the change of the route that accommodates the demand connection and the reassignment of wavelengths, and a quick connection and relocation of wavelengths cannot be expected.
[0011]
Further, by performing wavelength conversion at the node, it is possible to avoid the problem of accommodation of connections and wavelength allocation of the entire network, but this method causes an increase in cost at the node.
[0012]
Therefore, the present invention assigns the same wavelength to one connection in an optical wavelength division multiplexing network having a virtual ring in order to realize a simple failure restoration function and avoid an increase in cost at a node. It is an object of the present invention to provide a method for realizing secure connection accommodation and wavelength allocation.
[0013]
[Means for Solving the Problems]
Therefore, the wavelength allocation method of the optical wavelength multiplexing network of the present invention is to minimize the number of wavelengths λ required in the multiplexing network.
Deriving a graph with a virtual ring as a point, the weight of the point as the number of connections x _r accommodated in the virtual ring, and sharing a link between the virtual rings as branches, and points belonging to each clique c of the graph In order to minimize the maximum value Dmax of the sum D of weights, a linear constraint is used, and the resource constraint that all clique weights D are equal to or less than the maximum value Dmax of clique weights, and k between nodes A first stage for deriving a demand constraint that the number of connections x _kr is equal to or greater than the number of demand connections d _k between all nodes k, and the number of connections x _kr satisfying the condition :
With the number of connections x _kr, assigned in order to minimize the number of wavelengths used for the virtual ring containing the connection, using the linear programming method, the same wavelength of the plurality of virtual ring over links Wavelength that satisfies the conditions of resource constraint that there is at most one virtual ring, demand constraint that wavelength must be assigned to connections accommodated in each virtual ring, and availability constraint of wavelength λ and having a second stage is assigned. That is, according to the present invention, the total number of wavelengths to be used is considered as an evaluation value of the accommodation efficiency of the demand connection, and is minimized. As a precondition for optical wavelength multiplexing, different wavelengths must be assigned to different virtual rings that share a link with each other.
[0016]
DETAILED DESCRIPTION OF THE INVENTION
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
[0017]
FIG. 2 is a configuration diagram of a network topology in the target optical wavelength division multiplexing network. The network topology has 8 nodes, 10 links connecting the nodes, and 6 virtual rings formed by the links. Each link includes only one optical fiber pair (a pair of an optical fiber that transmits data in the forward direction and an optical fiber that transmits data in the reverse direction). In addition, different wavelengths must be assigned to a plurality of virtual rings sharing a link.
[0018]
In addition, for simplicity of failure restoration, the same wavelength as the original route is assigned to the detour route at the time of failure without changing the wavelength, so one connection occupies one wavelength of one virtual ring. . Therefore, when a certain wavelength is assigned to a connection accommodated in a certain virtual ring, a connection accommodated in another virtual ring sharing a link with that virtual ring cannot use that wavelength.
[0019]
The present invention formulates the problem of accommodating connections to a virtual ring and wavelength allocation in accordance with the coloring problem of a graph and solves it using linear programming. Therefore, the present invention derives a graph from the network topology in order to minimize the number of wavelengths λ required in the multiplex network, and the maximum value Dmax of the weight sum D of points belonging to each clique c of the graph. Is stored in the virtual ring r, the first stage of deriving the connection number x _kr between the nodes k accommodated in the virtual ring r, and the virtual ring containing the connection using the connection number x _kr And a second stage of assigning wavelengths so as to minimize the number of wavelengths used.
[0020]
The following parameters are used to describe each stage.
Network topology: G = (V, E)
i: Node Index
V: node set j: link Index
λ: Wavelength index
Λ: Wavelength set inter-node demand k: SD pair Index (Source-Destination pair means inter-node)
K: SD pair set d _k : Demand given to SD pair k (number of connections)
Virtual ring set r: Virtual ring Index
R: Candidate virtual ring set R _k : Candidate virtual ring set A _jr for demand for SD pair k A _jr : Containment relationship between candidate virtual ring r and link j A _jr = 1: Candidate virtual ring r includes link j A _jr = 0: Link j is not included in candidate virtual ring r c: Clique index
C: Creek set I _cr: receiving relationship point corresponding to the clique c and virtual ring _{_{r I cr = 1: I cr}} = 0 contains a point of the virtual ring r to Creek c: the clique c points of the virtual ring r Not included [0021]
And the following decision variables are derived.
Dmax: Maximum number of wavelengths used, that is, a lower limit value of the number of required wavelengths (maximum clique weight)
x _kr: connection routing, that is, housed in a virtual ring r, SD pair k number of connections y _r _lambda: performing a wavelength assignment to connections, i.e. the assignment of the wavelength lambda of the connections housed in the virtual ring r Number of connections Z _λ : Whether wavelength is used or not used Z _λ = 1: Wavelength λ is used at one or more places in the network Z _λ = 0: Wavelength λ is not used anywhere in the network
First, the first stage for accommodating connections will be described.
[0023]
The number of wavelengths allocated to one virtual ring must be greater than or equal to the number of connections accommodated in the virtual ring. Therefore, the maximum value of the number of connections accommodated in one virtual ring is the lower limit value of the number of wavelengths required for wavelength allocation. In order to minimize the number of required wavelengths, connections are accommodated so that the number of connections accommodated in one virtual ring is minimized before wavelength allocation. That is, x _kr that minimizes the value of Dmax is obtained.
[0024]
FIG. 3 is a graph of a coloring problem corresponding to the network topology of FIG. The following relationship exists between the topology of FIG. 2 and the graph of FIG.
[0025]
FIG. 3 is a graph in which the virtual ring of FIG. 2 is a point, the weight of the point is the number of connections accommodated in the virtual ring, and the link sharing between the virtual rings is a branch. In FIG. 3, it can be seen that the following eight cliques exist.
Point 1-Point 2-Point 3, Point 1-Point 3-Point 5, Point 1-Point 5-Point 6, Point 1-Point 6-Point 2, Point 4-Point 2-Point 3, Point 4-Point 3 -Point 5, Point 4-Point 5-Point 6, Point 4-Point 6-Point 2
[0026]
The sum of the weights (number of accommodated connections) of the points (virtual ring) constituting one clique c indicates the minimum number of colors (number of wavelengths) required to separately paint (assign wavelengths) the points of this clique. . For each clique, the sum of the weights of the points constituting the clique (hereinafter referred to as “clique weight”) is obtained, and it is necessary to separate the clique having the maximum value (hereinafter referred to as “maximum clique”). The number of colors (number of wavelengths) is the minimum number of colors required for the entire graph G (the lower limit value of the number of required wavelengths). Therefore, in order to minimize the number of necessary colors, each point of the graph G is weighted (connection accommodation) so as to minimize the weight of the maximum clique.
[0027]
In the first stage, the resource constraint that the weight D of all cliques is not more than the maximum value Dmax of the clique weight, and the number of connections x _kr between nodes k are the number of demand connections d _k between all nodes _k. The number of connections x _kr that satisfies the above-described demand constraint is derived. The linear programming problem formulated in the first stage is shown below.
[0028]
Minimization: Dmax
(The maximum value Dmax of the sum D of the weights of the points belonging to each clique c is minimized)
Resource constraints:
[Expression 1]

Resource constraints:
[Expression 2]

[0029]
Next, the second stage of assigning wavelengths will be described.
[0030]
In the second stage, wavelength allocation for minimizing the number of used wavelengths is performed for the virtual ring accommodating the connection, and the wavelength used in each virtual ring is obtained. At this stage, it is necessary to assign a wavelength to the connection accommodated in each virtual ring, and the resource restriction that at most one virtual ring that can be assigned the same wavelength among a plurality of virtual rings via a link is required. The wavelength is assigned so as to satisfy the requirements of the demand constraint and the availability constraint on the wavelength λ. This linear programming problem formulated in the second stage is shown below.
[0031]
Minimize:
[Equation 3]

(Minimize the number of wavelengths used)
Resource constraints:
[Expression 4]

Resource constraints:
[Equation 5]

Restriction on availability of wavelength λ:
[Formula 6]

[0032]
As described above, the present invention proposes a method of formulating the problem of accommodating connections to the virtual ring and wavelength allocation in accordance with the coloring problem of the graph and solving it using linear programming.
[0033]
As described above, various changes, modifications, and omissions of the technical idea and the scope of the present invention can be easily made by those skilled in the art with respect to the various embodiments of the present invention described in detail. The above description is merely an example, and is not intended to be restrictive. The invention is limited only as defined in the following claims and the equivalents thereto.
[0034]
【The invention's effect】
Therefore, according to the optical wavelength division multiplexing network having the virtual ring of the present invention, optimal connection accommodation and wavelength allocation can be realized. Further, by assigning the same wavelength to one connection, it is possible to avoid an increase in cost at the node. Furthermore, a simple fault restoration function is realized by the virtual ring, and it is not necessary to perform connection accommodation or wavelength allocation again even in the event of a fault.
[Brief description of the drawings]
FIG. 1 is a configuration diagram illustrating self-healing based on a virtual ring configuration.
FIG. 2 is a configuration diagram of a network topology in a target optical wavelength division multiplexing network.
FIG. 3 is a graph of a coloring problem corresponding to the network topology of FIG. 2;

Claims

A wavelength allocation method for an optical wavelength division multiplexing network having a plurality of nodes, a link connecting k between the nodes, a plurality of virtual rings r formed by the plurality of links, and a wavelength λ allocated to each virtual ring. There,
In order to minimize the number of wavelengths λ required in the multiplex network,
A graph with the virtual ring as a point, the weight of the point as the number of connections x _r accommodated in the virtual ring, and a link sharing between the virtual rings as branches is derived, and belongs to each clique c of the graph In order to minimize the maximum value Dmax of the sum D of point weights, using linear programming , a resource constraint that all the clique weights D are less than or equal to the maximum clique weight value Dmax ; A first stage of deriving the number of connections x _kr satisfying the demand constraint that the number of connections k _kr between the nodes is equal to or greater than the number of demand connections d _k between all the nodes k ;
In order to minimize the number of wavelengths used for the virtual ring accommodating the connection using the connection number x _kr , linear programming is used to determine the number of the virtual rings that pass through the link. Among them, the resource constraint that there is at most one virtual ring that can be assigned the same wavelength, the demand constraint that the wavelength must be assigned to the connection accommodated in each virtual ring, the availability constraint on the wavelength λ, And a second stage in which a wavelength satisfying the above condition is assigned .