HKMP Networking and Tag developments

There have been some exciting developments since the last post pertaining to the networking of HKMP and the HKMP Tag project. Read on to get an insight in these topics and for a (late) announcement of an event we are planning.

Let's start off by discussing the networking issues that were resolved with the latest release. To understand this topic, however, I need to go a bit in-depth about game networking to make the root cause of the issue understandable. If you are familiar with networking in general you might know that there are two established protocols in internet networking: TCP and UDP. Without needing to explain too much, TCP ensures that whatever data you are sending to another computer arrives and that the data arrives in order. This means that if I send two packets of data using TCP to another computer that the packet 1 will arrive first and packet 2 second. It also means that if packet 1 gets lost during transit (this can happen for a variety of reasons), it will be resend again along with packet 2 directly after it until the other computer lets us know that they have arrived properly. If we increase the number of packets we are sending, it will have an increasingly detrimental effect on lost packets. Namely, if the latency between two computers is very high, a single lost packet on TCP will require a lot of resending of packets to keep the ordering that TCP promises.

This is the reason that most games use UDP for networking; UDP doesn't care about any ordering nor does it offer reliability guarantees of packet arriving. At this point you might be wondering how we ensure that clients receive necessary information if UDP is not reliable. This is where we create our own networking protocol on top of UDP to leverage the speed of UDP while maintaining the possibility of sending reliable data. In essence, the client and server will always be sending packets to each other at a constant rate. These packets include an identifier called a sequence number. To make sure we know which packets are getting lost and to achieve reliability the other party will include acknowledgements in their packets. These acknowledgements are the sequence numbers of the packets that were successfully received. Now if we don't get an acknowledgement for packet within a certain timeframe, we can assume that the packet was lost. In that case, we simply include the data of the packet that was lost in the next packet we are going to send. If for some reason the packet was in fact received, but the acknowledgement did not come through (either not on time, or the packet with the acknowledgement was lost), it might happen that we are resending data that has been received before. In that case, we can simply drop the duplicated data.

Now with basics of game networking out of the way, let's talk about the a major bug that eluded my sight for quite a while. The way HKMP calculates when to resend data, is based on the current round trip time (RTT) of a packet. The RTT is how long it takes for a packet to reach the server and subsequently for a packet from the server to reach the client again. Generally, we say that if a packet takes twice the RTT to get acknowledged, we mark it as lost and resend the data. The RTT is a moving average and is adjusted with each packet that we receive. And this works very well, because if the RTT of new packets suddenly starts increasing, the average is slowly adjusting to the new situation and resending occurs accordingly. That is, it works very well if a connection is on-going for at least some time, but it does not work as well during the initial few packets of a new connection. And that is exactly one of the oversights that caused a fatal bug in the networking protocol.

The other oversight is caused by how HKMP handles lost packets. As described before, once we assume packets are lost we start resending the data that was in them. After all data has been added to the next packet, we disregard the lost packet, because I assumed we don't need it anymore. Unfortunately, that is not the case. We still need to keep track of when we sent the packet to be able to calculate the RTT for that specific packet. If we don't, the moving average RTT is never updated and will stay constant. Now if we combine these two oversights, we finally arrive at the fatal bug that caused high-latency clients not being able to connect to servers at all. At the start of the connection the average RTT is unstable, for example it is way too low to represent the actual average RTT. Most packets will now exceed twice the RTT and trigger both parties to resend data. Once the data is resend the packets are disregarded and no longer considered for the moving average of RTT. This causes a cycle in which we keep resending data, because the average RTT is not adjusted, and the RTT is not adjusted because we keep resending data.

Luckily, once I figured out the root cause of the issue, the fix was straightforward. At the start of new connections, the average RTT is considered very high. This will make the threshold for resending data relatively high, until we have sent a good number of packets to ensure that the average RTT is stable. And of course, we process the RTT of packets that have their data resend so the average RTT is properly updated in all cases.

Now for some other developments that are less technical: HKMP Tag has been released and with the release comes a public server that hosts Tag games 24/7. This means that the server will be starting games if enough players are present, use confined areas on the map to play the games in and restart the game. All fully automatic! In a future post I will discuss the technical aspects of how this was made possible. For now, if you are interested in checking it out, please join the HKMP Discord (https://discord.gg/QtAG3amg). Today (16th of March) we will be hosting an event to play Tag on this public server (hopefully with a lot of players). The event formally starts at 21:00 GMT+2, 15:00 EDT, 12:00 PDT. Since the games are automatic, you are free to join at any moment and leave whenever as well!