Subject: [Tsvwg] What's the benefit of out-of-order processing?

From: Sam Liang <[email-masked]>
Date: Mon, 17 Sep 2001 12:54:38 -0700 (PDT)

RFC2960 for SCTP lists the lack of out-of-order processing as the first
major drawback of TCP:

   "TCP provides both reliable data transfer and strict order-of-
    transmission delivery of data.  Some applications need reliable
    transfer without sequence maintenance, while others would be
    satisfied with partial ordering of the data.  In both of these
    cases the head-of-line blocking offered by TCP causes unnecessary
    delay."

  Is there any study done on evaluating the effect of this TCP
"deficiency"?  What applications really need to and are capable to do
out-of-order processing? Can video over IP or voice over IP applications
process frames out-of-order? With SCTP's order-of-arrival delivery, how
much performance boost can be achieved over TCP, in terms of increased
throughput and reduced delay?

  Thanks,

Sam

_______________________________________________
tsvwg mailing list
[email-masked]
http://www1.ietf.org/mailman/listinfo/tsvwg

---

From: "David G. Andersen" <[email-masked]>
Date: Mon, 17 Sep 2001 16:06:42 -0400 (EDT)

Sam Liang just mooed:

> [Snip:  SCTP provides out-of-order processing, unlike TCP...]
> 

   For a start, see:

http://www.cs.berkeley.edu/~suchi/papers/raman-icnp00.ps

   ITP provides out-of-order delivery of frames to an image rendering
program (jpeg, etc.).  On lossy links, it results in better perceptual
quality of the images more quickly, compared to TCP.

  -Dave

--
work: [email-masked]                          me:  [email-masked]
      MIT Laboratory for Computer Science           http://www.angio.net/

---

From: "Jonathan M. Smith" <[email-masked]>
Date: Mon, 17 Sep 2001 16:31:59 -0400

David Feldmeier's "chunks" proposal examined this idea in a 1993 SIGCOMM 
paper, "A Data Labelling
Technique for High-Performance Protocol Processing and Its Consequences", 
pp. 170-181
-JMS

---

From: Craig Partridge <[email-masked]>
Date: Mon, 17 Sep 2001 16:37:59 -0400

I suspect some SCTP folks will have better answers, but here's a
small perspective.

About 14 years ago I did a little bit of study with RDP (RFC 908).
RDP supported out-of-order delivery of segments.

You could get some performance leverage by delivering segments as they
arrived to applications that knew where to put the segments in their
memory or disk (so, for instance, file transfer went a bit faster because
the receiving system was almost always saving data to the file -- it didn't
get the feast/famine mode that TCP gives you when a segment gets dropped).  

Craig

In message <[email-masked]>, Sam Liang writes

---

From: "Amr A. Awadallah" <[email-masked]>
Date: Mon, 17 Sep 2001 13:29:17 -0700

Large file downloads is a very good example application. For example, a 1GB 
can be sent in any order with no retransmission, then at end of the cycle a 
single NACK is sent for all missing packets and then iteratively go through 
the next batch and so on until all packets belonging to the file are 
delivered. Some loss signaling will still be needed for TCP congestion control 
to work. This might not lead to much improvement of goodput (since all packets 
still need to be delivered), but it simplifies the task of an ftp server with 
many receivers, since it does not need to handle as many ACK packets.

Take a look at the work from digital fountain:

http://www.digitalfountain.com/technology/library

-- Amr

---

From: "David P. Reed" <[email-masked]>
Date: Mon, 17 Sep 2001 18:12:37 -0400

The digital fountain idea (see Luby's theoretical work at SRC and Berkeley) 
is a great example of the benefit in multicast mode.

Recording data from a data source (whose rate is less than channel 
capacity) that generates data at a constant rate to a recipient's disk 
drive also benefits from out-of-order processing, if you want to avoid 
cumulative delay buildup.

Concurrent computation under optimistic concurrency control (see, for 
example, my 1978 PhD thesis) is another example where out-of-order delivery 
can pay off.

Gossip protocols (see recent work by Minsky, Trachtenberg and Zippel) also 
can benefit.

At 01:29 PM 9/17/2001 -0700, Amr A. Awadallah wrote:
>Large file downloads is a very good example application. For example, a 
>1GB can be sent in any order with no retransmission, then at end of the 
>cycle a single NACK is sent for all missing packets and then iteratively 
>go through the next batch and so on until all packets belonging to the 
>file are delivered. Some loss signaling will still be needed for TCP 
>congestion control to work. This might not lead to much improvement of 
>goodput (since all packets still need to be delivered), but it simplifies 
>the task of an ftp server with many receivers, since it does not need to 
>handle as many ACK packets.
>

---

From: Qiaobing Xie <[email-masked]>
Date: Mon, 17 Sep 2001 17:51:56 -0500

This out-of-order processing service was specifically required by MEGACO
folks at one point (don't know whether they still use it). Some of
MEGACO messages were transaction-oriented and always carried a
transaction ID inside, this means that the receiver can often process
them independently.

The same is true for other transaction-oriented applications, such as
database query services.

-Qiaobing

---

From: Sam Liang <[email-masked]>
Date: Mon, 17 Sep 2001 16:06:34 -0700 (PDT)

Amr,

  You suggested an interesting way to transmit a large file.  However,
just as you alluded to, how are you going to do congestion control if you
don't send back any intermediate feedback with ACKs?  Congestion control
is a complicated problem. 

  You want to reduce the number of ACKs the ftp server processes, I think
we should try to figure out a way to reduce the ACK frequency, which still
provide certain feedback to the sender for congestion control purpose.

Sam

---

From: "Lars Eggert" <[email-masked]>
Date: Mon, 17 Sep 2001 16:50:14 -0800

> is a complicated problem.

It's still an interesting idea for a private high-speed, high-error link
(i.e. most drops from bit errors not congestion).

But I agree that it may not be the right thing for this Internet.

Lars
--
Lars Eggert <[email-masked]>               Information Sciences Institute
http://www.isi.edu/larse/              University of Southern California

---

From: "David P. Reed" <[email-masked]>
Date: Mon, 17 Sep 2001 21:40:23 -0400

Congestion control is useful, but it is not an "application benefit" (at 
least directly).  Out of order delivery has *nothing* to do with whether 
congestion control signals are sent, or how their coding (as ACKs or 
whatever) reflects their meaning.

At 04:06 PM 9/17/2001 -0700, Sam Liang wrote:
> 1GB

---

From: Sam Liang <[email-masked]>
Date: Mon, 17 Sep 2001 22:29:29 -0700 (PDT)

> whatever) reflects their meaning.

  I certainly was not saying out-of-order delivery had anything directly
to do with congestion control signals.  Because Amr was suggesting a way to
transfer a large file that didn't send any ACKs until the end, I was
asking if no intermediate ACKs were sent back, how did the sender detect any
congestion condition.  Of course if you want, you can invent other ways to
report congestion condition.  But it won't be trivial.

Sam

---

From: Jon Crowcroft <[email-masked]>
Date: Tue, 18 Sep 2001 08:21:40 +0100

Sam

most people working on a variety of techniques for
congestion control for multicast transport protocols have 
had to tackle the problem of efficient sampling of congestion
conditions without a "full on" feedback channel - c.g. 
pgmcc: A TCP-friendly Single-Rate Multicast Congestion Control Scheme 
Luigi Rizzo (Universita di Pisa) 
http://www.acm.org/sigcomm/sigcomm2000/conf/abstract/1-2.htm
and
Extending Equation-Based Congestion Control to Multicast Applications
Joerg Widmer (University of Mannheim), Mark Handley (ACIRI)
in sigcom2001
http://www.acm.org/sigcomm/sigcomm2001/p22.html
and the also mentioned receiver based schemes by vicisano and also
used by luby et al...

also, the HIPPARCH project did a bunch of work on ALF type protocols -
see
http://www.docs.uu.se/hipparch/
for links to papers

 >>> > > > throughput and reduced delay?

 cheers

   jon

---

From: "Phillip T. Conrad" <[email-masked]>
Date: Tue, 18 Sep 2001 11:16:41 -0400

In response to the question 

>out-of-order processing? 

I would call your attention to the following journal articles and conferences papers:

        Computer Networks, 31(7), 4/99, P. Amer, S. Iren, G. Sezen, P. Conrad, M. Taube, A. Caro 
        "Network-conscious GIF image transmission over Internet"

        ACM Multimedia 2001 (to appear, 9/01) P. Conrad, A. Caro, P. Amer,  
        "ReMDoR: Remote Multimedia Document Retrieval over Parital Order Transport"

        IEEE MILCOM 2001 (to appear, 10/01) P. Conrad, G. Heinz, A. Caro,  P. Amer, J. Fiore, 
        "SCTP in Battlefield Networks"

These, and over a dozen more papers and articles on the benefits of out-of-sequence processing, (including three Ph.D. Dissertations addressing the topic) can be found at http://www.eecis.udel.edu/~amer/PEL/poc/index.html.

I would also call attention to the seminal paper in this area:

        Clark and Tennenhouse, 1990: D. Clark and D. Tennenhouse. Architectural 
        Considerations for a New Generation of Protocols. Proc. SIGCOMM ‘90.

as well as to the work of Diot and Gagnon, (which while I argue in my dissertation---see the link above---that it understates the benefit of out-of-sequence processing, is nevertheless useful in establishing some baselines for the benefit.)

        Diot and Gagnon, 1999: C. Diot, F. Gagnon. Impact of out-of-sequence processing
        on the performance of data transmission. Computer Networks, 31(5), 475-492,
        Mar. 1999.

I hope these are helpful.

Phill Conrad
Asst. Professor, CIS Dept. Temple University.

---

From: Fred Baker <[email-masked]>
Date: Tue, 18 Sep 2001 08:41:00 -0700

At 12:54 PM 9/17/2001, Sam Liang wrote:
>What applications really need to and are capable to do
>out-of-order processing?

Authentication servers, for one. RADIUS uses UDP because it can bang on the 
server knowing that the odd dropped packet won't get in the way of other 
requests, eve if it is requesting them at hundreds or thousands per second. 
But that has congestion issues. The idea here is to be able to side-step a 
few lost requests and retransmit them, *and* have congestion avoidance.