Thomas Bonald

Céline Comte

Virag Shah

Gustavo De Veciana

Poly-Symmetry in Processor-Sharing Systems *

Keywords: Processor-sharing queueing systems, performance, balanced fairness, poly-symmetry

We consider a system of processor-sharing queues with state-dependent service rates. These are allocated according to balanced fairness within a polymatroid capacity set. Balanced fairness is known to be both insensitive and Pareto-efficient in such systems, which ensures that the performance metrics, when computable, will provide robust insights into the real performance of the system considered. We first show that these performance metrics can be evaluated with a complexity that is polynomial in the system size if the system is partitioned into a finite number of parts, so that queues are exchangeable within each part and asymmetric across different parts. This in turn allows us to derive stochastic bounds for a larger class of systems which satisfy less restrictive symmetry assumptions. These results are applied to practical examples of tree data networks, such as backhaul networks of Internet service providers, and computer clusters.

Introduction

Systems of processor-sharing queues with state-dependent service rates have been extensively used to model a large variety of real communication and computation systems like content delivery systems [START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF][START_REF] Shah | Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems[END_REF], computer clusters [START_REF] Bonald | Balanced fair resource sharing in computer clusters[END_REF][START_REF] Gardner | The power of d choices for redundancy[END_REF] and data networks [START_REF] Veciana | Stability and performance analysis of networks supporting elastic services[END_REF][START_REF] Massoulié | Bandwidth sharing and admission control for elastic traffic[END_REF]. They are natural models for such real systems as they capture the complex interactions between different jobs and also have a promise of analytical tractability of user performance when subject to stochastic loads. Indeed, in the past two decades researchers have been able to obtain explicit performance expressions and bounds for several such systems, see [START_REF] Bonald | On performance bounds for balanced fairness[END_REF][START_REF] Bonald | On stochastic bounds for monotonic processor sharing networks[END_REF][START_REF] Bonald | Calculating the flow level performance of balanced fairness in tree networks[END_REF][START_REF] Bonald | A recursive formula for multirate systems with elastic traffic[END_REF][START_REF] Joseph | Stochastic networks with multipath flow control: Impact of resource pools on flow-level performance and network congestion[END_REF][START_REF] Kelly | Resource pooling in congested networks: proportional fairness and product form[END_REF][START_REF] Massoulié | Bandwidth sharing and admission control for elastic traffic[END_REF][START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF][START_REF] Shah | Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems[END_REF].

However, few performance results scale well with the system size. Those that do rely on restrictive assumptions related to the topology or the symmetry of the system [START_REF] Massoulié | Bandwidth sharing and admission control for elastic traffic[END_REF][START_REF] Shah | Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems[END_REF]. One of the main goals of this paper is to provide scalable performance results for a class of processor-sharing systems which find applications in bandwidth-sharing networks and computer clusters.

One of the key features of processor-sharing systems is the allocation of the service rates per queue in each state. A particular class of resource allocations which is more tractable for performance analysis is characterized by the balance property which constrains the relative gain in the service rate at one queue when we remove a job from another queue. Processor-sharing systems where the resource allocation satisfies this property are called Whittle networks [START_REF] Serfozo | Introduction to Stochastic Networks[END_REF]. In particular, if the service rates are constrained by some capacity set, corresponding to the resources of the real system considered, then there exists a unique policy which satisfies the balance property while being efficient, namely balanced fairness [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF]. In this paper we focus on systems which are constrained by a polymatroid capacity set [START_REF] Fujishige | Submodular functions and optimization[END_REF][START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF] and operate under balanced fair resource allocation.

It was proved in [START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF] that balanced fairness is Pareto-efficient when it is applied in polymatroid capacity sets, which in practice yields explicit recursion formulas for the performance metrics. However, if no further assumptions are made on the structure of the system, the time complexity to compute these metrics is exponential with the number of queues. It was proved in [START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF] that it can be made linear at the cost of strict assumptions on the overall symmetry of the capacity set and the traffic intensity at each queue. Under symmetry in interaction across queues, it was shown in [START_REF] Shah | Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems[END_REF] that the performance is robust to heterogeneity in loads and system configuration under an appropriate scaling regime. However, there is little understanding of performance for scenarios where queues themselves interact in heterogeneous fashion.

In this paper, we consider a scenario where the processor-sharing system is partitioned into a finite number of parts, so that queues are exchangeable within each part and asymmetric across different parts. For such systems, that we call poly-symmetric, we obtain a performance expression with computational complexity which is polynomial in the number of queues. We demonstrate the usefulness of these bounds by applying them to tree data networks, which are representative of backhaul networks, and to randomly configured heterogeneous computer clusters. In addition, we provide a monotonicity bound which allows us to bound performance of systems with capacity regions which are 'nearly' poly-symmetric.

The paper is organized as follows. Section 2 introduces the model and shows that it applies to real systems as varied as tree data networks and computer clusters. We also recall known facts about balanced fairness. In Section 3, we introduce the notion of poly-symmetry and show that it yields explicit recursion formulas for the performance metrics which have a complexity that is polynomial in the number of queues in the processor-sharing system. Finally, Section 4 gives stochastic bounds to compare the performance of different systems. We conclude in Section 5.

2 System model 2.1 Processor-sharing queueing system with a polymatroid capacity set We consider a system of n processor-sharing queues with coupled service rates and we denote by I = {1, . . . , n} the set of queue indices. For each i ∈ I, jobs enter the system at queue i according to some Poisson process with intensity λ i and have i.i.d. exponential service requirements with mean σ i , resulting in a traffic intensity ρ i = λ i σ i at queue i. Jobs leave the system immediately after service completion. Such a queueing system will be called a processor-sharing system throughout the paper.

The system state is described by the vector x = (x i : i ∈ I), where x i is the number of jobs at queue i for each i ∈ I. For each x ∈ N n , I(x) = {i ∈ I : x i > 0} denotes the set of active queues in state x. Queues have state-dependent service rates. For each x ∈ N n , φ(x) = (φ i (x) : i ∈ I) denotes the vector of service rates per queue when the system is in state x.

The system is characterized by a capacity set, which is defined as the set of all feasible resource allocations φ = (φ i : i ∈ I) ∈ R n + . This capacity set may be specified by practical constraints like the capacities of the links in a data network or the service rates of the servers in a computer cluster. We are interested in queueing systems whose capacity set is a particular type of polytope called a polymatroid [START_REF] Fujishige | Submodular functions and optimization[END_REF].

Definition 1. A polytope C in R n
+ is a polymatroid if there exists a non-negative function µ defined on the power set of I such that

C = φ ∈ R n + : i∈A φ i ≤ µ(A), ∀A ⊂ I
and µ satisfies the following properties: Before we specify the resource allocation, we give two examples of real systems that fit into this model.

Normalization: µ(∅) = 0, Monotonicity: for all A, B ⊂ I, if A ⊂ B, then µ(A) ≤ µ(B), Submodularity: for all A, B ⊂ I, µ(A) + µ(B) ≥ µ(A ∪ B) + µ(A ∩ B).
φ 2 (x) ρ 1 = λ 1 σ 1 ρ 2 = λ 2 σ 2 (c) Equivalent processor-sharing system φ 1 φ 2 (d) Capacity set

Tree data networks

The first example is a data network with a tree topology [START_REF] Bonald | Calculating the flow level performance of balanced fairness in tree networks[END_REF], representative of backhaul networks of Internet service providers. There are n users that can generate flows in parallel and we denote by I = {1, . . . , n} the set of user indices. For any i ∈ I, user i generates data flows according to some Poisson process with intensity λ i that is independent of the other users. All flows generated by user i follow the same route in the network and have i.i.d. exponentially distributed sizes with mean σ i in bits, resulting in a traffic intensity ρ i = λ i σ i in bit/s. The state of the network is described by the vector x = (x i : i ∈ I), where x i is the number of ongoing flows of user i, for each i ∈ I.

We make the following assumptions on the allocation of the resources. The capacity of each link can be divided continuously among the flows that cross it. Also, the resource allocation per flow only depends on the number of flows of each user in progress. In particular, all flows of a user receive the same capacity, so that the per-flow resource allocation is entirely defined in any state x ∈ N n by the total capacity φ i (x) allocated to flows of user i, for any i ∈ I.

Under these assumptions, we can represent the data network by a processor-sharing system with n queues, one per user. For each i ∈ I, the jobs at queue i in the equivalent processor-sharing system are the ongoing flows of user i in the data network, and the service rate of this queue in state x is the total capacity φ i (x) allocated to the flows of user i. We will now describe the corresponding capacity set.

Each link can be identified by the set of users that cross it. Specifically, we can describe the network by a family T of subsets of I, where a set L ⊂ I is in T if and only if there is a link crossed by the flows of all users i ∈ L. We assume that the network is a tree in the following way.

Definition 2. The network is called a tree if for all L, M ∈ T , L ∩ M = ∅ implies that L ⊂ M or M ⊂ L.
There is no loss of generality in assuming that I ∈ T , for if not, the network is a forest where each subtree can be considered independently. For each L ∈ T , we denote by C L the capacity in bit/s of link L. We assume that all links are constraining since otherwise we can simply ignore the non-constraining ones. The resource allocation must then satisfy the capacity constraints

i∈L φ i (x) ≤ C L , ∀L ∈ T , ∀x ∈ N n , (1)
so that the capacity set is given by

C = φ ∈ R n + : i∈L φ i ≤ C L , ∀L ∈ T .
Example 1. Figures 1a, 1c and 1d give the example of a tree data network with 2 users. The routes of the users are given in Figure 1a. The flows of each user cross one link that is individual and another that is shared by both users. The representation of this data network as a processor-sharing system is given in Figure 1c and the corresponding capacity set is given in Figure 1d. It is easy to see that it is a polymatroid for any value of the link capacities.

The following theorem generalizes this last remark to any tree data network.

Theorem 1. The capacity set of a tree data network is a polymatroid with rank function µ defined by

µ(A) = min L∈Σ C L : Σ ⊂ T is a family of disjoints sets s.t. A ⊂ L∈Σ L
for all non-empty set A ⊂ I. In addition, we have µ(L) = C L for each L ∈ T .

Proof. We can certainly assume that T contains all the singletons since letting C {i} = min L⊂T ,i∈L C L for each i ∈ I does not modify the capacity set C. We can easily see that the result remains true if we do not make this assumption. We apply the following lemma which is a direct consequence of Theorems 2.5 and 2.6 of [START_REF] Fujishige | Submodular functions and optimization[END_REF] about intersecting-submodular functions on intersecting families of subsets.

Lemma 1. Let T be a family of subsets of I and g : T → R such that, for all L, M ∈ T with L ∩ M = ∅, we have L ∩ M ∈ T , L ∪ M ∈ T and g(L) + g(M ) ≥ g(L ∪ M ) + g(L ∩ M ). Further assume that ∅, I ∈ T , g(∅) = 0 and T contains all the singletons of I. Then the set of solutions in R n of the equations

i∈L φ i ≤ g(L), ∀L ∈ T , is given by φ ∈ R n : i∈A φ i ≤ f (A), ∀A ∈ I ,
where f is the real-valued, normalized, submodular function defined on the power set of I by

f (A) = min L∈Σ g(L) : Σ ⊂ T is a partition of A , ∀A ⊂ I.
The definition of a tree ensures that T ∪ {∅} satisfies the assumptions of the lemma, with the function g defined on T ∪ {∅} by g(L) = C L for any L ∈ T and g(∅) = 0. Hence, the set of solutions of the capacity constraints (1) in R n is

P = φ ∈ R n : i∈A φ i ≤ f (A), ∀A ⊂ I µ({1, 2}) = f ({1, 2}) f ({1}) µ({1}) = f ({1, 2}) P C φ 1 φ 2
Figure 2: Construction of the capacity set of a tree data network in R n + from the set of solutions of its capacity constraints in R n where f is the normalized, submodular function given by

f (A) = min L∈Σ C L : Σ ⊂ T is a partition of A , ∀A ⊂ I.
Note that no claim about the monotonicity of f can be made above because the points in P can have negative components. This is illustrated in Figure 2, where the intersection point of the sides of P corresponding to the sets {1} and {1, 2} has a negative ordinate because f ({1, 2}) < f ({1}).

Since the components of a vector of resource allocation are always positive, the capacity set C of the data network is given by C = P ∩ R n + . As we will see, since we restrict ourselves to points with positive components, the function µ which characterizes C is not only normalized and submodular like f but also non-decreasing. This is illustrated in Figure 2, which shows that we can replace f ({1}) by f ({1, 2}) to describe the side corresponding to the set {1} in C.

More formally, we prove that C is equal to the polymatroid C with rank function µ given by

µ(A) = min {f (B) : A ⊂ B ⊂ I} , ∀A ⊂ I.
One can check that this function µ coincides with the one given in the theorem statement. We first show that µ is indeed a rank function and then we prove that C is equal to C . The normalization of µ follows from that of f . Also µ is non-decreasing by construction. Finally, for each A, B ⊂ I, we have µ(A) + µ(B) = f (A ) + f (B ) for some A , B ⊂ I such that A ⊂ A and B ⊂ B , and also

f (A ) + f (B ) ≥ f (A ∪ B ) + f (A ∩ B ) ≥ µ(A ∪ B) + µ(A ∩ B),
where the first inequality holds by submodularity of f and the second by definition of µ, since A∪B ⊂ A ∪B and A ∩ B ⊂ A ∩ B . Hence µ is submodular.

We finally prove that C = C . It is clear that any vector in C is also in

C = P ∩ R n + since µ(A) ≤ f (A) for all A ⊂ I. Conversely, consider φ ∈ C. If φ is not in C ,
then there is A ⊂ I so that i∈A φ i > µ(A), which implies that µ(A) < f (A). By definition of µ, it follows that there is B ⊂ I so that A is a strict subset of B and f (B) = µ(A). But then

i∈B\A φ i = i∈B φ i - i∈A φ i < f (B) -µ(A) = 0,
so that at least one component of φ is negative. This is a contradiction. Example 2. Figure 3 gives the example of a tree data network with its capacity set. The routes of the users are given in Figure 3a. Each link is labeled with the set of user indices whose flows cross this link. The capacity constraints are

φ 1 ≤ C {1} , φ 2 ≤ C {2} , φ 3 ≤ C {3} , φ 1 + φ 2 ≤ C {1,2} , φ 1 + φ 2 + φ 3 ≤ C {1,2,3} .
The rank function µ of the capacity set is given by

µ({1}) = C {1} , µ({1, 2}) = C {1,2} , µ({1, 2, 3}) = C {1,2,3} . µ({2}) = C {2} , µ({1, 3}) = min C {1} + C {3} , C {1,2,3} , µ({3}) = C {3} , µ({2, 3}) = min C {2} + C {3} , C {1,2,3} ,

Computer clusters

We consider a cluster of m servers which can be pooled to process jobs in parallel. The set of servers is denoted by S = {1, . . . , m}. There are n classes of jobs and we denote by I = {1, . . . , n} the set of class indices. For any i ∈ I, class-i jobs enter the cluster as a Poisson process with intensity λ i and have i.i.d. exponential service requirements with mean σ i , resulting in a traffic intensity ρ i = λ i σ i for class i. Jobs leave the cluster immediately after service completion. The state of the cluster is described by the vector x = (x i : i ∈ I), where x i is the number of jobs of class i, for each i ∈ I.

The class of a job defines the set of servers that can process it. The server assignment is given by a family (S i : i ∈ I) of subsets of S, where S i denotes the set of servers that can serve class-i jobs, for each i ∈ I. Equivalently, the server assignment can be described by a bipartite graph

G = I, S, i∈S ({i} × S i )
called the assignment graph of the computer cluster. The service capacity of server s is µ s for each s = 1, . . . , m. For any set A ⊂ I of job classes, we let

µ(A) = s∈ i∈A Si µ s (2)
denote the aggregate capacity available for the classes in A.

We make the following assumptions on the allocation of the server capacities. Servers can be pooled to process jobs in parallel. When a job is in service on several servers, its service rate is the sum of the rates allocated by each server to this job. We also assume that the capacity of each server can be divided continuously among the jobs it can serve. Finally, the allocation of the service rates per job only depends on the number of jobs of each class in the cluster. In particular, all jobs of a class receive service at the same rate, so that the per-job resource allocation is entirely defined in any state x ∈ N n by the total capacity φ i (x) allocated to class-i jobs, for each i ∈ I.

Under these assumptions, we can describe the evolution of the cluster with a processor-sharing system with n queues, one per class. For each i ∈ I, queue i contains class-i jobs and its service rate in state x is the total capacity φ i (x) allocated to class-i jobs collectively. It was proved in [START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF] that the capacity set of such a cluster is a polymatroid and that the function µ defined by ( 2) is its rank function.

Example 3. Figure 1b gives the assignment graph for an example of a computer cluster, where job classes are on the left and servers are on the right. Server 2 can serve both classes whereas servers 1 and 3 are specialized. The corresponding processor-sharing system with 2 queues is shown in Figure 1c and its capacity set, which is a polymatroid in R 2 + , is depicted Figure 1d. The vertical and horizontal sides correspond to the individual constraints of classes 1 and 2, with µ({1}) = µ 1 + µ 2 and µ({2}) = µ 2 + µ 3 . The diagonal side corresponds to the joint constraint on classes 1 and 2, with µ({1, 2}) = µ 1 + µ 2 + µ 3 .

Balanced fairness

The service rates are allocated by applying balanced fairness [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF] in the polymatroid capacity set C introduced in Section 2.1.

For each i ∈ I, let e i denote the n-dimensional vector with 1 in position i and 0 elsewhere. Balanced fairness is defined as the only resource allocation that both satisfies the balance property

φ i (x)φ j (x -e i ) = φ i (x -e j )φ j (x), ∀x ∈ N n , ∀i, j ∈ I(x),
and maximizes the resource utilization in the following sense: in any state x ∈ N n , φ(x) ∈ C and there exists

A ⊂ I(x) such that i∈A φ i (x) = µ(A).
The balance property ensures that there exists a balance function Φ on N n such that Φ(0) = 1 and

φ i (x) = Φ(x -e i ) Φ(x) , ∀x ∈ N n \ {0}, ∀i ∈ I(x).
The second condition implies that Φ satisfies the recursion

Φ(x) = max A⊂I(x) i∈A Φ(x -e i ) µ(A) , ∀x ∈ N n \ {0}.
In [START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF] it is proved that balanced fairness is Pareto-efficient in polymatroid capacity sets, which means that this maximum is always achieved by the set I(x) = {i ∈ I : x i > 0} of active queues:

Φ(x) = i∈I(x) Φ(x -e i ) µ(I(x)) , ∀x ∈ N n \ {0}. (3)
Since the balance property is satisfied, the processor-sharing system defined in Section 2.1 is a Whittle network [START_REF] Serfozo | Introduction to Stochastic Networks[END_REF]. A stationary measure of the system state X = (X

i : i ∈ I) is π(x) = π(0)Φ(x)ρ x , ∀x ∈ N n ,
where we use the notation ρ x = i∈I ρ i xi for any x ∈ N n . Substituting (3) into this expression yields

π(x) = i∈I(x) ρ i π(x -e i ) µ(I(x)) , ∀x ∈ N n \ {0}.
It is proved in [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF] that the system is stable, in the sense that the underlying Markov process is ergodic, if and only if

i∈A ρ i < µ(A), ∀A ⊂ I,
which means that the vector of traffic intensities belongs to the interior of the capacity set. In the rest of the paper, we assume that this condition is satisfied and we denote by π the stationary distribution of the system state.

Performance metrics

By abuse of notation, for each A ⊂ I, we denote by π(A) the stationary probability that the set of active queues is A:

π(A) = P {I(X) = A} = x∈N n , I(x)=A π(x), ∀A ⊂ I.
For each i ∈ I, let L i = E[X i ] denote the mean number of jobs at queue i and, for each

A ⊂ I, let L i (A) = E [X i |I(X) = A]
denote the mean number of jobs at queue i given that the set of active queues is A. By the law of total expectation, we have

L i = A⊂I L i (A)π(A), ∀i ∈ I.
The following theorem gives a recursive formula for π(A) and L i (A) for any A ⊂ I and i ∈ I. It is a restatement of Theorem 4 in [START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF] using the same idea as Proposition 4 and Theorem 1 in [START_REF] Shah | Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems[END_REF].

Theorem 2. For each non-empty set A ⊂ I, we have

π(A) = i∈A ρ i π(A \ {i}) µ(A) -i∈A ρ i . ( 4
)
Let i ∈ I. For each set A ⊂ I, we have L i (A) = 0 if i / ∈ A, and otherwise

π(A)L i (A) = ρ i π(A \ {i}) + ρ i π(A) + j∈A\{i} ρ j π(A \ {j})L i (A \ {j}) µ(A) -j∈A ρ j . (5)
Observe that (4) allows one to evaluate recursively π(A)/π(∅) for each A ⊂ I, from which π(∅) can be computed. Similarly, for each i ∈ I, (5) allows one to evaluate recursively π(A)L i (A)/π(∅) for each A ⊂ I and each i ∈ I, from which the value of L i can be deduced. One could then compute performance metrics like the mean delay or the mean service rate per queue from L i by applying Little's law. Note that the complexity is exponential in the number of queues.

3 Poly-symmetry

Definition

The exponential complexity of the formulas of Theorem 2 makes it impractical when we want to predict the performance of large-scale systems. To cope with this, we introduce the notion of poly-symmetry, which allows us to obtain formulas with a complexity that is polynomial in the number of queues at the cost of some regularity assumptions on the capacity set and the traffic intensity at each queue. Poly-symmetry is a generalization of the notion of symmetry which was considered in [START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF][START_REF] Shah | Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems[END_REF].

The following definition will be used subsequently to introduce poly-symmetry. It is easy to check that it defines an equivalence relation on the set I of indices. Let C be a polymatroid on R n + and denote its rank function by µ. Let i, j ∈ I with i = j. We say that indices i and j are exchangeable in C if

µ(A ∪ {i}) = µ(A ∪ {j}), ∀A ⊂ I \ {i, j}.
As the name suggests, two indices are exchangeable if and only if exchanging these indices does not modify the capacity set. Note that the exchangeability of two indices i and j implies that they have the same individual constraints µ({i}) = µ({j}). The reverse implication is not true when n > 2, as we will see in the following example.

Example 4. Consider the computer cluster with the assignment graph depicted in Figure 4a, where all servers have the same unit capacity. The corresponding polymatroid capacity set is illustrated in Figure 4b. We have µ({1}) = µ({3}) = 2 and µ({1, 2}) = µ({2, 3}) = 3, so that indices 1 and 3 are exchangeable. Index 2 is not exchangeable with any of the two other indices because µ({1, 2}) = µ({2, 3}) = 3 while µ({1, 3}) = 4.

Let us now define poly-symmetry. Suppose K ≥ 1 and consider a partition Σ = (I k : k = 1, . . . , K) of I in K parts. We now give an alternative definition of poly-symmetry which is equivalent to Definition 4. It is a generalization of the definition of symmetry given in [START_REF] Shah | High-performance centralized content delivery infrastructure: Models and asymptotics[END_REF][START_REF] Shah | Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems[END_REF]. We will use it to express and prove Theorem 3. Example 5. Consider the computer cluster with the assignment graph depicted in Figure 5, where all servers have the same unit capacity. The corresponding capacity set is illustrated in Figure 5b. It is poly-symmetric with respect to partition Σ = ({1, 3}, {2}) and the corresponding cardinality rank function h is given by h(0, 0) = 0, h(1, 0) = 2 and h(0, 1) = h(1, 1) = 3.

Performance metrics

Let Σ = (I k : k = 1, . . . , K) be a partition of I. We consider a processor-sharing system with a polymatroid capacity set which is poly-symmetric with respect to Σ. For each A ⊂ I, the vector |A| Σ = (|A ∩ I k | : k = 1, . . . , K) gives the number of active queues in each part of the partition when the set of active queues is A. By abuse of notation, for each k = 1, . . . , K, we denote by e k the vector of N K with 1 in component k and 0 elsewhere.

As in Section 2.4, the resources are allocated by applying balanced fairness in this capacity set under some vector of traffic intensity ρ which satisfies the stability constraints. For simplicity of notation, for each a ∈ N , we denote by π(a) the probability that the number of active queues in part k is a k for each k = 1, . . . , K:

π(a) = P{|I(X)| Σ = a} = A⊂I, |A|Σ=a π(A).
For each k = 1, . . . , K, let L k = E i∈I k X i denote the mean number of jobs in the queues of part k and, for each a ∈ N , let L k (a) = E i∈I k X i ||I(X)| Σ = a denote the mean number of jobs in the queues of part k given that there are a l active queues in part l for each l = 1, . . . , K. The regularity assumptions ensure that, for each k = 1, . . . , K, 1 n k L k and 1 n k L k (a) for each a ∈ N also give the mean numbers of jobs at queue i for any i ∈ I k . By the law of total expectation, we have

L k = a∈N L k (a)π(a), ∀k = 1, . . . , K.
The following theorem gives a recursive formula for π(a) and L k (a) that allows one to compute recursively these quantities with a complexity O(n 1 • • • n K ). The proof is given in Appendix A.

Theorem 3. Consider a system of n processor-sharing queues with state-dependent service rates allocated according to balanced fairness in a polymatroid capacity set C. Assume that C is poly-symmetric with respect to partition Σ and denote by h the corresponding cardinality rank function. Further assume that for each k = 1, . . . , K, all queues of I k receive jobs with the same traffic intensity k , i.e. ρ i = k for all i ∈ I k . For each a ∈ N \ {0}, we have

π(a) = K k=1 (n k -a k + 1) k π(a -e k ) h(a) - K k=1 a k k . ( 6
)
Let k = 1, . . . , K. For each a ∈ N , we have L k (a) = 0 if a k = 0, and otherwise

