New Sun Labs Technical Report:

by David Vengerov

August 5, 2009- Distributed virtual environments (DVEs) have become a major trend in distributed applications. These highly interactive systems simulate a virtual world where multiple users share the same scenario. DVE systems are currently used in many different applications such as civil and military distributed training, virtual shopping malls, collaborative design, and e-learning. However, the most popular application domain for DVE systems is that of commercial multiplayer online games environments. A DVE is usually deployed on top of a network of servers (nodes), and users can be dynamically migrated between the nodes so as to balance the computational load among the servers while at the same time placing communicating users together on the same node so as to minimize communication delay. A user migration policy has a large impact on performance of the DVE, and a good policy should ideally minimize the average system response time perceived by the users.

While it is easy to develop some fixed rules about migrating users in response to an overload on some node or an extensive communication between two different nodes, such rules would not constitute the optimal policy and could perform very poorly in some environments. This paper presents an adaptive distributed user migration policy, which uses Reinforcement Learning to optimally tune itself so as to formally minimize the average system response time perceived by the users.

Performance of the self-tuning policy was compared on a simulator with the standard benchmark non-adaptive migration policy and with the optimal static user allocation policy in a variety of scenarios. The self-tuning policy was shown to greatly outperform both benchmark policies, with performance difference increasing as the network became more overloaded.

Project Darkstar has recently developed a platform that supports development of multi-player online games, which represent a very fast growing business for Sun. Each user in that platform is represented by an object and all user actions are implemented as short tasks that affect some other objects in the game (those that represent other users or some parts of the game state). The self-tuning user migration policy presented in this paper is currently being evaluated by the engineers working on Project Darkstar for possible integration into their platform.