Efficient Zone Mapping Algorithms for Distributed Virtual Environments

ABSTRACT

This paper deals with the zone mapping problem in large-scale distributed virtual environments (DVEs), e.g., massively multi-player online games, distributed military simulations, etc. To support such large-scale DVEs with real-time interactions among thousands of concurrent, geographically separated clients, a distributed server infrastructure is generally needed, and the virtual world can be partitioned into several distinct zones to distribute the load among the servers. The NP-hard zone mapping problem concerns how to assign the zones of the virtual world to a number of distributed servers to improve interactivity. In this paper, we propose new zone mapping algorithms based on a Linear Programming relaxation of the original problem and meta-heuristics such as local search and evolutionary optimization techniques. We conducted extensive experiments with realistic Internet latency models obtained from real measurements using millions of pairs of geographically distributed IP addresses. The results have shown that our newly proposed algorithms significantly improved the performance of large-scale DVEs in terms of overall interactivity, when compared with existing mechanisms.

REFERENCES

• 1: Internet delay space synthesizer - data. Available at http://www.cs.rice.edu/ bozhang/ds2/matrix/, retrieved Nov 2008.
• 2: A. Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science, pages 509-512, 1999.
• 3: Wu-chang Feng , Wu-chi Feng, On the geographic distribution of on-line game servers and players, Proceedings of the 2nd workshop on Network and system support for games, p.173-179, May 22-23, 2003, Redwood City, California [doi>10.1145/963900.963916]
• 4: P. C. Chu , J. E. Beasley, A genetic algorithm for the generalised assignment problem, Computers and Operations Research, v.24 n.1, p.17-23, Jan. 1997 [doi>10.1016/S0305-0548(96)00032-9]
• 5: Harald Feltl , Günther R. Raidl, An improved hybrid genetic algorithm for the generalized assignment problem, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.968102]
• 6: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 7: O. Heckmann, M. Piringer, J. Schmitt, and R. Steinmetz. Generating realistic isp-level network topologies. IEEE Communication Letters, 2003.
• 8: Holger Hoos , Thomas Sttzle, Stochastic Local Search: Foundations & Applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 9: Kang-Won Lee , Bong-Jun Ko , Seraphin Calo, Adaptive server selection for large scale interactive online games, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.49 n.1, p.84-102, 15 September 2005 [doi>10.1016/j.comnet.2005.04.006]
• 10: John C. S. Lui , M. F. Chan, An Efficient Partitioning Algorithm for Distributed Virtual Environment Systems, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.193-211, March 2002 [doi>10.1109/71.993202]
• 11: C. D. Nguyen, F. Safaei, and P. Boustead. Optimal assignment of distributed servers to virtual partitions for the provision of immersive voice communication in massively multiplayer games. Elsevier Computer Communications, 29(9), 2006.
• 12: L. Qiu, V. Padmanabhan, and G. Voelker. On the placement of web server replicas. In Proc. of IEEE INFOCOM, 2001.
• 13: Sandeep Singhal , Michael Zyda, Networked virtual environments: design and implementation, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1999
• 14: D. N. B. Ta and S. Zhou. A Dynamic Load Sharing Algorithm for Massively Multi-Player Online Games. In Proc. of the 11th IEEE International Conference on Networks, 2003.
• 15: D. N. B. Ta and S. Zhou. A Network-centric Approach to Enhancing the Interactivity for Large-Scale Distributed Virtual Environments. Elsevier Computer Communications, 2006.
• 16: H. Tangmunarunkit, R. Govindan, S. Shenker, and D. Estrin. The Impact of Routing Policy on Internet Paths. In Proc. of IEEE INFOCOM, 2001.
• 17: B. M. Waxman. Routing of Multipoint Connections. IEEE Journal on Selected Areas in Communications, 9:1617- 1622, 1988.
• 18: Bo Zhang , T. S. Eugene Ng , Animesh Nandi , Rudolf Riedi , Peter Druschel , Guohui Wang, Measurement based analysis, modeling, and synthesis of the internet delay space, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177091]
• 19: Suiping Zhou , Wentong Cai , Bu-Sung Lee , Stephen J. Turner, Time-space consistency in large-scale distributed virtual environments, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.14 n.1, p.31-47, January 2004 [doi>10.1145/974734.974736]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Distributed

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
zone mapping, distributed virtual environments, metaheuristics