π(a)L k (a) = a k k π(a) + (n k -a k + 1) k π(a -e k ) + K l=1 (n l -a l + 1) l π(a -e l )L k (a -e l ) h(a) - K l=1 a l l . ( 7
)
This result applies to Example 5 with the partition Σ = ({1, 3}, {2}) when classes 1 and 3 have the same traffic intensity. The set of suitable vectors of traffic intensities is depicted as the darkly shaded region in Figure 5b.

In this theorem, we have assumed that the cardinality rank function h was given. Given a real system like those of Sections 2.2 and 2.3 which is known to be poly-symmetric with regard to some partition Σ = (I k : k = 1, . . . , K), one could ask if it is also possible to build h with a complexity O(n 1 • • • n K ). This is straightforward for a computer cluster. Concerning the tree data networks, we can actually apply a method similar to that of the proof of Theorem 1. Specifically, we first define recursively a concave function We will now see two examples of real systems where this result applies.

f on N by f (0) = 0, f (a) = C L if there is L ∈ T so that |L| Σ = a,

Application to tree data networks

We consider the simple example of a tree data network where each user has an individual access line and all users share an aggregation link which has a capacity C in bit/s. The user access lines can have K different capacities r 1 , . . . , r K in bit/s. This corresponds to the model introduced in [START_REF] Bonald | The multi-source model for dimensioning data networks[END_REF] to predict some performance metrics in Internet service provider access networks, where the individual access lines represent subscriber lines which are connected to the aggregation link by the digital subscriber line access multiplexer (DSLAM). 6 gives a toy example with K = 2 possible access rates r 1 and r 2 . There are three users with access rate r 1 and two users with access rate r 2 . All users are constrained by the aggregation link with capacity C.

Access lines with capacity r 1

Access lines with capacity r 2

Aggregation link with capacity C

For each k = 1, . . . , K we denote by I k the set of users with access rate r k . These form a partition of the set I = K k=1 I k of users. Theorem 1 ensures that the capacity set of this data network is a polymatroid with rank function µ given by

µ(A) = min K k=1 |A ∩ I k |r k , C , ∀A ⊂ I. (8)
It is poly-symmetric with respect to partition Σ = (I k : k = 1, . . . , K). The corresponding cardinality rank function h is given by

h(a) = min K k=1 a k r k , C , ∀a ∈ N .
We further assume that for each k = 1, . . . , K, all users with access line r k have the same traffic intensity k < r k . Then the network is stable whenever K k=1 n k k < C, and it meets the conditions of Theorem 3. A metric of interest is the mean throughput per user. For each i ∈ I, we denote by P i and E i the conditional probability measure and expectation given that user i is active, corresponding to the stationary distribution π i (x) ∝ 1 xi>0 π(x). For each k = 1, . . . , K and each i ∈ I k , the mean throughput perceived by user i is then given by

E i [φ i (X)] = E[φ i (X)] P{X i > 0} = k P{X i > 0} ,
where the second equality holds by the conservation equation k = E[φ i (X)] for all i ∈ I k . Using the notations of Section 3.2, the mean throughput of the users with access rate r k is given by

γ k = k 1 - a∈N :a k <n k n k -1 a k l =k n l a l π(a)
.

where π(a) for each a ∈ N can be computed with a complexity O(n 1 • • • n K ) by [START_REF] Bonald | Calculating the flow level performance of balanced fairness in tree networks[END_REF]. Other performance metrics such as the mean congestion rate per user can be computed similarly. Any class of I 1 shares exactly one server with any class of I 2 , and this server is dedicated to these two classes. The rank function of this cluster is thus given by

Application to computer clusters

µ(A) = |A ∩ I 1 |d 1 + |A ∩ I 2 |d 2 -|A ∩ I 1 | × |A ∩ I 2 |, ∀A ⊂ I.
The polymatroid capacity set defined by this rank function is poly-symmetric with respect to partition Σ = (I 1 , I 2 ) and the corresponding cardinality rank function is given by

h(a) = a 1 d 1 + a 2 d 2 -a 1 a 2 , ∀a ∈ N .
For each k = 1, 2, assume that all classes in I k have the same traffic intensity k . Further assume that the vector of traffic intensities = ( 1 , 2 ) stabilizes the system, that is

a 1 1 + a 2 2 < a 1 d 1 + a 2 d 2 -a 1 a 2 , ∀a ∈ N .
We can then apply Theorem 3 with partition Σ to compute the mean number of jobs of each class with a complexity O(n 1 n 2 ). We deduce the mean delay δ i of class-i jobs for each i ∈ I by Little's law:

δ i = L k n k λ i , ∀k = 1, 2, ∀i ∈ I k .
4 Stochastic Bounds Theorem 4. Let 0 < < 1. Consider two polymatroids Ĉ and C in R n + such that Ĉ is a subset of (1 + )C and a superset of (1 -)C. Let ρ be an element in the interior of (1 -)C and denote respectively by π, π + and π -the steady state distributions of the processor-sharing systems with capacity sets Ĉ, (1 + )C and (1 -)C under traffic intensity ρ. Then

π -(0) π + (0) π + (x) ≤ π(x) ≤ π + (0) π -(0) π -(x), ∀x ∈ N n .
Specifically, for each i ∈ I, we have

π -(0) π + (0) L i,+ ≤ L i ≤ π + (0) π -(0) L i,-,
where L i , L i,+ and L i,-are the mean number of job at queue i under distributions π, π + and π -respectively.

Proof. Denote by μ and µ the rank functions of Ĉ and C respectively. Let Φ, Φ + and Φ -denote the balance functions of the resource allocations defined by balanced fairness in the capacity sets Ĉ, (1 + )C and (1 -)C respectively. We first prove by induction on |x| that

Φ + (x) ≤ Φ(x) ≤ Φ -(x), ∀x ∈ N n .
The property holds for x = 0. Let x ∈ N n \ {0} and assume the inequality is valid for any y ∈ N n such that |y| < |x|. Then we have by (3):

Φ(x) = i∈I(x) Φ(x -e i ) μ(I(x)) ≤ i∈I(x) Φ -(x -e i ) μ(I(x)) ≤ i∈I(x) Φ -(x -e i ) ( 1
-)µ(I(x)) = Φ -(x)
where the first inequality holds by the induction assumption and the second holds by the inclusion of (1 -)C into Ĉ. We prove the other side of the inequality by using the inclusion of Ĉ into (1 + )C. This completes the proof by induction.

It follows that

1 π(0) = x∈N n Φ(x)ρ x ≥ x∈N n Φ + (x)ρ x = 1 π + (0)
.

Thus for each x ∈ N n , we obtain

π(x) = π(0)Φ(x)ρ x ≤ π(0)Φ -(x)ρ x ≤ π + (0)Φ -(x)ρ x = π + (0) π -(0) π -(x).
The proof for the other part of the inequality is similar. The second inequality about the mean number of jobs follows by summation.

The following sections illustrate how we can apply this result to the models of tree data networks and computer clusters.

Application to tree data networks

We first use this result to relax some assumptions of Section 3.3. The flows of each user go through an individual access line which is dedicated to this user and an aggregation link shared by all users. We still consider K groups I 1 , . . . , I K of users which form a partition of the set I. For each k = 1, . . . , K, the access rates of the users in I k may be different but we assume that they are all between (1-)r k and (1+ )r k for some > 0. Similarly, the capacity of the aggregation link is between (1 -)C and (1 + )C. The corresponding polymatroid capacity set Ĉ is not poly-symmetric with respect to partition Σ = (I k : k = 1, . . . , K) any more but its rank function μ satisfies:

(1 -)µ(A) ≤ μ(A) ≤ (1 + )µ(A), ∀A ⊂ I,
where µ is the rank function defined by [START_REF] Veciana | Stability and performance analysis of networks supporting elastic services[END_REF]. Denoting by C the polymatroid defined by µ, it follows that Ĉ is a superset of (1 -)C and a subset of (1 + )C. We can thus apply Theorem 4. In the special case where for each k = 1, . . . , K, all users of I k have the same traffic intensity k < (1 -)r k , with K k=1 n k k < (1 -)C, we can use Theorem 3 to compute the bounds.

Specifically, let π + and π -denote the steady state distributions of the processor-sharing systems with capacity sets (1 + )C and (1 -)C respectively under traffic intensity ρ. For each k = 1, . . . , K and each i ∈ I k , the mean throughput γ i of user i satisfies

π -(0) π + (0) γ k,-≤ γ i ≤ π + (0) π -(0) γ k,+ ,
where γ k,+ and γ k,-are the mean throughputs under distributions π + and π -respectively. We have

γ k,± = k 1 - a∈N :a k <n k n k -1 a k l =k n l a l π ± (a)
, ∀k = 1, . . . , K, and by ( 6)

