PaperPicker

Online Journal Club for Networking Researchers

Packet Reordering

Posted by Michael Gellman on November 7, 2006

I’ve been doing some literature surveys recently on the topic of measuring Packet Reordering, and, for what should be a simple thing to quantify, it has a surprisingly large body of research. In this post, I’ll talk about packet reordering, why it’s important to consider, and approaches to quantify it.

What is Packet Reordering?

When a sender generates a traffic stream (this could be anything, from TCP traffic, to real-time Voice or Video) it generates an in-order sequence of data packets. Due to any number of causes which we discuss below, there may be a chance that the ordering of the packets received at the destination is different from that which the sender generated. This phenomenon we refer to as reordering.

In their IMW 2002 paper [1], Jaiswal, et al cite 3 main causes for packets being received in a different order than they were generated by the source:

  • Retransmission. In this case a sender infers that a packet has been lost and retransmits the packet. The retransmitted packet will have a sequence number that is smaller than previously observed packets at the measurement point and hece will be deemed “out-of-sequence.”
  • 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 (and hence the same packet is observed more than once), or if the network itself creates a duplicate copy of the packet
  • In network-reordering. In this case, the network inverts the order of two packet in a connection (for example, because of parallelism within a router or a route change

In the full version of their paper, delivered at INFOCOMM 2003 [2], Jaiswal, et al present the results of a large measurement study into the extent of reordering in the Internet. Their work has a number of methodological contributions for the classifying TCP packets observed in the network backbone. From their study, they found that many of the out-of-order packets observed in the network were due to retransmissions, and only a small fraction of packets (on the order of 1%, on average) were re-ordered by the network.

Why is it a problem?

Bennett, et al [3] enumerate five negative consequences of reordering on TCP traffic:

  1. Reordering causes unnecessary retransmissions
  2. Reordering makes it difficult or impossible to grow TCP’s congestion window
  3. Reordering can cause actual packet losses to be obscured, so that TCP retransmits lost packets later than it normally would
  4. Reordering may cause the round-trip estimator to poorly estimate the round-trip time
  5. Reordering may reduce the efficiency of the receiving TCP

How can we measure it?

A straight-forward method for measuring the number of out-of-order packets in the network is to consider any packet that has a sequence number that is smaller than that of a previously observed packet in that connection [1]. This is also known as the Type-P-Reordered metric in [4].

This approach has the advantage that it is simple to compute, and it results in a single metric. However, this simplicity results in subtle problems that have been highlighted by various researchers. One particular drawback to is that a single out-of-order packet with high sequence number will classify many subsequent packets as reordered, skewing the results. This has caused some researchers to call for a more sophisticated metric to take into account the degree of reordering.

One approach proposed by Piratla et al in [5] is known as reorder density, which, instead of a single value for desequencing, results in a histogram of reordering, whereby the degree to which a packet arrived reordered is taken into account. They compare their method with many other proposed reordering metrics in [6].

Conclusion

I hope this has given you an overview of what Packet Reordering is, why it is harmful to network flows, and some of the ways that it can be measured.

For further references on this topic, a great resource has been created here by Dr. Piratla.

References

  • [1] – Jaiswal, S.; Iannaccone, G.; Diot, C.; Kurose, J. & Towsley, D. “Measurement and classification of out-of-sequence packets in a tier-1 IP backbone” IMW ’02: Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, ACM Press, 2002, 113-114
  • [2] – Jaiswal, S.; Iannaccone, G.; Diot, C.; Kurose, J. & Towsley, D. “Measurement and classification of out-of-sequence packets in a tier-1 IP backbone” INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2003, 2, 1199-1209
  • [3] – Bennett, J. C. R.; Partridge, C. & Shectman, N. “Packet reordering is not pathological network behavior” IEEE/ACM Trans. Netw., IEEE Press, 1999, 7, 789-798
  • [4] – Morton, A.; Ciavattone, L.; Ramachandran, G.; Shalunov, S. & Perser, J. “Packet Reordering Metric for IPPM” 2006
  • [5] – Piratla, N. M.; Jayasumana, A. P. & Bare, A. A. “Reorder Density (RD): A Formal, Comprehensive Metric for Packet Reordering.” Proc. IFIP Networking Conference, 2005, 78-89
  • [6] – Piratla, N. M.; Jayasumana, A. P. & Bare, A. “A Comparative Analysis of Packet Reordering Metrics” COMSWARE, 2006
Advertisements

3 Responses to “Packet Reordering”

  1. reddy said

    please mention the advantages of reordering in this page……

  2. Abdul Wahid Soomro said

    It is quite helpful article regarding reordering.
    Being a researcher in packet reordering i.e ip reordering, tcp reordering of packets at receiver side from a particular destination is essential.

  3. TarakRam said

    in which layer the reordering done…n/w or transport

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: