The Power of Two Choices on Graphs: the Pair-Approximation is Accurate

Nicolas Gast 1, *
* Auteur correspondant
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : The power of two-choice is a well-known paradigm to improve load balancing where each incoming task is allocated to the least loaded of two servers picked at random among a collection of n servers [6, 4]. We study the power of two-choice in a setting where the two servers are not picked independently at random but are connected by an edge in an underlying graph. Our problem is motivated by systems in which choices are geometrically constrained (see the model of bike-sharing systems introduced in [1, Section 4]). We study a dynamic setting in which jobs leave the system after being served by a server to which is was allocated. Our focus is when each server has few neighbors (typically 2 to 4) for which an mean-field approximation is not accurate. The static counterpart of our model is studied in [2] in which it is shown by counting the number of arrivals on an edge that the power of two-choice does not hold when the degree is small. This technique cannot be used for studying the dynamic setting as the departures induce long-range dependence. The process is N-dimensional and has no product-form stationary distribution. An exact analytic solution seems out of reach. We use pair-approximation, a technique widespread in biology [5]. We build the equations and show that they describe accurately the steady-state of the system. Our results show that, even in a graph of degree 2, choosing between two neighboring improve dramatically the performance compared to a random allocation. 1. GEOMETRIC TWO-CHOICE MODEL Our system is composed of n identical servers that are connected by an undirected graph (V, E), where the set of vertexes is the set of servers V = {1. .. n}. Each server serves jobs at rate µ and uses a first-come first-serve discipline. Jobs arrive in the system at rate nλ. For each incoming job, one server, say s1, is picked uniformly at random among the n servers. Then, another server s2 is picked uniformly at random among the neighbors of s1. The job is then allocated to the server s1 or s2 that has the least number of jobs (ties are broken at random). This allocation scheme is similar to the one of [2]. We denote the load by ρ = λ/µ and assume that ρ < 1. We now describe a few examples that we will explore numerically in Section 3.
Type de document :
Communication dans un congrès
Workshop on MAthematical performance Modeling and Analysis, Jun 2015, Portland, United States. Performance evaluation review, 〈http://www.sigmetrics.org/mama/〉
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01199271
Contributeur : Nicolas Gast <>
Soumis le : mardi 15 septembre 2015 - 11:10:00
Dernière modification le : mercredi 14 décembre 2016 - 01:08:39
Document(s) archivé(s) le : mardi 29 décembre 2015 - 07:06:28

Fichier

NGast.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01199271, version 1

Collections

Citation

Nicolas Gast. The Power of Two Choices on Graphs: the Pair-Approximation is Accurate. Workshop on MAthematical performance Modeling and Analysis, Jun 2015, Portland, United States. Performance evaluation review, 〈http://www.sigmetrics.org/mama/〉. 〈hal-01199271〉

Partager

Métriques

Consultations de la notice

290

Téléchargements de fichiers

129