Joanna Moulierac

Khoa Truong
email: truongkhoa.phan@inria.fr

Phan

Optimizing IGP link weights for energy-efficiency in multi-period traffic matrices

Keywords: Robust Network Optimization, Energy-aware Routing, Green Networking, Traffic Engineering

Recently, due to the increasing power consumption and worldwide gases emissions in ICT (Information and Communication Technology), energy efficient ways to design and operate backbone networks are becoming a new concern for network operators. Since these networks are usually overprovisioned and since traffic load has a small influence on power consumption of network equipments, the most common approach to save energy is to put unused line cards that drive links between neighbouring routers into sleep mode. To guarantee QoS, all traffic demands should be routed without violating capacity constraints and the network should keep its connectivity. From the perspective of traffic engineering, we argue that stability in routing configuration also plays an important role in QoS. In details, frequent changes in network configuration (link weights, slept and activated links) to adapt with traffic fluctuation in daily time cause network oscillations. In this work, we propose a novel optimization method to adjust the link weights of Open Shortest Path First (OSPF) protocol while limiting the changes in network configurations when multi-period traffic matrices are considered. We formally define the problem and model it as Mixed Integer Linear Program (MILP). We then propose an efficient heuristic algorithm that is suitable for large networks. Simulation results with real traffic traces on three different networks show that our approach achieves high energy saving while keeping the networks in stable state (less changes in network configuration).

Introduction

Recent studies have shown that ICT is responsible for 2% to 10% of the worldwide power consumption [START_REF]An inefficient Truth[END_REF][START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF]. For example, the Global e-Sustainability Initiative has estimated that the overall network energy requirement for European telecommunication will be around 35.8 TWh in 2020 [START_REF] Bolla | The Potential Impact of Green Technologies in Next-generation Wireline Networks: Is There Room for Energy Saving Optimization?[END_REF]. As estimation, energy consumption of backbone networks can increase to 40% of the total network power requirements by 2017 [START_REF] Lange | Energy-related aspects in backbone networks[END_REF]. Therefore, telecom operators and Internet service providers (ISP) have raised their interest in energy efficiency for backbone networks (see the surveys [START_REF] Bolla | Energy Efficiency in the Future Internet: A Survey of Existing Approaches and Trends in Energy-Aware Fixed Network Infrastructures[END_REF][START_REF] Bianzino | A Survey of Green Networking Research[END_REF]). While the traffic load has a marginal influence, the power consumption is mainly due to active elements on IP routers such as ports, line cards, base chassis, etc. [START_REF] Mahadevan | A Power Benchmarking Framework for Network Devices[END_REF]. Based on this observation, the energy-aware routing (EAR) approach aims at minimizing the number of used links while all the traffic demands are routed without any overloaded links [START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF][START_REF] Gupta | Greening of the Internet[END_REF]. In fact, turning off entire routers can gain significant energy saving, however, it takes time for turning on/off and also reduces life cycle of devices. Therefore, as in many existing works [START_REF] Chiaraviglio | Sleep Modes Effectiveness in Backbone Networks with Limited Configurations[END_REF][START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF], we assume to turn off (or put into sleep mode) only the links.

Following the green networking trend, we found a number of recent works that have been devoted to both energy-aware traffic engineering and shortest path routing [START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF][START_REF] Francois | Green IGP Link Weights for Energy-efficiency and Load-balancing in IP Backbone Networks[END_REF][START_REF] Shen | Routing On Demand: Toward the Energy-Aware Traffic Engineering with OSPF[END_REF][START_REF] Capone | OSPF Optimization via Dynamic Network Management for Green IP Networks[END_REF][START_REF] Lee | Link Weight Assignment and Loop-free Routing Table Update for Link State Routing Protocols in Energy-aware Internet[END_REF][START_REF] Cianfrani | An OSPF-Integrated Routing Strategy for QoS-Aware Energy Saving in IP Backbone Networks[END_REF][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] Amaldi | Energy Management in IP Traffic Engineering with Shortest Path Routing[END_REF]. These works consider the most widely used Internal Gateway Protocol (IGP) in IP networks, namely the Open Shortest Path First (OSPF) protocol. To save energy, a set of link weights should be used so that its induced shortest paths use a minimal number of active links. Then, inactive network elements are put into sleep mode to save energy.

To deal with traffic variation, daily time periods are characterized by different traffic levels (e.g. morning, afternoon and night) and in each period, a single traffic matrix is assumed to be accurately collected. Then, each traffic matrix is associated with a corresponding weight setting configuration. As assumed in literature [START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF][START_REF] Francois | Green IGP Link Weights for Energy-efficiency and Load-balancing in IP Backbone Networks[END_REF][START_REF] Shen | Routing On Demand: Toward the Energy-Aware Traffic Engineering with OSPF[END_REF][START_REF] Addis | Energy Management Through Optimized Routing and Device Powering for Greener Communication Networks[END_REF], as long as the network capacity is sufficient to handle all traffic demands, energy can be saved without causing service degradation to end users. Recall that [START_REF] Capone | OSPF Optimization via Dynamic Network Management for Green IP Networks[END_REF] proposes to integrate [START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF] in an off-line/on-line framework to guarantee both network responsiveness and prevent frequent oscillations. As explained in [START_REF] Chiaraviglio | Sleep Modes Effectiveness in Backbone Networks with Limited Configurations[END_REF][START_REF] Fortz | Optimizing OSPF/IS-IS Weights in a Changing World[END_REF], frequent changes to link weights are highly undesirable and should be avoided as much as possible. First, applying a large number of configurations may result in frequent transitions between active and sleep modes of network links. This reduces the life cycle of network devices, since they are designed to be always powered on. Second, routing protocol convergence at the IP layer is affected. The weight changes have to be flooded in the network via control messages. The routers then recompute the shortest paths and update their routing tables. This may take seconds before all routers agree on the new shortest paths. Meanwhile, in this transient time, packets may arrive out of order, degrading the perceived QoS for end-users. We refer the reader to [START_REF] Basu | Stability Issues in OSPF Routing[END_REF] for a detailed analysis of the stability issues in OSPF. In general, the more weight changes we try to flood simultaneously, the more chaos we introduce in the network [START_REF] Fortz | Optimizing OSPF/IS-IS Weights in a Changing World[END_REF]. In this paper, we propose some methods to reduce the number of changes in weight setting for the multi-period energy-aware traffic engineering problem. In summary, we make the following contributions:

• Based on the Mixed Integer Linear Program (MILP) in [START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF], we formulate the stable OSPF weight setting model for multi-period traffic matrices.

The objective is to limit the changes in the weight setting in transitions between traffic matrices.

• We also present a MILP robust formulation so that even a single weight setting can be feasible for a set of traffic matrices. Different from the stable weight setting, the robust one avoids any weight changes for the multiperiod traffic matrices with the assumption that only a limited number of traffic demands are at their peaks simultaneously.

• We propose heuristic algorithms that are effective for large networks for both the stable weight setting and the robust methods.

• Using real-life data traffic traces, we show that our methods achieve high energy saving while significantly reducing the number of network reconfigurations in daily traffic variation.

The rest of this paper is structured as follows. We summarize related works in Section 2. Then, our novel approaches to deal with traffic variation are introduced in Section 3. Simulation results are presented in Section 4. Finally, we conclude the work in Section 5.

Related work

General energy-aware routing (EAR)

As an example of EAR, we consider a network topology as a grid 3×4 (Fig. 1). Each link of the network has capacity 4 Gbps. There are three traffic demands: (0, 3), [START_REF] Lange | Energy-related aspects in backbone networks[END_REF][START_REF] Mahadevan | A Power Benchmarking Framework for Network Devices[END_REF] and [START_REF] Gupta | Greening of the Internet[END_REF][START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF], all with volume 1 Gbps. The shortest path routing, as shown in Fig. 1d, uses 9 active links whereas the remaining 8 links can be put into sleep mode. However, since there is enough capacity to aggregate the three traffic demands as in Fig. 1a, EAR solution allows 10 links to sleep, thus energy consumption is further decreased. The problem of minimizing the number of active links under capacity constraints can be precisely formulated using Mixed Integer Linear Programming (MILP). However, this problem is known to be NP-Hard [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF], and exact solutions can only be found for small networks using MILP. Thus, many heuristic algorithms have been proposed to find admissible solutions for large networks [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF][START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF].

In this work, we focus on using shortest path routing (e.g. OSPF protocol) to deploy energy-aware routing in a network. We found some recent works that have been devoted to energy-aware traffic engineering with shortest path routing [START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF][START_REF] Francois | Green IGP Link Weights for Energy-efficiency and Load-balancing in IP Backbone Networks[END_REF][START_REF] Shen | Routing On Demand: Toward the Energy-Aware Traffic Engineering with OSPF[END_REF][START_REF] Capone | OSPF Optimization via Dynamic Network Management for Green IP Networks[END_REF][START_REF] Lee | Link Weight Assignment and Loop-free Routing Table Update for Link State Routing Protocols in Energy-aware Internet[END_REF][START_REF] Cianfrani | An OSPF-Integrated Routing Strategy for QoS-Aware Energy Saving in IP Backbone Networks[END_REF]. In these works, the authors try to optimize the link weight setting so that the induced shortest path routing uses a minimum number of active links. However, they do not consider the stability in routing configuration in multi-period traffic matrices. We show that this limitation would decrease QoS when performing traffic engineering, therefore we propose some methods to address the problem in this paper (Section 3).

Optimizing weight setting for EAR

EAR routing can be applied to a network by setting an appropriate link weight setting. By assigning high weights to a set of links, no traffic passes through them and these links can be put into sleep mode to save energy. To better explain, we consider an example of a network topology with capacity on links as shown in Fig. 2a. There are 3 traffic demands and we collect their values at 3 different periods, leading to 3 traffic matrices M 1 , M 2 and M 3 (Table 1). The routing solutions in Fig. 2 follow OSPF/ECMP (Equal-cost multi-path) policy: a traffic demand flowing through a node i is equally split among all the interfaces connected to i which belong to at least one shortest path toward the considered destination. As shown in Fig. 2b, the three traffic demands are split among 3 different paths from 0 to 5, each path carries (30 + 30 + 10)/3 = 70/3 < 24. So, this routing is feasible but zero link can sleep. When traffic decreases, we can have better solutions. For example, 2 and 3 links are put in sleep mode for M 2 (Fig. 2c) and M 3 (Fig. 2d), respectively. The problem of optimizing the OSPF weight setting is known to be NP-hard, exact formulation and heuristic algorithm have been proposed in literature [START_REF] Fortz | Optimizing OSPF/IS-IS Weights in a Changing World[END_REF][START_REF] Fortz | Internet Traffic Engineering by Optimizing OSPF Weights[END_REF].

Mixed integer linear program (MILP)

The MILP for the optimal OSPF weight setting problem was proposed in [START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF]. In this section, we reformulate the MILP to fit with our robust model (Section 2.3). The MILP uses the notations detailed on Table 2 The objective function (1) minimizes the power consumption of the network represented by the number of active links. Constraints (2) establish the classical flow conservation constraints. We consider an undirected link capacity model [START_REF] Raack | On Cut-based Inequalities for Capacitated Network Design Polyhedra[END_REF] in which the capacity of a link is shared between the traffic in both directions. Constraints (3) limit the available capacity of a link (where µ denotes the maximum link utilization). The binary variable k t uv = 1 if and only if the link (u, v) belongs to one of the shortest paths from node u to node t. Constraints (4) are for ECMP routing. It makes sure that if k t uv = 1 then the flow f st vu destined to node t is equal to z st u , which is the common value of the flow assigned to all links outgoing from u and belonging to one of the shortest paths from u to t. Constraints (5) force f st uv = 0 for all links (u, v) that do not belong to a shortest path to node t. The variable r t u represents the cost of the shortest path from u to t. Constraints (6) compute the weight of link (u, v) if it belongs to the shortest path from u to t. Constraints [START_REF] Mahadevan | A Power Benchmarking Framework for Network Devices[END_REF] force link (u, v) to be on if it belongs to the shortest path from u to t. Note that, we do not force x uv = 0 when k t uv = 0 because if (u, v) belongs another shortest path to t 1 (in this case k t1 uv = 1 and x uv should be equal to 1). Constraints ( 8)-( 10) guarantee that if a link weight is equal to w max , then this link should be put into sleep mode.

f st vu -f st uv =      -1 if u = s, 1 if u = t, 0 else ∀u ∈ V, (s, t) ∈ D (2) (s,t)∈D D st (f st uv + f st vu ) ≤ µC uv x uv ∀(u, v) ∈ E (3) 0 ≤ z st u -f st uv ≤ 1 -k t uv ∀(s, t) ∈ D; (u, v) ∈ E (4) f st uv -k t uv ≤ 0 ∀(s, t) ∈ D; (u, v) ∈ E (5) 1 -k t uv ≤ r t v + w uv -r t u ≤ (1 -k t uv )M ∀t ∈ D t ; (u, v) ∈ E ( 6
)
k t uv -x uv ≤ 0 ∀t ∈ D t ; (u, v) ∈ E (7) w uv ≥ (1 -x uv )w max ∀(u, v) ∈ E ( 8
)
x uv + w uv ≤ w max ∀(u, v) ∈ E (9) 1 ≤ w uv ≤ w max ∀(u, v) ∈ E (10) x uv , k t uv ∈ {0, 1}; f st uv , z st u ∈ [0, 1]; r t u ≥ 0 (11)

Heuristic algorithm

Finding the optimal OSPF weight setting that deals with energy saving and/or traffic engineering issues is very challenging. We found in literature many works trying to solve this problem using heuristic approaches. For example, the authors in [START_REF] Fortz | Internet Traffic Engineering by Optimizing OSPF Weights[END_REF][START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF] have proposed to use local search by iteratively modifying the OSPF weights so as to achieve the objective. The authors in [START_REF] Francois | Green IGP Link Weights for Energy-efficiency and Load-balancing in IP Backbone Networks[END_REF] have used genetic algorithms to find the link weights for the joint-optimization of load-balancing and energy efficiency. As the traffic matrices are considered independently, these algorithms can find different sets of link weights in the optimization process for each traffic matrix. We call these methods as freely changed weight setting.

Γ-robust network design

Over the past years, robust optimization has been established as a special branch of mathematical optimization allowing to handle uncertain data [START_REF] Ben-Tal | Robust optimization[END_REF]. A specialization of robust optimization, which is particularly attractive by its computational tractability, is the so-called Γ-robustness concept introduced by Bertsimas and Sim [START_REF] Bertsimas | The Price of Robustness[END_REF]. As observed in real traffic traces, only few of the demands are simultaneously at their peaks at a given time [START_REF] Koster | Robust Network Design: Formulation, Valid Inequalities, and Computations[END_REF][START_REF] Zheng | Joint Power Optimization of Data Center Network and Servers with Correlation Analysis[END_REF]. For instance, Fig. 3 shows real traffic traces of the three source-destination pairs: (a) Washington D.C. -Los Angeles, (b) Seattle -Indianapolis, and (c) Seattle -Chicago in the US Abilene Internet2 network in intervals of 5 mins during the first 10 days of July 2004 [START_REF] Koster | Robust Network Design: Formulation, Valid Inequalities, and Computations[END_REF]. We observe that there is no point that all the three demands are at the peak values at the same time. Thus, it confirms the assumption: it is unlikely that all the traffic demands assume their peak values simultaneously. Γ-robust network design allows to choose an integer parameter Γ ≥ 0 so that at most Γ traffic demands can be at their peak values simultaneously. Note that, the model only limits a number of traffic demands (but not exactly which ones) that can be at their peaks at the same time. Therefore, from a practical perspective, by varying the parameter Γ, different solutions can be obtained with different levels of robustness. This concept has already been applied to several network optimization problems [START_REF] Koster | On the Robustness of Optimal Network Designs[END_REF][START_REF] Addis | A Robust Optimization Approach for Energy-aware Routing in MPLS Networks[END_REF][START_REF] Coudert | Robust Redundancy Elimination for Energy-aware Routing[END_REF].

To better explain, we consider an example in Fig. 1. Again, we use a grid 3 × 4, each link has a capacity 4 Gbps (Fig. 1). There are 3 traffic demands, each has a nominal and peak values (in Gbps) as shown in Table 3. As an example, assume that Γ = 2, meaning that zero, one or two traffic demands can be at their peak values simultaneously. This leads to a combination of seven possibilities that are shown in Table 4. The set Q includes these seven cases.

It is easy to see that in Case 1, all traffic demands are at nominal values, hence as EAR, Fig. 1a is the best solution with only 7 active links. In Case 2, when (0, 3) is at peak (4 Gbps), solutions in Fig. 1b and Fig. 1d are feasible. However, Fig. 1b is the best solution since only 8 active links are used. Similarly, in Case 7, solutions in Fig. 1c and Fig. 1d are feasible and Fig. 1c is the best one. In summary, Table 4 shows a set of possible traffic realizations and the corresponding best solution when Γ = 2. However, since we just limit the number demands (but not any specific demands) to be deviated, a feasible solution should be the one that satisfies all the seven cases. Therefore, Fig. 1d is the only feasible solution for Γ = 2. It is also easy to check that, if we limit Γ = 1 (less robust), Fig. 1b is the best solution. From these examples, we can observe that, depending on the desired robustness of a network, a single routing solution can be feasible for many traffic matrices.

In this paper, our goal is to avoid weight changes as much as possible between multi-period traffic matrices while minimizing energy consumption for the networks. The main contributions are presented in Section 3, where we propose two methods to stabilize the OSPF weight setting (called stable weight setting and Γ-robust approach). To better assess the algorithm performance in terms of energy saving, we have implemented a simple freely changed weight setting algorithm (in Section 3.1.3) to compare with the stable weight setting and the Γ-robust approach.

3. Optimizing OSPF weight setting in multi-period traffic matrices

Stable weight setting

In this approach, multi-period traffic matrices are used to capture the daily traffic pattern. However, these traffic matrices are not considered independently. The idea is that, when changing from a more to a less traffic matrix (traffic load is reducing), we only consider to sleep unused links. In other words, any set of active links for low traffic is included in that of higher traffic. In addition, the weight setting of remaining links are unchanged. The reason is to limit changes in routing configuration and reduce network oscillations that affect QoS. As we add restrictions, stable weight setting has less potential in saving energy than the freely changed weight setting approach. For instance, as the example in Fig. 2, when traffic changes from M 2 to M 3 , the stable weight setting can not have solution like Fig. 2d as both turning on and off links are necessary.

Since we try to stabilize the weight setting based on the previously used one, a question is how to find an initial weight setting that will be used for all the matrices of the multi-period traffic matrices. In fact, there are many ways to set link weights in practice. For instance, Cisco uses the inverse of link capacity; or more complicated load-balancing traffic engineering methods can be found in [START_REF] Fortz | Optimizing OSPF/IS-IS Weights in a Changing World[END_REF][START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF][START_REF] Francois | Green IGP Link Weights for Energy-efficiency and Load-balancing in IP Backbone Networks[END_REF]. Actually, the initial set of weight has an impact on the energy saving in daily time. We can use the freely changed weight method to find a good configuration for a traffic matrix. However, this configuration may not be good for subsequent traffic matrices and how to find a good starter for the whole day traffic variation is beyond the scope of this paper. In this work, the network operators are free to choose their own weight setting. Anytime they would like to start energy saving mode, the stable algorithm can be applied directly using the current weight setting configuration as the initial one. We propose an exact formulation and heuristic algorithms for the stable weight setting method in the following sections.

Stable weight MILP

The inputs are network topology G = (V, E), traffic matrix D and a set of current link weights W . The output is a routing solution that minimizes the number of active links so that it satisfies constraints (2) - [START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF]. Meanwhile, as the weight setting W should not be modified, following constraints should be added to the model ( 1) -( 11):

w uv -w * uv ≥ (1 -x uv )(w max -w * uv ) ∀(u, v) ∈ E (12) w * uv -w uv ≥ (x uv -1)w max ∀(u, v) ∈ E ( 13
)
We note w * uv as the current weight of the link (u, v). Constraints ( 12) -( 13) are used to force the new link weight w uv to be equal to w * uv if the link (u, v) is still used in the new routing solution. Otherwise, w uv is set to w max and the link (u, v) is put into sleep mode.

Stable Weight Heuristic

The stable weight setting problem is also very challenging for large networks. We propose in this section heuristic algorithms that can find feasible solution in an acceptable time. In brief, the heuristic algorithm includes sleeping step and feasible routing check step (Fig. 4).

Figure 4: Heuristic diagram

There are many criteria to choose a link (u, v) to sleep (see in [START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF][START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF]). In this paper, we propose to choose the min load link to sleep since this approach has been successfully applied in literature [START_REF] Amaldi | Energy-aware IP Traffic Engineering with Shortest Path Routing[END_REF][START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF][START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF][START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF][START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF][START_REF] Giroire | Optimizing Rule Placement in Software-Defined Networks for Energy-aware Routing[END_REF]. After the sleeping step, the feasible routing check step has inputs which are a subgraph G , a subset of link weights W and the same traffic matrix D. We perform OSPF/ECMP routing for D on G and check if some links are overloaded. If yes, the routing is not feasible, we mark the slept link as checked and go back to the sleeping step to find another link to make sleeping (the checked links will not be chosen). If the routing is feasible, we update the inputs and go back to the sleeping step to continue. This procedure is repeated until all links on the network are checked.

To deal with multi-period traffic matrices, we first sort the traffic matrices in non-increasing order of traffic load, that is from D n to D 1 . The traffic load is computed as the sum of the volumes of all traffic demands in a traffic matrix. Then, we run the MILP or heuristic algorithm for D n to find a feasible network configuration (link weight setting, set of links to sleep). Given this configuration as input, we find new feasible configuration for D n-1 in which we consider only to sleep links and the remaining links keep the same weight setting. As the traffic load of D n is larger than that of D n-1 , it is highly probable to use more active links in D n than in D n-1 . This process is repeated until we reach D 1 . Following the traffic variation of daily time, from a low to higher traffic matrices (e.g. D i to D i+1 ), we simply apply the configuration that has been found (from D i+1 to D i ). In this scenario, only slept links are woken up and the remaining links keep the same weight setting.

Freely changed weight heuristic

In order to compare the energy saving of the stable weight heuristic, we implemented a simple freely changed weight heuristic algorithm. Using the same diagram as in Fig. 4, at the feasible routing check step, we follow the idea of local search used in [START_REF] Fortz | Internet Traffic Engineering by Optimizing OSPF Weights[END_REF]. If the routing is infeasible, instead of marking the link as "checked" (impossible to sleep), we repeat the local search step, trying to find another feasible weight setting. The main idea is that: in each iteration, we increase the weights of the overloaded links to redirect traffic to other links, hoping that a new feasible routing solution can be found. Depending on the execution time of the algorithm, we can define a maximum number of loops for the local search. If there is still no feasible solution at the end of the iteration, we mark that link as "checked", then the algorithm repeats the sleeping step described in Fig. 4 with another chosen link.

Γ-robust approach: one network configuration for all

We propose in this sub-section a method to find a single nework configuration with a set of active links and weight setting that is feasible for all the considered traffic matrices.

Robust MILP

Assume that each traffic demand has a nominal D st and a deviated value where f st e = f st uv + f st vu ; Q is a subset containing demands that can be at peaks at the same time. The constraints ( 14) is non-linear since it contains the max notation. A trivial way to make it linear is to explicitly write down all the possibilities of the constraints, that is:

D st so
(s,t)∈D D st f st e + (s,t)∈Qi D st f st e ≤ µC e x e ∀Q i ⊆ D; |Q i | ≤ Γ; e ∈ E ( 14
)
Obviously, the constraints ( 14) is a combination of all possibilities of a subset Q i which has the size |Q i | ≤ Γ. Therefore, it is impractical to put all the constraints into the MILP model at one time when the set of demand D is large. To overcome this problem, we apply the method Γ-robustness (introduced by Bertsimas and Sim [START_REF] Bertsimas | The Price of Robustness[END_REF]). The main idea of this method is to use LP duality to make a compact formulation, so that it is possible to solve the MILP. We present step-by-step the procedure to form the compact formulation as follows.

Assume that we know the value of f st e (then they are constants), the maximum part of ( 14) can be computed by the following ILP:

β(f, Γ) := max (s,
ρ st e , π e ≥ 0 ∀(s, t) ∈ D ( 20
)
Since the constraints ( 18)-( 20) are linear. A compact reformulation can be obtained by embedding them into (1)-( 13). As a result, the robust stable weight setting can be compactly formulated as ( 1)-( 2), ( 4)-( 13) and replace (3) by:

(s,

Robust heuristic algorithm

The main idea of the heuristic algorithm is similar to the diagram in Fig. 4. However, is is difficult to check routing feasibility since we do not know explicitly which traffic demands are at peak values. To deal with this problem, we use the ILP constraints ( 21)-( 23) for the feasible routing check step as they represent the robust capacity constraints. In details, we consider a simplified MILP of the robust weight setting in which we only keep constraints (11) (remove variables k t uv , z st u , r t u ), and ( 21)-( 23):

(s,t)∈D (D st f st e + ρ st e ) + Γπ e ≤ µx e C e ∀e ∈ E π e + ρ st e ≥ D st f st e ∀(s, t) ∈ D; ∀e ∈ E ρ st e , π e ≥ 0; x e ∈ {0, 1}; f st e ∈ [0, 1] ∀(s, t) ∈ D; ∀e ∈ E
The OSPF/ECMP routing on G with a set of link weight W implicitly satisfies the flow conservation constraint. In addition, we have in hand a set of link weight W , therefore all the constraints (2) - [START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF] are not needed in the simplified ILP. When performing OSPF/ECMP routing for the subgraph G (after the sleeping step), we can get all the values of f st e and x e (x e = 0 if f st e = 0 ∀(s, t) ∈ D, otherwise x e = 1). Given them as the inputs, the variables x e and f st e in the simplified MILP are now fixed, only ρ st e and π e remain variables. Since the simplified MILP is used only to verify routing solution, we ignore the objective function. To check routing feasibility, we run the simplified MILP with inputs: G , D, Γ, f st e and x e , if a feasible solution is returned, it means that the routing solution satisfies the robust capacity constraints. Then, we go back to the sleeping step and continue the algorithm as in Fig. 4.

Computational evaluation

We solved the MILP models with IBM CPLEX 12.4 solver. All computations were carried out on a 2.7 Ghz Intel Core i7 with 8 GB RAM. We consider reallife traffic traces collected from the SNDlib [START_REF] Sndlib | [END_REF] In our test instances, five traffic matrices (D1 -D5) are used to represent daily traffic pattern (Fig. 5). From the SNDlib, we collect the mean and max traffic matrices (all traffic demands are at their mean and maximum values). Since traffic load is low, the mean traffic matrix is referred D1. To achieve a network with high link utilization, we scale the max traffic matrix with a factor of 1.3, 1.5, 1.8 and 2.0, in order to form D2 -D5, respectively. As a result, we represent D5 as the worst case scenario of highest traffic load. It is noted that, in reality, even at peak hour, not all the traffic demands are at their maximum values simultaneously as the case D5. The simulation results in this paper are based on the shape of the scaled traffic matrices D1 -D5. The results might be different if traffic demands vary more independently. In all test cases, as an approach of traffic engineering, we use a local search heuristic to find a set of link weights that minimize the maximum link load [START_REF] Fortz | Internet Traffic Engineering by Optimizing OSPF Weights[END_REF] for the traffic matrix D5. This weight setting is used as the initial one in the stable weight approaches. For Abilene network, we can find optimal solution using the MILP for the three methods (stable, robust and freely changed weight). For larger network (e.g. Geant, Germany50), it is not possible to find even a feasible solution within 2 hours using the MILP, thus only the heuristic algorithms are used to find solutions for these large networks. The execution time of the freely changed weight heuristic is limited to one hour by varying the number of loops in the local search. For the robust stable weight, we run with different values of Γ and get an average running time.

Computation time

It is clear that the stable weight and robust methods win a lot in running time. Indeed, these methods are based on an initial weight setting with a limited number of changes. Note that, we also use an initial weight setting for the robust case to limit network reconfiguration when changing from the normal (currently used) mode to the energy-aware mode. Thus, solution search space is small and optimal solutions can be found quite fast. Similar observation can be found for the heuristic approaches (Tables 6 and7): the stable weight and robust methods take less than 1 hour for all test cases, meanwhile the execution time of the freely changed weight reaches the time limit (set to 1 hour).

Stability of routing solutions

Fig. 6 shows changes in routing when shifting between periods of traffic during daily time. For the three tested networks, the stable weight approach always outperforms the freely changed weight. The former approach only allows to sleep links (resp. only wake up links) when changing from a high traffic matrix to a lower one (resp. from a low to a higher traffic matrix). However, for freely changed weight, there is no restriction, link can be turned on and off and also the weight setting of remaining links can be changed. For instance, in Abilene network, from D3 to D2, even the energy saving (and the number of active links) is unchanged, the solution allows one link to turn off, one link to turn on and two active links change their weights. Similar observation can be found for Geant and Germany networks (Fig. 6c -Fig. 6f). The larger the network we consider, the more chaos we introduce as more changes happen between multi-period traffic matrices.

Energy saving in daily time

Stable weight vs. freely changed weight

We show in Fig. 7 the energy saving of the three networks with traffic matrices in daily time. The energy saving is computed in comparison with the case when all links on the networks are active. It is clear that energy saving is high when traffic load is low since more links can be put into sleep mode to save energy. To compare between stable weight and freely changed weight approaches, the latter one can save more energy because it is flexible to change the weight setting. This can be observed in D3, D4, D5 in Fig. 7b and D3, D5 in Fig. 7c. Abilene network is small and only a few links (from 1 to 4 links) can sleep, thus the solutions between the two methods are similar. It is noted that, in D4 (Fig. 7c), stable weight method even has better result. Indeed, we limit the number of loops so that the heuristic algorithm is finished after one hour. Thus, the freely changed weight heuristic may stop before finding a better solution than the stable weight approach. This can happen for large network is large, where the algorithm does several loops to find a good solution.

Robust vs. stable weight approaches

Fig. 8 shows energy saving of the stable weight setting vs. the Γ-robustness (with different value of Γ) in daily time traffic variation. We exploit the robustness to obtain a single on-off pattern for the whole day. Each dash line of the robust method corresponds to a Γ value which is applied for the whole day. For instance, in Abilene network (Fig. 8a), when Γ is less than 7%, we can find a single on-off feasible configuration which can save around 27% of energy for the whole day. Simulation results also confirm that the higher Γ is, the more robust, but the less power savings we achieve. Note that, when Γ = 100%, the robust model becomes the worst case of the deterministic -the case with D5 (all traffic demands are at their peak values). In all the three networks, the solutions do Therefore when the values of Γ cover all of these dominating demands, increasing Γ does not affect the routing solution and the percentage of energy saving remains the same. To give a visualized comparison, we also draw energy saving of the stable weight method in daily time. For instance, from Fig. 8a, if Γ = 9%, it is possible to have only one weight setting that gives feasible routing if at most 9% of traffic demands are at their peaks simultaneously. Moreover, this single weight setting allows to save the same amount of energy as the stable weight method for D2 or D3 matrices. Similar observations can be found for Geant (Fig. 8b) and Germany network (Fig. 8c). However, Geant and Germany networks are more sensitive with traffic variation, and significant energy saving is found only with small Γ.

Traffic load 4.4.1. Stable weight vs. freely changed weight

In the simulation, we set the maximum link utilization µ = 100%. Intuitively, EAR would affect the utilization of links as fewer links are used to carry traffic. In this subsection, we evaluate the impact of EAR on link utilization. We draw the cumulative distribution function (CDF) of link load of Abilene, Geant and Germany networks in Fig. 9. To test the worst case scenario, we use the If one network configuration fits for all is too greedy, a few robust configurations are also enough for the whole day traffic. For instance, in Abilene network, we can use 4 periods: 2h -9h (Γ = 7%); 9h -11h (Γ = 13%); 11h -19h (Γ = 100% -D5 traffic matrix) and 19h -2h (Γ = 13%). However, it may save less energy with respect to the stable weight approach as daily traffic is divided into 9 periods and we assume that traffic matrix is accurately collected for each period.

Conclusion

To the best of our knowledge, this is the first work considering the stability of routing solution in energy-aware traffic engineering using OSPF protocol. We argue that, in addition to capacity constraints, the requirements on routing stability also play an important role in QoS. Moreover, using real traffic traces in the simulations, we show that our stable weight and robust methods are able to save a significant amount of energy. For future work, we will focus on how to find a good initial weight setting.

Figure 1 :

 1 Figure 1: Example of EAR and Γ-Robust network

  and link weight for M 2 2d. Routing and link weight for M 3 2b. Routing and link weight for M 1

Figure 2 :

 2 Figure 2: Example of OSPF/ECMP for EAR

Figure 3 :

 3 Figure3: Traffic demands in Abilene network[START_REF] Koster | Robust Network Design: Formulation, Valid Inequalities, and Computations[END_REF]

  l 0,4 = l 7,3 = 1, l 4,5,6,7 = 3, (7 links) l 8,4 = l 7,11 = 1 2 {(0, 3)} Fig. 1b l 0,1,2,3 = 4, l 4,5,6,7 = 2, (8 links) l 8,4 = l 7,11 = 1 3 {(4, 7)} Fig. 1b or 1c l 0,1,2,3 = 1, l 4,5,6,7 = 4, (8 links) l 8,4 = l 7,11 = 1 (Fig. 1b) 4 {(8, 11)} Fig. 1a l 0,4 = l 7,3 = 1, l 4,5,6,7 = 4, (7 links) l 8,4 = l 7,11 = 2 5 {(0, 3), (4, 7)} Fig. 1b l 0,1,2,3 = 4, l 4,5,6,7 = 4, (8 links) l 8,4 = l 7,11 = 1 6 {(0, 3), (8, 11)} Fig. 1b l 0,1,2,3 = 4, l 4,5,6,7 = 3, (8 links) l 8,4 = l 7,11 = 2 7 {(4, 7), (8, 11)} Fig. 1c l 0,1,2,3 = 4, l 4,0 = l 3,7 = 3, (8 links) l 8,9,10,11 = 2

NO

  Mark the link (u, v) as already checked linkYESUpdate input: G = G' and W = W'Sleeping stepFeasible routing check

Figure 5 :

 5 Figure 5: Daily traffic

Figure 6 :

 6 Figure 6: Changes in freely changed weight vs. stable weight methods

Figure 7 :

 7 Figure 7: Energy saving in multi-period traffic matrices

Figure 8 :

 8 Figure 8: Robust weight vs. stable weight

  -MLU (%) Gamma = 2% -MLU (%) Gamma = 100% -MLU (%) (c) Germany network

Figure 10 :

 10 Figure 10: Maximum link utilization (MLU) of robust solution in daily traffic

Table 1 :

 1 Traffic matrices for OSPF/ECMP

	Traffic matrix	Traffic demand (0, 6) (0, 7) (0, 8)
	M 1	30	30	10
	M 2	20	20	10
	M 3	20	10	10

Table 2 :

 2 Notations w max the maximum value of a link weight.

	M a large enough constant. It can be set M = 2w max .
	D a set of all traffic demands to be routed.
	D t a set containing all destination nodes. D st ∈ D demand of the traffic flow from s to t.
	C uv capacity of a link (u, v).
	µ ∈ (0, 1] maximum link utilization that can be tolerated. It is normally
		set to a small value, e.g. µ = 0.5.
	N (u) the set of neighbors of u in the network graph G.
	k t uv	binary variable to determine if the link (u, v) belongs to one of the shortest paths from node u to node t.
	z st u	variable to represent fraction of the flow (s, t) to be routed on outgoing node u using ECMP.
	r t

u cost of the shortest path from u to t. x uv binary variable to indicate if the link (u, v) is active or not. f st uv a flow (s, t) that is routed on the link (u, v).

Table 3 :

 3 Traffic demand variation

	Demand (s, t) Nominal value Peak value
	(0, 3)	1	4
	(4, 7)	1	3
	(8, 11)	1	2

Table 4 :

 4 Example of robustness: Γ = 2

	Case	Q	Best solution	Link load l uv (Gbps)
	1	{}	Fig. 1a

  As proposed by Bertsimas and Sim, we employ LP duality with the dual variables π e and ρ st e , which correspond to the constraints

	D st f st e y st e		(15)
	t)∈D
	s.t.
	y st e ≤ Γ	[π e ]	(16)
	(s,t)∈D
	y st e ∈ {0, 1}	[ρ st e ]	(17)
	where the primal binary variables y st e denote whether or not f st e is part of the subset Q ⊆ D. (s,t)∈D y st e ≤ Γ and y st e ≤ 1, respectively. The LP duality for β(g, Γ) is as follows:
	β(g, Γ) := min Γπ e +	ρ st e		(18)
	(s,t)∈D
	s.t.

π e + ρ st e ≥ D st f st e ∀(s, t) ∈ D (

19)

Table 5 :

 5 Abilene network -optimal solutions

			Execution time (s)
		D1 D2 D3	D4	D5
	Stable weight MILP	≤ 5 ≤ 5 ≤ 5	≤ 5	≤ 5
	Robust MILP		90
	Freely changed weight MILP 95	874 100 12900 20700

Table 6 :

 6 Geant network -heuristic solutions

		Execution time (s)
		D1 D2	D3	D4	D5
	Stable weight	139 140 160	182	256
	Robust stable weight		283
	Freely changed weight 62 157 1596 2115 3600

Table 7 :

 7 Germany network -heuristic solutions

			Execution time (s)
		D1	D2	D3	D4	D5
	Stable weight	468 1586 1787 2108 3108
	Robust stable weight			3090
	Freely changed weight 1739 3600 3600 3600 3600

Acknowledgements

This work was partly funded by the French Government (National Research Agency, ANR) through the Investments for the Future Program reference ANR-11-LABX-0031-01, ANR project Stint under reference ANR-13-BS02-0007, the

highest traffic matrix (D5). Since we guarantee capacity constraints, no link is overloaded. Our goal is not load balancing, thus we do not have an explicit comparison between the freely changed weight and the stable weight methods. However, from Fig. 9a, the stable weight method is slightly better, e.g. 60% of links have link utilization less than 80%, meanwhile it is only 40% of links for the freely changed weight method. This can be explained as the stable weight method uses an initial load-balancing link weight which is the one that minimizes the maximum link load.

Robust approach

For each value of Γ, we find a link weight setting that satisfies the capacity constraint if at most Γ demands are at peaks at the same time. However, we would like to test what will happen if we use a single robust network configuration while traffic is variated in daily time. Fig. 10 shows the maximum link utilization over all active links in the network for different values of Γ. Obviously, if we use Γ = 100%, we can find a single network configuration that is feasible (no overloaded link) for all-day traffic variation. However, the price of this solution is too expensive: e.g. only 6% of energy can be saved for the Abilene network (like the case D5). However we observe that, even with Γ = 1%, the maximum link utilization of the three networks is less than 200%. It means that if we carefully set the value of µ in the capacity constraints (e.g. µ = 50%), then the robust solution with Γ = 1% can be feasible for all-day traffic variation.


Frédéric Giroire

Joanna Moulierac

Khoa Truong
email: truongkhoa.phan@inria.fr

Phan

Frédéric Roudaut

Minimization of Network Power Consumption with Redundancy Elimination

Keywords: Redundancy Elimination, Energy-aware Routing, Algorithm, Green Networking

Recently, energy-aware routing (EAR) has gained an increasing popularity in the networking research community. The idea is that traffic demands are redirected over a subset of the network links, allowing other links to sleep to save energy. In this paper, we propose GreenRE -a new EAR model with the support of data redundancy elimination (RE). This technique, enabled within routers, can virtually increase the capacity of network links. Based on real experiments on Orange Labs platform, we show that performing RE increases the energy consumption for routers. Therefore, it is important to determine which routers should enable RE and which links to put into sleep mode so that the power consumption of the network is minimized. We model the problem as Integer Linear Program and propose greedy heuristic algorithms for large networks. Simulations on several network topologies show that the GreenRE model can gain further 37% of energy savings compared to the classical EAR model.

Introduction

Recent studies exhibit that traffic load on routers has a small influence on their energy consumption [START_REF] Chabarek | Power Awareness in Network Design and Routing[END_REF][START_REF] Mahadevan | A Power Benchmarking Framework for Network Devices[END_REF]. Instead, the dominating factor is the number of active elements on routers such as ports, line cards, base chassis, etc. The basic idea of energy-aware routing (EAR) is that, during low traffic periods (e.g. at night), traffic demands can be routed over a subset of the network links while preserving connectivity and QoS. In this way, the links excluded by the routing paths can be put into sleep mode (or more precisely, two network interfaces on the two routers will sleep) to save energy.

In general, link capacity is the main constraint of the EAR problem. In this work, we use an assumption that routers can eliminate redundant data traffic and hence, virtually increase capacity of network links. As a result, more traffic flows can be redirected and more links can sleep to save energy. Although routers nowadays cannot remove repeated content from network transfers, there exists WAN Optimization Controller (WOC) -a commercial device used in enterprises or small ISPs to eliminate traffic redundancy [START_REF]BlueCoat: WAN Optimization[END_REF][START_REF] Grevers | Application Acceleration and WAN Optimization Fundamentals[END_REF]5]. In order to identify the power consumption directly induced by RE, we perform real experiments on the WOC. Because the main idea of routers performing RE is similar to the WOC functionality (see Section 2.2), we believe that when a router eliminates traffic redundancy, it also consumes additional energy like the WOC. In summary, the contributions of this work are the following:

• We do real experiments to exhibit the power consumption of a WOC.

• We define and formulate GreenRE -a new EAR model as Mixed Integer

Linear Program (MILP).

• We propose and evaluate a greedy heuristic algorithm that can be used for large-scale networks.

• By simulation, we present energy savings on real network topologies.

The rest of this paper is structured as follows. We summarize related works in Section 2. In Section 3, we model GreenRE as ILP, then propose a greedy heuristic algorithm. Simulation results are presented in Section 4. We present a discussion on EAR in practice in Section 5. Finally, we conclude the work in Section 6.

Related Works

Classical Energy-aware Routing (EAR)

Today's networks are usually built with several redundant links and aggressive over-provision in bandwidth. While these redundancies increase network reliability, they also greatly reduce the network's energy efficiency. Indeed, all network devices are powered on but highly under-utilized most of the time. Since power consumption of a router is independent from its traffic load [START_REF] Chabarek | Power Awareness in Network Design and Routing[END_REF][START_REF] Mahadevan | A Power Benchmarking Framework for Network Devices[END_REF], people proposed to put unused network elements into sleep mode to save energy. This research idea is called energy-aware routing (EAR) and is illustrated by the example in Figure 1. Although several works have shown a great opportunity for saving energy using EAR [START_REF] Bolla | Energy Efficiency in the Future Internet: A Survey of Existing Approaches and Trends in Energy-Aware Fixed Network Infrastructures[END_REF][START_REF] Bianzino | A Survey of Green Networking Research[END_REF], there are a number of issues that arise in practical implementation. We give a discussion on these issues in Section 5. As an example of EAR, we refer to Fig. 1. There are two traffic demands 0 → 5 and 10 → 15 with volumes D 0,5 = 20 Gb and D 10,15 = 10 Gb. The shortest path routing, as shown in Fig. 1a, uses 10 active links whereas the remaining 7 links can be put into sleep mode. However, taking energy consumption into account, in Fig. 1b, EAR solution allows 8 links to sleep, thus energy consumption is further decreased. The problem of minimizing the number of active links under QoS constraints can be precisely formulated using Mixed Integer Linear Programming (MILP). However, this problem is known to be NP-Hard [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF], and currently exact solutions can only be found for small networks. Therefore, many heuristic algorithms have been proposed to find admissible solutions for large networks [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF][START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF].

Reduction of Traffic Load

Internet traffic exhibits a large amount of redundancy when different users access the same or similar contents. Therefore, several works [START_REF] Anand | Packet Caches on Routers: the Implications of Universal Redundant Traffic Elimination[END_REF][START_REF] Anand | SmartRE: an Architecture for Coordinated Network-wide Redundancy Elimination[END_REF][START_REF] Song | Redundancy-aware Routing with Limited Resources[END_REF] have explored how to eliminate traffic redundancy on the network. Spring et al. [START_REF] Spring | A Protocol-Independent Technique for Eliminating Redundant Network Traffic[END_REF] developed the first system to remove redundant bytes from any traffic flows. Following this approach, several commercial vendors have introduced WAN Optimization Controller (WOC) -a device that can remove duplicate content from network transfers [START_REF]BlueCoat: WAN Optimization[END_REF][START_REF] Grevers | Application Acceleration and WAN Optimization Fundamentals[END_REF]5]. WOCs are installed at individual sites of small ISPs or enterprises to offer end-to-end RE between pairs of sites. As shown in Fig. 2, the patterns of previously sent data are stored in database of the WOCs at both sending and receiving sides. The technique used to synchronize the databases at peering WOCs can be found in [START_REF] Grevers | Application Acceleration and WAN Optimization Fundamentals[END_REF]. Whenever the WOC at the sending side notices the same data pattern coming from the sending hosts, it sends a small signature instead of the original data (encoding process). The receiving WOC then recovers the original data by looking up the signature in its database (decoding process). Because signatures are only a few bytes in size, sending signatures instead of actual data gives significant bandwidth savings.

