Asymptotically Optimal Size-Interval Task Assignments
ANSELMI, Jonatha
Quality control and dynamic reliability [CQFD]
Performance analysis and optimization of LARge Infrastructures and Systems [POLARIS ]
Quality control and dynamic reliability [CQFD]
Performance analysis and optimization of LARge Infrastructures and Systems [POLARIS ]
ANSELMI, Jonatha
Quality control and dynamic reliability [CQFD]
Performance analysis and optimization of LARge Infrastructures and Systems [POLARIS ]
< Reduce
Quality control and dynamic reliability [CQFD]
Performance analysis and optimization of LARge Infrastructures and Systems [POLARIS ]
Language
en
Article de revue
This item was published in
IEEE Transactions on Parallel and Distributed Systems. 2019, vol. 30, n° 11, p. 2422-2433
Institute of Electrical and Electronics Engineers
English Abstract
Size-based routing provides robust strategies to improve the performance of computer and communication systems with highly variable workloads because it is able to isolate small jobs from large ones in a static manner. The ...Read more >
Size-based routing provides robust strategies to improve the performance of computer and communication systems with highly variable workloads because it is able to isolate small jobs from large ones in a static manner. The basic idea is that each server is assigned all jobs whose sizes belong to a distinct and continuous interval. In the literature, dispatching rules of this type are referred to as SITA (Size Interval Task Assignment) policies. Though their evident benefits, the problem of finding a SITA policy that minimizes the overall mean (steady-state) waiting time is known to be intractable. In particular it is not clear when it is preferable to balance or unbalance server loads and, in the latter case, how. In this paper, we provide an answer to these questions in the celebrated limiting regime where the system capacity grows linearly with the system demand to infinity. Within this framework, we prove that the minimum mean waiting time achievable by a SITA policy necessarily converges to the mean waiting time achieved by SITA-E, the SITA policy that equalizes server loads, provided that servers are homogeneous. However, within the set of SITA policies we also show that SITA-E can perform arbitrarily bad if servers are heterogeneous. In this case we prove that there exist exactly C! asymptotically optimal policies, where C denotes the number of server types, and all of them are linked to the solution of a single strictly convex optimization problem. It turns out that the mean waiting time achieved by any of such asymptotically optimal policies does not depend on how job-size intervals are mapped to servers. Our theoretical results are validated by numerical simulations with respect to realistic parameters and suggest that the above insights are also accurate in small systems composed of a few servers, i.e., ten.Read less <
English Keywords
Asymptotic optimality
Dispatching policies
Size-based routing
Performance
Origin
Hal imported