Re: Proposal: drop QPACK encoder stream framing

Ian Swett <ianswett@google.com> Wed, 13 June 2018 01:29 UTC

Return-Path: <ianswett@google.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 5207B1310A8 for <quic@ietfa.amsl.com>; Tue, 12 Jun 2018 18:29:50 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -17.51
X-Spam-Level:
X-Spam-Status: No, score=-17.51 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, ENV_AND_HDR_SPF_MATCH=-0.5, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, T_DKIMWL_WL_MED=-0.01, USER_IN_DEF_DKIM_WL=-7.5, USER_IN_DEF_SPF_WL=-7.5] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=google.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 5nRAen3t9uNH for <quic@ietfa.amsl.com>; Tue, 12 Jun 2018 18:29:45 -0700 (PDT)
Received: from mail-yb0-x229.google.com (mail-yb0-x229.google.com [IPv6:2607:f8b0:4002:c09::229]) (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 6F4ED130E95 for <quic@ietf.org>; Tue, 12 Jun 2018 18:29:45 -0700 (PDT)
Received: by mail-yb0-x229.google.com with SMTP id w74-v6so328479ybe.11 for <quic@ietf.org>; Tue, 12 Jun 2018 18:29:45 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=HU4Ne6tcgPS8lsHJ1A5ajh22YnNvvgdfkkdzWEePzqQ=; b=W5pvY/MrHnhyeSSGU56gLcUk4alM8hX33HK7R4og0aA7BdefpBSe9C8fb0jywMoZXI uE4rk/g8xL3g8YqZlrm9kzqIdtPymbxqBdDQNNgMVVy2l1O5nhjcCSb8d5gum0+/kBLd XQ+6TwTJp1u8XFl/vYNUFBZSfITphLV40eL2sTpke0xdgCtmoj8e0K1BFUEzAH4LruXg 84WhgZwkhITdG1nlqQxedgw8G2whey7PpnoEX87hyeS8lwSHrrZCzs4x49YwsOY/3spO l5LxASt95QVgr9d2pcDyy7jsmlaG/K+x3St3KTmmw1EcIAD/4RIoCMw9e6lnFulxTD4g XJbQ==
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:cc; bh=HU4Ne6tcgPS8lsHJ1A5ajh22YnNvvgdfkkdzWEePzqQ=; b=B38vcH/cqAJ6wRtWMtGpFwoCD/cu7kD+pqTDN2Q9YkeyoE5SZ1gdvGpO0oZCVHc/dZ D+nbxwMH7ipVBLb/vvfptGm2a9jfJjtMKDV1w/91n4+5azQxRo6WtQQxyn/JJsLth2WG NWsQGSWzQ23gmCPTVqMpBNLCvaWE1oJvhzTnVWfLnw8dv0C7z5b5tpNRsYE5iBXm97/Z RM6390cMHwcq/SnItbPIi7iKEzZxjrPSHU41+pFZdduPTupupXvi00sGoaGxTSe6SJMB hAPP527k2lRJll4POA1Z9K/hKmEkIkznk8+KPePVdPTqdCxBWTPxgkgiZct+SIgeOIVD nLVA==
X-Gm-Message-State: APt69E2Wc+Ia0oHifmWBv5J58fBeQTwgnuUcHriAu27ob0L9Wlmphnww k301oGGleaHxBE+EA+tUYIpBisQ7Wv/lzjWyRKDuLg==
X-Google-Smtp-Source: ADUXVKLQfYD1L76KZwcUdQ1SednvXZ713CBi0kE+OJpjpgFbH85MrVPThT1rWGauOEAa5cVFLWMKg5x3C6bn4SFWUCs=
X-Received: by 2002:a25:57d7:: with SMTP id l206-v6mr1403378ybb.206.1528853384309; Tue, 12 Jun 2018 18:29:44 -0700 (PDT)
MIME-Version: 1.0
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> <CANatvzwr6fSER-tq+xLz_e9rOw+mj5RpdS5eb679Ds_3m=PnoA@mail.gmail.com> <8616263A-31EF-4803-BEEF-1FE3FAEB23DB@fb.com> <CANatvzyHXnDCKPfpgf7-gZzDODRJ85Xz-diZ3ioBB-O=F2fvpg@mail.gmail.com> <535018A7-3DC1-448B-9A94-43B30211F10F@fb.com>
In-Reply-To: <535018A7-3DC1-448B-9A94-43B30211F10F@fb.com>
From: Ian Swett <ianswett@google.com>
Date: Tue, 12 Jun 2018 21:29:32 -0400
Message-ID: <CAKcm_gOxF7tA_cghQ12fzKcdV=_EJJwmSYQP96YeQ2k89YzzmQ@mail.gmail.com>
Subject: Re: Proposal: drop QPACK encoder stream framing
To: Roberto Peon <fenix@fb.com>
Cc: Kazuho Oku <kazuhooku@gmail.com>, Alan Frindell <afrind@fb.com>, IETF QUIC WG <quic@ietf.org>, Martin Thomson <martin.thomson@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000e37209056e7bea47"
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/n3ISmLosW2RYvAkxm-aA5XDQymw>
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: Wed, 13 Jun 2018 01:29:58 -0000

As a person who spent a fair amount of time both trying to make Google's
FEC scheme work and subsequently analyzing why it didn't, a core issue was
that losses were much more correlated than expected.  The only FEC scheme
tested had zero value if more than two packets were lost within an FEC
block.

Additionally, it was not wired up to the general purpose recovery code, so
it failed to prevent spurious retransmits.

That being said, if you have a few RTTs to play with, QUIC's fast
retransmission works very well.  If you're running a realtime application
like WebRTC, the bandwidth overhead of FEC is well-justified.

On Tue, Jun 12, 2018 at 7:36 PM Roberto Peon <fenix@fb.com> wrote:

> Were I to put lengths somewhere, it'd be on another stream, which
> consisted solely of fixed/constant-sized metadata about the headers.
> -=R
>
> ´╗┐On 6/9/18, 3:57 PM, "QUIC on behalf of Kazuho Oku" <quic-bounces@ietf.org
> on behalf of kazuhooku@gmail.com> wrote:
>
>     2018-06-09 8:26 GMT+09:00 Alan Frindell <afrind@fb.com>om>:
>     >     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).
>     >
>     > The O(N^2) work I was thinking of was something like this:
>     >
>     > The encoder sends a very long Huffman encoded header name followed
> by a long value, but they send the value one byte at a time.  If the
> decoder naively reparses the entire Insert instruction every time a byte
> arrives, it will end up Huffman decoding the header name on every new byte
> of the value.  The name can be skipped over to re-parse the value length,
> and verify if the full value is present.  However, even skipping over it
> may be a linear operation in a zero-copy implementation that maintains a
> linked list of data buffers.
>
>     Thank you for the clarification. That sounds like an interesting
>     attack vector that we need to be aware of.
>
>     OTOH, I am not sure if we need to consider the possibility of
>     streaming Huffman decoding in this discussion, considering the fact
>     that the compressed strings remain length-prefixed.
>
>     Even if we remove the framing of the QCACK instructions,
>     implementations will continue to have the freedom to buffer a complete
>     Huffman-encoded string (the length of the string being identified by
>     the length octets.
>
>     > -Alan
>     >
>     >
>
>
>
>     --
>     Kazuho Oku
>
>
>
>