# How to correctly aggregate networked data into UDP packets while avoiding fragmentation

I am starting to get my feet wet with game networking, having iterated many times now on some simple 2D games. For learning purposes, I've read the fantastic Gaffer on Games networking article a couple of times, the Source networking article, and the Quake sourcecode review about networking. I'm feeling comfortable with the concepts discussed there.

My question is about the proper implementation of data buffering within a game loop, with the intention of optimizing performance, and keeping IP fragmentation in mind. I'll give a python pseudocode example from just the client perspective, for simplicity. Also assume we are using UDP sockets.

Let's say hypothetically there are some events that can occur client-side, which should be transmitted to the server. Let's encapsulate this data in a simple dictionary called a message. A single message might look like this:

message = {
'type': 'move',
'data': 'right',
}


Within a single iteration of the client game loop, its possible for many of these messages to be generated. Here's an ultra-stupid game loop that might do this:

def main_loop():
if game.input.buttonA:
send_message({'type': 'foo', 'data': 'bar'})
for event in game.system.events:
send_message({'type': 'event', 'data': event.data})
game.render()


A naive implementation of send_message() would be to serialize the message and fire it off in a packet to the server immediately. The problem with that is that we could be potentially sending hundreds of packets per frame--I don't understand the low level details but I would think flooding the socket like this would be dangerous and bad.

Since these messages are really small when serialized, like <50 bytes, we could batch them up together in a single packet to send to the server. The implementation of that might look like this:

# Queue a message instead of sending it immediately
def queue_message(msg):
message_queue.push(msg)

# Flush the message queue into a single stream, JSON serialize and send to server
def flush_messages():
buf = []
for message in message_queue:
socket.send(''.join(buf))
message_queue.clear()

def main_loop():
if game.input.buttonA:
queue_message({'type': 'foo', 'data': 'bar'})
for event in game.system.events:
queue_message({'type': 'event', 'data': event.data})
game.render()
flush_messages()  # Send actual packet at the end of the loop


This seems much better, because we're sending far less packets per frame by grouping messages together. But what happens if the game loop generates a LOT of messages? Well, if the total packet size is over the MTU (around 1500 bytes for UDP), then we're going to experience fragmentation.

Lets say you send a 2500 byte packet. It will get fragmented into two separate packets and then reassembled transparently on the other end. From how I understand it, the problem with this is that if either half gets dropped, the whole packet is lost. When we're dealing with a highly realtime networking architecture like a game here, I think we actually would prefer to have only half of those messages and get the other half later, rather than none at all. Especially because the messages dont have any dependency on each other, they are just little chunks of data.

The problem I'm facing now is how to properly implement application level fragmentation, such that I can control how packets get split up. One way to do this would be to go through all my messages, putting them into packets until the packet is full, and then create a new packet, finally sending all of the packets at once.

def flush_messages():
buf = []
bufsize = 0
packets = [buf]

# Stuff messages into packet buffers, overflowing into the next when we hit MTU
for message in message_queue:
msgsize = len(message)
if bufsize + msg_size > MAXIMUM_PACKET_SIZE:
buf = []
bufsize = 0
packets.append(buf)
buf.append(message)
bufsize += msgsize

# Send all packets now and empty the message queue
for packet in packets:
socket.send(''.join(packet))
message_queue.clear()


Another way would be to simply only send the first 1500 bytes worth of messages this frame, and allow the rest to be handled the next frame.

def flush_messages()
buf = []
bufsize = 0

for message in message_queue:
msgsize = len(message)
if bufsize + msgsize > MAXIMUM_PACKET_SIZE:
break
buf.append(message)

# Send packet, but DONT clear message queue
socket.send(''.join(buf))


Of course, this latter approach has the danger of the buffer climbing over time and the server experiencing massive lag with respect to the client.

What's the right way to do this? Is my buffering approach here is wrong to begin with?

• Thinking of sending JSON text packets instead of binary custom-protocol packets is immensely wrong. I won't go as far as downvoting every answer which doesnt tell him "don't", but I couldn't blame anyone who did. – o0'. Dec 8 '13 at 17:08
• Agreed, I would never use JSON in practice. I used it in the mock example here because it is simply a serialization format which is well known, and I want to discuss structural concerns with the code rather than which serialization mechanism to use for messages. – minism Dec 20 '13 at 8:31
• Still it put you in the wrong track. You are talking about aggregating messages up to 1500 bytes, while in practice 1500 bytes should be like 300 messages: you'd never need to aggregate so much data. – o0'. Dec 20 '13 at 9:13

First off, you misunderstand how UDP works:

Lets say you send a 2500 byte packet. It will get fragmented into two separate packets and then reassembled transparently on the other end.

UDP datagrams are atomic. An UDP datagram will not be split up into packets.

I recommend sending the data in small atomic datagrams. The overhead is typically 28 bytes, not too excessive for 50 byte messages I think. If you want to batch them together, that is fine, but do not exceed 1500 bytes.

Make sure your datagrams are self contained, and useful in and by itself. Do not spread a single message over two datagrams, if one gets lost, the other is of no use.

• Minor note: 1500 is the maximum possible MTU value on the Internet. You are not guaranteed to be able to transmit that much in a single datagram -- that's the maximum it can possibly be. 1350 is the usual guess at "lowest common denominator" for MTU. – Trevor Powell Dec 1 '13 at 7:08

I would not recommend the second approach if your game is network intensive. As you pointed out, your game packets can experiment increasingly delay in this case.

I'm afraid that to be totally sure which one is the best approach you should profile your system. You already listed the relevant info needed to be profiled in your tests. They are:

1. How much lag is introduced when you postpone sending part of the packets. An elegant and robust way to quantify that is to make a stress test using threads simulating clients. The less elegant way is to write a fake flush function/object that have the intended behavior.
2. What is your peak of data transfer with acceptable lag. I think the same test of item 1 can report this quantity.
3. This is less important, but to eliminate all uncertains you could also quantify the percentage of game loop time that is being used by the disassemble/assemble of the messages.

You should always save in the back of your head the UNIVERSAL rules of optimization:

1. Should follow the rule "Don't do that unless you have to" or your system will suffer from premature optimisation.
2. Should not harm the system architecture. The API and maintainability is always first priority, since in the long run it pays itself by letting us sleep well...
3. Should be preceeded by profiling.

The same tips about optimizations are in this question. I would also suggest the book Effective Java, where these tips are extracted from. It is a must read for anyone which want to take the best from OOP.

The problem I'm facing now is how to properly implement application level fragmentation, such that I can control how packets get split up. One way to do this would be to go through all my messages, putting them into packets until the packet is full, and then create a new packet, finally sending all of the packets at once.

This is the gist of the correct approach. More sophisticated approaches need to take into account message priority and volatility. Given a particular client (player), consider two different objects in your game: one is another visible but distant player and the other is an NPC about to attack the client's avatar. Assuming you have only the space left in your out-going packet for the update of one or the other you must have a way to choose which to go with. This will generally be based on a combination of factors both static and dynamic. Players typically have a higher static priority than NPCs but closer entities are more important than distant ones. Some calculation needs to - for each client - determine the current priority of each sending object or message. For instance, that NPC about to attack should be of the highest priority since it has the most impact on the client's game experience, even though you usually want all the other players to have high priority normally to keep the social and multiplayer aspects of the game running smoothly. Priority can go as low as "off" as in the usual kind of AOI filtering; distant objects probably don't need to be updated on the client at all (and in fact, not sending updates for non-visible objects is an important anti-cheating behavior in some kinds of PvP games). Object priority can also include time since last update to ensure that even low-priority objects will be updated periodically even under higher message loads. Remember that these values are per-client for any dynamic value; what's high priority to one player's experience will not be high priority for another's in many cases, especially for players that are far apart from each other.

A second consideration is that of volatility. Say an object A generates a new set of position/rotation/velocity values each frame and we want these updates to be network replicated. If during the last "network frame" you were unable to fit object A into a packet but you are this network frame, surely you don't want to send two copies of A's information (one stale) and use up all that extra space. In your message queue, you need a way to know that a particular message replaces another rather than retaining old copies of volatile data. The client doesn't need to know about the intermediate positions; only the most current. Client-side prediction and interpolation will deal with smoothing over the missing intermediate position data. Some messages are not volatile, however. A "player fired his gun" message should always be delivered to ensure that everyone sees the firing animations and doesn't miss one. Some messages may even be relevant to gameplay and the state changes they trigger may be essential, though in general you should prefer sending the current state (which is volatile) rather than sending signals to change state (which are non-volatile).

These both play into packet retransmissions, too. Instead of trying to retransmit a whole packet you can be more intelligent and only attempt to retransmit any non-volatile and non-supceded volatile messages that were in that packet. Given that most messages should be volatile in the typical game, this means that retransmissions will be of smaller size than their original packets and multiple retransmissions of the same data will not grow particularly quickly. You can then often keep a single fixed-rate packet stream even in the face of dropped packets.

So far as worrying about objects trying to send too many messages for one packet: just don't do that. The absolute most important thing you can do (aside from making it all actually work, of course) is to add very comprehensive and detailed debugging, timing, and profiling tools to your networking library. You should be able to see at a glance which objects are sending messages, how many messages they're sending, current priorities of objects and messages, number of bytes being generated per object, the per-frame message and byte rates of the game, etc., all both incoming and outgoing. Being able to dump stats in a textual format is nice; being able to visualize graphs of game sessions is even nicer; being able to visualize real-time in-game graphs is nicest (though you'd still want the other two). The ability to capture and replay the network game is also exceedingly handy. In the end, you should have the tools on hand to simply make sure your game isn't trying to generate too much data to fit in one packet. If you're having trouble, either consider raising your game's bandwidth requirements (many people use requirements based on advice from past generations of game consoles and their lower limits) or consider trimming some of the "fat" out of your network data.

Remember that with a combination of priorities and sensible update rates you can cut traffic quite a bit. A game object doesn't need to constantly retransmit its health but can instead only transmit it when it changes. Lots of game state can be updated very infrequently. Take a game timer for instance. Once a clock is synchronized, the client can be trusted to tick it appropriately. Periodically resynchronize the clock just to account for any drift rather than trying to send a current value every network frame. With a single synchronized clock you can then express many other more complicated messages as simple clock deltas (say, instead of a large absolute time value you can now use small deltas from the clock, allowing more bit-level compression).

That last aside bringing up the point: get comfortable with bit-level compression. It's especially common for those working in higher-level languages like Python to be less aware of the tricks you can do with bit twiddling and compression. Numbers you know to always be small can be encoded with less bits. String/enum values can often be replaced with much smaller indices to pre-computed (or at least pre-agreed-upon in early initialization messages) tables. A 3x3 rotation matrix (9 floats) can be trivially converted to one quaternion (4 floats). The quaternion can then be further optimized since we know we're always using unit quaternions: we can drop one component (now down to 3 floats) and then use much smaller IEEE754-like formats (or a fixed-precision format) often dropping the per-component size pretty far below their usual 32 bits. Given that most of your messages are likely to be position/rotation/velocity updates, figuring out how to best compress those values will give you a lot of bang for the buck.

There's a lot to be said for how you package up multiple messages giving further advantage to sorting them before packing them. Take again the pos/rot/vel updates. If you're sending lots of them per packet, consider having a single update message that encodes a list of updates rather than each update individually. Assuming you need both the update data itself and an object ID, you can reduce things from a packet payload of msg_header|id|data|msg_header|id|data|msg_header|id|data|... to msg_header|count|id|data|id|data|id|data|... which results in a net saving of payload size after only a few messages (by removing the need to repeat the the msg_header data more than once). Obviously if you have only one of a given message then the count field may end up being a net loss in terms of size reduction so this trick needs to be thoughtfully applied to only specific messages (or thoughtfully encoded if you want something very generic). You could even reduce the need to repeat id much or at all if you can figure out a good way for your game to keep network IDs (mostly) contiguous. These are all micro optimizations in the general sense but for some types of messages they can be rather macro-sized improvements.

Short version: message priorities and tools, tools, tools.

For a game you're generally sending 10-30 packets per second, so at most you'll have 1/10th of a second of data in that buffer. If you're generating enough data to fill a 1500 byte packet in that time then you're almost certainly going to have bandwidth problems.

Many home internet connections have a very limited upload speed, so unless the game's limited to 2-4 players you'll run out of bandwidth on slower connections well before you hit the 1500 byte limit.

Because of that I wouldn't worry about it - if it's causing you problems you probably need to do some optimization on the data size before looking at the buffering scheme.

50 bytes packet? JSON? Take some steps back.

Sending JSON-encoded messages makes no sense, it's an egregious waste of resources.

1. figure out any thing that the client might be want to tell the server
2. create extremely small packets with bitwise fields

The first few bits should be the "command" (if you want to make it simpler, 1-byte commands are ok), followed by a few bits for the arguments.

For instance, your command for "move" is 0x4, and the following bits tell which movement buttons is the player clicking.

You also likely want to include a "sequence" number (1 or 2 bytes) to order packets, i.e. to discard older ones.

In total you should have packets ranging from 1 to 5 bytes tops. If they are any bigger, it's extremely likely you are doing something wrong.

Of course it might make sense to have an occasional big packet, but even that one should be carefully designed to be as small as possible.