π ± (a) = K k=1 (n k -a k + 1) k π ± (a -e k ) ( 1
± )h(a) - K k=1 a k k
, ∀a ∈ N \ {0}.

Application to computer cluster with random assignment

Random assignment. Consider a cluster as described in Section 2.3, where we denote by S = {1, . . . , m} the set of servers and by I the set of class indices. Let K ≥ 1 and consider for simplicity a partition Σ = (I 1 , . . . , I K ) of I into K parts of size n, so that the total number of job classes in the cluster is now given by Kn. We can easily generalize the result to K parts of different sizes. We use the same notation as in Sections 3.1 and 3.2: for each A ⊂ I, a = |A| Σ denotes the K-dimensional vector whose k-th component is a k = |A ∩ I k |, the size of the k-th part of A in partition Σ, for each k = 1, . . . , K; the set of these vectors is denoted by N = {0, 1, . . . , n} K . We now introduce a random assignment of the servers to the job classes, which is described by an assignment graph with random edges. Each realization of this random assignment defines a polymatroid capacity set as in Section 2.1. Hence, once this initial assignment is settled, we can apply balanced fairness over the associated capacity set as described in Section 2.4. Note that our assignment is static in the sense that the assignment graph does not change with time. For a given realization, we can thus observe the evolution of the cluster under stochastic arrivals and compute the resulting performance metrics as we did in Section 2.5.

The servers are randomly assigned to the job classes as follows. Let d = (d k : k = 1, . . . , K) be a vector of positive integers. For any k = 1, . . . , K and i ∈ I k , the set S i of servers that can process class-i jobs is chosen uniformly and independently at random among the subsets of S = {1, . . . , m} of cardinality d k . As in Section 2.3, the random assignment is described by the family (S i : i ∈ I) which defines a random bipartite graph

G = I, S, i∈I ({i} × S i )
with deterministic sets of vertices I and S and a random set of edges. Each realization (S i : i ∈ I) of the random assignment defines a polymatroid capacity set with a rank function given by ( 2). This allows us to define a random rank function associated with the random assignment by

M(A) = s∈S µ s 1 s∈ i∈A Si , ∀A ⊂ I.
Now let µ denote the corresponding mean rank function:

µ(A) = E[M(A)], ∀A ⊂ I.
The following lemma proves that the polymatroid defined by µ is poly-symmetric with respect to Σ.

p a = 1 - K k=1 1 - d k m a k .
Proof. Let a ∈ N and consider any set A ⊂ I with |A| Σ = a. We just need to observe that

µ(A) = s∈S µ s P s ∈ i∈A S i .
For each k = 1, . . . , K such that a k > 0, the probability that a server can not serve a specific class of

A ∩ I k is m-1 d k / m d k = 1 -d k m .
Since the assignments of the classes are independent, it follows that the probability that this server can serve at least one class in A is given by p a . Let ρ = (ρ i : i ∈ I) be a vector of traffic intensities. If G is a realization of the random assignment graph G such that ρ is in the interior of the polymatroid capacity set defined by G, then the corresponding processor-sharing system is stable under balanced fairness and we can study its steady-state behavior. We thus denote by X = (X i : i ∈ I) the random vector distributed according to the stationary distribution of the system state when ρ is in the interior of G, and for completeness we let X = 0 otherwise. For each realization G of the random assignment such that ρ is in the interior of the corresponding capacity set, we let

L i (G) = E [X i |G = G] , ∀i ∈ I,
which is simply the mean number of jobs of each class in the corresponding processor-sharing system under balanced fairness, as defined in Section 2.5. For each realization G which is not stabilized by ρ, we let

L i (G) = +∞.
Asymptotic poly-symmetry. We consider a sequence of computer clusters with random assignment as defined in the previous section. Let K ≥ 1 and b > 0.

For each n ≥ 1, the n-th random cluster of the sequence contains m (n) = bn servers and Kn job classes. We denote the set of servers by S (n) = {1, . . . , m (n) } and the set of job classes by I (n) = {1, . . . , Kn}. The service rate of server s is µ (n) s for each s ∈ S (n) . For simplicity, we consider a partition Σ (n) = (I

(n) k : k = 1, . . . , K) of I (n) into K parts of size n.
We can generalize the result to K parts of different sizes as long as the size of each part is linear in n. For each k = 1, . . . , K and i ∈ I

(n) k , the set S (n) i
of servers that can process class-i jobs is chosen uniformly and independently at random among the subsets of S (n) of cardinality d

(n) k .
Let G (n) denote the random graph defined by this random assignment, M (n) the corresponding random rank function and µ (n) its expectation.

By Lemma 2, for any n ≥ 1 and a ∈ N (n) = {0, . . . , n} K , we have

µ (n) (A) = E M (n) (A) = ξ (n) m (n) p (n) a with p (n) a = 1 - K k=1 1 - d (n) k m a k for all set A ⊂ I (n) with |A| Σ (n) = a, where ξ (n) = 1 m (n) s∈S (n) µ (n) s
is the mean server capacity. Theorem 5 below shows that, under the following two assumptions on the server capacities and the degrees of parallelism, the probability that the random rank function is uniformly close to its mean is 1 -o 1 n . The proof is given in Appendix B.

Assumption 1. For each n ≥ 1, S (n) is partitioned into a constant number of groups. Each group contains Ω(n) servers which have the same capacity. Assumption 2. For each k = 1, . . . , K, the sequence d

(n) k : n ≥ 1 satisfies d (n) k = ω(log n).
Theorem 5. Let 0 < < 1. Under Assumptions 1 and 2, there exists a sequence (g n : n ≥ 1) such that g n = ω(log n) and for any n ≥ 1,

P ∃A ⊂ I (n) s.t. M (n) (A) ≤ (1 -)µ (n) (A) ≤ e -gn and P ∃A ⊂ I (n) s.t. M (n) (A) ≥ (1 + )µ (n) (A) ≤ e -gn .
Corollary 1 follows from Theorem 5. For any n ≥ 1, let C (n) denote the polymatroid defined by the rank function µ (n) . C (n) is poly-symmetric with respect to the partition Σ (n) .

Corollary 1. Let 0 < < 1. Under Assumptions 1 and 2, the random capacity set resulting from the random assignment is a subset of (1 + )C (n) and a superset of (1 -)C (n) with probability 1 -o 1 n .

Performance metrics. For each n ≥ 1, we consider a vector (n) ∈ R K + of traffic intensities per part which stabilizes the processor-sharing system with n queues and capacity set (1 -)C (n) under balanced fairness, that is,

K k=1 a k (n) k < (1 -)h (n) (a), ∀a ∈ N (n) ,
where h (n) is the cardinality rank function of the mean capacity set with respect to partition Σ (n) :

h (n) (a) = ξ (n) m (n) p (n)
a , ∀a ∈ N (n) . Let X (n) denote the state in the n-th randomized computer cluster when we allocate the resources according to balanced fairness. Given a realization G (n) which is stabilized by (n) , the mean numbers of jobs per class are given by For each realization G (n) which is not stabilized by (n) , we let L i G (n) = +∞. This allows us to define the random variables

L i G (n) = E X (n) i G (n) = G (n) , ∀i ∈ I (n) .
L (n) i = L i G (n) , ∀i ∈ I.
Combining Theorems 4 and 5 yields the following result.

Theorem 6. Let 0 < < 1. For any n ≥ 1, denote by π

+ and π

-the stationary distributions of the processor-sharing systems with n queues and capacity sets (1 + )C (n) and (1 -)C (n) respectively, when the traffic intensity of the classes in

I (n) k is (n) k , for any k = 1, . . . , K. Let L (n) k,+ and L (n)
k,-denote the corresponding mean number of jobs per queue in part k, for each k = 1, . . . , K.

Under Assumptions 1 and 2, we have

P π (n) -(0) π (n) + (0) L (n) k,+ n ≤ L (n) i ≤ π (n) + (0) π (n) -(0) L (n) k,- n , ∀k = 1, . . . , K, ∀i ∈ I k = 1 -o 1 n .
For each n ≥ 1, Theorem 3 gives formulas to compute π (n)

± and L

(n) k,± for each k = 1, . . . , K with a complexity O n K . Using Little's law, we can deduce bounds on the mean delay per class.

Numerical application. We omit writing the exponents for brevity. Consider a randomized cluster with m = 10, 000 servers with unit capacity. The set of classes is partitioned into two parts I 1 and I 2 with n = 1, 000 classes each. The classes of I 1 have a degree d 1 = 20 and the ones of I 2 have a degree d 2 = 40. All jobs have a mean size 1 and the arrival rates are proportional to the degrees. The traffic intensity of any class in I 2 is thus twice that of any class in I 1 . Let ∈ R 2 + so that

