Publication:
Enhancing the power of two choices load balancing algorithm using round robin policy

Simple item page
carlosiii.embargo.terms2022-06-30
dc.affiliation.dptoUC3M. Departamento de Informáticaes
dc.affiliation.grupoinvUC3M. Grupo de Investigación: Arquitectura de Computadores, Comunicaciones y Sistemases
dc.contributor.authorGarcía Carballeira, Félix
dc.contributor.authorCalderón Mateos, Alejandro
dc.contributor.authorCarretero Pérez, Jesús
dc.contributor.funderComunidad de Madrides
dc.date.accessioned2021-12-09T16:30:55Z
dc.date.available2022-06-30T23:00:05Z
dc.date.issued2020-06-22
dc.description.abstractThis paper proposes a new version of the power of two choices, SQ(d), load balancing algorithm. This new algorithm improves the performance of the classical model based on the power of two choices randomized load balancing. This model considers jobs that arrive at a dispatcher as a Poisson stream of rate lambdan,lambda<1, at a set of n servers. Using the power of two choices, the dispatcher chooses some d constant for each job independently and uniformly from the n servers in a random way and sends the job to the server with the fewest number of jobs. This algorithm offers an advantage over the load balancing based on shortest queue discipline, because it provides good performance and reduces the overhead in the servers and the communication network. In this paper, we propose a new version, shortest queue of d with randomization and round robin policies, SQ-RR(d). This new algorithm combines randomization techniques and static local balancing based on a round-robin policy. In this new version, the dispatcher chooses the d servers as follows: one is selected using a round-robin policy, and the d&#8722;1 servers are chosen independently and uniformly from the n servers in a random way. Then, the dispatcher sends the job to the server with the fewest number of jobs. We demonstrate with a theoretical approximation of this approach that this new version improves the performance obtained with the classical solution in all situations, including systems at 99% capacity. Furthermore, we provide simulations that demonstrate the theoretical approximation developed.en
dc.description.sponsorshipThis work was partially supported by the Project ‘‘CABAHLA-CM: Convergencia Big data-Hpc: de los sensores a las Aplicaciones’’ S2018/TCS-4423 from Madrid Regional Government.en
dc.identifier.bibliographicCitationGarcia-Carballeira, F., Calderon, A. & Carretero, J. Enhancing the power of two choices load balancing algorithm using round robin policy. Cluster Comput 24, 611–624 (2021). https://doi.org/10.1007/s10586-020-03139-6en
dc.identifier.doihttps://doi.org/10.1007/s10586-020-03139-6
dc.identifier.issn1386-7857
dc.identifier.publicationfirstpage611
dc.identifier.publicationlastpage624
dc.identifier.publicationtitleCluster Computing-The Journal of Networks Software Tools and Applicationsen
dc.identifier.publicationvolume24
dc.identifier.urihttps://hdl.handle.net/10016/33731
dc.identifier.uxxiAR/0000026228
dc.language.isoengen
dc.publisherSpringeren
dc.relation.projectIDComunidad de Madrid. S2018/TCS-4423es
dc.rights© 2020, Springer Science Business Media, LLC, part of Springer Naturees
dc.rights.accessRightsrestricted accessen
dc.subject.ecienciaInformáticaes
dc.subject.otherthe power of two choicesen
dc.subject.otherload balancingen
dc.subject.otherdistributed systemsen
dc.titleEnhancing the power of two choices load balancing algorithm using round robin policyen
dc.typeresearch article*
dc.type.hasVersionAM*
dspace.entity.typePublication
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
enhancing_CC_2021_ps.pdf
Size:
578.4 KB
Format:
Adobe Portable Document Format
Description:
Download
Collections
DI - ATC - Artículos de revistas