Patrick Poullie
email: poullie@ifi.uzh.ch

Burkhard Stiller
email: stiller@ifi.uzh.ch

Cloud Flat Rates Enabled via Fair Multi-resource Consumption

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Cloud Computing (CC) is a computing paradigm enabled by the growing connectivity provided by modern communication systems combined with virtualization technology [START_REF] Etsion | A Global Scheduling Framework for Virtualization Environments[END_REF][START_REF] Wei | A Game-theoretic Method of Fair Resource Allocation for Cloud Computing Services[END_REF]. CC allows server farms to provide their combined computing power on demand to customers, such as end-users and companies. To process a workload through CC a customer starts Virtual Machines (VM) in the cloud that process the workload. In particular, VMs are defined by Virtual Resources, e.g., virtual CPU and virtual RAM [START_REF] Arcangeli | Increasing Memory Density by Using KSM[END_REF][START_REF] Etsion | A Global Scheduling Framework for Virtualization Environments[END_REF]. Resources in private/commodity clouds are often managed by quotas, i.e., each user has a quota defining a maximum of VRs that his VMs may have in total.

As opposed to this, in commercial clouds, it is common practice that customers pay on a per-VM-basis [START_REF]Amazon EC2 Pricing[END_REF]. However, the telecommunications sector has shown that customers often prefer flat rates [START_REF] Altmann | Effects of Pricing on Internet User Behavior[END_REF][START_REF] Levinson | Too Expensive to Meter: the Influence of Transaction Costs in Transportation and Communication[END_REF][START_REF] Odlyzko | Internet Pricing and the History of Communications[END_REF], even if a volume-based tariff would reduce costs [START_REF] Lambrecht | Paying Too Much and Being Happy about It: Existence, Causes, and Consequences of Tariff-Choice Biases[END_REF]. Contrary to a volume-based tariff, a flat rate induces a fixed cost cap. For private users this allows for care-free use and for commercial users an easy budgeting of costs. This suggests high demand for cloud flat rate schemes. With a cloud flat rate customers pay a monthly fee to get access to a cloud, where they can start VMs. Just as Internet flat rates come with a maximum bandwidth, cloud flat rate customers would get a certain quota to spawn VMs.

However, this mechanism is neither sufficient to cap costs that individual customers cause nor to ensure fairness between customers, because customers (i) often deploy different amounts of their quota and (ii) load VMs differently. In particular, (i) means that some customers may only operate a few VMs leaving most of their quota unused, while others fully utilize their quota. (ii) describes that even if customers create exactly the same number and types of VMs, the costs they cause varies depending on how they utilize their VMs. Because VMs on the same host compete for resources, a heavily loaded VM may impair the performance of other VMs on the same host. Therefore, in flat rate or private/commodity clouds, it is desirable to limit VMs of heavy customers in favor of VMs of more moderate customers, such that VMs of moderate customers are not impaired by VMs of heavy customers.

While technical means to enforce fairness in this way exist [START_REF] Arcangeli | Increasing Memory Density by Using KSM[END_REF][START_REF] Guo | Understanding Memory Resource Management in VMware vSphere 5.0. Performance study[END_REF][START_REF]Best Practices for KVM[END_REF], cloud fairness is neither sufficiently enforced nor explored [START_REF] Dolev | No Justified Complaints: On Fair Sharing of Multiple Resources. 3rd[END_REF][START_REF] Etsion | A Global Scheduling Framework for Virtualization Environments[END_REF][START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF][START_REF] Joe-Wong | Multi-resource Allocation: Fairness-efficiency Tradeoffs in a Unifying Framework[END_REF][START_REF] Majid Zahedi | REF: Resource Elasticity Fairness with Sharing Incentives for Multiprocessors[END_REF]. What makes the definition of cloud fairness problematic, is that multi-resource fairness has to be defined without access to utility functions. Here, multi-resource implies that bundles, which are allocated to the consumers, consist of heterogenous resources and the non-accessibility of utility functions implies that it is unknown how much consumers valuate different bundles (a consumer's utility function maps each bundle to a number quantifying the consumer's valuation for the bundle). Utility functions are unknown, because, depending on the workload a VM executes, dependencies between resources differ. Therefore, even for the owner of a VM, the VM's utility function is difficult to determine. Furthermore, no standardized format to describe utility functions exists. Lastly, even if cloud users could determine and express utility functions, they may not want to reveal it to the cloud operator, as it reveals private information about internal processes.

The problem of cloud fairness is often addressed by VM scheduling, i.e., deciding which VM should be started next. This is insufficient to streamline resource utilization in clouds, because it makes static assumptions on utility functions necessary [START_REF] Bonald | Enhanced Cluster Computing Performance through Proportional Fairness[END_REF][START_REF] Dolev | No Justified Complaints: On Fair Sharing of Multiple Resources. 3rd[END_REF][START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF], while VM demands are dynamic. To reach a general applicability (including VM runtime), this paper defines the Greediness Metric (GM) in return to the research question how to quantify the commensurability of VMs' runtime resource utilization, i.e., how fair VMs behave. Because fairness is an intuitive concept, i.e., differs from person to person, the conformance of the GM with an intuitive understanding of fairness is verified by a questionnaire among more than 600 participants.

The remainder of this paper is structured as follows: Section 2 discusses related work leading to the research question stated in Section 2.1. Section 3 outlines the questionnaire, presents its results, and discusses key findings. Based on these outcomes, the new Greediness Metric (GM) is defined in Section 4. Section 5 draws conclusions and outlines future work.

For a single resource, the size of bundles can be quantified, and thus, the value of bundles objectively compared. Therefore, fairness can be intuitively defined as Max-Min-Fairness [START_REF] Floyd | Metrics for the Evaluation of Congestion Control Mechanisms[END_REF] or Proportional Fairness [START_REF] Bonald | Enhanced Cluster Computing Performance through Proportional Fairness[END_REF] and quantified by metrics such as [START_REF] Rajendra | A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems[END_REF][START_REF] Lan | An Axiomatic Theory of Fairness in Network Resource Allocation[END_REF][START_REF] Zukerman | Efficiencyfairness Tradeoff in Telecommunications Networks[END_REF]. While such allocation problems were extensively studied in computer science [START_REF] Chandra | Surplus Fair Scheduling: A Proportional-share CPU Scheduling Algorithm for Symmetric Multiprocessors[END_REF][START_REF] Floyd | Metrics for the Evaluation of Congestion Control Mechanisms[END_REF], multi-resource allocation received much less attention.

In data centers, which comprise clusters, grids, and clouds, consumers share resources, such as CPU time, RAM, Disk I/O and space, and network access, wherefore it is necessary to define fairness, when every consumer receives a bundle of heterogenous resources. As noted in [START_REF] Dolev | No Justified Complaints: On Fair Sharing of Multiple Resources. 3rd[END_REF][START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF][START_REF] Joe-Wong | Multi-resource Allocation: Fairness-efficiency Tradeoffs in a Unifying Framework[END_REF][START_REF] Klusáček | Multi Resource Fairness: Problems and Challenges[END_REF][START_REF] David | Beyond Dominant Resource Fairness: Extensions, Limitations, and Indivisibilities[END_REF][START_REF] Majid Zahedi | REF: Resource Elasticity Fairness with Sharing Incentives for Multiprocessors[END_REF], multi-resource allocation in data centers is so far not fully investigated and often reduced to single-resource allocation problems at the cost of efficiency and fairness [START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF][START_REF] Lee | Heterogeneity-aware Resource Allocation and Scheduling in the Cloud[END_REF].

