Skip to Main content Skip to Navigation
Journal articles

Asymptotically Optimal Size-Interval Task Assignments

Jonatha Anselmi 1, 2 Josu Doncel 3
1 CQFD - Quality control and dynamic reliability
IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
2 POLARIS - Performance analysis and optimization of LARge Infrastructures and Systems
LIG - Laboratoire d'Informatique de Grenoble, Inria Grenoble - Rhône-Alpes
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 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.
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download
Contributor : Jonatha Anselmi <>
Submitted on : Thursday, October 17, 2019 - 11:27:06 AM
Last modification on : Monday, April 20, 2020 - 11:44:05 AM
Document(s) archivé(s) le : Saturday, January 18, 2020 - 1:38:30 PM


Files produced by the author(s)




Jonatha Anselmi, Josu Doncel. Asymptotically Optimal Size-Interval Task Assignments. IEEE Transactions on Parallel and Distributed Systems, Institute of Electrical and Electronics Engineers, 2019, 30 (11), pp.2422-2433. ⟨10.1109/TPDS.2019.2920121⟩. ⟨hal-02318576⟩



Record views


Files downloads