Theorem 2. At a Nash equilibrium as in Definition 1, the path
allocations λr solve the welfare maximization problem ( 4).
The proof follows since at a Nash equilibrium, type s players only use minimum “cost” paths, which can be shown to
coincide with the Kuhn–Tucker conditions of ( 4). This result
says that a selfish choice of path sets by end-users results in
a solution that is socially optimal.
4. 2. uncoordinated control
We introduce the following notion of Nash equilibrium.
Definition 2. The collection of per path connection numbers Nr
is a Nash equilibrium for selfish throughput maximization if it
satisfies ∑r Nr = Ns, and furthermore, the allocations ( 6) are such
that for all s ∈ S, all r ∈ R(s), if Nr > 0, then
◊
The intuition for this definition is as follows: any class s
session maintains a connection along path r only if it cannot
find an alternative path r′ along which the default congestion control mechanism would allocate a larger rate.
We then have the following result, whose proof is similar
to that of Theorem 2.
Theorem 3. Assume that for each s ∈ S, there is a class utility
function Us such that Ur(x) ≡ Us(x/b) for all r ∈ R(s). Then for a
Nash equilibrium (Nr), the corresponding rate allocations (λr)
solve the general optimization problem ( 4).
To summarize: if (i) the utility functions associated with
the congestion control mechanism are path-independent,
(ii) users agree to concurrently use a fixed number b of paths,
and (iii) they manage to find throughput-optimal paths, that
is they achieve a Nash equilibrium, then at the macroscopic
level, the per-class allocations solve the coordinated optimization problem ( 4).
It is well known that the bandwidth shares achieved
by TCP Reno are affected by the path round trip times.
Thus the underlying utility functions are necessarily path
dependent and the above result does not apply as (i) fails to
hold. As a consequence “bad” Nash equilibrium can exist.
Indeed, a specific example is given in Key et al. 11 where
the preference of TCP for “short-thin links” over “
fat-long-links” gives rise to a Nash equilibrium where the throughput is half of what could be achieved. If (ii) is relaxed,
different uses have different “market power,” where those
with larger bs gain a large share, thus also creating “bad”
Nash equilibria in general.
5. muLtiPath RoutinG With RanDom Path
ReseLection
In the previous section we explored the effect of allow-
ing users to greedily select their set of paths (b in num-
ber) out of the set of all possible paths that are available to
them. In this section we focus on two questions. The first
regards how many paths, bs, to allow each class s user so as
to enhance its performance and that of the system. We estab-
lish a monotonicity result for coordinated control in order
to address this question. The second question regards how
to manage the overhead that may ensue due to the need for
a user to balance load actively over a large number of paths.
Possibly surprisingly, we will show that it suffices for a user
to maintain a small set of paths, say two (b = 2), provided that
it repeatedly selects new paths at random and replaces the
old paths with these paths when the latter provide higher
throughput. It is interesting to point out that Bit Torrent uses
a strategy much like this where it “unchokes” a peer (tries out
a new peer) and replaces the lowest performing of its existing
four connections with this new connection if the latter exhib-
its higher throughput.
5. 1. coordinated control
We begin by addressing the first question, namely how many
paths are needed. Consider a network G that supports a set
of flow classes S with populations {Ns}, and utility functions
{Us}. Let {R(s)} and {R′(s)} be two collections of paths for S
that satisfy R(s) R′(s) for s ∈ S and suppose that each session applies coordinated control over these paths. Then for
the problem ( 4)
and hence performance increases when the path sets
increase, with performance measured by the optimal welfare
under the capacity constraints. This follows from the fact
that a solution honoring the constraints on path-sets {R}
remains a feasible solution when the set of paths increases.
Remark 1. Although we have not shown strict inequality, it
is easy to construct examples where aggregate utility strictly
increases as more and more paths are provided.
The above result suggests that we would like to provide each
user with as large a set of paths possible to perform active
load balancing on. However, this comes with the overhead of
having to maintain these paths. We examine this issue next
by considering a simple policy where a session is given a set
of possible paths to draw from, say R(s) for a class s session,
and the policy allows the session to actively use a small subset of these paths, say two of them, while at the same time
constantly trying out new paths and replacing poorly performing paths in the old set with better performing paths in
the new set. More specifically we consider the following path
selection mechanism. Assume a user is using path set c. This
user is offered a new path set c′ at some fixed rate Acc′. This
new path set is accepted under the condition that the user
receives a higher aggregate rate than it was receiving under
c. This process then repeats.
We use the model of Section 2, where the class s users, Ns
in number, are divided according to the set of paths they are