# On Two-Level State-Dependent Routing Polling Systems with Mixed Service

Authors: Guan Zheng; Yang Zhijun; Qian Wenhua; He Min
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Based on priority differentiation and efficiency of the system, we consider anN+1 queues’ single-server two-level polling system which consists of one key queue and N normal queues. The novel contribution of the present paper is that we consider that the server just polls active queues with customers waiting in the queue. Furthermore, key queue is served with exhaustive service and normal queues are served with 1-limited service in a parallel scheduling. For this model, we derive an expression for the probability generating function of the joint queue length distribution at polling epochs. Based on these results, we derive the explicit closed-form expressions for the mean waiting time. Numerical examples demonstrate that theoretical and simulation results are identical and the new system is efficient both at key queue and normal queues.


---

## Body

## 1. Introduction

In this paper, we study a class ofN+1 queues’ polling systems that consists of one key queue, Qh, and N normal queues, Q1,Q2,…,QN, which are attended by a single server. Studies on the polling systems have attracted extensive attentions in the last years due to their vast area of applications in communication network, production, and transportation. Excellent surveys on polling systems analysis and their applications may be found in [1–4]. However, many studies in the literatures assume that the server visit the queues in a fixed, cyclic order. This might not be a realistic assumption, as queues might have different priority level; queues with high priority should be visit more frequently than the lower ones; sometime queues might be empty and then there is no need to visit. As such, we study the case where the server just visits active queues with customers. Note that as a consequence, after skipping the empty queues, server could provide more visit opportunity to active queues with customers. Furthermore, parallel process of service period and switch-over period allows a successive service between two active queues without the duration of switch-over time. To provide priority differentiation service, queues are separated as one key queue and N normal queues. Two-level route order and mixed service scheme are used to provide high priority to key queue.It is observed that in the wide body of literature on polling system hardly can any studies be found that take the consideration of queue state-dependent routing and service priority simultaneously. The reason for this may lie in the fact that the analysis of state-dependent routing polling model is much more complex than that of cyclic polling model, especially in priority differentiated model. In particular, waiting time and queue length analysis of two-level priorities polling systems can be found in [5–7], in which the server visits queues in a two-level route; that is, the server polls key queue with exhaustive scheme after each gated service to normal queue [5]. This work is extended in [6] with assigning 1-limited service discipline to normal queues. More recently, Yang et al. set the exhaustive service for normal queue and gated service for key queue to ensure fairness but just acquire the first moment performance of the system as mean queue length at the polling epoch and the mean cyclic time [7]. The parallel discipline is used to improve the delay performance in [8], in which when the current polling queue has customers in storage the server will process service while switching to the successive queue simultaneously and begins to serve the successor once it finishes the service of the current one. This scheme could improve polling efficiency in high traffic cases. However, the parallel mechanism will be invalid when there is no customer in the queue. In low traffic cases, useless polling to idle queue becomes an obvious liability in cyclic polling model. Routing depends on the event whether a queue is empty or it is not helpful to this problem [9]. In this paper, we consider the special setting to a two-level mixed service polling model, where the key queue is served exhaustively while normal queues are served in 1-limited mechanism. Furthermore, the server no longer checks all the stations in a fixed order; only active stations with transfer requirements could be served and then the switch-over period and service period are processed paralleled. This mechanism increases the system utilization and reduces the mean waiting time.Although the exhaustive service discipline in principle fits the branching property, the present model involves 1-limited service discipline, which does not satisfy the above-mentioned branching property. The explicit analysis of nonbranching service disciplines is mostly in special setting, such as [10, 11] studied on two-queue polling systems and [12] studied on symmetric 1-limited model. In this paper, we follow the special setting in [8] and analyze the mean waiting time of the present model under the assumption on the symmetrical characteristic among normal queues, as will be described in greater detail in Section 2.Initially, we follow an approach similar to the analysis of [5], which uses a recursive iteration of a functional equation, for the probability generating function (PGF) of the joint queue-length distribution at moments the server starts a visit period.The main contributions of this paper can be summarized as follows. Firstly, we extend the parallel two-level poling system in [8] by using queue state-dependent routing, in which only active queues with customers could be visited by server. This scheme is helpful to avoid the consumptions induced by idle visit. Secondly, under the assumption of a stable system, we obtain the explicit expressions for the PGF for the joint queue length distribution at polling epochs as a starting point of key queue and normal queue separately. Thirdly, we achieve the exact closed-form expression of the mean waiting time under the assumption on the symmetrical characteristic of normal queue.The rest of the paper is structured as follows. In Section2, we give a formal description of the polling model that we study and we introduce the necessary notation. Based on this, in Section 3, we derive the expressions for the mean waiting time of the present model under the assumption of a semisymmetric (symmetrical characteristic of normal queue) stable system, by taking a functional equation for the PGF for the joint queue length distribution at polling epochs as a starting point. In Section 4, numerical results obtained with the proposed analytical models are shown and their very good agreement with realistic simulation results is discussed. Finally, concluding remarks and directions for future research are given in the end.


## 2. Model Description

Consider a discrete time (timeline is divided into time slot) polling system consisting ofN (N≥2) infinite-buffer queues Q1,Q2,…,QN, and Qh. The single server visits active queues in a two-level state-dependent routing order and serves the customers with mixed service discipline.In the arrival process, type-j (j=1,2,…,N,h) customers arrive at Qj according to an independent Poisson arrival process. The generating function of arrival process in queue j is Aj(zj), with the variance of σλj2=Aj′′1+λj-λj2 and the arrival rate of λj=Aj′1. The total arrival rate is ∑i=1Nλi+λh.In theservice process, we assume that customers in queue j (j=1,2,…,N,h) receive individual service. The service time of a customer at each queue is independent of each other. Their generating function is Bj(zj), with the variance of σβj2=Bj′′1+βj-βj2 and the mean value βj=Bj′1. We propose a two-level server routing make the high priority queue be visited more frequently than others and add mix-service discipline to ensure the high priority of Qh. The load offered to Qj is ρj=λjβj, and the total offered load is equal to ∑i=1Nρi+ρh.State-Dependent Routing. Queues are partitioned as active queue and idle queue by their buffer condition. Only active queues with customers waiting in the buffer could be visited by the server in order. Idle queue with empty buffer would be skipped in the current polling round.Two-Level Polling. The server visits queues governed by a two-level routing. In the first polling level, the server polls between the high priority queue Qh and an active normal queue; in the second level, for each time after the exhaustive service at Qh, one normal active queue is visited in a cyclic order; that is, the server routing in this model is 1→h→⋯→i→h→i+1→⋯→h→N.In theswitch-over process, a parallel mechanism is used. When the server polls an active queue at time with customers in its buffer, the server will provide service and inquire the next active queue simultaneously and then switch to serve the successor immediately without the switch-over time once it has finished the current service. Combined with the state-dependent routing scheme, over the course of a visit period, the server serves the active queues and normal queue in sequence continuously until the entire system is empty; there will be no consumption of switch-over time anymore in the present model. More especially, we assume the server consume one time slot to confirm the system state when the system is entirely empty.Mix-Service Discipline. Exhaustive discipline is specified for the key queue and 1-limited discipline for normal queues, so that the entire customers in the key queue could be served in the present server round, while those who are in normal queues might need several rounds when there are more than one customer in the buffer. Let Fh denote the duration of a service period for the customers arrive during arbitrary time slot in Qh. This service period consists of the services of its ancestral customers arriving during the exact slot and the services of the offspring line of the ancestral customers [13]. The generating function of Fh is denoted by Fh(zh)=E[zhFh]. Such a functional equation has already been derived in [14] as Fh(zh)=Ah(Bh(zhF(zh))).In the remainder of this paper, we are interested in the queue length distributions at the polling epoch ofQi and Qh. Let ξj(n) denote the number of customers present at Qj at tn when the server starts a visit period at Qi, and let ξj(n∗) denote the number of customers present at Qj at tn∗ when the server starts a visit period at Qh successively with the service of Qi. The joint distribution of ξj(n+1) and ξj(n∗) is represented by the N-dimensional PGF Gi+1(z1,…,zN,zh) and Gih(z1,…,zN,zh).We analyze the system under stability conditions (∑i=1Nρi+ρh<1) [12]. Normal queues in the present model are served in a 1-limited manner, which does not satisfy the well-known branching property in polling systems. Therefore, more specifically, in the analyses of mean waiting time, we assume the normal queues are symmetric; that is, normal queues have the same customer arrival rate and service rate.


## 3. Analysis for Steady-State Systems

In this section, we derive explicit expression for the joint queue length distribution. In Section3.1, we first obtain expressions for Gi+1(z1,…,zN,zh) and Gih(z1,…,zN,zh), the joint queue length PGF at the polling epoch at Qi+1 and Qh. These results ultimately lead in Section 3.2 to the first and second moment of the PGF, and obtain the expressions for E[Wi] and E[Wh], the mean waiting time of type-i and type-h customers that arrive at an arbitrary point in time.


### 3.1. Joint Queue Length Distribution at Polling Epoch

