Home | Articles | Past volumes | About | Login | Notify | Contact | Search
 Stochastic Systems > Vol. 6 (2016) open journal systems 


Randomized assignment of jobs to servers in heterogeneous clusters of shared servers for low delay

Arpan Mukhopadhyay, University of Waterloo
A. Karthik, University of Waterloo
Ravi R. Mazumdar, University of Waterloo


Abstract
We consider the problem of assignning jobs to servers in a multi-server system consisting of \(N\) parallel processor sharing servers, categorized into \(M\) (\(\ll N\)) different types according to their processing capacities or speeds. Jobs of random sizes arrive at the system according to a Poisson process with rate \(N \lambda\). Upon each arrival, some servers of each type are sampled uniformly at random. The job is then assigned to one of the sampled servers based on their states. We propose two schemes, which differ in the metric for choosing the destination server for each arriving job. Our aim is to reduce the mean sojourn time of the jobs in the system.

It is shown that the proposed schemes achieve the maximal stability region, without requiring the knowledge of the system parameters. The performance of the system operating under the proposed schemes is analyzed in the limit as \(N \to\infty\). This gives rise to a mean field limit. The mean field is shown to have a unique, globally asymptotically stable equilibrium point which approximates the stationary distribution of load at each server. Asymptotic independence among the servers is established using a notion of intra-type exchangeability which generalizes the usual notion of exchangeability. It is further shown that the tail distribution of server occupancies decays doubly exponentially for each server type. Numerical evidence shows that at high load the proposed schemes perform at least as well as other schemes that require more knowledge of the system parameters.

AMS 2000 subject classifications: Primary 60K35; secondary 60K25, 90B15.

Keywords: Processor sharing, power-of-two, mean field, asymptotic independence, stability, propagation of chaos.

Creative Common LOGO

Full Text: PDF
Mukhopadhyay, Arpan, Karthik, A., Mazumdar, Ravi R., Randomized assignment of jobs to servers in heterogeneous clusters of shared servers for low delay, Stochastic Systems, 6, (2016), 90-131 (electronic). DOI: 10.1214/15-SSY179.

References

[1]    Altman, E., Ayesta, U., and Prabhu, B. J. (2008). Load balancing in processor sharing systems. Telecommunication Systems 47, 1-2, 35–48.

[2]    Anantharam, V. and Benchekroun, M. (1993). A technique for computing sojourn times large networks of interacting queues. Probability in Engineering and Informational Sciences 7, 441–464.

[3]    Bramson, M. (2011). Stability of join the shortest queue networks. Annals of Applied Probability 21, 4, 1568–1625. MR2857457

[4]    Bramson, M., Lu, Y., and Prabhakar, B. (2010). Randomized load balancing with general service time distributions. In Proceedings of the ACM SIGMETRICS. 275–286.

[5]    Bramson, M., Lu, Y., and Prabhakar, B. (2012). Asymptotic independence of queues under randomized load balancing. Queueing Systems 71, 3, 247–292. MR2943660

[6]    Budhiraja, A. and Lee, C. (2008). Stationary distribution convergence for generalized jackson networks in heavy traffic. Mathematics of Operations Research 34, 1, 45–56. MR2542988

[7]    Ethier, S. N. and Kurtz, T. G. (1985). Markov Processes: Characterization and Convergence. John Wiley and Sons Ltd. MR0838085

[8]    Garmanik, D. and Zeevi, A. (2006). Validity of heavy traffic steady-state approximations in generalized jackson networks. The Annals of Applied Probability 16, 1, 56–90. MR2209336

[9]    Graham, C. (2000). Chaoticity on path space for a queueing network with selection of shortest queue among several. Journal of Applied Probability 37, 1, 198–211. MR1761670

[10]    Gupta, V., Balter, M. H., Sigman, K., and Whitt, W. (2007). Analysis of join-the-shortest-queue routing for web server farms. Performance Evaluation 64, 9-12, 1062–1081.

[11]    Haddad, J.-P. and Mazumdar, R. R. (2012). Heavy traffic approximation for the stationary distribution of stochastic fluid networks. Queueing Syst. 70, 1, 3–21. MR2886474

[12]    Kelly, F. P. (1979). Reversibility and Stochastic Networks. John Wiley and Sons Ltd. MR0554920

[13]    Martin, J. B. and Suhov, Y. M. (1999). Fast Jackson networks. Annals of Applied Probability 9, 3, 854–870. MR1722285

[14]    Mitzenmacher, M. (1996). The power of two choices in randomized load balancing. Ph.D. thesis, Harvard University. MR2695522

[15]    Mitzenmacher, M. (2001). The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems 12, 10, 1094–1104.

[16]    Mukhopadhyay, A., Karthik, A., Mazumdar, R. R., and Guillemin, F. (2015). Mean field and propagation of chaos in multi-class heterogeneous loss models. Performance Evaluation 91, 117–131.

[17]    Mukhopadhyay, A. and Mazumdar, R. R. (2014). Rate-based randomized routing in large heterogeneous processor sharing systems. In Proceedings of the 26th International Teletraffic Congress (ITC 26). 1–9.

[18]    Mukhopadhyay, A. and Mazumdar, R. R. (2015). Analysis of randomized join-the-shortest-queue (JSQ) schemes in large heterogeneous processor sharing systems. IEEE Transactions on Control of Network Systems 3, 2, 116–126. MR3514587

[19]    Psounis, K. and Prabhakar, B. (2002). Efficient randomized web-cache replacement schemes using samples from past eviction times. IEEE/ACM Transactions on Networking 10, 4, 441–454.

[20]    Schassberger, R. (1984). A new approach to the M∕G∕1 processor-sharing queue. Advances in Applied Probability 16, 1, 202–213. MR0732137

[21]    Schurman, E. and Brutlag, J. (2009). The user and business impact on server delays, additional bytes and http chunking in web search. In O’Reilly Velocity Web Performance and Operations Conference.

[22]    Sznitman, A. S. (1991). Topics in propagation of chaos. In École d’été de probabilites de Saint-Flour XIX - 1989. Lecture Notes in Mathematics, Vol. 1464. Springer, 165–251. MR1108185

[23]    Turner, S. R. E. (1998). The effect of increasing routing choice on resource pooling. Probability in the Engineering and Informational Sciences 12, 109–124. MR1492143

[24]    Vvedenskaya, N. D., Dobrushin, R. L., and Karpelevich, F. I. (1996). Queueing system with selection of the shortest of two queues: an asymptotic approach. Problems of Information Transmission 32, 1, 20–34. MR1384927

[25]    Weber, R. R. (1978). On the optimal assignment of customers to parallel servers. Journal of Applied Probability 15, 406–413. MR0518586

[26]    Winston, W. (1977). Optimality of the shortest line discipline. Journal of Applied Probability 14, 1, 181–189. MR0428516

[27]    Xie, Q., Dong, X., Lu, Y., and Srikant, R. (2015). Power of d choices for large-scale bin packing: A loss model. In Proceedings of ACM SIGMETRICS.

[28]    Xu, J. and Hajek, B. (2013). The supermarket game. Stochastic Systems 3, 2, 405–441. MR3353208

[29]    Zachary, S. (2007). A note on insensitivity in stochastic networks. Journal of Applied Probability 44, 1, 238–248. MR2312999
Home | Articles | Past volumes | About | Login | Notify | Contact | Search

Stochastic Systems. ISSN: 1946-5238