Applicability of group communication for increased scalability in MMOGs

ABSTRACT

Massive multiplayer online games (MMOGs) are today the driving factor for the development of distributed interactive applications, and they are increasing in size and complexity. Even a small MMOG supports thousands of players, the biggest support hundreds of thousands of concurrent players. Since they are typically built as strict client-server systems, they suffer from the inherent scalability problem of the architecture. Computing power and bandwidth limitations close to the server limit the possible number of players. Also, the latency of communication between players through the server will be higher than using direct communication. In the paper, we address these issues and investigate improvement options.

A typical MMOG consists of a virtual world with a concept of time and space that is similar to the real world. In it, players are represented by avatars. Only subsets of these avatars interact with each other at any given time. This allows us to divide them into groups, and communication among group members becomes a multi-party communication problem. Thus, to reduce resource consumption, we compare the performance of several algorithms for group communication with the current central server approach. We use overlay multicast as the means of providing group communication, and research algorithms for creating shortest path trees, spanning trees, delay-bounded spanning trees and, more specific, applying Steiner tree heuristics.

Our experimental results indicate that different approaches are useful to reduce resource consumption while achieving a good perceived quality under varying conditions, such as frequent changes in group membership and the demand for low latency.

REFERENCES

• 1: S. Banerjee and B. Bhattacharjee. Analysis of the NICE application layer multicast protocol. Technical Report UMIACSTR, 2002-60 and CS-TR 4380, Department of Computer Science, University of Maryland, College Park, June 2002.
• 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, San Jose, CA, USA, 2001.
• 4: M. S. Borella. Source models of network game traffic. Elsevier Computer Communications, 23(4):403--410, Feb. 2000.
• 5: Marcel Busse , Bernd Lamparter , Martin Mauve , Wolfgang Effelsberg, Lightweight QoS-support for networked mobile gaming, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016540.1016543]
• 6: C. Chambers, Wu-chang Feng, S. Sahu, and D. Saha. Measurement-based characterization of a collection of on-line games. In Proceedings of the USENIX Internet Measurement Conference (IMC), pages 1--14, Berkeley, CA, USA, 2005.
• 7: Kuan-Ta Chen , Polly Huang , Chun-Ying Huang , Chin-Laung Lei, Game traffic analysis: an MMORPG perspective, Proceedings of the international workshop on Network and operating systems support for digital audio and video, June 13-14, 2005, Stevenson, Washington, USA [doi>10.1145/1065983.1065988]
• 8: Mark Claypool, The effect of latency on user performance in real-time strategy games, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.49 n.1, p.52-70, 15 September 2005 [doi>10.1016/j.comnet.2005.04.008]
• 9: Marcus Poggi de Aragão , Renato Fonseca F. Werneck, On the Implementation of MST-Based Heuristics for the Steiner Problem in Graphs, Revised Papers from the 4th International Workshop on Algorithm Engineering and Experiments, p.1-15, January 04-05, 2002
• 10: G. Feng, Tak-Shing, and P. Yum. Efficient multicast routing with delay constraints. Int. J. Commun. Sys., 12:181--195, January 1999.
• 11: Wu-chang Feng , Francis Chang , Wu-chi Feng , Jonathan Walpole, Provisioning on-line games: a traffic analysis of a busy counter-strike server, Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, November 06-08, 2002, Marseille, France [doi>10.1145/637201.637223]
• 12: Geoffrey Fox , Shrideep Pallickara, The Narada Event Brokering System: Overview and Extensions, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, p.353-359, June 24-27, 2002
• 13: P. Francis, S. Ratnasamy, R. Govindan, and C. Alaettinoglu. Yoid project.
• 14: Funcom. Anarchy online. http://www.anarchy-online.com/, Feb. 2006.
• 15: M. Goodrich and R. Tamassia. Algorithm Design: Foundations, Analysis and Internet Examples. John Wiley and Sons, 2002.
• 16: C. Griwodz and P. Halvorsen. The fun of using TCP for an MMORPG. In Proceedings of the International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV), Newport, RI, USA, May 2006. ACM Press.
• 17: Oliver Heckmann , Michael Piringer , Jens Schmitt , Ralf Steinmetz, On realistic network topologies for simulation, Proceedings of the ACM SIGCOMM workshop on Models, methods and tools for reproducible network research, August 25-27, 2003, Karlsruhe, Germany [doi>10.1145/944773.944779]
• 18: Shun-Yun Hu , Guan-Ming Liao, Scalable peer-to-peer networked virtual environment, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016540.1016552]
• 19: F. Hwang, D. Richards, and P. Winter. The Steiner tree problem. Elsevier Annals of Discrete Mathematics, 53:203--282, 1992.
• 20: Takuji Iimura , Hiroaki Hazeyama , Youki Kadobayashi, Zoned federation of game servers: a peer-to-peer approach to scalable multi-player online games, Proceedings of 3rd ACM SIGCOMM workshop on Network and system support for games, August 30-30, 2004, Portland, Oregon, USA [doi>10.1145/1016540.1016549]
• 21: C. Jin, Q. Chen, and S. Jamin. Inet: Internet topology generator. Technical Report CSE-TR-433-00, Dept. of EECS, University of Michigan, Ann Arbor, Sept. 2000.
• 22: L. Kou, G. Markowsky, and L. Berman. A fast algorithm for Steiner trees. Acta Inf., 15:141--145, 1981.
• 23: L. S. Liu and R. Zimmermann. Immersive peer-to-peer audio streaming platform for massive online games. In Proceedings of the IEEE International Workshop on Networking Issues in Multimedia Entertainment (NIME), Las Vegas, NV, USA, 2006.
• 24: 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]
• 25: Alberto Medina , Anukool Lakhina , Ibrahim Matta , John Byers, BRITE: Universal Topology Generation from a User''s Perspective, Boston University, Boston, MA, 2001
• 26: Lothar Pantel , Lars C. Wolf, On the impact of delay on real-time multiplayer games, Proceedings of the 12th international workshop on Network and operating systems support for digital audio and video, May 12-14, 2002, Miami, Florida, USA [doi>10.1145/507670.507674]
• 27: D. Pendarakis, S. Shi, D. Verma, and M. Waldvogel. ALMI: An application level multicast infrastructure. In Proceedings of the 3rd USENIX Symposium on Internet Technologies and Systems (USITS), pages 49--60, 2001.
• 28: V. Rayward-Smith and A. Clare. The computation of nearly minimal Steiner trees in graphs. International Journal of Mathematical Education in Science and Technology, 14(1):8pp, 1983.
• 29: Nathan Sheldon , Eric Girard , Seth Borg , Mark Claypool , Emmanuel Agu, The effect of latency on user performance in Warcraft III, Proceedings of the 2nd workshop on Network and system support for games, p.3-14, May 22-23, 2003, Redwood City, California [doi>10.1145/963900.963901]
• 30: S. Shi and J. Turner. Routing in overlay multicast networks. In Proceedings of the Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), New York, NY, USA, 2002.
• 31: Sherlia Y. Shi , Jonathan S. Turner , Marcel Waldvogel, Dimensioning server access bandwidth and multicast routing in overlay networks, Proceedings of the 11th international workshop on Network and operating systems support for digital audio and video, p.83-91, January 2001, Port Jefferson, New York, United States [doi>10.1145/378344.378357]
• 32: The boost graph library: user guide and reference manual, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2002
• 33: H. Takahashi and A. Matsuyama. An approximate solution for the Steiner problem in graphs. Math. Japonica 24, 24(6):573--577.
• 34: Knut-Helge Vik, Game state and event distribution using proxy technology and application layer multicast, Proceedings of the 13th annual ACM international conference on Multimedia, November 06-11, 2005, Hilton, Singapore [doi>10.1145/1101149.1101365]
• 35: Jürgen Vogel , Jörg Widmer , Dirk Farin , Martin Mauve , Wolfgang Effelsberg, Priority-based distribution trees for application-level multicast, Proceedings of the 2nd workshop on Network and system support for games, p.148-157, May 22-23, 2003, Redwood City, California [doi>10.1145/963900.963914]
• 36: B. M. Waxman. Routing of Multipoint Connections. IEEE Journal of Selected Areas in Communications, 6, December 1988.
• 37: Shinya Yamamoto , Yoshihiro Murata , Keiichi Yasumoto , Minoru Ito, A distributed event delivery method with load balancing for MMORPG, Proceedings of 4th ACM SIGCOMM workshop on Network and system support for games, October 10-11, 2005, Hawthorne, NY [doi>10.1145/1103599.1103610]
• 38: A. Young, C. Jiang, M. Zheng, A. Krishnamurthy, L. Peterson, and R. Wang. Overlay mesh construction using interleaved spanning trees, 2004.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.0 General
          Subjects: Games

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Artificial, augmented, and virtual realities
      H.5.3 Group and Organization Interfaces
          Subjects: Organizational design; Collaborative computing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Performance