Competitive Analysis of Online Algorithms for Scheduling Packets with Uniform Lifespans

Abstract

Táto práca sa zameriava na kompetetivnú analýzu online algoritmov pre plánovanie pakety s jednotnou životnosťou. Primárny dôraz bol kladený na výskum o predchádza- júcich prác. Preskúmali sme správu vyrovnávacích pamätí v sieťových prepínačoch, kde pakety sú dočasne uložené. Študovali sme deterministické aj randomizované algoritmy s dôrazom na modely, ako je bounded-delay buffer a FIFO (First In, First Out). Analy- zovali sme Greedy algoritmus pre 2 uniformé inštancie. Dokázali sme, že kompetitívný pomer pre 2-uniformné inštancie je 3 2 . Dokázali sme to využitím potenciálnej funkcie. Zo známych inštancií vieme, že tieto výsledky sú skutočne tesné. Prostredníctvom tohto výskumu sme získali hlbšie znalosti o kompetitívnej analýze online algoritmov a základné poznatky z prác mnohých výskumníkov. 1

This thesis focuses on the competitive analysis of online algorithms for scheduling packets with uniform lifespans. The primary focus was on reviewing previous work. We explored the management of buffers in network switches, where packets are stored temporarily. We studied both deterministic and randomized algorithms with attention to models such as bounded-delay buffer and FIFO (First In, First Out). We analyzed the Greedy algorithm for 2 uniform instances. We proved that the competitive ratio for 2-uniform instances is 3 2 . We proved it by using a potential function. By known instances, those proven results are indeed tight. Through this research, we gained a deeper knowledge of the competitive analysis of online algorithms and basic knowledge of previous work done by many researchers. 1