idnits 2.17.1 draft-ietf-quic-qpack-01.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 (June 28, 2018) is 2100 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 1066 -- Looks like a reference, but probably isn't: '2' on line 1068 -- Looks like a reference, but probably isn't: '3' on line 1070 == Outdated reference: A later version (-34) exists of draft-ietf-quic-http-13 == Outdated reference: A later version (-34) exists of draft-ietf-quic-transport-12 -- 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: December 30, 2018 Akamai Technologies 6 A. Frindell, Ed. 7 Facebook 8 June 28, 2018 10 QPACK: Header Compression for HTTP over QUIC 11 draft-ietf-quic-qpack-01 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 December 30, 2018. 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 . . . . . . . . . . . . . . . . . . . . . . . . 3 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 . . . . . . . . . . . . . . . . . 8 73 3.1. Notational Conventions . . . . . . . . . . . . . . . . . 9 74 4. Configuration . . . . . . . . . . . . . . . . . . . . . . . . 9 75 5. Wire Format . . . . . . . . . . . . . . . . . . . . . . . . . 9 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 . . . . . . . . . . . . 11 82 5.2.3. Duplicate . . . . . . . . . . . . . . . . . . . . . . 12 83 5.2.4. Dynamic Table Size Update . . . . . . . . . . . . . . 12 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 . . . . . . . . . . . . . . . . . 14 88 5.4. Request and Push Streams . . . . . . . . . . . . . . . . 15 89 5.4.1. Header Data Prefix . . . . . . . . . . . . . . . . . 15 90 5.4.2. Instructions . . . . . . . . . . . . . . . . . . . . 16 91 6. Encoding Strategies . . . . . . . . . . . . . . . . . . . . . 19 92 6.1. Single Pass Encoding . . . . . . . . . . . . . . . . . . 19 93 6.2. Preventing Eviction Races . . . . . . . . . . . . . . . . 19 94 6.3. Reference Tracking . . . . . . . . . . . . . . . . . . . 19 95 6.3.1. Blocked Eviction . . . . . . . . . . . . . . . . . . 20 96 6.3.2. Blocked Decoding . . . . . . . . . . . . . . . . . . 20 97 6.4. Speculative table updates . . . . . . . . . . . . . . . . 20 98 6.5. Sample One Pass Encoding Algorithm . . . . . . . . . . . 20 99 7. Security Considerations . . . . . . . . . . . . . . . . . . . 22 100 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 22 101 8.1. Settings Registration . . . . . . . . . . . . . . . . . . 22 102 8.2. Stream Type Registration . . . . . . . . . . . . . . . . 22 103 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 22 104 9.1. Normative References . . . . . . . . . . . . . . . . . . 22 105 9.2. Informative References . . . . . . . . . . . . . . . . . 23 106 9.3. URIs . . . . . . . . . . . . . . . . . . . . . . . . . . 23 107 Appendix A. Change Log . . . . . . . . . . . . . . . . . . . . . 23 108 A.1. Since draft-ietf-quic-qpack-00 . . . . . . . . . . . . . 23 109 A.2. Since draft-ietf-quic-qcram-00 . . . . . . . . . . . . . 24 110 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 24 111 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 25 113 1. Introduction 115 The QUIC transport protocol was designed from the outset to support 116 HTTP semantics, and its design subsumes many of the features of 117 HTTP/2. HTTP/2 used HPACK ([RFC7541]) for header compression, but 118 QUIC's stream multiplexing comes into some conflict with HPACK. A 119 key goal of the design of QUIC is to improve stream multiplexing 120 relative to HTTP/2 by reducing head-of-line blocking. If HPACK were 121 used for HTTP/QUIC, it would induce head-of-line blocking due to 122 built-in assumptions of a total ordering across frames on all 123 streams. 125 QUIC is described in [QUIC-TRANSPORT]. The HTTP/QUIC mapping is 126 described in [QUIC-HTTP]. For a full description of HTTP/2, see 127 [RFC7540]. The description of HPACK is [RFC7541], with important 128 terminology in Section 1.3. 130 QPACK reuses core concepts from HPACK, but is redesigned to allow 131 correctness in the presence of out-of-order delivery, with 132 flexibility for implementations to balance between resilience against 133 head-of-line blocking and optimal compression ratio. The design 134 goals are to closely approach the compression ratio of HPACK with 135 substantially less head-of-line blocking under the same loss 136 conditions. 138 2. Header Tables 140 Like HPACK, QPACK uses two tables for associating header fields to 141 indexes. The static table (see Section 2.1) is predefined and 142 contains common header fields (some of them with an empty value). 144 The dynamic table (see Section 2.2) built up over the course of the 145 connection and can be used by the encoder to index header fields 146 repeated in the encoded header lists. 148 Unlike in HPACK, entries in the QPACK static and dynamic tables are 149 addressed separately. The following sections describe how entries in 150 each table is addressed. 152 2.1. Static Table 154 The static table consists of a predefined static list of header 155 fields, each of which has a fixed index over time. Its entries are 156 defined in Appendix A of [RFC7541]. Note that because HPACK did not 157 use zero-based references, there is no value at index zero of the 158 static table. 160 2.2. Dynamic Table 162 The dynamic table consists of a list of header fields maintained in 163 first-in, first-out order. The dynamic table is initially empty. 164 Entries are added by instructions on the Encoder Stream (see 165 Section 5.2). 167 Before a new entry is added to the dynamic table, entries are evicted 168 from the end of the dynamic table until the size of the dynamic table 169 is less than or equal to (maximum size - new entry size) or until the 170 table is empty. 172 If the size of the new entry is less than or equal to the maximum 173 size, that entry is added to the table. It is an error to attempt to 174 add an entry that is larger than the maximum size; this MUST be 175 treated as a connection error of type 176 "HTTP_QPACK_DECOMPRESSION_FAILED". 178 A new entry can reference an entry in the dynamic table that will be 179 evicted when adding this new entry into the dynamic table. 180 Implementations are cautioned to avoid deleting the referenced name 181 if the referenced entry is evicted from the dynamic table prior to 182 inserting the new entry. 184 The dynamic table can contain duplicate entries (i.e., entries with 185 the same name and same value). Therefore, duplicate entries MUST NOT 186 be treated as an error by a decoder. 188 The encoder decides how to update the dynamic table and as such can 189 control how much memory is used by the dynamic table. To limit the 190 memory requirements of the decoder, the dynamic table size is 191 strictly bounded. 193 The decoder determines the maximum size that the encoder is permitted 194 to use for the dynamic table. In HTTP/QUIC, this value is determined 195 by the SETTINGS_HEADER_TABLE_SIZE setting (see Section 4.2.5.2 of 196 [QUIC-HTTP]). 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 control 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 control 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 control 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 Successful 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 was processed successfully permits the encoder 348 to avoid evicting entries while references remain outstanding; see 349 Section 6.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 (TODO: reference 411 PR#1357) for 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 header field name is represented using the relative 495 index of that entry, which is represented as an integer with a 6-bit 496 prefix (see Section 5.1 of [RFC7541]). 498 The header name reference is followed by the header field value 499 represented as a string literal (see Section 5.2 of [RFC7541]). 501 0 1 2 3 4 5 6 7 502 +---+---+---+---+---+---+---+---+ 503 | 1 | S | Name Index (6+) | 504 +---+---+-----------------------+ 505 | H | Value Length (7+) | 506 +---+---------------------------+ 507 | Value String (Length octets) | 508 +-------------------------------+ 510 Insert Header Field -- Indexed Name 512 5.2.2. Insert Without Name Reference 514 An addition to the header table where both the header field name and 515 the header field value are represented as string literals (see 516 Section 5.1) starts with the '01' two-bit pattern. 518 The name is represented as a 6-bit prefix string literal, while the 519 value is represented as an 8-bit prefix string literal. 521 0 1 2 3 4 5 6 7 522 +---+---+---+---+---+---+---+---+ 523 | 0 | 1 | H | Name Length (5+) | 524 +---+---+---+-------------------+ 525 | Name String (Length octets) | 526 +---+---------------------------+ 527 | H | Value Length (7+) | 528 +---+---------------------------+ 529 | Value String (Length octets) | 530 +-------------------------------+ 532 Insert Header Field -- New Name 534 5.2.3. Duplicate 536 Duplication of an existing entry in the dynamic table starts with the 537 '000' three-bit pattern. The relative index of the existing entry is 538 represented as an integer with a 5-bit prefix. 540 0 1 2 3 4 5 6 7 541 +---+---+---+---+---+---+---+---+ 542 | 0 | 0 | 0 | Index (5+) | 543 +---+---+---+-------------------+ 545 Figure 1: Duplicate 547 The existing entry is re-inserted into the dynamic table without 548 resending either the name or the value. This is useful to mitigate 549 the eviction of older entries which are frequently referenced, both 550 to avoid the need to resend the header and to avoid the entry in the 551 table blocking the ability to insert new headers. 553 5.2.4. Dynamic Table Size Update 555 An encoder informs the decoder of a change to the size of the dynamic 556 table using an instruction which begins with the '001' three-bit 557 pattern. The new maximum table size is represented as an integer 558 with a 5-bit prefix (see Section 5.1 of [RFC7541]). 560 0 1 2 3 4 5 6 7 561 +---+---+---+---+---+---+---+---+ 562 | 0 | 0 | 1 | Max size (5+) | 563 +---+---+---+-------------------+ 565 Figure 2: Maximum Dynamic Table Size Change 567 The new maximum size MUST be lower than or equal to the limit 568 determined by the protocol using QPACK. A value that exceeds this 569 limit MUST be treated as a decoding error. In HTTP/QUIC, this limit 570 is the value of the SETTINGS_HEADER_TABLE_SIZE parameter (see 571 Section 4) received from the decoder. 573 Reducing the maximum size of the dynamic table can cause entries to 574 be evicted (see Section 4.3 of [RFC7541]). This MUST NOT cause the 575 eviction of entries with outstanding references (see Section 6.3). 576 Changing the size of the dynamic table is not acknowledged as this 577 instruction does not insert an entry. 579 5.3. QPACK Decoder Stream 581 The decoder stream carries information used to ensure consistency of 582 the dynamic table. Information is sent from the QPACK decoder to the 583 QPACK encoder; that is, the server informs the client about the 584 processing of the client's header blocks and table updates, and the 585 client informs the server about the processing of the server's header 586 blocks and table updates. 588 The contents of the decoder stream are an unframed sequence of the 589 following instructions. 591 5.3.1. Table State Synchronize 593 The Table State Synchronize instruction begins with the '00' two-bit 594 pattern. The instruction specifies the total number of dynamic table 595 inserts and duplications since the last Table State Synchronize or 596 Header Acknowledgement that increased the Largest Known Received 597 dynamic table entry. This is encoded as a 6-bit prefix integer. The 598 encoder uses this value to determine which table entries might cause 599 a stream to become blocked, as described in Section 2.3.1. 601 0 1 2 3 4 5 6 7 602 +---+---+---+---+---+---+---+---+ 603 | 0 | 0 | Insert Count (6+) | 604 +---+---+-----------------------+ 606 Figure 3: Table State Synchronize 608 A decoder chooses when to emit Table State Synchronize instructions. 609 Emitting a Table State Synchronize after adding each new dynamic 610 table entry will provide the most timely feedback to the encoder, but 611 could be redundant with other decoder feedback. By delaying a 612 Table State Synchronize, a decoder might be able to coalesce multiple 613 Table State Synchronize instructions, or replace them entirely with 614 Header Acknowledgements. However, delaying too long may lead to 615 compression inefficiencies if the encoder waits for an entry to be 616 acknowledged before using it. 618 5.3.2. Header Acknowledgement 620 After processing a header block on a request or push stream, the 621 decoder emits a Header Acknowledgement instruction on the decoder 622 stream. The instruction begins with the '1' one-bit pattern and 623 includes the request stream's stream ID, encoded as a 7-bit prefix 624 integer. It is used by the peer's QPACK encoder to know when it is 625 safe to evict an entry. 627 The same Stream ID can be identified multiple times, as multiple 628 header blocks can be sent on a single stream in the case of 629 intermediate responses, trailers, and pushed requests. Since header 630 frames on each stream are received and processed in order, this gives 631 the encoder precise feedback on which header blocks within a stream 632 have been fully processed. 634 0 1 2 3 4 5 6 7 635 +---+---+---+---+---+---+---+---+ 636 | 1 | Stream ID (7+) | 637 +---+---------------------------+ 639 Figure 4: Header Acknowledgement 641 When blocking references are permitted, the encoder uses 642 acknowledgement of header blocks to update the Largest Known Received 643 index. If a header block was potentially blocking, the 644 acknowledgement implies that the decoder has received all dynamic 645 table state necessary to process the header block. If the Largest 646 Reference of an acknowledged header block was greater than the 647 encoder's current Largest Known Received index, the block's Largest 648 Reference becomes the new Largest Known Received. 650 5.3.3. Stream Cancellation 652 A stream that is reset might have multiple outstanding header blocks. 653 A decoder that receives a stream reset before the end of a stream 654 generates a Stream Cancellation instruction on the decoder stream. 655 Similarly, a decoder that abandons reading of a stream needs to 656 signal this using the Stream Cancellation instruction. This signals 657 to the encoder that all references to the dynamic table on that 658 stream are no longer outstanding. 660 An encoder cannot infer from this instruction that any updates to the 661 dynamic table have been received. 663 The instruction begins with the '01' two-bit pattern. The 664 instruction includes the stream ID of the affected stream - a request 665 or push stream - encoded as a 6-bit prefix integer. 667 0 1 2 3 4 5 6 7 668 +---+---+---+---+---+---+---+---+ 669 | 0 | 1 | Stream ID (6+) | 670 +---+---+-----------------------+ 672 Figure 5: Stream Cancellation 674 5.4. Request and Push Streams 676 HEADERS and PUSH_PROMISE frames on request and push streams reference 677 the dynamic table in a particular state without modifying it. Frames 678 on these streams emit the headers for an HTTP request or response. 680 5.4.1. Header Data Prefix 682 Header data is prefixed with two integers, "Largest Reference" and 683 "Base Index". 685 0 1 2 3 4 5 6 7 686 +---+---+---+---+---+---+---+---+ 687 | Largest Reference (8+) | 688 +---+---------------------------+ 689 | S | Delta Base Index (7+) | 690 +---+---------------------------+ 691 | Compressed Headers ... 692 +-------------------------------+ 694 Figure 6: Frame Payload 696 "Largest Reference" identifies the largest absolute dynamic index 697 referenced in the block. Blocking decoders use the Largest Reference 698 to determine when it is safe to process the rest of the block. 700 "Base Index" is used to resolve references in the dynamic table as 701 described in Section 2.2.1. 703 To save space, Base Index is encoded relative to Largest Reference 704 using a one-bit sign and the "Delta Base Index" value. A sign bit of 705 0 indicates that the Base Index has an absolute index that is greater 706 than or equal to the Largest Reference; the value of Delta Base Index 707 is added to the Largest Reference to determine the absolute value of 708 the Base Index. A sign bit of 1 indicates that the Base Index is 709 less than the Largest Reference. That is: 711 if sign == 0: 712 baseIndex = largestReference + deltaBaseIndex 713 else: 714 baseIndex = largestReference - deltaBaseIndex 716 A single-pass encoder is expected to determine the absolute value of 717 Base Index before encoding a header block. If the encoder inserted 718 entries in the dynamic table while encoding the header block, Largest 719 Reference will be greater than Base Index, so the encoded difference 720 is negative and the sign bit is set to 1. If the header block did 721 not reference the most recent entry in the table and did not insert 722 any new entries, Base Index will be greater than the Largest 723 Reference, so the delta will be positive and the sign bit is set to 724 0. 726 An encoder that produces table updates before encoding a header block 727 might set Largest Reference and Base Index to the same value. When 728 Largest Reference and Base Index are equal, the Delta Base Index is 729 encoded with a zero sign bit. A sign bit set to 1 when the Delta 730 Base Index is 0 MUST be treated as a decoder error. 732 A header block that does not reference the dynamic table can use any 733 value for Base Index; setting both Largest Reference and Base Index 734 to zero is the most efficient encoding. 736 5.4.2. Instructions 738 5.4.2.1. Indexed Header Field 740 An indexed header field representation identifies an entry in either 741 the static table or the dynamic table and causes that header field to 742 be added to the decoded header list, as described in Section 3.2 of 743 [RFC7541]. 745 0 1 2 3 4 5 6 7 746 +---+---+---+---+---+---+---+---+ 747 | 1 | S | Index (6+) | 748 +---+---+-----------------------+ 750 Indexed Header Field 752 If the entry is in the static table, or in the dynamic table with an 753 absolute index less than or equal to Base Index, this representation 754 starts with the '1' 1-bit pattern, followed by the "S" bit indicating 755 whether the reference is into the static (S=1) or dynamic (S=0) 756 table. Finally, the relative index of the matching header field is 757 represented as an integer with a 6-bit prefix (see Section 5.1 of 758 [RFC7541]). 760 5.4.2.2. Indexed Header Field With Post-Base Index 762 If the entry is in the dynamic table with an absolute index greater 763 than Base Index, the representation starts with the '0001' 4-bit 764 pattern, followed by the post-base index (see Section 2.2.1) of the 765 matching header field, represented as an integer with a 4-bit prefix 766 (see Section 5.1 of [RFC7541]). 768 0 1 2 3 4 5 6 7 769 +---+---+---+---+---+---+---+---+ 770 | 0 | 0 | 0 | 1 | Index (4+) | 771 +---+---+---+---+---------------+ 773 Indexed Header Field with Post-Base Index 775 5.4.2.3. Literal Header Field With Name Reference 777 A literal header field with a name reference represents a header 778 where the header field name matches the header field name of an entry 779 stored in the static table or the dynamic table. 781 If the entry is in the static table, or in the dynamic table with an 782 absolute index less than or equal to Base Index, this representation 783 starts with the '01' two-bit pattern. If the entry is in the dynamic 784 table with an absolute index greater than Base Index, the 785 representation starts with the '0000' four-bit pattern. 787 The following bit, 'N', indicates whether an intermediary is 788 permitted to add this header to the dynamic header table on 789 subsequent hops. When the 'N' bit is set, the encoded header MUST 790 always be encoded with a literal representation. In particular, when 791 a peer sends a header field that it received represented as a literal 792 header field with the 'N' bit set, it MUST use a literal 793 representation to forward this header field. This bit is intended 794 for protecting header field values that are not to be put at risk by 795 compressing them (see Section 7.1 of [RFC7541] for more details). 797 0 1 2 3 4 5 6 7 798 +---+---+---+---+---+---+---+---+ 799 | 0 | 1 | N | S |Name Index (4+)| 800 +---+---+---+---+---------------+ 801 | H | Value Length (7+) | 802 +---+---------------------------+ 803 | Value String (Length octets) | 804 +-------------------------------+ 806 Literal Header Field With Name Reference 808 For entries in the static table or in the dynamic table with an 809 absolute index less than or equal to Base Index, the header field 810 name is represented using the relative index of that entry, which is 811 represented as an integer with a 4-bit prefix (see Section 5.1 of 812 [RFC7541]). The "S" bit indicates whether the reference is to the 813 static (S=1) or dynamic (S=0) table. 815 5.4.2.4. Literal Header Field With Post-Base Name Reference 817 For entries in the dynamic table with an absolute index greater than 818 Base Index, the header field name is represented using the post-base 819 index of that entry (see Section 2.2.1) encoded as an integer with a 820 3-bit prefix. 822 0 1 2 3 4 5 6 7 823 +---+---+---+---+---+---+---+---+ 824 | 0 | 0 | 0 | 0 | N |NameIdx(3+)| 825 +---+---+---+---+---+-----------+ 826 | H | Value Length (7+) | 827 +---+---------------------------+ 828 | Value String (Length octets) | 829 +-------------------------------+ 831 Literal Header Field With Post-Base Name Reference 833 5.4.2.5. Literal Header Field Without Name Reference 835 An addition to the header table where both the header field name and 836 the header field value are represented as string literals (see 837 Section 5.1) starts with the '001' three-bit pattern. 839 The fourth bit, 'N', indicates whether an intermediary is permitted 840 to add this header to the dynamic header table on subsequent hops. 841 When the 'N' bit is set, the encoded header MUST always be encoded 842 with a literal representation. In particular, when a peer sends a 843 header field that it received represented as a literal header field 844 with the 'N' bit set, it MUST use a literal representation to forward 845 this header field. This bit is intended for protecting header field 846 values that are not to be put at risk by compressing them (see 847 Section 7.1 of [RFC7541] for more details). 849 The name is represented as a 4-bit prefix string literal, while the 850 value is represented as an 8-bit prefix string literal. 852 0 1 2 3 4 5 6 7 853 +---+---+---+---+---+---+---+---+ 854 | 0 | 0 | 1 | N | H |NameLen(3+)| 855 +---+---+---+---+---+-----------+ 856 | Name String (Length octets) | 857 +---+---------------------------+ 858 | H | Value Length (7+) | 859 +---+---------------------------+ 860 | Value String (Length octets) | 861 +-------------------------------+ 863 Literal Header Field Without Name Reference 865 6. Encoding Strategies 867 6.1. Single Pass Encoding 869 An encoder making a single pass over a list of headers must choose 870 Base Index before knowing Largest Reference. When trying to 871 reference a header inserted to the table after encoding has begun, 872 the entry is encoded with different instructions that tell the 873 decoder to use an absolute index greater than the Base Index. 875 6.2. Preventing Eviction Races 877 Due to out-of-order arrival, QPACK's eviction algorithm requires 878 changes (relative to HPACK) to avoid the possibility that an indexed 879 representation is decoded after the referenced entry has already been 880 evicted. QPACK employs a two-phase eviction algorithm, in which the 881 encoder will not evict entries that have outstanding (unacknowledged) 882 references. 884 6.3. Reference Tracking 886 An encoder MUST ensure that a header block which references a dynamic 887 table entry is not received by the decoder after the referenced entry 888 has already been evicted. An encoder also respects the limit set by 889 the decoder on the number of streams that are allowed to become 890 blocked. Even if the decoder is willing to tolerate blocked streams, 891 the encoder might choose to avoid them in certain cases. 893 In order to enable this, the encoder will need to track outstanding 894 (unacknowledged) header blocks and table updates using feedback 895 received from the decoder. 897 6.3.1. Blocked Eviction 899 The encoder MUST NOT permit an entry to be evicted while a reference 900 to that entry remains unacknowledged. If a new header to be inserted 901 into the dynamic table would cause the eviction of such an entry, the 902 encoder MUST NOT emit the insert instruction until the reference has 903 been processed by the decoder and acknowledged. 905 The encoder can emit a literal representation for the new header in 906 order to avoid encoding delays, and MAY insert the header into the 907 table later if desired. 909 To ensure that the blocked eviction case is rare, references to the 910 oldest entries in the dynamic table SHOULD be avoided. When one of 911 the oldest entries in the table is still actively used for 912 references, the encoder SHOULD emit an Duplicate representation 913 instead (see Section 5.2.3). 915 6.3.2. Blocked Decoding 917 For header blocks encoded in non-blocking mode, the encoder needs to 918 forego indexed representations that refer to table updates which have 919 not yet been acknowledged with Section 5.3. Since all table updates 920 are processed in sequence on the control stream, an index into the 921 dynamic table is sufficient to track which entries have been 922 acknowledged. 924 To track blocked streams, the necessary Base Index value for each 925 stream can be used. Whenever the decoder processes a table update, 926 it can begin decoding any blocked streams that now have their 927 dependencies satisfied. 929 6.4. Speculative table updates 931 Implementations can _speculatively_ send header frames on the HTTP 932 Control Streams which are not needed for any current HTTP request or 933 response. Such headers could be used strategically to improve 934 performance. For instance, the encoder might decide to _refresh_ by 935 sending Duplicate representations for popular header fields 936 (Section 5.2.3), ensuring they have small indices and hence minimal 937 size on the wire. 939 6.5. Sample One Pass Encoding Algorithm 941 Pseudo-code for single pass encoding, excluding handling of 942 duplicates, non-blocking mode, and reference tracking. 944 baseIndex = dynamicTable.baseIndex 945 largestReference = 0 946 for header in headers: 947 staticIdx = staticTable.getIndex(header) 948 if staticIdx: 949 encodeIndexReference(streamBuffer, staticIdx) 950 continue 952 dynamicIdx = dynamicTable.getIndex(header) 953 if !dynamicIdx: 954 # No matching entry. Either insert+index or encode literal 955 nameIdx = getNameIndex(header) 956 if shouldIndex(header) and dynamicTable.canIndex(header): 957 encodeLiteralWithIncrementalIndex(controlBuffer, nameIdx, 958 header) 959 dynamicTable.add(header) 960 dynamicIdx = dynamicTable.baseIndex 962 if !dynamicIdx: 963 # Couldn't index it, literal 964 if nameIdx <= staticTable.size: 965 encodeLiteral(streamBuffer, nameIndex, header) 966 else: 967 # encode literal, possibly with nameIdx above baseIndex 968 encodeDynamicLiteral(streamBuffer, nameIndex, baseIndex, 969 header) 970 largestReference = max(largestReference, 971 dynamicTable.toAbsolute(nameIdx)) 972 else: 973 # Dynamic index reference 974 assert(dynamicIdx) 975 largestReference = max(largestReference, dynamicIdx) 976 # Encode dynamicIdx, possibly with dynamicIdx above baseIndex 977 encodeDynamicIndexReference(streamBuffer, dynamicIdx, 978 baseIndex) 980 # encode the prefix 981 encodeInteger(prefixBuffer, 0x00, largestReference, 8) 982 if baseIndex >= largestReference: 983 encodeInteger(prefixBuffer, 0, baseIndex - largestReference, 7) 984 else: 985 encodeInteger(prefixBuffer, 0x80, 986 largestReference - baseIndex, 7) 988 return controlBuffer, prefixBuffer + streamBuffer 990 7. Security Considerations 992 TBD. 994 8. IANA Considerations 996 8.1. Settings Registration 998 This document creates two new settings in the "HTTP/QUIC Settings" 999 registry established in [QUIC-HTTP]. 1001 The entries in the following table are registered by this document. 1003 +-----------------------+------+---------------+ 1004 | Setting Name | Code | Specification | 1005 +-----------------------+------+---------------+ 1006 | HEADER_TABLE_SIZE | 0x1 | Section 4 | 1007 | | | | 1008 | QPACK_BLOCKED_STREAMS | 0x7 | Section 4 | 1009 +-----------------------+------+---------------+ 1011 8.2. Stream Type Registration 1013 This document creates two new settings in the "HTTP/QUIC Stream Type" 1014 registry established in [QUIC-HTTP]. 1016 The entries in the following table are registered by this document. 1018 +----------------------+------+---------------+--------+ 1019 | Stream Type | Code | Specification | Sender | 1020 +----------------------+------+---------------+--------+ 1021 | QPACK Encoder Stream | 0x48 | Section 5 | Both | 1022 | | | | | 1023 | QPACK Decoder Stream | 0x68 | Section 5 | Both | 1024 +----------------------+------+---------------+--------+ 1026 9. References 1028 9.1. Normative References 1030 [QUIC-HTTP] 1031 Bishop, M., Ed., "Hypertext Transfer Protocol (HTTP) over 1032 QUIC", draft-ietf-quic-http-13 (work in progress), June 1033 2018. 1035 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1036 Requirement Levels", BCP 14, RFC 2119, 1037 DOI 10.17487/RFC2119, March 1997, 1038 . 1040 [RFC7541] Peon, R. and H. Ruellan, "HPACK: Header Compression for 1041 HTTP/2", RFC 7541, DOI 10.17487/RFC7541, May 2015, 1042 . 1044 [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC 1045 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, 1046 May 2017, . 1048 9.2. Informative References 1050 [QUIC-TRANSPORT] 1051 Iyengar, J. and M. Thomson, "QUIC: A UDP-Based Multiplexed 1052 and Secure Transport", draft-ietf-quic-transport-12 (work 1053 in progress), May 2018. 1055 [RFC2360] Scott, G., "Guide for Internet Standards Writers", BCP 22, 1056 RFC 2360, DOI 10.17487/RFC2360, June 1998, 1057 . 1059 [RFC7540] Belshe, M., Peon, R., and M. Thomson, Ed., "Hypertext 1060 Transfer Protocol Version 2 (HTTP/2)", RFC 7540, 1061 DOI 10.17487/RFC7540, May 2015, 1062 . 1064 9.3. URIs 1066 [1] https://mailarchive.ietf.org/arch/search/?email_list=quic 1068 [2] https://github.com/quicwg 1070 [3] https://github.com/quicwg/base-drafts/labels/-qpack 1072 Appendix A. Change Log 1074 *RFC Editor's Note:* Please remove this section prior to 1075 publication of a final version of this document. 1077 A.1. Since draft-ietf-quic-qpack-00 1079 o Renumbered instructions for consistency (#1471, #1472) 1081 o Decoder is allowed to validate largest reference (#1404, #1469) 1082 o Header block acknowledgments also acknowledge the associated 1083 largest reference (#1370, #1400) 1085 o Added an acknowledgment for unread streams (#1371, #1400) 1087 o Removed framing from encoder stream (#1361,#1467) 1089 o Control streams use typed unidirectional streams rather than fixed 1090 stream IDs (#910,#1359) 1092 A.2. Since draft-ietf-quic-qcram-00 1094 o Separate instruction sets for table updates and header blocks 1095 (#1235, #1142, #1141) 1097 o Reworked indexing scheme (#1176, #1145, #1136, #1130, #1125, 1098 #1314) 1100 o Added mechanisms that support one-pass encoding (#1138, #1320) 1102 o Added a setting to control the number of blocked decoders (#238, 1103 #1140, #1143) 1105 o Moved table updates and acknowledgments to dedicated streams 1106 (#1121, #1122, #1238) 1108 Acknowledgments 1110 This draft draws heavily on the text of [RFC7541]. The indirect 1111 input of those authors is gratefully acknowledged, as well as ideas 1112 from: 1114 o Ryan Hamilton 1116 o Patrick McManus 1118 o Kazuho Oku 1120 o Biren Roy 1122 o Ian Swett 1124 o Dmitri Tikhonov 1126 Buck's contribution was supported by Google during his employment 1127 there. 1129 A substantial portion of Mike's contribution was supported by 1130 Microsoft during his employment there. 1132 Authors' Addresses 1134 Charles 'Buck' Krasic 1135 Netflix 1137 Email: ckrasic@netflix.com 1139 Mike Bishop 1140 Akamai Technologies 1142 Email: mbishop@evequefou.be 1144 Alan Frindell (editor) 1145 Facebook 1147 Email: afrind@fb.com