Subject: [quicwg/base-drafts] Recovery uses both time and packet thresholds (#1974)

From: ianswett <[email-masked]>
Date: Tue, 06 Nov 2018 03:12:12 -0800

Based on @pravb feedback at tcpm and my anecdotal experience, combining the two should work well.

Fixes #1969
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/1974

-- Commit Summary --

  * Recovery uses both time and packet thresholds

-- File Changes --

    M draft-ietf-quic-recovery.md (47)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/1974.patch
https://github.com/quicwg/base-drafts/pull/1974.diff

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974

---

From: ianswett <[email-masked]>
Date: Tue, 06 Nov 2018 03:14:41 -0800

@ianswett pushed 1 commit.

aea6a42  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/4367f31056942f8692f972748dd4e06285bcc7f5..aea6a4265e7386ac2c89aff9c7e0ee053b9de821

---

From: ianswett <[email-masked]>
Date: Tue, 06 Nov 2018 03:20:30 -0800

51ebc20  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/aea6a4265e7386ac2c89aff9c7e0ee053b9de821..51ebc206ae583608e09242483a93ce9f509ba9b1

---

From: Marten Seemann <[email-masked]>
Date: Tue, 06 Nov 2018 04:16:01 -0800

This would make #1226 obsolete, right?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#issuecomment-436232562

---

From: ianswett <[email-masked]>
Date: Tue, 06 Nov 2018 07:43:20 -0800

c23f901  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/51ebc206ae583608e09242483a93ce9f509ba9b1..c23f901273498cb372e1478ece502d0e7be86e0f

---

From: ianswett <[email-masked]>
Date: Tue, 06 Nov 2018 07:46:57 -0800

Yes @marten-seemann , the hope is to make #1226 obsolete, though I suspect this PR needs a bit more work as well.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#issuecomment-436300219

---

From: ianswett <[email-masked]>
Date: Tue, 06 Nov 2018 18:48:20 -0800

c98a79c  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/c23f901273498cb372e1478ece502d0e7be86e0f..c98a79c87d102d4544dadf2676161cd7db03fc62

---

From: ianswett <[email-masked]>
Date: Tue, 06 Nov 2018 18:59:57 -0800

cd05b45  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/c98a79c87d102d4544dadf2676161cd7db03fc62..cd05b4526cf345e7749d07121a8ef16cae4fdffe

---

From: ianswett <[email-masked]>
Date: Tue, 06 Nov 2018 19:03:03 -0800

1c2596e  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/cd05b4526cf345e7749d07121a8ef16cae4fdffe..1c2596eb43b86271f6fb12c8ee771e9c009f4900

---

From: MikkelFJ <[email-masked]>
Date: Tue, 06 Nov 2018 23:50:29 -0800

mikkelfj commented on this pull request.

>  as a fraction of the round-trip time (kTimeReorderingFraction), is 1/8.
 
-An endpoint SHOULD set the timer such that a packet is marked as lost no earlier
-than 1.125 * max(SRTT, latest_RTT) since when it was sent.
+An endpoint SHOULD declare packets lost no earlier than
+1.125 * max(SRTT, latest_RTT) after when they were sent.  If packets sent prior
+to the largest acknowledged packet cannot yet be declared lost, then a timer
+SHOULD be set for the remainint time.

remaining

> @@ -312,16 +292,10 @@ Using max(SRTT, latest_RTT) protects from the two following cases:
 * the latest RTT sample is higher than the SRTT, perhaps due to a sustained
   increase in the actual RTT, but the smoothed SRTT has not yet caught up.
 
-The 1.125 multiplier increases reordering resilience. Implementers MAY
-experiment with using other multipliers, bearing in mind that a lower multiplier
-reduces reordering resilience and increases spurious retransmissions, and a
-higher multiplier increases loss recovery delay.
-
-This mechanism is based on Early Retransmit for TCP {{?RFC5827}}. However,
-{{?RFC5827}} does not include the timer described above. Early Retransmit is
-prone to spurious retransmissions due to its reduced reordering resilence
-without the timer. This observation led Linux TCP implementers to implement a
-timer for TCP as well, and this document incorporates this advancement.
+Implementers MAY experiment with using other reordering fractoins, bearing

fractions

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#pullrequestreview-172368439

---

From: ianswett <[email-masked]>
Date: Tue, 06 Nov 2018 23:58:02 -0800

52aa21a  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/1c2596eb43b86271f6fb12c8ee771e9c009f4900..52aa21aaa0e49b7db5c0f20c306bbb2dc18850be

---

From: Subodh Iyengar <[email-masked]>
Date: Fri, 09 Nov 2018 01:35:56 -0800

i think this diff would have to change SetLossDetectionAlarm as well. Currently SetLossDetectionAlarm sets the loss alarm based on the last unacked packet

```
   loss_detection_timer.set(
      time_of_last_sent_retransmittable_packet + timeout)
```

However in the case of time reordering, we would have to set the time based on the least unacked packet instead.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#issuecomment-437303613

---

From: janaiyengar <[email-masked]>
Date: Mon, 12 Nov 2018 03:49:56 -0800

FWIW, I'm in favor of this algorithmic change (remove time-based loss detection), but this change does not remove ER.  Early retransmit is exactly what the timer is used for, which gets armed if there are < 3 packets beyond the unacked packet. What we want is FR-with-packet-threshold and ER-with-time-threshold.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#issuecomment-437851876

---

From: janaiyengar <[email-masked]>
Date: Mon, 12 Nov 2018 03:50:13 -0800

janaiyengar commented on this pull request.

 ### Fast Retransmit
 
 An unacknowledged packet is marked as lost when an acknowledgment is received
 for a packet that was sent a threshold number of packets (kReorderingThreshold)
-and/or a threshold amount of time after the unacknowledged packet. Receipt of
-the acknowledgement indicates that a later packet was received, while the
-reordering threshold provides some tolerance for reordering of packets in the
-network.
+or a threshold amount of time (kTimeReorderingFraction) after the

how 'bout just kPacketThreshold and kTimeThreshold? The context makes clear what it's used for and exactly what the units are.

> @@ -274,34 +274,14 @@ TCP-NCR {{?RFC4653}}, to improve QUIC's reordering resilience.
 Time threshold loss detection uses a time threshold to determine how much
 reordering to tolerate.  In this document, the threshold is expressed as a
 fraction of an RTT, but implemenantations MAY experiment with absolute
-thresholds.  This may be used either as a replacement for a packet reordering
-threshold or in addition to it.
-
-When a larger packet is acknowledged, if it was sent more than the threshold
-after any in flight packets, those packets are immediately declared lost.
-Otherwise, a timer is set for the the reordering threshold minus the time
-difference between the earliest in flight packet and the largest newly
-acknowledged packet.  Note that in some cases the timer could become longer when
-packets are acknowleged out of order. The RECOMMENDED time threshold, expressed
+thresholds.  It is recommended this is is used in conjunction with packet
+threshold fast retransmit. The RECOMMENDED time threshold, expressed

This sentence is mostly unclear ("in conjunction with packet threshold fast retransmit") and not really useful. I would drop it entirely.

> -Unacknowledged packets close to the tail may have fewer than
-kReorderingThreshold retransmittable packets sent after them.  Loss of such
-packets cannot be detected via Packet Threshold Fast Retransmit. To enable
-ack-based loss detection of such packets, receipt of an acknowledgment for
-the last outstanding retransmittable packet triggers the Early Retransmit
-process, as follows.
-
-If there are unacknowledged in-flight packets still pending, they should
-be marked as lost. To compensate for the reduced reordering resilience, the
-sender SHOULD set a timer for a small period of time. If the unacknowledged
-in-flight packets are not acknowledged during this time, then these
-packets MUST be marked as lost.
-
-An endpoint SHOULD set the timer such that a packet is marked as lost no earlier
-than 1.125 * max(SRTT, latest_RTT) since when it was sent.
+An endpoint SHOULD declare packets lost no earlier than

I don't think the early retransmit section should be removed. This is a separate mechanism, and it is the only thing that uses the time threshold. I think a different structure might be useful... I'd actually argue for removing the time threshold section and leaving ER as is, since the time threshold section doesn't add much.

This is still true. I would leave this in.

> @@ -841,7 +807,7 @@ Pseudocode for SetLossDetectionTimer follows:
         time_of_last_sent_crypto_packet + timeout)
       return
     if (loss_time != 0):
-      // Early retransmit timer or time loss detection.
+      // Time threshold loss detection.

```suggestion
      // Early retransmit timer.
```

> @@ -875,7 +841,7 @@ Pseudocode for OnLossDetectionTimeout follows:
        RetransmitUnackedCryptoData()
        crypto_count++
      else if (loss_time != 0):
-       // Early retransmit or Time Loss Detection
+       // Time threshold loss Detection

```suggestion
       // Early retransmit
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#pullrequestreview-173860472

---

From: ianswett <[email-masked]>
Date: Tue, 20 Nov 2018 13:10:24 -0800

ianswett commented on this pull request.

I'm confused, so let's talk today.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#discussion_r235170048

---

From: ianswett <[email-masked]>
Date: Tue, 20 Nov 2018 13:11:14 -0800

21635b4  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/52aa21aaa0e49b7db5c0f20c306bbb2dc18850be..21635b4d047ca438b2cef45866913b218bda3455

---

From: Subodh Iyengar <[email-masked]>
Date: Tue, 20 Nov 2018 19:27:27 -0800

siyengar commented on this pull request.

I don't think this is only early retransmit @janaiyengar in this current form. loss_time is always set here

> @@ -907,14 +872,8 @@ Pseudocode for DetectLostPackets follows:
 DetectLostPackets(largest_acked):
   loss_time = 0
   lost_packets = {}
-  delay_until_lost = infinite
-  if (kUsingTimeLossDetection):
-    delay_until_lost =
-      (1 + time_reordering_fraction) *
-          max(latest_rtt, smoothed_rtt)
-  else if (largest_acked.packet_number == largest_sent_packet):
-    // Early retransmit timer.
-    delay_until_lost = 9/8 * max(latest_rtt, smoothed_rtt)
+  delay_until_lost = (1 + time_reordering_fraction) *

this looks like it will always set the loss time to be  1 + 1/8 rtt now. However this might be super aggressive for regular cases. This is even lower than 1/4 rtt for tlp. So tlp will never fire.

it seems like @janaiyengar  is right here. Early retransmit and time based loss detection are 2 separate mechanisms with different time_reordering_fractions.

something like:

```
 delay_until_lost = (1 + time_ordering_fraction) * max(lrtt, srtt)
  if (largest_acked.packet_number == largest_sent_packet):
     delay_until_lost = 9/8 * max(lrtt, srtt)
```

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#pullrequestreview-177063937

---

From: ianswett <[email-masked]>
Date: Fri, 30 Nov 2018 12:58:47 -0800

This only is used if there are retransmittable packets smaller than the largest acked, unlike TLP which aims for tail losses.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#discussion_r238000251

---

From: janaiyengar <[email-masked]>
Date: Fri, 30 Nov 2018 21:04:19 +0000 (UTC)

### Fast Retransmit
 
 An unacknowledged packet is marked as lost when an acknowledgment is received
-for a packet that was sent a threshold number of packets (kReorderingThreshold)
-and/or a threshold amount of time after the unacknowledged packet. Receipt of
-the acknowledgement indicates that a later packet was received, while the
-reordering threshold provides some tolerance for reordering of packets in the
-network.
+for a packet that was sent kReorderingThreshold number of packets or
+kTimeReorderingFraction amount of time after the unacknowledged packet.

suggestion: expand this into a bulleted list. "Fast Retransmit uses two thresholds to mark packets as lost..."

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#pullrequestreview-180448488

---

From: ianswett <[email-masked]>
Date: Fri, 30 Nov 2018 13:05:10 -0800

5afcc2a  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/21635b4d047ca438b2cef45866913b218bda3455..5afcc2a7c9a4bcd7dc0443e2c1c46b6f7e9f9d97

---

From: ianswett <[email-masked]>
Date: Fri, 30 Nov 2018 13:16:12 -0800

d606f71  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/5afcc2a7c9a4bcd7dc0443e2c1c46b6f7e9f9d97..d606f714ab878d577e09c71f7fca9dff009e6e8f

---

From: ianswett <[email-masked]>
Date: Fri, 30 Nov 2018 13:45:19 -0800

fd835fa  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/d606f714ab878d577e09c71f7fca9dff009e6e8f..fd835fafc27b439f39529a8bd1653362633baece

---

From: ianswett <[email-masked]>
Date: Fri, 30 Nov 2018 13:51:50 -0800

561e227  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/fd835fafc27b439f39529a8bd1653362633baece..561e22717749ccc0f7d8f22c8d9c8fdb52355954

---

From: ianswett <[email-masked]>
Date: Fri, 30 Nov 2018 21:52:36 +0000 (UTC)

7560bb4  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/561e22717749ccc0f7d8f22c8d9c8fdb52355954..7560bb462cacfbfe7cfd5e56ceb12ba846fa03a5

---

From: Subodh Iyengar <[email-masked]>
Date: Fri, 30 Nov 2018 13:53:36 -0800

not sure what you mean.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#discussion_r238013939

---

From: ianswett <[email-masked]>
Date: Fri, 30 Nov 2018 14:10:37 -0800

c3bc7bb  Merge branch 'master' into ianswett-both-thresholds

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/7560bb462cacfbfe7cfd5e56ceb12ba846fa03a5..c3bc7bbecfcd015aea92ced387d2a5f6816791a2

---

From: ianswett <[email-masked]>
Date: Fri, 30 Nov 2018 14:14:31 -0800

loss_time will only be non-0 if there are unacknowledged retransmittable packets sent prior to the largest acked packet.  In that case, the loss threshold declares the unacknowledged packet lost.  If there are no unacked packets less than largest acked, then the TLP would be armed, and as you said, it has a longer timeout.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#discussion_r238019097

---

From: ianswett <[email-masked]>
Date: Fri, 30 Nov 2018 14:17:54 -0800

ddfe711  Update draft-ietf-quic-recovery.md

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974/files/c3bc7bbecfcd015aea92ced387d2a5f6816791a2..ddfe711e11ce216154b7b566433e5ebb12dcb97a

---

From: janaiyengar <[email-masked]>
Date: Fri, 30 Nov 2018 17:17:10 -0800

I was thinking about this as a fix to ER, but I'm now convinced that this is a better framing. I'm suggesting some editorial changes in #2080, but I'm quite happy with the direction this is heading in. 

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1974#issuecomment-443386175