September 2011
Spotlight Summary by Piero Castoldi
Fast Exact ILP Decompositions for Ring RWA
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.
You must log in to add comments.
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.
Add Comment
You must log in to add comments.
Article Information
Fast Exact ILP Decompositions for Ring RWA
Emre Yetginer, Zeyu Liu, and George N. Rouskas
J. Opt. Commun. Netw. 3(7) 577-586 (2011) View: Abstract | HTML | PDF