Thursday, January 24, 2013

UDP message dependency graph

Many multiplayer games with realtime requirements, such as first person shooters, use UDP for networking (huh, it just dawned on me that saying "UDP protocol" is like saying "ATM machine"). The advantage of using UDP rather than TCP is that if a packet is lost, the connection doesn't have to wait until that packet is recovered before processing newer packets. Of course, the downside is the fact that you acutally have to deal with lost packets (and that you don't even have a connection).

Glenn Fiedler has a great series of articles called Networking for Game Programmers which talks about TCP and UDP in more detail, and then goes on to describe how to implement a virtual connection on top of UDP and how to deal with packet loss. I won't go into detail here, as I've linked the articles, but in summary the implementation works by having the side receiving a packet send an ACK (acknowledgement) back to the sender to alert them that the packet has been received. This way, when sending a packet, you can know for sure when it gets through, and if an ACK is missed, you can decide how to proceed (whether or not to resend data). In this post I'm going to talk about my approach to making this decision.

In my project, "DR", packets are made up of a series of messages. Each message represents a command like "spawn object of type ENEMY at (x,y,z)" or "update object with ID 5 to position (x,y,z)". Some of these messages are important - if a packet with a "spawn enemy" message is dropped, you definitely want to resend that packet, since if you don't, the player would have an invisible enemy draining its health, and that wouldn't be very fun. Well, maybe it would be, but it's certainly not the intent. Other messages, like the "update object" message, aren't as important - if a packet with an "update object" message is dropped, the player might see a a very brief moment of lag (or maybe not even that, if extrapolation/prediction is used), but another "update object" message would be sent immediately after, and the mistake would quickly be fixed.

The first choice I made was to have two message types: guaranteed messages and non-guaranteed messages. When sending guaranteed messages, the content of the message is copied in a buffer, and once the ACK for the packet containing that message is received, the message is removed from the buffer. However, if the ACK for that packet is missed, the message is automatically sent along with the next packet. This process keeps occurring until an ACK for a packet containing that message is received. For non-guaranteed messages, none of this happens - you just send out the message and forget about it.

So that solves the issue of guaranteed messages. But there's another issue with UDP: packets don't necessarily arrive in order. I made the decision to simply drop packets which are older that the most recently received packet, but messages can still arrive out of order. For example, consider the following sequence of events:

Server sends packet 1 containing message A

Server sends packet 2 containing message B

Client receives packet 2 (packet 1 was lost) containing message B and sends back an ACK

Server realizes packet 1 was lost and resends message A in packet 3

Client receives packet 3 containing message A

The server sent A, then B, but the client received B, then A. This could cause some bad situations. For example, suppose message A contains "spawn ENEMY with ID 1", and message B contains "kill ENEMY with ID 1". Those messages need to be correctly ordered. A common solution is to implement a small part of TCP to allow for ordered messages. Each guaranteed message has a sequence number which is incremented, and a message with sequence number N is only executed once all messages with sequence numbers from 0 to N-1 have been executed. So when an out-of-order message is received, it is stored and then recalled to be executed once the messages that should come before it are received.

Of course, implementing TCP on top of UDP brings the same problems that we wanted to avoid with TCP! Messages can get delayed if other messages are dropped. For example, suppose you want chat messages to be guaranteed, as well as "spawn enemy" messages. If a player says something over chat and that packet is dropped, no "spawn enemy" messages can get through until the chat message is recovered. This contraint is obviously pointless and undesirable. One way to fix this is to have several guaranteed message "channels", such as one for critical game events and one for chat messages. Each channel would have its own sequence number counter, so messages from the "chat" channel wouldn't delay messages from the "critical game events" channel. This is better, but still not ideal. If you're spawning 10 enemies and the message to spawn the first enemy gets dropped, it would be nice if the other 9 weren't held up.

I was thinking about this when I came to the realization that message ordering "channels" are simply a special case of a more general data structure - a directed acyclic graph. In the message channel model, each message has a single dependency: the message that came directly before it. (Terminology: if B depends on A, then B is a successor of A and A is a predecessor of B). If you had 3 different message channels, the graph representation would look like 3 separate chains of nodes. If you remove the channel restriction and just allow for arbitrary dependencies (without cycles of course), all the issues I talked about above are solved. For example, a chat message would have a single dependency to the previous chat message, a "spawn enemy" message would have no dependencies, and a "kill enemy" message would have a single dependency to its corresponding "spawn enemy" message. Another example: suppose you have the server send info about each of the N players to each player, and then a "start game" message. The "start game" message could have N dependencies on the N "player info" messages. This way, the game wouldn't start until all player info was received.

I'm going to end this post, as it's getting late, but next I'll talk about my implementation of the UDP message dependency graph.

No comments:

Post a Comment