Low Complexity Design of Fault-Tolerant Optical Network with Arbitrary Mesh Topology

M.K.-S. Ho and K.-W. Cheung (PRC)


Network Design, Arbitrary Topology, Survivability, Spare Capacity Planning, Drop Algorithm.


We present a low-complexity algorithm for designing survivable optical mesh networks with arbitrary topology. In this class of problems, the geographic locations of the network nodes are given and the traffic demand between each source-destination pair is given by a traffic matrix. The problem is to optimize the total network cost that is characterized by three parameters for each link, namely, the installation cost, the bandwidth cost and the equipment cost. The problem is NP-hard. We tackle the problem by incorporating a modified drop algorithm (MDA) into an efficient spare-capacity planning algorithm SCAPE which is a low complexity heuristic for optimizing the allocation of spare capacities on a given topology network to render it fully single-fault (or multi-faults) tolerant. Joint optimization for the topology design, working- and spare-capacity planning is shown for the first time, and we show that joint optimization can result in a cost reduction of about 28% for a 10-node network.

Important Links:

Go Back