Optimal assignment of distributed servers to virtual partitionsfor the provision of immersive voice communicationin massively multiplayer games

This paper investigates the assignment of audio mixing operations to a geographically distributed set of servers to provide an immersive voice communication environment for massively multi-player online games. The immersive voice communication service enables each avatar to hear a spatially accurate audio mix of the conversations in its hearing range. There are three primary delivery architectures for this service, namely, peer-to-peer, central server, and distributed servers. We focus on a distributed server architecture, which partitions the virtual world into regions or locales and then assigns the computation associated with the creation of audio scenes for all avatars in each locale to a server. Our aim is to find the optimal way to partition the virtual world into locales and then choose the locale servers in such a way that reduces the total delay perceived by all avatars.We have produced a mathematical formulation for the optimal partitioning and server assignment and developed a heuristics approach based on a graph algorithm. We have developed a simulation environment that creates both the physical world (geographic distribution of participants and the Internet topology model) and the virtual world (distribution of avatars based on different avatar aggregation behaviors). We have solved the problem exactly as well as using the heuristics for a range of simulated virtual and physical worlds. In many cases, the heuristics results were within 5% of the optimal. Our algorithms and simulation study will be of benefit to future immersive voice communication service providers in the design of a cost effective delivery architecture for this service.