Optics InfoBase: Spotlight on Optics - Fast Exact ILP Decompositions for Ring RWA

Spotlight on Optics

| HIGHLIGHTED ARTICLES FROM OSA JOURNALS

September 2011

Fast Exact ILP Decompositions for Ring RWA

Published in Journal of Optical Communications and Networking, Vol. 3 Issue 7, pp.577-586 (2011)
by Emre Yetginer, Zeyu Liu, and George N. Rouskas

Source article Abstract | Full Text: XHTML | Full Text: PDF

Spotlight summary: Routing and wavelength assignment (RWA) has been studied for a long time and under different perspectives, with NP-hard problem and various techniques proposed to overcome this issue. Over the years, a number of heuristic solutions have been proposed, starting with the seminal papers that introduced the concept of light path and considered assumptions of networks with different topologies and increasing number of features: continuous wavelength, wavelength selection, regenerator use, fixed and tunable transponders, etc. More recently, formulations based on maximal independent sets (MIS) have appeared as a viable workaround that, by relaxing the dependence of the problem size on the number of wavelengths, shift the complexity to the number of independents sets.

RWA is a crucial problem in optical wavelength-division multiplexing (WDM) networks, and the scientific community is always interested in finding novel approaches to solve well-known problems by tackling them in a fundamentally innovative way. As an example, the ring topology still dominates the metro environment, exploiting various flavors of WDM. Indeed, focusing on a ring WDM network, Yetginer et al., devised a fast, exact integer linear program (ILP) decomposition for the offline RWA problem. They did this by introducing the novel concept of MIS decomposition (MISD), i.e., the recursive graph decomposition by 2 x (x is arbitrary) groups of the link set, still yielding an optimal approach. The CPLEX solution of the relevant ILP formulation is really fast (order of magnitudes lower), especially for small networks.

This work constitutes a significant improvement in addressing the face scalability problem in offline RWA for WDM networks. We look forward to its extension to mesh topology, which would be a really powerful planning tool for the core networks of the major telecom operators.

--Piero Castoldi

OCIS Codes:	(060.4250) Fiber optics and optical communications : Networks
	(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms

Posted on September 27, 2011