Accelerated simulation of a leaky bucket controller.

Abstract

The leaky bucket controller has been proposed to shape traffic entering an ATM network. Cells arrive at the leaky bucket controller according to a superposition of a group of heterogeneous Markov modulated sources (modeled by a multidimensional Markov process). The bucket capacity is L tokens. Every time slot the bucket leaks s tokens. If a cell arrives I tokens are added to the bucket unless it overflows. A cells producing an overflow is marked nonconforming and no tokens are added. The proportion of nonconforming cells and the mean time between nonconforming cells are significant for evaluating the performance of the leaky bucket. Such parameters can be approximated by developing a change of measure to transform a recurrent process into a transient one. For this twisted process, the event until overflow is no longer a rare event and can be simulated efficiently. We can now give a formula for calculating the proportion of cells which are nonconforming as well as the mean time between bursts of nonconforming cells.