Stochastic Upper and Lower Bounds for General Markov Fluids

Promising perspectives of a hypothetical 'Tactile Internet', or 'Internet at the speed of light', whereby network latencies become imperceptible to users, have (again) triggered a broad interest to understand and mitigate Internet latencies. In this paper we revisit the queueing analysis of the versatile Markov Fluid traffic model, which was mainly investigated in the 1980-90s, yet with low accuracy. We derive upper bounds on the tail distribution of the queue size, which improve state-of-the-art results by an exponential factor O(kappa(n)) in a special case, where 0 < kappa < 1 and n is the number of multiplexed sources; additionally, we provide the first lower bounds. The underlying results are quite general in that they can be easily adapted to derive the delay distribution for SP, FIFO, and EDF scheduling. Our overall results rely on a powerful martingale methodology which was recently shown to be highly accurate.