A comparison of Quad-tree and Voronoi-based spatial partitioning for dynamic load balancing
Date
2014-12
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
ENGLISH ABSTRACT: Massively multi-user virtual environments (MMVEs) face scalability challenges, one being the large number of concurrent users interacting in the virtual environment (VE).
Spatial partitioning addresses this problem by distributing partitions of the VE, and their associated users, to separate servers. Users dynamically migrate between partitions as they move within the VE and server load imbalances occur when users flock to popular locations (such as cities or boss arenas).
Dynamic Load Balancing can be achieved by dynamically scaling the VE partitions and migrating users to underloaded servers. In this paper, we assume an MMVE has load balancing
and focus on comparing two spatial partitioning methods, namely Quad-trees and Voronoi diagrams, using OverSim, an extension of the OMNeT++ simulation package. We evaluate each approach using the number of messages sent between
servers, the distribution of users across servers and the number of servers in use as performance metrics. We conclude that a Voronoi based system is better in distributing the load across multiple servers, but has a greater computational cost than a Quad-tree based system.
AFRIKAANSE OPSOMMING: Geen opsomming beskikbaar
AFRIKAANSE OPSOMMING: Geen opsomming beskikbaar
Description
Please cite as follows:
Van Greunen, M. & Engelbrecht, H. A. 2014. A comparison of Quad-tree and Voronoi-based spatial partitioning for dynamic load balancing, in Proceedings of the First International Conference on the use of Mobile Informations and Communication Technology (ICT) in Africa UMICTA 2014, 9-10 December 2014, STIAS Conference Centre, Stellenbosch: Stellenbosch University, Department of Electrical & Electronic Engineering, South Africa, ISBN: 978-0-7972-1533-7.
The conference is available at http://mtn.sun.ac.za/conference2014/
See also the record http://hdl.handle.net/10019.1/95703
Van Greunen, M. & Engelbrecht, H. A. 2014. A comparison of Quad-tree and Voronoi-based spatial partitioning for dynamic load balancing, in Proceedings of the First International Conference on the use of Mobile Informations and Communication Technology (ICT) in Africa UMICTA 2014, 9-10 December 2014, STIAS Conference Centre, Stellenbosch: Stellenbosch University, Department of Electrical & Electronic Engineering, South Africa, ISBN: 978-0-7972-1533-7.
The conference is available at http://mtn.sun.ac.za/conference2014/
See also the record http://hdl.handle.net/10019.1/95703
Keywords
Massively multi-user virtual environments (MMVEs), Virtual Environment (VE), Spatial systems, Voronoi diagrams, Servers (Computers) -- Dynamic Load Balancing