Internet Draft


Network Working Group                         Jeffrey Mogul, Compaq WRL,
Internet-Draft                          Balachander Krishnamurthy, AT&T,
Expires: 1 October 1999                              Fred Douglis, AT&T,
                                                    Anja Feldmann, AT&T,
                                                Yaron Goland, Microsoft,
                                                Arthur van Hoff, Marimba
                                                        19 February 1999
                         Delta encoding in HTTP

                     draft-mogul-http-delta-01.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

        Many HTTP requests cause the retrieval of slightly modified
        instances of resources for which the client already has a
        cache entry.  Research has shown that such modifying
        updates are frequent, and that the modifications are
        typically much smaller than the actual entity.  In such
        cases, HTTP would make more efficient use of network
        bandwidth if it could transfer a minimal description of the
        changes, rather than the entire new instance of the
        resource.  This is called ``delta encoding.''  This
        document describes how delta encoding can be supported as a
        compatible extension to HTTP/1.1.




Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff       [Page 1]

Internet-Draft               Delta encoding       19 February 1999 15:55


                           TABLE OF CONTENTS

1 Introduction                                                         3
     1.1 Related research and proposals                                4
2 Goals                                                                5
3 Terminology                                                          6
4 Relationship between content-coding, transfer-coding, and ranges     7
     4.1 Ordering of transformations in the same phase                10
5 Basic mechanisms                                                    10
     5.1 Background: an overview of HTTP cache validation             10
     5.2 Requesting the transmission of deltas                        12
     5.3 Content-coding or Transfer-coding?                           13
     5.4 Choice of delta algorithm and format                         14
     5.5 Identification of delta-encoded responses                    15
     5.6 Transmission of delta-encoded responses                      16
     5.7 Examples of requests combing Range and delta encoding        17
6 Encoding algorithms and formats                                     19
     6.1 IANA Considerations                                          20
7 Management of base instances                                        20
     7.1 Multiple entity tags in the If-None-Match header             21
     7.2 Hints for managing the client cache                          22
8 Delta-encoding and clustering                                       24
9 Use of templates                                                    26
10 Deltas and intermediate caches                                     28
11 Digests for data integrity                                         29
12 Specification                                                      30
     12.1 Protocol parameter specifications                           30
     12.2 Status code specifications                                  31
          12.2.1 226 Delta                                            31
          12.2.2 227 Range of Delta                                   31
     12.3 Header specifications                                       32
          12.3.1 Delta-Base                                           32
          12.3.2 DCluster                                             32
          12.3.3 DTemplate                                            33
13 New requirements for existing headers                              34
     13.1 Accept-Encoding                                             34
     13.2 TE                                                          34
     13.3 Use of compression with delta encoding                      34
     13.4 Delta encoding and multipart/byteranges                     35
14 New Cache-control directives                                       36
15 Quantifying the protocol overhead                                  36
16 Security Considerations                                            38
     16.1 Spoofing attacks using the DCluster header                  38
17 History                                                            39
     17.1 draft-mogul-http-delta-01.txt                               39
18 Acknowledgements                                                   39
19 References                                                         39
20 Authors' addresses                                                 42

Index                                                                 43


Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff       [Page 2]

Internet-Draft               Delta encoding       19 February 1999 15:55


1 Introduction

   The World Wide Web is a distributed system, and so often benefits
   from caching to reduce retrieval delays.  Retrieval of a Web resource
   (such as document, image, icon, or applet) over the Internet or other
   wide-area network usually takes enough time that the delay is over
   the human threshold of perception.  Often, that delay is measured in
   seconds.  Caching can often eliminate or significantly reduce
   retrieval delays.

   Many Web resources change over time, so a practical caching approach
   must include a coherency mechanism, to avoid presenting stale
   information to the user.  Originally, the Hypertext Transfer Protocol
   (HTTP) provided little support for caching, but under operational
   pressures, it quickly evolved to support a simple mechanism for
   maintaining cache coherency.

   In HTTP/1.0 [2], the server may supply a ``last-modified'' timestamp
   with a response.  If a client stores this response in a cache entry,
   and then later wishes to re-use the response, it may transmit a
   request message with an ``If-modified-since'' field containing that
   timestamp; this is known as a conditional retrieval.  Upon receiving
   a conditional request, the server may either reply with a full
   response, or, if the resource has not changed, it may send an
   abbreviated reply, indicating that the client's cache entry is still
   valid.  HTTP/1.0 also includes a means for the server to indicate,
   via an ``Expires'' timestamp, that a response will be valid until
   that time; if so, a client may use a cached copy of the response
   until that time, without first validating it using a conditional
   retrieval.

   HTTP/1.1 [10] adds many new features to improve cache coherency and
   performance.  However, it preserves the all-or-none model for
   responses to conditional retrievals: either the server indicates that
   the resource value has not changed at all, or it must transmit the
   entire current value.

   Common sense suggests (and traces confirm), however, that even when a
   Web resource does change, the new instance is often substantially
   similar to the old one.  If the difference, or ``delta'', between the
   two instances could be sent to the client instead of the entire new
   instance, a client holding a cached copy of the old instance could
   apply the delta to construct the new version.  In a world of finite
   bandwidth, the reduction in response size and delay could be
   significant.

   One can think of deltas as a way to squeeze as much benefit as
   possible from client and proxy caches.  Rather than treating an
   entire response as the ``cache line,'' with deltas we can treat
   arbitrary pieces of a cached response as the replaceable unit, and
   avoid transferring pieces that have not changed.

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff       [Page 3]

Internet-Draft               Delta encoding       19 February 1999 15:55


   This document proposes a set of compatible extensions to HTTP/1.1
   that allow clients and servers to use delta encoding with minimal
   overhead.

   We assume that the reader is familiar with the HTTP/1.1
   specification.

1.1 Related research and proposals
   The idea of delta-encoding to reduce communication or storage costs
   is not new.  For example, the MPEG-1 video compression standard
   transmits occasional still-image frames, but most of the frames sent
   are encoded (to oversimplify) as changes from an adjacent frame.  The
   SCCS and RCS [27] systems for software version control represent
   intermediate versions as deltas; SCCS starts with an original version
   and encodes subsequent ones with forward deltas, whereas RCS encodes
   previous versions as reverse deltas from their successors.
   Jacobson's technique for compressing IP and TCP headers over slow
   links [18] uses a clever, highly specialized form of delta encoding.

   In spite of this history, it appears to have taken several years
   before anyone thought of applying delta encoding to HTTP, perhaps
   because the development of HTTP caching has been somewhat haphazard.
   The first published suggestion for delta encoding appears to have
   been by Williams et al. in a paper about HTTP cache removal
   policies [29], but these authors did not elaborate on their design
   until later [28].

   The WebExpress project [16] appears to be the first published
   description of an implementation of delta encoding for HTTP (which
   they call ``differencing'').  WebExpress is aimed specifically at
   wireless environments, and includes a number of orthogonal
   optimizations.  Also, the WebExpress design does not propose changing
   the HTTP protocol itself, but rather uses a pair of interposed
   proxies to convert the HTTP message stream into an optimized form.
   The results reported for WebExpress differencing are impressive, but
   are limited to a few selected benchmarks.

   Banga et al. [1] describe the use of optimistic deltas, in which a
   layer of interposed proxies on either end of a slow link collaborate
   to reduce latency.  If the client-side proxy has a cached copy of a
   resource, the server-side proxy can simply send a delta (or a 304
   [Not Modified] response).  If only the server-side proxy has a cached
   copy, it may optimistically send its (possibly stale) copy to the
   client-side proxy, followed (if necessary) by a delta once the
   server-side proxy has validated its own cache entry with the origin
   server.  The use of optimistic deltas, unlike delta encoding,
   actually increases the number of bytes sent over the network, in an
   attempt to improve latency by anticipating a ``Not Modified''
   response from the origin server.  The optimistic delta paper, like
   the WebExpress paper, did not propose a change to the HTTP protocol
   itself, and reported results only for a small set of selected URLs.

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff       [Page 4]

Internet-Draft               Delta encoding       19 February 1999 15:55


   Mogul et al. [23] collected lengthy traces, at two different sites,
   of the full contents of HTTP messages, to quantify the potential
   benefits of delta-encoded responses.  They showed that delta encoding
   can provide remarkable improvements in response-size and
   response-delay for an important subset of HTTP content types.  They
   proposed a set of HTTP extensions, but without the level of detail
   required for a specification.  Douglis et al. [8] used the same sets
   of full-content traces to quantify the rate at which resources change
   in the Web.

   The HTTP Distribution and Replication Protocol (DRP), proposed to W3C
   by Marimba, Netscape, Sun, Novell, and At Home, aims to provide a
   collection of new features for HTTP, to support ``the efficient
   replication of data over HTTP'' [14].  One aspect of the DRP proposal
   is the use of ``differential downloading,'' which is essentially a
   form of delta encoding.  The original DRP proposal uses a different
   approach than is described here, but a forthcoming revision of DRP
   will be revised to conform to the proposal in this document.


2 Goals

   The goals of this proposal are:

      1. Reduce the mean size of HTTP responses, thereby improving
         latency and network utilization.

      2. Avoid any extra network round trips.

      3. Minimize the amount of per-request and per-response
         overheads.

      4. Support a variety of encoding algorithms and formats.

      5. Interoperate with HTTP/1.0 and HTTP/1.1.

      6. Be fully optional for clients, proxies, and servers.

      7. Allow moderately simple implementations.

   The goals do not include:

      - Reducing the number of HTTP requests sent to an origin
        server.

      - Reducing the size of every HTTP message.

      - Increasing the cache-hit ratio of HTTP caches.

      - Allowing excessively simplistic implementations of delta
        encoding.

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff       [Page 5]

Internet-Draft               Delta encoding       19 February 1999 15:55


      - Delta encoding of request messages, or of responses to
        methods other than GET.

      Nothing in this specification specifically precludes the use of
      a delta encoding for the body of a PUT request.  However, no
      mechanism currently exists for the client to discover if the
      server can interpret such messages, and so we do not attempt to
      specify how they might be used.


3 Terminology

   HTTP/1.1 [10] defines the following terms:

   resource         A network data object or service that can be
                   identified by a URI, as defined in section 3.2.
                   Resources may be available in multiple
                   representations (e.g. multiple languages, data
                   formats, size, resolutions) or vary in other ways.

   entity           The information transferred as the payload of a
                   request or response.  An entity consists of
                   metainformation in the form of entity-header fields
                   and content in the form of an entity-body, as
                   described in section 7.

   variant          A resource may have one, or more than one,
                   representation(s) associated with it at any given
                   instant. Each of these representations is termed a
                   `variant.' Use of the term `variant' does not
                   necessarily imply that the resource is subject to
                   content negotiation.

   The dictionary definition for ``entity'' is ``something that has
   separate and distinct existence and objective or conceptual
   reality'' [21].  Unfortunately, the definition for ``entity'' in
   HTTP/1.1 is similar to that used in MIME [13], based on an entirely
   false analogy between MIME and HTTP.

   In MIME, electronic mail messages do have distinct and separate
   existences, so the MIME definition of ``entity'' as something that
   ``refers specifically to the MIME-defined header fields and contents
   of either a message or one of the parts in the body of a multipart
   entity'' makes sense.

   In HTTP, however, a response message to a GET does not have a
   distinct and separate existence.  Rather, it is describing the
   current state of a resource (or a variant, subject to a set of
   constraints).  The HTTP/1.1 specification provides no term to
   describe ``the value that would be returned in response to a GET
   request at the current time for the selected variant of the specified

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff       [Page 6]

Internet-Draft               Delta encoding       19 February 1999 15:55


   resource.''  This leads to awkward wordings in the HTTP/1.1
   specification in places where this concept is necessary.

   It is too late to fix the terminological failure in the HTTP/1.1
   specification, so we instead define a new term, for use in this
   document:

   instance         The entity that would be returned in a status-200
                   response to a GET request, at the current time, for
                   the selected variant of the specified resource, but
                   without the application of any content-coding or
                   transfer-coding.

   One can think of an instance as a snapshot in the life of a resource.

   It is convenient to think of an entity tag, in HTTP/1.1, as being
   associated with an instance, rather than an entity.  That is, for a
   given resource, two different response messages might include the
   same entity tag, but two different instances of the resource should
   never be associated with the same (strong) entity tag.

   We will informally use the term ``delta,'' in this document, to mean
   an HTTP response encoded as the difference between two instances.

   We define one more term, whose implications will be discussed in
   section 8:

   uniqueness scope
                   The uniqueness scope of an entity tag is the set of
                   resources across which this entity tag is unique for
                   all time.  That is, within this set of resources, if
                   two instances share an entity tag, then the values of
                   these instances (including their instance bodies and
                   their instance headers) are equal.

   In unmodified HTTP/1.1, the uniqueness scope of an entity tag is
   always a single resource.  In this proposal, we provide a means to
   extend the uniqueness scope to include multiple resources.


4 Relationship between content-coding, transfer-coding, and ranges

   HTTP/1.1 supports a number of different transformations on the body
   of a value:

   Content-coding   According to the specification, ``Content coding
                   values indicate an encoding transformation that has
                   been or can be applied to an entity. Content codings
                   are primarily used to allow a document to be
                   compressed or otherwise usefully transformed without
                   losing the identity of its underlying media type and

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff       [Page 7]

Internet-Draft               Delta encoding       19 February 1999 15:55


                   without loss of information. Frequently, the entity
                   is stored in coded form, transmitted directly, and
                   only decoded by the recipient.''  Content-codings are
                   normally end-to-end transformations; i.e., once
                   applied at the sender, they are not removed except at
                   the ultimate recipient.  An intermediate server may
                   apply a content-coding, in appropriate circumstances.

   Transfer-coding  According to the specification, ``Transfer coding
                   values are used to indicate an encoding
                   transformation that has been, can be, or may need to
                   be applied to an entity-body in order to ensure "safe
                   transport" through the network.  This differs from a
                   content coding in that the transfer coding is a
                   property of the message, not of the original
                   entity.''  Transfer-codings are explicitly hop-by-hop
                   transformations (although, as an optimization, an
                   intermediate proxy may store the transfer-coded
                   version of a message if this behavior is not
                   inconsistent with its externally visible function.)

   Ranges           An HTTP client, using the Range header, may request
                   that the server return one or more subranges of the
                   instance, rather than the entire instance value.
                   HTTP/1.1 only supports byte-ranges, although there is
                   some possibility that future extensions will allow
                   for other kinds of range-specifiers (such as chapters
                   of a document).

   A client signals its willingness to receive a content-coding by
   sending an ``Accept-Encoding'' header, listing the set of
   content-codings that it understands.  It may optionally include
   information about which content-codings it prefers.  If a server uses
   any non-identity content-coding(s), it includes a
   ``Content-Encoding'' header field in the response, listing these
   content-codings in their order of application.

   RFC2068 [10] did not include an analogous mechanism for negotiating
   the use of transfer-codings, although it does include an analogous
   ``Transfer-Encoding'' header for marking the response.  A new ``TE''
   header has since been added to HTTP/1.1 [11], analogous to the
   ``Accept-Encoding'' header.

   One must understand the relationship between these transformations in
   order to see how delta encoding applies to HTTP responses.

   Conceptually, the various transformations are related as follows:

      1. Upon receiving a GET request, the server uses the URI in
         the request to identify the requested resource.


Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff       [Page 8]

Internet-Draft               Delta encoding       19 February 1999 15:55


      2. Optionally, it uses information from the request (and
         perhaps additional information) to select a variant of
         that resource.

      3. The result of the first two steps, at the time when the
         request is processed, is an instance.  The instance
         includes a body (possibly empty) and possibly some
         instance headers.

      4. At this point, the server may apply a non-identity
         content-coding to the instance, or one might have been
         inherent in its generation.  This also results in a
         Content-Encoding header.

      5. If the request included a Range header, the server may
         optionally produce a range response, consisting of the
         original set of headers, a Content-Range header, and an
         appropriately encoded body.

      6. The result of the fifth step becomes the entity,
         consisting of entity headers and an entity body.

      7. The server may then apply a non-identity transfer-coding;
         on-the-fly compression would be done in this step.  If so,
         a Transfer-Encoding header is added to the message.

      8. The results of the seventh step is the message, consisting
         of a message body (the transfer-encoded version of the
         entity body), the entity headers, and additional response
         and general headers.

   The distinction between transfer-coding and content-coding is most
   visible when a Range is also involved, because Range selections are
   applied after content-codings and before transfer-codings.  Ranges
   are used for two main purposes:

      1. to complete a partial response after a premature
         termination of a message

      2. to obtain just selected sections of an instance.

   The former use of Range is consistent with the use of delta encoding
   as a content-coding; the latter requires the use of delta encoding as
   a transfer-coding.  (This proposal supports the use of delta encoding
   as either a content-coding or a transfer-coding.)

   Although it is possible to use delta encoding as a transfer-coding,
   it is more likely to be useful as a content-coding.  Since
   transfer-coding is done hop-by-hop, using a delta encoding is only
   feasible if each caching proxy along the path has a cache entry for
   both instances involved.  Otherwise, a caching proxy could not meet

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff       [Page 9]

Internet-Draft               Delta encoding       19 February 1999 15:55


   the formal requirement that a transfer-coding is removed on each hop.
   However, a proxy can always act as a ``tunnel'' when forwarding a
   request which might elicit a response transfer-encoded with a delta
   encoding; this removes the requirement that the proxy delete
   transfer-codings.

   It does not seem to make sense to apply delta encodings as both a
   content-coding and transfer-coding for the same message.

4.1 Ordering of transformations in the same phase
   Another apparent ambiguity is whether, if both are applied as
   content-codings (or both are applied as transfer-codings), should a
   delta encoding be applied before or after compression?  Some
   experience suggests that computing the delta between two different
   compressed files can yield a relatively small result, if the files
   are large and the differences are either very small, or near the end
   of the files.  Similarly, some simple differencing algorithms (such
   as the UNIX ``diff'' command) require post-compression of their
   output to yield the best results.

   However, HTTP's mechanism for negotiating the use of content-codings
   (and the proposed mechanism for negotiating the use of
   transfer-codings) does not specify a means for the client to request
   that the transformations be applied in a specified order.  This is
   not impossible; for example, the specification could be changed to
   require that if multiple transformations are applied, then they are
   applied in the order in which they appear in the ``Accept-Encoding''
   header field (or in the ``TE'' header field).

   A general requirement for preserving coding orderings would not be
   compatible with deployed implementations of HTTP/1.1.  However, by
   making such a requirement apply only when a delta encoding is listed,
   we can avoid incompatibility, because delta encoding is not yet
   deployed.  Therefore, this proposal requires that if any delta
   encoding is used, either as a transfer-coding or as a content-coding,
   then any other codings applied by the server must be applied in the
   same order as they appear in the TE or Accept-Encoding header.  See
   sections 13.1 and 13.2 for a formal specification of this
   requirement.


5 Basic mechanisms

   In this section, we explain the concepts behind delta encoding.  This
   is not meant as a formal specification of the proposed extensions;
   see section 12 for that.

5.1 Background: an overview of HTTP cache validation
   When a client has a response in its cache, and wishes to ensure that
   this cache entry is current, HTTP/1.1 allows the client to do a
   ``conditional GET'', using one of two forms of ``cache validators.''

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 10]

Internet-Draft               Delta encoding       19 February 1999 15:55


   In the traditional form, available in both HTTP/1.0 and in HTTP/1.1,
   the client may use the ``If-Modified-Since'' request-header to
   present to the server the ``Last-Modified'' timestamp (if any) that
   the server provided with the response.  If the server's timestamp for
   the resource has not changed, it may send a response with a status
   code of 304 (Not Modified), which does not transmit the body of the
   resource.  If the timestamp has changed, the server would normally
   send a response with a status code of 200 (OK), which carries a
   complete copy of the resource, and a new Last-Modified timestamp.

   This timestamp-based approach is prone to error because of the lack
   of timestamp resolution: if a resource changes twice during one
   second, the change might not be detectable.  Therefore, HTTP/1.1 also
   allows the server to provide an entity tag with a response.  An
   entity tag is an opaque string, constructed by the server according
   to its own needs; the protocol specification imposes a bare minimum
   of requirements on entity tags.  (In particular, a ``strong'' entity
   tag must change if the value of the resource changes.) In this case,
   the client may validate its cache entry by sending its conditional
   request using the ``If-None-Match'' request-header, presenting the
   entity tag associated with the cached response.  (The protocol
   defines several other ways to transmit entity tags, such as the
   ``If-Range'' header, used for short-circuiting an otherwise necessary
   round trip.) If the presented entity tag matches the server's current
   tag for the resource, the server should send a 304 (Not Modified)
   response.  Otherwise, the server should send a 200 (OK) response,
   along with a complete copy of the resource.

   In the existing HTTP protocol (HTTP/1.0 or HTTP/1.1), a client
   sending a conditional request can expect either of two responses:

      - status = 200 (OK), with a full copy of the resource,
        because the server's copy of the resource is presumably
        different from the client's cached copy.

      - status = 304 (Not Modified), with no body, because the
        server's copy of the resource is presumably the same as the
        client's cached copy.

   Informally, one could think of these as ``deltas'' of 100% and 0% of
   the resource, respectively.  Note that these deltas are relative to a
   specific cached response.  That is, a client cannot request a delta
   without specifying, somehow, which two instances of a resource are
   being differenced.  The ``new'' instance is implicitly the current
   instance that the server would return for an unconditional request,
   and the ``old'' instance is the one that is currently in the client's
   cache.  The cache validator (last-modified time or entity tag) is
   what is used to communicate to the server the identity of the old
   instance.



Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 11]

Internet-Draft               Delta encoding       19 February 1999 15:55


5.2 Requesting the transmission of deltas
   In order to support the transmission of actual deltas, an extension
   to HTTP/1.1 needs to provide these features:

      1. A way to mark a request as conditional.

      2. A way to specify the old instance, to which the delta will
         be applied by the client.

      3. A way to indicate that the client is able to apply one or
         more specific forms of delta encoding.

      4. A way to mark a response as being delta-encoded in a
         particular format.

   The first two features are already provided by HTTP/1.1: the presence
   of a conditional request-header (such as ``If-Modified-Since'' or
   ``If-None-Match'') marks a request as conditional, and the value of
   that header uniquely specifies the old instance (ignoring the problem
   of last-modified timestamp granularity).

   We defer discussion of the fourth feature, until section 5.6.

   The third feature, a way for the client to indicate that it is able
   to apply deltas (aside from the trivial 0% and 100% deltas), can be
   accomplished by transmitting a list of acceptable delta-encoding
   formats in a request-header field.  The presence of this list in a
   conditional request indicates that the client is able to apply
   delta-encoded cache updates.

   A client that wishes to have a delta encoding used as a
   content-coding does so by listing the name of one or more delta
   encoding formats as content-codings in an ``Accept-Encoding'' header
   field.

   Similarly, a client that wishes to have a delta encoding used as a
   transfer-coding does so by listing the name of one or more delta
   encoding formats as content-codings in an ``TE'' header field.

   In other words, we propose extending the the set of content-codings
   and the set of transfer-codings to include a number of standard delta
   encoding formats.

   For example, a client might send this request:

      GET /foo.html HTTP/1.1
      If-None-Match: "123xyz"
      Accept-Encoding: vcdiff, diff-e, gzip

   The meaning of this request is that:


Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 12]

Internet-Draft               Delta encoding       19 February 1999 15:55


      - The client wants to obtain the current value of /foo.html.

      - It already has a cached response for that resource, whose
        entity tag is ``123xyz''.

      - It is willing to accept delta-encoded updates using either
        of two formats, ``diff-e'' (i.e., output from the UNIX
        ``diff -e'' command), and ``vcdiff''.  (Encoding algorithms
        and formats, such as ``vcdiff'', are described in section
        6.)

      - It is willing to accept responses that have been compressed
        using ``gzip,'' whether or not these are delta-encoded.
        (However, based on the new ordering constraint proposed in
        section 4.1, if both delta encoding and compression are
        applied, then this request header specifies that
        compression should be done last.)

   If, in this example, the server's current entity tag for the resource
   is still ``123xyz'', then it should simply return a 304 (Not
   Modified) response, as would a traditional server.

   If the entity tag has changed, presumably but not necessarily because
   of a modification of the resource, the server could instead compute
   the delta between the instance whose entity tag was ``123xyz'' and
   the current instance.

   We defer discussion of what the server needs to store, in order to
   compute deltas, until section 7.

   We note that if a client indicates it is willing to accept deltas,
   but the server does not support this form of content-coding, the
   HTTP/1.1 specification for ``Accept-Encoding'' allows the server to
   simply ignore this.  Such a server acts as if the client had not
   requested a delta-encoded response: it generates a status-200
   response.

5.3 Content-coding or Transfer-coding?
   Since a delta encoding could be either a content-coding or a
   transfer-coding, delta-capable clients have a choice to make when
   constructing a request that might be answered with a delta.  That is,
   should a client use Accept-Encoding or TE to indicate its willingness
   to accept a delta-encoded response?

   Since content-codings, unlike transfer-codings, are end-to-end (that
   is, do not depend on support by intermediate proxies), in simple
   cases, clients should probably request delta-encoded responses using
   Accept-Encoding.  This maximizes the utility of delta encoding at the
   origin server, since any delta-capable proxy along the request chain
   is still free to make any appropriate use of delta-encoded responses
   that it forwards.

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 13]

Internet-Draft               Delta encoding       19 February 1999 15:55


   However, if the origin server does not support delta encoding, but
   the next-hop proxy both supports delta encoding and has the necessary
   instances in its cache, then the client might gain some benefit from
   requesting delta-encoded responses using TE.

   A client wishing to maximize its likelihood of receiving a
   delta-encoded response should send both Accept-Encoding and TE header
   fields listing delta-encoding formats.  This does increase the size
   of the request, so it is not necessarily the optimal approach.

   The situation becomes more complex when the client is requesting a
   Range of the instance.  As discussed in section 4, if the client's
   purpose in requesting a Range is to complete a partial response after
   a premature termination of a message, then it should use
   Accept-Encoding to request a delta-encoded response.  (Presumably,
   the interrupted response used the same delta encoding, if any.)

   However, if the client's purpose in requesting a Range is to obtain
   just a selected portion of the instance, and if it wants the response
   to be delta-encoded against the same portion of another instance, it
   should use TE to request a delta-encoded response.

   A client sending a Range request SHOULD NOT list delta encoding
   formats in both Accept-Encoding and TE request header fields, since
   this amounts to an ambiguous declaration of the client's wishes with
   respect to the Range selection.  If a server receives such an
   ambiguous request, it MAY use either a delta content-coding, or a
   delta transfer-coding; it SHOULD NOT use both.

5.4 Choice of delta algorithm and format
   The server is not required to transmit a delta-encoded response.  For
   example, the result might be larger than the current size of the
   resource.  The server might not be able to compute a delta for this
   type of resource (e.g., a compressed binary format); the server might
   not have sufficient CPU cycles for the delta computation; the server
   might not support any of the delta formats supported by the client;
   or, the network bandwidth might be high enough that the delay
   involved in computing the delta is not worth the delay avoided by
   sending a smaller response.

   However, if the server does want to compute a delta, and the set of
   encodings its supports has more than one encoding in common with the
   set offered by the client, which encoding should it use?  This is
   mostly at the option of the server, although the client can express
   preferences using ``Quality Values'' (or ``qvalues'') in the
   ``Accept-Encoding'' or ``TE'' header.  The HTTP/1.1
   specification [10] describes qvalues in more detail.  (Clients may
   prefer one delta encoding format over another that generates a
   smaller encoding, if the decoding costs for the first format are
   lower and the client is resource-constrained.)


Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 14]

Internet-Draft               Delta encoding       19 February 1999 15:55


   Server implementations have a number of possible approaches.  For
   example, if CPU cycles are plentiful and network bandwidth is scarce,
   the server might compute each of the possible encodings and then send
   the smallest result.  Or the server might use heuristics to choose an
   encoding format, based on things such as the content-type of the
   resource, the current size of the resource, and the expected amount
   of change between instances of the resource.

   Note that it might pay to cache the deltas internally to the server,
   if a resource is typically requested by several different
   delta-capable clients between modifications.  In this case, the cost
   of computing a delta may be amortized over many responses, and so the
   server might use a more expensive computation.

5.5 Identification of delta-encoded responses
   A response using delta encoding as either a content-coding or a
   transfer-coding must be identified as such.  This is done using the
   ``Content-Encoding'' or ``Transfer-Encoding'' headers defined in
   HTTP/1.1.

   However, a simplistic application of this approach would cause
   serious problems if a content-coded delta response flows through an
   intermediate (proxy) cache that is not cognizant of the delta
   mechanism.  Because the Internet is full of HTTP/1.0 caches, which
   might never be entirely replaced, and because the HTTP specifications
   insist that message recipients ignore any header field that they do
   not understand, a non-delta-capable proxy cache that receives a
   delta-encoded response might store that response, and might later
   return it to a non-delta-capable client that has made a request for
   the same resource.  This naive client would believe that it has
   received a valid copy of the entire resource, with predictably
   unpleasant results.

   This problem does not apply to responses using delta encoding only as
   a transfer-coding, since ``Transfer-Encoding'' is a hop-by-hop header
   field.

   To solve this problem, we propose that delta-encoded responses be
   identified as such using a new HTTP status code.  For specificity in
   the discussion that follows, we will use the (currently unassigned)
   code of 226, with a reason phrase of ``Delta''.  There is some
   precedent for this approach:  the HTTP/1.1 specification introduces
   the 206 (Partial Content) status code, for the transmission of
   sub-ranges of a resource.  Existing proxies apparently forward
   responses with unknown status codes, and do not attempt to cache
   them.

   An alternative to using a new status code would be to use the
   ``Expires'' header to prevent HTTP/1.0 caches from storing the
   response, then use ``Cache-control: max-age'' (defined in HTTP/1.1)
   to allow more modern caches to store delta-encoded responses.  This

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 15]

Internet-Draft               Delta encoding       19 February 1999 15:55


   adds many bytes to the response headers, and so would reduce the
   effectiveness of delta encoding.  It is also not entirely clear that
   this approach suppresses all caching by all HTTP/1.0 proxies.  Most
   importantly, it would not prevent incorrect caching by HTTP/1.1
   shared caches that do not understand delta-encoded responses; this
   implies that such responses would also have to be protected using the
   Vary header.  E.g.:

              HTTP/1.1 200 OK
              Expires: Tue, 01 Jan 1970 00:00:01 GMT
              Date: Wed, 24 Dec 1997 14:00:00 GMT
              Cache-control: max-age=3600
              Content-Encoding: vcdiff
              Vary: Accept-Encoding, If-None-Match

   Unfortunately, unless we were to also specify a complex new set of
   rules for the interpretation of the Vary header, this would
   significantly reduce the ability of a proxy cache that does
   understand delta-encoding to optimize the responses it sends to
   delta-capable clients.

   Additionally, when a response both uses a delta encoding as a
   content-coding, and carries a Range of an entity, one cannot simply
   use a status code of 206 (Partial Content), because there are
   HTTP/1.1 proxy caches that understand Ranges but not deltas.  One
   could perhaps use 226 (Delta) and expect that all delta-capable
   proxies also understand Content-Range; i.e., such a proxy would
   realize from the presence of the Content-Range header that a partial
   content is involved.  However, because it might make proxy
   implementation simpler, we also introduce an additional status code
   (provisionally, 227) with a reason phrase of ``Range of Delta''.

      We were reluctant to define additional status codes as part of
      the support for delta encoding.  However, we see no other way
      to remain compatible with the present design of HTTP status
      codes, and the deployed base of HTTP/1.1 cache implementations.

5.6 Transmission of delta-encoded responses
   A delta-encoded response differs from a standard response in three
   ways:

      1. It carries a status code of 226 (Delta), or 227 (Range of
         Delta), if the delta encoding is a content-coding.

      2. It carries a ``Content-encoding'' header field, or a
         ``Transfer-encoding'' header field, indicating which delta
         encoding is used in this response.

      3. Its message-body is a delta-encoding of the current
         instance, rather than a full copy of the instance.


Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 16]

Internet-Draft               Delta encoding       19 February 1999 15:55


   For example, a response to the request given in section 5.2 might
   look like:

      HTTP/1.1 226 Delta
      ETag: "489uhw"
      Content-Encoding: vcdiff
      Date: Tue, 25 Nov 1997 18:30:05 GMT

      ...

   (We do not show the actual contents of the response body, since this
   is a binary format.)

5.7 Examples of requests combing Range and delta encoding
   We used this example in section 5.2: the client sends:

      GET /foo.html HTTP/1.1
      If-None-Match: "123xyz"
      Accept-Encoding: vcdiff, diff-e, gzip

   and the server either responds with a 304 (Not Modified) response, or
   with the appropriate delta encoding.

   Here are a few more examples, to clarify how the client request
   should be interpreted.

   If the client sends

      GET /foo.html HTTP/1.1
      If-None-Match: "123xyz"
      Accept-Encoding: vcdiff, diff-e, gzip
      Range: 0-99

   then the meaning is the same as in the example above, except that
   after the delta encoding (and compression, if any) is created, the
   server then returns only the first 100 bytes of the output of the
   delta encoding.  (If it is shorter than 100 bytes, the entire delta
   encoding is returned.)

   The interaction between the If-Range mechanism and delta encoding is
   somewhat complex.  (If-Range means, informally, ``if the entity is
   unchanged, send me the part(s) that I am missing; otherwise, send me
   the entire new entity.'')  Here is an example that should clarify the
   use of this combination.

   Suppose that the client wants to have the complete current instance
   of http://bar.example.net/foo.html.  It already has a (complete)
   cache entry for this URI, with entity tag "A", so it issues this
   request:



Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 17]

Internet-Draft               Delta encoding       19 February 1999 15:55


      GET /foo.html HTTP/1.1
      host: bar.example.net
      If-None-Match: "A"
      Accept-Encoding: vcdiff

   Suppose that the server's current instance has entity tag "B", so the
   server responds:

      HTTP/1.1 226 Delta
      Etag: "B"
      Content-Encoding: vcdiff
      Date: Tue, 25 Nov 1997 18:30:05 GMT
      Content-Length: 1000

      ...

   but the network connection is terminated after the client has
   received exactly 900 bytes of the message body for the delta-encoded
   content.

   The client wants to retrieve the remaining 100 bytes of the
   delta-encoding that was being sent in the interrupted response.  It
   therefore should send:

      GET /foo.html HTTP/1.1
      host: bar.example.net
      If-None-Match: "A"
      If-Range: "B"
      Accept-Encoding: vcdiff
      Range: 900-

   This rather elaborate request has a well-defined meaning, which
   depends on the current entity tag Tcur of the instance when the
   server receives the request:

   Tcur = "A"       (i.e., for some reason, the instance has reverted to
                   the value already in the client's cache).  The server
                   must return a 304 (Not Modified) response, as
                   required by the HTTP/1.1 specification for
                   ``If-None-Match''.

   Tcur = "B"       (i.e., the instance has not changed again).  The
                   HTTP/1.1 specification for ``If-None-Match'', in this
                   case, is that the header field is ignored (by a
                   server that does not understand delta encoding).
                   Therefore, this is equivalent to the client's
                   previous request, except that the Range selection is
                   applied after content-coding.  So the (delta-aware)
                   server again computes the delta between the "A"
                   instance and the "B" instance (or uses a cached
                   computation of the delta), then applies the Range

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 18]

Internet-Draft               Delta encoding       19 February 1999 15:55


                   selection, and returns a 227 (Range of Delta)
                   response.

   Tcur = "C"       (i.e., the instance has changed again).  In this
                   case, the HTTP/1.1 specification for
                   ``If-None-Match'' again means that this is equivalent
                   to an unconditional request for the current instance.
                   The specification for ``If-Range'' requires the
                   server to return the entire current entity.  However,
                   a delta-aware server can construct the delta between
                   the "A" instance described by the ``If-None-Match''
                   field and the current ("C") instance, and return a
                   226 (Delta) response.

   If the client's request had not included the ``If-None-Match: "A"''
   header field, the server could not have computed a delta, since it
   would not have known which entire instance was already available to
   the client.  If the request had not included the ``If-Range: "B"''
   header field, the server could not have distinguished between the
   latter two cases (Tcur = "B" or Tcur = "C") and would not have been
   able to apply the Range selection to the result of delta encoding.


6 Encoding algorithms and formats

   A number of delta encoding algorithms and formats have been described
   in the literature:

   diff -e          The UNIX ``diff'' program is ubiquitously available,
                   and is relatively fast for both encoding and decoding
                   (decoding is actually done using the ``ed'' program).
                   However, the size of the resulting deltas is
                   relatively large.  This algorithm can only be used on
                   text-format files.

   diff -e | gzip   Running the output of ``diff'' through a compression
                   algorithm such as ``gzip'' [5] (or, perhaps better,
                   ``deflate'' [7, 6]) yields a more compact encoding,
                   but the costs of encoding and decoding are much
                   higher than for ``diff'' by itself.  This algorithm
                   can only be used on text-format files.

   vcdiff (vdelta)  The algorithm that generates the ``vcdiff''
                   format [19, 20] inherently compresses its output, and
                   generally produces smaller results than the
                   combination of ``diff'' and ``gzip''.  The algorithm
                   also runs much faster, and can be applied to
                   binary-format input.  The ``vcdiff'' format is based
                   on previous work on an algorithm named ``vdelta.''
                   (Note that the ``vcdiff'' format can be used either
                   for delta encoding or as a compressed format, so

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 19]

Internet-Draft               Delta encoding       19 February 1999 15:55


                   different coding names are used in HTTP to
                   distinguish these two uses.)  A recent study suggests
                   that ``vdelta'' is the best overall delta
                   algorithm [17].

   gdiff            The gdiff format [15] was specified as a generic,
                   algorithm-independent format for expressing deltas.
                   Because it is more generic it is easy to implement,
                   but it may not be the most compact encoding format.

   Our proposal does not recommend any specific algorithm or format, but
   rather encourages client and server implementors to choose the most
   appropriate one(s).  However, to avoid the possibility of excessively
   long ``Accept-Encoding'' (or ``TE'') headers, we suggest that, after
   some period of experimentation, it might be reasonable to specify a
   ``recommended'' set of delta formats for general-purpose HTTP
   implementations.

   We suspect that it should be possible to devise a delta encoding
   algorithm appropriate for use on typical image encodings, such as GIF
   and JPEG.  Although experiments with vdelta have not shown much
   potential [23], this may simply be because these experiments used
   vdelta directly on the already-compressed forms of these encodings.
   However, it might be necessary to devise a delta encoding algorithm
   that is aware of the two-dimensional nature of images.  We have some
   expectation that this is possible, since MPEG compression relies on
   computing deltas between successive frames of a video stream.

6.1 IANA Considerations
   The Internet Assigned Numbers Authority (IANA) administers the name
   spaces for HTTP content-coding and transfer-coding values.  The sets
   of delta-content-coding values and delta-transfer-coding values are
   subsets, respectively, of the sets of HTTP content-coding and
   transfer-coding values, and are therefore subject to the rules
   established for these IANA registries by the HTTP/1.1
   specification [11].


7 Management of base instances

   If the time between modifications of a resource is less than the
   typical eviction time for responses in client caches, this means that
   the ``old instance'' indicated in a client's conditional request
   might not refer to the most recent prior instance.  This raises the
   question of how many old instances of a resource should be maintained
   by the server, if any.  We call these old instances ``base
   instances.''

   There are many possible options for server implementors.  For
   example:


Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 20]

Internet-Draft               Delta encoding       19 February 1999 15:55


      - The server might not store any old instances, and so would
        never respond with a delta.

      - The server might only store the most recent prior instance;
        requests attempting to validate this instance could be
        answered with a delta, but requests attempting to validate
        older instances would be answered with a full copy of the
        resource.

      - The server might store all prior instances, allowing it to
        provide a delta response for any client request.

      - The server might store only a subset of the prior
        instances.  The use of an LRU algorithm to determine this
        kind of subset has proved effective in some similar
        circumstances, such as cache replacement.

   The server might not have to store prior instances explicitly.  It
   might, instead, store just the deltas between specific base instances
   and subsequent instances (or the inverse deltas between base
   instances and prior instances).  This approach might be integrated
   with a cache of computed deltas.

   None of these approaches necessarily requires additional protocol
   support.  However, if a server administrator wants to store only a
   subset of the prior instances, but would like the server to be able
   to respond using deltas as often as possible, then the client needs
   some additional information.  Otherwise, the client's
   ``If-None-Match'' header might specify a base instance not stored at
   the server, even though an appropriate base instance is held in the
   client's cache.

   We identify two additional protocol changes to help solve this
   problem.

7.1 Multiple entity tags in the If-None-Match header
   Although the examples we have given so far show only one entity tag
   in an ``If-None-Match'' header, the HTTP/1.1 specification allows the
   header to carry more than one entity-tag.  This feature was included
   in HTTP/1.1 to support efficient caching of multiple variants of a
   resource, but it is not restricted to that use.

   Suppose that a client has kept more than one instance of a resource
   in its cache.  That is, not only does it keep the most recent
   instance, but it also holds onto copies of one or more prior, invalid
   instances.  (Alternatively, it might retain sufficient delta or
   inverse-delta information to reconstruct older instances.)  In this
   case, it could use its conditional request to tell the server about
   all of the instances it could apply a delta to.  For example, the
   client might send:


Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 21]

Internet-Draft               Delta encoding       19 February 1999 15:55


      GET /foo.html HTTP/1.1
      host: bar.example.net
      If-None-Match: "123xyz", "337pey", "489uhw"
      Accept-Encoding: vcdiff

   to indicate that it has three instances of this resource in its
   cache.  If the server is able to generate a delta from any of these
   prior instances, it can select the appropriate base instance, compute
   the delta, and return the result to the client.

   In this case, however, the server must also tell the client which
   base instance to use, and so we need to define a response header,
   named ``Delta-base'', for this purpose.  For example, the server
   might reply:

      HTTP/1.1 226 Delta
      ETag: "1acl059"
      Content-Encoding: vcdiff
      Delta-base: "337pey"
      Date: Tue, 25 Nov 1997 18:30:05 GMT

   This response tells the client to apply the delta to the cached
   response with entity tag ``337pey'', and to associate the entity tag
   ``1acl059'' with the result.

   Of course, if the server has retained more than one of the prior
   instances identified by the client, this could complicate the problem
   of choosing the optimal delta to return, since now the server has a
   choice not only of the delta format, but also of the base instance to
   use.

7.2 Hints for managing the client cache
   Support for multiple entity tags in choosing the base instance
   implies that a client might benefit from storing multiple old
   instances of a resource in its cache.  A client with finite space
   would not want to keep all old instances, so it must manage its cache
   for maximal effectiveness by saving those instances most likely to be
   useful for future deltas.  Although this could be accomplished using
   information purely local to the client (e.g., an LRU algorithm),
   certain ``hint'' information from the server could improve the
   client's ability to manage its cache.  The use of hints for improving
   Web cache performance has been described previously [22, 4].

   If the server intends to retain certain instances and not others, it
   can label the responses that transmit the retained instances.  This
   would help the client manage its cache, since it would not have to
   retain all prior instances on the possibility that only some of them
   might be useful later.  The label is a hint to the client, not a
   promise that the server will indefinitely retain an instance.



Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 22]

Internet-Draft               Delta encoding       19 February 1999 15:55


   We propose adding a new directive to the existing ``Cache-control''
   header for this purpose, named ``retain''.  For example, in response
   to an unconditional request, the server might send:

      HTTP/1.1 200 OK
      ETag: "337pey"
      Date: Tue, 25 Nov 1997 18:30:05 GMT
      Cache-control: retain

   to suggest that a delta-capable client should retain this instance.
   The ``retain'' directive could also appear in a delta response:

      HTTP/1.1 226 Delta
      ETag: "1acl059"
      Date: Tue, 25 Nov 1997 18:30:05 GMT
      Cache-control: retain
      Content-Encoding: vcdiff
      Delta-base: "337pey"

   The ``retain'' directive includes an optional timeout parameter,
   which the server can use if it expects to delete an old base instance
   at a particular time.  For example,

      HTTP/1.1 200 OK
      ETag: "337pey"
      Date: Tue, 25 Nov 1997 18:30:05 GMT
      Cache-control: retain=3600

   means that the server intends to retain this base instance for one
   hour.

   Another situation where a server can provide a hint to a client is
   where the server supports the delta mechanism in general, but does
   not intend to provide delta-encoded responses for a particular
   resource.  By sending a ``retain=0'' directive, it indicates that the
   client should not waste request-header bytes attempting to obtain a
   delta-encoded response using this base instance (and, by implication,
   for this resource).  It also indicates that the client ought not
   waste cache space on this instance after it has become stale.  To
   avoid wasting response-header bytes, a server ought not send
   ``retain=0'' except in reply to a request that attempts to obtain a
   delta-encoded response.

   Note that the ``retain'' directive is orthogonal to the ``max-age''
   directive.  The ``max-age'' directive indicates how long a cache
   entry remains fresh (i.e.,can be used without contacting the origin
   server for revalidation); the ``retain'' directive is of interest to
   a client after the cache entry has become stale.

   In practice, the ``Cache-control'' response-header field might
   already be present, so the cost (in bytes) of sending this directive
   might be smaller than these examples implies.
Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 23]

Internet-Draft               Delta encoding       19 February 1999 15:55


8 Delta-encoding and clustering

   The basic delta-encoding model assumes that deltas are computed
   between two instances of a specific resources; i.e., both deltas are
   associated with a single URL.  However, the WebExpress project [16]
   suggested that by treating a query URL (that is, a URL with an
   embedded ``?'')  as a prefix followed by a set of parameters, one
   could then profitably compute deltas between resource values whose
   URLs have identical prefixes, but perhaps different parameters
   (suffixes).  Our trace-based study confirmed this [23].  We believe
   that this might be generalized to certain other patterns of URLs
   (i.e., not just those using ``?'' as a separator).  We use the term
   ``clustering'' for this approach.

   For example, if a client has cached a response for a DEC stock quote
   (``http://quote.yahoo.com/q?s=DEC&d=f''), and then requests a quote
   for AT&T from the same server (``http://quote.yahoo.com/q?s=T&d=f''),
   the prefix for the cluster would be ``http://quote.yahoo.com/q?''.

   In order to support clustering, we need a mechanism for the server to
   indicate to the client which URLs are eligible for clustering (since
   it would be highly inefficient for the client to send the entity tags
   of every resource in its cache on every request).

   We propose a new, optional response header for this purpose, to
   specify a URL-prefix for other resources that ``cluster'' with the
   given response.  The header name is ``DCluster''.

   Once a cluster-eligible response is cached, when the client is about
   to make a subsequent request, it would match the request-URI against
   all of the URL-prefixes in its cache.  The ``If-None-Match'' field in
   its request could then list the entity tags for all of the matching
   entries.  In some cases, it might be more efficient to list only a
   subset (such as the most recently received cache entries), to avoid
   excessive request header lengths.

   For example, if a client makes this initial request:

      GET /foo?p=1 HTTP/1.1
      Host: bar.example.net

   and receives this response:

      HTTP/1.1 200 OK
      Date: Sun, 06 Nov 1994 08:49:37 GMT
      Etag: "abc"
      DCluster: "//bar.example.net/foo?"

   then when the client later makes a request for
   ``http://bar.example.net/foo?p=2'', it can match the stored cluster
   prefix in its cache, and generate this request:

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 24]

Internet-Draft               Delta encoding       19 February 1999 15:55


      GET /foo?p=2 HTTP/1.1
      Host: bar.example.net
      If-None-Match: "abc"
      Accept-encoding: vcdiff

   As a generalization, the DCluster header field may include multiple
   URL-prefixes, to allow specification of a set of URIs that do not
   share a single common prefix.

   In order to use this approach to clustering, we need to impose one
   important constraint.  HTTP/1.1 requires so-called ``strong'' entity
   tags to be unique for a given URI, but does not impose any broader
   uniqueness requirements.  However, if a server sends a ``DCluster''
   header, this implies that the entity tag in the response is unique
   not only for the Request-URI, but also for all URIs for which the
   string given by ``DCluster'' is a prefix.

   We call this set of URIs the ``uniqueness scope'' of the entity tag.
   Note that a response might carry multiple ``DCluster'' header fields
   (or, by the basic HTTP syntax rules, one such header field with a
   comma-separated list of prefix strings).  This means that the
   uniqueness scope is the union of the scopes specified by the set of
   prefixes, plus the original Request-URI.  Because the URI in a
   ``DCluster'' header field can be an absolute URI (i.e., contain a
   host name), a uniqueness scope can span multiple servers.
   Presumably, these servers have some out-of-band means to maintain the
   uniqueness property.

   A client making a request may have cache entries for many different
   resources in the uniqueness scope of the Request-URI.  This is
   another situation where the ability of ``If-None-Match'' to carry
   multiple entity tags is employed.  Abstractly, when the client makes
   a request for which it wants a delta-encoded response, it finds all
   of its cache entries in the same uniqueness scope, then sends the
   entity tags for these cache entries in an ``If-None-Match'' header.

   It would not make sense to have an extremely broad uniqueness scope
   (i.e., one that includes large numbers of resources), because this
   would imply that a client that has cache entries for many of those
   files would send lots of entity-tags in its request for a delta.
   This would bloat the request message, obviating the transfer-time
   reduction of the delta encoding.  Therefore, in actual use, the
   ``DCluster'' header field value should represent not the entire
   uniqueness scope, but a subset of the uniqueness scope that is most
   likely to result in small deltas.

   Client implementations, however, should be prepared to prune their
   ``If-None-Match'' headers in case a server inadvertently (or
   maliciously) specifies an over-broad uniqueness scope.



Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 25]

Internet-Draft               Delta encoding       19 February 1999 15:55


   Server implementation that support clustering should minimize the
   length of the entity tags that they generate, consistent with the
   other requirements for entity tags, since the effect of overlong
   entity on request-header size is potentially multiplied many times by
   the use of clustering.

   Note that the ``DCluster'' header can be used in a potential spoofing
   attack.  This attack, and defenses against it, are discussed in
   section 16.1.


9 Use of templates

   The model of delta encoding outlined so far requires the server to
   compute a delta between the current instance of the resource and some
   previous instance of that resource, or (if clustering is used) a
   previous instance of some other resource.  This means that the base
   instance is, in effect, a moving target, since we do not want to
   require servers or clients to retain old instances for indefinite
   periods.

   Douglis et al. describe an approach to dynamically-generated
   documents in which the document is broken down into separate static
   and dynamic parts [9].  The static part is a macro with unbound
   variables, and the dynamic part is a set of bindings between
   variables and specific values.  In their mechanism, the client
   retains the static part, called a ``template'' in its cache.  It
   repeatedly requests, as needed, a new instance of the dynamic part,
   and then reevaluates the template macro, with its variables bound as
   specified in the dynamic part, in order to generate the current
   instance of the entire document.  Their macro language is an
   extension to HTML, although other languages (such as Java) might be
   just as suitable.

   The WebExpress project [16] adopted the concept of a designated
   ``base object'', which is nearly identical to the template concept
   described here.  WebExpress included a mechanism for ``rebasing'' a
   client (providing it with a new base object).  The primary difference
   between the WebExpress approach and our approach is the time at which
   a client discovers the identity of a (possibly new) template.

   We can apply a similar template-based mechanism to substantially
   simplify the use of delta encoding.  In this approach, the server
   ``computes'' the delta between the current instance of a resource,
   and a separately-identified template resource.  (Depending on the
   encoding format, it might be possible to generate the delta directly,
   rather than generating the current instance and then computing a
   delta.)  The client then applies the delta to the template resource,
   rather than to a previous instance of the requested resource.



Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 26]

Internet-Draft               Delta encoding       19 February 1999 15:55


   Since this approach avoids the need to retain old instances of the
   dynamic resource at either the client or the server, it greatly
   simplifies the implementation and optimization of base instance
   management at both client and server.  However, it requires a new
   mechanism to inform the client of the appropriate template resource,
   and its success may depend on the proper construction of the
   template.

   To support template-base deltas, therefore, we define a new response
   header that the origin server uses as a ``hint'' to inform a client
   of the URI of the template resource.  For example, if the client
   request is

      GET /foo.html HTTP/1.1
      Host: bar.example.net
      Accept-Encoding: vcdiff

   the server might send:

      HTTP/1.1 200 OK
      Date: Sun, 06 Nov 1994 08:49:37 GMT
      Etag: "abc"
      DTemplate: "http://bar.example.net/foo.tplt"

   The implication of the DTemplate header is that, on subsequent
   requests for http://bar.example.net/foo.html, the client should ask
   for a delta between http://bar.example.net/foo.tplt and the current
   instance.  This means, of course, that the client would first have
   obtained and cached an instance of http://bar.example.net/foo.tplt.
   The client might retrieve the template either on demand (i.e., just
   before making the new request for foo.html), or during an otherwise
   idle moment, or not at all (since the use of deltas is fully
   optional).

   The DTemplate header implies that the specified URL is within the
   uniqueness scope of the Request-URI (or else it would not be possible
   to ask for a delta between the template and the Request-URI).  For
   example, if the client requests the template:

      GET /foo.tplt HTTP/1.1
      Host: bar.example.net

   and receives the response:

      HTTP/1.1 200 OK
      Date: Sun, 06 Nov 1994 08:49:47 GMT
      Etag: "pqr"

   then the client can make a subsequent request for foo.html as:



Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 27]

Internet-Draft               Delta encoding       19 February 1999 15:55


      GET /foo.html HTTP/1.1
      Host: bar.example.net
      If-None-match: "pqr"
      Accept-Encoding: vcdiff

   Alternatively, the DTemplate header field can be used to specify that
   a specific instance of a resource (rather than any available
   instance) be used as a template, by including an entity tag in the
   header field.  For example:

      HTTP/1.1 200 OK
      Date: Sun, 06 Nov 1994 08:49:37 GMT
      Etag: "abc"
      DTemplate: "http://bar.example.net/foo.tplt"/etag="pqr"

   This form of the header further simplifies the instance-management
   problem, by eliminating any ambiguity about which instances are worth
   saving.  It might, however, reduce the possibilities for delta
   encoding.

   Finally, the DTemplate and DCluster headers can be combined.  For
   example:

      HTTP/1.1 200 OK
      Date: Sun, 06 Nov 1994 08:49:37 GMT
      Etag: "abc"
      DTemplate: "http://bar.example.net/foo.tplt"
      DCluster: "//bar.example.net/foo?"

   This means that for any Request-URI matching the prefix specified in
   the DCluster header field, the URI specified in the DTemplate field
   is an appropriate template.

   Note that an origin server ought not necessarily send a DTemplate
   header field on every response; doing so could waste network
   bandwidth, if the recipient is not delta-capable.  Instead, the
   server should employ heuristics to decide whether to send this header
   field.  For example, it might be worth sending it whenever the
   client's request message indicates its willingness to accept a
   delta-encoded response, and when the If-None-Match field in the
   request does not already specify the entity-tag of the template
   resource.


10 Deltas and intermediate caches

   Although we have designed the delta-encoded responses so that they
   will not be stored by naive proxy caches, if a proxy does understand
   the delta mechanism, it might be beneficial for it to participate in
   sending and receiving deltas.


Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 28]

Internet-Draft               Delta encoding       19 February 1999 15:55


   A proxy could participate in several independent ways:

      - In addition to forwarding a delta-encoded response, the
        proxy might store it, and then use it to reply to a
        subsequent request with a compatible ``If-None-Match''
        field (i.e., one that is either a superset of the
        corresponding field of the request that first elicited the
        response, or one that includes the ``Delta-base'' value in
        the cached response), and with a compatible
        ``Content-Encoding'' or ``Transfer-Encoding'' field (one
        that includes the actual delta-encoding used in the
        response.)  Of course, such uses are subject to all of the
        other HTTP rules concerning the validity of cache entries.

      - In addition to forwarding a delta-encoded response, the
        proxy might apply the delta to the appropriate entry in its
        own cache, which could then be used for later responses
        (even from non-delta-capable clients).

      - When the proxy receives a conditional request from a
        delta-capable client, and the proxy has a complete copy of
        an up-to-date (``fresh,'' in HTTP/1.1 terminology) response
        in its cache, it could generate a delta locally and return
        it to the requesting client.

      - When the proxy receives a request from a non-delta-capable
        client, it might convert this into a delta request before
        forwarding it to the server, and then (after applying a
        resulting delta response to one of its own cache entries)
        it would return a full-body response to the client.

   All of these optional techniques increase proxy software complexity,
   and might increase proxy storage or CPU requirements.  However, if
   applied carefully, they should help to reduce the latencies seen by
   end users, and load on the network.  Generally, CPU speed and disk
   costs are improving faster than network latencies, so we expect to
   see increasing value available from complex proxy implementations.


11 Digests for data integrity

   When a recipient reassembles a complete HTTP response from several
   individual messages, it might be necessary to check the integrity of
   the complete response.  For example, the client's cache might be
   corrupt, or the implementation of delta-encoding (either at client or
   server) might have a bug, or a malicious server could have sent a
   bogus ``Dcluster'' header.

   HTTP/1.1 includes mechanisms for ensuring the integrity of individual
   messages.  A message may include a ``Content-MD5'' response header,
   which provides an MD5 message digest of the body of the message (but

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 29]

Internet-Draft               Delta encoding       19 February 1999 15:55


   not the headers).  The Digest Authentication mechanism [12] provides
   a similar message-digest function, except that it includes certain
   header fields.  Neither of these mechanisms makes any provision for
   covering a set of data transmitted over several messages, as would be
   the case for the result of applying a delta-encoded response (or, for
   that matter, a Range response).

   Data integrity for reassembled messages requires the introduction of
   a new message header.  Such a mechanism is proposed in a separate
   document [24].  One might still want to use the Digest Authentication
   mechanism, or something stronger, to protect delta messages against
   tampering.


12 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 [3].

12.1 Protocol parameter specifications
   This specification defines no new HTTP parameter types.  It does,
   however, extend the sets of content-codings and transfer-codings.

   The set of content-coding values is extended:

       content-coding = token | delta-content-coding
       delta-content-coding = token

   The set of delta-content-coding values is initially:

      - vcdiff
        A delta using the ``vcdiff'' encoding format [19, 20].

      - diffe
        The output of the UNIX ``diff -e'' command [25].

      - gdiff
        The GDIFF encoding format [15].

   An HTTP implementation that supports any delta-content-coding values
   SHOULD support the vcdiff format.  This provides an efficient ``least
   common denominator'' delta-content-encoding format.  This is not a
   mandatory requirement of the specification.

   The set of transfer-coding values is extended:

       transfer-coding = token | delta-transfer-coding
       delta-transfer-coding = token



Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 30]

Internet-Draft               Delta encoding       19 February 1999 15:55


   The set of delta-transfer-coding values is initially:

      - vcdiff
        A delta using the ``vcdiff'' encoding format [19, 20].

      - diffe
        The output of the UNIX ``diff -e'' command [25].

      - gdiff
        The GDIFF encoding format [15].

   An HTTP implementation that supports any delta-transfer-coding values
   SHOULD support the vcdiff format.  This provides an efficient ``least
   common denominator'' delta-transfer-encoding format.  This is not a
   mandatory requirement of the specification.

12.2 Status code specifications
   The following new status codes are defined for HTTP.  (Note that the
   precise 3-digit values for these codes may change, as a result of the
   process now being considered for allocating HTTP status codes [26].)

12.2.1 226 Delta
   The server has fulfilled a GET request for the resource, and is
   returning a delta between the current instance of the resource and a
   previous instance.  The request MUST have included an Accept-Encoding
   header field listing at least one delta-content-coding.  The response
   MUST include an Etag header field giving the entity tag of the
   current instance, and SHOULD include a Delta-Base header field giving
   the entity tag of the previous instance.

   A response received with a status code of 226 MAY be stored by a
   cache and used in reply to a subsequent request (subject to the HTTP
   expiration mechanism and any Cache-control headers), if
   content-coding is consistent with the Accept-Encoding field of the
   subsequent request, and if that request does not include a Range
   header.

   A response received with a status code of 226 MAY be used by a cache,
   in conjunction with a cache entry for the base instance, to create a
   cache entry for the current instance.

12.2.2 227 Range of Delta
   The server has fulfilled a partial GET request for the resource, and
   is using, as a content-coding, a delta between the current instance
   of the resource and a previous instance.  The request MUST have
   included an Accept-Encoding header field listing at least one
   delta-content-coding.  The response MUST include an Etag header field
   giving the entity tag of the current instance, and SHOULD include a
   Delta-Base header field giving the entity tag of the previous
   instance.  Except for its status code, the response meets the
   requirements for a 206 (Partial Content) response.

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 31]

Internet-Draft               Delta encoding       19 February 1999 15:55


   A response received with a status code of 227 MAY be may be stored by
   a cache and used in reply to a subsequent request (subject to the
   HTTP expiration mechanism and any Cache-control headers), if
   content-coding is consistent with the Accept-Encoding field of the
   subsequent request, and if that request includes a Range header
   consistent with the Content-Range header(s) in the response, and if
   the cache meets the requirements stated for caching of 206 (Partial
   Contents) responses.

   A response received with a status code of 227 MAY be used by a cache,
   in conjunction with a cache entry for the base instance, to create or
   update a partial cache entry for the current instance, if the cache
   supports the Content-Range header.

12.3 Header specifications
   The following headers are defined, for use as entity-headers.  (Due
   to the terminological confusion discussed in section 3, some
   entity-headers are more properly associated with instances than with
   entities.)

12.3.1 Delta-Base
   The Delta-Base entity-header field is used in a delta-encoded
   response to specify the entity tag of the base instance.  A
   delta-encoded response has a status code of 226 (Delta) or 227 (Range
   of Delta).  A delta-encoded response encodes the difference between
   the current instance of the requested resource, and some other
   instance of the same resource, or of a different resource in the same
   uniqueness scope.

       Delta-Base = "Delta-Base" ":" entity-tag

   A Delta-Base header field MUST be included in a 226 (Delta) or 227
   (Range of Delta) response if the request included more than one
   entity tag in its If-None-Match header field, or if the uniqueness
   scope for an entity tag of any instance of the requested resource has
   ever included another resource.  Any 226 or 227 response MAY include
   a Delta-base header.

      ---------
      We are not aware of other cases where a delta-encoded response
      MUST or SHOULD include a Delta-base header, but we have not
      done an exhaustive or formal analysis.  Implementors might be
      wise to include a Delta-base header in every 226 or 227
      response.
      ---------

12.3.2 DCluster
   The DCluster entity-header field is used in a response to specify a
   subset of the uniqueness scope of the entity tag given in the Etag
   header field of the response.  The uniqueness scope is the set of
   URIs across which this strong entity tag is guaranteed to be unique,

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 32]

Internet-Draft               Delta encoding       19 February 1999 15:55


   for all time.  A uniqueness scope is specified by providing one or
   more prefixes for other URIs in the set.

       DCluster = "DCluster" ":" #( <"> uri-prefix <">)
       uri-prefix = scheme ":" "//" host [ ":" port ] [ abs_path ]
               | abs_path
               | rel_path

   If the uri-prefix is an abs_path or rel_path, the implied scheme is
   the scheme used in the Request-URI.  (Typically, the scheme would be
   "http".)  If the uri-prefix is an abs_path, it is interpreted
   relative to the origin server host name.  If the uri-prefix is a
   rel_path, it is interpreted relative to the Request-URI.

   The uniqueness scope of a strong entity tag in an ETag header field
   always includes the Request-URI of the corresponding request, and the
   union of all URIs matching one or more of the uri-prefix strings in
   the DCluster header field of the response.  It may include other URIs
   not described in a DCluster header field.  That is, the set of URIs
   for which a uri-prefix in a DCluster header field is a prefix MUST be
   a subset of the uniqueness scope, and MAY be a proper subset.

   Generally, the DCluster header does not necessarily describe the
   entire uniqueness scope of an entity tag.  Rather, it describes a
   subset of the uniqueness scope whose members are likely to differ by
   small deltas.

12.3.3 DTemplate
   The DTemplate entity-header field is used in a response to specify
   another resource that the origin server prefers to use as the base
   instance for computing deltas for the Request-URI, or for other
   resources in the uniqueness scope specified by a DCluster header
   field in the response.

       DTemplate = "DTemplate" ":"
                        #( <"> dt-uri <"> [ "/" dt-param])
       dt-uri = absoluteURI | abs_path
       dt-param = "etag" "=" entity-tag

   If the dt-uri is an abs_path, it is interpreted relative to the
   origin server host name.

   A URI specified in a DTemplate header field is, by definition, in the
   uniqueness scope of the Request-URI.

   If a client has received a DTemplate header field within a given
   uniqueness scope, the client SHOULD use an instance of the specified
   template resource(s) as the base instance for any future delta
   requests for other resources in the uniqueness scope.



Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 33]

Internet-Draft               Delta encoding       19 February 1999 15:55


   If the DTemplate header field includes an entity tag with a URI, then
   the client SHOULD use only the specified instance of the template
   resource base instance for any future delta requests for other
   resources in the uniqueness scope.


13 New requirements for existing headers

13.1 Accept-Encoding
   When an Accept-Encoding request-header field includes one or more
   delta-content-coding values, the request MUST contain an
   If-None-Match header field, listing one or more entity tags from URIs
   in the uniqueness scope of an entity tag from a prior response for
   the request-URI.

   If a response uses a delta-content-coding as a content-coding, and
   the response uses more than one non-identity content-coding, the
   content-codings MUST be applied in the order in which they appear in
   the Accept-Encoding request-header field.

   A server MUST NOT use a delta-content-coding for a response unless
   the delta-content-coding is listed in an Accept-Encoding header in
   the request.

13.2 TE
   When a TE request-header field includes one or more
   delta-transfer-coding values, the request MUST contain an
   If-None-Match header field, listing one or more entity tags from URIs
   in the uniqueness scope of an entity tag from a prior response for
   the request-URI.

   If a response uses a delta-transfer-coding as a transfer-coding, and
   the response uses more than one non-identity transfer-coding, the
   transfer-codings MUST be applied in the order in which they appear in
   the TE request-header field.

   A server MUST NOT use a delta-transfer-coding for a response unless
   the delta-transfer-coding is listed in a TE header in the request.

13.3 Use of compression with delta encoding
   The application of data compression to the diffe and gdiff delta
   codings has been shown to greatly reduce the size of the resulting
   message bodies, in many cases.  (The vcdiff coding, on the other
   hand, is inherently compressed and does not benefit from further
   compression.)  Therefore, it is strongly recommended that
   implementations that support the diffe and/or gdiff delta codings
   also support the gzip and/or deflate compression codings.  (The
   deflate coding provides a more compact result.)  However, this is not
   a requirement for the use of delta encoding, primarily because the
   CPU-time costs associated with compression and decompression may be
   excessive in some environments.

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 34]

Internet-Draft               Delta encoding       19 February 1999 15:55


   A client that supports both delta encoding and compression as
   content-codings signals this by, for example

      Accept-Encoding: diffe, deflate

   The ordering rule stated in section 13.1 requires that, if the server
   uses both content-codings in the response, that compression is
   applied to the result of the delta encoding, rather than vice versa.
   I.e., the response in this case would include

      Content-Encoding: diffe, deflate

   If the client is willing to accept a variety of delta
   content-codings, and is also willing to accept compression of the
   results, its Accept-Encoding header would list the delta
   content-codings before the compression content-codings.  For example,

      Accept-Encoding: diffe, vcdiff, gdiff, deflate, gzip

   is an appropriate (if lengthy) listing.

   For transfer-codings, analogous guidelines apply.

13.4 Delta encoding and multipart/byteranges
   A client may request multiple, non-contiguous byte ranges in a single
   request.  The server's response uses the ``multipart/byteranges''
   media type (section 19.2 of [11]) to convey multiple ranges in a
   response.  If a multipart/byteranges response is delta-encoded (using
   either a content-coding or a transfer-coding), the delta-related
   headers are associated with the entire response, not with the
   individual parts.  (This is because there is only one base instance
   and one current instance involved.)  A delta-encoded response with
   multiple ranges MUST use the same delta-content-coding or
   delta-transfer-coding for all of the ranges.

   A server MAY choose not to use a delta encoding for a
   multipart/byteranges response, but if it does use such an encoding,
   it MUST generate a response in accordance with the following rules.

   When a multipart/byteranges response uses a delta content-coding,
   this coding is applied prior to the selection of the byte ranges (see
   section 4).  In other words, the server firsts generates a sequence
   of bytes representing the difference (delta) between the two
   instances, then selects the specified ranges of bytes, and transmits
   each such range in a part of the multipart/byteranges media type.

   When a multipart/byteranges response uses a delta transfer-coding,
   however, this coding is applied after the selection of the byte
   ranges (see section 4).  In other words, the server first selects the
   specified ranges from the current instance, and also selects the
   specified ranges from the base instance.  (Some of these selected

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 35]

Internet-Draft               Delta encoding       19 February 1999 15:55


   ranges might be the empty sequence, if the instance is not long
   enough.)  The server then generates the individual differences
   (deltas) between the pairs of ranges, and transmits each such
   difference in a part of the multipart/byteranges media type.


14 New Cache-control directives

   The set of cache-response-directive values is augmented to include
   the retain directive.

               | "retain" [ "=" delta-seconds ]

   A retain directive is always a ``hint'' from a server to a client; it
   never specifies a mandatory action for the recipient.

   The presence of a retain directive indicates that a delta-capable
   client ought to retain the instance in the response in its cache,
   space permitting, and ought to use the corresponding entity tag in a
   future request for a delta-encoded response.  I.e., the server is
   likely to provide delta-encoded responses using the corresponding
   instance as a base instance.  By implication, if a client has
   retrieved and cached several instances of a resource, some of which
   are marked with ``retain'' and some not, then there is no point in
   caching the instances not marked with ``retain''.

   If the retain directive includes a delta-seconds value, then the
   server is likely to stop using the corresponding instance as a base
   instance after the specified number of seconds.  A client ought not
   use the corresponding entity tag in a future request for a
   delta-encoded response after that interval ends.  The interval is
   measured from the time that the response is generated, so a client
   ought to include the response's Age in its calculations.

   If the retain directive includes a delta-seconds value of zero, a
   client SHOULD NOT use the corresponding entity tag in a future
   request for a delta-encoded response.  A server SHOULD NOT send
   ``retain=0'' except in reply to a request that attempts to obtain a
   delta-encoded response.


15 Quantifying the protocol overhead

   The proposed protocol changes increase the size of the HTTP message
   headers slightly.  In the simplest case, a conditional request (i.e.,
   one for a URI for which the client already has a cache entry) would
   include one more header, e.g.:

       Accept-Encoding:vcdiff

   This is about 24 extra bytes.  A recent study [23] reports mean

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 36]

Internet-Draft               Delta encoding       19 February 1999 15:55


   request sizes from two different traces of 281 and 306 bytes, so the
   net increase in request size would be between 8% and 9%.  Smaller
   increases would result for requests that already include an
   Accept-Encoding header field, or if the TE request header field were
   used instead (assuming that the TE header is not the only one needing
   to be listed in a Connection header.)

   Because a client must have an existing cache entry to use as a base
   for a delta-encoded response, it would never send ``Accept-encoding:
   vcdiff'' (or listing other delta encoding formats) for its
   unconditional requests.  The same study showed that at least 46% of
   the requests in lengthy traces were for URLs not seen previously in
   the trace; this means that no more than about half of typical client
   requests could be conditional (and the actual fraction is likely to
   be smaller, given the finite size of real caches).

   The study also showed that 64% of the responses in a lengthy trace
   were for image content-types (GIF and JPEG).  As noted in section 6,
   we do not currently know of a delta-encoding format suitable for such
   image types.  Unless a client did support such a delta-encoding
   format, it would presumably not ask for a delta when making a
   conditional request for image content-types.

   Taken together, these factors suggest that the mean increase in
   request header size would be much less than 9%, and probably closer
   to 2%.

   Delta-encoded responses carry slightly longer headers.  In the
   simplest case, a response carries one more header, e.g.:

       Content-Encoding:vcdiff

   This is about 25 bytes.  If a delta-transfer-coding is used instead
   (with a ``TE'' header), the increase is smaller.  Other headers (such
   as ``Delta-Base'' and ``DCluster'') might also be included.  However,
   none of these extra headers would be included except in cases where a
   delta encoding is actually employed, and the sender of the response
   can avoid sending a delta encoding if this results in a net increase
   in response size.  Thus, a delta-encoded response should never be
   larger than a regular response for the same request.

   Simulations suggest that, when delta-encoding pays off at all, it
   saves several thousand bytes [23].  Thus, adding a few dozen bytes to
   the response headers should almost never obviate the savings in the
   message-body size.

   Finally, the use of the ``retain'' Cache-control directive and the
   ``DCluster'' header in non-delta-encoded responses might cause some
   additional overhead.  Some server heuristics might be successful in
   limiting the use of these headers to situations where they would
   probably optimize future responses.  Neither of these headers is
   necessary for the simpler uses of delta encoding.
Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 37]

Internet-Draft               Delta encoding       19 February 1999 15:55


16 Security Considerations

16.1 Spoofing attacks using the DCluster header
   We have identified a potential spoofing attack via the ``DCluster''
   header. In this scenario, a malicious server (e.g.,
   malicious.example.org) generates a response (e.g., for
   http://malicious.example.org/trap.html) with a ``DCluster'' header
   indicating that the uniqueness scope of the entity tag in the
   response includes another server (e.g., victim.example.com).  Suppose
   that the response includes the entity tag "abc".  Now suppose that
   the client makes this request:

      GET /foo.html HTTP/1.1
      host: victim.example.com
      If-None-Match: "abc"
      Accept-Encoding: vcdiff

   If the victim.example.com server does actually have an instance with
   entity tag "abc", either for http://victim.example.com/foo.html or
   for a resource that really is in the same uniqueness scope, then the
   server will generate a delta.  However, if the client applies this
   delta to the cached response for
   http://malicious.example.org/trap.html, it will end up either with
   garbage, or (more perniciously) with an apparently genuine result
   that actually contains bogus information inserted by
   malicious.example.org.  (The response for
   http://malicious.example.org/trap.html might contain the bogus
   information concealed in HTML comments.)

   Protection against this attack can be accomplished by the use of
   end-to-end digests on the instances, as described in another
   proposal [24].  (Message digests, such as provided by ``Content-MD5''
   or by Digest Authentication, are not sufficient, since none of the
   individual messages are tampered with in this attack.)

   Note that protection against spoofing via the ``DCluster'' header
   does not inherently require a keyed digest.  Since the delta encoded
   response for http://victim.example.com/foo.html is not itself
   generated by malicious.example.org, an end-to-end digest included
   with this response by victim.example.com is sufficient to prove that
   the client's reconstruction of foo.html is correct.  However, if
   message tampering is also a possibility, then the server should also
   provide a keyed message digest.

   Another defense against such an attack is for the client to ignore a
   ``DCluster'' header that specifies a different server.  However, this
   defense is only effective if servers that generate delta-encoded
   responses are not shared among multiple, possibly mutually
   untrustworthy, content providers.  It also reduces the potential
   effectiveness of clustering, especially for large sites split across
   multiple servers.

Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 38]

Internet-Draft               Delta encoding       19 February 1999 15:55


   Note that because the DTemplate header field also adds one or more
   URIs to the uniqueness scope of an entity tag, the same spoofing
   attack is possible using the DTemplate header, and the same defenses
   apply.

   We recommend that if a client receives a delta-encoded response
   without an accompanying Digest, and if the client's view of the
   uniqueness scope for the Request-URI includes more than one server
   hostname, then the response should either be discarded, or presented
   to the user as potentially corrupt.


17 History

17.1 draft-mogul-http-delta-01.txt
   Renamed ``vdcode'' to ``vcdiff'', and corrected some of the
   references to vcode/vcdiff/vdelta.  Recommended use of vcdiff.

   Added section 13.4 on using delta encoding with multipart/byteranges
   responses.

   Updated IANA Considerations in section 6.1.


18 Acknowledgements

   Phong Vo has provided a great deal of guidance in the choice of delta
   encoding algorithms and formats.


19 References

   NOTE TO RFC EDITOR: many of the references here might be out of date.
   Please verify these with the primary author of this Internet-Draft
   before issuing this document as an RFC.

   1.  Gaurav Banga, Fred Douglis, and Michael Rabinovich.  Optimistic
   Deltas for WWW Latency Reduction.  Proc. 1997 USENIX Technical
   Conference, Anaheim, CA, January, 1997, pp. 289-303.

   2.  T. Berners-Lee, R. Fielding, and H. Frystyk.  Hypertext Transfer
   Protocol -- HTTP/1.0.  RFC 1945, HTTP Working Group, May, 1996.

   3.  S. Bradner.  Key words for use in RFCs to Indicate Requirement
   Levels.  RFC 2119, Harvard University, March, 1997.

   4.  Edith Cohen, Balachander Krishnamurthy, and Jennifer Rexford.
   Improving End-to-End Performance of the Web Using Server Volumes and
   Proxy Filters.  Proc. SIGCOMM '98, September, 1998, pp. 241-253.



Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 39]

Internet-Draft               Delta encoding       19 February 1999 15:55


   5.  P. Deutsch.  GZIP file format specification version 4.3.  RFC
   1952, Network Working Group, May, 1996.

   6.  P. Deutsch.  DEFLATE Compressed Data Format Specification version
   1.3.  RFC 1951, Network Working Group, May, 1996.

   7.  P. Deutsch and J-L. Gailly.  ZLIB Compressed Data Format
   Specification version 3.3.  RFC 1950, Network Working Group, May,
   1996.

   8.  Fred Douglis, Anja Feldmann, Balachander Krishnamurthy, and
   Jeffrey Mogul.  Rate of Change and Other Metrics:  a Live Study of
   the World Wide Web.  Proc. Symposium on Internet Technologies and
   Systems, USENIX, Monterey, CA, December, 1997, pp. 147-158.

   9.  Fred Douglis, Antonio Haro, and Michael Rabinovich.  HPP: HTML
   Macro-Preprocessing to Support Dynamic Document Caching.  Proc.
   USENIX Symposium on Internet Technologies and Systems, USENIX,
   Monterey, CA, December, 1997, pp. 83-94.

   10.  Roy T. Fielding, Jim Gettys, Jeffrey C. Mogul, Henrik Frystyk
   Nielsen, and Tim Berners-Lee.  Hypertext Transfer Protocol --
   HTTP/1.1.  RFC 2068, HTTP Working Group, January, 1997.

   11.  Roy T. Fielding, Jim Gettys, Jeffrey C. Mogul, Henrik Frystyk
   Nielsen, and Tim Berners-Lee.  Hypertext Transfer Protocol --
   HTTP/1.1.  Internet-Draft draft-ietf-http-v11-spec-rev-06, HTTP
   Working Group, November, 1998. This is a work in progress.

   12.  J. Franks, P. Hallam-Baker, J. Hostetler, P. Leach, A. Luotonen,
   E. Sink, L. Stewart.  An Extension to HTTP: Digest Access
   Authentication.  RFC 2069, HTTP Working Group, January, 1997.

   13.  N. Freed and N. Borenstein.  Multipurpose Internet Mail
   Extensions (MIME) Part One:  Format of Internet Message Bodies.  RFC
   2045, Network Working Group, November, 1996.

   14.  Arthur van Hoff, John Giannandrea, Mark Hapner, Steve Carter,
   and Milo Medin.  The HTTP Distribution and Replication Protocol.
   Technical Report NOTE-DRP, World Wide Web Consortium, August, 1997.
   URL http://www.w3.org/TR/NOTE-drp-19970825.html.

   15.  Arthur van Hoff and Jonathan Payne.  Generic Diff Format
   Specification.  Technical Report NOTE-GDIFF, World Wide Web
   Consortium, August, 1997. URL
   http://www.w3.org/TR/NOTE-gdiff-19970901.html.

   16.  Barron C. Housel and David B. Lindquist.  WebExpress: A System
   for Optimizing Web Browsing in a Wireless Environment.  Proc. 2nd
   Annual Intl. Conf. on Mobile Computing and Networking, ACM, Rye, New
   York, November, 1996, pp. 108-116.
   http://www.networking.ibm.com/art/artwewp.htm.
Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 40]

Internet-Draft               Delta encoding       19 February 1999 15:55


   17.  James J. Hunt, Kiem-Phong Vo, and Walter F. Tichy.  An Empirical
   Study of Delta Algorithms.  IEEE Soft. Config. and Maint. Workshop,
   1996.

   18.  Van Jacobson.  Compressing TCP/IP Headers for Low-Speed Serial
   Links.  RFC 1144, Network Working Group, February, 1990.

   19.  David G. Korn and Kiem-Phong Vo.  A Generic Differencing and
   Compression Data Format.  Technical Report ????, AT&T Labs -
   Research, February, 1999.

   20.  David G. Korn and Kiem-Phong Vo.  The VCDIFF Generic
   Differencing and Compression Data Format.  Internet-Draft
   draft-vo-vcdiff-00, IETF, February, 1999. This is a work in progress.

   21.  Merriam-Webster.  Webster's Seventh New Collegiate Dictionary.
   G. & C. Merriam Co., Springfield, MA, 1963.

   22.  Jeffrey C. Mogul.  Hinted caching in the Web.  Proc. Seventh ACM
   SIGOPS European Workshop, Connemara, Ireland, September, 1996, pp.
   103-108. URL http://www-sor.inria.fr/sigops96/papers/mogul.ps.

   23.  Jeffrey C. Mogul, Fred Douglis, Anja Feldmann, and Balachander
   Krishnamurthy.  Potential benefits of delta encoding and data
   compression for HTTP.  Research Report 97/4, DECWRL, July, 1997. URL
   http://www.research.digital.com/wrl/techreports/abstracts/97.4.html.

   24.  Jeffrey C. Mogul and Arthur Van Hoff.  Instance Digests in HTTP.
   Internet-Draft draft-mogul-http-digest-01, IETF, February, 1999. This
   is a work in progress.

   25.  The Open Group.  The Single UNIX Specification, Version 2 - 6
   Vol Set for UNIX 98.  Document number T912, The Open Group, February,
   1997.

   26.  H. Schulzrinne.  Assignment of Status Codes for HTTP and
   HTTP-Derived Protocols.  Internet-Draft
   draft-schulzrinne-http-status-00.txt, IETF, July, 1997. In
   preparation.  This is a work in progress.

   27.  W. Tichy.  "RCS - A System For Version Control".  Software -
   Practice and Experience 15, 7 (July 1985), 637-654.

   28.  Stephen Williams.  Personal communication.
   http://ei.cs.vt.edu/~williams/DIFF/prelim.html.

   29.  Stephen Williams, Marc Abrams, Charles R. Standridge, Ghaleb
   Abdulla, and Edward A. Fox .  Removal Policies in Network Caches for
   World-Wide Web Documents.  Proc. SIGCOMM '96, Stanford, CA, August,
   1996, pp. 293-305.


Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 41]

Internet-Draft               Delta encoding       19 February 1999 15:55


20 Authors' addresses

   Jeffrey C. Mogul
   Western Research Laboratory
   Compaq Computer Corporation
   250 University Avenue
   Palo Alto, California, 94305, U.S.A.
   Email: mogul@pa.dec.com
   Phone: 1 650 617 3304 (email preferred)

   Balachander Krishnamurthy
   AT&T Labs - Research
   180 Park Ave, Room D-229
   Florham Park, NJ 07932-0971, U.S.A.
   Email: bala@research.att.com

   Fred Douglis
   AT&T Labs - Research
   180 Park Ave, Room B-137
   Florham Park, NJ 07932-0971, U.S.A.
   Email: douglis@research.att.com
   Phone: 973-360-8775

   Anja Feldmann
   AT&T Labs - Research
   180 Park Ave, Room B-137
   Florham Park, NJ 07932-0971, U.S.A.
   Email: anja@research.att.com

   Yaron Y. Goland
   Microsoft Corporation
   1 Microsoft Way
   Redmond, WA 98052, U.S.A
   Email: yarong@microsoft.com

   Arthur van Hoff
   Marimba, Inc.
   440 Clyde Avenue
   Mountain View, CA 94043, U.S.A.
   Email: avh@marimba.com
   Phone: 1 (650) 930 5283











Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 42]

Internet-Draft               Delta encoding       19 February 1999 15:55


INDEX

          Open issues: see pages   32

















































Mogul, Krishnamurthy, Douglis, Feldmann, Goland, van Hoff      [Page 43]