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

From: "Howard Berkey" <[email-masked]>
Date: Sun, 11 Jun 2000 12:13:09 GMT

>Such a product would likely end up becoming self-selective in its 
market.
>Maybe technically the product can reorder data all it wants, but the 
market
>won't want a product that does it.

With good reason.

---

From: [email-masked]
Date: Mon, 12 Jun 2000 10:49:31 +0300

Hi,

The PILC group draft "Advice for Internet Subnetwork Designers"
<draft-ietf-pilc-link-design-02.txt> has the following passage
about packet reordering in subnetworks:

Packet Reordering
   The Internet architecture does not guarantee that packets will arrive
   in the same order in which they were originally transmitted, and
   transport protocols like TCP must take this into account.  However,
   we recommend that subnetworks not gratuitously deliver packets out of
   sequence.  Since TCP returns a cumulative acknowledgment (ACK)
   indicating the last in-order segment that has arrived, out-of-order
   segments cause a TCP receiver to transmit a duplicate acknowledgment.
   When the TCP sender notices three duplicate acknowledgments it
   assumes that a segment was dropped by the network and uses the fast
   retransmit algorithm [Jac90,APS99] to resend the segment.  In
   addition, the congestion window is reduced by half, effectively
   halving TCP's sending rate.  If a subnetwork badly re-orders segments
   such that three duplicate ACKs are generated the TCP sender
   needlessly reduces the congestion window, and therefore performance.

MikaL

> -----Original Message-----
> From: EXT sankar ramamoorthi [mailto:[email-masked]]
> Sent: 10. kesäkuuta 2000 6:13
> To: [email-masked]
> Subject: network device and tcp-flow packet ordering
> 
> 
> Hi,
> 
> Is there a reference in any rfc's which says
> to the equivalent of 
> 'Thou shall not reorder packets in a flow' by a
> network device like router or a switch.
> 
> I am trying to make a case that a parralel
> network-device (a device with a lot of parallel
> engines inside it) should make effort to ensure that
> packets inside a tcp flow are not reordered - but am
> losing the argument. Without any effot the device has
> the potential to reorder packets inside tcp flows
> because of the parallism.
> 
> Also what would be the effect of such reordering on
> TCP timers? What is the effect on SACK?
> 
> Any input on this point is welcome.
> 
> Thanks,
> 
> -- sankar ramamoorthi --
> 
> 
> __________________________________________________
> Do You Yahoo!?
> Yahoo! Photos -- now, 100 FREE prints!
> http://photos.yahoo.com
>

---

From: Vern Paxson <[email-masked]>
Date: Mon, 12 Jun 2000 00:53:12 PDT

> the problem i see is that the delay should be tuned to the
> bottleneck bandwidth -- i.e. it should be larger than the transmit
> time for a packet or two.

The paper discusses this a bit.  Basically, yes, if you're worrying about
single packet reorderings.  But if you are only affected by double-packet
reorderings (which is the case for lowering the threshold to 2), then this
is much less of a problem, because it requires a very large reordering
elsewhere in the network (one large enough that a packet is delayed by
more than the link's propagation time for the packet):

	\footnote{ However, as noted above, some network paths have
	substantial \emph{minimum} reordering times.  For today's
	slower-rate paths, these times can well exceed the $20$~msec figure
	we have explored.  For such paths prone to reordering, we would
	expect any approach based on delaying $\wait = 20$~msec to lead to
	significant, unnecessary retransmissions, and poor performance.
	This problem is considerably diminished for $N_d = 2$ because then
	we must have quite substantial (in terms of time) reordering in
	order to generate enough dups to falsely trigger fast
	retransmission.}

> that's an interesting observation, because the sender knows the
> RTT already (not accurately, though). So the heuristic could be something
> like "do a fast retransmit and assume congestion after N dupacks
> _or_ 1 RTT from the last in-sequence ack, whichever comes first" ?

If I'm wrong about the above, then perhaps; but I think you can indeed
get away with just waiting for 20 msec.

		Vern

---

From: [email-masked]
Date: Mon, 12 Jun 2000 14:01:24 +0300

Hi,

I am thinking that a sender could treat retransmission timout
as a fast retransmit if it has received at least one dupack
in the meantime. If there are no dupacks, congestion is the
probable cause for the timeout. However, if the sender is
receiving dupacks something must be getting through. The sender
could still do a normal fast retransmit on 3rd dupack as usual.

This would be a very simple change to existing implementations
and, assuming reasonable window sizes, would probably increase
fast retransmit opportunities considerably. No hard data on this
though.

	MikaL

> > increase in false retransmits.  It also works for the 
> *sender* to wait
> > 20 msec before entering fast retransmission on the 2nd dup 
> ack, and in
> > that case you only need to deploy the change on the sender side.
> 
> 	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
> -----------------------------------+--------------------------
> -----------
> > 		Vern
> > 
>

---

From: Mark Allman <[email-masked]>
Date: Mon, 12 Jun 2000 12:26:34 -0400

> 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 ?)

Yep:

    Mark Allman. On the Generation and Use of TCP
    Acknowledgments. ACM Computer Communication Review, 28(5),
    October 1998.  
    http://roland.grc.nasa.gov/~mallman/papers/acks.ps

    Mark Allman. TCP Byte Counting Refinements. ACM Computer
    Communication Review, 29(3), July 1999. 
    http://roland.grc.nasa.gov/~mallman/papers/bc-ccr.ps

allman

---

From: "Howard Berkey" <[email-masked]>
Date: Mon, 12 Jun 2000 14:02:57 GMT

Of course, another way to look at it is that routers that don't make a 
best effort to maintain packet order will be noticed (and shunned) if 
they cause a drop in overall throughput on today's TCP implementations.

>
>On Mon, 12 Jun 2000, Lloyd Wood wrote:
>
>> if reordering resulting from parallelism leads to a product with
>> faster overall throughput, there's some incentive to deploy the
>> product and then related improvements to TCP.
>> 
>> (people buy computers based on MHz ratings; they'll buy networking
>>  hardware based on Gbps throughput. What the actual performance
>>  _seen_ turns out to be is almost secondary...)
>
>Well said -- I concur. 
>
>So this goes to the original poster:
>
>If you can do it cheaply and get higher throughput, dont worry about
>packet re-ordering. End systems should fix that. 
>Of course, i realize the above statement sounds like blasphemy. 
>Unfortunately it is reality. People are building parallelized path
>switches; and if you think this is bad wait until "content
>switching" hardware hits the market. 
>
>cheers,
>jamal
>
>

---

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: "Howard Berkey" <[email-masked]>
Date: Sun, 11 Jun 2000 12:13:09 GMT

market.
market

With good reason.