Thomas Bonald
email: thomas.bonald@telecom-paristech.fr

Traffic Models for User-Level Performance Evaluation in Data Networks

Keywords: Flow-level model, mean throughput, congestion rate, balanced fairness

Traffic modeling is key to the capacity planning of data networks. Usual models rely on the implicit assumption that each user generates data flows in series, one after the other, the ongoing flows sharing equitably the considered backhaul link. We relax this assumption and consider the more realistic case where users may generate several data flows in parallel, these flows having to share the user's access line as well. We derive explicit user-level performance metrics like mean throughput and congestion rate in this context, assuming balanced fair sharing between ongoing flows. These results generalize existing ones in that both match in the limit of an infinite number of access lines.

I. INTRODUCTION

Internet service providers need to predict the impact of traffic load on the quality of service perceived by their customers. This is increasingly important with the advent of high-speed internet access that tends to move congestion from the access to the backhaul, where resources are shared by several users.

Internet traffic is most often modeled at flow level 1 , assuming some ideal bandwidth sharing between ongoing flows [START_REF] Heyman | A new method for analysing feedback-based protocols with applications to engineering web traffic over the internet[END_REF], [START_REF] Berger | Dimensioning bandwidth for elastic traffic in high-speed data networks[END_REF], [START_REF] Ben Fredj | Statistical bandwidth sharing: a study of congestion at flow level[END_REF], [START_REF] Barakat | Modeling internet backbone traffic at the flow level[END_REF], [START_REF] Kherani | Stochastic models for throughput analysis of randomly arriving elastic flows in the internet[END_REF]. Modeling traffic at packet level proves too complex and is hardly effective, given that users typically perceive quality of service at flow level [START_REF] Dukkipati | Why flow-completion time is the right metric for congestion control[END_REF]. In fact, the flow-level models of data networks can be considered as the analogues for the Erlang model of telephone networks and its extensions to multi-rate circuit-switched networks [START_REF] Bonald | Network Performance Analysis[END_REF]. They have proved essential for both dimensioning [START_REF] Berger | Dimensioning bandwidth for elastic traffic in high-speed data networks[END_REF], [START_REF] Bonald | Dimensioning high speed IP access networks[END_REF], [START_REF] Lassila | Dimensioning of data networks: a flow-level perspective[END_REF], [START_REF] Lassila | Dimensioning methods for data networks with flow-level QoS requirements[END_REF], [START_REF] Indre | Evaluating user-perceived performance in high-speed backhaul networks[END_REF] and traffic engineering [START_REF] Heyman | A new method for analysing feedback-based protocols with applications to engineering web traffic over the internet[END_REF], [START_REF] Lakshmikantha | Impact of file arrivals and departures on buffer sizing in core routers[END_REF], [START_REF] Kortebi | On the scalability of fair queueing[END_REF].

These models rely on the implicit assumption that each user generates data flows in series, one after the other, so that bandwidth sharing occurs on the considered backhaul link only, and not on the user's access line. In this paper, we relax this assumption and consider the more realistic case where users may generate several data flows in parallel, these flows having to share both the backhaul link and the user's access line. It is not obvious how bandwidth is shared by end-to-end congestion control in this context. We assume bandwidth sharing is balanced fair, which is the only allocation yielding a closed-form stationary distribution of the network state [START_REF] Bonald | Insensitive bandwidth sharing in data networks[END_REF]. Balanced fairness in fact provides a very good Thomas Bonald is a member of LINCS. See www.lincs.fr 1 A flow is here defined as the set of packets having the same 5-tuple: IP source and destination addresses, IP source and destination ports, protocol. approximation of proportional fairness [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF], which is considered as representative of the way bandwidth is shared in the Internet [START_REF] Kelly | Rate control for communication networks: shadow prices, proportional fairness and stability[END_REF], [START_REF] Mo | Fair end-to-end window-based congestion control[END_REF], [START_REF] Kunniyur | End-to-end congestion control schemes: Utility functions, random losses and ecn marks[END_REF].

Existing models assume that flows are generated either according to a Poisson process (the so-called infinite-source model) or by n users, each alterning between the active state and the idle state (the so-called finite-source model) [START_REF] Bonald | Network Performance Analysis[END_REF]; in both cases, each user has at most one flow in progress at any given time. Our model consists of n users, each generating data flows according to a Poisson process; in particular, there is no limit on the number of flows in progress coming from the same user. We refer to this model as the multi-source model, since each user can now be viewed as an independent source of flows.

Since the model allows each user to generate multiple flows in parallel, it is not sufficient to focus on the flow level to evaluate user-level performance. In particular, the throughput of each user is the total throughput of her flows in progress. The corresponding performance results can differ significantly from those obtained under the infinite-source model and the finite-source model. They coincide only in the limit of an infinite number of access lines.

We consider a single backhaul link of fixed capacity (in bit/s) shared by a population of n users. The total throughput of each user is also constrained by the rate of her access line. The models apply equally to the uplink (from the users to the Internet) and to the downlink (from the Internet to the users). All traffic is elastic, meaning that each flow generated by a user corresponds to some data transfer and remains active as long as the corresponding data have not been fully transferred. Due to the insensitivity property, we do not specify the flow size distribution beyond the mean, nor the distribution of the idle times in the finite-source model [START_REF] Bonald | Network Performance Analysis[END_REF]. We provide formulas that can be used in planning tools or directly by network engineers to get insights into the impact traffic on user-level performance [START_REF] Indre | Evaluating user-perceived performance in high-speed backhaul networks[END_REF].

In the rest of the paper, we first review and extend the results obtained with the infinite-source model and the finitesource model, with a focus on two performance metrics: mean throughput and congestion rate. We then present the multisource model and compare numerically the results derived from the three models in some typical traffic scenarios.

II. INFINITE-SOURCE MODEL

Like the Erlang model for telephone networks, which relies on the assumption of Poisson call arrivals [START_REF] Erlang | Solution of some problems in the theory of probabilities of significance in automatic telephone exchanges[END_REF], it is common practice to assume Poisson flow arrivals in data networks. This is referred to as the infinite-source model since it corresponds to the finite-source model (presented in the next section) in the limiting case where the number of users n grows to infinity.

A. No access rates

We start with the simplest case where there is no rate limit at the access: each user has full access to the backhaul link, which is assumed to be equitably shared by ongoing flows. Flows arrive according to a Poisson process of intensity λ and have i.i.d. sizes of mean σ bits, corresponding to a traffic intensity of A = λσ bit/s. Denoting by C the capacity of the backhaul link in bit/s, the link load is ρ = A/C. Under the assumption of perfect fair sharing, the traffic model corresponds to an M/G/1 processor-sharing queue of load ρ. It is stable if and only if ρ < 1, in which case the stationary distribution of the number of flows in progress X is given by:

π(x) = (1 -ρ)ρ x .
It turns out that the stationary distribution seen by a user having a flow in progress is different. Since there are x flows in progress in state x, which are assumed to be generated by different users, each active user sees the size-biased probability distribution of the random variable X, π (x) ∝ xπ(x).

Observe that π (0) = 0. We will denote by P and E the corresponding probability measure and expectation, respectively. We derive two key performance metrics on this basis.

Mean throughput: The first performance metric is the mean throughput experienced by users. Assume there are x ongoing flows, with x > 0. The throughput of each flow is then C/x. Thus the mean throughput experienced by users, normalized by the maximum throughput C, is given by

γ = E 1 X .
Replacing E by its expression, we obtain

γ = x>0 π(x) E(X) = ρ E(X)
,

that is γ = 1 -ρ. (1)
Observe that the mean throughput decreases linearly with the link load.

Congestion rate: The second performance metric is the congestion rate, defined as the probability that an active user gets a throughput less than the maximum throughput C. Since there is no rate limit at the access, the congestion rate is the probability seen by an active user that there are other active users:

η = P (X > 1)
.

Replacing E by its expression, we obtain

η = x>1 xπ(x) E(X) = 1 - P (X = 1) E(X) , that is η = ρ(2 -ρ). (2)
As expected, the congestion rate grows from 0 to 1 as the link load grows from 0 to 1.

B. Same access rates

We now consider the practically interesting case where each flow has a rate limit r < C corresponding to the capacity of the user's access line in bit/s. For convenience, we assume that the capacity of the backhaul link is some multiple of this access rate, that is C = mr for some integer m ≥ 1. We denote by α = A/r the traffic intensity expressed in units of the access rate. This would correspond to the mean number of flows if the backhaul link were of infinite capacity. The model corresponds to an M/G/m processor-sharing queue of load ρ = A/C. Under the stability condition ρ < 1, the stationary distribution of the number of flows X is given by:

π(x) = 1 G α x x! for x ≤ m, α m m! ρ x-m for x > m, where G denotes the normalization constant: G = m x=0 α x x! + α m m! ρ 1 -ρ .
Both performance metrics extend to this case. We still denote by P and E the corresponding size-biased probability measure and expectation. Mean throughput: Assume there are x ongoing flows, with x > 0. The throughput of each flow is then min(r, C/x). We deduce the mean throughput seen by users, normalized by the maximum throughput r,

γ = E min 1, m X .
Replacing E by its expression, we obtain

γ = E(min(X, m)) E(X) = α E(X)
,

where the second equality follows from work conservation. Finally, we get

γ = m(1 -ρ) 2 π(m) + m(1 -ρ) 2 .
Congestion rate: The throughput of a flow is less than its maximum r whenever the number of flows exceeds m. We deduce the congestion rate

η = P (X > m), that is η = π(m)(1 + m(1 -ρ)) π(m) + m(1 -ρ) 2 .

C. Different access rates

Finally, we consider the general case of K different access rates r 1 , . . . , r K . We denote by A 1 , . . . , A K the respective traffic intensities in bit/s generated by each class of users, and by α 1 = A 1 /r 1 , . . . , α K = A K /r K the traffic intensities expressed in multiples of the access rates; these would correspond to the mean number of flows of each class if the backhaul link were of infinite capacity. The corresponding loads on the backhaul link are ρ 1 = A 1 /C, . . . , ρ K = A K /C, and the total load is ρ = ρ 1 + . . . + ρ K .

Let X be the K-dimensional vector of the number of flows of each class in progress. Denote by φ k (x) the total throughput of class-k users in state x. The capacity constraints are

∀k = 1, . . . , K, φ k (x) ≤ x k r k and K k=1 φ k (x) ≤ C.
Now let r be the K-dimensional vector of access rates. Under balanced fair sharing [START_REF] Bonald | A recursive formula for multirate systems with elastic traffic[END_REF], all users get their maximum throughput, in the sense that φ k (x) = x k r k for all k = 1, . . . , K, if and only if x.r ≤ C (the access lines are limiting); otherwise, no user gets her or his maximum throughput and the total throughput is

K k=1 φ k (x) = C (the backhaul link is limiting).
The stability condition is ρ < 1 and the vector X has the stationary distribution:

π(x) = 1 G α x 1 1 x1! . . . α x K K x K ! for x.r ≤ C, K k=1 ρ k π(x -e k ) for x.r > C,
where e k is the unit vector on component k and G denotes the normalization constant. Here and in the rest of the paper, we adopt the convention that π(x) = 0 for any x ∈ N K .

Performance now depends on the user's class. The stationary distribution of X seen by class-k users is

π k (x) ∝ x k π(x).
We denote by P k and E k the corresponding probability measure and expectation, respectively.

Mean throughput: All class-k users get the same throughput φ k (x)/x k in any state x such that x k > 0. We deduce the mean throughput of class-k users, normalized by the maximum throughput r k ,

γ k = E k φ k (X) X k r k . (3)
Replacing E k by its expression, we obtain

γ k = E(φ k (X)) E(X k )r k = α k E(X k ) ,
where the second equality follows from work conservation.

Congestion rate: The throughput of a class-k user is less than its maximum r k in any state x such that x.r > C. We deduce:

η k = P k (X.r > C). (4)
Both performance metrics can be computed through a recursive formula [START_REF] Bonald | A recursive formula for multirate systems with elastic traffic[END_REF], which is the analogue of the Kaufmann-Roberts formula for circuit-switched networks.

D. Numerical results

Figure 1 shows the mean throughput and congestion rate as a function of the link load ρ when all users have the same access rate r and the backhaul link has capacity C = mr with m = 1, 10, 100. For m = 1, there is actually no access rate limit and users have full access to the backhaul link, as considered in §II-A.

We observe that performance improves with m, as the backhaul link becomes less constraining. For m = 100, the mean throughput is approximately equal to the access rate until a load of 85%, corresponding to a congestion rate smaller than 5% (the impact of the backhaul link is negligible), then decreases quickly to 0, with congestion rate larger than 5% (the impact of the backhaul link becomes dominant).

III. FINITE-SOURCE MODEL

When the user population is relatively small, flow arrivals cannot be considered as Poisson. Each user is still assumed to generate flows in series, with a random idle time between the end of a flow and the beginning of the next flow. This is the analogue of the Engset model used for telephone networks [START_REF] Engset | On the calculation of switches in an automatic telephone system[END_REF]. We only give the stationary distribution of the number of active users; the corresponding performance metrics can be derived as for the infinite-source model.

A. No access rates

Consider n users having full access to the backhaul link. Any idle user tends to become active at rate ν > 0, while any active user tends to become idle at rate µ = C/σ when no other users are active. We deduce that any user alone in the system is active a fraction of time β/(1 + β), with β = ν/µ. Now assume active users share the backhaul link in a fair way. The stationary distribution of the number of active users X is then given by

π(x) = 1 G n! (n -x)! β x , x ≤ n,
where G is the normalization constant:

G = n x=0 n! (n -x)! β x .
The infinite-source model corresponds to the case n → ∞ and β → 0, with nβ → ρ. A key difference with the infinitesource model is that traffic intensity is no longer an exogenous parameter but given by A = CP (X > 0). We deduce the link load:

ρ = P (X > 0) = G -1 G .

B. Same access rates

Now assume all users have the same access rate r. The link capacity is C = mr for some integer m ≥ 1, with n > m. Any active user tends to become idle at rate µ = r/σ when no other users are active. The stationary distribution of the number of flows X becomes:

π(x) = 1 G n x β x for x ≤ m, n! (n-x)!m! β x m x-m for m < x ≤ n,
where β = ν/µ and G is the normalization constant. Traffic intensity is A = E(min(X, m))r, corresponding to load ρ = E(min(X, m)) m .

C. Different access rates

Finally, consider the general case of K different access rates r 1 , . . . , r K . There are n k users with access rate r k , mean flow size σ k and mean idle time 1/ν k between two flows. Under balanced fair sharing, the stationary distribution of the system state X is given by:

π(x) = 1 G K k=1 n k x k β x k k for x.r ≤ C, K k=1 β k r k C (n k -x k + 1)π(x -e k ) for x.r > C, where β k = ν k /µ k , µ k = r k /σ k
and G the normalization constant. Traffic intensity is A = E(min(X.r, C)), corresponding to load:

ρ = E(min(X.r, C)) C .

D. Numerical results

Figure 2 shows the mean throughput and the congestion rate when all users have the same access rate r and the backhaul link has capacity C = mr with m = 10; the number of users is n = 20, 50, 100 and ∞, this last case corresponding to the infinite-source model. We observe that, while the congestion rate obtained with the finite-source model quickly tends to that derived from the infinite-source model when n grows, the convergence is much slower for the mean throughput: for n = 100, the results still differ significantly.

IV. MULTI-SOURCE MODEL

We now introduce the multi-source model where data flows must share both the backhaul link and the user's access line. We consider n users, with user i generating flows according to an independent Poisson process of intensity λ i , corresponding to the traffic intensity a i = λ i σ in bit/s. We are interested in the total throughput obtained by each user.

A. No access rates

As above, we first consider the case where each user has full access to the backhaul link. Under fair sharing between flows in progress, the model reduces to an M/G/1 multi-class processor-sharing queue. Denoting by ρ i = a i /C the load due to user i and by ρ = ρ 1 +. . .+ρ n the total load, the stationary distribution of the number of flows of each user X is given by

π(x) = (1 -ρ) x 1 + . . . + x n x 1 , . . . , x n ρ x1 1 . . . ρ xn n ,
under the stability condition ρ < 1. Now user i sees the stationary distribution

π i (x) ∝ π(x)1 xi>0
when active. We denote by P i and E i the corresponding probability measure and expectation.

Mean throughput: The total throughput of user i is proportional to the number of ongoing flows of this user, that is (x i / j x j )×C in any state x such that x i > 0. We deduce the mean throughput of user i, normalized by the maximum throughput C,

γ i = E i X i j X j
.

By work conservation,

ρ i = E X i j X j 1 Xi>0 , so that γ i = ρ i P (X i > 0) . Since P (X i > 0) = ρ i 1 -ρ + ρ i ,
we obtain

γ i = 1 -ρ + ρ i .
Note that the mean throughput is larger than that obtained with the infinite-source model, given by (1), with equality when ρ i → 0 (in which case user i generates flows in series, as in the infinite-source model). Observe also that the mean (normalized) throughput of user i is larger than the load ρ i generated by this user, with equality when ρ → 1 (in which case the system is saturated and the throughput of each user corresponds to her bandwidth share). For homogeneous traffic distribution, all users get the same throughput,

γ = 1 -ρ + ρ n ≥ 1 n .
Congestion rate: The congestion rate seen by user i is the probability that the total throughput of this user is less than C, that is the probability that there are other active users:

η i = P i ( j X j > X i ).
We get

η i = P (X i > 0, j =i X j > 0) P (X i > 0) . Since P (X i > 0, j =i X j = 0) = ρ i (1 -ρ) 1 -ρ i ,
we obtain

η i = (2 -ρ) ρ -ρ i 1 -ρ i .
This congestion rate is smaller than that obtained with the infinite-source model, given by ( 2), with equality when ρ i → 0.

B. Same access rates

Now assume all users have the same access rate r, with C = mr for some integer m such that 1 ≤ m < n. We denote by i = a i /r the load of user-i access line. The load of user i on the backhaul link is

ρ i = a i /C = i /m.
Let φ i (x) be the total throughput of user i in state x. The capacity constraints are ∀i = 1, . . . , n, φ i (x) ≤ r and n i=1 φ i (x) ≤ C.

Let n(x) = n i=1 1 xi>0 be the number of active users in state x. Under balanced fair sharing, all active users get their maximum throughput, that is φ i (x) = r for all i = 1, . . . , n such that x i > 0, if and only if n(x)r ≤ C (the access lines are limiting); otherwise, no user gets the maximum throughput and the total throughput is n i=1 φ i (x) = C (the backhaul link is limiting). Under the stability condition ρ < 1 and i < 1 for all i = 1, . . . , n, the stationary distribution of the network state X is

π(x) = 1 G n i=1 xi i for n(x) ≤ m, n i=1 ρ i π(x -e i ) otherwise,
where G is the normalization constant. Since the network has a tree topology, we deduce from [START_REF] Bonald | Computational aspects of balanced fairness[END_REF] that

G = I⊂{1,...,n},|I|≤m i∈I i 1 -i + I⊂{1,...,n},|I|=m i∈I i 1 -i i ∈I i m - n i=1 i .
Mean throughput: The mean throughput of user i, normalized by the maximum throughput r, is given by

