Keywords: Network survivability, Elastic Optical Inter-DataCenter Networks (EO-DCNs), Directed p-cycle protection, Dedicated path protection, Integer linear program (ILP), Column generation (CG), Heuristic algorithm P-cycle

With the widespread popularity of applications such as cloud computing, ultra-highdefinition video-on-demand, streaming, etc., the exponential growth of the generated information presents a challenge for the current optical networks, especially for Inter-DataCenter (DC) networks, which carry massive amounts of DC-to-client information. The traditional wavelength division multiplexing (WDM) optical network is not adapted to future networks due to its "one-size-fits-all" data transmission mode. Meanwhile, elastic optical networks (EONs) have shown the flexibility and scalability to solve the problem of huge traffic provisioning. It is widely regarded as the next-generation optical network architecture and inter-DC network, which is so-called Elastic Optical Inter-DataCenter Network (EO-DCN). However, the multitudes of Internet services are facing critical threats from network failures, e.g. fiber cut, and natural disruption. These network failures will cause incalculable financial losses. Thus, network resilience is one of the most significant factors for a majority of DC-based services. In this dissertation, we develop two classic protection schemes in EO-DCNs, i.e. directed pre-configured cycles (p-cycle) protection and dedicated path protection, against single link failure and disaster failure, respectively, to further enhance the survivability of EO-DCNs.

We first propose to investigate how to schedule the directed p-cycle protection for lower power consumption based on a compact modulation format selection in EO-DCNs. Instead of a brief upper bound on the modulation format assignment in the conventional directed p-cycle design, the proposed modulation format adaptation is designed as just enough for the directed p-cycle, which is determined by the distance of each on-cycle protection path. The problem involves the directed p-cycle generation, modulation format adaptation, power consumption minimization, and spectrum allocation. To this end, three different integer linear programs (ILPs) are formulated to provide joint optimization of power consumption and spectrum usage for all the directed p-cycles generated in EO-DCNs. The directed p-cycles are constructed via flow conservation in a way without candidate cycle enumeration, to reduce computational complexity. Then, the modulation format adaptation is achieved by relying on different flows in ILPs. To solve the problem with large-scale instances, the column generation (CG) approach is proposed to construct a promising solution. To guarantee the performance with respect to the optimal solution, the ϵ-accuracy is then introduced to evaluate the optimality of the CG approach. Extensive simulations are conducted to compare the proposed ILP and the CG approach with the conventional ones. Numerical results demonstrate that the proposed ILP models show better performance on iii power consumption. The proposed CG approach is also proven with high computation efficiency and guaranteed performance with large-scale traffics.

We then investigate disaster protection for EO-DCNs. We focus on the disasterresilient service provisioning problem leveraging cooperative storage system (CSS). Instead of mirrored content backup on a single DC, our proposed CSS partitions a required content into no less than three fragments if possible, each of which is then stored on a DC located in different disaster zones (DZs), to ensure they are DZ-disjoint. Accordingly, multi-path routing with the adaptive number of working paths to distinct DCs is employed to serve each request, while a protection path is computed to protect against a disaster failure. The studied problem involves DC assignment, content partition, and placement, working/protection paths computation, as well as spectrum allocation. Our main objective is to jointly minimize the spectrum usage and maximal occupied frequency slot index (MOFI) subject to disaster resilience. Besides, we also expect to cut the content storage space. To this end, we propose for the first time a CSS-based dedicated end-to-content path protection (CDP), which allows service provisioning through multiple paths with the adaptive number of paths rather than a single path. This consequently reduces at least half of the reserved spectrum on the protection path. To find the optimal CDP strategy, we formulate the studied problem as an ILP model and then propose a fast heuristic algorithm. Observing the trade-off between the spectrum usage and content storage space, we further design a maximum-CDP (M-CDP), which generates the maximum number of working paths to reduce the content storage space. Simulations are conducted to compare the proposed schemes with the traditional protection strategy using mirrored storage and single-path routing. These findings highlight the potential advantages of the CDP strategy on disaster protection in EO-DCNs.

Finally, we focus on disaster protection for network function virtualization (NFV) embedded EO-DCNs. NFV technology enables flexible, adaptive, effective, and economic network services deployment and upgrades for service providers. However, it is also facing critical threats from large-scale network failures, due to natural disasters disruptions. This is driving the need for efficient network protection schemes of service function chain (SFC) provisioning, especially for EO-DCNs. To this end, we investigate the disaster-resilient SFC provisioning problem leveraging power-efficient path protection with distance-adaptive modulation formats, as well as considering virtual network function (VNF) placement, SFC mapping, path protection, and spectrum allocation simultaneously. This study provides the first comprehensive disaster protection for SFC provisioning. An ILP model is then formulated with the objective of the joint minimum power consumption and spectrum usage, subject to disaster resilience. A heuristic approach is also developed for the sake of scalability. Numerical Simulation results demonstrate that the proposed disaster protection scheme enables a significant reduction in power consumption.

Introduction

The explosive growth of the generated information around the world poses a significant challenge for the current data transmission. The overall amount of data generated annually is predicted to be 2,142 ZB in 2035 [START_REF] Of | Information and C. Technology[END_REF]. For current optical networks, the annual IP traffic is predicted to reach 4.8 ZB by 2022 with a compound annual growth rate of 26% since 2017 [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. It drives the evolution of the next-generation optical networks. To this end, for such huge traffic demands, the elastic optical networks (EONs) architectures have shown the ability to solve the problem of traffic provisioning with big volume [START_REF] Gong | Efficient resource allocation for all-optical multicasting over spectrum-sliced elastic optical networks[END_REF][START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF][START_REF] Wang | A survey on data center networking for cloud computing[END_REF][START_REF] Zhu | Dynamic service provisioning in elastic optical networks with hybrid single-/multi-path routing[END_REF]. Typically, the service providers deploy the network services at datacenters (DCs) due to long-term economic concerns. Thus, to provide the cloud services, 597 hyperscale DCs have been built by the end of 2020. The market size of the internet DC has reached 139.6 billion dollars by the end of 2020 [100]. Benefiting from the inherent flexible spectrum usage and low latency, the DCs can be interconnected through EONs to facilitate the huge data exchanges and migrations, which forms the so-called elastic optical inter-data center networks (EO-DCNs) [START_REF] Lu | Highly efficient data migration and backup for big data applications in elastic optical inter-data-center networks[END_REF][START_REF] Wang | A survey on data center networking for cloud computing[END_REF]. However, the multitudes of Internet services are facing critical threats from network failures, e.g. fiber cut and natural disaster disruption. The DCs are especially economically vulnerable to network failure. The downtime of each server may cause a loss of $ 9,000 per minute [START_REF] Carroll | How effective is your data center's disaster recovery plan?[END_REF]. The network failure can cause an average loss of 402,542 dollars in the USA, and 212,254 dollars in the UK [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. Naturally, network survivability is regarded as the most significant factor from these perspectives.

For current survivable optical networks, the protection strategies differ in their priorities. The single link failure is the most common network failure due to the disruption of cable cut. To this end, the pre-configured-cycle (p-cycle) protection has been proved as a spectrum-efficient, switching-fast, and energy-saving strategy against single link failure with the ring-like structure [START_REF] Asthana | p-cycles: An overview[END_REF][START_REF] Grover | Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration[END_REF][START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Ju | Distance-adaptive, low capex cost p -cycle design without candidate cycle enumeration in mixed-line-rate optical networks[END_REF]]. As it is noticed, among all the business traffics, 82% are Internet video [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. With other content delivery services, such traffic shows an asymmetric feature to today's optical networks. Meanwhile, the huge traffic demands require enormous electricity support, in which the energy consumption of the information and communication industry is predicted to rise as 8,263 kWh by 2030, occupying 20% of global electricity [START_REF] Andrae | New perspectives on internet electricity use in 2030[END_REF]. As reported in [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Rocha | Directed vs. undirected p-cycles and FIPP p-cycles[END_REF], the directed p-cycle has less energy consumption when protecting the asymmetric traffic against single link failure, compared to the undirected p-cycle. We then focus on the most common single link failure, e.g. fiber cut. We investigate the directed p-cycle protection aiming to jointly reduce the power consumption and spare capacity with the single link xi protection in EO-DCNs.

In addition to the directed p-cycle protection against single link failure, the natural disaster is an emerging failure scenario and a critical threat that may destroy the largescale network nodes and links. For instance, the 8.3-magnitude Wenchuan earthquake in May 2008 destroyed 3,897 telecommunication nodes and 28,765 km cables. Thus, we first focus on the dedicated backup path protection with consideration of the spectrum efficiency in elastic optical datacenter networks (EO-DCNs). Different from the conventional 1 : 1 working/backup path configuration, we allow the working paths to be adaptively split as disaster zone disjoint leveraging cooperative storage system (CSS), namely CSS-based dedicated end-to-content path protection (CDP). Such a method can reduce the spectrum usage on the backup path as well as the overall storage space at the DCs.

Besides the end-to-content communications, we finally investigate the network function virtualization (NFV) embedded EO-DCNs, where the services need to be provisioned by the required service function chain (SFC). SFC consists of an ordered set of virtual network functions (VNFs). Therefore, disaster protection becomes more challenging with two problems, i.e. VNF placement and SFC mapping, which are classified as N P-hard [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF]. The dedicated path protection with distance-adaptive and powerefficient considerations is then designed.

The rest of this chapter is organized into three parts:

• Motivations and Objectives

• Contributions of the Thesis • Organization of the Thesis

Motivations and Objectives

In this thesis, we focus on the survivability of EO-DCNs that is guaranteed by the various network protection schemes. The fundamental issues of terrestrial optical networks have been well explored for decades. The current works in this perspective mainly focus on the protection cost optimization with full protection for each request. Following this, we investigate how the network performance can be optimized through the various protection schemes, including dedicated path protection and p-cycle protection.

Motivation 1:

The single link failure is the most common network failure. We configure directed p-cycle to protect each request as the directed p-cycle scheme has shown better protection for the asymmetric traffics. Note that, the up-to-date directed p-cycle design is not compact for the modulation format selection. It lacks the means to determine the protection path of the straddling spans. Thus, the modulation format assignment in the conventional directed p-cycle design roughly relies on a relaxed upper bound, consequently leading to a cost waste into the solution. In addition, an efficient method is urgently needed for realistic scenarios with large-scale traffics. From these perspectives, we investigate to propose a novel directed p-cycle design in EO-DCNs xii with a novel and compact modulation format adaptation. Based on the directed p-cycle design, three integer linear program (ILP) models without candidate cycle enumeration and two scalable column generation (CG) methods with guaranteed performance are proposed.

Motivation 2: To protect each request against a single disaster failure, the up-to-date research uses 1 : 1 working/backup path configuration to provide two disaster zone (DZ) disjoint paths to maintain the network survivability [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF]. It requires at least 100% extra spectrum usage for the backup path. Meanwhile, the maximum distance separable (MDS) codes provide a feasible method of building a cooperative storage system (CSS) for EO-DCN to reduce the pressure of storage space for DCs [START_REF] Dimakis | Network coding for distributed storage systems[END_REF]. Through MDS coding, the working path can be split and constructed in a DZ-disjoint mode. Two paths are DZ-disjoint if their physical links are not affected by the same DZ (except the DZ covers the source node), such that the backup path can be activated once the working path is blocked by any DZ. Thus, the backup path can be assigned only a fraction of the one in the conventional method to protect any one of the working paths. It motivates us to formulate a new network protection scheme with the mentioned coding technique, namely CSS-based dedicated end-to-content backup path (CDP). With the benefits of adaptive path generation, it is also promising to lower the content storage space. Our objective is to jointly optimize the overall spectrum usage and the maximal occupied FS index (MOFI). Besides, the conventional work uses mirrored storage system. The CDP allows content storage space to be reduced on each DC due to the CSS.

Motivation 3:

For disaster failure, we finally focus on the dedicated path protection for SFC provisioning in EO-DCNs. In such a scenario, the traffic of each request needs to be processed by the required SFC, which is a set of ordered VNFs that are deployed at DCs. Thus, the both working path and backup path need to take the VNF placement into consideration. Note that the involved sub-problems of VNF placement and SFC mapping are both classified as N P-hard [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF], which makes the disaster protection even more challenging. To the best of our knowledge, disaster-resilient SFC provisioning has not been applied in EO-DCNs. EO-DCNs can support the flexible modulation format adaptation, and it has been proven with the potential to enable a higher spectrum efficiency and thus less spectrum usage and reduced power consumption by previous works. Furthermore, VNF placement requires specific transponder deployment. Thus, a source-to-destination flow may be processed by the middle-placed VNFs and rerouted to the next node. It leads to various path configurations with several segments of lightpaths from the end-to-end path, and an optimal design would reduce the network resources to a large extent.

Contributions of the Thesis

This thesis explores the survivability issue for EO-DCNs. The main contributions are listed and explained in detail below.

Power-Efficient Directed p-Cycle leveraging Flow Conservation and Column Generation xiii

We first study the network protection against single link failure leveraging directed p-cycle in the EO-DCNs. We propose a novel directed p-cycle design with the compact modulation format adaptation. It is then formulated by three integrated ILP models without candidate cycle enumeration, with a guarantee on the full protection for all the traffic-loaded links. The main contributions are specified as follows.

• The studied problem involves directed p-cycle generation, modulation format adaptation, power consumption minimization, and spectrum allocation. A novel and compact modulation format adaptation is designed to reduce power consumption and spectrum usage.

• Three different ILP models are proposed to formulate the novel directed p-cycle design with flow conservation. Three strategies are adopted in these ILP models, including individual link flow (ILF) directed p-cycle, aggregated link flows (ALF) directed p-cycle, and loop-eliminating flow (LEF) directed p-cycle. They differ from each other on how the flows can construct the directed p-cycles, respectively. The ILP models are also designed in a way without candidate cycle enumeration to jointly minimize power consumption and spectrum usage. They are evaluated in terms of overall objective value and computational efficiency.

• The LEF directed p-cycle ILP model shows the best performance in our observation. Thus, based on the LEF-directed p-cycle, we then propose a CG-based approach (namely ILP-CG) to extend the scenario into the medium-scale network.

The ILP-CG approach generates each promising directed p-cycle, i.e. column in the CG, based on an ILP model. The overall performance of the ILP-CG is guaranteed by a proven ϵ-optimality.

• Next, a further CG approach, namely De-CG, is proposed to extend the scenario into the large-scale networks. Different from the ILP-CG, the pricing problem of the De-CG is solved by a fast heuristic decomposition algorithm. The De-CG can provide a near-exact solution with much less computational time.

• We compare the proposed directed p-cycle design with the traditional scheme.

The simulation results elucidate a significant improvement in the overall performance. The CG approaches also show their superiority in very high efficiency with a near-exact solution for large-scale scenarios.

Disaster Protection in Inter-DataCenter Networks leveraging Cooperative Storage

We then study a novel network protection design against the single disaster failure in the EO-DCNs. We propose the cooperative dedicated end-to-content backup path protection (CDP) to guarantee the full protection for all the requests. The main contributions are presented as follows.

• The studied CDP problem involves DC assignment, content partition and placement, adaptive working/protection paths computation, modulation adaptation assignment, as well as spectrum allocation. Meanwhile, the content storage space is also reduced owing to content partition in CSS and multi-path routing.

xiv

• An integer linear program (ILP) is formulated to model the proposed CDP. The objective aims to jointly minimize the spectrum usage and maximal index of occupied frequency slots (MOFI).

• A heuristic algorithm is proposed to solve the CDP in large-scale scenarios. With the same objective as the ILP, the solution in the heuristic algorithm is generated greedily first and then optimized globally after. It uses coloring algorithms to minimize the overall spectrum usage by decomposing the spectrum conflict.

• Through CDP, we observe that the spectrum utilization performance is not positively related to the number of the working paths [START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF]. Hence, to further explore the impact of multi-path routing in the CDP, we propose to generate the maximum number of working paths for each request in the CDP scheme, which is then called maximum CDP (M-CDP). The M-CDP provides a better solution on content storage space at the cost of more spectrum resource.

• Finally, we compare two CDP schemes and a traditional scheme using single-path routing and mirrored storage in NSFNET, COST239, and the US Backbone networks. Simulation results demonstrate the significant performance improvement of the proposed methods compared with the traditional protection scheme.

Distance-adaptive and Power-efficient Disaster Protection for Service Function Chain Provisioning in EO-DCNs

At last, we investigate the disaster protection for SFC provisioning in NVF-embedded EO-DCNs. We consider dedicated path protection for each request, and the required SFC needs to be configured on each path. The DZ-disjoint VNF placement and path generation both need to be considered. We summarize the main contributions as follows.

• We propose a novel disaster protection scheme for SFC provisioning to jointly improve the spectrum and power efficiency of the networks. The requests are provisioned with anycast technique from the available DCs. The explored problem also involves VNF placement, SFC provisioning, disaster-resilient path generation, modulation format adaptation, as well as spectrum allocation.

• We formulate the joint problem as an integer linear program (ILP) model, aiming to minimize spectrum usage and power consumption.

• To tackle instances of larger sizes, we then propose a fast heuristic approach. It first enumerates the possible configuration of each request and selects the feasible ones. Then, the spectrum of each lightpath is allocated based on a color algorithm.

• Finally, we compare the proposed schemes to a traditional scheme using a single modulation format in NSFNET, and US Backbone networks. Simulation results demonstrate the significant performance improvement of the proposed methods, up to 32.05% reduction in power consumption, compared with the traditional protection scheme.

xv

Organization of the Thesis

The thesis carried out studies on survivability for next-generation optical networks.

The survivability issue for EO-DCNs is explored. From these perspectives, backgrounds of the EO-DCNs are presented in the Chapter 1, and survivability problems are addressed in the Chapter 2. Then, the rest of this thesis is organized as two parts: powerefficient directed p-cycle leveraging compact modulation format adaptation and column generation methods for the EO-DCNs in the Chapter 3, disaster protection leveraging CSS for the EO-DCNs in the Chapter 4, and power-optimal and distance-adaptive disaster protection for SFC provisioning in the Chapter 5.

Chapter 1 introduces the backgrounds of the EO-DCNs and the survivability issue for next-generation optical networks, including the key enabling technologies and hardware of EONs, and the literature review of p-cycle protection and disaster protection. We first report the Internet traffic trends in recent years and their prediction for the future. Then, we provide a comprehensive description of the EO-DCNs with the urgent needs, main considerations, and key enabling technologies of EONs. Next, survivability issues are introduced with a detailed illustration of classic network protection schemes. Finally, the challenges and the related works of network protection are presented.

Chapter 2 describes survivability problems in the existing and emerging optical networks, including the threats, classic network protection methods, and challenges of network protection.

Chapter 3 investigates how to schedule the directed p-cycle protection with a compact modulation format selection. First, we elaborate on the related studies of the directed p-cycle design and point out the deficiency. Then, to address that, we present a novel directed p-cycle protection method based on the compact modulation format adaptation. We formulate the proposed directed p-cycle design with three different ILP models without candidate cycle enumeration. The objective minimizes joint power consumption and spare spectrum usage. The results show the one constructed by loopeliminating flow has the best efficiency, namely LEF directed p-cycle ILP model. Next, two different CG approaches are proposed to solve the problem with large-scale traffics. The CG approach with LEF-ILP-model-based pricing problem aims to provide a guaranteed solution with a few hundred instances, while the CG approach with heuristicbased pricing problem provides a scalable and efficient solution for large-scale scenarios. The ϵ-accuracy is also introduced to evaluate the solution quality. Finally, Extensive simulations are conducted, to compare the proposed ILP and two CG approaches with the conventional ones under a variety of conditions. The work of this chapter can be found in the publication [C2].

Chapter 4 investigates the disaster-resilient service provisioning problem leveraging CSS. First, we describe the conventional disaster protection in EO-DCNs and discuss the existing improved techniques. Based on this, we present the design of the proposed disaster protection method, i.e. CDP. Then, we formulate the proposed CDP as an ILP model. The objective minimizes the joint overall spectrum usage and MOFI. Next, xvi an unexpected observation drives us to further explore the M-CDP scheme, which has better performance on content storage space but costs more spectrum utilization. The proposed CDP and M-CDP schemes are then decomposed as heuristic algorithms to deal with large-scale instances. Finally, simulations are conducted to compare the proposed CDP and M-CDP with conventional disaster protection under a variety of conditions. The work of this chapter has been published in [J1] and [C3].

Chapter 5 explores the power-efficient and distance-adaptive disaster protection for SFC provisioning. First, we explain the NVF technology, and how the SFC-based services, which are coupled with SFC mapping and VNF placement problems, are different from the conventional ones. Then, we propose the disaster-resilient SFC provisioning design in EO-DCNs, concerning VNF placement, SFC provisioning, disasterresilient path generation, modulation format adaptation, and spectrum allocation simultaneously. An ILP model is formulated to joint minimize power consumption and spectrum usage. To tackle large-scale instances, we next propose a fast heuristic algorithm. Finally, simulations are conducted to compare the proposed methods with the conventional one, which only uses a single modulation format. The work of this chapter can be found in [C1].

Finally, chapter 6 concludes the thesis and envisages the future work.

Background and Technological Context

The organization of this chapter is as follows.

• In Section 1.1, we report the Internet traffic trends.

• In Section 1.2, we present the background of elastic optical inter-data center networks (EO-DCNs). We also introduce the key enabling technologies, enabling hardware, and the lightpath features of elastic optical networks (EONs).

• In Section 1.3, we review the related works on the p-cycle protection and disaster protection in optical networks.

Internet Traffic Trends

The last two decades have witnessed the rapid development of a variety of Internetbased applications, such as video-on-demand, streaming, cloud services, etc. The rapid development of information and communications technology (ICT) industry has greatly improved people's living standards. According to the prediction from Cisco, the number of total Internet users will rise from 3.9 billion (half of the global population) in 2018 to 5.3 billion (two-thirds of the global population) by 2023 [START_REF]Cisco annual internet report[END_REF]. Each person will own 3.6 networked devices on average that access to the Internet, up from 2.4 for each person in 2018 [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. The Internet services, especially the high-definition video distribution services, drives high-speed broadband penetration and requirement. For instance, the average download speed of fixed broadband in Western Europe has reached 90.56 Mbps in Jan. 2022, which was 24.01 Mbps in 2017 [START_REF] Cable | Worldwide broadband speed league[END_REF]. With other increasing bandwidth requirement from various of web-based devices and applications, such as Internet of Things (IoT) and 5G mobile applications, there continuous to be accelerating speeds of Internet traffic growth over last two decades. The global Internet networks carried about 100 GB of traffic each day 30 years ago in 1992, while it has reached more than 46,000 GB per second in 2017. It is predicted to be 150,700 GB per second in 2022 [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. Shown as in Table 1.1, the global Internet traffic has been increasing dramatically for over past two decades. In general, it is predicted that the global IP traffic will reach 396 EB per month by 2022 with a compound annual growth rate of 26% since 2017, up from 122 EB per month in 2017 [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF], as shown in Fig. The exponential growth of Internet data is challenging more than current transport networks. It also requires enormous enabling devices to support long-haul transmission and big data storage. To store the explosive data, the dataceneters (DCs) in China has reached over 5 million in 2020, up from 1.24 million in 2015 [START_REF] Of | Information and C. Technology[END_REF]. Globally, 597 hyperscale DCs have been built by the end of 2020. The market size of the internet DC will reach 139.6 billion dollars by the end of 2020 [100]. The energy consumption of the information and communication industry is predicted to rise as 8,263 kWh by 2030, occupying 20% of global electricity [START_REF] Andrae | New perspectives on internet electricity use in 2030[END_REF].

To summarize, the dramatic increasing Internet traffic is saturating the capacity of the backbone networks. The current optical networks are undergoing significant changes to support the huge data transmission with more cores, more fibers, and expanding bandwidth. Meanwhile, the next-generation networks also require the sustainable, power-efficient, and environmentally aware optical network infrastructure.

Elastic Optical Inter-DataCenter Networks

Elastic Optical Inter-DataCenter Network (EO-DCN) can be formed by Elastic Optical Network (EON) interconnecting DCs. Thus, the network transmission characteristics of EO-DCNs can be obtained by understanding the characteristics of EONs. This section therefore describes the background, enabling technologies, enabling hardware, and lightpath in EONs, in order to better understand the data transmission of EO-DCNs.

From fixed-grid WDM networks towards EONs

The fiber-based optical networks are one of the most important technologies in modern human society. The optical networks enable the rapid development of the information technology (IT) industry in the 21st century, and they have dramatically changed hu-man life. The wavelength division-multiplexing (WDM) technology is the most mature optical network implementation technology. It divides the spectrum of each lightpath into separate channels with the spacing of 50 or 100 GHz, which is specified by International Telecommunication Union -Telecommunication Standardization Sector (ITU-T) standards, as shown in Fig. 1.2. The dense wavelength-division multiplexing (DWDM) transmission systems can achieve 10 Tbps data transmission per fiber using a 50 GHz frequency grid [START_REF] Jinno | Elastic optical networking: Roles and benefits in beyond 100-gb/s era[END_REF]. The transceivers can be configured with 10 Gbps, 40 Gbps, and 100 Gbps according to the assigned modulation formats. However, current WDM systems work with fixed grids with rigid large granularity, in which the wavelength assignment and modulation format assignment are achieved in a fixed manner. Each fixed grid is a This consequently causes waste of spectrum resources. As an instance is shown in Fig. 1.3, the traffic with 10 Gbps and 40 Gbps is not sufficient to fill the entire capacity of wavelength, but no other wavelength assignment is available but the rigid large 50 GHz channel. Even with assigned the lowest-order modulation format, i.e. binary phase shift keying (BPSK), it still causes a large portion of the unutilized spectrum in the fixed-grid WDM networks. Furthermore, a guard band between any two adjacent channels pair does not allow spectral overlapping. Thus, super-channel configurations cannot be achieved. The transmission with 400-Gbps bit rates, for instance, is not available at standard modulation formats, as it may overlap fixed-grid boundary. A flexible grid, however, can support scalable data transmission in a spectrum-efficient manner, as shown in Fig. 1 With the concerns of low efficient utilization on the spectrum utilization, a spectrum efficient and scalable optical transport network architecture called spectrum-sliced elastic optical path network (SLICE) was then proposed in [START_REF] Jinno | Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies[END_REF], which is currently called the EON for simplicity. The term elastic refers to two key properties [START_REF] Gerstel | Elastic optical networking: A new dawn for the optical layer[END_REF]:

or 100 GHz channel spacing

• Elastic spectrum allocation in a highly spectrum-efficient and scalable manner:

The optical spectrum can be divided up as finer granularity with 12.5 GHz, or 6,25 GHz (from ITU-T existing 50 GHz granularity). It is based on the implementation of flexible channel allocation, i.e. flexible grid.

• Variable bit rates: The transponder can support flexible data transmission with variable bit rates based on the bandwidth-variable transponders (BVTs) and flexible optical cross-connects (OXCs).

The EONs architecture is one of the most promising candidates for next-generation optical networks since it can provide highly spectrum-efficient communications to accommodate heterogeneous service provisions. Benefiting from the inherent flexible spectrum usage, variable data transmission, huge capacity, and low latency of EON, the DCs can be interconnected through EONs to facilitate the huge data exchanges and migrations, which forms the so-called EO-DCNs [START_REF] Lu | Highly efficient data migration and backup for big data applications in elastic optical inter-data-center networks[END_REF][START_REF] Wang | A survey on data center networking for cloud computing[END_REF], as shown in Fig. 1.5.

Enabling Technologies of EONs

The EONs architecture is considered as a realistic perspective, as it can be seamlessly deployed from the existing infrastructures [START_REF] Napoli | Next generation elastic optical networks: The vision of the european research project idealist[END_REF]. EONs adopt optical orthogonal frequencydivision multiplexing (O-OFDM), Nyquist WDM, and time and frequency packing (TFP) techniques [START_REF] Jinno | Spectrum-efficient and scalable elastic optical path network: architecture, benefits, and enabling technologies[END_REF][START_REF] Napoli | Next generation elastic optical networks: The vision of the european research project idealist[END_REF]. The O-OFDM can generate orthogonal subcarriers that are overlapped in the frequency domain. The orthogonal subcarriers, i.e. frequency slots (FSs), can bring high spectrum efficiency with narrower channel spacing and finer granularity, as shown in Fig. 1.6 (a). The Nyquist WDM applies the pulse-shaping filters to confine the signals within the Nyquist frequency. Thus, the inter-symbol interference between the subcarriers can be greatly reduced. The subcarriers can be densely merged to form super-channels. As illustrated in Fig. 1.6 (b), the Nyquist WDM shapes the O-OFDM subcarriers as the rectangular profile. The TFP can generate the pules that strongly overlap in time or frequency or both. By reducing the bandwidth of each subcarrier, the frequency spacing is kept below the Nyquist limit. Thus, it can greatly increase spectrum efficiency, as shown in Fig. 1.6 (c).

With the implementation of the physical layer, EONs thus can support the data transmission with the following features:

• The super-channels are formed with multiple subcarriers aggregation. Unlike the strict guard bands in WDM networks, the subcarriers in a super-channel do not • The FS in EONs has finer granularity. The connection of each end-node pair can be properly sized. The connections with 10 and 40 Gbps can be assigned with less spectrum, rather than the 50 GHz in the fixed grid, as illustrated in Fig. 1.7. The channel spacing is also reduced thanks to Nyquist WDM. The spectrum efficiency is further increased.

• The BVTs can assign the modulation format based on the distance of a lightpath. A higher-order modulation format contributes to higher spectrum efficiency, consequently less optical spectrum. Thus, a lightpath with a shorter distance can be allocated with the minimum spectrum.

Enabling hardware of EONs

The flexibility of EONs is mainly enabled by BVTs and bandwidth-variable OXCs. The BVTs generate the optical flows from client nodes at the network edge. The bandwidthvariable optical cross-connects (BV-OXCs) can route these flows to their destination nodes.

(

1) Bandwidth Variable Transponders

The bandwidth variable transponder, i.e. BVT, can provide the flexible-bandwidth data transmissions. As shown in Fig. 1.8, the traffics are aggregated and generated as an optical flow, and the flow is then routed by a reconfigurable optical add and drop multiplexer (ROADM).

An instance of distance-adaptive and flexible-bandwidth data transmission is shown

ROA D M BVT

Variable traffic

Variable bandwidth optical flow in Fig. 1.9. The modulation format assignment is restricted by the transmission reach of the modulation format due to the physical layer impairment. In this case, the transmission for source node s to node e1 can be assigned with 16 quadrature amplitude modulation (QAM), in which the spectrum efficiency is 4 bps/Hz. Whereas the transmission for source node s to node e2 can only be assigned with quadrature phase-shift keying (QPSK) due to a long transmission path length, in which the spectrum efficiency is 2 bps/Hz. Generally, a higher-order modulation format is less tolerant to the physical layer impairments. The physical layer impairments are accumulated along the lightpath due to the non-ideal optical transmission medium. Typically, 16-QAM has high spectrum efficiency but is limited by short transmission reach and high power consumption. Binary phase-shift keying (BPSK) can support the data transmissions for long-haul links with less power consumption, but it suffers from low spectrum efficiency. Table 1.2 summarizes four typical modulation formats, i.e. BPSK, QPSK, 8-QAM , and 16-QAM , with their spectrum efficiency, transmission reach, and power consumption. Note that each subcarrier is with 12.5 GHz, which is a single FS in EONs.

Based on the BVT, the concept of sliceable BVT (S-BVT) has emerged to enhance the [START_REF] Sambo | Next generation sliceable bandwidth variable transponders[END_REF]. An S-BVT is known as a multi-flow transponder that is able to generate multiple optical flows rather than a single flow in the BVT. These flows can be either aggregated to the super-channels or can be sliced into several different sub-channels. Thus, an S-BVT can work as one single BVT to serve one traffic demand with a large bandwidth requirement, or several independent requests simultaneously with sliced spectrum. Flexibility is further improved, as shown in Fig 1 .10. (

ROA D M

Traffics towards multiple destinations

2) Bandwidth Variable Optical Cross-Connects

The optical cross-connects (OXCs) can switch the optical signal into different channels but with a much simpler fiber connection, higher reliability, and higher scalability. The BV-OXC is an OXC that can add/drop the flows with the corresponding spectrum bandwidth to create the proper-sized lightpaths. A BV-OXC is typically composed of several interconnected power splitters and bandwidth-variable spectrum selective switches (BV-SSS).

As shown in Fig. 1.12, the input optical signals are copied and broadcast into the BV-SSSs. Then each BV-SSS chooses to pass or block the received signals. Thus, the optical signals are distributed into different output ports and fibers according to the traffic demands.

Lightpaths in EONs

The trend of the next-generation optical networks is from opaque networks to translucent networks, and eventually transparent networks. In the opaque networks, all the nodes are implemented with electrical components that support optical-electrical-optical (OEO) conversions, where the optical signals are converted to the electronic domain in the relaying nodes and then sent to the next hop in the optical domain. In the translucent networks, a part of the nodes can provide OEO conversions for the optical signals. While in the transparent networks, the optical signals stay at the optical domain until they are received by the destination. The transparent networks are also known as all-optical networks. Such a configuration without the OEO regenerator would benefit from lower cost, lower power consumption, and lower connection latency for the network services, but it increases the complexity of network design and management. The EONs are assumed to be configured in the mode of transparent way in this work.

A lightpath is an optical communication path without OEO conversions, including its physical path and the assigned spectrum. Thus, a path of traffic demand is a lightpath between two ending nodes in the transparent networks. It needs to satisfy some principles when configuring such a connection in the EONs.

• Spectrum contiguity constraints: The assigned spectrum for a lightpath must be contiguous FSs.

• Spectrum continuity constraints: All the links along a lightpath should be as-

BV-SSS

frequency input fiber output fiber Figure 1.12: Spectrum selection in a BV-SSS [START_REF] Chatterjee | Routing and spectrum allocation in elastic optical networks: A tutorial[END_REF].

signed with the same FSs.

• Spectrum conflict constraint: The assigned FSs for the lightpaths should not have conflict. The spectrum conflict occurs if two lightpaths use the same FS if they share at last one common link.

• Modulation format assignment constraint: For each lightpath, the path length should be no longer than the transmission reach of the assigned modulation format due to the physical layer impairments, as aforementioned in Section 1.2.3 1).

Generally, the first three constraints are known as the spectrum allocation problem. The routing, spectrum allocation, and modulation format assignment are also known as RMSA problem [START_REF] Chatterjee | Routing and spectrum allocation in elastic optical networks: A tutorial[END_REF]. Each connection of a service provisioning needs to solve the RMSA problem. It is an N P-hard problem for the optical network to implement the RMSA for all the traffic demands [START_REF] Chatterjee | Routing and spectrum allocation in elastic optical networks: A tutorial[END_REF].

Threats in optical networks

With the dramatic development of the optical networks, the multitudes of Internet services in the current optical networks are also facing critical threats from network failures.

The network failure can cause services outage for all kinds of network-based services, such as 5G services, streaming, video-on-demand, cloud storage, and cloud computing services. The network outages were detected more frequently in 2020 during the long-term disruption of COVID-19 [101]. As shown in Fig. 1.13, the number of network disruptions rose sharply in March 2020.

The natural disasters, e.g. hurricanes, wildfires, floods, and earthquakes, cause much more severe damages that can destroy the large regional electricity systems and transport networks for a relatively long time [START_REF] Neelam | A scientometric review of global research on smart disaster management[END_REF]. There continues to be an increasing rate of the population and built-up surface exposed to the hazards. Alone the earthquake, the data shows about 2.7 billion people (37% of the global population) in 2015 are living in the seismic areas [START_REF] Pesaresi | Atlas of the human planet 2017. global exposure to natural hazards[END_REF]. Fig. 1.14 shows the earthquake seismic areas with classifications following Mercalli modified intensity scale. Some natural disasters examples are shown as follows. • Hurricane Katrina decreased the network usability of the affected area from 99.99% to 85%, which caused severe losses in Louisiana and Mississippi in the Southeastern US in August 2005 [START_REF] Sterbenz | Resilience and survivability in communication networks: Strategies, principles, and survey of disciplines[END_REF].

• The 8.3-magnitude Wenchuan earthquake in May 2008 damaged 3,897 telecom offices, 142,078 telecom poles, and destroyed 28,765 km cables in Sichuan, Gansu, Shaanxi, and other provinces [START_REF] Ran | Considerations and suggestions on improvement of communication network disaster countermeasures after the wenchuan earthquake[END_REF].

• The 9-magnitude earthquake, known as Great East Japan Earthquake in March 2011. With its secondary tsunami, the disasters damaged 65,000 telecom poles, and cut off 6,300 km cables and 90 relay transmission routes [START_REF] Adachi | The restoration of telecom power damages by the great east japan earthquake[END_REF].

• A submarine volcano eruptions in the South Pacific destroyed undersea cable, i.e. Southern Cross Cable, in January 2022. It caused nationwide disconnection of Tonga from outside the world. It took 38 days to repair the undersea cable and reconnection the Internet [START_REF] Bbc | Tonga volcano: Internet restored five weeks after eruption[END_REF].

The economic loss from the network disruption is huge. An average loss of each network outage in 2018 was 402,542 dollars in the USA, and 212,254 dollars in UK [START_REF] Appdynamic | The rise of AIOps: How data, machine learning, and ai will transform performance monitoring[END_REF]. The damages on the optical networks from disaster-caused network failures are too severe to estimate. The downtime of each DC server may cause a loss of $ 9,000 per minute [START_REF] Carroll | How effective is your data center's disaster recovery plan?[END_REF]. Such disaster-caused network paralysis has cost billions of dollars in losses. Naturally, network survivability is regarded as the most significant factor for a majority (59.8%) of the business continuance professionals [START_REF] Cisco | 2021 global networking trends report: Business resilience special edition[END_REF]. To summarize, as EO-DCN plays a critical role in next-generation backbone data transportation, it is facing a serious challenge from various network failures. Network survivability needs to be addressed considering the evolution of optical network infrastructure, concerning network cost, power consumption, and resource usage [START_REF] Ju | Optimization of Protection Schemes for Next Generation Optical Networks (Optimisation de la Protection des Réseaux Optiques de Nouvelle Génération[END_REF].

Literature review

As this dissertation focuses on the directed pre-configured cycle (p-cycle) protection against single link failure and dedicated backup path protection against disaster failure, we then present the related literature review on p-cycle protection and disaster protection in optical networks.

p-Cycle protection in optical networks

The strategy of p-cycle protection was first proposed in [START_REF] Grover | Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration[END_REF]. A cycle-oriented preconfiguration is designed to remain survivability for a mesh network technology. Different from the self-healing ring, a p-cycle has the ability to achieve the restoration of its straddling spans. The spare capacity assigned for a p-cycle can protect either its on-cycle links or its straddling links. Since the on-cycle link and straddling link of a p-cycle are not affected by a single link failure, the assigned wavelength is configured as the shared mode for all its protected links in this perspective. Also, a few p-cycles can achieve 100% resilience against single link failure, and the p-cycle protection can reduce the spare capacity usage to a large extent. In addition, p-cycles also have fast restoration speed thanks to their ring-like structure. The literature presented that it is possible to reduce recovery times with distributed control system down to the level of 50-100 ms. The authors also provided an ILP formulation for p-cycle network design to minimize the spare capacity usage, where a set of elemental distinct p-cycles is required as the input of the ILP model. Then, thanks to its high spectrum utilization efficiency and fast recovery time, the p-cycle has attracted various researchers to explore network survivability.

Authors in literature [START_REF] Eshoul | Survivability approaches using p-cycles in wdm mesh networks under static traffic[END_REF] proposed two approaches to solve the routing and wavelength assignment problems for both working paths and p-cycles in WDM networks under static traffics. The first approach uses a two-step method. It assigns the spare capacity for the p-cycle first. Then, it solves the working lightpath problem by generating the most likely candidate routes between each source-destination nodes pairs. The second approach jointly solves the two involved problems via an ILP formulation. It also requires a set of candidate cycles as the input of the ILP model. The simulation results have shown that the two-step approach is more recommended in a more complex scenario, while the joint approach had more optimality for a restricted problem.

Literature [START_REF] Xiao | Joint design on dcn placement and survivable cloud service provision over all-optical mesh networks[END_REF] explored the p-cycle protection against single link failure for cloud services in datacenter networks. The joint problem of data center placement, service routing, and network protection were brought together into consideration in the transparent optical network. An ILP model is used to jointly reduce the datacenter network construction cost, the service transmission cost, and the service protection cost. In the ILP model, it requires the p-cycles are enumerated with the cycle exclusion algorithm in advance. Then, a two-step heuristic algorithm was also proposed for the scalability issue. It first solves the problem of datacenter placement and working path routing. Then it configures the p-cycle protection for the working paths.

The p-cycle protection was first brought into EONs in literature [START_REF] Ji | Dynamic p-cycle protection in spectrum-sliced elastic optical networks[END_REF]. The authors investigated a dynamic p-cycle protection design that combines the protected working capacity envelope with spectrum planning. To this end, they proposed an algorithm to achieve a dynamic p-cycle in EONs. It first needs to obtain a set of p-cycles that provide full protection for all the links in the network and then partitions the spectrum resources to either working paths, p-cycle, or both. Spectrum planning allocates the static spare capacity in the spectrum domain to reduce spectrum fragmentation. In order to maintain the coverage of the networks, the authors also proposed to reduce the lengths of backup paths via Hamiltonian cycles and topology partition. In the simulations, the proposed algorithms have shown a lower blocking probability than the shared backup path protection scheme, and the average length of backup paths per request could be controlled well.

Literature [START_REF] Ju | Leveraging spectrum sharing and defragmentation to p -cycle design in elastic optical networks[END_REF] presented two spectrum efficient p-cycles, based on spectrum-shared strategy in EONs. Different from the most adopted spectrum-dedicated p-cycles, the spectrum-shared strategy allows the multiple p-cycle with common link(s) to share their spare capacity, as long as no spectrum conflict exists among them. An ILP model formulated the spectrum-shared p-cycle, whose objective is to minimize the sum of occupied FS margin on all the links and the maximum index of occupied FS. The ILP model also requires the candidate cycle set as its input. Then, a time-efficient heuristic algorithm was proposed to solve the large-scale instances. The simulation results have shown the spectrum-shared p-cycles could cut the spectrum usage and spectrum fragmentation ratio.

Literature [START_REF] Asthana | Distributed protocol for removal of loop backs and optimum allocation of p-cycles to minimize the restored path lengths[END_REF] presented a distributed p-cycle protocol with the consideration of the cycle-circumferences-limited constraints in WDM networks. The p-cycles were established by the distributed protocol for removal of loop backs. It finds all the copies of the same p-cycle in single iteration to lower the computational complexity. The proposed p-cycle design also restricts the maximum hops of the p-cycles to reduce the circumference of the p-cycle. The problem was then formulated as the optimum p-cycle allocation problem and solved by the Hungarian algorithm. The simulation results have shown that the distributed protocol could reduce the computational complexities, and the proposed algorithm could reduce the circumference of the p-cycles. With smaller-sized p-cycles, the propagation delay and excessive signal degradation along the protection path were also reduced. Meanwhile, the reliability of the restored path in the event of second failure was increased.

The above p-cycle designs are based on a two-step approach. First, enumerate apart of or all the p-cycles as the candidates. Then, select the p-cycles via ILP, MILP, or heuristic algorithm. For MILP or ILP, the candidate cycle enumeration causes a too large feasible solution set as the input for ILP and MILP, which shows very limited scalability. Literature [START_REF] Wu | ILP formulations for p-cycle design without candidate cycle enumeration[END_REF] then proposed three different ILP designs of p-cycles without candidate cycle enumeration in WDM networks, based on recursion, flow conservation, and cycle exclusion, respectively. The generated p-cycles are also the elements of the optimal solution set. The ILP models solved the problems of spare capacity placement and joint capacity placement. The objectives of the proposed ILP models are minimizing the total cost of all p-cycles. The simulation results have shown that the most efficient p-cycle design is based on cycle exclusion, which is constructed by the root node and virtual voltage of nodes.

Based on the p-cycle protection of the cycle exclusion, literature [START_REF] Ju | Distance-adaptive, low capex cost p -cycle design without candidate cycle enumeration in mixed-line-rate optical networks[END_REF] extended the voltage-based design combined with the path-length-limited p-cycle in transparent mixed-line-rate WDM networks. Different from the limited number of hops, the scale of the p-cycle is restricted by the protection path length in the consideration of transmission reach at various line rates, which aimed to guarantee the received optical signal along the protection path in the transparent optical network without OEO conversion. An MILP model was proposed to jointly minimize the capital expenditures (CAPEX) cost without candidate cycle enumeration. A graph partitioning algorithm was also developed to deal with large-scale instances. The simulation results have shown a significant CAPEX cost saving achieved from the proposed p-cycle design.

Directed p-cycle protection was explored in literature [START_REF] Rocha | Directed vs. undirected p-cycles and FIPP p-cycles[END_REF], in which three p-cycle strategies, i.e. directed p-cycle, undirected p-cycle, and failure independent path protecting (FIPP) p-cycle, were compared via column generation algorithm. The FIPP p-cycles can provide end-to-end path protection in addition to link protection. The authors evaluated the impact on the cost of p-cycle-based networks under asymmetric traffic scenarios. The authors reported that the use of asymmetric links is very cost-effective under asymmetric traffic scenarios. The simulation results have shown a reduction of up to 45% in the cost of directed models over undirected models with asymmetric links. The efficiency gain increased linearly as traffic asymmetry augments.

Literature [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF] then proposed the voltage-based directed p-cycle with distance adaptive consideration on power-efficient protection for asymmetric traffic in EONs. Four different modulation formats were adaptively assigned for each p-cycle based on the transmission reaches of the modulation format and the protection path lengths of the p-cycle. An ILP model formulated the joint problem including directed p-cycle generation, spectrum allocation, and adaptive modulation formats selection without candidate cycle enumeration. The objective of the ILP model aims to minimize the power consumption of the deployed BVTs, OXCs, and OAs, and the spare capacity usage. Extensive simulations have shown that the directed p-cycle design could achieve power savings up to 47.9% compared with the conventional undirected p-cycles with the scenarios of pure asymmetric traffics.

Disaster protection in optical networks

The disaster protection design was first proposed in literature [START_REF] Habib | Design of disaster-resilient optical datacenter networks[END_REF], in which the authors brought together the subproblems of content placement, routing, path protection, and content protection in WDM datacenter networks. They used the concept of the disaster zone to mark the links and nodes that can be affected by the same failure, which is also named as SRLG. The disaster modeling for the links and nodes is widely used in disaster resilience works. Then, each backup path is then constructed as DZ-disjoint to the working path of the same request provisioning. The working DC and backup DC are also selected as DZ-disjoint to maintain the disaster failure resilience. To formulate the joint problem, an integrated ILP model was proposed to solve the subproblems synchronically. In addition, a two-step ILP model and LP relaxations were also proposed to decompose the complex integrated ILP model. A heuristic algorithm was used to find a feasible solution from the LP-relaxed solution. The results have shown a significant improvement of the proposed disaster protection that exploits anycast technique with less spectrum usage, compare with the conventional dedicated single-link failure protection. Furthermore, proportionate DC locations and corresponding content placement would provide better survivability for the networks.

Literature [START_REF] Savas | Disasteraware service provisioning with manycasting in cloud networks[END_REF] investigated survivable cloud service provisioning against large-area network failures, in an effort to minimize the effects of network/datacenter failures and maintain critical services in case of a disaster. The authors proposed a novel disasteraware service-provisioning scheme by multiplexing service over multiple paths destined to multiple servers/datacenters with manycasting. The scheme can offer a service with a degraded level after a failure occurs. An ILP model was proposed based on the k-shortest path routing, of which the input is the path routed from each node to each datacenter. It aims to reduce bandwidth loss and network resource utilization in the case of a disaster. The heuristic optimization approaches were also provided for large problem instances. The manycasting was configured in a risk-aware manner for service provisioning by intelligently selecting ending nodes. Numerical examples have shown that exploiting manycasting can provide a high level of survivability with no extra cost compared to the other survivable schemes.

Literature [START_REF] Savas | Backup reprovisioning with partial protection for disaster-survivable software-defined optical networks[END_REF] then introduced a backup reprovisioning with a partial protection scheme against disaster failure in WDM networks. The motivation was that full protection against disaster failure would require massive and economically unsustainable bandwidth overprovisioning. The dedicated backup path protection in the scheme allowed backup resources reserved but not provisioned (as in shared-path protection). Such that the reserved bandwidth for backup paths as well as their routings is subject to dynamic changes, given the network state, to increase utilization. By exploiting the approach of Software-Defined Networking (SDN), the authors implemented the algorithmic solutions in a network of OpenFlow-enabled switches and servers. The results have shown that the network resources were better allocated with more connections being provisioned. The improved performances came from the flexibility from the means of backup paths degrading.

Due to lack of appropriate mechanisms deployed in practice within Europe, the EU-funded Resilient Communication Services Protecting End-user Applications from Disaster (RECODIS) project was then formed, aiming to develop promising solutions to provide cost-efficient resilient communications in the presence of disaster-based disruptions. The project considers both existing and communication networks (e.g. IPv4/IPv6based, current Internet) and emerging network architectures (e.g. EONs) [START_REF] Rak | Recodis: Resilient communication services protecting end-user applications from disaster-based failures[END_REF]. Apart from developing the relevant mechanisms, such as routings against disaster failure, RE-CODIS also offers suggestions for network operators on how to design and maintain networks to improve their resilience to disaster failures (based on topological characteristics of networks). Furthermore, the Action aims to address research issues that are strategically important for Europe, not only in terms of science and technology, but also in terms of important socio-economic issues, because the survivability of communication and emergency services, in any disaster-related scenario, is critical for people who require rapid information exchange.

The members in working group 1 of RECODIS then presented a comprehensive survey of network protection strategies against large-scale natural disasters in literature [START_REF] Gomes | A survey of strategies for communication networks to protect against large-scale natural disasters[END_REF]. In this work, an overview of the network vulnerability to failure caused by disaster disruptions was presented, covering network vulnerability measurements, identification of sensitive locations, and physical infrastructure vulnerability. The researchers then looked at guidelines and approaches for making network topologies less sensitive to disaster-related failures. There were two options for moving forward: Pre-disaster network resilience enhancements, such as in-network and out-network solutions; as well as post-disaster network/service recovery approaches, such as rapid emergency communication network deployment and effective network maintenance Finally, disaster-resilient routing algorithms were defined as customisable survival against a single link loss, resilience against several failures, spatio-temporal disaster-aware routing, and post-disaster routing.

Literature [START_REF] Pašić | Fradir: A novel framework for disaster resilience[END_REF] reported a framework for disaster resilience (FRADIR) in optical networks. FRADIR aims to increase the availability of mission-critical applications. The work integrated robust network design, disaster failure modeling, and protection routing. FRADIR forms a spanning tree (the considered spine) with links with higher availability, which can improve the connectivity between the communication end-points of critical services. The disaster survivability is guaranteed by dedicated backup path protection approaches. The simulation results have shown a significant improvement in the network performance in terms of blocking probability and average resource consumption. Then, FRADIR was further explored in literature [START_REF] Pašić | Fradir-ii: An improved framework for disaster resilience[END_REF][START_REF] Pašić | Fradir meets availability[END_REF], in which the authors observed a trade-off between the average bandwidth consumption, the blocking probability, and the availability for any of the investigated protection routings (1 + 1 and four versions of general dedicated protection). They introduced a novel routing method that minimizes bandwidth cost while ensuring protection against certain failure events. The method can also guarantee the communication path still satisfies a certain availability level after any of these failure events.

Literature [START_REF] Tomás | Disaster recovery layer for distributed openstack deployments[END_REF] presented the disaster recovery layer that enabled OpenStack-managed DC workloads, virtual machines, and volumes, to be protected and recovered in another DC. The main goal was to implement efficient OpenStack integration, extensibility of the protection and restoration approaches, low-resource overhead, fast recovery, and transparent operation. A distributed failure detection technique was also considered, based on the idea of voters deciding on the condition of a DC using information received from multiple pingers. The experiments have shown that the proposed replication policies outperformed the snapshot-based methods, in terms of protection and recovery times, with efficient use of the available spectrum.

Literature [START_REF] Xu | Disaster survivability in elastic optical datacenter networks[END_REF] proposed shared backup path protection to ensure disaster resilience in the elastic optical DC networks, considering both anycast method and unicast method. The anycast method was used for the end-to-content services, where a requesting node was provisioned by a certain content with the required data rate. One of the potential DCs was then assigned as the destination node. Different from anycast method, the unicast method specified a destination node. An ILP model formulated the proposed scheme with the objective of maximizing the network throughput. It also solved routing and spectrum assignment problems for anycast method. In the testbed of the 6-node network, the simulation results have shown that the anycast method consumed much less spectrum usage, but with the same throughput as that of unicast.

Literature [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF] brought together with the problems of content and DC placement, DZ-disjoint working path and backup path generation, spectrum allocation, and distanceadaptive modulation format assignment in EO-DCNs. The authors adopted two spectrum allocation methods, forming dedicated end-to-content backup path protection (DEBPP) and shared end-to-content backup path protection (SEBPP) with 100% resilience against disaster failure. An ILP formulation was proposed to jointly minimize spectrum usage, consisting of the total assigned FSs and maximal index of assigned FSs. A column generation approach was also developed to handles large requests. The simulations were also conducted to see how bad the situation can be without path protection and to study how much the recovery time DEBPP earns compared with the SEBPP in EO-DCN. The simulation results have shown a significant improvement of the proposed methods over the conventional ones, and the proposed SEBPP needs less spectrum usage at the expense of a longer disaster recovery time.

Conclusion

In this chapter, we reported the current Internet traffic trends. By presenting the key enabling technologies, and enabling hardware of next-generation optical networks, we obtain an overview of the emerging EO-DCNs. Next, we introduce the survivability issue of the communications in optical networks, including its main threats, classic network protection methods, and challenges. At last, we provided the related literature review on p-cycle protection and disaster protection in optical networks.

Protection and restoration in optical networks

To maintain survivability against network outage, two main approaches are widely explored, i.e. network protection and network restoration, as shown in Fig. 2.1. Network protection is a preplanned strategy. The basic idea is to pre-configure certain spare capacity (reserved protection capacity) for the backup paths or rings. When the primary path is affected by some network failure, the spare capacity can be switched to carry on the transmissions in a very short time. As opposed to it, network restoration is a post-failure strategy. It assigns the network resources after the network failure occurs and recovers the affected services. Network restoration generally needs a longer recovery time, because the protection paths and spectrum for a certain failure have to be determined dynamically according to the available network resources. It is a crucial issue that the mechanisms and algorithms need long processing time to implement the restoration after the failure occurs [START_REF] Goscien | Protection in elastic optical networks[END_REF]. Also, network restoration has lower reliability. The failure is not 100% restorable. It may fail to find sufficient network resources to rebuild the failed path. Thus, in this dissertation, our main focus is on protection methods in EONs. [START_REF] Bao | Adaptive path splitting based survivable virtual network embedding in elastic optical networks[END_REF][START_REF] Habib | Design of disaster-resilient optical datacenter networks[END_REF][START_REF] Ju | Leveraging spectrum sharing and defragmentation to p -cycle design in elastic optical networks[END_REF][START_REF] Shen | Survivable elastic optical networks: survey and perspective[END_REF].

For network protection schemes, they differ as they pre-allocate either the dedicated or shared spectrum for the backup paths or rings. For instance, in the path protection schemes, the spectrum assigned for the paths allows overlapping as long as any two or more paths are not activated or used at the same time in shared backup path protection (SBPP). However, the FSs can be assigned for only one path in the dedicated backup path protection (DBPP). The shared spectrum allocation mode is also used for ringbased protection, e.g. p-cycles [START_REF] Ju | Leveraging spectrum sharing and defragmentation to p -cycle design in elastic optical networks[END_REF]. It is specified in the Section 2.2.

Generally, the shared backup protection is more efficient on spectrum usage, but it requires a longer recovery time (time elapsed from when the network service outage occurs to the recovery of the affected service), compared to dedicated backup protection. The reason for this is that the FSs allocation is not configured for any certain backup path in the shared protection mode. It needs to be determined when the failure occurs. The spectrum configuration is the main latency of the recovery time. Similarly, network restoration is most efficient on the spectrum usage as it does need to reserve any redun-dant resources for the backup. But it suffers a long recovery time as it needs to reroute the paths and allocate them with the appropriate spectrum.

Network restoration can also be divided into link restoration and path restoration depending on the restoration aiming to rebuild the damaged link or jammed path. While network protection can also be divided into three protection strategies on either link level or path level or disaster level. In link protection, the link failure is only detected by its adjacent nodes. The backup path and its spectrum are pre-configured between these two detecting nodes. In the path protection, the failure is aware to the source node of the traffic demand via failure-informing message hop by hop [START_REF] Ramamurthy | Survivable WDM mesh networks[END_REF]. Thus, it can protect the primary path against any failure that occurs and affects the path. The disaster protection, however, involves path protection against multi-links and -nodes failure. A disaster may cut off many links and affects several nodes at the same time. It is by far the most complicated and urgently needed network protection [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF].

Ring-based protection is a classic structure to protect a single link as it can protect any on-cycle link of the ring. It can be divided into undirectional path switched rings (UPSR) and bidirectional line switched ring (BLSR) [START_REF] Shen | Survivable elastic optical networks: survey and perspective[END_REF].

Path protection usually uses a backup path to protect the primary path, namely 1 : 1 path protection, such that the connection is switched on the backup path if a primary path is cut off [START_REF] Chatterjee | Routing and spectrum allocation in elastic optical networks: A tutorial[END_REF], a case also shown in Fig. 2.5. The up-to-date path protection is currently developing to n : 1 path protection, where one primary path can be split into n different paths and 1 backup path with the help of rateless coding. Thus, the backup path only needs to protect any one of the n primary paths [START_REF] Bao | Adaptive path splitting based survivable virtual network embedding in elastic optical networks[END_REF].

Classic Protection Schemes

In this section, we present the classic schemes and the up-to-date works on network protection. A various of protection schemes were proposed facing different kinds of network failure under different conditions. Among them, the protection against single link failure is by far the most extensively researched since it is the most common failure, which usually occurs when the optical fiber cut during the operation of network configurations. Apart from single link failure, the disaster failure draws lots of attentions in recent years. The disaster protection is much more complicated and urgently needed for current and next-generation optical networks. We then summarize the protection schemes based on their failure types and protection strategies.

Single link failure protection

Single link failure can be protected by link protection and path protection, depending on the detection technique used in the optical networks. We then discuss how the link protection and path protection are configured against single link failure, as well as their FS allocation with shared mode and dedicated mode. Note that network protection aims to provide 100% resilience against the single link failure.

(1). Link protection

As aforementioned, single link failure in the the link protection is only detected by two ending nodes of the link. Thus, the basic idea of link protection is to build a backup path between two ending nodes of the each used link. If any working link is failed, the corresponding backup path will then replace the damaged link to carry on the traffic, such that the connection can be maintained after the failure occurs. An instance is shown in Fig. 2.2. Two backup path candidates, i.e. path 1-5-4-2 and path 1-6-5-4-3-2, can be configured in the 6-node network. Any one of them can protect the link (1, 2) against failure. The backup path selection is determined by the optimization objective, such as the number of used FSs and power consumption. The spectrum is also pre-assigned for the backup paths can be configured with either shared or dedicated mode. A case is shown in Fig. 2.3 for better clarification. Note that the assigned modulation format is assumed to be BPSK in transparent EONs for simplicity. Two different links are loaded with traffics, where link (1, 2) carries 5 FSs traffics and link (3, 2) carries 3 FSs traffics. The backup path 1-5-4-2 is configured to protect link (1, 2) and backup path 3-4-2 is configured to protect link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF]. The backup paths have one common link, i.e. link (4, 2). In the shared mode, they can share FSs 1 to 3 since single link failure will not fail links (1, 2) and (4, 2) simultaneously, as shown in Fig. 2.3 (a). On the contrary, the FS overlapping is prohibited in the dedicated spectrum allocation. Thus, they are assigned with different FSs in Fig. 2.3 (b). Note that the assigned FSs for a lightpath should be continuous according to the spectrum contiguity constraints aforementioned, and all the used links of the backup path are assigned with the same FSs according to the spectrum continuity constraints.