1 = d 1 d 1 + d 2 h(n, n) n and 2 = d 2 d 1 + d 2 h(n, n) n ,
where h is the cardinality rank function of the mean capacity set with respect to partition Σ = (I 1 , I 2 ):

h(a) = m 1 -1 - d 1 m a1 1 - d 2 m a2 , ∀a ∈ {0, 1, . . . , n} 2 .
We can prove that the vector of traffic intensities ρ ∈ R 2n + with ρ i = 1 for all i ∈ I 1 and ρ i = 2 for all i ∈ I 2 is on the boundary of the mean capacity set.

Let 0 < < 1. For each α ∈ (0, 1 -), α stabilizes the processor-sharing systems with capacity sets (1 + )C and (1 -)C. The bounds on the mean delay that follow from Theorem 6 by applying Little's law are given by

1 + α π -(0) π + (0) L k,+ n k and 1 - α π + (0) π -(0) L k,- n k ,
where π ± (0) and L k,± are computed with the recursion expressions of Theorem 3 as follows. For each a ∈ {0, 1, . . . , n} 2 ,

π ± (a) = (n -a 1 + 1) 1 π ± (a -e 1 ) + (n -a 2 + 1) 2 π ± (a -e 2 ) 1± α h(a) -a 1 1 -a 2 2
.

For any k = 1, 2 and a ∈ N , we have L k,± (a) = 0 if a k = 0, and otherwise

π ± (a)L k,± (a) = 1 1± α h(a) -a 1 1 -a 2 2 a k k π ± (a) + (n -a k + 1) k π ± (a -e k ) + 2 l=1 (n -a l + 1) l π ± (a -e l )L k,± (a -e l ) .
Figure 8 gives the bounds obtained as a function of α ∈ (0, 1 -), for different values of . For simplicity, we draw the mean service rate per job, which is simply the inverse of the mean delay since all jobs have a unit mean size.

Conclusion

In this paper, we consider processor-sharing systems and introduce a poly-symmetry criterion on the structure of their capacity set which ensures that the performance metrics can be computed with a complexity which is polynomial in the number of queues if the traffic intensities per queue are adjusted accordingly. We showed that these formulas can also be used to bound the performance of a system when its capacity set is nearly poly-symmetric. We applied these results to tree data networks and computer clusters.

In future works, we would like to generalize the notion of poly-symmetry to relax some symmetry assumptions imposed in this paper while keeping a reasonable time complexity for the calculation of the performance metrics. We also believe there is further scope of enhancing the stochastic bounds by expanding their scope as well as obtaining tighter bounds in some specific scaling regimes.

For any k = 1, . . . , K and any i ∈ I k , we do the substitution

A⊂I,i∈A |A|Σ=a π(A \ {i}) = B⊂I\{i} |B|Σ=a-e k π(B),
and thus we obtain for any k = 1, . . . , K,

i∈I k A⊂I,i∈A |A|Σ=a π(A \ {i}) = B⊂I |B|Σ=a-e k i∈I k \(B∩I k ) π(B) = (n k -a k + 1)π(a -e k ). (9)
This proves [START_REF] Bonald | Calculating the flow level performance of balanced fairness in tree networks[END_REF].

A.2 Recursion (7)

Let k = 1, . . . , K and a ∈ N \ {0}. By definition of L k (a), we have

L k (a) = E i∈I k X i |I(X)| Σ = a = i∈I k E [X i ||I(X)| Σ = a] . It follows that π(a)L k (a) = i∈I k A⊂I,i∈A |A|Σ=a π(A)L i (A), (10)
and by ( 5), we obtain

π(a)L k (a) = i∈I k A⊂I,i∈A |A|Σ=a ρ i π(A \ {i}) + ρ i π(A) + j∈A\{i} ρ j π(A \ {j})L i (A \ {j}) µ(A) -j∈A ρ j .
Using the regularity assumptions, this can be rewritten as

h(a) - K l=1 a l l π(a)L k (a) = k i∈I k A⊂I,i∈A |A|Σ=a π(A \ {i}) + k i∈I k A⊂I,i∈A |A|Σ=a π(A) + i∈I k A⊂I,i∈A |A|Σ=a j∈A j =i ρ j π(A \ {j})L i (A \ {j}).
The first term is given by ( 9). The second term is simply

k i∈I k A⊂I,i∈A |A|Σ=a π(A) = k A⊂I |A|Σ=a i∈A∩I k π(A) = a k k π(a).
Finally, for any i ∈ I k , we have

A⊂I,i∈A |A|Σ=a j∈A j =i ρ j π(A \ {j})L i (A \ {j}) = K l=1 l j∈I l j =i A⊂I,i,j∈A |A|Σ=a π(A \ {j})L i (A \ {j}).
Doing the same substitution as in (9), we have for any l = 1, . . . , K,

j∈I l j =i A⊂I,i,j∈A |A|Σ=a π(A \ {j})L i (A \ {j}) = B⊂I,i∈B |B|Σ=a-e l j∈I l \(B∩I l ) π(B)L i (B), = (n l -a l + 1) B⊂I,i∈B |B|Σ=a-e l π(B)L i (B).
Hence the third term of the sum is equal to

i∈I k K l=1 (n l -a l + 1) l B⊂I,i∈B |B|Σ=a-e l π(B)L i (B) = K l=1 (n l -a l + 1) l i∈I k B⊂I,i∈B |B|Σ=a-e l π(B)L i (B), = K l=1 (n l -a l + 1) l π(a -e l )L k (a -e l ),
where the second equality holds by [START_REF] Fujishige | Submodular functions and optimization[END_REF]. When we substitute the three terms by their expressions, we obtain [START_REF] Bonald | A recursive formula for multirate systems with elastic traffic[END_REF].

B Proof of Theorem 5

We give the proof only for the case K = 2 for ease of notation; the other cases follow analogously. For now, we assume that for all n ≥ 1, all servers have the same capacity µ

(n) s = ξ (n)
for any s ∈ S (n) . Let 0 < < 1. We will show that there exists a sequence (g n : n ≥ 1) such that g n = ω(log n) and for any n ≥ 1,

P ∃A ⊂ I (n) s.t. M (n) (A) ≤ (1 -)µ (n) (A) ≤ e -gn .
Let us first give the main ideas of the proof. As in [START_REF] Shah | Impact of fairness and heterogeneity on delays in large-scale centralized content delivery systems[END_REF], it is divided in three steps. We first provide a bound for P M (n) (A) ≤ (1 -)µ (n) (A) for each A ⊂ I (n) for n large enough. Then, for each a ∈ N (n) = {0, 1, . . . , n} 2 , we use the union bound to obtain a uniform bound over all sets A ⊂ I (n) with |A| Σ (n) = a. Finally, another use of the union bound over all a ∈ N (n) gives us the result.

B.1 Partial bound

Let n ≥ 1, a ∈ N (n) and A ⊂ I (n) so that |A| Σ (n) = a. Recall that µ (n) (A) = E[M (n) (A)] with M (n) (A) = ξ (n) s∈S (n) 1 s∈ i∈A S (n) i . The variables 1 s∈ i∈A S (n) i for s ∈ S (n) are Bernoulli distributed with parameter p (n) a = 1 - K k=1 1 - d (n) k m (n) a k .
Dubbashi et al. proved in Theorem 10 of [START_REF] Dubhashi | Negative dependence through the FKG inequality[END_REF] that these random variables are negatively associated in the sense of Definition 3 of [START_REF] Dubhashi | Negative dependence through the FKG inequality[END_REF]. Their Theorem 14 then showed that the Chernoff-Hoeffding bounds (see for instance [START_REF] Motwani | Randomized Algorithms[END_REF][START_REF] Sinclair | Cs271 randomness & computation[END_REF]), which hold for independent random variables, can also be applied to these random variables. Hence we have so that

P M (n) (A) ≤ (1 -)µ (n) (A) ≤ e -2 2 m (n) p (n) a , (11)
P M (n) (A) ≤ (1 -)µ (n) (A) ≤ e -m (n) H[(1-)p (n) a ||p (n) a ] , (12)
δ 3 m (n) -a 1 d (n) 1 + a 2 d (n) 2 ≤ -2 a 1 d (n) 1 -a 2 d (n) 2 ≤ -2 a 1 d (n) 1 + a 2 d (n) 2
for large enough n. The same argument holds by inverting a 1 and a 2 when a 2 > n gn , so we conclude that there is a positive constant δ 4 such that for large enough n, we have (n) 2

P M (n) (A) ≤ (1 -)µ (n) (A) ≤ e -δ4 a1d
for some positive constant δ 5 < δ 4 .

B.2 Conclusion

Combining cases B.1.1 and B.1.2, we deduce that there exists a positive constant δ 6 such that

P ∃A ⊂ I (n) s.t. |A| Σ (n) = a and M (n) (A) ≤ (1 -)µ (n) (A) ≤ e -δ6gn , ∀a ∈ N (n)
when n is large enough. Using the union bound again, we obtain