The assumption of more advanced approaches is that the resource utilization of jobs, which determine those entities consuming resources in clusters and grids, is static or at least follows static ratios [START_REF] Dolev | No Justified Complaints: On Fair Sharing of Multiple Resources. 3rd[END_REF][START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF]. This allows to introduce fairness by job scheduling, i.e., which job should be started next. However, VMs, which are the entities consuming resources in clouds, change their resource utilization frequently and dynamically. This not only prohibits reducing cloud fairness to VM scheduling but also prohibits incorporating the concept of envy-freeness [START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF][START_REF] Gutman | Fair Allocation without Trade[END_REF][START_REF] Majid Zahedi | REF: Resource Elasticity Fairness with Sharing Incentives for Multiprocessors[END_REF]. Envy-freeness, i.e., no consumer prefers to swap his bundle with another, is essential for the definition of fairness in economics. However, this definition is not applicable, when consumer's utility functions are unknown or highly dynamic, as it is the case for clouds. Subsequently, approaches to multi-resource fairness in data centers (especially their cloud instances) are compared here, while ignoring numerous approaches focusing on a single resource. Dominant Resource Fairness (DRF) is the most prominent approach to introduce multi-resource fairness in data centers [START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF]. DRF defines the value of a bundle as the biggest proportion relative to the total supply of any resource in it (cf. Section 3.2). Therefore, to define the value of a bundle only one resource is considered, which is also known as the L ∞ norm. A DRF fair allocation is the allocation that maximizes this value for every consumer. [START_REF] Gutman | Fair Allocation without Trade[END_REF] points out that for many other functions (including all other L i∈N norms) a unique allocation exists that can be found in polynomial time, but that the authors of DRF never argue why their choice is superior. Leontief utility functions model that resources are required in static ratios, i.e., increasing the amount a consumer receives of one resource does not increase his utility if his share of all other resources is not increased by the same factor. While all proofs for DRF's desirable properties are based on Leontief utility functions [START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF][START_REF] David | Beyond Dominant Resource Fairness: Extensions, Limitations, and Indivisibilities[END_REF], the actual DRF scheduling policy, as proposed in [START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF], allows consumers to request different resource bundles. Therefore, in the scheduling process, consumers can have arbitrary utility functions, but DRF's properties are only proven for Leontief utility functions. [START_REF] Bonald | Enhanced Cluster Computing Performance through Proportional Fairness[END_REF] shows that proportional fairness is superior to DRF in terms of efficiency and comes with the same desirable characteristics under realistic assumptions. Bottleneck-based fairness (BBF) was introduced in [START_REF] Dolev | No Justified Complaints: On Fair Sharing of Multiple Resources. 3rd[END_REF][START_REF] Etsion | A Global Scheduling Framework for Virtualization Environments[END_REF]. An allocation is bottleneck-based fair, if every consumer either is allocated all requested resources or at least the equal share on a congested/bottleneck resource and the other resource in proportion. [START_REF] Zeldes | On-line Fair Allocations Based on Bottlenecks and Global Priorities[END_REF] defines a multi-resource on-line scheduling policy that achieves BBF without knowing consumer's utility functions in advance.

[28] presents an allocation policy that achieves game-theoretic fairness, i.e., sharing incentive, envy freeness, and pareto-efficiency, when allocating cache capacity and memory bandwidth. Different applications are profiled to convincingly argue that Cobb-douglas utility functions are well suited to model diminishing returns and substitution effects for these resources.

[17] considers the fair sharing of grids between customers and research groups. Contrary to all other approaches discussed in this section, [START_REF] Klusáček | Multi Resource Fairness: Problems and Challenges[END_REF] achieves fairness by a penalty/priority function, which is close to our approach. In particular, such function determines the priority of consumers when granting resource requests. Such approach is much more practically oriented, because no assumptions about utility functions need to be made.

Another research field on cloud resource allocation focuses on live-migration [START_REF] Kapil | Live Virtual Machine Migration Techniques: Survey and Research Challenges[END_REF][START_REF] Strunk | Costs of Virtual Machine Live Migration: A Survey[END_REF], i.e., rescheduling VMs during runtime. While live-migration is applied during VM runtime it is, just as VM scheduling, orthogonal to this work here, because it does not change priorities of VMs.

Table 1 compares the approaches discussed in terms of the adopted fairness definition, the application area, and the assumed utility function. Most approaches are way too complex to be applied during VM runtime and none of these is based on an intuitive understanding of fairness. This motivates the general research undertaken and specifically this paper's problem statement.

Problem Statement

The characteristic of fair cloud resource allocations that is distinct for this context is that customers (between whom fairness is to be defined) utilize resources from different resource pools (hosts) by intermediaries (VMs). While fairness has to be achieved between customers, this has to be done by allocating resources to their VMs. Unfortunately resources can only be moved between VMs, which run on the same host. However, besides this structural dilemma, also a more general problem is faced: Defining and enforcing fairness of multi-resource allocations without knowing consumers' utility functions. In particular, because bundles consist of multiple heterogenous resources, bundles can contain resources in different amounts. This prohibits an objective comparison of bundles. For example, some customers may require more CPU for their workloads, while others require more RAM [START_REF] Lee | Heterogeneity-aware Resource Allocation and Scheduling in the Cloud[END_REF]. A third customer may deploy the cloud for backups and, therefore, mostly requires disk-space and bandwidth. Therefore, consumers can have different preferences over the same bundles.

Because utility functions of consumers in clouds are unknown, it is not possible to define fairness via utility functions here and, thus, fairness has to be defined via bundles that VMs serve themselves. In particular, hosts work as "self-serving stores" for VMs, which means that they provide all requested resources to VMs, if possible. Therefore, fairness in clouds has to be defined as constraining VMs of those customers whose VMs overcharge their self-serving stores, i.e., are greedy. While also the concept of greediness has no formal definition, it can be better defined and quantified with the information that is available in clouds.

Therefore, the problem statement for this paper reads as follows: The greediness of VMs can be defined and quantified based on their multi-resource self-servings. An allocation is fair in such a case, when (i) the aggregates per customer of these quantifications are aligned and (ii) VMs of "greedy" customers are constrained in favor of VMs of "less greedy" customers.

Questionnaire

A questionnaire was developed to evaluate the intuitive understanding of fairness and greediness and to justify empirically the design of the new Greediness Metric (GM). The questionnaire can be found in the appendix of [START_REF] Poullie | Cloud Flat Rates Enabled via Fair Multi-resource Consumption[END_REF]. The questionnaire specified real-life resource allocation scenarios in terms of three questions Q1, Q2, and Q3 to not distract participants by technical terms and let them fully concentrate on the question of fairness. While these scenarios were specific, the questions were carefully designed to reach generic insights about intuitive understandings of fairness and greediness. To describe these questions subsequently, resources and consumers are denoted by r i and c j , respectively, where i, j ∈ N >0 . Questionnaire participants had to chose between different options of allocations or define rankings of consumers. Additionally, participants were offered to explain their answers in text boxes. The questionnaire did not address any particular target group, to allow evaluating a popular and intuitive understanding of fairness that is not biased by technical notions established by experts. Out of 721 participants, who started the questionnaire, 604 completed it. Q2 addressed the question of how consumer requests should be taken into account, when allocating resources, but did not address the question of how fairness or greediness can be defined. Therefore, Q2 is not directly related to the design of the GM and only discussed in [START_REF] Poullie | Cloud Flat Rates Enabled via Fair Multi-resource Consumption[END_REF].

Choosing the Most Fair Allocation (Question 1)

DRF is the most prominent approach for fairness in data centers (cf. Section 2). Therefore, DRF's conformance with an intuitive understanding of fairness was evaluated by Q1. In particular, DRF's centerpiece, which is using the L ∞ norm to measure the value of a bundle (c.f. Section 2 and Section 3.2), was evaluated. The scenario described covers two resources r 1 and r 2 of which six and twelve units where available, respectively. These resources have to be allocated to three consumers c 1 , c 2 , and c 3 . c 1 only requires r 1 , c 2 only r 2 , and c 3 requires for each unit of r 1 two units of r 2 . This results in seven possible allocations to allocate all resources and do not give consumers resources they have no use for. However, most of these allocations are intuitively unfair, e.g., in two of these allocations at least one consumer receives no resources at all.

