Article

A tight bound on online buffer management for two-port shared-memory switches

Authors:

Koji Kobayashi,

Shuichi Miyazaki,

Yasuo OkabeAuthors Info & Claims

SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

Pages 358 - 364

https://doi.org/10.1145/1248377.1248437

Published: 09 June 2007 Publication History

Abstract

The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered. In this paper, we focus on shared memory switches with preemption. We prove that the competitive ratio of the Longest Queue Drop (LQD) policy is 4M-4<over>3M-2 in the case of N=2, where N is the number of output ports in a switch and M is the size of the buffer. This matches the lower bound given by Hahne, Kesselman and Mansour. Also, in the case of arbitrary N, we improve the competitive ratio of LQD from 2 to 2-1<over>M min_{K=1, 2, ..., N}{⌊M<over>K⌋ + K - 1.

References

[1]

W. Aiello, Y. Mansour, S. Rajagopolan, and A. Rosen, "Competitive queue policies for differentiated services," IEEE INFOCOM, pp. 431--440, 2000.

[2]

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

Digital Library

[3]

N. Andelman and Y. Mansour, "Competitive management of non--preemptive queues with multiple values," In Proc. of 17th International Symposium on Distributed Computing, pp. 166--180, 2003.

[4]

N. Andelman, Y. Mansour and A. Zhu, "Competitive queueing policies for QoS switches," In Proc. of 14th annual ACM-SIAM Symposium on Discrete Algorithms, pp. 761--770, 2003.

Digital Library

[5]

Y. Azar and Y. Richter, "Management of multi--queue switches in QoS networks," In Proc. of 35th annual ACM Symposium on Theory of Computing, pp. 82--89, 2003.

Digital Library

[6]

Y. Bartal, F. Chin, M. Chrobak, S. Fung, W. Jawor, R. Lavi, J. Sgall and T. Tichý, "Online competitive algorithms for maximizing weighted throughput of unit jobs," In Proc. of 21st International Symposium on Theoretical Aspects of Computer Science, pp. 187--198, 2004.

[7]

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

Digital Library

[8]

F. Chin and S. Fung, "Online scheduling for partial job values: Does timesharing or randomization help?," Algorithmica, Vol.37, pp. 149--164, 2003.

Digital Library

[9]

M. Chrobak, W. Jawor, J. Sgall and T. Tichý, "Improved online algorithms for buffer management in QoS switches," In Proc. of 12th annual European Symposium on Algorithms, pp. 204--215, 2004.

[10]

M. Englert and M. Westermann, "Lower and Upper Bounds on FIFO Buffer Management in QoS Switches," In Proc. of 14th annual European Symposium on Algorithms, pp. 352--363, 2006.

Digital Library

[11]

E. Hahne, A. Kesselman and Y. Mansour, "Competitive buffer management for shared-memory switches," In Proc. of 13th annual ACM Symposium on Parallel Algorithms and Architectures, pp. 53--58, 2001.

Digital Library

[12]

B. Hajek, "On the competitiveness of on-line scheduling of unit-length packets with hard deadlines in slotted time," In Proc. 35th annual Conference on Information Sciences and Systems, pp. 434--439, 2001.

[13]

A. Kesselman, Z. Lotker, Y. Mansour, B. Patt-Shamir, B. Schieber, and M. Sviridenko, "Buffer overflow management in QoS switches," In Proc. of 33rd annual ACM Symposium on Theory of Computing, pp. 520--529, 2001.

Digital Library

[14]

A. Kesselman and Y. Mansour, "Harmonic buffer management policy for shared memory switches," Theoretical Computer Science, Vol. 324, No. 2-3, pp. 161--182, 2004.

Digital Library

[15]

A. Kesselman, Y. Mansour and R. Stee, "Improved competitive guarantees for QoS buffering," In Proc. of 11th annual European Symposium on Algorithms, pp. 361--372, 2003.

[16]

F. Li, J. Sethuraman, and C. Stein, "An optimal online algorithm for packet scheduling with agreeable deadlines," In Proc. of 16th annual ACM-SIAM Symposium on Discrete Algorithms, pp. 801--802, 2005.

Digital Library

[17]

M. Schmidt, "Packet buffering-randomization beats deterministic algorithms," In Proc. of 22nd International Symposium on Theoretical Aspects of Computer Science, pp. 293--304, 2005.

Digital Library

[18]

D. Sleator and R. Tarjan, "Amortized efficiency of list update and paging rules," CACM 28, pp. 202--208, 1985.

Digital Library

[19]

M. Sviridenko, "A lower bound for on-line algorithms in the FIFO model," unpublished manuscript, 2001.

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
Kobayashi KMiyazaki SOkabe Y(2017)Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithmsTheoretical Computer Science10.1016/j.tcs.2017.02.014675:C(27-42)Online publication date: 2-May-2017
https://dl.acm.org/doi/10.1016/j.tcs.2017.02.014
Kawahara JKobayashi KMiyazaki S(2017)Better bounds for online k-frame throughput maximization in network switchesTheoretical Computer Science10.1016/j.tcs.2016.10.009657:PB(173-190)Online publication date: 2-Jan-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.10.009
Show More Cited By

Index Terms

A tight bound on online buffer management for two-port shared-memory switches
1. Networks
  1. Network protocols
    1. Network layer protocols
      1. Routing protocols
2. Theory of computation

Recommendations

A Tight Bound on Online Buffer Management for Two-Port Shared-Memory Switches

The online buffer management problem formulates the problem of queueing policies of network switches supporting QoS (Quality of Service) guarantee. For this problem, several models are considered. In this paper, we focus on shared memory switches with ...
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 ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures

June 2007

376 pages

ISBN:9781595936677

DOI:10.1145/1248377

General Chair:
Phillip B. Gibbons
Intel Research, USA
,
Program Chair:
Christian Scheideler
Technische Universität München, Germany

Copyright © 2007 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SPAA07

Sponsor:

SPAA07: 19th ACM Symposium on Parallelism in Algorithms and Architectures

June 9 - 11, 2007

California, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
234
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 14 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
Kobayashi KMiyazaki SOkabe Y(2017)Competitive buffer management for multi-queue switches in QoS networks using packet buffering algorithmsTheoretical Computer Science10.1016/j.tcs.2017.02.014675:C(27-42)Online publication date: 2-May-2017
https://dl.acm.org/doi/10.1016/j.tcs.2017.02.014
Kawahara JKobayashi KMiyazaki S(2017)Better bounds for online k-frame throughput maximization in network switchesTheoretical Computer Science10.1016/j.tcs.2016.10.009657:PB(173-190)Online publication date: 2-Jan-2017
https://dl.acm.org/doi/10.1016/j.tcs.2016.10.009
Kawahara JKobayashi KMaeda T(2014)Tight Analysis of Priority Queuing for Egress TrafficCombinatorial Optimization and Applications10.1007/978-3-319-12691-3_34(459-473)Online publication date: 13-Nov-2014
https://doi.org/10.1007/978-3-319-12691-3_34
Kawahara JKobayashi KMiyazaki S(2013)Better Bounds for Online k-Frame Throughput Maximization in Network SwitchesAlgorithms and Computation10.1007/978-3-642-45030-3_21(218-228)Online publication date: 2013
https://doi.org/10.1007/978-3-642-45030-3_21
Kawahara JKobayashi K(2013)Optimal Buffer Management for 2-Frame Throughput MaximizationStructural Information and Communication Complexity10.1007/978-3-319-03578-9_23(274-285)Online publication date: 2013
https://doi.org/10.1007/978-3-319-03578-9_23
Goldwasser M(2010)A survey of buffer management policies for packet switchesACM SIGACT News10.1145/1753171.175319541:1(100-128)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1145/1753171.1753195
Kobayashi KMiyazaki SOkabe YMeyer auf der Heide FBender M(2009)Competitive buffer management for multi-queue switches in qos networks using packet buffering algorithmsProceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures10.1145/1583991.1584070(328-336)Online publication date: 11-Aug-2009
https://dl.acm.org/doi/10.1145/1583991.1584070
Chrobak M(2008)SIGACT news online algorithms column 13ACM SIGACT News10.1145/1412700.141271939:3(96-121)Online publication date: 1-Sep-2008
https://dl.acm.org/doi/10.1145/1412700.1412719

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents