Heuristic for the maximum disjoint paths problem in wavelength-routed networks with shared-risk link groups [Invited]

Abstract

We tackle the problem of finding the maximum number of link-disjoint paths between a pair of source-destination nodes in wavelength-routed networks, subject to the shared-risk link group (SRLG) constraints. We propose a simple heuristic algorithm whose main idea is to iteratively find the path with the minimum total weight of all the SRLGs through which it passes until no further path can be found, where the weight of each SRLG is basically proportional to its size, and those SRLGs appearing in the minimum cut between the source-destination nodes are assigned higher weights. Extensive simulation results show that the proposed method, with a complexity comparable to that of the simplest conventional k-shortest-path algorithm, steadily outperforms the best existing method.

© 2003 Optical Society of America