Exercises — HTTP - 2 — multiplexing, header compression (HPACK), server push

From the framing spec, the 9 bytes = 72 bits split as:

• Length — 24 bits
• Type — 8 bits
• Flags — 8 bits
• R (reserved) — 1 bit
• Stream ID — 31 bits

Check: $24+8+8+1+31=72$ bits $=9$ bytes. ✅

Client streams use odd IDs (1, 3, 5, …); server-pushed streams use even IDs (2, 4, 6, …). Why: both sides open streams on the same connection. If both could pick from the same pool, two independent choosers could pick the same number → collision. Splitting into odd/even is a zero-coordination way to guarantee the two never clash.

• HEADERS — carries the (HPACK-encoded) header block that begins a message.
• DATA — carries the body bytes.
• PUSH_PROMISE — announces a stream the server intends to push, reserving an even Stream ID.
• RST_STREAM — abruptly cancels one stream without touching the connection.

$2^{14}=16384$ bytes ($16$ KiB). The Length field could hold up to $2^{24}-1=16777215$ bytes, but the default cap is deliberately smaller. Why: if one frame could be huge, sending it would hog the single TCP connection for a long stretch — reintroducing the very head-of-line stall multiplexing exists to kill. Capping at 16 KiB means frames from other streams can slip in between.

The rule: if $I<2^N-1$ store $I$ directly in the $N$ bits. Here $N=5$, so $2^5-1=31$. Since $10<31$, we just write $10$ into the 5 bits. The 3 high bits of that byte are HPACK flag bits (they mark the representation type). One byte total. No continuation needed.

$2^5-1=31$ and $1337\ge 31$, so the prefix overflows.

1. Emit the prefix value $31$ (all 5 bits set).
2. Remainder $I^{\prime }=1337-31=1306$.
3. Split $1306$ into 7-bit groups, low group first, high bit = "more follow":
   • $1306=10\cdot 128+26$, so first continuation byte $=26+128=154$.
   • Next $I^{\prime }=10<128$, so final byte $=10$ (high bit clear = "last").

Byte sequence: 31, 154, 10 — three bytes.

Fully indexed = leading 1 bit, then the index in a 7-bit prefix. Index $2<2^7-1=127$, so it fits directly. The byte is 1 followed by 0000010: $\text{1}\Vert \text{0000010}=\text{0b10000010}=130$ One byte encodes the entire :method: GET line.

Per connection setup $=\text{TCP}+\text{TLS}=1+2=3$ RTTs.

• HTTP/1.1, 6 cold connections opened for one origin: the handshakes can overlap in time, but each connection still pays $3$ RTTs and each starts with a tiny cold congestion window. Setup RTTs per connection $=3$ RTT $=3\times 40=120$ ms.
• HTTP/2, 1 connection: $3$ RTT $=120$ ms — same handshake latency, but only one warmed congestion window instead of six cold ones.

The real win isn't the handshake number (both are $3$ RTTs of setup); it's that HTTP/2 pays it once and then reuses one properly-grown congestion window, while HTTP/1.1's six windows each start cold and compete. Total handshake work: HTTP/1.1 $=6\times 3=18$ RTT-connections of setup cost; HTTP/2 $=1\times 3=3$. Ratio $18/3=6\times$ less setup cost.

Setup: three streams (1, 3, 5) interleave DATA frames over one TCP connection. Suppose one TCP segment carrying part of stream 1 is lost on the network.

• TCP guarantees the application receives bytes in order. So TCP buffers everything that arrived after the lost segment — including the perfectly-intact frames for streams 3 and 5 — and refuses to hand them up until the lost segment is retransmitted (≈ 1 RTT later).
• At the HTTP/2 layer, streams are independent — nothing there blocks. But the block happens one layer below, at TCP (transport).

Conclusion: HTTP/2 removes application-layer HOL blocking but not transport-layer HOL blocking. HTTP/3 over QUIC gives each stream its own ordering, so a lost packet stalls only its own stream — see TCP for why in-order delivery forces the wait.

(a) HTTP/1.1: $200\times 100=20000$ bytes. (b) HPACK: request 1 sends the full literal ($\approx 200$ bytes) and stores it in the dynamic table; requests 2–100 each send a 1-byte index → $200+99\times 1=299$ bytes. Savings: $20000-299=19701$ bytes, a $20000/299\approx 66.9\times$ shrink.

1. HEADERS on Stream 1 — client's request for /index.html. Stream 1 is odd → client-initiated. ✅
2. PUSH_PROMISE on Stream 1 — announced on the requesting stream, reserving Stream 2 (even → server-initiated) for the pushed resource.
3. HEADERS on Stream 2 — response headers for /style.css.
4. DATA on Stream 2 — the CSS bytes.
5. HEADERS on Stream 1 — response headers for /index.html.
6. DATA on Stream 1 — the HTML bytes.

Key point: the promise rides the client's stream (1), but the pushed content lives on a fresh even stream (2), so it never collides with any odd client stream. When the parser discovers the <link> to style.css, it's already arriving/cached → round trip saved.

Each index $<127$, so each is a single fully-indexed byte: 1 || 7-bit index.

• idx 2 → 1 byte
• idx 4 → 1 byte
• idx 7 → 1 byte

Total $=3$ bytes for three whole header lines. (Compare: writing them as text would be dozens of bytes.)

Two HPACK properties break the attack:

1. No adaptive entropy coding across attacker+secret. HPACK's string compression uses a static Huffman table fixed in the spec, not an adaptive coder that shrinks when attacker text matches secret text. So the compressed length no longer signals "your guess matched a secret byte."
2. Indexing is per-whole-header, table-based. A secret cookie either is a table index (opaque, fixed 1 byte) or a literal — it isn't mixed byte-by-byte with attacker input the way gzip's sliding window would mix them.

Together these remove the length-vs-guess correlation CRIME exploited. The layer still needing its own protection is TLS (encryption/integrity of the whole connection); HPACK protects the compression side, TLS protects the confidentiality side. See CRIME-and-BREACH-attacks.

Encode (from L2.3): prefix $=31$; remainder $1306=10\cdot 128+26$ → bytes 31, 154, 10. Decode: prefix is all-ones ($31$) → start accumulator at $31$, then read continuation bytes:

• byte $154$: high bit set (subtract $128\Rightarrow 26$), add $26\cdot 128^0=26$. Accumulator $=31+26=57$. More follow.
• byte $10$: high bit clear → add $10\cdot 128^1=1280$, then stop. Accumulator $=57+1280=1337$. ✅

Recovered $1337$ — the encoding is lossless. This is the same varint idea: 7 data bits per byte, top bit = continuation flag.

Default frame payload $=2^{14}=16384$ bytes. Body $=2^{20}=1048576$ bytes. Number of frames $=2^{20}/2^{14}=2^6=64$ frames exactly. Representable in one frame? The Length field holds up to $2^{24}-1=16777215$ bytes, and $2^{20}=1048576\le 16777215$, so yes, a single 1 MiB frame is representable — but only if the peer raised SETTINGS_MAX_FRAME_SIZE. By default you'd send $64$ frames of $16$ KiB so no single frame monopolises the connection.

Odd Stream IDs belong to whom? ::: The client (client-initiated streams). Even Stream IDs belong to whom? ::: The server (pushed streams). Default max frame payload in bytes? ::: 16384 ($2^{14}$). HPACK's three mechanisms? ::: Static table, dynamic table, static Huffman coding. Which HOL blocking does HTTP/2 still suffer? ::: Transport-layer (TCP in-order delivery). The modern replacement for server push? ::: 103 Early Hints + link rel=preload.