Assuming that the server begin the service ofQi at tn, define a random variable ξj(n) as the number of type-j (j=1,2,…,N,h) customers at time tn. Then the status of the entire polling model at time tn can be represented as {ξ1(n),…,ξN(n),ξh(n)}. Denote ξj(n+k) as the number of type-j customers at tn+k, the polling epoch of Qi+k. The status of the entire polling model at time tn+k can be represented as {ξ1(n+k),…,ξN(n+k),ξh(n+k)} while ξi(n∗) is the number of type-j customers in at time tn∗, at which the server begins providing service to Qh and the status of the entire polling model at time tn∗ can be represented as {ξ1(n∗),…,ξN(n∗),ξh(n∗)}. Under the necessary and sufficient condition for the stability of the system ∑i=1Nρi+ρh<1, the probability distribution is defined as(1)limn→∞⁡Pξjn=xj;j=1,…,N,h=πix1,…,xN,xh,limn→∞⁡pξjn∗=yj;j=1,…,N,h=πihy1,…,yN,yh.The generating functions at tn and tn∗ are(2)Giz1,…,zN,zh=∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zNxnzhxhπix1,…,xN,xhi=1,2,…,N,Gihz1,…,zN,zh=∑y1=0∞⋯∑yN=0∞∑yh=0∞z1y1⋯zNynzhyhπihy1,…,yN,yhi=1,2,…,N.According to the proposed mechanism, the system variables have the following equations. When the server begins the service onQi+1 at tn+1, we have(3)ξjn+1=ξjn∗+ηjνhj≠h0j=h.vj(n) is the service time in Qj and ηk(vj) is the number of arrivals to Qk during vj(n).The server just finishes the service ofQh in an exhaustive manner and starts the polling on Qi+1 at tn+1. Such a functional equation of exhaustive service has already been derived in [12]. Applying these results to our case, we obtain(4)Gi+1z1,z2,…,zN,zh=limn→∞⁡E∏j=1Nzjξin+1zhξhn+1=Gihz1,z2,…,zN,Bh∏j=1NAjzjFh∏j=1NAjzj.The expression can be interpreted as follows. At the start of the visit period atQi+1, type-i customers are those at the polling epoch of Qh plus the new customers arriving at each queue during the service period of the Qh in exhaustive scheme, and no type-h customer resumes at that moment.When the server begins the service onQh at tn∗, we have(5)ξjn∗=ξjn+ηjνi,j≠i≠h,ξin+ηiνi-1,j=iξin≠0,ηjνi,j=h,ξjn∗=ξjn,j≠i≠h,0,j=iξin=0,0,j=hνj(n) is the service time in Qj, and ηk(νj) is the number of arrivals to Qk during νj(n).In our case, for normal queues, the server just polls the active queues with customers in parallel 1-limited manner. To gain more insight in the state-dependent service discipline, letPi denote the queue length at the service epoch in an M/G/1 queue with the same arrival process and service-time distribution as Qi. We assume that the k customers have waited in Qi at the start of the busy period with probability pk∈[0,1), ∑k=0∞pk=1. Then we can acquire the queue length generating function at the service epoch as Pizi=Aizi∑k=0∞pkzik, where Ai(zi) is the PGF of the arrival process as defined in Section 2. Specifically, the server does not provide service when the queue length is zero, so we assume that k∗ customers resumed after the end of the busy time in 1-limited service with the probability of pk∗∈[0,1), and pk∗=pk+1 for k=0,1,…. Consequently, the probability space could be rebuilt as(6)Pi∗zi=BiAiziAizip0+∑k=0∞pk∗zik=BiAizi∑k=0∞pkzik-p0zi0zi+p0zi0.With the definition ofPi(zi), we have(7)Pi∗zi=BiAiziPizi-Pizizi=0zi+Pizizi=0.Applying these results to our case, we obtain(8)Gihz1,…,zN,zh=limn→∞⁡E∏j=1Nzjξin∗zhξhn∗=1ziBi∏j=1NAjzjAhzhGiz1,…,zN,zh-Giz1,…,zN,zhzi=0+Giz1,…,zN,zhzi=0-Giz1,…,zN,zhz1,…,zN,zh=0+∏j=1NAjzjAhzhGiz1,…,zN,zhz1,…,zN,zh=0.The expression can be interpreted as follows. At the start of the visit period atQh, in the case that the former Qi is active, one type-i customer would have been served at tn∗ and new customers arrived at each queue during the service period of the exact type-i customer. The server would skip Qi to Qi+1 when Qi is empty; in that case, the distribution of the number of customers in the systems is represented by the generating function Giz1,…,zi,…,zN-1,zhzi=0, with the exception as the system is entirely empty, which is represented by the generating function Giz1,…,zi,…,zN-1,zhz1,…,zN-1,zh=0. When the system is entirely empty, the server will stop providing service for one time slot until new customers arrive during this time slot, and this number of customers is represented by the last partition of the addition formula.


### 3.2. Expression for the Mean Waiting Time

Now we have derived expressions for the PGFGi+1z1,…,zi,…,zN,zh and Gihz1,…,zi,…,zN,zh pertaining to the queue length at polling epoch of Qi+1 and Qh, we use these results to obtain E[Wi], the mean waiting time of type-i normal customers, and E[Wh], the mean waiting time of type-h high priority customers.


#### 3.2.1. The First and Second Moment ofGi+1z1,…,zi,…,zN,zh and Gihz1,…,zi,…,zN,zh

