Relationship Between Perturbation Realization Factors With Queueing Models and Markov Models

Perturbation realization factor is an important concept in perturbation analysis of both queueing systems and Markov systems. A perturbation realization factor measures the effect of a perturbation on the system performance. This concept is important for the performance sensitivity and performance optimization of these systems. Since the perturbations in queueing systems are continuous in nature and those in Markov systems are discrete, it is not straightforward to establish the relationship between these two types of fundamental concepts. This note solves this long-standing problem. We find a formula that links these two types of perturbation realization factors in Gordon-Newell and open Jackson networks together. The results enhance our understanding of perturbation analysis and lead to new research directions.     

Full-state perturbation analysis of discrete event dynamic systems

Discrete event dynamic systems are studied within the framework of perturbation analysis in this paper. Perturbation is extended from the event times only to both event times and queue lengths. An approximate technique, full-state perturbation analysis (PA), is developed as an extension of the PA approach. Full-state PA is able to deal with problems involving queue length perturbations which often defy existing PA methods, while it still retains all the advantages of existing PA. Full-state PA is used to calculate the throughput sensitivity to the number of customers in closed queueing networks and the throughput sensitivity to routing change. Numerical examples are given. Experimental results verify the validity and accuracy.This work is supported in part by the National High Technology Project and by Southeast University Research Funds for Young Teachers.     

First and Second Derivative Estimators for Closed Jackson-Like Queueing Networks Using Perturbation Analysis Techniques

We consider a closed Jackson—like queueing network with arbitrary service time distributions and derive an unbiased second derivative estimator of the throughput over N customers served at some node with respect to a parameter of the service distribution at that node. Our approach is based on observing a single sample path of this system, and evaluating all second-order effects on interdeparture times as a result of the parameter perturbation. We then define an estimator as a conditional expectation over appropriate observable quantities, as in Smoothed Perturbation Analysis (SPA). This process recovers the first derivative estimator along the way (which can also be derived using other techniques), and gives new insights into event order change phenomena which are of higher order, and on the type of sample path information we need to condition on for higher-order derivative estimation. Despite the complexity of the analysis, the final algorithm we obtain is relatively simple. Our estimators can be used in conjunction with other techniques to obtain rational approximations of the entire throughput response surface as a function of system parameters.     

New performance sensitivity formulae for a class of product-form queueing networks

Perturbation analysis (PA) applies a dynamic point of view to the sample paths of stochastic systems; the realization factor, one of the main concepts of PA, measures the final effect of a perturbation on system performance and provides a novel approach in obtaining performance sensitivities. In this paper, we solve analytically the set of equations for realization factors of a two-server cyclic network. We prove an invariance property of the performance sensitivity for Norton's aggregation. Using the results, we derive closed-form formulae for the derivatives of performance measures in a closed queueing network with load-dependent exponential servers. The performance measures have two general forms: customer average and time average. In contrast with the usual approach based on product-form solutions, our results provide additional insights into the performance sensitivity of closed queueing networks and have immediate applications to problems of optimal control. The general formulae are expressed in terms of Buzen's algorithm with a computational complexity comparable to that of the formulae obtained by directly taking the derivatives of the product-form solutions.     

关于加工生产线的一种新的模型及其扰动分析

本文首先建立在实际生产中应用较广的串联生产线和装配生产线的新的代数摸型(在新 韵代数系下).基于这类模型,在扰动幅度大小没有任何限制的情况下,对平均服务时间的扰 动,建立扰动传播的数学方程,给出系统输出率对平均服务时间的灵敏度公式.仿真结果验证 了理论分析结果,其精度令人满意.     

First-order perturbation analysis of a simple multi-class finite source queue

Perturbation analysis is an efficient method to compute parameter sensitivities for discrete event systems. This paper considers a simple multi-class finite source queue which models a computer system with multi-type programs. It is shown that first-order analysis is needed. Detailed discussions on the example system reveal the main features of multi-class queueing networks. An algorithm based on first-order analysis is proposed. This algorithm yields an asymptotically unbiased estimate of the sensitivity for the example system based on only one sample path of the system. The accuracy of first-order perturbation analysis for general queueing networks is also discussed.     

The potential structure of sample paths and performance sensitivities of Markov systems

We study the structure of sample paths of Markov systems by using performance potentials as the fundamental units. With a sample path-based approach, we show that performance sensitivity formulas (performance gradients and performance differences) of Markov systems can be constructed intuitively, by first principles, with performance potentials (or equivalently, perturbation realization factors) as building blocks. In particular, we derive sensitivity formulas for two Markov chains with possibly different state spaces. The proposed approach can be used to obtain flexibly the sensitivity formulas for a wide range of problems, including those with partial information. These formulas are the basis for performance optimization of discrete event dynamic systems, including perturbation analysis, Markov decision processes, and reinforcement learning. The approach thus provides insight on on-line learning and performance optimization and opens up new research directions. Sample path based algorithms can be developed.     

闭排队网络当性能函数与参数相关时的性能灵敏度分析

借助于无穷小矩阵摄动方法, 讨论了一类Markov过程, 其稳态性能关于参数摄动的灵敏度分析问题. 然后研究了闭排队网络的稳态性能灵敏度分析问题, 并在参数相关性能函数的情况下, 给出了网络的几种稳态性能的灵敏度公式. 这些公式表明稳态性能灵敏度很容易通过网络势能进行计算.     

Sensitivity analysis and optimization of throughput in a production line with blocking

Production lines with limited storage capacities can be modeled as cyclic queueing networks with finite buffers and general service times. A new technique, called perturbation analysis of discrete event dynamic systems, is applied to these queueing networks. An estimate of the gradient of the system throughput is obtained by perturbation analysis based on only one sample trajectory of the system. We show that the estimate is strongly consistent. Using this perturbation analysis estimate of gradient, we can apply the Robbins-Monro stochastic procedure in optimizing the system throughput. Compared to the conventional Kiefer-Wolfowitz optimization procedure, this approach saves a large amount of computation. For a real system, the gradient estimate can be obtained without changing any parameters in the system. The results also hold for systems with general routing but in which no server can block more than one other server simultaneously.     

Sensitivity formulas of performance in two-server cyclic queueing networks with phase-type distributed service times

With the approach of the infinitesimal generator perturbation, sensitivities of the steady-state performance are studied in two-server cyclic queueing networks with phase-type distributed service times. Sensitivity formulas expressed by the potentials of the networks are given for parameter-dependent performance functions. An algorithm to compute the potentials and the performance derivatives of the networks is given, and a numerical example is provided.     

Perturbation analysis of a multiclass queueing system withadmission control

A service facility with multiple customer classes is considered. Each class forms an independent Poisson arrival process with admission controlled by a threshold parameter and is characterized by a general service time distribution. Gradient estimators are derived for performance measures of the system (mean system time, throughput, blocking probabilities) using perturbation analysis techniques. The approach is based on exploiting alternative sample path representations of generalized semi-Markov process models of the system, such that the resulting sample functions are continuous with respect to parameters of interest. The unbiasedness of the estimators is proved. Simulation examples are included to illustrate their properties     

New perturbation–iteration solutions for Bratu-type equations

Perturbation–iteration theory is systematically generated for both linear and nonlinear second-order differential equations and applied to Bratu-type equations. Different perturbation–iteration algorithms depending upon the number of Taylor expansion terms are proposed. Using the iteration formulas derived using different perturbation–iteration algorithms, new solutions of Bratu-type equations are obtained. Solutions constructed using different perturbation–iteration algorithms are contrasted with each other as well as with numerical solutions. It is found that algorithms with more Taylor series expansion terms yield more accurate results.     

A Near-Optimal Optimization Algorithm for Link Assignment in Wireless Ad-Hoc Networks

Over the past few years, wireless networking technologies have made vast forays in our daily lives. In wireless ad-hoc networks, links are set up by a number of units without any permanent infrastructures. In this paper, the resource optimization is considered to maximize the network throughput by efficiently using the network capacity, where multi-hop functionality and spatial TDMA （STDMA） access scheme are used. The objective is to find the minimum frame length with given traffic distributions and corresponding routing information. Because of the complex structure of the underlying mathematical problem, previous work and analysis become intractable for networks of realistic sizes. The problem is addressed through mathematical programming approach, the linear integer formulation is developed for optimizing the network throughput, and then the similarity between the original problem and the graph edge coloring problem is shown through the conflict graph concept. A column generation solution is proposed and several enhancements are made in order to fasten its convergence. Numerical results demonstrate that the theoretical limit of the throughput can be efficiently computed for networks of realistic sizes.     

Properties and performance bounds for closed free choicesynchronized monoclass queueing networks

It is shown that many monoclass queuing networks (QN) with synchronizations can naturally be modeled with a subclass of Petri nets (PN) called free-choice nets (FC), for which a wide gamut of qualitative behavioral and structural results have been derived. Some of these net theoretic results are used to characterize the ergodicity, boundedness, and liveness of closed free-choice synchronized QNs. Upper and lower throughput bounds are defined based on the mean value of the service times, without any assumption on the probability distributions (thus including both the deterministic and the stochastic cases). It is shown that monotonicity properties exist between the throughput bounds and the parameters of the model in terms of population and service times. Proposed are (theoretically polynomial and practically linear complexity) algorithms for the computation of these bounds, based on linear programming problems defined on the incidence matrix of the underlying FC net. Using classical laws from queuing theory, bounds are provided for mean queue lengths and response time     

An approximate MVA algorithm for exponential, class-dependent multiple servers

Mean value analysis (MVA) is an efficient algorithm for determining the mean sojourn time, the mean queue length, and the throughput in a closed multiclass queueing network. It provides exact results for the class of product-form networks. Often different classes have different service requirements in FCFS queues, but such networks are not of product form. There are several possibilities to compute performance measure for such nodes and networks. In this paper we present an approximation formula for multiple-server FCFS queues with class-dependent service times as a Norton flow equivalent product node, where the departure rate of any class depends on the number of customers of all classes in the queue. We will use this approximation in the sojourn time formula of some exact and approximate MVA algorithms.     

Probability distribution in varying-structure queueing networks

The paper is devoted to the computation of stationary distributions of queueing systems in random media. Results obtained for considered models follow from a theorem proved in the paper. As an application of the theorem, we consider Jackson networks whose structure (the set of working nodes, service and input flow intensities, routing matrix, state set) and type (open/closed network) varies as the state of another network or of the environment changes. Product-form formulas for the computation of stationary distributions of the considered networks are obtained, and algorithms for the solution of auxiliary problems are developed.     

Probabilistic framework and performance evaluation for prioritized call admission control in next generation networks

Next generation networks (NGN) are designed to support a wide range of applications with various service classes (SCs) guaranteeing the respective quality of service (QoS) levels. Since such networks are resource constrained, call admission control (CAC) is imperative to achieve the required QoS levels. In this paper, a new probabilistic framework for CAC schemes is proposed based on controlling each SC independently by admitting low priority SC calls with a variable imposed probability. The incorporation of such a probabilistic framework is considered under a bandwidth-centric approach named probabilistic bandwidth reservation scheme (PBRS). Though equal service times are usually assumed in the literature, the present analysis considers SCs of different service times. By employing Markov chain analysis to treat the independent SCs that correspond to different call specifications, analytical expressions for the call blocking probabilities (CBPs) are derived. The performance of the proposed CAC scheme is studied not only with regard to CBP but, also, taking into account the priorities assigned to different SCs as well as fairness among various SCs and total network throughput. The proposed probabilistic framework allows the dynamic control of network resources considering also priority assignment, fairness and throughput. Analytical results concerning delay tolerant (DT) and delay-non-tolerant (DNT) traffic have been obtained applying the proposed scheme. Moreover, the relevant simulations have verified the accuracy of the proposed analysis.     

First- and second-derivative estimators for cyclic closed-queueingnetworks

We consider a cyclic closed-queueing network with arbitrary service time distributions and derive first- and second-derivative estimators of some finite horizon performance metrics with respect to a parameter of any one of the service distributions. Our approach is based on observing a single sample path of this system and evaluating first- and second-order effects on departure times as a result of the parameter perturbation. We then define an estimator as a conditional expectation over appropriate observable quantities, using smoothed perturbation analysis techniques. This process recovers the first-derivative estimator along the way and gives new insights into event order change phenomena which are of higher order. Despite the complexity of the analysis, the final algorithms we obtain are relatively simple. Further, we show that our estimators are unbiased and include some numerical examples. We also show the use of our estimators in obtaining approximations of the entire system response surface as a function of system parameters     

Machine allocation algorithms for job shop manufacturing

In this paper we present algorithms for the solution of two server (machine) allocation problems that occur in manufacturing networks. The manufacturing network is modelled as an open network of queues with general interarrival time and service time distributions. The queueing network is analyzed by using the parametric decomposition method: a two-moment approximation scheme. The server allocation problems are solved by means of a marginal analysis scheme. Numerical results on two manufacturing networks are presented.