Minimizing slowdown in heterogeneous size-aware dispatching systems

Abstract

We consider a system of parallel queues where tasks are assigned (dispatched) to one of the available servers upon arrival. The dispatching decision is based on the full state information, i.e., on the sizes of the new and existing jobs. We are interested in minimizing the so-called mean slowdown criterion corresponding to the mean of the sojourn time divided by the processing time. Assuming no new jobs arrive, the shortest-processing-time-product (SPTP) schedule is known to minimize the slowdown of the existing jobs. The main contribution of this paper is three-fold: 1) To show the optimality of SPTP with respect to slowdown in a single server queue under Poisson arrivals; 2) to derive the so-called size-aware value functions for M/G/1-FIFO/LIFO/SPTP with general holding costs of which the slowdown criterion is a special case; and 3) to utilize the value functions to derive efficient dispatching policies so as to minimize the mean slowdown in a heterogeneous server system. The derived policies offer a significantly better performance than e.g., the size-aware-task-assignment with equal load (SITA-E) and least-work-left (LWL) policies.

References

1. S. Aalto, U. Ayesta, S. Borst, V. Misra, and R. Núnez-Queija. Beyond processor sharing. SIGMETRICS Perform. Eval. Rev., 34:36--43, 2007.
2. S. Aalto, U. Ayesta, and R. Righter. On the Gittins index in the M/G/1 queue. Queueing Systems, 63(1--4):437--458, 2009.
3. S. Aalto and J. Virtamo. Basic packet routing problem. In NTS-13, Trondheim, Norway, Aug. 1996.
4. E. Bachmat and H. Sarfati. Analysis of SITA policies. Performance Evaluation, 67(2):102--120, 2010.
5. C. E. Bell and J. Shaler Stidham. Individual versus social optimization in the allocation of customers to alternative servers. Management Science, 29(7):831--839, July 1983.
6. M. E. Crovella, M. Harchol-Balter, and C. D. Murta. Task assignment in a distributed system: Improving performance by unbalancing load. In ACM SIGMETRICS, pages 268--269, June 1998.
7. A. Downey. A parallel workload model and its implications for processor allocation. In IEEE HPDC'97, pages 112--123, Aug. 1997.
8. A. Ephremides, P. Varaiya, and J. Walrand. A simple dynamic routing problem. IEEE Transactions on Automatic Control, 25(4):690--693, Aug. 1980.
9. H. Feng and V. Misra. Mixed scheduling disciplines for network flows. SIGMETRICS Perform. Eval. Rev., 31:36--39, Sept. 2003.
10. H. Feng, V. Misra, and D. Rubenstein. Optimal state-free, size-aware dispatching for heterogeneous M/G/-type systems. Perform. Eval., 62(1--4), 2005.
11. J. Gittins. Multi-armed Bandit Allocation Indices. Wiley, 1989.
12. V. Gupta, M. Harchol-Balter, K. Sigman, and W. Whitt. Analysis of join-the-shortest-queue routing for web server farms. Performance Evaluation, 64(9--12):1062--1081, Oct. 2007.
13. M. Harchol-Balter. Task assignment with unknown duration. J. ACM, 49(2):260--288, Mar. 2002.
14. M. Harchol-Balter, M. E. Crovella, and C. D. Murta. On choosing a task assignment policy for a distributed server system. Journal of Parallel and Distributed Computing, 59:204--228, 1999.
15. M. Harchol-Balter and A. B. Downey. Exploiting process lifetime distributions for dynamic load balancing. ACM Transactions on Computer Systems, 15(3):253--285, Aug. 1997.
16. M. Harchol-Balter, A. Scheller-Wolf, and A. R. Young. Surprising results on task assignment in server farms with high-variability workloads. In ACM SIGMETRICS, pages 287--298, 2009.
17. M. Harchol-Balter, K. Sigman, and A. Wierman. Asymptotic convergence of scheduling policies with respect to slowdown. Perform. Eval., 49(1--4):241--256, Sept. 2002.
18. M. Haviv and T. Roughgarden. The price of anarchy in an exponential multi-server. Oper. Res. Lett., 35(4):421--426, 2007.
19. E. Hyytia, S. Aalto, and A. Penttinen. Minimizing slowdown in heterogeneous size-aware dispatching systems (full version). Technical report, Mar. 2012. arXiv:1203.5040.
20. E. Hyytia, A. Penttinen, and S. Aalto. Size- and state-aware dispatching problem with queue-specific job sizes. European Journal of Operational Research, 217(2):357--370, Mar. 2012.
21. E. Hyytia, A. Penttinen, S. Aalto, and J. Virtamo. Dispatching problem with fixed size jobs and processor sharing discipline. In ITC'23, SFO, USA, Sept. 2011.
22. E. Hyytia, J. Virtamo, S. Aalto, and A. Penttinen. M/M/1-PS queue and size-aware task assignment. Performance Evaluation, 68(11):1136--1148, Nov. 2011.
23. K. R. Krishnan. Joining the right queue: a state-dependent decision rule. IEEE Transactions on Automatic Control, 35(1):104--108, Jan. 1990.
24. Z. Liu and R. Righter. Optimal load balancing on distributed homogeneous unreliable processors. Operations Research, 46(4):563--573, 1998.
25. Z. Liu and D. Towsley. Optimality of the round-robin routing policy. Journal of Applied Probability, 31(2):466--475, June 1994.
26. L. Schrage. A proof of the optimality of the shortest remaining processing time discipline. Operations Research, 16(3), 1968.
27. W. Whitt. Deciding which queue to join: Some counterexamples. Oper. Res., 34(1):55--62, 1986.
28. A. Wierman. Fairness and scheduling in single server queues. Surveys in Operations Research and Management Science, 16(1):39--48, 2011.
29. A. Wierman, M. Harchol-Balter, and T. Osogami. Nearly insensitive bounds on SMART scheduling. In ACM SIGMETRICS, pages 205--216, 2005.
30. W. Winston. Optimality of the shortest line discipline. Journal of Applied Probability, 14:181--189, 1977.
31. S. Yang and G. de Veciana. Size-based adaptive bandwidth allocation: optimizing the average QoS for elastic flows. In IEEE INFOCOM, 2002.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Mathematics of computing

  • Probability and statistics

    • Statistical paradigms

      • Queueing theory

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making