A novel algorithm for node‐encircling and link candidate p‐cycles design in WDM mesh network

Abstract

A fault recovery system that is fast and reliable is essential in survivability design in wavelength‐division‐multiplexing (WDM) mesh networks. The Pre‐configuration Cycle (p‐cycle) is a promising approach for protecting working capacities in optical mesh networks. Finding good candidate cycles is the first and a very important step in p‐cycle design. We first introduce the definition of the local‐map and several algorithms for finding cycles. A novel heuristic algorithm, called Local‐map Cycles Mining Algorithm (LCMA), for finding simple node‐encircling and link candidate p‐cycles based on the local‐map is proposed in this paper. We perform the expanding algorithms on the cycle generated by LCMA to get more efficient candidate p‐cycles. Comparisons are made between this algorithm and the Depth First Search (DFS) algorithm and the result shows that the LCMA can find more candidate p‐cycles with good efficiency in optical mesh networks without enumerating all cycles.

Key words:

• optical network
• p‐cycle
• local‐map
• finding cycles

Notes

Corresponding author. (Tel: [phone]; Fax: [phone]; Email: [email protected])