Analysis and efficient simulation of queueing models of telecommunication systems

In modern packet-switched telecommunication systems, information (such as e-mail, sound, pictures) is transported in the form of small packets (or cells) of data through a network of links and routers. The Quality of Service provided by such a network can suffer from phenomena such as loss of packets (due to buffer overflow) and excessive delays. These aspects of the system are adequately described by queueing models, so the study of such models is of great relevance for designing systems such that they provide the required QoS. This thesis contributes methods for the efficient estimation of several loss probabilities in various queueing models of communications systems. The focus is on rare-event simulation using importance sampling, but some analytical, asymptotic and numerical results are also provided. One part of this thesis is concerned with issues related to the estimation of the probability of consecutive (cell) loss: the loss of several consecutive arrivals to a queue. Analytical calculation of this is demonstrated for several simple queues (M/G/1/k and G/M/m/k), and an importance sampling simulation procedure is provided for M/G/1/k queues. Furthermore, an M/M/1/k queue with multiple sources is considered, in which the probability of consecutive (cell) loss incurred by one of these sources is calculated analytically. The other part of this thesis is concerned with the estimation of overflow probabilities in queueing networks. For estimating these probabilities, importance sampling simulation methods are considered, in which several adaptive techniques (mostly based on cross-entropy) are applied to approximate the optimal change of measure. Two classes of change of measure are used: those which do not depend explicitly on the state of the model (e.g., a ``static'' change of the arrival and service rates), and those which do (e.g., changing the arrival and service rates separately for each state). The methods using a state-independent change of measure turn out to be quite effective and to result in an asymptotically efficient simulation in most cases; however, some counterexamples are also observed. With a state-dependent change of measure, an asymptotically efficient simulation is obtained in every example tried, including those for which no good state-independent change of measure is known. The state-dependent method has only been applied to Markovian networks, but possible ways to extend it to non-Markovian networks are briefly discussed. Furthermore, a simple numerical method is proposed for the calculation of overflow probabilities in simple Jackson networks, which is used to verify the correctness of the results from the above simulation methods. In the course of the work on the above two main problems, some interesting subproblems and related issues were investigated. The obtained results are also useful in other contexts, and include the following: (1) asymptotic expressions for the past and remaining service time distributions upon reaching a high (overflow) level in M|G|1 queues; (2) asymptotically efficient importance sampling simulation schemes for the estimation of probabilities of events of the form ni 1 Xi ] Y, where Xi are positive i.i.d. random variables, and Y is also a positive random variable (useful in e.g. reliability models); (3) an extension of the central limit theorem to exponentially tilted random variables (useful for asymptotic efficiency proofs)