Subject: Re: network device and tcp-flow packet ordering

From: Sally Floyd <[email-masked]>
Date: Sun, 11 Jun 2000 09:35:21 -0700

I think it is fairly clear that currently, TCP gives abysmal
performance in the presence of significant reordering.  (When the
TCP receiver receives out-of-order packets, the TCP receiver sends
duplicate acknowledgements to tell the TCP sender.  The TCP sender
then does a Fast Retransmit, retransmitting the packet presumed to
be lost, and cutting the congestion window at least in half.  This
is true of Tahoe, Reno, NewReno, and SACK TCP, and, I presume, of
any TCP implementation more recent that 1988.)

I believe that the first step in making TCP more robust to reordering
is in the D-SACK (duplicate-SACK) extension to SACK, "An Extension
to the Selective Acknowledgement (SACK) Option for TCP",
"http://search.ietf.org/internet-drafts/draft-floyd-sack-00.txt".
This has already been approved by the IESG for Proposed Standard,
and is on the RFC editor's to-do queue.

I have a draft paper, "A Report on Some Recent Developments in TCP
Congestion Control", that discusses how the D-SACK option could be
used to make TCP more robust to reordering.  I am appending an
excerpt from that paper below.  As the excerpt makes clear, there
is a significant amount of work that would have to be done to take
the information in the D-SACK option and come out with viable,
tested algorithms that allow TCP to be robust to persistent
reordering...

- Sally
--------------------------------
http://www.aciri.org/floyd/
--------------------------------

From "A Report on Some Recent Developments in TCP
Congestion Control":

An initial step towards adding robustness in the presence of
unnecessary Retransmit Timeouts and Fast Retransmits is to give
the TCP sender the information to determine when an unnecessary
Retransmit Timeout or Fast Retransmit has occurred..  This first
step has been accomplished with the D-SACK (for duplicate-SACK)
extension \cite{FMMPR99} that has recently been added to the SACK
TCP option.  The D-SACK extension allows the TCP data receiver to
use the SACK option to report the receipt of duplicate segments.
With the use of D-SACK, the TCP sender can correctly infer the 
segments that have been received by the data receiver, including
duplicate segments. 

When the sender has retransmitted a packet, D-SACK does not allow
TCP to distinguish between the receipt at the receiver of both the
original and retransmitted packet, and the receipt of two copies  
of the retransmitted packet, one of which was duplicated in the
network.  If necessary, TCP's timestamp option could be used to
distinguish between these two cases \cite{AP99,L99}.  However, in
an environment with minimal packet replication in the network,
D-SACK allows the TCP sender to make reasonable inferences, one
round-trip time after a packet has been retransmitted, about whether
the retransmission was necessary or unnecessary.
    
If the TCP data sender determines, a round-trip time after
retransmitting a packet, that the receiver received two copies of
that segment and therefore that the packet retransmission was most
likely unnecessary, then the sender could have the option of
``undoing'' the halving in the congestion window.  The sender can
``undo'' the recent halving of the congestion window by increasing
the Slow-Start threshold ssthresh to the previous value of the old
congestion window, effectively slow-starting until the congestion
window has reached its old value.  In addition to restoring the
congestion window, the TCP sender could adjust the duplicate
acknowledgement threshold or the retransmit timeout parameters, to
avoid the wasted bandwidth of persistent unnecessary retransmits.

The first part of this work, providing the information to the sender
about duplicate packets received at the receiver, is done with the
D-SACK extension.  The next step is to evaluate specific mechanisms
for identifying an unnecessary halving of the congestion window,
and for adjusting the duplicate acknowledgement threshold or
retransmit timeout parameters.  Once this is done, there is no
fundamental reason why TCP congestion control cannot perform
effectively in an environment with persistent reordering.

---

From: Luigi Rizzo <[email-masked]>
Date: Mon, 12 Jun 2000 07:06:54 +0200 (CEST)

Overnight thinking on TCP and reordering.

Given the following:
    * the receiver knows there is reordering;
    * reordering will occur in less than 1RTT;
    * the receiver can compute the RTT
    * we already tolerate delayed ACKs
    * the first duplicate ACKs will not trigger any new data transmission
      (maybe excet with SACK, i am a bit out-of-date on this)
