Competitive Analysis of Online Algorithms for Scheduling Packets with Uniform Lifespans
Matúš Mitro · Digital Repository (National Repository of Grey Literature) · 2025
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