UDP from MOG Perspective

	Author:	“No Bugs” Hare  Follow:
	Job Title:	Sarcastic Architect
	Hobbies:	Thinking Aloud, Arguing with Managers, Annoying HRs, Calling a Spade a Spade, Keeping Tongue in Cheek

To navigate through the book, you may want to use Development&Deployment of MOG: Table of Contents.]]

[[Also note that Chapter XI(a) has been skipped from publishing on the site; it is too much similar to a recent post of mine Once again on TCP vs UDP, and you can get most of the related discussion there]]

As it was mentioned above, UDP is all about datagrams¹, and UDP datagram sits right on top of IP packet. Typical UDP datagram has the following structure:

More importantly, for UDP there is one-to-one correspondence of UDP datagrams with IP packets.

“you may think of UDP as of an analog of good old C: you can do pretty much everything, but it is not because the language helps you – it is rather because it doesn’t stand in the way 🙂It means that working with UDP is logically very much the same as working with IP directly. In other words, you have full control but need to do everything yourself. With UDP, you don’t have any built-in reliability (though you can implement it yourself), no flow control (though you can implement it yourself), and so on, and so forth. Just to give you some feeling about “how on-your-own you are with UDP”: for UDP, even checksum is optional.²

If making parallels with programming languages, you may think of UDP as of an analog of good old C: you can do pretty much everything, but it is not because the language helps you – it is rather because it doesn’t stand in the way 🙂 .

On UDP payload size

With UDP (unlike TCP) you do have control over the datagrams/packets which you’re sending. On the flip side of it, you DO need to care about maximum datagram size. For answering the question “what maximum size of UDP datagram is acceptable for the public Internet”, there are several different schools of thought.

Conservative school.

MTU maximum transmission unit (MTU) of a communications protocol of a layer is the size (in bytes or octets) of the largest protocol data unit that the layer can pass onwards— Wikipedia —Conservative school of thought with regards to UDP datagram size says that we need to fit the whole packet into 576 bytes (which is often considered minimum practical MTU for the Internet³), which effectively means that we should limit UDP payload to 512 bytes or so (number 548=576-20-8 is a bit too optimistic due to IPv4 header options).

Moderate school.

Moderate school says that we should limit ourselves to UDP payload sizes of around 1400-something. This is based on a very practical observation that a typical Ethernet MTU is 1500; then, allowing for various encapsulations (such as those in PPPoE etc.) and header sizes, we’ll have around 1400 bytes left for our UDP payload.

Close results will be obtained if we take IPv6 minimum MTU of 1280 bytes as a baseline (which will lead us to around-1200 bytes for our UDP payload).

Optimistic school.

Optimistic school says “hey, we have a standard which says that we can have UDP payload up to 65467 bytes” (65467=65535-(60+8)). And this is technically true, and the sky probably won’t fall. However, we need to keep in mind that such large datagrams are almost guaranteed to be fragmented, which (combined with a fact that even if one single fragment is lost, the whole datagram is lost) – it leads to increased datagram loss rate 🙁 .

Also, if we’re using UDP for our network-tick packets, then we need to keep in mind that sending 60K bytes payload 20 times per second would lead to a traffic of 60000*8*20 bit/s/player = 10MBit/s/player, which is usually WAY too much for an MOG.

Theoretically Correct School.

“Theoretically correct school of thought says that we should try to perform so-called PMTUD, to find out minimum MTU on the path from Server to ClientTheoretically correct school of thought (coming from multiple RFCs) says that we should try to perform so-called “Path MTU Discovery” (a.k.a. PMTUD), to find out minimum MTU on the path from Server to Client, and to optimise our packet size based on it. However, for fast-paced games I would usually advise against doing it.

The idea of PMTU in a nutshell looks as follows.⁴ At some point, we’re sending a packet with a so-called DF=Don’t Fragment IP bit. If this packet doesn’t fit into next MTU, the router in question will drop the packet, sending a special ICMP packet (with type=3, code=4) back to the sender. So, the sender can learn whether the last packet sent is larger or smaller than minimum MTU along the path (so-called “path MTU”). If the sender has learned that the packet does fit MTU – it usually increases size-of-packets-it-sends, if it learns that the packet doesn’t fit MTU – it can either use last-packet-size-which-has-fit as a future MTU, or attempt to find MTU more precisely.

For last 15+ years, PMTUD is routinely performed for TCP connections (and works pretty well for last 10+ years), and usually, the rationale for doing PMTUD is that as every packet is small, and has a significant overhead, so when we’re transferring large files, we will save quite a bit of bandwidth if we’re using MTU of 1500 bytes over those “guaranteed” 576 bytes (for TCP, the gain from changing MTU from 576 bytes to 1500 bytes is around 6-7%).

“Most of the game packets are usually pretty small, and division between packets is rarely driven by MTU (but is usually driven by timing restrictions).However, for games, this logic doesn’t usually apply. Most of the game packets are usually pretty small, and division between packets is rarely driven by MTU (but is usually driven by timing restrictions). Under these conditions, personally I usually feel that PMTUD is not really necessary. Moreover, PMTUD can even be mildly detrimental for some players at least in two distinct scenarios:

• for those players sitting behind broken firewalls which drop ICMP packets. While this was quite a problem 15+ years ago, these days it is quite uncommon.
• for those players whose path has changed in the middle of connection (in particular, it happens rather frequently for mobile devices). While a fairly common scenario, it rarely causes Big Problems though.

Neither of these two issues is really Big Enough in practice (that is, if you have TCP fallback), but they do serve as an argument against PMTUD (and as there aren’t too many really compelling pro-PMTUD arguments in MOG context, it usually becomes a kind of a stalemate).

My Personal Take

My personal take on the question of “how big UDP datagram to use” depends on quite a few specifics, but in some “average case” it is usually along the following lines:

• be moderate and go for 1200-1400 UDP payload
• have TCP fallback as a “last resort” even if you think that your game is only “barely playable” over TCP
• as for PMTUD – you MAY want to try it for “slow-paced updates” (see definition below) if your “Reliable UDP” library supports it. However, YMMV, and often you may be better without PMTUD, so if your library doesn’t support PMTUD – I would certainly be perfectly ok with it.

On UDP broadcast/multicast – Don’t Hold Your Breath

“Indeed, it would be Really Great to send each update only once... However, don’t hold your breath over it.UDP as such is known for supporting broadcast and multicast, which MIGHT look as “just the ticket” for your game. Indeed, it would be Really Great to send each update only once, and let the Internet infrastructure populate the packet to all the hundreds of thousands of your players. However, don’t hold your breath over it.

First of all, let’s note that as UDP sits right on top of IP, to implement broadcast or multicast, it relies on IP broadcast/multicast. Now let’s look at these two beasts.

IP broadcasts works only within LAN (and is very popular for LAN-based P2P-architecture games for peer discovery). IP broadcast doesn’t work beyond so-called “broadcast domain”, which is usually limited to a single LAN or “subnet”. Broadcast never works over the Internet (and neither over Intranets). In IPv6, broadcast was abolished entirely (and effectively replaced with a special type of multicast).

IP multicast is a much more interesting beast, and your admins MAY make it working over the global Intranet with millions of users. However, while it is a standard, and you can find a lot of information how beautifully the standard is designed (which it is) and how multicast is supposed to work, there is much less obvious and much less-known among developers fact:

Information about IP multicast being de-facto unroutable over the public Internet is scarce, and the best reference I was able to find about it, is a discussion on [ServerFault]. However, I assure you that at the very least for IPv4, it is a fact of life 🙁 .

“As most of the routers (including pretty much every backbone router out there) are not configured to support multicast, it makes multicast over the public Internet hopelessThe story goes as follows. First of all, to have multicast working, you need all the routers between your server and all of your clients to support multicast. And as most of the ISPs (including pretty much every backbone ISPs out there) are not doing it, it makes multicast over the public Internet hopeless 🙁 .⁵

