Subject: LL vs. E2E ARQ [Re: When non TCP/IP literate people design cable modem systems]

From: Reiner Ludwig <[email-masked]>
Date: Thu, 24 Jun 1999 11:43:02 -0700

after most of the gun smoke has cleared out ... 

... let my collectively respond to some of the replies I have 
provoked, clarify a few things, and maybe raise a few more 
issues people might find outrageous (like making TCP retransmit 
"forever" (means "until the _application_ decides to close the 
connection") instead of only 12 times). 

Clearly, I'm implicitly assuming a wireless link (not 
necessarily a first/last-hop link) here but, hey, soon the 
Internet will have more clients that connect wireless rather 
than wireline ...

Let me start by picking up Steve Deering's question: Can we have 
transport-protocol-blind link-layer protocols that are *good 
enough* for all (useful/necessary) transport protocols?
YES WE CAN. 

The alternative I (and others) proposed is to do:

A. implement flow-adaptive link layers, and

B. give reliable flows (TCP, NFS, Reliable Multicast, etc.) 
   fully-reliable LL ARQ (as defined below), and 

C. (optionally) put the "Eifel" algorithm into your reliable 
   transport protocol or, i.e., get rid of the "retransmission 
   ambiguity"  [Karn/Partridge87] to further (beyond what A & B 
   already give you) improve e2e performance.

***********************
*Fully-*Reliable Link Layer Error Recovery - Definition and 
a few Notes
***********************

This has raised a lot of confusion. I have cut/pasted this part 
to the end of this mail in order not to bother you up front with 
this lengthy list of replies and clarifications.

***********************
Flow-adaptive Link Layers
***********************

(1) Only people who know nothing or too little about wirless can 
make the claim: "In general, link layers should stay dumb or 
they'll hurt people."

(2) The concept of "flow-adaptive link layers" says: the more 
the link knows about what the flow (its application) wants, the 
better it can tune the error control schemes it has in its 
toolbox (e.g., adaptive versions of FEC, power control, 
spreading factor control, ARQ persistency, ARQ frame length 
control, etc.). The way to go is, however, NOT to make the link 
layer transport-aware. Instead, have the application express in 
the IP header what it wants and use that information at the link 
layer. That's how you get 
    I. independence from transport layer (or higher) protocol 
       semantics, and
    II. co-existence with any form of IPsec.
More on this in 
http://iceberg.cs.berkeley.edu/papers/Ludwig-FlowAdaptive/index.html

Note,  

(a) that this is NOT layer violation! All it takes is a capable 
network-layer/link-layer interface definition.

(b) that the QoS for reliable flows are as simple as it gets: 
"Get the bits across the link as fast as possible, but 
*reliable*, while the per packet delay is not so important." 
This allows to aggressively optimize FEC/ARQ towards high 
throughput. For delay-sensitive flows (e.g., a TCP-friendly 
audio stream) things are (by far) not so simple anymore ..... 
probably no ARQ and lots of FEC for hard-realtime, and little 
ARQ and a little FEC for realtime-with-play-back-buffers. Who 
knows. There is not much info you get out of the IP header, yet. 
(range of target error rates / range of target bandwidths would 
be nice to know ...). 

(c) This has nothing to do with queue management techniques. I'm 
certainly not proposing to have the link layer retransmit 
packets that need to be dropped. Who would do such a thing? 
(more on this below).

(d) This is perfectly compatible with the e2e-argument. Some 
people on this list misuse the e2e-argument by saying that 
EVERYTHING has to be done e2e. This is a misinterpretation of 
what the authors wrote in their landmark paper. I recommend to 
those who misuse the e2e-argument in that way to go back and 
take closer look at that paper (the intro says it all): 
http://people.qualcomm.com/karn/library.html

(e) (Big) Limitation of this concept: it only works for TCP as 
other reliable flows cannot be identified from the information 
we have in the IP header. -> DS field should allow to do that.
(we know the TOS definitions, but they are (unfortunately) not 
used!)

***********************
The Misconception of how far you get with FEC-only
***********************

