Ashwin Rao
email: ashwin.rao@inria.fr

Arnaud Legout
email: arnaud.legout@inria.fr

Bruno Cessac
email: bruno.cessac@inria.fr

Walid Dabbous
email: walid.dabbous@inria.fr

Floor the Ceil & Ceil the Floor: Revisiting AIMD Evaluation

Keywords: AIMD, Sensitivity, Fairness, Efficiency, Integer Arithmetic

Additive Increase Multiplicative Decrease (AIMD) is a widely used congestion control algorithm that is known to be fair and efficient in utilizing the network resources. In this paper, we revisit the performance of the AIMD algorithm under realistic conditions by extending the seminal model of Chui et al. [6]. We show that under realistic conditions the fairness and efficiency of AIMD is sensitive to changes in network conditions. Surprisingly, the root cause of this sensitivity comes from the way the congestion window is rounded during a multiplicative decrease phase. For instance, the floor function is often used to round the congestion window value because either kernel implementations or protocol restrictions mandate to use integers to maintain system variables.

To solve the sensitivity issue, we provide a simple solution that is to alternatively use the floor and ceiling functions in the computation of the congestion window during a multiplicative decrease phase, when the congestion window size is an odd number. We observe that with our solution the efficiency improves and the fairness becomes one order of magnitude less sensitive to changes in network conditions.

INTRODUCTION

The Additive Increase Multiplicative Decrease (AIMD) [START_REF] Jacobson | Congestion Avoidance and Control[END_REF] is the most popular congestion control algorithm because of its excellent trade-off between fairness and efficiency unlike other algorithms such as additive increase additive decrease (AIAD), multiplicative increase multiplicative decrease (MIMD), and multiplicative increase multiplicative decrease algorithm (MIAD), as shown by Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF].

Despite the popularity of their model, Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] acknowledge that it cannot be used for a realistic performance evaluation of the AIMD algorithm. Their model inherently assumes that each source's reaction to the feedback is instantaneous. They also assume homogeneous round trip times among competing flows; this makes the reaction to the feedback synchronous. Such synchronous and instantaneous reaction to feedback does not exist in real network because real networks consists of flows with different round trip times competing for the bottleneck resource. The round trip times introduces a non zero delay in the time to react to the feedback. The heterogeneity in round trip times also ensures that the reaction to the feedback is asynchronous. Another shortcoming of their model is that they assume that systems implementing AIMD can use real numbers. However, either due to protocol restrictions or due to restrictions imposed by the operating system kernels, developers may be restricted to use only integer variables while implementing the AIMD algorithm.

Additive Increase Multiplicative Decrease (AIMD) [START_REF] Jacobson | Congestion Avoidance and Control[END_REF] is the current congestion control algorithm used in TCP [START_REF] Allman | TCP Congestion Control[END_REF] when losses are used as the signal of congestion. In addition, the AIMD algorithm has been proposed for ICP [START_REF] Carofiglio | Icp: Design and evaluation of an interest control protocol for content-centric networking[END_REF] to regulate the rate of content requests in Content Centric Networks [START_REF] Jacobson | Networking Named Content[END_REF]. We therefore believe that a model to capture the behavior of AIMD under realistic conditions is important and timely.

In this paper, we make the following contributions.

1. We extend the model of Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] to improve its realism by taking into account (a) asynchronous feedback, (b) system variables maintained as integer, and (c) round trip time heterogeneity. We believe this extension can be easily applied to other algorithms such as AIAD, MIAD, and MIMD.

2. We show that the AIMD fairness is highly sensitive to changes in the capacity of the bottleneck and also in the round trip time. We show that the root cause of this sensitivity is the rounding operation performed on the congestion window size during a multiplicative decrease phase.

3. We provide a fix to the implementation of the AIMD algorithm to solve this high sensitivity that (a) improves fairness, (b) reduces the sensitivity of fairness to changes in network conditions by an order of magnitude, and (c) improves the overall efficiency. We also show the perfect compatibility of our solution with current TCP implementation, which makes an immediate and incremental deployment of our solution possible.

The remainder of this paper is structured as follows. We begin by providing a summary of our reference model, the model of Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF], and detail its shortcomings in Section 2. In Section 3, we extend the reference model to abstract realistic conditions that exist in communication networks. We then provide numerical results that highlight issues such as unfairness of AIMD under realistic network conditions. In Section 4, we present our solution to address these issues of AIMD. We also provide supporting numerical results to quantify the benefits of using our solution. We discuss the related work in Section 5 and finally conclude in Section 6.

REFERENCE MODEL

In this section, we present the reference model of Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] and show the need to extend it. We henceforth refer to this model as the reference model.

Model Description

Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] consider a network of n flows that share the service of a single bottleneck of capacity X goal . In a given slot of their discrete time model, each user i generates a load given by x i (t). The total load generated by the n users during the time slot t is

X(t) = i=n i=1 x i (t).
Congestion at the bottleneck (that is X(t) > X goal ) is signaled with a binary feedback y(t) = 1 that indicates users decrease their respective load. Conversely, when there is no congestion (that is X(t) ≤ X goal ), y(t) = 0, which indicates users to increase their load.

In summary, Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] use the following equations to represent the AIMD algorithm.

X(t) = i=n i=1 x i (t), (1)
y(t) = 0 when X(t) ≤ X goal 1 when X(t) > X goal (2)
x i (t + 1) = a I + x i (t) when y(t) = 0 m D x i (t) when y(t) = 1. (3)
In Equation ( 3), a I and m D respectively represent the additive increase and multiplicative decrease components of the AIMD algorithm. In the rest of the paper, unless explicitly specified, we consider the most popular values of a I = 1 and m D = 0.5 [START_REF] Allman | TCP Congestion Control[END_REF][START_REF] Floyd | Equation-based congestion control for unicast applications[END_REF][START_REF] Jacobson | Congestion Avoidance and Control[END_REF].

Shortcomings of the model

The important shortcomings of this model are as follows.

1. The model assumes that each flow has the same fixed round trip time.

2. As a consequence, all users get notified of a congestion event in the same time slot, that is end-users reaction to a congestion is synchronous.

3. The load generated by each flow is assumed to be a floating point number (see Equation ( 3)).

However, there is a high round trip time heterogeneity in the Internet leading to asynchronous feedback loops. In addition, integer variables are used in AIMD algorithm implementations either because of protocol restriction [START_REF] Carofiglio | Icp: Design and evaluation of an interest control protocol for content-centric networking[END_REF] or because popular kernels, such as the Linux kernel, strongly recommend against using floating point operations in the kernel [7]. We believe considering integer variables is important because the multiplicative decrease operation performed using integers introduces rounding errors whose impact on the performance of AIMD is not known.

We would like to point out that though Linux and BSD implementations maintain the TCP congestion window as integer variables, the units used by these kernels differ. The BSD kernel maintains the congestion window as bytes while the Linux kernel maintains the congestion window as full sized segments. The IETF RFC for TCP [START_REF] Allman | TCP Congestion Control[END_REF] suggests keeping the congestion window in bytes, however, it acknowledges that some implementations maintain the window in units of full sized segments or packets; this RFC also acknowledges the use of integer arithmetic while performing the multiplicative decrease. We shall later see the impact of using packets instead of bytes.

In summary, in this section, we described the reference model of Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] and highlighted its shortcomings. In the next section, we present an extension to address the shortcomings.

EXTENSION TO REFERENCE MODEL

In this section, we first present our extension to the reference model. We then present the metrics we use for the numerical resolution of our reference model. Finally, we analyze the numerical resolution and identify the root cause of a high sensitivity of the AIMD algorithm to network conditions.

Description of Extension

We now extend the reference model to address its shortcomings. To take into account the notion of round trip time, we assume that the load generated by the i-th source remains in the system for a round that lasts for a duration of d i slots; we call d i the round duration of the i-th user. For our analysis we assume that the round duration of each user is fixed Figure 1: Numerical resolution of a system of three flows with round duration of 10, 11, and 13 slots when X goal = 12.We observe that the flows respond asynchronously to the feedback.

round, the i-th user updates its load depending on the feedback received during the last round of d i slots. The i-th user increases its load only if the system was not overloaded during the last round.

Our extension to the reference model keeps Equation (1) and Equation ( 2) and modifies Equation (3) as follows.

x i (t + 1) =                  x i (t)
when t ≡ 0(mod d i ) (4a)

a I + x i (t)
when t ≡ 0(mod d i ) and

d i -1 j=0 y(t -j) = 0 (4b) max(⌊m D x i (t)⌋ , 1) otherwise (4c)
In this extension, Equation (4a) abstracts the notion of round trip times per flow, Equation (4b) and Equation (4c) ensure that the response time to a congestion notification is a function of the round duration (d i ); thus the flows react to a congestion asynchronously. Equation (4c) restricts the minimum load to be 1, the smallest non zero integer; similar restrictions exist in TCP [START_REF] Allman | TCP Congestion Control[END_REF]. For example, the following code snippet shows that the TCP implementation in Linux kernel version 3.5.2, one of the latest kernel versions2 , uses the floor function and restricts the minimum congestion window to at least two TCP segments on a multiplicative decrease.

