Buffer management for colored packets with deadlines

ABSTRACT

We consider buffer management of unit packets with deadlines for a multi-port device with reconfiguration overhead. The goal is to maximize the throughput of the device, i.e., the number of packets delivered by their deadline. For a single port or with free reconfiguration, the problem reduces to the well-known packets scheduling problem, where the celebrated earliest-deadline-first (EDF) strategy is optimal 1-competitive. However, EDF is not 1-competitive when there is a reconfiguration overhead. We design an online algorithm that achieves a competitive ratio of 1 - o(1) when the ratio between the minimum laxity of the packets and the number of ports tends to infinity. This is one of the rare cases where one can design an almost 1-competitive algorithm. One ingredient of our analysis, which may be interesting on its own right, is a perturbation theorem on EDF for the classical packets scheduling problem. Specifically, we show that a small perturbation in the release and deadline times cannot significantly degrade the optimal throughput. This implies that EDF is robust in the sense that its throughput is close to the optimum even when the deadlines are not precisely known.

REFERENCES

• 1: William A. Aiello , Yishay Mansour , S. Rajagopolan , Adi Rosén, Competitive queue policies for differentiated services, Journal of Algorithms, v.55 n.2, p.113-141, May 2005 [doi>10.1016/j.jalgor.2004.04.004]
• 2: N. Andelman and Y. Mansour. Competitive management of non-preemptive queues with multiple values. In Proceedings 17th International Conference on Distributed Computing, pages 166--180, 2003.
• 3: 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
• 4: N. Bansal, L. Fleischer, T. Kimbrel, M. Mahdian, B. Schieber, and M. Sviridenko. Further improvements in competitive guarantees for qos buffering. In Proceedings 31st International Colloquium on Automata, Languages and Programming, pages 196--207, 2004.
• 5: Reuven Bar-Yehuda , Jonathan Laserson, Exploiting locality: approximating sorting buffers, Journal of Discrete Algorithms, v.5 n.4, p.729-738, December, 2007 [doi>10.1016/j.jda.2006.08.001]
• 6: Y. Bartal, F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, R. Lavi, J. Sgall, and T. Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. In Proceedings 21st Annual Symposium on Theoretical Aspects of Computer Science, pages 187--198, 2004.
• 7: Marcin Bienkowski , Marek Chrobak , Christoph Dürr , Mathilde Hurand , Artur Jeż , Lukasz Jeż , Grzegorz Stachowiak, Collecting weighted items from a dynamic queue, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.1126-1135, January 04-06, 2009, New York, New York
• 8: F. Y. L. Chin, M. Chrobak, S. P. Y. Fung, W. Jawor, J. Sgall, and T. Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. J. Discrete Algorithms, 4(2):255--276, 2006.
• 9: F. Y. L. Chin and S. P. Y. Fung. Online scheduling with partial job values: Does timesharing or randomization help? Algorithmica, 37(3):149--164, 2003.
• 10: Marek Chrobak , Wojciech Jawor , Jiří Sgall , Tomáš Tichý, Improved online algorithms for buffer management in QoS switches, ACM Transactions on Algorithms (TALG), v.3 n.4, p.50-es, November 2007 [doi>10.1145/1290672.1290687]
• 11: Matthias Englert , Harald Räcke , Matthias Westermann, Reordering buffers for general metric spaces, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250871]
• 12: M. Englert, H. Röglin, and M. Westermann. Evaluation of online strategies for reordering buffers. In Proceedings 5th International Workshop on Experimental Algorithms, pages 183--194, 2006.
• 13: M. Englert and M. Westermann. Reordering buffer management for non-uniform cost models. In Proceedings 32nd International Colloquium on Automata, Languages and Programming, pages 627--638, 2005.
• 14: 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]
• 15: 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
• 16: Amos Fiat , Yishay Mansour , Uri Nadav, Competitive queue management for latency sensitive packets, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.228-237, January 20-22, 2008, San Francisco, California
• 17: I. Gamzu and D. Segev. Improved online algorithms for the sorting buffer problem. In Proceedings 24th Annual Symposium on Theoretical Aspects of Computer Science, pages 658--669, 2007.
• 18: M. R. Garey and D. S. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput., 4(4):397--411, 1975.
• 19: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 20: B. Hajek. On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In Proceedings Conference on Information Sciences and Systems, pages 434--438, 2001.
• 21: 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]
• 22: A. Kesselman, Y. Mansour, and R. van Stee. Improved competitive guarantees for qos buffering. Algorithmica, 43(1--2):63--80, 2005.
• 23: R. Khandekar and V. Pandit. Offline sorting buffers on line. In Proceedings 17th International Symposium on Algorithms and Computation, pages 81--89, 2006.
• 24: R. Khandekar and V. Pandit. Online sorting buffers on line. In Proceedings 23rd Annual Symposium on Theoretical Aspects of Computer Science, pages 584--595, 2006.
• 25: J. S. Kohrt and K. Pruhs. A constant approximation algorithm for sorting buffers. In Proceedings 6th Latin American Symposium on Theoretical Informatics, pages 193--202, 2004.
• 26: Chang Joo Lee , Onur Mutlu , Veynu Narasiman , Yale N. Patt, Prefetch-Aware DRAM Controllers, Proceedings of the 2008 41st IEEE/ACM International Symposium on Microarchitecture, p.200-209, November 08-12, 2008 [doi>10.1109/MICRO.2008.4771791]
• 27: 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
• 28: Fei Li , Jay Sethuraman , Clifford Stein, Better online buffer management, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.199-208, January 07-09, 2007, New Orleans, Louisiana
• 29: Onur Mutlu , Thomas Moscibroda, Stall-Time Fair Memory Access Scheduling for Chip Multiprocessors, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.146-160, December 01-05, 2007 [doi>10.1109/MICRO.2007.40]
• 30: Harald Räcke , Christian Sohler , Matthias Westermann, Online Scheduling for Sorting Buffers, Proceedings of the 10th Annual European Symposium on Algorithms, p.820-832, September 17-21, 2002
• 31: Scott Rixner , William J. Dally , Ujval J. Kapasi , Peter Mattson , John D. Owens, Memory access scheduling, Proceedings of the 27th annual international symposium on Computer architecture, p.128-138, June 2000, Vancouver, British Columbia, Canada
• 32: M. Schmidt. Packet buffering: Randomization beats deterministic algorithms. In Proceedings 22nd Annual Symposium on Theoretical Aspects of Computer Science, pages 293--304, 2005.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
buffer management, dram scheduling, earliest deadline first, online algorithms, packets scheduling