Performance sensitivity analysis of open Markovian queueing networks

This paper studies the sensitivity of a class of performance measures in open networks with exponentially distributed service requirements and state-dependent service rates. It derives a set of analytical formulae for the sensitivities of performance with respect to the service rates or the arrival rates. The paper also develops algorithms for estimating these performance sensitivities; the algorithms are based on a single sample path of the network. The approach is based on perturbations analysis (PA). The main concept of PA, the realization factor of a perturbation, is extended to open networks. A set of linear equations specifying the realization factors is derived. The paper shows that, under a mild condition called the quasi-Lipschitz condition, the normalized sensitivity of the steady-state performance with respect to a service rate (or an arrival rate) equals the negative expected value of the realization factor, and that the estimate given by the single-sample-path-based algorithm converges with probability one to the normal sensitivity of the steady-state performance. As an example, the sensitivities of the response time in an M/M/1 queue are studied. The results provide a new analytical method of calculating performance sensitivity and justify the application of PA to open networks.