Online algorithms for packet scheduling and buffer management

Al-Bawani, Kamal; Englert, Matthias; Unger, Walter; Rossmanith, Peter

doi:HT019044522

Online algorithms for packet scheduling and buffer management = Online-Algorithmen für Packet Scheduling und Buffer Management

Al-Bawani, Kamal

2016

Verantwortlichkeitsangabevorgelegt von M.Sc. Kamal Al-Bawani

ImpressumAachen 2016

Umfang1 Online-Ressource (viii, 90 Seiten) : Diagramme

Dissertation, RWTH Aachen University, 2016

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Englert, Matthias (Thesis advisor) ; Unger, Walter (Thesis advisor)^RWTH* ; Rossmanith, Peter (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2016-04-22

Online
URN: urn:nbn:de:hbz:82-rwth-2016-056092
URL: http://publications.rwth-aachen.de/record/660821/files/660821.pdf
URL: http://publications.rwth-aachen.de/record/660821/files/660821.pdf?subformat=pdfa

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
online algorithms (frei) ; competitive analysis (frei) ; scheduling (frei) ; buffer management (frei) ; QoS switches (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
In dieser Arbeit untersuchen wir aus einer algorithmischen Perspektive das Puffer-Management-Problem in Netzwerk-Switches. In typischen Szenarios in der Datenpaketvermittlung kommen Pakete mit verschiedenen Service-Anforderungen an den Eingangsports des Switches an, und werden in Puffern (Warteschlangen) mit begrenzter Kapazität gespeichert. Danach werden sie über die Switching-Fabric in ihre entsprechenden Ausgangsports übertragen, wo sie anderen Warteschlangen beitreten. Schließlich werden die Pakete aus dem Switch durch seine ausgehenden Verbindungen zu ihren nächsten Zielen im Netzwerk gesendet. Da die Bandbreite der ein- und ausgehenden Verbindungen und auch die Kapazitäten der Puffer beschränkt sind, kann Pufferüberlauf auftreten. Es ist in diesem Fall unvermeidlich, einige Pakete zu verwerfen. In anderen Switching-Modellen können Pakete, die verzögerungsempfindlich sind, verworfen werden, wenn sie eine bestimmte Deadline in der Warteschlange überschreiten. Wir betrachten mehrere Switching-Modelle mit dem Ziel, den Durchsatz der Switches zu maximieren. Wenn alle Pakete gleich behandelt werden, d.h. in Übereinstimmung mit dem Best-Effort-Konzept des Internet, quantifizieren wir den Durchsatz als die Anzahl der Pakete, die erfolgreich durch den Switch übertragen werden. In Netzwerken mit Quality of Service (QoS) Anforderungen werden Pakete Werte, die ihren Dienststufen entsprechen, zugeordnet. Der Durchsatz ist in diesem Fall gleich dem Gesamtwert der Pakete, die erfolgreich übertragen werden. Wir präsentieren verschiedene Algorithmen für das Puffer-Management-Problem. In der Buffering-Phase dieser Algorithmen untersuchen wir, ob ein ankommendes Paket angenommen oder abgelehnt werden soll, und ob ein bereits in der Warteschlange enthaltenes Paket verdrängt werden soll, um Platz für weitere wertvollen Pakete zu reservieren. In der Scheduling-Phase beantworten wir Fragen von der Art "welches Paket soll in einem festen Zeitschritt von einem Eingangsport zu einem Ausgangsport übertragen werden?'', und "welches Paket soll von einem Ausgangspuffer entlassen werden?''. Eine Eingabe für unsere Algorithmen ist eine endliche Folge von Paketen, die in einer "Online'' Art und Weise betrachtet werden. Das heißt, dass die Pakete nach einander über die Zeit ankommen und eine unwiderrufliche Entscheidung on the fly gemacht werden muss, bevor zukünftige Ankünfte bekannt werden. Solche Algorithmen, die unvollständige Informationen über die Zukunft bewältigen müssen und deren Entscheidungen nicht rückgängig gemacht werden können, werden Online-Algorithmen genannt. Es ist bekannt, dass Paketankunftszeiten keine spezifische Ankunftsverteilung einhalten. In der Wirklichkeit haben Pakete die Tendenz, in "Bursts'' und nicht in glatten Poisson-like-Verteilungen anzukommen. Aus diesem Grund machen wir keine vorherigen Annahmen über die Ankunftsverteilung der Pakete. Deshalb greifen wir zur Methode der Competitive-Analyse, welche die typische Worst-Case-Analyse ist, die verwendet wird, um die Leistung von Online-Algorithmen zu beurteilen. In der Competitive-Analyse vergleichen wir die Güte eines Online-Algorithmus mit der Güte eines optimalen Algorithmus, von dem angenommen wird, dass er die gesamte Eingabesequenz im Voraus kennt. Ein Online-Algorithmus heißt c-competitive, wenn für jede Eingangssequenz die Güte des optimalen Algorithmus höchstens c mal die Güte des Online-Algorithmus ist. Der Wert c wird auch als competitive ratio des Online-Algorithmus genannt. Wir beweisen obere und untere Schranken des competitive ratio von mehreren Online-Algorithmen, und zeigen, dass einige dieser Algorithmen optimal sind.

In this work, we study the problem of buffer management in network switches from an algorithmic perspective. In a typical switching scenario, packets with different service demands arrive at the input ports of the switch and are stored in buffers (queues) of limited capacity. Thereafter, they are transferred over the switching fabric to their corresponding output ports where they join other queues. Finally, packets are transmitted out of the switch through its outgoing links to their next destinations in the network.Due to limitations in the link bandwidth and buffer capacities, buffers may experience events of overflow and thus it becomes inevitable to drop some packets. In other switching models, packets that are sensitive to delay are dropped if they exceed a specific deadline inside the queue. We consider multiple models of switching with the goal of maximizing the throughput of the switch. If all packets are treated equally, i.e., corresponding to the best-effort concept of the Internet, we quantify the throughput as the number of packets that are successfully transmitted through the switch. In networks with Quality of Service (QoS) requirements, packets are assigned values that correspond to their levels of service, and the throughput in this case is equal to the total value of packets that are successfully transmitted. We present different algorithms for the problem of buffer management. In the buffering phase of these algorithms, we examine whether an arriving packet is accepted or rejected, and whether an already queued packet is preempted (dropped) to save space for more valuable packets. In the scheduling phase, we seek to answer questions of the kind "which packet to transfer from an input port to an output port in a given time step?'', and "which packet to transmit from an output buffer?''. An input instance for our algorithms is a finite sequence of packets arriving in an ``online'' manner, i.e., packets arrive one by one over time and an irrevocable decision has to be made on the fly before future arrivals become known. Such algorithms which need to cope with incomplete information about future and cannot undo their decisions are called online algorithms. It is known that packet arrivals do not adhere to any specific arrival distribution. In reality, packets tend to arrive "in bursts'' rather than in smooth Poisson-like distributions. Thus, we do not make any prior assumptions about the arrival process of packets. We therefore resort to the framework of competitive analysis which is the typical worst-case analysis used to assess the performance of online algorithms. In competitive analysis, the benefit of an online algorithm is compared to the benefit of an optimal algorithm which is assumed to know the entire input sequence in advance. An online algorithm is called c-competitive if for each input sequence, the benefit of the optimal algorithm is at most c times the benefit of the online algorithm. The value c is also called the competitive ratio of the online algorithm. We prove upper and lower bounds on the competitive ratio of several online algorithms, and show that some of these algorithms are optimal.

OpenAccess:
PDF PDF (PDFA)
(zusätzliche Dateien)