Hussein Zahr
email: hussein.zahr@ensam.eu

Mohamed Trabelsi
email: mohamed.trabelsi@ensam.eu

Eric Semail
email: eric.semail@ensam.eu

Comparison and Analysis of Post-Fault Operation Modes in a Five-Phase PMSM Considering Thermal Behavior

Keywords: Fault tolerant control, five-phase PMSM, openedphase fault, copper losses, thermal analysis. I

This paper presents a comparative evaluation of fault tolerant control strategies for a five-phase Permanent Magnet Synchronous Machine (PMSM) under an opened-phase fault mode. Two main classical Fault Tolerant Control (FTC) methods and the no-reconfiguration strategy are compared with the normal mode operation considering peak current, peak voltage, average torque, torque ripples and measured temperatures of five windings of the five phases. The analysis of the temperature repartition shows that, in fault mode, at least in the particular studied case, the knowledge of the Joule losses is not sufficient for a correct control of the temperature.

INTRODUCTION

Thanks to their fault tolerance and torque density, the multiphase PMSM are studied in transport applications as automotive [START_REF] Patel | Six-phase fractional-slotper-pole-per-phase permanent-magnet machines with low space harmonics for electric vehicle application[END_REF], aerospace [START_REF] Huang | Design of a five-phase brushless dc motor for a safety critical aerospace application[END_REF], aeronautic [START_REF] Haylock | Operation of a fault tolerant pm drive for an aerospace fuel pump application[END_REF] and marine [START_REF] Parsa | Five-phase permanent magnet motordrives for ship propulsion applications[END_REF]- [START_REF] Williamson | Fault tolerance in multiphase propulsion motors[END_REF]. Anyway, although a multiphase drive can continue to operate in faulty mode, post-fault operation without reconfiguration of control can lead to some harsh and undesired effects on the machine such as overheating and significant torque ripples. Thus, it is important to reconfigure the control in post-fault operation in order to reduce these effects on the drive. Two main families of FTC have been developed in previous works for the opened-phase fault. In the first family (called MT, as Maximum Torque), the copper losses and the current waveform in the healthy phases are imposed to be equal [START_REF] Fu | Disturbance-free operation of a multiphase current-regulated motor drive with an opened phase[END_REF]- [START_REF] Baudart | Torque Control Strategy of Polyphase Permanent-Magnet Synchronous Machines With Minimal Controller Reconfiguration Under Open-Circuit Fault of One Phase[END_REF], inducing then also identical peak currents. The current constraints for the transistors of the Voltage Source Inverter are then easily defined by the peak value. Moreover, when the electromotive forces (emf) are sinusoidal [START_REF] Baudart | Torque Control Strategy of Polyphase Permanent-Magnet Synchronous Machines With Minimal Controller Reconfiguration Under Open-Circuit Fault of One Phase[END_REF]- [START_REF] Fall | Variable speed control of a 5-phase permanent magnet synchronous generator including voltage and current limits in healthy and open-circuited modes[END_REF] or with only the first and third harmonics [START_REF] Bianchi | Post-fault operations of five-phase motor using a full-bridge inverter[END_REF] , the torque ripples are also easily controlled and references of current are calculated in order to obtain the maximum torque. In the second family of FTC, the waveforms of the currents are free: for given waveforms of emf and required average torque, the Joule losses are minimized under the constraint of zero torque ripples. The currents are calculated either by optimization approach (as Lagrangian multiplier) in case of sinusoidal [START_REF] Baudart | Torque Control Strategy of Polyphase Permanent-Magnet Synchronous Machines With Minimal Controller Reconfiguration Under Open-Circuit Fault of One Phase[END_REF] but also non-sinusoidal emf [START_REF] Wang | Optimal torque control of faulttolerant permanent magnet brushless machines[END_REF]- [START_REF] Dwari | An optimal control technique for multiphase PM machines under open-circuit faults[END_REF] or by a vectorial approach [START_REF] Locment | Vectorial Approach-Based Control of a Seven-Phase Axial Flux Machine Designed for Fault Operation[END_REF]- [START_REF] Kestelyn | A vectorial approach for generation of optimal current references for multiphase permanent-magnet synchronous machines in real time[END_REF], this last one being more convenient for real-time control and non-sinusoidal emf. With this second family of FTC, the peak currents and voltages can be quite different in the healthy phases, leading to unequal Joule losses even if the global losses are the same as the normal operation. This unbalance between the healthy phases in terms of losses could be considered as an unbalanced thermal constraint between the windings. In fact the proposed paper shows that it is not always the case because it is finally not the losses which are important but the temperatures which are depending not only on the losses but also on the thermal coupling between the windings: even with equal losses in the healthy phases, the temperature is not the same in the healthy phases. In [START_REF] Bianchi | Thermal analysis of a five-phase motor under faulty operations[END_REF], for a given control, an interesting analysis of the temperatures in fault mode obtained by Finite Element simulation has been already achieved and experimental results but in a particular machine configuration is provided. In the proposed paper, an experimental five-phase prototype is considered without particular configuration and the impact on the temperatures of the control in fault mode is presented. It is appearing that the repartition of the Joule losses is not representative of this one of the temperatures. As consequence the elaboration of control strategies based only on the losses is not the best choice in fault mode. It is the reason why in the paper is comparing different FTC considering other criteria than losses. For this studied machine, the results obtained by the two kinds of FTC (called M 3 and M 4 similar as in [START_REF] Baneira | Control Strategy for Multiphase Drives With Minimum Losses in the Full Torque Operation Range Under Single Open-Phase Fault[END_REF]) in terms of torque, torque ripples, peak current, peak voltages and finally temperature of one winding of each phase are presented. They are compared between them and with the healthy case (M 1 ) and fault case without reconfiguration (M 2 ).

This paper is organized as follows: after a presentation of the machine in section II, the current waveforms are defined for pre-fault and post-fault operation modes in section III. In section IV, comparative analysis is provided between different classical control strategies based on several parameters related to the machine performance. In section V, a thermal behaviour investigation is pointed out experimentally for each control strategy using thermal resistance detectors installed on some coils in the machine.

II. FIVE-PHASE PMSM PROTOTYPE AND MODELLING

The considered machine is a prototype that has been achieved in the frame of an industrial project for 48V low voltage hybrid automotive application. Fig. 1-a and Fig. 1-b show the 20-slot/14-pole five-phase PMSM [START_REF] Aslan | Slot/pole combinations choice for concentrated multiphase machines dedicated to mild-hybrid applications[END_REF], in which fractional slot tooth concentrated winding and IPM rotor are used.

In order to characterize the thermal behaviour especially in fault mode the prototype has been equipped of several temperature sensors. The location of the resistance thermal detector (RTD) is depicted in Fig. 1-b. One RTD is inserted for each phase. It is placed on one coil among the four coils forming each phase winding. These coils are labelled by the phase to which they belong with the subscription c1, as illustrated in Fig. 1-c (A c1 , B c1 , C c1 , D c1 and E c1 ). The coils of the phase A are not represented in the figure since it is the phase where the fault will occur. The main parameters of the five-phase PMSM useful for the vector control are given in table I. The characteristic shape of its back-EMF is depicted in Fig. 2: the third harmonic is about 12% of the first harmonic.

For classical Maximum Torque Par Ampere (MTPA) vector control, the considered harmonics of currents are only the same as those of emf. Currents are expressed by (1):

Where Ω is the mechanical frequency, p the pole pairs, (I 1 , I 3 ) are the magnitude of the first and the third harmonic current amplitude, φ 1 (respectively φ 3 ) is the phase shift between the first (respectively third) harmonic of current and the first (respectively third) harmonic of the emf. Then, the delivered torque can be expressed as follows: (2)

III. DEFINITION OF CONTROL STRATEGIES IN PRE-FAULT AND POST-FAULT OPERATION MODES

In this section, the control strategies applied to the fivephase PMSM, in pre-fault and in post-fault operation modes, are summarized. For sake of simplicity, regardless the operating conditions, the first choice in this work is to keep the same structure of the controllers in all operation modes. As consequence, the reconfiguration of the drive system after the fault occurrence consists essentially in modification of the references considering the minimization of both torqueripples and copper losses. Accordingly, the comparative study will be achieved for four different modes as below:

Healthy mode (M 1 ): it corresponds to the MTPA control under healthy operating conditions. It will be considered as reference mode for the temperatures.

Opened-phase operation mode without reconfiguration (M 2 ): although the fault occurrence in the PMSM, the same reference currents are kept as in normal mode operation.

Opened-phase operation mode with reconfiguration (M 3 ): in this case, the reconfiguration strategy consists in minimizing the copper losses for a given torque without imposing any constraint on the current. Opened-phase operation mode with reconfiguration (M 4 ): this one consists in minimizing the copper losses but the currents must be sinusoidal and of equal amplitude in the healthy phases verifying voltage and current limits.

The M 3 and M 4 strategies can be only applied after the detection of fault is achieved. Then the M 2 strategy is 12% implicitly used before the adoption of a reconfiguration. The M 4 strategies have been studied for induction machine [START_REF] Fu | Disturbance-free operation of a multiphase current-regulated motor drive with an opened phase[END_REF] and PM machines [START_REF] Baudart | Torque Control Strategy of Polyphase Permanent-Magnet Synchronous Machines With Minimal Controller Reconfiguration Under Open-Circuit Fault of One Phase[END_REF]- [START_REF] Fall | Variable speed control of a 5-phase permanent magnet synchronous generator including voltage and current limits in healthy and open-circuited modes[END_REF].

For the experimental results, the working point corresponds to copper losses of around 250 W in healthy mode (M 1 ) and a mechanical power of 2.5 kW. In post-fault operation strategies (M 2 , M 3 and M 4 ), the reference currents are modified so that the same global copper losses remain unchanged (250W) and the torque is then reduced.

A. Maximum Torque Per Ampere control in pre-fault operation mode (M 1 strategy) For the system under study, in pre-fault operation mode (M 1 ), the MTPA strategy is correctly achieved when the two following conditions are respected:

9 Based on equation 2, the phase-shift between current harmonic and the same harmonic in the back-EMFs is zero:

0 3 1 M M ( 3 ) 9
The ratio of the third current harmonic component and the first one is the same as the ratio between the third harmonic and the first one of the back-EMFs. It is defined as follows

3 3 1 1 E I E I U (4)
Taking into account (3) and ( 4), for a given RMS current value I rms , the amplitude of the first and the third current harmonic components are given by: The time-domain waveforms of the motor phase currents in MTPA strategy (mode M 1 ) are illustrated in Fig. 3-a. The motor phase currents are normalized with respect to the current peak value. As about 12% of third harmonic current in injected in this case in phase with the emf, the peak value is about 112% of peak value of the first harmonic Fig. 3b presents their spectrogram in one out of five windings.

B. Maximum Torque Per Ampere control under a faulty condition (M 2 strategy)

As announced above, this mode corresponds to an openedphase fault in the PMSM without reconfiguration. Therefore, the same control is kept and the copper losses are maintained equal to those achieved in pre-fault operation mode by experimental fitting of the current references. The timedomain waveforms of the motor phase currents, normalized with respect to the peak value obtained in pre-fault mode, are illustrated in Fig. 4-a.The open-phase fault occurrence results in different modification of harmonic components in the healthy phase-currents (phase b, c, d, e), since the variation of their magnitudes are not the same. This means that the fault is not equally divided between the healthy phases. In these conditions, a current peak value of about 120% is reached in the phase E (in comparison to the one obtained in pre-fault mode).

C. FTC control strategies

Two different post-fault tolerant control strategies are addressed when an opened-phase occurs in the five-phase PMSM. The motor phase currents obtained for both FTC strategies (M 3 and M 4 ) are normalized with respect to the current peak value obtained in a healthy mode.

1) FTC control with minimum copper losses (M3 strategy):

The generation of the optimal reference currents is performed so that a constant torque (with minimum ripples) must be obtained in post-fault operation mode. For this, the dimension of the current vector is adapted to the dimension of the accessible back-EMF vector with a minimization of the total joule losses as an optimisation criterion. From [START_REF] Kestelyn | A vectorial approach for generation of optimal current references for multiphase permanent-magnet synchronous machines in real time[END_REF], the optimal reference current vector and the corresponding waveforms in the healthy phases are given by formula (6):

* 2 * || || T i acc acc H H G G G (6)
where acc H G denotes the normalized-speed accessible back- EMF vector [START_REF] Kestelyn | A vectorial approach for generation of optimal current references for multiphase permanent-magnet synchronous machines in real time[END_REF], T * is the desired torque. Fig. 5 depicted the time-domain waveforms of the motor phase currents with their harmonic content. Imposing the global copper losses leads easily to the Torque reference T * .

2) Strategy with sinusoidal current injection (strategy M 4 ): in comparison to FTC control proposed in M 3 , this strategy consists in minimizing the joule losses but injecting only sinusoidal references currents. This approach aims to balance power in all healthy phases. The reference currents which must be injected are defined by [START_REF] Fu | Disturbance-free operation of a multiphase current-regulated motor drive with an opened phase[END_REF], [START_REF] Fall | Variable speed control of a 5-phase permanent magnet synchronous generator including voltage and current limits in healthy and open-circuited modes[END_REF] [START_REF] Baudart | Torque Control Strategy of Polyphase Permanent-Magnet Synchronous Machines With Minimal Controller Reconfiguration Under Open-Circuit Fault of One Phase[END_REF] Since the copper losses are the same as in the healthy operation mode (250W), we have to add a constraint concerning the copper losses in this machine in order to determine I opt .

W opt I s R j P 250 2 4 (8)
The time domain waveforms of phase currents corresponding to this control strategy are depicted in Fig. 6. It appears that the currents introduced in the healthy phases are sinusoidal and with equal amplitude.

IV. COMPARATIVE ANALYSIS

In this section, a comparative evaluation between the four control modes (M 1 , M 2 , M 3 , M 4 ) is presented. It is achieved regarding the following criteria:

9
The average delivered torque. 9

The torque ripples.

9

The peak voltage value required by the PMSM.

9

The peak current value.

A. Torque and voltage/current peak behavior

The comparative analysis between different control strategies presented above is achieved. It is based on Finite Element (FE) model simulation. Therefore, the obtained timedomain current waveforms are injected into the FE model of the five-phase PMSM. Fig. 7 illustrates FE simulation results of the comparison between the different control strategies. 1) Torque average value: Comparing the results in Fig. 7-a, it can be seen that, except for the normal operation mode in which the torque is equal to 32.5 N.m, the torque average value is about 26 N.m (80% of torque corresponding to the mode M 1 ) in post-fault operation when the copper losses is kept equal to 250W.

2) Torque ripple: under healthy operation mode of the PMSM (mode M1), the machine generates a quite smooth torque. On contrary, under faulty operating conditions corresponding to an opened-phase fault (mode M 2 ), a large dissymmetry is introduced in the motor, resulting in high torque ripples equal Fig. 5. Time-domain waveforms of the motor phase currents with reconfiguration (M3 strategy) under an opened-phase fault (phase a is opened ia= 0). Fig. 6. Time-domain waveforms of the motor phase currents with reconfiguration (M4 strategy) under an opened-phase fault (phase a is opened ia= 0). to 93%, as shown in Fig. 8. Thanks to FTC, strategies M 3 or M 4 , an acceptable ripples level of the torque is obtained. It is important to point out that the constraint of sinusoidal supply as achieved only in mode M 4 resulting in torque ripples 30% larger than the ripples obtained for FTC control of mode M 3 (14%) as shown in Fig. 7-a and Fig. 8.

3) Required peak voltage: as shown in Fig. 7-b, with regard to mode M 2 , it can be concluded that the fault induces a high voltage peak value of 130% in comparison to the normal operation mode of the motor. Applying the fault tolerant control strategies corresponding to the modes M 3 and M 4 , the voltage peak value are kept relatively low approximately near 115%. 4) Peak current: as for the required voltage, strategies (M3 and M 4 ) required low peak current than M 2 for the same amount of torque. In conclusion, the reconfiguration of control in postfault operation modes is important in order to reduce the required voltage/current for a given torque.

B. Copper losses comparison and thermal behavior analysis

As discussed above, the voltages and currents distortion in post-fault operation modes affects the performance of the fivephase PMSM. In fact, the non-sinusoidal supply applied to the PMSM results in various harmonic components circulation in motor windings. Consequently, high frequency electric components produce additional losses, increasing thus the operating temperature of the windings as well as the core. These conditions result in degradation of the performance.

Fig. 9 summarizes the normalized copper losses in each phase when the considered control strategies are applied. The results are normalized with respect to the value of the copper losses per phase, equal to 50W, corresponding to the healthy operation mode of the five-phase PMSM.

In post-fault operation mode, the 250W of copper losses are distributed between the remaining healthy phases, either equally as in modes M 1 and M 4 or non-equally as in mode M 2 and M 4 . The post-fault operation modes create nonhomogenous distribution of losses in the motor windings. As the temperature is directly related to losses, the nonhomogeneity of the losses distribution impacts significantly the temperature difference between the motor phase windings. As there are no copper losses in the faulty phase, it is expected that it has the lowest temperature value. According to Fig. 9, phases C and D have almost identical copper losses in all the considered operation modes (M 1 , M 2 , M 3 and M 4 ). In addition, the phase E has the greater copper losses in post-fault operation mode (M 2 , M 3 and M 4 ). Then, it is expected that this phase will have the highest temperature among the five phases when an open circuit fault occurred in phase A. The temperature measurement analysis detailed in section V confirms these conclusions.

V. THERMAL TEST AND ANALYSIS FOR CONTROL STRATEGIE

A. Thermal environment and cooling of the machine

The presented machines is equipped by two external fans sticked on both sides of the rotor, and are designed to ensure an efficient cooling of the end-windings as illustrated in Fig. 1a. Furthermore, fins are present at the bottom, right and left sides of the motor cover as observed in Fig. 1-a. At these sides of the machine, the cooling with natural ventilation is enhanced. However, the connexion box is fixed on the top of the machine, which makes less efficient the cooling by the natural ventilation in this side. The presented cooling circuit of the machine have a noticeable impact on the temperature repartition.

Temperature probes are inserted into the machine according to Fig. 1-b. All these probes are placed within the slot, in contact with the copper. The resistance thermal detectors (RTD) are linked to a data acquisition system that allowed plotting the temperature versus time curve for each detector. The temperature measured in steady state is normalized with respect to the mean value of the temperature in healthy mode operation (M 1 ), which equal to 111 o C. Results are illustrated in Fig. 10.

B. Analysis of temperature measurement

In healthy operation mode M 1 , the measured temperatures are not identical between all the phases as shown in Fig. 10, although the copper losses are the same in these phases. There is up to 30% of difference. The first remark is that it is not obvious to consider the temperature of a phase which is obtained with several windings. For example, in the phase A the coil A c1 has the highest temperature. Thermal analysis shows that it is due mainly to the connexion box (see Fig. 1-a) whose thermal resistivity is higher than for the other coils which are near fins.

In fault mode configuration it can be observed that the repartition is of course different for the different modes but even if there is no more current in phase A, the temperature of the coil A c1 is still higher than in the healthy phases. As consequence the choice to keep the same Joule Losses in the remaining healthy phases is an adequate criterion in terms of thermal goal.

VI. CONCLUSION

This paper shows that in fault mode, the strategy which consists in imposing the same Joule losses in the remaining healthy phases does not lead to equal temperatures in the healthy phases and even more the temperature in winding of opened phase is not the weakest. A hot point can appear. As consequence in order to able to reduce the security margins concerning the temperatures in windings, it should be interesting to define new strategies based on temperature measurements and a thermal modelling of the machine: in each phase, admissible Joule losses and waveform of current could be chosen in order to obtain the maximum possible average torque under constraints of peak voltage and peak current. This kind of approach will be particularly interesting for drive in transportation since transient operation as acceleration phase during less than 60s are often required. In this case the repartition of the temperatures is of utmost importance.

Fig. 1 .Fig. 2 .

 12 Fig.1. Motor prototype (5-Φ 20-slot/14-pole). (a) stator/rotor (b) Resistance thermal detector (RTD) location and the faulty coils location.

Fig. 3 .Fig. 4 .

 34 Fig. 3. Time-domain waveforms of the phase currents for the MTPA control (M1 strategy) under a healthy operation mode of the five-phase PMSM.

Fig. 7 .

 7 Fig. 7. Parameters of comparison between the healthy mode control strategy and post-fault control strategies.

Fig. 8 .

 8 Fig. 8. Torque ripples calculated by FE simulations normalized with respect to the mean value for each operation mode.

Fig. 9 .Fig. 10 .

 910 Fig. 9.Variation of copper losses in each phase for each control strategy.

ACKNOWLEDGMENT

This work has been achieved within the framework of CE2I project. CE2I is co-financed by European Union with the financial support of European Regional Development Fund (ERDF), French State and the French Region of Hauts-de-France.


Rihab Abid Maaloul

Raouia Taktak

Lamia Chaari

Bernard Cousin

Energy-Aware Routing in Carrier-Grade Ethernet using SDN Approach

Keywords: Energy-Aware Routing, Carrier-Grade Ethernet, Software-Defined Networking (SDN), Routing Optimization

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Energy-Aware Routing in Carrier-Grade Ethernet using SDN Approach Rihab Maaloul * , Raouia Taktak * Lamia Chaari * and Bernard Cousin †

I. INTRODUCTION

E

NERGY optimization in carrier-grade networks is becoming a concern in networking. Studies have shown that the energy consumed by carrier-grade networks may reach 50% of the total network power by 2020 [START_REF] Hinton | Power consumption and energy efficiency in the internet[END_REF], [2]. Therefore, reducing the energy consumption of carrier-grade networks has attracted an increasing interest. The energy consumption in a network generally depends on the technology used and elements' power profile. Carrier Ethernet elements present an ON-OFF power profile. This profile fully empowers network devices when they may later be turned on [3], [4]. Consequently, a constant amount of power is consumed when a device is on, regardless of its traffic load. In the case of an ON-OFF power profile, it would be more energy efficient to aggregate traffic on a small set of network devices (line cards and a router chassis) to allow the maximal set to be turned off. Accordingly, Energy Aware Routing (EAR) mechanisms constitute a potential solution to energy consumption minimization. EAR can be implemented and integrated over two architectures (centralized and distributed). Distributed architectures exploit limited amounts of data, relying on multiple agents which are able to locally adjust the sleeping decision.

Compared to the distributed architectures, centralized ones dispose of a central controller. Sleeping decisions are carried out in a coordinated way by a central entity who has a global network knowledge. The implementation of an energy-aware routing within an SDN (Software Defined Network) logically centralized architecture can be easily achieved. Carrier-grade network operators specify the need for creating an SDN architecture to facilitate the management and increase the flexibility of their networks [START_REF] Nunes | A survey of software-defined networking: Past, present, and future of programmable networks[END_REF], [START_REF] Martino | Resiliency Challenges in Accelerating Carrier-Grade Networks with SDN[END_REF]. In fact, for the optical transport networks, the Optical Transport working group of the Open Networking Foundation (ONF) [START_REF] Foundation | Software-defined networking: the new norm for networks[END_REF] emphasizes the improvements in the flexibility of control and management by leveraging virtualization and SDNs. SDN implementations, in particular using Openflow , focus on carrier Ethernet to optimize its operational expenditures.

A detailed description of how Openflow promotes carrier

Ethernet advances is provided in [START_REF] Vaishampayan | Demonstrating openflow over a carrier ethernet switch router (cesr)a services perspective[END_REF], [START_REF] Bidkar | Field trial of a software defined network (SDN) using carrier ethernet and segment routing in a tier-1 provider[END_REF].

Openflow switches can either be pure or hybrid. Pure switches do not support legacy control protocols and only rely on the Openflow controller for routing decisions, while hybrid switches integrate both. In [START_REF] Agarwal | Traffic engineering in software defined networks[END_REF], the authors demonstrate an effective use of SDN for traffic engineering especially when SDN is incrementally introduced into an existing networks.

This can be ensured using hybrid switches which are the most deployed in carrier-grade Ethernet [START_REF] Nunes | A survey of software-defined networking: Past, present, and future of programmable networks[END_REF], [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF].

Openflow architecture makes energy-aware routing algorithms less complex due to its logically centralized controller.

The Openflow controller can learn network topology and network devices' states, and then compute the best paths in terms of energy savings. In traditional networks, as illustrated in Fig. 1, the strong coupling between the data and control planes makes the deployment of energy-aware routing algorithms very difficult.

It may also become very costly when the numerous devices come from different manufacturers, or when they use different programming interfaces or different protocols. In fact, this would imply a modification of the control plane for all the network devices which act as a closed-system. In contrast, an SDN-based architecture decouples the control plane from the data plane to produce an external entity which is called the SDN controller or the Network Operating System. The logically centralized architecture has the advantage of being consistent with energy-aware traffic engineering. However, to enable energy savings in the Openflow controller, specific features must be controllable by adding extra messages such as the port power status on/off and the adaptive line rate [START_REF] Staessens | Software defined networking: Meeting carrier grade requirements[END_REF].

