A fundamental problem in survivable routing in
wavelength division multiplexing (WDM) optical networks is the computation of a
pair of link-disjoint (or node-disjoint) light paths connecting a source with a
destination, subject to the wavelength continuity constraint. However, this
problem is NP-hard when the underlying network topology is a general mesh
network. As a result, heuristic algorithms and integer linear programming (ILP)
formulations for solving this problem have been proposed. In this paper, we
advocate the use of 2-edge connected (or 2-node connected) sub graphs of
minimum isolated failure immune networks as the underlying topology for WDM
optical networks. We present a polynomial-time algorithm for computing a pair
of link-disjoint light paths with shortest total length in such networks. The
running time of our algorithm is O (nW2), where n is the number of nodes, and W
is the number of wavelengths per link. Numerical results are presented to
demonstrate the effectiveness and scalability of our algorithm. Extension of
our algorithm to the node-disjoint case is straightforward.
No comments:
Post a Comment