6 - Managing large networks

Summary

Several methods discussed for joint working and spare capacity planning in survivable WDM networks in the last chapter considered a static traffic demand and optimized the network cost assuming various cost models and survivability paradigms. The focus here lies in network operation under dynamic traffic. The common framework that captures the various operational phases in a survivable WDM network in a single ILP optimization problem avoids service disruption to the existing connections. However, the complexity of the optimization problem makes the formulation applicable only for network provisioning and offline reconfigurations. The direct use of this method for online reconfiguration remains limited to small networks with a few tens of wavelengths.

Online algorithm

The goal here is to develop an algorithm for fast online reconfiguration using a heuristic algorithm based on an LP relaxation technique. Since the ILP variables are relaxed, a way is needed to derive a feasible solution from the solution of 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 ensures that the LP yields a feasible solution. The preprocessing step is based on (i) the assumption that in a network, two routes between any given node-pair are generally sufficient to provide effective fault tolerance, and (ii) an observation on the working of the ILP for such networks. In the second step, using the processed topology as input, the LP is solved. It is interesting to obtain some insights into why the LP formulation may yield a feasible solution to the ILP.