Better online buffer management

ABSTRACT

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 packets 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 packets 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 packets are buffered for delivery and all packets have the same processing time. The packets arrive online, and our objective is to maximize the sum of weights of those packets 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.

REFERENCES

• 1: Susanne Albers , Markus Schmidt, On the performance of greedy algorithms in packet buffering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007366]
• 2: Nir Andelman , Yishay Mansour , An Zhu, Competitive queueing policies for QoS switches, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 3: Yossi Azar , Yossi Richter, Management of multi-queue switches in QoS networks, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780556]
• 4: Yossi Azar , Yossi Richter, The zero-one principle for switching networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007369]
• 5: N. Bansal, L. K. Fleischer, T. Kimbrel, M. Mahdian, B. Schieber, and M. Sviridenko, Further Improvements in Competitive Guarantees for QoS Buffering, In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP), pages 196--207, 2004.
• 6: Y. Bartal, F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, R. Lavi, J. Sgall, and T. Tichy, Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs, In Proceedings of the 21st Symposium on Theoretical Aspects of Computer Science (STACS), pages 190--210, 2004.
• 7: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 8: M. Chrobak, W. Jawor, J. Sgall, and T. Tichy, Improved Online Algorithms for Buffer Management in QoS Switches, In Proceedings of the 12th European Symposium on Algorithms (ESA), pages 204--215, 2004.
• 9: F. Y. L. Chin and S. P. Y. Fung, Online Scheduling with Partial Job Values: Does Timesharing or Randomization Help?, Algorithmica, Volume 37(3), pages 149--164, 2003.
• 10: Matthias Englert , Matthias Westermann, Lower and upper bounds on FIFO buffer management in QoS switches, Proceedings of the 14th conference on Annual European Symposium, p.352-363, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_33]
• 11: Matthias Englert , Matthias Westermann, Considering suppressed packets improves buffer management in QoS switches, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.209-218, January 07-09, 2007, New Orleans, Louisiana
• 12: B. Hajek, On the Competitiveness of Online Scheduling of Unit-Length Packets with Hard Deadlines in Slotted Time, In Proceedings of 2001 Conference on Information Sciences and Systems (CISS), pages 434--438, 2001.
• 13: Alexander Kesselman , Zvi Lotker , Yishay Mansour , Boaz Patt-Shamir , Baruch Schieber , Maxim Sviridenko, Buffer Overflow Management in QoS Switches, SIAM Journal on Computing, v.33 n.3, p.563-583, 2004 [doi>10.1137/S0097539701399666]
• 14: A. Kesselman, Y. Mansour, and R. van Stee, Improved Competitive Guarantees for QoS Buffering, Algorithmica, Volume 43, pages 63--80, 2005.
• 15: Fei Li , Jay Sethuraman , Clifford Stein, An optimal online algorithm for packet scheduling with agreeable deadlines, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 16: Zvi Lotker , Boaz Patt-Shamir, Nearly optimal FIFO buffer management for DiffServ, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571851]
• 17: M. Schmidt, Packet Buffering: Randomization Beats Deterministic Algorithms, In Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science (STACS), pages 293--304, 2005.