Matthieu Jonckheere
email: m.t.s.jonckheere@tue.nl

Jean Mairesse
email: jean.mairesse@liafa.jussieu.fr.

Towards an Erlang formula for multiclass networks

Consider a multiclass stochastic network with state dependent service rates and arrival rates describing bandwidth-sharing mechanisms as well as admission control and/or load balancing schemes. Given Poisson arrival and exponential service requirements, the number of customers in the network evolves as a multi-dimensional birth-and-death process on a finite subset of N k . We assume that the death (i.e. service) rates and the birth rates depending on the whole state of the system, satisfy a local balance condition. This makes the resulting network a so-called Whittle network and the stochastic process describing the state of the network is reversible with an explicit stationary distribution that is in fact insensitive to the service time distribution. Given routing constraints, we are interested in the optimal performance of such networks. We first construct bounds for generic performance criteria, that can be evaluated using recursive procedures, these bounds being attained in the case of a unique arrival process. We then study the case of several arrival processes, focusing in particular on the instance with admission control only. Building on convexity properties, we characterize the optimal policy, and give criteria on the service rates for which our bounds are again attained.

Introduction

The Erlang formula [START_REF] Erlang | Solutions of some problems in the theory of probabilities of significance QUES9185_source[END_REF] has proved to be a central tool of performance evaluation for telephone networks. Its impressive and lasting success in an engineering context can be explained by both its simplicity and its robustness [START_REF] Bonald | Insensitive traffic models for communication networks[END_REF]. The Erlang formula is insensitive to the call duration distribution and depends on a unique parameter: the traffic intensity. The only assumptions which are required to apply the formula are Poisson arrivals. At the mathematical level, the key property is the reversibility of the one dimensional birth-and-death process. On the ground of this early work of Erlang has developed the whole theory of stochastic networks whose state evolves as a reversible stochastic process. Such networks became very popular with the seminal work of Kelly [START_REF] Kelly | Reversibility and Stochastic Networks[END_REF] further developed by Whittle [START_REF] Whittle | Systems in stochastic equilibrium[END_REF]. The crucial insensitivity property of the Erlang model extends to circuit-switched networks (without admission control and dynamic load balancing). More recently, (quasi-)reversible networks have emerged as a powerful tool to capture the essential dynamics of complex and diverse real-life telecommunication networks, see for instance [START_REF] Bonald | Insensitive load balancing[END_REF][START_REF] Bonald | A queueing analysis of maxmin fairness, proportional fairness and balanced fairness[END_REF]. Because the key performance indicators of these models are independent of all traffic characteristics beyond the traffic intensity, they provide simple and robust engineering rules, just like the Erlang formula.

The situation gets more complicated in the presence of admission control and/or load balancing. The admission control consists in possibly rejecting customers even when the full capacity of the network is not utilized. Load balancing consists in routing an arriving customer to one of the queues in a subset of possible target queues. These techniques ensure an efficient utilization of resources by taking into account the system state to make decisions. They have become a key component of computer and communication systems.

The corresponding mathematical model can be described by a general multi-dimensional birth-and-death process on a finite subset of N I , where I is the finite set of nodes (queues) of the network. The death (i.e. service) transition rates depend on the whole state of the system. Defining an admission control and/or a load balancing policy consists in tuning the birth (i.e. arrival) transition rates. More precisely, let us concentrate on one given class of customers arriving at rate ν. Admission control consists of defining, as a function of the state of the system x, the rate λ(x) ≤ ν at which the customers are admitted in the network. Assume that for this class, the arriving customers can be served by any of the nodes in a subset I of I. Load balancing (aka routing) consists in choosing the rates λ i (x), i ∈ I , i λ i (x) = λ(x), at which the admitted customers are assigned to the different nodes.

The goal is to find the policy which optimizes some performance criterion, typically the blocking probability of an arriving customer. This leads in many cases to very difficult optimization problems. A discussion of some existing results appears in [START_REF] Bonald | Insensitive load balancing[END_REF], see also the references therein. The book of Ross [START_REF] Ross | Multiservice Loss Models for Broadband Telecommunication Networks[END_REF] is also devoted to a special instance of this question: the model considered, known as the stochastic knapsack model, is a model with admission control but without routing (each class of customer is assigned to a specific and different node). Partial optimality results in dimension 2 and 3 are obtained, for service rates depending only on the local number of customers at the node.

In the present paper, we restrict our attention to networks where the service rates satisfy the so-called "balance condition" and we consider the optimization problem within the restricted subclass of policies for arrivals which satisfy an analogous "balance condition", the so-called insensitive policies. Such policies are called insensitive because the resulting stochastic network is insensitive in the sense that its stationary distribution depends on the service time distribution only via its mean.

So the questions are three-fold: (1) Is it possible to find the optimal insensitive policy ? (2) Can we efficiently evaluate the optimal insensitive policy ? (3) Is the performance of the best insensitive policy close to the one of the best policy ? Here we address only the first two questions, having in mind the hope that the answer to the third question is yes for a broad range of parameters. In any case, the optimal performance of insensitive policies provides a bound for the optimal performance of general policies. This may bring enough motivation for studying the former.

Since these questions are difficult to answer in general, we first focus on policies with an admission region shaped as a rectangular hyper-parallelepiped and give efficient recursive formulas to evaluate their performance. This provides computable lower and upper bounds for the performance of the optimal insensitive policy.

We then study the tightness of our bounds. When there is a unique arrival process, our bounds are always attained, i.e., the optimal insensitive policy can be described as a specific rectangular shaped policy.

Later on, we turn our attention to the case of several arrival processes and consider as its simplest instance, the case of networks with admission control only. This problem is of crucial importance when looking at the flow level modelling of fixed and wireless data networks [START_REF] Roberts | A survey on statistical bandwidth sharing[END_REF]. We assume that the state space is coordinate-convex (see Figure 1). A coordinate-convex policy is a policy with full admission within a coordinate-convex subset of the state space, and full rejection out of it (see Figure 1). We prove that these policies are extremal within insensitive policies: any insensitive policy can be decomposed as a convex combination of coordinate-convex policies. Using this result, we prove that the minimal blocking probability for insensitive policies is reached by a coordinate-convex policy.

We define a decentralized policy to be a coordinate-convex policy in which the admission region is the intersection of the whole state space with a rectangular hyper-parallelepiped. On Figure 1, the left case corresponds to a non-decentralized coordinate-convex policy, while the other two cases correspond to decentralized policies. Our results show that in general, decentralized policies are not optimal within insensitive policies. In other terms, there exist instances in which a coordinate-convex policy achieves a blocking probability which is strictly smaller than the one achieved by the best decentralized policy, which contrasts with the case of a unique arrival process. We provide a toy example of a network in which this phenomenon occurs. This emphasizes the intrinsic increased complexity of models where several classes of customers are competing. To give a complete picture, we also provide sufficient conditions on the model (monotonicity or light traffic) under which complete sharing policies (decentralized policies admitting all the traffic inside the state space) are optimal among insensitive policies.

The paper is organized as follows. Section 2 introduces the model, the notation and the objectives. In Section 3, we provide computable bounds for a broad set of performance criteria in the general case. Section 4 is a detailed analysis of networks with admission control only. In Section 5, we illustrate the concepts and the results on a toy example, which can be described as the simplest non trivial multiclass model.

General framework

Notation. Let e i be the point of N k defined by (e i ) i = 1, (e i ) j = 0, j = i. A Ferrers set is a finite subset E of N k such that:

x ∈ E, x i > 0 =⇒ x -e i ∈ E .
In other words, it is a coordinate-wise convex finite set. The set of all Ferrers sets is denoted by F(N k ). The set of Ferrers sets included in E ⊂ N k is denoted by F(E). The notation x ≤ y is used for the coordinate-wise ordering: ∀i, x i ≤ y i . We further denote:

|x| = k i=1 x i and |x| x = |x|! x 1 ! . . . x k ! .
We denote by 1 S the indicator function of S, that is the map taking value 1 inside S and 0 outside. We denote respectively by R + and R * + the set of non-negative and positive reals.

Model

Consider a network with a finite set of servers (nodes) I. An arriving customer is served by one of the nodes and then leaves the network. More precisely, I is partitioned into finitely many non-empty subsets I k , k ∈ K, each customer has a class which is an element of K, and a customer of class k has to be served by one of the nodes in I k . The state of the system is described by a vector in N I corresponding to the number of customers in each node. The state space, denoted by X , is assumed to be a Ferrers set:

X ∈ F(N I ) .
Class-k customers arrive according to a Poisson process of intensity ν k . The different arrival processes are mutually independent. An arriving customer of class k is either routed to a node in I k or rejected (recall that the state space is finite). The routing/admission policy depends on the whole state of the system at the instant of arrival. The service requirements of the customers are independent and exponentially distributed with parameter 1. The service rate at a given node depends on the whole state of the system.

Let X be the stochastic process valued in X describing the state of the system. The above assumptions result in X being a continuous-time jump Markov process, on the state space X , with infinitesimal generator Q = (q(x, y)) x,y∈X given by: ∀x ∈ X ,

⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ q(x, x -e i ) = φ i (x) if x -e i ∈ X q(x, x + e i ) = λ i (x) if x + e i ∈ X q(x, y) = 0 if y ∈ X , y = x -e i , x + e i .
(

) 1
It is convenient to define φ i , λ i , for all x in N I , so we set φ i (x) = 0 if (x-e i ) ∈ X , and λ i (x) = 0 if (x + e i ) ∈ X . The scalars λ i (x) define the routing/admission policy. By definition of the model, they satisfy:

Intensity constraints: ∀k ∈ K, i∈I k λ i (x) ≤ ν k (2)
QUES9185_source.tex; 7/07/2010; 12:16 p. 5

By definition, the rejection rate of class-k customers in state x is equal to ν k -i∈I k λ i (x).

The intensity h : X -→ R * + of a routing is defined by

h(x) = i∈I λ i (x) . ( 3
)
The maximum routing intensity ν : X -→ R * + is defined by

ν(x) = k∈K ν k 1 {∃i∈I k ,x+e i ∈X } . ( 4
)
Clearly, the intensity h of any routing satisfies: ∀x ∈ X , h(x) ≤ ν(x).

Concerning the service rates, we make the following assumption:

∀i ∈ I, ∀x ∈ X , x i > 0, φ i (x) > 0 . ( 5
)
In the paper, the service rates φ i (x) are assumed to be given and fixed. On the other hand, the routing rates λ i (x) will vary, and the actual state space of the process X will depend on this. For some choices of the routing rates, Q will not be irreducible. However, according to [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF], the set of recurrent states of Q is always strongly connected, and belongs to F(X ). In particular, there exists a unique stationary distribution for X that we denote by π.

Performance criterion. Below, the goal is to choose the routing rates in order to optimize a performance criterion. This criterion can be typically chosen as a given linear combination of the blocking probabilities of each class of customers. Consider p = (p k ) k∈K , p k > 0, k p k = 1. Set:

B p = x∈X π(x) k∈K p k 1 - i∈I k λ i (x) ν k . ( 6
)
Using the PASTA property, the blocking probability B of an arriving customer is a special case of this generic criterion: B = B (ν k /ν) k , where ν = k ν k . When the routing policy is defined via a balance function Λ, we denote the associated blocking probability by B p (Λ). We also give results which are valid for any criterion of the form E[f (X)], for a given f : X → R.

Balanced services and routing

The service rates are said to be balanced if there exists Φ :

X → R * + such that ∀i, ∀x ∈ X , x i > 0, φ i (x) = Φ(x -e i ) Φ(x) . ( 7
)
Consider the following property:

∀i, j, ∀x ∈ X , x i > 0, x j > 0, φ i (x)φ j (x -e i ) = φ j (x)φ i (x -e j ) . (8)
Clearly ( 7) implies [START_REF] Kelly | Reversibility and Stochastic Networks[END_REF]. Conversely, assume that (8) holds. Set o = (0, . . . , 0). Consider a directed path from o to x in N I , that is a sequence of points (

x 0 = o, x 1 , . . . , x n = x), such that x k -x k-1 = e i k , ∀1 ≤ k ≤ n. Define Φ : X → R * + by the formula: Φ(x) = C φ i 1 (x 1 )φ i 2 (x 2 ) • • • φ in (x n ) -1 .
where C is some positive constant. Using (8), we can prove that the value of Φ(x) does not depend on the chosen directed path from o to x. Formula (7) follows readily.

Similarly, the routing rates are balanced if the following equivalent conditions are satisfied:

∃Λ : X → R * + , ∀i, ∀x ∈ X , x + e i ∈ X , λ i (x) = Λ(x + e i )/Λ(x) . (9) ∀i, j, ∀x ∈ X , x + e i ∈ X , x + e j ∈ X, λ i (x)λ j (x + e i ) = λ j (x)λ i (x + e j ) .
It is often convenient to define Λ or Φ on N I instead of X . Of course, the actual rates λ i and φ i depend only on the restrictions of Λ and Φ to X .

Assume that both the service and the routing rates are balanced. Using ( 7) and ( 9), we get, ∀x ∈ X , x

+ e i ∈ X , Φ(x)Λ(x)λ i (x) = Φ(x + e i )Λ(x + e i )φ i (x + e i ) .
Since λ i (x) = q(x, x + e i ) and φ i (x + e i ) = q(x + e i , x), we conclude that the process X is reversible and that the stationary distribution is given by

π(x) = Φ(x)Λ(x) y∈X Φ(y)Λ(y) . ( 10
)
The balance conditions are obviously restrictive conditions. For instance, ( 9) is not satisfied for usual routing policies such as "join-the-shortest-queue".

The balance condition goes back to Kelly [START_REF] Kelly | Reversibility and Stochastic Networks[END_REF] (the slightly different concept of job-balance was developed by Hordijk et al [START_REF] Hordijk | Networks of queues, part 1: Job-local-balance and the adjoint process; part 2: General routing and service characteristics[END_REF]). Balance is satisfied for example if the rates at node i depend on x only via x i or if the service capacities are fairly shared between classes i.e., φ i (x) = c x i |x| , or more generally in a bandwidth sharing network operated under the balanced fairness allocation [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF].

It was recently proved that balance conditions are closely related to insensitivity. Assuming that the service rates are balanced, a necessary and sufficient condition for the insensitivity property to hold is that the routing rates be balanced, see [START_REF] Serfozo | Introduction to Stochastic Networks[END_REF][START_REF] Bonald | Insensitivity in processor-sharing networks[END_REF].

In the sequel, we always assume that the service rates and the routing rates are balanced which implies the insensitivity of the studied network. We shall then speak of insensitive policies to refer to those policies with balanced service and routing rates. The model defined in Section 2.1 corresponds, at the network level, to exponentially distributed service times. However, since we restrict our attention to insensitive policies, all the results remain true for i.i.d. generally distributed service times.

QUES9185_source.tex; 7/07/2010; 12:16 p. 7

Admissible balance functions

From now on, assume that the service rates (φ(x)) x∈X are balanced (by a balance function Φ) and fixed.

Let A be the set of normalized balance functions which satisfy the routing constraints, i.e.,

A = Λ : N I → R + , ∀x / ∈ X , Λ(x) = 0 , x∈X Λ(x)Φ(x) = 1 , ( 11
)
∀x, ∀i ∈ K,

j∈I i Λ(x + e j ) ≤ ν i Λ(x) . ( 12
)
Such balance functions are called admissible. To each admissible balance function, we can associate the routing rates defined by [START_REF] Leino | Insensitive load balancing in data networks[END_REF]. Below, we often identify an admissible balance function with the routing policy it defines.

In the following, it will often be convenient to relax the normalization condition ( 11), when considering a balance function. To differentiate between both cases, we shall use the notation Λ instead of Λ when a balance function is not normalized.

We can characterize the structure of A as follows.

Proposition 2.1. The set A is convex and compact (for the topology of pointwise convergence). The blocking probability B p is a linear function on A:

B p (Λ) = 1 - x∈X Φ(x) i∈K p i ν i j∈I i Λ(x + e j ) .
Proof. From the constraints ( 11) and ( 12), it is easily checked that if Λ1 and Λ2 belong to A, so does tΛ1 + (1t)Λ2 for t ∈ [0, 1]. Since A is a set of bounded functions with finite support X , it is compact. Consider now a balance function Λ. Expressing the routing rates as a function of Λ and using [START_REF] Pla | Martï¿ 1 2 nez-Bauset. Optimal robust policies for bandwidth allocation and admission control in wireless networks[END_REF], we can rewrite equation ( 6) as:

B p (Λ) = x∈X Λ(x)Φ(x) k∈K p k 1 - 1 ν k i∈I k Λ(x + e i ) Λ(x) = 1 - x∈X Φ(x) k∈K p k ν k i∈I k Λ(x + e i ) .
As a consequence,

B p (tΛ1 + (1 -t)Λ2) = tB p (Λ1) + (1 -t)B p (

Λ2). P 3 Rectangular balance functions and performance bounds

In this section, we focus on balance functions characterized by an admission region reduced to the intersection of X with a rectangular hyper-parallelepiped y ↓ = {x ≤ y}. We show how to use these balance functions to derive computable lower and upper bounds for the performance of the optimal insensitive policy.

Rectangular balance function

Definition 3.1. Consider a point y ∈ X and a function g : X → R * + such that g ≤ ν, where ν is the maximum routing intensity defined in [START_REF] Bonald | Insensitivity in processor-sharing networks[END_REF]. The rectangular balance function Λy,g : N I → R + associated with y and g is defined by:

Λy,g (x) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 if x = y g(x) -1 i∈I Λy,g (x + e i ) if x ≤ y, x = y 0 otherwise .
Any admissible balance function defined on X ∩ y ↓ can be represented as a rectangular balance function by choosing g appropriately. This can be shown recursively, starting with the extremal points of the state space, that is:

x ∈ X ∩ y ↓ , ∀i, x + e i ∈ X ∩ y ↓ .
On the other hand, a normalized rectangular balance function Λ y,g is not necessarily admissible. Consider the rates λ i (x) associated with Λ y,g and defined according to [START_REF] Leino | Insensitive load balancing in data networks[END_REF]. We have i∈I λ i (x) = g(x) ≤ ν(x). However, the rates may or may not satisfy the intensity constraints (2). This is an important point, so we illustrate it with an example.

ν 2 x 1 x 1 N x x 2 ν 1 2 N ≤ ≤
λ 1 (x) ≤ 1/2, λ 2 (x) ≤ 1/2,
which for balance functions boil down to:

Λ(x) ≥ 2Λ(x + e 1 ), Λ(x) ≥ 2Λ(x + e 2 ).
Consider the state space

X = {(x 1 , x 2 ), x 1 ≤ N, x 2 ≤ N }. So the maximum routing intensity is ν(x) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 for x 1 < N, x 2 < N 1/2 for x 1 < N, x 2 = N or x 1 = N, x 2 < N 0 for x 1 = N, x 2 = N .
Consider the point y = (n, n) with n < N, and the function g = ν. The corresponding rectangular balance function is:

Λy,ν :

1 • • • 1 1 1 1 . . . 4 3 2 1 . . . 1 0 6 3 1 . . . 2 0 1 0 4 1 . . . . . . • • • • • • • • • • • • • 1 (13)
The intensity constraints are not satisfied except on the diagonal {(i, i), 0 ≤ i ≤ n -1}. For instance, for the point x = (n -1, n -2), we have

λ 1 (x) = Λy,ν (x + e 1 )/Λ y,ν (x) = 1/3, λ 2 (x) = Λy,ν (x + e 2 )/Λ y,ν (x) = 2/3 >> ν 2 .
Assume now that ν 1 = x and ν 2 = 1x, for x irrational between 0 and 1. The maximum routing intensity is unchanged and equal to 1 on y ↓ . So the rectangular balance function associated with y and ν is still given by [START_REF] Ross | Multiservice Loss Models for Broadband Telecommunication Networks[END_REF]. But now the intensity constraints are violated at all the points of y ↓ .

We now come up with an explicit expression for rectangular balance functions. An increasing path from x to y, y ≥ x, is a sequence of points (x 0 = x, x 1 , . . . , x k = y) such that x j+1x j = e i j for all j. Let P (x, y) be the set of increasing paths from x to y. Lemma 3.2. We have

Λy,g (x) = ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ 1 if x = y p∈P (x,y) z∈p,z =y g(z) -1 if x ≤ y, x = y 0 otherwise . ( 14
)
Proof. Denote by H(x, y) the right-hand side of [START_REF] Serfozo | Introduction to Stochastic Networks[END_REF]. A path from x to y can be decomposed as a path from x to x + e i and a path from x + e i to y, for some i such that x i < y i . As a consequence, we have: H(x, y) = i:x i <y i H(x + e i , y)g(x) -1 . We conclude that H and Λy,g satisfy the same recursive equations and the same initial condition: H(y, y) = 1 = Λy,g (y). P

Recursive evaluation of rectangular balance functions

We now show how to compute the performance of policies corresponding to rectangular balance functions.

We hence still assume that the service rates (φ(x)) x∈X are balanced (by a balance function Φ) and fixed. We fix a rectangular balance function Λy,g (y ∈ X ) and consider the routing rates λ i (x) associated with the balance function and defined according to [START_REF] Leino | Insensitive load balancing in data networks[END_REF].

As underlined by the Example 1, the intensity constraints may not be satisfied. However, let us consider the model operated under this (possibly non-admissible) policy. That is, consider the stochastic process X with infinitesimal generator (1) for λ, φ. We first show how to compute the performance of the policy. Later on, we will use this to bound the performance of admissible policies. Define:

C(y, g) = x∈X Λy,g (x)Φ(x), P j (y, g) = x∈X
Λy,g (x + e j )Φ(x) .

Observe that C(y, g) is the normalizing constant, that is, the stationary distribution π y,g satisfies: ∀x ∈ X , π y,g (x) = C(y, g) -1 Λy,g (x)Φ(x) .

Proposition 3.3. Let B p = B p (Λ y,g ) be the blocking probability defined as in [START_REF] Erlang | Solutions of some problems in the theory of probabilities of significance QUES9185_source[END_REF]. We have

B p = 1 - j∈K p j ν -1 j i∈I j P i (y, g) C(y, g) . ( 15
)
The quantities P j and C can be computed using the recursive schemes:

C(y, g) = Φ(y) + i∈I:y i >0 C(y -e i , g)g(y -e i ) -1 , ( 16
)
P j (y, g) = Φ(y -e j )1 {y j >0} + i∈I:y i >0 P j (y -e i , g)g(y -e i ) -1 . ( 17
)
Proof. Formula ( 15) is obtained directly from Prop. 2.1. Let us prove (16). If x ≤ y, x = y, we have Λy,g (x) = i:x i <y i

