Asymptotic independence of queues under randomized load balancing

被引:90
作者
Bramson, Maury [1 ]
Lu, Yi [2 ]
Prabhakar, Balaji [3 ]
机构
[1] Univ Minnesota, Sch Math, Minneapolis, MN 55455 USA
[2] Univ Illinois, Dept Elect & Comp Engn, Urbana, IL 61801 USA
[3] Stanford Univ, Dept Elect Engn, Stanford, CA 94305 USA
基金
美国国家科学基金会;
关键词
Load balancing; Join the shortest queue; Join the least loaded queue; Asymptotic independence; 2; CHOICES; STABILITY; POWER;
D O I
10.1007/s11134-012-9311-0
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Randomized load balancing greatly improves the sharing of resources while being simple to implement. In one such model, jobs arrive according to a rate-alpha N Poisson process, with alpha < 1, in a system of N rate-1 exponential server queues. In Vvedenskaya et al. (Probl. Inf. Transm. 32:15-29, 1996), it was shown that when each arriving job is assigned to the shortest of D, Da parts per thousand yen2, randomly chosen queues, the equilibrium queue sizes decay doubly exponentially in the limit as N -> a. This is a substantial improvement over the case D=1, where queue sizes decay exponentially. The reasoning in Vvedenskaya et al. (Probl. Inf. Transm. 32:15-29, 1996) does not easily generalize to jobs with nonexponential service time distributions. A modularized program for treating randomized load balancing problems with general service time distributions was introduced in Bramson et al. (Proc. ACM SIGMETRICS, pp. 275-286, 2010). The program relies on an ansatz that asserts that, for a randomized load balancing scheme in equilibrium, any fixed number of queues become independent of one another as N -> a. This allows computation of queue size distributions and other performance measures of interest. In this article, we demonstrate the ansatz in several settings. We consider the least loaded balancing problem, where an arriving job is assigned to the queue with the smallest workload. We also consider the more difficult problem, where an arriving job is assigned to the queue with the fewest jobs, and demonstrate the ansatz when the service discipline is FIFO and the service time distribution has a decreasing hazard rate. Last, we show the ansatz always holds for a sufficiently small arrival rate, as long as the service distribution has 2 moments.
引用
收藏
页码:247 / 292
页数:46
相关论文
共 19 条
[1]  
[Anonymous], 1965, FIZMATGIZ MOSKOW
[2]  
[Anonymous], 1972, BRANCHING PROCESSES
[3]  
Azar Y., 1999, SIAM Journal on Computing, V29, P180, DOI [10.1145/195058.195412, 10.1137/S0097539795288490]
[4]  
Bramson M., 2012, ANN APPL PR IN PRESS
[5]  
Bramson M., 2008, LECT NOTES MATH, V1950
[6]   STABILITY OF JOIN THE SHORTEST QUEUE NETWORKS [J].
Bramson, Maury .
ANNALS OF APPLIED PROBABILITY, 2011, 21 (04) :1568-1625
[7]  
Bramson M, 2010, PERF E R SI, V38, P275, DOI 10.1145/1811099.1811071
[8]  
CHUNG KL, 1985, COURSE PROBABILITY T
[9]  
Davis M. H. A., 1993, MARKOV MODELS OPTIMI
[10]   On the stability of a partially accessible multi-station queue with state-dependent routing [J].
Foss, S ;
Chernova, N .
QUEUEING SYSTEMS, 1998, 29 (01) :55-73