Network Working Group Jeffrey Mogul, Compaq WRL
Internet-Draft 6 April 2001
Expires: 1 November 2001
Support for out-of-order responses in HTTP
draft-mogul-http-ooo-00.txt
STATUS OF THIS MEMO
This document is an Internet-Draft and is in full
conformance with all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet
Engineering Task Force (IETF), its areas, and its working
groups. Note that other groups may also distribute working
documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of
six months and may be updated, replaced, or obsoleted by
other documents at any time. It is inappropriate to use
Internet-Drafts as reference material or to cite them other
than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be
accessed at http://www.ietf.org/shadow.html.
Distribution of this document is unlimited. Please send
comments to the authors.
ABSTRACT
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.
Mogul [Page 1]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
TABLE OF CONTENTS
1 Introduction 3
1.1 Goals 3
1.2 Related proposals 4
2 Overview 6
2.1 Performance considerations 8
3 Specification 8
3.1 RID 8
3.2 Examples 9
3.3 RID-Barrier 11
4 Interoperability Considerations 12
5 Security Considerations 13
6 Acknowledgements 13
7 References 13
8 Author's address 14
Index 15
Mogul [Page 2]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
1 Introduction
The introduction of persistent connections into the HTTP protocol has
resulted in many potential performance benefits [8, 10].
Persistent-connection HTTP (P-HTTP) uses a single TCP connection for
the serial transmission of multiple requests and responses. However,
user-perceived latency may suffer in P-HTTP because of "head-of-line
blocking" (HOL blocking), in which a slow response may hold up all of
the subsequent responses. Various solutions have been proposed,
including block multiplexing below the HTTP layer, or various
TCP-layer improvements aimed at obviating persistent connections.
Instead of such complex multiplexing solutions, it appears that a
very simple, compatible extension to HTTP, allowing the server to
return responses out of order, could significantly reduce
head-of-line blocking. This proposal is based on several
observations:
- It is much easier to support out-of-order responses on a
hop-by-hop (per-connection) basis, rather than end-to-end
(see section 2).
- Delays in the network itself cannot be avoided by an
end-to-end block-multiplexing protocol, but a hop-by-hop
mechanism that reorders entire responses can hide some of
these delays.
- Many, if not most, static HTTP responses can be satisfied
after at most one disk-I/O delay. This nearly eliminates
the incentive to reorder data units smaller than an entire
response.
This proposal is designed as an extension to the HTTP/1.1 protocol
specification [5], and inherits all of the terminology defined in
that specification.
1.1 Goals
The goals of this proposal are to:
1. Substantially reduce the incidence of head-of-line
blocking related to pipelining in HTTP/1.1.
2. Protection against reordering of responses in cases where
reordering is not appropriate.
3. Interoperate with all compliant or conditionally compliant
implementations of HTTP/1.1, and with widely-used
implementations of earlier versions of HTTP.
4. Allow origin servers to deliver responses out of order.
Mogul [Page 3]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
5. Allow proxy servers to deliver responses out of order,
hence allowing a proxy to multiplex independent requests
on the same connection to an inbound server.
6. Allow relatively simple implementations in clients,
servers, and proxies.
7. Allow significant room for variation and innovation in the
implementations.
The goals do NOT include:
- Support for out-of-order responses from or to HTTP/1.0
systems, even those that implement the "Keep-alive" header
field.
- Support for end-to-end reordering of responses when one or
more intervening proxies are not able to reorder or do not
support this extension.
- Support for reordering or multiplexing portions of an HTTP
response message.
- Interoperation with "transparent proxy" systems that
explicitly violate mandatory requirements of the HTTP
specification.
- Specification of algorithms for efficient implementation of
this extension in client, server, or proxy systems.
These non-goals have been chosen to ensure the simplicity of the
extension.
1.2 Related proposals
Previous proposals have been offered to deal with HOL blocking, and
related problems, in HTTP.
The oldest approach, adopted before persistent connections were
widely considered, is the use of multiple simultaneous TCP
connections between client and server.
I would appreciate it if someone could supply me with a
reference to a document from Netscape (or elsewhere) describing
the earliest use of parallel connections from Web browsers.
In principle, this allows each response to proceed at its own rate.
In practice, the use of parallel connections over a given network
path can lead to unnecessary congestion (and hence inefficiency),
especially if the path is at or near capacity. The use of multiple
single-request connections also causes unwanted overheads (extra
packets, poor interaction with TCP slow-start, extra network
round-trips, and extra server overhead).
Mogul [Page 4]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
Balakrishan et al. [3] observed, based on traces of the official
1996 Olympics server:
- "A client using a collection of parallel connections
between a client and server is a more aggressive user of
the network than an application that uses a single TCP
connection. Throughput is positively correlated with the
number of active connections. When multiple connections are
concurrently active and one of them experiences a loss,
only half of the remaining ones on average experience a
loss. The combined congestion window of a group of parallel
connections does not decrease as much as the congestion
window of a single connection after a loss epoch.
- Of a group of parallel connections, ones with small
outstanding windows could experience a larger number of
losses than their share of the total outstanding window
would warrant. This means that it may be harder to initiate
a new connection than to keep an existing connection
going."
Delays caused by congestive packet losses could be as long or longer
as the delays causes by HOL blocking at the origin server, and so the
increased risk of congestion from parallel connections might not
always be worth the reduction in HOL blocking.
While some older clients allowed the user to specify the maximum
number of parallel connections, modern browsers set a fixed upper
limit of approximately four connections, apparently to avoid
congestion effects. Allman [2] reports that "nearly all connections"
observed in a recent trace used "4 or fewer TCP connections" (some
Web crawlers apparently use a much higher degree of parallelism). As
a result of this connection limit, even browsers using parallel TCP
connections are prone to HOL blocking, although the probability of
blocking is reduced.
Several proposals have been offered for adding a multiplexing layer
under HTTP:
- The Session Control Protocol (SCP) [12] offered a simple
mechanism for creating multiple lightweight connections
over a single TCP connection. Several such lightweight
connections could be active simultaneously. These
lightweight connections, or "sessions," were given session
IDs and could be fragmented into units smaller than an
entire HTTP message, so two or more responses could be sent
in an arbitrary order. SCP offered a few other features
(including header compression).
- WebMUX [6] was a session management protocol separating the
underlying transport from the upper level application
Mogul [Page 5]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
protocols. It provided a lightweight communication channel
to the application layer by multiplexing data streams on
top of a reliable stream oriented transport. WebMUX had
many goals, but apparently one feature was the ability to
create independent sessions over a single transport
connection, which would allow the responses for two or more
sessions to be sent in arbitrary order. The WebMUX
protocol appears to have been intended for use with the
HTTP-ng "binary wire protocol" [7], which added support for
request-specific serial numbers. The HTTP-ng proposals
were much more complex than the SCP proposal. Both of
these Internet-Drafts have long since expired, and the
HTTP-ng effort has not made any progress.
The Blocks Extensible Exchange Protocol (BEEP or sometimes BXXP) [11]
is a new protocol for support of new Internet applications. The core
of BEEP is a framing mechanism permitting "simultaneous and
independent exchanges of mechanisms between peers." BEEP, as a
foundation for new protocols, is apparently not intended to fit under
HTTP.
2 Overview
In the existing HTTP specification, the server must return responses
on a given transport connection in exactly the same order as it
receives them. This allows the client to match responses to
requests.
In order to support out-of-order responses, the HTTP protocol must be
extended with mechanism for identifying requests and their
corresponding responses. A request ID may be supplied by the client,
in a new header field. The server, if it reorders responses, returns
this same header field with the corresponding response. Thus, the
client is able to match reordered responses to requests.
Request IDs are generated by the client, and are opaque to the
server. That is, the server cannot perform any operation on a
request ID (such as a "greater than" comparison), except to echo it
back to the client. The request ID name space is local to a given
transport connection, so that a client with multiple connections
could use the same ID simultaneously on two different connections. A
client may reuse a request ID, but only if there is no pending
response on the given connection for that request ID. The intention
is that the request IDs can be expressed in a minimal number of
bytes, thus avoiding unnecessary overhead.
The client may wish to prevent certain responses from being
reordered. To support this, this extension introduces the notion of
a "barrier," which is a request whose response must be ordered with
respect to all previous and subsequent requests on the given
Mogul [Page 6]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
connection. That is, when the server receives a "barrier" request,
it must first respond to all previous requests before responding to
the barrier request, and must not respond to any subsequent requests
before responding to the barrier request. Barrier requests are
somewhat analogous to "memory barrier" or "memory fence" instructions
used in multiprocessor memory systems [1], or "sequence points" in
the C programming language.
A barrier request is simply an HTTP request that carries no request
ID header field. This definition means that all existing HTTP
clients appear to be treating every request as barriers, and hence
their requests will never be reordered. Therefore, this extension
requires no negotiation mechanism to allow interoperation with any
kind of client.
A server that does not wish to reorder a response need not return the
corresponding request ID. That is, it may treat the request as a
barrier request. The behavior of a server that does not implement
this extension is thus indistinguishable from one that simply chooses
not to reorder any responses. Therefore, this requires no
negotiation mechanism to allow interoperation with any kind of
server.
Because the request ID is unique only with respect to a particular
transport connection, it is a "hop-by-hop" mechanism, not an
"end-to-end" mechanism. The request ID header field must be listed
in a Connection header field, as defined by HTTP/1.1. While this
means that the mechanism cannot be used on hops that include proxies
that do not comply with this specification, the use of a hop-by-hop
approach significantly simplies the extension:
- The request ID name space is local to a given client; there
is no need to make IDs unique across all clients (or all
clients of a given proxy).
- A proxy that does not understand response reordering is at
no risk of accidentally mismatching a set of requests and
responses, which would be fatal for correct cache behavior.
- A proxy that does understand response reordering may use
the mechanism to avoid HOL blocking on its inbound
connections. That is, in some cases it might be useful to
exploit the mechanism hop-by-hop even if it cannot be used
end-to-end.
Even though this mechanism does not allow end-to-end reordering on a
path with non-complying proxies, it may still allow reordering on
portions of such a path. If the two endpoints of any given hop on
that path do comply, then they are free to reorder responses on that
hop, which may serve to hide some or all of the HOL blocking
experienced by a series of responses.
Mogul [Page 7]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
---------
Do we need to provide the client the option to send an
end-to-end barrier (as well as a hop-by-hop barrier), so that
no proxy along the path will attach a request ID to a request
that should not be reordered?
---------
2.1 Performance considerations
This protocol extension leaves a lot of freedom to servers and
proxies to decide whether or not to reorder a particular sequence of
requests. Such scheduling and resource-allocation decisions are
likely to be the topic of additional research and/or proprietary
innovation.
3 Specification
In this specification, the The key words "MUST", "MUST NOT",
"SHOULD", "SHOULD NOT", and "MAY" document are to be interpreted as
described in RFC2119 [4].
3.1 RID
The RID header general-header field is used by either a client or a
server (including a proxy acting in either of these roles) to
transmit a request ID.
request-id = token
RID = "RID" ":" request-id
The RID header field, if used in a message, MUST be listed in a
Connection header field in that message. (If the RID header field
appears in a message but is not listed in a Connection header field
of that message, the recipient MUST ignore the RID header field.)
A client MAY send at most one RID header field with a request-id
value of its chosing. (If more than one RID header field is present
in a request, the server MUST ignore all of the RID header fields.)
A server MAY reorder response messages among any contiguous set of
request messages, on a given transport connection, that all include
RID header fields. If the server reorders a response message, that
message MUST include the exact RID header field (ignoring LWS) as was
present in the corresponding request. If a request message does not
include an RID header field, the server MUST NOT reorder the response
with respect to any prior or subsequent requests on the same
transport connection.
A client MUST NOT reuse a request-id value on a given transport
connection until it has fully received the response message
corresponding to a previous request using the same request-id.
Mogul [Page 8]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
A client SHOULD NOT send an RID header field with a request if the
semantics of the operation might not permit reordering. A server
SHOULD NOT reorder a response if the semantics of the operation might
not permit reordering. For example, a DELETE request probably ought
not to be reordered with other requests.
3.2 Examples
If the client issues the following sequence of pipelined requests
over a persistent connection:
HEAD /1.gif HTTP/1.1
Host: example.com
Connection: RID
RID: 1
HEAD /2.gif HTTP/1.1
Host: example.com
Connection: RID
RID: II
HEAD /3.gif HTTP/1.1
Host: example.com
HEAD /4.gif HTTP/1.1
Host: example.com
Connection: RID
RID: four
HEAD /5.gif HTTP/1.1
Host: example.com
Connection: RID
RID: E
then one legal sequence of responses would be:
Mogul [Page 9]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:04 GMT
Etag: "a79d-338-33b7d40b"
Content-type: image/gif
Connection: RID
RID: II
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:05 GMT
Etag: "a79d-338-33b7d40c"
Content-type: image/gif
Connection: RID
RID: 1
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:06 GMT
Etag: "a79d-338-33b7d40d"
Content-type: image/gif
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:07 GMT
Etag: "a79d-338-33b7d40e"
Content-type: image/gif
Connection: RID
RID: E
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:08 GMT
Etag: "a79d-338-33b7d40f"
Content-type: image/gif
Connection: RID
RID: four
However, the following sequence of responses would NOT be legal,
because it reorders the response to the third request (for
"http://example.com/3.gif"):
Mogul [Page 10]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:04 GMT
Etag: "a79d-338-33b7d40b"
Content-type: image/gif
RID: II
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:05 GMT
Etag: "a79d-338-33b7d40c"
Content-type: image/gif
RID: 1
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:06 GMT
Etag: "a79d-338-33b7d40e"
Content-type: image/gif
RID: E
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:07 GMT
Etag: "a79d-338-33b7d40d"
Content-type: image/gif
HTTP/1.1 200 OK
Date: Mon Apr 2 15:21:08 GMT
Etag: "a79d-338-33b7d40f"
Content-type: image/gif
RID: four
3.3 RID-Barrier
---------
This might be needed for completeness! We will need to analyze
the protocol extension more carefully before deciding.
---------
The RID-Barrier request-header field prevents a proxy server from
adding a RID header field to a request message:
RID-Barrier = "RID-Barrier"
The RID-Barrier header field is an end-to-end field and MUST NOT be
listed in a Connection header field.
A proxy forwarding a request message containing a RID-Barrier header
field MUST NOT add a RID header field to that message.
A server receiving a message with both a RID header field and a
RID-Barrier header field MUST ignore the RID header field.
Mogul [Page 11]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
A proxy might need to establish a new inbound transport connection in
order to allow continued reordering of unrelated responses while
preserving the ordering constraints implied by the RID-Barrier header
(relative to a previous request that it has forwarded without yet
receiving a response).
4 Interoperability Considerations
There is some evidence that certain proxy or other intermediary
systems fail to comply with some of the mandatory requirements of the
HTTP/1.1 specification. This could create interoperability problems
when the RID header field is used.
For example, if an HTTP/1.0 proxy that fails to correctly identify
its own implementation version receives an HTTP/1.1 request message
with a RID header field, it might forward both the RID header field
and the Connection header field to the inbound server. This server
would not realize that the RID header field was incorrectly
forwarded. (While RFC2145 [9] requires a proxy to generate messages
with its own implementation's version number, some existing proxies
might incorrectly forward the version number of the request.)
If that proxy is caching responses, it would probably associate
reordered responses with the wrong requests, and hence subsequent
cache hits would yield wrong answers.
It might also be possible for a layer-7 switch, acting as a
transparent or interception proxy, to create confusion, if the device
does not obey the Connection header.
It is therefore possible that some interoperability problems will be
discovered during operational testing of this protocol extension. If
such problems are found, implementations that normally support the
RID header field (both clients and servers, including proxies in
either role) SHOULD provide a means to disable the use of reordering.
Such a means could either apply to all messages, or perhaps just to
those messages sent to a particular set of network addresses or DNS
names.
Unfortunately, it is in the nature of "transparent" proxies to be
undetectable, and if a proxy is simultaneously undetectable and
non-compliant, little can be done to work around the problem. Users
may want to complain to switch vendors and network operators
responsible for non-compliant transparent proxies, and protocol
compliance and performance-testing tools should give failing grades
to such systems.
Mogul [Page 12]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
5 Security Considerations
There do not appear to be any security considerations beyond those
associated with HTTP/1.1 in general.
6 Acknowledgements
Terence Kelly provided helpful review comments on this document.
7 References
1. Sarita V. Adve and Kourosh Gharachorloo. "Shared Memory
Consistency Models: A Tutorial". IEEE Computer 29, 12 (December
1996), 66-76.
http://research.compaq.com/wrl/techreports/abstracts/95.7.html.
2. Marc Allman. "A Web Server's View of the Transport Layer".
Computer Communication Review 30, 5 (October 2000), ???-???.
http://www.acm.org/sigcomm/ccr/archive/2000/oct00/
ccr_200010-allman.html.
3. Hari Balakrishnan, Venkata N. Padmanabhan, Srinivasan Seshan,
Mark Stemm, and Randy H. Katz . TCP Behavior of a Busy Internet
Server: Analysis and Improvements. Proc. IEEE Infocom, San
Francisco, CA, March, 1998, pp. ???-???.
http://www.cs.berkeley.edu/~ss/papers/infocom98/html/infocom98.html.
4. S. Bradner. Key words for use in RFCs to Indicate Requirement
Levels. RFC 2119, Harvard University, March, 1997.
5. Roy T. Fielding, Jim Gettys, Jeffrey C. Mogul, Henrik Frystyk
Nielsen, Larry Masinter, Paul Leach, and Tim Berners-Lee. Hypertext
Transfer Protocol -- HTTP/1.1. RFC 2616, HTTP Working Group, June,
1999.
6. Jim Gettys and Henrik Frystyk Nielsen. The WebMUX Protocol.
Internet Draft draft-gettys-webmux-00.txt, W3C, August, 1998.
http://www.w3.org/Protocols/MUX/WD-mux-980722.html.
7. Bill Janssen. w3ng: Binary Wire Protocol for HTTP-ng.
Internet-Draft draft-janssen-httpng-wire-00.txt, W3C, August, 1998.
http://www.w3.org/Protocols/HTTP-NG/1998/08/
draft-janssen-httpng-wire-00.txt.
8. Jeffrey C. Mogul. The Case for Persistent-Connection HTTP.
Proc. SIGCOMM '95 Symposium on Communications Architectures and
Protocols, Cambridge, MA, August, 1995, pp. 299-313.
http://www.research.compaq.com/wrl/techreports/abstracts/95.4.html.
Mogul [Page 13]
Internet-Draft HTTP out-of-order responses 6 April 2001 15:39
9. Jeffrey C. Mogul, Roy T. Fielding, Jim Gettys, and Henrik Frystyk
Nielsen. Use and Interpretation of HTTP Version Numbers. RFC 2145,
HTTP Working Group, May, 1997.
10. Henrik Frystyk Nielsen, James Gettys, Anselm Baird-Smith, Eric
Prud'hommeaux, Hakon Wium Lie, and Chris Lilley. Network Performance
Effects of HTTP/1.1, CSS1, and PNG. Proc. SIGCOMM '97, Cannes,
France, September, 1997.
11. Marshall T. Rose. The Blocks Extensible Exchange Protocol Core.
RFC 3080, Network Working Group, March, 2001.
http://www.ietf.org/rfc/rfc3080.txt.
12. Simon E. Spero. SCP - Session Control Protocol V 1.1.
http://www.ibiblio.org/ses/scp.html.
8 Author's address
Jeffrey C. Mogul
Western Research Laboratory
Compaq Computer Corporation
250 University Avenue
Palo Alto, California, 94305, U.S.A.
Email: Jeffrey.Mogul@Compaq.com
Phone: 1 650 617 3304 (email preferred)
Mogul [Page 14]