[e2e] Packet reordering in Internet

[Paddy Ganti]

In our past experience packet reordering is seen most commonly at very small
time scales; that is, packets that get sent back to back on a high-speed
network are likely to be reordered, but with even a millisecond or so
spacing between packets (such as if the packets originated on a 10BaseT net)
the chance of reordering is far less. So thats why you usually never see
them on LANs but is very common on a GigE WAN.

That said RFC 4737 is a good read to decide which metric of packet
reordering that you want to focus upon.

>Is that a safe assumption?

I dont think so.  The following paper clearly details the role of transmit
buffer allocation in packet reordering.

S. Govind, R. Govindarajan and Joy Kuri “Packet Reordering in Network
Processors”, Proceedings of the International Parallel and Distributed
Processing
Symposium (IPDPS-07), CA, USA, 2007

Also this paper details why the assumption is not safe:

A. Bare, A. Jayasumana, N. Piratla, “On Growth of Parallelism within Routers
and Its Impact on Packet Reordering,” Proceedings of the
2007 15th IEEE Workshop on Local and Metropolitan Area Networks, ,
Princeton, NJ, 2007.

>Are there any other mechanisms in the routers/switches that could lead to
packet reordering?

Link-Layer Retransmissions and  Router Forwarding Lulls are also causes.
Please see the following paper for details

K. Leung, Victor O.K. Li, Daiqin Yang, “An Overview of Packet Reordering in
Transmission Control Protocol; Problems, Solutions, and Challenges”,
IEEE Transactions on Parallel and Distributed Systems, Vol. 18. No. 4, 2007


Finally the following papers might be of interest to you as well

L. Gharai et al., ”Packet reordering, high speed networks and transport
protocol performance,” In Proceeding of the 13th ICCCN,
Chicago, IL, October 2004

Yi Wang, Guohan Lu and Xing Li, "A Study of Internet Packet Reordering," in
Proceedings of International Conference on Information
Networking (ICOIN), Lecture Notes in Computer Science 3090, Springer-Verlag,
2004

S. Jaiswal, et al., “Measurement and Classification of Out-of-sequence
Packets in Tier-1 IP Backbone,” IEEE/ACM Transactions on
Networking, Vol. 15, No. 1, February 2007.

S. Kandula, D. Katabi, S. Sinha, A. Berger, “Dynamic load balancing without
packet reordering,” ACM SIGCOMM Computer
Communication Review, 37(2), April 2007

Hope this helps.

-Paddy

On Wed, Aug 12, 2009 at 8:32 AM, Manish Jain <jain.manish at gmail.com> wrote:

> Thanks everyone for the useful pointers.
>
> Based on the some pointers and past discussions, I understand that
> routers in the current Internet have load-balancing implemented in a
> way to preserve packet order within a TCP flow. Is that a safe
> assumption? Are there any other mechanisms in the routers/switches
> that could lead to packet reordering?
>
> --
> Manish
>
> On Wed, Aug 12, 2009 at 9:50 AM, Bartek Belter<bart at man.poznan.pl> wrote:
> > Hi Manish,
> >
> > Some time ago we did some experiments in the pan-European education
> network. The results of experiments were summarized in a paper.
> > It is available here:
> http://tnc2005.terena.org/core/getfile.php?file_id=626 (Shall we worry
> about Packet Reordering?).
> >
> > Hope it helps.
> >
> > Best regards,
> > Bartek
> >
> > -----Original Message-----
> > From: end2end-interest-bounces at postel.org [mailto:
> end2end-interest-bounces at postel.org] On Behalf Of Manish Jain
> > Sent: Tuesday, August 11, 2009 11:57 PM
> > To: end2end-interest at postel.org
> > Subject: [e2e] Packet reordering in Internet
> >
> > Hello,
> >
> > I was wondering if there are measurement studies of Internet traffic
> quantifying the magnitude of packet reordering within a TCP flow. Is
> reordering a common problem for TCP in the current Internet? How about the
> load balancing features in the routers from major vendors : is it per flow
> basis or per packet basis, and if flow based load balancing is done, then
> how is the flow classification is done these routers?
> > What could be/are other sources of reordering withing a TCP flow?
> >
> > Thanks,
> > Manish
> >
> >
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.postel.org/pipermail/end2end-interest/attachments/20090812/2fc3546a/attachment-0001.html