Jean-Baptiste Bardet

Alejandra Christen

Arnaud Guillin

Florent Malrieu

Pierre-André Zitt

Total variation estimates for the TCP process

Keywords: Network Protocols, Queueing Theory, Additive Increase Multiplicative Decrease Processes (AIMD), Piecewise Deterministic Markov Processes (PDMP), Exponential Ergodicity, Coupling AMS-MSC. 68M12, 60K30, 60K25, 90B18

The TCP window size process appears in the modeling of the famous Transmission Control Protocol used for data transmission over the Internet. This continuous time Markov process takes its values in [0, ∞), is ergodic and irreversible. The sample paths are piecewise linear deterministic and the whole randomness of the dynamics comes from the jump mechanism. The aim of the present paper is to provide quantitative estimates for the exponential convergence to equilibrium, in terms of the total variation and Wasserstein distances.

Introduction and main results

The TCP protocol is one of the main data transmission protocols of the Internet. It has been designed to adapt to the various traffic conditions of the actual network. For a connection, the maximum number of packets that can be sent at each round is given by a variable W , called the congestion window size. If all the W packets are successfully transmitted, then W is increased by 1, otherwise it is divided by 2 (detection of a congestion). As shown in [DGR02, [START_REF] Guillemin | AIMD algorithms and exponential functionals[END_REF][START_REF] Ott | The stationary behavior of ideal TCP congestion avoidance[END_REF], a correct scaling of this process leads to a continuous time Markov process, called the TCP window size process. This process X = (X t ) t 0 has [0, ∞) as state space and its infinitesimal generator is given, for any smooth function f : [0, ∞) → R, by Lf (x) = f (x) + x(f (x/2) -f (x)).

(1)

The semi-group (P t ) t 0 associated to (X t ) t 0 is classically defined by

P t f (x) = E(f (X t )|X 0 = x),
for any smooth function f . Moreover, for any probability measure ν on [0, ∞), νP t stands for the law of X t when X 0 is distributed according to ν.

The process X t increases linearly between jump times that occur with a state-dependent rate X t . The first jump time of X starting at x 0 has the law of √ 2E + x 2 -x where E is a random variable with exponential law of parameter 1. In other words, the law of this jump time has a density with respect to the Lebesgue measure on (0, +∞) given by f x : t ∈ (0, +∞) → (x + t)e -t 2 /2-xt ,

(2) see [START_REF] Chafaï | On the long time behavior of the TCP window size process[END_REF] for further details. The sample paths of X are deterministic between jumps, the jumps are multiplicative, and the whole randomness of the dynamics relies on the jump mechanism. Of course, the randomness of X may also come from a random initial value. The process (X t ) t 0 appears as an Additive Increase Multiplicative Decrease process (AIMD), but also as a very special Piecewise Deterministic Markov Process (PDMP). In this direction, [MZ09] gives a generalization of the scaling procedure to interpret various PDMPs as limits of discrete time Markov chains. In the real world (Internet), the AIMD mechanism allows a good compromise between the minimization of network congestion time and the maximization of mean throughput. One could consider more general processes (introducing a random multiplicative factor or modifying the jump rate) but their study is essentially the same than the one of the present process.

The TCP window size process X is ergodic and admits a unique invariant law µ, as can be checked using a suitable Lyapunov function (for instance V (x) = 1 + x, see e.g. [START_REF] Bakry | Rate of convergence for ergodic continuous Markov processes: Lyapunov versus Poincaré[END_REF][START_REF] Costa | Stability and ergodicity of piecewise deterministic Markov processes[END_REF][START_REF] Meyn | Markov chains and stochastic stability[END_REF][START_REF] Hairer | Yet another look at Harris' ergodic theorem for Markov chains[END_REF] for the Meyn-Tweedie-Foster-Lyapunov technique). It can also be shown that µ has a density on (0, +∞) given by

x ∈ (0, +∞) → 2/π n 0 1 -2 -(2n+1) n 0 (-1) n 2 2n n k=1 (2 2k -1) e -2 2n-1 x 2 , (3)
(this explicit formula is derived in [DGR02, Prop. 10], see also [GRZ04, MZ09, MZ06, GK09] for further details). In particular, one can notice that the density of µ has a Gaussian tail at +∞ and that all its derivatives are null at the origin. Nevertheless, this process is irreversible since time reversed sample paths are not sample paths and it has infinite support (see [START_REF] Löpker | On Time Reversal of Piecewise Deterministic Markov Processes[END_REF] for the description of the reversed process). In [RR96], explicit bounds for the exponential rate of convergence to equilibrium in total variation distance are provided for generic Markov processes in terms of a suitable Lyapunov function but these estimates are very poor even for classical examples as the Ornstein-Uhlenbeck process.

They can be improved following [RT00] if the process under study is stochastically monotone that is if its semi-group (P t ) t 0 is such that x → P t f (x) is nondecreasing as soon as f is nondecreasing. Unfortunately, due to the fact that the jump rate is an nondecreasing function of the position, the TCP process is not stochastically monotone. Moreover, we will see that our coupling provides better estimates for the example studied in [RT00].

The work [START_REF] Chafaï | On the long time behavior of the TCP window size process[END_REF] was a first attempt to use the specific dynamics of the TCP process to get explicit rates of convergence of the law of X t to the invariant measure µ. The answer was partial and a bit disappointing since the authors did not succeed in proving explicit exponential rates.

Our aim in the present paper is to go one step further providing exponential rate of convergence for several classical distances: Wasserstein distance of order p 1 and total variation distance. Let us recall briefly some definitions.

Definition 1.1. If ν and ν are two probability measures on R, we will call a coupling of ν and ν any probability measure on R × R such that the two marginals are ν and ν. Let us denote by Γ(ν, ν) the set of all the couplings of ν and ν.

Definition 1.2. For every p 1, the Wasserstein distance W p of order p between two probability measures ν and ν on R with finite p th moment is defined by

W p (ν, ν) = inf Π∈Γ(ν,ν) R 2 |x -y| p Π(dx, dy) 1/p . (4)
Definition 1.3. The total variation distance between two probability measures ν and ν on R is given by

ν -ν TV = inf Π∈Γ(ν,ν) R 2 1 {x =y} Π(dx, dy).
It is well known that, for any p 1, the convergence in Wasserstein distance of order p is equivalent to weak convergence together with convergence of all moments up to order p, see e.g. [Rac91,[START_REF] Villani | Topics in optimal transportation[END_REF]. A sequence of probability measures (ν n ) n 1 bounded in L p which converges to ν in total variation norm converges also for the W p metrics. The converse is false: if ν n = δ 1/n then (ν n ) n 1 converges to δ 0 for the distance W p whereas ν n -δ 0 TV is equal to 1 for any n 1.

Any coupling (X, X) of (ν, ν) provides an upper bound for these distances. One can find in [START_REF] Lindvall | Lectures on the coupling method[END_REF] a lot of efficient ways to construct smart couplings in many cases. In the present work, we essentially use the coupling that was introduced in [START_REF] Chafaï | On the long time behavior of the TCP window size process[END_REF]. Firstly, we improve the estimate for its rate of convergence in Wasserstein distances from polynomial to exponential bounds.

Theorem 1.4. Let us define M = √ 2(3 + √ 3) 8 ∼ 0.84 and λ = √ 2(1 - √ M ) ∼ 0.12. ( 5
)
For any λ < λ, any p 1 and any t 0 > 0, there is a constant C = C(p, λ, t 0 ) such that, for any initial probability measures ν and ν and any t t 0 ,

W p (νP t , νP t ) C exp - λ p t .
Secondly, we introduce a modified coupling to get total variation estimates.

Theorem 1.5. For any λ < λ and any t 0 > 0, there exists C such that, for any initial probability measures ν and ν and any t t 0 ,

νP t -νP t TV C exp - 2 λ 3 t ,
where λ is given by (5).

Remark 1.6. In both Theorems 1.4 and 1.5, no assumption is required on the moments nor regularity of the initial measures. Note however that following Remark 3.4, one can obtain contraction's type bounds when the initial measures ν and ν have initial moments of sufficient orders. In particular they hold uniformly over the Dirac measures. If ν is chosen to be the invariant measure µ, these theorems provide exponential convergence to equilibrium.

The remainder of the paper is organized as follows. We derive in Section 2 precise upper bounds for the moments of the invariant measure µ and the law of X t . Section 3 and Section 4 are respectively devoted to the proofs of Theorem 1.4 and Theorem 1.5. Unlike the classical approach "à la" Meyn-Tweedie, our total variation estimate is obtained by applying a Wasserstein coupling for most of the time, then trying to couple the two paths in one attempt. This idea is then adapted to others processes: Section 5 deals with two simpler PDMPs already studied in [PR05, LP09, CMP10, RT00] and Section 6 is dedicated to diffusion processes.

Moment estimates

The aim of this section is to provide accurate bounds for the moments of X t . In particular, we establish below that any moment of X t is bounded uniformly over the initial value X 0 . Let p > 0 and α p (t) = E(X p t ). Then one has by direct computation

α p (t) = pα p-1 (t) -1 -2 -p α p+1 (t). ( 6
)
2.1 Moments of the invariant measure Equation (6) implies in particular that, if m p denotes the p-th moment of the invariant measure µ of the TCP process (m p = x p µ(dx)), then for any p > 0

m p+1 = p 1 -2 -p m p-1 .
It gives all even moments of µ: m 2 = 2, m 4 = 48 7 , . . . and all the odd moments in terms of the mean. Nevertheless, the mean itself cannot be explicitly determined. Applying the same technique to log X t , one gets the relation log(2)m 1 = m -1 . With Jensen's inequality, this implies that 1/ √ log 2 m 1 √ 2.

Uniform bounds for the moments at finite times

The fact that the jump rate goes to infinity at infinity gives bounds on the moments at any positive time that are uniform over the initial distribution.

Lemma 2.1. For any p 1 and t > 0

M p,t := sup x 0 E x (X p t ) 2p + 2p t p .
Proof. One deduces from (6) and Jensen's inequality that

α p (t) pα p (t) 1-1/p -(1 -2 -p )α p (t) 1+1/p .
Let β p (t) = α p (t) 1/p -√ 2p. Then, using the fact that 1 -2 -p 1 2 ,

β p (t) = 1 p α p (t) 1/p-1 α p (t) 1 - 1 2p α p (t) 2/p = - 2 p β p (t) - β p (t) 2 2p .
In particular, β p (t) < 0 as soon as β p (t) > 0.

Let us now fix t > 0. If β p (t) 0, then α p (t) (2p) p/2 and the lemma is proven. We assume now that β p (t) > 0. By the previous remark, this implies that the function s → β p (s) is strictly decreasing, hence positive, on the interval [0, t]. Consequently, for any s ∈ [0, t],

β p (s) - β p (s) 2 2p .
Integrating this last inequality gives 1 β p (t)

1 β p (0) + t 2p t 2p ,
hence the lemma.

Let us derive from Lemma 2.1 some upper bounds for the right tails of δ x P t and µ.

Corollary 2.2. For any t > 0 and r 2e(1 + 1/t), one has

P x (X t r) exp - t 2e(t + 1) r . (7)
Moreover, if X is distributed according to the invariant measure µ then, for any r √ 2e, one has

P(X r) exp - r 2 4e .
Proof. Let t > 0 and a = 2(1 + 1/t). Notice that, for any p 1, E x (X p t ) is smaller than (ap) p . As a consequence, for any p 1 and r 0, P x (X t r) exp (p log(ap/r)).

Assuming that r ea, we let p = r/(ea) to get:

P x (X t r) e -r/(ea) .
For the invariant measure, the upper bound is better: E(X p ) (2p) p/2 . Then, the Markov inequality provides that, for any p 1,

P(X r) exp p log √ 2p r .
As above, if r 2 2e, one can choose p = r 2 /(2e) to get the desired bound.

Remark 2.3. A better deviation bound should be expected from the expression (3) of the density of µ. Indeed, one can get a sharp result (see [START_REF] Chafaï | On the long time behavior of the TCP window size process[END_REF]). However, in the sequel we only need the deviation bound (7).

Exponential convergence in Wasserstein distance

This section is devoted to the proof of Theorem 1.4. We use the coupling introduced in [START_REF] Chafaï | On the long time behavior of the TCP window size process[END_REF]. Let us briefly recall the construction and the dynamics of this stochastic process on R 2 + whose marginals are two TCP processes. It is defined by the following generator

Lf (x, y) = (∂ x + ∂ y )f (x, y) + y f (x/2, y/2) -f (x, y) + (x -y) f (x/2, y) -f (x, y)
when x y and symmetric expression for x < y. We will call the dynamical coupling defined by this generator the Wasserstein coupling of the TCP process (see Figure 1 for a graphical illustration of this coupling). This coupling is the only one such that the lower component never jumps alone. Let us give the pathwise interpretation of this coupling. Between two jump times, the two coordinates increase linearly with rate 1. Moreover, two "jump processes" are simultaneously in action:

1. with a rate equal to the minimum of the two coordinates, they jump (i.e. they are divided by 2) simultaneously, 2. with a rate equal to the distance between the two coordinates (which is constant between two jump times), the bigger one jumps alone. The existence of non-simultaneous jumps implies that the generator does not act in a good way on functions directly associated to Wasserstein distances. To see this, let us define V p (x, y) = |x -y| p . When we compute LV p , the term coming from the deterministic drift disappears (since V p is unchanged under the flow), and we get for x/2 y x:

LV p (x, y) = -y(1 -2 -p )V p (x, y) + (x -y)((y -x/2) p -(x -y) p ).
For example, choosing p = 1 gives:

LV 1 (x, y) = -V 1 (x, y)(y/2 -(y -x/2) + (x -y)) = -(3/2)V 1 (x, y) 2 . This shows that E[|X t -Y t |]
decreases, but only gives a polynomial bound: the problem comes from the region where x -y is already very small.

Choosing p = 2, we get

LV 2 (x, y) = -(3/4)yV 2 (x, y) + (x -y)(-(3/4)x 2 + xy).
The effect of the jumps of X is even worse: if x = 1 and x -y is small, LV 2 (x, y) is positive (≈ (1/4)(x -y)).

For p = 1/2, the situation is in fact more favorable: indeed, for 0 < y x,

LV 1/2 (x, y) = -y 1 - √ 2 2 V 1/2 (x, y) + (x -y)( |y -x/2| - √ x -y) = -V 1/2 (x, y) x - √ 2 2 y -(x -y)(y -x/2) = -x 1 -ϕ y x V 1/2 (x, y) , with ϕ(u) = √ 2 2 u + (1 -u)|u -1/2| for u ∈ [0, 1].
By a direct computation, one gets that

M := max 0 u 1 ϕ(u) = ϕ 9 + √ 3 12 = √ 2(3 + √ 3) 8 ∼ 0.8365.
Hence, when 0 < y x,

LV 1/2 (x, y) -xλV 1/2 (x, y), (8)
with λ = 1 -M ∼ 0.1635. This would give an exponential decay for V 1/2 if x was bounded below: the problem comes from the region where x is small and the process does not jump.

To overcome this problem, we replace V 1/2 with the function

V (x, y) = ψ(x ∨ y)|x -y| 1/2 = ψ(x ∨ y)V 1/2 (x, y),
where

ψ(x) = 1 + α(1 -x/x 0 ) 2 , x x 0 , 1, x x 0 ,
the two positive parameters α and x 0 being chosen below. The negative slope of ψ for x small will be able to compensate the fact that the bound from (8) tends to 0 with x, hence to give a uniform bound. Indeed, for 0 < y x,

L V (x, y) = ψ (x)(x -y) p + yψ(x/2) (x -y) p 2 p + (x -y)ψ(x/2 ∨ y)|x/2 -y| p -x V (x, y) = -V (x, y) - ψ (x) ψ(x) + x - ψ(x/2) ψ(x) y 2 p - ψ(x/2 ∨ y) ψ(x) (x -y) 1-p |x/2 -y| p -V (x, y) - ψ (x) ψ(x) + x 1 - ψ(x/2) ψ(x) ϕ y x -V (x, y) - ψ (x) (1 + α) + x (1 -(1 + α)M ) = -V (x, y) 2α x 0 (1+α) + x 1 -(1 + α)M -2α x 2 0 (1+α) when x x 0 , -V (x, y)x (1 -(1 + α)M ) when x x 0 .
Finally, as soon as (1 + α)M < 1, one has

L V (x, y) -λ α,x 0 V (x, y) ∀x, y > 0 with λ α,x 0 = min 2α x 0 (1 + α) , x 0 (1 -(1 + α)M ) .
By direct computations, one gets that the best possible choice of parameters α and x 0 is α = 1/ √ M -1 ∼ 0.0934 and x 0 = √ 2. We obtain finally, for any x, y > 0,

L V (x, y) -λ V (x, y), (9)
with λ = λ α,x 0 = √ 2(1 - √ M ) ∼ 0.
1208. Hence, directly from (9), for any x, y > 0

E x,y [ V (X t , Y t )] e -λt V (x, y). ( 10
)
Immediate manipulations lead to the following estimate.

Proposition 3.1. Let M = √ 2(3 + √ 3) 8 ∼ 0.84 and λ = √ 2(1 - √ M ) ∼ 0.12. ( 11
)
Then, for any x, y > 0, one has

E x,y |X t -Y t | 1/2 1 √ M e -λt |x -y| 1/2 . ( 12
)
Moreover, for any initial conditions (X 0 , Y 0 ) and any t t 0 > 0,

E |X t -Y t | 1/2 2 √ 2 + 4t -1 0 M e -λ(t-t 0 ) . ( 13
)
Proof. Equation ( 12) is a straightforward consequence of Equation (9) since ψ(R + ) is the interval [1, 1 + α]. As a consequence, for any t t 0 > 0, one has

E |X t -Y t | 1/2 1 √ M e -λ(t-t 0 ) E |X t 0 -Y t 0 | 1/2 e λt 0 √ M E(X t 0 ) + E(Y t 0 )e -λt .
Then, Lemma 2.1 provides the estimate (13).

Remark 3.2. The upper bound obtained in Proposition 3.1 is compared graphically to the "true" function t → E x,y |X t -Y t | 1/2 in Figure 2. By linear regression on this data, one gets that the exponential speed of convergence of this function is on the order of 0.4. Note also that this method can be adapted to any V p with 0 < p < 1, giving even better (but less explicit) speed of convergence for some p = 1 2 : we estimated numerically that the best value for λ would be approximately 0.1326, obtained for p close to 2/3.

We may now deduce from Proposition 3.1 estimates for the Wasserstein distance between the laws of X t and Y t . Then, for any t 0 > 0 and any θ ∈ (0, 1), there exists C(p, t 0 , θ) < +∞ such that, for any initial conditions (X 0 , Y 0 ) and for all t t 0 ,

E(|X t -Y t | p ) C(p, t 0 , θ) exp (-λθt)
where λ is defined by (11).

Proof of Theorem 3.3. Let p 1. For any 0 < θ < 1, Hölder's inequality gives, for any t 0,

E(|X t -Y t | p ) E |X t -Y t | 2p-θ 2(1-θ) 1-θ E |X t -Y t | 1/2 θ .
Thanks to Lemma 2.1 and the inequality (a + b) q 2 q-1 (a q + b q ), when q 1, one gets

E |X t -Y t | 2p-θ 2(1-θ) 1-θ 2 2p-θ 2(1-θ) M 2p-θ 2(1-θ) ,t 1-θ 2 p-θ/2 2p -θ 1 -θ + 2p -θ (1 -θ)t p-θ/2
.

Then, it suffices to use Equation (13) to conclude the proof with

C(p, t 0 , θ) = 2 p M θ/2 2p -θ 1 -θ + 2p -θ (1 -θ)t 0 p-θ/2 √ 2 + 2 t 0 θ/2 e λθt 0 . Since W p (L(X t ), L(Y t )) p E(|X t -Y t | p ), Theorem 1.4 is a direct consequence of this result.
Remark 3.4. Let us remark that we can obtain "contraction's type bounds" using Equation (12) instead of (13) : for any p 1, any 0 < θ < 1, any t 0 and any x, y > 0,

E x,y (|X t -Y t | p ) 2 p-θ/2 M θ/2 2p -θ 1 -θ + 2p -θ (1 -θ)t p-θ/2 e -λθt |x -y| θ/2 .
We then obtain that if ν and ν have finite θ/2-moments then for p 1 and t 0,

W p (νP t , νP t )   2 p-θ/2 M θ/2 2p -θ 1 -θ + 2p -θ (1 -θ)t p-θ/2   1 p e -λθ p t W θ 2 (ν, ν) 2 pθ .
which still allows a control by some Wasserstein "distance" (in fact, this is not a distance, since θ/2 < 1) of the initial measures.

Remark 3.5. We estimated numerically the exponential speed of convergence:

• of the function t → E x,y (|X t -Y t |)
for the Wasserstein coupling (by Monte Carlo method and linear regression). It seems to be on the order of 0.5 (we obtained 0.48 for x = 2, y = 10, m = 10 000 copies, and linear regression between times 2 and 10);

• of the Wasserstein distance t → W 1 (δ x P t , δ y P t ), using the explicit representation of this distance for measures on R to approximate it by the L 1 -distance between the two empirical quantile functions. It is on the order of 1.6 (we get 1.67 for x = 2, y = 0.5, m = 1 000 000 copies, and linear regression on 20 points until time 4).

In conclusion, our bound from Theorem 3.3 seems reasonable (at least when compared to those given by [RR96], see section 4.2 below), but is still off by a factor of 4 from the true exponential speed of convergence. Since the coupling itself seems to converge approximately 3 times slower than the true Wasserstein distance, one probably needs to find another coupling to get better bounds.

Remark 3.6. Let us end this section by advertising on a parallel work by B. Cloez [START_REF] Cloez | Wasserstein decay of one dimensional jump-diffusions[END_REF] who uses a completely different approach, based on a particular Feynman-Kac formulation, to get some related results.

Exponential convergence in total variation distance

In this section, we provide the proof of Theorem 1.5 and we compare our estimate to the ones that can be deduced from [RR96].

From Wasserstein to total variation estimate

The fact that the evolution is partially deterministic makes the study of convergence in total variation quite subtle. Indeed, the law δ x P t can be written as a mixture of a Dirac mass at x + t (the first jump time has not occured) and an absolutely continuous measure (the process jumped at some random time in (0, t)):

δ x P t = p t (x)δ x+t + (1 -p t (x))L(X t |X 0 = x, T 1 t)
where, according to Equation (2),

p t (x) := P x (T 1 > t) = e -t 2 /2-xt . ( 14
)
This implies that the map y → δ x P t -δ y P t TV is not continuous at point x since one has, for any y = x,

δ x P t -δ y P t TV p t (x) ∨ p t (y) = e -t 2 /2-(x∧y)t .
Nevertheless, one can hope that

δ x P t -δ y P t TV ∼ y→x p t (x).
The lemma below makes this intuition more precise.

Lemma 4.1. Let t ε x-y > 0. There exists a coupling (X t ) t 0 , (Y t ) t 0 of two TCP processes driven by (1) and starting at (x, y) such that the probability P(X s = Y s , s t) is larger than

q t (x, y) = t x-y (f x (s) ∧ f y (s -x + y)) ds p x-y x + t 2 (p ε (x) -p t (x) -2εα(x))p ε x + t 2 , ( 15
)
where f x is defined in Equation (2) and α(x) := ∞ 0 e -u 2 /2-ux du. Moreover, for any x 0 > 0 and ε > 0, let us define

A x 0 ,ε = {(x, y) : 0 x, y x 0 , |x -y| ε}. ( 16
)
Then,

inf (x,y)∈Ax 0 ,ε q t (x, y) exp -ε 2 - 3x 0 + t 2 ε -e -t 2 /2 - √ 2πε.
Proof. The idea is to construct an explicit coalescent coupling starting from x and y. The main difficulty comes from the fact that the jump are deterministic. Assume for simplicity that y < x. Let us denote by (T x k ) k 1 and (T y k ) k 1 the jump times of the two processes. If

T x 1 = T y 1 + x -y and T y 2 -T y 1 x -y (17)
then the two paths are at the same place at time T x 1 since in this case

X T x 1 = x + T x 1 2 = y + T y 1 2 + T x 1 -T y 1 = Y T x 1 .
The law of T x 1 has a density f x given by (2). As a consequence, the density of T 1 y + x -y is given by s → f y (s -x + y). The best way of obtaining the first equality in (17) before a time t x -y is to realize an optimal coupling of the two continuous laws of T x 1 and T y 1 + x -y. This makes these random variables equal with probability

I(x, y, t) = t x-y (f x (s) ∧ f y (s -x + y)) ds.
Assume now that 0 x -y ε t. For any s x -y, one has

f y (s -x + y) = (2y -x + s) exp - 1 2 (s -x + y) 2 -y(s -x + y) = (s + x -2(x -y)) exp - s 2 2 -xs + (2s + x -3(x -y)/2)(x -y) (s + x -2ε) exp - s 2 2 -xs .
As a consequence, if 0 x -y ε t, I(x, y, t)

t x-y (s + x -2ε) exp - s 2 2 -xs ds p ε (x) -p t (x) -2εα(x)
where p t (x) is defined in (14) and α(x) = ∞ 0 e -u 2 /2-ux du. Finally, one has to get a lower bound for the probability of the set {T y 2 -T y 1

x -y}. For this, we notice that

z ∈ [0, +∞) → P(T z 1 s) = p s (z) = e -s 2 /2-sz
is decreasing and that Y T y 1 (y + t)/2 as soon as T y 1 t. As a consequence, inf

0 z (x+t)/2 P(T z 1 s) p x-y x + t 2 p ε x + t 2 .
This provides the bound (15). The uniform lower bound on the set A x 0 ,ε is a direct consequence of the previous one.

Let us now turn to the proof of Theorem 1.5.

Proof of Theorem 1.5. We are looking for an upper bound for the total variation distance between δ x P t and δ y P t for two arbitrary initial conditions x and y. To this end, let us consider the following coupling: during a time t 1 < t we use the Wasserstein coupling. Then during a time t 2 = t -t 1 we try to stick the two paths using Lemma 4.1. Let ε > 0 and x 0 > 0 be as in Lemma 4.1. If, after the time t 1 , one has

(X t 1 , Y t 1 ) ∈ A ε,x 0
where A ε,x 0 is defined by (16), then the coalescent coupling will work with a probability greater than the one provided by Lemma 4.1. As a consequence, the coalescent coupling occurs before time t 1 + t 2 with a probability greater than

P((X t 1 , Y t 1 ) ∈ A ε,x 0 ) inf (x,y)∈Aε,x 0 q t 2 (x, y).
Moreover,

P((X t 1 , Y t 1 ) / ∈ A ε,x 0 ) P(X t 1 x 0 ) + P(Y t 1 x 0 ) + P(|X t 1 -Y t 1 | ε).
¿From the deviation bound (7), we get that, for any x 0 2e(1 + 1/t 1 ), P(X t 1 x 0 ) e -a(t 1 )x 0 with a(t 1 ) = t 1 2e(t 1 + 1) .

The estimate of Proposition 3.1 concerning the Wasserstein coupling ensures that

P(|X t 1 -Y t 1 | ε) C √ ε e -λt 1 with C = 2 √ 2 + 4t -1 0 M e λt 0 ,
for any 0 < t 0 t 1 . As a consequence, the total variation distance between δ x P t and δ y P t is smaller than

D := 1 -e -ε 2 -3x 0 +t 2 2 ε + e -t 2 2 /2 + √ 2πε + 2e -a(t 1 )x 0 + C √ ε e -λt 1 .
In order to get a more tractable estimate, let us assume that t 2

x 0 and use that 1 -e -u u to get

D ε 2 + 2εx 0 + e -t 2 2 /2 + √ 2πε + 2e -a(t 0 )x 0 + C √ ε e -λt 1 .
Finally let us set

t 2 = 2 log(1/ε), t 1 = 3 2λ log(1/ε), x 0 = 1 a(t 0 ) log(1/ε).
Obviously, for ε small enough, x 0 max(t 2 , 2e(1 + 1/t 1 )) and t 1 t 0 . Then, one gets that

δ x P t 1 +t 2 -δ y P t 1 +t 2 TV 2 a(t 0 ) ε log(1/ε) + (3 + C + √ 2π + ε)ε.
One can now express ε as a function of t 1 to get that there exists K = K(t 0 ) > 0 such that δ x P t 1 +t 2 -δ y P t 1 +t 2 TV K(1 + t 1 )e -2λ 3 t 1 .

Since t 2 = (4λ/3)t 1 , one gets that

δ x P t -δ y P t TV K(1 + t)e K √ t e -2λ 3 t .
This provides the conclusion of Theorem 1.5 when the initial measures are Dirac masses. The generalisation is straightforward.

A bound via small sets

We describe here briefly the approach of [RR96] and compare it with the hybrid Wasserstein/total variation coupling described above. The idea is once more to build a successful coupling between two copies X and Y of the process. In algorithmic terms, the approach is the following:

• let X and Y evolve independently until they both reach a given set C,

• once they are in C, try to stick them together,

• repeat until the previous step is successful.

To control the time to come back to C × C, [RR96] advocates an approach via a Lyapunov function. The second step works with positive probability if the set is "pseudo-small", i.e. if one can find a time t , an α > 0 and probability measures

ν xy ∀x, y ∈ C 2 , L(X t |X 0 = x) αν xy and L(X t |X 0 = y) αν xy . ( 18
)
The convergence result can be stated as follows.

Theorem 4.2 ([RR96], Theorem 3, Corollary 4 and Theorem 8).1 Suppose that there exists a set C, a function V 1, and positive constants λ, Λ such that

LV -λV + Λ1 C . ( 19
)
Suppose that δ = λ -Λ/ inf x / ∈C V > 0. Suppose additionally that C is pseudo-small, with constant α.

Then for A = Λ δ + e -δt sup x∈C V , A = Ae δt , and for any r < 1/t ,

L(X t ) -µ TV (1 -α) rt + e -δ(t-t ) (A ) rt -1 EV (X 0 ).
If A is finite, this gives exponential convergence: just choose r small enough so that (A ) rt e -δt decreases exponentially fast.

To compute explicit bounds we have to make choices for C and V and estimate the corresponding value of α. Our best efforts for the case of the TCP process only give decay rates of the order 10 -14 . We believe this order cannot be substantially improved even by fine-tuning C and V .

Two other models

This section is devoted to the study of two simple PDMPs. The first one is a simplified version of the TCP process where the jump rate is assumed to be constant and equal to λ. It has been studied with different approaches: PDE techniques (see [START_REF] Perthame | Exponential decay for the fragmentation or celldivision equation[END_REF][START_REF] Laurençot | Exponential decay for the growthfragmentation/cell-division equation[END_REF]) or probabilistic tools (see [START_REF] Van Leeuwaarden | Transient moments of the TCP window size process[END_REF][START_REF] Ott | Transient behavior of processes in the TCP paradigm[END_REF][START_REF] Chafaï | On the long time behavior of the TCP window size process[END_REF]). The second one is studied in [RT00]. It can also be checked that our method gives sharp bounds for the speed of convergence to equilibrium of the PDMP which appears in the study of a penalized bandit algorithm (see Lemma 7 in [LP08]).

The TCP model with constant jump rate

In this section we investigate the long time behavior of the TCP process with constant jump rate given by its infinitesimal generator:

Lf (x) = f (x) + λ(f (x/2) -f (x)) (x 0).
The jump times of this process are the ones of a homogeneous Poisson process with intensity λ. The convergence in Wasserstein distance is obvious.

Lemma 5.1 ([PR05, CMP10]). For any p 1,

W p (δ x P t , δ y P t ) |x -y|e -λpt with λ p = λ(1 -2 -p ) p . ( 20
)
Remark 5.2. The case p = 1 is obtained in [START_REF] Perthame | Exponential decay for the fragmentation or celldivision equation[END_REF] by PDEs estimates using the following alternative formulation of the Wasserstein distance on R. If the cumulative distribution functions of the two probability measures ν and ν are F and F then

W 1 (ν, ν) = R |F (x) -F (x)| dx.
The general case p 1 is obvious from the probabilistic point of view: choosing the same Poisson process (N t ) t 0 to drive the two processes provides that the two coordinates jump simultaneously and

|X t -Y t | = |x -y|2 -Nt .
As a consequence, since the law of N t is the Poisson distribution with parameter λt, one has

E x,y (|X t -Y t | p ) = |x -y| p E 2 -pNt = |x -y| p e -pλpt .
This coupling turns out to be sharp. Indeed, one can compute explicitly the moments of X t (see [START_REF] Van Leeuwaarden | Transient moments of the TCP window size process[END_REF][START_REF] Ott | Transient behavior of processes in the TCP paradigm[END_REF]): for every n 0, every x 0, and every t 0,

E x ((X t ) n ) = n! n k=1 θ k + n! n m=1 m k=0 x k k! n j=k j =m 1 θ j -θ m e -θmt , (21)
where θ n = λ(1 -2 -n ) = nλ n for any n 1. Obviously, assuming for example that x > y,

W n (δ x P t , δ y P t ) n E x ((X t ) n ) -E y ((Y t ) n ) ∼ t→∞ n! n k=0 x k -y k k! n-1 j=k 1 θ j -θ n e -θnt .
As a consequence, the rate of convergence in Equation ( 20) is optimal for any n 1. Nevertheless this estimate for the Wasserstein rate of convergence does not provide on its own any information about the total variation distance between δ x P t and δ y P t . It turns out that this rate of convergence is the one of the W 1 distance. This is established by Theorem 1.1 in [START_REF] Perthame | Exponential decay for the fragmentation or celldivision equation[END_REF]. It can be reformulated in our setting as follows.

Theorem 5.3 ([PR05]

). Let µ be the invariant measure of X. For any measure ν with a finite first moment and t 0,

νP t -µ TV e -λt/2 (3λW 1 (ν, µ) + ν -µ TV ).
Let us provide here an improvement of this result by a probabilistic argument.

Proposition 5.4. For any x, y 0 and t 0,

δ x P t -δ y P t TV λe -λt/2 |x -y| + e -λt . (22)
As a consequence, for any measure ν with a finite first moment and t 0,

νP t -µ TV λe -λt/2 W 1 (ν, µ) + e -λt ν -µ TV . (23)
Remark 5.5. Note that the upper bound obtained in Equation ( 22) is non-null even for x = y. This is due to the persistence of a Dirac mass at any time, which implies that taking y arbitrarily close to x for initial conditions does not make the total variation distance arbitrarily small, even for large times.

Proof of Proposition 5.4. The coupling is a slight modification of the one used to control Wasserstein distance. The paths of (X s ) 0 s t and (Y s ) 0 s t starting respectively from x and y are determined by their jump times (T X n ) n 0 and (T Y n ) n 0 up to time t. These sequences have the same distribution than the jump times of a Poisson process with intensity λ.

Let (N t ) t 0 be a Poisson process with intensity λ and (T n ) n 0 its jump times with the convention T 0 = 0. Let us now construct the jump times of X and Y . Both processes make exactly N t jumps before time t. If N t = 0, then X s = x + s and Y s = y + s for 0 s t.

Assume now that N t 1. The N t -1 first jump times of X and Y are the ones of (N t ) t 0 :

T X k = T Y k = T k 0 k N t -1.
In other words, the coupling used to control Wassertein distance (see Lemma 5.1) acts until the penultimate jump time T Nt-1 . At that time, we have

X T N t -1 -Y T N t -1 = x -y 2 Nt-1 .
Then we have to define the last jump time for each process. If they are such that

T X Nt = T Y Nt + X T N t -1 -Y T N t -1
then the paths of X and Y are equal on the interval (T X Nt , t) and can be chosen to be equal for any time larger than t.

Recall that conditionally on the event {N t = 1}, the law of T 1 is the uniform distribution on (0, t). More generally, if n 2, conditionally on the set {N t = n}, the law of the penultimate jump time T n-1 has a density s → n(n -1)t -n (t -s)s n-2 1 (0,t) (s) and conditionally on the event {N t = n, T n-1 = s}, the law of T n is uniform on the interval (s, t).

Conditionally on N t = n 1 and T n-1 , T X n and T Y n are uniformly distributed on (T n-1 , t) and can be chosen such that

P T X n = T Y n + x -y 2 n-1 N X t = N Y t = n, T X n-1 = T Y n-1 = T n-1 = 1 - |x -y| 2 n-1 (t -T n-1 ) ∨ 0 1 - |x -y| 2 n-1 (t -T n-1 )
.

This coupling provides that

δ x P t -δ y P t TV 1 -E 1 - |x -y| 2 Nt-1 (t -T Nt-1 ) 1 {Nt 1} e -λt + |x -y|E 2 -Nt+1 (t -T Nt-1 ) 1 {Nt 1} .
For any n 2,

E 1 t -T Nt-1 N t = n = n(n -1) t n t 0 u n-2 du = n t .
This equality also holds for n = 1. Thus we get that

E 2 -Nt+1 (t -T Nt-1 ) 1 {Nt 1} = 1 t E N t 2 -Nt+1 = λe -λt/2 ,
since N t is distributed according to the Poisson law with parameter λt. This provides the estimate (22).

To treat the case of general initial conditions and to get (23), we combine the coupling between the dynamics constructed above with the choice of the coupling of the initial measures µ and ν as a function of the underlying Poisson process (N t ) t 0 : the time horizon t > 0 being fixed, if N t = 0, one chooses for L(X 0 , Y 0 ) the optimal total variation coupling of ν and µ; if N t 1, one chooses their optimal Wasserstein coupling. One checks easily that this gives an admissible coupling, in the sense that its first (resp. second) marginal is a constant rate TCP process with initial distribution ν (resp. µ). And one gets with this construction, using the same estimates as above in the case where N t 1:

P(X t = Y t ) = P(X t = Y t , N t 1) + P(X t = Y t , N t = 0) E |X 0 -Y 0 | 2 -Nt+1 (t -T Nt-1 ) 1 {Nt 1} + P(X 0 = Y 0 , N t = 0) = λe -λt/2 W 1 (ν, µ) + e -λt ν -µ TV ,
which clearly implies (23).

A storage model example

In [RT00], Roberts and Tweedie improve the approach from [RR96] via Lyapunov functions and minorization conditions in the specific case of stochastically monotonous processes. They get better results on the speed of convergence to equilibrium in this case. They give the following example of a storage model as a good illustration of the efficiency of their method. The process (X t ) t 0 on R + is driven by the generator

Lf (x) = -βxf (x) + α ∞ 0 (f (x + y) -f (x))e -y dy.
In words, the current stock X t decreases exponentially at rate β, and increases at random exponential times by a random (exponential) amount. Let us introduce a Poisson process (N t ) t 0 with intensity α and jump times (T i ) i 0 (with T 0 = 0) and a sequence (E i ) i 1 of independent random variables with law E(1) independent of (N t ) t 0 . The process (X t ) t 0 starting from x 0 can be constructed as follows: for any i 0,

X t = e -β(t-T i ) X T i if T i t < T i+1 , e -β(T i+1 -T i ) X T i + E i+1 if t = T i+1 .
Proposition 5.6. For any x, y 0 and t 0, W p (δ x P t , δ y P t ) |x -y|e -βt , and (when α = β)

δ x P t -δ y P t TV e -αt + |x -y|α e -βt -e -αt α -β . ( 24
)
Moreover, if µ is the invariant measure of the process X, we have for any probability measure ν with a finite first moment and t 0, νP t -µ TV ν -µ TV e -αt + W 1 (ν, µ)α e -βt -e -αt α -β .

Remark 5.7. In the case α = β, the upper bound (24) becomes

δ x P t -δ y P t TV (1 + |x -y|αt)e -αt .
Remark 5.8 (Optimality). Applying L to the test function f (x) = x n allows us to compute recursively the moments of X t . In particular,

E x (X t ) = α β + x - α β e -βt .
This relation ensures that the rate of convergence for the Wasserstein distance is sharp. Moreover, the coupling of total variation distance requires at least one jump. As a consequence, the exponential rate of convergence is greater than α. Thus, Equation (24) provides the optimal rate of convergence α ∧ β.

Remark 5.9 (Comparison with previous work). By way of comparison, the original method of [RT00] does not seem to give these optimal rates. The case α = 1 and β = 2 is treated in this paper (as an illustration of Theorem 5.1), with explicit choices for the various parameters needed in this method. With these choices, in order to get the convergence rate, one first needs to compute the quantity θ (defined in Theorem 3.1), which turns out to be approximately 5.92. The result that applies is therefore the first part of Theorem 4.1 (Equation ( 27)), and the convergence rate is given by β defined by Equation ( 22). The computation gives the approximate value 0.05, which is off by a factor 20 from the optimal value α ∧ β = 1.

Proof of Proposition 5.6. Firstly, consider two processes X and Y starting respectively at x and y and driven by the same randomness (i.e. Poisson process and jumps). Then the distance between X t and Y t is deterministic:

X t -Y t = (x -y)e -βt .
Obviously, for any p 1 and t 0, W p (δ x P t , δ y P t ) |x -y|e -βt .

Let us now construct explicitly a coupling at time t to get the upper bound (24) for the total variation distance. The jump times of (X t ) t 0 and (Y t ) t 0 are the ones of a Poisson process (N t ) t 0 with intensity α and jump times (T i ) i 0 . Let us now construct the jump heights (E

X i ) 1 i Nt and (E Y i ) 1 i Nt of X and Y until time t. If N t = 0, no jump occurs. If N t 1, we choose E X i = E Y i for 1 i N t -1 and E X
Nt and E Y Nt in order to maximise the probability

P X T N t + E X Nt = Y T N t + E Y Nt X T N t , Y T N t .
This maximal probability of coupling is equal to

exp -|X T N t -Y T N t | = exp -|x -y|e -βT N t 1 -|x -y|e -βT N t .
As a consequence, we get that

δ x P t -δ y P t TV 1 -E 1 -|x -y|e -βT N t 1 {Nt 1} e -αt + |x -y|E e -βT N t 1 {Nt 1} .
The law of T n conditionally on the event {N t = n} has the density

u → n u n-1 t n 1 [0,t] (u). This ensures that E e -βT N t 1 {Nt 1} = 1 0 e -βtv E N t v Nt-1 dv.
Since the law of N t is the Poisson distribution with parameter λt, one has

E N t v Nt-1 = αte αt(v-1) .
This ensures that E e -βNt 1 {Nt 1} = α e -βt -e -αt α -β which completes the proof. Finally, to get the last estimate, we proceed as follows: if N t is equal to 0, a coupling in total variation of the initial measures is done, otherwise, we use the coupling above (the method is exactly the same as for the equivalent result in Proposition 5.4, see its proof for details).

The case of diffusion processes

Let us consider the process (X t ) t 0 on R d solution of

dX t = A(X t ) dt + σ(X t ) dB t , (25)
where (B t ) t 0 is a standard Brownian motion on R n , σ is a smooth function from R d to M d,n (R) and A is a smooth function from R d to R d . Let us denote by (P t ) t 0 the semi-group associated to (X t ) t 0 . If ν is a probability measure on R d , νP t stands for the law of X t when the law of X 0 is ν.

Under ergodicity assumptions, we are interested in getting quantitative rates of convergence of L(X t ) to its invariant measure in terms of classical distances (Wasserstein distances, total variation distance, relative entropy,. . . ). Remark that if A is not in gradient form (even if σ is constant), X t is not reversible and the invariant measure is usually unknown, so that it is quite difficult to use functional inequalities such as Poincaré or logarithmic Sobolev to get a quantitative rate of convergence in total variation or Wasserstein distance (using for example Pinsker's inequality or more generally transportationinformation inequality). Therefore the only general tool seems to be Meyn-Tweedie's approach, via small sets and Lyapunov functions, as explained in Section 4.2. However, we have seen that in practical examples the resulting estimate can be quite poor.

The main goal of this short section is to recall the known results establishing the decay in Wasserstein distance and then to propose a strategy to derive control in total variation distance.

Decay in Wasserstein distance

The coupling approach to estimate the decay in Wasserstein distance was recently put forward, see [CGM08] and [START_REF] Bolley | Trend to equilibrium and particle approximation for a weakly selfconsistent Vlasov-Fokker-Planck equation[END_REF] or [START_REF] Eberle | Reflection coupling and Wasserstein contractivity without convexity[END_REF]. It is robust enough to deal with nonlinear diffusions or hypoelliptic ones. In [BGG12], the authors approach the problem directly, by differentiating the Wasserstein distance along the flow of the SDE.

Let us gather some of the results in these papers in the following statement.

Proposition 6.1.

1. Assume that there exists λ > 0 such that for p > 1 p -1 2 (σ(x) -σ(y))(σ(x) -σ(y)) t + (A(x) -A(y)) • (x -y) -λ|x -y| 2 , x, y ∈ R d .

(26) Then, for any ν, ν ∈ P p (R d ), one has W p (νP t , ν P t ) e -λt W p (ν, ν ).

(27)

2. Assume that for all x, σ(x) = α I d for some constant α and that A is equal to -∇U where U is a C 2 function such that Hess(U ) -K I d outside a ball B(0, r 0 ) and Hess(U ) ρ I d inside this ball for some positive ρ. Then there exists c > 1, α > 0 such that W 1 (νP t , ν P t ) c e -αt W 1 (ν, ν ).

(28)

3. Suppose that the diffusion coefficient σ is constant. Assume that A is equal to -∇U where U a C 2 convex function such that Hess(U ) ρ I d outside a ball B(0, r 0 ), with ρ > 0. Then there exists an invariant probability measure ν ∞ and α > 0 such that

W 2 (νP t , ν ∞ ) e -αt W 2 (ν, ν ∞ ). ( 29
)
Proof. The first point is usually proved using a trivial coupling (and it readily extends to p = 1 in the case of constant diffusion coefficient), namely considering the same Brownian motion for two different solutions of the SDE starting with different initial measures. Note also that, in the case p = 2, the coercivity condition ( 26) is equivalent to the uniform contraction property (27) for the W 2 metric (see [START_REF] Von Renesse | Transport inequalities, gradient estimates, entropy, and Ricci curvature[END_REF]). The second point is due in this form to Eberle [START_REF] Eberle | Reflection coupling and Wasserstein contractivity without convexity[END_REF], using reflection coupling as presented by [LR86], used originally in this form by Chen and Wang to prove spectral gap estimates (see a nice short proof in [HSV11, Prop. 2.8]) in the reversible case.

Finally, the third part was proved by [BGG12] establishing the dissipation of the Wasserstein distance by an adequate functional inequality. Remark 6.2.

• Let us remark that the contraction property of the two first points ensures the existence of an invariant probability measure ν ∞ and an exponential rate of convergence towards this invariant measure in Wasserstein distance.

• Note also that in the hypoelliptic case of a kinetic Fokker-Planck equation:

dx t = v t dt dv t = dB t -F (x t )dt -V (v t )dt
with F (x) ∼ ax and V (v) ∼ bv for positive a and b, one has W 2 (νP t , ν P t ) ≤ c e -αt W 2 (ν, ν ) for c > 1 and a positive α (see [CGM08]). Remark 6.6. Once again, one can give in the case of kinetic Fokker-Planck equation estimate in total variation distance, using the previous remarks (see [START_REF] Bakry | Rate of convergence for ergodic continuous Markov processes: Lyapunov versus Poincaré[END_REF] for qualitative results).

Figure 1 :

 1 Figure1: Two trajectories following the Wasserstein coupling; the bigger jumping alone can be good, making the distance between both trajectories smaller, or bad.

Figure 2 :

 2 Figure2:The "true" function E x,y |X t -Y t | 1/2 (solid, black; by Monte Carlo method with m = 10 000 copies) and the bound given in Equation (12) (dashed, blue), for x = 2 and y = 10.

In fact, in [RR96], the result is given with A instead of A in the upper bound. Joaquin Fontbona pointed out to us that Lemma 6 from [RR96] has to be corrected, adding the exponential term e δt to the estimate. We thank him for this remark.

Acknowledgements. Part of this work was done during a short (resp. long) visit of F.M. (resp. J.B.B.) to CMM (Santiago, Chile). They both thank colleagues from CMM for their warm hospitality, and particularly Joaquin Fontbona for interesting discussions. Another part of this work was done during a visit of F.M. and P.-A. Z. to the University of Neuchâtel; they thank Michel Benaïm for his hospitality and additional interesting discussions. A.C. acknowledges the hospitality of IRMAR (Rennes, France). The research of A.C. is sponsored by MECESUP Doctoral Fellowship UCH 0410/07-10, MECESUP Doctoral Fellowship for sojourn UCH0607 and CONICYT Doctoral Fellowship/11. This research was partly supported by the French ANR projects EVOL and ProbaGeo. We deeply thank the referee for his/her quick and constructive report.

Total variation estimate

If Σ = 0 in Equation (25), the process (X t ) t 0 is deterministic and its invariant measure is a Dirac mass at the unique point x ∈ R d such that A(x) = 0. As a consequence, for any x = x, δ x P t -δ x TV = 1 and H(δ x P t |δ x) = +∞.

A non-zero variance is needed to get a convergence estimate in total variation distance.

Classically, the Brownian motion creates regularity and density. There are a lot of results giving regularity, in terms of initial points, of semigroup in small time. Let us quote the following result of Wang, which holds for processes living on a manifold.

Lemma 6.3 ([Wan10]

). Suppose that σ is constant and denote by η the infimum of its spectrum. If A is a C 2 function such that

then there exists K η such that, for small ε > 0,

Remark 6.4.

• There are many proofs leading to this kind of results, see for example Aronson [Aro67] for pioneering works, and [Wan10] using Harnack's and Pinsker's inequalities.

• Note that in [START_REF] Guillin | Degenerate Fokker-Planck equations: Bismut formula, gradient estimate and Harnack inequality[END_REF], an equivalent bound was given for the kinetic Fokker-Planck equation but with ε replaced by ε 3 . Now that we have a decay in Wasserstein distance and a control on the total variation distance after a small time, we can use the same idea as for the TCP process. As a consequence, we get the following result. Theorem 6.5. Assume that σ is constant. Under Points 1. or 2. of Proposition 6.1, one has, for any ν and ν in P 1 (R d ),

Under Point 3. of Proposition 6.1, one has, for any ν and ν in P 2 (R d ),

Proof. Using first Lemma 6.3 and then Point 1. of Proposition 6.1, we get

The proof of the second assertion is similar, except the use of Point 3. of Proposition 6.1 in the second step.


Eugen Feller
email: eugen.feller@inria.fr

Christine Morin
email: christine.morin@inria.fr

Armel Esnault
email: armel.esnault@irisa.fr

A Case for Fully Decentralized Dynamic VM Consolidation in Clouds

Keywords: Cloud Computing, Dynamic VM Consolidation, Ant Colony Optimization, Unstructured P2P Network, Virtualization

One way to conserve energy in cloud data centers is to transition idle servers into a power saving state during periods of low utilization. Dynamic virtual machine (VM) consolidation (VMC) algorithms are proposed to create idle times by periodically repacking VMs on the least number of physical machines (PMs). Existing works mostly apply VMC on top of centralized, hierarchical, or ring-based system topologies which result in poor scalability and/or packing efficiency with increasing number of PMs and VMs.

In this paper, we propose a novel fully decentralized dynamic VMC schema based on an unstructured peer-to-peer (P2P) network of PMs. The proposed schema is validated using three well known VMC algorithms: First-Fit Decreasing (FFD), Sercon, V-MAN, and a novel migration-cost aware ACO-based algorithm. Extensive experiments performed on the Grid'5000 testbed show that once integrated in our fully decentralized VMC schema, traditional VMC algorithms achieve a global packing efficiency very close to a centralized system. Moreover, the system remains scalable with increasing number of PMs and VMs. Finally, the migration-cost aware ACO-based algorithm outperforms FFD and Sercon in the number of released PMs and requires less migrations than FFD and V-MAN.

I. INTRODUCTION

Cloud data center providers are now provisioning an increasing number of data centers to handle customers growing resource demands. Such data centers do not only require tremendous energy amounts to power their IT and cooling infrastructures but also impose scalability challenges on their system management frameworks. For example, according to [START_REF] Esnault | How Clean Is Your Cloud?[END_REF] cloud computing services consumed approximately 662 billion kWh of energy in 2007. This is not surprising when considering today's public cloud providers data center scales. For instance, Rackspace which is one of the leading Infrastructure-as-a-Service (IaaS) providers is estimated to host approximately 78 000 servers in 2012 [START_REF]Hosting reports third quarter[END_REF].

While the system architecture details of Rackspace and other cloud providers (e.g. Amazon EC2) are not publicly available, several research attempts have been made in the last years on the design of energy-efficient virtual machine (VM) management frameworks in order to ease the creation of private clouds. Energy efficiency is typically obtained by transitioning idle physical machines (PMs) into a power-saving state during periods of low utilization. To facilitate the creation of idle times dynamic VM consolidation (VMC) can be used, whose objective is to pack the VMs on the least number of PMs while minimizing the number of migrations. In contrast to static VMC which assumes empty PMs prior starting the VM to PM assignment, dynamic VMC starts from pre-loaded PMs. Starting from pre-loaded PMs adds a new dimension to the problem as it not only requires the number of PMs to be minimized but also the number of migrations needed in order to arrive to the new VM-PM assignment. In other words, dynamic VMC is a multi-objective problem while static VMC is a single-objective problem. Throughout the rest of the document we assume dynamic VMC when we refer to VMC.

VMC even in its single-objective variant is an NP-hard combinatorial optimization problem and thus is expensive (in time and space) to compute with increasing numbers of PMs and VMs. Consequently, choosing the appropriate system topology is crucial in order to obtain good scalability and packing efficiency. Packing efficiency is defined as the ratio between the number of released PMs to the total number of PMs. Existing VMC approaches either rely on centralized (e.g. [START_REF] Vmware | Distributed Resource Scheduler (DRS)[END_REF]- [START_REF] Verma | pMapper: power and migration cost aware application placement in virtualized systems[END_REF]), hierarchical (e.g. [START_REF] Feller | Snooze: A Scalable and Autonomic Virtual Machine Management Framework for Private Clouds[END_REF], [START_REF] Graubner | Energy-Efficient Management of Virtual Machines in Eucalyptus[END_REF]), or ring-based [START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS[END_REF] system topologies. While the centralized topology yields to the best packing efficiency, it suffers from poor scalability due to the large amount of considered PMs and VMs. On the other hand, the hierarchical approach achieves better scalability through partitioning of PMs in groups and applying VMC only in the scope of the groups. However, this is achieved at the cost of decreased packing efficiency as the VMC solutions remain local to the groups. Finally, in the ring-based approach PMs are organized in a ring and scheduling is performed event-based upon underload/overload detection by forwarding the VMC requests in the ring. The scalability of this system is limited by the cost of ring-maintenance and its worst-case complexity which requires a full ring traversal to place the VMs.

This paper makes the following two contributions 1 :

schema based on an unstructured peer-to-peer (P2P) network of PMs. Our VMC schema does not enforce any particular system topology shape. Instead, the topology is periodically modified to form random neighbourhoods of PMs. Considering the computational complexity of VMC we limit its application to the scope of the neighbourhoods. Moreover, the randomness of the system topology facilitates the convergence of the schema towards a global packing efficiency very close to a centralized system by leveraging traditional centralized VMC algorithms. • We adapt our previously proposed ACO-based static VMC algorithm [START_REF] Feller | Energy-Aware Ant Colony Based Workload Placement in Clouds[END_REF] to minimize the number of VM migrations in the framework of dynamic VMC. Minimizing the number of migrations required to move from the current state (VM-PM assignment) to the newly computed one is crucial as each migration has a direct impact on the VM performance as well as the amount of data to be transferred over the network. Both contributions are integrated within a distributed emulator along with three state-of-the-art greedy VMC algorithms, namely FFD, Sercon [START_REF] Murtazaev | Sercon: Server Consolidation Algorithm using Live Migration of Virtual Machines for Green Computing[END_REF] and V-MAN [START_REF] Marzolla | Server consolidation in Clouds through gossiping[END_REF]. Extensive evaluation performed on the Grid'5000 experimental testbed shows that once integrated all the evaluated algorithms achieve a global packing efficiency very similar to a centralized system. Moreover, the migration-cost aware ACO-based algorithm outperforms FFD and Sercon in the number of released PMs and its solutions require less migrations than the ones from FFD and V-MAN (see Table I). This paper is organized as follows. Section II reviews existing dynamic VMC works. Section III details the first contribution, a fully decentralized dynamic VMC schema. Section IV presents the second contribution, a migrationcost aware ACO-based dynamic VMC algorithm. Section V discusses the evaluation results. Finally, Section VI closes this paper with conclusions and future work.

II. BACKGROUND

Several dynamic VMC systems and algorithms have been proposed during the last years. In this work we distinguish between four types of systems: centralized, hierarchical, structured P2P, and unstructured P2P which integrate different types of algorithms (e.g. mathematical programming, greedy).

In [START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] a centralized system called Entropy is introduced. Entropy employs constraint programming to solve the VMC problem using a centralized architecture. Both design choices result in limited scalability and make it suffer from single point of failure (SPOF). A similar approach can be found in [START_REF] Verma | pMapper: power and migration cost aware application placement in virtualized systems[END_REF] which applies a greedy VMC algorithm on top of a centralized system architecture.

In our previous work [START_REF] Feller | Snooze: A Scalable and Autonomic Virtual Machine Management Framework for Private Clouds[END_REF] we have introduced Snooze, a scalable and autonomic VM management framework based on a hierarchical architecture. Snooze currently relies on a greedy VMC algorithm called Sercon proposed by Murtazaev et al [START_REF] Murtazaev | Sercon: Server Consolidation Algorithm using Live Migration of Virtual Machines for Green Computing[END_REF]. VMC is only applied within groups of PMs thus allowing it to scale with increasing number of PMs and VMs. However, due to a lack of inter-group coordination currently the VMC solutions remain local thus limiting the packing efficiency of the system.

In [START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS[END_REF] a system based on a structured P2P network of PMs is presented. Each PM attempts to apply VMC event-based upon underload/overload detection by first considering all the predecessor PMs and otherwise forwards the VMC request to the successor PM in the ring which repeats the procedure by considering itself and all its predecessor PMs. Besides the fact that the achievable packing efficiency remains unclear when used with periodic VMC, its scalability is limited by the cost of the ring maintenance and its worst-case complexity which requires a full ring traversal to consolidate the VMs.

In contrast to all these works our schema does not rely on a static system topology but rather employs a fully decentralized dynamic topology construction schema. Particularly, the system topology is periodically and randomly modified through the exchange of neighbourhood information among the PMs to form random PM neighbourhoods. VMC is applied periodically only within the scope of the neighbourhoods. This property does not only allow the system to scale with increasing number of PMs and VMs but also facilitates the VMC algorithm convergence towards almost the same global packing efficiency as of a centralized system. Finally, the schema is not limited to any particular VMC algorithm and supports heterogeneous PMs and VMs.

The closest work in terms of system architecture can be found in [START_REF] Marzolla | Server consolidation in Clouds through gossiping[END_REF] where the authors introduce V-MAN, a fully decentralized VMC schema. Similarly to our work V-MAN leverages randomized system topology construction and applies VMC only within the scope of the neighbourhoods. However, it is limited to a simple VMC algorithm which considers at most two PMs at a time. Moreover, it makes its decisions solely based on the number of VMs thus ignoring the actual VM resource demands. As our results show both design decisions yield to a large number of migrations. Finally, V-MAN as introduced is restricted to homogeneous servers (physical/virtual) and has been validated by simulation only.

III. A FULLY DECENTRALIZED DYNAMIC VM CONSOLIDATION SCHEMA

This section presents our first contribution: a fully decentralized dynamic VMC schema. First, the system assumptions and notations are introduced. Afterwards, the design principles are discussed and the system topology construction mechanism is detailed. Finally, the VM consolidation process is presented.

A. System Assumptions

We assume a data center whose PMs are interconnected with a high-speed LAN connection such as Gigabit Ethernet or Infiniband. PMs hardware can be either homogeneous or heterogeneous. VMs can be live migrated between the PMs. This work considers the dynamic VMC problem. Particularly, VMs are assumed to be running on the PMs and VMC is triggered periodically according to the system administrator specified interval to further optimize the VM placement.

VM resource demands are assumed to be static. In other words, VMC decisions are based on the requested VM capacity as specified during VM deployment. Taking into account the actual resource usage could further improve the data center utilization. However, it is out of the scope of this work.

B. Notations

We now define the notions used in this work. Let P denote the set of PMs and V p the set of VMs hosted by a PM p.

PMs are represented by d-dimensional total capacity vectors TC p := {TC p,k } 1≤k≤d . In this work three dimensions are considered (d = 3). Each dimension k represents the PMs capacity of resource R k ∈ R with R being defined as R := {CPU, Memory, Network}.

VMs are represented by requested capacity vectors RC v := {RC v,k } 1≤k≤d with each component specifying the requested VM capacity of resource R k .

The total used PM capacity l p is computed as the sum of all VM requested capacity vectors:

l p := ∀v∈V p RC v .

C. Design Principles

Due to the NP-hardness of the VMC problem it is not sufficient for a system to rely on a centralized server which executes the VMC algorithm. Indeed, to remain scalable and avoid SPOF with increasing numbers of servers (physical and virtual) a more distributed approach is desirable. Moreover, the system should compute VMC solutions which have a high packing efficiency thus able to release a large number of PMs.

In order to achieve both scalability and high packing efficiency we have designed a fully decentralized VMC system based on an unstructured P2P network of PMs. For scalability our system is built on top of the Cyclon protocol [START_REF] Voulgaris | CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays[END_REF]. Cyclon is an epidemic membership protocol which allows to periodically construct time-varying randomized P2P overlays in which each PM has only a partial system view, the so-called neighbourhood. This property allows the system to scale with increasing number of PMs as it does not rely on a central server. PMs can join and leave the network at any time without the need to notify a central server.

Our system exploits the randomized neighbourhoods in order to achieve a high packing efficiency by periodically applying the VMC algorithms in the scope of the neighbourhoods. As the neighbourhoods are modified periodically and randomly the entire system tends to converge towards a high packing efficiency by solely making local VMC decisions within neighbourhoods without the need of a central server.

D. System Topology Construction

The system topology construction mechanism is based on the Cyclon membership protocol. Cyclon has been designed for fast information dissemination while dealing with a high number of nodes that can join and leave the system. It is based on a periodic and random exchange of neighbourhood information among the peers, the so called shuffling operation. Each peer maintains a local list of neighbours, called cache entries. A cache entry contains the address (IP/port) and the age value of a neighbour. The role of the age field is to bound the time a neighbour is chosen for shuffling thus facilitating the early elimination of dead peers. The shuffling operation is repeated periodically according to a parameter λt > 0. The resulting system topology can be viewed as a directed graph where vertices represent nodes and edges the relations. For example, X -→ Y means Y is a neighbour of X. Note, that the relations are asymmetric (i.e. Y is a neighbour of X does not imply that X is a neighbour of Y). More details on the system topology construction can be found in [START_REF] Voulgaris | CYCLON: Inexpensive Membership Management for Unstructured P2P Overlays[END_REF]. Figure 1 depicts an example system topology with six PMs (PM 1 , . . . , PM 6 ) and eleven VMs (V M 1 , . . . , V M 11 ) that are distributed among the PMs. The neighbourhood size is two. For the sake of simplicity a single resource "number of cores" is considered in this example: physical (PCORES) and virtual (VCORES). PMs are homogeneous and have five PCORES. VMs can request one, two or three VCORES. The total capacity of PMs in the system is 30 PCORES. 19 PCORES are currently utilized, which corresponds to an utilization of approximately 63%.

PM1 VM1 PM6 VM10 PM2 VM4 PM3 VM3 PM4 VM7 VM11 VM6 VM5 PM5 VM8 VM9 VM2 PM Neighbours 1 {3,5} 2 {1,6} 3 {2,4} 4 {3,5} 5 {2,6} 6
{1,4}

E. VM Consolidation Process

Each PM periodically triggers a VM consolidation process within its neighbourhood in order to optimize the VM placement. The process is composed of the following six steps:

1) First, PM p which initiates the consolidation checks whether it is not already under consolidation. If not it attempts to acquire a lock for each member (including itself) of its neighbourhood. Otherwise, the consolidation is aborted. Locks are associated with all PMs in order to avoid concurrent access to PM resources in case of multiple ongoing consolidations. Acquiring a lock is a non-blocking operation. If it does not succeed, the member will not participate in the consolidation process. 2) For each successful lock acquisition, PM p requests from the corresponding node its total capacity, currently packed VMs and their requested capacity vectors.

3) The VMC algorithm is started once all the resource information is received from the locked members. It outputs a migration plan (MP) which corresponds to the ordered set of the new VM-PM assignments. Any centralized VMC algorithm can be used in this operation. 4) An actuation module on the PM enforces the MP by sending migration operations to the PMs hypervisors. 5) After the actuation all locks are released. 6) Each PM which does not accommodate VMs anymore power-cycles itself in order to conserve energy. Figure 2 illustrates the decentralized consolidation process using the topology introduced in Figure 1. Starting from the initial state as shown in Figure 1, PM 4 initiates the first consolidation with its neighbours PM

A. Ant Colony Optimization

Ant Colony Optimization (ACO) [START_REF] Dorigo | Ant algorithms for discrete optimization[END_REF] is a probabilistic meta-heuristic for finding near optimal solutions to complex combinatorial optimization problems (e.g. VMC). ACO design is inspired from the natural food discovery behaviour of real ants. Particularly, while traversing their environment ants deposit a chemical substance called pheromone. Other ants can smell the concentration of this substance on a certain path and tend to favour paths with a higher concentration. To favour the exploration of alternative paths pheromone evaporates after a certain amount of time. Controlled experiments have shown that after some time the entire colony tends to converge towards the shortest path to the food source [START_REF] Deneubourg | The self-organizing exploratory pattern of the argentine ant[END_REF].

B. Design Principles

In our previous work [START_REF] Feller | Energy-Aware Ant Colony Based Workload Placement in Clouds[END_REF] we have applied ACO to solve the static VMC problem. ACO is especially attractive for VMC due to its polynomial worst-case complexity and ease of parallelization (i.e. ants work independently).

The key idea of the algorithm is to let multiple artificial ants construct VMC solutions concurrently in parallel within multiple cycles. As the VMC model does not incorporate the notion of a path, ants deposit pheromone on each VM-PM pair within a pheromone matrix.

To choose a particular VM as the next one to pack in a PM a probabilistic decision rule is used. This rule is based on the current pheromone concentration information on the VM-PM pair and a heuristic information which guides the ants towards choosing VMs leading to better overall PM utilization. Hence, the higher the amount of pheromone and heuristic information associated with an VM-PM pair is, the higher the probability that it will be chosen.

At the end of each cycle, all solutions are compared and the one requiring the least number of PMs is saved as the new global best solution. Afterwards, the pheromone matrix is updated to simulate pheromone evaporation and reinforce VM-PM pairs which belong to the so-far best solution.

In the following sections we describe the modifications (marked bold) done to the original algorithm for considering the dynamic VMC problem. They involve the objective function, heuristic information, the pheromone evaporation rule and finally the algorithm pseudo-code.

C. Formal Problem Definition

The objective function (OF) we attempt to maximize is defined by Eq. 1. It takes as input the set of PMs and the migration plan (MP). MP denotes the ordered set of new VM to PM assignments.

The OF is designed to favour the number of released PMs, the variance [START_REF] Goodman | The Variance of the Product of K Random Variables[END_REF] of the scalar valued PM used capacity vectors l p and smaller MPs. In other words, the higher the number of released PMs and the variance between the PMs used capacity vectors, the better it is. Indeed, one of our objectives is to release as many PMs as possible. Releasing PMs also helps to increase the variance which is an important indicator for increased resource utilization. In this work the L1 norm [START_REF] Weisstein | L1-norm[END_REF] is used to compute the scalar values. The second objective is to minimize the number of migrations. Consequently, we favour MPs with the least number of migrations. This is reflected by defining the OF to be inverse proportional to the MP size.

