Article

A scalable dynamic load distribution scheme for multi-server distributed virtual environment systems with highly-skewed user distribution

Authors:

Dongman LeeAuthors Info & Claims

VRST '03: Proceedings of the ACM symposium on Virtual reality software and technology

Pages 160 - 168

https://doi.org/10.1145/1008653.1008681

Published: 01 October 2003 Publication History

Abstract

This paper proposes and evaluates a scalable dynamic load distribution scheme for multi-server distributed virtual environment systems, where users are highly skewed rather than uniformly distributed over a virtual environment. In the proposed scheme, an overloaded server initiating load distribution selects a set of servers to be involved in load distribution by dynamically adapting to the workload status of other servers, unlike the existing approaches. Upon completion of server selection, the intiating server repartitions the regions dedicated to the involved servers using a graph partitioning algorithm so that all the involved servers have the roughly equal workload. The involved servers then migrate their workloads with each other in a peer-to-peer manner according to the result of repartitioning. We present and analyze the simulation results that compare the performance of the proposed scheme with that of the existing schemes.

References

[1]

Asheron's Call. http://www.microsoft.com/games/zone/asheronscall/.

[2]

W. Cai, P. Xavier, S. J. Turner, and B. Lee. A scalable architecture for supporting interactive games on the internet. In Proceedings of the 16th Workshop on Parallel and Distributed Simulation (PADS'02), pages 60--67, 2002.

Digital Library

[3]

J. Chen and V. E. Taylor. Mesh partitioning for efficient use of distributed systems. IEEE Transactions on Parallel and Distributed Systems, 13(1):67--79, January 2002.

Digital Library

[4]

T. K. Das, G. Singh, A. Mitchell, P. S. Kumar, and K. McGee. NetEffect: A network architecture for large-scale multi-user virtual worlds. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology (VRST'97), pages 157--163, 1997.

Digital Library

[5]

E. Frecon, C. Greenhalgh, and M. Stenius. The DiveBone: An application-level network architecture for Internet-based CVEs. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology (VRST'99), page 58--65, 1999.

Digital Library

[6]

T. Funkhouser. RING: A client-server system for multi-user virtual environments. In Proceedings of the Symposium on Interactive 3D Graphics (SI3D'95), pages 85--92, 1995.

Digital Library

[7]

D. B. Johnson and D. A. Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, pages 153--181. Kluwer Academic Publisher, 1996.

[8]

R. Kazman. Making WAVES: On the design of architectures for low-end distributed virtual environments. In Proceedings of the IEEE Virtual Reality Annual International Symposium (VRAIS'93), pages 443--449, 1993.

Digital Library

[9]

D. Lee, M. Lim, and S. Han. ATLAS - a scalable network framework for distributed virtual environments. In Proceedings of the ACM International Conference on Collaborative Virtual Environments (CVE'02), pages 47--54, September-October 2002.

Digital Library

[10]

Lineage. http://www.lineage.com/.

[11]

J. C. S. Lui and M. F. Chan. An efficient partitioning algorithm for distributed virtual environment systems. IEEE Transactions on Parallel and Distributed Systems, 13(3):193--211, March 2002.

Digital Library

[12]

M. R. Macedonia and M. J. Zyda. A taxonomy for networked virtual environments. IEEE MultiMedia Magazine, 4(1):48--56, January-March 1997.

Digital Library

[13]

METIS: Family of multilevel partitioning algorithms. http://www-users.cs.umn.edu/~karypis/metis/.

[14]

B. Ng, A. Si, R. W. H. Lau, and F. W. B. Li. A multi-server architecture for distributed virtual walkthrough. In Proceedings of the ACM Symposium on Virtual Reality Software and Technology (VRST'02), pages 163--170, 2002.

Digital Library

[15]

S. Pekkola, M. Robinson, M. O. Saarinen, J. Korhonen, S. Hujala, and T. Toivonen. Collaborative virtual environments in the year of the dragon. In Proceedings of the ACM International Conference on Collaborative Virtual Environments (CVE'00), pages 11--18, 2000.

Digital Library

[16]

G. Resta and P. Santi. An analysis of the node spatial distribution of the random waypoint mobility model for ad hoc networks. In Proceedings of the ACM International Workshop on Principles of Mobile Computing (POMC'02), pages 44--50, 2002.

Digital Library

[17]

S. Singhal and M. J. Zyda. Networked Virtual Environments: Design and Implementation. Addison-Wesley, 1999.

Digital Library

[18]

Ultima Online. http://www.uo.com/.

Cited By

Donkervliet JTrivedi AIosup APhanishayee AStutsman R(2020)Towards supporting millions of users in modifiable virtual environments by redesigning minecraft-like games as serverless systemsProceedings of the 12th USENIX Conference on Hot Topics in Cloud Computing10.5555/3485849.3485851(2-2)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3485849.3485851
Tsipis AKomianos VOikonomou K(2019)A Cloud Gaming Architecture Leveraging Fog for Dynamic Load Balancing in Cluster-Based MMOs2019 4th South-East Europe Design Automation, Computer Engineering, Computer Networks and Social Media Conference (SEEDA-CECNSM)10.1109/SEEDA-CECNSM.2019.8908282(1-6)Online publication date: Sep-2019
https://doi.org/10.1109/SEEDA-CECNSM.2019.8908282
Farlow STrahan J(2018)Periodic load balancing heuristics in massively multiplayer online gamesProceedings of the 13th International Conference on the Foundations of Digital Games10.1145/3235765.3235769(1-10)Online publication date: 7-Aug-2018
https://dl.acm.org/doi/10.1145/3235765.3235769
Show More Cited By

Recommendations

A task-based load distribution scheme for multi-server-based distributed virtual environment systems

Multi-server-based distributed virtual environment (MSDVE) systems have become prevalent, supporting a large number of internet users. In MSDVEs, the load balancing among servers is an important issue to achieve system scalability. However, existing ...
Scalable Request Routing with Next-Neighbor Load Sharing in Multi-Server Environments
AINA '05: Proceedings of the 19th International Conference on Advanced Information Networking and Applications - Volume 1

Load balancing for distributed servers is a common issue in many applications and has been extensively studied. Several distributed load balancing schemes have been proposed that pro-actively route individual requests to appropriate servers to best ...
An Efficient Partitioning Algorithm for Distributed Virtual Environment Systems

Distributed virtual environment (DVE) systems model and simulate the activities of thousands of entities interacting in a virtual world over a wide area network. Possible applications for DVE systems are multiplayer video games, military and industrial ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

VRST '03: Proceedings of the ACM symposium on Virtual reality software and technology

October 2003

235 pages

ISBN:1581135696

DOI:10.1145/1008653

Copyright © 2003 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

VRST03

Sponsor:

VRST03: The ACM Symposium on Virtual Reality Software and Technology 2003

October 1 - 3, 2003

Osaka, Japan

Acceptance Rates

VRST '03 Paper Acceptance Rate 28 of 81 submissions, 35%;

Overall Acceptance Rate 66 of 254 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
689
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Donkervliet JTrivedi AIosup APhanishayee AStutsman R(2020)Towards supporting millions of users in modifiable virtual environments by redesigning minecraft-like games as serverless systemsProceedings of the 12th USENIX Conference on Hot Topics in Cloud Computing10.5555/3485849.3485851(2-2)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3485849.3485851
Tsipis AKomianos VOikonomou K(2019)A Cloud Gaming Architecture Leveraging Fog for Dynamic Load Balancing in Cluster-Based MMOs2019 4th South-East Europe Design Automation, Computer Engineering, Computer Networks and Social Media Conference (SEEDA-CECNSM)10.1109/SEEDA-CECNSM.2019.8908282(1-6)Online publication date: Sep-2019
https://doi.org/10.1109/SEEDA-CECNSM.2019.8908282
Farlow STrahan J(2018)Periodic load balancing heuristics in massively multiplayer online gamesProceedings of the 13th International Conference on the Foundations of Digital Games10.1145/3235765.3235769(1-10)Online publication date: 7-Aug-2018
https://dl.acm.org/doi/10.1145/3235765.3235769
Vengerov D(2017)Dynamic adaptation of user migration policies in distributed virtual environments2017 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN.2017.7966364(4028-4035)Online publication date: May-2017
https://doi.org/10.1109/IJCNN.2017.7966364
Zhang WZhou H(2017)A dynamic mapping method for reducing migrations in DVE systems2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC)10.1109/IAEAC.2017.8054003(187-190)Online publication date: Mar-2017
https://doi.org/10.1109/IAEAC.2017.8054003
Farooq UGlauert J(2017)Faster dynamic spatial partitioning in OpenSimulatorVirtual Reality10.1007/s10055-017-0307-221:4(193-202)Online publication date: 1-Nov-2017
https://dl.acm.org/doi/10.1007/s10055-017-0307-2
Kim HPark HLee S(2014)A Hybrid Load Balancing Scheme for Games in Wireless NetworksInternational Journal of Distributed Sensor Networks10.1155/2014/38031810:5(380318)Online publication date: Jan-2014
https://doi.org/10.1155/2014/380318
Deng YLau R(2014)Dynamic load balancing in distributed virtual environments using heat diffusionACM Transactions on Multimedia Computing, Communications, and Applications10.1145/249990610:2(1-19)Online publication date: 14-Feb-2014
https://dl.acm.org/doi/10.1145/2499906
Hu HLau RHu HWah B(2014)On View Consistency in Multi-Server Distributed Virtual EnvironmentsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2013.24420:10(1428-1440)Online publication date: Oct-2014
https://doi.org/10.1109/TVCG.2013.244
Deng YHuang Z(2014)A Multi-server Approach for Large Scale Collaborative Game-Based LearningAdvances in Web-Based Learning – ICWL 201410.1007/978-3-319-09635-3_9(87-97)Online publication date: 2014
https://doi.org/10.1007/978-3-319-09635-3_9
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten