currently using, Nc(t) denoting the number of class s-users actively using paths in c  R(s) at time t. Class s users actively using the set c of paths consider replacing their path set c with path set c′ according to a Poisson process with intensity Acc′. We shall assume that |c| = |c′| = b, i.e., the number of paths in an active set is fixed at b. Finally, assume that for each class s, any r ∈ R(s), any given set c ∈ C(s), there is some c′ such that r ∈ c′ and Acc′ is positive (recall that C(s) is defined as the collection of size b subsets of R(s) ). This assumption states that all paths available to a class s session should be tried no matter what set of initial paths is given to that session.

We also have to concern ourselves with the sending rates of the different users as path reselection proceeds over time. Let λc(t) denote the data transfer rate for a user actively using path set c, λc(t) = ∑r∈c λc,r(t) where λc,r(t) is the sending rate along path r at time t. We have described in Key et al. 11 a dynamic process where the vectors {Nc(t), λc,r(t)} change over time. This process is stochastic in nature and consequently difficult to model. However, if we assume that the population of users in each class is large, which is reasonable for the Internet, then we can model this process over time by a set of ordinary differential equations, representing the path reselection and rate adaptation dynamics of users over their active path sets. Under the condition that the utility functions and penalty functions are well behaved, we can show that Nc(t) converges to a limit Nc and λcr(t) converges to λcr as t tends to infinity. Remarkably, we can show that these limits are the maximizers of subject to ∑c∈C(s) Nc = Ns. In other words, this resampling process allows the system to converge to a state where the proportion of class s sessions using active path set c ∈ R(s) and the aggregate rates at which they use these paths maximize the aggregate sum of utilities. This is more precisely stated in the following theorem.

Theorem 4. Assume that the utility functions Us and the penalty function Γ are continuously differentiable on their domain, that the former are strictly concave increasing, and the latter convex increasing. Assume further that U′ s (x) → 0 as x → ∞. Then (Nc, λc,r) converges to the set of maximizers of the welfare function ( 10) under the constraints ∑c∈C(s) Nc = Ns. The corresponding equilibrium rates (λr) are solutions of the coordinated welfare maximization problem ( 2).

The proof proceeds by showing that trajectories of the limiting ordinary differential equation are bounded, that welfare increases over time, and then using Lasalle’s invariance theorem to prove that the limiting points of these dynamics coincide with equilibrium points of the ordinary differential equation; showing that the equilibrium points coincide with the maximum of ( 10) completes the proof.

maximization on the part of a user conforms exactly to the user trying to maximize its rate through the path reselection process. Thus, this path reselection policy is easy to implement: at random times the session initiates data transfer using the coordinated rate controller over a new set of paths and measures the achieved throughput, dropping either the old path set or new path set depending on which achieves lower throughput. This equivalence is a consequence of the assumption that the utility U is strictly concave and continuously differentiable.

5. 2. uncoordinated congestion control

As one might expect by now, the story is not as clean in the case of uncoordinated control, and no monotonicity result exists. Indeed, for a symmetric triangle network described in Key et al., 11 with three source-destination session types, allowing each session to use the two-link path as well as the direct path decreases throughput. However, random resampling is still beneficial provided that the uncoordinated control exhibits no RTT bias. If a session is given a set of paths to draw from, then the random resampling strategy described earlier maximizes welfare without the need to use all paths. Moreover, it suffices for sessions to use a greedy rate optimization strategy to determine which set of paths to keep in order to ensure welfare maximization. The reader is referred to Key et al. 11 for further details.

6. Discussion anD DePLo Yment

Till now, we have focused on networks supporting workloads consisting of persistent or infinite backlog flows. Moreover, the emphasis has been on the effect that multipath has on aggregate utility. In this section we consider workloads consisting of finite length flows that arrive randomly to the network. Our metric will be the capacity of the network to handle such flows. We will observe that several results from previous sections have their counterparts when we focus on finite flows.

As before, we represent a network as a capacitated undirected graph G = (V, E, C) supporting a finite set of flow classes, S with attendant sets of paths {R(s)}. We assume that class s sessions arrive at rate as according to a Poisson process and that they introduce independent and identical exponentially distributed workloads with a mean number of bits 1/ms. We introduce the notion of a capacity region for this network, namely the sets of {as} and {ms} for which there exists some rate allocation over the paths available to the sessions such that the time required for sessions to complete their downloads are finite.

In the case of coordinated control, it is possible to derive the following monotonicity result with respect to the capacity region of the network. Consider a network G that supports a set S of flow classes with arrival rates {as} and loads {ms}. Let {R(s)} and {R′(s)} be two collections of paths for these classes that satisfies R(s)  R′(s) for each s ∈ S and suppose that each session applies coordinated rate and path control over these paths. Then if {as}, {ms}, lie within the capacity region of the network with path sets {R(s)}, they lie in the capacity region of the network with path sets {R′(s)} as well.