Prediction-based concurrency control for a large scale networked virtual environment supporting various navigation speeds

ABSTRACT

Shared sense of a virtual world is often enhanced by replicating the information at each user's site since replication provides acceptable interactive performance, especially when users are geographically distributed over large networks like the Internet. However, multiple concurrent updates may lead to inconsistent views among replicas. Therefore concurrency control is a key factor to maintaining a consistent state among replicas. We proposed a scalable prediction-based scheme in which an ownership request is multicasted to only the users surrounding a target entity. In our previous work, we assumed that all the users navigate a virtual world with a single speed. It, however, is quite common in a networked virtual environment like a network game that users are allowed to change their navigation speed as they interact with a virtual world for adding more realism. This paper proposes an enhancement to support users with various speeds. The enhanced scheme allows as many Entity Radii as the number of different speed and allocates a separate queue for users of each speed. Each queue is examined in parallel to predict the next owner candidate and among the selected candidates is chosen the final candidate, which has a minimum predicted collision time. It contributes to the timely advanced transfer of ownership by using appropriate Entity Radius based on a user's speed, fair granting of ownership by reducing the interference between users with different speed and latency, and high prediction accuracy by reducing the redundant ownership transfer.

REFERENCES

• 1: Sumeer Bhola , Guruduth Banavar , Mustaque Ahamad, Responsiveness and consistency tradeoffs in interactive groupware, Proceedings of the 1998 ACM conference on Computer supported cooperative work, p.79-88, November 14-18, 1998, Seattle, Washington, United States [doi>10.1145/289444.331531]
• 2: Olof Hagsand, Interactive Multiuser VEs in the DIVE System, IEEE MultiMedia, v.3 n.1, p.30-39, January 1996 [doi>10.1109/93.486702]
• 3: Rodger Lea , Yasuaki Honda , Kouichi Matsuda , Olof Hagsand , Marten Stenius, Issues in the design of a scalable shared virtual environment for the Internet, Proceedings of the 30th Hawaii International Conference on System Sciences: Software Technology and Architecture, p.653, January 03-06, 1997
• 4: D. Lee, J. Yang, C. Yu, and S.J. Hyun, "Entity-Centric Scalable Concurrency Control for Distributed Interactive Applications," IEEE IPCCC'00, February 2000.
• 5: J. Leigh, A. Johnson, T. DeFanti, "CAVERN: A Distributed Architecture for Supporting Scalable Persistence and Interoperability in Collaborative Virtual Environments," Journal of Virtual Reality Research, Development and Applications, the Virtual Reality Society, Vol. 2.2, 1997, pp. 217-237.
• 6: Michael R. Macedonia , Michael J. Zyda, A Taxonomy for Networked Virtual Environments, IEEE MultiMedia, v.4 n.1, p.48-56, January 1997 [doi>10.1109/93.580395]
• 7: D. Roberts, A. Richardson, P. Sharkey, and T. Lake, "Optimising Exchange of Attributed Ownership in the DMSO RTI," SISO'98
• 8: D. Roberts, P. Sharkey, and P. Sandoz, "A Real-time, Predictive Architecture for Distributed Virtual Reality," Proc. 1st ACM Siggraph Workshop Simulation & Interaction in Virtual Environments, Des Monies, Iowa, pp. 279-288, July 1995.
• 9: P. Sandoz, P. Sharkey, and D. Roberts, "Collision prediction of a moving object within a virtual world," VR World '96, February 13-15th, Stuttgart, Germany
• 10: G. Singh, L. Serra, W. Png, and H. Ng, "BrickNet: A Software Toolkit for Network-Based Virtual Worlds," Presence, MIT Press, Vol. 3, No. 1, 1994, pp. 19-34.
• 11: Sandeep Singhal , Michael Zyda, Networked virtual environments: design and implementation, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1999
• 12: Martin R. Stytz, Distributed Virtual Environments, IEEE Computer Graphics and Applications, v.16 n.3, p.19-31, May 1996 [doi>10.1109/38.491182]
• 13: Un-Jae Sung , Jae-Heon Yang , Kwang-Yun Wohn, Concurrency Control in CIAO, Proceedings of the IEEE Virtual Reality, p.22, March 13-17, 1999
• 14: Richard C. Waters , David B. Anderson , Derek L. Schwenke, Design of the Interactive Sharing Transfer Protocol, Proceedings of the 6th Workshop on Enabling Technologies on Infrastructure for Collaborative Enterprises, p.140-147, June 18-20, 1997
• 15: Jeonghwa Yang , Dongman Lee, Scalable Prediction Based Concurrency Control for Distributed Virtual Environments, Proceedings of the IEEE Virtual Reality 2000 Conference, p.151, March 18-22, 2000

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Internet (e.g., TCP/IP)

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Concurrency
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.1 Multimedia Information Systems
          Subjects: Artificial, augmented, and virtual realities
      H.5.3 Group and Organization Interfaces
          Subjects: Synchronous interaction

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.2 Graphics Systems
          Subjects: Distributed/network graphics
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Virtual reality

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
advance ownership request and transfer, concurrency control, prediction, entity radius, generality, scalability, various navigation speed