Because the scenario describes that resources are requested in static ratios, it is transferable to allocation problems in data centers, where these static ratios of resource requests, i.e., Leontief utility functions, are the standard assumption [START_REF] Bonald | Enhanced Cluster Computing Performance through Proportional Fairness[END_REF][START_REF] Dolev | No Justified Complaints: On Fair Sharing of Multiple Resources. 3rd[END_REF][START_REF] Ghodsi | Dominant Resource Fairness: Fair Allocation of Heterogeneous Resources in Datacenters[END_REF]. Table 2 shows four of the seven allocations and their respective labels. These four allocations were presented to participants numerically and graphically and they had to choose the allocation that seemed most fair to them. As expected, A11 and A14 were only chosen by a minority of the 721 participants (0.4% and 1.1%, respectively) and most participants deterred between A12 and A13 (30.0% and 68.5%, respectively). The following arguments in support of A12 are summarized from textual comments received:

c 1 and c 2 only compete with c 3 for resources, but not with one another. A fair allocation splits resources equally between those who contend for them. -All receive an equal amount of what they want.

-This is the only allocation where nobody can complain that someone has more of the same resource.

For the following reasons A13 was supported:

-When prices are introduced based on available units, this option gives the same value to all consumers. c 1 and c 2 receive 2/3 of one resource and c 3 1/3 of two resources, which makes 2/3 for everybody. On a similar note, some participants rejected A12, because c 3 gets as much as c 1 and c 2 combined. -Because c 1 and c 2 only want one resource, they should get more of it than c 3 , as c 3 wants both resources. -This option is the result of a simple auction or when all consumers get an equal share of both resources and then trade.

Estimating Greediness (Question 3)

Q3 was designed to collect information on how the greediness of consumers, who served themselves from a pool of common resources, is perceived. The transferability to clouds is evident, because in clouds VMs serve themselves from their host. Moreover, because in flat rate and commodity clouds no payment on a per VM basis occurs, such clouds are also a common resource shared among customers. In addition, insights were collected on how proportionality and value of resource bundles is perceived, when no information about consumers' utility functions is available. Thus, Q3 provides insights on how resources that different VMs on the same host utilize can be compared. Q3 is based on three scenarios S31, S32, and S33, were three consumers c 1 , c 2 , and c 3 had served themselves from a pool of three common resources r 1 , r 2 , and r 3 (like VMs on the same host). To split these resources, each consumer had allocated himself a certain bundle as shown in Table 3. The three consumers had to be ranked according to how their greediness was perceived, all being based on the amounts the consumers had allocated themselves.

Metrics: Many participants tackled Q3 by proposing one of the four metrics discussed subsequently.

Price: The price metric is the simplest metric. The value of one unit of resource r i is defined as p/ ← → r i , where p is a constant and ← → r i is the number of units available of r i . The value of a bundle is the sum of values of its resources. For example, for p = 1 the value of c 2 's bundle in S31 is 2 12 + 1 9 + 5 9 = 5 6 . This metric is equivalent to the sum-based-penalty function presented in [START_REF] Klusáček | Multi Resource Fairness: Problems and Challenges[END_REF].

P×S (Price×Scarcity):

The P×S metric is a natural extension of the price metric. The value of one unit of resource r i is defined as a(r i ) • p/ ← → r i 2 , where a(r i ) is the amount that is allocated in total of r i . The value of a bundle is defined as the sum of values of those resources contained. For example, for p = 1 the value of c 2 's bundle in S31 is 2•10 12 2 + 1•6 9 2 + 5•9 9 2 = 29 54 .

P∩S (Price∩Scarcity):

The P∩S metric is another natural extension of the price metric and defines the value of a resource just as the price metric. However, the value of a bundle is defined only over resources that are depleted, i.e., resources where a(r i ) = ← → r i . For example, for p = 1 the value of c 2 's bundle in S31 is

10 12 • 2 12 + 6 9 • 1 9 + 9 9 • 5 9 = 5 9 .

DRF (Dominant Resource Fairness):

The DRF metric defines the value of a bundle by the L ∞ norm, i.e., by the biggest share of any resource relative to the overall amount of the resource. For example, the value of c 2 's bundle in S31 is max 2 12 , 1 9 , 5 9 = 5 9 . According to this DRF metric, the bundles of c 1 and c 2 in S33 are equally valuable. This tie is broken by the second biggest share in the bundles, wherefore c 1 's bundle is more valuable. Frequency Investigations: For some questionnaire rankings the free text indicated that the participant had assumed real life values of those resources and ranked the consumers accordingly. These rankings as well as incomplete rankings were removed, wherefore the presented results are based 553 answers. Subsequently, consumer rankings are denoted by triplets. For example, the triplet (2,1,3) denotes the first consumer as moderate, the second consumer as most greedy, and the third consumer as least greedy. Figure 1 illustrates for each scenario how many participants selected each ranking and highlights those rankings that correspond to all metrics discussed in Section 3.2. These numbers in Figure 1 allow to compile Table 4 showing for each metric the respective ranking in the three scenarios and by how many participants this ranking was selected. Figure 1 and Table 4 show that the metrics discussed in Section 3.2 cover the majority of participants' rankings. [START_REF] Poullie | Cloud Flat Rates Enabled via Fair Multi-resource Consumption[END_REF] analyses the combinations of rankings over the three scenarios, because these rankings given by most participants did not match the same metric over the three scenarios. This reveals that the most frequent combination was selected by 79 participants, conforming to the DRF metric. The second, third, and fourth most frequent combinations were selected by 55, 43, and 32 participants, conforming to the P×S, Price, and P∩S metric, respectively.

Discussion

Only the first two arguments of the questionnaire's text replies in favor of A12 of the above presented Q1 are correct. The third argument is incorrect, because c 1 receives least of r 2 and c 2 least of r 1 . Therefore, the arguments in favor of A13 are more versatile and sound than those in favor of A12. Because A12 and A13 were chosen by 30.0% and 68.5% of the participants, respectively, it is concluded that A13 determines the intuitively fair allocation.

