# Convolution Model of a Queueing System with the cFIFO Service Discipline

Authors: Sławomir Hanczewski; Adam Kaliszan; Maciej Stasiak
Journal: Mobile Information Systems
 (2016)

---

## Abstract

This article presents an approximate convolution model of a multiservice queueing system with the continuous FIFO (cFIFO) service discipline. The model makes it possible to service calls sequentially with variable bit rate, determined by unoccupied (free) resources of the multiservice server. As compared to the FIFO discipline, the cFIFO queue utilizes the resources of a multiservice server more effectively. The assumption in the model is that the queueing system is offered a mixture of independent multiservice Bernoulli-Poisson-Pascal (BPP) call streams. The article also discusses the results of modelling a number of queueing systems to which different, non-Poissonian, call streams are offered. To verify the accuracy of the model, the results of the analytical calculations are compared with the results of simulation experiments for a number of selected queueing systems. The study has confirmed the accuracy of all adopted theoretical assumptions for the proposed analytical model.


---

## Body

## 1. Introduction

In recent years there has been a rapid increase in development of networks, in particular of mobile networks. While the evidence indicates that increasing competition is bringing down the cost of mobile services and user equipment, this implicates that more and more of the percentage of total network traffic is generated by mobile devices. According to the report [1], there were 7.3 billion active mobile devices in 2015, while the identified global trends are reporting much increased smartphone-generated traffic with each smartphone generating 1.4 Gb per month on average. It is also worth noticing that the ever-increasing number of users is using wireless broadband access networks. The authors of the report estimate that the number of active devices operating on LTE networks will reach 4.3 billion in 2021.The dynamic development of telecommunications (mobile) networks, the growing number of offered online services with strictly defined Quality of Service (QoS) parameters, and the ever-increasing number of network users cause network operators to introduce a number of different traffic management mechanisms that increase the effectiveness of the network. Good examples of the above mechanisms are threshold compression mechanisms [2–4] and thresholdless compression mechanism that allow elastic and adaptive traffic to be supported [5, 6]. In the case of systems with real time services it is necessary to ensure an appropriate delay level and/or deviation from true periodicity of a presumed periodic signal (jitter). As a result, analyses of these systems are not feasible unless appropriate models of queueing systems that would take into account the multiservice nature of traffic are constructed. A great number of works, including [7–9], discuss a solution that is based on a single-service Erlang C model with the accompanying assumption that all call classes have similar characteristics and service conditions. Another solution proposes an application of a recurrent formula that describes the occupancy distribution in full-availability multiservice systems with elastic traffic [5]. The model presented in [6] has an accompanying assumption that all streams of serviced traffic—if there is an instance of a lack of free resources in the system—can be compressed without limit, which eventually leads to lossless traffic service. Here, the level of compression can be interpreted as a measure of delay for all call classes. These solutions, however, do not allow us to determine delay parameters for individual call classes. In [10–13] new queueing models are proposed that make it possible to determine individual delay characteristics for particular call classes offered to the system with a queueing discipline called state-dependent FIFO (SD-FIFO). This discipline ensures access to a multiservice server to be available for all classes of calls, while the division of the resources of a server between individual call classes depends on the number of all calls that are currently in the queueing system and corresponds to the balanced fairness algorithm [14, 15] for the division of resources in multiservice systems.This article proposes an approximate model of a queueing system with continuous FIFO (cFIFO) service discipline for a mixture of multiservice Bernoulli-Poisson-Pascal (BPP) call streams. In general, the cFIFO discipline assumes that calls that are in the queue are serviced according to the FIFO discipline. However, when the server has a lower amount of resources than demanded by the first call in the queue, then it can start servicing this call with a lower bitrate than the one demanded by the call. In the proposed model, a convolution algorithm is used to determine the occupancy distribution in the queueing system. Appropriate convolution algorithms to model full-availability multiservice systems with losses and multiservice access network systems (the so-called multiservice tree network) are proposed in [16–18]. Papers [19, 20] propose convolution algorithms to model multiservice full-availability systems with resource reservation. Paper [21] develops and discusses a two-dimensional convolution model for a multiservice overflow system. Yet another work [22] proposes a generalized version of a convolution algorithm that makes it possible to model different multiservice state-dependent systems. The advantage of convolution algorithms is that they provide a possibility to model approximately systems with call streams with different distributions, provided they are not mutually dependent. Hence, in order to present the capabilities of the proposed model, this article also presents the results of a comparison of the analytical model with the data obtained by the digital simulation experiments for traffic streams other than BPP call streams. It is worthwhile to stress that convolution algorithms have never been used in the analysis of queueing systems before.The article is organized as follows. Section2 provides a description of a multiservice queueing system with the SD-FIFO discipline. Section 3 presents a description of a multiservice queueing system with the continuous discipline cFIFO. Section 4 proposes an analytical convolution model of the considered queueing system. A number of exemplary results of a comparison of the analytical model with the results of a simulation are provided and discussed in Section 5. The last section, Section 6, is a short summary of the article.


## 2. Queueing System with the SD-FIFO Discipline

The multiservice queueing system with the SD-FIFO queue service discipline is described in [10, 11, 13]. The analytical model developed for this system allows the most important parameters that characterize the queueing system (such as the average time for a call to be in the queue or the average queue length) to be determined for each call class offered to the system. An exemplary SD-FIFO system is shown in Figure 1. The system is composed of a multiservice server with the capacity V allocation units (AUs) (allocation unit is the capacity unit for broadband systems [23, 24]. Typically, it is defined as the greatest common divisor of the maximum bitrates of individual calls [25] or equivalent bandwidths [26] determined for offered call streams. A method for a determination of allocation units in telecommunications systems is provided in the Appendix) and a buffer with the capacity U AUs. The notion of the multiservice server is understood to be a server with the capacity that enables concurrent service to a number of calls with different demanded bitrates to be effected. The system (Figure 1) is offered 3 call classes. In the considered SD-FIFO queueing system, virtual queues for each call class serviced by the system are created within one buffer. Depending on the number of calls that are currently in the system, appropriate resources of the server are allocated to individual classes. The amount of these resources varies every time the number of calls of individual classes that are currently in the system is changed (resulting by a termination of service or admittance of a new call). According to this discipline, in each occupancy state of the system, appropriate resources of the service are allocated to calls of all classes. It should be stressed that the method for resource allocation in the server for individual call classes is compatible with the balanced fairness algorithm, well known from the literature of the subject [14, 15].Figure 1
Queueing system with the SD-FIFO service discipline.The system is composed of a multirate server with the capacityV AUs and a buffer with the capacity U AUs. The system is offered a set of M traffic classes of the type T (T∈Er,En,Pa,G), where(i)
Er denotes the Erlang traffic (Poisson call stream),(ii)
En denotes the Engset traffic (Bernoulli call stream),(iii)
Pa denotes the Pascal traffic (Pascal call stream),(iv)
G denotes a type of traffic, with non-Poissonian call stream whose properties have been determined either empirically or in a simulation.The cardinality of the set M, that is, the number of traffic classes offered to the system, is equal to mM=m. Any randomly chosen traffic class c demands tT,c AUs for service. This notation method will be also used in the remaining part of the article to identify the parameters related to the considered call classes. We notice that the mixture of Erlang, Engset, and Pascal traffics is denoted as BPP traffic.Let us consider now a queueing system with the SD-FIFO discipline composed of a multiservice server with the capacityV AUs and a buffer with the capacity U AUs. The system is offered a set of M traffic classes of the Erlang-type call classes. Individual call classes are described by the following parameters:(i)
λEr,i is the intensity of a call stream of class i0<i≤m,(ii)
μEr,i is the intensity of a service stream of class i,(iii)
tEr,i is the number of AUs demanded by a call of class i,(iv)
aEr,i is the traffic intensity of class i:(1)aEr,i=λEr,iμEr,i.The occupancy distribution in the system with the SD-FIFO discipline is determined on the basis of the following recurrence [11]: (2)QnV,UM=1min⁡n,V∑i=1maEr,itEr,iQn-tEr,iV,UMfor0≤n≤V+U,0otherwise,where QnV,UM is the probability that there are n occupied AUs in the system with server capacity V AUs and buffer capacity U AUs. To the system a set of M traffic classes is offered.It is possible to determine on the basis of the distributionQnV,UM the parameter yEr,inV,U, that is, the number of calls of class i serviced in the server in state n: (3)yEr,inV,U=aEr,itEr,iQn-tEr,iV,UMQnV,UM.The yEr,inV,U parameter determines then the resources occupied in the server by a given traffic class and is dependent on the occupancy distribution QnV,UM. This means that the resources occupied in the server by a given call class are dependent on the occupancy state of resources n by all traffic classes in the system (serviced in the server and those in the queue).Thus, Formula (3) defines the queueing service discipline in the system determined by distribution (2), that is, that from a virtual queue of class i; in a given occupancy state of system n, this number of calls of this class is taken for service that satisfies (3). Because of these dependencies, this discipline is labeled SD-FIFO [11].On the basis of distribution (2) one can determine the appropriate queueing characteristics for the system under consideration [11], for example, average waiting time, average queue length, or blocking probability.


## 3. Queueing System with Continuous cFIFO Discipline

Let us consider the multiservice queueing system presented in Figure2. Calls that are in the queue are serviced according to the proposed cFIFO discipline. In the case when the multiservice server has a lower throughput than the bitrate required by the first call that is in the queue to be serviced, then the server can start servicing this call with a lower bitrate than the demanded tT,c AUs. Figure 2 shows a call, marked with the hyphenated line, that demands 3 AUs. The server only has two free AUs; hence—in line with the cFIFO service discipline—2 AUs of the considered call will be serviced in the server, while one AU will be waiting for service in the buffer. Only one call in the system can be serviced with a lower number of AUs than that demanded for service. Such a concept ensures the maximum usage of the resources of the server providing at the same time a simple algorithm for buffer service.Figure 2
Queueing system with cFIFO queueing discipline.Let us consider now the operation of a queueing system with the system with the parametersV=2 AUs and U=2 AUs, presented in Figure 3(a), as an example. This system can be analyzed either at the microstate level (Figure 3(b)) or at the macrostate level (Figure 3(c)). Microstate of the multiservice service process is defined by the number of calls of individual classes serviced in the server and waiting in the buffer [11]. Macrostate is then defined by the total number of AUs that are occupied by calls that are in the system, that is, those that are being serviced in the server and those waiting in the buffer [11]. The macrostate does not take into consideration the distribution of occupied AUs between individual classes of calls. The system presented in Figure 3(a) is offered two call classes that demand tT,1=1 and tT,2=2 AUs, respectively. Each microstate of the process is represented by the ordered set X/Z = xT,1;xT,2/zT,1;zT,2, where the values xT,1 and xT,2 define the number of calls of classes 1 and 2 that are serviced in the server and the values zT,1 and zT,2 define then the number of calls of classes 1 and 2 that are waiting in the buffer. In Figure 3(b), the microstate 1;0.5/0;0.5 determines such an occupancy state of the considered queueing system in which a call of class 2 is serviced in the server with a lower number of AUs than that demanded; that is, one AU (“0.5 of the call”) is serviced in the server and one AU (“0.5 of the call”) is waiting in the buffer. Let us consider two possible ways of service termination for a call of class 2 in the microstate under consideration. In the first case, after the termination of service for a call of class 1, the server starts to service a call of class 2 with the demanded number of tT,2 = 2 AUs (in Figure 3(b) it is the transition from microstate 1;0.5/0;0.5 to microstate 0;1/0;0). In the second case, because of long service time for the call of class 1, the considered call of class 2 is serviced with tT,2=1 AU throughout the service (in Figure 3(b) it is the transition from microstate 1;0.5/0;0.5 to microstate 1;0/0;0).Figure 3
Queueing system with cFIFO discipline (V=2 AUs, U=2 AUs): (a) visualization of macrostate {1;0.5/0;0.5}, (b) service process, microstate level, and (c) service process, macrostate level.
(a) (b) (c)


## 4. Model of a Queueing System with cFIFO Discipline

The model of a queueing system proposed in the article has been developed at the macrostate level. This means that the occupancy state is described by just one parameter, namely, the total number of occupied AU in the system (i.e., together in the server and buffer). Each macrostateΩn is the sum of such microstates X/Z that satisfies the following condition: (4)Ωn=XZ:∑c=1mxT,ctT,c+∑c=1mzT,ctT,c=n.A description of a system at the macrostate level greatly simplifies its analysis in that it limits the analysis to a lower number of states. In the system presented in Figure 3(a), and defined by the parameters V=2 AUs, U=2 AUs, the number of microstates is equal to 12 (Figure 3(b)), whereas the number of macrostates is equal to 5 (Figure 3(c)). In Figure 3(b), the contours of the microstates that belong to one macrostate are marked by identical line. For example, macrostate Ω3 includes the following microstates: 2;0/1;0, 1;0.5/0;0.5, and 0;1/1;0.


### 4.1. Convolution Algorithm

Multiservice telecommunications systems can be generally modelled by algorithms that analyze either the dependencies between microstates or macrostates. The one approach is characterized by a large computational complexity [27], whereas the other approach is effective in modelling systems that are offered Poisson call streams. Papers [16, 17] propose convolution algorithms that make it possible to model systems with multiservice traffic on the basis of mutually independent occupancy distributions. These distributions are determined for all call streams offered to the system and can be determined on the basis of appropriate models and theoretical single-service systems. They can also directly result from conducted measurements in real systems or from simulation experiments for a number of selected classes of calls.Let us consider now the operation of a convolution algorithm with a multiservice system that is composed of a server with the capacityV and a buffer with zero capacity (U=0) as an example [28, 29]. In the literature of the subject this system is frequently labelled as the full-availability group (FAG) [30]. Our assumption is that the system is offered a set of MM=m traffic classes of the type T (T∈Er,En,Pa,G) and any randomly chosen traffic class c demands tT,c AUs for service.The input data for the convolution algorithm are the occupancy distributions for single classespV,0T,c, where c∈M. In the adopted notation for the distribution pV,0T,c the first expression in the lower index V defines the capacity of the server, while the second element U defines the capacity of the buffer (in the system under investigation, the buffer with zero capacity U=0 is considered). The distributions pV,0T,c are determined with the assumption that the system with the capacity V is offered only one class of calls. For Erlang, Engset, or Pascal traffic classes, to determine this distribution one can use appropriate theoretical distributions [31]; for example, in the case of class i of Erlang traffic, the distribution for a single class can be determined on the basis of the Erlang distribution:(5)pxvEr,iEr,i=aEr,ix/x!∑l=0vEr,iaEr,il/l!,where x∈0≤x≤vEr,i and aEr,i is the traffic intensity of class i, whereas the parameter vEr,i denotes the maximum number of calls that can be serviced in the server with the capacity V:(6)vEr,i=VtEr,i.In the case of Engset and Pascal traffic, the distributions of single classes can be determined on the basis of the following formulas:(7)pxvEn,jEn,j=SEn,jxγEn,jx∑l=0vjSEn,jlγEn,jl,(8)pxvPa,kPa,k=-SPa,kx-γPa,kx∑l=0vk-SPa,kl-γPa,kl,where the parameters γEn,j and γPa,k define the average intensity of calls offered by a single free Engset and Pascal traffic source. The parameters SEn,j and SPa,k are the total number of Engset and Pascal traffic sources. The relationship between the average traffic offered to the system by Engset traffic stream aEn,j and Pascal traffic stream aPa,k and the parameters γEn,j and γPa,k is as follows:(9)aEn,j=SEn,jγEn,j1+γEn,j,(10)aPa,k=-SPa,k-γPa,k1+-γPa,k.The occupancy distributionpV,0T,c=p0V,0{T,c},p1V,0T,c,p2V,0T,c,…, pnV,0T,c,…,pVV,0T,c of a single class c, determining the occupancy probabilities for all macrostates n (such that n=x·tT,c AUs) in the server with the capacity V, is related to distribution (5) by the following dependence:(11)pnV,0T,c=pxvT,cT,cforn=x·tT,c,0≤x≤vT,c0for  remainingn.In the case of other traffic streams (of the typeG), distributions of single classes can be determined on the basis of measurements taken in real systems or on the basis of relevant simulation experiments.By having the single distributions for all classes offered to the systempV,0T,c at our disposal we can now determine the aggregated distribution P•,0M which is the result of the convolution operation of all distributions for single classes offered to the system: (12)P•,0M=pV,0T,1∗pV,0T,2∗⋯∗pV,0T,m.The distribution P•,0M is not a normalized distribution. After an appropriate normalization process, the normalized distribution PV,0M can be written in the following form: (13)PV,0M=kP0•,0M,kP1•,0M,…,kPV•,0M,where k is the normalization constant: (14)k=1∑n=0VPn•,0M.Let us note that, for example, as a result of the convolution operation of two normalized distributions with the lengthV, a distribution with the length 2V is obtained. From the point of view of the considered system with the capacity of V AUs, all states n>V will never occur. Therefore, such states, in the distribution with the length 2V must be removed and distribution must be normalized. This process is discussed in detail in [16, 17, 19], among others.In (12), the symbol ∗ denotes the convolution operation which is defined in the following way: (15)P•,0A∪B=PV,0A∗PV,0B=P0V,0AP0V,0B,P0V,0AP1V,0B+P1V,0AP0V,0B,…,∑l=0nPlV,0APn-lV,0B,…,∑l=0VPlV,0APV-lV,0B,where the symbol PV,0A denotes the normalized distribution of a single class or the aggregated distribution of a number of classes that belong to a given set A (A∈M), whereas the symbol PV,0B denotes the normalized distribution of a single class or the aggregated normalized distribution of a number of classes that belong to a given set B (B∈M and A∩B=0). The symbol P•,0A∪B defines the aggregated nonnormalized distribution that is the result of a convolution of the distributions from the sets A and B.The convolution operation (15) enables us to determine the average number yT,cnV,0 of serviced calls of class c in the server with the capacity V AUs with zero buffer that is in the occupancy state n AUs. A determination of this parameter should take into consideration the following reasoning [30]. First, the aggregated nonnormalized distributions of all classes, except class c, are to be determined: (16)P•,0M∖c=pV,01∗⋯∗pV,0c-1∗pV,0c+1∗⋯∗pV,0m.Then, on the basis of the distributionsP•,0M∖c and pV,0c the value of the parameter yEr,cnV,0 can be determined, that is, the average number of calls of class c in occupancy state n of the server:(17)yT,cnV,0=∑l=0nlplV,0cPn-l•,0M∖ctT,c∑l=0nplV,0cPn-l•,0M∖c.


### 4.2. Model of the cFIFO Queueing System for Poisson Traffic Streams

Let us consider now the queueing system with the cFIFO service discipline the operation of which is presented in Section3. Our assumption is that this system is offered m Erlang traffic streams for which call arrival intensities of new calls are described by Poisson distributions with the parameters λEr,1,…,λEr,i,…,λEr,m for each traffic class, respectively. Service time is described with exponential distributions with the parameters μEr,1,…,μEr,i,…,μEr,m. Individual call classes demand, respectively, tEr,1,…,tEr,i,…,tEr,m AUs for service. In the case of Erlang traffic, it is assumed that the number of traffic sources is infinite. This means that the call arrival intensity for new call arrivals λEr,i of a given class i is independent of the number of calls of this class that are currently in the system: (18)λEr,in=λEr,ifor0⩽n⩽V+U.The intensity of offered Erlang traffic of class i can be determined on the basis of Formula (1):(19)aEr,i=aEr,in=λEr,iμEr,ifor0⩽n⩽V+U.By expressing the call intensity for a given class i in allocation units per time unit (the product λEr,itEr,i), we can express traffic offered to the system in the following form: (20)AEr,i=aEr,itEr,i.Paper [30] analyzes the dependence between the occupancy distribution in a multiservice full-availability system and the occupancy distribution in a multiservice state-dependent system, with the assumption of identical capacity and traffic offered to both systems. A similar approach will be now applied to the queueing model proposed in the article to determine the dependence between the occupancy distribution PnV+U,0M in the server with zero buffer and the distribution QnV,UM in the considered queueing system: (21)QnV,UM=δnPnV+U,0M,where δn defines the relation between the corresponding probabilities QnV,UM and PnV+U,0M, that is, the probability that the queueing system (V,U) is in state n AUs and the occupancy probability n AUs in the server with zero buffer (V+U,0), with the assumption that traffic offered to both systems is identical. To determine the parameter δ(n) we can use the recurrence dependencies derived for multiservice SD-FIFO queueing systems. The distribution QnV,UM in the cFIFO system is then approximated by distribution (2) that, with (20) taken into consideration, will be rewritten in the following way: (22)QnV,UM=1min⁡n,V∑i=1mAEr,iQn-tEr,iV,UMfor0≤n≤V+U,0otherwise.Assuming, then, that the method for a determination of the occupancy distribution in the queueing system and in the system with zero buffer (when the system is offered Erlang call classes) is known, it is possible to determine the value of the parameterδ(n) by dividing both sides of (22) by the probabilities PnV+U,0M: (23)QnV,UMPnV+U,0M=1min⁡n,V∑i=1mQn-tEr,iV,UMPnV+U,0MAEr,i.Equation (23), with (21) taken into consideration, can be easily transformed into an iterative formula for the parameter δ(n): (24)δn=1min⁡n,V∑i=1mδn-tEr,iPn-tEr,iV+U,0MAEr,iPnV+U,0M.The Markov process in the server with zero buffer to which a mixture of Erlang traffic classes is offered is a reversible process [28, 29]. For the neighboring states Ω(n) and Ωn-ti, because of class i, it is possible then to write local balance equations: (25)AEr,iPn-tEr,iV+U,0M=tEr,iyEr,inV+U,0PnV+U,0M.Now, taking into consideration (25), (24) can be rewritten in the following form: (26)δn=∑i=1mδn-tEr,iyEr,inV+U,0tEr,imin⁡n,V,The convolution operation makes a determination of the occupancy distributionPV+U,0M and the average number of calls of individual classes yEr,inV+U,0 serviced in the server with zero buffer (Formulas (16) and (17)) possible. These results enable us then to assess the value of the parameter δn (Formula (26)) and eventually to evaluate the occupancy distribution in the queueing system QnV,UM on the basis of (21).


### 4.3. Commentary

In Section4.2, to find the general dependence δn between the cFIFO queueing system described by the parameters (V,U) and the system with zero buffer (V+U,0) the occupancy distribution QnV,UM in the SD-FIFO system is used. The possibility of an approximation of the cFIFO system by the SD-FIFO system results from significant similarities in both queue service disciplines involved. In the cFIFO discipline considered in the article only one call can be partly serviced in the server and partly waiting in the queue. The SD-FIFO discipline, in turn, allows even a number of calls to be partly serviced simultaneously. In both instances, however, resources of the server are used maximally and it is just this fact that determines the probability of occupancy distributions for systems with cFIFO and SD-FIFO queues. Figures 4 and 5 show the occupancy distribution QnV,U in a queueing system with the structural parameters V=20 AUs and U=10 AUs, respectively. The occupancy distributions in the SD-FIFO system and the cFIFO system obtained in a simulation were then compared. The systems were offered three Erlang traffic streams with the following demands: tEr,1=1 AU, tEr,2=2 AUs, and tEr,3=3 AUs. Traffic was offered in the following proportions: AEr,1:AEr,2:AEr,3=1:1:1. Figure 4 shows the occupancy distributions for the case of small system loads (a=0.6 Erl/AU) and Figure 5 for large system loads (a=1.2 Erl/AU), where a is the average traffic offered per AU of the system:(27)a=AEr,1+AEr,2+AEr,3V.Figure 4
Occupancy distributions in SD-FIFO and cFIFO queueing systems (a=0.6 Erl/AU).Figure 5
Occupancy distributions in SD-FIFO and cFIFO queueing systems (a=1.2 Erl/AU).The simulation results are shown with 95% confidence interval determined on the basis of the Student distribution for 5 series, 100,000 calls each. The results for the presented comparison indicate a very good convergence of occupancy distributions in the SD-FIFO and cFIFO queueing systems. The simulation experiments for other systems differentiated by their capacity, number, and demands of offered traffic classes conducted by the authors earlier confirm strong convergence of occupancy distributions of both queueing systems.It should be stressed that queueing characteristics (such as the average number of calls of particular classes in the queue in corresponding occupancy states of the system) are not characterized by just as good convergence as the occupancy distributions. This would be the first reason why the SD-FIFO model cannot be directly applied to determine queueing characteristics for the cFIFO system. The other reason is the fact that to determine the parameterδ(n) (Formula (26)) the occupancy distribution of the SD-FIFO queueing system, derived for Erlang traffic, is used. In the case of other traffic streams, we do not observe such a good convergence between distributions for the SD-FIFO and cFIFO systems any longer. However, Formula (26) turns out to be very universal and versatile and approximates cFIFO queueing systems that service traffic with any, mutually independent, call streams very well. Appropriate numerical examples are presented in Section 5.


### 4.4. Characteristics of cFIFO System with Erlang Traffic

By having the knowledge of the coefficientsδ(n) at hand we are in position to determine the occupancy distribution QV,UM in a queueing system with the cFIFO discipline. This distribution can also provide a basis for a determination of appropriate QoS parameters, such as the blocking probability Ei and the average number of occupied AUs in queue L. The phenomenon of blocking for calls of class i in the queueing system occurs when the queue lacks tEr,i free AUs to store a new call of class i. Therefore, (28)EEr,i=∑n=V+U-tEr,i+1V+UQnV,UM.The average queue length L (for calls of all classes) is a mean value for the resources (expressed in AUs) occupied by calls of all classes that are waiting in the queue:(29)L=∑n=1UnQV+nU,VM.Let us consider now a method for a determination of the average numberLEr,i of busy AUs in a queue occupied by calls of class i. This article proposes an approximate determination of this parameter on the basis of the following reasoning. First, it is the average number of LEr,i AUs occupied by calls of class i that are waiting in the queue that has to be determined: (30)LEr,i=∑n=V+1V+UzEr,intEr,iQnU,VM,where zEr,i(n) is the average number of calls of class i waiting in the queue in state n of the system. The product zEr,i(n)tEr,i is the average number of AUs occupied in the buffer by waiting calls of class i in state n. In states n such that n≤V, the queue is empty; therefore the product zEr,i(n)tEr,i is equal to zero.In statesn such that n>V, the total number of occupied AUs in the queue (by calls of all classes) can be determined as follows: (31)∑i∈MzEr,intEr,i=n-V.Between the neighboring states n-1 and n there is a difference in the number of busy AUs occupied by calls of class i waiting in the queue, which, in the article, is denoted by the symbol ΔEr,cn. We can thus write (32)zEr,in·tEr,i=zEr,in-1·tEr,i+ΔEr,in,where (33)∑i∈MΔEr,in=1.Let us assume that the parameter ΔEr,i(n) is proportional to the intensity in which the buffer is occupied by calls of a given class i. We can therefore determine the value of the parameter ΔEr,i(n) in the following way: (34)ΔEr,in=Qn-tEr,iV,UMλEr,iφEr,in-tEr,i∑j∈MQn-tEr,jV,UMλEr,jφEr,jn-tEr,j,where (35)φEr,in-tEr,i=tEr,iforn-tEr,i≥V,n-VforV-tEr,i<n-tEr,i<V.Equation (35) is the result of a particular service discipline in the cFIFO queue. If in system state n-tEr,i a new call of class i arrives, then in the occupancy states of the server that are determined by the condition V-tEr,i<n-tEr,i<V a number of AUs of the considered call of class i will be immediately serviced by the server, while the remaining part will be directed to the queue. If n-tEr,i>V, then all AUs of a new call of class i will be immediately placed in the queue. Equations (34) and (35) can be written as just one equation in the following way: (36)ΔEr,in=Qn-tEr,iV,UMλEr,i·min⁡tEr,i,n-V∑j∈mQn-tEr,jV,QMλEr,j·min⁡tEr,j,n-V.Ultimately, (32), taking into account (36), can be written as follows: (37)zEr,intEr,i=zEr,in-1tEr,i+Qn-tcV,UMλEr,i·min⁡tEr,i,n-V∑j∈mQn-tEr,jV,UMλEr,j·min⁡tEr,j,n-V,where n>V. A determination of all values zEr,i(n) will make it possible, on the basis of (30), to evaluate and assess all queue lengths for calls of individual classes.


### 4.5. Model of a Queueing System with cFIFO Discipline and State-Dependent Call Streams

