Routing and Protection in Flexible Optical Networks

Routing and Protection in Flexible Optical Networks Min Ju To cite this version: Min Ju. Routing and Protection in Flexible Optical Networks. Hardware Architecture [cs.AR]. Université d’Avignon; Institut d’études avancées sur la culture européenne (Shanghai, Chine), 2018. English. �NNT : 2018AVIG0226�. �tel-01924170v2� HAL Id: tel-01924170 https://tel.archives-ouvertes.fr/tel-01924170v2 Submitted on 3 Dec 2018 HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. ACADÉMIE D’AIX-MARSEILLE UNIVERSITÉ D’AVIGNON ET DES PAYS DE VAUCLUSE THÈSE présentée à l’Université d’Avignon et des Pays de Vaucluse pour obtenir le diplôme de DOCTORAT SPÉCIALITÉ : Informatique École Doctorale 536 « Sciences et Agronomie » Laboratoire d’Informatique (EA 4128) Optimisation de la Protection des Réseaux Optiques de Nouvelle Génération par Min Ju Soutenue publiquement Janvier 2018 devant un jury composé de : M. M. M. M. M. M. M. Bernard Cousin Massimo Tornatore Rami Langar Bogdan Uscumlic Juan-Manuel Torres Shilin Xiao Fen Zhou Professeur, IRISA, Université de Rennes 1 Maître de Conférences, École polytechnique de Milan Professeur, LIGM, Université Paris-Est Marne-la-Vallée Ingénieur de Recherche, Nokia Bell Labs Maître de Conférences (HDR), LIA, Université d’Avignon Professeur, LOCT, Université de Shanghaï Jiao Tong Maître de Conférences, LIA, Université d’Avignon Rapporteur Rapporteur Examinateur Examinateur Directeur de thèse Co-directeur de thèse Co-directeur de thèse Laboratoire d’Informatique d’Avignon ACADÉMIE D’AIX-MARSEILLE UNIVERSITÉ D’AVIGNON ET DES PAYS DE VAUCLUSE THESIS A thesis submitted at the University of Avignon for the degree of Doctor of Philosophy In : Computer Science Doctoral School 536 « Sciences et Agroscience » Laboratoire d’Informatique (EA 4128) Optimization of Protection Schemes for Next Generation Optical Networks by Min Ju Defended publicly January 2018 before the jury members: M. M. M. M. M. M. M. Bernard Cousin Massimo Tornatore Rami Langar Bogdan Uscumlic Juan-Manuel Torres Shilin Xiao Fen Zhou Professor, IRISA, University of Rennes 1 Associate Professor, Polytechnic University of Milan Professor, LIGM, University Paris-Est Marne-la-Vallée Research Engineer, Nokia Bell Labs Associate Professor, LIA, University of Avignon Professor, LOCT, Shanghai Jiao Tong University Associate Professor, LIA, University of Avignon Reviewer Reviewer Examiner Examiner Supervisor Co-supervisor Co-supervisor Laboratoire d’Informatique d’Avignon ii Résumé La tolérance aux pannes est une propriété très importante des réseaux optiques de nouvelle génération. Cette thèse aborde la conception des mécanismes de protection contre des pannes liées à la défaillance d’une fibre optique ou à une catastrophe naturelle. Deux systèmes de protection classiques, à savoir la protection par des cycles préconfigurés (p-cycles) et la protection du chemin de secours, sont étudiés pour atteindre une efficacité de protection élevée, tout en considérant le coût de l’équipement optique, la consommation d’énergie et l’utilisation de la ressource spectrale. Ces problèmes de survivabilité sont d’abord formulés en utilisant la programmation linéaire en nombres entiers (PLNE), et ensuite résolus soit par algorithmes heuristiques, soit par une approche de décomposition. La panne d’une seule fibre optique est le scénario le plus courant. Nous allons donc considérer d’abord des pannes liées à la défaillance d’une fibre optique dans les réseaux optiques multi-débit. Pour réduire le coût des transpondeurs, un système de protection par p-cycles de longueur adaptable et peu coûteux est proposé. Spécifiquement, les pcycles de longueur limitée sont conçus pour utiliser un débit approprié en fonction du coût du transpondeur et de la portée de transmission. Un modèle de programmation linéaire en nombres entiers (PLNE) sans énumération des cycles candidats est formulé pour générer directement les p-cycles de coût dépenses d’investissement minimum. De plus, un algorithme GPA (Graph Partitioning in Average) et un algorithme d’estimation des nombres de cycles (EI) sont développés pour rendre le modèle PLNE plus efficace au niveau du temps de calcul. En ce qui concerne la consommation d’énergie des réseaux optiques élastiques résilients, nous proposons d’utiliser un schéma de p-cycles dirigés, efficaces en énergie, pour protéger le trafic asymétrique. En raison de l’avantage de distinguer du volume de trafic dans les deux directions, les p-cycles dirigés consomment peu d’énergie en attribuant de créneaux ou slots du spectre et des formats de modulation différents à chaque direction. Un modèle PLNE est formulé pour minimiser la consommation d’énergie totale sous contraintes de génération du cycle dirigée, d’allocation de spectre, d’adaptation de modulation et de capacité de protection. Pour le passage à l’échelle, le modèle PLNE est décomposé en deux sous-problèmes: une méthode d’énumération de cycles améliorée et un modèle PLNE simplifié pour la sélection des cycles. Nous avons montré que les p-cycles dirigés obtiennent une meilleure performance comparant les p-cycles iii non-dirigés pour le trafic asymétrique en termes de la consommation d’énergie et de l’utilisation du spectre. Afin d’améliorer l’efficacité d’utilisation du spectre dans réseaux optiques élastiques, une protection par p-cycles (SS-p-cycle) à spectre partagé est proposée. Les SS-p-cycles permettent de réduire l’utilisation du spectre et le taux de fragmentation spectrale en exploitant un partage de spectre spécial entre plusieurs p-cycles ayant des liens communs. Les modèles PLNE est conçus dans les cas �sans� ou �avec� conversion spectrale afin de minimiser l’utilisation du spectre. Ces modèles peuvent obtenir la solution optimale pour un petit réseaux optiques élastiques, et une heuristique efficace est développée pour résoudre les instances à grande échelle. Les résultats de simulations montrent que les SS-p-cycles ont des avantages significatifs pour réduire l’utilisation de la ressource spectrale et la défragmentation des fréquence. De plus, la conversion du spectre aide les SS-p-cycles à acquérir une meilleure utilisation du spectre. Finalement, bien que la panne de liaison unique est le scénario le plus courant, les défaillances à grande échelle dues aux catastrophes naturelles menacent la capacité de survie des réseaux de centres de données. Également, le problème d’approvisionnement de service de cloud après sinistre est étudié, en considérant la disposition du contenu, le routage, la protection du chemin et du contenu, et l’allocation du spectre. Les services cloud permettent d’utiliser un autre nœud centres de données avec du contenu répliqué pour garantir la survivabilité en cas de sinistre. Nous étudions deux modèles de protection contre les pannes liées aux catastrophes naturelles: la protection par chemin de secours de bout en bout dédiée et la protection par chemin de secours de bout en bout partagée, qui visent à minimiser l’utilisation du spectre. Un modèles PLNE est formulés pour chaque schéma de protection. Une approche de décomposition basée sur la génération de colonnes est proposée afin de trouver les solutions de chaque schéma de protection pour un réseaux optiques élastiques à l’échelle. Une évaluation approfondie a été réalisée pour étudier l’impact sur l’utilisation du spectre en termes de la quantité de trafic, du nombre de centre de données, du nombre de répliques et de topologies des réseaux. Mots clés : Protection avec p-cycles, Routes de secours, Réseaux optiques multidébit, Réseaux optiques élastiques, Génération de colonnes, Programmation linéaire en nombres entiers (PLNE), Algorithmes heuristiques. iv Abstract Network survivability is a critical issue for optical networks to maintain resilience against network failures. This dissertation addresses several survivability design issues against single link failure and large-scale disaster failure in optical networks. Two classic protection schemes, namely pre-configured Cycles (p-Cycle) protection and path protection, are studied to achieve high protection capacity efficiency while taking into account the equipment cost, power consumption and resource usage. These survivable network design problems are first formulated by mathematical models and then offered scalable solutions by heuristic algorithms or a decomposition approach. We first consider single link failure scenario. To cut the multi-line rates transponders cost in survivable Mixed-Line-Rate (MLR) optical networks, a distance-adaptive and low Capital Expenditures (CAPEX) cost p-cycle protection scheme is proposed without candidate cycle enumeration. Specifically, path-length-limited p-cycles are designed to use appropriate line rate depending on the transponder cost and transmission reach. A Mixed Integer Linear Programming (MILP) model is formulated to directly generate the optimal p-cycles with the minimum CAPEX cost. Additionally, Graph Partitioning in Average (GPA) algorithm and Estimation of cycle numbers (EI) algorithm are developed to make the proposed MILP model scalable, which are shown to be efficient. Regarding the power consumption in survivable Elastic Optical Networks (EONs), power-efficient directed p-cycle protection scheme for asymmetric traffic is proposed. Owing to the advantage of distinguishing traffic amount in two directions, directed p-cycles consume low power by allocating different Frequency Slots (FSs) and modulation formats for each direction. An MILP model is formulated to minimize total power consumption under constraints of directed cycle generation, spectrum assignment, modulation adaptation and protection capacity allocation. To increase the scalability, the MILP model is decomposed into an improved cycle enumeration and a simplified Integer Linear Programming (ILP) model. We have shown that the directed p-cycles outperform the undirected p-cycles in terms of power consumption and spectrum usage. In order to improve the spectrum usage efficiency in p-cycle protection, a Spectrum Shared p-cycle (SS-p-cycle) protection is proposed for survivable EONs with and without spectrum conversion. SS-p-cycles permit to reduce spectrum usage and Spectrum Fragmentation Ratio (SFR) by leveraging potential spectrum sharing among multiple p-cycles that have common link(s). The ILP formulations are designed in both cases of v with and without spectrum conversion to minimize the spectrum usage of SS-p-cycles which can obtain the optimal solution in small instance, and a time-efficient heuristic algorithm is developed to solve large-scale instances. Simulation results show that SSp-cycles have significant advantages on both spectrum allocation and defragmentation efficiency, and the spectrum conversion does help SS-p-cycle design to acquire better spectrum utilization. Finally, large-scale disaster failures are being threatening the survivability of elastic optical Datacenter Networks (DCNs) although single link failure is the most common failure scenario. The disaster-survivable cloud service provisioning problem is investigated regarding the content placement, routing, protection of path and content, and spectrum allocation. Cloud services allow to use another DC node with replicated content to ensure disaster survivability. ILP models are formulated for Dedicated Endto-content Back-up Path Protection (DEBPP) and Shared End-to-content Back-up Path Protection (SEBPP), both of which aim at minimizing the spectrum usage. A decomposition approach based on Column Generation (CG) is proposed to increase the scalability of the ILP models of DEBPP and SEBPP. Extensive evaluation is performed to study the impact on the spectrum usage in terms of traffic amount, DCs, replicas, and network topologies. Key-words: p-Cycle protection, Path protection, Mixed line rate networks, Elastic optical networks, Column generation, MILP, Heuristic algorithm. vi Acknowledgements This work is supported by China Scholarship Council and French Eiffel Scholarship. First and foremost, I offer my gratitude to my supervisor, Dr. Fen Zhou, who supported me throughout my thesis with his guidance and encouragement. Without his effort, patience and availability during these three years, I would not have been able to complete this work. I would like to thank my co-advisors, Prof. Shilin Xiao and Dr. Torres Juan-Manuel. They always give me very good advices and encourage me in my work. I am very grateful to them. I appreciate Prof. Shilin Xiao to encourage me to participate in the joint-supervision program. I would like to thank Prof. Zuqing Zhu for his invaluable suggestions and kind encouragement. I appreciate the opportunity to work with him. I also would like to thank my committee members for their prompt evaluation and comments to improve the quality of this dissertation. I would like to thank my friends Minh Huong, Mohamed Amine Ait Ouahmed, Zakaria Ye, Haitao Wu, Jingyi Jiang, Weihua Wu and all the fellow graduate students in University of Avignon for their friendship during the three years of my stay in France. Special thanks to Haitao Wu and Weihua Wu for the opportunity of working together and valuable discussion. I would like to thank fellow graduate students and friends Zhao Zhou, Meihua Bi, Tao Qi, Jia Peng in Shanghai Jiao Tong University for their friendship during my work. Special thanks to Zhao Zhou for the recommendation to work with Dr. Fen Zhou. Last but not least, I would like to thank my family for their encouragement and support throughout my life. vii viii Introduction The past few decades have witnessed the evolution of optical networks from SingleLine-Rate (SLR) Wavelength-Division Multiplexing (WDM) towards Mixed-Line-Rate (MLR) WDM and Elastic optical networks (EONs) architectures [66, 94, 96, 122]. The network capacity and flexibility have been gradually improved in order to satisfy the requirements on high-bandwidth and on-demand applications [66, 107]. Also, network survivability is a key issue for optical networks to maintain operation against common network failures (e.g., fiber cut), since a huge number of services are provisioned by the optical infrastructure [93]. In addition to the most common single link failure, the new failure scenario of large-scale disaster has threatened the optical Data Center Networks (DCNs), which can cause huge data loss and service disruptions [55]. There exist several protection schemes for survivable optical networks, such as link protection, path protection, ring protection and Pre-Configured-Cycle (p-Cycle) protection [33, 72, 116]. We first focus on the p-cycle protection scheme against single link failure owing to its distinct advantages that it has fast switching speed and provides protection capacity for both on-cycle links and straddling links [52]. Conventional pcycle designs are required to enumerate candidate cycle set in advance, and to screen the most efficient p-cycles from the candidate cycle set. In contrast, we investigate pcycle design principle without candidate cycle enumeration, which can overcome the drawback that it would be intractable to enumerate all the candidate cycles for large networks. In addition to p-cycle protection, path protection is also studied for disastersurvivable elastic optical DCNs. More specifically, Dedicated End-to-content Back-up Path Protection (DEBPP) and Shared End-to-content Back-up Path Protection (SEBPP) are explored for anycast traffic enabled by datacenter service. Survivable optical networks encounter new challenges along with the evolution of optical network infrastructure with respect to equipment cost, power consumption and resource usage [107, 129]. However, this involves a very complex interdependencies optimization as the resource usage affects the protection capacity efficiency, equipment cost and power consumption. In MLR WDM optical networks, transponders operating at different line rates have different cost and transmission reach of the transmitted signal [18]. The situation becomes even more complex in EON because the BandwidthVariable Transponders (BVTs) work depending on not only the Frequency Slot (FS) usage but also the modulation format used, which will affect spectrum usage, cost, energy consumption and transmission reach together, and the use of Bandwidth-Variable Optiix cal cross-Connects (BV-OXCs) in EONs also results in higher cost and energy consumption [129]. To deal with these challenges in next generation optical network protection, the objective of this thesis is to design efficient protection schemes in the consideration of spare capacity, network cost and network power consumption. The rest of this chapter is organized follows: • Motivation and Objectives • Contributions of the Thesis • Organization of the Thesis Motivation and Objectives Owing to the advanced technologies in optical networks, the transmission capacity has largely increased in which a single optical fiber can carry over 20 Tbps traffic transmission [10]. The network failures, such as fiber cut and large-area disaster, will cause huge loss for service providers and costumers. Thus, survivability of optical networks is of critical importance. This thesis concerns the design of efficient protection schemes using p-cycles and backup paths for next generation optical networks. Conventional protection schemes were mostly explored for minimizing protection capacity while our study focuses on joint optimization of both protection capacity and network performance metrics such as equipment cost, power consumption and spectrum usage. The main advantage of joint optimization is that it leads to more resource-efficient designs from the perspective of the network operator. However, it corresponds to a much more complex design problem thus efficient algorithms or decomposition approaches are needed against the scalability issue. We first study p-cycle protection against single link failure. p-Cycle protection scheme has fast switching speed, and it provides protection capacity for both on-cycle links and straddling links [52]. Most of conventional p-cycle design schemes require to enumerate a candidate cycle set in advance and then optimize protection capacity to select p-cycles from the candidate set. However, optimal solution can not be reached with these methods as only partial cycles are formed in the candidate cycle set due to the scalability issue in large networks. We propose p-cycle design principle without cycle enumeration and integrate it with protection capacity constraint in mathematical formulation, which is guaranteed to obtain the optimal solution. Moreover, the advanced architecture of optical networks introduces additional network performance metrics for p-cycle protection. MLR optical networks add the line rate selection for p-cycle protection, which relates to not only wavelength usage but also transponder cost as well as transmission reach. EONs involve the spectrum allocation and modulation format selection as well power consumption, which further increases the complexity of the p-cycle protection problem. To achieve the high cost efficiency and power efficiency in survivable MLR and EONs, this thesis proposes joint optimization of p-cycle protection formulation and efficient algorithms. x To overcome the large area disaster threat on cloud service, path protection schemes are studied for survivable elastic DCNs, in which the service can be served by other Data Center (DC) replicas upon a disaster. In addition to spectrum allocation in survivable EONs, elastic optical DCNs are being faced with the problem of content placement, routing, protection of path and content. We first formulate the mathematical model for this problem and design DEBPP and SEBPP schemes. Then, to increase the scalability, DEBPP and SEBPP models are decomposed by Column Generation (CG) approach using a master problem and a pricing problem. This is solved iteratively, augmenting the number of columns until optimality of the original problem is proved with the available columns. To speed up the iteration, an algorithm is designed in the pricing problem to select the most promising columns rather than using all the columns. It has shown that CG is an intelligent way of generating promising working and backup lightpaths for survivable elastic optical data networks. Contributions of the Thesis This thesis investigates several protection schemes for next generation optical networks against single link failure and large area disaster failure. The contributions of these protection schemes in this thesis are listed and explained in detail below. 1. Cost-effective p-cycle protection: The unidrected p-cycle design model without candidate cycle enumeration is studied in MLR optical networks with respect to the transmission reach and transponder cost. Path-length-limited p-cycle is proposed to efficiently optimize the line rate selection, in which the transmission reach restricts the length of each protection path instead of the circumference of the cycle p-cycle. The Capital Expenditures (CAPEX) cost and the spare capacity are minimized by designing a Mixed Integer Linear Programming (MILP) model, which considers the cycle generation constraints, line rate assignment and protection capacity constraints together. In addition, Graph Partitioning in Average (GPA) heuristic algorithm is incorporated with the computation of number of required p-cycles approach to enable concurrent computation in sub-graphs with the proposed MILP model. Simulation results show that the proposed p-cycle protection scheme achieves significant CAPEX cost savings for MLR optical networks, especially the transponder cost savings, in comparison to conventional p-cycle protection with SLR and p-cycle protection with candidate cycle enumeration. 2. Power efficient p-cycle protection: A novel directed p-cycle protection scheme is proposed for asymmetric traffic in power-efficient EONs. Directed p-cycles benefit from distinguishing traffic amount in two directions and thus they are promising to consume low power by allocating different FSs and modulation formats for each direction. The directed p-cycle design, spectrum allocation, modulation adaptation and protection capacity are concerned by formulating an MILP model, which aims at minimizing the power consumption of optical equipments and the FS usage. The scalability issue of the MILP is solved by an improved cycle enumeration and a simplified Integer Linear Programming (ILP) model. The simulation results indicate the directed pxi cycles achieve power savings up to 47.9% in comparison with conventional undirected p-cycles. Moreover, it has been shown that the amount of power savings in directed p-cycles goes up when increasing the traffic asymmetry and anycast ratio of traffic patterns. 3. Spectrum shared p-cycle protection: A novel Spectrum Shared p-cycle (SS-pcycle) protection scheme is proposed for survivable EONs with and without spectrum conversion. SS-p-cycles have the property that two p-cycles can share the same spectrum if and only if all of their protection paths do not have common links against any single link failure. SS-p-cycles permit to reduce spectrum usage and Spectrum Fragmentation Ratio (SFR) by leveraging potential spectrum sharing among multiple pcycles. The design of SS-p-cycles is enabled by the ILP models, which check the promising spectrum sharing in terms of the protected link(s), and allocates the FSs for each SS-p-cycle. To overcome the lack of scalability in SS-p-cycle ILP, a fast and efficient SSp-cycle Spectrum Allocation (SS-SA) algorithm is proposed to perform cycle selection and FSs allocation. The results indicate that SS-p-cycles significantly improve spectrum efficiency compared with conventional no-shared p-cycles in terms of maximum index of FSs and spectrum efficiency. The results also show that the spectrum conversion does help SS-p-cycle design to acquire better spectrum utilization, but it shows different impacts on maximum index of FSs and spectrum efficiency under different network nodal degree and network with/without spectrum conversion. 4. Disaster-survivable path protection: Disaster protection schemes, including DEBPP and SEBPP, are proposed for elastic optical DCNs. Mathematical models are formulated for DEBPP and SEBPP, respectively, taking into account content placement, routing, protection of path and content and spectrum allocation. The DEBPP and SEBPP models are further decomposed to increase the scalability, which is conducted by CG approach using a master problem and a pricing problem. The master problem optimizes the spectrum usage by selecting the working and backup paths from the paths set while pricing problem takes charge of generating new working and backup paths that may achieve a better solution. It has shown that CG achieves comparable results within an much shorter time than the joint ILP models. The spectrum usage of DEBPP and SEBPP is evaluated regarding the number of traffic amount, DCs, replicas, and different network topologies. Organization of the Thesis The thesis carried out studies on single link failure and large area disaster failure protection in next generation optical networks. Both p-cycle protection and path protection schemes are investigated. This thesis is organized according to the types of failure scenarios and protection schemes in terms of MLR optical networks, EONs and elastic DCNs. The rest of the thesis is divided into four parts: Background and Technological Context (Chapter, 1), p-Cycle Protection Scheme for MLR WDM against Single Link Failure (Chapter, 2), p-Cycle Protection Schemes for EONs against Link Failure (Chapters, 3, xii and 4) and Path Protection Schemes for Elastic DCNs against Disaster Failure (Chapter, 5). The first part with Chapter 1 provides background information on optical networks, which covers the evolutions of optical backbone networks, key technologies of EONs, survivability in optical networks and literature review of classical protection schemes. The evolution of optical networks includes traffic-driven optical networks from SLR WDM to MLR WDM, and then EONs. Then, the property of flexible grid and bandwidth variable equipments in EONs are addressed. The survivability in optical networks is categorized into protection and restoration and involves the classic protection schemes and the challenges of survivable EONs. The literature review includes the existing p-cycle protection scheme and protection schemes that concern resource usage, cost, power consumption and cloud services issues. The second part with Chapter 2 concerns the low-cost p-cycle protection for MLR optical network. It addresses the voltage-based undirected p-cycle design without candidate cycle enumeration in MLR optical networks, which concerns the line rate selection, transmission reach, transponder cost and wavelength assignment. The objective is to minimize the transponder cost and wavelength channel cost in p-cycle protection for MLR optical networks. Both ILP formulation and a network partition algorithm are developed to address this issue. The work of this chapter can be found in the publications [J3] and [C5]. Concerning the network evolution from WDM optical networks to EONs, the third part comprising Chapters 3 and 4 address the p-cycle protection for EONs in terms of low power consumption and efficient spectrum usage. Specifically, Chapter 3 addresses the directed p-cycle design under asymmetric traffic scenario in EONs and concerns the power consumption and spectrum usage in survivable EONs. The objective is to minimize the spectrum usage and power consumption related to BVTs, BV-OXCs and Optical Amplifiers (OAs), which is accomplished by designing the MILP models and decomposition algorithms. The benefits of using directed p-cycle rather than unidrected p-cycle for asymmetric traffic protection is analyzed and evaluated. The work of this chapter can be found in the publications [J2] and [C3]. Chapter 4 concerns the efficient spectrum sharing among multiple p-cycles. The specific formulations for SS-p-cycles are developed in addition to the conventional spectrum allocation in survivable EONs with and without spectrum conversion. The performance of spectrum usage in SS-p-cycles is evaluated in comparison with conventional spectrum no-shared p-cycles. The work of this chapter can be found in the publications [J1] and [C2]. Concerning the current large area disaster failure issue in DCNs, the fourth part with Chapter 5 further addresses the disaster-survivable DEBPP and SEBPP schemes in DCNs with EONs. The mathematical models of DEBPP and SEBPP schemes are first formulated. Then, the DEBPP and SEBPP formulations are further decomposed by CG approach to increase the scalability. A master problem, optimizing the spectrum usage of the selection of the working and backup lightpaths, and a pricing problem that generates the promising new working and backup lightpaths are addressed. Finally, Chapter 6 concludes the thesis and envisages the future work. xiii xiv Contents Résumé iii Abstract v Acknowledgements vii Introduction ix I Background and Technological Context 1 1 Background and Technological Context 1.1 Evolution from fixed-grid to flexible-grid in optical networks . . . . . . . 1.1.1 Fixed-grid WDM optical networks . . . . . . . . . . . . . . . . . . 1.1.2 Flexible-grid EONs . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Key technologies of EONs . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Elastic optical path provisioning . . . . . . . . . . . . . . . . . . . 1.2.2 Enabling hardware technology . . . . . . . . . . . . . . . . . . . . 1.3 Survivability in optical networks . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Protection and restoration . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 Classic protection schemes . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Challenges of next generation optical network protection . . . . . 1.4 Literature review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Cost-effective protection and power-efficient schemes for MLR WDM networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Cost-effective and power-efficient protection schemes for EONs . 1.4.3 Disaster-survivable cloud provisioning for optical DCNs . . . . . II 3 4 5 8 10 10 11 13 14 15 23 26 27 28 30 p-Cycle Protection Scheme for MLR WDM against Single Link Failure 33 2 Low-Cost p-Cycle Design Without Candidate Cycle Enumeration in MLR Optical Networks 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv 35 36 36 38 2.4 2.5 2.6 2.7 III MILP formulation . . . . . . . . . . . . . . . . . . . 2.4.1 MILP model . . . . . . . . . . . . . . . . . . 2.4.2 Computational complexity . . . . . . . . . 2.4.3 Path-length-limited p-cycle . . . . . . . . . 2.4.4 Discussion . . . . . . . . . . . . . . . . . . . Algorithms for time-efficient MILP model . . . . . 2.5.1 GPA algorithm . . . . . . . . . . . . . . . . 2.5.2 EI algorithm . . . . . . . . . . . . . . . . . . Simulation and performance evaluation . . . . . . 2.6.1 The efficiency of GPA and EI . . . . . . . . 2.6.2 p-Cycle design with GPA and EI . . . . . . 2.6.3 Comparison to SLR-NCE-40 and MLR-CE Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p-Cycle Protection Schemes for EONs against Single Link Failure 41 41 44 45 48 49 50 51 52 53 53 57 62 63 3 Power-Efficient Protection With Directed p-Cycles for Asymmetric EONs 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 MILP formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 MILP model . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 A two-step approach . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Improved cycle enumeration . . . . . . . . . . . . . . . . 3.5.2 Decomposed EDPC (De-EDPC) . . . . . . . . . . . . . . . 3.5.3 Computational complexity . . . . . . . . . . . . . . . . . 3.6 Simulation and performance evaluation . . . . . . . . . . . . . . 3.6.1 Quality of solution in De-EDPC . . . . . . . . . . . . . . . 3.6.2 Impact of TASY on power savings in De-EDPC . . . . . 3.6.3 Impact of anycast ratio on power savings in De-EDPC . 3.6.4 Impact of DCs number on power savings in De-EDPC . 3.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Spectrum-efficient p-Cycle Design in EONs 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Problem statement . . . . . . . . . . . . . . . . . . . . . . 4.4 ILP formulation . . . . . . . . . . . . . . . . . . . . . . . . 4.4.1 SS-PC-ILP Model (without spectrum conversion) 4.4.2 SS-PC-SC-ILP model (with spectrum conversion) 4.4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . 4.5 Heuristic algorithm . . . . . . . . . . . . . . . . . . . . . . 4.6 Simulation and performance evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 . 92 . 93 . 94 . 96 . 97 . 98 . 99 . 100 . 101 xvi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Traffic in 65 66 67 69 73 73 77 78 78 80 80 81 82 83 85 87 89 4.6.1 4.6.2 4.6.3 4.7 FSs allocation with different weighting θ1 and θ2 . . . . . . . . . . FSs allocation advantage in SS-p-cycles . . . . . . . . . . . . . . . Spectrum allocation in SS-p-cycles with/without spectrum conversion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6.4 Performance evaluation of SS-PC-SA algorithm . . . . . . . . . . Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 103 104 106 107 IV Path Protection Schemes for Elastic Optical DCNs against Disaster 109 5 Column Generation for Cloud Services in Disaster-Survivable Elastic Optical DCNs 111 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 5.2 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.3 Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.4 Joint ILP formulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.4.1 DEBPP ILP model . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 5.4.2 SEBPP ILP model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.4.3 Computational complexity . . . . . . . . . . . . . . . . . . . . . . 122 5.5 Decomposition approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5.5.1 Step 1. DC assignment and content placement . . . . . . . . . . . 123 5.5.2 Step 2. Initial solution . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.5.3 Step 3. Master problem . . . . . . . . . . . . . . . . . . . . . . . . 124 5.5.4 Step 4. Pricing problem . . . . . . . . . . . . . . . . . . . . . . . . 126 5.5.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 5.6 Simulation and Performance Evaluation . . . . . . . . . . . . . . . . . . . 130 5.6.1 Simulation setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.6.2 The efficiency of CG approach compared with ILP . . . . . . . . . 132 5.6.3 Spectrum usage VS no. requests . . . . . . . . . . . . . . . . . . . 133 5.6.4 Spectrum usage VS number of DCs location and content replicas 134 5.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 V Conclusions and Perspectives 139 6 Conclusions and Perspectives 141 6.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 List of Figures 145 List of Tables 149 Bibliography 151 Acronyms 165 xvii Lists of Publications 169 xviii Part I Background and Technological Context 1 Chapter 1 Background and Technological Context Contents 1.1 1.2 1.3 1.4 Evolution from fixed-grid to flexible-grid in optical networks . . . . 4 1.1.1 1.1.2 Fixed-grid WDM optical networks . . . . . . . . . . . . . . . . . Flexible-grid EONs . . . . . . . . . . . . . . . . . . . . . . . . . . 5 8 Key technologies of EONs . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.1 Elastic optical path provisioning . . . . . . . . . . . . . . . . . . 10 1.2.2 Enabling hardware technology . . . . . . . . . . . . . . . . . . . 11 Survivability in optical networks . . . . . . . . . . . . . . . . . . . . . 13 1.3.1 1.3.2 1.3.3 Protection and restoration . . . . . . . . . . . . . . . . . . . . . . Classic protection schemes . . . . . . . . . . . . . . . . . . . . . Challenges of next generation optical network protection . . . . 14 15 23 Literature review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.4.1 1.4.2 Cost-effective protection and power-efficient schemes for MLR WDM networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Cost-effective and power-efficient protection schemes for EONs 28 1.4.3 Disaster-survivable cloud provisioning for optical DCNs . . . . 3 30 Chapter 1. Background and Technological Context 1.1 Evolution from fixed-grid to flexible-grid in optical networks 1 Ebit/s Transmission capacity per fiber 100 Pbit/s 10 Pbit/s Innovative optical transmission technologies (new transmission fibers, new multiplexing technologies) 1 Pbit/s Optical amplification bandwidth limitation Current optical fiber input power limit 100 Tbit/s Nonlinear optical effect, Shannon limit, fiber fuse Digital coherent technology 10 Tbit/s 1 Tbit/s WDM technology Optical amplification technology 100 Gbit/s 10 Gbit/s Electrical multiplexing TDM technology 1 Gbit/s Approx. 4 orders of magnitude in 30 years 100 Mbit/s 1980 1990 2000 2010 2020 2030 2040 Year of deployment Figure 1.1: Evolution in optical transmission technology [92]. Several decades have witnessed the rapid development of optical networks towards high speed, high-capacity and long-distance since optical transmission was realized in 1970s [103]. As shown in Fig. 1.1, over the past several decades, the optical transmission technology has developed rapidly mainly through several technological innovations: Time Division Multiplexing (TDM) technology based on electrical multiplexing, optical amplification technology combined with WDM technology, and remarkably successful coherent technology with Digital Signal Processing (DSP) [64, 73, 92]. In the early 1990s, the transmission capacity of optical networks was dramatically increased in a cost-effective manner enabled by the development of WDM and Erbium-Doped Fiber Amplifier (EDFA) [9, 95]. WDM allows to concurrently multiplexe many optical wavelengths over a single optical fiber and each of the wavelengths is viewed as a separate channel for data transmission. In the early stage, WDM transmission systems operate in fixed grids with SLR transponders either 10Gb/s, 40Gb/s or 100Gb/s. It is broadly expected that with the advent of new networking capabilities and demanding cloud services, the evolution of optical networks will lead towards MLR WDM network and EON architectures [44, 107]. MLR WDM network is energy- and cost-effective by applying co-existing line rates (10/40/100 Gbps) transponders and multiple modulation formats [77, 96]. However, with high-bandwidth and on-demand applications continuing to emerge, WDM networks have limitations such as low spectrum utilization and rigidity in provisioning 4 1.1. Evolution from fixed-grid to flexible-grid in optical networks 24% CAGR 24% 2016-2021 CAGR 2016-2021 300 278 250 228 200 Exabytes per month 186 150 151 122 100 96 50 0 2016 2017 2018 2019 2020 2021 Figure 1.2: Cisco global IP traffic forecast, 2016-2021 [22]. for growing heterogeneous traffic demands. According to Cisco’s report [22], the overall IP traffic is expected to grow to 278 Exabytes per month by 2021, up from 96 EB per month in 2016, a Compound Annual Growth Rate (CAGR) of 24 percent, as illustrated in Fig. 1.2. Representing the elastic allocation with sub-wavelength, super-wavelength, and multiple-rate data traffic accommodation, a more flexible optical network architecture was first named the spectrum sliced elastic optical path network architecture (SLICE) and is currently called the EON for simplicity [65, 66]. EONs enable flexible spectrum usage and adaptive modulation formats, which has been regarded as one of the most promising candidates for the next generation optical networks with respect to network spectrum cost, size, and power requirements [21, 127]. 1.1.1 Fixed-grid WDM optical networks ch.-3 ch.-2 ch.-1 10 40 100 400 Gbps Gbps Gbps Gbps 192.95THz 193 THz ch.0 193.05THz 193.1THz ch.1 193.15THz ch.2 193.2THz ch.3 193.25THz (anchor frequency) 50 GHz channel spacing Figure 1.3: ITU-T fixed-grid [117]. In WDM optical networks, separate wavelengths or channels of optical signals are multiplexed and simultaneously transmitted in a single optical fiber. There is already commercial 100-Gb/s Dense Wavelength-Division Multiplexing (DWDM) transmission systems with a per fiber capacity of 10 Tb/s using the conventional 50 GHz frequency grid, as illustrated in Fig. 1.3 [1, 64]. DWDM technology is enabled by the advance of 5 Chapter 1. Background and Technological Context optical components, such as Distributed Feedback (DFB) lasers, EDFAs, WavelengthSelective Switches (WSS)-based Reconfigurable Optical Add/Drop Multiplexer (ROADM), and coherent techniques [120]. For each wavelength, the transmission line rate has been increased from 2.5 Gbps up to 100 Gbps with the improvements in transponder technology [58]. However, current DWDM systems with fixed grids are not able to accommodate heterogeneous traffic in an spectrum-efficient manner. Some traffic demands may occupy much less bandwidth than that provided by a full wavelength, which results in the bandwidth and spectrum waste while some may require multiple wavelengths. For example, one 50 GHz wavelength channel should be used for the 10 Gbps demand, while it can accommodate an 100 Gbps Dual-Polarization Quadrature Phase Shift Keying (DP-QPSK) signal, but it is not sufficient to transmit a 400 Gbps signal within the same spectral spacing. 1). SLR WDM 10 10 10 10 10 10 10 Gbps sceanrio Gbps Gbps Gbps Gbps Gbps Gbps 40 40 40 40 40 40 40 Gbps sceanrio Gbps Gbps Gbps Gbps Gbps Gbps 100 100 100 100 100 100 100 Gbps sceanrio Gbps Gbps Gbps Gbps Gbps Gbps Figure 1.4: SLR-WDM grid. SLR WDM offers only one line rate with specific transmission reach for all types of demands. The network can be configured with either 10 Gb/s, 40 Gb/s or 100 Gb/s line rate sceanrio, as shown in Fig. 1.4. SLR WDM needs to address the basic Routing and Wavelength Assignment (RWA) problem. The general definition of the RWA problem is as follows, given a set of communication requests, set up lightpaths by routing and assigning wavelengths to them, so as to minimize the network resources used or maximize the requests served. A lightpath is an optical communication path between two nodes without the Optical-Electrical-Optical (O/E/O) conversion, established by allocating the same wavelength throughout the route of the transmitted data. A lightpath is uniquely identified by a wavelength and a physical path. Two important issues should be addressed during the wavelength assignment process [20] : • Wavelength continuity constraint: A lightpath must be assigned a common wavelength on each link it traverses except the utilization of wavelength converters 6 1.1. Evolution from fixed-grid to flexible-grid in optical networks [101]. • Distinct wavelength constraint: Two lightpaths sharing a fiber link must occupy different wavelengths. These two constraints of wavelength allocation are involved with the lightpath generation whose length should be less than the maximum transmission reach at a specific line rate. The RWA problem can be solved jointly or separately towards the routing problem and wavelength assignment problem. The objective of RWA problem can involve several issues, such as minimizing wavelength usage, minimizing network cost, minimizing energy, enabling survivability, etc [11, 24, 90]. 2). MLR WDM 10 Gbps 40 Gbps 100 Gbps 10 40 40 Gbps Gbps Gbps Figure 1.5: MLR-WDM grid. Currently, WDM networks support mixed 10/40/100 Gbps per wavelength in the existing 50 GHz channels, as illustrated in Fig. 1.5. In MLR WDM, different types of transponders are configured to provision traffic at several line rates balancing the requirements on the capacity and transmission distance of the demand [18, 81, 151]. Thus, a single fiber link may carry various line-rate signals of 10/40/100 Gbps. MLR is leveraged to design a cost-effective network by exploiting the volume discount1 of 40 and 100 Gbps transponders [81]. Then, the WDM network cost could be reduced because low-bitrate services will require less grooming ( i.e., less multiplexing with other low-bitrate services onto high-capacity wavelength), while high-bitrate services can be provisioned on an individual wavelength channel [96]. With the introduction of co-existing mixed line rates, the basic RWA problem in SLR WDM is enhanced to the Routing, Wavelength, and Rate Assignment (RWRA) problem [81]. However, due to the nonlinear effects induced by the co-propagating wavelengths with co-existing mixed line rates, the transmission reach and performance of 10/40/100 Gbps in MLR are further limited. According to the study in [18], the pure transmission reach of 10 Gbps with On/Off Key (OOK), 40 Gbps with Differential Phase Shift Keying (DPSK), and 100 Gbps with DP-QPSK are 1800 km, 2200 km, and 7000 km, respectively under a threshold Bit-Error Rate (BER) of 10−3 . Higher transmission reach of 100G is owing to the coherent reception technology which could be incorporated in commercially available 100 Gbps transponders. Nevertheless, in MLR WDM, the co-existing mixed line rates restricted the transmission reach of 10/40/100 Gbps to 1750/1800/900 1 Volume discount means the cost of a resource increase at a line rate that is lower than the linear increase of the rate, e.g., the cost of a 100 Gbps transponder can eventually be 4.5 times that of a 10 Gbps transponder under steady-state conditions, which is less than the line rate increase of ten times [81]. 7 Chapter 1. Background and Technological Context Unutilized spectrum Unutilized spectrum 100 10 100 100 10 Gbps Gbps Gbps Gbps Gbps 50 GHz channel spacing (a) Spectrum allocation in WDM fixed-grid optical networks Gurd band (b) Overlapping subcarriers caused by OFDM technology Figure 1.6: Flex-Grids in EONs [12]. km, respectively [18]. In addition to wavelength continuity constraint and distinct wavelength constraint in SLR WDM optical networks, MLR WDM optical networks should consider the follow single line rate continuity issue: • Single line rate continuity constraint: only single line rate can be used for a lightpath along all the traversing links even though multiple line rates are available. The introduction of MLR offers an opportunity to design resource-efficient optical networks even though the involved RWRA problem increases the complexity of network design. The MLR network architecture has been shown to be energy- and cost-efficient in satisfying heterogeneous traffic demands than SLR network architecture [18, 87]. The joint optimization of line rate selection, lightpath generation and wavelength assignment contribute to the cost savings and energy savings in optical equipments. 1.1.2 Flexible-grid EONs The burgeoning number of on-demand applications and instantaneously increasing cloud services require major evolution of the backbone network towards high bandwidth, high flexibility and high survivability [107, 127]. The conventional WDM optical 8 1.1. Evolution from fixed-grid to flexible-grid in optical networks networks would waste a large portion of the spectrum if the channels carry only low bandwidth, and no traffic can be transmitted in the unused frequency gap between two adjacent channels, as reflected in Fig. 1.6. EONs can overcome the spectrum allocation limitations of the conventional WDM optical networks by utilizing the promising transmission techniques such as Nyquist Wavelength-Division Multiplexing (NWDM), Orthogonal Frequency-Division Multiplexing (OFDM), and Time Frequency Packing (TFP) [108]. EON architecture is one of the most promising candidates for optical networks to provision increasing traffic with fine-granularity flexible spectrum allocation and adaptive modulation formats. The term elastic refers to two key properties: • Elastic spectrum: The optical spectrum can be divided into FS, having a spectral width of e.g. 12.5 GHz, 6.25 GHz or 5 GHz, and the channel can be a combination of a set of continuous FSs. • Elastic optical components: The elastic optical paths can be accommodated with bitrate-variable equipments such as BVTs and BV-OXCs. EONs alleviate the fixed-grid bandwidth issue of current WDM optical networks. Instead, EONs allow arbitrary contiguous concatenation of optical spectrum according to the traffic volume or user request in a highly spectrum-efficient and scalable manner [66]. The efficient spectrum usage in EONs comes from two factors. The first one is the Guard Bands (GB) are not "wasted" on two separate channels for the connection between two nodes. The second reason is that the spectrum assigned to each connection is "tailored" to their respective bandwidth, quality and reach requirements. The main characteristics of EONs are efficient accommodation of multiple data rates, elastic variation of allocated resources, reach-adaptable line rate, etc. Apart from the difference of allocating spectrum resources as the WDM optical networks, EONs employ adaptable transponders with different line rates and adaptive modulation formats. Thus, a number of transmission parameters, such as line rate, the FSs, the modulation format, will interact with each other, which directly or indirectly affects the resource allocation decision [125, 127]. EONs will bring lots of benefits for optical networks towards rate adaptive, distance adaptive, and availability adaptive service provision [65]. Nevertheless, EONs result in the increased complexity of network design and operation as the conventional RWA problem is modified to Routing and Spectrum Assignment (RSA) problem in EONs. Similar to the conventional wavelength continuity constraint, RSA needs to address the following spectrum allocation constraints [12]: • Spectrum continuity constraint: All the links along a lightpath should use the same FSs. • Spectrum contiguity constraint: The FSs allocated to a lightpath should be contiguous FSs. As a result, the introduction of spectrum allocation dictates the enhancement of the network planning and optimization procedure to consider the resource-efficient network design. Cost- and energy-efficient EONs can be achieved by selecting the optimal combination of the parameters modulation level and the number of FSs. Recently, 9 Chapter 1. Background and Technological Context several experimental demonstrations of EONs have been done to test the viability of the novel flexible optical networks with Software-Defined Network (SDN) technologies (e.g., OpenFlow) [5]. However, there are still several challenges of EONs demonstration related to the routing, code and spectrum allocation, multi-domain and multitechnology orchestration, BVTs technology, monitoring aspects, etc [25]. To conclude, EONs are regarded as the promising solution to provision such traffic with flexible spectrum allocation. However, the requirements on BVTs and BV-OXCs are the main challenges of upgrading current WDM optical networks to EONs. Meanwhile, MLR optical networks with co-existing line rates (10/40/100 Gbps) can be the transitional solution, which has been proven to achieve the comparable performance as EONs [75]. 1.2 Key technologies of EONs The evolution towards EONs will bring several benefits for optical networks, such as the spectral savings, enhanced network availability, etc. These benefits require the key technologies existing in elastic optical provisioning, hardware equipment and network management and control, which are presented as follows. Client node Optical path 50 G 100 G Segmentation 10 G Sub-wavelength 20 G 30 G 10 G 100 G Multiple data rate Fiber Fiber Aggregation 300 G Super-wavelength Variation 100 G Elastic variation 100 G L2 link aggregation 100 G Variation Rigid frequency grid (a) Flexible spectrum assign Conventional optical path network (b) SLICE Figure 1.7: Elastic optical path provisioning [66]. 1.2.1 Elastic optical path provisioning EONs allow to accommodate each demand with a "proper size" of the spectrum based on its bitrate and the transmission distance. For a demand of more than 400 Gbps, WDM optical networks need to demultiplex it into small ones in order to fit the fixed 10 1.2. Key technologies of EONs grid. In contrast, EONs support the high-capacity demands of 400 Gbps, 1 Tbps in a flexible optical grid, which eliminates most of the inefficient optical GBs and allows optical spectrum to be allocated to wavelengths as needed in FS increments [23] 2014. Thus, EONs allow to provision traffic demands with sub-wavelength, superwavelength and multiple data rates, as illustrated in Fig. 1.7 [66]. • Sub-wavelength provisioning: For the traffic requiring only a fractional of bandwidth, EONs permit to accommodate it with just enough optical bandwidth. Every node on the lightpath allocates a cross-connection with an appropriate spectrum bandwidth to create an appropriate-sized end-to-end optical path. It allows to efficiently use the network resources by the cost-effective provisioning of fractional bandwidth service. • Super-wavelength provisioning: EONs enable the super-wavelength provisioning by aggregating traffic from multiple physical ports/links in a switch/router into a single logical port/link. The super-wavelength provisioning can ensure high utilization of spectral resources. The aggregation technology can be realized by the OFDM SLICE transponders. • Multiple data rate provisioning: EONs also allow to spectrally efficiently accommodate the mixed data bitrates owing to flexible spectrum allocation. 1.2.2 Enabling hardware technology 1). Bandwidth Variable Transponders 100 Gbit/s 100-400 Gbit/s 400 Gbit/s (a) Distance-variable transponder (a) Transmission-rate-and-distancevariable transponder Figure 1.8: BVT [92]. BVTs, including flexible bandwidth transmitters and receivers, are used to tune the transmission bandwidth by adjusting several transmission parameters, such as the modulation format, number of bits per symbol, and spectrum used, as shown in Fig. 1.8. BVTs are able to trade spectral efficiency at different modulation formats against transmission reaches. For example, QPSK or Binary Phase-Shift Keying (BPSK) modu11 Chapter 1. Background and Technological Context lation formats are more robust but less efficient, thus BPSK can support longer transmission distance, while 16-Quadrature Amplitude Modulation (16-QAM) modulation format is more efficient but with shorter transmission reaches [12]. Table 1.1: Transmission rate, power consumption and transmission reach of a BVT with a single FS 12.5 GHz [129, 146] Modulation Formats Transmission Power Consumprate (Gbps) tion (W) Transmission Reach (km) BPSK QPSK 8QAM 16QAM 12.5 25 37.5 50 9600 4800 2400 1200 112.374 133.416 154.457 175.498 BVTs for EONs can be implemented with several multicarrier solutions, such as Coherent Wavelength-Division Multiplexing (CoWDM) [41], Coherent Optical Orthogonal Frequency-Division Multiplexing (CO-OFDM) [118] and dynamic Optical Arbitrary Waveform Generation (OAWG) [43]. Even though there is similarity among multicarrier signal generation between CO-OFDM, CoWDM, and OFDM transmitters, their operation principles and capabilities differ from each other [44]. Finally, the concept of Sliceable Bandwidth-Variable Transponder (S-BVT) has emerged in order to enable higher utilization of flexible transceivers [108]. The major property of S-BVT is the ability to allocate the capacity into one or several independent optical flows that are transmitted towards one or multiple destinations. An S-BVT can generate multiple optical flows that can be routed into different lightpaths flexibly towards different destinations. S-BVT is represented by a class of transponders able to dynamically tune the required optical bandwidth and transmission reach by adjusting parameters of bitrate, modulation format, Forward Error Correction (FEC) coding, and shaping of optical spectrum [108]. The deployment of BVTs introduces a trade-off between spectral efficient modulation format and transmission reach as well as network cost and power consumption related to optical module of ADC, DAC, I/Q modulators and the electronic processing [108]. The higher level modulation formats lead to increased effective capacity and spectral efficiency, however, they result in reduced transparent transmission reach, increased equipment cost and power consumption. Table 1.1 presents the transmission rate, power consumption and transmission reach of a BVT with a single FS (bandwidth 12.5 GHz) at different modulation formats [129, 146]. 2). Bandwidth Variable Optical Cross-Connects BV-OXCs allow to switch transmitted signals within their frequency bandwidth to appropriate switch output ports. They can allocate an appropriate-sized cross-connection with the corresponding spectrum bandwidth to support an elastic optical lightpath provisioning. The switching window of BV-OXCs needs to be configured according to the spectral width of the incoming optical signal in a flexible manner [12]. As shown in 12 1.3. Survivability in optical networks To East BV WSS From East Frenquency From West BV WSS To West Output Fiber #1 Frenquency From North Input Fiber BV WSS BV WSS To North Output Fiber #2 BV WSS Output Fiber #3 Output Fiber #4 BV WSS BV WSS Client Signals BV Transponders (a) Bandwidth variable OXC (b) Bandwidth variable WSS Figure 1.9: BV-OXC and BV-WSS. [66]. Fig. 1.9, an BV-OXC is typically constructed out of several interconnected BandwidthVariable Wavelength Selective Switches (BV-WSS) and amplifiers. The BV-WSS is an 1 × N switch or filter providing a continuously tunable and variable seamless transmission spectrum. BV-WSSs can be implemented by one of the several technologies: optical Micro Electro Mechanical Systems (MEMS), Liquid Crystals On Silicon (LICOS), or silica Planar Lightwave Circuits (PLCs) [120]. BV-OXC design needs to consider the penalties introduced by the filtering characteristics and crosstalk between different channels, which can be alleviated by increasing the bandwidth of the optical filter and introducing higher GBs between super channels [122]. 1.3 Survivability in optical networks Survivability has critical importance for high-bandwidth optical backbone networks to provide resilience against network failures. The failures in fiber-optic networks occur often due to the cable-based technology and co-located infrastructure with other network utilities [35]. Furthermore, the transmission capacity in today’s networks has largely increased in which a single optical fiber can carry over 20 Tbps traffic transmission, thus, the failures will cause huge loss for service providers and costumers [10]. The following text is organized as the concept of protection and restoration, classic protection schemes and challenges of next generation optical network protection. 13 Chapter 1. Background and Technological Context Protection/restoration schemes Restoration (best effort recovery) Protection (pre-planned capacity) Dedicated backup Shared backup Link restoration Link protection Path protection Link protection Path protection UPSR/BLSR, ring cover p-cycles 1+1/1:1 path protection Span restoration (SR) SBPP PR Path restoration Figure 1.10: Network protection/restoration schemes [116]. 1.3.1 Protection and restoration Over the last few decades, several protection techniques have been investigated for optical networks. They can be classified under two general categories: protection strategy and restoration strategy depending on the establishment operation before or after the occurrence of a failure [150]. Figure 1.10 shows a classification of survivable techniques in terms of protection strategy and restoration strategy [102, 116]. Both protection strategy and restoration strategy offer the survivable technique on link level and path level. In link survivable scheme, the source and destination nodes of the connection are oblivious to the link failure, and only the two ending nodes of the failed link do the recovery operation. In path survivable scheme, the source node and the destination node of each connection are informed about the failure via messages from the nodes adjacent to the failed link [102]. 1). Protection Protection is used to configure pre-assigned capacity to ensure survivability by reserving the spare capacity dedicated to cover a specific set of failure scenarios. Protection strategy reserves resources for recovery from failures at either connection setup or network design time, and keeps idle when there is no failure. It results in short recovery time 2 but relatively non-efficient spare capacity 3 . The network resources used in protection strategy may be dedicated for each failure scenario, named dedicated protection; alternatively, the network resources can be shared against failures among different failure scenarios, named shared protection. For instance, under assumption of single span failure, Shared Backup Path Protection (SBPP) allows protection paths to share the pro2 Recovery time is referred to as the time elapsed from when a failure occurs to the recovery of the failure. 3 Spare capacity is referred to the total reserved protection capacity in the whole network. 14 1.3. Survivability in optical networks tection capacity on their common spans as long as their corresponding working paths do not traverse any common span [115]. Shared protection schemes are generally more capacity-efficient than the dedicated protection schemes owing to the capacity sharing. 2). Restoration Restoration is used to reroute the affected traffic after failure occurrence by using available capacity which is not dedicated to any specific failure but can be configured as needed [102]. The spare capacity available within the network is utilized for restoring services once a failure occurs. Generally, restoration strategy is more efficient in utilizing spare capacity due to the multiplexing of the spare-capacity requirements and provide resilience against different kinds of failures, but it requires more recovery time as the spare capacity has to be determined dynamically according to the available spare capacity. Moreover, the dynamic restoration algorithms are usually complicated. Table 1.2: Performance comparison among different protection schemes ❛❛ ❛❛ Protection schemes ❛❛ ❛❛ ❛❛ ❛❛ Metrics ❛ Spare capacity efficiency Recovery time Protection stability Dedicated protection Shared protection Path protection Link protection Low Short Low High Long High High Long High Low Short Low We focus on protection schemes in this dissertation. Different protection schemes have their own properties and benefits, as shown in Tab.1.2. From the perceptive of spare capacity usage, path protection provides significant capacity savings over link protection, and shared protection provides significant savings over dedicated protection. From the perceptive of recovery time, dedicated protection requires less recovery time than shared protection, and link protection requires less recovery time than path protection. From the perceptive of protection stability, path protection is more susceptible to multiple link failures than link protection, and shared protection is more susceptible to multiple link failures than dedicated protection. In our work, we only focus on single link failure and single disaster zone failure. Node failure and multiple failure are not considerded since the single failure happens the most. 1.3.2 Classic protection schemes Protection schemes are by far the most studied for optical networks as dynamic algorithms for restoration are usually complicated. We focus on the protection schemes for next generation optical networks in this dissertation. Lots of protection schemes have been proposed for optical networks against different types of failures. Among 15 Chapter 1. Background and Technological Context these protection schemes, single link failure protection schemes have drawn more attention as it is a common failure of fiber cuts during the operation of optical networks. Furthermore, network-area disaster failures, such as earthquake, hurricane, tsunami or human-made disasters, have started to attract more attention in today’s DCNs due to the increasing traffic in cloud services [55]. We summarize the classical protection schemes in terms of failure type: 1). Link failure protection In an optical network, each link carries many lightpaths, and the failure of a single link causes the failure of all the lightpaths traversing the link. Both link protection and path protection can be used to protect link failure. • Link protection 1 2 3 Link failure Protection paths 5 4 6 (a) Link protection Protection path 1 with  Protection path 2 with  2 Protection path 1 with  Protection path 2 with  1 1 4 2 5 1 3 6 4 (b) Dedicated link protection 2 5 1 1 3 6 (c) Shared link protection Figure 1.11: Link protection against single link failure. The basic idea of link protection is that a protection path is reserved for each link, and when the link fails, traffic is rerouted around the failed link via the protection path. Link protection involves only the nodes adjacent to the failed link and switches the failed connections to the backup path around the link failure. Figure 1.11 shows an example of link protection against a link failure. In Fig. 1.11 (a), once the link failure occurs between nodes 5 and 6, the affected traffic is rerouted through the backup path 5-2-6 or the alternative one 5-1-2-3-6. The ending nodes 5 and 6 take charge of the recovery of the the failed link. The link protection schemes can be further classified as dedicated or shared link protection depending on if the spare capacity is shared or not. Dedicated link protection 16 1.3. Survivability in optical networks means that the spare capacity, i.e., a wavelength is dedicated to a protection path on a particular link. Thus, different wavelengths must be assigned to the protection paths if they have common link(s). As shown in Fig. 1.11 (b), protection path 1 is assigned with λ1 for a working channel traversing link 5-6 while protection path 2 is assigned with λ2 for a working channel traversing link 1-2. The benefit of dedicated link protection is that it may offer protection against the failure of multiple links. Both protection path 1 and protection path 2 can be used if the links 5-6 and 1-2 fail simultaneously. Shared link protection allows different protection paths to share the wavelength on the common link(s). As shown in Fig. 1.11 (c), the protection path 1 and protection path 2 can share wavelength λ1 on link 5–2. Shared link protection can utilize the spare capacity more efficiently than dedicated link protection [150]. • Path protection 1 2 3 Link failure Protection path 5 4 Working path 6 (a) Path protection Working path 1 Protection path 1 with  1 Working path 1 Protection path 1 with  1 Working path 2 Protection path 2 with  2 Working path 2 Protection path 2 with  1 1 4 2 5 3 1 6 4 (b) Dedicated path protection 2 5 3 6 (c) Shared path protection Figure 1.12: Path protection against single link failure. In contrast to link protection, the source and destination nodes of the failed connection in path protection are conscious of the failure occurrence. They switch the traffic to the protection path and active the spare capacity reserved upon a link failure. Figure 1.12 shows an example of path protection against link failure. In Fig. 1.12 (a), once the link failure occurs between nodes 5 and 6 on the working path 4-5-6, the affected traffic is rerouted through the protection path 4-1-2-3-6. As a special case, the protection path 4-1-2-3-6 has no common link with the working path 4-5-6, then it can use the same or different wavelength resource for protection. Path protection also has the dedicated scenario and the shared scenario. In dedicated path protection shown in Fig. 1.12 (b), for each working path, the spare wave17 Chapter 1. Background and Technological Context length is reserved on the links of the protection path. Different wavelengths should be assigned for the protection paths if they have common link(s). The protection path 4-1-2-6 is provided for working path 4-5-6 while the the protection path 1-5-2-6-3 is provided for working path 1–2–3. As the two protection paths have the common link 2-6, they must use different wavelengths λ1 and λ2, respectively. Dedicated path protection requires a large amount of extra capacity for protection purposes and the reserved spare capacity is kept idle. However, the dedicated path protection has more protection stability as it is able to provide recovery from not only single-link failures, but also some multi-link failures. The shared path protection, known as the SBPP, allows to share the spare capacity on the common links of protection paths as long as the corresponding working paths are link-disjoint. Because in this case, the two working paths can not fail at the same time then the survivability can be ensured. As an example in Fig . 1.12 (c), the two protection paths can now share λ1 on link 2–6. Therefore, they can just use the λ1 for the protection of both working paths, as opposed to the dedicated path protection. The SBPP is able to utilize the capacity more efficiently, while still achieving 100% survivability from single-link failure [150]. • p-Cycle protection p-Cycle 1 2 7 6 8 (a) p-Cycle structure Protection path 1 Protection path 2 1 3 5 4 Link failure Protection path 2 5 4 7 1 3 6 8 (b) Protecting an “on-cycle” failure 2 3 5 4 7 6 8 (c) Protecting a straddling failure Figure 1.13: p-Cycle protection against single link failure. The method of p-cycle protection has emerged as a topic of great importance over the past few years due to its ring-like short recovery time and mesh-like high efficiency in the use of spare capacity [52, 72]. There exist different types of p-cycle protection schemes, such as link-protecting p-cycle, path-protecting p-cycle and node encirling pcycle [72]. It is assumed that the optical nodes are relatively reliable so that most of the studies in the literature focus on link- and path-protecting p-cycles. We focus on link-protecting p-cycle protection in this dissertation. Figure 1.13 (a) illustrates the basic operation of a link-protecting p-cycle 1-2-3-6-5-87-4-1. All the links in this small network can be protected by the p-cycle as either "oncycle" link 4 or "straddling" link 5 . The protection for "on-cycle" link case is illustrated 4 5 An on-cycle link is a link of p-cycle, such as 1-2 and 2-3. A straddle link is a link which is connected between two nodes of p-cycle but does not belong to the 18 1.3. Survivability in optical networks in Fig .1.13 (b), in which the end nodes of the failed link 2-3 loop back the traffic to the protection path 2-1-4-7-8-5-6-3 on the p-cycle. Figure 1.13 (c) shows the case of "straddling" link protection, in which the end nodes of failed link 2-6 can loop back the traffic to two alternative protection paths 2-3-6 and 2-1-4-7-8-5-6 on the p-cycle. The protection capacity of p-cycle is configured in advance, and only the two end nodes of the failed link switch the working traffic to pre-configured protection path. Specifically, one unit of protection capacity is provided for each on-cycle link in one p-cycle, while two units of protection capacity are provided for each straddling link. Configuration in fiber e Configuration in fiber a b d c e Undirected p-Cycle Link Failure Protection path a b d c Directed p-Cycle Link Failure Protection path (b) Directed p-cycle protection (a) Undirected p-cycle protection Figure 1.14: Undirected and directed p-cycles. The previous concept of p-cycle in Fig. 1.13 refers to the undirected p-cycle strategy, and there exists another directed p-cycle strategy, as shown in Fig. 1.14. Undirected p-cycle is the common protection strategy, in which the same protection capacity is configured in the two directions according to the maximum traffic amount of the two directional links. It means that once the undirected p-cycle is determined, the same spare capacity are configured in the two parallel fiber links for opposite directions. Then, it enables to provide two units of protection capacity for each straddling link, like a − d in Fig. 1.14 (a). However, directed p-cycle only configures protection capacity in one direction in the directed on-cycle links. Although a directed p-cycle provides one unit of protection capacity for each directed straddling link, e.g., a → d and d → a in Fig. 1.14 (b), it can distinguish directional links and provide different protection capacity, which is beneficial for asymmetric traffic provisioning in two directions. Thus, the total protection capacity can be saved in directed p-cycles by efficiently allocating protection capacity for unidirectional links. Hence, directed p-cycles have the potential to protect the asymmetric traffic in a resource-efficient way. 2). Node failure protection In optical networks, nodes failure occurs because of the equipments failure at optical cross-connect nodes. For instance, the malfunction of a transmitting or receiving line card. The resilience for this failure case can be provided by a redundant number of line p-cycle, such as 1-5 and 2-6. 19 Chapter 1. Background and Technological Context cards. Alternatively, a node is protected if the network is able to switch the lightpahts crossing this node to protection paths with spare resources. Generally, node failures in a service layer such as the failure of a network interface card on a router can only be recovered by node elements in peer-level not by other layers such as WDM physical layer [72]. • Node-encircling p-Cycle Node failure p-Cycle 1 2 5 4 7 1 3 2 3 6 4 5 8 6 (b) (a) Figure 1.15: Node-encircling p-cycles. The conventional link-protecting p-cycle protection has been extended to provide protection against node failure, called "Node-encircling p-cycle" [70]. Node-encircling p-cycle maintain the resilience followed by the two properties: First, it must not include the failed node that is protected by the node-encircling p-cycle, and second, it must contain all of the node that were adjacent to the failed node. Therefore, it is able to substitute failed routes for all of the possible flows that traversed them before node failure. As illustrated in Fig. 1.15, the node-encircling p-cycle must cross all nodes immediately adjacent to the failed node but not the node itself. In Fig. 1.15 (a), the sevennode p-cycle 1-2-3-6-8-7-4-1 in blue crosses all six nodes adjacent to the failed node 5. Thus, upon failure of the encircled node, any lightpath transiting the failed node can be rerouted in either direction around the p-cycle. In addition to the simple p-cycle Fig. 1.15 (a) (i.e., it does not cross the same node and/or span more than once), non-simple p-cycle also logically encircles the failed node, as illustrated in Fig. 1.15 (b). 3). Network-area disaster failure protection In addition to the common single link failure and node failure, the network-area disaster failure is becoming a critical issue in communication networks. For instance, the earthquate and tsunami of 2011 in Japan and Sichuan earthquake of 2008 in China caused massive damage to telecom networks in large geographic areas. With the benefits from DCNs and the anycasting services, connection protection can be enhenced by serving from different DCs. Instead of providing a backup path from the source to the original DC node, using another DC node with replicated content is allowed to ensure 20 1.3. Survivability in optical networks disaster survivability. Since the first study about disaster-resilient network design was conducted in 2011 [54], different approaches have been proposed for disaster protection in the consideration of disaster-disjoint path generation and content placement in DCNs. Most of the disaster protection schemes are path protection by assigning the alternative backup path from the backup DC upon a large-area disaster. Note that there exist lots of anycasting protection approaches against single link failure or DC node failure that also offer a backup path from another DC. These approaches can be applied into disaster protection involved with disaster area. We classify the related path protection for disaster or anycasting below: • Dedicated/Shared End-to-content Backup Path Protection (DEBPP/SEBPP) [80] 3 2 1 Working path of r1 Protection path r1with  1 5 r1 6 4 Working path r2 Protection path r2 with  2 7 r2 10 9 8 (a) DEBPP 3 2 Working path of r1 Protection path r1with  1 1 5 r1 Working path r2 Protection path r2 with  1 6 4 7 r2 10 9 8 (b) SEBPP Figure 1.16: DEBPP and SEBPP in disaster protection. The path protection schemes against disaster failures concern the path protection and content protection simultaneously. A Disaster Zone (DZ) is defined as a set of nodes and links which might be affected simultaneously by a single disaster event. Thus, the primary and backup paths should be DZ-disjoint. Moreover, the specific content should be satisfied as the backup path uses a different DC node rather than the primary DC node. The end-to-content backup path protection can be divided into Dedicated End-to-content Backup Path Protection (DEBPP) and Shared End-to-content 21 Chapter 1. Background and Technological Context Backup Path Protection (SEBPP) according to the spare capacity allocation mechanism. As shown in Fig. 1.16, two requests originate from node 4 and node 10 respectively in the network with 3 available DCs and 8 DZs. The request r1 is provisioned through 4-1 to DC 1, while it is protected through 4-6-2 to DC 2. The request r2 is provisioned through 10-9 to DC 9, while it is protected through 10-6-2 to DC 2. Because the two protection paths have common link 6-2, the DEBPP scheme in Fig. 1.16 (a) uses different spectrum resources on them, while the SEBPP scheme in Fig. 1.16 (b) allows them to share the spectrum resource as their working paths do not fall into the same DZ. Thus, the DEBPP scheme reserves specific spare capacity for each backup path while the SEBPP scheme allows spare capacity sharing on common links among different backup paths as long as their primary paths do not fail simultaneously due to a single disaster. • Multiple-path protection [109] 3 2 Working path of r1 with 0.3B 1 5 Working path of r1 with 0.4B 0.3B Working path of r1 with 0.3B 0.4B r1 4 0.3B 6 7 10 9 8 Figure 1.17: Disaster-aware multipath provisioning scheme. (B is the bandwidth required by r1 .) Multipath protection scheme for disaster-aware service provisioning is conducted by multiplexing service over multiple paths destined to multiple DCs with manycasting [109]. Manycasting is referred to providing service from a subset of the DCs. Thus, the manycasting owns the advantage of resilience by allowing serving a cloud user from an intelligently selected subset of DCs having the requested service. Some services may accept a reduced level of bandwidth during failures, depending on their characteristics. As shown in Fig. 1.17, the multipath provisioning scheme is enabled by the cloud services over DCNs so that the request can be provisioned from several different DC nodes. The request r1 at node 4 can be provisioned by multipath routing through 4-1,46-2, and 4-6-9. Each of the multiple paths only provides partial bandwidth 0.3B, 0.4B and 0.3B respectively to maintain the survivability. As a result, for a multipath service provisioning, even if some paths are down due to a disaster failure, the other paths can maintain some bandwidth for degraded-service level. • Anycast-protecting p-cycle protection [119] 22 1.3. Survivability in optical networks 3 2 p-Cycle 1 5 Working path of r1 Protection path of r1 6 4 7 r1 10 9 8 Figure 1.18: Anycast-protecting p-cycle protection scheme. A p-cycle path protection for anycast traffic provisioning, named anycast-protecting p-cycles, was proposed in [119] even though there is no work about the p-cycle protection against disaster failure. It combines protection of physical links with protection of flow paths. The key idea of the anycast-protecting p-cycle is that it provided the backup path as long as the both the requesting node and the backup replica DC node are on a p-cycle. Thus, the protection can be provided on the flow level by the backup path as a straddling path or as an on-cycle path. In case of any link failure, the request can be provisioned from the replica DC instead of restoring the original working path. An example is shown in Fig. 1.18, where request r1 is provisioned though the DC 9 via 10-6-9. In order to provide the anycasting protection, the p-cycle 1-2-5-6-10-8-41 is designed to provide the protection path 10-6-5-2 for request r1 . The protection is enabled by the DC node 2 that is involved by the p-cycle. Note that the p-cycle can provide multiple protection for different requests as long as the request node and the backup DC are involved in the p-cycle. The advantage of the anycast-protecting p-cycle is that it can provide restoration of the entire working path using even one p-cycle for each request. Moreover, the backup DC can be available in any p-cycle protecting links of the entire working path [119]. 1.3.3 Challenges of next generation optical network protection In this dissertation, we focus on p-cycle protection for MLR optical networks and EONs, and path protection for disaster-survivable DCNs. Generally, both p-cycle protection and path protection provide efficient protection capacity with wavelength/spectrum to recover from the network failures. To concern the next generation optical network protection, we address several potential research challenge respect to network cost and energy issues, specific protection scheme for optical DCNs as well as the complexity of 23 Chapter 1. Background and Technological Context protection design methodology, as shown in Fig. 1.19. The first challenge is to address the cost and energy performance of networking design for protection schemes as the continually increasing traffic and the advanced technologies in optical networks are requiring more network cost and power consumption [116, 122, 129, 144]. Secondly, for the optical DCNs, specific protection schemes need to study for efficiently protecting the new traffic scenarios with the introduction of today’s new service, such as anycast service [131, 138]. To solve these survivability issues related to network performance metrics and new traffic scenarios, protection schemes can be explored with network design methodology either by mathematical formulation or heuristic algorithms. This addresses the third challenge of network protection design methodology as the multiple degrees of freedom and their interdependencies make the protection scheme designing more complicated. In the following text, we will address these three challenges and discuss about their impacts on next generation optical network protection. Network performance metric Spectrum Cost Power Challenge one Protection schemes for next generation optical networks Challenge two Challenge three Specific protection scheme for optical DCNs Complexity of mathematical methodology for protection design Figure 1.19: Main considerations of next generation optical network protection. 1). Spectrum-efficient, cost-efficient and energy-efficient network protection The ever-increasing traffic demands supported by optical networks dramatically introduce new challenges of capital investment and energy consumption in addition to deploying enough capacity [129]. These growing traffic demands also consume increasing energy, which keeps an average annual growth rate of 10% in today’s telecommunication networks since 2007 [144]. It becomes a key issue to investigate new protection mechanisms to improve the cost and energy efficiency for the next generation optical networks. The development of MLR optical networks and EONs permits to achieve potential cost and energy savings by more flexible network protection technology [27]. The network cost and power lie in optical equipments such as optical transponders, inline amplifiers and the nodal pre- and post-amplifiers, regenerator and the core switching elements. The network cost and power consumption mainly depend on the transmission line rate, which also restricts the transparent transmission reach [107]. It has been shown that EONs can achieve potential advantages with respect to energy and 24 1.3. Survivability in optical networks spectral efficiency as well significant cost savings for the operators. However, the cost efficiency of EONs strongly depends on the main cost contributor BVT, and it differs in traffic conditions and network topologies [129]. Thus, it is of great importance to design cost- and energy-efficient protection schemes for next generation optical networks. In both fixed-grid MLR WDM and EONs, network protection involves the solution of some sort of resource allocation problem, which lies in the transponders, the regenerators, and the spectrum units (wavelengths or FSs) on the links and the crossconnects [125]. Adaptable transponders can be used in MLR WDM and EONs so that the resource allocation decision can be affected by a number of transmission parameters directly or indirectly, such as the request capacity, transmission reach, modulation format, etc. Moreover, efficient resource allocation of wavelengths or FSs can achieve the savings of network protection cost and power [129]. This is because the resource usage, cost and energy interrelate the transmission reach, the transmission rate, and other parameters. Thus, the multiple degrees of freedom and their interdependencies make traffic protection establishment in new generation optical networks like MLR WDM and EONs more complicated than in conventional WDM networks. 2). Specific protection scheme for optical DCNs DCNs interconnects all of the DC resources (computational, storage, network) together to handle the growing demands of cloud computing for end users [79]. DCNs accommodate multiple DC tenants with a variety of workloads, in which DCs are the components that provide users with requested services/contents. The studies on DCNs in the literature have generated solutions for many use cases such as cloud computing, Content Delivery Networks (CDNs), distributed storage, etc [131]. DCNs offer many features to help to organize the new applications with the following benefits [133]: (i) DCNs permit to expand the traffic provisioning in an efficient way by the connection of thousands of DC servers, (ii) DCNs allows traffic reliability and efficiency to massive machine-to-machine communications with the distributed workloads on DC servers, (iii) DCNs support various virtualization techniques related to Virtual Machine (VM), virtual network, and virtual function. As an efficient traffic provisioning technique in DCNs, anycasting has been used to serve the customer with one-of-many destination DC as long as the service-level agreements (e.g., bandwidth and computing requirements) are satisfied [147]. Anycasting communication scheme permits to utilize the optical spectrum more wisely owing to that the destination DC of a request is implicit. However, these new anycasting-enabled network services involve asymmetric traffic provisioning in addition to the conventional symmetric traffic provisioning [131]. Conventional symmetric traffic protection schemes assign the same amount of protection capacity in two directions between the same pair of nodes [130]. However, compared with the symmetric approach, it has been proven that asymmetric traffic provisioning can bring resource savings (up to 50% of spectrum usage and up to 30% of CAPEX cost) in EONs [131], thus protection schemes that focus on asymmetric traffic have big potential to achieve power savings. 3). Complexity of the protection design methodology 25 Chapter 1. Background and Technological Context The protection scheme design concerns the different requirements on traffic characteristics and network property. The spare capacity allocation is involved in the optimization of resource usage related to the network cost, energy, etc. However, these areas are clearly interrelated and pose many trade-offs, such as the transmission reach with the spectral efficiency trade-off [125]. The spare capacity problem for the protection schemes is referred to the survivable RSA problem, which finds an appropriate working route and backup route for a source and destination pair and to allocate suitable FSs to the requested lightpaths. The RSA problem in EONs is quite similar to the RWA problem in WDM optical networks. The difference between RSA and RWA is due to the capability of the EON architecture to offer flexible spectrum allocation. In RSA, a set of contiguous FSs is allocated to a lightpath instead of the single wavelength by RWA in fixed-grid WDM networks [12]. The allocated FSs must be placed in an appropriate way to satisfy the spectrum contiguity constraint and spectrum continuity constraint. It has been stated that RSA is an N P -hard problem in [12]. One methodology used to solve this complicated protection design problem is efficient MILP/ILP formulation, and alternative approach is designing algorithms. However, the optimal solution is not always guaranteed as the classical p-cycle generation, RWA and RSA problems are N P -hard [12, 21, 51]. Heuristic algorithms have much lower computation complexity but it can not guarantee the optimal solution. Another alternative method for achieving the overall optimal design is the decompose technique, such as CG approach, which permits to get the optimal solution by generating promising columns iteratively [113]. 1.4 Literature review Survivability is always a key concern for optical network design to maintain the availability against network failures. A lot of protection schemes have been studied for MLR WDM optical networks and EONs due to the more resource allocation flexibility. Considering the advanced equipment requirements on the optical layer in MLR optical networks and EONs, most of these protection schemes shift the focus to the cost-effective and energy-efficient network protection rather than only the conventional wavelength/spectrum-efficient network protection [7, 13, 18, 32, 75, 81, 82, 84, 99, 123, 124, 128, 129]. Recently, disaster-survivable cloud service provisioning has been regarded as a crucial issue as more and more cloud traffic is delivered by DCNs. Some protection schemes have already been proposed to provide survivability against disaster failures [39, 45, 55, 109, 110, 142]. The approaches to solve these protection design problems were conducted by either ILP formulation or heuristic algorithms. Below, we summarize different protection schemes for MLR WDM optical networks, EONs and optical DCNs with respect to different protection issues. 26 1.4. Literature review 1.4.1 Cost-effective protection and power-efficient schemes for MLR WDM networks In [81], cost-effective protection for transparent MLR WDM optical networks was studied with three dedicated-path protection mechanisms: MLR-at-p-lightpath protection (MLR-p), MLR-at-lightpath protection (MLR-l), and MLR-with-backup-flow-grooming protection (MLR-g). The goal is to minimize the network cost in terms of transponders at various bitrates. They first proposed an ILP-based two-step approach by relaxing the wavelength-clash constraint and solving the routing/rate assignment and first-fit wavelength assignment. It has been observed that MLR-l addressed a good trade-off between performance and complexity, achieving a significant cost reduction and being solved in a reasonable time. Thereafter, they proposed a heuristic approach for MLR-l and the simulation results showed that cost-effective MLR survivable networks can be designed by intelligent assignment of bitrates to the lightpaths while satisfying all the traffic demands. The authors in [81] further proposed a Shared Subconnection Protection (SSP) scheme for MLR optical networks [82]. The SSP scheme addressed the cost-versus-capacity trade-off in providing shared protection for a transparent MLR network. They stated that SSP was an excellent candidate for protection in MLR networks for the following reasons: (i) Both working lightpaths and backup subconnections can take advantage of rate heterogeneity in MLR networks; (ii) SSP enabled low restoration time, which was crucial when transporting very high bitrates; (iii) SSP can avoid power transients that arose when the power level on a link was suddenly changed. A two-step approach was developed to formulate part of the problem as an ILP. The simulation results showed that SSP enabled higher sharing of backup capacity in an MLR network, in which the design cost was up to 37% less than an SLR network with SSP and around 40% less than MLR with dedicated protection. In [124], a computation-efficient multipath routing scheme was proposed for survivable provisioning in MLR networks. They studied the degraded service in which certain services can accept a fraction of the requested bandwidth in the event of a failure in exchange of paying a lower cost. They concerned minimum-cost MLR network design by choosing which transponder rates to use at each node while considering the opportunity to exploit multipath routes to support degraded services. Both MILP solution and a heuristic were proposed for the partial-protection. The MILP formulation was proposed to minimize the total transponder cost while exploring various rateassignment choices with respect to all possible grooming options. The proposed heuristic algorithm comprised of two major steps, i.e., route assignment and rate assignment in computing a multipath routing solution. The results have shown that significant cost savings can be achieved with the help of partial protection versus full protection, which was highly beneficial for network operators. They also noted that multipath routing in MLR networks exploited volume discount of higher-line-rate transponders by cost-effectively grooming requests over appropriate line rates versus SLR. In [32], a new solution for p-cycle design in MLR optical networks was developed and evaluated, which was the first p-cycle protection scheme for MLR networks to the 27 Chapter 1. Background and Technological Context best of our knowledge. Considering the impact of multiple heterogeneous rates in MLR networks, a p-cycle protection scheme was proposed to exploit the under-utilization of p-cycles and protect additional demands. Both exact optimization formulation and a heuristic solution for this critical problem were proposed. Simulation results showed that p-cycle for MLR had increased protection efficiency over SLR networks. [18], the authors first formulated mathematical models for designing energy- and cost-efficient MLR optical networks in transparent, translucent, and opaque IPoWDM networks. To evaluate these models, they further determined the maximum transmission reach of different line rates when they are mixed with other line-rate channels in the fiber transmission. They conducted several numerical simulations to study the energy consumption of MLR compared with the conventional SLR network, and investigated the relationship between energy-minimized and cost-minimized MLR network design. They found that energy-minimized design may not be the CapEx-minimized design depending on the relative values of transponders and amplifiers. 1.4.2 Cost-effective and power-efficient protection schemes for EONs In [128, 129], the authors evaluated the energy- and cost-efficiency of different protection schemes in EONs and compared them with the protection schemes for conventional WDM networks. The energy efficiency and cost efficiency evaluation were conducted with three common path protection schemes: 1+1 Dedicated Protection (1+1 DP), 1:1 DP, and Shared Protection (SP). Transponders, OXC and OAs were considered as the dominant optical equipments of energy and cost issues. In order to address the spectral efficiency in addition to energy efficiency, the Energy efficiency per GHz (bits/Joule/GHz) was adopted from wireless networks to evaluate the protection performance. BandwidthCBand is the available ITU-T C-band spectrum, i.e. around 4 THz. EnergyE f f iciency(bits/Joule) AvgSpectrumOccupancy ∗ BandwidthCBand( GHz) (1.1) Considering the DP and SP protection schemes, they stated the differences in the constraints between the routing and resource allocation in SLR WDM networks, MLR WDM networks and EON, and provided a broad vision of the situations where a particular protection scheme or transmission technology was more beneficial in terms of energy and cost-efficiency. The results showed that the flexible resource allocation of the EONs can be beneficial in energy efficiency for a realistic survivable network, and the SP protection scheme offered the best energy efficiency at any traffic load value in their simulations. In [99], the power consumption wastage for survivability in IP/Multi-Protocol Label Switching (MPLS) over DWDM multi-layer optical networks was studied. The authors focused on the design of survivable multi-layer optical networks over an SLR, MLR or an Elastic DWDM optical layer minimizing the total network CAPEX. Comparing with the existing works on optical layer energy-efficient design, multi-layer IP/MPLS over elastic DWDM optical networks was concerned with CAPEX and energy issues. 28 1.4. Literature review A two-step network design approach was proposed based on ILP. The first step was to determine the unprotected capacity with minimum total network CAPEX, and the second step conducted a joint optimization of the extra capacity to make the network survivable to all link failure scenarios with minimum CAPEX. From their results, EONs can yield up to 36% optical layer power consumption reduction when compared to SLR while this remarkable power consumption reduction was also translated into a significant 9.3% overall network power consumption reduction when considering IP and optical layers together. In [84], a Differentiated Quality of Protection (Diff QoP) scheme was proposed to maintain high service availability with improved energy- and spectral-efficiency. The proposed Diff QoP schemes were able to match the actual client/service requirements for network protection in both static (offline) and dynamic (online) scenarios. A framework for implementation of Diff QoP was proposed in an optical transport network as well as a thorough explanation of the heuristic to improve both the energy- and spectral-efficiency of the networks. The performance of Diff QoP in terms of energyand spectral-efficiency were comprehensively evaluated in both WDM (SLR and MLR) and EON network architectures with both static and dynamic traffic operation. They concluded that Diff QoP can be considered as a promising protection scheme for enhancing both the energy- and spectral-efficiency of optical transport networks while maintaining the heterogeneous reliability requirements of different services/users. In [13], the authors addressed the minimum network cost problem for survivable virtual optical network mapping in flexible bandwidth optical networks. Dedicatedpath protection was explored with an ILP model, the LBSD (the largest bandwidth requirement (LB) of virtual links versus the shortest distance (SD)) mapping approach and the LCSD (the largest computing (LC) resources requirement versus the shortest distance) mapping approach. The simulation results showed that the proposed approaches not only achieved the minimum total network cost but also minimum spectrum usage and minimum number of regenerators. In [123], an optimal cost-effective network dimensioning was studied for different configurations of optical slot switching metropolitan rings with elastic-rate transponders. MILP-based model was formulated to study the network cost depending on the protection type and the elasticity. In [75], a real network with 1113 physical nodes and 1+1 protection was evaluated by varying the ratio of core/metro nodes to find the optimum network performance regarding cost and power efficiency of EONs. The protection scheme was designed to simultaneously minimize CAPEX and power consumption allowing for a mostly transparent (translucent) network. Their results confirmed that the use of the flex grid is beneficial for the EON scenario. In [7], a hybrid protection approach based adaptive routing introducing the regenerator activation was proposed in the consideration of energy consumption. Both DP and SP protection schemes were designed by ILP formulation and greedy or heuristic algorithms. In their study, the first algorithm identified the primary path of each connection request and the second algorithm selected the path with minimal power consumption with their appropriate modulation formats. When a connection request 29