doc: Add RFC documents

1 files changed, 2747 insertions, 0 deletions

diff --git a/doc/rfc/rfc3229.txt b/doc/rfc/rfc3229.txt
new file mode 100644
index 0000000..9d53081
--- /dev/null
+++ b/doc/rfc/rfc3229.txt
@@ -0,0 +1,2747 @@
+
+
+
+
+
+
+Network Working Group                                           J. Mogul
+Request for Comments: 3229                                    Compaq WRL
+Category: Standards Track                               B. Krishnamurthy
+                                                              F. Douglis
+                                                                    AT&T
+                                                             A. Feldmann
+                                                   Univ. of Saarbruecken
+                                                               Y. Goland
+                                                             A. van Hoff
+                                                                 Marimba
+                                                          D. Hellerstein
+                                                                ERS/USDA
+                                                            January 2002
+
+
+                         Delta encoding in HTTP
+
+Status of this Memo
+
+   This document specifies an Internet standards track protocol for the
+   Internet community, and requests discussion and suggestions for
+   improvements.  Please refer to the current edition of the "Internet
+   Official Protocol Standards" (STD 1) for the standardization state
+   and status of this protocol.  Distribution of this memo is unlimited.
+
+Copyright Notice
+
+   Copyright (C) The Internet Society (2002).  All Rights Reserved.
+
+Abstract
+
+   This document describes how delta encoding can be supported as a
+   compatible extension to HTTP/1.1.
+
+   Many HTTP (Hypertext Transport Protocol) 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."
+
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                     [Page 1]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+Table of Contents
+
+   1 Introduction....................................................  3
+        1.1 Related research and proposals...........................  4
+   2 Goals...........................................................  5
+   3 Terminology.....................................................  6
+   4 The HTTP message-generation sequence............................  8
+        4.1 Relationship between deltas and ranges................... 11
+   5 Basic mechanisms................................................ 13
+        5.1 Background: an overview of HTTP cache validation......... 13
+        5.2 Requesting the transmission of deltas.................... 14
+        5.3 Choice of delta algorithm and format..................... 16
+        5.4 Identification of delta-encoded responses................ 16
+        5.5 Guaranteeing cache safety................................ 17
+        5.6 Transmission of delta-encoded responses.................. 18
+        5.7 Examples of requests combining Range and delta encoding.. 19
+   6 Encoding algorithms and formats................................. 22
+   7 Management of base instances.................................... 23
+        7.1 Multiple entity tags in the If-None-Match header......... 24
+        7.2 Hints for managing the client cache...................... 25
+   8 Deltas and intermediate caches.................................. 27
+   9 Digests for data integrity...................................... 28
+   10 Specification.................................................. 28
+        10.1 Protocol parameter specifications....................... 28
+        10.2 IANA Considerations..................................... 30
+        10.3 Basic requirements for delta-encoded responses.......... 30
+        10.4 Status code specifications.............................. 30
+             10.4.1 226 IM Used...................................... 31
+        10.5 Header specifications................................... 31
+             10.5.1 Delta-Base....................................... 31
+             10.5.2 IM............................................... 32
+             10.5.3 A-IM............................................. 33
+        10.6 Caching rules for 226 responses......................... 35
+        10.7 Rules for deltas in the presence of content-codings..... 36
+             10.7.1 Rules for generating deltas in the presence of
+                    content-codings.................................. 37
+             10.7.2 Rules for applying deltas in the presence of
+                    content-codings.................................. 37
+             10.7.3 Examples for using A-IM, IM, and content-codings. 38
+        10.8 New Cache-Control directives............................ 40
+             10.8.1 Retain directive................................. 40
+             10.8.2 IM directive..................................... 40
+        10.9 Use of compression with delta encoding.................. 41
+        10.10 Delta encoding and multipart/byteranges................ 42
+   11 Quantifying the protocol overhead.............................. 42
+   12 Security Considerations........................................ 44
+   13 Acknowledgements............................................... 44
+   14 Intellectual Property Rights................................... 44
+
+
+
+Mogul, et al.               Standards Track                     [Page 2]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   15 References..................................................... 44
+   16 Authors' addresses............................................. 47
+   17 Full Copyright Statement....................................... 49
+
+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 a  document, image, icon, or applet) over the Internet or
+   other wide-area networks 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.
+
+
+
+Mogul, et al.               Standards Track                     [Page 3]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   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.
+
+   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 [17] 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
+   [30], but these authors did not elaborate on their design until later
+   [29].
+
+   The WebExpress project [15] 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
+
+
+
+Mogul, et al.               Standards Track                     [Page 4]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   [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 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" [13].  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.
+
+   Tridgell and Mackerras [28] describe the "rsync" algorithm, which
+   accomplishes something similar to delta encoding.  In rsync, the
+   client breaks a cache entry into a series of fixed-sized blocks,
+   computes a digest value for each block, and sends the series of
+   digest values to the server as part of its request.  The origin
+   server does the same block-based computation, and returns only those
+   blocks whose digest values differ.  We believe that it might be
+   possible to support rsync using the "instance manipulation" framework
+   described later in this document, but this has not been worked out in
+   any detail.
+
+2 Goals
+
+   The goals of this proposal are:
+
+      1. Reduce the mean size of HTTP responses, thereby improving
+         latency and network utilization.
+
+
+
+
+Mogul, et al.               Standards Track                     [Page 5]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      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.
+
+      -  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.
+
+
+
+
+Mogul, et al.               Standards Track                     [Page 6]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   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 [12], based on a false analogy between
+   MIME and HTTP.
+
+   In MIME, electronic mail messages do have distinct and separate
+   existences.  MIME defines "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."
+
+   In HTTP, however, a response message to a GET does not have a
+   distinct and separate existence.  Rather, it reflects the current
+   state of a resource (or a variant, subject to a set of constraints).
+   The HTTP/1.1 specification has 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 resource."  This leads to
+   awkward wordings in the HTTP/1.1 specification in places where this
+   concept is necessary.
+
+   To express this concept, we 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, with
+                   the application of zero or more content-codings, but
+                   without the application of any instance manipulations
+                   (see below) or transfer-codings.
+
+   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.
+
+
+
+
+
+
+Mogul, et al.               Standards Track                     [Page 7]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   More formally, delta encodings are members of a potentially larger
+   class of transformations on instances, leading to this new term:
+
+   instance manipulation
+                   An operation on one or more instances which may
+                   result in an instance being conveyed from server to
+                   client in parts, or in more than one response
+                   message.  For example, a range selection or a delta
+                   encoding.  Instance manipulations are end-to-end, and
+                   often involve the use of a cache at the client.
+
+   For reasons that will become clear later on, it is convenient to
+   think about subrange selection as a form of instance manipulation.
+   In some contexts, compression might also be treated as an instance
+   manipulation, rather than as a content-coding or transfer-coding.
+
+4 The HTTP message-generation sequence
+
+   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
+                   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.)
+
+
+
+
+Mogul, et al.               Standards Track                     [Page 8]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   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.
+
+   RFC 2068 [9] 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 [10], analogous to the
+   "Accept-Encoding" header.
+
+   In this document, we add new, optional message headers to support the
+   use of instance manipulations.  A client signals its willingness to
+   receive an instance-manipulation by sending an "A-IM" header (short
+   for "Accept-Instance-Manipulation", which is far too long to spell
+   out), analogous to the "Accept-Encoding" header.  Similarly, a server
+   lists the set of instance-manipulations it has applied using an "IM"
+   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 applied in the
+   following sequence:
+
+      1. Upon receiving a GET request, the server uses the URI in the
+         request to identify the requested resource.
+
+      2. Optionally, it uses information from the request (and perhaps
+         additional information) to select a variant of that resource.
+
+      3. 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.
+
+
+
+
+
+
+Mogul, et al.               Standards Track                     [Page 9]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      4. The result of the first three steps, at the time when the
+         request is processed, is an instance.  The instance includes a
+         body (possibly empty) and possibly some instance headers.  The
+         entity tag, if any, is assigned at this point.  That is, an
+         entity tag is associated with an instance, NOT an entity.
+
+      5. The server may then apply an instance-manipulation.  For
+         example, 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 the appropriate
+         range(s) from the (possibly encoded) body.  Delta encodings are
+         instance-manipulations, and are computed at this stage.
+
+      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 could 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-coded version of the entity body),
+         the entity headers, and additional response and general
+         headers.
+
+      Note: Section 14.13 of the HTTP/1.1 specification [10] says "The
+      Content-Length entity-header field indicates the size of the
+      entity-body."  In other words, Content-Length measures the length
+      of an entity, not of an instance or of a variant.  For example, if
+      the message is a delta encoding, Content-Length gives the length
+      of the delta encoding, not the length of the current instance.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 10]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   Diagrammatically, the sequence is:
+
+       datatype        operation leading to next datatype
+       ========        ==================================
+       resource
+                   |   choose acceptable variant, if needed
+                   v
+       variant
+                   |   apply content-coding, if any
+                   v
+
+                   |   compute/assign entity tag
+                   v
+       instance
+                   |   apply instance manipulation, if any
+                   v      (delta encoding, range selection, etc.)
+       entity-body
+                   |   apply transfer-coding, if any
+                   v
+       message-body
+
+   This formalization of the HTTP message generation sequence has not
+   previously been described.  However, it is clear that Range selection
+   needs to be done after the entity tag has been assigned and after any
+   content-coding has been applied, and before any transfer-coding is
+   applied.  Therefore, this formalization is fully consistent with
+   previous practice and specification.
+
+4.1 Relationship between deltas and ranges
+
+   If both Ranges and delta encodings are forms of instance
+   manipulation, which should be applied first?  This depends on how the
+   Range is being used.
+
+   Ranges are used for two main purposes, at the discretion of the
+   requesting client:
+
+      1. to complete a partial response after a premature termination of
+         a message transmission.
+
+      2. to obtain just selected sections of an instance.
+
+   In the first use of Range, it would have to be applied after any
+   delta encoding, since the intended use is to recover an intact copy
+   of the delta-encoded instance.  In the second use of Range, it would
+   have to be applied before any delta encoding, because otherwise the
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 11]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   offsets specified in the Range request would be meaningless (the
+   client generally cannot know how a server's delta encoding maps
+   instance byte offsets to entity byte offsets).
+
+   Therefore, we need a mechanism to allow the client to specify the
+   order in which two or more instance-manipulations should be applied.
+   This is easily provided as part of the specification of the "A-IM"
+   header (see section 10.5.3), where we require that the server apply
+   instance-manipulations in the order that they are listed in the "A-
+   IM" header.  We also include a "range" literal in the set of
+   registered instance-manipulations, to allow the client to specify (by
+   its ordering with respect to other instance-manipulations) whether
+   range selection is done before or after delta encoding.
+
+   We also need a mechanism for the server to indicate in which order
+   two or more instance-manipulations have been applied; this is part of
+   the specification of the "IM" header (see section 10.5.2), where we
+   follow the same practice used for the "Content-Encoding" header:  the
+   "IM" header lists the instance-manipulations in the order that were
+   applied (including, perhaps, the special "range" literal).
+
+   A similar issue arises when Ranges are combined with compression.  If
+   the client is using a Range to complete a partial response after a
+   premature termination of a compressed message, then the Range would
+   have to be applied after the compression.  This is feasible in
+   unmodified HTTP/1.1, because the compression can be done as a
+   content-coding.  However, if the client is using a Range to obtain
+   selected sections of an instance, it would normally be able to
+   specify offsets only in terms of the uncompressed variant.  If the
+   selected portion was large enough to warrant compression, the client
+   could request a compressed transfer-coding, but this is a hop-by-hop
+   transformation and is not the most efficient approach (especially if
+   an HTTP/1.0 proxy is in the path).
+
+   We can resolve this issue by supporting the use of compression as an
+   instance-manipulation (as well as as a content-coding or transfer-
+   coding), and by using the new mechanism that allows the client to
+   specify that the compression instance-manipulation is done after the
+   Range instance-manipulation.
+
+   This also allows the client to control whether compression is done
+   before or after delta encoding, since some simple differencing
+   algorithms (such as the UNIX "diff" command) require post-compression
+   of their output to yield the best results.
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 12]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+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 10 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."  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.
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 13]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      -  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.
+
+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; specifically, the "A-IM" header.
+   The presence of this list in a conditional request indicates that the
+   client is able to apply delta-encoded cache updates.
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 14]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   For example, a client might send this request:
+
+      GET /foo.html HTTP/1.1
+      Host: bar.example.net
+      If-None-Match: "123xyz"
+      A-IM: vcdiff, diffe, gzip
+
+   The meaning of this request is that:
+
+      -  The client wants to obtain the current value of /foo.html.
+
+      -  It already has a cached response (instance) for that resource,
+         whose entity tag is "123xyz".
+
+      -  It is willing to accept delta-encoded updates using either of
+         two formats, "diffe" (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.  (It
+         might be useful to compress the output of "diff -e".)  However,
+         based on the mandatory ordering constraint specified in section
+         10.5.3, if both delta encoding and compression are applied,
+         then this "A-IM" 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 instance-manipulation,
+   the server will simply ignore this aspect of the request.  (HTTP
+   always allows an implementation to ignore a header that is not
+   required by a specification that the implementation complies with,
+   and the specification of "A-IM" allows the server to ignore an
+   instance-manipulation it does not understand.)  So if a server either
+   does not implement the A-IM header at all, or does not implement any
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 15]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   of the instance manipulations listed in the A-IM header, it acts as
+   if the client had not requested a delta-encoded response: the server
+   generates a status-200 response.
+
+5.3 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 it 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 "A-IM"
+   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.)
+
+   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.4 Identification of delta-encoded responses
+
+   A response using delta encoding must be identified as such.  This is
+   done using the "IM" response-header, specified in section 10.5.2.
+
+   However, a simplistic application of this approach would cause
+   serious problems if a delta-encoded response flows through an
+   intermediate (proxy) cache that is not cognizant of the delta
+
+
+
+Mogul, et al.               Standards Track                    [Page 16]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   mechanism.  Because the Internet still includes a significant number
+   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.
+
+   To solve this problem, we propose that delta-encoded responses
+   (actually, all instance-manipulated 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 "IM Used".  (We see no benefit in spelling out the
+   words "Instance Manipulation Used," since this requires the
+   transmission of unnecessary bytes, and this Reason-phrase should not
+   normally be seen by human users.)  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 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.
+
+      We were reluctant to define an additional status code as part of
+      the support for delta encoding.  However, we see no other
+      efficient way to remain compatible with the deployed base of
+      HTTP/1.0 cache implementations.
+
+5.5 Guaranteeing cache safety
+
+   Although we are not aware of any HTTP/1.1 proxy implementations that
+   would attempt to cache a response with an unknown 2xx status code,
+   the HTTP/1.1 specification does allow this behavior if the response
+   carries an Expires or Cache-Control header field that explicitly
+   allows caching.  This would present a problem when a 226 (IM Used)
+   response carries such headers.
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 17]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   The solution in that case is to exploit the Cache Control Extensions
+   mechanism from the HTTP/1.1 specification.  We define a new cache-
+   directive, "im", which indicates that the "no-store" cache-directive
+   may be ignored by implementations that conform to the specification
+   for the IM and A-IM headers.
+
+   For example, this response:
+
+      HTTP/1.1 226 IM Used
+      ETag: "489uhw"
+      IM: vcdiff
+      Date: Tue, 25 Nov 1997 18:30:05 GMT
+      Cache-Control: no-store, im, max-age=30
+
+      ...
+
+   "MUST NOT" be stored by a cache that complies with the HTTP/1.1
+   specification (which states that the max-age cache-directive "implies
+   that the response is cacheable [...] unless some other, more
+   restrictive cache directive is also present.").  However, a cache
+   that does comply with the specification for the im cache-directive
+   (i.e., a cache that complies with the specification for the A-IM and
+   IM header fields, and the 226 status code) ignores the no-store
+   directive, and therefore sees the max-age directive as allowing
+   caching.
+
+      We are not entirely sure that all HTTP/1.1 caches obey the rule
+      that the max-age directive is overridden by the no-store
+      directive.  If operational testing reveals this to be a problem,
+      more elaborate solutions are possible.
+
+   Warning to origin server implementors: it does not suffice to send
+
+      Vary: If-None-Match, A-IM
+
+   in status-226 responses.  We have discovered at least one scenario
+   where this does not prevent a proxy cache that does not implement IM
+   and A-IM from incorrectly "validating" a cached 226 response.
+
+5.6 Transmission of delta-encoded responses
+
+   A delta-encoded response differs from a standard response in four
+   ways:
+
+      1. It carries a status code of 226 (IM Used).
+
+      2. It carries an "IM" response-header field, indicating which
+         delta encoding is used in this response.
+
+
+
+Mogul, et al.               Standards Track                    [Page 18]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      3. Its message-body is a delta encoding of the current instance,
+         rather than a full copy of the instance.
+
+      4. It might carry several other new headers, as described later in
+         this document.
+
+   For example, a response to the request given in section 5.2 might
+   look like:
+
+      HTTP/1.1 226 IM Used
+      ETag: "489uhw"
+      IM: 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.)
+
+      Note: the Etag header in a 226 response with a delta encoding
+      provides the entity tag of the current instance of the resource
+      variant.  It is not meaningful to associate an entity tag with the
+      delta value, which is not an instance.
+
+5.7 Examples of requests combining Range and delta encoding
+
+   In the example used in section 5.2, the client sends:
+
+      GET /foo.html HTTP/1.1
+      Host: bar.example.net
+      If-None-Match: "123xyz"
+      A-IM: vcdiff, diffe, 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
+      Host: bar.example.net
+      If-None-Match: "123xyz"
+      A-IM: vcdiff, diffe, gzip, range
+      Range: bytes=0-99
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 19]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   then the meaning is the same as in the example above, except that
+   after the delta encoding (and compression, if any) is computed, 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.)  Because the "range" token appears last in the
+   "A-IM" header, this tells the origin server to apply any range
+   selection after the other instance-manipulations.
+
+   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:
+
+      GET /foo.html HTTP/1.1
+      host: bar.example.net
+      If-None-Match: "A"
+      A-IM: vcdiff
+
+   Suppose that the server's current instance has entity tag "B", and
+   that the server also has retained a copy of the instance with entity
+   tag "A".  Then, the server could compute the difference between "B"
+   and "A", and respond with:
+
+      HTTP/1.1 226 IM Used
+      Etag: "B"
+      IM: 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:
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 20]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      GET /foo.html HTTP/1.1
+      host: bar.example.net
+      If-None-Match: "A"
+      If-Range: "B"
+      A-IM: vcdiff,range
+      Range: bytes=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
+                   should 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 the vcdiff instance manipulation (if
+                   both are to be applied).  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 selection, and returns
+                   a 226 (IM Used) response, with an message-body
+                   containing bytes 900 to 999 of the result of the
+                   vcdiff encoding, with an "IM:vcdiff,range" response
+                   header.
+
+   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 instance.  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 (IM Used) response, with an "IM:vcdiff" response
+                   header.
+
+   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
+
+
+
+Mogul, et al.               Standards Track                    [Page 21]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   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.
+
+   On the other hand, suppose that the client has a cache entry for the
+   "A" instance of http://bar.example.net/foo.html, and it has already
+   received the first 900 bytes of a new instance "B" (perhaps as the
+   result of an aborted transfer).  Now the client wants to receive the
+   entire current instance, so it could send this request:
+
+      GET /foo.html HTTP/1.1
+      host: bar.example.net
+      If-None-Match: "A"
+      If-Range: "B"
+      A-IM: range,vcdiff
+      Range: bytes=900-
+
+   In this example, as in the previous example, if Tcur = "A" then the
+   server should send 304 (Not Modified), and if Tcur = "C", then the
+   server should send the entire new instance, either as a 200 response
+   or as a delta encoding against instance "A".
+
+   However, if Tcur = "B", in this case the server should first select
+   the specified range (bytes 900 through the end) from both instances
+   "A" and "B", then compute the delta encoding between these ranges
+   (using vcdiff), and then transmit the result using a 226 (IM Used)
+   response with an "IM:range,vcdiff" response header.
+
+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.
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 22]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   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 two different instance-
+                   manipulation values would have to be registered in
+                   order to distinguish these two uses, should its use
+                   as a compressed format be adopted.)  The most recent
+                   published study suggests that "vdelta" is the best
+                   overall delta algorithm [16].
+
+   gdiff           The gdiff format [14] 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 "A-IM" 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.
+
+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."
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 23]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   There are many possible options for server implementors.  For
+   example:
+
+      -  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 a Least Recently Used (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
+
+
+
+Mogul, et al.               Standards Track                    [Page 24]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   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:
+
+      GET /foo.html HTTP/1.1
+      host: bar.example.net
+      If-None-Match: "123xyz", "337pey", "489uhw"
+      A-IM: 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 IM Used
+      ETag: "1acl059"
+      IM: 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 [4, 22].
+
+
+
+Mogul, et al.               Standards Track                    [Page 25]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   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.
+
+   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,
+   referring to the current instance:
+
+      HTTP/1.1 226 IM Used
+      ETag: "1acl059"
+      Date: Tue, 25 Nov 1997 18:30:05 GMT
+      Cache-Control: retain
+      IM: 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
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 26]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   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.
+
+8 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.
+
+   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 "IM" response-header field (one that includes the
+         actual delta-encoding format 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
+
+
+
+Mogul, et al.               Standards Track                    [Page 27]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+         resulting delta response to one of its own cache entries) it
+         would return a full-body response to the client (or a response
+         with status code 206 or 304, as appropriate).
+
+   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.
+
+9 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.
+
+   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
+   not the headers).  The Digest Authentication mechanism [11] 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.
+
+10 Specification
+
+   In this specification, the key words "MUST", "MUST NOT", "SHOULD",
+   "SHOULD NOT", and "MAY" are to be interpreted as described in RFC
+   2119 [3].
+
+10.1 Protocol parameter specifications
+
+   This specification defines a new HTTP parameter type, an instance-
+   manipulation:
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 28]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      instance-manipulation = token [imparams]
+
+      imparams = ";" imparam-name [ "=" ( token | quoted-string ) ]
+      imparam-name = token
+
+   Note that the imparam-name MUST NOT be "q", to avoid ambiguity with
+   the use of qvalues (see [10]).
+
+   The set of instance-manipulation values is initially:
+
+      -  vcdiff
+         A delta using the "vcdiff" encoding format [19, 20].
+
+      -  diffe
+         The output of the UNIX "diff -e" command [26].
+
+      -  gdiff
+         The GDIFF encoding format [14].
+
+      -  gzip
+         Same definition as the HTTP "gzip" content-coding.
+
+      -  deflate
+         Same definition as the HTTP "deflate" content-coding.
+
+      -  range
+         A token indicating that the result is partial content, as the
+         result of a range selection.
+
+      -  identity
+         A token used only in the A-IM header (not in the IM header), to
+         indicate whether or not the identity instance-manipulation is
+         acceptable.
+
+   For convenience in the rest of this specification, we define a subset
+   of instance-manipulation values as delta-coding values:
+
+      delta-coding = "vcdiff" | "diffe" | "gdiff" | token
+
+   Future instance-manipulation values might also be included in this
+   list.
+
+
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 29]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+10.2 IANA Considerations
+
+   The Internet Assigned Numbers Authority (IANA) administers the name
+   space for instance-manipulation values.  Values and their meaning
+   must be documented in an RFC or other peer-reviewed, permanent, and
+   readily available reference, in sufficient detail so that
+   interoperability between independent implementations is possible.
+   Subject to these constraints, name assignments are First Come, First
+   Served (see RFC 2434 [25]).
+
+   This specification also inserts a new value in the IANA HTTP Status
+   Code Registry (see RFC 2817 [18]).  See section 10.4.1 for the
+   specification of this code.
+
+10.3 Basic requirements for delta-encoded responses
+
+   A server MAY send a delta-encoded response if all of these conditions
+   are true:
+
+      1. The server would be able to send a 200 (OK) response for the
+         request.
+
+      2. The client's request includes an A-IM header field listing at
+         least one delta-coding.
+
+      3. The client's request includes an If-None-Match header field
+         listing at least one valid entity tag for an instance of the
+         Request-URI (a "base instance").
+
+   A delta-encoded response:
+
+      -  MUST carry a status code of 226 (IM Used).
+
+      -  MUST include an IM header field listing, at least, the delta-
+         coding employed.
+
+      -  MAY include a Delta-Base header field listing the entity tag of
+         the base-instance.
+
+10.4 Status code specifications
+
+   The following new status code is defined for HTTP.
+
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 30]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+10.4.1 226 IM Used
+
+   The server has fulfilled a GET request for the resource, and the
+   response is a representation of the result of one or more instance-
+   manipulations applied to the current instance.  The actual current
+   instance might not be available except by combining this response
+   with other previous or future responses, as appropriate for the
+   specific instance-manipulation(s).  If so, the headers of the
+   resulting instance are the result of combining the headers from the
+   status-226 response and the other instances, following the rules in
+   section 13.5.3 of the HTTP/1.1 specification [10].
+
+   The request MUST have included an A-IM header field listing at least
+   one instance-manipulation.  The response MUST include an Etag header
+   field giving the entity tag of the current 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, and to the
+   requirements in section 10.6.
+
+   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.
+
+10.5 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.)
+
+10.5.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.
+
+      Delta-Base = "Delta-Base" ":" entity-tag
+
+   A Delta-Base header field MUST be included in a response with an IM
+   header that includes a delta-coding, if the request included more
+   than one entity tag in its If-None-Match header field.
+
+   Any response with an IM header that includes a delta-coding MAY
+   include a Delta-Base header.
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 31]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      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 delta-encoded response.
+
+   A cache or proxy that receives a delta-encoded response that lacks a
+   Delta-base header MAY add a Delta-Base header whose value is the
+   entity tag given in the If-None-Match field of the request (but only
+   if that field lists exactly one entity tag).
+
+10.5.2 IM
+
+   The IM response-header field is used to indicate the instance-
+   manipulations, if any, that have been applied to the instance
+   represented by the response.  Typical instance manipulations include
+   delta encoding and compression.
+
+      IM = "IM" ":" #(instance-manipulation)
+
+   Instance-manipulations are defined in section 10.1.
+
+   As a special case, if the instance-manipulations include both range
+   selection and at least one other non-identity instance-manipulation,
+   the IM header field MUST be used to indicate the order in which all
+   of these instance-manipulations, including range selection, were
+   applied.  If the IM header lists the "range" instance-manipulation,
+   the response MUST include either a Content-Range header or a
+   multipart/byteranges Content-Type in which each part contains a
+   Content-Range header.  (See section 10.10 for specific discussion of
+   combining delta encoding and multipart/byteranges.)
+
+   Responses that include an IM header MUST carry a response status code
+   of 226 (IM Used), as specified in section 10.4.1.
+
+   The server SHOULD omit the IM header if it would list only the
+   "range" instance-manipulation.  Such responses would normally be sent
+   with response status code 206 (Partial Content), as specified by
+   HTTP/1.1 [10].
+
+   Examples of the use of the IM header include:
+
+      IM: vcdiff
+
+   This example indicates that the entity-body is a delta encoding of
+   the instance, using the vcdiff encoding.
+
+      IM: diffe, deflate, range
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 32]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   This example indicates that the instance has first been delta-encoded
+   using the diffe encoding, then the result of that has been compressed
+   using deflate, and finally one or more ranges of that compressed
+   encoding have been selected.
+
+      IM: range, vcdiff
+
+   This example indicates that one or more ranges of the instance have
+   been selected, and the result has then been delta encoded against
+   identical ranges of a previous base instance.
+
+   A cache using a response received in reply to one request to reply to
+   a subsequent request MUST follow the rules in section 10.6 if the
+   cached response includes an IM header field.
+
+10.5.3 A-IM
+
+   The A-IM request-header field is similar to Accept, but restricts the
+   instance-manipulations (section 10.1) that are acceptable in the
+   response.  As specified in section 10.5.2, a response may be the
+   result of applying multiple instance-manipulations.
+
+      A-IM = "A-IM" ":" #( instance-manipulation
+                               [ ";" "q" "=" qvalue ] )
+
+   When an A-IM request-header field includes one or more delta-coding
+   values, the request MUST contain an If-None-Match header field,
+   listing one or more entity tags from prior responses for the
+   request-URI.
+
+   A server tests whether an instance-manipulation (among the ones it is
+   capable of employing) is acceptable, according to a given A-IM header
+   field, using these rules:
+
+      1. If the instance-manipulation is listed in the A-IM field, then
+         it is acceptable, unless it is accompanied by a qvalue of 0.
+         (As defined in section 3.9 of the HTTP/1.1 specification [10],
+         a qvalue of 0 means "not acceptable.")  A server MUST NOT use a
+         non-identity instance-manipulation for a response unless the
+         instance-manipulation is listed in an A-IM header in the
+         request.
+
+      2. If multiple but incompatible instance-manipulations are
+         acceptable, then the acceptable instance-manipulation with the
+         highest non-zero qvalue is preferred.
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 33]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      3. The "identity" instance-manipulation is always acceptable,
+         unless specifically refused because the A-IM field includes
+         "identity;q=0".
+
+   If an A-IM field is present in a request, and if the server cannot
+   send a response which is acceptable according to the A-IM header,
+   then the server SHOULD send an error response with the 406 (Not
+   Acceptable) status code.
+
+   If a response uses more than one instance-manipulation, the
+   instance-manipulations MUST be applied in the order in which they
+   appear in the A-IM request-header field.
+
+   The server's choice about whether to apply an instance-manipulation
+   SHOULD be independent of its choice to apply any subsequent two-input
+   instance-manipulations to the response.  (Two-input instance-
+   manipulations include delta-codings, because they take two different
+   values as input.  Compression and "range" instance-manipulations take
+   only one input.  Other instance-manipulations may be defined in the
+   future.)
+
+      Note: the intent of this requirement is to prevent the server from
+      generating a delta-encoded response that the client can only
+      decode by first applying an instance-manipulation encoding to its
+      cached base instance.  A server implementor might wish to consider
+      what the client would logically have in its cache, when deciding
+      which instance-manipulations to apply prior to a delta-coding.
+
+   Examples:
+
+      A-IM: vcdiff, gdiff
+
+   This example means that the client will accept a delta encoding in
+   either vcdiff or gdiff format.
+
+      A-IM: vcdiff, gdiff;q=0.3
+
+   This example means that the client will accept a delta encoding in
+   either vcdiff or gdiff format, but prefers the vcdiff format.
+
+      A-IM: vcdiff, diffe, gzip
+
+   This example means that the client will accept a delta encoding in
+   either vcdiff or diffe format, and will accept the output of the
+   delta encoding compressed with gzip.  It also means that the client
+   will accept a gzip compression of the instance, without any delta
+   encoding, because A-IM provides no way to insist that gzip be used
+   only if diffe is used.
+
+
+
+Mogul, et al.               Standards Track                    [Page 34]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   It is left to the server implementor to choose useful combinations of
+   acceptable instance-manipulations (for example, following diffe by
+   gzip is useful, but following vcdiff by gzip probably is not useful).
+
+10.6 Caching rules for 226 responses
+
+   When a client or proxy receives a 226 (IM Used) response, it MAY use
+   this response to create a cache entry in three ways:
+
+      1. It MAY decode all of the instance-manipulations to recover the
+         original instance, and store that instance in the cache.  In
+         this case, the recovered instance is stored as a status-200
+         response, and MUST be used in accordance with the normal HTTP
+         caching rules.
+
+      2. It MAY decode all of the instance-manipulations except for
+         range selection(s), and store the result in the cache.  In this
+         case, the result is stored as a status-206 response, and MUST
+         be used in accordance with the normal HTTP caching rules for
+         Partial Content.
+
+      3. It MAY store the status-226 (IM Used) response as a cache
+         entry.
+
+   A status-226 cache entry MUST NOT be used in response to a subsequent
+   request under any of these conditions (a cache that never stores
+   status-226 responses may ignore these tests):
+
+      1. If any of the instance-manipulation values from the IM header
+         field in the cached response do not appear in the subsequent
+         request's A-IM header field.  The comparison between the
+         headers is done using an exact match on each instance-
+         manipulation value including any associated imparams values
+         (see section 10.1).
+
+      2. If the order of instance-manipulation values appearing in the
+         cached IM header field differs from the order of that set of
+         instance-manipulations in the A-IM header field of the
+         subsequent request.
+
+      3. If the cache implementation is not aware of, or is not at least
+         conditionally compliant with, the specification of any of the
+         instance-manipulation values in the cached IM header field.
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 35]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+         Note: This rule allows for extending the set of instance-
+         manipulations without causing deployed cache implementations to
+         commit errors.  The specification of new instance-manipulations
+         may include additional caching rules to improve cache-hit rates
+         in cognizant implementations.
+
+      4. If any of the instance-manipulation values in the cached IM
+         header field is a delta-coding, and the cache entry includes a
+         Delta-Base header field, and that Delta-Base entity tag is not
+         one of the entity tags listed in an If-None-Match header field
+         of the subsequent request.
+
+      5. If any of the instance-manipulation values in the cached IM
+         header field is a delta-coding, the cache entry does not
+         include a Delta-Base header field, and the If-None-Match header
+         field of the request that led to that cache entry does not
+         match the If-None-Match header field of the subsequent request.
+
+   If the IM header field of the cached response includes the "range"
+   instance-manipulation, then a status-226 cache entry MUST NOT be used
+   in response to a subsequent request if the cached response is
+   inconsistent with the Range header field value(s) in the request, as
+   would be the case for a cached 206 (Partial Content) response.
+
+      Note: we know of no existing, published formal specification for
+      deciding if a cached status-206 response is consistent with a
+      subsequent request.  We believe that either of these conditions is
+      sufficient:
+
+         1. The ranges specified in the headers of the request that led
+            to the cached response are the same as specified in the
+            headers of the subsequent request.
+
+         2. The ranges specified in the cached response are the same as
+            specified in the headers of the subsequent request.
+
+      Further analysis might be necessary.
+
+10.7 Rules for deltas in the presence of content-codings
+
+   The use of delta encoding with content-encoded instances adds some
+   slight complexity.  When a client (perhaps a proxy) has received a
+   delta encoded response, either or both of that new response and a
+   cached previous response may have non-identity content-codings.  We
+   specify rules for the server and client, to prevent situations where
+   the client is unable to make sense of the server's response.
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 36]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+10.7.1 Rules for generating deltas in the presence of content-codings
+
+   When a server generates a delta-encoded response, the list of
+   content-codings the server uses (i.e., the value of the response's
+   Content-Encoding header field) SHOULD be a prefix of the list of
+   content-codings the server would have used had it not generated a
+   delta encoding.
+
+   This requirement allows a client receiving a delta-encoded response
+   to apply the delta to a cached base instance without having to apply
+   any content-codings during the process (although the client might, of
+   course, be required to decode some content-codings).
+
+10.7.2 Rules for applying deltas in the presence of content-codings
+
+   When a client receives a delta response with one or more non-identity
+   content codings:
+
+      1. If both the new (delta) response and the cached response
+         (instance) have exactly the same set of content-codings, the
+         client applies the delta response to the cached response
+         without removing the content-codings from either response.
+
+      2. If the new (delta) response and the cached response have a
+         different set of content-codings, before applying the delta the
+         client decodes one or more content-codings from the cached
+         response, until the result has the same set of content-codings
+         as the delta response.
+
+      3. If a proxy or cache is forwarding the result of applying the
+         delta response to a cached base instance response, or later
+         forwards this result from a cache entry, the forwarded response
+         MUST carry the same Content-Encoding header field as the new
+         (delta) response (and so it must be content-encoded as
+         indicated by that header field).
+
+   The intent of these rules (and in particular, rule #3) is that the
+   results are always consistent with the rule that the entity tag is
+   associated with the result of the content-coding, and that any
+   recipient after the application of the delta-coding receives exactly
+   the same response it would have received as a status-200 response
+   from the origin server (without any delta-coding).
+
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 37]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+10.7.3 Examples for using A-IM, IM, and content-codings
+
+   Suppose a client, with an empty cache, sends this request:
+
+      GET /foo.html HTTP/1.1
+      Host: example.com
+      Accept-encoding: gzip
+
+   and the origin server responds with:
+
+      HTTP/1.1 200 OK
+      Date: Wed, 24 Dec 1997 14:00:00 GMT
+      Etag: "abc"
+      Content-encoding: gzip
+
+   We will use the notation URI;entity-tag to denote specific instances,
+   so this response would cause the client to store in its cache the
+   entity GZIP(foo.html;"abc").
+
+   Then suppose that the client, a minute later, issues this conditional
+   request:
+
+      GET /foo.html HTTP/1.1
+      Host: example.com
+      If-none-match: "abc"
+      Accept-encoding: gzip
+      A-IM: vcdiff
+
+   If the server is able to generate a delta-encoded response, it might
+   choose one of two alternatives.  The first is to compute the delta
+   from the compressed instances (although this might not yield the most
+   efficient coding):
+
+      HTTP/1.1 226 IM Used
+      Date: Wed, 24 Dec 1997 14:01:00 GMT
+      Etag: "def"
+      Delta-base: "abc"
+      Content-encoding: gzip
+      IM: vcdiff
+
+   The body of this response would be the result of
+   VCDIFF_DELTA(GZIP(foo.html;"abc"), GZIP(foo.html;"def")).  The client
+   would store as a new cache entry the entity GZIP(foo.html;"def"),
+   after recovering that entity by applying the delta to its previous
+   cache entry.
+
+   The server's other alternative would be to compute the delta from the
+   uncompressed values, returning:
+
+
+
+Mogul, et al.               Standards Track                    [Page 38]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      HTTP/1.1 226 IM Used
+      Date: Wed, 24 Dec 1997 14:01:00 GMT
+      Delta-base: "abc"
+      Etag: "ghi"
+      IM: vcdiff
+
+   The body of this response would be the result of
+   VCDIFF_DELTA(GUNZIP(GZIP(foo.html;"abc")), foo.html;"ghi"), or more
+   simply VCDIFF_DELTA(foo.html;"abc", foo.html;"ghi").  The client
+   would store as a new cache entry the entity foo.html;"ghi" (i.e.,
+   without any content-coding), after recovering that entity by applying
+   the delta to its previous cache entry.
+
+   Note that the new value of foo.html (at 14:01:00 GMT) without the
+   gzip content-coding must have a different entity tag from the
+   compressed instance of the same underlying file.
+
+   The client's second request might have been:
+
+       GET /foo.html HTTP/1.1
+       Host: example.com
+       If-none-match: "abc"
+       Accept-encoding: gzip
+       A-IM: diffe, gzip
+
+   The client lists gzip in both the Accept-Encoding and A-IM headers,
+   because if the server does not support delta encoding, the client
+   would at least like to achieve the benefits of compression (as a
+   content-coding).  However, if the server does support the diffe
+   delta-coding, the client would like the result to be compressed, and
+   this must be done as an instance-manipulation.
+
+   A server that does support diffe might reply:
+
+      HTTP/1.1 226 IM Used
+      Date: Wed, 24 Dec 1997 14:01:00 GMT
+      Delta-base: "abc"
+      Etag: "ghi"
+      IM: diffe, gzip
+
+   The body of this response would be the result of
+   GZIP(DIFFE_DELTA(GUNZIP(GZIP(foo.html;"abc")), foo.html;"ghi")), or
+   more simply GZIP(DIFFE_DELTA(foo.html;"abc", foo.html;"ghi")).
+   Because the gzip compression is, in this case, an instance-
+   manipulation and not a content-coding, it is not retained when the
+   reassembled response is stored or forwarded, so the client would
+   store as a new cache entry the entity foo.html;"ghi" (without any
+   content-coding or compression).
+
+
+
+Mogul, et al.               Standards Track                    [Page 39]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+10.8 New Cache-Control directives
+
+   We define two new cache-directives (see section 14.9 of RFC 2616 [10]
+   for the specification of cache-directive).
+
+10.8.1 Retain directive
+
+   The set of cache-response-directive values is augmented to include
+   the retain directive.
+
+      cache-response-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.
+
+      Note: We recommend that server implementors consider the bandwidth
+      implications of sending the "retain=0" directive to clients or
+      proxies that might not have the ability to make use of it.
+
+10.8.2 IM directive
+
+   The set of cache-response-directive values is augmented to include
+   the im directive.
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 40]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+      cache-response-directive = ...
+              | "im"
+
+   A cache that complies with the specification for the IM header, the
+   A-IM header, and the 226 response-status code SHOULD ignore a no-
+   store cache-directive if an im directive is present in the same
+   response.  All other implementations MUST ignore the im directive
+   (i.e., MUST observe a no-store directive, if present).
+
+10.9 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.
+
+   A client that supports both delta encoding and compression as
+   instance-manipulations signals this by, for example
+
+      A-IM: diffe, deflate
+
+   The ordering rule stated in section 10.5.3 requires, if the server
+   uses both instance-manipulations in the response, that compression be
+   applied to the result of the delta encoding, rather than vice versa.
+   I.e., the response in this case would include
+
+      IM: diffe, deflate
+
+   Note that a client might accept compression either as a content-
+   coding or as an instance-manipulation.  For example:
+
+      Accept-Encoding: gzip
+      A-IM: gzip, gdiff
+
+   In this example, the server may apply the gzip compression, either as
+   a content-coding or as an instance-manipulation, before delta
+   encoding.  Remember that the entity tag is assigned after content-
+   coding but before instance-manipulation, so this choice does affect
+   the semantics of delta encoding.
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 41]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+10.10 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 [10]) to convey multiple ranges in a response.
+   If a multipart/byteranges response is delta encoded (i.e, uses a
+   delta-coding as an instance-manipulation), 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-coding for all of the ranges.
+
+   If a server chooses to use a delta encoding for a
+   multipart/byteranges response, it MUST generate a response in
+   accordance with the following rules.
+
+   When a multipart/byteranges response uses a delta-coding prior to a
+   range selection, the A-IM and IM header fields list the delta-coding
+   before the "range" literal.  (Recall that this is the approach taken
+   to obtain a partial response after a premature termination of a
+   message transmission.)  The server firsts generates a sequence of
+   bytes representing the difference (delta) between the base instance
+   and the current instance, 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-coding after a
+   range selection, the A-IM and IM header fields list the delta-coding
+   after the "range" literal.  (Recall that this is the approach taken
+   to obtain an updated version just of selected sections of an
+   instance.)  The server first selects the specified ranges from the
+   current instance, and also selects the same specified ranges from the
+   base instance.  (Some of these selected 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.
+
+11 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.:
+
+      A-IM:vcdiff
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 42]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   This is about 13 extra bytes.  A recent study [23] reports mean
+   request sizes from two different traces of 281 and 306 bytes, so the
+   net increase in request size would be between 4% and 5%.
+
+   Because a client must have an existing cache entry to use as a base
+   for a delta-encoded response, it would never send "A-IM: 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 5%, and probably below
+   1%.
+
+   Delta-encoded responses carry slightly longer headers.  In the
+   simplest case, a response carries one more header, e.g.:
+
+      IM:vcdiff
+
+   This is about 11 bytes.  Other headers (such as "Delta-Base") 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 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, et al.               Standards Track                    [Page 43]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+12 Security Considerations
+
+   We are not aware of any aspects of the basic delta encoding mechanism
+   that affect the existing security considerations for the HTTP/1.1
+   protocol.
+
+13 Acknowledgements
+
+   Phong Vo has provided a great deal of guidance in the choice of delta
+   encoding algorithms and formats.  Issac Goldstand and Mike Dahlin
+   provided a number of useful comments on the specification.  Dave
+   Kristol suggested many textual corrections.
+
+14 Intellectual Property Rights
+
+   The IETF has been notified of intellectual property rights claimed in
+   regard to some or all of the specification contained in this
+   document.  For more information consult the online list of claimed
+   rights, at <http://www.ietf.org/ipr.html>.
+
+   The IETF takes no position regarding the validity or scope of any
+   intellectual property or other rights that might be claimed to
+   pertain to the implementation or use of the technology described in
+   this document or the extent to which any license under such rights
+   might or might not be available; neither does it represent that it
+   has made any effort to identify any such rights.  Information on the
+   IETF's procedures with respect to rights in standards-track and
+   standards-related documentation can be found in BCP 11.  Copies of
+   claims of rights made available for publication and any assurances of
+   licenses to be made available, or the result of an attempt made to
+   obtain a general license or permission for the use of such
+   proprietary rights by implementors or users of this specification can
+   be obtained from the IETF Secretariat.
+
+15 References
+
+   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.  Berners-Lee, T., Fielding, R. and H. Frystyk, "Hypertext Transfer
+       Protocol -- HTTP/1.0", RFC 1945, May 1996.
+
+   3.  Bradner, S., "Key words for use in RFCs to Indicate Requirement
+       Levels", BCP 14, RFC 2119, March 1997.
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 44]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   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.
+
+   5.  Deutsch, P., "GZIP file format specification version 4.3", RFC
+       1952, May 1996.
+
+   6.  Deutsch, P., "DEFLATE Compressed Data Format Specification
+       version 1.3", RFC 1951, May 1996.
+
+   7.  Deutsch, P. and J-L. Gailly, "ZLIB Compressed Data Format
+       Specification version 3.3", RFC 1950, 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.  Fielding, R., Gettys, J., Mogul, J., Nielsen, H. and T. Berners-
+       Lee, "Hypertext Transfer Protocol -- HTTP/1.1", RFC 2068, January
+       1997.
+
+   10. Fielding, R., Gettys, J., Mogul, J., Nielsen, H., Masinter, L.,
+       Leach, P. and T. Berners-Lee, "Hypertext Transfer Protocol --
+       HTTP/1.1", RFC 2616, June 1999.
+
+   11. Franks, J., Hallam-Baker, P., Hostetler, J., Leach, P., Luotonen,
+       A., Luotonen, L. and L. Stewart, "HTTP Authentication:  Basic and
+       Digest Access Authnetication", RFC 2617, June 1999.
+
+   12. Freed, N. and N. Borenstein, "Multipurpose Internet Mail
+       Extensions (MIME) Part One:  Format of Internet Message Bodies",
+       RFC 2045, November 1996.
+
+   13. 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.
+
+   14. Arthur van Hoff and Jonathan Payne.  Generic Diff Format
+       Specification.  Technical Report NOTE-GDIFF, World Wide Web
+       Consortium, August, 1997.
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 45]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   15. 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.
+
+   16. James J. Hunt, Kiem-Phong Vo, and Walter F. Tichy.  An Empirical
+       Study of Delta Algorithms.  IEEE Soft. Config. and Maint.
+       Workshop, 1996.
+
+   17. Jacobson, V., "Compressing TCP/IP Headers for Low-Speed Serial
+       Links", RFC 1144, February 1990.
+
+   18. Khare, R. and S. Lawrence, "Upgrading to TLS Within HTTP/1.1",
+       RFC 2817, May 2000.
+
+   19. David G. Korn and Kiem-Phong Vo.  A Generic Differencing and
+       Compression Data Format.  Technical Report HA1630000-021899-02TM,
+       AT&T Labs - Research, February, 1999.
+
+   20. Korn, D. and K. Vo, "The VCDIFF Generic Differencing and
+       Compression Data Format", 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.
+
+   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.
+
+   24. Mogul, J. and A. Van Hoff, "Instance Digests in HTTP", RFC 3230,
+       January 2002.
+
+   25. Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA
+       Considerations Section in RFCs", BCP 26, RFC 2434, October 1998.
+
+   26. The Open Group.  The Single UNIX Specification, Version 2 - 6 Vol
+       Set for UNIX 98.  Document number T912, The Open Group, February,
+       1997.
+
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 46]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   27. W. Tichy.  "RCS - A System For Version Control".  Software -
+       Practice and Experience 15, 7 (July 1985), 637-654.
+
+   28. Andrew Tridgell and Paul Mackerras.  The rsync algorithm.
+       Technical Report TR-CS-96-05, Department of Computer Science,
+       Australian National University, June, 1996.
+
+   29. Stephen Williams.  Personal communication.
+       http://ei.cs.vt.edu/~williams/DIFF/prelim.html.
+
+   30. 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.
+
+16 Authors' addresses
+
+   Jeffrey C. Mogul
+   Western Research Laboratory
+   Compaq Computer Corporation
+   250 University Avenue
+   Palo Alto, California, 94305, U.S.A.
+
+   Phone: 1 650 617 3304 (email preferred)
+   EMail: JeffMogul@acm.org
+
+   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.
+
+   Phone: 1 973 360-8775
+   EMail: douglis@research.att.com
+
+   Anja Feldmann
+   University of Saarbruecken, Germany,
+   Computer Science Department
+   Im Stadtwald, Geb. 36.1, Zimmer 310
+   D-66123 Saarbruecken, Germany
+
+   EMail: anja@cs.uni-sb.de
+
+
+
+Mogul, et al.               Standards Track                    [Page 47]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+   Yaron Y. Goland
+
+   Email: yaron@goland.org
+
+   Arthur van Hoff
+   Marimba, Inc.
+   440 Clyde Avenue
+   Mountain View, CA 94043, U.S.A.
+
+   Phone: 1 650 930 5283
+   EMail: avh@marimba.com
+
+   Daniel M. Hellerstein
+   Economic Research Service, USDA
+   1909 Franwall Ave, Wheaton MD 20902
+
+   Phone: 1 202 694-5613 or 1 301 649-4728
+   EMail: danielh@crosslink.net or webmaster@srehttp.org
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 48]
+
+RFC 3229                 Delta encoding in HTTP             January 2002
+
+
+17 Full Copyright Statement
+
+   Copyright (C) The Internet Society (2002).  All Rights Reserved.
+
+   This document and translations of it may be copied and furnished to
+   others, and derivative works that comment on or otherwise explain it
+   or assist in its implementation may be prepared, copied, published
+   and distributed, in whole or in part, without restriction of any
+   kind, provided that the above copyright notice and this paragraph are
+   included on all such copies and derivative works.  However, this
+   document itself may not be modified in any way, such as by removing
+   the copyright notice or references to the Internet Society or other
+   Internet organizations, except as needed for the purpose of
+   developing Internet standards in which case the procedures for
+   copyrights defined in the Internet Standards process must be
+   followed, or as required to translate it into languages other than
+   English.
+
+   The limited permissions granted above are perpetual and will not be
+   revoked by the Internet Society or its successors or assigns.
+
+   This document and the information contained herein is provided on an
+   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
+   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
+   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
+   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
+   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
+
+Acknowledgement
+
+   Funding for the RFC Editor function is currently provided by the
+   Internet Society.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+Mogul, et al.               Standards Track                    [Page 49]
+