[e2e] Ouput or input reordering in routers

Tue Aug 10 08:31:21 PDT 2004

Nischal,

I happened to work on one core router before, so my answer is based on state of
the art in 1998-1999:

1) Routers use the arrival order, so if the previous hop router reorders the packet,
   then there is nothing that the current hop can do.

2) Nope, see answer below.

3) Typically, deep packet inspection that goes to the TCP level is slowing the
   performance of the datapath (more memory read to know what's going on). Furthermore,
   trying to figure out flows to just fix the order of the packets does not scale very
   well (esp. in the core).

However, I do think that putting back the order at the access router is feasible 
(since more and more of those devices are doing firewall and the number of TCP flows
is much more manageable).

Hope this help,

-----Original Message-----
From: end2end-interest-bounces at postel.org
[mailto:end2end-interest-bounces at postel.org]On Behalf Of Nischal Piratla
Sent: Tuesday, August 10, 2004 1:39 AM
To: end2end-interest at postel.org
Subject: [e2e] Ouput or input reordering in routers

I have read on this forum (as pasted below)that the NPU vendors make sure that 
there is no reordering within a router. Let us consider a data transfer 
scenario with multiple hops. Assume that the first half of the routers along 
the path do not provide input or output reordering. Also, we will assume that 
there is reordering due to load-balancing (processing), in these routers. Now 
lets say that the remaining routers have input or output reordering enabled, 
i.e., they do not allow reordering. 
Here are my concerns:
1) Since the latter bunch of routers do consider the arrival order as actual 
order of packets, do they maintain the reordering that occured in earlier 
hops?
2) Or, is there a different meachanism to find out the actual order, while 
inside the latter bunch of routers? 
3) Even if it is a TCP flow, will the routers ever crack into the IP packets 
to extract TCP sequence numbers for input/output reordering?

Thank you,

- Nischal Piratla

Abhijit, check out the IBM and Motorola network processors, as well as Vitesse
(IQ2200), TI and Intel (IXP2800).  Cisco uses the IQ, the IXP and, I believe
some IBM ones.  The designers of most NPUs considered reordering a no-no, so
provided built-in hardware to track flows, as identified in simplest form by
tuples, like: input-interface, port/channel, IP details, etc.  However, the
output process, no matter how parallel the input, can be controlled more
finely in most NPUs by the firmware designer, so he/she can extend the
ordering checks at pkt-output time to see if any pkt on a particular output
queue shouold be released form transmission, regardless of which input path it
arrived on.  The IXP2400, in fact, doesn't support anything but programmer
ordering checks.

Alex

Abhijit Bare wrote:
>
> I understand that multiple input interfaces at a given NPU may process 
packets
> of a single stream in different orders. I was wondering if anybody can 
direct
> me to some detailed description of such architectures in use.
>
> Also, as we move on to high speed routers, the router architectures are
> becoming more parallel in their design. For example, VOQ structures or
> multi-plane switching fabcrics etc. Does this mean that we should expect 
more
> packet reordering as the network speeds increase ? Certainly, it depends 
upon
> the specific router architectures. But still internally they may end up in
> more reordering, putting higher burden on the packet re-sequencing units.
>
> Abhijit
>
> >===== Original Message From cannara at attglobal.net =====
> >Exactly right, in fact single-chip network processors from most all the
> >vendors have internal hardware (e.g., CAMs) simply to prevent pkts from 
being
> >released before all prior ones that arrived via the same input path.
> However,
> >since an input path is typically a channel on an interface, such as SPIx 
and
> >multiple interfaces exist on NPUs, there may be instances of pkts that
> >traversed different upstream paths getting reordered at a given processor
> that
> >can't know better.
> >
> >Alex
> >
> >"Ghanwani, Anoop" wrote:
> >>
> >> As far as I know, under normal circumstances most routers do not
> >> reorder packets.  I think Juniper routers had a problem with reordering,
> >>
> >> but the general design practice (as far as I know) is that reordering
> >> is a no-no.
> >>
> >> See
> >> http://www.lightreading.com/document.asp?doc_id=4009&page_number=8
> >> for an interesting discussion on this subject.
> >>
> >> -Anoop
> >>
> >> > -----Original Message-----
> >> > From: abhijit [mailto:abhijit at engr.colostate.edu]
> >> > Sent: Friday, August 08, 2003 2:45 PM
> >> > To: end2end-interest at postel.org
> >> > Subject: [e2e] Reordering in routers
> >> >
> >> >
> >> > Hi all,
> >> > I am studying the packet-reordering problem over the Internet
> >> > from the point
> >> > of view of the routers being a reason of reordering.
> >> >
> >> > In the paper by "Packet Reordering is Not Pathological
> >> > Network Behavior" by
> >> > Bennet, Partridge, and Shectman, the router queuing structure
> >> > was said to be
> >> > the reason behind the reordering observed at MAE-east. The
> >> > DEC gigaswitch used
> >> > at MAE-east point used hunt groups i.e. collection of ports
> >> > together acting as
> >> > input ports that caused the packets getting distributed and
> >> > hence reordered.
> >> >
> >> > I am studying queuing architectures and queuing disciplines
> >> > of present
> >> > routers. But I do not find any routers with parallel input
> >> > queuing sothat
> >> > incoming packets are distributed over a number of queues
> >> > before getting
> >> > processed. It will be great if anybody can give me
> >> > information or pointers
> >> > over this problem, especially:
> >> > 1. Are the internal structure issues i.e. queuing
> >> > architectures (input, output
> >> > queues, VOQ, VIQ etc), disciplines (packet scheduling or
> >> > buffer management
> >> > schemes) responsible or can be responsible for reordering?
> >> > 2. Or the external reasons such as route flapping, multi-path
> >> > routing,
> >> > parallel links between two routers, etc. are more responsible
> >> > for reordering
> >> > happening in the present Internet?
> >> >
> >> > I appreciate any information shared on this problem.
> >> > Regards,
> >> > Abhijit
> >> >

/******************************************
Research Assistant
Computer Networking Research Laboratory
Department of Electrical and Computer Eng.
1373, Colorado State University, 
Fort Collins, CO 80523 USA
http://www.cnrl.colostate.edu
http://lamar.colostate.edu/~nischal
*******************************************