ILP formulation for p-cycle construction based on flow conservation

Abstract

The concept of p-cycle (Preconfigured Protection Cycle) allows fast and efficient span protection in WDM mesh networks. To construct p-cycles, conventional algorithms need to enumerate all the candidate cycles in the network before ILP (Integer Linear Program) can be applied to find the optimal solution. To reduce the size of the candidate set and thus speed up the optimization process, heuristic algorithms are proposed for candidate cycle pre-selection at the cost of lower solution quality. Recently, some interesting ILP formulations were proposed to construct p-cycles without candidate cycle enumeration/preselection. But they tend to require a long running time. Following the approach of no candidate cycle enumeration, we formulate a new ILP based on flow conservation in this paper. Numerical results show that our new ILP runs much faster than the existing ones. © 2007 IEEE.