On the Calculation of Sample-Path Backlog Bounds in Queueing Systems over Finite Time Horizons

The ability to calculate backlog bounds is of key importance for buffer sizing in packet-switched networks. In particular, it is critical to capture the statistical multiplexing gains which, in turn, calls for stochastic backlog bounds. The stochastic network calculus (SNC) is a promising methodology to compute such stochastic backlog bounds. So far in the literature SNC-based backlog bounds apply only to an arbitrary, but fixed single point in time. Yet, from the network engineering perspective, one would rather like to have a sample path backlog bound, i.e., a bound that applies (with a certain fixed violation probability) all of the time. While, in general, such bounds are hard to obtain we investigate in this paper how sample path backlog bounds can be computed over finite time horizons. In particular, we show how a simple extension of the known SNC results can lead to sub-optimal bounds by deriving an alternative methodology (based on extreme value theory) for bounding the backlog over finite time horizons. Interestingly, none of the two methods completely dominates the other. For the new method we also discuss how it can be evolved into a corresponding calculus for network analysis analogous to the existing SNC.