# Modeling and Optimization ofM/G/1-Type Queueing Networks: An Efficient Sensitivity Analysis Approach

Authors: Liang Tang; Hong-sheng Xi; Jin Zhu; Bao-qun Yin
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

A mathematical model forM/G/1-type queueing networks with multiple user applications and limited resources is established. The goal is to develop a dynamic distributed algorithm for this model, which supports all data traffic as efficiently as possible and makes optimally fair decisions about how to minimize the network performance cost. An online policy gradient optimization algorithm based on a single sample path is provided to avoid suffering from a “curse of dimensionality”. The asymptotic convergence properties of this algorithm are proved. Numerical examples provide valuable insights for bridging mathematical theory with engineering practice.


---

## Body

## 1. Introduction

In the past decades, great efforts have been devoted to model and optimize the network-based communication systems with the increasing transmitting demands and sophisticated performance criteria. However, technical challenges abound in designing such systems due to the limited network resources and the stochastic network characteristics. It is wellstudied that queueing theory is one of the primary tools used to deal with traffic engineering problems over both wired and wireless packet networks [1–3]. Factors affecting performance of network systems, based on the models in queueing theory, include the arrival rates (or the interarrival time distributions), the service rates (or the interservice time distributions), and the queue discipline. In this paper, we will concentrate on how to optimally and efficiently allocate the service rates to all concurrent user queues in each network element according to the arrival rates, so that the the lowest possible performance cost is achieved.Suppose that the arrival rates parameter for each user is uncontrollable, and the interarrival time parameter is exponentially distributed. Let queue discipline be first-come first-served (FCFS). Based on this model, the decision parameter is the service time, namely, the service rates allocated to each user. Without loss of generality, consider that the service times of each user are independent and identically distributed withG. Thus, the user queues are modeled as multiple concurrent M/G/1 queues, for which many techniques can be found in the literature [4–7]. More importantly, the optimal resource allocation problem is then translated into a resource-constrained Markov decision problem (MDP). The objective of the MDP is to find a resource allocation policy that minimizes the overall performance cost, by observing and analyzing the system behavior information. To achieve this goal in such a mathematically tractable MDP model, some solving results were proposed in [8, 9]. However, these methods may typically suffer from a “curse of dimensionality” [10]. In addition, if no structural information about the system is gained, we cannot explicitly compare the performance cost by observing and analyzing the network system behavior under different policies. Hence, a crucial question that comes to mind is how can we achieve our goal of performance cost minimization using as little computation effort and system structure information as possible? Thinking along this direction, we propose a sensitivity-based optimization algorithm tailored for the bandwidth-constrained and backlog-constrained M/G/1 queueing system.Within the above issues addressed, we now confront a key question, namely, how to quantify the network system cost in terms of performance metrics. Note that the performance metrics may change not only as actual network scenarios vary but also as the influence factors change, that is, different network environments will lead to different definitions of performance metrics. For instance, a flexible cost function was proposed in [11], which takes into account the power, interference, backlog, and other factors in the ultrawide band (UWB) communication networks. In [12], a bandwidth related cost function was presented for wide area overlay networks. Another type of performance metrics, considering the waiting time and the energy consumption for serving jobs in an M/GI/1 processor sharing (PS) queue, was provided in [13]. Therefore, throughout this paper, we use the word “cost” to refer to both backlog and service rates-related performance cost criteria in a broad sense.In summary, the contributions of this paper are as follows. Firstly, we present a distributed resource-constrainedM/G/1-type queueing model for supporting multiple user traffic over communication networks. By translating the multiple queues of each relay network node into continuous-time semi-Markov processes, we further formulate the network system performance cost minimization as a stochastic optimization problem in the Markov system. Secondly, within the optimization framework, we explicitly define the network system performance cost measure, based on which an online policy scheme combining performance sensitivity analysis and MDP is proposed. This scheme is cost-benefit since during the data transmission process, the performance cost is significantly reduced by choosing the optimal policy while the computational complexity is greatly decreased in that it is based on a single sample path, that is, a trajectory of each user queue. Thirdly, with the estimation of the performance gradients, a resource allocation algorithm is developed. From the performance comparison formula, we directly obtain the optimality condition. Moreover, the asymptotic convergence properties of such algorithm are proved. Last but not least, the established model can be easily extended to a more general situation when the states of the M/G/1-type queueing system are partially observable, that is, partially observable Markov decision problems (POMDPs).The rest of paper is organized as follows. Section2 starts by presenting the M/G/1-type queueing system model. Next, Section 3 proposes the cost-benefit resource allocation optimization algorithm. To evaluate the performance of the proposed algorithm, numerical examples are provided in Section 4. Finally, the paper concludes with a short discussion in Section 5.


## 2. System Model