MPs with high number of migrations (i.e. VM-PM pairs) will lower its value, while smaller MPs will increase it. Three parameters, e, g, m > 0, are used to either give more weight to the number of released PMs, the PM load variance or the MP size.

D. Probabilistic Decision Rule and Heuristic Information

The probability p v,p for an ant to choose a VM v to be migrated to PM p is defined in Eq. 2.

p v,p := [τ v,p ] α × [η v,p ] β v∈V p [τ v,p ] α × [η v,p ] β , ∀v ∈ V, ∀p ∈ P (2)
where τ v,p represents the amount of pheromone associated with a particular VM-PM pair. η v,p denotes the heuristic information. Its definition is shown in Eq. 3.

η v,p, := κ v,p |MP| if l p + RC v ≤ TC p 0 otherwise (3)
The key idea is to emphasize VM to PM migrations which yield in: high PM used capacity and are part of a small MP. Consequently, η v,p is defined as the ratio between κ v,p and the MP size in case the VM fits into the PM, and 0 otherwise. We use the constraint l p + RC v ≤ TC p to prevent new VMs from exceeding the total PM capacity.

To reward VMs which fill the PMs better κ v,p is defined as the inverse of the scalar valued difference between the static PM capacity and the utilization of the PM after placing VM v (see Eq. 4). Consequently, VMs which yield to better PM used capacity result in higher κ v,p value.

κ v,p := 1 |TC p -(l p + RC v )| 1 (4)
Finally, two parameters, α, β ≥ 0 are used to either emphasize the pheromone or heuristic information.

E. Pheromone Trail Update

After all ants have computed a MP, the pheromone trail update rule is used to reward VM-PM pairs which belong to the smallest MP (MP gBest ) as well as to simulate pheromone evaporation on the remaining VM-PM pairs. The pheromone trail update rule τ v,p is defined in Eq. 5.

τ v,p := (1 -ρ) × τ v,p + ∆ best τ v,p , ∀(v, p) ∈ V × P (5)
where ρ, 0 ≤ ρ ≤ 1 is used to control the evaporation rate. Consequently, higher values for ρ yield to faster pheromone evaporation. In order to reward VM-PM pairs which belong to the best MP, ∆ best τ v,p is defined as the cycle-best VM-PM pheromone amount. Particularly, VM-PM pairs which belong to the best MP receive an increasing pheromone amount and thus become more attractive during subsequent cycles. Other pairs, which are not part of the best MP continue loosing pheromone and thus become less attractive.

The goal of the algorithm is to release as many PMs as possible using the least number of migrations. Consequently, it attempts to maximize the OF f . Therefore, ∆ best τ v,p is defined to give f (P, MP gBest ) pheromone amount to VM-PM pairs (v, p) which belong to MP gBest , and 0 otherwise.

∆ best τ v,p := f(P, MP gBest ) if (v, p) ∈ MP gBest 0 otherwise (6)
Finally, to bound the pheromone amount on the VM-PM pairs, τ v,p is restricted to the range [τ min , τ max ].

F. Algorithm Definition

The pseudo-code is shown in Algorithm 1. It takes as input the set of PMs P including their associated VMs and a set of parameters (e.g. τ max , α, β, nCycles, nAnts) (line 1). The algorithm then sets the pheromone value on all the VM-PM pairs to τ max and iterates over a number of nCycles (lines 5 to 35). In each cycle multiple (nAnts) ants compute MPs concurrently in parallel (lines 7 to 21). The MPs accommodate at most |V M| migrations (line 10). Particularly, first the ants compute a probability p v,p for migrating a VM v to PM p for all VMs and PMs (line 11). Based on the computed probability they choose a VM-PM pair (v, p) stochastically and add it to the MP (lines 12 to 13). The source and destination PM capacity is then updated by removing the selected VM from the source and adding it to the destination PM (line 14). Afterwards, a score is computed by applying the OF (see Eq. 1) on the set of PMs P and the MP (line 15). Finally, if the newly computed score is greater than the local best score the local best score is updated and the VM-PM pair (v, p) is added to the local MP (lines 16 to 19). Note, that a VM is allowed to appear multiple times in the MP as long as it yields to a better score.

After all ants have finished computing the MPs, they are compared according to the OF f . The cycle best MP is selected and saved as MP cBest (line 22). If the cycle best MP is also the global best one, it becomes the new global best one (lines 23 to 25). Finally, the pheromone values on all VM-PM pairs are updated by applying the pheromone trail update rule (see Eq. 5) and enforcing the τ min , τ max bounds (lines 26 to 34).

The algorithm terminates after nCycles and returns the global best migration plan MP gBest (line 36).

V. EXPERIMENTAL RESULTS

This section presents the evaluation results. First, the prototype implementation principles are introduced. Afterwards, the system setup is detailed and the results are discussed.

A. Prototype Implementation

To validate our work we have implemented a distributed Python-based VMC-enabled Cyclon P2P system emulator. Each PM is emulated by a daemon which listens for TCP

We run the emulator once for each of the evaluated algorithms: FFD, Sercon, V-MAN and the proposed ACO-based algorithm. The ACO parameters are shown in Table III. They were derived empirically through numerous experiments. The evaluation is focused on: (1) analysis of the number of active PMs (packing efficiency) and migrations; (2) scalability of the system; and (3) comparison of the packing efficiency with the centralized topology for all the VMC algorithms.

C. Number of Active PMs and Migrations

We first analyze the number of active PMs. The results of this evaluation are shown in Figure 3. As it can be observed the consolidation phase starts at the 30th second. FFD performs the worst as it only manages to release 246 nodes. V-MAN achieves the best result with 323 released PMs which is closely followed by the ACO-based algorithm with 322 released PMs. Note, that Sercon performs worse than V-MAN and ACO.

Figure 4 depicts the number of migrations with the progress of the experiment. As it can be observed the number of migrations quickly converges towards zero with Sercon, V-MAN and the ACO algorithm thus demonstrating the good reactivity of our schema. Note, that the ACO algorithm requires more migrations than Sercon. Indeed, it trades the number of migrations for the amount of released PMs (see Figure 3). Finally, V-MAN performs the worst among the three dynamic VMC algorithms. FFD yields in a tremendous amount of migrations (in total 96494). We explain this with the fact the algorithm is not designed to take into account the current VM-PM assignment. Particularly, due to its static nature it assumes that the PMs do not host any VMs prior computing the new VM-PM assignment. This results in a permanent movement of most of the VMs in each VMC iteration.

D. Scalability

To evaluate the scalability of our system we have varied the number of PMs from 120 to 1008 and analyzed the obtained packing efficiency. The results are summarized in Table IV. As it can be observed, except the outlier with V-MAN at 504 PMs, the packing efficiency does not change significantly with increasing numbers of PMs and VMs, thus demonstrating the good scalability of our schema. Another important metric to evaluate is the maximum number of migrations per VM during the whole duration of the experiment. In other words, due to the fully decentralized nature of the system and the random neighbourhood construction, VMs could traverse multiple PMs during subsequent consolidation rounds. As our results show, the maximum number of migrations per VM highly depends on the current VM-PM assignment and the VMC algorithm, less on the number of PMs and VMs. Particularly, in the current setup, Sercon requires at most one migration per VM. On the other hand, V-MAN results in at most 5 and ACO needs at most 9 migrations. Finally, FFD as it does not consider the current VM-PM assignment yields to the largest number of migrations.

E. Comparison with a Centralized System Topology

Table V depicts the results from the comparison of the number of migrations and packing efficiency of our approach with the centralized topology for 1008 PMs and 6048 VMs. To simulate a centralized topology we have run the VMC algorithms (FFD, Sercon, ACO) on a single PM. Note that, V-MAN is a decentralized algorithm thus its evaluation is not part of the centralized topology evaluation. As it can be observed the ACO-based VMC algorithm is unable to compute a solution in a reasonable amount of time when used in the centralized topology for this kind of scale. Sercon on the other hand outperforms FFD in both the number of migrations (1920 vs. 6040) and released PMs (320 vs. 249). This is not further surprising as in contrast to FFD, Sercon is designed to minimize the number of migrations.

More interestingly, our fully decentralized VMC schema achieves almost equivalent packing efficiency for the evaluated algorithms when compared to the centralized topology. When considering the number of migrations, FFD achieves the worst result with 96494 migrations. We explain this with the fact that the algorithm by nature does not take into account the current VM-PM assignments. Consequently, its solutions result in a permanent reassignment of VMs within neighbourhoods during subsequent consolidation rounds.

Our ACO-based algorithm outperforms FFD as well as Sercon in the number of released PMs and performs equal with V-MAN. However, the gains in the number of released PMs come at the cost of an increased number of migrations. For example, when compared to Sercon twice as many migrations are required. On the other hand, when considering V-MAN more than 150 migrations are saved by the ACO algorithm. This demonstrates that the ACO algorithm can serve as a competitive alternative to the other evaluated algorithms in the fully decentralized VMC schema.

VI. CONCLUSIONS AND FUTURE WORK

This paper has made two novel contributions. The first contribution has introduced a fully decentralized dynamic VMC schema based on an unstructured P2P network of PMs. In contrast to existing works which mostly rely on static system topologies our system employs a dynamic topology which is built by periodically and randomly exchanging neighbourhood information among the PMs. VMC is periodically applied only within the scope of the neighbourhoods thus allowing the system to scale with increasing number of PMs and VMs as no global system knowledge is required. Moreover, the randomized neighbourhood construction property facilitates the VMC convergence towards a global packing efficiency very similar to a centralized system by leveraging existing centralized VMC algorithms. The second contribution has introduced a migration-cost aware ACO-based dynamic VMC algorithm. In contrast to our previously proposed ACO-based algorithm which solely focuses on minimizing the number of PMs, the novel algorithm also attempts to minimize the number of migrations required to move from the current to the newly computed VM placement.

We have implemented a distributed Python-based VMCenabled Cyclon P2P system emulator and used it to evaluate three state-of-the-art VMC algorithms, namely FFD, Sercon and V-MAN along with our migration-cost aware ACO-based algorithm. The evaluation was conducted on a 42 node cluster of the Grid'5000 testbed which allowed to emulate up to 1008 PMs and 6048 VMs. The results show that the proposed fully decentralized VMC schema achieves a global packing efficiency very close to a centralized topology for all the evaluated algorithms. Moreover, the system remains scalable with increasing numbers of PMs and VMs. Finally, the proposed migration-cost aware ACO-based algorithm outperforms FFD and Sercon in the number of released PMs and requires less migrations than FFD and V-MAN when used in our fully decentralized VMC schema (see Table I).

In the future we plan to study the impact of neighbourhood size and ACO parameters choice on the system performance. We also plan to integrate both contributions in our recently open-sourced holistic energy-efficient VM management framework called Snooze [START_REF] Feller | Snooze: A Scalable and Autonomic Virtual Machine Management Framework for Private Clouds[END_REF]. This will allow taking into account the dynamic VM resource demands as well as to handle underload situations thus allowing to further improve the data center utilization. In this context we will investigate the complementaries between VM resource demands in order to support more accurate VM to PM assignment decisions (e.g. co-locate CPU and data intensive VMs). This will require the extensions of existing VMC algorithms to consider VM placement constraints such as co-location and anti-colocation.

Finally, we will work on improving the neighbourhood construction schema to build neighbourhoods taking into account the physical distance between the PMs. Last but not least, fault tolerance properties of the VMC schema will be evaluated.

Fig. 1 :

 1 Fig. 1: Example system topology

  [START_REF] Vmware | Distributed Resource Scheduler (DRS)[END_REF] and PM 5 . The result of this consolidation is shown in[START_REF] Esnault | How Clean Is Your Cloud?[END_REF]. V M 11 has been migrated from PM 4 to PM 5 and V M 6 & V M 7 have been migrated from PM 4 to PM 3 . PM 5 and PM 3 resources are now better utilized than in the previous configuration. In[START_REF]Hosting reports third quarter[END_REF], PM 2 triggers a consolidation with its neighbours PM 1 and PM 6 . V M 4 has been migrated from PM 2 to PM 1 . PM 1 is now fully utilized and PM 2 has become idle. Finally, in (3) PM 6 starts another consolidation with PM 1 and PM 4 . V M 5 has been moved from PM 4 to PM 6 . The node PM 4 has now become idle and PM 6 better utilized. The final system state with two released PMs (PM 2 and PM 4 ) is shown in[START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF]. It results in a new, almost global optimal data center utilization of approximately 95%.

Fig. 2 :

 2 Fig. 2: Example VM consolidation IV. A MIGRATION-COST AWARE ACO-BASED DYNAMIC VM CONSOLIDATION ALGORITHMThis section presents our second contribution: a novel migration-cost aware ACO-based dynamic VMC algorithm, one possible algorithm which can be integrated in the previously introduced fully decentralized VMC schema. First, a brief description of ACO is given and the algorithm design principles are outlined. Afterwards, the formal problem definition is introduced and the algorithm details are presented.

  max f(P, MP) := (nReleasedPMs) e × Var((|l p | 1 ) p∈P ) g × ( 1 |MP| ) m

Algorithm 1 3 : 4 : 9 :

 1349 Migration-cost Aware ACO-based VMC 1: Input: Set of PMs P with their associated VMs, Set of parameters 2: Output: Global best migration plan MP gBest MP gBest := ∅ 5: Set pheromone value on all VM-PM pairs to τ max 6: for all q ∈ {0 . . . nCycles -1} do 7: for all a ∈ {0 . . . nAnts -1} do 8: S core lBest := 0 MP tmp , MP a := ∅ 10:

Fig. 4 :

 4 Fig. 3: Number of active PMs

TABLE I :

 I Evaluation Summary

	Criteria	Best algorithm	2nd	3rd	4th
	#Migrations	Sercon	ACO V-MAN	FFD
	Packing efficiency	V-MAN	ACO	Sercon	FFD

TABLE II :

 II System parameters

	Parameter	Value
	Number of PMs and VMs	1008 (resp. 6048)
	Experiment duration	360s
	Consolidation interval	30s
	Shuffling interval	10s
	Neighbourhood size	16 PMs
	Considered resources	CPU, memory and network
	PM total capacity vector	(48, 26, 20)
	VM requested capacity vectors (0.2, 0.5, 0.1), (

TABLE III

 III

			: ACO parameters
	α, β	ρ	τ min , τ max	e, g, m	nCycles nAnts
	0.1, 0.9	0.1	0.2, 1	5, 3, 1	2	2

TABLE IV :

 IV Scalability

	Algorithm	PMs	VMs	Released	Migrations	Packing
				PMs	per VM	Efficiency
						(%)
		120	720	29	26	24.1
	FFD	240 504	1440 3024	58 124	26 27	24.1 24.6
		1008	6048	246	26	24.4
		120	720	36	5	30.0
	ACO	240 504	1440 3024	77 161	7 8	32.0 31.9
		1008	6048	322	9	31.9
		120	720	39	3	32.5
	V-MAN	240 504	1440 3024	79 122	5 4	32.9 24.2
		1008	6048	323	4	32.0
		120	720	37	1	30.8
	Sercon	240 504	1440 3024	74 155	1 1	30.8 30.7
		1008	6048	311	1	30.8

TABLE V :

 V Centralized vs. Unstructured P2P Topology

	Topology	Algorithm Migrations	Released	Packing
				PMs	Efficiency
					(%)
		FFD	6040	249	24.7
	Centralized	Sercon	1920	320	31.7
		ACO	-	-	-
		FFD	96494	246	24.4
	P2P	V-MAN	4189	323	32.0
		ACO	4015	322	31.9
		Sercon	1872	311	30.8

VII. ACKNOWLEDGEMENTS

We would like to express our gratitude to Louis Rilling and Nikos Parlavantzas for their detailed feedbacks. This research is funded by the French Agence Nationale de la Recherche (ANR) project EcoGrappe under the contract number ANR-08-SEGI-008-02. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr).

Choose (v, p) randomly according to the probability p v,p connections. One node serves as the introducer to bootstrap the system. To prevent concurrent access to PMs the prototype implementation integrates a distributed locking mechanism. PMs shutdown themselves when they do not host any VMs. VMs are represented by their requested capacity vectors. Each PM writes events (e.g. migration, consolidation, shutdown) in a local SQLite database during the experiment execution. Once the experiment is finished all databases are collected and merged into a single one for post-analysis. Emulator modules such as the introducer mechanism, consolidation algorithms, scheduler for shuffling and consolidation are defined in a configuration file for the ease of replacement.

The current implementation integrates four VMC algorithms: the FFD, Sercon, V-MAN state-of-the-art algorithms and the introduced migration-cost aware ACO-based algorithm. FFD is a static VMC algorithm which is often applied in the context of dynamic VMC. Consequently, it serves as the baseline for comparison in our work. In contrast, Sercon, V-MAN and our algorithm are dynamic VMC algorithms which were specifically designed to reduce the number of migrations.

B. System Setup

We have deployed the emulator on 42 servers of the Grid'5000 testbed in France. All servers are equipped with two CPUs each having 12 cores (in total 1008 cores). This allowed us to emulate one PM per core. In other words, throughout all the experiments each server hosts 24 emulator instances (one per core) which represent the emulated PMs.

The emulator considers three types of resources: CPU, memory, and network. It supports six kinds of VM instances: nano, micro, small, medium, large and xlarge, which are represented by their corresponding requested capacity vectors: (0.2, 0.5, 0.1), (1, 1, 1), (2, 1, 1), (4, 2, 2), [START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] and [START_REF] Weisstein | L1-norm[END_REF][START_REF] Quesnel | Cooperative and reactive scheduling in large-scale virtualized platforms with DVMS[END_REF][START_REF] Hermenier | Entropy: a consolidation manager for clusters[END_REF] respectively.

PMs have a total capacity of (48, 26, 20). They host 6 VMs, one of each type at the beginning of the experiment. Consequently, in total 6048 VMs are emulated. The experiment runs for six minutes. Consolidation is triggered by the PMs concurrently and independently every 30 seconds. The neighbourhood size is set to 16 PMs and the shuffling operation is triggered every 10 seconds by the PMs. Table II provides a summary of the introduced system parameters and their corresponding values.