Esa Hyytiä, D.Sc. (Tech.) Professor, Department of Computer Science, University of Iceland

• Home
• Research interests
• Publications
• Past activities
• Student projects
• Contact

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].

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:

v(Δ1,...,Δ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:

• SITA with Switch: SITA-E (equal load) chooses size-intervals in such a way that the offered load is split evenly among the servers. SITA with Switch operates similarly as SITA-E, except that after each task assignment the roles (size-intervals) of the queues are switched in such a way that the size-interval with the shortest jobs is associated with the shortest queue, the next size-interval with the second shortest queue, etc. This policy is obtained by comparing the expected cumulative costs in terms of sojourn time (given by the value function) for different permutations of the size-intervals, and choosing the one with the smallest expected cost in infinite time-horizon. [7]
• FPI-SITA: Eq. (1) allows also the standard FPI yielding a new state-dependent policy that is often close to the optimal. Basically, one evaluates the increase in the expected cumulative sojourn time for assigning the new job to each queue, and chooses the queue with the smallest increment. [7]

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.

Last updated, January 2012.