Platten-Scheduling und stochastische Service-Garantien für multimediale Daten-Server

Abstract

In dieser Arbeit werden neuartige Algorithmen für das Platten-Scheduling in multimedialen Daten-Servern vorgestellt und ein stochastisches Modell zur Vorhersage der vom Server garantierbaren Service-Qualität entwickelt. Angenommen wird, daß die Speicherung der multimedialen Daten auf den Platten eines Disk-Arrays gemischt erfolgt. Dies bedeutet, daß sowohl kontinuierliche Daten (Audio, Video) als auch diskrete Daten (Text, Bild, Graphik) gemeinsam auf einer Platte abgelegt werden. Bedingt durch diese gemischte Datenhaltung muß jede Magnetplatte Zugriffe auf kontinuierliche und diskrete Daten verarbeiten können. Die Auswirkungen verschiedener Scheduling-Algorithmen auf die Service-Qualität beim Datenzugriff auf kontinuierliche und diskrete Daten werden experimentell evaluiert. Die Service- Qualität für kontinuierliche Daten ist hierbei durch die Störungsrate bestimmt, d.h. durch die Haüfigkeit, mit der der Server zeitweilig die U¨ bertragung des Datenstromes zum Client unterbrechen muß. Die Service-Qualität für diskrete Daten wird durch die Antwortzeit festgelegt. Grundlage für die Vorhersage der Service-Qualität bildet die stochastische Modellierung des Daten-Servers. Zu diesem Zweck wird die Verteilungsfunktion für die Zeitdauer analysiert, die für eine Menge von Plattenzugriffen benötigt wird. Hierauf aufbauend läßt sich dieWahrscheinlichkeit bestimmen, mit der eine festgelegte Störungsrate bzw. eine festgelegte Antwortzeitschranke überschritten wird. Für letzteres wird ein M/G/1-Warteschlangenmodell entwickelt, das die Verteilungsfunktion der Antwortzeit in Form der Laplace-Transformierten berechnet. Die Vorhersagen des stochastischen Modells bilden die Basis für die Konfiguration des Disk- Arrays und für die Zulassungkontrolle, mit der der Server die vereinbarte Service-Qualität garantieren kann.

This thesis presents new methods for disk scheduling in multimedia servers and derives a stochastic model to predict the quality-of-service that the server can guarantee. It is assumed that all data, i.e. continuous data (audio/video) and discrete data (text/indexes/images), resides for efficiency reasons on a shared disk-array. Thus, accesses to this data induce a mixed workload on each disk. The impact of different disk scheduling policies on the quality-of-service for both continuous and discrete data is studied, and a framework for describing various policies in terms of a few parameters is developed. The quality-of-service for continuous data is determined by the error rate, i.e. the frequency of the server temporarily suspending the delivery of data to the client. The quality-of-service for discrete data is given by the response time for discrete data requests. A stochastic model is developed based on deriving the distribution function of the service time for batched disk service under a multi-user load. Using this result it is possible to bound the tail probabilities of the error rate and the response time. The latter can be obtained using an M/G/1 queueing model that derives the Laplace transform of the response time distribution. The results from the stochastic model provide the basis for configuring the disk-array and exerting an admission control such that the server can guarantee its quality-of-service.