Remark 2. It is easy to find examples where the capacity region strictly increases with the addition of more paths. Remark 3. Although this result is stated for the case of exponentially distributed workloads, it is straightforward to show that it holds for any workload whose distribution is characterized by a decreasing failure rate. This includes heavy-tailed distributions such as Pareto.

It is interesting to ask the same question about the capacity region when uncoordinated control is used by all flows. Unfortunately, similar to the infinite session workload case, no such monotonicity property exists.

It is also interesting to ask the question as to which controller yields the larger capacity region. As in the case for finite flows, we can show that for a given network configuration (G, S, and R fixed), if {as : s ∈ S}, {ms : s ∈ S} lies within the capacity region of the network when operating with an uncoordinated control, then they lie within the capacity region of the network when operating under coordinated control as well.

Remark 4. It is easy to construct cases where the converse is not true. For instance, the symmetric triangle with single and two-link routing mentioned for fixed flows is such an example (see Key and Massoulié12).

We conclude from this monotonicity property for coordinated control that more is better. However, improved capacity comes at the cost of increased complexity at the end-host, namely maintenance of state for each path and executing rate controllers over each path. Fortunately, as in the case of infinite backlogged sessions, this is not necessary. It suffices for a session to maintain a small set of paths, say two paths, and continually try out random paths from the set of paths available to it, and drop the path which provides it with the poorest performance, say throughput. Note the similarity of this process to that of BitTorrent, which periodically drops the connection providing the lowest throughput and replacing it with a random new connection. Interestingly enough, this multipath algorithm coupled with random resampling achieves the same capacity region as one that requires flows to utilize all paths. Indeed, we can prove the analogy of 5. 1.

Theorem 5. Assume that class s sessions use all paths from R(s). Assume the set of loads {as} and {ms} lies within the network capacity region. Consider an approach where a class s session uses a subset of paths from R(s), randomly samples a new path set according to a Poisson process with rate γs and drops the worst of the two path sets. Then {ak} and {mk} also lie within the capacity region when flows use this resampling approach in the limit as gs → ∞.

Figure 3 illustrates and summarizes our capacity results. As before it is also interesting to ask about the effect of uncoordinated control coupled with random sampling on capacity. Surprisingly enough, uncoordinated control on a small set of paths coupled with random resampling can often

figure 3. capacity region under multipath with and without resampling.

maximum capacity multi path two paths ingle path two paths + resampling

increase capacity over uncoordinated control over the entire set of paths.

6. 1. Deployment

To effectively deploy multipath, key ingredients are first, diversity, which is achieved through a combination of multihoming and random path sampling, and second, path selection and multipath streaming using a congestion controller that actively streams along the best paths from a working set. Although home-users are currently often limited in their choice of Internet Service Provider (ISP) and hence cannot multihome, in contrast campus or corporate nodes often have diverse connections, via different ISPs or through 3G wireless and wired connectivity. Moreover, the growth of wireless hot-spots, wireless mesh and broadband wireless in certain parts of the globe means that even home-users may become multihomed in the future. Recent figures1 suggest that 60% of stub-ASes (those which do not transit traffic) are multihomed, and de Launois5 claims that with IPv6 type multihoming there are at least two disjoint paths between such stub-ASes.

The multipath controllers we have outlined need to be put into practice. Some high-level algorithms designs are considered in Kelly and Voice10 and Han et al., 7 and practical questions are addressed in Raiciu et al. 18 Translating from algorithms derived from fluid models to practical packet-based implementations does require care; however, we believe this to be perfectly feasible in practice. Indeed, the IETF has a current Multipath TCP working group, which is looking into adding multipath into TCP.

7. summaRY

There are potentially significant gains from combining multipath routing with congestion control. Two different flavors of control are possible: one which coordinates transfers across the multiple paths; and another uncoordinated control with sets up parallel connections. The uncoordinated approach is simpler to implement; however, it can suffer from poorer performance while coordinated control is better performing and intrinsically “fairer.” We have contrasted the two types of control, and shown that with fixed path choices uncoordinated control can yield inferior