QPACK proposal: wrap absolute index values

Dmitri Tikhonov <dtikhonov@litespeedtech.com> Sun, 05 August 2018 15:47 UTC

Return-Path: <dtikhonov@litespeedtech.com>
X-Original-To: quic@ietfa.amsl.com
Delivered-To: quic@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id D81C5130E66 for <quic@ietfa.amsl.com>; Sun, 5 Aug 2018 08:47:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 3.09
X-Spam-Level: ***
X-Spam-Status: No, score=3.09 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, GB_SUMOF=5, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, T_DKIMWL_WL_MED=-0.01, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=litespeedtech-com.20150623.gappssmtp.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 wkmxzwB9u3k5 for <quic@ietfa.amsl.com>; Sun, 5 Aug 2018 08:47:00 -0700 (PDT)
Received: from mail-qt0-x22b.google.com (mail-qt0-x22b.google.com [IPv6:2607:f8b0:400d:c0d::22b]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id EA6B91277BB for <quic@ietf.org>; Sun, 5 Aug 2018 08:46:59 -0700 (PDT)
Received: by mail-qt0-x22b.google.com with SMTP id m13-v6so11262438qth.1 for <quic@ietf.org>; Sun, 05 Aug 2018 08:46:59 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=litespeedtech-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:subject:message-id:mail-followup-to:mime-version :content-disposition:user-agent; bh=7QFFcPRr17+C0zvGqTjpOEQve6b1gvQMJO64Em0YSyQ=; b=sfqs9lz30i+3MAxcpv/Q5GSQk05RWkM4Ml7SXK76XjtKNucfi19CROHRoz5ghl6AIX 1I5ZE/hRLO+8GngtLq2/e9Tb0mcWd8uG5m+j9r4aDh9MtrABtIUsfFS+4rzCDMOlCdSq HRD1aqb0TykSHucRUn49J4hiIPS/oAXC1f1iy5Fn/rQx+Ez5qWkU62R1tmyoY4SeCiWV afNPZxq0GKITnzFyzr9KxtmN78YejheW+r4LLpKB/dBgguUYVc26vGIbMwurgMsmJxWd rqHPd03EfNOnQWFxDhW93GEFmlQoybcue2NiIiY9OYfVMOIexaM9aezeKfzjuL3AXVD6 OtFg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:mail-followup-to :mime-version:content-disposition:user-agent; bh=7QFFcPRr17+C0zvGqTjpOEQve6b1gvQMJO64Em0YSyQ=; b=ll7UxYrM0JAazZMAIOjhcWW3yXdj8+v1L2oJvmxCFBJXZbDuFmq+arH5joySr8Gskl VJ5VWxQoNUDwgxFVomH3VlBkoXJ4d8O33gJ7n5piyGiuBFjFvdowieCS+GYUnOa/wehM QkOI0papiTsf+ZzVgxJikvSTIx494FyF2kuXD6SqLiT9S/UNksTR3rOZ424vtuRzU5BF z7V06uH3OhDD2OFKBb6q9aPgFqixR0qLSoPZZk4do+43q3NTz8trsiaMLYaKpIFgfO9W /h0ROxoi9TYnVAnU0lIcCQ+b3OKbbD7AJHCv+Ooe7ksseee2gNGwZXNXS5loUb76U52N h68Q==
X-Gm-Message-State: AOUpUlFSu8opbOHphPUFcsea9fMIprP0R9ddAoHAXrB+A2ze6dmKzRN4 GEl6xAOHg/JniJc5ClyVy3lslAkAKsk=
X-Google-Smtp-Source: AAOMgpdo8JBhRgy/kpFlJLukfCZVCHgfgJ1aiuCtog5EShAvqYBDtqMukMi0YiJFqPPjZRmi5DhXGg==
X-Received: by 2002:a0c:8d8e:: with SMTP id t14-v6mr10286614qvb.32.1533484018843; Sun, 05 Aug 2018 08:46:58 -0700 (PDT)
Received: from ubuntu-dmitri (ool-44c1d219.dyn.optonline.net. [68.193.210.25]) by smtp.gmail.com with ESMTPSA id a187-v6sm6727017qkd.47.2018.08.05.08.46.57 for <quic@ietf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 05 Aug 2018 08:46:58 -0700 (PDT)
Date: Sun, 5 Aug 2018 11:46:50 -0400
From: Dmitri Tikhonov <dtikhonov@litespeedtech.com>
To: IETF QUIC WG <quic@ietf.org>
Subject: QPACK proposal: wrap absolute index values
Message-ID: <20180805154649.GA14245@ubuntu-dmitri>
Mail-Followup-To: IETF QUIC WG <quic@ietf.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
User-Agent: Mutt/1.5.24 (2015-08-30)
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/GXqAGa0XCV_dMs1FYKJVh4JgLSU>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.27
Precedence: list
List-Id: Main mailing list of the IETF QUIC working group <quic.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic>, <mailto:quic-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic/>
List-Post: <mailto:quic@ietf.org>
List-Help: <mailto:quic-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic>, <mailto:quic-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 05 Aug 2018 15:47:02 -0000

Abstract
--------

The practical and theoretical problems caused by the unbounded absolute
index values in the current QPACK Internet Draft are discussed.  The
proposal to impose a limit on the range of absolute index values by
wrapping them is presented.

Background
----------

The current QPACK draft states that

   [the] first entry inserted has an absolute index of "1"; indices
   increase sequentially with each insertion.

No upper limit is specified.  This is reasonable, as it is impossible
to run out of numbers.

Nevertheless, an absolute index whose value is ever-increasing creates
significant problems.

Problem 1: Compression Impact
-----------------------------

A large absolute index value has a negative effect on compression.
There are two places in QPACK that use the unadjusted value of the
absolute index:

    - the Largest Reference field in the Header Data Prefix; and
    - the Table State Synchronize instruction.

Larger values mean that more bytes are necessary to encode them.
For example, using 8-bit prefix integer encoding, values larger than
254 encode to 2 bytes, larger than 382 to 3 bytes, and larger than
16638 to 4 bytes.

Relatively quickly, the overhead associated with communicating the
absolute index doubles and then triples.

Problem 2: Theoretical Concerns
-------------------------------

Why should compression at t(1) be worse than at t(0)?  An ability
to operate at the optimum level in perpetuity is a good property
for a protocol to have.

Problem 3: Implementation Efficiency
------------------------------------

A QPACK implementation has to place some limits on the value of the
absolute index -- simply because it has to pick an integral type to
store it.  For example, uint64_t is likely large enough for all uses of
the protocol, but it is wider than uint32_t and may be more expensive
to process.  On other platforms, uint16_t may be the fastest integer;
the unbounded nature of the absolute index would rule out its use.

Such limit also requires an extra check [1] to cease inserting entries
into the dynamic table once the maximum value for the integer is
reached.  (One can run out of numbers in practice...)

Solution: Have the Absolute Index Wrap Around
---------------------------------------------

The main insight of the proposal is that the dynamic table has a bounded
number of entries, that both encoder and decoder know what this number is,
and that both can use this information to place an absolute index value
communicated to it by its peer at the correct place in the sequence.

The dynamic table has a maximum size which is specified at the beginning
of the connection and which never changes afterwards.  The current size
of the table is the sum of all its entry sizes.  The entry size is the sum
of the fixed overhead plus the lengths of the name and the value strings.
It is this fixed entry overhead that places a hard limit on the number
of entries in the dynamic table:

    MaxEntries = MaxTableSize / FixedEntryOverhead

For example, using the current QPACK defaults, this number is

    MaxEntries = 4096 / 32 = 128

Imagine an encoder or decoder whose largest absolute index value (referred
to as the total number of insertions in the QPACK draft) is X.  The
smallest valid absolute index value its peer could possibly communicate
to it is X - MaxEntries + 1.  The largest value is X + MaxEntries.  (All
other values would indicate a bug at one or both sides.)  The maximum
size of the valid absolute index values window, then, is MaxEntries * 2.

Therefore, we can wrap the absolute index value without loss of
information.  The proposal is to limit the absolute index values to
the range

    [ 1, MaxEntries * 2 ]

Continuing with the QPACK defaults example above, the sequence would
go

    1, 2, 3, ... 254, 255, 256, 1, 2, ... (and so on).

The compression overhead cost is now a function of the maximum table
size (and not a function of time as before).

To continue with our example, out of 256 possible values, 254 encode
to 1 byte and 2 to two bytes.  A 64 KB table results in a maximum
encoding of 3 bytes, while a 1 MB table has a maximum encoding of 4
bytes.

Changes to the Draft
--------------------

The changes to the draft are small.  Only the definition of the
absolute index has to change; all instructions and encodings stay
the same.

Conclusion
----------

Limiting the range of values the absolute index can have improves
compression and implementation efficiency and removes the time penalty
from the QPACK protocol.  A mechanism to do just that using existing
QPACK parameters and with minimal changes to the draft has been proposed.
I suggest that it be examined for flaws.  If none be found, I say let's
include it in the next version of the QPACK Internet Draft.


  - Dmitri.

1. https://github.com/litespeedtech/ls-qpack/blob/122d1163eaca359f5d79cd608722b1b19acad15f/src/lsqpack.c#L1110