(1) There still seem to be people who believe that only FEC will 
do the job. I can understand that when people have a 
satellite-only background when it comes to "wireless", but ... 
.... on satellite links the packet transmission delay is usually 
much smaller than the "typical" error length. Thus, there is not 
much to gain from LL ARQ. On long-thin wireless links (e.g., 
cellular telephone networks) things are _very_ different. E.g. a 
1500 byte packet can have a transmission delay (9.6 kb/s) of 
1250 ms. However, the error length is mostly only 20 or 40 ms 
long:
http://iceberg.cs.berkeley.edu/papers/Ludwig-Mobicom99/index.html. 
=> no question: you need LL ARQ. Putting in even more FEC would 
   be ...... not such a great idea.

(2) The following claim has often been made: "TCP has this 
"natural" probing loss rate, lets call it X, where it loses one 
packet - in the ideal case - at the end of each congestion 
avoidance cycle. [No doubt so far] So just design your FEC with 
a damage loss rate of Y with Y < X. [Big doubts]", but ....
... this does not work because X is not known at the LL (its 
only known at the end points of the path) and can vary 
considerably from flow to flow as it depends on the each flow's 
bandwidth/delay product. Thus, one would need brute force, 
super-wasteful FEC to protect against the worst-case to make 
things work with FEC-only (in the general case - maybe 
satellite links are an exception, don't know). 

***********************
The "Eifel" Algorithm
***********************

(1) The "Eifel" idea says: Spurious timeouts and spurious fast 
retransmits are NOT bad. They are your *friends* if you 
    I. can identify them, and
    II. do something to limit the damage they cause.

(2) Spurious timeouts are due to excessive packet delay and can 
be caused by such things as full-reliable LL ARQ, route changes, 
route flappings, routing table updates, etc. Spurious timeouts 
force (because of the retransmission ambiguity) the TCP sender 
into go-back-N and set the window to one.

(3) Spurious fast retransmits are due to packet re-orderings 
beyond the DUPACK threshold and can be caused by out-of-order LL 
delivery, route changes, route flappings, etc. Spurious fast 
retransmits cut the window in half.

(4) To identify them in TCP you need to get rid of the 
retransmission ambiguity. That's easy with the timestamp option 
(RFC 1323).

(5) Once identidied: restore the window (cwnd), make sure you 
don't create a burst, and avoid go-back-N (after timeouts) but 
continue to send "from the top". Under "normal" circumstances 
this prevents all but the first spurious retransmission.

(6) Check out Figures 7 & 8 in 
http://iceberg.cs.berkeley.edu/papers/Ludwig-FlowAdaptive/index.html 
if you want to take a quick look at how (the spurious timeout 
part of) it works.

Note, 

(a) that, assuming RFC 1323 to be part of the TCP protocol, this 
is only a minor change to the TCP sender implementation, NOT the 
protocol. Still, like any proposed change to TCP's
implementation, this has the usual deployment concerns. However, 
it is *incrementally* deployable as it does not srew up existing 
TCPs and it does NOT touch congestion control behavior in any 
way.

(b) that although we have implemented this for TCP (and will 
make the FreeBSD source available soon) this is not TCP 
specific. Reliable transport protocol in general should not 
perform (avoidable) go-back-N-style, duplicate retransmissions 
and restore their send rate once they have found out that they 
have unnecessarily reduced it in response to a spurious timeout 
or a spurious fast retransmit.

(c) that it is impossible to engineer a transport layer 
retransmission timer that avoids all kinds of spurious timeouts. 
That's the wrong design goal! An adaptive transport layer 
retransmission timer should not be tuned to prevent all spurious 
timeouts as this results in a retransmission timer which is 
overly conservative. This has a negative impact on TCP’s 
performance whenever the sender has to resort to a (long) 
timeout to recover a lost packet. This affects interactive 
applications but also bulk data transfers as soon the receiver’s 
receive buffer is exhausted to absorb any further out-of-order 
packets. As a result the sender is blocked from sending any 
further packets.
Instead, an adaptive transport layer retransmission timer should 
be "reasonably" conservative while a sender should be able to 
detect spurious timeouts and react appropriately (with the 
"Eifel" algorithm). The BSD4.4 TCP retransmission timer e.g. 
misses this goal and is overly conservative (see the now often 
enough referenced paper).

(d) that the following claim has been made many times: "Don't 
introduce LL ARQ delay beyond transport layer retransmission 
timers to avoid spurious timeouts." That's impossible because 
unknown at the link layer. Spurious timeouts can be your friend 
if you use the "Eifel" algorithm.

***********************
Snoop and similar approaches
***********************

(1) In general, the attractiveness of link layer solutions over 
approaches that require access to the transport layer headers in 
the network, are their independence from transport (or higher) 
layer protocol semantics and the possibility of co-existence 
with any form of network layer encryption as proposed with 
IPsec. 

(2) The particular problem of Snoop is that it violates the e2e
semantics of the congestion control scheme found in most 
implementions of TCP. The reason is the suppression of DUPACKs, 
which filters out a congestion signal, and a proposed NACK
scheme. 
When sending *to* the mobile host, packets dropped at a 
bottleneck link between the wireless link and the mobile host 
are mistaken for damage loss by the TCP-aware cache. The 
congestion signal (the three DUPACKs) is not propagated back to 
the sender. For packets sent *from* the mobile host, the NACK 
scheme causes a problem. If the wireless link itself (or any 
other link between the mobile host and the wireless link) 
becomes the bottleneck, packets lost due to congestion cannot be 
discriminated from those lost due to damage. A NACK is sent in 
either case, and the sender again relies on external means to 
get the congestion signal (e.g., the infamous source quench).

***********************
Why does TCP only retransmit 12 times?
***********************

(1) Imagine the following scenario: you are on the way out of 
your office. Before you get in the car you initiate a large ftp 
from your PDA (connected via short-range radio to your 
IP-cell-phone which in turn is connected to the Internet via 
some decent packet radio link like, say, GPRS). Just before you 
get home you are out of GPRS coverage for about 15 minutes. What 
happens? TCP will do 12 retransmission (~ 9 minutes) and then 
give up with a RST. Too bad, very frustrated you have to 
re-initiate your 2 MBytes ftp. 

(2) Why does TCP do that? How does TCP know that this is what 
the application wanted?

(3) Clearly, you can build a robust ftp but then you have to 
build that into every application layer protocol. That's the 
wrong design decision!

(4) What you need is a TCP sender that does not "give up" until 
told so by the application !!! Retransmitting the oldest unacked 
packet every 64 seconds (or even less frequent for those who 
think that 64 seconds is aggressive) should not be a big deal. 
The application will often re-initiate the very same session 
(with very same data) anyway. Closing the connection _has to be_ 
an appication layer decision.

***********************
*Fully-*Reliable Link Layer Error Recovery - Definition and 
a few Notes
***********************

(1) I'm using "reliable" to imply: error-free (to the degree 
that CRCs can protect a frame), in-sequence delivery, and 
removal of duplicate *LL frames*.

(2) I'm using "link layer error recovery" (LL ARQ for short) as 
opposed to "local error recovery" to imply independence from 
transport layer (or higher) protocol semantics, i.e., no 
inspection of transport layer headers in any way.

(3) I'm using the term "fully-" to imply that the LL sender 
tries _really_ hard to get a packet across the link. Still, if 
the LL sender did not succeed after a max of MSL/TTL the packet 
is discarded. This is probably where the confusion comes from. 
I could call this "very persistent semi-reliable" but I think 
"fully-reliable" is still a valid term here. If there was no 
such thing as the MSL and the deployment concerns coupled with 
that, one could define an even more persistent version of 
"fully-reliable LL ARQ" ....

(4) Above that, only TCP flows (this is where the concept of 
flow-adaptive LL comes in) receive this "special" treatment of 
fully-reliable LL ARQ. By default a UDP packet does not get any 
(or only a very few up to an extra delay of, say, 20 ms - as it 
could be realtime voice) retransmissions and is simply discarded 
if received in error by the LL receiver.

(5) The key benefits of this approach is that 
    I.  It allows to aggressively optimize FEC/ARQ towards high 
        throughput (as mentioned before).
    II. after temporary link outages, it avoids an idle wait for 
        a backed-off transport layer retransmission timer to 
        expire (up to 64 seconds). If, on the other hand, 
        packets are still queued at the (wireless) LL, the 
        end-to-end flow of data is re-started immediately after 
        the link has become available again.

