Re: QPACK proposal: wrap absolute index values

Martin Thomson <martin.thomson@gmail.com> Wed, 08 August 2018 21:32 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 02A03130E25 for <quic@ietfa.amsl.com>; Wed, 8 Aug 2018 14:32:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 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, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001] autolearn=ham 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 XYw_gDKbSjKh for <quic@ietfa.amsl.com>; Wed, 8 Aug 2018 14:32:13 -0700 (PDT)
Received: from mail-oi0-x22e.google.com (mail-oi0-x22e.google.com [IPv6:2607:f8b0:4003:c06::22e]) (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 EB3CA130E14 for <quic@ietf.org>; Wed, 8 Aug 2018 14:32:12 -0700 (PDT)
Received: by mail-oi0-x22e.google.com with SMTP id n21-v6so6351600oig.3 for <quic@ietf.org>; Wed, 08 Aug 2018 14:32:12 -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=oFfZef+kVlnTKxzLbvPcwh+qQyI/w7dcAyONeFjQjLw=; b=HUS8P/SuVc3MkpnTsauucC3Z5Tu2kNmS95ocpMbqbcmPKhy5rV9LEbb68fxnViUOEz ay7+be+q9LBgGbvqbhLUkUkLlkUAETINWQlByquRvs8Ob3Z15z34eavdDi3WrvskZ0pb dLGLP31xPVl0jlZaUGvquARIHYToN9iPpxQE/W+biHvKjc+YCj+2N+rLd5GxTu26Ai3d kohV7PDGchpi9TANnvbail6VRpnV5gOdUjguLzAtd1gVHHaLqm0uSic+IhIw9Au6wjjh zn3MjuhNgTjBsKtElTyfnJjnMqmFZD+ILn+El9bIlemyb9kqdWDGoWAM6fM8zz5WGwW9 op5A==
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=oFfZef+kVlnTKxzLbvPcwh+qQyI/w7dcAyONeFjQjLw=; b=Dq8ybsLW0A6uZGeHD1npwF/PImoIh8SxsyOsaAlxr53xpfS+Ael5qdYz5sydOLXBDm 0yxwVdc/62NSMu5ngQiPqUuRLVNWEnWOqOVDDi5M6MP1tR77s+0ALupC2m7D97xgRPTN 5MKBnqNwYtrjSWaUgbMETNfq5dpXo2jKhLW+P5RlZ6Hl2Z4/N3YFYA1uFvh0Q+23r9rt qzSuTnkHWKzFgxX3f5BqAz2L74ITcHpiZzEBx/J4tL2ujkWj/nThh93xwVwf+ges78om +ddMOWOfz6v+SrOaeK9xBmXyiABuXGBaTmqO0l3z3cGT70SVBKryo9XtF6WzOY7w9g8d fOGg==
X-Gm-Message-State: AOUpUlFvj339AghZrxhJyBaT87tg195fyMsly31J1HjhRxRu9znWJJE9 KfEx52ziIjoIYwA3EeWcaWWveEaJxbX+duTAKVHY1w==
X-Google-Smtp-Source: AA+uWPw3jUbM/Q1rDjDmYnlrBPR5Ci0DIuuaxZJuxCrO+yMWfLaYEJfPIciC5N4CkAtSRz2ssA1fuNu02Zx5bZTc0lA=
X-Received: by 2002:aca:100f:: with SMTP id 15-v6mr4904891oiq.110.1533763931917; Wed, 08 Aug 2018 14:32:11 -0700 (PDT)
MIME-Version: 1.0
References: <20180805154649.GA14245@ubuntu-dmitri> <CABkgnnV2Ugu6O_6Q8grjhQiqavUe6P8FVP_BNRuNqtzVXTbOgw@mail.gmail.com> <20180806043610.GC25402@ubuntu-dmitri> <20180806044626.GD25402@ubuntu-dmitri> <CABkgnnWA8ZzrKzjZ-hQ1Qk3yOtgtcmwNuFwkJEP3DnqqqnCkBA@mail.gmail.com> <20180806121947.GA31889@ubuntu-dmitri>
In-Reply-To: <20180806121947.GA31889@ubuntu-dmitri>
From: Martin Thomson <martin.thomson@gmail.com>
Date: Thu, 9 Aug 2018 07:32:01 +1000
Message-ID: <CABkgnnVJYnmr+=xgzDSExZs4c5342iN2tv=YS3Fa0qz0Yabtvw@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/i4lOlk5UX29kpMrLlagL6jocHXo>
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: Wed, 08 Aug 2018 21:32:15 -0000

So this is a really interesting idea, but I did a triage yesterday and
missed it.  Dmitri, would you mind creating an issue for this?
On Mon, Aug 6, 2018 at 10:19 PM Dmitri Tikhonov
<dtikhonov@litespeedtech.com> wrote:
>
> On Mon, Aug 06, 2018 at 04:52:34PM +1000, Martin Thomson wrote:
> > On Mon, Aug 6, 2018 at 2:46 PM Dmitri Tikhonov
> > <dtikhonov@litespeedtech.com> wrote:
> > >       bool
> > >       isHeaderBlocked (unsigned LargestRef)
> >
> > Thanks for sharing code.  Note that I'm not just interested in whether
> > I'm blocked, but for how many table updates I should block for, but I
> > can use this function (repeatedly if necessary) to make that
> > determination, I guess.
>
> Well, that's just pseudo-code, you know.  I'd never CamelCase real
> code!
>
> > It took me ages to understand this code.  Are you expecting all the
> > arithmetic for CurMax to be modulo MaxEntries*2 ?  Because if that is
> > the case, then this makes sense.  Without that stipulation, I really
> > struggled.
>
> Yes, all the arithmetic for the absolute index is modulo MaxEntries * 2.
>
> > 2. You can't receive a header block with a largest reference that is
> > more than MaxEntries new.  This doesn't hold because we don't cap the
> > amount that a header block can be blocked by.
>
> This is true -- my assertion about the future horizon is incorrect.
> Somehow I assumed that the mirror argument about the encoder worked,
> but it does not.  For example, nothing prevents the encoder from
> pumping the table full of speculative updates, maybe even a few times
> over, before ever using it.
>
> > Now, it's arguably a
> > reasonable restriction, because it takes multiple round trips to reach
> > a state where that header block can be used, but we don't currently
> > prevent someone from doing something like that.
> >
> > Now, it's reasonable to assume that you can't have more than
> > MaxEntries worth of updates in flight, which means that in one round
> > trip, this will never happen.  But we don't say that you can't
> > reference dynamic table entries that are far in the future.  For this
> > to work, we would have to prohibit that.  Maybe we should, because
> > referencing entries that can't be sent is a footgun, just as
> > referencing entries that have not yet been sent is a footgun (it can
> > deadlock flow control if you do that).
>
> Yes, for the proposed mechanism to work, we'd have to mandate that the
> encoder not create new entries past some limit, which is a function of
> the known decoder state (based on TSS or Header Acks) and MaxEntries.
>
> Thanks for identifying this flaw.  The change is larger than I was
> hoping it would be.  It's still worth it.
>
>   - Dmitri.