Virtualisation and resource allocation in MECEnabled metro optical networks

PROGRAMA DE DOCTORADO EN Tecnologías de la Información y las Telecomunicaciones TESIS DOCTORAL: Virtualisation and Resource Allocation in MEC- Enabled Metro Optical Networks Presentada por Lidia Ruiz Pérez para optar al grado de Doctor/a por la Universidad de Valladolid Dirigida por: Dr. Ramón J. Durán Barroso Universidad de Valladolid Dpto.de Teor´ ia de la Se˜ nal y Comunicaciones eIngenier´ ia Telem ´ atica Ph.D. Thesis Virtualisation and Resource Allocation in MEC-Enabled Metro Optical Networks Lidia Ruiz Pérez February 2020 Director: Dr. Ramón J. Durán Barroso ii A mi familia iii iv Abstract The appearance of new network services and the ever-increasing network traffic and number of connected devices will push the evolution of current communication networks towards the Future Internet. In the area of optical networks, wavelength routed optical networks (WRONs) are evolving to elastic optical networks (EONs) in which, thanks to the use of OFDM or Nyquist WDM, it is possible to create super-channels with custom-size bandwidth. The basic element in these networks is the lightpath, i.e., all-optical circuits between two network nodes. The establishment of lightpaths requires the selection of the route that they will follow and the portion of the spectrum to be used in order to carry the requested traffic from the source to the destination node. That problem is known as the routing and spectrum assignment (RSA) problem, and new algorithms must be proposed to address this design problem. Some early studies on elastic optical networks studied gridless scenarios, in which a slice of spectrum of variable size is assigned to a request. However, the most common approach to the spectrum allocation is to divide the spectrum into slots of fixed width and allocate multiple, consecutive spectrum slots to each lightpath, depending on the requested bandwidth. Moreover, EONs also allow the proposal of more flexible routing and spectrum assignment techniques, like the split-spectrum approach in which the request is divided into multiple "sub-lightpaths". In this thesis, four RSA algorithms are proposed combining two different levels of flexibility with the well-known k−shortest paths and first fit heuristics. After comparing the performance of those methods, a novel spectrum assignment technique, Best Gap, is proposed to overcome the inefficiencies emerged when combining the first fit heuristic with highly flexible networks. A simulation study is presented to demonstrate that, thanks to the use of Best Gap, EONs can exploit the network flexibility and reduce the blocking ratio. On the other hand, operators must face profound architectural changes to increase the adaptability and flexibility of networks and ease their management. Thanks to the use of network function virtualisation (NFV), the necessary network functions that must be applied to offer a service can be deployed as virtual appliances hosted by commodity servers, which can be located in data centres, network nodes or even end-user premises. The appearance of new computation and networking paradigms, like multi-access edge computing (MEC), may facilitate the adaptation of communication networks to the new demands. Furthermore, the use of MEC technology will enable the possibility of installing those virtual network functions (VNFs) not only at data centres (DCs) and central offices (COs), traditional hosts of VFNs, but also at the edge nodes of the network. Since data processing is performed closer to the enduser, the latency associated to each service connection request can be reduced. MEC nodes will be usually connected between them and with the DCs and COs by optical networks. In such a scenario, deploying a network service requires completing two phases: the v vi VNF-placement, i.e., deciding the number and location of VNFs, and the VNF-chaining, i.e., connecting the VNFs that the traffic associated to a service must transverse in order to establish the connection. In the chaining process, not only the existence of VNFs with available processing capacity, but the availability of network resources must be taken into account to avoid the rejection of the connection request. Taking into consideration that the backhaul of this scenario will be usually based on WRONs or EONs, it is necessary to design the virtual topology (i.e., the set of lightpaths established in the networks) in order to transport the traffic from one node to another. The process of designing the virtual topology includes deciding the number of connections or lightpaths, allocating them a route and spectral resources, and finally grooming the traffic into the created lightpaths. Lastly, a failure in the equipment of a node in an NFV environment can cause the disruption of the SCs traversing the node. This can cause the loss of huge amounts of data and affect thousands of end-users. In consequence, it is key to provide the network with faultmanagement techniques able to guarantee the resilience of the established connections when a node fails. For the mentioned reasons, it is necessary to design orchestration algorithms which solve the VNF-placement, chaining and network resource allocation problems in 5G networks with optical backhaul. Moreover, some versions of those algorithms must also implements protection techniques to guarantee the resilience system in case of failure. This thesis makes contribution in that line. Firstly, a genetic algorithm is proposed to solve the VNF-placement and VNF-chaining problems in a 5G network with optical backhaul based on star topology: GASM (genetic algorithm for effective service mapping). Then, we propose a modification of that algorithm in order to be applied to dynamic scenarios in which the reconfiguration of the planning is allowed. Furthermore, we enhanced the modified algorithm to include a learning step, with the objective of improving the performance of the algorithm. In this thesis, we also propose an algorithm to solve not only the VNF-placement and VNF-chaining problems but also the design of the virtual topology, considering that a WRON is deployed as the backhaul network connecting MEC nodes and CO. Moreover, a version including individual VNF protection against node failure has been also proposed and the effect of using shared/dedicated and end-to-end SC/individual VNF protection schemes are also analysed. Finally, a new algorithm that solves the VNF-placement and chaining problems and the virtual topology design implementing a new chaining technique is also proposed. Its corresponding versions implementing individual VNF protection are also presented. Furthermore, since the method works with any type of WDM mesh topologies, a technoeconomic study is presented to compare the effect of using different network topologies in both the network performance and cost. Resumen La aparición de nuevos servicios de red, así como el creciente tráfico y número de dispositivos conectados a las redes de comunicación, impulsarán la evolución de dichas redes hacia la Internet del Futuro. En el área de las comunicaciones ópticas, las redes ópticas con encaminamiento por longitud de onda (wavelength routed optical networks, WRONs) están evolucionando hacia las redes ópticas elásticas (elastic optical networks, EONs) en las que, gracias al uso de técnicas como OFDM o Nyquist WDM, es posible crear super canales con ancho de banda adaptable. El elemento básico en ambos tipos de redes es el camino de luz o lightpath, que es un circuito totalmente óptico que se establece entre dos nodos de la red. El establecimiento de los caminos de luz requiere la selección de la ruta que seguirá dicho camino, así como de la porción de espectro que usará para transportar el tráfico solicitado desde el origen hasta el destino. Ese problema, en EONs, se conoce como el problema de asignación de ruta y espectro (routing and spectrum assignment problem, RSA), y será necesario proponer nuevos algoritmos de asignación de recursos que solucionen este problema de diseño. Los primeros estudios sobre redes ópticas elásticas consideraron escenarios en los que se asignaba una porción variable del espectro a una solicitud de transmisión de tráfico. Sin embargo, la tendencia más estudiada es considerar al espectro dividido en tramos de un ancho fijo y asignar, a cada solicitud, un número determinado de tramos consecutivos, que dependerá del ancho de banda requerido. Además, las redes ópticas elásticas permiten utilizar técnicas más flexibles de asignación de ruta o espectro, como el espectro dividido (split-spectrum), que permite repartir el tráfico solicitado entre múltiples caminos de luz. En esta tesis se proponen cuatro algoritmos RSA combinando dos niveles distintos de flexibilidad con las técnicas de asignación de ruta y espectro k−shortest paths y first fit. Tras comparar el comportamiento de dichos métodos, se propone unan novedosa técnica de asignación de espectro llamada Best Gap, con el objetivo de solventar las ineficiencias que aparecen cuando se aplica la técnica first fit a redes con gran flexibilidad en la asignación de espectro. Por último, se realiza una simulación mediante el desarrollo de un simulador de redes elásticas en C++, utilizando el simulador de eventos discretos OMNeT++, para demostrar que las redes ópticas elásticas son capaces de explotar mejor la propia elasticidad, mejorando la tasa de bloqueo, gracias al uso de la técnica Best Gap. Por otra parte, las operadoras deben realizar cambios profundos en la arquitectura de las redes de comunicación para aumentar su adaptabilidad y flexibilidad, así como para facilitar su gestión. Gracias al uso de tecnologías como la virtualización de funciones de red (network function virtualisation, NFV), las funciones de red, necesarias para poder ofrecer cualquier servicio, podrán desplegarse como aplicaciones software instaladas en servidores que podrán estar localicados en centros de datos, en los nodos de la red o incluso en los equipos del vii xiv CONTENTS 4.3 Conclusions.................................... 88 5 Genetic Algorithm for Effective Service Mapping 91 5.1 ProblemStatement ................................ 93 5.2 A Genetic Algorithm to Solve the Service Mapping Problem . . . . . . . . . . 94 5.2.1 AlgorithmOverview ........................... 94 5.2.2 Simulation Study and Results . . . . . . . . . . . . . . . . . . . . . . 97 5.3 GASM in Reconfiguration Scenarios . . . . . . . . . . . . . . . . . . . . . . . 103 5.3.1 Static planning for peak loads with GASM . . . . . . . . . . . . . . . 103 5.3.2 Service Mapping Reconfiguration with GASM . . . . . . . . . . . . . 105 5.3.3 Simulation Scenario and Results . . . . . . . . . . . . . . . . . . . . . 107 5.4 Conclusions....................................118 6 Joint Solution of VNF Mapping and Virtual Topology Design 121 6.1 Genetic Algorithm for Service Mapping with Virtual Topology Design . . . . . 122 6.1.1 Algorithm Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 6.1.2 Simulation Scenario and Settings . . . . . . . . . . . . . . . . . . . . 124 6.1.3 Performance of GASM-VTD . . . . . . . . . . . . . . . . . . . . . . . 127 6.2 Fault-management techniques to guarantee survivability in NFV environments . 128 6.2.1 Individual VNF protection schemes . . . . . . . . . . . . . . . . . . . 129 6.2.2 Integrating VNF protection into GASM-VTD . . . . . . . . . . . . . . 130 6.2.3 Simulation scenario and results . . . . . . . . . . . . . . . . . . . . . 131 6.2.4 Comparison between individual VNF protection and end-to-end SC protectionschemes............................137 6.3 Efficiently solving the VNF-placement, chaining, virtual topology design and survivability problems on any kind of WDM-mesh network . . . . . . . . . . . 141 6.3.1 GASVIT .................................141 6.3.2 Providing individual VNF protection with GASVIT . . . . . . . . . . . 143 6.3.3 Simulation scenario and results . . . . . . . . . . . . . . . . . . . . . 144 6.4 Conclusions....................................154 7 Conclusions and Future Work 157 7.1 Conclusions....................................157 7.2 Futurework....................................160 7.3 Publications....................................160 8 Conclusiones y Futuras Líneas de Investigación 163 8.1 Conclusiones ...................................163 8.2 Futuras líneas de investiación . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 8.3 Publicaciones...................................167 A Developed Simulators using OMNeT++ 169 A.1 Introduction....................................169 A.2 EONSimulator ..................................170 A.3 NFVSimulator ..................................171 Bibliography 174 List of Figures 2.1 ITU-T Grid for (1) 100 GHz, (2) 50 Ghz, (3) 25 GHz and (4) 12.5 GHz channel spacing....................................... 7 2.2 Channel comparison between Fixed DWDM Grid with 50 GHz channel spacing (1) and Flexgrid with 6.25 GHz spacing between Central Frequencies (2).......................................... 26 2.3 Summaryofthechapter. ............................. 35 3.1 Example of Flexgrid and Gridless spectrum. . . . . . . . . . . . . . . . . . . . 39 3.2 Blocking ratio for the JSF algorithm when k=1, for different slot granularities. 46 3.3 Blocking ratio for the JSF algorithm when k=3, for different slot granularities. 47 3.4 Blocking ratio for the JSF algorithm when k=5, for different slot granularities. 47 3.5 Blocking ratio for the JSF algorithm when k=1,3,5 and T=12.5 GHz. . . . . 48 3.6 Blocking ratio for the DSF algorithm when k=1, for different slot granularities. 49 3.7 Blocking ratio for the DSF algorithm when k=3, for different slot granularities. 50 3.8 Blocking ratio for the DSF algorithm when k=5, for different slot granularities. 50 3.9 Blocking ratio for the DSF algorithm when k=1,3,5 and T=50 GHz. . . . . 51 3.10 Blocking ratio for the JSG algorithm when k=1,3,5............... 51 3.11 Blocking ratio for the DSG algorithm when k=1,3,5. ............. 52 3.12 Blocking ratio obtained by the schemes in their best performing configurations. 52 3.13 Computational times obtained by the schemes in their best performing configurations. .................................. 53 3.14 Example of resource allocation using Joint Flexgrid-First Fit and Joint Flexgrid-Best Gap. For simplicity, guard-bands are not considered in this example....................................... 54 3.15 Example of resource allocation using Disjoint Flexgrid-First Fit and Disjoint Flexgrid-Best Gap. For simplicity, guard-bands are not considered in this example....................................... 55 3.16 Blocking ratio achieved by JSF-BG when k=1,3 and 5 respectively. . . . . . . 58 3.17 Blocking ratio achieved by DSF-BG when k=1,3 and 5 respectively. . . . . . 59 3.18 Blocking ratio achieved by JSG and DSG when k=1,3 and 5. . . . . . . . . . 60 3.19 Blocking ratio for the best performing configuration of the proposed RSA algorithms. .................................... 61 3.20 Computational time for the best performing configuration of the proposed RSA algorithms. .................................... 62 xv xvi LIST OF FIGURES 4.1 ETSI NFV Reference Architecture [1],[2]. . . . . . . . . . . . . . . . . . . . . 65 4.2 End-to-end SC protection scheme for a SC with four primary VNFs. . . . . . . 81 4.3 Individual VNF protection scheme for a SC with four primary VNFs. . . . . . 82 4.4 SDN Reference Architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 4.5 OpenFlowArchitecture............................... 86 4.6 MECFramework.................................. 87 4.7 Summaryofthechapter. ............................. 90 5.1 5G access optical network scenario where 5G-nodes are connected to a CO using point-to-point optical links. . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.2 Representation of a chromosome. . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.3 Service blocking ratio for MEC-First, CO-First and GASM [3]. . . . . . . . . . 101 5.4 Percentage of active CPU cores for MEC-First, CO-First, and GASM [3]. . . . 101 5.5 RAM consumption for MEC-First, CO-First and GASM . . . . . . . . . . . . 102 5.6 HDD consumption for MEC-First, CO-First and GASM . . . . . . . . . . . . 102 5.7 Service blocking ratio achieved for peak load plannification with GASM for different values of kand φ=0.5 .........................108 5.8 Active CPU Cores (%) achieved for peak load plannification with GASM for different values of kand φ=0.5 .........................109 5.9 RAM and HDD consumption (in (%)) for a peak-load planning with k=1,1.5 or 2 and φ=0.5. .................................110 5.10 Service blocking ratio achieved when statically planning for peak loads using GASM with k=1,1.5 and 2 and φ=0.25.....................111 5.11 Service blocking ratio achieved for peak load plannification with GASM for different values of kand φ=0.75.........................111 5.12 Service blocking ratio for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.5.........112 5.13 Active CPU cores (%) for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.5.........113 5.14 RAM and HDD consumption (in (%)) for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.5. 114 5.15 Service blocking ratio for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.25 ........115 5.16ActiveCPUCores(%) ..............................115 5.17 Service blocking ratio and CPU core consumption in (%) for the reconfiguration algorithms, the static algorithms and the online methods MEC- First and CO-First when φ=0.25. ........................115 5.18 Service blocking ratio for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.75. . . . . . . . . 116 5.19 Active CPU cores (%) for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.75. . . . . . . . . 117 5.20 Service blocking ratio and Active CPU cores (in (%)) for for the reconfiguration algorithms, the static algorithms and the online methods MEC- First and CO-First when φ=0.75. ........................117 5.21 Execution times of the compared algorithms when φ=0.5 [4]. . . . . . . . . . 117 LIST OF FIGURES xvii 6.1 WDM-ring topology scenario [5]. . . . . . . . . . . . . . . . . . . . . . . . . 125 6.2 Service blocking ratio of GASM-VTD-Collaborative, GASM-VTD-No- Collaborative, MEC First, and CO-First in a WDM-ring 5G network [5]. . . . . 127 6.3 Percentage of CPU core consumption of GASM-VTD-Collaborative, GASMVTD-No-Collaborative, MEC First and, CO-First in a WDM-ring 5G network [5]..........................................128 6.4 Service blocking ratio of GASM-VTD with the different protection techniques when the WDM network can use 10 wavelengths [6]. . . . . . . . . . . . . . . 132 6.5 Percentage of CPU core consumption of GASM-VTD with the different protection techniques when the WDM network can use 10 wavelengths [6]. . . 133 6.6 Comparison of the percentage of allocated CPU cores to the primary and backup VNFs, for the different protection schemes when the WDM network can use 10 wavelengths, for ¯u=500,¯u=2,500 and ¯u=4,500 [6]. . . . . . . . 134 6.7 Service blocking ratio of GASM-VTD with the different protection techniques when the WDM network can use 20 wavelengths [6]. . . . . . . . . . . . . . . 135 6.8 Percentage of CPU core consumption of GASM-VTD with the different protection techniques when the WDM network can use 20 wavelengths [6]. . . 136 6.9 Comparison of the percentage of allocated CPU cores to the primary and backup VNFs, for the proposed protection schemes when the WDM network can use 20 wavelengths, for ¯u=500,¯u=2,500 and ¯u=4,500 [6]. . . . . . . . 136 6.10 Service blocking ratio of GASM-VTD with end-to-end SC protection schemes when the WDM network can use 10 wavelengths. . . . . . . . . . . . . . . . . 139 6.11 Service blocking ratio of the end-to-end SC protection schemes when the WDM network can use 20 wavelengths. . . . . . . . . . . . . . . . . . . . . . 140 6.12 Service blocking ratio of the best performing configurations of end-to-end SC and individual VNF protection schemes when the WDM network can use 10 and20wavelengths.................................140 6.13 Service blocking ratio of GASVIT, GASM-VTD, MEC First, and CO-First when the WDM-ring 5G network can use 10 wavelengths. . . . . . . . . . . . 145 6.14 Percentage of CPU core consumption of GASVIT, GASM-VTD, MEC First, and CO-First when the WDM-ring 5G network can use 10 wavelengths. . . . . 146 6.15 Average hops of the SCs established with GASVIT, GASM-VTD, MEC First, and CO-First when the WDM-ring 5G network can use 10 wavelengths. . . . . 147 6.16 Service blocking ratio of GASVIT with protection when the network uses up to10wavelengths. ................................148 6.17 Service blocking ratio obtained by GASVIT with protection when the network usesupto20wavelengths. ............................148 6.18 Percentage of the CPU cores employed by GASVIT with protection when the network uses up to 10 wavelengths. . . . . . . . . . . . . . . . . . . . . . . . 149 6.19 Percentage of the CPU cores employed by GASVIT with protection when the network uses up to 20 wavelengths. . . . . . . . . . . . . . . . . . . . . . . . 150 6.20 Percentage of CPU cores allocated to primary and backup VNFs for GASVIT with protection when the network uses up to 10 wavelengths. . . . . . . . . . . 151 xviii LIST OF FIGURES 6.21 Reduction in terms of service blocking ratio and CPU core consumption obtained by GASVIT (SV, SN) compared to GASM-VTD, S-VNF & S-Net, when the network uses up to 10 wavelengths. . . . . . . . . . . . . . . . . . . 151 6.22 Topologies compared in the techno-economic study. . . . . . . . . . . . . . . . 152 6.23 Reduction of the service blocking ratio obtained by the different network topologies......................................154 A.1 NFSNet implemented in the EON simulator . . . . . . . . . . . . . . . . . . . 170 A.2 Control node structure of the EON Simulator . . . . . . . . . . . . . . . . . . 171 A.3 Network topologies implemented in the GASM simulator. . . . . . . . . . . . 172 A.4 Structure of the Controller module of GASM simulator. . . . . . . . . . . . . . 172 List of Tables 2.1 Topology design proposals based on NLP, ILP and MILP formulations. . . . . 10 2.2 Summary of heuristics and meta-heuristics that solve the topology design subproblem..................................... 11 2.3 Virtual topology reconfiguration proposals. . . . . . . . . . . . . . . . . . . . 13 2.4 Summary of proposals to solve the RWA problem. . . . . . . . . . . . . . . . . 18 2.5 Summary of protection proposals in survivable WRONs. . . . . . . . . . . . . 22 2.6 Summary of static RSA techniques that propose a linear programming formulation..................................... 29 2.7 Heuristics to solve the RSA problem. . . . . . . . . . . . . . . . . . . . . . . . 30 4.1 Mathematical formulations for solving the VNF-placement and chaining problems in a static scenario. . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.2 Heuristics for solving the VNF-placement and chaining problems in static scenarios. ..................................... 74 4.3 Mathematical formulations for solving the dynamic VNF-placement and chaining problems in dynamic scenarios. . . . . . . . . . . . . . . . . . . . . . 75 4.4 Heuristics and meta-heuristics for solving the VNF-placement and chaining problems in dynamic scenarios. . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.5 Summary of protection proposals to address the NFV survivability problem. . . 84 5.1 Hardware capabilities of the different 5G-nodes . . . . . . . . . . . . . . . . . 97 5.2 Requirements of the deployed service chains. NAT: Network Address Translator, FW: Firewall, TM: Traffic Monitor, WOC: WAN Optimization Controller, VOC: Video Optimization Controller and IDPS: Intrusion Detection Prevention System [3], [4], [7], [8], [9], [10]. . . . . . . . . . . . . . 99 5.3 Hardware requirements associated with the VNFs [7], [8], [9], [10], [3], [4] . . 100 6.1 Hardware capabilities of the different 5G-nodes. . . . . . . . . . . . . . . . . . 125 6.2 Requirements of the deployed service chains. NAT: Network Address Translator, FW: Firewall, TM: Traffic Monitor, WOC: WAN Optimization Controller, VOC: Video Optimization Controller and IDPS: Intrusion Detection Prevention System [7], [8], [9], [10], [3], [4]. . . . . . . . . . . . . . 126 6.3 Hardware requirements associated with the VNFs [5]. *We assume that FW also includes NAT function, therefore the HW requirements are the same. Requirements for VOC are derived from the requirements of the other VNFs. . 126 6.4 Number of WSS required to build each type of OXC. . . . . . . . . . . . . . . 153 xix xx LIST OF TABLES 6.5 Topology cost in terms of number of WSS. . . . . . . . . . . . . . . . . . . . . 153 Chapter 1 Introduction Future Internet must overcome the challenges that will emerge with the appearance of new network services and the ever-increasing number of connected devices. The appearance of new applications as Cloud Computing or the Internet of Things (IoT), and the deployment of 5G, which promises to reduce the latency to figures never seen before (less than 1 ms) require flexible, adaptable and easily manageable networks. Traditional network deployments, which rely on proprietary hardware from different vendors, are not able to offer these capabilities since adapting the networks to offer new applications requires high capital and operational expenditures (CAPEX and OPEX) and time. In consequence, network operators must face a profound architectural change in order to adapt their networks and IT resources to the new services and requirements. The access segment will evolve to 5G, a broadband access technology that promises to shake up the communications panorama by bringing new network capabilities like high bandwidth, low latency, high scalability, heterogeneous technologies convergence, coordinated automation, or on-demand and service-oriented resource allocation, among other features. Furthermore, 5G will have to cope with the increasing number of connected devices, up to 100-fold, while reducing the CAPEX and OPEX [11]. The backhaul of these networks is expected to be built upon optical technologies, given their high capacity and flexibility [12]. Optical networks, particularly in the core/metro segments, will also experiment a profound change in order to better exploit the capacity of optical fibres and cope with the future increase of traffic and connected devices. In particular, Wavelength Routed Optical Networks (WRON) are evolving to Flexible or Elastic Optical Networks (EON), which make better use of spectrum by adjusting the allocated bandwidth to a connection to the actual demanded capacity, instead of allocating fixed bandwidth to each connection, like WRONs do. Moreover, future networks will change their control plane in order to increase the flexibility and adaptability of networks and ease their management. Thanks to that increment in flexibility, future networks will allow faster deployment of new services. Software Defined Networking (SDN) is considered as the technology that will allow that evolution and it is based on the separation of the Control Plane and the Data Plane in networks. In this manner, the Data Plane will be composed by simple packet forwarding devices, while the Control Plane, responsible for orchestrating the networks, can be deployed using software appliances. Finally, two technologies will be also responsible of the “softwarisation” of networks: Multi-access Edge Computing (MEC) and Network Function Virtualisation (NFV). MEC 1 2 Chapter 1. Introduction provides cloud computing capabilities to the edge nodes of networks, pushing the data processing closer to the end-user [13]. NFV proposes the deployment of common network functions like packet inspectors or firewalls in the form of software appliances, instead of using the traditional, vendor-based hardware devices. In this manner, the adaptability and the flexibility of the network increases, since deploying new network services only requires the creation of software instances instead of the purchase and installation of new network equipment. This thesis has been developed in the context of two national research projects ONOFRE (TEC2014-53071-C3-2-P) and ONOFRE-2 (TEC2017-84423-C3-1-P), the fellowship program of the Spanish Ministry of Economy, Industry and Competitiveness (BES 2015-074514), the research network Go2Edge (RED2018-102585-T), and the European Regional Development Fund (ERDF) through the proyect DISRUPTIVE of the cooperation programme Interreg V-A Spain-Portugal (POCTEP) 2014-2020, and makes contributions in two research fields: control algorithms for EONs and methods for the orchestration of 5G network with optical backhaul. All the contributions of this Thesis were evaluated by means of simulations and compared with techniques with similar objectives from the literature. 1.1 Thesis objectives This thesis makes contributions in the development of the orchestration of 5G optical access and metro networks, and in the evolution from WRONs to EONs, by proposing a set of algorithms to solve the RSA problem. The objectives of this thesis can be divided as follows: 1. To review of the state-of-art of circuit-based optical networks (from WRONs to EONs), and NFV, MEC, and SDN paradigms. 2. Proposals on Elastic Optical Networks: 2.1 To analyse of the integration of four levels of flexibility (regarding to two different spectrum division techniques and the allowance of split-spectrum) in two wellknown RSA heuristics as k−shortest paths and first fit. 2.2 To propose of a new spectrum allocation technique to exploit the flexibility of EONs and improve the network performance in terms of blocking ratio. 3. VNF-placement and VNF-chaining problems: 3.1. To propose of an algorithm to solve the VNF-placement and chaining problems in a static 5G network: GASM. 3.2. To extend the algorithm to solve the VNF-placement and chaining problems in a dynamic 5G network by performing a periodical reconfiguration of the network. 4. VNF-placement, chaining and virtual topology design problems in 5G networks with optical backhaul: 4.1. To propose an algorithm to solve the VNF-placement, chaining and virtual topology design problems in 5G networks with WDM-ring backhaul: GASM-VTD. 1.2. Thesis structure 3 4.2. To extend the algorithm including individual VNF protection against node failure. 4.3. To conduct a performance comparison of individual VNF protection and end-to- end SC protection schemes. 4.4. To conduct a techno-economic study to compare the effect on the network cost and performance in terms of service blocking ratio of deploying different topologies in the backhaul of 5G networks considering only the NFV design problems. 1.2 Thesis structure The thesis is structured as follows: Chapter 2, introduces the circuit-based optical technologies WRON and EON. The most important design problems, like the virtual topology design, the static and dynamic RWA problem in WRONs, the static and dynamic RSA problem in EONs and other issues as survivability are reviewed, including the methods proposed in the literature to address them. Chapter 3 presents two sets of algorithms that solve the RSA problem in Elastic Optical Networks. The first set combines two different types of flexibility with the classical RSA algorithms k−shortest path and first fit. Furthermore, a new spectrum assignment technique is proposed to more efficiently exploit the flexibility of EONs compared to other classical RSA algorithms. Moreover, a simulation study is presented to evaluate the performance of the proposals. Chapter 4 introduces the network technology NFV and briefly describes SDN and MEC, as related technologies to NFV. The Chapter reviews the most important NFV design problems, as the VNF-placement and chaining, and issues like the survivability in NFV environments. Moreover, the proposed methods in the literature to address these problems are reviewed. Chapter 5 presents an algorithm to solve the VNF-placement and chaining problems in 5G networks to minimise the service blocking ratio and resource consumption. In this Chapter, the same algorithm is adapted to be able to perform a periodical reconfiguration of the network planning, i.e., the location and number of VNF instances, in a dynamic scenario. Moreover, a learning technique is implemented to improve the performance of the algorithm when reconfiguration is allowed. Chapter 6 proposes an algorithm to solve the VNF-placement, chaining and virtual topology design in 5G networks with optical backhaul built using WDM-mesh topologies. The algorithm includes techniques to solve the virtual topology design problem, and exploits the MEC capabilities of the nodes to reduce the service blocking ratio. Our proposal is compared to other proposals in the literature. Furthermore, versions of this algorithm are proposed to implement protection techniques that ensure the resilience of the established connections against single-node failure. The versions of the algorithm implementing the proposed protection techniques are also compared to other protection approaches proposed in the literature. Moreover, a new algorithm is proposed to implement a novel chaining technique whose objective is to make better use of the collaboration between the MEC-nodes of the network. Versions of the algorithm are proposed to implement individual VNF protection techniques to ensure the resilience of the established SCs in case of node failure. Finally, a techno-economic study is conducted to analyse the cost of deploying 5G networks with different WDM topologies and compare the performance of these topologies in terms of service blocking ratio. 10 Chapter 2. Evolution of Optical Networks Authors Subproblems Formulation Characteristics Mukherjee et al. [14] 1 −3 NLP Minimises either delay or congestion Chen et al. [37] 1 −2−3 ILP Reduces CAPEX minimising the number of optical transceivers Cinkler et al. [31] 1 −2−3 ILP Minimizes electric resource utilization Banerjee et al. [32] 1 −3 ILP Minimises single hop traffic Xin et al. [33] 1 −3 ILP Minimises resource usage or maximises revenue Labourdette and Acampora [34] 1−3 MILP Maximises routed traffic in a single hop Ramaswami and Siravajan. [15] 1−3 MILP Minimises congestion Durán et al. [36] 1 −2−3 MILP Minimises congestion Asghar et al. [28] 1 −3 MILP Optimises resource utilization and delay Huiban and Mateus. [35] 1−3 MILP Multiobjective optimisation: congestion and active wavelengths Table 2.1: Topology design proposals based on NLP, ILP and MILP formulations. 2.1. Wavelength-Routed Optical Networks 11 virtual topology design that minimises the number of utilised transceivers and wavelengths, considering physical layer impairments. Asghar et al. proposed in [28] a heuristic to design virtual topologies reducing the number of O/E/O conversions and the established number of lightpaths. Pavón et al. [40] proposed a heuristic for virtual topology design that minimises the network cost by reducing the necessary number of transceivers. Mukherjee et al. [14] presented heuristics based on simulated annealing and flow-deviation for topology design and routing. The objective of the simulated annealing algorithm is to minimise congestion, whereas the flow-deviation algorithm minimises the average packet delay. Saha et al. [41] took Mukherjee’s work as a starting point for solving the topology design problem, but employed genetic algorithms instead of simulated annealing, obtaining better scaleup and total delay results. In [42], Gazen and Ersoy proposed a genetic algorithm to design topologies by means of applying classical genetic operations as crossover or mutation to predefined virtual topologies, until the resulting topologies outperform the existing, predefined ones. Furthermore, Ghose et al. [43] proposed a heuristic an a genetic algorithm that solves the topology design and the RWA problem minimising the delay. Durán et al. [27], [44], [45] proposed a set of genetic algorithms to solve the topology design, RWA and routing problems, minimising the delay, the congestion or the utilized resources (number of transceivers and active wavelengths). Fernández et al. enhanced those genetic algorithms with the objective of minimising the network power consumption, proposing in [46], two multiobjective algorithms, one of them enhanced with cognition techniques. Fukushima et al. [47] proposed a heuristic for virtual topology design, lightpath provisioning and routing which aims at maximising the throughput and minimising the number of employed fibre amplifiers. Din [48] proposed a heuristic and a genetic algorithm to solve the topology design and the rate of the lightpaths in mixed-line-rate (MLR) WDM networks with the objective of minimising the cost of the transceivers. Table 2.2 summarises these techniques. Table 2.2: Summary of heuristics and meta-heuristics that solve the topology design subproblem. Authors Subproblems Technique Objective Ramaswami and Siravajan [15] 1−2 Heuristic based on placing logical links according to some design criteria Four algorithms: •Congestion minimisation •Delay minimisation •Active wavelength minimisation •Meeting degree constraints Continued on next page 12 Chapter 2. Evolution of Optical Networks Table 2.2 – Continued from previous page Authors Subproblems Technique Objective Zhang and Acampora [38] 1−2 Greedy algorithm Maximises the sum of one-optical-hop traffic to minimize congestion Banerjee et al. [32] 1 Link elimination through matching scheme Minimises maximum carried traffic by a lightpath Sengezer and Karasan [39] (1 −3) +2 Tabu and greedy search Maximises transported traffic while minimizing number of transceivers, considering physical impairments Asghar et al. [28] 1 −2−3 Multiweighted graph combined with a Pareto optimal algorithm Minimises O/E/O conversions and employed lightpahts Pavon-Marino et al. [40] 1 −3 Traffic dominance based heuristic Optimises network costs minimizing the number of required transceivers Mukherjee et al. [14] 1 −3 Simulated Annealing and fow deviation Two algorithms: •Minimise congestion •Minimise packet delay Saha et al. [41] 1 −3 Genetic Algorithm Congestion minimisation Gazen and Ersoy [42] 1 Genetic Algorithm Virtual Topology Design Ghose et al. [43] (1 −3) +2 Genetic Algorithm Delay minimisation Durán et al. [27], [44], [45] 1−2−3 Multiobjective genetic algorithm Congestion, resource utilisation and delay minimisation Continued on next page 2.1. Wavelength-Routed Optical Networks 13 Table 2.2 – Continued from previous page Authors Subproblems Technique Objective Fernández et al. [46] 1 −3 Multiobjective genetic algorithms Power minimisation, one enhanced with cognition techniques Fukushima et al. [47] 1 −2−3 Greedy algorithm Heuristic which maximises throughput and minimises fibre amplifiers Din [48] 1 Heuristic and genetic algorithm Minimise cost of transceivers Lastly, studies can be found in literature which reconfigure static logical topologies. Given the variable nature of traffic, designing a static topology may cause network inefficiencies or traffic losses. The reconfiguration is accomplished by setting up new lightpaths or changing and removing existing lightpaths [49]. The objective of reconfiguration is to achieve improvements in the efficiency and reliability of the network while optimising aspects as the resource usage. Table 2.3: Virtual topology reconfiguration proposals. Authors Reconfiguration Stage Algorithm Objective Zhang et al. [50] Offline Reconfiguration Multi-stage decision-making process and prediction-based heuristic Minimise average hop count Chen et al. [37] 1 −2−3 ILP Reduces CAPEX minimising the number of optical transceivers Baldine and Rouskas [51] Offline Reconfiguration Multi-stage decision-making process Select rewarding and cost functions to achieve the desired performance Continued on next page 14 Chapter 2. Evolution of Optical Networks Table 2.3 – Continued from previous page Authors Reconfiguration Stage Algorithm Objective Ricciato et al. [52] Offline Reconfiguration MILP Minimise cost Ohsita et al. [53] Online Reconfiguration Multi-stage reconfiguration based on traffic prediction Limit the changing lightpaths at each stage Gençata and Mukherjee [54] Online Reconfiguration Load-based lightpath addition or deletion Minimise the number of changes Melidis et al. [55] Online Reconfiguration Load-based lightpath addition or deletion Minimise the power consumption and reduce the number of required reconfigurations Durán et al. [44] Offline Redesign Genetic Algorithm Minimise number of changes Fernández et al. presented in [56] Online Redesign Cognitive and traffic prediction-based reconfiguration algorithm and transition planning Minimise instabilities Banerjee and Mukherjee [26] Single-step Migration ILP Minimise of number Wavelength- Routing Switch configurations Takagi et al. [57] Step-by-step Migration Migration heuristics in which only one ligthpath changes at each migration step Maximise network availability 2.1. Wavelength-Routed Optical Networks 15 The WDM network reconfiguration consists of three steps [49], the design of a reconfiguration policy which decides whether the reconfiguration should be performed, the selection of a new topology according to an optimisation criterion and the migration to the new topology. There are two main events that trigger the reconfiguration of a network, which are a change in the traffic pattern or a change in the network resources, for example, for the addition of new network equipment, the deletion due to network maintenance or the failure of network equipment. Reconfiguration policies can be classified as offline policies and online policies. Offline policies are designed using traffic estimation techniques before its implementations in the network. Zhang et al. [50] propose a multi-stage decision-making process formulation and a prediction-based heuristic for offline reconfiguration. Baldine and Rouskas [51] also proposed a multi-stage decision process for network reconfiguration which focuses on appropriately selecting rewarding and cost functions to achieve the desired performance. Finally, Ricciato et al. [52] proposed a MILP formulation for network reconfiguration that assumes that the operator knows the network traffic behaviour in advance. Ohsita et al. [53] proposed an online reconfiguration policy that divides the reconfiguration process in various stages and predicts the traffic using the traffic matrices of past stages. In this manner, the algorithm limits the number of lightpaths that change at each stage. Gençata and Mukherjee proposed in [54] an algorithm to reconfigure a virtual topology, adding or deleting lightpaths according to the lightpath loads at the end of an observation period, minimising the number of changes. Similarly, in [55], Melidis et al. proposed an online policy that minimises the power consumption and reduces the number of required reconfigurations. In this case, a third threshold is added: if a lightpath is overloaded but the carried traffic does not exceed the activation threshold, new traffic demands will not be routed through these lightpaths but no additional lightpath will be created. Another option to react against a traffic change or network failure is redesigning the virtual topology. However, since reconfiguring the topology may cause instabilities and, consequently, packet delay or loss, the design methods employed when reconfiguration is allowed tend to include mechanisms to minimise the number of added and/or deleted lightpaths and, consequently, instabilities. Durán et al. [44] presented a proposal in which the number of changed lightpaths and, consequently, the changes between the previous and the reconfigured network are minimised. Fernández et al. presented in [56] an algorithm that proactively reconfigures the virtual topology using cognitive techniques and traffic prediction and also plans a transition sequence that minimises the possible instabilities. Finally, once a new topology is designed, a migration between the old topology and the new topology must be perform. The objective is to reduce the instabilities and packet delay and the packet loss rate. We can find two approaches to the migration phase: the single-step migration, in which the traffic migrates from one topology to another in just one step. Banerjee and Mukherjee proposed in [26] an ILP that minimises the number Wavelength-Routing Switch configurations required to change from the existing to the new topology. On the contrary, some studies approach the migration phase using a step-by-step migration technique. In [57], Takagi et al. proposed algorithms in which the basic change unit is the lightpath, i.e., only one lightpath changes from one configuration to another, in order to maximise the network availability. A summary of the reconfiguration methods can be seen in Table 2.3. 16 Chapter 2. Evolution of Optical Networks 2.1.1.2 The Routing and Wavelength Assignment Problem After the lightpaths to be established in the virtual topology, they have to be embedded in the physical topology. This process implies allocating to each lightpath composing the designed virtual topology a route, or set of fibres to be traversed, and an available wavelength which has not been assigned to other lightpath traversing all or part of the fibres in the route. This second subproblem is known as the Routing and Wavelength Assignment (RWA) problem. Some of the methods that solved the topology subproblem also addressed the RWA problem [15], [27], [28], [31], [36], [37], [38], [39], [43], [44], [45], [47] . However, there are methods that solve the RWA subproblem independently. This subproblem can be solved using ILP formulations, as the proposed by Ramaswami and Sivarajan in [58]. However, Chlamtac et al. proved this problem to be NP-Hard [59] and, therefore, its computational complexity increases exponentially with the network size. Consequently, it is often solved using heuristics and meta-heuristics since this kind of approaches simplifies the solving process. The existence of wavelength converters in the network is an important aspect to consider when solving the RWA problem. In the absence of wavelength converters, the allocated wavelength to a lightpath must be the same throughout the route. However, if the nodes of the network can be equipped with wavelength converters, additional design decisions must be solved, such as the number and position of the converters or the range of wavelengths they can convert. Stern and Bala proposed in [60] an ILP formulation that can be applied to a wavelength-convertible network, which solves the routing problem. Chu et al. solved the converter placement problem in [61]. More information on the RWA problem-solving under wavelength conversion can be found in [62]. However, converters increment the network cost and complexity, so the common approach is to solve the RWA problem in the absence of this element. It is common to solve the RWA problem by separately finding a route and then an available wavelength to be allocated to the lightpath. In this manner, the routing subproblem can be solved utilizing a pre-computed list of paths between the source and destination nodes. On the other hand, the wavelength allocation problem can be solved attending to different design criteria, as minimising the number of active wavelengths or the energy consumption. The routing problem is frequently solved using one of these heuristics: 1. Fixed Routing (FR): This is the most straightforward method and consists in assigning always the same route to the same pair of source-destination nodes, which means that only one route for each pair is pre-calculated. The route is usually calculated as the shortest-path route in terms of hops or total delay using methods as Dijkstra’s algorithm [62]. 2. Fixed-Alternate Routing (FAR): In this technique, each node of the network maintains a routing table containing pre-calculated routes to each destination node. These routes are frequently sorted in increasing order of length, i.e., the first route is the shortest-path route, followed by the second shortest-path route, etc. Consequently, when a request arrives, the algorithm tries the routes following the order in the routing table, until finding the first available route. 3. Adaptive Routing (AR): The routes are calculated according to the network state and 2.1. Wavelength-Routed Optical Networks 17 reordered accordingly [63]. On the other hand, the wavelength assignment problem can be solved using one of the following techniques: 1. First Fit (FF): In this assignment scheme, wavelengths are numbered and checked from the lower-numbered to the highest-numbered wavelength, selecting the first available one. 2. Most Used (MU): This scheme attempts to allocate the wavelength which has been employed more times in the network. 3. Least Used (LU): Similar to the previous method, this method selects the least used wavelength in the network. 4. Random: The scheme computes the set of available wavelengths and randomly selects one from this set. Chlamtac et al. [59] proposed a heuristic in which routes are ordered from the longest to the shortest path. In that order, the algorithm assigns an available wavelength utilising the FF scheme. Banerjee and Mukherjee [64] proposed a method which also divides the RWA problem into two steps, solving the routing problem through an ILP formulation which minimises the number of lightpaths sharing a link. Authors showed that the wavelength allocation problem is equivalent to a graph colouring problem and used the solving methods for that kind of problem. Stern and Bala [60] proposed a non linear formulation for joint RWA problem-solving which minimises the number of active wavelengths and routes. In [65], Deylamsalehi et al. proposed a MILP formulation for solving the RWA problem that aims at minimising the electricity cost and the produced emissions. Since the MILP formulation will not solve the problem in polynomial time when the objective network is large, authors accompanied their proposal with a logistic regression model to solve the RWA problem minimising the electricity cost and the produced emissions. Christodoulopoulos et al. [66] proposed a RWA algorithm which minimises the maximum network resources in use. The algorithm first precomputes the possible paths in a network, solves the static RWA problem and, if the problem is infeasible, if tries iterative rounding and fixing techniques or increases the number of possible wavelengths until a result is found. This algorithm was further extended to render it impairment aware, so that it introduces the physical impairments as constraints of their formulation. Another technique for jointly solving the RWA problems is using a wavelength graph as in [31], [67], [68]. This technique consists in creating copies of the physical topology for each available wavelength. In order to enable wavelength conversion, a link can be added between layers through the nodes with this capacity. This links can be assigned a larger weight in order to avoid wavelength conversion. Initially, any wavelength can be utilised when establishing a lightpath between nodes. Therefore, a shortest path algorithm can be applied, resulting in the route and wavelength to use at each fibre. This route is removed from the wavelength graphs so that they can be reused in following searches. The different proposals to solve the RWA problem are summarised in Table 2.4. 18 Chapter 2. Evolution of Optical Networks Authors RWA solving strategy Technique Objective Ramaswami and Siravajan [58] Joint RWA ILP Maximise routed connections Chlamtac et al. [59] R +W Routes ordered in decreasing length order +FF Maximise unused wavelengths Banerjee and Mukherjee [64] R+WA ILP +graph coloring algorithms Minimises required wavelengths Stern and Bala [60] Joint RWA NLP Minimises active wavelengths and routes Deylamsalehi et al. [65] Joint RWA MILP and logistic regression model Minimises electricity costs and produced emissions Christodoulopoulos et al. [66] Joint RWA Heuristic +LP for RWA Minimises network resources in use Cinkler et al. [31] Joint RWA Wavelength graph Minimise number of hops Chatterjee et al. [67] Joint RWA Wavelength graph Minimise blocking rate Zhou et al. [68] Joint RWA Wavelength graph Minimise blocking rate Table 2.4: Summary of proposals to solve the RWA problem. 2.1. Wavelength-Routed Optical Networks 19 2.1.1.3 The Routing Subproblem The final step is routing the traffic over the lightpaths which were designed solving the first subproblem and embedded in the physical topology solving the second subproblem. Some proposals that addressed the topology subproblem also solved the routing subproblem [14], [15], [27], [28], [31], [32], [33], [34], [35], [36], [37], [39], [40], [41], [43], [44], [45], [46], [47]. However, the routing can be solved independently. There are two possibilities for carrying the traffic: the first one is routing all the traffic between the source and destination nodes using a single route or through multiple routes. Furthermore, some traffic requests may require less bandwidth than the total capacity of the lightpath. Assigning a lightpath to carry this single traffic flow would be highly inefficient since the unoccupied bandwidth would be misused. Consequently, it is common to carry or groom multiple low-speed connections or flows into a high-capacity lightpath. In this manner, the network throughput, i.e., the amount of traffic successfully carried by the network is maximised, and the network cost is optimised. This technique is known as traffic grooming [69]. When we consider static traffic demands, the traffic grooming subproblem can be considered an optimisation problem and, therefore, can be solved using an ILP formulation as the presented in [69], [70]. However, the traffic grooming problem has been shown to be NP-Hard [71], [72], [73] and thus, this kind of formulations will not be able to solve the traffic grooming problem in polynomial time when the network size increases. Therefore, there are in literature traffic grooming solving methods based on heuristics, as the ones presented in [74] and [75]. 2.1.1.4 Survivable WRON Given the amount of traffic that optical networks carry, due to the increasing number of connected users and the apparition of new applications and services, a failure of the equipment or the fibres composing the network can cause the disruption of one or more established lightpaths and, consequently, a dramatic loss of information. Therefore, it is important to provide fault-recovery schemes to ensure the survivability of the connections. Fault-recovery can be performed in the electrical domain. In this domain, protection schemes will generally aim at rerouting the affected traffic using existing lightpaths with spare capacity. Fault-recovery mechanisms in the optical layer reroute the traffic affected by a lightpath disruption through a new lightpath. The mechanisms can be classified into two types: protection and restoration. In protection, backup resources as routes and wavelengths are precomputed and reserved in advance for all or some lightpaths [76]. In restoration, however, a new route and wavelength are dynamically discovered and employed to transport the traffic affected by a connection interruption [77]. Some advantages of dynamic restoration schemes are the efficient use of network resources since they do not reserve backup resources in advance and the provided resilience against different types of failures. However, this sort of schemes cannot guarantee the recovery of interrupted connections, as protection schemes do. Furthermore, protection schemes shorten the reaction time to failure [12]. Depending on the network topology, protection schemes can be classified as ring protection and mesh protection. The mesh protection schemes can be further classified as: 1. Path protection: This sort of schemes provides end-to-end protection to a path. Both 26 Chapter 2. Evolution of Optical Networks Figure 2.2: Channel comparison between Fixed DWDM Grid with 50 GHz channel spacing (1) and Flexgrid with 6.25 GHz spacing between Central Frequencies (2). 2.2. EON 27 route them together until arriving to the destination node. Consequently, traffic demands greater than wavelength capacity can be accommodated in tailor-made super-channels, making a more efficient use of the spectrum since super-wavelength accommodation reduces the introduction of guard-bands. This feature does not eliminate, however, the requirement of adding guard-bands between two adjacent super-channels. 3. Aggregation: EON is able to aggregate multiple requests to be transmitted over a single super-channel, hence saving utilised spectrum. 4. Bandwidth Variation: Since the capacity demand of an established path can vary with time, EON is able to dynamically adjust the allocated spectrum to a connection. 5. Efficient multiple data rate accommodation: The flexible assignment of spectrum enables the possibility of accommodating mixed data-bit rates in the optical domain in contrast to WRON, where accommodating low bit rate signals can lead to the stranding of the optical bandwidth, due to the excess of frequency spacing. 6. Reach-adaptable line rate: The ability to vary the employed modulation formats and the number of subcarriers enables EONs to support line rates adapted to the optical reach, as well as the dynamic expansion or contraction of the allocated bandwidth to a connection. 7. Energy Saving: When the carried traffic decreases, EONs are able to turn offsome subcarriers, hence reducing the energy consumption. 8. Network virtualisation: It is possible to virtualise the network by creating virtual links that can be supported by the subcarriers. Adding flexibility to the optical transport network promises higher spectrum efficiency compared to WDM, but also poses new challenges in the network optimisation. One of these issues is the optimisation of the connection establishment. Since EON allocates portions of spectrum to a connection, instead of full wavelength capacity, the RWA problem transforms now in the Routing and Spectrum Assignment (RSA) problem, i.e., deciding which portion of spectrum and route should be allocated to a connection, considering two key conditions: the bandwidth that the connection occupies must be the same throughout the whole route, restriction referred to as the spectrum continuity constraint, and the bandwidth must be contiguously allocated, condition known as the spectrum contiguity constraint. In the following subsection we will focus on the RSA problem. 2.2.1 The RSA problem While in WRON the RWA problem must be solved to allocate a route and a wavelength to a connection, in EON an analogous problem must be solved, only that it is a portion of spectrum, instead of a wavelength, the resource to be allocated to a connection. Hence, the basic problem to solve when facing the network design phase, i.e., when allocating network resources to a connection request is the Routing and Spectrum Assignment (RSA) problem. In this case, the network receives a connection request with an associated bandwidth demand. The problem is finding a set of contiguous FSs that satisfies the demanded capacity. If there are not enough 28 Chapter 2. Evolution of Optical Networks contiguous slots along the chosen path and the contiguity constraint cannot be satisfied, then it is possible to break the connection into smaller demands, where each new demand would require less contiguous FS. Furthermore, the continuity constraint must be fulfilled, in the same manner as in the RWA in the absence of wavelength converters, i.e., the same FSs must be allocated at each link composing the path [109]. Elastic networks, however, not only bring flexibility in terms of allocated spectrum but also offer other flexibility degrees as the power level or the modulation format. When the latter area is to be taken into account, then the problem is referred to as the Routing, Modulation Level, and Spectrum Allocation (RMLSA) problem. 2.2.2 The Static RSA problem The RSA problem can be jointly solved using mathematical methods like ILP and MILP, as in RWA. These methods will optimally solve the problem but, just as in the RWA case, they could lead to high computational complexity, particularly when the network is large, since the RSA problem is shown to be NP-Hard [109], [110], [113]. Therefore, these methods are more suitable to solve the offline RSA problem, in which the traffic matrix is known in advance. For example, Klinkowsky and Walkowiak proposed in [114] an ILP formulation for solving the joint RSA problem that aims at minimising the number of FSs allocated to at least one connection. Christodoulopoulos et al. [110] proposed an algorithm which precalculates kpaths between each source-destination pair and then applies an ILP model to solve the joint RSA problem which finds the path and the starting frequency of the allocated bandwidth, minimising the total used spectrum. Wang et al. presented in [115] an ILP formulation that jointly solves the RSA problem, minimising the maximum subcarrier index in all the fibres, as well as the total allocated subcarriers over the fibres of the network. In [116], Cai et al. presented an ILP formulation which jointly solves the RSA problem and minimises the maximum FS index employed in the network. Miyagawa et al. [117] proposed two ILP models for static EON in intra-data centre networks, the first aiming at minimising the number of utilised FSs and the second aiming at maximising the number of served traffic requests under the given number of FSs. These methods are summarised in Table 2.6. Many studies also tackle the joint static RSA problem proposing heuristics, that will be able to find a solution to the problem in polynomial time. This is the case for Klinkowsky and Walkowiak, who also proposed in [114] a heuristic which minimises the maximum FS index used in the network. The heuristic examines each candidate path for all the demands, in decreasing order of demanded FSs, and selects the path for which there is a set of FSs that satisfy the traffic demand and the index of the initial FS is the smallest between the initial FSs indexes of the candidate paths. Cai et al. also proposed a greedy algorithm for joint RSA problem-solving in [116], based on spectrum window, i.e., a window or set of available FSs, whose size can vary according to the traffic demand. Hence, the algorithm calculates the hoplength of the shortest path between each source-destination pair of nodes. Then, for each demand, the algorithm creates a plane or layer for each spectrum-window. This layer contains a virtual topology with the links in which the spectrum window is available. Finally, for each layer, the algorithm computes the shortest path between source and destination and selects the shortest path. If no path is selected, a new FS is added, and the algorithm repeats the process. Finally, Wang et al. [113] presented two heuristics to solve the RSA problem aiming at minimising the maximum subcarrier index, called Shortest Path with Maximum Spectrum 2.2. EON 29 Authors RSA solving strategy Technique Objective Klinkowsky and Walkowiak et al. [114] Joint RSA ILP Minimises the allocated FSs Christodoulopoulos et al. [110] Joint RSA ILP Minimise used spectrum Wang et al. [115] Joint RSA ILP Minimises maximum FS index and allocated FSs over the fibres of the network Cai et al. [116] Joint RSA ILP Minimises maximum FS index employed in the network Miyagawa et al. [117] Joint RSA ILP Two objectives: •Minimises number of utilised FSs •Maximises number of served traffic requests Table 2.6: Summary of static RSA techniques that propose a linear programming formulation. 30 Chapter 2. Evolution of Optical Networks Reuse (SPSR) and Balanced Load Spectrum Allocation (BLSA). In the former, requests are sorted in decreasing order of demanded FSs and, for each request, allocates the shortest path and the lowest-indexed consecutive FSs available. The same spectrum slots allocated to a given request can be reused in a different one if the paths are link-disjoint. BLSA is a threestage heuristic that first computes k−shortest paths for each source-destination node pair, then checks which of the computed paths minimises the maximum fibre load and finally allocates the lowest-indexed consecutive FSs. The techniques are summarised in Table 2.7. As in WRONs, the RSA problem can be solved as a subproblem of the Virtual Topology Design (VTD). The VTD problem comprises the selection of lightpaths to be established, the allocation of network resources solving the RSA problem and the routing of the traffic through the established lightpaths. Zhao et al. [118] propose an ILP to solve the topology design and the resource allocation problems in EON, with the objective of minimising the maximum used FS index on any link of the topology. The proposal includes a list scheduling heuristic that reduces the request blocking and the bandwidth blocking compared to first fit based heuristics. Yu et al. [119] proposed a MILP formulation and a heuristic to solve the topology design and network resource allocation problems, minimising the power consumption. Velasco et al. [120] propose an ILP formulation that solves the topology design as an RMSA problem, minimising the capital expenditures (CAPEX) of the network. Authors RSA solving strategy Technique Objective Klinkowsky and Walkowiak et al. [114] Joint RSA Path Shorting and selection of lowest indexed FS Minimises the allocated FSs Cai et al. [116] Joint RSA Greedy algorithm Minimises maximum FS index employed in the network Wang et al. [115] Joint RSA SP+Spectrum reuse and balanced load spectrum allocation Minimises maximum FS index and allocated FSs over the fibres of the network Table 2.7: Heuristics to solve the RSA problem. 2.2.3 The Dynamic RSA problem In dynamic scenarios, upon a connection request, the network should be able to provision a traffic demand with an available portion of spectrum and a route in a brief period of time. Since the RSA problem is NP-Hard, methods as ILP are not particularly suitable to solve the problem in these scenarios, since they will not solve the problem in polynomial time. Hence, it is very common to find proposals based on heuristics and meta-heuristics, to solve the dynamic RSA problem. These methods can be divided into one-step RSA and two step-RSA. 2.2. EON 31 In one-step RSA, the routing and the spectrum assignment are jointly solved employing just one step. Wan et al. [121] proposed in two heuristics that jointly solve the RSA problem. The Spectrum-Constraint Path Vector Searching Algorithm (SPV) builds a decision tree whose route is the source node and whose leaves are adjacent nodes in the path whose connecting link has enough available to satisfy the bandwidth demand, including the guard-band. If there is enough spectrum, the algorithm adds the node to the decision link and repeats the process between this node and the following hop in the path. Finally, it selects the path with enough available spectrum and minimum cost. Additionally, authors presented a modified version of Dijkstra’s Shortest Path (Modified Shortest Path, MSA), in which the algorithm computes the shortest path between source and destination and checks each link to calculate the aggregated available spectrum along the whole path. In this manner, the algorithm is able to verify that the same consecutive FSs are available in all the links composing the path. At the same time, the algorithm checks if the portions of available spectrum satisfy the bandwidth and guard demands. Salani et al. [122] presented an ILP to solve the RSA in one step, aiming at minimising the number of transceivers and the number of FSs in use. If multiple modulation formats are included, then the solution includes reach constraints and becomes the Routing, Modulation and Spectrum Assignment (RMSA) problem. Furthermore, the ILP is enhanced with machine learning techniques to include Quality of Transmission (QoT) estimation in the solution. Leiva et al. [123] proposed a Dynamic Graph Coloring algorithm that jointly solves the RSA problem. For each FS in the spectrum, the algorithm builds sub-graphs that include the links with enough available FSs to satisfy the traffic demand, assuming that the first FS in the available set is the checked FS. When the sub-graphs are built, the algorithm looks for the shortest path in terms of number of hops and assigns the path and the available FSs. On the other hand, the RSA problem can be addressed by breaking it up into the routing and the spectrum allocation problems and solving them separately, in a similar approach as the RWA problem. The routing problem can be addressed through two different approaches. The first tactic would not consider the elastic characteristics of EONs. In this case, analogous algorithms to those employed to solve the RWA problem can be adopted. Therefore, we can employ Fixed Routing or Fixed Alternate Routing as in [124], Adaptive Routing like Alyatama et al. employed in [125], or Least Congested Routing, in which the algorithm selects the path among a set of predetermined routes between the source-destination pair, with more FSs available, i.e., the least congested path [12], [109]. The second tactic, on the other hand, would account for the elastic features of EONs. Single path routing in the RSA approach can lead to spectrum fragmentation, i.e., the introduction of gaps, or not utilised spectrum, which is a frequent issue in dynamic scenarios. This problem may produce connection blocking since the remaining sets of contiguous FSs may not be enough to allocate the connection, although there might be enough overall spectrum. Hence, to overcome this issue, we can employ routing approaches that account for this issue as multi-path or spectrum splitting routing [126], [127], [128] in which the request is split into two or more paths, provided that the consecutive available slots of the paths satisfy the traffic demand of the request. Finally, the spectrum allocation problem can be solved through one of the following algorithms: 1. First Fit (FF): In this scheme, the FSs are indexed and a list of the available and utilised 32 Chapter 2. Evolution of Optical Networks FSs is maintained. The algorithm precalculates k-shortest paths between the source and destination nodes and sorts it in increasing length order. Then, it searches for a set of contiguous FSs that satisfies the traffic demand, also in ascending index order, i.e., aiming at allocating the lowest-indexed FSs first. If the algorithm finds spectrum to allocate to the demand, it stores the assigned FSs in the not available FSs list. When the connection is released, the slots return to the available slot list. This policy is employed in [129], [130], [131]. 2. Random Fit (RF): This scheme was proposed in [130] and it randomly selects spectrum portions among the list of available FSs. These portions must be big enough to satisfy the traffic demand and must be the same in all the links conforming the first found route 3. Last Fit: Similar to FF in the functioning, this policy, however, attempts at allocating the highest indexed FSs to a lightpath [132]. 4. Lowest Starting Slot (LSS): presented in [133], the policy tries to allocate the first set of available FSs that satisfy the traffic request. The policy examines the available paths between the source and destination nodes, and the available slots from the ones with lower index to the ones with higher index. The policy assigns the path with the lowestindexed available slots among the candidate paths. 5. First-Last-Exact Fit (FLEF): This policy [134] separates connections into two groups: non-disjoint and disjoint. Disjoint requests are solved using First-Exact Fit which, similarly to FF, tries to assign the first (and thus the lowest-indexed) set of FS which exactly adapt to the traffic demand, or assigns the lower indexed FS if no exact fit is found. On the other hand, non-disjoint requests are solved using Last-Exact Fit, which attempts at allocating the highest-indexed FSs that exactly fit the traffic demand. If no exact fit is found, allocates the first, higher-indexed available slots. In this manner, the number of contiguous slots is maximised, and so the policy reduces the blocking probability. 2.2.4 Issues related to the performance of RSA There are aspects related to EONs, as the fragmentation, survivability and traffic grooming issues, that may impact the performance of the RSA algorithms. In this subsection we will briefly describe them and their effects on the performance of RSA. Fragmentation: Since EONs assign contiguous FSs to the connection requests that adjust the demanded bandwidth, a dynamic set up and tear down of lightpaths can cause available FSs to be isolated between them. This condition is known as fragmentation and complicates the employment of the isolated FSs in upcoming connections [109]. Fragmentation can be managed through the RSA algorithms employed to provision a connection. For example, proposals in [135], [136], [137] employ the multipath transmission, which divides a request into various, smaller connections and transmits them through different paths. Moura et al. [138] proposed a heuristic based on multigraph, a graph where vertices can have various edges. In their proposal, the vertices are the OXC of the network and there are as many edges connecting the OXCs as FSs in the spectrum of each link. Using this grapth, authors calculate the number of FSs required to satisfy the traffic demand and propose a 2.2. EON 33 heuristic which selects the available consecutive FSs which satisfy the demand and reduce the overall power consumption and bandwidth blocking, according to a cost model proposed by the authors. Moreover, a partition approach can be employed. This technique makes partitions out of the spectrum and classifies lightpaths, both according to some criteria. In this manner, the technique can dedicate each partition to one sort of lightpath, as in [134]. Lastly, Waldman et al. proposed a deadlock-avoidance technique [139] that aims at reducing fragmentation by only assigning network resources if the allocated link, after reserving resources, is fully utilised or if the available spectrum resources are enough to accommodate another traffic request. Bórquez-Paredes et al. [140] compared this strategy to other greedy techniques as first fit and last fit and showed that the deadlock-avoidance strategy was able to reduce fragmentation and bandwidth blocking. Nevertheless, a new type of blocking due to the restricting criteria to accept connection requests raised with this technique. Additionally, fragmentation can be addressed through an operation called defragmentation, in which the existing connections and allocated spectrum are periodically reconfigured. In this manner, the misuse of spectrum resources and the bandwidth rejection, i.e., the rejection or blocking of incoming requests because of the inexistence of enough consecutive FSs to fulfil the traffic request, are avoided [19], [109]. Dá et al. [141] proposed two meta-heuristics based on Ant Colony Optimisation and Genetic Algorithms that aim at reducing the request blockage by deciding the best set of lightpaths to be proactively rerouted. Furthermore, there are various defragmentation techniques, as the hop-tuning, the make-before-brake technique, and the push-and-pull approach [19], [142], that aim at reducing the misuse of spectrum. The hop-tuning approach [143] keeps the physical route of the lightpath but moves the allocated slots to other, available slots. The push-and-pull technique [144] changes only the allocated slots to a connection, by first increasing the allocated resources to the connection, then pushing the central frequency so that it is moved as near as possible to the side of the adjacent lightpath and finally reconfiguring the allocated resources to reduce them to the original number of assigned slots. Finally, the make-before-break technique [145] provisions a new connection between the source and destination nodes of the lightpath to be defragmented. The routes of the old and new lightpaths are link-disjoint. The traffic is shifted from the original connection to the new lightpath and then the original lightpath is torn down. A comprehensive survey about fragmentation can be found in [142]. Traffic Grooming: Traditionally employed in WRON, traffic grooming consists in aggregating low-speed connection requests into a higher capacity traffic flow (e.g. a lightpath) to improve the spectrum utilisation. In EON this technique was introduced because (i) it allowed to make a better use of the transponder capacity, given the limitations in slicing that BV-T presented in their early stages [134] and (ii) it allowed to improve the use of the spectrum, since electrically aggregating low-speed connection into a higher capacity traffic flow reduced the introduction of guard-bands between channels [109]. Traffic grooming can be performed electrically by employing electrical subcarrier multiplexing and switching [146], [147]. However, it requires additional O/E/O conversions and switching requirements at the intermediate nodes, incrementing the energy consumption [147], [148], [149]. Furthermore, in order to overcome the limitations of BVTs, researchers developed the Sliceable BVT, a device capable of supporting different modulation formats, bit rates, transmission distances and sliceability [109],[147], [150]. Employing these devices, traffic grooming can be partially performed at the optical layer, by aggregating in the optical 34 Chapter 2. Evolution of Optical Networks layer different low capacity connections into one BVT and switch them as an optical tunnel or group of optical paths, where a guard-band to separate the different services inside a network should be added [147], [148], [151]. Optical grooming can be planned offline, i.e., for static traffic. For example, Zhang et al. [148] proposed an ILP formulation and a heuristic to perform optical grooming with the possibility of minimising either the consumed spectrum or the number of employed transponders. It can also be performed under dynamic traffic, as the proposal by Khodashenas et al. [152], a heuristic that solves the RSA problem with traffic grooming to minimise the spectrum and transmitter usage in the network. Furthermore, traffic grooming can be performed considering aspects as fragmentation or survivability. A survey on traffic grooming in EONs can be found in [147]. Survivability: As in WRON, a connection disruption in EON can cause the loss of an incredible amount of data, as well as affect thousands of users. Hence, it is important to provide fault-management mechanisms that minimise the effects of a failure in the network. EON’s fault-management techniques can be classified as protection and restoration. In protection, backup lightpaths are precomputed before a failure event. They can be dedicated, if the backup lightpath only protects a primary connection, as in the proposed offline RSA algorithms by Klinkowski et al. [153], or shared, where the backup lightpath can protect various primary lightpaths, provided they are link-disjoint as in the proposals by Shao et al. [154] or Wang et al. [155]. The second class of fault-management techniques is restoration. This approach searches resources for a new lightpath when a failure happens, employing the available resources at the moment of the failure. Since sometimes it is not possible to allocate the full capacity of the primary connection to the backup lightpath, approaches as the bitrate squeezing used in [156], [157], in which just part of the capacity is recovered, or the multipath transmission employed in [157], in which the original capacity is split among multiple connections, are explored. 2.3 Conclusions The increasing traffic that transport networks must carry and the apparition of new services demanded new technologies which closed the gap between the capacity of optical fibre and the actual transmission capacity of electronic equipment. WDM closed this gap by allowing the transmission of multiple channels at electronic speeds over the same physical links. These channels are composed of a set of fibres or route and a wavelength and are called lightpaths. Moreover, the set of lightpaths established over a physical network topology is called Virtual Topology. The Virtual Topology Design is a highly complex problem and, in consequence, can be solved in one step or divided into various subproblems: Topology design, Routing and Wavelength Assignment (RWA) for embedding the design topology, and Traffic Grooming. We have explained the main methods to solve these subproblems. In dynamic scenarios, on the other hand, lightpaths are provisioned and set up upon request arrival and tear down after a given holding time. In this type of scenario, the RWA problem becomes the dynamic RWA problem. Therefore, we have reviewed the most important proposals to solve the RWA problem dynamically. Nevertheless, the increasing traffic required more spectrum efficient routing techniques. Some technological breakthroughs as the apparition of new modulation formats, the BV- 2.3. Conclusions 35 Figure 2.3: Summary of the chapter. Transponder and the WXC, combined with the adoption of a new frequency grid that divided the spectrum into slots described by their central frequency and width and with a smaller channel spacing favoured the apparition of Elastic Optical Networks. One of the most interesting features of EONs is their ability to provision portions of spectrum to the connections, instead of full wavelength capacity. Therefore, EONs are able to provision just the required capacity, increasing the spectrum efficiency. In this kind of networks, the RWA problem becomes the Routing and Spectrum Assignment Problem in its basic form. Moreover, other flexibility parameters like the modulation level, can be considered during the routing and spectrum assignment problem. In that case, the problem is known as the Route, Modulation Level and Spectrum Assignment (RMLSA) problem. We have also reviewed the most important methods to solve both the static and the dynamic RSA problem and some issues related to EONs that can affect the performance of the RSA algorithms. In the next Chapter, two sets of RSA algorithms to solve the dynamic, centralised RSA problem are introduced. The first set combines different flexibility degrees regarding the assignment of the spectrum and the possibility of splitting the request into multiple sublightpaths with traditional routing and spectrum assignment methods as shortest path and first fit [62]. The second set combines the same flexibility degrees with first fit and a new spectrum assignment method named Best Gap (BG). We will study the performance of the proposed methods in terms of blocking rate and analyse the benefits of introducing different flexibility degrees in the RSA algorithms. 42 Chapter 3. Exploiting Different Types of Flexibility in EONs Algorithm 2 Disjoint Spectrum Flexgrid (DSF) 1: procedure DSF(origin,destination,bandwidth,lpHoldingTime,slotS ize,guardbandS ize) 2: remainingCapacity ←bandwidth 3: paths ←kShortestPaths(origin,destination) 4: for i=0, i <size(paths), i++ do 5: search ←true 6: while search =true do 7: f ibres ←getFibres(paths[i]) 8: occupiedFrequencies ←getOccupiedSlots(f ibres) 9: availableS lots ←getAvailableSlots(occupiedFrequencies) 10: demandedS lots ←(bandwidth +guardbandS ize)/slotS ize 11: allocatedS lots ← findSuitableSetOfSlots(availableS lots,demandedS lots) 12: if size(allocatedS lots),0then 13: allocatedCapacity ← calculateAllocatedCapacity(guardBand,allocatedS lots) 14: remainingCapacity ←remainingCapacity −allocatedCapacity 15: reservedS lotsAndPathMatrix ←[allocatedS lots,paths[i]] 16: if remainingCapacity =0then 17: search =f alse 18: else 19: search =f alse 20: if remainingCapacity ,0then 21: for i=0, i <size(reservedS lotsAndPathMatrix), i++ do 22: releaseResources(reservedS lotsAndPathMatrix[i]) 23: blockConnection(origin,destination,bandwidth) 24: else 25: for i=0, i <size(reservedS lotsAndPathMatrix), i++ do 26: establishConnection(reservedS lotsAndPathMatrix[i]) 3.1. RSA Algorithms 43 2.1. Calculates and sorts available slices in the route in a matrix in increasing order of index, i.e., from the lowest to the highest frequencies. 2.2. For each slice: 2.2.1. Checks if the slice is equal or greater than the requested bandwidth. 2.2.1.1. If an available block is found, the algorithm stops the search, allocates the required spectrum and establishes the connection. When the set up time is finished, the algorithm tears down the connection and releases the resources. End the algorithm. 2.2.1.2. Otherwise, checks the next spectrum slice. 3. If the algorithm is not able to assign a a slice of spectrum after checking all the computed paths, the request is blocked. Algorithm 3 shows the pseudocode for the Joint Spectrum Gridless RSA algorithm. Algorithm 3 Joint Spectrum Gridless (JSG) 1: procedure JSG(origin,destination,bandwidth,lpHoldingTime,guardbandS ize) 2: establishedConnection ←f alse 3: paths ←kShortestPaths(origin,destination) 4: for i=0, i <size(paths), i++ do 5: f ibres ←getFibres(paths[i]) 6: occupiedFrequencies ←getOccupiedBandwidth(f ibres) 7: availableS lices ←getAvailableSlices(occupiedFrequencies) 8: demandedCapacity ←bandwidth +guardband 9: allocatedBandwidth ← findSuitableSlice(availableS lices,demandedCapacity) 10: if size(allocatedBandwidth),0then 11: establishConnection(paths[i],allocatedBandwidth,lpHoldingTime) 12: establishedConnection ←true 13: break 14: if establishedConnection =f alse then 15: blockConnection(origin,destination,bandwidth) Since a guard-band between two consecutive channels must be included to avoid interference, our algorithm computes the required spectrum as S=B+G,(3.4) where Sis the size of the allocated portion of spectrum, Bis the requested bandwidth and Gis the size of the guard-band, all measured in Hz. 3.1.4 Disjoint Spectrum Gridless (DSG) Lastly, the fourth proposed method, shown in Algorithm 4, works in a similar manner to DSF, but considering the gridless approach and, consequently, assigning slices of spectrum to each sub-lightpath. Therefore, upon a traffic request, the algorithm performs the following actions: 44 Chapter 3. Exploiting Different Types of Flexibility in EONs 1. Calculates the kshortest paths between the source and destination nodes and sorts them in increasing order of hop length. 2. For each path: 2.1. Calculates and sorts available slices in the matrix in increasing order of index, i.e., from the lowest frequencies to the highest ones. 2.2. For each slice: 2.2.1. Checks if the slice size is greater or equal to the requested bandwidth. 2.2.1.1. If an available slice of proper size is found, stops the search, allocates the slice and establishes the sub-lightpath. When the holding time is finished, the algorithm tears down the sub-lightpath and releases the resources. End the algorithm. 2.2.1.2. If a slice is found, but the size is insufficient to meet the requested bandwidth, reserves the available frequencies, updates the remaining bandwidth that requires allocation and continues the search until all the demanded traffic is allocated or all the available slices are checked. 3. If the algorithm is not able to find enough slices to satisfy the traffic request after checking all the computed paths, the reserved resources are released, and the request is blocked. Again, in the gridless techniques, a guard-band between adjacent sub-lightpaths is added to avoid interference. Therefore, the actual bandwidth allocated to the sub-lightpath ican be calculated as Bi=Si−G,(3.5) where Biis the allocated bandwidth to the sub-lightpath, Siis the size of the allocated portion of spectrum and Gis the guard-band size, all measured in Hz. Therefore, the remaining bandwidth Brto be allocated after reserving resources for the sub-lightpath iis updated according to the expression: Br=B− i X j=1 Bj(3.6) 3.1.5 Performance Comparison In this subsection we evaluate the performance of the proposed algorithms in terms of blocking ratio and execution times. To that aim, we have implemented a flexible optical network simulator using the C++ based, discrete event simulator OMNeT++ [159] (see Appendix A). We have chosen the 14−node NSFNet physical topology for this study, where we assumed that the cable connecting two nodes of the network consists of two unidirectional fibres, one for each direction. We set the capacity of each fibre in 4 THz. The lightpath requests arrive at the network following a Poisson process, while the source and destination nodes of each request are randomly selected using a uniform distribution U(0,N−1), where N=14 represents the number of nodes. Moreover, the requested traffic for each lightpath is also randomly generated using a uniform distribution U(Bwmin,Bwmax) where 3.1. RSA Algorithms 45 Algorithm 4 Disjoint Spectrum Gridless (DSG) 1: procedure DSG(origin,destination,bandwidth,lpHoldingTime,guardbandS ize) 2: remainingCapacity ←bandwidth 3: paths ←kShortestPaths(origin,destination) 4: for i=0, i <size(paths), i++ do 5: search ←true 6: f ibres ←getFibres(paths[i]) 7: while search =true do 8: occupiedFrequencies ←getOccupiedSlots(f ibres) 9: availableS lices ←getAvailableSlices(occupiedFrequencies) 10: demandedBandwidth ←bandwidth +guardbandS ize 11: allocatedBandwidth ← findSuitableSlices(availableS lices,demandedCapacity) 12: if size(allocatedBandwidth),0then 13: allocatedCapacity ← calculateAllocatedCapacity(guardBand,allocatedBandwidth) 14: remainingCapacity ←remainingCapacity −allocatedCapacity 15: reservedBandwidthAndPathMatrix ←[allocatedBandwidth,paths[i]] 16: if remainingCapacity =0then 17: search =f alse 18: else 19: search =f alse 20: if remainingCapacity ,0then 21: for i=0, i <size(reservedBandwidthAndPathMatrix), i++ do 22: releaseResources(reservedBandwidthAndPathMatrix[i]) 23: blockConnection(origin,destination,bandwidth) 24: else 25: for i=0, i <size(reservedBandwidthAndPathMatrix), i++ do 26: establishConnection(reservedBandwidthAndPathMatrix[i][0]) 46 Chapter 3. Exploiting Different Types of Flexibility in EONs Bwmin =1 GHz and Bwmax =300 GHz. The holding time for each connection is calculated using the exponential distribution: exponential(0,averageLightpathHoldingTime).(3.7) Finally, the frequency in which the requests arrive at the network is calculated using an exponential distribution exponential(avRequestInterval,0),(3.8) where avRequestInterval =averageLightpathHoldingTime load ·(nodes −1) ·Bwmax −Bwmin 2·Bwmax (3.9) and 0.1≤load ≤0.9 in normalised Erlangs. We added a guard-band of size 10 GHz between adjacent connections in the four schemes. For the schemes implementing the flexgrid spectrum approach, the guard-band was accommodated inside the last slot of each established superchannel. Furthermore, in these schemes we explored the results for different granularities, and hence the FS width could take the values 12.5,25,50 and 100 GHz, being the 12.5 GHz width the most common size employed in the studies of Elastic Optical Networks. In the gridless methods, the guard-band is also accommodated at the end of each superchannel. The algorithms pre-compute k−shortest paths. Simulations for k=1,3 and 5, i.e., for different numbers of kpaths between each pair of nodes, were performed. The results are plotted in average with 95% confidence intervals. Figure 3.2: Blocking ratio for the JSF algorithm when k=1, for different slot granularities. Figure 3.2 shows the blocking ratio for all the possible values of FS width and k=1, i.e., when the algorithm checks only the shortest path. Results show that the largest slot width is the configuration which obtains the highest blocking rate, due to the lack of precision in the bandwidth assignment offered by large FSs. Results show that the best performance is achieved when the slot width is fixed in 12.5 GHz, and for low network loads can be approximately a 3.1. RSA Algorithms 47 78% lower than the blocking ratio of JSF for a 100 GHz slot width. With regard to the other possible values of slot width, the second-best performance is achieved by the second-smallest FS width, i.e., 25 GHz, so the third-best performance is achieved when the FS has a width of 50 GHz. Therefore, smaller slot sizes achieve better results, as they make more efficient use of the spectrum. Figure 3.3: Blocking ratio for the JSF algorithm when k=3, for different slot granularities. Figure 3.4: Blocking ratio for the JSF algorithm when k=5, for different slot granularities. 48 Chapter 3. Exploiting Different Types of Flexibility in EONs If we increase the possible number of paths to 3 and 5, the best performance is obtained with a width of 12.5 GHz as shown in Figures 3.3 and 3.4 respectively. This result was expected given that, with a smaller slot size, the spectrum allocation is performed in a more precise manner. Furthermore, the increment of the number of possible paths which can be assigned to a connection also causes an increment of the probability of finding a path with available bandwidth and, therefore, the blocking ratio decreases. We can observe this tendency in Figure 3.3 and, particularly, in Figure 3.4, where the blocking ratio is close to 0 for loads lower than 0.4 and a slot size of 12.5 GHz. Figure 3.5 shows that JSF with T=12.5 GHz and k=5 obtains lower blocking ratio compared to JSF with the same slot size and lower number of k, which confirms that allowing for a higher number of possible routes between the source and the destination decreases the blocking ratio in this kind of scheme. Figure 3.5: Blocking ratio for the JSF algorithm when k=1,3,5 and T=12.5 GHz. Next, we present the results for the DSF scheme, which assumes that the spectrum is divided into slots, and splits, if necessary, the traffic request into multiple sub-lightpaths, if there is not a set of contiguous FSs which satisfies the requested bandwidth. Although initially it could be thought that splitting the request into multiple sub-lightpaths can minimise the blocking rate, it is also important to consider the inefficiency in the spectrum utilisation in which this kind of scheme incurs since they have to add a guard-band to each newly established connection. We can see in 3.6 the blocking ratio achieved by this scheme for all the slot width granularities when k=1. Figure 3.6 shows that the best performing size are 25 and 50 GHz. It can be observed that the scheme with slot size of 12.5 GHz, the size which achieved better results in JSF, is now the width value achieving the worst behaviour in terms of blocking ratio. Given the very narrow size of the slot, the scheme is able to split the capacity into many sub-lightpaths, but also wastes spectrum in allocating guard-bands to the new connections. A medium slot width, on the other hand, is able to achieve a good trade-offbetween the number of established sub-lightpaths and the misuse spectrum, reducing the blocking rate, as Figure 3.1. RSA Algorithms 49 3.6 shows. Moreover, increasing the number of possible paths also decreases the blocking rate, as happens when using JSF. This behaviour can be observed in Figures 3.7 and 3.8, which show the results for k=3 and k=5 respectively. In both cases, the best results are achieved when the 50 GHz slot size is employed. The 100 GHz slot size is able to improve the results of the 25 GHz slot size for high network loads when k=3, and totally when k=5. These results suggest a trade-offbetween slot size and guard-bands: small slot widths increase the precision of the bandwidth allocation, in DSF also implies a higher number of guard-bands, and therefore, the use of the spectrum. However, bigger sizes of slots offer less precise bandwidth allocation but also allows for the establishment of fewer connections and, consequently, the scheme employs less bandwidth to allocate guard-bands. Figure 3.6: Blocking ratio for the DSF algorithm when k=1, for different slot granularities. Lastly, Figure 3.9 shows the performance comparison of DSF when the slot width is 50 GHz for all possible values of k. We can observe that allowing more paths also increases the possibility of establishing enough sub-lightpaths to satisfy the traffic request, hence reducing the blocking ratio. We now present the results obtained by JSG and DSG, which follow the gridless approach and, in consequence, assign a spectrum slice whose size is equal or the closest possible to the demanded bandwidth plus the guard-band. Figure 3.10 shows the blocking ratio achieved by JSG for all values of k. The higher the number of possible paths is, the higher is the probability of finding a route which a spectrum block whose size is sufficient to meet the traffic request. Therefore, the blocking ratio obtained when k=5 is lower than the obtained with k=1 or 3. This behaviour can also be observed for DSG in Figure 3.11. However, this scheme establishes more connections since it splits a traffic request into as many sub-lightpaths of different allocated bandwidths as required to satisfy the demanded traffic. Therefore, it also 50 Chapter 3. Exploiting Different Types of Flexibility in EONs Figure 3.7: Blocking ratio for the DSF algorithm when k=3, for different slot granularities. Figure 3.8: Blocking ratio for the DSF algorithm when k=5, for different slot granularities. allocates part of the spectrum to create guard-bands, leading to inefficient use of the spectrum, as in the case of DSF. In consequence, although the blocking ratio is better for the lowest network loads than the obtained using the JSG method, the inefficiency in the spectrum utilisation leads to higher blocking ratio for the highest network loads. Lastly, we compare the performance of the different proposed methods. For this aim, we choose, for each scheme, the value of kand the slot size which present the better performance 3.1. RSA Algorithms 51 Figure 3.9: Blocking ratio for the DSF algorithm when k=1,3,5 and T=50 GHz. Figure 3.10: Blocking ratio for the JSG algorithm when k=1,3,5. in terms of blocking ratio. Figure 3.12 shows the blocking ratio of all the schemes in their best performing configuration. It can be seen that the lowest blocking ratio is achieved by DSF with a slot size of 50 GHz. Note that DSF with a slot size of 50 GHz is the configuration of a classic WRON, although in this case the split of the request into multiple sub-lightpaths is allowed. The DSG scheme, which is the more flexible method in terms of the spectrum allocation and sublightpath formation is the worst performing scheme, i.e., the method which leads to the highest blocking ratio. The result, therefore, suggests that allowing the splitting of the request into 58 Chapter 3. Exploiting Different Types of Flexibility in EONs (a) k=1 (b) k=3 (c) k=5 Figure 3.16: Blocking ratio achieved by JSF-BG when k=1,3 and 5 respectively. 3.2. The Best Gap (BG) Spectrum Assignment 59 (a) k=1 (b) k=3 (c) k=5 Figure 3.17: Blocking ratio achieved by DSF-BG when k=1,3 and 5 respectively. 60 Chapter 3. Exploiting Different Types of Flexibility in EONs (a) JSG (b) DSG Figure 3.18: Blocking ratio achieved by JSG and DSG when k=1,3 and 5. 3.3. Conclusions 61 Figure 3.19: Blocking ratio for the best performing configuration of the proposed RSA algorithms. disjoint traffic implies a reduction of the blocking ratio. For example, if we compare the most and least flexible methods, i.e., DSG-BG and JSF, we can observe that DSG-BG achieves a blocking ratio two orders of magnitude lower than the blocking ratio obtained by JSF. If we observe the computational times of the methods, which are shown in Figure 3.20, we can observe that applying the BG technique to the DSG helps to reduce the computational time required to solve the RSA problem. In the case of DSF, the computational time using BG is significantly higher than the computational time using FF. This is due to the fact that the best configuration of DSF-BG employs slots of 12.5 GHz of size, whilst DSF with First Fit uses slots of size 50 GHz, reducing the number of elements or blocks that must be checked and, in consequence, the computational time compared to DSF-BG. This technique, on the other hand, slightly increases the computational time for JSF-BG and JSG, although they are still feasible in a dynamic network. 3.3 Conclusions Elastic Optical Networks are a specially promising technology since they exploit the capacity of the fibre by assigning to each connection request the exact or nearly exact bandwidth that satisfies the demanded traffic. In this manner, the spectrum is used more efficiently and more traffic can be carried. In these kinds of networks, the routing and wavelength assignment (RWA) problem is transformed into the routing and spectrum assignment (RSA) problem. The routing problem can be solved using traditional routing techniques as k−shortest paths, while the spectrum assignment problem can be solved using strategies as first fit. However, this kind of technology allows exploring new techniques and strategies and flexibility levels for solving the RSA 62 Chapter 3. Exploiting Different Types of Flexibility in EONs Figure 3.20: Computational time for the best performing configuration of the proposed RSA algorithms. problem. In this Chapter, we have combined two degrees of flexibility to propose new RSA strategies. The first flexibility degree is to consider the spectrum divided into slots, like traditionally considered in most of the studies on EON, or to consider the spectrum as a block and assign a spectrum slice of size adjusted to the requested frequency. The second flexibility degree consists in allocating the requested bandwidth in one lightpath or allowing the split of the request into multiple sub-lightpaths, with different allocated bandwidth. Combining both flexibility levels we have proposed the JSF, DSF, JSG, and DSG algorithms. Results showed that combining the highest levels of flexibility with First Fit does not improve the performance of the network in terms of blocking ratio. In conclusion, when k−shortest paths and first fit are used as RSA algorithms, it is more effective to split the request into multiple sublightpaths to reduce the blocking ratio, instead of following the gridless approach and allocate spectrum slices. Consequently, new spectrum assignment techniques must be proposed to more efficiently exploit the flexibility of EONs. To address this problem, we propose the Best Gap technique, a spectrum allocation method which searches the most adapted set of consecutive FSs or spectrum slice, in terms of size, to the requested traffic. We have proposed four new RSA algorithms: JSF-BG, DSF-BG, JSG-BG, and DSG-BG. The use of BG improves the blocking ratio compared to First Fit. Furthermore, it helps to better exploit the flexibility, since the most flexible methods, i.e., DSF and DSG noticeably improve their performance compared with the same methods when the first fit technique is adopted. To conclude, EONs require efficient RSA methods to show their full potential. Our spectrum assignment proposal, Best Gap, is and efficient technique capable of exploiting the network flexibility and improve its performance in terms of blocking ratio, compared to other classical spectrum assignment algorithms as first fit. Chapter 4 NFV, SDN and MEC The increasing number of connected users and devices, as well as the appearance of new applications and network services, have pushed the evolution of optical networks and favoured the appearance of technologies as WRON or EON. However, emerging paradigms and applications as Cloud Networking, Big Data, Industry 4.0, Tactile Internet or Social Networking are demanding flexibility, adaptability, and ubiquitous access to the new networks. Furthermore, 5G, whose backbone is expected to be based on optical technologies, promises to bring new features like multi-tenancy, low latency services, high capacity, resource virtualisation or high-speed communications. In order to achieve these features, operators must face profound architectural changes in their networks. Moreover, the appearance of new computation and networking paradigms may facilitate the adaptation of communication networks to the new demands and the increasing traffic, while helping operators to reduce the investments and the capital and operational costs. In this chapter, the Network Function Virtualisation (NFV) paradigm, the technology that promises to reduce the management complexity and the network costs by deploying network functions as virtual appliances, is reviewed. The chapter also describes the architecture, the main building blocks and the most important design problems. Furthermore, two technologies related to NFV are briefly introduced: Software Defined Networking and Multi-access Edge Computing, reviewing their structure and main features. 4.1 NFV Overview Network Function Virtualisation is a network architecture paradigm emerged from the collaboration between industry and the European Telecommunications Standards Institute [1], with the aim of reducing the number of hardware appliances that populate current networks. In order to deploy new services, operators perform operations called Network Functions (NFs) on associated traffic. This NFs cover a variety of processes like Network Address Translator (NAT), Firewall (FW), Traffic Monitor (TM) Wide Area Network (WAN) optimizer, Intrusion Detection and Protection (IDP) systems, proxies, or load-balancers [160]. These NFs are chained, i.e., they are connected following a certain order to achieve the desired network functionality. Hence, the NFs are essential for the correct performance of the network. Commonly, NFs are deployed as proprietary hardware appliances called middleboxes. Each middlebox performs only one function and does not allow to perform more operations. 63 64 Chapter 4. NFV, SDN and MEC Furthermore, a middlebox is independently provisioned for peak loads and usually, middleboxes are managed separately. Additionally, they are expensive and their life cycle is short. Therefore, any time operators deploy a new service, they must acquire a number of new hardware appliances and manually integrate them in the network. As a consequence, operators incur in high Capital (CapEx) and Operational (OpEx) expenditures any time they deploy and operate a new service, with little revenue. Network Functions Virtualisation (NFVs) aims to solve the aforementioned shortcomings by using standard IT virtualisation techniques [161]. This networking paradigm proposes to deploy NFs as virtual appliances called virtual network functions (VNF). VNFs are hosted by commodity servers, which could be located in data centres, network nodes or even enduser premises [161]. Compared to current practices, NFV introduces the following major differences [162], [2]: •Software and Hardware Decoupling: In the traditional approach, NF are integrated software and hardware entities. The virtualisation approach separates software from hardware and leverages the possibility of an independent evolution of both parts. •Flexible Deployment of NFs: If a pool of hardware resources is installed, the virtualization of NFs enables the possibility of automatically deploying functions on this pool of resources. Furthermore, the virtualization approach also leverages the resource reallocation and sharing. •Dynamic Operation: The virtualisation approach allows the network operators to dynamically scale the NF performance according to the current network conditions. With the advent and deployment of NFV, not only can operators benefit from reduced equipment costs, network flexibility, and faster service deployment cycle, but also from multiversion and multi-tenancy network appliances, which allow sharing resources across services and customer bases and from the introduction of varied eco-systems [161]. However, there are some technical requirements to be considered during the deployment of an NFV infrastructure [162]: •Performance: Migrating from network functions implemented in dedicated hardware appliances to virtualised appliances may degrade some performance parameters as latency or throughput. Therefore, aspects as the performance of the deployed hardware platforms and the state of the network must be taken into account during the VNF deployment stage, in order to minimise the performance degradation. •Manageability and Scalability: The NFV infrastructure must be capable of creating and placing VNFs at the required time and location, allocate and scale hardware resources, and choose and connect the VNFs to create a service chain. The manager entity should also be able to make the best utilisation of resources and be able to detect and manage any failure in the VNF infrastructure. •Security: The deployment of a NVF environment brings new security concerns, due to the utilisation of third-party infrastructures, as data centres, new software elements as orchestrators and hypervisors, or the possibility of deploying software components from different vendors may introduce new vulnerability threads to the infrastructure that should be taken into consideration during the design stage. 4.1. NFV Overview 65 Figure 4.1: ETSI NFV Reference Architecture [1],[2]. •Reliability and Stability: Moving from dedicated hardware appliances to virtual appliances instantiated at prone-error hardware platforms may affect the performance of the services. It is important to deploy resilience and fault-management methods to ensure that the service level agreements and the reliability are guaranteed. Furthermore, migration should be performed so that the service continuity is not affected. The following subsection introduces the ETSI NFV reference architecture and the NFV technical requirements. 4.1.1 NFV Reference Architecture Figure 4.1 depicts the ETSI NFV reference architecture. The NFV architecture is divided into three key segments: Network Function Virtualisation Infrastructure (NFVI), NFV Management and Orchestration (NFV MANO) and Virtual Network Functions (VNFs). The NFVI [1], [2], [163] is the set of hardware and software resources that composes the environment in which to establish, execute and manage Virtual Network Functions (VNFs). The computing resources are assumed to be Commercial-Off-The-Shelf hardware, whereas the storage resources can be either shared Network Attached Storage (NATs) or the storage devices inside the COTS server. The physical infrastructure of the NFV can be geographically distributed among different NFV Points of Presence (NFV-PoP or PoP). Consequently, the network interconnecting those PoPs would be part of the NFVI, distinguishing between [2]: •NFV-PoP Network: The network which connects the computing and storage elements in an NFVI, including switching and routing for external communication. •Transport Network: The network connecting different NFV-PoPs and the network which connects the NFV-PoP with other network elements which do not belong to an NFV-PoP. This network can be owned by one or different network operators. The physical infrastructure provides the processing, storage, and connectivity to the VNFs through the Virtualisation Layer or hypervisor [2]. This layer is responsible for abstracting 66 Chapter 4. NFV, SDN and MEC the physical resources into virtual resources, providing these virtual resources to the VNFs and allowing the software that implements VNFs to make use of them, so that VNFs can be executed. NFV MANO [2], [164] is the element responsible for managing the NFVI resources and orchestrating the allocation of the resources necessary for the correct performance of the VNFs. Therefore, MANO manages the lifecycle of VNFs and physical resources and orchestrate hardware resources [1] among other tasks. The NFV MANO is composed of the following functional identities: •Virtualised Infrastructure Manager (VIM): This block is responsible for the control and management of the storage, computational, and network resources of the NFVI. •VNF Manager (VNFM): This block is responsible for the management of the VNF lifecycle. Among other functions, the lifecycle management would include operations like VNF instantiation, scaling (increase or reduction of the VNF capacity), update and upgrade of the VNFs, and release. One VNFM entity can manage multiple VNF instances. However, each VNF instance is managed by only one VNFM entity. •NFV Orchestrator (NFVO): This block is responsible for the NFVI resource orchestration. Therefore, this block would allocate and release resources to the VNFs through multiple VIMs. Furthermore, this identity manages the lifecycle of the Network Services, being responsible for instantiating, scaling, updating and releasing Network Services, among other functions. Finally, VNFs are the software deployment of the physical network functions. Each VNF would be managed by a functional block named Element Manager, responsible for tasks as configuration, accounting or security management of the VNFs. An EM may manage one or various VNFs in an NFV system. The set of Element Managers is called Element Manager System (EMS). In the next subsection we will explain in a little bit more detail the VNFs and the main research challenges. 4.1.2 Virtual Network Functions Any service offered by a network operator has a Service Chain (SC) associated with it. An SC is a concatenation of NFs or, if the NFV paradigm is applied to the network, a set of VNFs which must be traversed in a specific order. When deploying a new service, operators must make decisions regarding the following aspects of the VNF deployment: placement, chaining, scheduling, migration, and orchestration. The VNF-placement problem is the process for which operators decide the number of instances of the VNFs shall be created and which NFV-PoP hosts them. These NFV-PoPs can be Data Centres (DC), the Central Office (CO) or the nodes of the network. After placing the VNFs, it is also necessary to decide which instances are going to be part of the SC and the routes to connect each VNF to the following one in the SC. Furthermore, the chosen VNFs must be connected between them, so network resources must be allocated to the connections. This is known as the VNF-chaining problem. The VNF-scheduling problem englobes two design aspects. The first one is scheduling the VNFs required to provide a service. This aspect is commonly solved in conjunction with the VNF-placement problem [1]. The second aspect is finding the most adequate time slot to 4.1. NFV Overview 67 perform a given task or VNF on a traffic flow, since it can impact the resource scaling decisions. For example, assigning new traffic to an already active VNF instance may require the operators to allocate more computing resources to this VNF to maintain the Service Level Agreement (SLA) of the service. If that were not possible, it could even cause the rejection of the service request. Whereas allocating this traffic to another, less loaded, VNF instance may avoid the computing resource scaling and a possible service request rejection [165]. When the VNF-placement, chaining, and network resource allocation are solved jointly, the problem is commonly known as the VNF-orchestration problem [166]. Finally, the VNF-migration problem must be solved when VNFs migrate from one location to another. This event can be triggered due to hardware maintenance or to keep some performance requirements as load balance. In case of migration, the VNF state must also migrate to the new location. The VNF-placement and chaining problems have raised great interest in the scientific community. Consequently, we can find studies which may address different aspects of the placement and chaining processes, such as the resource allocation, the energy consumption, the load balancing, the latency or the blocking probability. It is also studied in different networks and network segments, such as Data Centre Networks (DCN), the metro/core networks or the access network. In the next subsection, we will cover some of the existing techniques in the literature that handle the VNF-placement and chaining problem for static scenarios. 4.1.2.1 VNF-Placement and Chaining Problem in Static Scenarios The VNF-placement and chaining problems can be solved in static scenarios where the traffic matrix, i.e., the number of service requests are known in advance. In this kind of scenarios, optimal solutions can be found using mathematical formulations such as ILP or MILP. Furthermore, the problems can be solved aiming at optimising different parameters or fulfilling diverse key performance indicators. Consequently, we can find studies aiming at the minimisation of resource consumption, energy consumption or to ensure that the latency requirements are fulfilled. There are several examples of VNF-placement studies that aim at finding an optimal solution through the development of mathematical models. Moens and Turck [167] presented an ILP formulation for solving the VNF-placement and chaining problems in hybrid and totally virtualised scenarios. The model aims at minimising the computational resource consumption and ensures that the network capacity is not exceeded and that the corresponding latency restrictions associated with each service are met. In [168], Lin et al. considered the NFV use case Link Level VNFs [169], in which traffic flows that are routed through a given set of links must also traverse a certain set of VNFs, and proposed a MILP formulation that, taking as inputs the set of end-to-end requests and the physical substrate network with the associated link and node capacities, solves the VNF- placement and chaining problem minimising the resource consumption. Bari et al. presented in [166] an ILP problem which decides the optimal number and placement of VNFs required to serve a given number of service connection requests, minimising the cost of the network in terms of deployment, energy consumption, and traffic forwarding costs. This study was further extended in [170] to include the minimisation of network resource fragmentation. Similarly, Wang et al. [171] proposed an ILP formulation to solve the VNF-placement and chaining problems in a SDN network. The proposal aims at 74 Chapter 4. NFV, SDN and MEC Authors Design Problem Optimisation Objective Bari et al. [166], [170] VNF-placement and chaining Heuristic to reduce the cost of network Wang et al. [171] VNF- placement, scheduling and chaining Framework JoraNFV, that reduces the network resource consumption, delay and costs Chi et al. [181] VNF-placement Heuristic which optimises the inter-server traffic and computation resource consumption Carpio et al. [174] VNF-placement Genetic algorithm which optimises the load balance in the network Bhamare et al. [176] VNF-placement Heuristic which reduces the latency due to VNF processing and inter-DC propagation Nguyen et al. [182] VNF-placement Heuristics which aim at minimising the cost of the network Marotta et al. [178] VNF-placement Heuristic to reduce the energy consumption and meet the SC latency requirements Cho et al. [179] VNF-placement Heuristic which minimises the network latency Khebbache et al. [183] VNF-chaining Genetic algorithm to minimise the active number of servers and the link resource utilisation Arouk et al. [180] VNF-placement and chaining Multi-Objective Placement algorithm that maximises: •the load balance •the virtualised BBUs or minimises the active NFV-enabled nodes Agarwal et al. [184] VNF-placement Heuristic which minimises latency Table 4.2: Heuristics for solving the VNF-placement and chaining problems in static scenarios. 4.1. NFV Overview 75 minimising the operational costs. Cziva et al. [186] proposed a method to dynamically solve the VNF-placement at the edge network considering the user demands, the network dynamicity, and the user mobility to achieve the latency-optimal location of the VNFs. This method acts in two stages: first, authors solve statically the optimal VNF-placement by means of an ILP formulation. Then, they apply a scheduler that triggers a re-evaluation of the VNF-placement, by choosing the optimal stopping time twhich, in this case, is the time in which the cumulative latency violations is the closest to the maximum latency violation tolerated by the system. In this manner, the scheduler reduces the number of times the re-evaluation is triggered and, in consequence, the migration costs generated when VNF must be migrated. In [187], Rankothge et al. proposed a set of ILP equations to solve two different aspects of the VNF-placement problem: the provisioning of new VNFs and the scaling of existing VNFs, in cloud environments. The set of ILP formulations aim at minimising the required resources in terms of active servers, the number of links and link utilization when creating new VNF instances and minimising the number of changes while guaranteeing that the requirements due to traffic changes are satisfied when scaling existing VNF instances. Authors Design Problem Technique Optimisation Objective Ghaznavi et al. [185] Elastic VNF- placement Mathematical Model Minimises the operational costs Cziva et al. [186] VNF- placement ILP + re-evaluation Minimises the migration costs Rankothge et al. [187] VNF- placement ILP Minimises the required resources in terms of servers, number of links and link optimisation Table 4.3: Mathematical formulations for solving the dynamic VNF-placement and chaining problems in dynamic scenarios. A summary of the proposals which implement mathematical formulations to solve the dynamic VNF-placement and chaining problems is shown in Table 4.3. Although mathematical models can be proposed to solve the dynamic VNF-placement and chaining problems, these are not the most adequate methods to employ in dynamic scenarios since the VNF-placement and chaining are NP-Hard problems [170] and, therefore, a mathematical model would not be able to solve the problem in polynomial time. For this reason, the most common approach to solve the problems is the proposal of heuristics and meta-heuristics. Ghaznavi et al. [185] proposed a heuristic for solving the elastic VNF-placement problem in DC-networks called Simple Lazy Facility Location. The heuristic aims at minimising the operational costs of the network. Upon a connection request, the algorithm assigns the traffic 76 Chapter 4. NFV, SDN and MEC to an existing VNF with minimum transport cost and, for each node of the network, calculates the migration and installation transport potential, i.e., the difference in the transport cost of the chosen VNF at the current node and the cost if the VNF migrates to another node or the cost of creating a new VNF in the node. Then, the algorithm computes the best migration and installation potentials and selects the best option, i.e., leaving the traffic to the assigned VNF, migrating to another node or creating a new instance of the VNF. When a connection is released, the algorithm optimises the VNF-placement by deciding if the VNF to which the demand was allocated should migrate to another node or removed from the network. The algorithm computes the difference in costs before and after migrating the VNF to another node and the cost before and after removing the VNF. Lastly, the algorithm selects the option which minimises the costs. In [182], Nguyen et al. complemented the proposed offline heuristics with an online heuristic to solve the VNF-placement and the routing problems, which aims at maximising the acceptance ratio. The heuristic computes the shortest path between origin and destination and then locates the VNFs at the nodes in the route one by one. Rankothge et al. complemented their ILP in [187] with a genetic algorithm which finds optimal or near-to-optimal solutions to the VNF-placement problem in cloud environments, reducing the required computing time. Authors assumed that a connection request may specify the required VNFs and the interconnectivity between them, which authors called policy. Therefore, the algorithm creates populations of individuals, in which individuals are full solutions to the VNF-placement problem. The full solutions are composed of partial solutions, which contain the servers considered to place the VNFs and the paths considered to route the traffic according to the different policies. Then, the algorithm computes the fitness of the solutions and creates a new population by applying crossover and mutation operations. In crossover, the algorithm randomly selects two individuals from the set and a partial solution. Then checks if the first partial solution can be applied to the second partial solution. If it can be applied, the solutions are interchanged. In the mutation operation, the algorithm either can change the placement of the VNFs or the paths. If the placement is change, the algorithm randomly selects a partial solution and tries to move all the VNFs to one, different server, and computes new paths. If the mutation operation changes the path, then it randomly selects a partial solution and a VNF and changes the path between the selected VNF and the following VNF in the chain. Beck et al. addressed the dynamic SC provisioning in [188] and proposed a heuristic to solve the problem with the objective of maximising the acceptance ratio. For each incoming SC request, the algorithm determines the set of VNFs that must be instantiated. Then, it randomly selects a node of the network for creating the first VNF, then selects the next VNF in the chain and tries to allocate it in a node with sufficient network and computing resources. The process is repeated until the SC is provisioned. If the algorithm is not able to allocate a VNF at one point, reverses the last decision and considers other allocation options. Zeng et al. complemented their static MILP formulation in [172] with a greedy algorithm to solve the VNF-placement problem in an inter-DC EON. The proposal jointly finds the location of the required VNFs and allocates the required spectrum resources and route to establish the SCs. Wang et al. studied the dynamic VNF-placement in DCs [189]. Authors proposed an online method which aims at minimising the operational and deployment costs. The method computes 4.1. NFV Overview 77 the total number of VNF instances required at a certain time slot to establish the SCs and serve the requested traffic. Then, authors proposed an algorithm which solves the initial placement of the computed number of VNF instances assuming that the served traffic is equal to the maximum flow which the system can support. Finally, authors proposed a heuristic to solve the final number and placement of the VNF instances. The algorithm employs the obtained initial VNF placement, decides whether the initial placement have enough instances to serve the SC or new ones must be created, and puts the instances which have not been employed to create the chain at idle state. Finally, the algorithm calculates the number of time slots in which the instances can remain idle before been removed from the system, as a function of the operational and deployment costs. The study is extended in [190] to consider traffic fluctuations and inter- DC bandwidth limitations, so that the authors slightly modified their method to only solve the required number of VNF instances at a certain time slot, and proposed an additional step which locates each VNF instance minimising the total congestion. López et al. [191] studied the impact on the number of accepted requests, latency and resource consumption of different VNF-placement and chaining heuristics. Authors proposed four heuristics based on greedy algorithms which search the placement which either introduces minimum latency between the source and destination nodes, maximises the resource usage, i.e., uses the hosts with larger available computing and network resources, minimises the overall delay by placing the VNFs at the most central nodes first or jointly optimises the latency and the resource consumption. Otokura et al. proposed in [192] a genetic algorithm-based method to dynamically solve the VNF-placement problem minimising the delay and the number of active CPU cores. The individuals, or solutions to the VNF-placement problem, contain the physical servers, the virtual machines created at each server and the VNF type and instance created at each VM. The algorithm computes the fitness of each individual and measures the behaviour in terms of delay and core utilisation, or in terms of the number of delay violations. Individuals are mutated to create new offspring and populations, but authors do not employ the crossover operation. Furthermore, authors proposed a method called Evolvable VNF Placement, which periodically changes the fitness objective of the genetic algorithm to enhance its performance and accelerate the evolution process. Authors consider two contributions to the delay: the propagation delay and the processing delay. The processing delay is modelled as a M/M/1 queue. There are proposals that focus on the VNF-placement and chaining problems in metro/core and access network, closer to the end-user, essential to meet the most stringent latency requirements, as Savi et al. shown in [8]. In this work, authors studied VNF-placement and chaining problems at the edge network and metro/core network, when latency-sensitive services are to be offered by a network operator. In this case, operators must choose between the “cheap” solution, which would be centralising all the VNFs in a DC, at the risk of degrading the performance of the network in terms of latency constraints fulfilment, or placing the VNFs at the network edge or the metro/access network nodes, closer to the end-user. In this case, Central Offices and the nodes of the network would be the potential hosts of the VNF instances. Authors proposed a heuristic to solve the VNF-placement problem in an edge network with latency-sensitive SCs, considering the physical topology, the bandwidth of the links and the capacity of the nodes. In the proposal, the SCs firstly try to employ existing VNFs in the network or create new ones in active NFV nodes if the VNFs do not have enough available capacity. If the established SC does not meet the delay requirements, the resources are released 78 Chapter 4. NFV, SDN and MEC and VNFs are placed in inactive NFV nodes, i.e., nodes which have not hosted VNFs before, on the shortest latency path. The result provides the position of the VNF instances so that the SC is established, the latency requirements are met, and the capacity constraints are fulfilled, and showed that for those services with restrictive latency requirements, VNFs should be located closer to the end-user. In [193], Askari et al. proposed an algorithm for dynamic VNF-orchestration in metro networks, which adjusts the location of the VNFs to the network state to ensure that the latency threshold of the different SCs are met. Authors consider the propagation delay, the O/E/O conversion, the Forward Error Correction (FEC) and the context switching delay as the main contributors for the overall latency. The algorithm first tries to use active VNFs in the network. If it does not find active VNFs with enough computational resources, it tries to allocate them in the nodes conforming the shortest path between source and destination. Finally, once the VNFs are placed, the algorithm checks if the latency requirements are met. If not, the algorithm tries to minimise the delay by calculating the longest virtual link delay and placing the VNFs hosted at the end points of that link at the adjacent virtual nodes. Lastly, Pedreno-Manresa et al. introduced a VNF-placement and chaining problem-solving algorithm in [9], [10], which considers rapid time-varying traffic, Quality of Service (QoS) and Quality of Experience (QoE) expectations in 5G-access scenarios. The authors presented a heuristic that dynamically places the SC, ensuring that the computing resources and the network bandwidth requirements are met, while minimising the blocking probability. Their heuristic aims at utilising available VNF instances located at the local node to which the requesting user is connected or creating new ones if there are enough computational resources. If it is not possible, but there are enough network resources to connect to the Central Office, the algorithm aims at employing existing VNFs or creating new ones at this node. If the operation fails due to lack of network or computing resources, the connection is blocked. Table 4.4: Heuristics and meta-heuristics for solving the VNF-placement and chaining problems in dynamic scenarios. Authors Design Problem Technique Optimisation Objective Ghaznavi et al. [185] VNF- placement Simple Lazy Facility Location heuristic Minimises the operational costs Nguyen et al. [182] VNF- placement and routing Shortest Path + VNF-placement at nodes of the path Maximises the acceptance ratio Continued on next page 4.1. NFV Overview 79 Table 4.4 – Continued from previous page Authors Design Problem Technique Optimisation Objective Rankothge et al. [187] VNF- placement Genetic Algorithm Minimises the required resources in terms of servers, number of links and link optimisation Beck et al. [188] VNF- placement and chaining Backtracking algorithm Maximises the established connections Zeng et al. [172] VNF- placement Greedy algorithm Minimises the overall cost of the network Wang et al. [189], [190] VNF- placement Bin-packing (pre-planning) +heuristic for single SC placement Minimise the provisioning cost López et al. [191] VNF- placement and chaining Greedy algorithm Four objectives: •Minimises introduced latency •Maximises resource usage •Minimises overall delay •Optimises latency and resource consumption Otokura et al. [192] VNF- placement Genetic Algorithm Minimises the delay and the active CPU cores Savi et al. [8] VNF- placement and chaining Heuristic Meet the latency and the capacity constraints Askari et al. [193] VNF- placement and chaining Heuristic Meet the latency constraints Continued on next page 80 Chapter 4. NFV, SDN and MEC Table 4.4 – Continued from previous page Authors Design Problem Technique Optimisation Objective Pedreno-Manresa et al. [9], [10] VNF- placement and chaining Heuristic Guarantee and acceptable Quality of Service and Experience The proposals that implement heuristics and meta-heuristics to solve the VNF-placement and chaining in dynamic scenarios are summarised in Table 4.4. We have seen the importance of the VNF-placement and chaining and the interest that these problems have raised in the scientific community. The problems can be solved in static and dynamic scenarios, and several efforts have been presented which aim the problems separately or jointly, using mathematical formulations as ILP or MILP, or heuristic approaches which try to find a solution in less computational time that the optimal mathematical formulations. In the next subsection we will introduce another important issue that affects NFV-environments: the survivability of VNFs. 4.1.2.3 Survivability in NFV The VNF-placement and chaining problems are key design stages to establish a service connection optimising the network and computing resources and, therefore, the acceptance ratio and the operational and capital costs of the networks. Furthermore, it is important to provide mechanisms which protect the established connections from a potential failure. If a node, a VNF or a link in the network fails, the SCs traversing those nodes or links or employing the failing VNF will be disrupted, which may affect thousands of end-users and cause the loss of important amounts of data. Fault-management techniques can be classified according to the element to which they provide protection. This can be the Service Chain, the individual VNFs or the path of the SC. If the SC is to be protected, then a backup SC is found, i.e., backup VNFs and network resources. In case of a failure, the traffic is rerouted through the backup SC, hence this kind of scheme provides end-to-end SC protection. Figure 4.2 shows an example of this kind of protection schemes. We can see that network resources are allocated between primary VNFs (blue arrows) and between backup VNFs (red arrows) if they are placed at different nodes. However, there are no network resources reserved to connect primary to backup VNFs and vice versa. Hence, if a node hosting a primary VNF fails, the traffic necessarily has to traverse the entire backup SC. On the other hand, VNFs can be protected individually, searching backup resources for each primary VNF. In case of failure, the SC employs the backup VNF which protects the failing primary one, but then returns to the working VNFs. Therefore, also network resources to connect the primary VNFs and the backup VNFs must be provided. An example of an individual VNF protection scheme for a primary SC composed of four VNFs can be seen in Figure 4.3. As shown in the figure, if node A fails, the traffic traverses the backup VNF1located at Node B, and then goes to the primary VNF2using the virtual link established between backup VNF1and primary VNF2. If node B fails, then the traffic traverses the primary VNF1, travels 4.1. NFV Overview 81 Figure 4.2: End-to-end SC protection scheme for a SC with four primary VNFs. to the backup VNF2, using the corresponding virtual link, then traverse the backup VNF3and travels to the primary VNF4. Finally, if node C fails, the traffic travels from primary VNF3to the backup VNF4and arrives at the end point of the SC, using the corresponding virtual links. Finally, network resilience may be the focus at the moment of providing protection to SCs. If that is the case, we can employ the link/path protection schemes developed for network protection, as shown in sections 2.1.1.4 and 2.2.4. There are several studies in the literature that address the SC protection approach. Hmaity et al. proposed in [194] three ILP formulations to provide end-to-end SC protection. Each of these formulations implements one of the following protection schemes: •Path Protection: In this case, the path of the backup SC must be link-disjoint with respect to the working path. However, the backup VNFs do not need to be in different nodes from the working VNFs. Furthermore, if no VNF protection is offered, the backup SC can employ the same VNF instances as the primary SC. •Node Protection: In this case, the backup SC employs VNF instances located at different nodes with respect to the primary SC, i.e., the working and backup SC are node-disjoint. •Path and Node Protection: Primary and backup SCs share neither VNF resources nor network resources, so they are link and node-disjoint. Ye et al. proposed a method for SC embedding [195] in an inter-DC network, that aims at minimising the network resource consumption. The algorithm builds a decision tree containing the VNFs which can be combined, i.e., which can be hosted at the same cloud, and their neighbours, sorted in decreasing cost, or bandwidth consumption. In this manner, the algorithm solves first the location of the VNFs which consume more bandwidth, and then collocates the less bandwidth consuming VNFs. This algorithm is further enhanced to provide end-to-end SC protection, introducing the dedicated and shared schemes. In dedicated protection, a backup 82 Chapter 4. NFV, SDN and MEC Figure 4.3: Individual VNF protection scheme for a SC with four primary VNFs. SC protects only one working SC. Their proposal provisions initially a primary SC and creates a new virtual topology eliminating the nodes and links allocated to the primary SC and the computing and network resources allocated to other existing working and backup SCs. Then, the proposed algorithm is executed to find a backup SC. In shared protection, backup resources can be shared between the services whose primary SCs are totally node and path-disjoint. Therefore, the scheme implementations are similar to the dedicated approach but only backup resources, either computational or network ones, are removed from the new virtual topology if they protect SCs employing the same VNFs or routed through common physical links. The individual VNF protection approach has also been covered in the literature. VNF protection can be shared when a backup VNF protects two primary VNFs located at different nodes, or dedicated, if a backup VNF protects only a primary VNF. Since not only computing resources but network resources to connect the primary and backup VNFs are required, the dedicated scheme requires great consumption of both kinds of resources. The shared scheme, on the other hand, is able to reduce the resource consumption, but may be insufficient to provide reliability in a multi-node or multi-VNF failure scenario. To address this problem, Fan et al. [196] proposed a heuristic for SC provisioning with VNF protection that aims at minimising the number of backup VNFs required to guarantee a certain network reliability degree, proposing a new protection scheme for multi-VNF failure, called Joint Protection. This scheme allocates enough computational resources to a backup VNF, so it is able to protect two primary VNFs if they fail at the same time. The algorithm computes the reliability of the network in terms of Mean Time Between Failures. Then, it selects the two less reliable primary VNFs, allocates them a backup VNF, and recomputes the total reliability of the network. The backup VNF is located at the node with higher available computing resources, and backup network resources are also provisioned. The algorithm repeats the process until achieving a certain reliability degree. Casazza et al. [197] proposed a greedy algorithm and a variable-neighbourhood search to solve the VNF-placement of the primary VNFs and protect them with a backup VNF. 4.2. Technologies related to NFV: SDN and MEC 83 The algorithms, however, do not perform VNF-chaining and, therefore, no network resources between primary VNFs or to connect them with the backup resources are reserved. Beck et al. enhanced their algorithm in [188] adding path and node protection. In the path protection scheme, at each primary VNF provisioning iteration, a link-disjoint backup path is also computed. In the node protection scheme, at each VNF provisioning iteration, a backup VNF is created in a different node and network resources are reserved to connect the previous primary VNF with the backup VNF and the previous backup VNF with the new backup VNF. Finally, some authors focus on the network resilience, proposing path protection schemes but not VNF protection schemes. Tomassilli et al. [198] proposed a link protection scheme for SC provisioning. Authors proposed an ILP and a decomposition model for shared and dedicated link protection which provisions an SC with their primary and backup, link-disjoint paths for each service request. Gao et al. [199] addressed the path protection issue by proposing an ILP formulation and a heuristic algorithm which solves the VNF-placement and chaining. In this case, multipath transmission is employed, so that the proposals calculate kpaths between the hosting data centres of the VNFs and reserve the required capacity. The reviewed proposals to address the survivability problem in NFV are shown in Table 4.5. 4.2 Technologies related to NFV: SDN and MEC We have just discussed the NFV paradigm, which will bring flexibility and manageability to the networks while, at the same time, reducing their cost. We have briefly introduced the NFV architecture and its main components, and we have focussed on the main design problems of this kind of environments: placement, chaining, and survivability. For this kind of networks to be implemented and develop their full potential, it is also necessary to introduce new network and computing technologies. In this subsection we will present two new technologies related to NFV: Software Defined Networking and Multi-access Edge Computing. 4.2.1 Software Defined Networking Current networks present severe management difficulties: firstly, they present a high heterogeneity, i.e., routers, switches, and other network devices are provided by different manufacturers and vendors. Moreover, networks also present difficulties in the device management since they must be handled individually, commonly with vendor-specific commands. Furthermore, network devices are vertically integrated: the controllers responsible for deciding how to manage the traffic and the physical parts forwarding the traffic packets are integrated into the same device [200]. Consequently, techniques to facilitate the network management and configuration must be proposed. SDN is a networking paradigm expected to facilitate the management and configuration and, consequently, the evolution of networks by decoupling the Data Plane and the Control Plane. In this manner, network devices composing the Data Plane would be mere Packet Forwarding Devices, while the Control Plane would be composed of centralized, softwarebased controllers, responsible for the management and configuration of the network devices. 90 Chapter 4. NFV, SDN and MEC Figure 4.7: Summary of the chapter. Chapter 5 Genetic Algorithm for Effective Service Mapping In Chapter 4, we introduced NFV, one of the key technologies that will bring the necessary architectural changes to adapt to the new demands and services. This paradigm deploys network functions as virtual appliances, instead of the traditional proprietary hardware. In this manner, network operators can easily deploy new network services by creating instances of the virtual network functions (VNFs) at commodity servers, increasing the flexibility and manageability of the network and reducing costs, since no proprietary, vendor-specific hardware must be purchased. In this kind of networks, service deployment is divided into two steps. The first one is to decide the number and location of the VNFs that must be instantiated over the network. This deployment step is known as VNF-placement. VNFs can be instantiated at Commercial-Off- The-Shelf (COTS) servers, located at data centres or the Central Office (CO) [7]. However, thanks to Multi-access Edge Computing, which provides computing and cloud capabilities to the edge nodes of the network, these nodes become a potential location for VNFs. In this manner, the data processing is pushed closer to the end-user and the latency is reduced [13]. In order to decide the location of the VNFs, parameters like the traffic patterns, energy efficiency, quality of service/experience (QoS/E), and the computing and network resource availability must be taken into account. The computing resource availability is of particular importance in 5G optical access network scenarios, in which VNFs can be located at the nodes of the network thanks to the MEC paradigm, hence reducing the latency, but whose computing capacities are low compared to the available resources present in data centres. Once the VNF-placement is solved, the operators must create the required service chains (SCs) associated with each offered service. An SC is a set of VNFs that must be traversed in a certain order. Therefore, operators must select the most suitable VNFs to create the SCs, according to the VNF availability, the network resource availability and performance parameters like QoS or latency. This deployment stage is known as the VNF-chaining problem. A service blocking occurs if there are not sufficient computing or networking resources to instantiate and connect the VNFs which compose the requested SC. Consequently, the network technology, the network topology, and the network resource availability will have a great impact on the VNF-placement and chaining, and they must be taken into account during the design of NFV environments in order to minimise the service blocking ratio while meeting 91 92 Chapter 5. Genetic Algorithm for Effective Service Mapping other 5G key performance parameters as the latency. In Chapter 4 we have introduced the VNF-placement and chaining problems and reviewed some of the available studies that address these design stages. The reviewed studies may address just one of the problems at the time or try to solve both problems jointly. The latter case is known as VNF-orchestration or VNF-mapping. These studies aim at reducing the computing and/or network resource consumption, reducing the number of active VNF-enabled nodes, minimising the energy consumption, meeting the latency requirements or minimising the service blocking ratio. In this chapter, we propose GASM (Genetic Algorithm for effective Service Mapping), a genetic algorithm that solves the VNF-placement and chaining problems in a 5G network with optical backhaul. We consider a network composed of 5G-nodes that are equipped with MEC resources and, in consequence, can host instances of VNFs. These nodes are connected to a CO by dedicated optical links, i.e., forming a star topology. The CO is also equipped with IT resources, hence enabled to host VNFs. The objective of GASM is minimising the service blocking ratio and the computing resource consumption, hence reducing the energy consumption and the operation expenses (OpEx). Moreover, our method considers limited available computing and network resources. The 5G-nodes can be traditional macro and micro-stations, but they can also implement the C-RAN technology, which divides the traditional Base Stations into two entities, the Remote Radio Heads, implementing basic Layer−1 functions, and Base Band Units (BBUs), which implement Layer−2 and Layer−3 operations. The advantage of BBUs is that they can be virtualised and hosted at different layers of the hierarchical aggregation network [215]. We will consider 5G-nodes implemented using C-RAN architecture. Therefore, 5G-nodes are composed of RRHs that are connected to an Access Central Office, which we call Access Office (AO). AOs are connected to the CO using point-to-point optical links, and both elements can host the virtualised Layer−2 and 3 functionality in the form of VNFs. We initially consider a static scenario in which the service connection requests are known in advance. However, the service requests vary with time in real scenarios and statically planning this kind of networks may cause an increase of the service blocking ratio, if the number of VNFs is under-provisioned, or make inefficient use of the IT resources, if more VNFs than the necessary are created. Therefore, we propose a modification of our algorithm in order to be applied to dynamic scenarios in which the reconfiguration of the planning is allowed. Furthermore, we enhance the modified algorithm to include a learning step, with the objective of improving the performance of the algorithm. We call these algorithms GASM with reconfiguration and Evolutive GASM, respectively. These algorithms consider the operational time to be divided into time slots, and they solve the VNF-placement problem offline at the beginning of each slot, whereas the VNF-chaining problem is solved online using modifications of techniques already proposed in the literature. The rest of the Chapter is structured as follows: In Section 5.1 we introduce the problem to be solved and the network scenario. Section 5.2 presents our proposal: GASM. In this section we describe the algorithm and compare its performance with other VNF-placement and chaining algorithms proposed in literature. In Section 5.3 we justify the necessity of allowing reconfigurations of the VNF-planning to properly design the VNF-placement and chaining in dynamic scenarios and present GASM with reconfiguration. This algorithm is further enhanced with a learning stage which improves its performance in terms of service blocking ratio. We 5.1. Problem Statement 93 Figure 5.1: 5G access optical network scenario where 5G-nodes are connected to a CO using point-to-point optical links. compare our proposals with the static planning with GASM and with online VNF-placement and chaining algorithms proposed in literature. Finally, we present some conclusions in Section 5.4. 5.1 Problem Statement We aim at addressing the VNF-placement and chaining problems in a 5G network with optical star topology backhaul, with the objective of minimising the service blocking ratio and the computing resource consumption, considering limited IT and network resources. We assume that the 5G network is composed of 5G-nodes implementing the C-RAN architecture. Therefore, the nodes are composed of a number of RRHs connected to an AO, which, at the same time, is connected to a CO through dedicated optical links. An example of the architecture is shown in 5.1. Some 5G nodes attend a higher number of average users, therefore we call them High- Demand 5G-nodes (HD-5G-nodes). The nodes which attend a lower number of users are called Low-Demand 5G-nodes (LD-5G-nodes). The 5G-nodes are connected to a Central Office (CO) with a dedicated optical link, composing a star topology network. We assume that the nodes are equipped with MEC servers, hence they are supplied with computing and cloud capabilities, and C-RAN functionalities. HD-5G-nodes have more computing resources than LD-5G-nodes since they attend a higher number of average users. Furthermore, the CO is also equipped with computing resources. In this manner, the nodes of the network and the CO can host VNFs, however, their computing resources will be limited, compared to the available computing resources offered by data centres. 94 Chapter 5. Genetic Algorithm for Effective Service Mapping In this scenario, the nodes of the network receive service requests from their connected endusers. The total service requests that should be attended are known before the algorithm starts its operation, hence the algorithm works in a static scenario. The services have an associated SC composed of a set of VNFs which must be traversed in a certain order. In order to establish each requested connection, it is necessary to compute the number of instances of each VNF that must be created to serve them considering two factors: the computing resources with which each node of the network is equipped and the available network resources. GASM solves the VNF-placement and chaining problem trying to minimise the service blocking ratio and the computing resource consumption, which implies less energy consumption and a reduction of network costs. Our method considers, furthermore, the limited available computing resources and the availability of network resources. 5.2 A Genetic Algorithm to Solve the Service Mapping Problem In this section, we present a method to solve the VNF-mapping problem called Genetic Algorithm for Effective Service Mapping (GASM) [3]. Contrary to other proposals, which study the service mapping problem in inter-DC networks or generic core/metro networks, our proposal solves the VNF-placement and chaining problem in a 5G network with optical backhaul, to place the VNFs closer to the end-user and meet the 5G latency requirements. Furthermore, this kind of scenario presents a disadvantage in terms of available resources, since nodes are equipped with MEC capabilities, but the IT resources are limited compared to the IT resources offered in data centres. Furthermore, our algorithm aims at minimising the service blocking ratio and the computing resources usage, in contrast to other proposals in the literature focused on the VNF-placement and chaining in the access network optimising only one objective design. 5.2.1 Algorithm Overview We propose a genetic algorithm to solve the VNF-placement and chaining problem in a 5G- network with point-to-point optical backhaul. Genetic algorithms are based on the mechanics of natural selection and evolution [216], and they are able to find close-to-optimal solutions to complex problems in reduced computational times. In consequence, they are commonly applied to solve search and optimization problems. Since the VNF-placement and chaining problems are NP-hard, a mathematical formulation cannot solve the problem in polynomial time. We avoid this problem by proposing a genetic algorithm. 5.2.1.1 Individuals and chromosome structure In genetic algorithms, each solution in the space of all potential solutions, or search space, is called individual [216]. In GASM, an individual represents the potential solution to the VNF- placement problem. Individuals are described by their chromosomes, and a chromosome is composed of genes. In our proposal, a gene encodes the number of instances of a certain VNF which a given node must host. Figure 5.2 shows an example of a chromosome in GASM. Our proposal works with n different VNFs, and we consider network composed of mnodes, m−1 5G-nodes plus a CO. Therefore, the first gene of the chromosome represents the number of instances of VNF1that 5.2. A Genetic Algorithm to Solve the Service Mapping Problem 95 Figure 5.2: Representation of a chromosome. node1must host. In the figure, it corresponds to 4 instances which must be hosted at HD-5G- node1. The second gene, therefore, represents the number of instances of VNF2that node1 should host. Therefore, genenrepresents the number of instances of VNFnto be hosted at node1. If we follow the sequence, the gene n+1 represents the instances of VNF1that must be created at node2. In consequence the gene ((m−1) ·n+i)) represents the instances of VNFito be hosted by nodem. 5.2.1.2 Initial parent population construction Our proposal is based on the classical genetic loop [216]. GASM creates an initial parent population composed of randomly generated individuals and two ad-hoc individuals. The mission of ad-hoc individuals is to enhance the performance of our proposal and speed up the process. We create these two individuals using VNF-placement and chaining heuristics proposed in the literature. We call the first ad-hoc individual "MEC-First" and it is based on the proposal by Pedreno-Manresa et al. [9], [10]. This heuristic starts the placement and chaining process at the local node to which the requesting user is connected. The algorithm tries to employ an existing VNF with available enough capacity. If it is not able to find an available VNF, it tries to create a new instance employing the remaining computing resources of the node. If the node cannot host more VNF instances and there are enough network resources between the node and the CO, the algorithm tries to repeat the same process at the CO, i.e., employs an existing VNF or tries to create a new one. Once in the CO, the algorithm is not able to search neither back at the local node nor at other nodes of the network. If the algorithm is capable of chaining the required VNFs and allocate network resources, the connection is established, otherwise is blocked. We proposed a second method inspired by the MEC-First heuristic, called CO-First [3], [4]. The main difference is that the chaining process starts at the CO. Therefore, the algorithm tries to employ existing VNF instances or to create new VNF instances at the CO first. If the algorithm is not able to continue the chaining process at the CO due to lack of resources, but there is enough available bandwidth, the algorithm continues the searching process at the local node. The idea behind this method is to reduce the number of active VNFs and, in consequence, the energy consumption. 5.2.1.3 Genetic evolution When the initial parent population is completed, the individuals undergo two classical genetic operations, i.e., crossover and mutation, with the objective of constructing a descendant population composed of newly generated individuals, until achieving a certain descendant 96 Chapter 5. Genetic Algorithm for Effective Service Mapping population size. In crossover, the algorithm randomly selects two individuals from the parent population and a crossover point. The algorithm then interchanges the second part of the chromosomes. The crossover pseudocode is shown in algorithm 5. Algorithm 5 Crossover 1: procedure crossover(parentPopulation) 2: parentA,parentB ←selectDifferentParents(parentPopulation) 3: randomPoint ←random(0,size(parentA) 4: newIndividual[0,randomPoint −1] ←parentA[0,randomPoint −1] 5: newIndividual[randomPoint −1,size(parentB)−1] ← parentB[randomPoint,size(parentB)−1] 6: return newIndividual The resulting individuals or offspring undergo then a mutation operation. In mutation, the algorithm randomly mutates each gene of the chromosome with a mutationProbability, which is user-defined. If the algorithm decides that a gene must be mutated, the new value of the gene is randomly generated, and the algorithm uses a uniform distribution between 0 and the maximum possible value for the gene, which is user-defined. The pseudocode for the mutation operation can be seen in algorithm 6. Algorithm 6 Mutation 1: procedure mutation(individual,maxVNFperLocation,mutationProbability) 2: gene ←0 3: while gene <size(individual)do 4: if random(0,1) <mutationProbability then 5: individual[gene]←random(0,maxVNF perLocation) 6: gene ←gene +1 7: return individual Once the individuals have undergone crossover and mutation, the algorithm verifies if the instances of the VNFs can be created at their corresponding hosting nodes of the network, as described by the chromosome. If the instantiation is possible, the individual is marked as valid, otherwise, it is discarded and a new individual is created with the crossover and mutation operations until the descendant population is completed. Valid individuals then go through the translation stage. During the translation stage, the algorithm creates the VNF instances indicated by the chromosome of the individual at their corresponding locations. Then, the algorithm sorts the service connection requests according to a certain priority order to be determined by the network operator. Next, the algorithm tries to establish the SC associated with each request. Therefore, the algorithm checks which VNFs must be concatenated in order to establish the connection, and begins the chaining process using a variation of the MEC-First policy proposed in [9], [10]. Employing the modified MEC- First policy, the algorithm looks for the corresponding VNF instances at the local 5G-node to which the user is connected. If the created instances do not have enough processing capacity to deal with the traffic of the request, the algorithm does not try to create new instances at the local node. Instead, it tries to concatenate instances located at the CO if they have available processing capacity and there are enough available network resources to connect the local 5G- 5.2. A Genetic Algorithm to Solve the Service Mapping Problem 97 node and the CO. Once at the CO, the algorithm does not look for available instances of other VNF in the chain back at the local 5G-node or in other 5G-nodes. If the algorithm is not able to set up the SC either due to lack of VNFs with enough processing capacity or due to lack of network resources, the request is blocked. 5.2.1.4 Fitness calculation and individual selection When the translation process is completed, the algorithm computes the fitness of the individuals. Fitness is measured in terms of service blocking ratio and percentage of active CPU cores in the network. Once the algorithm has computed the fitness of the individuals, it chooses the best ones among the parent and the descendant populations to be the parents of the next one. To that aim, the algorithm selects the individuals with the best performance in terms of service blocking ratio. However, if two individuals are tied in this parameter, the algorithm chooses the individual with a lower percentage of active CPU cores. The algorithm will repeat the evolution process a number of times, or generations, which is user-defined. At the end of the procedure, GASM returns the best individual, or VNF- placement configuration, in terms of service blocking ratio and CPU consumption found until that moment. Algorithm 7 shows the pseudocode of our proposed algorithm GASM. 5.2.2 Simulation Study and Results We have developed a network simulator using the C++ based discrete event simulator OMNeT++ [159], with the objective to test the performance of GASM (see Appendix A). Our simulator implements a 5G network with optical backhaul composed of 10 HD-5G-nodes and 10 LD-5G-nodes connected to a CO through dedicated optical links. Each link is composed of two optical fibres whose capacity is set to 10 Gb/s each. Location Computational resources Central Office 100 CPU cores, 480 GB RAM and 27 TB HDD HD-5G-node 16 CPU cores, 64 GB RAM and 10 TB HDD LD-5G-node 8 CPU cores, 32 GB RAM and 7 TB HDD Table 5.1: Hardware capabilities of the different 5G-nodes We assumed that all nodes are equipped with MEC resources, hence they have computing capability to host VNFs. Since the HD-5G-nodes attend in average more users than the LD- 5G-nodes, they are equipped with higher computing resources with respect to the LD-nodes. The CO also has IT resources and can host VNFs. The computing capabilities associated with each kind of node are shown in Table 5.1 and are the same of [3], [4], [7], [8], [9], [10]. We assumed that the network is managed by one network operator that offers three classes of network services: Voice over IP (VoIP), video streaming and web services. The users request one of those network services with a probability of 30%, 20% and 50% respectively, like in [9], 98 Chapter 5. Genetic Algorithm for Effective Service Mapping Algorithm 7 GASM 1: procedure GASM(tra f f icRequests,parentPopulationS ize,descendantPopulationS ize, numGenerations) 2: solution ← ∅ 3: parentPopulation ← ∅ 4: parentPopulation ←generatedAdHocIndividuals 5: while size(parentPopulation)<parentPopulationS ize do 6: parentPopulation ←checkFeasibility(generatedRandomIndividuals()) 7: i←0 8: while i<numGenerations do 9: descendantPopulation ← ∅ 10: checkPopulation ← ∅ 11: while size(descendantPopulation)<descendantPopulationS ize do 12: o f f spring ←crossover(parentPopulation) 13: o f f spring ←mutation(o f f spring) 14: descendantPopulation ← descendantPopulation∪checkFeasibility(o f f spring) 15: checkPopulation ←parentPopulation ∪descendantPopulation 16: checkPopulationFitness ← fitnessEvaluation(checkPopulation,tra f f icRequest) 17: checkPopulation,checkPopulationFitness ← selectFittestIndividuals(checkPopulation,checkPopulationFitness, size =parentPopulationS ize) 18: i←i+1 19: solution ←selectFittestIndividual(checkPopulation,checkPopulationFitness, size =1) 20: return solution 5.2. A Genetic Algorithm to Solve the Service Mapping Problem 99 Service Chained VNFs Bandwidth VoIP NAT-FW-TM-FW-NAT 64 kbps Video NAT-FW-TM-VOC-IDPS 4 Mbps Web Services NAT-FW-TM-WOC-IDPS 100 kbps Table 5.2: Requirements of the deployed service chains. NAT: Network Address Translator, FW: Firewall, TM: Traffic Monitor, WOC: WAN Optimization Controller, VOC: Video Optimization Controller and IDPS: Intrusion Detection Prevention System [3], [4], [7], [8], [9], [10]. [10]. Each service has an associated SC and bandwidth, which are shown in Table 5.2. The employed resources are the same as the resources in studies [7], [8]. Furthermore, each VNF has some associated computing resource requirements and a maximum number of concurrent users. This requirements are shown in Table 5.3, and are the same as the requirements presented in [9], [10]. We defined a parentPopulationS ize of 5 individuals, a descendantPopulationS ize of 10 individuals and a mutationProbability of 0.01. The chromosomes of the individuals were randomly created using a uniform distribution U(0,maxVNFperLocation), where maxVNF perLocation was fixed in 10 for the CO, 4 for the HD-5G-node and 2 for the LD- 5G-node. We have also defined the input parameter ¯u, which represents the average connected users per HD-5G-node. At the beginning of each simulation, the average users connected to each HD-5G-node was randomly generated using a uniform distribution: U[0,2·¯u].(5.1) The LD-5G-nodes attend on average 10% fewer users than HD-5G-nodes. In consequence, the number of connected users to each node of this class was randomly generated, at the beginning of each simulation, employing a uniform distribution: U"0,2·¯u 10 #.(5.2) We performed simulations for values of ¯ubetween 500 and 8,500, with increments of 1,000 average users. For each scenario, GASM stopping criterion was set to 100 generation and 100 simulations with different traffic requests were performed. Results are plotted in average, with 95% confidence intervals. Other configurations have been tested, being the presented in this Thesis the configuration which offered the best performance. Figure 5.3 shows a comparison of the service blocking ratio (SBR) achieved by MEC- First, CO-First and GASM. Results show that our proposal is able to achieve the same service blocking ratio than MEC-First, and improves the results obtained by CO-First. Furthermore, MEC-First and GASM are able to attend all the connection requests when ¯u<6500. However, if we observe the CPU consumption shown in Figure 5.4, we can see that GASM is able to obtain the same service blocking ratio than MEC-First while employing less active CPU cores. 106 Chapter 5. Genetic Algorithm for Effective Service Mapping Algorithm 9 Evolutive GASM [4] 1: procedure EvoGASM(tra f f icEstimation,previousProvisioning, parentPopulationS ize,descendantPopulationS ize,numGenerations) 2: solution ← ∅ 3: parentPopulation ← ∅ 4: parentPopulation ←previousProvisioning 5: parentPopulation ←generatedAdHocIndividuals 6: while size(parentPopulation)<parentPopulationS ize do 7: parentPopulation ←checkFeasibility(generatedRandomIndividuals()) 8: i←0 9: while i<numGenerations do 10: descendantPopulation ← ∅ 11: checkPopulation ← ∅ 12: while size(descendantPopulation)<descendantPopulationS ize do 13: o f f spring ←crossover(parentPopulation) 14: o f f spring ←mutation(o f f spring) 15: descendantPopulation ← descendantPopulation∪checkFeasibility(o f f spring) 16: checkPopulation ←parentPopulation ∪descendantPopulation 17: checkPopulationFitness ← fitnessEvaluation(checkPopulation,tra f f icRequest) 18: parentPopulation ← selectFittestIndividuals(checkPopulation,checkPopulationFitness, size =parentPopulationS ize) 19: i←i+1 20: solution ←selectFittestIndividual(checkPopulation,checkPopulationFitness, size =1) 21: if solution ,currentlyEstablishedS olution then 22: establishVNF(solution) 5.3. GASM in Reconfiguration Scenarios 107 5.3.3 Simulation Scenario and Results We have analysed the performance of GASM in a dynamic scenario using the same simulation settings described in subsection 5.2.2. Therefore, we assume a 5G network with 10 HD-5G- nodes and 10 LD-5G-nodes connected to a CO through dedicated optical links. We assume that the 5G-nodes are equipped with MEC resources and, in consequence, they are VNF-enabled nodes. The CO is also equipped with computing resources and can host instances of different VNFs. We assume that the computing resources with which the different nodes are equipped are the same as in the static scenario, shown in Table 5.1. Like in the static scenario, we assume that the network is managed by one operator which offers VoIP, Video Streaming and Web searching services. Users connected to the network can request one of these services with 30,20 and 50% probability. The associated SCs and maximum number of concurrent users are shown in Table 5.2, whereas the hardware requirements of the VNFs are shown in Table 5.3. The main difference between the simulation scenario with respect to the static simulation scenario is the traffic. Static traffic scenarios cannot be considered realistic since the transported traffic by a real network experiences variations with time. Therefore, we consider a dynamic scenario in which the number of connected users to the 5G-nodes varies with time according to the following equation [217]: usersi(t)=usersiβ(t)"1+φsin 2·π·t tvariation !#,(5.5) where usersirepresents the connected users to node i, while usersirepresents the average number of connected users at the 5G-node i.β(t) is a variable employed to introduce burstiness to the traffic and is randomly generated using a uniform distribution U[1−, 1+]every time that usersi(t) is evaluated, where represents the level of traffic burstiness and is set to 10% (i.e. 0.1) in our simulation study. φrepresents the traffic variability and can take the values 0.25,0.5 and 0.75. and tvariation represents the variation period in seconds. In our study, we set tvariation =86,400 s, i.e., one day. The variable usersiis randomly generated at the beginning of each simulation using the same parameter ¯uas in the static scenario, which represented the number of average users connected to the HD-5G-node. Therefore, usersifor the HD-5G-node is randomly generated using the uniform distribution: U[0,2·¯u],(5.6) while in the case of the LD-5G-nodes, which will attend in average ten times fewer users than the HD-5G-nodes, this parameter is randomly generated using the following uniform distribution: U"0,2·¯u 10 #.(5.7) ¯utakes values from 500 to 8,500 users with increments of 1,000 users. We repeat the simulation for each value of ¯u300 times with different traffics. At the beginning of each simulation, the network is planned for peak loads, and only in the reconfiguration scenario this planning is modified at the beginning of each time slot. We defined a simulation time of three days. We defined a parentPopulationS ize of 5 individuals, a descendantPopulationS ize of 10 108 Chapter 5. Genetic Algorithm for Effective Service Mapping Figure 5.7: Service blocking ratio achieved for peak load plannification with GASM for different values of kand φ=0.5 individuals, and create 100 generations at the peak load planning stage, and 10 generations at the re-planning stage. The figures are plotted with 95% confidence interval. 5.3.3.1 Results of Static Configuration in Dynamic Scenarios In this dynamic scenario, we have evaluated the performance of GASM (Algorithm 8) to statically plan the network, considering that the traffic is always equal to the peak value. The traffic peaks were estimated as described in section 5.3.1. We used the scaling factor kwith values 1,1.5 and 2. The planning is performed only at the beginning of each simulation and it remains unmodified throughout the three-day simulation. Figure 5.7 shows the service blocking ratio for GASM when φ=0.5, while Figure 5.8 shows the percentage of active CPU cores. Figure 5.7 shows that the best results in terms of service blocking ratio are obtained when a scaling factor of k=1.5 is employed. When k=1, the number of connected users is under-estimated and the VNF configuration is not prepared to deal with the actual number of connected users. In consequence, the network presents a high value of service blocking ratio and makes this configuration infeasible to be used in a real network. On the other and, the number of users is over-estimated when k=2 is used. In consequence, an unnecessary increment of the active CPU cores appears, as Figure 5.8 shows, which does not translate into an improvement of the service blocking ratio compared to the one obtained when k=1.5. If we observe the consumption of RAM and HDD, shown in Figures, 5.9a and 5.9b respectively, the same conclusions can be extracted, i.e., under-estimating the number of connected users with a scaling factor of k=1 leads to low consumption of the computing resources (either CPU cores, RAM or HDD) but also to poor results in terms of service blocking ratio. Selecting a scaling factor of k=1.5 increases the computing resource consumption but also achieves the best results in terms of service blocking ratio. Finally, if 5.3. GASM in Reconfiguration Scenarios 109 Figure 5.8: Active CPU Cores (%) achieved for peak load plannification with GASM for different values of kand φ=0.5 k=2 the connected users are over-estimated, the computing resource consumption increases but the service blocking ratio is not improved. Let us see what happens with different values of traffic variation. The service blocking ratio obtained by GASM when k=1,1.5 and 2 and φ=0.25 is shown in Figure 5.10. When φ=0.25, the scaling factor that obtains the best behaviour in terms of service blocking ratio is k=1.5. When k=1 the network cannot deal with the actual connected users, increasing the service blocking ratio, and k=2 leads to an over-estimation of the connected users that does not translate into a better performance in terms of service blocking ratio compared to k=1. If we increase the traffic variation to φ=0.75, we obtain the service blocking ratio results shown in Figure 5.11. In this case, incrementing the traffic variation affects the performance of GASM when k=1.5 to the point of causing the blocking of service requests for low values of ¯u, as shown in Figure 5.11. In conclusion, it is important to carefully select the scaling factor if a static planning for peak loads is to be implemented, since the traffic variation may affect the performance of the network. Results show that under-dimensioning leads to a bad performance in terms of service blocking ratio if the traffic variation is low. Over-dimensioning can achieve better results in terms of service blocking ratio, at the cost of increasing the computing resource consumption. 5.3.3.2 Enabling Reconfiguration in Dynamic Scenarios In the previous subsection, we have seen the importance of selecting a good scaling factor to estimate the traffic when statically planning a network. In this subsection, we compare the results of statically solving the VNF-placement problem to the results obtained with our proposed algorithms GASM with reconfiguration and Evolutive GASM [4]. Furthermore, we also compare our results with the ones obtained when the VNF-placement and chaining are 110 Chapter 5. Genetic Algorithm for Effective Service Mapping (a) Active RAM (%) (b) Active HDD (%) Figure 5.9: RAM and HDD consumption (in (%)) for a peak-load planning with k=1,1.5 or 2 and φ=0.5. 5.3. GASM in Reconfiguration Scenarios 111 Figure 5.10: Service blocking ratio achieved when statically planning for peak loads using GASM with k=1,1.5 and 2 and φ=0.25. Figure 5.11: Service blocking ratio achieved for peak load plannification with GASM for different values of kand φ=0.75 112 Chapter 5. Genetic Algorithm for Effective Service Mapping Figure 5.12: Service blocking ratio for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.5 dynamically solved using the online methods MEC-First [9], [10] and CO-First. In order to perform reconfigurations, we assume that time is divided into time slots whose duration is 900s. This value was chosen since it offered the best results in terms of service blocking ratio and CPU core consumption. In order to test the reconfiguration algorithms, at the beginning of each simulation, the VNF-placement problem is solved for peak loads using GASM (Algorithm 8) with a value of k=2. GASM evolves for 100 generations. Then, at the beginning of each time slot, GASM with reconfiguration or Evolutive GASM (Algorithms 8, 9), perform a reconfiguration of the VNF-placement using the traffic estimation computed using Equation 5.4. In this case, we configure the algorithms to evolve only for 10 generations to reduce the computational time, which must be lower than the time slot duration. Figure 5.12 and 5.13 show the service blocking ratio and the CPU consumption obtained when planning with GASM for peak loads, allowing reconfiguration with GASM with reconfiguration and Evolutive GASM, and solving online the VNF-placement and chaining problems using MEC-First and CO-First when the traffic variation is set to φ=0.5. In this case, making a static planning causes a higher service blocking ratio than allowing a reconfiguration of the VNF-placement or online solving the service mapping with MEC-First. We can observe that GASM with k=2 is one of the most CPU core-consuming algorithms while presenting one of the highest service blocking ratios, which confirms that over-dimensioning can lead to bad network performance and inefficient resource consumption. Although the performance of the static planning can be improved selecting other values of k, like 1.5, other planning algorithms like GASM with reconfiguration are able to outperform the static planning. Evolutive GASM is able to outperform MEC-First and GASM with k=1.5 in terms of service blocking ratio in almost an order of magnitude, making a lower consumption of CPU cores. Moreover, Evolutive GASM improves the performance of GASM with reconfiguration in terms of service 5.3. GASM in Reconfiguration Scenarios 113 Figure 5.13: Active CPU cores (%) for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.5 blocking ratio in almost two orders of magnitude. Furthermore, when compared to basic GASM when reconfiguration is allowed, the service blocking ratio is reduced in almost two orders of magnitude, proving the effectiveness of adding a learning stage to improve the behaviour of the algorithm. Evolutive GASM also makes a more effective use of the CPU cores, reducing the usage compared to GASM with reconfiguration and MEC-First almost a 10%. The same behaviour can be seen in the consumption of RAM and HDD, which are shown in Figures 5.14a and 5.14b respectively. Evolutive GASM outperforms MEC-First and GASM with reconfiguration making a lower use of the RAM and HDD up to 10% and 0.4% respectively. Figures 5.15 and 5.16 show the service blocking ratio and the active CPU cores for φ=0.25. For low traffic variations, unless a proper scaling factor is selected, planning with GASM for peak loads leads to a reduction of the network performance in terms of service blocking ratio, as Figure 5.15. GASM with reconfiguration outperforms GASM when k=1 and k=2. Furthermore, the learning stage of Evolutive GASM helps to improve the performance with respect to GASM with reconfiguration, although not as noticeably as in the case of φ=0.5. Both GASM with reconfiguration and Evolutive GASM outperform CO-First, but do not improve the performance of MEC-First in terms of service blocking ratio, since this algorithm adapts very well to low traffic variations. However, GASM with reconfiguration and Evolutive GASM obtain similar results to MEC-First for medium to high values of average users per HD-5G-node reducing the CPU consumption, as shown in Figure 5.16. Similar results are obtained in terms of RAM and HDD consumption. Finally, Figures 5.18 and 5.19 show the service blocking ratio and the percentage of active CPU cores when the traffic variation is set to φ=0.75. It can be observed, in Figure 5.18, that high traffic variations affect the performance of the network by increasing the service 114 Chapter 5. Genetic Algorithm for Effective Service Mapping (a) Active RAM (%) (b) Active HDD (%) Figure 5.14: RAM and HDD consumption (in (%)) for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.5. 5.3. GASM in Reconfiguration Scenarios 115 Figure 5.15: Service blocking ratio for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.25 Figure 5.16: Active CPU Cores (%) Figure 5.17: Service blocking ratio and CPU core consumption in (%) for the reconfiguration algorithms, the static algorithms and the online methods MEC-First and CO-First when φ=0.25. 122 Chapter 6. Joint Solution of VNF Mapping and Virtual Topology Design grooming. Later, we present a new version of GASM-VTD providing SC resilience against node failure. If a node fails, the SCs traversing that node may suffer a degradation of the Quality of Service (QoS) or even a disruption, which may affect thousands of end-users and cause the loss of large amounts of data. Hence, our proposal solves the individual VNF protection including the required connections (and allocated network resources) to ensure the transportation of traffic from the primary VNFs to the backup VNFs. We compare the performance of our proposals on different network scenarios, assuming limited and unlimited network resources. Furthermore, we compare our proposals with end-to-end SC protection strategies, which provide a complete backup SC to protect each working SC, based on proposals existing in the literature. Finally, we present GASVIT, a new algorithm that solves the VNF-placement and chaining problems and the virtual topology design implementing a new chaining technique. The algorithm makes more efficient placement of the VNFs compared to the previous proposals by better exploiting the collaboration between MEC nodes. Four versions of GASVIT to provide individual VNF protection are proposed. We compare the performance of GASVIT and GASVIT with protection with GASM-VTD and its version with protection. Furthermore, since GASVIT works with any type of topology, a techno-economic study is conducted to compare different network topologies in terms of service blocking ratio and network costs. The rest of this chapter is structured in the following manner: In Section 6.1, GASM-VTD is described and its performance in terms of service blocking ratio and computing resource consumption is presented. Section 6.2 presents the versions of GASM-VTD that integrate the different individual VNF-protection. Furthermore, protection schemes proposed in the literature [194] are presented and integrated into GASM-VTD, comparing the performance of the individual VNF protection and the end-to-end protection schemes. Section 6.3 presents GASVIT, the proposed versions of this algorithm that include protection techniques, the study of their performance compared to the performance of other methods. A techno-economic study that compares the behaviour of different network topologies in terms of service blocking ratio and network costs is also performed in this section. Finally, Section 6.4 concludes this chapter. 6.1 Genetic Algorithm for Service Mapping with Virtual Topology Design In Chapter 5, we introduced GASM [3], [4], a genetic algorithm for effective service mapping which solves the VNF-placement and chaining problem in 5G networks with optical backhaul. The network was constructed over a star topology and its nodes were equipped with MEC server, thus being able to host VNFs. However, GASM is only able to use VNFs hosted at the local node at which the end-user is connected or the CO since any communication between MEC nodes implies traversing the CO, therefore consuming high bandwidth, increasing the latency and making the CO more complex. Consequently, GASM was not able to fully exploit the MEC capabilities of the 5G-nodes. On the other hand, GASM was initially designed to solve the service mapping problem in 5G networks. However, 5G-nodes can be part of metro/core networks as in [215], [193]. Hence, it is necessary to adapt GASM to be able to solve the VNF-placement and chaining in other network topologies. 6.1. Genetic Algorithm for Service Mapping with Virtual Topology Design 123 In this section, we present a version of GASM which is able to address these two aspects of the algorithm, called Genetic Algorithm for effective Service Mapping with Virtual Topology Design and embedding (GASM-VTD) [5]. Our proposal works with WDM networks that connect the 5G-nodes and a CO deploying different topologies. Therefore, a virtual link between two nodes of the network hosting two consecutive VNFs in an SC must be created to transport the traffic from one VNF to another. Since the nodes are connected through a WDM network, the algorithm establishes lightpaths, i.e., all-optical routes between the nodes, and electrically grooms the virtual links into the existing lightpaths, if they have enough available capacity, or creates new lightpaths otherwise, if there are sufficient network resources. Therefore, the algorithm: •solves the VNF-placement problem. •solves the VNF-chaining problem. •solves the virtual topology design, including: –the connectivity problem, i.e., decide which lightpaths must be established. –the routing and wavelength assignment (RWA) problem for each lightpath. –the routing of traffic through the established lightpaths performing traffic grooming. 6.1.1 Algorithm Structure As explained in Chapter 5, in genetic algorithms, each possible solution from the search space is an individual. Each individual is described by a chromosome, which in GASM-VTD represents the number of instances of a given VNFs that should be created at each hosting node of the network. The chromosome is analogous to the chromosome in GASM, and an example is shown in Figure 5.2. GASM-VTD creates an initial parent population composed of randomly generated individuals and two ad-hoc individuals, created using the MEC-First [9], [10] and CO-First [3], [4]. However, GASM-VTD does not take into account the bandwidth availability at the moment of deciding which VNF instances compose each SC. Once the parent population is created, the composing individuals undergo the same genetic evolution loop as in GASM. The crossover operation is described in Algorithm 5. The offspring undergoes then the mutation operation described in Algorithm 6. After that, the individual is validated, i.e., GASM-VTD checks if the number of instances of the VNFs can be created at the corresponding hosting 5G-nodes, as the chromosome indicates. If the instantiation is possible, because there are enough available computing resources, then the individual is valid. Otherwise, it is discarded and a new one is generated using the crossover and mutation operations, until achieving a certain descendant population size, which is user-defined. At this stage, the algorithm translates the chromosome and evaluates the fitness of the corresponding solution. For this process, GASM-VTD creates the instances of the VNFs according to the information of the chromosome. After that, the algorithm sorts the connection requests according to the operator’s priority order (e.g., VoIP, video and web) and decides which of the VNF instances should be concatenated, according to their capacity availability only, thus not considering the bandwidth availability. We propose two versions of GASMVTD, according to the chaining strategy: 124 Chapter 6. Joint Solution of VNF Mapping and Virtual Topology Design 1. GASM-VTD-No-Collaborative: This strategy only concatenates VNFs with available processing capacity located at the local 5G-node to which the requesting end-user is connected, and the CO. Once the strategy employs a VNF located at the CO, it does not search for available VNFs back at the local 5G-node. If the algorithm is not able to find an available VNF, the request is blocked. 2. GASM-VTD-Collaborative. This chaining strategy can use any VNF located at any node of the network. The strategy starts the chaining at the local node. If the algorithm is not able to find the corresponding VNF with enough capacity in that location, then tries to employ an available VNF located at the CO. If unable to concatenate a VNF, the algorithm continues the search starting with the nodes with larger computation capabilities and finishing with the nodes with fewer computation resources. If the algorithm is not able to set up an SC due to a lack of VNF instances with enough available capacity to process the associated traffic, the request is blocked. Once all the instances have been reserved for all the SCs required to establish the requested services, the algorithm starts with the virtual topology design process. If an SC contains two consecutive VNFs located at different nodes of the network, the algorithm creates a virtual link between them with enough capacity to transport the requested traffic. If there is an established lightpath between the hosting nodes with enough available capacity to create the virtual link required to transport the requested bandwidth, the algorithm grooms the traffic into this lightpath. If not, the algorithm tries to set up a new lightpath between the two nodes making use of the available network resources. GASM-VTD creates the lightpaths using the k−shortest paths and first fit strategies [62]. If the algorithm is not able to groom the virtual link into existing lightpaths and cannot establish new ones due to lack of network resources, the connection request is blocked and the reserved VNFs are released. Hence, at the end of this process a new virtual topology has been designed, solving the RWA problem to establish the required lightpaths and performing traffic grooming to transport the requested traffic over these lightpath. The fitness of the individual is evaluated considering three parameters: the service blocking ratio, the percentage of active CPU cores and the percentage of used wavelengths, in that order. Then, the algorithm selects the fittest individuals, among the parent and descendant populations, to build the parent population of the following generation and repeats the process for a number of generations which is determined by the user. During the selection of the fittest individuals, the algorithm can find two individuals with the same score in terms of service blocking ratio. In that case, the algorithm selects the individual with the lowest percentage of active CPU cores. If the individuals are also tied in this parameter, the algorithm selects the individual with the lowest percentage of used wavelengths. At the end of the process, the algorithm provides the best solution which is composed of the VNF-placement, the established SCs, and the virtual topology. 6.1.2 Simulation Scenario and Settings We tested the performance of GASM-VTD in a WDM-ring metro network conducting a simulation study using OMNeT++ [159] (see Apendix A). The objective is to compare the performance of GASM-VTD-Collaborative to the performance of GASM-VTD-No- Collaborative, GASM-VTD-Collaborative, MEC-First [9], [10], and CO-First [3], [4]. The 6.1. Genetic Algorithm for Service Mapping with Virtual Topology Design 125 Figure 6.1: WDM-ring topology scenario [5]. network is composed of 5 HD-5G-nodes, 5 LD-5G-nodes, and a CO, as shown in 6.1. As explained in Chapter 5, the 5G-nodes are equipped with MEC capabilities, while the CO is also equipped with IT resources. Consequently, both kinds of nodes are able to host VNFs. However, HD-5G-nodes attend ten times more users on average than the LD-5G-nodes and, in consequence, they are equipped with larger MEC capabilities. The IT capabilities associated with each kind of node are shown in Table 6.1 [9], [10]. The IT capabilities are the same as the employed in Table 5.1 and are repeated in this chapter for the reader’s convenience. We assumed that the nodes of the network are equipped with a set of transceivers and a reconfigurable optical add-drop modulator (ROADM). In this study, the network can employ 10 wavelengths at a 10 Gb/s rate. We assumed that the network is managed by a network operator which offers VoIP, video streaming and web services. Each user can request one of these services with a probability of 30%, 20% or 50% respectively. The associated SC and demanded bandwidth are shown in Table 6.2 [7], [8], [3], [4], [5]. These requirements are the same as the shown in Table 5.2, and are repeated in this chapter for the reader’s convenience. Location Computational resources Central Office 100 CPU cores, 480 GB RAM and 27 TB HDD HD-5G-Node 16 CPU cores, 64 GB RAM and 10 TB HDD LD-5G-Node 8 CPU cores, 32 GB RAM and 7 TB HDD Table 6.1: Hardware capabilities of the different 5G-nodes. The IT resources and throughput associated with each VNF are shown in Table 6.3. In this 126 Chapter 6. Joint Solution of VNF Mapping and Virtual Topology Design case, the figures have been updated with respect to the values presented in Table 5.3, and the throughput is used instead of the number of concurrent operations as the capacity measure of the VNF. Service Chained VNFs Bandwidth VoIP NAT-FW-TM-FW-NAT 64 kbps Video NAT-FW-TM-VOC-IDPS 4 Mbps Web Services NAT-FW-TM-WOC-IDPS 100 kbps Table 6.2: Requirements of the deployed service chains. NAT: Network Address Translator, FW: Firewall, TM: Traffic Monitor, WOC: WAN Optimization Controller, VOC: Video Optimization Controller and IDPS: Intrusion Detection Prevention System [7], [8], [9], [10], [3], [4]. Service HW requirements Throughput NAT CPU: 2 core, RAM: 4 GB, HDD: 16 GB 2 Gb/s [218] FW CPU: 2 cores, RAM: 4 GB, HDD: 16 GB 2 Gb/s [218] TM CPU: 1 core, RAM: 2 GB, HDD: 16 GB 1 Gb/s [219] VOC CPU: 2 cores, RAM: 4 GB, HDD: 2 GB 2 Gb/s* WOC CPU: 1 core, RAM: 2 GB, HDD: 40 GB 0.5 Gb/s [220] IDPS CPU: 1 cores, RAM: 2 GB, HDD: 8 GB 2 Gb/s [221] Table 6.3: Hardware requirements associated with the VNFs [5]. *We assume that FW also includes NAT function, therefore the HW requirements are the same. Requirements for VOC are derived from the requirements of the other VNFs. As we did in Chapter 5, we define the parameter ¯uwhich represents the number of average users connected to an HD-5G-node. At the beginning of each simulation, the number of connected users to each HD-5G-node is randomly calculated using the uniform distribution: U[0,2·¯u].(6.1) On the other hand, the LD-5G-nodes attend ten times fewer users on average than the HD- 5G-nodes. Therefore, in each simulation, the number of connected users to each LD-5G-node is randomly generated using the uniform distribution: U"0,2·¯u 10 #.(6.2) 6.1. Genetic Algorithm for Service Mapping with Virtual Topology Design 127 Figure 6.2: Service blocking ratio of GASM-VTD-Collaborative, GASM-VTD-No- Collaborative, MEC First, and CO-First in a WDM-ring 5G network [5]. The size of the parent population was set to 5 individuals, whereas the size of the descendant population was set to 10 individuals. The mutation probability was set to 0.02. We created 50 generations and repeated the simulation 900 times with different traffic demands. Results are shown on average, and are plotted with 95% confidence intervals. 6.1.3 Performance of GASM-VTD The performance of the algorithm in terms of service blocking ratio is shown in Figure 6.2, whilst the percentage of CPU consumption of the algorithm is shown in Figure 6.3. We can observe that GASM-VTD-No-Collaborative achieves the same results in terms of service blocking ratio than MEC-First while improving the CPU resource consumption, particularly for the lowest values of ¯u, as Figure 6.3 shows [5]. Nevertheless, GASM-VTD-Collaborative, which exploits the collaboration between the nodes of the network, is able to outperform all the strategies compared in this study. In particular, the algorithm is able to support an average of 1,000 users for the HD-5G-nodes and 100 users for the LD-5G-nodes more than GASM-VTD-No-Collaborative and MEC-First without causing service blockage. This algorithm presents a similar consumption of CPU core resources than GASM-VTD-No-Collaborative and MEC-First for low to medium values of ¯u. However, the algorithm obtains the highest consumption of CPU cores for the highest values of ¯u, as pictured in Figure 6.3 [5]. CO-First is the algorithm with the highest service blocking ratio and lowest IT resource consumption since it is not able to fully exploit the IT capabilities of the edge nodes. In conclusion, allowing the collaboration between MEC nodes of a WDM network to solve the VNF-placement and chaining reduces the service blocking ratio while optimizing the number of active CPU cores. 128 Chapter 6. Joint Solution of VNF Mapping and Virtual Topology Design Figure 6.3: Percentage of CPU core consumption of GASM-VTD-Collaborative, GASMVTD-No-Collaborative, MEC First and, CO-First in a WDM-ring 5G network [5]. 6.2 Fault-management techniques to guarantee survivability in NFV environments Results from the previous section have shown the importance of jointly solving the VNF- placement and chaining problems and the virtual topology design. Nevertheless, GASM-VTD does not address the survivability problem. If a VNF or a node fails, the SCs which concatenate the failing VNF or any VNF in the failing node will suffer QoS degradation or even a disruption. As a consequence, thousands of end-users can see their connection degraded or completely interrupted, and large amounts of data will be lost. Hence, we extended GASM-VTD to include protection techniques that guarantee the resilience of the SCs in a single-node failure scenario. As showed in Chapter 4, the faultmanagement techniques can be classified according to the protected element. We can find SC protection techniques which provide a complete backup SC to protect a primary SC. In case of failure of one of the elements of the primary SC, the associated traffic would traverse the backup SC. Hence, this kind of technique provides end-to-end SC protection, as Figure 4.2 shows. Contrarily, there are techniques proposed in the literature which only provide individual VNF protection. In this kind of strategy, a backup VNF is provided for each primary VNF. If the primary VNF fails, the traffic will traverse the corresponding backup VNF and then the next elements of the initial primary SC, as shown in Figure 4.3. On the other hand, the protection schemes can be dedicated or shared. In dedicated protection schemes, the backup element, which can be either a VNF or an SC, can protect only one primary element. Contrarily, in shared protection schemes the backup element can protect multiple primary elements. In the case of SC protection, a backup SC and its protected primary SCs cannot contain the same VNFs and the chains must be node-disjoint to avoid collision 6.2. Fault-management techniques to guarantee survivability in NFV environments 129 problems. In the case of individual VNF protection, a backup VNF cannot be employed as a primary VNFs, and can only protect multiple VNFs if they are node-disjoint between them and the backup VNF. We present a version of GASM-VTD enriched with individual VNF protection, which solves the survivable VNF-placement and chaining problems and the virtual topology design, including the reservation of VNFs and the virtual links necessary to build the backup SCs. We have studied the impact of using dedicated and shared protection schemes, and analysed their performance in terms of service blocking ratio and computing resource consumption. Lastly, the performance of the proposed algorithm with individual VNF protection is compared to the performance of the algorithm with end-to-end protection schemes proposed in the literature. 6.2.1 Individual VNF protection schemes When the individual VNF protection strategy is chosen, a backup VNF is assigned to each primary VNF employed in an SC. The primary VNF and its associated backup VNF must be hosted in different nodes of the network. Moreover, the corresponding virtual links between the primary VNFs and the backup VNFs must also be reserved to ensure that the traffic can traverse the backup VNF and be transported to the next primary VNF of the SC. We call these virtual links "backup virtual links". We showed an example of a primary SC with individual VNF protection in Figure 4.3, where the different cases in which a backup virtual link must be established were introduced. The protection can be delivered either allocating dedicated protection resources to the primary VNFs or allocating shared resources between multiple primary VNFs. Moreover, we can allocate dedicated network resources to the virtual links between the primary and backup VNFs, or share those resources. Accordingly, we propose five variations of GASM-VTD [6]: 1. GASM-VTD (NP): This version of GASM-VTD does not provide individual VNF protection, allocating neither backup VNFs nor backup network resources. This scenario is equivalent to execute GASM-VTD-Collaborative. 2. GASM-VTD (DV, DN): This method allocates a dedicated backup VNF to each primary VNF. A primary VNF cannot be eligible to protect another primary VNF concatenated in any primary SC. The method also allocates dedicated network resources to establish the virtual links between the primary and backup nodes. Therefore, these network resources are not utilised to establish virtual links between primary and backup VNFs in any other established SC. 3. GASM-VTD (DV, SN): As in the previous version, the method provides dedicated VNF protection, so each backup VNF will only protect one primary VNF. However, the method shares the network resources allocated to backup virtual links between multiple SCs. 4. GASM-VTD (SV, DN): This method provides shared VNF protection and, thus, can use one single backup VNF to protect multiple primary VNFs. The primary VNFs cannot share the same location in order to avoid collision problems if a node fails. Furthermore, the primary and backup VNFs must be node-disjoint. The network resources allocated to backup virtual links are dedicated in this strategy, therefore they cannot be used to connect primary and backup VNFs in other SCs. 130 Chapter 6. Joint Solution of VNF Mapping and Virtual Topology Design 5. GASM-VTD (SV, SN): This method shares either the backup VNFs and the network resources. 6.2.2 Integrating VNF protection into GASM-VTD We have proposed four variations of GASM-VTD that provide SC resilience by assigning backup VNFs to the designed primary VNFs and reserving network resources for the required backup virtual links. The chromosome of the individuals in GASM-VTD with protection is analogous to the chromosome in GASM-VTD. Therefore, each gene indicates the number of instances of a certain VNF which should be created at a certain host. The initial parent population in GASM-VTD with protection is composed of randomly generated individuals, which undergo the same crossover and mutation processes described in Chapter 5, Algorithms 5 and 6. The resulting offspring of each generation is validated checking if the required instances of each VNF can be created at every hosting node as the chromosome indicates. If the algorithm is unable to create the indicated instances due to lack of computing resources, the individual is discarded and a new one is created using the crossover and mutation operations. The process is repeated until achieving a user-defined population size. After the population of valid individuals is completed, the algorithm starts the translation process. For each individual in the population, the algorithm translates it, i.e., creates the indicated instances of the VNFs at their corresponding hosts, which are assumed to remain idle until the algorithm is able to chain them in an SC, or reserve them as a backup VNF. The algorithm sorts the incoming service requests according to a certain operator’s priority order. After that, the algorithm tries to serve each connection request by reserving first the VNFs to build the required primary SC and then the backup VNFs to protect the primary SC. The algorithm employs the GASM-VTD-Collaborative chaining policy introduced in Subsection 6.1.1. Hence, to construct the primary SC, it tries to chain VNFs with available capacity located at the local 5G-node. If no available instances of VNFs are found, the algorithm tries to find available VNF instances located at the CO. Again, if the algorithm is not able to find the required VNF at the CO, it searches at the 5G-nodes, starting with the nodes equipped with larger IT capabilities, and finishing with the nodes with fewer IT capabilities. If the algorithm cannot construct the SC, the service request is automatically blocked. Otherwise, the algorithm begins with the reservation of the backup VNFs. After the primary SC is completed, the algorithm searches for backup VNFs to protect the primary VNFs in this SC. The VNFs already in use in any constructed primary SC cannot be utilised to protect another primary VNFs. In the same manner, a backup VNF cannot be chained in a primary SC. Furthermore, the primary VNF and its backup VNF must be hosted by different nodes, in order to provide node failure protection. If the dedicated VNF protection scheme is employed, then each backup VNF protects only one primary VNF. However, if the shared protection scheme is implemented, a backup VNF can protect multiple primary VNFs, provided that the hosting nodes are totally disjoint, i.e., two or more primary VNFs cannot be located at the same node, to avoid collision problems. The search strategy employed to find backup VNFs is highly similar to GASM-VTD-Collaborative, since the algorithm searches available VNFs at the CO, then at the nodes with larger computing resources and finishing with the nodes with fewer IT capabilities, avoiding the node at which the VNF to be protected is located. If the algorithm is not able to find a backup VNF for each VNF in the primary SC, 6.2. Fault-management techniques to guarantee survivability in NFV environments 131 the connection is blocked. After constructing the primary SCs and allocating backup VNF resources the algorithm assigns network resources. If two consecutive VNFs of a primary SC are hosted by different nodes, the algorithm creates a virtual link between the nodes to connect them and establish the service connection. If a lightpath between the nodes exists, and it has enough available capacity to transport the associated traffic to the SC, then the algorithm uses it to establish the virtual link. Otherwise, the algorithm tries to establish a new lightpath between the two nodes, if there are sufficient available network resources. The algorithm uses the k−shortest paths and first fit policies to set up the required lightpaths. If the algorithm is able to assign the required network resources to the primary SC, it creates the required backup virtual links to connect the primary VNFs with their backup resources, and the consecutive backup VNFs hosted by different nodes which protect VNFs located at the same node. In this case, the lightpaths employed by the primary and backup VNFs are completely independent. Hence, a backup lightpath does not transport traffic associated with primary SCs. If the dedicated network resource scheme is employed, the connections between primary and backup VNFs and connections between backup VNFs are dedicated for each SC. Otherwise, these connections can be shared with other SCs. If the algorithm finds network resources for the primary and backup connections, it reserves the required bandwidth and establishes the connection. Otherwise, the service request is blocked. For each individual in the population, the algorithm computes its fitness. As in GASMVTD, the three selected fitness parameters are the service blocking ratio, the percentage of active CPU cores, and the percentage of used wavelengths. The algorithm selects the fittest individuals among the parent and the descendant populations to become the parents of the descendant population of the next generation. If two individuals obtain the same results in terms of service blocking ratio, the algorithm selects the one with better performance in terms of CPU core usage. If there is also a tie in this parameter, the individual with the lowest number of active wavelengths is selected. GASM-VTD with protection repeats the classical genetic loop for a number of user-defined generations. At the end of the process, the algorithm provides the best solution which is composed of the VNF-placement, the established SCs, their corresponding backup resources, and the designed virtual topology, including the primary and backup connections. 6.2.3 Simulation scenario and results We performed a simulation study to compare the performance of the four versions of GASM-VTD with protection over a 5G WDM-ring network using the developed simulator in OMNeT++ [159]. We utilised the same network scenario described in Subsection 6.1.2. We assumed that the CO is equipped with IT resources and the 5G-nodes with MEC servers. The IT capabilities with which the nodes are equipped are shown in Table 6.1 [9], [10]. As in previous studies, we assume three different kinds of network services: VoIP, video streaming and web services. The end-user can request one of the services with 30%, 20% and 50% probability, respectively. Each network service has an associated SC and bandwidth requirements, which are shown in Table 6.2 [7], [8], [3], [4], [5]. Finally, each VNF has the associated CPU core, RAM, hard disk requirements, and throughput shown in Table 6.3. We configured GASM-VTD with protection to create 50 generations, with an parent