[quicwg/base-drafts] 3+ and 4+ in the QPACK wire format are complex and inefficient (#3561)

Kazu Yamamoto <notifications@github.com> Tue, 31 March 2020 01:22 UTC

Return-Path: <noreply@github.com>
X-Original-To: quic-issues@ietfa.amsl.com
Delivered-To: quic-issues@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A7ED03A1731 for <quic-issues@ietfa.amsl.com>; Mon, 30 Mar 2020 18:22:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.199
X-Spam-Level:
X-Spam-Status: No, score=-1.199 tagged_above=-999 required=5 tests=[DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_IMAGE_ONLY_32=0.001, HTML_MESSAGE=0.001, MAILING_LIST_MULTI=-1, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=github.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id wEM3UO0OSuYc for <quic-issues@ietfa.amsl.com>; Mon, 30 Mar 2020 18:22:03 -0700 (PDT)
Received: from out-7.smtp.github.com (out-7.smtp.github.com [192.30.252.198]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 898753A1726 for <quic-issues@ietf.org>; Mon, 30 Mar 2020 18:21:54 -0700 (PDT)
Date: Mon, 30 Mar 2020 18:21:53 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=github.com; s=pf2014; t=1585617713; bh=yqqP8r7YamOV15A0+dBhO2pQQuucm2gaVDhSdOj5wbg=; h=Date:From:Reply-To:To:Cc:Subject:List-ID:List-Archive:List-Post: List-Unsubscribe:From; b=Q/MUv9HRFLx8mnGQiNgDKYdxH3wJ6ZrEEZy8MN1HEbCJDc98CSf/swKWSvtzNAjFj i+L5fnnjYmBihiTx1oVlJMebxswn5oIDeUKovB74Ip7W84P4rNDGu3a3VxRn4qfqhs +vpx+uGKC5q7YgIEvKuEjxiCbt4XIju84EEtSfkU=
From: Kazu Yamamoto <notifications@github.com>
Reply-To: quicwg/base-drafts <reply+AFTOJK5KVOBLSSKZ4R24W4N4RZ6DDEVBNHHCGNMNEI@reply.github.com>
To: quicwg/base-drafts <base-drafts@noreply.github.com>
Cc: Subscribed <subscribed@noreply.github.com>
Message-ID: <quicwg/base-drafts/issues/3561@github.com>
Subject: [quicwg/base-drafts] 3+ and 4+ in the QPACK wire format are complex and inefficient (#3561)
Mime-Version: 1.0
Content-Type: multipart/alternative; boundary="--==_mimepart_5e829b3196629_616e3fe753ccd95c593110"; charset=UTF-8
Content-Transfer-Encoding: 7bit
Precedence: list
X-GitHub-Sender: kazu-yamamoto
X-GitHub-Recipient: quic-issues
X-GitHub-Reason: subscribed
X-Auto-Response-Suppress: All
X-GitHub-Recipient-Address: quic-issues@ietf.org
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic-issues/btSN1nTMdyfXW8YwPbteFWFwd48>
X-BeenThere: quic-issues@ietf.org
X-Mailman-Version: 2.1.29
List-Id: Notification list for GitHub issues related to the QUIC WG <quic-issues.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic-issues>, <mailto:quic-issues-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic-issues/>
List-Post: <mailto:quic-issues@ietf.org>
List-Help: <mailto:quic-issues-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic-issues>, <mailto:quic-issues-request@ietf.org?subject=subscribe>
X-List-Received-Date: Tue, 31 Mar 2020 01:22:05 -0000

For instance, QPACK uses the following wire format:

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | N | H |NameLen(3+)|
+---+---+---+---+---+-----------+
|  Name String (Length bytes)   |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
|  Value String (Length bytes)  |
+-------------------------------+
```

The designers of QPACK make use of 3 bits of the flag part. But HPACK uses the following wire format:

```
0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 |       0       |
+---+---+-----------------------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length octets)  |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
| Value String (Length octets)  |
+-------------------------------+
```

The designers of HPACK did not use 4 bits and chose 7+ for name length.

Let's calculate integer ranges of one/two/three bytes for each N+:

```
N+   1   2     3 <- bytes
8  127 382 16638
7   63 254 16510
6   31 190 16446
5   15 158 16414
4    7 142 16398
3    3 134 16390
2    1 130 16386
1    0 128 16384
```

One byte of 3+ can only express 0 - 3. In most cases, two bytes of 3+ are necessary for the length of header names. 

So, why don't we use 7+ for simplicity?

```
  0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| 0 | 0 | 1 | N | H |     0     |
+---+---+---+---+---+-----------+
| H |     Name Length (7+)      |
+---+---------------------------+
|  Name String (Length bytes)   |
+---+---------------------------+
| H |     Value Length (7+)     |
+---+---------------------------+
|  Value String (Length bytes)  |
+-------------------------------+
```

This keeps the length of wire format in most cases and enables us to reuse the code of HPACK.


-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/3561