Implementing Network Coding

[scopedog]

I'm currently implementing Network Coding to MsQuic which is supposed to drastically reduce packet retransmissions in packet loss.
See "Network Coding Meets TCP" https://ieeexplore.ieee.org/document/5061931 or search with Random Network Coding for more details.

However, I'm struggling with how to handle lost packets around QuicConnRecvDatagramBatch() in core/connection.c.
What I want to do:
Even if there was a lost packet, the receiver should not exclude it from next ACK. For example, suppose packet 101 and 103 were received but 102 was lost. In a certain condition, the lost packet can be ignored and the receiver sends ACK with the largest packet 103 and the first ACK range with non 0 (maybe 10, 20....).

What I did:
For the lost packet, I used QuicAckTrackerAddPacketNumber() and QuicAckTrackerAckPacket() (or QuicRangeAddValue(&Tracker->PacketNumbersToAck, LostPacketNumber)) so that it is not treated as lost in the next ACK. However, it causes disconnection between server and client. I also created dummy Packet to do other things but the things don't seem that simple.

I tried so many other things and don't remember everything I did but what else should I do to handle the lost packet correctly?
Once I publish my research paper, I'll put my source code at github.

Thank you.

[nibanks]

Hi @scopedog, I don't really understand what you're trying to do.

I'm struggling with how to handle lost packets around QuicConnRecvDatagramBatch()

QuicAckTrackerAckPacket is where a received packet is marked for acknowledgement. Later, on the send path, QuicAckTrackerAckFrameEncode is called to build up the ACK frames. Loss detection is driven by a combination of QuicLossDetectionProcessTimerOperation and QuicLossDetectionProcessAckBlocks.

Even if there was a lost packet, the receiver should not exclude it from next ACK.

If I understand correctly, you're saying that you would ACK a packet you did not receive? This would be very bad. Best case, the peer would never retransmit the data in that lost packet; worst case, the peer might have skipped the packet number on purpose and would treat an ACK of a non-existent packet as a fatal error for the connection.

[scopedog]

Thank you for your response.

If I understand correctly, you're saying that you would ACK a packet you did not receive?

Yes but that is OK with network coding.
Here is how NC works:
Suppose the sender wants to send N packets, then it creates N + 1 network coded packets and sends them. The receiver can restore the original data if it receives N (out of N + 1) packets.
For example, if the sender wants to send 4 packets, it encodes those packets and creates 5 new network coded packets, then it sends the 5 packets. If the receiver receives 4 out of 5 packets, it can decode the packets and can obtain the original 4 packets. Therefore, even if there's a lost packet, the receiver can restore the original data.

I currently emulate the packet loss with Linux's tc command but it seems better to do inside MsQuic... As you mentioned, treating a lost packet as if it were received looks very troublesome to MsQuic. I'll change my programs.

I appreciate your comment.

[nibanks]

Is this essentially FEC? It sounds like it based on your description. If so, I'd recommend a slightly different approach perhaps.

Explicitly acknowledging a packet you never received is likely not going to work. So I don't recommend you change the ACK path. Instead, make the sender smarter to realize that if 4 of the 5 packets were acknowledged, then there is no reason to retransmit the data in the 5th packet.

This is similar to the scenario where you send some data in packet N, then later (because you thought N was lost) resend the data in packet N+1; but then packet N gets ACKed. If packet N+1 ends up actually getting lost, you don't actually need to retransmit it because the data has already been acknowledged in packet N.

[scopedog]

Thank you.

In the current scenario, NC works like FEC but is a little different (there may be error correction based on NC though).

Instead, make the sender smarter to realize that if 4 of the 5 packets were acknowledged, then there is no reason to retransmit the data in the 5th packet.

That sounds much better. I'll try it also.

Regards,

[sebastian-peters]

Hi all,
I might add that ACK of packets that are not received could also be detected as an Optimistic ACK attack - if that part of the QUIC RFC 9000 is implemented at some point.
"An endpoint that acknowledges packets it has not received might cause a congestion controller to permit sending at rates beyond what the network supports. An endpoint MAY skip packet numbers when sending packets to detect this behavior."

Optimistic ACK Attack