Note, 

(a) that this has nothing to do with queue management 
techniques. I'm certainly not proposing to have the LL 
retransmit packets that need to be dropped. 
Packets that are dropped by the network layer according to 
simple drop-tail or a more advanced RED- or RED/ECN-style queue 
management will never be handed down to the LL. But once handed 
to the LL (and if they are TCP packets) they will stay there 
until they have been successfully transmitted or the MSL/TTL 
"packet discard timeout" has expired. Cleary, during link 
outages this will lead to congestion and many dropped packets. 
So what? That's exactly the right signal we want to give the 
senders of those _reliable_ flows: "Hey sender, you are sending
too fast to get that data to the other end reliably!" 

(b) that there is no interworking problem with any form of IPsec 
here.

(c) that this does not at all require "the link/end-end ARQ 
strategy has to operate on a shared database and neither could 
work in isolation from the other. "

(d) that this says nothing about FEC. Clearly, a well-engineered 
link requires the "right" level of FEC. 
Question: what is "right"? (see below)

(e) For "typical" situations where there is at least some (e.g. 
wireless) connectivity this definition is not a big deal as 
usually a few LL retransmissions do the job when the wireless 
link is well designed, i.e. has the right level of FEC. This 
definition is only interesting in situations of temporary link 
outages.

(f) that this does not bring you X.25-style of hop-by-hop acking 
of packets. However, in theory, when a path is made up of N of 
these kind of wireless links it would be just that. But I 
guarantee the vigorous FEC-only fans that in this (hypothetical)
case and without LL ARQ, your TCP receiver will not ever see a 
single packet (not even the initial SYN). Just make N large 
enough. No problem with LL ARQ, though.

///Reiner

---

From: "Perry E. Metzger" <[email-masked]>
Date: 24 Jun 1999 18:17:57 -0400

> after most of the gun smoke has cleared out ... 

Oh, we haven't even begun to fire.

>    already give you) improve e2e performance.

I hope I never find myself on the other end of a link like this.

TCP is not sacred -- we keep tinkering with it all the time -- but it
is sad to see people mangling it badly over and over again in
the name of "improving performance". We see this sort of thing all the 
time -- you know, the manufacturer who "discovers" his workstations
are "faster" without slow start, the manufacturer that "discovers" the 
wonderful benefits of a "reliable"[sic] link layer, etc. In the end,
we get the same trouble over and over again.

Those who forget the past are doomed to repeat its mistakes over and
over. 

Perry

---

From: Hari Balakrishnan <[email-masked]>
Date: Thu, 24 Jun 1999 18:02:35 -0400

> which filters out a congestion signal, and a proposed NACK

Reiner,

This is wrong.  Great care was taken to ensure that e2e congestion
control isn't compromised.

> the sender. 

Retransmissions from the base station are done only on the arrival of
the 2nd dupack (i.e., you know that 2 segments reached).  Even if it had
retransmitted on the first one, this retransmission would follow packet
conservation.  Furthermore, it is done only after checking local queue
state on the interface.

> For packets sent *from* the mobile host, the NACK

For this case, Snoop uses ELN.  No NACK scheme.  ELN is set, by the base
station, only on dupacks for that have been known to have been lost due
to corruption.
		   data
	Wireless ----------> Base ===============> Receiver
	sender		     Stn
		   ACKs
		  <--------        <------------

Base stn keeps track of holes in seq space that correspond to
corruption.  A sequence hole added to list of holes if missing data is
detected and if both local queue len and queue len on interface of
wireless sender are not large (this is piggybacked w/ link header). 
Both instantaneous and average lens are used (avg reqd for RED).  

