Lecture Notes in Computer Science, 2009, Volume 5564/2009, 265-278, DOI: 10.1007/978-3-642-02158-9_23

Improved Online Algorithms for Multiplexing Weighted Packets in Bounded Buffers

Fei Li

View Related Documents

Abstract

Motivated by providing differentiated services in the Internet, we consider online buffer management algorithms for quality-of-service network switches. We study a multi-buffer model. Packets have values and deadlines; they arrive at a switch over time. The switch consists of multiple buffers whose sizes are bounded. In each time step, only one pending packet can be sent. Our objective is to maximize the total value of the packets sent by their deadlines. We employ competitive analysis to measure an online algorithm’s performance. In this paper, we first show that the lower bound of competitive ratio of a broad family of online algorithms is 2. Then we propose a (3 + Ö3 » 4.7233 + \sqrt{3} \approx 4.723)-competitive deterministic algorithm, which is improved from the previously best-known result 9.82 (Azar and Levy. SWAT 2006).
Research is partially supported by the Seed Grant from the Office of the Vice President for Research and Economic Development at George Mason University.

Fulltext Preview

Image of the first page of the fulltext document