Re: [TLS] Efficiency of ACKing scheme

[Hanno Becker <[e-mail]>]

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 <[e-mail]> on behalf of Hanno Becker <[e-mail]>
Sent: Friday, April 3, 2020 5:35 PM
To: [e-mail] <[e-mail]>
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.