Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
The Journal of Supercomputing
Published in: The Journal of Supercomputing 14/2023

22-04-2023

Multiresource fair allocation with time window constraints

Authors: Xingxing Li, Weidong Li, Xuejie Zhang

Published in: The Journal of Supercomputing | Issue 14/2023

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We study the problem of multiresource fair allocation with time window constraints for user tasks in cloud computing systems where users can enter and leave the system multiple times. We propose a new mechanism, dominant resource fairness with time window constraints (DRFTW), that extends the concepts of dominant resource fairness and lexicographically max-min fairness to the case where user tasks have time window constraints. We design an algorithm for DRFTW to produce the optimal allocations. DRFTW has several highly desirable properties: no user can improve its performance without making at least one other user worse off; no user prefers even allocations; no user envies other users’ allocations; and no user can increase its utility by providing false information. Simulations driven by Alibaba Cluster Trace further revealed that DRFTW can significantly increase the minimum dominant share and improve fairness among users compared with three conventional fair allocation methods.
previous article Dynamic stochastic game-based security of edge computing based on blockchain
next article A risk assessment model for similar attack scenarios in industrial control system

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Ghodsi A, Zaharia M, Hindman B, Konwinski A, Shenker S, Stoica I (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
2.
Radunovic B, Boudec JL (2007) A unified framework for max-min and min-max fairness with applications. IEEE/ACM Trans Netw 15(05):1073–1083CrossRef
3.
Chakraborty M, Igarashi A, Suksompong W, Zick Y (2021) Weighted envy-freeness in indivisible item allocation. ACM Trans Econ Comput TEAC 9(3):1–39MathSciNetCrossRef
4.
Parikh SM (2013) A survey on cloud computing resource allocation techniques. In: 2013 Nirma University International Conference on Engineering (NUiCONE), pp 1–5
5.
Li J, Zhang J, Li W, Zhang X (2019) A fair distribution strategy based on shared fair and time-varying resource demand. J Comput Res Dev 56(7):1534
6.
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 Netw Serv Manage 15(1):169–183CrossRef
7.
8.
Sadok H, Campista MEM, Costa LHMK (2021) Stateful DRF: considering the past in a multi-resource allocation. IEEE Trans Comput 70(7):1094–1105MathSciNetCrossRefMATH
9.
Floyd S (2008) Metrics for the evaluation of congestion control mechanisms. RFC 5166, Citeseer
10.
Kelly F, Maulloo A, Tan D (1998) Rate control for communication networks: shadow prices, proportional fairness and stability. J Oper Res Soc 3:49MATH
11.
12.
Dolev D, Feitelson DG, Halpern JY, Kupferman R, Linial N (2012) No justified complaints: On fair sharing of multiple resources. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp 68–75
13.
Zhang X, Liu X, Li W, Zhang X (2016) Dynamic fair allocation of multi-resources based on shared resource quantity. J Commun 37(7):151
14.
Dolev D, Feitelson DG, Halpern J, Kupferman R, Linial N (2012) No justified complaints: On fair sharing of multiple resources. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp 68–75
15.
Zahedi SM, Lee BC (2014) Resource elasticity fairness with sharing incentives for multiprocessors. In: Proceedings of the 19th International Conference on Architectural Support for Programming Languages and Operating Systems
16.
Li W, Liu X, Zhang X, Zhang X (2017) A further analysis of the dynamic dominant resource fairness mechanism. In: International Workshop on Frontiers in Algorithmics, pp 163–174
17.
Wang W, Liang B, Li B (2015) Multi-resource fair allocation in heterogeneous cloud computing systems. IEEE Trans Parallel Distrib Syst 26(10):2822–2835CrossRef
18.
Joe-Wong C, Sen S, Lan T, Chiang M (2013) Multiresource allocation: fairness-efficiency tradeoffs in a unifying framework. IEEE/ACM Trans Netw 21(6):1785–1798CrossRef
19.
Tang S, Yu C, Li Y (2022) Fairness-efficiency scheduling for cloud computing with soft fairness guarantees. IEEE Trans Cloud Comput 10(3):1806–1818CrossRef
20.
Li X, Li W, Zhang X (2022) Extended efficiency and soft-fairness multiresource allocation in a cloud computing system. Computing, 1–29
21.
22.
Kash I, Procaccia AD, Shah N (2014) No agent left behind: dynamic fair division of multiple resources. J Artif Int Res 51(1):579–603MathSciNetMATH
23.
Reiss C, Tumanov A, Ganger GR, Katz RH, Kozuch MA (2012) Heterogeneity and dynamicity of clouds at scale: Google trace analysis. In: Proceedings of the Third ACM Symposium on Cloud Computing, pp 1–13
24.
Friedman E, Psomas CA, Vardi S (2017) Controlled dynamic fair division. In: Proceedings of the 2017 ACM Conference on Economics and Computation, pp 461–478
25.
26.
Kelly FP, Maulloo AK, Tan DKH (1998) Rate control for communication networks: shadow prices, proportional fairness and stability. J Oper Res Soc 49(3):237–252CrossRefMATH
27.
Ghodsi A, Zaharia M, Shenker S, Stoica I (2013) Choosy: Max-min fair sharing for datacenter jobs with constraints. In: Proceedings of the 8th ACM European Conference on Computer Systems, pp 365–378
28.
Parkes DC, Procaccia AD, Shah N (2015) Beyond dominant resource fairness: extensions, limitations, and indivisibilities. ACM Trans Econ Comput TEAC 3(1):1–22MathSciNetCrossRef
29.
Vavilapalli V.K, Murthy AC, Douglas C, Agarwal S, Konar M, Evans R, Graves T, Lowe J, Shah H, Seth S, Saha B, Curino C, O’Malley O, Radia S, Reed B, Baldeschwieler E (2013) Apache hadoop yarn: Yet another resource negotiator. In: Proceedings of the 4th Annual Symposium on Cloud Computing, pp 1–16
30.
Hindman B, Konwinski A, Zaharia M, Ghodsi A, Joseph A.D, Katz R, Shenker S, Stoica I (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
31.
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
32.
Li W, Liu X, Zhang X, Zhang X (2017) Multi-resource fair allocation with bounded number of tasks in cloud computing systems. In: National Conference of Theoretical Computer Science, pp 3–17
33.
Zhang X, Li J, Li G, Li W (2022) Generalized asset fairness mechanism for multi-resource fair allocation mechanism with two different types of resources. Clus Comput 5:3389–403CrossRef
34.
Waldspurger CA (1996) Lottery and stride scheduling: flexibile proportional-share resource management. PhD thesis, PhD thesis, MIT, Laboratory of Computer Science, USA
35.
Li X, Li W, Zhang X (2023) Multi-resource fair allocation with bandwidth requirement compression in the cloud-edge system. Comput Electr Eng 105:108510CrossRef
Metadata
Title
Multiresource fair allocation with time window constraints
Authors
Xingxing Li
Weidong Li
Xuejie Zhang
Publication date
22-04-2023
Publisher
Springer US
Published in
The Journal of Supercomputing / Issue 14/2023
Print ISSN: 0920-8542
Electronic ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-023-05248-6

Other articles of this Issue 14/2023

The Journal of Supercomputing 14/2023 Go to the issue

OriginalPaper

Dynamic stochastic game-based security of edge computing based on blockchain

OriginalPaper

Lightweight and authentic symmetric session key cryptosystem for client–server mobile communication

OriginalPaper

FSCN: a novel forwarding method based on Shannon entropy and COPRAS decision process in named data networking

OriginalPaper

Evaluation of 3D LiDAR SLAM algorithms based on the KITTI dataset

OriginalPaper

Embedding channel pruning within the CNN architecture design using a bi-level evolutionary approach

OriginalPaper

On forcibly k-edge-connected and forcibly super edge-connected uniform hypergraphic sequences

Premium Partner

    Image Credits