| This dissertation deals with rare-event simulation (RES) in the context of communications network performance analysis. Although existing RES techniques can provide orders of magnitude speed-up for many interesting cases, these techniques are rather restrictive and, thus, applicable only to systems with modest complexity. Our primary objective in the thesis is to expand the applicability of RES techniques to more complex systems. We start by establishing a novel theoretical model to describe how visiting probabilities of certain state-space regions can be artificially increased in a Markovian system. The theory allows the redistribution of steady-state probabilities in an arbitrary and controlled manner. We desciptively name the theoretical procedure “direct probability redistribution” (DPR).; Based on DPR, we then develop a simulation algorithm that realizes the DPR effect using trajectory splitting. As any splitting technique, DPR-based splitting does not require the knowledge of the transition probability matrix, thus allows for easy application to systems with realistic complexity. Moreover, the main advantage of the DPR-based simulation technique over existing splitting techniques is that DPR does not impose any restrictions on the state transitions and it provides asymptotically unbiased estimates even if the rare event set overlaps many splitting partitions. One of the appealing features of splitting is that for a large class of problems its application is straightforward, requiring very little system-specific knowledge. A few counter-examples, however, already show that for certain types of problems this simplicity does not hold. We introduce several techniques that can help to solve many of these problems. Such techniques include multidimensional splitting, use of indicator queues, and prolonged sub-trajectories.; The second half of the thesis deals with the application of the derived splitting technique to rare-event problems arising in communication networks, including the evaluation of queue length distributions, cell loss probabilities, and delay threshold probabilities in various systems. Many of the provided examples represent (classes of) problems which were either regarded earlier as “unsolvable” by RES means, or for which successful RES solution has not yet been reported in the literature. |
