Afficher la notice abrégée

Heterogeneous Resource Allocation under Degree Constraints

hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorBEAUMONT, Olivier
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorEYRAUD-DUBOIS, Lionel
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorREJEB, Hejer
hal.structure.identifierDepartment of telecommunication systems and computation
dc.contributor.authorTHRAVES-CARO, Christopher
dc.date.accessioned2024-04-15T09:44:16Z
dc.date.available2024-04-15T09:44:16Z
dc.date.created2012
dc.date.issued2012
dc.identifier.issn1045-9219
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/197829
dc.description.abstractEnIn this paper, we consider the problem of assigning a set of clients with demands to a set of servers with capacities and degree constraints. The goal is to find an allocation such that the number of clients assigned to a server is smaller than the server's degree and their overall demand is smaller than the server's capacity, while maximizing the overall throughput. This problem has several natural applications in the context of independent tasks scheduling or virtual machines allocation. We consider both the \emph{offline} (when clients are known beforehand) and the \emph{online} (when clients can join and leave the system at any time) versions of the problem. We first show that the degree constraint on the maximal number of clients that a server can handle is realistic in many contexts. Then, our main contribution is to prove that even if it makes the allocation problem more difficult (NP-Complete), a very small additive resource augmentation on the servers degree is enough to find in polynomial time a solution that achieves at least the optimal throughput. After a set of theoretical results on the complexity of the offline and online versions of the problem, we propose several other greedy heuristics to solve the online problem and we compare the \emph{performance} (in terms of throughput) and the \emph{cost} (in terms of disconnections and reconnections) of all proposed algorithms through a set of extensive simulation results.
dc.description.sponsorshipSimulation de systèmes de prochaine génération - ANR-11-INFR-0013
dc.language.isoen
dc.publisherInstitute of Electrical and Electronics Engineers
dc.subject.enOnline computation
dc.subject.enApproximation algorithms
dc.subject.enResource Augmentation
dc.subject.enDivisible Scheduling
dc.subject.enBin Packing
dc.subject.enCloud Computing
dc.title.enHeterogeneous Resource Allocation under Degree Constraints
dc.typeArticle de revue
dc.identifier.doi10.1109/TPDS.2012.175
dc.subject.halInformatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
bordeaux.journalIEEE Transactions on Parallel and Distributed Systems
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00771773
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00771773v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=IEEE%20Transactions%20on%20Parallel%20and%20Distributed%20Systems&rft.date=2012&rft.eissn=1045-9219&rft.issn=1045-9219&rft.au=BEAUMONT,%20Olivier&EYRAUD-DUBOIS,%20Lionel&REJEB,%20Hejer&THRAVES-CARO,%20Christopher&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée