[Literature] Network Infrastructure for Massively Distributed Games

by Daniel Bauer et al. 2002

Motivation

Client-Server (CS) Architecture: According to the authors, an Apache server on a usual computer using a Linux OS connected to a Gigabit Ethernet can handle roughly 2000 256-byte HTTP transactions per second. Server farms are said to handle a number of connections on the same order of magnitude. The authors also mention that whereas network bandwidth is abundant, the bottlenecks of such systems are CPU cycles, memory bandwidth, and server I/O. They conclude that server farms handling loads greater than 10⁵ HTTP requests per second currently [in 2002] are infeasible with existing technology and, by extension, so are million-person games requiring as little as a single event per minute. They also take Everquest as an example: Although Everquest claims that tens of thousands of people can participate simultaneously, [...] Everquest is better thought of as 40 independent instances of the same game, each of which handles about 2000 playersEven if this paper was published in 2002, I think what they wrote is still accurate.

Peer-to-Peer (P2P) Architecture: Scalability is limited by the computational power of the weakest peer, because each peer needs to run the complete simulation. Therefore, the authors suggest a hybrid approach to overcome the scalability problems.

Proposed network-level solution: booster boxes

The authors start with the assumption that not all the information the clients send to the server is relevant. The server often sends the same packets to different clients (for instance, in a PVP zone, the death of a player will be communicated to all the players who currently see the dead player). To solve this problem, booster boxes can be set up between ISP Access Routers and Edge Routers. They have 4 roles:

• Caching non-real-time information
• Aggregation of redundant events
• Filtering of no-longer relevant events
• Routing packets to the appropriate server(s)

Booster box architecture

Data layer: for the bulk of traffic, booster boxes behave like ordinary level-2 forwarding devices, e.g. like ethernet switches. The data layer must be able to handle packet forwarding at speeds equivalent to the port of a residential access router, i.e. in the range of 155Mbits/s to 1Gbits/s and still has to process, copy or divert packets to the booster layer. The authors explain that a pure hardware solution is not flexible enough and a pure software solution is not able to handle such line speeds, that is why they introduce Network Processors (NP). A NP is a general purpose processor with access to many network-specific co-processors performing tasks such as checksum generation, table look up and header comparison. They suggest writing the network-forwarding code in C and load this code in the processor.

Booster layer: application-level layer. A Booster Library contains the API through which the boosters can call the data-layer operations (ie copy, divert, pass through, forward, ...). Boosters' code can be executed either on a general-purpose CPU or on the NP (or on a combination of the 2). Boosters can perform tasks independently or be coordinated by the Booster Control Point to work together. Another role of the Booster Control Point is to establish a Quality of Service overlay network between booster boxes. This Booser Overlay Network (BON) can circumvent several network problems that I have not fully understood yet. BON uses its own addressing schemes and packets eventually exchanged between booster boxes and servers contain a BON header (a BON packet is encapsulated in an IP packet).

Examples

Large Interactive Game Show: a TV program asks a question, spectators send their answer to the TV server (on the Internet). The authors pretend their system reduces the server's load exponentially.

Large Virtual World: The dotted arrows in the figure nearby shows how information comes from a player to the server. A white player sends an event to the closest booster box (in the network cloud). The correct server receives the event notification from the booster box. The solid arrows show how the server answers to this information: all the booster boxes to which white players are connected receive the update and forward it to their own white players.
Remark: in the case of a server-wide event such as a GM broadcast, the white game server will have somehow to tell the black game server to forward the information.
Interestingly, the authors suggest creating a game transport protocol in which the virtual location is encoded independently of the particular game, bringing the advantage that a game booster could to a large extent be independent of the game. To my mind, this idea is nice for ISP because they will rent their booster boxes to MMOG companies, but MMOG companies will have to follow booster box norms. I do not think there is currently any consortium able to establish protocol norms on MMOG...

See also: Understanding Network Processors by Shah.

[Literature] Optimizing Online FPS Game Server Discovery through Clustering Servers by Origin Autonomous System

by Grenville Armitage, 2008 located here.

Armitage is Australian, and Australians seem to suffer from latency problems. This might explain why he was looking for an efficient way to solve a latency problem: server discovery in CS:S. According to the author, the (client-side) server discovery process algorithm is as follow:

1. Issue a getservers query to UDP port 27011 on the Steam master server
2. Receive a packet containing a list of 231 active servers <IP address:port>
3. Probe each game server in the previously received list
4. Repeat until the Steam master server has no more game servers to return

The speed of server discovery is actually configured by the user: it is the "What is your connection capacity" which possible parameters are "Modem 56k", "DSL", "DSL+", etc. This parameter changes the speed of game server probation (phase 3 in the algorithm above). There are approximately 30K game servers and with a Steam client configured with "DSL > 256K", 140 servers can be probed per second. Without optimization, it takes 230s to complete the discovery process with a Steam client configured with "DSL > 256K".

In general, players want the game server with the smallest ping or RTT. A first solution could be grouping servers based on their location, but it is not always true that the closer geographically the server is, the smaller the ping will be. The paper proposes clustering game servers by the Autonomous System to which each game server's IP address belongs (its origin AS), ie grouping servers based on the Internet topology. An AS relies on IP routing prefixes to group IP together. The author also added an automatic termination of server discovery when servers RTT are above a specified threshold such as 200ms. Here is the algorithm:

1. Retrieve all game servers
2. Group servers in clusters based on their AS number
3. Calibration process: this eventually splits clusters into smaller ones. In the end, the RTT of a randomly-picked server inside a cluster should be within a 40ms range of the cluster median RTT.
4. Rank clusters in ascending order of their median RTT
5. Probe the servers which have not been probed during the calibration process until a certain RTT threshold (200ms for instance)

Approximately 3k servers (10% of all the servers) are probed during the calibration phase. Around 1k clusters are created during the calibration process. In locations such as Australia, Taiwan or Japan, the algorithm stops within a minute and gives nearly all the available servers which RTT is below the specified threshold. Countries like Germany, the USA or the UK are closer to game servers and their RTT is smaller in average. Therefore, reaching the 200ms RTT threshold takes nearly the same time for players in these countries. However, if the RTT threshold is lowered to 100ms (for instance), the algorithm may stop much faster. If the player could specify the RTT threshold he/she wants the algorithm to stop, the proposed solution could be an efficient improvement to the current discovery process of Valve Counter-Strike game servers.