Multipath routing and the ability to simultaneously use multiple network paths has long been proposed as a means for meeting the reliability and performance improvement goals of a next generation Internet. However, its use causes out-of-order packet delivery, which is well known to hinder TCP performance. While next-generation transport protocols will no doubt better cope with this phenomenon, a complete switch to these new protocols cannot be made on all devices "overnight"; the reality is that we will be forced to continue using TCP on such multipath networks well after deployment of a future Internet is complete. In this paper, we investigate the use of best-effort packet reordering -- an optional network layer service for improving the performance of any TCP session in the presence of out-of-order packet delivery. Such a service holds the promise of allowing unmodified TCP to take advantage of the reliability and performance gains offered by a future multipath-enabled Internet without suffering the adverse performance effects commonly associated with out-of-order packet delivery. Our experiments test the performance of two common TCP variants under packet dispersion with differing numbers of paths and amounts of inter-path latency variance. They were conducted using multipath network and packet reorderer implementations implemented within the Emulab testbed. Our results demonstrate that a simple best-effort reordering service can insulate TCP from the type of reordering that might be expected from use of packet dispersion over disjoint paths in a wide-area network, and is capable of providing significant performance benefits with few ill side-effects.

This paper analytically studies performance improvement achieved by packet dispersion. Contrary to the previous work on packet dispersion, we consider the tail distribution of queue length and that of packet delay as performance measures, and we model a packet network as multiple parallel queues where the arrival processes from sources are not renewal but highly bursty. To appropriately evaluate the performance improvement achieved by packet dispersion, we develop approximate formulas to estimate the tail distributions. Our approximate formulas yield more accurate estimations than the standard approximate formulas. In the numerical results, we observe that packet dispersion can greatly improve the delay performance of packets. We also see that packet-level load balancing is superior to flow-level load balancing for any distribution ratio.