γ i = E i φ i (X) r .
By work conservation, E(φ i (X)) = a i so that

γ i = i P (X i > 0) . Now P (X i = 0) = G i G ,
where G i denote the normalization constant in the absence of user i,

G i = I⊂{1,...,n}\{i},|I|≤m j∈I j 1 -j + I⊂{1,...,n}\{i},|I|=m j∈I j 1 -j j ∈I,j =i j m -j =i j .
We deduce

γ i = G i G -G i . (5)
Congestion rate: The congestion rate seen by user i is

η i = P i (φ i (X) < r).
We get

η i = P (X i > 0, j 1 Xj >0 > m) P (X i > 0) , that is η i = F -F i G -G i , (6)
with

F = I⊂{1,...,n},|I|=m j∈I j 1 -j j ∈I j m - n j=1 j
and

F i = I⊂{1,...,n}\{i},|I|=m j∈I j 1 -j j ∈I,j =i j m -j =i j .

C. Different access rates

We now consider the general case where user i has access rate r i . The load of user-i access line becomes i = a i /r i . The capacity constraints are

∀i = 1, . . . , n, φ i (x) ≤ r i and n i=1 φ i (x) ≤ C.
Under balanced fair sharing, all active users get their maximum throughput if and only if n i=1 r i 1 xi>0 ≤ C. Under the stability condition ρ < 1 and i < 1 for all i = 1, . . . , n, the stationary distribution of the network state X is

π(x) = 1 G n i=1 xi i for n i=1 r i 1 xi>0 ≤ C, n i=1 ρ i π(x -e i ) otherwise,
where G denotes the normalization constant [START_REF] Bonald | Computational aspects of balanced fairness[END_REF] G = I⊂{1,...,n},e I .r≤C i∈I i

1 -i + I⊂{1,...,n},e I .r≤C i∈I i 1 -i i ∈I,ri+e I .r>C i r i C - n i=1 i r i
, with e I the vector of ones on all components i ∈ I and zeros elsewhere.

Mean throughput: The mean throughput of user i normalized by the maximum throughput r i of this user is

γ i = E i φ i (X) r i .
We obtain the same expression [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF], with 1j j ∈I,j =i,rj +e I .r>C j r j Cj =i j r j .

G i = I⊂{1,...,
Congestion rate: The congestion rate seen by user i is

η = P i (φ i (X) < r i ),
that is (6) with F = I⊂{1,...,n},e I .r≤C j∈I j 1j j ∈I,rj +e I .r>C j r j Cj j r j and F i = I⊂{1,...,n},i ∈I,e I .r≤C j∈I j 1j j ∈I,j =i,rj +e I .r>C j r j Cj =i j r j .

D. Different user classes

The previous formulas have exponential complexity in n. To keep the complexity polynomial in n, we need to group users in some finite number of classes K, as in the infinite-source model and the finite-source model. With some slight abuse of notation, we denote respectively by r k and k the rate and the load of the access line of each class-k user. There are n k class-k users and we denote by n the vector (n 1 , . . . , n K ). The normalization constant is then given by G = ≤n: .r≤C

K k=1 n k k k 1 -k k + ≤n: .r≤C K k=1 n k k k 1 -k k × j: j <nj , .r+rj >C (n j -j ) j r j C - K k=1 n k k r k .
The mean throughput of each class-k user is

γ k = G k G -G k ,
where G k is the constant G with n k replaced by n k -1.

Similarly, letting

F = ≤n: .r≤C K k=1 n k k k 1 -k k × j: j <nj , .r+rj >C (n j -j ) j r j C - K k=1 n k k r k ,
we obtain the congestion rate of class-k users

η k = F -F k G -G k ,
where F k is the constant F with n k replaced by n k -1.

In the limit where the number of users tends to infinity with traffic intensities n 1 1 r 1 , . . . , n K K r K tending to some fixed constants A 1 , . . . , A K such that A 1 + . . . + A K < C, the multi-source model reduces to the infinite-source model: there is an infinite population of users, each user generating flows according to a Poisson process of null intensity. We observe that the infinite-source model is overly pessimistic while the finite-source model is overly optimistic compared to the multi-source model, especially for the mean throughput. For the congestion rate, the infinite-source model is a good approximation of the multi-source model only for n = 10m while the finite-source model is a very good approximation in both cases.

E. Numerical results

Figure 5 shows the results obtained for two classes of users, class-2 users generating 10 times more traffic than class-1 users. There is the same number of class-1 and class-2 users. All users have the same access rate r, C = mr with m = 1, 10, 100, and there is a total of n = 10m users. We observe that class-1 performance is well approximated by the infinite-source model while class-2 performance is better approximated by the finite-source model. None of these two models is satisfactory: the underlying assumption of flows generated in series by each user does not allow a proper evaluation of user-level performance.

The same conclusion can be drawn from Figure 6, showing the results for two classes of users with different access rates, r 1 = 1 and r 2 = 4. We take n 1 = 4n 2 and the same load for all access lines so that the total traffic intensity is the same for each class. Here m = C/r 1 takes the values 5, 50, 500 and the total number of users is n = 2m.

V. CONCLUSION

We have proposed a new traffic model for evaluating userlevel performance in data networks. The key characteristic of this model is to account for bandwidth sharing on the user's access line. The results turn out to be very different from those obtained with usual models in practically interesting cases, like n = 100 users having different traffic profiles or access rates. They coincide only for large values of n, say n ≥ 1000.

One of the key benefits of the proposed multi-source model is to account precisely for the number of access lines n without the complexity of the finite-source model. For instance, traffic intensity (and thus link load) is an exogenous parameter of the multi-source model but an endogenous parameter of the finite-source model. Moreover, the normalization constant is explicit in the multi-source model, which greatly simplifies the computation of the performance metrics.

A drawback of the multi-source model compared to the infinite-source model is the lack of a recursive formula for evaluating the normalization constant in the presence of a large number of different access rates. We let this for future work. Other interesting issues include the extensions of this model to non-elastic traffic (for instance, adaptive streaming traffic) and to several aggregation stages in the backhaul network.

Fig. 1 .

 1 Fig. 1. Performance metrics under the infinite-source model.

Fig. 2 .

 2 Fig. 2. Performance metrics under the finite-source model.

Figures 3 Fig. 3 .Fig. 4 .

 334 Figures 3 and 4 compare the performance metrics obtained with the three considered models when all users have the same access rate r, C = mr with m = 1, 10, 100, n = 2m and n = 10m, respectively. Traffic distribution is homogeneous.

Fig. 5 .

 5 Fig. 5. Mean throughput for m = 1, 10, 100 (from bottom to top) and n 1 = n 2 = 5m.

Fig. 6 .

 6 Fig. 6. Mean normalized throughput for m = 5, 50, 500 (from bottom to top), n = 2m, n 1 = 4n 2 .


Thomas Bonald
email: thomas.bonald@telecom-paristech.fr

James Roberts
email: james.roberts@irt-systemx.fr

Multi-Resource Fairness: Objectives, Algorithms and Performance

Keywords: C.2.1 [Computer communication networks]: Network Architecture and Design-packet-switching networks; C.4 [Performance of systems]: [modeling techniques, performance attributes] Algorithms, Performance Dominant resource fairness, proportional fairness, bottleneck max fairness, multi-resource sharing, cluster computing

Designing efficient and fair algorithms for sharing multiple resources between heterogeneous demands is becoming increasingly important. Applications include compute clusters shared by multi-task jobs and routers equipped with middleboxes shared by flows of different types. We show that the currently preferred objective of Dominant Resource Fairness (DRF) has a significantly less favorable efficiency-fairness tradeoff than alternatives like Proportional Fairness and our proposal, Bottleneck Max Fairness. We propose practical algorithms to realize these sharing objectives and evaluate their performance under a stochastic demand model. It is shown, in particular, that the strategyproofness property that motivated the choice of DRF for an assumed fixed set of jobs or flows, is largely irrelevant when demand is dynamic.

INTRODUCTION

Multi-resource fairness has recently received a lot of attention thanks mainly to two papers by A. Ghodsi and coauthors [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF][START_REF] Ghodsi | Multi-resource fair queueing for packet processing[END_REF]. In the present paper we argue that the objective of dominant resource fairness (DRF), advocated by Ghodsi et al. for resource sharing in compute clusters and routers equipped with middleboxes, respectively, is not preferable to more classical sharing objectives like proportional fairness (PF) which achieve a better efficiency-fairness tradeoff. Such objectives were discarded by Ghodsi et al. as being vulnerable to manipulation by users seeking to gain more than their fair share by falsely stating their requirements. The advocated strategyproofness property, possessed by DRF but not PF in a context of static demand, is not in fact discriminating when considering the more realistic context of dynamic demand.

Multi-resource sharing in a compute cluster consists in launching appropriate numbers of tasks of multi-task jobs. Each task of a given job has its particular requirements for CPU, RAM and other resources. In practice, various constraints on the placement of tasks on physical machines need to be taken into account but, for present purposes, we follow Ghodsi et al. [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF] and assume resources of the same type are assembled in homogeneous pools. The question is, how should a central scheduler determine the numbers of simultaneous tasks to run for all the currently active jobs, ensuring efficiency and some measure of fairness.

Routers increasingly employ middleboxes to process packets and these constitute potential bottlenecks for flows, in addition to link bandwidth. Different flows have different per-packet resource requirements (e.g., some require complex packet processing, others none) and the issue here is what packet rates should be imposed for concurrent flows in order to efficiently and fairly share all types of resource of these software routers.

Bandwidth sharing in a network is a particular form of multi-resource sharing. The problem is generally simpler since all flows sharing a given link are assumed to have identical requirements. This assumption is not true, however, for some wireless links where the resource to be allocated is spectrum time and the amount required to realize a given bit rate varies considerably between terminals, depending on their particular radio conditions. It is important to share wireless and wired links in a manner that adequately balances efficiency and fairness.

We have already made the case in a recent paper for proportional fair sharing of compute cluster resources [START_REF] Bonald | Enhanced cluster computing performance through proportional fairness[END_REF]. Here we extend those arguments to the case of router resources and networks and introduce a new allocation objective called bottleneck max fairness (BMF). BMF is a pragmatic alternative to PF to which it has similar performance in all three application areas.

In addition to the introduction of BMF, the main contributions of the paper are • a characterization of the properties of BMF including, in Theorem 1, a first result on the stability conditions of this sharing objective,

• practical algorithms allowing the implementation of PF and BMF allocations, the algorithms for BMF being rather simpler than those for PF,

• results on the impact of falsely declared resource requirements, illustrating the practical strategyproofness of PF and BMF allocations under dynamic demand.

We first describe DRF, PF and BMF sharing objectives in abstract terms common to the above three application contexts. We define the corresponding allocations and discuss their significant characteristics. Algorithms are then discussed for realizing the respective allocations and we propose practical, low-complexity algorithms to realize PF and BMF sharing in compute clusters, software routers and networks, respectively. The following section on performance includes an important theorem on BMF stability and presents numerical results that justify our claim that DRF is not in fact the preferred objective. Under dynamic demand, where jobs or flows arrive over time and have finite size, completion times are consistently and significantly smaller with either PF or BMF allocations. We further highlight the implausibility of players being able to game the system when these allocations are applied to a dynamic population of jobs or flows.

OBJECTIVES

We define DRF, PF and BMF multi-resource sharing objectives with respect to a fluid model where resources are assumed infinitely divisible. The model is abstract and, rather than jobs or flows, we refer to transactions. These are assumed divisible into a large number of infinitesimal components (representing tasks or packets, for instance) having homogeneous resource usage characteristics.

The fluid model

Consider R infinitely divisible resources of normalized capacity 1 to be shared by n transactions indexed by i. Each transaction i requires amounts of each resource in fixed proportions and the amount allocated determines the rate at which the transaction progresses. We denote the requirements of transaction i by a vector ai = (ai1, . . . , aiR). We say that transaction i requires resouce j if aij > 0. A resource j for which aij = max k {a ik } is called a dominant resource for transaction i.

An allocation is defined by a vector of real numbers ϕ = (ϕ1, . . . , ϕn) such that ϕiaij is the fraction of resource j allocated to transaction i. The allocation must satisfy capacity constraints:

n i=1 ϕiaij ≤ 1, for j = 1, . . . , R. (1)
We say that resource j is saturated if n i=1 ϕiaij = 1. We refer to such a resource as a bottleneck.

Sharing properties

The allocation ϕ should arguably possess the following properties [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF][START_REF] Bonald | Enhanced cluster computing performance through proportional fairness[END_REF]: Pareto-efficiency. Each transaction requires some resource which is saturated.

Envy-freeness.

No transaction should prefer the allocation of some other transaction.

Sharing-incentive. Each transaction gets no less than a 1/n share of its dominant resource.

Single-resource fairness. Resource shares ϕiai1 are all equal to 1/n when R = 1.

Single-bottleneck fairness. The shares ϕiaij of resource j are all equal to 1/n whenever j is the only bottleneck.

Strategyproofness. The resource shares of any transaction do not increase if this transaction modifies its vector of resource requirements.

Scale-invariance. The resource shares remain the same when the vector of resource requirements of any transaction is multiplied by a scaling factor.

It is straightforward to check that single-resource fairness is a rather crucial requirement in that it is realized by any Pareto-efficient allocation that fulfills any one of the other properties.

Dominant resource fairness

Dominant resource fairness (DRF) is the unique Pareto efficient allocation where transactions obtain fractions of their dominant resource that are as equal as possible. Equality may not be possible if some transactions require only a subset of the resources [START_REF] Parkes | Beyond dominant resource fairness: extensions, limitations, and indivisibilities[END_REF]. DRF in fact corresponds to weighted max-min fairness where the weight of transaction i is inversely proportional to its dominant resource requirement maxj{aij}.

DRF satisfies all properties listed in §2.2 except singlebottleneck fairness [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF][START_REF] Bonald | Enhanced cluster computing performance through proportional fairness[END_REF]: even in the presence of a single bottleneck, the shares of this resource are not equal and depend on requirements for non-saturated resources. The main advantage of DRF over other allocations is that it is strategyproof. This means a transaction cannot gain a greater share of resources by boosting some component of its requirement vector.

Proportional fairness

An allocation ϕ is proportional fair (PF) if, for any other allocation ϕ satisfying (1), the sum of proportional changes is non-positive, i (ϕ i -ϕi)/ϕi ≤ 0 [START_REF] Kelly | Rate control for communication networks: Shadow prices, proportional fairness and stability[END_REF]. Equivalently, ϕ maximizes i log ϕi subject to (1) and can thus be said to maximize social welfare assuming a logarithmic utility function.

While PF was introduced in [START_REF] Kelly | Rate control for communication networks: Shadow prices, proportional fairness and stability[END_REF] as an objective for sharing bandwidth in a wired network, it was advocated independently by Tse and co-authors as the preferred allocation for a time-shared wireless downlink channel [START_REF] Viswanath | Opportunistic beamforming using dumb antennas. Information Theory[END_REF].

By the Karush-Kuhn-Tucker theorem, PF is uniquely characterized in terms of Lagrange multipliers νj. We have,

1 ϕi = R j=1 aijνj, (2)
for i = 1, . . . , n, where νj ≥ 0 and νj > 0 if and only if resource j is a bottleneck. PF is clearly Pareto-efficient. In fact, it satisfies all properties of §2.2 except strategyproofness. The proof of envyfreeness is given below; other properties are proved in [START_REF] Bonald | Enhanced cluster computing performance through proportional fairness[END_REF].

Proposition 1. The PF allocation is envy-free.

Proof. For any two transactions i1, i2, it follows from (2) that R j=1 νj(ϕi 1 ai 1 j -ϕi 2 ai 2 j ) = 0.

Since not all Lagrange multipliers are zero, this implies that ϕi 1 ai 1 j ≥ ϕi 2 ai 2 j for some resource j: transaction i1 does not prefer the allocation of transaction i2.

PF is the only utility maximizing allocation that is singleresource fair [START_REF] Bonald | Enhanced cluster computing performance through proportional fairness[END_REF]. In particular, none of the properties except Pareto-efficiency is satisfied by a utility maximizing allocation other than PF.

To see why PF is not strategyproof, consider the following example: we have R = 2 resources and n = 2 transactions with requirements a1 = (1/2, 1) and a2 = (1, 1/2). The PF allocation is then ϕ = (2/3, 2/3). If transaction 1 claims requirement a 1 = (2/3, 1), we find ϕ = (3/4, 1/2) yielding a bigger share for transaction 1 at the expense of transaction 2. Note, however, that if a user does not know the other requirements, an ill-chosen modification can instead lead to it receiving a smaller share. Continuing the above example, if transaction 1 claims a 1 = (1, 1), the PF allocation would be ϕ = (1/2, 1/2). Both transactions lose out compared to the result of the truthful declaration, a1 = (1/2, 1).

It is interesting to note that, for n = 2, one can characterize the maximum gain a transaction can obtain by a false declaration. We have the following proposition.

Proposition 2. For n = 2 transactions, the relative gain obtained by a transaction declaring false requirements cannot exceed 50% under PF.

Proof. Without loss of generality, we can assume that R = 2 (whenever R > 2, one of the resources is never saturated since its requirements are dominated by those of another resource). By scale invariance, we can take a12 = a21 = 1 and a11, a22 ≤ 1. Assume transaction 1 declares false requirement a 11 on resource 1. If 1 2 (1/a11 + a22) < 1 then resource 1 is the single bottleneck and no winning strategy exists. Otherwise, resource 2 is a bottleneck for the true requirement and transaction 1 gets the maximum share of this resource, given by:

ϕ1 = min 1 2 , 1 -a22 1 -a11a22 .
The best strategy for transaction 1 is to increase a11 until it gets the maximum share of both resource 1 and resource 2, that is to set

a 11 = 1 2 -a22 ,
in which case the allocation is given by

ϕ 1 = 1 - a22 2 .
It can be verified that the relative gain satisfies

ϕ 1 -ϕ1 ϕ1 ≤ 1 2 ,
with equality for a11 = 0, a22 = 1/2, that is a 11 = 2/3.

Bottleneck max fairness

Dolev et al. proposed the "no justified complaints" objective as an alternative to DRF [START_REF] Dolev | No justified complaints: On fair sharing of multiple resources[END_REF]. To be concise, we adopt a simplified version of this objective: a transaction has no justified complaint if it receives at least a fraction 1/n of at least one bottleneck. Pareto efficient allocations fulfilling this objective for all users are said to realize "bottleneckbased fairness" [START_REF] Zeldes | On-line fair allocations based on bottlenecks and global priorities[END_REF][START_REF] Gutman | Fair allocation without trade[END_REF].

There are in fact many allocations that are bottleneckbased fair. We restrict the class of such allocations somewhat by requiring in addition that every transaction i receives an allocation ϕiaij of some bottleneck resource j that is maximal for that resource. We call such allocations "bottleneck max fair" (BMF).

Discussions on bottleneck-based fairness in [START_REF] Dolev | No justified complaints: On fair sharing of multiple resources[END_REF] and [START_REF] Gutman | Fair allocation without trade[END_REF] suggest the existence of a BMF allocation is far from obvious. The following proposition, proved in the appendix, establishes the existence of a BMF allocation. Proposition 3. A BMF allocation always exists.

Like PF, BMF meets all properties of §2.2 except strategyproofness. It is Pareto-efficient by definition and envyfree since, for any transaction i, there is some resource j such that ϕiaij is maximal over all transactions. The no justified complaints objective clearly implies BMF has the sharing-incentive property. It is both single-resource fair and single-bottleneck fair since all transactions attain the maximum allocation of the resource in question and this is necessarily equal to 1/n. It is scale-invariant since the definition involves the resource shares ϕiaij only.

It turns out that BMF is not necessarily unique. The following proposition, also proved in the appendix, shows however that BMF is unique for R = 2 resources. Proposition 4. The BMF allocation is unique for two resources.

That uniqueness does not extend to more than 2 resources is established by the following counter-example. Consider a 3 resource system with 3 transactions having requirement vectors (1, 1, 1), (1, 1/2, 3/4) and (1/2, 1, 3/4). Allocations ϕ (0) = (2/5, 2/5, 2/5) and ϕ (1) = (1/3, 4/9, 4/9) both satisfy the definition. In fact, allocations ϕ (x) = (2/5 -x/15, 2/5 + 2x/45, 2/5+2x/45) for 0 ≤ x ≤ 1 are all BMF. Note that the absence of uniqueness is not necessarily problematic since all the allocations may be considered satisfactory with respect to the considered properties.

The fact that BMF is not strategyproof follows on observing that BMF coincides with PF for n = 2 transactions, so that the counterexample of §2.4 applies to BMF as well. BMF and PF in fact coincide for any two homogeneous populations of transactions.

Proposition 5. BMF coincides with PF for two types of transactions.

Proof. We assume without loss of generality that R = 2 (see the proof of Proposition 2). Take n1 transactions with resource requirements a1 and n2 transactions with resource requirements a2. By scale invariance, we can assume that a11a22 = a12a21 (otherwise, there is actually a single type of transaction and each transaction gets a fraction 1/n of the most constraining resource).

Assume resource 1 is the single bottleneck. By singlebottleneck fairness, the allocation ϕ is the same under PF and BMF and given by ϕ1a11 = ϕ2a21 = 1/n. Since resource 2 is not saturated, we obtain

1 n n1 a12 a11 + n2 a22 a21 < 1. (3)
Similarly, resource 2 is the single bottleneck if and only if

1 n n1 a11 a12 + n2 a21 a22 < 1, (4)
in which case PF and BMF coincide. Now assume that neither (3) nor ( 4) hold. Then both resources are bottlenecks under both BMF and PF. We deduce that

n1ϕ1a11 + n2ϕ2a21 = 1, n1ϕ1a12 + n2ϕ2a22 = 1,
which has a unique solution whenever a11a22 = a12a21.

It is worth noting that the proof of the above proposition is based on the following three properties of BMF and PF only: scale-invariance, Pareto efficiency and single-bottleneck fairness. This means in particular that, for two types of transaction, there is no other allocation that satisfies these three properties. By the counterexample of §2.4, this allocation is not strategyproof, which shows that there is no allocation meeting all properties listed in §2.2. Any Pareto-efficient, scale-invariant allocation is either strategyproof (like DRF) or single-bottleneck fair (like PF and BMF).

ALGORITHMS

We discuss algorithms to realize DRF, PF and BMF, successively for the fluid model, for a compute cluster shared by multi-task jobs and for router or network resources shared by flows of packets.

Dominant resource fairness

Since DRF corresponds to max-min fair sharing with weights equal to the dominant resource requirements, the allocation can be computed through a water-filling algorithm [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF][START_REF] Parkes | Beyond dominant resource fairness: extensions, limitations, and indivisibilities[END_REF]: the ϕi are increased at rates inversely proportional to the dominant resource requirements maxj{aij} until some resource is fully used; transactions using that resource are frozen while rates of the others with non-zero requirements on non-saturated resources are further increased at their respective rates until a second resource is full; the process continues until all the ϕi are frozen. The complexity of this algorithm is of order O(Rn).

Ghodsi et al. [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF] show how the DRF allocation can be realized in practice for compute cluster resources. As resources are freed on task completion they are re-allocated preferentially to the most deprived job. This is the job with the smallest share on its dominant resource. Tasks are assigned when jobs arrive, if resources are available, or when other tasks end. If available resources are insufficient to accommodate a task of the most deprived job, allocations are frozen until a sufficient number of other tasks end or some other job takes over the most-deprived status. Note that we continue to assume resources are pooled though the assignment algorithm could be adapted to account for additional practical constraints such as assigning CPU and RAM on the same physical server, say [START_REF] Psomas | Beyond beyond dominant resource fairness : Indivisible resource allocation in clusters[END_REF], or meeting other compatibility constraints [START_REF] Ghodsi | Choosy: Max-min fair sharing for datacenter jobs with constraints[END_REF].

To share router resources between flows, we can apply the DRFQ algorithm defined by Ghodsi et al. [START_REF] Ghodsi | Multi-resource fair queueing for packet processing[END_REF]. To highlight parallels with similar algorithms defined below for PF and BMF, we adopt a slightly different specification of DRFQ.

DRFQ approximately realizes weighted max-min fairness by applying the start-time fair queuing (SFQ) algorithm at each resource [START_REF] Goyal | Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks[END_REF]. This algorithm serves waiting packets in increasing order of their virtual start time. The virtual start time S k ij of packet k of flow i at resource j is determined recursively,

S k ij = max Vj(u k ij ), S k-1 ij + max j {aij} , (5)
where u k ij is the packet arrival time at resource j and the virtual time functions Vj(t) of real time t are set equal to the largest start time at t of any packet to have begun service at that resource. Each resource needs to maintain a sorted list of virtual start times, yielding a complexity of O(log n) per packet arrival.

As long as each resource is aware of the weight to apply (i.e., the dominant resource requirement maxj{aij}), the scheduling can be applied independently at each resource, even when the resources are separated geographically as in the network application. There is no constraint on the order in which resources are used and processing can proceed in parallel, if possible, without compromising the DRF properties.

Note that the virtual time functions determine how the first packet of a burst is inserted into the schedule while the second term in the max operator of (5) ensures fairness between flows that are backlogged. DRFQ basically inherits the latency and fairness properties of SFQ and is satisfactory as long as packet processing times are small, as is usual.

Proportional fairness

The optimization problem defining PF is computationally expensive in general. An approximate solution can be obtained by the gradient descent algorithm applied iteratively to the Lagrange multipliers,

νj ← max νj + θ n i=1 ψiaij -1 , 0 , (6)
where θ > 0 is a sufficiently small step size and

ψi = 1 R j=1 aijνj , for i = 1, . . . , n.
The allocation is then given by ( 2). This approximate solution can be used in a practical taskbased algorithm for sharing a compute cluster. This consists in applying the same "most deprived job" approach from §3.1. Specifically, the most deprived job is that whose ratio of actual to ideal allocation is smallest.

An algorithm for packet-based PF can be derived on extending the analysis of Massoulié and Roberts for network bandwidth sharing [START_REF] Massoulié | Bandwidth sharing: Objectives and algorithms[END_REF]. This relies on an assumption that resources are used consecutively and not in parallel. Each flow maintains a fixed window of W packets. This window might be realized within a router by creating an ingress queue and only admitting packet k to any internal buffer when packet k -W has finished processing at all resources. Denote the number of flow i packets waiting or in service at resource j by Qij and let Qj = i Qij. We have the conservation equation,

W = R j=1 Qij. (7)
Assume the system attains a stable regime where the Qij are positive constants when resource j is a bottleneck, or zero otherwise. This corresponds to the fluid limit regime where W tends to infinity, as considered for instance by Schweitzer [START_REF] Schweitzer | Bottleneck determination in networks of queues[END_REF] and Walton [START_REF] Walton | Proportional fairness and its relationship with multi-class queueing networks[END_REF]. In practice, assuming constant packet sizes, it is sufficient that W ≥ R so that each flow is backlogged on some resource. It turns out that serving packets at rates proportional to Qij/aij yields the PF allocation.

We have,

n i=1 ϕiaij = 1 =⇒ Q kj Qij = ϕ k a kj ϕiaij
and summing over k yields Qij = ϕiaijQj. On substituting for Qij in [START_REF] Ghodsi | Choosy: Max-min fair sharing for datacenter jobs with constraints[END_REF] we derive,

1 ϕi = j aij Qj W
where Qj ≥ 0 and Qj > 0 if and only if i ϕiaij = 1. Comparison with [START_REF] Bonald | Enhanced cluster computing performance through proportional fairness[END_REF] shows that the variables Qj/W coincide with the Lagrange multipliers νj and, therefore, that ϕ is indeed the unique PF allocation.

To realize the required packet rates we can again adapt the SFQ algorithm. Start times S k ij are defined recursively and independently for each resource j,

S k ij = max Vj(u k ij ), S k-1 ij + aij/Qij , ( 8
)
where notation is as defined above in §3.1. Complexity is still O(log n). This algorithm is not entirely satisfactory. The assumption that resources are visited sequentially by each packet is restrictive for the software router application. Moreover, for the network application, it would be necessary to take account of non-zero propagation times between visits to successive resources. This case is considered in [START_REF] Massoulié | Bandwidth sharing: Objectives and algorithms[END_REF] where it is shown that, even with homogeneous resource requirements, the algorithm only realizes PF approximately if the window W is large compared to the bandwidth delay product, i.e., the product of ϕi and the round trip propagation time of flow i.

Bottleneck max fairness

For small systems, it is possible to determine a BMF allocation by testing the feasibility of all possible one-to-one mappings of transactions to potential bottlenecks. For a mapping to be feasible, it must be possible to find values ϕi satisfying (1) such that every resource j with at least one mapped transaction is a bottleneck and all transactions mapped to j have the maximum share of j. Fortunately, it is not necessary to apply this algorithm in any practical implementation, as discussed below.

The most deprived job approach can be adapted to realize BMF in a compute cluster. For every job i we note its rank at each resource j: jobs with the biggest allocation have rank 1, jobs of rank k for k > 1 have a smaller share than k -1 other jobs. The deprivation status of job i is its highest rank on a bottleneck resource. A resource is considered a bottleneck here if its residual capacity is less than the maximal requirement for that resource over all transactions. Tasks are launched preferentially for the job whose current status is furthest from 1. Each resource maintains a sorted list of n jobs, yielding a complexity of O(log n) per task arrival or departure.

For the router application, BMF can be realized by imposing local weighted max-min fairness at each resource with respective weights 1/aij. To demonstrate this, we again assume the existence of a steady state and extend arguments from [START_REF] Massoulié | Bandwidth sharing: Objectives and algorithms[END_REF]. We assume each flow i maintains a window of Wi packets and, to include the possibility of remotely located resources (as in the network application), we introduce the round trip propagation times Ti. The following conservation relations generalize [START_REF] Ghodsi | Choosy: Max-min fair sharing for datacenter jobs with constraints[END_REF],

Wi = ϕiTi + R j=1 Qij. (9)
Relation [START_REF] Gutman | Fair allocation without trade[END_REF] shows that for every flow i, as long as Wi is sufficiently large, there is at least one bottleneck resource j such that Qij > 0 (assuming constant packet sizes, it is in fact sufficient that Wi > ϕiTi + R to ensure that flow i is backlogged at some resource). Moreover, the weighted fair queuing scheduler at j ensures ϕiaij = max k (ϕ k a kj ), completing the BMF defining conditions. To realize BMF using SFQ, start times must be calculated as follows,

S k ij = max Vj(u k ij ), S k-1 ij + aij , (10)
where notation is again as defined above in §3.1.

Complexity is O(log n).

Note that this algorithm is much simpler than that of PF in not requiring knowledge of queue lengths or imposing the same window for all flows. Like DRFQ, it can be applied independently of whether the resources are visited in parallel or sequentially and it does not depend on propagation times beyond the requirement that Wi be big enough to maintain a positive queue at bottlenecks.

PERFORMANCE

While the sharing algorithms are defined above with respect to a fixed set of n transactions, their behavior can only be realistically appraised under dynamic demand where transactions occur over time, each bringing a finite amount of work to be accomplished. We propose a simple Markovian demand model and use it to compare the performance of DRF, PF and BMF.

Markovian demand model

We suppose transactions belong to one of K classes and transactions of class k arrive as a Poisson process of rate λ k . Class k transactions have requirement a k = (a k1 , . . . , a kR ) and bring a random amount of work with an exponential distribution with parameter µ k . This work corresponds to the job duration for the computer cluster application and to the flow size in bits for the network application, for instance.

The state vector n = (n1, . . . , nK ), giving the current number of transactions of each class in progress, is then a Markov process with component-k birth rate λ k and death rate φ k µ k , where φ = (n1ϕ1, . . . , nK ϕK ) denotes the perclass allocation vector. The Markovian model is adopted for the sake of simplicity. We expect, however, in view of the approximate insensitivity of fair resource sharing systems, that the comparative performance of DRF, PF and BMF will be similar under more accurate demand models (see [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF], for example, for a discussion on the insensitivity property in the context of bandwidth sharing).

Capacity constraints (1) can be written

K k=1 φ k a kj ≤ 1, (11)
for j = 1, . . . , R. When the allocation φ is DRF or PF, known results for bandwidth sharing in networks (e.g., [START_REF] Ye | Stability of data networks under an optimization-based bandwidth allocation[END_REF]) allow us to conclude that the above process is stable as long as loads ρ k = λ k /µ k satisfy the following inequalities,

K k=1 ρ k a kj < 1, (12)
for j = 1, . . . , R. This follows for DRF since the objective is just a particular weighted max-min allocation. The BMF allocation is not included in the class of allocations considered by Ye [START_REF] Ye | Stability of data networks under an optimization-based bandwidth allocation[END_REF] and it proves difficult to establish the stability condition for a general system. The following theorem, proved in the appendix, shows that condition ( 12) is sufficient for a system limited to two resources with homogeneous mean service requirements, µ1 = . . . = µK . We believe that, like DRF and PF, this result in fact extends to any number of resources and is insensitive to the distributions of service requirement beyond the means.

Theorem 1. Conditions (12) are sufficient to ensure the stability of BMF in the case of two resources with homogeneous mean service requirements.

In the following we assume the system is stable and has a stationary distribution π( n) from which we can compute performance measures like expected completion times. We compare algorithm performance via the mean service rate γ k , defined as the ratio of the mean work 1/µ k to the mean completion time. Using Little's law, we find γ k = ρ k /E(n k ) where E(n k ) is the mean number of class k transactions in progress. Observe that, if there are only class-k transactions with normalized dominant resource requirement, that is maxj a kj = 1, the model reduces to a processor-sharing queue with arrival rate λ k and service rate µ k . In particular, E(n k ) = ρ k /(1 -ρ k ) and γ k = 1 -ρ k : the relative service rate decreases linearly with the system load.

Performance of the fluid model

We illustrate the relative performance of DRF, PF and BMF using a numerical example. Two resources are shared by 3 classes of transaction with requirement vectors a1 = (.1, 1), a2 = (1, .1), a3 = (1, 1). The figures plot realized service rates γ k against the load of the heaviest loaded resource, argmax j=1,2 K k=1 ρ k a kj . Figure 1 corresponds to balanced load ρ1 = ρ2 = ρ3 and shows performance is similar for all three allocations. BMF is very close to PF while both are somewhat better than DRF, especially at high load. The difference in performance is accentuated under unbalanced load, as illustrated in Figure 2 for the case ρ1 = 4ρ2 = 4ρ3. In this scenario resource 1 has less than half the load of resource 2. The plots show that strict fairness imposed by DRF prevents class 2 transactions from fully exploiting this. The service rates of PF and BMF are roughly equivalent, both yielding a better efficiency-fairness tradeoff with a significant gain in γ2 for negligible reductions in γ1, γ3.

The generality of these results for DRF and PF was discussed in [START_REF] Bonald | Enhanced cluster computing performance through proportional fairness[END_REF] where light and heavy load behavior was determined for two resources and two transaction classes. It is noteworthy that the performance advantage of PF for unbalanced load arises due to the fact that DRF sacrifices singlebottleneck fairness in the interest of strategyproofness.

Strategyproofness

The strategyproof property in §2.2 relates to a static population of transactions. We demonstrate in this subsection that the absence of this property for PF and BMF is hardly a disadvantage in dynamic traffic. Even if some transaction knows some statistics about the resource requirements of competing transactions, it does not know how many transactions are active or how this number will evolve and thus can hardly define a consistent strategy to improve its service rate by lying about its resource requirements. Consider the potential for gaming when some test transaction competes with a homogeneous population of other transactions evolving according to the model of §4.1. Recall from Proposition 5 that PF and BMF allocations are identical for this case (since only two resources can be limiting).

From Proposition 2, the greatest gain for two resources and two transactions is obtained for a1 = (0, 1) and a2 = (1, 1/2) with transaction 1 falsely declaring a 1 = (2/3, 1). Suppose first that transaction 1 truly declares a1 = (0, 1). The service rate of transaction 1 is then φ1 = 1 for n2 = 0 and φ1 = 1/2 otherwise, while φ2 = 1 for any n2. In particular, n2 has a geometric distribution with parameter ρ2. If transaction 1 is infinitesimally small, n2 remains constant during its service. We deduce that the mean duration of transaction 1 is proportional to 1 -ρ2 + 2ρ2 for an infinitesimally small size, yielding

γ1 = 1 1 + ρ2 .
If transaction 1 is infinitely large, the service rates average and we get

γ1 = 1 -ρ2 + ρ2 2 = 1 - ρ2 2 .
Now assume transaction 1 claims requirement a 1 = (2/3, 1). The service rate of transaction 1 is then φ1 = 1 for n1 = 0 and φ1 = 3/(2(n2 + 1)) otherwise, while φ2 = n2/(n2 + 1) for any n2. If transaction 1 is infinitesimally small then n2 still has a geometric distribution with parameter ρ2 and the mean duration of transaction 1 is proportional to

1 -ρ2 + 2 3 n 2 ≥1 (n2 + 1)(1 -ρ2)ρ n 2 2 , yielding γ1 = 1 -ρ2 1 -2 3 ρ2 + ρ 2 2 3
.

If transaction 1 is infinitely large, the probability of state (1, n2) is proportional to (n2 + 1)ρ n 2 2 so that γ1 = (1 -ρ2) 2 (1 + 3 2 n 2 ≥1 ρ n 2 2 ) = (1 -ρ2)(1 + ρ2 2 ),
which is less that the original service rate for any load ρ2. Figure 3(a) shows how the service rate of transaction 1 behaves with the false declaration a 1 = (2/3, 1) as a function of ρ2 when this transaction occurs at an arbitrary instant and is infinitesimally small. The maximum gain in this configuration is only 10% compared to the 50% gain realized under static load. Moreover, this gain is realized only under a very particular configuration and rapidly disappears as the worst case conditions are relaxed. For example, Figure 3(b) confirms that if transaction 1 is not small but very large, there is no gain from the false declaration at any load.

The fact that transaction 1's competitors all have the profile (1,1/2) further exaggerates the scope for illicit gain. Transaction 1 can take no additional rate from any concurrent transactions with the same dominant resource (i.e., having a profile (a11, 1) for a11 ≤ 1). In any mixed demand scenario, it is clear that the maximum gain is considerably less than 10%. Moreover, we note from the results of Figure 3 that the false requirements only ever yield a marginal improvement in the smallest completion times. Longer completion times, because load is heavy, as on the right of Fig. 3(a), or because the transaction is intrinsically long, as in Fig. 3(b), will be increased and not decreased.

The above clearly does not show that PF and BMF are strategyproof. Indeed they are not in case of static demand. However, the results do suggest it is rather implausible that any transaction can define a winning strategy when demand is dynamic.

Task-based allocations

While the fluid models analyzed above are useful in appraising the relative merits of alternative fairness objectives, it is necessary in practice to account for the fact that jobs are not infinitely divisible. In this section we relax this assumption. We compare the performance of task-based versions of DRF, PF and BMF through the results of simulation experiments. We follow the proposal in [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF] in seeking to realize the fairness objective by preferentially launching tasks of the most deprived job with respect to the objective fairness criterion. The respective criteria for defining deprivation status were presented in §3.

Figure 4 plots the results of simulations showing how the algorithms perform in a particular configuration. Two resources (e.g., CPU and RAM) are shared by jobs of three classes with profiles (.1,1), (1,.1) and (1,1) and demand is unbalanced with ρ1 = 4ρ2 = 4ρ3. This is the same data used for the fluid model in Figure 2. The present results show the service rate is much smaller for the task-based allocation. This is due to the finite task size which invalidates the infinite divisibility assumption of the fluid model.

We have assumed here that each job has 500 tasks to run, each having an independent exponential duration, and that the capacities of CPU and RAM are 100. For very low load, each job is alone with high probability and 100 of its tasks are processed in parallel while there remain at least 100 to run. From then on, the task completion rate decreases with the number of remaining tasks in progress from 99 to 1. It is possible in this case to compute the maximum service rate of 0.54 [START_REF] Bonald | Enhanced cluster computing performance through proportional fairness[END_REF]. The discrepancy with respect to the fluid model is smaller when the task duration is less variable or when the number of tasks to run is much greater than the resource capacity.

The figure shows that PF and BMF still significantly outperform DRF for the class of jobs whose dominant resource is the least loaded (class 2 and resource 1 in this case). The algorithm for BMF is rather more effective than that of PF and yields greater service rates whereas the fluid results were virtually the same.

Packet-based allocations

In this section we evaluate by simulation the effectiveness of the SFQ-based algorithms defined in §3 for router resource sharing. The simulations assume two resources (e.g., CPU and bandwidth) are used successively by flow packets. The number of packets in each flow has a geometric distribution of mean 20000. For all algorithms we set the window W to 30 for all flows. We have verified that these parameter choices do not critically impact the presented results.

Service rates are shown in Figure 5 for the same unbalanced load scenario used in the previous section. Crosses are results of packet-based simulations for 10 5 flow arrivals and lines are the fluid model results from Figure 2. The results show that all three packet-based algorithms closely approximate the service rates of the ideal allocations, confirming the performance advantage of PF and BMF over DRF.

From a practical point of view, BMF is preferable to PF in that the algorithm is simpler to implement and more robust. Like DRF, BMF sharing is also realized by the same algorithm when some resources can be used simultaneously and not sequentially. Crucially for the network application, BMF is also applicable when propagation times are non-zero.

RELATED WORK

DRF [START_REF] Ghodsi | Dominant resource fairness: Fair allocation of multiple resource types[END_REF] and "no justified complaints" [START_REF] Dolev | No justified complaints: On fair sharing of multiple resources[END_REF] were placed in a more general economics framework in the work of Gutman and Nisan [START_REF] Gutman | Fair allocation without trade[END_REF]. Joe-Wang et al. also generalized DRF by introducing two families of allocations that allow a controlled tradeoff between efficiency and fairness [START_REF] Joe-Wong | Multi-resource allocation: Fairness-efficiency tradeoffs in a unifying framework[END_REF]. However, all these objectives are evaluated assuming static demand. It would be necessary to reappraise the impact of such generalizations under the more realistic assumption of dynamic, stochastic demand.

The "serve the most deprived job" approach introduced in [6] proves very versatile. It is used by Zeldes and Feitelson [24] to implement bottleneck-based fairness and by Ghodsi and co-authors [START_REF] Ghodsi | Choosy: Max-min fair sharing for datacenter jobs with constraints[END_REF] to account for compatibility constraints in task placement. Our proposed implementations of PF and BMF for sharing cluster resources are further illustrations of this versatility. It would be not difficult to account for possible placement constraints in these implementations.

The packet-based algorithms designed by Ghodsi et al. [START_REF] Ghodsi | Multi-resource fair queueing for packet processing[END_REF] to realize DRFQ for shared router resources are based on start-time fair queuing. Wang and co-authors have proposed alternative realizations that adapt Deficit Round Robin [START_REF] Shreedhar | Efficient fair queueing using deficit round robin[END_REF] to the multi-resource context [START_REF] Wang | Multi-resource round robin: A low complexity packet scheduler with dominant resource fairness[END_REF]. Our implementations of PF and BMF rely on SFQ though it would be straightforward to substitute alternative fair queuing mechanisms.

The need to evaluate the performance of resource sharing objectives under dynamic demand is still not widely recognized. The paper by Massoulié and Roberts [START_REF] Massoulié | Bandwidth sharing and admission control for elastic traffic[END_REF] was perhaps the first to note the importance of this while some of the most significant subsequent findings are summarized by Bonald et al. [START_REF] Bonald | A queueing analysis of max-min fairness, proportional fairness and balanced fairness[END_REF]. Our earlier paper [START_REF] Bonald | Enhanced cluster computing performance through proportional fairness[END_REF] and the present work extend this analysis to the domain of multi-resource sharing.

The stability of network bandwidth sharing under various allocation objectives, with and without Markovian demand assumptions, is discussed by Walton and Mandjes [START_REF] Walton | A stability conjecture on bandwidth sharing networks[END_REF]. Their paper surveys the literature on the stability question and illustrates its inherent difficulty. While existing results can be applied to prove the stability of DRF and PF, this is not the case for BMF.

CONCLUSIONS

Multi-resource sharing for efficiency and fairness is an old issue in networking with challenging new variants occurring in the domains of cluster computing and software routers. Recent prominent publications have led to the emergence of DRF and its apparent acceptance as the preferred sharing objective. DRF is implemented in the Hadoop Next Generation Fair Scheduler, for instance.

We have argued in this paper that this popularity is misplaced since alternative objectives like PF display a better efficiency-fairness tradeoff. This result is revealed on considering the completion time performance of alternative objectives under the realistic and crucial assumption that demand is dynamic: jobs and flows occur over time and their completion times depend critically on the implemented resource sharing objective.

We have proposed BMF as a pragmatic alternative to PF. It has similar performance and can be realized more simply, especially when sharing router and network resources between flows. It is clearly the most practical objective for a network integrating radio access and wired backhaul. Independent schedulers simply share their own resource equitably. BMF thus generalizes network-wide max-min fairness that is known to be realized by fair schedulers acting independently on each link [START_REF] Hahne | Round-robin scheduling for max-min fairness in data networks. Selected Areas in Communications[END_REF].

Concerns about the vulnerability of objectives like PF and BMF to malicious gaming have been shown to be largely unfounded. While users can manipulate allocations by falsely boosting their declared requirement of non-dominant resources, their gain depends critically on knowing the requirements of competitors. Such knowledge is hardly conceivable in the context of highly dynamic populations of active transactions occurring in a realistic model of demand. Moreover, we have shown that the falsification is counter-productive in most cases, especially for large transactions.

While BMF is relatively straightforward to implement, it remains difficult to completely characterize its essential properties. We have proved that the usual per-resource stability conditions are sufficient in a system limited to two resource types. However, the extension of this result to more than two resources is a challenging open problem. and α2 = ϕ k+1 a k+1,2 = . . . = ϕnan2 ≥ ϕ k a k2 . Without loss of generality, we can assume that α1 > ϕ k+1 a k+1,1 (we take index k + 1 instead of k otherwise). We have

kα1 + S2(n -k)α2 = 1, S1(k)α1 + (n -k)α2 = 1, where S1(k) = k i=1 ai2 ai1 and S2(k) = n i=n-k+1 ai1 ai2 . Now S1(k) k S2(n -k) n -k ≤ a k,2 a k,1 × a k+1,1 a k+1,2 ≤ 1,
where one of the last two inequalities is strict in view of [START_REF] Parkes | Beyond dominant resource fairness: extensions, limitations, and indivisibilities[END_REF]. Then

S1(k)S2(n -k) < k(n -k) and α1 = n -k -S2(n -k) k(n -k) -S1(k)S2(n -k) , α2 = k -S1(k) k(n -k) -S1(k)S2(n -k) .
In particular, S1(k) < k and S2(n -k) < n -k.

It remains to prove the uniqueness of the index k. Define δ k = α2/α1. Note that a k,2 a k,1 ≤ δ k < a k+1,2 a k+1,1 .

Let P k be the property that S1(k) < k and S2(n -k) < n -k. In view of ( 15), there exists some index i1 such that ai 1 ,2 ai 1 ,1 ≤ 1 < ai 1 +1,2 ai 1 +1,1 .

If P k holds and k < i1 then P k+1 holds; similarly if P k holds and k > i1 + 1 then P k-1 holds. Thus the set of indices k such that P k holds is of the form {k1, . . . , k2} with k1 ≤ k2. For all k = k1 + 1, . . . , k2,

δ k ≥ a k2 a k1 , ⇐⇒ k -S1(k) ≥ a k2 a k1 (n -k -S2(n -k)), ⇐⇒ k -S1(k -1) ≥ a k2 a k1 (n -k + 1 -S2(n -k)), ⇐⇒ k -1 -S1(k -1) ≥ a k2 a k1 (n -k + 1 -S2(n -k + 1)), ⇐⇒ δ k-1 ≥ a k2 a k1 ,
where we have used the fact that S1(k) = S1(k -1) + a k2 /a k1 and S2(n-k) = S2(n-k+1)-a k1 /a k2 . Now assume that k satisfies [START_REF] Schweitzer | Bottleneck determination in networks of queues[END_REF]. If k > k1 then δ k ≥ a k2 /a k1 implies δ k-1 ≥ a k2 /a k1 ≥ a k-1,2 /a k-1,1 and, by induction, δ l ≥ a l+1,2 /a l+1,1 for all l = k1, . . . , k -1.

Similarly, if k < k2 then δ k < a k+1,2 /a k+1,1 implies δ k+1 < a k+1,2 /a k+1,1 ≤ a k+2,2 /a k+2,1 and, by induction, δ l < a l,2 /a l,1 for all l = k +1, . . . , k2. We conclude that there is at most one index k such that P k holds and ( 17) is satisfied. We now relax the assumption that aij > 0 for all i, j. We still number the transactions in increasing order of ai2/ai1, with ai2/ai1 = +∞ if ai1 = 0. Again, we consider three cases:

• Case 1 n n i=1 ai2/ai1 ≤ 1. This implies that ai1 > 0 for all i = 1, . . . , n and we prove in the same way that the allocation ϕ such that (ϕ1a11, . . . , ϕnan1) = (1/n, . . . , 1/n) is the unique BMF allocation.

• Case 1 n n i=1 ai1/ai2 ≤ 1. This implies that ai2 > 0 for all i = 1, . . . , n and the allocation ϕ such that (ϕ1a12, . . . , ϕnan2) = (1/n, . . . , 1/n) is the unique BMF allocation.

• Case 1 n n i=1 ai2/ai1 > 1 and 1 n n i=1 ai1/ai2 > 1. By the bottleneck-max property, there exists some index k < n such that α1 = ϕ1a11 = . . . = ϕ k a k1 ≥ ϕ k+1 a k+1,1 and α2 = ϕ k+1 a k+1,2 = . . . = ϕnan2 ≥ ϕ k a k2 . Observe in particular that, by the sharing-incentive property, ai1 > 0 for all i ≤ k and ai2 > 0 for all i > k. The rest of the proof is identical.

Theorem 1 -Stability of BMF

Assume that max(a k1 , a k2 ) = 1 for all k; this assumption is not restrictive by scale invariance. We know by the proof of Proposition 4 that resource -n < 0.

In particular, n.a2 ≥ na1 implies that resource 2 is a bottleneck; similarly, n.a1 ≥ na2 implies that resource 1 is a bottleneck. Let V be the function defined by V (x) = max(x.a1, x.a2) for all x ∈ R K + . Observe that the sets { n : V ( n) ≤ m} are finite for any m > 0 so that V is a Lyapunov function for the Markov process n(t). The drift is given by

∆V ( n) = K k=1 λ k (V ( n + e k ) -V ( n)) + k:n k >0 µφ k ( n)(V ( n -e k ) -V ( n)),
where e k denotes the unit vector on component k and µ = µ1 = . . . = µ k . For any state n such that n.(a1 -a2) ≥ 0 and ( n±e k ).(a1-a2) ≥ 0 for all k, resource 1 is a bottleneck both in state n and after any jump from state n. In particular, V ( n) = n.a1 and

∆V ( n) = µ K k=1 ρ k a k1 -1 ≤ -µδ,
where δ = 1 -maxj=1,2 K k=1 ρ k a kj is a positive constant. Similarly, in any state n such that n.(a2 -a1) ≥ 0 and ( n±e k ).(a2-a1) ≥ 0 for all k, resource 2 is a bottleneck both in state n and after any jump from state n and ∆V ( n) ≤ -µδ. Since V is a continuous, piecewise linear function and the transition rates of the Markov process n(t) are bounded, there exists some smoothened version W of V , which is a Lyapunov function for n(t) and such that ∆W ( n) ≤ -µδ/2 outside a compact set [START_REF] Veciana | Stability and performance analysis of networks supporting elastic services[END_REF]. By Foster's criterion, the Markov process n(t) is ergodic.

Figure 1 :

 1 Figure 1: Service rates γ k against resource load for BMF and DRF with balanced load: a1 = (.1, 1), a2 = (1, .1), a3 = (1, 1); ρ1 = ρ2 = ρ3; γ1 = γ2 > γ3.

Figure 2 :

 2 Figure 2: Service rates γ k against resource 2 load for BMF and DRF with unbalanced load: a1 = (.1, 1), a2 = (1, .1), a3 = (1, 1); ρ1 = 4ρ2 = 4ρ3; γ2 > γ1 > γ3.

Figure 3 :

 3 Figure 3: Service rate of a test transaction against class 2 load: the test transaction requires (0,1) but falsely declares (2/3,1) and competes with a dynamic population of transactions of profile (1,1/2).

Figure 4 :

 4 Figure 4: Cluster sharing: service rates γ k against resource 2 load for unbalanced load: a1 = (.1, 1), a2 = (1, .1), a3 = (1, 1); ρ1 = 4ρ2 = 4ρ3.

Figure 5 :

 5 Figure 5: Router sharing: service rates γ k against resource 2 load for unbalanced load: a1 = (.1, 1), a2 = (1, .1), a3 = (1, 1); ρ1 = 4ρ2 = 4ρ3.

  1 is the single bottleneck if and only if a k1 > 0 for all k and K k=1 n k

									a k2 a k1 < n, which implies
	n.a2 < n.a1 since
	n.(a2 -a1) =	K k=1	n k	a k2 -a k1 a k1	+	K k=1	n k	a k2 -a k1 a k1	(a k1 -1),
	≤	K k=1	n k	a k2 a k1

APPENDIX Proposition 3 -Existence of BMF

It is convenient here to abandon the normalization of resource capacities and define the vector C = (C1, ..., CR) associated with capacity constraints n i=1 ϕiaij ≤ Cj, for j = 1, . . . , R.

We prove by induction on n that there exists a BMF allocation ϕ which is a continuous function of the vector C. For n = 1 transaction, we take ϕ1 = minj:a 1j >0 Cj/a1j, which is a continuous function of C. Now assume that the property holds for n -1 transactions, for some n ≥ 2. For any nonnegative θ < minj:a 1j >0 Cj/a1j, there exists a bottleneckmax fair allocation ϕ (θ) , which is a continuous function of θ, for the system restricted to transactions 2, . . . , n -1 and the capacity vector C (θ) = C -θa1. For any sufficiently small θ, we have, for all j = 1, . . . , R,

i aij}. [START_REF] Massoulié | Bandwidth sharing and admission control for elastic traffic[END_REF] Let θ1 be the largest number such that this property is satisfied for all θ < θ1. Observe that, by the continuity of ϕ (θ) in θ, this property is violated for θ = θ1. In particular, there exists some resource j1 such that

Now define ϕ1 = θ1 and ϕi = ϕ

In view of ( 14), transaction 1 gets the maximum share of bottleneck resource j1 under allocation ϕ. Now take any increasing sequence θ(1), θ(2), . . . tending to θ1 such that for each transaction i = 2, . . . , n, there is some bottleneck resource ji in the system restricted to transactions 2, . . . , n whose transaction-i share ϕ (θ) i aij i is maximum over all transactions 2, . . . , n, for all θ = θ(1), θ(2), . . . Such a sequence exists because ϕ (θ) is bottleneck-max fair and there is a finite number of resources. It follows from ( 13) that θa1j i < ϕ (θ) i aij i for all transactions i = 2, . . . , n and all θ = θ(1), θ(2), . . .. Taking the limit, it follows from the continuity of ϕ (θ) that each transaction i gets the maximum share of resource ji under allocation ϕ: the allocation is BMF. It remains to prove the continuity of the function ϕ in C, which follows from that of ϕ (θ) in θ and that of θ1 in C. 2

Proposition 4 -Uniqueness of BMF

We first assume that aij > 0 for all i, j and number the transactions in increasing order of ai2/ai1. Observe that ϕ1a11 ≥ ϕ2a21 ≥ . . . ≥ ϕnan1 (if ϕ1a11 < ϕ2a21 for instance then ϕ1a12 ≤ ϕ1a11 × a22/a21 < ϕ2a22 so that the bottleneck-max property is violated for transaction 1). Similarly, ϕ1a12 ≤ ϕ2a22 ≤ . . . ≤ ϕnan2. Without loss of generality, we can assume that n ≥ 2 and

Otherwise, one of the two resources is not limiting and the allocation is unique by single-bottleneck fairness. We consider three cases:

The allocation ϕ such that (ϕ1a11, . . . , ϕnan1) = (1/n, . . . , 1/n) is BMF. Assume there is another BMF allocation, say ϕ = ϕ. We have

Since ϕ = ϕ, ϕ 1 a11 > 1/n > ϕ n an1. Let k be the maximum index i such that ϕ i ai1 > 1/n and define

Observe that

where one of the last two inequalities is strict in view of [START_REF] Parkes | Beyond dominant resource fairness: extensions, limitations, and indivisibilities[END_REF]. Using ( 16), we get

By single-bottleneck fairness, this implies ϕ = ϕ, a contradiction.

• Case 1 n n i=1 ai1/ai2 ≤ 1. We prove similarly that the BMF allocation is unique.

• Case 1 n n i=1 ai2/ai1 > 1 and 1 n n i=1 ai1/ai2 > 1. By the bottleneck-max property, there exists some index k < n such that α1 = ϕ1a11 = . . . = ϕ k a k1 ≥ ϕ k+1 a k+1,1