Table of Contents
Welcome to the first article of the Fast-Paced Multiplayer Implementation series.
UDP vs TCP
UDP and TCP are the two most widely used transport-layer protocols on the Internet. For fast-paced multiplayer you will most likely want to use UDP instead of TCP.
TCP always guarantees a reliable and ordered packet stream, at the cost of waiting for older messages to be re-sent when they’re lost in transit. UDP only offers an unreliable and unordered packet stream, allowing you to decide when and what to re-send, saving precious time.
I refer you to Glenn Fiedler’s article on the matter if you’re undecided. It’s certainly possible to get away with TCP with a compatible game design and some compromises as .io games have proven, but UDP is still very relevant. I’m choosing UDP for my prototype and this series.
UDP challenges
Gabriel’s demo models an environment where messages arrive in the order that they were sent, and are never lost - essentially what TCP guarantees. UDP will complicate matters:
- Unordered packets - Latency is variable: messages can arrive in a different order than the one they were sent in.
- Packet loss - Messages might not arrive at all. Around 1% of packets sent across the Internet are lost in travel even in the best networking conditions.
- Duplicate packets - Multiple copies of the same message (forked during travel or received through redundant network interfaces) may arrive at the destination.
These issues affect our prototype the most.
There are other issues involved such as:
- Packet fragmentation
- Flow control / congestion avoidance
- Poor data corruption detection mechanism
- Security
But I won’t dwell on those since they won’t affect our client-side prediction, server reconciliation or interpolation strategies.
UDP will not detect or correct any of the issues mentioned above when they occur. It’s up to the user to implement another layer on top of UDP to solve them in the optimal manner for our use-case.
Many networking libraries provide that layer. The most popular and battle-tested open-source ones seem to be RakNet, ENet, and Lidgren. Yojimbo is a new one that looks very promising.
In the next article of this series I will implement a minimal library similar to RakNet/ENet/Lidgren, and show how their features can be used to update our lag mitigation strategies for a UDP context.
Network model
The demo simulates the following network properties for each player. It’s possible to set these separately for incoming and outgoing messages.
- Minimum lag
- Maximum lag
- Packet drop chance
- Packet drop correlation (how much the current packet drop chance is affected by the previous one - to simulate bursts of packet loss)
- Packet duplication chance
Of course this model is a very simplified version of what happens in the real world but it’s good enough for my purposes.
Demo
Here’s the demo: https://fouramgames.com/posts/chart/main.html (Chrome recommended). The source (TypeScript) is provided below.
The graph at the top of the demo represents player 1’s network state (incoming and outgoing). Note that the player doesn’t send any messages if there’s no new inputs. Click on the legend to hide/show a dataset, and press p to pause the graph at any time.
The X axis represents the time when the packet was sent (in seconds since launch). You would normally expect this to be the time when a packet was received, so beware.
It continuously stays a second behind the current time so that new packets can be added without jarring pops in the graph.
The Y axis represents the latency of a packet (time received - time sent in milliseconds).
The lines connecting the points represent the order in which the packets were received. This allows to easily see when packets were received out of order. This is why the X axis represent the packet’s time sent instead of its time received.
Analysis
Server update rate
When the server’s update rate (10 FPS below) is lower than the client’s (50 FPS below) it creates a sawtooth wave, because packets are received in a “bundle”.
This can interfere with the interpretation of the graph. A server update rate of 60 FPS for example will create more consistent results.
Late packets
Disorder in the message stream can be described as packets arriving “late”. A packet is late when one sent more recently arrives before it at the destination. Packets are sent at a fixed rate, so this can only happen if the lag difference between two packets is larger than the update duration: update_duration < packet2_lagtime - packet1_lag_time.
The largest possible lag time difference is max_lagtime - min_lag_time. So to know if our simulated network state can generate late packets we can use the re-stated condition: update_duration < max_lagtime - min_lag_time.
Our clients run at 50 FPS (20ms update duration), and our server’s update rate is configurable.
The probability that a packet will arrive late (assuming a uniform random lag distribution) is:
(max_lagtime - min_lag_time - update_duration) / (max_lagtime - min_lag_time)
Late packets - Graph
The lines represent the order in which packets were received. Late packets generate a characteristic “V” shape slanted to towards the left - where the most recently sent packet in a line’s point pair is the one that the previous line connects to.
Late packets - Impact
An unordered message stream breaks our reconciliation, prediction, and interpolation strategies.
Our reconciliation and prediction strategies obtain from the server the last processed input ID for our client. It’s assumed that the server has processed every input that was sent before that one. UDP doesn’t provide that guarantee.
Our interpolation strategy inserts entity states into a buffer - first come first served. This will mirror one to one any disorder in the UDP packet stream.
The next article will extend the strategies to account for this.
Source
I’ve converted Gabriel’s original demo to TypeScript. You will find it almost identical, except for the additional network model properties. It’s the master branch of this repository: https://github.com/Ohmnivore/FastPacedMultiplayerImplementation/tree/master.
The network state graph was added in the chart branch: https://github.com/Ohmnivore/FastPacedMultiplayerImplementation/tree/chart.
Next article
In the next article I plan the design of a minimal reliable UDP library which will provide us with the message delivery types we need (unreliable, reliable, and reliable ordered), and some other necessary features. It will allow us to overcome the drawbacks of UDP in an efficient manner.