B Addis

A Capone
email: capone@elet.polimi.it

G Carello

L G Gianoli
email: gianoli@elet.polimi.it

B Sansò

On the Energy Cost of Robustness and Resiliency in IP Networks

Keywords: Energy-Aware, Traffic Engineering, Network resiliency, Robust Optimization, Shared protection, Dedicated protection

Despite the growing concern for the energy consumption of the Internet, green strategies for network and traffic management cannot undermine the quality and the functional level normally expected from carrier networks. In particular, two very important issues that may be affected by green networking techniques are resilience to node and link failures, and robustness to traffic variations.

In this paper, we study how strategies aiming at achieving different levels of resiliency and robustness impact the efficiency of energy-aware network management approaches in saving energy. We propose novel optimization models to minimize the energy consumption of IP networks that explicitly guarantee network survivability to failures and robustness to traffic variations. Network consumption is reduced by putting in sleep mode idle line cards and nodes according to daily traffic variations that are modeled by dividing a single day into multiple time intervals. To guarantee network survivability we consider two different schemes, dedicated and shared protection, which assign a backup path to each traffic demand and some spare capacity on the links along the path. Robustness to traffic variations is provided through an approach that allows to tune the capacity margin on active links in order to accommodate load variations of different magnitude. Furthermore, we impose some inter-period constraints necessary to guarantee network stability and preserve device lifetime. Both exact and heuristic methods are proposed.

Experimentations carried out on realistic networks operated with flow-based routing protocols (like MPLS) allow us to quantitatively analyze the trade-off between energy cost and level of protection and robustness. Results show that with optimal strategies significant savings, up to 30%, can be achieved even when both survivability and robustness are fully guaranteed.

Introduction

Both network operators and device manufacturers agree that the energy consumption of communications networks cannot be neglected anymore [5]. According to recent estimates [START_REF] Lambert | Worldwide electricity consumption of communication networks[END_REF], the worldwide electricity consumption of telecom operators has grown from 150 Twh/y in 2007 to 260 TWh/y in 2012, which accounts for almost 3% of the total worldwide consumption.

This growing consumption has stimulated the development of new strategies to increase the energy efficiency of communications networks, with particular focus on IP networks [START_REF] Mellah | Review of facts, data and proposals for a greener Internet[END_REF][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] Vetter | Research roadmap for green wireline access[END_REF]. In this context, remarkable improvements can be obtained with energy-aware strategies for network management and traffic engineering that dynamically optimize the network configuration by putting in sleep mode some of the network components (line cards and nodes) and using the remaining active part to serve the actual traffic [START_REF] Amaldi | Energy-aware ip traffic engineering with shortest path routing[END_REF][START_REF] Chabarek | Power awareness in network design and routing[END_REF]11,[START_REF] Bianzino | A survey of green networking research[END_REF][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] Zeadally | Energy-efficient networking: past, present, and future[END_REF].

Basically, the aim of energy-aware management is to adjust both the network topology and the available capacity to varying traffic levels in order to keep active only the resources that are essential for the actual load. It is basically a dynamic redesign of the network that takes as input the predicted or measured traffic pattern. Management approaches differ depending on the strategy to select the sleeping/active parts, on how optimizing the network routing through the active network, and on how closely traffic variations can be followed by network reconfiguration.

It is quite evident that the best energy performance can be obtained tailoring perfectly the network capacity to the traffic level. But on the other side there are several important functions that depend on the spare capacity available in the network in case actual working conditions are dif-ferent from expected. Protection techniques are widely used to guarantee the network capability of being resilient to failures of links (or device interface serving a link) and nodes. In case of failure occurrence, the affected traffic is rerouted on the surviving part of the network. To verify the possibility of accommodating this traffic on alternative paths to destination it is obviously necessary to have some spare capacity left there to cope with these anomalous situations. Also traffic can be different from what expected because of the uncertainty intrinsic in traffic estimations or possible rapid deviations that cannot be followed by monitoring and measurement techniques. Networks should be designed to be robust to these variations, and also in this case the price to pay is some spare capacity in the network to be used for compensating traffic fluctuations around the nominal value.

For these reasons, there is clearly a trade off between energy consumption and the level of resilience and robustness of the network. However, how protection techniques and robustness strategies are integrated in the energy-aware network management methodologies is fundamental to determine their energy cost. Moreover, if technologies are available for rapidly reactivating sleeping elements when needed, more energy-efficient approaches can be defined by integrating procedures to recover from failures within the network energy management framework.

The fundamental question that we tackle in this paper is whether it is possible to design a network with embedded reliability, survivability and robustness and still aiming at energy reduction. We also want to investigate what is the energy cost of protection and robustness considering different available techniques. To this aim, we introduce a novel framework for survivable and robust energy-aware network management that builds on our recent work on multi-period energy-aware network management in IP networks [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF] 1 . The central idea is to introduce dedicated and shared protection into the energy-aware IP network management models and add as well the notion of network robustness to traffic variations [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF]. This paper is organized as follows. In Section 2 we review state-of-the-art literature on energy-aware network management and point out the novelties of our work. In Section 3 we discuss the most relevant aspects of the proposed energy-aware framework, while in Sections 4, 5 and 6 we present some MILP formulations to take into account both survivability and robustness issues. The resolution methods and computational results are extensively discussed in Section 7 and 8, respectively. Finally, some concluding remarks are reported in Section 9.

Related work

The issues concerning the optimization of Internet energy consumption were first discussed in the seminal work 1 Preliminary results have been presented in [START_REF] Addis | Multi-period traffic engineering of resilient networks for energy efficiency[END_REF][START_REF] Addis | Energy aware management of resilient networks with shared protection[END_REF][START_REF] Addis | A robust optimization approach for energy-aware routing in MPLS networks[END_REF].

by Gupta and Singh [START_REF] Gupta | Greening of the internet[END_REF]. Since then, in the last decade, several studies have been conducted to develop efficient strategies to make the Internet greener [START_REF] Bianzino | A survey of green networking research[END_REF][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] Zeadally | Energy-efficient networking: past, present, and future[END_REF].

As pointed out in [START_REF] Mellah | Review of facts, data and proposals for a greener Internet[END_REF], green networking proposals can be classified into: (i) new technologies and architectures for energy-efficient networking devices, (ii) virtualizationbased strategies, (iii) methodologies for energy-aware network management and design. The modelling framework to minimize the daily energy consumption of IP networks proposed in this paper belongs to the last class.

Preliminary studies that evaluate the applicability and effectiveness of energy-aware network management have been presented in [START_REF] Bolla | Cutting the energy bills of internet service providers and telecoms through power management: An impact analysis[END_REF][START_REF] Baldi | Time for a "greener" internet[END_REF][START_REF] Restrepo | Energy profile aware routing[END_REF][START_REF] Bianzino | Energy-aware routing: A reality check[END_REF][START_REF] Bolla | The potential impact of green technologies in next-generation wireline networks: Is there room for energy saving optimization?[END_REF][START_REF] Chiaraviglio | Modeling sleep modes gains with random graphs[END_REF][START_REF] Chiaraviglio | On the effectiveness of sleep modes in backbone networks with limited configurations[END_REF]. It is worth pointing out that energy-aware network management based on device sleeping represents a promising strategy to reduce network consumption [START_REF] Chiaraviglio | Modeling sleep modes gains with random graphs[END_REF].

Several studies for energy-aware network management without additional requirements such as survivability or robustness have recently been presented. To the best of our knowledge, multi-period optimization with interperiod constraints has been considered only in our two previous articles, [START_REF] Addis | Energy-aware multiperiod traffic engineering with flow-based routing[END_REF][START_REF] Addis | A robust optimization approach for energy-aware routing in MPLS networks[END_REF], where both a MILP exact formulation, and a GRASP heuristic to put to sleep network line cards and chassis were proposed. The other proposals can be naturally categorized according to the routing scheme considered.

The per-flow routing taken into account in this paper was adopted in [START_REF] Chiaraviglio | Minimizing ISP network energy cost: Formulation and solutions[END_REF][START_REF] Vasić | Energy-aware traffic engineering[END_REF][START_REF] Avallone | Energy efficient online routing of flows with additive constraints[END_REF]. Different off-line greedy heuristics to route traffic demands and switch-off idle links and nodes are presented in [START_REF] Chiaraviglio | Minimizing ISP network energy cost: Formulation and solutions[END_REF]. Other dynamic procedures to dynamically optimize routing paths and network power consumption are instead presented in [START_REF] Vasić | Energy-aware traffic engineering[END_REF]; the proposed methods exploit a local search scheme and assume to cope with network devices whose consumption is strongly dependant on the utilization. Other work on energy-aware network management with flow-based routing include [START_REF] Garroppo | Energy saving heuristics in backbone networks[END_REF][START_REF] Garroppo | Mixed integer non-linear programming models for green network design[END_REF][START_REF] Athanasiou | Introducing energy-awareness in traffic engineering for future networks[END_REF][START_REF] Chu | Green mpls traffic engineering[END_REF][START_REF] Coiro | Energyaware traffic engineering: A routing-based distributed solution for connection-oriented {IP} networks[END_REF][START_REF] Galán-Jiménez | Using bio-inspired algorithms for energy levels assessment in energy efficient wired communication networks[END_REF][START_REF] Giroire | Minimization of network power consumption with redundancy elimination[END_REF].

Shortest path routing protocols such as OSPF are considered in [START_REF] Prem Bianzino | Grida: Green distributed algorithm for energy-efficient ip backbone networks[END_REF][START_REF] Shenand | Routing on demand: toward the energy-aware traffic engineering with ospf[END_REF][START_REF] Amaldi | Energy-aware ip traffic engineering with shortest path routing[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 [START_REF] Prem Bianzino | Grida: Green distributed algorithm for energy-efficient ip backbone networks[END_REF] the authors proposed a distributed algorithm to put to sleep network links by exploiting link state packets exchanged by OSPF to disseminate information concerning the link loads. Link state packets are used to exchange information also in [START_REF] Shenand | Routing on demand: toward the energy-aware traffic engineering with ospf[END_REF], where a centralized network management platform to adjust OSPF link weights and equal cost path splitting ratios is presented. Energy-aware link weight optimization is also used by the heuristic methods for off-line network management proposed in [START_REF] Amaldi | Energy-aware ip traffic engineering with shortest path routing[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]. The OSPF protocol is instead modified in [START_REF] Cianfrani | An ospf-integrated routing strategy for qos-aware energy saving in ip backbone networks[END_REF] to force the network to forward the packets on a restricted set of shortest path trees. In this way, an higher number of links will remain idle and thus put to sleep.

Other energy-aware network management approaches that adopt different perspectives include a restricted path MILP formulation to put to sleep network links in networks operated with a hybrid OSPF+MPLS routing protocol [START_REF] Zhang | Greente: Power-aware traffic engineering[END_REF], methods for energy-aware traffic engineering in Carrier Grade Ethernet networks [START_REF] Capone | An optimization framework for the energy management of carrier ethernet networks with multiple spanning trees[END_REF], strategies to switch off links according exclusively to network topology features (traffic demands are ignored) [START_REF] Cuomo | Network pruning for energy saving in the internet[END_REF] and MILP models for energy-aware network planning [START_REF] Idzikowski | Optimal design of green multi-layer core networks[END_REF].

Preserving network resiliency is a key issue in particular when related to energy consumption. [START_REF] Sansò | On reliability, performance and Internet power consumption[END_REF] shows for the first time the impact on network reliability when only energy-efficiency is considered in the design. Thus, network survivability requirements must be taken into account when reducing network consumption [START_REF] Monti | Energy-efficient lightpath provisioning in a static wdm network with dedicated path protection[END_REF][START_REF] Muhammad | Energy-efficient wdm network planning with dedicated protection resources in sleep mode[END_REF][START_REF] Cavdar | Energy-efficient design of survivable wdm networks with shared backup[END_REF][START_REF] Jirattigalachote | Dynamic provisioning strategies for energy efficient wdm networks with dedicated path protection[END_REF][START_REF] Bao | Poweraware provisioning strategy with shared path protection in optical wdm networks[END_REF][START_REF] Aldraho | Enabling energy efficient and resilient networks using dynamic topologies[END_REF][START_REF] He | Dynamic power-aware shared path protection algorithms in wdm mesh networks[END_REF][START_REF] Wu | Power efficient integrated routing with reliability constraints in ip over wdm networks[END_REF][START_REF] Francois | Optimizing link sleeping reconfigurations in isp networks with offpeak time failure protection[END_REF]. Almost all these articles focus on the WDM domain -only [START_REF] Aldraho | Enabling energy efficient and resilient networks using dynamic topologies[END_REF][START_REF] Francois | Optimizing link sleeping reconfigurations in isp networks with offpeak time failure protection[END_REF] deals with IP networks -and they provide a set of algorithm and models for the energyaware management of lightpaths. Backup lightpaths are used to reserve resources to implement the desired protection scheme, and network devices that are unused or carry backup lightpaths only are put to sleep.

Dedicated protection is considered in [START_REF] Muhammad | Energy-efficient wdm network planning with dedicated protection resources in sleep mode[END_REF][START_REF] Monti | Energy-efficient lightpath provisioning in a static wdm network with dedicated path protection[END_REF][START_REF] Jirattigalachote | Dynamic provisioning strategies for energy efficient wdm networks with dedicated path protection[END_REF]. An ILP formulation to efficiently manage the lightpaths and based on a set of precomputed paths is proposed in [START_REF] Muhammad | Energy-efficient wdm network planning with dedicated protection resources in sleep mode[END_REF]. Some heuristic algorithm to tackle the same problem are presented in [START_REF] Monti | Energy-efficient lightpath provisioning in a static wdm network with dedicated path protection[END_REF][START_REF] Jirattigalachote | Dynamic provisioning strategies for energy efficient wdm networks with dedicated path protection[END_REF]. Shared protection is instead adopted in [START_REF] Cavdar | Energy-efficient design of survivable wdm networks with shared backup[END_REF][START_REF] Bao | Poweraware provisioning strategy with shared path protection in optical wdm networks[END_REF][START_REF] He | Dynamic power-aware shared path protection algorithms in wdm mesh networks[END_REF]. In [START_REF] He | Dynamic power-aware shared path protection algorithms in wdm mesh networks[END_REF] the authors propose an algorithm for dynamic energy-aware admission control where connections are accepted if enough spare capacity is available in the network. Heuristic algorithms to optimize the routing of a fixed set of network demands and put to sleep network devices are presented in [START_REF] Cavdar | Energy-efficient design of survivable wdm networks with shared backup[END_REF][START_REF] Bao | Poweraware provisioning strategy with shared path protection in optical wdm networks[END_REF]. Our work differs from the previous ones for several aspects, including (i) the multi-period structure of our optimization problem, (ii) the routing management performed, in our case, at the IP level, (iii) the use of two different maximum-utilization thresholds that account for the two cases when a link failure has occurred or not, and (iv) the development of both exact and heuristic methods. Furthermore, the proposed heuristic algorithm can be used also as online optimization tool.

Differently from the proposals already mentioned, in [START_REF] Wu | Power efficient integrated routing with reliability constraints in ip over wdm networks[END_REF] network survivability is not managed by explicitly defining backup paths, but imposing a budget on the minimum reliability required by each connection. The reliability of each path is computed by considering a measure of the failure probability observed on each link. The authors propose a heuristic to minimize the power consumption by optimizing the network routing and blocking the connection that cannot be served with the required reliability.

Finally, in [START_REF] Aldraho | Enabling energy efficient and resilient networks using dynamic topologies[END_REF] the authors present some MILP formulation to save energy while providing protection to each single network links or demands, while in [START_REF] Francois | Optimizing link sleeping reconfigurations in isp networks with offpeak time failure protection[END_REF] a heuristic framework to compute different topology configurations by considering a single link failure protection is proposed.

To the best of our knowledge, except in our preliminary work presented in [START_REF] Addis | A robust optimization approach for energy-aware routing in MPLS networks[END_REF], the explicit management of uncertain traffic demands taking into account the consumption reduction has been previously addressed only in [START_REF] Coudert | Robust Redundancy Elimination for Energy-aware Routing[END_REF], where the authors proposed a green robust approach to exploit redundancy elimination to reduce the amount of transmit-ted traffic and consequently reduce the network consumption. In [START_REF] Coudert | Robust Redundancy Elimination for Energy-aware Routing[END_REF] the uncertainty affects the redundancy degree of each demand and the addressed optimization problem is very different from ours. More generally, in literature the management of traffic variation issues is typically faced in an indirect way by applying on-line strategies that adjust the network configuration according to the observed traffic variations. We refer the reader to [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF] and [START_REF] Ben-Tal | Robust optimization[END_REF] for general surveys on robust optimization applied in both general and network contexts.

Finally, we refer the reader to [START_REF] Pióro | Routing, Flow and Capacity Design in Communication and Computer Networks[END_REF] for a general survey on multi-period network optimization and survivable network design.

Energy Management, robustness and survivability

We here present the key elements of our proposed approach and discuss their interactions and roles when we manage the system so as to reduce the energy consumption and to guarantee at the same time a certain level of protection again failures and traffic variations. This preliminary high level description of the framework is intended to give an overview of the issues that motived our mathematical models that are then presented with all their details in next section. For this reason we included at the end of this section also a visual example on a small network that can help understand more easily the impact of resiliency and robustness on energy efficiency.

Energy management

Given a backbone IP network composed of routers (chassis) and links (line cards), we consider the problem of planning in advance (i.e. off-line) both routing and topology configurations so as to minimize the daily network consumption, while guaranteeing the normal network operation, in terms of both QoS and resiliency to failures. Power consumption is reduced by efficiently exploiting a subset of network equipment to route traffic demands and by putting to sleep the remaining idle devices.

To efficiently adapt the network configuration to the traffic level, we split the considered time horizon, a single day for instance, in multiple time periods, or scenarios, characterized by a given level of traffic (see Figure 1). The time period division is performed by analyzing the daily traffic profiles (see for instance [START_REF] Mackarel | Study of environmental impact, dn3.5.2, geant project[END_REF]) typically observed or estimated by the network provider. The traffic demand in each time period is, for the sake of simplicity, represented by a single average estimated traffic matrix, the traffic scenario. The demand profile associated to the considered time horizon is cyclically repeated.

Demand robustness

Due to the regular daily/weekly behaviour of the traffic profiles [START_REF] Mackarel | Study of environmental impact, dn3.5.2, geant project[END_REF], network providers exploit direct [59] and indirect methods [START_REF] Casas | Efficient methods for traffic matrix modeling and on-line estimation in largescale ip networks[END_REF], to estimate traffic matrices in normal conditions. Since real traffic matrices naturally deviate around predicted values, we use robust optimization techniques to reserve enough spare bandwidth to satisfy unpredictable peaks of traffic. The basic idea is to adapt the modeling proposed in [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF], according to which each traffic demand can vary into a close symmetric interval centered on its average traffic value, to our energy aware-problem. Next, a set of tunable parameters is used to adjust the robustness degree of the solutions by varying the total deviation allowed on each link.

In our multi-period modeling framework the consumption over the entire time horizon is minimized by jointly considering all traffic scenarios. Inter-period constraints are introduced to take into account the energy cost paid to power on a particular device and to preserve network stability. For instance, we impose a so-called card-reliability constraints to preserve the line-card lifetime by forbidding to reactivate too many times a single line card over the considered time horizon.

Survivability

Network resiliency to failures is provided by considering two different kind of protection schemes, i.e. dedicated and shared, which allow to protect the network in case of break down of a single link. Given that multiple link failures and single node failures are very unlikely events, they have not been considered in this paper. Both dedicated and shared protection require the definition of a primary path and a backup path for each traffic demand. The latter is used to transmit data only after a link break down in the primary path. The two schemes have different advantages and disadvantages. Dedicated protection reserves demand capacity on both primary and backup paths. This results in an excessive amount of reserved backup resources that, in case of single link-failure, will never be completely exploited. In shared protection, the backup paths corresponding to two link-disjoint primary paths share the same backup capacity when routed on the same link, in fact they will never be activated simultaneously. In this case the amount of backup capacity required is the maximum of the two traffic amounts. Due to the smaller amount of backup resources required, shared protection naturally allows to reduce the energy consumption.

A visual example

In this subsection we illustrate with an example different outcomes of our modeling framework that depend on the protection and robustness features being introduced or not in the modeling. They are presented in Figures 2(a), 2(b), 2(c) and 2(d). In the figures, link capacity is assumed to be 2 units and there are four traffic demands each requesting 1 unit of traffic.

Figure 2(a) represents the simple case for which no protection schemes are implemented. We can see that there are 4 nodes and 10 bidirectional links to put to sleep, making this case the most energy-efficient.

When the uncertainty of traffic demands is explicitly considered (Figure2(b)) the system cannot share any link between the four traffic demands routed in the network. Thus, 6 more links and 3 more nodes have to be activated, increasing the consumption with respect to the Simple case given above.

In case of dedicated protection (Figure 2(c)), additional links and nodes have to be switched on (3 more nodes and 6 more links) to carry the backup paths. Note that, since each backup path has the same bandwidth requirement of the primary one, the two demands G -I cannot be routed on the links already used by the backup paths of the two demands D -F. However, by implementing shared protection (Figure 2(d)), it is possible to sensibly reduce the consumption due to protection and put to sleep 2 more nodes and 2 more links w.r.t. the dedicated case. These savings can be achieved because shared protection allows to share the backup resources on the links used by the secondary paths (links G -H and H -I), since the two couples of demands D -F and G -I are satisfied two by two by link disjoint paths.

To further reduce the network power consumption, in addition to the classic approach just described, we also investigate a slightly modified variant, that we call smart version, in which line cards carrying only backup paths can be put to sleep for most of the time, thus having negligible consumption. In fact, since line cards can be rapidly reactivated (in the order of milliseconds) from the sleeping state [START_REF]Active/idle toggling with 0base-x for energy efficient ethernet[END_REF], it is reasonable to assume that those used only by backup paths are powered only when required by the occurrence of a failure. It is worth pointing out that the same scheme cannot be applied to network routers because a chassis switch on requires non negligible time. Further, QoS is guaranteed by imposing a limitation on the maximum link utilization allowed. Since the occurrence of a link failure is very unlikely, we opted to include a second higher utilization threshold enable only when backup resources are exploited. Allowing the network to operate with a higher but still reasonable congestion during the very limited failure intervals we are able to further increase the energy savings.

As shown in Figures 2(e) and 2(f), the smart protection allows to further reduce the network consumption by switching off an additional number of links. When compared with the corresponding classic cases, the dedicatedsmart protection 6 more links can be put to sleep, whereas with shared-smart protection the additional sleeping links are 4. Note that with the smart strategies the system is pushed to use different links to carry backup and primary paths, while with the classic ones links can be shared by primary and backup without forcing to switch on a the considered link.

In the following section, we provide more details on the considered problems and describe the mathematical formulations.

Reference model for energy management

Let us consider a backbone IP network. Each router is composed of a chassis of capacity ψ and a set of line cards each of capacity γ. Duplex links connect routers. To guarantee the connectivity of link (i, j), the same number n i j of line cards is available on both routers i and j. Therefore, each link has multiple operating states based on the number of powered-on line cards. Since links have the same bandwidth in both directions, the same number of line cards has to be available on each router. We can model the network by a symmetric directed graph G(N, A), where N represents the sets of chassis, and A represents the bidirectional links and their associated line cards.

Furthermore, let π i j and π be positive real parameters representing the hourly power consumption, respectively, of a single card installed on link (i, j), and of a chassis of i. Since the reactivation of a chassis typically causes a consumption spike, parameter δ is used to quantify the additional power consumption (normalized with respect to hourly one) associated to a chassis switching-on.

The maximum utilization level allowed on each link to guarantee the required QoS is denoted by the positive real parameter µ a ∈ [0, 1]. Therefore the available bandwidth on one card is given by µ a γ. When all the line cards connected to a given router are in the stand-by mode, the router chassis can be put to sleep too.

Due to the multi-period nature of the addressed problem, the considered daily time horizon is split among a set S of time periods σ of duration h σ . The network traffic is represented by a set of traffic demands D, where each demand d ∈ D is described by a source node o d , a destination node t d , and the amount of demand q σ d that has to be satisfied during period σ. Such amount is a fraction of the nominal value of demand ρ d . Table 1 resumes the parameters list.

We first introduce the reference MILP formulation for the multi-period energy-aware network management previously presented in [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF], then, in the following sections, we describe the modeling of the resiliency and robustness features. The variables used in the models are resumed in Table 2.

Routing constraints

Demand d routing in scenario σ is described through binary variables x dσ i j , which are equal to 1 if the routing path of demand d is routed on link (i, j) in scenario σ. The routing constraints (1) represent flow conservation constraints and describe the single path unsplittable routing typically used in MPLS networks. The right hand side parameter

b d i is 1 if i = o d , -1 if i = t d
and 0 in all the other cases.

(i, j)∈A

x dσ i j -

( j,i)∈A x dσ ji = b d i , ∀σ ∈ S , i ∈ N, d ∈ D (1)

Chassis status constraints

The status of the chassis in each scenario is described by a binary variable y σ i , which is equal to 1 if the chassis i is on during scenario σ, and 0 otherwise. The proper value of such variables is forced by constraints (2): if a demand is routed through chassis i the left hand side of equation ( 2) is strictly positive and therefore y σ i must be equal to one. On the other hand, if y σ i is equal to zero, no demand can be routed through chassis i. The constraints guarantee also that the chassis capacity ψ is not exceeded.

(i, j)∈A d∈D q σ d x dσ i j + ( j,i)∈A d∈D q σ d x dσ ji ≤ ψy σ j , ∀σ ∈ S , j ∈ N (2)

Card and link status and capacity

The number of active line cards on link (i, j) during period σ is represented by an integer variable w σ i j ∈ [0, n i j ]. As for the chassis, the status of cards is set through a set of constraints, which also guarantee that the bandwidth available on each link, which depends on the number of active cards w σ i j , is not exceeded (3). To insure a suitable level of QoS, the total used capacity is limited by a fraction µ a . Besides, constraints (4) force to keep activated the same number of line cards in both the direction of each link, so as to guarantee network stability.

d∈D q σ d x dσ i j ≤ µ a γw σ i j , ∀σ ∈ S , (i, j) ∈ A (3)
w σ i j = w σ ji , ∀σ ∈ S , (i, j) ∈ A (4)

Chassis activation consumption constraints

The power consumption for the reactivation of chassis j at the beginning of scenario σ is represented by continuous non negative variable z σ j , whose value is set by means of constraint (5).

z σ j ≥ δ π y σ j -y σ-1 j , ∀σ ∈ S , j ∈ N (5)

Card activation constraints

To preserve the lifetime and the reliability of network equipment, a single line card cannot be switched on more than ε times along an entire day. The number of activation of a card is described by auxiliary binary variable u σ i jk , which is equal to one if cards k-th linking nodes i and j is powered on in scenario σ. The number of card activations is limited by constraints [START_REF] Mellah | Review of facts, data and proposals for a greener Internet[END_REF], while the proper value of variables u σ i jk is set by constraints [START_REF] Bolla | Energy efficiency in the future internet: a survey of existing approaches and trends in energy-aware fixed network infrastructures[END_REF].

σ∈S u σ i jk ≤ ε, ∀(i, j) ∈ A, k ∈ [1, n i j ] (6)
n i j k=1 u σ i jk ≥ w σ i j -w σ-1 i j , ∀σ ∈ S , (i, j) ∈ A (7)

Objective function

The objective function [START_REF] Vetter | Research roadmap for green wireline access[END_REF] aims at minimizing the daily energy consumption. It is the sum of three terms taking into account, respectively, the energy consumed by the router chassis in each scenario j∈N πy σ j , the energy used by the line cards (i, j)∈A π i j w σ i j , and energy one consumed when chassis are reactivated j∈N z σ j .

min σ∈S         h σ         j∈N πy σ j + (i, j)∈A π i j w σ i j         + j∈N z σ j         (8)

Modeling resilience

Modeling a protection scheme requires the addition of both routing variables and flow conservation constraints.

Backup path routing constraints

The backup paths are represented by binary variables ξ dσ i j , which are equal to one if backup path of demand d is routed on link (i, j) in scenario σ. As the variables describing the primary path x dσ i j , the backup path variables must satisfy the flow conservation constraints [START_REF] Amaldi | Energy-aware ip traffic engineering with shortest path routing[END_REF].

(i, j)∈A ξ dσ i j - ( j,i)∈A ξ dσ ji = b d i ∀σ ∈ S , i ∈ N, d ∈ D (9)

Link disjoint constraints

In addition, the primary and backup path of a given demand d must be link disjoint, as guaranteed by constraints [START_REF] Chabarek | Power awareness in network design and routing[END_REF] and (11).

x dσ i j + ξ dσ i j ≤ 1, ∀σ ∈ S , (i, j) ∈ A, d ∈ D (10)
x dσ i j + ξ dσ ji ≤ 1, ∀σ ∈ S , (i, j) ∈ A, d ∈ D (11)

Chassis status constraints

Chassis capacity constraints (12) take into account the resources reserved for primary and backup paths:

(i, j)∈A d∈D q σ d x dσ i j + ξ dσ i j + ( j,i)∈A d∈D q σ d x dσ ji + ξ dσ ji ≤ ψy σ j , ∀σ ∈ S , j ∈ N (12)

Card capacity constraints

Concerning the line card capacity, two values of the maximum card capacity fraction are considered to provide the network QoS both in case of normal network operation and of single link failure. If no failure occurs, the value of maximum card capacity fraction is µ a , and the constraints are inequalities [START_REF] Bolla | Cutting the energy bills of internet service providers and telecoms through power management: An impact analysis[END_REF]. For the single link failure, the value of maximum card capacity fraction is µ b , which represents the maximum utilization allowed in case of failure when both primary and backup paths are used. The value µ b is greater or equal than µ a , and it is used by the network operator to find the desired trade off between resilience and consumption. It allows the network congestion to be slightly deteriorating during the very short and unlikely periods in which a single link failure occurs, in order to achieve higher savings in normal conditions.

The capacity needed on each link is different according to the different adopted protection schemes [START_REF] Zeadally | Energy-efficient networking: past, present, and future[END_REF] and [START_REF] Addis | Multi-period traffic engineering of resilient networks for energy efficiency[END_REF].

Dedicated protection case

According to the dedicated protection scheme, the capacity constraint [START_REF] Zeadally | Energy-efficient networking: past, present, and future[END_REF] states that the sum of the demands whose primary and backup paths are routed on a link cannot exceed the link available capacity.

d∈D q σ d x dσ i j + ξ dσ i j ≤ µ b γw σ i j , ∀σ ∈ S , (i, j) ∈ A (13)

Shared protection case

According to the shared protection scheme, the capacity on a link must be greater or equal than the sum of the demands whose primary path is routed on the considered link plus the worst backup capacity due to different failures. Such case is computed by evaluating the impact of each failure and selecting the highest one. The impact of a failure is given by the sum of the demands whose backup paths are routed on the considered link and whose primary paths fall if the considered failure occurs. To correctly model the backup capacity to be reserved on each link, a set of binary variables g dσ i jkl is introduced. A binary variable g dσ i jkl is defined for each pair of links (i, j) and (k, l), each demand d and each scenario σ, and it is equal to 1 if the demand must be rerouted on link (i, j) if link (k, l) fails, i.e. the traffic demand d is served by a primary and a backup paths routed, respectively, on link (i, j) and link (k, l) in scenario σ. Constraints ( 14) force the correct value of g dσ i jkl .

g dσ i jkl ≥ x dσ i j + ξ dσ kl -1, ∀σ ∈ S , (i, j), (k, l) ∈ A, d ∈ D, (14)
Taking into account variables g dσ i jkl , the impact of failure (k, l) on link (i, j) can be computed by constraints [START_REF] Addis | Multi-period traffic engineering of resilient networks for energy efficiency[END_REF], which allow to protect the network (i.e. to reserve enough capacity) by reserving on each link enough backup bandwidth to cope with the worst-case single link failure. d∈D q σ d x dσ i j + g dσ kli j ≤ µ b γw σ i j , ∀σ ∈ S , (i, j), (k, l) ∈ A (15)

The smart consumption variant

The smart protection variant exploit the possibility of reactivating sleeping line cards in a few milliseconds and therefore the possibility of putting to sleep line cards that carry only backup paths during normal network operation. Such new feature of dynamic network can be modelled by replacing constraints [START_REF] Zeadally | Energy-efficient networking: past, present, and future[END_REF] with constraints [START_REF] Addis | Energy aware management of resilient networks with shared protection[END_REF] for the dedicated protection case.

d∈D q σ d x dσ i j + ξ dσ i j ≤ µ b γn i j y σ j , ∀σ ∈ S , (i, j) ∈ A. (16)
Similarly, constraints (15) must be replaced with [START_REF] Addis | A robust optimization approach for energy-aware routing in MPLS networks[END_REF] for the shared protection case. d∈D q σ d x dσ i j + g dσ kli j ≤ µ b γn i j y σ j , ∀σ ∈ S , (i, j), (k, l) ∈ A (17) Constraints ( 16) and [START_REF] Addis | A robust optimization approach for energy-aware routing in MPLS networks[END_REF] guarantee that the total available capacity on each link (γn i j ) is not exceeded by the sum of primary and backup traffic routed on it, when all the cards are switched on. H owever, the status of cards is forced by primary paths only, as described by [START_REF] Bolla | Cutting the energy bills of internet service providers and telecoms through power management: An impact analysis[END_REF]. Note that the sleeping cards carrying backup paths have to be connected to an active chassis.

Modeling robustness to traffic variations

Uncertainty may arise in the problem, if the demand amount is described by an uncertain parameter q σ d . To deal with such uncertainty, we apply the cardinalityconstrained approach proposed in [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF]. The approach exploits the idea that all the uncertain parameters are very unlikely to assume simultaneously their worst possible value. The uncertain parameters are assumed to vary in the interval q σ d -qσ d , q σ d + qσ d , where q σ d and qσ d represent, respectively, the expected traffic value and the maximal variation considered during period σ. In [START_REF] Bertsimas | Theory and applications of robust optimization[END_REF] uncertainty is dealt with in such a way to guarantee than any solution is feasible if, for each card capacity constraint associated to link (i, j) and scenario σ, at most Γ σ i j2 demands, among those routed on (i, j), assume their maximum value q σ d + qσ d , while all the others assume their expected one, q σ d . Parameters Γ σ i j ∈ [0, |D|] can be used to tune the required robustness degree by limiting the number of traffic demands that are considered uncertain. In this way, we do not limit ourself to perform a trivial worst-case optimization. Instead, by using Γ σ i j values smaller than |D|, we can ignore the most unlikely realizations where all the traffic demands routed on a link (i, j) assume simultaneously the maximal deviation, achieving in this way higher level of energy savings.

Uncertain parameters have an impact on constraints (3) 3 . For each such constraints a set U σ i j is defined as the set of demands which assume their maximum possible amount. The cardinality of U σ i j is at most Γ σ i j . The robust counterpart of constraints (3) is:

d∈D q σ d x dσ i j + max {U σ i j ⊆D, |U σ i j |≤⌊Γ σ i j ⌋}          d∈U σ i j qσ d x dσ i j          (18)
≤ µγw σ i j , ∀σ ∈ S , (i, j) ∈ A Let Θ σ i j represents the worst case additional traffic to be considered on link (i, j) during period σ, i.e.

Θ σ i j = max {U σ i j ⊆D, |U σ i j |≤⌊Γ σ i j ⌋} d∈U σ i j qσ d x dσ i j
. The value of Θ σ i j can be computed through dualization.

Given a solution represented by the routing variables x dσ i j , the value of Θ σ i j can be computed solving the following linear programming problem:

Θ σ i j = max d∈D qσ d x dσ i j u dσ i j (19)
s.t.

d∈D u dσ i j ≤ Γ σ i j ( 20
)
0 ≤ u dσ i j ≤ 1, ∀d ∈ D (21)
Let us denote with ǫ σ i j and l dσ i j the dual variables associated to constraints ( 20) and ( 21) respectively. The dual of problem ( 19)-( 21) is the following:

min d∈D l dσ i j + Γ σ i j ǫ σ i j (22)
s.t.

ǫ σ i j + l dσ i j ≥ qσ d x dσ i j , ∀d ∈ D (23)
l dσ i j ≥ 0, ǫ σ i j ≥ 0 ∀d ∈ D (24)
According to the duality properties, the optimal primal and dual objective functions coincide and thus the robust constraints (18) can be replaced with the following constraints:

d∈D q σ d x dσ i j + d∈D l dσ i j + Γ σ i j ǫ σ i j ≤ µγw σ i j , (25)
∀σ ∈ S , (i, j) ∈ A

ǫ σ i j + l dσ i j ≥ qσ d x dσ i j , ∀d ∈ D, ∀(i, j) ∈ A, ∀σ ∈ S (26)
l dσ i j ≥ 0, ∀d ∈ D, ∀(i, j) ∈ A, ∀σ ∈ S (27)
ǫ σ i j ≥ 0, ∀(i, j) ∈ A, ∀σ ∈ S (28)
It is very important to point out that the robust approach can be naturally applied to the protected case too.

Resolution methods

All the MILP formulations previously presented can be treated by state-of-the-art solvers. In our case we experimented with CPLEX 12.5.0.0 using the AMPL modeling language and setting a resolution time limit of 1 hour. Due to the time-limit and the complexity of the models, the final solution may be sub-optimal.

Since, for scalability reasons, the MILP formulations can be efficiently solved for instances with less than 20 nodes, 50 links and 50 demands, to solve larger instances (up to 50 nodes and 300 demands) we developed different mathematical programming heuristic techniques exploiting variants of the original MILP formulations.

Single time period heuristic

The single time period heuristic (STPH) presented in [START_REF] Addis | Energy management through optimized routing and device powering for greener communication networks[END_REF] to efficiently solve the reference problem can be easily adapted to solve both the protected and the robust cases. The basic idea is to deal with each time period separately and sequentially, by solving a reduced MILP model derived from the main one, where only variables and constraints concerning the considered interval are taken into account. It is worth pointing out that some group of constraints are used to correctly evaluate the energy consumed to reactivate a chassis, and keep track of the number of switching on each line card along all the previous periods. Card reliability constraints are respected by keeping activated all the line cards already switched on ε times in the previously optimized time intervals. Since the choice of the starting period may influence the final solution, the algorithm is repeated |S | times, taking at each iteration a different starting scenario.

Path restriction

To further speed up the single time period heuristic, we developed a new version of the algorithm, i.e. single time period heuristic with restricted paths (STPH-RP) based on the use of a pre-computed restricted set of paths assigned to each traffic demand.

To formalize the restricted-path variants of the complete MILP formulations, let P d represent the set of precomputed paths assigned to demand d, and let χ d p and λ d p be the binary variables equal to 1 when path p ∈ P d is exploited by demand d, respectively, as primary path and backup path. Note that in the variables we neglect the scenario index σ because in the single time period heuristic we consider one single scenario at the time.

The following set of constraints replace the flow conservation constraints (1) to force each demand to use a single primary path:

p∈P d χ d p = 1, ∀d ∈ D (29)
Similarly, for the protected case, flow conservation constraints of backup path (9) are replaced by:

p∈P d λ d p = 1, ∀d ∈ D (30)
Then, considering that:

x d i j = p∈P d :(i, j)⊂p λ d p , ∀(i, j) ∈ A, d ∈ D (31)
ξ d i j = p∈P d :(i, j)⊂p χ d p , ∀(i, j) ∈ A, d ∈ D, (32)
all the original constraints have to be modified by replacing the x d i j and ξ d i j variables with the corresponding path-based expression.

The pre-computed paths of each demand are generated by means of the following procedure. First, for each demand d ∈ D, an LP formulation is solved to compute the maximum flow m d that can be routed from node o d to node t d when each link has unitary capacity. Then, being Ω an integer positive parameter, the precomputed paths are obtained by performing Ω iterations of the following multistage algorithm: (i) a random weight is assigned to each link, (ii) for each demand d, m d shortest paths (disjoint if possible) are computed by solving a minimum cost flow LP formulation, (iii) a minimum cost spanning tree is computed with the Kruskal algorithm, (iv) a single path for each demand is extracted from the links belonging to the spanning tree. At the end of the procedure Ωm d + Ω paths are available. It is worth pointing out that the two different strategies used to generate the paths allow to find both disjoint paths to better achieve load balancing and implement the protection schemes, and very correlated paths (with a lot of common links) to minimize the consumption.

Warm starting

Due to the extreme complexity of the shared protection model, we developed a procedure to warm start CPLEX (when solving both the multi-period exact model and each single period of the heuristic) with a solution rapidly obtained by solving the dedicated protection formulation with a limited time-limit. The warm-start is implemented in CPLEX using the option send_statuses 2. In case of the exact formulation the time limit is typically set to 3 minutes (with 57 minutes left to the resolution of the main model). For the heuristic the solution obtained for the previous scenario is given as input to solver, by properly initializing the variables of the considered time periods with the values of those of the previous one. The warm-start is implemented in CPLEX using the option send_statuses 2. In the heuristic, due to some AMPL code constraints, the resolution of each single period is equally split between the dedicated protection warm start and the shared protection model. Note that each feasible solution of the dedicated protection is naturally feasible for the shared protection one.

Computational Results

We performed several computational tests to evaluate both the impact of the different proposed strategies and the performance of the resolution methods. All the experiments were carried out on machines equipped with Intel i7 processors with 4 core and multi-thread 8x, and 8Gb of RAM. Test-bed and instance characteristics are described in Section 8.1, the behaviour of each strategy is exhaustively discussed in Section 8.2 and, finally, extensive results on the largest instances are analysed in Section 8.3.

The test-bed

We tested both exact and heuristic methods using four network topologies provided by the SND Library (SNDLib) [START_REF] Orlowski | Sndlib 1.0 survivable network design library[END_REF], i.e. polska, nobel-germany, nobel-eu and germany.

The summary of the instances features is reported in Table 4, where columns ID, Net, |N|-|N c |, |A|, |D|, equip and scenario represent the instance label, the network topology, the number of nodes and core nodes, the number of unidirectional link, the number of traffic demands, the equipment configuration and the traffic scenario, respectively.

In each test instance all routers are assumed to be equipped with the same type of chassis and the same type of cards. However, we experimented with three different configuration cases, alfa, delta, and eta, wherein the chassis technology is always the same, while the type of cards is varied (but the same technology is used for all the cards in a given instance). Chassis and card details are reported in Table 3. The network nodes are equally and randomly divided between core routers and edge routers. Notice that only core routers can be put to sleep, since they are neither source nor destination of any traffic demand.

Traffic matrices have been derived by those provided by the SNDLib. The nominal values ρ d have been computed by scaling the SNDLib matrices with a fixed parameter ̟ µ b µ a . The chosen value of ̟ µ b µ a is the highest value such that the matrix obtained multiplying the SNDLib values by ̟ µ b µ a can be routed in the real full active network with protection (dedicated or shared), while respecting the maximum utilization in normal conditions µ a , and the maximum utilization in failure conditions µ b . In the majority of our tests we used matrices scaled for ̟ 85% 50% computed by considering dedicated protection. That is, we used µ a (link max-utilization due to primary paths) equal to 50% and µ b (link max-utilization due to both primary and backup paths) equal to 85%.

We split a single day in six traffic periods corresponding to the following time intervals: 1) 8a.m.-11a.m., 2) 11a.m.-1p.m., 3) 1p.m.-2.30p.m., 4) 2.30p.m.-6.30p.m., 5) 6.30p.m.-10.30p.m., 6) 10.30p.m.-8a.m. We experimented with four different traffic scenarios (column scenario). The first three, i.e a, b, and c, were generated by considering traffic values q σ d distributed uniformly as a fraction r σ d of nominal value ρ d . In particular we considered q σ d = r σ d ρ d , where parameter r σ d is generated according to the uniform distribution N(r

σ d + r σ d , r σ d -rσ d ).
The average values r σ d were chosen according to the traffic profile of Figure 1, the variation rσ d is chosen as 0.2 4 . In the fourth traffic scenario, namely aver (see Table 4), all the r σ d are equal to the average values r σ d . This last scenario was used to compare with the robust approaches.

To evaluate the performance of the robust approaches, we experimented with uncertainty sets of different sizes, 4 Negative values are rounded up to value zero.

i.e. by setting rσ d = 0.05, 0.10, 0.15, 0.20, and by tuning the robustness degree of the solutions, i.e. by varying each Γ σ i j from 0 (no robustness) to 5 (high level of robustness in the considered instances).

As for the remaining parameters, we set δ (chassis switching-on normalized consumption) equal to 0.25, ε (switching-on limit) equal to 1, and n i j (number of cards in link (i, j)) equal to 2 for each link.

Savings vs. Protection/Robustness

First we aim at pointing out the impact of the different features provided to the network according to the protection/robustness strategy considered, i.e. simple, robust, dedicated-classic, shared-classic dedicated-smart, shared-smart, robust plus dedicated-classic and robust plus dedicated-smart. The expected trade-off between energy savings and network survivability/robustness is reported in Figure 3. Starting from the simple energy-aware problem with no protection and no robustness, we expect the energy consumption of the network to gradually increase if we increase the protection/robustness (P/R) level. At the first P/R level we put the robust approach with no protection, which, by varying the robustness parameters Γ dσ i j and the size of the uncertainty intervals rσ d , allows to allocate additional resources to cope with traffic variations. Then, we find, in sequence, the shared-smart strategy and the dedicated-smart one. Although shared protection guarantees the same degree of survivability of the dedicated one, with single link failures, we consider it less conservative because it produces solutions with, in general, less spare capacity available. Clearly, the larger the spare capacity, the higher the capability of the network to react to failures and other unexpected events. Moving towards the right side of the graph, we first meet the shared-classic and the dedicated-classic strategies, and finally the two robust plus dedicated ones. Classic schemes are considered more conservative that the smart ones because all the backup capacity is kept constantly activated. It is worth to notice that, in term of consumptions, the possibility of switching off the backup links is considered more effective than the switching from the simple dedicated protection to the complex shared one (it will be confirmed by the following results). Robust plus shared strategies are not reported due to the excessive computational effort required, that does not allow to efficiently solve even the smaller instances.

To confirm the expected behaviour we considered twelve instances associated to the smallest network, polska, and solved the MILP formulation of each problem with a time limit of one hour. The effectiveness of the computing methods, i.e. computing times, solution optimality, absolute savings, are evaluated, as well.

Robust strategy

Let us first analyze the results reported in Table 5 for the robust case. Columns r and TL represent the size of the demand deviation and the resolution time-limit, respectively. Then, for each instance, column %E c represents the ratio between the energy consumption of the optimized network and the energy consumption of the full active one. The robustness degree of the solution is evaluated on a set of randomly generated scenarios. We generated 10 , 000 random traffic scenarios where the r dσ parameters were generated with the uniform distribution N(r

σ d + rσ d , r σ d -rσ d ).
For each generated scenario we then tested the optimized solutions by routing the random demands and verifying the violation of the capacity robust constraints. Columns % in f eas and Max dev represent the percentage of random scenarios wherein at least one capacity constraint was violated, and the largest positive difference between the observed maximum utilization and the allowed maximum one, respectively. A solution can be considered completely robust if % in f eas = 0%. Results clearly show that, thanks to the robust model, the optimized solutions can be completely immunized to traffic variations by using the robust parameter Γ equal to 4 (four demands considered uncertain on each link). Most importantly, the absolute energy consumption increase necessary to reserve additional resources is smaller, in average, than 1%, and, in the worst case (instance 4 with r = 0.2) equal to 2.8%. It is worth pointing out that (i) the nominal solution (Γ = 0) is largely unreliable, with % in f eas 95.6% and Max dev = 35.6% in the worst case (instance 12 with r σ d = 0.2), (ii) the increase of Γ produces a gradual improvement of the robustness degree, as expected, (iii) the increase of the uncertainty interval force the model to reserve more resources and reduce the potential savings. The results analysis suggests that robustness has a relatively small energetic cost and allows to greatly reduce the violations of the maximum utilization constraint due to traffic variations, which is a very crucial aspect for any off-line network management approach.

Protection strategies: energy efficiency

Results concerning the protection scheme models are reported in Tables 789.In Table 7, the energy savings achieved by simple, dedicated-classic, and shared-classic models is shown. Column %E c represents the ratio between the energy consumption of the optimized network and the energy consumption of the full active one. Column gap opt represents the gap of the final solution w.r.t. to the best lower bound computed by CPLEX. Column gap simple represents the relative increase of energy consumption due to the survivability requirement: it is computed as

E prot c -E simple c /E simple c
, where %E prot c and %E prot simple c represent the energy consumption of the optimized network w.r.t. the full active one, for the unprotected and protected case, respectively. As expected, the explicit im-Exact model -Robust approach with no protection

Γ = 0 Γ = 1 Γ = 2 Γ = 3 Γ = 4 ID r TL %E c % in f eas Max dev %E c % in f eas Max dev %E c % in f eas Max dev %E c % in f eas Max dev %E c
% in f eas Max dev 4 0.05 1h 60,6% 42,33% 6,57% 60,7% 9,91% 0,78% 60,9% 0,00% 0,00% 60,9% 0,00% 0,00% 60,9% 0,00% 0,00% 4 0.10 1h 60,6% 81,69% 16,32% 60,9% 10,18% 2,56% 60,9% 0,09% 1,73% 60,9% 0,09% 1,73% 60,9% 0,00% 0,00% 4 0.15 1h 60,6% 92,32% 24,64% 60,9% 15,27% 9,22% 61,4% 0,27% 4,76% 61,4% 0,27% 4,76% 61,4% 0,00% 0,00% 4 0.20 1h 60,6% 95,60% 32,30% 60,9% 32,89% 19,19% 62,4% 0,04% 1,26% 62,4% 0,04% 1,26% 63,4% 0,00% 0,00% 8 0.05 1h 50,6% 40,80% 6,24% 50,8% 10,48% 0,78% 51,0% 0,00% 0,00% 51,0% 0,00% 0,00% 51,0% 0,00% 0,00% 8 0.10 1h 50,6% 78,39% 14,83% 51,0% 1,29% 0,61% 51,0% 0,00% 0,00% 51,0% 0,00% 0,00% 51,0% 0,00% 0,00% 8 0.15 1h 50,6% 88,64% 24,24% 51,0% 9,49% 8,85% 51,5% 0,46% 4,89% 51,5% 0,46% 4,89% 51,6% 0,00% 0,00% 8 0.20 1h 50,6% 93,95% 33,59% 51,0% 27,62% 19,41% 52,6% 0,05% 1,10% 52,6% 0,05% 1,10% 53,2% 0,00% 0,00% 12 0.05 1h 60,0% 41,37% 7,05% 60,1% 4,71% 0,70% 60,3% 0,00% 0,00% 60,3% 0,00% 0,00% 60,3% 0,00% 0,00% 12 0.10 1h 60,0% 78,73% 15,41% 60,3% 11,23% 2,34% 60,3% 0,00% 0,00% 60,3% 0,00% 0,00% 60,5% 0,00% 0,00% 12 0.15 1h 60,0% 88,49% 24,41% 60,3% 6,87% 9,17% 60,7% 0,41% 4,92% 60,7% 0,41% 4,92% 60,8% 0,00% 0,00% 12 0.20 1h 60,0% 94,12% 35,61% 60,3% 40,13% 18,45% 61,6% 0,01% 0,20% 61,6% 0,01% 0,20% 62,5% 0,00% 0,00% plementation of a protection scheme increases the network energy consumption, in fact the energy-aware approaches keep activated additional resources to cope with possible failures. In the case without protection, the consumption E c varies from 50.1% to 60.6%, in the dedicated-classic case network consumption is between 61.4% and 71.4%, with absolute and relative increase, on average, of 10% and 20%, respectively. By considering the more sophisticated shared-classic protection, the consumption can be reduced, w.r.t. the dedicated-classic case, up to 5%. However, while for the dedicated-classic, the model computes nearly optimal solutions within the time limit of one hour ( gap opt usually lower than 1% and never above 3.5%), for the shared-classic case the gap from the best lower bound is in some instances larger than 15% (Instances 6-7), as the model is more complex and requires a high computational effort. For this reason, in some instances the reported difference between shared and dedicated protection consumption is smaller than 1% (Instances 6-7-11).

