research-article

Online scheduling of packets with agreeable deadlines

Authors:

Jay Sethuraman,

Clifford SteinAuthors Info & Claims

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

Article No.: 5, Pages 1 - 11

https://doi.org/10.1145/2390176.2390181

Published: 26 December 2012 Publication History

Abstract

This article concerns an online packet scheduling problem that arises as a natural model for buffer management at a network router. Packets arrive at a router at integer time steps, and are buffered upon arrival. Packets have non-negative weights and integer deadlines that are (weakly) increasing in their arrival times. In each integer time step, at most one packet can be sent. The objective is to maximize the sum of the weights of the packets that are sent by their deadlines. The main results include an optimal (ϕ := (1 + √ 5)/2 ≈ 1.618)-competitive deterministic online algorithm, a (4/3 ≈ 1.33)-competitive randomized online algorithm against an oblivious adversary, and a 2-speed 1-competitive deterministic online algorithm. The analysis does not use a potential function explicitly, but instead modifies the adversary's buffer and credits the adversary to account for these modifications.

References

[1]

Achlioptas, D., Chrobak, M., and Noga, J. 2000. Competitive analysis of randomized paging algorithms. Theoret. Comput. Sci. 234, 1-2, 203--218.

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 queuing polices for QoS switches. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 761--770.

Digital Library

[4]

Azar, Y. and Richter, Y. 2003. Management of multi-queue switches in QoS networks. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC). 82--89.

Digital Library

[5]

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

Digital Library

[6]

Bansal, N., Fleischer, L. K., Kimbrel, T., Mahdian, M., Schieber, B., and Sviridenko, M. 2004. Further improvements in competitive guarantees for QoS buffering. In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP). 196--207.

[7]

Bieńkowski, M., Chrobak, M., and Jeż, Ł. 2011. Randomized competitive algorithms for online buffer management in the adaptive adversary model. Theoret. Comput. Sci. 412, 39, 5121--5131.

[8]

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

Digital Library

[9]

Chin, F. Y. L., Chrobak, M., Fung, S. P. Y., Jawor, W., Sgall, J., and Tichy, T. 2006. Online competitive algorithms for maximizing weighted throughput of unit jobs. J. Disc. Algor. 4, 2, 255--276.

Digital Library

[10]

Chin, F. Y. L. and Fung, S. P. Y. 2003. Online scheduling with partial job values: Does timesharing or randomization help&quest; Algorithmica 37, 3, 149--164.

[11]

Chrobak, M., Jawor, W., Sgall, J., and Tichý, T. 2007a. Improved online algorithms for buffer management in QoS switches. ACM Trans. Algor. 3, 4, Article No. 50.

Digital Library

[12]

Chrobak, M., Jawor, W., Sgall, J., and Tichý, T. 2007b. Online scheduling of equal-length jobs: Randomization and restarts help. SIAM J. Comput. 36, 6, 1709--1728.

Digital Library

[13]

Chrobak, M. and Larmore, L. L. 1994. Generosity helps or an 11-competitive algorithm for three servers. J. Algor. 16, 2, 234--263.

Digital Library

[14]

Englert, M. and Westermann, M. 2007. Considering suppressed packets improves buffer management in QoS switches. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 209--218.

Digital Library

[15]

Englert, M. and Westermann, M. 2009. Lower and upper bounds on FIFO buffer management in QoS switches. Algorithmica 53, 4, 523--548.

Digital Library

[16]

Goldwasser, M. H. 2010. A survey of buffer management policies for packet switches. SIGACT News 41, 1, 100--128.

Digital Library

[17]

Hajek, B. 2001. On the competitiveness of online scheduling of unit-length packets with hard deadlines in slotted time. In Proceedings of the 35th Annual Conference on Information Sciences and Systems (CISS). 434--438.

[18]

Jeż, Ł. 2011. One to rule them all: A general randomized algorithm for buffer management with bounded delay. In Proceedings of the 19th Annual European Symposium on Algorithms (ESA). 239--250.

Digital Library

[19]

Jeżabek, J. 2009. Increasing machine speed in on-line scheduling of weighted unit-length jobs in slotted time. In Proceedings of the 35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). Vol. 5404, 329--340.

Digital Library

[20]

Kesselman, 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

[21]

Kesselman, A., Mansour, Y., and van Stee, R. 2005. Improved competitive guarantees for QoS buffering. Algorithmica 43, 1-2, 63--80.

Digital Library

[22]

Li, F., Sethuraman, J., and Stein, C. 2007. Better online buffer management. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 199--208.

