Re: Proposal: drop QPACK encoder stream framing
Alan Frindell <afrind@fb.com> Fri, 08 June 2018 23:27 UTC
Return-Path: <prvs=96974df54d=afrind@fb.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 90235130DC1 for <quic@ietfa.amsl.com>; Fri, 8 Jun 2018 16:27:13 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.721
X-Spam-Level:
X-Spam-Status: No, score=-2.721 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, T_DKIMWL_WL_HIGH=-0.01, T_DKIMWL_WL_MED=-0.01] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=fb.com header.b=js/qQni5; dkim=pass (1024-bit key) header.d=fb.onmicrosoft.com header.b=CV5lh+Pk
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 W0OR6yy6xkpV for <quic@ietfa.amsl.com>; Fri, 8 Jun 2018 16:27:12 -0700 (PDT)
Received: from mx0a-00082601.pphosted.com (mx0a-00082601.pphosted.com [67.231.145.42]) (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 246B0126F72 for <quic@ietf.org>; Fri, 8 Jun 2018 16:27:12 -0700 (PDT)
Received: from pps.filterd (m0109334.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.22/8.16.0.22) with SMTP id w58NNFoO010921; Fri, 8 Jun 2018 16:27:09 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : content-id : content-transfer-encoding : mime-version; s=facebook; bh=9srrctTrs2kKHWeOzE9Z+i9BxaezpXUpK/vtdi8YYaw=; b=js/qQni5xufmZ82Maa6pzqJPaRIjSrFONL6dEmWnC4YFsGtP7xTgqcyLOQVAKOsPCZIc aY2srzl9dcQbHi55qtj6pzangTeCAFqTeb/EjgJRoUNIhE+EbM6uz8+43FHbF8wzzLSC NlM+C71IpUMawHon+9PiQ97Bgb5S0izYp1U=
Received: from mail.thefacebook.com ([199.201.64.23]) by mx0a-00082601.pphosted.com with ESMTP id 2jg007rjbc-1 (version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT); Fri, 08 Jun 2018 16:27:09 -0700
Received: from NAM01-BY2-obe.outbound.protection.outlook.com (192.168.54.28) by o365-in.thefacebook.com (192.168.16.13) with Microsoft SMTP Server (TLS) id 14.3.361.1; Fri, 8 Jun 2018 16:26:56 -0700
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=fb.onmicrosoft.com; s=selector1-fb-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=9srrctTrs2kKHWeOzE9Z+i9BxaezpXUpK/vtdi8YYaw=; b=CV5lh+PkQvLo2nCMnBko1rXKdfpkhT4YcJat3a2wxnR/sRVd9i+1R2TeyA6t1IcZXZJiEUy06CO7d70Z72UOQhNMFvhiay8qZd8T8kI3dCfCe78YyhCqmUtpSweoGNqIiAqo/6DfsQWT3hkA3NXTdz0YRtg26wZHjPsZb4OS/38=
Received: from MWHPR15MB1181.namprd15.prod.outlook.com (10.175.2.135) by MWHPR15MB1552.namprd15.prod.outlook.com (10.173.235.137) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.841.17; Fri, 8 Jun 2018 23:26:55 +0000
Received: from MWHPR15MB1181.namprd15.prod.outlook.com ([fe80::399c:db50:dfc0:3860]) by MWHPR15MB1181.namprd15.prod.outlook.com ([fe80::399c:db50:dfc0:3860%4]) with mapi id 15.20.0841.015; Fri, 8 Jun 2018 23:26:55 +0000
From: Alan Frindell <afrind@fb.com>
To: Kazuho Oku <kazuhooku@gmail.com>
CC: Martin Thomson <martin.thomson@gmail.com>, QUIC WG <quic@ietf.org>
Subject: Re: Proposal: drop QPACK encoder stream framing
Thread-Topic: Proposal: drop QPACK encoder stream framing
Thread-Index: AQHT/nHqXJJQhdl+r0afCsPvVPdYN6RWJZAAgAAStYCAACnpgIAAhKkA//+nSwA=
Date: Fri, 08 Jun 2018 23:26:55 +0000
Message-ID: <8616263A-31EF-4803-BEEF-1FE3FAEB23DB@fb.com>
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>
In-Reply-To: <CANatvzwr6fSER-tq+xLz_e9rOw+mj5RpdS5eb679Ds_3m=PnoA@mail.gmail.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/10.c.0.180410
x-originating-ip: [2620:10d:c090:200::7:1e0]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; MWHPR15MB1552; 7:BxfNXryQURaV1bDaP/g3uy86Lgyq+CttHXowv7T6SDMWOZ6I7bJ7sv2DiT5QJGWlaxHQCAgN+2FivqyxtZ+5kU42ZKI8hQl8JEAvhNqhlWeqTrHIKG7OaC8uHL9ayhhX/y5fL6a8ysafZHGFzZJChtM4Q9ZpvJ4NArtlbF6lECRRPQFNFgrYYOIm5vEuAF5CEioMYbC24761MbAU8eDEB51V6e8jY8oGdkm7oCJmrbhmCQWb6uotEJdvlm+ece33; 20:d7QxjwsyWeg/uXgkOxjKjQr5lutMfyS6p97csdiSV3o/cX2ZkBKKMf07fN26qm7q/I0DAJ4stKgC2TrgG9wrhGEOmEVZniTELd3opX1cfBZ3+Cb2XqYh8PHvUHLGy5ze52LwNbAG9tGhIop1Af3yFcH09p7bV8Unt/sK4dQDLEs=
x-ms-exchange-antispam-srfa-diagnostics: SOS;
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020095)(4652020)(5600026)(4534165)(4627221)(201703031133081)(201702281549075)(2017052603328)(7153060)(7193020); SRVR:MWHPR15MB1552;
x-ms-traffictypediagnostic: MWHPR15MB1552:
x-microsoft-antispam-prvs: <MWHPR15MB155297BEC72E67E8DE1897EDA77B0@MWHPR15MB1552.namprd15.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:;
x-ms-exchange-senderadcheck: 1
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(93006095)(93001095)(10201501046)(3002001)(3231254)(11241501184)(944501410)(52105095)(149027)(150027)(6041310)(20161123560045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123564045)(20161123558120)(20161123562045)(6072148)(201708071742011)(7699016); SRVR:MWHPR15MB1552; BCL:0; PCL:0; RULEID:; SRVR:MWHPR15MB1552;
x-forefront-prvs: 06973FFAD3
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(346002)(39380400002)(39860400002)(396003)(366004)(376002)(189003)(199004)(46003)(4326008)(6916009)(1411001)(83716003)(446003)(6436002)(54906003)(33656002)(11346002)(6486002)(8936002)(53936002)(93886005)(86362001)(99286004)(478600001)(6246003)(14454004)(76176011)(6512007)(8676002)(39060400002)(2616005)(2900100001)(186003)(5660300001)(59450400001)(486006)(3660700001)(305945005)(82746002)(6116002)(3280700002)(229853002)(2906002)(7736002)(476003)(81166006)(81156014)(25786009)(5250100002)(68736007)(105586002)(102836004)(36756003)(6506007)(316002)(97736004)(58126008)(106356001); DIR:OUT; SFP:1102; SCL:1; SRVR:MWHPR15MB1552; H:MWHPR15MB1181.namprd15.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; MX:1; A:1;
received-spf: None (protection.outlook.com: fb.com does not designate permitted sender hosts)
x-microsoft-antispam-message-info: mxz1ajwGYDCo2s7/AbRrODXxMvb3Y8QDQc5rS/kxjDddR+A0V1BTi9+9tpbapo6K/TUevK0nxfItuFKo8nAxaumK8XVN1wFKcUczyJJBpSFGlrsySKItpTiRwSE+Omb9oDcBvKNASGlDsvts5VpRECPe7JrKkDt6are9/F8UZy1imeyrTLevhLqmQNdu3Q9n
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-ID: <59D4E207024B39459D6C434F770CDD4C@namprd15.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Office365-Filtering-Correlation-Id: 205ae0b1-a95d-41c5-8fb9-08d5cd9752c6
X-MS-Exchange-CrossTenant-Network-Message-Id: 205ae0b1-a95d-41c5-8fb9-08d5cd9752c6
X-MS-Exchange-CrossTenant-originalarrivaltime: 08 Jun 2018 23:26:55.3622 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MWHPR15MB1552
X-OriginatorOrg: fb.com
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:, , definitions=2018-06-08_10:, , signatures=0
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/2yb08ypj_T6cVe6jDHJX35UPf_A>
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 23:27:14 -0000
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. -Alan
- Re: Proposal: drop QPACK encoder stream framing Ian Swett
- Re: Proposal: drop QPACK encoder stream framing Roberto Peon
- Re: Proposal: drop QPACK encoder stream framing Roberto Peon
- Proposal: drop QPACK encoder stream framing Dmitri Tikhonov
- Re: Proposal: drop QPACK encoder stream framing Spencer Dawkins at IETF
- Re: Proposal: drop QPACK encoder stream framing Spencer Dawkins at IETF
- Re: Proposal: drop QPACK encoder stream framing Dmitri Tikhonov
- Re: Proposal: drop QPACK encoder stream framing Kazuho Oku
- Re: Proposal: drop QPACK encoder stream framing Martin Thomson
- Re: Proposal: drop QPACK encoder stream framing Ian Swett
- Re: Proposal: drop QPACK encoder stream framing Alan Frindell
- Re: Proposal: drop QPACK encoder stream framing Kazuho Oku
- Re: Proposal: drop QPACK encoder stream framing Alan Frindell
- Re: Proposal: drop QPACK encoder stream framing Kazuho Oku
- Re: Proposal: drop QPACK encoder stream framing Dmitri Tikhonov
- RE: Proposal: drop QPACK encoder stream framing Mike Bishop
- Re: Proposal: drop QPACK encoder stream framing Alan Frindell
- Re: Proposal: drop QPACK encoder stream framing Dmitri Tikhonov
- Re: Proposal: drop QPACK encoder stream framing Dmitri Tikhonov