An Optimal Randomized Online Algorithm for QoS Buffer Management
Pages 28 - 30
Abstract
The QoS buffer management problem, with significant and diverse computer applications, e.g., in online cloud resource allocation problems, is a classic online admission control problem in the presence of resource constraints. In its basic setting, packets with different values, arrive in online fashion to a switching node with limited buffer size. Then, the switch needs to make an immediate decision to either admit or reject the incoming packet based on the value of the packet and its buffer availability. The objective is to maximize the cumulative profit of the admitted packets, while respecting the buffer constraint. Even though the QoS buffer management problem was proposed more than a decade ago, no optimal online solution has been proposed in the literature. This paper proposes an optimal randomized online algorithm for this problem.
References
[1]
W. Aiello, Y. Mansour, S. Rajagopolan, and A. Rosén. Competitive queue policies for differentiated services. In Proc. of IEEE INFOCOM, pages 431--440, 2000.
[2]
N. Andelman and Y. Mansour. Competitive management of non-preemptive queues with multiple values. In Proc. of DISC, pages 166--180, 2003.
[3]
A. Kesselman, Z. Lotker, Y. Mansour, B. Patt-Shamir, and B. Schieber. Buffer overflow management in QoS switches. SIAM Journal on Computing, 33(3), 2004.
[4]
E. Mohr, I. Ahmad, and G. Schmidt. Online algorithms for conversion problems: a survey. Surveys in Operations Research and Management Science, 19(2), 2014.
[5]
L. Yang, M. H. Hajiesmaili, H. Yi, and M. Chen. Hour-ahead offering strategies in electricity market for power producers with storage and intermittent supply. In Proc. of ACM SIGMETRICS, 2017.
[6]
L. Yang, W. S. Wong, and M. H. Hajiesmaili. An optimal randomized online algorithm for qos buffer management. Proc. ACM Meas. Anal. Comput. Syst., 1(2):36:1--36:26, December 2017.
[7]
Z. Zhang, Z. Li, and C. Wu. Optimal posted prices for online cloud resource allocation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(1):23, 2017.
Index Terms
- An Optimal Randomized Online Algorithm for QoS Buffer Management
Recommendations
An Optimal Randomized Online Algorithm for QoS Buffer Management
SIGMETRICS '18The QoS buffer management problem, with significant and diverse computer applications, e.g., in online cloud resource allocation problems, is a classic online admission control problem in the presence of resource constraints. In its basic setting, ...
An Optimal Randomized Online Algorithm for QoS Buffer Management
The QoS (Quality of Service) buffer management problem, with significant and diverse computer applications, e.g., in online cloud resource allocation problems, is a classic online admission control problem in the presence of resource constraints. In its ...
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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2018
155 pages
ISBN:9781450358460
DOI:10.1145/3219617
- General Chair:
- Konstantinos Psounis,
- Program Chairs:
- Aditya Akella,
- Adam Wierman
Copyright © 2018 Owner/Author.
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 June 2018
Check for updates
Author Tags
Qualifiers
- Extended-abstract
Conference
SIGMETRICS '18
Sponsor:
SIGMETRICS '18: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems
June 18 - 22, 2018
CA, Irvine, USA
Acceptance Rates
SIGMETRICS '18 Paper Acceptance Rate 54 of 270 submissions, 20%;
Overall Acceptance Rate 459 of 2,691 submissions, 17%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 115Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)1
Reflects downloads up to 15 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in