Re: QPACK proposal: wrap absolute index values

Martin Thomson <martin.thomson@gmail.com> Mon, 06 August 2018 00:30 UTC

Return-Path: <martin.thomson@gmail.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 3E321130DC6 for <quic@ietfa.amsl.com>; Sun, 5 Aug 2018 17:30:04 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 3
X-Spam-Level: ***
X-Spam-Status: No, score=3 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, GB_SUMOF=5, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 jRXOagXN4C1d for <quic@ietfa.amsl.com>; Sun, 5 Aug 2018 17:30:02 -0700 (PDT)
Received: from mail-oi0-x22f.google.com (mail-oi0-x22f.google.com [IPv6:2607:f8b0:4003:c06::22f]) (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 4F950130DC2 for <quic@ietf.org>; Sun, 5 Aug 2018 17:30:02 -0700 (PDT)
Received: by mail-oi0-x22f.google.com with SMTP id n21-v6so19242500oig.3 for <quic@ietf.org>; Sun, 05 Aug 2018 17:30:02 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=pmvUGyWHBzCWLskHjSCvhNvdIZ/Hbak3KaNV9eo4fUY=; b=TfdXoNh6QQh+laBXL0Z77wTj4OXOewv1ucYamWR5SMSLQzTXWwZYQBC6PO5FGWX9by kEkgGpMul05tfUeBB1Gak+1Vl/sqU0x72o3lVUbHCGUIwhDbeUYSbiVXwQPqjioKZLyZ beNyJFzDBLOt+66t/1J3dB7xXnwrFclS8z5sssL3waauQuMFD16Sa2ULYqPzf0pxt9NN zDtVMkUNJyuJa9n/atuQxx/A1Lwpy/YHOR9hT4NbqtB1kYAcgYQVoH3uygmi9FOJ4Cfd 8Lc6SizOH6tHoVEQTq7jyz1Bcbh4v4GW2q4d95679mh7JoFh1RTgnS6Ka9QCKfBKXmIx pOrg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=pmvUGyWHBzCWLskHjSCvhNvdIZ/Hbak3KaNV9eo4fUY=; b=Tx+3pp33ENoZc71p0QOYQDnWJbMLVcmarHmMWSIuskqL0NhDi/OOuHTiCJEJakeo+e UtZBF1Ev88zQThTQm9UL9ZSWN0yx1ZG/qziee838s5ATQRCDw4/gQtlOoJIWEw5OjsfG saxm7q9HKbQHZSuACuqQX1yh5bQDXQCpSuocZ1FS8tD7z+IpR+vGhPznB9zKcEv8sblR FYWKeAzbEuS06HH2xzUW9dEsvrkd2KJoNbIyt4/fapDsrv4rlIZup19xgewfQiiQEsoy bIm8nc1v43dbXaPEeaYqfKYuDUWzwyN9gWu76+pkIjzOTGdLiFfHB666UFX0OWfBTtUy 7Ypg==
X-Gm-Message-State: AOUpUlEYzW73eYvg2wlEefQEnPdy8s0h3tDhQvc+wK+FevwLUbq1xpjx VVUnzq/EDsw4flWpbDSvGfNjfcoWjZa5yIyf0+t+dwXy
X-Google-Smtp-Source: AA+uWPzKCzZERROzyv6sDxR5UfKHkiUxSp/tBcCqxneoDCVZ087QMZjPGb8k03d/FzWj5Ftg2RRV+/zqisQz+Mnccs8=
X-Received: by 2002:aca:b208:: with SMTP id b8-v6mr11798471oif.144.1533515401370; Sun, 05 Aug 2018 17:30:01 -0700 (PDT)
MIME-Version: 1.0
References: <20180805154649.GA14245@ubuntu-dmitri>
In-Reply-To: <20180805154649.GA14245@ubuntu-dmitri>
From: Martin Thomson <martin.thomson@gmail.com>
Date: Mon, 6 Aug 2018 10:29:50 +1000
Message-ID: <CABkgnnV2Ugu6O_6Q8grjhQiqavUe6P8FVP_BNRuNqtzVXTbOgw@mail.gmail.com>
Subject: Re: QPACK proposal: wrap absolute index values
To: QUIC WG <quic@ietf.org>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/nAHIyuAMS_ie3bOE5pxGij3IM_E>
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: Mon, 06 Aug 2018 00:30:04 -0000

Table State Synchronize is relative, so it wouldn't benefit from a
change here.  That's something I missed initially, so it's probably a
candidate for clearer text.

I've no real opinion on the wrapping proposal.  It seems like it might
work for the Largest Reference.  The math is a tiny bit annoying to
decode in the same way the packet number encoding is, but it is
doable.  I imagine that you reconstruct the Largest Reference based on
the smallest index in the table.  That is:

rotation = floor(table_size / 32)
base = minimum - (minimum % rotation)
# equivalently: base = floor(minimum / rotation) * rotation
largest = encoded + base
if largest < minimum:
  largest += rotation
On Mon, Aug 6, 2018 at 1:47 AM Dmitri Tikhonov
<dtikhonov@litespeedtech.com> wrote:
>
> 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
>