Energy Efficient Traffic Engineering in Software Defined Networks Ingénierie de trafic pour des réseaux énergétiquement efficaces

As the traffic of wired networks continues to grow, their energy consumption becomes a serious efficiency and sustainability concern. This work seeks to improve the energy efficiency of backbone networks by automatically managing the paths of network flows to reduce the over-provisioning. Compared to numerous works in this field, we stand out by focusing on low computational complexity and smooth deployment of the proposed solution in the context of Software Defined Networks (SDN). To ensure that we meet these requirements, we validate the proposed solutions on a network testbed built for this purpose. Moreover, we believe that it is indispensable for the research community in computer science to improve the reproducibility of experiments. Thus, one can reproduce most of the results presented in this thesis by following a couple of simple steps.

In the first part of this thesis, we present a framework for putting links and line cards into sleep mode during off-peak periods and rapidly bringing them back on when more network capacity is needed. The solution, which we term "SegmenT Routing based Energy Efficient Traffic Engineering" (STREETE), was implemented using state-of-art dynamic graph algorithms. STREETE achieves execution times of tens of milliseconds on a 50-node network. The approach was also validated on a testbed using the ONOS SDN controller along with OpenFlow switches. We compared our algorithm against optimal solutions obtained via a Mixed Integer Linear Programming (MILP) model to demonstrate that it can effectively prevent network congestion, avoid turning-on unneeded links, and provide excellent energy-efficiency.

The second part of this thesis studies solutions for maximizing the utilization of existing components to extend the STREETE framework to workloads that are not very well handled by its original form. This includes the high network loads that cannot be routed through the network without a fine-grained management of the flows. In this part, we diverge from the shortest path routing, which is traditionally used in computer networks, and perform a particular load balancing of the network flows.

In the last part of this thesis, we combine STREETE with the proposed load balancing technique and evaluate the performance of this combination both regarding turned-off links and in its ability to keep the network out of congestion. After that, we use our network testbed to evaluate the impact of our solutions on the TCP flows and provide an intuition about the additional constraints that must be considered to avoid instabilities due to traffic oscillations between multiple paths.

iii Résumé La consommation d'énergie est devenue un facteur limitant pour le déploiement d'infrastructures distribuées à grande échelle. Ce travail a pour but d'améliorer l'efficacité énergétique des réseaux de coeur en éteignant un sous-ensemble de liens par une approche SDN (Software Defined Network). Nous nous différencions des nombreux travaux de ce domaine par une réactivité accrue aux variations des conditions réseaux. Cela a été rendu possible grâce à une complexité calculatoire réduite et une attention particulière au surcoût induit par les échanges de données. Pour valider les solutions proposées, nous les avons testées sur une plateforme spécialement construite à cet effet.

Dans la première partie de cette thèse, nous présentons l'architecture logicielle "Seg-menT Routing based Energy Efficient Traffic Engineering" (STREETE). Le coeur de la solution repose sur un re-routage dynamique du trafic en fonction de la charge du réseau dans le but d'éteindre certains liens peu utilisés. Cette solution utilise des algorithmes de graphes dynamiques pour réduire la complexité calculatoire et atteindre des temps de calcul de l'ordre des millisecondes sur un réseau de 50 noeuds. Nos solutions ont aussi été validées sur une plateforme de test comprenant le contrôleur SDN ONOS et des commutateurs OpenFlow. Nous comparons nos algorithmes aux solutions optimales obtenues grâce à des techniques de programmation linéaires en nombres entiers et montrons que le nombre de liens allumés peut être efficacement réduit pour diminuer la consommation électrique tout en évitant de surcharger le réseau.

Dans la deuxième partie de cette thèse, nous cherchons à améliorer la performance de STREETE dans le cas d'une forte charge, qui ne peut pas être écoulée par le réseau si des algorithmes de routages à plus courts chemins sont utilisés. Nous analysons des méthodes d'équilibrage de charge pour obtenir un placement presque optimal des flux dans le réseau.

Dans la dernière partie, nous évaluons la combinaison des deux techniques proposées précédemment : STREETE avec équilibrage de charge. Ensuite, nous utilisons notre plateforme de test pour analyser l'impact de re-routages fréquents sur les flux TCP. Cela nous permet de donner des indications sur des améliorations à prendre en compte afin d'éviter des instabilités causées par des basculements incontrôlés des flux réseau entre des chemins alternatifs.

Nous croyons à l'importance de fournir des résultats reproductibles à la communauté scientifique. Ainsi, une grande partie des résultats présentés dans cette thèse peuvent être facilement reproduits à l'aide des instructions et logiciels fournis.

Chapter 1 Introduction

Motivations

Advances in network and computing technologies have enabled a multitude of servicese.g. those used for big-data analysis, stream processing, video streaming, and Internet of Things (IoT) -hosted at multiple data centers often interconnected with high-speed optical networks. Many of these services follow business models such as cloud computing, which allow a customer to rent resources from a cloud and pay only for what she consumes. Although these models are flexible and benefit from economies of scale, the amount of data transferred over the network increases continuously. Network operators, under continuous pressure to differentiate and deliver quality of service, often tackle this challenge by expanding network capacity, hence always adding new equipment, or increasing the rates of existing links. Existing work argues that, if traffic continues to grow at the current pace, in less than 20 years network operators may reach an energy capacity crunch where the amount of electricity consumed by network infrastructure may become a bottleneck and further limit the Internet growth [START_REF] Kilper | Energy challenges in access and aggregation networks[END_REF].

Major organizations have attempted to curb the energy consumption of their infrastructure by reducing the number of required network resources and maximizing their utilization. Google, for instance, created custom Software Defined Network (SDN) devices and updated their applications to co-operate with the network devices. In this way, it was possible to achieve near-100% utilization of intra-domain links [START_REF] Jain | B4: Experience with a Globallydeployed Software Defined Wan[END_REF]. With this smart traffic orchestration, Google was able to increase the energy efficiency while providing a high quality of service. However, such traffic management requires co-operation between the communicating applications and the network management, a technique that is out-of-reach of ordinary network operators.

As the network operators do not have control over the applications that use the network, they over-provision the network capacity to handle the peak load. Furthermore, to prevent failures due to vendor-specific errors, it is not exceptional for a big network provider to implement vendor redundancy in its core network. Vendor redundancy consists of using devices from multiple vendors in parallel. The Orange France mobile network blackout in 2012 1 is an example of a vendor specific error where a software update introduced a bug both on the primary and on the backup device. To avoid these situations, Figure 1.1: Traffic passing through the 200Gbps link between Paris and Geneva. Geant Network [START_REF]Geant network looking glass and usage map[END_REF] some network operators double the capacity by using backup devices from multiple vendors. All these approaches contribute to highly over-provisioned networks. For example, evidence shows that the utilization of production 200Gbps links in the Geant network can be as low as 15% even during the periods of highest load (Fig. 1.1). Moreover, during the off-peak times during night and weekends, the network utilization is even lower. It drops to almost 5% of the link capacity.

As a result of all this over-provisioning, the energy efficiency of operator networks is low: devices are fully powered all the time while being used only at a fraction of their capacity. This over-provisioning leaves a lot of potential for innovation and for reducing the energy that a network consumes by switching off unused devices and optimizing their usage.

This work is done as part of the GreenTouch consortium, which intends to reduce the net energy consumption in communications networks by up to 98% by 2020 [START_REF]GreenTouch Final Results from Green Meter Research Study[END_REF].

Research problem and objectives

Large-scale computer networks are major electricity consumers whose consumption is not yet optimized. A backbone network device can consume as much as 10kW2 irrespective of its utilization. This thesis investigates means to improve the energy-efficiency of future backbone networks while retaining the performance constraints.

In particular, we target high-speed IP over Wavelength Division Multiplexing (IPoWDM) operator networks with extremely high data-rates, reaching several hundred gigabits per second per link in currently deployed systems. Unlike dedicated networks -such as those deployed in between data centers, enterprises or research institutes -the company that manages the network devices does not have control over the applications whose traffic traverses the network. Our main lever used to increase the energy efficiency of these networks is agnostic to the applications: we use "traffic engineering" techniques which consist in dynamically changing the paths of data flows transparently to the applications.

This thesis revolves around two ideas. The first natural idea consists in decreasing the energy consumption of the networks by reducing the number of resources that are active during off-peak periods. In particular, we intend to turn off transponders and port cards on the extremities of a link. The status of these components is set to sleep mode whenever a link is idle, and they are brought back to the operational state when required. We also term this process of activating and deactivating network links as switching links on and off respectively. To free certain resources, the network traffic is dynamically consolidated on a limited number of links, thus enabling the remaining links to enter the low power consumption modes. Respectively, when the network requires more capacity, the corresponding links are brought back online to avoid congestion. In other words, we transparently change the paths taken by the application data in the network to accommodate network capacity to the load.

The second idea relies on the observation that a well-utilized network does not consume resources in vein. A proper load balancing technique allows transferring more data with the same resources, avoiding premature updates to higher data rates and thus avoiding the increase of energy consumption due to this update. As detailed later, we conclude that both these methods are necessary and must be used in parallel to achieve a good energy efficiency of operator networks.

We position our work in the context of Software-Defined Network (SDN)-based backbone networks and work within a single operator network domain. Although different methods have already been proposed for reducing the energy consumption of communication networks, our contribution is an end-to-end validation of the proposed solutions. These solutions were both validated through simulations and implemented in a real network testbed comprising Software-Defined Network (SDN) switches and the Open Network Operating System (ONOS) SDN controller. Moreover, we also used the testbed to evaluate the impact of frequent path changes on data flows and conclude that such techniques can be used with minimal impact on application flows.

Contributions and structure of the manuscript

Chapter 1 introduced the motivation of this work: the continuous growth of the number of connected devices relying on the network to access remote services puts a significant load on operator backbone networks. Faster speeds and bigger devices have to be deployed, continuously increasing the energy consumption.

In the rest of this chapter, we detail how to reproduce most of the results presented in this thesis. This work was performed considering the growing concern of reproducibility of scientific work in computer science. We also reference the Android applications which we created to provide an interactive way to test our algorithms and visualize their results.

Chapter 2 sets the context of our work. We provide a general overview of the architectures of backbone networks and explore the panorama of methods used to reduce their energy consumption. Most of these methods propose structural modifications of the network. For example, this includes completely re-designing the physical topology, the network devices, or the applications using the network. In contrast, we follow a less intrusive approach that relies on traffic engineering; a mature technology widely deployed by operators for other goals, such as differentiated services.

CHAPTER 1. INTRODUCTION

We continue the chapter with an extended introduction to the existing traffic engineering techniques and, in particular, to the concept of Software-Defined Network (SDN). In parallel, we present the related work that uses traffic engineering for increasing the energy efficiency of networks. This introduction allows us to conclude that there is still a need for an online solution, capable of reacting fast to changes in network traffic and, in particular, to the unexpected growth of network demand.

The chapter ends with a discussion on the particularities that must be considered when designing a SDN-based solution for high-speed backbone networks. The presented challenges underlie the design of our solutions in the rest of this work. We also introduce the Source Packet Routing In NetworkinG (SPRING)/"Segment Routing" protocol, intended to meet the requirements of traffic engineering in backbone networks, and hence circumvent the challenges above.

Chapter 3 provides the theoretical background needed to understand the results from this thesis. We give an introduction to linear programming and the classical network flow problem known as "maximum concurrent flow". We illustrate the two usual ways to model this problem as a linear program, namely the "node-arc" and the "edge-path" formulations. The first model is used throughout the work to provide a comparison baseline for the quality of our algorithms. At the same time, the edge-path is at the base of efficient approximate algorithms for computing the maximum concurrent flow in a network.

The chapter ends with some mathematical properties of the edge-path formulation and its dual, which is used in the later chapters of the thesis.

Chapter 4 presents the design, implementation and evaluation of STREETE, a SDNbased framework meant to reduce the energy consumption of backbone networks by switching links off and on.

The main particularity of this work is the capacity to react very fast to changes in the network conditions and, in particular, to unexpected growth of network demand. This is achieved thanks by incorporating a technique that uses two different views of the network to feed the heuristic. Moreover, we use dynamic shortest path algorithms at the core of our solution to speed up the computations and the SPRING protocol to enable low-overhead management of the network by the SDN controller.

We validate the proposed solution in the OMNeT++/INET network simulator and conclude that it performs very well under low network load, but there is room for improvement at high load. This conclusion served as motivation for the work presented in Chapter 5 of this thesis, which tries to make STREETE perform well in any network conditions while being able to compute a solution on the evaluated backbone networks quickly.

This chapter also presents the SDN-based testbed built for validating the proposed solutions experimentally. This testbed allowed us to highlight an additional weakness of STREETE. These results motivated the study done in Chapter 6, which allows for improving our framework further.

Chapter 5 presents two load balancing methods proposed for the STREETE framework to enable better utilization of active network resources.

The first method provides a consistent improvement over the shortest path routing, but the output quality is not very stable and did not satisfy our expectations. We present the reasons behind this behavior and continue with the second, more elegant, load balancing method that is based on state of the art for approximately solving the maximum concurrent flow problem. It builds on the work done by George Karakostas [START_REF] Karakostas | Faster Approximation Schemes for Fractional Multicommodity Flow Problems[END_REF] to produce a complete solution for near-optimal Software-Defined Network (SDN)based online load balancing in backbone networks. This solution also leverages the power of SPRING source routing protocol to reduce the complexity and cost of centralized management.

Chapter 6 starts by unifying the results from the two previous chapters and evokes the problem that the combination of STREETE with load balancing techniques may produce a lot of route changes for network flows which may affect network performance. In particular, the change in end-to-end delay can be interpreted by the TCP protocol as a sign to slow down its transmission. Taking into consideration that TCP is, by far, the most used transport protocol, this detail can have a severe impact on the overall network performance.

In the second part of the chapter, we use our network testbed to evaluate if frequent route changes can negatively impact the network performance. We conclude that the drop in the bandwidth of network flows can be significant if routes change too frequently. Moreover, network instabilities may happen as a result of bad inter-operation between the STREETE protocol and TCP if no special care is taken to avoid them.

We quantify the tolerable frequency based on data from our analysis and conclude the chapter with a discussion on the tuning to be done in the STREETE framework to achieve a stable, near-optimal, energy efficient traffic engineering solution.

Chapter 7 concludes the thesis with a summary of main findings, discussion of future research directions, and final remarks.

Reproducing the results

The simulation results from chapters 4 and 5 can be easily reproduced on a Linux system using Docker3 . Some of the simulations rely on CPLEX. This LP solver is free for academic usage and can be downloaded from IBM after an academic verification. If the CPLEX 12.7.1 installation file is provided, it will be automatically detected, and the corresponding results will be generated. If the appropriate version of the installation file is not provided, those simulations will not run.

Fast mode

To make it easy to reproduce the simulations, we provide an archive containing all the necessary files except CPLEX. Reproducing the results becomes as easy as executing the following steps:

• Install dependencies (docker, wget) using the package manager of your distribution.

• Download the archive with all the files: https://radu.carpa.me/these/streeteCode.tar

• Extract the archive: tar -xaf streeteCode.tar

• (optional) Put the "cplex_studio1271.linux-x86-64.bin" file in the streeteCode/installFiles folder • Build the docker image and run the simulations: cd streeteCode && ./buildAn-dRun.sh

In particular, on an Ubuntu host, you can just copy/paste the following lines into the terminal to follow these steps and run all the simulations except the CPLEX optimizations: sudo apt-get install docker.io wget wget https://radu.carpa.me/these/streeteCode.tar tar -xaf streeteCode.tar cd streeteCode sudo ./buildAndRun.sh echo "Finished!"

The raw simulation outputs will be placed into the streeteCode/results folder. An image is also generated for each simulated time point, thus providing a visual representation of the state of the network. An example of such a figure is given in Fig. 1.2 where the color and the percentage of the links represent their utilization. Two percentages are shown (one per direction). The color is a helper for easier visualization and corresponds to the biggest of these two percentages represented using the "jet" color scheme (blue = low utilization; red = high utilization4 ). A dotted line means that the link is used only in one direction. A slim black line means that neither of the two directions is used.

The figures which will be presented in chapters 4 and 5 will be generated in the sub-folders of the streeteCode/figures folder.

Fallback mode

Alternatively, a much smaller archive, which does not contain the third party installation files, is included with this PDF as an attachment on the first page of the manuscript. The same archive is also disposable via a couple of reliable cloud service:

• https://s3-eu-west-1.amazonaws.com/me.carpa.archive/Thesis/streeteCode.light.tar.xz

• https://drive.google.com/open?id=0B-57pIpvqZLgUThqbTh3ZnNleFk

The reader must manually provide the omnetpp-5.1-src-linux.tgz5 , inet-3.6.0-src.tgz 6 and qt-opensource-linux-x64-5.9.0.run7 files in the streeteCode/installFiles folder. Furthermore, similarly to the previous section, the CPLEX (cplex_studio1271.linux-x86-64.bin) binary can be added to enable the corresponding simulations.

To be also noted that the DockerFile file is self-explanatory. The commands listed in this file can be run directly on an ubuntu 16.04 host machine instead of using Docker.

Demo using the Android app

A much more interactive way to visualize the execution and result of the proposed algorithms is done by our Android application which can be freely installed via Google play. The QR code from Fig 1 .3 can be used to access the application on Play Store. A short instruction on how to use this application is provided in Appendix 7.2. In the previous chapter, we motivated the need for improving the energy efficiency of computer networks. Before digging into the core of this problem, we begin the current chapter by providing a general overview of the architectures of backbone networks and of solutions from the literature for reducing the energy these networks consume.

Afterward, we focus on a technique for reducing the energy consumption: intelligent traffic engineering. We present existing traffic engineering techniques and, in particular, the concept of Software-Defined Network (SDN). These practical details will allow us to understand better the state of the art on SDN-based traffic engineering in general and especially of energy efficient traffic engineering in backbone networks.

We finish the chapter by discussing the particularities that must be considered when designing a SDNbased solution for high-speed backbone networks. The presented challenges will define the design of our solutions in the rest of this work. This chapter also introduces the Source Packet Routing In NetworkinG (SPRING) protocol, designed for meeting the requirements of traffic engineering in backbone networks and for addressing some of the mentioned challenges.

CHAPTER 2. POSITIONING AND RELATED WORKS ON ENERGY EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS

Architecture of backbone networks

IP is now the de-facto protocol for transporting the data all around the world. It is also generally accepted that the optical technologies are the best solution for high-speed, long-distance communications. Current commercial products allow single-carrier optical transmissions at 200Gbps between nodes at 2000km distance [6]. To make the best use of the costly optical fibers, operators deploy multi-layered architectures. Fig. 2.1 shows a logical separation of the layers often found in an operator's network.

Physical layer

At the bottom of the architecture, we illustrate the actual optical fibers. Due to certain impairments, the signal passing through the fiber attenuates with the distance. As a result, optical amplifiers must be used to amplify the signal. Unfortunately, these devices also amplify the noise. There is hence a limit on the maximum number of amplifiers that can be used in series before the data becomes unrecoverable from the noise. An Optical-Electrical-Optical (OEO) conversion of the signal is needed to re-generate a new signal and therefore achieve longer distances. The distance between the optical amplifiers is approximately 80km. By using multiple amplifiers in series, manufacturers advertise that their devices can transmit a 100Gbps signal at a 5000km distance without the need for OEO conversion [6]. As a result, OEO conversion is usually not required between the points of presence except for submarine communication cables.

ARCHITECTURE OF BACKBONE NETWORKS

The energy consumption of the amplifiers is small. For example, the authors of [START_REF] Van Heddeghem | Power consumption modeling in optical multilayer networks[END_REF] affirm that the most common type of amplifier, the Erbium Doped Fibre Amplifier (EDFA), consumes approximately 110W to amplify all the wavelengths in the fiber. Nevertheless, the number of amplifiers may be considerable. Fig. 2.2 illustrates a small part of the physical topology of the Geant network. The little dots correspond to the various optical amplifiers along the fibers while the bigger squares correspond to WDM devices presented in the next section. As a result of their large number, the total power consumption of the optical amplifiers in a backbone network is not negligible.

Wavelength Division Multiplexing (WDM) layer

Second from the bottom is the Wavelength Division Multiplexing (WDM) layer. This layer operates on a wavelength (λ) granularity. Fig. 2.3a illustrates the operation of this layer at the node A from Fig. 2.1. The two signals from the upper layer are converted into two different wavelengths λ 1 and λ 2 and are multiplexed into the optical fibers by Add Drop Multiplexers (ADM). Historically, static optical splitters and cross-connects performed this job, but modern systems rely on Reconfigurable Optical Add Drop Multiplexers (ROADM) for remotely reconfiguring the optical layer. It is important to notice that the wavelength λ 3 is directly switched from one fiber to another without any additional treatment. Jumping forward, we can see that this wavelength is perceived by the upper, TDM, layer as a direct connection between the nodes B and D; it "bypasses" the upper layers of the node A. That is why the literature refers to this kind of connections by the name of "optical bypass".

The WDM technology enables the transmission of multiple terabits per second over a single optical fiber. Unfortunately, the number of wavelengths in a fiber is limited, and fine-grained traffic separation is difficult to achieve. This work is done by the higher levels of the core network hierarchy by multiplexing/demultiplexing multiple low-speed communications into/from an optical lambda.

We rely on the model of energy consumption presented in [START_REF] Van Heddeghem | Power consumption modeling in optical multilayer networks[END_REF]. After consulting a large number of commercial product datasheets, the authors conclude that the consumption CHAPTER 2. POSITIONING AND RELATED WORKS ON ENERGY EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS of an Add Drop Multiplexers (ADM) device (the big box in Fig. 2.1) can be modeled as d ¨85W `a ¨50W `150W , where d is the number of optical fibers entering the node; and a is the add/drop degree, the number of northbound interfaces connected to transponders. We must add to these values the power consumption of transponders, which are represented with small black rectangles on Fig. 2.1. They do complex electrical processing to generate the optical signal adapted for transmission over a long distance. The consumption of transponders, given by the same source [START_REF] Van Heddeghem | Power consumption modeling in optical multilayer networks[END_REF], is summarized in Tab. 2.1.

Speed (Gbps)

Consumption (W) To be noted that transponders correspond to cards (Fig. 2.3b) plugged into another network device. They are not independent devices as it can be viewed in Fig. 2.3a. The Time-Division Multiplexing (TDM) layer is usually built with the old SDH/SONET or the newer OTN(G.709) protocols. Their goal is to multiplex/demultiplex multiple low-speed connections into a higher speed λ for better spectral utilization of the optical fibers. In the absence of this layer, the point-to-point connection between the nodes A and C in the packet (IP/MPLS) layer would have to use an integral wavelength regardless of the needed capacity. As an example: assume that a client of the operator leases a dedicated connection between the nodes A and C with a capacity of 1Gbps. Without the TDM layer, the operator must reserve a whole wavelength (which has a potential of transmitting 400Gbps), to satisfy the clients' demand for 1Gbps. Fig. 2.4 schematically represents the work of the TDM layer at node A. The gray and the black signals are multiplexed into a single one, with higher data rate.

Time-Division Multiplexing (TDM) layer

The power consumption of the TDM ports is presented in Table 2.2.

Packet layer

Finally, the IP/MPLS layer corresponds to the packet based transmission. Similarly to the previous layers, the network topology seen by the packet layer corresponds to a virtual topology which does not necessarily matches the physical optical fibers. In particular, in A particularity of the packet layer in operator networks is that it frequently relies on MultiProtocol Label Switching (MPLS) forwarding rather than IP routing. This is because the "best effort" service provided by IP is insufficient in today's convergent networks. Intelligent traffic management is needed to enable a network to be shared between delay-critical audio flows and best-effort traffic.

In this layer, a single device can consume as much as 10 kilowatts, 75% of which is due to the slot and port cards regardless of their utilization [START_REF] Van Heddeghem | Power consumption modeling in optical multilayer networks[END_REF].

Layered backbone networks, from theory to practice

Unfortunately, there is no consensus on the best combination of the previously presented layers and on how to better map the IP traffic into the optical fibers. Multiple different solutions can be encountered in currently deployed operator networks as a result of searching for a balance between complexity, features, and cost. Small players will tend to choose convergent solutions to reduce the operational cost of their network. On the contrary, larger operators tend to have a very clear separation between the layers and even have separate teams responsible for the operation and management of each layer.

Moreover, each device manufacturer tries to push the technologies at which they are best. For instance, Cisco, one of the leaders in packet-based forwarding, attempts to encourage the use of entirely convergent packet over fiber solutions, promising a better link utilization at a fraction of the cost of implementing a network with TDM devices. On the other hand, manufacturers with a long background in the telecommunication industry promote TDM solutions for interoperability with legacy devices and to offload the transit traffic from the IP/MPLS routers.

The most common architectures are IPoOTN and IPoWDM. Each one of them has its strengths and its weaknesses which we present in the following sections.

IP over OTN (IPoOTN)

In theory, Optical Transport Network (OTN) is just a Time-Division Multiplexing (TDM) protocol standardized by the International Telecommunication Union (ITU) in the G.709 recommendation [START_REF]Interfaces for the optical transport network[END_REF]. At the same time, in the networking lingo, IPoOTN refers to a group of integrated solutions: where the TDM sub-wavelength multiplexing and the management of WDM lambda wavelengths are both done by the same device. This allows For historical reasons, IPoOTN is the preferred choice of large transit operators. The OTN devices are designed to be backward compatible with legacy TDM protocols (SDH and SONET) which were deployed in times when most network traffic consisted of audio flows. OTN devices allow gradual transitions to higher speeds without having to completely re-design the existing network.

CHAPTER 2. POSITIONING AND RELATED WORKS ON ENERGY EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS

Another advantage of OTN solutions is the fact that transit traffic is kept at TDM layer instead of passing through multiple IP routers and the fact that existing protocols are very mature and allow end-to-end management through multi-vendor networks. Nevertheless, there are no technical limitations to implement these services, i.e. multi-tenancy and agile management of transit traffic, in the packet layer. Moreover, IP/MPLS packet forwarding can be seen as a Time-Division Multiplexing (TDM) technique. The services provided by the packet and the TDM layer are, to some extent, redundant. That is why in the modern era, with most network traffic being packet-based, IPoWDM architectures that we present in the next section are becoming increasingly popular.

IP over WDM (IPoWDM)

In IPoWDM solutions, the IP routers integrate re-configurable optics which allow generating the optical lambda wavelength directly. They are then mapped into the optical

ON IMPROVING THE ENERGY EFFICIENCY OF IPOWDM BACKBONE NETWORKS

fibers by a separate Reconfigurable Optical Add Drop Multiplexers (ROADM). This solution moves the cost of transponder/optics from optical layer equipment to the router. The IP/MPLS packets are directly mapped into optical fibers without the need for the intermediate TDM layer. The aggregation of multiple small, low speed, flows into a highspeed flow is thus done at packet layer. The multi-tenancy and Quality of Service (QoS) are also implemented using the MPLS and RSVP-TE protocols at the packet level.

This level allows the most flexibility in traffic management. The disadvantage of this solution is in need to process all the transit packets in the IP layer. The packet processing per gigabit is, unfortunately, more costly than the TDM processing: the most power-efficient devices consume 7W per Gbps for IP/MPLS processing, which is slightly worse than TDM processing shown in Tab. 2.2. On the other hand, an optical bypass can be used when it is justified to avoid transit processing.

On improving the energy efficiency of IPoWDM backbone networks

In the previous section, we presented the different levels which can be encountered in backbone networks and described the two types of topologies deployed in production networks, namely IPoOTN and IPoWDM. Due to the relative simplicity of the IPoWDM and to the fact that this topology is better suited for the currently predominant IP traffic, we decided to target it in this thesis. Following a pioneering work [START_REF] Gupta | Greening of the Internet[END_REF] on reducing the energy consumption of computer networks, numerous other authors dedicated themselves to improving their energy efficiency. In this section, we start by a quick general overview of the different approaches proposed in the literature and targeting IPoWDM networks. This introduction will lead us to the introduction of the domain of energy efficient traffic engineering in the IP layer.

Energy efficient network design

Some works approach the problem of network energy efficiency from a clear-state design perspective. [START_REF] Dong | On the Energy Efficiency of Physical Topology Design for IP Over WDM Networks[END_REF], for example, proposes to incorporate the energy efficiency as a decision variable from the earliest stage of the network construction: the design of the physical network topology. The authors inspect how different physical topologies result in various overall power consumption. Direct fibers between the nodes reduce the average hop count and allow to avoid the power-hungry electrical processing of transit traffic. However, such direct long links need more optical amplifiers which consume power regardless of the amount of traffic passing through a link. The authors investigate the balance between these factors.

With the same goal of reducing the network hop counts, the GreenTouch consortium proposed [START_REF]GreenTouch Final Results from Green Meter Research Study[END_REF] to re-design the modern Internet and use long reach point to point optical links to directly connect the end users and business to an extremely well-meshed network core.

On the other hand, most researchers follow a less radical approach and consider that the physical topology of optical fibers cannot be changed. A multitude of works [START_REF] Chabarek | Power Awareness in Network Design and Routing[END_REF][12] [START_REF] Coiro | Impact of energy-aware topology design and adaptive routing at different layers in IP over WDM networks[END_REF] search to optimize the network design for energy consumption by selecting

CHAPTER 2. POSITIONING AND RELATED WORKS ON ENERGY EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS

the best combination of IP and optical devices at each point of presence. Such works usually use linear or nonlinear models because the computational time is not crucial in the network design phase.

Another approach to energy efficient network design relies on the following idea: the best way to reduce the energy consumption of the networks is to completely avoid using the network. A very attractive solution relies on caching the content as close to the end user as possible. In particular, [START_REF] Kilper | Energy challenges in access and aggregation networks[END_REF] proposes to use Content Delivery Networks (CDNs) and FOG1 computing to avoid the growth of the network energy consumption beyond what power grids can sustain. To be noted that CDNs are already widely used by content providers such as Netflix to both unload the network core and improve the user experience [START_REF]Scaling the Netflix Global CDN, lessons learned from Terabit Zero[END_REF]. There are thus no technical limitations to implement this kind of solutions.

An alternative way to reduce the amount of network traffic, applicable when CDNs can not easily cache the content, is the redundancy elimination. Individual devices are placed in the path of network flows, and compression mechanisms are afterward used to reduce the amount of data sent trough the system. Unfortunately, when it comes to evaluating the energy consumption of solutions employing redundancy elimination, the research community diverges. [START_REF] Kilper | Energy Challenges in Current and Future Optical Transmission Networks[END_REF], for instance, affirms that the increase of energy consumption due to compression may be higher than the reduction due to transmitting fewer data into the network. Other works are more optimistic [START_REF] Dong | Energy-efficient core networks[END_REF] [START_REF] Giroire | Minimization of network power consumption with redundancy elimination[END_REF]. For example, the authors of [START_REF] Giroire | Minimization of network power consumption with redundancy elimination[END_REF] propose a solution which combines compression with energy efficient traffic engineering which we present in a later section. The authors take special care to avoid the unfavorable case shown in [START_REF] Kilper | Energy Challenges in Current and Future Optical Transmission Networks[END_REF].

Energy efficient device design

The power consumption of network devices per Gbps of traffic is "naturally" decreasing thanks to the Moore's Law and continuous miniaturization of electronic components. Nevertheless, the energy proportionality of modern network devices remains surprisingly bad. For example, [START_REF] Chabarek | Power Awareness in Network Design and Routing[END_REF] measured the energy consumption of IP/MPLS routers and concluded that the load has a marginal impact on the power consumption. This result was also confirmed by measurements done by our team on a network switch (Fig. 2

.6).

To increase the energy proportionality of network devices, the Institute of Electrical and Electronics Engineers (IEEE) standardized the 803.2az protocol [START_REF] Bolla | A Closed-Form Model for the IEEE 802.3az Network and Power Performance[END_REF]. This solution puts sub-components of network interface to sleep for short time periods when no packet is passing through the interface. When packets arrive into the interface's packet queue, the latter is awakened and the data is transferred. Small Office Home Office (SOHO) devices implementing the 803.2az protocol are already commercialized.

Unfortunately, transitions to/from the sleeping mode uses both energy and time. As a consequence, the efficiency of this approach is small when interfaces are highly utilized. For example, when waking from a low power state, the energy consumption of the interface may spike up to 4 times the power needed under normal operation [START_REF] Bolla | The hidden cost of network low power idle[END_REF]. Experimental analysis shows that the power savings are close to zero when the utilization of the interfaces reaches 20% [START_REF] Sivaraman | An experimental power profile of Energy Efficient Ethernet switches[END_REF]. Furthermore, this approach is only applicable in access networks and is not efficient on backbone links due to a very short inter-packet arrival time [START_REF] Bolla | Energy efficiency in optical networks[END_REF]. To illustrate the reason, assume a 100Gbps interface which is utilized at 10%. If it receives uniformly distributed 1000byte packets, it will receive a packet every 0.8 microseconds. With existing technologie, the time needed for an interface to transit to a low power state or to be awakened from sleep is much longer. Evidences show that modern commercial transponders need that tens of seconds, or even minutes, to become operational after a power cycle2 , [START_REF] Cfp Msa Group | C form-factor pluggable (CFP) Specification[END_REF], [START_REF]SFF-8431 Specification for SFP+[END_REF]. Fortunately, the research community affirms that it is possible to reduce this time and that transitions to/from a low power state are possible in milliseconds [START_REF] Miyazaki | High speed 100GE adaptive link rate switching for energy consumption reduction[END_REF] by keeping part of the interface active, like in the 802.3az protocol.

ON IMPROVING THE ENERGY EFFICIENCY OF IPOWDM BACKBONE NETWORKS

Alternatively, Adaptive Link Rate (ALR) technologies propose to reduce the energy consumption of network devices and achieving a better energy proportionality by dynamically adapting the maximum rate of the network links. The port modulation is changed when lower data rates are needed and hence adjust the rate. For example, at low demands, a Gigabit Ethernet port will be passed to a 100Mbit mode. By doing that, the power consumption will be reduced. [START_REF] Morea | Datarate Adaptation for Night-Time Energy Savings in Core Networks[END_REF] analyses the possibility of doing modulation scaling in optical backbone networks.

New technologies may emerge soon to reduce the power consumption of network devices even further. The STAR project [START_REF]Confidential CHIST-ERA Project Periodic Report[END_REF], for example, promise shortly to present a prototype of an all-optical switch which can be used to switch terabits worth of wavelengths while only consuming 8 watts.

We believe that the solutions which rely on energy efficient network design, CDNs, redundancy elimination, and energy-efficient device design are indispensable in a genuinely eco-responsible solution. However, these are long-term solutions. On a shorter time scale, it is possible to increase the energy efficiency of existing networks by using intelligent provisioning and traffic management, which we present in the next subsections.

CHAPTER 2. POSITIONING AND RELATED WORKS ON ENERGY EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS

IPoWDM cross-layer optimization: leveraging optical bypass

The multi-layered architecture of backbone networks enables the possibility to save energy through a joint optimization of the IP and WDM layers. For instance, processing IP/MPLS traffic in the electronic domain consumes more power per Gbps than bypassing the intermediate node in the optical domain. The all-optical transmission is cheap: transporting an additional point-to-point WDM wavelength over existing infrastructure is virtually "free" regarding energy consumption of intermediate point of presence. However, each wavelength passing through the optical layer must be generated by energy-hungry transponders.

As a consequence, there are various works which search for a balance between routing the traffic in the IP/MPLS layer and bypassing the upper layers in the optical domain. The authors of [START_REF] Comellas | Integrated IP/WDM routing in GMPLS-based optical networks[END_REF] and [START_REF] Lee | Traffic grooming for IP-Over-WDM networks: Energy and delay perspectives[END_REF] show, using mathematical models, that a proper technique to balance the traffic between the IP/MPLS layer and the optical bypass via λ-paths can increase the network performance and decrease the energy consumption.

Unfortunately, there are also works which show that power saving potential of this technique is not as clear as it seems. The authors of [START_REF] Van Heddeghem | Power consumption evaluation of circuit-switched versus packet-switched optical backbone networks[END_REF] conclude that optical bypass occurs to consume more energy than IP processing if wavelengths are filled at less than 50%. For example, using a dedicated wavelength, and thus dedicated transponders, to transport a small (100Mbps) flow and bypass IP processing at a couple of intermediate nodes will consume much more energy than processing the same 100Mbps of traffic in the IP layer of the intermediate nodes. The wavelengths must be adequately filled to profit from the advantage of the optical bypass. The authors of [START_REF] Musumeci | On the energy consumption of IP-over-WDM architectures[END_REF] also conclude that there is no general solution to the cross-layer optimization problem. Its usefulness always depends on the network topology (dimension, connectivity index) and the network load. The authors of [32] [33] used MILP models to analyze the saving potential in different layers and conclude that optimizing the traffic in the IP layer allows the most energy savings while dynamically re-configuring the optical domain has little impact on the energy efficiency in real networks.

To make things even more complicated, the number of WDM lambdas sharing a fiber is limited. Moreover, more transponders mean more place in the network device chassis. With current technological limitations on the number of wavelengths per fiber, it is impossible to efficiently create a well-meshed topology of point-to-point WDM wavelengths in a big network.

After reading all this evidence, we decided not to do cross-level optimizations and to concentrate instead solely on increasing the network energy efficiency via traffic engineering in the packet layer.

Energy efficient network operation

The energy efficient network operation techniques act by optimizing the utilization of resources which are already present in the network. These approaches contrast to the energy efficient network design, which is used to decide how to deploy resources and build an entirely new network.

A popular technique which allows reducing the energy consumption of computer net-

TRAFFIC ENGINEERING

works rely on aggregating traffic flows over a subset of network resources, allowing to switch off a subset of network components.

In an ideal world with energy proportional network devices, the energy consumption would scale linearly with the utilization. As a result, there would be no way to improve the energy efficiency by extending the paths of network flows. However, we already presented in a previous section (2.2.2), that the consumption of the modern devices is not linear and maximizing the device utilization increases its energy efficiency.

In this thesis, we follow the trend of optimizing the energy consumption in the IP layer. First of all, the energy consumption of the IP layer was shown to dominate the one in the optical layer [START_REF] Tucker | Evolution of WDM Optical IP Networks: A Cost and Energy Perspective[END_REF]. Secondly, the optical fibers are frequently shared among different operators and re-optimizations in the optical layer without turning amplifiers off has a marginal impact on the consumption of the network [START_REF] Idzikowski | Saving energy in IP-over-WDM networks by switching off line cards in low-demand scenarios[END_REF] [START_REF] Idzikowski | Dynamic Routing at Different Layers in IP-over-WDM Networks -Maximizing Energy Savings[END_REF]. It is also important to notice that, while transponders can be quickly shut down, switching amplifier sites on and off is a time-consuming task [START_REF] Morea | Protocol Enhancements for "Greening" Optical Networks[END_REF]. Lighting on an intercontinental fiber may take several hours.

We also limit ourselves to only turning off links, i.e. router ports and transponders, without touching to network devices. The main reason is that there is no clear separation between core and aggregation devices in production networks. Any core router is, at the same time, used to aggregate client traffic. Turning the device off would cut the connectivity of all connected clients. To be noted that some works proposed to virtualize the network devices and transparently forward optical access/aggregation ports to an active node using the optical infrastructure [START_REF] Chen | Virtual router migration and infrastructure sleeping for energy management of IP over WDM networks[END_REF][37] [START_REF] Eramo | Evaluation of Power Saving and Feasibility Study of Migrations Solutions in a Virtual Router Network[END_REF]. We believe that this solution has significant shortcomings. One of them is the fact that access ports are not adapted to long-distance transmission. We prefer thus to avoid switching off network nodes.

To switch off a subset of network resources, traffic engineering techniques are needed to wisely optimize the paths for traffic flows while satisfying a set of performance objectives. In the following section, we provide a detailed analysis of what traffic engineering is and off associated related work in the field of applied energy efficient traffic engineering via turning links off.

Traffic engineering

The goal of traffic engineering is to change the paths of network flows to satisfy a set of performance objectives. For example, good energy savings can be achieved by employing traffic engineering and turning off idle resources.

When it comes to implementations, two main different traffic engineering approaches exist: proactive and reactive. In the proactive case, actions are taken upfront to avoid unfavorable future network states. In contrast, reactive solutions will dynamically adapt to adverse events which already happened in the network. An example of such adverse event is network congestion. A network element is said to be congested if it experiences sustained overload over an interval of time. Congestion almost always results in the degradation of the Quality of Service (QoS) perceived by the end users. If it is possible, a traffic engineering solution will re-distribute the traffic to avoid congestion at any device in the network. For example, if a network resource becomes congested due to an increase in network traffic, the overall network may be reconfigured to reduce the load on this EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS resource. Some of the most common traffic engineer optimization objectives are load balancing to avoid congestion; path protection in case of a link or device failure; differentiated service for distinct classes of network flows.

In this work we are particularly interested in two traffic engineering objectives: i) minimizing the energy consumption of the network by releasing links and turning them off ; ii) increasing the efficiency of resources by increasing their utilization while avoiding congestion.

A significant challenge of traffic engineering solutions is to react to changes in the network automatically. To detect these changes, traffic engineering has to gather information about the state of the network. Therefore, once a change in network condition is detected, techniques are required to configure the behavior of network elements to steer traffic flows accordingly. Such functions, embedded into data and control planes, were traditionally performed in a decentralized manner, but more recently many traffic engineering schemes have re-considered the centralization of control functions.

In the remaining part of this section, we present the most popular traffic engineering techniques. We start with the decentralized and reactive solutions relying on the Interior Gateway Protocol (IGP). Afterward, we introduce the centralized techniques relying on the IGP weight assignment and those using MPLS with Resource reSerVation Protocol Traffic Engineering (RSVP-TE) or Path Computation Element (PCE). We finish with an introduction to SDN and the related works in the field of energy efficient traffic engineering.

Traffic engineering using the IGP

A well-known reactive distributed approach to traffic engineering relies on Interior Gateway Protocol (IGP), such as OSPF [START_REF] Moy | OSPF Version 2[END_REF] or IS-IS [START_REF] Oran | OSI IS-IS Intra-domain Routing Protocol[END_REF]. It is easy to enable this kind of traffic engineering because it relies on a single protocol, which is almost always present in the network.

The Interior Gateway Protocol (IGP)-based traffic engineering allows to dynamically adapt the routes of traffic flows across the network based on available network resources; the routes are dynamically changed to meet QoS requirements. To achieve that, the network devices periodically flood the network with information about the load of the directly connected links. This information allows each network device to compute the paths through the network in a way which avoids heavily used spots.

A constrained shortest path algorithm is used for this purpose. However, special care must be taken to prevent oscillations: when all devices start using a lowly loaded link and congest it. This action, in its turn, makes all the devices avoid the link. For instance, the analysis of the OSPF-based traffic engineering shows that it may take whole minutes to converge to a steady state after an unfavorable network event [START_REF] Goyal | Improving Convergence Speed and Scalability in OSPF: A Survey[END_REF]. Moreover, a detailed analysis of OSPF-TE indicates that its communication overhead is extremely high even under normal operation of the network [START_REF] Salsano | Traffic Engineering with OSPF-TE and RSVP-TE: Flooding Reduction Techniques and Evaluation of Processing Cost[END_REF]. As a result, the IGP-based traffic engineering is reserved for small networks and is seldom used in production.

TRAFFIC ENGINEERING

Traffic engineering via IGP metric assignment

A way to profit of centralized network-wide optimization while maintaining a low management overhead is to assign metrics to network links. As a result of this action, the classical shortest path algorithms used by the IGP will diverge from the initial routes. The disadvantage of solutions relying on the IGP metric is in the fact that they are limited by the use of shortest path to compute the routes. However, a theoretical property affirms that an optimal routing is possible in the network by using only D+M paths in the network [START_REF] Liu | Multipath Routing from a Traffic Engineering Perspective: How Beneficial Is It?[END_REF] , where D is the number of demand pair and M the number of links. As a result, such solutions can actually approach very close to the optimum.

Traffic engineering using MPLS

A more elegant reactive traffic engineering solution relies on MultiProtocol Label Switching (MPLS); a protocol frequently used in backbone networks 3 . One of the strengths of MPLS is its ability to explicitly set the path of the packets by using virtual tunnels instead of transmitting them over the shortest path.

Two different approaches to MPLS-based traffic engineering exist, namely distributed and centralized. In the distributed case, to achieve the TE objective, information about the network is propagated between the nodes in the same way as in the case of IGP-based TE. The convergence speed is drastically improved thanks to the fact that each device tries to reserve resources before actually changing the routes of network flows. The RSVP-TE CHAPTER 2. POSITIONING AND RELATED WORKS ON ENERGY EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS [START_REF] Farrel | Inter-Domain MPLS and GMPLS Traffic Engineering -Resource Reservation Protocol-Traffic Engineering (RSVP-TE) Extensions[END_REF] protocol is used between nodes to reserve resources along a path in the network. MPLS is then used to create a virtual tunnel which bypasses the shortest paths. It is also possible to establish multiple disjoint tunnels from a source to a destination. Equal-cost Multi-path (ECMP) is afterward used to split the traffic across multiple tunnels towards an egress device. Even if, by using resource reservation, the convergence speed increases and the risk of oscillations decreases, this solution still leads to under-optimality due to the greedy local selection of network paths by each device.

The centralized MPLS-based traffic engineering is the precursor of SDN. In this case, a Path Computation Element (PCE) is used. A PCE is a special device that monitors the networks and programs the paths into the network devices. We do not spend time on this case because it is fundamentally equivalent to SDN, which is explained in the next section.

Traffic engineering using SDN

Software-Defined Network (SDN) is a novel paradigm which seeks to bring even more agility into the networks. It can be seen as an evolution of the Path Computation Element (PCE)-based TE and allows the integration of the system with custom-made software to enable resource management at a level which is unreachable by traditional network protocols. In particular, SDN allows a lot of flexibility when it comes to traffic engineering which can solve the shortcomings of the previous solutions by leveraging centralized traffic management.

There is no consensus on what Software-Defined Network (SDN) means. It is even usual to encounter conflicting points of view. For example, SDN is frequently considered to be a synonym of OpenFlow. In contrast, in this work, we adhere to a more general definition of SDN, given in the RFC 7426 [START_REF] Haleplidis | Software-Defined Networking (SDN): Layers and Architecture Terminology[END_REF]: A programmable network approach that supports the separation of control and forwarding planes via standardized interfaces.

An essential element of SDN is thus the separation of the control plane from the data plane. In practical terms, that means that network devices perform tasks that ensure data forwarding (i.e. the data plane) whereas management activities (i.e. the control plane) are factored out and placed at a central entity termed as the SDN controller. Fig. 2.8 illustrates the layers of a software defined network.

• At the bottom, we represent the network devices which are simplified to the maximum. Instead of running complex distributed protocols, the network devices are only capable of forwarding packets that arrive through an incoming port towards the correct outgoing port. Henceforth data plane devices will be referred to as SDN switches.

• In the middle is the SDN controller, which executes many of the traffic-engineering requirements on gathering traffic information, performing management and control. SDN controllers enable a lot of flexibility when it comes to traffic engineering. They maintain and exploit network-wide knowledge to execute all required computations. In Fig. 2.8 the controller is illustrated running a topology service, which discovers the network topology; a statistics service to keep track of network status, and a flow rule service to apply routes into the network devices. • At the top, we show the custom business applications written in the network administrator's language of choice. An example application is cloud infrastructure utilizing a network to provision cloud services for customers.

The communication between the layers is done via abstraction APIs. This comes in contrast to the traditional networks, where the control and data planes are tightly coupled. An effort has been made towards standardizing the interface between the controller and the data plane, generally termed as southbound API, and the manner the controller exposes network programmability features to applications, commonly called northbound API. The most known southbound API is OpenFlow. When it comes to the northbound API, it is frequently exposed as HTTP-based RESTful APIs.

In a short period, Software Defined Networks have emerged from a concept into a product which is expected to revolutionize the network management. Some SDN pioneers, including Microsoft [START_REF] Hong | Achieving High Utilization with Softwaredriven WAN[END_REF] and Google [START_REF] Jain | B4: Experience with a Globallydeployed Software Defined Wan[END_REF], have deployed software controlled networks in production environments, increasing the efficiency of their system.

In the next section, we present the challenges which appear when implementing SDNbased traffic engineering in backbone networks.

Energy efficient traffic engineering

Numerous works rely on traffic engineering to reduce the energy consumption of the computer networks. The idea is to modify the paths of network flows in a way to minimize the energy consumption. Some of the works, for instance, set the paths in a way to optimize the network for adaptive link rates, but the majority seeks to turn off the links or even devices completely. As noted in the previous section, we position ourselves in-between and concentrate on solutions which only turn-off links.

CHAPTER 2. POSITIONING AND RELATED WORKS ON ENERGY EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS

Distributed traffic engineering

One of the few works which rely only on the IGP for energy-efficient traffic engineering is [START_REF] Bianzino | GRiDA: A green distributed algorithm for backbone networks[END_REF]. In this work, every node monitors the utilization of adjacent links and decides whether to switch off a link by using a utility function that depends on the energy consumption and a penalty function which we describe later. If a link is chosen for switch off, the node floods into the network its will to turn it off. All nodes update their IP routing tables via the IGP. As a result, the data flows will avoid the links marked for sleep. Machine learning mechanisms are used to avoid choosing links whose extinctions provoked a congestion in the past. A per-link penalty is used for this purpose: each time a wrong decision caused a degradation of the network performance, the penalty increases, ensuring that the link will not be turned off in the near future.

Unfortunately, the authors drastically underestimate the overhead of their solution regarding exchanged messages. In a network with 30 nodes, they estimate that OSPF-TE would flood the system once every 10 seconds. However, a detailed analysis of OSPF-TE [START_REF] Salsano | Traffic Engineering with OSPF-TE and RSVP-TE: Flooding Reduction Techniques and Evaluation of Processing Cost[END_REF] shows that it will happen six times per second. If we recalculate the results from [START_REF] Bianzino | GRiDA: A green distributed algorithm for backbone networks[END_REF], we discover that the announced overhead of 0.52% will become a 30% increase in the number of OSPF-TE flooding. This is not negligible because OSPF-TE flooding is costly both in the number of messages and needed processing power.

Another work which relies on the IGP to do energy efficient traffic engineering is [START_REF] Bianzino | Distributed algorithms for green IP networks[END_REF]. The authors propose to use OSPF-TE to announce the link load into the network. Afterward, if no link has a load greater than a certain threshold, the least loaded link is locally turned off by the corresponding node. If the threshold is violated, the last turned-off link is awakened. This solution has the weakness of potentially turning on links in the network even if this action does not help to solve the congestion.

[50] presents an original solution where a control node is elected in the network. This node then guides the construction of the solution to obtain better overall energy savings while still mostly relying on the distributed operation of the IGP. A subset of this algorithm was implemented using the Quagga software by the authors of [START_REF] Rifai | Towards enabling green routing services in real networks[END_REF]. Sadly, the paper provides little insights on the lessons learned from this implementation.

All previously mentioned papers suffer from the biggest problem of solutions relying entirely on the IGP: a slow convergence. That is why centralized solutions, relying on metric assignment or precise routes via MPLS or SDN, are more frequently proposed in the literature.

Centralized traffic engineering

Centralized energy efficient traffic engineering solutions use a central controller in charge of executing an optimization algorithm and apply the changes to the network. The centralized solution can be grouped into two categories: i) based on IGP metric assignment, and ii) based on explicit paths. When it comes to selecting between these two techniques, we must note that it was theoretically proven that, for any optimal solution that uses explicit paths, it is possible to find a link weight assignment under which these paths are the shortest [START_REF] Shen | Routing On Demand: Toward the Energy-Aware Traffic Engineering with OSPF[END_REF]. As a result, it is possible to obtain very good solutions using link weight assignment.

The solutions relying on metric assignment act by setting a high metric on the links which have to be turned off. As a result, the traffic is rerouted to avoid these "costly"

CHALLENGES IN IMPLEMENTING SDN-BASED TRAFFIC ENGINEERING

IN BACKBONE NETWORKS links, allowing to turn them off effectively. Nevertheless, this approach has a major drawback: temporary network loops can be created during the re-configuration of IGP as a result of weight changes. Alternatively, using explicit paths enables more flexibility in traffic management like, for example, easier unequal cost multipath forwarding and avoidance of network loops. Pioneer works in this field proposed to use MPLS for data forwarding [START_REF] Zhang | GreenTE: Power-aware traffic engineering[END_REF]. Recently, the trend shifted towards using SDN for solutions relying on explicit path.

The panorama of research in these two fields is vast. For example, a recent survey [START_REF] Idzikowski | A Survey on Energy-Aware Design and Operation of Core Networks[END_REF], cites more than 50 works which propose to reduce the energy consumption of wired network via centralized traffic engineering. There is a trade-off to be found between the energy efficiency, network performance, and computational complexity. For instance, the optimal solution to the problem of energy efficient traffic engineering can be found using linear and non-linear models. Moreover, these models can easily be augmented to incorporate additional constraints like, for example, path protection [START_REF] Addis | On the energy cost of robustness and resiliency in IP networks[END_REF]; limited number of network reconfiguration per day [START_REF] Chiaraviglio | Sleep modes effectiveness in backbone networks with limited configurations[END_REF] [57]; redundancy elimination [START_REF] Giroire | Minimization of network power consumption with redundancy elimination[END_REF]; maximum propagation delay [START_REF] Wang | Energy-aware routing algorithms in Software-Defined Networks[END_REF]; Quality of Service (QoS) [START_REF] Yonezu | QoS aware energy optimal network topology design and dynamic link power management[END_REF].

