Subject: [quicwg/base-drafts] Prevent an unlikely deadlock (#1965)

From: ianswett <[email-masked]>
Date: Sun, 04 Nov 2018 23:40:17 -0800

QUIC, unlike TCP, allows the connection to get into a situation where there could be packets in flight, and a connection could even be CWND limited, but there may not be any outstanding data to retransmit.

The suggested solution is to send a retransmittable frame.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Prevent an unlikely deadlock

-- File Changes --

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

-- Patch Links --

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

---

From: ianswett <[email-masked]>
Date: Mon, 05 Nov 2018 00:00:45 -0800

@ianswett pushed 1 commit.

38dbee0  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/1965/files/e49f5b753daeb2740d3d1ed573d58bebbe053207..38dbee065f7db61f45809718c3fd397f19f540a7

---

From: ianswett <[email-masked]>
Date: Mon, 05 Nov 2018 00:02:39 -0800

5fc3b2e  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/1965/files/38dbee065f7db61f45809718c3fd397f19f540a7..5fc3b2e95ccd6f9377fb2a4978398a5a82c64b4d

---

From: martinduke <[email-masked]>
Date: Mon, 05 Nov 2018 00:26:05 -0800

martinduke approved this pull request.

I agree with the concept, though I have some problems with the explanatory text.

One zoom-out question about TLP in QUIC: If there's a tail loss, you'll have to wait for an entire delayed-ack timeout to send, wait at worst for another DAT to get the ack, then a reordering timeout to declare the intervening packets lost. How does that compare to a plain old RTO?

> @@ -418,6 +418,12 @@ used to send a probe into the network prior to establishing any packet loss,
 prior unacknowledged packets SHOULD NOT be marked as lost when a TLP timer
 expires.
 
+If no new data or unacknowledged data is available to send, a retransmittable
+frame SHOULD be sent.  Sending a retransmittable frame ensures that any in
+flight packets are acknowledged or declared lost in a timely manner,

I don't think TLP accelerates acknowledgment of in-flight pkts unless you happen to hit what the maximum number of delayed-acked pkts are.

So I would delete "acknowledged or"

> @@ -418,6 +418,12 @@ used to send a probe into the network prior to establishing any packet loss,
 prior unacknowledged packets SHOULD NOT be marked as lost when a TLP timer
 expires.
 
+If no new data or unacknowledged data is available to send, a retransmittable
+frame SHOULD be sent.  Sending a retransmittable frame ensures that any in
+flight packets are acknowledged or declared lost in a timely manner,
+potentially preventing a deadlock if all in flight packets contain no data

Delete everything after "deadlock."

-- 
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/1965#pullrequestreview-171445838

---

From: martinduke <[email-masked]>
Date: Mon, 05 Nov 2018 00:28:29 -0800

D'oh! comments passed in flight.

+If no new data or unacknowledged data is available to send, a retransmittable
+frame SHOULD be sent.  Sending a retransmittable frame ensures that any in
+flight packets are acknowledged or declared lost in a timely manner.

"acknowledged or" remains problematic.

-- 
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/1965#pullrequestreview-171448802

---

From: ianswett <[email-masked]>
Date: Mon, 05 Nov 2018 00:29:13 -0800

ianswett commented on this pull request.

Well, if you TLP, then you haven't received an ACK that contained any information about the in flight packets, because otherwise you'd fast or early retransmit them.  So you have some number of in flight packets, and you don't know what their status is.  It's possible the ACK was just lost, etc.  So in that sense, it accelerates receiving an acknowledgement for them if they were in fact not 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/1965#discussion_r230663696

---

From: ianswett <[email-masked]>
Date: Mon, 05 Nov 2018 00:30:52 -0800

Sorry, I update the text right as you were reviewing, 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/1965#discussion_r230664091

---

From: ianswett <[email-masked]>
Date: Mon, 05 Nov 2018 00:31:24 -0800

howso?

-- 
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/1965#discussion_r230664195

---

From: martinduke <[email-masked]>
Date: Mon, 05 Nov 2018 00:33:06 -0800

martinduke commented on this pull request.

Ah yes, ack losses. You're 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/1965#discussion_r230664599

---

From: martinduke <[email-masked]>
Date: Mon, 05 Nov 2018 08:34:15 +0000 (UTC)

Never mind, see above.

-- 
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/1965#discussion_r230664862

---

From: martinduke <[email-masked]>
Date: Mon, 05 Nov 2018 00:35:08 -0800

New data also prevents a deadlock.

-- 
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/1965#discussion_r230665079

---

From: Mike Bishop <[email-masked]>
Date: Mon, 05 Nov 2018 01:30:21 -0800

MikeBishop commented on this pull request.

+If no new data or unacknowledged data is available to send, a retransmittable
+frame SHOULD be sent.  Sending a retransmittable frame ensures that any in
+flight packets are acknowledged or declared lost in a timely manner.
+Otherwise, a deadlock results if there is no available congestion window and
+all in flight packets contain no data that can be retransmitted.

Hyphenate "in-flight" when used before the noun this way.

-- 
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/1965#pullrequestreview-171469749

---

From: ianswett <[email-masked]>
Date: Mon, 05 Nov 2018 02:53:36 -0800

9905361  Mike in-flight

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1965/files/5fc3b2e95ccd6f9377fb2a4978398a5a82c64b4d..9905361d72c7b94468ccc8400dcc6220beddac7d

---

From: ekr <[email-masked]>
Date: Mon, 05 Nov 2018 03:33:53 -0800

I feel like maybe I don't understand this. It's titled "deadlock" but it looks to me like it's really just RTO. Am I misunderstanding?

-- 
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/1965#issuecomment-435843746

---

From: ianswett <[email-masked]>
Date: Mon, 05 Nov 2018 15:32:23 +0000 (UTC)

Good question, @ekr 

It's definitely a detail point, but I think the above approach is likely the ideal fix.  But here's what I expect to happen now.

If the implementation stores some state saying "the tlp alarm fired, but I couldn't send anything, and I'll remember that in case there is some data I can send in the near future." then when there's new data, everything should be fixed, though you'll also only be able to send a single packet.  And if that packet or the corresponding ACK is lost, it'll be another TLP before you can send a packet.

Alternately, an implementation could fire the alarm, realize it can't send anything, then not re-arm the alarm(since if it was re-armed, it would just fire immediately and you'd spin).

