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