Combatting UDP packet loss through data redundancy

Quote:

Original post by clb But somehow, this whole idea of adding redundancy seems, well, redundant and wasteful. As a result, in my mind I've started to think of more sophisticated schemes of adaptively controlling the amount of redundancy, but I'm not sure if I'd even want to go there. So, I'm asking what do you think? Are you aware of any other sources that discuss this topic? Can you think if there's a "clearly superior" alternative to this? Do you think this is a simple hack, or a viable method?

It's a very well researched topic. See related topics as well.

But, I once did some napkin-math. I came to the conclusion that as long as you're not sending data to the moon with multiple second round trip time, explicit request for resend will recover data faster.

The alternative would be to add so much redundancy that bandwidth becomes a problem (unlike optical drive error correction), and still fails to model many loss characteristics.

It is a nice idea in theory, but after examining its applicability in practice, it simply doesn't offer any advantage (signal/loss ratio, bandwidth, jitter, RTT, ...) over simple ack/nack retransmit scheme.

One of biggest problems with redundancy approach is that most schemes work for errors on bit-level, but in networking this type of errors are rare and well handled already - instead one needs to deal with packet loss, or thousands of bits. This makes such schemes unviable compared to retransmit.

Quote:

Original post by Antheus The alternative would be to add so much redundancy that bandwidth becomes a problem (unlike optical drive error correction), and still fails to model many loss characteristics. It is a nice idea in theory, but after examining its applicability in practice, it simply doesn't offer any advantage (signal/loss ratio, bandwidth, jitter, RTT, ...) over simple ack/nack retransmit scheme.

Wouldn't that depend on the game in question? It certainly seems like an easy optimization to make for improving any game where bandwidth is plentiful and latency critical.
Say if I wanted to add networking to a NES emulator for instance, e.g. for playing old two-player classics across the net, then piggybacking a few frames of old input on top of the latest packet seems like a no-brainer.

Quote:

Original post by implicit Wouldn't that depend on the game in question? It certainly seems like an easy optimization to make for improving any game where bandwidth is plentiful and latency critical. Say if I wanted to add networking to a NES emulator for instance, e.g. for playing old two-player classics across the net, then piggybacking a few frames of old input on top of the latest packet seems like a no-brainer.

If your state is very small, and you can always send last n states, then yes.

I was looking into a more general solution.

Typically, one will not have the luxury of sending fixed size payloads. This complicates error correction since the stream being sent needs to be split into blocks. Depending on the size, blocks will be smaller or larger than a single packet.

On extreme end, single byte would be sent with each packet. This scheme would be trivially recoverable, but with prohibitive overhead.

Typically, there would be multiple blocks packed into single UDP packet. But since packet loss occurs for each packet individually, losing just a single UDP packet would lose multiple consecutive redundancy blocks.

While using convolution codes such consecutive loss can be compensated, it adds latency to recovery. Or - if m consecutive blocks are lost (as will be the general case with each lost UDP packet), f(m) additional blocks are needed. To minimize latency, block size can be increased to include more redundancy, or redundancy can be spread over longer sequence of blocks.

Size increase is not viable, since f(m) grows fast. Spreading redundancy over time is viable, but the added latency (it becomes necessary to receive f(m) additional blocks after m lost blocks) means that it would take more time to reconstruct lost blocks than it would to just request retransmit (one RTT, or time to receive two redundant packets).


Redundancy has limited application to recovery of single lost packets, or where state is small enough to send history of last n states. In most other realistic cases it isn't, at least not if low latency is required, as the number of additional packets before recovery grows. For reliable transfers without regard to latency, redundancy would work, but it is unlikely that redundancy would outweigh explicit retransmits. Just 1/8 redundancy means that under 12% packet loss, retransmits will likely require less total data to be transmitted.

It also doesn't address accompanying issues, such as packet loss causing jitter and stalls.

Also, regardless of redundancy, all schemes have upper bound on number of errors they can correct, and those limits become problematic after one considers MTU, meaning that redundancy needs to be spread over time, which defeats the purpose of low latency scheme.

Note that you can often get great compression out of including previous states or inputs in a packet. If you are input synchronous, and forward "key presses" as a bit mask, then many packets in a row will have the same value, and thus you can use RLE encoding of those. Sending the last 30 states that way costs no more than sending the last 1 state, except when the user changes whether a key is up or down, at which point it costs one additional state's worth. (If you use something like 16 bits for game controller input, that's still pretty tiny -- two shorts instead of one).