draft-ietf-httpbis-cache-digest-01.txt   draft-ietf-httpbis-cache-digest-latest.txt 
Network Working Group K. Oku HTTP Working Group K. Oku
Internet-Draft DeNA Co, Ltd. Internet-Draft DeNA Co, Ltd.
Intended status: Standards Track M. Nottingham Intended status: Standards Track M. Nottingham
Expires: May 4, 2017 October 31, 2016 Expires: October 28, 2017 April 26, 2017
Cache Digests for HTTP/2 Cache Digests for HTTP/2
draft-ietf-httpbis-cache-digest-01 draft-ietf-httpbis-cache-digest-latest
Abstract Abstract
This specification defines a HTTP/2 frame type to allow clients to This specification defines a HTTP/2 frame type to allow clients to
inform the server of their cache's contents. Servers can then use inform the server of their cache's contents. Servers can then use
this to inform their choices of what to push to clients. this to inform their choices of what to push to clients.
Note to Readers Note to Readers
Discussion of this draft takes place on the HTTP working group Discussion of this draft takes place on the HTTP working group
mailing list (ietf-http-wg@w3.org), which is archived at mailing list (ietf-http-wg@w3.org), which is archived at
https://lists.w3.org/Archives/Public/ietf-http-wg/. https://lists.w3.org/Archives/Public/ietf-http-wg/ .
Working Group information can be found at http://httpwg.github.io/; Working Group information can be found at http://httpwg.github.io/ ;
source code and issues list for this draft can be found at source code and issues list for this draft can be found at
https://github.com/httpwg/http-extensions/labels/cache-digest. https://github.com/httpwg/http-extensions/labels/cache-digest .
Status of this Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on May 4, 2017. This Internet-Draft will expire on October 28, 2017.
Copyright Notice Copyright Notice
Copyright (c) 2016 IETF Trust and the persons identified as the Copyright (c) 2017 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Notational Conventions . . . . . . . . . . . . . . . . . . 3 1.1. Notational Conventions . . . . . . . . . . . . . . . . . 3
2. The CACHE_DIGEST Frame . . . . . . . . . . . . . . . . . . . . 3 2. The CACHE_DIGEST Frame . . . . . . . . . . . . . . . . . . . 3
2.1. Client Behavior . . . . . . . . . . . . . . . . . . . . . 4 2.1. Client Behavior . . . . . . . . . . . . . . . . . . . . . 4
2.1.1. Computing the Digest-Value . . . . . . . . . . . . . . 5 2.1.1. Computing the Digest-Value . . . . . . . . . . . . . 5
2.1.2. Computing a Hash Value . . . . . . . . . . . . . . . . 6 2.1.2. Computing a Hash Value . . . . . . . . . . . . . . . 6
2.2. Server Behavior . . . . . . . . . . . . . . . . . . . . . 6 2.2. Server Behavior . . . . . . . . . . . . . . . . . . . . . 6
2.2.1. Querying the Digest for a Value . . . . . . . . . . . 7 2.2.1. Querying the Digest for a Value . . . . . . . . . . . 7
3. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 3. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8
4. Security Considerations . . . . . . . . . . . . . . . . . . . 8 4. Security Considerations . . . . . . . . . . . . . . . . . . . 8
5. References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5. References . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.1. Normative References . . . . . . . . . . . . . . . . . . . 8 5.1. Normative References . . . . . . . . . . . . . . . . . . 9
5.2. Informative References . . . . . . . . . . . . . . . . . . 9 5.2. Informative References . . . . . . . . . . . . . . . . . 9
Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 9 Appendix A. Acknowledgements . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 10
1. Introduction 1. Introduction
HTTP/2 [RFC7540] allows a server to "push" synthetic request/response HTTP/2 [RFC7540] allows a server to "push" synthetic request/response
pairs into a client's cache optimistically. While there is strong pairs into a client's cache optimistically. While there is strong
interest in using this facility to improve perceived Web browsing interest in using this facility to improve perceived Web browsing
performance, it is sometimes counterproductive because the client performance, it is sometimes counterproductive because the client
might already have cached the "pushed" response. might already have cached the "pushed" response.
When this is the case, the bandwidth used to "push" the response is When this is the case, the bandwidth used to "push" the response is
effectively wasted, and represents opportunity cost, because it could effectively wasted, and represents opportunity cost, because it could
be used by other, more relevant responses. HTTP/2 allows a stream to be used by other, more relevant responses. HTTP/2 allows a stream to
be cancelled by a client using a RST_STREAM frame in this situation, be cancelled by a client using a RST_STREAM frame in this situation,
but there is still at least one round trip of potentially wasted but there is still at least one round trip of potentially wasted
capacity even then. capacity even then.
This specification defines a HTTP/2 frame type to allow clients to This specification defines a HTTP/2 frame type to allow clients to
inform the server of their cache's contents using a Golumb-Rice Coded inform the server of their cache's contents using a Golomb-Rice Coded
Set [Rice]. Servers can then use this to inform their choices of Set [Rice]. Servers can then use this to inform their choices of
what to push to clients. what to push to clients.
1.1. Notational Conventions 1.1. Notational Conventions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in [RFC2119]. document are to be interpreted as described in [RFC2119].
2. The CACHE_DIGEST Frame 2. The CACHE_DIGEST Frame
skipping to change at page 5, line 31 skipping to change at page 5, line 14
CACHE_DIGEST has no defined meaning when sent from servers, and CACHE_DIGEST has no defined meaning when sent from servers, and
SHOULD be ignored by clients. SHOULD be ignored by clients.
2.1.1. Computing the Digest-Value 2.1.1. Computing the Digest-Value
Given the following inputs: Given the following inputs:
o "validators", a boolean indicating whether validators ([RFC7232]) o "validators", a boolean indicating whether validators ([RFC7232])
are to be included in the digest; are to be included in the digest;
o "URLs'", an array of (string "URL", string "ETag") tuples, each o "URLs'", an array of (string "URL", string "ETag") tuples, each
corresponding to the Effective Request URI ([RFC7230], Section corresponding to the Effective Request URI ([RFC7230],
5.5) of a cached response [RFC7234] and its entity-tag [RFC7232] Section 5.5) of a cached response [RFC7234] and its entity-tag
(if "validators" is true and if the ETag is available; otherwise, [RFC7232] (if "validators" is true and if the ETag is available;
null); otherwise, null);
o "P", an integer that MUST be a power of 2 smaller than 2**32, that o "P", an integer that MUST be a power of 2 smaller than 2**32, that
indicates the probability of a false positive that is acceptable, indicates the probability of a false positive that is acceptable,
expressed as "1/P". expressed as "1/P".
"digest-value" can be computed using the following algorithm: "digest-value" can be computed using the following algorithm:
1. Let N be the count of "URLs"' members, rounded to the nearest 1. Let N be the count of "URLs"' members, rounded to the nearest
power of 2 smaller than 2**32. power of 2 smaller than 2**32.
2. Let "hash-values" be an empty array of integers. 2. Let "hash-values" be an empty array of integers.
3. For each ("URL", "ETag") in "URLs", compute a hash value 3. For each ("URL", "ETag") in "URLs", compute a hash value
(Section 2.1.2) and append the result to "hash-values". (Section 2.1.2) and append the result to "hash-values".
4. Sort "hash-values" in ascending order. 4. Sort "hash-values" in ascending order.
5. Let "digest-value" be an empty array of bits. 5. Let "digest-value" be an empty array of bits.
6. Write log base 2 of "N" to "digest-value" using 5 bits. 6. Write log base 2 of "N" to "digest-value" using 5 bits.
7. Write log base 2 of "P" to "digest-value" using 5 bits. 7. Write log base 2 of "P" to "digest-value" using 5 bits.
8. Let "C" be -1. 8. Let "C" be -1.
9. For each "V" in "hash-values": 9. For each "V" in "hash-values":
1. If "V" is equal to "C", continue to the next "V". 1. If "V" is equal to "C", continue to the next "V".
2. Let "D" be the result of "V - C - 1". 2. Let "D" be the result of "V - C - 1".
3. Let "Q" be the integer result of "D / P". 3. Let "Q" be the integer result of "D / P".
4. Let "R" be the result of "D modulo P". 4. Let "R" be the result of "D modulo P".
5. Write "Q" '0' bits to "digest-value". 5. Write "Q" '0' bits to "digest-value".
6. Write 1 '1' bit to "digest-value". 6. Write 1 '1' bit to "digest-value".
7. Write "R" to "digest-value" as binary, using log2("P") bits. 7. Write "R" to "digest-value" as binary, using log2("P") bits.
8. Let "C" be "V" 8. Let "C" be "V"
10. If the length of "digest-value" is not a multiple of 8, pad it 10. If the length of "digest-value" is not a multiple of 8, pad it
with 0s until it is. with 0s until it is.
2.1.2. Computing a Hash Value 2.1.2. Computing a Hash Value
Given: Given:
o "URL", an array of characters o "URL", an array of characters
o "ETag", an array of characters o "ETag", an array of characters
o "validators", a boolean o "validators", a boolean
o "N", an integer o "N", an integer
o "P", an integer o "P", an integer
"hash-value" can be computed using the following algorithm: "hash-value" can be computed using the following algorithm:
1. Let "key" be "URL" converted to an ASCII string by percent- 1. Let "key" be "URL" converted to an ASCII string by percent-
encoding as appropriate [RFC3986]. encoding as appropriate [RFC3986].
2. If "validators" is true and "ETag" is not null: 2. If "validators" is true and "ETag" is not null:
1. Append "ETag" to "key" as an ASCII string, including both the 1. Append "ETag" to "key" as an ASCII string, including both the
"weak" indicator (if present) and double quotes, as per "weak" indicator (if present) and double quotes, as per
[RFC7232] Section 2.3. [RFC7232] Section 2.3.
3. Let "hash-value" be the SHA-256 message digest [RFC6234] of 3. Let "hash-value" be the SHA-256 message digest [RFC6234] of
"key", expressed as an integer. "key", expressed as an integer.
4. Truncate "hash-value" to log2( "N" * "P" ) bits. 4. Truncate "hash-value" to log2( "N" * "P" ) bits.
2.2. Server Behavior 2.2. Server Behavior
In typical use, a server will query (as per Section 2.2.1) the In typical use, a server will query (as per Section 2.2.1) the
CACHE_DIGESTs received on a given connection to inform what it pushes CACHE_DIGESTs received on a given connection to inform what it pushes
to that client; to that client;
o If a given URL has a match in a current CACHE_DIGEST with the o If a given URL has a match in a current CACHE_DIGEST with the
STALE flag unset, it need not be pushed, because it is fresh in STALE flag unset, it need not be pushed, because it is fresh in
cache; cache;
o If a given URL and ETag combination has a match in a current o If a given URL and ETag combination has a match in a current
CACHE_DIGEST with the STALE flag set, the client has a stale copy CACHE_DIGEST with the STALE flag set, the client has a stale copy
in cache, and a validating response can be pushed; in cache, and a validating response can be pushed;
o If a given URL has no match in any current CACHE_DIGEST, the o If a given URL has no match in any current CACHE_DIGEST, the
client does not have a cached copy, and a complete response can be client does not have a cached copy, and a complete response can be
pushed. pushed.
Servers MAY use all CACHE_DIGESTs received for a given origin as Servers MAY use all CACHE_DIGESTs received for a given origin as
current, as long as they do not have the RESET flag set; a current, as long as they do not have the RESET flag set; a
skipping to change at page 7, line 30 skipping to change at page 7, line 37
CACHE_DIGEST. CACHE_DIGEST.
Servers MUST ignore CACHE_DIGEST frames sent on a stream other than Servers MUST ignore CACHE_DIGEST frames sent on a stream other than
0. 0.
2.2.1. Querying the Digest for a Value 2.2.1. Querying the Digest for a Value
Given: Given:
o "digest-value", an array of bits o "digest-value", an array of bits
o "URL", an array of characters o "URL", an array of characters
o "ETag", an array of characters o "ETag", an array of characters
o "validators", a boolean o "validators", a boolean
we can determine whether there is a match in the digest using the we can determine whether there is a match in the digest using the
following algorithm: following algorithm:
1. Read the first 5 bits of "digest-value" as an integer; let "N" 1. Read the first 5 bits of "digest-value" as an integer; let "N"
be two raised to the power of that value. be two raised to the power of that value.
2. Read the next 5 bits of "digest-value" as an integer; let "P" be 2. Read the next 5 bits of "digest-value" as an integer; let "P" be
two raised to the power of that value. two raised to the power of that value.
3. Let "hash-value" be the result of computing a hash value 3. Let "hash-value" be the result of computing a hash value
(Section 2.1.2). (Section 2.1.2).
4. Let "C" be -1. 4. Let "C" be -1.
5. Read '0' bits from "digest-value" until a '1' bit is found; let 5. Read '0' bits from "digest-value" until a '1' bit is found; let
"Q" bit the number of '0' bits. Discard the '1'. "Q" be the number of '0' bits. Discard the '1'.
6. Read log2("P") bits from "digest-value" after the '1' as an 6. Read log2("P") bits from "digest-value" after the '1' as an
integer; let "R" be its value. integer; let "R" be its value.
7. Let "D" be "Q" * "P" + "R". 7. Let "D" be "Q" * "P" + "R".
8. Increment "C" by "D" + 1. 8. Increment "C" by "D" + 1.
9. If "C" is equal to "hash-value", return 'true'. 9. If "C" is equal to "hash-value", return 'true'.
10. Otherwise, return to step 5 and continue processing; if no match 10. Otherwise, return to step 5 and continue processing; if no match
is found before "digest-value" is exhausted, return 'false'. is found before "digest-value" is exhausted, return 'false'.
3. IANA Considerations 3. IANA Considerations
This draft currently has no requirements for IANA. If the This draft currently has no requirements for IANA. If the
CACHE_DIGEST frame is standardised, it will need to be assigned a CACHE_DIGEST frame is standardised, it will need to be assigned a
frame type. frame type.
skipping to change at page 8, line 41 skipping to change at page 9, line 10
be. be.
Additionally, User Agents SHOULD NOT send CACHE_DIGEST when in Additionally, User Agents SHOULD NOT send CACHE_DIGEST when in
"privacy mode." "privacy mode."
5. References 5. References
5.1. Normative References 5.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/ Requirement Levels", BCP 14, RFC 2119,
RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>. <http://www.rfc-editor.org/info/rfc2119>.
[RFC3986] Berners-Lee, T., Fielding, R., and L. Masinter, "Uniform [RFC3986] Berners-Lee, T., Fielding, R., and L. Masinter, "Uniform
Resource Identifier (URI): Generic Syntax", STD 66, Resource Identifier (URI): Generic Syntax", STD 66,
RFC 3986, DOI 10.17487/RFC3986, January 2005, RFC 3986, DOI 10.17487/RFC3986, January 2005,
<http://www.rfc-editor.org/info/rfc3986>. <http://www.rfc-editor.org/info/rfc3986>.
[RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms [RFC6234] Eastlake 3rd, D. and T. Hansen, "US Secure Hash Algorithms
(SHA and SHA-based HMAC and HKDF)", RFC 6234, (SHA and SHA-based HMAC and HKDF)", RFC 6234,
DOI 10.17487/RFC6234, May 2011, DOI 10.17487/RFC6234, May 2011,
skipping to change at page 9, line 47 skipping to change at page 10, line 12
DOI 10.17487/RFC6265, April 2011, DOI 10.17487/RFC6265, April 2011,
<http://www.rfc-editor.org/info/rfc6265>. <http://www.rfc-editor.org/info/rfc6265>.
[Rice] Rice, R. and J. Plaunt, "Adaptive variable-length coding [Rice] Rice, R. and J. Plaunt, "Adaptive variable-length coding
for efficient compression of spacecraft television data", for efficient compression of spacecraft television data",
IEEE Transactions on Communication Technology 19.6 , 1971. IEEE Transactions on Communication Technology 19.6 , 1971.
Appendix A. Acknowledgements Appendix A. Acknowledgements
Thanks to Adam Langley and Giovanni Bajo for their explorations of Thanks to Adam Langley and Giovanni Bajo for their explorations of
Golumb-coded sets. In particular, see http://giovanni.bajo.it/post/ Golomb-coded sets. In particular, see
47119962313/golomb-coded-sets-smaller-than-bloom-filters, which http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-
refers to sample code. than-bloom-filters , which refers to sample code.
Thanks to Stefan Eissing for his suggestions. Thanks to Stefan Eissing for his suggestions.
Authors' Addresses Authors' Addresses
Kazuho Oku Kazuho Oku
DeNA Co, Ltd. DeNA Co, Ltd.
Email: kazuhooku@gmail.com Email: kazuhooku@gmail.com
 End of changes. 52 change blocks. 
36 lines changed or deleted 73 lines changed or added

This html diff was produced by rfcdiff 1.44jr. The latest version is available from http://tools.ietf.org/tools/rfcdiff/