Re: Proposal: drop QPACK encoder stream framing

Kazuho Oku <kazuhooku@gmail.com> Fri, 08 June 2018 21:44 UTC

Return-Path: <kazuhooku@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 E0721130934 for <quic@ietfa.amsl.com>; Fri, 8 Jun 2018 14:44:26 -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 P2N-qSuqtBGM for <quic@ietfa.amsl.com>; Fri, 8 Jun 2018 14:44:25 -0700 (PDT)
Received: from mail-pf0-x233.google.com (mail-pf0-x233.google.com [IPv6:2607:f8b0:400e:c00::233]) (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 5E02C129385 for <quic@ietf.org>; Fri, 8 Jun 2018 14:44:25 -0700 (PDT)
Received: by mail-pf0-x233.google.com with SMTP id b17-v6so7263602pfi.0 for <quic@ietf.org>; Fri, 08 Jun 2018 14:44:25 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=cP/jjiUuMp4KUlwn68ExiWpY0bf/PHADBposgxkOrXY=; b=r4uSz/8w0dtrUaL7FFw7xUJTGhH06hWa9cF4kNx+BrXeIS/X1Q25gRsw/sIJQb/mRT l2lhugoWMdMhM+6QyTLYqOa6koJgd1uyooXhV2WjUlJQof2WF+bLwfzSFMJ8tUH/OXZy 9N2nmGbAlKDCYWq1K8saaY1g+7RiHyiMARpL+bZu1fn5w+EezSA8mEMfF6Cv5eiUkZaG ZwJvQPrA5QB+nQhTj5VPFnzni38MQ5WH4KY/auQnJiNoYinCHnGY3cs7BOcVQUVhrbVZ DtUqxqTFBwGXm2sHRW0RiZXPYKuvva0dgSxFr37+/R+Q6b9eigy7tXsbTgZ0KGMji1Q9 wqtg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=cP/jjiUuMp4KUlwn68ExiWpY0bf/PHADBposgxkOrXY=; b=cYqFzhfsfTUUM2oMYehrVdfgUbXcFvGAot+PUtnm9htLsaoPiHlP01KxpNAQv8haGX +kboCnZBZYO691Jud5LpD5B0Q3mJ5rEghnYOSCVICirUYeqiv+3MjBy8KtFKjItpAfGI 9t195HD8wcIByHTvJLzXmMJtXmp5j1fTaRTbKAwqh0rgVTLouCWDiCyNEalrdnygy0ZR TsmUQTmkA31nrYfgNfbyyjrtyz2zGs6+6VTx3fIf5RUqRB3U0KCmH+hczYM+RvZ+x14g +K58mjinXnY/Lm+RvctiObBnZd0TLxzaiCA0I4/CRGwp39LgDiDFlZs05fdY0WULPFE0 TbXA==
X-Gm-Message-State: APt69E13LZQHuwQJQ6Smwbdb5NBzcuB+BXp1ixuFeJfqOotEvN71UMPl ve7WAmzqEqSzQQhxk/R26uPMpGCdKA4dByIWvEI=
X-Google-Smtp-Source: ADUXVKLMlB8IABDWHny3aOTXGJfzE3te9QV9zFk+HSvcs4jIYDx5pMBW2b05Lm+8GEHLqwfL9/E/TcIfGbmOsv8Rq2k=
X-Received: by 2002:a63:a902:: with SMTP id u2-v6mr1656368pge.67.1528494264914; Fri, 08 Jun 2018 14:44:24 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a17:90a:1181:0:0:0:0 with HTTP; Fri, 8 Jun 2018 14:44:24 -0700 (PDT)
In-Reply-To: <F04D1BA6-8EC6-43EB-ABEC-34C4B30352AB@fb.com>
References: <20180607151112.GA28823@ubuntu-dmitri> <CABkgnnXbfkVbq6vCvud100h6wr3+9ir3iO7dD6-qaykOmK3JBQ@mail.gmail.com> <CANatvzzzXF8WCXgDCahTa_7JWZ1c1i-9rU_c8c9QWk5_O5u4Ow@mail.gmail.com> <F04D1BA6-8EC6-43EB-ABEC-34C4B30352AB@fb.com>
From: Kazuho Oku <kazuhooku@gmail.com>
Date: Sat, 9 Jun 2018 00:44:24 +0300
Message-ID: <CANatvzwr6fSER-tq+xLz_e9rOw+mj5RpdS5eb679Ds_3m=PnoA@mail.gmail.com>
Subject: Re: Proposal: drop QPACK encoder stream framing
To: Alan Frindell <afrind@fb.com>
Cc: Martin Thomson <martin.thomson@gmail.com>, QUIC WG <quic@ietf.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/O_qUvTx5KrF6Hmf-R-6gEJcGbgk>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.26
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: Fri, 08 Jun 2018 21:44:28 -0000

2018-06-08 23:49 GMT+03:00 Alan Frindell <afrind@fb.com>om>:
>     1a. buffer the entire frame, and then iterate though the instructions,
>     while checking for every instruction that it does not go beyond the
>     end of the frame
>     1b. iterate though the instructions as they arrive, while checking
>     that the entire instruction is available and that the instruction does
>     not go beyond the end of the frame
>
>     If we remove framing, the decoder can be implemented as:
>
>     2. iterate through the instructions as they arrive, while checking
>     that the entire instruction is available
>
> Consider the most complicated instruction, which is Inserting a pure literal (all fields have variable length)
>
> | Name Length | Name | Value Length | Value |

Thank you for bringing up the example. I think this is a very good
example, that would help us determine the complexity.

> When you know the length of the instruction block in advance, you know that an incomplete instruction is a decoding error which you can check as you decode, and fail immediately on underflow.  Here, you either need to do a trial decode of the variable lengths to see if you have enough bytes, or check while decoding, and decide whether you want to save the state for later or discard it and reparse from the beginning of the instruction.  I'm not even sure reparsing is workable since it might open you up to doing N^2 work -- at least you need to be careful how you implement it.  It's worth calling out that discovering the length of a QPACK varint is more complicated than a QUIC varint.

Because I think reparsing is the best strategy here, let me argue that
the worst case is not O(N^2).

Of course, in theory it is O(N^2), because there is no upper bound for
the integer representation. But the reality is that implementations
are required to have an upper bound. I'd assume that they would
typically only permit values that fit in a 32-bit (u)int (16-bit is
another option for some).

Note that such safe-guard is required even if we have framing.

RFC7541; section 5.1 specifically requires HPACK stacks to implement
such safe-guard:

   This integer representation allows for values of indefinite size.  It
   is also possible for an encoder to send a large number of zero
   values, which can waste octets and could be used to overflow integer
   values.  Integer encodings that exceed implementation limits -- in
   value or octet length -- MUST be treated as decoding errors.
   Different limits can be set for each of the different uses of
   integers, based on implementation constraints.

Considering these facts, I would argue that the worst case cost of
parsing a Literal header field will remain O(N), and that complexity
of the code will remain at least comparable to when having framing
(considering the fact that framing is a complexity by itself).

> It’s not impossible to solve of course.  “It’s just software” as Dmitri likes to say.  It’s just one piece of complexity I was hoping to avoid.

Yeah. It's a trade-off between having more layers to split the issues
vs. reducing the numbers of layers to minimize overall complexity.

>
> -Alan
>



-- 
Kazuho Oku