On routing in large WDM networks

An important problem in WDM network design is to construct a logical topology and determine an optimal routing over that topology. Mixed Integer Linear Program (MILP) formulations to generate optimal solutions for this problem have been presented. Such formulations are computationally intractable, even for moderate sized networks. A standard approach is to decouple the problem of logical topology design and the problem of routing the traffic on this logical topology. Heuristics for finding the logical topology exist and a straight-forward linear program (LP), based on the node-arc formulation can be used to solve the routing problem over a given logical topology. We have found that such LP formulations become computationally infeasible for large networks. In this paper, we present a new formulation, based on the arc-chain representation, for optimally routing the specified traffic over a given logical topology to minimize the congestion of the network. We have used the revised simplex method incorporating an implicit column generation technique, and exploited the special Generalized Upper Bounding structure as well as the possibility of eta-factorization for efficiently updating the dual variables and finding the solution. Experimental results on a number of networks demonstrate the suitability of this approach.