ILP Model and Relaxation-Based Decomposition Approach for Incremental Topology Optimization in p-Cycle Networks

p-cycle networks have attracted a considerable interest in the network survivability literature in recent years. However, most of the existing work assumes a known network topology upon which to apply p-cycle restoration. In the present work, we develop an incremental topology optimization ILP for p-cycle network design, where a known topology can be amended with new fibre links selected from a set of eligible spans. The ILP proves to be relatively easy to solve for small test case instances but becomes computationally intensive on larger networks. We then follow with a relaxation-based decomposition approach to overcome this challenge. The decomposition approach significantly reduces computational complexity of the problem, allowing the ILP to be solved in reasonable time with no statistically significant impact on solution optimality. 1. Introduction High-availability networks have become integral to our everyday lives, used for banking, financial transactions, voice and data communications, entertainment, and so forth. While much effort has been made to make them as reliable as possible, failures and, more critically, service outages still occur with alarming frequency. The vast majority of such failures are a result of fibre cuts, with most of those failures due to cable digups and similar construction accidents [1]. As the frequency of failures has increased, researchers have developed many approaches for ensuring survivability of the network even in the face of cable cuts or other equipment failures, including a number of mechanisms that allow the network to actively respond to a failure by rerouting affected traffic onto one or more backup routes. Survivability mechanisms are often thought of as being either restoration or protection [2]. Although the differences between the two are often blurred, and some mechanisms can be considered to be either type, the general idea is that restoration techniques are those in which a backup route is formed after failure, while protection techniques are those in which a backup route is formed before failure. Each individual survivability mechanism has its own advantages and disadvantages and requires differing amounts of spare capacity distributed throughout the network to accommodate backup routes. One particular protection mechanism that has received a lot of attention in recent years is -cycles [3, 4]. A p-cycle is a cyclic structure of preconfigured spare capacity, as illustrated in Figure 1, for example, where a six-span -cycle is shown in the leftmost panel. In the event of failure of an on-cycle span (a