A practical approach to operating survivable WDM networks

• Published in: IEEE journal on selected areas in communications 2002-01, Vol.20 (1), p.34-46
• Main Authors: Sridharan, M., Salapaka, M.V., Somani, A.K.
• Format: Article
• Language: English
• Subjects: Algorithms; Capacity planning; Computer networks; Cost function; Heuristic algorithms; Integer linear programming; Linear programming; Mathematical models; Network topology; Networks; On-line systems; Online; Optimization methods; Reconfiguration; Studies; Telecommunication traffic; Traffic control; Wavelength division multiplexing; WDM networks
• ISSN: 0733-8716; 1558-0008
• DOI: 10.1109/49.974660

Several methods have been developed for joint working and spare capacity planning in survivable wavelength-division-multiplexing (WDM) networks. These methods have considered a static traffic demand and optimized the network cost assuming various cost models and survivability paradigms. Our interest primarily lies in network operation under dynamic traffic. We formulate various operational phases in survivable WDM networks as a single integer linear programming (ILP) optimization problem. This common framework avoids service disruption to the existing connections. However, the complexity of the optimization problem makes the formulation applicable only for network provisioning and offline reconfiguration. The direct use of this method for online reconfiguration remains limited to small networks with few tens of wavelengths. Our goal in this paper is to develop an algorithm for fast online reconfiguration. We propose a heuristic algorithm based on LP relaxation technique to solve this problem. Since the ILP variables are relaxed, we provide a way to derive a feasible solution from the relaxed problem. The algorithm consists of two steps. In the first step, the network topology is processed based on the demand set to be provisioned. This preprocessing step is done to ensure that the LP yields a feasible solution. The preprocessing step in our algorithm is based on: (a) the assumption that in a network, two routes between any given node pair are sufficient to provide effective fault tolerance and (b) an observation on the working of the ILP for such networks. In the second step, using the processed topology as input, we formulate and solve the LP problem. Interestingly, the LP relaxation heuristic yielded a feasible solution to the ILP in all our experiments. We provide insights into why the LP formulation yields a feasible solution to the ILP We demonstrate the use of our algorithm on practical size backbone networks with hundreds of wavelengths per link. The results indicate that the run time of our heuristic algorithm is fast enough (in order of seconds) to be used for online reconfiguration.