Subject: [quicwg/base-drafts] Fix time loss detection and early retransmit (#394)

From: ianswett <[email-masked]>
Date: Mon, 13 Mar 2017 09:33:34 -0700

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

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

-- Commit Summary --

  * Fix time loss detection and early retransmit

-- File Changes --

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

-- Patch Links --

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

---

From: ianswett <[email-masked]>
Date: Mon, 13 Mar 2017 10:23:49 -0700

@ianswett pushed 1 commit.

26bd685  Fix trailing whitespace

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/394/files/876df8f8531522597adc6b4531dc941c21800c14..26bd685d6b8b5a42cf2ce8bdf36c509b7ed7bf18

---

From: janaiyengar <[email-masked]>
Date: Mon, 13 Mar 2017 10:51:53 -0700

janaiyengar commented on this pull request.

Thanks Ian, a few comments

-use_time_loss:
-: When true, loss detection operates solely based on reordering
-  threshold in time, rather than in packet number gaps.
+loss_time:
+: The time at which the next packet will be considered lost based on early
+transmit or exceeding the reordering window in time.

early transmit --> early retransmit

 sent_packets:
-: An association of packet numbers to information about them, including a time
-  field indicating the time a packet was sent and a bytes field indicating the
-  packet's size.
+: An association of packet numbers to information about them, including a number
+  field indicating the packet number, a time field indicating the time a packet
+  was sent and a bytes field indicating the packet's size.  sent_packets is

oxford comma nit: "... was sent, and a bytes field ..."

 sent_packets:
-: An association of packet numbers to information about them, including a time
-  field indicating the time a packet was sent and a bytes field indicating the
-  packet's size.
+: An association of packet numbers to information about them, including a number
+  field indicating the packet number, a time field indicating the time a packet
+  was sent and a bytes field indicating the packet's size.  sent_packets is
+  ordered by packet number, and packets remain in sent_packets until
+  acknowledged or lost.

nit: "until they are acknowledged or lost"

> @@ -258,8 +258,13 @@ follows:
    handshake_count = 0
    tlp_count = 0
    rto_count = 0
-   reordering_threshold = kReorderingThreshold
-   use_time_loss = false
+   if (UsingTimeLossDetection())
+     reordering_threshold = infinite
+     time_reordering_fraction = kTimeReorderingFraction
+   else:
+     reordering_threshold = kReorderingThreshold
+     time_reordering_fraction = infinite
+   lost_time = 0

loss_time = 0

> @@ -406,10 +410,9 @@ Pseudocode for SetLossDetectionAlarm follows:
         alarm_duration = 2 * smoothed_rtt
       alarm_duration = max(alarm_duration, kMinTLPTimeout)
       alarm_duration = alarm_duration << handshake_count
-    else if (largest sent packet is acked):
-      // Early retransmit
-      // with an alarm to reduce spurious retransmits.

I think this comment can fit in a line

> @@ -442,9 +445,9 @@ Pseudocode for OnLossDetectionAlarm follows:
        RetransmitAllHandshakePackets();
        handshake_count++;
      // TODO: Clarify early retransmit and time loss.
-     else if ():
+     else if (lost_time != 0):

loss_time

> @@ -463,9 +466,9 @@ Pseudocode for OnLossDetectionAlarm follows:
 ## Detecting Lost Packets
 
 Packets in QUIC are only considered lost once a larger packet number is
-acknowledged.  DetectLostPackets is called every time there is a new largest
-packet or if the loss detection alarm fires the previous largest acked packet is
-supplied.
+acknowledged.  DetectLostPackets is called every time an ack is received.
+If the loss detection alarm fires and the lost_time is set, the previous

Make loss_time or lost_time consistent. Either works. How about "reordering_threshold_in_time" and "reordering_threshold_in_packets" (or remove the "in" if you want more succinct) instead of loss_time and reordering_threshold ?

> @@ -463,9 +466,9 @@ Pseudocode for OnLossDetectionAlarm follows:
 ## Detecting Lost Packets
 
 Packets in QUIC are only considered lost once a larger packet number is
-acknowledged.  DetectLostPackets is called every time there is a new largest
-packet or if the loss detection alarm fires the previous largest acked packet is
-supplied.
+acknowledged.  DetectLostPackets is called every time an ack is received.
+If the loss detection alarm fires and the lost_time is set, the previous
+largest acked packet is supplied.

This paragraph is a little discontinuous. Let's submit it and we can fix it up later

> @@ -481,19 +484,31 @@ DetectLostPackets takes one parameter, acked, which is the largest acked packet.
 Pseudocode for DetectLostPackets follows:
 
 ~~~
-   DetectLostPackets(acked):
+   DetectLostPackets(largest_acked):

nit: "largest_acked" --> "largest_acked_number" ?

>       lost_packets = {}
-     foreach (unacked less than acked):
-       time_delta = acked.time_sent - unacked.time_sent
-       packet_delta = acked.packet_number - unacked.packet_number
-       if (time_delta > kTimeReorderThreshold * smoothed_rtt):
+     time_when_lost = 0;

This isn't the time but a wait period... suggestion: reordering_period ? or "short_timeout"? you could just call it short_timeout_period... up to you

>       lost_packets = {}
-     foreach (unacked less than acked):
-       time_delta = acked.time_sent - unacked.time_sent
-       packet_delta = acked.packet_number - unacked.packet_number
-       if (time_delta > kTimeReorderThreshold * smoothed_rtt):
+     time_when_lost = 0;
+     if (time_reordering_fraction == infinite):

This should be !=

>       lost_packets = {}
-     foreach (unacked less than acked):
-       time_delta = acked.time_sent - unacked.time_sent
-       packet_delta = acked.packet_number - unacked.packet_number
-       if (time_delta > kTimeReorderThreshold * smoothed_rtt):
+     time_when_lost = 0;
+     if (time_reordering_fraction == infinite):
+       time_when_lost =
+         (1 + time_reordering_fraction) * max(latest_rtt, smoothed_rtt)
+     else if (largest_acked.packet_number == largest_sent_packet):
+       // Early retransmit alarm.
+       time_when_lost = 9/8 * max(latest_rtt, smoothed_rtt)
+     foreach (unacked less than largest_acked.packet_number):
+       time_since_sent = now() - unacked.time_sent
+       packet_delta = largest_acked.packet_number - unacked.packet_number
+       if (time_since_sent > time_when_lost):

if time loss detection is disabled, won't time_when_lost be 0?

>           lost_packets.insert(unacked)
        else if (packet_delta > reordering_threshold)
          lost_packets.insert(unacked)
+       else if (loss_time == 0 && time_when_lost != 0):
+         loss_time = time_when_lost - time_since_sent

add a comment here saying something like "loss_time is used for setting the loss detection alarm later."

>       OnPacketsLost(lost_packets)
-     MaybeRetransmit(lost_packets)
+     foreach (packet in lost_packets)
+       sent_packets.remove(packet.packet_number)

does it make sense, for editorializing, to move these packets to a "lost_packets" structure? doesn't need to be done here, but thinking aloud

-- 
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/394#pullrequestreview-26611754

---

From: ianswett <[email-masked]>
Date: Mon, 13 Mar 2017 11:48:22 -0700

55d791c  Fix inconsistencies and nits

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/394/files/26bd685d6b8b5a42cf2ce8bdf36c509b7ed7bf18..55d791c481b3ee6d2c880d70e9f28ada5655db03

---

From: ianswett <[email-masked]>
Date: Mon, 13 Mar 2017 11:48:26 -0700

ianswett commented on this pull request.

Thanks Jana, updated.

 sent_packets:

Done.

 sent_packets:

I left it as is, because it's shorter.

It was removed.

    handshake_count = 0
    tlp_count = 0
    rto_count = 0

SGTM, I went with loss_time everywhere.

Done

SGTM.

loss_time is somewhat orthogonal to reordering theshold.  Do you mean reordering_threshold and time_reordering_fraction, which are more analagous?

 ~~~

It's a packet, not a number, because I use fields of the packet below, such as the time it was sent.

Thanks.

How about delay_until_lost?

Good point, I set it to infinite.

Possibly, though I still need a way to inform the congestion control of newly lost packets.  I was thinking of creating a pending_retransmissions data structure in congestion control to store any lost packets that couldn't be sent immediately?

-- 
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/394#pullrequestreview-26630643

---

From: janaiyengar <[email-masked]>
Date: Mon, 13 Mar 2017 12:19:40 -0700

janaiyengar approved this pull request.

-- 
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/394#pullrequestreview-26642491

---

From: janaiyengar <[email-masked]>
Date: Mon, 13 Mar 2017 12:22:02 -0700

Merged #394.

-- 
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/394#event-997857429