Michael H. Goldwasser
Skip Abstract Section
Abstract
Over the past decade, there has been great interest in the study of buffer management policies in the context of packet transmission for network switches. In a typical model, a switch receives packets on one or more input ports, with each packet having a designated output port through which it should be transmitted. An online policy must consider bandwidth limits on the rate of transmission, memory constraints impacting the buffering of packets within a switch, and variations in packet properties used to differentiate quality of service. With so many constraints, a switch may not be able to deliver all packets, in which case some will be dropped
In the online algorithms community, researchers have used competitive analysis to evaluate the quality of an online policy in maximizing the value of those packets it is able to transmit. In this article, we provide a detailed survey of the field, describing various models of the problem that have been studied, and summarizing the known results.
- Baruch Awerbuch, Yair Bartal, Amos Fiat, and Adi Ros'en. Competitive non-preemptive call control. In Proc. Fifth Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 312--320, Arlington, Virginia, January 1994. Google Scholar
Digital Library
- Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, and Prasad Raghavendra. Buffer management for colored packets with deadliens. In Friedhelm Meyer auf der Heide and Michael A. Bender, editors, Proc. 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 319--327, Calgary, Alberta, Cananda, August 2009. Google ScholarDigital Library
- Susanne Albers and Tobias Jacobs. An experimental study of new and known online packet buffering algorithms. In Lars Arge and Michael Hoffmann, editors, Proc. 15th European Symp. on Algorithms (ESA), volume 4698 of Lecture Notes in Computer Science, pages 754--765, Eilat, Israel, October 2007. Springer-Verlag. Google ScholarDigital Library
- Susanne Albers and Tobias Jacobs. An experimental study of new and known online packet buffering algorithms. Algorithmica, 2010.Google ScholarCross Ref
- William Aiello, Alex Kesselman, and Yishay Mansour. Competitive buffer management for shared-memory switches. ACM Trans. on Algorithms, 5(1), 2008. Google ScholarDigital Library
- Yossi Azar and Arik Litichevskey. Maximizing throughput in multi-queue switches. In Susanne Albers and Tomasz Radzik, editors, Proc. 12th European Symp. on Algorithms (ESA), volume 3221 of Lecture Notes in Computer Science, pages 53--64, Bergen, Norway, September 2004. Springer-Verlag.Google Scholar
- Yossi Azar and Nir Levy. Multiplexing packets with arbitrary deadlines in bounded buffers. In Lars Arge and Rusins Freivalds, editors, Proc. 10th Scandinavian Workshop on Algorithm Theory (SWAT), volume 4059 of Lecture Notes in Computer Science, pages 5--16, Riga, Latvia, July 2006. Springer-Verlag. Google ScholarDigital Library
- Yossi Azar and Arik Litichevskey. Maximizing throughput in multi-queue switches. Algorithmica, 45(1):69--90, 2006.Google ScholarDigital Library
- Nir Andelman and Yishay Mansour. Competitive management of non-preemptive queues with multiple values. In Faith Ellen Fich, editor, Proc. 17th Int. Conf. on Distributed Computing (DISC), volume 2848 of Lecture Notes in Computer Science, pages 166--180, Sorento, Italy, October 2003. Springer-Verlag.Google Scholar
- William A. Aiello, Yishay Mansour, S. Rajagopolan, and Adi Rosén. Competitive queue policies for differentiated services. In Proc. Nineteenth IEEE Conf. on Computer Communications (INFOCOM), volume 2, pages 431--440, Tel-Aviv, Israel, March 2000.Google ScholarCross Ref
- William A. Aiello, Yishay Mansour, S. Rajagopolan, and Adi Rosén. Competitive queue policies for differentiated services. J. Algorithms, 55(2):113--141, May 2005. Google ScholarDigital Library
- Nir Andelman, Yishay Mansour, and An Zhu. Competitive queueing policies for QoS switches. In Proc. 14th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 761--770, Baltimore, Maryland, January 2003. Google ScholarDigital Library
- Nir Andelman. Randomized queue management for DiffServ. In Phillip B. Gibbons and Paul G. Spirakis, editors, Proc. 17th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 1--10, Las Vegas, Nevada, July 2005. Google ScholarDigital Library
- William Aiello, Rafail Ostrovsky, Eyal Kushilevitz, and Adi Rosén. Dynamic routing on networks with fixed-sized buffers. In Proc. 14th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 431--440, Baltimore, Maryland, January 2003. Google ScholarDigital Library
- Yossi Azar and Yossi Richter. Management of multi-queue switches in QoS networks. In Proc. 35th ACM Symp. on Theory of Computing (STOC), pages 82--89, San Diego, California, June 2003. Google ScholarDigital Library
- Yossi Azar and Yossi Richter. An improved algorithm for CIOQ switches. In Susanne Albers and Tomasz Radzik, editors, Proc. 12th European Symp. on Algorithms (ESA), volume 3221 of Lecture Notes in Computer Science, pages 65--76, Bergen, Norway, September 2004. Springer-Verlag.Google Scholar
- Yossi Azar and Yossi Richter. The zero-one principle for switching networks. In László Babai, editor, Proc. 36th ACM Symp. on Theory of Computing (STOC), pages 64--71, Chicago, Illinois, June 2004. Google ScholarDigital Library
- Yossi Azar and Yossi Richter. Management of multi-queue switches in QoS networks. Algorithmica, 43(1-2):81--96, 2005.Google ScholarDigital Library
- Yossi Azar and Yossi Richter. An improved algorithm for CIOQ switches. ACM Trans. on Algorithms, 2(4):640--660, 2006. Google ScholarDigital Library
- Susanne Albers and Markus Schmidt. On the performance of greedy algorithms in packet buffering. In László Babai, editor, Proc. 36th ACM Symp. on Theory of Computing (STOC), pages 35--44, Chicago, Illinois, June 2004. Google ScholarDigital Library
- Susanne Albers and Markus Schmidt. On the performance of greedy algorithms in packet buffering. SIAM Journal on Computing, 35(2):278--304, 2005. Google ScholarDigital Library
- Yossi Azar. Online packet switching. In Giuseppe Persiano and Roberto Solis-Oba, editors, Proc. Second Workshop on Approximation and Online Algorithms (WAOA), volume 3351 of Lecture Notes in Computer Science, pages 1--5, Bergen, Norway, September 2004. Springer-Verlag. Google ScholarDigital Library
- Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jiří Sgall, and Tomáš Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. In Volker Diekert and Michel Habib, editors, Proc. 21st ACM Symp. on Theoretical Aspects of Computer Science (STACS), volume 2996 of Lecture Notes in Computer Science, pages 187¿198, Montpellier, France, March 2004. Springer-Verlag.Google Scholar
- Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jeż, Lukasz Jeż, and Grzegorz Stachowiak. Collecting weighted items from a dynamic queue. In Proc. 20th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 1126--1135, New York, New York, January 2009. Google ScholarDigital Library
- Marcin Bienkowski, Marek Chrobak, and Lukasz Jeż. Randomized algorithms for buffer management with 2-bounded delay. In Evripidis Bampis and Martin Skutella, editors, Proc. Sixth Workshop on Approximation and Online Algorithms (WAOA), Lecture Notes in Computer Science, pages 92--104, Germany, September 2008. Springer-Verlag.Google Scholar
- Allan Borodin and Ran El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, New York, 1998. Google ScholarDigital Library
- Nikhil Bansal, Lisa K. Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, and Maxim Sviridenko. Further improvements in competitive guarantees for QoS buffering. In Josep Díaz, Juhani Karhumäki, Arto Lepistö, and Donald Sannella, editors, Proc. 31st Int. Colloquium on Automata, Languages and Programming (ICALP), volume 3142 of Lecture Notes in Computer Science, pages 196--207, Turku, Finland, July 2004. Springer-Verlag.Google Scholar
- Amotz Bar-Noy, Ari Freund, Shimon Landa, and Joseph (Seffi) Naor. Competitive on-line switching policies. In Proc. 13th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 525--534, San Francisco, California, January 2002. Google ScholarDigital Library
- Amotz Bar-Noy, Ari Freund, Shimon Landa, and Joseph (Seffi) Naor. Competitive on-line switching policies. Algorithmica, 36(3):225--247, 2003.Google ScholarDigital Library
- Marcin Bienkowski and Aleksander Mądry. Geometric aspects of online packet buffering: An optimal randomized algorithm for two buffers. In Eduardo Sany Laber, Claudson F. Bornstein, Loana Tito Nogueira, and Luebio Fario, editors, Proc. 8th Latin American Symp. on Theoretical Informatics (LATIN), volume 4957 of Lecture Notes in Computer Science, pages 252--263, Búzios, Brazil, April 2008. Springer-Verlag. Google ScholarDigital Library
- Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Jiří Sgall, and Tomáš Tichý. Online competitive algorithms for maximizing weighted throughput of unit jobs. J. Discrete Algorithms, 4(2):255--276, 2006.Google ScholarDigital Library
- Francis Y. L. Chin and Stanley P. Y. Fung. Online scheduling for partial job values: Does timesharing or randomization help? Algorithmica, 37:149--164, 2003.Google ScholarDigital Library
- Marek Chrobak. Online algorithms column 13. SIGACT News, 39(3):96--121, September 2008. Google ScholarDigital Library
- Marek Chrobak, Wojciech Jawor, Jiří Sgall, and Tomáš Tichý. Improved online algorithms for buffer management in QoS switches. In Susanne Albers and Tomasz Radzik, editors, Proc. 12th European Symp. on Algorithms (ESA), volume 3221 of Lecture Notes in Computer Science, pages 204--215, Bergen, Norway, September 2004. Springer-Verlag.Google Scholar
- Marek Chrobak, Wojciech Jawor, Jiří Sgall, and Tomáš Tichý. Improved online algorithms for buffer management in QoS switches. ACM Trans. on Algorithms, 3(4), 2007. Google ScholarDigital Library
- Matthias Englert. Online Scheduling for Buffering Problems. PhD thesis, RWTH Aachen University, May 2008.Google Scholar
- Leah Epstein and Rob van Stee. Buffer management problems. SIGACT News, 35(3):58--66, 2004.Google ScholarDigital Library
- Matthias Englert and Matthias Westermann. Lower and upper bounds on FIFO buffer management in QoS switches. In Yossi Azar and Thomas Erlebach, editors, Proc. 14th European Symp. on Algorithms (ESA), volume 4168 of Lecture Notes in Computer Science, pages 352--363, Zurich, Switzerland, September 2006. Springer-Verlag. Google ScholarDigital Library
- Matthias Englert and Matthias Westermann. Considering suppressed packets improves buffer management in QoS switches. In Proc. 18th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 209--218, New Orleans, Louisiana, January 2007. Google ScholarDigital Library
- Matthias Englert and Matthias Westermann. Lower and upper bounds on FIFO buffer management in QoS switches. Algorithmica, 53(4):523--548, April 2009.Google ScholarCross Ref
- Amos Fiat, Yishay Mansour, and Uri Nadav. Competitive queue management for latency sensitive packets. In Proc. 19th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 228--237, San Francisco, California, January 2008. Google ScholarDigital Library
- Stanley P. Y. Fung. Bounded delay packet scheduling in a bounded buffer. Technical Report cs.DS/0907.2741, arXiv.org, July 2009.Google Scholar
- Eyal Gordon and Adi Rosén. Competitive weighted throughput analysis of greedy protocols on DAGs. In Proc. 24th ACM Symp. on Principles of Distributed Computing (PODC), pages 227--236, Las Vegas, Nevada, July 2005. Google ScholarDigital Library
- B. Hajek. On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In Proc. 35th Conf. in Information Sciences and Systems (CISS), pages 434--438, Baltimore, Maryland, March 2001.Google Scholar
- Ellen L. Hahne, Alexander Kesselman, and Yishay Mansour. Competitive buffer management for shared-memory switches. In Proc. Thirteenth ACM Symp. on Parallel Algorithms and Architectures (SPAA), pages 53--58, Heraklion, Crete, Greece, July 2001. Google ScholarDigital Library
- Toshiya Itoh and Noriyuki Takahashi. Competitive analysis of multi-queue preemptive QoS algorithms for general priorities. IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, E89-A(5):1186--1197, 2006. Google ScholarDigital Library
- Wojciech Jawor. Three dozen papers on online algorithms. SIGACT News, 36(1):71--85, 2005. Google ScholarDigital Library
- Lukasz Jeż. Randomised buffer management with bounded delay against adaptive adversary. CoRR, abs/0907.2050, 2009.Google Scholar
- Jan Jeżabek. Increasing machine speed in on-line scheduling of weighted unit-length jobs in slotted time. In Proc. 35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 5404 of Lecture Notes in Computer Science, pages 329--340, Špindleruv Mlýn, January 2009. Springer-Verlag. Google ScholarDigital Library
- Jan Jeżabek. Resource augmentation for QoS buffer management with agreeable deadlines. (unpublished), 2009.Google Scholar
- Lukasz Jeż. A 4/3-competitive randomised algorithm for online scheduling of packets with agreeable deadlines. In Jean-Yves Marion and Thomas Schwentick, editors, Proc. 27th ACM Symp. on Theoretical Aspects of Computer Science (STACS), Dagstuhl Seminar Proceedings, Nancy, France, March 2010. to appear.Google Scholar
- Jae-Hoon Kim. Optimal buffer management via resource augmentation. In Proc. 15th Annual Int. Symp. on Algorithms and Computation (ISAAC), volume 3341 of Lecture Notes in Computer Science, pages 618--628, Hong Kong, China, December 2004. Springer-Verlag. Google ScholarDigital Library
- Tracy Kimbrel. A simple proof of the 2-competitiveness of the greedy FIFO buffering algorithm. Technical Report RC23272, IBM Research, 2004.Google Scholar
- Alex Kesselman, Kirill Kogan, and Michael Segal. Best effort and priority queuing policies for buffered crossbar switches. In Proc. 15th Int. Colloqium on Structural Information and Communication Complexity (SIROCCO), volume 5058 of Lecture Notes in Computer Science, pages 170--184, Villars-sur-Ollon, Switzerland, June 2008. Springer-Verlag. Google ScholarDigital Library
- Alex Kesselman, Kirill Kogan, and Michael Segal. Improved competitive performance bounds for CIOQ switches. In Dan Halperin and Kurt Mehlhorn, editors, Proc. 16th European Symp. on Algorithms (ESA), volume 5193 of Lecture Notes in Computer Science, pages 577--588, Karlsruhe, Germany, September 2008. Springer-Verlag. Google ScholarDigital Library
- Alex Kesselman, Kirill Kogan, and Michael Segal. Packet mode and QoS algorithms for buffered crossbar switches with FIFO queueing. In Proc. 27th ACM Symp. on Principles of Distributed Computing (PODC), pages 335--344, Toronto, Canada, August 2008. Google ScholarDigital Library
- Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boal Patt-Shamir, Baruch Schieber, and Maxim Sviridenko. Buffer overflow management in QoS switches. In Proc. 33rd ACM Symp. on Theory of Computing (STOC), pages 520--529, Crete, Greece, July 2001. Google ScholarDigital Library
- Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boal Patt-Shamir, Baruch Schieber, and Maxim Sviridenko. Buffer overflow management in QoS switches. SIAM Journal on Computing, 33(3):563--583, 2004. Google ScholarDigital Library
- Alexander Kesselman and Yishay Mansour. Loss-bounded analysis for differentiated services. In Proc. 12th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 591--600, Washington, DC, January 2001. Google ScholarDigital Library
- Alex Kesselman and Yishay Mansour. Harmonic buffer management policy for shared memory switches. In Proc. 21st IEEE Conf. on Computer Communications (INFOCOM), New York City, New York, June 2002.Google ScholarCross Ref
- Alexander Kesselman and Yishay Mansour. Loss-bounded analysis for differentiated services. J. Algorithms, 46(1):79--95, 2003. Google ScholarDigital Library
- Alexander Kesselman and Yishay Mansour. Harmonic buffer management policy for shared memory switches. Theoretical Computer Science, 324(2-3):161--182, 2004. Google ScholarDigital Library
- Koji Kobayashi, Shuichi Miyazaki, and Yasuo Okabe. A tight bound on online buffer managment for two-port shared-memory switches. In Phillip B. Gibbons and Christian Scheideler, editors, Proc. 19th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 358--364, San Diego, California, June 2007. Google ScholarDigital Library
- Koji Kobayashi, Shuichi Miyazaki, and Yasuo Okabe. Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithms. In Friedhelm Meyer auf der Heide and Michael A. Bender, editors, Proc. 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 328--336, Calgary, Alberta, Cananda, August 2009. Google ScholarDigital Library
- Anna Karlin, Mark Manasse, Larry Rudolph, and Daniel Sleator. Competitive snoopy paging. Algorithmica, 3(1):70--119, 1988.Google Scholar
- Alex Kesselman, Yishay Mansour, and Rob van Stee. Improved competitive guarantees for QoS buffering. In Giuseppe Di Battista and Uri Zwick, editors, Proc. 11th European Symp. on Algorithms (ESA), volume 2832 of Lecture Notes in Computer Science, pages 361--372, Budapest, Hungary, September 2003. Springer-Verlag.Google Scholar
- Alex Kesselman, Yishay Mansour, and Rob van Stee. Improved competitive guarantees for QoS buffering. Algorithmica, 43(1-2):97--111, 2005.Google ScholarDigital Library
- Alex Kesselman, Boal Patt-Shamir, and Gabriel Scalosub. Competitive buffer management with packet dependencies. In Proc. 23rd Int. Parallel and Distributed Processing Symp., pages 1--12, Rome, Italy, May 2009. Google ScholarDigital Library
- Alex Kesselman and Adi Ros'en. Scheduling policies for CIOQ switches. In Proc. Fifteenth ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 353--362, San Diego, California, June 2003. Google ScholarDigital Library
- Alex Kesselman and Adi Rosén. Scheduling policies for CIOQ switches. J. Algorithms, 60(1):60--83, July 2006. Google ScholarDigital Library
- Alex Kesselman and Adi Ros'en. Controlling CIOQ switches with priority queuing and in multistage interconnection networks. J. Interconnection Networks, 9(1-2):53--72, 2008.Google ScholarCross Ref
- Fei Li. Competitive scheduling of packets with hard deadlines in a finite capacity queue. In Proc. 28th IEEE Conf. on Computer Communications (INFOCOM), volume 2, pages 1062--1070, Rio de Janeiro, Brazil, April 2009.Google ScholarCross Ref
- Fei Li. Improved online algorithms for multiplexing weighted packets in bounded buffers. In Proc. 5th Int. Conference on Algorithmic Aspects in Information and Management, volume 5564 of Lecture Notes in Computer Science, pages 265--278, San Francisco, California, June 2009. Springer-Verlag. Google ScholarDigital Library
- Fei Li. Packet scheduling in a size-bounded buffer. CoRR, abs/0909.3637, 2009.Google Scholar
- Zvi Lotker and Boaz Patt-Shamir. Nearly optimal FIFO buffer management for Diff-Serv. In Proc. 21st ACM Symp. on Principles of Distributed Computing (PODC), pages 134--142, Monterey, California, July 2002. Google ScholarDigital Library
- Zvi Lotker and Boaz Patt-Shamir. Nearly optimal FIFO buffer management for two packet classes. Computer Networks, 42(4):481--492, 2003. Google ScholarDigital Library
- Fei Li, Jay Sethuraman, and Clifford Stein. An optimal online algorithm for packet scheduling with agreeable deadlines. In Proc. 16th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 801--802, Vancouver, British Columbia, Canada, January 2005. Google ScholarDigital Library
- Fei Li, Jay Sethuraman, and Clifford Stein. Better online buffer management. In Proc. 18th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 199--208, New Orleans, Louisiana, January 2007. Google ScholarDigital Library
- Yishay Mansour, Boaz Patt-Shamir, and Ofer Lapid. Optimal smoothing schedules for real-time streams. In Proc. 19th ACM Symp. on Principles of Distributed Computing (PODC), pages 21--29, Portland, Oregon, July 2000. Google ScholarDigital Library
- Yishay Mansour, Boaz Patt-Shamir, and Ofer Lapid. Optimal smoothing schedules for real-time streams. Distributed Computing, 17(1):77--89, 2004. Google ScholarDigital Library
- Harald Räcke and Adi Rosén. Approximation algorithms for time-constrained scheduling on line networks. In Friedhelm Meyer auf der Heide and Michael A. Bender, editors, Proc. 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 337--346, Calgary, Alberta, Cananda, August 2009. Google ScholarDigital Library
- Adi Rosén and Gabriel Scalosub. Rate vs. buffer size: Greedy information gathering on the line. In Phillip B. Gibbons and Christian Scheideler, editors, Proc. 19th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pages 305--314, San Diego, California, June 2007. Google ScholarDigital Library
- Markus Schmidt. Packet buffering: Randomization beats deterministic algorithms. In Volker Diekert and Bruno Durand, editors, Proc. 22nd ACM Symp. on Theoretical Aspects of Computer Science (STACS), volume 3404 of Lecture Notes in Computer Science, pages 293--304, Stuttgart, Germany, February 2005. Springer-Verlag. Google ScholarDigital Library
- Daniel Sleator and Robert Tarjan. Amortized efficiency of list update and paging rules. Communications of the ACM, 28:202--208, 1985. Google ScholarDigital Library
- An Zhu. Analysis of queueing policies in QoS switches. J. Algorithms, 53(2):137--168, 2004. Google ScholarDigital Library
Index Terms
- A survey of buffer management policies for packet switches
Index terms have been assigned to the content through auto-classification.
Recommendations
High-speed buffer management for 40 Gb/s-based photonic packet switches
We develop a method of high-speed buffer management for output-buffered photonic packet switches. The use of optical fiber delay lines is a promising solution to constructing optical buffers. The buffer manager determines packet delays in the fiber ...
Buffer Overflow Management in QoS Switches
We consider two types of buffering policies that are used in network switches supporting Quality of Service (QoS). In the FIFO type, packets must be transmitted in the order in which they arrive; the constraint in this case is the limited buffer ...
An optimal lower bound for buffer management in multi-queue switches
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithmsIn the online packet buffering problem (also known as the unweighted FIFO variant of buffer management), we focus on a single network packet switching device with several input ports and one output port. This device forwards unit-size, unit-value ...
Comments