iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s00607-022-01138-6
Extended efficiency and soft-fairness multiresource allocation in a cloud computing system | Computing Skip to main content
Springer Nature Link
Log in

Extended efficiency and soft-fairness multiresource allocation in a cloud computing system

  • Regular Paper
  • Published:
Computing Aims and scope Submit manuscript

Abstract

Efficiency and fairness are two essential objectives for multiresource allocations in shared cloud computing systems. Due to the different demands of different users and the different capacities of each resource, it is impossible for multiresource allocations to achieve absolute fairness and maximum efficiency simultaneously. In this paper, we generalize dominant resource fairness (DRF) and propose a new allocation mechanism, max–min efficiency DRF (MME-DRF), to achieve a tradeoff between fairness and efficiency. MME-DRF first fairly allocates some resources to ensure a lower bound of relative soft fairness among users. Then, MME-DRF allocates the remaining resources with the goal of maximizing the minimum resource utilization. MME-DRF can obtain a max–min resource utilization that directly reflects the overall resource utilization of the system. Rigorous proofs show that MME-DRF satisfies four desirable properties, e.g., the sharing incentive, soft fairness, Pareto efficiency and weighted envy freeness. In addition, we develop an algorithm for MME-DRF and evaluate it via simulations driven by examples and Google cluster traces. The simulation results show that MME-DRF guarantees soft fairness and significantly improves the resource utilization of the system.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Ealiyas A, Jeno Lovesum SP (2018) Resource allocation and scheduling methods in cloud - a survey. In: 2018 Second International Conference on Computing Methodologies and Communication (ICCMC), pp 601–604

  2. Poullie P, Bocek T, Stiller B (2018) A survey of the state-of-the-art in fair multi-resource allocations for data centers. IEEE Trans Network Serv Manag 15(1):169–183

    Article  Google Scholar 

  3. Parikh SM (2013) A survey on cloud computing resource allocation techniques. In: 2013 Nirma University International Conference on Engineering (NUiCONE), pp 1–5

  4. Vavilapalli VK, Murthy AC, Douglas C, et al (2013) Apache hadoop yarn: Yet another resource negotiator. In: Proceedings of the 4th annual Symposium on Cloud Computing, pp 1–16

  5. Hindman B, Konwinski A, Zaharia M, et al (2011) Mesos: A platform for fine-grained resource sharing in the data center. In: 8th USENIX Symposium on Networked Systems Design and Implementation (NSDI 11), pp 295–308

  6. Ghodsi A, Zaharia M, Hindman B, et al (2011) Dominant resource fairness: Fair allocation of multiple resource types. In: Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, pp 323–336

  7. Li J, Zhang J, Li W et al (2019) A fair distribution strategy based on shared fair and time-varying resource demand. J Comput Res Develop 56(7):1534–1544

    Google Scholar 

  8. Gutman A, Nisan N (2012) Fair allocation without trade. In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, AAMAS ’12, pp 719–728

  9. Zhang X, Liu X, Li W et al (2016) Dynamic fair allocation of multi-resources based on shared resource quantity. J Commun 37(7):151–160

    Google Scholar 

  10. Rényi A (1961) On measures of entropy and information. In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics, pp 547–561

  11. Jain RK, Chiu DW, Hawe WR et al (1984) A quantitative measure of fairness and discrimination. Digital Equipment Corporation, Hudson, MA, Eastern Research Laboratory

    Google Scholar 

  12. Zukerman M, Tan L, Wang H et al (2005) Efficiency-fairness tradeoff in telecommunications networks. IEEE Commun Lett 9(7):643–645

    Article  Google Scholar 

  13. Joe-Wong C, Sen S, Lan T et al (2013) Multiresource allocation: fairness-efficiency tradeoffs in a unifying framework. IEEE/ACM Trans Network 21(6):1785–1798

    Article  Google Scholar 

  14. Tang S, Yu C, Li Y (2020) Fairness-efficiency scheduling for cloud computing with soft fairness guarantees. IEEE Trans Cloud Comput 2:1–10

    Google Scholar 

  15. Bonald T, Roberts J (2014) Enhanced cluster computing performance through proportional fairness. Perfor Evaluat 79:134–145

    Article  Google Scholar 

  16. Khamse-Ashari J, Lambadaris I, Kesidis G et al (2018) An efficient and fair multi-resource allocation mechanism for heterogeneous servers. IEEE Trans Parall Distrib Syst 29(12):2686–2699

    Article  Google Scholar 

  17. Wang W, Feng C, Li B, et al (2014) On the fairness-efficiency tradeoff for packet processing with multiple resources. In: Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, CoNEXT ’14. pp 235–248

  18. Danna E, Mandal S, Singh A (2012) A practical algorithm for balancing the max-min fairness and throughput objectives in traffic engineering. In: 2012 Proceedings IEEE INFOCOM, pp 846–854

  19. Jiang S, Wu J (2021) Multi-resource allocation in cloud data centers: A trade-off on fairness and efficiency. Concurr Comput Pract Exper 33(6):e6061

    Article  MathSciNet  Google Scholar 

  20. Wilkes J (2011) More google cluster data. Available online: http://googleresearch.blogspot.com/2011/11/more-googlecluster-data.html (accessed on 21 October 2022), google research blog, 2011

  21. Li W, Liu X, Zhang X et al (2017) Multi-resource fair allocation with bounded number of tasks in cloud computing systems. Natl Confer Theoret Comput Sci 20:3–17

    Article  Google Scholar 

  22. Liu X, Zhang X, Li W et al (2017) Swarm optimization algorithms applied to multi-resource fair allocation in heterogeneous cloud computing systems. Computing 99(12):1231–1255

    Article  MathSciNet  MATH  Google Scholar 

  23. Meskar E, Liang B (2018) Fair multi-resource allocation with external resource for mobile edge computing. In: IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp 184–189

  24. Wang W, Liang B, Li B (2015) Multi-resource fair allocation in heterogeneous cloud computing systems. IEEE Transact Parall Distrib Syst 26(10):2822–2835

    Article  Google Scholar 

  25. Tan J, Zhang L, Li M et al (2015) Multi-resource fair sharing for multiclass workflows. Perfoma valuat Rev 42(4):31–37

    Google Scholar 

  26. Sadok H, Campista MEM, Costa LHMK (2021) Stateful drf: Considering the past in a multi-resource allocation. IEEE Trans Comput 70(7):1094–1105

    Article  MathSciNet  MATH  Google Scholar 

  27. Poullie P, Mannhart S, Stiller B (2016) Virtual machine priority adaption to enforce fairness among cloud users. In: Proceedings of the 12th Conference on International Conference on Network and Service Management, pp 91–99

  28. Lan T, Kao D, Chiang M, et al (2010) An axiomatic theory of fairness in network resource allocation. In: 2010 Proceedings IEEE INFOCOM, pp 1–9

  29. Li W, Liu X, Zhang X, et al (2017) A further analysis of the dynamic dominant resource fairness mechanism. In: International Workshop on Frontiers in Algorithmics, pp 163–174

  30. Grandl R, Ananthanarayanan G, Kandula S et al (2014) Multi-resource packing for cluster schedulers. SIGCOMM Comput Commun Rev 44(4):455–466

    Article  Google Scholar 

  31. Kash I, Procaccia AD, Shah N (2014) No agent left behind: dynamic fair division of multiple resources. J Artif Intell Res 51(1):579–603

    Article  MathSciNet  MATH  Google Scholar 

  32. Li J, Xue J (2013) Egalitarian division under leontief preferences. Econ Theory 54(3):597–622

    Article  MathSciNet  MATH  Google Scholar 

  33. Parkes DC, Procaccia AD, Shah N (2015) Beyond dominant resource fairness: Extensions, limitations, and indivisibilities. Assoc Comput Mach 3(1):1–22

    MathSciNet  Google Scholar 

  34. IBM (2022) IBM ILOG CPLEX Optimizer. Available online: https://www.ibm.com/analytics/cplex-optimizer (accessed on 21 October 2022)

Download references

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China [Nos. 12071417, 62266051 and 62062065] and the 14th Postgraduate Innovation Project of Yunnan University [No. KC-22223141].

Author information

Authors and Affiliations

  1. School of Information Science and Engineering, Yunnan University, Kunming, People’s Republic of China

    Xingxing Li & Xuejie Zhang

  2. School of Mathematics and Statistics, Yunnan University, Kunming, People’s Republic of China

    Weidong Li

Authors
  1. Xingxing Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Weidong Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xuejie Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xuejie Zhang.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, X., Li, W. & Zhang, X. Extended efficiency and soft-fairness multiresource allocation in a cloud computing system. Computing 105, 1217–1245 (2023). https://doi.org/10.1007/s00607-022-01138-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00607-022-01138-6

Keywords

Search

Navigation