[e2e] Reordering in routers

[Abhijit Bare]

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

*******************************************
Computer Networking Research Laboratory,
Colorado State University, Fort Collins, CO