Dynamic clustering in Delaunay-Based P2P networked virtual environments

Classical client/server approaches for Networked Virtual Environments (NVEs) require considerable server resources to support a large number of players. On the opposite peer-to-peer (p2p) architectures achieve the required scalability at much lower cost. The feasibility of a p2p approach to NVEs depends heavily on the fact that a given user is interested only in a small part of the virtual world. For this reason, the Delaunay network is an appealing solution, which organizes peers according to their position within the NVE. However, in a NVE players typically tend to aggregate around some attractive points. As the cost of maintenance of the Delaunay network increases with player density and velocity, some peers may see a considerable volume of maintenance traffic. To address this issue, we propose a dynamic clustering algorithm: each peer in the network monitors his cost of maintenance and triggers the creation of a cluster as soon as the volume of traffic generated exceeds a given threshold. Members of a cluster then expand their coordinates to increase their reciprocal distances. In this way, decreasing the concentration of players we achieve a diminution of the maintenance cost. To evaluate our clustering scheme we simulate a simple NVE and run an experiment in Second Life. The results we obtained show that our solution is effective in keeping the amount of maintenance traffic below a chosen threshold.