Subject: Re: When non TCP/IP literate people design cable modem systems

From: [email-masked]
Date: Wed, 23 Jun 1999 14:09:55 -0700

*> 
  *> TCP is an end-to-end connection based transport layer, whose
  *> reliability mechanisms are geared towards losses due to network
  *> congestions (slow start is the problem). For certain short hop link
  *> layers, such as on either side of a cable TV line, or say, a wireless
  *> network, where the packet losses may be due to the physical channel or
  *> external interference, there are benefits to having reliability
  *> mechanisms on the link layer protocols. There is no way you can
  *> guarantee 100 % reliability, but you can have retransmissions within
  *> temporal windows that do not cause TCP timers to expire.
  *> 
  *> The long ping times are probably due to improper implementation. It
  *> has no bearing on where reliability mechanisms must be implemented.
  *> 
  *> Ciao,
  *> Kumar.
  *> 

This is the first-order conventional wisdom.  This wisdom was
challenged by Hari Balakrishnan's ACK snooping.  Here is a paraphrase
of a discussion of this topic that took place in 1995:

	  Steve Deering asked: what about link layer reliability
	  approaches?  HariB: If the link layer is unaware of the
	  transport protocol, you can get redundant retransmissions.
	  Deering:  Even if it's blind, it should still be a win.
	  Lixia Zhang, Craig Partridge: The problem is dup acks.  If
	  TCP packets arrive out of order, you get dup acks, and the
	  sender will resend even though the link layer has already
	  filled the hole.

	  Summary: if it's *reliable* (and in order) across the link,
	  yes, link layer reliability wins, but if it's not, or if loss
	  *is* okay, then the link layer is the wrong place to fix it.

Bob Braden

---

From: John Leong <[email-masked]>
Date: Wed, 23 Jun 1999 15:51:18 -0700

>  HariB: If the link layer is unaware of the
>  .....

I would actually flip the statement around as in if the transport
protocol does not know or cannot properly guess the link layer's latency
characteristic, redundant transmission can happen.  I would also map the
link layer error recovery to that of [potentially highly variable] link
latency.  In the modem example observed, the dynamic range of that
latency [and corresponding RTT] is huge enough to cause temporary time
out value underestimation leading to redundant retransmission.

Within bound, I do actaully think there are good justification for link
layer retransmission.  When I am in a hotel sitting in front of a crappy
phone line, it is better to have the terminal server's modem retry
(LAPM) a few times instead of having the retries to be all done
end2end.  In the latter case, quite a few upstream bandwidth would be
wasted in delivering packets to the terminal server only to be chewed up
by the chicken wire. Again, all within limit and relatively consistant
enough for TCP to reasonably accurately calibrate the RTT.

Regards,
John
--
---------------------------------------------------------
Bell Labs Research       [email-masked]
4995 Patrick Henry Dr.                  Tel: 408-567-4459
Santa Clara, CA 95054                   Fax: 408-567-4448

---

From: George Michaelson <[email-masked]>
Date: Thu, 24 Jun 1999 10:01:21 +1000

Is there not a dimension of bandwidth/delay issue here about where you
want link layer re-train/retransmit?

After all, your cited example is the last mile link, lowest bandwidth in
the path (in most cases) with a total end-to-end b/w measured as a small
fraction of the total path width. Its likely to define the path-MTU constraint
and will almost certainly be where the packet queue is in any 
routing/forwarding active device.

But Cable is going to be anywhere from double to 10x faster, and may exceed
other path elements for speed. The only shared attribute is that its also
the last mile. It might not be the shortest MTU, and it might not be where
the delay queue is.

Also, there is the question of how frequently the link layer has to invoke
its recovery function. Most modems give up very quickly under noise. The
cable system seems to be designed to be super-persistant. After all, its
an 'always on' service.

cheers
	-George
--
George Michaelson         |  DSTC Pty Ltd
Email: [email-masked]    |  University of Qld 4072
Phone: +61 7 3365 4310    |  Australia
  Fax: +61 7 3365 4311    |  http://www.dstc.edu.au

---

From: John Leong <[email-masked]>
Date: Wed, 23 Jun 1999 18:02:29 -0700

> want link layer re-train/retransmit?

Yup.  To the higher level protocol, link level error recovery and
retransmission (assuming it does not in itself cause duplicated
packets!) will appear as wide fluctuation of latency. I think
retransmission at link level is acceptable as long as the resultant
increase in latency range is kept within a "reasonable" factor of the
end2end RTT without such retransmission.

In the example given, potential frequent and huge variations between few
ms to 300,000 ms due to persistent retry can really do some interesting
things to RTO estimations.

> Its likely to define the path-MTU constraint

Not sure where path MTU comes in ...

Regards,
John Leong

---

From: Kumar Balachandran <[email-masked]>
Date: Thu, 24 Jun 1999 13:56:14 -0400 (EDT)

Let me try to repeat this with more clarity than before. Wireless
links for one usually have bandwidth restrictions. Link layer
reliability mechanisms are better suited to utilizing system resources
effectively. This is mostly because the unit of data transmission on
the link layer is more suited to the characteristics of the physical
medium. TCP was designed for reliable high bandwidth links where most
losses occur due to congestion in the network. TCP was not designed to
handle a link layer for any specific medium and makes no assumptions
about transfer modes. Mechanisms such as snoop TCP are valiant
attempts at making TCP do what it was not designed for, but lets not
belabour the point. I would use snoop TCP to handle interfacing
between a legacy link layer and the TCP/IP protocol suite. I would not
use snoop TCP if I had control over transfer mode design.

Ciao,
Kumar

>>>>> "braden" == braden  <[email-masked]> writes:

    braden>   *> *> TCP is an end-to-end connection based transport
    braden>   layer, whose *> reliability mechanisms are geared
    braden>   towards losses due to network *> congestions (slow start
    braden>   is the problem). For certain short hop link *> layers,
    braden>   such as on either side of a cable TV line, or say, a
    braden>   wireless *> network, where the packet losses may be due
    braden>   to the physical channel or *> external interference,
    braden>   there are benefits to having reliability *> mechanisms
    braden>   on the link layer protocols. There is no way you can *>
    braden>   guarantee 100 % reliability, but you can have
    braden>   retransmissions within *> temporal windows that do not
    braden>   cause TCP timers to expire.  *> *> The long ping times
    braden>   are probably due to improper implementation. It *> has
    braden>   no bearing on where reliability mechanisms must be
    braden>   implemented.  *> *> Ciao, *> Kumar.  *>

    braden> This is the first-order conventional wisdom.  This wisdom
    braden> was challenged by Hari Balakrishnan's ACK snooping.  Here
    braden> is a paraphrase of a discussion of this topic that took
    braden> place in 1995:

    braden> 	  Steve Deering asked: what about link layer
    braden> 	  reliability approaches?  HariB: If the link layer is
    braden> 	  unaware of the transport protocol, you can get
    braden> 	  redundant retransmissions.  Deering: Even if it's
    braden> 	  blind, it should still be a win.  Lixia Zhang, Craig
    braden> 	  Partridge: The problem is dup acks.  If TCP packets
    braden> 	  arrive out of order, you get dup acks, and the
    braden> 	  sender will resend even though the link layer has
    braden> 	  already filled the hole.

    braden> 	  Summary: if it's *reliable* (and in order) across
    braden> 	  the link, yes, link layer reliability wins, but if
    braden> 	  it's not, or if loss *is* okay, then the link layer
    braden> 	  is the wrong place to fix it.

    braden> Bob Braden

---

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

Kumar Balachandran <[email-masked]> writes:
> links for one usually have bandwidth restrictions.

All links have bandwidth restrictions. No link has infinite bandwidth.

The whole point of the various TCP congestion control mechanisms is to
assure that TCP doesn't try to take more of the bandwidth than is
actually available. That it can do so without explicit signaling is
one of the really amazing discoveries of the last twenty years.

> Link layer reliability mechanisms are better suited to utilizing
> system resources effectively.

Such a blanket statement is on its face untrue. "It depends".  Error
correcting codes on each data link layer packet on a wireless link are
useful if the uncorrected packet error rate would be high, but such
codes do not add any sort of variable delay to the link. The issue is
when you start dealing with retransmission mechanisms, especially ones
that cause delay. TCP already has retransmission built in, and a badly
designed link layer can very easily get into a fight with TCP, and
drastically increase link congestion.

In particular, it is critical that no link layer reliability mechanism
attempt to mask congestion conditions. Protocols that evaluate packets
and request retransmission are a very bad mechanism in any data link
layer that has to carry IP, but things can get even worse: if a
retransmission occurs because the link was too congested to transmit
frames, you have just broken TCP's ability to detect congestion and
back off, and you've created a monster in which congestive collapse is 
all but certain.

Perry

---

From: John Leong <[email-masked]>
Date: Thu, 24 Jun 1999 15:41:29 -0700

> TCP was designed for reliable high bandwidth links where most
> losses occur due to congestion in the network.

I am not sure that is necessary the case. The definition of 'reliable'
and 'high' when TCP was first deployed back in the early 80's ARAPNET
days were somewhat different from what we have today.  56K was consider
magic and some of the long haul microwave links and even the analog T1
trunks at that time can be pretty spotty.

