Skip to main content

Deterministic Arrivals Queues (D/G/K)


Following the work of Gupta et al it is natural to ask whether the gap phenomenon persists to other similar types of queues such as ones with different arrivals processes. It might have been hoped that taking a deterministic arrivals process, so that one of the sources of randomness in the queue is removed, could give us an improvement. However, by extending/adapting the proofs of Gupta we have found that even in this most simple of cases the gap persists.

We are therefore interested in fixing the first two moments of the job-size distribution $X$. By a time scaling we may assume wlog that the first moment is 1 and take the second moment to be $C^2$. To look at the gap we define the following notation. The gap is then taken to be the difference between these two values.

$ W^{C^2}_h(D) := \sup_G\{\mathbb{E}[W^{D/G/K}] | \mathbb{E}[X] = 1, \mathbb{E}[X^2] = C^2 + 1, \text{where} X \sim G\}$
$W^{C^2}_l(D) := \inf_G \{ \mathbb{E}[W^{D/G/K}] | \mathbb{E}[X] = 1, \mathbb{E}[X^2] = C^2 + 1, \text{where} X \sim G\}$


By adapting and extending the proofs of Gupta we were able to obtain the following results:

Theorem 1: Lower Traffic

For $0< \rho < \frac{K-1}{K}$ and finite $C^2 > 0$
$W_l^{C^2}(D) = 0$
$ W^{C^2}_h(D) \geq (C^2+1)\mathbb{E}\left[W^{Ge((C^2+1)d,1/(C^2+1))\:/\:D\:/\:K}\right] $

Theorem 2: Higher Traffic

For \frac{K-1}{K}\leq \rho < 1 and finite C^2 > 0
$ W^{C^2}_h \geq \frac{(C^2+1)}{2}\mathbb{E}\left[W^{Ge\left(\frac{d(C^2+1)}{2},\frac{2}{C^2+1}\right)\:/\:M/K}\right]$
$\liminf_{\tilde{C}\downarrow C}W^{\tilde{C}^2}_l(D)\leq \mathbb{E}[W^{M/M/K}] + \frac{1}{1-\rho}\left[\rho - \frac{K-1}{K}\right]\frac{C^2-1}{2} + 1$

Sketch proof

In particular, the results of Theorem 1 and the sup result of Theorem 2 can be obtain quickly my mirroring the procedures in the proofs of Gupta. Due to the increased complexity of the proof used by Gupta for the final result we chose to try to leverage this result in its original form rather than mirroring it. To do this we found a sequence of job-size distributions $F_\epsilon$ which give a sequence of D/G/K queues that are bounded by a sequenece of M/G/K queues used in the Gupta proof of the Markovian case.

The procedure to achieve this is as follows and can be visualised by the animation below where each square/rectangle is a job from the arrivals process which will be entering the system. Along the horizontal axis is the time that the jobs are created. Clicking the buttons will move through the different steps of the bounding procedure.

$\mathbb{E}[W^{D/F^{(\epsilon)}/K}]$ Start with a compound deterministic queue
$ = \mathbb{E}[W^{\begin{smallmatrix} Ge_s\\Ge_l\end{smallmatrix}/\begin{smallmatrix}M_s\\M_l\end{smallmatrix}/K_{[B]}}]$ Consider as two independant geometric arrivals processes with a queueing discipline that batched jobs which arrive simulatensouly (ie they are served by the same server)
$\leq \mathbb{E}[W^{\begin{smallmatrix} Ge_s\\Ge_l\end{smallmatrix}/\begin{smallmatrix}M_s\\M_l\end{smallmatrix}/K_{[FCFS]}}] + 1 $ Change queueing discipline back to first come first serve
$\leq\mathbb{E}[W^{\begin{smallmatrix} M_s\\M_l\end{smallmatrix}/\begin{smallmatrix}M_s\\M_l\end{smallmatrix}/K}]+1$ Bound geometric arrivals with exponential arrivals  
$= \mathbbE[W^{M/H^{(\epsilon)}/K}]+1$ Merge exponential arrivals processes to obtain queues from the proof in Gupta
$=\mathbb{E}[W^{M/M/K}] + \frac{1}{1-\rho}\left[\rho - \frac{K-1}{K}\right]\frac{C^2-1}{2} + 1$ Substitute in Gupta's results
start seperate unbatch exponential merge

Back to main page