Exact distribution of discrete-time D-BMAP/G/ ∞ \infty queueing model
Tonglin Liao, Youming Li · 2025
Read Exact distribution of discrete-time D-BMAP/G/ ∞ \infty queueing model by Tonglin Liao, Youming Li (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23178.txt.
Introduction
Tonglin Liao and Youming Li solve a queueing model exactly in this 2025 mathematics paper. The model describes customers who arrive in patterned batches and are served by an endless pool of servers, so no one waits for a free one. Time runs in discrete steps rather than as a smooth flow.
The authors build a Markov-style description of the system that can be handled in closed form. From it they derive the exact distribution of the number of customers present at any time, along with its averages. Computer simulations matched the formulas. As a check, they worked out the classic case of random arrivals and random service times. They then compared that step-by-step result with the well-known smooth-time version of the same queue. Exact results like these give engineers a firm base for planning systems with ample service capacity.
Catalog record
| CREATOR | Tonglin Liao, Youming Li |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 29 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-23178
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Exact distribution of discrete-time D-BMAP/G/ ∞ \infty queueing model Tonglin Liao, Youming Li Abstract In this paper, we consider discrete-time D-BMAP/G/ ∞ \infty queueing model. We construct effective discrete-time Markovian dynamics for this model and utilize it to derive exact time-dependent distribution of customer number and the corresponding moments for the original queueing model. Numerical simulations are used to verify our results. Using our result, we provide analytical distribution for discrete-time M/M/ ∞ \infty , and then compare it with the distribution of continuous-time M/M/ ∞ \infty . keywords Discrete-time queue, D-BMAP/G/ \infty queueing model, Effective Markovian dynamics, Probability generating function 1 Introduction Since Erlang’s pioneering work Erlang (1909) , there have been considerable research efforts on continuous-time queueing models, which have laid the foundation for the analysis of stochastic service systems. Queueing theory has been extensively applied to diverse domains including information technologies, transportation systems, and modern management systems, where it continues to play a pivotal role in performance optimization and system design Nazarov et al. (2014) ; Kerobyan et al. (2018) . Moreover, queueing theory has also been used in modeling and analyzing biological systems. Recent biological experiments have found non-Markovian phenomena in stochastic gene expression, and due to the great potential of queueing theory in solving non-Markovian models, many researchers studying stochastic gene expression models have begun to pay attention to this classical yet powerful field Shi et al. (2023) ; Shi et al. (2024) ; Szavits-Nossan and Grima (2024) . To model complex arrival mechanisms in real world, general arrival processes are needed. The batch Markovian arrival process (BMAP) introduced in Lucantoni (1991) is capable of capturing the batch, correlated, and bursty characteristics of real-world arrival processes Cao and Xie (2018) , and it covers a wide range of well-known arrival processes, including Poisson process (M), Phase-type renewal process (PH), Markov-modulated Poisson process (MMPP), and Markovian arrival process (MAP) Kerobyan et al. (2018) ; Schwartz (1986) ; Neuts (1979) . While continuous-time queueing models have been extensively studied in the literature, discrete-time queueing systems, whose emergence can be traced back to the year 1958 Meisling (1958) , have also attracted increasing attention for their applicability in digital communication and computer systems. In communication network, digital information is often disseminated in fixed-length “packets” Harini and Indhira (2023) , requiring a fixed-length transmission time known as slots. For example, when studying signal transmission and reception, the transmission time for a packet has been observed to be close to 5.5 ms Wu et al. (2016) , which highlights the discrete nature of such transmission processes. Due to its suitability for modeling computer systems and performance analysis, discrete-time queues have attracted considerable attention from queueing theorists and communication engineers. Most literature on discrete queueing theory focus on the analysis of single-server systems based on matrix-analytic methods Saffer and Telek (2010) ; Hunter (2014) ; Takagi and Leung (1994) ; Harini and Indhira (2023) . For example, there have been recent articles studying the application of MMBP/G/1 in communication networks Wu et al. (2016) ; Wang et al. (2011) , where MMBP refers to the Markov-modulated Bernoulli process. On the other hand, multi-server and infinite-server queueing models are equally important Schwartz (1986) due to their practical applications in various fields. For instance, discrete-time infinite-server queueing models have been used to analyze healthcare demand Worthington et al. (2020) . In this paper, we study the exact solution of the discrete-time D-BMAP/G/ \infty queueing model. The main idea is to construct the effective Markovian dynamics of the queueing model, and then solve it by classical methods to obtain the solution for the original queueing model. The paper is organized as follows: In Section 2 we introduce the discrete-time queueing model under consideration. In Section 3 we establish the effective Markovian dynamics for the queueing models. In Section 4 we provide the analytical results for D-BMAP/G/ \infty . In Section 5 we apply our results to some examples. 2 Discrete-time D-BMAP/G/ \infty In this paper we consider discrete-time queueing models with infinite servers. Different from classical continuous-time queueing models, for discrete-time queueing models, time axis is segmented into uniform intervals called time slots. The time axis is denoted by 0,1,...,t,... with t being integer, and the inter-arrival and service times are both non-negative integer-valued random variables. We are interested in the distribution of the number of customers present in the system at specific time slots. Since there are infinitely many servers, each arriving customer begins service immediately upon arrival and is assigned an independent service time. Definition 1 . Let Y be the service time of a customer taking values in {1, 2, …} with probability mass function \mathbb{P}\{Y=k\} . The survival function of the service time distribution is defined by \Phi(t)=\mathbb{P}(Y>t) . Consider a customer arriving at time slot t with service time s . Such a customer is counted at time slots t,t+1,\dots,t+s-1 . but starting from time slot t+s , the customer will no longer be counted, as its service is completed. The arrival process is governed by a discrete-time batch Markovian arrival process (D-BMAP), a versatile and mathematically tractable model for capturing correlated and bursty arrivals in discrete-time queueing systems Cao and Xie (2018) ; Saffer and Telek (2010) . The D-BMAP framework is built upon a background Markov chain whose state transitions are synchronized with possible batch customer arrivals (i.e., multiple customer arrivals per time slot). Let the state space of the background Markov chain be \{1,2,\dots\} , and we let d_{ij}(l) be the probability that there are l customer arrivals along with the transition from i to j . Then the synchronized batch customer arrivals can be fully described by a set of arrival probability matrices \{\mathbf{D}_{l}\}_{l=0}^{\infty} , where \mathbf{D}_{0} is the matrix with elements d_{ij}(0) governs transitions corresponding to no arrivals, and \mathbf{D}_{l} with l\geq 1 is the matrix with elements d_{ij}(l) that governs transitions corresponding to arrivals of batches of size l . Clearly, any D-BMAP is completely determined by the matrix sequence \{\mathbf{D}_{l}\}_{l=0}^{\infty} . Definition 2 . The matrix generating function of the \{\mathbf{D}_{l}\}_{l=0}^{\infty} is defined by D(z)=\sum_{l=0}^{\infty}\mathbf{D}_{l}z^{l}, (1) with its (i,j) -element being D_{ij}(z) defined by D_{ij}(z)=\sum_{l=0}^{\infty}d_{ij}(l)z^{l}. (2) Clearly, there exists a bijective correspondence between the matrix sequence \{\mathbf{D}_{l}\}_{l=0}^{\infty} and its generating function D(z) , and \mathbf{D}_{l} characterizes the batch size probabilities d_{ij}(l) associated with the transition from i to j . Moreover, the matrix D(1)=\sum_{l=0}^{\infty}\mathbf{D}_{l} is actually the transition probability matrix for the background Markov chain governing the queueing state, and for this reason we also write the matrix as P . We stress here that for discrete-time queueing models, when the inter-arrival time or service time distribution is described by {\rm M} using Kendall’s notation, then the distribution is actually geometrically distributed since the geometric distribution is the unique memoryless discrete distribution. Specifically, the memoryless service process means that any arrived customer completes its service in each time slot with a fixed probability, regardless of the history, making the total time of leaving follows a geometric distribution. The D-BMAP actually covers many arrival processes. For example, when a D-BMAP is constrained to allow only 0 or 1 arrivals per slot, it reduces to an Markov-Modulated Bernoulli Process (MMBP) with Wu et al.