[e2e] Reordering in routers

[Cannara]

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
> >> >