These messages and their processing add overhead to the control plane and increase the communication delay between the controller and the forwarding devices. Furthermore, the performance of the control plane depends on the size of the flow table embedded in the openflow switches. In our work, we neglect the message exchange issues and consider only the the limitation of flow-table size. In this paper, we use optimization techniques to achieve SDN-based energy-aware routing in carrier Ethernet networks. We first give an Integer Linear Programming (ILP) formulation for the problem that takes into account the rule space capacity constraint, as well as flow conservation and resource utilization constraints. We then introduce a heuristic method that provide near-optimal solutions in a reduced amount of time. As there exists a tradeoff between power savings and network quality of service provisioning, we evaluate the efficiency of our proposed algorithms using diverse performance metrics. These include the network connectivity, the average path length, the average traffic load, and the fairness of traffic distribution.

The sequel is organized as follows. We present related works in the next section. In Section III, we formally describe the problem and model it as an ILP formulation. In Section IV, we describe heuristic algorithms. A performance analysis of the proposed resolution methods is presented in Section V.

Finally, Section VI is devoted to giving concluding remarks and new directions for future works.

II. RELATED WORKS

A. Energy-Aware Routing in traditional architectures

Energy-Aware Routing strategy refers to smartly routed traffic based on energy-saving objectives. A typical example of EAR consists in modifying the network protocol and turning off unused elements, in order to route traffic over energy efficient paths. Dabaghi et al. [START_REF] Dabaghi | A survey on green routing protocols using sleep-scheduling in wired networks[END_REF] categorize EAR approaches that use sleeping techniques into two main types:

(i) traffic-unaware algorithms that ignore the network traffic;

and (ii) traffic-aware approaches that consider a network traffic matrix in a sleeping decision. Only the works [START_REF] Cianfrani | An energy saving routing algorithm for a green OSPF protocol[END_REF], [START_REF] Cianfrani | An OSPF enhancement for energy saving in IP networks[END_REF], [START_REF] Cuomo | Energy saving in the Internet based on Occurrence of Links in routing paths[END_REF], [START_REF] Cuomo | Network pruning for energy saving in the Internet[END_REF], [START_REF] Matsuura | Energy-saving routing algorithm using Steiner tree[END_REF] and [START_REF] Maaloul | Energyaware forwarding strategy for Metro Ethernet networks[END_REF] have considered type (i) of the problem.

Although these approaches are able to achieve high energy conservation, they may impact the traffic routing and imply an important congestion on transiting elements especially during high traffic periods. The authors show that the traffic flows can be consolidated through a small set of links and switches which are sufficient to serve the bandwidth requests for most of the time. The work in [START_REF] Bruschi | Green extension of OpenFlow[END_REF] proposes an EAR solution inside Openflow protocol with Green Abstraction Layer (GAL) [START_REF] Bolla | The green abstraction layer: A standard power-management interface for next-generation network devices[END_REF], a recently approved standard of the European Telecommunications Standards Institute (ETSI). This integration permits internal communication between network devices to interchange their power states. In this way, the Openflow controller becomes aware of the energy consumption of each network component. In [START_REF] Bolla | Finegrained energy-efficient consolidation in SDN networks and devices[END_REF], an extension of the work presented in [START_REF] Bruschi | Green extension of OpenFlow[END_REF] is proposed including more power states instead of simple ON-OFF states. The authors consider an Openflow protocol that integrates further energyaware capabilities and power management primitives of the hardware components, line cards, nodes and logical resources.

Authors in [START_REF] Wang | Energy-aware routing algorithms in software-defined networks[END_REF] EAR approach [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF] for SDN-based networks allows only links to be turned off when the rule space constraint is considered.

The authors first model the problem in terms of ILP. They also propose a greedy heuristic based on one sorting criterion that iteratively selects the minimally loaded link as a candidate to be turned off.

Recall that using an SDN-based network for EAR offers the major advantage of logically centralized operation. SDN approaches also allow low operating expenses and the flexibility to manage the network and to improve the QoS. In this work, we focus on using Openflow to deploy energy-aware routing in carrier-grade Ethernet networks. Our work can be seen as an extension of [START_REF] Wang | Energy-aware routing algorithms in software-defined networks[END_REF] considering the rule space capacity, and an extension of [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF] offering the possibility to save energy on both links and nodes.

C. Optimizing rule space in Openflow forwarding node

In an Openflow network, the forwarding node contains one or more separated flow tables for handling packets. Starting from version 1.1 and thereafter, Openflow supports a pipeline process consisting of multiple flow tables [START_REF] Nunes | A survey of software-defined networking: Past, present, and future of programmable networks[END_REF], [START_REF] Kreutz | Software-defined networking: A comprehensive survey[END_REF]. Each flow table consists of a set of flow entries that are created by the controller, and that determine how flows will be processed.

Each entry in the table corresponds to a routing rule associated with an appropriate action. A flow entry can be divided into three parts: (1) a matching rule that may contain packet header information (e.g., source and destination MAC/IP addresses, and the ingress port); (2) an action to be executed on matching packets (e.g., to output the frame to a specific interface or flood it to all interfaces, to discard the frame, etc.); (3) a counter used to keep statistics on the matching packets. Large tables which are powerful for storing an important number of rules, provide fine-grained flow control and efficient energy-aware traffic engineering. However, it is worth noting that these rules are installed in a TCAM on-chip that is expensive and has limited space to hold a great number of rules. Hence, it would be interesting to optimize the number of rules installed in forwarding devices. TCAM-based energy-aware SDN issues received significant attention as shown in [START_REF] Tuysuz | A survey on energy efficiency in software defined networks[END_REF]. Some of the works address the problem of rule placement without considering energy savings, see [START_REF] Kang | Optimizing the one big switch abstraction in software-defined networks[END_REF], [START_REF] Kanizo | Palette: "Distributing tables in software-defined networks[END_REF] and [START_REF] Rifai | Too many SDN rules? Compress them with MINNIE[END_REF]. In other works, such as [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF] and [START_REF] Kannan | Compact TCAM: "Flow entry compaction in TCAM for power aware SDN[END_REF], both rule space capacity and energy consumption are optimized. Giroire et al. [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF] come with idea of using a default rule to deal with the rule capacity limitation. They have proposed an energy-aware routing algorithm that optimizes the rule placement of an Openflow router in backbone networks. In [START_REF] Kannan | Compact TCAM: "Flow entry compaction in TCAM for power aware SDN[END_REF], the authors propose to reduce the size of flow entries and manage large-sized SDN flows, while optimizing only the power consumption induced by the TCAM (without turning off network elements). The authors introduce the Flow-ID concept to enable a new TCAM look-up process that reduces the TCAM power cost.

Our main contribution in this work is to model SDNbased, energy-aware routing in carrier Ethernet networks while respecting the memory limitations in an Openflow switch, which is also known as rule of space capacity. Consequently, it is important to route flows on a single path when the maximum number of rules that can be installed at each node is limited.

We use the default rule for optimizing flow tables as in [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF].

To the best of our knowledge, the previous works that are the closest to ours are [START_REF] Chiaraviglio | Minimizing ISP network energy cost: Formulation and solutions[END_REF], [START_REF] Wang | Energy-aware routing algorithms in software-defined networks[END_REF] and [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF]. Our work is an extension of [START_REF] Wang | Energy-aware routing algorithms in software-defined networks[END_REF], [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF] and [START_REF] Chiaraviglio | Minimizing ISP network energy cost: Formulation and solutions[END_REF]. TABLE I gives in details the main common points and differences between our work and those proposed in [START_REF] Chiaraviglio | Minimizing ISP network energy cost: Formulation and solutions[END_REF], [START_REF] Wang | Energy-aware routing algorithms in software-defined networks[END_REF] and [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF].

III. PROBLEM STATEMENT AND FORMULATION

A. Problem statement

As an example of EAR, we consider the network topology shown in Fig. 2a. The capacity of each link is 7Gbps.

There are six traffic demands. Each demand is given by a pair of nodes (the source and destination nodes): (2, 5) and (2, 7). Similarly, demands (2, 6) and (2, 5) cannot be routed via node 2. Note that demand (1, 4) does not need to be stored in node 4's flow table as node 4 is a destination.

D = {(1, 6
As a consequence, the best EAR solution with the rule space constraint is shown in Fig. 2c and is as follows.

(1,6) :

1-3-5-6 ; (1,5) : 1-3-5 ; (1,4) : 1-3-5-4 ; (2,6) : 2-4-6 ; (2,5) : 2-4-5 ; (2,7) : 2-4-5-7
As shown in Fig. 2c, EAR can turn off only two links. Note that, links (1, 3) and (3, 5), can never be turned off. TABLE II shows the routing rules used by nodes 1 to 5, i.e., each node's flow table contains at most three rules. The flow table of node 6 and node 7 are not reported because they have no demands (rules) to handle.

To address the space limitation issue, one can use, as in [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF], default rule to optimize the flow-table size and to enhance the EAR solution. For instance, if we come back to the example in Fig. 2a and apply the default rule to the node flow tables (see Fig. 3 which contains the flow table for node 4), then the routing solution produces exactly the same topology as the one described in Fig. 2b.

In the given example of Fig. 3, before reducing the number of entries in the flow table, we cannot route more than 5 demands according to the available space. To address a large number of flow demands, port 5 is defined as a default port because it initially carried the largest number of rules. Assume that, after shrinking the rule space, we have ten flow demands to route. A feasible solution will match 4 demands with 4 distinct rules, and the 6 remaining demands will match the default one.

Rule Action (

∑ v∈ N G (u) [( f s t u v -f st v u ) + (g s t u v -g st vu )] =              -1 if u=s, 1 if u=t, 0 if u s,t, ∀u ∈ V, ∀(s, t) ∈ D, (2)
∑ (s, t )∈D d st ( f s t u v + f st v u + g st u v + g st v u ) ≤ µC e x e ∀e = (u, v) ∈ E, (3)
f st u v + f st vu + g st u v + g s t v u ≤ 1 ∀(u, v) ∈ E, ∀(s, t) ∈ D, (4)
∑ d st ∈D ∑ v∈ N G (u) f s t vu ≤ (R u -1)y u ∀u ∈ V, (5)
∑ v∈ N G (u) k u v ≤ 1 ∀u ∈ V, (6)
g s t u v ≤ k u v ∀(u, v) ∈ E, ∀(s, t) ∈ D, (7)
∑ e∈δ G (u)
x e ≤ M y u ∀u ∈ V . Inequality (3) says that the sum of traffic for all demands routed through link e = (u, v) must not exceed the tolerated link capacity µC e . Inequality (4) ensures that the flow passing through link (u,v) is routed using only one rule, which can be either a distinct or a default rule. It also guarantees that the flow for a demand (s,t) is routed in one direction on link (u,v), which can either be from u to v or from v to u. Inequality [START_REF] Nunes | A survey of software-defined networking: Past, present, and future of programmable networks[END_REF] limits the rule space to a maximum allowed rule space capacity at each node, while keeping only one rule as the default rule.

µ µ ∈]0, 1]; maximum tolerated link utilization N G (u) Set of neighboring nodes of u ∈ V δ G (u) Incident links to u ∈ V M A non-negative,
Inequalities ( 6) and ( 7) are used to restrict the default port for each node to one. Finally, inequality [START_REF] Vaishampayan | Demonstrating openflow over a carrier ethernet switch router (cesr)a services perspective[END_REF] ensures that when a node u is turned off, none of its incident links can be turned on.

Note that the choice of parameter M is crucial for the experiments. M should be greater than or equal to max

u ∈V |δ G (u)|, or largely M ≥ |V | -1.
It is very challenging, and sometimes impossible, to achieve an optimal solution using the previous ILP formulation for large topologies and dense instances. In fact, formulation (1) -

(3) falls into the class of multi-commodity integral flow problems (see [START_REF] Ahuja | Network flows: theory, algorithms, and applications[END_REF]). According to [START_REF] Addis | Energy management in communication networks: a journey through modeling and optimization glasses[END_REF], the multicommodity flow problem, with continuous flow variables, can be solved in a polynomial time. However, when flow variables are integers, the corresponding decision problem is NP-complete even when considering only two demands and unitary capacities (see [START_REF] Garey | A Guide to the Theory of NP-Completeness[END_REF]). Moreover, if we omit all the coefficients, variables and constraints related to rule space and energy optimization, then we obtain the problem studied in [START_REF] Giroire | Minimizing routing energy consumption: from theoretical to practical results[END_REF], which is proven to be NP-hard. Thus, solving the previous ILP using only exact methods for the resolution is expected to be inefficient. As a consequence, for large topologies, we choose to tackle the problem using heuristic methods.

IV. HEURISTIC ALGORITHMS

We present a set of first-fit heuristic-based algorithms that are practical for large-sized networks. The first-fit heuristic is an efficient heuristic that is widely used to solve binpacking-like problems. It was chosen for this case because it is a straightforward greedy approximation algorithm that can provide a feasible solution in polynomial-time. For more details about the bin-packing optimization problem and the first-fit heuristic, the reader may refer to [START_REF] Johnson | Fast algorithms for bin packing[END_REF], [START_REF] Xia | Tighter bounds of the First Fit algorithm for the bin-packing problem[END_REF].

We propose a centralized implementation of the heuristic algorithms into an Openflow controller. First, the controller collects information on the network topology and the user traffic demands. Then, the controller runs the heuristic to find a subset of selected nodes and links to route traffic demands. In Note that implementing energy saving heuristic algorithms will mainly involve the application modules (Topology, EAR, users' requests, statistics information). Note that a crucial step for this first-fit heuristic is the way the elements are sorted. In our algorithms, we choose three criteria to sort nodes and links:

1) First-Fit Most-Power (MP): iteratively selects the element with the highest power consumption.

2) First-Fit Least-Flow (LF): iteratively selects the element with the smallest amount of traffic already routed through it. This selection criterion is used by [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF] to sort candidate links.

3) First-Fit Random (R): randomly selects an element.

Here, Step2 is neglected because it does not need to sort the network elements. flow tables and assuming that all elements are turned on.

After sorting the elements based on a given criteria, we next apply the following procedure for nodes and then for links.

At each iteration, we remove (i.e., turn off) the first element in the ordered set. Then, we compute, for each demand (s, t), the best possible path along the residual network topology as described in Algorithm 1. The best path is the shortest path that satisfies inequalities (2)-(4). If no path exists, then the removed element is put back into the network. For the sake of simplicity and without loss of generality, when routing we consider that the weights of all links are equal to one. When a shortest path is found, the remaining capacity of the links is updated as described in Algorithm 2. Recall that, for each node u, the two sets F u and G u denote distinct and default flows respectively (see TABLE III). Initially, flow entries are created without hindrance until the flow table becomes full, and then there is no available space to assign a new rule. Then, the flow table is adjusted (line 4, Algorithm 2) by selecting the port that carries the largest number of flows, as the default port. This step has been previously described in Fig. 3.

V. PERFORMANCE ANALYSIS

In this section, we evaluate the ILP formulation and the heuristic-based algorithms. First, we describe the considered performance metrics and the experimental scenarios. Our goal is to accomplish the following evaluations:

1) a general performance analysis of the ILP model on different network instances that consider different rule space capacities;

2) a comparison of the solutions obtained using the ILP formulation with those obtained using the heuristics on the same network instances;

3) a general performance analysis of the heuristic solutions for large networks.

A. Performance metrics

The performance of the proposed resolution approaches is evaluated using five performance metrics. The first two metrics indicate the percentage of energy savings that can be obtained.

• η L o f f is the percentage of energy savings related to the links turned off by our EAR algorithms. It is computed as follows:

η L o f f = ∑ e∈E E e - ∑ e ∈E ′ E e ∑ e ∈E E e × 100. (9)
• η N o f f is the percentage of energy savings related to the nodes turned off by our EAR algorithms. It is computed as follows:

η N o f f = ∑ u ∈V E u - ∑ u ∈V ′ E u ∑ u ∈V E u × 100. (10)
The third metric, denoted by λ 2 (G), represents an important characteristic of graphs, which is the connectivity. This parameter can be computed using the Laplacian matrix of the undirected graph G , denoted by L G [START_REF] Mohar | The Laplacian spectrum of graphs[END_REF]. In graph theory, which can be ordered sequentially in an ascending order

L G is
(λ 1 (G) ≤ λ 2 (G) ≤ ... ≤ λ V (G)). For a connected graph G, λ 2 (G) > 0.
The second smallest eigenvalue λ 2 is called the algebraic connectivity of the graph [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF].

In our case, the computation of λ 2 enables to control the connectivity of the active part of the network.

As load balancing is a requirement that should be fulfilled in carrier Ethernet, the fourth metric is devoted to measuring the fairness of traffic distribution on the active links E ′ .

The fairness index FI measures if the traffic load is fairly distributed among all the links. In our performance analysis, we use Jain's Fairness Index [START_REF] Jain | The art of computer systems performance analysis: tech-niques for experimental design, measurement, simulation, and modeling[END_REF], which is given by:

F I = ( ∑ e ∈E ′ l e ) 2 |E ′ | × ∑ e ∈E ′ l e 2 , ( 11
)
where l e is the percentage of traffic utilization of link e ∈ E ′ .

Note that, when F I = 1, the traffic is distributed in a fair way.

The last metric to be introduced is related to the increase of route length. Consider a demand (s, t) ∈ D, then we define

ϕ st = L st 2 -L st 1 ,
where L st 1 is the length of path routing demand (s, t) using the shortest path without considering EAR. L st 2 is the length of the path routing (s, t) using our EAR algorithms.

L st

1 and L st 2 are given in terms of hops. Note that for (s, t) ∈ D, L st 2 ≥ L st 1 . This is obvious as EAR algorithms may turn off some elements of the graph, which may increase the length of paths.

B. Experimental context

We solve the ILP model using the solver CPLEX with Concert Technology (C++) [45]. Note that Cplex is a solver that uses exact methods of resolution to solve integer, mixed integer and quadratic programs [46]. The time limit is set to 3 hours (10800 seconds), and M parameter is set to |V | -1. The heuristic algorithms are implemented using MATLAB. All the experiments are performed on a PC with 2.6 GHz Intel Core i7 and 8GB RAM.

Data for the real network topology used by ISPs are considered confidential, so they are not easily revealed. Consequently, we consider realistic network instances collected from SNDlib [START_REF] Orlowski | SNDlib 1.0-Survivable network design library[END_REF]. TABLE V presents the main properties of the used network topologies. We consider two main types of traffic matrices:

• T M1: is a meshed traffic matrix, i.e., every node of the network appears at least in one demand as a source or destination. T M1 is nothing but the traffic matrix provided by SNDlib for the chosen networks.

• T M2: is generated from T M1 so that some randomly chosen nodes (from 10% to 15% of |V |) are assumed to be pass-through nodes (transit nodes, i.e., neither source nor destination of any demand). To generate the traffic matrix TM2, we first begin by choosing the set of nodes that will be considered as pass-through, i.e. transit nodes.

The corresponding demands in TM1 are then removed and replaced in TM2 by new ones, randomly generated, in order to maintain the same number of demands for each topology. We assume that the daily traffic patterns have the shape of Fig. 6 taken from [START_REF] Telkamp | Best Practices for Determining the Traffic Matrix in IP Networks[END_REF]. Note that the traffic matrices found in SNDlib are collected at 6:00 a.m. In order to fit the best to reality and represent the daily traffic levels, we scale T M1

and T M2 with parameter γ ranging from [0.25, 2.5].

Fig. 6: Daily traffic for different networks

We also assume, as in [START_REF] Giroire | Optimizing rule placement in software-defined networks for energyaware routing[END_REF], that the rule capacity of each

flow table is R u = (ρ × |D|) where ρ ∈]0, 1].
In all the experiments, we use the same estimation of the power consumption as in [START_REF] Capone | An optimization framework for the energy management of carrier ethernet networks with multiple spanning trees[END_REF]. The power consumption of a single line card is 150 Watts, therefore, the power consumption of a link e is E e = 300 Watts. While the consumption of node v is assumed to be E v =(1200 + |δ(v)|) Watts, where δ(v), we eval is the degree of v.

C. Computational results

In this section, we present the performance results to confirm the effectiveness of our algorithms. We start with a demonstration on the smallest test instance (i.e., Abilene network). Then, we compare the performance of the ILP model with the heuristic algorithms on nine different network topologies. Finally, we present a substantial evaluation of the heuristics with respect to the different network performance previously defined.

1) Optimal vs. heuristic solutions for Abilene network

As a first experimental evaluation, we consider the ILP model We also notice that, for all the cases, the obtained sub-graphs are always full-covering trees. Recall that, for this first set of experiments, we use a fully-meshed traffic matrix (i.e., T M1),

which implies that all the nodes must be turned on for all the solutions. All the obtained solutions are full-covering trees, which means that we succeed in routing all the demands using the minimum number of links that guarantee network connectivity (i.e., |E ′ | = |V | -1). The first column indicates the network instance characteristics.

