Constructing communication subgraphs and deriving an optimal synchronization interval for distributed virtual environment systems

The author considers problems of constructing a communication subgraph and deriving an optimal synchronization interval for a distributed virtual environment system (DVE). In general, a DVE system is a distributed system which allows many clients who are located in different parts of the network to concurrently explore and interact with each other under a high resolution, 3D, graphical virtual environment. Each client in a DVE system is represented by an avatar in the virtual environment, and each avatar can move and interact freely in the virtual environment. There are many challenging issues in designing a cost-effective DVE system. The article addresses two important design issues, namely: 1) how to construct a communication subgraph which can efficiently carry traffic generated by all clients in a DVE system, and 2) how to guarantee that each participating client has the same consistent view of the virtual world. In other words, if there is an action taken by an avatar or if there is any change in the state of an object in the virtual world, every participating client will be able to view the change. To provide this consistent view, a DVE system needs to perform synchronization actions periodically, We present several algorithms for constructing a communication subgraph. In the subgraph construction, we try to reduce the consumption of network bandwidth resources or reduce the maximum delay between any two clients in a DVE system. Based on a given communication subgraph, we then derive the optimal synchronization interval so as to guarantee the view consistency among all participating clients. The derivation of the optimal synchronization interval is based on the theory of Markov chains and the fundamental matrix