# Finite-Buffer M/G/1 Queues with Time and Space Priorities

Authors: Kilhwan Kim
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Many communication systems have finite buffers and service delay-sensitive and loss-sensitive types of traffic simultaneously. To meet the diverse QoS requirements of these heterogeneous types of traffic, it is desirable to offer delay-sensitive traffic time priority over loss-sensitive traffic, and loss-sensitive traffic space priority over delay-sensitive traffic. To analyze the performance of such systems, we study a finite-buffer M/G/1 priority queueing model where nonpreemptive time priority is given to delay-sensitive traffic and push-out space priority is given to loss-sensitive traffic. Compared to the previous study on finite-buffer M/M/1 priority queues with time and space priority, where service times are identical and exponentially distributed for both types of traffic, in our model we assume that service times are different and are generally distributed for different types of traffic. As a result, our model is more suitable for the performance analysis of communication systems accommodating multiple types of traffic with different service-time distributions. For the proposed queueing model, we derive the queue-length distributions, loss probabilities, and mean waiting times of both types of traffic, as well as the push-out probability of delay-sensitive traffic. With numerical examples, we also explore how the performance measures are affected by system parameters such as the buffer size, and the arrival rates and mean service times of both types of traffic for different service-time distributions.


---

## Body

## 1. Introduction

In this paper, we study a finite-buffer M/G/1 queueing model with two priority classes, where one class is given time priority and the other space priority, to meet the diverse QoS (Quality of Service) requirements of both classes.Priority queues have been extensively studied for the performance analysis of communication systems that serve heterogeneous types of traffic with different QoS requirements. Various studies have been conducted on priority queues. One line of these studies focuses on priority queues with an infinite buffer, where packet loss never occurs, so the delays of different classes of traffic are a main concern. In these priority queues, one class of traffic is given time priority over the other class so that high-priority packets can be served before low-priority packets, even though the low-priority packets arrive at the system earlier than the high-priority packets. A variety of priority disciplines, such as nonpreemptive, preemptive, and mixed types, and related queueing models have been proposed to meet the different delay requirements of high- and low-priority classes of traffic. An analysis of the classical time-priority queueing models can be found in [[1], Ch. 3] and [[2], Ch. 3], and the analysis of more sophisticated time-priority queueing models can be found in [3, 4] and the references therein. Another line of research is focused on priority queueing models with a finite buffer, where packet loss can occur, so the loss probabilities of different classes of traffic are more important than their delays. In these priority queues, one class of traffic is given space priority over the other class so that high-priority packets can access the buffer even when low-priority packets are not allowed to access the buffer and are lost. Several space-priority mechanisms for buffer management, such as partial buffer-sharing and push-out mechanisms, have been proposed to meet the diverse loss requirements of high- and low-priority classes of traffic [5–8].However, these two types of priority queues have their own limitations, because they only deal with the delay or loss requirements of traffic solely with priority disciplines. Communication systems generally have finite buffers and serve delay- and loss-sensitive types of traffic simultaneously. In this case, it can be more desirable to employ both time and space priorities and give time priority to delay-sensitive traffic and space priority to loss-sensitive traffic. For example, Internet traffic can be grouped into streaming and elastic types of traffic. While streaming traffic served on UDP, such as audio and video streaming packets, is delay sensitive, elastic traffic served on TCP, such as file transfer packets, is loss sensitive [9]. Streaming traffic requires real-time transmission, so packets that exceed a certain tight delay bound will simply be discarded at the destination end. Thus, packets that are too delayed to be discarded at the destination end do not have more value than packets lost during their transmission along communication links. Instead, they may be harmful, as valuable communication links are consumed in transmitting useless packets. Therefore, the user of streaming traffic may have an interest in reducing packet delay when competing for transmission links with other types of traffic at the cost of an increase in packet loss when traffic congestion occurs. On the other hand, elastic traffic on top of TCP generally tolerates variation of packet delay, but packet loss has a significant negative impact on the performance of elastic traffic because this causes the transmission rate to drop considerably due to the operation characteristic of TCP [10]. Therefore, the user of elastic traffic may also be interested in reducing packet loss during periods of traffic congestion at the cost of an increase in packet delay when competing for transmission links with other types of traffic. Offering time priority to streaming traffic and space priority to elastic traffic results in an exchange of packet delay and loss between the two types of traffic that may improve the aggregate utility of the communication system that the users of both types of traffic receive.Several studies have dealt with priority queues with both time and space priorities [6, 9, 11–17]. However, many of them [6, 11, 13, 14] consider priority queues where both time and space priorities are provided to the same class so that they are not appropriate to address the different diverse requirements of both delay- and loss-sensitive types of traffic. Lee and Choi [12] analyzed priority queues with a hierarchical priority structure where traffic was grouped into high- and low-time-priority classes, and then each time-priority class was divided into high- and low-space-priority subclasses. Although the priority queue in [12] was more sophisticated, it was also not appropriate to address the different diverse requirements of delay- and loss-sensitive types of traffic, because both time and space priorities were provided to the same subclass of traffic (high-time-priority and high-space-priority subclass). There is another approach for dealing with both time and space priorities, where the system provides delay-sensitive traffic time priority and a finite buffer, and loss-sensitive traffic space priority with a virtually infinite buffer [15–17]. However, assuming a virtually infinite buffer for one class is not realistic in communication systems. Thus, the applicability of this approach is also limited.Recently, [9] analyzed a finite-buffer M/M/1 priority queue where delay-sensitive traffic was given nonpreemptive time priority and loss-sensitive traffic was given push-out space priority. To the best of the author’s knowledge, this study is the only work dealing with priority queues with a finite buffer where time and space priorities are given to different classes. However, the queueing model in [9] also has a limitation. In [9], the service times of delay-sensitive and loss-sensitive packets are assumed to be exponentially distributed and have the same distribution for the tractability of the analysis. However, this is a substantial limitation because the maximum packet sizes of delay- and loss-sensitive types of traffic can be set to different values and the packet sizes of the traffic can have an arbitrary distribution.In this paper, we analyze a finite-buffer M/G/1 priority queue where time and space priorities are given to different classes of traffic. This work can be viewed as a generalization of the queueing model in [9] in the sense that the service times of different classes can be assumed to have different arbitrary distributions. As a result, using this queueing model, we can explore the impact of the service-time distributions on system performance. As will be seen in Section 6, the service-time distribution of loss-sensitive traffic has different effects on the performance measures, depending on whether the buffer is nearly monopolized by loss-sensitive traffic or not.As in [9], our model also employs a push-out space-priority mechanism. Here, we provide a rationale for employing push-out mechanism in the proposed space-time-priority queueing model. As mentioned earlier, there are several space-priority mechanisms to differentiate packet loss probabilities between classes of traffic. The simplest way to implement space priority is to provide each class of traffic with a separate region in the buffer, and the higher the space priority a class of traffic has, the more the portion of the buffer it is given to experience a lower packet loss probability [18]. However, compared to when the whole buffer is shared by all classes of traffic, this mechanism may bring about a significantly underutilized buffer because an arriving packet cannot enter the buffer even when the buffer has many vacancies if the buffer region for the class of the arrival is already full. One of the remedies for this underutilized buffer problem is the partial buffer-sharing (PBS) mechanism, where the buffer is divided into two regions. One region is shared by all packets, regardless of their classes, and the other region is used only for high-space-priority packets [11, 19]. Thus, while the shared region promotes buffer utilization, the dedicated region differentiates packet loss probabilities between classes. However, one difficulty with this mechanism is that it is difficult to determine an appropriate portion of the shared region, especially when the stochastic characteristics of the classes of traffic fluctuate. The push-out mechanism is different from the above two mechanisms in respect of the way of differentiating loss probabilities. While the above two mechanisms utilize buffer partitioning to differentiate loss probabilities between classes, the push-out mechanism uses selective loss of arriving packets when the buffer is full. If a low-space-priority packet arrives when the buffer is full, then the arriving packet is always lost. However, if a high-space-priority packet arrives when the buffer is full, then a packet of the lower class in the buffer (if any) is lost instead of the arriving packet [9, 13, 14, 20–23]. Compared to the PBS mechanism, the push-out mechanism has the following advantages: It is efficient in terms of buffer utilization, as any buffer vacancies are always available for arriving packets, regardless of their classes. It is also adaptive in terms of buffer sharing. The higher the traffic load of high-space-priority packets, the more the portion of the buffer they will use autonomously. Thus, we do not need to determine the dedicated portion for high-space-priority packets in advance or adjust it to protect the access of high-space-priority packets to the buffer. A drawback of the push-out mechanism is that it is more involved in implementing a push-out mechanism in communication systems than the PBS mechanism [24]. Another drawback is that high-space-priority packets may prevail in the buffer as their traffic load soars. However, this drawback can be alleviated if high-space-priority packets are such elastic as TCP packets that adaptively reduces its traffic load when congestion occurs [10] (even though this behavior of elastic traffic is not considered in the proposed queueing model in this study).This paper is organized as follows. In Section2, we define the priority queueing model that is analyzed in this paper. In Section 3, using an embedded Markov chain, we obtain the joint distribution of loss- and delay-sensitive queue lengths at departure epochs. In Section 5, we derive the joint distribution of queue lengths and remaining service time at an arbitrary time using the results of the embedded Markov chain. In Section 6, we derive the loss probabilities and mean waiting times of both classes. In Section 7, we present some numerical examples to investigate the impact of the system parameters, such as the buffer size and the arrival rates and the mean service times of both classes, on the system performance for different service-time distributions.


## 2. Model

We consider the following finite-buffer M/G/1 queue: There are two classes of packets that arrive at the system. One is loss sensitive, and the other is delay sensitive. The loss-sensitive and delay-sensitive classes of packets will be called classesL and D, respectively. Class-g packets, g=L,D, arrive at the system according to a Poisson process with rate λg, λg>0. Thus, the total arrival rate λ is given by λ=λL+λD. The service time Sh of a class-h, h=L,D, packet follows a nondegenerate general distribution Sht, t≥0, of finite mean; i.e., 0<ESh<∞.Since class-D packets are delay sensitive, we give class-D packets nonpreemptive time priority over class-L packets. That is, when the server is available for the next service, we choose one of class-D packets (if any) in the buffer, even though there are class-L packets which arrive earlier than the class-D packets. The FCFS service order is assumed between packets of the same class.On the other hand, we give class-L packets push-out space priority over class-D packets because class-L packets are loss-sensitive. We assume that the size of the buffer is K, and a packet of either class in the buffer occupies one buffer slot in the buffer. Thus, there are at most K+1 packets in the system (one is in service and at most K packets in the buffer). If the buffer is not full on arrival of a packet, then the packet joins the buffer, regardless of its class. However, if the buffer is full, whether to join the buffer depends on the class of the packet: A class-D packet is always lost if the buffer is full on its arrival, while a class-L packet can push out a class-D packet in the buffer if the buffer is full but there is a class-D packet in the buffer on its arrival. If the buffer is full and there is more than one class-D packet in the buffer on arrival of a class-L packet, then the last class-D packet in order of arrival is pushed out. Neither class-L nor -D packet is allowed to push out packets of the same class in the buffer or a packet in service.


## 3. The Embedded Markov Chain at Departure Epochs

We now consider an embedded Markov chain (EMC) at packet departure epochs. LetNgdn, g=L,D, n=1,2,…, denote the number of class-g packets in the system just after the n-th service completion. Then, NLdn,NDdn|n=1,2,… constitutes an EMC. Observe that NLdn,NDdn≥0 and NLdn+NDdn≤K due to the finite-buffer size K. Define the limiting probabilities as(1)πi,j=limn⟶∞PrNLdn=i,NDdn=j,i,j≥0,i+j≤K.We will call all the states that satisfyNLdn=i, i,0,i,1,…,i,K−i, level i, 0≤i≤K. We also define the corresponding partial limiting probability vectors of level i and the whole limiting probability vector as(2)πi=πi,0πi,1…πi,K−i1×K−i+1,0≤i≤K,π=π0π1…πK1×K+1K+2/2.Letpi,j,l,m denote the transition probability of the EMC from state i,j to state l,m, i,j,l,m≥0, i+j,l+m≤K. We define the partial transition matrix Pi,l from level i to level l as follows:(3)Pi,l=pi,0,l,0pi,0,l,1…pi,0,l,K−lpi,1,l,0pi,1,l,1…pi,1,l,K−l⋮⋮⋱⋮pi,K−i,l,0pi,K−i,l,1…pi,K−i,l,K−lK−i+1×K−l+1.Notice that, since class-L packets in the buffer are not pushed out, at most one class-L packet can depart from the system between two consecutive embedded points. Thus, Pi,l=0 for 0≤i≤K, 0≤l<i−1. Therefore, the whole transition matrix P has the left-skip-free structure for levels:(4)P=P0,0P0,1…P0,K−2P0,K−1P0,KP1,0P1,1…P1,K−2P1,K−1P1,K0P2,1…P2,K−2P2,K−1P2,K⋮⋮⋱⋮⋮⋮00…PK−1,K−2PK−1,K−1PK−1,K00…0PK,K−1PK,KK+1K+2/2×K+1K+2/2.We will exploit this M/G/1-type structure when deriving the limiting probability vectorπ. If the EMC is irreducible and ergodic, then the limiting probability vector π satisfies the following relationship (see [[25], Sec. 7.6]):(5)π=πP,πe=1,where e is a K+1K+2/2×1 column vector whose elements are all 1.We now derive the transition probabilitiespi,j,l,m. To do this, let AgSh, g,h=L,D, denote the number of class-g arrivals during the service time of a class-h packet. We further define the following probabilities associated with AgSh:(6)al,mh=PrALSh=l,ADSh=m=∫t=0∞λLtll!λDtmm!e−λL+λDtdSht>0,al,⋅h=PrALSh=l=∫t=0∞λLtll!e−λLtdSht>0.forl,m≥0 and h=L,D. The inequalities above hold because λg>0 and Sh is a nondegenerate nonnegative random variable with finite mean.Since we assume that class-D packets have time priority over class-L packets, if NDdn≥1, then a class-D packet gets serviced during the transition from the n-th to the n+1-th embedded points. Furthermore, if NDdn=0 and NLdn≥1, then a class-L packet gets serviced during the transition. Finally, if NDdn=NLdn=0, then an idle period begins and a packet which arrives during the idle period gets serviced during the transition. Hence, we can divide the state space i,j:i,j≥0,i+j≤K of the EMC into the following disjoint subsets, each of which corresponds to the type of the transition time between the n-th and n+1-th embedded points:(1)
i≥0, j≥1, and i+j≤K, where the transition time is SD.(2)
1≤i≤K and j=0, where the transition time is SL.(3)
i=j=0, where the transition time is the idle period plus either SL with probability λL/λ or SD with probability λD/λ.We now considerpi,j,l,m for each of the above disjoint subsets.


### 3.1.pi,j,l,m When i≥0, j≥1, and i+j≤K

IfNLdn≥0, NDdn≥1, and NLdn+NDdn≤K, then the transition time is SD due to the time priority. Hence, one class-D packet gets serviced and departs from the system, and ALSD class-L packets and ADSD class-D packets arrive at the system during this transition. Notice also that there are NLdd class-L packets and NDdn−1 class-D packets in the buffer at the beginning of this transition because one class-D packet is in the service area then.We first considerNLdn+1. Since, due to space priority, class-L arrivals can push out class-D packets in the buffer, the effective buffer size for class-L packets is K. Thus, we have(7)NLdn+1=minNLdn+ALSD,K.We now considerNDdn+1. Since, due to space priority, all class-D packets in the buffer can be pushed out during the transition, the effective buffer size for class-D packets becomes K−NLdn+1 by the end of this transition. Thus, we have(8)NDdn+1=minNDdn−1+ADSD,K−NLdn+1.Hence, forNLdn≥0, NDdn≥1, and NLdn+NDdn≤K, we have the following relationship:(9)NLdn+1,NDdn+1=minNLdn+ALSD,K,minNDdn−1+ADSD,K−NLdn+1=K,0,ALSD≥K−NLdn,NLdn+ALSD,K−NLdn−ALSD,K−NLdn−NDdn+1≤ALSD,ALSD≤K−NLdn−1,NLdn+ALSD,K−NLdn−ALSD,0≤ALSD≤K−NLdn−NDdn,ADSD≥K−NLdn−ALSD−NDdn+1,NLdn+ALSD,NDdn−1+ADSD,0≤ALSD≤K−NLdn−NDdn,0≤ADSD≤K−NLdn−ALSD−NDdn,where each case corresponds to the following events: The first case occurs when the buffer is full and is monopolized by class-L packets at the end of the transition. The second and third cases occur when the buffer is full but is not monopolized by class-L packets at the end of the transition, and all the ALSD class-L arrivals during the transition join the buffer. The main difference between the second and third cases is whether NLdn+NDdn−1+ALSD≥K or not. If NLdn+NDdn−1+ALSD≥K, then none of the class-D arrivals can remain in the buffer by the end of the transition. Hence, we can only consider the marginal probabilities of ALSD to derive the transition probability. However, if NLdn+NDdn−1+ALSD<K, some of the ADSD class-D arrivals can remain in the buffer at the end of the transition. Hence, we need to consider the joint probabilities of ALSD and ADSD to derive the transition probability. The last case occurs when the buffer is not full at the end of this transition, and all arrivals of both classes during the transition successfully join the buffer. Therefore, from the above relationship of NLdn,NDdn and NLdn+1,NDdn+1, the transition probabilities pi,j,l,m, i≥0, j≥1, i+j≤K, are given by(10)pi,j,l,m=∑n=K−i∞an,⋅D>0,l=K,m=0,al−i,⋅D>0,i+1≤K−j+1≤l≤K−1,l+m=K,∑n=K−l−j+1∞al−i,nD>0,i≤l≤K−j,l+m=K,al−i,m−j+1D>0,l≥i,m≥j−1,l+m≤K−1,0,otherwise.


### 3.2.pi,j,l,m When 1≤i≤K and j=0

IfNLdn≥1 and NDdn=0, then the transition time between the n-th and n+1-th embedded points is SL. Hence, one class-L packet gets serviced and departs from the system, and ALSL class-L packets and ADSL class-D packets arrive at the system during this transition. Notice that there are no class-D packets and NLdn−1 class-L packets in the buffer at the beginning of the transition because one class-L packet enters its service then. Since class-L packets can push out class-D packets in the buffer, the effective buffer size for class L is K and that for class D becomes K−NLdn+1 by the end of this transition. Hence, the state NLdn+1,NDdn+1 at the end of this transition is determined as(11)NLdn+1,NDdn+1=minNLdn−1+ALSL,K,minADSL,K−NLdn+1=K,0,ALSL≥K−NLdn+1,NLdn−1+ALSL,K−NLdn+1−ALSL,0≤ALSL≤K−NLdn,ADSL≥K−NLdn+1−ALSLNLdn−1+ALSL,ADSL,0≤ALSL≤K−NLdn,0≤ALSL≤K−NLdn−ALSL,Therefore, for1≤i≤K, we have(12)pi,0,l,m=∑n=K−i+1∞an,⋅L>0,l=K,m=0,∑n=K−l∞al−i+1,nLi−1≤l≤K−1,l+m=K,al−i+1,mL>0,l≥i−1,m≥0,l+m≤K−1,0otherwise.


### 3.3.pi,j,l,m When i=j=0

In this case, the transition time consists of the idle period plus eitherSL with probability λL/λ or SD with probability λD/λ, and the one packet which arrives during the idle period is serviced and departs from the system on this transition. Since there are neither class-L packets nor class-D packets in the buffer at the beginning of the service of the packet which arrives during the idle period, if the class of packet which arrives in the idle period is h, then the following relationship holds for h=L,D:(13)NLdn+1,NDdn+1=minALSh,K,minADSh,K−NLdn+1=K,0,ALSh≥K,ALSh,K−ALSh,0≤ALSh≤K−1,ADSh≥K−ALSh,ALSh,ADSh,0≤ALSh≤K−1,0≤ADSh≤K−ALSh−1.Therefore, we have(14)p0,0,l,m=∑h∈L,Dλhλ∑n=K∞an,⋅h>0,l=K,m=0,∑h∈L,Dλhλ∑n=K−l∞al,nh>0,0≤l≤K−1,l+m=K,∑h∈L,Dλhλal,mh>0,l≥0,m≥0,l+m≤K−1,0otherwise.Finally, from (10), (12), and (14), we can construct all the partial transition matrices Pi,l, 0≤i≤K, max0,i−1≤l≤K, in the whole transition probability matrix P, and their special structures are presented in Section A in the appendix. From the special structures of the partial transition matrices and the whole transition matrix, we have the following lemma.Lemma 1.
The EMC with transition probabilityP is an irreducible ergodic Markov chain.The rigorous proof of Lemma1 is given in Section A in the appendix. Here, a brief explanation of the irreducibility and ergodicity of the EMC is given. In order for the EMC to be irreducible, all the states can reach each other. From the M/G/1-type structure of P in (4) and Pii in (A.3), it is easy to see that all the levels can reach each other and that all the states within the same level can also reach each other. Therefore, the EMC is irreducible. Notice that if an irreducible finite-state Markov chain is aperiodic, then it is an ergodic Markov chain, whose limiting probabilities converge to a positive value (see [[25], Sec. 7.5]). Notice also that if, starting from a state, the Markov chain can return back to that state in one-step transition, then it is aperiodic at the state (see [[26], Sec. 4.2]). From the structure of Pii in (A.3), for each state, the one-step transition probability to itself is pi,j,i,j>0. Thus, the EMC is aperiodic and, therefore, ergodic.Since, from Lemma1, the EMC is an irreducible ergodic Markov chain, there exists a positive limiting probability vector π, which is also a unique stationary probability vector that satisfies (5) (see [[25], Secs. 7.5-7.6]). Therefore, if we compute the stationary probability vector that satisfies (5), then the limiting probability vector π of the EMC is obtained.


## 3.1.pi,j,l,m When i≥0, j≥1, and i+j≤K

IfNLdn≥0, NDdn≥1, and NLdn+NDdn≤K, then the transition time is SD due to the time priority. Hence, one class-D packet gets serviced and departs from the system, and ALSD class-L packets and ADSD class-D packets arrive at the system during this transition. Notice also that there are NLdd class-L packets and NDdn−1 class-D packets in the buffer at the beginning of this transition because one class-D packet is in the service area then.We first considerNLdn+1. Since, due to space priority, class-L arrivals can push out class-D packets in the buffer, the effective buffer size for class-L packets is K. Thus, we have(7)NLdn+1=minNLdn+ALSD,K.We now considerNDdn+1. Since, due to space priority, all class-D packets in the buffer can be pushed out during the transition, the effective buffer size for class-D packets becomes K−NLdn+1 by the end of this transition. Thus, we have(8)NDdn+1=minNDdn−1+ADSD,K−NLdn+1.Hence, forNLdn≥0, NDdn≥1, and NLdn+NDdn≤K, we have the following relationship:(9)NLdn+1,NDdn+1=minNLdn+ALSD,K,minNDdn−1+ADSD,K−NLdn+1=K,0,ALSD≥K−NLdn,NLdn+ALSD,K−NLdn−ALSD,K−NLdn−NDdn+1≤ALSD,ALSD≤K−NLdn−1,NLdn+ALSD,K−NLdn−ALSD,0≤ALSD≤K−NLdn−NDdn,ADSD≥K−NLdn−ALSD−NDdn+1,NLdn+ALSD,NDdn−1+ADSD,0≤ALSD≤K−NLdn−NDdn,0≤ADSD≤K−NLdn−ALSD−NDdn,where each case corresponds to the following events: The first case occurs when the buffer is full and is monopolized by class-L packets at the end of the transition. The second and third cases occur when the buffer is full but is not monopolized by class-L packets at the end of the transition, and all the ALSD class-L arrivals during the transition join the buffer. The main difference between the second and third cases is whether NLdn+NDdn−1+ALSD≥K or not. If NLdn+NDdn−1+ALSD≥K, then none of the class-D arrivals can remain in the buffer by the end of the transition. Hence, we can only consider the marginal probabilities of ALSD to derive the transition probability. However, if NLdn+NDdn−1+ALSD<K, some of the ADSD class-D arrivals can remain in the buffer at the end of the transition. Hence, we need to consider the joint probabilities of ALSD and ADSD to derive the transition probability. The last case occurs when the buffer is not full at the end of this transition, and all arrivals of both classes during the transition successfully join the buffer. Therefore, from the above relationship of NLdn,NDdn and NLdn+1,NDdn+1, the transition probabilities pi,j,l,m, i≥0, j≥1, i+j≤K, are given by(10)pi,j,l,m=∑n=K−i∞an,⋅D>0,l=K,m=0,al−i,⋅D>0,i+1≤K−j+1≤l≤K−1,l+m=K,∑n=K−l−j+1∞al−i,nD>0,i≤l≤K−j,l+m=K,al−i,m−j+1D>0,l≥i,m≥j−1,l+m≤K−1,0,otherwise.


## 3.2.pi,j,l,m When 1≤i≤K and j=0

IfNLdn≥1 and NDdn=0, then the transition time between the n-th and n+1-th embedded points is SL. Hence, one class-L packet gets serviced and departs from the system, and ALSL class-L packets and ADSL class-D packets arrive at the system during this transition. Notice that there are no class-D packets and NLdn−1 class-L packets in the buffer at the beginning of the transition because one class-L packet enters its service then. Since class-L packets can push out class-D packets in the buffer, the effective buffer size for class L is K and that for class D becomes K−NLdn+1 by the end of this transition. Hence, the state NLdn+1,NDdn+1 at the end of this transition is determined as(11)NLdn+1,NDdn+1=minNLdn−1+ALSL,K,minADSL,K−NLdn+1=K,0,ALSL≥K−NLdn+1,NLdn−1+ALSL,K−NLdn+1−ALSL,0≤ALSL≤K−NLdn,ADSL≥K−NLdn+1−ALSLNLdn−1+ALSL,ADSL,0≤ALSL≤K−NLdn,0≤ALSL≤K−NLdn−ALSL,Therefore, for1≤i≤K, we have(12)pi,0,l,m=∑n=K−i+1∞an,⋅L>0,l=K,m=0,∑n=K−l∞al−i+1,nLi−1≤l≤K−1,l+m=K,al−i+1,mL>0,l≥i−1,m≥0,l+m≤K−1,0otherwise.


## 3.3.pi,j,l,m When i=j=0

In this case, the transition time consists of the idle period plus eitherSL with probability λL/λ or SD with probability λD/λ, and the one packet which arrives during the idle period is serviced and departs from the system on this transition. Since there are neither class-L packets nor class-D packets in the buffer at the beginning of the service of the packet which arrives during the idle period, if the class of packet which arrives in the idle period is h, then the following relationship holds for h=L,D:(13)NLdn+1,NDdn+1=minALSh,K,minADSh,K−NLdn+1=K,0,ALSh≥K,ALSh,K−ALSh,0≤ALSh≤K−1,ADSh≥K−ALSh,ALSh,ADSh,0≤ALSh≤K−1,0≤ADSh≤K−ALSh−1.Therefore, we have(14)p0,0,l,m=∑h∈L,Dλhλ∑n=K∞an,⋅h>0,l=K,m=0,∑h∈L,Dλhλ∑n=K−l∞al,nh>0,0≤l≤K−1,l+m=K,∑h∈L,Dλhλal,mh>0,l≥0,m≥0,l+m≤K−1,0otherwise.Finally, from (10), (12), and (14), we can construct all the partial transition matrices Pi,l, 0≤i≤K, max0,i−1≤l≤K, in the whole transition probability matrix P, and their special structures are presented in Section A in the appendix. From the special structures of the partial transition matrices and the whole transition matrix, we have the following lemma.Lemma 1.
The EMC with transition probabilityP is an irreducible ergodic Markov chain.The rigorous proof of Lemma1 is given in Section A in the appendix. Here, a brief explanation of the irreducibility and ergodicity of the EMC is given. In order for the EMC to be irreducible, all the states can reach each other. From the M/G/1-type structure of P in (4) and Pii in (A.3), it is easy to see that all the levels can reach each other and that all the states within the same level can also reach each other. Therefore, the EMC is irreducible. Notice that if an irreducible finite-state Markov chain is aperiodic, then it is an ergodic Markov chain, whose limiting probabilities converge to a positive value (see [[25], Sec. 7.5]). Notice also that if, starting from a state, the Markov chain can return back to that state in one-step transition, then it is aperiodic at the state (see [[26], Sec. 4.2]). From the structure of Pii in (A.3), for each state, the one-step transition probability to itself is pi,j,i,j>0. Thus, the EMC is aperiodic and, therefore, ergodic.Since, from Lemma1, the EMC is an irreducible ergodic Markov chain, there exists a positive limiting probability vector π, which is also a unique stationary probability vector that satisfies (5) (see [[25], Secs. 7.5-7.6]). Therefore, if we compute the stationary probability vector that satisfies (5), then the limiting probability vector π of the EMC is obtained.


