# Novel P-Cycle Selection Algorithms for Elastic Optical Networks

Rujia Zou, Suresh Subramaniam

► To cite this version:

Rujia Zou, Suresh Subramaniam. Novel P-Cycle Selection Algorithms for Elastic Optical Networks. 23rd International IFIP Conference on Optical Network Design and Modeling (ONDM), May 2019, Athens, Greece. pp.154-167, 10.1007/978-3-030-38085-4_14 . hal-03200676

HAL Id: hal-03200676

https://inria.hal.science/hal-03200676

Submitted on 16 Apr 2021

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Novel P-Cycle Selection Algorithms for Elastic Optical Networks

Rujia Zou[0000-0002-4855-2715] and Suresh Subramaniam[0000-0003-1501-5953]

The George Washington University, Washington, DC 20052, USA
{rjzou, suresh}@gwu.edu

**Abstract.** Elastic optical networks (EONs) promise to provide high spectrum utilization efficiency due to flexibility in resource allocation. Survivability is regarded as an important aspect of EONs. P-cycle protection is very attractive for EONs due to fast restoration and high protection efficiency. P-cycles have been extensively studied for conventional fixed-grid WDM networks; however, p-cycle design and selection for EONs has received much less attention. In this paper, we consider the design and selection of p-cycles for EONs with distance-dependent modulation. We propose two novel link-based p-cycle evaluation methods: individual p-cycle selection and p-cycle set selection for EONs. Based on these methods, two p-cycle design algorithms, namely, Traffic Independent P-cycle Selection (TIPS) and Traffic-Oriented P-cycle Selection (TOPS), are proposed to find the best set of p-cycles that is able to provide 100% failure-dependent protection against single link failures. We evaluate our algorithms using both static and dynamic traffic models. Simulation results indicate that the proposed algorithms have better performance than commonly used baseline algorithms.

**Keywords:** Elastic Optical Network · Survivability · P-cycle.

## 1 Introduction

With the dramatic growth of network traffic, elastic optical networks (EONs) have arisen as an efficient solution due to their flexibility in resource allocation and spectrum assignment [6]. The resource in EONs is assigned as frequency slot (FS) instead of wavelength. Therefore, the routing and wavelength assignment problem in Wavelength Division Multiplexing (WDM) optical networks has evolved into the Routing and Spectrum Assignment (RSA) problem with spectrum continuity and spectrum contiguity in EONs [1].

Survivability is regarded as an important aspect for optical networks, and many methods have been developed for protection [4, 10, 12, 13]. Among these methods, p-cycle protection is considered to be particularly promising due to fast restoration and high protection efficiency. The key feature of p-cycle protection is that the backup capacity is pre-connected by ring-like structures. Compared with ring protection, p-cycle is able to support the protection of both on-cycle link and straddling link, which leads to huge advantages in protection efficiency. An attractive feature of failure-independent p-cycles is that the protection switches can be pre-configured, leading to very fast switchover times in the event of a
failure. P-cycles can also be designed to provide failure-dependent link protec-
tion, i.e., the p-cycles may share some links; in this case too, all protection
switches, except the switches at the forking points of two shared cycles, can
be pre-configured before the failure. There exists some research on link-based
p-cycle protection in EONs. In [7], a heuristic link-based p-cycle protection
algorithm with spectrum sharing and defragmentation is investigated. Several
dynamic p-cycle protection algorithms with spectrum planning are discussed
in [5]. A service availability-oriented p-cycle algorithm for dynamic EONs is
studied in [2]. A failure-independent path protection p-cycle approach in EONs
is designed with modulation format consideration in [3]. Nevertheless, p-cycle
selection and p-cycle set evaluation for EONs are still under-explored.

In this work, we study link-based p-cycle protection in EONs and aim to
provide 100% failure-dependent protection against any single link failure. We
design two novel p-cycle evaluation methods for EONs based on two cost metrics:
individual p-cycle cost and p-cycle set cost. Both of these methods consider the
physical distance and usable modulation level. Then, two heuristic algorithms
are proposed to generate p-cycles: Traffic-Independent P-cycle Selection (TIPS)
and Traffic-Oriented P-cycle Selection (TOPS). The contributions of our work
can be summarized as follows:

- We propose a novel pair of p-cycle cost metrics, i.e., individual p-cycle cost and p-cycle set cost, and corresponding p-cycle evaluation methods, to select p-cycles that can provide 100% failure-dependent protection in EONs. To the best of our knowledge, this is the first paper that considers both individual p-cycle and set of p-cycles evaluation in EONs.

- We propose two heuristic algorithms to select p-cycles with and without traffic information.

- Simulation results show the effectiveness of our metrics and algorithms for both static and dynamic traffic.

2 Motivation and Problem Statement

2.1 Motivation

In p-cycle protection, different sets of p-cycles may lead to different performance of protection. Therefore, p-cycle selection is the core part of the protection scheme. There are many papers that have studied p-cycle evaluation and selec-tion. In [8], a mixed integer linear programming model is formulated to minimize the total power consumption for p-cycle protection. However, this work does not allow for spectrum sharing between protection cycles if the corresponding work-ing paths have no common link. In [14,15], all the candidate cycles in a network are ranked using a metric called A Priori Efficiency (AE). The set of p-cycles that is used for protection is determined by using different limited numbers of top-ranked candidate cycles for ILP designs, but AE was not designed specifically for EONs. A load-balance-aware p-cycle protection heuristic algorithm and an ILP formulation are proposed in [16]. An individual p-cycle is evaluated with traffic load balance, but physical distance and modulation format are not considered. In [9], a distance-adaptive p-cycle protection algorithm without candidate cycle enumeration in mixed-line-rate optical networks is proposed, and an individual
p-cycle is evaluated with transponder cost and spare capacity cost. However, the p-cycle evaluation and spectrum assignment are designed without frequency slot consideration.

None of the above papers consider optical signal modulation format and length of the p-cycle. For instance, since the modulation format is determined by the physical distance of p-cycle, large cycles have to be assigned a lower level modulation format for protection while small cycles can be assigned higher level modulation to achieve better spectrum efficiency. The length of p-cycle also influences the protection efficiency. A large p-cycle implies more FSs are needed to protect from a single link failure, but the protection capacity can be shared among many links. A small p-cycle requires fewer FSs for each failure, but small p-cycles have a lower probability of having straddling links, leading to a lower efficiency. Besides these conventional trade-offs, distance-dependent modulation in EONs requires that the physical length of p-cycles also be considered in the evaluation and selection of a p-cycle.

For example, given a network, consider two sets of p-cycles that can provide 100% protection: one consists of several small cycles, and the other is a large Hamiltonian cycle. The performance of these two sets of p-cycles (e.g., amount of protection bandwidth needed) will be different of course. Further, in the small p-cycle case, choosing the best individual p-cycles one by one until the network is fully protected does not mean that the entire set of cycles is collectively a good set of p-cycles, as bandwidth sharing among p-cycles may not be high in this case. Metrics and evaluation methods for a set of p-cycles that collectively protect every link in the network and which considers the above factors are therefore needed.

## 2.2 Problem Statement

We formally define the problem as follows. Given a network $G(N, E)$, where $N$ represents the node set and $E$ represents the link set. On each link $e$, a pair of fibers (with opposite directions) is used for working paths, and a pair of fibers is used for the p-cycle protection paths. A set of unidirectional lightpath request set $R$ is given, where each lightpath is represented as $r(s, d, w)$, $s$ and $d$ denotes the source and destination nodes, and $w$ denotes the lightpath data rate. Assume there are several modulation formats with different spectrum efficiencies and distance limitations. The objective is to select a set of p-cycles that is able to provide full link-protection with the minimum possible protection bandwidth. This problem includes two parts. One is the RSA problem for each request $r$, the other is the assignment of a protection path with a set of p-cycles for each link along the working path of request $r$. We assume that spectrum conversion is not allowed.

# 3 P-Cycle Evaluation

Now we present our methods to evaluate an efficient set of p-cycles for 100% link-protection. Our first approach is applicable when the p-cycles are designed without a priori knowledge of the traffic requests, for instance, in a dynamic traffic scenario. When the set of lightpath requests is known a priori, as in typical provisioning problems, it is possible to use this information to design a
set of p-cycles that is tailor-made for this set of lightpaths. We call these the Traffic-Independent P-Cycle Selection and the Traffic-Oriented P-Cycle Selection methods, respectively. For each of the design methods, we propose cost metrics to evaluate a single p-cycle as well as a set of p-cycles in this section.

## 3.1 Traffic-Independent P-cycle Selection (TIPS)

Here, we aim to design a set of p-cycles that provide 100% protection when the traffic is not known ahead of time. We first propose the individual and set cost metrics here and the p-cycle selection algorithms are presented in the next section.

**Individual Cycle Protection Cost** In order to evaluate the efficiency and cost of cycles with different modulation formats, the novel metric Individual Cost for TIPS ($IC_{TIPS}$) is proposed. It is given by:

$$IC_{TIPS} = \frac{M \times L}{S} \times A \qquad (1)$$

where $M$ is the modulation index, $L$ is the number of links on the p-cycle, and $S$ is the number of links that can be protected by the p-cycle. $A$ is the average protection distance (in hops). $A$ is calculated by finding the number of hops on the p-cycle for each potential failed link, and then calculating the average number of hops. The rationale for this cost is as follows. A higher level modulation has lower value of $M$ indicating that fewer slots are needed for a given data rate. Here, since we do not know the working paths, $M$ is determined by the physical length of the p-cycle. For BPSK, QPSK, and 8QAM, the corresponding spectrum efficiencies are 1, 2, and 3 bits/s/Hz; therefore we choose the corresponding $M$ as 1, 0.5, and 0.34, respectively [5]. The modulation index represents the required spectrum resource normalized by that for the lowest modulation level, to support the same transmission bandwidth as its corresponding protection cycle.

The ratio $L/S$ is a measure of the protection bandwidth needed per protected link of the p-cycle – since every on-cycle link is allocated protection bandwidth but straddling links are not. $A$ is designed to capture the risk of unshareable protection due to load imbalance. If the working capacity on a link is higher than on other links, a p-cycle with larger $A$ implies a larger number of backup FSs for an individual link failure.

We need to emphasize that Individual Cost (IC) is a metric for an individual p-cycle that is based purely on the network topology. A p-cycle with a lower IC is expected to be more efficient than a p-cycle with a higher IC.

**Cycle Set Protection Cost** As p-cycles may overlap with each other, and since a link is only protected by one p-cycle, adding the ICs of the p-cycles in a set of p-cycles may not be an effective cost metric for a set of p-cycles. The evaluation of a set of p-cycles is based on p-cycle Set protection Cost (SC). Since overlap between p-cycles in a set is possible, we assume that every link is protected by the lowest IC p-cycle from the selected set that can provide protection to this link. If a link can be protected by multiple p-cycles that have the same lowest IC, which is unlikely to happen, the link will be assigned to one
of them at random. The SC is calculated as follows:

$$SC_{TIPS} = \sum_{p \in \mathbf{P}} M_p \times A_p \times N_p \qquad (2)$$

where **P** is the set of candidate p-cycles that provides full protection for the network, *p* is an individual p-cycle in the set, $M_p$ is the modulation index of *p*, and $A_p$ is the average protection distance of *p* in hops, and $N_p$ is the number of links protected by *p*. As before, smaller *M* and *A* indicate that fewer protection FSs are required. $N_p$ is a measure of the possibility of unshareable protection and load imbalance. The more links that are protected by the p-cycle, the higher the risk of load imbalance. We need to emphasize that not all the links that can be protected by a p-cycle are in fact protected by this p-cycle due to the overlapping of p-cycles. A p-cycle set with a lower SC is expected to a better set of cycles and is encouraged to be used for protection.

## 3.2 Traffic Oriented P-cycle Selection (TOPS)

**Individual Cycle Protection Cost** In TOPS, the p-cycle evaluation and selection are based on the given traffic. Given a set of lightpath requests with data rate in Gbps, we first route all the lightpath requests without any spectrum assignment using Dijkstra's shortest path algorithm with physical distance. We use the total data rate on each link when evaluating the p-cycles. The IC and SC for TOPS are calculated as follows:

$$IC_{TOPS} = M \times D_{\max} \times L^2 \qquad (3)$$

where *M* is the modulation index (same as in *TIPS*), $D_{\max}$ is the maximum data rate over all the links that can be protected by this cycle, and *L* is the length of the cycle in hops. *M*, $D_{\max}$ and *L* are used to measure the consumption of backup FSs in full protection sharing scenario. We use another factor of *L* here to capture the risk of unshareable protection FSs. If the backup FSs of a link cannot be shared with other links, the backup capacity is increased, and a larger *L* indicates more backup extra FSs.

**Cycle Set Protection Cost** In TOPS, the cycle set evaluation is also based on data rate. The SC is calculated as follows:

$$SC_{TOPS} = \sum_{p \in \mathbf{P}} M_p \times D_{p, \max} \times L_p \times N_p \qquad (4)$$

where **P** is the set of p-cycles that provides full protection, $D_{p, \max}$ is the maximum data rate over all the links that are protected by p-cycle *p*, $L_p$ is the length of *p* in hops, and $N_p$ is the number of links that are assigned to be protected by *p*. Smaller *M*, $D_{\max}$, and *L* indicate fewer backup FSs required, while larger *N* indicates higher unshareable consumption and lower possibility for a full sharing scenario. The p-cycle set that has a lower $SC_{TOPS}$ is considered to be better.

# 4 Static P-Cycle Set Generation and RSA

## 4.1 Cycle Generation

In this subsection, we describe the algorithm for finding a set of p-cycles based on IC and SC. This algorithm is used in both TIPS and TOPS, and the pseudocode is shown in Algorithm 1.
<caption>**Algorithm 1 Finding a set of p-cycles**</caption>

**Require:** Network topology
**Ensure:** A candidate set of p-cycles
1: **while** the network is not fully protected **do**
2: Randomly select an unprotected link *l*
3: Use Dijkstra's algorithm with physical distance to find a shortest path *sp* between the two ends of the link
4: Merge *l* and *sp* as a p-cycle *p* and initialize the candidate p-cycle as *p*
5: Calculate *IC* for *p* as *p*<sub>IC</sub>
6: Initialize *IC*<sub>min</sub> as *p*<sub>IC</sub>
7: **while** EXPAND_P-CYCLE(*p*) ≠ NULL **do**
8: &nbsp;&nbsp;&nbsp;&nbsp;*p*′ = EXPAND_P-CYCLE(*p*)
9: Calculate the *IC* of *p*′ as *p*'<sub>IC</sub>
10: **if** *p*'<sub>IC</sub> < *IC*<sub>min</sub> **then**
11: Update the candidate p-cycle to *p*'
12: Update *IC*<sub>min</sub> to *p*'<sub>IC</sub>
13: **end if**
14: *p* = *p*'
15: **end while**
16: Add the candidate p-cycle to p-Cycle set P
17: Mark links that can be protected by candidate cycle as protected.
18: **end while**

We start by randomly finding a link *l* in the network. Then we find a shortest path *sp* between two ends of this link. Let the selected link *l* and the path *sp* be combined to form a basic p-cycle *p*. Calculate the IC for this p-cycle and mark this p-cycle as a candidate p-cycle.

Continue to expand the p-cycle unless the p-cycle cannot be expanded further. The pseudocode of expanding p-cycle is shown in Algorithm 2. For each expanding step, assume that the p-cycle after expanding is *p'*. Calculate the *IC* of *p'*. If the *IC* of *p'* is lower than *IC*<sub>min</sub>, update the candidate p-cycle to *p'* and update *IC*<sub>min</sub> to *p*'<sub>IC</sub>. After the expansion phase is over, put the candidate p-cycle into the p-cycle set and mark the links that can be protected by this p-cycle as *protected*. If the network is not fully protected, randomly select a link that is not protected and add another candidate p-cycle into the cycle set again and continue. After all the links in the network are marked as protected, we have a set of p-cycles that can be used to protect the network.

The above procedure produces a “good” p-cycle set since we used IC to expand the p-cycles, but the p-cycle set is also somewhat random because since the starting link and expansion phase for each p-cycle are based on randomly selected links. We generate a large number of such p-cycle sets (by using different random links as starting link for each p-cycle and while expanding). Then, we choose the best p-cycle set among these as the set with the lowest SC. Later,
we will compare the performance of such a p-cycle set (simply called *Best*) with some baseline algorithms for selecting p-cycle sets.

<caption>**Algorithm 2 EXPAND_P-CYCLE**</caption>

**Require:** p-cycle *p*
**Ensure:** Larger p-cycle *p*'
1: Randomly select an on-cycle link *l* on cycle *p*
2: Mark two ends of *l* as *a*, *b*
3: Remove all the links on *p* from the network
4: Use Dijkstra's algorithm with physical distance to find the shortest route *R* in physical distance between *a* and *b*
5: **if** *R* does not exist **then**
6:     **goto** line 1
7: **end if**
8: Merge *R* and *p* as the new cycle *p*'

## 4.2 Routing and Spectrum Assignment

This section focuses on routing and spectrum assignment for the working paths and p-cycle protection. This process is separated into two steps: p-cycle selection and spectrum assignment. Both TIPS and TOPS use this RSA algorithm.

In TIPS, the Best p-cycle set can be found purely based on topology. In TOPS, the working paths are first routed without spectrum assignment by using Dijkstra's shortest path algorithm and the maximum data rate on links is recorded. Then the IC and SC for TOPS are used to find the Best p-cycle set.

In the spectrum assignment step, first we use Dijkstra's shortest path algorithm to find a route for the working path. Then we fail the links on this working path one by one. For each failed link, we select the p-cycle with minimum IC to protect this link. The total physical distance of the protection path can be calculated by adding up the length of the working path (excluding the failed link) and the length of the protection path on the protection cycle for the failed link. Note that we use the shorter of the two cycle paths for protecting straddling links. The highest modulation index that is acceptable for this total length is then recorded, and the minimum of these modulation indexes (over all failed links) is then chosen as the modulation index for this lightpath. No matter which link fails, the lowest modulation index guarantee that the transparent transmission distance constraint is satisfied. After the modulation format is selected, the spectrum assignment is completed by using the first fit method if slots are available. Otherwise, the request is blocked.

We adapt the above approaches for dynamic traffic as follows. Since the lightpath requests are unknown in advance in this case, TIPS are used for dynamic traffic case. Therefore, a set of p-cycles based on IC and SC are generated in advance, and only RSA is performed and a modulation is selected when a new lightpath request arrives. The request is blocked without any assignment if FSs are not available for the request.
5 Simulation Results

In this section, simulation results are presented to demonstrate the effectiveness of our proposed p-cycle design methods under both static and dynamic traffic. The network topologies used for simulations are the COST239 network and the pan-European network. The COST239 network consists of 11 nodes and 26 links (shown in Fig. 1), while the pan-European network consists of 28 nodes and 44 links (shown in Fig. 2). The physical distance in km is shown adjacent to the links. On each link in the network, a pair of working fibers in opposite directions are used for working path, and a pair of protection fibers in opposite directions are used for protection. In static traffic model, a set of unidirectional traffic

<figure><img src="image_2.png" /><figcaption>Fig. 1: 11-node COST239 network.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2: 28-node pan-European network.</figcaption></figure>

requests is to be assigned a working path and protection path in the network. The source and destination nodes for each connection request are uniformly randomly selected from the nodes of the network. We assume three different types of demands with rate 40/100/400 Gbps. The data rate is generated from the following distribution: 40 Gbps, 100 Gbps, and 400 Gbps with probability 0.2, 0.5, and 0.3, respectively. The number of required FSs for a lightpath is determined by its data rate and modulation format. Table I shows the number of FSs corresponding to different data rates under different modulation formats [13]. The performances are evaluated in terms of spectrum usage per link (the total number of used FSs for both working and protection on all links divided by number of links in the network). Moreover, in order to evaluate the spectrum usage without blocking, we assume that there are an unlimited number of FSs on each fiber.

In dynamic traffic model, the lightpath requests arrive to the network according to a Poisson process with different arrival rates. Each request has a mean duration time of 1 (arbitrary time unit) with exponential distribution. The distribution of data rate of requests is the same as before. The highest FS available on each fiber is assumed to be 352. We use the demand blocking ratio of dynamic traffic requests to indicate the performance of p-cycle selection and protection. For each simulation, the results of 1 million dynamic requests are computed.

For each modulation format, the physical distance limitations are shown in Table II [13]. The modulation index in p-cycle evaluation and selection are also
determined by this limitation. In our tests, we assume that there is no physical distance limitation for BPSK in order to guarantee that all the requests can be established in the static case. We also present the bandwidth blocking ratio if the distance limit for BPSK is set to 4000 km.

For p-cycle selection, the Best p-cycle set is found in advance by generating a large number of (≈ 3000) p-cycle sets and selecting the one with the lowest SC, which is $SC_{TIPS}$ for TIPS and $SC_{TOPS}$ for TOPS. While the p-cycle sets in TIPS are based only on topology, the sets are also based on the traffic and data rate in TOPS, as explained earlier. We compare the Best p-cycle set

