Re: [TLS] Efficiency of ACKing scheme
Martin Thomson <mt@lowentropy.net> Mon, 06 April 2020 01:49 UTC
Return-Path: <mt@lowentropy.net>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6CC533A0B35 for <tls@ietfa.amsl.com>; Sun, 5 Apr 2020 18:49:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level:
X-Spam-Status: No, score=-2.1 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, 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=lowentropy.net header.b=lmo/XV7l; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=fHNjUm5L
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 XXSbwXREHgYy for <tls@ietfa.amsl.com>; Sun, 5 Apr 2020 18:49:22 -0700 (PDT)
Received: from out5-smtp.messagingengine.com (out5-smtp.messagingengine.com [66.111.4.29]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 9AB9E3A0B33 for <tls@ietf.org>; Sun, 5 Apr 2020 18:49:22 -0700 (PDT)
Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailout.nyi.internal (Postfix) with ESMTP id B7B775C00B1 for <tls@ietf.org>; Sun, 5 Apr 2020 21:49:21 -0400 (EDT)
Received: from imap2 ([10.202.2.52]) by compute2.internal (MEProxy); Sun, 05 Apr 2020 21:49:21 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=lowentropy.net; h=mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type; s=fm1; bh=DORJq9ETdcsxaJYmKD7DQOrRcxYeFYc eOZUsP3TGPlg=; b=lmo/XV7lb8Wur+iNFWRVZZhfHeVFK/ocnb2n613BhiQlP2D q3ZR0IIW0zezpnBvsKnPoMZxT567ZEeUptD+e3ycz2hQtOtdz7x7sx1bxDE4c6SA Ac9wiEiIannT6x1hKiED42haWfwt9IYyzEY26hzJPouESN7tMGiMbC1lBbNhqLtk bNknw65SG4tOGDW7WVbLZ/Hrr+DP/ltSLlpzWn3SrasaYh3Y5V/NfuN+8uC+3dGK ir90/8WsQ2jJe+JnPMyeRw9FPcJfhewZVCIwiY/78DwyDsGK/++R2SQmPyG5EhoT F7DIe6RcJSiITOCfK5d+OcTtJiNHPHGSrbq/Aqg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-proxy :x-me-proxy:x-me-sender:x-me-sender:x-sasl-enc; s=fm2; bh=DORJq9 ETdcsxaJYmKD7DQOrRcxYeFYceOZUsP3TGPlg=; b=fHNjUm5LJ2mMpXsgXlBqeb +eiD8E3Oxa7JQqoW0RVT9GfMRK024Mku4kl1HBv5hTytcPOb8O11Eq87fK4MT91/ wsOIZXjqpqKtjmB/Wf3IdfJV8aGgOAL7m063GoY72X5Y+7Vvrr3WKvp8t9dP/c2X K749IkxZd1lwFsVWL4WDnRLqoVolP+DMEziUDeL+IvX31PBVSGgMsFHr+X1x/SCa gfIEpyc3xKCL7OabIcJZZFiRjkMNmek+PHudJm0Uvaxpn/NuVrouq0VWHFNsL4xZ JXRP+lyr+Tuju2CKig/+ukLt879C29h561IRHY3Ujx8v8kJ60nEafRp1CJONQ3lQ ==
X-ME-Sender: <xms:oYqKXofOw3sH-cWtbGkadAIkaKa4p1LkcboTK8rDmaVbFbZBMr763Q>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgeduhedruddvgdehvdcutefuodetggdotefrodftvf curfhrohhfihhlvgemucfhrghsthforghilhdpqfgfvfdpuffrtefokffrpgfnqfghnecu uegrihhlohhuthemuceftddtnecunecujfgurhepofgfggfkjghffffhvffutgesthdtre dtreertdenucfhrhhomhepfdforghrthhinhcuvfhhohhmshhonhdfuceomhhtsehlohif vghnthhrohhphidrnhgvtheqnecuffhomhgrihhnpehivghtfhdrohhrghenucevlhhush htvghrufhiiigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehmtheslhhofigvnhht rhhophihrdhnvght
X-ME-Proxy: <xmx:oYqKXu4g74LDVivzTocyH-ZAKJiT6rD9aW1ccZ8qSHpVJLUWbQndlw> <xmx:oYqKXha8P5LwB0JGEbOfq3aJPBSz3OurnX-K9IQev8q2NYfeG-Emqg> <xmx:oYqKXhsGGjMdd0dwPsQ6w4U-X9b9zB2H5mE4U79F5JFduGbnBlUoqw> <xmx:oYqKXnpd-Yhl6b8i35Z002HTL_eMsguNhAvN8yVhW9UdW6V0oaGqpg>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id 358C4E00B1; Sun, 5 Apr 2020 21:49:21 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.1.7-1082-g13d7805-fmstable-20200403v1
Mime-Version: 1.0
Message-Id: <8fed27dc-f5eb-4104-8308-186c361781bc@www.fastmail.com>
In-Reply-To: <AM6PR08MB331832C84A0E5D04AA5612A99BC70@AM6PR08MB3318.eurprd08.prod.outlook.com>
References: <AM6PR08MB331820C710440F07055382739BC70@AM6PR08MB3318.eurprd08.prod.outlook.com> <AM6PR08MB331832C84A0E5D04AA5612A99BC70@AM6PR08MB3318.eurprd08.prod.outlook.com>
Date: Mon, 06 Apr 2020 11:49:03 +1000
From: Martin Thomson <mt@lowentropy.net>
To: tls@ietf.org
Content-Type: text/plain
Archived-At: <https://mailarchive.ietf.org/arch/msg/tls/iKK1ZHcyqG5I3BQ2FHZlztZ3CZc>
Subject: Re: [TLS] Efficiency of ACKing scheme
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tls/>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 06 Apr 2020 01:49:27 -0000
Hi Hanno, I think that you are assuming a lot about how the loss recovery part of the sender is operating here. If you receive ACK { 1, 3 }, then it might be reasonable to assume that 2 got lost, but it seems to me that assuming anything about 4 is premature. As you say, delaying ACKs is a good way to ensure that you capture all incoming data, but it also affects overall latency. The trade-offs are complex. The sender can also make some adjustments, without necessarily adhering to a strict interpretation of the recommendations in the spec. The draft is imprecise about this logic intentionally. It recommends that the sender send missing data, which will likely work, and be fast. For large flights, yes, this will be suboptimal, but we are also assuming that this data is not subject to congestion control limits. If we go to PQ schemes with large amounts of data, then that requires a different set of assumptions. It might also require that implementations take extra steps to avoid the resulting inefficiencies. On Sat, Apr 4, 2020, at 04:00, Hanno Becker wrote: > An additional note: All solutions which retain the paragraph > > Upon receipt > of an ACK for only some messages from a flight, an implementation > SHOULD retransmit the remaining messages or fragments. > and hence trigger retransmission immediately upon receiving a partial ACK, > suffer from the following problem: > > On Low-MTU networks, and looking ahead at the use of Post-Quantum Cryptography, > it might happen that a single ACK is too small to hold the entire list of record > sequence numbers of the flight being ACKed. > > Doing the math in an example: If the maximum plaintext size is, say, 512 Bytes, > then a single ACK can not ACK more than 64 Records, each of which contains at > most 512 Bytes of handshake data. Hence, we've got a theoretical max of ~32Kb > flight length we can ACK in a single ACK message. > > While this seems a lot, some PQC schemes go beyond that. For example, > the SPHINCS > signature scheme has 41Kb signature size. > > To avoid this problem, it appears beneficial to go for option 2., that > is, don't > retransmit immediately upon receiving an ACK, but accumulate some ACKs > first. This > allows to split ACKing a very large flight into multiple ACKs. > *From:* TLS <tls-bounces@ietf.org> on behalf of Hanno Becker > <Hanno.Becker@arm.com> > *Sent:* Friday, April 3, 2020 5:35 PM > *To:* tls@ietf.org <tls@ietf.org> > *Subject:* [TLS] Efficiency of ACKing scheme > Hi again, > > The DTLS 1.3 ACKing scheme seems to be quite inefficient as it is written, > and I wonder if the current spec matches the authors' intentions. > > Example: > > Consider a flight broken down as sequence of records 1, 2, .., N. > Assume record 2 gets dropped, while all other records go through > without reordering, corruption or loss; hence, the record sequence > observed on the receiver is 1, 3, 4, ..., N. > > Then, according to the spec, the following SHOULD happen: > > On the receiver-side, we have the following from Section 7.1: > > ``` > When an implementation receives a partial flight, it SHOULD generate > an ACK that covers the messages from that flight which it has > received so far. Implementations have some discretion about when to > generate ACKs, but it is RECOMMENDED that they do so under two > circumstances: > * When they receive a message or fragment which is out of order, > either because it is not the next expected message or because it > is not the next piece of the current message. > ``` > > So, when the receiver receives records 1 and 3, it notices that 2 is missing > and immediately sends an ACK for { 1, 3 }. > > On the sender-side, we have the following from Section 7.2: > > ``` > 7.2. Receiving ACKs > When an implementation receives an ACK, it SHOULD record that the > messages or message fragments sent in the records being ACKed were > received and omit them from any future retransmissions. Upon receipt > of an ACK for only some messages from a flight, an implementation > SHOULD retransmit the remaining messages or fragments. > ``` > > So, when the receiver receives the ACK for { 1, 3 }, it resends records > 2, 4, 5, .., N. > > That's obviously not optimal, and probably not what was intended, but what > unambiguously appears to be the recommended behavior according to the spec. > > How should this be resolved? > > I see two similar and comparably unintrusive options: > > 1) Send ACKs only after period of inactivity > > Instead of sending ACKs straight away when something hints at > something going wrong (such as an out-of-order receipt), as > currently stated in Section 7.1, only send ACKs after a period > of time where no further messages has been received. > > That is, replace the current version > > ``` > When an implementation receives a partial flight, it SHOULD generate > an ACK that covers the messages from that flight which it has > received so far. Implementations have some discretion about when to > generate ACKs, but it is RECOMMENDED that they do so under two > circumstances: > * When they receive a message or fragment which is out of order, > either because it is not the next expected message or because it > is not the next piece of the current message. Implementations > MUST NOT send ACKs for handshake messages which they discard as > out-of-order, because otherwise those messages will not be > retransmitted. > * When they have received part of a flight and do not immediately > receive the rest of the flight (which may be in the same UDP > datagram). A reasonable approach here is to set a timer for 1/4 > the current retransmit timer value when the first record in the > flight is received and then send an ACK when that timer expires. > In addition, implementations MUST send ACKs upon receiving all of any > flight which they do not respond to with their own messages. > ``` > > by something along the following lines: > > ``` > As long as implementation has received some but not all of the next incoming > flight, it SHOULD send an ACK message after an implementation-defined period > a time during which no further messages are received. A reasonable approach > here is to reset a timer to 1/4 the current retransmission timer with every > record received in the current flight, and send an ACK when that timer expires. > ``` > > In the above example, this would mean that as long as records > 3,4,...,N arrive > in close succession, it will only once send an ACK for {1,3,4,...,N} > in the end, > triggering retransmission of record 2 only, which is optimal. > > The drawback of this is that the receiver of a flight does not inform > a peer > about a gap in a flight as soon as it notices it. For this to work, > the content > of an ACK would need to be what's missing instead of what's present, > which > appears to be a too intrusive change to be considered at this stage.. > The > benefit of this approach is that it leads to very good retransmission > bandwidth. > > 2. Essentially same as option 1., but 'mirrored': Allow the receiver of > a flight > to send ACKs recurringly (though preferably still bunched, i.e. using > some timer > for the bunching), and replace the part of Section 7.2: > > ``` > 7.2. Receiving ACKs > When an implementation receives an ACK, it SHOULD record that the > messages or message fragments sent in the records being ACKed were > received and omit them from any future retransmissions. Upon receipt > of an ACK for only some messages from a flight, an implementation > SHOULD retransmit the remaining messages or fragments. > ``` > > by something along the lines of > > ``` > 7.2. Receiving ACKs > If an implementation receives an ACK for parts of a flight, but doesn't > immediately receive ACKs for the rest of the flight, it SHOULD retransmit > the messages that have not been ACKed. A reasonable approach here is to > reset a timer to 1/4 the current retransmission timer with every ACK record > received, and retransmit the last outgoing flight when that timer expires. > ``` > > Let me know what you think and which option (if not a completely different one) > you'd prefer. > > Cheers, > Hanno > IMPORTANT NOTICE: The contents of this email and any attachments are > confidential and may also be privileged. If you are not the intended > recipient, please notify the sender immediately and do not disclose the > contents to any other person, use it for any purpose, or store or copy > the information in any medium. Thank you. > IMPORTANT NOTICE: The contents of this email and any attachments are > confidential and may also be privileged. If you are not the intended > recipient, please notify the sender immediately and do not disclose the > contents to any other person, use it for any purpose, or store or copy > the information in any medium. Thank you. > _______________________________________________ > TLS mailing list > TLS@ietf.org > https://www.ietf.org/mailman/listinfo/tls >
- [TLS] Efficiency of ACKing scheme Hanno Becker
- Re: [TLS] Efficiency of ACKing scheme Hanno Becker
- Re: [TLS] Efficiency of ACKing scheme Martin Thomson
- Re: [TLS] Efficiency of ACKing scheme Thomas Fossati
- Re: [TLS] Efficiency of ACKing scheme Rob Sayre
- Re: [TLS] Efficiency of ACKing scheme Hanno Becker
- Re: [TLS] Efficiency of ACKing scheme Thomas Fossati
- Re: [TLS] Efficiency of ACKing scheme Thomas Fossati
- Re: [TLS] Efficiency of ACKing scheme Hanno Becker
- Re: [TLS] Efficiency of ACKing scheme Eric Rescorla
- Re: [TLS] Efficiency of ACKing scheme Thomas Fossati
- Re: [TLS] Efficiency of ACKing scheme Thomas Fossati
- Re: [TLS] Efficiency of ACKing scheme Hanno Becker
- Re: [TLS] Efficiency of ACKing scheme Thomas Fossati
- Re: [TLS] Efficiency of ACKing scheme Eric Rescorla
- Re: [TLS] Efficiency of ACKing scheme Thomas Fossati
- Re: [TLS] Efficiency of ACKing scheme Eric Rescorla
- Re: [TLS] Efficiency of ACKing scheme Thomas Fossati
- Re: [TLS] Efficiency of ACKing scheme Eric Rescorla
- Re: [TLS] Efficiency of ACKing scheme Hannes Tschofenig
- Re: [TLS] Efficiency of ACKing scheme Thomas Fossati
- Re: [TLS] Efficiency of ACKing scheme Hanno Becker