To start the analysis of mean waiting time of type-j customers, we need to calculate the generating functions and its derivation at the point z=1, z is the abbreviation of the (1×N+1) vector of (z1,…,zi,…,zN,zh), and 1 is the (1×N+1) vector with 1.G
i
+
1
(
z
) is the PGF of the joint queue length at the polling epoch of Qi, so we have(9)Giz1,…,zi,…,zN,zh=∑x1=0∞⋯∑xi=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zixi⋯zNxnzhxhPξ1n=x1,…,ξin=xi,…,ξNn=xN,ξhn=xh=∑x1=0∞⋯∑xi=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zixi⋯zNxnzhxhPξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=xiPξin=xi.Taking thekth derivative with respect to zi yields(10)∂kGiz1,z2,…,zi,…,zN,zh∂zik=∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zixi-k⋯zNxNzhxhxi!xi-k!Pξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=xiPξin=xi.Settingzi=0 yields(11)∂kGiz1,z2,…,zi,…,zN,zh∂zikzi=0=∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯1⋯zNxNzhxhk!Pξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=kPξin=k=k!Pξin=k∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯1⋯zNxNzhxhPξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=k=k!Pξin=kEz1ξ1n⋯1⋯zNξNnzhξhn∣ξin=k.Rearranging terms and setting k=0, we have(12)Giz1,z2,…,zi,…,zN,zhzi=0=Pξin=0Ez1ξ1n⋯1⋯zNξNnzhξhn∣ξin=0,Gi1i=Pξin=0.Extending this result we have(13)Gi0=Pξ1n=0,…,ξin=0,…,ξNn=0,ξhn=0.0 is the (1×N+1) vector with 0, and 1j is the (1×N+1) vector with 0 in jth position and 1 in all other entries.Define the first derivative ofGi(z) and Gih(z) at z=1 as (14)gij=limz1,…,zi,…,zN,zh→1⁡∂Giz∂zj,gihj=limz1,…,zi,…,zN,zh→1⁡∂Gihz∂zj,j,k=1,2,…,N,h.(15)gihj=βiλj1-Gi1i+gij+λjGi0(16)gihi=βiλi-11-Gi1i+gii+λiGi0(17)gihh=βiλh1-Gi1i+λhGi0(18)gi+1i=gihi+gihhβhλi1+Fh′1(19)gi+1j=gihj+gihhβhλj1+Fh′1.Calculate ∑j=1Ngj+1k yields(20)1-Gi1i=NλiGi01-ρh-Nρ.Define the second derivative of Gi(z) and Gih(z) at z=1 as(21)gij,k=limz1,…,zi,…,zN,zh→1⁡∂2Giz∂zj∂zkgi0j,k=limz1,…,zi-1,zi+1,…,zN,zh→1⁡∂2Gizzi=0∂zj∂zkgi00j,k=limz1,…,zN,zh→0⁡∂2Gizz1,…,zN,zh=0∂zj∂zkgihj,k=limz1,…,zN,zh→1⁡∂2Gihz∂zj∂zki=1,2,…,Nj,k=1,2,…,N,h.Substitute (4) and (8) into the above second derivative formulas.We assume theN normal queues are symmetrical; that is, λi=λ, βi=β, i=1,2,…,N. Then simplifying these we get the second derivative of Gi(z) and Gih(z) at z=1 as follows:(22)gihh,h=B′′1λh21-Gi1i+βAh′′11-Gi1i+Ah′′1Gi0.(23)gii=1-Gi1i211-ρh-Nρ1-ρhρhA′′1λ1-ρh2+Ah′′βh2+λhBh′′+NB′′1λ2+NβA′′1+λ1-ρh+λhλBh′′11-ρh-Nρ+1-Gi1i.Remark 1.
Thoughgi(i) is the first derivative at z=1Gi(z) in definition, it is clear that it contains the second moment parameter as Aj′′(1) and Bj′′(1). So, gi(i) is a second moment parameter for the system performance.


#### 3.2.2. Analysis ofE[Wh] and E[Wi]

DefineWh and Wi as the waiting time of type-h and type-i customers, which denotes the time from the epoch when a customer arrives at the queue to the time it is served. In the present model, high priority type-h customers are served in the exhaustive service and normal type-i customers are served in 1-limited service. Based on the related research works in [14], the mean waiting time of type-h customers E[Wh] and the type-i customers E[Wi] can be calculated as follows:(24)EWh=gihh,h2λhgihh-Ah′′12λh21+ρh+λhBh′′121-ρh,(25)EWi=1λ1-Gi1igii-1λ-A′′12λ2.Taking (17), (22) in (24) in the above expressions, we have(26)EWh=121-ρh1-ρh+NλB′′1+λhBh′′1-12λh21+ρhAh′′1.Taking (17), (22), and (23) in (25) in the above expressions, we have(27)EWi=12λ11-ρh-Nρ1-ρhρhA′′1λi1-ρh2+Ah′′βh2+λhBh′′+NB′′1λ2+NβA′′1+λ1-ρh+λhλBh′′11-ρh-Nρ-A′′12λ2.


## 3.1. Joint Queue Length Distribution at Polling Epoch

Assuming that the server begin the service ofQi at tn, define a random variable ξj(n) as the number of type-j (j=1,2,…,N,h) customers at time tn. Then the status of the entire polling model at time tn can be represented as {ξ1(n),…,ξN(n),ξh(n)}. Denote ξj(n+k) as the number of type-j customers at tn+k, the polling epoch of Qi+k. The status of the entire polling model at time tn+k can be represented as {ξ1(n+k),…,ξN(n+k),ξh(n+k)} while ξi(n∗) is the number of type-j customers in at time tn∗, at which the server begins providing service to Qh and the status of the entire polling model at time tn∗ can be represented as {ξ1(n∗),…,ξN(n∗),ξh(n∗)}. Under the necessary and sufficient condition for the stability of the system ∑i=1Nρi+ρh<1, the probability distribution is defined as(1)limn→∞⁡Pξjn=xj;j=1,…,N,h=πix1,…,xN,xh,limn→∞⁡pξjn∗=yj;j=1,…,N,h=πihy1,…,yN,yh.The generating functions at tn and tn∗ are(2)Giz1,…,zN,zh=∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zNxnzhxhπix1,…,xN,xhi=1,2,…,N,Gihz1,…,zN,zh=∑y1=0∞⋯∑yN=0∞∑yh=0∞z1y1⋯zNynzhyhπihy1,…,yN,yhi=1,2,…,N.According to the proposed mechanism, the system variables have the following equations. When the server begins the service onQi+1 at tn+1, we have(3)ξjn+1=ξjn∗+ηjνhj≠h0j=h.vj(n) is the service time in Qj and ηk(vj) is the number of arrivals to Qk during vj(n).The server just finishes the service ofQh in an exhaustive manner and starts the polling on Qi+1 at tn+1. Such a functional equation of exhaustive service has already been derived in [12]. Applying these results to our case, we obtain(4)Gi+1z1,z2,…,zN,zh=limn→∞⁡E∏j=1Nzjξin+1zhξhn+1=Gihz1,z2,…,zN,Bh∏j=1NAjzjFh∏j=1NAjzj.The expression can be interpreted as follows. At the start of the visit period atQi+1, type-i customers are those at the polling epoch of Qh plus the new customers arriving at each queue during the service period of the Qh in exhaustive scheme, and no type-h customer resumes at that moment.When the server begins the service onQh at tn∗, we have(5)ξjn∗=ξjn+ηjνi,j≠i≠h,ξin+ηiνi-1,j=iξin≠0,ηjνi,j=h,ξjn∗=ξjn,j≠i≠h,0,j=iξin=0,0,j=hνj(n) is the service time in Qj, and ηk(νj) is the number of arrivals to Qk during νj(n).In our case, for normal queues, the server just polls the active queues with customers in parallel 1-limited manner. To gain more insight in the state-dependent service discipline, letPi denote the queue length at the service epoch in an M/G/1 queue with the same arrival process and service-time distribution as Qi. We assume that the k customers have waited in Qi at the start of the busy period with probability pk∈[0,1), ∑k=0∞pk=1. Then we can acquire the queue length generating function at the service epoch as Pizi=Aizi∑k=0∞pkzik, where Ai(zi) is the PGF of the arrival process as defined in Section 2. Specifically, the server does not provide service when the queue length is zero, so we assume that k∗ customers resumed after the end of the busy time in 1-limited service with the probability of pk∗∈[0,1), and pk∗=pk+1 for k=0,1,…. Consequently, the probability space could be rebuilt as(6)Pi∗zi=BiAiziAizip0+∑k=0∞pk∗zik=BiAizi∑k=0∞pkzik-p0zi0zi+p0zi0.With the definition ofPi(zi), we have(7)Pi∗zi=BiAiziPizi-Pizizi=0zi+Pizizi=0.Applying these results to our case, we obtain(8)Gihz1,…,zN,zh=limn→∞⁡E∏j=1Nzjξin∗zhξhn∗=1ziBi∏j=1NAjzjAhzhGiz1,…,zN,zh-Giz1,…,zN,zhzi=0+Giz1,…,zN,zhzi=0-Giz1,…,zN,zhz1,…,zN,zh=0+∏j=1NAjzjAhzhGiz1,…,zN,zhz1,…,zN,zh=0.The expression can be interpreted as follows. At the start of the visit period atQh, in the case that the former Qi is active, one type-i customer would have been served at tn∗ and new customers arrived at each queue during the service period of the exact type-i customer. The server would skip Qi to Qi+1 when Qi is empty; in that case, the distribution of the number of customers in the systems is represented by the generating function Giz1,…,zi,…,zN-1,zhzi=0, with the exception as the system is entirely empty, which is represented by the generating function Giz1,…,zi,…,zN-1,zhz1,…,zN-1,zh=0. When the system is entirely empty, the server will stop providing service for one time slot until new customers arrive during this time slot, and this number of customers is represented by the last partition of the addition formula.


## 3.2. Expression for the Mean Waiting Time

Now we have derived expressions for the PGFGi+1z1,…,zi,…,zN,zh and Gihz1,…,zi,…,zN,zh pertaining to the queue length at polling epoch of Qi+1 and Qh, we use these results to obtain E[Wi], the mean waiting time of type-i normal customers, and E[Wh], the mean waiting time of type-h high priority customers.


### 3.2.1. The First and Second Moment ofGi+1z1,…,zi,…,zN,zh and Gihz1,…,zi,…,zN,zh

