Acknowledgement reliability using UDP

Question

I have a question about UDP. For context, I'm working on a real-time action game.

I've read quite a bit about the differences between UDP and TCP and I feel I understand them quite well, but there's one piece that has never felt correct, and that's reliability, and specifically acknowledgements. I understand that UDP offers no reliability by default (i.e. packets can be dropped or arrive out of order). When some reliability is required, the solution I've seen (which makes sense conceptually) is to use acknowledgements (i.e. the server sends a packet to the client, and when the client receives that message, it sends back an acknowledgement to the server).

What happens when the acknowledgement is dropped?

In the example above (one server sending a packet to one client), the server handles potential packet loss by re-sending packets every frame until acknowledgements are received for those packets. You could still run into issues of bandwidth or out-of-order messages, but purely from a packet-loss perspective, the server is covered.

However, if the client sends an acknowledgement that never arrives, the server would have no choice but to eventually stop sending that message, which could break the game if the information contained in that packet was required. You could take a similar approach to the server (i.e. keep sending acknowledgements until you receive an ack for the ack?), but that approach would have you looping back and forth forever (since you'd need an ack for the ack for the ack and so on).

I feel my basic logic is correct here, which leaves me with two options.

1. Send a single acknowledgment packet and hope for the best.
2. Send a handful of acknowledgment packets (maybe 3-4) and hope for the best, assuming that not all of them will be dropped.

Is there an answer to this problem? Am I fundamentally misunderstanding something? Is there some guarantee of using UDP I'm not aware of? I feel hesitant to move forward with too much networking code until I feel comfortable that my logic is sound.

Answer 1

This is a form of the Two Generals Problem, and you're right - no number of retries is enough to perfectly guarantee receipt.

In practice in games, there's usually a time horizon beyond which the information doesn't really matter though even if it technically arrives reliably. Like finding out you had a perfect headshot lined up 2 seconds ago - it's too late for the player to use that information now.

If your packet loss is so high that you can't routinely get the needed info through inside a tight reaction window, then for a realtime game you might be better off kicking the player and trying to find a better match for them elsewhere, rather than continue trying to send the packet to emulate a reliable connection.

Because of this, some game replication systems skip acknowledgement & retries altogether and opt to just spam the newest update as often as they can. If one gets dropped or arrives late, too bad, skip it, pick up the next one and carry on, relying on the prediction & interpolation systems to smooth the gap and minimize hiccups visible to the player.

I suddenly want to start calling this "Simba Replication" for how it disregards problems in the past and tries to live in the present moment. ;)

A hybrid solution is to race ahead sending the new update AND (since game state updates can often be quite small / compressible) also pack-in the last update, and maybe the one before that... So just in case the client missed them, you don't have to wait a full round trip time to find out and fix it. Most of the time the client already saw this, so there's redundant data this way, but the latency for correcting a missed message is lower. The client's updates can include the index number of the most recent consecutive update they've seen, so you can be minimally conservative with how many old updates you include in the next update packet. Glenn Fiedler explains this strategy in more detail in this Gaffer On Games article.

You could also implement a two-tier system as another type of hybrid, where short-lived state is replicated in an unreliable rapid-fire manner, and long-term state is synchronized reliably, using TCP or your own reliability implementation with a high retry count. This gets more complex to manage though, because you have two messaging systems to maintain, and the two snapshots can be out of sync with one another, adding a whole new class of edge case.

Answer 2

The approach TCP uses is that the sender will keep resending the packet until it receives an acknowledgement. The receiver will ignore duplicate packets, but still send acknowledgements for them. The sender will ignore duplicate acknowledgements.

If a packet gets lost, the sender resends it, as you already know.
If an acknowledgement gets lost, the sender resends the original packet, which causes the receiver to resend the acknowledgement.

If an acknowledgement is not received within a certain time (perhaps 60 seconds, or 20 retries) then the player is considered to be disconnected from the game. You must implement some kind of timeout rule, or otherwise a player who unplugs their network cable will tie up resources on your server forever.

Answer 3

If you want to reinvent TCP, it makes sense to look at TCP first, which deals with the exact problem you describe (part of the solution is to use user defined values for retry attempts and timeouts).

Solutions that use 2 channels, a TCP channel (for reliable communication) as well as a UDP (for low latency communication) channel are not uncommon.

Some solutions detect when a client is missing some information for too long, and start a resynchronization, which may use UDP or TCP.

Another common approach is to design communication such that it doesn't rely on acknowledgements at all, but that's outside the scope of the question.

Answer 4

In an RTS you really cannot use a protocol like TCP, and you cannot make UDP reliable either. If you try to, the game will freeze whenever a there is a network hick-up.

Instead, you design the protocol so that missed packets don't matter too much.

The short version is that you don't care where the other players were last frame as long as you know where they are now. The long version is more complicated.

The question then becomes, what do you do when a packet goes missing? And the answer is... you guess. The player is probably moving in a straight line, right? Just move them one step further along that line. ... Except no RTS player ever moves in a straight line. And then there is collision detection.

This is hard. Many games get it wrong. It can be argued that there is no right answer to this, only various wrongs that can be traded off.

The reason these games work pretty well is not only that they have thought long and hard about these problems, but also that the Internet has become pretty reliable. Almost all UDP packets actually reach their destination in a timely manner. (Unless there is a permanent problem like a firewall)