idnits 2.17.1 draft-ietf-quic-qpack-02.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 abstract seems to contain references ([2], [3], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (August 15, 2018) is 2080 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. 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 1088 -- Looks like a reference, but probably isn't: '2' on line 1090 -- Looks like a reference, but probably isn't: '3' on line 1092 == Outdated reference: A later version (-34) exists of draft-ietf-quic-http-14 == Outdated reference: A later version (-34) exists of draft-ietf-quic-transport-13 -- Obsolete informational reference (is this intentional?): RFC 7540 (Obsoleted by RFC 9113) Summary: 1 error (**), 0 flaws (~~), 3 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 QUIC C. Krasic 3 Internet-Draft Netflix 4 Intended status: Standards Track M. Bishop 5 Expires: February 16, 2019 Akamai Technologies 6 A. Frindell, Ed. 7 Facebook 8 August 15, 2018 10 QPACK: Header Compression for HTTP over QUIC 11 draft-ietf-quic-qpack-02 13 Abstract 15 This specification defines QPACK, a compression format for 16 efficiently representing HTTP header fields, to be used in HTTP over 17 QUIC. This is a variation of HPACK header compression that seeks to 18 reduce head-of-line blocking. 20 Note to Readers 22 Discussion of this draft takes place on the QUIC working group 23 mailing list (quic@ietf.org), which is archived at 24 https://mailarchive.ietf.org/arch/search/?email_list=quic [1]. 26 Working Group information can be found at https://github.com/quicwg 27 [2]; source code and issues list for this draft can be found at 28 https://github.com/quicwg/base-drafts/labels/-qpack [3]. 30 Status of This Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at https://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on February 16, 2019. 47 Copyright Notice 49 Copyright (c) 2018 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (https://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 65 2. Header Tables . . . . . . . . . . . . . . . . . . . . . . . . 4 66 2.1. Static Table . . . . . . . . . . . . . . . . . . . . . . 4 67 2.2. Dynamic Table . . . . . . . . . . . . . . . . . . . . . . 4 68 2.2.1. Absolute and Relative Indexing . . . . . . . . . . . 5 69 2.2.2. Post-Base Indexing . . . . . . . . . . . . . . . . . 6 70 2.3. Avoiding Head-of-Line Blocking in HTTP/QUIC . . . . . . . 7 71 2.3.1. State Synchronization . . . . . . . . . . . . . . . . 8 72 3. Conventions and Definitions . . . . . . . . . . . . . . . . . 9 73 3.1. Notational Conventions . . . . . . . . . . . . . . . . . 9 74 4. Configuration . . . . . . . . . . . . . . . . . . . . . . . . 9 75 5. Wire Format . . . . . . . . . . . . . . . . . . . . . . . . . 10 76 5.1. Primitives . . . . . . . . . . . . . . . . . . . . . . . 10 77 5.1.1. Prefixed Integers . . . . . . . . . . . . . . . . . . 10 78 5.1.2. String Literals . . . . . . . . . . . . . . . . . . . 10 79 5.2. QPACK Encoder Stream . . . . . . . . . . . . . . . . . . 11 80 5.2.1. Insert With Name Reference . . . . . . . . . . . . . 11 81 5.2.2. Insert Without Name Reference . . . . . . . . . . . . 12 82 5.2.3. Duplicate . . . . . . . . . . . . . . . . . . . . . . 12 83 5.2.4. Dynamic Table Size Update . . . . . . . . . . . . . . 13 84 5.3. QPACK Decoder Stream . . . . . . . . . . . . . . . . . . 13 85 5.3.1. Table State Synchronize . . . . . . . . . . . . . . . 13 86 5.3.2. Header Acknowledgement . . . . . . . . . . . . . . . 14 87 5.3.3. Stream Cancellation . . . . . . . . . . . . . . . . . 15 88 5.4. Request and Push Streams . . . . . . . . . . . . . . . . 15 89 5.4.1. Header Data Prefix . . . . . . . . . . . . . . . . . 15 90 5.4.2. Instructions . . . . . . . . . . . . . . . . . . . . 17 91 6. Error Handling . . . . . . . . . . . . . . . . . . . . . . . 19 92 7. Encoding Strategies . . . . . . . . . . . . . . . . . . . . . 20 93 7.1. Single Pass Encoding . . . . . . . . . . . . . . . . . . 20 94 7.2. Preventing Eviction Races . . . . . . . . . . . . . . . . 20 95 7.3. Reference Tracking . . . . . . . . . . . . . . . . . . . 20 96 7.3.1. Blocked Eviction . . . . . . . . . . . . . . . . . . 20 97 7.3.2. Blocked Decoding . . . . . . . . . . . . . . . . . . 21 98 7.4. Speculative table updates . . . . . . . . . . . . . . . . 21 99 7.5. Sample One Pass Encoding Algorithm . . . . . . . . . . . 21 100 8. Security Considerations . . . . . . . . . . . . . . . . . . . 23 101 9. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23 102 9.1. Settings Registration . . . . . . . . . . . . . . . . . . 23 103 9.2. Stream Type Registration . . . . . . . . . . . . . . . . 23 104 9.3. Error Code Registration . . . . . . . . . . . . . . . . . 23 105 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 24 106 10.1. Normative References . . . . . . . . . . . . . . . . . . 24 107 10.2. Informative References . . . . . . . . . . . . . . . . . 24 108 10.3. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 24 109 Appendix A. Change Log . . . . . . . . . . . . . . . . . . . . . 25 110 A.1. Since draft-ietf-quic-qpack-01 . . . . . . . . . . . . . 25 111 A.2. Since draft-ietf-quic-qpack-00 . . . . . . . . . . . . . 25 112 A.3. Since draft-ietf-quic-qcram-00 . . . . . . . . . . . . . 25 113 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 25 114 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 26 116 1. Introduction 118 The QUIC transport protocol was designed from the outset to support 119 HTTP semantics, and its design subsumes many of the features of 120 HTTP/2. HTTP/2 uses HPACK ([RFC7541]) for header compression, but 121 QUIC's stream multiplexing comes into some conflict with HPACK. A 122 key goal of the design of QUIC is to improve stream multiplexing 123 relative to HTTP/2 by reducing head-of-line blocking. If HPACK were 124 used for HTTP/QUIC, it would induce head-of-line blocking due to 125 built-in assumptions of a total ordering across frames on all 126 streams. 128 QUIC is described in [QUIC-TRANSPORT]. The HTTP/QUIC mapping is 129 described in [QUIC-HTTP]. For a full description of HTTP/2, see 130 [RFC7540]. The description of HPACK is [RFC7541]. 132 QPACK reuses core concepts from HPACK, but is redesigned to allow 133 correctness in the presence of out-of-order delivery, with 134 flexibility for implementations to balance between resilience against 135 head-of-line blocking and optimal compression ratio. The design 136 goals are to closely approach the compression ratio of HPACK with 137 substantially less head-of-line blocking under the same loss 138 conditions. 140 2. Header Tables 142 Like HPACK, QPACK uses two tables for associating header fields to 143 indexes. The static table (see Section 2.1) is predefined and 144 contains common header fields (some of them with an empty value). 145 The dynamic table (see Section 2.2) built up over the course of the 146 connection and can be used by the encoder to index header fields 147 repeated in the encoded header lists. 149 Unlike in HPACK, entries in the QPACK static and dynamic tables are 150 addressed separately. The following sections describe how entries in 151 each table is addressed. 153 2.1. Static Table 155 The static table consists of a predefined static list of header 156 fields, each of which has a fixed index over time. Its entries are 157 defined in Appendix A of [RFC7541]. Note that because HPACK did not 158 use zero-based references, there is no value at index zero of the 159 static table. 161 2.2. Dynamic Table 163 The dynamic table consists of a list of header fields maintained in 164 first-in, first-out order. The dynamic table is initially empty. 165 Entries are added by instructions on the encoder stream (see 166 Section 5.2). 168 Before a new entry is added to the dynamic table, entries are evicted 169 from the end of the dynamic table until the size of the dynamic table 170 is less than or equal to (maximum size - new entry size) or until the 171 table is empty. 173 If the size of the new entry is less than or equal to the maximum 174 size, that entry is added to the table. It is an error to attempt to 175 add an entry that is larger than the maximum size; this MUST be 176 treated as a connection error of type 177 "HTTP_QPACK_DECOMPRESSION_FAILED". 179 A new entry can reference an entry in the dynamic table that will be 180 evicted when adding this new entry into the dynamic table. 181 Implementations are cautioned to avoid deleting the referenced name 182 if the referenced entry is evicted from the dynamic table prior to 183 inserting the new entry. 185 The dynamic table can contain duplicate entries (i.e., entries with 186 the same name and same value). Therefore, duplicate entries MUST NOT 187 be treated as an error by a decoder. 189 The encoder decides how to update the dynamic table and as such can 190 control how much memory is used by the dynamic table. To limit the 191 memory requirements of the decoder, the dynamic table size is 192 strictly bounded. 194 The decoder determines the maximum size that the encoder is permitted 195 to use for the dynamic table. In HTTP/QUIC, this value is determined 196 by the SETTINGS_HEADER_TABLE_SIZE setting (see Section 4). 198 An encoder can choose to use less capacity than this maximum size 199 (see Section 5.2.4), but the chosen size MUST stay lower than or 200 equal to the maximum set by the decoder. Whenever the maximum size 201 for the dynamic table is reduced, entries are evicted from the end of 202 the dynamic table until the size of the dynamic table is less than or 203 equal to the maximum size. 205 This mechanism can be used to completely clear entries from the 206 dynamic table by setting a maximum size of 0, which can subsequently 207 be restored. 209 2.2.1. Absolute and Relative Indexing 211 Each entry possesses both an absolute index which is fixed for the 212 lifetime of that entry and a relative index which changes over time 213 based on the context of the reference. The first entry inserted has 214 an absolute index of "1"; indices increase sequentially with each 215 insertion. 217 The relative index begins at zero and increases in the opposite 218 direction from the absolute index. Determining which entry has a 219 relative index of "0" depends on the context of the reference. 221 On the encoder stream, a relative index of "0" always refers to the 222 most recently inserted value in the dynamic table. Note that this 223 means the entry referenced by a given relative index will change 224 while interpreting instructions on the encoder stream. 226 +---+---------------+-----------+ 227 | n | ... | d + 1 | Absolute Index 228 + - +---------------+ - - - - - + 229 | 0 | ... | n - d - 1 | Relative Index 230 +---+---------------+-----------+ 231 ^ | 232 | V 233 Insertion Point Dropping Point 235 n = count of entries inserted 236 d = count of entries dropped 238 Example Dynamic Table Indexing - Control Stream 240 Because frames from request streams can be delivered out of order 241 with instructions on the encoder stream, relative indices are 242 relative to the Base Index at the beginning of the header block (see 243 Section 5.4.1). The Base Index is an absolute index. When 244 interpreting the rest of the frame, the entry identified by Base 245 Index has a relative index of zero. The relative indices of entries 246 do not change while interpreting headers on a request or push stream. 248 Base Index 249 | 250 V 251 +---+-----+-----+-----+-------+ 252 | n | n-1 | n-2 | ... | d+1 | Absolute Index 253 +---+-----+ - +-----+ - + 254 | 0 | ... | n-d-3 | Relative Index 255 +-----+-----+-------+ 257 n = count of entries inserted 258 d = count of entries dropped 260 Example Dynamic Table Indexing - Request Stream 262 2.2.2. Post-Base Indexing 264 A header block on the request stream can reference entries added 265 after the entry identified by the Base Index. This allows an encoder 266 to process a header block in a single pass and include references to 267 entries added while processing this (or other) header blocks. Newly 268 added entries are referenced using Post-Base instructions. Indices 269 for Post-Base instructions increase in the same direction as absolute 270 indices, but the zero value is one higher than the Base Index. 272 Base Index 273 | 274 V 275 +---+-----+-----+-----+-----+ 276 | n | n-1 | n-2 | ... | d+1 | Absolute Index 277 +---+-----+-----+-----+-----+ 278 | 1 | 0 | Post-Base Index 279 +---+-----+ 281 n = count of entries inserted 282 d = count of entries dropped 284 Dynamic Table Indexing - Post-Base References 286 If the decoder encounters a reference to an entry which has already 287 been dropped from the table or which is greater than the declared 288 Largest Reference (see Section 5.4.1), this MUST be treated as a 289 stream error of type "HTTP_QPACK_DECOMPRESSION_FAILED" error code. 290 If this reference occurs on the encoder stream, this MUST be treated 291 as a session error. 293 2.3. Avoiding Head-of-Line Blocking in HTTP/QUIC 295 Because QUIC does not guarantee order between data on different 296 streams, a header block might reference an entry in the dynamic table 297 that has not yet been received. 299 Each header block contains a Largest Reference which identifies the 300 table state necessary for decoding. If the greatest absolute index 301 in the dynamic table is less than the value of the Largest Reference, 302 the stream is considered "blocked." While blocked, header field data 303 should remain in the blocked stream's flow control window. When the 304 Largest Reference is zero, the frame contains no references to the 305 dynamic table and can always be processed immediately. A stream 306 becomes unblocked when the greatest absolute index in the dynamic 307 table becomes greater than or equal to the Largest Reference for all 308 header blocks the decoder has started reading from the stream. If a 309 decoder encounters a header block where the actual largest reference 310 is not equal to the largest reference declared in the prefix, it MAY 311 treat this as a stream error of type HTTP_QPACK_DECOMPRESSION_FAILED. 313 A decoder can permit the possibility of blocked streams by setting 314 SETTINGS_QPACK_BLOCKED_STREAMS to a non-zero value (see Section 4). 315 This setting specifies an upper bound on the number of streams which 316 can be blocked. 318 An encoder can decide whether to risk having a stream become blocked. 319 If permitted by the value of SETTINGS_QPACK_BLOCKED_STREAMS, 320 compression efficiency can be improved by referencing dynamic table 321 entries that are still in transit, but if there is loss or reordering 322 the stream can become blocked at the decoder. An encoder avoids the 323 risk of blocking by only referencing dynamic table entries which have 324 been acknowledged, but this means using literals. Since literals 325 make the header block larger, this can result in the encoder becoming 326 blocked on congestion or flow control limits. 328 An encoder MUST limit the number of streams which could become 329 blocked to the value of SETTINGS_QPACK_BLOCKED_STREAMS at all times. 330 Note that the decoder might not actually become blocked on every 331 stream which risks becoming blocked. If the decoder encounters more 332 blocked streams than it promised to support, it SHOULD treat this as 333 a stream error of type HTTP_QPACK_DECOMPRESSION_FAILED. 335 2.3.1. State Synchronization 337 The decoder stream signals key events at the decoder that permit the 338 encoder to track the decoder's state. These events are: 340 o Complete processing of a header block 342 o Abandonment of a stream which might have remaining header blocks 344 o Receipt of new dynamic table entries 346 Regardless of whether a header block contained blocking references, 347 the knowledge that it has been processed permits the encoder to evict 348 entries to which no unacknowledged references remain; see 349 Section 7.3.1. When a stream is reset or abandoned, the indication 350 that these header blocks will never be processed serves a similar 351 function; see Section 5.3.3. 353 For the encoder to identify which dynamic table entries can be safely 354 used without a stream becoming blocked, the encoder tracks the 355 absolute index of the decoder's Largest Known Received entry. 357 When blocking references are permitted, the encoder uses 358 acknowledgement of header blocks to identify the Largest Known 359 Received index, as described in Section 5.3.2. 361 To acknowledge dynamic table entries which are not referenced by 362 header blocks, for example because the encoder or the decoder have 363 chosen not to risk blocked streams, the decoder sends a Table State 364 Synchronize instruction (see Section 5.3.1). 366 3. Conventions and Definitions 368 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 369 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 370 "OPTIONAL" in this document are to be interpreted as described in BCP 371 14 [RFC2119] [RFC8174] when, and only when, they appear in all 372 capitals, as shown here. 374 Definitions of terms that are used in this document: 376 Header: A name-value pair sent as part of an HTTP message. 378 Header set: The full collection of headers associated with an HTTP 379 message. 381 Header block: The compressed representation of a header set. 383 Encoder: An implementation which transforms a header set into a 384 header block. 386 Decoder: An implementation which transforms a header block into a 387 header set. 389 QPACK is a name, not an acronym. 391 3.1. Notational Conventions 393 Diagrams use the format described in Section 3.1 of [RFC2360], with 394 the following additional conventions: 396 x (A) Indicates that x is A bits long 398 x (A+) Indicates that x uses the prefixed integer encoding defined 399 in Section 5.1 of [RFC7541], beginning with an A-bit prefix. 401 x ... Indicates that x is variable-length and extends to the end of 402 the region. 404 4. Configuration 406 QPACK defines two settings which are included in the HTTP/QUIC 407 SETTINGS frame. 409 SETTINGS_HEADER_TABLE_SIZE (0x1): An integer with a maximum value of 410 2^30 - 1. The default value is 4,096 bytes. See Section 2.2 for 411 usage. 413 SETTINGS_QPACK_BLOCKED_STREAMS (0x7): An integer with a maximum 414 value of 2^16 - 1. The default value is 100. See Section 2.3. 416 5. Wire Format 418 QPACK instructions occur in three locations, each of which uses a 419 separate instruction space: 421 o The encoder stream is a unidirectional stream of type "0x48" 422 (ASCII 'H') which carries table updates from encoder to decoder. 423 Instructions on this stream modify the dynamic table state without 424 generating output to any particular request. 426 o The decoder stream is a unidirectional stream of type "0x68" 427 (ASCII 'h') which carries acknowledgements of table modifications 428 and header processing from decoder to encoder. 430 o Finally, the contents of HEADERS and PUSH_PROMISE frames on 431 request streams and push streams reference the QPACK table state. 433 There MUST be exactly one of each unidirectional stream type in each 434 direction. Receipt of a second instance of either stream type MUST 435 be treated as a connection error of HTTP_WRONG_STREAM_COUNT. Closure 436 of either unidirectional stream MUST be treated as a connection error 437 of type HTTP_CLOSED_CRITICAL_STREAM. 439 This section describes the instructions which are possible on each 440 stream type. 442 All table updates occur on the encoder stream. Request streams and 443 push streams only carry header blocks that do not modify the state of 444 the table. 446 5.1. Primitives 448 5.1.1. Prefixed Integers 450 The prefixed integer from Section 5.1 of [RFC7541] is used heavily 451 throughout this document. The format from [RFC7541] is used 452 unmodified. 454 5.1.2. String Literals 456 The string literal defined by Section 5.2 of [RFC7541] is also used 457 throughout. This string format includes optional Huffman encoding. 459 HPACK defines string literals to begin on a byte boundary. They 460 begin with a single flag (indicating whether the string is Huffman- 461 coded), followed by the Length encoded as a 7-bit prefix integer, and 462 finally Length octets of data. When Huffman encoding is enabled, the 463 Huffman table from Appendix B of [RFC7541] is used without 464 modification. 466 This document expands the definition of string literals and permits 467 them to begin other than on a byte boundary. An "N-bit prefix string 468 literal" begins with the same Huffman flag, followed by the length 469 encoded as an (N-1)-bit prefix integer. The remainder of the string 470 literal is unmodified. 472 A string literal without a prefix length noted is an 8-bit prefix 473 string literal and follows the definitions in [RFC7541] without 474 modification. 476 5.2. QPACK Encoder Stream 478 Table updates can add a table entry, possibly using existing entries 479 to avoid transmitting redundant information. The name can be 480 transmitted as a reference to an existing entry in the static or the 481 dynamic table or as a string literal. For entries which already 482 exist in the dynamic table, the full entry can also be used by 483 reference, creating a duplicate entry. 485 The contents of the encoder stream are an unframed sequence of the 486 following instructions. 488 5.2.1. Insert With Name Reference 490 An addition to the header table where the header field name matches 491 the header field name of an entry stored in the static table or the 492 dynamic table starts with the '1' one-bit pattern. The "S" bit 493 indicates whether the reference is to the static (S=1) or dynamic 494 (S=0) table. The 6-bit prefix integer (see Section 5.1 of [RFC7541]) 495 that follows is used to locate the table entry for the header name. 496 When S=1, the number represents the static table index; when S=0, the 497 number is the relative index of the entry in the dynamic table. 499 The header name reference is followed by the header field value 500 represented as a string literal (see Section 5.2 of [RFC7541]). 502 0 1 2 3 4 5 6 7 503 +---+---+---+---+---+---+---+---+ 504 | 1 | S | Name Index (6+) | 505 +---+---+-----------------------+ 506 | H | Value Length (7+) | 507 +---+---------------------------+ 508 | Value String (Length octets) | 509 +-------------------------------+ 511 Insert Header Field -- Indexed Name 513 5.2.2. Insert Without Name Reference 515 An addition to the header table where both the header field name and 516 the header field value are represented as string literals (see 517 Section 5.1) starts with the '01' two-bit pattern. 519 The name is represented as a 6-bit prefix string literal, while the 520 value is represented as an 8-bit prefix string literal. 522 0 1 2 3 4 5 6 7 523 +---+---+---+---+---+---+---+---+ 524 | 0 | 1 | H | Name Length (5+) | 525 +---+---+---+-------------------+ 526 | Name String (Length octets) | 527 +---+---------------------------+ 528 | H | Value Length (7+) | 529 +---+---------------------------+ 530 | Value String (Length octets) | 531 +-------------------------------+ 533 Insert Header Field -- New Name 535 5.2.3. Duplicate 537 Duplication of an existing entry in the dynamic table starts with the 538 '000' three-bit pattern. The relative index of the existing entry is 539 represented as an integer with a 5-bit prefix. 541 0 1 2 3 4 5 6 7 542 +---+---+---+---+---+---+---+---+ 543 | 0 | 0 | 0 | Index (5+) | 544 +---+---+---+-------------------+ 546 Figure 1: Duplicate 548 The existing entry is re-inserted into the dynamic table without 549 resending either the name or the value. This is useful to mitigate 550 the eviction of older entries which are frequently referenced, both 551 to avoid the need to resend the header and to avoid the entry in the 552 table blocking the ability to insert new headers. 554 5.2.4. Dynamic Table Size Update 556 An encoder informs the decoder of a change to the size of the dynamic 557 table using an instruction which begins with the '001' three-bit 558 pattern. The new maximum table size is represented as an integer 559 with a 5-bit prefix (see Section 5.1 of [RFC7541]). 561 0 1 2 3 4 5 6 7 562 +---+---+---+---+---+---+---+---+ 563 | 0 | 0 | 1 | Max size (5+) | 564 +---+---+---+-------------------+ 566 Figure 2: Maximum Dynamic Table Size Change 568 The new maximum size MUST be lower than or equal to the limit 569 determined by the protocol using QPACK. A value that exceeds this 570 limit MUST be treated as a decoding error. In HTTP/QUIC, this limit 571 is the value of the SETTINGS_HEADER_TABLE_SIZE parameter (see 572 Section 4) received from the decoder. 574 Reducing the maximum size of the dynamic table can cause entries to 575 be evicted (see Section 4.3 of [RFC7541]). This MUST NOT cause the 576 eviction of entries with outstanding references (see Section 7.3). 577 Changing the size of the dynamic table is not acknowledged as this 578 instruction does not insert an entry. 580 5.3. QPACK Decoder Stream 582 The decoder stream carries information used to ensure consistency of 583 the dynamic table. Information is sent from the QPACK decoder to the 584 QPACK encoder; that is, the server informs the client about the 585 processing of the client's header blocks and table updates, and the 586 client informs the server about the processing of the server's header 587 blocks and table updates. 589 The contents of the decoder stream are an unframed sequence of the 590 following instructions. 592 5.3.1. Table State Synchronize 594 The Table State Synchronize instruction begins with the '00' two-bit 595 pattern. The instruction specifies the total number of dynamic table 596 inserts and duplications since the last Table State Synchronize or 597 Header Acknowledgement that increased the Largest Known Received 598 dynamic table entry. This is encoded as a 6-bit prefix integer. The 599 encoder uses this value to determine which table entries might cause 600 a stream to become blocked, as described in Section 2.3.1. 602 0 1 2 3 4 5 6 7 603 +---+---+---+---+---+---+---+---+ 604 | 0 | 0 | Insert Count (6+) | 605 +---+---+-----------------------+ 607 Figure 3: Table State Synchronize 609 A decoder chooses when to emit Table State Synchronize instructions. 610 Emitting a Table State Synchronize after adding each new dynamic 611 table entry will provide the most timely feedback to the encoder, but 612 could be redundant with other decoder feedback. By delaying a 613 Table State Synchronize, a decoder might be able to coalesce multiple 614 Table State Synchronize instructions, or replace them entirely with 615 Header Acknowledgements. However, delaying too long may lead to 616 compression inefficiencies if the encoder waits for an entry to be 617 acknowledged before using it. 619 5.3.2. Header Acknowledgement 621 After processing a header block whose declared Largest Reference is 622 not zero, the decoder emits a Header Acknowledgement instruction on 623 the decoder stream. The instruction begins with the '1' one-bit 624 pattern and includes the request stream's stream ID, encoded as a 625 7-bit prefix integer. It is used by the peer's QPACK encoder to know 626 when it is safe to evict an entry. 628 The same Stream ID can be identified multiple times, as multiple 629 header blocks can be sent on a single stream in the case of 630 intermediate responses, trailers, and pushed requests. Since header 631 frames on each stream are received and processed in order, this gives 632 the encoder precise feedback on which header blocks within a stream 633 have been fully processed. 635 0 1 2 3 4 5 6 7 636 +---+---+---+---+---+---+---+---+ 637 | 1 | Stream ID (7+) | 638 +---+---------------------------+ 640 Figure 4: Header Acknowledgement 642 When blocking references are permitted, the encoder uses 643 acknowledgement of header blocks to update the Largest Known Received 644 index. If a header block was potentially blocking, the 645 acknowledgement implies that the decoder has received all dynamic 646 table state necessary to process the header block. If the Largest 647 Reference of an acknowledged header block was greater than the 648 encoder's current Largest Known Received index, the block's Largest 649 Reference becomes the new Largest Known Received. 651 5.3.3. Stream Cancellation 653 A stream that is reset might have multiple outstanding header blocks. 654 A decoder that receives a stream reset before the end of a stream 655 generates a Stream Cancellation instruction on the decoder stream. 656 Similarly, a decoder that abandons reading of a stream needs to 657 signal this using the Stream Cancellation instruction. This signals 658 to the encoder that all references to the dynamic table on that 659 stream are no longer outstanding. 661 An encoder cannot infer from this instruction that any updates to the 662 dynamic table have been received. 664 The instruction begins with the '01' two-bit pattern. The 665 instruction includes the stream ID of the affected stream - a request 666 or push stream - encoded as a 6-bit prefix integer. 668 0 1 2 3 4 5 6 7 669 +---+---+---+---+---+---+---+---+ 670 | 0 | 1 | Stream ID (6+) | 671 +---+---+-----------------------+ 673 Figure 5: Stream Cancellation 675 5.4. Request and Push Streams 677 HEADERS and PUSH_PROMISE frames on request and push streams reference 678 the dynamic table in a particular state without modifying it. Frames 679 on these streams emit the headers for an HTTP request or response. 681 5.4.1. Header Data Prefix 683 Header data is prefixed with two integers, "Largest Reference" and 684 "Base Index". 686 0 1 2 3 4 5 6 7 687 +---+---+---+---+---+---+---+---+ 688 | Largest Reference (8+) | 689 +---+---------------------------+ 690 | S | Delta Base Index (7+) | 691 +---+---------------------------+ 692 | Compressed Headers ... 693 +-------------------------------+ 695 Figure 6: Frame Payload 697 "Largest Reference" identifies the largest absolute dynamic index 698 referenced in the block. Blocking decoders use the Largest Reference 699 to determine when it is safe to process the rest of the block. 701 "Base Index" is used to resolve references in the dynamic table as 702 described in Section 2.2.1. 704 To save space, Base Index is encoded relative to Largest Reference 705 using a one-bit sign and the "Delta Base Index" value. A sign bit of 706 0 indicates that the Base Index has an absolute index that is greater 707 than or equal to the Largest Reference; the value of Delta Base Index 708 is added to the Largest Reference to determine the absolute value of 709 the Base Index. A sign bit of 1 indicates that the Base Index is 710 less than the Largest Reference. That is: 712 if sign == 0: 713 baseIndex = largestReference + deltaBaseIndex 714 else: 715 baseIndex = largestReference - deltaBaseIndex 717 A single-pass encoder is expected to determine the absolute value of 718 Base Index before encoding a header block. If the encoder inserted 719 entries in the dynamic table while encoding the header block, Largest 720 Reference will be greater than Base Index, so the encoded difference 721 is negative and the sign bit is set to 1. If the header block did 722 not reference the most recent entry in the table and did not insert 723 any new entries, Base Index will be greater than the Largest 724 Reference, so the delta will be positive and the sign bit is set to 725 0. 727 An encoder that produces table updates before encoding a header block 728 might set Largest Reference and Base Index to the same value. When 729 Largest Reference and Base Index are equal, the Delta Base Index is 730 encoded with a zero sign bit. A sign bit set to 1 when the Delta 731 Base Index is 0 MUST be treated as a decoder error. 733 A header block that does not reference the dynamic table can use any 734 value for Base Index; setting both Largest Reference and Base Index 735 to zero is the most efficient encoding. 737 5.4.2. Instructions 739 5.4.2.1. Indexed Header Field 741 An indexed header field representation identifies an entry in either 742 the static table or the dynamic table and causes that header field to 743 be added to the decoded header list, as described in Section 3.2 of 744 [RFC7541]. 746 0 1 2 3 4 5 6 7 747 +---+---+---+---+---+---+---+---+ 748 | 1 | S | Index (6+) | 749 +---+---+-----------------------+ 751 Indexed Header Field 753 If the entry is in the static table, or in the dynamic table with an 754 absolute index less than or equal to Base Index, this representation 755 starts with the '1' 1-bit pattern, followed by the "S" bit indicating 756 whether the reference is into the static (S=1) or dynamic (S=0) 757 table. Finally, the relative index of the matching header field is 758 represented as an integer with a 6-bit prefix (see Section 5.1 of 759 [RFC7541]). 761 5.4.2.2. Indexed Header Field With Post-Base Index 763 If the entry is in the dynamic table with an absolute index greater 764 than Base Index, the representation starts with the '0001' 4-bit 765 pattern, followed by the post-base index (see Section 2.2.2) of the 766 matching header field, represented as an integer with a 4-bit prefix 767 (see Section 5.1 of [RFC7541]). 769 0 1 2 3 4 5 6 7 770 +---+---+---+---+---+---+---+---+ 771 | 0 | 0 | 0 | 1 | Index (4+) | 772 +---+---+---+---+---------------+ 774 Indexed Header Field with Post-Base Index 776 5.4.2.3. Literal Header Field With Name Reference 778 A literal header field with a name reference represents a header 779 where the header field name matches the header field name of an entry 780 stored in the static table or the dynamic table. 782 If the entry is in the static table, or in the dynamic table with an 783 absolute index less than or equal to Base Index, this representation 784 starts with the '01' two-bit pattern. If the entry is in the dynamic 785 table with an absolute index greater than Base Index, the 786 representation starts with the '0000' four-bit pattern. 788 The following bit, 'N', indicates whether an intermediary is 789 permitted to add this header to the dynamic header table on 790 subsequent hops. When the 'N' bit is set, the encoded header MUST 791 always be encoded with a literal representation. In particular, when 792 a peer sends a header field that it received represented as a literal 793 header field with the 'N' bit set, it MUST use a literal 794 representation to forward this header field. This bit is intended 795 for protecting header field values that are not to be put at risk by 796 compressing them (see Section 7.1 of [RFC7541] for more details). 798 0 1 2 3 4 5 6 7 799 +---+---+---+---+---+---+---+---+ 800 | 0 | 1 | N | S |Name Index (4+)| 801 +---+---+---+---+---------------+ 802 | H | Value Length (7+) | 803 +---+---------------------------+ 804 | Value String (Length octets) | 805 +-------------------------------+ 807 Literal Header Field With Name Reference 809 For entries in the static table or in the dynamic table with an 810 absolute index less than or equal to Base Index, the header field 811 name is represented using the relative index of that entry, which is 812 represented as an integer with a 4-bit prefix (see Section 5.1 of 813 [RFC7541]). The "S" bit indicates whether the reference is to the 814 static (S=1) or dynamic (S=0) table. 816 5.4.2.4. Literal Header Field With Post-Base Name Reference 818 For entries in the dynamic table with an absolute index greater than 819 Base Index, the header field name is represented using the post-base 820 index of that entry (see Section 2.2.2) encoded as an integer with a 821 3-bit prefix. 823 0 1 2 3 4 5 6 7 824 +---+---+---+---+---+---+---+---+ 825 | 0 | 0 | 0 | 0 | N |NameIdx(3+)| 826 +---+---+---+---+---+-----------+ 827 | H | Value Length (7+) | 828 +---+---------------------------+ 829 | Value String (Length octets) | 830 +-------------------------------+ 832 Literal Header Field With Post-Base Name Reference 834 5.4.2.5. Literal Header Field Without Name Reference 836 An addition to the header table where both the header field name and 837 the header field value are represented as string literals (see 838 Section 5.1) starts with the '001' three-bit pattern. 840 The fourth bit, 'N', indicates whether an intermediary is permitted 841 to add this header to the dynamic header table on subsequent hops. 842 When the 'N' bit is set, the encoded header MUST always be encoded 843 with a literal representation. In particular, when a peer sends a 844 header field that it received represented as a literal header field 845 with the 'N' bit set, it MUST use a literal representation to forward 846 this header field. This bit is intended for protecting header field 847 values that are not to be put at risk by compressing them (see 848 Section 7.1 of [RFC7541] for more details). 850 The name is represented as a 4-bit prefix string literal, while the 851 value is represented as an 8-bit prefix string literal. 853 0 1 2 3 4 5 6 7 854 +---+---+---+---+---+---+---+---+ 855 | 0 | 0 | 1 | N | H |NameLen(3+)| 856 +---+---+---+---+---+-----------+ 857 | Name String (Length octets) | 858 +---+---------------------------+ 859 | H | Value Length (7+) | 860 +---+---------------------------+ 861 | Value String (Length octets) | 862 +-------------------------------+ 864 Literal Header Field Without Name Reference 866 6. Error Handling 868 The following error code is defined for HTTP/QUIC to indicate all 869 failures of QPACK which prevent the stream or connection from 870 continuing: 872 HTTP_QPACK_DECOMPRESSION_FAILED (0x06): QPACK failed to decompress a 873 frame and cannot continue. 875 7. Encoding Strategies 877 7.1. Single Pass Encoding 879 An encoder making a single pass over a list of headers must choose 880 Base Index before knowing Largest Reference. When trying to 881 reference a header inserted to the table after encoding has begun, 882 the entry is encoded with different instructions that tell the 883 decoder to use an absolute index greater than the Base Index. 885 7.2. Preventing Eviction Races 887 Due to out-of-order arrival, QPACK's eviction algorithm requires 888 changes (relative to HPACK) to avoid the possibility that an indexed 889 representation is decoded after the referenced entry has already been 890 evicted. QPACK employs a two-phase eviction algorithm, in which the 891 encoder will not evict entries that have outstanding (unacknowledged) 892 references. 894 7.3. Reference Tracking 896 An encoder MUST ensure that a header block which references a dynamic 897 table entry is not received by the decoder after the referenced entry 898 has already been evicted. An encoder also respects the limit set by 899 the decoder on the number of streams that are allowed to become 900 blocked. Even if the decoder is willing to tolerate blocked streams, 901 the encoder might choose to avoid them in certain cases. 903 In order to enable this, the encoder will need to track outstanding 904 (unacknowledged) header blocks and table updates using feedback 905 received from the decoder. 907 7.3.1. Blocked Eviction 909 The encoder MUST NOT permit an entry to be evicted while a reference 910 to that entry remains unacknowledged. If a new header to be inserted 911 into the dynamic table would cause the eviction of such an entry, the 912 encoder MUST NOT emit the insert instruction until the reference has 913 been processed by the decoder and acknowledged. 915 The encoder can emit a literal representation for the new header in 916 order to avoid encoding delays, and MAY insert the header into the 917 table later if desired. 919 To ensure that the blocked eviction case is rare, references to the 920 oldest entries in the dynamic table SHOULD be avoided. When one of 921 the oldest entries in the table is still actively used for 922 references, the encoder SHOULD emit an Duplicate representation 923 instead (see Section 5.2.3). 925 7.3.2. Blocked Decoding 927 For header blocks encoded in non-blocking mode, the encoder needs to 928 forego indexed representations that refer to table updates which have 929 not yet been acknowledged with Section 5.3. Since all table updates 930 are processed in sequence on the encoder stream, an index into the 931 dynamic table is sufficient to track which entries have been 932 acknowledged. 934 To track blocked streams, the necessary Base Index value for each 935 stream can be used. Whenever the decoder processes a table update, 936 it can begin decoding any blocked streams that now have their 937 dependencies satisfied. 939 7.4. Speculative table updates 941 Implementations can _speculatively_ send header frames on the HTTP 942 Control Streams which are not needed for any current HTTP request or 943 response. Such headers could be used strategically to improve 944 performance. For instance, the encoder might decide to _refresh_ by 945 sending Duplicate representations for popular header fields 946 (Section 5.2.3), ensuring they have small indices and hence minimal 947 size on the wire. 949 7.5. Sample One Pass Encoding Algorithm 951 Pseudo-code for single pass encoding, excluding handling of 952 duplicates, non-blocking mode, and reference tracking. 954 baseIndex = dynamicTable.baseIndex 955 largestReference = 0 956 for header in headers: 957 staticIdx = staticTable.getIndex(header) 958 if staticIdx: 959 encodeIndexReference(streamBuffer, staticIdx) 960 continue 962 dynamicIdx = dynamicTable.getIndex(header) 963 if !dynamicIdx: 964 # No matching entry. Either insert+index or encode literal 965 nameIdx = getNameIndex(header) 966 if shouldIndex(header) and dynamicTable.canIndex(header): 967 encodeLiteralWithIncrementalIndex(controlBuffer, nameIdx, 968 header) 969 dynamicTable.add(header) 970 dynamicIdx = dynamicTable.baseIndex 972 if !dynamicIdx: 973 # Couldn't index it, literal 974 if nameIdx <= staticTable.size: 975 encodeLiteral(streamBuffer, nameIndex, header) 976 else: 977 # encode literal, possibly with nameIdx above baseIndex 978 encodeDynamicLiteral(streamBuffer, nameIndex, baseIndex, 979 header) 980 largestReference = max(largestReference, 981 dynamicTable.toAbsolute(nameIdx)) 982 else: 983 # Dynamic index reference 984 assert(dynamicIdx) 985 largestReference = max(largestReference, dynamicIdx) 986 # Encode dynamicIdx, possibly with dynamicIdx above baseIndex 987 encodeDynamicIndexReference(streamBuffer, dynamicIdx, 988 baseIndex) 990 # encode the prefix 991 encodeInteger(prefixBuffer, 0x00, largestReference, 8) 992 if baseIndex >= largestReference: 993 encodeInteger(prefixBuffer, 0, baseIndex - largestReference, 7) 994 else: 995 encodeInteger(prefixBuffer, 0x80, 996 largestReference - baseIndex, 7) 998 return controlBuffer, prefixBuffer + streamBuffer 1000 8. Security Considerations 1002 TBD. 1004 9. IANA Considerations 1006 9.1. Settings Registration 1008 This document creates two new settings in the "HTTP/QUIC Settings" 1009 registry established in [QUIC-HTTP]. 1011 The entries in the following table are registered by this document. 1013 +-----------------------+------+---------------+ 1014 | Setting Name | Code | Specification | 1015 +-----------------------+------+---------------+ 1016 | HEADER_TABLE_SIZE | 0x1 | Section 4 | 1017 | | | | 1018 | QPACK_BLOCKED_STREAMS | 0x7 | Section 4 | 1019 +-----------------------+------+---------------+ 1021 9.2. Stream Type Registration 1023 This document creates two new settings in the "HTTP/QUIC Stream Type" 1024 registry established in [QUIC-HTTP]. 1026 The entries in the following table are registered by this document. 1028 +----------------------+------+---------------+--------+ 1029 | Stream Type | Code | Specification | Sender | 1030 +----------------------+------+---------------+--------+ 1031 | QPACK Encoder Stream | 0x48 | Section 5 | Both | 1032 | | | | | 1033 | QPACK Decoder Stream | 0x68 | Section 5 | Both | 1034 +----------------------+------+---------------+--------+ 1036 9.3. Error Code Registration 1038 This document establishes one new error code in the "HTTP/QUIC Error 1039 Code" registry established in [QUIC-HTTP]. 1041 Name: HTTP_QPACK_DECOMPRESSION_FAILED 1043 Code: 0x06 1045 Description: QPACK failed to interpret an instruction and cannot 1046 continue. 1048 10. References 1050 10.1. Normative References 1052 [QUIC-HTTP] 1053 Bishop, M., Ed., "Hypertext Transfer Protocol (HTTP) over 1054 QUIC", draft-ietf-quic-http-14 (work in progress), August 1055 2018. 1057 [QUIC-TRANSPORT] 1058 Iyengar, J., Ed. and M. Thomson, Ed., "QUIC: A UDP-Based 1059 Multiplexed and Secure Transport", draft-ietf-quic- 1060 transport-13 (work in progress), August 2018. 1062 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1063 Requirement Levels", BCP 14, RFC 2119, 1064 DOI 10.17487/RFC2119, March 1997, 1065 . 1067 [RFC7541] Peon, R. and H. Ruellan, "HPACK: Header Compression for 1068 HTTP/2", RFC 7541, DOI 10.17487/RFC7541, May 2015, 1069 . 1071 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 1072 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 1073 May 2017, . 1075 10.2. Informative References 1077 [RFC2360] Scott, G., "Guide for Internet Standards Writers", BCP 22, 1078 RFC 2360, DOI 10.17487/RFC2360, June 1998, 1079 . 1081 [RFC7540] Belshe, M., Peon, R., and M. Thomson, Ed., "Hypertext 1082 Transfer Protocol Version 2 (HTTP/2)", RFC 7540, 1083 DOI 10.17487/RFC7540, May 2015, 1084 . 1086 10.3. URIs 1088 [1] https://mailarchive.ietf.org/arch/search/?email_list=quic 1090 [2] https://github.com/quicwg 1092 [3] https://github.com/quicwg/base-drafts/labels/-qpack 1094 Appendix A. Change Log 1096 *RFC Editor's Note:* Please remove this section prior to 1097 publication of a final version of this document. 1099 A.1. Since draft-ietf-quic-qpack-01 1101 o Only header blocks that reference the dynamic table are 1102 acknowledged (#1603, #1605) 1104 A.2. Since draft-ietf-quic-qpack-00 1106 o Renumbered instructions for consistency (#1471, #1472) 1108 o Decoder is allowed to validate largest reference (#1404, #1469) 1110 o Header block acknowledgments also acknowledge the associated 1111 largest reference (#1370, #1400) 1113 o Added an acknowledgment for unread streams (#1371, #1400) 1115 o Removed framing from encoder stream (#1361,#1467) 1117 o Control streams use typed unidirectional streams rather than fixed 1118 stream IDs (#910,#1359) 1120 A.3. Since draft-ietf-quic-qcram-00 1122 o Separate instruction sets for table updates and header blocks 1123 (#1235, #1142, #1141) 1125 o Reworked indexing scheme (#1176, #1145, #1136, #1130, #1125, 1126 #1314) 1128 o Added mechanisms that support one-pass encoding (#1138, #1320) 1130 o Added a setting to control the number of blocked decoders (#238, 1131 #1140, #1143) 1133 o Moved table updates and acknowledgments to dedicated streams 1134 (#1121, #1122, #1238) 1136 Acknowledgments 1138 This draft draws heavily on the text of [RFC7541]. The indirect 1139 input of those authors is gratefully acknowledged, as well as ideas 1140 from: 1142 o Ryan Hamilton 1144 o Patrick McManus 1146 o Kazuho Oku 1148 o Biren Roy 1150 o Ian Swett 1152 o Dmitri Tikhonov 1154 Buck's contribution was supported by Google during his employment 1155 there. 1157 A substantial portion of Mike's contribution was supported by 1158 Microsoft during his employment there. 1160 Authors' Addresses 1162 Charles 'Buck' Krasic 1163 Netflix 1165 Email: ckrasic@netflix.com 1167 Mike Bishop 1168 Akamai Technologies 1170 Email: mbishop@evequefou.be 1172 Alan Frindell (editor) 1173 Facebook 1175 Email: afrind@fb.com