P ∃A ⊂ I (n) s.t. M (n) (A) ≤ (1 -)µ (n) (A)
≤ n 2 e -δ6gn = e 2 log n e -δ6gn = e -gn(δ6-2 log n gn ) .

Since g n = ω(log n), we conclude that for a constant δ 7 < δ 6 , we have for large enough n

P ∃A ⊂ I (n) s.t. M (n) (A) ≤ (1 -)µ (n) (A) ≤ e -δ7gn .
Finally, when servers are in groups as in Assumption 1, we can break down M (n) into a sum of random rank functions, one for each groups. The result follows by showing the concentration in each group as above, and then using the union bound again. . For large enough n, we have p (n) a ≥ δ (a 1 + a 2 )g n n , ∀a = (a 1 , a 2 ) ∈ 0, 1, . . . , n g n 2 .

Proof. Consider the sequence (f n : n ≥ 1) of functions defined on R 2 + by

f n (t 1 , t 2 ) = 1 -1 - d (n) 1 bn t1 1 - d (n) 2 bn t2 , ∀(t 1 , t 2 ) ∈ R 2 + .
We have Thus, there is n δ ≥ 1 so that f n 2n gn , 0 ≥ 2δ and f n 0, where the first two inequalities hold by concavity of f n .

f n 2n g n , 0 = 1 -   1 - d (n) 1
Lemma 4. There exists a positive constant δ such that

H (1 -)p (n) a ||p (n) a ≥ -δ + a 1 d (n) 1 + a 2 d (n) 2 m (n)
, ∀n ≥ 1, ∀a ∈ N (n) .

Proof. By definition of H,

H (1 -)p (n) a ||p (n) a = (1 -)p (n) a log(1 -) + 1 -(1 -)p (n) a log 1 -(1 -)p (n) a -1 -(1 -)p (n) a log 1 -p (n) a .
The first and the second terms are greater than (1 -) log(1 -) and log( ) respectively. With δ = (1 -

) log 1 1-
+ log 1 > 0, we obtain

H (1 -)p (n) a ||p (n) a ≥ -δ -1 -(1 -)p (n) a log 1 -p (n) a ≥ -δ -log 1 -p (n) a .
Finally, observe that log 1 -p (n) a = a 1 log 1 -

d (n) 1 m (n) + a 2 log 1 - d (n) 2 m (n) ≤ - a 1 d (n) 1 + a 2 d (n) 2 m (n) ,
where in the inequality we used the fact that log 1 -

d (n) k m (n) ≤ - d (n) k m (n) for k = 1, 2.
Hence, we obtain the expected result.

Figure 1 :

 1 Figure1: A tree data network and a computer cluster with their representation as a processor-sharing system with n = 2 queues

Figure 3 :

 3 Figure 3: Representation of a tree data network

Figure 4 :

 4 Figure 4: Computer cluster with two exchangeable indices and a third index

Definition 4 .

 4 Let C be a polymatroid in R n + . C is called poly-symmetric with respect to partition Σ if for any k = 1, . . . , K, all indices in I k are pairwise exchangeable in C. Since the exchangeability of indices defines an equivalence relation on I, we can consider the quotient set of I by this relation, which is the partition of I into the maximal sets of pairwise exchangeable indices. Definition 4 can then be rephrased as follows: a polymatroid C is poly-symmetric with respect to a partition Σ if and only if Σ is a refinement of the quotient set of I by the exchangeability relation in C. It follows directly from the definition that the polymatroid of Example 2 is poly-symmetric with respect to partition ({1, 2}, {3}) when C {1} = C {2} , as we can see in Figure 3b. Also in Example 4, the polymatroid is poly-symmetric with respect to partition ({1, 3}, {2}). For each k = 1, . . . , K, let n k = |I k | denote the size of part k, where by part we mean a subset of the partition. For any A ⊂ I, let |A| Σ = (|A ∩ I k | : k = 1, . . . , K) denote the vector of sizes of each part of A in the partition. The set of these vectors is denoted by N = K k=1 {0, 1, . . . , n k }.

Figure 5 :Definition 5 .

 55 Figure 5: Computer cluster with a polymatroid capacity set which is poly-symmetric with respect to partition Σ = ({1, 3}, {2})

  and otherwise f (a) = min{f (b) + f (c) : b, c ∈ N s.t. b, c = a and a = b + c}, from which we can construct h by letting h(a) = min{f (b) : b ∈ N and a ≤ b}, ∀a ∈ N .

Figure 6 :

 6 Figure 6: User routes Example 6.Figure6gives a toy example with K = 2 possible access rates r 1 and r 2 . There are three users with access rate r 1 and two users with access rate r 2 . All users are constrained by the aggregation link with capacity C.

Figure

Let d 1 , d 2 ≥ 1 .Figure 7 :

 1217 Figure 7: Computer cluster with d 1 = 2 and d 2 = 3

4. 1

 1 Monotonicity resultWhile the property of poly-symmetry is not often satisfied in practice, except in specific cases like the examples of Sections 3.3 and 3.4, it can be used to derive stochastic bounds on most systems, as shown below. The following result will allow us to control the impact of the capacity set on performance.Given 0 < < 1 and a polymatroid C in R n + with rank function µ, we denote by (1 + )C the polymatroid in R n + with rank function (1 + )µ and by (1 -)C the polymatroid in R n + with rank function (1 -)µ.

Lemma 2 .

 2 For each A ⊂ I, we have µ(A) = ξmp a with ξ = 1 m s∈S µ s , a = |A| Σ and

Figure 8 :

 8 Figure 8: Bounds obtained with m = 10, 000, n = 1, 000, d 1 = 20, d 2 = 40