To determine the occupancy distribution in a queueing system with the cFIFO queueing discipline and offered BPP traffic (or traffic with any distribution of the call stream) we will use the general recurrence dependencies derived for a system with Erlang traffic (Section4.4). To determine the occupancy distribution in the cFIFO queueing system with BPP traffic we use then dependencies (21) and (25) that, in their generalized form, can be rewritten as follows: (38)QnV,UM=δnPnV+U,0M,(39)δn=∑c=1mδn-tT,cyT,cnV+U,0tT,cmin⁡n,V,where the parameter yT,cnV+U,0 is determined on the basis of a convolution operation (Formulas (16) and (17)). The occupancy distribution for the server with zero buffer PnV+U,0M in Formula (38) is determined on the basis of a convolution algorithm for which the input data are the distributions of single classes, determined for Erlang traffic by Formula (5) and for Engset and Pascal traffic by Formulas (7) and (9) as well as (8) and (10), respectively.It should be emphasized that the application of the convolution algorithm in the proposed model makes it possible to determine characteristics of queueing systems for call streams other than BPP streams. Distributions of single classes that are the input data for the convolution algorithm can be then determined empirically on the basis of measurements or by simulation experiments.On the basis of the occupancy distributionQV,UM, according to (28) and (29), it is possible to determine the blocking probability and the average queue length for calls of all classes.Let us consider now the method for a determination of the average queue length for calls of a single classc. We will first determine the average number of occupied resources in the buffer zT,cntT,c in state n of the system by calls of class c. By the adoption of the same initial assumptions (30)–(33) that were earlier adopted for the Erlang call stream, (32) can be rewritten in such a way as to include any type traffic T: (40)zT,cn·tT,c=zT,cn-1·tT,c+ΔT,cn.Equation (36) will be also rewritten in our adopted notation to include the dependence between the call stream and the state: (41)ΔT,cn=Qn-tT,cV,UMλT,cn·min⁡tT,c,n-V∑j∈mQn-tT,jV,UMλT,jn·min⁡tT,j,n-V,where λT,c(n) determines the call arrival intensity of new calls of any traffic class c of type T in state n of the system.In the case of Engset traffic, the parameterλEn,j(n) in state n depends on the total number of traffic sources SEn,j and on the number of currently serviced calls in the server xEn,j(n) and the number of calls waiting in the buffer zEn,j(n): (42)λEn,jn=γEn,j·SEn,j-xEn,jn-zEn,jn=λEn,jSEn,j-xEn,jn-zEn,jnSEn,j,where λEn,j is the intensity of the call arrival process for calls of class j, determined with the assumption that all sources are not occupied: (43)λEn,j=γEn,jSEn,j.By approximating the number of occupied resources xEn,jn+zEn,jn in the considered queueing system with nonzero buffer by calls of class j in state n by the average number yEn,jnV+U,0 of occupied resources in state n in the server with zero buffer, Formula (42) can be rewritten as follows: (44)λEn,jn=λEn,jSEn,j-yEn,jnV+U,0SEn,j.Using the analogous simplifying assumptions as for Engset traffic we are in position to determine the intensity of the call arrival process for Pascal calls in state n of the system in the following way: (45)λPa,kn=λPa,kSPa,k+yPa,knV+U,0SPa,k.The call arrival intensities that have been described by (44) for calls of Engset class, and (45) for Pascal class, make it possible to determine, on the basis of (40) and (41), the average number of occupied resources of a queue by calls of individual classes.Independently of the considered call streams, the proposed model can be written in the form of the following method, henceforth called the cFIFO method.cFIFO Method (1)
Determination of occupancy distributions for individual classes:pV+U,01,pV+U,02,…,pV+U,0m in multiservice server with the capacity V+U and with zero buffer. (2)
Determination of nonnormalized aggregated occupancy distributions of all classes, except a classc (c∈M): P•,V+U,0M∖1,P•,V+U,0M∖2,…,P•,V+U,0M∖c-1, P•,V+U,0M∖c,P•,V+U,0M∖c+1,…,P•,V+U,0M∖m. (3)
Determination of the average numberyT,cnV+U,0 of serviced calls in state n (n∈0,V+U) for each class c (c∈M). (4)
Determination, by convolution algorithm, of the occupancy distributionPV+U,0M for multiservice server with the capacity V+U and with zero buffer. (5)
Determination of transformation coefficientsδ(n). (6)
Determination of the occupancy distributionQnV,UM for queueing system with the cFIFO discipline. (7)
Determination of the average queue lengthL and the blocking probability ET,c (c∈M) for calls of individual classes. (8)
Determination of the average numberzT,cntT,c of occupied AUs by calls of class c (c∈M) waiting in the queue in such states n of the system that V<n≤V+U. (9)
Determination of the average numberLT,c of occupied AUs by calls of class c, (c∈M), waiting in the queue.


## 4.1. Convolution Algorithm

Multiservice telecommunications systems can be generally modelled by algorithms that analyze either the dependencies between microstates or macrostates. The one approach is characterized by a large computational complexity [27], whereas the other approach is effective in modelling systems that are offered Poisson call streams. Papers [16, 17] propose convolution algorithms that make it possible to model systems with multiservice traffic on the basis of mutually independent occupancy distributions. These distributions are determined for all call streams offered to the system and can be determined on the basis of appropriate models and theoretical single-service systems. They can also directly result from conducted measurements in real systems or from simulation experiments for a number of selected classes of calls.Let us consider now the operation of a convolution algorithm with a multiservice system that is composed of a server with the capacityV and a buffer with zero capacity (U=0) as an example [28, 29]. In the literature of the subject this system is frequently labelled as the full-availability group (FAG) [30]. Our assumption is that the system is offered a set of MM=m traffic classes of the type T (T∈Er,En,Pa,G) and any randomly chosen traffic class c demands tT,c AUs for service.The input data for the convolution algorithm are the occupancy distributions for single classespV,0T,c, where c∈M. In the adopted notation for the distribution pV,0T,c the first expression in the lower index V defines the capacity of the server, while the second element U defines the capacity of the buffer (in the system under investigation, the buffer with zero capacity U=0 is considered). The distributions pV,0T,c are determined with the assumption that the system with the capacity V is offered only one class of calls. For Erlang, Engset, or Pascal traffic classes, to determine this distribution one can use appropriate theoretical distributions [31]; for example, in the case of class i of Erlang traffic, the distribution for a single class can be determined on the basis of the Erlang distribution:(5)pxvEr,iEr,i=aEr,ix/x!∑l=0vEr,iaEr,il/l!,where x∈0≤x≤vEr,i and aEr,i is the traffic intensity of class i, whereas the parameter vEr,i denotes the maximum number of calls that can be serviced in the server with the capacity V:(6)vEr,i=VtEr,i.In the case of Engset and Pascal traffic, the distributions of single classes can be determined on the basis of the following formulas:(7)pxvEn,jEn,j=SEn,jxγEn,jx∑l=0vjSEn,jlγEn,jl,(8)pxvPa,kPa,k=-SPa,kx-γPa,kx∑l=0vk-SPa,kl-γPa,kl,where the parameters γEn,j and γPa,k define the average intensity of calls offered by a single free Engset and Pascal traffic source. The parameters SEn,j and SPa,k are the total number of Engset and Pascal traffic sources. The relationship between the average traffic offered to the system by Engset traffic stream aEn,j and Pascal traffic stream aPa,k and the parameters γEn,j and γPa,k is as follows:(9)aEn,j=SEn,jγEn,j1+γEn,j,(10)aPa,k=-SPa,k-γPa,k1+-γPa,k.The occupancy distributionpV,0T,c=p0V,0{T,c},p1V,0T,c,p2V,0T,c,…, pnV,0T,c,…,pVV,0T,c of a single class c, determining the occupancy probabilities for all macrostates n (such that n=x·tT,c AUs) in the server with the capacity V, is related to distribution (5) by the following dependence:(11)pnV,0T,c=pxvT,cT,cforn=x·tT,c,0≤x≤vT,c0for  remainingn.In the case of other traffic streams (of the typeG), distributions of single classes can be determined on the basis of measurements taken in real systems or on the basis of relevant simulation experiments.By having the single distributions for all classes offered to the systempV,0T,c at our disposal we can now determine the aggregated distribution P•,0M which is the result of the convolution operation of all distributions for single classes offered to the system: (12)P•,0M=pV,0T,1∗pV,0T,2∗⋯∗pV,0T,m.The distribution P•,0M is not a normalized distribution. After an appropriate normalization process, the normalized distribution PV,0M can be written in the following form: (13)PV,0M=kP0•,0M,kP1•,0M,…,kPV•,0M,where k is the normalization constant: (14)k=1∑n=0VPn•,0M.Let us note that, for example, as a result of the convolution operation of two normalized distributions with the lengthV, a distribution with the length 2V is obtained. From the point of view of the considered system with the capacity of V AUs, all states n>V will never occur. Therefore, such states, in the distribution with the length 2V must be removed and distribution must be normalized. This process is discussed in detail in [16, 17, 19], among others.In (12), the symbol ∗ denotes the convolution operation which is defined in the following way: (15)P•,0A∪B=PV,0A∗PV,0B=P0V,0AP0V,0B,P0V,0AP1V,0B+P1V,0AP0V,0B,…,∑l=0nPlV,0APn-lV,0B,…,∑l=0VPlV,0APV-lV,0B,where the symbol PV,0A denotes the normalized distribution of a single class or the aggregated distribution of a number of classes that belong to a given set A (A∈M), whereas the symbol PV,0B denotes the normalized distribution of a single class or the aggregated normalized distribution of a number of classes that belong to a given set B (B∈M and A∩B=0). The symbol P•,0A∪B defines the aggregated nonnormalized distribution that is the result of a convolution of the distributions from the sets A and B.The convolution operation (15) enables us to determine the average number yT,cnV,0 of serviced calls of class c in the server with the capacity V AUs with zero buffer that is in the occupancy state n AUs. A determination of this parameter should take into consideration the following reasoning [30]. First, the aggregated nonnormalized distributions of all classes, except class c, are to be determined: (16)P•,0M∖c=pV,01∗⋯∗pV,0c-1∗pV,0c+1∗⋯∗pV,0m.Then, on the basis of the distributionsP•,0M∖c and pV,0c the value of the parameter yEr,cnV,0 can be determined, that is, the average number of calls of class c in occupancy state n of the server:(17)yT,cnV,0=∑l=0nlplV,0cPn-l•,0M∖ctT,c∑l=0nplV,0cPn-l•,0M∖c.


