Adaptive server selection for large scale interactive online games

ABSTRACT

In this paper, we present a novel distributed algorithm that dynamically selects game servers for a group of game clients participating in large scale interactive online games. The goal of server selection is to minimize server resource usage while satisfying the real-time delay constraint. We develop a synchronization delay model for interactive games and formulate the server selection problem, and prove that the considered problem is NP-hard. The proposed algorithm, called zoom-in-zoom-out, is adaptive to session dynamics (e.g. clients join and leave) and lets the clients select appropriate servers in a distributed manner such that the number of servers used by the game session is minimized. Using simulation, we present the performance of the proposed algorithm and show that it is simple yet effective in achieving its design goal. In particular, we show that the performance of our algorithm is comparable to that of a greedy selection algorithm, which requires global information and excessive computation.

REFERENCES

• 1: J. Bar-Ilan and D. Peleg. Approximation algorithms for selecting network centers. In Proc. 2nd Workshop on Algorithms and Data Structures, Lecture Notes in Comput. Sci. 519 pages 343--354, 1991.
• 2: Daniel Bauer , Sean Rooney , Paolo Scotton, Network infrastructure for massively distributed games, Proceedings of the 1st workshop on Network and system support for games, p.36-43, April 16-17, 2002, Bruanschweig, Germany [doi>10.1145/566500.566506]
• 3: P. Bettner and M. Terrano. 1500 archers on a 28.8: Network programming in age of empires and beyond. In Game Developers Conference 2001.
• 4: BRITE. http://www.cs.bu.edu/brite/
• 5: Butterfly.net. http://www.butterfly.net/
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: E. Cronin, B. Filstrup, and A. Kurc. A distributed multiplayer game server system, technical report, Univ. of michigan. Technical report, May 2001.
• 8: C. Diot and L. Gautier. A distributed architecture for multiplayer interactive applications on the internet, IEEE networks magazine, vol. 13, no. 4, July/August 1999.
• 9: Yow-Jian Lin , Katherine Guo , Sanjoy Paul, Sync-MS: Synchronized Messaging Service for Real-Time Multi-Player Distributed Games, Proceedings of the 10th IEEE International Conference on Network Protocols, p.155-164, November 12-15, 2002
• 10: Martin Mauve , Stefan Fischer , Jörg Widmer, A generic proxy system for networked computer games, Proceedings of the 1st workshop on Network and system support for games, p.25-28, April 16-17, 2002, Bruanschweig, Germany [doi>10.1145/566500.566504]
• 11: Mehrdad Parsa , Qing Zhu , J. J. Garcia-Luna-Aceves, An iterative algorithm for delay-constrained minimum-cost multicasting, IEEE/ACM Transactions on Networking (TON), v.6 n.4, p.461-474, Aug. 1998 [doi>10.1109/90.720901]
• 12: PlanetSide. http://www.planetside.com/
• 13: L. Qiu, V. Padmanabham, and G.Voelker. On the placement of web server replicas. In Proc. 20th IEEE INFOCOM 2001 August 2001.
• 14: Debanjan Saha , Sambit Sahu , Anees Shaikh, A service platform for on-line games, Proceedings of the 2nd workshop on Network and system support for games, p.180-184, May 22-23, 2003, Redwood City, California [doi>10.1145/963900.963917]
• 15: H. F. Salama, D. S. Reeves, and Y. Viniotis. An Efficient Delay-Constrained Minimum Spanning Tree Heuristic, Technical Report TR-96/46, North Carolina State University. Technical report,1996.
• 16: Terazona. http://www.zona.net/
• 17: D. G. Thaler and C. V. Ravishankar. Distributed center-location algorithms. IEEE Transactions on Selected Areas in Communications, vol. 15, issue 3 April 1997.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network communications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

General Terms:
Algorithms, Design, Performance

Keywords:
MMOG, distributed algorithm, server selection, synchronization delay model