u32 tcp_reno_ssthresh(struct sock *sk) { const struct tcp_sock *tp = tcp_sk(sk); return max(tp->snd_cwnd >> 1U, 2U); } We would like to point out that our extension can be used for realistic evaluation of other algorithms such as AIAD, MIAD, and MIMD, however in this paper we restrict ourselves to the popular AIMD algorithm.

We now use Figure 1 to validate that our extension indeed addresses the shortcomings presented in Section 2.2. Figure 1 shows the time evolution of the load generated by three flows that share a single bottleneck of capacity X goal = 15. The three flows have a round duration of 10, 11, and 12 slots respectively; all the three flows start with a load of 1. We see that each source updates its load during different time slots. This shows that the reaction to a feedback is asynchronous and that it depends on the round duration. We also see that the flow 1 (d 1 = 10) dominates the other flows. Considering the dominance of flow 1, it is desirable to know if the flows are indeed receiving their fair share and if the system is efficient. In the next section we present the metrics we use to evaluate the fairness and efficiency.

Metrics To Evaluate Performance of AIMD Algorithm

We now present the metrics to evaluate the system performance, and study the trade-off between fairness and efficiency of the AIMD algorithm.

1) Mean Load (x i ). The mean load generated by the

i-th flow is xi = t=T t=1 x i (t) T
, where T represents the total time for which the flow was active. We use the mean load to compute the following metrics.

2) Load Ratio and Sensitivity of Load Ratio. We use the ratio of the load generated by two flows as an indicator of the fairness between these two flows. We compute the load ratio between flow i and flow j as

follows, L ij = xi xj
. By using the technique used by Mathis et al. [START_REF] Mathis | The Macroscopic Behavior of the TCP Congestion Avoidance Algorithm[END_REF], one can show that the desired value of the load ratio is

L ij = d j d i .
In the following, we define the sensitivity of the load ratio to a change in the round duration and in X goal . When all the system variables other than the round duration of flow k are constant, a change in the round duration d k of flow k by ∆d k results in the load ratio between flow i and flow j to be modified by ∆L ij . We define the sensitivity of the load ratio L i,j to the change

in round duration of flow k as | ∆L ij ∆d k |.
Similarly, when all the system variables other than X goal are constant, a change in X goal by an amount ∆X goal results in the load ratio between flow i and flow j to be modified by a value given by ∆L ij . We define the sensitivity of the load ratio L i,j to the change in

X goal as | ∆L ij ∆X goal |.
3) System Efficiency (ρ) and Sensitivity of System Efficiency. We define the efficiency of a system with n flows competing for a bottleneck resource with a capacity X goal to be ρ = n i=1 xi X goal .

In the following, we define the sensitivity of the efficiency to changes in round duration and changes in X goal . When all the system variables other than the round duration of flow k are constant, then a change in the round duration d k of flow k by an amount ∆d k results in the efficiency to be modified by a value given by ∆ρ. We define the sensitivity of the system efficiency ρ to the change in round duration of flow k as

| ∆ρ ∆d k |.
Similarly, when all the system variables other than X goal are constant, then a change in X goal by an amount ∆X goal results in the efficiency to be modified by a value given by ∆ρ. We define the sensitivity of the system efficiency ρ to a change in

X goal as | ∆ρ ∆X goal |.
In summary, we use the load ratio L ij and the efficiency ρ to evaluate the trade-off between system fairness and system efficiency. We use the load ratio and not the Jain fairness index [START_REF] Aggarwal | Understanding the Performance of TCP Pacing[END_REF][START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] for evaluating the fairness because the load ratio gave us a better picture on the sensitivity of fairness. We use the sensitivity of the load ratio and the sensitivity of the efficiency to quantify the system sensitivity to changes in the network conditions. One can also extend this study of sensitivity to changes in the initial conditions of the load generated by the flows. However, based on our results we present in the following section, we believe that the parameters we use give a clear picture of the behavior of the system.

Numerical Evaluation

For the sake of clarity, in this section, we only present results for a network of two flows. We performed numerical evaluation for a network of up to four flows and our conclusions hold for all the different networks we evaluated.

The goal of our evaluation is to assess the impact of integer arithmetic on the fairness and efficiency of an AIMD algorithm. To reach this goal, we compare the numerical evaluation of our model using integer arithmetic with the numerical evaluation of our model using floating point arithmetic, that is Equation (4c) is replaced by x i (t) = max(m D x i (t), 1).

In the following, we start presenting the parameters used for the numerical evaluation of our model, then we discuss its fairness properties and finally its efficiency.

Parameters

In our extension to the reference model, the round duration abstracts the round trip time in communication networks. About 70% of the round trip times observed by iPlane measurements are less than 150 ms [START_REF] Madhyastha | iPlane: An information plane for distributed services[END_REF]. Based on their results, we select the round duration of flow 1, d 1 , in the interval [50, 75] slots, and the round duration for flow 2, d 2 in the interval [25,150] slots.

The load generated by each flow abstracts the notion of congestion window. We now use the following calculations to determine the range of X goal values. Akamai reports that 73% of the global links to Akamai servers have a connection speed of less than 5 Mbps [START_REF] Akamai | The State of the Internet[END_REF]. The

Variable Description n

The number of flows.

d i
The round duration of i-th source.

x i (t)
The load generated by i-th flow.

X(t)

The total load generated by the n flows.

X goal

The capacity of bottleneck resource. y(t)

The feedback.

L ij

The ratio of load generated by flow i and flow j. ρ

The system efficiency.

a I Additive increase component of AIMD m D
Multiplicative decrease component of AIMD same report also mentions that 27% of connections from India to Akamai servers use a link speed of less than 256 kbps. A one way delay of 75 ms (round trip time of 150 ms) for a link speed of 5 Mbps results in a congestion window of 32 packets of 1500 bytes. Therefore, for each pair of (d 1 , d 2 ) we performed numerical evaluations using an X goal in the interval [START_REF] Floyd | On Traffic Phase Effects in Packet-Switched Gateways[END_REF]75].

For our numerical evaluation, we assume that each flow begins with a load of 1. We stop the evaluation after 0.5 * 10 6 slots. In this section, unless explicitly specified we consider a I = 1 and m D = 0.5.

Fairness

Figure 2 shows the impact of integer and floating point arithmetic on the fairness of an AIMD algorithm under realistic network conditions. In this figure, we plot the load ratio for d 1 = 50, d 2 in the interval [50, 100], and X goal in the set 10, 30, 50. The desired value for the load ratio L ij is d 2 /d 1 . However, in Figure 2 (a) we observe that with integer arithmetic the load ratio increments in steps as d 2 /d 1 increases. These steps indicate that one of the two flows gets more than its desired fair share. Furthermore, we observe that the curves differ The maximum load ratio is significantly larger when using integer variables compared to when floating point variables are allowed.

vastly for different values of X goal . We observe that the steps become steeper, indicating a higher unfairness, when X goal is smaller. The explanation is that the steps become steeper because a decrease in the input values for Equation (4c) causes the rounding errors due to the floor function in Equation (4c) to increase. In addition Figure 2 (b) shows that the fairness of the AIMD algorithm with floating point arithmetic, does not contain the steps observed in Figure 2 (a). This validates our intuition that the rounding errors introduced by Equation (4c) are responsible for the steps observed in Figure 2 (a). . We now specifically focus on the impact of X goal on the fairness of an AIMD algorithm with integer (Int.) and floating point (Flt.) arithmetic in Figure 3. In this figure, for each value of X goal selected in the interval [START_REF] Floyd | On Traffic Phase Effects in Packet-Switched Gateways[END_REF]50], we consider d 1 ranging from 50 to 75, and for each value of d 1 , we choose d 2 ranging from 0.5d 1 to 2d 1 . For each value of X goal , the desired value of the load ratio is d 2 /d 1 . We therefore expect the maximum load ratio to be 2 and the minimum load ratio to be 0.5 for all values of X goal . In Figure 3, we plot the minimum and maximum load ratio observed for each X goal for all d 1 and d 2 .

When x i (t) is a floating point number we observe that the maximum and minimum load ratios converge to their desired values of 2 and 0.5 respectively when X goal is large. However, for smaller values of X goal we observe a significant difference between the desired values and the observed values. This difference is because the amount of overload due to an additive increase of 1 (a I = 1) increases when X goal decreases. When x i (t) is an integer, we observe a non-monotonous behavior. This is because of the rounding errors introduced by the floor function in Equation (4c).

We quantify the sensitivity of the load ratio to variations in the round duration and X goal in Figure 4 (a) and Figure 4 (b) respectively. In Figure 4 (a) we use a semilog scale to plot the maximum and minimum value of the sensitivity to the round duration d 2 for each value Figure 4: Sensitivity of load ratio. Sensitivity when using integers is an order of magnitude larger compared to when floating point numbers are used to maintain the load.

of X goal ; we use ∆d 2 = 1 for this plot. The values of d 1 , d 2 , and X goal were chosen from the same set used to generate Figure 3. In Figure 4 (a) we observe that the maximum sensitivity with floating point arithmetic is an order of magnitude smaller than with integer arithmetic for all the values of X goal considered. We also observe that the difference between the maximum and minimum sensitivity when using floating point numbers is visibly smaller than when using integer arithmetic. Figure 4 (a) thus shows that using floating point arithmetic makes the system less sensitive to changes in round duration for a given value of X goal .

