RE: Deadlocking in the transport

"Lubashev, Igor" <ilubashe@akamai.com> Thu, 11 January 2018 04:54 UTC

Return-Path: <ilubashe@akamai.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 2CC3712E891 for <quic@ietfa.amsl.com>; Wed, 10 Jan 2018 20:54:27 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, 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=akamai.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 gaTcFMv7lrJN for <quic@ietfa.amsl.com>; Wed, 10 Jan 2018 20:54:24 -0800 (PST)
Received: from mx0a-00190b01.pphosted.com (mx0a-00190b01.pphosted.com [IPv6:2620:100:9001:583::1]) (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 2C17712E88D for <quic@ietf.org>; Wed, 10 Jan 2018 20:54:24 -0800 (PST)
Received: from pps.filterd (m0122333.ppops.net [127.0.0.1]) by mx0a-00190b01.pphosted.com (8.16.0.22/8.16.0.22) with SMTP id w0B4q30U008192; Thu, 11 Jan 2018 04:54:18 GMT
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=akamai.com; h=from : to : cc : subject : date : message-id : references : in-reply-to : content-type : mime-version; s=jan2016.eng; bh=fQakvMF9HUyJlTMGcN/dMvwS2SprmcrpmLIszOgG4YE=; b=mORppK/r9A17YbKAEfD0owD2WWAXc7uZ3iDsmDQCcJ/YYcECPy0/xw0op+v0voXuXFwv cQEz4dZ1PghGvTI6bZOdMrUMYVXb0bu/lGR/Wfq0vVQwwaZl26zelgMHbMbxu+mHbrEc iX90uavzrBlsKtMpEMh9Vciex/8TdcztGUfBOL6cuqw8w9MsarRKzEyOOtbYseM/QI59 NEz7sCShKFeSeY8fMH7LJhW+ZB9lmm8kVThpaMCik2/v+KY0Y/880VGDJ7eFyFEsYqZ1 KM5beiomwmHCDfK1e3tqH9AVN3vcRN68YlSF1FMOvDsGYnu7NHPbaZQwp3JexnYrdFn6 lA==
Received: from prod-mail-ppoint2 (prod-mail-ppoint2.akamai.com [184.51.33.19]) by mx0a-00190b01.pphosted.com with ESMTP id 2fda90n4w1-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Thu, 11 Jan 2018 04:54:17 +0000
Received: from pps.filterd (prod-mail-ppoint2.akamai.com [127.0.0.1]) by prod-mail-ppoint2.akamai.com (8.16.0.21/8.16.0.21) with SMTP id w0B4ogZ4030837; Wed, 10 Jan 2018 23:54:16 -0500
Received: from email.msg.corp.akamai.com ([172.27.123.33]) by prod-mail-ppoint2.akamai.com with ESMTP id 2fatpe5897-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-SHA384 bits=256 verify=NOT); Wed, 10 Jan 2018 23:54:16 -0500
Received: from USMA1EX-DAG1MB5.msg.corp.akamai.com (172.27.123.105) by usma1ex-dag3mb3.msg.corp.akamai.com (172.27.123.58) with Microsoft SMTP Server (TLS) id 15.0.1263.5; Wed, 10 Jan 2018 23:54:15 -0500
Received: from USMA1EX-DAG1MB5.msg.corp.akamai.com (172.27.123.105) by usma1ex-dag1mb5.msg.corp.akamai.com (172.27.123.105) with Microsoft SMTP Server (TLS) id 15.0.1263.5; Wed, 10 Jan 2018 23:54:15 -0500
Received: from USMA1EX-DAG1MB5.msg.corp.akamai.com ([172.27.123.105]) by usma1ex-dag1mb5.msg.corp.akamai.com ([172.27.123.105]) with mapi id 15.00.1263.000; Wed, 10 Jan 2018 23:54:15 -0500
From: "Lubashev, Igor" <ilubashe@akamai.com>
To: "martin.thomson@gmail.com" <martin.thomson@gmail.com>, "jri@google.com" <jri@google.com>, "mbishop@evequefou.be" <mbishop@evequefou.be>
CC: "quic@ietf.org" <quic@ietf.org>, "ckrasic@google.com" <ckrasic@google.com>
Subject: RE: Deadlocking in the transport
Thread-Topic: Deadlocking in the transport
Thread-Index: AQHTidqwSZojuevrjEKuWaFfJc7FkKNs/m4AgAC3uoCAAB3ugIAAA6mAgAAEuYCAAAC5AIAAAhWAgAACuICAAAJVAIAAGr0AgAAIxgCAAADVgIAAA74AgAAQVsA=
Date: Thu, 11 Jan 2018 04:54:14 +0000
Message-ID: <d8fc96a972bb43c5b6e13fc60c8bc9ad@usma1ex-dag1mb5.msg.corp.akamai.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>, <CY4PR08MB24231DA846126B51A83DC420DA110@CY4PR08MB2423.namprd08.prod.outlook.com>
In-Reply-To: <CY4PR08MB24231DA846126B51A83DC420DA110@CY4PR08MB2423.namprd08.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-transport-fromentityheader: Hosted
Content-Type: multipart/alternative; boundary="_000_d8fc96a972bb43c5b6e13fc60c8bc9adusma1exdag1mb5msgcorpak_"
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2018-01-11_02:, , signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 suspectscore=0 malwarescore=0 phishscore=0 bulkscore=0 spamscore=0 mlxscore=0 mlxlogscore=550 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1711220000 definitions=main-1801110063
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2018-01-11_02:, , signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 priorityscore=1501 malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0 clxscore=1011 lowpriorityscore=0 mlxscore=0 impostorscore=0 mlxlogscore=501 adultscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.0.1-1711220000 definitions=main-1801110063
Archived-At: <https://mailarchive.ietf.org/arch/msg/quic/uvcTALp3D8cPabNat8FEiWRHp-Q>
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: Thu, 11 Jan 2018 04:54:27 -0000

Mandating a strict priority order on the sender may cause an increase in HOL blocking, if the contents of a higher-priority stream are not needed by all lower-priority streams. That happens when a higher-priority stream has MAX_STREAM_DATA that allows the sender to keep transmitting on that stream exclusively for 1-2 rtt, but one of the early packets is lost. The entire connection is blocked till that one loss is repaired.

The value of MAX_STREAM_DATA cannot be reduced below 1-2 rtt-worth of data, in case the higher-priority stream is the only stream with data.

A transport wishing to minimize HOL blocking may decide to allocate bandwidth in an other than strict priority order. Or the transport API would need to be very versatile to convey strict stream dependency graphs as well as stream priorities.

-----Original Message-----
From: Mike Bishop [mbishop@evequefou.be]
Received: Wednesday, 10 Jan 2018, 5:55PM
To: Martin Thomson [martin.thomson@gmail.com]; Jana Iyengar [jri@google.com]
CC: QUIC WG [quic@ietf.org]; Charles 'Buck' Krasic [ckrasic@google.com]
Subject: RE: Deadlocking in the transport

No disagreement.  When choosing which stream *with pending data* to make progress on, I think choosing the higher-priority stream is necessary rather than advisory.  With H2, we're talking about client preferences about server responses which might not be ready yet, so it's always advisory to the server.  Here, we're talking about the application's preferences about its own data that it has already handed off.  That's something that happened within the HTTP/2 implementation, so there was no agreement or contract needed.

So long as the dependency is strictly on a higher-priority stream and the transport layer is handling priorities strictly when choosing what to send in a flow-control-limited situation, I think we avoid the deadlock.  That is, when X depends on Y, if new flow control credit is guaranteed to cause Y to make forward progress (and the other side is continuing to read from Y's stream), the other side would eventually be able to process X.

This isn't a protocol element, but an implementation element that's necessary for the protocol to be fully functional.

-----Original Message-----
From: QUIC [mailto:quic-bounces@ietf.org] On Behalf Of Martin Thomson
Sent: Wednesday, January 10, 2018 2:42 PM
To: Jana Iyengar <jri@google.com>;
Cc: QUIC WG <quic@ietf.org>;; Charles 'Buck' Krasic <ckrasic@google.com>;
Subject: Re: Deadlocking in the transport

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?