WAN `WOC

Synchronized compression database

Recently, the success of WOC deployment has motivated researchers to explore the benefits of deploying RE in routers across the entire Internet [START_REF] Anand | SmartRE: an Architecture for Coordinated Network-wide Redundancy Elimination[END_REF][START_REF] Song | Redundancy-aware Routing with Limited Resources[END_REF]. The core techniques used here are similar to those used by the WOC: each router on the network has a local cache to store previously sent data used to encode and decode data packets later on. Obviously, this technique requires heavy computation and large memory for the local cache. However, Anand et al. have shown that on a desktop 2.4 GHz CPU with 1 GB RAM, the prototype can work at 2.2 Gbps for encoding and at 10 Gbps for decoding packets [START_REF] Anand | SmartRE: an Architecture for Coordinated Network-wide Redundancy Elimination[END_REF]. Moreover, they believe that higher throughput can be attained if the prototype is implemented in hardware. Several real traffic traces have been collected to show that up to 50% of the traffic load can be reduced with RE support [START_REF] Anand | SmartRE: an Architecture for Coordinated Network-wide Redundancy Elimination[END_REF][START_REF] Song | Redundancy-aware Routing with Limited Resources[END_REF].

In next section, we propose GreenRE -the first model of energy-aware routing with RE support. We show that RE, which was initially designed for bandwidth savings, is also potential to reduce network power consumption.

Energy-aware Routing with RE

In the GreenRE model, RE is used to virtually increase capacity of the network links. A drawback is that, as shown in [START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF], when a router performs RE, it consumes more energy than usual. This introduces a tradeoff between enabling RE on routers and putting links into sleep mode. We show that it is a non-trivial task to find which routers should perform RE and which links should sleep to minimize energy consumption for a backbone network. As an example, we refer to Fig. 3a with two traffic demands D 0,5 = 20 Gb and D 10,15 = 10 Gb. Let a RE-router cost 30 Watts (see Section 4.1) and a link consume 200 Watts [START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF]. Assume that 50% of the traffic is redundant and RE service is enabled at the router 6 and router 9, thus traffic flows 0 → 5 and 10 → 15 passing links [START_REF] Bolla | Energy Efficiency in the Future Internet: A Survey of Existing Approaches and Trends in Energy-Aware Fixed Network Infrastructures[END_REF][START_REF] Bianzino | A Survey of Green Networking Research[END_REF][START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF][START_REF] Chiaraviglio | Minimizing ISP Network Energy Cost: Formulation and Solutions[END_REF] are reduced to (10 + ϵ) Gb and (5 + ϵ ′ ) Gb where ϵ, ϵ ′ denotes the total size of the signatures used for each flow. In reality, each signature is only a few bytes in size [START_REF] Grevers | Application Acceleration and WAN Optimization Fundamentals[END_REF], therefore ϵ, ϵ ′ are small and the routing in Fig. 3a is feasible without any congestion. As a result, the GreenRE solution allows to sleep 10 links and enables 2 RE-routers which saves (10 × 200 -2 × 30) = 1940 Watts, compared to 8 × 200 = 1600 Watts of the EAR solution (Fig. 1b). It is noted that, in some extreme cases, GreenRE even helps to find feasible routing solution meanwhile it is impossible for the classical EAR. For example, if we add a third demand from router 0 to 1 with volume 20 Gb, then Fig. 3b is a feasible solution. However, without RE-routers, no feasible solution is found because there is not enough capacity to route all the three demands.

Integer Linear Program (ILP) Formulation

The GreenRE model can be formulated as Integer Linear Program. We present a network topology as an undirected graph G = (V, E). The set of nodes V describe routers and the edges (u, v) ∈ E describe connections between those routers. We note N (u) as a set of neighbor nodes of u in the graph G. For each link (u, v) ∈ E , we use a binary variable x uv to determine if the link is used or not. If link (u, v) is active, two network interfaces at router u and router v are enabled, this consumes P E uv Watts. We define γ st as the percentage of unique (non redundant) traffic. For example, with 40% of redundancy (γ st = 0.6), instead of sending a traffic demand 10 Gb, we are sending only (6 + ϵ) Gb after removing redundancy. For simplicity, since ϵ is small, we can ignore it in the formulation and a traffic flow from which redundancy has been removed is called a compressed flow. It is noted that, the notion γ st only captures the intra-flow redundancy (and not the inter-flow redundancy as presented in [START_REF] Anand | Packet Caches on Routers: the Implications of Universal Redundant Traffic Elimination[END_REF]). We note f st uv (resp. g st uv ) be the fraction of normal flow (resp. compressed flow) on edge (u, v) corresponding to the demand D st flowing from u to v. We define a binary variable w u which is equal to 1 if router u performs RE (called RE-router and it consumes additional P N u Watts). We consider three different scenarios of the problem:

(1) all routers on the network can perform RE, we can enable or disable RE service on routers; (2) only a predefined set of routers on the network have RE capability, other routers are normal routers and (3) there is a limited number of RE-routers, the network operators should find where to place them to increase energy efficiency for the network. We formulate the three scenarios of the GreenRE problem as follows:

3.1.1. Scenario 1: All Routers are RE-capable Routers min ∑ uv∈E P E uv x uv + ∑ u∈V P N u w u (1) s.t. ∑ v∈N (u) ( f st vu + g st vu -f st uv -g st uv ) =      -1 if u = s, 1 if u = t, 0 else ∀u ∈ V, (s, t) ∈ D (2) ∑ v∈N (u) (g st uv -g st vu ) ≤ w u ∀u ∈ V, (s, t) ∈ D (3) ∑ v∈N (u) (g st vu -g st uv ) ≤ w u ∀u ∈ V, (s, t) ∈ D (4) ∑ (s,t)∈D D st ( f st uv + f st vu + γ st (g st uv + g st vu ) ) ≤ µC uv x uv ∀uv ∈ E (5) f st uv , g st uv ∈ [0, 1], w u , x uv ∈ {0, 1} (6)
The objective function ( 1) is to minimize the power consumption of the network represented by the number of active links and RE-routers. Constraints (2) establish flow conservation constraints. Constraints (3)-( 4) are used to determine whether RE service is enabled at router u or not. If it is not (w u = 0), the router u only forwards flows without compression or decompression, then the amount of compressed flows incoming and outgoing the router u is unchanged. It is noted that if a flow is compressed, it needs to be decompressed somewhere on the way to its destination. This requirement is implicitly embedded in the constraints (4). For instance, assume that a destination node t is not a RE-router (w t = 0). When a compressed flow g st reaches its destination, because t is the last node on its path, the flow can not be decompressed. Consider the constraints (4), we have u = t, then ∑ v∈N (u) g st vt > 0 (the compressed flow enters node t) and ∑ v∈N (u) g st tv = 0 (t is the destination node). Therefore, the constraint ( 4) is violated and the flow should be decompressed before or at least at the destination node (w t = 1). We consider an undirected link capacity model [START_REF] Raack | On Cut-based Inequalities for Capacitated Network Design Polyhedra[END_REF] in which the capacity of a link is shared between the traffic in both directions. We use constraints (5), where µ denotes the link utilization in percentage, to limit the available capacity of a link.

Scenario 2: a Predefined Set of Routers are RE-capable Routers

We define the following constraints:

w u = 0 ∀u / ∈ V ′ , V ′ ⊂ V, (7)
where V ′ is a predefined subset of routers that have RE-capability, we force all other routers to be normal routers (w u = 0). By adding [START_REF] Bianzino | A Survey of Green Networking Research[END_REF] to the first scenario ( 1)-( 6), we have the second scenario of the GreenRE problem.

Scenario 3: a Limited Numbers of RE-routers

We add the following constraints to the first scenario ( 1)-( 6):

∑ u∈V w u ≤ M, ( 8
)
where M is a parameter denoting the maximum number of RE-routers that can be placed on the network. By using constraints (8), we allow any router to perform RE. However, the total number of RE-routers on the network should be less than M .

Heuristic Algorithm

Energy-aware routing problem is known to be NP-Hard [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF][START_REF] Koster | Extended Cutset Inequalities for the Network Power Consumption Problem[END_REF]. We have presented a greedy heuristic called H-GreenRE for large network topologies in our previous work [START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF]. Since the power consumption of a link is much more compared to an enabled RE-router, the heuristic should give priority to minimize the number of active links. The basic idea of H-GreenRE is that we first assume all routers are RE-enabled routers. Then, the traffic flows can be compressed everywhere on the network. Based on this, we find feasible routing solutions (without overloaded links) and then turn off the link with minimum traffic load. This procedure is repeated until there is no link that can be turned off. After that, we fix the routing and based on some rules defined in [START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF], we disable unnecessary RE service on routers to save energy. The main problem of H-GreenRE is that, to find a feasible routing, we pick up demand one by one and try to route it using shortest path routing. Thus, in case the feasible routing is not a shortest path, H-GreenRE can not find it. In this paper, we introduce a new heuristic algorithm based on the ILP formulation (let's call it H ILP -GreenRE). Using the ILP formulation, H ILP -GreenRE tries all the possibilities to find a feasible routing if any, thus it is more efficient than the H-GreenRE (see Section 4.2.1). In the GreenRE problem, to find optimal solution we must consider power consumption of both active links and RE-routers at the same time. For the heuristic H ILP -GreenRE, we divide the original problem into two sub-problems: (1) minimize the number of active links and (2) minimize the number of RE-routers. Similar to the H-GreenRE, the H ILP -GreenRE has two steps: the first step is to find as few active links as possible (sub-problem 1), and then we minimize the number of RE-routers in the second step (sub-problem 2).

Step 1 (sub-problem 1) is a constraint satisfaction problem returning a feasible routing solution. We use the same framework for the three scenarios of the GreenRE problem. For details, to find feasible solutions (P currentline 2 and P new -line 8), we set the objective function to min 0 and use the constraints (2)-( 6) for scenario 1. Similarly, scenario 2 (resp. scenario 3) uses the constraints (2)-(7) (resp. constraints (2)-( 6), [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF]) and the objective is min 0. In each round of the algorithm, we try to remove a link with low Algorithm 1: Inputs: A graph G = (V, E) with link capacity C e , a set of traffic demands and non-redundant rates. load (line 6 -7) and then find a new feasible routing (P new -line 8) using less active links. The idea behind this algorithm is that we try to put into sleep mode the low loaded links and to accommodate their traffic on other links in order to reduce the total number of active links. Observe that unused links (i.e. links that do not carry traffic) are not considered in the set S since the removal of such a link will result in a routing P new equal to P current. To further reduce the computation time, we can consider additional heuristic. For instance, while removing a low loaded link (line 6 -7), we can also set the variable x uv associated to a heavily loaded link to 1 so that it can speed up the resolution for finding P new (line 8). Indeed, such high loaded link will certainly be part of the final solution. Since we relax the objective function and the goal is just to justify whether a set of constraints is feasible or not, it is quite fast to find P current and P new . In our simulations, the execution time of Algorithm 1 (including the two steps) is less than one hour for the tested network topologies (see Section 4).

After

Step 1, if a feasible routing is found, and so a set of active links, we proceed to Step 2 (sub-problem 2) to minimize the number of enabled RErouters. More precisely, we use again the ILP formulation (of the scenario we want to solve) in which the objective function is set to min ∑ u∈V w u . Furthermore, we set all binary variables associated to active links to 1 and the others to 0 (this speed-up the resolution of the ILP).

Experiment and Simulation Results

Energy Consumption with WOC

Several results of bandwidth savings using WOC can be found in [START_REF] Grevers | Application Acceleration and WAN Optimization Fundamentals[END_REF]. We have also performed experiments on the network platform of the project Network Boost at Orange Labs (the full figure of the test-bed can be found in [17]). We installed two WOCs, each at the access link of the two sites (let's call them site A and site B). These two sites are connected via a backbone composed of 4 routers. We setup FTP connections for uploading files from site A to site B. As shown in Fig. 4a, power consumption of the WOC is increased (from 26 Watts to 34 Watts) with the number of concurrent FTP sessions. For the next experiment, we keep only one FTP session and let the WOC perform RE for 10 hours in which the sizes of uploaded files are increased. The results show that the WOC consumes around 30 Watts on average (Fig. 4b). Therefore, for sake of simplicity, we use an average value of power consumption (30 Watts) to represent additional cost for the router to perform RE.

Simulation Results with GreenRE

We solve the GreenRE model with IBM CPLEX 12.4 solver [START_REF] Ilog | [END_REF]. All computations were carried out on a 2.7 Ghz Intel Core i7 with 8 GB RAM. We studied ten classical real network topologies extracted from SNDLib [START_REF] Orlowski | SNDlib 1.0 -survivable network design library[END_REF]. Their sizes span from 15 to 54 nodes and from 22 to 89 edges, as summarized in Table 1. According to the results of the works mentioned in Section 2.2, we use redundancy rates equal to 50% (high redundancy, γ = 50%), 25% (medium redundancy, γ = 75%) and 10% (low redundancy, γ = 90%). For worst-case scenario and for comparison with previous work [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF][START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF], all links are set up with the same capacity C and the demands are all-to-all (one router has to send traffic to all remaining routers on the network) with the same traffic volume D for each demand. [START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF] We propose in this paper a new heuristic based on the ILP formulation called H ILP -GreenRE. To compare with the heuristic H-GreenRE proposed in the previous work [START_REF] Giroire | Minimization of Network Power Consumption with Redundancy Elimination[END_REF], two simulation scenarios (with γ = 50%) have been done for the ten network topologies (we sort the networks in increasing order of the number of nodes).

Comparison with the Heuristic H-GreenRE in

First, we find the minimum values of capacity/demand ratio λ minRE that allow for each heuristic algorithm to find a feasible routing solution with the support of RE-routers. Note that, λ represents the level of traffic load on the network. Small value of λ means that the traffic load on the network is high (e.g. traffic at peak hours), thus it is hard to find feasible solution because of the lack of capacity (refer to the example in Fig. 3b). Therefore, the heuristic algorithm that can find feasible routing with smaller value of λ minRE is the better one. To compute λ minRE , we first fix the demand value, e.g. D = 1. Then, starting with a large capacity value, e.g. C = 1000, we decrease the value of C and test the heuristic until we get the minimum value of C that is still possible to find a feasible solution. Let's call this value is C min , then we have λ minRE = C min . Fig. 5 shows that H ILP -GreenRE can find feasible solutions with smaller values of λ minRE than H-GreenRE. For example, for the Atlanta network, H ILP -GreenRE finds a solution with λ minRE = 19 while H-GreenRE is with λ minRE = 22: that is, for example, for a link capacity of 10 Gbit/sec, the first heuristic succeeds in routing an all-to-all demand of 10/19 =0.53 Gbit/sec for each demand and the second heuristic, a demand of only 10/22 = 0.45 Gbit/sec. In summary, H ILP -GreenRE finds feasible solutions close to the lower bounds of λ min found in [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF]. The best improvement is on Zib54 network: λ minRE = 147 (for H ILP -GreenRE) in comparison with λ minRE = 168 (for H-GreenRE). We show next the energy savings for the ten networks. We use the value of λ minRE that allows for H-GreenRE to find feasible routing solution for each network (the second column in Fig. 5). If a network has dense links, there are more chances to redirect traffic and put links into sleep mode, thus more energy can be saved. As shown in Fig. 6, H ILP -GreenRE again outperforms H-GreenRE for all the networks. Energy efficiency can be increased from 2% (Atlanta network) to 19.8% (Pioro40 network). In this subsection, we present simulation results for Atlanta network. In Fig. 7a, with the same redundancy rate (γ = 50%), we vary capacity/demand ratios and compare between the ILP-EAR without RE-routers (given by [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF]), the ILP with RE-routers (the formulation ( 1) -( 6): ILP-GreenRE) and the heuristic with RE-routers (H ILP -GreenRE). Even for small network like Atlanta, CPLEX also takes some hours to find an optimal solution when the capacity/demand ratios are high (e.g. λ ≥ 48). It is noted that when λ < 48, it is possible to find an optimal solution within one hour. We limit the solving time to one hour for all instances of Atlanta network corresponding to different capacity/demand ratios. In average, the optimality gap is within 10% for all the best solutions. The heuristic is quite fast, it takes less than 10 seconds to find a solution. The x-axis in Fig. 7a represents the capacity/demand ratio λ and the y-axis is energy savings in percentage. As shown in Fig. 7a, without RE-router (ILP-EAR), there is no feasible routing solution and hence, no energy is saved if λ < 38. When λ increases, links have more bandwidth to aggregate traffic, the solutions with and without RE-router converge to the same amount of energy savings. In general, the heuristic with RE-routers works well and approximates to the results of ILP-GreenRE (the max gap is 3.8%).

Energy Savings for Atlanta Network

In Fig. 7b, we evaluate energy savings for Atlanta network with different level of redundancy. It is clear that when traffic redundancy is high, e.g. γ = 50%, more traffic flows are aggregated and thus, more links can be turned off to save energy. Similarly, when γ = 75% and γ = 90% (corresponding to 25% and 10% of traffic redundancy), less energy can be saved. These remarks can be seen in Fig. 7b where the gaps between ILP-GreenRE and ILP-EAR are reducing when γ is increasing. It is noted that ILP-GreenRE should be at least as good as ILP-EAR. It is because the objective of ILP-GreenRE is to minimize energy consumption for the network. In case the redundancy elimination does not help to turn off more links, ILP-GreenRE does not enable RE service on router (even it helps to reduce the traffic load). Therefore, in the worst case scenario (redundancy rate is zero or γ = 100%), ILP-GreenRE has no RE-enabled router and the routing solution is the same as in ILP-EAR. We present in Table 1 energy gain for ten classical network topologies using H ILP -GreenRE and H-EAR -the heuristic without RE-routers found in [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF]. Different from λ minRE in Section 4.2.1, we use λ min be the smallest value of capacity/demand ratio that allows to find a feasible route for all the demands without RE-router (found in [START_REF] Giroire | Minimizing Routing Energy Consumption: from Theoretical to Practical Results[END_REF]). In the simulations, a range of λ = {λ min , 2λ min , 3λ min } is used to represent high (e.g. traffic at peak hours), medium and low traffic load (e.g. traffic at night) on the networks. As shown in Table 1, with RE-routers, it starts to save a large amount of energy (in average 37%) even with λ = λ min . Recall that routing with RE-routers is possible even with λ < λ min meanwhile no feasible solution is found without RE-router. When λ is large enough, it is not necessary to have RE-routers on the network, therefore both the solutions (with and without RE-router) converge to almost the same value of gains in energy savings. In this section, we evaluate energy savings of scenario 2 (a predefined subset of RE-capable routers) and scenario 3 (a limited numbers of REcapable routers). We set link capacity and demand corresponding to λ min in Section 4.2.3. The x-axis of Fig. 8 is the percentage of RE-capable routers on the network. For instance, with scenario 3, we find the routing solution that minimizes energy consumption while there are at most (x × |V |) RE-routers on the network. For scenario 2, we place (x × |V |) RE-capable routers on (1) highest degree nodes or (2) lowest degree nodes in graph G. As shown in Fig. 8, the scenario 3 always outperforms the scenario 2 since it can find best positions to place RE-capable routers. For instance, in Atlanta network with a maximum of 6 RE-routers, the max gap is 4.5% and there are 4 RErouters at the highest degree nodes and the two others are at the medium and the lowest degree nodes. Another important observation we found in the scenario 2 is that, placing RE-routers on high degree nodes gives better results in energy savings. It is because placing RE-capable routers on high degree nodes helps to reduce traffic load and gives more chances to redirect traffic on a few links, allowing other links on these nodes to sleep.

Energy Savings for the Ten Classical Networks

Energy Savings for Scenario 2 and Scenario 3 of the GreenRE Problem

Discussion

While the results in this work show a great improvement on energy efficiency for backbone networks, there are still a number of issues of EAR in practice that we discuss below. Nowadays, network operators do not like to turn-off links and change routing. As a matter of fact,

• the convergence between two routing configurations is usually long and can take up to several seconds for some distributed protocols (e.g. for BGP), leading to perturbations for the network traffic.

• even signaling takes non-negligible time: a simple control message may take tens of milliseconds to traverse the network and reach a given router.

However, in our study, we are in a simplified configuration as we consider:

• Preplanned changes: our approach in this paper is completely off-line as we are studying a single traffic matrix. We are not in a context of rapid changes for the routing. Considering a given network and an estimation of the traffic, we can precompute a set of configurations depending on different time instants for a whole day. The number of configurations depends on several parameters that need to be discussed with the network operator and optimized, e.g., link over-dimensioning, QoS, length of paths, number of desired routing changes per day, etc. For instance, as shown in [START_REF] Chiaraviglio | Sleep Modes Effectiveness in Backbone Networks with Limited Configurations[END_REF], only few configurations (two or three per day) are enough to significantly save energy. Similarly, the authors in [START_REF] Francois | On IGP Link Weight Optimization for joint Energy Efficiency and Load Balancing Improvement[END_REF] suggest to use only two network configurations for a daily time.

During peak hours, all the links in the network are active while EAR (with sleep links) is considered only in off-peak time to save energy.

• Intra-domain network: our work focus on intra-domain network, which is a simpler case as the routing changes do not need to be propagated to other domains by inter-domain routing protocols such as BGP. Moreover, the network operator can manage its own domain without explicit cooperation with other domains and update metrics for the routing protocol, turn on/off links, or set up a centralized entity in order to perform a better optimization with a complete view of the network and the traffic.

• Centralized control (SDN): within a network operator domain, an SDN solution, like Openflow, can be implemented. OpenFlow is a promising method to implement EAR in a network [START_REF] Wang | CARPO: Correlation-Aware Power Optimization in Data Center Networks[END_REF][START_REF] Heller | ElasticTree: Saving Energy in Data Center Networks[END_REF]. Without setting entries manually, a centralized controller can collect traffic matrices, perform routing calculation in advance and then trigger an installation of new routing rules on routers at the precomputed time based on the planification. Openflow will make energy-aware solutions possible by allowing to switch on and off equipments based on traffic measures. Such a system will experience a much lower routing convergence time than existing distributed protocols [START_REF] Reitblatt | Abstractions for network update[END_REF].

Even if our work focus on a simplified version of the whole problem, we discuss below the problems that may arise when passing from a routing configuration to another, or if unexpected events appear.

-Transition between two configurations. We must ensure that the network behaves correctly between two consecutive transitions. In [START_REF] Reitblatt | Abstractions for network update[END_REF], the authors describe a mechanism using Openflow for consistent network updates in which the packets are processed either with the old or the new configuration but never with a mixture of the two. One of the ideas presented in the paper is to pre-install the new routing rules while keeping the old routing in place. When all flows matching a given old rule finish, the new routing configuration takes effect. In [START_REF] Francois | Disruption free topology reconfiguration in ospf networks[END_REF], the authors use OSPF routing protocol and propose incremental updates of links (turning on and off links is also considered) in order to ensure a loop-free transition between two configurations. In [START_REF] Moulierac | Optimizing IGP Link Weights for Energy-efficiency in a Changing World[END_REF], we proposed methods to limit OSPF changes between two consecutive routing configurations to reduce network oscillation during transient time. Moreover, as shown in [START_REF] Peresini | ESPRES: Easy Scheduling and Prioritization for SDN[END_REF], an appropriate scheduling and prioritization in rule update can help to reduce the side effects in transitioning between network configurations.

-Unexpected events. In case of traffic burstiness, the network should react quickly in order to avoid packet losses. Similarly to what is actually done by telecommunication operators, our model integrates over provisioning on links (parameter µ in the linear program). This allows to tolerate some traffic increase without changing the network configuration. If the capacity on links is not sufficient enough, then the SDN controller can send signals to wake up all the links and apply the routing configuration for peak hours.

In this case, the delay will include the time for the controller to contact all the routers, and the routers to change their routing configurations. This will be the worst-case scenario implying the longer delay.

-QoS degradation and routing loops. Another issue of EAR is QoS degradation during transient times such as routing loops. Moreover, during these periods, packets may arrive out of order which causes problems for TCP, degrading the perceived QoS for end-users [START_REF] Leung | An Overview of Packet Reordering in Transmission Control Protocol (TCP): Problems, Solutions, and Challenges[END_REF]. These effects can be limited if two consecutive routing configurations contain a minimal number of changes. Moreover, we believe that these periods will be short (in the order of seconds) and will be acceptable in view of the gain in energy savings.

-Delay for (de)/activating links. The time required for sleeping/activating a link on router is substantial. Indeed, commercial routers available today do not integrate this sleep mode functionality yet. However, there are on-going works on this issue [START_REF]Econet project[END_REF]. For instance, the works in [START_REF] Christensen | IEEE 802.3az: The Road to Energy Efficient Ethernet[END_REF][START_REF] Bolla | A Closed-Form Model for the IEEE 802.3az Network and Power Performance[END_REF] show that it is possible to put a link into sleep mode and wake it up in short time (e.g. less than 5µs for 10GBASE-T links). Thus, we can expect that these advances may come in the future, especially if they offer big energy savings, and will be negligeable. However, this delay is not only for the material to be turnedon but also for the controller to contact all the routers, and the routers to change their routing table.

To sum up, turning-off links in EAR will cause unavoidable overhead, especially in transient time between different routing configurations. However, if the planification of these changes is done with a reasonable number of configurations per day, with few changes between two configurations in order to limit the routing loops and the network oscillations, and with an ordered list of routing changes to be sent to the routers by the SDN controller, we can expect that these drawbacks would be acceptable in view of the energy savings.

Conclusion

To the best of our knowledge, GreenRE is the first work considering redundancy elimination as a complementary help for energy-aware routing problem. We formulate the problem as Mixed Integer Linear Program and propose greedy heuristic algorithms. The simulations on several network topologies show a significant gain in energy savings with GreenRE. For future work, we will consider a more realistic model in which data redundancy rates and traffic demand volumes variate based on real life traffic traces. Moreover, we plan to study the inter-flow redundancy as it could further reduce network traffic.

  Shortest path routing: sleep 7 links (b) EAR: sleep 8 links

Figure 1 :

 1 Figure 1: Example of shortest path routing and EAR.

Figure 2 :

 2 Figure 2: Reduction of end-to-end link load using WOC

  sleep 10 links, enable 2 RE-routers (b) sleep 9 links, enable 2 RE-routers

Figure 3 :

 3 Figure 3: GreenRE with 50% of traffic redundancy

12 E := E\{e}; 13 end 14 else 15 R 16 end

 1213141516 := R ∪ {e}; 17 until (S = ∅) or (R = S); 18 Return the final feasible routing solution (if any); 19 Step 2 -Find feasible solution minimizing the number of RE-routers on the set of active links E found in Step 1.

Figure 4 :

 4 Figure 4: Power consumption of the WOC

Figure 5 :

 5 Figure 5: Comparison of λ minRE between H ILP -GreenRE and H-GreenRE

Figure 6 :

 6 Figure 6: Comparison of energy savings between H ILP -GreenRE and H-GreenRE

  Heuristic vs. ILP-GreenRE vs. ILP-EAR with different RE rates

Figure 7 :

 7 Figure 7: Simulation results for Atlanta network

  percentage of RE-routers (%) Scenario 3: limited RE-routers Scenario 2: highest degree nodes Scenario 2: lowest degree nodes

Figure 8 :

 8 Figure 8: Energy savings with limited RE-routers vs. a subset of capable RE-routers

1

  Step 1 -Minimize number of active links by removing low loaded links: 2 Find a feasible routing solution using the ILP called P current; 3 Let S be an ordered list initialized with the links of G sorted by increasing traffic load in P current; 4 Let R := ∅ be the set of links that cannot be removed;

	5 repeat
	6	e := S.lowest loaded link() such that e / ∈ R;

7 S := S\{e}; 8 if a feasible routing P new on E\{e} is found then 9 if P new has less active links than P current then 10 P current := P new ; 11 S := list of links sorted by increasing traffic load in P new ;

Table 1 :

 1 min 2λ min 3λ min λ min 2λ min 3λ min Gain of energy consumption (in %)

	Traffic volume (capacity/demand ratio λ)

Acknowledgment

This work has been done in collaboration with Network Boost Project (Orange Labs) and partly funded by the ANR DIMAGREEN. The authors would like to thank Didier Leroy (Orange Labs), Yaning Liu (JCP-Consult R&D) and David Coudert (Project COATI) for their advices and support.