乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,26]],"date-time":"2024-08-26T15:06:46Z","timestamp":1724684806474},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T00:00:00Z","timestamp":1594857600000},"content-version":"unspecified","delay-in-days":45,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Appl. Probab."],"published-print":{"date-parts":[[2020,6]]},"abstract":"Abstract<\/jats:title>We study a class of load-balancing algorithms for many-server systems (N<\/jats:italic> servers). Each server has a buffer of size

$b-1$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> with

$b=O(\\sqrt{\\log N})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>, i.e. a server can have at most one job in service and

$b-1$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> jobs queued. We focus on the steady-state performance of load-balancing algorithms in the heavy traffic regime such that the load of the system is

$\\lambda = 1 - \\gamma N^{-\\alpha}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> for

$0<\\alpha<0.5$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and

$\\gamma > 0,$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> which we call the sub-Halfin\u2013Whitt regime (

$\\alpha=0.5$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> is the so-called Halfin\u2013Whitt regime). We establish a sufficient condition under which the probability that an incoming job is routed to an idle server is 1 asymptotically (as

$N \\to \\infty$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>) at steady state. The class of load-balancing algorithms that satisfy the condition includes join-the-shortest-queue, idle-one-first, join-the-idle-queue, and power-of-d<\/jats:italic>-choices with

$d\\geq \\frac{r}{\\gamma}N^\\alpha\\log N$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> (r<\/jats:italic> a positive integer). The proof of the main result is based on the framework of Stein\u2019s method. A key contribution is to use a simple generator approximation based on state space collapse.<\/jats:p>","DOI":"10.1017\/jpr.2020.13","type":"journal-article","created":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T10:13:04Z","timestamp":1594894384000},"page":"578-596","source":"Crossref","is-referenced-by-count":26,"title":["Steady-state analysis of load-balancing algorithms in the sub-Halfin\u2013Whitt regime"],"prefix":"10.1017","volume":"57","author":[{"given":"Xin","family":"Liu","sequence":"first","affiliation":[]},{"given":"Lei","family":"Ying","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2020,7,16]]},"reference":[{"key":"S0021900220000133_ref2","doi-asserted-by":"crossref","first-page":"1384","DOI":"10.1214\/aoap\/1015345407","article-title":"Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions","volume":"11","author":"Bertsimas","year":"2001","journal-title":"Ann. Appl. Prob."},{"key":"S0021900220000133_ref6","first-page":"867","article-title":"Join the shortest queue with many servers. The heavy-traffic asymptotics","volume":"43","author":"Eschenfeldt","year":"2018","journal-title":"Res."},{"key":"S0021900220000133_ref4","doi-asserted-by":"publisher","DOI":"10.1214\/16-AAP1211"},{"key":"S0021900220000133_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/2964791.2901463"},{"key":"S0021900220000133_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2011.07.015"},{"key":"S0021900220000133_ref15","doi-asserted-by":"publisher","DOI":"10.1287\/14-SSY139"},{"key":"S0021900220000133_ref19","doi-asserted-by":"publisher","DOI":"10.2307\/3213411"},{"key":"S0021900220000133_ref16","unstructured":"[16] van der Boor, M. , Borst, S. C. , van Leeuwaarden, J. S. and Mukherjee, D. (2017). Scalable load balancing in networked systems: Universality properties and stochastic coupling methods. arXiv:1712.08555."},{"key":"S0021900220000133_ref17","first-page":"20","article-title":"Queueing system with selection of the shortest of two queues: An asymptotic approach","volume":"32","author":"Vvedenskaya","year":"1996","journal-title":"Problemy Peredachi Informatsii"},{"key":"S0021900220000133_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3219617.3219663"},{"key":"S0021900220000133_ref1","unstructured":"[1] Banerjee, S. and Mukherjee, D. (2018). Join-the-shortest queue diffusion limit in Halfin\u2013Whitt regime: Tail asymptotics and scaling of extrema. arXiv:1803.03306."},{"key":"S0021900220000133_ref3","unstructured":"[3] Braverman, A. (2018). Steady-state analysis of the join the shortest queue model in the Halfin\u2013Whitt regime. arXiv:1801.05121."},{"key":"S0021900220000133_ref5","doi-asserted-by":"publisher","DOI":"10.1287\/15-SSY212"},{"key":"S0021900220000133_ref7","unstructured":"[7] Gast, N. (2017). Expected values estimated via mean-field approximation are $1\/n$ -accurate. Proc. ACM Meas. Anal. Comput. Syst. 1, 17:1\u201317:26."},{"key":"S0021900220000133_ref9","unstructured":"[9] Gupta, V. and Walton, N. (2017). Load balancing in the non-degenerate slowdown regime. arXiv:1707.01969."},{"key":"S0021900220000133_ref20","doi-asserted-by":"publisher","DOI":"10.2307\/3213271"},{"key":"S0021900220000133_ref10","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8485827"},{"key":"S0021900220000133_ref12","unstructured":"[12] Mitzenmacher, M. (1996). The power of two choices in randomized load balancing. Ph.D. thesis, University of California at Berkeley."},{"key":"S0021900220000133_ref13","unstructured":"[13] Mukherjee, D. , Borst, S. C. , van Leeuwaarden, J. S. and Whiting, P. A. (2016). Universality of power-of-d load balancing in many-server systems. arXiv:1612.00723."},{"key":"S0021900220000133_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-015-9448-8"},{"key":"S0021900220000133_ref18","doi-asserted-by":"publisher","DOI":"10.1145\/3199524.3199565"},{"key":"S0021900220000133_ref22","unstructured":"[22] Ying, L. (2017). Stein\u2019s method for mean field approximations in light and heavy traffic regimes. Proc. ACM Meas. Anal. Comput. Syst. 1, 12:1\u201312:27."}],"container-title":["Journal of Applied Probability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0021900220000133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,16]],"date-time":"2020-07-16T10:13:57Z","timestamp":1594894437000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0021900220000133\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["S0021900220000133"],"URL":"https:\/\/doi.org\/10.1017\/jpr.2020.13","relation":{},"ISSN":["0021-9002","1475-6072"],"issn-type":[{"value":"0021-9002","type":"print"},{"value":"1475-6072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6]]}}}