Direkt zum Inhalt | Direkt zur Navigation

Eingang zum Volltext

Lizenz

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:bsz:25-opus-58139
URL: http://www.freidok.uni-freiburg.de/volltexte/5813/


Gunia, Christian

On energy-efficient broadcasts

Über energie-effiziente Broadcasts

Dokument1.pdf (1.050 KB) (md5sum: 47d0da07b0cb26b1d257d8864deb709f)

Kurzfassung in Englisch

In this work we address three different kinds of communication problems, in which a server stores and transmits data items to a set of clients. The transmission is performed as a broadcast such that every currently listening client receives it. We call these data items henceforth pages. In any investigated scenario we require the existence of a (technical) infrastructure that supports this kind of operation and merely focus on the timing of the broadcasts. This infrastructure is modeled by a transmission channel. We analyze the energy consumption needed to obtain a predetermined quality of service at the serviced clients.

In the first scenario clients request the pages and the quality of service is measured by the sum of the experienced flow times. The flow time is the time a client waits until it has received the requested page completely. Each page is associated to an individual transfer volume that defines the amount of data needed to be transferred, in order to transmit it completely. The transmission speed of the channel is fixed and, thus, a broadcast takes a fixed amount of time and thereby consumes a fixed amount of energy. The server is provided with an energy limit that must not be exceeded. Depending on the number of stored pages and the their transfer volumes we distinguish different variants of the problem. Basically, we distinguish between the single-page and the multi-page case. After presenting offline algorithms that compute an optimal sequence of broadcasts in polynomial time, we lower bound the achievable competitive ratio for the online version by providing worst-case instances. We point out that the obtained lower bounds hold for randomized online algorithms as well. Finally, we show how to realize them by deterministic algorithms. These deterministic algorithms turn out to induce only a slight administrative and technological overhead at the clients when compared to broadcasting strategies for servers without energy saving techniques.

In the second scenario we require the clients to issue a deadline along with their request. The server must broadcast the requested page completely before the deadline in order to answer its request. Analyzing the flow time in this scenario is not meaningful as the clients upper bound the accepted flow time by providing the deadline. Instead we minimize the energy consumption needed at the server to perform the schedule. The transmission channel is speed-controlled with a convex function describing the ratio between transmission speed and consumed energy. We show that an optimal sequence of broadcasts is computable in polynomial time in the offline version for the single-page case. For the online version we derive an upper bound on the achievable competitive ratio by presenting a structurally simple algorithm for the single-page case and show that it is worst-case optimal. For the multi-page case we present lower and upper bounds on the achievable competitive ratio.

In the third scenario the push-based model is addressed where the server transmits the pages on a regular basis without explicit requests by the clients. Each page has a window length associated with that upper bounds the distance between two consecutive broadcasts of this page. The server has access to a set of speed-controlled channels and again the objective is energy minimization. We show how to achieve a constant factor approximation in polynomial time by providing offline algorithms for the single- and multi-channel case.

In the last part of this work we investigate the second scenario once more. We experimentally analyze the energy savings on request sequences taken from real-world applications. Here, we use traces recorded by web servers and derive a random model on their typical' distribution. We show that the capability to adjust the speed of every broadcast independently helps saving energy on these request sequences.


Kurzfassung in Deutsch

In dieser Arbeit befassen wir uns mit drei verschiedenen Kommunikationsproblemen. In jedem speichert ein Server verschiedene Nachrichten, die er an eine Menge von Klienten übermittelt. Diese Übermittlung wird als Broadcast durchgeführt. Somit erhält jeder empfangsbereite Klient die gesendete Nachricht. Wir gehen jeweils davon aus, dass bereits eine Infrastruktur existiert, die diese Art der Übertragung ermöglicht, und modellieren dies durch einen Übertragungskanal. Wir widmen unser Augenmerk den zeitlichen Aspekten der Broadcasts und analysieren den Energiebedarf, der notwendig ist, um eine gewisse Servicequalität bei den Klienten zu garantieren.

In dem ersten untersuchten Szenario fragen die Klienten die Nachrichten explizit an. Die Antwortzeit einer Anfrage ist die Zeit, die zwischen dem Absenden der Anfrage und der vollständigen Übermittlung der Antwort verstreicht. Wir verwenden die Summe der resultierenden Antwortzeiten als Maß der Servicequalität. Diese ist offensichtlich zu minimieren. Jede Nachricht hat ein gewisses Transfervolumen, das die Menge an Daten angibt, die gesendet werden müssen, um die Nachricht vollständig zu übertragen. Die Sendegeschwindigkeit des Übertragungskanals ist a priori festgelegt, und somit benötigt die Übermittlung einer Seite sowohl eine gewisse Zeit als auch eine gewisse Energiemenge. Der Server verfügt über eine begrenzte Menge an Energie, die dieser zur Beantwortung der Anfragen verwenden darf. Abhängig von der Anzahl an gespeicherten Nachrichten und dem Transfervolumen unterscheiden wir verschiedene Varianten dieses Problems. Zunächst präsentieren wir Offline-Algorithmen, die eine optimale Sequenz von Broadcasts in polynomieller Zeit berechnen. Anschließend beschränken wir den in der Online-Version erreichbaren kompetitiven Faktor von unten durch Angabe von Worst-Case Instanzen (auch für randomisierte Algorithmen). Schließlich zeigen wir, wie diese Schranken durch strukturell einfache und deterministische Algorithmen erreicht werden können. Diese angegebenen Algorithmen erfordern, verglichen mit Broadcast-Strategien, die keinerlei Energiesparmaßnahmen verwenden, lediglich einen geringen technologischen und administrativen Mehraufwand auf Seite der Klienten.

In dem zweiten Szenario fordern wir von den Klienten, dass sie ihre Anfrage zusätzlich um eine selbst gesetzte Frist ergänzen. Der Server hat sicherzustellen, dass die angefragte Nachricht bis zu dieser Frist dem Klienten vollständig übermittelt wurde. Die Antwortzeit in diesem Szenario zu untersuchen, erscheint wenig sinnvoll, da die Klienten die Antwortzeit, die sie für akzeptabel halten, implizit durch Angabe der Frist festlegen. Anstelle dessen untersuchen wir die Möglichkeit, den Energieverbrauch des Servers zu minimieren. Dazu geben wir dem Server die Möglichkeit, die Übertragungsgeschwindigkeit des Kanals selbstständig zu regulieren. Ferner nehmen wir an, dass die Abhängigkeit zwischen Übertragungsgeschwindigkeit und Energieverbrauch durch eine konvexe Funktion beschrieben wird. Wir zeigen, dass eine optimale Lösung erneut in Polynomialzeit berechenbar ist, falls lediglich eine Nachricht auf dem Server gespeichert wird. Für die Online-Version erhalten wir eine obere Schranke für den erreichbaren kompetitiven Faktor, indem wir einen strukturell einfachen Algorithmus angeben und zeigen, dass dieser Worst-Case optimal ist. Im Falle einer beliebigen Anzahl an gespeicherten Nachrichten geben wir untere und obere Schranken für den erreichbaren kompetitiven Faktor an.

In dem dritten Szenario widmen wir uns dem so genannten "push-based model", bei dem der Server die Nachrichten nicht auf Anfrage, sondern in regelmäßigen Abständen versendet. Jede Nachricht ist nun mit einer Fensterlänge versehen, die eine obere Schranke für den Abstand zwischen zwei aufeinander folgenden Übertragungen dieser Nachricht vorgibt. Dem Server steht zur Übertragung der Nachrichten eine Menge identischer Kanäle zur Verfügung, deren Geschwindigkeit er unabhängig voneinander regulieren kann. Auch hier ist das Ziel die Energieminimierung auf Seiten des Servers. Durch Angabe von Offline-Algorithmen sowohl für den Fall, dass nur eine Seite auf dem Server gespeichert wird, als auch für den allgemeinen Fall von mehreren gespeicherten Seiten, zeigen wir, dass eine Approximation von konstanter Güte in polynomieller Zeit erreichbar ist.

Im letzten Teil der Arbeit betrachten wir das zweitgenannte Szenario unter einem abgewandelten Gesichtspunkt erneut. Wir analysieren die erreichbare Energieeinsparung experimentell mit Hilfe von Anfragesequenzen, die auf Anwendungen der wirklichen Welt basieren. Wir verwenden Aufzeichnungen von Anfragen an verschiedene Webserver und leiten von diesen zunächst ein Zufallsmodel für "typische Anfragen" ab. Anschließend zeigen wir, dass die Möglichkeit, die Geschwindigkeit von Broadcast zu Broadcast getrennt einstellen zu können, maßgeblich zur Energieeinsparung beiträgt.


SWD-Schlagwörter: Algorithmus
Freie Schlagwörter (deutsch): Energie-Effizienz , Broadcasts
Freie Schlagwörter (englisch): Energy-Efficiency , Broadcasts , Algorithms
CCS Klassifikation F.2.2 Nonn
Institut: Institut für Informatik
Fakultät: Technische Fakultät (bisher: Fak. f. Angew. Wiss.)
DDC-Sachgruppe: Informatik
Dokumentart: Dissertation
Erstgutachter: Albers, Susanne (Prof. Dr.).
Sprache: Englisch
Tag der mündlichen Prüfung: 30.06.2008
Erstellungsjahr: 2008
Publikationsdatum: 29.09.2008
Indexliste