wouldn't it make sense for the receiver who sees out-of-sequence
delivery of packets to withold the ACKs for such packets until
a) the hole is filled, or b) a small timeout has elapsed (this can be
of the same order of the delayed ack timer, or half the RTT if we have
a local estimate available).

The only drawback i see is some burstiness in the flow, as the ACKs
which would reach the sender would liberate a number of packets
(this could be a problem as reordering might not occur at the
bottleneck), and of course one should use byte-counting rather than
ACK-counting to open the window (this is easy and has been documented
by someone, right ?)

	cheers
	luigi

-----------------------------------+-------------------------------------
  Luigi RIZZO, [email-masked]  . Dip. di Ing. dell'Informazione
  http://www.iet.unipi.it/~luigi/  . Universita` di Pisa
  TEL/FAX: +39-050-568.533/522     . via Diotisalvi 2, 56126 PISA (Italy)
  Mobile   +39-347-0373137
-----------------------------------+-------------------------------------

---

From: Fred Baker <[email-masked]>
Date: Mon, 12 Jun 2000 13:11:04 -0700

>     * the receiver knows there is reordering;

the problem is that the receiver doesn't necessarily know that. It may know 
that some packet previous in this session had been reordered, but it 
generally has no visibility of other sessions on the same machine (which 
may use different routes) or sessions to different machines. On the first 
reordered packet in a session, it knows only that the message it has 
received is not the next one it expected to receive. The discrepancy may be 
due to reordering, and it may be due to loss. In the latter case, you'd 
like to recover as quickly as you could.

>a local estimate available).

Maybe. An issue arises with delaying the Ack in the presence of a 
measurement of RTT - the delay is itself part of the RTT. So I would argue 
that only *these* Acks want to be delayed - only the Acks that might 
trigger a retransmission. And when you do send them, it would be either to 
acknowledge the now-in-order segment when it arrived and subsequently to 
trigger further transmissions (would rather not see a burst) or to trigger 
the retransmission, so in either case you actually want the specific Ack, 
not a collected Ack of several segments.

I tend to think Sally's approach, being explicit rather than heuristic, is 
a better one.

---

From: Luigi Rizzo <[email-masked]>
Date: Mon, 12 Jun 2000 23:07:57 +0200 (CEST)

> the problem is that the receiver doesn't necessarily know that. It may know 
...
> like to recover as quickly as you could.
...
> I tend to think Sally's approach, being explicit rather than heuristic, is 

but as you say, the receiver doesn't necessarily know that there
is reordering, nor does the sender, so either you wait or you have
to make your bet :) So my idea woud be that you start by assuming
that there is no reordering, but when you see reordering once, you
become biased on the other one.

For those arguing that delaying ACKs is detrimental to RTT measurements:
yes, it is, but we have been living with delayed acks triggered by
applications reads for >10 years now...

	cheers
	luigi

---

From: "Wilson C. Chung" <[email-masked]>
Date: Fri, 16 Jun 2000 14:41:25 -0700

What are the typical instruction set extension on
a CPU so that implementing TCP/IP/UDP network stacks
would be more efficient?

Tx, Wilson Chung
VMLabs

---

From: Craig Partridge <[email-masked]>
Date: Mon, 19 Jun 2000 18:42:29 -0400

>a CPU so that implementing TCP/IP/UDP network stacks

That's a hard question to answer, since a lot depends on what the instruction
set already offers and whether your focus is on TCP/UDP/IP (i.e. a host) or
just IP (e.g. a router).

Here are some general comments about instruction sets on a host system using
TCP/UDP/IP:

* the instruction set should have good support for 8, 16, and 32 bit
    field manipulations in registers (e.g., get a value out of a particular
    offset, update it, put the value back in at that offset)

* a carry bit is *very* valuable

* have enough registers that, after the registers used by the compiler for
   stacks, return locations, etc, you can put all 40 bytes of the TCP and
   IP header into registers and still have 3 or 4 registers left over...

These a broad guidelines -- your architecture will vary.

Craig

---

From: Greg Minshall <[email-masked]>
Date: Mon, 19 Jun 2000 18:06:58 -0700

> a CPU so that implementing TCP/IP/UDP network stacks

add-with-carry is a nice instruction; it makes it somewhat faster to do IP 
checksums...