On-line Survivable Routing in WDM Networks

On-line Survivable Routing in WDM Networks

Beshir, A.A.
Kuipers, F.A.
Van Mieghem, P.
Orda, A.

Electrical Engineering, Mathematics and Computer Science

Network Architectures and Services

In WDM networks, survivable routing and wavelength assignment (SRWA) involves assigning link-disjoint primary and backup lightpaths. In the on-line SRWA problem, a sequence of requests arrive and each request is either accepted or rejected based only on the input sequence seen so far. For special networks, we establish on-line algorithms with constant and logarithmic competitive ratios. It is not possible to obtain good competitive ratios in general topologies. Hence, we propose heuristic schemes and evaluate their performance by way of simulations. The building blocks in these schemes are 2-approximation algorithms (MSA and ESA) that we establish for the minimum disruption link-disjoint paths (MDLDP) problem. These approximations require far less memory and computation time than the best-known exact solution of the MDLDP problem. We use these three algorithms as heuristics for the on-line SRWA problem for infinite and finite duration requests and we show that, in terms of on-line performance, our algorithms do as well as (even at times better than) the exact algorithm of the MDLDP problem. We also provide an exact ILP formulation to solve the infinite duration off-line SRWA problem.

http://resolver.tudelft.nl/uuid:523bea7b-e78b-41e1-a200-8533984e0efc

International Teletraffic Congress

21st International Teletraffic Congress (ITC 21), 15-17 September 2009

Institutional Repository

conference paper

(c) 2009 Beshir, A.A., Kuipers, F.A., Van Mieghem, P., Orda, A.