ISSN : 1796-2056
Volume : 1 Issue : 3 Date : July 2006
Efficient Distributed Algorithm for RWA Using Path Protection
Arunita Jaekel and Ying Chen
Page(s): 1-8
Full Text: PDF (370 KB)
Abstract
A number of Integer Linear Program (ILP) formulations for both static and dynamic lightpath
allocation have been proposed, for the design of survivable WDM networks. However, such
formulations become computationally intractable for larger networks. In this paper, we present two
heuristic algorithms for dynamic lightpath allocation, using both dedicated and shared path
protection. The first is a centralized algorithm and the second is a distributed algorithm. The
objective in both cases is to minimize the amount of resources (wavelengthlinks) needed to
accommodate the new connection. We have tested our algorithms on a number of well-known
networks and compared their performance to “optimal” solutions generated by ILPs. Experimental
results show that our heuristics generate solutions that are within 15% of the optimal. Our approach
is much faster and more scalable compared to existing ILP formulations.
Index Terms
Distributed RWA; Path protection; Survivable WDM networks
