15
\$\begingroup\$

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.

\$\endgroup\$
  • 11
    \$\begingroup\$ Perhaps you are missing an idea of "timeouts" and "retries". \$\endgroup\$ – Kromster Jun 15 '17 at 4:44
  • \$\begingroup\$ I might be, sure. You're suggesting my logic is correct and, not to sound too negative, but while network programming, I can assume no guarantees on virtually any piece of networked information? During the course of a real-time game, that's a ton of potentially dropped information, which is fine, but I just want to make sure I understand the issue. \$\endgroup\$ – Grimelios Jun 15 '17 at 4:55
  • 10
    \$\begingroup\$ No guarantees at all. Right. Don't ever include "hope" in your algorithms. They must handle ANY unlucky combinations. P.S. We simply switched to TCP in our RTS, where eberything is taken care of, since we need reliable communication (for lockstep simulation). \$\endgroup\$ – Kromster Jun 15 '17 at 5:14
  • 5
    \$\begingroup\$ Use TCP when reliability is needed, use UDP when it doesn't matter. For example, the coordinates of the player are sent in my game via UDP. I use interpolation & smoothing to smoothe out any missing packets. works like a charm. things that really need to be reliable but can be a bit slower are sent via TCP. If you have state wehere newer state invalidates old state, UDP is a good choice becuase it doesn't matter when something in between was dropped 8e.g. player position). \$\endgroup\$ – Polygnome Jun 15 '17 at 9:27
  • \$\begingroup\$ This isn't a direct answer to your question, but I strongly recommend only requiring an acknowledge in a real time game when they are absolutely necessary (e.g., on initial connection). It is far simpler (and robust) to design both the client and the server so that they "work with what they have" until they get a new packet in a stateless system if you can. Quake 3 did this incredibly well with a snapshot-based system. Also libraries like Enet can send only certain packets reliably, for those cases when you really need it \$\endgroup\$ – jrh Jun 15 '17 at 18:03
32
\$\begingroup\$

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. ;)

Rafiki laying down some reductio ad absurdum on that life philosophy

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.

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ +1, well written. I would just highlight, that this is more relevant to action / real-time games. TBS and RTS games (and some action game's events) have a different view on "time horizon beyond which the information doesn't really matter". \$\endgroup\$ – Kromster Jun 15 '17 at 5:27
  • 3
    \$\begingroup\$ Yeah, for a turn-based game, I'd imagine one would use TCP rather than try to roll one's own reliability layer on top of UDP. ;) I'd still class the micro in an RTS as the type of gameplay with an exacting time horizon though - that hybrid approach may do well there, where you have both low-latency updates for the heat of the moment as well as a safety net to retroactively handle critical missed events like resource spending. \$\endgroup\$ – DMGregory Jun 15 '17 at 5:32
  • \$\begingroup\$ That's extremely helpful and kind of validates my initial concern. Thank you very much. \$\endgroup\$ – Grimelios Jun 15 '17 at 7:04
  • 2
    \$\begingroup\$ It might also be useful to mention Forward Error Correction. Design your protocol such that the receiver can independently figure out that a packet was dropped when the next packet is received, adding some extra data to smooth out the required interpolation. This can be useful because often the UDP packets aren't full anyway, and you just send smaller packets more often to keep the latency down. Adding some extra bytes won't hurt the latency, and bandwidth is not an issue in these cases. \$\endgroup\$ – MSalters Jun 15 '17 at 11:11
  • \$\begingroup\$ @MSalters I'd say that's worth elaborating on in its own answer, if you're up for it. I'd upvote that. :) \$\endgroup\$ – DMGregory Jun 15 '17 at 11:25
9
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ An essential feature of TCP is that the sender doesn't need to care about whether any particular packet got acknowledged, but mostly needs to care about the "high water mark" and how long packets have been outstanding without the high-water mark moving. \$\endgroup\$ – supercat Jun 15 '17 at 19:09
  • 1
    \$\begingroup\$ @supercat I wouldn't say that's essential; more like an optimization. \$\endgroup\$ – immibis Jun 15 '17 at 21:25
  • \$\begingroup\$ Regarding the thing in parenthesis (sending ACK for packets you already got), I think you should actually emphasise it instead of parenthesising it. It seems to be missing from the OP's understanding (or at least its description). \$\endgroup\$ – Angew Jun 16 '17 at 7:51
  • \$\begingroup\$ @Angew done now. \$\endgroup\$ – immibis Jun 16 '17 at 8:07
6
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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)

\$\endgroup\$
  • \$\begingroup\$ Warcraft 3 uses TCP. \$\endgroup\$ – fsp Jun 17 '17 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.