## 4. An Algorithm to Compute the Stationary Probability Vector of the EMC

In general,π that satisfies (5) can be obtained by one of numerical methods for computing stationary probability vectors such as those described in [27]. However, if the buffer size K is large, then the dimension of the matrix P becomes also large, K+1K+2/2×K+1K+2/2, so the computation of π can be computationally expensive. For instance, if we use the LU decomposition method, one of the standard numerical methods for stationary probability vectors, to compute π, then the numerical method requires OK6 floating-point operations because, for the LU decomposition of an n×n matrix n3/3, floating-point additions and multiplications are needed. In addition, as seen in (4), the transition probability matrix P has a special structure. Hence, if we exploit this probability structure, then we can not only develop a more efficient algorithm to obtain the stationary probability vector π, but also gain insight into the behavior of the proposed queueing model.Observe first that, from the M/G/1-type structure of P in (4), the EMC is left-skip-free for levels. That is, any path from level i to level l, 0≤l≤i−1, must go through every intermediate level l′, l<l′<j, at least once on this path. We now consider the hitting probability from level i to level l, 0≤l<i≤K. The hitting probability gi,j,l,m is defined to be the probability that, starting from state i,j, the first state visited at level l is the state l,m for 0≤l<i≤K, 0≤j≤K−i, 0≤m≤K−l. We define also the hitting probability matrix Gi,l from level i to level l to be(15)Gi,l=gi,0,l,0gi,0,l,1⋯gi,0,l,K−lgi,1,l,0gi,1,l,1⋯gi,1,l,K−l⋮⋮⋱⋮gi,K−i,l,0gi,K−i,l,1⋯gi,K−i,l,K−lK−i+1×K−l+1,0≤l<i≤K.For brevity, letGi denote the hitting probability matrix Gi,i−1 from level i to the next lower level i−1.Lemma 2.
The hitting probability matricesGi, 1≤i≤K, are given by the recursive formula(16)Gi=IK−i+1×K−i+1−∑l=i+1KPi,lGl,i−Pi,i−1Pi,i−1,1≤i≤K,where Ii×i is the i×i identity matrix and(17)Gl,i−1=GlGl−1…Gi,1≤i≤l≤K.In addition, all the elements ofGi are positive, and Gi is a stochastic matrix; i.e.,(18)Gi>0,GieK−i+2×1=eK−i+1×1,1≤i≤K,where ei×1 is an i -dimensional column vector whose elements are all one.The proof of Lemma2 is given in Section B in the appendix.We now derive the partial probability vectorsπi, 0≤i≤K. To this end, we consider the following censored Markov chain Hk, 0≤k≤K, from the original EMC, where we only observe the original EMC when the state is within levels 0,1,…,k. (Censored Markov chains are also known as restricted or watched Markov chains and have been used for the analysis of Markov chains which have partitioned structure. See [28, 29] and the references therein.) We first define hi,j,l,mk to be the transition probability of the censored Markov chain Hk from state i,j to state l,j, 0≤i,l≤k, 0≤j≤K−i, 0≤m≤K−l. We also define the partial transition probability matrix Hi,lk from level i to level l to be(19)Hi,lk=hi,0,l,0khi,0,l,1k⋯hi,0,l,K−lkhi,1,l,0khi,1,l,1k⋯hi,1,l,K−lk⋮⋮⋱⋮hi,K−i,l,0khi,K−i,l,1k⋯hi,K−i,l,K−lkK−i+1×K−l+1,0≤i,l≤k,and the whole transition probability matrixHk to be(20)Hk=H0,0kH0,1k…H0,kkH1,0kH1,1k…H1,kk⋮⋮⋱⋮Hk,0kHk,1k…Hk,kkk+12K+1−k/2×k+12K+1−k/2.Lemma 3.
The censored Markov chainHk, 0≤k≤K, is an irreducible ergodic Markov chain, and the transition probability matrix is given by(21)Hk=P0,0P0,1P0,2…P0,k−2P0,k−1H0,kkP1,0P1,1P1,2…P1,k−2P1,k−1H1,kk0P2,1P2,1…P2,k−2P2,k−1H2,kk⋮⋮⋮⋱⋮⋮⋮000…Pk−1,k−2Pk−1,k−1Hk−1,kk000…0Pk,k−1Hk,kk,where(22)Hi,kk=Pi,k+∑l=k+1KPi,lGl,k,0≤i≤k.The proof of Lemma3 is given in Section C in the appendix.From the structure of the censored Markov chainHk in (21), if we obtain Hi,kk, 0≤i≤k, then we can construct the whole transition matrix Hk. Thus, the transition probability matrices HK,HK−1,…,H0 can be constructed from the following recursive formula in Lemma 4.Lemma 4.
The partial transition matrixHi,kk, 0≤i≤k≤K, can be calculated from the following recursive equations(23)Hi,KK=Pi,K,0≤i≤K,Hi,kk=Pi,k+Hi,k+1k+1Gk+1,0≤i≤k≤K−1.Furthermore,Gk can be calculated from Hk,kk as(24)Gk=I−Hk,kk−1Pk,k−1,1≤k≤K.The proof of Lemma4 is given in Section D in the appendix.Since the censored Markov chainHk is an irreducible ergodic Markov chain from Lemma 3, there exists the unique stationary probability vector hk that satisfies the following equations:(25)hk=hkHk,hke=1.The stationary probability vectorhk for the censored Markov chain Hk and a portion of the stationary probability vector π of the original EMC P have a proportional relationship, described in Lemma 5.Lemma 5.
If we define the partial stationary probability vectorπk associated with the states from level 0 to level k in the original EMC to be(26)πk=π0π1…πk1×k+12K+1−k/2,0≤k≤K,
then the vectorπk satisfies the following equation:(27)πk=πkHk,0≤k≤K,
which implies the following proportional relationship:(28)hk=πkπkek+12K+1−k/2×1,0≤k≤K.The proof of Lemma5 is given in Section E in the appendix.Finally, if we use the proportional relationship of the stationary probability vectors in Lemma5, then we can recursively compute the vectors hk, 0≤k≤K, which differ from the partial probability vectors πk by a constant multiplier, as described in Theorem 1.Theorem 1.
The partial probability vectorπk is given by(29)πk=βhk,0≤k≤K,where h0 is the 1×K+1 unique stationary probability vector that satisfies(30)h0=h0H0,00,h0eK+1×1=1.hk are 1×K−k+1 vectors that are given by the recursion formula:(31)hk=∑i=0k−1hiHi,kkI−Hk,kk−1,1≤k≤K,andβ is the following positive constant:(32)β=1∑k=0KhkeK−k+1×1.Proof.
From (21), for k=0, we have H0=H0,00. Thus, from Lemma 3, H0,00 is the transition probability matrix of the irreducible ergodic Markov chain H0. Therefore, there exists a unique vector h0 that satisfies (30), which is also identical to h0. From (28), we also have(33)π0=π0=βh0=βh0,where β=π0eK+1×1, which is an unknown multiplier so far. Moreover, from (21) and (27), we have πl=∑i=0lπiHi,ll, 1≤l≤K, which leads to(34)πl=∑i=0l−1πiHi,llI−Hl,ll−1,1≤l≤K.
Suppose now that (29) and (31) hold for all k less than a certain level l, 1≤l≤K. In addition, define hl as (31) for k=l. Then, since we assume that (29) holds for k=0,1,…,l−1, from the above equation, we have(35)πl=β∑i=0l−1hiHi,llI−Hl,ll−1=βhl.
Therefore, by induction, (29) and (31) hold for 1≤k≤K. In addition, from the normalization condition of π, we have(36)∑k=0KπkeK−k+1×1=β∑k=0KhkeK−k+1×1=1,
which leads to (32).
WhenK≥1, from Lemmas 2–5 and Theorem 1, we can compute π from the following algorithm.
Compared to the methods of directly computingπ from (5), which has a computational complexity of OK6, the proposed algorithm has a computational complexity of OK5 (see Section F in the appendix). Hence, the proposed algorithm is about K times more computationally efficient, and this can be significant for performance analysis, especially when K is large and we need to obtain performance measures for multiple combinations of system parameters. Additionally, in the course of developing the algorithm, we can gain insight into the behavior of the proposed queueing model. For example, (16) and (17) for the hitting probabilities can be readily extended to the analysis of the hitting time from level i to level l, 0≤l<i≤K, which, in turn, can be utilized for the analysis of busy period analysis, even though this is not done in this study.Algorithm 1: An algorithm to compute the stationary probability vector of the EMC.
(1)
ComputeGi, 1≤i≤K.1-1. Seti=K.1-2. From (16), compute Gi.1-3. For alll, i+1≤l≤K, compute Gl,i−1=Gl,i×Gi. Moreover, set Gi,i−1=Gi.1-4. Seti=i−1.1-5. Ifi≥1, then go to step 1-2. Otherwise, go to step 2.(2)
ComputeHj,k, 0≤j≤k≤K.2-1. For0≤j≤K, set Hj,KK=Pj,K.2-2. Setk=K.2-3. For0≤j≤k−1, compute Hj,k−1k−1 from (23).2-4. Setk=k−1.2-5. Ifk≥1, then go to step 2-3. Otherwise, go to step 3.(3)
Computehk, 0≤k≤K.3-1. Obtain a vectorh0 that satisfies (30).3-2. Setk=1.3-3. Computehk from (31).3-4.k=k+1.3-5. Ifk≤K, then go to step 3-3. Otherwise, go to step 4.(4)
Normalizeπ.4-1. Computeβ=1/∑k=0Khk⋅eK−k+1×1.4-2. For0≤k≤K, set πk=βhk.


## 5. Joint Distribution of Queue Lengths and Remaining Service Time at an Arbitrary Time

LetNg, g∈L,D, denote the number of class-g packets in the system in a steady state. Let also ξ denote the class of a packet in service when the server is busy. Given ξ=h, h∈L,D, let She and Shr denote the elapsed and remaining service times in a steady state, respectively. Since there can be at most K packets in the buffer and at most one packet in the server, NL+ND≤K+1. Define the joint distributions of NL, ND, ξ, and Sξr as(37)Qi,j=PrNL=i,ND=ji,j≥0,i+j≤K+1,Qi,j,ht=PrNL=i,ND=j,ξ=h,Shr≤t,i,j≥0,1≤i+j≤K+1.h∈L,D,t≥0.Define also the corresponding joint probabilities as(38)qi,j,htdt=dQi,j,ht=PrNL=i,ND=j,ξ=h,t≤Shr<t+dt.Note that ifNL≥1 and ND=0, then ξ=L, and that if NL=0 and ND≥1, then ξ=D. Thus, we have(39)Qi,0=Qi,0,L∞=∫t=0∞qi,0,Ltdt,1≤i≤K+1,Q0,j=Q0,j,D∞=∫t=0∞q0,j,Dtdt,1≤j≤K+1,Qi,j=Qi,j,L∞+Qi,j,D∞=∫t=0∞qi,j,Ltdt+∫t=0∞qi,j,Dtdt,i,j≥1,i+j≤K+1.Therefore, if we haveQ0,0 and qi,j,ht, i,j≥0, 1≤i+j≤K+1, h∈L,D, then all Qi,j, i,j≥0, i+j≤K+1, can be obtained.To deriveQ0,0 and qi,j,ht, we consider the semi-Markov process (NLdn,NDdn,Tn) associated with the EMC NLdn,NDdn, where Tn is the transition time from the n-th embedded point until the n+1-th embedded point. Due to the time priority of class-D packets over class-L packets, we have(40)Tn=SD,ifNDdn≥1,SL,ifNLdn≥1,NDdn=0,I+SD,ifNLdn=NDdn=0,ALI,ADI=0,1,I+SL,ifNLdn=NDdn=0,ALI,ADI=1,0,where I is the length of the idle period which follows an exponential distribution with rate λ, and AgI, g∈L,D, is the number of class-g packets which arrive during the idle period. Thus, if we let T=limn⟶∞Tn, then from the semi-Markov process theory we have (see [[25], Sec. 9.1])(41)ET=ESD∑i=0K∑j=1K−iπi,j+λDλ⋅π0,0+ESL∑i=1Kπi,0+λLλ⋅π0,0+1λ⋅π0,0.Furthermore, since the system is empty only during the idle period, we have(42)Q0,0=1/λπ0,0ET.To deriveqi,j,ht, we now consider the relationship between the state NL,ND,ξ,Sξr at an arbitrary time when the system is busy and the state NLd,NDd at the last embedded point before the arbitrary time. Notice that if NLd+NDd≥1 at the last embedded point, then the time between the last embedded point and the arbitrary time is the elapsed service time Sξe. If NLd=NDd=0, then an idle period starts at the last embedded point, a packet which arrives in the idle period starts a busy period following the idle period, and the time between the beginning of the service of the packet and the arbitrary time is Sξe. Hence, if we let AgSξe, g∈L,D, denote the number of class-g packets which arrive during the elapsed service time Sξe, then from arguments analogous to those used to derive (10), (12), and (14) in Section 3, we can derive the relationship between the state NL,ND,ξ,Sξr at the arbitrary time and the state NLd,NDd at the last embedded point as follows.SupposeNLd≥0, NDd≥1, and NLd+NDd≤K. Then, a class-D packet enters its service at the last embedded point. Additionally, the effective buffer size for class-L packets is K, and that for class-D packets becomes K−NL at the arbitrary time because NL class-L packets are in the buffer at that time. Considering one class-D packet in service and the effective buffer size of each class, we deduce that the maximum numbers of class-L and -D packets in the system at the arbitrary time are K and K−NL+1, respectively. Thus, we have(43)NL=minNLd+ALSDe,K,ND=minNDd+ADSDe,K−NL+1,ξ=D.Suppose next1≤NLd≤K and NDd=0. Then, a class-L packet enters its service at the last embedded point. Furthermore, the effective buffer size for class-L packets is K, and that for class-D packets becomes K−NL+1 at the arbitrary time because NL−1 class-L packets are in the buffer at that time. Considering one class-L packet in service and the effective buffer size of each class, we have(44)NL=minNLd+ALSDe,K+1,ND=minADSDe,K−NL+1,ξ=L.SupposeNLd=NDd=0. If ALI,ADI=0,1, then a class-D packet enters its service at the end of the idle period. Since there are one class-D packet in service and no packets in the buffer at that point, we have(45)NL=minALSDe,K,ND=min1+ADSDe,K−ALSDe+1,ξ=D.Similarly, ifALI,ADI=1,0, then a class-L packet enters its service at the end of the idle period, and we have(46)NL=min1+ALSLe,K+1,ND=minADSLe,K−ALSLe,ξ=L.Therefore, the relationship between the stateNL,ND,ξ,Sξr at the arbitrary time during the busy period and the state NLd,NDd at the last embedded point can be summarized by Table 1.Table 1
The relationship between the last embedded point and the arbitrary time during the busy period.
Possible states at the embedded pointArrivals between the embedded point and the arbitrary timeNL,ND,ξ,SξrPossible states at the arbitrary timeNLd≥0, NDd≥1, NLd+NDd≤K0≤ALSDe+ADSDe≤K−NLd−NDdNLd+ALSDe,NDd+ADSDe,D,SDrNL≥NLd≥0, ND≥NDd≥1, NL+ND≤K, ξ=DALSDe+ADSDe≥K+1−NLd−NDd, 0≤ALSDe≤K−NLd−NDdNLd+ALSDe,K+1−NLd−ALSDe,D,SDr0≤NLd≤NL≤K−NDd, NL+ND=K+1, ξ=DK+1−NLd−NDd≤ALSDe≤K−1−NLdNLd+ALSDe,K+1−NLd−ALSDe,D,SDrK+1−NDd≤NL≤K−1, NL+ND=K+1, ξ=DALSDe≥K−NLdK,1,D,SDrNL=K, ND=1, ξ=D1≤NLd≤K, NDd=00≤ALSLe+ADSLe≤K−NLdNLd+ALSLe,ADSLe,L,SLrNL≥NLd≥1, ND≥NDd=0, NL+ND≤K, ξ=LALSLe+ADSLe≥K+1−NLd, 0≤ALSLe≤K−NLdNLd+ALSLe,K+1−NLd−ALSLe,L,SLr1≤NLd≤NL≤K, NL+ND=K+1, ξ=LALSLe≥K+1−NLdK+1,0,L,SLrNL=K+1, ND=0, ξ=LNLd=NDd=0ALI,ADI=0,1, 0≤ALSDe+ADSDe≤K−1ALSDe,1+ADSDe,D,SDrNL≥0, ND≥1, NL+ND≤K, ξ=DALI,ADI=0,1, ALSDe+ADSDe≥K, 0≤ALSDe≤K−1ALSDe,K+1−ALSDe,D,SDr0≤NL≤K−1, NL+ND=K+1, ξ=DALI,ADI=0,1, ALSDe≥KK,1,D,SDrNL=K, ND=1, ξ=DALI,ADI=1,0, 0≤ALSLe+ADSLe≤K−11+ALSLe,ADSLe,L,SLrNL≥1, ND≥0, NL+ND≤K, ξ=LALI,ADI=1,0, ALSLe+ADSLe≥K, 0≤ALSLe≤K−11+ALSLe,K−ALSLe,L,SLr1≤NL≤K, NL+ND=K+1, ξ=LALI,ADI=1,0, ALSLe≥KK+1,0,L,SLrNL=K+1, ND=0, ξ=LIn addition, from the renewal theory, the joint distribution ofShe and Shr is given by(47)Prx≤She<x+dx,t≤Shr<t+dt=dShx+tdtESh,x,t≥0,h∈L,D.Thus, the joint distributions ofALShe, ADShe, and Shr are given by(48)a˜i,jhtdt=PrALShe=i,ADShe=j,t≤Shr<t+dt=1ESh∫x=0∞λLxii!λDxjj!e−λL+λDxdShx+tdt,i,j≥0,t≥0,h∈L,Da˜i,⋅htdt=PrALShe=i,t≤Shr<t+dt=1ESh∫x=0∞λLxii!e−λLxdShx+tdt,i≥0,t≥0,h∈L,D.Using the semi-Markov process theory, from the relationships in the first four rows and the eighth, ninth, and tenth rows in Table1, we have(49)PrNL=i,ND=j,ξ=D,t≤SDr<t+dt=∑l=0K∑m=0K−lPrNLd=l,NDd=m,ξ=D,×PrNL=i,ND=j,t≤SDr<t+dt|NLd=l,NDd=m,ξ=D=∑l=0K∑m=1K−lπl,mESDET⋅Prminl+ALSDe,K=i,minm+ADSDe,K−i+1=j,t≤SDr<t+dt+π0,0λD/λESDET⋅PrminALSDe,K=i,min1+ADSDe,K−ALSDe+1=j,t≤SDr<t+dt,which leads to(50)qi,j,Dt=ESDET∑l=0i∑m=1jπl,ma˜i−l,j−mDt+λDλπ0,0a˜i,j−1Dt,i≥0,j≥1,i+j≤K,ESDET∑l=0i∑m=1K−iπl,m∑n=K+1−m−i∞a˜i−l,nDt,+∑l=0i∑m=K+1−iK−lπl,ma˜i−l,⋅Dt+λDλπ0,0∑n=K−i∞a˜i,nDt,0≤i≤K−1,i+j=K+1,ESDET∑l=0K∑m=1K−lπl,m∑n=K−l∞a˜n,⋅Dt+λDλπ0,0∑n=K∞a˜n,⋅Dt,i=K,j=1.Similarly, from the relationships in the fifth, sixth, and seventh rows and the last three rows in Table1, we have(51)qi,j,Lt=ESLET∑l=1iπl,0⋅a˜i−l,jLt+λLλπ0,0a˜i−1,jLt,i≥1,j≥0,i+j≤K,ESLET∑l=1iπl,0∑K+1−i∞a˜i−l,nLt,+λLλ⋅π0,0∑K+1−i∞a˜i−1,nLt,1≤i≤K,i+j=K+1,ESLET∑l=1Kπl,0∑K+1−l∞a˜n,⋅Lt+λLλ⋅π0,0∑K∞a˜n,⋅Lt,i=K+1,j=0.Therefore, from (42), (50), and (51), we can calculate all the joint probabilities Qi,j of NL and ND, i,j≥0, i+j≤K+1, which will be utilized to derive the loss probabilities and mean queue lengths of both classes in Section 5. Moreover, the joint probabilities qi,j,htdt of the queue lengths and the remaining service time will be used to derive the waiting time distribution of a class-D packet.


## 6. Loss Probabilities and Mean Waiting Times

There are two types of packet loss under the push-out priority discipline. One occurs when a packet is blocked and lost on its arrival, and the other occurs when a class-L packet pushes out a class-D packet in the buffer. Let Pgb, g∈L,D, denote the probability that a class-g packet is blocked and lost on its arrival because the buffer is full of packets which have space priority higher than or the same as that of the class-g packet. Let PLpo also denote the probability that a class-L packet pushes out a class-D packet in the buffer on arrival of the class-L packet.Under the push-out priority discipline, class-D arrivals are always blocked if the buffer is full on their arrivals. Hence, from PASTA, the class-D blocking probability PDb is given by(52)PDb=PrNL+ND=K+1=∑i=0K+1Qi,K+1−i.However, class-L arrivals can push out class-D packets in the buffer even though the buffer is full. Thus, PLb is not identical to PDb. Note that class-L packets are blocked only when the buffer is full of K class-L packets and that, when ξ=L, there is one more class-L packet in service other than class-L packets in the buffer. Thus, from PASTA, the class-L blocking probability PLb is given by(53)PLb=PrNL=K+1,ξ=L+PrNL=K,ξ=D=QK+1,0,L+QK,1,D.Note also that a class-L packet pushes out a class-D packet in the buffer if the buffer is full and there are one or more class-D packets in the buffer on arrival of the class-L packet, and that, when ξ=D, there is one more class-D packet in service other than class-D packets in the buffer. Thus, from PASTA, we have(54)PLpo=PrNL+ND=K+1,ND≥1,ξ=L+PrNL+ND=K+1,ND≥2,ξ=D=∑i=1KQi,K+1−i,L+∑i=0K−1Qi,K+1−i,D.From (52)–(54), we also have(55)PDb=PLb+PLpo.Letλgb, λgpo, and λgs, g∈L,D, denote the blocked rate, push-out rate, and served rate of class-g packets. Then, since all class-L arrivals which are not blocked are served and all class-D arrivals which are neither blocked nor pushed out are served, we have(56)λgb=λgPgb,g∈L,D,λLpo=λLPLpo,λLs=λL−λLb=λL1−PLb,λDs=λD−λDb−λLpo=λD1−PDb−λLPLpo.In addition, since class-D packets arrive at rate λD and get pushed out at rate λLpo, the probability PDpo that a class-D arrival is pushed out in a steady state is given by(57)PDpo=λLpoλD=λLPLpoλD.Furthermore, if we letLg and LgQ, g∈L,D, denote the mean number of class-g packets in the system and in the buffer in a steady state, respectively, then we have(58)LL=∑i=1K+1∑j=0K+1−ii⋅Qi,j,LLQ=∑i=2K+1∑j=0K+1−ii−1⋅Qi,j,L+∑i=1K∑j=1K+1−ii⋅Qi,j,D,LD=∑i=0K+1∑j=1K+1−ij⋅Qi,j,LDQ=∑i=1K+1∑j=1K+1−ij⋅Qi,j,L+∑i=0K∑j=2K+1−ij−1⋅Qi,j,D.LetWg and WgQ denote the mean sojourn and queue waiting times of a served class-g packet in a steady state. Note that, when considering sojourn and queue waiting times, we exclude packets that are pushed out as well as being blocked. Thus, from Little’s law, we have(59)WL=LLλLs,WLQ=LLQλLs.However, the mean sojourn time and waiting time of a class-D packet cannot be obtained from Little’s law because class-D packets in the buffer can be either served or pushed out, and LD and LDQ take into account not only contribution by served class-D packets but also that by pushed-out class-D packets. Therefore, we employ a tagged customer approach to derive WD and WDQ instead.Suppose that we observe a tagged class-D packet in the buffer just after the n-th embedded point. Let Xdn denote the remaining queue waiting time of the tagged class-D packet after the n-th embedded point. Let NDd,beforen also denote the number of class-D packets in the system at the n-th embedded point which arrive before the tagged packet. Notice that the tagged class-D packet is finally either served or pushed out. Observe also that class-D packets which arrive after the tagged packet affect neither the waiting time of the tagged packet nor whether the tagged packet is finally served or pushed out because a push-out happens to the last arrived class-D packet in the buffer when the buffer is full.Since there are at mostK packets in the system just after the n-th embedded point, 0≤NLdn+NDd,beforen≤K−1 because one slot of the buffer is occupied by the tagged packet. We now define the partial LST (Laplace–Stieltjes Transform) Xi,jd∗s;n of Xdn as(60)Xi,jd∗s;n=Prserved|NLdn=i,NDd,beforen=j×Ee−sXdn|NLdn=i,NDd,beforen=j,served,i,j≥0,i+j≤K−1,ℜs≥0,where “served” is the event that the tagged packet is finally served.Suppose thatNDd,beforen=0. Then, the tagged packet enters its own service just after the embedded point, due to time priority. Hence, we have(61)Xi,0d∗s;n=1,0≤i≤K−1.Suppose now thatNDd,beforen≥1, then one class-D packet which arrived before the tagged packet enters its service, and there are NDd,before−1 class-D packets in the buffer which arrive before the tagged packet just after the n-th embedded point. Thus, there are NLdn+NDd,beforen−1 packets in the buffer which have effective space priority over the tagged packet, in the sense that they are not pushed out before the tagged packet is pushed out. Observe that if more than K−NLdn−NDd,beforen class-L packets arrive between the n-th and n+1-th embedded points, i.e., ALSD>K−NLdn−NDd,beforen, then the tagged packet will be pushed out by the n+1-th embedded point because the buffer will become full of K packets which will have effective space priority over the tagged packet by then. Thus, we have(62)Prserved|NLdn=i,NDd,beforen=j,ALSD>K−i−j=0.IfALSD≤K−NLdn−NDd,beforen, then the tagged packet is not pushed out between the n-th and n+1-th embedded points. Hence, the tagged packet needs to wait in the buffer during this transition of SD plus the remaining waiting time Xdn+1 after the n+1-th embedded point, when there are NL+ALSD class-L packets and NDd,before−1 class-D packets which arrive earlier than the tagged packet in the buffer. Thus, from the Markovian property at embedded points, we have, for 0≤l≤K−i−j,(63)Prserved|NLdn=i,NDd,beforen=j,ALSD=l×Ee−sXdn|NLdn=i,NDd,beforen=j,ALSD=l,served=Prserved|NLdn+1=i+l,NDd,beforen=j−1×Ee−sSD|ALSD=l×Ee−sXdn+1|NLdn+1=i+l,NDd,beforen+1=j−1,served.Therefore, conditioning on the numbers of class-L arrivals between the n-th and n+1-th embedded points leads to the following recursive formula:(64)Xi,jd∗s;n=∑l=0∞PrALSD=l⋅Prserved|NLdn=i,NDd,beforen=j,ALSD=l×Ee−sXdn|NLdn=i,NDd,beforen=j,ALSD=l,served=∑l=0K−i−jal,⋅D∗s⋅Xi+l,j−1d∗s;n+1,i≥0,j≤1,i+j≤K−1,where(65)al,⋅h∗s=PrALSh=l⋅Ee−sSh|ALSh=l=∫t=0∞λLtll!e−s+λLtdSht,h∈L,D,ℜs≥0.If we letXd=limn⟶∞Xdn and Xi,jd∗s=limn⟶0Xi,jd∗s;n, then from (61) and (64), we have(66)Xi,0d∗s=1,0≤i≤K−1(67)Xi,jd∗s=∑l=0K−i−jal,⋅D∗s⋅Xi+l,j−1d∗s,i≥0,j≤1,i+j≤K−1.Notice that allXi,jd∗s, i,j≥0, i+j≤K−1, can be obtained from the recursive formula (67) with the initial condition (66).LetX denote the queue waiting time of a tagged class-D packet which arrives at an arbitrary time.Define the partial LSTX∗s of the queue waiting time of the tagged class-D packet as(68)X∗s=Prserved⋅Ee−sX|served.Consider first the case where the tagged packet arrives when the buffer is full. Then, the tagged packet is lost, not served. Thus, we have(69)Prserved|NL+ND=K+1=0.Consider next the case where the tagged packet arrives when the system is empty, i.e., NL=ND=0. Then, the tagged packet immediately enters its service so that X=0. Thus, we have(70)Prserved|NL=ND=0⋅Ee−sX|served=1.Consider now the case where the tagged packet arrives when the system is not empty and the buffer is not full, i.e.,1≤NL+ND≤K. Then, the tagged packet joins the buffer immediately and observes the remaining service time Sξr of a class-ξ packet in service. Notice that the number of packets in the buffer just after the tagged packet joins the buffer is NL+ND because the tagged packet occupies one slot in the buffer. Notice also that, given that the tagged packet observes the remaining service time Sξr, if the number of class-L packets which arrive during Sξr is more than K−NL−ND, i.e., ALSξ>K−NL−ND, then the tagged packet will be pushed out during Sξr. Thus, we have(71)Prserved|1≤NL+ND≤K,ALSξ>K−NL−ND=0.IfALSξ≤K−NL−ND, then the tagged packet will wait the remaining service time Sξr until the first embedded point after the tagged packet’s arrival. After the embedded point, the remaining waiting time of the tagged packet after the embedded point is XNLd,NDd,befored where NLd is the number of class-L packets in the buffer and NDd,before is the number of class-D packets in the buffer which arrive earlier than the tagged packet at the embedded point. Furthermore, given ALSξ≤K−NL−ND, we have(72)NLd,NDd,before=NL+ALSξ−1,ND,ifξ=L,NL+ALSξ,ND−1,ifξ=D,because the packet in service on arrival of the tagged customer departs from the system at the embedded point. Thus, fori≥1, j≥0, i+j≤K, 0≤n≤K−i−j, we have(73)Prserved|NL=i,ND=j,ξ=L,ALSLr=n×Ee−sX|NL=i,ND=j,ξ=L,ALSLr=n,served=Prserved|NLd=i+n−1,NDd,before=j⋅Ee−sSLr|ALSLr=n×Ee−sSLr+Xd|NLd=i+n−1,NDd,before=j,served,and fori≥0, j≥1, i+j≤K, 0≤n≤K−i−j, we have(74)Prserved|NL=i,ND=j,ξ=D,ALSDr=n×Ee−sX|NL=i,ND=j,ξ=D,ALSDr=n,served=Prserved|NLd=i+n,NDd,before=j−1⋅Ee−sSDr|ALSDr=n×Ee−sXd|NLd=i+n,NDd,before=j−1,served.Therefore, conditioning onNL, ND, ξ, and ALSξr results in(75)X∗s=Q0,0+∑i=0K−1∑j=1K−i∑n=0K−i−jqi,j,D,n∗s⋅Xi+n,j−1d∗s+∑i=1K∑j=0K−i∑n=0K−i−jqi,j,L,n∗s⋅Xi+n−1,jd∗s,where(76)qi,j,h,n∗s=PrNL=i,ND=j,ξ=h,ALSξr=n×Ee−sSξr|NL=i,ND=j,ξ=h,ALSξr=n=∫t=0∞λLtnn!e−s+λLtqi,j,htdt,fori≥1ξ=L, j≥1ξ=D, i+j≤K+1, n≥0, h∈L,D.Thus, the LST of the queue waiting times of a class-D packet which is finally served is given by(77)Ee−sX|served=X∗sX∗0.Therefore, we finally have(78)WDQ=−X∗′0X∗0,WD=WDQ+ESD.


## 7. Numerical Examples

In this section, we explore the impact of the buffer sizeK, the arrival rates, and the service-time distributions on the performance measures with numerical examples.We first examine the impact of the buffer sizeK on the performance measures with the following numerical example: The arrival rates λL and λD are set to 1, and the mean service times ESL and ESD are set to 1/3. To see the effect of the service-time distributions of both classes, we use three distributions with the same mean of 1/3 for the service-time distributions: an exponential distribution with rate 3, an Erlang distribution with rate 6 and shape parameter 2, and a hyperexponential distribution with rates 6 and 3/2 and weights 2/3 and 1/3. The coefficients of variation (CVs) of the Erlang, exponential, and hyperexponential distributions are 1/2, 1, and 2, respectively. To explore the effect of K, the buffer size K varies from 1 to 7.Figure1 shows the blocking probabilities PLb and PDb, the push-out probability PDpo of class-D packets, and the mean sojourn times WL and WD as a function of the buffer size K. As seen in Figure 1, the blocking probabilities PLb (top-left) and PDb (top center) and the push-out probability Ppo (top-right) all decrease as K increases for all the combinations of the service-time distributions. (The labels in the legend are the distribution names of SL (before the hyphen) and SD (after the hyphen).) However, the mean sojourn times WL (bottom-left) and WD (bottom-right) increase as the buffer size K increases. This is because, for a smaller value of K, arrivals are more prone to loss, and a long queue cannot build. Additionally, the smaller the CVs of SL and SD, the smaller the blocking/push-out probabilities and the mean sojourn times. This is because large CVs of SL and SD lead to a high level of the buffer occupancy, which, in turn, results in high blocking and push-out probabilities and mean waiting times. In addition, we can observe higher blocking probabilities and lower mean sojourn times of class-D packets than those of class-L packets because we offer space priority to class-L packets but time priority to class-D packets.Figure 1
Performance measures over various values ofK.We now examine the impact of the arrival rateλL on the performance measures with the same numerical example as for the buffer size K, except that, to see the effect of λL, λL varies from 0.1 to 3.6, and the buffer size K is fixed to be 3. As seen in Figure 2, the blocking probabilities PLb and PDb and the push-out probability PDpo, as well as the mean sojourn time WL of class-L packets, increase as the arrival rate λL increases. (For brevity of presentation, the exponential cases are omitted in Figure 2.) This is because a large arrival rate λL leads to a high level of the buffer occupancy by class-L packets (see the top-left panel of Figure 3), which, in turn, results in high levels of the blocking probabilities of both classes and the mean sojourn time WL. However, the mean sojourn time WD of class-D packets does not follow this pattern (see the bottom-right panel of Figure 2). WD initially increases and then decreases as λL increases, except when SL has the Erlang distribution and SD the hyperexponential distribution. (For the Erlang-Hyper combination, WD decreases monotonically.) This is because there are positive and negative effects of λL on WD. As λL increases, the probability that the server is busy for class-L packets also increases (see the bottom-left panel of Figure 3 where ρLs=λLsESL). This negative effect of increasing λL makes the waiting time of class-D packets longer. However, this negative effect on WD is limited because class-L packets in the buffer do not affect WD due to the time priority of class-D packets. Only class-L packets in service have a negative effect on WD. On the other hand, as λL increases, the push-out probability of class-D packets rises (see the top-right panel of Figure 2). This effect makes the queue level of class-D packets low (see the top-right panel of Figure 3). For large values of λL, this positive effect of high push-out probabilities on WD dominates the negative effect of high server utilization. Hence, the mean sojourn time WD of class-D packets initially increases and then decreases.Figure 2
Performance measures over various values ofλL.Figure 3
Various factors over various values ofλL.In addition, for small values ofλL (e.g., λL=0.1), the lager the CV of SL, the larger the WD for the same distribution of SD (see the bottom-right panel of Figure 2). However, as λL increases, WD with a larger CV of SL rises and then falls more rapidly than that with a smaller CV of SL for the same distribution of SD. As a result, for large values of λL (e.g., λL=3.6), the larger the CV of SL, the smaller the WD. This phenomenon can also be explained by the negative and positive effects of λL on WD. When λL is small, the queue level of class-L packets is low and push-out rarely occurs (see the top-right panel of Figure 2). Hence, the negative effect of λL on WD dominates its positive effect. The negative effect of λL on WD is due to the remaining service time of class-L packets in service. Hence, a larger CV of SL results in a larger WL. On the other hand, when λL is large (e.g., λL=3), the buffer is nearly full of class-L packets due to the space priority of class-L packets, and the server is mostly occupied by class-L packets (see the top-left and bottom-left panels of Figure 3). Hence, it is highly likely that most class-D packets arrive during the service time of a class-L packet, and there is only one vacancy in the buffer at the beginning of the service of that class-L packet because the buffer is nearly full of class-L packets and the class-L packet enters its service from the buffer then. In this situation, a class-D packet can successfully join and be served mainly when there are no arrivals during the elapsed service time of the class-L packet in service (for joining the buffer) and no class-L arrivals during the remaining service time of the class-L packet in service (for no push-out before entering service). In this case, the mean queue waiting time of a class-D packet is ESLr|ALSLe=ADSLe=ALSLr=0. The bottom-right panel of Figure 3 shows ESLr|ALSLe=ADSLe=ALSLr=0 as a function of λL. (Since the distribution of SD does not affect this quantity, the lines of the different distributions of SD for the same SL distribution overlap perfectly.) As seen in the bottom-right panel of Figure 3, for small values of λL, the larger the CV of SL, the larger the ESLr|ALSLe=ADSLe=ALSLr=0, but for large values of λL, the larger the CV of SL, the smaller the ESLr|ALSLe=ADSLe=ALSLr=0, which, in turn, results in a larger WD. In other words, when λL is so large that class-L packets monopolize the buffer, the queue level of class-D packets is nearly zero so that the waiting time of a class-D packet which successfully joins and is served converges to the remaining service time of a class-L packet in service on its arrival, provided there are no more class-L arrivals during the service time of the class-L packet. In this case, the mean of this remaining service time tends to be smaller for a larger value of CV of SL.We now examine the impact of the arrival rateλD on the performance measures with the same numerical example as for the buffer size K, except that, to see the effect of λD, λD varies from 0.1 to 3.6, and the buffer size K is fixed to be 3. As seen in Figure 4, the blocking probabilities PLb and PDb and the push-out probability PDpo, as well as the mean sojourn times WL and WD, all increase as the arrival rate λD increases. (For brevity of presentation, the exponential cases are omitted in Figure 4.) In contrast with the impact of λL on WD, WD keeps increasing as λD increases. This is because, as λD increases, the queue level of class-D packets increases, which results in a negative effect on WD, but the positive effect of push-out on WD is limited when λL is fixed. (Compare the push-out probability of class-D packets in the top-right panel of Figure 4 with that in the top-right panel of Figure 2.) Moreover, similar to the effect of λL on WD for different values of CV of SL, for small values of λD, the larger the CV of SD, the larger the mean sojourn time WL and WD, but for large values of λD, the larger the CV of SD, the smaller the WL and WD, even though this tendency is mild.Figure 4
Performance measures over various values ofλD.We now examine the impact of the mean service timeESL on the performance measures with the same numerical example as for the buffer size K, except that, to see the effect of ESL, ESL varies from 0.2 to 2, and the buffer size K is fixed to be 3. As seen in Figure 5, the blocking probabilities and mean sojourn times of both classes increase as the mean service time ESL increases. (For brevity of presentation, the exponential cases are omitted in Figure 5.) However, the push-out probability PDpo of class-D packets initially increases and then decreases as ESL increases. This is because there are positive and negative effects of ESL on PDpo. As ESL increases, the mean queue length of class-L packets also increases (see the top-left panel of Figure 6). This negative effect makes the push-out probability of class-D packets high. On the other hand, as ESL increases, the server is nearly always occupied by class-L packets (see the bottom-left panel of Figure 6), and the buffer is nearly full of class-L packets, due to the space priority of class-L packets. In this situation, a class-D packet can successfully join and be pushed out by a class-L arrival mostly when there are no arrivals during the elapsed service time of the class-L packet in service (for joining the buffer) and one or more class-L arrivals during the remaining service time of the class-L packet in service (for push-out before the class-D packet enters service). In this case, the push-out probability is PrALSLe=ADSLe=0,ALSLr>0. As seen in the bottom-right panel of Figure 6, PrALSLe=ADSLe=0,ALSLr>0 initially rises and then falls, as ESL increases. (Since the distribution of SD does not affect this quantity, the lines of the different distributions of SD for the same SL distribution overlap perfectly.) This is because, as ESL increases, the expected number of class-D arrivals during SL linear increases, but when class-L packets nearly monopolize the buffer, only the first class-D arrival during SL has a chance to join and be pushed out, and the other class-D arrivals are simply blocked. Furthermore, as seen in the bottom-right panel of Figure 6, the lines of PrALSLe=ADSLe=0,ALSLr>0 for two different CVs of SL cross each other, which explains why the lines of the push-out probabilities PDpo of two different CVs of SL for the same distribution of SD also cross each other.Figure 5
Performance measures over various values ofESL.Figure 6
Various factors over various values ofESL.We finally examine the impact of the mean service timeESD on the performance measures with the same numerical example as for the buffer size K, except that, to see the effect of ESD, ESD varies from 0.2 to 2, and the buffer size K is fixed to be 3. As seen in Figure 7, the blocking probabilities PLb and PDb, the push-out probability PDpo, and the mean sojourn times WL and WD all increase as the mean service time ESD increases. (For brevity of presentation, the exponential cases are omitted in Figure 7.) In contrast with the impact of ESL on PDpo, as ESD increases, the slope of PDpo becomes flat, but does not fall to negative. This is because the effect of ESD is limited by the space priority of class-L packets. While, as ESL increases, the server utilization ρL=λLsESL by class-L packets approaches 1 (see the bottom-left panel of Figure 6), as ESD increases, the server utilization ρD=λDsESD by class-D packets does not approach 1 (see the bottom-right panel of Figure 7).Figure 7
Performance measures over various values ofESD.In summary, the buffer size, the arrival rates, and the mean service times all have significant effects on the performance measures. In general, for higher CVs of the service-time distributions, the system performance measures become worse because the buffer level grows higher. However, this can be not the case when the buffer is nearly monopolized by packets of the space-priority class. As seen in the bottom-right panel of Figure2 and the top-right panel of Figure 5, the service-time distribution of space-priority packets has different effects on the performance measures, depending on whether the buffer is nearly monopolized by space-priority packets or not.


## 8. Conclusions

In this paper, we analyzed a finite-buffer M/G/1 queueing model with two priority classes, where delay-sensitive traffic was given time priority and loss-sensitive traffic was given space priority, to meet the diverse QoS requirements of both types of traffic. To do this, we first derived the algorithm for computing the joint queue-length distribution at departure epochs using the embedded Markov chain; then, we obtained the joint distributions of queue lengths and remaining service time at an arbitrary time using the semi-Markov process. Using these distributions, we derived the performance measures, such as loss probabilities, push-out probabilities, and mean waiting times for the proposed queueing models. With several numerical examples, we finally demonstrated the applicability of the proposed analysis and explored the effect of system parameters on the performance measures.Compared to the previous study [9], which tackled a queueing model having identically and exponentially distributed service times for both types of traffic, this study dealt with a queueing model having differently and generally distributed service times for different types of traffic. As a result, the performance measures could be explored not only as functions of the buffer size K, the arrival rates, and the mean service time, but also for different service-time distributions. As seen in Section 6, the service-time distributions with different CVs had different effects on the performance measures, especially when the arrival rate and mean service time of the space-priority packets changed. Therefore, it is expected that we can predict the performance measures of the system more accurately, if the proposed finite-buffer M/G/1 model with time and space priorities is employed, instead of the finite-buffer M/M/1 model, to analyze communication systems accommodating multiple types of traffic with different service-time distributions.We finally conclude this paper with future research directions. In this study, we assumed that the time-priority discipline was nonpreemptive and the space-priority discipline was the push-out mechanism. Our study can be extended to time-space-priority queueing models with other time- and space-priority disciplines. For example, the space-priority discipline can be the partial buffer-sharing mechanism, and/or the time-priority discipline can be preemptive. If this research is achieved, then we can analyze the effect of different combinations of space- and time-priority disciplines on system performance and could design an optimal priority policy to balance different service requirements of loss- and delay-sensitive types of traffic.In addition, the proposed method can be extended to the analysis of the corresponding batch-arrival model and the corresponding discrete-time model. For the batch-arrival model, there are two different batch acceptance policies regarding how to accept a batch whose arrival makes the buffer exceed the capacity. While for the partial-acceptance policy, a part of the arriving batch joins the buffer until the buffer becomes full, for the total rejection policy, the whole batch is blocked (see [[30], Sec. 5.6]). For the partial-acceptance policy, it is expected that the embedded Markov chain and the semi-Markov process have a stochastic structure so similar to those in this study that the proposed method can be applied to the batch-arrival model. However, for the total rejection policy, constituting the embedded Markov chain is very difficult (see [[30], Sec. 5.6]), so an approach other than the proposed method will be needed to analyze the batch-arrival model. Similarly, the corresponding finite Geo/G/1 model and the corresponding partial-acceptance finite GeoX/G/1 model can be tackled with the proposed method because the embedded Markov chain and semi-Markov process have a similar structure.



---

*Source: 4539940-2022-05-20.xml*