Size-based task assignment with cycle stealing under immediate dispatching

We consider a task assignment policy in a server farm with a dispatcher (see Figure 3.14(a)), where jobs at each server are served in first-come-first-serve order. Consider $m$ homogeneous servers and $m$ classes of jobs. Class $i$ jobs arrive at a dispatcher according to a Poisson process with rate $\lambda_i$ and have an exponential service time distribution with rate $\mu_i$ ($\mu_i<\mu_j$ if $i<j$) for $1\leq i\leq m$. We will show in Chapter 5 that the size-based task assignment with cycle stealing under immediate dispatching, SBCS-ID, provides lower mean response time than common assignment policies. Under SBCS-ID, class 1 jobs (largest jobs) are always dispatched to server 1. For $i\geq 2$, a class $i$ job first checks to see if the $(i-1)$-th server is idle. If so, the class $i$ job is dispatched to the $(i-1)$-th server; otherwise, it is dispatched to the $i$-th server. Observe that the arrival process (of class $i$ jobs) at server $i$ depends on whether server $i-1$ is idle or not. Below, we will model the system with SBCS-ID as an RFB process.

Figure 3.14: An example of an RFB process: Size-based task assignment with cycle stealing under immediate dispatching. (a) The SBCS-ID policy. (b)-(e) Markov chains for the number of jobs at each server, where $N_j$ denotes the number of class $j$ jobs at the server. The middle row shows the Markov chains for server $1\leq i\leq m-1$, (b) when server $i-1$ has $>0$ jobs (``server 0'' is defined to have $>0$ jobs always), and (c) when server $i-1$ has $0$ jobs. The bottom row shows the Markov chains for server $m$, (d) when server $m-1$ has $>0$ jobs, and (e) when server $m-1$ has $0$ jobs.

(a) SBCS-ID

Number of jobs at server $i$ for $1\leq i\leq m-1$

(b) when server $i-1$ has $>0$ jobs

(c) when server $i-1$ has $0$ jobs

Number of jobs at server $m$

(d) when server $m-1$ has $>0$ jobs

(e) when server $m-1$ has $0$ jobs

Figures 3.14(b)-(e) show the Markov chains for the number of jobs at server $i$, conditioned on the number of jobs at server $i-1$. Specifically, Figure 3.14(b) shows the Markov chain for the number of jobs at server $i$ when server $i-1$ has $>0$ jobs, for $1\leq i\leq m-1$ (``server 0'' is defined to have $>0$ jobs always). Since server $i-1$ has $>0$ jobs, an arrival of a class $i$ job is dispatched to server $i$. Figure 3.14(c) shows the Markov chain for the number of jobs at server $i$ when server $i-1$ has $0$ jobs, for $2\leq i\leq m-1$. Since server $i-1$ has $0$ jobs, an arrival of a class $i$ job is dispatched to server $i-1$; hence there is no transition due to a class $i$ job arrival. Note that there is only one Markov chain for server 1 (Figure 3.14(b)), since the behavior (arrival and service) at server 1 is independent of the number of jobs at the other servers. Figures 3.14(d)-(e) show the Markov chains for the number of jobs at server $m$ when server $m-1$ has $>0$ jobs and when server $m-1$ has $0$ jobs, respectively. Since ``class $m+1$'' does not exist, Figures 3.14(d)-(e) have no transitions corresponding to $\lambda_{m+1}$ and $\mu_{m+1}$.

Now, it is easy to model the number of jobs in the system under SBCS as an RFB process. Here, the Markov chain at server $i$, $Q_i$, corresponds to the $i$-th process for $1\leq i\leq m$. Since $Q_1$ is a finite-phase QBD process that does not depend on other processes, it can be seen as the first process. There are two forms of infinitesimal generators for $Q_2$, depending on the number of jobs at server 1, i.e. depending on the level of $Q_1$. Thus, $Q_2$ can be seen as the second process. Likewise, $Q_i$ can be seen as the $i$-th process, since its infinitesimal generator is determined by the level of $Q_{i-1}$ for $2\leq i\leq m$. Note that the infinitesimal generator of $Q_i$ is fixed while $Q_{i-1}$ is in levels $\geq 1$ for all $i$ (i.e., $\kappa_1=\cdots=\kappa_{m-1}=1$).