Dynamic Routing in the Mean-Field Approximation

Philippe Jacquet 1 Yuri Suhov Nikita Vvedenskaya 1
1 HIPERCOM - High performance communication
Inria Paris-Rocquencourt, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
Abstract : A queuing system is considered, with stations $1$, $2$, where station $i$ contains a collection $S_i$ of infinite-buffer FCFS single servers. The number of servers in each $S_i$ is $N$, and we assume that $N$ is large (formally, $N\to\infty$). The system is fed by a Poisson flow of rate $2\l N$, with i.i.d. exponential service times of mean one. Upon arrival, a customer chooses two servers according to the following rule. He performs two independent trials, each time choosing station $1$ with probability $p_1$ and $2$ with probability $p_2=1-p_1$ and then choosing a server at random from the corresponding collection $S_i$. He then selects the server with a shortest queue from the two, breaking ties at random if necessary. We assume that $p_1\geq p_2\geq 0$; the main result is that (a) the inequalities $\lambda <1$, $2\lambda p_1^2 <1$, are necessary and sufficient for the existence (and uniqueness) of a (stable) stationary regime, and (b) under these inequalities, a stationary queue-size distribution has a super-exponentially decaying tail. These results are in a striking contrast with a `linear' model where a customer simply chooses a station with probabilities $p_1$ and $p_2$ and then selects a server at random from the corresponding $S_i$. Here, the necessary and sufficient condition is $2\lambda p_1<1$, and the queue-size distribution is geometric.
Type de document :
[Research Report] RR-3789, INRIA. 1999
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 11:08:42
Dernière modification le : vendredi 25 mai 2018 - 12:02:06
Document(s) archivé(s) le : dimanche 4 avril 2010 - 21:09:13



  • HAL Id : inria-00072870, version 1



Philippe Jacquet, Yuri Suhov, Nikita Vvedenskaya. Dynamic Routing in the Mean-Field Approximation. [Research Report] RR-3789, INRIA. 1999. 〈inria-00072870〉



Consultations de la notice


Téléchargements de fichiers