## 4.2. Model of the cFIFO Queueing System for Poisson Traffic Streams

Let us consider now the queueing system with the cFIFO service discipline the operation of which is presented in Section3. Our assumption is that this system is offered m Erlang traffic streams for which call arrival intensities of new calls are described by Poisson distributions with the parameters λEr,1,…,λEr,i,…,λEr,m for each traffic class, respectively. Service time is described with exponential distributions with the parameters μEr,1,…,μEr,i,…,μEr,m. Individual call classes demand, respectively, tEr,1,…,tEr,i,…,tEr,m AUs for service. In the case of Erlang traffic, it is assumed that the number of traffic sources is infinite. This means that the call arrival intensity for new call arrivals λEr,i of a given class i is independent of the number of calls of this class that are currently in the system: (18)λEr,in=λEr,ifor0⩽n⩽V+U.The intensity of offered Erlang traffic of class i can be determined on the basis of Formula (1):(19)aEr,i=aEr,in=λEr,iμEr,ifor0⩽n⩽V+U.By expressing the call intensity for a given class i in allocation units per time unit (the product λEr,itEr,i), we can express traffic offered to the system in the following form: (20)AEr,i=aEr,itEr,i.Paper [30] analyzes the dependence between the occupancy distribution in a multiservice full-availability system and the occupancy distribution in a multiservice state-dependent system, with the assumption of identical capacity and traffic offered to both systems. A similar approach will be now applied to the queueing model proposed in the article to determine the dependence between the occupancy distribution PnV+U,0M in the server with zero buffer and the distribution QnV,UM in the considered queueing system: (21)QnV,UM=δnPnV+U,0M,where δn defines the relation between the corresponding probabilities QnV,UM and PnV+U,0M, that is, the probability that the queueing system (V,U) is in state n AUs and the occupancy probability n AUs in the server with zero buffer (V+U,0), with the assumption that traffic offered to both systems is identical. To determine the parameter δ(n) we can use the recurrence dependencies derived for multiservice SD-FIFO queueing systems. The distribution QnV,UM in the cFIFO system is then approximated by distribution (2) that, with (20) taken into consideration, will be rewritten in the following way: (22)QnV,UM=1min⁡n,V∑i=1mAEr,iQn-tEr,iV,UMfor0≤n≤V+U,0otherwise.Assuming, then, that the method for a determination of the occupancy distribution in the queueing system and in the system with zero buffer (when the system is offered Erlang call classes) is known, it is possible to determine the value of the parameterδ(n) by dividing both sides of (22) by the probabilities PnV+U,0M: (23)QnV,UMPnV+U,0M=1min⁡n,V∑i=1mQn-tEr,iV,UMPnV+U,0MAEr,i.Equation (23), with (21) taken into consideration, can be easily transformed into an iterative formula for the parameter δ(n): (24)δn=1min⁡n,V∑i=1mδn-tEr,iPn-tEr,iV+U,0MAEr,iPnV+U,0M.The Markov process in the server with zero buffer to which a mixture of Erlang traffic classes is offered is a reversible process [28, 29]. For the neighboring states Ω(n) and Ωn-ti, because of class i, it is possible then to write local balance equations: (25)AEr,iPn-tEr,iV+U,0M=tEr,iyEr,inV+U,0PnV+U,0M.Now, taking into consideration (25), (24) can be rewritten in the following form: (26)δn=∑i=1mδn-tEr,iyEr,inV+U,0tEr,imin⁡n,V,The convolution operation makes a determination of the occupancy distributionPV+U,0M and the average number of calls of individual classes yEr,inV+U,0 serviced in the server with zero buffer (Formulas (16) and (17)) possible. These results enable us then to assess the value of the parameter δn (Formula (26)) and eventually to evaluate the occupancy distribution in the queueing system QnV,UM on the basis of (21).


## 4.3. Commentary

In Section4.2, to find the general dependence δn between the cFIFO queueing system described by the parameters (V,U) and the system with zero buffer (V+U,0) the occupancy distribution QnV,UM in the SD-FIFO system is used. The possibility of an approximation of the cFIFO system by the SD-FIFO system results from significant similarities in both queue service disciplines involved. In the cFIFO discipline considered in the article only one call can be partly serviced in the server and partly waiting in the queue. The SD-FIFO discipline, in turn, allows even a number of calls to be partly serviced simultaneously. In both instances, however, resources of the server are used maximally and it is just this fact that determines the probability of occupancy distributions for systems with cFIFO and SD-FIFO queues. Figures 4 and 5 show the occupancy distribution QnV,U in a queueing system with the structural parameters V=20 AUs and U=10 AUs, respectively. The occupancy distributions in the SD-FIFO system and the cFIFO system obtained in a simulation were then compared. The systems were offered three Erlang traffic streams with the following demands: tEr,1=1 AU, tEr,2=2 AUs, and tEr,3=3 AUs. Traffic was offered in the following proportions: AEr,1:AEr,2:AEr,3=1:1:1. Figure 4 shows the occupancy distributions for the case of small system loads (a=0.6 Erl/AU) and Figure 5 for large system loads (a=1.2 Erl/AU), where a is the average traffic offered per AU of the system:(27)a=AEr,1+AEr,2+AEr,3V.Figure 4
Occupancy distributions in SD-FIFO and cFIFO queueing systems (a=0.6 Erl/AU).Figure 5
Occupancy distributions in SD-FIFO and cFIFO queueing systems (a=1.2 Erl/AU).The simulation results are shown with 95% confidence interval determined on the basis of the Student distribution for 5 series, 100,000 calls each. The results for the presented comparison indicate a very good convergence of occupancy distributions in the SD-FIFO and cFIFO queueing systems. The simulation experiments for other systems differentiated by their capacity, number, and demands of offered traffic classes conducted by the authors earlier confirm strong convergence of occupancy distributions of both queueing systems.It should be stressed that queueing characteristics (such as the average number of calls of particular classes in the queue in corresponding occupancy states of the system) are not characterized by just as good convergence as the occupancy distributions. This would be the first reason why the SD-FIFO model cannot be directly applied to determine queueing characteristics for the cFIFO system. The other reason is the fact that to determine the parameterδ(n) (Formula (26)) the occupancy distribution of the SD-FIFO queueing system, derived for Erlang traffic, is used. In the case of other traffic streams, we do not observe such a good convergence between distributions for the SD-FIFO and cFIFO systems any longer. However, Formula (26) turns out to be very universal and versatile and approximates cFIFO queueing systems that service traffic with any, mutually independent, call streams very well. Appropriate numerical examples are presented in Section 5.


## 4.4. Characteristics of cFIFO System with Erlang Traffic

By having the knowledge of the coefficientsδ(n) at hand we are in position to determine the occupancy distribution QV,UM in a queueing system with the cFIFO discipline. This distribution can also provide a basis for a determination of appropriate QoS parameters, such as the blocking probability Ei and the average number of occupied AUs in queue L. The phenomenon of blocking for calls of class i in the queueing system occurs when the queue lacks tEr,i free AUs to store a new call of class i. Therefore, (28)EEr,i=∑n=V+U-tEr,i+1V+UQnV,UM.The average queue length L (for calls of all classes) is a mean value for the resources (expressed in AUs) occupied by calls of all classes that are waiting in the queue:(29)L=∑n=1UnQV+nU,VM.Let us consider now a method for a determination of the average numberLEr,i of busy AUs in a queue occupied by calls of class i. This article proposes an approximate determination of this parameter on the basis of the following reasoning. First, it is the average number of LEr,i AUs occupied by calls of class i that are waiting in the queue that has to be determined: (30)LEr,i=∑n=V+1V+UzEr,intEr,iQnU,VM,where zEr,i(n) is the average number of calls of class i waiting in the queue in state n of the system. The product zEr,i(n)tEr,i is the average number of AUs occupied in the buffer by waiting calls of class i in state n. In states n such that n≤V, the queue is empty; therefore the product zEr,i(n)tEr,i is equal to zero.In statesn such that n>V, the total number of occupied AUs in the queue (by calls of all classes) can be determined as follows: (31)∑i∈MzEr,intEr,i=n-V.Between the neighboring states n-1 and n there is a difference in the number of busy AUs occupied by calls of class i waiting in the queue, which, in the article, is denoted by the symbol ΔEr,cn. We can thus write (32)zEr,in·tEr,i=zEr,in-1·tEr,i+ΔEr,in,where (33)∑i∈MΔEr,in=1.Let us assume that the parameter ΔEr,i(n) is proportional to the intensity in which the buffer is occupied by calls of a given class i. We can therefore determine the value of the parameter ΔEr,i(n) in the following way: (34)ΔEr,in=Qn-tEr,iV,UMλEr,iφEr,in-tEr,i∑j∈MQn-tEr,jV,UMλEr,jφEr,jn-tEr,j,where (35)φEr,in-tEr,i=tEr,iforn-tEr,i≥V,n-VforV-tEr,i<n-tEr,i<V.Equation (35) is the result of a particular service discipline in the cFIFO queue. If in system state n-tEr,i a new call of class i arrives, then in the occupancy states of the server that are determined by the condition V-tEr,i<n-tEr,i<V a number of AUs of the considered call of class i will be immediately serviced by the server, while the remaining part will be directed to the queue. If n-tEr,i>V, then all AUs of a new call of class i will be immediately placed in the queue. Equations (34) and (35) can be written as just one equation in the following way: (36)ΔEr,in=Qn-tEr,iV,UMλEr,i·min⁡tEr,i,n-V∑j∈mQn-tEr,jV,QMλEr,j·min⁡tEr,j,n-V.Ultimately, (32), taking into account (36), can be written as follows: (37)zEr,intEr,i=zEr,in-1tEr,i+Qn-tcV,UMλEr,i·min⁡tEr,i,n-V∑j∈mQn-tEr,jV,UMλEr,j·min⁡tEr,j,n-V,where n>V. A determination of all values zEr,i(n) will make it possible, on the basis of (30), to evaluate and assess all queue lengths for calls of individual classes.


## 4.5. Model of a Queueing System with cFIFO Discipline and State-Dependent Call Streams

To determine the occupancy distribution in a queueing system with the cFIFO queueing discipline and offered BPP traffic (or traffic with any distribution of the call stream) we will use the general recurrence dependencies derived for a system with Erlang traffic (Section4.4). To determine the occupancy distribution in the cFIFO queueing system with BPP traffic we use then dependencies (21) and (25) that, in their generalized form, can be rewritten as follows: (38)QnV,UM=δnPnV+U,0M,(39)δn=∑c=1mδn-tT,cyT,cnV+U,0tT,cmin⁡n,V,where the parameter yT,cnV+U,0 is determined on the basis of a convolution operation (Formulas (16) and (17)). The occupancy distribution for the server with zero buffer PnV+U,0M in Formula (38) is determined on the basis of a convolution algorithm for which the input data are the distributions of single classes, determined for Erlang traffic by Formula (5) and for Engset and Pascal traffic by Formulas (7) and (9) as well as (8) and (10), respectively.It should be emphasized that the application of the convolution algorithm in the proposed model makes it possible to determine characteristics of queueing systems for call streams other than BPP streams. Distributions of single classes that are the input data for the convolution algorithm can be then determined empirically on the basis of measurements or by simulation experiments.On the basis of the occupancy distributionQV,UM, according to (28) and (29), it is possible to determine the blocking probability and the average queue length for calls of all classes.Let us consider now the method for a determination of the average queue length for calls of a single classc. We will first determine the average number of occupied resources in the buffer zT,cntT,c in state n of the system by calls of class c. By the adoption of the same initial assumptions (30)–(33) that were earlier adopted for the Erlang call stream, (32) can be rewritten in such a way as to include any type traffic T: (40)zT,cn·tT,c=zT,cn-1·tT,c+ΔT,cn.Equation (36) will be also rewritten in our adopted notation to include the dependence between the call stream and the state: (41)ΔT,cn=Qn-tT,cV,UMλT,cn·min⁡tT,c,n-V∑j∈mQn-tT,jV,UMλT,jn·min⁡tT,j,n-V,where λT,c(n) determines the call arrival intensity of new calls of any traffic class c of type T in state n of the system.In the case of Engset traffic, the parameterλEn,j(n) in state n depends on the total number of traffic sources SEn,j and on the number of currently serviced calls in the server xEn,j(n) and the number of calls waiting in the buffer zEn,j(n): (42)λEn,jn=γEn,j·SEn,j-xEn,jn-zEn,jn=λEn,jSEn,j-xEn,jn-zEn,jnSEn,j,where λEn,j is the intensity of the call arrival process for calls of class j, determined with the assumption that all sources are not occupied: (43)λEn,j=γEn,jSEn,j.By approximating the number of occupied resources xEn,jn+zEn,jn in the considered queueing system with nonzero buffer by calls of class j in state n by the average number yEn,jnV+U,0 of occupied resources in state n in the server with zero buffer, Formula (42) can be rewritten as follows: (44)λEn,jn=λEn,jSEn,j-yEn,jnV+U,0SEn,j.Using the analogous simplifying assumptions as for Engset traffic we are in position to determine the intensity of the call arrival process for Pascal calls in state n of the system in the following way: (45)λPa,kn=λPa,kSPa,k+yPa,knV+U,0SPa,k.The call arrival intensities that have been described by (44) for calls of Engset class, and (45) for Pascal class, make it possible to determine, on the basis of (40) and (41), the average number of occupied resources of a queue by calls of individual classes.Independently of the considered call streams, the proposed model can be written in the form of the following method, henceforth called the cFIFO method.cFIFO Method (1)
Determination of occupancy distributions for individual classes:pV+U,01,pV+U,02,…,pV+U,0m in multiservice server with the capacity V+U and with zero buffer. (2)
Determination of nonnormalized aggregated occupancy distributions of all classes, except a classc (c∈M): P•,V+U,0M∖1,P•,V+U,0M∖2,…,P•,V+U,0M∖c-1, P•,V+U,0M∖c,P•,V+U,0M∖c+1,…,P•,V+U,0M∖m. (3)
Determination of the average numberyT,cnV+U,0 of serviced calls in state n (n∈0,V+U) for each class c (c∈M). (4)
Determination, by convolution algorithm, of the occupancy distributionPV+U,0M for multiservice server with the capacity V+U and with zero buffer. (5)
Determination of transformation coefficientsδ(n). (6)
Determination of the occupancy distributionQnV,UM for queueing system with the cFIFO discipline. (7)
Determination of the average queue lengthL and the blocking probability ET,c (c∈M) for calls of individual classes. (8)
Determination of the average numberzT,cntT,c of occupied AUs by calls of class c (c∈M) waiting in the queue in such states n of the system that V<n≤V+U. (9)
Determination of the average numberLT,c of occupied AUs by calls of class c, (c∈M), waiting in the queue.


## 5. Numerical Results

In order to verify the proposed analytical method the results of the calculations were compared with the results provided by the simulation experiments. For this purpose, a dedicated simulation program for a cFIFO queueing system evaluation was developed. The simulator uses an experiment with steady system time in which the process interaction method is used. The classes with finite number of sources were implemented according to the principles described in [32]. The program was written in the C++ language in the Qt environment. The software architecture and process interaction method is described in [33]. The obtained results are presented in graphs as the function of traffic offered to one AU in the server: (46)a=∑c=1mAT,cV.Each simulation experiment to determine the characteristics of the system under investigation for particular valuesa involved 10 series. The prerequisite condition for a single series to be completed was call service for 10,000,000 calls or a loss of 10,000 calls. The adopted length of a single series in the simulation made it possible to determine confidence intervals at the 95% level. The results obtained on the basis of the analytical model are shown in the graphs with lines, whereas the results of the simulation are presented with appropriate symbols. In most cases, the values for the confidence intervals in the graphs are so small that they do not exceed the value of the symbol that denotes the result of a simulation. The proportions of offered traffic in all presented cases were AT,1:AT,2:AT,3=1:1:1. For each of the considered queueing systems, the results for the blocking probability and the average queue lengths for individual classes, expressed in the number of occupied AUs, will be presented.Figures6–8 show the results for three queueing systems that service Erlang traffic. The assumption in the systems presented in Figures 6 and 7 was that the intensities of service streams of particular call classes were, respectively, equal to μEr,1=1, μEr,2=1, μEr,3=1, whereas in the case of the results shown in Figure 8 they were, respectively, μEr,1=1, μEr,2=2, μEr,3=3.Figure 6
The blocking probability and the average queue length (V=20, U=50, m=3, tEr,1=1, tEr,2=2, tEr,3=3).Figure 7
The blocking probability and the average queue length (V=20, U=10, m=3, tEr,1=1, tEr,2=2, tEr,3=3).Figure 8
The blocking probability and the average queue length (V=20, U=10, m=3, tEr,1=1, tEr,2=2, tEr,3=3).The next stage in the process of verification of the proposed analytical model was to test its accuracy for systems to which a mixture of Erlang, Engset, and Pascal traffic was offered (Figure9). In this case, the intensities of service streams of particular call classes were, respectively, equal to μEn,1=1, μPa,2=1, μEr,3=1. The number of traffic sources for Engset and Pascal classes is equal to SEn,1=30, SPa,2=20, respectively.Figure 9
The blocking probability and the average queue length (V=20, U=10, m=3, tEn,1=1, tPa,2=2, tEr,3=3, μEn,1=1, μPa,2=1, μEr,3=1, SEn,1=30, SPa,2=20).In the first case of considered types of non-Poissonian offered traffic (denoted by symbol NE), each call stream is described by normal distributionN(meanc,varc) and each service stream is described by exponential distribution. It is assumed that the mean value meanc is equal to the inverse of offered traffic intensity of a given call class (aN,c-1) and variance is equal to meanc2. So, we consider the system with normally distributed call stream N(aN,c-1,aN,c-2). The intensities of service streams are equal to μN,1=μN,2=μN,3=1 (similar to previously considered queueing systems). The results for this queueing system are presented on Figure 10.Figure 10
The blocking probability and the average queue length (V=20, U=10, m=3, tNE,1=1, tNE,2=2, tNE,3=3).Figure11 shows the results for a queueing system that, for each serviced traffic class, the call stream and service stream are described by normal distribution. This type of traffic is denoted by symbol NN. Similar to previous case, each call stream is described by the distribution N(aNN,c-1,aNN,c-2). Each service stream is given by the distribution N(μNN,c-1,μNN,c-2), where in the experiment was admitted μNN,1=μNN,2=μNN,3=1.Figure 11
The blocking probability and the average queue length (V=20, U=10, m=3, tNN,1=1, tNN,2=2, tNN,3=3).The results presented on Figure12 were worked out for queueing system in which call streams are described by uniform distribution unifmin⁡,max⁡ and service streams are described by exponential distribution. This type of traffic is denoted by symbol UE. It is assumed that for each traffic class the uniform distribution is given by parameters min⁡=0 and max⁡=2aUE,c-1 (where aUE,c is the traffic intensity of class c). The intensities of service streams are equal to μUE,1=1, μUE,2=1, μUE,3=1.Figure 12
The blocking probability and the average queue length (V=20, U=10, m=3, tUE,1=1, tUE,2=2, tUE,3=3).The results of the study showed in Figures6–12 confirm high accuracy of the proposed approximate analytical model of the queueing system with the cFIFO discipline. The diversified accuracy of the results stems from the dependence between the method for a determination of the average number of calls for individual classes in the system adopted in the study (independently for the server and queue) and the type of offered traffic. More accurate results were obtained for BPP streams, while those for non-Poisson streams were less accurate. This results from the adoption of the method of the approximation of the distribution in the system with the cFIFO discipline by the distribution in the SD-FIFO system that can be only precisely determined for Poisson streams. During the study no dependence between the accuracy of the model and the number of offered classes of calls and their demands was observed.


## 6. Conclusions

This article proposes an approximate analytical model of a queueing system that services multiservice traffic with the cFIFO queueing discipline. The model is based on a convolution algorithm in which to determine certain characteristics, such as the average number of serviced calls, the formulas derived on the basis of accurate Markovian models for multiservice systems with zero and nonzero buffer (with the SD-FIFO service discipline for the queue) are used. The introduction of these assumptions makes it possible to construct a general model of a multiservice queueing system with the cFIFO discipline. The proposed model is characterized by high accuracy, which makes an analysis of cFIFO systems for call streams with any, mutually independent, probabilistic distributions possible. This high accuracy stems from the fact that any errors that may possibly result from the adopted approach will be minimized by the convolution operation.



---

*Source: 2185714-2016-11-29.xml*