Adaptive partitioning for multi-server distributed virtual environments

ABSTRACT

A distributed virtual environment (DVE) allows users at different geographical locations to share information and interact within a common virtual environment (VE) via a local network or through the Internet. However, when the number of users exploring the VE increases, the server will quickly become the bottleneck. To enable good performance, we are currently developing a multi-server DVE prototype. In this paper, we describe an adaptive data partitioning technique to dynamically partition the whole VE into regions. All objects within each region will be managed by a single server. As the loading of the servers changes, we show how it can be redistributed while minimizing the communication cost. Our initial results show that the proposed adaptive partitioning technique significantly improves the performance of the overall system.

REFERENCES

• 1: Asheron's Call. Available at http://www.microsoft.com/games/zone/asheronscall/.
• 2: Todd Barron , Patricia Pizer, Multi-Player Game Programming with CDROM, Premier Press, Incorporated, 2001
• 3: Jimmy H. P. Chim , Mark Green , Rynson W. H. Lau , Hong Va Leong , Antonio Si, On caching and prefetching of virtual objects in distributed virtual environments, Proceedings of the sixth ACM international conference on Multimedia, p.171-180, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290769]
• 4: J. Chim, R. Lau, H. Leong, and A. Si. CyberWalk: A Web-based Distributed Virtual Walkthrough Environment. IEEE Trans. on Multimedia (to appear).
• 5: Tapas K. Das , Gurminder Singh , Alex Mitchell , P. Senthil Kumar , Kevin McGee, NetEffect: a network architecture for large-scale multi-user virtual worlds, Proceedings of the ACM symposium on Virtual reality software and technology, p.157-163, September 1997, Lausanne, Switzerland [doi>10.1145/261135.261164]
• 6: Diablo II, Starcraft. Available at http://www.blizzard.com/.
• 7: EverQuest. Available at http://everquest.station.sony.com/.
• 8: Thomas A. Funkhouser, RING: a client-server system for multi-user virtual environments, Proceedings of the 1995 symposium on Interactive 3D graphics, p.85-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199418]
• 9: M. Hori, T. Iseri, K. Fujikawa, S. Shimojo, and H. Miyahara. Scalability Issues of Dynamic Space Management for Multiple-Server Networked Virtual Environments. In Proc. of IEEE Pacific Rim Conf. on Communications, Computers and signal Processing, pages 200--203, 2001.
• 10: Beatrice Ng , Antonio Si , Rynson W.H. Lau , Frederick W.B. Li, A multi-server architecture for distributed virtual walkthrough, Proceedings of the ACM symposium on Virtual reality software and technology, November 11-13, 2002, Hong Kong, China [doi>10.1145/585740.585768]
• 11: Quake. Available at http://www.idsoftware.com/.
• 12: Ultima Online. Available at http://www.uo.com/.