To start the analysis of mean waiting time of type-j customers, we need to calculate the generating functions and its derivation at the point z=1, z is the abbreviation of the (1×N+1) vector of (z1,…,zi,…,zN,zh), and 1 is the (1×N+1) vector with 1.G
i
+
1
(
z
) is the PGF of the joint queue length at the polling epoch of Qi, so we have(9)Giz1,…,zi,…,zN,zh=∑x1=0∞⋯∑xi=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zixi⋯zNxnzhxhPξ1n=x1,…,ξin=xi,…,ξNn=xN,ξhn=xh=∑x1=0∞⋯∑xi=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zixi⋯zNxnzhxhPξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=xiPξin=xi.Taking thekth derivative with respect to zi yields(10)∂kGiz1,z2,…,zi,…,zN,zh∂zik=∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zixi-k⋯zNxNzhxhxi!xi-k!Pξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=xiPξin=xi.Settingzi=0 yields(11)∂kGiz1,z2,…,zi,…,zN,zh∂zikzi=0=∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯1⋯zNxNzhxhk!Pξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=kPξin=k=k!Pξin=k∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯1⋯zNxNzhxhPξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=k=k!Pξin=kEz1ξ1n⋯1⋯zNξNnzhξhn∣ξin=k.Rearranging terms and setting k=0, we have(12)Giz1,z2,…,zi,…,zN,zhzi=0=Pξin=0Ez1ξ1n⋯1⋯zNξNnzhξhn∣ξin=0,Gi1i=Pξin=0.Extending this result we have(13)Gi0=Pξ1n=0,…,ξin=0,…,ξNn=0,ξhn=0.0 is the (1×N+1) vector with 0, and 1j is the (1×N+1) vector with 0 in jth position and 1 in all other entries.Define the first derivative ofGi(z) and Gih(z) at z=1 as (14)gij=limz1,…,zi,…,zN,zh→1⁡∂Giz∂zj,gihj=limz1,…,zi,…,zN,zh→1⁡∂Gihz∂zj,j,k=1,2,…,N,h.(15)gihj=βiλj1-Gi1i+gij+λjGi0(16)gihi=βiλi-11-Gi1i+gii+λiGi0(17)gihh=βiλh1-Gi1i+λhGi0(18)gi+1i=gihi+gihhβhλi1+Fh′1(19)gi+1j=gihj+gihhβhλj1+Fh′1.Calculate ∑j=1Ngj+1k yields(20)1-Gi1i=NλiGi01-ρh-Nρ.Define the second derivative of Gi(z) and Gih(z) at z=1 as(21)gij,k=limz1,…,zi,…,zN,zh→1⁡∂2Giz∂zj∂zkgi0j,k=limz1,…,zi-1,zi+1,…,zN,zh→1⁡∂2Gizzi=0∂zj∂zkgi00j,k=limz1,…,zN,zh→0⁡∂2Gizz1,…,zN,zh=0∂zj∂zkgihj,k=limz1,…,zN,zh→1⁡∂2Gihz∂zj∂zki=1,2,…,Nj,k=1,2,…,N,h.Substitute (4) and (8) into the above second derivative formulas.We assume theN normal queues are symmetrical; that is, λi=λ, βi=β, i=1,2,…,N. Then simplifying these we get the second derivative of Gi(z) and Gih(z) at z=1 as follows:(22)gihh,h=B′′1λh21-Gi1i+βAh′′11-Gi1i+Ah′′1Gi0.(23)gii=1-Gi1i211-ρh-Nρ1-ρhρhA′′1λ1-ρh2+Ah′′βh2+λhBh′′+NB′′1λ2+NβA′′1+λ1-ρh+λhλBh′′11-ρh-Nρ+1-Gi1i.Remark 1.
Thoughgi(i) is the first derivative at z=1Gi(z) in definition, it is clear that it contains the second moment parameter as Aj′′(1) and Bj′′(1). So, gi(i) is a second moment parameter for the system performance.


### 3.2.2. Analysis ofE[Wh] and E[Wi]

DefineWh and Wi as the waiting time of type-h and type-i customers, which denotes the time from the epoch when a customer arrives at the queue to the time it is served. In the present model, high priority type-h customers are served in the exhaustive service and normal type-i customers are served in 1-limited service. Based on the related research works in [14], the mean waiting time of type-h customers E[Wh] and the type-i customers E[Wi] can be calculated as follows:(24)EWh=gihh,h2λhgihh-Ah′′12λh21+ρh+λhBh′′121-ρh,(25)EWi=1λ1-Gi1igii-1λ-A′′12λ2.Taking (17), (22) in (24) in the above expressions, we have(26)EWh=121-ρh1-ρh+NλB′′1+λhBh′′1-12λh21+ρhAh′′1.Taking (17), (22), and (23) in (25) in the above expressions, we have(27)EWi=12λ11-ρh-Nρ1-ρhρhA′′1λi1-ρh2+Ah′′βh2+λhBh′′+NB′′1λ2+NβA′′1+λ1-ρh+λhλBh′′11-ρh-Nρ-A′′12λ2.


