Expand this Topic clickable element to expand a topic
Skip to content
Optica Publishing Group

Fast Exact ILP Decompositions for Ring RWA

Open Access Open Access

Abstract

Wavelength division multiplexing rings are now capable of supporting more than 100 wavelengths over a single fiber. Conventional link and path formulations for the routing and wavelength assignment problem are inefficient due to the inherent symmetry in wavelength assignment and the fact that the problem size increases fast with the number of wavelengths. Although a formulation based on maximal independent sets (MIS) does not have these drawbacks, it suffers from exponential growth in the number of variables with increasing network size. We develop a new ILP (integer linear program) formulation based on the key idea of partitioning the path set and representing the MIS in the original network using the independent sets calculated in each of these partitions. This exact decomposition trades off the number of variables with the number of constraints and, as a result, achieves a much better scalability in terms of network dimension. Numerical results on ring networks of various sizes demonstrate that this new ILP decomposition achieves a decrease of several orders of magnitude in running time compared to existing formulations. Our main contribution is a novel and extremely fast technique for obtaining, in a few seconds using commodity CPUs, optimal solutions to instances of maximum size SONET rings with any number of wavelengths; such instances cannot be tackled with classical formulations without vast investments in computational resources and time.

©2011 Optical Society of America

Full Article  |  PDF Article
More Like This
Traffic Grooming in Optical Networks: Decomposition and Partial Linear Programming (LP) Relaxation

Hui Wang and George N. Rouskas
J. Opt. Commun. Netw. 5(8) 825-835 (2013)

Stable Logical Topologies for Survivable Traffic Grooming of Scheduled Demands

Arunita Jaekel, Ying Chen, and Ataul Bari
J. Opt. Commun. Netw. 2(10) 793-802 (2010)

A Near-Optimal Solution Approach for the Multi-hop Traffic Grooming Problem

Ali Balma, Nejib Ben Hadj-Alouane, and Atidel B. Hadj-Alouane
J. Opt. Commun. Netw. 3(11) 891-901 (2011)

Cited By

Optica participates in Crossref's Cited-By Linking service. Citing articles from Optica Publishing Group journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (10)

Fig. 1
Fig. 1 (Color online) The four-node ring network for the example in Subsection III.C.
Fig. 2
Fig. 2 (Color online) MISD-4 path set partitions in a four-node ring network.
Fig. 3
Fig. 3 Path graph G p c w for clockwise paths in a four-node ring network.
Fig. 4
Fig. 4 Representation of MISs in G p c w by the MISs in G p c w , 0 and G p c w , 1 and core sets in G p c o r e .
Fig. 5
Fig. 5 (Color online) Comparison of formulations in terms of MIS decision variables.
Fig. 6
Fig. 6 (Color online) Solution times as a function of N.
Fig. 7
Fig. 7 (Color online) Solution times as a function of T max ; N = 16 .
Fig. 8
Fig. 8 (Color online) Size of the largest network size N max that can be solved with each minRWA formulation for a given number W of wavelengths, within 3000 s of CPU time.
Fig. 9
Fig. 9 Path graph of MISD- 2 x .
Fig. 10
Fig. 10 MIS Representation in MISD- 2 x .

Equations (27)

Equations on this page are rendered with MathJax. Learn more.

min V
l L n + c i j w , l l L n c i j w , l = 0 n i , j t i j n = i n N , t i j n = j ( i , j ) Z , w ,
( i , j ) Z c i j w , l 1 l L , w ,
( i , j ) Z l L c i j w , l u w Z L w ,
V w u w w ,
min V
k = c w , c c w w c i j , k w = t i j ( i , j ) Z ,
( i , j ) Z k = c w , c c w c i j , k w X i j , k l 1 l L , w ,
( i , j ) Z k = c w , c c w c i j , k w u w P w ,
V w u w w ,
Y i j , k m = 1 , if path set  m  contains path  p i j , k , 0 , otherwise.
min V
k = c w , c c w b i j , k = t i j ( i , j ) Z ,
b i j , k m M v m Y i j , k m ( i , j ) Z , k = c w , c c w ,
m M v m V .
b i j , k m M k v m k X i j , k m ( i , j ) Z , k = c w , c c w ,
m M k v m k V k = c w , c c w .
b i j , k q Q k v q k , c o r e X i j , k q p i j , k P k , c o r e , k = c w , c c w ,
b i j , k q Q k m M q k , r v q , m k , r X i j , k m p i j , k P k , r , k = c w , c c w , r = 0 , 1 ,
q Q k v q k , c o r e V k = c w , c c w ,
m M q k , r v q , m k , r = v q k , c o r e q Q k , r = 0 , 1 .
b i j , k q k , 1 Q k , 1 V q k , 1 X i j , k q k , 1 p i j G p k , 1 , k = c w , c c w ,
b i j , k q k , 1 Q k , 1 q k , r Q k , r q k , 1 V q k , r X i j , k q k , r p i j G p k , r , k = c w , c c w r = 2 , 3 ,
b i j , k q k , 1 Q k , r 1 q k , r 2 Q k , r 2 q k , 1 q k , r s 1 Q k , r s 1 q k , r s 2 m k , r s M k , r s q k , r s 1 V m k , r s X i j , k m k , r s p i j , k G p k , r s , s = x , 2 x 1 r s 2 x 1 , r s 1 = r s 2 , r s 2 = r k 1 2 , , r 1 = r 2 2 = 1 , k = c w , c c w ,
q k , r Q k , r q k , 1 V q k , r = V q k , 1 k = c w , c c w r = 2 , 3 ,
m k , r s M k , r s q k , r s 1 V m k , r s = V q k , r s 1 s = x , 2 x 1 r s 2 x 1 , r s 1 = r s 2 k = c w , c c w ,
V q Q k v q k , 1 k = c w , c c w .
Select as filters


Select Topics Cancel
© Copyright 2024 | Optica Publishing Group. All Rights Reserved