Subject: Re: Comments to "Advice for Internet Subnetwork Designers"

From: Phil Karn <[email-masked]>
Date: Wed, 22 Nov 2000 16:45:02 -0800

Going back to some mail of yours from early August, I've been giving
your comments a lot of thought, and I have to admit I'm moving closer
to your point of view on some things.

>>What you really want to avoid are the nasty interactions between TCP
>>and link/physical layer retransmissions that can occur in certain link
>>operating regions.

>People often talk about those interactions as if there where so many of 
>those. What are those interactions you are talking about?

>I only know of two such interactions:
>(1) spurious timeouts that lead to a go-back-N retransmisison mode in TCP, and

A compliant TCP never does go-back-N; it only retransmits the oldest
unacked segment.  But even this could be a spurious retransmission if the earlier
delay was caused by a link layer retransmission.

>(2) out-of-order delivery at the link layer that falsely triggers fast 
>retransmit / fast recovery.

I think this is not as significant a problem in practice, since most
link layers already enforce packet ordering.

>Given that PILC recommends that link layers should avoid out-of-order 
>delivery (also for the sake of not causing trouble for TCP/IP header 
>compression) this leaves spurious timeouts as the cardinal problem.

But now I'm no longer sure that ordered delivery at the link level is
even a good thing.

The basic problem is that ordered delivery can only be done by
intentionally delaying any packets that would otherwise be delivered
out of order. This is harmless or even beneficial if the delayed
packets belong to the same TCP connection.  But if they don't, then
you merely impair the performance of the other connection(s) with no
compensating benefit.  (True, the link *could* peek at the TCP and IP
headers and only enforce in-order delivery of packets belonging to the
same TCP connection, but that would be an egregious layer violation --
i.e., it wouldn't work with IPSEC).

I believe this is much the same reasoning that originally led to the
Internet architects to say that IP need not deliver packets in
sequence, that reordering is a transport layer responsibility.

Transport protocols can compensate for many subnetwork and Internet
ills, including packet loss, duplication and reordering. But high
delay is one subnetwork ill that a transport protocol can *never*
overcome.  That's why I think any low-level mechanism that
deliberately introduces delay should be viewed with great skepticism.

This also leads to the conclusion that if packet reordering spuriously
triggers TCP's dup ack mechanism, then this is really TCP's fault and
it should be fixed inside TCP. (I didn't say this would be easy, though.)

This leaves one remaining argument for ordered delivery on links: VJ
header compression. So we could simply say that in-order delivery is
important only if you plan to implement VJ header compression.

Anyway, back to retransmission interactions.

>>But whenever the link layer retransmits, the RTT spikes
>>and there's a spurious TCP retransmission.

>This is a simply not true. You have to let things go really bad to force a 
>spurious timeout in TCP. Depending on your path characteristics especially 

You say it's rare, but it is something I've seen quite often in TCP
traces. I think this difference is simply due to our having operated
over different environments.  Our air links tend to have relatively
high latencies even without link level retransmissions, and more
significantly this latency tends to dominate that of the total
Internet path.  So we probably see many more cases of spurious TCP
retransmissions being triggered by link retransmissions than you do.

Also, our link protocols have historically been implemented in cell
phones with severely limited memory resources, and this has led us to
implement non-persistent link ARQ schemes that don't require a lot of
buffer memory.  Of course, this problem is going away over time.

But perhaps you're right that, overall, it's better to not limit the
persistence of the link layer ARQ scheme. Fair queuing might help
limit the effect of the spurious retransmissions on other competing
flows, for example. Also, having a highly persistent link layer ARQ
might be the best way to help TCP recover quickly from sustained link
outages.

Phil

---

From: Lloyd Wood <[email-masked]>
Date: Thu, 23 Nov 2000 13:04:25 +0000 (GMT)

> link layers already enforce packet ordering.

That's not what Bennett and Partridge observed in the backbone:
   
J.C. Bennett, C. Partridge, and N. Schectman, Packet Reordering is Not
Pathological Network Behaviour, IEEE/ACM Transactions on Networking,
7(6), pp. 789-798, 2000.

> deliberately introduces delay should be viewed with great skepticism.

...including highly-persistent ARQ.

> it should be fixed inside TCP. (I didn't say this would be easy, though.)

Yes - and tweaking the dupack threshold is being examined by a few
people.

L.

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

---

From: Dr G Fairhurst <[email-masked]>
Date: Thu, 23 Nov 2000 13:50:05 +0000

See also:

draft-ietf-pilc-link-arq-issues-00.txt

> compensating benefit.

I thought PILC recommended PER-FLOW ordering. This may in many
protocols be implemented as PER-LINK or per-host-pair-of-IP-addresses,
but these are design decisions taken during the link implementation.

There are cases for out-of-order delivery between flows.
Low persistency may also reduce the head-of-line link reciever blocking
which you mention.

> (True, the link *could* peek at the TCP and IP

That is re-ordering within a flow - I think you mean.

> important only if you plan to implement VJ header compression.

V-J isn't recommended with lossey links....

There are more arguments for low link delay in:
draft-ietf-pilc-link-arq-issues-00.txt

> might be the best way to help TCP recover quickly from sustained link

FQ helps at the input to the link-ARQ, it can't help if the link propagation
delay is high and there are frames under-going error recovery.

> Phil

Gorry

------------------------------
http://www.erg.abdn.ac.uk/users/gorry

---

From: Reiner Ludwig <[email-masked]>
Date: Thu, 23 Nov 2000 16:17:19 +0100

>to your point of view on some things.

I'm glad to hear this. Ideally, we can get our views converged on this 
matter so that we can get this section "Reliability and Error Control" 
straight in the "Advice for Internet Subnetwork Designers".

Maybe, we can make this a topic at the PILC meeting in San Diego. I would 
be happy to present my view ... if the WG chairs think that that's appropriate.

>delay was caused by a link layer retransmission.

Please, check out section 3.1 in this paper:
http://www.acm.org/sigcomm/ccr/archive/2000/jan00/ccr-200001-ludwig.html

A compliant TCP has no other chance but to go into go-back-N after a 
spurious timeout, i.e., a spurious timeout forces TCP into the go-back-N.

I have just submitted an Internet Draft to TSVWG on this matter:
http://search.ietf.org/internet-drafts/draft-ludwig-tsvwg-tcp-eifel-alg-00.txt

>link layers already enforce packet ordering.

I agree with respect to existing link layers. I'm not so sure, though, 
whether we should also recommend in-order delivery for future wireless links.

>i.e., it wouldn't work with IPSEC).

Again, I agree except to the layer violation concerns.

I would also like to stronlgly promote clean designs, i.e., without layer 
violations. But to implement what I call inter-flow out-of-order delivery 
(as opposed to intra-flow out-of-order delivery, i.e., o-o-o delivery 
within a single flow), you do not need to have the link layer inspect IP 
headers.

Instead, you could, e.g., run multiple logical link layers (one per flow) 
across a hop, and have IP distribute the packets onto those links based on 
port numbers. "one per flow" clearly does not scale, but for the first/last 
hop this shouldn't be a problem.

Yes, as with so many things, this does not work with IPsec.

>it should be fixed inside TCP. (I didn't say this would be easy, though.)

The ID I mentioned above is such a fix (inside TCP).

>important only if you plan to implement VJ header compression.

The evolved VJ header compression, RFC2507, optionally uses sequence 
numbers within the compressed headers to deal with links that re-order. So, 
this would eliminate the "one remaining argument". However, there would be 
no benefit in having the link layer do o-o-o delivery in this case, since 
now we have the header decompressor delaying the packets to bring them back 
into order.

>over different environments.

Plus, it very much depends on your TCP (timer granularity, restart of the 
timer after an ACK, ...). We see more spurious timeouts with LINUX for 
example. Still, with the current RTO calculation, spurious timeouts should 
be rare.

>Our air links tend to have relatively

I don't know what you mean when you say "our air links", but I did quite a 
few measurements in GSM which certainly qualifies as high latency, and also 
it dominates the e2e RTT. Still, spurious timeouts were extremely rare (in 
BSD) and when they occured, then this was always in the beginning of the 
connection. This is since the RTO had not been given enough time to adapt.

>buffer memory.  Of course, this problem is going away over time.

I see highly persistent LL ARQ as independent from buffer memory. When some 
people hear highly persistent LL ARQ, they often think that this equals 
"buffering for ever". *No, it does not!* The queues need to remain 
appropriately small also with highly persistent LL ARQ.

>persistence of the link layer ARQ scheme.

I think it should be limited to 64 seconds sicne this is TCP max. RTO. 
There is really no point in delaying a packet beyond that. In addition, 
should the system hosting the link layer get into memory problems, then 
this might also be a reason to drop (from front) packets before 64sec have 
passed.

>Fair queuing might help
>flows, for example.

I agree, if you seperate flow classes (UDP vs. TCP) at the link layer, 
there needs to be some scheme in place that devides the link's bandwidth 
between those classes. E.g., 30% for elastic TCP traffic, the rest for 
delay-sensitive traffic.

>Also, having a highly persistent link layer ARQ

Exactly.

///Reiner

---

From: Lloyd Wood <[email-masked]>
Date: Thu, 23 Nov 2000 16:09:43 +0000 (GMT)

On Thu, 23 Nov 2000, Reiner Ludwig wrote:
> Phil Karn wrote in replky to Reiner:
>
> >unacked segment.  But even this could be a spurious retransmission if the 
> >earlier delay was caused by a link layer retransmission.
> 

even with use of SACK and knowledge of the receiver window state? (Did
I miss a timeout causing the SACK scoreboard to be discarded?)

puzzled,

L.

---

From: Reiner Ludwig <[email-masked]>
Date: Thu, 23 Nov 2000 23:03:35 +0100

>I miss a timeout causing the SACK scoreboard to be discarded?)

Yes, even with SACK. Note, that the first thing(s) a sender sees after a 
spurious timeout are the returning ACKs that were triggered by the 
*original* segments arriving at the receiver. Those ACKs will not carry any 
SACK info.

Sure, *after* the go-back-N has been performed, the sender will then find 
out what went wrong when it receives D-SACK info in the ACKs that are 
triggered by the duplicate segments sent during the go-back-N. But at that 
point it's too late; an entire flight has already been resent unnecessarily.

///Reiner

---

From: Phil Karn <[email-masked]>
Date: Thu, 23 Nov 2000 23:43:31 -0800

>That's not what Bennett and Partridge observed in the backbone:

Thanks for the pointer to that paper, as I wasn't aware of it.
I just finished reading it. It's very good, and I recommend it
to the group. I found this rather poor quality PDF copy:

http://www.acm.org/pubs/articles/journals/ton/1999-7-6/p789-bennett/p789-bennett.pdf

I should have been more clear in my choice of words. I was thinking of
a single point-to-point link, not a collection of parallel links
and/or reordering routers along a given Internet path.  I think it's
still correct to say that most physical links still enforce packet
ordering, even if those links are frequently used in parallel and/or
with switches and routers (like the DEC Gigaswitch discussed in that
paper) that do frequently reorder packets.

I generally agree with the paper's conclusions: reordering does happen
in the real Internet and it does cause problems with TCP performance.
TCP should be made more robust to reordering *and* the subnetworks
should be designed to avoid it whenever possible.

So how's this for a LINK recommendation: subnetworks should try to
deliver packets in order when possible, but not if doing so impairs
the subnetwork's capacity or increases its latency.

Comments?

Phil

---

From: Lloyd Wood <[email-masked]>
Date: Fri, 24 Nov 2000 13:31:38 +0000 (GMT)

> point it's too late; an entire flight has already been resent unnecessarily.

isn't this really an argument against bursts and in favour of TCP
pacing?

L.

---

From: Phil Karn <[email-masked]>
Date: Fri, 24 Nov 2000 08:58:15 -0800

>I miss a timeout causing the SACK scoreboard to be discarded?)

I'm still confused here. I have always understood TCP to requre (or at
least strongly encourage) that when a timeout occurs, only the oldest
unacknowledged segment is retransmitted. If this fills a hole in the
receiver's reassembly queue (the receiver has already received
subsequent segments), the receiver will ack as much as it can.

This is not classic "go-back-N" as it was implemented in HDLC LAPB,
for example. In LAPB, anything received after a missing frame was
discarded, and the sender resends all N frames from the missing frame
onward. Obviously this is much less efficient than resending just the
missing frame.

So perhaps by "go back N" you simply meant that TCP has to go back and
fill in the missing packet with a retransmission, not retransmit the
entire window's worth of data?

Phil

---

From: Dr G Fairhurst <[email-masked]>
Date: Fri, 24 Nov 2000 18:09:37 +0000

You make many interesting points...

>Reiner Ludwig wrote:
>I would also like to strongly promote clean designs, i.e., without layer
>   violations. But to implement what I call inter-flow out-of-order delivery >
(as opposed to intra-
>  flow out-of-order delivery, i.e., o-o-o delivery

>   hop this shouldn't be a problem.

I agree with this idea.

I like the idea of decoupling the ARQ between different flows. Ordering does
not require persistence, or vice versa - yet many link protocols I have seen do
both of these or neither.  I know there are protocols which do not, and
I am very interested in thinking about the implications of this.  Have you
thought about the pros and cons of using parallel links with individual ARQ?

>   appropriately small also with highly persistent LL ARQ.

I think this is where I begin to get confused?  When the link carries some TCP and

some UDP flows.  The UDP sources don’t simply stop because some of their
data is lost or waiting transmission in the link layer.  Then, don’t you end up
with an excess of data queued at the link transmit interface. If the window/queue
is small, then  you drop?  Do you have to drop UDP preferentially to keep
TCP performance?

I wonder what happens when you have many many TCP flows all sharing then,
don’t you need to buffer a lot? or drop a lot?

Gorry Fairhurst