B. 1 . 2 ) 1 , 2 nd (n) 1 gn 2 nd

 121212 Case 2: a 1 > n gn or a 2 > n gn Combining Lemma 4 with (12), we deduce that there is a positive constant δ 3 such thatP M (n) (A) ≤ (1 -)µ (n) (A) ≤ e δ3m (n) -a1d any A ⊂ I (n) such that |A| Σ (n) = a. Since m (n) = bn and g n = o d (nwe have δ 3 m (n) ≤when n is large enough. If a 1 > n gn , we also have that

2 =

 2 any A ⊂ I(n) such that |A| Σ (n) = a. The union bound yieldsP ∃A ⊂ I (n) s.t. |A| Σ (n) = a and M (n) (A) ≤ (1 -)µ (n) (A) ω(log n),for large enough n, we haveP ∃A ⊂ I (n) s.t. |A| Σ (n) = a and M (n) (A) ≤ (1 -)µ (n) (A) ≤ e -δ5a1d (n)1 e -δ5a2d (n)

C Proof of the lemmas for Theorem 5 Lemma 3 .

 53 Let 0 < δ < 1 2 . Consider a sequence (g n : n ≥ 1) such that g n = o d

  2n gn ≥ 2δ for all n ≥ n δ . Then, for any n ≥ n δ and any t 1 , t 2 ≤ n gn , we havef n (t 1 , t 2 ) = f n t 1 t 1 + t 2 (t 1 + t 2 , 0) + 1 -t 1 t 1 + t 2 (0, t 1 + t 2 ) , ≥ t 1 t 1 + t 2 f n (t 1 + t 2 , 0) + t 2 t 1 + t 2 f n (0, t 1 + t 2 ),

	≥	t 1 t 1 + t 2	t 1 + t 2 2n gn	f n	2n g n	, 0 +	t 2 t 1 + t 2	t 1 + t 2 2n gn	f n 0,	2n g n	,
	≥ 2δ	t 1 g n 2n	+ 2δ	t 2 g n 2n	,
	= δ	(t 1 + t 2 )g n n	,

Appendix A Proof of Theorem 3

A.1 Recursion [START_REF] Bonald | Calculating the flow level performance of balanced fairness in tree networks[END_REF] Let a ∈ N \ {0}. By (4), we have

The regularity assumptions ensure that µ(A)

where for any p, q ∈ (0, 1), H[p||q] is the KL divergence between two Bernoulli random variables with parameters p and q respectively, given by

We also use the following lemmas which will be proved later in Appendix C:

and

. For large enough n, we have

Lemma 4. There exists a positive constant δ such that

Consider the sequence (g n : n ≥ 1) given by

, ∀n ≥ 1.

Observe that

and

. Now let n ≥ 1 and a ∈ N (n) . We distinguish two cases depending on the value of a.

gn and 0 ≤ a 2 ≤ n gn By Lemma 3, there is a positive constant δ 1 such that, for large enough n,

Using [START_REF] Gardner | The power of d choices for redundancy[END_REF], we deduce that

The union bound yields


BINAURAL LOUDNESS OF MOVING SOURCES IN FREE FIELD: PERCEPTUAL MEASUREMENTS VERSUS AT-EAR LEVELS

Sabine Meunier, Sophie Savel, Jacques Chatron, and Guy Rabau Aix Marseille Univ, CNRS, Centrale Marseille, LMA, Marseille, France 4 impasse Nikola Tesla, CS 40006, 13453 Marseille Cedex 13 Abstract Most investigations on the variations of loudness with the spatial position of a sound source have been made for static sounds. The purpose of this work was to study the loudness of a moving source. By analogy with studies on difference in loudness between sounds increasing or decreasing in intensity (without movement of the source), we studied the global loudness of a moving sound. The analogy with the sounds whose intensity varies is direct because the at-ear level depends on the position of the source, so a moving sound will create levels that vary over time at the entrance of the auditory canal. We measured the overall loudness of a moving source as a function of the starting and ending positions of the stimulus and of its direction of rotation. Overall, we did not find any overall loudness difference according to the direction of variation of the source. Moreover, the results obtained with a static sound seem to confirm, with absolute magnitude estimation, the amount of directional loudness sensitivity measured previously with an adaptive method.

In free field, loudness depends on the position of the sound source [START_REF] Sivonen | Directional loudness in an anechoic sound field, head-related transfer functions, and binaural summation[END_REF]. In order to quantify the effect of the incidence angle on loudness, the directional loudness sensitivity (DLS) is measured. DSL is defined as the level difference required for equal loudness between a frontal reference sound (azimuth 0°, elevation 0°) and a test sound at a given position. A negative DLS means that the test sound has been perceived softer than the frontal sound and vice versa. In a previous study, we showed a decrease in DLS with an increase in azimuth of an amount of more than 10 dB on average (25 listeners, [START_REF] Meunier | Interindividual differences in directional loudness[END_REF]. Different studies have also examined the loudness of sounds that increase and sounds that decrease in level. For sounds that only differ in temporal envelop, it has been shown that the global loudness of a sound whose level increases is greater than the global loudness of a sound whose level decreases (Ponsot et al., 2015a(Ponsot et al., , 2015b)). This phenomenon has been called asymmetry in loudness.

When a sound source is moving around a listener, the at-ear level of the sound varies. Moreover, if we refer to the studies on directional loudness, its loudness should also vary. The aim of the work presented here was to explore how global loudness of moving sounds is formed and the main point was to determine whether there is an asymmetry between sounds that move in opposite directions as their level and loudness also vary in opposite directions.

Experiment

Ten normal-hearing listeners participated in the experiment.

The loudness of moving sounds was measured in an anechoic room. The Vector Amplitude Base Panning (VBAP) method was used (Pulkki,1λλ7). It consisted in creating virtual sources from several loudspeakers situated at equidistance from the listener head in varying the gain of each loudspeaker. With this technique it was possible to move the sound around the listener. The speed of the movement was constant. The stimuli used for the experiment were a third-octave noise band centered at 5 kHz and white noise (140-17 000 Hz) of duration 2 s. The levels were 45, 50, 55, and 60 dB SPL. They were measured in the absence of the listener at the theoretical center of the head. The experiment was realized in the horizontal plan (elevation = 0°). The azimuths of the third-octave-band stimulus were either fixed at 75 or 135° (static sources) or varied from 75 to 135° and inversely (moving sources). For the white noise, the static positions were 45, 75, 135 and 150°, and the sound moved from 45 to 150° (and inversely) and from 75 to 135° (and inversely). These positions were chosen in order to produce different at-ear levels and different loudness levels when the stimulus varied in azimuth. For the third-octave-band stimulus, the directional loudness sensitivity decreased by about 8 dB from 75 to 135°; the at-ear level decreased by about 9.5 dB on the right ear (ipsilateral) and varied by less than 2 dB on the left ear (contralateral). For the white noise, the directional loudness sensitivity decreased by about 2.5 dB from 45 to 150° and by about 2 dB from 75 to 135°. The at-ear level decreased by about 6 dB on the right ear from 45 to 150° and by about 4 dB from 75 to 135°. It varied by about 4 dB on the left ear from 45 to 150° and by less than 1 dB from 75 to 135°. The at-ear levels were measured with blocked ear canals for all loudspeaker positions and all listeners. The values given above correspond to the average of the measurements made previously [START_REF] Meunier | Interindividual differences in directional loudness[END_REF] on the 10 listeners of the present work. The loudness was evaluated using an absolute magnitude estimation procedure. One block consisted of all conditions for one stimulus (static and moving sources at the 4 different levels). Each condition was repeated 3 times. A block was repeated once. Thus, for one listener and one condition the loudness was the geometric mean of 6 estimates. A training block was also run for each stimulus.

Results

The geometric means of the 10 listeners are shown in figures 1 and 2. There was no significant effect of the direction of variation on the estimates either for the thirdoctave-band stimulus [F(9,1)=0.013, p=0.91] or for the white noise [F(9,1)=3.33, p=0.1 for 45-150° ; F(9,1)=0.32, p=0.58 for 75-135°].

For the third-octave-band, a post-hoc LSD showed significant differences between the estimates of the static sounds at 75° and the other conditions (p<0.001) and no significant differences between the three other conditions. Whatever the direction of movement, the estimates of the moving sounds corresponded to the estimate of the sound at the position of 135° which was the softest sound.

For the white noise, there were no significant differences between all conditions.

For the static sounds, we found almost the same difference in level between sounds of different positions that were equally loud using an absolute magnitude estimation method (figures 1 and 2, left panels: 6 dB for the third-octave-band, 2 dB for the white noise between 45 and 150° and 1.8 dB for the white noise between 75 and 135°) and using an adaptive method to measure the DLS (figures 1 and 2, right panels : 7 dB for the third-octave-band, 2.5 dB for the white noise between 45 and 150° and 2 dB for the white noise between 75 and 135°).

The exponents of the loudness functions seem to be independent of the sound source position and of the movement (figures 1 and 2, left panels). They were around 0.25 for the third-octave band stimulus and around 0.29 for the white noise.

Discussion and Conclusion

The direction of the movement does not seem to affect the global loudness while DLS and at-ear levels vary in opposite ways for opposite directions. We did not find any asymmetry in loudness in this case, even if the at-ear level varied. This finding is in disagreement with the results of studies on asymmetry in loudness, in which the global loudness of an increasing sound was found larger than that of a decreasing sound. This may be due to the small amount of at-ear level variation (9.5 dB for the third-octaveband stimulus, 6 dB for the white noise from 45 to 150° and 4 dB from 75 to 135°, in the ipsilateral ear), much smaller than the dynamics of the stimuli used in experiment on loudness asymmetry for static sounds (15 or 30 dB). It may also be due to an influence of the contralateral ear in which the level variations were very small but were present.

For the third-octave band, we found than the loudness of the moving sound corresponded to the loudness of the sound at 135°, whatever the direction of variation. This result is in discrepancy with a prevalence of the louder part of the sound on the global loudness because at 135° the loudness of the third-octave-band stimulus is softer than at 75°. This phenomenon might be due to the fact that at 135° the source is not in the visual field of the listener, which would induce more attention to that part of the space. But for narrow-band noise, the localization is very poor, and around 5 kHz the sound would be localized in front of the listener [START_REF] Blauert | Spatial hearing.The psychophysics of human sound localization[END_REF].

Based on a different procedure, this experiment confirms the amount of directional loudness sensitivity found previously [START_REF] Meunier | Interindividual differences in directional loudness[END_REF]. The absolute magnitude estimation is much faster than the adaptive procedure used in [START_REF] Meunier | Interindividual differences in directional loudness[END_REF], and would be a promising alternative for measuring directional loudness sensitivity.

The exponents of the loudness functions were the same for the static and dynamic stimuli and did not depend on the position of the sound source. However, the exponents were very small, much smaller than the ones found usually in literature. For example, [START_REF] Canévet | Assimilation and asymmetry of loudness change in magnitude-estimation measurements[END_REF] found an exponent of 0.49 for a 4 kHz pure-tone. At 1 kHz the exponent is about 0.6 [START_REF] Steven | Concerning the form of the loudness function[END_REF]. This may be due to a contextual effect as static and dynamic sounds were presented in the same blocks.

Fechner Day 2018 34th

 2018 Annual Meeting of the International Society for Psychophysics 20th -24th August 2018, Lüneburg, Germany

Figure 1 .

 1 Figure 1. Geometric means (10 listeners) of the loudness estimates for the third-octave band centered on 5 kHz for static and dynamic sounds (left panel) and Directional Loudness Sensitivity as a function of the azimuth: mean of 10 listeners for the thirdoctave band centered on 5 kHz (right panel)

Acknowledgements

This work was supported by the LoudNat project funded by the French National Research Agency ANR-11-BS09-016-01.