Greedy Algorithms for Client Assignment in Large-Scale Distributed Virtual Environments

Abstract

Distributed Virtual Environments (DVEs) such as online games, military simulations or collaborative design are currently very popular. To support large-scale DVEs, an architecture with multiple, geographically distributed servers is usually employed, and the virtual world is partitioned into multiple zones for load distribution. The client assignment problem arises when assigning the participating clients to the servers. Current approaches usually assign clients to servers based on a resource-driven approach, i.e. the only concern is not to overload the servers. This approach may degrade the interactivity of DVEs if the network delay from a client to its assigned server is large. In this paper, we formulate the client assignment problem, and propose three new algorithms to assign clients to servers in a more efficient way. The proposed algorithms are based on the greedy heuristics developed for the well-known Terminal Assignment problem. From extensive simulation studies with realistic settings, we find that even under heterogeneous environments such as the Internet where accurate input data for the assignment algorithms are usually impractical to obtain, some of the proposed algorithms are still beneficial to the performances of DVEs.