# Optimization ofp-Cycle Placement for Differentiated Levels of Protection

Authors: Hong Hui Li; Xue Liang Fu
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper develops a new scalable and efficient model for the design ofp-cycles with the differentiated levels of node protection. The proposed model allows the indicated level of node survivability ranging from 0% to 100%, which could facilitate a carrier offer node-failure survivability (and hence availability) on a differentiated service basis. To design p-cycles, an integer linear program (ILP) is usually formulated with the prerequisite of a prior enumeration of all possible p-cycle candidates. A huge number of candidates may exist in a large-scale network. Thus, the resulting ILP becomes intractable. We propose a new design and solution method based on large-scale optimization techniques, known as column generation (CG). With CG, our design method generates p-cycle candidates dynamically when needed. Extensive experiments have been conducted for evaluation. The numerical results show that, with the spare capacity used only for link protection, up to 50% node-failure survivability can be achieved for free. Full node protection can be achieved at a marginal cost in comparison with those for link protection only.


---

## Body

## 1. Introduction

WDM (wavelength division multiplexing) mesh networks are preferred as next generation optical core networks [1]. The WDM technology enables a single fiber to carry up to hundreds of wavelength channels, each of which operates at a speed of several Gbps. Thus, a single network element failure may cause the failure of a number of light paths, which leads to the huge data as well as revenue loss. Survivability therefore is an important requirement in the design of WDM mesh networks.Different kinds of protection approaches have been proposed for WDM optical mesh networks to ensure survivability from any single failure. Among them,p-cycles (short for preconfigured protection cycle) [2] have attracted extensive research interests due to their unique characteristics, that is, fast recovery speed and efficient capacity usage. Most of studies on p-cycle-based survivable network design [2–7] only consider protection against a single link failure with no consideration of a single node failure. A single node failure happens less frequently than a single link failure in WDM mesh networks. However, the resulting effects may be catastrophic as a single node failure disrupts all its incident links. Moreover, according to service level agreements, customers may require differentiated levels of node protection. Thus, partial protection of paths from a single node failure may be cost effective and an attractive offering of a differentiated business.So far, however, very few papers have exploredp-cycle design with the differentiated levels of node protection. Node-encircling p-cycles (NEPC) are proposed in [8] for protection against any single node failure. An enhanced APS for p-cycles with node protection is proposed in [9]. Path-segment-protecting p-cycles are suggested in [10] for node protection. A very recent finding regarding p-cycles for node protection is reported in [11]. In order to keep the simplicity of p-cycle protection switching, the authors propose the two-hop-segment strategy for node protection [12] (see Section 2).To designp-cycles with node protection, the conventional way (e.g., [9, 10]) is to formulate the design problem as integer linear program (ILP). The prerequisite for the ILP solution is a prior enumeration of all possible p-cycle candidates. The number of p-cycle candidates increases exponentially with the increase of network size (the number of links). Thus, the resulting ILP becomes less tractable in large-scale optical networks. If only a subset of p-cycles candidates is considered, solution quality may not be guaranteed.In this paper, we explorep-cycle design with the differentiated levels of node protection using the two-hop-segment strategy. The objective is to minimize spare capacity cost such that a network can survive from any single link failure as well as survive from the required level of any single node failure. (Note that for a single node failure, only the working paths passing through it are considered for protection.) In contrast with the protection approach in [12], the proposed approach [13, 14] enhances the p-cycle protection capability. A p-cycle can protect multiple affected paths upon an intermediate node failure. To deal with the scalability issues suffered in the conventional designs, we develop a new design method based on large-scale optimization tools, namely, column generation (CG). With CG, our proposed design generates p-cycle candidates dynamically when needed in the course of the optimization process.The rest of the paper is organized as follows. Section2 illustrates the principle of p-cycles for node protection. Section 3 presents the CG formulation developed for the design of p-cycles with differentiated levels of node protection. Section 4 evaluates the solution performance of the proposed design. Conclusions are made in Section 5.


## 2. Background

In this section, we illustrate the two-hop-segment strategy for node protection usingp-cycles. p-Cycles are originally proposed for link protection. The very recent study [12] suggests the two-hop-segment strategy, with which p-cycles can protect from a single node failure. For an intermediate node of a working path, the related two-hop segment includes two links on the path which are adjacent to the node. If a p-cycle protects the two links of a two-hop segment, a p-cycle can protect the associated intermediate node in an on-cycle protection manner. In this on-cycle manner, a p-cycle provides one protection path for the recovery of one unit traffic through the failed node. If only two end nodes of a two-hop segment are sitting on a p-cycle, the p-cycle cab offers two protection paths. This protection manner is named as a straddling protection manner.Figure1 illustrates the principal of node protection with p-cycles, where a demand s-d is carried on working path s-a-b-c-d. For the intermediate node b, the associated two-hop segment consists in a-b-c. To protect node b, the associated p-cycle must protect the two-hop segment a-b-c wholly. As shown in Figure 1(a) to Figure 1(d), each p-cycle, from c1 to c4, can be used to protect the intermediate node b. Among them, Figure 1(a) to Figure 1(c) show the on-cycle protection manner, while Figure 1(d) shows the straddling protection manner.Two-hop-segment strategy for node protection withp-cycles.
(a)
(b)
(c)
(d)


## 3. A Column Generation Model

An optical network is denoted by a graphG=(V,L), where V is the set of nodes and L is the set of links, indexed by v and ℓ, respectively.In order to deal with the scalability issues in the classical design, we develop a column-generation- (CG-) based optimization model. Only a very few number of promisingp-cycle candidates are generated online as needed in the course of the optimization process. With the CG technique (see, e.g., [15] for basic reference), the original design problem is decomposed into two problems: the master problem and the pricing problem. The master problem chooses p-cycles from candidates in order to protect all traffic against a single link failure or a single node failure according to the related quality of protection of node. A p-cycle candidate is generated dynamically by the pricing problem in each iteration of the CG algorithm.


### 3.1. The Master Problem

We denote the number of traffic units on linkℓ by ωℓ. For a given working path p∈P, let dp be the number of connection requests carried on it and let Vp be its intermediate node set. Let Φ be the QoP of the intermediate nodes of the working path p.Candidates are associated with the configuration setC. A cycle configuration c consists in a cycle that protects a set of links and a set of working paths against the failure of the associated intermediate nodes. A cycle configuration c is associated with a vector (aℓc)ℓ∈L and a matrix (apvc)p∈P,v∈Vp. The element aℓc∈{2,1,0} denotes the number of protection paths for link ℓ provided by the configuration c. The element apvc∈{2,1,0} represents the number of protection paths provided by configuration c for working path p against the failure of its relay node v. Let COSTc be the spare capacity cost of configuration c, which relies on the number of the on-cycle links.Variableszc denote the number of configuration c copies that are selected in the current solution. The design objective is to minimize the total spare capacity usage to protect all links as well as meet the required QoP for nodes.The mathematical model can then be written as follows:(1)min∑c∈C‍COSTczc(2)subjectto:∑c∈C‍aℓczc≥ωℓℓ∈L(3)∑c∈C‍apvczc≥Φdpp∈P,v∈Vp(4)zc∈ℤ+c∈C.Constraints (2) ensure that all traffic units are protected against any single link failure. Constraints (3) ensure that all demands are protected against a single node failure according to the associated level of QoP. Constraints (4) are variable domain constraints.


### 3.2.  The Pricing Problem

