Better online buffer management
Fei Li, Jay Sethuraman, Clifford Stein · Symposium on Discrete Algorithms · 2007
As the Internet becomes more mature, there is a realization that improving the performance of routers has the potential to substantially improve Internet performance in general. Currently, most routers forward in a First-In-First-Out (FIFO) order. However, the diversity of applications supported by modern IP-based networks has resulted in unpredictable packet flows, and heterogeneous network traffic. Thus, it is becoming more reasonable to consider differentiating between different types of packets, and perhaps to consider allowing to specify a deadline by which it must be processed. These issues have made buffer management at routers a critical issue in providing effective quality of service to the various applications that use the network.In this paper, we study an online problem in which each packet is described by its discrete arrival time, non-negative weight and discrete deadline; arriving are buffered for delivery and all have the same processing time. The arrive online, and our objective is to maximize the sum of weights of those that are sent by their deadlines. We describe an online deterministic algorithm with a competitive ratio of 1.854, improving the best previous known competitive ratio of 1.939 (Bartal et al. STACS 2004).The algorithmic framework we use has several interesting features. First, we do not use a potential function. Instead, after each step we modify the adversary's buffer. Second, we introduce dummy packets to facilitate the decision making.