Subject: Re: Reordering and MPLS?

From: "J. Noel Chiappa" <[email-masked]>
Date: Tue, 4 Jan 2000 15:17:37 -0500

> From: Eric Gray <[email-masked]>

    >> Is there a requirement to preserve packet order in MPLS? 

    > It is probably a reasonable expectation of network elements and may be a
    > reasonable expectation of the network as a whole ... if we assume that
    > implementations .. do not themselves change the order of packet delivery
    > .. then we can get ordered behavior out of the network as a whole

What you say is of course theoretically correct.

However, as I expect everyone already understands, it would be extremely
unwise to try and guarantee this "in-order" property of the network as a
whole, to the point where implementations in endnodes rely on it. It would be
equally unwise for endnodes to rely on this guarantee, even if the network
tried to make it.

The reasoning is simple. One one hand, it only takes one bug, in a complex
mass of mechanism distributed across many independent components, to break
this property. On the other hand, the cost (in performance, and complexity) of
building endnodes which do not rely on this property is minimal. Given the
importance of robustness (i.e. fault tolerance), including it in this area,
when the cost is so minimal, is really the only choice.

To expand on the cost a bit, ideas like header-prediction mean that one does
not pay the overhead of dealing with out-of-order packets on every normal
packet. Checks for out-of-order packets, and waiting queued out-of-order
packets, can be performed only if the incoming packet is not the "next
expected packet". Also, out-of-order packets are handled in much the same way
as the latter packets in a burst, if an early one is dropped - so most of the
mechanism to handle them has to be there anyway.

If the point of the question was not literally "required", but rather "the
network should try hard to keep packets in order", that's a different point,
to which the answer is clearly "yes". Out-of-order packets will likely have a
performance impact. However, exactly how hard the network should try is a
complex subject.

For exmple, it may enable great simplification in the network, and network
elements, if intermediate elements are allowed to run a low-probability risk
of reordering a packet (e.g. in the routing case you cite).

	Noel

---

From: Eric Gray <[email-masked]>
Date: Tue, 04 Jan 2000 17:58:24 -0500

Hi Noel.  Please see below.

> What you say is of course theoretically correct.

Interesting that the hacked up version above - while it reads
like a sentence - is just as clearly incorrect.  I'm glad I
didn't say it...  :-)

> equally unwise for endnodes to rely on this guarantee, even if the network

It is clearly expensive to guarantee in order delivery for
all packets transmitted across a network.  But it is easily
justified for specific uses of the network.  For example, if
I want to transport data using an LSP from one end node to 
another that needs to be delivered in order - just because
I'm ornery and simply want to skip the step of adding an IP 
header - there should be no reason why I should not be able
to do this.  There are technologies today that allow this.

> when the cost is so minimal, is really the only choice.

Interestingly enough, there are some companies who've had it
as a long term goal to produce equipment that is not so buggy.

> of reordering a packet (e.g. in the routing case you cite).

Actually, even the low probability risk should be eliminated 
if a specific network application is using an LSP that was
setup using an explicit route and/or route pinning.  The only
reason why "should be" rather than "will be" is because it is
always possible that there are companies out there that have
not had it as a long term goal to produce equipment that is
not so buggy.  :-)

For an application of LSPs that requires in order delivery, it
should take a network event that results in lost connectivity
to cause the LSP to fail.  This is appropriate, since - for at
least one application of this sort - out of order delivery is
exactly the same thing as lost connectivity.

---

From: Jeremy Lawrence <[email-masked]>
Date: Wed, 05 Jan 2000 14:45:26 +1100

Reordering has come up a couple of times recently, and I'm
wondering why. As Noel has eloquently explained, a
well-designed network attempts wherever feasible to deliver
similar packets (e.g. packets of the source, destination, and
diffserv class) in order, and a well-designed end-system can
tolerate occasional mis-ordering. Unless I'm missing something,
this all seems quite sensible.

Is it just that a note to this effect needs to be added to a
document somewhere? (I'm not sure where: these are fundamentals
of packet network & equipment design independent of MPLS or IP.)

Or is it that people are considering applications of MPLS in
circumstances where it seems desirable that packet ordering be
guaranteed at the network layer? If so, then it seems important
to discuss the applications themselves.

Jeremy Lawrence