extended-abstract

Heavy-Traffic Delay Insensitivity in Connection-Level Models of Data Transfer with Proportionally Fair Bandwidth Sharing

Authors:

Siva Theja Maguluri,

Lei YingAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 45, Issue 3

Pages 232 - 245

https://doi.org/10.1145/3199524.3199565

Published: 20 March 2018 Publication History

Abstract

Motivated by the stringent requirements on delay performance in data center networks, we study a connection-level model for bandwidth sharing among data transfer flows, where file sizes have phase-type distributions and proportionally fair bandwidth allocation is used. We analyze the expected number of files in steady-state by setting the steady-state drift of an appropriately chosen Lyapunov function equal to zero. We consider the heavy-traffic regime and obtain asymptotically tight bounds on the expected number of files in the system. Our results show that the expected number of files under proportionally fair bandwidth allocation is insensitive in heavy traffic to file size distributions, thus complementing the diffusion approximation result of Vlasiou et al. [20].

References

[1]

S. Asmussen. Applied Probability and Queues. Springer- Verlag New York, 2003.

[2]

D. Bertsimas, D. Gamarnik, and J. N. Tsitsiklis. Performance of multiclass markovian queueing networks via piecewise linear lyapunov functions. Ann. Appl. Probab., 11(4):1384-1428, 11 2001.

[3]

T. Bonald and L. Massoulié. Impact of fairness on internet performance. In Proc. ACM SIGMETRICS Int. Conf. Measurement and Modeling of Computer Systems, pages 82-91, Cambridge, MA, 2001.

Digital Library

[4]

T. Bonald and A. Prouti`ere. Insensitive bandwidth sharing in data networks. Queueing Syst., 44(1):69- 100, 2003.

Digital Library

[5]

M. Bramson. State space collapse with application to heavy traffic limits for multiclass queueing networks. Queueing Syst., 30(1/2):89-148, June 1998.

Digital Library

[6]

G. de Veciana, T.-J. Lee, and T. Konstantopoulos. Stability and performance analysis of networks supporting elastic services. IEEE/ACM Trans. Netw., 9(1):2-14, Feb. 2001.

Digital Library

[7]

A. Eryilmaz and R. Srikant. Asymptotically tight steady-state queue length bounds implied by drift conditions. Queueing Syst., 72(3-4):311-359, Dec. 2012.

Digital Library

[8]

B. Hajek. Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab., 14(3):502-525, 1982.

[9]

W. N. Kang, F. P. Kelly, N. H. Lee, and R. J. Williams. State space collapse and diffusion approximation for a network operating under a fair bandwidth sharing policy. Ann. Appl. Probab., 19(5):1719-1780, Oct. 2009.

[10]

F. Kelly. Charging and rate control for elastic traffic. Eur. T. Telecommun., 8(1):33-37, 1997.

[11]

Y. Lu, S. T. Maguluri, M. S. Squillante, and T. Suk. On optimal weighted-delay scheduling in input-queued switches. arXiv:1704.02302 {math.OC}, Apr. 2017.

[12]

D. G. Luenberger. Optimization by Vector Space Methods. JohnWiley & Sons, 1969.

[13]

S. T. Maguluri and R. Srikant. Heavy traffic queue length behavior in a switch under the maxweight algorithm. Stoch. Syst., 6(1):211-250, 2016.

[14]

S. T. Maguluri, R. Srikant, and L. Ying. Heavy traffic optimal resource allocation algorithms for cloud computing clusters. Perform. Eval., 81:20-39, 2014.

Digital Library

[15]

S. T. Maguluri, S. K. Burle, and R. Srikant. Optimal heavy-traffic queue length scaling in an incompletely saturated switch. In Proc. ACM SIGMETRICS Int. Conf. Measurement and Modeling of Computer Systems, pages 13-24, Antibes Juan-les-Pins, France, 2016.

Digital Library

[16]

L. Massoulié and J. W. Roberts. Bandwidth sharing and admission control for elastic traffic. Telecommun. Syst., 15(1):185-201, 2000.

Digital Library

[17]

F. Paganini, A. Tang, A. Ferragut, and L. L. H. Andrew. Network stability under alpha fair bandwidth allocation with general file size distribution. IEEE Trans. Autom. Control, 57(3):579-591, Mar. 2012.

[18]

D. Shah, J. N. Tsitsiklis, and Y. Zhong. Qualitative properties of α-fair policies in bandwidth-sharing networks. Ann. Appl. Probab., 24(1):76-113, 2014.

[19]

E. D. Sontag. Mathematical Control Theory: Deterministic Finite Dimensional Systems. Springer-Verlag, 1990.

Digital Library

[20]

M. Vlasiou, J. Zhang, and B. Zwart. Insensitivity of proportional fairness in critically loaded bandwidth sharing networks. arXiv:1411.4841v2 {math.PR}, 2014.

[21]

C.-H. Wang, S. T. Maguluri, and T. Javidi. Heavy traffic queue length behavior in switches with reconfiguration delay. In Proc. IEEE Int. Conf. Computer Communications (INFOCOM), Atlanta, GA, May 2017.

[22]

W. Wang, K. Zhu, L. Ying, J. Tan, and L. Zhang. MapTask scheduling in MapReduce with data locality: Throughput and heavy-traffic optimality. IEEE/ACM Trans. Netw., 24:190-203, Feb. 2016.

Digital Library

[23]

W. Wang, S. T. Maguluri, R. Srikant, and L. Ying. Heavy-traffic delay insensitivity in connection-level models of data transfer with proportionally fair bandwidth sharing. Technical report, 2017.

[24]

R. Williams. Diffusion approximations for open multiclass queueing networks: sufficient conditions involving state space collapse. Queueing Syst., 30(1):27-88, 1998.

Digital Library

[25]

Q. Xie and Y. Lu. Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality. In Proc. IEEE Int. Conf. Computer Communications (INFOCOM), pages 963-972, Hong Kong, China, Apr. 2015.

[26]

H.-Q. Ye and D. D. Yao. A stochastic network under proportional fair resource control-diffusion limit with multiple bottlenecks. Oper. Res., 60(3):716-738, 2012.

Digital Library

[27]

H.-Q. Ye and D. D. Yao. Diffusion limit of fair resource control-stationarity and interchange of limits. Math. Oper. Res., 41(4):1161-1207, 2016.

Digital Library

Cited By

Hong YWang W(2024)Sharp Waiting-Time Bounds for Multiserver JobsStochastic Systems10.1287/stsy.2023.000614:4(455-478)Online publication date: Dec-2024
https://doi.org/10.1287/stsy.2023.0006
Liu XGong KYing L(2024)Large-System Insensitivity of Zero-Waiting Load Balancing AlgorithmsStochastic Systems10.1287/stsy.2022.0023Online publication date: 22-Jan-2024
https://doi.org/10.1287/stsy.2022.0023
Goldsztajn DBorst Svan Leeuwaarden J(2024)Server Saturation in Skewed NetworksProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36560188:2(1-37)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3656018
Show More Cited By

Index Terms

Heavy-Traffic Delay Insensitivity in Connection-Level Models of Data Transfer with Proportionally Fair Bandwidth Sharing
1. Computing methodologies
  1. Modeling and simulation
    1. Model development and analysis

Recommendations

Heavy-traffic approximations for linear networks operating under α-fair bandwidth-sharing policies
valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodolgies and tools

We consider the flow-level performance of a linear network supporting elastic traffic, where the service capacity is shared among the various classes of users according to a weighted alpha-fair policy. Assuming Poisson arrivals and exponentially ...
Heavy-Traffic Analysis of a Multiple-Phase Network with Discriminatory Processor Sharing

We analyze a generalization of the discriminatory processor-sharing (DPS) queue in a heavy-traffic setting. Customers present in the system are served simultaneously at rates controlled by a vector of weights. We assume that customers have phase-type ...
Heavy-Traffic Insensitive Bounds for Weighted Proportionally Fair Bandwidth Sharing Policies
We consider a connection-level model proposed by Massoulié and Roberts for bandwidth sharing among file transfer flows in a communication network. We study weighted proportionally fair sharing policies and establish explicit-form bounds on the weighted ...

Comments

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 45, Issue 3

December 2017

253 pages

ISSN:0163-5999

DOI:10.1145/3199524

Editor:
Nidhi Hegde
Bell Labs, Nokia, Nozay, France

Issue’s Table of Contents

Copyright © 2018 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: 20 March 2018

Published in SIGMETRICS Volume 45, Issue 3

Check for updates

Qualifiers

Extended-abstract

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

25
Total Citations
View Citations
197
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hong YWang W(2024)Sharp Waiting-Time Bounds for Multiserver JobsStochastic Systems10.1287/stsy.2023.000614:4(455-478)Online publication date: Dec-2024
https://doi.org/10.1287/stsy.2023.0006
Liu XGong KYing L(2024)Large-System Insensitivity of Zero-Waiting Load Balancing AlgorithmsStochastic Systems10.1287/stsy.2022.0023Online publication date: 22-Jan-2024
https://doi.org/10.1287/stsy.2022.0023
Goldsztajn DBorst Svan Leeuwaarden J(2024)Server Saturation in Skewed NetworksProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36560188:2(1-37)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3656018
Mou SMaguluri S(2024)Heavy-traffic queue length behavior in a switch under Markovian arrivalsAdvances in Applied Probability10.1017/apr.2023.60(1-47)Online publication date: 1-Mar-2024
https://doi.org/10.1017/apr.2023.60
Rutten DMukherjee D(2023)Load Balancing Under Strict Compatibility ConstraintsMathematics of Operations Research10.1287/moor.2022.125848:1(227-256)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1287/moor.2022.1258
Wang WMaguluri SSrikant RYing L(2022)Heavy-Traffic Insensitive Bounds for Weighted Proportionally Fair Bandwidth Sharing PoliciesMathematics of Operations Research10.1287/moor.2021.122547:4(2691-2720)Online publication date: 1-Nov-2022
https://dl.acm.org/doi/10.1287/moor.2021.1225
Wang WXie QHarchol-Balter M(2022)Zero Queueing for Multi-Server JobsACM SIGMETRICS Performance Evaluation Review10.1145/3543516.345392449:1(13-14)Online publication date: 7-Jun-2022
https://dl.acm.org/doi/10.1145/3543516.3453924
Hong YWang WChong SJoo CLee K(2022)Sharp waiting-time bounds for multiserver jobsProceedings of the Twenty-Third International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing10.1145/3492866.3549717(161-170)Online publication date: 3-Oct-2022
https://dl.acm.org/doi/10.1145/3492866.3549717
Minkevičius SKatin IKatina JVinogradova-Zinkevič I(2021)On Little’s Formula in Multiphase QueuesMathematics10.3390/math91822829:18(2282)Online publication date: 16-Sep-2021
https://doi.org/10.3390/math9182282
Hairi Liu XYing L(2021)Beyond ScalingProceedings of the Twenty-second International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing10.1145/3466772.3467029(1-10)Online publication date: 26-Jul-2021
https://dl.acm.org/doi/10.1145/3466772.3467029
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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents