research-article

Competitive buffer management for shared-memory switches

Authors:

William Aiello,

Alex Kesselman,

Yishay MansourAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 5, Issue 1

Article No.: 3, Pages 1 - 16

https://doi.org/10.1145/1435375.1435378

Published: 12 December 2008 Publication History

Abstract

We consider buffer management policies for shared memory switches. We study the case of overloads resulting in packet loss, where the constraint is the limited shared memory capacity. The goal of the buffer management policy is that of maximizing the number of packets transmitted. The problem is online in nature, and thus we use competitive analysis to measure the performance of the buffer management policies. Our main result is to show that the well-known preemptive Longest Queue Drop (LQD) policy is at most 2-competitive and at least √2-competitive. We also demonstrate a general lower bound of 4/3 on the performance of any deterministic online policy. Finally, we consider some other popular non-preemptive policies including Complete Partition, Complete Sharing, Static Threshold and Dynamic Threshold and derive almost tight bounds on their performance.

References

[1]

Aiello, W. A., Mansour, Y., Rajagopolan, S., and Rosén, A. 2005. Competitive queue policies for differentiated services. J. Algor. 55, 2, 113--141.

Digital Library

[2]

Albers, S., and Schmidt, M. 2005. On the performance of greedy algorithms in packet buffering. SIAM J. Comput. 35, 2, 278--304.

Digital Library

[3]

Andelman, N., Mansour, Y., and Zhu, A. 2003. Competitive queueing policies for qos switches. In Proceedings of 14th ACM-SIAM Symposium on Discrete Algorithms (SODA 2003). ACM, New York, 761--770.

Digital Library

[4]

Arpaci, M., and Copeland, J. A. 2000. Buffer management for shared-memory atm switches. IEEE Commun. Surv. 3, 1, 2--10.

Digital Library

[5]

Azar, Y., and Litichevskey, M. 2006. Maximizing throughput in multi-queue switches. Algorithmica 45, 1, 69--90.

Digital Library

[6]

Azar, Y., and Richter, Y. 2004. The zero-one principle for switching networks. In Proceedings of the 36th annual ACM symposium on Theory (STOC 2004). 64--71.

Digital Library

[7]

Azar, Y., and Richter, Y. 2005. Management of multi-queue switches in qos networks. Algorithmica 43, 1-2, 81--96.

Digital Library

[8]

Azar, Y., and Richter, Y. 2006. An improved algorithm for cioq switches. ACM Trans. Algor. 2, 2, 282--295.

Digital Library

[9]

Borodin, A., and El-Yaniv, R. 1998. Online Computation and Competitive Analysis. Cambridge University Press.

Digital Library

[10]

Choudhury, A. K., and Hahne, E. L. 1998. Dynamic queue length thresholds for shared-memory packet switches. IEEE/ACM Trans. Netw. 6, 2 (Apr.), 130--140.

Digital Library

[11]

Epstein, L., and Stee, R. V. 2004. Sigact news online algorithms. ACM SIGACT News 35, 3 (Sept.), 58--66.

Digital Library

[12]

Irland, M. 1978. Buffer management in a packet switch. IEEE Trans. Commun. COM-26, 3 (Mar.), 328--337.

[13]

Kamoun, F., and Kleinrock, L. 1980. Analysis of shared finite storage in a computer network node environment under general traffic conditions. IEEE Trans. Commun. COM-28, 7 (July), 992--1003.

[14]

Kesselman, A., and Mansour, Y. 2004. Harmonic buffer management policy for shared memory switches. TCS Special Issue on Online Algorithms in Memoriam of Steve Seiden 324, 2-3, 161--182.

Digital Library

[15]

Kesselman, A., and Rosén, A. 2006. Scheduling policies for cioq switches. J. Algor. 60, 1, 60--83.

Digital Library

[16]

Kesselmanm, A., Lotker, Z., Mansour, Y., Patt-Shamir, B., Schieber, B., and Sviridenko, M. 2004. Buffer overflow management in qos switches. SIAM J. Comput. 33, 3, 563--583.

Digital Library

[17]

Kroner, H. 1990. Comparative peformance study of space priority mechanisms for atm networks. In Proceedings of IEEE INFOCOM 1990. IEEE Computer Society Press, Los Alamitos, CA, 1136--1143.

[18]

Sleator, D., and Tarjan, R. 1985. Amortized efficiency of list update and paging rules. Commun. ACM 28, 202--208.

Digital Library

[19]

Thareja, A. K., and Agrawala, A. K. 1984. On the design of optimal policy for sharing finite buffers. IEEE Trans. Communications COM-32, 6 (June), 737--740.

[20]

Wei, S. X., Coyle, E. J., and Hsiao, M. T. 1991. An optimal buffer management policy for high-performance packet switching. In Proceedings of IEEE GLOBECOM 1991. IEEE Computer Society Press, Los Alamitos, CA, 924--928.

Cited By

Antoniadis AEnglert MMatsakis NVeselý P(2024)Breaking the Barrier of 2 for the Competitiveness of Longest Queue DropACM Transactions on Algorithms10.1145/367688720:4(1-29)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3676887
Davydow AChuprikov PNikolenko SKogan K(2021)Competitive buffer management for packets with latency constraintsComputer Networks10.1016/j.comnet.2021.107942189(107942)Online publication date: Apr-2021
https://doi.org/10.1016/j.comnet.2021.107942
Kogan KMenikkumbura DPetri GNoh YNikolenko SSirotkin AEugster P(2020)Towards Software-Defined Buffer ManagementIEEE/ACM Transactions on Networking10.1109/TNET.2020.301104828:5(2337-2349)Online publication date: Oct-2020
https://doi.org/10.1109/TNET.2020.3011048
Show More Cited By

Index Terms

Competitive buffer management for shared-memory switches
1. Networks
  1. Network types
    1. Packet-switching networks
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
      1. Scheduling algorithms
    2. Online algorithms
      1. Online learning algorithms
        Scheduling algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning
        Sequential decision making

Recommendations

Online Packet Scheduling for CIOQ and Buffered Crossbar Switches
SPAA '16: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures

We consider the problem of online packet scheduling in Combined Input and Output Queued (CIOQ) and buffered crossbar switches. In the widely used CIOQ switches, packet buffers (queues) are placed at both input and output ports. An N x N CIOQ switch has ...
Comparison-Based Buffer Management in QoS Switches

The following online problem arises in network devices, e.g., switches, with quality of service (QoS) guarantees. In each time step, an arbitrary number of packets arrive at a single buffer and only one packet can be transmitted. The differentiated ...
An optimal lower bound for buffer management in multi-queue switches
SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

In 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 5, Issue 1

November 2008

281 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1435375

Issue’s Table of Contents

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 December 2008

Accepted: 01 October 2007

Revised: 01 October 2007

Received: 01 October 2005

Published in TALG Volume 5, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
579
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)4

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Antoniadis AEnglert MMatsakis NVeselý P(2024)Breaking the Barrier of 2 for the Competitiveness of Longest Queue DropACM Transactions on Algorithms10.1145/367688720:4(1-29)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3676887
Davydow AChuprikov PNikolenko SKogan K(2021)Competitive buffer management for packets with latency constraintsComputer Networks10.1016/j.comnet.2021.107942189(107942)Online publication date: Apr-2021
https://doi.org/10.1016/j.comnet.2021.107942
Kogan KMenikkumbura DPetri GNoh YNikolenko SSirotkin AEugster P(2020)Towards Software-Defined Buffer ManagementIEEE/ACM Transactions on Networking10.1109/TNET.2020.301104828:5(2337-2349)Online publication date: Oct-2020
https://doi.org/10.1109/TNET.2020.3011048
Fiandrino Cde la Oliva AWidmer JKogan KHansdah RKrishnaswamy DVaidya N(2019)pDCellProceedings of the 20th International Conference on Distributed Computing and Networking10.1145/3288599.3288636(71-80)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.1145/3288599.3288636
Al-Bawani KEnglert MWestermann M(2018)Online Packet Scheduling for CIOQ and Buffered Crossbar SwitchesAlgorithmica10.5555/3288645.328866580:12(3861-3888)Online publication date: 1-Dec-2018
https://dl.acm.org/doi/10.5555/3288645.3288665
Chuprikov PNikolenko SDavydow AKogan K(2018)Priority Queueing for Packets With Two CharacteristicsIEEE/ACM Transactions on Networking10.1109/TNET.2017.278277126:1(342-355)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1109/TNET.2017.2782771
Yang YLiao CHan XZhang L(2018)Online buffer management for transmitting packets with processing cyclesTheoretical Computer Science10.1016/j.tcs.2018.02.035723(73-83)Online publication date: May-2018
https://doi.org/10.1016/j.tcs.2018.02.035
Eugster PKesselman AKogan KNikolenko SSirotkin A(2018)Admission control in shared memory switchesJournal of Scheduling10.1007/s10951-018-0564-221:5(533-543)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1007/s10951-018-0564-2
Al-Bawani KEnglert MWestermann M(2018)Online Packet Scheduling for CIOQ and Buffered Crossbar SwitchesAlgorithmica10.1007/s00453-018-0421-x80:12(3861-3888)Online publication date: 5-Mar-2018
https://doi.org/10.1007/s00453-018-0421-x
Kogan KMenikkumbura DPetri GNoh YNikolenko SSirotkin AEugster P(2017)A programmable buffer management platform2017 IEEE 25th International Conference on Network Protocols (ICNP)10.1109/ICNP.2017.8117533(1-10)Online publication date: Oct-2017
https://doi.org/10.1109/ICNP.2017.8117533
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents