ILP formulations for non-simple p-cycle and p-trail design in WDM mesh networks

Abstract

Conventional simple p-cycle (Preconfigured Protection Cycle) concept allows fast and capacity-efficient span protection in WDM mesh networks. Unlike simple p-cycle, non-simple p-cycle can traverse a node or span multiple times. The recently proposed p-trail (Pre-Cross-Connected Trail) concept further removes the cycle constraint by allowing arbitrary protection trails, leading to the most flexible and general design. Although non-simple p-cycles and p-trails are expected to be more capacity-efficient than simple p-cycles, it is still unclear how much capacity gain they can achieve compared with simple p-cycles. In this paper, we first point out some unique features of non-simple p-cycles and p-trails which are not fully explored in previous studies. This motivates us to formulate a new suite of ILPs (Integer Linear Programs) for optimal design of non-simple p-cycles and p-trails, based on which the achievable capacity gain over simple p-cycles can be investigated. Different from all the previous studies, the proposed ILPs are free of candidate cycle/trail enumeration, and can truly achieve an optimal design of non-simple p-cycles and p-trails. Our numerical results show that the capacity gain can be significant in some small-size networks with lightly-loaded traffic, but is generally trivial as the network size and the traffic load increase. © 2009 Elsevier B.V. All rights reserved.