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.