Re: Deadlocking in the transport

Roberto Peon <fenix@fb.com> Fri, 12 January 2018 18:01 UTC

Return-Path: <prvs=45509646aa=fenix@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 98E6F12D871 for <quic@ietfa.amsl.com>; Fri, 12 Jan 2018 10:01:46 -0800 (PST)
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, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=fb.com header.b=QOOOdHIO; dkim=pass (1024-bit key) header.d=fb.onmicrosoft.com header.b=aQzHsiDC
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 EFX_hdxs7nxo for <quic@ietfa.amsl.com>; Fri, 12 Jan 2018 10:01:44 -0800 (PST)
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 A947912D87A for <quic@ietf.org>; Fri, 12 Jan 2018 10:01:42 -0800 (PST)
Received: from pps.filterd (m0044010.ppops.net [127.0.0.1]) by mx0a-00082601.pphosted.com (8.16.0.22/8.16.0.22) with SMTP id w0CI0VQO016304; Fri, 12 Jan 2018 10:01:39 -0800
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=Gcm1g9ZdxiSiUwOmpW9PjgyxG+eEhL8dWRL1dDhyRdc=; b=QOOOdHIO3it4E5fSON1u1F2P6swyDWqFTmPEpNd4aoPWtODY1SYu5SkToVlEe3GsiimA KqnsT3gxP/yS3pVuk8VK1Ur7pxsohV9rD91q0GP/DlK9EUHhx24ylNUkgpinSSi/tCma iwH9OenlSnXT0aVk0WC7FOn0Bcv8cWkZYNU=
Received: from maileast.thefacebook.com ([199.201.65.23]) by mx0a-00082601.pphosted.com with ESMTP id 2fereat3bv-1 (version=TLSv1 cipher=ECDHE-RSA-AES256-SHA bits=256 verify=NOT); Fri, 12 Jan 2018 10:01:38 -0800
Received: from NAM03-CO1-obe.outbound.protection.outlook.com (192.168.183.28) by o365-in.thefacebook.com (192.168.177.23) with Microsoft SMTP Server (TLS) id 14.3.361.1; Fri, 12 Jan 2018 13:01:36 -0500
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; bh=Gcm1g9ZdxiSiUwOmpW9PjgyxG+eEhL8dWRL1dDhyRdc=; b=aQzHsiDCYcNy2hltcqt4dt0ppeneiZpTowr1A/Ubec8a+UuyGYhw1G8pecqBDjS5QhuaLu8URABf6JwNDKxoOC/KqTNR8C9/Ief2AYDChLf/NOtc3IRU+ozPzG80lsqVSlaAKP/U1TgeS3igH0TZvkm8R0BFT+Jh/+TOydQCqDA=
Received: from SN6PR1501MB2191.namprd15.prod.outlook.com (52.132.120.28) by SN6PR1501MB2191.namprd15.prod.outlook.com (52.132.120.28) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.20.366.8; Fri, 12 Jan 2018 18:01:16 +0000
Received: from SN6PR1501MB2191.namprd15.prod.outlook.com ([fe80::a873:4c9f:f589:4b2d]) by SN6PR1501MB2191.namprd15.prod.outlook.com ([fe80::a873:4c9f:f589:4b2d%13]) with mapi id 15.20.0366.011; Fri, 12 Jan 2018 18:01:16 +0000
From: Roberto Peon <fenix@fb.com>
To: =?utf-8?B?TWlyamEgS8O8aGxld2luZA==?= <mirja.kuehlewind@tik.ee.ethz.ch>, Martin Thomson <martin.thomson@gmail.com>
CC: Jana Iyengar <jri@google.com>, QUIC WG <quic@ietf.org>, "Charles 'Buck' Krasic" <ckrasic@google.com>
Subject: Re: Deadlocking in the transport
Thread-Topic: Deadlocking in the transport
Thread-Index: AQHTidq/6Mg61g6LuEipz9qoFIGKPqNsqpwAgAC3uoCAAB3vgIAAA6iAgAAEuYCAAAC5AIAAAhWAgAACuICAAAJVAIAAGr0AgAAIxgCAAADWgIACtUUA//+auwA=
Date: Fri, 12 Jan 2018 18:01:16 +0000
Message-ID: <51C80222-9513-4CF6-82FD-5692C1DAB058@fb.com>
References: <CABkgnnUSMYRvYNUwzuJk4TQ28qb-sEHmgXhxpjKOBON43_rWCg@mail.gmail.com> <CAGD1bZYV7iHg_YarUMqUSnpbAB2q8dwEWO=dHE2wbw8Oea_zfA@mail.gmail.com> <CAD-iZUY-Y-MO_T74JmP6B9XVj=91eVovfcWnE=9s9kd0Ji+CnA@mail.gmail.com> <CAGD1bZa7ugOTT11qOKfCm4NFdi+t-pdrXnscWHgg0bO5tgUqmg@mail.gmail.com> <20180110194716.GA30573@ubuntu-dmitri> <CAGD1bZYiDOakLYNppMBr=99JreX3Xr2zkS7O2DRNfvr_o0NUbg@mail.gmail.com> <20180110200646.GB30573@ubuntu-dmitri> <CAGD1bZa-ZOw5J6oSWBYdk3uYHOpGvak+vwGp0XsZB44zbLvRrw@mail.gmail.com> <20180110202357.GC30573@ubuntu-dmitri> <CAGD1bZbPM3wnatLLN5938wGPo3e1qmxnGzobSTym6XX3W8FNJQ@mail.gmail.com> <CABkgnnU3CQkvd7m+G80sCOPJfzb_=HonbRDSQJC8wqD_uWoj0w@mail.gmail.com> <CAGD1bZbrtMEJE-OOXqG02yWmHy_2baEvaZu=rFCBTtcq94JrOg@mail.gmail.com> <CABkgnnWtmprf291pBgTOrfi6yU9tXSfKi5J5uQpm7Z4JHuiGWg@mail.gmail.com> <EDF23BB9-DA04-44A5-8682-3D22C1DD7380@tik.ee.ethz.ch>
In-Reply-To: <EDF23BB9-DA04-44A5-8682-3D22C1DD7380@tik.ee.ethz.ch>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-originating-ip: [2620:10d:c090:200::5:6ba8]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; SN6PR1501MB2191; 7:sMGokbWdRB6BdI809BI2/zpPoIljZWMvnViCVCY/Ggx7NJUsY0P2Mf6me2PTSw6j550aEu4LEkvq0rLytU47DY3Tlhkm7MgCHPACUuMwX1tuCQpoXe3MBEEcftAP3zGbof9KULqFhxM1fjNCioiVHR3TbUwncPr/qtGIiuFOXqygCrfNU3rtg9bNJlrKSRg9ml1T6CyM2pVckGMCPy9007NSqLZGZ3xk1jzfD/1FNekCDkERLuP0ee5gop6d3Shw; 20:PStqKGzY+aS4Zxzsh88anKdKXWB8sZCzD0mUH98NRIxOVYejVIiG7vT0Gr9NwHwLJ6XztT8qNcPohqyecPYn6GVBmulWrXZRFKJT1RiCM5cY4aijjjYz2m0xnWd6k1rQSDij5X0Rph+vhANeRZPkXqcFVKtlnTCNOLXdnYlaFZE=
x-ms-exchange-antispam-srfa-diagnostics: SSOS;
x-ms-office365-filtering-correlation-id: 7a5164bf-bbcd-436e-5301-08d559e679c4
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(7020085)(4652020)(5600026)(4604075)(3008032)(2017052603307)(7153060)(7193020); SRVR:SN6PR1501MB2191;
x-ms-traffictypediagnostic: SN6PR1501MB2191:
x-microsoft-antispam-prvs: <SN6PR1501MB2191BA182790695B4C4D8952CD170@SN6PR1501MB2191.namprd15.prod.outlook.com>
x-exchange-antispam-report-test: UriScan:(158342451672863)(85827821059158)(211936372134217)(153496737603132);
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(6040470)(2401047)(8121501046)(5005006)(3002001)(3231023)(11241501184)(944501146)(93006095)(93001095)(10201501046)(6041268)(20161123564045)(20161123560045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123558120)(20161123562045)(6072148)(201708071742011); SRVR:SN6PR1501MB2191; BCL:0; PCL:0; RULEID:(100000803101)(100110400095); SRVR:SN6PR1501MB2191;
x-forefront-prvs: 0550778858
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(346002)(39380400002)(39860400002)(366004)(376002)(396003)(189003)(199004)(24454002)(51444003)(97736004)(25786009)(4326008)(81166006)(3480700004)(68736007)(39060400002)(8676002)(5250100002)(81156014)(6246003)(8936002)(3660700001)(82746002)(106356001)(105586002)(316002)(6486002)(229853002)(93886005)(2900100001)(6116002)(6506007)(33656002)(102836004)(54906003)(53936002)(6512007)(86362001)(14454004)(53546011)(76176011)(83716003)(3280700002)(36756003)(99286004)(305945005)(2950100002)(110136005)(6346003)(7736002)(6436002)(2906002)(478600001)(5660300001)(42262002); DIR:OUT; SFP:1102; SCL:1; SRVR:SN6PR1501MB2191; H:SN6PR1501MB2191.namprd15.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:3; LANG:en;
received-spf: None (protection.outlook.com: fb.com does not designate permitted sender hosts)
x-microsoft-antispam-message-info: LQlko2PGzLQIl4xuZlChIjUVkvSivt6Wbb7r+2fClSMrGtntNxpkRzJdbmU62rScXZpr3VvOMVRureNewKVULw==
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-ID: <BBA2C03DC722074689D6565A88028C9A@namprd15.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: 7a5164bf-bbcd-436e-5301-08d559e679c4
X-MS-Exchange-CrossTenant-originalarrivaltime: 12 Jan 2018 18:01:16.1959 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR1501MB2191
X-OriginatorOrg: fb.com
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2018-01-12_09:, , signatures=0
X-Proofpoint-Spam-Reason: safe
X-FB-Internal: Safe
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/DXCKp9NZX11mPYaOM6DNMdFO5MA>
X-BeenThere: quic@ietf.org
X-Mailman-Version: 2.1.22
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, 12 Jan 2018 18:01:46 -0000

The transport *CANNOT* provide ordering guarantees w.r.t. prioritization because flows are end-to-end, whereas connections are point to point.
Flow-control, being a property of flows, ends up being asserted end-to-end though the mechanism at each hop is point-to-point.

Consider the ‘standard’ client->proxy->server topology.
If the server asserts flow control, the proxy must respect it. 
As the client<->proxy hop is asynchronous from the proxy<->server hop in most circumstances with a loadbalancing (i.e. shared flow) proxy, the proxy cannot guarantee flow-control window will be available for sending to the server even when flow control window is available from the client<->proxy.

Preemption/cancellation/retry, the addition of more resources, or finer management of resources can be used to resolve the (transitive) deadlock.


The sub-case of compression may be solvable without solving the general case as compression is point-to-point.
-=R


On 1/12/18, 8:04 AM, "QUIC on behalf of Mirja Kühlewind" <quic-bounces@ietf.org on behalf of mirja.kuehlewind@tik.ee.ethz.ch>; wrote:

    I disagree. I think it can be good to provide the transport hints about dependencies in application data which then could be used by the transport to optimize the sent-out scheduling, but I don’t think the transport should provide guarantees for ordered processing between streams. For me the whole point of having streams in the transport is to resolve dependencies between independent data.
    
    Therefore, I think it would probably be good to mention this deadlock problem in the main draft but I don’t think we should add strict priorities as a transport feature to QUIC. There are several ways how an application can avoid (don’t have dependencies by using the same stream for dependent data or wait until data has be sent before sending dependent data) or resolve (read all streams and implement an additional application layer buffer) such a deadlock and these should be explained in the applicability document respectively.
    
    My 2c,
    Mirja
    
    
    > Am 10.01.2018 um 23:42 schrieb Martin Thomson <martin.thomson@gmail.com>;:
    > 
    > On Thu, Jan 11, 2018 at 9:39 AM, Jana Iyengar <jri@google.com>; wrote:
    >> Yes, I think there's easy misinterpretation here -- something I realized
    >> today as I've had conversations about this. What I meant was specifically at
    >> the API between the app and the transport, at the sender. This is basically
    >> saying that to avoid deadlock due to dependencies across streams, the
    >> transport write API must allow the app to express strict priorities.
    > 
    > Ahh, excellent, then I think at least we two are in agreement.  It
    > seems like there is an emerging acceptance of the problem and proposed
    > approach, I guess we might start considering how to address it.
    > 
    > I think that this needs to be in the main spec.  Failing to document
    > this sort of pitfall could be fatal.  Does anyone disagree?
    >