To overcome this problem, the single time period heuristic can be applied. Heuristic results are reported in Tables 8 and 9. In Table 8 9,6% 3 1h 60,3% 0,6% 71,4% 0,7% 18,4% 70,4% 8,9% 16,7% 5 1h 50,7% 2,4% 62,2% 2,6% 22,7% 59,3% 10,1% 17,0% 6 1h 50,1% 0,8% 61,4% 3,3% 22,7% 60,3% 15,5% 20,5% 7 1h 50,3% 0,4% 61,7% 2,7% 22,6% 61,7% 15,8% 22,6% 9 1h 60,0% 1,4% 70,9% 0,9% 18,1% 66,2% 3,2% 10,3% 10 1h 59,8% 0,7% 70,7% 0,8% 18,1% 65,7% 3,6% 9,8% 11 1h 59,7% 0,0% 70,8% 0,5% 18,6% 70,9% 11,1% 18,8% by the smart protection solution produced by STPH w.r.t. the classic one. Columns ∆ classic smart represent the absolute difference between the energy consumption obtained with the smart and the classic models. The time limits are reported, as well: in Tables 8 and9, differently from Tables 5 and7, T L represent the time limit imposed to CPLEX when solving a single time period of STPH.

Table 8 shows that, by using STPH with a time limit of 6 minutes, we reduce the energy consumption of the solutions with shared protection up to about 5% (Instances 3 -6-7-11). The difference between shared and dedicated protection for the instances for which the gap obtained solving the model is large (Instances 6-7-11) is therefore increased. Furthermore, it is worth pointing out that, even for the instances of the dedicated case solved at optimality or with a very small gap using the complete model, the gap between STPH and the formulation is very small, varying between 0.6% and -0.2%, negative values meaning that STPH solutions improve upon the sub-optimal solutions found by CPLEX when solving the model. Having shown the good quality of STPH algorithm solutions in the remainder of this section we report only the results obtained by solving STPH, for practical and space reasons. The possibility of putting to sleep the line cards carrying only the backup links (smart protection) is expected to substantially decrease the energy consumption of the network w.r.t. the classic case. This hypothesis is clearly confirmed by the results of Table 9, where we observe that smart protection allows to reduce the consumption of the protected solutions (w.r.t. the total network consumption) by up to 7.1% and 3.9%, for the dedicated and shared case, respectively. Smart shared produces smaller energy consumption reduction, w.r.t. the non smart case, than smart dedicated. The smaller reduction produced by shared protection solutions w.r.t. dedicated one is motivated by the fact that, since the first requires a minor amount of backup capacity, also lesser backup resources can be put to sleep when switching from the classic to the smart scheme. The most important result is that with the smart scheme dedicated protection can be more energy efficient than classic shared protection, while being less computationally expensive.

Protection strategies: congestion analysis

Concerning the congestion, it is necessary to remind that shared protection, due to the high efficiency of the backup allocation scheme, can deal with levels of traffic that cannot be managed by the dedicated protection scheme, without violating the maximum utilization constraints. In Table 10 the value of ̟ 85% 50% , namely the maximum values used to scale the SNDLib traffic matrix while respecting the maximum utilization constraints with µ a = 0.5, µ b = 0.85 and r σ d = 1 ∀d ∈ D, σ ∈ S , are reported for the shared and dedicated case. Results show that shared protection allows to manage a traffic that is, on average, greater than the one managed by the dedicated case. The increase rises up to about 10%. Therefore, although the computational effort required by the shared case is significantly increased, shared protection scheme is worth to be implemented to reduce the network congestion. To better understand the balance between network congestion and energy savings, we report in Figure 4 the network energy-consumption computed by varying the secondary maximum utilization threshold µ b from 0.5 to 1. In this specific set of tests, we considered dedicated protection and traffic matrices obtained by using ̟ 50% 50% instead of the ̟ 85% 50% . In fact, with ̟ 85% 50% the problem would not be feasible in case of µ b < 0.85. Figure 4 shows that the dif-ference between the network consumption obtained with µ b = 0.5 and µ b = 1 varies from 4% to 8%. The plot clearly shows how a network provider can balance energy savings and network congestion according to his own requirements.

Joint protection and robustness

To conclude the analysis on the polska instances, let us analyse the results reported in Table 6, which reports about the robust dedicated case solved with the exact formulation. As for the simple robust case, it is possible to obtain solutions completely immunized to traffic variation (% in f eas = 0%) where the power consumption is increased, on average of 1% and in the worst case of 2.6% (Instance 8, r σ d = 0.2). Furthermore, the energy consumption reduction obtained by the smart approach w.r.t. the classic one, is about 4% and up to 6% (similar to the protected non robust case).

Finally, Figure 5 reports the average energy savings obtained with the three scenarios a, b, and c. It is possible to observe that the final energy consumption for polska computed by varying the protection degree follows the expected trend previously showed in Figure 3.

Largest networks

In the second group of tests, we experimented with nobel-germany, nobel-eu and germany network by running STPH or STPH-RP (the restricted path version of STPH). For comparison purposes, a restricted set of instances were tested with both procedures. STPH-RP was then used to solve instances that were too computationally demanding to be efficiently solved in a reasonable amount of time by the simple STPH. The time limit for the single time period used to run STPH and STPH-RT are reported in Table 11. We report a / when a given network has not been solved with the corresponding method (for instance with nobel-germany we used only STPH).

Figure 6 reports the results for the nobel-germany network, while Figure 7 reports the results for the nobel-eu network.

First of all, we can observe that the consumption trend showed in Figure 5, is confirmed in Figures 6 and7, where we report the network consumption obtained by STPH on nobel-germany and nobel-eu networks considering different protection cases. The only difference that can be observed is that the energy consumption for the dedicatedsmart case is on average smaller that that one of the shared-classic case. This can be explained as the solver is not able to efficiently solve the shared protection model, even for single period, and to obtain a small gap when the instance dimensions increase. It is worth to note that, in some tests, the solution computed by the warm start procedure cannot be improved by the solver within the chosen time-limit. Besides, due to memory limits (8GB of RAM), the shared protection instances could not even be initialized for the nobel-eu and germany networks. Thus, as a solution feasible for the dedicated problem is naturally feasible for the shared one the solutions obtained by solving the dedicated problem are applied also for the shared case. By solving STPH, the consumption difference between the simple case and the most protected one, i.e. the dedicated-classic robust, is around 20% for both nobel-germany, nobel-eu networks.

In Figure 8, the network energy consumption, the infeasibility degree and the maximum threshold overrun are represented for the robust case (in Table 5, the last two values are indicated as % in f eas and Max dev ). The four graphics clearly prove that our approach allow to efficiently manage traffic variations without considerably increasing the network consumption (increase lower than 2% for solution completely immunized). It is also worth pointing out that by simply increasing Γ from 0 (no robustness) to 1, we are already able to substantially immunize the solution, with % in f eas improved from 90% to around 15%. The results for the eta case are very similar and therefore not reported.

For the dedicated robust case, the medium size nobeleu network was solved using the restricted-path version of STPH, for efficiency reasons. With the aim of evaluating the efficiency of STPH-RP in Figure 10 the consumption obtained with both STPH and STPH-RP (with Ω = 10) considering nobel-eu network and dedicated classic protection are reported. The consumption difference between the two solution methods is generally slightly lower than 10%. Therefore, taking into account all the paths allows to gain a substantial amount of saving when handling small and medium size instances. However, the use of a restricted set of paths turned out to be a reasonable strategy to reduce the computational effort when dealing with larger instances without excessively degrading the achieved energy saving.

Finally, to further confirm the good performance of STPH-RP, the average network consumption values computed on the germany network with all the different protection schemes are reported in Figure 11. We solved the instances with STPH-RP with Ω = 5. Also in this case the heuristic method provides significant savings, obtaining final network consumption from 60% up to 80% of the original value.

Concluding Remarks

In this paper we have exhaustively investigated the issues concerning energy saving and network resilience to both failures and traffic variations. We have proposed a comprehensive set of modelling tools to efficiently perform multi-period off-line energy-aware network management without compromising the normal network opera-tion. We have presented and discussed both exact and heuristic methods able to put to sleep network line cards and chassis while reserving backup resources to efficiently cope with single link failures and leaving enough spare capacity to absorb the unexpected peak of traffic. Extensive experimentations have shown that even when full protection is guaranteed (dedicated protection with robustness to traffic variations) it is possible to save up to 30% of the daily network consumption.

Figure 1 :

 1 Figure 1: Traffic scenarios.

Figure 2 :

 2 Figure 2: Energy consumption minimization vs Resilience requirements.

  Joint primary and backup path routing

Figure 3 :

 3 Figure 3: Savings vs Protection/Robustness.

Figure 4 :

 4 Figure 4: Analysis of the trade-off between energy savings and network congestion, obtained by adjusting the secondary utilization threshold µ b from 0.5 to 1 when solving STPH.

Figure 5 :

 5 Figure 5: Energy savings achieved by STPH when implementing the different protection schemes on polska instances.

Figure 6 :

 6 Figure 6: Energy savings achieved by STPH when implementing the different protection schemes on nobel-germany instances.

Figure 7 :

 7 Figure 7: Energy savings achieved by STPH when implementing the different protection schemes on nobel-eu instances. The * in the graph legend is used for the instances solved, due to complexity issues, with STPH-RP using Ω = 10.

Figure 8 :

 8 Figure 8: Energy savings achieved by STPH when implementing the robust scheme on nobel-germany instances.

Figure 9 :

 9 Figure 9: Energy savings achieved by STPH when implementing the robust scheme on nobel-eu instances.

Table 1 :

 1 Number of available cards on link (i, j) γ Per card capacity π i j Card power consumption η Maximum number of allowed card switch-on µ a Max primary paths arc capacity fraction µ b Max primary and backup paths arc capacity fraction o d Origin of demand d t d Destination of demand d q σ Parameters

	ψ Chassis maximum capacity
	π Chassis power consumption
	δ	Chassis switch on energy consumption
	Demand value on scenario σ h σ Duration of scenario σ n i j d

Table 2 :

 2 Variables

Table 3 :

 3 Overview of different network configurations

	case	device	capacity	hourly cons.
	-	Chassis Juniper M10i	16Gbps	86.4 W
	al f a	FE 4 ports	400 Mbps	6.8 W
	delta	OC-3c 1 port	155 Mbps	18.6 W
	eta	GE 1 port	1 Gbps	7.3 W

Table 4 :

 4 Test instances.

	ID	Net	|N|-|N c |	|A|	|D| equip scenario
	1	polska	12-6	36	15	alfa	a
	2	polska	12-6	36	15	alfa	b
	3	polska	12-6	36	15	alfa	c
	4	polska	12-6	36	15	alfa	aver
	5	polska	12-6	36	15	delta	a
	6	polska	12-6	36	15	delta	b
	7	polska	12-6	36	15	delta	c
	8	polska	12-6	36	15	delta	aver
	9	polska	12-6	36	15	eta	a
	10	polska	12-6	36	15	eta	b
	11	polska	12-6	36	15	eta	c
	12	polska	12-6	36	15	eta	aver
	13 nobel-ger	17-9	42	21	alfa	a
	14 nobel-ger	17-9	42	21	alfa	b
	15 nobel-ger	17-9	42	21	alfa	c
	16 nobel-ger	17-9	42	21	alfa	aver
	17 nobel-ger	17-9	42	21	delta	a
	18 nobel-ger	17-9	42	21	delta	b
	19 nobel-ger	17-9	42	21	delta	c
	20 nobel-ger	17-9	42	21	delta	aver
	21 nobel-ger	17-9	42	21	eta	a
	22 nobel-ger	17-9	42	21	eta	b
	23 nobel-ger	17-9	42	21	eta	c
	24 nobel-ger	17-9	42	21	eta	aver
	25	nobel-eu	28-14	82	90	alfa	a
	26	nobel-eu	28-14	82	90	alfa	b
	27	nobel-eu	28-14	82	90	alfa	c
	28	nobel-eu	28-14	82	90	alfa	aver
	29	nobel-eu	28-14	82	90	delta	a
	30	nobel-eu	28-14	82	90	delta	b
	31	nobel-eu	28-14	82	90	delta	c
	32	nobel-eu	28-14	82	90	delta	aver
	33	nobel-eu	28-14	82	90	eta	a
	34	nobel-eu	28-14	82	90	eta	b
	35	nobel-eu	28-14	82	90	eta	c
	36	nobel-eu	28-14	82	90	eta	aver
	37 germany	50-25	176 182	alfa	a
	38 germany	50-25	176 182	alfa	b
	39 germany	50-25	176 182	alfa	c
	40 germany	50-25	176 182	alfa	aver
	41 germany	50-25	176 182 delta	a
	42 germany	50-25	176 182 delta	b
	43 germany	50-25	176 182 delta	c
	44 germany	50-25	176 182 delta	aver
	45 germany	50-25	176 182	eta	a
	46 germany	50-25	176 182	eta	b
	47 germany	50-25	176 182	eta	c
	48 germany	50-25	176 182	eta	aver

Table 5 :

 5 Robustness analysis for the solutions obtained by the robust exact model with no protection with 1h time limit on polska instances

					Exact model -Robust approach with dedicated protection
					Γ = 0			Γ = 1			Γ = 3			Γ = 5
	ID	r	TL	%E c	% in f eas	∆ classic smart	%E c	% in f eas	∆ classic smart	%E c	% in f eas	∆ classic smart	%E c	% in f eas	∆ classic smart
	4	0.05	1h	70,6%	96,7%	-3,1%	71,4%	17,9%	-3,4%	71,5%	0,5%	-3,4%	71,6%	0,0%	-3,5%
	4	0.10	1h	70,6%	98,7%	-3,1%	71,4%	61,7%	-3,2%	71,6%	1,2%	-3,3%	71,8%	0,0%	-3,4%
	4	0.15	1h	70,6%	99,8%	-3,1%	71,6%	63,2%	-3,4%	71,9%	0,7%	-3,3%	72,1%	0,0%	-3,3%
	4	0.20	1h	70,6%	99,7%	-3,1%	71,6%	64,1%	-3,2%	72,1%	3,5%	-3,1%	72,6%	0,0%	-3,4%
	8	0.05	1h	60,8%	95,7%	-5,5%	61,8%	31,9%	-6,2%	61,8%	0,4%	-5,7%	62,0%	0,0%	-6,0%
	8	0.10	1h	60,8%	99,1%	-5,5%	61,8%	38,6%	-5,7%	62,3%	1,9%	-5,4%	62,3%	0,0%	-5,9%
	8	0.15	1h	60,8%	99,0%	-5,5%	61,8%	63,8%	-5,8%	62,6%	1,8%	-5,8%	63,2%	0,0%	-6,2%
	8	0.20	1h	60,8%	99,8%	-5,5%	62,0%	55,4%	-5,5%	62,9%	2,8%	-5,3%	63,4%	0,0%	-5,5%
	12	0.05	1h	70,0%	91,4%	-3,2%	70,9%	21,4%	-3,7%	70,9%	0,9%	-3,4%	71,0%	0,0%	-3,7%
	12	0.10	1h	70,0%	97,4%	-3,2%	70,9%	32,3%	-3,5%	71,0%	1,0%	-3,4%	71,3%	0,0%	-3,7%
	12	0.15	1h	70,0%	99,0%	-3,2%	71,0%	56,2%	-3,5%	71,4%	1,5%	-3,4%	71,5%	0,0%	-3,5%
	12	0.20	1h	70,0%	99,4%	-3,2%	71,0%	71,3%	-3,4%	71,6%	2,1%	-3,3%	71,9%	0,0%	-3,5%

Table 6 :

 6 Robustness analysis for the solutions obtained by the robust exact model with classic dedicated protection with 1h time limit on polska instances

  we analyze the gap between exact model and STPH solutions. Columns Heur gap represent the difference between the energy consumption obtained by the model and that achieved by STPH, i.e. E heur

					Exact model
			simple case dedicated prot classic	shared prot classic
			ID TL %E c	gap opt %E c	gap opt gap simple %E c	gap opt gap simple
			1 1h 60,6% 1,3% 71,4% 1,4% 17,8% 66,9% 3,6% 10,3%
			2 1h 60,5% 0,9% 71,3% 0,9% 17,8% 66,3% 4,4%
	c	-E model c	.
	In Table 9 we compare the saving improvement achieved

Table 7 :

 7 Comparison between simple and protected solutions obtained by solving the exact model with 1h time limit with polska instances.

Table 8 :

 8 Comparison between the energy saving achieved by solving the exact model and running the single time period heuristic with different types of protection.

Table 9 :

 9 Comparison between the energy saving achieved by STPH with classic and smart protection schemes.

Table 10 :

 10 Comparison between the efficiency of the shared protection and the dedicated protection schemes.

		S hared	Ded
	ID	̟ 85% 50%	̟ 85% 50%
	1-2-3-4	1053.7	941.8
	5-6-7-8	408.32	365.0
	9-10-11-12	2634.3	2354.6
	13-14-15-16	18039.3	16451.6
	17-18-19-20	6990.5	6375.0
	21-22-23-24	45099.9	41129.0

Table 11 :

 11 CPLEX time limits for the single time period to solve nobel-germany, nobel-eu and germany instances with different types of protection. Energy saving comparison between STPH and STPH-RP on nobel-eu network with dedicated classic protection.

			simple		robust	dedicated		shared	robust-dedicated
	Net T L S T PH	T L S T PH-RP	T L S T PH	T L S T PH-RP	T L S T PH	T L S T PH-RP	T L S T PH	T L S T PH-RP	T L S T PH	T L S T PH-RP
	nobel-ger	60s	/	90s	/	90s	/	360s	/	120s	/
	nobel-eu	300s	/	300s	/	300s	300s	/	/	1200s	/
	germany	/	600s	/	600s	/	600s	/	/	/	1200s

For the sake of conciseness, we assume parameters Γ i j to be integer. However a more general case, in which they can also continuous, can be easily dealt with, as described in[START_REF] Bertsimas | Theory and applications of robust optimization[END_REF].

[START_REF] Bolla | Cutting the energy bills of internet service providers and telecoms through power management: An impact analysis[END_REF] Although uncertain parameters are present in constraint (2), uncertainty has not an impact on such constraints, as such constraints force the status of chassis variables rather than limiting the overall used capacity.

]Brunilde Sansó is a full professor of electrical engineering at École Polytechnique de Montreal and director of the LOR-LAB. Her interests are in performance, reliability, design, and optimization of wireless and wireline networks. She is a recipient of several awards, Associate Editor of Telecommunication Systems, and editor of two books on planning and performance.