Re: Is a faithful HTTP/2 response scheduler necessarily O(n) in the worst case?

Cory Benfield <cory@lukasa.co.uk> Wed, 25 January 2017 08:36 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 88E5E129878 for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Wed, 25 Jan 2017 00:36:21 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -9.619
X-Spam-Level:
X-Spam-Status: No, score=-9.619 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HEADER_FROM_DIFFERENT_DOMAINS=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RCVD_IN_SORBS_SPAM=0.5, RP_MATCHES_RCVD=-3.199, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=lukasa-co-uk.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 JfYd4fsnwknW for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Wed, 25 Jan 2017 00:36:20 -0800 (PST)
Received: from frink.w3.org (frink.w3.org [128.30.52.56]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 10F54129864 for <httpbisa-archive-bis2Juki@lists.ietf.org>; Wed, 25 Jan 2017 00:36:19 -0800 (PST)
Received: from lists by frink.w3.org with local (Exim 4.80) (envelope-from <ietf-http-wg-request@listhub.w3.org>) id 1cWJ0u-0006XO-Ez for ietf-http-wg-dist@listhub.w3.org; Wed, 25 Jan 2017 08:33:08 +0000
Resent-Date: Wed, 25 Jan 2017 08:33:08 +0000
Resent-Message-Id: <E1cWJ0u-0006XO-Ez@frink.w3.org>
Received: from titan.w3.org ([128.30.52.76]) by frink.w3.org with esmtps (TLS1.2:RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <cory@lukasa.co.uk>) id 1cWJ0p-0006Vh-7w for ietf-http-wg@listhub.w3.org; Wed, 25 Jan 2017 08:33:03 +0000
Received: from mail-wm0-f54.google.com ([74.125.82.54]) by titan.w3.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.84_2) (envelope-from <cory@lukasa.co.uk>) id 1cWJ0i-0000iw-QK for ietf-http-wg@w3.org; Wed, 25 Jan 2017 08:32:58 +0000
Received: by mail-wm0-f54.google.com with SMTP id c206so17411618wme.0 for <ietf-http-wg@w3.org>; Wed, 25 Jan 2017 00:32:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=lukasa-co-uk.20150623.gappssmtp.com; s=20150623; h=from:message-id:mime-version:subject:date:in-reply-to:cc:to :references; bh=LmHvS42ZI2NHite+weAn1u7ENMhFcSYp/d87Lf+FNj0=; b=trYXs0cXEGV/I9KfLtM4PKku/TGKfaH2r5DvcFXJbHWYQdyxKVJpD2pG2o/YOGnYLv IG9knlyM+BtqAyhXrUyzmls0XUQkrdDXF0grkrq7lPwawpL20n2c9Y8n/b5Zh/0XGIcV 0fkOGSWzFgl6n5Ed5Z5+BFgPPgfr9qM5XYTHie9bi+cftBXy4z9OoaioTN0ijvxmyeNQ 68Gtev2vxUQFuvDTYrt3OQN01MQg9PcnaOxpBjjdlsQiIzoKvLBSzUEg8mAIf3v/iLSb Hzx/lpTmsbCP1XeADLS3rQu70UimqLgJKlCx75M18rEqnP0CIRWYnvDeG3nJGiEwmZom MwCw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:from:message-id:mime-version:subject:date :in-reply-to:cc:to:references; bh=LmHvS42ZI2NHite+weAn1u7ENMhFcSYp/d87Lf+FNj0=; b=VbYSFqJpoejvlUh2z+kx6J1A/Xtnkb6cMgkFUCGi2ug7pUW9zQJRGM2GGVWH7LT0AF rL47jjadRV0MQcoXpUh2e7hIamhE7yvatUiblfANhYGKiJeV6rNVFxQP2kGc/2gjqDtd nVFW1oLKR69jA/NB8vgGUU2VCK6c+ekY6ruNgaIT1i4paSQearmQDsOAY+4ipeDDPdVU A8FiMlxI058uQX9XmXxO+upvLxQ8kkrAvmXbUoaMW3Cc1S/uul8+agG62IIKSSeCvV6R yqrSMJk994Iu6lkFoooqjiAC3NAoNYenGWdzYMA5IQ7GIvWXPzE63QUPGttasGNLRKW4 1Ddg==
X-Gm-Message-State: AIkVDXKu6wQowA5gL7EhcQ/jUqRYsMZq5t/0yjii80yTgXN3GYnMs9GnDDsdfNsAma8P1w==
X-Received: by 10.223.168.111 with SMTP id l102mr31487498wrc.150.1485333149759; Wed, 25 Jan 2017 00:32:29 -0800 (PST)
Received: from [192.168.1.3] (227.71.125.91.dyn.plus.net. [91.125.71.227]) by smtp.gmail.com with ESMTPSA id k43sm23745006wrc.46.2017.01.25.00.32.28 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 25 Jan 2017 00:32:28 -0800 (PST)
From: Cory Benfield <cory@lukasa.co.uk>
Message-Id: <C2828755-7067-49B0-8FFE-A417B265FDC7@lukasa.co.uk>
Content-Type: multipart/alternative; boundary="Apple-Mail=_96E21404-801D-4109-8E51-DD77A4D9A09E"
Mime-Version: 1.0 (Mac OS X Mail 10.2 \(3259\))
Date: Wed, 25 Jan 2017 08:32:27 +0000
In-Reply-To: <CAPyZ6=LYEufwdqnXZGrP9o3dfuNVXkyL=Mj04s=PhQG9v0oLGg@mail.gmail.com>
Cc: Tom Bergan <tombergan@chromium.org>, Stefan Eissing <stefan.eissing@greenbytes.de>, =?utf-8?B?IkthenUgWWFtYW1vdG8gKOWxseacrOWSjOW9piki?= <kazu@iij.ad.jp>, HTTP Working Group <ietf-http-wg@w3.org>
To: Tatsuhiro Tsujikawa <tatsuhiro.t@gmail.com>
References: <CA+3+x5Ft8MfRduWp1RzJ9_qAgQiCujac8f5FLz81Xpyu3cTDxw@mail.gmail.com> <CANatvzz0AYxBDDyEbpvnq1xPd1-vrFazbnVt2usanXS0CTKbeA@mail.gmail.com> <20170124.165356.870174430965764062.kazu@iij.ad.jp> <900A5D6B-0752-470E-840C-4518D933DD09@greenbytes.de> <CA+3+x5EdkLSAR2gWR9TT72o2Tg4Z_xKXMh8yVREYD7mvNuLB8w@mail.gmail.com> <CAPyZ6=LYEufwdqnXZGrP9o3dfuNVXkyL=Mj04s=PhQG9v0oLGg@mail.gmail.com>
X-Mailer: Apple Mail (2.3259)
Received-SPF: pass client-ip=74.125.82.54; envelope-from=cory@lukasa.co.uk; helo=mail-wm0-f54.google.com
X-W3C-Hub-Spam-Status: No, score=-3.6
X-W3C-Hub-Spam-Report: AWL=-0.157, BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RCVD_IN_SORBS_SPAM=0.5, SPF_PASS=-0.001, W3C_AA=-1, W3C_WL=-1
X-W3C-Scan-Sig: titan.w3.org 1cWJ0i-0000iw-QK 7eac1c6dd86ab9cc48a5089355c39322
X-Original-To: ietf-http-wg@w3.org
Subject: Re: Is a faithful HTTP/2 response scheduler necessarily O(n) in the worst case?
Archived-At: <http://www.w3.org/mid/C2828755-7067-49B0-8FFE-A417B265FDC7@lukasa.co.uk>
Resent-From: ietf-http-wg@w3.org
X-Mailing-List: <ietf-http-wg@w3.org> archive/latest/33376
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: <http://www.w3.org/Mail/>
List-Post: <mailto:ietf-http-wg@w3.org>
List-Unsubscribe: <mailto:ietf-http-wg-request@w3.org?subject=unsubscribe>

> On 25 Jan 2017, at 02:01, Tatsuhiro Tsujikawa <tatsuhiro.t@gmail.com> wrote:
> 
> ​If large n is concern, server can limit SETTINGS_MAX_CONCURRENT_STREAMS to the reasonable number.  Usually we use 100, and it is pretty fast.=

The various Python HTTP/2 implementations also set SETTINGS_MAX_CONCURRENT_STREAMS to 100.

Cory