Measurement and Classification of Out-of-Sequence Packets in a Tier-1 IP Backbone

Authors: Sharad Jaiswal, Gianluca Iannaccone, Christophe Diot, Jim Kurose, Don Towsley

Complete Citation

Sharad Jaiswal, Gianluca Iannaccone, Christophe Diot, Jim Kurose, Don Towsley. Measurement and Classification of Out-of-Sequence Packets in a Tier-1 IP Backbone. IEEE/ACM Transactions on Networking (TON), Volume 15 , Issue 1 (February 2007), Page(s): 54-66 Digital Object Identifier 10.1109/TNET.2006.890117

Abstract

We present a classification methodology and a measurement study for out-of-sequence packets in TCP connections going over the Sprint IP backbone. Out-of-sequence packets can result from many events including loss, looping, reordering, or duplication in the network. It is important to quantify and understand the causes of such out-of-sequence packets since it is an indicator of the performance of a TCP connection, and the quality of its end-end path. Our study is based on passively observed packets from a point inside a large backbone network--as opposed to actively sending and measuring end-end probe traffic at the sender or receiver. A new methodology is thus required to infer the causes of a connection's out-of-sequence packets using only measurements taken in the "middle" of the connection's end-end path. We describe techniques that classify observed out-of-sequence behavior based only on the previously- and subsequently-observed packets within a connection and knowledge of how TCP behaves. We analyze numerous several-hour packet-level traces from a set of OC-12 and OC-48 links for tens of millions connections generated in nearly 7600 unique ASes. We show that using our techniques, it is possible to classify almost all out-of-sequence packets in our traces and that we can quantify the uncertainty in our classification. Our measurements show a relatively consistent rate of out-of-sequence packets of approximately 4%. We observe that a majority of out-of-sequence packets are retransmissions, with a smaller percentage resulting from in-network reordering.

Annotations

This paper proposed a methodology to classify out-of-sequence packets in TCP connections going over the Sprint IP backbone. Since the study is based on passive measurements, millions of TCP connections were monitored.

Three reasons for out-of-sequence packets:

• Retransmission. In this case, a sender infers that a packet has been lost and retransmits the packet.
• In-network reordering. The network can invert the order of two packets in a connection (because of parallelism within a router, a route change, or a route loop in the end–end path).
• Network duplication. In this case, a non-sender-retransmitted copy of a packet is observed. This can occur when the measurement point is within a routing loop, or if the network itself creates a duplicate copy of the packet.

Experimental results:

• About 4% of packets generated by TCP connections are out-of-sequence, most of which are due to retransmission in response to a packet loss.
• Packet reordering affects about 1%–1.5% of all data packets, however, they have little impact on the quality of a TCP/IP connection as perceived by the end users.
• Other network anomalies such as duplication of packets represent a very marginal phenomenon in the Internet.

-- YingxinJiang - 14 Nov 2007