Efficient cycle algorithms for capacitated optical network design

Abstract

This thesis studies the cycle-based protection schemes for DWDM (Dense Wavelength Division Multiplexing) networks. We first present the MSCC (Min-Sum Cycle Cover) Algorithm for simultaneous detection and protection using the Eulerian graph theory, and then analyze the performance of the algorithm through making comparison of it with other algorithms. By extending the features of algorithm SLA (Straddling Link Algorithm) and initial ideas for p-cycle candidate generation (operations called Add and Join), we formulate more advanced cycle-generation algorithms: SP-Add, SP-Join and SP-Merge. We then use the developed heuristic spare capacity planning algorithms based on weighted or unity capacity efficiency of p-cycles, WCIDA, to test the fully restorable p-cycle network design. In addition, two capacitated algorithms will be presented and compared with each other.