Client-Side Adaptive Search Optimisation for Online Game Server Discovery

Wed, 05/07/2008 - 00:01 by Damien Saucez • Categories:

The paper "Client-Side Adaptive Search Optimisation for Online Game Server Discovery" presented at Networking'08 and written by G. Armitage aims at reducing response time and resources consumption of server selection in online games.

It is well-known that game clients need low-latency connectivity to game servers. In the most popular games, the server is selected based on the RTT between to her. To decide which server to use, clients contact a "Master Server" that returns the list of all the available servers. The clients then measure RTT to all these servers and select the best (often, this choice is let to the gamers).

Unfortunately, as shown by the author, this technique consumes a large amount of ressources (a probe is sent to every server, NAT states are created at the client side...). For instance, from a client in Australia, probing the CS servers during 200 seconds causes 25K unique NAT entries to be created!

The paper proposes to tackle that problem by pre-treating the list. The idea is to order the server list by RTT using a clustering techniques. Thus the client choses a server within the most attractive clusters.

The author proposes to cluster the destinations according to their country (using maxmind) and a prefix-length of 8 bits. The Algorithm 1 shows a way to estimate the cluster latency and, if their is too many variations within the cluster, reduce the size.

The technique looks promising as it allows to reduce the number of measurements and the waiting time for the gamer. Indeed, instead of probing all the servers, only a small portion of server is queried within the cluster. When clusters are characterized, only clusters with to smallest latency are measured in depth (every server is queried).

The main advantage of that technique is that is it possible to "auto-stop" the server selection (Algorithm 2.) as the client has some hints about the possible server performances and it is no more needed to measure all the servers to make a choice.

In the paper, the clustering is a bit simple, and should be compared with ideas of papers like [08-04-14]. However, server latency pre-analysis in online games seems to be a promising technique.

This paper is related to our IDIPS researches (