Re: Proposal: drop QPACK encoder stream framing

Dmitri Tikhonov <dtikhonov@litespeedtech.com> Sat, 09 June 2018 15:55 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 A5BBD130EB2 for <quic@ietfa.amsl.com>; Sat, 9 Jun 2018 08:55:39 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.011
X-Spam-Level:
X-Spam-Status: No, score=-0.011 tagged_above=-999 required=5 tests=[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 m2OB8y92eQjJ for <quic@ietfa.amsl.com>; Sat, 9 Jun 2018 08:55:38 -0700 (PDT)
Received: from mail-qt0-x232.google.com (mail-qt0-x232.google.com [IPv6:2607:f8b0:400d:c0d::232]) (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 403E2126DBF for <quic@ietf.org>; Sat, 9 Jun 2018 08:55:38 -0700 (PDT)
Received: by mail-qt0-x232.google.com with SMTP id q6-v6so16453910qtn.7 for <quic@ietf.org>; Sat, 09 Jun 2018 08:55:38 -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:content-transfer-encoding :in-reply-to:user-agent; bh=kMhKUCKQF9tcQGwR9NfViYrAQesuQ/p8McxjVB9k9bI=; b=CRpsZH2FbXcFdX4nGg197ABDn0ZUOkLczMVrsTp+oftUKhrE5fY+mTtlApJOGOnv14 jXycKyKoAGYAb3azUx7KEYeWOcjbjk+3rF/Vh8RgqAy0JOp/vDGUNkW1eXglHAFgKXGH 7EDoNFtba8Oy3UeF0hAU6fjFLoJq01ZsU8TQOf9AfOz9UEUde+s5NtbB3kRRzKbK/Mfg LmtgfUQ/RP2KyX68TXyp7cUYkquNz4vr0wykY2eBunzNrHUuuGjxBdvtporCVBTrkZHH yYuHD1OXPbUIHXOD8CUA9AVOFnv8yQhLru11rlh95p7KQoHwTnGw3WXoa6pt1tWSKcW4 eHvg==
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 :content-transfer-encoding:in-reply-to:user-agent; bh=kMhKUCKQF9tcQGwR9NfViYrAQesuQ/p8McxjVB9k9bI=; b=THGJxtr1lfSKveFbchguUJvQRT5+xI+37vfNqAJXqVnYQmoUxnCkG90DquspaFVJdJ fs5ssKo+1WcYr0Rrj2scv4qGfCxfRfVPvCSrY2I5Ey8FJFedbSA52gXZ2p6if6GLe/J+ eDdbcEG3PnuVeWcuHJysjzPoOvOIhJCCD4kysu2BT7AbHfMiBz+6xXKw5cnxq1eGvyA3 wVk+LjdFzXhgZfJ8Vp6Uze3bMonShPrA0T8OEx8nkN8IwWk/Ts66cjwJgAUKMC2XFS1U aiRgjnron2En2MjdQko++/AK8VOa7EVsNNIE1JU/mJSnEU6aZPWetTVru3oKgTPzsInv G78w==
X-Gm-Message-State: APt69E38Olub7qCmxLFTrGxZEBGTNsUoV/m3bQn2VsseZHm4cjA4X1M4 FnN0XX2nskenNKkNIJgptmb7vA==
X-Google-Smtp-Source: ADUXVKJ0yrWhbF3oCHwx7d04Wy69ECOizABS9Zy/uNqJEiZituubttLhAPNNRMkwr7UT24JPuWA7jw==
X-Received: by 2002:ac8:2a39:: with SMTP id k54-v6mr5427530qtk.360.1528559737392; Sat, 09 Jun 2018 08:55:37 -0700 (PDT)
Received: from ubuntu-dmitri (ool-45715890.dyn.optonline.net. [69.113.88.144]) by smtp.gmail.com with ESMTPSA id a24-v6sm21574738qth.70.2018.06.09.08.55.36 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 09 Jun 2018 08:55:36 -0700 (PDT)
Date: Sat, 9 Jun 2018 11:55:31 -0400
From: Dmitri Tikhonov <dtikhonov@litespeedtech.com>
To: Alan Frindell <afrind@fb.com>
Cc: Kazuho Oku <kazuhooku@gmail.com>, Martin Thomson <martin.thomson@gmail.com>, QUIC WG <quic@ietf.org>
Subject: Re: Proposal: drop QPACK encoder stream framing
Message-ID: <20180609155530.GA6795@ubuntu-dmitri>
Mail-Followup-To: Alan Frindell <afrind@fb.com>, Kazuho Oku <kazuhooku@gmail.com>, Martin Thomson <martin.thomson@gmail.com>, QUIC WG <quic@ietf.org>
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>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <F04D1BA6-8EC6-43EB-ABEC-34C4B30352AB@fb.com>
User-Agent: Mutt/1.5.24 (2015-08-30)
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/edcz1BzU_ynsTrs-RJ2shDNorlk>
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: Sat, 09 Jun 2018 15:55:40 -0000

On Fri, Jun 08, 2018 at 08:49:37PM +0000, Alan Frindell wrote:
> Consider the most complicated instruction, which is Inserting a pure
> literal (all fields have variable length)
> 
> | Name Length | Name | Value Length | Value |
> 
> 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.

The example above contradicts the argument that follows.  It is evident
that we have a length followed by an instruction block (the Huffman-encoded
string).  A QPACK implementation is still free to buffer the instruction
blocks, in which case all the perceived advantages of framing you present
below are applicable.

Parsing of the length is, of course, more complicated than requiring a
known number of bytes to be available to read in a fixed-length integer.
Nevertheless, as Kazuho points out, there are practical limits whereby
most implementations will abide.

> 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.

An efficient implementation will not just blindly reparse over and over
as each byte of the stream data becomes available.  With a buffering
implementation, the need to reparse disappears if one is willing to
allocate the buffer large enough.  This is exactly the approach you
advocate to use with the current instruction block framing.

The proposal to drop framing is to allow an optimization (eliminate a
copy) at the encoder, not the decoder.  The decoder is still free to
use the same programming techniques as before.

> 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

And I hope I have demonstrated that the complexity increase is
minimal.  Soon, I will demonstrate the same using C code.

  - Dmitri.