idnits 2.17.1 draft-ietf-quic-qcram-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 149: '...ulnerable header fields, BLOCKING MUST...' RFC 2119 keyword, line 156: '... flag MUST be set. If the peer does...' RFC 2119 keyword, line 171: '... MUST remain in the blocked stream's...' RFC 2119 keyword, line 184: '.... The value of BLOCKING MUST be 0 for...' RFC 2119 keyword, line 220: '...e Control Stream SHOULD contain only L...' (7 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 20, 2018) is 2229 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) -- Looks like a reference, but probably isn't: '1' on line 411 == Missing Reference: 'M' is mentioned on line 411, but not defined == Outdated reference: A later version (-34) exists of draft-ietf-quic-http-09 == Outdated reference: A later version (-34) exists of draft-ietf-quic-transport-09 -- Obsolete informational reference (is this intentional?): RFC 7540 (Obsoleted by RFC 9113) Summary: 1 error (**), 0 flaws (~~), 4 warnings (==), 3 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 QUIC C. Krasic 3 Internet-Draft Google, Inc 4 Intended status: Standards Track M. Bishop 5 Expires: August 24, 2018 Akamai Technologies 6 A. Frindell, Ed. 7 Facebook 8 February 20, 2018 10 Header Compression for HTTP over QUIC 11 draft-ietf-quic-qcram-00 13 Abstract 15 The design of the core QUIC transport subsumes many HTTP/2 features, 16 prominent among them stream multiplexing. A key advantage of the 17 QUIC transport is stream multiplexing free of head-of-line (HoL) 18 blocking between streams. In HTTP/2, multiplexed streams can suffer 19 HoL blocking due to TCP. 21 If HTTP/2's HPACK is used for header compression, HTTP/QUIC is still 22 vulnerable to HoL blocking, because of HPACK's assumption of in-order 23 delivery. This draft defines QCRAM, a variation of HPACK and 24 mechanisms in the HTTP/QUIC mapping that allow the flexibility to 25 avoid header-compression-induced HoL blocking. 27 Status of This Memo 29 This Internet-Draft is submitted in full conformance with the 30 provisions of BCP 78 and BCP 79. 32 Internet-Drafts are working documents of the Internet Engineering 33 Task Force (IETF). Note that other groups may also distribute 34 working documents as Internet-Drafts. The list of current Internet- 35 Drafts is at https://datatracker.ietf.org/drafts/current/. 37 Internet-Drafts are draft documents valid for a maximum of six months 38 and may be updated, replaced, or obsoleted by other documents at any 39 time. It is inappropriate to use Internet-Drafts as reference 40 material or to cite them other than as "work in progress." 42 This Internet-Draft will expire on August 24, 2018. 44 Copyright Notice 46 Copyright (c) 2018 IETF Trust and the persons identified as the 47 document authors. All rights reserved. 49 This document is subject to BCP 78 and the IETF Trust's Legal 50 Provisions Relating to IETF Documents 51 (https://trustee.ietf.org/license-info) in effect on the date of 52 publication of this document. Please review these documents 53 carefully, as they describe your rights and restrictions with respect 54 to this document. Code Components extracted from this document must 55 include Simplified BSD License text as described in Section 4.e of 56 the Trust Legal Provisions and are provided without warranty as 57 described in the Simplified BSD License. 59 Table of Contents 61 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 62 1.1. Head-of-Line Blocking in HPACK . . . . . . . . . . . . . 3 63 1.2. Avoiding Head-of-Line Blocking in HTTP/QUIC . . . . . . . 3 64 2. HTTP over QUIC mapping extensions . . . . . . . . . . . . . . 4 65 2.1. HEADERS and PUSH_PROMISE . . . . . . . . . . . . . . . . 4 66 2.2. HEADER_ACK . . . . . . . . . . . . . . . . . . . . . . . 5 67 3. HPACK extensions . . . . . . . . . . . . . . . . . . . . . . 5 68 3.1. Allowed Instructions . . . . . . . . . . . . . . . . . . 5 69 3.2. Header Block Prefix . . . . . . . . . . . . . . . . . . . 5 70 3.3. Hybrid absolute-relative indexing . . . . . . . . . . . . 6 71 3.4. Preventing Eviction Races . . . . . . . . . . . . . . . . 7 72 3.4.1. Blocked Evictions . . . . . . . . . . . . . . . . . . 7 73 3.5. Refreshing Entries with Duplication . . . . . . . . . . . 8 74 4. Performance considerations . . . . . . . . . . . . . . . . . 8 75 4.1. Speculative table updates . . . . . . . . . . . . . . . . 8 76 4.2. Additional state beyond HPACK. . . . . . . . . . . . . . 8 77 4.2.1. Vulnerable Entries . . . . . . . . . . . . . . . . . 8 78 4.2.2. Safe evictions . . . . . . . . . . . . . . . . . . . 9 79 4.2.3. Decoder Blocking . . . . . . . . . . . . . . . . . . 9 80 4.2.4. Fixed overhead. . . . . . . . . . . . . . . . . . . . 9 81 5. Security Considerations . . . . . . . . . . . . . . . . . . . 10 82 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 83 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 10 84 8. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 85 8.1. Normative References . . . . . . . . . . . . . . . . . . 10 86 8.2. Informative References . . . . . . . . . . . . . . . . . 11 87 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 89 1. Introduction 91 The QUIC transport protocol was designed from the outset to support 92 HTTP semantics, and its design subsumes many of the features of 93 HTTP/2. QUIC's stream multiplexing comes into some conflict with 94 header compression. A key goal of the design of QUIC is to improve 95 stream multiplexing relative to HTTP/2 by eliminating HoL (head of 96 line) blocking, which can occur in HTTP/2. HoL blocking can happen 97 because all HTTP/2 streams are multiplexed onto a single TCP 98 connection with its in-order semantics. QUIC can maintain 99 independence between streams because it implements core transport 100 functionality in a fully stream-aware manner. However, the HTTP/QUIC 101 mapping is still subject to HoL blocking if HPACK is used directly. 102 HPACK exploits multiplexing for greater compression, shrinking the 103 representation of headers that have appeared earlier on the same 104 connection. In the context of QUIC, this imposes a vulnerability to 105 HoL blocking (see Section 1.1). 107 QUIC is described in [QUIC-TRANSPORT]. The HTTP/QUIC mapping is 108 described in [QUIC-HTTP]. For a full description of HTTP/2, see 109 [RFC7540]. The description of HPACK is [RFC7541], with important 110 terminology in Section 1.3. 112 QCRAM modifies HPACK to allow correctness in the presence of out-of- 113 order delivery, with flexibility for implementations to balance 114 between resilience against HoL blocking and optimal compression 115 ratio. The design goals are to closely approach the compression 116 ratio of HPACK with substantially less head-of-line blocking under 117 the same loss conditions. 119 QCRAM is intended to be a relatively non-intrusive extension to 120 HPACK; an implementation should be easily shared within stacks 121 supporting both HTTP/2 over (TLS+)TCP and HTTP/QUIC. 123 1.1. Head-of-Line Blocking in HPACK 125 HPACK enables several types of header representations, one of which 126 also adds the header to a dynamic table of header values. These 127 values are then available for reuse in subsequent header blocks 128 simply by referencing the entry number in the table. 130 If the packet containing a header is lost, that stream cannot 131 complete header processing until the packet is retransmitted. This 132 is unavoidable. However, other streams which rely on the state 133 created by that packet _also_ cannot make progress. This is the 134 problem which QUIC solves in general, but which is reintroduced by 135 HPACK when the loss includes a HEADERS frame. 137 1.2. Avoiding Head-of-Line Blocking in HTTP/QUIC 139 In the example above, the second stream contained a reference to data 140 which might not yet have been processed by the recipient. Such 141 references are called "vulnerable," because the loss of a different 142 packet can keep the reference from being usable. 144 The encoder can choose on a per-header-block basis whether to favor 145 higher compression ratio (by permitting vulnerable references) or HoL 146 resilience (by avoiding them). This is signaled by the BLOCKING flag 147 in HEADERS and PUSH_PROMISE frames (see Section 2). 149 If a header block contains no vulnerable header fields, BLOCKING MUST 150 be 0. This implies that the header fields are represented either as 151 references to dynamic table entries which are known to have been 152 received, or as Literal header fields (see [RFC7541] Section 6.2). 154 If a header block contains any header field which references dynamic 155 table state which the peer might not have received yet, the BLOCKING 156 flag MUST be set. If the peer does not yet have the appropriate 157 state, such blocks might not be processed on arrival. 159 The header block contains a prefix (Section 3.2). This prefix 160 contains table offset information that establishes total ordering 161 among all headers, regardless of reordering in the transport (see 162 Section 3.3). 164 In blocking mode, the prefix additionally identifies the minimum 165 state required to process any vulnerable references in the header 166 block (see "Depends Index" in Section 3.3). The decoder keeps track 167 of which entries have been added to its dynamic table. The stream 168 for a header with BLOCKING flag set is considered blocked by the 169 decoder and can not be processed until all entries in the range "[1, 170 Depends Index]" have been added. While blocked, header field data 171 MUST remain in the blocked stream's flow control window. 173 2. HTTP over QUIC mapping extensions 175 2.1. HEADERS and PUSH_PROMISE 177 HEADERS and PUSH_PROMISE frames define a new flag. 179 BLOCKING (0x01): Indicates the stream might need to wait for 180 dependent headers before processing. If 0, the frame can be 181 processed immediately upon receipt. 183 HEADERS frames can be sent on the Connection Control Stream as well 184 as on request / push streams. The value of BLOCKING MUST be 0 for 185 HEADERS frames on the Connection Control Stream, since they can only 186 depend on previous HEADERS on the same stream. 188 2.2. HEADER_ACK 190 The HEADER_ACK frame (type=0x8) is sent from the decoder to the 191 encoder on the Control Stream when the decoder has fully processed a 192 header block. It is used by the encoder to determine whether 193 subsequent indexed representations that might reference that block 194 are vulnerable to HoL blocking, and to prevent eviction races (see 195 Section 3.4). 197 The HEADER_ACK frame indicates the stream on which the header block 198 was processed by encoding the Stream ID as a variable-length integer. 199 The same Stream ID can be identified multiple times, as multiple 200 header-containing blocks can be sent on a single stream in the case 201 of intermediate responses, trailers, pushed requests, etc. as well as 202 on the Control Streams. Since header frames on each stream are 203 received and processed in order, this gives the encoder precise 204 feedback on which header blocks within a stream have been fully 205 processed. 207 0 1 2 3 4 5 6 7 208 +---+---+---+---+---+---+---+---+ 209 | Stream ID [i] | 210 +---+---------------------------+ 212 HEADER_ACK frame 214 The HEADER_ACK frame does not define any flags. 216 3. HPACK extensions 218 3.1. Allowed Instructions 220 HEADERS frames on the Control Stream SHOULD contain only Literal with 221 Incremental Indexing and Indexed with Duplication (see Section 3.5) 222 representations. Frames on this stream modify the dynamic table 223 state without generating output to any particular request. 225 HEADERS and PUSH_PROMISE frames on request and push streams MUST NOT 226 contain Literal with Incremental Indexing and Indexed with 227 Duplication representations. Frames on these streams reference the 228 dynamic table in a particular state without modifying it, but emit 229 the headers for an HTTP request or response. 231 3.2. Header Block Prefix 233 For request and push promise streams, in HEADERS and PUSH_PROMISE 234 frames, HPACK Header data is prefixed by an integer: "Base Index". 235 "Base index" is the cumulative number of entries added to the dynamic 236 table prior to encoding the current block, including any entries 237 already evicted. It is encoded as a single 8-bit prefix integer: 239 0 1 2 3 4 5 6 7 240 +-+-+-+-+-+-+-+-+ 241 |Base Index (8+)| 242 +---------------+ 244 Figure 1: Absolute indexing (BLOCKING=0x0) 246 Section 3.3 describes the role of "Base Index". 248 When the BLOCKING flag is 0x1, a the prefix additionally contains a 249 second HPACK integer (8-bit prefix) 'Depends': 251 0 1 2 3 4 5 6 7 252 +-+-+-+-+-+-+-+-+ 253 |Base Index (8+)| 254 +---------------+ 255 |Depends (8+)| 256 +---------------+ 258 Figure 2: Absolute indexing (BLOCKING=0x1) 260 Depends is used to identify header dependencies (see Section 1.2). 261 The encoder computes a value "Depends Index" which is the largest 262 (absolute) index referenced by the following header block. To help 263 keep the prefix smaller, "Depends Index" is converted to a relative 264 value: "Depends = Base Index - Depends Index". 266 3.3. Hybrid absolute-relative indexing 268 HPACK indexed entries refer to an entry by its current position in 269 the dynamic table. As Figure 1 of [RFC7541] illustrates, newer 270 entries have smaller indices, and older entries are evicted first if 271 the table is full. Under this scheme, each insertion to the table 272 causes the index of all existing entries to change (implicitly). 273 Implicit index updates are acceptable for HTTP/2 because TCP is 274 totally ordered, but are problematic in the out-of-order context of 275 QUIC. 277 QCRAM uses a hybrid absolute-relative indexing approach. 279 When the encoder adds a new entry to its header table, it can compute 280 an absolute index: 282 "entry.absoluteIndex = baseIndex++; " 283 Since literals with indexing are only sent on the control stream, the 284 decoder can be guaranteed to compute the same absolute index values 285 when it adds corresponding entries to its table, just as in HPACK and 286 HTTP/2. 288 When encoding indexed representations, the following holds for 289 (relative) HPACK indices: 291 "relative index = baseIndex - entry.absoluteIndex + staticTable.size" 293 Header blocks on request and push streams do not modify the dynamic 294 table state, so they never change the "baseIndex". However, since 295 ordering between streams is not guaranteed, the value of "baseIndex" 296 can not be synchronized implicitly. Instead then, QCRAM sends 297 encoder's "Base Index" explicitly as part of the prefix (see 298 Section 3.2), so that the decoder can compute the same absolute 299 indices that the encoder used: 301 "absoluteIndex = prefix.baseIndex + staticTable.size - 302 relativeIndex;" 304 In this way, even if request or push stream headers are decoded in a 305 different order than encoded, the absolute indices will still 306 identify the correct table entries. 308 It is an error if the HPACK decoder encounters an indexed 309 representation that refers to an entry missing from the table, and 310 the connection MUST be closed with the 311 "HTTP_HPACK_DECOMPRESSION_FAILED" error code. 313 3.4. Preventing Eviction Races 315 Due to out-of-order arrival, QCRAM's eviction algorithm requires 316 changes (relative to HPACK) to avoid the possibility that an indexed 317 representation is decoded after the referenced entry has already been 318 evicted. QCRAM employs a two-phase eviction algorithm, in which the 319 encoder will not evict entries that have outstanding (unacknowledged) 320 references. 322 3.4.1. Blocked Evictions 324 The encoder MUST NOT permit an entry to be evicted while a reference 325 to that entry remains unacknowledged. If a new header to be inserted 326 into the dynamic table would cause the eviction of such an entry, the 327 encoder MUST NOT emit the insert instruction until the reference has 328 been processed by the decoder and acknowledged. 330 The encoder can emit a literal representation for the new header in 331 order to avoid encoding delays, and MAY insert the header into the 332 table later if desired. 334 To ensure that the blocked eviction case is rare, references to the 335 oldest entries in the dynamic table SHOULD be avoided. When one of 336 the oldest entries in the table is still actively used for 337 references, the encoder SHOULD emit an Indexed-Duplicate 338 representation instead (see Section 3.5). 340 3.5. Refreshing Entries with Duplication 342 0 1 2 3 4 5 6 7 343 +-+-+-+-+-+-+-+-+ 344 |0|0|1|Index(5+)| 345 +-+-+-+---------+ 347 Figure 3: Indexed Header Field with Duplication 349 _Indexed-Duplicates_ insert a new entry into the dynamic table which 350 duplicates an existing entry. [RFC7541] allows duplicate HPACK table 351 entries, that is entries that have the same name and value. 353 This replaces the HPACK instruction for Dynamic Table Size Update 354 (see Section 6.3 of [RFC7541], which is not supported by HTTP over 355 QUIC. 357 4. Performance considerations 359 4.1. Speculative table updates 361 Implementations can _speculatively_ send header frames on the HTTP 362 Control Streams which are not needed for any current HTTP request or 363 response. Such headers could be used strategically to improve 364 performance. For instance, the encoder might decide to _refresh_ by 365 sending Indexed-Duplicate representations for popular header fields 366 (Section 3.2), ensuring they have small indices and hence minimal 367 size on the wire. 369 4.2. Additional state beyond HPACK. 371 4.2.1. Vulnerable Entries 373 For header blocks encoded in non-blocking mode, the encoder needs to 374 forego indexed representations that refer to vulnerable entries (see 375 Section 1.2). An implementation could extend the header table entry 376 with a boolean to track vulnerability. However, the number of 377 entries in the table that are vulnerable is likely to be small in 378 practice, much less than the total number of entries, so a data 379 tracking only vulnerable (un-acknowledged) entries, separate from the 380 main header table, might be more space efficient. 382 4.2.2. Safe evictions 384 Section Section 3.4 describes how QCRAM avoids invalid references 385 that might result from out-of-order delivery. When the encoder 386 processes a HEADER_ACK, it dereferences table entries that were 387 indexed in the acknowledged header. To track which entries must be 388 dereferenced, it can maintain a map from unacknowledged headers to 389 lists of (absolute) indices. The simplest place to store the actual 390 reference count might be the table entries. In practice the number 391 of entries in the table with a non-zero reference count is likely to 392 stay quite small. A data structure tracking only entries with non- 393 zero reference counts, separate from the main header table, could be 394 more space efficient. 396 4.2.3. Decoder Blocking 398 To support blocking, the decoder needs to keep track of entries it 399 has added to the dynamic table (see Section 1.2), and it needs to 400 track blocked streams. 402 Tracking added entries might be done in a brute force fashion without 403 additional space. However, this would have O(N) cost where N is the 404 number of entries in the dynamic table. Alternatively, a dedicated 405 data structure might improve on brute force in exchange a small 406 amount of additional space. For example, a set of pairs (of 407 indices), representing non-overlapping sub-ranges can be used. Each 408 operation (add, or query) can be done within O(log M) complexity. 409 Here set size M is the number of sub-ranges. In practice M would be 410 very small, as most table entries would be concentrated in the first 411 sub-range [1, M]. 413 To track blocked streams, an ordered map (e.g. multi-map) from 414 "Depends Index" values to streams can be used. Whenever the decoder 415 processes a header block, it can drain any members of the blocked 416 streams map that have "Depends Index <= M" where "[1,M]" is the first 417 member of the added- entries sub-ranges set. Again, the complexity 418 of operations would be at most O(log N), N being the number of 419 concurrently blocked streams. 421 4.2.4. Fixed overhead. 423 HPACK defines overhead as 32 bytes ([RFC7541] Section 4.1). As 424 described above, QCRAM adds some per-connection state, and possibly 425 some per-entry state to track acknowledgment status and eviction 426 reference count. A larger value than 32 might be more accurate for 427 QCRAM. 429 5. Security Considerations 431 TBD. 433 6. IANA Considerations 435 This document registers a new frame type, HEADER_ACK, for HTTP/QUIC. 436 This will need to be added to the IANA Considerations of [QUIC-HTTP]. 438 7. Acknowledgments 440 This draft draws heavily on the text of [RFC7541]. The indirect 441 input of those authors is gratefully acknowledged, as well as ideas 442 from: 444 o Mike Bishop 446 o Alan Frindell 448 o Ryan Hamilton 450 o Patrick McManus 452 o Kazuho Oku 454 o Biren Roy 456 o Ian Swett 458 o Dmitri Tikhonov 460 8. References 462 8.1. Normative References 464 [QUIC-HTTP] 465 Bishop, M., "Hypertext Transfer Protocol (HTTP) over 466 QUIC", draft-ietf-quic-http-09 (work in progress), January 467 2018. 469 [RFC7541] Peon, R. and H. Ruellan, "HPACK: Header Compression for 470 HTTP/2", RFC 7541, DOI 10.17487/RFC7541, May 2015, 471 . 473 8.2. Informative References 475 [QUIC-TRANSPORT] 476 Iyengar, J. and M. Thomson, "QUIC: A UDP-Based Multiplexed 477 and Secure Transport", draft-ietf-quic-transport-09 (work 478 in progress), January 2018. 480 [RFC7540] Belshe, M., Peon, R., and M. Thomson, Ed., "Hypertext 481 Transfer Protocol Version 2 (HTTP/2)", RFC 7540, 482 DOI 10.17487/RFC7540, May 2015, 483 . 485 Authors' Addresses 487 Charles 'Buck' Krasic 488 Google, Inc 490 Email: ckrasic@google.com 492 Mike Bishop 493 Akamai Technologies 495 Email: mbishop@evequefou.be 497 Alan Frindell (editor) 498 Facebook 500 Email: afrind@fb.com