3. 1. uncoordinated congestion control
Denote by λi the total rate that user i obtains from all its
connections. In the case of uncoordinated congestion
control, we can show that the worst-case rate allocation,
min λi decreases like b2 log(log N)/log N as N increases.
This is to be compared with the worst-case rate allocation
that one gets when b = 1, that is when a single path is used:
from classical balls and bins models, 16 this also decreases
as log(log(N) )/log(N) as N increases. It should come as no
surprise that using more than two paths exhibits the same
asymptotic performance as using only one path; there is
no potential for balancing load within the network when
all connections operate independent of each other. A formal statement and proof of this result can be found in Key
et al. 11
3. 2. coordinated congestion control
Here we assume as before that there are aN users, each
selecting b resources at random, from a collection of N available resources. Denote by λij the rate that user i obtains from
resource j, and let R(i ) denote the set of resources that user
i accesses. In contrast with the previous situation, we now
assume that the rates λij are chosen to maximize:
for some concave utility function U.
Theorem 1. Assume there are N resources, and aN users each
connecting to b resources selected at random. Denote by {λ*i }
the optimal allocations that result. Then there exists x > 0, that
depends only on a and b, such that:
The style of the proof has wide applicability and we outline
it here: first, an application of Hall’s celebrated marriage
theorem shows that the minimum allocation will be at least
x provided that any set of users (of size n say) connect to
at least x times as many servers (nx servers). If this condition is satisfied, the allocation (λ*i ) will exceed x; hence it is
sufficient to ensure that Hall’s condition is met with high
probability for all nonempty subsets of 1, . . . , aN. Using the
binomial theorem and the union bound yields an upper
bound on the probability the condition fails to hold, and
then Stirling’s approximation is used to approximate this
bound.
This result says that the worst-case rate allocation is
bounded away from zero as N tends to infinity, i.e., it is
O( 1) in the number of resources N. Thus coordinated control exhibits significantly better load balancing properties
than does uncoordinated control. It is also interesting to
compare this result to the result quoted by Mitzenmacher
et al., 16 which says that if users arrive in some random
order, and choose among their b candidate resources one
with the lowest load, then the worst-case rate scales like 1/
log(log(N) ), which unlike the allocation under coordinated
control, goes to zero as N increases. The difference between
the two schemes is that in Mitzenmacher’s scheme a choice
has to be made immediately at arrival, which cannot be
changed afterward, whereas a coordinated controller
actively and adaptively balances load over the b paths reacting to changes that may occur to the loads on the resources.
4. a Path seLection Game
In this section we address the following question. Suppose
that each session is restricted to using exactly b paths each,
taken from a much larger set of possible paths: What is the
effect of allowing each user to choose its b paths so as to
maximize the benefit that it receives? To answer this question, we study a path selection game. Here each session is a
player that greedily searches for throughput-optimal paths.
We characterize the equilibrium allocations that ensue. We
show that the same equilibria arise with coordinated congestion control and uncoordinated congestion control provided that the latter does not introduce RTT biases on the
different paths. Moreover, these equilibria correspond to
the optimal set of rates that solve problems ( 2) and ( 6), i.e.,
achieve welfare maximization. We shall use the models and
notation of Section 2.
We shall restrict attention to when Ns is large, so that a
change of paths by an individual player (session) does not
significantly change the network performance. In game
theory terms we are only considering non-atomic games.
4. 1. coordinated congestion control
For coordinated control, we use the model of Section 2, where
the number of sessions Ns is fixed for all s, and introduce the
following notion of a Nash equilibrium.
Definition 1. The nonnegative variables Nc, c ∈ C(s), s ∈ S, are a
Nash equilibrium for the coordinated congestion control allocation if they satisfy the constraints ∑c Nc = Ns, and, moreover, for
all s ∈ S, all c ∈ C(s), if Nc > 0, then the corresponding coordinated
rate allocations satisfy
In other words, for each session (player), weight is only given
to sets c that maximize the throughput for s. ◊