Λy-e i ,g (x)g(ye i ) -1 .

So we get

C(y, g) = x∈X Λy,g (x)Φ(x) = Λy,g (y)Φ(y) + x≤y,x =y Φ(x) i:x i <y i
Λy-e i ,g (x)g(y

-e i ) -1 = Φ(y) + i:y i >0 C(y -e i , g)g(y -e i ) -1 .
The proof of (17) is analogous. P An equivalent recursive formula implying the service rates instead of the balance function can be considered instead of ( 16)-(17). Define P j , j ∈ I, and C such that P j (y, g)/C (y, g) = P j (y, g)/C(y, g) and

C (y, g) = 1 + i:y i >0 C (y -e i , g)φ i (y)g(y -e i ) -1 , P j (y, g) = φ j (y)1 {y j >0} + i:y i >0 P j (y -e i , g)φ i (y)g(y -e i ) -1 .
Other performance criteria. Consider a performance criterion of the form P f = E[f (X)] for some function f : X → R + . Proposition 3.4. We have P f (y) = D(y, g)/C(y, g), where D(y, g) can be evaluated using the recursive scheme:

D(y, g) = f (y)Φ(y) + i∈I:y i >0 D(y -e i , g)g(y -e i ) -1 .

Decentralized policies

We introduce a subclass of admissible balanced functions called decentralized balance functions. Let k be a class, define x (k) to be the point such that:

x (k) j =
x j for j ∈ I k 0 otherwise. Decentralized balance functions correspond to policies having the desirable property that the routing intensities concerning a given class of customers depend only on the number of customers of that class present in the network. Definition 3.5. Consider a point y ∈ N I , not necessarily in X . The decentralized balance function Λy associated with y is defined by:

Λy (x) = ⎧ ⎨ ⎩ k∈K |y (k) -x (k) | y (k) -x (k) ν -|y (k) -x (k) | k if x ∈ y ↓ ∩ X 0 otherwise . ( 18
)
The normalized version of Λy is easily seen to be an admissible balance function. When y ∈ X , the decentralized balance function is the rectangular balance function (see Definition 3.1) associated with y and ν.

Let us define the decentralized routing policy associated with the decentralized balance function. The intensity function (see (3)) of the decentralized routing policy is

∀x ≤ y, h y (x) = k∈K ν k i∈I k y i -x i |y (k) -x (k) | 1 {x+e i ∈y ↓ ∩X } .
The decentralized policies work as follows. Do not accept customers outside the region y ↓ . Inside the region y ↓ ∩ X , all possible customers are accepted, except at points

x ∈ y ↓ ∩ X such that ∃k ∈ K, ∃i, j ∈ I k , x+ e i ∈ y ↓ ∩ X , x + e j ∈ y ↓ ∩ X c . ( 19
)
Therefore, the decentralized policy becomes particularly simple when there exists no such point. This happens in the following two cases among others:

1. When y ∈ X , implying that y ↓ ∩ X = y ↓ . When |K| = 1, the decentralized policies with y ∈ X are extremal and boil down to the simple policies described in [START_REF] Bonald | Insensitive load balancing[END_REF] (see Section 3.6).

2 2n • • • • • • • • • • • • 2 n (20)
Here we check that we have full admission of customers strictly inside the region y ↓ ∩ X = y ↓ . Assume now that n > N. We obtain Λy by restricting (20) to the state space X . After renormalization, we obtain exactly the same function as before. So we still have full admission strictly inside y ↓ ∩ X . More generally, it is easily seen that full admission would hold for the decentralized policy associated with any point y. This is consistent with the fact that |I| = |K|.

X = {(x 1 , x 2 ), x 1 ≤ N, x 2 ≤ N }. Choose y = (y 1 , y 2 ) ∈ X .

Applying (18), we get

Λy :

1 • • • 1 1 1 1 . . . 4 3 2 1 . . . 10 6 3 1 . . . 20 10 4 1 . . . . . . • • • • • • • • • • • • • 1 (21)
Observe that the balance function coincides with the balance function obtained in Example 1. This is natural since the balance function considered in Example 1 corresponds to the possibility of routing the total traffic indistinctively to both classes which boils down to a single-class system with two nodes. For a point x = (x 1 , x 2 ), x ∈ y ↓ , x = y, the routing is

λ 1 (x) = y 1 -x 1 y 1 -x 1 + y 2 -x 2 , λ 2 (x) = y 2 -x 2 y 1 -x 1 + y 2 -x 2 .
So we have λ 1 (x) + λ 2 (x) = 1, and there is full admission at point x for x ∈ y ↓ , x = y.

x ν 1

x 2 x 3 x +

= {(x 1 , x 2 , x 3 ), x 1 ≤ N, x 2 + x 3 ≤ N }. Choose y = (y 1 , y 2 , y 3 ). Applying (18), we get Λ y (x) =
|y (1) x (1) | y (1) x (1) ν -|y (1) -x (1) | 1

ν -y 3 +x 3 2
For a point x = (i, j, k) ∈ X , the routing is

λ 1 (x) = ν 1 y 1 -i y 1 -i + y 2 -j 1 {i+1≤N } , λ 2 (x) = ν 1 y 2 -j y 1 -i + y 2 -j 1 {j+k+1≤N } and λ 3 (x) = ν 2 1 {k+1≤y 3 } 1 {j+k+1≤N } .
Hence we have

λ 1 (x) + λ 2 (x) = ν 1 y 1 -i y 1 -i + y 2 -j 1 {i+1≤N } + y 2 -j y 1 -i + y 2 -j 1 {j+k+1≤N } .
We do not have full admission at point x when i + 1 ≤ N and j + k + 1 > N.

QUES9185_source.tex; 7/07/2010; 12:16 p. 14

Recursive evaluation of decentralized policies

When y ∈ X , the decentralized policies are a subclass of the rectangular policies defined in Section 3.1. So the recursive formula (15) can be applied directly.

If y / ∈ X , then the decentralized policy is not rectangular but is however the restriction of a rectangular policy defined on a larger state space containing both X and y ↓ . By following the exact same steps, we prove that the results of Proposition 3.3 hold in this generalized context. More precisely, we have the following.

Let X be a finite Ferrers set containing both X and y ↓ . For z ∈ X , let Λz be the decentralized balance function on X associated with z and defined according to (18). For z ∈ X , define:

C(z) = x∈X Λz (x)Φ(x), P j (z) = x∈X Λz (x + e j )Φ(x) . Define ν : X -→ R * + by ν (x) = k∈K ν k 1 {∃i∈I k ,x+e i ∈X } .
Proposition 3.6. Consider y / ∈ X . The blocking probability of the decentralized policy on X associated with Λ y satisfies

B p (Λ y ) = 1 - j∈K p j ν -1 j i∈I j P i (y) C(y)
.

The quantities P j and C can be computed using the recursive schemes:

C(z) = Φ(z)1 {z∈X } + i∈I:z i >0 C(z -e i )ν (z -e i ) -1 , P j (z) = Φ(z -e j )1 {z-e j ∈X } + i∈I:z i >0 P j (z -e i )ν (z -e i ) -1 .

Bounds

We obtain bounds by applying the following simple principle. Consider a routing associated with the intensity function h. If h ≤ g, then the balance function can be decomposed in terms of balance functions of rectangular policies with intensity g. We state more formally this result in the following lemma.

Theorem 3.7. Consider an admissible balance function Λ with intensity h such that h ≤ g, we have:

Λ = y∈X c y Λ y,g , with (c y ) y∈X defined by c y = Λ y,g (y) -1 Λ(y) -g(y) -1 i∈I Λ(y + e i ) .
Proof. Introduce the frontier of the attainable states under Λ, H = {x : Λ(x) = 0, ∀i ∈ I, Λ(x + e i ) = 0}. Since Λ is admissible, for every reachable state not in H, we have

h(x) -1 i∈I Λ(x + e i ) = Λ(x) =⇒ g(x) -1 i∈I Λ(x + e i ) ≤ Λ(x) .
Set c y = Λ y,g (y) -1 Λ(y)g(y) -1 i∈I Λ(y + e i ) . We have shown that c y is non-negative. Now define Λ = y∈X c y Λ y,g . Using an induction on the state space (starting from the states in H), we prove that Λ = Λ . P

A direct consequence of the above Proposition is that:

B p (Λ) ≥ min y∈X B p (Λ y,g ) . ( 22
)
Corollary 3.8. Denote by B * p the minimum value of the blocking probability B p over A. We have the following bounds:

min y∈X B p (Λ y,ν ) ≤ B * p ≤ min y∈N N B p (Λ y ) = min y:∀i, y (i) ∈X B p (Λ y ) .
Proof. Since ν is an upper bound of the intensity for any admissible policy, we can always apply ( 22) with g = ν. This provides the lower bound for B * p . The upper bound is clear: it follows from the fact that the decentralized balance functions Λ y are admissible. P Remark 3.1. We could have stated the same result for any performance criterion P f : A → R + which is convex, that is, which satisfies:

∀t ∈ [0, 1], ∀Λ 1 , Λ 2 ∈ A, P f ((1 -t)Λ 1 + tΛ 2 ) ≥ (1 -t)P f (Λ 1 ) + tP f (Λ 2 ) . ( 23
)

One class of customers

Structural and optimality results for networks with only one arrival process have been given in [START_REF] Bonald | Insensitive load balancing[END_REF]. We show that the results from [START_REF] Bonald | Insensitive load balancing[END_REF] are a special case of the above results. Also the situation becomes much simpler, and for instance, the bounds of Corollary 3.8 are attained.

The set I is defined as before. The set K is reduced to a singleton and we simplify the notation accordingly. For instance, ν is the rate of the unique arrival process.

Consider a rectangular balance function associated with y ∈ X and ν. We have by definition i∈I λ i (x) = ν. Since there is a single arrival process, the intensity constraint ( 2) is satisfied and Λy,g is admissible. Also, we have (using ( 14) and ( 18))

Λy,g (x) = Λy (x) = |y-x| y-x ν -|y-x| if x ∈ y ↓ 0 o t h e r w i s e .
Therefore any rectangular balance function is decentralized. The decentralized balance functions (also called "simple" balance functions) are in that case 'extremal' and form a basis to decompose admissible balance functions. Next result is a corollary of Theorem 3.7 (see also [START_REF] Bonald | Insensitive load balancing[END_REF]Theorem 1]).

Corollary 3.9. Consider an admissible balance function Λ. There exists

(c x ) x∈X , c x ≥ 0, x c x = 1, such that: Λ = y∈X c y Λ y . ( 24
)
This implies in particular, that for the blocking probability B defined in ( 6), a simple balance function is optimal. This holds more generally for any convex (see ( 23)) performance criterion.

Furthermore, the blocking probability can be evaluated very easily. By specializing the results in Section 3.2, we get that B(Λ y ) = π y (y) = Φ(y)/C(y) which can be evaluated recursively using the formula (16) for C(y):

(B(Λ y )) -1 = 1 + i∈I:y i >0 φ i (y) ν (B(Λ y-e i )) -1 , ( 25
) with B(Λ o ) = 1.

Networks with admission control

We now consider models with more than one arrival process. We restrict ourselves to the situation where each node is fed by only one arrival process: K = I. There is no "routing" but only admission control. The model includes for example bandwidth sharing processor sharing network operated under balance fairness [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF] and subject to admission control schemes.

Note that the service rates can be coupled in a very complex way.

The book of Ross [START_REF] Ross | Multiservice Loss Models for Broadband Telecommunication Networks[END_REF] gives a good overview of existing results when the service rates are "uncoupled" i.e., depend on the local number of customers at each node only: φ i (x) = φ i (x i ) (the so-called stochastic knapsack problem). The author studies several types of insensitive policies under more specific assumptions on the state space and/or the service rates of the network. The optimality results provided concern the case of locally dependent routing intensities, λ i (x) = λ i (x i ), and mostly in dimension 2 or 3.

In this Section, we do not restrict ourself to the assumption that φ i (x) = φ i (x i ) but consider any balanced service rates (i.e. satisfying [START_REF] Hordijk | Networks of queues, part 1: Job-local-balance and the adjoint process; part 2: General routing and service characteristics[END_REF]). We first give a characterization of any insensitive policy in terms of coordinate-convex policies, i.e. policies such that customers are fully accepted in a Ferrers shaped subset of the state space. This allows us to conclude that an optimal insensitive policy is necessarily coordinate-convex. We then give conditions for which the optimal policy is the complete sharing policy, i.e. consists in always accepting customers when possible. In this last case, we will be able to compute efficiently the optimal performance of the network.

Extremal stationary measures

Let X , I = K, and Φ be fixed.

The complete sharing policy is the policy in which customers are admitted whenever it is possible. It is characterized by the rates :

∀x ∈ X , ∀i ∈ I, λ i (x) = ν i if x + e i ∈ X 0 otherwise .
We denote by Λ d the balance function corresponding to the complete sharing policy:

∀x ∈ X , Λd (x) = i ν x i i .
Observe that Λ d coincides with the normalized decentralized balance function Λ y associated with a point y such that X ⊂ y ↓ . It corresponds to the following coordinate-convex policy:

if x + e i ∈ C, then λ i (x) = ν i , if x + e i ∈ C, then λ i (x) = 0.
In words, customers are accepted in a Ferrers shaped subset of the state space.

We now state the main result of this section.

Theorem 4.2. An admissible balance function Λ can be decomposed as:

Λ(x) = C∈F(X ) β(C)Λ C (x),
with β(C) ≥ 0 for all C and C∈F(X ) β(C) = 1.

Observe the difference with Theorem 3.7: here all the balance functions Λ C are admissible. Theorem 4.2 is hence similar to the decomposition obtained for the single-class systems in Corollary 3.9.

Proof. We use an induction on the cardinality of the state space. If the state space contains one state, the result is obviously true. Suppose it is satisfied for any X ∈ F(N I ) of cardinality less than or equal to n -1. Consider a state space X ∈ F(N I ) of cardinality n and an admissible balance function Λ. We are going to show that: Λ(x) = β ΛX (x) + G(x), with G being an admissible balance function defined on a strictly smaller state space X ⊂ X .

Consider

H(x) = Λ(x)/ i ν x i i .
Recall the intensity constraints (see ( 2) and ( 9)): ∀i, ∀x, Λ(x+ e i )/ Λ(x) ≤ ν i . These inequalities can be rewritten as: ∀i, ∀x, H(x) ≥ H(x + e i ). Now define ω as the smallest value of H on X (which is attained on the frontier of X since H is coordinate-wise decreasing) and x 0 as a point of the frontier such that

H(x 0 ) = ω. Set G(x) = H(x) -ω1 {x∈X } . We have, ∀x ∈ X , Λ(x) = G(x) i ν x i i + ω i ν x i i Λ(x) = G(x) i ν x i i + ω ΛX (x) .
QUES9185_source.tex; 7/07/2010; 12:16 p. 18

For all x ∈ X , x + e i ∈ X ,

G(x + e i ) = H(x + e i ) -ω ≤ H(x) -ω = G(x) . ( 26
)
Set G(x) = G(x) i ν x i i . Using (26), we obtain that G(x + e i )/ G(x) ≤ ν i . Therefore G is an admissible balance function. By construction G(x 0 ) = 0. Therefore, G is non-zero on a set of cardinality less than or equal to n -1. Also, since X is a Ferrers set and the point x 0 belongs to the frontier of X , the set X \ {x 0 } is still a Ferrers set. So, G can be viewed as an admissible balance function on the Ferrers set X \ {x 0 } of cardinality n -1. This concludes the proof. P

Let the performance criterion be the blocking probability B p defined in [START_REF] Erlang | Solutions of some problems in the theory of probabilities of significance QUES9185_source[END_REF]. We can deduce from Theorem 4.2 that the optimal insensitive policy is a coordinate-convex policy.

Corollary 4.3. Let B *

p be the infimum of B p over all insensitive policies. We have:

B * p = min C∈F(X ) B p (Λ C ),
where Λ C is introduced in Definition 4.1.

This optimality result extends to any convex criterion. In general, the minimum is not attained for a decentralized policy. This is illustrated in Section 5.

Recursive formulas and optimality of a complete sharing policy

We show how to compute the blocking probabilities recursively (Proposition 4.4). We also provide sufficient conditions to guarantee that the optimal policy is a complete sharing policy.

B p (Λ C ) = 1 - 1 C(C) i p i P i (C) ν i . ( 27
)
The quantities P i (C) and C(C) can be evaluated recursively. For a point x / ∈ C such that C ∪ {x} is also a Ferrers set, we have:

C(C ∪ {x}) = C(C) + Λd (x)Φ(x), ( 28
) P i (C ∪ {x}) = P i (C) + Λd (x)Φ(x -e i ) . ( 29
)
Proof. Let us prove formula (27). Recall that the stationary distribution is given by (Φ(x)Λ C (x)) x∈C . Using λ i (x) = Λ C (x + e i )/Λ C (x), the blocking probability B i (Λ C ) of customers of class i satisfies:

1

-B i (Λ C ) = x∈C Φ(x)Λ C (x) Λ C (x + e i ) Λ C (x) 1 ν i = x∈C Φ(x) ΛC (x)
y∈C Φ(y) ΛC (y) ΛC (x + e i ) ΛC (x)

1 ν i = x∈C Φ(x) ΛC (x + e i )
y∈C Φ(y) ΛC (y)

1 ν i = P i (C) ν i C(C) .
Formula (27) follows readily. Consider a Ferrers set C and a point x / ∈ C such that C ∪ {x} is also a Ferrers set. We have:

C(C ∪ {x}) = z∈C∪{x} Λd (z)1 {z∈C∪{x}} Φ(z) = C(C) + Λd (x)Φ(x). P j (C ∪ {x}) = z∈C∪{x} 1 {z+e j ∈C∪{x}} Λd (z + e j )Φ(z),
Using that C ∪ {x} is a Ferrers set, z + e j ∈ C ∪ {x} and z ∈ C ∪ {x} implies z ∈ C and z + e j ∈ C or z = xe j . Hence:

P j (C ∪ {x}) = z∈C 1 {z+e j ∈C} Λd (z + e j )Φ(z) + Λd (x)Φ(
xe j ), P j (C ∪ {x}) = P j (C) + Λd (x)Φ(xe j ). P Proposition 4.5. Let X be a r.v. distributed according to the stationary number of customers. We have:

B p (Λ C ) = 1 - i∈I p i ν i E[φ i (X)] . ( 30
)
Let x be a point such that C ∪ {x} ∈ F(X ). The blocking probabilities satisfy:

B p (Λ C∪{x} ) ≤ B p (Λ C ) ⇐⇒ i∈I p i ν i E[φ i (X)] ≤ i∈I p i ν i φ i (x) . ( 31
)
Proof. Denote by B i (Λ C ) the blocking probability of class i customers. We first prove the rate conservation law:

