[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

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]


Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/