Subject: Proposal (I-D) for extending HTTP to support out-of-order responses

From: Jeffrey Mogul <[email-masked]>
Date: Wed, 11 Apr 2001 11:46:02 -0700

A few weeks ago, I gave a short "Work In Progress" talk at
USITS (the "USENIX Symposium on Internet Technologies and
Systems") about some very early research results I had obtained
about the potential value of supporting out-of-order responses
in HTTP.

Several people came up to me after the talk and seemed very eager
to try out this kind of mechanism.  One person had even
implemented the idea in his own server code while the session was
in progress.  So it seemed like it might be a good idea to
propose a standard extension *before* lots of people started to
deploy this kind of thing.  Hence, I wrote up a simple proposal
as an Internet-Draft:

	Title		: Support for out-of-order responses in HTTP
	Author(s)	: J. Mogul
	Filename	: draft-mogul-http-ooo-00.txt
	Pages		: 14
	Date		: 09-Apr-01

	http://www.ietf.org/internet-drafts/draft-mogul-http-ooo-00.txt
	
    The introduction of persistent connections and pipelining
    into HTTP has resulted in potential performance benefits,
    but has also exposed the problem of head-of-line blocking.
    A simple, compatible, and optional extension to HTTP to
    allow a server to issue responses out of order could
    significantly reduce HOL blocking.  In this extension,
    clients add short ID fields to their requests, and servers
    echo these IDs back in their responses.  This extension is
    defined as a hop-by-hop rather than end-to-end mechanism,
    so it avoids much of the complexity of the end-to-end
    approach.
    
If members of the HTTP-WG mailing list have comments on this,
I'd be happy to receive them.

I want to stress that the research evaluation that might prove
(or disprove) the value of this approach has NOT been finished.
So it does not make sense to start an argument about whether
this is useful (unless someone else has already done a careful
evaluation of this kind of approach).

I'm just looking for comments on whether the protocol makes sense
(and, in particular, whether it might lead to screwups by caching
proxies that don't comply with the HTTP specifications).

Thanks
-Jeff

---

From: "Roy T. Fielding" <[email-masked]>
Date: Wed, 11 Apr 2001 17:05:40 -0700

That is a nice draft -- very complete and readable.  I remember discussing
the out-of-order question with some of the CERN folks in October 1994 at
the Chicago WWW conference.  The conclusion we came to was that it would
be easier to deploy SCP as an incompatible protocol than it would be to fix
all of the pre-standard HTTP/1.0 implementations, with more to gain from
doing the former.  I suspect we are still at that state.

One thing I've toyed with in the past was to use a hierarchical request
ID as a poor man's form of transaction identifier.  That is,

   TID: 1234

would be a simple request #1234, whereas

   TID: 888/1234

would indicate that request 1234 was part of transaction 888, and

   TID: 7/888/1234

would be transaction 7, sub-transaction 888, request 1234.  Naturally,

   TID: http://example.com/7/888/1234

would be the globally unique identifier, if such were needed.  Killing
two birds with one stone.

Cheers,

Roy T. Fielding, Chief Scientist, eBuilt, Inc.
                 2652 McGaw Avenue
                 Irvine, CA 92614-5840  fax:+1.949.609.0001
                 ([email-masked])  <http://www.eBuilt.com>

---

From: Patrick McManus <[email-masked]>
Date: Thu, 12 Apr 2001 16:03:22 -0400

> proxies that don't comply with the HTTP specifications).

2 thoughts, the first is just a throw-away:

1 - HTTP is stateless. indeed 2616 in its intro describes itself this
    way.. this is a pretty fundamental change, even as an optional
    extension.. so the intro should probably discuss it. that's all.

2 - This isn't a safety/correctness thing, but it seems like its a bit of
  a problem to effective usage..

given: 1] non-safe methods like POST or PUT are more likely  to be
          barrier-requests than GETs
 
       2] POSTs and PUTs can have large request bodies with
       significant upload latencies

       3] large request bodies benefit from the expect/100-continue
       mechanism

       4] real networks often have symmetric up and down capactiy that
       its a big win to leverage by overlapping.

I'm thinking about the expect/continue mechanism and how the execution
of a resource by a big POST or PUT is likely to be a sequence point
(and thus a barrier request). the time spent uploading the data would
do well to be overlapped with any outstanding responses even if it
can't be executed until outstanding requests have been processed.. but
if we mark it a sequence point we can't do that because the server
can't say 100-continue until all of the outstanding requests have been
satisfied.. it'd be nice to be able to separate the out-of-order
properties of the 100 with that of the final response so that a "start
sending" signal could be given OOO but the resource itself not
executed OOO. Obviously this requires some server side buffering, and
if it's not willing to do that it could simply do the 100 in-order.

the obvious way to do this seems to be to associate an attribute with
100-continue.. say ERID that works similarly to RID, but applies only
to the 100 response, not the final one.

hopefully the following case played out 3 ways will help illustrate:

assume we've got a POST(d) that takes 6 units to send, and 5 responses
that take 4(a), 5(b.cgi), 2(c), and 2(d), 3(e) to send. throw in the
kicker that b.cgi takes 5 units of time to calculate its response and
d takes 2 units to process the big post.

first, the we'll do the easy case where d is not a request-barrier.

Time    Upstream			    Downstream
----	---------			    -----------
1        GET /a, RID: 1       
2        GET /b.cgi, RID: 2                 200 - RID : 1 (1/4)
3        GET /c, RID: 3			    200 - RID : 1 (2/4)
4        POST /d, RID:4, Expect:..	    200 - RID : 1 (3/4)
5					    200 - RID : 1 (4/4)
6					    100 - RID : 4 (1/1)
7	POST/d, RID: 4 body (1/6)	    200 - RID : 3 (1/2)
8	POST/d, RID: 4 body (2/6)	    200 - RID : 3 (2/2)
9	POST/d, RID: 4 body (3/6)	    200 - RID : 2 (1/5)
10	POST/d, RID: 4 body (4/6)	    200 - RID : 2 (2/5)
11	POST/d, RID: 4 body (5/6)	    200 - RID : 2 (3/5)
12	POST/d, RID: 4 body (6/6)	    200 - RID : 2 (4/5)
13	GET /e, RID: 5			    200 - RID : 2 (5/5)
14					    200 - RID : 5 (1/3)
15					    200 - RID : 5 (2/3)
16					    200 - RID : 5 (3/3)
17					    200 - RID : 4 (1/2)
18					    200 - RID : 4 (2/2)

18 units.. pretty cool.. 

but now, what if /d (the post) is a request barrier under mogul-00?

Time    Upstream			    Downstream
----	---------			    -----------
1        GET /a, RID: 1       
2        GET /b.cgi, RID: 2                 200 - RID : 1 (1/4)
3        GET /c, RID: 3			    200 - RID : 1 (2/4)
4        POST /d,  Expect:..		    200 - RID : 1 (3/4)
5					    200 - RID : 1 (4/4)
6					    200 - RID : 3 (1/2)
7					    200 - RID : 3 (2/2)
8					    200 - RID : 2 (1/5)
9					    200 - RID : 2 (2/5)
10					    200 - RID : 2 (3/5)
11					    200 - RID : 2 (4/5)
12					    200 - RID : 2 (5/5)
13					    100 continue
14       POST/d, body (1/6)
15       POST/d, body (2/6)
16       POST/d, body (3/6)
17       POST/d, body (4/6)
18       POST/d, body (5/6)
19       POST/d, body (6/6)
20	 GET /e, RID: 5			    [wait - processing d]
21		 			    [wait - processing d]
22					    200   (1/2)	 
23					    200   (2/2)	 
24					    200 - RID : 5 (1/3)
25					    200 - RID : 5 (1/3)
26					    200 - RID : 5 (1/3)

26 units.. not as cool.. but what if the 100-continue could be out of
order, without making the final response out of order?

Time    Upstream			    Downstream
----	---------			    -----------
1        GET /a RID: 1       
2        GET /b.cgi, RID: 2                 200 - RID : 1 (1/4)
3        GET /c, RID: 3			    200 - RID : 1 (2/4)
4        POST /d, Expect: 100-c..; ERID=E1  200 - RID : 1 (3/4)
5					    200 - RID : 1 (4/4)
6					    100 - ERID : E1 (1/1)
7	POST/d, RID: 4 body (1/6)	    200 - RID : 3 (1/2)
8	POST/d, RID: 4 body (2/6)	    200 - RID : 3 (2/2)
9	POST/d, RID: 4 body (3/6)	    200 - RID : 2 (1/5)
10	POST/d, RID: 4 body (4/6)	    200 - RID : 2 (2/5)
11	POST/d, RID: 4 body (5/6)	    200 - RID : 2 (3/5)
12	POST/d, RID: 4 body (6/6)	    200 - RID : 2 (4/5)
13	GET /e, RID: 5			    200 - RID : 2 (5/5)
14					    [ wait - processing d]
15					    200 (1/2)
16					    200 (1/2)
17					    200 - RID : 5 (1/3)
18					    200 - RID : 5 (2/3)
19					    200 - RID : 5 (3/3)

19 units!

-Patrick

---

From: "Roy T. Fielding" <[email-masked]>
Date: Thu, 12 Apr 2001 13:58:35 -0700

>     extension.. so the intro should probably discuss it. that's all.

HTTP is stateless in the sense that all of the information needed to
interpret and handle a request is present in that request and not based
on a prior request's leftover state.  A RID doesn't change that in
principle, though it would certainly complicate the implementation
to handle out-of-order responses.  On the server-side, the ability
to have out-of-order responses makes it easier to partition pipelined
requests out to multiple server instances, which is one of the main
reasons why HTTP is stateless.

....Roy