Subject: [QUIC] About loss detection and recovery in draft-iyengar-quic-loss-recovery-00

From: marcelo bagnulo braun <[email-masked]>
Date: Fri, 7 Oct 2016 08:05:20 +0200

Hi,

So, i have been trying to understand the packet loss detection and 
retransmission schemes for quic, described in 
draft-iyengar-quic-loss-recovery-00.

I had a few difficulties to understand how this works, based on the 
description in the draft. I include below what i think i understood, let 
me know if i got this right.

Section 2 and 3 mention the retransmission of lost packets, but if i 
understood it correctly, i think the draft would benefit from dropping 
the concept of retransmitted packet. I mean, I dont think there is such 
a thing as a retransmitted packet. What quic retransmits is the data 
within packets that were detected as lost, but the packet is not 
retransmitted. For starters, the packet containing the retransmitted 
data has a different PSN. But also, the content of the packet may be 
different as some frames are not to be retransmitted.

Moreover, if eventually some form of priority is implemented, i would 
guess that data with higher priority would be retransmitted earlier than 
data with lower priority. I think such flexibility would be useful.

Let me see if I understand the overall framework for loss detection and 
retransmission for quic. I think that quic detect packet loss, but 
retransmits data (that was sent in packets) so it probably possible to 
decouple the loss detection from the retransmission.

I understand that all data (control and application data) that is 
reliably transmitted is transmitted within a stream. Other data that is 
not transmitted within a given stream (like ACKs) is not reliably 
transmitted. Is this correct? If so, it may be worth stating it as a 
design principle, so people know that if they want to include control 
information such as other options to be reliably transmitted, they 
should do it within a stream.

So, if a sender has M ongoing streams, then it has M+1 sliding windows, 
i.e. one for each stream plus one for the packets at the connection 
level. Let's call the packet one, the packet window and the other the 
stream n window. The packet window is in packets, while the stream 
windows are in bytes.

The packet window has the following types of packets: packets acked, 
non-acked packets and lost packets. The left side of the window moves to 
packet number n when all packets with packet number lower than n are 
marked as acked or as lost. In other words, the left side of the window 
is the non-acked packet with lowest packet number. This corresponds to 
the "least unacked" packet mentioned in the draft.

Each stream window has the following types of bytes. bytes acked, bytes 
non-acked, bytes awaiting for transmission. Bytes non-acked are bytes 
that are contained in packets on flight. Bytes awaiting for transmission 
are bytes that either have not been sent yet or bytes that have been 
sent in packets that have been determined as lost.

Whenever a packet is acked, the bytes in each stream window 
corresponding to the data of each stream included in the acked packet 
are marked as acked.

Whenever a packet is determined as lost, the bytes in each stream window 
corresponding to the data of that stream included in the packet are 
marked as bytes awaiting for transmission.

Whenever a new packet is transmitted, the bytes in each stream window 
included in the packet are marked as non-acked.

Packet loss detection only operates using the packet window. So, each 
non-acked packet has an associated timer that when it times out, the 
packet is marked as lost. You can define any other mechanisms to detect 
packet loss only operating in this window, i believe.

Packet transmission otoh, needs to get data from the different stream 
windows, probably using the bytes awaiting for transmission with the 
lowest offset. This would include both the transmission of new data as 
well as retransmission of old data.

Do you think this properly describes the framework of operation for loss 
detection and retransmission of quic?

Regards, marcelo

---

From: Ian Swett <[email-masked]>
Date: Fri, 7 Oct 2016 15:13:39 -0400

Thanks for taking such a close look Marcelo, comments inline.

On Fri, Oct 7, 2016 at 2:05 AM, marcelo bagnulo braun <[email-masked]>
 wrote:

> retransmission schemes for quic, described in draft-iyengar-quic-loss-recove
> ry-00.
>
> description in the draft. I include below what i think i understood, let me
> know if i got this right.
>
> understood it correctly, i think the draft would benefit from dropping the
> concept of retransmitted packet. I mean, I dont think there is such a thing
> as a retransmitted packet. What quic retransmits is the data within packets
> that were detected as lost, but the packet is not retransmitted. For
> starters, the packet containing the retransmitted data has a different PSN.
> But also, the content of the packet may be different as some frames are not
> to be retransmitted.
>
>
Completely true that QUIC never retransmits packets, only data.  It would
be better to drop that wording.

> data with lower priority. I think such flexibility would be useful.
Completely agreed, though I'm not sure that needs to be specified in this
doc or left up to implementations?

> decouple the loss detection from the retransmission.
Yes, very much so.

> I understand that all data (control and application data) that is reliably
> transmitted is transmitted within a stream. Other data that is not
> transmitted within a given stream (like ACKs) is not reliably transmitted.
> Is this correct? If so, it may be worth stating it as a design principle,
> so people know that if they want to include control information such as
> other options to be reliably transmitted, they should do it within a stream.
>
>
It's correct that acks and stop waiting frames are not reliable frames and
hence are not retransmitted, but other frame types are retransmittable and
not be part of a stream(ie: PING frames).

> i.e. one for each stream plus one for the packets at the connection level.
> Let's call the packet one, the packet window and the other the stream n
> window. The packet window is in packets, while the stream windows are in
> bytes.
>
>
Yes.

> packet number n when all packets with packet number lower than n are marked
> as acked or as lost. In other words, the left side of the window is the
> non-acked packet with lowest packet number. This corresponds to the "least
> unacked" packet mentioned in the draft.
>
> non-acked, bytes awaiting for transmission. Bytes non-acked are bytes that
> are contained in packets on flight. Bytes awaiting for transmission are
> bytes that either have not been sent yet or bytes that have been sent in
> packets that have been determined as lost.
>
> Whenever a packet is acked, the bytes in each stream window corresponding
> to the data of each stream included in the acked packet are marked as acked.
>
> corresponding to the data of that stream included in the packet are marked
> as bytes awaiting for transmission.
>
> non-acked packet has an associated timer that when it times out, the packet
> is marked as lost. You can define any other mechanisms to detect packet
> loss only operating in this window, i believe.
>

Yes, the default mechanism actually uses FACK style packet number gaps, but
time is an option and the important thing is loss detection operates on
this connection-level packet window.

> windows, probably using the bytes awaiting for transmission with the lowest
> offset. This would include both the transmission of new data as well as
> retransmission of old data.
>
I think that captures the core ideas, yes.

---

From: marcelo bagnulo braun <[email-masked]>
Date: Fri, 7 Oct 2016 21:27:14 +0200

thanks for the reply
a few follow ups below...

El 07/10/16 a las 21:13, Ian Swett escribió:
>
>     Moreover, if eventually some form of priority is implemented, i
>     would guess that data with higher priority would be retransmitted
>     earlier than data with lower priority. I think such flexibility
>     would be useful.
>
>
>
>
> Completely agreed, though I'm not sure that needs to be specified in 
> this doc or left up to implementations?

mmm, probably you should allow the applications to express somehow the 
priority of the data so that quic can distribute them into the stream 
with the right priority , so i guess at least you would need to define 
this in the API, no?

>     reliably transmitted is transmitted within a stream. Other data
>     that is not transmitted within a given stream (like ACKs) is not
>     reliably transmitted. Is this correct? If so, it may be worth
>     stating it as a design principle, so people know that if they want
>     to include control information such as other options to be
>     reliably transmitted, they should do it within a stream.
>
>
> It's correct that acks and stop waiting frames are not reliable frames 
> and hence are not retransmitted, but other frame types are 
> retransmittable and not be part of a stream(ie: PING frames).
>

I fail to see the point of reliably transmitting pings. I mean, a ping 
is a test packet, if it fails, i guess this is the test output, no?
you may want to send anohter ping, is basically you want to do anohter 
test. There is no point in retransmitting the old one (conceptually, i mean)

In any case, I understand you are saying that there is some information 
that is not transmitted in streams that needs to be reliably 
transmitted, is that correct?
I wonder if this doenst creates a bit of a mess and wouldnt be cleaner 
to simply state that reliable transmission is only achieved in the 
streams and other frames transmitted outside a stream are non reliably 
transmitted. I dont really understand the implications of this design 
choice, but seems appealing because seems like a cleanner design choice.

>     So, if a sender has M ongoing streams, then it has M+1 sliding
>     windows, i.e. one for each stream plus one for the packets at the
>     connection level. Let's call the packet one, the packet window and
>     the other the stream n window. The packet window is in packets,
>     while the stream windows are in bytes.
>
>
> Yes.
>
>     The packet window has the following types of packets: packets
>     acked, non-acked packets and lost packets. The left side of the
>     window moves to packet number n when all packets with packet
>     number lower than n are marked as acked or as lost. In other
>     words, the left side of the window is the non-acked packet with
>     lowest packet number. This corresponds to the "least unacked"
>     packet mentioned in the draft.
>
>     Each stream window has the following types of bytes. bytes acked,
>     bytes non-acked, bytes awaiting for transmission. Bytes non-acked
>     are bytes that are contained in packets on flight. Bytes awaiting
>     for transmission are bytes that either have not been sent yet or
>     bytes that have been sent in packets that have been determined as
>     lost.
>
>     corresponding to the data of each stream included in the acked
>     packet are marked as acked.
>
>     Whenever a packet is determined as lost, the bytes in each stream
>     window corresponding to the data of that stream included in the
>     packet are marked as bytes awaiting for transmission.
>
>     Whenever a new packet is transmitted, the bytes in each stream
>     window included in the packet are marked as non-acked.
>
>     Packet loss detection only operates using the packet window. So,
>     each non-acked packet has an associated timer that when it times
>     out, the packet is marked as lost. You can define any other
>     mechanisms to detect packet loss only operating in this window, i
>     believe.
>
>
> Yes, the default mechanism actually uses FACK style packet number 
> gaps, but time is an option and the important thing is loss detection 
> operates on this connection-level packet window.

Talking about default mechanisms, have you consider using RACK as the 
default mechanism for quic?
It seems to me a very clean fit, since you already have per packet 
timers, no?

Regards, marcelo

>
>     Packet transmission otoh, needs to get data from the different
>     stream windows, probably using the bytes awaiting for transmission
>     with the lowest offset. This would include both the transmission
>     of new data as well as retransmission of old data.
>
>     Do you think this properly describes the framework of operation
>     for loss detection and retransmission of quic?
>
>

---

From: "Christian Huitema" <[email-masked]>
Date: Fri, 7 Oct 2016 13:23:59 -0700

> test. There is no point in retransmitting the old one (conceptually, i mean)

The way I see it, the ACK mechanism of QUIC performs loss detection. Conceptually, upon detecting a loss, the protocol engine examines the content of the lost packet. (There are multiple ways to do that in practice.) Then, based on what was lost, the protocol engine decides further actions. For example, stream data will be retransmitted most of the time, but not always -- e.g., not retransmitted if the stream was aborted. If a control packet is missing, the equivalent control may be transmitted again, but this time with updated value. An example would be a stream flow control packet, for which it is preferable to send the up-to-date information rather than resend the old value.

The case of the ping is particular. The engine sends a ping to check that the other end is alive. Arguably, it knows that if it receives an acknowledgement for the packet containing the ping frame, or for any later packet. Pings will thus only need to be retransmitted in some kind of "tail loss probe" scenario resulting in a timeout. The ping frame is actually a great way to implement the tail loss probe algorithm.

By the way, we are bound to see implementations that don't bother with these subtleties and just retransmit the entire contents of the lost packets. We should verify that this suboptimal behavior does not cause a protocol error, e.g. if two consecutive flow control frames slightly differ...

-- Christian Huitema