Re: QPACK proposal: wrap absolute index values

Dmitri Tikhonov <dtikhonov@litespeedtech.com> Mon, 06 August 2018 04:36 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 68F07130E8C for <quic@ietfa.amsl.com>; Sun, 5 Aug 2018 21:36:16 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.911
X-Spam-Level:
X-Spam-Status: No, score=-1.911 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, T_DKIMWL_WL_MED=-0.01] autolearn=ham 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 LNAlR9U4hjEI for <quic@ietfa.amsl.com>; Sun, 5 Aug 2018 21:36:14 -0700 (PDT)
Received: from mail-qt0-x234.google.com (mail-qt0-x234.google.com [IPv6:2607:f8b0:400d:c0d::234]) (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 8B48A130DC1 for <quic@ietf.org>; Sun, 5 Aug 2018 21:36:14 -0700 (PDT)
Received: by mail-qt0-x234.google.com with SMTP id h4-v6so12434064qtj.7 for <quic@ietf.org>; Sun, 05 Aug 2018 21:36:14 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=litespeedtech-com.20150623.gappssmtp.com; s=20150623; h=date:from:to:cc:subject:message-id:mail-followup-to:references :mime-version:content-disposition:in-reply-to:user-agent; bh=Z/fr9rVn3tT83UMyCndQL8h7qZwnQdtgZtAfM+zJvG0=; b=o5vmMgNUZSnLud7qXD0X9ZxgBNGNOhzkJmrjyOk0CnFPa1LV90AQobo1NbnC+Qsx+e vJ4uPrAWCS9x6WrzMemexYZAKTcuqw9w6c+Diu2DqPe9Ftke23BwyU4YjvOHpaKSYYEC R+/iIl+GcP8Tb2dbIQt2vRLtLQZ13YCM7mEGUqhWCcsbX+dFwM+Ki4FFhnF9aAmwUscV IRUnFmE/L/1K/xRESZv8ngHUHzwmqudiwi7mSMLvPg93+1PjqFYYjQ0NuXH6HqVF55vE 7d/IRI7oiatQj5V3KbzpHAgLpjtaAWkL2ezxvlUNAFGy5XJ4amIl0Q3YuUrrhM/SW4q+ YD1g==
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:cc:subject:message-id :mail-followup-to:references:mime-version:content-disposition :in-reply-to:user-agent; bh=Z/fr9rVn3tT83UMyCndQL8h7qZwnQdtgZtAfM+zJvG0=; b=ZImSvmS9oPxRZQPLg5VU7xjY4ey8wGc0FKJFNdu3BMdm7gs3tgchf7yEP2XvojUlwt oDo0QIwpubglivqb1Hc4uMbD/O/8hiRfsRXClyQ37xgEpXHSXx+AcdtHtBOO4kQyhbjl U9qOGz/j7gsUHXvMpCIYmTHpBNfF8RiKY2rn659jrOci3rrLJeLKcGo9qsDrPqKtSVPI ZfHI+Jtu16k8No4Lc57LTt0GMsXKEdT4ER2yvgPhAXWbqcfmyryLvt72EER4EhGo6MYg XWKi1aAB8o17MTmpRMrEiYPID1iK0+5IpAq11ILVIktT4GGkZttXjQzyDopoa6ubq+Ax k7fg==
X-Gm-Message-State: AOUpUlFT0IUHHyLi+3yhoxEBmJ/GzwIUCVgRWywrG38gx14kRFId5UJT nQSHEiweoaFmIPmteMl2U7qzXA==
X-Google-Smtp-Source: AAOMgpdLpgQMZI0yESX6QR4pdTWrIasYUydM2sXaBrKe+MZ+/c1ezkzwQhd0B0Sjxk7CBUBmrFkUMA==
X-Received: by 2002:aed:235a:: with SMTP id i26-v6mr12813136qtc.382.1533530173695; Sun, 05 Aug 2018 21:36:13 -0700 (PDT)
Received: from ubuntu-dmitri (ool-44c1d219.dyn.optonline.net. [68.193.210.25]) by smtp.gmail.com with ESMTPSA id i1-v6sm5021488qtj.65.2018.08.05.21.36.12 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sun, 05 Aug 2018 21:36:13 -0700 (PDT)
Date: Mon, 6 Aug 2018 00:36:11 -0400
From: Dmitri Tikhonov <dtikhonov@litespeedtech.com>
To: Martin Thomson <martin.thomson@gmail.com>
Cc: QUIC WG <quic@ietf.org>
Subject: Re: QPACK proposal: wrap absolute index values
Message-ID: <20180806043610.GC25402@ubuntu-dmitri>
Mail-Followup-To: Martin Thomson <martin.thomson@gmail.com>, QUIC WG <quic@ietf.org>
References: <20180805154649.GA14245@ubuntu-dmitri> <CABkgnnV2Ugu6O_6Q8grjhQiqavUe6P8FVP_BNRuNqtzVXTbOgw@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CABkgnnV2Ugu6O_6Q8grjhQiqavUe6P8FVP_BNRuNqtzVXTbOgw@mail.gmail.com>
User-Agent: Mutt/1.5.24 (2015-08-30)
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/EPtl8YrXbyEhrus3Ls37udVf74I>
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 04:36:17 -0000

On Mon, Aug 06, 2018 at 10:29:50AM +1000, Martin Thomson wrote:
> 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

My thinking is that there is no need to reconstruct the Largest
Reference, as the encoded value represents the actual absolute
index.  It is its interpretation that requires some logic.

One way to think about it is whether the absolute index is in the
Past or the Future -- as it is always either one or the other.

        The window is 2 * MaxEntries wide

 1                                        2 * MaxEntries

 |--------------------------------------------|

If the current maximum absolute index has the value MaxEntries, all
values to its left are in the Past, while all entries to the right
are in the Future:

    <-- Past ---------\ /---- Future --->
 |----------------- CurMax -------------------|

If CurMax is larger than or equal to than MaxEntries, the Past region is
contiguous.  If CurMax is smaller than or equal to MaxEntries, the Future
region is contiguous.

The code is

    bool
    isHeaderBlocked (unsigned LargestRef)
    {
        if (CurMax <= MaxEntries)
            return LargestRef > CurMax
                                && LargestRef <= CurMax + MaxEntries;
        else
            return !(LargestRef <= CurMax
                                && LargestRef > CurMax - MaxEntries + 1);
    }


  - Dmitri.