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/",
}