7 Management of base instances
If the time between modifications of a resource is less than the
typical eviction time for responses in client caches, this means that
the "old instance" indicated in a client's conditional request might
not refer to the most recent prior instance. This raises the
question of how many old instances of a resource should be maintained
by the server, if any. We call these old instances "base instances."
There are many possible options for server implementors. For
example:
- 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
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].
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
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
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:
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.
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 RFCor 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 RFC2434 [25]).
This specification also inserts a new value in the IANA HTTP Status
Code Registry (see RFC2817 [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.
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.
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
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.
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.
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.
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.
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).
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:
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).
10.8 New Cache-Control directives
We define two new cache-directives (see section 14.9 of RFC2616 [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.
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.
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
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.
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", RFC1945, May 1996.
3. Bradner, S., "Key words for use in RFCs to Indicate Requirement
Levels", BCP 14, RFC2119, March 1997.
4. Edith Cohen, Balachander Krishnamurthy, and Jennifer Rexford.
Improving End-to-End Performance of the Web Using Server Volumes
and Proxy Filters. Proc. SIGCOMM '98, September, 1998, pp. 241-
253.
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", RFC1951, May 1996.
7. Deutsch, P. and J-L. Gailly, "ZLIB Compressed Data Format
Specification version 3.3", RFC1950, 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", RFC2068, 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", RFC2616, 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", RFC2617, June 1999.
12. Freed, N. and N. Borenstein, "Multipurpose Internet Mail
Extensions (MIME) Part One: Format of Internet Message Bodies",
RFC2045, 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.
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", RFC1144, February 1990.
18. Khare, R. and S. Lawrence, "Upgrading to TLS Within HTTP/1.1",
RFC2817, 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", RFC3230,
January 2002.
25. Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA
Considerations Section in RFCs", BCP 26, RFC2434, 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.
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
Yaron Y. Goland
Email: yaron@goland.org