Fast-Paced Multiplayer Implementation: Message Delivery Types

Posted on January 01, 2018

Table of Contents

Welcome to the second article of the Fast-Paced Multiplayer Implementation series.

In this article I’ll plan a minimalist reliable UDP library for the demo’s simulated network, and discuss various message delivery types used for UDP and their use cases.

Features

Here are the features that the library will support:

  • A few message delivery types (discussed below)
  • Discarding of duplicate messages through sequencing
  • Round-trip time (ping) measurement

Of course it’s only a fraction of what a real reliable UDP library encompasses but the demo doesn’t require any other noteworthy features.

Message delivery types

RakNet has a page which describes the various ordering types it supports. I’ll implement the same ones.

  • Unreliable: Just send through UDP, the usual. Messages may arrive late or not at all.
  • Unreliable sequenced: Messages are sent with a sequence number. Late messages will be discarded. Messages may not arrive.
  • Reliable: Messages are guaranteed to arrive. Messages may arrive late.
  • Reliable sequenced: Messages are guaranteed to arrive. Late messages will be discarded.
  • Reliable ordered: Messages are guaranteed to arrive in the order that they were sent.

Some of the differences are not immediately apparent. This RakNet forum post did wonders to clear it up, and this is the best bit:

Reliable or unreliable refers to transmission. Sequenced and ordered refers how that transmission is reassembled in case it arrives with lost, duplicated, or out of order messages. -Rak’kar

Some use-case examples can also help.

Examples

I will recycle a few from the bottom of this RakNet page of programming tips.

Reliable:

  • Toggle switch where only the number of toggles matters
  • New networked entity creation

Reliable ordered

  • Chat messages
  • Client inputs

Reliable sequenced

  • It’s great for sending absolute values (i.e. order doesn’t matter) that we can’t afford to lose.
  • Sending a player’s health when it changes.
  • When sending positions for an entity only when it moves, we need to be sure that the last sent position arrives or else it could de-sync on the client until the entity moves again.
  • In practice you would often use reliable instead and use your own sequencing on top of it when you need to do more with late messages than to just discard them (such as inserting into an interpolation/jitter buffer).

Unreliable

  • Great for continuous high-frequency server updates - where a lost packet would be irrelevant by the time it arrives because newer ones will already have been received, and have newer data that supersedes all previous data.
  • Entity absolute position updates with an interpolation buffer. Late packets are inserted into their correct position in the buffer’s timeline.

Unreliable sequenced

  • Entity absolute position updates without interpolation. Late packets are simply discarded.

Beware

Every ordering type uses a separate message queue. Meaning that if for example message A is sent over reliable, and then message B over reliable ordered then they’re not guaranteed to arrive in order. If message B expects that message A has already been received by the time it arrives, this will be an issue.

It’s necessary to design around this limitation. Realistically, this might mean that reliable ordered will be used much more often than reliable for sending reliable messages. ENet takes a more extreme stance and actually only provides the reliable ordered type for reliable messages.

The demo’s message streams

Unreliable: We can afford to receive server updates out of order, we’ll just insert them in order into our interpolation buffer. We can even afford to lose some messages and use the newer ones for interpolation since we’re sending absolute positions, not the changes between frames as is (maybe more) often done.

Using our ping measurement we’ll be able to approximate where in the interpolation timeline a message belongs. We’ll also sequence these ourselves instead of using the unreliable sequenced type as that would drop old messages entirely. We need instead to detect them and process them accordingly. This will fix our entity interpolation strategy.

Reliable: At the moment clients receive their entity IDs not through the network but through the runtime. They should be sent reliably instead (can’t afford to lose them, but don’t care about order).

Reliable ordered: It’s imperative that the clients’ inputs arrive, and in the correct order. There are so many cases where the input order matters that we might as well assume that it always does.

Input order matters in the interaction of movement and collision physics for example: move down, then left (no collisions) vs move left (hit wall), then down.


(Tileset by Buch)

The server will send the last processed input ID to the client just as it has always done, but now this ordering type will effectively guarantee that all the prior inputs had been processed in the correct order - fixing our client-side prediction and server reconciliation strategies.

Ack callbacks

Some libraries notify the user when a message has been acknowledged by a peer.

This is very useful because it enables delta encoding (sending only changes relative to a state). For example consider messages that update an entity’s position. Message 7 (x = 100000, y = 100000) has been acked. Instead of sending the entity’s absolute position (x = 100004, y = 100028) in message 8, we can send (dx = 4, dy = 28, ref = 7). Notice that the numbers involved become much smaller, and we can use less space to store them and less bandwidth to send them. It’s a very interesting topic, but out of the scope of this series. I recommend Glenn Fiedler’s articles on the subject if you haven’t read them already.

Message type matrix

So let’s combine the transmission, ordering, and acknowledgment types.

It’s assumed that reliable messages, by their nature, are always acked. It’s also assumed that unreliable ordered messages don’t exist, the closest types being sequenced or user-managed buffering of unordered. We now have 7 different types to choose from!


Unordered Sequenced Ordered
Reliable + Acked
 Reliable + Acked + Unordered Reliable + Acked + Sequenced Reliable + Acked + Ordered
Unreliable Unreliable + Unordered Unreliable + Sequenced X
Unreliable + Acked
 Unreliable + Acked + Unordered
 Unreliable + Acked + Sequenced
 X


Not every reliable UDP library includes all these types out of the box. RakNet and Lidgren do.

Implementation

I’ll be using Glenn Fiedler’s articles as a guide for the reliability algorithms.

I will only include the unreliable, reliable, and reliable ordered message types, omitting the sequenced types. I feel like all too often users need sequencing but still need to process late messages instead of immediately dropping them. This is the case for the demo’s server update messages for example.

This will be made easy because all messages, even of the unreliable type, will include a sequence number that will be used internally to discard duplicate messages. Users could use the same field to implement their own sequencing behaviors.

On second thought: While actually working on the implementation I realized that there’s a benefit to implementing the reliable sequenced message delivery type at the network library level because it uses much less bandwidth (re-transmits messages less often) than the reliable type. I still chose to not include it to limit the scope of my work

I also won’t implement unreliable acked types because I won’t cover delta encoding in this series.

Next article

In the next article I report the interesting tidbits I learned while implementing the reliable UDP library, and make the client-side prediction and server reconciliation strategies great again.