Size-Based Routing Policies: Non-Asymptotic Analysis and Design of Decentralized Systems
dc.contributor.author | Bachmat, Eitan | |
dc.contributor.author | Doncel Vicente, Josu | |
dc.date.accessioned | 2021-04-30T10:18:21Z | |
dc.date.available | 2021-04-30T10:18:21Z | |
dc.date.issued | 2021-04-12 | |
dc.identifier.citation | Sensors 21(8) : (2021) // Article ID 2701 | es_ES |
dc.identifier.issn | 1424-8220 | |
dc.identifier.uri | http://hdl.handle.net/10810/51266 | |
dc.description.abstract | 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 α=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 α=1 and an arbitrary number of servers as well as (ii) for Bounded Pareto distributed job sizes with α∈(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. | es_ES |
dc.description.sponsorship | Josu Doncel has received funding from the Department of Education of the Basque Government through the Consolidated Research Group MATHMODE (IT1294-19), from the Marie Sklodowska-Curie grant agreement No 777778, and from the Spanish Ministry of Science and Innovation with reference PID2019-108111RB-I00 (FEDER/AEI). Eitan Bachmat’s work was supported by the German Science Foundation (DFG) through the grant, Airplane Boarding, (JA 2311/3-1). | es_ES |
dc.language.iso | eng | es_ES |
dc.publisher | MDPI | es_ES |
dc.relation | info:eu-repo/grantAgreement/EC/H2020/777778 | es_ES |
dc.relation | info:eu-repo/grantAgreement/MICINN/PID2019-108111RB-I00 | es_ES |
dc.rights | info:eu-repo/semantics/openAccess | es_ES |
dc.rights.uri | http://creativecommons.org/licenses/by/3.0/es/ | |
dc.subject | parallel servers | es_ES |
dc.subject | size-based routing | es_ES |
dc.subject | queuing theory | es_ES |
dc.title | Size-Based Routing Policies: Non-Asymptotic Analysis and Design of Decentralized Systems | es_ES |
dc.type | info:eu-repo/semantics/article | es_ES |
dc.date.updated | 2021-04-23T13:33:34Z | |
dc.rights.holder | 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/). | es_ES |
dc.relation.publisherversion | https://www.mdpi.com/1424-8220/21/8/2701/htm | es_ES |
dc.identifier.doi | 10.3390/s21082701 | |
dc.contributor.funder | European Commission | |
dc.departamentoes | Matemáticas | |
dc.departamentoeu | Matematika |
Files in this item
This item appears in the following Collection(s)
Except where otherwise noted, this item's license is described as 2021 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).