More Web Proxy on the site http://driver.im/

research-article

Multi-Resource Fairness: Objectives, Algorithms and Performance

Authors:

James RobertsAuthors Info & Claims

SIGMETRICS '15: Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

Pages 31 - 42

https://doi.org/10.1145/2745844.2745869

Published: 15 June 2015 Publication History

Abstract

Designing efficient and fair algorithms for sharing multiple resources between heterogeneous demands is becoming increasingly important. Applications include compute clusters shared by multi-task jobs and routers equipped with middleboxes shared by flows of different types. We show that the currently preferred objective of Dominant Resource Fairness (DRF) has a significantly less favorable efficiency-fairness tradeoff than alternatives like Proportional Fairness and our proposal, Bottleneck Max Fairness. We propose practical algorithms to realize these sharing objectives and evaluate their performance under a stochastic demand model. It is shown, in particular, that the strategyproofness property that motivated the choice of DRF for an assumed fixed set of jobs or flows, is largely irrelevant when demand is dynamic.

References

[1]

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

Digital Library

[2]

T. Bonald and J. Roberts. Enhanced cluster computing performance through proportional fairness. Performance Evaluation, 79(0):134--145, 2014. Special Issue: Performance 2014.

[3]

G. De Veciana, T.-J. Lee, and T. Konstantopoulos. Stability and performance analysis of networks supporting elastic services. Networking, IEEE/ACM Transactions on, 9(1):2--14, 2001.

Digital Library

[4]

D. Dolev, D. G. Feitelson, J. Y. Halpern, R. Kupferman, and N. Linial. No justified complaints: On fair sharing of multiple resources. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pages 68--75, New York, NY, USA, 2012. ACM.

Digital Library

[5]

A. Ghodsi, V. Sekar, M. Zaharia, and I. Stoica. Multi-resource fair queueing for packet processing. In Proceedings of ACM SIGCOMM 2012, pages 1--12, New York, NY, USA, 2012. ACM.

Digital Library

[6]

A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica. Dominant resource fairness: Fair allocation of multiple resource types. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI'11, pages 24--24, Berkeley, CA, USA, 2011. USENIX Association.

Digital Library

[7]

A. Ghodsi, M. Zaharia, S. Shenker, and I. Stoica. Choosy: Max-min fair sharing for datacenter jobs with constraints. In Proceedings of the 8th ACM European Conference on Computer Systems, EuroSys '13, pages 365--378, New York, NY, USA, 2013. ACM.

Digital Library

[8]

P. Goyal, H. Vin, and H. Cheng. Start-time fair queueing: a scheduling algorithm for integrated services packet switching networks. Networking, IEEE/ACM Transactions on, 5(5):690--704, Oct 1997.

Digital Library

[9]

A. Gutman and N. Nisan. Fair allocation without trade. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, AAMAS '12, pages 719--728, Richland, SC, 2012. International Foundation for Autonomous Agents and Multiagent Systems.

Digital Library

[10]

E. Hahne. Round-robin scheduling for max-min fairness in data networks. Selected Areas in Communications, IEEE Journal on, 9(7):1024--1039, Sep 1991.

Digital Library

[11]

C. Joe-Wong, S. Sen, T. Lan, and M. Chiang. Multi-resource allocation: Fairness-efficiency tradeoffs in a unifying framework. In INFOCOM, 2012 Proceedings IEEE, pages 1206--1214, 2012.

[12]

F. P. Kelly, A. K. Maulloo, and D. K. H. Tan. Rate control for communication networks: Shadow prices, proportional fairness and stability. The Journal of the Operational Research Society, 49(3):pp. 237--252, 1998.

[13]

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

Digital Library

[14]

L. Massoulié and J. Roberts. Bandwidth sharing: Objectives and algorithms. IEEE/ACM Trans. Netw., 10(3):320--328, June 2002.

Digital Library

[15]

D. C. Parkes, A. D. Procaccia, and N. Shah. Beyond dominant resource fairness: extensions, limitations, and indivisibilities. In ACM Conference on Electronic Commerce, pages 808--825. ACM, 2012.

Digital Library

[16]

C.-A. Psomas and J. Schwartz. Beyond beyond dominant resource fairness : Indivisible resource allocation in clusters. Tech Report Berkeley, 2013.

[17]

P. J. Schweitzer. Bottleneck determination in networks of queues. In R. Disney and T. Ott, editors, Applied Probability-Computer Science: The Interface Volume 1, volume 2 of Progress in Computer Science, pages 471--485. Springer, 1982.

[18]

M. Shreedhar and G. Varghese. Efficient fair queueing using deficit round robin. SIGCOMM Comput. Commun. Rev., 25(4):231--242, Oct. 1995.

Digital Library

[19]

P. Viswanath, D. Tse, and R. Laroia. Opportunistic beamforming using dumb antennas. Information Theory, IEEE Transactions on, 48(6):1277--1294, Jun 2002.

Digital Library

[20]

N. S. Walton. Proportional fairness and its relationship with multi-class queueing networks. The Annals of Applied Probability, 19(6):2301--2333, 2009.

[21]

N. S. Walton and M. R. Mandjes. A stability conjecture on bandwidth sharing networks. Queueing Syst. Theory Appl., 68(3-4):237--250, Aug. 2011.

Digital Library

[22]

W. Wang, B. Li, and B. Liang. Multi-resource round robin: A low complexity packet scheduler with dominant resource fairness. In ICNP 2013, 2013.

[23]

H.-Q. Ye. Stability of data networks under an optimization-based bandwidth allocation. Automatic Control, IEEE Transactions on, 48(7):1238--1242, July 2003.

[24]

Y. Zeldes and D. G. Feitelson. On-line fair allocations based on bottlenecks and global priorities. In Proceedings of the 4th ACM/SPEC International Conference on Performance Engineering, ICPE '13, pages 229--240, New York, NY, USA, 2013. ACM.

Digital Library

Cited By

Aslan FIosifidis GAyala-Romero JGarcia-Saavedra ACosta-Perez X(2024)Fair Resource Allocation in Virtualized O-RAN PlatformsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36390438:1(1-34)Online publication date: 21-Feb-2024
https://dl.acm.org/doi/10.1145/3639043
Si Salem TIosifidis GNeglia G(2023)Enabling Long-term Fairness in Dynamic Resource AllocationACM SIGMETRICS Performance Evaluation Review10.1145/3606376.359354151:1(31-32)Online publication date: 27-Jun-2023
https://doi.org/10.1145/3606376.3593541
Meskar ELiang B(2023)Fair Multi-Resource Allocation in Heterogeneous Servers With an External Resource TypeIEEE/ACM Transactions on Networking10.1109/TNET.2022.321342631:3(1244-1262)Online publication date: Jun-2023
https://doi.org/10.1109/TNET.2022.3213426
Show More Cited By

Index Terms

Multi-Resource Fairness: Objectives, Algorithms and Performance

Recommendations

Multi-Resource Fairness: Objectives, Algorithms and Performance
Performance evaluation review

Designing efficient and fair algorithms for sharing multiple resources between heterogeneous demands is becoming increasingly important. Applications include compute clusters shared by multi-task jobs and routers equipped with middleboxes shared by ...
Multicast scheduling with resource fairness constraints

Integration of multicast and unicast data in future radio access networks will be necessary in order to improve the resource efficiency and provide new services. Such integration requires new and efficient resource sharing mechanisms. These mechanisms ...
Proportional Fairness in Multi-Channel Multi-Rate Wireless Networks - Part II: The Case of Time-Varying Channels with Application to OFDM Systems

This is Part II of a two-part paper series that studies the use of the proportional fairness (PF) utility function as the basis for resource allocation and scheduling in multichannel multi-rate wireless networks. The contributions of Part II are twofold,...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '15: Proceedings of the 2015 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

June 2015

488 pages

ISBN:9781450334860

DOI:10.1145/2745844

General Chairs:
Bill Lin
University of California, San Diego
,
Jun (Jim) Xu
Georgia Tech
,
Program Chairs:
Sudipta Sengupta
Microsoft Research
,
Devavrat Shah
Massachusetts Institute of Technology

ACM SIGMETRICS Performance Evaluation Review Volume 43, Issue 1
Performance evaluation review
June 2015
468 pages
ISSN:0163-5999
DOI:10.1145/2796314
Editors:
Derek Eager
University of Saskatchewan
,
Carey Williamson
University of Calgary
Issue’s Table of Contents

Copyright © 2015 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

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMETRICS '15

Sponsor:

SIGMETRICS

SIGMETRICS '15: ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems

June 15 - 19, 2015

Oregon, Portland, USA

Acceptance Rates

SIGMETRICS '15 Paper Acceptance Rate 32 of 239 submissions, 13%;

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
721
Total Downloads

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

Reflects downloads up to 26 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aslan FIosifidis GAyala-Romero JGarcia-Saavedra ACosta-Perez X(2024)Fair Resource Allocation in Virtualized O-RAN PlatformsProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/36390438:1(1-34)Online publication date: 21-Feb-2024
https://dl.acm.org/doi/10.1145/3639043
Si Salem TIosifidis GNeglia G(2023)Enabling Long-term Fairness in Dynamic Resource AllocationACM SIGMETRICS Performance Evaluation Review10.1145/3606376.359354151:1(31-32)Online publication date: 27-Jun-2023
https://doi.org/10.1145/3606376.3593541
Meskar ELiang B(2023)Fair Multi-Resource Allocation in Heterogeneous Servers With an External Resource TypeIEEE/ACM Transactions on Networking10.1109/TNET.2022.321342631:3(1244-1262)Online publication date: Jun-2023
https://doi.org/10.1109/TNET.2022.3213426
Wang XTang PSheng YZhang RLiu MChu YZhu XZhang J(2023)An Analysis of Typical Scenarios and Design Suggestions for the Application of V2X TechnologyEngineering Psychology and Cognitive Ergonomics10.1007/978-3-031-35389-5_38(552-559)Online publication date: 9-Jul-2023
https://doi.org/10.1007/978-3-031-35389-5_38
Si Salem TIosifidis GNeglia G(2022)Enabling Long-term Fairness in Dynamic Resource AllocationProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/35706066:3(1-36)Online publication date: 8-Dec-2022
https://doi.org/10.1145/3570606
Wang HLiu GShen H(2022)Cooperative Job Scheduling and Data Allocation in Data-Intensive Parallel Computing ClustersIEEE Transactions on Cloud Computing10.1109/TCC.2022.3206206(1-14)Online publication date: 2022
https://doi.org/10.1109/TCC.2022.3206206
Bei XLi ZLuo J(2022)Fair and Efficient Multi-resource Allocation for Cloud ComputingWeb and Internet Economics10.1007/978-3-031-22832-2_10(169-186)Online publication date: 9-Dec-2022
https://doi.org/10.1007/978-3-031-22832-2_10
Sadok HCampista MCosta L(2021)Stateful DRF: Considering the Past in a Multi-Resource AllocationIEEE Transactions on Computers10.1109/TC.2020.300600770:7(1094-1105)Online publication date: 1-Jul-2021
https://doi.org/10.1109/TC.2020.3006007
Faruque M(2021)A Review Study on “5G NR Slicing Enhancing IoT & Smart Grid Communication”2021 12th International Renewable Engineering Conference (IREC)10.1109/IREC51415.2021.9427791(1-4)Online publication date: 14-Apr-2021
https://doi.org/10.1109/IREC51415.2021.9427791
Chang TKuo TTsai M(2020)Fair VNF Provisioning in NFV Clusters via Node LabelingGLOBECOM 2020 - 2020 IEEE Global Communications Conference10.1109/GLOBECOM42002.2020.9347991(1-6)Online publication date: Dec-2020
https://doi.org/10.1109/GLOBECOM42002.2020.9347991
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.

Media

Figures

Other

Tables

View Table of Contents