ν i (1 -B i (Λ C )) = E[φ i (X)] .
Let (X(t)) t be a Markov process describing the state of the network in stationary behavior. The processes M t = X i (t) -t 0 (λ i (X(s))φ i (X(s))ds are square integrable martingales, for all i ∈ I, see for instance [START_REF] Robert | Stochastic Networks and Queues[END_REF]. By Doob's martingale convergence theorem, M t converges a.s. to a finite limit as t goes to infinity, so M t /t converges a.s. to 0. Since the state space is finite, we also have that X i (t)/t converges a.s. to 0. It implies that:

1 t t 0 (ν i 1 {X(s)+e i ∈C} -φ i (X(s)))ds t -→ ν i (1 -B i (Λ C )) -E[φ i (X)] = 0 .
By summing over i, we get (30). Now let us prove (31). Write P p (C) = i (p i /ν i )P i (C) . We have

B p (Λ C∪{x} ) ≤ B p (Λ C ) ⇐⇒ P p (C ∪ {x}) C(C ∪ {x}) ≥ P p (C) C(C) .
Using Proposition 4.4, simple computations, and (30), this is equivalent to:

i∈I p i ν i φ i (x) ≥ P p (C) C(C) = 1 -B p (Λ C ) = i∈I p i ν i E[φ i (X)] .
P The simple comparison rule (31) allows to conclude that a complete sharing policy is optimal when the load of the network is small enough, or when the network is work conserving. We thus have the following results as direct consequences of Proposition 4.5.

Corollary 4.6 (Light traffic regime). Suppose that:

min x∈X -o i∈I p i ν i φ i (x) ≥ 1 , ( 32
)
then a complete sharing policy is optimal for the blocking probability B p .

Corollary 4.7 (Work-conserving network). Suppose that:

i φ i (x) = c1 {x =o} , ( 33
)
for some constant c ∈ R * + . Then a complete sharing policy is optimal for the blocking probability of an arrival customer, that is B p with p i = ν i /( j ν j ).

Finding the optimal routing can be done by using Proposition 4.4. However, the complexity of such an optimization program might be too big to be considered as a practical scheme. In any case, the results of Section 3 still applies: by focusing on policies having rectangular hyper-parallelepiped state spaces, we get easily computable upper and lower bounds of the optimal performance.

A four state example

Consider a model with two classes of customers and two nodes (|K| = |I| = 2) and a state space X = {(0, 0), (1, 0), (0, 1), (1, 1)}. The arrival rates of the classes are denoted by λ 1 and λ 2 respectively. The service rates φ i (x) are supposed to be balanced which means that: φ 1 (1, 1)φ 2 (0, 1) = φ 2 (1, 1)φ 1 (1, 0). We use the notation

φ 1 (1, 0) = a, φ 2 (0, 1) = b, φ 1 (1, 0)φ 2 (1, 1) = c .
In Figure 5, we have represented all the different coordinate-convex insensitive policies as well as various sensitive policies (for which the traffic of a given class in a given state is either fully accepted or fully rejected). The vertices represent the reachable states for each policy while the edges correspond to the transitions between states, of intensity λ 1 for an horizontal edge and λ 2 for a vertical one. We denote by P a , P b , P abc the three decentralized policies, and by P ab the unique non-decentralized coordinate-convex policy. The blocking probability of an arriving customer for the four insensitive policies are given by:

B(P a ) = λ 1 (λ 1 + λ 2 2 ) + λ 2 a(λ 1 + λ 2 )(1 + λ 2 /a) , B(P b ) = λ 2 (λ 1 + λ 2 ) + λ 2 1 b(λ 1 + λ 2 )(1 + λ 1 /b) , B(P ab ) = λ 2 /a + λ 1 /b 1 + λ 1 /b + λ 2 /a , B(P abc ) = λ 1 (λ 1 /b + λ 1 λ 2 /c) + λ 2 (λ 2 /a + λ 1 λ 2 /c) (λ 1 + λ 2 )(1 + λ 1 /b + λ 2 /a + λ 1 λ 2 /c
) . Consider now the rectangular (not necessarily admissible) policies of Sections 3.1 and 3.2. They are all represented in Figure 6, with the transitions intensities being represented on the edges. The two policies on the left of Figure 6 are non-admissible (let us call them P 1 and P 2 ), while the one on the right is P abc . The blocking probabilities of an arriving customer for P 1 and P 2 are:

Pb

B(P 1 ) = λ 1 λ + λ 2 a(1 + λ/a) , B(P 2 ) = λ 2 λ + λ 2 b(1 + λ/b) .
In particular, we check that it is possible to have min(B(P 1 ), B(P 2 )) < min(B(P a ), B(P b ), B(P ab ), B(P abc )) , in which case the lower bound computed in Corollary 3.8 is not attained. We represent in Figure 7 the value of the blocking for each coordinate-convex policy when c = 0.1 (left), c = 2 (right) for a and b varying from 0 to 4. The color code is as follows: the green curve corresponds to P a , the blue curve corresponds to P b , the yellow one to P ab , and the red one to P abc . Hence, the optimality of the non-decentralized policy P ab can be observed for c = 0.1, while for c = 2 the complete sharing policy P abc is always optimal. In accordance with Corollary 4.6, the complete sharing policy P abc is optimal in light traffic in both cases. Different observations can be made:

• Scenario 1 falls into a well studied case of a loss network with two circuits and symmetric service requirements since φ 1 (1, 0) = φ 2 (0, 1) = φ 1 (1, 1) = φ 2 (1, 1). The optimal policy is known to be one of the policies of Figure 5, see [START_REF] Ross | Multiservice Loss Models for Broadband Telecommunication Networks[END_REF]. We are in the domain of application of Proposition 4.6, so the complete sharing policy is optimal among insensitive policies. Since all the service rates are equal, it is clear that this policy is actually optimal among sensitive policies as well. It explains why all the curves correspond in Figure 8 (left). The non-monotonicity of the blocking probability with respect to the load (due to the trade-off between the influences of the two classes) can be observed.

• In the scenarios 2,3, and 4, the asymmetry of the service rates makes the insensitive policies perform worse than the sensitive ones for some loads. The lower bound of Corollary 3.8 becomes very loose in light traffic, while it is attained in heavy traffic.

• In scenarios 2 and 3, decentralized policies are optimal among insensitive policies while a non-decentralized policy is the best insensitive policy in scenario 4 for moderate loads. The service rates are balanced and given by a fair sharing between classes ( i.e. of the type φ i (x) = x i /( j x j )). The authors show numerically that decentralized policies are actually optimal in the whole class of insensitive policies, for the whole range of load parameters, when classes 1 and 3 have the same mean service requirement. (Note that our results of Section 5 allow to efficiently compute the performance of these decentralized policies.) This example gives hope that the optimality of decentralized policies holds more generally under certain, still unknown, conditions.

Conclusion

We give efficient recursive formulas to evaluate rectangular policies in the general case. This enables us to obtain computable bounds for the performance of the optimal insensitive policy.

We then give a precise characterization of the optimal insensitive policies for networks with admission control. To find conditions ensuring the optimality of decentralized policies is still a challenging open question for general network topologies. Another important remaining issue is to determine whether the performance of the best insensitive policy is close to the one of the best policy.

Figure 1 :

 1 Figure 1: Coordinate-convex policy (left) and decentralized policies (middle and right)

Figure 2 :

 2 Figure 2: Network of example 1 : the admission constraints are x 1 ≤ N , x 2 ≤ N

Figure 3 :Example 3 .

 33 Figure 3: Network of example 3 : the admission constraints are x 1 ≤ N, x 2 ≤ N

Figure 4 :Example 4 .

 44 Figure 4: Network of example 4 : the admission constraints are x 1 ≤ N , x 2 + x 3 ≤ N

Definition 4 . 1 .

 41 Consider a Ferrers set C ∈ F(X ). The coordinate-convex balance function associated with C is defined by, ΛC (x) = Λd (x)1 {x∈C} .

Proposition 4 . 4 .

 44 As in Section 3, for a Ferrers set C, define C(C) = z∈C ΛC (z)Φ(z), P j (C) = z∈C ΛC (z + e j )Φ(z) . Consider a Ferrers set C ∈ F(X ) and the corresponding coordinate-convex policy. The blocking probability B p (Λ C ) satisfies

Figure 5 :

 5 Figure 5: Insensitive policies and sensitive policies

Figure 6 :

 6 Figure 6: Rectangular (not necessarily admissible) policies

Figure 7 :

 7 Figure 7: Blocking probabilities of the coordinate-convex policies

Scenario

Figure 8 :

 8 Figure 8: Blocking probabilities (log scale) for scenarios 1 (left) and 2 (right)

Figure 9 :

 9 Figure 9: Blocking probabilities (log scale) for scenarios 3 (left) and 4 (right)

  |K| (each class is assigned to a specific node). In that case, such policies are sometimes called threshold policies in the literature, with the point y determining the threshold. We elaborate further on this case in Section 4.

	QUES9185_source.tex; 7/07/2010; 12:16					p. 12
	2. When |I| = Let us illustrate the above on a few examples.
	Example 2. Consider the same model as in Example 1. Consider the point y = (n, n) with
	n < N. The decentralized balance function associated with this point is:
		2 n • • •	8	4	2	1
		. . .	1 6	8	4	2
	Λy :	. . . . . .	3 2 1 6 6 4 3 2 1 6 8 8 4
		. . .				. . .

Table 1 :

 1 Parameters of the 4 scenarios

		a	b c/a λ 2
	1	2 2	2	1
	2	0.3 2	2	1
	3	2 6	2	1
	4	2 6	1	1

QUES9185_source.tex; 7/07/2010; 12:16 p. 3

QUES9185_source.tex; 7/07/2010; 12:16 p. 6

QUES9185_source.tex; 7/07/2010; 12:16 p. 8

QUES9185_source.tex; 7/07/2010; 12:16 p. 9

QUES9185_source.tex; 7/07/2010; 12:16 p. 10

QUES9185_source.tex; 7/07/2010; 12:16 p.[START_REF] Ross | Multiservice Loss Models for Broadband Telecommunication Networks[END_REF]

QUES9185_source.tex; 7/07/2010; 12:16 p.[START_REF] Whittle | Systems in stochastic equilibrium[END_REF]

QUES9185_source.tex; 7/07/2010; 12:16 p. 16

QUES9185_source.tex; 7/07/2010; 12:16 p. 20

QUES9185_source.tex; 7/07/2010; 12:16 p. 21


Stefania Costache

Nikos Parlavantzas

Christine Morin

Samuel Kortas

Themis: A Spot-Market Based Automatic Resource Scaling Framework

Cloud computing brings new provisioning models that offer applications more flexibility and better control over their resource allocations. However these models suffer from the following problem: either they provide limited support for applications demanding quality of service, or they lead to a limited infrastructure utilization. In this paper we propose Themis, a novel resource management system for virtualized infrastructures based on a virtual economy. By limiting the coupling between the applications and the infrastructure through the use of a dynamic resource pricing mechanism, Themis can support diverse types of applications and performance goals while ensuring an efficient resource usage.

MOTIVATION

High Performance Computing (HPC) infrastructures are used to execute increasingly complex and dynamic applications. Given the workload dynamicity and heterogeneity, a general concern in managing these infrastructures is ensuring the best application performance and resource utilization. Cloud providers partially address this concern by offering users "instant" access to virtualized resources [1], and thus, allowing them to meet their SLOs more effectively. However, to maintain this "instant provisioning" illusion a cloud provider needs to keep a large amount of idle resources.

An approach that overcomes this limitation is to automatically allocate resources to applications through a spot market. In this approach users submit bids for resources and their allocations and the resource price vary with the total user demand. This mechanism allows users with valuable requests to receive resources instantly while users with less valuable requests can benefit more from resources in low utilization periods. When applying this approach in managing * The author is currently a PhD student at INRIA and EDF R &D. This work is supported by ANRT through the CIFRE sponsorship No. 0332/2010 virtualized HPC infrastructures, two challenges need to be addressed: (i) how to implement a spot market mechanism in an efficient way to provide maximum resource utilization and fairness to users; (ii) how to provide support to applications to meet their SLOs.

THEMIS

We have developed Themis, a spot-market based resource allocation system. The contribution that Themis brings is a decentralized resource control system that uses dynamic pricing as a user demand regulating mechanism. Our system relies on the use of a virtual economy and is composed of: (i) independent application controllers that use feedback-loops to dynamically provision resources for applications and meet their SLOs; (ii) a market-based proportional-share scheduler to control the resource allocation; (iii) a virtual bank to manage the system's total currency. Figure 1 describes our system's components and the communication between them. We detail these components next.

Application Controllers: Themis' application controllers use feedback loops based on generic adaptation policies to change the resource allocation given the current spot price, users valuation for applications and their specified SLOs. An application controller uses plugins that monitor, parse application performance information and adapt incrementally the number of virtual machines and submitted bid. Users can replace these plugins with their own, to build controllers specific to their application types. To provide support for building specific feedback loops, we provide two generic adaptation policies that change the virtual machine bid and the number of virtual machines. To execute their applications on the infrastructure, users start an application controller with an XML application configuration file. The application configuration contains: (i) deployment information: a template used to specify any cloud-manager required virtual machine configuration; files to be transferred to virtual machines; required scripts to be executed to start and stop application components; (iii) budgeting information (i.e., an initial credit amount and the rate at which it is renewed); (iv) adaptation policy information (i.e., policy type to be used, specific thresholds). Based on this information the application controller provisions an initial number of virtual machines and starts the application.

Market-based Scheduler:

The market-based proportionalshare scheduler ensures maximum resource utilization through its work-conserving nature and fine-grained resource control. The scheduler allocates fractional amounts of CPU resource to virtual machine instances proportional to the virtual machine bid and inversely proportional to the current resource price. Previous work has shown that this mechanism can provide a good efficiency even when users anticipate the effect of changing their bids on the resource price [START_REF] Feldman | The proportional-share allocation market for computational resources[END_REF]. To ensure the work-conserving property of the proportional-share policy (i.e., any available resource amount is distributed between the virtual machines), and that each virtual machine receives a share as close as possible to the one that it deserves, the scheduler also performs load-balancing between hosts. The load-balancing algorithm uses a tabusearch heuristic that keeps the number of virtual machine migrations below an administrator-defined limit.

Cloud Manager: We built our system on top of the Open-Nebula cloud manager [START_REF] Sotomayor | An Open Source Solution for Virtual Infrastructure Management in Private and Hybrid Clouds[END_REF]. The components of Themis interact with OpenNebula through its provided XML-RPC API to : (i) perform virtual machine operations (e.g., deploy, migrate, terminate); (ii) retreive monitoring information about physical nodes and virtual machines; (iii) retreive user accounts information and authenticate the users in the system to allow them to submit their applications. As OpenNebula does not support virtual machine dynamic resizing, the scheduler enforces its computed CPU allocations by communicating with the node hypervisors (i.e., Xen).

Virtual Bank: A virtual bank manages the system's total currency. Users are funded with an amount of virtual currency periodically recharged, based on the amount that was spent. Currently, to avoid hoarding of credits and budget depletion, a simple policy is implemented: when an application is submitted, the virtual bank creates an account for it and transfers from the user's account an initial amount of credits, replenished periodically at a user-specified rate.

VALIDATION

We have previously simulated the architecture of Themis using CloudSim toolkit [START_REF] Calheiros | Cloudsim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms[END_REF] and tested simple scaling policies for two types of applications, namely rigid and elastic [START_REF] Costache | An economic approach for application qos management in clouds[END_REF]. Currently we have implemented Themis in Python. The communication between its components is done through XML-RPC. All the information regarding application and user accounts is kept in a MySql database storage.

To show a real use-case of Themis, we have deployed it on 10 nodes from Grid'5000 [START_REF] Bolze | Grid'5000: A large scale and highly reconfigurable experimental grid testbed[END_REF] and developed an application controller that automatically scales a Condor [START_REF] Litzkow | Condor-a hunter of idle workstations[END_REF] managed virtual cluster using feedback regarding the resource price and the number of pending jobs. To change the number of virtual machines we have used a simple adaptation policy: (i) the number increases when the number of jobs in Condor's queue is higher than a given threshold; (ii) the number decreases when there are fewer jobs in queue or the resource price is too high. We submitted two batches of jobs. During the first submission the infrastructure was underutilized and the Themis controller increased the number of virtual machines, leading to a maximum resource utilization and jobprocessing throughput. During the second submission the infrastructure was highly used and the Themis controller could not scale the number of virtual machines due to its budget limitation and the high resource price.

CONCLUSIONS

We have presented an automatic resource management framework based on a spot market. With Themis the resource control is decentralized, allowing each application to apply its own adaptation policies while the resource management is kept generic and simple.

We currently plan to measure the impact of the resource control decentralization and virtual machine operations. We will extend our system in two directions: (i) define controller policies for different application types; (ii) extend the scheduling algorithm to support allocation of multiple types of resources. Regarding the controller policies, we plan to take scaling decisions based on an application reconfiguration cost and future price predictions. Regarding the scheduling algorithm we plan to investigate how application preferences for multiple resources can be considered in the design of a fair efficient allocation policy.

Figure 1 :

 1 Figure 1: System overview.


est destinée au dépôt

GRACE mass balance estimates for all the Earth's ice-covered regions

Thomas Jacob, J. Wahr, T. W. Pfeffer, S. Swenson

To cite this version:

Thomas Jacob, J. Wahr, T. W. Pfeffer, S. Swenson. GRACE mass balance estimates for all the Earth's ice-covered regions. Grace Science team meeting 2012, Sep 2012, Potsdam, Germany. hal-00721697

We have used GRACE satellite gravity measurements to construct 2003-2010 mass loss estimates for all the world's mountain glacier systems and ice caps (GIC's), as well as for Greenland and Antarctica. We find that the GIC's, excluding the Greenland and Antarctic peripheral glaciers and ice caps (PGIC's), lost mass at a rate of 148 ± 30 Gt yr-1 from January 2003 to December 2010, contributing 0.41 ± 0.08 mm yr-1 to global sea level rise (SLR) during this period. This rate is about 30% smaller than previously published ground-based estimates that most nearly matched this time span. Our results for the high mountains of Asia, in particular, show a mass loss of only 4 20 Gt yr-1, compared to 47-55 Gt yr-1 in previously published estimates.

We also estimate that the Greenland and Antarctic ice sheets, including their PGIC's, lost 384 ±71 Gt yr-1, contributing 1.06 ± 0.19 mm yr-1 to SLR, over this same time period. The total SLR contribution from all ice-covered regions was then 1.48 ± 0.26 mm yr-1, agreeing with independent estimates of SLR from new water to within the respective error bars.