Subject: network device and tcp-flow packet ordering

From: sankar ramamoorthi <[email-masked]>
Date: Fri, 9 Jun 2000 20:12:56 -0700 (PDT)

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: Alan Cox <[email-masked]>
Date: Sat, 10 Jun 2000 12:39:04 +0100 (BST)

> network device like router or a switch.

Not that I am aware of. You can drop, duplicate or re-order frames at will

> packets inside a tcp flow are not reordered - but am

It should.

> TCP timers? What is the effect on SACK?

Throw it through a simulator. Thats what simulators are for. I think you
will it looks not too unreasonable until you get errors at which point it
will look a lot lot uglier than if the frames were almost always in order.

Also bench the host CPU utilisation at both ends - that will rise materially
if the frames are not ordered and thus following the fastpaths.

Alan

---

From: Craig Partridge <[email-masked]>
Date: Sat, 10 Jun 2000 08:23:25 -0400

There's no RFC that says it.

However, Jon Bennett, Nick Shectman and I published a paper showing how
packet reordering really trashes TCP performance in IEEE/ACM Trans. on
Networking last year.

Craig

In message <[email-masked]>, sankar ramamoor

---

From: Lloyd Wood <[email-masked]>
Date: Sun, 11 Jun 2000 02:59:29 +0100 (BST)

> There's no RFC that says it.

thank goodness. hurrah. etc.

> packet reordering really trashes TCP performance in IEEE/ACM Trans. on

imo this really indicates a problem with the state of the art of TCP's
congestion algorithms; TCP deserves to be trashed, and fast recovery
could be a lot more flexible here. (cf section IV C of that Dec. 1999
paper.)

relevant work I don't think has been mentioned in this thread yet:

http://www.ietf.org/internet-drafts/draft-allman-tcp-lossrec-00.txt

draft-allman-tcp-lossrec-00.txt [Enhancing TCP's Loss Recovery Using
Early Duplicate Acknowledgment Response, M. Allman, H. Balakrishnan,
S. Floyd]

This draft discusses selectively _lowering_ the fast recovery
threshold under certain specific low-window conditions (and cites the
paper Craig mentions above).

AFAIK there are as yet no concrete implementation proposals for TCP to
selectively _raise_ this threshold in the face of continual
misordered delivery.

(no doubt because that's a much less conservative and open-ended
 change that would require a lot more study of the dynamics under a
 wide range of conditions, and probably some experimental operational
 observation as well).

Raising the TCP sender's 3-dupack threshold to increase its tolerance
when experiencing packet/ack reordering won't restore the level of TCP
goodput to that of a perfectly ordered flow, which is the maximum
bound - but you can improve throughput and gradually approach that
bound as you raise the threshold. (I've shown this in simulation for
part of a submitted paper.)

Work done within the network reordering a flow of in-transit packets
is work wasted on not doing useful delivery.

imo any packet network should be _encouraged_ to gratuitously misorder
packets (especially if locally appropriate for delivery efficiency)
without worrying about the endeffects - it's the easiest way to keep
the equipment simple (cf the workconserving appendix to Bennett et
al's paper).

Having all the network work like hell to maintain the illusion that an
ordered circuit-like flow can be maintained all the time is a Crime
Against Nature. (Well, entropy.)

Put reordering complexity in the receiver where it belongs. Once.
Not in every implementation of every protocol in every switch.
Improve TCP, and build *simpler* fast packet networks.

L.

read can this understand you perfectly the point you if. Yoda as does.

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

---

From: "Eric A. Hall" <[email-masked]>
Date: Sun, 11 Jun 2000 00:04:24 -0700

> Improve TCP, and build *simpler* fast packet networks.

I agree with you irt prev-gen gear, but in those cases the switch path was
linear. Out-of-order data is/was due to bad design of something rather than
a side effect of "normal" read-and-forward operation. In this case though it
seems to be a given that a parrallel switch will most likely cause a
significant amount of reordering to occur naturally which is an unplanned
phenomenon for TCP.

But it also probably depends on the end-to-end bandwidth, too. Reordering
probably won't be a problem on end-to-end connections that are only a
fraction of the bandwidth, since they won't get into the parrallel switch
fast enough to get out-of-ordered by the switch (unless the feeds are more
than a fraction, which is not the scenario). On pipes that can be filled
with a single flow or which can feed the switch at a significant rate
anyway, I bet it knocks performance way down on the effected end-points. In
this case, maybe ISPs won't care about reordering but researchers will care
very much. Then we'll just need faster all over again.

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.

---

From: "Eric A. Hall" <[email-masked]>
Date: Sun, 11 Jun 2000 00:04:15 -0700

---

From: Lloyd Wood <[email-masked]>
Date: Mon, 12 Jun 2000 15:51:20 +0100 (BST)

On Sun, 11 Jun 2000, Eric A. Hall wrote:

> In this case though it

yes.

> than a fraction, which is not the scenario). 

unfortunately, TCP is extremely bursty in how it sends segments
back-to-back (especially as it opens a window). As a result of this,
reordering will still occur when the end-to-end connection occupies a
tiny fraction of the available bandwidth.

(This could be avoided by widely implementing rate-based pacing in
 TCP, but rate-based pacing has been shown to suffer when used against
 the more-aggressive traditionally bursty TCP [*], so there's no
 incentive for deploying that. We're stuck at a local maximum on the
 surface of TCP performance.)

[*] http://www.cs.washington.edu/homes/savage/
    Understanding the Performance of TCP Pacing,
    Amit Aggarwal, Stefan Savage, and Tom Anderson,
    Proceedings of the 2000 IEEE Infocom Conference, Tel-Aviv,
    Israel, March, 2000.

> won't want a product that does it.

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

L.

---

From: Greg Minshall <[email-masked]>
Date: Mon, 12 Jun 2000 09:15:28 -0700

let me just mention to all and sundry that *independent* of fast retransmit, 
etc., re-ordering is a code path in a TCP that is more expensive than the 
normal "in-order" delivery path.  for me, this is the fundamental reason to 
try to avoid re-ordering in the network.

notice, i did not say "eliminate"; rather, "try to avoid" (as in "not 
gratuitously deliver packets out of sequence", as in the PILC link design 
draft quoted).  by doing *some* work in the net, we can improve the situation 
for the end system, and that is worth doing.  (though, in the original query 
with a parallel network device, "some work" may be a fair amount of work in 
that single system; it would be nice, though, if the idiosyncrasies of a given 
implementation didn't permeate through the net out to end systems.)

---

From: "Jamal Hadi Salim" <[email-masked]>
Date: Mon, 12 Jun 2000 12:58:45 -0400 (EDT)

>  _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: Alan Cox <[email-masked]>
Date: Mon, 12 Jun 2000 19:36:32 +0100 (BST)

> >  _seen_ turns out to be is almost secondary...)

People by lines by bandwidth. So we'll see people selling 'reordering packet
line optimisers' for your routers. It would probaly make a nice little Linux
netfilter project in fact 8)

> switching" hardware hits the market. 

Long term you are probably right. There is a limit to the rate you can get
bits down a set of wires and order them sanely the other end. However the
changeover is likely to be very messy since a few of these boxes doing
say 2% re-ordering turns the packet stream to mush by the time its passed
through 3 or 4.

I imagine the sudden doubling of network use at most ISP's will encourage them
to switch back. Especially when their customers complain about poor 
performance - but yes in the end it has to be solved.

Alan

---

From: Craig Partridge <[email-masked]>
Date: Mon, 12 Jun 2000 15:17:29 -0400

In message <[email-masked]>, Ll

>    Proceedings of the 2000 IEEE Infocom Conference, Tel-Aviv,

I'll be the first to say that I haven't fully asorbed the results of
this particular paper (having just skimmed it briefly) but we didn't see
signs of these problems in the simulation work we've done (published at
GLOBECOM at the same time Amit published his other TCP pacing paper).

See http://mimas.lcs.mit.edu/~jokulik/tcppacing.html for details.

We've now got a working tcp pacing implementation and are starting real
world tests, so perhaps we'll know more soon (I'll also make a note
to cross compare our results with U. Wash).

Thanks!

Craig

---

From: Craig Partridge <[email-masked]>
Date: Mon, 12 Jun 2000 16:12:37 -0400

In message <[email-masked]>, Alan Cox writes:

>bits down a set of wires and order them sanely the other end.

This is not true.  There are some very good algorithms, some published,
some not (e.g. in the patent process) that give you full or very near
full utilization of the parallel links but retain ordering.

The best known public version is the WASHU algorithm (Varghese was one
of the authors) published, I believe, in IEEE/ACM Trans. on Networking
a few years ago.

Another algorithm, which takes a very different approach from the WASHU
algorithm and has lower complexity, is the subject of a patent I co-authored
and I'm told will be issued shortly.

Craig