Analysis of the waiting time distribution for polling systems with retrials and glue periods

Abstract

We consider a single-server multi-station polling system with retrials and glue periods. Just before the server arrives at a station, there is a deterministic glue period. During a glue period, arriving customers (either newly arriving customers or retrying customers) at the station stick in the queue of that station and will be served during the following service period of that station. Whereas during any other period, arriving customers at the station join the orbit of that station and will retry after an exponentially distributed time. In this paper, we derive the Laplace–Stieltjes transform of the waiting time distribution of an arbitrary customer. This transform allows us to obtain the mean and variance of the waiting time.

1 Introduction

Polling systems are queueing models where a single server visits (or polls) a finite number of stations in a prescribed order. Polling systems have been widely used to model many problems in computer-communication systems, production systems, traffic and transportation systems, and maintenance systems. A typical polling system is a system where a single server visits the stations in a cyclic order. Detailed overviews for polling systems can be found in the surveys of Boon et al. (2011), Levy and Sidi (1990) and Vishnevskii and Semenova (2006) and the books of Borst (1996) and Takagi (1986).

A service discipline determines how many customers are served during a visit of the server to a station. Many service disciplines have been considered and studied in the context of polling systems. The most commonly used service disciplines are exhaustive discipline, gated discipline, and 1-limited discipline. In this paper, the service discipline at all stations is gated. Under gated service, the server serves only the customers that were present at the start of the visit. Customers who arrive during the course of a visit, are served in the next visit.

Langaris (1997, 1999a, b) studied a multi-station polling system with retrials. In all these papers, the author obtained the mean number of retrial customers in each station at the steady state, under various service disciplines. In a single server queueing system with retrials, any customer who finds the server busy upon arrival joins an orbit, and then attempts for service after a random amount of time. For details regarding retrial queueing systems, refer to the books of Falin and Templeton (1997) and Artalejo and Gómez-Corral (2008).

In this paper we consider a polling system with retrials and glue periods. The glue period is activated just before the arrival of the server at a station. During a glue period, arriving customers (either newly arriving customers or retrying customers) at the station stick in the queue of that station and will be served during the following service period of that station. Whereas during any other period, arriving customers at the station join the orbit of that station and will retry after an exponentially distributed time. As described in the introduction section of Abidini et al. (2016, 2017), a polling system with retrials and glue periods can be used to study the performance of certain switches in optical communication systems.

Boxma and Resing (2014) first studied a polling model with retrials and glue periods. They analyzed the steady-state distribution of the number of customers in a station, when the glue periods are deterministic. The main focus of their paper was on a single server and a single station, but it also outlined how that analysis can be extended to the case of two stations. Abidini et al. (2016) considered the same model with multiple stations and then obtained the generating functions of the steady-state joint distribution of the station size (i.e., the number of customers in each station), both at the embedded points (the beginnings of glue periods, service periods and switchover periods), and at arbitrary time points. Recently, Abidini et al. (2017) studied the steady-state joint distribution of the station size for the same model as in Abidini et al. (2016), but when the glue periods are exponentially distributed.

The waiting time distribution for a polling system with retrials and glue periods is much more difficult to analyze than the station size distribution. Due to the complexity of this polling system, analytic results for the waiting time distribution are difficult to obtain, although the mean waiting times can be easily obtained with the help of Little’s formula. In this paper, we derive the Laplace–Stieltjes transform (LST) of the waiting time distribution of an arbitrary customer for the same model as in Abidini et al. (2016). This transform allows us to obtain the mean and variance of the waiting time. Also, numerical results are given to show the computations of the mean and variance of the waiting time.

The paper is organized as follows. In Sect. 2, we describe our model in detail. In Sect. 3, we provide the station size distributions at embedded points as a preliminary. In Sect. 4, we derive the LST of the waiting time distribution of an arbitrary customer. In Sect. 5, numerical results are given to show the computations of the mean and variance of the waiting time. Conclusion and suggestions for further research are given in Sect. 6.

2 The model

We consider a single server polling system with retrials and glue periods. There are $K \ge 2$ stations each with an infinite capacity. The server visits and serves the stations in a cyclic order. We index the stations by i, $i=1,\ldots ,K$, in the order of the server movement. All references to station indices greater than K or less than 1 are implicitly assumed to be modulo K. Customers arrive at station i according to a Poisson process with rate $\lambda _i$, and they are called type-i customers, $i=1,\ldots ,K$. We denote the total arrival rate by $\lambda =\lambda _1+\cdots +\lambda _K$ and the vector of arrival rates by ${\varvec{\lambda }}=(\lambda _1, \ldots ,\lambda _K)$. The service times of customers at station i are independent and identically distributed (i.i.d.) random variables with a generic random variable $B_i$, $i=1,\ldots ,K$. Let $\tilde{B}_i(s)=\mathbb {E}[e^{-sB_i}]$ be the LST of the service time distribution at station i. The switchover times from station i to station $i+1$ are i.i.d. random variables with a generic random variable $S_i$, $i=1,\ldots , K$. Let $\tilde{S}_i(s)=\mathbb {E}[e^{-sS_i}]$ be the LST of the switchover time from station i to station $i+1$. The interarrival times, the service times, and the switchover times are assumed to be mutually independent. After the server switches to station i, there is a deterministic glue period, which will be followed by the service period of station i. After the service period, the server starts switching to the next station. See Fig. 1. Let $g_i$ be the length of the glue period of station i, $i=1,\ldots ,K$.

Fig. 1

A cycle starting from the beginning of a glue period of station 1

Each station consists of an orbit and a queue. During a glue period, arriving customers (either newly arriving customers or retrying customers) at station i stick and wait in the queue of station i to receive a service during the service period of station i. Whereas during any other period, arriving customers at station i join the orbit of station i and will retry after a random amount of time. The inter-retrial time of each customer in the orbit of station i is exponentially distributed with mean $\nu _i^{-1}$, $i=1,\ldots ,K$, and is independent of all other processes.

A single server cyclically moves from one station to another serving the glued customers at each of the stations. The service discipline at all stations is gated. During the service period of station i, the server serves all glued customers in the queue of station i, i.e., all type-i customers waiting in the queue at the end of the glue period (both newly arriving customers and retrying customers during the course of the service period will not be served). The utilization of the server at station i (also called the offered load at station i), $\rho _i$, is defined by $\rho _i = \lambda _i \mathbb {E}[B_i]$, and the total utilization of the server, $\rho$, is given by $\rho =\sum _{i=1}^K \rho _i$. The system is stable if and only if $\rho <1$ (see the “Appendix” section). Therefore, we assume that $\rho <1$ for stability of the system.

3 Preliminary: station size distribution at embedded points

In this section, we briefly review the steady-state joint distributions of the number of customers in each station at embedded points. For further details, refer to Abidini et al. (2016).

Let $X_j^{(i)}$ be the number of customers in the orbit of station j (i.e., the number of type-j customers in the system) at the start of a glue period of station $i\, (i, j = 1,\ldots , K)$ in the steady state. Let $Y_j^{(i)}$ be the number of customers in the orbit of station j at the start of a service period to station $i\, (i, j = 1,\ldots , K)$ in the steady state. Let $\tilde{Y}^{(i)}$ be the number of glued customers at the start of a service period to station $i\, (i = 1,\ldots , K)$ in the steady state. Finally, $Z_j^{(i)}$ denotes the number of customers in the orbit of station j at the start of a switchover from station i to station $i + 1\, (i, j = 1,\ldots , K)$ in the steady state. Let us define the following joint generating functions of the number of customers at the start of a glue period, service period and switchover period as:

$$\begin{aligned} \Pi ^{G_i}(\mathbf{{z}})&=\mathbb {E}\left[ z_1^{X_{1}^{(i)}} z_2^{X_{2}^{(i)}}\cdots z_K^{X_{K}^{(i)}}\right] , \\ \Pi ^{V_i}(\mathbf{{z}},w)&=\mathbb {E}\left[ z_1^{Y_{1}^{(i)}}z_2^{Y_{2}^{(i)}}\cdots z_K^{Y_{K}^{(i)}}w^{\tilde{Y}^{(i)}}\right] , \\ \Pi ^{S_i}(\mathbf{{z}})&=\mathbb {E}\left[ z_{1}^{Z_{1}^{(i)}} z_2^{Z_{2}^{(i)}}\cdots z_K^{Z_{K}^{(i)}}\right] , \end{aligned}$$

for $\mathbf{{z}} = (z_1,z_2, \ldots , z_K)$ with $|z_i| \le 1$, $i=1,\ldots ,K$, and $|w| \le 1$. Then we have the following result for these joint generating functions, refer to Eqs. (3.1)–(3.3) of Abidini et al. (2016).

Proposition 1

(Abidini et al. 2016) The generating functions $\Pi ^{G_i}(\mathbf{{z}}), \Pi ^{V_i}(\mathbf{{z}},w)$, and $\Pi ^{S_i}(\mathbf{{z}})$, satisfy the following equations:

$$\begin{aligned} \Pi ^{G_i}(\mathbf{{z}})&= \Pi ^{S_{i-1}}(\mathbf{{z}}) \tilde{S}_{i-1}(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}), \\ \Pi ^{V_i}(\mathbf{{z}},w)&= \Pi ^{G_i}(f_i(\mathbf{{z}},w)) e^{g_i(\sum _{j\ne i} \lambda _j z_j +\lambda _i w -\lambda )}, \\ \Pi ^{S_i}(\mathbf{{z}})&= \Pi ^{V_i}(\mathbf{{z}}, \tilde{B}_i(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}})), \end{aligned}$$

where $f_i(\mathbf{{z}},w)=(z_1,\ldots ,z_{i-1},e^{-g_i\nu _i}z_i + (1-e^{-g_i\nu _i})w,z_{i+1},\ldots ,z_K)$.

4 The LST of the waiting time distribution

In this section, we investigate the waiting time distribution of an arbitrary customer. Let W denote a generic random variable representing the waiting time of an arbitrary customer in the steady state and let $\tilde{W}(s)=\mathbb {E}[e^{-sW}]$ be its LST.

We assume that the order of service of the glued customers within each station is first-glued first-served. We choose an arbitrary type-1 customer who arrives at station 1, and call it the tagged customer. Let $\sigma$ be the arrival epoch of the tagged customer and $\tau$ the service initiation epoch of the tagged customer. Let $A_0$ be the event that the tagged customer arrives during the glue period of station 1 and $A_1$ be the complement of event $A_0$. Note that $\mathbb {P}(A_0)=\frac{g_1}{\mathbb {E}[C]}$ and $\mathbb {P}(A_1)=1-\frac{g_1}{\mathbb {E}[C]}$, where $\mathbb {E}[C]$ is the mean cycle length. The mean cycle length is independent of the station involved (and the service discipline), and is given by

$$\begin{aligned} \mathbb {E}[C]=\frac{\sum _{i=1}^K (\mathbb {E}[S_i]+g_i)}{1-\rho }. \end{aligned}$$

Then the LST $\tilde{W}(s)$ of the waiting time distribution of the tagged customer is given by

$$\begin{aligned} \tilde{W}(s)&= \mathbb {E}[e^{-s(\tau -\sigma )}] \nonumber \\&= \frac{g_1}{\mathbb {E}[C]}\mathbb {E}[e^{-s(\tau -\sigma )}|A_0] +\left( 1-\frac{g_1}{\mathbb {E}[C]}\right) \mathbb {E}[e^{-s(\tau -\sigma )}|A_1] \nonumber \\&= \frac{g_1}{\mathbb {E}[C]}\tilde{W}^G(s)+\left( 1-\frac{g_1}{\mathbb {E}[C]}\right) \tilde{W}^{NG}(s), \end{aligned}$$

(1)

where $\tilde{W}^G(s)=\mathbb {E}[e^{-s(\tau -\sigma )}|A_0]$ and $\tilde{W}^{NG}(s)=\mathbb {E}[e^{-s(\tau -\sigma )}|A_1]$. That is, $\tilde{W}^G(s)$ is the conditional LST of the waiting time distribution of the tagged customer, given that the tagged customer arrives during the glue period of station 1. $\tilde{W}^{NG}(s)$ is the conditional LST of the waiting time distribution of the tagged customer, given that the tagged customer arrives in any other period than the glue period of station 1.

In order to obtain $\tilde{W}(s)$, we have to investigate $\tilde{W}^G(s)$ and $\tilde{W}^{NG}(s)$. The expression for $\tilde{W}^G(s)$ is given by Lemma 1, as shown below.

Lemma 1

The conditional LST $\tilde{W}^G(s)$ is given by

$$\begin{aligned} \tilde{W}^G(s)=\frac{1}{g_1}\int _0^{g_1}\Pi ^{G_1}(b_1(s,x), 1, \ldots ,1)e^{\lambda _1x(\tilde{B}_1(s)-1)-(g_1-x)s} dx, \end{aligned}$$

(2)

where $b_1(s,x)=(1-e^{-\nu _1x})\tilde{B}_1(s)+e^{-\nu _1x}$.

Proof

Assume that the tagged customer arrives during the glue period of station 1. Let x be the elapsed time of the glue period at the arrival epoch of the tagged customer (i.e., the elapsed time from the start of the glue period to the arrival of the tagged customer). The waiting time of the tagged customer is the sum of (i) the remaining time of the glue period, (ii) the service times of type-1 customers arriving during the elapsed glue period x, and (iii) the service times of type-1 customers who retry during the elapsed glue period x. Note that the LST of (i) is $e^{-(g_1-x)s}$. Also, the LSTs of (ii) and (iii) are given as follows: The number of type-1 customers arriving during the elapsed glue period x, has a Poisson distribution with mean $\lambda _1 x$. Since the generating function of the Poisson distribution with mean $\lambda _1 x$ is $e^{\lambda _1x(z-1)}$, the LST of (ii) is $e^{\lambda _1x(\tilde{B}_1(s)-1)}$. The number of type-1 customers who retry during the elapsed glue period x, has the generating function $\Pi ^{G_1}((1-e^{-\nu _1x})z+e^{-\nu _1x}, 1, \ldots ,1)$. Thus the LST of (iii) is $\Pi ^{G_1}(b_1(s,x), 1, \ldots ,1)$. Therefore, the LST of the waiting time distribution of the tagged customer, given that the tagged customer arrives during the glue period of station 1 and the elapsed glue period is x, is

