Re: Proposal: drop QPACK encoder stream framing

Kazuho Oku <kazuhooku@gmail.com> Fri, 08 June 2018 11:19 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 D6AB2130E79 for <quic@ietfa.amsl.com>; Fri, 8 Jun 2018 04:19:39 -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 x80XvfYX7uze for <quic@ietfa.amsl.com>; Fri, 8 Jun 2018 04:19:36 -0700 (PDT)
Received: from mail-pl0-x22a.google.com (mail-pl0-x22a.google.com [IPv6:2607:f8b0:400e:c01::22a]) (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 1B3D9130E78 for <quic@ietf.org>; Fri, 8 Jun 2018 04:19:36 -0700 (PDT)
Received: by mail-pl0-x22a.google.com with SMTP id z9-v6so8135893plk.11 for <quic@ietf.org>; Fri, 08 Jun 2018 04:19:36 -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; bh=owpED+4WVRFfCBNcn7D8TtzEehf1hLtrDEG86f3lXgk=; b=NxPBADMzZeOKzHTmqkZD88JwPq+WFaeBoPxWdTlTPt2bizAsXpETMAkR5bzprJdSSn 6IIsgENk5ijHgHUtACV2IdhLi4tFe/jpJQNpRhT0oVG0B3dBRAyGk44wj7qAuxlKNALZ O/yHv0JUehqAmL5Cv1zLWyc6kapyPH29WNtsrV7eeoRTj5Ue6fze5l7+XuwxjjxIrkqD QFWb0g78rvLRlE5oUcgMmM3xYdGASF/fO67vep564gC0Yd5j0X+m0H54EpiECUVuHZxx h47gRLEktmcHQk4sNepsU9M2Sj5mWcwOh08RGsuOEfMO51POd3xsjNpBYUf4CgHZMB0A MV5g==
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; bh=owpED+4WVRFfCBNcn7D8TtzEehf1hLtrDEG86f3lXgk=; b=PAzzmLc9ztPotlo9Hb6YuN77tmQDst3+soE1fdYFKpGzws7SWiVlDHcamSdjrXXI3g mxwXmMxrRQmfeg0u2hikC8DS9IUBcBOqHO4FQQZtTFV0L63MqmmlgWXhawu/I+/C0zdN VPhBrvJZs1i9L3gyPtf67Q7mNBm1OfIqg6Qae/zPTKyxz0yIz/2KsXF0ARzsBbpzBhVq Y2CdXyiTIMvz58p0QmrbnYc6ZG8TcTvddPYMnXiftE4STommyMD6B1+n0iMDHWccXDeA tUkD/P4z500Y6SaA5o8BOzbDmge09XMyrCQxu9RepxEi85g8wbenzjj3tfusfZ2NcVC6 i/NQ==
X-Gm-Message-State: APt69E1bEGWVR4Ev6NaYUZFNoR8ITJi3xFSt3IFdYzuN9Y6TpqJcGPQj 4TDHIU60Bz4JuAQ3jq3EMqqViJ3lXhMCo72VKRY=
X-Google-Smtp-Source: ADUXVKKgz2NH0yYZW0XNQAJXBA9GgzbYMgTWhvAUswUADbA38csc7+cQOyXQI6zyLVXjryDG8nXGnU8xcqaBg8t7V7I=
X-Received: by 2002:a17:902:d697:: with SMTP id v23-v6mr6157559ply.193.1528456775632; Fri, 08 Jun 2018 04:19:35 -0700 (PDT)
MIME-Version: 1.0
Received: by 2002:a17:90a:1181:0:0:0:0 with HTTP; Fri, 8 Jun 2018 04:19:35 -0700 (PDT)
In-Reply-To: <CABkgnnXbfkVbq6vCvud100h6wr3+9ir3iO7dD6-qaykOmK3JBQ@mail.gmail.com>
References: <20180607151112.GA28823@ubuntu-dmitri> <CABkgnnXbfkVbq6vCvud100h6wr3+9ir3iO7dD6-qaykOmK3JBQ@mail.gmail.com>
From: Kazuho Oku <kazuhooku@gmail.com>
Date: Fri, 8 Jun 2018 13:19:35 +0200
Message-ID: <CANatvzzzXF8WCXgDCahTa_7JWZ1c1i-9rU_c8c9QWk5_O5u4Ow@mail.gmail.com>
Subject: Re: Proposal: drop QPACK encoder stream framing
To: Martin Thomson <martin.thomson@gmail.com>
Cc: QUIC WG <quic@ietf.org>
Content-Type: text/plain; charset="UTF-8"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/y5UWYyOf1mbOn9w8JMSNNlKUQHQ>
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 11:19:40 -0000

2018-06-08 13:12 GMT+03:00 Martin Thomson <martin.thomson@gmail.com>om>:
> I think that this is a reasonable request and I'd support this.  It
> saves an encoder from having to buffer and it even saves a few octets.
> The complexity increase (the increased need to delay acknowledgments)
> is manageable and even encourages good practice - the current design
> encourages a little bit of laziness because you can acknowledge at the
> end of each block and have a reasonable expectation of it being
> approximately correct... most of the time.

+1

Previously I had thought that having prefix has the possibility of
simplifying the encoder. But I think I was wrong.

If we have framing, we need to do either of the following:

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

As you can see, removing the framing simplifies the decoder design.
Because it reduces one layer of variable-length encoding.

> On Thu, Jun 7, 2018 at 5:11 PM Dmitri Tikhonov
> <dtikhonov@litespeedtech.com> wrote:
>>
>> Abstract
>> --------
>>
>> The encoder block specified in Section 3.3 of draft-ietf-quic-qpack-00
>> is unnecessary.  For reasons of efficiency, I propose that the framing
>> be removed: let the encoder instructions be written and interpreted as
>> a stream instead.
>>
>> Background
>> ----------
>>
>> I brought this up during the first day (June 6) of the Kista Interim.
>> Alan explained that there are two reasons for framing the instructions
>> in this way on the encoder stream:
>>
>>     1. Historically, some (or most) HPACK decoders have struggled with
>>        input that breaks in the middle of an instruction, as they do
>>        not maintain state.
>>
>>     2. The blocks can be used as a clue to send Table State Synchronize
>>        instructions on the decoder stream (Section 3.4.1).
>>
>> The downside to having length-prefixed blocks is that it makes it
>> difficult to optimize encoding by writing to the outgoing packets
>> directly.  One has to buffer the block, write the block length first,
>> and then copy the block.
>>
>> Additionally, there is a potential for a deadlock (issue #1420).  Recall
>> that QPACK owes its current form to the fact that the WG decided to
>> prevent deadlocks at the compression protocol level, and not via advisory
>> notes to the implementers.
>>
>> Reasons Behind the Block
>> ------------------------
>>
>> First, let's look at the historical HPACK chokers.
>>
>> The HPACK decoder only processes HEADER blocks.  There is only one stream
>> and thus only one HEADER block can be processed at a time.
>>
>> The QPACK decoder has to process two inputs: a) the encoder stream
>> and b) HEADER blocks.  There is only one encoder stream.  This stream
>> modifies the decoder state: the dynamic table.  The HEADER blocks do not
>> modify the state.
>>
>> The HEADER blocks already come with a prefix length (HQ framing), and so
>> QPACK implementations can choose to wait until the whole HEADER block is
>> available.  It is processing of the encoder stream that is under
>> consideration.
>>
>> With regards to the Table Synch signaling, the draft states that
>>
>>  "                                                         A decoder MAY
>>  " coalesce multiple synchronization updates into a single update.
>>
>> This effectively means that the encoder already should not expect to get
>> a one-to-one mapping between its Encoder Blocks and Table Synchs.
>>
>> Working with the Encoder Stream
>> -------------------------------
>>
>> The dynamic table instruction stream can be thought of as its own state.
>> Already, the QPACK decoder must be able to pause reading from streams when
>> a blocked HEADERS block arrives.  Similar techniques can be used to resume
>> reading from the encoder stream.  It should not be difficult to resume
>> decoding a single instruction!  While breaking with the HPACK precedent
>> (the hold-my-hand-I-need-buffer-size chokers), it keeps in line with the
>> Seattle hum that the new compression mechanism is free from its HPACK
>> shackles.
>>
>> Conclusion
>> ----------
>>
>> Prefixing arbitrary sets of encoder instructions with a length denies
>> zero-copy optimization opportunities.  At the cost of some slight
>> complexity increase at the decoder, this framing mechanism can be
>> dropped.  The proposed change is limited to just this -- technically
>> superfluous -- piece.
>>
>>   - Dmitri.
>>
>> P.S.  An added bonus is some saved framing bytes on the encoder stream.
>>       I believe the "compression performance above everything else" is
>>       also the Working Group's consensus (Melbourne).
>>
>



-- 
Kazuho Oku