Fairness Analysis in Competitive FIFO Buffer Management

Motivated by providing differentiated services on the Internet, we consider efficient algorithms for buffer management in quality-of-service (QoS) routers. We study a FIFO buffering model with fairness constraint, in which packets have values to represent their priorities. The order of packets being sent complies with the order of their arriving time. Fairness is enforced such that the dropping rate of a higher- priority traffic class should not be much higher than that of a lower-priority traffic class by a factor of their values´ ratio. Our objective is to maximize the total value of the packets sent. In this paper, we design both offline and online fair FIFO buffering algorithms. We first give a polynomial- time optimal offline algorithm. Then we discuss the fairness of a family of online algorithms and prove that all previously developed FIFO buffering algorithms do not guarantee fairness. For online algorithms, we use competitiveness to measure their performance against the worst-case scenarios. At last, we provide a fair online algorithm with a constant competitive ratio for the two traffic classes model. Our online algorithm is the first attempt to address the fairness concern in a competitive FIFO queue. It safeguards QoS guarantees and makes no stochastic assumptions on the input packet sequences.