In this section, we model the queueing system according to the dynamic transmission procedure of each network user. With the formulation ofM/G/1 user queues, firstly, we derive the steady-state Markov transition probability matrix. We then define the performance cost measure, based on which the objective function of the optimization algorithm is presented. Before digging into details, we summarize the used notations in Table 1.Table 1
Notations.
SymbolDefinition𝒢=(𝒱,ℰ)Graph representation of the networkCιService capacity of linkιN(t)Number of active user applications served within a network elementCo(t)Leftover service capacityGiGeneral distribution of theith user queue's interservice timeλiThe long-term average rate ofith user arrivalsμiMean service rates of theith user queueKEach user queue's backlog capacityXiSemi-Markov process of eachM/G/1-type user queueΦThe state space of each user queueYiThe embedded Markov chain of the semi-Markov processQμi(t)The semi-Markov kernelPμiThe transition probability matrixAμiThe infinitesimal generatorπμiThe steady-state probability vectorfμi (fi)The performance cost functionηfμiThe performance cost measuregμiThe performance potential vectorDfμiThe realization matrixΓiThe feasible region of the service rates allocated to theith user queueΩ(t)The policy space for all user queuesν(t)A feasible resource allocation policyϵThe stopping criterion of the policy algorithmlThe iteration index of the policy algorithmspThe span seminormConsider a network modeled by a topology graph, that is,𝒢=(𝒱,ℰ), where 𝒱 denotes the set of network elements (nodes), and ℰ represents the set of links. Note that if a link ι∈ℰ, there exist a work-conserving server with time-invariant service capacity Cι, which serves packets and transfers them from source element to end element of ι. More precisely, consider that each element v∈𝒱 keeps a separate queue for every user traffic going through it, which is illustrated in Figure 1. For the simplicity of exposition, let N(t) be the number of user queues served at any given time t≥0. Without loss of generality, consider  that the capacity of each user queue i∈{1,…,N(t)} is upper bounded by a constant K, that is, M/G/1/K queueing model with limited backlog capacity K.Figure 1
Simplified network structure.Denote the service time allocated to user queuei as a general distribution Gi(s,t) for any given time t≥0. Since the users arrive at and depart from each network element randomly, we should allocate the service rates  μi(t) dynamically for all t≥0 so that the performance cost at the element is minimized.Then, we have(2.1)μi(t)≡1∫0∞sdGi(s,t)∈ℛ+≜(0,∞),
where μi(t) represents the mean service rates of user queue i at time t, satisfying ρi≜λi/μi(t)<1, λi is the long-term average rate of the  ith user arrivals, namely, the intensity of the Poisson arrival process. For ease of presentation, hereafter, μi(t) and μi will be used interchangeably. Let Γi(t)⊂ℛ+ be the feasible region of the service rates allocated to user queue i. To be more precise, we introduce some definitions to accurately modeling the ith user queue.Definition 2.1 (semi-Markov queueing process).
A semi-Markov processXi={Xti,t≥0} characterizes the ith user queue's behavior on the state space Φ={0,1,…,K}, where Xti represents the number of packets in the queue after the latest packet left a network element at time t≥0.Remark 2.2.
The semi-Markov kernel ofXi can be further represented as
(2.2)Qμi(t)[(K+1)×(K+1)]=[p0i(t)p1i(t)p2i(t)⋯pK-1i(t)pKi(t)q0i(t)q1i(t)q2i(t)⋯qK-1i(t)qKi(t)0q0i(t)q1i(t)⋯qK-2i(t)qK-1i(t)⋮⋮⋮⋱⋮⋮000⋯q0i(t)q1i(t)],
where
(2.3)qki(t)=∫0te-λis(λis)kk!dG(s,t),k∈Φ,pki(t)=∫0tqki(t-s)λie-λisds,k∈Φ.LetYi={Ymi;m=0,1,2,…} be the embedded Markov chain of Xi, where Ymi is interpreted as the number of packets in the ith user queue when the mth packet has been served. It is essential to note that Yi is positive recurrent, irreducible, and aperiodic under the condition of ρi<1 since Xi is. Moreover, Yi has both the same steady-state probability vector πμi=(πμi(0),…,πμi(K)),πμi(k)>0,k∈Φ and the same steady-state performance cost measure (discussed later) as Xi. According to [3], Xi has standard transfer probabilities pkj(t),k,j∈Φ, and for any j with respect to k∈Φ,pkj(t)/t converges consistently to a constant for k≠j as t→0. In this state, the transition probability matrix Pμi of Yi can be derived as follows
(2.4)P[(K+1)×(K+1)]μi=limt→∞Qμi(t)[(K+1)×(K+1)]=[a0ia1ia2i⋯aK-1iaKia0ia1ia2i⋯aK-1iaKi0a0ia1i⋯aK-2iaK-1i⋮⋮⋮⋱⋮⋮000⋯a0ia1i],
where(2.5)limt→∞pki(t)=limt→∞qki(t)=aki,k∈Φ.Remark 2.3.
Note that the symbolaki represents the probability of k packets arriving at the time interval when a packet of the ith user queue is being served. The balance equation of each concurrent user queue i can be  further  expressed as
(2.6)πμi(Pμi-I)=0,πμie=1,
where e=(1,1,…,1)T is a (K+1)-dimensional column vector whose all components are 1's, and the superscript “T” denotes transpose.In principle, the performance cost measure is based on the definition of performance cost function. Note that performance cost is a commonly used term that changes its meaning with different network environments. Considering there is limited backlog space in each network element, therefore, the more backlog is occupied, the higher cost is paid. In this state, with the increasing of service rates, the backlog-related cost can be reduced accordingly. However, in many practical networks, especially considering the various wireless environments, transmission cost cannot be neglected. In general, the transmission power is considered as a convex increasing function with respect to the service rates. Thus, the design of performance cost function should trade off both the backlog related and the service rates related costs. Conceptually, we associate to each user queue a performance cost function defined as follows.Definition 2.4 (performance cost function).
Consider a general performance cost functionfi:Φ×Γi→ℛ+ associated to the ith user queue, which is the sum of the backlog-related cost φ1(k) and the service rates-related cost φ2(μi), that is,
(2.7)fi(k,μi)=φ1(k)+φ2(μi),∀k∈Φ.Suppose that the performance cost functionfi is differentiable with the service rates μi on Γi. For ease of notation, hereafter, the terms fi and fμi are used interchangeably throughout the paper. Now, it is imperative to define the performance cost measure as our objective function for each user queue. Motivated by [3, 14], the definition is as follows.Definition 2.5 (performance cost measure).
The performance cost measureηfμi with respect to the service rates μi for each user queue i is denoted as
(2.8)ηfμi=Eπμi(fμi)=∑k∈Φπμi(k)fμi(k)=πμifμi,
where fμi=(fμi(0),…,fμi(K))T is a (K+1)-dimensional column vector, and Eπμi denotes the expectation with respect to the steady-state probability πμi of the semi-Markov process Xi in Definition 2.1.Since the state space ofXi is finite, we should note that for each nonnegative bounded performance cost function, there is(2.9)ηfμi=∑k∈Φπμi(k)fμi(k)<∞.Remark 2.6.
Each user queuei has been modeled as a semi-Markov queueing process Xi, based on which the transition probability matrix P[(K+1)×(K+1)]μi has been derived. Suppose that it is differentiable with service rates μi∈Γi. Denote A[(K+1)×(K+1)]μi=P[(K+1)×(K+1)]μi-I as an infinitesimal generator of Xi under the service rates  μi, where akk and akj for k≠j are elements of A[(K+1)×(K+1)]μi and satisfy akk<0 and akj≥0 for k≠j, k,j∈Φ. Thus, the infinitesimal generator is differentiable with respect to μi. Note that the elements of A[(K+1)×(K+1)]μi represent the transition rate of the packet number in each user queue. More importantly, the cost-benefit optimization algorithm can be further developed for all M/G/1-type user queues in Section 3 by changing the service rates μi allocated so that the corresponding infinitesimal generator of each user queue is modified.


## 3. Resource Allocation Algorithm

In this section, we take a fresh look at the problem of resource allocation from the perspective of system performance cost and explore a cost-benefit gradient algorithm that minimizes the performance cost for all concurrentM/G/1-type queues, subject to the bandwidth constraint.


### 3.1. Problem Formulation and Optimality Criterion

Since we focus on the stochastic dynamic queueing system, the estimation of its statistical properties is essential. In addition, such estimation needs not only to be accurate but more importantly, to be efficient when taking into consideration the delay sensitiveness of the real-time network applications. Consider that the main tenet of perturbation analysis (PA) is that a great deal of information is contained in the sample paths of a dynamic system, beyond the usual statistics collected such as the means and variances of various variables [15]. Thus, in essence, we can estimate the performance gradient with respect to the service rates and further minimize the user queue's performance cost measure based on a single sample path with PA.In particular, several PA approaches have been introduced in solving network problems (see, e.g., [16, 17]). However, a general approach that supports a wide range of stochastic optimization problems awaits to be proposed. A new approach was proposed in [18] to analyze a number of Markov systems based on a single sample path. Moreover, the optimization formulations for Markov [14, 19, 20], semi-Markov [21], and partially observable Markov [22] systems were proposed, and in [3], the theory has successfully been extended to evaluate the M/G/1 queueing systems. The structure of PA-based queueing system is shown in Figure 2. For each feasible resource allocation policy, a set of service rates are allocated to each user queue. With each change of one user queue's service rate, a perturbation is generated on the queue's sample path, which has effect on the system performance cost.Figure 2
Structure of user queueing system with PA.As illustrated in Figure3, in an M/G/1-type user queue {Ymi;m=0,1,2,…}, such a perturbation can be regarded as a “jump” among its states k∈Φ and has effect on the performance cost ηfμi. Thus, we need to measure all states' effect on the performance cost ηfμi before discussing the performance cost optimization. We briefly introduce a concept called performance potential that is useful in this paper [18].Figure 3
A perturbation of a single sample path.Definition 3.1 (performance potential).
Denotegμi(k) as the ith user queue's performance potential of state k∈Φ under service rates μi with respect to the performance cost function fi. It measures the effect of state k to the performance cost ηfμi and can be written as
(3.1)gμi(k)=E{∑n=0∞[fi(Ymi,μi)-ηfμi]∣Y0i=k}.Remark 3.2.
The performance potential vector of theM/G/1/K user queue {Ymi} with respect to the performance cost function fμi is denoted as gμi=(gμi(0),…,gμi(K))T. In essence, the performance potential vector is the solution of the Poisson equation, which has been studied remarkably in the literature [23]:
(3.2)Aμigμi=-fμi+ηfμie.
Furthermore, if {Ymi} is strongly ergodic, all of the performance potential vectors can be calculated by gμi=-(Aμi)#fμi+ce,c∈ℛ, where (Aμi)# is said to be the group inverse (for details, see [18]) of the {Ymi}'s infinitesimal generator Aμi under service rates μi.Now, we need to assign the feasible service rates region to each active user queue. It is well-studied from queueing theory that anM/G/1-type user queue {Ymi;m=0,1,2,…} is called stable if ρi<1, that is, λi<μi. Moreover, the network element is stable if and only if all individual user queues are stable. Suppose that the lower bound service rates of each user queue at epoch t≥0 are set to μimin(t)=λi+1, and ∑i=1N(t)μimin(t)<Cι. Thus, we denote the leftover service capacity as Co(t)≜Cι-∑i=1N(t)μimin(t). In this state, we further assign the ith user queue a parameter called sharing weight(3.3)ϕi(t)≜λi∑i=1N(t)λi.
Apparently, we have ∑i=1N(t)ϕi(t)=1 for any given t. Thus, at epoch t, the service rates of user queue i are upper bounded by,(3.4)μimax(t)=μimin(t)+ϕi(t)Co(t).
Therefore, the service rates policy space in Figure 2 is defined as follows.Definition 3.3 (feasible policy space).
The policy space for all user queues at epocht≥0 can be denoted as a compact set Ω(t), where Ω(t)≜Γ1(t)×⋯×ΓN(t)(t), and Γi(t)≜[μimin(t),μimax(t)],i∈{1···N(t)}.Next, we analyze the optimal criterion for the performance cost optimization.Theorem 3.4 (optimality criterion).
A cost-benefit resource allocation policyν*(t)≜(μ1*(t),…,μN(t)*(t))∈Ω(t) is optimal with each given initial policy if and only if for each user queue i, one has
(3.5)χi≜minimizeμi(t)∈Γi(t){fμi(t)+Aμi(t)gμi*(t)-eηfμi*(t)}=0,∀i∈{1,…,N(t)}.Proof.
Note thatΓi(t) is a compact set, and fμi(t)+Aμi(t)gμi(t) is component-wise continuous on Γi(t). Thus, there must exist at least one cost optimal service rates in Γi(t).
According to [20], we have the fact that the service rates  μi*(t) for ith user queue is cost optimal if and only if(3.6)fμi*(t)+Aμi*(t)gμi*(t)⪯fμi(t)+Aμi(t)gμi*(t),∀μi(t)∈Γi(t),
where the symbol ⪯ denotes vector inequality or component-wise inequality in ℛ(K+1), and (K+1) is the the states' number of each user queue.
Note that a better cost-benefit service rates can be searched based on the comparison of current service rate. Besides, from (3.2), we have eηfμi*(t)=fμi*(t)+Aμi*(t)gμi*(t).
Thus, we can conclude that if theμi*(t) is the cost optimal service rates, the following equation:(3.7)χi=minimizeμi(t)∈Γi(t){fμi(t)+Aμi(t)gμi*(t)-eηfμi*(t)}=0
is established and vice versa.


### 3.2. Gradient-Based Policy Optimization

Now, the purpose is to develop an efficient and practical policy algorithm, which minimizes all the user queues' performance cost based on the corresponding sample paths. In essence, the objective function for each user queue in Definition2.5 represents the time-average performance measure of the M/G/1 queue. Thus, developing a global optimization algorithm for such a performance measure will greatly increase the complexity. More importantly, to some extent, it is impractical to consider both the delay sensitiveness of user applications and the dynamic changes of the network element. In this state, a fast gradient-based optimization for the stochastic system is considered. It is well studied that a gradient optimization algorithm is to find a local minimum of objective function; however, it can be fairly efficient, especially when the interval Γi(t) for each user queue i is not very large. To begin with, the performance gradient formula for each user queue is derived as follows.Theorem 3.5 (performance gradient).
For any given resource allocation policyν(t)=(μ1(t),…,μN(t)(t))∈Ω(t) at each event time t≥0,k=1,2,…, the gradient of the performance cost ηfμi(t) generated by the ith user queue is obtained by
(3.8)∇ηfμi(t)=πμi(t)∇Pμi(t)gfμi(t)+πμi(t)∇fμi(t).Proof.
By taking the gradient of the performance measure (2.8), we have
(3.9)∇ηfμi(t)=∇πμi(t)fμi(t)+πμi(t)∇fμi(t).
From [14, 20], there must be particular solution to (3.2), such that ηfμi(t)=πμi(t)gμi(t); thus, we obtain
(3.10)(-Aμi(t)+eπμi(t))gμi(t)=fμi(t).
With Pμi(t)=Aμi(t)+I, we further have
(3.11)(I-Pμi(t)+eπμi(t))gμi(t)=fμi(t).
Left-multiply by ∇πμi(t) on both sides of (3.11), it follows that
(3.12)∇πμi(t)fμi(t)=∇πμi(t)(I-Pμi(t)+eπμi(t))gμi(t).
Recall that πμi(t)e=1,Pμi(t)e=e,andπμi(t)Pμi(t)=πμi(t), then we have
(3.13)∇πμi(t)Pμi(t)+πμi(t)∇Pμi(t)=∇πμi(t),∇πμi(t)e=0.
Hence, using (3.12), it suffices to show that
(3.14)∇πμi(t)fμi(t)=πμi(t)∇Pμi(t)gμi(t).
Combining (3.9) with (3.14), the result then follows.Then, we proceed to describe the process flow of thepolicy gradient algorithm shown in Figure 4. The procedure of the algorithm is described in Algorithm 1. Note that in Algorithm 1,(3.15)sp(h)≜maxi{h(i)}-mini{h(i)},h∈ℛn
is defined as the span seminorm on ℛn.Algorithm 1:Policy gradient algorithm.
Input: An arbitrary initial policy ν(t)=(μ1(t),…,μN(t)(t))∈Ω(t) at given t≥0.Output: The optimal policy for all user queues ν*(t)=(μ1*(t),…,μN(t)*(t))∈Ω(t).Procedure:(1) Choose 0<ϵ≪1 as the stopping criterion for all user queues.(2) for  queue i=1 to N(t)  do(3)  repeat(4)   Set iteration index l=0.(5)   Calculate πμil(t) and gμil(t) by solving (2.6) and (3.2), respectively.(6)   Determine the gradient such that:∇ηfμil(t)=πμil(t)∇Pμil(t)gμil(t)+πμil(t)∇fμil(t).(7)   Do line search along the gradient, choose the right step size γil.(8)   Update service rates μil+1(t):=μil(t)-γil∇ηfμil(t).(9)   Set l:=l+1.(10)  Until  sp(fμil+1(t)+Aμil+1(t)gμil(t))<ϵ  or  μil+1(t)∉Γi(t).(11) end  forFigure 4
Policy gradient algorithm procedure.Moreover, the construction of the algorithm is presented as follows. The algorithm begins by choosing an arbitrary feasible policy for all user queues at given timet. Then, with current service rates, the corresponding performance gradient is calculated by analyzing the sample path of each user queue. Based on the line search along the gradient, the right step size is obtained. Thus, a better policy can be updated for each user queue. By iteration until the stopping criterion is met, the optimal cost-benefit resource allocation policy can finally be achieved.Without loss of generality, suppose that every gradient iteration of each user queue leads to an improving performance cost, that is,(3.16)fμil+1(t)+Aμil+1(t)gμil(t)⪯fμil(t)+Aμil(t)gμil(t),∀i∈{1,…,N(t)},
where l∈𝒵+ represents the iteration index in Algorithm 1. The convergence property of the policy gradient algorithm is evaluated as follows.Theorem 3.6 (convergence property).
Considerνl(t)=(μ1l(t),…,μN(t)l(t))∈Ω(t),l∈𝒵+ is a performance improving resource allocation policy sequence at each given time t≥0, then foralli∈{1,…,N(t)}; one has:(a)
(3.17)liml→∞sp(fμil+1(t)+Aμil+1(t)gμil(t))=0,(b)
That there must exist an optimal cost-benefit resource allocation policy, denoted asν*(t)=(μ1*(t),…,μN(t)*(t))∈Ω(t), such that
(3.18)liml→∞μil(t)=μi*(t),liml→∞ηfμil(t)=ηfμi*(t).Proof.
For part (a) Sinceνl(t)=(μ1l(t),…,μN(t)l(t))∈Ω(t),l∈𝒵+,i∈{1,…,N(t)} is a performance improving resource allocation policy sequence, we can conclude that for each user queue i, {ηfμil(t)} is a monotonously decreasing and bounded performance cost sequence, with lower bound ηfμi*(t).
By using the continuity ofηfμi(t), we obtain a service rates μi(t)∈Γi(t) for each user queue i, satisfying ηfμi(t)=c∈ℛ+ and liml→∞μil(t)=μi(t).
Thus, it follows that(3.19)liml→∞(fμil+1(t)+Aμil+1(t)gμil(t))=fμi(t)+Aμi(t)gμi(t)=eηfμi(t),
which is equivalent to
(3.20)liml→∞{(fμil+1(t)+Aμil+1(t)gμil(t))(k)}=ηfμi(t),∀k∈Φ.
Recall that(3.21)sp(fμil+1(t)+Aμil+1(t)gμil(t))=maxk∈Φ{(fμil+1(t)+Aμil+1(t)gμil(t))(k)}-mink∈Φ{(fμil+1(t)+Aμil+1(t)gμil(t))(k)};
by taking limit as l→∞, we further have
(3.22)liml→∞sp(fμil+1(t)+Aμil+1(t)gμil(t))=ηfμi(t)-ηfμi(t)=0.
For part (b) Note that forallϵ>0,∃l0∈𝒵+, such that sp(fμil+1(t)+Aμil+1(t)gμil(t))<ϵ,holds when l>l0.
To show the second relation of the theorem, consideringl>l0; it follows that(3.23)ηfμil+1(t)=πμil+1(t)fμil+1(t)=πμil+1(t)(fμil+1(t)+Aμil+1(t)gμil(t))≤maxk∈Φ{(fμil+1(t)+Aμil+1(t)gμil(t))(k)}.
Since in Algorithm1, μil+1(t) is the best choice for μil(t) along the gradient by the line search, we therefore have(3.24)ηfμi*(t)=πμi*(t)(fμi*(t)+Aμi*(t)gμil(t))≥πμi*(t)(fμil+1(t)+Aμil+1(t)gμil(t))≥mink∈Φ{(fμil+1(t)+Aμil+1(t)gμil(t))(k)}.
Subtracting (3.23) by (3.24), for ∀l>l0, it follows that(3.25)0<ηfμil+1(t)-ηfμi*(t)≤sp(fμil+1(t)+Aμil+1(t)gμil(t))<ϵ.
Thus, it can be regarded thatμil+1(t) is an ϵ-optimal service rates, and we can write liml→∞ηfμil+1(t)=ηfμi*(t) by the arbitrariness of ϵ.
Finally, from the fundamental fact of the uniqueness principle of limitation theory, we can conclude thatηfμi*(t)=ηfμi(t), which is equivalent to say that μi(t) is an optimal cost-benefit service rates. This leads immediately to the results that liml→∞μil(t)=μi*(t) and liml→∞ηfμil(t)=ηfμi*(t).Remark 3.7.
By proving the convergence property of the policy gradient algorithm, the cost-benefit resource allocation optimization approach for theM/G/1/K user queues has been proposed. In a broad sense, the service time allocated to each user queue i has been considered as a general distribution Gi. However, the mathematical expression of performance gradient is not unique according to different application scenarios.


### 3.3. Performance Gradient Analysis of Application Scenarios

To make the analysis more tractable, we now present two application scenarios for which the performance gradient can be explicitly derived.Deterministic inter-service time.
This is the simplest practical case where inter-service times for each user queuei are deterministic, that is, M/D/1/K. Without loss of generality, we denote each inter-service time as a constant 1/μi. Consider now that  ρi=λi/μi<1. Let Pμi be the transfer matrix of the embedded Markov chain. In this scenario, hence, we have that for all k∈Φ, the element aki of the transfer matrix is equal to,
(3.26)aki=e-ρiρikk!,
implying that the element of steady-state probability vector πμi(k),k∈Φ satisfies
(3.27)πμi(k)={1-ρi,ifk=0,(1-ρi)(eρi-1),ifk=1,(1-ρi)∑j=1k(-1)k-je-jρi[(jρi)k-j(k-j)!+(jρi)k-j-1(k-j-1)!],otherwise.
According to (3.26), hence, we have
(3.28)∂aki∂μi={λiμi2e-ρi=ρiμiaki,ifk=0,λie-ρiμi2[ρikk!-ρik-1k-1!]=ρiμi(aki-ak-1i),otherwise.Corollary 3.8.
Considering theith user queue in the steady state, from Theorem 3.5, the performance gradient with respect to the service rates μi for the case of M/D/1/K is(3.29)∂ηfμi∂μi=ρiμi∑k=0K[πμi(k)-πμi(k-1)]gμi(k)+πμi∂f∂μi,
where πμi=(πμi(0),…,πμi(K)),gμi=(gμi(0),…,gμi(K)), and πμi(-1)=0.Exponential inter-service time.
Having considered the straightforward scenario of deterministic service rates, we will now investigate theM/M/1/K case where the inter-service times are independent and exponentially distributed, that is, memoryless. For ease of notation, we show results using the same parameters as in the first scenario. Similarly, in this case, we derive the element aki,forallk∈Φ of the transfer matrix as follows:
(3.30)aki=ρik(1+ρi)k+1;
it  suffices to show that,
(3.31)πμi(k)=(1-ρi)ρik,∂aki∂μi=ρi-kμi(1+ρi)aki.Corollary 3.9.
Considering theith user queue in the steadystate, from Theorem 3.5, the performance gradient with respect to the service rates μi for the case of M/M/1/K is
(3.32)∂ηfμi∂μi=πμi∂f∂μi-∑k=0Kbkigμi(k),
where
(3.33)bki=πi(0)k-ρi1+ρiaki+∑j=0kπi(j+1)k-j-ρi1+ρiak-ji.Remark 3.10.
Note that the essential feature behind the cost-benefit resource allocation is the performance gradient corresponding to the service rates. Based on this, the policy gradient algorithm for each user queue is executed, until the performance cost of network system is minimized.


## 3.1. Problem Formulation and Optimality Criterion

Since we focus on the stochastic dynamic queueing system, the estimation of its statistical properties is essential. In addition, such estimation needs not only to be accurate but more importantly, to be efficient when taking into consideration the delay sensitiveness of the real-time network applications. Consider that the main tenet of perturbation analysis (PA) is that a great deal of information is contained in the sample paths of a dynamic system, beyond the usual statistics collected such as the means and variances of various variables [15]. Thus, in essence, we can estimate the performance gradient with respect to the service rates and further minimize the user queue's performance cost measure based on a single sample path with PA.In particular, several PA approaches have been introduced in solving network problems (see, e.g., [16, 17]). However, a general approach that supports a wide range of stochastic optimization problems awaits to be proposed. A new approach was proposed in [18] to analyze a number of Markov systems based on a single sample path. Moreover, the optimization formulations for Markov [14, 19, 20], semi-Markov [21], and partially observable Markov [22] systems were proposed, and in [3], the theory has successfully been extended to evaluate the M/G/1 queueing systems. The structure of PA-based queueing system is shown in Figure 2. For each feasible resource allocation policy, a set of service rates are allocated to each user queue. With each change of one user queue's service rate, a perturbation is generated on the queue's sample path, which has effect on the system performance cost.Figure 2
Structure of user queueing system with PA.As illustrated in Figure3, in an M/G/1-type user queue {Ymi;m=0,1,2,…}, such a perturbation can be regarded as a “jump” among its states k∈Φ and has effect on the performance cost ηfμi. Thus, we need to measure all states' effect on the performance cost ηfμi before discussing the performance cost optimization. We briefly introduce a concept called performance potential that is useful in this paper [18].Figure 3
A perturbation of a single sample path.Definition 3.1 (performance potential).
Denotegμi(k) as the ith user queue's performance potential of state k∈Φ under service rates μi with respect to the performance cost function fi. It measures the effect of state k to the performance cost ηfμi and can be written as
(3.1)gμi(k)=E{∑n=0∞[fi(Ymi,μi)-ηfμi]∣Y0i=k}.Remark 3.2.
The performance potential vector of theM/G/1/K user queue {Ymi} with respect to the performance cost function fμi is denoted as gμi=(gμi(0),…,gμi(K))T. In essence, the performance potential vector is the solution of the Poisson equation, which has been studied remarkably in the literature [23]:
(3.2)Aμigμi=-fμi+ηfμie.
Furthermore, if {Ymi} is strongly ergodic, all of the performance potential vectors can be calculated by gμi=-(Aμi)#fμi+ce,c∈ℛ, where (Aμi)# is said to be the group inverse (for details, see [18]) of the {Ymi}'s infinitesimal generator Aμi under service rates μi.Now, we need to assign the feasible service rates region to each active user queue. It is well-studied from queueing theory that anM/G/1-type user queue {Ymi;m=0,1,2,…} is called stable if ρi<1, that is, λi<μi. Moreover, the network element is stable if and only if all individual user queues are stable. Suppose that the lower bound service rates of each user queue at epoch t≥0 are set to μimin(t)=λi+1, and ∑i=1N(t)μimin(t)<Cι. Thus, we denote the leftover service capacity as Co(t)≜Cι-∑i=1N(t)μimin(t). In this state, we further assign the ith user queue a parameter called sharing weight(3.3)ϕi(t)≜λi∑i=1N(t)λi.
Apparently, we have ∑i=1N(t)ϕi(t)=1 for any given t. Thus, at epoch t, the service rates of user queue i are upper bounded by,(3.4)μimax(t)=μimin(t)+ϕi(t)Co(t).
Therefore, the service rates policy space in Figure 2 is defined as follows.Definition 3.3 (feasible policy space).
The policy space for all user queues at epocht≥0 can be denoted as a compact set Ω(t), where Ω(t)≜Γ1(t)×⋯×ΓN(t)(t), and Γi(t)≜[μimin(t),μimax(t)],i∈{1···N(t)}.Next, we analyze the optimal criterion for the performance cost optimization.Theorem 3.4 (optimality criterion).
A cost-benefit resource allocation policyν*(t)≜(μ1*(t),…,μN(t)*(t))∈Ω(t) is optimal with each given initial policy if and only if for each user queue i, one has
(3.5)χi≜minimizeμi(t)∈Γi(t){fμi(t)+Aμi(t)gμi*(t)-eηfμi*(t)}=0,∀i∈{1,…,N(t)}.Proof.
Note thatΓi(t) is a compact set, and fμi(t)+Aμi(t)gμi(t) is component-wise continuous on Γi(t). Thus, there must exist at least one cost optimal service rates in Γi(t).
According to [20], we have the fact that the service rates  μi*(t) for ith user queue is cost optimal if and only if(3.6)fμi*(t)+Aμi*(t)gμi*(t)⪯fμi(t)+Aμi(t)gμi*(t),∀μi(t)∈Γi(t),
where the symbol ⪯ denotes vector inequality or component-wise inequality in ℛ(K+1), and (K+1) is the the states' number of each user queue.
Note that a better cost-benefit service rates can be searched based on the comparison of current service rate. Besides, from (3.2), we have eηfμi*(t)=fμi*(t)+Aμi*(t)gμi*(t).
Thus, we can conclude that if theμi*(t) is the cost optimal service rates, the following equation:(3.7)χi=minimizeμi(t)∈Γi(t){fμi(t)+Aμi(t)gμi*(t)-eηfμi*(t)}=0
is established and vice versa.


## 3.2. Gradient-Based Policy Optimization

Now, the purpose is to develop an efficient and practical policy algorithm, which minimizes all the user queues' performance cost based on the corresponding sample paths. In essence, the objective function for each user queue in Definition2.5 represents the time-average performance measure of the M/G/1 queue. Thus, developing a global optimization algorithm for such a performance measure will greatly increase the complexity. More importantly, to some extent, it is impractical to consider both the delay sensitiveness of user applications and the dynamic changes of the network element. In this state, a fast gradient-based optimization for the stochastic system is considered. It is well studied that a gradient optimization algorithm is to find a local minimum of objective function; however, it can be fairly efficient, especially when the interval Γi(t) for each user queue i is not very large. To begin with, the performance gradient formula for each user queue is derived as follows.Theorem 3.5 (performance gradient).
For any given resource allocation policyν(t)=(μ1(t),…,μN(t)(t))∈Ω(t) at each event time t≥0,k=1,2,…, the gradient of the performance cost ηfμi(t) generated by the ith user queue is obtained by
(3.8)∇ηfμi(t)=πμi(t)∇Pμi(t)gfμi(t)+πμi(t)∇fμi(t).Proof.
By taking the gradient of the performance measure (2.8), we have
(3.9)∇ηfμi(t)=∇πμi(t)fμi(t)+πμi(t)∇fμi(t).
From [14, 20], there must be particular solution to (3.2), such that ηfμi(t)=πμi(t)gμi(t); thus, we obtain
(3.10)(-Aμi(t)+eπμi(t))gμi(t)=fμi(t).
With Pμi(t)=Aμi(t)+I, we further have
(3.11)(I-Pμi(t)+eπμi(t))gμi(t)=fμi(t).
Left-multiply by ∇πμi(t) on both sides of (3.11), it follows that
(3.12)∇πμi(t)fμi(t)=∇πμi(t)(I-Pμi(t)+eπμi(t))gμi(t).
Recall that πμi(t)e=1,Pμi(t)e=e,andπμi(t)Pμi(t)=πμi(t), then we have
(3.13)∇πμi(t)Pμi(t)+πμi(t)∇Pμi(t)=∇πμi(t),∇πμi(t)e=0.
Hence, using (3.12), it suffices to show that
(3.14)∇πμi(t)fμi(t)=πμi(t)∇Pμi(t)gμi(t).
Combining (3.9) with (3.14), the result then follows.Then, we proceed to describe the process flow of thepolicy gradient algorithm shown in Figure 4. The procedure of the algorithm is described in Algorithm 1. Note that in Algorithm 1,(3.15)sp(h)≜maxi{h(i)}-mini{h(i)},h∈ℛn
is defined as the span seminorm on ℛn.Algorithm 1:Policy gradient algorithm.
Input: An arbitrary initial policy ν(t)=(μ1(t),…,μN(t)(t))∈Ω(t) at given t≥0.Output: The optimal policy for all user queues ν*(t)=(μ1*(t),…,μN(t)*(t))∈Ω(t).Procedure:(1) Choose 0<ϵ≪1 as the stopping criterion for all user queues.(2) for  queue i=1 to N(t)  do(3)  repeat(4)   Set iteration index l=0.(5)   Calculate πμil(t) and gμil(t) by solving (2.6) and (3.2), respectively.(6)   Determine the gradient such that:∇ηfμil(t)=πμil(t)∇Pμil(t)gμil(t)+πμil(t)∇fμil(t).(7)   Do line search along the gradient, choose the right step size γil.(8)   Update service rates μil+1(t):=μil(t)-γil∇ηfμil(t).(9)   Set l:=l+1.(10)  Until  sp(fμil+1(t)+Aμil+1(t)gμil(t))<ϵ  or  μil+1(t)∉Γi(t).(11) end  forFigure 4
Policy gradient algorithm procedure.Moreover, the construction of the algorithm is presented as follows. The algorithm begins by choosing an arbitrary feasible policy for all user queues at given timet. Then, with current service rates, the corresponding performance gradient is calculated by analyzing the sample path of each user queue. Based on the line search along the gradient, the right step size is obtained. Thus, a better policy can be updated for each user queue. By iteration until the stopping criterion is met, the optimal cost-benefit resource allocation policy can finally be achieved.Without loss of generality, suppose that every gradient iteration of each user queue leads to an improving performance cost, that is,(3.16)fμil+1(t)+Aμil+1(t)gμil(t)⪯fμil(t)+Aμil(t)gμil(t),∀i∈{1,…,N(t)},
where l∈𝒵+ represents the iteration index in Algorithm 1. The convergence property of the policy gradient algorithm is evaluated as follows.Theorem 3.6 (convergence property).
Considerνl(t)=(μ1l(t),…,μN(t)l(t))∈Ω(t),l∈𝒵+ is a performance improving resource allocation policy sequence at each given time t≥0, then foralli∈{1,…,N(t)}; one has:(a)
(3.17)liml→∞sp(fμil+1(t)+Aμil+1(t)gμil(t))=0,(b)
That there must exist an optimal cost-benefit resource allocation policy, denoted asν*(t)=(μ1*(t),…,μN(t)*(t))∈Ω(t), such that
(3.18)liml→∞μil(t)=μi*(t),liml→∞ηfμil(t)=ηfμi*(t).Proof.
For part (a) Sinceνl(t)=(μ1l(t),…,μN(t)l(t))∈Ω(t),l∈𝒵+,i∈{1,…,N(t)} is a performance improving resource allocation policy sequence, we can conclude that for each user queue i, {ηfμil(t)} is a monotonously decreasing and bounded performance cost sequence, with lower bound ηfμi*(t).
By using the continuity ofηfμi(t), we obtain a service rates μi(t)∈Γi(t) for each user queue i, satisfying ηfμi(t)=c∈ℛ+ and liml→∞μil(t)=μi(t).
Thus, it follows that(3.19)liml→∞(fμil+1(t)+Aμil+1(t)gμil(t))=fμi(t)+Aμi(t)gμi(t)=eηfμi(t),
which is equivalent to
(3.20)liml→∞{(fμil+1(t)+Aμil+1(t)gμil(t))(k)}=ηfμi(t),∀k∈Φ.
Recall that(3.21)sp(fμil+1(t)+Aμil+1(t)gμil(t))=maxk∈Φ{(fμil+1(t)+Aμil+1(t)gμil(t))(k)}-mink∈Φ{(fμil+1(t)+Aμil+1(t)gμil(t))(k)};
by taking limit as l→∞, we further have
(3.22)liml→∞sp(fμil+1(t)+Aμil+1(t)gμil(t))=ηfμi(t)-ηfμi(t)=0.
For part (b) Note that forallϵ>0,∃l0∈𝒵+, such that sp(fμil+1(t)+Aμil+1(t)gμil(t))<ϵ,holds when l>l0.
To show the second relation of the theorem, consideringl>l0; it follows that(3.23)ηfμil+1(t)=πμil+1(t)fμil+1(t)=πμil+1(t)(fμil+1(t)+Aμil+1(t)gμil(t))≤maxk∈Φ{(fμil+1(t)+Aμil+1(t)gμil(t))(k)}.
Since in Algorithm1, μil+1(t) is the best choice for μil(t) along the gradient by the line search, we therefore have(3.24)ηfμi*(t)=πμi*(t)(fμi*(t)+Aμi*(t)gμil(t))≥πμi*(t)(fμil+1(t)+Aμil+1(t)gμil(t))≥mink∈Φ{(fμil+1(t)+Aμil+1(t)gμil(t))(k)}.
Subtracting (3.23) by (3.24), for ∀l>l0, it follows that(3.25)0<ηfμil+1(t)-ηfμi*(t)≤sp(fμil+1(t)+Aμil+1(t)gμil(t))<ϵ.
Thus, it can be regarded thatμil+1(t) is an ϵ-optimal service rates, and we can write liml→∞ηfμil+1(t)=ηfμi*(t) by the arbitrariness of ϵ.
Finally, from the fundamental fact of the uniqueness principle of limitation theory, we can conclude thatηfμi*(t)=ηfμi(t), which is equivalent to say that μi(t) is an optimal cost-benefit service rates. This leads immediately to the results that liml→∞μil(t)=μi*(t) and liml→∞ηfμil(t)=ηfμi*(t).Remark 3.7.
By proving the convergence property of the policy gradient algorithm, the cost-benefit resource allocation optimization approach for theM/G/1/K user queues has been proposed. In a broad sense, the service time allocated to each user queue i has been considered as a general distribution Gi. However, the mathematical expression of performance gradient is not unique according to different application scenarios.


## 3.3. Performance Gradient Analysis of Application Scenarios

To make the analysis more tractable, we now present two application scenarios for which the performance gradient can be explicitly derived.Deterministic inter-service time.
This is the simplest practical case where inter-service times for each user queuei are deterministic, that is, M/D/1/K. Without loss of generality, we denote each inter-service time as a constant 1/μi. Consider now that  ρi=λi/μi<1. Let Pμi be the transfer matrix of the embedded Markov chain. In this scenario, hence, we have that for all k∈Φ, the element aki of the transfer matrix is equal to,
(3.26)aki=e-ρiρikk!,
implying that the element of steady-state probability vector πμi(k),k∈Φ satisfies
(3.27)πμi(k)={1-ρi,ifk=0,(1-ρi)(eρi-1),ifk=1,(1-ρi)∑j=1k(-1)k-je-jρi[(jρi)k-j(k-j)!+(jρi)k-j-1(k-j-1)!],otherwise.
According to (3.26), hence, we have
(3.28)∂aki∂μi={λiμi2e-ρi=ρiμiaki,ifk=0,λie-ρiμi2[ρikk!-ρik-1k-1!]=ρiμi(aki-ak-1i),otherwise.Corollary 3.8.
Considering theith user queue in the steady state, from Theorem 3.5, the performance gradient with respect to the service rates μi for the case of M/D/1/K is(3.29)∂ηfμi∂μi=ρiμi∑k=0K[πμi(k)-πμi(k-1)]gμi(k)+πμi∂f∂μi,
where πμi=(πμi(0),…,πμi(K)),gμi=(gμi(0),…,gμi(K)), and πμi(-1)=0.Exponential inter-service time.
Having considered the straightforward scenario of deterministic service rates, we will now investigate theM/M/1/K case where the inter-service times are independent and exponentially distributed, that is, memoryless. For ease of notation, we show results using the same parameters as in the first scenario. Similarly, in this case, we derive the element aki,forallk∈Φ of the transfer matrix as follows:
(3.30)aki=ρik(1+ρi)k+1;
it  suffices to show that,
(3.31)πμi(k)=(1-ρi)ρik,∂aki∂μi=ρi-kμi(1+ρi)aki.Corollary 3.9.
Considering theith user queue in the steadystate, from Theorem 3.5, the performance gradient with respect to the service rates μi for the case of M/M/1/K is
(3.32)∂ηfμi∂μi=πμi∂f∂μi-∑k=0Kbkigμi(k),
where
(3.33)bki=πi(0)k-ρi1+ρiaki+∑j=0kπi(j+1)k-j-ρi1+ρiak-ji.Remark 3.10.
Note that the essential feature behind the cost-benefit resource allocation is the performance gradient corresponding to the service rates. Based on this, the policy gradient algorithm for each user queue is executed, until the performance cost of network system is minimized.


## 4. Performance Evaluation

In this section, we investigate the performance of theM/G/1-type queueing system. Before proceeding, we first present the simulation model, namely, the sample path-based simulation scheme.


### 4.1. Simulation Model

To evaluate the performance of Algorithm1 for each user queue i, it is imperative to calculate both the steady-state probability vector πμil(t) and the performance potential gμil(t) with any feasible service rates μil(t) in every iteration l=0,1,2,….According to the Borel property [24], the steady-state probability of state k in the embedded Markov chain Ymi has an unbiased estimate as follows:(4.1)πμî(k)=1ζ∑n=0ζ-1Ik(Ymi)∀k∈Φ,
where(4.2)Ik(Ymi)≜{1,Ymi=k,0,Ymi≠k,
and ζ denotes the transfer number of the queue states and is set to 10000 in this simulation. Once the steady-state probability vector has been estimated, the estimation of the performance cost ηfμî for the user queue can be derived by ηfμî=πμîfμi.However, solving the Poisson equation in (3.2) for achieving gμil(t) leads to significant computational complexity, which is impractical for the online cost-benefit optimization. Therefore, a sample path-based estimation is very essential. Note that the performance potential can be estimated as(4.3)gμî=-DfμîπμîT,
where Dfμî=[dkjμî][(K+1)×(K+1)],k,j∈Φ is called the realization matrix, and(4.4)dkjμî≜E{∑n=0L{k∣j}-1[fi(Ymi,μi)-ηfμî]∣Y0i=j},
the first passage time L{k∣j} from state j to state k, is expressed as L{k∣j}≜inf{n≥0:Ymi=k∣Y0i=j}.Thus by Theorem3.5, the gradient corresponding to the service rates μil(t) allocated in the lth iteration for the user queue i can be efficiently estimated by(4.5)∇η̂fμil(t)=π̂μil(t)∇Pμil(t)ĝμil(t)+π̂μil(t)∇fμil(t).


### 4.2. Numerical Results

The following describes numerical examples to illustrate the analytical results derived in the previous sections. Consider a given timet0>0 and that there are four active user queues in the network element. Here, we limit our experimental tests to the simulation parameters values that are depicted in Table 2. Note that the value of λi(t0), μimin(t0), and μimax(t0) can be considered as packet numbers transmitted per unit time.Table 2
Simulation Parameters.
Parameters (i=1,2,3,4)λi(t0)μimin(t0)ϕi(t0)μimax(t0)User queue 115160.1734.7User queue 220210.2245.2User queue 325260.2856.8User queue 430310.3367.3Besides, the backlog capacity of every user queue is set to 100 packets. The performance cost function of the sharing user queues is considered asfi(k,μi)=c1k+c2μi,i=1,2,3,4,k∈Φ, where c1,c2>0 are constants. In this experiment, they are set to 80 and 1, respectively. Moreover, the stopping criterion ϵ in Algorithm 1 is set to 0.001, and the link service capacity Cι is set to 200 packets per unit time. By choosing the initial resource allocation policy as the minimum service rates for all user queues, the simulation results are described in Table 3. Finally, the iteration processes of the four user queues are shown in Figure 5.Table 3
Optimal resource allocation policy.
IndexUser queue 1User queue 2User queue 3User queue 4Optimal service rates32.357137.820339.424640.6496Optimal performance cost45.337750.101555.856164.9322Iterations891411The iteration processes of the four user queues.
(a)(b)(c)(d)Based on the observation on Figure5, we can conclude the following. (i)
Given the the stopping criterionϵ=0.001 and each feasible region Γi(t0),i∈{1,…,N(t0)}, all iterations for user queues can converge within 15 steps.(ii)
During the algorithm iterative process, the corresponding performance cost has been reduced by56.3%,55.7%,52.3%, and 44.5%, respectively for each user queue.(iii)
The optimal service rates for each user queue (e.g.,μ1*(t0)) may not be achieved on the boundary (i.e., μ1min(t0) or μ1max(t0)) of the feasible region shown in Table 2.Remark 4.1.
Note that the convergence rate of the proposed algorithm is closely related with the estimation of theperformance gradients. The convergence rate of the algorithm will grow faster with a more accurate estimation. More precisely, according to Theorem3.5, the performance gradient can be calculated via the steady-state probability vector πμil(t) and the performance potential gμil(t) in every iteration l∈𝒵+. Thus, we can increase the number of queue states' transfers, thereby achieving the estimation accuracy of steady-state probability vector and performance potential, or equivalently, performance gradient. In addition, the reason for the location of the optimal service rates is that there exists a trade-off between the backlog-related and service rate-related performance cost, which can be adjusted by the definition of the performance cost function.


## 4.1. Simulation Model

To evaluate the performance of Algorithm1 for each user queue i, it is imperative to calculate both the steady-state probability vector πμil(t) and the performance potential gμil(t) with any feasible service rates μil(t) in every iteration l=0,1,2,….According to the Borel property [24], the steady-state probability of state k in the embedded Markov chain Ymi has an unbiased estimate as follows:(4.1)πμî(k)=1ζ∑n=0ζ-1Ik(Ymi)∀k∈Φ,
where(4.2)Ik(Ymi)≜{1,Ymi=k,0,Ymi≠k,
and ζ denotes the transfer number of the queue states and is set to 10000 in this simulation. Once the steady-state probability vector has been estimated, the estimation of the performance cost ηfμî for the user queue can be derived by ηfμî=πμîfμi.However, solving the Poisson equation in (3.2) for achieving gμil(t) leads to significant computational complexity, which is impractical for the online cost-benefit optimization. Therefore, a sample path-based estimation is very essential. Note that the performance potential can be estimated as(4.3)gμî=-DfμîπμîT,
where Dfμî=[dkjμî][(K+1)×(K+1)],k,j∈Φ is called the realization matrix, and(4.4)dkjμî≜E{∑n=0L{k∣j}-1[fi(Ymi,μi)-ηfμî]∣Y0i=j},
the first passage time L{k∣j} from state j to state k, is expressed as L{k∣j}≜inf{n≥0:Ymi=k∣Y0i=j}.Thus by Theorem3.5, the gradient corresponding to the service rates μil(t) allocated in the lth iteration for the user queue i can be efficiently estimated by(4.5)∇η̂fμil(t)=π̂μil(t)∇Pμil(t)ĝμil(t)+π̂μil(t)∇fμil(t).


## 4.2. Numerical Results

The following describes numerical examples to illustrate the analytical results derived in the previous sections. Consider a given timet0>0 and that there are four active user queues in the network element. Here, we limit our experimental tests to the simulation parameters values that are depicted in Table 2. Note that the value of λi(t0), μimin(t0), and μimax(t0) can be considered as packet numbers transmitted per unit time.Table 2
Simulation Parameters.
Parameters (i=1,2,3,4)λi(t0)μimin(t0)ϕi(t0)μimax(t0)User queue 115160.1734.7User queue 220210.2245.2User queue 325260.2856.8User queue 430310.3367.3Besides, the backlog capacity of every user queue is set to 100 packets. The performance cost function of the sharing user queues is considered asfi(k,μi)=c1k+c2μi,i=1,2,3,4,k∈Φ, where c1,c2>0 are constants. In this experiment, they are set to 80 and 1, respectively. Moreover, the stopping criterion ϵ in Algorithm 1 is set to 0.001, and the link service capacity Cι is set to 200 packets per unit time. By choosing the initial resource allocation policy as the minimum service rates for all user queues, the simulation results are described in Table 3. Finally, the iteration processes of the four user queues are shown in Figure 5.Table 3
Optimal resource allocation policy.
IndexUser queue 1User queue 2User queue 3User queue 4Optimal service rates32.357137.820339.424640.6496Optimal performance cost45.337750.101555.856164.9322Iterations891411The iteration processes of the four user queues.
(a)(b)(c)(d)Based on the observation on Figure5, we can conclude the following. (i)
Given the the stopping criterionϵ=0.001 and each feasible region Γi(t0),i∈{1,…,N(t0)}, all iterations for user queues can converge within 15 steps.(ii)
During the algorithm iterative process, the corresponding performance cost has been reduced by56.3%,55.7%,52.3%, and 44.5%, respectively for each user queue.(iii)
The optimal service rates for each user queue (e.g.,μ1*(t0)) may not be achieved on the boundary (i.e., μ1min(t0) or μ1max(t0)) of the feasible region shown in Table 2.Remark 4.1.
Note that the convergence rate of the proposed algorithm is closely related with the estimation of theperformance gradients. The convergence rate of the algorithm will grow faster with a more accurate estimation. More precisely, according to Theorem3.5, the performance gradient can be calculated via the steady-state probability vector πμil(t) and the performance potential gμil(t) in every iteration l∈𝒵+. Thus, we can increase the number of queue states' transfers, thereby achieving the estimation accuracy of steady-state probability vector and performance potential, or equivalently, performance gradient. In addition, the reason for the location of the optimal service rates is that there exists a trade-off between the backlog-related and service rate-related performance cost, which can be adjusted by the definition of the performance cost function.


## 5. Conclusions

In this paper, performance optimization problems of communication networks with stochastic characteristics are studied. To describe this complex dynamic process of system behavior, all user queues in each network element are represented by multiple concurrentM/G/1-type Markov processes such that system model is proposed. Furthermore, an efficient algorithm is developed for the optimization of system performance cost by using sensitivity analysis approach. During every iteration, the proposed algorithm estimates the derivative of the performance measure and the performance potential by analyzing a single sample path of each user queue, which implies its computational efficiency. The asymptotical convergence analysis, combined with the numerical examples, paves the way for designing cost-aware computer communications systems.



---

*Source: 130319-2010-08-09.xml*