(2). Path protection

• 1 : 1 Backup Path protection
Path protection is also known as backup path protection. As aforementioned, the detection of single link failure in the path protection can be transferred to the ending nodes of the paths hop by hop. Thus, the backup path can be configured between two ending nodes. The most extensively studied backup path protection is 1 : 1 backup path protection, where one working path and one backup path are configured for each request. The backup path should be implemented as link-disjoint to the working path. In other words, two paths do not have any common link to ensure the single link does not affect both two path at the same time. A case of path protection in an 8-nodes network is shown in Fig. 2.4. The working path 5-6-1-2 is threatened by link failure from link [START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF][START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF], [START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF][START_REF] Adachi | The restoration of telecom power damages by the great east japan earthquake[END_REF], and (1, 2). It can be protected by either protection path 5-7-8-2 or protection path 5-4-3-2. Protection path is also known as backup path. In this work, we use them interchangeably. The protection paths are both link-disjoint from the working path, and any one of two protection paths is sufficient to protect the connection from single link failure. Different from link protection, path protection is able to provide resilience against multilink failure in some cases.

Similar to the link protection, the path protection can also be divided into shared mode and dedicated mode regarding its spectrum allocation. They are SBPP and DBPP, respectively. For instance, Fig. 2.5 shows the a case of two requests provisioned by 1 : 1 SBPP and DBPP with modulation format of BPSK. The request 1 and 2 are with 4 and 2 FSs, respectively. They are provisioned by working paths 6-7-8-3 and 5-7-1-2, respectively, and they are protected by paths 6-5-4-3 and 5-4-8-2, respectively. It can be seen that two working paths are not threatened by the same network failure, i.e. single link failure, in this case, and two protection paths have one common link [START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF]. Thus, in SBPP, the assigned spectrum can be overlapped for the protection paths. As shown in Fig. 2.5 (a), FSs 1 to 2 can be assigned for both the protection paths 1 and 2 simultaneously. The DBPP, however, can only assign each FS for only one path on each link. Also, the assigned FSs for each path (including working path and backup path) should be continuous according to the spectrum contiguity constraints, and all the used links of each path are assigned with the same FSs according to the spectrum continuity constraints. Apparently, the SBPP is more efficient on the spectrum usage but more complicated on the configuration.

• n : 1 Backup Path protection Apart from 1 : 1 backup path protection, n : 1 backup path protection was proposed for less spectrum usage. It uses rateless erasure coding to split the working path into several paths, and one backup path is configured to protect any of the working paths against a single link failure. Specifically, the original data can be divided into several data blocks, say data of size K divided into m fragments. Each fragment is of equal size as K/m. They are then joint encoded into n blocks of the same size, using an (n, m) maximum distance separable (MDS) code. Any set of m blocks would recover the original data [START_REF] Anglano | Exploiting rateless codes in cloud storage systems[END_REF][START_REF] Dimakis | Network coding for distributed storage systems[END_REF][START_REF] Liu | Exact-repair codes with partial collaboration in distributed storage systems[END_REF][START_REF] Torre | Implementation of network-coded cooperation for energy efficient content distribution in 5g mobile small cells[END_REF]. For the backup path protection, we can always split a working path (requiring K Gbps) into several paths via an MDS code, say n + 1 total paths including n working paths and 1 backup path. Each path is with an equal data rate (K/n Gbps). Any set of n paths can satisfy the bandwidth requirement of the request. Thus, if any working path is blocked by a single link failure, the backup path can be switched with other n -1 working paths to continue the service provisioning. The n : 1 backup path protection is more complicated than 1 : 1 backup path protection since each of the n + 1 paths should be configured as link-disjoint to any other path [START_REF] Bao | Adaptive path splitting based survivable virtual network embedding in elastic optical networks[END_REF]. Fig. 2.6 shows an instance of n : 1 backup path protection with the modulation format at BPSK in COST239 network. Assuming that the request demands 8 FSs bandwidth. For 1 : 1 backup path protection, both the working path and the backup path need to be assigned with 8 FSs, as shown in Fig. 2.6 (a). The n : 1 backup path protection allows the multiple working paths, 4 working paths in Fig. 2.6 (b) and each with 2 FSs. A backup path with 2 FSs is sufficient to protect them from single link failure as they are configured as link-disjoint. Although the sum of the bandwidth of working paths remains the same, the bandwidth of the backup path can be reduced to a fraction of that of the former one.

Note that there exists some overhead of path splitting design in n : 1 backup path protection. Generally, the first working path is probably the shortest path between two ending nodes. Each additional path has no less hop than the former one. The solution with a maximum number of paths can reduce the bandwidth pressure of each path, but it may consume more overall spectrum resources of the network with more occupied links. Thus, it requires an adaptive mechanism to obtain an optimistic solution. (

3). p-Cycle protection

• Undirected p-cycle

The method of p-cycle has high spectrum utilization efficiency and fast recovery time due to its ring-like structure. It can be designed to provide resilience for the on-cycle spans and straddling spans against either single link failure or single node failure. As the nodes in the EONs are relatively robust compared to the optical links, we focus on the p-cycle protection against single link failure. We first introduce the traditional p-cycle, which is designed as undirectional to protect the traffic in both directions for every single link.

The basic idea of undirected p-cycle is shown in Fig. 2.7. For such a 6-nodes network, the p-cycle 1-2-3-4-5-6-1 is able to provide full protection for each link, including on-cycle links and straddling links. Specifically, a case of undirected p-cycle protection is shown in Fig. 2.8, where the modulation format is assumed to be BPSK for simplicity. Fig. 2.8 (a) shows the protection path of the affected on-cycle link. When on-cycle link (1, 2) is failed, the protection path 1-6-5-4-3-2 is then replacing the link (1, 2) to carry on the corresponding traffics. The protection path also needs to be reserved with sufficient spare capacity, e.g. 4 FSs in this case. The protection of the link (2, 1) failure is similar. The protection of straddling links is different. As shown in Fig. 2.8 (b), the link [START_REF] Adachi | The restoration of telecom power damages by the great east japan earthquake[END_REF][START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF] failure is protected by two backup paths 1-6-5 and 2-3-4-5, such that each path can be assigned only half of the FSs on the working link. In this case, the link (1, 5) carries with 8-FSs traffic, and the p-cycle can be assigned with 4 FSs spare capacity. Note that the undirected p-cycle can protect the bidirectional links and unidirectional links. The traffic is asymmetrical for unidirectional links. A bidirectional link can be regarded as two unidirectional links in opposite directions.

• Directed p-cycle

As it is noticed, the introduction of Ultra-High-Definition (UHD), or 4K, video streaming is anticipated to occupy the majority of the Internet traffic [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. There is already support for 8K and 16K Full UHD videos on YouTube. The business traffics show an extra asymmetric feature to next-generation EO-DCNs [START_REF] Walkowiak | Evaluation of impact of traffic asymmetry on performance of elastic optical networks[END_REF]. In this context, the directed p-cycle design is proposed to better support asymmetric-traffics protection [START_REF] Rocha | Directed vs. undirected p-cycles and FIPP p-cycles[END_REF].

It exhibited an improvement of up to 45% over undirected p-cycles with the scenarios of pure asymmetric traffics.

The traditional p-cycle and directed p-cycle designs are illustrated in Fig. 2.9. Specifically, Fig. 2.9 (a) shows that the directed p-cycle and undirected p-cycle are configured to protection links (1, 2), (6, 2), and [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF], where the modulation format is operated at BPSK for simplicity. Fig. 2.9 (b), shows the protection paths of the directed p-cycle. The link (1, 2) is protected by path 1-6-5-3-2, the link (6, 2) is protected by path 6-5-3-2, and link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF] is protected by path 3-2-1-6-5. The assigned FSs for the directed p-cycle should be no less than that of the protected links. In this case, the number of assigned spare capacity is 8 FSs for each on-cycle link of the directed p-cycle. The undirected p-cycle, however, needs to assign the network resources on both fibers of each on-cycle link, as shown in Fig. 2.9 (c). Although the protection of link (6, 2) can be split into two paths with half FSs, the extra FSs assigned on the opposite-on-cycle links greatly waste spectrum in such an asymmetric-traffic scenario.

• Modulation format assignment of p-cycles

The modulation format assignment for link protection and path protection is based on the length of the protection path. Different from them, the modulation format assignment for the p-cycle design is based on the length of cycle circumference or upper bound of protection path lengths [START_REF] Asthana | Distributed protocol for removal of loop backs and optimum allocation of p-cycles to minimize the restored path lengths[END_REF][START_REF] Huang | Distributed protocol for removal of loop backs with asymmetric digraph using gmpls in p-cycle based optical networks[END_REF][START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Kodian | The threshold hop-limit effect in p-cycles: Comparing hop-and circumference-limited design[END_REF][START_REF] Yadav | P-cycle based network design to control the optical path lengths in restored state of transparent network[END_REF]. Such a mechanism is directionirrelevant, as the cycle circumference and protection path length are the same for each direction of a p-cycle. Thus, the modulation format assignment is the basically the same for the designs of directed p-cycle and undirected p-cycle.

We then introduce cycle-circumference-length-based and path-length-based modulation format assignment in Fig. 2.10, where p-cycle is configured to protect link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF] and link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF]. As shown in Fig. 2.10 (b), the modulation format assignment is roughly based on the total link distances of a p-cycle. The length of cycle circumference of the p-cycle in this case is 5, 600 km, which leads to only the BPSK can be operated to the p-cycle with spectral efficiency of 1 bps/Hz. The length-adaptation modulation format refers to work [START_REF] Chen | On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks[END_REF]. With path-length-based modulation format assignment, however, the longest protection path is then reduced as 4, 700 km, as shown in Fig. 2.10 (c). The longest path 3-2-1-4 does not take link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF] into consideration since it is the protected link. Thus, the highest-order modulation format is QPSK for the p-cycle with spectral efficiency of 2 bps/Hz. Meanwhile, the link protection is fully guaranteed in this case. The path-length-based p-cycle is the up-to-date work and it shows great performance on spectral efficiency. Nevertheless, we should point out the flaws of the current work. It has an excellent approximation on each protection path of the on-cycle link in modulation format assignment, but it lacks the means to determine the protection path of the straddling links. Specifically, the path-length-based p-cycle uses decrement to approximate the length of protection path in MILP [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Ju | Distance-adaptive, low capex cost p -cycle design without candidate cycle enumeration in mixed-line-rate optical networks[END_REF], as shown in Eq.(2.1).

l path = c cycle -l straddling (2.1)
where l path is the estimated length of protection path, c cycle is the length of cycle circumference, and l straddling is the length of the protected straddling link.

Such the formulation requires each triangle in the network topology to satisfy the trigonometric inequality principle [START_REF] Ju | Optimization of Protection Schemes for Next Generation Optical Networks (Optimisation de la Protection des Réseaux Optiques de Nouvelle Génération[END_REF]. However, the links in the realistic scenario are not always implemented with straight lines. The fiber cables are erected crossing mountains or dived through the waters due to the cost of laying. In a lot of network topologies, such as German network, NSFNET network, COST239 network, and US Backbone network [START_REF] Habib | Design of disaster-resilient optical datacenter networks[END_REF][START_REF] Mello | Optical networking with variable-code-rate transceivers[END_REF], there exists the sub-topology that the sum of the lengths of two sides of some triangles is less than its third side.

Two specific cases of directed p-cycle based on the rough upper bound are shown in Fig. 2.11, where the exact protection path length is the same, 2, 300 km. For case (a) in Fig. 2.11 (a), each triangle in the topology satisfies the trigonometric inequality.

According to the Eq.(2.1), the protection path length for case (a) is 2, 900 km, in which the approximation is not sharp but can provide an upper bound to assign modulation format. For case (b) in Fig. 2.11 (b), the length of straddling link is than than sum of any other two sides. The protection path length is estimated to be 1, 900 km by the Eq.(2.1), which is less than the actual path length. If the modulation format is assigned according to an underestimated path length, the actual path length is likely to be bigger than the transmission reach of the modulation format. It will lead to the optical signal not being demodulated correctly at the receiver.

Disaster failure protection

In addition to the single link failure, the disaster failure can cause a severe network break-off for a relatively long time (10 days on average). It can be regarded as a network failure with multiple failed links simultaneously, in which these links are then called shared risk link group (SRLG) [START_REF] Develder | Joint dimensioning of server and network infrastructure for resilient optical grids/clouds[END_REF][START_REF] Pašić | Fradir: A novel framework for disaster resilience[END_REF]. The links of an SRLG are normally geographically aggregated, and they are located in the same disaster zone (DZ), e.g. earthquake, and under the threats from the same disaster.

(

1). Disaster-zone-disjoint path protection

Most of the methods of disaster failure protection are backup path protection. Different from that against single link failure, the paths of disaster failure protection need to be configured as DZ-disjoint. The DZ-disjoint path protection can guarantee full protection against a single DZ failure. The disaster failure can affect increasing requests as the traffic grows. Fig. 2.12 shows the number of affected requests per DZ on average, in the NSFNET network and US Backbone network, respectively [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF] (readers who are interested in further details of the simulations may refer to work [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF]). It shows the DZ-disjoint path protection can provide survivability against a single disaster, and they can recover 100% requests from the single DZ failure. The figure shows how bad the situation can be without path protection if a single disaster occurs. The affected requests for the path protections remain 0 regardless of the scale of demands and networks. However, the affected requests per DZ go up to 11% of the total requests without path protection. Fig. 2.13 shows the backup path protection difference between single link failure and disaster failure. The working path 6-7-8-2 goes through a DZ. Two different protection paths are configured in Fig. 2.13 (a). Path 6-1-2 is a typical link-disjoint protection path to the working path, and path 6-5-4-3-2 is a DZ-disjoint protection path to the working path. The disaster failure can damage a set of links, including bidirectional links [START_REF] Adachi | The restoration of telecom power damages by the great east japan earthquake[END_REF][START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF], [START_REF] Adachi | The restoration of telecom power damages by the great east japan earthquake[END_REF][START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF], [START_REF] Adachi | The restoration of telecom power damages by the great east japan earthquake[END_REF][START_REF] Andrae | New perspectives on internet electricity use in 2030[END_REF], [START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF][START_REF] Andrae | New perspectives on internet electricity use in 2030[END_REF], [START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF][START_REF] Andrae | New perspectives on internet electricity use in 2030[END_REF], and [START_REF] Andrae | New perspectives on internet electricity use in 2030[END_REF][START_REF] Anglano | Exploiting rateless codes in cloud storage systems[END_REF]. Apparently, the link-disjoint protection path is unable to protect the services against disaster failure. The DZ-disjoint path 6-5-4-3-2 is then switched on to continue the connection, as shown in Fig. 2.13 (b).

(2). End-to-content backup path protection against disaster failure in EO-DCNs

The cloud services allow clients to access DCs to obtain the required services, such as cloud computing, and video on demand. Distributing the resources or contents in several DCs can achieve higher robustness, lower latency, and lower cost. Such content delivery and cloud computing services are provisioning-node-insensitive for the requesting node. It does not need to assign a certain service provisioning node but to guarantee the required content can be transmitted to the requesting node. Anycast technique is then implemented to transmit the required content from any of the contentstored DCs. These location-separate DCs store the whole replicas or encoded fragments of the contents. To protect such end-to-content services, end-to-content backup path protection is then proposed against disaster failure. It is divided into dedicated end-tocontent backup path protection (DEBPP) and shared end-to-content backup path protection (SEBPP) based on the spectrum allocation principles [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF].

A case of DEBPP is shown in Fig. 2.14 operating the modulation format at BPSK in the NSFNET network. The request r 1 (3, 1, 5) represents node 1 requires for content 1 with 5 FSs bandwidth when using BPSK, and the request r 2 (10, 2, 3) represents node 10 requires for content 2 with 3 FSs bandwidth when using BPSK. The DCs that store replicas of content 1 are located in nodes 7, 11, and 13, while the DCs that store replicas of content 2 are located in nodes 1, 9, and 12. The DCs for each content are distributed as DZ-disjoint against disaster-caused node failure. Then, the primary DCs for r 1 and r 2 are at node 1, and 7, respectively, and the backup DCs for r 1 and r 2 are at node 9, and 13, respectively. The DEBPP uses the multicast technique to provision the requests with a set of selected DCs. Two DCs thus corresponds to one primary path and one protection path. Both DZ-disjoint DCs and DZ-disjoint paths are guaranteed against a single DZ failure. The same case of SEBPP is shown in Fig. 2.15. The only difference lies in the spectrum allocation of links [START_REF] Asghar | Survivable inter-datacenter network design based on network coding[END_REF][START_REF] Appdynamic | The rise of AIOps: How data, machine learning, and ai will transform performance monitoring[END_REF] and [START_REF] Appdynamic | The rise of AIOps: How data, machine learning, and ai will transform performance monitoring[END_REF][START_REF] Bao | Adaptive path splitting based survivable virtual network embedding in elastic optical networks[END_REF]. As the primary paths of two requests are not affected by the same DZ, the FSs of backup paths can be assigned as overlapped. Thus, the FSs index of the backup path of r 1 is from 1 to 3 in the SEBPP, Fig. 2.16 shows the recovery time for DEBPP and SEBPP in the NSFNET network and US Backbone network, respectively (readers who are interested in further details of the simulations may refer to work [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF]). The results have shown that the dedicated mode required much less time to recover a request on average. For the path protection with dedicated spectrum allocation, the recovery time only consists of messageprocessing time, propagation delay, and failure detecting time, which is in several µs. It shows that the recovery time for DEBPP then remains from 2 ms to 4 ms. However, when a connection is set up in shared spectrum allocation mode, e.g. SEBPP, spectrum resource is reserved in advance for backup paths but optical cross-connects (OXCs) are not configured to allow for sharing of backup FSs [START_REF] Ramamurthy | Survivable WDM mesh networks[END_REF]. Thus, SEBPP needs extra time to configure OXCs at each intermediate node of the backup path, which is the main delay in the recovery time. It can be seen that SEBPP requires much more time to recover a connection after the disaster failure occurs, up to 150 ms.

Challenges of network protection in EO-DCNs

The Internet traffic presents continuous and strong growth for next-generation optical networks. The annual IP traffic is predicted to reach 4.8 ZB by 2022 with a compound annual growth rate of 26% since 2017 [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. Every network failure would cut off the massive connections and lead the losses of up to millions of dollars per minute. Network protection is an essential mechanism to maintain the survivability of Internet services. However, the implementation of network protection would add to the heavy burden of optical networks. The conventional 1 : 1 dedicated backup path protection, for example, at least doubles the power consumption and the spectrum usage, compared to the configuration without any protection. It is a challenging task to further reduce the network protection cost while maintaining network survivability. In this dissertation, we focus on two different network protections against single link failure and disaster failure in EO-DCNs, respectively. The former one corresponds to the most common network failure scenario, fiber cut, while the latter one corresponds to the larger-scale network failure caused by the natural disaster.

Power-efficient directed p-cycle protection in EO-DCNs against single link failure

With dramatic Internet traffic growth, the power consumption to support the ICT industry is enormous. The electricity use of the Internet is predicted to rise as 8, 263 TWh by 2030, occupying 20% of global electricity [START_REF] Andrae | New perspectives on internet electricity use in 2030[END_REF]. As the EO-DCNs permit the flexibility of data transmission, it requires a novel network protection mechanism with better power savings and less spare capacity usage. To this end, the directed p-cycle protection has been demonstrated to better protect the asymmetric traffic against single link failure [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Rocha | Directed vs. undirected p-cycles and FIPP p-cycles[END_REF]. The studied directed p-cycle protection problem is N P-hard, as it contains an N P-hard problem of RMSA [START_REF] Ju | Optimization of Protection Schemes for Next Generation Optical Networks (Optimisation de la Protection des Réseaux Optiques de Nouvelle Génération[END_REF]. Apart from guaranteed network protection against single link failure, other main considerations of directed p-cycle in EO-DCNs are summarized as follows.

• The ILP formulation of directed p-cycle generation without candidate cycle enumeration: The number of directed p-cycle candidates is up to hundreds. The conventional two-step ILP model, candidate cycle enumeration first network allocation after, has an extremely high computational complexity. It is a challenging task to design the ILP formulation that gives the directed p-cycle generation without candidate cycle enumeration.

• Modulation format adaptation in terms of compact protection path length versus transmission reach of modulation format: The current modulation format is based on a rough upper bound of the estimated path lengths, which causes a waste of network resources to a large extent. It is urgent to be improved with a better modulation format adaptation design.

• Directed p-cycle protection with less power consumption: The power consumption in EO-DCNs is mainly caused by the BVTs, OXCs, and optical amplifiers (OAs) [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF]. How to schedule them in a more efficient way is a significant issue when reducing the energy cost.

• Spectrum allocation for the used directed p-cycle. It is also a key sub-problem to allocate the FSs to the directed p-cycles.

Spectrum-efficient backup path protection in EO-DCNs against disaster failure

The network protection against disaster failure was first raised in 2012 [START_REF] Habib | Design of disaster-resilient optical datacenter networks[END_REF]. The network failure caused by large-scale disasters has much a severe impact on the Internet traffics and datacenters, in both time and space dimensions. To this end, suffering from huge financial losses, the datacenter network needs specific protection concerning both the Internet service and datacenter survivability. The 1 : 1 backup path protection is the only existing network protection strategy against disaster failure. It is a challenging task to reduce the spectrum usage while maintaining disaster resilience in EO-DCNs.

The main considerations of backup path protection in EO-DCNs are summarized as follows.

• Content partition in EO-DCNs: A cooperative strategy can be utilized to distribute the content to several DCs via MDS coding. The content partition is then attractive as reducing the content storage space on each DC sufficiently benefits the electricity savings. It is related to the distribution of requesting nodes.

• DC assignment and content placement: Based on the probable DC locations, the DCs need to be assigned in the optimized nodes to better reduce the spectrum usage for each path, as well as keep the disaster resilience. Then, different kinds of content should also be distributed as DZ-disjoint to maintain content survivability.

• Adaptive path generation: Different 1 : 1 backup path protection, n : 1 backup path protection can be adopted with less spectrum usage. However, n should be further optimized for each request, because more paths, i.e. larger n, does not necessarily lead to less spectrum usage [START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF].

• RMSA problem: The generation of each path should also solve the routing, modulation format, and spectrum allocation problem, i.e. RMSA problem. Each request should be provisioned by several primary DCs and one backup DCs using anycast technique. In addition, all the paths should be generated as DZ-disjoint, which has been stated as an N P-hard problem [START_REF] Chatterjee | Routing and spectrum allocation in elastic optical networks: A tutorial[END_REF].

(

3). Power-efficient and distance-adaptive backup path protection for service function chain (SFC) provisioning in EO-DCNs against disaster failure

We then extend the disaster protection problem for SFC-based services in network function virtualization (NVF) embedded EO-DCNs with power-efficient and distanceadaptive considerations. For SFC provisioning, the streaming of the services needs to be processed by the corresponding SFC, which consists of an ordered set of virtual network functions (VNFs) [START_REF] Li | Gnn-based hierarchical deep reinforcement learning for nfvoriented online resource orchestration in elastic optical dcis[END_REF]. A video streaming service SFC, for instance, is an ordered set of VNFs, including the network address translator, firewall, traffic monitor, video optimization controller, and intrusion detection prevention system [START_REF] Huin | Energy-efficient service function chain provisioning[END_REF]. Therefore, disaster protection becomes more challenging with two problems, i.e. VNF placement and SFC mapping, which are classified as N P-hard [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF]. The main considerations are summarized as follows.

• VNF placement and SFC mapping with anycast technology: For each request, several DCs are assigned with the required SFC and corresponding VNFs. Thus, each type of VNF and its replicas are distributed in several DCs to keep the SFC provisioning. It should be implemented to better reduce the power consumption of the hosted physical machines at each DC and the data transmission of EONs, as well as keeping the disaster resilience.

• Modulation format adaptation: For each end-to-end path, the traffic may be processed by the VNFs at the meddle nodes, where extra BVTs are equipped to receive and transmit the optical signals. Thus, the path can be regarded as several lightpaths, and each of them is assigned with a modulation format based on the length of the lightpath. This problem is even more complicated than the aforementioned modulation format assignment problem.

• DZ-disjoint path generation: We consider 1 : 1 backup path protection, where a primary path and a backup path should be generated as DZ-disjoint. In addition, each end-to-end path should be configured with the corresponding SFC and VNFs, and its lightpaths should be assigned with modulation formats.

Optimization methodology and large-scale optimization tools of network protection

The network protection problem involves a bunch of sub-problems. Alone the RMSA has been stated as an N P-hard problem. For such a complex joint problem, the ILP model is the most widely adopted optimization methodology to formulate the network protection schemes. However, the ILP model for the aforementioned network protection schemes is with extremely high computational complexity, due to the complicated joint problem that we are facing. Thus, an efficient design of the ILP model is another challenging and essential task.

The ILP model can provide the joint optimization for the given problem, yet it lacks scalability for the realistic scenario, which is usually with large-scale instances. Thus, the heuristic algorithm is an alternative with high efficiency to deal with realistic scenarios. Meanwhile, the main drawback is that the optimality of obtained solutions is not guaranteed. To this end, a large-scale optimization tool for the studied problem needs to be explored to decompose the huge ILP model.

Conclusion

In this chapter, we introduce the survivability issue in optical networks. We describe the classic network protection methods, covering single link failure protection, disaster protection, p-cycle protection, and path protection. At last, we point out the main challenges of EO-DCNs.

Introduction

Internet traffic around the world is growing rapidly. The number of total Internet users will rise from 3.9 billion (half of the global population) in 2018 to 5.3 billion (two-thirds of the global population) by 2023, while annual IP traffic is predicted to reach 4.8 ZB by 2022 with a compound annual growth rate of 26% since 2017 [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. For such huge traffic demands, the elastic optical networks (EONs) have shown the ability to solve the problem of traffic provisioning with huge volume [START_REF] Gong | Efficient resource allocation for all-optical multicasting over spectrum-sliced elastic optical networks[END_REF][START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF][START_REF] Wang | A survey on data center networking for cloud computing[END_REF][START_REF] Zhu | Dynamic service provisioning in elastic optical networks with hybrid single-/multi-path routing[END_REF]. However, the multitudes of Internet services are facing critical threats from network failures, e.g. fiber cut, due to natural disasters. Such a network failure can cause an average loss of 402,542 dollars in the USA, and 212,254 dollars in UK [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. Naturally, network resilience is regarded as the most significant factor for a majority of the business continuance professionals [START_REF] Cisco | 2021 global networking trends report: Business resilience special edition[END_REF]. To this end, the network protection provided by pre-configured-cycles (p-cycles) has been proved as a spectrum-efficient, switching-fast, and energy-saving strategy with the ring-like structure [START_REF] Asthana | p-cycles: An overview[END_REF][START_REF] Grover | Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration[END_REF][START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF]. A p-cycle can protect both its on-cycle and straddling spans. These features have enabled the p-cycle strategy as one of the most promising network protections.

As it is noticed, among all the business traffic, 82% are Internet video [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. Benefiting from the inherent flexible spectrum usage and low latency of EONs, the DCs can be interconnected through EONs to facilitate the huge data exchanges and migrations, which form the so-called elastic optical inter-data center networks (EO-DCNs) [START_REF] Lu | Highly efficient data migration and backup for big data applications in elastic optical inter-data-center networks[END_REF][START_REF] Wang | A survey on data center networking for cloud computing[END_REF]. With other content delivery and cloud computing services, such traffic shows an asymmetric feature to the current and future inter-data center networks. Meanwhile, the huge traffic demands require enormous electricity support, in which the energy consumption of the information and communication industry is predicted to rise as 8,263 TWh by 2030, occupying 20% of global electricity [START_REF] Andrae | New perspectives on internet electricity use in 2030[END_REF]. The directed p-cycle protection has been demonstrated to better protect the asymmetric traffic against single link failure with less energy cost, compared to the undirected p-cycle [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Rocha | Directed vs. undirected p-cycles and FIPP p-cycles[END_REF].

The up-to-date directed p-cycle design is formulated by a mixed integer linear program (MILP) without candidate cycle enumeration, in which the design of the modulation format selection can be further improved. The modulation format selection of p-cycle lacks the means to determine the protection path of the straddling links. Thus, the modulation format assignment in the conventional directed p-cycle design roughly relies on a relaxed upper bound, consequently leading to a waste of network resources in the solution.

From these perspectives, we propose three novel directed p-cycle design with a novel and compact modulation format adaptation in EO-DCNs, aiming to protect against single link failure with lower power consumption and less spare capacity usage. They are then formulated via three integer linear program (ILP) models by flow conservation without candidate cycle enumeration. The ILP models differ from each other on how the flows can construct the directed p-cycles, namely individual link flow (ILF) directed p-cycle, aggregated link flows (ALF) directed p-cycle, and loop-eliminating flow (LEF) directed p-cycle, respectively. A novel and compact modulation format adaptation strategy is also proposed and formulated relying on accurate protection path lengths, which are determined via different flow designs. To the best of our knowledge, it is the first time that the directed p-cycle designs with compact modulation format adaptation are proposed, as well as three different ILP formulations.

In addition, the performance of the conventional heuristics of the directed p-cycle protection is not guaranteed, although they can deal with large-scale instances with high efficiency. The conventional heuristics lack the efficient means and optimality analysis to decompose a large number of feasible solution candidates, of which the different protections with directed p-cycle combinations can rise more than 10 million [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF]. Next, we leverage the large-scale optimization tools, i.e. column generation (CG) techniques, to deal with the scenarios with large-scale instances. To this end, two CG approaches were proposed. The ILP-based CG (ILP-CG) provides a guaranteed performance based on a solid lower bound and the introduced ϵ-accuracy with a few hundreds of instances. The heuristic-decomposition-algorithm-based CG (De-CG) can provide a near-exact solution with much larger scale traffic on very high efficiency.

The main contributions of this chapter are summarized as follows.

• We propose three novel directed p-cycle design leveraging ILF, ALF, and LEF without candidate cycle enumeration via three ILP models. They protect asymmetric traffic in EO-DCNs against single link failure with joint minimization of power consumption and spare capacity usage. A novel and compact modulation format adaptation for directed p-cycles is designed and formulated via three proposed designs leveraging flow conservation and accurate protection path length.

The studied problem involves directed p-cycle generation, modulation format adaptation, power consumption minimization, and spectrum allocation.

• Based on the proposed ILP models, we then propose the ILP-CG approach to decompose the large ILP model. Through our primary work in [START_REF] Liu | On flow-based directed p-cycle design in elastic optical networks[END_REF], the LEF ILP design is observed as the most efficient one among the proposed directed p-cycle designs. Thus, the ILP-CG approach generates implicitly all promising directed p-cycles with LEF ILP model, i.e. columns in the CG techniques. Then, ILP-CG solves the final and simple ILP based on the generated columns. The performance of the ILP-CG is guaranteed by a proven ϵ-optimality.

• Next, we propose a further CG approach, namely De-CG, aiming to solve the problem with the large-scale instances. Different from the ILP-CG, the De-CG method is developed with a heuristic in order to enumerate all possible directed p-cycles. The most promising ones are selected by the pricing problem in the CG techniques (the CG techniques can be referred to [START_REF] Chvatal | Linear Programming[END_REF]), which is also solved by a fast heuristic decomposition algorithm. The De-CG can provide a comparable solution with very high computational efficiency.

• We compare the proposed directed p-cycle designs with the traditional schemes.

The simulation results show a significant improvement in the performances. The CG approaches also show their superiority on very high efficiency with a nearexact solution for large-scale scenarios.

The rest of the chapter is organized as follows. Section 3.2 provides the related works. Section 3.3 proposes the novel directed p-cycle design. Section 3.4 formulates three joint ILP models for the proposed method. In Section 3.5, two CG approaches are then proposed. Their performances are evaluated in Section 3.6. Section 3.7 concludes this work.

Related Work

The strategy of p-cycle was first proposed in [START_REF] Grover | Cycle-oriented distributed preconfiguration: ring-like speed with mesh-like capacity for self-planning network restoration[END_REF]. Then, thanks to its high spectrum utilization efficiency and fast recovery time, the p-cycle has attracted various researchers to explore network survivability. Literature [START_REF] Eshoul | Survivability approaches using p-cycles in wdm mesh networks under static traffic[END_REF] proposed two approaches to provide resources optimization for both working paths and p-cycles in wavelength division multiplexing (WDM) networks. Literature [START_REF] Huang | Distributed protocol for removal of loop backs with asymmetric digraph using gmpls in p-cycle based optical networks[END_REF] solved the resource inefficiency issue for long restored paths in p-cycle. Literature [START_REF] Xiao | Joint design on dcn placement and survivable cloud service provision over all-optical mesh networks[END_REF] explored the p-cycle in data center network. The data center placement, service routing, and protection were solved by ILP and a two-step heuristic to minimize the network cost. Then, the p-cycle was brought into EONs in [START_REF] Ji | Dynamic p-cycle protection in spectrum-sliced elastic optical networks[END_REF]. The authors explored dynamic p-cycle to achieve lower blocking probability. Literature [START_REF] Ju | Leveraging spectrum sharing and defragmentation to p -cycle design in elastic optical networks[END_REF] gave two spectrum efficient p-cycles, based on spectrum-shared and spectrum-dedicated strategy. In [START_REF] Zou | Link-protection and fipp p-cycle designs in translucent elastic optical networks[END_REF], the p-cycles for both link protection and failure-independent path protection were investigated in translucent EON. The p-cycle with MLR consideration was first explored in [START_REF] Drid | P-cycle design for mixed-line rate optical networks[END_REF]. In [START_REF] Asthana | Distributed protocol for removal of loop backs and optimum allocation of p-cycles to minimize the restored path lengths[END_REF], the cyclecircumferences-limited constraints were brought into the p-cycle design, which limits the maximum hops of the protection path.

The above p-cycle designs are based on a two-step approach. First, enumerate a part of or all the p-cycles as the candidates. Then, select the p-cycles via ILP or MILP. However, such a candidate cycle enumeration causes a too large feasible solution set for ILP and MILP, which shows a very limited scalability [START_REF] Wu | ILP formulations for p-cycle design without candidate cycle enumeration[END_REF]. To this end, the p-cycle ILP formulation without candidate cycle enumeration was first proposed in [START_REF] Schupke | An ILP for optimal p-cycle selection without cycle enumeration[END_REF], in which the p-cycles are generated adaptively to protect the links. Then, three different p-cycle constructions, formulated by two ILPs and an MILP respectively, were investigated without candidate cycle enumeration in WDM networks [START_REF] Wu | ILP formulations for p-cycle design without candidate cycle enumeration[END_REF]. The results showed the most efficient p-cycle design is based on cycle exclusion, which is constructed with the help of root node and node voltage for MILP. Then, literature [START_REF] Ju | Distance-adaptive, low capex cost p -cycle design without candidate cycle enumeration in mixed-line-rate optical networks[END_REF] extends the voltagebased p-cycle design as the path-length-limited p-cycle in WDM networks, which aims to achieve maximized power saving. Rather than the limitation of hops in [START_REF] Asthana | Distributed protocol for removal of loop backs and optimum allocation of p-cycles to minimize the restored path lengths[END_REF], the p-cycle was also assigned with the corresponding modulation format considering the protection path length and transmission reach of the modulation format.

As for the directed p-cycles, literature [START_REF] Rocha | Directed vs. undirected p-cycles and FIPP p-cycles[END_REF] first investigated the directed p-cycle design, which exhibits an improvement up to 45% over undirected p-cycles with the scenarios of pure asymmetric traffic. With a similar p-cycle construction method in [START_REF] Ju | Distance-adaptive, low capex cost p -cycle design without candidate cycle enumeration in mixed-line-rate optical networks[END_REF][START_REF] Wu | ILP formulations for p-cycle design without candidate cycle enumeration[END_REF], literature [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF] proposed the distance adaptive directed p-cycle design with modulation format assignment in EO-DCNs.

To decompose the complex ILP, the CG approach was then proved as an efficient and scalable tool to generate p-cycles without candidate cycle enumeration [START_REF] Sebbah | Design of survivable WDM networks using preconfigured protection structures with unrestricted shapes[END_REF]. Literature [START_REF] Metnani | Stability of fipp p-cycles under dynamic traffic in wdm networks[END_REF] employed the CG to investigate the stability of failure-independent path-protecting (FIPP) -cycles under dynamic traffic. The p-cycle design leveraging the CG approach was also extended in [START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF][START_REF] Kiaei | Efficient network protection design models using pre-cross-connected trails[END_REF][START_REF] Sebbah | An efficient column generation design method of p-cycle-based protected working capacity envelope[END_REF].

To the best of our knowledge, the work in [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF] is the up-to-date directed p-cycle design without candidate cycle enumeration in EO-DCNs. Yet, the modulation format selection for the conventional directed p-cycle is based on a brief upper bound rather than the exact length of each protection path. The reason is that the conventional directed p-cycle designs lack the means to determine the protection path of the straddling link, especially for the conventional voltage-based p-cycle models. They will, therefore, consume an increased amount of resources on unexpected links. With respect to all these researches, our work has a significant difference in directed p-cycle construction, modulation format adaptation, and scalable mathematical models. Focusing on the directed p-cycle design without candidate cycle enumeration in EO-DCNs, we construct directed p-cycle via three different constructions, and the compact modulation format adaptation is also enabled. The straddling links are then added into consideration of the modulation format adaptation. Thus, the spectral efficiency of spare capacity can be further improved. Furthermore, we leverage the CG techniques to solve the joint problem with high efficiency, of which the performances are guaranteed to reach a near-optimal solution for the LEF directed p-cycle with proven accuracy. Two different CG approaches are developed focusing on optimality and computational efficiency, respectively.

Problem Statement: Directed p-Cycles with Compact modulation format Adaptation

A digraph G(V, A) is used in this chapter to model the network, where V denotes the set of nodes, and A represents the set of directed links. The link set A also contains the set A ϕ of traffic-loaded links, which need to be protected. Note that we use desired link referring to the traffic-loaded links that need to be protected by the directed pcycle in the rest of this chapter, and each frequency slot (FS) in EO-DCNs is with 12.5 GHz in this work. No guard band is configured between the directed p-cycles in this work for simplicity. The EO-DCNs are assumed as translucent in this work, where only transponders are deployed at each ending node of the protection paths.

To show the advantage of directed p-cycle in asymmetric traffic, an instance is shown in Fig. 3.1 with a 6-node network with 3 traffic-loaded links, i.e. the links (1, 2), [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF] and a straddling link (6, 2), loaded with traffic of 80, 100, and 80, in Gbps, respectively. Note that the links (1, 2) and [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF] are the opposite on-cycle links (OCLs) for directed p-cycle. Two p-cycles are both generated with the same loop, as shown in Fig. 3.1 (a). For directed p-cycle, the protection paths are generated with 1-6-5-3-2, 3-2-1-6-5, and 6-5-3-2, respectively, as shown in Fig. 3.1 (b). With the modulation format consideration (detailed in the following Modulation format adaptation, the spare capacity usage needed on each directed link for three paths are both 3 FSs at the modulation format of 8-QAM. For undirected p-cycle, the difference lies in the protection path for straddling link [START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF][START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF], where the the spare capacity usage can be equally divided on two path, i.e. 6-5-3-2 and 6-1-2, as shown in Fig. 3.1 (c). Thus, to protect link (6, 2), the needed FSs for these two paths are 1 and 2, respectively. However, the undirected p-cycle still assigns 3 FSs for each on-cycle link. Furthermore, as undirected p-cycle assign FSs on both directions, it cost extra power consumption and spectrum on links (1, 2), (2, 3), [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF], [START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF][START_REF] Adachi | The restoration of telecom power damages by the great east japan earthquake[END_REF], and (6, 1). The overall performance of power consumption and spare capacity usage is summarized in Table 3.1. Note that the FS usage refers to spare capacity usage of directed p-cycles. The main considerations of each sub-problem can be summarized as follows.

1) Directed p-cycle generation

The conventional p-cycle design leverages voltage and root node (VRN) [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Wu | ILP formulations for p-cycle design without candidate cycle enumeration[END_REF], as shown in Fig. 3.2 (a), constructing the directed p-cycles by the ascending voltages. The VRN also needs a root node to distinguish different directed p-cycles. Thus, the VRN can only determine the paths between any two adjacent on-cycle nodes, and the protection path length of the straddling span is estimated with a rough upper bound, which is described in 2) Modulation format adaptation. It results in a bigger upper bound for the lengths of protection paths to be obtained, and then lower-order modulation formats are assigned for the generated directed p-cycles. Consequently, higher power consumption and spectrum usage are introduced in the solution.

To overcome the drawbacks of the conventional method, in this work, we provide three flow-based ILP formulations for the directed p-cycle designs, where flows are constructed as follows.

• Each flow starts from each on-cycle node (except root node) respectively and ends at the root node for each directed p-cycle, as shown in Fig. 3.2 (b). The directed pcycles are constructed by determining each flow. Thus, we call it the ILF directed p-cycle in this work.

• The aggregated flows start from the root node, and then decrease by one when crossing each on-cycle node other than the root itself, as shown in Fig. 3.2 (c). Note that each flow of the aggregated flows can be regarded as the same as the one in the ILF directed p-cycle except for the flow direction. However, the construction of directed p-cycles is different, which is achieved by determining the number of flows on each link. We then name it the ALF directed p-cycle in this work.

• For each on-cycle node pair, a flow is generated from one node and ends at the other node. Thus, the flows exist in all ordered pairs of nodes, as shown in Fig. 3.2 (d). Different from the above directed p-cycle constructions, such a method does not need the help of the root node to construct a loop. We then name it the LEF directed p-cycle in this work.

Note that we use VRN when referring to the conventional directed p-cycle, since it is the up-to-date directed p-cycle design.

2) Modulation format adaptation

Considering the physical layer impairments in EO-DCNs, the optical signal is degraded along a lightpath, where the received signal-to-noise ratio (SNR) decreases as the transmission distance increases. Thus, we restrict the transmission reach for each modulation format to guarantee that the received SNR can maintain the acceptable level. We consider four modulation formats, i.e. 16-QAM, 8-QAM, QPSK, and BPSK, whose transmission reaches are 1, 200, 2, 400, 4, 800, and 9, 600, in km, respectively [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF]. The available transmission rates per FS (12.5 GHz) for them are 12.5, 25, 37.5, and 50, in Gbps, respectively [START_REF] Chen | On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks[END_REF]. For each directed p-cycle, its maximum protection path length should not exceed the corresponding transmission reach of the assigned modulation format.

Furthermore, the consideration of the proposed modulation format adaptation is achieved based on the protection path length of each desired link. As the proposed modulation format adaptation is the same for the proposed directed p-cycle, we use LEF to refer the proposed directed p-cycle design in this case. As shown in Fig. 3.3 (a), we assume the LEF and VRN use the same directed p-cycle to protect link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF] and link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF] in this case. The difference between the proposed LEF and conventional VRN lies in the protection path of the straddling link, i.e. link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF]. As shown in Fig. 3.3 (b), the conventional directed p-cycle designs employ a longer protection path to estimate the protection path of the straddling link [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Ju | Distance-adaptive, low capex cost p -cycle design without candidate cycle enumeration in mixed-line-rate optical networks[END_REF]. The VRN needs protection path 3-2-1-4 for the desired link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF], where path 2-1-4 is the compact solution to protect link [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF] in the LEF. Because the conventional directed p-cycle designs lack the means to determine the protection path of the straddling span, especially for the conventional MILP models. It results in a more relaxed upper bound for the lengths of protection paths and a lower-order modulation format to be obtained. Therefore, VRN will consume an increased amount of power, e.g. in this case, 3, 416.27 W is wasted.

3) Power consumption

The power consumption in EO-DCNs is mainly due to bandwidth-variable transponders (BVTs), bandwidth variable optical cross-connects (OXCs), and optical amplifiers (OAs) [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Vizcaíno | Protection in optical transport networks with fixed and flexible grid: Cost and energy efficiency evaluation[END_REF]. In this work, we assume two BVTs are deployed at two ending nodes of each protection path on each directed p-cycle in EO-DCNs. The power consumption of BVT is related to transmission rate in terms of modulation format, which are 112.374, 133.416, 154.457, and 175.498, in W per FS, for 16-QAM, 8-QAM, QPSK, and BPSK, respectively [START_REF] Vizcaíno | Protection in optical transport networks with fixed and flexible grid: Cost and energy efficiency evaluation[END_REF]. The power model of BVT e BVT m at modulation format m is expressed as follows:

e BVT m = 1.683 • R + 91.333 (3.1)
where R is the transmission rate per FS in Gbps.

The OXCs are deployed at each on-cycle node, in which the power consumption depends on the nodal degree and the add/drop degree β. The β is assumed as 9 in this work. Hence, on the ends of link (v, u), the BVT power model e OXC v can be expressed as follows:

e OXC v = 85 • |N v | + 100 • β + 150 (3.2)
The erbium-doped fiber amplifiers (EDFAs) are deployed as OAs on the span every 80 km. Each EDFA consumes 100 W for each directed link [START_REF] Vizcaíno | Protection in optical transport networks with fixed and flexible grid: Cost and energy efficiency evaluation[END_REF]. The power model of EDFA e EDFA a can be expressed as:

e EDFA a = ⌊ d a 80 + 1⌋ • 100 (3.3)

4) Spectrum allocation

The directed p-cycles need to protect the links with two conditions: 1) two ending nodes are the on-cycle nodes; 2) the link is not an on-cycle link. A sufficient spectrum should be assigned to protect the traffic on the desired links. For each directed p-cycle, the spectrum is allocated under the following principles. a) Spectrum continuity: For each directed p-cycle, all on-cycle links are assigned with the same FSs. b) Spectrum contiguity: The FSs assigned for each directed p-cycle should be continuous slots. c) Spectrum conflict: Each FS on each link can only be assigned once for the directed pcycles. No overlapping is allowed in this work.

ILP formulation

In this section, we formulate three ILP models for directed p-cycles leveraging different flow-based constructions. For the sake of readability, we use ∀i, ∀v, ∀u, ∀a, ∀m, and ∀s to denote ∀i ∈ I, ∀v ∈ V, ∀u ∈ V, ∀a ∈ A, ∀m ∈ M, and ∀s ∈ S, respectively. We also use ∀(v, u), ∀v ̸ = u, ∀v > u, and ∀i ̸ = i ′ to denote ∀(v, u) ∈ A, ∀v, u ∈ V, v ̸ = u, ∀v, u ∈ V, v > u, and ∀i, i ′ ∈ I, i ̸ = i ′ , respectively. Throughout this chapter, the ILPs have the same objective function for a fair comparison.

The network sets and parameters are presented as follows.

• G(V, A): Network with node set V, and link set A. |V| is the number of the nodes for the networks.

• N v : Set of adjacent nodes of node v.

• i ∈ I: The directed p-cycle set with maximum number |I| allowed, i indicates i-th directed p-cycle in I.

• A ϕ ⊆ A: Set of traffic-carrying links.

• ϕ a : The traffic on link a, denoted by the number of FSs as an integer, when using the BPSK.

• S: Set of reserved FSs for directed p-cycle on each link. |S| denotes the number of reserved FSs. The available bandwidth for an FS is 12.5 GHz in this work.

• d a : The distance of link a in km.

• m ∈ M: The modulation format level set, i.e. 16-QAM, 8-QAM, QPSK, and BPSK.

• h m : Maximum transmission reach at modulation level m, which is 1, 200, 2, 400, 4, 800, and 9, 600, in km for 16-QAM, 8-QAM, QPSK, and BPSK, respectively [START_REF] Chen | On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks[END_REF]. h max = 9, 600 km.

• d ˜: The maximum length of the path that can be generated in network G(V, A).

• T m : The spectrum efficiency. The available transmission rate per FS for BPSK, QPSK, 8-QAM, and 16-QAM is 12.5, 25, 37.5, and 50, in Gbps, respectively. Thus, T m for them is 1, 2, 3, and 4, respectively.

• e BVT m : The power consumption of BVT at modulation format m.

• e OXC a : The power consumption of OXC on ending nodes of link a.

• e EDFA a : The power consumption of EDFA on link a.

The variables for all the ILP models are presented as follows.

• l i vu ∈ {0, 1}: Equals 1 if link (v, u) is an on-cycle link in i, and 0 otherwise.

• y i v ∈ {0, 1}: Equals 1 if node v is an on-cycle node of directed p-cycle i, and 0 otherwise.

• c i v ∈ {0, 1}: Equals 1 if node v is the root node of directed p-cycle i, and 0 otherwise.

• t i vu ∈ {0, 1}: Equals 1 if both node v and node u are the on-cycle nodes of directed p-cycle i, and 0 otherwise.

• q i vu ∈ {0, 1}: Equals 1 if the link (v, u) desires to be protected by directed p-cycle i, and 0 otherwise.

• f iv wu ∈ {0, 1}: Used only for ILF. Equals 1 if the link (w, u) carries a flow generated from node v in directed p-cycle i, and 0 otherwise.

• f i a ∈ [0, |V|]: Used only for ALF. The number of the flows on the link a in directed p-cycle i.

• p i v ∈ [0, |V|]:
Used only for ALF. Equals the number of on-cycle nodes of i if the node v is the root node of directed p-cycle i, and 0 otherwise.

• f i,uv u ′ v ′ ∈ {0, 1}:
Used only for LEF. Equals 1 if the link (u ′ , v ′ ) carries a flow generated from node v and terminated at node u in directed p-cycle i, and 0 otherwise.

• b i m ∈ {0, 1}: Equals 1 if the directed p-cycle i operates at modulation format m, and 0 otherwise.

• z i a ∈ [-d ˜, d ˜]: The protection path length of link a on directed p-cycle i if z i a is positive. Otherwise, (z i a + ∑ a∈A d a • l i a )
is the protection path length of link a on directed p-cycle i if z i a is negative.

• u i a ∈ {0, 1}: Equals 1 if the variable z i a is positive, and 0 otherwise.

• j i a ∈ [0, d ˜]: Used to eliminate the non-linearity in constraints (3.20), and (z i a + j i a ) is the protection path length of link a on directed p-cycle i.

• π im a ∈ [0, |S|]: The number of FSs assigned for directed p-cycle i at modulation format m to protect link a.

• Φ i a ∈ [0, |S|]:
The number of FSs assigned on link a for directed p-cycle i.

• Φ i ∈ [0, |S|]:
The number of FSs assigned for directed p-cycle i.

• k iv a ∈ {0, 1}: Used only for ALF. Equals 1 if the on-cycle link a is in front of oncycle node v in directed p-cycle i, and 0 otherwise. Note that the root node is the beginning node.

• E: The total power consumption for all the directed p-cycles.

• s i a ∈ [0, |S| -1]: The starting FS index in directed p-cycle i on link a.

• x is a ∈ {0, 1}: Equals 1 if the FS index s is assigned for directed p-cycle i on link a.

• E i : The total power consumption for the directed p-cycle i.

Directed p-cycle design leveraging ILF

In this section, we formulate the directed p-cycle ILP model leveraging individual link flows, namely ILF. In ILF, the individual link flow starts from each on-cycle node (except root node) and ends at the root node for each directed p-cycle. The directed p-cycle is then constructed by determining each flow. We use f iv wu to denote whether the flow that ends at node v exists on link (w, u).

min θ 1 • ∑ i∈I ∑ a∈A Φ i a + θ 2 • ∑ i∈I E i ILF-ILP (3.4) s.t. Constraints (3.6)-(3.40).
The objective function aims to jointly minimize the weighted sum of total spare capacity usage and power consumption for all the directed p-cycles. θ 1 and θ 2 are adjustable weights. The first term represents the total FS usage of all the directed p-cycles, denoted by the number of FSs. The second term is the total power consumption E i for directed p-cycle i with the unit of Watt, expressed by

E i = ∑ a∈A ϕ ∑ m∈M 2 • e BVT m • π im a + ∑ a∈A e EDFA a • Φ i a |S| + ∑ v∈V ∑ u∈N v e OXC v • Φ i vu |S| (3.5)
where the first term represents the power consumption for BVT on two ending nodes of the desired links, the second term calculates the power consumption for EDFA on each on-cycle link, and the last term denotes the power consumption for OXC for each on-cycle node [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF].

1) Cycle generation constraints

l i vu + l i uv ≤ 1, ∀i, ∀v > u (3.6) ∑ u∈N v l i vu -∑ u∈N v l i uv = 0, ∀i, ∀v (3.7)
y i v = ∑ u∈N v l i vu , ∀i, ∀v (3.8)
c i v ≤ y i v , ∀i, ∀v (3.9)
∑ v∈V c i v ≤ 1, ∀i (3
f iv wu ≤ l i wu + y i v 2 , ∀i, ∀v, ∀(w, u) (3.11) ∑ u∈N v f iv vu -∑ u∈N v f iv uv ≤ y i v -c i v + 1 2 , ∀i, ∀v (3.12)
∑ u∈N v f iv vu -∑ u∈N v f iv uv ≥ y i v -c i v , ∀i, ∀v (3.13)
∑

u∈N w f iv uw -∑ u∈N w f iv wu ≤ y i v + c i w 2 , ∀i, ∀v ̸ = w (3.14) ∑ u∈N w f iv uw -∑ u∈N w f iv wu ≥ y i v + c i w -1, ∀i, ∀v ̸ = w (3.15)
Constraints (3.11)-(3.15) construct the directed p-cycle using flow with closed-loop. Specifically, constraints (3.11) prohibit the existence of the flow on the out-of-cycle links or the flow to a node not on cycle. Constraints (3.12) and (3.13) indicate that a node v will generate a unit of flow to the root node, if it is not a root node. Constraints (3.14) and (3.15) indicate that if the node w is the root node and w ̸ = v, then it will consume a flow from v.

3) Modulation adaptation constraints

z i vu = ∑ a∈A d a • f iv a -∑ a∈A d a • f iu a , ∀(v, u) ∈ A ϕ , ∀i (3.16
)

u i a • d ˜-z i a ≥ 0, ∀a ∈ A ϕ , ∀i (3.17)
(1

-u i a ) • d ˜+ z i a ≥ 0, ∀a ∈ A ϕ , ∀i (3.18)
∑ m∈M b i m ≤ 1, ∀i (3.19)
Constraints (3.16) calculate the path length of the traffic-loaded link (v, u) from node v to node u on each directed p-cycle, which is determined by individual flows. Note that the z i vu is protection path length if the z i vu is positive, otherwise the protection path length is composed by the rest of the links on directed p-cycle i, i.e. (z i a + ∑ a∈A d a • l i a ).

To distinguish the two above situations, constraints (3.17 ) ensure that only one modulation format can be assigned for each directed p-cycle.

z i a + (1 -u i a ) • ∑ a ′ ∈A d a ′ • l i a ′ ≤ ∑ m∈M b i m • h m + (1 -q i a ) • d ˜, ∀a ∈ A ϕ , ∀i (3.20)
Constraints (3.20) guarantee modulation format adaptation with maximum transmission reach for the links that desire to be protected by directed p-cycle i. To ensure linearity, constraints (3.20) are then substituted by constraints (3.21)- (3.24).

z i a + j i a ≤ ∑ m∈M b i m • h m + (1 -q i a ) • d ˜, ∀a ∈ A ϕ , ∀i (3.21)
j i a ≤ (1 -u i a ) • (d ˜+ d a ), ∀a ∈ A ϕ , ∀i (3.22)
j i a ≤ ∑ a ′ ∈A d a ′ • l i a ′ , ∀a ∈ A ϕ , ∀i (3.23)
j i a ≥ ∑ a ′ ∈A d a ′ • l i a ′ -u i a • (d ˜+ d a ), ∀a ∈ A ϕ , ∀i (3.24)
4) Protection capacity constraints

q i vu ≤ y i v + y i u 2 , ∀i, ∀(v, u) ∈ A ϕ (3.25) q i a + l i a ≤ 1, ∀i, ∀a ∈ A ϕ (3.26) ∑ m∈M π im a ≤ Φ i , ∀i, ∀a ∈ A ϕ (3.27) Φ i a ≥ Φ i + (l i a -1) • |S|, ∀i, ∀a ∈ A ϕ (3.28) Φ i a ≤ Φ i , ∀i, ∀a ∈ A ϕ (3.29) Φ i a ≤ l i a • |S|, ∀i, ∀a ∈ A ϕ (3.30) π im a ≤ ϕ a • q i a , ∀i, ∀m, ∀a ∈ A ϕ (3.31) π im a ≤ ϕ a • b i m , ∀i, ∀m, ∀a ∈ A ϕ (3.32) ∑ i∈I ∑ m∈M π im a • T m ≥ ϕ a , ∀a ∈ A ϕ ( 3

5) Spectrum allocation constraints

Φ i ≥ Φ i a , ∀i, ∀a (3.34)
Φ i a ≥ Φ i + (l i a -1) • |S|, ∀i, ∀a (3.35)
Constraints (3.34)- (3.35) imply that the number of assigned FSs for each on-cycle link are the same for the directed p-cycle i.

∑ s∈S x is a = Φ i a , ∀i, ∀a (3.36) s • x is a ≥ s i a , ∀i, ∀a, ∀s (3.37) s • x is a ≤ s i a + Φ i a , ∀i, ∀a, ∀s (3.38)
Constraints (3.36) indicate each assigned FS for each on-cycle link for each directed p-cycle. Also, the assigned FSs should be continuous according to the principle of Spectrum Continuity. Specifically, constraints (3.37) assign the starting FS index and constraints (3.38) assign the ending FS index for the directed p-cycle i.

s i a + Φ i a ≤ l i a • |S|, ∀i, ∀a, ∀s (3.39) ∑ i∈I x is a ≤ 1, ∀a, ∀s (3.40)
Constraints (3.39) prohibit the FS assignment on out-of-cycle links and ensure the assigned FSs are no more than the reserved FSs. Constraints (3.40) guarantee no FS overlapping exists no according to the principle of Spectrum Conflict. We treat FS index of spare capacity of the directed p-cycles as independent from the one of the working traffic, i.e. s is from 1 to |S|.

Directed p-cycle design leveraging ALF

In this section, we formulate the directed p-cycle ILP model leveraging aggregated link flows, namely ALF. To facilitate differentiation from ILF, the flows in this model start at the root node and end at each on-cycle node (except the root node itself) in a directed pcycle. The directed p-cycle is then constructed by determining the number of flows on each on-cycle link for each directed p-cycle. We denote f i a as the number of aggregated flows on link a. The ALF directed p-cycle ILP can be formulated as follows.

min The objective is the same as ILF. To keep the models self-contained, we repeat the statement of the objective in the ALF and LEF models.

θ 1 • ∑ i∈I ∑ a∈A Φ i a + θ 2 • ∑ i∈I E i ALF-
The differences between the models of ALF directed p-cycle and ILF directed p-cycle lie in Flow conservation constraints and Modulation format adaptation constraints. The added constraints are shown as follows.

f i a ≤ (|V| -1) • l i a , ∀i, ∀a (3.41)
p i v ≤ ∑ u∈V y i u , ∀i, ∀v (3.42)
p i v ≤ |V| • c i v , ∀i, ∀v (3.43)
p i v ≥ ∑ u∈V y i u + |V| • (c i v -1), ∀i, ∀v (3.44) ∑ u∈N v f i uv -∑ u∈N v f i vu = y i v -p i v , ∀i, ∀v (3

|V| • (k

iv a + 1 -y i v ) ≥ f i a -∑ u∈N v f i vu , ∀i, ∀v, ∀a (3.46) |V| • (k iv a -1) ≤ f i a -∑ u∈N v f i vu -1, ∀i, ∀v, ∀a (3.47)
k iv a ≤ l i a + y i v 2 , ∀i, ∀v, ∀a (3.48
z i vu = ∑ a∈A d a • k iu a -∑ a∈A d a • k iv a , ∀(v, u) ∈ A ϕ , ∀i (3.49)
Similarly to constraints (3.16), constraints (3.49) calculate the values of the variables z i vu from the ending node u to beginning node v of the link (v, u) on directed p-cycle i by cycle direction.

Directed p-cycle design leveraging LEF

In this section, we formulate the directed p-cycle ILP model leveraging loop-eliminating flows, namely LEF. The flows exist on all ordered pairs of nodes, where each flow starts from one on-cycle node and ends at the other on-cycle node. We use variables f i,uv a to denote whether the link a exists the ordered flow that starts from node u and ends at node v. Such that the root node for the directed p-cycle generation is not necessary. The LEF directed p-cycle can be formulated by the following ILP. The Flow conservation constraints and Modulation format adaptation constraints for LEF are also different from the aforementioned directed p-cycle models, and it needs no root node as well. The added constraints are shown as follows.

min θ 1 • ∑ i∈I ∑ a∈A Φ i a + θ 2 • ∑ i∈I E i LEF-ILP s.t. Constraints (
t i vu ≥ y i v + y i u -1, ∀i, ∀v > u (3.50) t i vu ≤ y i v + y i u 2 , ∀i, ∀v > u (3.51) t i vu = t i uv , ∀i, ∀v > u (3.52) f i,vu a ≤ l i a + t i vu 2 , ∀i, ∀(v, u), ∀a (3.53
∑ u ′ ∈N v ′ f i,uv u ′ v ′ -∑ u ′ ∈N v ′ f i,uv v ′ u ′ = ⎧ ⎪ ⎨ ⎪ ⎩ t i uv , v ′ = u -t i uv , v ′ = v, ∀i, ∀(u, v), ∀v ′ 0, otherwise, (3.54)
Constraints (3.54) construct the directed p-cycle using flow conservation.

∑ v ′ ∈V ∑ u ′ ∈N v ′ d u ′ v ′ • f i,uv u ′ v ′ ≤ ∑ m∈M b i m • h m + h max • (1 -q i uv ), ∀i, ∀(u, v) (3.55)
Constraints (3.55) guarantee modulation format adaptation with maximum transmission reach. Different from the ILF and ALF, the LEF is complex in cycle generation by determining the flows between every ordered pair of nodes, but the modulation format adaptation benefits from it.

Computational Complexity

Column Generation

In this section, we propose the column generation method as the optimization tool to deal with the scenarios under large-scale traffic. We first provide a simple and efficient heuristic initial solution to find a feasible solution and enumerate all the directed pcycles. Then, we formulate the master problem and the corresponding pricing problem. The pricing problem is achieved by two different means, i.e. ILP and heuristic. Thus, two CG approaches, namely ILP-CG and De-CG, are proposed focusing on solution optimality and execution efficiency, respectively. At last, a final ILP gives an integer solution for the generated directed p-cycles. Note that the only difference between ILP-CG and De-CG lies in how they construct the pricing problem, i.e. how the columns are generated.

The procedure of column generation for LEF-p-cycle is explained in Fig. 3.4. Specifically, an initial solution is obtained with the initial columns by a heuristic algorithm. It can also give a complete directed p-cycle candidates enumeration for De-CG. The master problem is then relaxed and solved with the initial solutions. The linear relaxation provides the optimal dual variables, which are the inputs of the pricing problem. Next, the pricing problem is executed to find a new promising directed p-cycle at each generation. Here, two different pricing problem corresponds to two different CG approaches. For the ILP-CG, it needs no directed p-cycle candidates enumeration but implicitly generates each directed p-cycle via the ILP model. For the De-CG, we propose the heuristic algorithm to select each column from the directed p-cycle candidate enumeration set. Note that each column corresponds to a directed p-cycle, which will be used interchangeably in this work. The column with negative reduced cost (solved by pricing problem) contributes to minimizing the objective of the linear relaxation of the master problem (LRMP). Thus, it is then added to the LRMP to generate the next column. This LRMP-pricing loop runs iteratively till there is no promising column can be found, where we get a non-negative reduced cost in the pricing problem. By solving the last LRMP of ILP-CG, the lower bound on the optimal integer value is obtained, which gives the accuracy of the optimality to the final solution. Finally, we integerize the LRMP as an ILP to solve the final solution in the master problem.

Initial Solution

The initial solution is essential for the CG method, which is the one feasible solution for the problem, and the input for the master problem. An initial solution with higher quality benefits the CG approach searching in a smaller solution set. For instance, in an extreme case, the initial solution obtained by LEF-p-cycle ILP will lead that no column being generated, as the initial solution is the optimal solution and no more promising directed p-cycle can be found. As the CG itself is an approach to finding a better solution with high efficiency, a time-efficient heuristic would be adequate. Thus, we give a heuristic for the initial solution (IS) with modulation format adaptation as Algorithm 3.1. The modulation format adaptation is based on the length of each protection path for each directed p-cycle. The additional variables are shown as follows.

• I: The set of the directed p-cycle candidate enumeration. Note that each directed p-cycle includes its on-cycle links, desired links, assigned number of FSs, spectrum location on each on-cycle link, and assigned modulation format.

• I * : The set of directed p-cycle generated or selected by the pricing problem. Each directed p-cycle candidate is generated by the initial solution and the pricing problem iteratively.

• C i : The set of the on-cycle links of directed p-cycle i.

• P i : The set of the desired links of directed p-cycle i.

• P k i : The k-th combination set of the desired links of directed p-cycle i. • m i ∈ M: The assigned modulation format for directed p-cycle i. Shown in Algorithm 3.1, line 1 initializes the sets, I, I * , and I temp as empty, where the set I temp is a temporary set. Line 2 enumerates the directed p-cycles using the approach in [START_REF] Doucette | Algorithmic approaches for efficient enumeration of candidate p-cycles and capacitated p-cycle network design[END_REF]. It gives an enumeration of all the cycles allowed in the networks, which only include on-cycle links. We treat an undirected cycle in [START_REF] Doucette | Algorithmic approaches for efficient enumeration of candidate p-cycles and capacitated p-cycle network design[END_REF] as two directed cycles in this work. Then, lines 3-7 indicate the desired links for the directed p-cycle candidate. Note that the directed p-cycle candidate enumeration is not complete here, and different

Algorithm 3.1: IS Algorithm

Input : G(V, A). Output: I, I * . I = ∅, I * = ∅, I temp = ∅; Enumerate the directed p-cycle candidate set I using the approach in [START_REF] Doucette | Algorithmic approaches for efficient enumeration of candidate p-cycles and capacitated p-cycle network design[END_REF]; for i ∈ I do

P i = ∅; for (u, v) ∈ A ϕ do if y i u = 1, y i v = 1, l i uv ̸ = 1 then 7 P i = P i ∪ {(u, v)}; end end end for i ∈ I do for j from 1 to |P i | -1 do
Enumerate all the combinations of j desired links, and construct the set of the desired-link combinations P k i for directed p-cycle i, where

|P k i | = ( |P i | j ) -1; end for k from 1 to |P k i | do
Construct new directed p-cycle i ′ based on C i , and P k i , where Here, we explain the directed p-cycle extension in the De-CG. It aims to provide precise modulation format assignment and power consumption for different protection solutions. A directed p-cycle with different desired links leads to a different maximum length of the protection path. Consequently, it is assigned with different modulation format and power consumption with different desired links. The directed p-cycle i can protect total |P i | traffic-loaded links, but some of them can be protected more effectively by other directed p-cycles. Therefore, the desired links of the directed p-cycle i can be reduced less than |P i |, which leads to a shorter protection path for directed p-cycle i, and consequently a higher-order modulation format and less power consumption can be assigned. An instance is shown in Fig. 3.5, three different configurations can provide enough protection for the desired links but with different spare capacity usage and power consumption. The configuration 1 only uses one directed p-cycle for the protection, yet it may consume more power for longer protection path length. Thus, the configuration 2 and 3 use two directed p-cycles for protection as long as the desired FSs are sufficient. Although the directed p-cycles A and C are with the same on-cycle links, they have different desired links. It probably leads to the different modulation formats for them. As the master problem only determine the directed p-cycles are selected or not, the columns generated in the De-CG should be sufficiently complete to improve optimality. Lines 14-17 then calculate the length of each protection path and assign a just-enough modulation format to the directed p-cycle. Next, line 18 solves a simple ILP model with Eq. (3.56)- (3.57).

I temp = I temp ∪ i ′ , C i ′ = C i
min θ 1 • ∑ i∈I ∑ a∈C i Φ i a + θ 2 • E i (3.56) s.t. ∑ i∈I π im a • T m ≥ ϕ a , ∀a ∈ A ϕ , m = m i (3.57) Φ i a = Φ i , ∀i ∈ I, a ∈ C i (3.58) π im a ≤ Φ i , ∀i ∈ I, a ∈ P i , m = m i (3.59)
Similar to the objective of the LEF-p-cycle ILP model, the objective (3.56) aims to minimize the power consumption and the used number of FSs. Constraints (3.57) guarantee that the efficient FSs are assigned to protect the traffic-loaded links. Constraints (3.58) and (3.59) permit the protection of the desired links with the FSs no more than the assigned FSs for directed p-cycle i. Different from the LEF-p-cycle ILP model, the set I provide on-cycle links C i , desired links P i , assigned modulation format m i of the directed p-cycle i. Thus, the above ILP is of low computational complexity, which only needs to determine the spectrum usage for these directed p-cycles.

The directed p-cycles with assigned FSs are selected into the initial solution in lines 19-21. Those directed p-cycles with 0 FS are not selected to the feasible column set I * . At last, lines 22 allocates FSs based on coloring algorithm, referred to [START_REF] Wu | On the distance spectrum assignment in elastic optical networks[END_REF]. The time

complexity of IS is O(|I| • |A ϕ | • log |I|}).

Master Problem

The additional variables of the CG methods are presented as follows. Others remain the same as aforementioned.

• z i ∈ {0, 1}: Equals 1 if the directed p-cycle i is selected, 0 otherwise. Note that to get the dual variables, z i are then relaxed as z i ∈ [0, 1] in the linear relaxation of the master problem.

We then give the ILP formulation of the master problem, which is a restricted ILP model of the LEF-p-cycle ILP model in Section 3.4, shown as follows.

min θ 1 • ∑ i∈I * ∑ a∈P i Φ i a • z i + θ 2 • ∑ i∈I * E i • z i (3.60) s.t. ∑ i∈I * ∑ m∈M π im a • T m • z i ≥ ϕ a , ∀a ∈ A ϕ (3.61) ∑ i∈I * x is a • z i ≤ 1, ∀a, ∀s (3.62)
Similar to the objective function of LEF-p-cycle ILP in Eq. (3.4), the objective of the master problem is to jointly minimize the weighted sum of the total spectrum usage and power consumption for all the directed p-cycles. The columns in the master problem are the generated directed p-cycles, including all the on-cycle links, the desired links, and the selected modulation format of the directed p-cycle. Note that the only variables are z i in the master problem, others are the obtained values in the feasible columns set I * from the initial solution and pricing problem. We remain the same expression of them in the master problem for readability. Constraints (3.61) ensure the FSs provided by the directed p-cycles are sufficient to protect the corresponding links. Constraints (3.62) guarantee that the FS on each link can be only assigned once. Here, the values of Φ i a , π im a , and x is a are obtained by the initial solution and each generated column. They are not the variables when solving the master problem.

Pricing Problem for ILP-CG

To formulate the pricing problem, we first need to get the values of the dual variables of the current LRMP, the dual variables are shown as follows.

• α a ≥ 0: The dual variables of constraints (3.61).

• β s a ≥ 0: The dual variables of constraints (3.62). Note that to get the dual variables α a , and β s a , the ILP of the master problem needs to be relaxed as LP, i.e. the variables z i are relaxed as

z i ∈ [0, 1].
Then, with optimized duals, the pricing problem for the new column, i.e. i-th directed p-cycle, is min 3.39) assign the spectrum for it. Thus, we can simply set |I| as 1 for these constraints to optimize the pricing problem. We do not rewrite them in this section for simplicity.

θ 1 • ∑ a∈A Φ i a + θ 2 • E i -∑ a∈A ∑ m∈M π im a • T m • α a + ∑ a∈A ∑ s∈S x is a • β s a ( 3
Then, we get a new directed p-cycle and its reduced cost, i.e. optimized objective value of Eq. (3.63). The new directed p-cycle with negative reduced cost is then added to the feasible solution set, i.e. directed p-cycle candidate set I * . Note that such a directed p-cycle should contain the information of its on-cycle links, desired links, used number of FSs, spectrum locations, and assigned modulation format. The ILP-CG then solves the LRMP with the updated I * . The above steps run iteratively till we get a nonnegative reduced cost, where no more promising directed p-cycle can be generated.

Pricing Problem for De-CG

The ILP-CG has a proven accuracy for the obtained solution. However, the directed p-cycle generation in each pricing problem of ILP-CG is still an ILP model. Thus, we provide a heuristic decomposition algorithm to generate directed p-cycle effectively, shown as Algorithm 3.2. Therefore, another CG approach, namely De-CG, is proposed to deal with large-scale traffic. The Algorithm 3.2 searches the directed p-cycle candidate enumeration set and selects the one with minimized reduced cost as the generated column. For a huge directed p-cycle candidate enumeration set, we can always shrink it to get a result with a reasonable execution time.

Line 1 initializes I, cost, and i * . The input I and I * are first adopted from Algorithm 3.1, and they are updated in each pricing problem. Lines 2-5 calculate the reduced cost of each directed p-cycle and the one with minimized reduced cost is selected. With the optimal dual variables α a and β s a , the reduced cost can be expressed as Eq. (3.64).

cost i = θ 1 • ∑ a∈C i Φ i a + θ 2 • E i -∑ a∈P i ∑ m∈M π im a • T m • α a + ∑ a∈C i ∑ s∈S x is a • β s a (3.64)
Lines 6-7 add the new column to the set I * . Then, lines 8-10 ensure De-CG enters the next column generation if it finds another promising directed p-cycle. Lines 11-12 find no negative reduced cost for the rest of directed p-cycles, where no more feasible directed p-cycle can be generated. Then, the set I * with all the feasible directed p-cycles is sent to the final solution, in which the master problem with integer variables is solved.

Final Solution

In the final solution, we need to transfer the LRMP into the ILP model. A simple way to get the final solution is using the branch-and-bound method embedded in the CPLEX solver to get the integer values from the LRMP. However, before we formulate the final solution, there is one issue that needs to be explored.

The constraints (3.62) in the LRMP aim to assign the dedicated FSs for each p-cycle. Observing that the variables z i are relaxed from binaries to reals in the CG method, the constraints (3.62) are also relaxed. Then, low quality of the linear relaxation allows fractional values of z i , in this way keeping the value of the product on the left-hand side less than or equal to 1. For instance, by setting column 1 with z 1 = 0.5 and column 2 with z 2 = 0.5 in the LRMP, these two directed p-cycles might be assigned with the same FS(s) even they have the common link(s). It is best for the LRMP but against the principle of spectrum conflict. After z i are transferred from reals to binaries for the final master problem in its integer programming version, the constraints (3.62) prohibit these directed p-cycles selected at the same time. Thus, constraints (3.62) do not fulfill their purpose on spectrum allocation for every directed p-cycles. Although a feasible solution can always be obtained by simply using the branch-and-bound method to the final master problem, it can be further improved by adjusting their assigned spectrum in the final solution.

A simple way to the above problem is to re-allocate the number of assigned FSs and the FS index location for all the generated columns. Thus, we added some constraints in the final master problem to avoid the spectrum conflict that occurred among the columns. In this work, one of our ambitions is to measure the obtained result based on a guaranteed lower bound. Therefore, the constraints (3.62) are still adopted in the LRMP, which might contribute to getting a guaranteed lower bound. In this way, we can get a qualified lower bound for the ILP-CG.

We formulate the final solution by the following ILP.

min θ 1 • ∑ i∈I * ∑ a∈C i Φ i a + θ 2 • ∑ i∈I * E i (3.65) s.t. ∑ i∈I * x is a ≤ 1, ∀s, ∀a (3.66) ∑ i∈I * π im a • T m ≥ ϕ a , ∀a ∈ A ϕ , m = m i (3.67) ∑ s∈S x is a = Φ i a , ∀i ∈ I * , a ∈ C i (3.68) Φ i a = Φ i , ∀i ∈ I * , a ∈ C i (3.69) π im a ≤ Φ i , ∀i ∈ I * , a ∈ P i , m = m i (3.70)
The objective of the final solution is the same as the master problem. Note that the variables z i need to be transferred from reals to binaries. Constraints (3.66) and (3.67) are adopted from the master problem. They guarantee no spectrum conflict for the selected directed p-cycle and enough FSs assigned for the protection, respectively. Constraints (3.68) to (3.70) are adopted from the initial solution. They determine the relationship among the variables Φ i , Φ i a , π im a , and x is a for directed p-cycle i. Note that the directed p-cycle i with Φ i = 0 is not selected in the final solution as it has no contribution to the protection. It is equivalent to the column i with z i = 0.

Optimality

We then use ϵ-optimality to present the accuracy (ϵ) obtained by the CG approaches [START_REF] Jaumard | Efficient spectrum utilization in large scale rwa problems[END_REF], which can be expressed by

ϵ = η CG -η LP η LP (3.71)
where η LP is the optimal value obtained by LP model of the LRMP in the ILP-CG, which gives the proven lower bound on the optimal integer value of the final solution, i.e. η CG . Thus, the accuracy (ϵ) can be adopted to show the solution quality of the CG approach. Note that the De-CG can also provide a lower bound if the directed p-cycle candidate enumeration is complete with all the columns. However, the directed pcycle candidates in the scenarios with large-scale traffic is too many to be enumerated, of which the amount is up to thousands of millions. The lower bound obtained by De-CG is guaranteed. Thus, we only use the ILP-CG to compute η LP in this work. Such a way can guarantee the quality of the ϵ-optimality.

Simulations and Performance Evaluations

We use CPLEX 12.06 to solve the proposed ILP models on a server with 128 GBytes RAM, and the proposed two CG approaches are solved on a PC with 8 GBytes RAM. The 6-node network (6 nodes, 16 directed links, average link length 338 km, and average nodal degree 2.67, shown in Fig. 3.1 [START_REF] Chen | On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks[END_REF], NSFNET network (14 nodes, 44 directed links" average link length 1, 936 km, and average nodal degree 3.14), and COST239 network (11 nodes, 52 directed links, average link length 578 km, and average nodal degree 4.73) [START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF] are used as testbeds, shown in Fig. 3.6. To evaluate the directed pcycle, we compare our proposed LEF-p-cycle with the directed p-cycle design based on voltage and root node using MILP and heuristic algorithm [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF], which are called VRN in the simulations. For a fair comparison, we also set the same objective to VRN, which is defined as the same as Eq. (3.4). For simplicity, we assume the available FSs are 300 maximum on each link, and we also set the weights of the objective as the same value, i.e. θ 1 = θ 2 = 1, if not indicated specifically. We consider the static scenarios, where the traffic is generated with pairs of nodes following Traffic Asymmetry (TA) among (0, 125 Gbps]. The parameter TA is adopted from works [START_REF] Jaumard | Directed vs. undirected p-cycles and FIPP p-cycles[END_REF][START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF] to indicate the average traffic asymmetry in the network by Eq. (3.72) and (3.73). The working paths are generated via Dijkstra's algorithm.

TA uv = |r uv -r vu | r uv + r vu • 100% (3.72) TA = TA uv (3.73)
where r uv is the traffic demand from node u to node v, and TA uv indicates the traffic asymmetry between nodes u and v. The traffic become symmetric with TA = 0% and asymmetric with TA = 100%, respectively. Note that TA remains 20% if not specified.

Validation of the proposed directed p-cycles

We first explore the performances on the objective, i.e. the joint power consumption and spectrum usage for the proposed ILPs of the directed p-cycles with modulation format 66 Power FS Usage adaptation, i.e. ILF, ALF, and LEF, compared with the traditional MILP, i.e. VRN. These simulations are conducted under small-scale traffics (from 10 to 50) with the maximum number of directed p-cycles (|I|) from 2 to 6, respectively, in the 6-node network due to their high computational complexity.

The overall performances of the proposed methods are better than VRN for all situations in the simulation results. We notice the performances for the proposed three ILPs are the same in Fig. 3.7. Because the proposed three directed p-cycle designs are the same in the modulation format adaptation although with different formulations. The reduction on the joint objective value is then summarized in Fig. 3.7(f). The proposed directed p-cycle designs obtain the improvement on the objective for all the situations, which is up to 24.31% with at most 2 directed p-cycles allowed to protect the traffics.

The objective value also decreases as |I| increases. A smaller number of directed p-cycles leads to a longer protection path length for directed p-cycles, thus a lowerorder modulation format, where the proposed directed p-cycles show a more obvious improvement. We can conclude that more directed p-cycles allowed for the ILP and MILP model provide better protection on the desired links. However, the extremely long execution time needs to be tolerated, which will be observed in Section 3.6.3.

We also notice the spectrum usage gets worse with more directed p-cycles. The proposed methods can find a better solution, which can provide a better solution to reduce power consumption, but at the expense of higher spectrum costs. This is because the value of power consumption occupies a larger share of the objective value, and sacrificing spectrum usage can significantly reduce power consumption, thus a lower objective. We notice that the performances of the proposed directed p-cycles with modulation format adaptation are the same in the former subsection. Therefore, to verify the efficiency of the acquired solutions, we analyze the performances on the execution time with 72 hours running time limitation. The simulations are conducted with 50 requests with a maximum number of directed p-cycles (|I|) from 2 to 5. As shown in Table 3.2, the LEF is most effective. The directed p-cycle generation of LEF is most complex on flow design, but it can provide the path for every on-cycle node pair, thus the modulation format assignment is fast. On the contrary, the ILF and ALF need to determine the modulation format adaptation with different situations of the protection path whether it goes through the root node or not, and it increases the computational complexity. Also, ALF employs the number of flows to construct the directed p-cycle. It is effective on directed p-cycle generation but suffers to determine each protection path. Eventually, the ALF takes the longest execution time.

Analysis on Execution Time of Three ILP Models

Validation of CG Approaches Compared with ILP

To verify the efficiency and quality of the solution acquired by the CG approach, we conduct simulations under small traffic demands (the number of requests varies from 10 to 50) with ILP model and CG approaches in the 6-node network. As the LEF p-cycle design shows the best performance, we only conduct LEF ILP model in this section. The maximum number of directed p-cycles is set as 6 for LEF ILP model. The results are summarized in Table 3.3, in which Obj represents the objective value, |I * | is the number of used directed p-cycles, LB denotes the lower bound of the ILP-CG, t denotes the execution time in second, Gap is introduced by the gap of the CG approaches compared with the ILP model, and ϵ is the optimality from the CG objective values to LB in Eq. (3.71). We also show the lower bound obtained by De-CG to verify the quality of the solution. Note that the lower bound obtained by ILP-CG is solid because it generates implicitly all potential p-cycles with the ILP model in the pricing problem. The enumeration of the De-CG, however, is not always complete due to the scalability issue.

As shown in Table 3.3, two proposed CG approaches have basically similar performances compared with the ILP. The ILP-CG has even better performance than the ILP when the requests are more than 10, in which the ILP-CG finds a better solution with more directed p-cycles. For instance, the number of used directed p-cycles for the ILP-CG is 20 with 30 requests, but |I| is pre-set as 6 in the ILP model due to its high computational complexity. It shows a significant advantage of the CG approaches lies in the high efficiency and the adaptive number of generated directed p-cycles. A similar tendency can also be observed in the De-CG. However, the performance of the De-CG is slightly worse than the ILP-CG, because the decomposition algorithm of the De-CG does not search every spectrum combination, which may reduce the quality of the solution. The differences between the two CG approaches will be analyzed in Section 3.6.4.

We also notice the execution time for ILP is huge due to the complex joint problem. Conversely, the execution time for two CG approaches is negligible. Table 3.3 shows LB ′ acquired by the De-CG is higher than LB from the ILP-CG, but it is still lower than the ILP results due to the linear relaxation of the integer values. However, the lower bound obtained by the De-CG is not guaranteed, for the De-CG may ignore some columns to accelerate the execution with large problem instances. The ϵ-optimality of ILP-CG is less than 11%, which shows the performance of the ILP-CG can be guaranteed by the accuracy ϵ. Note that the ϵ of De-CG is also introduced by its objective value and the ILP-CG-obtained lower bound.

Comparison of ILP-CG and De-CG for Medium-Scale Traffics

We then compare the performances of ILP-CG and De-CG. The simulations are conducted under medium-scale traffic demands (the number of requests varies from 50 to 200) in the NSFNET and COST239 networks. The abbreviations are set as same as before. It is observed in Table 3.4 that the objective values of the De-CG and ILP-CG are not in a big gap, but the ILP-CG performs better than the De-CG. The relatively gap between them is 4.12% and 2.05% in the NSFNET network and COST239 network, respectively. However, it comes at the cost of more execution time for ILP-CG, which is, on average, 109 times longer than the one for De-CG in the NSFNET network, and 609 times in the COST239 network. We can conclude the De-CG fulfills its purpose on high computational efficiency with a comparable solution. Table 3.4 shows the De-CG consumes the same execution time with 150 and 200 requests in the COST239 network due to the numbers of column candidates reaching the limitation. We also notice the prob-lem in the COST239 is more complicated with more execution time. It can be explained by the denser network topology of the COST239 network. An interesting inconsistency is that more requests do not necessarily lead to more execution time and used directed p-cycles for the ILP model and ILP-CG. The reason for this is that fewer working links may need more finer directed p-cycles, i.e. directed pcycles with less on-cycle links and shorter protection path lengths, to reduce the overall power consumption and FSs usage. In other words, if the number of working links is large enough, the optimal solution needs less directed p-cycles, which can protect more desired links with more on-cycle nodes and links. The number of used directed p-cycles in a way reflects complexity of the problem. Thus, more computational time for ILP and ILP-CG is required. Different in the De-CG, more working links result more column candidates. To traverse the candidate enumeration, it requires more computational time in the De-CG.

Validation of LEF (De-CG) Compared with VRN (heuristic) for Large-Scale Traffics

We further investigate the system performance of LEF using the De-CG for large-scale traffic (from 200 to 1000) in NSFNET and COST239 networks, compared with VRN using the heuristic in [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF]. We set the maximum number of FSs for each link as 1,200 for large-scale traffic. Note that the directed p-cycle candidate enumeration, obtained by Algorithm 3.1, expands as the traffic grows. Although the directed p-cycles constructed with different on-cycle links may be only no more than 1,000, they rapidly increase as we treat the directed p-cycle with a different combination of desired links as a new column. For instance, there are over 10 million directed p-cycle candidates in the NSFNET network with 1,000 requests. Thus, we restrict no more than 1 million directed p-cycles of the candidate enumeration by adjusting searching steps, e.g. each directed p-cycle generated with an even number of FSs, in case the simulation runs out of memory. For readability, we use legend Power and p-cycles in Fig. 3.8 to represent the power consumption, and the number of directed p-cycles, respectively. As shown in Fig. 3.8, the LEF significantly outperforms VRN in both NSFNET and COST239 networks.

A joint objective value reduction up to 48.39% can be observed in Fig. 3.8(c). The improvement of LEF directed p-cycles is mainly obtained on power consumption, but surprisingly the FS usage for LEF is worse. It implies a trade-off between power consumption and FS usage, where less power consumption comes with the price of more FS usage. It is also due to the fact that the value of power consumption occupies a larger share of the objective. The results confirm that the advantage of the LEF is owing to the proposed modulation format adaptation on the one hand. The LEF allows the directed p-cycles to be assigned with higher-order modulation format and lower power consumption, even though they are with the same on-cycle links as the ones in VRN. On the other hand, the CG approach can provide a high-performed solution. It results in a much better power consumption obtained by the proposed algorithm, compared to the conventional heuristic.

Validation of LEF (CG) Compared with VRN (heuristic) in Terms of Traffic Asymmetry

In this subsection, we compare the proposed CG algorithms with the conventional heuristic in NSFNET and COST239 networks with 100 requests. The simulations are conducted under different traffic asymmetry, i.e. TA, varying from 0% to 100%. Fig. 3.9 then summarizes the overall reduction of the proposed CG methods compared to the VRN. Fig. 3.9(a) shows a significant improvement from 60.72% to 69.43% for De-CG in NSFNET network, while it is 62.42% to 70.68% for ILP-CG. The performance of ILP-CG outperforms De-CG under each traffic asymmetry, which is also observed in COST239 network in Fig. 3.9(b). The overall reduction in COST239 network is from 22.25% to 51.35%, and 40.29% to 63.40% for De-CG and ILP-CG, respectively. The reason is that the complexity is higher in a denser network, and ILP-CG is more promising compared to De-CG. Thus, the improvement of ILP-CG gets even more in the more complicated scenarios owing to its optimality. We also notice the overall reduction is at minimum with symmetric traffic with TA = 0%. Under such situations, the traffic is the same in both directions of each link. Thus, the directed p-cycle protection may lose flexibility at a certain level, especially for the proposed LEF with compact modulation format adaptation. However, the advancement of LEF becomes visible once the traffic pattern shows asymmetry.

Analysis on Weights

We are presently looking into the effects of different weights, i.e., θ 1 and θ 2 , in the situations with 1000 requests using De-CG in NSFNET network and COST239 networks. θ 1 weights the overall spare capacity usage and θ 2 weights the power consumption for the directed p-cycles. The maximum number of FSs for each link is also set as 1,200. We change the ratio of θ 1 and θ 2 varies among 1 : 0, 1 : 0.001, 1 : 0.01, 1 : 1, and 1 : 0. Then, we present the results of objective value, FS usage, power consumption, and the number of generated directed p-cycles for these solutions, to explore the performances under different weightings.

As shown in Table 3.5, the power consumption decreases as it weights more, along with the FS usage increasing, in the COST239 network. We notice when the ratio of θ 1 and θ 2 varies from 1 : 1 to 1 : 0 in the NSFNET network, both the power consumption and FS usage get worse. One possible explanation may be the minimization of FS usage can help power consumption optimization at some certain level. However, the connection between them is not always positive. According to the discussion in Section 3.6.5, the power consumption can be reduced at the expense of higher spare capacity usage. Thus, a singular point of spare capacity usage may exist in the NSFNET network, which makes the most reduction on power consumption.

Conclusion

In this chapter, we proposed three novel flow-based directed p-cycle designs without candidate cycle enumeration, i.e. ILF, ALF, and LEF with the consideration of modulation format adaptation in EO-DCNs. We first formulated three directed p-cycle designs as ILPs to protect networks against single link failure with the objective to jointly minimize power consumption and spectrum usage. Then, we proposed time-efficient and performance-guaranteed approaches to overcome the scalability issue. Simulations are conducted to compare the proposed methods with the conventional directed p-cycle design which uses a rough upper bound on modulation format selection. The results showed the superiority of the proposed directed p-cycle protection by saving up to 70.68% joint objective value of power consumption and spare capacity usage. We also observed that LEF is the most efficient one among the proposed directed p-cycle designs. Two proposed CG approaches have shown near-optimal performance with hundreds of instances, and comparable solutions with short execution time and high scalability in the situations of large-scale traffic, respectively.

Introduction

With the high spectrum efficiency and huge spectrum resource capacity, Elastic Optical inter-DataCenter Networks (EO-DCNs) have shown the ability to support big data storage and provide the platform for the deployment of diversified network services and applications [START_REF] Bari | Data center network virtualization: A survey[END_REF][START_REF] Gong | Efficient resource allocation for all-optical multicasting over spectrum-sliced elastic optical networks[END_REF][START_REF] Ju | Disaster-resilient cloud services provisioning in elastic optical inter-data center networks[END_REF][START_REF] Wang | A survey on data center networking for cloud computing[END_REF][START_REF] Zhou | Joint optimization for the delivery of multiple video channels in telco-cdns[END_REF][START_REF] Zhu | Dynamic service provisioning in elastic optical networks with hybrid single-/multi-path routing[END_REF]. However, as tens of natural disasters worldwide destroy power systems and subsequently affect optical networks [START_REF] Neelam | A scientometric review of global research on smart disaster management[END_REF] The interruption of networks may break off the cloud services, 5G, and content distribution services, and it is especially costly for inter-datacenter networks. The downtime of each data center (DC) server may cause a loss of $ 9,000 per minute [START_REF] Carroll | How effective is your data center's disaster recovery plan?[END_REF], and such disaster-caused network paralysis may lead to billions of dollars in losses. To maintain the survivability of content delivery in EO-DCNs, anycast technique provides the mechanism of path protection against network failure [39] [72]. When the content or service is required, it is provisioned with several potential DCs and corresponding routing. However, existing protection schemes mostly aim at single link or node failure, which cannot deal with such disaster failure [START_REF] Gomes | A survey of strategies for communication networks to protect against large-scale natural disasters[END_REF]. Hence, there is a strong need to develop protection methods to ensure end-to-end communications in EO-DCNs.

The requirement for huge content storage space also grows rapidly. The amount of Internet data generated will grow to 2,142 ZB in 2035 [START_REF] Of | Information and C. Technology[END_REF]. Alone the content streaming contributes an overwhelming percentage of Internet traffic, e.g. 79% in 2016. To store these data, 597 hyperscale datacenters have been built by the end of 2020. The market size of the internet DC will reach 139.6 billion dollars by the end of 2020 [100]. To reduce the pressure of storage space for DCs, the maximum distance separable (MDS) codes provide a feasible method of building a cooperative storage system (CSS) for EO-DCN, in which content can be encoded and divided into numerous different fragments, and they are then stored spatially in multiple DCs [START_REF] Dimakis | Network coding for distributed storage systems[END_REF]. Through MDS coding, the required content can be decoded/recovered through the coded segments from different DCs. Therefore, a request can be satisfied with the help of the cooperation of multiple DCs holding the coded segment of the requested content. In other words, multiple DCs can be assigned as the primary DCs simultaneously and a distinct working path from the source node to each of these primary DCs is established to serve the request. Besides, a backup DC is also assured to protect any one of the primary DCs. Meanwhile, the multiple working paths and backup path from end to content are generated as DZ-disjoint to protect the services against a single DZ failure. Thus, if any working path is affected by DZ failure, the backup path can be switched on to replace the failed working path, and enough data segments can guarantee the recovery of the required data. Furthermore, the DC assignment together with content partition and placement also needs to be explored.

We aim to design a novel disaster protection scheme in EO-DCNs leveraging CSS and adaptive multi-path routing. The applicable scenarios include cloud service, content delivery, distributed storage, video-on-demand service, etc. We focus on the cooperative dedicated end-to-content backup path protection (CDP) against disaster failure. To support the adaptive multi-path routing for each request with disaster resilience, the contents are partitioned and jointly encoded into several fragments, each of which is then stored on a DC located in different disaster zones. Then, the CDP allows each request provisioned by multi-path routing with the adaptive number of paths. Besides, we observe that the more working paths CDP uses, the smaller content storage space is required. Then, we extend CDP to maximum CDP (M-CDP), which enables us to find the optimal content storage space by using the maximum number of paths. We further explore how network topologies impact system performance. The existing works of disaster protection leverage a single working path and mirrored storage, which clones the whole content on one backup DC. To the best of our knowledge, it is the first time that the CSS and adaptive multi-path routing are employed for disaster protection in EO-DCNs. The contributions of this chapter are summarized as follows.

• We propose a novel disaster protection scheme leveraging CSS and adaptive multiple working paths, namely CDP. The studied CDP problem involves DC assignment, content partition and placement, adaptive working/protection paths computation, modulation adaption, as well as spectrum allocation. We formulate the joint problem as an integer linear program (ILP) to jointly minimize the spectrum usage and maximal index of occupied frequency slots. Meanwhile, the content storage space is also reduced owing to content partition in CSS and multi-path routing.

• To find efficient CDP strategies for large instances, we then propose a heuristic algorithm, namely HCDP, to solve the working/protection path generation, modulation adaption, adaptive multi-paths routing, and spectrum allocation. The solution in the HCDP algorithm is generated greedily first and then optimized globally after, and it uses coloring algorithms to minimize the spectrum resource by decomposing the spectrum conflict.

• Through CDP, we observe that the spectrum utilization performance is not positively related to the number of the working paths [START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF]. Hence, to further explore the impact of multi-path routing in the CDP, we propose to generate the maximum number of working paths for each request in the CDP scheme, which is then called M-CDP. Simulation results demonstrate that M-CDP provides a better solution on content storage space while using more spectrum resource.

• Finally, we compare two CDP schemes and a traditional scheme using single-path routing and mirrored storage in NSFNET, COST239, and the US Backbone networks. Simulation results demonstrate the significant performance improvement of the proposed methods compared with the traditional protection scheme.

The rest of the chapter is organized as follows. Section 4.2 first gives the related work. We then present the CDP disaster protection scheme in Section 4.3 and formulate it by a joint ILP in Section 4.4. In Section 4.5, heuristic algorithm, HCDP, is proposed for CDP and M-CDP, respectively, and their performances are evaluated in Section 4.6. Section 4.7 concludes this work.

Related Work

Several works about disaster protection in optical networks have been published. A fast and coordinated emergency backup system in geographically distributed optical inter-DC networks was proposed in [START_REF] Xie | Evacuate before too late: Distributed backup in inter-dc networks with progressive disasters[END_REF][START_REF] Yao | On fast and coordinated data backup in geo-distributed optical inter-datacenter networks[END_REF], which is triggered in response to a predictable and progressive disaster. A stochastic model named earthquake risk and backbone optical network model was provided in [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF], which estimated the impact of earthquake disasters on a backbone optical network. The authors assessed the generic applicability and evaluated the performance of protection, recovery, and topology design scheme irrespective of the varying geographical region and network topology. Research [START_REF] Savas | Network adaptability to disaster disruptions by exploiting degraded-service tolerance[END_REF] developed a degraded-service-network to maintain the most traffic after disaster failure, and it uses degraded-service tolerance as the parameter to assign the resource to the connections. The RECODIS project [START_REF] Gomes | A survey of strategies for communication networks to protect against large-scale natural disasters[END_REF] was formed to achieve disaster resilience, and the members of its Working Group 1 gave a survey, which summarized different disaster-resilient strategies of wavelength division multiplexing (WDM) optical networks. The concept of disaster in the networks is described as a group of nodes and links, called shared risk group (SRG), in which the disaster failure would destroy the corresponding nodes and links [START_REF] Develder | Joint dimensioning of server and network infrastructure for resilient optical grids/clouds[END_REF] [START_REF] Pašić | Fradir: A novel framework for disaster resilience[END_REF]. A framework for the disaster-resilient optical network called FRADIR was designed in [START_REF] Pašić | Fradir: A novel framework for disaster resilience[END_REF], in which authors brought together network design, failure modeling, and protection routing. The disaster resilience is achieved via the edge availability values, shared risk link groups list, and dedicated path protection. Authors in [START_REF] Tomás | Disaster recovery layer for distributed openstack deployments[END_REF] presented the disaster recovery layer that enables OpenStack-managed DC workloads, virtual machines and volumes, to be protected and recovered in another DC. Researchers investigated in [START_REF] Ferdousi | Joint progressive network and datacenter recovery after large-scale disasters[END_REF] a joint progressive network and DC recovery, in which the network recovery and DC recovery are conducted in a coordinated manner.

While keeping the disaster resilience for optical networks, several works have been proposed to optimize the network resource. Such disaster protection design was firstly conducted in [START_REF] Habib | Design of disaster-resilient optical datacenter networks[END_REF]. The DC placement and content management were explored for EO-DCNs to minimize risk, in which the risk is defined as the expected loss of content. In [START_REF] Yin | Spectral and spatial 2D fragmentation-aware routing and spectrum assignment algorithms in elastic optical networks[END_REF], the algorithms considering both routing and spectrum assignment (RSA) problems for elastic optical networks were proposed, in which the RSA problem has been shown to be NP-hard. The content placement and independent end-to-content paths calculation were explored for the disaster-resilient k-node (edge) content connected EO-DCNs [START_REF] Li | Content placement with maximum number of end-to-content paths in k-node (edge) content connected optical datacenter networks[END_REF]. Cloud service with mirrored storage method in EO-DCNs against disaster failure was investigated in [START_REF] Ju | Optimization of Protection Schemes for Next Generation Optical Networks (Optimisation de la Protection des Réseaux Optiques de Nouvelle Génération[END_REF] [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF], in which the authors proposed both dedicated and shared path protection to maintain disaster resilience. Literature [START_REF] Wu | On the distance spectrum assignment in elastic optical networks[END_REF] gave a coloring algorithm-based method to generate a conflict graph, which is then used to assign the FSs for all the paths in the network. Diversity and redundancy problem was studied in [START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF], to achieve network resiliency in terms of availability, reliability, and fault tolerance for service chain provisioning. The existing proposed schemes are based on mir-rored replication system, which reserved the same bandwidth on the backup path as the working path, and the storage space is linearly increasing as the number of backup DCs grows, leading to a significant waste of network resource.

As for the network storage system, the CSS has shown better performance in storage efficiency. With erasure codes, the required data is able to be recovered by offering several encoded distinct fragments, which are of the same size in all as the original data. Such codes have a long research history, and typical erasure codes include Reed-Solomon code [START_REF] Reed | Polynomial codes over certain finite fields[END_REF], Low-Density Parity-check Code [START_REF] Gallager | Low-density parity-check codes[END_REF], and so on. Literature [START_REF] Dimakis | Network coding for distributed storage systems[END_REF] first gave the concept of network coding and regenerating code design, and analyzed the trade-off between repair bandwidth and storage space, in which the code with minimal storage space can be regarded as MDS codeAuthors in [START_REF] Asghar | Survivable inter-datacenter network design based on network coding[END_REF] proposed a survivable virtual network based on network coding, which can achieve the minimal spare capacity for backup links. Erasure codes are also used to achieve content distribution in [START_REF] Wu | Content fragmentation: A redundancy scheme to save energy in cloud networks[END_REF][START_REF] Xu | Deterministic data distribution for efficient recovery in erasure-coded storage systems[END_REF]. Content Distribution was also studied in literature [START_REF] Torre | Implementation of network-coded cooperation for energy efficient content distribution in 5g mobile small cells[END_REF], which utilizes Random Linear Network Coding to reduce energy consumption. Paper [START_REF] Liu | Exact-repair codes with partial collaboration in distributed storage systems[END_REF] proposed a partially collaborative repair code to maintain resilience from multiple node failures. In [START_REF] Bao | Adaptive path splitting based survivable virtual network embedding in elastic optical networks[END_REF], the authors proposed an adaptive multi-cast scheme to optimize the spectrum utilization and blocking ratio for virtual network embedding in elastic optical networks. However, none of the existing works involves disaster protection.

These studies are essential for disaster protection. Previous studies have demonstrated the potential of the CSS on spectrum usage and storage space. However, with respect to all these works, the CSS has never been implemented for disaster protection. The existing disaster protection is only studied based on the traditional mirrored storage system, in which each redundancy of the content in EO-DCNs is a simple clone of the whole original data, and no adaptive multi-path routing is available. Therefore, it is essential to explore CSS-based disaster protection strategies in EO-DCNs. We first give a simple example in Fig. 4.1 to better illustrate the disaster protection scheme leveraging CSS. We consider a 6-node network with 3 DCs (nodes 1, 4, and 6), 1 content, and 5 DZs, where a request originated from node 5 should be provisioned with the content. For simplicity, we set the modulation format BPSK in this case. As-suming the transmission rate of 100 Gbps is required to transport the content from a DC to node 5. Note that the bandwidth per frequency slot (FS) for EO-DCNs is 12.5 GHz in this work. Fig. 4.1 (a) draws the solution provided by the traditional dedicated end-to-content backup path protection (DP). The acronym of dedicated end-to-content backup path protection is DEBPP in the works [START_REF] Ju | Optimization of Protection Schemes for Next Generation Optical Networks (Optimisation de la Protection des Réseaux Optiques de Nouvelle Génération[END_REF] [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF]. To ease the readability, we use DP referring to it in this work. In this scheme, node 6 is set as the primary DC storing the entire required content, and the content is also mirrored on the backup DC node 1. The request is provisioned with the working path 5-6 and the backup path 5-1, and 8 FSs are utilized on each fiber link of both working and protection paths. While Fig. 4.1 (b) presents a solution provided by the scheme leveraging CSS, i.e. CDP. With the help of advanced coding techniques like MDS code [START_REF] Dimakis | Network coding for distributed storage systems[END_REF], the content can be coded into infinitive distinct fragments, and stored on different DCs. This spatial and cooperative storage method has a significant advantage in that the original content can be recovered through the reception of any coded fragments of the same size. Different from the previous solution using only one primary DC, both nodes 1 and 6 are served as the primary working DCs and the backup DC is node 4. Instead of storing the whole original content, only the coded fragments are stored on these DCs, and each has a half size of the original one. We can see the request can get the entire required content by establishing two simultaneous working paths from node 5 to nodes 1 and 6. in Fig. 4.1 (b). Thus, the request is provisioned with two working paths and one backup path, which are DZdisjoint except for the DZ that the source node is located in. Each working and backup path benefits from the cooperative method to lower its transmission load, which only needs half of the required FSs. Supposing the storage space for the content is C, then CDP allows each DC to cost only C/2 in this case. Although the number of total FSs served on the working paths is the same, it is reduced on the backup path from 8 to 4. The spectrum usage, maximal occupied FS index (MOFI), and storage space are then summarized in Table 4.1. A digraph G(V, A, D) is used In this chapter to model the network, where V denotes the set of nodes, A represents the set of symmetric directed links, and D is the set of DCs. For each disaster zone, it may affect several links and nodes. We use z ∈ Z to denote the affected nodes as well as the links. For any request r(s r , z r , |k r |, c r , ϕ r ), s r is the source node, z r is the disaster zone in which the source node is located, |k r | is the number of the working paths to be generated, c r is the required content, and ϕ r is the required number of FS using the modulation format BPSK. Note the request will be blocked if a DZ failure destroys more than one generated path simultaneously, including the working path and backup path. To avoid such a situation, we must force the generated paths of each request can not be affected by the same DZ (except z r ). Furthermore, we denote |k r | as the number of the path for the request r, and its value is affected by source nodal degree, DZ, content placement, DC locations and etc. In fact, it is not an easy job. The range of |k r | can be determined by the Algorithm 4.1 line 1-21 (see later in Section 4.5). The objective of the studied disaster protection problem is to minimize the weighted sum of the total spectrum usage and the MOFI in the whole network (see later in Section 4.4, Eq(4.1)). The objective affects the overall spectrum utilization and network load balancing. The main considerations of each sub-problem can be summarized as follows.

CDP Disaster Protection Scheme

1) Content partition

In this work, a cooperative strategy is proposed to optimize content partition against DZ failure. We assume a content with l size is divided into m fragments of equal size l m . They are jointly encoded into k ˜(k ˜> m) distinct fragments, each with l m size and placed at most K (k ˜> K > m) different DCs. Any m distinct fragments would successfully recover the original data. For the request r, the number of fragments on each DC depends on the number of working paths, which should be sufficient for every path that requires the corresponding content. Therefore, the storage space of a content c for CSS in each DC is reduced to l t max rkcd , where t max rkcd is the maximum transmission capacity of the path demanding the content c on DC d. Note that it is possible that the transmission capacity is bigger than the size of the content, due to the granularity of one FS.

2) DC assignment and content placement

Based on the available DC locations and the prior information, DC assignment and content placement are jointly optimized. The prior information for the content is the distribution of the potential source nodes, which contains source node ID, content ID, and the maximal number that the working paths can be generated (|k r |). In order to ensure content survivability, at least (k max r,c ) DZ-disjoint DCs should be assigned as the storage DC, where k max r,c is the maximum of |k r | among the requests that require the content c. Note that the fragments stored at each DC are distinct from each other in the CDP scheme since they are generated by MDS coding.

3) Working paths and backup path generation

We focus on the failure caused by a single DZ, in which situation the working paths and backup path should be generated as DZ-disjoint (except z r ). Along the paths, the flow conversation should be followed. The dedicated backup path generation method based on CSS is considered, i.e. CDP. For CDP, a backup path is generated with dedicated spare capacity, in which the FSs cannot be shared when any two paths use the common link. Note that the failure of z r would absolutely block the request whose source node is s r . Thus, this case leads to no solution for the protection of the request r, which is consequently removed from the input request set of our problem.

4) Modulation adaption

We consider the modulation level set M consisting of BPSK, QPSK, 8-QAM, and 16-QAM. The granularity of FS is 12.5 GHz in this work. Thus, the protection capacity of one FS with each modulation format is 12.5, 25, 37.5, and 50, in Gbps, respectively [START_REF] Chen | On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks[END_REF]. The corresponding maximum transmission reaches of these modulation formats are assumed to be 9,600, 4,800, 2,400, and 1,200, in km, respectively [START_REF] Zhang | Dynamic RMSA in spectrum-sliced elastic optical networks for high-throughput service provisioning[END_REF]. Each path should be set as the maximum transmission rate depending on its path length since a higher modulation format can provide the provisioning with less spectrum usage.

5) Adaptive multi-path routing

For the requests supporting multiple working paths generation, we assign the first path as the working path and the last path as the backup path. The rest paths are automatically selected for the minimum objective. Assuming |k r | paths are generated for the request r, then any |k r | -1 paths should provide sufficient transmission capacity to serve the request.

6) Spectrum allocation

For each path, the spectrum is allocated under the following principles. a) Spectrum continuity: Without spectrum conversion in this work, each link is assigned with the same FSs along the path. b) Spectrum contiguity: The FSs to be assigned should be continuous for each fiber link. c) Spectrum conflict: The spectrum allocation for each backup path is dedicated in CDP.

Joint ILP formulation

In this section, we first give the sets, parameters, and variables of ILP. Then, we formulate a joint ILP model for CDP.

Sets, Parameters and Variables

For the sake of readability, we use [|k r |], ∀k, ∀b, ∀v, ∀a, ∀d, ∀c, ∀z, ∀m, and ∀r to denote

{1, 2, • • • , |k r |}, ∀k ∈ [|k r |], ∀b ∈ B, ∀v ∈ V, ∀a ∈ A, ∀d ∈ D, ∀c ∈ C, ∀z ∈ Z, ∀m ∈ M,
and ∀r ∈ R, respectively. We also use ∀r ̸ = r ′ , and ∀k ̸ = k ′ to denote ∀r, r ′ ∈ R, r ̸ = r ′ , and ∀k,

k ′ ∈ [|k r |], k ̸ = k ′ , respectively, if not indicated specifically.
The network sets and parameters are presented as follows.

• G(V, A, D): Network with node set V, link set A and DC set D.

• C: Set of content.

• K: Number of assigned DCs for each content.

• R: Set of requests r(s r , z r , |k r |, c r , ϕ r ), where s r , z r , |k r |, c r and ϕ r are source node, disaster zone that source node is placed, the number of paths that can be generated, content, and the the required number of FSs using BPSK, respectively. |R| is the number of the requests.

• k r : Set of paths for the request r. |k r | is the number of paths that can be generated. We use nodal degree of the source node to initialize |k r |. Note that we define the first path as the working path, and the last (|k r |-th) path as the backup path.

For the second to |k r | -1-th path, they are adaptively generated to minimize the spectrum utilization.

• D r : Set of the content-placed DCs for request r. |D r | is the number of the contentplaced DCs for request r.

• m ∈ M: The available modulation level set, i.e., BPSK, QPSK, 8-QAM, and 16-QAM.

• h m : Maximum transmission reach at modulation level m, which is 9, 600, 4, 800, 2, 400, and 1, 200, in km for BPSK, QPSK, 8-QAM, and 16-QAM, respectively [START_REF] Chen | On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks[END_REF]. h max =9600 km.

• T m : The spectrum efficiency. The available transmission rate per FS (12.5 GHz) for BPSK, QPSK, 8-QAM, and 16-QAM is 12.5, 25, 37.5, and 50, in Gbps, respectively. Thus, T m is 1, 2, 3, and 4, respectively.

• d a : The distance of link a in km.

• k max r,c : The maximum of |k r | among the requests that require the content c. • z ∈ Z: DZ/DZs set. Z ⊂ G contains the sets of links and nodes.

• S: Set of FSs on each link. |S| denotes the number of available FSs. The available bandwidth for one FS is 12.5 GHz in this work.

• ν k r : Configuration consisting of k working paths and a backup path to serve the request r.

• µ k r,d : Generated path k from d to s r .

• Ψ + v /Ψ - v : Set of outgoing/incoming links for node v ∈ V. The Variables in ILP models for CDP are presented as follows.

• p k ra ∈ {0, 1}: Equals 1 if link a is used by the path k for request r.

• Λ k rd ∈ {0, 1}: Equals 1 if DC d is used as the end node of path k for request r. • α k rz ∈ {0, 1}: Equals 1 if the path k of r goes through DZ z. • R c r d ∈ {0, 1}: Equals 1 if content c, which is required by request r, is placed at DC d. • Φ k rm ∈ [0, |S|]:
The number of FSs served for working/backup path w/B of request r with modulation format m.

• w k r ∈ {0, 1}: Equals 1 if the k-th path is used for request r. w 1 r and w |k r | r equal 1, as they are chosen as the first working path, and backup path, respectively.

• ξ i r ∈ {0, 1}: Equals 1 if the number of working paths is i for request r, where the

integer i ∈ [|k r | -1]. • Φ k ra ∈ [0, |s|]:
Integer variable denoting the assigned FSs on arc a for the k-th path of the request r.

• g k r ∈ [0, |S| -1]: Integer variable denoting the assigned starting FS index of path k for request r.

• β kk ′ r ∈ {0, 1}: Equals 1 if g k r is smaller than g k ′ r for request r.

• β kk ′ rr ′ ∈ {0, 1}: Equals 1 if g k r of request r is smaller than g k ′ r ′ of request r ′ .
• γ kk ′ r ∈ {0, 1}: Equals 1 if two paths of the same request r have any common link.

• γ kk ′ rr ′ ∈ {0, 1}: Equals 1 if two paths, k of r and k ′ of r ′ , have any common link. • ∆ ∈ [0, |S|]: Maximal index of the occupied FSs.

ILP Formulations

The studied disaster protection problem can be formulated by the following ILP, namely CDP ILP.

min θ 1 • ∑ a∈A ∑ r∈R ∑ k∈[|k r |] Φ k ra + θ 2 • ∆ (4.1) s.t. Constraints (4.2)-(4.30).
In the objective function, the first term calculates the total spectrum usage on all the links of all the paths, and the second term denotes the MOFI. Each link may exist FS fragments between any two assigned continuous FSs due to the spectrum continuity and spectrum contiguity. The MOFI, i.e. maximal occupied FS index, measures the load balancing of a network. In a healthy network, the MOFI of each link should be as even and small as possible. An un-balanced distributed MOFI would make the network at risk of node and link congestion under small traffics, and thus lower the transmission capacity of this network. In the rest of this work, we also use spectrum utilization referring to the objective. θ 1 and θ 2 are two adjustable weights. The constraints for CDP ILP can be divided into six parts, DC assignment and content placement constraints

1) DC assignment and content placement constraints

∑ d∈D Λ k rd = w k r , ∀k, ∀r (4.2)
Constraints (4.2) guarantee each DC can only be assigned for the working/backup path for once.

2 ≤ ∑ d∈D R c r d ≤ |k r |, ∀r (4.3)
Constraints (4.3) give the lower and upper bounds on the number of content storage DCs.

∑ k∈k r Λ k rd ≤ R c r d , ∀r, ∀d (4.4)
Constraints (4.4) assure that these DCs are different from each other so that the DZdisjoint paths can be generated.

2) Flow-conservation constraints

∑ a∈Ψ + v p k ra -∑ a∈Ψ - v p k ra = ⎧ ⎪ ⎨ ⎪ ⎩ w k r , v = s r -Λ k rv , v ∈ D, ∀r, ∀k 0, otherwise (4.5)
Constraints (4.5) generate working paths and backup path through flow conservation. Specifically, the outgoing flow and incoming flow are equal for each content fragment, unless it is a destination (DC) node, which has an only incoming flow, or requesting node, which has only outgoing flow.

3) Disaster-zone-disjoint path constraints

α k rz ≤ ∑ a∈z p k ra , ∀r, ∀z, ∀k (4.6)
α k rz ≥ p k ra , ∀r, ∀z, ∀a ∈ z, ∀k (4.7)
Constraints (4.6)-(4.7) determine whether the working paths and backup paths are affected by each DZ. Specifically, α k rz equals 1 if any path using any link(s) is affected by DZ z.

∑ k∈k r α k rz ≤ 1, ∀r, ∀k, ∀z ∈ {x|x ∈ Z, x / ∈ z r } (4.8)
Constraints (4.8) ensure that the working and backup paths of the same request are generated as DZ-disjoint (except z r ). Note that the failure of z r would absolutely block the requests with s r . In this case, the request will be removed from our input request list directly, since it results in no protection solution.

4) Modulation adaption constraints

∑ a∈A d a • p k ra ≤ h m + h max • (1 -b k mr ), ∀r, ∀m, ∀k (4.9)
∑ m∈M b k mr ≤ w k r , ∀r, ∀k (4.10)
Φ k r = ∑ m∈M Φ k mr , ∀r, ∀k (4.11)
Φ k mr ≤ b k mr • |S|, ∀r, ∀k∀m (4.12)
Constraints (4.9) guarantee that the modulation format is selected with the maximum transmission reach for each path. Note that the path longer than h max cannot be generated. Constraints (4.10) ensure that only one modulation format can be assigned for each path. Constraints (4.11) give the FS assigned for each request. Constraints (4.12) guarantee that no FS is assigned for the non-selected paths or none-selected modulation formats.

5) Adaptive multi-path routing constraints

p k ra ≤ w k r , ∀r, ∀a, ∀k (4.13
)

|k r |-1 ∑ i=1 w i r = |k r |-1 ∑ i=1 i • ξ i r , ∀r (4.14)
|k r |-1 ∑ i=1 ξ i r = 1, ∀r (4.15)
w 1 r = w |k r | r = 1, ∀r (4.16)
w k r ≥ w k+1 r , ∀r, ∀k ∈ [|k r | -2] (4.17)
Constraints (4.13) prohibit the path generation if the k-th path is not selected. Constraints (4.14) and (4.15) indicate the number of working paths for the request. Constraints (4.16) assign the first path as the working path, and the last path as the backup path. Constraints (4.17) ensure that the paths with less index are to be preferred.

∑ m∈M Φ k rm • T m + (1 -w k r ) • ϕ r ≥ ϕ r • ∑ i∈[|k r |-1] ξ i r i , ∀r, ∀k (4.18)
Constraints (4.18) ensure that the total FSs assigned on the working/backup paths are sufficient to serve the request, in which each path carries the same transmission rates for the request r.

Φ k ra ≤ p k ra • |S|, ∀r, ∀k, ∀a (4.19)
Φ k ra ≤ Φ k r , ∀r, ∀k (4.20)
Φ k ra ≥ Φ k r -|S| • (1 -p k ra ), ∀r, ∀k, ∀a (4.21)
Constraints (4.19)-(4.21) calculate the total FS on each link for each request.

6) Spectrum allocation constraints

p k ra + p k ′ ra -1 ≤ γ kk ′ r , ∀r, ∀a, ∀k, k ′ , k > k ′ (4.22) γ kk ′ r = γ k ′ k r , ∀r, ∀k, k ′ , k > k ′ (4.23) p k ra + p k ′ r ′ a -1 ≤ γ kk ′ rr ′ , ∀r > r ′ , ∀a, ∀k, ∀k ′ ∈ k r ′ (4.24) γ kk ′ rr ′ = γ k ′ k r ′ r , ∀r > r ′ , ∀k ∈ k r , ∀k ′ ∈ k r ′ (4.25)
Constraints (4.22)-(4.25) indicate whether any two paths have any common link.

β kk ′ r + β k ′ k r = 1, ∀r, ∀k, k ′ , k > k ′ (4.26)
β kk ′ rr ′ + β k ′ k r ′ r = 1, ∀r > r ′ , ∀k ∈ k r , ∀k ′ ∈ k r ′ (4.27)
Constraints (4.26) and (4.27)) compare the starting index of FSs between any two paths.

g k r + Φ k r ≤ ∆, ∀r, ∀k (4.28)
Constraints (4.28) imply the maximum index of occupied FSs.

g k r + Φ k r -g k ′ r ≤ |S| • (2 -γ kk ′ r -β kk ′ r ), ∀r, ∀k, k ′ , k ̸ = k ′ (4.29) g k r + Φ k r -g k ′ r ′ ≤ |S| • (2 -γ kk ′ rr ′ -β kk ′ rr ′ ), ∀r, r ′ , r ̸ = r ′ , ∀k ∈ k r , ∀k ′ ∈ k r ′ (4.30)
The spectrum conflict occurs if any two paths have any common link. Then, based on the Starting Slot Assignment principle, which assigns the starting FSs to the demand, constraints (4.29) avoid spectrum conflict among the paths of the same request, and constraints (4.30) avoid spectrum conflict among the paths of different requests. The spectrum contiguity is ensured by setting a contiguous range of FSs and for each path.

Computational Complexity

Heuristics for CDP and M-CDP

To improve the scalability in the scenarios with large requests, we propose a heuristic algorithm to solve the adaptive path generation, and spectrum allocation. We then design a backtracking method to optimize the objective by minimizing the cost of each request path by path, forming the heuristic algorithm called heuristic for CDP (HCDP). Furthermore, we notice that the content storage space is of minimum if the number of paths is set as its maximum. Thus, we propose another maximum-CDP, namely M-CDP, to further reduce the content storage space. Note that if not indicated specifically, all the variables in this part are consistent with the Section 4.4.

The procedure of HCDP is explained in Fig. 4.2. For each request, we use k-shortest routing from the source node to each DC. We select the path with the minimum cost as the first path and then delete the DZ-joint links and nodes from the topology. The rest paths are generated with the same means till there is no DC that can be routed. For each combination with more than two paths, we choose the one with minimum cost and the one with maximum paths as the configurations of CDP and M-CDP, respectively. After we configure all the requests, we then use the color-algorithm-based conflict graph to allocate the spectrum for them. 4.1 uses three steps to solve the problem. At first, we generate the solution set request by request based on the given k r and then select the initial solution with minimal cost of each request. It is a greedy algorithm, shown in lines 2-22. Next, we use a coloring algorithm to generate a conflict graph for all the paths based on the initial solution. Then, we assign the spectrum usage based on the conflict graph, shown in lines 23-25. Finally, we backtrack the generated solution set to find whether there is a better solution with less total cost, shown in lines 26-39.

Line 1 initializes all the variables and sets. Line 3 sets nodal degree as the upper bound of the number of paths. Lines 5-6 update the network topology by removing the DZ-joint node(s) and link(s) of the former generated path, such that the next generated path is DZ-disjoint. Lines 7-8 compute the shortest path from each DC with required content c r (d ∈ D r ) to the source node. Lines 9-11 assign the modulation format for the path with as the higher transmission rate as possible. Line 12 calculates the cost for each path. The cost of the path is the sum of spectrum usage, shown as

cost r p = ( ∑ a∈A p k ra • Φ k r ) (4.32)
where p k ra equals 1 if link a is used by path k, and Φ k r is the number of FSs reserved for the k-th path of request r.

Lines 13-14 select the path with minimal cost as the working path for the request r and the corresponding DC d as the primary DC and put the path into the path set k r . Lines 15-19 generate the paths as many as possible configurations for each request. We regard every succeeded generation with more than two paths as one candidate configuration since it can offer complete path protection. The value k -1 is the number of working paths of the configuration ν k r . Then, we calculate the cost of each configuration and select the best one as the solution for the request. The cost for one configuration is computed by Eq. (4.33).

cost r,ν con f = ∑ k∈ν k r ∑ a∈A p k ra • Φ k r (4.33)
where p k ra equals 1 if link a is used by k-th path of configuration ν k r , and ν k r is a configuration with |k| generated paths for request r.

Lines 23-25 generate conflict graph to assign the FSs [START_REF] Wu | On the distance spectrum assignment in elastic optical networks[END_REF]. The conflict graph is decomposed based on a coloring algorithm, whose details can be referred to [START_REF] Wu | On the distance spectrum assignment in elastic optical networks[END_REF]. Lines 26-27 calculate the total cost and find the link with the MOFI. Similarly, the total cost can be expressed in Eq. (4.34).

cost total = θ 1 • ( ∑ a∈A p ra • Φ k r ) + θ 2 • ∆ (4.34)
Although it may achieve minimal spectrum usage for each request, it may not be the best solution for the entire network, especially for the MOFI. Also, it is of large if At least one path can be found then [START_REF] Bao | Adaptive path splitting based survivable virtual network embedding in elastic optical networks[END_REF] Select the path from d to s r with the minimal cost as the k-th path (noted as

p k r ), k r ← k r ∪ {p k r }, µ k r,d ← 1; 15 if k ≥ 2 then 16
Generate a new candidate configuration ν k r ;

17 Set p k r as the backup path and the others in k r as working paths; probability that the selected configuration is at the same cost as other candidate configurations. Therefore, Line 28 finds the link(s) of the MOFI. Lines 29-39 give the descent method for total cost by regenerating the paths before it fails until a preset number of times. The regeneration principle is to avoid using the link(s) of the MOFI, such that the spectrum usage can remain the same and the MOFI would be reduced. Note that there exists a Ping-Pong effect, e.g., the MOFI alternates to occur in a few specific links in every iteration, and yet the cost still remains the same. To avoid such a situation, we use F max as the maximum failure times to limit the backtracking process.

18 |k r | ← k; ∀k ′ ∈ [k], Φ k ′ r ← ⌈ Φ ¯k′ r k -1 ⌉;
In Algorithm 4.

O(F max • |R| • |D| • |A| • (|R| • |D| • |V| • |M| • log |A| + |R| • |K| log(|R| • |K|)))
, which is also the computational complexity for Algorithm 4.1.

Maximum-CDP

We notice that there exists a trade-off between content storage space and spectrum usage. For a content storage space of l, k working paths can reduce the content storage space on each DC to l k . However, each additional path may also have more hops/links than the former one, then the FSs overhead on the additional path is more than reduced FSs on the backup path. As a consequence, the spectrum usage may not be optimal for M-CDP. Therefore, we design M-CDP to optimize content storage space, aiming to serve the requests with as many paths as possible.

To generate M-CDP, we can simply remove lines 15-19 of Algorithm 4.1 and replace line 22 with:

• Set p k r as the backup path and the others in k r as working paths;

Φ k ′ r ← ⌈ Φ ¯k′ r |k r | -1 ⌉;
• Calculate the cost for the candidate configuration using Eq. (4.33);

Simulations and Performance Evaluations

In this section, extensive simulations have been done to assert the performance of the proposed CSS-based CDP protection schemes. we first compare the system performance between CDP and DP, using ILP for small-scale requests. Then, we study the efficiency of the HCDP and its gap to the optimal solution computed by the ILP model. Next, for a large scale of requests, we evaluate the system performance by using the heuristic algorithm proposed for DP and different CDP schemes respectively. The simulations are conducted for the different number of available DC locations and number of replicas per content, i.e. K. The M-CDP with as many as possible |k r | is also validated. At last, to assert the performance of storage space, we assume the total size of the original content data is normalized as 1. We assume the content is first divided into 10 parts, and then encoded to at most 10 × K fragments via a rateless coding [START_REF] Anglano | Exploiting rateless codes in cloud storage systems[END_REF], where K is the number of assigned DCs per content. Note that the overall content storage space depends on the results of CDP, and 10 × K fragments is the upper bound of the content storage space. Thus, in the traditional mirrored storage system, the storage space for each content equals K.

Simulation settings

We • Spectrum utilization of CDP, DP, and M-CDP (computed by using the proposed heuristic algorithms) for large scale of requests , when varying the number of available DC locations, i.e. |D|, and the number of DCs per content, i.e. K;

• Content storage space for different CDP, DP, and M-CDP;

• Analysis on weights using ILP with 5 DCs.

The topologies are shown in Fig. 4.3. It can be seen that NSFNET is a low-connected network, while COST-239 is a dense network with higher connectivity, and US Backbone network is even denser but with low connectivity. As disaster prediction is still a critical issue to be addressed, we adopt the disaster zones used in the previous studies [START_REF] Ju | Optimization of Protection Schemes for Next Generation Optical Networks (Optimisation de la Protection des Réseaux Optiques de Nouvelle Génération[END_REF] [55] [START_REF] Habib | Design of disaster-resilient optical datacenter networks[END_REF], which are generated randomly with a range up to 170 km [START_REF] Weems | How far is far enough[END_REF]. Each DZ involves the group of affected nodes and links. The simulation parameters for different scenarios are set as follows. In NSFNET: 1) 5 available DC locations at nodes 2, 5, 6, 9 and 11; 2) 4 available DC locations at nodes 2, 5, 9 and 11. In COST239: 1) 5 available DC locations at nodes 1, 2, 7, 8 and 11; 2) 4 available DC locations at nodes 1, 2, 7 and 8. In US Backbone network: 1) 8 available DC locations at nodes 1, 7, 9, 12, 14, 19, 21 and 28; 2) 6 available DC locations at nodes 1, 7, 14, 19, 21 and 28. These DC locations are chosen with the shortest distance to the requesting nodes on average. Then, to evaluate the disaster resilience performance of EO-DCNs with CSS, we compare different CDPs with DP [START_REF] Ju | Optimization of Protection Schemes for Next Generation Optical Networks (Optimisation de la Protection des Réseaux Optiques de Nouvelle Génération[END_REF] [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF]. We consider the static scenarios, where the requests are randomly generated with 10 contents, and the required transmission rate is randomly generated following uniform distribution among (0, 125 Gbps]. Each link is set with a maximum of 300 FSs to carry the traffic. For simplicity, the weights of the objective, i.e. the weighted sum of spectrum usage and MOFI, are set as the same value, i.e. θ 1 = θ 2 = 1, except in the subsection Analysis on Weight. To ease the readability, we use spectrum utilization in the simulations to refer to the objective aforementioned. We also set F max as 100 in the HCDP.

Validation of Efficiency of the HCDP Compared with ILP

To verify the efficiency of the HCDP, we conduct simulations under small traffic demands (the number of requests varies from 10 to 40) with both the ILP model and the HCDP in NSFNET and COST239 networks, while the execution time is limited to 10800s. The results are summarized in Table 4.2. We assume that in the NSFNET network there are 3 DCs with 5 available locations (at nodes 2, 5, 6, 9, and 11) per content, and in the COST239 network, there are 3 DCs with 5 available locations (at nodes 1, 2, 7, 8 and 11) per content.

Table 4.2 shows the solution of total spectrum utilization (Objective in the table) and computation time of ILP and HCDP. Due to the high computational complexity, the joint ILP model requires in total 10800s for more than 20 requests in the NSFNET network, while that is 10 in the COST239 network. The ILP model cannot solve the problem once the number of requests scales 40 within 10800s. It can be seen that the execution time in the HCDP is negligible. However, the introduced gap is a bit high in -No feasible ILP solution is obtained after 3 hours or exhausting all the memory.

the NSFNET for the HCDP at 10, because the DC assignment and content placement are pre-determined and solved separately. For a low-connected network, the DC assignment and content placement severely impact the spectrum utilization. However, it can also be noticed that the solution of the HCDP is much closer to that of the ILP in the COST239 network. As the number of requests increases to more than 10, ILP cannot solve the problem to optimality, let alone to get a near-optimal solution. The computation is more complicated in a dense and high-connected network. Thus, the performance of HCDP is even better than that of ILP.

Validation of CDP Compared with DP for Small-Scale Instances (Using ILP)

Let us then investigate the spectrum utilization of CDP compared with DP for smallscale instances (the number of requests varies from 10 to 40). We assume that 3 DCs with 5 available locations (at nodes 2, 5, 6, 9, and 11) per content in the NSFNET network, and 3 DCs with 5 available locations (at nodes 1, 2, 7, 8, and 11) per content in the COST239 network.

As shown in Fig. 4.4(a) and Fig. 4.4(b), performances of the CDP scheme are better than the traditional schemes, the spectrum utilization is improved. The reduction of spectrum utilization is up to 21.6% in NSFNET. Such improvement is because the proposed CDP scheme allows the multiple DZ-disjoint working paths generation, and FSs allocated for the backup path to protect one working path are reduced at least by half. The reduction of spectrum utilization in the COST239 network for CDP can also be observed. Note that in some cases, the MOFI is worse for the CDP. Compared to the DP, the CDP allows less FS usage for each request by sharing the traffic on multiple paths. However, sometimes it will cause the over utilization of the links adjacent to DCs. Consequently, the MOFI on these links may be higher for CDP when the number of requests varies from 10 to 40. Even with the cons, the CDP still chooses the solution DP CDP with multiple working paths, because the overall spectrum utilization is less, as shown in Fig. 4.4(a).

Validation of CDPs Compared with DP for Large-scale Instances (Using HCDP)

To further explore the performance of CDP, we use heuristics to evaluate DP, CDPs, and M-CDP on the situation with a large scale of requests in the networks of NSFNET, COST239, and US Backbone network, where the number of requests is up to 400. The scenarios are with the different number of available DC locations and K. Note that the number of requests is from 50 to 200 in Fig. 4.5(b), because the required bandwidth beyond the maximum transmission capacity in some links under this scenario, when the number of requests is more than 200. Due to the same reason, some points cannot be generated in Fig. 4.5(a), i.e. K = 3 and number of requests is 400. Note that the US Backbone network is a much denser network with a shorter average link distance compared to NSFNET and COST239. Also, with more available DCs, the requests are provisioned with shorter path lengths, thus with higher modulation formats. Therefore, the number of the provisioned requests can reach 400. However, the total spectrum utilization for all links is much higher since the number of links is larger compared to other networks.

As shown in Fig. 4.5(a) and 4.5(b), compared with DP, the performance improvement of CDP is small in NSFNET, because in such a low-connected network, the number of paths that can be generated for most nodes is no larger than 2, and the principle on disaster resilience also exacerbates this issue. These results that most requests are provisioned with one working path and one backup path. Thus, the solutions of CDP and DP tend to be the same, as well as the spectrum utilization. However, the performances are quite different in COST239 network, as demonstrated in Fig. 4.6(a) and 4.6(b). This is because the connectivity of the COST239 network is high enough to support multi-path routing, where the number of the paths is up to 5. As a consequence, CDP outperforms the others, since adaptive multi-path routing shows its superiority. Similar significant improvement can also be observed in the US Backbone network, whose results are plotted in Fig. 4 obtained with large K and 8 available DC locations. With more DCs, it becomes easier for the CDP to find more appropriate DCs locations for each request, which can significantly promote the quality of the generated routing paths to reduce the spectrum usage. While reducing the number of DCs will degrade the quality of the generated routing paths. Therefore, we can conclude that the advantages of the CDP are more evident in the high-connected networks with more available DCs. However, M-CDP is worse than DP in these scenarios. The reason is that the number of paths is too large, and the cost for the 4-th or 5-th path is much larger than the formerly generated paths for having more routing hops. Thus, the extra cost is bigger than the reduced spectrum resource reserved on the backup path. A trade-off between the number of paths and spectrum utilization can be observed. We will discuss it in the next subsection. The improved spectrum utilization is at most from K = 3 to K = 4 in Fig. 4.5(a). We also notice that the spectrum utilization of the same K is better with more DC locations, in both NSFNET and COST239. It demonstrates the DC locations also have a significant impact on the system performance.

Analysis on Content Storage Space

We then give the content storage space performance based on all DP, CDP, and M-CDP varying different number of DCs with 5 available locations of nodes 2, 5, 6, 9, and 11 in NSFNET, and at nodes 1, 2, 7, 8 and 11 in the COST239 network, respectively. In Fig. 4.8 (a) and (b), CDP also shows the superiority on storage space, and the storage space is cut up to 14.3%, especially in the COST239 network. With the normalized storage space, the average storage space per content for a traditional storage system is K, i.e. number of DCs. For the CSS, it only depends on the potential source nodes. Besides, the scenario with a small scale of requests can be seen as the targeted content provisioning applications, in which the content is only supplied for a small part of the nodes in the network due to the concerns of copyright, cost, etc. Thus, the proposed systems achieve lower storage space in such a scenario. As request number increases in the NSFNET network, the even distribution of requests tends to traverse all network nodes, and consequently, storage space will grow to serve the request with |k r | = 2, i.e. only two paths can be generated due to disaster resilience consideration. Therefore, the storage space of the CSS tends to have the same storage space as the conventional one in Fig. 4.8 (a). However, the nodal degree in the COST239 network is large enough, in which the minimum |k r | is 3. Thus, the CDP in such a situation allows a storage space reduction up to 14.3%, and its improvement keeps existing as the number of requests increases. Furthermore, M-CDP achieves the least storage space with a reduction up to 67.8%, because more working paths allow less spectrum resource split for each path and less storage space needs for each DC. Hence, M-CDP with larger |k r | can cut more content storage space. However, as discussed in the last subsection, the decrement of the content storage space in M-CDP comes with the price of high spectrum resources, while CDP nicely balances the spectrum utilization with substantial storage space saving.

Analysis on Weights

We now investigate the impact of different weights, i.e., θ 1 and θ 2 , in the situation with 20 requests using ILP. The parameters of the networks are set with 5 DCs at nodes 2, 5, 6, 9, and 11 in the NSFNET network, and at nodes 1, 2, 7, 8, and 11 in the COST239 network, respectively. θ 1 weights the overall FSs usage (FS total ), and θ 2 weights the MOFI. Considering FSs usage is usually dozens of times of MOFI, we then change the ratio of θ 1 and θ 2 varies 0 : 1, 0.1 : 1, 0.5 : 1, 1 : 1, 1 : 0.5, and 1 : 0, and calculate the objective, FS usage, and MOFI of these solutions, to explore the performances under different weightings.

As shown in Table 4.3, we can see that the optimizations of single-objective, i.e. θ 1 = 0 and θ 2 = 0, cause either high MOFI or high FS usage in both topologies. Note that for θ 2 = 0, the MOFI is of the maximum of the link capacity, i.e. 300 FSs. Because it is not optimized in the objective function. For the joint optimization, although the objectives are different, the FS usage and MOFI remain the same value for rest weights combinations in NSFNET. It shows the obtained solutions do not differ from each other, because the available routes from the source node to the assigned DC are few in such a sparse network, and it is easy to get the optimal solution for the combination of each weight. Thus, these solutions tend to get the same output. While in COST239 network, as θ 1 : θ 2 increases from 0.1 : 1 to 0.5 : 1, the FSs usage decreases and MOFI increases. Then, the solutions remain the same for other weight ratios. Such a change is consistent with the weights change.

Conclusion

In this chapter, we proposed a novel disaster protection scheme in EO-DCNs leveraging CSS and adaptive multi-path routing. Our protection scheme proposes to guarantee 100% disaster resilience with near-optimal spectrum utilization and substantial content storage space saving for the first time, which allows service provisioning with adaptive multi-path routing. In CDP, each content is jointly encoded via rate-less code, which is then distributed on no-less than three DCs located in different DZs. To jointly minimize the spectrum usage and MOFI, we formulated CDP as an ILP and also proposed a fast heuristic algorithm. To improve further the system performance of content storage space, we then develop M-CDP to generate a maximal number of working paths for each request. At last, we evaluated and analyzed CDP and M-CDP via simulations. Simulation results confirm that the proposed protection scheme CDP outperforms its counterpart by saving up to 21.6% spectrum utilization and 14.3% content storage space. CDP shows its superiority, especially in a densely connected network.

Introduction

The rapid development of a variety of Internet-based applications, especially high definition video streaming, video-on-demand services, etc, are driving exponential growth of the data transmission for current optical networks. The demand for flexible and scalable network function deployment has also aroused for the emerging services with huge bandwidth requirements. Network function virtualization (NFV) thus provides virtualization methods that enable the network functions to be executed by generic hardware instead of dedicated middleboxes [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF]. Hence, the service providers (SPs) can accelerate the launch of new services by using NFV more effectively and adaptively. Typically, SPs deploy network services at DCs utilizing virtual network functions (VNFs) due to long-term economic concerns, where several types of VNFs are chained together to provide a network service, namely service function chains (SFC) [START_REF] Li | Gnn-based hierarchical deep reinforcement learning for nfvoriented online resource orchestration in elastic optical dcis[END_REF]. A video streaming service SFC, for instance, is an ordered set of VNFs, including the network address translator, firewall, traffic monitor, video optimization controller, and intrusion detection prevention system [START_REF] Huin | Energy-efficient service function chain provisioning[END_REF]. Therefore, NFV-based service deployment is typically considered in inter-datacenters networks due to the enrichment of commodity servers, storage, and switches in DCs [START_REF] Li | Gnn-based hierarchical deep reinforcement learning for nfvoriented online resource orchestration in elastic optical dcis[END_REF]. The VNFs are then usually hosted at the physical machines (PMs) at datacenters (DCs), and the DCs are interconnected with elastic optical networks (EONs) to support flexible and variable data transmission. Such a network forms the elastic optical interdata center networks (EO-DCNs), as shown in Fig 5 .1. EO-DCN has demonstrated the potential to handle flexible data transmission and provide a platform for the deployment of a variety of network services and applications, with the finer granularity of frequency slot (FS), higher spectrum resource capacity in fiber, and flexible grid [START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF][START_REF] Luo | An online algorithm for vnf service chain scaling in datacenters[END_REF][START_REF] Wang | A survey on data center networking for cloud computing[END_REF]. However, large-scale network failures, such as natural disasters, pose a serious challenge to a wide range of Internet services. For instance, a submarine volcano eruption in the South Pacific destroyed an undersea cable in January 2022. It caused a nationwide web disconnection of Tonga from outside the world. It took 38 days to repair the undersea cable and reconnection the Internet [START_REF] Bbc | Tonga volcano: Internet restored five weeks after eruption[END_REF]. The interruption of networks is especially costly for the network services based on inter-datacenter networks. The downtime of each DC server may cause a loss of $ 9,000 per minute [START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF]. The report showed a cost of 402,542 dollars in the US and 212,254 dollars in the UK on average for a network failure [START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]. Naturally, resilience shows great importance to SFC provisioning, and any outage of VNF would break off the entire SFC. Thus, network resilience is regarded as the most significant factor for a majority of the business continuance professionals [START_REF] Cisco | 2021 global networking trends report: Business resilience special edition[END_REF]. There is a strong need to develop protection methods to ensure NFV-based connections against disaster failure.

In addition to the conventional network protections, VNFs must be mapped to physical nodes in order to serve user requests, and traffic should be routed through these VNFs, which creates the desired SFC [START_REF] Varasteh | Holu: Power-aware and delay-constrained vnf placement and chaining[END_REF]. Both VNF placement and SFC mapping problems have been classified as N P-hard [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF]. As a result, the path protection for SFC service is more challenging in placing the ordered VNFs for both the working and backup paths [START_REF] Cai | Disaster-resilient service function chain embedding based on multi-path routing[END_REF]. Also, different SFCs require various end-to-end delay constraints and bandwidth requirements. To the best of our knowledge, there is no disaster protection design for survivable SFC provisioning in EO-DCNs. In this work, we propose power-efficient and distance-adaptive disaster protection aiming to reduce spectrum usage and power consumption of EO-DCN. To maintain survivability, we leverage the anycast technique to provision the requests from the available DCs. The modulation format adaptation is also taken into consideration. We summarize the main contributions as follows:

• We propose a novel disaster protection scheme for SFC provisioning to jointly improve the spectrum and power efficiency of networks. The requests are provisioned by anycast technique from the available DCs. The explored problem also involves VNF placement, SFC provisioning, disaster-resilient path generation, modulation format adaptation, as well as spectrum allocation.

• We formulate the joint problem as an integer linear program (ILP) model, aiming to minimize spectrum usage and power consumption.

• To tackle instances of larger sizes, we then propose a heuristic algorithm. We first enumerate the possible configuration of each request. Then, the spectrum of each lightpath is allocated based on a color algorithm.

• Finally, we compare the proposed schemes to a traditional scheme using a single modulation format in NSFNET, and US Backbone networks. Simulation results demonstrate the significant performance improvement of the proposed methods compared with the traditional protection scheme.

The rest of the chapter is organized as follows. Section 5.2 first provides the related work. We then present the SFC provisioning disaster protection design in Section 5.3, which is then formulate by a joint ILP in Section 5.4. In Section 5.5, a heuristic algorithm is proposed to tackle scalability issue. Section 5.6 evaluates the performances via numerical simulations. Section 5.7 concludes this work.

Related Work

Disaster protection has been attracting increasing interest with the explosion of demand for cloud-based services. The disaster-resilient networking was first explored in [START_REF] Habib | Design of disaster-resilient optical datacenter networks[END_REF], where the authors brought together content placement, routing, and path protection in the WDM network. The disaster protection was then developed in EO-DCNs in [START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF] with the adaptive path generation, modulation format assignment, and content placement. Then, the authors in [START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF] compared the dedicated and shared path protection in EO-DCNs. A project, EU-funded COST CA15127 (RECODIS), was also formed to develop promising solutions to provide cost-efficient resilient communications in the presence of disaster-based disruptions [START_REF] Gomes | A survey of strategies for communication networks to protect against large-scale natural disasters[END_REF].

A brief overview of NFV can be found in [START_REF] Han | Network function virtualization: Challenges and opportunities for innovations[END_REF], which has explained the requirements and architectural framework, present several use cases, and discuss the challenges of NVF technology. Literature [START_REF] Mijumbi | Network function virtualization: State-of-the-art and research challenges[END_REF] has given a survey on NVF. A VNF placement and chaining has been investigated with power consumption and delay constraints in [START_REF] Varasteh | Holu: Power-aware and delay-constrained vnf placement and chaining[END_REF]. With the EO-DCN as the substrate network, several works of the SFC provisioning have been managed with network resource orchestration based on tree graph [START_REF] Zeng | Orchestrating tree-type vnf forwarding graphs in inter-dc elastic optical networks[END_REF], cost efficiency [START_REF] Wang | Cost-efficient virtual network function graph (vnfg) provisioning in multidomain elastic optical networks[END_REF], game-theoretic mechanism [START_REF] Chen | On incentive-driven vnf service chaining in inter-datacenter elastic optical networks: A hierarchical gametheoretic mechanism[END_REF], and deep reinforcement learning [START_REF] Li | Gnn-based hierarchical deep reinforcement learning for nfvoriented online resource orchestration in elastic optical dcis[END_REF]. As for network protection for resilient SFC provisioning, most of the works focus on the VNF failure or server failure [START_REF] Alleg | Joint diversity and redundancy for resilient service chain provisioning[END_REF][START_REF] Herker | Data-center architecture impacts on virtualized network functions service chain embedding with high availability requirements[END_REF][START_REF] Hmaity | Virtual network function placement for resilient service chain provisioning[END_REF][START_REF] Ishigaki | Deeppr: Progressive recovery for interdependent vnfs with deep reinforcement learning[END_REF][START_REF] Mohan | Resilient vnf placement for service chain embedding in diversified 5g network slices[END_REF]. Such failures are caused by the single link or node failure in the network, which have been demonstrated as not dealing with large-scale disaster failure [START_REF] Gomes | A survey of strategies for communication networks to protect against large-scale natural disasters[END_REF][START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF]. To the best of our knowledge, the only work of disaster-resilient protection design for SFC services was explored in [START_REF] Cai | Disaster-resilient service function chain embedding based on multi-path routing[END_REF], where the authors leverage the multi-path routing to reduce the spectrum usage with only the ILP model. No existing work with modulation format adaptation for disasterresilient SFC provisioning in EO-DCNs was found. The previous works have shown that modulation format adaptation can effectively increase spectrum efficiency. Thus, it is essential to explore disaster protection for distance-adaptive SFC provisioning in EO-DCNs. A scalable heuristic algorithm is also required to deal with large-scale instances.

4) Power consumption

