Sabidur Rahman
email: krahman@ucdavis.edu

Tanjila Ahmed
email: tanahmed@ucdavis.edu

Sifat Ferdousi
email: sferdousi@ucdavis.edu

Partha Bhaumik
email: pbhaumik@ucdavis.edu

Pulak Chowdhury
email: pchowdhury@ucdavis.edu

Massimo Tornatore
email: massimo.tornatore@polimi.it

Goutam Das
email: gdas@gssst.iitkgp.ac.in

Biswanath Mukherjee
email: bmukherjee@ucdavis.edu

Virtualized Controller Placement for Multi-domain Optical Transport Networks

Keywords: SDN and optical controller, optical transport network, cost savings, network virtualization, edge computing

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.

Introduction

Existing proposals for controller placement [START_REF] Wang | The controller placement problem in software defined networking: a survey[END_REF] have focused mostly on packetswitched Software-Defined Networks (SDNs) and they often ignore the complexity, heterogeneity, and vendor specificity of a transport-network control plane. Current technical solutions for transport-network control planes (e.g., Transport SDN, T-SDN) are designed for circuit-switched layer 0 (optical) and layer 1 (SONET/ SDH and OTN). T-SDN supports multi-layer, multi-vendor, circuitoriented networks that are different from packet-based SDN-controlled networks [START_REF] Alvizu | Comprehensive survey on T-SDN: Software-defined networking for transport networks[END_REF]. The control plane for optical transport networks employs a hierarchical distributed architecture [START_REF] Lopez | Control plane architectures for elastic optical networks[END_REF] comprising heterogeneous (often vendor-specific) Optical Network (ON) Controllers (ONC) and SDN Controllers (SDNC).

Our study considers that T-SDN controllers can be deployed as virtualized controller instances (as in [START_REF] Munoz | Integrated SDN/NFV management and orchestration architecture for dynamic deployment of virtual SDN control instances for virtual tenant networks[END_REF]). Virtualized controller placement has many benefits. First, manually deploying SDN and ON controllers in traditional 'hardware boxes' can take several days, compared to few minutes in case of virtualized instances (hosted on Virtual Machines (VMs), docker containers, etc.) in the cloud datecenter (DCs) or in computing nodes at edge datacenters (Edge-DCs) (such as Network Function Virtualization Infrastructure Points of Presence (NFVI-PoPs), metro datacenters (DCs), or Central Offices Re-architected as Datacenters (CORDs), etc.). Second, virtualized controllers can be easily recovered from failures or disasters using the backed-up/replicated virtual copy of the controllers. These instances can be easily moved from one location to another and can be redeployed [START_REF] Rahman | Dynamic Workload Migration over Optical Backbone Network to Minimize Data Center Electricity Cost[END_REF] without significant down time. Third, operational cost savings for network operators and leasing cost savings for network leasers are other important motivations toward virtualization.

Prior studies exploring static [START_REF] Heller | The Controller Placement Problem[END_REF] [8], and dynamic [START_REF] Sallahi | Optimal Model for the Controller Placement Problem in Software Defined Networks[END_REF] controller placement problems mostly focused on packet-based SDN controllers and DC networks [10] [11]. But, as we discuss in Section II, methods proposed in SDN and DC scenarios are often not applicable and not optimal for heterogeneous optical transport networks.

To the best of our knowledge, our study is the first to propose dynamic placement of controllers for heterogeneous, multi-domain transport networks comprising heterogeneous ON and SDN controllers, considering the complexity due to virtual instances hosted jointly on DCs and Edge (e.g. NFVi-PoPs), and inter-domain and intra-domain latency constraints. In addition, we observe that [START_REF] Alvizu | Comprehensive survey on T-SDN: Software-defined networking for transport networks[END_REF] [4] both fixed-grid and flex-grid technologies might be required to co-exist (i.e., mixed-grid) with seamless interoperability (see Fig. 1). In this context, our proposed method can support the deployment of different controller types, by enforcing 'controller-type constraint' (e.g., flex-grid controllers for flex-grid domains, fixed-grid controllers for fixed-grid domains, etc.). In addition, we explore the technical details of the dynamic controller placement problem (e.g., latency requirements, resource limitations at Edge-DCs, controller capacity limitations, etc.), propose the Virtualized Controller Deployment Algorithm (VCDA), and report illustrative results comparing with prior studies.

This study is organized as follows. Section II reviews prior work on controller placement problems. Section III discusses the control-plane architecture. Section IV provides a formal problem statement and describes the proposed solution method. Section V discussed numerical results on cost savings and delay minimization. Section VI concludes the study.

Background and Related Work

In the context of SDN controllers, both static [START_REF] Heller | The Controller Placement Problem[END_REF] [8], and dynamic [START_REF] Sallahi | Optimal Model for the Controller Placement Problem in Software Defined Networks[END_REF] placement problems have been explored. But most studies on SDN Controller Placement Problems (CPPs), e.g., [START_REF] Heller | The Controller Placement Problem[END_REF]- [START_REF] Sallahi | Optimal Model for the Controller Placement Problem in Software Defined Networks[END_REF], consider placement of only controller 'middleboxes', not virtualized instances. Ref. [START_REF] Savas | Disaster-resilient control plane design and mapping in softwaredefined networks[END_REF] considers recovery of SDN controllers in a disaster scenario. These early studies do not consider the additional complexities due to virtualization, delay constraints, hosting location constraints, etc.

Recently, control-plane architectures [12] [16] in T-SDN paradigm are proposed to accommodate multiple heterogeneous network domains and associated domain-specific ON controllers. But, as recent studies [START_REF] Alvizu | Comprehensive survey on T-SDN: Software-defined networking for transport networks[END_REF] [16] suggests, there is still no consensus on the design of the T-SDN control plane. Ref. [START_REF] Munoz | Integrated SDN/NFV management and orchestration architecture for dynamic deployment of virtual SDN control instances for virtual tenant networks[END_REF] was among the first to propose a virtualized control plane architecture for transport networks, but not from placement perspective.

Recent studies [10] [11] on Elastic Control Placement (ECP) for SDN controllers discuss threshold-based methods to dynamically resize the ECPs. Ref. [START_REF] Kim | T-DCORAL: A Threshold-based Dynamic Controller Resource Allocation for Elastic Control Plane in Software-Defined Data Center Networks[END_REF] focuses on DC networks managed through homogeneous SDN controllers, minimizing control-plane resizing delay. Refs. [10] [11] consider DC placement (of controller instances), which is practical for a DC network scenario. But, for a transport network with distributed heterogeneous domains, we also consider joint deployment in DCs and Edge-DCs. This introduces new constraints such as host location capacity, and inter-domain and intra-domain communication delays (which [10] [11] do not consider).

Control Plane Architecture

Fig. 1 shows an example of a hierarchical control plane for heterogeneous transport networks. Domain-specific controllers are connected with 'parent controller(s)', which are connected to the 'application plane' (e.g., Transport Network Orchestrator (TNO), Operations Support Systems (OSS), etc.). 'Domain Controllers' are responsible for the communication between 'control plane' and 'data plane'. Different autonomous domains, depending on the underlying ONC/SDNC, use specific type of controllers and protocols to control the 'data plane' switches. Fig. 1 shows three types of domains. This example architecture can be extended to support more variations of domain controllers and associated technologies.

Problem Statement

The controller-placement problem is known to be NP-hard [START_REF] Wang | The controller placement problem in software defined networking: a survey[END_REF]. Traditional dynamic controller placement methods [START_REF] Sallahi | Optimal Model for the Controller Placement Problem in Software Defined Networks[END_REF] [10] focus on the 'switch-to-controller' mapping, ensuring that each switch (forwarding plane) is connected to at least one controller (control plane); incoming traffic flow requests originated inside a domain will be served by the same controller; and controller capacity limit is preserved. When a new traffic flow request arrives, the 'switch' depends on the controller for routing and path computation decisions.

The dynamic 'on-demand' controller deployment problem can be defined as follows: Given a topology, a set of controller hosting locations with limited capacity, arrival rate of traffic flows, a set of heterogeneous network domains, controller capacity, and constraints, deploy optimal number of controllers to satisfy all the domains, minimizing the leasing costs. -C T : variable containing total cost of running the controllers in all the domains (more details in Section IV.D).

Constraints

We consider the following constraints:

1. Latency constraints: Controllers must be placed within the allowed latency limit, i.e., switch-to-controller and controller-to-switch delay, including processing delay must not exceed the allowed delay limit:

D(s, h) + D p + D(h, s) ≤ α; ∀s S v , ∀h V (1)
where function D(x, y) represents transmission, propagation, and processing delay between points x and y, s is origin, h is controller hosting location, and D p is processing delay at controller instances M v . 2. Controller type constraint: To reflect heterogeneity, we enforce the following controller type constraints:

T v == M t v ; ∀v V (2)
where, the constraint enforces that all controller instances of v, (M t v ) match the required controller type T v . 3. Controller capacity constraints: Deployed controllers must have enough capacity to support domain switches:

s Sv λ(s) ≤ T µ v * |M v |; ∀v V (3)
4. Controller host capacity limit: Hosting location (v.h) must have both compute and memory capacity:

g V |M g | * T χ g ≤ χ t v ; H g == v; ∀v V (4) g V |M g | * T ω g ≤ ω t v ; H g == v; ∀v V (5)

Cost Models

Leasing cost for virtual controller instances We consider that network operators lease capacity from DC operators. Virtual instance leasing cost C C can be stated as:

C C = v V (|M v | * γ * d) (6)
where γ is per-unit compute per unit-time cost of leasing virtual instances and d is duration of operation.

Network capacity cost Cost of network usage is often ignored in prior studies focusing on DC SDN scenarios. But the distributed nature of virtualized controller deployment for transport networks can add significant communication cost. First, switch-to-controller communication cost, C S N , is:

C S N = ( v V (B(S v , M v ))) * π (7)
where B(x,y) gives bandwidth consumption between x and y, and π gives the per-GBps per unit-time bandwidth price.

Similarly, controller-to-controller (same domain) communication cost, C M N , is:

C M N = v V (B(M v (i), M v (j)); i = j)) * π (8)
where B(M v (i), M v (j)); i = j gives bandwidth consumption between controllers instances of the same domain.

Similarly, controller-to-controller (different domains) communication cost, C P N , is:

C P N = p,q V (B(M p , M p ; p = q)) * π (9)
In addition, controllers may require to be migrated from one hosting location to other. This live VM migration process adds to the network cost (C V N ) as follows:

C V N = v V (B V M (v)) * π (10)
where B V M (.) is the bandwidth consumption due to migrations. Hence, total network cost, C N , is:

C N = C S N + C M N + C P N + C V N (11)
Delay Cost We also consider the impact of controller delays on user experience (higher delay means unhappy user, leading to revenue penalty). This cost adds delay factor in decision making and encourages the algorithm to minimize delays. Similar to network cost, cost of switch-to-controller delay (C S U ), controller-tocontroller (same domain) communication delay (C M U ), and controller-to-controller (different domains) delay (C K U ) can be calculated by replacing B(x,y) with D(x,y) and π with σ in Eqns. ( 7), [START_REF] Yao | On the Capacitated Controller Placement Problem in Software Defined Networks[END_REF], and (9), respectively. Here, D(x,y) gives delay due to communication between sets x and y, and σ is cost ($) associated to per unit-time delay. Also, our model considers cost due to processing delay at controllers, C P U . Hence, total delay cost becomes:

C U = C S U + C M U + C K U + C P U (12)
Now, total cost is modeled as:

C T = C C + C N + C U (13)
The objective of the proposed method is to minimize the cost of controller deployment:

M inimize(C T ) (14)

Algorithm

We propose a polynomial-time heuristic, called Virtualized Controller Deployment Algorithm (VCDA), as a scalable solution for a heterogeneous optical transport network (see Algorithm 1). Since turning controllers on/off too often may make the network unstable, we introduce a decision epoch (e), a dynamic variable allowing network operators to tune the decision frequency. We also use two management entities: Network Management and Orchestration (NMO) and Distributed Cloud Management (DCM). NMO takes care of load balancing and assignment of switches and traffic with the controllers.

Algorithm 1 Virtualized Controller Deployment Algorithm (VCDA) if

1: Input: G(V, E), λ(v),
(χ t h -χ u h ) > δ * T χ v & (ω t h -ω u h ) > δ * T ω v then 13:
Turn on additional δ controllers (Tv type) at location h; 14:

