Performance sensitivity analysis of open Markovian queueing networks

In this paper, we study the sensitivity of a class of performance measures in open networks with exponentially distributed service requirements and state-dependent service rates. We derive a set of analytical formulae for the sensitivities of performance with respect to the service rates or the arrival rates. We also develop algorithms for estimating these performance sensitivities; the algorithms are based on a single sample path of the network. The approach is based on perturbation 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. We show 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 normalized 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.