extended-abstract

Performance of Balanced Fairness in Resource Pools: A Recursive Approach

Authors:

Fabien MathieuAuthors Info & Claims

SIGMETRICS '18: Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems

Pages 125 - 127

https://doi.org/10.1145/3219617.3219669

Published: 12 June 2018 Publication History

Abstract

Understanding the performance of a pool of servers is crucial for proper dimensioning. One of the main challenges is to take into account the complex interactions between servers that are pooled to process jobs. In particular, a job can generally not be processed by any server of the cluster due to various constraints like data locality. In this paper, we represent these constraints by some assignment graph between jobs and servers. We present a recursive approach to computing performance metrics like mean response times when the server capacities are shared according to balanced fairness. While the computational cost of these formulas can be exponential in the number of servers in the worst case, we illustrate their practical interest by introducing broad classes of pool structures that can be exactly analyzed in polynomial time. This extends considerably the class of models for which explicit performance metrics are accessible.

References

[1]

D. P. Anderson. 2004. BOINC: A System for Public-Resource Computing and Storage Proc. of the 5th IEEE/ACM Int. Workshop on Grid Comput. (GRID '04). IEEE Comput. Soc., Washington, DC, USA, 4--10.

Digital Library

[2]

S. A. Berezner and A. E. Krzesinski. 1996. Order independent loss queues. Queueing Syst. Vol. 23, 1--4 (March 1996), 331--335.

[3]

T. Bonald and C. Comte. 2017. Balanced fair resource sharing in computer clusters. Perf. Evaluation Vol. 116 (Nov. 2017), 70--83.

Digital Library

[4]

T. Bonald, C. Comte, and F. Mathieu. 2017 a. Performance of Balanced Fairness in Resource Pools: A Recursive Approach. Proc. ACM Meas. Anal. Comput. Syst. Vol. 1, 2 (Dec. 2017), 41:1--41:25.

Digital Library

[5]

T. Bonald, C. Comte, V. Shah, and G. de Veciana. 2017 b. Poly-symmetry in processor-sharing systems. Queueing Syst. Vol. 86, 3--4 (Aug. 2017), 327--359.

Digital Library

[6]

T. Bonald, L. Massoulié, A. Proutière, and J. Virtamo. 2006. A queueing analysis of max-min fairness, proportional fairness and balanced fairness. Queueing Syst. Vol. 53, 1--2 (June 2006), 65--84.

Digital Library

[7]

T. Bonald and A. Proutière. 2003. Insensitive Bandwidth Sharing in Data Networks. Queueing Syst. Vol. 44, 1 (May 2003), 69--100.

Digital Library

[8]

T. Bonald and J. Virtamo. 2004. Calculating the flow level performance of balanced fairness in tree networks. Perf. Evaluation Vol. 58, 1 (Oct. 2004), 1--14.

Digital Library

[9]

K. Gardner, M. Harchol-Balter, E. Hyyti"a, and R. Righter. 2017a. Scheduling for efficiency and fairness in systems with redundancy. Perf. Evaluation Vol. 116 (Nov. 2017), 1--25.

Digital Library

[10]

K. Gardner, M. Harchol-Balter, A. Scheller-Wolf, M. Velednitsky, and S. Zbarsky. 2017b. Redundancy- d : The Power of d Choices for Redundancy. Operations Research Vol. 65, 4 (April 2017), 1078--1094.

[11]

K. Gardner, S. Zbarsky, S. Doroudi, M. Harchol-Balter, E. Hyytia, and A. Scheller-Wolf. 2016. Queueing with redundant requests: exact analysis. Queueing Syst. Vol. 83, 3--4 (Aug. 2016), 227--259.

Digital Library

[12]

P. G. Harrison. 1985. On Normalizing Constants in Queueing Networks. Operations Research Vol. 33, 2 (1985), 464--468.

Digital Library

[13]

A. E. Krzesinski. 2011. Order Independent Queues. In Queueing Networks, bibfieldeditorR. J. Boucherie and N. M. van Dijk (Eds.). Number 154 in Int. Series in Operations Research & Management Science. Springer US, 85--120.

[14]

K. Lee, Y. Lee, H. Choi, Y. D. Chung, and B. Moon. 2012. Parallel Data Processing with MapReduce: A Survey. SIGMOD Rec. Vol. 40, 4 (Jan. 2012), 11--20.

Digital Library

[15]

L. Massoulié. 2007. Structural Properties of Proportional Fairness: Stability and Insensitivity. The Annals of Appl. Probability Vol. 17, 3 (2007), 809--839.

[16]

V. Shah and G. de Veciana. 2015. High-Performance Centralized Content Delivery Infrastructure: Models and Asymptotics. Trans. on Netw. Vol. 23, 5 (2015), 1674--1687.

Digital Library

[17]

V. Shah and G. de Veciana. 2016. Asymptotic Independence of Servers' Activity in Queueing Systems with Limited Resource Pooling. Queueing Syst. Vol. 83, 1--2 (June 2016), 13--28.

Digital Library

[18]

I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. 2001. Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. SIGCOMM Comput. Commun. Rev. Vol. 31, 4 (2001), 149--160.

Digital Library

Cited By

Mete AManjunath DNair JPrabhu B(2019)Partial Server Pooling in Redundancy Systems2019 31st International Teletraffic Congress (ITC 31)10.1109/ITC31.2019.00024(106-114)Online publication date: Aug-2019
https://doi.org/10.1109/ITC31.2019.00024
Gardner KRighter R(2022)The cost of collaborationQueueing Systems: Theory and Applications10.1007/s11134-021-09721-y100:1-2(7-40)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11134-021-09721-y
Gardner KRighter R(2020)Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overviewQueueing Systems: Theory and Applications10.1007/s11134-020-09668-696:1-2(3-51)Online publication date: 14-Oct-2020
https://dl.acm.org/doi/10.1007/s11134-020-09668-6

Index Terms

Performance of Balanced Fairness in Resource Pools: A Recursive Approach
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
      1. Cloud computing
2. Mathematics of computing
  1. Probability and statistics
    1. Stochastic processes
      1. Markov processes

Recommendations

Performance of Balanced Fairness in Resource Pools: A Recursive Approach

Understanding the performance of a pool of servers is crucial for proper dimensioning. One of the main challenges is to take into account the complex interactions between servers that are pooled to process jobs. In particular, a job can generally not be ...
Performance of Balanced Fairness in Resource Pools: A Recursive Approach
SIGMETRICS '18

Understanding the performance of a pool of servers is crucial for proper dimensioning. One of the main challenges is to take into account the complex interactions between servers that are pooled to process jobs. In particular, a job can generally not be ...
Performance Evaluation of Load Balanced Web Proxies
WAINA '11: Proceedings of the 2011 IEEE Workshops of International Conference on Advanced Information Networking and Applications

A large university usually has many units that may locate far apart, and there are many proxy servers installed to give web access services to those units individually. However, some proxies may face the performance bottleneck when many users access the ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '18: Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems

June 2018

155 pages

ISBN:9781450358460

DOI:10.1145/3219617

General Chair:
Konstantinos Psounis
University of Southern California
,
Program Chairs:
Aditya Akella
University of Wisconsin-Madison
,
Adam Wierman
California Institute of Technology

ACM SIGMETRICS Performance Evaluation Review Volume 46, Issue 1
SIGMETRICS '18
June 2018
142 pages
ISSN:0163-5999
DOI:10.1145/3292040
Editor:
Nidhi Hegde
Borealis AI
Issue’s Table of Contents

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

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

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

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

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
79
Total Downloads

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

Reflects downloads up to 05 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mete AManjunath DNair JPrabhu B(2019)Partial Server Pooling in Redundancy Systems2019 31st International Teletraffic Congress (ITC 31)10.1109/ITC31.2019.00024(106-114)Online publication date: Aug-2019
https://doi.org/10.1109/ITC31.2019.00024
Gardner KRighter R(2022)The cost of collaborationQueueing Systems: Theory and Applications10.1007/s11134-021-09721-y100:1-2(7-40)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s11134-021-09721-y
Gardner KRighter R(2020)Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overviewQueueing Systems: Theory and Applications10.1007/s11134-020-09668-696:1-2(3-51)Online publication date: 14-Oct-2020
https://dl.acm.org/doi/10.1007/s11134-020-09668-6

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 Table of Conten