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]