Polynomial biasing importance sampling for Markov fluid models

Importance Sampling is an established technique for the simulation of rare events in Markov fluid systems, a widely used model in the context of high-speed multiservice networks. The main issue with Importance Sampling is the definition of the biasing procedure which strongly affects the effectiveness of the simulation technique. In this paper a biasing procedure is proposed which couples the simplicity of application with a performance close to the optimal procedure. The new procedure, named Polynomial Biasing, relies on a single biasing parameter which is used to alter all the elements of the transition rate matrix of the Markov chain with a polynomial sequence. A one-dimensional minimization algorithm is employed to arrive at the best value of the biasing parameter. Polynomial Biasing provides results identical to the optimal biasing for any superposition of two-state sources. For the general case of multi-state sources its performance, analysed through the comparison with the overflow probability obtained through optimal biasing and the evaluation of the optimality indicator in some numerical examples, results close to the optimal one.