Abstract
We investigate a discretetime twoqueue system with a single server. At the beginning of every time slot, the single server randomly selects either queue 1 or queue 2 to serve. The decision of the server to select either queue 1 or queue 2 in each time slot is independent of the state of the system and is determined by a single parameter. The service times of the customers are deterministically equal to 1 time slot. The numbers of arrivals into both queues during consecutive slots are characterized by a joint probability generating function. By extending prior research, we analyze the behavior of the system as the number of customers in the first queue approaches infinity, thereby obtaining exact asymptotics for the stationary joint probability distribution of customer numbers in both queues.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
This paper studies the stationary joint distribution of the system contents of a discretetime twoqueue system with one server that uses a randomly alternating scheduling discipline.
A randomly alternating scheduling discipline means that the server randomly switches between queues, independent of the number of customers present at each queue. Multiqueue systems where a single server selects a queue for service according to some rule are commonly referred to as polling systems. There is a substantial body of literature on various polling mechanisms; for comprehensive reviews and applications (up to 2021), see (Borst 2018; Vishnevsky and Semenova 2021). However, studies of polling systems with a randomly alternating service discipline are relatively scarce. To the best of our knowledge, the first analysis of such a polling system appeared in de Haan et al. (2009). In that study, the authors investigated a continuoustime multiqueue system where the server remains at each queue for an exponentially distributed time before switching, regardless of the number of customers, and allows for generally distributed switchover times. This type of scheduling discipline was initially referred to as the autonomousserver discipline (Al Hanbali et al. 2012), and later as the pure (exponential) timelimited policy (De Haan et al. 2020). This model has been primarily motivated by the need to evaluate the performance of (mobile) ad hoc networks. In Saxena et al. (2017); Kapodistria et al. (2023), the authors have focused on the twoqueue version of de Haan et al. (2009) but without switchover times.
The motivation to study the discretetime queueing model of the present paper stems from earlier work, starting with Devos et al. (2019). In our model, the server randomly alternates between serving queue 1 and queue 2 in the following way. In each discrete time step, the server is allocated to queue 1 or queue 2 with probabilities denoted as \(\alpha \) and \(1  \alpha \), respectively. The service time of any customer in either queue is equal to 1 time slot, ensuring that service is nonpreemptive. The arrival process is characterized by specifying the numbers of arrivals, in both queues during consecutive slots, instead of the discrete interarrival times. It is assumed that the numbers of arrivals in both queues during consecutive slots are i.i.d. with any given joint probability generating function, denoted as A(x, y). Note that the numbers of arrivals in both queues during a slot may be dependent.
We assume that the two queues, which are \(Geo^X/D/1\) queues with Bernoulli interruptions when viewed in isolation (Bruneel and Kim 1993, Ch. 3.2), are stable. We focus on the stationary joint distribution of the system contents. However, an exact analysis of this model is extremely hard for a general joint arrival distribution because the system contents in this queueing model correspond to a twodimensional random walk in the positive quadrant. Notice that this random walk has state transitions between nonneighboring states since an arbitrary number of customers can arrive in any slot in each of the two queues for general joint arrival distribution. Interested readers are directed to Cohen and Boxma (1983); Fayolle et al. (2017) for both an overview and a thorough examination of this topic. The most prominent techniques to date for computing the steadystate joint distribution of the system contents (if possible) include the boundaryvalue approach, the compensation method, the uniformization method, and the powerseries technique. A recent overview of these four approaches is given in the introduction of Bruneel and Devos (2023).
This paper’s contribution is finding the exact asymptotics of the stationary joint distribution of the system contents. Therefore, the results presented in this work are closely related to the asymptotic analysis of twodimensional Markov chains. One of the main challenges in this analysis is that, in general, no analytical expression for the joint probability generating function is available. Despite this difficulty, the tail asymptotic problem for twodimensional queueing models has been extensively investigated over the past two decades, particularly in the context of nearestneighbor random walks. There are mainly three alternative methods to study tail asymptotics for stationary distributions, namely largedeviations theory, matrixanalytic methods, and complexfunction methods. Readers interested in a more exhaustive review of the literature are directed to Miyazawa (2011), which provides an extensive survey up to 2011, complemented by recent advancements discussed in Ozawa (2022) and Zhao (2022).
Our approach in the present paper relies on ideas developed by Bruneel and Devos (2023), who studied a system of two parallel queues, each having their dedicated server, and where arrivals in both queues during consecutive slots are i.i.d. with a common probability generating function denoted as A(x, y). The approach in Bruneel and Devos (2023) considers the steadystate behavior of the system under the condition that the content of queue 1 becomes very high (approaches infinity). This conditional system, referred to as the “asymptotic system” in Bruneel and Devos (2023), turns out to be nearly identical to the original (unconditional) system, but with a modified joint arrival probability generating function that can be explicitly computed from A(x, y). This approach yielded exact asymptotics for the stationary joint distribution of the system contents. The approach avoids the intricacies of analytic continuation, as seen in complexfunction methods (Li and Zhao 2011, 2018; Zhao 2022), by focusing on the conditional asymptotic behavior of the twoqueue system when one queue becomes temporarily overloaded. Standard singularity analysis is then applied to the resulting conditional transforms.
A significant distinction between Bruneel and Devos 2023 and the current study is the presence of an additional stochastic process, namely the state of the single server determining which queue gets access to the server during each slot. Whereas Bruneel and Devos (2023) involves a single source of coupling between the two queues, the current study deals with two sources of coupling. Despite this additional difficulty, we are able to obtain a similar result to that presented in Bruneel and Devos (2023), namely that the asymptotic behavior of our system remains of the same type as the original system: independent arrivals from slot to slot and independent server allocations from slot to slot, but with modified parameters that can be explicitly calculated from the original system parameters. Furthermore, in this asymptotic system, the arrival process and the state of the server remain statistically independent. This is the main motivation and novelty of this paper, namely to show that the technique in Bruneel and Devos (2023) can be extended to coupled queues involving also stochasticity at the output of the system.
The paper is structured as follows: Section 2 presents preliminary results for the model. Section 3 outlines the mathematical focus, proving our main result, detailed in Section 4. Section 5 discusses the conditions under which this result holds true. Section 6 illustrates our methodology through specific examples of arrival distributions. Finally, Section 7 concludes by suggesting further extensions of our approach.
2 Preliminaries
2.1 Mathematical Model and Basic Notations
In the present paper we aim to study a discretetime queueing model with two queues with infinite capacity and sharing one server, shown in Fig. 1. Since time is assumed to be discrete, the time axis is divided into fixedlength intervals referred to as (time) slots. Within each slot, the server is exclusively available to one of the two queues. We assume that the server is available to queue 1 during a slot with probability \(\alpha \), independently from slot to slot. Consequently, the server is available to queue 2 during a slot with probability \(1\alpha \). Finally, we assume that each customer’s service requires precisely one slot.
We are concerned with the system contents in both queue 1 and queue 2, where the system content refers to the number of customers in the queue, including the customer currently being served (if any). The system contents at the beginning of slot k are denoted by \(u_{1,k}\) and \(u_{2,k}\), with the first index \(*\) of \(u_{*,k}\) distinguishing between the two queues. The evolution of \(\{u_{1,k}, u_{2,k} \}\) is defined by the system equations:
In our notation, \((x)^+\) denotes \(\max (0, x)\), and \(\{a_{1,k}, a_{2,k}\}\) represents a sequence of i.i.d. nonnegative discrete random vectors. These vectors share a common joint probability generating function (PGF) denoted as \(A(z_1, z_2)\)., i.e.,
Additionally, \(\{r_k\}\) constitutes a sequence of i.i.d. Bernoulli random variables with parameter \(\alpha \). The random variable \(r_k\) models the number of available servers (0 or 1) for queue 1 during slot k. The random variables \(a_{1,k}\) and \(a_{2,k}\) are to be understood as the numbers of arrivals during slot k at queue 1 and queue 2, respectively. Notice that we incorporate the possibility that the numbers of arrivals in different queues (within a slot) are correlated. We furthermore define the marginal PGF of the number of arrivals in queue j per slot as
We also denote the mean number of arrivals in queue j per slot by \(\lambda _j = A_j^{\prime }(1)\).
To ensure stability, it is assumed that
The stability conditions are intuitively clear. The average number of customers entering a queue should be strictly less than the average number of customers that can be served from the queue, per slot. These stability conditions can for instance be found in Chapter 3.2 of Bruneel and Kim (1993).
Finally, denote with
the steadystate joint PGF of the process \(\{u_{1,k},u_{2,k}\}\). By \((u_1,u_2)\) we denote a pair of random variables with this joint PGF.
2.2 Known Results for the Singlequeue Model
In Kendall notation, queue 1 (resp. queue 2) is a discretetime \(Geo^X/D/1\) queue with Bernoulli interruptions, with the PGF of the number of arrivals in a slot equal to \(A_1(z)\) (resp. \(A_2(z)\)) and singleslot service times. Let us denote the PGF of the stationary system content \(u_j\) by \(U_j(z)\). The PGF \(U_j(z)\) can be expressed as (see for instance Chapter 3.2 of Bruneel and Kim (1993))
The objective of this paper is to examine the joint system under the condition that the first queue is heavily populated. Consequently, our initial focus is on the probabilities \(\Pr [u_1=n]\) as \(n \rightarrow \infty \). To establish a formal proof, we introduce the following assumption:
Assumption 1
(Wellbehaved distribution). The PGF \(A_1(z)\) has a radius of convergence \(\Omega _1>1\) and \(\lim _{z\rightarrow \Omega _1} A_1(z) = +\infty \).
It is noteworthy that this assumption holds for a wide range of commonly encountered discrete probability distributions, such as the Poisson, Bernoulli, binomial, and geometric distributions. Throughout the remainder of this paper, we refer to PGFs that satisfy Assumption 1 as “wellbehaved” PGFs.
Thanks to Assumption 1, it can be shown that the denominator of Eq. 5 has exactly one real positive zero, defined as \(\tau _1\), such that \(1<\tau _1<\Omega _1\), which has multiplicity 1. In general, the value of \(\tau _1\) is implicitly defined by the equation and constraint:
Using classical arguments, it follows that the dominant singularity of \(U_1(z)\) is \(\tau _1\) and that this singularity is a simple pole. The negative of the residue at this pole is given by
Hence, it follows that as \(n \rightarrow \infty \)
where \(\sim \) means that
The approximation (9) is commonly referred to as the “dominantpole approximation” of \(\Pr [u_1 =n]\), see for example Van Mieghem 1996.
3 Conditional Arrival Process and Service Process
It is clear that an extreme length of queue 1 is due to either a high number of arrivals and/or limited service in queue 1 during the previous slots. Both scenarios affect the evolution of queue 2.
To study the behavior of the second queue under the condition that the first queue is large, we first concentrate on obtaining the joint arrival and service process conditioned on the event that the content of queue 1 is large. The rationale behind this approach is that the system content in queue 2 at the beginning of a slot is a function of the arrivals and services before this slot.
More specifically, consider an arbitrary slot S in a steady state. A formal proof will be given below to show that for every natural number m,
where
The result (10) shows that the numbers of arrivals in both queues follow a modified joint distribution with PGF \(\tfrac{A(x \tau _1,y)}{A_1(\tau _1)}\) and the states of the server follow a modified Bernoulli distribution with PGF R(w), both of which are independent and identically distributed. Additionally, the arrival process and service process are mutually independent.
3.1 A Useful Recurrence Relation
For brevity, let us define for any natural number \(m\) and \(j\in \{1,2,\ldots ,m\}\):

\(\textbf{w}_{j:m} = (w_j, w_{j+1}, \ldots , w_m)\) the vector of \(w\) values with indices ranging from j to \(m\),

\(\textbf{x}_{j:m} = (x_j, x_{j+1}, \ldots , x_m)\) the vector of \(x\) values with indices ranging from j to \(m\),

\(\textbf{y}_{j:m} = (y_j, y_{j+1}, \ldots , y_m)\) the vector of \(y\) values with indices ranging from j to \(m\).
In the remainder, we will always assume that
Let us now introduce the joint PGF \(V_{m,S}\) of the random variables \( r_{S\ell }, a_{1, S\ell }, a_{2, S\ell }\), \(\ell =1\), \(\ldots ,m\) and \(u_{1,S}\):
The multivariate functon \(V_{m,S}\) has \(3m +1\) arguments. Using the system equation (1), we get the following recursive relation:
Because the slot S is a random slot in steady state, the function \(V_{m,S}\) does not explicitly depend on the choice of the slot S (Bruneel and Devos 2023). Consequently, the functions \(V_{m,S_1}\) and \(V_{m,S_2}\) are identical for any slots \(S_1\) and \(S_2\) in steady state. Therefore we may omit the subscript S, i.e.,
In view of Eq. 14, we obtained the following recursive relation:
3.2 Dominant Singularity of \(V_m\) and its Residue
Recall that by definition, see Eq. 13,
The functon \(V_1\) can be explicitly computed using the same technique as to derive the recurrence relation for \(V_m\). One finds that
Now since \(S1\) is a slot in steady state, the PGF of \(u_{1,S1}\) is given by Eq. 5. We find that
Consider the variables \(w_1\), \(x_1\) and \(y_1\) fixed such that \(w_1\le 1\) \(x_1\le 1\), \(y_1\le 1\). In this case, Eq. 16 implies that the univariate function \(z \mapsto V_1(w_1,x_1,y_1,z)\) admits \(\tau _1\) as unique dominant singularity. This singularity is a simple pole. We can compute the negative of the residue at this pole:
where the function R is defined in Eq. 11.
We have demonstrated that the dominant singularity of \(V_1\) is \(\tau _1\), a simple pole. We prove by induction that this is also the case for \(V_m\), for every m. Suppose that this is true for \(n=1,2,\ldots , m1\). Considering the recurrence relation (15) we see that the possible singularities of \(V_m\) are the singularities of \(V_{m1}\) and \(A(x_1z, y_1)\). Notably, it is worth mentioning that \(z=0\) is a removable singularity of \(V_m\) due to \(\lim _{z \rightarrow 0} z V_m(z) = 0\). Because of the induction hypothesis, \(\tau _1\) is a singularity of \(V_{m1}\). Hence, \(\tau _1\) is a singularity of \(V_{m}\) as well. This singularity is the dominant singularity of \(z \mapsto V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)\) since
We now calculate the negative of the residue of \(z \mapsto V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)\) at \(\tau _1\). We begin with
where, in the first equality we applied (15), and in the last equality, we multiplied the numerator and denominator by \(A_1(\tau _1)\) and used the fact that, cf. Eq. 7:
Solving the recursive equation (18) yields
where \(b_1\) is defined in Eq. 8.
3.3 Asymptotics
From Section 3.2, it follows that for fixed \(w_j\le 1\) \(x_j\le 1\), \(y_j\le 1\), the principal part at \(z=\tau _1\) of the function \(z \mapsto V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)\) is given by
implying that the coefficients \(\{[z^n] V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z) \}_{n=0}^{\infty }\) of the power series expansion of the function \(z \mapsto V_{m}(\textbf{w}_{1:m},\textbf{x}_{1:m},\textbf{y}_{1:m},z)\) satisfy
By applying the law of total expectation, it is apparent that
Hence, in view of (21),
as \(n \rightarrow \infty \). By combining (20) and (22) with
as shown in (9), we derive our main result:
3.4 Summary of the Results
To begin, let us define the following notations:
Using Eq. 19, we can now express R(w), as defined in Eq. 11, as follows:
Conditioned on \(u_{1,S} \rightarrow \infty \), our analysis yields the following notable results:

1.
The arrivals into the two queues during the slots preceding slot S are independent and identically distributed with common joint PGF \(A^*(x,y)\).

2.
The states of the server during the slots preceding slot S are independent and identically distributed with common Bernoulli distribution with parameter \(\alpha ^*\).

3.
The state of the server is independent of the arrivals into the two queues during the slots preceding slot S.
4 Main Result for the System Contents in the Alternating Service Model
In the preceding section, we established that when the system content \(u_1\) at the beginning of a random slot in steady state is sufficiently large, the arrivals into the twoqueue system in previous slots are (approximately) independent from slot to slot. Moreover, the arrival process is characterized by a joint PGF \(A^*(x,y)\), as defined in Eq. 24. Additionally, the server’s state during previous slots follows a Bernoulli process with parameter \(\alpha ^*\), as defined in Eq. 25, and this service process is independent of the arrival process. Hence, this implies that conditioned on \(u_{1,S}\rightarrow \infty \), the arrival process to the second queue is described by an independent arrival process characterized by the PGF \(A^*(1,y)\) and the interruptions constitute a Bernoulli process with parameter \(1\alpha ^*\), for an infinite number of slots preceding slot S. We thus observe that the conditional system content in queue 2 in our queueing system is equal to the system content in an equivalent queueing system. This equivalent system is also a discretetime \(Geo^X/D/1\) queue with Bernoulli interruptions but with an adjusted arrival and interruption process. This equivalent queueing system can be stable or unstable. Let us denote
then the stability condition of the equivalent queueing system reads:
If the inequality (27) is fulfilled, the conditional distribution of \(u_{2,S}\) given \(u_{1,S}=n\), \(n\rightarrow \infty \), exists and its PGF is given by, cf. Eq. 6,
In terms of \(A(z_1,z_2)\) and \(\alpha \), this PGF can be expressed as,
where in the last equality, we rewrote the first factor using the following identities:
From the PGF (28), moments and tail probabilities can be calculated. For instance, the mean value is given by
Tail probabilities can be calculated using singularity analysis. The most common and easiest case is when the dominant singularity of \(z \mapsto \lim _{n \rightarrow \infty } \text {E}[z^{u_{2,S}}  u_{1,S} = n]\) is given by the smallest real zero of the denominator in Eq. 28. This is the case if \(A(\tau _1,z)\) is wellbehaved in the sense of Assumption 1. In all the examples we have examined, \(\frac{A(\tau _1 x, y)}{A_1(\tau _1)}\) has the same form as A(x, y) (by which we mean that it is the PGF of the same parametric family of distributions), ensuring that \(A(\tau _1,z)\) is wellbehaved in these examples.
Let us assume that \(A(\tau _1, z)\) is wellbehaved. In this case, we have that
as \(\ell \rightarrow \infty \), where \(\sigma \) is the smallest positive real zero of \(\tau _1 z  [(1\alpha )\tau _1 + \alpha z ]A(\tau _1,z)\) and
Notice that \(\sim \) in (30) means
Finally, using the asymptotic (9) and the wellknown fact that \(\Pr [u_1=n, u_2 = \ell ] = \Pr [ u_2 = \ell  u_1=n] \Pr [u_1=n] \), we obtain that
Hence for large \(\ell \) and n we can approximate the joint stationary distribution of the system contents as
Concluding this section, it is important to note that the two limits in (32) do not commute. Interchanging the roles of queue 1 and queue 2, by conditioning on the event \(u_{2,S}= \ell \) as \(\ell \rightarrow \infty \), leads to a different outcome. Assuming a similar condition for \(A_2(z)\) as Assumption 1, one obtains that
where \(\tau _2\) is the smallest positive real zero of the denominator of \(U_2(z)\) given in Eq. 6. Now it can be seen that the dominant singularity of the function above is in general not the same as the function (28). In the most common case, assuming that \(A_1(z)\) satisfies Assumption 1, the former is given by the smallest positive real zero, say \(\delta \), of \(\tau _2 z  [(1\alpha )z + \alpha \tau _2 ]A(z,\tau _2)\). Without any symmetry, for example if \(\alpha =1/2\) and \(A(z_1,z_2)=A(z_2,z_1)\) there is no reason that \(\delta \) is the same as \(\sigma \). Hence, for some constant e, we have that
and for some constant \(b_2\), cf. (9),
implying
Assuming that the order of the limits is irrelevant, then this would yield a different result than (32), which is impossible. Hence, we can conclude that the limits do not commute.
5 Discussion of the Asymptotic Stability Condition
The asymptotic stability condition (27) is always fulfilled when the numbers of arrivals in both queues are independent, i.e. \(A(z_1,z_2)=A_1(z_1)A_2(z_2)\). Indeed, in this case we have that
where we used the stability condition (3) of the original system in the first inequality, and in the last inequality we used the fact that \(A_1(\tau _1)<\tau _1\), which follows from Eq. 7.
When the numbers of arrivals in both queues are dependent, i.e. \(A(z_1,z_2)\) is not of a product form, it is not possible to draw general conclusions. In the case of negative correlation between the arrivals in queue 1 and queue 2, and given that the server can only serve one queue at a time, we expect queues 1 and 2 to exhibit complementary behavior, in the sense that \(u_2\) typically takes small values when \(u_1\) takes high values, and vice versa. Consequently, it is plausible to conjecture that the asymptotic stability condition (27) is always fulfilled for negatively correlated arrivals. However this conjecture is incorrect. A counterexample is given by the following PGF:
The idea in the construction of this counterexample was to include a small probability that there can occur a large number of arrivals in both queues, but that the covariance is still negative. Additionally, for the sake of completeness, it is also possible to find examples with positive correlation between the arrivals in queue 1 and queue 2 that violate condition (27), such as:
Finally, we note that even if the stability condition (27) is not met, meaningful statements about the system contents can still be made, albeit in less detail. One approach, consistent with the methodology of this paper, involves utilizing singularity analysis to approximate transient characteristics in queueing systems (Walraevens et al. 2009). In Bruneel (1991), the transient system content at the beginning of slots is analyzed for a discretetime \(Geo^X/D/1\) queue with Bernoulli interruptions. By applying the approach of Walraevens et al. (2009) to the formulas available in Bruneel (1991), we can for example derive approximate results for the mean system content in an unstable system as the number of slots goes to infinity. However, we believe that the case where the stability condition is met is the most interesting to consider. Therefore, our focus in the examples below will exclusively be on scenarios where the stability condition is satisfied.
6 Examples and Discussion
The main result (28) in this paper can be applied to various types of PGFs \(A(z_1,z_2)\), provided that Assumption 1 and stability condition (27) are satisfied. Below, we will discuss some specific applications of the method in detail, focusing on particular choices of the distribution of the arrivals. We investigate three types of arrival processes: independent Bernoulli arrivals, independent geometric arrivals, and independent Poisson arrivals. The first two examples are selected to facilitate the analytical calculation of \(\tau _1\). However, while this analytical approach is not obligatory, it is advantageous for the exposition of the results. The third type of arrival process is included to demonstrate that, while numerical work is required, it remains minimal.
6.1 Independent Bernoulli Arrivals
Let us assume that the arrivals \(a_{1,k}\) and \(a_{2,k}\) constitute two independent sequences of independent and identically Bernoulli distributed random variables such that
The value \(\tau _1\), defined in Eq. 7, is in this case given by
It is then an easy exercise to compute the adjusted arrival PGF \(A^*(x,y)\) from Eq. 24:
The adjusted PGF \(A^*(1,z)\) defined in Eq. 24 equals of course \(A_2(z)\), because the numbers of arrivals in queue 1 and queue 2 are independent. The adjusted interruption parameter \(\alpha ^*\) defined in Eq. 25 is now given by
We can observe that the arrival rate \(\lambda _1\) and the interruption parameter \(\alpha \) are simply interchanged. This result, which may seem simple, has already been long discovered for the continuoustime M/M/1 queue. An example of this can be found in Shwartz and Weiss (1995): The way an M/M/1 queue becomes saturated is that for a long time, the arrival rate and service rate are interchanged. In our case, since the singlequeue Bernoulli model with singleslot service times can also be seen as a singlequeue model with geometric service times, the first queue is a discretetime Geo/Geo/1 queue. Therefore, we observe that we have the same remarkable property as its continuoustime equivalent: the way the first queue builds up is by changing the arrival probability and successful transmission probability for an infinite duration of time.
Furthermore, by simply replacing \(\alpha \) by \(\lambda _1\) in Eq. 6, we obtain the following expression for the asymptotic conditional PGF:
By canceling the common factor \((z1)\) in numerator and denominator, writing down the corresponding Taylor series expansion and by equating coefficients, it follows that
Hence, as \(n \rightarrow \infty \), we get for \(\ell = 1,2,\ldots \)
As mentioned in the introduction, it is worth noting that there are very few cases where an explicit expression for the joint PGF of \(u_1\) and \(u_2\) can be derived, and the case of independent Bernoulli arrivals is one of them (see Devos et al. (2020)). Equation (54) of Devos et al. (2020) provides the expression for the joint distribution of \(u_1\) and \(u_2\). By using this equation, we can obtain the same asymptotic as Eq. 34, which is expected. The high accuracy of formula Eq. 34 for large n, is demonstrated through a specific example shown in Fig. 2, where it is compared against the exact results from Devos et al. (2020).
Table 1 summarizes various results for \(\Pr [u_1=n, u_2 = \ell ]\) with the parameters \(\lambda _1 = 0.2\), \(\lambda _2 = 0.5\), and \(\alpha = 0.3\).
6.2 Independent Geometric Arrivals
Let us assume that the arrivals \(a_{1,k}\) and \(a_{2,k}\) constitute two independent sequences of independent and identically geometrically distributed random variables such that
We emphasize that, in contrast to the previous example, no explicit expression is known for \(U(z_1,z_2)\) for this specific \(A(z_1,z_2)\).
The value \(\tau _1\) defined in Eq. 7 and the adjusted interruption parameter \(1\alpha ^*\) from Eq. 25 are given by
and
respectively. Since \(A^*(1,z)=A_2(z)\), we obtain the asymptotic conditional PGF of interest by simply replacing \(1\alpha \) with \(1\alpha ^*\) in Eq. 6, yielding
The expression above is the PGF of a geometrically distributed random variable with parameter \( \tfrac{\lambda _2}{1\alpha }(1 \alpha + \lambda _1)\). Hence we immediately obtain that
Furthermore, as \(n \rightarrow \infty \), we get for \(\ell = 0,1,2,\ldots \)
We demonstrate the accuracy of formula (35) for large n through a particular example depicted in Fig. 3, where a comparison is made with simulation results. We emphasize that generating simulation results for joint probabilities \(\Pr [u_1 = n = u_2 = \ell ]\) with high values of n or \(\ell \), or both, is extremely timeconsuming due to the rarity of these events. In contrast, evaluating the closed formula (35) is instantly obtained by just substituting the parameter values into the expression.
Table 2 summarizes various results for \(\Pr [u_1=n, u_2 = \ell ]\) with the parameters \(\lambda _1=0.25\), \(\lambda _2=0.6\), \(\alpha =0.3\).
6.3 Independent Poisson Arrivals
In this last example, the numbers of arrivals in both queues during consecutive slots are two independent sequences of independent and identically Poisson distributed random variables such that
The value \(\tau _1\) can only be determined numerically, as Eq. 7 is now a transcendental equation in \(\tau _1\):
Once \(\tau _1\) is computed numerically, \(\alpha ^*\) is given by Eq. 25. Then, in the asymptotic system, queue 2 behaves as a stable singleserver queue with 1slot service times, Poisson arrivals with mean \(\lambda _2\) and Bernoulli interruptions with parameter \(1\alpha ^*\), implying that the PGF of the queue2 system content exist and is given by, see Eq. 28,
Let us take a look at the dominant singularity of this (conditional) PGF. The denominator of Eq. 36 has exactly one real positive zero in the interval \(]1, \infty [\). In accordance with Section 4, we denote this zero as \(\sigma \). As outlined in Section 4, we have the following approximation for the stationary joint distribution of the system contents:
where the constants \(b_1\) and d are in this case given by, see Eqs. 8 and 31,
Unlike the previous two examples,, the values \(\tau _1\) and \(\sigma \) have to be calculated using a numerical method, e.g. the NewtonRaphson method. However, the computational time involved in this numerical method is negligible both absolutely and relative to the time required for simulation. The approximation is again very accurate, as demonstrated in Figure 4 and Table 3, where a comparison is made with simulation. We observe that the approximation for \(\Pr [u_1=n, u_2=1]\) is less accurate compared to the previous two examples of arrival PGFs. This is because, in the earlier cases, we had exact expressions for \(\lim _{n \rightarrow \infty } \Pr [u_2 = \ell  u_1=n]\), whereas here we approximated this limiting probability using the dominantpole technique, as explained in Section 4.
7 Conclusion and Further Research
We derived analytical asymptotic formulas for the stationary joint distribution of the system contents. Hereto we used and extended the ideas and techniques as in Bruneel and Devos (2023) such as first studying the arrivals and services when conditioning on one of the two queue contents. The evaluation of the expressions requires minimal effort, as only the root of a nonlinear equation needs to be calculated. As an illustration we applied our method to some specific choices of \(A(z_1,z_2)\). For example, in the case where at most one customer can arrive in each queue during a slot, independently of each other, the exact joint stationary distribution has been reported previously in the literature. Our results in this case align with previous calculations, confirming the effectiveness of our approach.
A crucial step in our analysis is having the explicit expression (16), which represents the joint PGF of \(r_{S1}\), \(a_{1,S1}\), \(a_{2,S1}\) and \(u_{1,S}\), with S being a random slot in steady state. This was made possible by having an explicit expression for the PGF of \(u_{1,S1}\), see Eq. 5. We believe that the basic idea of our method, which is to consider a random slot S in steady state and to analyze the underlying stochastic processes describing the queueing system in the slots preceding S, can be extended to other discretetime twoqueue models where the stationary distribution of at least one marginal system content is known.
Further research includes extending the approach to more complex coupled queues. For example, one such candidate is the randomly alternating service system with its workconserving variant, i.e. the server is always assigned to a nonempty queue (Vanlerberghe et al. 2016; Walraevens et al. 2010). In this model, the marginal PGFs of the system content are no longer known. However, the PGF of the total system content is known due to the workconserving property. Therefore, it may be beneficial to condition on the event that the total system content becomes large instead of focusing on a single queue. Another possible extension to explore is investigating whether the method can be extended to a system with more than two queues. However, a system with more than two queues introduces additional complexities due to the presence of multiple types of conditioning. For instance, scenarios may arise where all queues except one become saturated, or where only one queue becomes saturated. Addressing these variations would require further refinement and adaptation of the methodology, potentially involving novel analytical techniques.
Data Availability
No datasets were generated or analysed during the current study.
References
Al Hanbali A, de Haan R, Boucherie RJ, van Ommeren JK (2012) Timelimited polling systems with batch arrivals and phasetype service times. Annals Operations Res 198(1):57–82
Borst S (2018) Polling: past, present, and perspective. Top 26(3):335–369
Bruneel H (1991) Exact derivation of transient behavior for buffers with random output interruptions. Comput Netw ISDN Syst 22(4):277–285
Bruneel H, Devos A (2023) Asymptotic behavior of a system of two coupled queues when the content of one queue is very high. Queueing Syst 3(3–4):189–232
Bruneel H, Kim BG (1993) Discretetime models for communication systems including ATM. Kluwer Academic Publisher, Boston
Cohen JW, Boxma OJ (1983) Boundary value problems in queueing system analysis. NorthHolland, Amsterdam
de Haan R, Boucherie RJ, van Ommeren JK (2009) A polling model with an autonomous server. Queueing Syst 62(3):279–308
De Haan R, Al Hanbali A, Boucherie RJ, Van Ommeren JK (2020) Transient analysis for exponential timelimited polling models under the preemptive repeat random policy. Adv Appl Probability 52(1):32–60
Devos A, Walraevens J, Fiems D, Bruneel H (2020) Analysis of a discretetime twoclass randomly alternating service model with Bernoulli arrivals. Queueing Syst 96(1–2):133–152
Devos A, Fiems D, Walraevens J, Bruneel H (2019) An approximate analysis of a Bernoulli alternating service model. In: Queueing Theory and Network Applications: 14th international conference, QTNA 2019, Ghent, Belgium, August 2729, 2019, Proceedings 14 (pp. 314329). Springer International Publishing
Fayolle G, Iasnogorodski R, Malyshev VA (2017) Random walks in the quarterplane: algebraic methods, boundary value problems. SpringerVerlag, Berlin, Applications to queueing systems and analytic combinatorics
Kapodistria S, Saxena M, Boxma OJ, Kella O (2023) Workload analysis of a twoqueue fluid polling model. J Appl Probability 60(3):1003–1030
Li H, Zhao YQ (2011) Tail asymptotics for a generalized twodemand queueing model  a kernel method. Queueing Syst 69(1):77–100
Li H, Zhao YQ (2018) A kernel method for exact tail asymptotics  random walks in the quarter plane. Queueing Models Serv Manag 1(1):95–129
Miyazawa M (2011) Light tail asymptotics in multidimensional reflecting processes for queueing networks. TOP 19(2):233–299
Ozawa T (2022) Tail asymptotics in any direction of the stationary distribution in a twodimensional discretetime QBD process. Queueing Syst 102(1):227–267
Saxena M, Boxma OJ, Kapodistria S, Nunez Queija R (2017) Two queues with random timelimited polling. Probability Math Stat 37(2):257–289
Shwartz A, Weiss A (1995) Large deviations for performance analysis: queues, communication and computing. Chapman and Hall, New York
Van Mieghem P (1996) The asymptotic behavior of queueing systems: large deviations theory and dominant pole approximation. Queueing Syst 23(1–4):27–55
Vanlerberghe J, Maertens T, Walraevens J, De Vuyst S, Bruneel H (2016) On the optimization of twoclass workconserving parameterized scheduling policies. 4ORA Quarterly J Operations Res 14(3):281–308
Vishnevsky V, Semenova O (2021) Polling systems and their application to telecommunication networks. Mathematics 9(2):117
Walraevens J, Fiems D, Moeneclaey M (2009) Using singularity analysis to approximate transient characteristics in queueing systems. Probability Eng Inf Sci 23(2):333–355
Walraevens J, van Leeuwaarden JSH, Boxma OJ (2010) Power series approximations for twoclass generalized processor sharing systems. Queueing Syst 66(2):107–130
Zhao YQ (2022) The kernel method tail asymptotics analytic approach for stationary probabilities of twodimensional queueing systems. Queueing Syst 100(1):95–131
Funding
No funds, grants, or other support was received.
Author information
Authors and Affiliations
Contributions
A.D. wrote the main manuscript text. H.B. and J.W. reviewed the manuscript.
Corresponding author
Ethics declarations
Competing interests
The authors declare no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author selfarchiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Devos, A., Walraevens, J. & Bruneel, H. Analysis of A Twoqueue Discretetime Model with Random Alternating Service Under High Occupancy in One Queue. Methodol Comput Appl Probab 26, 43 (2024). https://doi.org/10.1007/s11009024101097
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11009024101097