Competitive FIFO Buffer Management for Weighted Packets

摘要

Motivated by providing differentiated services on the Internet, we consider efficient online algorithms for buffer management in network switches. We study a FIFO buffering model, in which unit-length packets arrive in an online manner and each packet is associated with a value (weight) representing its priority. The order of the packets being sent should comply with the order of their arriving time. The buffer size is finite. At most one packet can be sent in each time step. Our objective is to maximize weighted throughput, defined by the total value of the packets sent. In this paper, we design competitive online FIFO buffering algorithms, where competitive ratios are used to measure online algorithms' performance against the worst-case scenarios. We first provide an online algorithm with a constant competitive ratio 2. Then, we study the experimental performance of our algorithm on real Internet packet traces and compare it with all other known FIFO online competitive algorithms. We conclude that for the same instance, the algorithms' experimental performances could be different from their competitive ratios; other factors such as packet flow characteristics and buffer sizes affect the outcome. Our algorithm outperforms other online algorithms when the buffer resource is limited.