$$\begin{aligned} e^{-(g_1-x)s}e^{\lambda _1x(\tilde{B}_1(s)-1)}\Pi ^{G_1}(b_1(s,x), 1, \ldots ,1). \end{aligned}$$

Since the elapsed glue period is uniformly distributed over $[0,g_1]$, given $A_0$, we obtain (2). $\square$

Now, we will find an expression for $\tilde{W}^{NG}(s)$. When the tagged customer arrives in any other period than the glue period of station 1 (i.e., given $A_1$), we define the following epochs:

• $\eta _n^{G_1}=$ the initiation epoch of the nth glue period of station 1 after the arrival of the tagged customer, $n=1,2,\ldots$,

• $\eta _n^{G_i}=$ the initiation epoch of the first glue period of station i after $\eta _n^{G_1}$, $i=2,3,\ldots ,K$, $n=1,2,\ldots$,

• $\eta _n^{V_i}=$ the initiation epoch of the first service period of station i after $\eta _n^{G_1}$, $i=1,2,\ldots ,K$, $n=1,2,\ldots$,

• $\eta _n^{S_i}=$ the initiation epoch of the first switchover period from station i (to station $i+1$) after $\eta _n^{G_1}$, $i=1,2,\ldots ,K$, $n=1,2,\ldots$.

With these notations, we define the following joint transforms: for $i=1,2,\ldots ,K$ and $n=1,2\ldots$,

$$\begin{aligned} T^{G_i,n}(s,\mathbf{{z}})&= \mathbb {E}\left[ e^{-s(\eta _n^{G_i}-\sigma )}z_1^{N_1(\eta _n^{G_i})}\cdots z_K^{N_K(\eta _n^{G_i})}\mathbb {1}_{\{\eta _n^{G_i}<\tau \}} \big | A_1\right] , \\ T^{S_i,n}(s,\mathbf{{z}})&= \mathbb {E}\left[ e^{-s(\eta _n^{S_i}-\sigma )}z_1^{N_1(\eta _n^{S_i})}\cdots z_K^{N_K(\eta _n^{S_i})}\mathbb {1}_{\{\eta _n^{S_i} <\tau \}} \big | A_1\right] , \end{aligned}$$

where $N_i(t)$ is the number of customers in the orbit of station i, excluding the tagged customer, at time t. Similarly, we define $T^{V_i,n}(s,\mathbf{{z}},w)$ as

$$\begin{aligned} T^{V_i,n}(s,\mathbf{{z}},w)&= \mathbb {E}\left[ e^{-s(\eta _n^{V_i}-\sigma )}z_1^{N_1(\eta _n^{V_i})}\cdots z_K^{N_K(\eta _n^{V_i})}w^{M(\eta _n^{V_i})}\mathbb {1}_{\{\eta _n^{V_i} <\tau \}} \big | A_1\right] , \end{aligned}$$

where M(t) is the number of glued customers at time t. Then the relations between $T^{G_i,n}(s,\mathbf{{z}}), T^{V_i,n}(s,\mathbf{{z}},w)$ and $T^{S_i,n}(s,\mathbf{{z}})$ are given by Eqs. (3)–(6). The derivation is standard, therefore it will be omitted. For $i=1,2,\ldots ,K$, and $n=1,2,\ldots$,

$$\begin{aligned} T^{V_i,n}(s,\mathbf{{z}},w)=\left\{ \begin{array}{ll} e^{-g_1(\nu _1+s)} T^{G_1,n}(s,f_1(\mathbf{{z}},w)) e^{\sum _{j=2}^K\lambda _jz_j+\lambda _1w-\lambda } &{} \hbox { if } i=1,\\ e^{-g_is}T^{G_i,n}(s,f_i(\mathbf{{z}},w))e^{\sum _{j\ne i}\lambda _jz_j+\lambda _iw-\lambda } &{} \hbox { if } i=2,\ldots ,K. \\ \end{array} \right. \end{aligned}$$

(3)

For $i=1,2,\ldots ,K$, and $n=1,2,\ldots$,

$$\begin{aligned} T^{S_i,n}(s,\mathbf{{z}})=T^{V_i,n}(s,\mathbf{{z}},\tilde{B}_i(s+\lambda -{\varvec{\lambda }} \cdot \mathbf{{z}})). \end{aligned}$$

(4)

For $n=2,3,\ldots$,

$$\begin{aligned} T^{G_1,n}(s,\mathbf{{z}})=T^{S_K,n-1}(s,\mathbf{{z}})\tilde{S}_K(s+\lambda - {\varvec{\lambda }}\cdot \mathbf{{z}}). \end{aligned}$$

(5)

For $i=2,3,\ldots ,K$, and $n=1,2,\ldots$,

$$\begin{aligned} T^{G_i,n}(s,\mathbf{{z}})=T^{S_{i-1},n}(s,\mathbf{{z}})\tilde{S}_{i-1}(s+ \lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}). \end{aligned}$$

(6)

If we let $T^{G_i}(s,\mathbf{{z}}) = \sum _{n=1}^\infty T^{G_i,n}(s,\mathbf{{z}})$, $T^{V_i}(s,\mathbf{{z}},w) = \sum _{n=1}^\infty T^{V_i,n}(s,\mathbf{{z}},w)$, and $T^{S_i}(s,\mathbf{{z}})=\sum _{n=1}^\infty T^{S_i,n}(s,\mathbf{{z}})$, then from Eqs. (3)–(6) we obtain the following lemma.

Lemma 2

The transforms $T^{G_i}(s,\mathbf{{z}}), T^{V_i}(s,\mathbf{{z}},w)$ and $T^{S_i}(s,\mathbf{{z}})$ satisfy the following equations: for $i=1,2,\ldots , K$,

$$\begin{aligned} T^{V_i}(s,\mathbf{{z}},w)&= e^{-\nu _1g_1\delta _{i1}-g_is}T^{G_i}(s,f_i(\mathbf{{z}},w)) e^{\sum _{j\ne i}\lambda _jz_j+\lambda _iw-\lambda }, \\ T^{S_i}(s,\mathbf{{z}})&= T^{V_i}(s,\mathbf{{z}},\tilde{B}_i(s+\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}})), \\ T^{G_i}(s,\mathbf{{z}})&= \delta _{i1}T^{G_1,1}(s,\mathbf{{z}}) +T^{S_{i-1}}(s,\mathbf{{z}})\tilde{S}_{i-1}(s+\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}), \end{aligned}$$

where $\delta _{i1}$ denotes the Kronecker delta.

With Lemma 2 we are able to obtain an expression for $\tilde{W}^{NG}(s)$, as shown below.

Lemma 3

The conditional LST $\tilde{W}^{NG}(s)$ is expressed as

$$\begin{aligned} \tilde{W}^{NG}(s)=\nu _1 \int _0^{g_1}T^{G_1}(s,b_1(s,x),1\ldots ,1) e^{-\nu _1x-g_1s+\lambda _1x(\tilde{B}_1(s)-1)} dx. \end{aligned}$$

(7)

Proof

Write $\tilde{W}^{NG}(s)$ as

$$\begin{aligned} \tilde{W}^{NG}(s)=\sum _{n=1}^\infty \mathbb {E} \left[ e^{-s(\tau -\sigma )}\mathbb {1}_{\{\eta _n^{G_1}<\tau \le \eta _{n+1}^{G_1}\}} \big |A_1\right] . \end{aligned}$$

For $\eta _n^{G_1}<\tau \le \eta _{n+1}^{G_1}$, the tagged customer should not start its service before $\eta _n^{G_1}$ and this customer should retry during the glue period starting from $\eta _n^{G_1}$. Assume that the tagged customer does not begin its service before $\eta _n^{G_1}$ and this customer retries during the glue period starting from $\eta _n^{G_1}$. Let $\xi$ be the retrial epoch of the tagged customer, i.e., $\xi$ is the time when the tagged customer is glued. Let x be the elapsed glue period at the retrial epoch of the tagged customer, i.e., $x=\xi -\eta _n^{G_1}$. The waiting time of the tagged customer is the sum of (i) the elapsed time from the arrival of the tagged customer to $\eta _n^{G_1}$, (ii) the glue period, (iii) the service times of type-1 customers arriving during the elapsed glue period x, and (iv) the service times of type-1 customers who retry during the elapsed glue period x. Note that the LST for the sum of (i) and (iv) is $\frac{T^{G_1,n}(s,b_1(s,x),1\ldots ,1)}{T^{G_1,n}(0,1,\ldots ,1)}$, the LST of (ii) is $e^{-g_1s}$ and the LST of (iii) is $e^{\lambda _1x(\tilde{B}_1(s)-1)}$. Therefore, we have

$$\begin{aligned}&\mathbb {E}[e^{-s(\tau -\sigma )}\vert A_1, \eta _n^{G_1}<\tau \le \eta _{n+1}^{G_1}, \xi -\eta _n^{G_1}=x] \nonumber \\&= \frac{T^{G_1,n}(s, b_1(s,x),1\ldots ,1)}{T^{G_1,n}(0,1,\ldots ,1)} e^{-g_1s+\lambda _1x(\tilde{B}_1(s)-1)}. \end{aligned}$$

(8)

Since

$$\begin{aligned} \mathbb {P}(\eta _n^{G_1}<\tau \le \eta _{n+1}^{G_1}\vert A_1)&= \mathbb {P}(\eta _n^{G_1} <\xi \le \eta _n^{G_1}+g_1 \vert A_1)\\&= \mathbb {P}(\xi>\eta _n^{G_1}\vert A_1)\mathbb {P}(\xi -\eta _n^{G_1}\le g_1 \vert \xi >\eta _n^{G_1})\\&= T^{G_1,n}(0,1,\ldots ,1)(1-e^{-\nu _1g_1}), \end{aligned}$$

and $\xi -\eta _n^{G_1}$, given $A_1 \cap \{\eta _n^{G_1}<\tau \le \eta _{n+1}^{G_1}\}$, has the probability density function $\frac{\nu _1e^{-\nu _1x}}{1-e^{-\nu _1g_1}}\mathbb {1}_{\{g_1 \ge x\}}$, it follows from (8) that

$$\begin{aligned}&\mathbb {E} \left[ e^{-s(\tau -\sigma )}\mathbb {1}_{\{\eta _n^{G_1}<\tau \le \eta _{n+1}^{G_1}\}}\big |A_1\right] \\&= \mathbb {P}(\eta _n^{G_1}<\tau \le \eta _{n+1}^{G_1}\vert A_1) \\&\quad \times \int _0^{g_1} \frac{\nu _1e^{-\nu _1x}}{1-e^{-\nu _1g_1}} \mathbb {E}[e^{-s(\tau -\sigma )} \vert A_1, \eta _n^{G_1}<\tau \le \eta _{n+1}^{G_1}, \xi -\eta _n^{G_1}=x] dx \\&=\int _0^{g_1}\nu _1 e^{-\nu _1x} T^{G_1,n}(s,b_1(s,x),1\ldots ,1) e^{-g_1s+\lambda _1x(\tilde{B}_1(s)-1)} dx. \end{aligned}$$

Adding this equation for $n=1,2,\ldots$, we obtain (7). $\square$

By Lemmas 1 and 3, (1) is written as

$$\begin{aligned} \tilde{W}(s)&= \frac{1}{\mathbb {E}[C]}\int _0^{g_1}\Pi ^{G_1}(b_1(s,x), 1, \ldots ,1)e^{\lambda _1x(\tilde{B}_1(s)-1)-(g_1-x)s} dx \\&\quad + \left( 1-\frac{g_1}{\mathbb {E}[C]}\right) \nu _1\int _0^{g_1}T^{G_1}(s,b_1(s,x),1\ldots ,1) e^{-\nu _1x-g_1s+\lambda _1x(\tilde{B}_1(s)-1)} dx. \end{aligned}$$

Therefore, in order to obtain $\tilde{W}(s)$, by Lemma 2, we need to look at $T^{G_1,1}(s, \mathbf{{z}})$.

To obtain the expression for $T^{G_1,1}(s, \mathbf{{z}})$, we define the following epochs:

• $\eta _0^{G_1}=$ the initiation epoch of the last glue period of station 1 before the arrival of the tagged customer,

• $\eta _0^{G_i}=$ the initiation epoch of the first glue period of station i after $\eta _0^{G_1}$, $i=2,3,\ldots ,K$,

• $\eta _0^{V_i}=$ the initiation epoch of the first service period of station i after $\eta _0^{G_1}$, $i=1,2,\ldots ,K$,

• $\eta _0^{S_i}=$ the initiation epoch of the first switchover period from station i (to station $i+1$) after $\eta _0^{G_1}$, $i=1,2,\ldots ,K$.

With these notations, we define the following joint transforms: for $i=1,\ldots ,K$,

$$\begin{aligned} \Phi ^{G_i}(s,\mathbf{{z}})&= \mathbb {E}\left[ e^{-s(\eta _0^{G_i}-\sigma )}z_1^{N_1(\eta _0^{G_i})}\cdots z_K^{N_K(\eta _0^{G_i})}\mathbb {1}_{\{\sigma<\eta _0^{G_i}\}} \big | A_1\right] , \\ \Phi ^{V_i}(s,\mathbf{{z}},w)&= \mathbb {E}\left[ e^{-s(\eta _0^{V_i}-\sigma )}z_1^{N_1(\eta _0^{V_i})}\cdots z_K^{N_K(\eta _0^{V_i})}w^{M(\eta _0^{V_i})}\mathbb {1}_{\{\sigma<\eta _0^{V_i}\}} \big | A_1\right] , \\ \Phi ^{S_i}(s,\mathbf{{z}})&= \mathbb {E}\left[ e^{-s(\eta _0^{S_i}-\sigma )}z_1^{N_1(\eta _0^{S_i})}\cdots z_K^{N_K(\eta _0^{S_i})}\mathbb {1}_{\{\sigma <\eta _0^{S_i}\}} \big | A_1\right] . \end{aligned}$$

Then, we have the relations between them and $T^{G_1,1}(s, \mathbf{{z}})$. Note that $\Phi ^{V_1}(s,\mathbf{{z}},w)=0$ and for $i=2,3,\ldots ,K$,

$$\begin{aligned} \Phi ^{V_i}(s,\mathbf{{z}},w)&= \mathbb {E}\left[ e^{-s(\eta _0^{V_i}-\sigma )}z_1^{N_1(\eta _0^{V_i})}\cdots z_K^{N_K(\eta _0^{V_i})} M{(\eta _0^{V_i})}\mathbb {1}_{\{\sigma<\eta _0^{G_i}\}} \big | A_1\right] \\&\quad + \mathbb {E}\left[ e^{-s(\eta _0^{V_i}-\sigma )}z_1^{N_1(\eta _0^{V_i})}\cdots z_K^{N_K(\eta _0^{V_i})} M{(\eta _0^{V_i})}\mathbb {1}_{\{\eta _0^{G_i}\le \sigma<\eta _0^{V_i}\}} \big | A_1\right] \\&= \Phi ^{G_i}(f_i(\mathbf{{z}},w)) e^{-sg_i+\sum _{j\ne i}\lambda _jz_j+\lambda _iw-\lambda } + \mathbb {P}(\eta _0^{G_i}\le \sigma<\eta _0^{V_i}|A_1) \\&\quad \times \mathbb {E}\left[ e^{-s(\eta _0^{V_i}-\sigma )}z_1^{N_1(\eta _0^{V_i})}\cdots z_K^{N_K(\eta _0^{V_i})}M{(\eta _0^{V_i})} \big | \eta _0^{G_i}\le \sigma <\eta _0^{V_i}, A_1\right] \\&= \Phi ^{G_i}(f_i(\mathbf{{z}},w)) e^{-sg_i+\sum _{j\ne i}\lambda _jz_j+\lambda _iw-\lambda } +\frac{g_i}{\mathbb {E}[C]-g_1}\Pi ^{V_i}(\mathbf{{z}},w)\frac{1-e^{-g_is}}{g_is}. \end{aligned}$$

Similarly, for $i=1,2,\ldots ,K$,

$$\begin{aligned} \Phi ^{S_i}(s,\mathbf{{z}})&= \Phi ^{V_i}(s,\mathbf{{z}},\tilde{B}_i(s+\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}))+\frac{\mathbb {E}[\tilde{Y}^{(i)}]\mathbb {E}[B_i]}{\mathbb {E}[C]-g_1} \frac{\tilde{B}_i(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}) -\tilde{B}_i(s+\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}})}{s\mathbb {E}[B_i]} \\&\quad \times \frac{\Pi ^{V_i}(\mathbf{{z}},\tilde{B}_i(s+\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}})) -\Pi ^{V_i}(\mathbf{{z}},\tilde{B}_i(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}))}{\mathbb {E}[\tilde{Y}^{(i)}](\tilde{B}_i(s+\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}) -\tilde{B}_i(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}))}. \end{aligned}$$

Also, note that $\Phi ^{G_1}(s,\mathbf{{z}})=0$ and for $i=1,2,\ldots ,K-1$,

$$\begin{aligned} \Phi ^{G_{i+1}}(s,\mathbf{{z}})&= \Phi ^{S_{i}}(s,\mathbf{{z}})\tilde{S}_i(s+\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}) \\&\quad + \frac{\mathbb {E}[S_i]}{\mathbb {E}[C]-g_1}\Pi ^{S_{i}}(\mathbf{{z}}) \frac{\tilde{S}_i(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}})-\tilde{S}_i(s+\lambda - {\varvec{\lambda }}\cdot \mathbf{{z}})}{s\mathbb {E}[S_i]}. \end{aligned}$$

Finally,

$$\begin{aligned} T^{G_1,1}(s,\mathbf{{z}})&= \Phi ^{S_{K}}(s,\mathbf{{z}})\tilde{S}_K(s+\lambda - {\varvec{\lambda }}\cdot \mathbf{{z}}) \\&\quad + \frac{\mathbb {E}[S_K]}{\mathbb {E}[C]-g_1}\Pi ^{S_{K}}(\mathbf{{z}}) \frac{\tilde{S}_K(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}})-\tilde{S}_K(s+\lambda - {\varvec{\lambda }}\cdot \mathbf{{z}})}{s\mathbb {E}[S_K]}. \end{aligned}$$

In summary, we have the following lemma.

Lemma 4

• (a) $\Phi ^{V_1}(s,\mathbf{{z}},w)=0$ and for $i=2,3,\ldots ,K$,

  $$\begin{aligned} \Phi ^{V_i}(s,\mathbf{{z}},w) = \Phi ^{G_i}(f_i(\mathbf{{z}},w)) e^{-sg_i+\sum _{j\ne i}\lambda _jz_j+\lambda _iw-\lambda } +\frac{1}{\mathbb {E}[C]-g_1}\Pi ^{V_i}(\mathbf{{z}},w)\frac{1-e^{-g_is}}{s}. \end{aligned}$$

• (b) For $i=1,2,\ldots ,K$,

  $$\begin{aligned} \Phi ^{S_i}(s,\mathbf{{z}})&= \Phi ^{V_i}(s,\mathbf{{z}},\tilde{B}_i(s+\lambda - {\varvec{\lambda }}\cdot \mathbf{{z}})) \\&\quad + \frac{1}{\mathbb {E}[C]-g_1} \frac{\Pi ^{V_i}(\mathbf{{z}},\tilde{B}_i(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}})) -\Pi ^{V_i}(\mathbf{{z}},\tilde{B}_i(s+\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}))}{s}. \end{aligned}$$

• (c) $\Phi ^{G_1}(s,\mathbf{{z}})=0$ and for $i=1,2,\ldots ,K-1$,

  $$\begin{aligned} \Phi ^{G_{i+1}}(s,\mathbf{{z}})&= \Phi ^{S_{i}}(s,\mathbf{{z}})\tilde{S}_i(s+\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}}) \\&\quad + \frac{1}{\mathbb {E}[C]-g_1}\Pi ^{S_{i}}(\mathbf{{z}}) \frac{\tilde{S}_i(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}})-\tilde{S}_i(s+\lambda - {\varvec{\lambda }}\cdot \mathbf{{z}})}{s}, \\ T^{G_1,1}(s,\mathbf{{z}})&= \Phi ^{S_{K}}(s,\mathbf{{z}})\tilde{S}_K(s+\lambda - {\varvec{\lambda }}\cdot \mathbf{{z}}) \\&\quad + \frac{1}{\mathbb {E}[C]-g_1}\Pi ^{S_{K}}(\mathbf{{z}}) \frac{\tilde{S}_K(\lambda -{\varvec{\lambda }}\cdot \mathbf{{z}})-\tilde{S}_K(s+\lambda - {\varvec{\lambda }}\cdot \mathbf{{z}})}{s}. \end{aligned}$$

The main result of this section is summarized in the following theorem.

Theorem 1

The LST of the waiting time distribution of an arbitrary customer is given by

$$\begin{aligned} \tilde{W}(s)&= \frac{1}{\mathbb {E}[C]}\int _0^{g_1}\Pi ^{G_1}(b_1(s,x), 1, \ldots ,1)e^{\lambda _1x(\tilde{B}_1(s)-1)-(g_1-x)s} dx \\&\quad + \left( 1-\frac{g_1}{\mathbb {E}[C]}\right) \nu _1 \int _0^{g_1}T^{G_1}(s,b_1(s,x),1\ldots ,1) e^{-\nu _1x-g_1s+\lambda _1x(\tilde{B}_1(s)-1)} dx, \end{aligned}$$

where $\Pi ^{G_1}(\mathbf{{z}})$ is obtained from Proposition 1, and $T^{G_1}(s,\mathbf{{z}})$ is obtained from Lemmas 2 and 4.

5 Numerical results

In this section, we present numerical results for the computations of the mean and variance of the waiting time of an arbitrary customer. By using Theorem 1, we can obtain the mean and variance of the waiting time. To illustrate the computations of the mean and variance of the waiting time, we consider the following two polling systems, both with three stations (i.e., $K=3$).

Example 1

We assume that the arrival rate of type-i customers is $\lambda _i=0.12$ for all i, $i=1,2,3$. The service times of type-i customers are exponentially distributed with means $\mathbb {E}[B_1]=1, \mathbb {E}[B_2]=2$ and $\mathbb {E}[B_3]=3$, respectively. Hence the total utilization of the server is $\rho =\sum _{i=1}^3 \rho _i=0.72<1$. The switchover times from station i to station $i+1$ are deterministic with $\mathbb {E}[S_i]=1$ for all i, $i=1,2,3$. The retrial rates of customers in the orbit of station i, $i=1,2,3$, are 3, 2 and 1, respectively. The glue period at station i is deterministic, x, i.e., $g_i=x$ for all i, $i=1,2,3$.

Example 2

We assume that the arrival rate of type-i customers is $\lambda _i=0.15$ for all i, $i=1,2,3$. The same distributions as in Example 1 are assumed for the service times of type-i customers. Hence the total utilization of the server is $\rho =\sum _{i=1}^3 \rho _i=0.9<1$. The same distributions as in Example 1 are also assumed for the switchover times, the retrial times and the glue periods.

Let $W_i$ denote the waiting time of an arbitrary type-i customer, $i=1,2,3$. In Figs. 2 and 3 we plot the mean and variance of the waiting time of an arbitrary type-i customer, $\mathbb {E}[W_i]$ and Var[$W_i$], $i=1,2,3$, for Example 1, with the parameter x of the glue period varying. In Figs. 4 and 5 we plot the mean and variance of the waiting time of an arbitrary type-i customer, $i=1,2,3$, for Example 2, with x varying.

Fig. 2

Mean waiting time of an arbitrary type-i customer, $i=1,2,3$, for Example 1

Fig. 3

Variance of the waiting time of an arbitrary type-i customer, $i=1,2,3$, for Example 1

Fig. 4

Mean waiting time of an arbitrary type-i customer, $i=1,2,3$, for Example 2

Fig. 5

Variance of the waiting time of an arbitrary type-i customer, $i=1,2,3$, for Example 2

We can assume from Figs. 2, 3, 4 and 5 that the mean and variance of the waiting time are convex in x. A number of numerical examples also support this convexity property. The mean waiting time is minimized for an appropriate x. This can be explained from the following two facts: (i) If the glue period of a station is small, the chance for customers to retry in that glue period is low, and therefore the mean waiting time is large. (ii) If the glue period of a station is large, glued customers have to wait the remaining glue period, which is likely to be long, until the beginning of service period, and so the mean waiting time is large.

6 Conclusion and suggestions for further research

We have considered a gated polling system with retrials and deterministic glue periods. Due to the complexity of this polling system, analytic results for the waiting time distribution are difficult to obtain. In this paper we have derived the Laplace–Stieltjes transform of the waiting time distribution for deterministic glue periods. From this we have obtained the mean and variance of the waiting time.

As an extension of this research, we intend to study a polling system with retrials and generally distributed glue periods. In order to study the waiting time distribution, the station size distribution needs to be analyzed first. However, there has been no studies on the station size distribution for generally distributed glue periods. Therefore, for future research, we will study the station size distribution and the waiting time distribution, when the glue periods are generally distributed.

Appendix: Stability condition

We define the periodicity of our polling system as follows: Let D be the set of all positive real numbers $\delta$ such that $\sum _{i=1}^K(g_i+S_i)$, and $B_1,\ldots ,B_K$ have their supports in $\delta \mathbb {Z}_+ =\{0,\delta ,2\delta ,\ldots \}$. Our polling system is aperiodic if the set D is empty; otherwise the polling system is periodic. When our polling system is periodic, i.e., when D is nonempty, it can be shown that D has a maximum. This maximum is the period of the polling system.

In the following proposition, we obtain the stability condition of the system.

Proposition 2

Let ${\varvec{N}}(t)=(N_1(t), \ldots , N_K(t))$, where $N_i(t)$ is the number of customers in station i at time t. Suppose that $\rho <1$. If the system is aperiodic, then ${\varvec{N}}(t)$ converges in distribution as $t\rightarrow \infty$. If the system is periodic with period d, then ${\varvec{N}}(nd)$ converges in distribution as $n\rightarrow \infty$.

Proposition 2 implies that if $\rho < 1$, then $\{\mathcal {L}({\varvec{N}}(t)): t\ge 0\}$ is tight, where $\mathcal {L}({\varvec{N}}(t))$ is the distribution of ${\varvec{N}}(t)$.

Proof of Proposition 2

Let

$$\begin{aligned} \tau _0^L=\inf \left\{ t\ge 0: \sum _{i=1}^K N_i(t)\mathbb {E}[B_i]\le L, t \hbox { is the beginning epoch of a glue period of station } 1\right\} , \end{aligned}$$

and for $n \ge 1$,

$$\begin{aligned} \tau _n^L=\inf \left\{ t>\tau _{n-1}^L: \sum _{i=1}^K N_i(t)\mathbb {E}[B_i]\le L, t \hbox { is the beginning epoch of a glue period of station } 1\right\} . \end{aligned}$$

First, we show that there exist positive real numbers L, C, and $\epsilon$ such that for all ${\varvec{l}}=(l_1,\ldots ,l_K)$ with $\sum _{i=1}^K l_i\mathbb {E}[B_i]>L$,

$$\begin{aligned}&\mathbb {E}\left[ \sum _{i=1}^K N_i(\tau _1^\infty )\mathbb {E}[B_i] \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \le (1-\epsilon )\sum _{i=1}^K l_i\mathbb {E}[B_i], \end{aligned}$$

(9)

$$\begin{aligned}&\mathbb {E}\left[ \tau _1^\infty -\tau _0^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \le C \sum _{i=1}^K l_i\mathbb {E}[B_i], \end{aligned}$$

(10)

and for all ${\varvec{l}}$ with $\sum _{i=1}^K l_i\mathbb {E}[B_i]\le L$,

$$\begin{aligned}&\mathbb {E}\left[ \sum _{i=1}^K N_i(\tau _1^\infty )\mathbb {E}[B_i] \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \le C, \end{aligned}$$

(11)

$$\begin{aligned}&\mathbb {E}\left[ \tau _1^\infty -\tau _0^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \le C. \end{aligned}$$

(12)

Note that $N_i(\tau _1^\infty ) = N_i(\tau _0^\infty )-\mathcal {D}_i+\mathcal {A}_i$, where $\mathcal {D}_i$ is the number of service completions at station i during $(\tau _0^\infty , \tau _1^\infty )$, and $\mathcal {A}_i$ is the number of arrivals at station i during $(\tau _0^\infty , \tau _1^\infty )$. Thus

$$\begin{aligned}&{\mathbb {E}\left[ {\varvec{N}}(\tau _1^\infty ) \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] }\\&\quad = {\varvec{l}}-\mathbb {E}\left[ (\mathcal {D}_1, \ldots ,\mathcal {D}_K) \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] +\mathbb {E}\left[ (\mathcal {A}_1, \ldots ,\mathcal {A}_K) \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] . \end{aligned}$$

Since

$$\begin{aligned} \mathbb {E}\left[ (\mathcal {A}_1, \ldots ,\mathcal {A}_K) \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] =\sum _{i=1}^K(g_i+\mathbb {E}[S_i]+\mathbb {E} [\mathcal {D}_i|{\varvec{N}}(\tau _0^\infty )={\varvec{l}}]\mathbb {E}[B_i]){\varvec{\lambda }}, \end{aligned}$$

we have

$$\begin{aligned}&\mathbb {E}\left[ \sum _{i=1}^K N_i(\tau _1^\infty )\mathbb {E}[B_i] \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \\&\quad = \sum _{i=1}^K l_i\mathbb {E}[B_i]-\mathbb {E}\left[ \sum _{i=1}^K \mathcal {D}_i\mathbb {E}[B_i] \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \\&\qquad +\, \sum _{i=1}^K(g_i+\mathbb {E}[S_i] +\,\mathbb {E}[\mathcal {D}_i|{\varvec{N}}(\tau _0^\infty )={\varvec{l}}]\mathbb {E}[B_i]) \sum _{i=1}^K \lambda _i \mathbb {E}[B_i] \\&\quad = \rho \sum _{i=1}^K(g_i+\mathbb {E}[S_i]) + \sum _{i=1}^K l_i\mathbb {E}[B_i] -(1-\rho )\mathbb {E}\left[ \sum _{i=1}^K \mathcal {D}_i\mathbb {E}[B_i] \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] . \end{aligned}$$

Note that

$$\begin{aligned} \mathbb {E}[\mathcal {D}_i|{\varvec{N}}(\tau _0^\infty )={\varvec{l}}] \ge l_i(1-e^{-\nu _i g_i}) \ge \min _{1\le j\le K}(1-e^{-\nu _j g_j}) l_i. \end{aligned}$$

Hence

$$\begin{aligned}&{\mathbb {E}\left[ \sum _{i=1}^K N_i(\tau _1^\infty )\mathbb {E}[B_i] \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] } \nonumber \\&\quad \le \rho \sum _{i=1}^K (g_i+\mathbb {E}[S_i])+\left( 1-(1-\rho )\min _{1\le j\le K}(1-e^{-\nu _j g_j})\right) \sum _{i=1}^K l_i \mathbb {E}[B_i] \nonumber \\&\quad = \rho \sum _{i=1}^K (g_i+\mathbb {E}[S_i])+(1-2\epsilon ) \sum _{i=1}^K l_i \mathbb {E}[B_i], \end{aligned}$$

(13)

where $\epsilon = \frac{1-\rho }{2} \min _{1\le j\le K}(1-e^{-\nu _j g_j})$. Therefore,

$$\begin{aligned} \limsup _{\sum _{i=1}^K l_i\mathbb {E}[B_i] \rightarrow \infty }\frac{\mathbb {E}\left[ \sum _{i=1}^K N_i(\tau _1^\infty )\mathbb {E}[B_i] \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] }{\sum _{i=1}^K l_i\mathbb {E}[B_i]} \le 1-2\epsilon , \end{aligned}$$

and so there exists a positive number L such that

$$\begin{aligned} \frac{\mathbb {E}\left[ \sum _{i=1}^K N_i(\tau _1^\infty )\mathbb {E}[B_i] \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] }{\sum _{i=1}^K l_i\mathbb {E}[B_i]} \le 1-\epsilon \end{aligned}$$

for all ${\varvec{l}}$ with $\sum _{i=1}^K l_i\mathbb {E}[B_i]> L$. This proves (9). We have from (13) that there exists C satisfying (11). To prove (10) and (12), we note that $\tau _1^\infty -\tau _0^\infty$ is stochastically less than the sum of $\sum _{i=1}^K (g_i+S_i)$, and the busy period with initial workload $W_0$ in the standard M / G / 1 queue (where $W_0$ has the same distribution as the workload at $\tau ^\infty _0$ in our polling system). Thus

$$\begin{aligned} \mathbb {E}\left[ \tau _1^\infty -\tau _0^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \le \frac{\sum _{i=1}^K l_i\mathbb {E}[B_i]}{1-\rho }+\sum _{i=1}^K (g_i+\mathbb {E}[S_i]). \end{aligned}$$

This proves that there exists C satisfying (10) and (12).

Next, we prove

$$\begin{aligned} \mathbb {E}[\tau _{1}^L-\tau _0^L \vert {\varvec{N}}(\tau _0^L)={\varvec{l}}]<\infty \end{aligned}$$

for all ${\varvec{l}}$ with $\sum _{i=1}^K l_i\mathbb {E}[B_i]\le L$. We can see from (9) that for ${\varvec{l}}$ with $\sum _{i=1}^K l_i\mathbb {E}[B_i]>L$,

$$\begin{aligned}&\mathbb {E}\left[ \sum _{i=1}^K N_i(\tau _n^\infty )\mathbb {E}[B_i] \mathbb {1}_{\{\tau _n^\infty <\tau _0^L\}} \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \le (1-\epsilon )^n\sum _{i=1}^K l_i\mathbb {E}[B_i]. \end{aligned}$$

(14)

Also, for ${\varvec{l}}$ with $\sum _{i=1}^K l_i\mathbb {E}[B_i]>L$, by (10),

$$\begin{aligned}&\mathbb {E}\left[ (\tau _{n+1}^\infty -\tau _n^\infty )\mathbb {1}_{\{\tau _n^\infty<\tau _0^L\}} \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \nonumber \\&\quad = \sum _{{\varvec{l}}': \sum _{i=1}^K l_i'\mathbb {E}[B_i]>L} \mathbb {E}\left[ \tau _{n+1}^\infty -\tau _n^\infty \vert {\varvec{N}}(\tau _n^\infty )={\varvec{l}}',\tau _n^\infty<\tau _0^L\right] \nonumber \\&\qquad \times \mathbb {P}({\varvec{N}}(\tau _n^\infty )={\varvec{l}}',\tau _n^\infty<\tau _0^L\vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}) \nonumber \\&\quad \le \sum _{{\varvec{l}}': \sum _{i=1}^K l_i'\mathbb {E}[B_i]>L} C\sum _{i=1}^K l_i'\mathbb {E}[B_i] \mathbb {P}({\varvec{N}}(\tau _n^\infty )={\varvec{l}}',\tau _n^\infty<\tau _0^L\vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}) \nonumber \\&\quad = C \mathbb {E}\left[ \sum _{i=1}^K N_i(\tau _n^\infty )\mathbb {E}[B_i] \mathbb {1}_{\{\tau _n^\infty <\tau _0^L\}} \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] . \end{aligned}$$

Thus, by (14),

$$\begin{aligned} \mathbb {E}\left[ (\tau _{n+1}^\infty -\tau _n^\infty )\mathbb {1}_{\{\tau _n^\infty <\tau _0^L\}} \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \le C (1-\epsilon )^n\sum _{i=1}^K l_i\mathbb {E}[B_i]. \end{aligned}$$

Hence, for ${\varvec{l}}$ with $\sum _{i=1}^K l_i\mathbb {E}[B_i]>L$,

$$\begin{aligned} \mathbb {E}\left[ \tau _0^L-\tau _0^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right]&= \mathbb {E}\left[ \sum _{n=0}^\infty (\tau _{n+1}^\infty -\tau _n^\infty )\mathbb {1}_{\{\tau _n^\infty <\tau _0^L\}} \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \nonumber \\&\le \frac{C}{\epsilon }\sum _{i=1}^K l_i\mathbb {E}[B_i]. \end{aligned}$$

(15)

Now, for ${\varvec{l}}$ with $\sum _{i=1}^K l_i\mathbb {E}[B_i]\le L$,

$$\begin{aligned}&\mathbb {E}\left[ \tau _1^L-\tau _0^L \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \\&\quad = \mathbb {E}\left[ \tau _1^\infty -\tau _0^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \\&\qquad + \sum _{{\varvec{l}}': \sum _{i=1}^K l_i'\mathbb {E}[B_i]>L} \mathbb {P}({\varvec{N}}(\tau _1^\infty )={\varvec{l}}' \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}) \mathbb {E}\left[ \tau _1^L-\tau _1^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}},{\varvec{N}}(\tau _1^\infty )={\varvec{l}}'\right] \\&\quad = \mathbb {E}\left[ \tau _1^\infty -\tau _0^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] \\&\qquad + \sum _{{\varvec{l}}': \sum _{i=1}^K l_i'\mathbb {E}[B_i]>L} \mathbb {P}({\varvec{N}}(\tau _1^\infty )={\varvec{l}}' \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}) \mathbb {E}\left[ \tau _0^L-\tau _0^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}'\right] \\&\quad \le \mathbb {E}\left[ \tau _1^\infty -\tau _0^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] + \sum _{{\varvec{l}}': \sum _{i=1}^K l_i'\mathbb {E}[B_i]>L} \mathbb {P}({\varvec{N}}(\tau _1^\infty )={\varvec{l}}' \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}) \frac{C}{\epsilon }\sum _{i=1}^K l_i'\mathbb {E}[B_i] \\&\quad \le \mathbb {E}\left[ \tau _1^\infty -\tau _0^\infty \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] + \frac{C}{\epsilon }\mathbb {E}\left[ \sum _{i=1}^K N_i(\tau _1^\infty )\mathbb {E}[B_i] \vert {\varvec{N}}(\tau _0^\infty )={\varvec{l}}\right] , \end{aligned}$$

which is finite by (11) and (12). Here we have used (15) in the second last inequality. Therefore, we have proved $\mathbb {E}[\tau _{1}^L-\tau _0^L \vert {\varvec{N}}(\tau _0^L)={\varvec{l}}]<\infty$ for all ${\varvec{l}}$ with $\sum _{i=1}^K l_i\mathbb {E}[B_i]\le L$.

Note that

• ${\varvec{N}}(t)$ is a Markov regenerative process with Markov renewal sequence $({\varvec{N}}(\tau _n^L), \tau _n^L)$.

• The Markov process ${\varvec{N}}(\tau _n^L)$ has a finite state space and is irreducible.

• The semi-Markov process (SMP) corresponding to this Markov renewal sequence is positive recurrent.

Refer to Chapter 9 of Kulkarni (1995) for further details on the theory of Markov regenerative processes, Markov renewal sequences, and SMPs.

If the polling system is aperiodic, then the SMP is aperiodic. In this case ${\varvec{N}}(t)$ converges in distribution as $t\rightarrow \infty$ (refer to Theorem 9.30 of Kulkarni 1995). If the polling system is periodic with period d, then the SMP is periodic with period d. In this case ${\varvec{N}}(nd)$ converges in distribution as $n\rightarrow \infty$. $\square$

In the following proposition, we obtain the instability condition of the system.

Proposition 3

Let U(t) be the workload at time t in our polling system. If $\rho \ge 1$, then

$$\begin{aligned} U(t) \rightarrow \infty \hbox { in distribution as } t \rightarrow \infty . \end{aligned}$$

Proposition 3 implies that if $\rho \ge 1$, then $\{\mathcal {L}(U(t)): t \ge 0\}$ is not tight, where $\mathcal {L}(U(t))$ is the distribution of U(t). This also ensures that if $\rho \ge 1$, then $\{\mathcal {L}({\varvec{N}}(t)): t\ge 0\}$ is not tight.

Proof of Proposition 3

Let $\tilde{U}(t)$ be the workload at time t in the standard M / G / 1 queue with arrival rate $\lambda$ and service time distribution $\sum _{i=1}^K \frac{\lambda _i}{\lambda }\mathbb {P}(B_i \le x)$. If $U(0)=\tilde{U}(0)$ in distribution, then $U(t) \ge \tilde{U}(t)$ stochastically for all $t \ge 0$. If $\rho \ge 1$, then $\tilde{U}(t) \rightarrow \infty$ in distribution as $t \rightarrow \infty$, and so $U(t) \rightarrow \infty$ in distribution as $t \rightarrow \infty$. $\square$