Subject: [quicwg/base-drafts] Add a loss_time per packet number space (#2451)

From: ianswett <[email-masked]>
Date: Mon, 11 Feb 2019 15:31:58 +0000 (UTC)

Fixes #2435 

I failed to fully think this through when #2417 landed, but the intent was always that time threshold loss detection apply to Initial and Handshake packet number spaces, as well as ApplicationData.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Add a loss_time per packet number space

-- File Changes --

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

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/2451.patch
https://github.com/quicwg/base-drafts/pull/2451.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/2451

---

From: ianswett <[email-masked]>
Date: Mon, 11 Feb 2019 07:45:57 -0800

@ianswett pushed 1 commit.

cee749c18d519bf4e26e281e212749b12fa9aee0  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/2451/files/ec2418410ceb50526dad6b8fe94f751378ff83fd..cee749c18d519bf4e26e281e212749b12fa9aee0

---

From: Marten Seemann <[email-masked]>
Date: Mon, 11 Feb 2019 07:46:00 -0800

marten-seemann commented on this pull request.

This is basically exactly what I just worked out on paper an hour ago, before running into https://github.com/quicwg/base-drafts/issues/2435#issuecomment-462371300.

I believe you forgot to change `OnLossDetectionTimeout()` to the following:
```
OnLossDetectionTimeout():
  min_loss_time = min_non_zero(loss_time[Initial], loss_time[Handshake], loss_time[ApplicationData])
  if (min_loss_time != 0):
    // Time threshold loss Detection
    DetectLostPackets(packet number space with the min_loss_time)
  else if (crypto packets are in flight):
    // Crypto retransmission timeout.
    RetransmitUnackedCryptoData()
    crypto_count++
  else:
    // PTO
    SendOneOrTwoPackets()
    pto_count++

  SetLossDetectionTimer()
```

> @@ -1029,6 +1028,12 @@ SetLossDetectionTimer():
     loss_detection_timer.cancel()
     return
 
+  for (loss_time : loss_times) {

I don't think this guarantees that you're picking the earliest timer. We need something like 
```
min_loss_time = min_non_zero(loss_time[Initial], loss_time[Handshake], loss_time[ApplicationData])
if (min_loss_time != 0):
    loss_detection_timer.update(min_loss_time)
    return
```

> @@ -1117,11 +1115,11 @@ DetectLostPackets(pn_space):
       if (unacked.in_flight):
         lost_packets.insert(unacked)
     else if (pn_space == ApplicationData):

Just `else`, no `else if`.

> @@ -873,10 +873,9 @@ max_ack_delay:
   received ACK frame may be larger due to late timers, reordering,
   or lost ACKs.
 
-loss_time:
-: The time at which the next packet will be considered lost based on
-  exceeding the reordering window in time. Only applies to the ApplicationData
-  packet number space.
+loss_times[kPacketNumberSpace]:

Nit: `loss_time` would be more consistent, since we also use `largest_acked_packet[kPacketNumberSpace]`, not `largest_acked_packets[kPacketNumberSpace]`.

-- 
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/2451#pullrequestreview-202171753

---

From: Marten Seemann <[email-masked]>
Date: Mon, 11 Feb 2019 08:04:00 -0800

> @@ -1067,14 +1066,18 @@ Pseudocode for OnLossDetectionTimeout follows:
 
 ~~~
 OnLossDetectionTimeout():
-  if (crypto packets are in flight):
+  packets_lost = false
+  for pn_space in [ Initial, Handshake, ApplicatonData ]:
+    if (loss_times[pn_space] != 0):
+      // Time threshold loss Detection
+      DetectLostPackets(pn_space)

It seems a bit wasteful to run this for every packet number space that has a non-zero `loss_time`, since we'll only detect lost packets in the space that has the earliest `loss_time`.

> @@ -1067,14 +1066,18 @@ Pseudocode for OnLossDetectionTimeout follows:
 
 ~~~
 OnLossDetectionTimeout():
-  if (crypto packets are in flight):
+  packets_lost = false
+  for pn_space in [ Initial, Handshake, ApplicatonData ]:
+    if (loss_times[pn_space] != 0):
+      // Time threshold loss Detection
+      DetectLostPackets(pn_space)
+      packets_lost = true
+  // Don't retransmit all crypto data if a packet was just lost.
+  if (!packets_lost &&

If `packets_lost = true`, we'd send PTO packets. I don't think this is the intention. We should return early in that case.

-- 
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/2451#pullrequestreview-202187885

---

From: ianswett <[email-masked]>
Date: Mon, 11 Feb 2019 08:20:07 -0800

5339f9a8b38958be9091ce2dd82a0639236a5428  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/2451/files/cee749c18d519bf4e26e281e212749b12fa9aee0..5339f9a8b38958be9091ce2dd82a0639236a5428

---

From: ianswett <[email-masked]>
Date: Mon, 11 Feb 2019 16:20:33 +0000 (UTC)

f6e85a0fa4ca87228970e2af0bd2e81ca1697453  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/2451/files/5339f9a8b38958be9091ce2dd82a0639236a5428..f6e85a0fa4ca87228970e2af0bd2e81ca1697453

---

From: ianswett <[email-masked]>
Date: Mon, 11 Feb 2019 08:24:12 -0800

ianswett commented on this pull request.

 ~~~

I added GetEarliestLossTime, which I think makes this more efficient and correct.

-- 
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/2451#discussion_r255582852

---

From: ianswett <[email-masked]>
Date: Mon, 11 Feb 2019 16:25:07 +0000 (UTC)

da874788e729470f9587ad2194c334f5e71f528c  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/2451/files/f6e85a0fa4ca87228970e2af0bd2e81ca1697453..da874788e729470f9587ad2194c334f5e71f528c

---

From: ianswett <[email-masked]>
Date: Mon, 11 Feb 2019 08:25:35 -0800

Added GetEarliestLossTime(), PTAL

-- 
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/2451#discussion_r255583547

---

From: ianswett <[email-masked]>
Date: Mon, 11 Feb 2019 16:27:02 +0000 (UTC)

d183dbcf3fec1a338259abe3fc657645b2b6fbaa  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/2451/files/da874788e729470f9587ad2194c334f5e71f528c..d183dbcf3fec1a338259abe3fc657645b2b6fbaa

---

From: Marten Seemann <[email-masked]>
Date: Mon, 11 Feb 2019 17:29:56 -0800

It's a big annoying that we need the `GetEarliestLossTime()` function for something that trivial.
If we initialize the loss times to infinity, taking the minimum would become more straightforward, but we'd still need some code to tell which packet number space the chosen time comes from, so I'm not sure if this change would really help.

> @@ -1022,13 +1021,31 @@ timers wake up late. Timers set in the past SHOULD fire immediately.
 Pseudocode for SetLossDetectionTimer follows:
 
 ~~~
+// Returns the earliest loss_time and the packet number
+// space it's from.  Returns 0 if all times are 0.
+GetEarliestLossTime():
+  time = loss_time[Initial]
+  space = Initial
+  for pn_space in [ Handshake, ApplicatonData ]:
+    if loss_time[pn_space] != 0 &&
+       (time == 0 || loss_time[pn_space] < time):
+      time = loss_time[pn_space];
+      space = Initial

`space = pn_space`

>  SetLossDetectionTimer():
   // Don't arm timer if there are no ack-eliciting packets
   // in flight.
   if (no ack-eliciting packets in flight):
     loss_detection_timer.cancel()
     return
 
+  [loss_time, pn_space] = GetEarliestLossTime()

In Python, you don't need square brackets to receive multiple return values.

And since we're not using the the `pn_space` here, we could write: `loss_time, _ = GetEarliestLossTime()`

> @@ -1067,14 +1078,15 @@ Pseudocode for OnLossDetectionTimeout follows:
 
 ~~~
 OnLossDetectionTimeout():
-  if (crypto packets are in flight):
+  [loss_time, pn_space] = GetEarliestLossTime()

Same here.

> @@ -1067,14 +1078,15 @@ Pseudocode for OnLossDetectionTimeout follows:
 
 ~~~
+  [loss_time, pn_space] = GetEarliestLossTime()
+  if (loss_time != 0):

This comment only makes sense for someone who followed the evolution of this algorithm. We should instead have a comment that describes when to retransmit all crypto data.

-- 
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/2451#pullrequestreview-202436241

---

From: ianswett <[email-masked]>
Date: Tue, 12 Feb 2019 08:50:16 -0800

89c8c3b8bd1e79692a93ab312820cea63f560a4a  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/2451/files/d183dbcf3fec1a338259abe3fc657645b2b6fbaa..89c8c3b8bd1e79692a93ab312820cea63f560a4a

---

From: ianswett <[email-masked]>
Date: Tue, 12 Feb 2019 08:50:52 -0800

8cfa8346c072d629f0b9397f9b7795327b90fc49  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/2451/files/89c8c3b8bd1e79692a93ab312820cea63f560a4a..8cfa8346c072d629f0b9397f9b7795327b90fc49

---

From: ianswett <[email-masked]>
Date: Tue, 12 Feb 2019 08:51:46 -0800

f7fb4829175e975920b1026cc0d4431301a14dea  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/2451/files/8cfa8346c072d629f0b9397f9b7795327b90fc49..f7fb4829175e975920b1026cc0d4431301a14dea

---

From: Marten Seemann <[email-masked]>
Date: Tue, 12 Feb 2019 16:15:53 -0800

marten-seemann approved this pull request.

LGTM, minus one comment.

 ~~~
+      space = pn_space
+  return [time, space]

In Python you don’t need the brackets here. Sorry for missing this on my earlier review. 

-- 
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/2451#pullrequestreview-202974943

---

From: ianswett <[email-masked]>
Date: Wed, 13 Feb 2019 06:02:20 -0800

be00d3c1013de2900569cf4ea374cf53069b6188  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/2451/files/f7fb4829175e975920b1026cc0d4431301a14dea..be00d3c1013de2900569cf4ea374cf53069b6188

---

From: ianswett <[email-masked]>
Date: Wed, 13 Feb 2019 06:02:35 -0800

~~~

Thanks.

-- 
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/2451#discussion_r256407239

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 20 Feb 2019 15:53:18 -0800

janaiyengar approved this pull request.

This looks good, so I'll merge this. I think we need largest_acked in DetectLostPackets to be per pn_space as well though... what do you think?

-- 
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/2451#pullrequestreview-206062207

---

From: Jana Iyengar <[email-masked]>
Date: Wed, 20 Feb 2019 23:53:30 +0000 (UTC)

Merged #2451 into master.

-- 
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/2451#event-2153532086