home/Research Interests/Dispatching Problem/SITA

Dispatching Problem: SITA and FPI

1. Size-Interval Task Assignment (SITA)

  • Consider a dispatching system with m FCFS servers
  • Typical problem with FCFS is that later arriving short jobs end up waiting for a completion of a long job
  • Idea: assign tasks based on their size (service requirement)
  • That is, each server receives the jobs of certain size interval, e.g.,
    "Short jobs to Server 1 and long ones to Server 2."
  • This Size-Interval Task Assignment (SITA) policy, proposed by Crovella et al. [1] and Harchol-Balter et al. [2], has been shown to be the optimal state-free policy by Feng et al. [3].
dispatching system
Figure: A dispatching system.

By segregating long jobs from short ones, a SITA policy often achieves a low mean delay (i.e., response time).

2. SITA with Switch and Policy Improvement

Our work on improving the basic SITA policy is based on queueing theory and Markov decision processes. We assume a Poisson arrival process and that also the queue states are available (state-aware). The basic SITA is state-independent (state-free), i.e., the dispatching decision does not depend on the queue states. Consequently, the arrival process to each queue is Poissonian and the queues behave according to an M/G/1-FCFS queue. The so-called first policy iteration (FPI) of MDP requires the corresponding value function, and in [1] we have derived it for the size-aware M/G/1-FCFS queue with respect to the sojourn time:

v1,...,Δn)  - v0  = 
λ ( Σi Δi)2
2(1-ρ)
 +  Σi i · Δi,
(1) 

where Δi denotes the (remaining) size of job i. Due to the independence of queues (with a state-independent basic policy), the value function of the whole system is obtained as a sum of the queue specific value functions. These allow one to find the expected difference in the cumulative sojourn times between any two states of the system. Eventually, one obtains two new state-dependent dispatching policies:

Both SITA with Switch and FPI-SITA outperform the corresponding basic SITA policy, where the latter is generally the better albeit a slightly more complex policy.

References

[1]  M. Harchol-Balter, M. E. Crovella and C. D. Murta, On Choosing a Task Assignment Policy for a Distributed Server System, J. Parallel Distrib. Comput., 59 (1999) 204-228. (pdf)
[2] M. Crovella, M. Harchol-Balter and C. Murta, Task Assignment in a Distributed System: Improving Performance by Unbalancing Load, in ACM SIGMETRICS, June 1998, (pdf)
[3] H. Feng, V. Misra and D. Rubenstein, Optimal state-free, size-aware dispatching for heterogeneous M/G/-type systems, Performance Evaluation, 62(1-4) (2005) 475-492. (pdf)
[4] B. Schroeder and M. Harchol-Balter, Evaluation of Task Assignment Policies for Supercomputing Servers: The Case for Load Unbalancing and Fairness, Cluster Computing, 7(2) (2004). (pdf)
[5] E. Bachmat and H. Sarfati, Analysis of SITA policies, Performance Evaluation, 67(2) (2010) 102-120. (pdf)
[6] 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, 2009. (pdf)
[7] E. Hyytiä, A. Penttinen and S. Aalto, Size- and State-Aware Dispatching Problem with Queue-Specific Job Sizes, Eur. J. Oper. Res., 217 (2) (2012) 357-370. (pdf)