In Q3, participants who ranked in conformance to the Price and P∩S metrics, stated that they had applied these metrics to arrive at the ranking. In contrast, participants who ranked conforming to the DRF and P×S metrics often argued not in conformance to the respective metric. In particular, for participants ranking in conformance to the DRF metric, only one participant argued in conformance to the DRF metric, while the majority argued that those consumers who exceed their equal share are greedy. Thus, in S31 c 2 is the greediest due to the disproportional consumption of r 3 . Analog, in S32 and S33 c 3 is the greediest, because c 3 exceeds the equal share of r 2 by 50% and c 1 is the second greedy, because c 1 exceeds the equal share of r 1 by 33%. Participants who ranked conforming to the P×S metric mostly argued that the total amount of resources consumed is deceive (the tie of c 1 and c 3 in S33 according to this logic was broken by c 3 's 50% overconsumption of r 2 ). Further details can be found in [START_REF] Poullie | Cloud Flat Rates Enabled via Fair Multi-resource Consumption[END_REF].

Implications for existing metrics: While the metrics discussed in Section 3.2 cover the majority of participants rankings (cf. Table 4 and [START_REF] Poullie | Cloud Flat Rates Enabled via Fair Multi-resource Consumption[END_REF]), none of these metrics captures an intuitive understanding of fairness: The P∩S metric has a low conformance in S32 and S33 and for S33 results in the inverted ranking of S32. The latter implies that consumers can decrease their score by consuming more. This is not only counter-intuitive, but gives the undesirable incentive to consume more than needed. The Price metric has a low conformance in S33 and identifies c 1 as "greediest" in S31, although c 1 does not cause the bottleneck, but precisely sticks to his equal share (a behavior that is considered humble in S32 and S33). The sum-and the root-based-penalty functions, which [START_REF] Klusáček | Multi Resource Fairness: Problems and Challenges[END_REF] identifies as best metrics, result in the same rankings as the Price metric and, therefore, are also not satisfactory. Similar arguments hold for the P×S metric.

The DRF metric is satisfactory at a first glance: For all three scenarios of Q3 it results in the most frequent ranking and also in the most frequent combination of rankings (cf. Table 4 and [START_REF] Poullie | Cloud Flat Rates Enabled via Fair Multi-resource Consumption[END_REF]). However, only one participant argued according to DRF, while the majority argued that those who exceed their equal share are greedy. Therefore, the high conformance of DRF stems rather from the fact that every consumer exceeds the equal share on at most one resource (because DRF only considers these resources, this allows DRF to produce good results). Table 5 shows an allocation that proves that DRF's approach to ignore all but one resource can lead to undesirable results. For the depicted allocation, all other metrics discussed in Section 3.2 give the inverse ranking of DRF. Also, according to the arguments made by the participants, the DRF ranking is unfair: DRF classifies c 1 as the consumer with the most valuable bundle, although c 1 only receives the least loaded resource. c 3 cedes no resource at all and receives most of the only scarce resource, but DRF classifies c 3 as most humble. Also, Q1 of the questionnaire identified A13 as the intuitively fair allocation, while the DRF-fair allocation is A12. Because Leontief utility functions are assumed in Q1, i.e., resources are required in static ratios, and DRF is defined based on this assumption, DRF should result in an intuitively fair allocation. Therefore, while DRF is often applied, when Leontief utility functions do not hold, Q1 shows that already for Leontief utility functions, DRF may result in allocations that are not intuitively fair. Moreover, consumers and resources can be added to this scenario, where consumer c i requests only resource r i (and as before one consumer requests all resources evenly). Thereby, the perceived unfairness of DRF can be increased arbitrarily, because the consumer requesting all resources receives as much as all other consumers combined.

Due to these shortcomings of all metrics presented so far, the new Greediness Metric (GM) was developed. This GM is aligned with arguments of this discussion and, thus, (i) classifies A13 in Q1 as the most fair allocation, (ii) results in the most frequent ranking for each of the three scenarios in Q3, (iii) gives the "correct" ranking for the allocation in Table 5, and (iv) captures an intuitive understanding of fairness, which allows defining attractive cloud flat rate models.

Greediness Metric

The Greediness Metric (GM) maps each resource bundle in an allocation to a rational number that can be associated to the greediness of the consumer, who served himself the bundle. In that sense this GM serves the same purpose as the other metrics presented in Section 3.2, which quantify the value of a bundle. As the most frequent textual comments of the questionnaire suggest, the GM sums up, what exceeds the equal share in each bundle. However, it also deducts what is not consumed of the equal share but handed over to other consumers instead.

Let R = (r 1 , r 2 , . . . , r m ) be a set of m resources, where resource r i ∈ R is available in the amount of ← → r i . An allocation of R to n consumers (c 1 , c 2 , . . . , c n ) can be denoted by a matrix A ∈ R m×n ≥0 with n j=1 a ij ≤ ← → r i , for all i ∈ {1, 2, . . . , m}, where c j receives amount a ij of r i . The amount of r i that c j receives beyond his equal share is then a ij -← → r i /n (if the difference is negative, c j does not utilize its entire equal share of the resource).

If a ij > ← → r i /n, consumers other than c j have to cede some of their equal share of r i in order to enable c j 's share of r i . Therefore, the amount by which c j exceeds his equal share is added to the greediness of c j .

If a ij = ← → r i /n, c j exactly receives his equal share, wherefore it does not change c j 's greediness. In particular, if a ij = ← → r i /n for all i ∈ {1, 2, . . . , m}, c j 's greediness is zero. If a ij < ← → r i /n, c j 's cession of r i is credited to c j , i.e., subtracted from c j 's greediness, to the extent that other consumers profit from this cession, which is the case, when they utilize r i beyond their equal share. This extension not only depends on how much of r i is utilized beyond the equal share by other consumers, but also on how much of r i is ceded by other consumers. Therefore, the credit factor for the cession of r i is the ratio of what is ceded of r i to what is consumed beyond the equal share of r i . To capture this notion formally, the sum of what consumers receive beyond and cede of their equal share of r i is defined by α(r i ) and β(r i ), respectively. Therefore,

α(r i ) := n j=1 max 0, a ij -← → r i /n and β(r i ) := n j=1 max 0, ← → r i /n -a ij .
Multiplying the amount that c j cedes of r i with α(r i )/β(r i ) implements the considerations above. Therefore, the greediness of c j is defined as

g(c j ) := m i=1 o(i, j) • n/(m • ← → r i ), (1)
where o(i, j) is the offset for c j 's consumption of r i and defined as

o(i, j) := a ij -← → r i /n if a ij ≥ ← → r i /n, γ • α(ri) β(ri) • a ij -← → r i /n else. (2)
Note that, if β(r i ) = 0, no consumer cedes r i and, therefore, the else-part of Equation 2 is never reached (thus, no division by zero occurs). The factor n/(m • ← → r i ) in Equation 1 normalizes resource units. [START_REF] Poullie | Cloud Flat Rates Enabled via Fair Multi-resource Consumption[END_REF] discusses (i) the choice of this normalization factor in detail, (ii) detailed examples for the calculation of the GM, and (iii) how the GM is applicable to scenarios, where consumers have different endowments (instead of every consumer having an endowment of ← → r i /n). The parameter γ defines how strongly the ceding of resources is credited and, thereby, fine-tunes the greediness metric to best comply with the questionnaire results. Table 6 shows the results of the GM dependent on γ for the questionnaire's scenarios. As the table shows, already without the parameter γ (or, equivalently, γ = 1), the GM complies with results of Q1 and S31. However, for S32 and S33, the GM results in the ranking (3,2,1) (cf. Table 6), while the ranking most frequently selected by the participants is (2,3,1) (cf. Table 4). This mismatch for γ = 1 can be explained as follows: In S32 and S33, c 1 exceeds the equal share of r 3 by 33% but also cedes 50% of r 2 to c 3 , while c 2 is "neutral". Thus, while c 2 's greediness is zero independent of γ, c 1 has a negative greediness for γ = 1, i.e., for γ = 1, the GM ranks c 2 greedier than c 1 . However, most participants rated c 1 greedier than c 2 , because c 1 over-consumes r 3 while c 2 never exceeds the equal share. Accordingly, γ ∈ [0, 1] regulates how strongly the ceding of resources is credited (in addition to the dynamic regulation by α(ri) β(ri) ), where, the smaller γ is chosen, the harder it gets to compensate for exceeding the equal share. [START_REF] Poullie | Cloud Flat Rates Enabled via Fair Multi-resource Consumption[END_REF] shows that for γ ∈ ] 1 4 , 2 3 [ the GM perfectly complies with the questionnaire results and Table 6 lists that γ = 0.5 is an appropriate choice.

Conclusions and Future Work

Multi-resource fairness for clouds was so far not defined satisfactorily. Therefore, the Greediness Metric (GM) was defined and verified via a questionnaire among more than 600 participants. The GM defines an intuitive understanding of multi-resource fairness without access to utility functions. This questionnaire also revealed that DRF, which is the state-of-the-art in data center fairness, not always conforms with an intuitive understanding of fairness. Because the GM's definition is based on arguments of non-technical participants, it is intuitively comprehensible. This intuitive definition of cloud applicable fairness, allows for the design of attractive cloud flat rates. In particular, the telecommunications sector has shown that customers often prefer flat rates. Also private/commodity clouds are a perfect use case for the GM, as here no service level agreements guide the resource allocation making fairness an important allocation goal.

In addition to its intuitiveness, the GM is also well suited to be integrated into cloud sharing schemes, because the GM provides the right incentives to chose the configuration of a VM, such that it matches the VM's subsequent load: When a VM tries to exceed the resources it is configured with, it will receive them, if available. However, the customer's greediness increases with a potentially negative effect on other VMs of this customer. Because a customer's greediness only decreases, when resources that his VMs do not utilize are utilized by other VMs, it is not guaranteed that idle resources are credited to the consumer. Therefore, under-as well as over-provisioning VMs is costly. No metric known today (including those in Section 3.2) provides this incentive mechanism.

The GM is currently being evaluated within two different settings: the first setting allows for an evaluation of the GM under idealistic conditions to conclude on the effect of different design aspects, e.g., the function to aggregate the VM greediness to customer greediness. The second setting defines a CloudSim [START_REF] Calheiros | CloudSim: A Toolkit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[END_REF] extension, which allows for evaluating the GM under realistic conditions in operation. In turn, the implementation to integrate the GM fairness mechanism into OpenStack [START_REF] Jackson | OpenStack Cloud Computing Cookbook[END_REF] is ongoing.

Fig. 1 :

 1 Fig. 1: Ranking Frequencies (represented by triplets) in Q3 scenarios.

  1,3): 52.7% (2,3,1): 36.8% (2,3,1): 37.7% Price (1,2,3): 38.0% (1,3,2): 35.5% (1,3,2): 22.5% P×S (1,2,3): 38.0% (1,3,2): 35.5% (2,3,1): 37.7% P∩S (2,1,3): 52.7% (3,2,1): 22.5% (1,2,3): 13.4%

Table 1 :

 1 Comparison of related approaches.

	App.	Fairness	Area	Utility Function
	DRF	Max-min for L∞ norm	Scheduling	Leontief
	[4]	Proportional Fariness	Scheduling	Leontief
	BBF Equal share on a bottleneck	Scheduling	Perfectly complementary
	[28] Envy free and Pareto efficient Micro resources	Cobb-Douglas
	[17]	Priority based on metrics	Scheduling	Not needed
	GM	Based on questionnaire	Runtime	Not needed

Table 2 :

 2 The four Allocation Options A11, A12, A13, and A14.

Table 3 :

 3 The three Scenarios S31, S32, and S33.

Table 4 :

 4 Percentages of most frequent rankings in Q3.

Table 5 :

 5 A problematic DRF ranking.

		r1 r2 r3 Price P×S P∩S DRF
	available 30 30 30
	c1	18 0 0 1.80 1.68 0.00 0.60
	c2	0 14 17 3.10 3.04 1.40 0.56
	c3	10 16 12 3.80 3.69 1.60 0.53

Table 6 :

 6 GM results for Q1 and Q3 of the questionnaire.


Radu Carpa
email: radu.carpa@ens-lyon.fr

Olivier Gluck
email: olivier.gluck@ens-lyon.fr

Laurent Lefevre
email: laurent.lefevre@inria.fr

Jean-Christophe Mignot
email: jean-christophe.mignot@ens-lyon.fr

Improving the Energy Efficiency of Software Defined Backbone Networks

The continuous growth of traffic and the energy consumption of network equipments can limit the deployment of large-scale distributed infrastructure. This work 1 aims to improve the energy efficiency of backbone networks by dynamically adjusting the number of active links according to network load. We propose an intra-domain Software Defined Network (SDN) approach to select and turn off a subset of links. The SPRING protocol (a.k.a. Segment Routing) is used to make our algorithms converge faster. The algorithms -implemented and evaluated using the OMNET++ discrete event simulator -can achieve energy savings of around 44% when considering real backbone networks. energy efficiency backbone networks SDN traffic engineering SPRING segment routing MPLS

I. INTRODUCTION

Networks are essential to today's highly instrumented and connected society. Currently responsible for a fraction of the energy the IT sector consumes, networks rely on equipments that often use a constant amount of power regardless of their utilisation; a worsening scenario as traffic is expected to increase by a factor of three in the next few years [START_REF]Cisco vni global mobile data traffic forecast[END_REF]. Backbone or core networks for instance, employ devices that consume several kilowatts of power even when idle.

Several techniques have been proposed for reducing the energy consumed by backbone networks, including traffic rerouting and using low power consumption modes. By rerouting data over alternative paths it is possible to offload a subset of links, or make them completely idle since operators generally over-provision their networks in order to handle peak-demands and provide clients with high Quality of Service (QoS). Evidence shows that even during peak hours many links are rarely used more than 50%. Figure 1 depicts the link utilisation computed from traffic matrices of the Géant network 2 , where most links are less than 25% utilised even at peak hours.

This work tackles the challenge of reducing the energy consumed by backbone networks by changing the status of router ports and transponders on the extremities of links. The status of these components is set to sleep mode whenever a link is not used for transferring data, and they are brought back to operational state when required. This process of activating Fig. 1: Link loads in the Géant network. and deactivating network links is also termed as switching links on and off respectively.

Existing work seeks to adjust the number of active links according to the amount of traffic in the network, but they are mostly solutions at the conceptional level. They search to minimise the number of active links via solving Mixed-Integer Linear Programming (MILP) formulations or by employing heuristics without considering implementation details, and they often ignore race conditions. We perform SDN-based traffic engineering and take into account several aspects of designing energy-efficient traffic engineering in core networks. We implemented the proposed solution using the OMNET++ packet-based discrete event simulator. Unlike existing work that uses IP link weights or Multiprotocol Label Switching (MPLS) with Resource reSerVation Protocol Traffic Engineering (RSVP-TE) for rerouting traffic, we use a new protocol called Source Packet Routing in Networking (SPRING). In addition to making the implementation easier, SPRING is well suited for dynamic reconfiguration of a network.

Our solution is provided as a framework named Seg-menT Routing based Energy Efficient Traffic Engineering (STREETE), which offers an online method for switching links off/on dynamically according to the network load [START_REF] Carpa | Segment routing based traffic engineering for energy efficient backbone networks[END_REF]. This generic and extensible framework allows for incremental enhancements, such as providing guarantees and more intelligent flow placement computations by simply updating the employed algorithms. Experiments considering real network topologies and dynamic traffic matrices allowed us to determine the trade-off between energy savings and the impact of our solution on network performance. This paper extends these initial results by providing a more extensive analysis of our framework considering dynamic aspects of a network and its evolution, and by relaxing some of the assumptions of our previous work. For instance, the number of interconnected data centres is expected to increase over time, we include experiments where we do not assume a diurnal traffic pattern and where the access nodes can be nearer the backbone.

The rest of this paper is structured as follows. Section II discusses related work, whereas Section III describes our assumptions and concepts such as SDN and segment routing. Our solution is presented in Section IV and the result analysis in Section V. Section VI describes ongoing work and finally, Section VII concludes the paper.

II. RELATED WORK

Gupta et al. [START_REF] Gupta | Greening of the internet[END_REF] were among the first to consider setting network interfaces to sleep mode to save energy. In backbone networks, however, links cannot be switched off easily without incurring data loss. Bolla et al. [START_REF] Bolla | Energy efficiency in optical networks[END_REF] have shown that even micro-second interruptions are difficult to achieve due to the small packet inter-arrival time. To cope with this challenge, Nedevschi et al. [START_REF] Nedevschi | Reducing network energy consumption via sleeping and rate-adaptation[END_REF] considered the transmission of data in bursts; nearly impossible to achieve under modern 100Gbps networks because very large buffers are needed to temporarily store packets.

A distributed network-wide solution has been provided by Vasić et al. [START_REF] Vasić | Energy-aware traffic engineering[END_REF] for changing flow paths and thus reduce link utilisation, allowing up to 21% of links of real networks to be put into sleep mode. Such a solution, however, is a concept whose implementation is not fully disclosed. Another distributed approach considers that every node locally monitors the utilisation of adjacent links and decides whether to switch them off [START_REF] Bianzino | Grida: A green distributed algorithm for backbone networks[END_REF]. Machine learning mechanisms are used to avoid switching off links that have previously caused congestion. Such a solution relies heavily on the Interior Gateway Protocol Traffic Engineering (IGP-TE) extensions, and after a detailed analysis, we observed that its communication overhead is highly underestimated. In a 30-node network authors estimate that Open Shortest Path First Traffic Engineering (OSPF-TE), the protocol used by their solution, floods the network six times per second. The proposed algorithm adds a couple more flooding per minute. However an analysis of OSPF-TE [START_REF] Salsano | Traffic engineering with ospf-te and rsvp-te: Flooding reduction techniques and evaluation of processing cost[END_REF] revealed that flooding will happen only once every ten seconds even under stress traffic patterns with lots of variations. After correcting the assumptions, the obtained overhead of 0.52% will increase resulting in a 30% improvement of OSPF-TE flooding, which is non-negligible as flooding is costly both in number of required messages and processing demands.

Another proposed centralised solution using MPLS and RSVP-TE [START_REF] Zhang | Greente: Power-aware traffic engineering[END_REF] relies on estimation of traffic matrices, which later was proven inefficient [START_REF] Gunnar | Traffic matrix estimation on a large ip backbone: A comparison on real data[END_REF]. Authors also provide a hybrid solution where MPLS and RSVP-TE are used in parallel with shortest path routing. Our work uses the SPRING protocol with the same advantages, but with less complexity.

III. ASSUMPTIONS AND BACKGROUND

We consider that the workload in a backbone network has slow variation and follows a diurnal pattern due to a high level of flow aggregation, as presented by Juva et al. [START_REF] Juva | Traffic characterization for traffic engineering purposes: analysis of funet data[END_REF]. Table I provides figures on the power consumed by backbonenetwork devices as described in previous work [START_REF] Van Heddeghem | Power consumption modeling in optical multilayer networks[END_REF]. Our model considers that switching off a port corresponds to powering off part of its integrated circuits and the transponder. Switching off link hence means powering off its two extremities. For instance, if a 100Gbps link is switched off, 2 × (135 + 150) = 570 Watts are saved. In a core network with links of hundreds of Gbps, a short failure may incur the loss of hundreds of gigabytes of data. Although we do not address protection issues in this paper, our solution never disconnects the network and guarantees the availability of a working path between any pair of nodes. The term Connectivity Constraint is hereafter used to refer to this guarantee.

Our solution works at the electronic level and does not change wavelength paths in the optical domain. Only extremities of optical links are turned off/on; that is, the transponders and the port cards of the IP router.

A. Software Defined Network

In traditional networks nodes contain both control and data planes, and enforcing network-wide policies often requires access and configuration of all devices. SDN aims to simplify management by separating control and data planes. The control plane retains the network intelligence for calculating paths for data flows and for programming them into the data plane. In a network device, packets that arrive through an incoming port are forwarded by the data plane to the right outgoing port. Henceforth data-plane devices are referred to as SDN switches.

SDN controllers enable a lot of flexibility when it comes to traffic engineering. They maintain and exploit network-wide knowledge in order to execute all required computations and use a predefined API for applying changes to SDN switches. In this work, we use an SDN solution. The SPRING protocol is used as data plane by the SDN controller.

B. SPRING protocol SPRING [START_REF] Filsfils | Segment routing architecture[END_REF], also known as Segment Routing, is currently an IETF draft started in 2013 that aims to replace MPLS+RSVP-TE for traffic engineering. It combines the power of source routing, allowing for flexible traffic engineering, with shortest path routing, which requires less signalling or header overhead.

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

• A nodal SID is globally unique and identifies a node (a, b, c, ..., h). • An adjacency SID is local to a node and identifies an outgoing interface (node b has the adjacency SIDs L1, L2, L3, L4 and L5). After network discovery, sending a packet to node a through the shortest path requires encapsulating it into a packet with destination a. Unlike in IP, much more flexible traffic engineering is possible:

• If node h wants to send a packet to node a while forcing it over link L1, it adds the header [b, L1] (Figure 2b). • If h wants to send a packet to a via f (Figure 2c), it uses the header [f, a]. Being a source routing protocol, SPRING enables fast flow setup and easy reconfiguration of virtual circuits with minimum overhead since changes must be applied only to the ingress devices. No time and signalling are lost re-configuring the midpoint devices.The policy state is in the packet header and is completely virtualized away from midpoints along the path. This means that a new flow may be created in the network by contacting only one network device: the ingress router. This comes in contrast with OpenFlow where the forwarding tables of all the devices along the path must be reconfigured. The agility in updating the paths of flows is essential in solutions that intend to perform link switch-off and improve energy efficiency.

Moreover, the label switching proved itself very efficient in backbone networks. For example, MPLS is the only forwarding protocol supported at full link speeds by Juniper PTX Series core routers.

IV. THE STREETE FRAMEWORK

This section provides a formal description of the energyefficient traffic engineering problem. It divides the overall problem into sub-problems for easier discussion and then presents an analysis of centralised and distributed solutions. Finally, we present details of our solution.

A. Steps of STREETE Algorithm

The problem of energy-efficient traffic engineering can be divided into the following three steps:

• Selecting links to switch off/on: this step selects candidate links to be switched off/on and is referred to as Select-LinksToOff/On. • Computing new routes to avoid/reuse links: prior to switching off/on the links selected by SelectLinks-ToOff/On, the algorithm must compute new paths for the flows traversing the network. Switching off a subset of links reduces network capacity, and thus flows must be intelligently rerouted to avoid congestion. In fact, congestion may occur even when a turned-on link provides a better path for a large number of flows. We refer to this step as ComputeNewRoutes. • Rerouting and switching off/on the links (RerouteAnd-SwitchOff/On): once new routes for flows are computed, the decision must be enforced on the network devices. This step triggers rerouting and the actual link switchoff. Algorithm 1 illustrates how the steps above fit together. The algorithm searches for links that can be switched on or off, and after that, executes RerouteAndSwitchOn or RerouteAnd-SwitchOff.

B. Centralised versus Distributed Approaches

There is often a divergence of opinions in the literature with respect to centralised and distributed approaches. Before implementing our solution, we compared the two approaches. We present here the conclusions after analysing each step of STREETE under centralised and distributed settings.

a) SelectLinksToOff/On:: Distributed approaches do not allow for optimising this step. There are essentially two ways to choose the links for switch-off; either each node independently decides to switch off a directly attached link, or a coordination between nodes is used to elect a link. Under the former, special measures must be taken by RerouteAndSwitchOff to ensure that the Connectivity Constraint is respected. As a result, coordination between nodes is necessary in both cases. Distributed N to N coordination means flooding the network with control messages, known to be costly in the IGP protocols. In contrast, a centralised solution can take complex decisions after collecting and analysing the traffic matrices, requiring only an N to 1 communication. b) ComputeNewRoutes:: In a distributed solution every node must calculate its own routes. From a computational complexity perspective, this is better than having a unique entity calculating all routes for the entire network domain. However, missing information about global network state can limit the optimisation of route selections. Although it is possible to distribute this information across all nodes, the information can take minutes to converge [START_REF] Salsano | Traffic engineering with ospf-te and rsvp-te: Flooding reduction techniques and evaluation of processing cost[END_REF], which can in turn result in long periods of network instability. Distributed solutions are limited to reactively rerouting the flows to avoid disabled links. A resource reservation protocol may be used to reserve new paths and avoid network congestion. However, the use of such protocol increases the time needed to setup the flows and reduces the network convergence speed.

Better energy efficiency and congestion avoidance are possible under centralised solutions. Centralised solutions can compute new routes by collecting traffic matrices and using them to solve either an approximation of the "Multicommodity Flow Problem" in order to optimise the distribution of load, or a K-shortest-path problem to optimise delay. c) RerouteAndSwitchOff/On:: When considering a distributed scenario, nodes need to synchronise their actions in order to avoid switching off a set of links that can disconnect the network. This risk is minimised when a central entity takes all decisions on links to switch off; it does not risk to switch off simultaneously two badly chosen links and violate the Connectivity Constraint.

Networks are increasingly relying on centralised architectures, with SDN becoming commonplace in many data centres and its use being largely studied in optical networks [START_REF] Liu | Experimental validation and performance evaluation of openflow-based wavelength path control in transparent optical networks[END_REF]. Therefore, we focus on an SDN solution. Although we agree that a distributed solution has the advantage of avoiding a single point of failure, several techniques exist to make SDN more robust [START_REF] Dixit | Towards an elastic distributed sdn controller[END_REF]. We are interested in using SDN for energy efficient traffic engineering, and the controller can be made optional for other operational activities. If the controller becomes unreachable, our solution can turn on the links and rollback to a fully functional distributed network without energy efficiency features.

C. Implementation Details of Each Step

To employ the proposed algorithm, an SDN controller must know the network status. During packet classification ingress routers compute the intensity of inter-domain flows. This data is used by the SDN controller to compute a network-wide traffic matrix.

We implement the "least congested link" technique for SelectLinksToOff as it is the approach against which most of existing work compares their results. First, links are sorted by instant transmission speed; a step whose complexity is

O(E • log(E))
, where E is the number of links (edges). Then the algorithm tries to switch off links that transmit less data by testing, for each link, whether switching it off does not violate the connectivity constraint. It will take at most O(E •(E +V )): E times breadth-first search to test the integrity of the network, where V is the number of nodes (vertices).

For SelectLinksToOn, our algorithm is simple. It tests the utilisation of the most utilised link and if it is above 75%, all links are switched on and the shortest path routes are recalculated.

ComputeNewRoutes uses a technique that computes the allpairs shortest path routes and tests the possibility to route all the available traffic over these paths. The computational complexity is O(V • (E + V • logV )) if Dijkstra from every node is computed. The complexity may decrease if using an optimised all-pairs shortest path algorithm.

Network links are switched off one by one while no link reaches the threshold utilisation of 60%. If the controller detects that turning off a selected link can increase the utilisation of any other link above 60%, it skips the selected link. When the utilisation of any link exceeds 75%, the network is switched back on.

The steps executed by RerouteAndSwitchOff to actually switch off the links are illustrated in Algorithm 2, where the links between nodes A and B, C and D, etc, were selected for switch-off.

V. PERFORMANCE EVALUATION

In this section, we analyse experimental results from simulations using OMNeT++. First, the simulation parameters are described. Second, a detailed analysis considering a small network is presented. Third, we discuss results on a simulation taking into account two backbone networks with real traffic matrices. Finally, we stress our solution on the Germany 50 network under more aggressive traffic variations. The controller tells every router the new paths to be used for virtual circuits;

3 Every router applies the changes to the forwarding table to reroute traffic over the new paths;

4 4
The controller tells nodes adjacent to links (A,B,...) to turn them off;

5 5
Nodes A,B,C,... ACK to the controller ;

6 6
The The experimental results reported in this work consider two real networks, namely Géant and Germany 50, depicted in Figure 3 and summarised in Table II. The centralised SDN solution was implemented in the OMNet++ discrete-event simulator. The implementation includes a draft version of the SPRING protocol used to dynamically reroute data in the network avoiding switched-off links. We prefer SPRING over the commonly used MPLS with RSVP-TE solution because the latter faces convergence issues under a large number of LSPs [START_REF]The ietf mailing list, motivation for benchmarking mpls-te convergence[END_REF]. With small numbers of virtual tunnels and the "refresh reduction" extension for RSVP-TE, the risk is small, but in our case we need a full mesh of virtual tunnels in order to reroute all flows when switching off links. Moreover, by switching off links we increase the load of a subset of routers and the number of LSPs they manage. SPRING is designed to be stable under a larger number of dynamically changing LSPs.

TABLE II: Evaluated network topologies.

Network

Number of nodes

Number of links Géant (Figure 3b) 22 * 36 Germany 50 (Figure 3a) 50 88

* the New York node is not shown in Figure 3b, but the two links connecting it to the network are visible.

We used the OMNet++ UDPBasicApp module to generate continuous traffic flows of a desired intensity. One flow is generated for each source-destination pair, hence resulting in V 2 flows, where V is the number of nodes. For real backbone networks, the intensity of flows corresponds to the real values found in the traffic matrices obtained from SNDLib3 , scaled up to represent today's faster network speeds. SNDLib contains snapshots of traffic matrices computed at fixed intervals of five minutes. As a result, the matrices lack detailed information about traffic variations within each five-minute period. As we are interested in traffic variations, we compressed every fiveminute interval into two seconds of simulation. Hence, we are able to reduce the time needed to run the simulations and simulate high network speeds.

In the other two cases, namely the simulation of a small network and the stress test on the Germany 50 network, we inject V 2 flows of identical intensities into the network. We exponentially vary the intensity during the simulation in order to test the solution both on slow and fast traffic variations. We reduced the speed of each link to 100Mbps to reduce the time needed to run a simulation.

In all cases, the propagation delay is time needed for light to travel through the fibre. The distance between nodes is the bird-fly distance as given by Google Maps API. Queuing delay is simulated by OMNeT++.

The SDN controller implemented in OMNet++ uses a custom protocol to communicate with network nodes. All the communication between the controller and the data-plane devices passes through the network. A TCP connection is created between every node and the controller and is influenced by all the turn-on/off operations applied to the network.

B. Validation on a Small Network

Figures 4 and5 provide results on a small network of nine nodes and fifteen links. We observe that the network is smoothly turning the links off until t = 5, at which moment the SelectLinksToOff algorithm detects that it can no longer turn off links without causing congestion. The network is stable until t = 11, when given the decrease in the amount of data transmitted through the network, SelectLinksToOff finds more links to be switched off. At t = 13, the network reaches the state of a spanning tree and no more links can be switched off without violating the Connectivity Constraint. The network remains unchanged until more data is injected and it reaches a state close to congestion at t = 24. The SelectLinksToOn algorithm switches on links in order to offer more capacity in the network.

Performed in parallel with the process above, the Compute-NewRoutes algorithm tries to avoid congestion by rerouting traffic over alternate paths as presented in Section IV-C. Figure 5 shows the state of the router queue for the most congested link. Rerouting the flows does not saturate the network in the periods t ∈ [1 . . . 5] and t ∈ [11 . . . 13]. The reason for saturation at t = 24 is the increase of intensity in the injected flows.

C. Results from Backbone Networks

A day of operation of the two considered backbone networks (i.e. Géant and Germany 50) was simulated. In Figures 6 and7, green lines represent the percentage of links that are left switched on by our algorithm. Using the values of Table I for 100Gbps links, this translates to the energy savings shown in Table III. Fig. 5: Length of the router queue for the link that triggered the turn-on.

1) Energy Consumption: At the beginning of the day, when our algorithm starts to run, both networks switch off links one by one and converge quickly to a spanning tree. Further switch off is not possible without violating the Connectivity Constraint. In the Germany 50 network, we observe a turnon at 23:00h, which is due to a large increase in traffic between two network nodes. We do not know the reason for this unusual increase in the original traffic matrix, but this demand was handled well by our algorithm, which switched on sleeping links and restored the full capacity of the network.

Rerouting data over paths that are not the shortest incurs in load overhead. The overhead of our solution can be viewed in Figures 6a and6b, where the maximum overhead is 18.56%. Even with this overhead, the networks converge to a minimum energy state. Moreover, we observe that even greedy techniques for SelectLinksToOff provide good energy savings due to high over-provisioning of the analysed networks. 2) Impact on End-to-End Delays: Figures 7 shows the impact of our solution on end-to-end delay. For every sourcedestination pair, we calculated the mean end-to-end delay at every hour. The box plots represent the distribution of mean of all pairs during the previous hour. The blue ones describe the delays in the original network and the red ones are the delays in the network with switched off links. We also present the mean delay for cases with switch off and without switch off as continuous lines of the same colours.

In the Germany 50 network, the delay increases by 37% in the worst case, but usually by around 20%. A more interesting result can be seen in the Géant network. While in most cases the delay increases, it can be seen that the maximum outlier suffered a delay reduction. It is due to the minimum hop count shortest path routing. The Géant network has a complex physical topology and it occurs that this routing policy is not well suited. In some cases traffic between two European nodes passes through New York. Turning off the 2 links forced flows to pass through multiple hops, but they remain in Europe.

3) Impact on Packet Loss: The simulation revealed that our algorithms did not cause packet loss. In backbone networks, the aggregated traffic flows do not change fast enough to produce a congestion that can affect our solution since STREETE switches on all the links and serves the increased demand at the smallest sign of congestion.

D. Faster Traffic Variations and Improved Switch-On

In the previous section we observed that the original traffic varies very slowly and that STREETE has more than enough time to react to variations in network load. Moreover, the networks are too over-provisioned and a spanning tree is capable to route all traffic even during peak hours. STREETE hence converges to a stable spanning tree and is very unlikely to ever switch on links in these networks.

In order to stress STREETE, we generate a more aggressive traffic pattern in the Germany 50 network where we exponentially increase the amount of traffic over a forty-second interval. At t = 40, one of the links reaches utilisation close to 1, and then load decreases at the same pace. Figure 8 shows the network load when subjected to the generated traffic. Preliminary tests revealed that an "all-on" strategy for the SelectLinksToOn step does not perform well in terms of energy consumption when subjected to big traffic variations. Among the links which are turned on, some are located far from the region of congestion. As a result, they have a high probability to be switched off again just after being turned on. A link-flap is produced, where links are continuously switched on and off. Therefore, we improved the SelectLinksToOn step of our algorithm by implementing a technique which selects, among the switched-off links, the link that would transport the most data in the all-on network.

Figure 9 summarises the execution with the improved SelectLinksToOn and the modified traffic pattern. It shows the utilisation map of each unidirectional link in the Germany 50 network, where the blue area has utilisation close to 0 and red points present utilisation close to 1. The white line in the right-hand side figure represents the limit between the links which are on an those that are off. As all links have the same speed, the percentage of energy savings follows the percentage of the switched off links, namely 39.7% on average.

Our solution progressively switches on links as load increases between t = 0 and t = 40. STREETE reacts with a small delay of approximately 2 seconds; the time needed for traffic matrices to be collected from all nodes and to detect the changes in network load. The algorithm switches off the links again when load decreases. Some links are left off even at the peak load. It is because they are located at the border of the network and transport a small number of packets. Turning them on does not have any impact on the load of the congested links (the links with utilisation greater than 75%).

Figure 10 shows the impact of STREETE on packet loss. The traffic injected into the network doubled between t = 30 and t = 40. There is a noticeable increase in the number of lost packets, especially at t = 40, when the initial network was already saturated. This increase is due to the two-second delay between the increase of network load and the moment STREETE reacts by switching on the links. With STREETE, the packet loss on the most congested link is 7.6% at t = 40.

VI. OUTGOING WORK

As described earlier, STREETE uses a very conservative approach to deal with congestion, which consists in switching all links back on at the smallest sign of congestion. Although this may look efficient from a QoS point of view -as it minimises the risks of overloading the network, increasing delays and losing packets -it may not be the best solution from an energy efficiency perspective. We are therefore working on algorithms for choosing links to switch on; algorithms that consider several aspects such as load decrease resulting from switching on a link, improvement of end-to-end delay, among other factors. Although the choice of links to switch on under congestion may look simple at first, it is challenging as it may require maintaining information about the network status during previous steps of link switch-off and, when possible, determining a previous stable state to which to roll back.

Moreover, we are working on implementing an SDNbased prototype using the Open Network Operating System (ONOS) 4 SDN controller for flow routing and switch on/off decisions. As data-plane devices we use both software switches in Mininet5 , and FPGA-based custom switches on a NetFPGA 10G infrastructure; whose cards are equipped with four 10Gbps Ethernet interfaces, a Xilinx Virtex 5 FPGA and additional hardware provided for prototyping and testing network protocols 6 . A subset of the SPRING protocol is being implemented.

VII. CONCLUSIONS

In this work, we designed an energy-aware traffic engineering technique for reducing energy consumption in backbone networks. Energy efficient traffic engineering was analysed in previous work, but none addressed implementation challenges of their solutions. We showed that ignoring to test the feasibility of techniques can lead to bad estimations and unstable solutions. We proposed and implemented a working prototype in the OMNET++ simulator.

Networks are progressively using centralised architecture and SDN is increasingly utilised in data centre networks. We believe that SDN may be extended to backbone networks. The implemented solution shows that SDN may also be a good means for reducing the energy consumption of network devices.

Compared to previous work, in this paper we used the SPRING protocol to improve the stability of energy efficient traffic engineering solutions. To the best of our knowledge, this is the first work proposing the use of SPRING to improve the energy efficiency of backbone networks. The flexibility of this routing protocol is well suited to frequent route changes that happen when we switch links off and on. Moreover, this protocol can be easily applied to SDN solutions.

Using simulations, we showed that as much as 44% of links can be switched off to save energy in real backbone networks. Even greedy techniques can easily approach the maximum reduction in the amount of energy consumed. In fact, the bottleneck in terms of energy efficiency in energy-aware traffic engineering is the connectivity constraint.

We performed a stress test of our solution under rapidly increasing traffic patterns and showed that more work must be

3 if 7 if 1 :

 371 1 while Energy Efficient Traffic Engineering is active do 2 List-Of-Links = SelectLinksToOn(); ComputeNewRoutes(All-links-that-are-ON ∪ List-Of-Links) then 4 RerouteAndSwitchOn(List-Of-Links); ComputeNewRoutes(All-links-that-are-ON \ List-Of-Links) then 8 RerouteAndSwitchOff(List-Of-Links); Main loop.

Fig. 2 :

 2 Fig. 2: SPRING protocol.

Data:

  List-Of-Links:[(A-B),(C-D),...] and the new routes / * given by <SelectLinksToOff> and <ComputeNewRoutes>

Fig. 3 :Fig. 4 :

 34 Fig. 3: Considered network topologies.

Fig. 6 :

 6 Fig. 6: Impact on link loads.

Fig. 7 :

 7 Fig. 7: Impact on end-to-end delay, Germany 50 (top) and Géant (bottom).

Fig. 8 :

 8 Fig. 8: Generated load and overhead of STREETE.

Fig. 9 :

 9 Fig. 9: Links utilisation without and with STREETE.

Fig. 10 :

 10 Fig. 10: Packet loss.

TABLE I :

 I Power consumption of router ports.

	Port Speed	Consumption (W)
	(Gbps)	Port card Transponder
	10	10	50
	40	35	100
	100	135	150
	400	335 *	300 *
	* mathematical projection

TABLE III :

 III Energy savings during the simulated day.

	Network	Average off time of links	Energy economy (kWh)
	Géant	14.88 out of 36	204
	Germany 50	38.18 out of 88	522

This work has been done as part of the CHIST-ERA STAR "SwiTching And tRansmission" European project (http://www.chistera.eu/projects/star).

http://www.geant.net

http://sndlib.zib.de/

http://onosproject.org/software/

http://mininet.org/

http://netfpga.org