The pricing problem corresponds to the optimization problem for generation of the promisingp-cycle candidates. The pricing problem is the same as the one in [13, 14] as the same protection approach is adapted for node protection with p-cycles. The objective is to minimize the so-called reduced cost of the master problem and subject to sets of constraints.The reduced cost can be written as follows:(5)COSTc¯=COSTc-∑ℓ∈L‍uℓaℓc-∑p∈P‍∑v∈Vp‍upvapvc,
where uℓ and upv are dual variables associated with constraints (2) and constraints (3), respectively.Let us next define the following notations.Sets and Parameters.  ω(v) is the set of links adjacent to a node v. ω(V′) is the set of links with one end node in the set V′ but the other end node not. Pv is the set of working paths going through node v.  τvℓ=1 if link ℓ is adjacent to node v and on path p; 0 otherwise.  epv1 and epv2 are two end nodes of the 2-hop segment defined by working path p and its relay node v.Variables.  bℓ=1 if link ℓ sits on the current cycle; 0 otherwise. sℓ=1 if link ℓ straddles the current cycle; 0 otherwise.  yv=1 if node v belongs to the current cycle; 0 otherwise. xpvℓ=1 if link ℓ is used to protect a path p against the failure of its relay node v; 0 otherwise.With these notations, the objective function of the pricing problem can then be written as follows:(6)min∑ℓ∈L‍(Λℓ-uℓ)bℓ-2∑ℓ∈L‍uℓsℓ-∑p∈P‍∑v∈Vp‍upv∑ℓ∈ω(epv1)‍xpvℓ.Regarding constraints, there are two parts in the pricing problem. The first part defines a cycle, while the second part identifies the associated intermediate nodes of the working paths which can be protected by the current cycle.In the following, the first part of constraints is presented:(7)∑ℓ∈ω(v)‍bℓ=2yvv∈V,(8)sℓ≤yv-bℓv∈V,ℓ∈ω(v),(9)sℓ≥yv+yv′-bℓ-1v,v′∈V,ℓ={v,v′}∈L,(10)∑ℓ∈ω(V′)‍bℓ≥yv+yv′-1V′⊂V,3≤|V′|≤|V|-3v∈V′,v′∈V∖V′.Constraints (7) ensure that an on-cycle node holds two incident links on the cycle. Constraints (8) and (9) say that a link is a straddling link if the link is with two on-cycle end nodes but itself is not. Constraints (10) forbid generating a configuration with multiple cycles. Otherwise, it may complicate the determination of straddling links.The second part of the constraints is next presented as follows:(11)xpvℓ≤bℓp∈P,v∈Vp,ℓ∈L,(12)xpvℓ≤1-τvℓp∈P,v∈Vp,ℓ∈L,(13)∑ℓ∈ω(epv1)‍xpvℓ=∑ℓ∈ω(epv2)‍xpvℓp∈P,v∈Vp,(14)∑ℓ∈ω(v′)‍xpvℓ≤2p∈P,v∈Vp,v′∈V,∑ℓ∈ω(v′)∣ℓ≠ℓ′‍xpvℓ≥xpvℓ′p∈P,v∈Vp,ℓ′∈ω(v′)(15)v′∈V∖{epv1,epv2},(16)∑p∈Pv‍xpvℓ≤1ℓ∈L,v∈V,(17)bℓ,sℓ,yv,xpvℓ∈{0,1}ℓ∈L,v∈V,p∈P.Constraints (11) say that only on-cycle links are eligible for protecting the intermediate nodes of the working path p. Constraints (12) say that a link cannot be used by the associated protection paths if the link is adjacent to the intermediate node v of the working path p. Constraints (13)–(15) are flow conservation constraints for defining the associated protection paths. The failure of a node affects all working paths through it. Constraints (16) say that, among them, only a disrupted working path can be recovered. The final set of constraints is variable domain constraints.


## 3.1. The Master Problem

We denote the number of traffic units on linkℓ by ωℓ. For a given working path p∈P, let dp be the number of connection requests carried on it and let Vp be its intermediate node set. Let Φ be the QoP of the intermediate nodes of the working path p.Candidates are associated with the configuration setC. A cycle configuration c consists in a cycle that protects a set of links and a set of working paths against the failure of the associated intermediate nodes. A cycle configuration c is associated with a vector (aℓc)ℓ∈L and a matrix (apvc)p∈P,v∈Vp. The element aℓc∈{2,1,0} denotes the number of protection paths for link ℓ provided by the configuration c. The element apvc∈{2,1,0} represents the number of protection paths provided by configuration c for working path p against the failure of its relay node v. Let COSTc be the spare capacity cost of configuration c, which relies on the number of the on-cycle links.Variableszc denote the number of configuration c copies that are selected in the current solution. The design objective is to minimize the total spare capacity usage to protect all links as well as meet the required QoP for nodes.The mathematical model can then be written as follows:(1)min∑c∈C‍COSTczc(2)subjectto:∑c∈C‍aℓczc≥ωℓℓ∈L(3)∑c∈C‍apvczc≥Φdpp∈P,v∈Vp(4)zc∈ℤ+c∈C.Constraints (2) ensure that all traffic units are protected against any single link failure. Constraints (3) ensure that all demands are protected against a single node failure according to the associated level of QoP. Constraints (4) are variable domain constraints.


## 3.2.  The Pricing Problem

