[quicwg/base-drafts] Boolean blocked streams setting (#3073)

Bence Béky <notifications@github.com> Wed, 02 October 2019 13:56 UTC

Return-Path: <noreply@github.com>
X-Original-To: quic-issues@ietfa.amsl.com
Delivered-To: quic-issues@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 8952F12088D for <quic-issues@ietfa.amsl.com>; Wed, 2 Oct 2019 06:56:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.001
X-Spam-Status: No, score=-8.001 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, MAILING_LIST_MULTI=-1, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H2=-0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=github.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id dubzXnkoX0y8 for <quic-issues@ietfa.amsl.com>; Wed, 2 Oct 2019 06:56:23 -0700 (PDT)
Received: from out-1.smtp.github.com (out-1.smtp.github.com []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 89A3212013B for <quic-issues@ietf.org>; Wed, 2 Oct 2019 06:56:23 -0700 (PDT)
Date: Wed, 02 Oct 2019 06:56:22 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=github.com; s=pf2014; t=1570024582; bh=xDvdOFYL2V/DhzDOq7TIal7LIE+tjd12NKvkSgBdFmY=; h=Date:From:Reply-To:To:Cc:Subject:List-ID:List-Archive:List-Post: List-Unsubscribe:From; b=jAFZTQxJqNQRBhfETOcdspBAZ8Mk1ShGt908WAQdYyVc5PM2Mps6WTVggKyo+1ygZ Pwhk0SvBqa8GRxbX8WW8K5xZZaNB0z2W96Y60Yq0HF6GWLkrCHSHARG8ZEFaRy0wgu 5SHOfsuKyGcMLP292TUBy15LpR4RUD+vEW3PFbU8=
From: Bence Béky <notifications@github.com>
Reply-To: quicwg/base-drafts <reply+AFTOJK6Q5CQU2SPUUFUZOOV3UHWRNEVBNHHB3ZDAFY@reply.github.com>
To: quicwg/base-drafts <base-drafts@noreply.github.com>
Cc: Subscribed <subscribed@noreply.github.com>
Message-ID: <quicwg/base-drafts/issues/3073@github.com>
Subject: [quicwg/base-drafts] Boolean blocked streams setting (#3073)
Mime-Version: 1.0
Content-Type: multipart/alternative; boundary="--==_mimepart_5d94ac8672970_792a3fc2a64cd968214561"; charset="UTF-8"
Content-Transfer-Encoding: 7bit
Precedence: list
X-GitHub-Sender: bencebeky
X-GitHub-Recipient: quic-issues
X-GitHub-Reason: subscribed
X-Auto-Response-Suppress: All
X-GitHub-Recipient-Address: quic-issues@ietf.org
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic-issues/c-Dg_OTT6FwWVcxo0Vza8BMMS1w>
X-BeenThere: quic-issues@ietf.org
X-Mailman-Version: 2.1.29
List-Id: Notification list for GitHub issues related to the QUIC WG <quic-issues.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/quic-issues>, <mailto:quic-issues-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/quic-issues/>
List-Post: <mailto:quic-issues@ietf.org>
List-Help: <mailto:quic-issues-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/quic-issues>, <mailto:quic-issues-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 02 Oct 2019 13:56:34 -0000

# Proposal

Replace the numerical limit SETTINGS_QPACK_BLOCKED_STREAMS on number of blocked
streams by a Boolean setting: if 0, the encoder MUST not send a header block
with Required Insert Count exceeding Known Insert Count and the decoder MUST
treat the receipt of such a header block as connection error.  If 1, the number
of blocked streams is not directly limited.

Given the necessary implementation complexity especially on the encoder side, I
do not believe that a numerical limit is worth its purported advantages.

# Pros

Determining the number of blocked streams has considerable computational
complexity on the encoding side.  While it is true that the encoder already has
to keep track of all unacknowledged header blocks, it takes extra work to count
the blocked ones.

One approach is to keep a count of blocked streams that needs to be updated
every time a header acknowledgement, an insert count increment, or a stream
cancellation instruction is received.  Examples include [nghttp3](https://github.com/ngtcp2/nghttp3/blob/master/lib/nghttp3_qpack.h#L239) and

Another approach is to count blocked streams every time a new header list is
encoded to determine if it is allowed to use unacknowledged references, by
iterating through all unacknowledged header blocks at least until the limit is
reached.  An example is [QUICHE](https://quiche.googlesource.com/quiche/+/master/quic/core/qpack/qpack_blocking_manager.cc#74) (the Google one, not the Cloudflare one).

Both approaches are considerably complex and thus error-prone to implement.

The situation is further complicated by two factors.  The first is that there
can be multiple unacknowledged header blocks on each stream (in case of 1xx
status code or trailing headers).  The second is that if there is already a
potentially blocking unacknowledged header block on a given stream, then
referencing unacknowledged entries is always allowed in subsequent header blocks
on the same stream regardless of the limit.

This is one of the most complex requirements necessary to implement a blocking
QPACK encoder, raising concerns of potential implementation bugs that could
result in incorrect behavior, or vulnerability to CPU attacks due to buggy or
suboptimal algorithms.  Replacing the numerical limit with a Boolean would allow
the encoder implementation to be much simplified.

# Cons

The desire for a limit on blocked streams is articulated at
https://github.com/quicwg/base-drafts/issues/1140#issuecomment-371677474, and is
further motivated by flow control considerations.

The number of streams with blocked header blocks a is already limited by the
number of bidirectional streams the peer can open, set by the decoder using the
initial_max_streams_bidi transport parameter and the MAX_STREAMS frame.  Since
the total memory footprint of the objects representing a stream (including
transport functionalities like buffering, ordering, flow control, and
retransmissions) are not expected to be dominated by the footprint of the QPACK
decoder and buffered header block (not considering the buffered data itself in
either case), there is little additional value in selectively limiting the
number of streams blocked on header block decoding given that the number of open
streams is already limited.

As for the issue of a blocked header block taking up a large amount of the flow
control window, SETTINGS_QPACK_BLOCKED_STREAMS only addresses this concern if
the stream level flow control window multiplied by the blocked stream limit is
less than the connection level flow control window.  However, a typical decoder
is expected to set the blocked stream limit to either zero or at least a dozen,
and connection level flow control is typically only a few times larger than the
stream level flow control for performance reasons.

You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub: