IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

A QUEUE WITH
SERVER OF WALKING TYPE

Erol GELENBE
Rudolph YASNOGORODSKY

Rapport de Recherche N° 227

Avril 1977
A QUEUE WITH SERVER OF WALKING TYPE
(AUTONOMOUS SERVICE)

Erol Gelenbe*, Rudolph Yasnogorodsky**

Résumé :

Les files d'attente avec «serveur autonome» représentent des files dans lesquelles la station de service s'absente après chaque service rendu aux clients. Elles sont utilisées en informatique pour modéliser les unités de mémoire secondaire (disques à têtes fixes ou à bras movible) qui comportent des temps d'accès ou de positionnement avant chaque transfert d'information.

Ce modèle a été étudié par Skinner [1] et par Borovkov [4] dans des cas particuliers.

Nous démontrons une formule générale permettant de calculer le temps d'attente à l'état stationnaire pour la file à serveur autonome à partir du temps d'attente à l'état stationnaire pour une file GI/G/1 qui lui correspond. Ce résultat permet d'éviter une analyse cas par cas de ce modèle, et généralise les résultats de Skinner [1]. Une application au modèle du tambour de pagination étudié par Coffman [2] est présentée.

Abstract :

Queues with autonomous service (QAS) represent service system in which server becomes una-
vailable for a random time after each service epoch. Such systems have been used to model se-
condary memory devices in computer systems (e.g. paging disks or drums). The queue with
«server of walking type» studied by Skinner [1] is a special instance of our model. This model
has also been considered by Borovkov [4].

Assuming general independent interarrival times we obtain an operational formula relating the
waiting time in stationary state of a QAS to the waiting time of the GI/G/1 queue. This result
dispenses the need for analysis of the QAS in special cases and generalizes the result of Skinner [1],
or that of Coffman [2] for a paging drum. Sufficient conditions for stability or instability of the
system are also obtained.

<footnote>* Département de Mathématiques - Université de Paris-Nord
av. J-B. Clément - 93430 - Villetaneuse</footnote>

<footnote>** IRIA-LABORIA - B.P. 105 - 78150 Le Chesnay.</footnote>
<figure><img src="image_2.png" /></figure>

# 1. Introduction

We examine a single server, first-come-first-served service center to which customers arrive according to a renewal process. Let $A_1, A_2, \dots, A_n, \dots$ denote the interarrival times, and denote by $s_1, s_2, \dots, s_n, \dots$ the service times of the successive customers. After serving the n-th customer, the server becomes for a time $T_n \ge 0$. We write $S_n \equiv s_n+T_n, n \ge 1$, and assume that $S_1, S_2, \dots, S_n, \dots$ is a sequence of i.i.d. (independent and identically distributed) random variables, independent also of the interarrival times.

Suppose that the queue becomes empty after the departure of the k-th customer (end of a busy period) at time $\tau_k$; the server becomes once again available for service at times $\tau_k+\bar{S}_1, \tau_k+\bar{S}_1+\bar{S}_2, \dots, \tau_k+\bar{S}_1+\bar{S}_2+\dots+\bar{S}_n, \dots$. That is, service will resume for the $(k+1)$-th customer at time

$$ \tau_k + \sum_{i=1}^{\ell(a_{k+1})} \bar{S}_i $$

where $\ell(a_{k+1}) := \inf \{ \ell : \sum_{i=1}^{\ell} \bar{S}_i \ge a_{k+1} \equiv \sum_{i=1}^{k+1} A_i \}$.

We assume that $\bar{S}_1, \bar{S}_2, \dots, \bar{S}_n, \dots$ are i.i.d. random variables independent of the $S_n, A_n, n \ge 1$. Notice that we are assuming that when the queue becomes empty it becomes unavailable except for instant of time $\bar{S}_1, \bar{S}_1+\bar{S}_2, \dots$ when service may begin, just like the case when the queue is full, except that we allow $\bar{S}$ to be different from S, where S and $\bar{S}$ are the random variables representing any clement in the sequence $S_n$ or $\bar{S}_n, n \ge 1$, respectively.

The model we consider arises in many applications. In computer systems [2,3,5] it serves as a model of a paging drum (in this case $S = \bar{S}$). In data communication systems it can represent a data transmission facility in which
transmissions can only begin at certain predetermined instants of time.

Using the terminology of Skinner [1] who analyzed the model assuming Poisson arrivals, we shall call it a queue with server of walking type : after each service the server "takes a walk". Borovkov [4] calls this model a queue with "autonomous service".

The purpose of this paper is to obtain a general formula relating the waiting time of the n-th customer in our model $W_n$, to the waiting time of the n-th customer $V_n$ in an equivalent GI/G/1 queue, $n \ge 1$. This equivalent GI/G/1 queue has the same arrival process, but the service times are $S_1, S_2, ... , S_n, ...$. This general result allows us to dispense with a special analysis of our queueing model in stationary state since we can obtain the result directly from the known analysis of the corresponding GI/G/1 queue.

The formula (Theorem 4) is derived in Section 2. Sufficient conditions for ergodicity are derived in Section 3, and Section 4 contains an application to the paging drum model.
## 2. Properties of the waiting time process

Consider the consequence $W_1, W_2, \dots, W_n, \dots$ where $W_n$ is the waiting time of the n-th customer arriving to the queue. We shall first prove that the $W_n, n \ge 1$, satisfy a simple recurrence relation. Let $\xi_n = S_n - A_n, n \ge 1$.

### Theorem 1

$$ (1) \quad W_{n+1} = \eta (-W_n - \xi_n), n \ge 1 $$

where $\eta(\cdot)$ is defined by

$$ \eta(x) = \begin{cases} -x & \text{if } x \le 0 \\ \sum_{i=1}^{\ell(x)} \bar{s}_i - x, & \text{if } x > 0 \end{cases} $$

where we define for $x > 0$:

$$ (2) \quad \ell(x) = \inf \{ \ell : \sum_{i=1}^{\ell} \bar{s}_i \ge x, \ell > 0 \} $$

*Proof:* The n-th customer arrives to the queue at time $\sum_{i=1}^{n} A_i$ and begins service at $\sum_{i=1}^{n} A_i + W_n$. The server will then be once again available (for the (n+1)-th customer) at time $\sum_{i=1}^{n} A_i + W_n + S_n$. Therefore

$$ (3) \quad W_{n+1} = \begin{cases} \sum_{i=1}^{n} A_j + W_n + S_n - \sum_{i=1}^{n+1} A_j, & \text{if } W_n + S_n - A_{n+1} \ge 0 \\ \ell(A_{n+1} - W_n - S_n) \bar{s}_j - (A_{n+1} - W_n - S_n) & \text{if } W_n + S_n - A_{n+1} < 0 \end{cases} $$

where $\ell(x)$ is defined in (2).

This can be rewritten as

$$ (4) \quad W_{n+1} = \begin{cases} W_n + \xi_n & \text{if } W_n + \xi_n \ge 0 \\ \ell(-W_n - \xi_n) \bar{s}_j - (-W_n - \xi_n) & \text{if } W_n + \xi_n < 0 \end{cases} $$

which is the formula (1) given in the theorem.
As a consequence of Theorem 1 we have the following result.

**Lemma 2** If $E\xi_n > 0$ for $n \ge 1$ then $W_n \to \infty$ with probability 1 as $n \to \infty$.

**Proof** : Notice from (1) that $\eta(x) \ge -x$ for all $x$ with probability 1.

If $x \le 0$ the statement is obvious. Since $\eta(x) \ge 0$ with probability 1 it follows that $\eta(x) \ge -x$ if $x > 0$. Therefore, by Theorem (1) we have
$$W_{n+1} \ge W_n + \xi_n, n \ge 1$$

Therefore $W_{n+1} \ge \sum_{i=1}^{n} \xi_n$, $n \ge 1$. If $E\xi_n > 0$, then the sum on the RHS converges with probability 1 to $+\infty$ as $n \to \infty$.

Henceforth we shall assume that $E\xi_n < 0$ for all $n \ge 1$.

**Remark 3.**

It is now clear that $W_1, W_2, \dots, W_n, \dots$ is a Markov chain since $\xi_1, \xi_2, \dots, \xi_n, \dots$ is a sequence of i.i.d. random variables and $\eta(\cdot)$ is a random function which depends on $\overline{S}_1, \overline{S}_2, \dots$ which are i.i.d. random variables.

We shall now study the characteristic function $Ee^{itW_{n+1}}$ for the waiting time process. Using (1) we have, for any real $t$

$$ (5) \quad \begin{aligned} Ee^{itW_{n+1}} = Ee^{it(W_n + \xi_n)} & \quad I[W_n + \xi_n \ge 0] \\ & + \sum_{k=0}^{\infty} Ee^{it(W_n + \xi_n + \sum_{l=1}^{k+1} \overline{S}_l)} \\ & \quad \cdot I[W_n + \xi_n + \sum_{l=1}^{k+1} \overline{S}_l \ge 0, 0 > W_n + \xi_n + \sum_{l=1}^{k} \overline{S}_l] \end{aligned} $$
where $I[P]$ is the indicator function of the predicate $P$: it is 1 if $P$ is true and 0 otherwise. Notice that we may write:

$$ (6) \quad Ee^{itW_{n+1}} = Ee^{it(W_n + \xi_n)} - Ee^{it(W_n + \xi_n)} \quad I[W_n + \xi_n < 0] $$

$$ \sum_{k=0}^{\infty} Ee^{it(W_n + \xi_n + \Sigma_l^{k+1} \bar{s}_i)} \quad I[W_n + \xi_n + \Sigma_l^{k+1} \bar{s}_i \ge 0, 0 > W_n + \xi_n + \Sigma_l^k \bar{s}_i] $$

and

$$ (7) \quad \sum_{k=0}^{\infty} Ee^{it(W_n + \xi_n + \Sigma_l^{k+1} \bar{s}_i)} \quad I[W_n + \xi_n + \Sigma_l^{k+1} \bar{s}_i \ge 0, 0 > W_n + \xi_n + \Sigma_l^k \bar{s}_i] $$

$$ \begin{aligned} & \sum_{k=0}^{\infty} Ee^{it(W_n + \xi_n + \Sigma_l^{k+1} \bar{s}_i)} \quad I[W_n + \xi_n + \Sigma_l^k \bar{s}_i < 0] \\ & - \sum_{k=0}^{\infty} Ee^{it(W_n + \xi_n + \Sigma_l^{k+1} \bar{s}_i)} \quad I[W_n + \xi_n + \Sigma_l^{k+1} \bar{s}_i < 0] \end{aligned} $$

since the two series on the right-hand-side are absolutely convergent, which will be shown at the end of this Section. We now group together the second term of the RHS of (6) with second term on the RHS of (7) to obtain:

$$ (8) \quad Ee^{itW_{n+1}} = Ee^{it(W_n + \xi_n)} + \sum_{k=0}^{\infty} Ee^{it(W_n + \xi_n + \Sigma_l^{k+1} \bar{s}_i)} $$

$$ \begin{aligned} & \sum_{k=0}^{\infty} Ee^{it(W_n + \xi_n + \Sigma_l^k \bar{s}_i)} \\ & - \sum_{k=0}^{\infty} Ee^{it(W_n + \xi_n + \Sigma_l^{k+1} \bar{s}_i)} \quad I[W_n + \xi_n + \Sigma_l^k \bar{s}_i < 0] \end{aligned} $$
$it\bar{s}$

Let $f(t) = Ee$

Then

$$
(9) \quad Ee^{itW_{n+1}} = Ee^{it(W_n + \xi_n)} + [f(t)-1] \sum_{k=0}^{\infty} Ee^{it(W_n + \xi_n + \sum_{l=1}^k \bar{s}_i)} \\
\phantom{(9) \quad Ee^{itW_{n+1}} = Ee^{it(W_n + \xi_n)} + [f(t)-1] \sum_{k=0}^{\infty} } \cdot I \left[ W_n + \xi_n + \sum_{l=1}^k \bar{s}_i < 0 \right]
$$

We are now ready to establish the main result of the paper. For the
time being we _assume_ that the Markov chain $W_1, W_2, \dots, W_n, \dots$ is ergodic.
We shall prove below a sufficient condition for ergodicity which is
$E\xi_n < 0$ for all $n \ge 1$.

**Theorem 4**

Suppose that the Markov chain $W_1, W_2, \dots, W_n, \dots$ is ergodic : then

$W = \lim_{p \to \infty} W_n$ is a proper random variable.

It is given by

$W = V + \gamma$

where $V = \lim_{n \to \infty} V_n$ and

$$
\gamma = \lim_{p \to \infty} \sum_{i=1}^{\ell(x)} \bar{s}_i - x
$$

That is, $\gamma$ is the (limiting) forward recurrence time of the renewal process
$\bar{s}_1, \bar{s}_1+\bar{s}_2, \dots, \bar{s}_1+\dots+\bar{s}_n, \dots$. Furthermore $\gamma$ is independent of $V$.

$$
It is well known that $P[\gamma<x] = \int_0^x [1 - F_{\bar{s}}(y)] \, dy / E\bar{s}
$$

**Proof :** Define
$$ \phi_n(t) = \sum_{k=0}^{\infty} e^{it(W_n + \xi_n + \Sigma_l^k \bar{S}_i)} $$

$$ \cdot I \left[ W_n + \xi_n + \Sigma_l^k \bar{S}_i < 0 \right] = \int_{-\infty}^{0^-} e^{itx} d\left\{ \sum_{k=0}^{\infty} P \left[ W_n + \xi_n + \Sigma_l^k \bar{S}_i < x \right] \right\} $$

Introduce the following relation :

$$ \psi_n(t) = e^{itW_n} g(t) = e^{it\xi} $$

Then (9) becomes

$$ \psi_{n+1}(t) = \psi_n(t) g(t) + (f(t)-1) \phi_n(t) $$

Suppose that $\lim_{n \to \infty} \phi_n = \phi$ exists, as has been assumed. Then $\lim_{n \to \infty} \psi_n = \psi$
also exists and we may write

$$ \psi(t) (1-g(t)) = (f(t)-1) \phi(t) $$

We now call upon a result of BOROVKOV [2] ; if $E\xi < 0$,
(Chapter 4, p. 103, equation (1)) :

$$ (1-g(t)) = \frac{P(V=0)}{Ee^{itV}} [1 - e^{itX}] $$

where X is a negative random variable. Therefore we may write, for a negative
random variable X,

$$ \psi(t) \frac{P(V=0)}{Ee^{itV}} [1 - e^{itX}] = (f(t)-1) \phi(t) $$

Or

$$ (10) \quad \frac{\psi(t) P(V=0) it}{(f(t)-1) Ee^{itV}} = \frac{it\phi(t)}{1-Ee^{itX}} $$

Notice that

$$ (11) \quad \phi_n(t) = \int_{-\infty}^{0^-} e^{ity} dE_n(y) $$

where
$$ (12) \quad G_n(y) \equiv \sum_{k=0}^{\infty} P \left[ W_n + \xi_n + \sum_{l=1}^{k} \bar{S}_l < y \right] $$

Thus the series on the RHS converges uniformly for all $y < 0$ (see Appendix I) and therefore $G_n(y)$ is a continuous function of $y$ for $y < 0$. It is obviously an increasing function of $y$ and $G_n(-\infty) = 0$ and $G_n(0^-) < \infty$, since for $y < 0$

$$ P \left[ W_n + \xi_n + \sum_{l=1}^{k} \bar{S}_l < y \right] < P \left[ \xi_n + \sum_{l=1}^{k} \bar{S}_l < 0 \right] $$

because $W_n \ge 0$. Therefore $G_n(y)$ is of bounded variation for $y < 0$. Thus we have established that $\phi_n(t)$ is a continuous function of $t$.

Consider the LHS of (10). $\psi(t)$, $f(t)$ and $Ee^{itV}$ are characteristic functions of positive random variables; they are therefore analytic in the upper half-plane $(\partial M(t) > 0)$ and continuous on the real line and bounded. Consider the RHS of (10). $\phi(t)$ is the characteristic function of a negative random variable (see (11)) and so is $Ee^{itX}$; therefore the RHS of (10) is analytic on the lower half-plane $(\partial M(t) < 0)$ and continuous on the real line and bounded. Therefore by the theorem of Liouville the expression (10) is a constant, call it $C$. Let us write :

$$ \psi(t) = \frac{C (f(t)-1)}{it P(V=0)} Ee^{itV} $$

Taking

$$ 1 = \psi(0) = \frac{C \overline{ES}}{P(V=0)} $$

Therefore $C = P(V=0)/\overline{ES}$ and we have

$$ (13) \quad \psi(t) = \frac{f(t)-1}{it\overline{ES}} Ee^{itV} $$
Formula (13) is the result since $(f(t)-1)/it\bar{E}\bar{S}$ is the characteristic function of $\gamma$ the limiting forward recurrence time of the renewal process $\bar{s}_1, \bar{s}_1+\bar{s}_2, \dots, \bar{s}_1+\bar{s}_2+\dots+\bar{s}_n, \dots$

Set $W_n = x$ in (7). We had assumed above that the two series on the right-hand-side of (7) are uniformly convergent on $R^+$ as functions of $x$; we now prove this last point.

$$ \begin{aligned} & \left| \sum_{k=0}^{\infty} Ee^{it(x+\xi_n + \Sigma_1^{k+1} \bar{s}_i)} \right| \\ & \le \sum_{k=0}^{\infty} P[x+\xi_n + \Sigma_1^k \bar{s}_i < 0] \\ & < \sum_{k=0}^{\infty} P[\xi_n + \Sigma_1^k \bar{s}_i < 0] = \mathrm{EH}(-\xi) \end{aligned} $$

where $H(\cdot)$ is the renewal function for the renewal process $\bar{s}_1, \bar{s}_1+\bar{s}_2, \bar{s}_1+\bar{s}_2+\bar{s}_3, \dots$ and $\mathrm{EH}(-\xi)$ is the expectation of $H(-\xi)$ with respect to the random variable $\xi$. But $H(y)$, which is the expected number of renewals in $[0,y[$ for $y > 0$ (and is zero for $y \le 0$), is bounded by a function $a$ + by for $a, b \ge 0$. This completes the proof since a similar argument can be applied to the second series.

### 3. Sufficient conditions for ergodicity of the waiting time process

In this section we shall prove the following. Let us point out that it has been shown (Lemma 2) that $E \xi_n < 0$ is a necessary condition for ergodicity.

**Theorem 5** : If $E \xi_n < 0$ then $\{W_n\}$ is ergodic.

**Proof** : Define

$$ \psi(x,t) \equiv E \left[ e^{itW_{n+1}} \mid W_n = x \right] $$
Using (9) we have :

$$
(14) \quad \psi(x,t) = \mathrm{Ee} \sum_{k=0}^{\infty} \int_{0}^{\infty} e^{\int (x+\xi_n) \cdot f(t)-1} \sum_{l=1}^{k} \int_{0}^{\infty} e^{\int (x+\xi_n+\Sigma_l^k \bar{S}_i)} \cdot I[x+\xi_n+\Sigma_l^k \bar{S}_i < 0] \, d\bar{S}_i
$$

$$
. I \left[ x + \xi_n + \sum_{i}^{k} \bar{S}_i < 0 \right] \}
$$

Let P(x,A), for x ∈ R⁺ and A ⊆ R⁺, denote the transition probability of {W_n}:

$$
P(x,A) = P \left[ W_{n+1} \in A \mid W_n = x \right]
$$

Clearly

$$
\psi(x,t) = \int_{0}^{\infty} e^{ity} P(x,dy)
$$

Therefore from (14)

$$
(15) \quad E \left[ W_{n+1} \mid W_n = x \right] = \frac{1}{i} \left. \frac{\partial \psi(x,t)}{\partial t} \right|_{t=0}
$$

$$
= x + E\xi + E\bar{S} \int_{-\infty}^{0} \int_{k=0}^{\infty} P \left[ x + \xi + \Sigma_{1}^{k} \bar{S}_{i} < y \right] d\Sigma
$$

$$
= x + E\xi + \overline{ES} \sum_{k=0}^{\infty} P \left[ x + \xi + \Sigma_{1}^{k} \bar{S}_{i} < 0 \right]
$$

$$
= x + E\xi + \overline{ES}.EH(-x-\xi)
$$

where EH(-x-ξ) is the expectation with respect to ξn of H(-x-ξ). It is well
known that there exist α > 0, β > 0 such that for any y

$0 \le H(y) < \alpha y + \beta$

Therefore

$$
0 \le EH(-x-\xi) = \int_{-\infty}^{-x} H(-x-y) \, dF_{\xi}(y)
$$

$$
0 \le EH(-x-\xi) \le (-\alpha x + \beta) F_{\xi}(-x) - \alpha \int_{-\infty}^{-x} y dF_{\xi}(y)
$$

As $x \to \infty$, both terms on the right-hand side tend to zero; thus

$$
\lim_{x \to \infty} EH(-x-\xi) = 0
$$

and there exists for each $\delta > 0$ an $x_0 > 0$ such that

$$
\overline{ES} \ E H(-x - \xi) \le \delta, \text{ for } x > x_0
$$
or

$$ \int_{\mathbb{R}^+} yP(x,dy) \le x + E\xi + \delta, \text{ for } x > x_0 $$

In particular, choose $\delta$ such that $\delta < |E\xi|$ and write

$$ (16) \quad \int_{\mathbb{R}^+} yP(x,dy) \le x - (|E\xi| - \delta), \text{ for } x > x_0 $$

Now choose a function $g(y)$:

$$ g(y) = \frac{y}{(|E\xi| - \delta)} $$

so that (16) yields

$$ (17) \quad \int_{\mathbb{R}^+} g(y) P(x,dy) \le g(x) - 1, \text{ for each } x > x_0 $$

Construct the compact set $K = [0, x_0]$ and notice from (16) that for each $x \in K$

$$ (18) \quad \int_{\mathbb{R}^+} g(y) P(x,dy) = g(x) + E\xi + \overline{E\xi}.EH(-\xi + \frac{x}{|E\xi|-\delta}) $$

is bounded. Thus {$w_n$} with $E\xi < 0$ satisfies a theorem of Tweedie (Theorem 4.2 of [6]) which states that {$w_n$} is ergodic if there exists a compact set K and a measurable function $g(\cdot)$ such that

$$ (i) \quad \int_{\mathbb{R}^+} g(y) P(x,dy) \le g(x)-1, \text{ for each } x \notin K $$

$$ (ii) \quad \int_{\mathbb{R}^+} g(y) P(x,dy) \text{ is bounded for each } x \in K $$

provided that {$w_n$} is an irreducible Markov chain on a topological space (in this case $(\mathbb{R}^+, \mathbb{J})$) and provided $P(x, \cdot)$ is continuous in x. +)

By (17) and (18) conditions (i) and (ii) are satisfied. $P(x, \cdot)$ is continuous in x because $\psi(x,t)$ is continuous in x.

### 4. Application to a paging drum model

In this section we shall apply the theoretical results obtained in the

<footnote>+) The chain is irreducible provided that for each x and each Borel set A, $P^n(x,A) > 0$ for some n.</footnote>
previous sections to a model arising in the analysis of computer system
behaviour [2,3,5]. Here the customers are requests for the transfer of
**pages** (blocks of information of fixed size) from a paging drum (a secondary memory
device used in computer systems). For the purpose of efficiency, described
in [2,3,5], page requests are addressed to one of N sector queues ; each
paging drum sector when traversed permits to deliver one page. Since the
paging drum rotates at constant speed, if T is the time for one complete rota-
tion then one page will be transfered in time T/N and service at this
particular sector queue will not be available for a time T(N-1)/N until the
paging drum can be once again positioned at the beginning of the same
sector.

Let W be the stationary waiting time at a sector queue with general
independent interarrivals, and V be the stationary waiting time of the
corresponding GI/D/1 queue with constant service time T. We then have :

**Theorem 6** : If $EA < T$ ($Eξ < 0$) then W and V are proper random variables related
by the formula

$W = V + Y$

where V and Y are independent and Y is uniformly distributed in [0,T].

In particular we can obtain the average waiting time for the case of
Poisson arrivals derived by Coffman [2] :

$$
EW = \frac{T}{2} + \frac{T}{2(1-\lambda T)}
$$

where $\lambda$ is the arrival rate of transfer requests.
Clearly, the response time R (waiting time plus service time) is simply

$$R = V + Y + \frac{T}{N}$$
REFERENCES

1. Skinner, C.E. "A priority queueing model with server walking type," *Operations Research* Vol. 15 (1967), pp. 278-285.

2. Coffman, E.G., "Analysis of a drum input-output queue under scheduled operation", *JACM* Vol. 16, n°1 (1969), pp. 73-90.

3. Gelenbe, E., Lenfant, J., Potier, D., "Response time of a fixed-head disk to transfer of variable length", *SIAM J. on Computing* Vol. 4, n°4 (1975), pp. 461-473.

4. Borovkov, A.A., "Stochastic Processes in Queueing Theory", Springer-Verlag, New York, 1976.

5. Fuller, S.H., Baskett, F., "An analysis of drum storage units", Tech. Rep. 29, Digital Syst. Lab. Stanford University, Stanford, Cal. (1972).

6. Tweedie, R.L., "Sufficient conditions for ergodicity and recurrence of Markov chains on a general state-space", *Stochastic Processes and Their Applications* Vol. 3, pp. 385-403, 1975.