The pricing problem corresponds to the optimization problem for generation of the promisingp-cycle candidates. The pricing problem is the same as the one in [13, 14] as the same protection approach is adapted for node protection with p-cycles. The objective is to minimize the so-called reduced cost of the master problem and subject to sets of constraints.The reduced cost can be written as follows:(5)COSTc¯=COSTc-∑ℓ∈L‍uℓaℓc-∑p∈P‍∑v∈Vp‍upvapvc,
where uℓ and upv are dual variables associated with constraints (2) and constraints (3), respectively.Let us next define the following notations.Sets and Parameters.  ω(v) is the set of links adjacent to a node v. ω(V′) is the set of links with one end node in the set V′ but the other end node not. Pv is the set of working paths going through node v.  τvℓ=1 if link ℓ is adjacent to node v and on path p; 0 otherwise.  epv1 and epv2 are two end nodes of the 2-hop segment defined by working path p and its relay node v.Variables.  bℓ=1 if link ℓ sits on the current cycle; 0 otherwise. sℓ=1 if link ℓ straddles the current cycle; 0 otherwise.  yv=1 if node v belongs to the current cycle; 0 otherwise. xpvℓ=1 if link ℓ is used to protect a path p against the failure of its relay node v; 0 otherwise.With these notations, the objective function of the pricing problem can then be written as follows:(6)min∑ℓ∈L‍(Λℓ-uℓ)bℓ-2∑ℓ∈L‍uℓsℓ-∑p∈P‍∑v∈Vp‍upv∑ℓ∈ω(epv1)‍xpvℓ.Regarding constraints, there are two parts in the pricing problem. The first part defines a cycle, while the second part identifies the associated intermediate nodes of the working paths which can be protected by the current cycle.In the following, the first part of constraints is presented:(7)∑ℓ∈ω(v)‍bℓ=2yvv∈V,(8)sℓ≤yv-bℓv∈V,ℓ∈ω(v),(9)sℓ≥yv+yv′-bℓ-1v,v′∈V,ℓ={v,v′}∈L,(10)∑ℓ∈ω(V′)‍bℓ≥yv+yv′-1V′⊂V,3≤|V′|≤|V|-3v∈V′,v′∈V∖V′.Constraints (7) ensure that an on-cycle node holds two incident links on the cycle. Constraints (8) and (9) say that a link is a straddling link if the link is with two on-cycle end nodes but itself is not. Constraints (10) forbid generating a configuration with multiple cycles. Otherwise, it may complicate the determination of straddling links.The second part of the constraints is next presented as follows:(11)xpvℓ≤bℓp∈P,v∈Vp,ℓ∈L,(12)xpvℓ≤1-τvℓp∈P,v∈Vp,ℓ∈L,(13)∑ℓ∈ω(epv1)‍xpvℓ=∑ℓ∈ω(epv2)‍xpvℓp∈P,v∈Vp,(14)∑ℓ∈ω(v′)‍xpvℓ≤2p∈P,v∈Vp,v′∈V,∑ℓ∈ω(v′)∣ℓ≠ℓ′‍xpvℓ≥xpvℓ′p∈P,v∈Vp,ℓ′∈ω(v′)(15)v′∈V∖{epv1,epv2},(16)∑p∈Pv‍xpvℓ≤1ℓ∈L,v∈V,(17)bℓ,sℓ,yv,xpvℓ∈{0,1}ℓ∈L,v∈V,p∈P.Constraints (11) say that only on-cycle links are eligible for protecting the intermediate nodes of the working path p. Constraints (12) say that a link cannot be used by the associated protection paths if the link is adjacent to the intermediate node v of the working path p. Constraints (13)–(15) are flow conservation constraints for defining the associated protection paths. The failure of a node affects all working paths through it. Constraints (16) say that, among them, only a disrupted working path can be recovered. The final set of constraints is variable domain constraints.


## 4. Computational Results

In this section, we evaluate the solution performances of our proposed design experimentally. Two metrics are exploited for evaluation, which include capacity redundancy (the ratio of spare capacity to working capacity [9]) and the average size (the average number of links) of the p-cycles selected in the final solution. Both design methods are implemented in C++ and solved by IBM CPLEX solver.


### 4.1. Date Instances

Four test networks are presented in Table1. For each network, we provide network name, the number of nodes, the number of links, and the node degree for approximately representing connectivity. Also, we list the number of demands carried on each network and the associated working capacity cost. Each element in the associated traffic matrices represents the number of requests between each node pair, which is uniformly distributed on the interval [1,…,20].Table 1
Network instances.
Networks
Nodes
Links
Node degree
Num. demands
Working capacity
GERMANY [16]
17
26
3.1
136
4034
BELLCORE [17]
15
28
3.7
105
2610
NJLATA [17]
11
23
4.2
55
943
COST239 [18]
11
26
4.7
55
792


### 4.2.  Experimental Comparison

