Information

  • Publication Type: Technical Report
  • Workgroup(s)/Project(s): not specified
  • Date: April 2000
  • Number: TR-186-2-00-09
  • Keywords: Visibility, Scheduling, Distributed Systems, Networking, Virtual Environments

Abstract

The problem of network bandwidth limitations is encountered in almost any distributed virtual environment or networked game. In a typical client-server setup, where the virtual world is managed by a server and replicated by connected clients which visualize the scene, the server must repeatedly transmit update messages to the clients. By employing visibility information, the number of messages transmitted over the network can be reduced by sending each client only update messages for objects which are visible from the viewpoint of the client. A naïve approach requires to examine visibility between pairs of objects and leads to a quadratic effort in the number of objects, substantially affecting the scalability of such environments. This paper presents a technique that allows the server to manage the transmission of update messages for each client with a constant overhead, reducing overall computational cost to a linear effort. We show how the server can employ visibility information to schedule all objects using the Priority Round-Robin algorithm. This algorithm is further enhanced with activity monitoring that provides a graceful degradation of the system's performance, even if the behavior of objects is unpredictable. This makes the algorithm suited to schedule update messages regarding server-controlled objects as well as user-controlled avatars.

Additional Files and Images

Weblinks

No further information available.

BibTeX

@techreport{Faisst-2000-VPRR,
  title =      "Scheduling for Very Large Virtual Environments and Networked
               Games Using Visibility and Priorities",
  author =     "Christian Faisstnauer and Dieter Schmalstieg and Werner
               Purgathofer",
  year =       "2000",
  abstract =   "The problem of network bandwidth limitations is encountered
               in almost any distributed virtual environment or networked
               game. In a typical client-server setup, where the virtual
               world is managed by a server and replicated by connected
               clients which visualize the scene, the server must
               repeatedly transmit update messages to the clients. By
               employing visibility information, the number of messages
               transmitted over the network can be reduced by sending each
               client only update messages for objects which are visible
               from the viewpoint of the client. A naïve approach requires
               to examine visibility between pairs of objects and leads to
               a quadratic effort in the number of objects, substantially
               affecting the scalability of such environments. This paper
               presents a technique that allows the server to manage the
               transmission of update messages for each client with a
               constant overhead, reducing overall computational cost to a
               linear effort. We show how the server can employ visibility
               information to schedule all objects using the Priority
               Round-Robin algorithm. This algorithm is further enhanced
               with activity monitoring that provides a graceful
               degradation of the system's performance, even if the
               behavior of objects is unpredictable. This makes the
               algorithm suited to schedule update messages regarding
               server-controlled objects as well as user-controlled
               avatars.",
  month =      apr,
  number =     "TR-186-2-00-09",
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  institution = "Institute of Computer Graphics and Algorithms, Vienna
               University of Technology ",
  note =       "human contact: technical-report@cg.tuwien.ac.at",
  keywords =   "Visibility, Scheduling, Distributed Systems, Networking,
               Virtual Environments",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2000/Faisst-2000-VPRR/",
}