In Figure 4 4 (a), in Figure 4 (b) we observe that using floating point arithmetic results in a smaller maximum sensitivity compared to when integer arithmetic is used. We also observe that the difference between the maximum and minimum sensitivity when using floating point numbers is visibly smaller than when using integer arithmetic.

In conclusion, a system that uses integer variables is more sensitive to changes in the round duration and X goal compared to a system that uses floating point variables.

Efficiency

We have seen that integer arithmetic adversely im- 75, and 0.5d 1 ≤ d 2 ≤ 2d 1 . Using integers as system variables provides better system efficiency compared to using floating point numbers.

pacts the fairness of an AIMD algorithm, we will now explore its impact on efficiency. In Figure 5, we plot the median efficiency of a system for a given value of X goal , the error bars indicate the minimum and maximum efficiency of the system. In Figure 5 we observe that the median efficiency when using integer arithmetic is higher than the median efficiency when using floating point arithmetic for even values of X goal . When X goal is odd we observe that median efficiency is close to the maximum and minimum efficiency when floating point arithmetic is used. The explanation for these observations is as follows. When the system is overloaded, X(t) > X goal , integer arithmetic causes the total load to exceed X goal by a load of at least 1 and at most n (1 ≤ X(t) -X goal ≤ n). Floating point arithmetic enables to signal an overload even when X t -X goal < 1; the range of values that can cause an over load is therefore 0 < X(t) -X goal ≤ n when floating point arithmetic is used. Therefore, the flows can be more aggressive when integer arithmetic is used compared to when floating point arithmetic is used. Furthermore, when X goal is a multiple of the number of flows, floating point arithmetic ensures that 0 < X(t) -X goal ≤ 1 when the round duration of at least one pair of flows is different. Thus, for even values of X goal in Figure 5, we observe that the median efficiency when using integer arithmetic is higher than the median efficiency when using floating point arithmetic. The system attains maximum efficiency when the round duration of each of the flows is the same. This is because all the flows are equally aggressive in attaining their respective fair share. When X goal is odd (for n = 2), floating point arithmetic ensures that the 0 < X t -X goal ≤ 1 for all combinations of round duration in the steady state. Therefore we observe that the median efficiency is close to the maximum and minimum efficiency. . We present the sensitivity of the efficiency to delay and X goal variations in Figure 6. The range of input values used to plot Figure 6 are the same as the ones Figure 4. We observe in Figure 6 (a) that, when X goal is odd, the maximum sensitivity is smaller with floating point arithmetic than with integer arithmetic, but the sensitivity in both cases is similar when X goal is even. In Figure 6 (b) we observe a smaller difference between the maximum and minimum sensitivity when integer arithmetic is used compared to when floating point arithmetic is used. In Figure 6 we observe that the efficiency of a system that uses integer variables is an order of magnitude less sensitive to changes in X goal compared to a system that uses floating point numbers.

Summary

To recap, during the numerical evaluation of our extension to the reference model we made the following observations.

1. With integer arithmetic, the load ratio (and hence fairness) is sensitive to the round duration of the competing flows and the value of X goal . We observe that the fairness is an order of magnitude more sensitive with integer than with floating point arithmetic.

2. With integer arithmetic, the efficiency of the system is higher than with floating point arithmetic.

We also observe that the efficiency of the system using integers arithmetic is an order of magnitude less sensitive to changes in X goal than with floating point arithmetic.

Discussion on Realistic Implementation of AIMD

The numerical resolution of our extension to the reference model portrays the classical trade-off between efficiency and fairness. On the one hand we observe that the system is more efficient when it uses integer variables while on the other hand the system suffer from poor fairness.

We also observe that the error introduced by the floor function performed during the multiplicative decrease amplifies when the round duration of competing flows are different. The amplification of the error makes the fairness of the system sensitive to changes in the round duration and X goal . Furthermore, we also observe that the unfairness increases as the bottleneck resource capacity, X goal , decreases.

In our extension we assume that the floor function is used when performing the multiplicative decrease. We make similar observations when we use the ceiling function instead of the floor function in Equation (4c). Similarly, in this section we present results for a system of two flows. We have performed numerical evaluations for a system of up to four flows and we make similar observations with respect to fairness and efficiency and their sensitivity to round duration and X goal .

It is important to remark that the issue we observe with integer arithmetic is an implementation issue because of protocol restrictions or because of restrictions by the operating systems. There is a rounding error, when the floor operation is performed on an odd congestion window during a multiplicative decrease phase. Therefore, we qualify this issue as an implementation bug that needs to be solved. In the following section, we present our solution to this rounding error bug.

FIXING THE ROUNDING ERROR BUG

In this section, we first present a fix to the bug causing rounding errors on a multiplicative decrease with integer arithmetic. Then, we show that our fix solves the observed unfairness issue without sacrificing efficiency.

Description of the fix

Our fix simply consists in alternating between the floor and the ceiling functions on successive calls to the multiplicative decrease procedure when its input is an odd number. The insight for this fix is the following.

The bug we observed in Section 3.3 is due to a rounding error. By alternating the floor and ceil functions, we expect to compensate for the rounding errors. In addition, in Equation (4c), the multiplication by m D = 0.5 produces an error only if the input for the multiplicative decrease is an odd number; there is no error when the multiplicative decrease is performed for even numbers. We therefore alternate between the floor and ceiling functions only when a multiplicative decrease is performed when the load is an odd numbers. The implementation of this fix is simple. We maintain a state in variable a which indicates whether the floor (a = 0) or the ceiling function (a = 1) needs to be called during the multiplicative decrease. The pseudo-code for our fix is the following.

if x(t) is even then

x(t + 1) ← max(x(t)/2, 1) else x(t + 1) ← max(x(t)/2 + a, 1) a ← (a + 1) mod 2 end if
We would like to point out that this fix is specific to an AIMD algorithm with m D = 0.5. However, for other values of m D similar fixes can be applied.

Numerical Evaluation

We evaluate in the following the efficiency and fairness achieved by our fix, and the possibility to incrementally deploy a patch. During incremental deployment flows that use our fix shall compete with flows that use the floor function while performing the multiplicative decrease (see Equation (4c)). For qualitative assessment of the impact of such a deployment, we also consider a system with two flows where one flow uses the floor function and the other uses the ceiling function while performing the multiplicative decrease. We use the following notations in the legend of the figures in this section.

• Our: The two flows use our fix.

• Int.: The two flows use integer arithmetic with the floor function (see Equation (4c)).

• Flt.: The two flows use floating point arithmetic.

• Our-Int.: Both the flows use integer arithmetic, however, one of the two flows uses our fix while the other uses the floor function. We use this result to assess the impact of incremental deployment of our fix.

• Int.*-Int.: Both the flows use integer arithmetic, however, one of the two flows uses the ceiling function while the other uses the floor function.

In Figure 7, we present the maximum and minimum load ratio between two flows; the range of values for We observe that when using our fix the load ratio monotonously converges to the desired values.

X goal , d 1 , and d 2 are the ones we used for Figure 3 in Section 3.3. We observe that values for the maximum load ratio with our fix are very close to the ones with floating point arithmetic. During incremental deployment (Our-Int.), we observe that the maximum load ratio is not a monotonous function of X goal ; the load ratio is significantly larger compared to when both the flows use our fix. This is because the flow that uses our fix performs the ceiling function, which is more aggressive that the floor function, during at most half of the multiplicative decrease events. However, the maximum load ratio during incremental deployment (Our-Int.) does not exceed the maximum load ratio observed when one flow uses the ceiling function and the other uses the floor function(Int*.-Int.). We make similar observations for the minimum load ratio in Figure 7 (b). We show in Figure 8 that by using our fix the load ratio, and thus system fairness, is an order of magnitude less sensitive to changes in both the round duration and X goal . We use the same range of values used to plot Figure 4 (a) and Figure 4 (b) in Section 3.3. In Figure 8 (a), we observe that with our fix (Our) the sensitivity of the load ratio is close to the one obtained with floating point arithmetic (Flt.), that is much better than with integer arithmetic without our fix (Int.).

In a system where one flow uses our fix and the other one uses the floor function during the multiplicative decrease (Our-Int.), the sensitivity is similar to that observed when both the flows use the floor function. In Figure 8 (b), we also observe that our fix solves the sensitivity issue of the load ratio to X goal variations. Figure 8: Sensitivity of the load ratio to the round duration and to X goal when 10 ≤ X goal ≤ 50, 50 ≤ d 1 ≤ 75, and 0.5d 1 ≤ d 2 ≤ 2d 1 . We observe that with our fix the system achieves the low sensitivity exhibited when using real numbers. We observe that by using our fix the system does not loose out on efficiency.

We now show that our fix significantly improves efficiency compared to the case with integer arithmetic without the fix. In Figure 9 (a), we plot the efficiency of the system when both flows use our fix. By comparing Figure 5 (a) and Figure 5 (b) with Figure 9 (a), we observe that the median efficiency with our fix is better We observe that, despite using integers, by using our fix the system becomes less sensitive to changes in round duration compared to when using only the floor function.

than the one observed with integer arithmetic or even with floating point arithmetic. We also observe that the minimum efficiency can be higher by up to 2.5% with our fix than with integer arithmetic without our fix. In Figure 9 (b), we observe that the system efficiency does not suffer when one flow uses our fix while the other uses integer arithmetic without our fix (that is the floor function only) during the multiplicative decrease phase. We now use Figure 10 to show that the sensitivity of efficiency to changes in round duration and X goal does not increase with our fix compared to when integer arithmetic is used with the floor function only. In Figure 10 (a), we plot the sensitivity of the efficiency to changes in the round duration. We observe that for odd values of X goal , the sensitivity with our fix is more than the low sensitivity observed with floating point arithmetic; however, it does not exceed the sensitivity observed when using only integer arithmetic with the floor function. When X goal is even, our fix mimics the behavior of using integer arithmetic and we observe a maximum sensitivity that is less than that observed when floating point arithmetic is used to maintain the system variables. Furthermore, when a source that uses our fix competes with a source using the floor function the maximum sensitivity does not increase to value beyond those exhibited when using either integer arithmetic or floating point arithmetic. In Figure 10 (b) we observe that our fix produces the smallest values for maximum sensitivity of efficiency to X goal . We also observe that during incremental deployment of our fix the maximum sensitivity does not exceed the maximum sensitivity observed when floating point arithmetic is used.

To recap, we observe that with our fix the system fairness improves to compared to when only integer arithmetic is used. We also observe that during incremental deployment of our fix the system fairness is never worse than the fairness exhibited when one flow uses the ceiling function and the other uses the floor function. Our results show that the gains in fairness do not result in poor efficiency. We observe that by using our fix the system is able to maintain the levels of efficiency exhibited when integer arithmetic is used with the floor function.

Summary

In the previous section, Section 3, we observed that the AIMD algorithm is the fairest with floating point arithmetic and the most efficient with integer arithmetic. In this section, we proposed a fix and showed that our fix achieves both the best fairness and efficiency. We observe that, despite using integers to maintain system variables, our fix makes the algorithm fairness an order of magnitude less sensitive to changes in the network condition without a decrease in system efficiency.

We also observe that during incremental deployment of our solution the efficiency and fairness is similar to that when the competing flows use integer arithmetic with the floor function. Apart from alternating between the floor and ceiling functions we also analyzed the impact of randomly selecting between a floor and ceiling function when the input for the multiplicative decrease is an odd number. We do not present these results to avoid redundancy. We observed that the results in the average case are close to what we observe on successively alternating between the floor and ceiling function, however in the worst case the behavior is like that of using the floor function.

RELATED WORK

We would like to point out that we are not the first to extend the model of Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF]. Gorinsky et al. [START_REF] Gorinsky | Extended analysis of binary adjustment algorithms[END_REF] have extended the model of Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] to highlight some of the issues with the AIMD algorithm. The authors then extend their work and propose Multiplicative Additive Increase Multiplicative Decrease (MIAMD) [START_REF] Gorinsky | A Theory of Load Adjustments and its Implications for Congestion Control[END_REF]. Though the authors support sources having different delays to the bottleneck link they do not incorporate the concept of a round duration in their paper. In their paper, during the first slot of each round the sources react to the feedback received only during a fraction of the slots of the round duration. These two works by Gorinsky et al.are the closest to our work in extending the reference model of Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] used in this paper. Indeed, in this paper we show that AIMD with a I = 1 and m D = 0.5 can have some serious shortcomings with respect to fairness under realistic conditions. However, we also show that AIMD (with a I = 1 and m D = 0.5) implemented using our solution can converge to the desired values of fairness and yet be efficient.

Floyd et al.

DISCUSSION AND CONCLUDING RE-MARKS

In this paper we revisit the performance of AIMD, the cornerstone algorithm used in internet congestion control. We extend the reference model of Chiu et al. [START_REF] Chiu | Analysis of the increase and decrease algorithms for congestion avoidance in computer networks[END_REF] to address its shortcomings which includes synchronous response to system feedback. We use our extension to show that the AIMD algorithm under realistic conditions suffers from the classical trade-off between efficiency and fairness.

Under realistic conditions we observe that AIMD suffers from not only poor fairness but also high sensitivity of fairness to changes in round duration or bottleneck capacity. We also observe that the unfairness increases as the bottleneck capacity decreases. We identify the source of the problem to be the rounding errors introduced by the multiplicative decrease operation. These rounding errors arise because of restrictions to use integers; these restrictions are imposed either by the protocol using AIMD or the operating system kernels. We the provide a simple fix to address this issue and show that by using our fix the system fairness and efficiency improves.

One argument against low resource availability could be the ever increasing network capacities. However, Akamai reports that about 44% of connection links to the Akamai servers have a data rate of less than 5 Mbps [START_REF] Akamai | The State of the Internet[END_REF]. Furthermore, our model abstracts the available congestion window as the resource and not the bottleneck bandwidth. Recent advances in queuing techniques such as CoDel [START_REF] Nichols | Controlling Queue Delay[END_REF] are aimed at operating at the optimal value of the congestion window. CoDel ensures that the TCP connections use a congestion window which significantly lower than those observed when the queues suffer from Bufferbloat [START_REF] Gettys | Dark buffers in the internet[END_REF]. On the same lines, applications are also explicitly limiting the congestion windows used by their TCP connections [START_REF] Ghobadi | Trickle : Rate Limiting YouTube Video Streaming[END_REF][START_REF] Rao | Network characteristics of video streaming traffic[END_REF].

The implementation of TCP in the Linux kernel main-tains the congestion window in units of full sized segments while the BSD implementations use units of bytes. By switching from packets to bytes, for the same congestion window, the rounding error decreases by several orders of magnitude. In this paper we show that the rounding errors tend to amplify the unfairness and make the system highly sensitive to changes in network conditions. Based on our observations we recommend maintaining the congestion window in units of bytes.

For other protocols that use AIMD we recommend using an appropriate unit for the load that minimizes the rounding error. We tested our solution using ns3 [START_REF]ns3 network simulator[END_REF] simulations. We considered a topology where n sources transfer data to n destinations. These n TCP flows pass through a common bottleneck router. We used the actual linux kernel stack for our simulations [START_REF]ns3 network simulator[END_REF] and considered up to 10 flows and different bottleneck capacities from 256 kbps to 5 Mbps. When no background traffic was passing through the bottleneck router we observe phase effects to be the dominating cause of unfairness [START_REF] Floyd | On Traffic Phase Effects in Packet-Switched Gateways[END_REF][START_REF] Floyd | Difficulties in Simulating the Internet[END_REF]. We could not observe any noteworthy improvement by using our solution when using the drop-tail and CoDel queue. With stochastic fair queuing [START_REF] Mckenney | Stochastic fairness queueing[END_REF] the system was fair even without our fix and on adding our solution we observed an efficiency of no more than 1%. For the CoDel and drop-tail queues, adding a background traffic that randomly generated a load of 10% to 15% of the bottleneck capacity desynchronized the flows. This desynchronization also abstracted the random selection between the floor and ceiling function; we therefore cannot confidently quantify the impact of our solution for existing TCP implementation. We would like to point out that we did not observe any side-effects or unexpected behaviors on using our solution in the Linux kernel.

  xi(t) as an integer. 0.5 0.75 1 1.25 1.5 1xi(t) as a floating point number.

Figure 2 :

 2 Figure2: Load Ratio for X goal of 10, 30 and 50. Round duration was 50 slots for flow 1, and 50 slots to 100 slots for flow 2. Using integer arithmetic for the load generated makes the system more sensitive to changes in the round duration.

Figure 3 :

 3 Figure 3: Maximum and minimum load ratio when 10 ≤ X goal ≤ 50, 50 ≤ d 1 ≤ 75, and 0.5d 1 ≤ d 2 ≤ 2d 1 .The maximum load ratio is significantly larger when using integer variables compared to when floating point variables are allowed.

  Sensitivity to X goal .

  System variables as floating point numbers.

Figure 5 :

 5 Figure 5: Efficiency when 10 ≤ X goal ≤ 50, 50 ≤ d 1 ≤75, and 0.5d 1 ≤ d 2 ≤ 2d 1 . Using integers as system variables provides better system efficiency compared to using floating point numbers.

  Sensitivity to X goal .

Figure 6 :

 6 Figure 6: Sensitivity of efficiency. Sensitivity when using floating point numbers is an order of magnitude larger compared to changes in X goal when integers are used to maintain the load.

Figure 7 :

 7 Figure 7: Maximum and minimum load ratio when 10 ≤ X goal ≤ 50, 50 ≤ d 1 ≤ 75, and 0.5d 1 ≤ d 2 ≤ 2d 1 .We observe that when using our fix the load ratio monotonously converges to the desired values.

  Sensitivity to round duration.

  Sensitivity to X goal .

  Both flows use our fix.

  One flow uses our fix while the other uses the floor function.

Figure 9 :

 9 Figure 9: Efficiency when 10 ≤ X goal ≤ 50, 50 ≤ d 1 ≤ 75, and 0.5d 1 ≤ d 2 ≤ 2d 1 .We observe that by using our fix the system does not loose out on efficiency.

  Sensitivity to round duration.

  Sensitivity to X goal .

Figure 10 :

 10 Figure10: Sensitivity of the efficiency when 10 ≤ X goal ≤ 50, 50 ≤ d 1 ≤ 75, and 0.5d 1 ≤ d 2 ≤ 2d 1 . We observe that, despite using integers, by using our fix the system becomes less sensitive to changes in round duration compared to when using only the floor function.

[ 9 ]

 9 have studied the fairness of AIMD algorithms for different values of a I and m D . They show a flows with a I = 1 and m D = 0.5 will be fair only to flows that have a I = 3m D 2 -m D . In this paper we restrict ourselves to a I = 1 and m D = 0.5 because these values of a I and m D are the most widely used values. Furthermore, we are not the only ones restricting to these values of a I and m D , most of the analysis of fairness of TCP flows available in the literature either explicitly mention or inherently a I = 1 and m D = 1 [10,11,17,23].

  1 . During the first slot of a

	Variable value	1 2 3 4 5 6				(t) x 1 x 2 (t) x 3 (t) y(t)
		0
		0	100	200 Time (t) in slots 300	400	500

Table 1 :

 1 Summary of variables used in our extension to the reference model.

The model can be extended to support a round duration that varies with time. However, in this paper, we restrict ourselves to a round duration that does not change with time.

Proportional rate reduction[START_REF] Dukkipati | Proportional Rate Reduction for TCP[END_REF] ensures that congestion window is set to the slow start threshold after loss recovery.


Houssem-Eddine Chihoub
email: houssem-eddine.chihoub@inria.fr

Shadi Ibrahim
email: shadi.ibrahim@inria.fr

Gabriel Antoniu
email: gabriel.antoniu@inria.fr

María S Pérez
email: mperez@fi.upm.es

Harmony: Towards Automated Self-Adaptive Consistency in Cloud Storage

Keywords: consistency, replications, data stale, Cassandra, cloud, self-adaptive

In just a few years cloud computing has become a very popular paradigm and a business success story, with storage being one of the key features. To achieve high data availability, cloud storage services rely on replication. In this context, one major challenge is data consistency. In contrast to traditional approaches that are mostly based on strong consistency, many cloud storage services opt for weaker consistency models in order to achieve better availability and performance. This comes at the cost of a high probability of stale data being read, as the replicas involved in the reads may not always have the most recent write. In this paper, we propose a novel approach, named Harmony, which adaptively tunes the consistency level at run-time according to the application requirements. The key idea behind Harmony is an intelligent estimation model of stale reads, allowing to elastically scale up or down the number of replicas involved in read operations to maintain a low (possibly zero) tolerable fraction of stale reads. As a result, Harmony can meet the desired consistency of the applications while achieving good performance. We have implemented Harmony and performed extensive evaluations with the Cassandra cloud storage on Grid'5000 testbed and on Amazon EC2. The results show that Harmony can achieve good performance without exceeding the tolerated number of stale reads. For instance, in contrast to the static eventual consistency used in Cassandra, Harmony reduces the stale data being read by almost 80% while adding only minimal latency. Meanwhile, it improves the throughput of the system by 45% while maintaining the desired consistency requirements of the applications when compared to the strong consistency model in Cassandra.

I. INTRODUCTION

Cloud computing has become a very popular paradigm. Part of its success is due to its flexibility, elasticity, and scalability. Clients can lease just the resources they need on the cloud in a Pay-as-You-Go manner with very little knowledge of the physical resources. For cloud computing to be a real alternative to grid and cluster computing, it should perform well with everyday applications. Nowadays many of these applications are data-intensive: companies like Google, Amazon, and Facebook deal with peta-and terabytes of data everyday. In this context, storage management and performance within clouds is extremely important.

Storage systems often rely on replication to achieve availability, data durability, fault tolerance, disaster recovery. However, with the use of replication comes the issue of consistency. Insuring data consistency at all times by means of synchronous replication results in very high operation latencies and thus in bad performance. Moreover, cloud storage systems are deployed on a wide area scale and data are replicated over geographically distant areas. Consequently, latencies become even higher when ensuring strong consistency. These high latencies may generate significant financial losses for service providers that use such storage systems. For instance, the cost of a single hour of downtime for a system doing credit card sales authorizations has been estimated to be between $2.2M-$3.1M [START_REF] Peglar | Eliminating planned downtime: the real impact and how to avoid it[END_REF]. Consequently, cloud providers tend to rely on storage systems with eventual consistency. Eventual consistency allows the system to return some stale data at some points in time, but ensures that all data will eventually become consistent.

In this context, many cloud storage systems have been developed such as Amazon Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF], Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF], Google BigTable [START_REF] Chang | Bigtable: A distributed storage system for structured data[END_REF], Yahoo! PNUTS [START_REF] Cooper | Pnuts: Yahoo!s hosted data serving platform[END_REF], and HBase [START_REF]Apache HBase[END_REF]. These solutions are practical to use as cloud and web service storage backends. They allow many web services to scale up their systems in an extreme way, while maintaining performance with very high availability. For example, Facebook uses Cassandra to scale up to host data for more than 800 million active users [START_REF]Facebook Statistcs[END_REF]. However, the undoubted availability and performance of such solutions prove to be too costly in terms of inconsistency. As shown in [START_REF] Wada | Data consistency properties and the trade-offs in commercial cloud storage: the consumers' perspective[END_REF], under heavy reads and writes some of these systems may return up to 66.61 % stale reads. This is an alarming rate, meaning that most probably two out of three reads are useless.

In this paper, we address these tradeoffs between consistency and performance on the one hand, and consistency and availability on the other. Accordingly, we propose an automated and self-adaptive approach, named Harmony, that tunes the consistency level at run-time to reduce the probability of stale reads caused by the cloud system dynamicity (i.e., the network latency which directly affects updates propagation to replicas) and the application's demands (i.e., the frequency of access patterns during reads, writes and updates), thus providing adequate tradeoffs between consistency and both performance and availability. Harmony embraces an intelligent estimation model to automatically identify the key parameter affecting the stale reads such as the system states (network latency) and application's requirements (current access pattern). Harmony, therefore, elastically scales up/down the number of replicas involved in read operations to maintain a low (possibly zero) tolerable fraction of stale reads, hence, improving the performance of the applications while meeting the desired consistency level.

We have implemented Harmony with intensive evaluations on Cassandra cloud storage system on different platforms: Grid'5000 [START_REF] Jégou | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF] -an academic experimental testbed based in France -and Amazon Elastic Compute Cloud (EC2) [START_REF]Amazon Elastic Compute Cloud (Amazon EC2)[END_REF]. We use the Yahoo! Cloud Serving Benchmark (YCSB) [START_REF] Cooper | Benchmarking cloud serving systems with ycsb[END_REF] to mimic a real cloud serving environment with elastic access pattern workloads (e.g., heavy read load, heavy update load etc). We show that Harmony can achieve good performance without exceeding the tolerated number of stale reads on the applications. For instance, in contrast to the Cassandra's static eventual consistency, Harmony with 20% tolerated stale reads reduces the stale data being read by almost 80% while adding only minimal latency. Moreover, it improves the throughput of the system by 45% compared to the Cassandra's strong consistency model while maintaining the desired consistency requirements of the applications. The contributions of this work can be summarized as follows:

• We propose an automated self-adaptive approach that gradually and dynamically scales the consistency level to best suit the application requirements, while taking into account the system state.

• By means of probabilistic computations we provide an estimation of the stale reads rate in a storage system for a running workload. • We evaluate the proposed approach with an extensive set of experiments both on a bare metal environment (Grid'5000) and on a cloud computing platform (Amazon EC2). The results show a significant improvement in performance compared to the traditional strong consistency approach, while providing better consistency than static eventual consistency approaches.

This paper is organized as follows. Section II briefly discusses consistency-performance and consistency-availability tradeoffs in cloud storage and zooms on the the eventual consistency model. Section III presents our adaptive model to handle consistency at run-time. Then section IV gives more details on how to estimate the amount of stale reads in the system. In section V we describe the Harmony implementation and present detailed results of experimental evaluations. Section VI discusses related work. Finally, section VII presents our conclusions and future work.

II. BACKGROUND

A. Tradeoffs between consistency, performance and availability in cloud storage

The CAP theorem, which was introduced in [START_REF] Brewer | Towards robust distributed systems[END_REF] then proved in [START_REF] Gilbert | Brewer's conjecture and the feasibility of consistent available partition-tolerant web services[END_REF], tackled a real design challenge for today's storage systems. The theorem states that only two out of the three following properties can be guaranteed simulta-neously: Consistency, Availability, and Partition tolerance 1 . Since partition tolerance is necessary for scalable distributed systems that rely on networking, a real tradeoff between consistency and availability needs to be defined. Twelve years after his CAP theorem, in [START_REF] Brewer | Cap twelve years later: How the "rules" have changed[END_REF] Brewer considers the tradeoff consistency-performance as even more important. He argues that partitions are rare and one obvious solution is to predict their occurrence times. In this case, the tradeoff between consistency and availability should be considered only during the partitions. In contrast, the consistencyperformance tradeoff is a permanent one. Abadi [START_REF] Abadi | Consistency tradeoffs in modern distributed database system design: Cap is only part of the story[END_REF] makes a connection between latency and availability. When latency is higher than some timeout the system becomes unavailable. Similarly, the system is available if latency is smaller than the timeout. However, the system can be available and exhibit high latencies nonetheless. This implies consistencylatency and consistency-availability tradeoffs are connected and exist outside CAP.

With cloud storage systems being deployed on a wide area scale with data replicated over geographically distant areas, latencies become even higher in this case for traditional storage systems that ensure strong consistency. Eventual consistency [START_REF] Vogels | Eventually consistent[END_REF] therefore was introduced as an alternative to the traditional strong consistency. Such consistency allows the system to return some stale data at some points in time, but ensures that all data will become eventually consistent. Influenced by such tradeoffs, many storage system designers opt for BASE properties (basically available, soft state, eventually consistent) [START_REF] Pritchett | Base: An acid alternative[END_REF] instead of ACID (Atomicity, Consistency, Isolation, and Durability) in order to relax consistency rules, and hence favor performance and availability. Today, some of the main cloud storage providers rely on storage systems with eventual consistency. For example, Amazon Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF] is the storage system for most of Amazon services including Amazon Simple Storage Service (S3) [START_REF]Amazon Simple Storage Service (Amazon S3)[END_REF]. Dynamo enables high availability and low latency for Amazon web services.

B. Zoom on eventual consistency in cloud storage

The way consistency is handled has a big impact on performance. Traditional synchronous replication (strong consistency) dictates that an update must be propagated to all the replicas before returning success. In cloud services where data updates occur often, it is difficult to keep the consistency among replicas in the entire cloud storage system. To solve this problem, eventual consistency with asynchronous quorum replication has been introduced. Here the consistency level is chosen on a per-operation basis and is represented by the number of replicas in the quorum (a subset of all the replicas). A quorum is computed as:

(replication f actor/2) + 1. Data accesses and updates are performed to all replicas in the quorum. Thus, using this level for both read and write operations guarantees that the intersection of replicas involved in both operations contains at least one replica with the last update. A partial quorum has a smaller subset of replicas, hence returning the most recent data when read is issued, is not guaranteed.

Consistency levels in Cassandra. In the Cassandra storage system, several consistency levels [START_REF]About Data Consistency in Cassandra[END_REF] are proposed peroperation. A write of consistency level one implies that data have to be written to the commit log and memory table of at least one replica before returning a success. Moreover, as shown in Figure 1, a read operation with consistency level ALL (strong consistency) implies that the read operation must wait for all the replicas to reply with consistent data in order to return the data to the client. However, this will introduce higher latency if some replicas are inconsistent with the most current version. In contrast, a read consistency level of quorum, 2 of the 3 replicas are contacted to fulfill the read request and the replica with the most recent version would return the requested data. In the background, a read repair will be issued to the third replica and will check for consistency with the first two. If inconsistency occurs, an asynchronous process will be launched to repair the stale nodes at a latter time.

Many cloud storage systems such as Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF], Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF], Voledemort [START_REF]Project Voldemort[END_REF], and Riak [START_REF]Riak: An Open Source Scalable Data Store[END_REF] adopt asynchronous quorum replication [26][27]. This gives the application writer more flexibility when selecting the type of consistency that is appropriate for each operation. This is a useful feature, but until now no automatic adaptive model has been proposed for these systems. This means that the application writer has to choose the type of consistency for every operation, which is hard when no information is available regarding the read and write frequencies, network latency, and the system state in general, or when operating on a very large scale. We present Harmony, an approach which aims to make this task automatic for the operations that are not critical or do not need a strictly strong consistency. This is achieved using just a small hint about the application needs.

III. ELASTIC ADAPTIVE CONSISTENCY MODEL

The goal of Harmony is to dynamically and elastically handle consistency at run time, in order to provide adequate tradeoffs between consistency and both performance and availability. Accordingly, Harmony considers not only the application requirements but also the storage system state. Moreover, rather than relying on a standard model based only on the access pattern to define the consistency requirement of an application -which is the case for most existing work -Harmony, in addition, uses the stale read rate of the application to precisely define such requirement. Why use the stale reads rate to define the consistency requirements of an application? For example, we consider two applications that may have at some point the same access pattern. One is a web-shop application that can have heavy reads and writes during the busy holiday periods, and a social network application that can also have heavy access during important events or in the evening of a working day. These two applications may have the same behavior at some point and are the same from the point of view of the system when monitoring data accesses and network state as well, thus they may be given the same consistency level. However, the cost for stale reads is not the same for both applications. A social network application can tolerate a higher number of stale reads than a web-shop application: a stale read has no effects on the former, whereas it could result in anomalies for the latter. Consequently, defining the consistency level in accordance to the stale reads rate can precisely reflect the application requirement.

We propose our model for distributed storage systems. In this context, data may be replicated over geographically distant data centers. In order to predict the effect of weaker consistencies, we compute θ stale , the estimation of the stale read rate in the system. The consistency requirement of an application should be determined by providing the rate of reads that should be fresh; in other words, the rate of stale reads that is tolerated by the application. Let this be app stale rate. For critical applications that require strong consistency, this rate should be 0%. Similarly, an application that does not need any consistency at all, such as an application that consists of only reads from archives, the rate should be 100% (which corresponds to static eventual consistency). A naïve way to map the consistency requirements of an application to the app stale rate is the following: for an application that needs an average consistency, the rate should be 50%. An application that needs less than average consistency should have a rate of 25%, and an application that requires higher consistency should use 75%. As part of future work, we plan to propose mechanisms to help an application administrator to determine such a rate in a more precise way. This rate is tunable and can be defined by studying the behavior of an application.

Additionally, in the case of distributed data replication, network latency may be high and thus, a performancedefining factor. Other than app stale rate, in our model, we consider the network latency and the application access pattern. We permanently, collect such information in order to estimate the stale read rate. From a higher level perspective, our solution uses the following decision scheme:

if app stale rate ≥ θ stale then Choose eventual consistency (Consistency Level = One) else

•

ComputeX n the number of always consistent replicas necessary to have app stale rate ≥ θ stale

•

Choose consistency level based on X n end if

The default consistency level is the basic eventual consistency that allows reading from only one replica. When such a level may not satisfy the consistency requirements of an application due to the growing number of stale reads, the number of replicas X n that should be involved in the reading requests is computed. All the following read requests will be performed with Consistency level X n . In the next section we explain in detail how we estimate the stale reads rate and how we compute the necessary number of replicas.

IV. PROBABILISTIC STALE READ RATE ESTIMATION

In this section, we propose an estimation of the stale read rate in the system by means of probabilistic computations. This estimation model requires basic knowledge of the application access pattern and of the storage system network latency. Network latency in this case is of high importance, since it is the determinant of the updates propagation time to other replicas. The access pattern, which includes read rates and write rates is a key factor to determine consistency requirements in the storage system. For instance, it is obvious that a heavy read-write access pattern would produce higher stale reads when adopting eventual consistency.

1) Stale read probability: We define the situation that leads to a stale read in Figure 2. The read may be stale if its starting time X w is in the time interval between the starting time of the last write and the end of the propagation time of data to the other replicas. This situation is repeatable for any of the writes that may occur in the system. T p in Figure 2 is the time necessary for the propagation of a write or an update to all the replicas. It is computed based on the network latency L n and the average write size avg w and should be represented as T p (L n , avg w ), but in order to simplify the representation, it will be denoted as T p in the rest of the paper.

Transactions arrivals are generally considered as a Poisson process as it is the common way to model them in literature [START_REF] Wada | Data consistency properties and the trade-offs in commercial cloud storage: the consumers' perspective[END_REF] [START_REF] Tai | Performability management in distributed database systems: An adaptive concurrency control protocol[END_REF]. We assume that the writes and the reads arrivals follow the Poisson distribution of parameter λ -1 w (we chose λ -1 w instead of λ w in order to simplify subsequent formulas where the parameter will be inverted) and λ r respectively. These parameters values change dynamically at run time following the read and write requests arrivals monitored in the storage system. Since the distribution of waiting time between two Poisson arrivals is an exponential process, the stochastic variables X w and X r of a write time and read time follow an exponential distribution of parameters λ -1 w and λ r respectively. The probability of the next read being stale corresponding to the aforementioned situation is given by formula [START_REF] Peglar | Eliminating planned downtime: the real impact and how to avoid it[END_REF] with N being the replication factor in the system and X being the number of replicas involved in the read operation. Here X n =1 for the basic eventual consistency.

P r(stale read)

= ∞ i=0 ( N -(X n = 1) N P r(X i w < X r < X i w + T + T p ) + X n = 1 N P r(X i w < X r < X i w + T )) (1)
Having all the writes times (that may occur in the system) following the exponential distribution, the sum of X i w all the writes follows a Gamma distribution of parameters i and λ w . Hence, the probability in formula (1) becomes:

P r(stale read) = ∞ i=0 ( N -1 N ∞ 0 f i w (t)(F r (t + T + T p ) -F r (t))dt + 1 N ∞ 0 f i w (t)(F r (t + T ) -F r (t))dt) (2)
The time T to write in the local memory is negligible in comparison to T P and therefore, we can consider it as equal to 0. A simple replacement of the probability mass function of Poisson distribution and the cumulative distribution function of Gamma distribution results in the following probability:

P r(stale read) = ∞ i=0 N -1 N ∞ 0 t i-1 e -t λw γ(i)λ i w (e -λr t -e -λr(t+Tp) )dt (3)
After simplifying formula (3), it becomes:

P r(stale read) = ∞ i=0 (N -1)(1 -e -λrTP ) N (1 + λ r λ w ) i ∞ 0 t i-1 e 1+λr λw λw t γ(i)( λw 1+λr λw ) i dt (4)
The right part of the function in ( 4) is the the cumulative distribution function of a Gamma law of parameters 1+λr λw λw and i, its value is equal to 1. Moreover, if we consider that:

∞ i=0 ( 1 1 + λ r λ w ) i = 1 λ r λ w + 1 (5)
The final value of the probability of next read to be stale, after simplification, is given by:

P r(stale read) = (N -1)(1 -e -λr Tp )(1 + λ r λ w ) N λ r λ w (6)
2) Computation of X n , the number of replicas: To compute the number of replicas to be involved in a read operation necessary to maintain the desired consistency, we compute X n in formula (1) to maintain the inequality [START_REF]Facebook Statistcs[END_REF] in order to provide a stale read rate smaller or equal to the app stale rate denoted as ASR for simplicity.

P r(stale read)

= ∞ i=0 ( N -X N ∞ 0 f i w (t)(F r (t + T + T p ) -F r (t))dt + X N ∞ 0 f i w (t)(F r (t + T ) -F r (t))dt) ≤ ASR (7)
After simplification, and following similar steps for computing in formulas (3), ( 4), and ( 6), the number of the replicas X n is given by the formula: Figure 3. Harmony implementation and integration with Cassandra and Yahoo! Cloud Serving Benchmark: While the monitoring module collects relevant information from the Cassandra storage cluster using Cassandra Nodetool and ping tool in multithreaded manner, the adaptive-consistency module estimates the read stale rate using the collected information as an input and then sends the most appropriate consistency level to the client "the modified Java client for Cassandra in YCSB"

X n ≥ N ((1 -e -λrTP )(1 + λ r λ w ) -ASRλ r λ w ) (1 -e -λr TP )(1 + λ r λ w ) (8)
V. EVALUATIONS

A. Harmony Implementation

Harmony can be applied to different cloud storage systems that featured with flexible consistency rules. Currently we have built Harmony in Apache Cassandra "Cassandra-1.0.2" [START_REF]Apache Cassandra[END_REF]. As described in Section II, Cassandra gives the user flexible usage of consistency levels in a per-operation manner. In addition, Cassandra is proven to be very scalable, offering very good performances, and being widely used with large scale applications such as Facebook and Twitter. Figure 3 gives an overview of the Harmony implementation.

Harmony is introduced as an extra layer on Cassandra that aims to provide the most appropriate level of consistency for reading data. The core of this layer consists of two modules. Both modules were implemented in Python 2.7.

The monitoring module collects relevant metrics needed for Harmony. The Cassandra Nodetool was used to collect the number of reads and writes in Cassandra storage, and the Ping tool was used to collect network latencies in the storage system network. The monitoring module was designed in a multithreaded manner in order to make it time-efficient and to reduce the monitoring time. Each thread collects data from a set of nodes and at the end an aggregation process is applied. The monitoring time is measured and taken into account when computing the read rates and write rates. This data is further communicated to the adaptive consistency module. This module is the heart of Harmony implementation. An estimation of the stale read rate is computed and then compared to the application stale read that can be tolerated (app stale rate) in order to provide an adequate consistency level for the running application at that point of time.

B. Evaluation Methodology

We adopt two complementary approaches to provide storage as a service for cloud clients. In our first approach, cloud clients which can be applications running on cloud computing service such as Amazon EC2 [START_REF]Amazon Elastic Compute Cloud (Amazon EC2)[END_REF] or Google App Engine [START_REF]Google App Engine[END_REF], can connect to the storage service on an S3-like interface to lease their storage resources. This is an interface to a highly distributed scalable storage backend that will physically host and manage data. We set up a cloud storage testbed on the Grid'5000 experimental grid and cloud testbed [START_REF] Jégou | Grid'5000: a large scale and highly reconfigurable experimental grid testbed[END_REF] that federates 10 sites in France. In our second approach the storage service is provided within the virtual disks attached to the virtual machines (VMs) side by side with cloud clients. We set up the underlying storage system on Amazon EC2 clusters and serve applications running inside VMs. Micro Benchmark. We aim at a micro benchmark representing typical workloads in current services hosted in clouds. Based on case studies [START_REF] Cooper | Pnuts: Yahoo!s hosted data serving platform[END_REF][11], we have selected the Yahoo! Cloud Serving Benchmark (YCSB) framework [START_REF]Yahoo Cloud Serving Benchmark[END_REF]. YCSB is used to benchmark Yahoo!'s cloud storage system "PNUTS" [START_REF] Cooper | Pnuts: Yahoo!s hosted data serving platform[END_REF]. It is extended to be used with a variety of open-source data stores such as mongoDB [START_REF]mongoDB[END_REF], Hadoop HBase [START_REF]Apache HBase[END_REF] and Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF]. YCSB provides the characteristics of a real cloud serving environment such as scale-out, elasticity and high availability. For this purpose, several workloads have already been proposed in order to apply a heavy read load, heavy update load, and read latest load, among other workloads. Also, the benchmark is designed to make the integration of new workloads very easy. We use YCSB-0.1.3, as shown in Figure 3. We modify the provided Java client for Cassandra in order to allow read operations to be performed with different consistency levels at run time. The Java client uses Thrift [START_REF]Apache Thrift[END_REF] to communicate with the cluster and is provided with the set of hosts from which it should request a read or a write. The modified Java client reads data from Cassandra with the consistency level provided dynamically by the adaptive consistency module.

C. Experimental Setup

We evaluate Harmony with Cassandra deployed on both Grid'5000 and Amazon EC2. Setup on Grid'5000. We use two clusters in the Sophia site with a total of 84 nodes and 496 cores. All nodes are equipped with x86 64 CPUs and 4GB of memory. The nodes are interconnected with Gigabit Ethernet. All nodes from the first cluster have two hard disks with combined capacity of 600GB per node. As for the second cluster, the nodes are all equipped with hard disks of 250GB. Setup on Amazon EC2. We use 20 Virtual machines of type Large located in the us-east-1a availability zone in the east cost. Each virtual machine has 2 cores and 7.5GB of memory. The total size of disk storage available is 14.78TB.

In both experiments, Cassandra is configured in order to have a replication factor of 5. Moreover, "OldNetwork-TopologyStrategy" was chosen as a replication strategy. This strategy ensures that data is replicated over all the clusters and racks. We deployed Cassandra on the two clusters on the Grid'5000 and on the 20 nodes of Amazon EC2. We use YCSB with workload-A which provides a heavy readupdate data access. For the experiments that were conducted on Grid'5000, we initially inserted a load of 3 million rows and a total size of 14.3GB after replication. Each workload run had a total of 3 million operations consisting of reads and updates. While for the experiments that were conducted on Amazon EC2, an initial load of 5 million rows, with a total size of 23.85GB after replication, was inserted. Each workload that was run consisted of 10 million operations.

D. Stale Reads Estimation in Harmony

We first study the impacts of the workload access patterns, the number of clients, and network latency on the stale reads estimation. Accordingly, we used two workloads: workload-A, which has a heavy read-update access pattern, and workload-B, which has a heavy read access pattern with a small portion of writes representing approximately 5% of the total number of operations. We ran both workloads, varying the number of threads starting with 90 threads, then, 70, 40, 15 and finally, one thread. The impacts of workloads' access patten and client number. As shown in Figure 4(a), the probability of reading stale data for workload-B is relatively smaller than the one for workload-A. This is because the number of updates is smaller. We observe that the number of updates plays very important role in causing stale reads even with a high number of reads. Moreover, we observe that the probability of reading stale data varies according to the number of threads. We can see that for workload-A, the probability of stale reads gradually decreases with the number of threads, because increasing the thread number increases the throughput and thus increases the reads and writes rate. Also, we notice the probability reduction gap is big during the transaction (changing the number of threads). The impacts of network latency. In order to see the impact of network latency on the stale reads estimation we ran workload-A -varying the number of threads starting with (d) Throughput on Amazon EC2 Figure 5. Latency and throughput in Harmony with S% tolerable stale reads (Harmony-S% Tolerable SR) against strong and eventual consistency on our both testbeds: Grid'5000 and Amazon EC2 90 threads, then, 70, 40, 15 and finally, one thread-on Amazon EC2 and measure the network latency during the run-time. Figure 4(b) presents the results. We can see that high network latency causes higher stale reads regardless of the number of the threads (higher latency dominates the probability of stale reads), while when the latency is small the probability will be varied according to the reads and writes rates (with smaller impacts of the network latency).

E. Latency and throughput of the applications in harmony

As mentioned earlier, in Harmony, the application requirements are defined as the stale reads rate that an application can tolerate during its running. Accordingly, we compare Harmony with two settings (two different tolerable stale read rates) with strong and eventual consistency on our both storage approaches (Grid'5000 and Amazon EC2). The first tolerable stale read rates are 40% for Grid'5000 and 60% for Amazon EC2 (these rates tolerate more staleness in the system implying lower consistency levels and thus less waiting time), and the second tolerable stale read rates are 20% for Grid'5000 and 40% for Amazon EC2 (these rates are more restrictive than the first ones, meaning that the number of read operations performed with a higher level of consistency is larger). Network latency is higher in Amazon EC2 than in Grid'5000 (5 times higher in the normal case), thus we choose higher stale read rate for the same workload with Amazon EC2. We run workload-A while varying the number of client threads.

Figures 5(a) and 5(b) presents the 99th percentile latency of read operations when the number of client threads increases on Grid'5000 and EC2 respectively. While the strong consistency approach provides the highest latency having all the reads to wait for the replies from all the replicas spread over different racks, the eventual consistency approach is the one that provides less latency because all the read operations are performed on one close replica but at the cost of consistency violation. We can clearly see that Harmony with both settings provides almost the same latency as the eventual consistency. Moreover, the latency increases by decreasing the tolerable stale reads rate of an application as the probability of stale read can easily get higher than these rates, which requires a higher consistency levels and, as a result, a higher latency.

In Figures 5(c) and 5(d), we show the overall throughput for read and write operations with different numbers of client threads. The throughput increases as the number of threads increases. However, the throughput decreases with more than 90 threads. This is because the number of client threads is higher than the number of storage hosts and threads are served concurrently. We can observe that the throughput is smaller with strong consistency. The fact that read operations with higher consistency levels have high latencies, makes the number of possible operations per second smaller. We can notice that our approach with a stale reads rate of 40% and 60% for Grid'5000 and Amazon EC2 respectively, provide very good throughput that can be compared to the one of static eventual consistency approach. But, while exhibiting very good throughputs, our adaptive policies provide a better consistency and fewer stale reads due to the fact that higher consistency levels are chosen only when it matters.

F. Actual Staleness in Harmony

In Figures 6(a) and 6(b) , we show that Harmony, with all the policies with different application tolerated stale reads rates, provides less stale reads than the eventual consistency approach. Moreover, we can see that, with a more restrictive tolerated stale reads rate, we get a smaller number of stale reads. We observe that with rates of 20% and 40% for Grid'5000 and Amazon EC2 respectively, the number of stale reads decreases when the number of threads grows over 40 threads. This is explained by the fact that with more than 40 threads the estimated rate of stale reads gets higher than 20% and 40% respectively, for most of the run time, and higher consistency levels are chosen, thus decreasing the number of stale reads. It needs to be pointed out that this number of stale reads is not the actual number of stale reads in the system in the normal run, but it is representative.

In fact, to measure the number of stale reads, we perform two read operations for every read operation in the workload. The first read is performed with the relevant consistency level chosen by our approach, and the second read is performed with the strongest consistency level. Then, we compare the returned timestamps from both reads, and if they do not match, it means that the read is stale. Although this helps to estimate the number of stale reads, it completely changes the latency of reads and the throughput in the system. Moreover, it directly affects the monitoring data about system state. Additionally, the second read with strong consistency level provides more time for the next write to be propagated to the other replicas and, thus more chances for the next read to be fresh.

VI. RELATED WORK

Eventual consistency was employed in cloud storage system as an alternative to traditional strong consistency to achieve scalable and high-performance services [START_REF] Vogels | Eventually consistent[END_REF]. Many commercial cloud storage systems have already adopted the eventual consistency approach such as Dynamo [START_REF] Decandia | Dynamo: amazon's highly available key-value store[END_REF] in Amazon S3 [START_REF]Amazon Simple Storage Service (Amazon S3)[END_REF], Cassandra [START_REF] Lakshman | Cassandra: a decentralized structured storage system[END_REF] in Facebook [START_REF]Facebook Statistcs[END_REF] and PNUTS [START_REF] Cooper | Pnuts: Yahoo!s hosted data serving platform[END_REF] in Yahoo!. A fair number of studies have been dedicated to measuring the actual provided consistency in cloud storage platforms [START_REF] Wada | Data consistency properties and the trade-offs in commercial cloud storage: the consumers' perspective[END_REF][34] [START_REF] Bermbach | Eventual consistency: How soon is eventual? an evaluation of amazon s3's consistency behavior[END_REF]. Wada et al. [START_REF] Wada | Data consistency properties and the trade-offs in commercial cloud storage: the consumers' perspective[END_REF] investigate the consistency properties provided by commercial storage systems and report on how and under what circumstances consumer may encounter stale data. Also, they explore the performance gain of using weaker consistency constraints. Anderson et al. [START_REF] Anderson | What consistency does your key-value store actually provide?[END_REF] propose an offline consistency verification algorithm and test three kind of consistency semantics on registers including safety, regularity, and atomicity in the Pahoehoe key-value store using a benchmark similar to YCSB [START_REF] Cooper | Benchmarking cloud serving systems with ycsb[END_REF]. They observed that consistency violations increase with the contention of accesses to the same key.

Moreover, in order to meet the consistency requirements of applications and reduce the consistency violation, some studies are done on adaptive consistency tuning in cloud storage systems [START_REF] Kraska | Consistency rationing in the cloud: pay only when it matters[END_REF] [37] [START_REF] Wang | An applicationbased adaptive replica consistency for cloud storage[END_REF]. Kraska et al. [START_REF] Kraska | Consistency rationing in the cloud: pay only when it matters[END_REF] propose a flexible consistency management that is able to adapt the resulting consistency level to the requirements stated by applications. The inconsistencies considered in their work are due to update conflicts. Accordingly, they build a theoretical model to compute the probability of update conflict, and then compare it to a threshold. As a result, they choose either serializability using strong consistency or session consistency, which is a weaker consistency. However, besides that their approach cannot be applied with eventual consistency as weaker consistency because: in eventual consistency, the staleness is due to the update propagation latency rather than just the conflict of two or more updates on different replicas. The threshold -used to determine the type of consistencyis computed based on the financial cost of pending update queues and not related to the storage backend itself. Wang et al. [START_REF] Wang | An applicationbased adaptive replica consistency for cloud storage[END_REF] propose an application-based adaptive mechanism of replica consistency. This mechanism was proposed with a specific replication architecture. The architecture relies on multi-primary replicas and secondary replicas where the latter are read-only replicas. Consistency is either strong or eventual and the choice between the two is made by comparing the read rate and the write rate to a threshold. The main limitation of this work is the arbitrary choice of a static threshold. In addition, this approach was proposed for their specific proposed replication architecture, which is not commonly used in current cloud storage solutions.

In contrast to the aforementioned work, Harmony is using the stale reads rate to define the consistency requirements of the application. Moreover, it dynamically alters the replicas number involved in an operation according to the estimated stale reads rate and the network latency, during run-time. Thus Harmony achieves adequate tradeoffs between consistency and both performance and availability.

VII. CONCLUSION

With the explosion of cloud storage businesses and the increasing number of web services migrating to the cloud, a strong consistency model becomes very costly when scalability and availability are required. Thus, weaker consistency models have been proposed, but these models may lead to far too much inconsistency in the system. In this paper, we present Harmony, a novel approach that handles data consistency in cloud storage adaptively by choosing the most appropriate consistency level dynamically at run time. In Harmony, we collect relevant information about the storage system in order to estimate the stale read rate when consistency is eventual, and make a decision accordingly. In order to be application-adaptive, Harmony takes into account the application's needs expressed by the stale read rate that can be tolerated. We show that our approach provides better performance than traditional approaches that are based on strong consistency. Moreover, it provides more adequate consistency than eventual consistency approaches. In addition, our solution is designed to be completely tunable to provide the system or the application administrator with the possibility of controlling the degree of compromise between performance and consistency.

For future work, we plan to provide a mechanism allowing the system to automatically divide data into different consistency categories without any human interaction by applying clustering techniques. Every category should be given the most appropriate consistency level in regard to the data it encloses. Another enhancement is to propose a mechanism that models the application and computes the stale read rate that can be tolerated automatically.

Figure 2 .

 2 Figure 2. Situation that leads to a stale read

Figure 4 .

 4 Figure 4. Stale read rate estimation in Harmony: (a) We show the impacts of both the workloads' access pattern and the number of client threads on the stale read estimation used in Harmony: We used Grid'5000 as we can guarantee the network latency. (b) We show the impact of network latency on the stale read estimation: the variability on EC2 network latency.

Figure 6 .

 6 Figure 6. Staleness in Harmony with S% tolerable stale reads (Harmony-S% Tolerable SR) against strong and eventual consistency.

Interestingly, Windows Azure Storage (WAS)[START_REF] Calder | Windows azure storage: a highly available cloud storage service with strong consistency[END_REF] and Scatter[START_REF] Glendenning | Scalable consistency in scatter[END_REF] are distributed storage systems that strongly rely on Paxos[START_REF] Lamport | Paxos made simple[END_REF] to simultaneously offer consistency and availability while tolerating faults in largescale settings, but with an extra cost on performance in contrast to eventual consistency[START_REF] Rao | Using paxos to build a scalable, consistent, and highly available datastore[END_REF].

ACKNOWLEDGMENTS

This work has been supported by the EU FP7 MCITN SCALUS project under grant agreement no. 238808 and by the HEMERA Large Wingspan Action led by INRIA. The experiments presented in this paper were carried out using the Grid'5000/ALADDIN-G5K experimental testbed. We would like to thank Louis-Claude Canon and Jésus Montes for helpful discussions and precious suggestions.