Static lightpath establishment in WDM networks - New ILP formulations and heuristic algorithms

This paper considers Wavelength Division Multiplexing (WDM) networks, which employ wavelength routing switches that enable the establishment of lightpaths through the network between node-pairs. Conventional Routing and Wavelength Assignment (RWA) algorithms for Static Lightpath Establishment (SLE) are based on traditional circuit-switched networks where routing and wavelength assignment steps are decoupled. In this paper, we propose new Integer Linear Program (ILP) formulations for maximizing network throughput for two different types of traffic patterns namely, uniform and non-uniform. In the proposed formulations, routing and wavelength assignment steps are tightly coupled, unlike earlier proposed formulations. However, for large size networks solving the ILP formulations can easily overwhelm the capabilities of today's state-of-art computing facilities. Hence, we propose two heuristic algorithms based on wavelength-graph for maximizing network throughput. Simulation studies indicate that the heuristic approach gives performance close to the optimal solution obtained using ILP based solution. © 2002 Elsevier Science B.V. All rights reserved.