<table><caption>Table 1
Number of required FSs for various data rates and modulations [13].</caption><thead><tr><th rowspan="2">Modulation</th><th colspan="3">Date Rate</th></tr><tr><th>40</th><th>100</th><th>400</th></tr></thead><tbody><tr><td>8QAM</td><td>2</td><td>3</td><td>11</td></tr><tr><td>QPSK</td><td>3</td><td>5</td><td>17</td></tr><tr><td>BPSK</td><td>4</td><td>9</td><td>33</td></tr></tbody></table>

<table><caption>Table 2
Physical distance limitation for different modulations [13].</caption><thead><tr><th>Modulation</th><th>Transparent Reach</th></tr></thead><tbody><tr><td>8QAM</td><td>1000km</td></tr><tr><td>QPSK</td><td>2000km</td></tr><tr><td>BPSK</td><td>&gt; 2000km</td></tr></tbody></table>

selection algorithm with the following three baseline algorithms for p-cycle set selection: namely, random cycle set (Random), top individual p-cycle set (TopIC), Hamiltonian cycle [11],<fnref n="1" /> and top A Priori Efficiency p-cycle set (TopAE). A Priori Efficiency (AE, $AE = \sum_{i \in E} \chi_{ij} / (\sum_{k \in E} \delta_{kj} \times C_k)$, where $\chi_{ij}$ refers to the number of paths can be provided by the cycle j if link i fails; the possible values are 0, 1 for on-cycle link and 2 for straddling link; $\delta_{kj}$ is a binary parameter that equals 1 if link i is on cycle j and 0 otherwise; $C_k$ is the cost of link k and which is assumed 1 in this work) was proposed as a single p-cycle evaluation for WDM networks without modulation and spectrum sharing consideration [14, 15]. For Random, TopIC, and TopAE, the set $C$ of all candidate cycles is first generated offline in advance using a depth-first-search algorithm. In Random, a random p-cycle set is formed by randomly selecting cycles from $C$ one by one until the network is fully protected. In TopIC and TopAE, the cycles in $C$ are sorted based on IC or AE, respectively, in non-decreasing order, and the TopIC p-cycle set and TopAE p-cycle set are formed by selecting cycles in this order until the network is fully protected. In both cases, only cycles that protect at least one as-yet unprotected link will be added to the p-cycle set.

## 5.1 Performance Analysis

Fig. 3 and Fig. 4 show the results for spectrum usage (i.e., number of FSs used per link) in COST239 and pan-European network respectively. We make several observations from the results. First, we compare the Best cycle set with Hamiltonian cycle and Random cycle set. There is an improvement of more than about

<footnote n="1">¹ Both the topologies in this paper have a Hamiltonian cycle.</footnote>
40% in spectrum usage in COST239 network, while the improvement is more
than about 20% in pan-European network. The Best cycle set has a better per-
formance because we select cycles with lower individual cost and cycle set cost.
Compared with TopAE, the Best and TopIC p-cycle sets have much better

<figure><img src="image_4.png" /><figcaption>Fig. 3: Spectrum Usage in COST239.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4: Spectrum Usage in COST239.</figcaption></figure>

performance, which shows the need for an improved p-cycle evaluation method
which takes modulation and cycle size into account in EONs. Moveover, the re-
sults show that the cycle set consisting of the top individual cycles is not the
best cycle set. This demonstrates the effectiveness of cycle set evaluation. Since
we take load balance risk into account when the IC is measured, the TopIC
cycle sets have a good performance as well. Moreover, for the Best cycle set,
the performance of TOPS is better than TIPS, because TOPS also takes into
account traffic and data rate. Suppose we assume that there is a 4000 km phys-
ical distance limitation for BPSK. In COST239, the bandwidth blocking ratio
for all the proposed algorithms and baseline algorithms are lower than 0.5%. In
pan-European network, the bandwidth blocking ratio for TOPS-Best, TOPS-
TopIC, TIPS-Best, and TIPS-TopIC are lower than 1%, whereas it is 94% and
<figure><img src="image_6.png" /><figcaption>Fig. 5: Demand blocking ratio in COST239.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 6: Demand blocking ratio in pan-European.</figcaption></figure>

91% for the Hamiltonian cycle and random cycle sets, respectively, due to the large network size. Therefore with physical distance limitation, large cycles are even more vulnerable to failure and blocking.

Fig. 5 and Fig. 6 show the result of blocking ratio under dynamic traffic for the COST239 and Pan-European networks. We can see that the Best cycle set has the best performance. In pan-European network, the p-cycles in TopIC tend to be small-sized cycles and are likely to be assigned high modulation index, therefore the blocking ratio is similar to the Best cycle set.

# 6 Conclusion

P-cycles are attractive for protection in optical networks because of their fast switching. In this work, we propose metrics to evaluate the cost of an individual p-cycle as well as a set of p-cycles, and use these metrics to generate a set of p-cycles that can provide 100% protection against single-link failures in EONs. Unlike previous work, our costs and cycle generation and selection algorithms consider factors such as path length, modulation index, and shareability of links. We proposed algorithms to select p-cycles both in the absence of traffic knowledge (Traffic-Independent P-cycle Selection, TIPS) and with traffic knowledge (Traffic-Oriented P-cycle Selection, TOPS). From extensive simulation results, we observed that the performances of the proposed selection algorithms are sig-
nificantly better than baseline algorithms in terms of required spectrum and blocking ratio.

## Acknowledgment

This work was supported in part by NSF grants CNS-1818858 and CNS-1813617.

## References

1. Cai, A., Guo, J., Lin, R., Shen, G., Zukerman, M.: Multicast routing and distance-adaptive spectrum allocation in elastic optical networks with shared protection. Journal of Lightwave Technology 34(17), 4076-4088 (2016)

2. Chen, X., Ji, F., Zhu, Z.: Service availability oriented p-cycle protection design in elastic optical networks. IEEE/OSA Journal of Optical Communications and Networking 6(10), 901-910 (2014)

3. Chen, X., Zhu, S., Jiang, L., Zhu, Z.: On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks. Journal of Lightwave Technology 33(17), 3719-3729 (2015)

4. Eshoul, A.E., Mouftah, H.T.: Survivability approaches using p-cycles in wdm mesh networks under static traffic. IEEE/ACM Transactions on Networking (TON) 17(2), 671-683 (2009)

5. Ji, F., Chen, X., Lu, W., Rodrigues, J.J., Zhu, Z.: Dynamic p-cycle protection in spectrum-sliced elastic optical networks. Journal of Lightwave Technology 32(6), 1190-1199 (2014)

6. Jinno, M., Takara, H., Kozicki, B., Tsukishima, Y., Sone, Y., Matsuoka, S.: Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies. IEEE communications magazine 47(11), 66-73 (2009)

7. Ju, M., Zhou, F., Xiao, S., Wu, H.: Leveraging spectrum sharing and defragmentation to p-cycle design in elastic optical networks. IEEE Communications Letters 21(3), 508-511 (2017)

8. Ju, M., Zhou, F., Xiao, S., Zhu, Z.: Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks. Journal of Lightwave Technology 34(17), 4053-4065 (2016)

9. Ju, M., Zhou, F., Zhu, Z., Xiao, S.: Distance-adaptive, low capex cost p-cycle design without candidate cycle enumeration in mixed-line-rate optical networks. Journal of Lightwave Technology 34(11), 2663-2676 (2016)

10. Oliveira, H.M., da Fonseca, N.L.: Algorithm for fipp p-cycle path protection in flexgrid networks. In: 2014 IEEE Global Communications Conference. pp. 1278-1283. IEEE (2014)

11. Schupke, D.A.: On hamiltonian cycles as optimal p-cycles. IEEE communications letters 9(4), 360-362 (2005)

12. Shen, G., Guo, H., Bose, S.K.: Survivable elastic optical networks: survey and perspective. Photonic Network Communications 31(1), 71-87 (2016)

13. Wang, C., Shen, G., Bose, S.K.: Distance adaptive dynamic routing and spectrum allocation in elastic optical networks with shared backup path protection. Journal of Lightwave Technology 33(14), 2955-2964 (2015)

14. Wei, Y., Xu, K., Jiang, Y., Zhao, H., Shen, G.: Optimal design for p-cycle-rotected elastic optical networks. Photonic Network Communications 29(3), 257-268 (2015)

15. Wei, Y., Xu, K., Zhao, H., Shen, G.: Applying p-cycle technique to elastic optical networks. In: 2014 International Conference on Optical Network Design and Modeling. pp. 1-6. IEEE (2014)

16. Wu, J., Liu, Y., Yu, C., Wu, Y.: Survivable routing and spectrum allocation algorithm based on p-cycle protection in elastic optical networks. Optik-International Journal for Light and Electron Optics 125(16), 4446-4451 (2014)