{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T08:23:40Z","timestamp":1775031820657,"version":"3.50.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,4,3]],"date-time":"2018-04-03T00:00:00Z","timestamp":1522713600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ONR","award":["N00014-17-1-2417"],"award-info":[{"award-number":["N00014-17-1-2417"]}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CNS-1719371"],"award-info":[{"award-number":["CNS-1719371"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Meas. Anal. Comput. Syst."],"published-print":{"date-parts":[[2018,4,3]]},"abstract":"<jats:p>\n            Heavy-traffic delay optimality is considered to be an important metric in evaluating the delay performance of load balancing schemes. In this paper, we argue that heavy-traffic delay optimality is a coarse metric that does not necessarily imply good delay performance. Specifically, we show that any load balancing scheme is heavy-traffic delay optimal as long as it satisfies a fairly weak condition. This condition only requires that in the long-term the dispatcher favors, even slightly, shorter queues over longer queues. Hence, although a load balancing scheme could be heavy-traffic delay optimal, the empirical delay performance of heavy-traffic delay optimal schemes can range from very good (that of join-shortest-queue) to very bad (arbitrarily close to the performance of random routing). To overcome this limitation, we introduce a new metric called\n            <jats:italic>degree of queue imbalance,<\/jats:italic>\n            which measures the queue length difference between all the servers in steady-state. Given a heavy-traffic delay optimal load balancing scheme, we can characterize the resultant\n            <jats:italic>degree of queue imbalance.<\/jats:italic>\n            This, in turn, allows us to explicitly differentiate between good and poor load balancing schemes. Thus, this paper suggests that when designing good load balancing schemes, they should not only be heavy-traffic delay optimal, but also have a low degree of queue imbalance.\n          <\/jats:p>","DOI":"10.1145\/3179424","type":"journal-article","created":{"date-parts":[[2018,4,4]],"date-time":"2018-04-04T12:11:45Z","timestamp":1522843905000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Degree of Queue Imbalance"],"prefix":"10.1145","volume":"2","author":[{"given":"Xingyu","family":"Zhou","sequence":"first","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fei","family":"Wu","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jian","family":"Tan","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kannan","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ness","family":"Shroff","sequence":"additional","affiliation":[{"name":"The Ohio State University, Columbus, OH, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,4,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Annals of Applied Probability","author":"Bertsimas Dimitris","year":"2001","unstructured":"Dimitris Bertsimas , David Gamarnik , and John N Tsitsiklis . 2001. Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Annals of Applied Probability ( 2001 ), 1384--1428. Dimitris Bertsimas, David Gamarnik, and John N Tsitsiklis. 2001. Performance of multiclass Markovian queueing networks via piecewise linear Lyapunov functions. Annals of Applied Probability (2001), 1384--1428."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019160803783"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/277858.277942"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-012-9305-y"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1978.1094075"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Ian Foster Yong Zhao Ioan Raicu and Shiyong Lu. 2008. Cloud computing and grid computing 360-degree compared 2008 Grid Computing Environments Workshop. Ieee 1--10.  Ian Foster Yong Zhao Ioan Raicu and Shiyong Lu. 2008. Cloud computing and grid computing 360-degree compared 2008 Grid Computing Environments Workshop. Ieee 1--10.","DOI":"10.1109\/GCE.2008.4738445"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901478"},{"key":"e_1_2_1_8_1","volume-title":"HBase: the definitive guide. \" O'Reilly Media","author":"George Lars","unstructured":"Lars George . 2011. HBase: the definitive guide. \" O'Reilly Media , Inc .\". Lars George. 2011. HBase: the definitive guide. \" O'Reilly Media, Inc.\"."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2007.06.012"},{"key":"e_1_2_1_10_1","volume-title":"Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing systems","author":"Kelly FP","year":"1993","unstructured":"FP Kelly and CN Laws . 1993. Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing systems , Vol. 13 , 1 ( 1993 ), 47--86. FP Kelly and CN Laws. 1993. Dynamic routing in open queueing networks: Brownian models, cut constraints and resource pooling. Queueing systems, Vol. 13, 1 (1993), 47--86."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2011.07.015"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/15-SSY193"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2014.08.002"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2016.7852246"},{"key":"e_1_2_1_16_1","volume-title":"Johan SH van Leeuwaarden, and Philip A Whiting","author":"Mukherjee Debankur","year":"2016","unstructured":"Debankur Mukherjee , Sem C Borst , Johan SH van Leeuwaarden, and Philip A Whiting . 2016 . Universality of Power-of-$ d $ Load Balancing in Many-Server Systems . arXiv preprint arXiv:1612.00723 (2016). Debankur Mukherjee, Sem C Borst, Johan SH van Leeuwaarden, and Philip A Whiting. 2016. Universality of Power-of-$ d $ Load Balancing in Many-Server Systems. arXiv preprint arXiv:1612.00723 (2016)."},{"key":"e_1_2_1_17_1","volume-title":"Some diffusion approximations with state space collapse. Modelling and performance evaluation methodology","author":"Reiman Martin I","unstructured":"Martin I Reiman . 1984. Some diffusion approximations with state space collapse. Modelling and performance evaluation methodology . Springer , 207--240. Martin I Reiman. 1984. Some diffusion approximations with state space collapse. Modelling and performance evaluation methodology. Springer, 207--240."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-016-9497-7"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11134-015-9448-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1075828046"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2014.2362745"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019108819713"},{"key":"e_1_2_1_23_1","volume-title":"2015 IEEE Conference on. IEEE, 963--972","author":"Xie Qiaomin","year":"2015","unstructured":"Qiaomin Xie and Yi Lu . 2015 . Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality Computer Communications (INFOCOM) , 2015 IEEE Conference on. IEEE, 963--972 . Qiaomin Xie and Yi Lu. 2015. Priority algorithm for near-data scheduling: Throughput and heavy-traffic optimality Computer Communications (INFOCOM), 2015 IEEE Conference on. IEEE, 963--972."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2016.7524416"}],"container-title":["Proceedings of the ACM on Measurement and Analysis of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3179424","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3179424","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3179424","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:18Z","timestamp":1750208898000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3179424"}},"subtitle":["Overcoming the Limitation of Heavy-traffic Delay Optimality in Load Balancing Systems"],"short-title":[],"issued":{"date-parts":[[2018,4,3]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,4,3]]}},"alternative-id":["10.1145\/3179424"],"URL":"https:\/\/doi.org\/10.1145\/3179424","relation":{},"ISSN":["2476-1249"],"issn-type":[{"value":"2476-1249","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,4,3]]},"assertion":[{"value":"2018-04-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}