4.5. Survivable Network Design Techniques

Given a specific traffic restoration scheme (e.g., p-cycles), the survivable network design problem is to determine the network topology or virtual topology to survive a set of failure scenarios. Survivable network design typically makes use of graph theoretic or optimization-based formulations [7, 9, 12, 39]. While there are a number of different approaches used, one differentiating characteristic is whether working routing is optimized jointly with restoration/protection routing and spare capacity, or if working routing is performed separately (e.g., often through shortest-path or minimum-cost routing). The former is usually referred to as joint-capacity allocation (JCA), while the latter is called spare-capacity allocation (SCA).

The goal of many survivable network design problems is to place sufficient capacity to fully protect against all single-span failure scenarios at minimal cost, though other design problems seek to reduce blocking probabilities, maximize single or dual-failure restorability, maximize network availability, and so on. Most of the various minimum-cost network design formulations used can also be divided into two main classes of optimization problem: arc-path approaches and transshipment approaches. In the arc-path approaches, the network graph topology is preprocessed to enumerate all or at least a subset of all distinct logical routes that can be used for restoration/protection routes, and an optimization problem formulated to select among them to provide full survivability (usually at minimum cost) [39]. The transhipment approaches formulate a series of conservation-of-flow type of constraint equations, where each working demand has a source and sink node, and all other nodes act as transhipment or intermediary nodes where any flow of a particular demand into the intermediary node must subsequently flow out of that node.

For illustration purposes, we now provide the arc-path formulation of the span restoration SCA and JCA problems [29, 39]. We first define the network topology as consisting of a set of spans S, a set of nodes N, and a set of demand relations D. In the transhipment approach, we also need to pass node and span adjacency information to the design optimization problem (i.e., the design problem needs to know which spans are adjacent to which nodes, and so on, in order to deal with the conservation of flow constraints), but in the arc-path approach, such information is only used in preprocessing to identify eligible route sets. Any method desired can be used to enumerate eligible routes, so long as we have a set of such routes to provide to the solver. Typically, custom-designed preprocessing software is used, often using a depth-first search algorithm that crawls through the network topology identifying eligible routes. The set of eligible routes could be the complete set of all distinct possible routes that can be drawn in the network’s topology, but generally this set can be quite large (negatively impacting on the design problem’s runtime). So we often restrict the eligible set to a subset of all distinct routes in the network such that, say, only the shortest 25 routes between each span’s end nodes are included, or alternately all the paths satisfying a hop count limit are included. In any case, through preprocessing of the network’s topology, we enumerate a set P_i of all distinct eligible routes that are available to act as restoration routes for working channels on failed span i ϵ S, and a set Q_r of all distinct eligible routes that are available to carry working path traffic for demand relation r ϵ D.

Eligible routes can be represented in a number of different ways, including as an ordered or unordered list of spans crossed, a list of nodes crossed, or, in our example here, through binary parameters. We encode restoration routes using the parameter , where if restoration route p for working channels on failed span j crosses span i, and otherwise. Similarly, we encode working routes using the parameter , where if working route q, that can be used to carry working path routing for demand relation r crosses span j, and otherwise. The number of unit-size working paths needed by demand relation r is denoted by parameter d^r, and the cost of placing a single unit of working or spare capacity on span j is c_j. This latter parameter is usually equated with the Euclidean distance between the end nodes of the span in order to represent costs that are roughly proportional to a span’s length (e.g., fiber itself, rights of way, amplifiers), though any other value(s) desired could be used. We then define a number of decision variables for the optimization problem to determine, namely: w_i ≥ 0 and s_i ≥ 0 are the amount of working capacity and spare capacity, respectively, that are placed on span i in the final solution. g^r,q ≥ 0 is the number of working channels assigned by the solver to working route q that can be used to carry working path routing for demand relation r, and f_i,p ≥ 0 is the number of spare channels assigned to restoration route p that can be used for restoration of working channels on failed span i.

Strictly speaking, since all four decision variables are usually required to take integer values only (say, corresponding to a WDM optical network where a unit of capacity would represent an individual wavelength), the optimization design problem is called an integer linear programming (ILP) problem. However, we often solve the ILP as a mixed integer linear programming (MIP) problem, where we allow working and restoration routing variables to take on fractional (i.e., noninteger) values. It has been shown that as long as the working and spare-capacity variables are forced to take on integer values, the integrality requirement of the underlying g^r,q and f_i,p variables can be relaxed without affecting optimality [47, 48]. We would solve the problem in this manner because a greater number of integer variables generally increases, often quite considerably, the complexity (and runtime) of an MIP/ILP problem. Using the notation just discussed, we can then express the span-restorable JCA network design problem as follows:

Equation 4.1

Equation 4.2

Equation 4.3

Equation 4.4

Equation 4.5

The objective function in Eq. 4.1 seeks to minimize the total cost of working and spare capacity assigned to the various spans in the network. Eq. 4.2 represents a set of constraints (one for each r ϵ D) that ensure the total number of working channels assigned to all eligible working routes for demand relation r are sufficient to fully route its entire demand, d^r. The constraints in Eq. 4.3 then place enough working capacity on each span to accommodate all working channels routed over it. Eq. 4.4 represents a similar set of constraints as those in Eq. 4.2, except that it ensures that the total number of spare channels assigned to all eligible restoration routes for failed span i are sufficient to fully restore all working channels, W_i, on that failed span. Finally, the constraints in Eq. 4.5 place enough spare capacity on each span j to accommodate all restoration paths that will be simultaneously routed over it for any single span failure scenario (i.e., failure of span i).

As already mentioned, the above ILP design model is the JCA version of the problem. It can easily be modified into the SCA version by changing Eq. 4.1 into removing Eqs. 4.2 and 4.3, performing working routing offline in advance, and then converting the W_i decision variables into input parameters. Alternatively, one could leave the model exactly as presented and simply provide only a single eligible working route for each demand relation, thereby forcing working routing to take a specified configuration. This problem also assumes there is no limit on the capacity of each span. We can easily implement span-capacity limits by adding a new set of constraints that enforce s_j + w_j ≤ T_j, for instance, where T_j is the capacity limit on span j. In a similar fashion, many useful variations on this basic survivable network design problem embedding it in a particular technology can be formulated by modifying/adding constraints and the objective function. The interested reader is encourage to consult [7, 9, 12–17, 20] and the recent literature.