Subject: Re: Nr in data packets

From: Vernon Schryver <[email-masked]>
Date: Fri, 21 Jan 2000 14:55:02 -0700 (MST)

> From: David Chen <[email-masked]>

> Why PPP demanding the lower layer be serial transmission? (frame in sequence)
> when its encapsulate IP(X)...that do not demand this.

Why?--because of history, as someone (perhaps you) observed early in
this thread.  PPP originally came from the fusion of two groups in the
IETF.  One was working on a more robust replacement for SLIP, RFC 1055.
The other was working on an interoperable, open-standard replacement
for proprietary router-to-router protocols over leased lines.  In both
cases, the underlying media never re-ordered frames, and so it made no
sense to add the major complications that would be required to deal with
link layers that might deliver out of order.

Even today, the overwhelming majority of all existing and likely
PPP links are on link layers that do not re-order frames.

You are mistaken about the requirements of the upper layers.  Many
protocols carried in PPP frames do not tolerate out-of-order packets.
Doesn't IPX require that its link layer not re-order packets?  The packets
supported by the PPP bridging protocol certainly must not be re-ordered.
Not even IPv4 is tolerant of re-ordered packets.  Some popular IP
implementations (e.g. for PC's) died when given out-of-order IP packets.
As I said earlier today, TCP/IP survives out-of-order segments, but does
not tolerate them, unless you define reduced speed as well as bandwidth
wasted on unnecessary retransmission counts as tolerance.

> If PPP needs this other then its encapsulate protocol then
> it can use RFC1663.

I do not understand that.  Before RFC 1663 can start working, LCP
must get to the OPENED state, and that requires that packets not
be re-ordered.  In other words, I do not see how RFC 1663 might
allow you to run PPP over a link that re-orders packets.

If you look in the archives of the PPP Compression mailing list and
probably also in the main PPP mailing list archives, you'll find that the
justification for RFC 1663 was to recover from lost packets for PPP payload
compression.  RFC 1663 was not intended to deal with packets re-ordered
by the lower layer, although I assume it would, if you could somehow also
ensure that LCP packets would not be re-ordered.

Another problem is the very limited support in the real world for RFC 1663.

PPP does not require a lossless, correctly ordered stream from the
lower layer.  The lower layer need do no more than detect out-of-order
packets and discard them instead of delivering them to upper layer.
To me, that requirement sounds trivial.

Vernon Schryver    [email-masked]

---

From: David Chen <[email-masked]>
Date: Fri, 21 Jan 2000 21:02:52 -0500

Does PPP recognized the difference of incoming packet has the 1,2,4,3,5 
(out of sequence)
order or 1,2,4,5 (missing packet).
If it does not, then it does not stop PPP function correctly even the lower 
layer does
not guarantee the frame transmitting sequence.
However, the performance could suffer.
--- David

---

From: "W. Mark Townsley" <[email-masked]>
Date: Sun, 23 Jan 2000 15:42:35 -0800

> protocols carried in PPP frames do not tolerate out-of-order packets.

That is true, which is why we can turn on sequencing when necessary. 

> wasted on unnecessary retransmission counts as tolerance.

We all know that, by design, IP may reorder packets. I see no reason why
it is L2TP's business to correct this for tunneled PPP/IP frames. If the
reordering of IP packets being detrimental to some broken stacks is
cause for enabling sequence mode by L2TP, then why limit L2TP traffic to
this new-found benefit for IP? We should start using L2TP in sequence
mode for all IP transmissions. L2TP becomes the packet sequencing
protocol for the Internet! This is of course obsurd, but it illustrates
the point that, when carrying IP within L2TP/PPP over IP, it is safe to
not bother with sequencing...  

> To me, that requirement sounds trivial.

In fact, there are some cases where sequence checking can actually be
dangerous on an IP link. Consider the following actual occurance that we
witnessed at a recent bakeoff. One implementation consisently reordered
fragmented L2TP packets. This UDP/IP stack was operating properly as IP
stacks are certainly allowed to reorder packets (and fragmentation is a
common cause of this). L2TP Sequence checking was enabled by the
receiving peer, thus dropping all out of order packets just as you
suggest. The end result was that no fragmented L2TP packets were ever
received. 

At any rate, yes there are indeed cases where preservation of order was
an important underlying assumption for PPP. For these, L2TP has a method
for enabling (and disabling) sequence numbers at any time during the
life of the session.

---

From: Grenville Armitage <[email-masked]>
Date: Mon, 24 Jan 2000 09:43:34 -0800

"W. Mark Townsley" wrote:
	[..]
> We all know that, by design, IP may reorder packets.

Judging by your subsequent response to Vern, this concept is
being interpreted more liberally than I think is warranted.

It is a design goal for protocols running over IP that they
dont blue-screen when reordering occurs. But there's no
design goal that such protocols must work efficiently, or
even at all, in the presence of reordered packets. Reordering
'may' occur as a rare consequence of routing transients. This
doesn't justify IP stacks (either at the end or in the middle)
from *consistently* reordering packets (or fragments) - that's
just broken stack design (especially since such a broken stack in
a LAC or end-host will typically still be in the path after a routing
change)

So IP *may* reorder packets as a rare event. But any design
(network or node) that causes regular, correlated, and repeatable
reordering is broken.

cheers,
gja
________________________________________________________________________
Grenville Armitage                            http://mh005.infi.net/~gja
Bell Labs Research Silicon Valley

---

From: "W. Mark Townsley" <[email-masked]>
Date: Tue, 25 Jan 2000 11:49:24 -0500

I won't claim to be the foremost IP stack expert for a moment, but
common sense to me says that if I receive an IP packet that must be
fragmented followed by a bunch of smaller packets that do not, it makes
sense to go and and switch the smaller packets rather than queuing them
while I chew on the fragmentation. If you have hardware or even driver
assisted fragmentation then perhaps it is not an issue, but if your
processer has to sit there and allocate a bunch of buffers, chop up the
packet, copy data, etc. this could take a serious amount of time.
Meanwhile, your input queue is growing, and latency increasing. Even if
the packets are associated with the same TCP stream (which on a middle
node they are likely not) latency can be as much of a burden to
performance as packet loss (ask anyone in tcpsat about that). I am
curious though, which RFC states that IP packet reordering may only
occur during route transitions? 

- Mark

---

From: Grenville Armitage <[email-masked]>
Date: Tue, 25 Jan 2000 09:33:32 -0800

"W. Mark Townsley" wrote:
> while I chew on the fragmentation.

Then our definition of 'common sense' differs ;) Given a goal of
optimizing end to end performance, the above is not common sense
(although on the surface it is an appealing argument from the
perspective of the node facing the sequence of packets you describe).

