Re: Priority implementation complexity (was: Re: Extensible Priorities and Reprioritization)

Patrick Meenan <patmeenan@gmail.com> Tue, 09 June 2020 15:23 UTC

Return-Path: <ietf-http-wg-request+bounce-httpbisa-archive-bis2juki=lists.ie@listhub.w3.org>
X-Original-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Delivered-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 076223A08FA for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Tue, 9 Jun 2020 08:23:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.748
X-Spam-Level:
X-Spam-Status: No, score=-2.748 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, MAILING_LIST_MULTI=-1, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=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 ENpzBhw-cdn9 for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Tue, 9 Jun 2020 08:23:31 -0700 (PDT)
Received: from lyra.w3.org (lyra.w3.org [128.30.52.18]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 58A7D3A090B for <httpbisa-archive-bis2Juki@lists.ietf.org>; Tue, 9 Jun 2020 08:23:31 -0700 (PDT)
Received: from lists by lyra.w3.org with local (Exim 4.92) (envelope-from <ietf-http-wg-request@listhub.w3.org>) id 1jig3I-0004cd-6X for ietf-http-wg-dist@listhub.w3.org; Tue, 09 Jun 2020 15:20:36 +0000
Resent-Date: Tue, 09 Jun 2020 15:20:36 +0000
Resent-Message-Id: <E1jig3I-0004cd-6X@lyra.w3.org>
Received: from titan.w3.org ([128.30.52.76]) by lyra.w3.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from <patmeenan@gmail.com>) id 1jig3H-0004bm-6D for ietf-http-wg@listhub.w3.org; Tue, 09 Jun 2020 15:20:35 +0000
Received: from mail-io1-xd36.google.com ([2607:f8b0:4864:20::d36]) by titan.w3.org with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from <patmeenan@gmail.com>) id 1jig3F-0001i8-F1 for ietf-http-wg@w3.org; Tue, 09 Jun 2020 15:20:35 +0000
Received: by mail-io1-xd36.google.com with SMTP id p20so23096274iop.11 for <ietf-http-wg@w3.org>; Tue, 09 Jun 2020 08:20:33 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=NUElX/fZ+DLZYxjnyrmPa5gFIMjP+Gls1CwzDgPSuPs=; b=BxcxgREdl/u5SI5PCGCbuaQtGhe4TY5mMsrHMSzNUo+baJ75q4DBWjXBBoIwY20CaQ tkYZgHcxOTYPKdhb1aeZjxr+0zC5ITwKtcxeYfUdAikDDiVp1k2vzjWiRhASpsYGgaVU GbwZrAWYiJvXHUta4oB8fWIp84JqJss521d4qAOTUo5e6MD5o8rT7JLf3OsBqBNSByaH l+bF9Hc/Z5SNO8yiMMu5HEkvDy+zkAVABA7vuzcetuIMwHQXTO3qTw+HfP43HDqhnRm6 JbtdUZ6VU4PdrhxKIQnvzrUVf3PnMtzui57AYhUblF87FudhvmfHwRw4s8TFOyP6dVu/ q8UA==
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; bh=NUElX/fZ+DLZYxjnyrmPa5gFIMjP+Gls1CwzDgPSuPs=; b=qmYumZv8H/6LOcixrI0S8lns9siKZNuxvJRKBkh72qjuMspigFFAN1e4mqHJqB075Z X0s51LGU0n3KHSF9rx/sQbGmTPhsFsu8XgzAoXRHZ1lb40TQ11GBIDQU1pR+XL7JbCj6 Gd6t4MlYD29Sj/rR08kZHP75OZIG0kkb7d/SiEEi+AV4Y84rx2uSAgy69AvWZgwkM0au o2nkg7SD4PsE47Y18InJ5ibY3xxi6UAJ+PkyZ1XGPbtr2WJj7sPJwGAxx1mHioRSGxcl 2d6uiWS4mwjn0RWVDeIJr99Jbn7rIjqOcwiL7EbPBt1YScBnOowbigRz9j1f2lhFcFDR Ki0g==
X-Gm-Message-State: AOAM531nCp6XZH+SNWQjBNM1JpdFL6G4j1mspbobZH31i6KZxetUfVhj 3yZLdZWTZ/R1Ho8dlBH633HU7xsa2TjhkfbhfV4=
X-Google-Smtp-Source: ABdhPJx2br8K+ZKOS8vvTelaIOez8WIP0dXNuOSpnjRoBR7JemolG//HAF9w7ig3jmeRUxAYXmh2ZcPKP3ja0og8yuY=
X-Received: by 2002:a05:6602:2e87:: with SMTP id m7mr27667798iow.203.1591716022171; Tue, 09 Jun 2020 08:20:22 -0700 (PDT)
MIME-Version: 1.0
References: <CALGR9obRjBSADN1KtKF6jvFVzNS1+JzaS0D0kCVKHKkd4sn+MQ@mail.gmail.com> <459C86F8-A989-4EF4-84DC-3568FF594F36@apple.com> <CANatvzwSpSHd7kZD-4tyMGkBJDdCBi6r_pLBvnaT8rrQy6SBHQ@mail.gmail.com> <CACMu3treK0m2mbpw9FebOjOcEed0bW-DbLbryHJH1DWAHoz+9g@mail.gmail.com> <CALGR9oZgE7ZfXdoYdUh9LUYC1fi8fMUyyTpvmV3GF7Z6Oxgg1g@mail.gmail.com> <20200609144428.GC22180@lubuntu>
In-Reply-To: <20200609144428.GC22180@lubuntu>
From: Patrick Meenan <patmeenan@gmail.com>
Date: Tue, 09 Jun 2020 11:20:10 -0400
Message-ID: <CAJV+MGyuhxx=P6kZKktuREeq5pipZjxmwWP4jE_Sxhj_+krU2Q@mail.gmail.com>
To: Lucas Pardue <lucaspardue.24.7@gmail.com>, HTTP Working Group <ietf-http-wg@w3.org>, Bence Béky <bnc@chromium.org>, Kazuho Oku <kazuhooku@gmail.com>
Content-Type: multipart/alternative; boundary="00000000000015c05605a7a844c2"
Received-SPF: pass client-ip=2607:f8b0:4864:20::d36; envelope-from=patmeenan@gmail.com; helo=mail-io1-xd36.google.com
X-W3C-Hub-Spam-Status: No, score=-4.1
X-W3C-Hub-Spam-Report: BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, W3C_AA=-1, W3C_WL=-1
X-W3C-Scan-Sig: titan.w3.org 1jig3F-0001i8-F1 71bfbdc8853c4fcf6e0c25174756dab1
X-Original-To: ietf-http-wg@w3.org
Subject: Re: Priority implementation complexity (was: Re: Extensible Priorities and Reprioritization)
Archived-At: <https://www.w3.org/mid/CAJV+MGyuhxx=P6kZKktuREeq5pipZjxmwWP4jE_Sxhj_+krU2Q@mail.gmail.com>
Resent-From: ietf-http-wg@w3.org
X-Mailing-List: <ietf-http-wg@w3.org> archive/latest/37738
X-Loop: ietf-http-wg@w3.org
Resent-Sender: ietf-http-wg-request@w3.org
Precedence: list
List-Id: <ietf-http-wg.w3.org>
List-Help: <https://www.w3.org/Mail/>
List-Post: <mailto:ietf-http-wg@w3.org>
List-Unsubscribe: <mailto:ietf-http-wg-request@w3.org?subject=unsubscribe>

Maybe I'm missing something but the priority updates don't need to
coordinate across multiple data streams, just between the one stream that
is being reprioritized and the control stream.

Would something like this not work?
- Control stream gets priority update for stream X
- If stream X is known and the request side is complete/closed then update
the priority as requested
- If stream X is either not known or still in the process of receiving
request details, store the priority update for stream X in a fixed
queue/map (size can be small but a safe size would be the max number of
streams supported)
- If there is already a pending priority update for stream X, discard it
and replace it with the current priority update
- If the pending priority update queue is full, drop the oldest and insert
the new update
- When a new request stream closes, check the pending priority update queue
to see if there is an update waiting for the stream. If so, remove it from
the queue and apply the new priority

There should be no DOS concerns since the queue is fixed and small. The
performance overhead would be trivial if we assume that out-of-order
reprioritizations are rare (i.e. the list will almost always be empty).

On Tue, Jun 9, 2020 at 10:48 AM Dmitri Tikhonov <dtikhonov@litespeedtech.com>
wrote:

> On Tue, Jun 09, 2020 at 03:15:44PM +0100, Lucas Pardue wrote:
> > I can hypothesize that an implementation with QPACK dynamic support has
> > already crossed the threshold of complexity that means implementing
> > reprioritization is not burdensome. I'd like to hear from other
> > implementers if they agree or disagree with this.
>
> I don't think we can judge either way.  If Alice implements QPACK and
> Bob implement reprioritization, results will vary based on their level
> of competence.  The degree of burden will also vary for each
> particular implementation.  Speaking for lsquic, reprioritization
> had to [1] touch more code and was much more tightly coupled than
> QPACK; on the other had, QPACK encoder logic was a lot more code.
>
> At a higher level, I don't understand the concern with complexity.
> If you look up "complexity" in the dictionary, you will see
>
>     complexity (n), see QUIC.
>
>   - Dmitri.
>
> 1. Before it was ripped out of the spec, that is, thanks a lot...
>
>