Bounds on accuracy when estimating the loss probability in a packet buffer

In this paper, we present a new approach to computing the lower bound on the measurement of buffer overflow probability, when the buffer state is modeled as a semi-Markov process. In this commonly assumed model of buffer overflow we use this approach to explore the relationship between sampling rate and accuracy. Crucially we go on to show that a realistic simulation of a packet buffer reveals that the distribution of buffer overflow periods is not always such as to allow simple Markov modeling of the buffer state; while the sojourn periods are exponential for the smaller burst periods, the tail of the distribution follows a power law (in effect following a power law for the extreme values). While our work validates the use of a two state Markov model for a useful approximation modeling the overflow of a buffer, we have established that earlier work which relies on simple Markovian assumptions will thereby underestimate the error in the measured overflow probabilities.