Classification of Discrete-Time Queues
Muhammad El-Taha · 2025
Read Classification of Discrete-Time Queues by Muhammad El-Taha (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-2509-01696.txt.
Introduction
Muhammad El-Taha sorts waiting line systems that run in discrete time steps into clear classes. A queue here is a line of jobs waiting for service, tracked step by step rather than in smooth time. His classes rest on how jobs are scheduled and when the line is observed. When observed waits match true waits, a system is coherent; when they run low or high, it falls in the other two classes.
For coherent systems, he shows that key traits stay fixed across the class. Those traits cover line length, wait time, busy spans, and a classic formula for average waits. One trait from a single setup thus extends to its whole class. The scheme also settles a dispute: a famed law linking line length and wait holds for all such queues.
Catalog record
| CREATOR | Muhammad El-Taha |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-01696
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Classification of Discrete-Time Queues Muhammad El-Taha Abstract Abstract. In this article we classify discrete-time queues based on scheduling rules and observation epochs combinations. This classification leads to coherent , sub-coherent , and super-coherent systems when observed waiting times are, respectively equal to, less than, or larger than actual waiting times. We then explore the consequences of this classification. Specifically, we discuss invariant properties of coherent systems including queue-lengths, waiting times, servers’ busy times, busy periods, Pollaczek-Khinchine formula, and other common characteristics. An important consequence is that a performance characteristic of a system with specific scheduling rule and observation epoch combination extends to the entire class. An unresolved issue in the literature is the assertion that Little’s law does not apply for discrete-time queues that incorporate certain scheduling rules. Using this classification, we reconcile the generality of Little’s law and its applicability to all discrete-time queues regardless of scheduling rules. Keywords: Classification of discrete-time queues, coherent queues, sample-path analysis, Little’s law, invariant characteristics 1 Introduction Consider a discrete-time queueing model where time \tau=0,1,2,\ldots is discrete, and where time slots are of equal unit length. Arrivals and departures can occur at the same discrete time instants. We refer to this as the actual system. To keep track of the system state and transitions between states one needs to order the arrivals and departures. This leads to several scheduling rules ( SR ) like the early arrival ( EAS ) and late arrival ( LAS ) systems. Moreover, to track the system state, (e.g., queue-length) one observes the system at slot edges or slot centers. Scheduling rules and observation epochs will be discussed in Section 2 . When considered together SR and observation epochs generate systems that are coherent and others that are incoherent in the sense that the customers’ observed waiting times in these incoherent systems are unequal to the actual system waiting times. It is well-known that Little’s law ( LL ) applies to discrete-time systems at great level generality. However, applying discrete-time LL to queues with scheduling rules ( SR ) has not been fully explored. There are assertions in the literature that there are instances when LL does not apply even when all assumptions are met. A primary motive in this article is to explore this issue and provide recommendations that remedy this situation. Hunter [ 18 ] discusses three SR , the early arrival, late arrival with immediate access, and late arrival with delayed access. He shows that for EAS and LAS models the waiting time distribution function is the same for all three SR for G/Geom/1 and B/Geom/1 FCFS models. But to derive his results, Hunter adopts the convention that (see page 228) for systems with LAS-IA he “counts the number of service time positions spent in the system”; for LAS-DA he “counts the completed number of time slots spent in the system”; and for the EAS system “both methods give the same waiting time”. It appears that Hunter assumes apriori that the waiting time distribution function should be the same and the choice of multiple ways to count service times is to achieve that outcome. Desert and Daduna [ 8 ] page 85 conclude that “ LL can be directly applied to a discrete-time queueing system in the late arrivals case only”. See also page 74 of their article. This is troubling as it is well known the LL applies universally to all discrete-time systems. Moreover, Desert and Daduna [ 8 ] study several SR ( EAS , LA-DF , LA-AF ) and conclude that waiting time distribution function is the same for these SR . They also discuss LL and conclude that (see pages 84-85) for certain observation epochs LL does not hold in the sense that the LL cannot be applied to the EAS case. Fiems and Bruneel [ 13 ] consider LL for discrete-time systems as a special case of the continuous time version. They consider a discrete time equivalent of the LL result in continuous time. They also study the effect of arrival/departure rescheduling on LL . The discretized version leads to instances (see equations (2) and (5) in their paper) where it appears L and \lambda W are unequal. Dattatreya and Singh [ 7 ] discuss relationships among different discrete-time models that arise in telecommunication networks. They study the EAS model and compare mean values (queue-lengths and response times) using slot edges and slot centers. They conclude (equation (17) in their paper) that LL applies when L is computed as slot centers, but not when L is computed at slot edges. These articles are examples of researchers’ discomfort with applying LL and illustrations of the need for more clarity as to when and how LL applies to discrete-time queues. Scheduling rules in discrete-time queues have been addressed by several authors. Gravey and Hebuterne [ 16 ] study the simultaneity of arrivals and departures in discrete-time queues, the need for SR , and the effect of these SR on systems performance. Chaudhry et al. [ 4 ] study discrete-time models using EAS and LAS-DA at the random observer (slot edges) and outside observer (slot centers) epochs. El-Taha et al. [ 12 ] introduce the LA-DF scheduling rule to study insensitivity of symmetric discrete-time queues. Chaudhry [ 3 ] gives a thorough discussion of the EAS , LAS-DA and LAS-IA scheduling rules. Daduna [ 6 ] discusses other issues that result from using scheduling rules. He mentions instances where BASTA does not hold even with Bernoulli arrivals in the sense that Bernoulli arrivals should see time averages at the random observer epochs. Articles that apply LL include Goswami [ 14 ] , Bruneel et al. [ 2 ] , Bruneel and Kim [ 1 ] and Chaudhry and Gupta [ 5 ] , among others. One can identify five popular scheduling rules and six observation epochs (Section 2 ). This creates a large number of potential instances that may require attention. This article creates a new framework that addresses these issues and provides a resolution. Specifically, the contributions of this article are: 1. Classify discrete-time queues based on actual and observed waiting times. This is a novel idea that has not been utilized before in the literature. We examine all SR and observation epochs arrangements and classify them into coherent , sub-coherent or super-coherent systems based on whether a SR /observation epoch combination leads to the observed waiting time being equal, less than or larger than the actual waiting. We shall carefully define what we mean by coherent , sub-coherent , super-coherent , actual , and observed in Sections 2 and 3 of this article. 2. Show that members of each class share invariant characteristics, thus can be studied together as one unit. In particular, we show that all coherent systems share the same stationary distribution, the same waiting time distribution function, the same servers’ utilization factors, the same busy periods, and many more. Thus, studying one coherent system will give results that are shared by the entire class. Contrast this with the literature, where each SR /observation epoch arrangement is studied independently. 3. We address an unresolved issue that LL does not appear to hold for some discrete systems. In particular, we