Re: [quicwg/base-drafts] Adds substantive descriptions of loss detection mechanisms (#801)

[ianswett <[e-mail]>]

ianswett commented on this pull request.

Lots of comments, but I like the content and structure.

> -    TCP's Tail Loss Probe.
-
-  * If all else fails, a Retransmission Timeout (RTO) alarm is always set when
-    any retransmittable packet is outstanding. When this alarm fires, all
-    unacknowledged packets are marked as lost.
-
-  * Instead of a packet threshold to tolerate reordering, a QUIC sender may use
-    a time threshold. This allows for senders to be tolerant of short periods of
-    significant reordering. In this mechanism, a QUIC sender marks a packet as
-    lost when a larger packet number is acknowledged and a threshold amount of
-    time has passed since the packet was sent.
-
-  * Handshake packets, which contain STREAM frames for stream 0, are
-    critical to QUIC transport and crypto negotiation, so a separate alarm
-    period is used for them.
+QUIC uses both ack information and timeouts to detect lost packets, and this

Also, ack information and timeouts is correct, but not super-descriptive and it might be worth saying once that this is sender side, even though it's obvious to us.  Maybe something like: "QUIC senders use both received acknowledgements and timeouts to detect and recover from lost packets.  This section provides..."

> +
+## Computing the RTT estimate
+
+(To be filled)
+
+
+## Ack-based Detection
+
+Ack-based loss detection implements the spirit of TCP's Fast Retransmit
+{{!RFC5681}}, Early Retransmit {{!RFC5827}}, FACK, and SACK loss recovery
+{{!RFC6675}}. This section provides an overview of how these algorithms are
+implemented in QUIC.
+
+### Fast Retransmit
+
+An unacknowledged packet is marked as lost when an acknowledgment is received

Given I just had the conversation about "acknowledgement" and what it meant, do we need to clarify it somewhere in this doc?

> +## Ack-based Detection
+
+Ack-based loss detection implements the spirit of TCP's Fast Retransmit
+{{!RFC5681}}, Early Retransmit {{!RFC5827}}, FACK, and SACK loss recovery
+{{!RFC6675}}. This section provides an overview of how these algorithms are
+implemented in QUIC.
+
+### 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)
+after the unacknowledged packet. Receipt of the ack indicates that a later
+packet was received, while kReorderingThreshold provides some tolerance for
+reordering of packets in the network. 
+
+The RECOMMENDED value for kReorderingThreshold is 3.

RECOMMENDED initial value?  Esp given you talk about changing it below.

> +{{!RFC6675}}. This section provides an overview of how these algorithms are
+implemented in QUIC.
+
+### 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)
+after the unacknowledged packet. Receipt of the ack indicates that a later
+packet was received, while kReorderingThreshold provides some tolerance for
+reordering of packets in the network. 
+
+The RECOMMENDED value for kReorderingThreshold is 3.
+
+We derive this default from recommendations for TCP loss recovery {{!RFC5681}}
+{{!RFC6675}}. It is possible for networks to exhibit higher degrees of
+reordering, causing a sender to spuriously detect losses. Spurious loss

nit: I think "detect spurious losses" reads a bit better, but I'm not sure.

> +{{!RFC6675}}. This section provides an overview of how these algorithms are
+implemented in QUIC.
+
+### 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)
+after the unacknowledged packet. Receipt of the ack indicates that a later
+packet was received, while kReorderingThreshold provides some tolerance for
+reordering of packets in the network. 
+
+The RECOMMENDED value for kReorderingThreshold is 3.
+
+We derive this default from recommendations for TCP loss recovery {{!RFC5681}}
+{{!RFC6675}}. It is possible for networks to exhibit higher degrees of
+reordering, causing a sender to spuriously detect losses. Spurious loss

Also, Spurious loss detection is sort of odd.   I'd go with "Detecting spurious losses leads..."

> +reordering, causing a sender to spuriously detect losses. Spurious loss
+detection leads to unnecessary retransmissions and may result in degraded
+performance due to the actions of the congestion controller upon detecting
+loss. Implementers MAY use algorithms developed for TCP, such as TCP-NCR
+{{!RFC4653}}, to improve QUIC's reordering resilience, though care should be
+taken to map TCP specifics to QUIC correctly. Similarly, using time-based loss
+detection to deal with reordering, such as in PR-TCP, should be more readily
+usable in QUIC. Making QUIC deal with such networks is important open research,
+and implementers are encouraged to explore this space.
+
+### Early Retransmit
+
+Unacknowledged packets close to the tail may have fewer than
+kReorderingThreshold number of packets sent after them. Loss of such packets
+cannot be detected via Fast Retransmit. To enable ack-based loss detection of
+such packets, receipt of an acknowledgment for the last outstanding packet

Do you want to clarify that it's the last outstanding ackable packet?

Also, now that I read through this, it seems like it'd be worth doing early retransmit for any packets within kReorderingThreshold from the tail, but that's a sidethought.

> +loss. Implementers MAY use algorithms developed for TCP, such as TCP-NCR
+{{!RFC4653}}, to improve QUIC's reordering resilience, though care should be
+taken to map TCP specifics to QUIC correctly. Similarly, using time-based loss
+detection to deal with reordering, such as in PR-TCP, should be more readily
+usable in QUIC. Making QUIC deal with such networks is important open research,
+and implementers are encouraged to explore this space.
+
+### Early Retransmit
+
+Unacknowledged packets close to the tail may have fewer than
+kReorderingThreshold number of packets sent after them. Loss of such packets
+cannot be detected via Fast Retransmit. To enable ack-based loss detection of
+such packets, receipt of an acknowledgment for the last outstanding packet
+triggers the Early Retransmit process, as follows.
+
+If there are unacknowledged packets still pending, they ought to be

how about "still pending when the last ackable packet is acknowledged"

"ought to be" is sort of weak, how about "they must be declared lost." and drop the part about "since they are no subsequent packets to trigger a Fast Retransmit", since you say that in the preceding paragraph.

> +{{!RFC4653}}, to improve QUIC's reordering resilience, though care should be
+taken to map TCP specifics to QUIC correctly. Similarly, using time-based loss
+detection to deal with reordering, such as in PR-TCP, should be more readily
+usable in QUIC. Making QUIC deal with such networks is important open research,
+and implementers are encouraged to explore this space.
+
+### Early Retransmit
+
+Unacknowledged packets close to the tail may have fewer than
+kReorderingThreshold number of packets sent after them. Loss of such packets
+cannot be detected via Fast Retransmit. To enable ack-based loss detection of
+such packets, receipt of an acknowledgment for the last outstanding packet
+triggers the Early Retransmit process, as follows.
+
+If there are unacknowledged packets still pending, they ought to be
+retransmitted, since there are no subsequent packets to trigger a Fast

Here you use retransmitted, where in other cases you use "marked as lost" or "declared lost", which I think is better.

> +If there are unacknowledged packets still pending, they ought to be
+retransmitted, since there are no subsequent packets to trigger a Fast
+Retransmit. To compensate for the reduced reordering resilience, the sender
+SHOULD set an alarm for a small period of time. If the unacknowledged packets
+are not acknowledged during this time, then these packets are marked as lost.
+
+An endpoint SHOULD set the alarm such that a packet is marked as lost no earlier
+than 1.25 * max(SRTT, latest_RTT) since when it was sent. 
+
+Using max(SRTT, latest_RTT) protects from the two following cases:
+
+* the latest RTT sample is lower than the SRTT, perhaps due to reordering where
+packet whose ack triggered the Early Retransit process encountered a shorter
+path;
+
+* the SRTT is lower than the latest RTT sample, perhaps due to a sustained

nit: I think it's easier to read if it's parallel and the latest RTT comes first in both statements, since you're mostly describing why the latest_rtt would have a smaller/larger value.

> +without the alarm. This observation led Linux TCP implementers to implement an
+alarm for TCP as well, and this document incorporates this advancement.
+
+
+## Timer-based Detection
+
+Timer-based loss detection implements the spirit of TCP's Tail Loss Probe
+and Retransmission Timeout mechanisms.
+
+### Tail Loss Probe
+
+The algorithm described in this section is an adaptation of the Tail Loss Probe
+algorithm proposed for TCP {{!I-D.draft-dukkipati-tcpm-tcp-loss-probe}}.
+
+A packet sent at the tail is particularly vulnerable to slow loss detection,
+since subsequent packets (and acks) are needed to trigger ack-based

How about "since acks of subsequent packets are needed..."

> +alarm when a tail packet is transmitted. When this alarm fires, a Tail Loss
+Probe (TLP) packet is sent to evoke an acknowledgement from the receiver.
+
+The alarm duration, or Probe Timeout (PTO), is set based on the following
+conditions:
+
+* If there is exactly one unacknowledged packet, PTO SHOULD be scheduled for
+  max(2*SRTT, 1.5*SRTT+kDelayedAckTimeout)
+
+* If there are more than one unacknowledged packets, PTO SHOULD be scheduled for
+  max(2*SRTT, 10ms).
+
+* If RTO is earlier, schedule a TLP alarm in its place. That is, PTO SHOULD be
+  scheduled for min(RTO, PTO).
+
+kDelayedAckTimeout is the worst case delayed ACK timer.  When the is exactly one

worst case is a bit misleading, given alarms can go off late.  

fix: "When there is"

> +
+* If there is exactly one unacknowledged packet, PTO SHOULD be scheduled for
+  max(2*SRTT, 1.5*SRTT+kDelayedAckTimeout)
+
+* If there are more than one unacknowledged packets, PTO SHOULD be scheduled for
+  max(2*SRTT, 10ms).
+
+* If RTO is earlier, schedule a TLP alarm in its place. That is, PTO SHOULD be
+  scheduled for min(RTO, PTO).
+
+kDelayedAckTimeout is the worst case delayed ACK timer.  When the is exactly one
+unacknowledged packet, the alarm duration includes time for an acknowledgment to
+be received, and additionally, a kDelayedAckTimeout period to compensate for the
+delayed acknowledgment timer at the receiver.
+
+The RECOMMENDED value for kDelayedAckTimeout is 25ms.

As with Neal's new TCP proposal, QUIC should really have a default like 25ms, then allow negotiation.  So maybe say "The RECOMMENDED default value for kDelayedAckTimeout is 25ms, though the transport allows for negotiation of different values."

> +  scheduled for min(RTO, PTO).
+
+kDelayedAckTimeout is the worst case delayed ACK timer.  When the is exactly one
+unacknowledged packet, the alarm duration includes time for an acknowledgment to
+be received, and additionally, a kDelayedAckTimeout period to compensate for the
+delayed acknowledgment timer at the receiver.
+
+The RECOMMENDED value for kDelayedAckTimeout is 25ms.
+
+A PTO value of at least 2*SRTT ensures that the ACK is overdue. Using a PTO of
+exactly 1*SRTT may generate spurious probes, and 2*SRTT is simply the next
+integral value of RTT.
+
+(TODO: These values of 2 and 1.5 are a bit arbitrary. Reconsider these.)
+
+If the Retransmission Timeout (RTO, {{rto}}) is smaller than the computed PTO,

It's a bit confusing that the RTO is a thing you do and a timeout value.  Maybe call it RTO period when referring to the timeout value?  

> +unacknowledged packet, the alarm duration includes time for an acknowledgment to
+be received, and additionally, a kDelayedAckTimeout period to compensate for the
+delayed acknowledgment timer at the receiver.
+
+The RECOMMENDED value for kDelayedAckTimeout is 25ms.
+
+A PTO value of at least 2*SRTT ensures that the ACK is overdue. Using a PTO of
+exactly 1*SRTT may generate spurious probes, and 2*SRTT is simply the next
+integral value of RTT.
+
+(TODO: These values of 2 and 1.5 are a bit arbitrary. Reconsider these.)
+
+If the Retransmission Timeout (RTO, {{rto}}) is smaller than the computed PTO,
+then a PTO is scheduled for the smaller RTO period.
+
+To reduce latency, it is RECOMMENDED that the sender send two sequential TLP

One could potentially read two sequential TLP packets as two packets in a row immediately.  How about wording like "it is RECOMMENDED that the sender allow the TLP alarm to expire twice before setting an RTO alarm."

> +
+A PTO value of at least 2*SRTT ensures that the ACK is overdue. Using a PTO of
+exactly 1*SRTT may generate spurious probes, and 2*SRTT is simply the next
+integral value of RTT.
+
+(TODO: These values of 2 and 1.5 are a bit arbitrary. Reconsider these.)
+
+If the Retransmission Timeout (RTO, {{rto}}) is smaller than the computed PTO,
+then a PTO is scheduled for the smaller RTO period.
+
+To reduce latency, it is RECOMMENDED that the sender send two sequential TLP
+packets before setting an RTO alarm. When the first TLP packet is sent, the TLP
+alarm should be scheduled for a second TLP. On the second TLP packet, an RTO
+alarm should be scheduled {{rto}}.
+
+A TLP packet SHOULD carry new data when available. If new data is unavailable, a

is it worth acknowledging that flow control could prevent sending new data as well?

Maybe "A TLP packet SHOULD carry new data when possible.  If new data is unavailable or new data cannot be sent due to flow control, ..."

> +
+(TODO: These values of 2 and 1.5 are a bit arbitrary. Reconsider these.)
+
+If the Retransmission Timeout (RTO, {{rto}}) is smaller than the computed PTO,
+then a PTO is scheduled for the smaller RTO period.
+
+To reduce latency, it is RECOMMENDED that the sender send two sequential TLP
+packets before setting an RTO alarm. When the first TLP packet is sent, the TLP
+alarm should be scheduled for a second TLP. On the second TLP packet, an RTO
+alarm should be scheduled {{rto}}.
+
+A TLP packet SHOULD carry new data when available. If new data is unavailable, a
+TLP packet MAY retransmit unacknowledged data to potentially reduce recovery
+time. Since a TLP packet is sent as a probe into the network prior to
+establishing any packet loss, prior unacknowledged packets SHOULD NOT be marked
+as lost.

as lost when the TLP packet is sent."

> +time. Since a TLP packet is sent as a probe into the network prior to
+establishing any packet loss, prior unacknowledged packets SHOULD NOT be marked
+as lost.
+
+A TLP packet MUST NOT be blocked by the sender's congestion controller. The
+sender MUST however count these bytes as additional bytes in flight, since a TLP
+adds network load without establishing packet loss.
+
+A sender will commonly not know that a packet being sent is a tail packet.
+Consequently, a sender may have to arm or adjust the TLP alarm on every sent packet.
+
+### Retransmission Timeout {#rto}
+
+A Retransmission Timeout (RTO) alarm is the final backstop for loss
+detection. The algorithm used in QUIC is based on the RTO algorithm for TCP
+{{!RFC5681}} and is additionally resilient to spurious RTOs.

since you mention spurious RTOs, maybe reference 5682 as well?

> +### Retransmission Timeout {#rto}
+
+A Retransmission Timeout (RTO) alarm is the final backstop for loss
+detection. The algorithm used in QUIC is based on the RTO algorithm for TCP
+{{!RFC5681}} and is additionally resilient to spurious RTOs.
+
+When the last TLP packet is sent, an alarm is scheduled for the RTO time. When
+this alarm fires, the sender sends two Retransmission Timeout (RTO) packets, to
+evoke acknowledgements from the receiver, and restarts the RTO alarm.
+
+Similar to TCP {{!RFC6298}}, the RTO alarm duration is set based on the
+following conditions:
+
+* When the final TLP packet is sent, RTO is set to max(SRTT + 4*RTTVAR, minRTO)
+
+* When an RTO alarm fires, RTO is set to twice its current value.

nit; "RTO is doubled." seems a bit less ambiguous.

> +the network prior to establishing any packet loss, prior unacknowledged packets
+SHOULD NOT be marked as lost.
+
+An RTO packet MUST NOT be blocked by the sender's congestion controller. A
+sender MUST however count these bytes as additional bytes in flight, since an
+RTO packet adds network load without establishing packet loss.
+
+
+### Handshake Timeout
+
+Handshake packets, which contain STREAM frames for stream 0, are critical to
+QUIC transport and crypto negotiation, so a separate alarm period is used for
+them.
+
+The initial flight has no prior RTT sample.  A client SHOULD remember
+the previous RTT it observed when resumption is attempted and use that for an

This is mostly a good recommendation, but if the client changes networks, does it still apply?  

> +
+
+### Handshake Timeout
+
+Handshake packets, which contain STREAM frames for stream 0, are critical to
+QUIC transport and crypto negotiation, so a separate alarm period is used for
+them.
+
+The initial flight has no prior RTT sample.  A client SHOULD remember
+the previous RTT it observed when resumption is attempted and use that for an
+initial RTT value.  If no previous RTT is available, the initial RTT defaults
+to 100ms.
+
+Endpoints MUST retransmit handshake frames if not acknowledged within a
+time limit. This time limit will start as the largest of twice the RTT value
+and MinTLPTimeout.  Each consecutive handshake retransmission doubles the

MinTLPTimeout is not defined in this text, it's just used above as 10ms when calculating the TLP alarm.

> +sender MUST however count these bytes as additional bytes in flight, since an
+RTO packet adds network load without establishing packet loss.
+
+
+### Handshake Timeout
+
+Handshake packets, which contain STREAM frames for stream 0, are critical to
+QUIC transport and crypto negotiation, so a separate alarm period is used for
+them.
+
+The initial flight has no prior RTT sample.  A client SHOULD remember
+the previous RTT it observed when resumption is attempted and use that for an
+initial RTT value.  If no previous RTT is available, the initial RTT defaults
+to 100ms.
+
+Endpoints MUST retransmit handshake frames if not acknowledged within a

Currently we retransmit "all unacknowledged handshake frames", so we should probably say that?

-- 
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/801#pullrequestreview-65854911