The second approach is a deadlock.  The first one is just going to be very slow recovery.  Both seem somewhat suboptimal.

There's another solution to this, which is to declare all in-flight packets lost.  But that goes against the approach we use throughout QUIC loss recovery where we don't declare packets lost until a larger packet is acknowledged.

OT: @martinduke pointed out that this should be fixed for RTO as well, since it's possible between TLP and RTO(or between two RTOs) in-flight data is cancelled, so now there's nothing to 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/1965#issuecomment-435917790

---

From: MikkelFJ <[email-masked]>
Date: Mon, 05 Nov 2018 09:02:33 -0800

mikkelfj commented on this pull request.

> @@ -142,7 +142,7 @@ of frames contained in a packet affect recovery and congestion control logic:
 
 * Packets that contain only ACK frames do not count toward congestion control
   limits and are not considered in-flight. Note that this means PADDING frames
-  cause packets to contribute toward bytes in flight without directly causing an
+  cause packets to contribute toward bytes in-flight without directly causing an
   acknowledgment to be sent.

I think it was agreed to spell this "bytes in flight" but I could be wrong.

-- 
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/1965#pullrequestreview-171658068

---

From: Matt Olson <[email-masked]>
Date: Mon, 05 Nov 2018 12:42:09 -0800

Rather than adding a new paragraph to patch the hole, I'd update the description of what a "probe" packet is. Currently it's "a packet which is not subject to CC and which contains unsent data (if possible) or sent data (otherwise)."

I'd update this sentence and move it somewhere to apply to both TLP and RTO probes.

-- 
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/1965#issuecomment-436027365

---

From: Nick Banks <[email-masked]>
Date: Mon, 05 Nov 2018 20:51:36 +0000 (UTC)

@ian do you have an example of a case where you have packets in flight but no outstanding data to retransmit? I was trying to come up with one but couldn't. In the case of a stream getting cancelled, you'd still have the RST_STREAM frame that needs to be sent. 

-- 
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/1965#issuecomment-436030148

---

From: MikkelFJ <[email-masked]>
Date: Mon, 05 Nov 2018 20:55:20 +0000 (UTC)

@nibanks couldn't RST happen async separate from the pipeline of schedule transmissions. More generally, data might exist, but not (yet) in the low level tranmissions system that deals with retransmission.

-- 
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/1965#issuecomment-436031286

---

From: Nick Banks <[email-masked]>
Date: Mon, 05 Nov 2018 12:56:57 -0800

@mikkelfj that's really an implementation detail. For me, resetting a stream, queuing the RST_STREAM frame for delivery and removing the actual stream data for retransmission is an atomic operation.

-- 
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/1965#issuecomment-436031799

---

From: MikkelFJ <[email-masked]>
Date: Mon, 05 Nov 2018 21:27:16 +0000 (UTC)

@nibanks I agree, but because it is an implementation detail, the protocol can make general assumptions on how implementations work. Forcing an implemtation to operate atomically is not ideal.

-- 
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/1965#issuecomment-436041260

---

From: Nick Banks <[email-masked]>
Date: Mon, 05 Nov 2018 13:32:27 -0800

@mikkelfj I totally agree. I was just trying to understand if there were any non-implementation specific scenarios where this could happen (in other words, does this apply to my implementation or can I ignore this bit of text).

-- 
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/1965#issuecomment-436043007

---

From: MikkelFJ <[email-masked]>
Date: Mon, 05 Nov 2018 22:23:11 +0000 (UTC)

If `in-flight` is used, I think other text needs to updated also. The motivation for not using hyphen was the confusion with `bytes_in_flight` as a variable name.

-- 
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/1965#discussion_r230936149

---

From: Mike Bishop <[email-masked]>
Date: Tue, 13 Nov 2018 16:19:27 -0800

"in-flight" when used as a compound modifier (in-flight packets, for example) should usually have a hyphen before the noun.  Here, it's after the noun, so this wouldn't get one.  See [here](https://www.quickanddirtytips.com/education/grammar/how-to-use-a-hyphen), for example.

-- 
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/1965#discussion_r233273505