Invited Session Mon.3.H 3002

Monday, 15:15 - 16:45 h, Room: H 3002

Cluster 23: Telecommunications & networks [...]

Optimization of optical networks


Chair: Brigitte Jaumard



Monday, 15:15 - 15:40 h, Room: H 3002, Talk 1

Brigitte Jaumard
Path vs. cutset column generaton models for the design of IP-over-WDM optical networks

Coauthors: Minh N. Bui, Anh H. Hoang


Multi-layer optical networks have recently evolved towards IP-over-WDM networks. Therein, in order to avoid protection/restoration redundancies against either single or multiple failures, synergies need to be developed between IP and optical layers in order to reduce the costs and the energy consumption of the future IP-over-WDM networks.
We propose two new column generation models. The first one is an enhanced cutset model. The second one is a path model, based on a multi-flow formulation. Both models can solve exactly most benchmark instances, which were only solved heuristically so far.



Monday, 15:45 - 16:10 h, Room: H 3002, Talk 2

Jørgen Thorlund Haahr
Heuristic planning of shared backup path protection

Coauthors: Thomas Stidsen, Martin Zachariasen


Protecting communication networks against failures is becoming increasingly important as they have become an integrated part of our society. Cable failures are fairly common, but it is unacceptable for a single cable failure to disconnect communication even for a very short period and hence protection schemes are employed. The most utilized protection schemes today are ring protection and 1+1 protection. Both schemes do however require a significant extra network capacity. A more advanced protection method such as shared backup path protection (SBPP) can be used instead. SBPP is a simple but efficient protection scheme that can be implemented in backbone networks with technology available today.
We prove that SBPP planning is a NP-hard optimization problem. Previous work confirms that it is time-consuming to solve the problem in practice using exact methods. We present heuristic algorithms and lower bound methods for the SBPP planning problem. Experimental results show that the heuristic algorithms are
able to find good quality solutions in few minutes. A solution gap of less than 12,% was achieved for seven test networks.



Monday, 16:15 - 16:40 h, Room: H 3002, Talk 3

Philippe Mahey
Algorithms for lower and upper bounds for routing and wavelength assignment

Coauthors: Christophe Duhamel, Alexandre Martins, Rodney Saldanha, Mauricio Souza


In all-optical networks a traffic demand is carried from source to destination through a lightpath, which is a sequence of fiber links carrying the traffic from end-to-end. The wavelength continuity constraint implies that to a given lightpath a single wavelength must be assigned. Moreover, a particular wavelength cannot be assigned to two different lightpaths sharing a common physical link. The routing and wavelength assignment (RWA) problem arises in this context as to establish lightpaths to carry traffic demands. The problem is found in two versions: (i) to minimize the number of wavelengths to meet fixed traffic requests; and (ii) to maximize the traffic requests satisfied given a fixed number of wavelengths. In this work, we develop algorithms to tackle the RWA via lower and upper bounds. We present, by combining column generation models from the literature, a fast procedure to obtain lower bounds. We also present heuristic approaches based on variable neighborhood descent (VND) with iterated local search (ILS) for the min-RWA. We report numerical results showing optimality gaps obtained on benchmark instances from the literature.


  There are three major facts that should be watched out for in all payday loans in the United States. On the global pharmaceutical market this medicine was issued in 2003 by two companies - Eli Lilly and ICOS. Initially, permission to sell Cheap Cialis was obtained in Europe, Australia, New Zealand.