Digital Library

[23]

Lotker, Z. and Patt-Shamir, B. 2003. Nearly optimal FIFO buffer management for two packet classes. Comput. Netw. 42, 4, 481--492.

Digital Library

Cited By

Tsanikidis CGhaderi J(2023)Randomized Scheduling of Real-Time Traffic in Wireless Networks Over Fading ChannelsIEEE/ACM Transactions on Networking10.1109/TNET.2022.322331531:4(1688-1701)Online publication date: Aug-2023
https://doi.org/10.1109/TNET.2022.3223315
Veselý PChrobak MJeż ŁSgall J(2022)A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with DeadlinesSIAM Journal on Computing10.1137/21M146975351:5(1626-1691)Online publication date: 31-Oct-2022
https://doi.org/10.1137/21M1469753
Veselý P(2021)Packet SchedulingACM SIGACT News10.1145/3471469.347148152:2(72-84)Online publication date: 17-Jun-2021
https://dl.acm.org/doi/10.1145/3471469.3471481
Show More Cited By

Index Terms

Online scheduling of packets with agreeable deadlines
1. Theory of computation

Recommendations

A comprehensive study of an online packet scheduling algorithm

We study the bounded-delay model for Qualify-of-Service buffer management. Time is discrete. There is a buffer. Unit-length jobs (also called packets) arrive at the buffer over time. Each packet has an integer release time, an integer deadline, and a ...
A near-optimal memoryless online algorithm for FIFO buffering two packet classes

We consider scheduling packets with values in a capacity-bounded buffer in an online setting. In this model, there is a buffer with limited capacity B. At any time, the buffer cannot accommodate more than B packets. Packets arrive over time. Each packet ...
A comprehensive study of an online packet scheduling algorithm
COCOA'11: Proceedings of the 5th international conference on Combinatorial optimization and applications

We study the bounded-delay model for Qualify-of-Service buffer management. Time is discrete. There is a buffer. Unit-length jobs (also called packets) arrive at the buffer over time. Each packet has an integer release time, an integer deadline, and a ...

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 9, Issue 1

December 2012

252 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/2390176

Issue’s Table of Contents

Copyright © 2012 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: 26 December 2012

Accepted: 01 October 2011

Revised: 01 August 2011

Received: 01 November 2010

Published in TALG Volume 9, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
382
Total Downloads

Downloads (Last 12 months)29
Downloads (Last 6 weeks)3

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tsanikidis CGhaderi J(2023)Randomized Scheduling of Real-Time Traffic in Wireless Networks Over Fading ChannelsIEEE/ACM Transactions on Networking10.1109/TNET.2022.322331531:4(1688-1701)Online publication date: Aug-2023
https://doi.org/10.1109/TNET.2022.3223315
Veselý PChrobak MJeż ŁSgall J(2022)A \(\boldsymbol{\phi }\) -Competitive Algorithm for Scheduling Packets with DeadlinesSIAM Journal on Computing10.1137/21M146975351:5(1626-1691)Online publication date: 31-Oct-2022
https://doi.org/10.1137/21M1469753
Veselý P(2021)Packet SchedulingACM SIGACT News10.1145/3471469.347148152:2(72-84)Online publication date: 17-Jun-2021
https://dl.acm.org/doi/10.1145/3471469.3471481
Tsanikidis CGhaderi J(2021)On the Power of Randomization for Scheduling Real-Time Traffic in Wireless NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2021.307227929:4(1703-1716)Online publication date: Aug-2021
https://doi.org/10.1109/TNET.2021.3072279
Kobayashi K(2021)An optimal algorithm for 2-bounded delay buffer management with lookaheadTheoretical Computer Science10.1016/j.tcs.2021.10.005896:C(65-78)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1016/j.tcs.2021.10.005
Markovitch MScalosub G(2021)Bounded delay scheduling with packet dependenciesComputer Communications10.1016/j.comcom.2021.10.008182:C(98-109)Online publication date: 29-Dec-2021
https://dl.acm.org/doi/10.1016/j.comcom.2021.10.008
Veselý PChrobak MJeż ŁSgall JChan T(2019)A ϕ-competitive algorithm for scheduling packets with deadlinesProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310444(123-142)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310444
Kobayashi K(2019)An Optimal Algorithm for 2-Bounded Delay Buffer Management with LookaheadComputing and Combinatorics10.1007/978-3-030-26176-4_29(350-362)Online publication date: 29-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-26176-4_29
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
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
Show More Cited By

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 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