A constraint which is frequently encountered in SDN based work is the limiting size of flow tables [START_REF] Khattar | Power-efficient routing for SDN with discrete link rates and size-limited flow tables: A tree-based particle swarm optimization approach[END_REF] [START_REF] Giroire | Optimizing rule placement in softwaredefined networks for energy-aware routing[END_REF]. These works target OpenFlow networks and, as a result, flow coalescing can overflow the flow table which is implemented in a size-limited ternary content addressable memory (TCAM). We believe that this costly constraint can be avoided by using the SPRING protocol instead of OpenFlow [START_REF] Davoli | Traffic Engineering with Segment Routing: SDN-Based Architectural Design and Open Source Implementation[END_REF]. This point of view also seems to be shared by the authors of [START_REF] Thaenchaikun | Mitigate the load sharing of segment routing for SDN green traffic engineering[END_REF], who are among the first to propose a solution for energy efficient traffic engineering built with the SPRING protocol in mind.

All the previously mentioned linear and nonlinear models cannot be solved to optimality on any, but small, network. That is why the authors usually also propose heuristics intended for use in real networks. Unfortunately, few works report the computational complexity of their algorithms. Such works include [START_REF] Moulierac | Optimizing IGP Link Weights for Energy-efficiency in Multi-period Traffic Matrices[END_REF], reporting up to one hour of computation; [START_REF] Zhang | GreenTE: Power-aware traffic engineering[END_REF] who artificially limit the execution time to 300s; [START_REF] Giroire | Optimizing rule placement in softwaredefined networks for energy-aware routing[END_REF] reports 10 seconds on a 15 node network; [START_REF] Yonezu | QoS aware energy optimal network topology design and dynamic link power management[END_REF] announce between tens of second, up to multiple hours depending on the desired precision.

In our work, we seek to design a solution which can react fast to network condition changes at the expense of trading off the additional optimization constraints. A similar work [START_REF] Wang | Energy-aware routing algorithms in Software-Defined Networks[END_REF] reports 10 seconds of computation on a 400 node network. However, their algorithm heavily depends on the number of request and the authors evaluated the solution with less than 2000 requests, which is extremely small for such a big network.

Challenges in implementing SDN-based traffic engineering in backbone networks

Traffic-engineering schemes are increasingly relying on SDN to simplify configuration and management operations. In this thesis, we also rely on SDN for the purpose of network optimization. We make use of the centralized view of (i) the network topology, (ii) running applications and, (iii) traffic demands; to program a network and change its virtual topology according to traffic conditions. Decoupling the control plane and the data plane produces its drawbacks. For instance,

CHAPTER 2. POSITIONING AND RELATED WORKS ON ENERGY EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS

the protocol traditionally used in SDN networks, OpenFlow, relies on the centralized management to the point that the network becomes nonoperational without a controller. Such a single critical point of failure is unacceptable in backbone networks.

In this section, we discuss the challenges and requirements in designing a SDN-based traffic engineering solution for backbone networks. This will allow us to introduce the constraints which will define the design of our algorithms.

Impact of traffic engineering on network flows

It is worth mentioning that rerouting the flows in the network changes the end-to-end delay perceived by network flows. Compared to Local Area Networks, where the delay variation is small and has little impact on performance, in backbone networks, the delay of two paths can differ significantly. As a result, packet reordering may occur, as depicted in Fig. 2.9 : packet 1 arrives at node b after the packets 2 and 3. This reordering may influence the speed of the flow. The Transmission Control Protocol (TCP), for instance, may assume a network congestion and reduce the sending rate. Due to that, the networking folklore implies that changing the route of TCP flows will have a severe negative impact on their throughput. The research community has extensively estimated the impact of random packet reordering on the performance of TCP flows. However, rerouting the flows is different from random packet reordering in the sense that reordered packets arrive in bursts at the receiver and may result in a different behavior compared to randomly reordered packets. Moreover, the joint evolution of the congestion window size of multiple TCP flows sharing a single router or link exhibit fluctuations due to the network as a whole and come on top of the standard behavior of TCP [START_REF] Baccelli | Interaction of TCP Flows As Billiards[END_REF].

To the best of our knowledge, previous work has not specifically evaluated the impact of frequent flow rerouting on multiple aggregated transported flows. Some works which estimated the impact of reordering on TCP include Bennett et al. [START_REF] Bennett | Packet reordering is not pathological network behavior[END_REF], who were among the first to highlight the frequency of packet reordering and its impact on the throughput of TCP flows. Their results showed that packet reordering has a powerful effect on a network's performance. As a result, the authors of [START_REF] He | Towards Robust Multi-Layer Traffic Engineering: Optimization of Congestion Control and Routing[END_REF], for example, proposed a traffic engineering algorithm which tries to optimize the congestion control and routing jointly. In the meantime, Laor and Gendel [START_REF] Laor | The effect of packet reordering in a backbone link on application throughput[END_REF] have experimentally measured the impact of reordering on a testbed and also concluded that even a small rate of packet reordering could significantly affect the performance of a high bandwidth network. A lot of work was afterwards performed to increase the tolerance of TCP to packet reordering [START_REF] Leung | An Overview of Packet Reordering in Transmission Control Protocol (TCP): Problems, Solutions, and Challenges[END_REF]

CHALLENGES IN IMPLEMENTING SDN-BASED TRAFFIC ENGINEERING IN BACKBONE NETWORKS

Finally, a solution to detect unneeded retransmissions caused by packet re-ordering and undo the congestion window was proposed and implemented. The problem of packet reordering was considered solved until the introduction of Multi-Path forwarding, where packets of a single flow are split among different paths [START_REF] Karlsson | Impact of multi-path routing on TCP performance[END_REF] [START_REF] Dixit | On the impact of packet spraying in data center networks[END_REF]. An RFC was even created to prevent splitting TCP flows over multiple paths [START_REF] Swallow | Avoiding Equal Cost Multipath Treatment in MPLS Networks[END_REF].

It is worth noting that different authors arrive at opposite conclusions concerning the impact of multi-path forwarding on TCP. Karlsson et al. [START_REF] Karlsson | Impact of multi-path routing on TCP performance[END_REF], for example, concluded that multi-path forwarding reduces the throughput of TCP flows and that mitigation techniques implemented at the transport layer in the Linux kernel are not effective in reducing the impact of packet reordering. On the other hand, the authors [START_REF] Dixit | On the impact of packet spraying in data center networks[END_REF] affirm that multi-path forwarding in fat tree data-center networks has little impact on the throughput. In any case, modern multi-path forwarding techniques try to act on a flowlet level and avoid reordering [START_REF] Katta | HULA: Scalable Load Balancing Using Programmable Data Planes[END_REF].

We performed an extensive evaluation on a testbed with the goal to answer the question whether route changes due to traffic engineering will have an adverse impact on the TCP flows and severely reduce the network performance. The detailed evaluation will be presented in the chapter 6. However, jumping forward, we can affirm that it is safe to reroute the flows as long as this action is not performed "too frequently".

Scalability of centralized management

SDN looks very promising in theory. Nevertheless, the first commercial implementation, OpenFlow had lots of drawbacks. One of them, which we rapidly mentioned in the previous section, is due to relying too much on the centralized controller.

Limited performance of the SDN controller was one of the issues that we faced in a testbed environment during preliminary tests. Although Open vSwitch software may achieve satisfactory switching rates, bursty traffic may drain the controller's resources and make it a network bottleneck even in small systems. Considering the time required to parse incoming packet_in OpenFlow message, calculate efficient path and push flow information to all intermediate flow tables, particular care should be taken to prevent improper handling of network streams.

Studies have shown that the latency induced by the control plan can have a significant impact on the SDN performance. For example, the delay needed to update a rule in the switches can be as high as 30ms [START_REF] He | Measuring Control Plane Latency in SDN-enabled Switches[END_REF]. The well-known Google's WAN network, B4, had an outage due to the incapacity of the SDN switches to process the high number of incoming flow modification messages at a sufficient rate [START_REF]Lessons learned from B4, Google's SDN WAN[END_REF].

Control traffic overhead

An essential requirement of traffic-engineering comprises the ability to gather information about the state of the network and to configure the behavior of network elements to route traffic flows accordingly. This information has to be exchanged between network devices or, in the case of SDN, transferred to a centralized network controller. This control traffic may induce a major overhead. In this section, we discuss the trade-offs between the amount of control traffic and the usefulness of the information.

CHAPTER 2. POSITIONING AND RELATED WORKS ON ENERGY EFFICIENCY AND TRAFFIC ENGINEERING IN BACKBONE NETWORKS

Gathering information about the state of the network

We are aware of the following approaches when it comes to gathering information about the network state:

• Traffic agnostic: the network traffic is not taken into consideration at all.

• Based on link utilization: the solution relies on knowing the utilization of each link.

• Relying on the traffic matrix (origin-destination flows): only the information about the accumulated bandwidth flowing from an ingress device towards each egress device is transmitted.

• Based on (micro-)flows: the throughput of each TCP/UDP flow is communicated to the SDN controller.

Each next level increases the management overhead but also enables more fine-grained optimization. Leaving aside the traffic agnostic solutions, the research community still does not agree on which approach is better [START_REF] Kamola | Shortest path green routing and the importance of traffic matrix knowledge[END_REF]. Some authors prefer to gather the link utilization and run complex algorithms to reconstruct traffic matrices instead of directly collecting the traffic matrix [START_REF] Zhang | GreenTE: Power-aware traffic engineering[END_REF][80], even though traffic matrix estimation was proven inefficient [START_REF] Gunnar | Traffic Matrix Estimation on a Large IP Backbone: A Comparison on Real Data[END_REF]. On the other hand, some production backbone networks are comfortably relying on OpenFlow-based micro-flow statistics [START_REF] Hong | Achieving High Utilization with Softwaredriven WAN[END_REF] [START_REF] Jain | B4: Experience with a Globallydeployed Software Defined Wan[END_REF].

We believe that micro-flow based statistic will not scale to the number of TCP/UDP flows traversing a backbone network. In the remaining part of this section, we estimate the control traffic overhead of solutions relying on traffic matrices to decide if it is a viable approach for our solutions.

In theory, the quantity of control traffic needed to update the origin-destination traffic matrix fully increases quadratically with the number of network devices: each ingress device must inform the SDN controller about how much data is originated towards every other (egress) devices. In practice, this behavior is confirmed in the current generation of SDN controllers, which adopt a polling strategy for statistics collection.

To provide a realistic estimation of the bandwidth needed, we tested the solution on a testbed network with the ONOS network controller. The tests showed that, on average, 122bytes were used by the OpenFlow protocol per flow to inform the controller of an update in the flow's demand. Knowing that there are exactly n ¨pn ´1q origindestination flows in a network, we obtain the estimations from Table 2 Given these results, we can affirm that, in a reasonably sized backbone network with 100 nodes, it is possible to maintain a fresh view of the network traffic matrix effortlessly even with any currently available SDN protocols. Moreover, in real-world networks, traffic entering the network does not usually change unexpectedly. A vast improvement is possible by assuming a temporal stability of the flows. Asynchronous notifications can 2.5. THE SPRING PROTOCOL be used to inform the controller only about changes in flow sizes at the cost of having a slightly less accurate view of the network traffic [START_REF] Yu | FlowSense: Monitoring Network Utilization with Zero Measurement Cost[END_REF].

Configuring network routes

SDN-based solutions proposed in literature frequently use explicit network paths for each origin-destination flow. A large number of forwarding rules which have to be transmitted from the network controller to the SDN switches may generate a lot of control traffic. Moreover, it can amplify the problem of the centralized management presented in the previous section.

We consider that a good solution must be somewhere in between the shortest path routing and explicit routing. Instead of sending explicit paths, the controller should send a small amount of meta information, allowing switches to rebuild the network paths locally as computed by the controller and to update their forwarding tables locally in batches.

To achieve this goal, our work uses a novel SDN-friendly source routing protocol: SPRING, which was initially introduced by Cisco in 2015 under the name of "Segment Routing". We present this protocol in the next section.

The SPRING protocol

Source Packet Routing In NetworkinG (SPRING) [START_REF] Filsfils | Segment Routing Architecture[END_REF] is an IETF draft protocol at the final stage of standardization is already implemented in the Linux kernel [START_REF]IPv6 segment routing in linux kernel[END_REF]. It was initially introduced by Cisco under the name of Segment Routing and is known under the latter name. We prefer however to adhere to the official IETF name in this work.

As presented by the creator itself [START_REF]Cisco Segment Routing Overview with Clarence Filsfils[END_REF], the SPRING protocol was inspired by the work done by Google [START_REF] Jain | B4: Experience with a Globallydeployed Software Defined Wan[END_REF] and Microsoft [START_REF] Hong | Achieving High Utilization with Softwaredriven WAN[END_REF] and was designed as a SDN-ready protocol for Wide Area Network (WAN) networks. Instead of taking the path of OpenFlow, which heavily relies on the centralized network controller for a normal operation, SPRING tries to combine the best of two worlds: traditionally distributed control plane and centralized SDN.

The goal was to create a robust SDN-ready protocol, which does not rely on a centralized control plane for the most critical network function: packet forwarding. It is however designed to build on SDN for Traffic Engineering, and other Operations, Administration and Management (OAM) features. As a result, in the case of a failure in the SDN control plane, SPRING will still be able to operate the network with some QoS degradation.

SPRING keeps the traditional well-tested IGP (OSPF/IS-IS) control plane while replacing other complex and error-prone protocols. For example, traffic engineering, computation of fast reroute backup paths, network monitoring, and other network functions are exported to the centralized SDN controller. To facilitate the centralized management, SPRING relies on the source routing paradigm.

The data plane used by SPRING utilizes the same concept of label switching of MPLS, but its control plane has been completely redesigned. The distribution of labels is done via an extension to the IGP instead of using specific protocols such as LDP/RSVP-TE. Moreover, unlike MPLS, labels, called Segment IDentifiers (SID) in SPRING, have a global scope. In the present work, we are interested in two types of SIDs, namely "nodal" and "adjacency" as shown in Figure 2.10a.

• A nodal SID is globally unique and identifies a node (a,b,c,...,h).

• An adjacency SID is local to a node and identifies an outgoing interface (node b has the adjacency SIDs L1,L2,L3,L4 and L5).

After network discovery, sending a packet to node a through the shortest path requires encapsulating it into a packet with destination a. Unlike in IP, much more flexible traffic engineering is possible:

• If node h wants to send a packet to node a while forcing it over link L1, it adds the header rb,L1s (Figure 2.10b).

• If h wants to send a packet to a via f (Figure 2.10c), it uses the header rf,as.

Being a source routing protocol, SPRING enables fast flow setup and easy reconfiguration of virtual circuits with minimum overhead since changes must be applied only to the ingress devices. No time and signalling are lost re-configuring the midpoint devices.The policy state is in the packet header and is completely virtualized away from midpoints along the path. This means that a new flow may be created in the network by contacting only one network device: the ingress router.

This agility and atomicity of flow paths updates is essential in solutions that intend to perform link switch-off and improve energy efficiency. This comes in contrast with Open-Flow where the forwarding tables of all the devices along the path must be reconfigured. As already mentioned earlier, the need to synchronize the flow rule updates created a lot of problems for the research community and even was one of the causes that provoked an outage in the Google's SDN backbone network.

Following all this analysis, we decide to rely on the SPRING protocol for our traffic engineering, as it respects better the requirements for designing an SDN-based solution that is presented in the current section.

CONCLUSION

Conclusion

In this chapter, we have introduced the context of backbone networks. We did a quick overview of the architectures which are currently deployed in operator infrastructures. In particular, we compared the IPoOTN and IPoWDM architectures and motivated our choice to concentrate our research on the latter: we believe that it is better suited to route modern traffic, which is predominantly packet-based.

The number of research papers that try to reduce the energy consumption of IPoWDM networks has recently exploded in number. We sought to present the panorama of works in this field, both at the network design phase and the network operation phase. Evidence shows that the best way to reduce the energy consumption of such network is to manage the traffic intelligently in the packet layer; a technique known in the literature as "energy efficient traffic engineering"

We continued by presenting the existing traffic engineering techniques and the state of art works which apply these techniques to the problem of reducing the energy consumption of computer networks. This allowed us to conclude that there is a need in a online, reactive, framework with low computational overhead.

We finished the chapter with a discussion on the challenges which may define the design of such a framework. We concluded that a good SDN-based traffic engineering solution must avoid sending explicit paths to the SDN switches. Combining a centralized optimization with a local update of network paths can drastically reduce the amount of control traffic passing through the network. As a way to achieve this goal, we proposed to use the Source Packet Routing In NetworkinG (SPRING) protocol, which allows to change the paths of flows by atomically changing a single forwarding entry on the ingress network device.

Chapter 3 Theoretical background

In the previous chapter, we introduced the context of IPoWDM backbone networks and presented the multiple ways used to reduce their energy consumption. In particular, we are interested in solving this problem via intelligent traffic engineering in the IP layer.

In this chapter, we provide the necessary theoretical background on which we base our work. We first introduce the classical way to model an IP layer of a communication network via graph theory. After that, we provide a brief introduction to the linear programming. Armed with these basics, we dig a deeper into the theory of the maximum concurrent flow problem and introduce theoretical results that enable efficient algorithms for centralized traffic management.

Graphs 101: model of a communication network

This section introduces the formal notations used throughout this work. Consider the communication network from Fig. 3.1a. In this thesis, we model this network as a connected directed graph GpV,Eq (Fig. 3.1b). The following notation is used:

• Each network device corresponds to a vertex v P V " ta, b, cu.

• Each link represents a (directed) edge e P E: pa,bq, pb,aq, pa,cq, pc,aq, pb,cq, pc,bq. We frequently use the short notation ab to refer to the edge pa,bq going from node a towards node b.

CHAPTER 3. THEORETICAL BACKGROUND

• A function c : E Ñ R `represents the capacities of the edges, i.e. the link speed.

• A function l : E Ñ R `represents the length (cost) of the edge.

• The traffic entering the network at the source node i P V and flowing toward the egress destination node j P V is defined as the demand d i,j ě 0. We assume that there is no traffic from a node to itself, i.e. @v P V, d v,v " 0.

• A path P " pe 1 , e 2 , ...q is a sequence of edges such that (e i " ab and e i`1 " xyq ñ b " x). The length of a path P " pe 1 , e 2 , ...q is the sum of the lengths of the edges in the path: lpP q " ř ePP lpeq. (in Fig. 3.1b, the two dashed lines show 2 paths between a and b).

• A shortest path SP i,j from the node i to node j is a path such that there is no other path P between i and j with lpP q ă lpSP i,j q. In Fig. 3.1, the path P 1 " pac, cbq is the shortest path between a and b under the given length function l, because lpP 1 q " lpacq `lpcbq " 2 ă 4 " lpabq.

• We introduce the notation P i,j : the set of all the paths between nodes i and j in G. Let P " Y pi,jqPV 2 :i‰j P i,j be the set of all the paths in the network. Note that, by definition, P also contains the paths with cycles. To simplify the examples in the forthcoming sections, we do not consider these paths, as they do not influence the result and are avoided during the execution of the algorithms based on shortest path computations.

Linear Programming 101

This section is intended to help the readers with no Linear Programming background to grasp basic notions and go through the rest of this thesis more handily. For the ones that already have such background, you can skip this section. For a much more in-depth overview of the Linear Programming and the proof of the properties presented in this chapter, the reader can relate to the book [START_REF] Bradley | Applied Mathematical Programming[END_REF], which served as a basis for our summary.

It is freely available online1 . Linear programming is a method for the optimization of linear objective functions subject to linear equality and inequality constraints. This technique can be used to model and solve a lot of optimization problems: which try to find the best possible allocation of limited resources while respecting a set of constraints. The objective and the constraints are defined by the nature of the problem being solved.

An elementary linear program is shown in Fig. 3.2. In this example, each dotted line represents a constraint expressed as an equality. The gray regions next to these lines indicate the directions of the inequality constraint. The shaded square area represents geometrically all the values of the variables x1 and x2 that simultaneously satisfy all the inequality constraints. Among the feasible solutions, the goal is to find the values of the variables x 1 and x 2 that maximize the objective function represented by the bold black lines. The sub-optimal solution is p5.15, 1.2q and the optimal solution is p5.6,1.2q.

LINEAR PROGRAMMING 101

Maximize 2 ¨x1 `1 ¨x2 under the constraints: Any point that is not within the feasible region violates at least one of the constraints of the problem. For example, this is the case for the point represented by a triangle. It respects all the inequalities except the third one: ´2 ¨4.5 `7 ¨1.6 " 2.2 ę 0.

3 ¨x1 ´4 ¨x2 ď 12 ´1 ¨x1 ´2 ¨x2 ď ´7 ´2 ¨x1 `7 ¨x2 ď 0 6 ¨x1 `7 ¨x2 ď 42 x 1 ě 0 x 2 ě 0 0 0.5 1
The previous linear program can also be represented in a matrix form tc

T x|Ax ď b, x ě 0u: max $ ' ' ' ' ' ' & ' ' ' ' ' ' % `2 1 cT ˆx1 x 2 ẋ ˇˇˇˇ¨3 ´4 ´1 ´2 ´2 7 6 7 ‹ ‹ ' A ˆx1 x 2 ẋ ď ¨12 ´7 0 42 ‹ ‹ ' b , ˆx1 x 2 ẋ ě ˆ0 0 0 , / / / / / / . / / / / / / -
An important property of the Linear Programming is the duality. For any maximization linear program presented in the form maxtc T x|Ax ď b, x ě 0u, we can formulate a corresponding minimization problem mintb T y|A T y ě c, y ě 0u, called the dual problem. The initial problem is called primal.

In matrix form, the dual problem will be represented as follows:

min $ ' ' ' ' ' ' & ' ' ' ' ' ' % `12 ´7 0 42 bT ¨y1 y 2 y 3 y 4 ‹ ‹ ' y ˇˇˇˇˆ3 ´1 ´2 6 ´4 ´2 7 7 ȦT ¨y1 y 2 y 3 y 4 ‹ ‹ ' y ě ˆ2 1 ċ , ¨y1 y 2 y 3 y 4 ‹ ‹ ' y ě ¨0 0 0 0 ‹ ‹ ' 0 , / / / / / / . / / / / / / -
This notation makes it easier to observe that each variable of the dual corresponds to a constraint in the primal.

One of the fundamental duality properties is referred to as "weak duality" and provides a bound on the optimal value of the objective function of either the primal or the dual. The value of the objective function for any feasible solution to the primal maximization problem is bounded from above by the value of the objective function for any feasible solution to its dual minimization problem. Similarly, the objective function CHAPTER 3. THEORETICAL BACKGROUND of the dual problem is always greater than the value of the objective of the primal. Furthermore, in a case when the linear program is feasible and has an optimal solution, we have: Strong Duality Property. If the primal (dual) problem has a finite optimal solution, so does the dual (primal) problem, and these two values are equal. That is, if we denote by x ˚the optimal primal solution and by y ˚the optimal dual solution, we have:

c T x ˚" b T y
The importance of this property is that it indicates that we may, in fact, solve the dual problem in place of (or in conjunction with) the primal problem. A solution which we show in a future chapter does indeed use this property to construct the primal problem jointly with the dual.

A linear program in which some variables are restricted to be integers is called Mixed-Integer Linear Programming (MILP). The integrality constraints allow the model to capture the discrete nature of the decisions. For example, a variable whose values are restricted to 0 or 1, called a binary variable, can be used to decide whether or not some action is taken. Unfortunately, the introduction of the integer variables makes the problem NP-hard.

In the next section, we study a real problem modeled in a linear program. In particular, we provide the classical edge-path modeling of the maximum concurrent flow problem.

The maximum concurrent flow problem

Flow problems are at the core of many optimization problems in the field of computer networks.

A special case of a flow problem is the maximum concurrent flow problem. It takes a graph GpV,Eq as an input, together with k different pairs of vertexes ps i ,t i q P V 2 ,0 ď i ă k. Each pair i has an associated demand d s i ,t i . The goal is to maximize the total flow in the graph while respecting: i) the edge capacities given by a function c : E Ñ R `; and ii) the constraint that the ratio of the flow supplied between a pair of vertexes to their demand must be the same for all k pairs. The latest constraint ensures that the demands of all pairs are satisfied in equal proportion. No pair is "starving" because other pairs consumed all the bandwidth.

In the forthcoming sections we'll provide a step by step construction of the edgepath Linear Program model of the maximum concurrent flow problem. This will allow to illustrate and better understand the reasoning which should be used to formulate a simple real-world problem into a mathematical linear programming model. Afterwards, we'll quickly introduce the dual of the LP and the node-arc formulation of the primal. In parallel, we present the fundamental properties used in the chapter 5 of this thesis. The operator wants to find how much more traffic can be theoretically absorbed into the network before having to replace the network devices with faster, more expensive and more power hungry ones. It assumes that all demands will increase at comparable rate. For example: if d a,b doubles to 18Gbps, d a,c will also double to 2Gbps.

Constructing the edge-path LP formulation

To find the solution, we use the following objective: maximize λ ¨9Gbps `λ ¨1Gbps = maximize λ ¨10Gbps = maximize λ [2 ] thus represents the traffic growth rate.

One can see that the only two possible ways to transport the data from node a to node b is by passing through the paths P 1 " tac,cbu and P 2 " tabu. We ignore the paths containing cycles as, for example: tac,ca,abu.

Let f a,b pP 1 q be the fraction of the demand λ ¨9Gbps passing through the path P 1 . By construction: f a,b pP 1 q `fa,b pP 2 q " λ ¨9Gbps. The same for the demand from a to c: f a,c pP 3 q `fa,c pP 4 q " λ ¨1Gbps.

The notation f a,b pP 1 q is redundant as the path P 1 is known to start at node a and to end at node b. We therefore use a condensed notation f pP 1 q. The previous equations can be rewritten as Demand constraints:

f pP 1 q `f pP 2 q ´9λ " 0 `f pP 3 q `f pP 4 q ´1λ " 0 (3.1)
Also, the flows passing through a link must be smaller than the capacity of this link. As a result, we have the following Capacity constraints:

f pP 1 q `f pP 4 q ď cpacq `f pP 2 q `f pP 3 q ď cpabq f pP 1 q ď cpcbq `f pP 3 q ď cpbcq (3.2)
Finally, the amount of data passing through a path cannot be negative. Flow nonnegativity constraints:

CHAPTER 3. THEORETICAL BACKGROUND f pP 1 q ě 0 f pP 2 q ě 0 f pP 3 q ě 0 f pP 4 q ě 0 (3.3)
These equations can be written in a condensed form:

Maximize: λ Subject to constraints: from 3.1 : ÿ

P PP i,j
f pP q " λ ¨di,j @pi,jq P V 2 : d i,j ą 0 from 3.2 : ÿ P PP:ePP f pP q ď cpeq @e P E from 3.3 : f pP q ě 0 @P P P

(3.4)
The problem solved by the Linear Program 3.4 is known by the name of Maximum Concurrent Flow Problem (MCFP). In the following, we refer to any valid solution λ as "concurrent flow of throughput λ". We use the notation λ ˚to designate the optimal solution to this problem.

The node-arc LP formulation

The edge-path linear programming formulation of the maximum concurrent flow problem is beneficial due to the relation between the primal and the dual, which we present in the next section. Moreover, it is better suited for use in conjunction with the method of column generation [START_REF] Wilhelm | A Technical Review of Column Generation in Integer Programming[END_REF] for solving the maximum concurrent flow problem: the general idea is to start with solving a linear program using a limited subset of network paths. After that, the variables of the dual are used to find a new path that could improve the solutions, which is then added to the initial paths in the primal and the solver re-iterates to search another path.

On the other hand, when searching for an optimal solution, the edge-path formulation is not the best one, because the number of paths in the network (the number of primal variables) can potentially be exponential in the network size. The node-arc formulation is preferrable. The following variables are used:

V set of nodes E
set of edges cpeq capacity of the edge e P E f i,j e ě 0 flow from node i P V to node j P V on link e P E w v set of outgoing links from the node v P V w v set of inbound links towards the node v P V

The model objective is still to maximize: λ Subject to the following constraints: i) Flow conservation constraints. These constraints algebraically state that the sum of the flow through arcs directed toward a node plus that node's supply, if any, equals the 3.3. THE MAXIMUM CONCURRENT FLOW PROBLEM sum of the flow through arcs directed away from that node plus that node's demand if any.

ÿ ePw v f i,j e ´ÿ ePw v f i,j e " $ ' & ' % ´λ ¨di,j , if v " i λ ¨di,j , if v " j 0, otherwise @v P V, @pi,jq P V 2 : d i,j ą 0 (3.5)
ii) Edge capacity constraints. The total flow passing through a link must be smaller than its capacity.

ÿ pi,jqPV 2 :d i,j ą0 f i,j e ď cpeq @e P E (3.6)
All the models used for validating our heuristics are based on this node-arc LP formulation.

Properties of the edge-path LP formulation

The edge-path formulation allows proving a set of useful properties, which will be used in this thesis. The first property is introduced by the authors of [START_REF] Shahrokhi | The Maximum Concurrent Flow Problem[END_REF] under the name "distance(length) upper bound". It affirms that, for any lengths assigned to the links, the ratio ř ePE lpeqcpeq ř pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j provides an upper bound for the maximum concurrent flow λ.

Formally, it is defined as follows: Furthermore, the length of a shortest path between a source node i and a destination node j is, by definition, shorter or equal to the length of any other path between these nodes, i.e.: @P P P i,j , lpP q ě lpSP i,j q. As a result:

ÿ P PP lpP qf pP q ě ÿ pi,jqPV 2 :d i,j ą0 plpSP i,j q ÿ P PP i,j f pP qq " " ÿ pi,jqPV 2 :d i,j ą0 lpSP i,j qλd i,j " "λ ÿ pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j (3.8)
From equations 3.7 3.8, and under the assumption that ř pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j ‰ 0,

we prove the claim.

The previous results can be applied to the particular case of an optimal maximum concurrent flow λ ˚:

ř ePE lpeqcpeq ř pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j ě λ ˚(3.9)

The dual of the edge-path LP and its properties

The dual of 3.4 has a variable zpi,jq for each demand constraint (3.1) and a variable lpeq for each capacity constraint (3.2) and is defined as follows:

Minimize: ÿ ePE lpeqcpeq Subject to constraints: ÿ ePP lpeq ě zpi,jq @pi,jq P V 2 : d i,j ą 0; @P P P i,j ÿ pi,jqPV 2 :d i,j ą0 zpi,jqd i,j ě 1

lpeq ě 0 e P E (3.10) Lemma 3.3.2.
Setting zpi,jq equal to the length of the shortest path between i and j under the length function l, i.e. zpi,jq Ð lpSP i,j q, neither changes the cost nor impacts the feasibility of the LP.

Proof. The first group of constraints forces each zpi,jq to be at most equal to the length of the shortest path between i and j. In any valid solution to the LP 3.10, if some zpi,jq is strictly smaller than lpSP i,j q, we can safely increase it without invalidating the constraint ř pi,jqPV 2 :d i,j ą0 zpi,jqd i,j ě 1 or changing the objective value. Proof. The first inequality is a direct application of the constraint ř pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j ě 1 of the LP 3.11. The second inequality is a direct application of the strong duality theorem on Equation 3.9 from the previous section.

Conclusion

This chapter rapidly introduces the theoretical background of this thesis. Our primary goal was to present the "maximum concurrent flow problem", a problem which received extensive attention from the academic research community. One of these works [START_REF] Karakostas | Faster Approximation Schemes for Fractional Multicommodity Flow Problems[END_REF] presented an efficient algorithm, which is adapted to our needs in Chapter 5.

We also highlight the importance of Equation 3.12 which provides an upper bound to the dual optimization objective. It is at the core of various algorithms for approximately solving the maximum concurrent flow problem, including our work.

Chapter 4

Consume Less: the STREETE framework for reducing the network over-provisioning

In this chapter, we present the SegmenT Routing based Energy Efficient Traffic Engineering (STREETE) framework, an online SDN-based method for switching links off/on dynamically according to the network load. To react quickly to traffic fluctuations in operators' core networks, we trade off optimality for speed and create a solution that relies entirely on dynamic shortest paths to achieve very fast computational times.

One of the main contribution of this chapter is the ability to react very fast in order to awake sleeping links. The literature has thus far mostly overlooked the problem of turning links on assuming that the traffic varies slowly in backbone networks due to the high aggregation level. Nevertheless, unexpected burst still happen and must be rapidly assimilated by the network. For example, the real traffic matrices which we use for validation on the Germany50 network contain such a sudden burst of traffic volume.

This chapter starts by giving a high-level overview of our framework, and then details the implemented algorithms. It then presents the methodology and the techniques used to evaluate the proposed solution. In particular, we provide a quick overview of network topologies; the software used for evaluation; the analyzed metrics; and the results obtained by simulation. We highlight the observed strengths and limits of STREETE, thus making a transition towards the next chapter, which presents a mean to make STREETE work under extremely high network load at the expense of increased complexity.

A large part of this chapter also presents the Software-Defined Network (SDN) testbed built for experimental evaluations and discusses on the problems revealed by the experimental evaluation.

General overview

At an abstract level, the SegmenT Routing based Energy Efficient Traffic Engineering (STREETE) framework works as follows:

• All ingress devices inform the network controller of their demand towards each egress node. That way, the controller maintains an up-to date network-wide traffic • The controller, which has an up-to-date and global view of the network topology and the traffic matrix, executes an algorithm to determine the network links that must be turned on or off.

• The controller sends the previously computed information to the SDN switches.

• The switches locally recompute the new routes to avoid the links which are off and update their forwarding tables.

The algorithm that the controller runs continuously simulates the routing of the latest network traffic matrix while trying to detect network under-utilization and/or highly utilized links. Under-utilization offers a chance to reduce the energy consumption by turning links off. Hence, the algorithm performs an in-memory simulation of turning the candidate links off and estimating the impact of such a decision, without actually turning them off in the physical network. Whenever the result of the simulation shows that it is possible to turn a link off without creating congestion, it is scheduled for switch off. Afterwards, the algorithm re-iterates to, potentially, turn-off other links. On the other hand, under high link utilization an imminent congestion is assumed and the algorithm acts in the same way to turn-on network links and solve the congestion if possible.

While the solution is conceptually simple and corresponds to a greedy, "generate and test", solution, it includes a couple of important optimizations that improve the performance and the quality of the final solution. The rest of this section presents the optimizations included into STREETE.

Provide an order for the greedy algorithm. The algorithm keeps two different views of the network: i) the current network view, with some links being off ; and ii) the full network topology, where all the links are assumed active. The second view allows guiding the construction of the solution by providing an order for the greedy algorithm.

Using a fully active view of the network provides useful metrics for the algorithm. This is especially important for turning links on. Compared to the phase of switch off, it is much more difficult to correctly select a good subset of links to turn on that can solve congestion. It may occur that the best candidate link is far from the place of congestion. It is also usual to have to turn-on more than one link for this purpose.

For the phase of turning off, providing an order to the execution is less important. Simple local heuristics generally lead to good results [START_REF] Kamola | Shortest path green routing and the importance of traffic matrix knowledge[END_REF]. Nevertheless, our double view of the network is still beneficial by avoiding chaining of link extinction. This case will be detailed latter in the current section.

The intuition behind the method that we propose is depicted in Figure 4.1. Starting from the network view with links being turned off (Figure 4.1a), the algorithm uses the traffic matrix to find the highly loaded links (Figure 4.1d). In the meantime, the demands from the traffic matrix are simulated being routed into the full network topology (Figure 4.1b). This action allows to sort the links in the decreasing order of their estimated utilization in the fully active network. Figure 4.1e illustrates the result of this computation where the thickness of the links represents their relatively high utilization compared to other links. The previous action enables defining the order in which the links will be turned on until, if possible, the congestion is resolved. For example, in Figure 4.1f, the link ab is selected as the best candidate for turn on because it is off, but it would transfer a lot of data in the all-on network.

Reduce the control traffic overhead. The algorithm executed by the SDN controller relies entirely on shortest path computations. This particularity allows to keep the communication overhead as low as possible because the SDN controller does not need to send explicit routes to the SDN switches. After receiving instructions from the controller, each network device locally computes the routes by using the same constrained shortest path algorithm as in the controller and naturally avoids disabled links. The only information which has to be sent from the SDN controller to the switches contains the state of all the links in the network: on/off. Moreover, there is no need to coordinate the updates between devices to avoid transient network loops. This problem is avoided by relying on the Source Packet Routing In NetworkinG (SPRING) protocol presented in a previous chapter.

Fast computations. To considerably reduce the computational overhead in the SDN controller, our solution relies on dynamic shortest path algorithms. The general idea is to partially update the shortest paths between the steps of the algorithm instead of computing a solution from scratch. We'll present one of the used dynamic shortest path algorithms in the section 4.2.4 of the present chapter.

Reduce the impact of historical decisions. As mentioned earlier, the two views of the network also reduce the influence of the historical decisions on the execution of the algorithm for the phase of extinction. This allows to avoid chains of turned-off links.

To provide an example on why a historical decision may have a negative impact on the final solution, we consider an algorithm from a related work [START_REF] Bianzino | Distributed algorithms for green IP networks[END_REF], which works as follows: "while there are no highly utilized links in the network, turn-off the least loaded link ". After doing some preliminary tests, we observed that this chain of events generates unnecessarily long routes in the network. In contrast, STREETE computes the order of extinction based on the all-on topology. This way, we ensure that the algorithm is not impacted by the actual state of links in the network.

Avoid route oscillations. The STREETE framework also incorporates a technique of double thresholds to avoid oscillations in the state of network links as a result of small traffic variations. In particular, it turns on a link only if this action reduces the utilization of any link which is used at more than a threshold α. At the same time, a link is turned off only if this action does not increase the utilization of any link beyond another threshold β. These thresholds can be modified at will in seek for a balance between the conservativeness and the energy efficiency of the algorithm. In this work we fix them to α " 0.8 and β " 0.6. STREETE will though try to maintain the utilization of links between 60% and 80%, avoiding to load the links dangerously close to congestion.

Algorithms

In this section, we present the details of the algorithms executed by the SDN controller.

Notations

To facilitate the formal description, we use a few custom notations besides the classical graph notations introduced in the previous chapter. For instance, we use the notation G for the initial network topology with all the links being on, and G 1 for referring to the modified topology, with a subset of links switched off : V

1 " V and E 1 Ă E. An example of G and G

1 can be seen in Figure 4.1a and 4.1b respectively. We use the symbols α and β for referring to the two thresholds which trigger turning links on and, respectively, off.

Based on these thresholds, for a given network G and a traffic matrix T M, we define the set of links at critical load CL G,T M " te P G | u G,T M peq ą αu. It contains the links with utilisation higher than α in G. For example, if α " 0.8, CL G 1 will contain the links 4.2. ALGORITHMS with utilization greater than 80%. Hereafter we refer to links in CL as "links close to congestion". In our example, Figure 4.1d, CL G 1 ,T M " tih, hf u.

Respectively, we use ML G,T M " te P G | u G,T M peq ą βu for referring to links at load more than β. The turn-off phase will avoid creating such links. To be noted that ML G,T M Ě CL G,T M .

Initialization and main loop

The following steps must be computed only once, at the initialization of the framework.

• Pre-computing a spanning tree. To avoid disconnecting the network, the minimum spanning tree in terms of delay is pre-computed using Prim's MST algorithm. The links on the spanning tree are never turned off.

• Pre-computing the shortest paths. Dijkstra algorithm is used to compute the |V | shortest path trees in the network.

The choice to never turn-off the links located on the minimum spanning tree may be criticized, because some links can remain enabled without being used to route network traffic. However, in the context of backbone networks, with aggregated network traffic the probability of this to happen is low. Fixing an always active spanning tree allows to keep the network connected for management purposes. Moreover, it may even be interesting to use graph spanners [START_REF] Peleg | Graph spanners[END_REF] instead of spanning trees to guarantee that no unnecessarily long paths are created in the network as a result of turning links off. A t-spanner of a graph G is a subgraph in which the distance between any two nodes is at most t times longer than the distance between the same nodes in G. Such a solution for grid networks was proposed in a related work [START_REF] Giroire | Grid spanners with low forwarding index for energy efficient networks[END_REF].

The main execution loop is self-explanatory (Alg. 1). It consists of an infinite loop which will periodically call STREETE-ON to find links which must be turned on and apply the change into the in-memory graph structure G 1 , followed by STREETE-OFF to find the links which must be turned off. The state of links will afterwards be sent to the network devices. Note that the algorithm can, in fact, shut down some links while turning on others. This happens when the load is increased in one part of the network while being reduced in another.

Algorithm 1 Main loop

STREETE-ON(G, G

1 , T M)

3: STREETE-OFF(G, G 1 , T M) 4:
SendToDevices(StateOfLinks(G 1 ))

5: end while

The following section presents the details of STREETE-ON. We do not enter into the details of STREETE-OFF, as its behavior is exactly the same as the turn-on, with the difference that links will be sorted in the ascending order of their utilization.

STREETE-ON

Algorithm 2 STREETE-ON 1: procedure STREETE-ON(G, G 1 , T M) 2:
result Ð H

3: candidateLinks Ð EzE 1 4: congested Ð CL G 1 ,T M 5:
changed Ð true 6:

while congested ‰ H and changed " true do 7:

changed Ð f alse

8:
for all e P sortedpcandidateLinks,u G,T M q do 9:

Ź sorted in descending order of utilisation in G 10:

if congested ‰ H then

11: return result 25: end procedure

E 1 Ð E 1 Y
We mentioned in a previous section that our greedy heuristic first tries to turn-on the links which are off in the energy-optimised network G

1 , but would have a high utilisation in G. This action is performed by Algorithm 2 at lines 3 and 8. We prioritise turning on the links that would create shortcuts for large flows.

At lines 11-12 the algorithm simulates turning the link on and estimates the congestion after this operation. At lines 13-20 it tests if congestion decreases. If so, the link is scheduled to be turned on in the physical network; otherwise the link is disregarded.

"congestion decreased" at line 13 is defined as:

• solving all the congestion

• or decreasing the utilization of any congested link while avoiding both i) to create new congested links and ii) to increase the utilization of any congested link.

Sometimes a set of links must be turned on to avoid congestion. The while loop at line 6 ensures that the algorithm is repeated until the congestion is resolved or it becomes impossible to solve without creating another congestion.

The previously presented algorithm hides a complex operation when accessing CL at lines 4 and 12, namely estimating the load of links to find the congested ones. To 4.2. ALGORITHMS estimate the load of the link, we must simulate the routing in the network by first finding the shortest paths and, afterwards, simulating the demands flowing through the network. The next section presents how we use dynamic shortest path algorithms to reduce the complexity of the first step. However, for the second step, it is also possible to achieve an Op|V |q complexity for routing all the |V|-1 flows from a common source. As this is not trivially intuitive, the algorithm 3 presents a way to achieve such a running time.

Algorithm 3 Compute how much data passes through the links of the spanning tree T rooted at node v root if the demands d vroot,˚, ˚P V are routed into the tree

1: function RouteInTree(T pV, E T q, v root P V, d vroot,˚) 2: sortedV Ð SortTreeNodes(T , v root ) 3: initialize f v Ð 0, @v P V 4: for i Ð |V | ´1; i ą 0; i Ð i ´1 do 5: v Ð sortedV ris 6:
find pu,vq P E T Ź Find the unique parent node u of v 7:

f v Ð f v `dvroot,v 8: f u Ð f u `fv 9:
f pu,vq " f v 10:

end for 11:

return f p˚,˚q " tf pu,vq : uv P E T u 12: end function

The main idea relies on the fact that, in a directed tree, the traffic crossing a link pu,vq can be recursively defined as the sum of i) the traffic going to the destination endpoint v; plus 2) the traffic flowing through the links tpv,˚q|˚P V u Ă E T outgoing from v. The algorithm can be imagined as starting with the leaf nodes, which have no outgoing traffic. Afterwards, the algorithm climbs into the tree and computes the flow on each link using the previously mentioned recursive relation.

Algorithm 4

Topologically sort the nodes of the (directed) tree T starting from the root node v root . Returns the ordered list of nodes.

1: function SortTreeNodes(T pV,E T q, v root P V ) 2:
sorted " rv root s Ź List of nodes with one element pvrootq 3: To achieve that, the algorithm proceeds in two phases. First, the tree is topologically sorted, i.e. the nodes are ordered such that there is no link going from a node towards any of its predecessors. This is easy to achieve in a tree and consists in traversing it starting CHAPTER 4. CONSUME LESS: THE STREETE FRAMEWORK FOR REDUCING THE NETWORK OVER-PROVISIONING from the root node, as shown in Algorithm 4. The algorithm 3 afterwards traverses the sorted nodes in decreasing order (lines 4-10). This order ensures that, when a node is encountered, the flow passing through all its children was already computed.

i " 0 Ź Index in

Dynamic shortest paths

A naive approach for recomputing the shortest paths uses n static Dijkstra computations. As we want our algorithm to react fast to network congestion, we used an optimised Dynamic All-Pairs Shortest Path (DAPSP) algorithm proposed in the literature [START_REF] Demetrescu | Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms[END_REF]. It is designed to execute only partial re-computation of the shortest paths in case of edge insertion/deletion. We use D-RRL, a slightly modified version of the algorithm initially proposed in [START_REF] Ramalingam | An Incremental Algorithm for a Generalization of the Shortest-path Problem[END_REF]. The worst case theoretical complexity of this algorithm is the same as static Dijkstra computations. It is higher than the complexities of its competitors [START_REF] Demetrescu | Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms[END_REF]. Nevertheless, aside the fact that it is the easiest to implement, this algorithm also happens to have the best performance on almost planar graphs which are encountered in computer networks.

Algorithm 5 Update the shortest path tree T to maintain the shortest paths from the root node v root towards all the other nodes after the insertion of a new edge e G 1 into the graph G

1 1: procedure D-RRL-addEdge(G 1 pV, E G 1 q, T pV,E T q, v root P V, e P E G 1 ) 2:
pu, vq Ð e Ź Get the extremities of the edge in G 1

3:

if v " v root then initialize distpwq Ð lpv root , wq, @w P V 10:

initialize pq Ð P riorityQueuepq end while 24: end procedure

EVALUATION BY SIMULATION

The D-RRL algorithm consists of two parts:

• Initialization of the initial in-memory data structures by pre-computing the |V | shortest path trees. This step is done only once, at the initialization of the network after the initial topology discovery.

• Partial update of shortest paths each time an edge is inserted or deleted. The algorithm 5, details this step for a partial update following an edge insertion to G 1 .

The algorithm tests at line 6 whether the insertion of the edge does reduce the distance from the root node to the destination end of the edge. If the distance is not decreased, there is no need to do any changes to the spanning tree.

If the insertion of the edge does decrease the distance towards the node v, the algorithm executes a Dijkstra-like construct (lines14-22 ) to update the impacted branch of the shortest path tree while leaving intact the rest of the tree. The actual reconstruction of the shortest path tree is done at lines 12 and 19: we delete from the shortest path tree the edge connecting the affected node and its predecessor on the path from the root. It is safe to assume that exactly one such edge exists, because every node except the root has exactly one inbound edge in a directed tree. The root node would never be examined due to the condition at the beginning of the algorithm.

The use of the dynamic shortest path algorithm has two advantages. First of all, it only recomputes the solution for the impacted subtree of each |V 1 | trees. Secondly, the biggest improvement is due to the fact that only a fraction of these trees will be, at all, impacted. Most of them will not pass the condition at line 3.

Evaluation by simulation

Although we made an extensive effort to evaluate the feasibility of the proposed solutions, access to real backbone network devices and real traffic information are difficult to obtain. Network operators and device manufacturers keep the details about their networks and their devices secret. Considering that experimenting with large scale production networks was not possible in our case, we resorted to simulations, combined with validation on a small-scale network testbed to assess the proposed techniques.

In our initial work [START_REF] Carpa | STREETE : Une ingénierie de trafic pour des réseaux de coeur énergétiquement efficaces[END_REF][C3][J2], we used the discrete event simulator OMNeT++, together with the network simulation framework INET, to simulate real packets flowing through the network and through the software stacks of network devices. However, due to extremely long simulation times and low benefits of the packet-based simulation in the context of backbone networks, we changed our testing methodology. We present some lessons learned from the packet-based simulations in a forthcoming section (4.3.4).

The subsequent work was evaluated on an algorithmic level: we executed the algorithms on emulated input data without simulating packets transiting through the network.

In parallel, we designed and implemented a proof of concept in the ONOS SDN controller and validated it on a small network testbed.

This section presents the evaluation methodology and the architecture of our testbed.

Evaluated networks

We employ the network topologies shown in Figure 4.3 to evaluate our solution. By using real traffic matrices for these networks, we evaluate our solutions in close to real scenarios. Although we do not simulate packets flowing through the network, we execute the algorithms and compare their estimation to a MILP baseline which is presented in the next section. The input of an algorithm is the traffic matrix at a discrete time t, and the output is the routing that must be applied to the network. Moreover, a few details are worth mentioning:

• The traffic matrices for the Geant and Germany50 networks are taken at 15 minute and, respectively, 5 minute intervals. We have no insight on the evolution of network flow in-between this sampling intervals. Moreover, the matrices date from 2007 and may not reflect the state of traffic in modern networks. Over the past years, the cloud has been extensively adopted by numerous companies and access to video streaming on demand has become commonplace in households around the world.

• The traffic matrices for the NSFNet, USNet, AT&T and Italian are issue from the GreenTouch project [START_REF] Korotky | Projections of IP Traffic to 2020 Based on Regression Analyses of Historical Trends and Nearer Term Forecasts[END_REF][94] and represent the average business Internet traffic expected between nodes of the networks in year 2020. For each network, we have 12 traffic matrices which reflect a day of operation with a 2 hour sampling interval.

• Most of these networks are small and may not correspond to the size of modern networks regarding the number of devices. Unfortunately, the operators keep the information about their network topology confidential. The only backbone network

EVALUATION BY SIMULATION

who's topology is not secret is Geant 1 . The size of this network didn't change much compared to the one provided by SNDLib in 2007. For this reason, we follow the same path as the rest of the research community and assume that the sizes of networks presented in Fig. 4.3 are representative of the reality.

Nevertheless, we believe that the continuous growth of network traffic may lead to a growth in number of devices. To evaluate the computational time on bigger networks, we also executed the algorithms with uniform all-to-all traffic on the networks from Figure 4.4. The first one, Coronet, was taken from the Internet 2 .

We also artificially generated a 200 node network using the igen 3 toolbox. The properties of these networks are summarized in

The MILP baseline

The MILP model used to generate a baseline for comparison, do not necessarily model the same problem as the described algorithms. We neither seek to design complex MILP models nor search for advanced techniques for solving them. Such techniques, for example, include the column generation method. For us, the Linear Programming provides a way to establish an upper bound for the solution quality against which our solutions can be compared.

The MILP model used in this chapter uses the following variables:

V set of nodes E
set of links cpeq capacity of the link e d i,j demand from source node i P V towards the destination node j P V f i,j e flow from node i P V to node j P V passing through link e P E x e boolean: 1 if the link e P E is ON; 0 if it is OFF w v set of outgoing links from the node v P V w v set of inbound links towards the node v P V

The model objective is to minimize the number of links being kept active. minimize:

ÿ ePE x e
Subject to: Flow conservation constraint:

ÿ ePw v f s,d e ´ÿ ePw v f s,d e " $ ' & ' % ´ds,d , if v " s d s,d , if v " d 0, otherwise @v P V, @ps,dq P V 2 : d s,d ą 0 (4.1)
Link capacity constraint:

ÿ ps,dqPV 2 :d s,d ą0 f s,d e ď cpeq ¨xe @e P E (4.2)
Likewise STREETE, we force an always-active spanning tree in the network:

x e " 1 @e P E : e is on spanning tree (4.

3)

The MILP model has a small advantage over STREETE: flows are allowed to follow multiple paths in the network. This was done to reduce the computational complexity. Without this simplification, the MILP solver was sometimes unable to find the exact result in 2 hours even for the 24 node USNET network.

To produce the optimal baselines for comparison, we use the CPLEX 12.7.1 C++ API to build the linear programs directly from our C++ code and to solve them. The biggest network for which CPLEX executed without running out of RAM was Germany50.

Evaluation metrics

Energy consumption. We consider uniform link speeds and, as explained in a previous chapter, the energy consumption of network devices does not depend on their utilization. As a result, we assume that the energy a network consumes is proportional to the number of active links. Although we recognize that it is important to handle heterogeneous link speeds and energy consumption, this scenario is left for future work.

Distribution of network load. The utilization of the links is another parameter that illustrates the quality of the solutions based on switching links on and off. This includes not only the utilization of the most loaded link, but also the distribution of the load across all links. The last case is especially interesting for the load balancing purpose in the following chapter of this thesis. We believe that having a single highly utilized link is worse than having two links at medium utilization. In the latter case, the network is less likely to become congested if the traffic increases. Hereafter we present figures (e.g. Figure 4.5) that condense a lot of useful information: they illustrate the proportion of links that are active, their utilization, and the distribution of the utilization across the whole network. In particular, Figure 4.5 illustrates a day of the NSFNet network with two different routing techniques: i) classical shortest path routing; and ii) a technique that tries to turn links off.

For the NSFNet network, we have 12 traffic matrices at 2 hour intervals. For example, traffic matrix 0 represents the network at 00:00 o clock, while the traffic matrix 1 at 02:00AM. Each column on the x axes represents the distribution of the load on the links with a fixed traffic matrix. The black area corresponds to the lightly utilized links, while white points show an utilization close to 1 (100%). The black links in the rightmost figure are off. The bold white line shows the border between the active and inactive links. The y axes allows to rapidly evaluate the number of inactive links.

The figure makes it easy to see the distribution of the load in the network. At 8AM (x " 4), not only we were able to reduce the energy consumption of the network, but we also avoided to create new white (highly utilized) links. With the traffic matrix 4, CHAPTER 4. CONSUME LESS: THE STREETE FRAMEWORK FOR REDUCING THE NETWORK OVER-PROVISIONING the utilization of most active links in the rightmost figure is between 20% and 40%. To generate this figure, for each traffic matrix, the links were sorted by their utilization. As a result, the most utilized link is always shown at the bottom of each column and does not necessarily correspond to the same link in the adjacent columns.

Computational time. Another important parameter is the time needed by the algorithms to generate a solution. The solution proposed in this chapter has a high theoretical complexity but while behaves well in practice. For this reason, we measure the actual time the algorithm takes on the previously presented network topologies.

All our algorithms were implemented in C++ within the OMNeT++ [START_REF]OMNeT++ Discrete Event Simulator[END_REF] discrete event simulator. Even if we no longer make use of the packet-based simulation, we rely on the powerful tools included with the simulator to facilitate the description of network topologies; generation of simulation traces; and their analysis. All simulations were performed on servers with two Intel Xeon E5-2620 v2 processors and 64Gb of RAM. The RAM was never a limiting factor for the execution of our algorithms.

Path stretch. The fact that we put links to sleep to save energy certainly impacts the network performance. First of all, both turning links off and load balancing the traffic come at the cost of probably taking longer routes and thus increasing the endto-end delay of the network traffic. Longer network paths are particularly problematic in the context of backbone networks, where a detour path can, potentially, go around a whole continent. To evaluate this fact, we introduce the parameter path-stretch, which defines how much the path length is increased compared to the shortest path routing. Taking into consideration that the sub-flows of an origin-destination flow can take multiple routes in some of our solutions, we consider the mean path length. Formally, pathstretch i,j " avgtlpP q:P PP i,j and f pP qą0u lpSP i,j q with lpeq " 1. A path-stretch value of 1 means that the longest path and the shortest path have equal length. Respectively, a path-stretch=2 means that the length of the paths is twice as long as the shortest path.

Evaluation results

Lessons learned from packet based simulations

As mentioned previously, our initial work was evaluated using packet-level simulations. However, the simulation times were prohibitive. In particular, the results which we published in our first papers [START_REF] Carpa | STREETE : Une ingénierie de trafic pour des réseaux de coeur énergétiquement efficaces[END_REF][C3][J2] took up to a weak of computation per simulation scenario. Obviously, this approach had some benefits, including: the possibility to easily measure the packet losses in router queues resulting from unexpected burst of network traffic; the possibility to measure the influence of the management delay on the overall reactivity of the solution.

For example, our results from Fig. 4.6, illustrate the impact of the management delay when energy efficient traffic engineering is used to reduce networks' energy consumption. In particular, we injected the network load shown by the red filled curve into the Germany 50 network and executed STREETE.

With the goal to react proactively, before any congestion really occurs in the network, the algorithm turns link on as soon as a link is utilized at more than 80% of its capacity. However, even wit a safe margin, the network drops packets. There is a noticeable increase in the number of lost packets, especially at t " 40, when the initial network was already saturated. The packet loss on the most congested link at this moment is as high as 7.6%. This behavior is due to an approximately two-second delay between the increase of network load and the moment when the new forwarding rules are applied into the network devices by the SDN controller. Fig. 4.7 gives more insights on the matter. It shows the utilization map of each link in the Germany 50 network, where the blue area has an utilization close to 0 and red points present utilization close to 1. The white line in the right-hand side figure represents the limit between the links which are on an those that are off. It can be clearly seen that the network reacts with a delay to the congestion occurring at t " 40. Links are turned on only at approximately t " 42. This delay is almost entirely due to: i) the time needed for the traffic increase to be detected by network devices; ii) the time needed to notify the SDN controller about this; and iii) time needed to update the forwarding rules on network switches.

While packet based simulation allow to closer emulate the behavior of production network and detect problematic cases like the one presented in this section, we transited to the less expensive algorithmic evaluation which emulates only the work done by the SDN controller and not the entire network. Each figure corresponds to a day of operation of the network evaluated at fixed time points. For example, the first figures (4.8a -4.8d) are generated using traffic matrices captured every two hours, producing 12 timestamps on the x axis. The latest two networks (4.8e -4.8f) were evaluate at 5 minute and, respectively, 15 minute intervals.

CHAPTER 4. CONSUME LESS: THE STREETE FRAMEWORK FOR REDUCING THE NETWORK OVER-PROVISIONING

State of network links

EVALUATION BY SIMULATION

Fig. 4.9 shows a more link-centric way to illustrate a part of the results condensed in the heatmaps. It allows to visualize the utilization of each link separately and, in particular, to see how the ignition of some sleeping links reduces the utilization of the most loaded ones. This is particularly well visible for the USNET network: at traffic matrix #7, the ignition of links reduced the utilization of other links to keep it below 80%. The figures illustrate very well that shortest path routing does not suit these networks. Very few elephant flows consume most of the bandwidth. These flows rapidly congest some of the links while most links have very low utilization. Note that there are less highly utilized links when the STREETE framework is active. This result is particularly well visible on the USNET network (Fig. 4.8b and 4.9b) and may be counter-intuitive.

CHAPTER 4. CONSUME LESS: THE STREETE FRAMEWORK FOR REDUCING THE NETWORK OVER-PROVISIONING

An illustration of the reason is given in Figure 4.10 where two flows are routed in the network and, when the link hd is down, the flows take a detour over longer paths. As a result, none of the links is at critical load. However, if the link is on, the flows are routed over hd and its utilisation rises above the threshold α. We can conclude that STREETE behaves very well in all these scenarios. A large number of network links is turned off, enabling effective energy savings of up to 56% of the power consumed by the network links. We only consider uniform link speeds in this work. During the hours of low utilization, most networks are reduced to spanning trees. Moreover, STREETE is able to adapt the network against rises of traffic demands by turning links on when capacity is needed. Nevertheless, these results also indicate that STREETE was tested using "comfortable" conditions because it never faces a highly utilized network. In the next section we test the limits of the algorithm.

Pushing the limits of shortest path routing

In this section we evaluate STREETE in a more stressful condition. For this purpose, we execute the following experiment: we take the first traffic matrix from the data-set and initialize the algorithm. Afterwards, the evaluation follows the following pattern: at each validation time point, corresponding to an iteration of the STREETE framework, we increase the initial network load by an additive factor. The value of a flow at iteration t of the simulation is equal to d a,b ptq " d a,b p0q ˚t. This ensures that the load in the network increases continuously. We stop the simulation when the load of any link in the network reaches 100%. We compare STREETE against the optimum provided by the MILP solver (called "CPLEX" for simplicity) regarding both the number of active links and how long the algorithm can keep the network out of congestion.

Earlier we concluded that STREETE performs very well with the realistic traffic matrices. However, the results from Figure 4.11 reveal some shortcomings. The x axis corresponds to the t in the formula d a,b ptq " d a,b p0q ˚t, normalized to the moment when the shortest path routing in the full network revealed a congestion. As a result, x " 5 means that it was possible to absorb 5 times more traffic than what was possible to absorb with shortest path routing. The y axes shows the number of active links.

STREETE is very close to the optimum while the network is at low utilization. The only case when STREETE had to turn-on a lot of links is for the NSFNet network. To explain this case we can correlate with x " 0 on Figure 4.8c. We conclude that this case is due to the particularity of the traffic matrix used for validation: the demands are exceptionally high in this network, creating a high overall network load. It is perfectly normal that the algorithm turned on a lot of links to avoid congestion. Something to be noted in Fig. 4.11 is the fact that STREETE is sometimes able to keep the network out of congestion longer than the shortest path routing. For example, this is the case in the USNET network, where STREETE is capable to route more than twice the amount of traffic of classical shortest path routing. The reason of this behavior was explained in the previous section, Fig. 4.10.

CPLEX is able to successfully route the demands in the network way beyond the point of congestion in the full network topology G with shortest path routing. Fig. 4.9 and 4.13 illustrate the reason behind this case on the example of the Generated200 network.

In the same scenario of constant traffic growth, both classical shortest path routing and STREETE congested the Generated200 network just after tm " 4. From the results provided on shortest path routing (left part of Fig. 4.12b), it becomes clear that the congestion occurs on one single link. Most of the links are not even close to having a high utilization. In this context, STREETE is even able to keep a lot of links off and reduce the energy consumption of the network (Fig. 4.12a, right). To make STREETE behave better under high network utilization, in the next chapter we propose a solution that allows it to reach the quality of CPLEX at the cost of increased computational complexity.

Computational time

One of our main goals was to create an online solution, capable to react fast to network changes. The computational time is very important, especially when it is necessary to turn link on to avoid an imminent congestion.

Path stretch

Fig. 4.14 indicates how much the paths in the network increase due to consolidating the flows on a subset of network links. It is obvious that this action drastically extends some network paths. A minority are almost 15 times longer than the shortest path. A solution to this problem is to force some additional links to remain active. This decision has to be done at a topological level. We propose to use graph spanners [START_REF] Peleg | Graph spanners[END_REF] instead of spanning trees to guarantee that no unnecessarily long paths are created in the network as a result of turning links off. This case is left for future work.

Proof of concept and evaluation on a testbed

To evaluate our solution in real conditions, we built a small network test-bed relying on the ONOS SDN controller. A detailed description of this testbed along with results and lessons learned were previously analyzed in our works [J1][C2]. This section starts by presenting the platform and finishes with a discussion on the extracted results and the lessons learned during the evaluations.

The ONOS SDN controller

Open Network Operating System (ONOS) is an initiative to build an SDN [START_REF]Introducing ONOS: A SDN Network Operating System for Service Providers. Whitepaper[END_REF] controller that relies on open-source software components. This SDN controller facilitates the work of developing network applications by providing northbound abstractions and southbound interfaces that transparently handle the forwarding devices, such as Open-Flow switches and other legacy network devices. In addition to a distributed core that enables control functions to be executed by a cluster of servers, ONOS provides two interesting northbound abstractions, namely the Intent Framework and the Global Network View. The intent framework, depicted in Figure 4.15, allows an application to request a network service without knowledge of how the service is performed. An intent manifested by an application is converted into a series of rules and actions that are applied to network devices. An example of intent is setting up a virtual circuit between two switches A and B. The global network view, as the name implies, provides an application with a view of the network and APIs to program it. The application may treat the view as a graph and perform several tasks that are crucial to traffic engineering, such as finding shortest paths. To use the platform, a user requests: a slice or a set of cluster nodes to be used by an application as virtual switches or serving as traffic sources and sinks, an OS image to be deployed and a network topology to be used (step 1). We crafted several OS images so that nodes can be configured as SDN controllers and OpenFlow software switches, as discussed later. A bare-metal deployment system is used to copy the OS images to the respective nodes and configure them accordingly [START_REF] Jeanvoine | Kadeploy3: Efficient and Scalable Operating System Provisioning[END_REF], whereas a Python application configures VLANs and interfaces of the virtual switches emulating point-to-point interconnects to create the user-specified network topology.

The segment-routing based platform

Once the nodes and the network topology are configured, the user deploys his or her application (step 2 in Figure 4.16). All cluster nodes are connected to enclosure Power Distribution Units (ePDUs)5 that monitor the power consumption of individual sockets [START_REF] Rossigneux | A Generic and Extensible Framework for Monitoring Energy Consumption of OpenStack Clouds[END_REF]. This information on power consumption may be used to evaluate the efficiency of an SDN technique (step 3).

The data plane comprises two types of OpenFlow switches, namely software-based and hardware-assisted. The former consists of a vanilla Open vSwitch (OVS) [START_REF] Pfaff | The Design and Implementation of Open vSwitch[END_REF], whereas the latter OVS offloads certain OpenFlow functionalities to NetFPGA cards [104]6 . We use a custom OpenFlow implementation for NetFPGAs, initially provided by the Universität Paderborn (UPB) [105], that performs certain OpenFlow functions in the card, e.g. flow tables, packet matching against tables, and forwarding. Although the NetFPGA cards are by default programmed as custom OpenFlow switches, a user can reprogram them for different purposes by copying a bitstream file to their flash memories and rebooting the system.

The current testbed7 , depicted in Figure 4.17, comprises eight servers -five Dell R720 servers equipped with a 10Gbps Ethernet card with 2 SPF+ ports each and three THE NETWORK OVER-PROVISIONING HP Z800 servers with NetFPGA cards with 4 SPF+ ports each. All servers also have multiple 1Gbps Ethernet ports. The SPF+ ports have optical transceivers and are all interconnected by a Dell N4032F L3 switch whereas two 1Gbps Ethernet ports of each server are connected to a Dell N2024 Ethernet switch. This configuration enables testing multiple network topologies. The infrastructure and the use of ONOS satisfy some requirements of energy-aware traffic engineering, namely providing actual hardware, allowing for traffic information to be gathered, using actual network protocols, enabling the overhead of control and management to be measured, and monitoring the power consumption of equipment. Some energy-optimisation mechanisms, however, are still emulated, such as switching off/on individual switch ports. Although the IP cores of the Ethernet hardware used in the NetFPGA cards enable changing the state of certain components, such as switching off transceivers, that would require a complete redesign of the employed OpenFlow implementation. It has therefore been left for future work.

We implemented the algorithms as an ONOS OSGI module. The base of our solution was the "Segment Routing" module which is available in the ONOS distribution. As a result, we leverage features of the Segment Routing/SPRING for traffic engineering, such as the possibility to atomically change routes only on ingress devices without having to synchronize updates between devices. This flexibility comes at the cost of a small increase of the mean packet header size.

Segment-Routing application

ONOS provides an application implementing the SPRING(Segment Routing) protocol. We integrated our STREETE framework into this application.

We use a series of ONOS components, including its topology information, flow-rule services, and traffic flow objectives. As shown in Figure 4.18, a service Manager triggers the creation of remaining components when it is launched. Our energy-aware module, which comprises the proposed traffic-engineering algorithms, registers a flow-rule listener to measure flow traffic and link utilisation. The configuration component loads a file that specifies how switches are connected to local networks. This information is then augmented by a topology discovery process. Once the topology is updated, default shortestpath rules are created to guarantee that hosts from a network connected to a switch may reach hosts linked to another switch. A rule consists of a forwarding objective comprising a traffic selector and a treatment. Selectors and treatments result in sets of OpenFlow instructions that are passed to the switches. MPLS push/pop forwarding objectives are created for switches that do not have ports in the source and destination segmentsi.e. are neither ingress nor egress switches -and normal IP forwarding objectives are built otherwise. While the service is running, our energy-aware module is notified about The experimental validation of our solutions allowed us to discover some elements to be taken into consideration, which are presented in the next section.

Lessons learned from experimental evaluation

We implemented our algorithms on the test-bed presented in the previous section, using the ONOS SDN controller and hybrid software/hardware(NetFPGA) openflow switches. The evaluated network contains 7 nodes with 10G NetFPGA cards. A modified Open vSwitch (OVS) v1.4 is used to offload some OpenFlow rules into the hardware. Rules which cannot be offloaded, are treated by the Open vSwitch software kernel stack.

Due to the small network size, we consider that the results in terms of heuristic quality and speed are not representative. Even the MILP solver is able to provide an optimum solution in negligible time on such a small network. That is why, we concentrate on the control traffic overhead and traffic matrix reconstruction. Similar work already exists in the literature [START_REF] Shih-Chun Lin | Control traffic balancing in software defined networks[END_REF], but the analysed scenarios are not applicable to our case. In particular, we are interested in an online, fast response to traffic burst with lots of flow modifications each time a link is turned on. The literature usually assumes that flow modification are spread in time.

Although switching off underused links may be effective from energy efficiency perspective, sudden bursts in traffic may lead to congestion, hence requiring links to be made available. Performance evaluation using discrete-event simulation and UDP-like traffic has shown that the approach successfully reacts to traffic bursts without incurring considerable packet loss. It is assumed, however, that the SDN controller gathers the in-THE NETWORK OVER-PROVISIONING formation about link utilisation from switches every second and that a decision to power a given link back on may be taken and enforced quickly. We performed a simple test and measured the time needed for a controller to decide whether a link should be switched on. A small network topology was considered, as depicted in Figure 4.19. The Figure also shows the ONOS graphical interface and a data flow (green lines). The network starts with a minimal number of links turned on, forming a spanning tree, and with a TCP flow that nearly exceeds the utilisation threshold, above which the controller decides to turn on more links to handle congestion. A second flow is then injected, thus exceeding the threshold and forcing the controller to switch links on; we measure the time from flow injection to a switch-on decision. In the simulation, the decision takes on average 1.075 seconds, with most of the time spent gathering information on link utilisation. In the testbed, the time is on average 20% higher than in simulation.

We notice that the difference in results between simulation and real testbeds are generally due to simulations assuming zero delay at multiple parts of the processing pipeline and the manner network events are handled. While a single delay simplification would have marginal impact on the results, multiple delays along the packet processing pipeline can account for up to 30% difference in the time to react to changes. Examples of delay simplifications during discrete-event simulations include: instantaneous insertion of forwarding rules into the data path, immediate update of routing tables, fast propagation of flow counters from the simulated hardware ports to the software of the SDN switch, and instantaneous processing of IP UDP/TCP packets. Generally, the only delay properly handled by a simulator is packet queueing time.

Existing work has already shown that updating the data path forwarding rules is slow in current commercial SDN switches [START_REF] He | Measuring Control Plane Latency in SDN-enabled Switches[END_REF]. Google employees report [START_REF]Lessons learned from B4, Google's SDN WAN[END_REF] that their SDN-based WAN had an outage due to this issue on propagation of forwarding rules. Improvements can be made in the simulation software to account for some delay, and in the hardware design itself to reduce the time to propagate rules.

Other issues that we investigated concern the stability of the algorithms and the impact of traffic re-routing on TCP flows. Unlike traditional networks where changes in link availability are sporadic, under energy efficient traffic engineering, frequent changes may be the rule. Re-routing TCP flows, however, may lead to serious performance degradation due to segments arriving out of order, which in turn result in multiple duplicate ACKs and hence triggering the TCP congestion algorithms at source. Even though the algo-4.5. CONCLUSION rithms in the simulator mimic the behaviour of their corresponding theoretical models, they differ from the actual network software implementations provided by certain operating systems. In our in-depth analysis, which we present in the chapter 6 of this thesis, we observed that the Linux kernel, for instance, includes several non-standard optimisations [START_REF] Sarolahti | Congestion Control in Linux TCP[END_REF]. While simulations highlighted that re-routing TCP flows severely impacts the throughput of the transported TCP flows, empirical evaluation on the testbed demonstrated almost no impact under the same conditions. We believe that existing work that wraps real network software stack into simulators8 may help minimise this issue.

Conclusion

Solutions for improving the energy efficiency of wired computer networks propose to turn the links off during periods of low network utilization. This chapter follows this trend and proposes a reactive Software-Defined Network (SDN)-based framework which dynamically monitors the network status and turns the links on or off to provide the capacity needed for routing the network flows. Compared to the related work in this field, we focus on an online solution capable to instantly react to unpredictable network events and keep the network out of congestion while maintaining a low number of links active, thus reducing the energy consumption of the network.

To maintain a low computational overhead, our algorithm relies on an innovative idea which maintains two different views of the network topology in parallel. This allows to improve the quality of the results, especially for finding the correct links to ignite, field which is mostly overlooked by the research community. Moreover, it allows to reduce the impact of historical decisions on the execution of the turn-off algorithm.

We implemented our solution using state of art dynamic shortest path algorithms to further increase the execution speed. Moreover, the fact of entirely relying on shortest path computations, together with the use of the SPRING source routing protocol, allows to keep the control traffic overhead at a minimum.

We evaluate the proposed algorithms using real backbone network topologies with real traffic matrices and conclude that good results are obtained at low traffic load both in number of turned-off links and in its ability to avoid network congestion. We also implemented a proof of concept on a testbed using the ONOS SDN controller in order to evaluate the framework on real hardware.

This extensive validation allowed to detect that there is room for improving our solution at high load, leading to the work which we'll present in the next chapter. Moreover, the validation on the testbed revealed some instabilities due to the bad inter-operation between STREETE and the TCP congestion control, leading to the analysis performed in the chapter 6 of this thesis.

Chapter 5 Consume Better: traffic engineering for optimizing network usage

In the previous chapter, we presented a framework for reducing the energy consumption of IPoWDM networks by turning links on and off depending on the network load. However, despite the energy saving potential and small footprint of the presented solution, the results highlighted a potential shortcoming: a lot of resources can remain underutilized due to the minimum hop shortest path routing. In this chapter, we intend to address this weakness by including a load balancing technique in the STREETE framework to enable better utilization of the active links.

We start the chapter with a description of our first attempt to design such a load balancing technique and justify the reason why we did not explore this direction further. In the second part of the chapter, we present another, much more elegant and efficient, attempt to design and integrate into STREETE an Software-Defined Network (SDN) based online traffic engineering solution based on a state-of-art approximate multi-commodity flow algorithm to keep the computational complexity as small as possible. This solution also leverages the power of SPRING source routing to reduce the complexity and cost of centralized management.

CF: Searching for the perfect cost function

General overview

Our first attempt to avoid the shortcomings of the minimum hop shortest path routing still relies on the Dijkstra algorithm, but with a cost of traversing links that depends on their utilization. Instead of always routing flows via the smallest number of hops, we select the least utilized route by using a carefully crafted cost function which makes the cost of traversing a link dependent on its utilization. To describe the change more formally, we revisit the cost function l : E Ñ R `which we introduced in chapter 3. Until now, we implicitly assumed that l is a constant. In this section, we force l " f pupeqq, with f : r0,1s Ñ R `.

An example of such functions is presented in Fig 5 .1. For example, a link utilized at 10% of its capacity will have a cost of 1.88, while a utilization of 80% will increase the cost of the link to 3.27. The intuition may tell us that routing flows in the network over The computational complexity of such a solution may be quite significant. A trivial algorithm will compute the shortest path for each origin-destination pair, resulting in |V | 2 shortest path computations. To reduce the complexity, we leverage a particularity of the sizes of network flows. More precisely, different authors [START_REF] Hassidim | Network utilization: The flow view[END_REF] [109] [START_REF] Uhlig | Providing public intradomain traffic matrices to the research community[END_REF] analyzed real traffic traces and concluded that most network traffic is transported by a low number of elephant network flows. This result was also confirmed in the case of aggregated origindestination demands [START_REF] De Schmidt | Gaussian traffic revisited[END_REF]. Our solution starts by breaking the demands from the traffic matrix into two groups. The first one contains the requirements of mice flows, while the second one the demands of elephant flows. For this purpose, we use a classification algorithm designed for heavy-tailed distributions [START_REF] Jiang | Head/tail Breaks: A New Classification Scheme for Data with a Heavytailed Distribution[END_REF].

The algorithm will route all the elephant demands one by one using a dedicated shortest path computation per demand. However, to keep a low computational overhead, the mice demands will be routed per-source: all the demands from the same source will be routed using our custom modified shortest path algorithm which greedily adapts the costs of links at the same time as computing the shortest path.

Algorithms

The only non-classical algorithm used by our solution is a modified Dijkstra created for routing the mice flows. It is a greedy algorithm which computes a tree for routing the flows originating from a given source node v root P V while dynamically updating the link costs in conformance with the cost provided by the function lpeq. In particular, during the execution of the algorithm, the costs lpeq are not static, they change as consequence of previous routing decisions and influence the selection of network paths for the subsequent flows. Nevertheless, it remains a greedy algorithm: at each iteration, the previous choices are never re-evaluated and only influence the subsequent ones.

CF: SEARCHING FOR THE PERFECT COST FUNCTION

Algorithm 6 Constructs the tree T which gives the routes for the demands originating from the root node v root towards all other nodes in the network while greedily respecting the link costs defined by the function lpeq

1: function RouteInTree(T pV, E T q, v root P V, d vroot,˚) 2:
for all v P V do for all v P visitedListr1 :s do Ź all elements in the list except the first one 13:

distancervs Ð 8 The algorithm proposed by us (Alg. 6) acts similarly to Dijkstra's. At each step, it selects the node a P V that is the closest to v root under the length function l and was not yet connected to the routing tree T . This operation is performed at lines 10-24. After that, the selected node is marked as treated and is connected to the tree being constructed (lines 26 -30).

At lines 32-36, the demand d vroot,a is placed into the network using the unique path from the root node v root to a in this tree T . This action will probably change the cost of passing through the corresponding edges. As a consequence, the distance of nodes from the root v root may also change. At lines 36-39, the distances are updated to reflect the new costs of links.

Finally, the last f or loop ensures that the neighbor nodes of a that were not yet encountered by the algorithm will be considered in the next iterations of the outer while loop.

Evaluation methodology and first results

Evaluation parameters

In the previous chapter, we highlighted that STREETE without load balancing is capable of delivering good results when the utilization of the network is inferior or equal to the utilization achieved by the classical shortest path routing. The bad performance starts to be noticeable at higher utilization. That is why we focus our evaluation with scenarios using high traffic load.

Similarly to the previous chapter, we evaluate the time the algorithm can keep the all-on network out of congestion. The traffic demands are additively increased at each step until the network becomes congested. We also analyze the utilization of the most loaded link. This metric is directly related to the capacity of the algorithm to keep the system out of congestion if the load increases. The problem of minimizing the utilization of the most loaded link is known under the name of "minimum bottleneck utilization routing problem" and is equivalent to the maximum concurrent flow problem [START_REF] Shahrokhi | The Maximum Concurrent Flow Problem[END_REF].

A critical part of the proposed algorithm is in selecting the correct link length function. Before investigating this problem further, we decided to test the viability of the proposed solution using a large number of randomly generated cost functions. We automatically generated cost functions using the cubic bezier parametric curve with random parameters. Figure 5.2 illustrates multiple examples of such functions. We tested the algorithm with each one and selected the best routing, i.e. that results in the smallest maximum link utilization.

CPLEX model used as baseline

The optimal baseline was computed using the following linear program, which corresponds to the standard node-arc formulation of the "minimum bottleneck utilization routing problem". NETWORK USAGE Considering the variables f e " ř pi,jqPV 2 :d i,j ą0 f i,j e , the model objective is to minimize the utilization of the most loaded link:

Minimize: maxp fe cpeq q Subject to the flow conservation and edge capacity constraints:

ÿ ePw v f i,j e ´ÿ ePw v f i,j e " $ ' & ' % ´di,j , if v " i d i,j , if v " j 0,
otherwise @v P V, @pi,jq P V 2 : d i,j ą 0 x axes are normalized to the moment of congestion with classical shortest path routing.

LB: MAXIMUM CONCURRENT FLOW FOR LOAD BALANCING WITH SDN

The results are shown in Fig. 5.3. We slightly improved the distribution of the load on the network and kept it out of congestion for up to 3 times longer than with shortest path routing. However, the quality of the result is volatile: the maximum link load varies a lot. Our tests showed that even tiny variation in the shape of the cost function could lead to extreme changes in the quality of the final solution.

Moreover, the additive nature of the cost of network paths does not suit the problem. An unfavorable case that frequently occurs in practice is depicted in Fig. 5.4. Two paths are possible between the node a and c: i)pad,dcq; and ii) pab,bcq. The first path contains two links with a utilization of 50%. The second path passes through two links, with a usage of 90% and 5%. At the same time, due to the additive nature of the lengths of the path, both paths have the same length of 4 and are considered equally good for routing the flow ac. This behavior is not desirable in a load balancing technique. The first path should probably be preferred to avoid increasing the utilization of the link ab even further. Our preliminary tests showed particularly bad results in the context of the heterogeneous links: the flows were not discouraged from passing through low speed links, leading to their congestion very fast.

We believe that there may exist techniques to improve the stability of the presented approach, but we abandoned this direction in favor of the solution proposed in the next section.

LB: maximum concurrent flow for load balancing with SDN

In this section, we present our second attempt to include a load balancing technique into STREETE. Similarly to the solution presented in the previous section, the central optimization phase of the current solution relies on assigning costs to network links. During the execution of the algorithm, the cost of each link increase when demand is routed through the link. Moreover, the algorithm also uses shortest path computations and relies on these costs to prioritize the paths passing through the less loaded links. However, there is a huge difference between the two approaches. The reason why the forthcoming algorithms obtain much better results is in the fact of repeatedly routing tiny fractions of the traffic demands into the network. Moreover, at each iteration, the costs of the links increase by a minimal factor. For example, thanks to the very slow variations of costs of the links, the unfavorable case presented in Fig. 5.4 will be avoided. NETWORK USAGE As a consequence of iteratively routing small fractions of demands at each iteration of the algorithm, the integral demands will be split into multiple paths. The originality of our contribution consists in proposing a way to efficiently achieve the multipath forwarding by combining centralized and distributed optimization. This way we also reduce the control traffic overhead, because the SDN controller does not have to orchestrate the data-planes of SDN switches explicitly. The SDN controller transmits only a set of constraints to each switch. These constraints are used to re-compute the network paths and update the forwarding tables locally. We rely on the source routing protocol SPRING to be able to atomically change the paths of the flows by only updating the forwarding database of ingress network devices.

The solution that we propose combines i) the advantage of making global routing decision in the SDN controller; with ii) the offloading of some computations and the multipath forwarding rule construction to the SDN switches.

General overview

In this section, we give a general overview of our solution without emphasis on details. The algorithms will be presented in the next section.

The SDN controller performs the first step of our solution. It relies on Karakostas'[5] work on solving the approximate maximum concurrent flow problem via the primal/dual method. It constructs a solution to the dual problem, i.e. the length(cost) of the edges, by making slow variations in the values of the variables of the primal i.e. the amount of flow per path. During the execution of this algorithm, the centralized controller keeps track of the total flow of each ingress node. In particular, for each source node, the controller computes the amount of total flow passing through the links of the network. shows an example of output computed by this algorithm in a small network with hypothetical all-to-all communications. In particular, we are interested in the following output: i) the best possible routing of the flow in the network which minimize the utilization of the most loaded link (Fig. 5.5a); ii) the decomposition of this multicommodity flow per source node (Fig. 5.5b -5.5e).

LB: MAXIMUM CONCURRENT FLOW FOR LOAD BALANCING WITH SDN

The second step of our solution corresponds to sending the output from the previous algorithm to the corresponding SDN switches. For example, it sends the following list to the node a: ppab, 1.43q, pcd, 19.03q, pad, 37.00q, pac, 20.85qq. In particular, SDN controller informs each SDN switch of how the data it originates must be transmitted through the network and provides a way to achieve a global optimization of the network traffic. On the other hand, the data transmitted to the SDN switches does not contain any explicit information about the routes to be taken by each origin-destination flow. The communication overhead decreases, but the ingress SDN switches must now locally compute the forwarding paths in a way to respect the constraints given by the centralized controller. For example, the switch a will try to locally route the traffic to match the flow from Fig. 5.5b.

The last step of our solution is to locally compute the forwarding rules on SDN switches while matching the flow transmitted by the SDN controller. We insist on the fact that the flow sent by the SDN controller is, by construction, a valid flow, but is not necessarily a minimum-cost one. As a consequence, it may contain cycles which we would like to reduce to simplify the task of building the forwarding rules. An example of cycle is shown in Fig. 5.5d: a Ñ b Ñ a. The SDN switch will start with applying the cycle-canceling algorithm [START_REF] Klein | A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems[END_REF] on the received flow. This operation has the advantage of outputting a Directed Acyclic Graph (DAG). The SDN switch can now easily compute the forwarding paths in the network by leveraging the properties of the DAGs. In particular, the fact that it can be topologically sorted. Moreover, the switch has the visibility into the composition of the flow at a granularity which cannot be transmitted to the SDN controller. It can leverage this knowledge to split the origin-destination flows into subflows and send each sub-flow over a separate path to match the constraints imposed by the controller correctly.

Step 1: maximum concurrent flow computed by the SDN controller

The core of the centralized optimization part of our solution relies on the algorithm by Karakostas [START_REF] Karakostas | Faster Approximation Schemes for Fractional Multicommodity Flow Problems[END_REF] for computing an approximate solution to the maximum concurrent flow problem.

Notations

Maximize λ under the constraints: Minimize ř ePE lpeqcpeq under the constraints:

ÿ P PP i,j
f pP q " λ ¨di,j @pi,jq P V 2 : d i,j ą 0 ÿ P PP:ePP f pP q ď cpeq @e P E f pP q ě 0 @P P P (a) Primal ÿ ePP lpeq ě lpSP i,j q @pi,jq P V 2 : d i,j ą 0 @P P P i,j ÿ pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j ě 1 For convenience, we summarize the notations. Fig. 5.6 shows the edge-path formulation of the maximum concurrent flow problem that was introduced in a previous chapter. We also recall that P is a path in the network, P represents the set of all the paths and P i,j is the set of all the paths starting at node i P V and finishing at node j P V . Moreover, f pP q is the amount of flow passing through the path P , d i,j is the demand from node i to node j. The function l : E Ñ R `and c : E Ñ R `give, respectively, the cost of passing through a link e P E and the capacity of this link. Finally SP i,j is the shortest path among all the paths from i to j: implicitly assumed under the length function l. To simplify the notations, let Dplq " ř ePE lpeqcpeq be the value of the dual objective function; Dpl ˚q be the dual optimum; and define aplq " ř pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j

lpeq ě 0 e P E (b) Dual
to be the expression from the last constraint of the dual.

Algorithm

The Alg. 7 presents the algorithm as implemented and used by our solution. It closely follows the original algorithm [START_REF] Karakostas | Faster Approximation Schemes for Fractional Multicommodity Flow Problems[END_REF]. Nevertheless, the structure was reorganized for easier implementation and possibility to compute the per-source flow. Moreover, we incorporated the details of some non-trivial building blocks used as primitives by the Karakostas.

The algorithm starts with the trivial valid solution f " 0 for the primal LP and a constant length function lpeq " δ cpeq which represents an invalid solution for the dual LP. After that, the algorithm proceeds in multiple phases to construct the optimum solution for the dual LP. Each step corresponds to an iteration of the loop at line 4. δ is a very small constant which is crucial to the proof of the algorithm and is specifically chosen for this purpose. More details on this constant will be provided in the next section.

In each phase, for each source node src, the algorithm uses the shortest path tree T src rooted at this source which is computed by the Dijkstra's algorithm. This allows to simultaneously route the demands towards all the destinations (line 10 ). The details of the RouteInT ree procedure was provided in the previous chapter (section 4.2.3). The algorithm then increases the length/cost of the links which have just been used exponentially to the amount of data which transited through the link (line 17). From an LP perspective, this action corresponds to adjusting those variables of the dual which violate the most its constraints. This is done while keeping a relationship between the variables of the primal and those of the dual.

A more intuitive interpretation can also be given: the algorithm repeatedly routes the demands over the least loaded links and increases the cost of these links exponentially to the added load. This way, the most loaded links will become more costly and have less probability to be used in the next steps of the algorithm.

By construction, the computed flow respects the flow conservation constraints and non-negativity constraints but may violate the link capacity constraints. At the end, the flow must be scaled down to obtain the minimum utilization routing used in the next steps of our solution.

Proof of the algorithm

This section unifies the proofs from the four works [START_REF] Shahrokhi | The Maximum Concurrent Flow Problem[END_REF][114] [START_REF] Garg | Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems[END_REF][5], as none of them provides a unified proof with all the necessary details. for all v src P V do 6:

Initialize d 1 vsrc,v dst Ð d vsrc,v dst , @v dst P V 7: moreTraffic Ð Dv dst s.t. d 1 vsrc,v dst ą 0 8:
while Dplq ă 1 and moreTraffic " true do 9: end while

T src Ð Dijkstra(v src ) 10: f p˚,˚q Ð RouteInTree(T src , v src , d 1 vsrc,˚)

25:

for all v P V do 26:

f v pu,vq Ð f v pu,vq {log 1`ǫ 1`ǫ δ 27:
end for 28: end procedure

The proof that the algorithm efficiently computes a solution to the maximum concurrent flow with a precision ǫ is done in three steps:

• provide an upper bound for the dual optimum Dpl ˚q at the end of the algorithm.

• provide a lower bound for the primal optimum λ ˚at the end of the algorithm.

• show that the dual to primal ratio Dpl ˚q λ ˚ď 1 `ǫ (in an optimal solution, the ratio Dpl ˚q λ ˚" 1. Moreover, by the weak duality property, Dplq ě λ for any Dplq and λ. This way, we prove that the algorithm computes an ǫ-approximation of the optimal solution.) i) To provide an upper bound on the resulted dual solution, we assume that Dpl ˚q ě 1. If Dpl ˚q ă 1, it is possible to scale down all the demands d i,j to ensure that Dpl ˚q ě 1. In fact, having Dpl ˚q ă 1, corresponds to the case when the network capacity is not enough to route all the demands. A possible scaling procedure will consist in routing the demands into the network by ignoring the link capacity constraints. This will allow to detect the maximum violation of a link capacity: r " maxp fuv cpuvq |uv P Eq. Scaling all the flows down by r will ensure that Dpl ˚q ě 1.

Let l i be the length function l at the end of phase i (i.e., of the iteration i of the loop at line 4). The operation at line 16 increases Dplq by at most ǫ ¨apl i q during the phase i. In fact, during the iterations of the outer loop, the increment added by each execution of the line 16 ( ǫ ¨lpuvq ¨fpu,vq ) gradually computes the same sum as ǫ ¨apl i q (i.e. ǫ ř pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j ), but with lower link lengths. Considering that the lengths monotonically increase at line 17, at the end of the phase i, apl i q will be bigger than the same sum computed with lower link lengths. As a result, at the end of each phase i, Dpl i q ď Dpl i´1 q `ǫ ¨apl i q

Consider the relation Dplq aplq ě Dpl ˚q which was proven true for any length function l in the chapter 3 ( lemma 3.12). It allows us to substitute apl i q in the previous equation and obtain Dpl i q ď Dpl i´1 q `ǫ Dpl i q Dpl ˚q . By re-organizing the therms, we get:

Dpl i q ď Dpl i´1 q 1 ´ǫ{Dpl ˚q
The previous recursive relation, together with the fact that Dpl 0 q Ð mδ at line 3 implies

Dpl i q ď mδ p1 ´ǫ{Dpl ˚qq i " mδ 1 ´ǫ{Dpl ˚q p1 `ǫ Dpl ˚q ´ǫ q i´1 ď mδ 1 ´ǫ{Dpl ˚q e ǫ¨pi´1q Dpl ˚q´ǫ
Under the assumption that Dpl ˚q ě 1:

Dpl i q ď mδ 1 ´ǫ e ǫ¨pi´1q p1´ǫq¨Dpl ˚q
Taking into consideration that the algorithm finishes at the first iteration t in which Dplq ě 1, we obtain mδ 1´ǫ e ǫ¨pt´1q p1´ǫq¨Dpl ˚q ě 1. As a result, at the end of the algorithm:

Dpl ˚q ď ǫ ¨pt ´1q p1 ´ǫqln 1´ǫ mδ (5.3)
ii) To provide a lower bound on the value of the primal solution λ ˚, we observe that each phase of the algorithm (except the last one) routes exactly d src,dst units of flow from each source node src to each destination node dst. As a result, if the algorithm finishes during the iteration t of the main loop, the algorithm has routed at least pt ´1q ¨dsrc,dst units of each flow.

Another observation is that, at the end of any phase i except the last one, the length l i peq of each edge e is shorter than 1{cpeq (otherwise Dplq " ř ePE lpeqcpeq ě 1 and terminates the algorithm). Furthermore, this property is also maintained during the last phase by the condition Dplq ă 1 in the loop 8. As a result, when the algorithm ends, this property is violated at most once per edge by the line 17. The length of any edge e at the end of the algorithm is thus at most lpeq ă p1 `ǫq{cpeq. Knowing that the lengths are initialized to δ{cpeq at the start of the algorithm (line 2), each edge finishes with a length which is at most p1`ǫq{cpeq δ{cpeq " 1`ǫ δ times its initial length. Moreover, the operation at line 13 ensures that each cpeq units of flow routed through an edge e increases its length by at least 1 `ǫ. As a result, the capacity of any edge is violated by at most log 1`ǫ 1`ǫ δ times its capacity. Finally, all these observations imply that the algorithm routes at least t ´1 units of each commodity, while violating the capacity of any edge by at most log 1`ǫ 1`ǫ δ times its capacity. Scaling the flow down by log 1`ǫ 1`ǫ δ gives us a feasible flow for the primal LP. As a result, at the end of the algorithm, a lower bound for λ ˚is given by:

λ ˚ě t ´1 log 1`ǫ 1`ǫ δ (5.4)
iii) From equations 5.3 and 5.4, we obtain: ˚becomes smaller than p1 ´ǫq ´3. It is possible to pick ǫ in a way such that the ratio is less than 1 `w for any w ą 0. As a result, the presented algorithm computes an 1 `ǫ approximation of the maximum concurrent flow problem.

Dplq λ˚ď ǫpt´1q p1´ǫqln 1´ǫ mδ t´1 log 1`ǫ 1`ǫ δ " ǫ ¨log 1`ǫ 1`ǫ δ p1 ´ǫqln 1´ǫ mδ " 1 1 ´ǫ ¨ǫ lnp1 `ǫq ¨ln 1`ǫ δ ln 1´ǫ mδ ď ď 1 1 ´ǫ ¨ǫ ǫ ´ǫ2 {2 ¨ln 1`ǫ δ ln 1´ǫ mδ ď 1 p1 ´ǫq 2

Discussions on choosing the precision

The asymptotic bound of the complexity proven by Karakostas [START_REF] Karakostas | Faster Approximation Schemes for Fractional Multicommodity Flow Problems[END_REF] is Õpǫ ´2|E| 2 q, where the notation Õ hides the logarithmic factor logp|E|qlogp|V |q. In practice, the algorithm is very dependent on the chosen precision ǫ for more than one reason.

Evidently, ǫ defines the execution time. However, the quality of the solutions is much more affected than the speed. For example, setting a precision of ǫ " 0.3 may be tempting, as the algorithm will provide a result almost ten times faster compared to a precision ǫ " 0.1. However, the obtained dual to primal ratio Dpl ˚q λ ˚" p1 ´03q ´3 " 2.91545 resulted in almost useless outputs during our preliminary tests.

Another, less obvious, dependence on ǫ is hidden in the initialization of the algorithm at line 2. δ is a very small constant which depends on ǫ and the number of links. Setting the precision too low, like 0.01, not only drastically increases the execution time, but also induces numerical issues due to the limited precision of floating point numbers.

To avoid these two issues, we have empirically chosen the precision to be ǫ " 0.1, which provides a dual to primal ratio of 1.37174. Even in this case, we had to use the "long double" type for our variables to avoid numerical issues on the biggest of our evaluated networks: Generated200.

Step 2: transmitting the constraints to the SDN switches

In this section, we discuss the communication overhead of the proposed solution. After execution of the centralized optimization phase, the SDN controller sends separately to each switch the flow he must achieve. At most, the control traffic overhead grows asymptotically with the number of links in the network: Op|E|q. However, in practice, only a fraction of the links will be used. 5.7 retakes the same example that was presented in the previous section (5.2.1) and illustrates the flow originating from the node a. In this case, the information transmitted by the network controller to the node a will consist of the list ppab, 1.43q, pcd, 19.03q, pad, 37.00q, pac, 20.85qq.

We evaluate the control traffic overhead in the Generated200 network. Even if we assume the worst case scenario when each of the nodes uses all the links, the total network traffic overhead is Op|V | ¨|E|q. We also consider an efficient encoding of data when transferring through the network, were only 32bytes are used to uniquely identify a link and represent the amount of flow passing through it. In this case, the SDN controller will have to send into the network a total of 200 ˚1148 ˚32bytes » 8M bytes of control traffic. We consider that this is a reasonable small control traffic overhead for a network with 200 nodes.

In practice, nodes do not use all the links for forwarding. For example, in 5.7, the nodes use less than half of network links. The communication overhead will be smaller than the estimated quantity.

Step 3: computing paths by SDN switches

The goal of this step is to compute the explicit paths used for data forwarding. The information transmitted by the SDN controller gives a good indication of the routes which must be preferred by the SDN switch but does not explicitly indicate these routes. An additional computation must be done to build the forwarding paths and update the 5.2. LB: MAXIMUM CONCURRENT FLOW FOR LOAD BALANCING WITH SDN forwarding database of the network device. For example, the node a from Fig. 5.7 will construct the following routing:

• The demand from a to b will be integrally sent over the path pabq

• The demand from a to c will be integrally sent over the path pacq

• The demand from a to d will be split over two paths:

-66% ( 3737`19.03 ) over the path padq -34% ( 19.03 37`19.03 ) over the path pac, cdq This section presents the algorithms proposed for this purpose. These algorithms rely on two hypothesis: i) use of a source routing forwarding protocol, and ii) the origindestination demands have a high aggregation level.

The first assumption is respected by the use of the SPRING protocol. It enables the ingress nodes to locally change the network routes without having to update the forwarding tables of midpoint devices. The second is true in backbone networks, making it is possible to split the demands at a TCP/UDP flow granularity: out of thousands of TCP/UDP connections which make the aggregated origin-destination flows, some connections will be forwarded over one path, while the others will take another path. Without a large aggregation of flows, the efficiency of the proposed solution may decrease, because it will be difficult to split the demands into multiple paths.

Transform the flow into a topologically sorted DAG

The per-source flow computed at the SDN controller is not necessarily a minimum-cost flow. When the ingress node receives the flow from the SDN controller, it will start by deleting the cycles from the flow graph of the source node src (G src ) to obtain a minimumcost flow. The corresponding algorithm is trivial: it starts by transforming the flow in the network topology graph into the corresponding residual flow. Afterward, it executes the classical cycle canceling algorithm [START_REF] Klein | A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems[END_REF]. As the resulting directed graph does not have any cycles, we topologically sort this DAG using the unmodified, classical, sorting algorithm [START_REF] Kahn | Topological Sorting of Large Networks[END_REF].

At this stage, the SDN switch has all the pre-requisites needed to quickly compute the forwarding paths for the network flows and assign the traffic to each route using the procedure that we present in the next section.

Computing the routes for flows

To define the explicit paths in the network, we propose a procedure that considers that the DAG has a topological order.

For each node v P V , a data structure is used to keep track of the explicit paths from the root v root towards this node. This data structure is a set of pairs, defined as R vroot,v :" tpP 1 , r 1 q, pP 2 ,r 2 q,...qu. Each pair represents a path P i and the associated ratio 0 ď r i ď 1, which corresponds to the ratio of demand d vroot,v which must be sent over the path P i . The sum of all ratios is ř i r i " 1. Alg. 8 describes the proposed solution. initialize ratio uv Ð 0, @uv P E D

3:

for all v P V do totalInT raf Ð totalInT raf `fuv end for 20: end procedure Before constructing the explicit paths, we do a preliminary computation: for each node v P V , we compute the fraction of flow entering the node through each of its inbound links (2 -11).

Afterward, the DAG is traversed following the topological order of nodes, which was computed in the previous section and stored in the list sortedV . Thanks to this order, when a node v is encountered, the paths used to reach its parents are already computed. At this moment, the set of paths allowing to reach v can be computed as the union of all the paths towards the parent nodes, extended by the corresponding inbound links from the parent (lines [START_REF] Dong | Energy-efficient core networks[END_REF][START_REF] Giroire | Minimization of network power consumption with redundancy elimination[END_REF]. The split ratio of flows over this path is the product of the split ratio to reach the parent multiplied by the ratio of inbound flow on the link. It is a number between 0 and 1. By construction, the computed split ration per path represents the fraction of the demand d vroot,v which must be sent over this path.

Once the paths and the corresponding ratios computed, the problem of assigning the sub-flows of the origin-destination demand d vroot,v into each of the computed paths corresponds to the "Generalized assignment problem" [START_REF] Cohen | An efficient approximation for the Generalized Assignment Problem[END_REF], which is NP-hard. Nevertheless, under the hypothesis of a high aggregation level, we assume that the integer constraint on the flows can be relaxed. As a result, the sub-flows of d vroot,v can be packed in these paths using a simple heuristics and obtain a solution which does not deviate much from the optimal fractional packing computed by the algorithm 8. An example of such heuristic may be the "first fit decreasing" algorithm. Without a large aggregation of flows, the efficiency of the proposed solution may decrease, because the efficiency of the "first fit decreasing" can be limited. The description of this heuristic is out of the scope of this work.

LB: MAXIMUM CONCURRENT FLOW FOR LOAD BALANCING WITH SDN

Avoiding long routes

The previous procedure has the drawback that it can generate a lot of long routes for transporting average ratios of the origin-destination flow. This applies in particular to big networks. However, it is possible to put a limit on the split level to avoid routes which are too long and provide little benefit. For this purpose, at line 16, whenever a small split ratio is detected, we should not add a new path to the set of paths. Instead, the corresponding fraction of demand d vroot,v should be redistributed over existing paths. In big networks, we recommend to use this approximation and prune all the paths with a small split ratio. Due to lack of time, we did not implement this optimization in the programs used to generate the results from the next section.

Evaluation

The algorithms were implemented in C++ and evaluated using the same methodology as presented in the previous chapter (section 4.3).

Maximum link utilization

Fig. 5.8 shows how well the algorithm keeps the network out of congestion and the maximum recorded link utilization. Once again, the x axes represent the time normalized to the moment just before a congestion in the all-on network. The y axes represent the utilization of the most loaded link in the network. For example, in the Italian network, our load balancing (LB) technique allowed to keep the network out of congestion 4 times longer (x axes) than the shortest path routing. In the meantime, the maximum link utilization was always close to the one provided by the LP solver (CPLEX). Our solution closely follows the optimum solution on all the networks. It is even difficult to distinguish between the result of our algorithms and the one provided by CPLEX. Our algorithm becomes unable to keep up with the optimal solution when very close to congestion. However, the deviation from the optimum is small. Fig. 5.9 shows the state of network links in the Italian network just before congestion. With LB, the network can route four times more traffic thanks to efficiently distributing the load. The shortest path routing performs very poorly in this case. The node R19 (top middle of the figure) is the destination of a vast number of elephant flows. Most of these flows pass through the same link. The figure on the right illustrates the Italian network using the LB routing technique. LB efficiently distributed the load over the four inbound links of the node R19. A small under-optimality can still be seen, as the two links at the left of R19 are less utilized compared to the two ones on the right. This is exactly the reason behind the sub-optimality which is visible in Fig. 5.8. Fig. 5.10 provides additional insights on the load of all the links in the eight evaluated networks. It separately shows the utilization of each network link. In fact, maximum value on the y axes on Fig. 5.10 corresponds to the value shown on the previous Fig. 5.8. The load is more uniformly distributed over the links. For example, in the case of the CORONET network (Fig. 5.10g), SPF routing results in a couple of highly loaded links and a lot of links with utilization close to zero. In the meantime, with LB, there are no links with utilization close to zero. All these results and other can be obtained by repeating the simulations. Please follow the instructions from the end of the first chapter of this thesis.

Computational time

Tab. 5.1 resumes the computational time taken by the algorithms. In the case of LB, the numbers include both the time taken by the centralized optimization phase presented in Section 5.2.2 and by the explicit computation of the forwarding paths presented in section 5.2.4. The precision used for the Karakosta's algorithm is ǫ " 0.1.

For completeness, we also provide the computational time taken by our first attempt to load balance (CF) presented in Section 5.1. We conclude that LB delivers better results while being, in most cases, faster than CF. This is particularly the case on big networks (Generated200, CORONET).

On small networks, CPLEX may seem to be an excellent alternative to the proposed heuristics, because it provides a proven optimal solution and its computational time is comparable to the heuristics. However, the output of the LP optimization is not a routing which can be directly applied to the network. Additional post-treatment must be done to build the routes for the flows. Alternatively, the linear programming (LP) model solved by the CPLEX solver could be updated to generate a viable routing directly. However,

Path length increase

Shifting the traffic out of the congestion zone comes at the cost of probably taking longer routes and thus increasing the end-to-end delay of the network traffic. In this section, we evaluate how much the path lengths increased during the evaluated scenarios compared to the shortest path routing. For this purpose, we use the parameter path-stretch introduced in the previous chapter. The results show that only a few flows are routed over long routes. The path length of each origin-destination flow rarely exceeds the double of the shortest path (SP) route. The median, represented by the red line in the middle of the box-plots, is close to one. This allows us to conclude that the majority of paths remain almost as short as with SP routing.

Conclusion

In this chapter, we proposed two solutions for load balancing the network load. The first one relies on a function that changes the cost of a link depending on its utilization. The preliminary validation revealed that minimal variations in the shape of the cost function could lead to a bad performance of the algorithm. In the search for a solution to this problem, we proposed an alternative load balancing technique.

Our second attempt provides a complete solution which tries to keep a low overhead of centralized management. For this purpose, the construction of the solution is split into two parts. First, a centralized optimization phase uses a state-of-the-art approximate maximum concurrent flow algorithm to find the near optimal distribution of the flow from each source. Similarly to the first load balancing technique, the central optimization phase of our second solution relies on assigning costs to network links. During the execution of the algorithm, the cost of each link increase when demand is routed through the link. Moreover, the algorithm also uses shortest path computations and relies on these costs to prioritize the paths passing through the less loaded links. However, thanks to making tiny steps during the execution of the algorithm, it is possible to achieve a testable nearoptimal solution.

Unfortunately, the algorithm delivers a solution which splits the traffic into multiple paths. Our contribution is in providing a way to effectively apply the previously computed routing into the network switches and change the paths of network flows. We avoid using explicit routes and keep the communication overhead reasonable low even on the biggest of the evaluated networks. This is achieved by deporting part of the computation to a network device. The second part of our solutions consists in locally computing the explicit paths for the network flows on ingress devices, which also allows updating the forwarding database locally. This solution would not be possible without the use of a source routing protocol for data forwarding. We propose to use SPRING for this purpose. It enables the ingress nodes to locally change the network routes without having to update the forwarding tables of midpoint devices.

The presented technique allows achieving a global, network-wise, traffic optimization. It was evaluated against a linear programming model and was shown to compute a nearoptimal routing in all the evaluated networks. The utilization of the most loaded link is always kept close to the value provided by the LP model. Moreover, the lengths of network paths are kept close to the lengths with shortest path routing. At the same time, the computational times do not surpass a couple of seconds in any of the real backbone networks used for evaluation.

Chapter 6

Consume less and better: evaluation and impact on transported protocols

In the previous two chapters, we presented two methods to increase the energy efficiency of backbone networks. The first one, which we called SegmenT Routing based Energy Efficient Traffic Engineering (STREETE), acts by putting unused resources to sleep whenever the network is at low utilization. In the second, we proposed a means to achieve a near-optimal distribution of the load in the network while keeping a low computational and communication overhead. The latter solution can be used separately, to push the limits of the network and avoid premature updates to higher data-rates that consume more power. Furthermore, this load balancing technique can also be incorporated into our STREETE framework to obtain a solution that acts both by minimizing the number of active resources and by optimizing the traffic within these active resources.

We start this chapter by evaluating the combination of the previously proposed techniques: STREETE combined with load balancing (LB). The proposed solution, which we call STREETE-LB, can compete with linear programming models both regarding turned-off links and in its ability to keep the network out of congestion.

Unfortunately, achieving such performance comes at the cost of frequent changes of network paths. Not only the algorithm has to reroute the flows each time a link is turned on or off, but even a small variation in network conditions may induce a reorganization of the paths due to the inclusion of the load balancing technique. To estimate the impact of such frequent route changes, we conduct a detailed evaluation on our network testbed. In particular, we evaluate how the change in the network delay due to moving a flow between two paths impacts the congestion control mechanism of TCP.

Consume less and better: STREETE-LB

In this section, we evaluate the combination of previously proposed techniques that we call STREETE-LB: STREETE with load balancing technique LB.

The combination of the two algorithms is straightforward. The STREETE algorithm (Alg. 2) presented in Chapter 4, (Section 4.2.3) remains unchanged. Only the logic behind the steps which simulate the routing of the traffic into the network must be modified. Unfortunately, this change is non-negligible because it drastically impacts the computational complexity on the critical path of the STREETE framework.

CHAPTER 6. CONSUME LESS AND BETTER: EVALUATION AND IMPACT ON TRANSPORTED PROTOCOLS

To reduce the influence of this computation, we use two different precisions for the Karakosta's algorithm. A low precision of ǫ " 0.2 is used during each iteration of the STREETE framework, i.e. when a link extinction/ignition is simulated. A higher precision, of ǫ " 0.1 is used to compute the final routing, which will be sent to the SDN switches. Performing less accurate computation during the iterations of STREETE allows for drastically improving the computational time because the complexity of the algorithm increases quadratically with the precision.

We use the same MILP model as in Chapter 4 (Sec. 4.3.2) for this evaluation.

Computational time

Taking into consideration that we introduced a complex computation into the critical path of the STREETE framework, the first parameter evaluated during our evaluations is the computational time. Tab. p ˚˚q-*CPLEX didn't find the optimal solution in the maximum allocated time (2h) **CPLEX wasn't able to initialize the model Table 6.1: Maximum computational time In our opinion, STREETE-LB is not fast enough in the big, 200-node network. In the worst case, it took a maximum of 20 minutes to compute a solution. Nevertheless, we believe that the 15 seconds on the 75-node CORONET network topology are promising. In fact, anticipating some conclusions detailed later, we affirm that very frequent reroutings may be dangerous for the network stability. More details on this matter are given in the second part of this chapter. STREETE-LB is thus capable of computing a solution on any of the evaluated real backbone networks in adequate time.

Performance at high network load

The biggest problem of the STREETE framework presented in Chapter 4 was the bad performance under high network load. Fig. 6.1 shows the behavior of the STREETE-LB mixed solution in this case. We do the same evaluation as previously where the network load increases continuously until congestion is detected.

The mixed solution can avoid congestion for almost the same time as CPLEX. Some notable exceptions can be seen in the cases of AT&T and USNET networks. We analyzed these scenarios in detail and concluded that it is due to the approximate nature of the Karakosta's algorithm and the low precision of 0.2 used by STREETE. Increasing the precision of the algorithm leads to better results at the cost of longer computations. It is a trade-off to be considered. It may be worth increasing the accuracy on small networks if sub-second computational time is not needed. For example, Fig. 6.2 illustrates the performance on the USNET network with a precision of ǫ " 0.1. The additional precision enables improving the quality of the results at a drastic increase in the computational complexity. The maximum time taken by STREETE-LB in this case was of approximately 18 seconds. For comparison, in the previous section, we showed that STREETE-LB takes approximately 0.7s with a precision ǫ " 0.2.

From Fig. 6.1 and 6.2, it may look like STREETE-LB behaves much worse than CPLEX in terms of active links. We observe links being switched on in bursts. For example, the biggest such burst is seen on the Germany50 network at around t " 3.5. Analyzing this behavior revealed that it is due to the much more conservative nature of STREETE compared to the CPLEX model used for validation. In particular, our solution uses a double threshold (60% and 80%) to decide if it is worth turning links off /on and to avoid link flapping1 . Fig. 6.3 shows that setting the two thresholds close to the link congestion makes STREETE-LB behave similarly to CPLEX for a longer period. However, using a double threshold allows to improve the stability of the framework and avoid frequent change in the paths of network flows.

Performance with realistic traffic matrices

STREETE alone showed real energy savings when tested with realistic traffic matrices. Nevertheless, we may expect to have better savings if the framework includes a load balancing technique. Surprisingly for us, the evaluation did not confirm this intuition. Fig. 6.4 shows the results in 3 representative cases. First, is represented the distribution of load in the NSFNet network. In this case, STREETE-LB behaves better than its shortest-path based equivalent (presented in chapter 4) because the overall network load is initially high compared to other networks. In this case, load balancing techniques came in handy and allowed to turn off more links. This is visible especially in the second half of the day (between tm " 6 and tm " 12)

A second case is seen on the Geant network. STREETE-LB behaves worse than its shortest path based equivalent. More links are kept active in the network. Nevertheless, this is not necessarily a bad behavior. The additional links were ignited to reduce the load on a couple of highly utilized links, which were close to congestion. The shortest path routing was unable to handle this case and avoid network congestion efficiently.

The latest case, illustrated on the Italian network, shows a distinct advantage of STREETE-LB. In this case, the algorithm was able to both slightly reduce the number of active links and to keep the network at relatively low utilization. CHAPTER 6. CONSUME LESS AND BETTER: EVALUATION AND IMPACT ON TRANSPORTED PROTOCOLS

Impact of frequent route changes on TCP flows

Throughout this manuscript, we have presented our framework for increasing the energy efficiency of IPoWDM backbone networks by employing frequent network re-optimizations. The paths of network flows constantly change for this purpose. However, we completely ignored that rerouting flows can have a severe impact on the transported protocols. In particular, a drop in throughput can occur if TCP is the transport protocol.

During the validation of the STREETE framework on our network testbed (presented in section 4.4), we observed uncontrolled oscillations of link states: on<->off. These oscillations occurred in rare cases when: i) TCP was used, and ii) the delay of the network paths differed in two or more orders of magnitude.

The reason of this oscillation was that TCP reduced its throughput when shifted to a new route. STREETE quickly detected this reduction of network traffic as an opportunity to switch some links off and save energy. Nevertheless, the drop in the speed of the TCP flow was only temporary. TCP quickly recovered from the drop and forced STREETE to turn-on links to provide enough capacity for the additional demand. Turning the link on has shifted flows towards new network paths, which produced a new drop in network bandwidth.

In fact, the use of double thresholds by STREETE as triggers to turn links on and off helped to avoid this case to a certain extent. This is the reason why the oscillation only occurred in extreme cases: when the delays of paths differed in orders of magnitude.

In this section, we use our networking testbed to perform an experimental analysis of this case. In particular, we evaluate how the default implementation of the TCP protocol in the Linux kernel reacts to the fact of frequently rerouting the network flows. Our goal is to find a rerouting frequency which is safe and avoids the case above.

Background

Rerouting and congestion control

The TCP's congestion control algorithm, defined in the RFC 5681, is an important, and one of the most complex, features of modern TCP implementations. This algorithm tries to split the network capacity fairly among all the flows traversing it. Under such algorithm, the sender keeps a congestion window that is dynamically modified depending on the network conditions. The source cannot send more data than what fits in this window during a Round-Trip Time (RTT). The maximum instantaneous bandwidth, B, of the TCP connection parameters, is thus limited by the size of the congestion window: B " W ¨M SS{RT T , where W is the size of the congestion window in segments, M SS is the maximum segment size in bytes.

TCP was initially designed for standard IP routing assuming that all packets follow the same route towards a destination. Packet reordering and route changes were considered rare. However, in an SDN network, the controller may frequently shift a TCP flow to an alternative path to optimize the overall network throughput. The route change can impact the throughput of a TCP flow in two different ways:

• When the new route has higher RTT, the sender increases the size of the congestion window to maintain the same sending rate. For example, if the RTT doubles, the 6.2. IMPACT OF FREQUENT ROUTE CHANGES ON TCP FLOWS bandwidth will be halved and will gradually increase with the growth of the TCP congestion window; a direct application of the equation B " W ¨M SS{RT T .

• The receiver sees packets arriving out of order if the new route has a lower RTT. TCP's congestion control algorithms assume the worst-case scenario and view this as an indication of packet loss due to congestion. Figure 6.5 illustrates the problem considering a sample backbone network. The link ab becomes available for transmission and hence packets 2 and 3 take a route shorter than packet 1. The packets arrive out of order at the receiver who uses duplicate ACKs to notify the sender about a problem. The sender reduces the size of the sending window to avoid congestion, hence decreasing the transmission rate. Given that a large part of network traffic is often carried by a small number of large, long-lived flows [START_REF] Qian | A flow-based performance analysis of TCP and TCP applications[END_REF], rerouting these flows may significantly reduce the overall network throughput.

Congestion Control Algorithms

The analysis focuses on the impact of route changes on the default TCP congestioncontrol mechanism in the Linux kernel. As of writing, the default algorithm used in all the tested devices is Cubic, with a fallback to Reno, including devices using kernel versions 3.2, 3.13, 4.4 and 4.7.

CHAPTER 6. CONSUME LESS AND BETTER: EVALUATION AND IMPACT ON TRANSPORTED PROTOCOLS

RENO The standard TCP congestion control mechanism is Reno, which is still the fallback algorithm in the Linux kernel. This algorithm is straightforward and comprises two phases: 1) the slow start phase, where the window size doubles each RTT; and 2) the congestion control phase where the window size increases by one each RTT or is divided by two under packet loss.

