Priority Scheduling for Networked Virtual Environments

Abstract

Ein Mangel an Resourcen ist ein Problem, das bei nahezu allen Virtual-Reality Applikationen ( Virtual Environments ) und Videospielen beobachtet werden kann. Die Netzwerk-Bandbreite, der Durchsatz der Graphik-Pipeline, oder die verf¨ugbaren Prozessorzyklen reichen oft nicht aus, um die Anforderungen des Systems zu erf¨ullen. Der daraus folgende Wettstreit um die Resourcen f¨uhrt zu einer massiven Beeintr¨achtigung des gesamten Systems, und beschr¨ankt dessen Skalierbarkeit. In einer Client-Server Anwendung, zum Beispiel, wird die virtuelle Welt von einem zentralen Server verwaltet, und von mit dem Server in Verbindung stehenden Clients repliziert, welche außerdem eine graphische Darstellung f¨ur den Benutzer erzeugen. Dies erfordert, daß alle Clients vom Server ¨uber s¨amtliche ¨ Anderungen in der gemeinsamen Datenbank informiert werden. Die zum Erzeugen dieser Mitteilungen ben¨otigten Prozessorzyklen, oder die zum ¨ Ubermitteln ben¨otigte Netzwerk-Bandbreite, ¨ubersteigt oft die zur Verf¨ugung stehenden Resourcen des Systems, sodaß nur eine Teilmenge der erforderlichen Daten bearbeitet werden kann. Dies f¨uhrt zu einer Aufsummierung von Fehlern, z.B. Sichtbarkeitsfehler, welche auf Positions¨anderungen der sich bewegenden Objekte beruhen. Diese Dissertation pr¨asentiert einen Scheduling-Algorithmus, genannt Priority Round-Robin (PRR) Scheduling, welcher zur Verwaltung von um Systemresourcen konkurrierende Objekte entwickelt wurde. PRR weist s¨amtlichen Objekten eine Priorit¨at zu, welche anhand einer frei definierbaren Fehlermetrik bestimmt wird, und versucht den Gesamtfehler des Systems zu minimieren. Trotzdem ist der Aufwand des Algorithmus nur von der Anzahl der auszuw ¨ahlenden Objekte abh¨angig, und nicht von der Gesamtanzahl der Objekte ( output sensitive ). Außerdem garantiert der Algorithmus, daß alle Elemente mindestens einmal innerhalb einer gewissen Zeitspanne ausgew¨ahlt werden, was die Gefahr einer Starvation minimiert. Durch die frei definierbare Fehlermetrik kann PRR in nahezu allen Situationen eingesetzt werden, in denen es zu Engp¨assen bei der Zuteilung von Resourcen kommt, und durch die output sensitivity des Algorithmus wird die Konstruktion von skalierbaren Systemen wesentlich erleichtert. PRR ist in der Lage, den durch Resource-Engp¨asse erzeugten Fehler stufenlos zu minimieren, und passt sich laufend an dynamische Situationen an. - The problem of resource bottlenecks is encountered in almost any distributed virtual environment or networked game. Whenever the demand for resources such as network bandwidth, the graphics pipeline, or processing power exceeds their availability, the resulting competition for the resources leads to a degradation of the system s performance. In a typical client-server setup, for example, 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. The computational power needed to select the messages to transmit to each client, or the network bandwidth limitations often allow only a subset of the update messages to be transmitted to the clients this leads to a performance degradation and an accumulation of errors, e.g. a visual error based on the positional displacement of the moving objects. This thesis presents a scheduling algorithm, developed to manage the objects competing for system resources, that is able to achieve a graceful degradation of the system s performance, while retaining an output sensitive behavior and being immune to starvation. This algorithm, called Priority Round-Robin (PRR) scheduling, enforces priorities based on a freely definable error metric, trying to minimize the overall error. The output sensitivity is a crucial requirement for the construction of scalable systems, and the freely definable error metric makes it suitable to be employed whenever objects compete for system resources, in client-server and peer-to-peer architectures as well. Therefore Priority Round-Robin scheduling is a substantial contribution to the development of distributed virtual environments and networked online-games.