When Base stn sees (dup) acks AND that ack corresponds to a segment in
the list of holes, we know it was lost to corruption.  So, it sets ELN
bit in header.  Sender rxmits without window halving when it sees dup
ACK w/ ELN.  Conservation of packets still holds.

Hari

---

From: Reiner Ludwig <[email-masked]>
Date: Thu, 24 Jun 1999 15:49:33 -0700

At 03:02 PM 6/24/99 , Hari Balakrishnan wrote:
[...]
>conservation.  Furthermore, it is done only after checking local queue

When sending *to* the mobile host and Snoop does NOT sit on the last-hop
link you effectively can't know why you are seeing the DUPACKs. The reason
could be congestion loss further down the path or (as Snoop assumes) damage
loss on the wireless link.

>station, only on dupacks for that have been known to have been lost due

How can you know that when you don't have access to the link layer that
discarded that packet/frame because of a CRC error ?

Summary: 
Only if Snoop knows that it sits on the last-hop link AND it if has access
to the link layer then are the e2e congestion semantics not violated. Or
else, Snoop does not do anything and trivially then does not violate those
semantics. Correct?

///Reiner

---

From: Lloyd Wood <[email-masked]>
Date: Fri, 25 Jun 1999 14:06:40 +0100 (BST)

> packets that need to be dropped. Who would do such a thing? 
[..]
> retransmit packets that need to be dropped.  

Naive question:  since the IP checksum checks the header only and not
the payload, surely it could be argued that LL ARQ'ing packets with
silent errors that have crept into their payload from earlier links -
errors that are only detected at end when UDP/TCP checksums are done
and the packets are then dropped - is actually already doing what
you're not proposing you do?

(Okay, this is an argument for per-LL checksumming, if not LL
 ARQing, so at least you learn where the error occurred and can
 possibly do something about it. Using existing higher-layer
 checksums? Detecting and dropping errored stuff ASAP makes sense to 
 me; the endpoints can't do anything about the errors, while the local
 link can. Very much a wireless-unreliable-link consideration,
 though.)

> .... on satellite links the packet transmission delay 

in-flight packet transmission time, right? (actual satellite delay is
rather large...)

> is usually much smaller than the "typical" error length.

Er, no. long bursty errors seen in the satellite channel are actually
an artefact of the FEC coding schemes chosen to make the satellite
links 99.999... reliable. (Turbo codes should improve this further,
but deployment on satellite is a relatively slow business.)

> Thus, there is not much to gain from LL ARQ.

that's because semi-decent FEC is already there. For GEO bent-pipe
transponders, ARQ would add around half a second's delay for each
resend, in any case. It's not really an option.

It's less clear-cut in LEO; if you're coming back from a number of
long hops through a radio/laser intersatellite-link mesh and your last
hop is through the atmosphere to the ground - less reliable - there
may be a case for implementing LL ARQ on the downlink. (the only
working example of this would be Iridium, which hasn't launched its
promised 4800bps reliable data/fax service yet afaik for some
unknown reason.)

> On long-thin wireless links (e.g., 

Belabouring the obvious here: Is this an argument that the longer IP
packets are and the more time they take to traverse a link relative to
errors on the link, the more you need LL ARQ?

(I'm extrapolating this as leading to fully ARQ'd jumbograms in many
 places once they finally get big enough. Or really really small IPv6
 path MTUs for better error resilience. Setting appropriate MTU size
 seems an issue.)

Interesting that your example and V.42 modems are both running over
systems originally intended for voice; anyone got an example of a good
link designed from scratch for data with LL ARQ because it really was
seen as the best choice? TIA.

> enough. No problem with LL ARQ, though.

Interesting. That justifies the existence of AX.25 completely.

L.

we now return you to your regularly scheduled discussion of
How Ethernet Is Actually Supposed to Work.

<[email-masked]>PGP<http://www.ee.surrey.ac.uk/Personal/L.Wood/>