The slow start phase allows for a fast increase in the window size at the beginning of communication. It corresponds to the spike at time 0 in Figure 6.6. In this work, we ignore the slow start.

Although TCP Reno behaves well under small Bandwidth x Delay Product (BDP), it severely underutilizes the channel on long fat networksi.e. networks with high data rate and high delay -because it linearly grows the windows by one every RTT when recovering from packet loss. In Figure 6.6, Reno takes more than a minute to grow the congestion window and fill a 100Mbps link with an RTT of 50ms.

CUBIC The Cubic TCP algorithm [START_REF] Ha | CUBIC: A New TCP-friendly Highspeed TCP Variant[END_REF] aims to avoid the shortcomings of Reno and achieve high data rates in networks with large BDP. At the same time, when Cubic detects a network with small BDP, it tries to mimic Reno's behavior emulated by a mathematical model. This happens, particularly in local high-speed, low-delay, networks.

As its name suggests, the algorithm grows the congestion window by using a cubic function of the elapsed time from the last loss event y " p∆tq 3 . More precisely, using a shifted and scaled version y " 0.4 ¨p∆t ´RT T ´Kq 3 `Wmax . In this equation, ∆t is the time passed from the last loss event, W max is the size of the congestion window just before the loss event. K " pW max {2q 1{3 is a parameter that depends on W max .

Cubic is also less aggressive in reducing the congestion window at a loss event. Compared to Reno, which halves the window, Cubic reduces it by 20%.

Estimating the Behaviour of TCP Cubic under Route Changes

Recovering from a Loss The growth function, y, used to increase the congestion window depends mainly on W max , which makes it easy to estimate the time taken by TCP cubic to restore its congestion window after a loss. To do that, we ignore the insignificant dependency on RTT in the Cubic function and solve W max " y " 0.4 ¨p∆t ´Kq 3 `Wmax . We obtain ∆t " K " pW max {2q 1{3 .

Moreover, the RTT and the bottleneck bandwidth are used to determine the maximum window size. Table 6 * the default maximum size of the kernel buffer is too small to allow full speed communications with RT T " 500ms. In this case, the transmission speed is limited by the size of the kernel buffer; approximately 2100 segments. Table 6.2: Estimated W max and time needed to recover after a loss, 100Mbps bottleneck link.

This estimation is valid only if no further loss is detected. Figure 6.7 contains a counter-example where TCP would reach W max at approximately t " 36s, but a loss happened at "34s and forced the congestion control algorithm to reduce the size of the congestion window.

While particularly interested in the time needed to recover from a loss, we note that route changes may generate false loss events when the TCP flow shifts towards a shorter route. At such time, the size of the congestion window decreases, and cubic tries to grow it back. Intuitively, the bandwidth of a TCP flow may drop significantly if the SDN controller attempts a second re-optimization in the meantime.

Relevant Linux Implementation Details

The TCP implementation in the Linux kernel incorporates a lot of standard and nonstandard optimizations [START_REF] Sarolahti | Congestion Control in Linux TCP[END_REF]. One of the non-standard features, which is very important for our work, is the possibility to undo an adjustment to the congestion window. This implementation tries to distinguish between packet reordering and loss by using the "Timestamp" TCP option. When the sender detects that a past loss event was a false positive due to packet reordering, the algorithm reverts the window size to the value used before the reduction. As a result, packet reordering may have much less impact compared to standard TCP.

CHAPTER 6. CONSUME LESS AND BETTER: EVALUATION AND IMPACT ON TRANSPORTED PROTOCOLS

Multiple TCP Flows on a Bottleneck Link

As mentioned earlier, TCP cannot send more data than the size of the congestion window per RTT. As a result, when the sender's window W is smaller than W max , TCP spends part of the time waiting for acknowledgments without sending any data. Figure 6.8 illustrates this case, summarizing data collected using the tcpdump application to capture the packets of a TCP flow over a second. The figure shows the times when packets were captured. Approximately 2/3 of the time, there was no packet passing through the network because the congestion window is too small (only 150 segments). Under such conditions, a congestion window of 431 segments was needed to fill the bottleneck link.

If a route change happens when a flow is waiting for acknowledgments, there is no reordering problem since no packet is sent. Hence, the probability that a TCP destination will receive packets out of order increases as W approaches W max . Respectively, when TCP backs off and lowers its sending rate by reducing W , it also reduces the probability to be impacted by the rerouting.

If a large number of TCP flows share the same bottleneck link, the flows spend a lot of time waiting for the ACKs. Hence, rerouting a large bunch of TCP flows at the same time may have less impact on the overall network bandwidth than rerouting a single TCP flow.

This TCP behavior may change in the future. The benefit of smoothing the transmission over time by employing traffic pacing was shown to have a beneficial effect on network performance [START_REF] Gharakheili | Edge versus host pacing of TCP traffic in small buffer networks[END_REF] and state-of-art congestion control algorithms, like BBR [START_REF] Cardwell | BBR: Congestion-Based Congestion Control[END_REF], use this technique to avoid the bufferbloat problem.

Experimental Evaluation

Experimental Setup

We consider backbone, highly over-provisioned, networks where resource capacity is not a limiting factor. The transmission speed is either bounded by a congested link in the aggregation, or by a very high propagation delay, i.e. by the size of the maximum allowed congestion window. No congestion ever occurs on the backbone links.

We construct the topology presented in Figure 6.9. The examined scenario consists of multiple TCP sources sending data to remote clients. The transfers pass through a backbone network employing traffic engineering: the two parallel 10Gbps links. The traffic is routed through two alternative paths within the backbone network, emulated

IMPACT OF FREQUENT ROUTE CHANGES ON TCP FLOWS

.9: Testbed overview by these two links. The paths have different delays. One of the backbone paths has no additional delay (0ms), while the second path induces an additional delay of X ms to simulate a longer route. We use tc-netem for this purpose. Each of the two paths (links) has sufficient capacity to transfer the flows. The bottleneck capacity is outside the backbone network. Congestion never happens on these two links.

The sources are aggregated in groups. The flows from 2 different groups never share a bottleneck point. However, two flows of the same group compete for the bandwidth allocated to the group. Each group has a different path RTT, uniformly distributed in the interval [0ms, 120ms], which adds to the delay of the backbone paths. The goal is to recreate the scenario where flows with different end-to-end delay coexist in the backbone network.

Concerning the physical infrastructure: nodes in the topology correspond to Ubuntu 14.04 Linux servers running Open vSwitch2 v2.4 (manually compiled for Ubuntu 14.04). The network is controlled by the ONOS SDN controller (v1.7) via an out-of-band control connection. We wrote an ONOS SDN application to reroute the flows between the two backbone links.

The backbone links use 10G optical Ethernet interconnects. The connections to the TCP sources use 1G Ethernet ports. In the physical topology, both 10G and 1G network interconnects pass through Dell Ethernet switches. The point-to-point links are emulated using VLANs on these hardware switches. This permits to reconfigure the network topology remotely. Unfortunately, the queuing disciplines on these switches are opaque and cannot be fine tuned. To avoid perturbations, we use tc-tbf (Token Bucket Filter) to limit the speed of each group to 100Mbps. In such a way, the data passing through a hardware switch is always much below the link capacity. Moreover, this allows avoiding perturbations due to the Ethernet flow control mechanisms: PAUSE frame. We use a drop-tail bottleneck queue having the size 0.1 * BDP. TRANSPORTED PROTOCOLS

Rerouting Independent Flows

This section analyses the impact of rerouting multiple independent TCP flows and how the total backbone throughput changes as a consequence of rerouting.

We generate 20 unsynchronised flows, one flow per group, that start at random times within a 30-second interval. We run the transfer for 400 seconds to allow TCP flows to converge to a steady state. After that, we reroute the traffic every 200 seconds and measure how the aggregated throughput changes at during rerouting. At t " 600, the flows are rerouted towards the path with lower delay. Respectively, at t " 400 and t " 800, the flows are rerouted towards the longer path. This experiment confirms our expectations, that rerouting the flows impacts their throughput both when moving towards a longer route and when moving towards a shorter one.

Nevertheless, packet reordering, which happens at t " 600, has a less pronounced impact than expected. Theoretically, Cubic would reduce the transmission window to 80% of its size when a loss is detected. Then it would gradually increase the window back to the size before the loss. However, the Linux TCP can detect packet reordering in some cases. In particular, this happens when the difference of delay between two routes is small compared to the delay of the fastest route. Hence, a slight variation of delay, like 10ms, has a marginal impact on the total throughput of the flows. The next section gives more insights on this optimization.

Rerouting towards the link with higher RTT substantially reduces the aggregate bandwidth of the 20 flows (t " 400 and t " 800). The larger the delay difference between the two routes, the bigger the drop. In this case, rerouting is transparent to the congestion control algorithm. The drop comes from the unexpected increase of the delay. As a consequence, the size of the transmission window must be increased to allow transmission at 6.2. IMPACT OF FREQUENT ROUTE CHANGES ON TCP FLOWS the same speed.

Rerouting Flows Sharing a Bottleneck Point

To evaluate the impact of sharing a bottleneck point where flows inside a group compete for bandwidth, we fix the RTT of the second path to 50ms and vary the number of flows per group. With one flow per group, 20 flows traverse the network whereas, under 9 flows per group, there is a total of 180 flows. Figure 6.11 shows how competing flows impact the recovering speed after rerouting. The bandwidth drop caused by rerouting towards a shorter route becomes quickly insignificant (t " 600s) in contrast to rerouting towards a longer path (t " 400s). With the increase in the number of flows sharing a bottleneck link, each of these flows gets a smaller proportion of the total bottleneck bandwidth. The flows hence spend more time waiting for acknowledgments than actually sending data. At rerouting, fewer flows see their packets arrive out-of-order. Moreover, the flows that do not experience out-of-order arrivals can increase their sending rate by using the capacity released by flows that have just reduced the sending window. As a consequence, the total aggregated throughput on the backbone links is almost not impacted.

When rerouting flows towards a longer path, the aggregate bandwidth recovered slightly quicker when the number of competing flows per group increases. It is due to nonlinear growth function used by Cubic. Having more flows increases the probability that some of them will be in the "aggressive growth" phase of the cubic function.

One TCP Flow under Frequent Rerouting

The previous sections showed that packet reordering has negligible impact compared to the increase of RTT. In this section, we assess whether very frequent route changes may CHAPTER 6. CONSUME LESS AND BETTER: EVALUATION AND IMPACT ON TRANSPORTED PROTOCOLS reorder enough packets to perturb the congestion control algorithm even if the delay difference between the two considered routes is small compared to the RTT.

While focusing on analyzing a single TCP flow, we use iperf to transfer 2Gbytes of data and measure its mean bandwidth (on testbed from Figure 6.9). A big enough transfer size was chosen to reduce the impact of the slow start phase on the mean throughput. Considering a maximum bottleneck throughput of 100Mbps, each transfer takes approximately 3 minutes if transferred at full speed. The flow is frequently rerouted between the two paths. We tested with periods of rerouting going from once every 15 seconds, to as low as once every 0.1s. Frequent route changes have a large impact on the performance of the congestion control algorithm. When the traffic is rerouted once every 0.1s, the throughput is as low as 35% of the throughput without rerouting. We can also observe that with a route change every 2 seconds, the throughput is around 85% compared to the throughput without rerouting. Although from a practical point of view we believe that these frequencies of rerouting are extreme (and not very realistic), they were included here to evaluate the limits on traffic rerouting. To re-optimise the network at such frequencies, a lot of control messages must be transmitted between the SDN controller and the switches, creating a flood of control traffic. Moreover, the network optimization problems are usually computationally intensive and take the time to find a good solution.

IMPACT OF FREQUENT ROUTE CHANGES ON TCP FLOWS

It is worth noting that the biggest drop in throughput is observed when a second rerouting happens before Cubic recovers from the first rerouting. Previously, we gave an estimation of the recovery time in Table 6.2. Figure 6.13 shows two interesting results for higher RTT: 1. Frequent rerouting has a beneficial effect under an RTT of 170, observed at period " 0.6s (the first ellipse) where the mean bandwidth of a flow rerouted every 0.6s is higher than the average bandwidth of a flow that is always transmitted over the same path.

2. Under RTT=480, the bandwidth of the flows is also less impacted when rerouted frequently.

These results are consistent among the multiple transfers. The error intervals are very tight and difficult to see in the figure. To explain this behavior, we analyze in detail the evolution of the congestion window and packets traversing the network. We choose to concentrate on the points marked with ellipses in Figure 6.13.

Inspecting the beneficial effect at RTT=170 Figure 6.14 gives more insights on this case. The dashed line shows the evolution of the congestion window without rerouting. At times t " 23, t " 43, etc, the congestion control algorithm does not behave as TRANSPORTED PROTOCOLS expected. Instead of reducing the congestion window by 20% as dictated by the Cubic algorithm, the drop is much higher. It is because Cubic claims bandwidth too aggressively. Hence a huge number of packets are lost when reaching the bottleneck capacity.

Moreover, Linux TCP does not employ a multiplicative decrease technique of reducing the congestion window. Instead, it reduces it additively at every second duplicate ACK received. These two causes together imply a bad performance at RTT=170.

Rerouting the flow in the meantime perturbs the Cubic protocol and avoids this unwanted behavior. It is due to the optimization in the Linux kernel which detects out-of-order deliveries thus reducing the impact of the rerouting. The evolution of the congestion window in the case when the route changes every 0.6s can be seen on the continuous, blue, line of Figure 6.14. For example, at t " 8, a duplicate ACK is detected as being due to reordering and not to a loss, the congestion window is restored to the size before the reduction. We mentioned in an earlier section that the TCP sender might "miss" a rerouting because the sender alternates between sending packets and waiting for ACKs. If the route change happens when the sender waits for ACKs, no packets will arrive out-of-order. The blue line illustrates this case. At small window size, between t " 0 and t " 30, the sender spends a lot of time waiting. As a result, the probability to be impacted by a rerouting is small. The bigger the congestion window, the higher the probability to be impacted by a rerouting. Starting with t " 120, an equilibrium is created. The sender struggles to grow the window any further: any rerouting has a high probability of reordering packets.

Inspecting the unexpected behavior at RTT=480 Figure 6.15, which analyses the evolution of the congestion windows, shows that the window remains constant if the routes do not change. This behavior is expected as the transmission is limited by the size of the congestion window, which in turn is constrained by the size of the in-kernel buffer reserved for the TCP connection.

If we compare the evolution of congestion window in case of rerouting, we observe that the Linux Kernel's optimization, which detects out-of-order packets, is more susceptible to work as expected at frequent route changes. This unexpected behavior is consistent among multiple transfers. However, rerouting once every 15 second allows the flow to converge towards the maximum window size. Any bigger rerouting period (20s, 30s, etc.) will have less impact on the average throughput. The worst case scenario occurs at a period of 14s.

IMPACT OF FREQUENT ROUTE CHANGES ON TCP FLOWS

Conclusion

In this chapter, we started by evaluating the combination of the techniques presented in the previous chapter, which we call STREETE-LB. We showed that it could achieve nearoptimal solutions both regarding active links and in its capacity to keep the network out of congestion. We managed to avoid the drastic increase of the computational complexity by using a variable precision during the execution of the algorithms.

After that, we analyzed the impact of frequent route changes on the Cubic TCP flows. We performed an extensive analysis of the behavior of cubic TCP on a real testbed to find a safe rerouting frequency. Our study confirmed that at a low aggregation level when a limited number of TCP flows share a path, the rerouting reduces the speed of the TCP flow. Nevertheless, the reason for this behavior is opposite to the reason that is usually evoked by the networking community.

It is considered that packet reordering will make TCP falsely assume a congestion in the network and reduce its speed. In reality, the engineers implemented a set of non-standard optimizations that detect this case and reduce the impact of reordering to a minimum. Moreover, the impact of reordering decreases as the aggregation level increases. This is because the probability of affecting a particular TCP flow decreases.

At the same time, we recorded a bandwidth drop when the flows are rerouted towards a longer path. The increase of delay artificially limits the speed of TCP until the congestion window "catches up" with the new network delay. The time needed by TCP to converge to a steady state depends on the difference of network delay between the two routes and the congestion control mechanism used by TCP. For example, in the case of the Cubic congestion control, approximately 20 seconds are enough, even with a very high difference in network delay, due to its fast growth of congestion window.

In any case, the traffic engineering SDN applications must be made aware of the short drop of network throughput following a rerouting and must limit the frequency of CHAPTER 6. CONSUME LESS AND BETTER: EVALUATION AND IMPACT ON TRANSPORTED PROTOCOLS network re-optimisations. Otherwise, this throughput drop caused by the reaction of the TCP congestion control mechanisms may be incorrectly interpreted as a need for further optimization of network flows, which can cause uncontrolled oscillations of traffic between network paths.

Chapter 7 Conclusion and perspectives

Conclusion

Information and communication technologies (ICT) are at the core of the digital economies and increasingly important part of all of our personal and professional lives. With this drastic rise in communicating applications, the network operators are in need to deploy additional capacity to their network to support predicted and unpredicted traffic growth. The resulted increase of the energy consumption has not only negative environmental consequences but also an economic impact. Major ICT players, including Google, Microsoft, and Facebook, are already deploying solutions to increase the efficiency of their networks. Nevertheless, these solutions rely on full control of the communicating applications and are limited to private deployments. They are suitable for cases where the communicating applications are not under the network operator's control. This thesis investigated the problem of improving the energy efficiency of operator backbone networks by changing the paths of network flows transparently to the communicating applications.

The first contribution of this thesis is the SegmenT Routing based Energy Efficient Traffic Engineering (STREETE) framework for aggregating the flows over a subset of links and turning the other links off. It is an online solution that uses two different views of the network to speed-up the execution. This is especially handy when there is a need for rapidly reacting to an unexpected burst of network traffic; a case that is mostly overlooked by the research community. To further increase the speed of our algorithms, we implemented them using state of the art dynamic shortest path algorithms. Moreover, relying on shortest path computations, together with the SPRING source routing protocol, allows keeping the control traffic overhead at a minimum. The evaluation of STREETE on real backbone network topologies with real traffic matrices enabled us to conclude that good results are obtained at low traffic load both in the number of turned-off links and in its ability to avoid network congestion.

To improve the quality of STREETE under heavy load, we searched for a SDN-based traffic engineering technique for optimizing the network utilization. We first presented an unsuccessful attempt to build such a solution using a link cost function. Later we presented a second solution, which we name "LB". It enables near-optimal load balancing of traffic on the network thanks to a careful combination of centralized and distributed computations.

The centralized computation performed by LB at the SDN controller consists of a state of the art algorithm for approximately solving the maximum concurrent flow problem. It can achieve near-optimal load balancing of traffic in the network. Our contribution is in proposing a means to apply the result of this centralized optimization into the network devices. Our solution keeps a low communication overhead between the SDN controller and the SDN switches. To achieve this goal, part of the optimization is made on the network devices. This allows for locally computing the paths of the flows and update the forwarding databases without the need of centralized orchestration. Similarly to STREETE, we rely on the source routing provided by the SPRING protocol to update the network paths atomically on a single device: the ingress SDN switch. As a next step, we combined STREETE with the LB load balancing technique and proposed the STREETE-LB framework. Overall, this combination revealed excellent results both concerning the number of turned-off links and regarding load distribution in the network. Nevertheless, to avoid an explosion of the computational complexity, we had to reduce the precision of the algorithms used by the load balancing technique, leading to sometimes sub-optimal, but still promising results.

We took the challenge of implementing and evaluating the STREETE framework on a network testbed using real SDN hardware and the ONOS SDN controller. This action allowed us to discover an oscillation due to the elasticity of TCP flows which did behave well under the frequent route changes made by STREETE. To find a safe rerouting frequency, we performed an in-depth evaluation of the behavior of TCP flows under frequent route changes. Contrary to popular belief, the experiments showed that packet reordering incurred by rerouting towards a path with lower RTT has a marginal impact on the bandwidth of TCP flows. This result is partially due to non-standard optimizations introduced by the Linux kernel developers. A degradation of throughput was only observed under very high rerouting frequencies. However, even this effect decreases with the increase of the flow aggregation level. In the meantime, shifting the traffic towards a path with longer RTT has an adverse influence on the bandwidth of TCP flows. We conclude that SDN-based traffic engineering techniques must be constrained to avoid significant variations in the end-to-end delay when rerouting the flows. Alternatively, if the increase of delay is unavoidable, the traffic engineering SDN applications must be made aware of the short temporary of network throughput which follows the rerouting. Otherwise, this short drop of throughput may be wrongly interpreted as a sign to perform a network re-optimization.

In addition to the scientific contributions, we took special care to enable the reproducibility of the results presented in chapters 4 and 5. All the results, except the ones based on the network tested, can be reproduced by following a couple of simple steps on any Linux computer. Moreover, an Android application was developed to allow interactive interaction with the proposed algorithms.

Perspectives

At critical times in the course of this thesis, some research directions have been preferred over others, leaving entire territories unexplored. Here we describe some of the areas that can be explored in the future.

PERSPECTIVES

Continuing the evaluation and implementation As a short term perspective, we would like to continue the implementation and the evaluation of the proposed solutions. The proposed load balancing technique and STREETE-LB were not validated on the real testbed. Some technical difficulties in the implementation may have to be solved to split the demands into multiple paths.

Moreover, we did not evaluate the overhead introduced by the explicit paths into the headers of network packets due to the use of the SPRING/Segment Routing. A huge advantage of SPRING over other source routing protocols is its ability to compress the paths stocked in the header, meaning that there is no need to list the intermediate nodes explicitly. Finding a good and fast technique for path compression, which respects the needs of the SPRING protocol, is a research direction to be considered.

The analysis of the behavior of TCP flows presented in the last chapter was done considering only the cubic congestion control algorithm. For the completeness of the study, we should consider testing the behavior of the compound algorithm in Windows and of the newreno algorithm in FreeBSD. This would cover the absolute majority of the big, long-lived, flows in the internet. In particular, it would be interesting to verify if the implementations in FreeBSD and in Windows are also robust to packet reordering.

Extending the STREETE framework Medium term perspectives include the extension of the STREETE framework to handle additional constraints.

We believe that the most important improvement is the inclusion of various link speeds. At this point, the decision of which link to shut down or to turn on does not take into consideration that it may be better to switch off multiple slow links instead of a single, high data-rate one. The load balancing technique presented in Chapter 5 is already capable of working with multiple link speeds. As a result, the main objective would be to find a more energy-aware metric for turning off compared to the number of links.

Another relevant problem of the STREETE framework is due to the extensive growth of network path as a result of rerouting towards longer routes. Future research may consider this aspect. We already mentioned that it is possible to use "graph spanners" for this purpose, but did not yet validate this solution.

Link failure is also an aspect that we did not take into consideration. In particular, due to the reduction of the number of active links, a fiber cut can disconnect the network. To avoid this problem, protection links may be computed in the network. We believe that link failure, similarly to the issue of path extension, is better treated at a topological level, by forcing some links to be always active. This would slightly increase the energy consumption but provide a much better resiliency. Moreover, we believe that these two problems may be solved together, the computed graph spanner for the previous solution may already provide a satisfactory level of redundancy.

Focusing on aggregation networks Another perspective would be to study the applicability of STREETE outside the backbone networks.

Devices of backbone networks consume substantial amounts of energy. However, the number of such devices is relatively small. An additional way to reduce the energy consumption would be to move closer to the access networks. Doing small energy savings on a large number of devices is a good way to cut off the overall consumption. However, STREETE is not suitable for access networks. It relies on the availability of multiple alternative paths between the network devices. In access networks, this is usually not true. That is why protocols similar to 802.3az reign at this level. However, in between the access and the core, lay the aggregation and metro networks. STREETE may be a viable solution at this level. However, due to a relatively large number of network devices, it may be needed to virtually partition these systems in smaller subsets to reduce the computational complexity.

Deadline-driven network optimization Finally, as a long-term research perspective, it would be interesting to study the deadline-driven network optimization techniques: given a certain deadline, find the best possible solution achievable in the provided time. This field is particularly interesting in the context of SDN networks, where meeting a given deadline may be more important than the accuracy of the solution. We may use Chapter 5 as an entry point towards this research direction. It is possible to click on a node (Fig. 3a) to select it. Doing so, filters on the the total flow originating from the selected node towards all other nodes in the network. Moreover, a new slider appears at the top-left corner. It allows to increase/reduce this flow. However, this functionality is in an early stage of development: the changes are applied into the network, but the slider does not keep the state.

To deselect the node, it is sufficient to click on it a second time. While having a node selected, it is possible to click on a second node to visualize the paths taken by the flows between these two nodes and the associated network flow (Fig. 3b).

Figure 1 . 2 :

 12 Figure 1.2: Image generated by simulations which illustrates the state of the links in the the Italian network.

Figure 1 . 3 :Figure 2 . 1 :

 1321 Figure 1.3: Access app using Google Play https://play.google.com/store/apps/details?id=me.carpa.streete

Figure 2 . 2 :

 22 Figure 2.2: The terabit capable part of the Geant network http://www.geant.net/Network/The_Network/Pages/Terabit-Network.aspx

Figure 2 . 3 :

 23 Figure 2.3: Insights on the WDM layer

Figure 2 .

 2 Figure 2.4: TDM layer at node A

Figure 2 . 5 :

 25 Figure 2.5: The architecture of IPoOTN and IPoWDM networks

Figure 2 . 6 :

 26 Figure2.6: Energy consumption of a network switch measured at idle during 300s and at full load afterwards. Source :[START_REF] El | Energy efficiency in very high-performance computing : application to fault tolerance and data broadcasting[END_REF]

  Routes of b (assigned)

Figure 2 . 7 :

 27 Figure 2.7: Example of IGP metric assignment for traffic engineering

Figure 2 . 8 :

 28 Figure 2.8: The architecture of SDN

Figure 2 . 9 :

 29 Figure 2.9: Rerouting towards a lower RTT ñ packet reordering.

  [START_REF] Feng | Packet reordering in high-speed networks and its impact on high-speed {TCP} variants[END_REF] [71][START_REF] Ludwig | The Eifel Algorithm: Making TCP Robust Against Spurious Retransmissions[END_REF].

CHAPTER 2 .Figure 2 . 10 :

 2210 Figure 2.10: SPRING protocol.

Figure 3 . 1 :

 31 Figure 3.1: Graph modelization of the network

Figure 3 . 2 :

 32 Figure 3.2: Example of linear program in R 2

  Consider the network from Fig.3.3. The operator observed that as much as d a,b " 9Gbps traffic is entering the network at node a and leaving at node b. Respectively, d a,c " 1Gbps traffic goes from a to c.

3. 3 . 4 Figure 3 . 3 :

 3433 Figure 3.3: Paths which can be taken by the packets of the demands d a,b and d a,c

Claim 3 . 3 . 1 .

 331 For any link length function l : E Ñ R `, and any feasible concurrent flow of throughput λ, we have ř ePE lpeqcpeq ř pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j ě λ. Note 1: We assume ř pi,jqPV 2 :d i,j ą0 lpSP i,j qd i,j ‰ 0. This condition is true in all the instances of the problem which are used in this thesis. Note 2: Some authors use the term "volume of the network" for referring to the term ř ePE lpeqcpeq Proof. As per link capacity constraints (3.2) of the primal LP, if a concurrent flow of throughput λ is feasible, the amount of flow which passes through a link never exceeds the capacity of this link: cpeq ě ř P PP:ePPf pP q. As a result, we have:

CHAPTER 4 .

 4 CONSUME LESS: THE STREETE FRAMEWORK FOR REDUCING THE NETWORK OVER-PROVISIONING matrix.

4. 1

 1 . GENERAL OVERVIEW b) Full network (G) a) Network with links off (G 1 ) loaded links (CL G 1 ) e) (Ordered) candidate links f) Link turned on

Figure 4 . 1 :

 41 Figure 4.1: STREETE-ON: simulating the all-on network view to select the best link(s) to turn on.

Figure 4 . 2 :

 42 Figure 4.2: Chain of turned-off links

CHAPTER 4 .

 4 CONSUME LESS: THE STREETE FRAMEWORK FOR REDUCING THE NETWORK OVER-PROVISIONING

Figure 4 . 3 :

 43 Figure 4.3: Topologies evaluated with real traffic traces

Figure 4 . 4 :

 44 Figure 4.4: Topologies evaluated with generated traffic

Figure 4 . 5 :

 45 Figure 4.5: The heat-map of the link utilization during a day in the NSFNet network. Also illustrating the links which are off (shown in black)

Figure 4 . 6 :

 46 Figure 4.6: Packet loss.

Figure 4 . 7 :

 47 Figure 4.7: Links utilisation without and with STREETE.

Figure 4 .

 4 Figure 4.8 shows the state of network links in each of the 6 network topologies evaluated with realistic traffic traces. For each network, the leftmost figure shows the utilization of the links when classical shortest path routing is used. The rightmost figure corresponds to the state of the network when our STREETE framework is used. For each figure, the black area represents the links with utilization close to 0% and the white points correspond to utilization close to 100%. The bold white line shows the border between the active and inactive links. The black points above the white line are switched off. More information about how this figure was generated was presented in the previous section (4.3.3).

Figure 4 . 8 :

 48 Figure 4.8: The heat-map of the link utilization. Also illustrating the links which are off (shown in black)

Figure 4 . 9 :

 49 Figure 4.9: The utilization of each link in the evaluated networks

9 f

 9 a,d " f g,d " 0.45 ¨c

Figure 4 . 10 :

 410 Figure 4.10: Congestion avoidance by turning off

Figure 4 . 11 :

 411 Figure 4.11: The number of links kept active in the network under continuous growth of network traffic. The x axes is normalized to the duration till congestion with shortest path routing.

Fig. 4 .

 4 [START_REF] Coiro | Impact of energy-aware topology design and adaptive routing at different layers in IP over WDM networks[END_REF] shows the distribution of the load in the network topology when STREETE THE NETWORK OVER-PROVISIONING

Figure 4 . 12 :

 412 Figure 4.12: The heat-map (left) and per-link utilization (right) in the Generated200 network with increasing uniform all-to-all traffic

Figure 4 . 13 :

 413 Figure 4.13: STREETE in the Generated200 network with the highest traffic before congestion (tm " 4 in Fig. 4.9)

Figure 4 . 14 :

 414 Figure 4.14: path-stretch in each of the evaluated networks using STREETE

CHAPTER 4 .

 4 CONSUME LESS: THE STREETE FRAMEWORK FOR REDUCING THE NETWORK OVER-PROVISIONING

Figure 4 .

 4 Figure 4.15: ONOS Intent Framework.

Figure 4 .

 4 Figure 4.16 illustrates our platform and its main components, depicting the deployment of switches, an SDN controller and applications. At smaller scale, the platform comprises components that are common to other infrastructures set up for networking research[97,

Figure 4 . 16 :

 416 Figure 4.16: Overview of the network testbed.

Figure 4 . 17 :

 417 Figure 4.17: Photo of the experimental platform

4. 4 .Figure 4 . 18 :

 4418 Figure 4.18: Start phase of the segment-routing application.

  Interface of OMNeT++ (b) Interface of the ONOS SDN controller

Figure 4 . 19 :

 419 Figure 4.19: Interfaces of the simulator and the testbed showing a data flow avoiding the shortest path

CHAPTER 5 .Figure 5 . 1 :

 551 Figure 5.1: Example of link cost function

7 :

 7 visitedList Ð rv root s Ź List of nodes containing one element (vroot)

Figure 5 . 2 :

 52 Figure 5.2: 1+3¨cubic_bezier(random parameters)

Figure 5 . 3 :

 53 Figure 5.3: Utilization of the most loaded link under continuous growth of network traffic.x axes are normalized to the moment of congestion with classical shortest path routing.

2 Figure 5 . 4 :

 254 Figure 5.4: Two paths of equal cost between the node a and c

Figure 5 . 5 :

 55 Figure 5.5: The total flow in the network (5.5a), and the decomposition of this flow per source node

Figure 5 . 6 :

 56 Figure 5.6: The primal and dual of the maximum concurrent flow problem in a path-flow formulation

5. 2 .

 2 LB: MAXIMUM CONCURRENT FLOW FOR LOAD BALANCING WITH SDN Algorithm 7 Approximate maximum fractional concurrent flow 1: procedure fractionalMCFP(G)

Figure 5 . 7 :

 57 Figure 5.7: Flow originating from the node a

CHAPTER 5 .Algorithm 8 1 :

 581 CONSUME BETTER: TRAFFIC ENGINEERING FOR OPTIMIZING NETWORK USAGE Compute the explicit routes for the flow from v root towards all nodes ˚P V procedure computeRoutesInDAG(DpV, E D q, v root P V, d vroot,˚, sortedV ) 2:

4 :raf Ð 0 5 :

 45 totalInT for all pu,vq P E D do 6:

CHAPTER 5 .Figure 5 . 8 :

 558 Figure 5.8: Utilization of the most loaded link under continuous growth of network traffic. x axes are normalized to the moment of congestion with classical shortest path routing.

Figure 5 . 9 :

 59 Figure 5.9: Italian network with the highest traffic before congestion. At the left: shortest path routing at t " 1 on figure 5.8. At the right: LB with 4 times more traffic than the shortest path routing (t " 4 on figure 5.8).

Figure 5 . 10 :

 510 Figure 5.10: The utilization of each link in the evaluated networks

Figure 5 . 11 :

 511 Figure 5.11: The heat-map and the link utilization in the NSFNet and Geant Networks with the daily traffic

Figure 5 .

 5 Figure 5.12: path-stretch in each of the evaluated networks

6. 1 .Figure 6 . 1 :

 161 Figure 6.1: Maximum link utilization in the analyzed networks using the STREETE-LB mixed solution

Figure 6 . 2 :

 62 Figure 6.2: Influence of the precision ǫ on the number of active links and on the congestion avoidance. USNET network

Figure 6 . 3 :

 63 Figure 6.3: Influence of the thresholds α and β on the number of active links in the Germany50 network

Figure 6 . 4 :

 64 Figure 6.4: The heat-map of network links with real traffic matrices

Figure 6 . 5 :

 65 Figure 6.5: Rerouting towards a lower RTT ñ packet reordering.

Figure 6 . 6 :

 66 Figure 6.6: TCP congestion control; RTT = 50ms; 100mbps link.

Figure 6 .

 6 Figure 6.6 shows how the congestion window of a single flow evolves when using the Reno and Cubic congestion control algorithms.

  * ((t-29.43-RTT)-K)3 + 455

Figure 6 . 7 :

 67 Figure 6.7: Function used by the Cubic algorithm; RTT = 50ms.

Figure 6 . 8 :

 68 Figure 6.8: Alternated sending and waiting phases.

Figure 6 . 10 :Figure 6 .

 6106 Figure 6.10: Bandwidth drop when rerouting 20 independent cubic flows

Figure 6 . 11 :

 611 Figure 6.11: Impact of the number of flows in each of 20 groups.

Figure 6 . 12 :

 612 Figure 6.12: Throughput of a TCP flow. Periodic rerouting between 2 routes with different RTT; Low RTT.

Figure 6 .

 6 Figure 6.12 summarises the results. Considering five experiment runs, each data point in the graph corresponds to mean throughput, i.e. the amount of transferred data divided by the total transmission time. The error intervals show the absolute minimum and maximum values recorded. The baseline without rerouting shows the average throughput of a TCP flow when it always passes through the same path. The baseline is the mean of 20 experiments. The inner plot zooms in on the region with frequent route changes.Frequent route changes have a large impact on the performance of the congestion control algorithm. When the traffic is rerouted once every 0.1s, the throughput is as low as 35% of the throughput without rerouting. We can also observe that with a route change every 2 seconds, the throughput is around 85% compared to the throughput without rerouting. Although from a practical point of view we believe that these frequencies of rerouting are extreme (and not very realistic), they were included here to evaluate the limits on traffic rerouting. To re-optimise the network at such frequencies, a lot of control messages must be transmitted between the SDN controller and the switches, creating a flood of control traffic. Moreover, the network optimization problems are usually computationally intensive and take the time to find a good solution.

Figure 6 . 13 :

 613 Figure 6.13: Throughput of a TCP flow. Periodic rerouting between 2 routes with different RTT; High RTT.

Figure 6 . 14 :

 614 Figure 6.14: Evolution of the congestion window at RT T " 170ms.

Figure 6 . 15 :

 615 Figure 6.15: Evolution of the congestion window at RT T " 480ms.

Figure 2 :

 2 Figure 2: Main interface of the application

( a )

 a Clicking on a node (b) Clicking on a second node

Figure 3 :

 3 Figure 3: Interacting with the network

Table 2 .

 2

	10	50
	40	100
	100	150
	400	300

* mathematical projection 1: Power consumption of transponders

Table 2 .

 2 2: Power consumption of TDM/OTN ports (bidirectional) our example, what seems to be direct connections between the nodes A-C and B-D are virtual tunnels provided by the TDM and, respectively, WDM layers.

	2.1. ARCHITECTURE OF BACKBONE NETWORKS
	Speed (Gbps)	Consumption (W)
	10	34
	40	160
	100	360
	400	1236

* mathematical projection

Table 2 .

 2 .3. The results assume that the traffic matrix is updated every second. 3: Estimated statistics traffic with 1s polling interval

	Network nodes	50	100	200	1000
	Control traffic 0.3Mbps 1.21Mbps 4.86Mbps 120Mbps

1 :

 1 while Energy Efficient Traffic Engineering is active do

	2:

  sorted of the next node to analyze

	4:	while sorted.size() ă |V | do
	5:	u Ð sortedris
	7:	sorted.append(v)
	8:	end for
	9:	i Ð i	`1
	10:	end while
	11:	return sorted
	12: end function

6:

for all v P V s.t. pu, vq P E T do

Table 4 .

 4 1. New York node is not visible in the Geant network, but the two links connecting it to the rest of the network are shown.

	Network	Number of nodes	Number of links
	NSFNET	14	42
	Italian	21	70
	Geant	22 ˚72
	USNET	24	86
	AT&T	25	108
	Germany50	50	176
	CORONET	75	198
	Generated200	200	1148
	*the

Table 4 . 1 :

 41 Summary of the network topologies.

Table 4 .

 4 2 indicates the maximum time taken by the algorithm on each of the analyzed networks. The most interesting results are provided by the Germany50, Coronet and Generated200 networks, because those are the biggest. The implementation with dynamic graph algorithm and a binary heap for Dijkstra computations allowed to scale 4.3. EVALUATION BY SIMULATION

	Network	STREETE	CPLEX
	NSFNet	1ms	(1s)1827ms
	Italian	3ms	(2s)2075ms
	Geant	2ms	(3s)3491ms
	USNET	4ms	(33s)33716ms
	ATT	6ms	(21s)21488ms
	Germany50	53ms	(2h ˚)7203220ms
	CORONET	39ms	p ˚˚q-
	Generated200	(8s)8311ms	p ˚˚q-
	*CPLEX didn't find the optimal solution in the maximum allocated time (2h)
	**CPLEX wasn't able to initialize the model

Table 4 .

 4 2: Maximum time taken by STREETE and CPLEX on each of the analyzed networks the algorithm to comfortably work on networks with 200 nodes.

  Ðmax(1, max uvPE T :f pu,vq Pf p˚,˚q pf pu,vq {cpuvqqq 12:for all f pu,vq P f p˚,˚q do 13:f pu,vq Ð f pu,vq {σ

	11: σ 14: 15:	f vsrc pu,vq Ð f vsrc pu,vq `fpu,vq d 1 pu,vq Ð d 1 pu,vq ´fpu,vq
	16:		Dplq Ð Dplq `lpuvq	˚ǫ f pu,vq cpuvq cpuvq
	17:		lpuvq Ð lpuvq `lpuvq	˚ǫ f pu,vq cpuvq q
	18: 19:		if d moreTrafficÐ true 1 pu,vq ą 0 then
	20:		end if
	21:	end for
	22:	end while
	23:	end for
	24:

  X Ð tpR.P `uv, R.r ¨ratio uv q|@R P R vroot,u u

	7:	end for
	8:	for all pu,vq P E D do
	9:	ratio uv Ð f uv {totalInT raf
	10:	end for
	11:	end for
	12:	R vroot,vroot Ð ppq,1q
	13:	for all v P sortedV r1 :s do
	14:	R vroot,v Ð H
	15:	for all pu,vq P E D do
	16:
	17:	R vroot,v Ð R vroot,v Y X
	18:	end for
	19:

Table 5 .

 5 5.2. LB: MAXIMUM CONCURRENT FLOW FOR LOAD BALANCING WITH SDN 1: Maximum computational timethis change will lead to a further increase of the computational time, making it less appealing than LB.

	Network	CF	LB	CPLEX
	NSFNet	225ms	166ms	458ms
	Italian	383ms	546ms (1s)1126ms
	Geant	829ms	248ms	948ms
	USNET	544ms	737ms (2s)2539ms
	ATT	823ms	794ms (2s)2830ms
	Germany50	(2s)2385ms	(2s)2024ms (8s)8333ms
	CORONET	(24s)24358ms	(3s)3688ms	p ˚q-
	Generated200 (8m)537820ms (1m)107526ms	p ˚q-
	*CPLEX was not able to initialize the model

  6.1 provides this information for each of the analyzed network topologies.

	Network	STREETE-LB	CPLEX
	NSFNet	216ms	(1s)1827ms
	Italian	496ms	(2s)2075ms
	Geant	104ms	(3s)3491ms
	USNET	637ms	(33s)33716ms
	ATT	(2s)2009ms	(21s)21488ms
	Germany50	(14s)14478ms	(2h ˚)7203220ms
	CORONET	(15s)15384ms	p ˚˚q-
	Generated200 (20m)1204510ms

  .2 estimates the size of the congestion window needed to transmit at 100Mbps with 1448 byte segments. It also uses the equation ∆t " K to assess the time taken by the Cubic algorithm to grow the window back to W max after a loss.

	RTT (ms)	10 50 180	500
	W max (segment)	87 431 1550 4316.3	Time
	to recover (s) 3.5	6	9.2	13

http://www.parismatch.com/Actu/Economie/Orange-revelations-sur-la-panne-geante-157766

Cisco CRS-3 data sheet: http://www.cisco.com/c/en/us/products/collateral/routers/ carrier-routing-system/data_sheet_c78-408226.html

https://www.docker.com

https://en.wikipedia.org/wiki/Heat_map

https://omnetpp.org/omnetpp

https://github.com/inet-framework/inet/releases/

https://download.qt.io/official_releases/qt/5.9/5.9.0/

https://en.wikipedia.org/wiki/Fog_computing

Juniper PTX Series Router Interface Module Reference

Juniper PTX[START_REF]PTX Series Packet Transport Routers Datasheet[END_REF], one of the biggest backbone routers, is a pure MPLS router and is not capable of doing IP processing at its maximum advertised speed.

http://web.mit.edu/15.053/www/

"10Gbps" is a constant. As a result, maximizing λ ¨10Gbps is equivalent to maximizing λ.

https://www.geant.org/Networks/Pages/Home.aspx http://www.monarchna.com/topology.html http://igen.sourceforge.net

https://www.grid5000.fr

http://www.eaton.com/Eaton/index.htm

http://netfpga.org/site/#/systems/3netfpga-10g/details/

The testbed was financially supported by the chist-era SwiTching And tRansmission (STAR) project

http://www.wand.net.nz/~stj2/nsc

frequent change of the state of links (off /on) due to small variations in network traffic

http://openvswitch.org

CHAPTER 1. INTRODUCTION

Appendices Using the android application

The android application can be installed by scanning the QR code from Fig. 1. It allows to interactively visualize the execution of the algorithms proposed in chapters 4 and 5 of this thesis.

Figure 1: Access app using Google Play https://play.google.com/store/apps/details?id=me.carpa.streete At launch, a network view is opened (Fig. 2). Its main components are:

• (1) Network selection. Sliding to the left/right reveals more available network topologies. To select a network, click on it.

• (2) Algorithm selection. By default, a shortest path routing based on the Dijkstra's algorithm is used. Checking "Consume Less", "Consume Better", or both, enables respectively STREETE, LB, or STREETE-LB.

• (3) Network state. It shows the link utilization when the algorithm selected by the previous check-boxes is applied into the network. On start, an uniform all-to-all traffic is injected into the network.

• (4) The slider allows to increase / reduce the traffic in the network by a multiplicative factor.