The second column gives the rule capacity ρ which is set to the three values 9%, 20%, and 100%. The optimum column indicates if the optimal solution is found (only in

η N o f f = 0%
. This is obvious since the traffic matrix T M1 is fully meshed; therefore, no node can be turned off.

During the experiments for all network topologies except for

France and Germany50, we remark that the number of links used to route the traffic is |V | -1. As discussed earlier, this is the minimum number of links needed to route a fully meshed traffic matrix (such as T M1). We also observe that, when the original graph is dense (i.e., λ 2 (G) is high), the percentage of turned off links is important (see, for instance, Di-yuan and Pdh networks).

The impact of rule space can be noticed particularly for the France and Germany50 instances. Clearly, we notice that η L o f f increases when ρ increases as well. We can explain this by the fact that, when providing more rule space, routing the demands would be more flexible and would use fewer links. Having more rule space also makes it easier to test instances. For example, with Atlanta or Nobel-us networks, when the rule space is scarce (ρ = 9%), the ILP cannot reach optimality within the time limit. However, the same networks, when ρ = 20% and ρ = 100% are solved to optimality before reaching the time limit.

In TABLE VIII, we report the results obtained using the heuristic-based algorithms and all the possible combinations of the sorting criteria given in TABLE IV. In particular, we report the best obtained solutions, in terms of energy savings and computation times, among all the combinations of sorting criteria. Note, however, that we obtain the same energy savings for the majority of combinations, but sometimes with different sub-graph solutions, (i.e., different values of λ 2 (G ′ )).

As a first observation, the heuristic algorithms represent encouraging results in terms of execution times. In addition,

for France and Gemany50 networks, our heuristics achieve a higher percentage of energy savings compared to those achieved with the ILP model (the ILP model is stopped before reaching optimality due to the large network size).

TABLE IX and TABLE X report computational results ob-

tained by running the ILP and heuristic algorithms respectively using T M2. Note that for these tables, we do not report the values of graph connectivity, i.e., λ 2 (G) and λ 2 (G ′ ) because the latter are not significant in this case. In fact, since T M2 is a sparse traffic matrix, some nodes act as pass-through nodes in the routing process, and hence, turning off these nodes improves the energy conservation. We notice that a significant gain of energy saving is achieved with both algorithms. For T M2 like T M1, the impact of rule space is also noticed for France and Germany50 networks. As expected, the resulting energy savings increase when the rule space also increases. In Fig. 12 and Fig. 13, the obtained results are as expected.

When analyzing the results reported in

η N o f f (%) η L o f f (%) λ 2 (G) λ 2 (G ′ ) UB (W) (
When the matrix factor increases for France, Nobel-germany, Nobel-us, and Polska networks, the energy savings are reduced. However, for the other networks except Abilene, the percentage of turned off links remains almost the same for the different values of γ. This is obviously due the fact that link capacities for the these networks are sufficient to satisfy the high-valued traffic demands. Only for Abilene Network, no feasible energy savings can be achieved for high-valued traffic demands. In Fig. 14, we notice that, for

Fig. 1 :

 1 Fig. 1: Traditional networking versus SDN networking

7 Fig

 7 Fig.2billustrates how EAR allows energy savings by turning off node 3 and four links (i.e., (3,1), (3,2), (3,5) and[START_REF] Nunes | A survey of software-defined networking: Past, present, and future of programmable networks[END_REF][START_REF] Martino | Resiliency Challenges in Accelerating Carrier-Grade Networks with SDN[END_REF]). In the obtained solution, the flow table of node 2 stores

  Fig. 2: Example of EAR

  big enough constant Objective function (1) minimizes the total energy consumed by links and nodes. Constraint (2) expresses the classical flow conservation. It ensures that incoming and outgoing flows are equal for each node except for the source and destination.

Fig. 4 ,

 4 we present the software architecture running inside SDN-based network. There are three layers in an SDN architecture; (i) Application layer transfers requirements to the controller using an open application programming interface (north-bound API) that allows a better orchestration of network resources, (ii) Control layer maps the application requirements to the network resources, (iii) Infrastructure layer (data plane), consists of heterogeneous network devices that support an open Southbound API, i.e., Openflow protocol.

Fig. 4 :Fig. 5 :

 45 Fig. 4: Software architecture running inside SDN-based network

  equal to the difference between the degree matrix D G and the adjacency matrix A G , i.e., L G = D G -A G . A G is a square binary matrix |V | × |V |, where the generic matrix element a i j indicates if vertices i and j are adjacent in the graph. The degree matrix D G of G is the diagonal matrix such that d ii = ∑ j ∈V ai j. The Laplacian matrix of an undirected graph is symmetric with real eigenvalues. The eigenspectrum λ(G) of L G is defined as the set of its |V | eigenvalues,

  and the heuristics solutions for Abilene Network (|V | = 12, |E | = 15, |D| = 132), using T M1 and varying the rule space capacity. Fig. 7 and Fig. 8 present the produced topologies after applying the ILP and MP-MP heuristic algorithms to the Abilene Network instances with rule capacities ρ = 9%, ρ = 20%, and ρ = 100% respectively. In Fig. 7 and Fig. 8, the continuous lines represent the links used in the final solution to route all demands. The dashed lines are links that appeared in the original graph and that have been turned off during the optimization process. For the different values of ρ, both algorithms (ILP and MP-MP heuristic) give solutions with always 26.5% of links turned off. However, we notice through Fig. 7 and Fig. 8, that the obtained solutions for the different rule spaces are not the same. In fact, the produced sub-graphs are different for the various rule spaces. This is obvious because when the rule capacity value ρ changes, the flow table size changes as well, therefore producing different routing solutions for the same instance.

Fig. 9a andFig. 7 :Fig. 8 :Fig. 9 :

 789 Fig. 9a and Fig. 9b illustrate the distribution of metric ϕ computed for Abilene instances (ρ = 9%, ρ = 20% and ρ = 100%) using ILP and MP-MP algorithms respectively.Obviously, using EAR algorithms increases the routing path lengths, which can, for some few demands, reach 9 extra hops compared to the shortest path routes. However, more than 70%

Fig. 12 reports

 12 the percentage of turned off links using T M1. While Fig.13and Fig.14report the percentage of turned off links and nodes, respectively, using T M2.

Fig. 11 :Fig. 12 :Fig. 13 :Fig. 14 :Fig. 15 :

 1112131415 Fig. 11: Turned off links versus µ using different combinations of sorting criteria for T M1

TABLE I :

 I Similarities and differences between our work and the closest ones

				Our contribution	[21]	[29]	[30]
	Assumptions		Rule space capacity Asleep elements Traffic	Nodes/Links Unsplittable flow	-Nodes/Links Splittable flow (MILP)	-Nodes/Links Unsplittable flow	Links only Unsplittable flow
			routing	(ILP and heuristic)	Unsplittable flow (heuristic)	(ILP and heuristic)	(ILP and heuristic)
	Resolution	methods	Exact methods Heuristic methods	ILP (binary variables) Sorting policies for network elements (random; least-flow; most-power)	MILP (continuous/binary variables) Sorting policies for network elements (random; least-flow; most-power; least-links)	ILP (binary variables) Sorting policies for demands (priority order of delay)	ILP (binary variables) Sorting policies for network elements (least-flow)

TABLE II :

 II Routing rules for Fig.2c(where each node can store at most three rules)

	Node 1	Node 2	Node 3	Node 4	Node 5
	Rule	Action	Rule	Action	Rule	Action	Rule	Action	Rule	Action
	(1,6)	port 3	(2,6)	port 4	(1,6)	port 5	(2,6)	port 6	(1,6)	port 6
	(1,5)	port 3	(2,5)	port 4	(1,5)	port 5	(2,5)	port 5	(1,4)	port 4
	(1,4)	port 3	(2,7)	port 4	(1,4)	port 5	(2,7)	port 5	(2,7)	port 7

TABLE III :

 III Summary of notations

	d s t	Traffic demand from node s to t
	x e	1 if link e is in use, 0 otherwise
	y u f st u v g s t u v	1 if node u is in use, 0 otherwise 1 if flow (s, t) goes through link (u, v) by a distinct rule, 0 otherwise 1 if flow (s, t) goes through link (u, v) by the default rule, 0 otherwise
	k u v	1 if the default port of node u goes to v, 0 otherwise
	F u	Set of distinct flows
	G u V ′	Set of default flows Set of nodes used to route the traffic
	E

Notation

Description G=(V ,E )

Undirected graph where V is the set of vertices (nodes) and E is the set of edges (links

) |V | , |E | |V | is the size of V, |E | is the size of E E e Power consumption of link e ∈ E E u Power consumption of node u ∈ V C e Capacity of link e ∈ E R u

Maximum number of rules that can be installed in node u ∈ V D

Set of all traffic demands D = {(s, t), s ∈ V, t ∈ V } ′ Set of links used to route traffic

TABLE IV

 IV

	summarizes the combined node/link sorting poli-
	cies. The columns correspond to the nodes' criteria and the
	rows to the links' criteria.

TABLE IV

 IV G=(V,E), initial flow tables and rule capacity R u for all u ∈ V, link capacity C e for all e ∈ E, and a set D of demands with traffic requirements d st for all (s, t) ∈ D. Output: G'=(V',E'): the output graph containing only elements used to route the demands. 1 initially, the remaining link capacity Cr e = C e for all ′′ G computed during the turning off step, the path p(s,t), rule capacity R u , the default port def(u) for all u ∈ V, remaining link capacity Cr e , and link capacity C e for all e ∈ E. Output: Updated flow tables and updated sets of distinct F u and default G u flows. 1 assign the route p(s,t) to the demand (s, t) ; 2 update Cr e = Cr ed st for all e ∈ p(s,t) ;

	3 for each u ∈ p(s,t) do 4 if |F u | == R u then 5 adjust the flow table of the node u as illustrated in Fig. 3; 6 end 7 for each v ∈ N ′′ G (u) do 8 if ((u,v) ∈ p(s,t) AND def(u) ==v) then 9 G u = G u ∪ (s, t) ; 10 else 11 if ((u,v) ∈ p(s,t) AND def(u) v ) then	Input: e ∈ E; 2 /*Node optimization*/ 3 sort nodes according to a predefined order in node-list; 4 for (i=1; i <= |V |; i++) do 5 turn off (node-list[i]); 6 for each (s, t) ∈ D do 7 path(s, t)=compute the best possible path from s to t ; 8 if !path (s, t) then
	13 14 15 16 end end end end					9 10 11 12	turn on (node-list); else update the graph and flow tables using Algorithm 2 ; end
	Algorithm 2: Updating flow tables, F		13	end
						14 end
						15 /*Link optimization*/
						16 sort links according to a predefined order in node-list;
						17 for ( j=1 ; j<= |E |; j++) do
						18	turn off (link-list[j]) ;
						19	for each (s, t) ∈ D do
						20	path(s, t)=compute the best possible path from
						s to t ;
						21	if !path (s,t) then
						22	turn on (link-list[j]) ;
						23	else
						24	update the graph and flow tables using
						Algorithm 2 ;
						25	end
						26	end
						27 end
						Algorithm 1: First-fit heuristic-based algorithms.
						For example, the MP-MP heuristic selects respectively the
						node and the link that consumes the highest amount of power
						as a candidate to be powered off. Hence, V and E are sorted
						according to decreasing values of E u , E e respectively. The
						LF-LF heuristic turns off elements (nodes and links) with
	links	nodes	MP	LF	R
	LF		MP-LF	LF-LF	R-LF
	MP		MP-MP	LF-MP	R-MP

: Combination of sorting criteria for the first-fit heuristics X X X X X X X increasing values of traffic that was already routed through each element. Algorithm 1 describes, in detail, the different steps of our heuristics.

We start from the whole network by considering the initial

Input: A subgraph G 12 F u = F u ∪ (

s, t) ; u , and G u

TABLE V :

 V Properties of network topologies

	Network instance	|V |	|E |	|D |	Traffic matrix origin	Link capacity
					origin	(units)
	Abilene	12	15	132	6:00 am of Sept 04 t h 2004	[2480-9920]
	Atlanta	15	22	210	given by SNDlib	[575000-3200000]
	Di-yuan	11	42	22	given by SNDlib	[8200-159300]
	France	25	45	300	given by SNDlib	2500
	Germany50	50	88	662	6:00 am of Feb 15 t h 2005	[4150-3290]
	Nobel-germany	17	26	121	6:00 am of Feb 02 n d 2005	600
	Nobel-us	14	21	91	given by SNDlib	[3580-20350]
	Pdh	11	34	24	given by SNDlib	1920
	Polska	12	18	66	given by SNDlib	[4260-6804]

  TABLE VI presents the percentage of through-

	pass nodes.

TABLE VI :

 VI Percentage of pass-through nodes for T M2

	Abilene Atlanta Di	France Germany50 Nobel	Nobel Pdh Polska
			-yuan			-germ.	-us
	10%	10%	12%	10%	10%	12%	15%	10% 15%

  TABLE VII and TABLE IX). The sorting criteria column indicates the sorting policies used to run the heuristic (only in TABLE VIII and TABLE X). The energy savings column reports the percentage of turned off nodes η N o f f and edges ηL o f f . λ 2 (G)and λ 2 (G ′ ) columns report the network connectivity before and after running the EAR algorithms. In other words, λ 2 (G) is the initial graph connectivity, and λ 2 (G ′ ) is the computed graph connectivity. λ 2 (G) and λ 2 (G ′ ) are computed only for the fully meshed matrix, which is the case of T M1(TABLE VII and TABLE VIII). The gap column is computedas the ratio (UB-LB)/LB, where UB is the upper bound on

	power consumption, (the power consumption of the sub-graph
	solution), and LB is the lower bound on power consumption
	(the power consumption of the linear relaxation). Finally, the
	time column gives the computation time in seconds.

TABLE VII

 VII

	and TABLE VIII report the computational
	results obtained by running the ILP and heuristic algorithms
	respectively for T M1. First, note that for all the instances,
	the percentage of nodes turned off using both algorithms is

TABLE VII

 VII

	to TA-
	BLE X, we can state that the heuristic algorithms provided en-
	ergy saving values better than or equal to those obtained with
	the ILP model within reasonable computation times. More-
	over, the heuristic results, especially those obtained for France
	and Germany50, demonstrate the efficiency of our heuristics
	on large-sized instances. Through the obtained results we also
	observe that the performance of our heuristics is influenced
	by the number of demands, such as Atlanta (|D|=210), France

(|D|=300) and Germany50 (|D|=662). This is obvious since

TABLE VII :

 VII ILP formulation using T M1

		Rule		Energy	Graph	Optimality	Power consumption	Execution
	Network	capacity	Optimum	Saving	connectivity	gap	Upper bound	Time
		(ρ%)		η N o f f (%)	η L o f f (%)	λ 2 (G)	λ 2 (G ′ )	(%)	UB (W)	(s)
		9	yes				0.13	0		2.22
	Abilene	20	yes	0	26.65	0.309	0.176	0	17730	1.93
		100	yes				0.086	0		1.83
		9	no				0.0467	2.6		10800
	Atlanta	20	yes	0	36.35	0.422	0.0706	0	22244	1961.49
		100	yes				0.0642	0		1893.13
		9	no				0.1023	7.4		10800
	Di-yuan	20	no	0	76.15	5.793	0.0741	7.1	16284	10800
		100	no				0.0938	7.5		10800
		9	no	0	33.33		0.1267	7.9	39090	10800
	France	20	no	0	35.55	0.350	0.0416	7.7	38790	10800
		100	no	0	37.75		0.0423	7.1	38490	10800
		9	no	0	31.8		0.029	15.7	78476	10800
	Germany50	20	no	0	32.95	0.182	0.055	12.9	77876	10800
		100	no	0	34.05		0.046	10.07	77576	10800
		9	yes				0.037	0		942.541
	Nobel-germany	20	yes	0	38.45	0.301	0.063	0	25252	1076.54
		100	yes				0.049	0		10248.3
		9	no				0.113	2.1		10800
	Nobel-us	20	yes	0	38.05	0.7326	0.064	0	20742	5013.33
		100	yes				0.018	0		942.541
		9	no				0.127	5.5		10800
	Pdh	20	no	0	70.55	2.524	0.1857	4.6	16268	10800
		100	no				0.145	5.4		10800
		9	yes				0.0805	0		78.6207
	Polska	20	yes	0	38.85	0.7125	0.1318	0	17736	34.6595
		100	yes				0.126	0		42.713

TABLE VIII :

 VIII Heuristic algorithms using T M1

		Rule	Sorting	Energy	Graph	Power consumption	Execution
	Network	capacity	criteria	Saving	connectivity	Upper bound	Time
		(ρ%)

TABLE IX :

 IX ILP formulation using T M2

		Rule		Energy	Optimality	Power consumption	Execution
	Network	capacity	Optimum	Saving	gap	Upper bound	Time
		(ρ%)		η N o f f (%)	η L o f f (%)	(%)	UB (W)	(s)
		9						1.25
	Abilene	20	yes	8.33	33.33	0	16528	0.54
		100						0.13
		9						171.56
	Atlanta	20	yes	6.66	40.90	0	20740	635.06
		100						3514.68
		9						3791
	Di-yuan	20	yes	09.09	78.57	0	14776	10800
		100						10800
		9		8	46.66	4.4	35183	10800
	France	20	no	8	44.44	3.8	34883	10800
		100		8	44.44	3.8	34883	10800
		9		10	42.04	27.1	70668	10800
	Germany50	20	no	6	39.77	27.5	70668	10800
		100		6	39.77	12.9	69454	10800
		9						14.63
	Nobel-germany	20	yes	11.76	46.15	0	22244	18.22
		100						14.51
		9						370.08
	Nobel-us	20	yes	14.28	47.61	0	17736	210.08
		100						1387.4
		9						6222.73
	Pdh	20	yes	9.09	73.52	0	14762	6474.38
		100						4384.39
		9						19.92
	Polska	20	yes	16.66	50	0	14728	14.55
		100						3.42

TABLE X :

 X Heuristic algorithms using T M2

		Rule	Sorting	Energy	Power consumption	Execution
	Network	capacity	criteria	Saving	Upper bound	Time
		(ρ%)		η N o f f (%)	η L o f f (%)	UB (W)	(s)
		9	MP-LF
	Abilene	20	MP-LF	8.33	33.33	16528	< 1
		100	LF-LF
		9	MP-LF
	Atlanta	20	LF-LF	6.66	40.90	20740	< 25
		100	MP-LF
		9	R-MP
	Di-yuan	20	R-MP	09.09	78.57	14776	< 40
		100	LF-MP
		9	MP-LF
	France	20	MP-LF	8	51.11	34577	< 743
		100	MP-MP
		9	MP-LF
	Germany50	20	MP-LF	10	50	67359	< 11282
		100	MP-LF
		9	LF-LF
	Nobel-germany	20	MP-MP	11.76	46.15	22244	< 10
		100	R-MP
		9	MP-LF
	Nobel-us	20	MP-LF	14.28	47.61	17736	< 27
		100	MP-LF
		9	R-MP
	Pdh	20	MP-MP	9.09	73.52	14762	< 49
		100	MP-LF
		9	MP-MP
	Polska	20	LF-LF	16.66	50	14728	< 15
		100	MP-LF
	of the sorting criteria.

the heuristic algorithms are based on a demand re-routing process after turning off selected nodes/links at each iteration.

3) Heuristics performances analysis

In what follows, we evaluate our heuristics with France, Germany50, and Nobel-germany networks using T M1 and based on the performance metric ϕ. The increase in the path lengths for these networks using the MP-MP heuristic algorithm is reported in Fig. 10.

We first remark that a significant fraction of demands (30% to 50%) is not affected by path length increase (ϕ = 0).

However, the increase in path length reaches for a small fraction of demands an important number of hops. An example is Germany50 Network, where the path length increases by 20 hops. Consequently, restrictions on the maximum number of hops should be considered in the future using additional constraint especially for large-sized networks.

We can limit the path length (in terms of hop) by adding the following constraint:

We also can limit paths length increase using the following path delay constraint:

where lat uv is the edge delay and latency st is the delay of the demand (s, t).

Further analysis is needed to evaluate the different sorting criteria used for the heuristic algorithms that are always applied to France, Germany50 and Nobel-germany networks.

To this end, we evaluate the different heuristics performances when the maximum link utilization µ on the network varies. In Fig. 11, we present the percentage of turned off links using the heuristic algorithms when considering