The design of TCP's error and congestion control mechanisms was based on the premise that packet loss is an indication of network congestion. Therefore, upon detecting loss, the TCP sender backs off its transmission rate by decreasing its congestion window. TCP uses two strategies for detecting packet loss. The first one is based on the sender's retransmission timeout (RTO) expiring and is sometimes referred to as coarse timeout. When the sender times out, congestion control responds by causing the sender to enter slow-start, drastically decreasing its congestion window to one segment. The other loss detection mechanism originates at the receiver and uses TCP's sequence number. Essentially, the receiver observes the sequence numbers of packets it receives; a ``hole'' in the sequence is considered indicative of a packet loss. Because TCP mainly uses cumulative acknowledgments, the receiver generates a ``duplicate acknowledgment'' (or DUPACK) for every ``out-of-order'' segment it receives. Note that until the lost packet is received, all other packets with higher sequence number are considered ``out-of-order'' and will cause DUPACKs to be generated. Modern TCP implementations adopt the fast retransmit algorithm which infers that a packet has been lost after the sender receives a few DUPACKs. The sender then retransmits the lost packet without waiting for a timeout and reduces its congestion window in half. The basic idea behind fast retransmit is to improve TCP's throughput by avoiding the sender to timeout (which results in slow-start and consequently the shutting down of the congestion window to one).

Fast retransmit can substantially improve TCP's performance in the presence of sporadic reordering but it still operates under the assumption that out-of-order packets indicate packet loss and therefore congestion. Consequently, its performance degrades considerably in the presence of ``persistent reordering.'' This is the case for reordering of both data and acknowledgment packets. Indeed, it is well known that TCP performs poorly under significant packet reordering (which may not be necessarily caused by packet losses).

Packet reordering is generally attributed to transient conditions, pathological behavior, and erroneous implementations. For example, oscillations or ``route flaps'' among routes with different round-trip times are a common cause for out-of-order packets observed in the Internet today. Internet experiments performed through MAE-East show that 90% of all connections tested experience packet reordering. Researchers at SLAC performed similar experiments and found that 25% of the connections monitored reordered packets . However, networks with radically different characteristics (when compared to the Internet, for example) can exhibit packet reordering as a result of their normal operation. This is the case of wireless networks, in particular multi-hop mobile ad-hoc networks (MANETs). In MANETs, which are also known as ``networks without a network,'' there is no fixed infrastructure and every node can be source, sink, as well as forwarder of traffic. The potential for unconstrained mobility poses many challenges to routing protocols including frequent topology changes. Thus MANET routing protocols need to recompute routes often, which may lead to (persistent) packet reordering. In fact, improving the performance of TCP in such environments (by trying to differentiate out-of-order packets from congestion losses) has been the subject of several recent research efforts.

Mechanisms that provide different quality-of-service (QoS) by differentiating traffic are also likely to introduce packet reordering as part of their normal operation. An example of such mechanisms is DiffServ, which has been proposed to provide different QoS on the Internet. In this case, a priority flow must obey negotiated bandwidth constraints. If the flow exceeds these constraints, the non-conformant packets are either dropped or given a lower priority. In the latter case, the packets will be placed in different queues and will likely experience different latency, resulting in out-of-order delivery to the final destination.

While packet reordering is often considered to be pathological in today's Internet, it is actually part of normal operation for a number of routers containing parallel paths through the switch. Due to the scheduling algorithms used, different packet sizes and arrivals times may result in the reordering of packets entering on a single interface. While the exact cause of packet reordering lies in the details of the scheduling algorithm, a more general reason is that parallel paths are employed for economic reasons; it is cheaper to build multiple moderate speed paths than a single very high-speed path. The result of seeking this increase in cost efficiency is that packets may sometimes be reordered. TCP-PR is a transport protocol compatible with multipath routing, hence it will not limit the drive for efficiency at the lower layers.

Beyond router design, there are other areas that stand to gain efficiency if multiple paths are permitted. For example, load balancing is greatly simplified if single flows are permitted to use different paths. When a flow is restricted to use a single path, then optimal load balancing reduces to an NP-hard integer programming problem but if the single path restriction is lifted, then optimal load balancing is a simpler linear programming problem. Different flows may be split along multiple paths in order to meet QoS requirements. Permitting even single flows to be split results in a more efficient use of network resources. In the case of MANETs, spreading packets across different links also decreases the battery drain on any particular mobile node and may increase the lifetime of the network.

While efficiency is one area that may benefit from multipath routing, fault tolerance and security can also be improved by utilizing multiple paths. For example, in wired networks, multipath routing has been shown to reduce the impact of link failures. Similarly, multipath routing can increase robustness to eavesdropping by spreading packets across different paths, thus forcing the attacker to sniff multiple links . Multipath routing can take advantage of the considerable path redundancy that already exists in today's Internet. For example, it was shown that in the US Sprintlink topology, 90% of PoP pairs are connected through at least 4 distinct paths.

In MANETs, alternate path routing has been an active area of research. It is suggested that alternate paths be found and stored in an attempt to anticipate failures in the primary path. However, it was shown that alternate paths may grow stale and no longer exist when the primary path fails. One way to learn that alternate paths have failed is to send part of the data stream along them, as in multipath routing. While multipath routing has many advantages, it leads to persistent packet reordering. Today's implementations of TCP are not compatible with networks that reorder packets and suffer great reductions in throughput when faced with persistent packet reordering. TCP's incompatibility with persistent packet reordering has been a major deterrent to the deployment of the mechanisms mentioned above on the Internet or on other networks in which TCP is prevalent. There are a number of methods for improving TCP's performance in packet-reordering prone environments, but most of them try to recover from occasional reordering and rely on the packet ordering itself to distinguish drops from reordering. However, under persistent reordering conditions, packet ordering conveys very little information on what is actually happening inside the network.

The key feature of TCP-PR is that duplicate ACKs are not used as an indication of packet loss. Rather, TCP-PR relies exclusively on timeout. Both worst-case analysis and Internet traces are used to ensure that the timeout threshold is not too small and only actual packet losses cause retransmissions. Through extensive ns-2 simulations, we evaluated the performance of TCP-PR, comparing it to a number of existing schemes that address TCP's poor performance under packet reordering. We found that under persistent packet reordering, TCP-PR achieves significantly higher throughput. We also test TCP-PR's compatibility and fairness to standard TCP variants, specifically TCP-SACK. In the absence of packet reordering, TCP-PR is shown to have similar performance and competes fairly with TCP-SACK. TCP-PR neither requires changes to the TCP receiver nor uses any special TCP header option. Hence, TCP-PR is suitable for incremental deployment.