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