|
|
Online Algorithms for Packet Scheduling
Veselý, Pavel ; Sgall, Jiří (vedoucí práce) ; Stein, Clifford (oponent) ; Englert, Matthias (oponent)
V této práci studujeme rozvrhovací algoritmy pro abstraktní modely sít'ového přepínače, v nichž přicházejí pakety do bufferu přepínače, aby byly odeslány skrz výstupní port. Počet paketů přicházejících do bufferu je však příliš veliký a některé tak nemohou být odeslány. Pakety mají prioritu danou váhou a cílem algoritmu je maximalizovat propustnost systému, tedy celko- vou váhu odeslaných paketů. Algoritmus nicméně nezná pakety, které přijdou v budoucnu, a nedosáhne tedy optimální propustnosti. Proto provádíme kom- petitivní analýzu a její zjemnění, jež analyzují chování online algoritmů v nejhorších případech. V první části práce se zaměříme na jednoduchý online rozvrhovací model s pakety jednotkové délky s termíny, zvaný Bounded-Delay Packet Scheduling. Navrhneme optimální φ-kompetitivní deterministický algoritmus pro tento problém, kde φ ≈ 1.618 je zlatý řez. Algoritmus je založen na detailním roz- boru struktury optimálních rozvrhů paketů v bufferu, zvaných plány. Dále se zaměříme na semi-online algoritmy s tzv. lookaheadem, který umožňuje algoritmu vidět pakety přicházející v nejbližší budoucnosti. Ukážeme algorit- mus s lookaheadem pro instance, v nichž každý paket může být rozvrhnut pouze...
|
host ::
RSS.