{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T00:50:37Z","timestamp":1760403037367,"version":"build-2065373602"},"reference-count":24,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Size-based routing policies are known to perform well when the variance of the distribution of the job size is very high. We consider two size-based policies in this paper: Task Assignment with Guessing Size (TAGS) and Size Interval Task Assignment (SITA). The latter assumes that the size of jobs is known, whereas the former does not. Recently, it has been shown by our previous work that when the ratio of the largest to shortest job tends to infinity and the system load is fixed and low, the average waiting time of SITA is, at most, two times less than that of TAGS. In this article, we first analyze the ratio between the mean waiting time of TAGS and the mean waiting time of SITA in a non-asymptotic regime, and we show that for two servers, and when the job size distribution is Bounded Pareto with parameter \u03b1=1, this ratio is unbounded from above. We then consider a system with an arbitrary number of servers and we compare the mean waiting time of TAGS with that of Size Interval Task Assignment with Equal load (SITA-E), which is a SITA policy where the load of all the servers are equal. We show that in the light traffic regime, the performance ratio under consideration is unbounded from above when (i) the job size distribution is Bounded Pareto with parameter \u03b1=1 and an arbitrary number of servers as well as (ii) for Bounded Pareto distributed job sizes with \u03b1\u2208(0,2)\\{1} and the number of servers tends to infinity. Finally, we use the result of our previous work to show how to design decentralized systems with quality of service constraints.<\/jats:p>","DOI":"10.3390\/s21082701","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T05:52:00Z","timestamp":1618206720000},"page":"2701","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Size-Based Routing Policies: Non-Asymptotic Analysis and Design of Decentralized Systems"],"prefix":"10.3390","volume":"21","author":[{"given":"Eitan","family":"Bachmat","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University, Beer-Sheva 84105, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5552-9134","authenticated-orcid":false,"given":"Josu","family":"Doncel","sequence":"additional","affiliation":[{"name":"Mathematics Department, University of the Basque Country, UPV\/EHU, 48940 Leioa, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Tang, X., Xu, J., and Chanson, S.T. (2005). Web Workload Characterization: Ten Years Later. Web Content Delivery, Springer US.","DOI":"10.1007\/0-387-27727-7"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Bachmat, E., Doncel, J., and Sarfati, H. (2019, January 21\u201325). Performance and Stability Analysis of the Task Assignment Based on Guessing Size Routing Policy. Proceedings of the IEEE 27th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, Rennes, France.","DOI":"10.1109\/MASCOTS.2019.00012"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1109\/TNET.2019.2902531","article-title":"Performance Degradation in Parallel-Server Systems","volume":"27","author":"Doncel","year":"2019","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"2422","DOI":"10.1109\/TPDS.2019.2920121","article-title":"Asymptotically optimal size-interval task assignments","volume":"30","author":"Anselmi","year":"2019","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Bachmat, E., and Doncel, J. (2020, January 17\u201319). Non-Asymptotic Performance Analysis of Size-Based Routing Policies. Proceedings of the 2020 28th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), Nice, France.","DOI":"10.1109\/MASCOTS50786.2020.9285943"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Harchol-Balter, M. (2013). Performance Modeling and Design of Computer Systems: Queueing Theory in Action, Cambridge University Press.","DOI":"10.1017\/CBO9781139226424"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1214\/aoap\/1015345342","article-title":"Join the shortest queue: Stability and exact asymptotics","volume":"11","author":"Foley","year":"2001","journal-title":"Ann. Appl. Probab."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1062","DOI":"10.1016\/j.peva.2007.06.012","article-title":"Analysis of join-the-shortest-queue routing for web server farms","volume":"64","author":"Gupta","year":"2007","journal-title":"Perform. Eval."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"406","DOI":"10.2307\/3213411","article-title":"On the optimal assignment of customers to parallel servers","volume":"15","author":"Weber","year":"1978","journal-title":"J. Appl. Probab."},{"key":"ref_10","first-page":"255","article-title":"The power of two random choices: A survey of techniques and results","volume":"9","author":"Richa","year":"2001","journal-title":"Comb. Optim."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"181","DOI":"10.2307\/3213271","article-title":"Optimality of the shortest line discipline","volume":"14","author":"Winston","year":"1977","journal-title":"J. Appl. Probab."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1287\/opre.34.1.55","article-title":"Deciding Which Queue to Join: Some Counterexamples","volume":"34","author":"Whitt","year":"1986","journal-title":"Oper. Res."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Crovella, M.E., Harchol-Balter, M., and Murta, C.D. (1998). Task Assignment in a Distributed System (Extended Abstract): Improving Performance by Unbalancing Load. Proceedings of the ACM SIGMETRICS, ACM.","DOI":"10.1145\/277851.277942"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1016\/j.peva.2005.07.031","article-title":"Optimal state-free, size-aware dispatching for heterogeneous M\/G\/-type systems","volume":"62","author":"Feng","year":"2005","journal-title":"Perform. Eval."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1006\/jpdc.1999.1577","article-title":"On Choosing a Task Assignment Policy for a Distributed Server System","volume":"59","author":"Crovella","year":"1999","journal-title":"J. Parallel Distrib. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1016\/j.peva.2009.09.007","article-title":"Analysis of SITA policies","volume":"67","author":"Bachmat","year":"2010","journal-title":"Perform. Eval."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Vesilo, R. (2008, January 8\u201310). Asymptotic analysis of load distribution for size-interval task allocation with bounded Pareto job sizes. Proceedings of the IEEE International Conference on Parallel and Distributed Systems, Melbourne, VIC, Australia.","DOI":"10.1109\/ICPADS.2008.20"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1017\/S0269964809990246","article-title":"To balance or unbalance load in size-interval task allocation","volume":"24","author":"Vesilo","year":"2010","journal-title":"Probab. Eng. Inform. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Harchol-Balter, M., Scheller-Wolf, A., and Young, A.R. (2009, January 15\u201319). Surprising Results on Task Assignment in Server Farms with High-variability Workloads. Proceedings of the SIGMETRICS, Seattle, WA, USA.","DOI":"10.1145\/1555349.1555383"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Harchol-Balter, M. (2000, January 10\u201313). Task assignment with unknown duration. Proceedings of the 20th IEEE International Conference on Distributed Computing Systems, Taipei, Taiwan.","DOI":"10.21236\/ADA368426"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"102122","DOI":"10.1016\/j.peva.2020.102122","article-title":"Analysis of the Task Assignment based on Guessing Size policy","volume":"142","author":"Bachmat","year":"2020","journal-title":"Perform. Eval."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1145\/263326.263344","article-title":"Exploiting Process Lifetime Distributions for Dynamic Load Balancing","volume":"15","author":"Downey","year":"1997","journal-title":"ACM Trans. Comput. Syst."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Zhang, H., Liu, X., Ji, H., Hou, Z., and Fan, L. (2019). Multi-Agent-Based Data-Driven Distributed Adaptive Cooperative Control in Urban Traffic Signal Timing. Energies, 12.","DOI":"10.3390\/en12071402"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/j.ejcon.2020.08.001","article-title":"Hybrid data-driven fuzzy active disturbance rejection control for tower crane systems","volume":"58","author":"Roman","year":"2021","journal-title":"Eur. J. Control."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/8\/2701\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T14:28:02Z","timestamp":1760365682000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/21\/8\/2701"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,12]]},"references-count":24,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,4]]}},"alternative-id":["s21082701"],"URL":"https:\/\/doi.org\/10.3390\/s21082701","relation":{},"ISSN":["1424-8220"],"issn-type":[{"type":"electronic","value":"1424-8220"}],"subject":[],"published":{"date-parts":[[2021,4,12]]}}}