Use of dynamic bounded regions to improve the scalability of decentralised online environments

Abstract

In a decentralised multi-user online virtual environment, object responsibility is efficiently allocated to a controlling peer. The virtual environment is divided into a plurality of cells, and control of each cell is allocated to a responsible peer. Each responsible peer participates in a distributed hash table (DHT) to effect integration of the cells to effect the virtual environment. When a communications and processing load on the responsible peer controlling a cell exceeds a threshold, a second peer creates and takes control responsibility for an object comprising a bounded interest management region covering a region of load. Within the bounded interest management region, objects are removed or de-associated from the associated cell and instead associated with the bounded interest management region.

1 . A method for efficiently allocating object responsibility to a controlling peer in a decentralized multi-user online virtual environment, the method comprising:
 dividing the virtual environment into a plurality of cells, and allocating control of each cell to a responsible peer, each responsible peer participating in a distributed hash table (DHT) to effect integration of the cells to effect the virtual environment;   upon a communications and processing load on the responsible peer controlling a cell exceeding a threshold, a second peer creating and taking control responsibility for an object comprising a bounded interest management region covering a region of load; and   within the bounded interest management region, removing objects from the associated cell and associating them with the bounded interest management region.   
     
     
         2 . The method of  claim 1  wherein the bounded interest management (IM) region is configured to contain all objects in the load region, so as to reduce network traffic associated with DHT redundancy. 
     
     
         3 . The method of  claim 1  wherein the size of the bounded IM region is altered as the region of load changes size over time. 
     
     
         4 . The method of  claim 1  wherein the location of the bounded IM region is altered as objects within the region of load move over time. 
     
     
         5 . The method of  claim 1  further providing for calving off of a second bounded IM region when objects within a first established IM region disperse beyond a maximum region size threshold. 
     
     
         6 . The method of  claim 1  wherein two or more bounded IM regions which come into proximity are merged. 
     
     
         7 . The method of  claim 1  wherein in the event of failure of a bounded IM region, associated objects are re-associated directly with the DHT. 
     
     
         8 . The method of  claim 1  wherein the decentralized multi-user online virtual environment is a massively multiplayer online game (MMOG). 
     
     
         9 . A computer program product comprising computer program code means to make a computer execute a procedure for efficiently allocating object responsibility to a controlling peer in a decentralized multi-user online virtual environment, the computer program product comprising:
 computer program code means for dividing the virtual environment into a plurality of cells, and for allocating control of each cell to a responsible peer, each responsible peer participating in a distributed hash table (DHT) to effect integration of the cells to effect the virtual environment;   computer program code means for determining whether a communications and processing load on the responsible peer controlling a cell has exceeded a threshold, and if so causing a second peer to create and take control responsibility for an object comprising a bounded interest management region covering a region of load; and   computer program code means for removing objects within the bounded interest management region from the associated cell and associating them with the bounded interest management region.   
     
     
         10 . The computer program product of  claim 9  wherein the bounded interest management (IM) region is configured to contain all objects in the load region, so as to reduce network traffic associated with DHT redundancy. 
     
     
         11 . The computer program product of  claim 9  wherein the size of the bounded IM region is altered as the region of load changes size over time. 
     
     
         12 . The computer program product of  claim 9  wherein the location of the bounded IM region is altered as objects within the region of load move over time. 
     
     
         13 . The computer program product of  claim 9  further providing for calving off of a second bounded IM region when objects within a first established IM region disperse beyond a maximum region size threshold. 
     
     
         14 . The computer program product of  claim 9  wherein two or more bounded IM regions which come into proximity are merged. 
     
     
         15 . The computer program product of  claim 9  wherein in the event of failure of a bounded IM region, associated objects are re-associated directly with the DHT. 
     
     
         16 . The computer program product of  claim 9  wherein the decentralised multi-user online virtual environment is a massively multiplayer online game (MMOG). 
     
     
         17 . A system comprised of a plurality of network nodes configured to execute the method of  claim 1 . 
     
     
         18 . A development platform software application enabling game developers to design multi-player online games in which object responsibility is allocated in accordance with the method of  claim 1 .