## 3.2.1. The First and Second Moment ofGi+1z1,…,zi,…,zN,zh and Gihz1,…,zi,…,zN,zh

To start the analysis of mean waiting time of type-j customers, we need to calculate the generating functions and its derivation at the point z=1, z is the abbreviation of the (1×N+1) vector of (z1,…,zi,…,zN,zh), and 1 is the (1×N+1) vector with 1.G
i
+
1
(
z
) is the PGF of the joint queue length at the polling epoch of Qi, so we have(9)Giz1,…,zi,…,zN,zh=∑x1=0∞⋯∑xi=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zixi⋯zNxnzhxhPξ1n=x1,…,ξin=xi,…,ξNn=xN,ξhn=xh=∑x1=0∞⋯∑xi=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zixi⋯zNxnzhxhPξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=xiPξin=xi.Taking thekth derivative with respect to zi yields(10)∂kGiz1,z2,…,zi,…,zN,zh∂zik=∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯zixi-k⋯zNxNzhxhxi!xi-k!Pξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=xiPξin=xi.Settingzi=0 yields(11)∂kGiz1,z2,…,zi,…,zN,zh∂zikzi=0=∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯1⋯zNxNzhxhk!Pξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=kPξin=k=k!Pξin=k∑x1=0∞⋯∑xN=0∞∑xh=0∞z1x1⋯1⋯zNxNzhxhPξ1n=x1,…,ξNn=xN,ξhn=xh∣ξin=k=k!Pξin=kEz1ξ1n⋯1⋯zNξNnzhξhn∣ξin=k.Rearranging terms and setting k=0, we have(12)Giz1,z2,…,zi,…,zN,zhzi=0=Pξin=0Ez1ξ1n⋯1⋯zNξNnzhξhn∣ξin=0,Gi1i=Pξin=0.Extending this result we have(13)Gi0=Pξ1n=0,…,ξin=0,…,ξNn=0,ξhn=0.0 is the (1×N+1) vector with 0, and 1j is the (1×N+1) vector with 0 in jth position and 1 in all other entries.Define the first derivative ofGi(z) and Gih(z) at z=1 as (14)gij=limz1,…,zi,…,zN,zh→1⁡∂Giz∂zj,gihj=limz1,…,zi,…,zN,zh→1⁡∂Gihz∂zj,j,k=1,2,…,N,h.(15)gihj=βiλj1-Gi1i+gij+λjGi0(16)gihi=βiλi-11-Gi1i+gii+λiGi0(17)gihh=βiλh1-Gi1i+λhGi0(18)gi+1i=gihi+gihhβhλi1+Fh′1(19)gi+1j=gihj+gihhβhλj1+Fh′1.Calculate ∑j=1Ngj+1k yields(20)1-Gi1i=NλiGi01-ρh-Nρ.Define the second derivative of Gi(z) and Gih(z) at z=1 as(21)gij,k=limz1,…,zi,…,zN,zh→1⁡∂2Giz∂zj∂zkgi0j,k=limz1,…,zi-1,zi+1,…,zN,zh→1⁡∂2Gizzi=0∂zj∂zkgi00j,k=limz1,…,zN,zh→0⁡∂2Gizz1,…,zN,zh=0∂zj∂zkgihj,k=limz1,…,zN,zh→1⁡∂2Gihz∂zj∂zki=1,2,…,Nj,k=1,2,…,N,h.Substitute (4) and (8) into the above second derivative formulas.We assume theN normal queues are symmetrical; that is, λi=λ, βi=β, i=1,2,…,N. Then simplifying these we get the second derivative of Gi(z) and Gih(z) at z=1 as follows:(22)gihh,h=B′′1λh21-Gi1i+βAh′′11-Gi1i+Ah′′1Gi0.(23)gii=1-Gi1i211-ρh-Nρ1-ρhρhA′′1λ1-ρh2+Ah′′βh2+λhBh′′+NB′′1λ2+NβA′′1+λ1-ρh+λhλBh′′11-ρh-Nρ+1-Gi1i.Remark 1.
Thoughgi(i) is the first derivative at z=1Gi(z) in definition, it is clear that it contains the second moment parameter as Aj′′(1) and Bj′′(1). So, gi(i) is a second moment parameter for the system performance.


## 3.2.2. Analysis ofE[Wh] and E[Wi]

DefineWh and Wi as the waiting time of type-h and type-i customers, which denotes the time from the epoch when a customer arrives at the queue to the time it is served. In the present model, high priority type-h customers are served in the exhaustive service and normal type-i customers are served in 1-limited service. Based on the related research works in [14], the mean waiting time of type-h customers E[Wh] and the type-i customers E[Wi] can be calculated as follows:(24)EWh=gihh,h2λhgihh-Ah′′12λh21+ρh+λhBh′′121-ρh,(25)EWi=1λ1-Gi1igii-1λ-A′′12λ2.Taking (17), (22) in (24) in the above expressions, we have(26)EWh=121-ρh1-ρh+NλB′′1+λhBh′′1-12λh21+ρhAh′′1.Taking (17), (22), and (23) in (25) in the above expressions, we have(27)EWi=12λ11-ρh-Nρ1-ρhρhA′′1λi1-ρh2+Ah′′βh2+λhBh′′+NB′′1λ2+NβA′′1+λ1-ρh+λhλBh′′11-ρh-Nρ-A′′12λ2.


## 4. Numerical Study

In this section we study the accuracy of the theoretical analysis and compare the mean waiting time of the present model with two existing two-level polling models. Consider anN+1 queues’ model with one high priority queue Qh and N normal queues Qi (i=1,…,N) defined as follows: the service times of all customers are exponentially distributed with mean β in Qi and βh in Qh. The arrival processes are Poisson process with rate λ in Qi and λh in Qh. The relative parameter values are listed in Table 1, in which {a:k:b} means the parameter is varied between a and b in steps of k.Table 1
Test bed used to compare the mean waiting time.
Parameter
Number of normal queues
Arrival rate
Service time
Switch over time
Notation value
N
λ
λ
h
β
β
h
γ
Figure1(a)
1
:
1
:
9
0.04
0.1
2
2
Figure1(b)
4
0.02
0.1
:
0.05
:
0.4
1
2
—
Figure1(c)
4
0.02
:
0.02
:
0.18
0.1
1
2
—
Figure1(d)
4
0.02
0.1
2
1
:
1
:
9
—
Figure1(e)
4
0.02
0.1
1
:
1
:
10
2
—
Figure2
4
0.01
:
0.01
:
0.09
0.1
2
2
1From Figure1, we can clearly see that, firstly, the theoretical value and the simulation result coincided with each other. Secondly, when the total offered load grew with the arrival rate, service time, and the number of queues, with the mean waiting time increasing distinctly in Qi, while the performances in Qh are much better, both queue and mean waiting time are much lower than normal queues, and the growth in Qh with the total offered load presents much more smoothly.Figure 1
Theoretical and simulation values ofE[Wh] and E[Wi] from different values of the load increasing with the increasing of the number of normal queues. (a) is the total offered load increasing with the growth of the number of normal queues. (b) is the total offered load increasing with the growth of the arrival rate of Qh. (c) is the total offered load increasing with the growth of the arrival rate of Qi. (d) is the total offered load increasing with the growth of the service time of Qh. (e) is the total offered load increasing with the growth of the service time of Qi.
(a)
(b)
(c)
(d)
(e)It is worth considering whether the state-dependent mechanism improves the performance of the system comparing with the existing two-level polling systems. In order to answer this question, we compare a classical two-level system with switch-over time [6], abbreviated as classical system and a parallel two-level system [8], abbreviated as parallel system in Figure 2. The service discipline in the comparisons is 1-limited service for normal queues and exhaustive service for the key queue. Overall models have the same test bed as shown in Table 1. We just vary the working mechanism.Figure 2
Comparing of mean waiting time among the classical two-level system [6], the parallel two-level system [8], and the state-dependent two-level system. (a) is the theoretical value comparison of E[Wi] with the growth of the arrival rate in Qi. (b) is the theoretical value comparison of E[Wh] with the growth of the arrival rate in Qi.
(a)
(b)Figure2 shows the mean waiting time of normal queues in (a) and mean waiting time of key queue in (b). Comparing with the forgoing, the state-dependent system achieves a better performance in delay guarantee and stability. It is clear in Figure 2(a), for lower load, in most of the cases, that there is no customer in the buffers; thus a switch-over time is necessary when the server switches between Qi and Qh in the classical and parallel system, while the empty queues would be skipped in the present model. Therefore, customers in the state-dependent system achieve a lower mean waiting time, which is under 20% of the forgoing. In the heavy traffic, the server could not provide service in the necessary switch-over time for the classical system; consequently, it becomes unstable when the arrival rate of Qi grows over 0.06 in this case. The parallel system and the state-dependent system have better performance in system stability; especially in state-dependent system, the mean waiting time of the normal customers has less than 50% of which in the parallel system. A conclusion can be drawn from a comparison between Figures 2(a) and 2(b), which is that for all three two-level models the mean waiting time of the customers in key queue is significantly lower than that in normal queues, and as illustrated in Figure 2(b), the mean waiting time for h-type customers in state-dependent system is lower than that of the others.


## 5. Conclusion

When comparing the model of the present paper with the existing literature, the contribution of the present paper is twofold. One of the most striking differences is the queues which are partitioned as active queue and idle queue by their buffer condition, and only active queues with customers waiting in the buffer could be visited by the server in a two-level order. As illustrated in the numerical example, bothi-type customers in normal queues and h-type customers in key queue acquire better delay performance than those in systems without queue-stated differentiation. Another notable contribution of the paper is that we achieve the closed-form exact expressions of the mean waiting time for customers in normal queues and key queue, under the assumption of the symmetric of normal queues. The total unknowns in these equations are all first moments of random variables and, thus, no correlation terms are required.



---

*Source: 109325-2015-10-18.xml*