h1

h2

h3

h4

h5
h6
http://join2-wiki.gsi.de/foswiki/pub/Main/Artwork/join2_logo100x88.png

Online scheduling for buffering problems = Online Scheduling-Algorithmen zur Verwaltung von Puffern



Verantwortlichkeitsangabevorgelegt von Matthias Englert

ImpressumAachen : Publikationsserver der RWTH Aachen University 2008

Umfang98 S. : graph. Darst.


Aachen, Techn. Hochsch., Diss., 2008


Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter


Tag der mündlichen Prüfung/Habilitation
2008-05-30

Online
URN: urn:nbn:de:hbz:82-opus-24391
URL: https://publications.rwth-aachen.de/record/50173/files/Englert_Matthias.pdf

Einrichtungen

  1. Lehrstuhl für Informatik 1 (Algorithmen und Komplexität) (121110)
  2. Fachgruppe Informatik (120000)

Inhaltliche Beschreibung (Schlagwörter)
Online-Algorithmus (Genormte SW) ; Competitive analysis (Genormte SW) ; Informatik (frei) ; online algorithms (frei) ; competitive analysis (frei) ; buffer management (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
Ein Schedulingproblem besteht darin, eine Menge von Aufgaben auf eine Menge von Ressourcen zu verteilen. Mit derartigen Problemen werden wir täglich konfrontiert und häufig müssen dabei Entscheidungen ohne verlässliche Informationen über zukünftige Aufgaben getroffen werden. Dieser Informationsmangel kann zu Entscheidungen führen, die sich im Nachhinein als suboptimal erweisen. Da jedoch nicht unbedingt alle Aufgaben unmittelbar verteilt werden können oder müssen, kann es notwendig oder zumindest möglich sein, Aufgaben zunächst in Puffern zwischenzuspeichern und damit gewisse Entscheidungen hinauszuzögern. Wir beschäftigen uns damit, wie solche Puffer verwaltet werden können, um trotz eingeschränkter Informationen über zukünftige Aufgaben eine möglichst gute Verteilung der Aufgaben zu erzielen.

In a scheduling problem, tasks have to be assigned to resources in such a way that some specified objective is accomplished. Often times, tasks either can or have to be stored in a buffer before they are assigned to a resource. In these cases, a buffer management strategy has to constantly facilitate decisions as to which tasks to store in the buffer, which tasks to execute, and which tasks to delete from the buffer. If the tasks arrive over time, these decisions have to be made online, that is, without knowledge of the future. The predominant method to investigate online algorithms is the competitive analysis. An online algorithm is c-competitive if, for every input, the solution returned by the algorithm is at most by a factor of c worse than a solution given by an optimal offline algorithm. We study four different online scheduling problems, in which buffers are a crucial component, in a competitive analysis. First, we introduce and study reordering buffers, which are used to reorder a stream of tasks, requests, or jobs in such a way that they can be served more efficiently. This concept can be applied to various scheduling problems in order to improve performance. To demonstrate the power of reordering buffers and to show how they can be efficiently used, we apply reordering buffers to two exemplary scheduling problems. In the first problem, the reordering buffer is used to minimize the sum of the distances between consecutive elements in a sequence of points from a metric space. We design the first algorithm achieving a polylogarithmic competitive ratio for general metric spaces. In the second problem, the reordering buffer is used to obtain improved competitive ratios for the well-known online minimum makespan scheduling problem. For the identical machine model, we present matching upper and lower bounds on the competitive ratio which are significantly lower than the bounds for the classic online minimum makespan scheduling problem without reordering buffers. This is somewhat surprising considering that, for more than four machines, no tight bounds are known for the problem without reordering, despite the great effort that was spent on this problem. Buffers cannot only be an optional tool for improving performance for various scheduling problems, they can also be a problem-specific necessity. We investigate two different scheduling problems that are motivated by the problem of packet forwarding in network switches that have so-called Quality-of-Service (QoS) capabilities, i.e., switches which are able to treat different kind of packets with different priority. Since a network switch may not be able to instantly forward every arriving data packet, network switches are equipped with buffers to temporarily store not yet forwarded data packets. The different packet priorities in the QoS scenario are abstracted by assigning each packet a certain value which reflects its priority. A scheduling strategy is used to decide which packets from the buffers are to be sent at any given time. First, we study a scenario in which the buffers in the network switch have limited capacity and packets have to be sent in the order they arrive. Since the capacity of the outgoing link is also limited, buffer overflow events may occur. In case of a buffer overflow, packets have to be dropped and cannot be forwarded anymore. In order to avoid dropping very valuable packets, it can make sense to preemptively drop packets of lower value at a point in time where it would otherwise not be necessary to drop packets at all. The challenge is to design algorithms that drop the right packets at the right time to achieve the best possible performance. In the second scenario we study, the capacity of buffers is unbounded and packets can be sent in arbitrary order. However, each packet has a deadline by which it has to be either sent or dropped. In this model, there is a trade-off between sending packets which are to expire shortly and sending packets with large values. We completely solve both problems for the case that only two different packet values appear in the input sequence and improve the previous bounds for the general case. For the first problem variant, we study the so-called preemptive greedy strategy, which is currently the only algorithm achieving a competitive ratio below 2. We analyze this algorithm more carefully and show improved upper and lower bounds on the competitive ratio of preemptive greedy. For the second problem variant, we introduce the novel concept of suppressed packets and demonstrate the potential of this approach by, among other things, presenting an algorithm achieving the currently best known competitive ratio.

Fulltext:
Download fulltext PDF

Dokumenttyp
Dissertation / PhD Thesis

Format
online, print

Sprache
English

Externe Identnummern
HBZ: HT015612663

Interne Identnummern
RWTH-CONV-112728
Datensatz-ID: 50173

Beteiligte Länder
Germany

 GO


OpenAccess

QR Code for this record

The record appears in these collections:
Document types > Theses > Ph.D. Theses
Faculty of Mathematics, Computer Science and Natural Sciences (Fac.1) > Department of Computer Science
Publication server / Open Access
Public records
Publications database
120000
121110

 Record created 2013-01-25, last modified 2022-04-22


Fulltext:
Download fulltext PDF
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)