01 March 2012

Netgames 2005

Summary of selected papers from the NetGames 2005 conference.

Traffic Characteristics of a Massively Multi-player Online Role Playing Game, by Kim et al.

  • Port mirroring through 1Gbps hub and tcpdump of 92 hours of a Lineage 2 server in December 2004. TCP packets.
  • Both upstream and downstream increase linearly with number of concurrent users.
  • Play session duration: 3 hours average, 26 min median, 40+ hours 99%
Stream Number of packets Ratio of data packets Payload (avg, median, and 99%) Bandwidth Bandwidth per user
Upstream (clients to server) 6.28 billions 23% (the rest are ACKs, SYNs, or FINs) 19, 20, 50 bytes max 9 Mbps 1.6 kbps
Downstream (server to clients) 6.43 billions 98% 318, 161, 1459 (= MTU) bytes max 140 Mbps 20 kbps

Dynamic Microcell Assignment for Massively Multiplayer Online Gaming, by De Vleeschauwer et al.

  • Divide the world in atomic square microcells. Compute each microcell's load induced by processing player actions (weight=1), forwarding player actions to neighbouring cells (w=0.05 if cells on same machine, w=0.1 if cells on different machines), receiving forwarded actions from neighbouring cells (w=0.2, w=0.4), and moving players to and from neighbouring cells (w=3, w=15). Then, assign cells to servers so that no server has a higher load than another server.
  • Algorithms to assign cells to servers:
    • Greedy: processes cells in descending order of their load, and assigns them to the server currently with the lowest load. Pro: fast. Con: does not take locality into account.
    • Clustering: start with each cell is a cluster. Merge two clusters that have the lowest load until there are as many clusters as servers. Con: in the last few steps, some heavy-load clusters are merged and may be assigned to servers that can't handle them.
    • Simulated annealing: start by randomly assigning cells to servers, then randomly swap or move cells around to find a better solution, and keep iterating to refine the solution. Able to find very good solutions if the initial solution comes from another algorithm.
    • Integer linear programming for the optimal deployment. Pro: optimal. Con: takes days to compute, but a timeout can be specified to get a suboptimal solution. (But then, other algorithms give better results faster).
  • Evaluation: If player hotspots are spread randomly, the maximum server load can be reduced by 30% compared to the baseline with one large cell of constant size per server. But if hotspots are regularly spread, and there's as many hotspots as available servers, then the microcell algorithms are at least 10% worse than the baseline. In general, simulated annealing starting from a greedy solution was the most efficient of the algorithms.

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.