If the packets do not belong to the same flow (or aren't even
targetted at the same IP destination) then process in whatever
order you like - but that's not "reordering" in the sense being
discussed here.

	[..]
> Even if
> performance as packet loss (ask anyone in tcpsat about that).

Latency happens. But reordering fragments of packet N
in order to expedite packets N+1, N+2, .. of the same TCP stream
is false economy. You'll just be screwing with TCP's mind, and
in the end your goodput will be lower than if you'd simply let
nature take its course and kept the stream's packets in order.

> I am

My words were:
	[..]
> > Reordering
> > 'may' occur as a rare consequence of routing transients.

Noone said there's a rule mandating it only occur under those
circumstances. That's just the unpredictable circumstance IP apps
need to be designed to tolerate. But IP stacks that reorder
in some misguided attempt to reduce latency constitute an avoidable
circumstance.

cheers,
gja

---

From: "W. Mark Townsley" <[email-masked]>
Date: Tue, 25 Jan 2000 16:54:42 -0500

> optimizing end to end performance, the above is not common sense

There are all sorts of things that can be optimized. Host to host TCP
performance is not the only thing, and overanalyzing each packet
midstream can be very costly.

> order you like - but that's not "reordering" in the sense being

Of course it is. When doing any sort of traffic shaping, there is
question of queuing, flow detection, etc. There are always tradeoffs.
The question here is whether it is worthwhile to peek into the UDP
packet to ensure in order delivery of L2TP, or even into the L2TP packet
to ensure inorder delievery of a TCP session being tunneled. The
"smarter" you are about the type of traffic you are switching, the
slower you are at switching it.

> in order to expedite packets N+1, N+2, .. of the same TCP stream

Sure, if part of the same TCP stream. But, you do not have that
information. So, the question becomes whether or not you expedite UDP
packets N+1, N+2, etc., not TCP packets of the same stream. These could
be intermixed L2TP, DNS, TFTP, voice, etc. packets, as well as multiple
streams within L2TP.

> in some misguided attempt to reduce latency constitute an avoidable

It's not just latency. It's overall throughput, CPU usage, queue and
memory limititations, etc.

---

From: Grenville Armitage <[email-masked]>
Date: Tue, 25 Jan 2000 14:48:43 -0800

> midstream can be very costly.

My apologies, I thought global optimization was always a goal
of local design considerations. If someone wants to build
a box that tosses packets through really really fast, and
casually reorders in the process, good luck to them. They'll
ace the pps test, and screw their customer's network performance.
I guess its a free marketplace.

	[..]
> Of course it is.

Again we differ. Inter-flow packet reordering isn't
relevant to the e2e performance of any given transport
flow. Intra-flow reordering *is*. Which is what I said
above. (Which is arguably what Vern has been pointing out
too)

> When doing any sort of traffic shaping, there is
> question of queuing, flow detection, etc.

The distinction between inter- and intra-flow reordering 
(microflows, in diffserv terminology) still stands. Inter-flow
reordering is vastly less important than intra-flow reordering.
Thus your scenario of a router facing a sequence of small
packets behind a to-be-fragmented large packet really depends
on whether the packets belong to the same flow/stream or not.
If so, do not reorder. If not, reorder as desired. 

	[..]
> Sure, if part of the same TCP stream.

Well, that's the case you mentioned (I even quoted it above
to establish context for my response).

> But, you do not have that
> information.

So you should assume it probably is, or at least probably
might be. Which means gratuitous reordering within
an IP stack is counter-productive (when viewing the system
as a whole, including the actions required of the endstations
to deal with the reordering).

> So, the question becomes whether or not you expedite UDP

If packet N is UDP, and packet N+1 is TCP then these represent
distinct flows (or flow aggregates, if for some reason meaningful
port numbers aren't available or aren't being used for internal
classification purposes within the IP stack in question). You
can reorder the fragments of N relative to N+1 to your hearts
content since the UDP and TCP streams will still arrive inorder
at their respective destinations. 

But I think you knew that. 

Like I said when I joined in, the statement that IP permits
reordering isn't a carte blanche invitation to IP stack
implementors to introduce internal reordering. To be more
precise, intra-flow reordering is the main concern. This
has been acknowledged in the diffserv WG, and MPLS WG.

	[..]
> memory limititations, etc.

Re-sequencing of reordered packets at the endstation consumes cpu,
queues, and memory. Performing the re-sequencing in general adds
latency. The endstation is the customer - 'the network' needs
to deal with that fact. 

cheers,
gja