Experimental results regarding capacity redundancy and the average size of thep-cycles are shown in Figure 2. In Figure 2(a), for the indicated network instance, each bar corresponds to the capacity redundancy of an optimal solution for the indicated level of node-failure recovery ratio (i.e., Φ values). Experimental results reveal that, with our proposed QoP design, p-cycles can provide 100% node-failure survivability (i.e., Φ=1) at marginal additional redundant spare capacity compared with those only for link protection (Φ=0), which ranges from ~1% to ~15%. The denser the network is, the less the redundant spare capacity is required for full node protection compared with that only for link protection. In addition, we can observe that, with the same spare capacity as the p-cycles designed for link protection, 25% node-failure survivability can be achieved for free for each network instance. For GERMANY and COST239, up to 50% node-failure survivability can be achieved with the spare capacity used for the provision of link-protecting p-cycles.QoPp-cycle design.
(a)
(b)Figure2(b) shows the solution structure of the QoP p-cycle design, where each bar indicates the average number of links of optimally selected p-cycles for the indicated network instance and the indicated level of node-failure survivability. We can observe that, for network instance GERMANY, the higher the level of node-failure survivability is, the larger the average size of p-cycles is. However, the trends do not appear in network instances NJLATA and BELLCORE. For the instance COST239, due to its high density of the network topology, there are many chances existing to build the same size (the same number) of p-cycles while holding a different node-protection capability. As a result, the average size of optimally designed p-cycles keeps invariable upon the QoP level (Φ value) no more than 75%.


## 4.1. Date Instances

Four test networks are presented in Table1. For each network, we provide network name, the number of nodes, the number of links, and the node degree for approximately representing connectivity. Also, we list the number of demands carried on each network and the associated working capacity cost. Each element in the associated traffic matrices represents the number of requests between each node pair, which is uniformly distributed on the interval [1,…,20].Table 1
Network instances.
Networks
Nodes
Links
Node degree
Num. demands
Working capacity
GERMANY [16]
17
26
3.1
136
4034
BELLCORE [17]
15
28
3.7
105
2610
NJLATA [17]
11
23
4.2
55
943
COST239 [18]
11
26
4.7
55
792


## 4.2.  Experimental Comparison

Experimental results regarding capacity redundancy and the average size of thep-cycles are shown in Figure 2. In Figure 2(a), for the indicated network instance, each bar corresponds to the capacity redundancy of an optimal solution for the indicated level of node-failure recovery ratio (i.e., Φ values). Experimental results reveal that, with our proposed QoP design, p-cycles can provide 100% node-failure survivability (i.e., Φ=1) at marginal additional redundant spare capacity compared with those only for link protection (Φ=0), which ranges from ~1% to ~15%. The denser the network is, the less the redundant spare capacity is required for full node protection compared with that only for link protection. In addition, we can observe that, with the same spare capacity as the p-cycles designed for link protection, 25% node-failure survivability can be achieved for free for each network instance. For GERMANY and COST239, up to 50% node-failure survivability can be achieved with the spare capacity used for the provision of link-protecting p-cycles.QoPp-cycle design.
(a)
(b)Figure2(b) shows the solution structure of the QoP p-cycle design, where each bar indicates the average number of links of optimally selected p-cycles for the indicated network instance and the indicated level of node-failure survivability. We can observe that, for network instance GERMANY, the higher the level of node-failure survivability is, the larger the average size of p-cycles is. However, the trends do not appear in network instances NJLATA and BELLCORE. For the instance COST239, due to its high density of the network topology, there are many chances existing to build the same size (the same number) of p-cycles while holding a different node-protection capability. As a result, the average size of optimally designed p-cycles keeps invariable upon the QoP level (Φ value) no more than 75%.


## 5. Conclusion

In this paper, we investigated the design ofp-cycles with the differentiated levels of the node-failure survivability in WDM mesh networks. The main goal is to develop a capacity-efficient and scalable design method. Our proposed design method enhances the p-cycle protection capabilities. A p-cycle can protect multiple affected paths upon a node failure. In order to manage the scalability issue suffered in the conventional design method, this paper exploited the large-scale optimization techniques, that is, column generation (CG). Based on CG, our proposed method generates the p-cycle candidates dynamically as needed in the course of the optimization process.Extensive experiments have been conducted. Experimental results show clearly that, with our proposed design method,p-cycles can provide full node protection at a marginal additional redundant capacity compared with those for link protection only. For some instances, up to 50% node-failure survivability can be achieved for free with spare capacity used only for link protection.



---

*Source: 920564-2013-08-27.xml*