> TCP was not designed to handle a link layer for any specific medium
> and makes no assumptions about transfer modes.

That is indeed true.  In fact as an end2end protocol, one cannot assume
there is only one link or even one medium type between the 2 ends.  Fine
tuning for the first hop local link may have some limitations.

Regards,
John Leong

---

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

> 	  sender will resend even though the link layer has already

SACK deployment fixes that, yes? So then LL ARQ is good because it
encourages SACK deployment...

L.

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

---

From: Cannara <[email-masked]>
Date: Sun, 27 Jun 1999 12:03:28 -0700

John, Kumar is right on the 1st point too.  TCP had nothing in its design
(still hasn't) that would allow it to distiguish an error loss from a router
loss.  The fact that TCP has only one policy for loss recovery -- time out
retransmit, back off -- means that a very low error rate (say <1%) carries a
very high performance hit (>20%).  This is a critical area for transport
improvement.

Alex

-- 
650-854-9040; fax: 0612
-----------------------
Dr. A. B. Cannara
V. P. Customer Services
NetPredict (.com)
Menlo Park, California
650-853-8301

---

From: John Leong <[email-masked]>
Date: Mon, 28 Jun 1999 11:45:31 -0700

> TCP had nothing in its design (still hasn't) that would allow it to
distiguish
> an error loss from a router loss.

Strictly speaking, that is indeed correct.

However, if "error loss" is in the form of corrupted data due to high
BER at the link level, or IP/link layer segmentation, then such error
will ikely to show up as TCP checksum.  Side note, interesting but not
toally relevant to this discussion : while IP segmentation could be be
discovered by MTU path discovery, link layer segmentation cannot.
Samples of link layer segmentation would included LAPM by V.42 modem and
SAR of ATM etc.

Given I touch on SAR, may also like to point out the obvious that link
layer can be a simple thing like an Ethernet but it can also be a
complex full blown congestion prone network such as ATM .... or for
those who have been around long enough and remember the last days of the
ARAPNET, the link layer was actually an X.25 network which mercifully
did not last that long before ARAPNET was shut down.  Now, that brings
to yet another intersting point I raised earlier on ....

One cannot assume and end2end path consists of only 1 link layer
network.  Indeed, the more typical senario is for the station to be
connected to an (wired or wireless) Ethernet which is connected to a T1
(cable modem, DSL, FR or SMDS) to an ATM backbone (even though I am not
a fan of ATM, that is the reality in most cases) which may be connected
to the reverse of the above.  The bottom line is that and end2end
protocol cannot assume a specific link layer behaviour.  TCP does a good
job in not making such assuming and dynamically tune the end2end path
performance (through continuously calibrating the RTT).  On the flip
side, I think all respectable link layers should make "reasonable"
effort to ensure deliver of its payload.  While the 300 seconds sample
that started this discusion is clearly out of wack, doing CSMA without
CD for Ethernet (regardless of calling it retry or retransmit) or CSMA
without CA for wireless LAN (to address hidden node) is also
unreasonable.  I suspect the problem is very real rather than academic
since most of the unreliable links are at the user's end of the equation
(wireless and dialup link).  Without "reasonable" link quality
(including link recovery protocols), a server has to continuously retry
.... adding a lot of redundant traffic into the backbone and major
congestion points which could contribute to an early congestion collapse
of the Internet.

Back to TCP.

> The fact that TCP has only one policy for loss recovery -- time out
> retransmit, back off

That is sort of yes and no.  Unlike SDLC and its derivatives (HDLC,
LAPx), TCP cannot use out of sequence packet arrival as a hint of a
packet loss (given that is possible in IP network) and immediately call
for retransmit (REJ). Hence the error feed back loop is much slower and
has to depend on the sender to time out waiting for Ack.  On the other
hand, TCP does requires the receiver of out of sequence segments to send
duplicated ACKs which essentially have the same semantic as REJ.
However, unlike SDLC like protocol, retransmission is done immediately
on the reception of REJ, TCP wait for a few duplicated ACK before doing
that ... so, in a sense, one can consider that to be a timer of sort
(hence my sort of yes and no).

Best regards,
John Leong

---

From: Jamshid Mahdavi <[email-masked]>
Date: 28 Jun 1999 11:55:00 -0700

> encourages SACK deployment...

SACK does not change the "3 DUPACKS" check in Reno TCP.  Although,
with SACK, there are all sorts of new options.  So, if a segment is
out of order by more than 3, three ACKs with SACK blocks will come
back, and the sender will retransmit.

--Jamshid

---

From: Reiner Ludwig <[email-masked]>
Date: Mon, 28 Jun 1999 13:53:32 -0700

At 11:45 AM 6/28/99 , you wrote:
>will ikely to show up as TCP checksum.  

Just as a side note: usually such errors do _not_ show up at the TCP layer
because  those corrupted packets have in most cases already been discarded
by a link layer protocol, e.g., PPP, that had a frame checksum error. 

While the function "error recovery" does not always make sense, the
function "error detection" is of fundamental importance for a link layer
protocol.

Which link layer protocols do not perfom "error detection"?

///Reiner

---

From: John Leong <[email-masked]>
Date: Mon, 28 Jun 1999 14:39:43 -0700

> by a link layer protocol, e.g., PPP, that had a frame checksum error.

Good point.  The exception is when the link layer chop up the TCP
segment into smaller chunks (ATM cell, LAPM frame and wireless packets).

> the function "error detection" is of fundamental importance for
> a link layer protocol.

Also  good point.

---

From: Reiner Ludwig <[email-masked]>
Date: Mon, 28 Jun 1999 14:49:00 -0700

>segment into smaller chunks (ATM cell, LAPM frame and wireless packets).

Hmmm, I really don't know much about ATM but isn't there some AAL layer
that takes care of packet framing and also of "error detection" by means of
per framed IP packet CRCs?

Also cellular telephone networks especially designed to also carry data,
like GSM and IS-95, chop up the TCP segment (the IP packet) into smaller
chunks but then rely on PPP to do the packet framing and "error detection".

///Reiner

---

From: Lloyd Wood <[email-masked]>
Date: Mon, 28 Jun 1999 22:56:31 +0100 (BST)

On Mon, 28 Jun 1999, John Leong wrote:

> Just as a side note: usually such errors do _not_ show up at the TCP
> layer because  those corrupted packets have in most cases already
> been discarded by a link layer protocol, e.g., PPP, that had a frame
> checksum error.
> 

I think the exception is actually the general case, and that it shows
up more often than you might think.

L.

hence TCP Boston.

---

From: Cannara <[email-masked]>
Date: Tue, 29 Jun 1999 15:21:03 -0700

Excellent points.  I can send various examples, if anyone is interested.

Alex

---

From: Dan Grossman <[email-masked]>
Date: Wed, 30 Jun 1999 13:35:59 -0400

When non-ATM literate people analyse TCP over ATM :-)...
> >layer
AAL5 has a length field and a well-understood 32-bit CRC.  It was designed to 
detect lost cells, single bit errors within cells, multiple bit errors within 
cells, multiple error bursts, and mis-inserted cells.  There was extensive 
informal analysis of this during the development of AAL5, which was reflected 
in contributions to T1S1 (sorry, they're packed in a box somewhere, so I don't 
have cites).  There was a later, more rigorous, analysis of the error 
detection propreties of AAL5 published in SIGComm proceedings a few years ago 
(I think Craig Partridge might have been an author, but memory does not 
serve).  

There is a negligable probability of corrupted frames showing up at the TCP 
layer due to a failure of AAL5 to detect errors.

---

From: Bill Sommerfeld <[email-masked]>
Date: Wed, 30 Jun 1999 13:42:06 -0400

> by a link layer protocol, e.g., PPP, that had a frame checksum

Hmm.  A random probably bogus thought:

Has anyone looked into the effects of passing up a specially
marked "error frame", with as much header as can be salvaged?  (about
all TCP could do in reaction to that would be to send a duplicate ack
with a "lost due to noise" bit set in it which might keep things going
again after a loss).

On ethernet-like links where corruption due to noise is likely due to
collisions (i.e., congestion), this would clearly be a bad idea, but
all the world's not ethernet..

> Which link layer protocols do not perfom "error detection"?

I can think of two..
	- SLIP 
	- the 10 megabit proteon token ring (which MIT used for its campus
	  backbone network in the late 80's).

None of these are particularly modern..

					- Bill

---

From: John Leong <[email-masked]>
Date: Wed, 30 Jun 1999 13:35:56 -0700

> layer due to a failure of AAL5 to detect errors.

Good point.  For that matter, bad TCP frame is also unlikely if LAPM is
doing its job.  Many years ago, I was a proponent of not bothering with
UDP checksum (since cycle time was expensive then) given Ethernet was
already doing checksum (by hardware).  I have to eat humble pie when I
actually got UDP packets with checksum errors.  That turned out to be a
hardware problem during the transfer from the procssor memeory of my
machine to the NIC card Tx buffer.

> There was extensive
> have cites).

Does that suggest ATM is history  ;-)

Best regards,
John Leong