Load balance and re-route among the Mvs using Eqns. ( Our algorithm ensures that, for each domain, enough controllers are deployed to serve current load, observing the constraints. At a given load, if the controller capacity constraint holds, it means that we do not need additional controller instances (line 5). But, if the controller capacity constraint fails (line 9), the algorithm checks if the current hosting location (h) has enough compute and memory capacity to host the additional δ controllers (line 13). If yes, we turn on additional controllers and load balance the switches and traffic flows (line [START_REF] Rahman | Auto-Scaling VNFs Using Machine Learning to Improve QoS and Reduce Cost[END_REF][START_REF] Savas | Disaster-resilient control plane design and mapping in softwaredefined networks[END_REF][START_REF] Lourenco | Robust hierarchical control plane for Transport Software-Defined Networks[END_REF][START_REF] Morabito | Power Consumption of Virtualization Technologies: an Empirical Investigation[END_REF]. If host location h does not have enough resources, the algorithm finds the next optimal location to host all the instances (line 20) following constraints as in Eqns. (1-5) and minimizing Eqn. [START_REF] Rahman | Auto-Scaling VNFs Using Machine Learning to Improve QoS and Reduce Cost[END_REF]. In this step, we utilize the benefits of consolidation in computing. Placing controllers from the same domain closer to each other will reduce delay cost (Eqn. ( 12)). We consider live VM migraion (line 24) to relocate the already-running controller instances to the new location with least interruption of services.

The algorithm turns off the extra controllers (line 32-37) to save operational cost. After each iteration, the algorithm waits for the epoch e to expire. The run-time complexity of VCDA depends on number of domains (|V |), maximum number of controllers (max(|M v |)), maximum number of switches in a domain (max(|S v |)), and number of host locations (|H v |). The run-time complexity of VCDA can be expressed as

O(|V | * max(|M v |) * max(|S v |)+|V | * |H v | * max(|M v |) * max(|S v |).

Illustrative Numerical Examples

We present illustrative results on a US-wide topology (see Fig. 2), with heterogeneous domains and Edge-DCs/DCs. Each network domain requires domainspecific controller(s), that are connected to other domains via backbone optical links. We consider two DC locations (2 and 13) and three Edge-DCs [START_REF] Rahman | Dynamic Workload Migration over Optical Backbone Network to Minimize Data Center Electricity Cost[END_REF][START_REF] Yao | On the Capacitated Controller Placement Problem in Software Defined Networks[END_REF][START_REF] Kim | T-DCORAL: A Threshold-based Dynamic Controller Resource Allocation for Elastic Control Plane in Software-Defined Data Center Networks[END_REF] to host controller instances. Capacities of DCs, racks, and servers vary significantly in practice. For Edge-DCs (6, 8, 10), we assume total compute capacity (χ t v ) is 30 units and total memory capacity (ω t v ) is 60 GB. For DCs, we consider 15000 compute and 30000 memory capacity (to represent virtually infinite capacity).

We observe that the size of the topology, number of domains, etc. have impact on the results from our study. Thus, we assume different domain scenarios using this topology: (a) for the results reported in Figs. 3 and4, we assume that each of the nodes in topology is a domain. Hence, we have six individual fixed-grid domains [START_REF] Ahmed | Dynamic Routing and Spectrum Assignment in Co-Existing Fixed/Flex Grid Optical Networks[END_REF][START_REF] Munoz | Integrated SDN/NFV management and orchestration architecture for dynamic deployment of virtual SDN control instances for virtual tenant networks[END_REF][START_REF] Heller | The Controller Placement Problem[END_REF][START_REF] Sallahi | Optimal Model for the Controller Placement Problem in Software Defined Networks[END_REF][START_REF] Aguado | ABNO: A feasible SDN approach for multivendor IP and optical networks[END_REF], two packet-network domains (8 and 11), and six flex-grid domains [START_REF] Wang | The controller placement problem in software defined networking: a survey[END_REF][START_REF] Alvizu | Comprehensive survey on T-SDN: Software-defined networking for transport networks[END_REF][START_REF] Lopez | Control plane architectures for elastic optical networks[END_REF][START_REF] Kim | T-DCORAL: A Threshold-based Dynamic Controller Resource Allocation for Elastic Control Plane in Software-Defined Data Center Networks[END_REF][START_REF] Rahman | Dynamic Controller Deployment for Mixed-Grid Optical Networks[END_REF][START_REF] Rahman | Auto-Scaling VNFs Using Machine Learning to Improve QoS and Reduce Cost[END_REF]. and (b) Fig. 5 results consider larger six domains. Nodes 1, 2, and 3 create a flex-grid domain: 1-2-3. Similarly, the other domains are: 4-5-6-7 (fixed-grid), 8-11 (packet), 10-13-14 (flex-grid), 9 (fixed-grid), and 12 (fixed-grid).

Per census data, we have 47.6% of US population in Eastern time zone, 29.1% in Central, 6.7% in Mountain, and 16.6% in Pacific time zone. Our study uses this data to generate spatial variation of incoming load λ(v). For example, full load (λ = 1) for the Eastern domains is 30,615 requests per seconds vs. 10,910 Fig. 3 shows that our algorithm has lowest normalized cost among all three approaches. As expected, placing controllers only at DCs results in very high delays (see Fig. 4), causing higher delay cost. At lower load (λ = 0.2), Edge-Greedy placement saves cost compared to DC-Only (10% extra cost for Edge-Greedy vs. 41% extra cost for DC-Only), by placing the domain controllers closer to Edge. VCDA benefits more from Edge resources using consolidated placement and reducing inter-controller communication delays, resulting in cost saving. But, at higher load (λ = 0.8), VCDA saves less due to tighter capacity limits at Edge-DCs, as consolidated controllers need to move to DC locations, resulting in higher network and delay costs. Still, VCDA's cost savings is higher than the other two methods.

A major limitation of virtualized controller placement in transport networks is the additional delays. Edge-DCs helps to reduce those delays. But, as shown in Fig. 4, if the placement method is not aware of the delays (DC-Only) or takes a greedy placement approach (Edge-Greedy), the controllers will experience significant additional delays (resulting in higher delay cost). At lower load (λ = 0.2), DC-Only placement method places the controllers far from the domains, resulting in very high delays (60% extra delays). Even Edge-Greedy placement method (13.5% extra delays) reduces significant delays compared to DC-Only. But, as load increases (λ = 0.6), VCDA experiences higher delays as more controllers are now being placed at DCs (due to Edge-DC hosting capacity limit). Edge-Greedy also experience more delays at higher loads as, in addition to delays due to DC locations usage, more scattered controller instances lead to higher communication delays. Fig. 5 shows normalized cost for topology scenario (b) (only six domains, instead of 14). At lower load (λ = 0.2), cost savings is 30% compared to 'DC-Only'. VCDA looses some cost savings (compared to 41% for the same load in Fig. 3). This observation can be explained as follows. When node 10 was a separate domain, it's controllers were placed in the Edge-DC at 10. But, with the bigger domain 10-13-14, controllers for this domain are hosted in DC at 13, adding to the switch-to-controller network and delay cost. As load grows cost savings reduces and gets close to 'DC-Only' ( 0.358% cost savings at load λ = 0.8). This observation can be explained with the following example: for domain 4-5-6-7, initially at lower load, controllers were placed at Edge-DC at 6, but as load grew, requiring more resources for controllers, the controller instances were migrated to DC (reducing the cost gap). More Edge-DC and DC locations can significantly change the cost and delay. More Edge-DC locations will allow to save more cost and reduce delay even in higher loads (λ = 0.8). In our study, we consider two DC locations, in two corners of the topology, from these intuitions: (1) DC operators in USA tend to place DCs in more populated east coast and west coast regions; and (2) Placing DCs apart allows us to demonstrate the impact of Edge-DCs. But if we add more DCs or change the DC locations, that will impact the cost and delays as well.

Conclusion

Virtualized controller placement in multi-domain heterogeneous optical transport networks introduces new challenges for network management. Our proposed method for controller placement considers transport-network-specific properties and constraints such as heterogeneous optical controller types, resource limitations at edge-hosting locations, cost from additional delays, etc. Illustrative examples show that our proposed method saves cost and reduces delays significantly, compared to prior studies. Future studies should explore variation of compute/memory requirements, variation of Edge-DC capacities, variation of Edge-DC and DC locations, temporal variation of load, and more detailed cost models.

Fig. 1 :

 1 Fig. 1: Control-plane architecture for heterogeneous transport networks.

4. 2

 2 Input Parameters and Variables -G(V, E): Optical transport network topology where V is set of domains and E is set of links. -M v : set of controllers serving domain v. -S v : set of switches in domain v. -T v : domain-specific controller type. -H v : controller hosting location where H v ⊆ V . χ t v : total compute capacity at v. χ u v : used compute capacity at v. ω t v : total memory capacity at v. ω u v : used compute capacity at v. -T µ v : service capacity limit (i.e., maximum number of requests served per second) for controller type T v . -T χ v : compute resource requirement for controller-type T v . -T ω v : memory resource requirement for controller-type T v . λ(v): arrival rate of new traffic flows for a given domain (v), where r v represents new arrival of flow routing request. S r is the switch at which the request has arrived, and M v gives the set of domain controllers the switch (S r ) is connected to. α: latency constraint (maximum allowed delay).

Fig. 2 :

 2 Fig. 2: Example optical network topology with controller host locations and heterogeneous domains (red denotes flex-grid, black denotes fixed-grid, and green denotes packet).

Fig. 3

 3 Fig.3compares the normalized cost (Eqn. (14)) among three different methods: (1) DC-Only method mimics controller placement methods which focus on dynamic placement of controllers inside DCs only; (2) Edge-Greedy method considering both DCs and Edge-DCs, but instead of consolidated VM placement considering delays, this method places VMs in a greedy way ignoring network cost (Eqn. 7-11) and delay cost (Eqn. 12) (similar to[START_REF] Sallahi | Optimal Model for the Controller Placement Problem in Software Defined Networks[END_REF], evolved to host controllers at Edge); and (3) our proposed VCDA method considering consolidated VM placement, delay and capacity constraints (Eqns. (1-5)), and cost minimization (Eqns.[START_REF] Rahman | Dynamic Workload Migration over Optical Backbone Network to Minimize Data Center Electricity Cost[END_REF][START_REF] Heller | The Controller Placement Problem[END_REF][START_REF] Yao | On the Capacitated Controller Placement Problem in Software Defined Networks[END_REF][START_REF] Sallahi | Optimal Model for the Controller Placement Problem in Software Defined Networks[END_REF][START_REF] Kim | T-DCORAL: A Threshold-based Dynamic Controller Resource Allocation for Elastic Control Plane in Software-Defined Data Center Networks[END_REF][START_REF] Potluri | An efficient DHT-based elastic SDN controller[END_REF][START_REF] Aguado | ABNO: A feasible SDN approach for multivendor IP and optical networks[END_REF][START_REF] Rahman | Dynamic Controller Deployment for Mixed-Grid Optical Networks[END_REF][START_REF] Rahman | Auto-Scaling VNFs Using Machine Learning to Improve QoS and Reduce Cost[END_REF]).

Fig. 3 :

 3 Fig. 3: Normalized cost versus load for topology scenario (a).

Fig. 4 :

 4 Fig. 4: Normalized delay versus load for topology scenario (a).

Fig. 5 :

 5 Fig. 5: Normalized cost versus load for topology scenario (b).

Acknowledgement

This work was supported by NSF Grant No. 1818972.


Hongxiang Guo
email: hxguo@bupt.edu.cn

Cen Wang

Yinan Tang

Yong Zhu

Jian Wu

Yong Zuo

Machine Learning Assisted Optical Network Resource Scheduling in Data Center Networks

Keywords: Machine learning, Optical switching, Data center network, Parallel computing

Parallel computing allows us to process incredible amounts of data in a timely manner by distributing the workload across multiple nodes and executing computation simultaneously. However, the performance of this parallelism usually suffers from network bottleneck. In optical switching enabled data center networks (DCNs), to satisfy the complex and time-varying bandwidth demands from the parallel computing, it is critical to fully exploit the flexibility of optical networks and meanwhile reasonably schedule the optical resources. Considering that the traffic flows generated by different applications in DCNs usually exhibit different statistical or correlative features, it is promising to schedule the optical resources with the assistance of machine learning. In this paper, we introduce a framework called intelligent optical resources scheduling system, and discuss how this framework can assist resource scheduling based on machine learning approaches. We also present our recent simulation results to verify the performance of the framework.

Introduction

In the age of big data, various large-scale parallel computing frameworks (e.g. Hadoop and Spark) have been widely applied in commercial data centers. Due to the diverse network patterns and the huge traffic volume caused by the parallel computing jobs, the traditional electrical data center networks (DCNs) are currently hard to satisfy their networking demands. In contrast, optical switching enabled DCNs possess advantages of high bandwidth, low latency and multidimensional (e.g., space/time/wavelength) switching capability and thus have been regarded as a potential solution for the next generation DCNs.

However, it is still a challenge to effectively schedule the optical network resources to meet the requirement of parallel computing. On one hand, because multiple parallel computing jobs may usually coexist in DCNs, it is hard to individually allocate optimal optical resources for each job. On the other hand, the background applications (e.g. virtual machine migration and data backups) will inevitably appear in DCNs and generate large background flows to compete the network resources with the running parallel computing jobs, leading to a significant slowdown of computing process. As a result, it is difficult to directly adapt the optical resources to the network traffic demands of parallel computing jobs.

Recent advances in machine learning (ML) have achieved remarkable performance in dealing with a variety of pattern recognition and classification problems. In DCNs, the statistical property of the traffic generated by different applications (i.e. background applications and parallel computing applications) shows significant difference. For instance, the parallel computing jobs usually generate socalled Coflows [START_REF] Chowdhury | Coflow: A networking abstraction for cluster applications[END_REF], which consist of many parallel flows with a common performance goal (e.g., a common completion deadline). Thus, the ML approach seems highly suitable to act as a traffic pattern recognizer and assist the optical resource scheduling process. Indeed, once the runtime network traffic patterns are accurately recognized before the optical resource scheduling, the multi-dimensional switching capability of optical switching enabled DCNs is expected to be exploited more effectively, and accordingly the upper-layer parallel computing can also be accelerated.

In this paper, we make a discussion on ML assisted optical network resource scheduling in DCNs. We introduce a framework named Intelligent Optical Resources Scheduling System (IORSS), which relies on ML techniques to classify the mixed traffic flows, recognize the traffic patterns of concurrently running parallel computing jobs, and then assist the optical switching enabled DCNs to appropriately scheduling its multi-dimensional network resources. We simply review our recent research works and shed light on the feasibility of our IORSS. We also verify the outstanding performance of IORSS through simulations.

Intelligent Optical Resource Scheduling System

The overview and the workflow of IORSS are shown in Fig. 1. The aim of IORSS is to recognize the traffic pattern by examining the collected traffic statistics, and then guide the DCN to reasonably allocate the optical resources for parallel computing jobs. To this end, a flow classification module is necessary to firstly distinguish and extract the network traffic generated by parallel computing applications. In other words, the original mixed traffic matrix R is divided into two parts, a background traffic matrix B and a mixed Coflow matrix C. Obviously, R = B + C, and the matrix B is relatively sparse as it is not likely that the large volume of background traffic arises throughout the whole DCN. As for the matrix C, it may contain several concurrent Coflows that are needed to be further decomposed, namely C = m k=1 A (k) , in which m denotes the total number of Coflows and A (k) represents the traffic matrix of k th Coflow. Therefore, a traffic pattern recognition module is utilized to analyze and recognize the traffic pattern of each individual parallel computing application. Finally, according to the recognized traffic pattern, an optical resources allocation model is required to adapt the optical resources to the running parallel computing applications as well as background flows.

Flow Classification Module

In DCNs, because the network traffic demands of different applications are usually mixed together, the flow classification module needs to identify the type of each flow according to the collected traffic statistics, and then classify it into different groups (i.e., whether or not the flow is generated by parallel computing jobs). The commonly used statistics may include the flow level information such as five-tuple, and the packet level statistics such as time stamp, average packet size and packet size variation.

Currently, machine learning algorithms have shown outstanding performance in solving the classification problem. Similarly, given the sufficient amount of related network statistics, we may anticipate a well-trained machine learning model (e.g., deep learning model) can provide an accurate mapping from the input statistics to the flow type. One example is our previously proposed decision tree model [START_REF] Wang | Decision Tree Classification based Mix-flows scheduling in Optical Switched DCNs[END_REF], which is capable of identifying the type of flow according to the packet size variation.

Traffic Pattern Recognition Module

Different from the point-to-point flows produced by background applications, the "all-to-all" network traffic in parallel computing is actually much more com-plicated. As for the resource scheduling in the case of multiple computing jobs, several heuristic approaches such as Narrowest-Coflow-First [START_REF] Chowdhury | Efficient coflow scheduling with Varys[END_REF] and Smallest-Coflow-First [START_REF] Chowdhury | Efficient coflow scheduling with Varys[END_REF] have proven their superiority, but the priori knowledge of the traffic pattern (e.g. which flows belong to the same computing job) is necessarily required. However, because the networking demands generated by concurrent computing jobs are also mixed up, the individual traffic pattern of the mixed flows are hard to be recognized and separated, leading to the difficulty in directly allocating optical resources for the mixed traffic of parallel computing jobs. Fortunately, the traffic flows of each job are usually clustered and show a potential correlation, which provides an opportunity to discover the traffic pattern by using ML techniques.

To obtain the traffic pattern, after extracting the statistics of the flows generated by parallel computing jobs, an intuitive way is to directly feed these flow statistics into a fullyconnected deep learning model and find a mapping which outputs the traffic pattern. Nevertheless, because the basic neural network cannot effectively deal with the input with 2D pattern (i.e., matrix), it is not suitable to recognize the traffic pattern of a specific computing job from mixed flows. Besides, the huge amount of flow statistics in DCN will definitely cause many difficulties in training a large scale fully-connected learning model. In our recent research [START_REF] Wang | Efficient Topology Reconstruction via Machine Learning based Traffic Patterns Recognition in Optically Interconnected Computing System[END_REF], we provided an alternative solution, which applies a convolutional neural network (CNN) to learn the number of parallel computing jobs running concurrently in DCNs, and then uses a spectral clustering method to obtain the set of worker nodes within each parallel computing job. By this way, the traffic pattern can be clearly figured out to guide the optical resource allocation process.

Optical Resource Allocation Module

Considering the traffic characteristics in data centers, it is beneficial to construct an optical switching enabled DCN by combining the coarse-grained optical circuit switching (OCS) and the fine-grained time-slotted optical switching. For the OCS resource allocation, the main principle is to offload the heavy stable network traffic in DCNs. According to the background flows classified by the flow classification module, the OCS reconfiguration strategies, such as b-matching [START_REF] Yang | Topology reconstruction strategy with the optical switching based small world data center network[END_REF], traffic adaptive topology reconstruction (TATR) [START_REF] Zhang | Enabling traffic optimized topology reconstruction with the optical switching based small world data center network[END_REF] and OCBridge [START_REF] Tang | Effectively Reconfigure the Optical Circuit Switching Layer Topology in Data Center Network by OCBridge[END_REF], can be simply employed. For the fine-grained optical resources, after obtaining the traffic pattern learnt by the traffic pattern recognition module, a simple but effective heuristic algorithm such as Smallest-Coflow-First [START_REF] Chowdhury | Efficient coflow scheduling with Varys[END_REF] can be applied as the principle of allocating the time-slotted optical network resources.

Performance Evaluation

In order to verify the feasibility and evaluate the performance of IORSS, we conducted a simulation on the OpenScale [START_REF] Zhang | Optical switching based small-world data center network[END_REF], which is a small-world topology based optical DCN architecture. Moreover, to validate the applicability of IORSS to different optical switching enabled DCN architectures, we further extended our IORSS into a Fat tree DCN architecture with OCS capability.

DCN Architectures and IORSS Implementation

The architecture as well as the node design of OpenScale is depicted in Fig. 2(a). In OpenScale, several hexagon rings are organized into a regular lattice structure. The nodes in each ring operate in a time-slotted switching manner to provide logical full-mesh connections among the adjacent nodes. Each node also has wavelength switching capability, so it can build a number of OCS paths to connect remote nodes directly. In summary, OpenScale is a typical optical DCN architecture which relies on both coarse-grained and fine-grained optical resources allocation. In our simulation, the OpenScale architecture consisted of 216 nodes. Each node was capable of building one OCS connection, and the bandwidth of each OCS path was set as 10 Gbps. We simplified the time-slotted switching in each ring as a time-slot based static allocation process. More specifically, each node was statically allocated 1 Gbps to communicate with other nodes within the same ring.

The Fat tree architecture is depicted in Fig. 2(b), where all nodes are connected with a high-radix electrical switch as well as a reconfigurable optical switching matrix. In the simulation, there were also 216 nodes included in the Fat tree architecture. The bandwidth of optical link and electrical link were set to 10 Gbps and 1 Gbps, respectively. Similar with the OpenScale, each node also had the capability to build one OCS connection to communicate with another node.

Regarding the implementation of IORSS, a decision tree based method [START_REF] Wang | Decision Tree Classification based Mix-flows scheduling in Optical Switched DCNs[END_REF] was deployed as the flow classification module, in order to extract Coflows [START_REF] Chowdhury | Coflow: A networking abstraction for cluster applications[END_REF] (i.e. all the correlated flows generated by parallel computing jobs) from the mixed traffic. For the traffic pattern recognition module, we used the method proposed in [START_REF] Wang | Efficient Topology Reconstruction via Machine Learning based Traffic Patterns Recognition in Optically Interconnected Computing System[END_REF]. Finally, we employed TATR [START_REF] Zhang | Enabling traffic optimized topology reconstruction with the optical switching based small world data center network[END_REF] as the coarse-grained OCS resources scheduling algorithm. We deployed Smallest-Coflow-First (SCF) algorithm [START_REF] Chowdhury | Efficient coflow scheduling with Varys[END_REF] to guide the fined-grained time-slotted resources, which means the bandwidth of time-slotted optical resources were firstly assigned to the smaller Coflows.

Simulation Setup and Results Analysis

In our simulation, the raw traffic requests were generated by mixing background flows and the traffic flows of multiple (from 1 to 6) Coflows. The size of background flows followed a uniform distribution from 10 5 Mbytes to 10 7 Mbytes, while the total size of each Coflow followed a uniform distribution from 1 Mbytes to 10 5 Mbytes. We randomly generated 200 groups of raw traffic requests and recorded the average Coflow completion time (CCT) under the ML assisted resource scheduling of IORSS. We compared the CCT result with the baseline scheduling method which randomly built OCS connections among the nodes and applied the round-robin algorithm to schedule the time-slotted optical resources.

As shown in Fig. 3(a), it can be found that when multiple Coflows coexisted in DCNs, our IORSS could provide an effective resource allocation in both OpenScale and Fat tree architectures. With the increasing number of concurrent Coflows, the performance promotion became more significant. According to the results shown in Fig. 3(b), we can find that with the help of SCF, the smaller Coflows had a better CCT promotion. As a result, the average CCT could be effectively reduced, and accordingly the parallel computing jobs were expected to be accelerated. Parallel computing has become one of the most popular applications in modern DCs. To fully take the advantage of optical switching enabled DCN architectures, a machine learning assisted intelligent optical resources scheduling system (IORSS) is introduced and discussed in this paper, and its applicability to different DCN architectures has also been successfully verified by simulations. We believe our IORSS can drive the optical switching enabled DCN architectures to more effectively scheduling their optical network resources, and improve the performance of the upper layer parallel computing applications.

Fig. 1 .

 1 Fig. 1. Intelligent optical resource scheduling system (IORSS) for optical switching enabled data center network. The figure also presents several example algorithms about how to realize each module in IORSS.

Fig. 2 .

 2 Fig. 2. (a) OpenScale architecture and (b) Fat tree architecture with OCS capability.

Fig. 3 .

 3 Fig. 3. Simulation results. The promotion ratio is defined by dividing the absolute CCT value under the IORSS by the CCT of baseline scheduling method.

Supported by the National Natural Science Foundation of China (NSFC) under Grant No. 61331008 and No. 61471054.


Rujia Zou
email: rjzou@gwu.edu

Suresh Subramaniam
email: suresh@gwu.edu

Novel P-Cycle Selection Algorithms for Elastic Optical Networks

Keywords: Elastic Optical Network, Survivability, P-cycle

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.

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 [START_REF] Jinno | Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies[END_REF]. 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 [START_REF] Cai | Multicast routing and distanceadaptive spectrum allocation in elastic optical networks with shared protection[END_REF].

Survivability is regarded as an important aspect for optical networks, and many methods have been developed for protection [START_REF] Eshoul | Survivability approaches using p-cycles in wdm mesh networks under static traffic[END_REF][START_REF] Oliveira | Algorithm for fipp p-cycle path protection in flexgrid networks[END_REF][START_REF] Shen | Survivable elastic optical networks: survey and perspective[END_REF][START_REF] Wang | Distance adaptive dynamic routing and spectrum allocation in elastic optical networks with shared backup path protection[END_REF]. 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 protection, 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 [START_REF] Ju | Leveraging spectrum sharing and defragmentation to p-cycle design in elastic optical networks[END_REF], 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 [START_REF] Ji | Dynamic p-cycle protection in spectrum-sliced elastic optical networks[END_REF]. A service availability-oriented p-cycle algorithm for dynamic EONs is studied in [START_REF] Chen | Service availability oriented p-cycle protection design in elastic optical networks[END_REF]. A failure-independent path protection p-cycle approach in EONs is designed with modulation format consideration in [START_REF] Chen | On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks[END_REF]. 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.

Motivation and Problem Statement

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 selection. In [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF], 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 working paths have no common link. In [START_REF] Wei | Otimal design for p-cycle-rotected elastic otical networks[END_REF][START_REF] Wei | Applying p-cycle technique to elastic optical networks[END_REF], 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 topranked 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 [START_REF] Wu | Survivable routing and spectrum allocation algorithm based on p-cycle protection in elastic optical networks[END_REF]. An individual p-cycle is evaluated with traffic load balance, but physical distance and modulation format are not considered.

In [START_REF] Ju | Distance-adaptive, low capex cost p-cycle design without candidate cycle enumeration in mixed-line-rate optical networks[END_REF], 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.

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.

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.

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 T IP S ) is proposed. It is given by:

IC T IP S = M × L S × A ( 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 [START_REF] Ji | Dynamic p-cycle protection in spectrum-sliced elastic optical networks[END_REF]. 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 T IP S = p∈P M p × A p × N p ( 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.

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 T OP S = M × D max × L 2 (3)
where M is the modulation index (same as in T IP S), 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 T OP S = p∈P M p × D p,max × L p × N p ( 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 T OP S is considered to be better.

Static P-Cycle Set Generation and RSA

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.

Algorithm 1 Finding a set of p-cycles

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 IC

6:

Initialize IC min as p IC 7:

while Expand p-cycle(p) = N U LL do 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 min , update the candidate p-cycle to p and update IC min to p IC . 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. goto line 1 7: end if 8: Merge R and p as the new cycle p

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 Dijsktra'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.

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 Fig. 1: 11-node COST239 network. Fig. 2: 28-node pan-European network. 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 [START_REF] Wang | Distance adaptive dynamic routing and spectrum allocation in elastic optical networks with shared backup path protection[END_REF]. 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 [START_REF] Wang | Distance adaptive dynamic routing and spectrum allocation in elastic optical networks with shared backup path protection[END_REF]. 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 T IP S for TIPS and SC T OP S 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 1 Number of required FSs for various data rates and modulations [START_REF] Wang | Distance adaptive dynamic routing and spectrum allocation in elastic optical networks with shared backup path protection[END_REF]. , where χ 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; δ 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 [START_REF] Wei | Otimal design for p-cycle-rotected elastic otical networks[END_REF][START_REF] Wei | Applying p-cycle technique to elastic optical networks[END_REF]. 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.

Modulation

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 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 performance 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 Fig. 3: Spectrum Usage in COST239. Fig. 4: Spectrum Usage in COST239. performance, which shows the need for an improved p-cycle evaluation method which takes modulation and cycle size into account in EONs. Moveover, the results 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 physical 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 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.

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.

Algorithm 2 1 : 2 : 3 :

 2123 Expand p-cycle Require: p-cycle p Ensure: Larger p-cycle p Randomly select an on-cycle link l on cycle p Mark two ends of l as a, b 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:

Fig. 5 :

 5 Fig. 5: Demand blocking ratio in COST239.

Fig. 6 :

 6 Fig. 6: Demand blocking ratio in pan-European.

  the following three baseline algorithms for p-cycle set selection: namely, random cycle set (Random), top individual p-cycle set (TopIC), Hamiltonian cycle [11], 1 and top A Priori Efficiency p-cycle set (TopAE). A Priori Efficiency (AE, AE = i∈E χ ij /

		Date Rate 40 100 400
	8QAM	2 3 11
	QPSK	3 5 17
	BPSK	4 9 33
		Table 2
	Physical distance limitation for different modulations [13].
	Modulation Transparent Reach
	8QAM	1000km
	QPSK	2000km
	BPSK	> 2000km
	selection algorithm with

k∈E δ kj × C k

Both the topologies in this paper have a Hamiltonian cycle.

Acknowledgment

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