The power consumption is mainly due to PM, BVTs, bandwidth variable optical cross-connects (OXCs), and optical amplifiers (OAs) [START_REF] Ju | Power-efficient protection with directed p-cycles for asymmetric traffic in elastic optical networks[END_REF][START_REF] Varasteh | Holu: Power-aware and delay-constrained vnf placement and chaining[END_REF][START_REF] Vizcaíno | Protection in optical transport networks with fixed and flexible grid: Cost and energy efficiency evaluation[END_REF]. We assume that each powered-on PM has the same power consumption on average. Data transmission components are related to the number of FSs. In this work, we assume a BVT is deployed at the DC of each lightpath in EO-DCNs, which is the path between two VNF-placed DCs. Thus, no power of BVT is consumed if two consecutive VNFs are placed at the same DC. The power consumption of OXCs and OAs also depends on the number of carried FSs. The detailed power model is described in Section 5.4.1.

5) Spectrum allocation

For each lightpath, the spectrum is allocated under the following principles. a)Spectrum continuity: Without spectrum conservation in this work, each link is assigned with the same FSs along the path. b)Spectrum contiguity: The FSs to be assigned for the request should be continuous for each path. c)Spectrum conflict: The spectrum allocation for each backup path is dedicated, in which each FS of each link cannot be assigned for multiple requests.

Joint ILP formulation

In this section, we formulate joint ILP model. For the sake of readability, we use ∀r, ∀k, ∀v, ∀a, ∀v ¯, ∀a ¯, ∀z, and ∀ f to denote ∀r ∈ R, ∀k ∈ K r , ∀v ∈ V, ∀a ∈ A, ∀v ¯∈ A ¯r, ∀v ¯∈ A ¯r, ∀z ∈ Z, and ∀ f ∈ F respectively. We also use ∀w ′ , ∀r ′ , and ∀r ̸ = r ′ to denote ∀w ′ ∈ W r , ∀r ′ ∈ R, and ∀r, r ′ ∈ R, r ̸ = r ′ respectively, if it is not indicated specifically. We further use uv and (u, v) to represent the link a with starting node u and ending node v for better expression. Similarly, (u ¯, v ¯) is also used to represent a virtual link. The network sets and parameters are presented as follows.

• G(V, A, D): Physical topology of EO-DCNs with physical node set V, physical link set A and DC set D.

• G ¯r(V ¯r, A ¯r): Virtual topology of of request r with virtual node set V ¯r, and virtual link set A ¯r.

• z ∈ Z: DZ set. Z ⊂ G contains the sets of links and nodes.

• f ∈ F : Set of VNFs.

• s ∈ S: Set of FSs on each link. |S| denotes the number of available FSs.

• r ∈ R: Set of requests r(V s r , C r , B r ), V s r , where V s r , C r and B r are source node, the required services, and the required bandwidth.

• C r : Set of services with the SFC with the corresponding delay requirement Ψ r .

• k ∈ K r : Set of path types of request r. We also use W and B to denote working path and backup path, respectively.

• N v : The adjacent node set of the node v.

• d a : The distance of the link a.

• m ∈ M: The available modulation level set, i.e., BPSK, QPSK, 8-QAM, and 16-QAM.

• h m : Maximum transmission reach at modulation level m, which is 9, 600, 4, 800, 2, 400, and 1, 200, in km for BPSK, QPSK, 8-QAM, and 16-QAM, respectively [START_REF] Chen | On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks[END_REF]. h max =9600 km.

• T m : The spectrum efficiency of BPSK, QPSK, 8-QAM, and 16-QAM are 12.5, 25, 37.5, and 50 Gbps per FS.

• P BVT m : The power consumption of BVT at modulation format m.

• P OXC v : The power consumption of OXC on node v.

• P OA a : The power consumption of EDFA on link a.

• Q f : The processing capacity of the VNF f .

• Q pm : The processing capacity of the PM.

• ψ v ¯/ ψ a : The processing delay of the VNF f and propagation delay of the link a, respectively.

The variables in ILP models are presented as follows.

• α rk z : The boolean variable that equals 1 if path k of request r is affected by DZ z (except z r ).

• l rk a : The boolean variable that equals 1 if link a is used by path k of request r, and 0 otherwise.

• e rk vv ¯: The boolean variable that equals 1 if virtual node (VNF) v ¯for the path k of request r is mapped to the physical node v, and 0 otherwise.

• e vv ¯: The boolean variable that equals 1 if VNF v ¯is mapped to the physical node v, and 0 otherwise.

• g rk aa ¯: The boolean variable that equals 1 if virtual link a ¯for the path k of request r is mapped to the physical link a, and 0 otherwise.

• b rkm

a ¯: The boolean variable that equals 1 if virtual link a ¯for the path k of request r operates at modulation format m, and 0 otherwise.

• Φ rkm aa ¯: The number of FSs assigned on link a of virtual link a ¯for the path k of request r that operates at modulation format m.

• Φ rkm a ¯: The number of FSs assigned on virtual link a ¯for the path k of request r that operates at modulation format m.

• Φ rk aa ¯: The number of FSs assigned on link a of virtual link a ¯for the path k of request r.

• Φ rk a ¯: The number of FSs assigned on virtual link a ¯for the path k of request r. • ϕ rk a ¯: The boolean variable that equals 1 if virtual link a ¯is not mapped to any physical link.

• n k v f : The number of VNF f of path type k on node v.

• n v pm : The number of powered-on PMs on node v.

• γ rka r′ k ′ a ¯′ : The boolean variable that equals 1 if the virtual link a ¯of the path k for request r has the common physical link with the virtual link a ¯′ of the path k ′ for request r ′ , and 0 otherwise.

• x rk

a ¯: The starting FS index of virtual link a ¯of the path k for request r.

• β rka r′ k ′ a ¯′ : The boolean variable that equals 1 if x rk a ¯is smaller than x r ′ k ′ a ¯′ , and 0 otherwise.

Power model of EO-DCNs

In this subsection, we provide the power model of BVTs, OXCs, and OA.

The power consumption of BVT is related to transmission rate in terms of modulation format for 16-QAM, 8-QAM, QPSK, and BPSK, respectively [START_REF] Vizcaíno | Protection in optical transport networks with fixed and flexible grid: Cost and energy efficiency evaluation[END_REF]. The power model of each FS at modulation format m is expressed as follows

P BVT m = 1.683 • TR + 91.333 (5.1)
where TR is the transmission rate per FS in Gbps.

The OXCs are deployed at each node, in which the power consumption depends on the nodal degree and the add/drop degree. On the ends of link (u, v), the BVT power model P OXC v can be expressed as follows

P OXC v = 85 • |N v | + 100 • β + 150 (5.2)
where N v is the nodal degree of node v, and β is the add/drop degree which assumed as 9 in this work.

The erbium-doped fiber amplifiers (EDFAs) are deployed as OAs on the span every 80 km. Each EDFA consumes 100 W for each directed link [START_REF] Vizcaíno | Protection in optical transport networks with fixed and flexible grid: Cost and energy efficiency evaluation[END_REF]. The power model of EDFA P OA a can be expressed as

P OA a = ⌊ d a 80 + 1⌋ • 100 (5.3)

ILP model

The studied disaster protection for SFC provisioning problem can be formulated by the following ILP

min θ 1 • Φ total + θ 2 • P total (5.4) s.t. Constraints (5.8)-(5.43)
The objective function aims to jointly minimize the weighted sum of total spectrm usage and power consumption for all the requests. θ 1 and θ 2 are adjustable weights. The first term represents the total FS usage of all the paths, denoted by the number of FSs, which is calculated by

Φ total = ∑ r∈R ∑ k∈K r ∑ a∈A ∑ a ¯∈A ¯r Φ rk aa ¯(5.5)
The second term is the overall power consumption with the unit of Watt. The overall power consumption consists of two parts, the power consumption of EON components P eon and the power consumption of PM at each DC P dc . P eon is expressed by

P eon = ∑ r∈R ∑ k∈K r ( ∑ a ¯∈A ¯r ∑ m∈M 2 • P BVT m • Φ rkm a ¯+ ∑ a∈A P OA a • Φ rk a |S| + ∑ v∈V ∑ u∈N v P OXC v • Φ rk vu |S| ) (5.6)
where the first term represents the power consumption for BVT on starting node of the virtual link. Note that no power is consumed for a virtual link if the two VNFs are placed at the same DC. The second term calculates the power consumption for EDFA on each physical link, and the last term denotes the power consumption for OXC for each physical node [START_REF] Vizcaíno | Protection in optical transport networks with fixed and flexible grid: Cost and energy efficiency evaluation[END_REF]. P dc is expressed by

P dc = ∑ v∈D P pm • n v pm (5.7)
where n v pm is the number of powered-on PMs on DC v, and P pm is the power consumption of each PM on average.

Constraints (5.8)-(5.9) determine whether the working paths and backup paths are affected by each DZ. Specifically, α rk z equals 1 if any path using any link(s) is affected by DZ z.

∑ k α k rz ≤ 1, ∀r, ∀z (5.10)
Constraints (5.10) ensure that the working and backup paths of the same request are generated as DZ-disjoint. Note that the failure that affects all the adjacent links of the source node s r , say z r , would absolutely block the requests with s r . Thus, the DZ set does not include z r for requests with s r .

2) VNF placement constraints

e rk vv ¯= 1, if v = v ¯= V s r , ∀r, ∀k (5.11)
∑ v∈V e rk vv ¯= 1, ∀r, ∀k, ∀v ¯(5.12)

Constraints (5.11) indicate that the virtual source nodes in the G ¯are mapped to the physical source nodes in the G. Constraints (5.12) guarantee the each replica of the VNF is installed at one node. Constraints (5.20) guarantee that the modulation format is selected with the maximum transmission reach for each lightpath. The lightpath is determined by virtual link a ¯, whose path length is the sum of the distances of the mapped physical links. The path length that is bigger than h max would lead to the optical signal not being received correctly. Constraints (5.21) ensure that only one modulation format can be assigned for each lightpath.

∑ r∈R e rk v f • B r ≤ n k v f • Q f , ∀v ∈ D, ∀ f , ∀k (5.33)
Constraints (5.33) ensure that sufficient VNFs are reserved for primary and backup VNFs of each request. Note that we assume in EO-DCNs each request, whose required bit rate ranges from 20 Gbps to 100 Gbps, is an aggregation of a batch of small demands from the same source node with the same services but usually requires a low bit rate (usually tens Mbps). Thus, each VNF of a request may need several instances to meet the bandwidth requirement. (5.39)

∑ k∈K r ∑ f ∈F n k v f • Q f ≤ Q pm • n v
The spectrum conflict occurs if any two paths have any common link. Then based on the Starting Slot Assignment principle, which assigns the starting FSs to the demand, constraints (5.39) avoid spectrum conflict among the paths of the same request. The spectrum contiguity is ensured by setting a contiguous range of FSs for each lightpath.

The common link(s) for the working path and backup path of the same request only exist if they are not affected by any DZ. Otherwise, such DZ would affect both the working path and backup path at the same time, and the protection cannot protect the service. Thus, constraints (5.36)-(5.39) can be ignored if all the arcs of the network topology are affected by at least one DZ, because the DZ-disjoint path generation has prohibited such a situation.

We then give the spectrum allocation for the paths of different requests.

Computational Complexity

The number of dominant variables and constraints in the ILP model are {O(|R| Line 16 removes the DZ-joint node(s) and link(s) of the generated working path from topology, such that the backup path can be generated as the DZ-disjoint from the working path. Lines 17-21 generate conflict graph for each lightpath. The conflict graph remarks all the lightpath pairs that have the common link(s). It is then used to allocate FSs for each lightpath by a color algorithm (detailed in [START_REF] Wu | On the distance spectrum assignment in elastic optical networks[END_REF]). Finally, line 22 computes the total cost by Eq. (5.45).

Simulations and Performance Evaluations

In this section, we conduct comprehensive simulations to analyze the performance for the proposed ILP model and heuristic. To the best of our knowledge, the up-to-date research on disaster protection for SFC-based services is the work in [START_REF] Cai | Disaster-resilient service function chain embedding based on multi-path routing[END_REF] using BPSK, which is used as benchmarks, named as SFC-DP, in the simulations. We set the same objective for a fair comparison. We also generate the heuristic algorithm for SFC-DP based on Algorithm 5.1. We name the proposed modulation format-assignment-based disaster protection for SFC provisioning as SFC-MADP. Thus, we compare the overall objective (sum of power consumption and spectrum usage) of the proposed SFC-MADP and conventional SFC-DP with both the ILP model and heuristic algorithm.

Simulation Settings

We use CPLEX 12.06 to solve the proposed ILP models on a server with 128 GBytes RAM. The simulations are conducted in two classical EO-DCN testbeds, NSFNET network (14 nodes, 44 directed links, 5 DCs, 14 DZs, average link length 1, 936 km, and [START_REF] Habib | Design of disaster-resilient optical datacenter networks[END_REF][START_REF] Ju | Disaster-resilient and distance-adaptive services provisioning in elastic optical inter-data center networks[END_REF][START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF]. We assume the replicas of each type of VNF are distributed at no more than 4 and 6 DCs at NSFNET and US Backbone networks, respectively.

Each directed link uses C-band that accommodates 358 FSs, i.e., |S| = 358. For simplicity, we assume the weights of the objective as the same value, i.e. θ 1 = θ 2 = 1. The requests are generated randomly with demanding node, and the required bit-rates are generated among [START_REF] Chatterjee | Routing and spectrum allocation in elastic optical networks: A tutorial[END_REF]100] Gbps. The SFC of each request is randomly generated among [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Alazemi | Fast and efficient network protection method using path pre-cross-connected trails[END_REF] VNFs with the delay requirement [0.1s, 15s]. The VNFs are summarized in Table 5.1 [START_REF] Luo | An online algorithm for vnf service chain scaling in datacenters[END_REF]. Each PM is deployed at DC and assumed with 384 CPU Cores, 768 GB RAM, and average power 695 Watt [98].

Validation of SFC-MADP Compared with SFC-DP (Using ILP)

We first investigate the performance of joint power consumption and spectrum usage for small-scale instances (varying from 10 to 100) in the NSFNET network and US Backbone network, respectively. As shown in Fig. 5.5, the performance of power consumption and FS usage for the proposed SFC-MADP are both better than the conventional SFC-DP. The reduction of the power consumption is up to 27.37% and 32.05% in NSFNET and US Backbone networks, respectively. The improvement is mainly acquired from the modulation format adaptation in the proposed SFC-MADP. A higherorder modulation format allows a higher spectrum efficiency for each lightpath, and consequently the lower FS usage. The power consumption of data transmission is also related to the carried number of FSs, where less power is consumed for BVTs, OXCs, and, EDFAs for the reduced FS usage. Therefore, the power consumption can be reduced largely.

The reduction obtained from the proposed method is larger in the US Backbone network. This is because the US Backbone network has more nodes and links but a denser topology than the NSFNET network, and it allows a more flexible configuration for all the requests and the variable modulation format selections. In addition, we notice that the FS usage is not positively related to the number of requests. For instance, solution, in which Gap is less than 4.54%. The execution time of the heuristic algorithm is negligible. However, the execution time for the ILP model is enormous. It is mostly caused by solving the spectrum allocation constraints. The possible lightpath configurations and corresponding spectrum allocation greatly reduce the ILP solving efficiency. On the contrary, the heuristic algorithm uses a coloring-based decomposition method to assign the FS for each lightpath. It should be pointed out that ILP may not solve the problem to optimality, for which a 3% relative optimality tolerance is set in CPLEX solver to ease the ILP solution. However, the results still show that the heuristic algorithm can acquire a comparable solution in a negligible execution time.

Validation of SFC-MADP Compared with SFC-DP (Using Heuristic)

We next validate the performance of SFC-MADP for large-scale instances (varying from 200 to 1000) in the NSFNET network and US Backbone network, respectively. Fig. 5.6 shows the proposed SFC-MADP also acquires a significant reduction in both power consumption and spectrum usage. The reduction of the power consumption is up to 27.85% and 29.83% in NSFNET and US Backbone networks, respectively, and the reduction of the FS usage is up to 53.56% and 29.83%, respectively. Similarly, the improvement is mainly acquired from the modulation format adaptation in the proposed SFC-MADP. The overall reduction of the proposed method gets larger with increasing requests. The results further prove the advancement of the proposed SFC-MADP in the scenario with large-scale instances.

Conclusion

In this chapter, we have proposed a novel disaster protection scheme for SFC provisioning in EO-DCNs. The sub-problems, including modulation format adaptation, VNF placement, SFC mapping, DZ-disjoint path protection, and spectrum allocation, are jointly solved by an ILP model and a fast heuristic algorithm. Our objective is to jointly minimize power consumption and spectrum usage. Compared with the existing method without modulation format selection, our scheme significantly improves the system performance subject to disaster resilience.

121

Chapter 6

Conclusions and Perspectives

Conclusions

This thesis has explored the network protection for EO-DCNs. Two different network failures are investigated, i.e. single link failure and disaster failure. The former one is the most common failure for the optical networks, and the latter one is a large-scale failure that may cause massive damages to numerous web-based services. For single link failure, we leverage directed p-cycle to address the issue of asymmetric traffic protection in EO-DCNs. The optimal solution of directed p-cycle protection is formulated by a joint ILP model in the way without candidate cycle enumeration, which significantly improves the computational efficiency compared to the ones with cycle enumeration as the input. The joint problem is tackled from the aspects of modulation format adaptation, directed p-cycle generation, power consumption reduction, and spectrum allocation. Two different CG approaches are also developed as the large-scale optimization tools to solve large instances. As for disaster failure, we propose adaptive dedicated path protection to maintain the robust of the end-to-content communications in EO-DCNs. A joint ILP model formulates the joint problem with the considerations of DC assignment, content partition and placement, adaptive working/protection paths computation, modulation adaption, as well as spectrum allocation. Similarly, a scalable heuristic algorithm is also developed for large-scale scenarios. Finally, this thesis investigates disaster protection for SFC provisioning in the NVF-embedded EO-DCNs, using the anycast technique to serve the requests from available DCs. This work aims to reduce spectrum usage and power consumption of EO-DCNs. Similarly, an ILP model is used to optimize the joint problem, considering VNF placement, SFC mapping, modulation format adaptation, and spectrum allocation, respectively. A fast heuristic algorithm is also proposed to solve the large-scale network request problem.

In chapter 1, we first report a brief background of current Internet traffic trends. We then provide an overview of the emerging EO-DCNs by presenting the core enabling technologies and enabling hardware of next-generation optical networks. Next, we point out that optical networks are facing serious threats from various network failures. Finally, we present an overview of the literature on p-cycle protection and disaster 123 protection in optical networks.

In chapter 2, we then discuss the subject of communications survivability in optical networks. Following that, the primary risks, the classic protection schemes, and network protection challenges are presented.

In chapter 3, we propose a novel directed p-cycle design method based on flow conservation and a compact modulation format adaptation in EO-DCNs. Three different ILP models formulate the joint problem in the way without candidate cycle enumeration. The problem involves the directed p-cycle generation, modulation format adaptation, power consumption reduction, and spectrum allocation. Then, to address the scaling issue, we propose time-efficient and performance-guaranteed methods leveraging CG techniques. The LEF-based directed p-cycle protection was found to be superior in simulations, saving up to 70.68% of the joint objective value of power consumption and spare capacity utilisation. In the case of large-scale traffic, two proposed CG techniques demonstrate near-optimal performance with hundreds of instances, as well as equivalent solutions with low execution time and high scalability.

In chapter 4, using CSS and adaptive multi-path routing, we develop a novel disaster prevention system for EO-DCNs. Our disaster protection strategy offers to ensure 100% disaster resilience with near-optimal spectrum usage and significant content storage space savings, allowing service provisioning with adaptive multi-path routing. Each content is jointly encoded using rate-less coding in CDP, and then dispersed among at least three DCs in separate DZs. We framed CDP as an ILP and provided a fast heuristic approach to jointly optimize spectrum utilization and MOFI. We then build M-CDP to generate a maximum number of working pathways for each request, in order to increase the system performance of content storage space even more. Finally, CDP and M-CDP were assessed and analyzed. The proposed protection method CDP beats its equivalent by saving up to 21.6% spectrum use and 15% content storage space, according to simulation results. The advantage of CDP is demonstrated, particularly in a densely connected network.

In chapter 5, we focus on disaster protection for SFC provisioning in EO-DCNs. The anycast technology and dedicated path protection are leveraged to guarantee disaster resilience. The requests are provisioned by several available DZ-disjoint DCs. Different from the work in chapter 4, the disaster-resilient SFC provisioning design needs to configure SFC and corresponding VNFs for each path, which are also the N P-hard problems. Thus, in addition to path generation, modulation format adaptation, and spectrum allocation, the problem also involves VNF placement and SFC provisioning. We aim to reduce the overall power consumption and spectrum usage for the interdatacenter networks. We next formulate the problem as an ILP model and a fast heuristic algorithm. Numerical simulation results show the advancement of the proposed scheme compared to the conventional one, saving up to 32.05% power consumption and 53.56% spectrum usage.

Future works

As we propose the enhanced survivability issue for EO-DCNs, there are still open challenges to be solved, and several future explorations to be done. They are summarized as follows.

Directed p-cycle for anycast-based services provisioning in EO-DCNs

The directed p-cycle protection in this dissertation focuses on the power and spare spectrum reduction of all the generated directed p-cycles. As the same to the conventional p-cycle designs, the working traffic is aware to be protected. Thus, the problem can be upgraded with the joint consideration of the RMSA problem for working paths in EO-DCNs. The anycast technology can also be implied to the EO-DCNs to serve the requests. For instance, each request is provisioned by one of the potential DCs, and all the working paths are protected by directed p-cycles. The modulation format assignment should be embedded for both working paths and directed p-cycles. A joint model can further improve the performance of the system.

Probability-based disaster protection in EO-DCNs

We have studied disaster protection based on the consideration of single DZ failure protection. As disaster prediction is still an open challenge, we assume each DZ is aware in the networks. Thus, to form a more practical model, a stochastic model for disaster occurrence can be used for disaster protection [START_REF] Agrawal | Network and risk modeling for disaster survivability analysis of backbone optical communication networks[END_REF][START_REF] Dikbiyik | Minimizing the risk from disaster failures in optical backbone networks[END_REF]. The distribution of disasters and their regions are estimated by a prediction model based on real-world data, and multiple disasters may occur simultaneously according to the occurrence probability. Therefore, all the requests are provisioned to maintain a certain block probability of threshold. The objective can be set as minimizing either the average block probability for each request or the network resources with a certain block probability. The key challenge is how to integrate the disaster protection design with a disaster prediction model.

Availability and reliability design for initialization of the hybrid underwater optical acoustic networks

Data explosion does not only exist in terrestrial scenarios, the increasing interest in ocean exploration also drives huge demand for marine wireless data transmission. The marine data, including sea surface temperature, ocean chemistry, currents, sea level, sea ice, and heat content, has reached petabyte size per year [START_REF] Li | Marine wireless big data: Efficient transmission, related applications, and challenges[END_REF]. It has shown the features of big data with the huge volume and high value [START_REF] Li | Marine wireless big data: Efficient transmission, related applications, and challenges[END_REF][START_REF] Liu | Initialization of hybrid underwater optical/acoustic network with asymmetrical duplex link[END_REF][START_REF] Lu | Highly-efficient data migration and backup for big data applications in elastic optical inter-datacenter networks[END_REF]. Over 4,000 buoys and floats with off-site links take daily measurements at the ocean surface as well as thousands of meters below. The emerging underwater wireless optical communications (UWOC) provides a solid solution for the urgent marine data transmission requirement. Naturally, network survivability in such a harsh environment is regarded as the most significant factor from these perspectives.

As for the marine scenarios, the various underwater applications urgently demand high speed and ecological communications. Conventional underwater wireless acoustic communications (UWAC) face the inherent defects of high propagation latency, low data rate, and high power consumption. The emerging UWOC can provide a strong capacity to carry the huge volume of data traffic, thanks to its high spectral efficiency and the great progress on hardware. Survivability for a harsh environment then focuses on the networking in underwater scenarios rather than the network protection on land, for the underwater wireless optical networks (UWONs) are still under underdevelopment. Thus, we mainly explore how the UWONs can be formed in the first place. We notice that initialization is a fundamental challenging task for the UWONs, but it is very often underestimated since the initialization technique has been developed for decades for terrestrial wireless radio frequency (RF) communications. We need to point out that the UWONs initialization cannot simply use the terrestrial technique due to the lack of GPS service and line-of-sight (LOS) communication mode. To this end, availability and reliability design is essential for initialization of the UWONs.

HCDP

Heuristic for CDP

HIS

Figure 1 . 1 :

 11 Figure 1.1: The Cisco Global IP Traffic Forecast [26].

Figure 1 . 2 :

 12 Figure 1.2: ITU-T grid.

Figure 1 . 3 :

 13 Figure 1.3: Fixed grid [36].

Figure 1 . 4 :Figure 1 . 5 :

 1415 Figure 1.4: Flexible grid [36].

Figure 1 . 6 :

 16 Figure 1.6: Examples for the spectrum of (a) O-OFDM; (b) Nyquist WDM; (c) TFP [91].

Figure 1 . 7 :

 17 Figure 1.7: Elastic optical path provisioning [53].

Figure 1 . 8 :

 18 Figure 1.8: Optical flow generated in a BVT and routed by a ROADM[34].

Figure 1 . 10 :

 110 Figure 1.10: Optical flows generated in an S-BVT and routed by a ROADM[34].

Figure 1 . 11 :

 111 Figure 1.11: Architecture of BV-OXC [20].

Figure 1 . 13 :

 113 Figure 1.13: Network disruptions rose sharply in March 2020, for both Internet service and cloud providers [101].

Figure 1 . 14 :

 114 Figure 1.14: Earthquake Hazards Map [84].

19

 19

Figure 2 . 1 :

 21 Figure 2.1: Network protection and restoration schemes[START_REF] Bao | Adaptive path splitting based survivable virtual network embedding in elastic optical networks[END_REF][START_REF] Habib | Design of disaster-resilient optical datacenter networks[END_REF][START_REF] Ju | Leveraging spectrum sharing and defragmentation to p -cycle design in elastic optical networks[END_REF][START_REF] Shen | Survivable elastic optical networks: survey and perspective[END_REF].

Figure 2 . 2 :

 22 Figure 2.2: Link protection.

Figure 2 . 3 :

 23 Figure 2.3: Shared and dedicated spectrum allocation of link protection.

Figure 2 . 4 :

 24 Figure 2.4: Path protection.

Connection 1 is from node 6 to node 3 with 4 FSs Connection 2 is from node 5 to node 2 with 2 FSsFigure 2 . 5 :

 4225 Figure 2.5: SBPP and DBPP.

Figure 2 . 6 :

 26 Figure 2.6: Backup path protection with 1 : 1 and n : 1 modes.

Figure 2 . 7 :

 27 Figure 2.7: p-Cycle protection.

Figure 2 . 8 :

 28 Figure 2.8: p-Cycle protection for on-cycle and straddling link failures.

Figure 2 . 9 :

 29 Figure 2.9: Directed p-cycle protection.

Figure 2 . 10 :

 210 Figure 2.10: Modulation format assignment of p-cycles.

Figure 2 . 11 :

 211 Figure 2.11: Directed p-cycle protection based on a rough upper bound.

Figure 2 . 12 :

 212 Figure 2.12: Average Number of Affected Requests per DZ [55].

Figure 2 . 13 :

 213 Figure 2.13: Backup path protection against single link failure and disaster failure.

FS index usage for each path 1 2 …path of r 2 Backup path of r 2 Figure 2 . 14 :Figure 2 . 15 :Figure 2 . 16 :

 222214215216 Figure 2.14: DEBPP against disaster failure.

Figure 3 . 1 :

 31 Figure 3.1: p-Cycle designs in 6-node topology with 3 traffic-loaded links. (a) 3 traffic-loaded links protected by undirected p-cycle and directed p-cycle. (b) Protection paths provided by directed pcycle. (c) Protection paths provided by undirected p-cycle.

Figure 3 . 2 :

 32 Figure 3.2: Directed p-cycle designs with the VRN, ILF, ALF, and LEF.

Figure 3 . 3 :

 33 Figure 3.3: Protection paths in the proposed directed p-cycle design and VRN.

. 10 ) 2 )

 102 Constraints (3.6) ensure each link can be used for directed p-cycle only in one direction. Constraints (3.7)-(3.8) guarantee the node on directed p-cycle must have one incoming on-cycle link and one outgoing on-cycle link. Constraints (3.9) indicate the root node should be on-cycle node, and constraints (3.10) indicate that only one root node can be assigned for each directed p-cycle. 52 Flow conservation constraints

  ) and(3.18) use variables u i a to indicate whether z i a is positive or negative. Constraints (3.19

. 33 )

 33 Constraints (3.25) and (3.26) indicate the links that can be protected by the directed p-cycles. Constraints (3.27)-(3.30) calculate the total number of FSs assigned on directed p-cycles. Constraints (3.31)-(3.33) guarantee the sufficient FSs are assigned for each directed p-cycle to protect the links with the traffic load.

. 45 )

 45 Constraints(3.41) require the flows only exist on on-cycle links. Constraints (3.42)-(3.44) leverage the intermediate variables p i v to eliminate the bi-linearities ∑ v∈V y i v • c i v for linearity. Note that p i v equals the number of on-cycle nodes if the node v is the root node of directed p-cycle i, and 0 for other nodes. Constraints (3.45) indicate the flow conservation for each node.

) Constraints ( 3 .

 3 [START_REF] Huang | Distributed protocol for removal of loop backs with asymmetric digraph using gmpls in p-cycle based optical networks[END_REF] and(3.47) indicate the cycle direction by the number of flows on each link. Constraints (3.48) guarantee that no cycle direction exists for the out-of-cycle links, and out-of-cycle nodes.

Figure 3 . 4 :

 34 Figure 3.4: Flow chart for the ILP-CG and De-CG.

2 Figure 3 . 5 :

 235 Figure 3.5: Directed p-cycle protection with different desired links.

  , and P i ′ = P k i ; end end I = I ∪ I temp ; for i ∈ I do for (u, v) ∈ P i do Calculate the length of the protection path from u to v on directed p-cycle i; end Set the modulation format m i according to the maximum length of the protection paths; end Solve the model with Eq. (3.56)-(3.59); for i ∈ I do if Φ i > 0 thenI * = I * ∪ i;According to the common links of directed p-cycles in I * , generate conflict graph and then allocate FSs[START_REF] Wu | On the distance spectrum assignment in elastic optical networks[END_REF]; end end situations of desired links need to be considered. Thus, lines 8-10 enumerate all the different combinations of desired links for each directed p-cycle. Each combination corresponds to a new directed p-cycle in lines 11-13.

Algorithm 3 . 2 : 3 for Φ i from 1 to |S| do 4 for a ∈ P i do 5 6 if cost i < cost then 7 costcost < 0 then 13 I 17 Output

 32345671317 Decomposition Algorithm Input : G(V, A), I * , I. Output: I * . 1 I = I \ I * , cost = 0, i * = 0; 2 for i ∈ I do Calculate the reduced cost of the directed p-cycle i, i.e. cost i , using Eq. (3.64); = cost i , i * = i; * = I * ∪ i * ; 14 Solve the next LRMP, the dual problem of LRMP, and the next pricing problem of De-CG; I * to the final solution; 18 end

Figure 3 . 6 :

 36 Figure 3.6: Topology of the testbeds used in simulations.

Figure 3 . 7 :

 37 Figure 3.7: Performance on Objective (Power Consumption and FS Usage) versus Number of Requests in 6-node network in Terms of |I|.

Figure 3 . 8 :

 38 Figure 3.8: Performance on Power Consumption and FS Usage versus Number of Requests in NSFNET and COST239 networks with Large-scale Traffics.

Figure 3 . 9 :

 39 Figure 3.9: Overall Reductions of the Proposed CG Methods Compared to VRN (heuristic) versus TA in NSFNET and COST239 networks with 100 requests.

Figure 4 . 1 :

 41 Figure 4.1: Solution acquired by DP and CDP with 6-node topology and 5 DZs.

  (4.2)-(4.4), Flow-conservation constraints (4.5), disaster-zone-disjoint path constraints (4.6)-(4.8), modulation adaption constraints (4.9)-(4.12), adaptive multi-path routing constraints (4.13)-(4.21), and spectrum allocation constraints (4.22)-(4.30).

Figure 4 . 3 :

 43 Figure 4.3: Topology of the testbeds used in simulations.

Figure 4 . 4 :

 44 Figure 4.4: Spectrum Utilization of DP and CDP using ILP in NSFNET, and COST239.

Figure 4 . 6 :

 46 Figure 4.6: Spectrum Utilization versus number of available DC locations in COST239 using HCDP.

Figure 4 . 7 :

 47 Figure 4.7: Spectrum Utilization versus number of available DC locations in US Backbone network using HCDP.

97

 97

  Average Storage Space per Content in COST239

Figure 4 . 8 :

 48 Figure 4.8: Storage Space Performance for 5 available DC locations per Content.

3 Figure 5 . 1 :

 351 Figure 5.1: The architecture of the EO-DCN.

Figure 5 . 3 :

 53 Figure 5.3: Distance-adaptive disaster protection in the NFV-embedded EO-DCNs.

  g rk aa ¯+ g r ′ k ′ aa ¯′ -1 ≤ γ rka r′ k ′ a ¯′ , ∀a, ∀r > r ′ , ∀k, ∀k ′ , ∀a ¯, ∀a ¯′ (5.40)γ rka r′ k ′ a ¯′ = γ r ′ k ′ a ¯′ rka ¯,∀a, ∀r > r ′ , ∀k, ∀k ′ , ∀a ¯, ∀a ¯′ (5.41)β rka r′ k ′ a ¯′ + β r ′ k ′ a ¯′ rka ¯= 1, ∀a, ∀r > r ′ , ∀k, ∀k ′ , ∀a ¯, ∀a ¯′ (5.42)Likewise, constraints (5.40)-(5.41) indicate whether any two lightpaths of two different requests have any common link. Constraints (5.42) then compare the FS starting index between the lightpaths of two different requests.x rk a ¯+ Φ rk a ¯-x r ′ k ′ a ¯′ ≤ |S| • (2γ rka r′ k ′ a ¯′β rka r′ k ′ a ¯′ ), ∀r ̸ = r ′ , ∀k, ∀k ′ , ∀a ¯, ∀a ¯′ (5.43)Constraints (5.43) avoid spectrum conflict among the paths of different requests.

Algorithm 5 . 1 : 5 6 Find 7 8 for i ∈ I do 9 for a ¯∈ A ¯r do 10 Calculate 28 for a ¯∈ A ¯r do 29 Generate

 5156789102829 Heuristic AlgorithmInput : G(V, A, D), Z, R, S. Output: I * , cost total for r ∈ R doG 0 = G; for k ∈ K r do for v ∈ D do Generate the shortest path from v to V s r in G k ; placement of v ¯∈ Cr at the DCs on path; Check the delay requirement and VNF capacity, and add all the feasible configurations into set I; from set I with the minimum cost as the path of type k using Eq. (5.44), and add it into set I * ; G k ← G k-1 \ {the DZ-joint links and nodes in the working path}; end end for i ∈ I * do for r ∈ R do for k ∈ K r do conflict graph for the lightpath, and allocate FSs basedon the color algorithm[START_REF] Wu | On the distance spectrum assignment in elastic optical networks[END_REF]; Calculate cost total using Eq. (5.45); node to each DC in topology G k . For each path, line 6 places the VNFs to the DCs in the order of C r . Here, a batch of configurations would be generated. Line 7 then adds all the feasible configurations into set I. A feasible configuration needs to satisfy the delay requirement of the request and the VNF capacity at DC. Then, lines 8-14 assign the modulation format and the number of FSs for lightpaths of the feasible configurations. Line 15 calculates the cost for each path and selects the one with minimum cost as the path k. The selected configurations are added into set I * . The cost of the path is the power consumption on the data transmission, shown as

  pm is the number of PMs at DC, determined by the total hosted VNFs and the capacity of each PM. The computational complexity for lines 1-16 is O(|R||D||A ¯r||I| log |A|). The computational complexity for lines 17-21 is O(|R||A ¯r| log(|R||A ¯r|)). Thus, the overall computational complexity for Algorithm 5.1 is O(|R||D||A ¯r||I| log |A| + |R||A ¯r| log(|R||A ¯r|)).

  Power Consumption and FS Usage vs. Number of Requests in NSFNET network Power Consumption and FS Usage vs. Number of Requests in US Backbone network

Figure 5 . 6 :

 56 Figure 5.6: Power Consumption and FS Usage vs. Number of Requests for SFC-MADP Compared with SFC-DP Using Heuristic Algorithm.

Table 1 . 1 :

 11 The Cisco historical Internet context[START_REF] Cisco | Cisco visual networking index: Forecast and trends, 2017-2022 white paper[END_REF]

	Year	Global Internet traffic
	1992	100 GB per day
	1997	100 GB per day
	2002	100 GB per second
	2007	2,000 GB per second
	2017	46,600 GB per second
	2022	150,700 GB per second

Table 1 . 2 :

 12 The spectrum efficiency, transmission reach, and power consumption with a single subcarrier (12.5 GHz)[START_REF] Vizcaíno | Protection in optical transport networks with fixed and flexible grid: Cost and energy efficiency evaluation[END_REF][START_REF] Zhang | Dynamic RMSA in spectrum-sliced elastic optical networks for high-throughput service provisioning[END_REF]

	Modulation format Transmission rate Transmission reach Power consumption
	16-QAM	50 Gbps	1,200 km	112.374 W
	8-QAM	37.5 Gbps	2,400 km	133.416 W
	QPSK	25 Gbps	4,800 km	154.457 W
	BPSK	12.5 Gbps	9,600 km	175.498 W
	flexibility of the data transmission in the EONs

Table 3 . 1 :

 31 Performance for directed and undirected p-cycles

	Schemes	Power consumption FSs usage
	Directed p-cycle	950.2 W	15
	Undirected p-cycle	1282.6 W	30

)

  Constraints (3.50)-(3.52) indicate whether the two nodes are both on-cycle nodes. The intermediate variables t i vu are used to eliminate the bi-linearities y i v • y i u . Constraints (3.53) allow the flow to exist only on on-cycle links and on-cycle nodes.

  The number of dominant variables and constraints for ILF are O(|I||A||V|), and O

	(	max{|I||V| 2 , |I| 2 |A|}	)	, respectively, for ALF are O(|I||A| 2 ), and O	(	max{|I||V||A|,
	|I| 2 |A|}	)	, respectively, and for LEF are O(|I||V| 2 |A|), and O	(	max{|I||A| 2 , |I| 2 |A|}	)	,
	respectively.

  The number of dominant variables and constraints are O(max{|V| 2 |A|, |A||S|}), and O(max{|V||A|, |A| 2 , |I * | 2 |A||S|}) in ILP-CG, respectively. They are O(|I * | 2 |A||S|), and O(|I * | 2 |A||S|) in De-CG, respectively.

Table 3 . 2 :

 32 Quality of proposed directed p-cycles with 50 requests in 6-node network

	Cycles		ILF		ALF		LEF
		Obj	Time(s)	Obj	Time(s)	Obj	Time(s)
	2	20820	9	20820	12	20820	10
	3	20253	81	20253	200	20253	20
	4	19846	11088	19846 257513 19846	107
	5	-	259200	-	259200 19504	805

-No feasible solution is obtained after 72 hours or exhausting the memory.

Table 3 . 3 :

 33 Quality of LEF ILP Model with |I| = 6, ILP-CG, and De-CG

	Requests	Obj	LEF ILP Model LB E (W) FSs |I * |	t (s)	Gap	ϵ
	10	10,178	N/A	10,097 81	6	1,776	N/A	N/A
	20	*19,172	N/A	19,034 138	6	37,236	N/A	N/A
	30	*26,261	N/A	26,107 154	6	51,439	N/A	N/A
	40	*35,621	N/A	35,397 224	6	8,685	N/A	N/A
	50	*42,943	N/A	42,676 267	6	23,261	N/A	N/A
				ILP-CG
	10	10,302 9,420.86 10,225 77	8	1	1.22%	9.35%
	20	19,150 17,252.7 19,032 118 15	4	-0.01% 11.00%
	30	25,782 24,318.9 25,625 157 20	4	-1.82% 6.02%
	40	35,180 33,290.2 34,947 233 17	3	-1.24% 5.68%
	50	42,591 40,249.6 42,305 286 15	2	-0.82% 5.82%
				De-CG
	10	10,302 9,984.36 10225 77	8	1	1.22%	9.35%
	20	19,516 17,765.6 19,409 107 14	2	-0.01% 11.00%
	30	25,782 24,739.8 25,625 157 12	4	1.82%	6.02%
	40	35,587 33,917.6 35,403 184 21	1	-0.10% 6.90%
	50	43,249 41,041.3 43,037 212 14	1	0.71%	7.45%

* The result obtained by ILP is even worse due to the limited |I| or exhausting the memory.

Table 3 . 4 :

 34 Efficiency of ILP-CG and De-CG

	Requests	Obj	LB	ILP-CG E (W) FSs |I * |	t (s)	ϵ	Obj	E (W)	De-CG FSs |I * | t (s)	ϵ
						NSFNET Network
	50	91,946 88,324.9 91,049	897	30	1,576 4.10% 99,471	98,495	976	26	3	12.62%
	100	175,295 168,183 173,823 1,472 30	2,560 4.23% 178,945 177,257 1,688 35	32	6.40%
	150	250,506 247,603 248,550 1,956 42	5,357 1.17% 262,013 259,969 2,044 42 222 5.82%
	200	331,366 324,974 328,604 2,762 53	4,240 1.97% 336,769 334,084 2,685 46 578 3.63%
						COST239 Network
	50	35,952 33,559.6 35,741	211	27 17,382 7.13% 37,198	37,010	188	26	59 10.84%
	100	87,242 82,572.6 86,788	454	48 61,210 5.65% 88,435	88,054	381	48 126 7.10%
	150	129,955 124,906 129,342 613	48 85,985 4.04% 133,692 133,089 603	50 212 7.03%
	200	173,294 167,284 172,345 949	38 14,891 3.59% 174,150 173,392 758	45 212 4.10%

Table 3 . 5 :

 35 Objective versus Different Weights Using De-CG with 1000 Requests

	Weights Ratio (θ 1 : θ 2 )	1 : 0	1 : 0.001	1 : 0.01	1 : 1	0 : 1
		NSFNET Network
	Objective	10,374	12,845.6	33,893.3 1,993,960 1,976,280
	Lower Bound	10,361.2	12,829.4	33,864.2 1,990,410 1,970,600
	FS Usage	10374	10413	10930	19797	19811
	Power Consumption (W) 3,400,840 2,432,570 2,296,330 1,974,160 1,976,280
	Number of p-cycles	21	32	38	42	41
		COST239 Network
	Objective	2,266	3,480.19	12,491.1	916,416	912,443
	Lower Bound	2,251.88	3,452.97	12,394.7	909,685	905,748
	FS Usage	2266	2375	2783	3954	3977
	Power Consumption (W) 1,354,410 1,105,190 970,810	916,462	912,443
	Number of p-cycles	31	43	53	50	49

  , EO-DCNs are facing serious threats from large-scale disasters. A disaster zone (DZ) failure may affect several links and nodes on a large scale and for a relatively long time. Examples include e.g., hurricane Katrina decreased the network usability of the affected area from 99.99% to 85%, which caused severe losses in Louisiana and Mississippi in the Southeastern US in August 2005. The 8.3-magnitude Wenchuan earthquake in May 2008 destroyed 3,897 telecommunication nodes and 28,765 km cables in Sichuan, Gansu, Shaanxi, and other provinces.

Table 4 . 1 :

 41 System performance in DP and CDP

	Schemes FSs usage MOFI Storage Space
	DP	16	8	2C
	CDP	12	4	3C/2

do for k from 1 to |k r | do 25

	19	Calculate the cost for the candidate configuration using Eq. (4.33);
	20	else
	21	Break;
		Select the candidate configuration with minimal cost for request r, and update |k r |
		accordingly;
		for r ∈ R Generate conflict graph, and allocate FSs based on the conflict graph [112];
		Calculate the MOFI, ∆ ← MOFI;
		Calculate cost total using Eq. (4.34);
		L max ← L max ∪ {link(s) with the MOFI};
		for i from 1 to F max do
		for r ∈ R do
	31 32	for d ∈ D r : µ k r,d = 1 do for a : p k ra = 1 do
	33 34	if a ∈ L max then G ′ ← G \ {a};
	35	Regenerate all the possible solutions based on G ′ ;
	36 37	if ∃ solution with cost ′ total < cost total then cost total ← cost ′ total ;

  1, the computational complexity for the first step, i.e. lines 2-22, to generate initial solution and solution set is O(|R| • |D| • |V| • |M| • log |A|). The computational complexity for the spectrum usage assignment is O(log(|R| • |K|)) [112]. Thus, the computational complexity of the second step, i.e. lines 23-25, is O(|R| • |K| • log(|R| • |K|). the computational complexity of the third step, i.e. lines 26-39, of backtracking is

  use CPLEX 12.60 to solve the proposed ILP model and heuristic on a PC with a 3.6 GHz CPU and a 64 GBytes RAM. In order to fairly evaluate the pros, cons, and applicable scenarios of CDP, we make the following comparisons in three classical EO-DCN testbeds NSFNET (14 nodes, 44 directed links, 14 DZs, average link length 1936 km, and average nodal degree 3.14), COST239 (11 nodes, 52 directed links, 7 DZs, average link length 578 km, and average nodal degree 4.73), and US Backbone network (28 nodes, 90 directed links, 15 DZs, average link length 466 km, and average nodal degree 3.2):

	• Efficiency of the HCDP compared with the ILP model, with 3 DCs at 5 available
	DC locations;
	• Optimal spectrum utilization of CDP and DP (computed by solving the proposed
	ILP model) with small scale of requests, with 3 DCs at 5 available DC locations;

Table 4 . 2 :

 42 Quality of Solution and Execution Time in Joint ILP models and the HCDP

	Method		Joint ILP model			HCDP
	Number of Requests Objective FS total MOFI Time(s) Objective FS total MOFI Time(s)	Gap
		NSFNET Network, 3 DCs at available locations of nodes 2, 5, 6, 9, and 11
	10	58	52	6	34	74	69	5	4	18.97%
	20	117	107	10	10800	120	113	7	17	2.56%
	30	190	174	16	10800	226	212	14	32	18.95%
	40	-	-	-	10800	279	266	17	57	-
		COST239 Network, 3 DCs at available locations of nodes 1, 2, 7, 8, and 11
	10	50	45	5	10800	51	45	6	1	2.00%
	20	96	85	10	10800	88	80	8	6	-8.33%
	30	149	133	16	10800	137	124	13	13	-8.05%
	40	-	-	-	10800	199	165	21	24	-

Table 4 . 3 :

 43 Objective of CDP versus Different Weights with 20 Requests (Using ILP)

	Weights Ratio (θ 1 : θ 2 )	0:1	0.1:1	0.5:1	1:1	1:0.5	1:0
	NSFNET Network, 5 DCs at nodes 2, 5, 6, 9, and 11
	Objective	10	20.2	61	112	108	102
	FS total	119	102	102	102	102	102
	MOFI	10	10	10	10	10	300
	COST239 Network, 5 DCs at nodes 1, 2, 7, 8, and 11
	Objective	6	15.6	53	98	94	90
	FS total	196	96	90	90	90	90
	MOFI	6	6	8	8	8	300

  Constraints(5.18) indicate that the outgoing flow and incoming flow of each physical node v are equal, if the physical link (v, u) is used by virtual link (v ¯, u ¯), unless it is a destination DC, which has an only incoming flow, or the requesting node, which has only outgoing flow. In specific, for the k-th path of the request r, the equation equals 1 if v ¯is placed on node v and equals -1 if u ¯is placed on node v. Otherwise, it remains 0.

	∑ u∈N v	g rk (v,u),(v ¯,u ¯) -∑ u∈N v	g rk (u,v),(v ¯,u ¯) = e rk vv ¯-e rk vu ¯,	∀r, ∀k, ∀v, ∀(v ¯, u ¯)	(5.18)
					∑ a∈A	g rW aa ¯≤ ∑ a∈A	g rB aa ¯,	∀r, ∀k, ∀a ¯(5.19)
	Constraints (5.19) ensure that the working path is always shorter than the backup
	path for each request.
	4) Modulation adaption constraints
	a∈A ∑	d a • g rk aa ¯≤ h m + h max • (1 -b rkm a ¯),	∀r, ∀k, ∀m, ∀a ¯(5.20)
	m∈M ∑	b rkm a ¯≤ 1,		∀r, ∀k, ∀a ¯(5.21)
				e vv ¯≥ e rk vv ¯,	∀r, ∀k, ∀v ̸ = V s r , ∀v ¯̸ = V s r	(5.13)
				e vv ¯= 0,	∀v / ∈ D, ∀v ̸ = V s r , ∀v ¯(5.14)
				v∈D ∑	e vv ¯≤ E,	∀v ¯(5.15)
	Constraints (5.13) to (5.15) indicate that the replicas of each VNF are distributed at
	no more than E DCs.
				l rk a ≤ ∑ a ¯grk aa ¯,	∀r, ∀k, ∀a	(5.16)
				l rk a ≥ g rk aa ¯,	∀r, ∀k, ∀a, ∀a ¯(5.17)
	Constraints (5.16) and (5.17) indicate whether the link a is used for path k of request
	r.
	3) Flow conservation constraints

5) Network capacity constraints

  Constraints(5.22) guarantee that no FS is allocated for the virtual link that is not mapped to any physical link. This case happens when two consecutive VNFs of the path are placed at the same DC, which is then determined by constraints (5.23) and(5.24). Constraints(5.22) also restrict the FSs are assigned within the link capacity. Constraints (5.25) and(5.26) give the number of FS assigned for each lightpath on each physical link. Constraints (5.27) guarantee that no FS is assigned for the nonselected paths or none-selected modulation formats.Constraints(5.29) provides the number of FSs assigned on each link for each path at each modulation format. Constraints (5.29) can provide information on each modulation format, which aim to calculate the power consumption of BVTs. To ensure linearity, constraints (5.29) are then rewritten as constraints (5.30)-(5.32).

	m∈M ∑	Φ rkm a ¯• T m ≥ B r • ϕ rk a ¯,	∀r, ∀k, ∀a ¯(5.28)
	Constraints (5.28) ensure that the FSs assigned for each lightpath are sufficient to
	serve the request.
	Φ rkm aa ¯= g rk aa ¯• Φ rkm a ¯,	∀r, ∀k, ∀a, ∀a ¯(5.29)
	Φ rkm aa ¯≤ g rk aa ¯• |S|,	∀r, ∀k, ∀m, ∀a, ∀a ¯(5.30)
	Φ rkm aa ¯≤ Φ rkm a ¯,	∀r, ∀k, ∀m, ∀a ¯(5.31)
	Φ rkm aa ¯≥ Φ rkm a ¯-|S| • (1 -g rk aa ¯),	∀r, ∀k, ∀m, ∀a, ∀a ¯(5.32)
	6) SFC provisioning constraints
	Φ rk a ¯≤ ϕ rk a ¯• |S|,	∀r, ∀k, ∀a ¯(5.22)
	ϕ rk a ¯≤ ∑ a∈A	g rk aa ¯,	∀r, ∀k, ∀a ¯(5.23)
	ϕ rk a ¯≥ g rk aa ¯,	∀r, ∀k, ∀a ¯(5.24)
	Φ rk a ¯= ∑ m∈M	Φ rkm a ¯,	∀r, ∀k, ∀a ¯(5.25)
	Φ rk aa ¯= ∑ m∈M	Φ rkm aa ¯,	∀r, ∀k, ∀a, ∀a ¯(5.26)
	Φ rkm a ¯≤ b rkm a ¯• |S|,	∀r, ∀k, ∀m, ∀a ¯(5.27)

  Constraints(5.34) ensure that the reserved VNFs at each DC do not exceed the capacity of the PM.Constraints(5.33) guarantee that the end-to-end delay is limited to the required delay. The total delay of each path consists of the VNF processing time at DCs and propagation time in physical links. 7) Spectrum allocation constraints g rW aa ¯+ g rB aa ¯′ -1 ≤ γ rWa rBa ¯′ , ∀a, ∀r, ∀a ¯∈ W r , ∀a ¯′ ∈ B r (5.36) ∀a, ∀r, ∀a ¯∈ W r , ∀a ¯′ ∈ B r (5.37) ∀a, ∀r, ∀a ¯∈ W r , ∀a ¯′ ∈ B r (5.38) Constraints (5.36) and (5.37) indicate whether any two lightpaths of working path and backup path of the same request have any common link. Constraints (5.38) then compare the FS starting index between the lightpaths of the working path and backup path of the same request. x rk a ¯+ Φ rk a ¯-x rk ′ a ¯′ ≤ |S| • (2γ rka rk ′ a ¯′β rka rk ′ a ¯′ ), ∀r, ∀k, k ′ ∈ r, k ̸ = k ′ , ∀a ¯∈ k, ∀a ¯′ ∈ k ′

	γ rWa rBa ¯′ = γ rBa ¯′ rWa ¯,
	β rWa rBa ¯′ + β rBa ¯′ rWa ¯= 1,
			pm ,	∀v ∈ D	(5.34)
	∑ v∈D	∑ v ¯∈A ¯r e rk vv ¯• ψ v ¯+ ∑ a∈A	l rk a • ψ a ≤ Ψ r ,	∀r, ∀k	(5.35)

  2 |A ¯r| 2 )} and {O(|R| 2 |A ¯r| 2 |A|)}, respectively.

Table 5 .1: VNF Configurations

 5 3.14), and US Backbone network (11 nodes, 52 directed links, 8 DCs, average link length 578 km, and average nodal degree 4.73) [69]. The simulation parameters for different scenarios are set as follows. 1) 5 available DCs at nodes 2, 5, 6, 9 and 11 in NSFNET network; 2) 8 available DC locations at nodes 1, 7, 9, 12, 14, 19, 21 and 28 in US Backbone network. The DC and DZ distribution and topology is detailed in

	VNF	CPU Cores Mem Capacity Type
	NAT	1	8 GB	900 Mbps
	Firewall	2	16 GB	900 Mbps
	Proxy	2	16 GB	900 Mbps
	IDS	4	32 GB	600 Mbps
	average nodal degree

Table 5 . 2 :

 52 Quality of Solution and Execution Time in ILP model and the Heuristic

	Method		ILP model			Heuristic
	Requests Objective Power (W) FS Usage	Time(s)	Objective Power (W) FS Usage Time(s)	Gap
				NSFNET Network with 4 DCs (E = 4)
	50	90,471	90, 084	387	431, 807	91,349	90, 854	495	1	0.97%
	100	179,099	178, 507	592	1, 469, 976	180,343	179, 338	1, 005	1	0.69%
				US Backbone Network with 8 DCs (E = 6)
	50	86,116	85, 805	311	427, 318	90,022	89, 436	586	1	4.54%
	100	167,761	167, 055	706	1211, 361	170,477	170, 377	1, 150	6	1.62%

Acknowledgements

This study is supported by China Scholarship Council (202006960046), and Bourses d'Excellence EIFFEL du Gouvernement Français (P745849E).

Heuristic for CDP

We notice that the system performance is related to the number of paths, the number of hops for each path, the distance of each path, as well as the required spectrum resource. This is because the different number of paths leads to different overhead, which is caused by the rounding up of the spectrum resource division. Also, the number of hops for each request may increase dramatically as the number of paths grows, and it would require much more FSs in total. Thus, the number of paths is not the more the better. There may exist an optimal number of paths for each request in the given topology. To this end, we then propose an adaptive method to generate the paths for each request, in which all the possible paths combination would be taken into consideration. Accordingly, we propose the heuristic algorithm HCDP, whose pseudo-code is given in Algorithm 4.1.

The HCDP runs after the DC assignment and content placement, which is obtained by ILP, i.e. ILP constraints (4.2)-(4.4), where constraints (4.2) are rewritten as

The objective is to minimize the overall hops from DCs to source nodes.

Disaster Resilient SFC Provisioning

In this work, we focus on EO-DCNs, where a digraph G(V, A, D) is used to model the physical network, being V the set of nodes, A the set of directed links, and D the set of DCs. Each DC is deployed with a cluster of PMs. We assume the DZs are aware in the network, in which Z denotes the set of DZs. Each DZ contains the corresponding affected nodes and links. Note that spectrum refers to FS in EO-DCNs, and the granularity of FS is assumed as 12.5 GHz in this work.

Each request is provisioned by the anycasting technique. It allows provisioning traffic through a backup path using a replica SFC hosted at several backup DCs, when the working path connection fails due to disaster failure. Thus, each request has a specific source node, the content, and the required bit rate. Each content also corresponds to a specific SFC. Thus, for request r(V s r , C r , B r ), V s r is the source node, C r represents the required content, and B r denotes the required bandwidth. Specifically, C r consists of an SFC and the corresponding delay requirement.

We use a digraph G r ¯(V r ¯, A r ¯) as a virtual network to model the SFC of the request r. The set of virtual nodes V r ¯is the ordered VNF set of C r for request r. In particular, the source node and the destination DC are also added to the set to ease the modeling. The set A r ¯consists of virtual links that interconnect the virtual nodes in the order of the requested SFC for request r. Each virtual node and virtual link should be mapped to the physical network G. We use superscript bar to distinguish the virtual graph from the physical graph. Fig. 5.2 gives an example of a virtual network, where the virtual nodes in the SFC are mapped to physical nodes. The VNF needs to be hosted at a PM on a physical node. Thus, the virtual links are mapped on the corresponding physical links, which vary depending on the location of the VNF. For instance, virtual links VNF1-VNF2 do not have a physical path because both VNFs are placed on the same physical node; in contrast, virtual links VNF3-VNF4 are mapped to two physical links. In particular, the request node is fixed and its refers to the same node in both the virtual and physical networks.

We first give a simple example in Fig. 5.3 to better illustrate the disaster protection scheme with distance adaptive configuration. We consider an 8-node network with 3 DCs (nodes 1, 3, and 7), and 7 DZs, where a request originated from node 8 demanding a SFC-based cloud service with 2 VNFs. The request is provisioned by a working path 3-7-8, and a backup path 1-2-4-8. Also, two primary DCs and one backup DC are assigned for the request. The working path is generated with two lightpaths, 3-7 and 7-8. The traffic needs to be processed by VNF 1 at DC 3 and VNF 2 at DC 7. While backup path only has one lightpath, since the replicas of VNF 1 and VNF 2 are both deployed at DC 1. It leads to a longer lightpath, and a lower order of modulation format that can be assigned. Note that the spatially separated VNF deployment can reduce the spectrum usage with the higher spectrum efficiency of higher-order modulation format. However, it requires extra bandwidth-variable transponders (BVTs) at relay DCs to reroute the traffic and consequently increases power consumption. We then describe the main considerations as follows.

1) Disaster resilient protection

We focus on dedicated path protection against disaster failure. Each request is provisioned by a working path and a backup path. Two paths should be configured as DZ-disjoint from each other. Two paths are DZ-disjoint if their physical links are not affected by the same DZ (except the DZ covers the source node), such that the backup path can be activated once the working path is blocked by any DZ.

2) VNF placement and SFC provisioning

We assume all the VNFs are placed at the DCs. The VNF placement should guarantee the SFC provisioning of each request. A complete corresponding SFC should be configured for both the working path and backup path for a request. The disaster resilience of the SFC is fulfilled once the DZ-disjoint paths are established. For each SFC, the corresponding delay requirement should also be met.

3) Modulation format adaptation

We restrict each modulation format's transmission range to ensure that the received SNR remains within acceptable limits. We investigate four modulation formats: 16-QAM, 8-QAM, QPSK, and BPSK, with transmission reaches of 1, 200, 2, 400, 4, 800, and 9, 600, respectively, in km [START_REF] Liu | Disaster protection in inter-datacenter networks leveraging cooperative storage[END_REF]. The available transmission rates of each FS are set as 50, 37.5, 25, and 12.5, in Gbps, respectively [START_REF] Chen | On spectrum efficient failure-independent path protection p-cycle design in elastic optical networks[END_REF]. The maximum path length for each lightpath should not exceed the corresponding transmission reach of the assigned modulation format.

Heuristic Algorithm

To improve the scalability to deal with large-scale instances, we propose a heuristic algorithm to solve the joint problem, whose procedure is explained in Fig. 5.4. For each request, we use k-shortest routing from the source node to each DC. We select the feasible path with the minimum cost as the first path and then delete the DZ-joint links and nodes from the topology. The backup path is then generated as DZ-disjoint from the working path. After we configure all the requests, we then use the color-algorithmbased conflict graph to allocate the spectrum for them. Accordingly, the pseudo-code is given in Algorithm 5.1.

Lines 1-2 initializes the network topology of the input as the current topology for each request. Lines 3-5 use k-shortest routing to generate each path from the source when number of requests is 50 and 60 in Fig. 5.5(a) and Fig. 5.5(b), respectively. One explanation is that the obtained solution is with fewer VNF-placed DCs, which offers much lower power consumption but a longer path length, thus a bit higher FS usage.

Validation of Efficiency for the Heuristic Compared with ILP Model

To verify the efficiency of the proposed heuristic algorithm, we then conduct simulations with both the ILP model and the heuristic algorithm in NSFNET and US Backbone networks. Note that we set 5 DCs with 4 of them being available for the VNF placement (E = 4) in the NSFNET, and 8 DCs with only 6 of them available for VNF placement (E = 6) in the US Backbone network. The Gap is introduced by the heuristic algorithm compared with the ILP model.

As shown in

List of Publications

International Journals: