/
draft-ietf-quic-qpack.txt
2318 lines (1832 loc) · 101 KB
/
draft-ietf-quic-qpack.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
QUIC C. Krasic
Internet-Draft Netflix
Intended status: Standards Track M. Bishop
Expires: 21 August 2021 Akamai Technologies
A. Frindell, Ed.
Facebook
17 February 2021
QPACK: Header Compression for HTTP/3
draft-ietf-quic-qpack
Abstract
This specification defines QPACK, a compression format for
efficiently representing HTTP fields, to be used in HTTP/3. This is
a variation of HPACK compression that seeks to reduce head-of-line
blocking.
Note to Readers
Discussion of this draft takes place on the QUIC working group
mailing list (quic@ietf.org (mailto:quic@ietf.org)), which is
archived at https://mailarchive.ietf.org/arch/
search/?email_list=quic.
Working Group information can be found at https://github.com/quicwg;
source code and issues list for this draft can be found at
https://github.com/quicwg/base-drafts/labels/-qpack.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 21 August 2021.
Copyright Notice
Copyright (c) 2021 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Simplified BSD License text
as described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Simplified BSD License.
Table of Contents
1. Introduction
1.1. Conventions and Definitions
1.2. Notational Conventions
2. Compression Process Overview
2.1. Encoder
2.1.1. Limits on Dynamic Table Insertions
2.1.2. Blocked Streams
2.1.3. Avoiding Flow Control Deadlocks
2.1.4. Known Received Count
2.2. Decoder
2.2.1. Blocked Decoding
2.2.2. State Synchronization
2.2.3. Invalid References
3. Reference Tables
3.1. Static Table
3.2. Dynamic Table
3.2.1. Dynamic Table Size
3.2.2. Dynamic Table Capacity and Eviction
3.2.3. Maximum Dynamic Table Capacity
3.2.4. Absolute Indexing
3.2.5. Relative Indexing
3.2.6. Post-Base Indexing
4. Wire Format
4.1. Primitives
4.1.1. Prefixed Integers
4.1.2. String Literals
4.2. Encoder and Decoder Streams
4.3. Encoder Instructions
4.3.1. Set Dynamic Table Capacity
4.3.2. Insert With Name Reference
4.3.3. Insert With Literal Name
4.3.4. Duplicate
4.4. Decoder Instructions
4.4.1. Section Acknowledgment
4.4.2. Stream Cancellation
4.4.3. Insert Count Increment
4.5. Field Line Representations
4.5.1. Encoded Field Section Prefix
4.5.2. Indexed Field Line
4.5.3. Indexed Field Line With Post-Base Index
4.5.4. Literal Field Line With Name Reference
4.5.5. Literal Field Line With Post-Base Name Reference
4.5.6. Literal Field Line With Literal Name
5. Configuration
6. Error Handling
7. Security Considerations
7.1. Probing Dynamic Table State
7.1.1. Applicability to QPACK and HTTP
7.1.2. Mitigation
7.1.3. Never-Indexed Literals
7.2. Static Huffman Encoding
7.3. Memory Consumption
7.4. Implementation Limits
8. IANA Considerations
8.1. Settings Registration
8.2. Stream Type Registration
8.3. Error Code Registration
9. References
9.1. Normative References
9.2. Informative References
Appendix A. Static Table
Appendix B. Encoding and Decoding Examples
B.1. Literal Field Line With Name Reference
B.2. Dynamic Table
B.3. Speculative Insert
B.4. Duplicate Instruction, Stream Cancellation
B.5. Dynamic Table Insert, Eviction
Appendix C. Sample One Pass Encoding Algorithm
Appendix D. Change Log
D.1. Since draft-ietf-quic-qpack-19
D.2. Since draft-ietf-quic-qpack-18
D.3. Since draft-ietf-quic-qpack-17
D.4. Since draft-ietf-quic-qpack-16
D.5. Since draft-ietf-quic-qpack-15
D.6. Since draft-ietf-quic-qpack-14
D.7. Since draft-ietf-quic-qpack-13
D.8. Since draft-ietf-quic-qpack-12
D.9. Since draft-ietf-quic-qpack-11
D.10. Since draft-ietf-quic-qpack-10
D.11. Since draft-ietf-quic-qpack-09
D.12. Since draft-ietf-quic-qpack-08
D.13. Since draft-ietf-quic-qpack-06
D.14. Since draft-ietf-quic-qpack-05
D.15. Since draft-ietf-quic-qpack-04
D.16. Since draft-ietf-quic-qpack-03
D.17. Since draft-ietf-quic-qpack-02
D.18. Since draft-ietf-quic-qpack-01
D.19. Since draft-ietf-quic-qpack-00
D.20. Since draft-ietf-quic-qcram-00
Acknowledgments
Authors' Addresses
1. Introduction
The QUIC transport protocol ([QUIC-TRANSPORT]) is designed to support
HTTP semantics, and its design subsumes many of the features of
HTTP/2 ([RFC7540]). HTTP/2 uses HPACK ([RFC7541]) for compression of
the header and trailer sections. If HPACK were used for HTTP/3
([HTTP3]), it would induce head-of-line blocking for field sections
due to built-in assumptions of a total ordering across frames on all
streams.
QPACK reuses core concepts from HPACK, but is redesigned to allow
correctness in the presence of out-of-order delivery, with
flexibility for implementations to balance between resilience against
head-of-line blocking and optimal compression ratio. The design
goals are to closely approach the compression ratio of HPACK with
substantially less head-of-line blocking under the same loss
conditions.
1.1. Conventions and Definitions
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in
BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all
capitals, as shown here.
Definitions of terms that are used in this document:
HTTP fields: Metadata sent as part of an HTTP message. The term
encompasses both header and trailer fields. Colloquially, the
term "headers" has often been used to refer to HTTP header fields
and trailer fields; this document uses "fields" for generality.
HTTP field line: A name-value pair sent as part of an HTTP field
section. See Sections 6.3 and 6.5 of [SEMANTICS].
HTTP field value: Data associated with a field name, composed from
all field line values with that field name in that section,
concatenated together with comma separators.
Field section: An ordered collection of HTTP field lines associated
with an HTTP message. A field section can contain multiple field
lines with the same name. It can also contain duplicate field
lines. An HTTP message can include both header and trailer
sections.
Representation: An instruction that represents a field line,
possibly by reference to the dynamic and static tables.
Encoder: An implementation that encodes field sections.
Decoder: An implementation that decodes encoded field sections.
Absolute Index: A unique index for each entry in the dynamic table.
Base: A reference point for relative and post-base indices.
Representations that reference dynamic table entries are relative
to a Base.
Insert Count: The total number of entries inserted in the dynamic
table.
QPACK is a name, not an acronym.
1.2. Notational Conventions
Diagrams use the format described in Section 3.1 of [RFC2360], with
the following additional conventions:
x (A) Indicates that x is A bits long
x (A+) Indicates that x uses the prefixed integer encoding defined
in Section 4.1.1, beginning with an A-bit prefix.
x ... Indicates that x is variable-length and extends to the end of
the region.
2. Compression Process Overview
Like HPACK, QPACK uses two tables for associating field lines
("headers") to indices. The static table (Section 3.1) is predefined
and contains common header field lines (some of them with an empty
value). The dynamic table (Section 3.2) is built up over the course
of the connection and can be used by the encoder to index both header
and trailer field lines in the encoded field sections.
QPACK defines unidirectional streams for sending instructions from
encoder to decoder and vice versa.
2.1. Encoder
An encoder converts a header or trailer section into a series of
representations by emitting either an indexed or a literal
representation for each field line in the list; see Section 4.5.
Indexed representations achieve high compression by replacing the
literal name and possibly the value with an index to either the
static or dynamic table. References to the static table and literal
representations do not require any dynamic state and never risk head-
of-line blocking. References to the dynamic table risk head-of-line
blocking if the encoder has not received an acknowledgment indicating
the entry is available at the decoder.
An encoder MAY insert any entry in the dynamic table it chooses; it
is not limited to field lines it is compressing.
QPACK preserves the ordering of field lines within each field
section. An encoder MUST emit field representations in the order
they appear in the input field section.
QPACK is designed to contain the more complex state tracking to the
encoder, while the decoder is relatively simple.
2.1.1. Limits on Dynamic Table Insertions
Inserting entries into the dynamic table might not be possible if the
table contains entries that cannot be evicted.
A dynamic table entry cannot be evicted immediately after insertion,
even if it has never been referenced. Once the insertion of a
dynamic table entry has been acknowledged and there are no
outstanding references to the entry in unacknowledged
representations, the entry becomes evictable. Note that references
on the encoder stream never preclude the eviction of an entry,
because those references are guaranteed to be processed before the
instruction evicting the entry.
If the dynamic table does not contain enough room for a new entry
without evicting other entries, and the entries that would be evicted
are not evictable, the encoder MUST NOT insert that entry into the
dynamic table (including duplicates of existing entries). In order
to avoid this, an encoder that uses the dynamic table has to keep
track of each dynamic table entry referenced by each field section
until those representations are acknowledged by the decoder; see
Section 4.4.1.
2.1.1.1. Avoiding Prohibited Insertions
To ensure that the encoder is not prevented from adding new entries,
the encoder can avoid referencing entries that are close to eviction.
Rather than reference such an entry, the encoder can emit a Duplicate
instruction (Section 4.3.4), and reference the duplicate instead.
Determining which entries are too close to eviction to reference is
an encoder preference. One heuristic is to target a fixed amount of
available space in the dynamic table: either unused space or space
that can be reclaimed by evicting non-blocking entries. To achieve
this, the encoder can maintain a draining index, which is the
smallest absolute index (Section 3.2.4) in the dynamic table that it
will emit a reference for. As new entries are inserted, the encoder
increases the draining index to maintain the section of the table
that it will not reference. If the encoder does not create new
references to entries with an absolute index lower than the draining
index, the number of unacknowledged references to those entries will
eventually become zero, allowing them to be evicted.
<-- Newer Entries Older Entries -->
(Larger Indicies) (Smaller Indicies)
+--------+---------------------------------+----------+
| Unused | Referenceable | Draining |
| Space | Entries | Entries |
+--------+---------------------------------+----------+
^ ^ ^
| | |
Insertion Point Draining Index Dropping
Point
Figure 1: Draining Dynamic Table Entries
2.1.2. Blocked Streams
Because QUIC does not guarantee order between data on different
streams, a decoder might encounter a representation that references a
dynamic table entry that it has not yet received.
Each encoded field section contains a Required Insert Count
(Section 4.5.1), the lowest possible value for the Insert Count with
which the field section can be decoded. For a field section encoded
using references to the dynamic table, the Required Insert Count is
one larger than the largest absolute index of all referenced dynamic
table entries. For a field section encoded with no references to the
dynamic table, the Required Insert Count is zero.
When the decoder receives an encoded field section with a Required
Insert Count greater than its own Insert Count, the stream cannot be
processed immediately, and is considered "blocked"; see
Section 2.2.1.
The decoder specifies an upper bound on the number of streams that
can be blocked using the SETTINGS_QPACK_BLOCKED_STREAMS setting; see
Section 5. An encoder MUST limit the number of streams that could
become blocked to the value of SETTINGS_QPACK_BLOCKED_STREAMS at all
times. If a decoder encounters more blocked streams than it promised
to support, it MUST treat this as a connection error of type
QPACK_DECOMPRESSION_FAILED.
Note that the decoder might not become blocked on every stream that
risks becoming blocked.
An encoder can decide whether to risk having a stream become blocked.
If permitted by the value of SETTINGS_QPACK_BLOCKED_STREAMS,
compression efficiency can often be improved by referencing dynamic
table entries that are still in transit, but if there is loss or
reordering the stream can become blocked at the decoder. An encoder
can avoid the risk of blocking by only referencing dynamic table
entries that have been acknowledged, but this could mean using
literals. Since literals make the encoded field section larger, this
can result in the encoder becoming blocked on congestion or flow
control limits.
2.1.3. Avoiding Flow Control Deadlocks
Writing instructions on streams that are limited by flow control can
produce deadlocks.
A decoder might stop issuing flow control credit on the stream that
carries an encoded field section until the necessary updates are
received on the encoder stream. If the granting of flow control
credit on the encoder stream (or the connection as a whole) depends
on the consumption and release of data on the stream carrying the
encoded field section, a deadlock might result.
More generally, a stream containing a large instruction can become
deadlocked if the decoder withholds flow control credit until the
instruction is completely received.
To avoid these deadlocks, an encoder SHOULD NOT write an instruction
unless sufficient stream and connection flow control credit is
available for the entire instruction.
2.1.4. Known Received Count
The Known Received Count is the total number of dynamic table
insertions and duplications acknowledged by the decoder. The encoder
tracks the Known Received Count in order to identify which dynamic
table entries can be referenced without potentially blocking a
stream. The decoder tracks the Known Received Count in order to be
able to send Insert Count Increment instructions.
A Section Acknowledgment instruction (Section 4.4.1) implies that the
decoder has received all dynamic table state necessary to decode the
field section. If the Required Insert Count of the acknowledged
field section is greater than the current Known Received Count, Known
Received Count is updated to that Required Insert Count value.
An Insert Count Increment instruction (Section 4.4.3) increases the
Known Received Count by its Increment parameter. See Section 2.2.2.3
for guidance.
2.2. Decoder
As in HPACK, the decoder processes a series of representations and
emits the corresponding field sections. It also processes
instructions received on the encoder stream that modify the dynamic
table. Note that encoded field sections and encoder stream
instructions arrive on separate streams. This is unlike HPACK, where
encoded field sections (header blocks) can contain instructions that
modify the dynamic table, and there is no dedicated stream of HPACK
instructions.
The decoder MUST emit field lines in the order their representations
appear in the encoded field section.
2.2.1. Blocked Decoding
Upon receipt of an encoded field section, the decoder examines the
Required Insert Count. When the Required Insert Count is less than
or equal to the decoder's Insert Count, the field section can be
processed immediately. Otherwise, the stream on which the field
section was received becomes blocked.
While blocked, encoded field section data SHOULD remain in the
blocked stream's flow control window. This data is unusable until
the stream becomes unblocked, and releasing the flow control
prematurely makes the decoder vulnerable to memory exhaustion
attacks. A stream becomes unblocked when the Insert Count becomes
unblocked when the Insert Count becomes greater than or equal to the
Required Insert Count for all encoded field sections the decoder has
started reading from the stream.
When processing encoded field sections, the decoder expects the
Required Insert Count to equal the lowest possible value for the
Insert Count with which the field section can be decoded, as
prescribed in Section 2.1.2. If it encounters a Required Insert
Count smaller than expected, it MUST treat this as a connection error
of type QPACK_DECOMPRESSION_FAILED; see Section 2.2.3. If it
encounters a Required Insert Count larger than expected, it MAY treat
this as a connection error of type QPACK_DECOMPRESSION_FAILED.
2.2.2. State Synchronization
The decoder signals the following events by emitting decoder
instructions (Section 4.4) on the decoder stream.
2.2.2.1. Completed Processing of a Field Section
After the decoder finishes decoding a field section encoded using
representations containing dynamic table references, it MUST emit a
Section Acknowledgment instruction (Section 4.4.1). A stream may
carry multiple field sections in the case of intermediate responses,
trailers, and pushed requests. The encoder interprets each
Section Acknowledgment instruction as acknowledging the earliest
unacknowledged field section containing dynamic table references sent
on the given stream.
2.2.2.2. Abandonment of a Stream
When an endpoint receives a stream reset before the end of a stream
or before all encoded field sections are processed on that stream, or
when it abandons reading of a stream, it generates a Stream
Cancellation instruction; see Section 4.4.2. This signals to the
encoder that all references to the dynamic table on that stream are
no longer outstanding. A decoder with a maximum dynamic table
capacity (Section 3.2.3) equal to zero MAY omit sending Stream
Cancellations, because the encoder cannot have any dynamic table
references. An encoder cannot infer from this instruction that any
updates to the dynamic table have been received.
The Section Acknowledgment and Stream Cancellation instructions
permit the encoder to remove references to entries in the dynamic
table. When an entry with absolute index lower than the Known
Received Count has zero references, then it is considered evictable;
see Section 2.1.1.
2.2.2.3. New Table Entries
After receiving new table entries on the encoder stream, the decoder
chooses when to emit Insert Count Increment instructions; see
Section 4.4.3. Emitting this instruction after adding each new
dynamic table entry will provide the timeliest feedback to the
encoder, but could be redundant with other decoder feedback. By
delaying an Insert Count Increment instruction, the decoder might be
able to coalesce multiple Insert Count Increment instructions, or
replace them entirely with Section Acknowledgments; see
Section 4.4.1. However, delaying too long may lead to compression
inefficiencies if the encoder waits for an entry to be acknowledged
before using it.
2.2.3. Invalid References
If the decoder encounters a reference in a field line representation
to a dynamic table entry that has already been evicted or that has an
absolute index greater than or equal to the declared Required Insert
Count (Section 4.5.1), it MUST treat this as a connection error of
type QPACK_DECOMPRESSION_FAILED.
If the decoder encounters a reference in an encoder instruction to a
dynamic table entry that has already been evicted, it MUST treat this
as a connection error of type QPACK_ENCODER_STREAM_ERROR.
3. Reference Tables
Unlike in HPACK, entries in the QPACK static and dynamic tables are
addressed separately. The following sections describe how entries in
each table are addressed.
3.1. Static Table
The static table consists of a predefined list of field lines, each
of which has a fixed index over time. Its entries are defined in
Appendix A.
All entries in the static table have a name and a value. However,
values can be empty (that is, have a length of 0). Each entry is
identified by a unique index.
Note that the QPACK static table is indexed from 0, whereas the HPACK
static table is indexed from 1.
When the decoder encounters an invalid static table index in a field
line representation it MUST treat this as a connection error of type
QPACK_DECOMPRESSION_FAILED. If this index is received on the encoder
stream, this MUST be treated as a connection error of type
QPACK_ENCODER_STREAM_ERROR.
3.2. Dynamic Table
The dynamic table consists of a list of field lines maintained in
first-in, first-out order. A QPACK encoder and decoder share a
dynamic table that is initially empty. The encoder adds entries to
the dynamic table and sends them to the decoder via instructions on
the encoder stream; see Section 4.3.
The dynamic table can contain duplicate entries (i.e., entries with
the same name and same value). Therefore, duplicate entries MUST NOT
be treated as an error by the decoder.
Dynamic table entries can have empty values.
3.2.1. Dynamic Table Size
The size of the dynamic table is the sum of the size of its entries.
The size of an entry is the sum of its name's length in bytes, its
value's length in bytes, and 32 additional bytes. The size of an
entry is calculated using the length of its name and value without
Huffman encoding applied.
3.2.2. Dynamic Table Capacity and Eviction
The encoder sets the capacity of the dynamic table, which serves as
the upper limit on its size. The initial capacity of the dynamic
table is zero. The encoder sends a Set Dynamic Table Capacity
instruction (Section 4.3.1) with a non-zero capacity to begin using
the dynamic table.
Before a new entry is added to the dynamic table, entries are evicted
from the end of the dynamic table until the size of the dynamic table
is less than or equal to (table capacity - size of new entry). The
encoder MUST NOT cause a dynamic table entry to be evicted unless
that entry is evictable; see Section 2.1.1. The new entry is then
added to the table. It is an error if the encoder attempts to add an
entry that is larger than the dynamic table capacity; the decoder
MUST treat this as a connection error of type
QPACK_ENCODER_STREAM_ERROR.
A new entry can reference an entry in the dynamic table that will be
evicted when adding this new entry into the dynamic table.
Implementations are cautioned to avoid deleting the referenced name
or value if the referenced entry is evicted from the dynamic table
prior to inserting the new entry.
Whenever the dynamic table capacity is reduced by the encoder
(Section 4.3.1), entries are evicted from the end of the dynamic
table until the size of the dynamic table is less than or equal to
the new table capacity. This mechanism can be used to completely
clear entries from the dynamic table by setting a capacity of 0,
which can subsequently be restored.
3.2.3. Maximum Dynamic Table Capacity
To bound the memory requirements of the decoder, the decoder limits
the maximum value the encoder is permitted to set for the dynamic
table capacity. In HTTP/3, this limit is determined by the value of
SETTINGS_QPACK_MAX_TABLE_CAPACITY sent by the decoder; see Section 5.
The encoder MUST NOT set a dynamic table capacity that exceeds this
maximum, but it can choose to use a lower dynamic table capacity; see
Section 4.3.1.
For clients using 0-RTT data in HTTP/3, the server's maximum table
capacity is the remembered value of the setting, or zero if the value
was not previously sent. When the client's 0-RTT value of the
SETTING is zero, the server MAY set it to a non-zero value in its
SETTINGS frame. If the remembered value is non-zero, the server MUST
send the same non-zero value in its SETTINGS frame. If it specifies
any other value, or omits SETTINGS_QPACK_MAX_TABLE_CAPACITY from
SETTINGS, the encoder must treat this as a connection error of type
QPACK_DECODER_STREAM_ERROR.
For HTTP/3 servers and HTTP/3 clients when 0-RTT is not attempted or
is rejected, the maximum table capacity is 0 until the encoder
processes a SETTINGS frame with a non-zero value of
SETTINGS_QPACK_MAX_TABLE_CAPACITY.
When the maximum table capacity is zero, the encoder MUST NOT insert
entries into the dynamic table, and MUST NOT send any encoder
instructions on the encoder stream.
3.2.4. Absolute Indexing
Each entry possesses an absolute index that is fixed for the lifetime
of that entry. The first entry inserted has an absolute index of 0;
indices increase by one with each insertion.
3.2.5. Relative Indexing
Relative indices begin at zero and increase in the opposite direction
from the absolute index. Determining which entry has a relative
index of 0 depends on the context of the reference.
In encoder instructions (Section 4.3), a relative index of 0 refers
to the most recently inserted value in the dynamic table. Note that
this means the entry referenced by a given relative index will change
while interpreting instructions on the encoder stream.
+-----+---------------+-------+
| n-1 | ... | d | Absolute Index
+ - - +---------------+ - - - +
| 0 | ... | n-d-1 | Relative Index
+-----+---------------+-------+
^ |
| V
Insertion Point Dropping Point
n = count of entries inserted
d = count of entries dropped
Figure 2: Example Dynamic Table Indexing - Encoder Stream
Unlike in encoder instructions, relative indices in field line
representations are relative to the Base at the beginning of the
encoded field section; see Section 4.5.1. This ensures that
references are stable even if encoded field sections and dynamic
table updates are processed out of order.
In a field line representation, a relative index of 0 refers to the
entry with absolute index equal to Base - 1.
Base
|
V
+-----+-----+-----+-----+-------+
| n-1 | n-2 | n-3 | ... | d | Absolute Index
+-----+-----+ - +-----+ - +
| 0 | ... | n-d-3 | Relative Index
+-----+-----+-------+
n = count of entries inserted
d = count of entries dropped
In this example, Base = n - 2
Figure 3: Example Dynamic Table Indexing - Relative Index in
Representation
3.2.6. Post-Base Indexing
Post-Base indices are used in field line representations for entries
with absolute indices greater than or equal to Base, starting at 0
for the entry with absolute index equal to Base, and increasing in
the same direction as the absolute index.
Post-Base indices allow an encoder to process a field section in a
single pass and include references to entries added while processing
this (or other) field sections.
Base
|
V
+-----+-----+-----+-----+-----+
| n-1 | n-2 | n-3 | ... | d | Absolute Index
+-----+-----+-----+-----+-----+
| 1 | 0 | Post-Base Index
+-----+-----+
n = count of entries inserted
d = count of entries dropped
In this example, Base = n - 2
Figure 4: Example Dynamic Table Indexing - Post-Base Index in
Representation
4. Wire Format
4.1. Primitives
4.1.1. Prefixed Integers
The prefixed integer from Section 5.1 of [RFC7541] is used heavily
throughout this document. The format from [RFC7541] is used
unmodified. Note, however, that QPACK uses some prefix sizes not
actually used in HPACK.
QPACK implementations MUST be able to decode integers up to and
including 62 bits long.
4.1.2. String Literals
The string literal defined by Section 5.2 of [RFC7541] is also used
throughout. This string format includes optional Huffman encoding.
HPACK defines string literals to begin on a byte boundary. They
begin with a single bit flag, denoted as 'H' in this document
(indicating whether the string is Huffman-coded), followed by the
Length encoded as a 7-bit prefix integer, and finally Length bytes of
data. When Huffman encoding is enabled, the Huffman table from
Appendix B of [RFC7541] is used without modification and Length
indicates the size of the string after encoding.
This document expands the definition of string literals by permitting
them to begin other than on a byte boundary. An "N-bit prefix string
literal" begins mid-byte, with the first (8-N) bits allocated to a
previous field. The string uses one bit for the Huffman flag,
followed by the Length encoded as an (N-1)-bit prefix integer. The
prefix size, N, can have a value between 2 and 8 inclusive. The
remainder of the string literal is unmodified.
A string literal without a prefix length noted is an 8-bit prefix
string literal and follows the definitions in [RFC7541] without
modification.
4.2. Encoder and Decoder Streams
QPACK defines two unidirectional stream types:
* An encoder stream is a unidirectional stream of type 0x02. It
carries an unframed sequence of encoder instructions from encoder
to decoder.
* A decoder stream is a unidirectional stream of type 0x03. It
carries an unframed sequence of decoder instructions from decoder
to encoder.
HTTP/3 endpoints contain a QPACK encoder and decoder. Each endpoint
MUST initiate at most one encoder stream and at most one decoder
stream. Receipt of a second instance of either stream type MUST be
treated as a connection error of type H3_STREAM_CREATION_ERROR.
These streams MUST NOT be closed. Closure of either unidirectional
stream type MUST be treated as a connection error of type
H3_CLOSED_CRITICAL_STREAM.
An endpoint MAY avoid creating an encoder stream if it will not be
used (for example if its encoder does not wish to use the dynamic
table, or if the maximum size of the dynamic table permitted by the
peer is zero).
An endpoint MAY avoid creating a decoder stream if its decoder sets
the maximum capacity of the dynamic table to zero.
An endpoint MUST allow its peer to create an encoder stream and a
decoder stream even if the connection's settings prevent their use.
4.3. Encoder Instructions
An encoder sends encoder instructions on the encoder stream to set
the capacity of the dynamic table and add dynamic table entries.
Instructions adding table entries can use existing entries to avoid
transmitting redundant information. The name can be transmitted as a
reference to an existing entry in the static or the dynamic table or
as a string literal. For entries that already exist in the dynamic
table, the full entry can also be used by reference, creating a
duplicate entry.
4.3.1. Set Dynamic Table Capacity
An encoder informs the decoder of a change to the dynamic table
capacity using an instruction that starts with the '001' 3-bit
pattern. This is followed by the new dynamic table capacity
represented as an integer with a 5-bit prefix; see Section 4.1.1.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | Capacity (5+) |
+---+---+---+-------------------+
Figure 5: Set Dynamic Table Capacity
The new capacity MUST be lower than or equal to the limit described
in Section 3.2.3. In HTTP/3, this limit is the value of the
SETTINGS_QPACK_MAX_TABLE_CAPACITY parameter (Section 5) received from
the decoder. The decoder MUST treat a new dynamic table capacity
value that exceeds this limit as a connection error of type
QPACK_ENCODER_STREAM_ERROR.
Reducing the dynamic table capacity can cause entries to be evicted;
see Section 3.2.2. This MUST NOT cause the eviction of entries that
are not evictable; see Section 2.1.1. Changing the capacity of the
dynamic table is not acknowledged as this instruction does not insert
an entry.
4.3.2. Insert With Name Reference
An encoder adds an entry to the dynamic table where the field name
matches the field name of an entry stored in the static or the
dynamic table using an instruction that starts with the '1' 1-bit
pattern. The second ('T') bit indicates whether the reference is to
the static or dynamic table. The 6-bit prefix integer
(Section 4.1.1) that follows is used to locate the table entry for
the field name. When T=1, the number represents the static table
index; when T=0, the number is the relative index of the entry in the
dynamic table.
The field name reference is followed by the field value represented
as a string literal; see Section 4.1.2.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | T | Name Index (6+) |
+---+---+-----------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+
Figure 6: Insert Field Line -- Indexed Name
4.3.3. Insert With Literal Name
An encoder adds an entry to the dynamic table where both the field
name and the field value are represented as string literals using an
instruction that starts with the '01' 2-bit pattern.
This is followed by the name represented as a 6-bit prefix string
literal, and the value represented as an 8-bit prefix string literal;
see Section 4.1.2.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | H | Name Length (5+) |
+---+---+---+-------------------+
| Name String (Length bytes) |
+---+---------------------------+
| H | Value Length (7+) |
+---+---------------------------+
| Value String (Length bytes) |
+-------------------------------+
Figure 7: Insert Field Line -- New Name
4.3.4. Duplicate
An encoder duplicates an existing entry in the dynamic table using an
instruction that starts with the '000' 3-bit pattern. This is
followed by the relative index of the existing entry represented as
an integer with a 5-bit prefix; see Section 4.1.1.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | Index (5+) |
+---+---+---+-------------------+
Figure 8: Duplicate
The existing entry is re-inserted into the dynamic table without
resending either the name or the value. This is useful to avoid
adding a reference to an older entry, which might block inserting new
entries.
4.4. Decoder Instructions
A decoder sends decoder instructions on the decoder stream to inform
the encoder about the processing of field sections and table updates
to ensure consistency of the dynamic table.
4.4.1. Section Acknowledgment
After processing an encoded field section whose declared Required
Insert Count is not zero, the decoder emits a Section Acknowledgment
instruction. The instruction starts with the '1' 1-bit pattern,
followed by the field section's associated stream ID encoded as a
7-bit prefix integer; see Section 4.1.1.
This instruction is used as described in Section 2.1.4 and in
Section 2.2.2.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 1 | Stream ID (7+) |
+---+---------------------------+
Figure 9: Section Acknowledgment
If an encoder receives a Section Acknowledgment instruction referring
to a stream on which every encoded field section with a non-zero
Required Insert Count has already been acknowledged, this MUST be
treated as a connection error of type QPACK_DECODER_STREAM_ERROR.
The Section Acknowledgment instruction might increase the Known
Received Count; see Section 2.1.4.
4.4.2. Stream Cancellation
When a stream is reset or reading is abandoned, the decoder emits a
Stream Cancellation instruction. The instruction starts with the
'01' 2-bit pattern, followed by the stream ID of the affected stream
encoded as a 6-bit prefix integer.
This instruction is used as described in Section 2.2.2.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 1 | Stream ID (6+) |
+---+---+-----------------------+
Figure 10: Stream Cancellation
4.4.3. Insert Count Increment
The Insert Count Increment instruction starts with the '00' 2-bit
pattern, followed by the Increment encoded as a 6-bit prefix integer.
This instruction increases the Known Received Count (Section 2.1.4)
by the value of the Increment parameter. The decoder should send an
Increment value that increases the Known Received Count to the total
number of dynamic table insertions and duplications processed so far.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| 0 | 0 | Increment (6+) |
+---+---+-----------------------+
Figure 11: Insert Count Increment
An encoder that receives an Increment field equal to zero, or one
that increases the Known Received Count beyond what the encoder has
sent MUST treat this as a connection error of type
QPACK_DECODER_STREAM_ERROR.
4.5. Field Line Representations
An encoded field section consists of a prefix and a possibly empty
sequence of representations defined in this section. Each
representation corresponds to a single field line. These
representations reference the static table or the dynamic table in a
particular state, but do not modify that state.
Encoded field sections are carried in frames on streams defined by
the enclosing protocol.
4.5.1. Encoded Field Section Prefix
Each encoded field section is prefixed with two integers. The
Required Insert Count is encoded as an integer with an 8-bit prefix
using the encoding described in Section 4.5.1.1. The Base is encoded
as a sign bit ('S') and a Delta Base value with a 7-bit prefix; see
Section 4.5.1.2.
0 1 2 3 4 5 6 7
+---+---+---+---+---+---+---+---+
| Required Insert Count (8+) |
+---+---------------------------+
| S | Delta Base (7+) |
+---+---------------------------+
| Encoded Field Lines ...
+-------------------------------+
Figure 12: Encoded Field Section
4.5.1.1. Required Insert Count
Required Insert Count identifies the state of the dynamic table
needed to process the encoded field section. Blocking decoders use
the Required Insert Count to determine when it is safe to process the
rest of the field section.
The encoder transforms the Required Insert Count as follows before
encoding:
if ReqInsertCount == 0:
EncInsertCount = 0
else:
EncInsertCount = (ReqInsertCount mod (2 * MaxEntries)) + 1
Here "MaxEntries" is the maximum number of entries that the dynamic
table can have. The smallest entry has empty name and value strings
and has the size of 32. Hence "MaxEntries" is calculated as
MaxEntries = floor( MaxTableCapacity / 32 )
"MaxTableCapacity" is the maximum capacity of the dynamic table as
specified by the decoder; see Section 3.2.3.
This encoding limits the length of the prefix on long-lived