A bit of side discussion: traditionally, for IPv4 multicast, there were two Big Problems preventing backbone ISPs from enabling it. The first Big Problem for supporting IP multicast over the public Internet was about multicast address allocation: with only about 64M multicast addresses available in IPv4, any schema of allocating them (except as on case-by-case basis by IANA as in “let’s use 224.0.1.1 for NTP”) will lead to a quick exhaustion of the multicast address space. With IPv6 and its unicast-prefix-based multicast addresses, it seems that this first problem has been addressed; however, there is still another Huge Obstacle. The second Big Problem for supporting IP multicast over the public Internet is that with unicast-prefix-based multicast addresses, everybody and his dog will be able to create multicast groups, and all these groups will need to be supported by backbone routers at least to a certain extent. As backbone routers are already loaded to the brim, asking them to store uncontrollable number of mappings between multicast IP addresses and their respective destinations is probably too much 🙁 :-(. As a result, my rather-poorly-educated guess is that the transition to IPv6 is not likely to enable multicast over public Internet; however, I would be happy to be wrong (as noted above, for many things out there, multicast would be a Wonderful Thing™).

Still, at least at the moment, the bottom line about UDP multicast and broadcast goes as follows:

UDP: Addressing Lack of Reliability

One thing to remember about when working with UDP, is that UDP is NOT a reliable protocol in any sense. Each and every packet on the Internet can be lost. And as UDP datagram is only an extremely thin layer on top of IP packet – each and every UDP datagram can be lost too 🙁 . This is not fatal (after all, “reliable” TCP is built on top of unreliable IP packets), but it does mean lots of additional work on top of UDP.⁶

In game context, approaches to ensuring reliability over UDP tend to depend significantly on the nature of the communication. As it was noted in Chapter VII, for Server-to-Server communications we’re likely to use TCP anyway, which leaves UDP to communications between Client and Server, and these communications are further divided into (a) publishing of the World State, and (b) point-to-point communications between Client and Server.

Publishing World States over UDP

First, let’s consider publishing of your world state to all your clients. As it was noted in Chapter III, you DO need to spend quite a bit of time to split your World State into Client-Side State, Server State, and Publishable State (with the following inequation usually standing: size-of(Client-Side State) << size-of(Server-Side State) << size-of(Publishable State)).

“we’ll assume not only that you’re not going to transfer all those mesh triangles over the network, but also that you’ve implemented your Interest Management and worked on optimizing your Publishable StateFor the purposes of this Chapter, we’ll assume that you’ve already done your homework in this regard, splitting and optimizing your Game World States. In other words, we’ll assume not only that you’re not going to transfer all those mesh triangles over the network, but also that you’ve implemented your Interest Management and worked on optimizing your Publishable State (including, but not limited to, switching to fixed-point in-transit representations where applicable). All these traffic optimizations mentioned in Chapter III, with the notable exclusion of Compression, can (and generally SHOULD) be done in exactly the same manner regardless of you using UDP or TCP (this will also help to have that fallback to TCP, which we’ve spoken about above).

Fast-paced Updates vs Slow-Paced Ones

Now let’s take even a closer look to these World State updates. In different games, there are different types of updates; sometimes they even co-exist within one single game.

The first type of updates is about things-which-change-on-every-network-tick; coordinates of your characters is one good example of such fast-paced updates. The second type of updates is all about things-which-change-much-more-rarely-than-that; one nice illustration of these things is player chat (and a bit worse example is an inventory of the chest which is about to be inspected). Of course, the division line is not that clear (what about health of your character? Does it qualify as a fast-paced change or as a slow-paced one?),⁷ but (as it was noted in Chapter III) generally I find it useful to make such a split, designating each of the parts of the Publishable State into one of these two categories.

Fast-paced Updates: Compression without built-in reliability

[[TODO: remove from Chapter XI (it has been moved to Chapter III)]]

When speaking about those fast-paced updates (like coordinates), the picture is usually rather obvious. We have all those updates to coordinates etc. calculated by the Server-Side at each network tick, and we need to deliver them to the Client-Side. And of course, we want to use all those Compression techniques (including Delta Compression – both whole-field and numerical flavours, and of course, Dead Reckoning) – as described in Chapter III.

Now let’s see how these Compression techniques will interplay with the inherently unreliable nature of UDP.

“it may easily happen that previous packet is not available to the Client when our current packet arrivesAs UDP does not guarantee us delivery of each and every packet, it may easily happen that previous packet is not available to the Client when our current packet arrives; as a result, we cannot use any kind of reference to the previous packet when using UDP. Bummer. On this basis, it might seem that we’re not able to use both Delta Compression and Dead Reckoning (which would increase traffic enormously). However, in reality it is not that bad.

The most popular way of dealing with this kind of things is the following. First of all, we note that in addition to the packets coming from Server to Client (the ones which bring World State data) there are also packets coming in the opposite direction – coming from Client to Server (normally containing inputs). Second, let’s say that each of the packets coming from Server to Client, contains the number of the “network tick” which it corresponds to (we need this pretty much anyway for other reasons too). Third, let’s say that each packet coming from Client to Server, also contains a number of last-network-tick-received-by-this-Client (!).

As soon as we have all these things in place, our Server happens to “know” that such and such Client already has network-tick #X. Then (assuming that Server keeps a few last states)⁸ Server can issue the next packet #Y, effectively saying that “this is packet #Y, WHICH IS BASED ON PACKET #X, and using all the Delta Compression and Dead Reckoning COMPARED TO THAT PACKET #X”. As we know for sure that Client already has that exact PACKET #X – we can be reasonably sure that on receiving this PACKET #Y it will be able to reconstruct the whole Publishable Game World State correctly.

Fig XI.1 shows one possible interaction between Server and Client while using the algorithm described above.

One note: the approach described above means that PACKET #Y can be easily different for different Clients (in extreme case – it can be different for each Client). However, as we’re bound to use unicast anyway, this doesn’t cause too much problems in reality.

Another note is that with this algorithm, we do NOT guarantee delivery of each-and-every packet (and that’s a Good Thing™, as otherwise we’d waste lots of time and bandwidth). Instead, what we’re doing is guaranteeing data synchronization even when some packets are lost.

Slow-Paced Updates: State Sync

As noted in Chapter III, slow-paced updates to the Publishable Game World State usually have three significant differences from fast-paced ones:

• They’re slow
• They MAY be large
• They MAY contain non-numerical stuff (mostly strings, but MAY contain even images etc.)

“In any case, for slow-paced updates I suggest to use a reliable stream, with differential updates on top of itWhether you Really Need to implement full-scale sync of abstract data trees – or just need to deal with chat-as-a-part-of-Publishable-State (which is MUCH simpler),⁹ it depends on specifics of your game. In any case, for slow-paced updates I suggest to use a reliable stream, with differential updates on top of it (usually sent only when the change happens, and NOT on every network tick); whether you want to add a differential sync algorithm along the lines described in Chapter III (or just to resend the whole state in case of resync) – it heavily depends on your specific needs.

From UDP perspective, it means that we can use pretty much the same reliable stream which we’d use for Point-to-Point Client-to-Server communications (described right below in “Point-to-Point Communications over UDP” section).