Extremal shape-controlled traffic patterns in high-speed networks

We consider a variable bit-rate connection with a deterministically shaped random traffic process, as specified by communications networking standards. Regarding randomness, we assume no restricted model other than the natural requirement that the process be stationary and ergodic. Given only the shape parameters, we consider the open problem of determining the maximum service bandwidth required to achieve a given bound on the probability that the packet-transfer delay exceeds a certain threshold. The shape parameters together with a probabilistic bound on the packet-transfer delay define a variable bit-rate “channel”; an equivalent problem is to determine the “capacity” of this channel. To this end, we consider a queue with a constant service rate and a shaped arrival process and obtain tight bounds on queue occupancy and queueing delay. In particular, we describe that traffic pattern (among all stationary-ergodic and deterministically constrained arrival processes) which achieves the probabilistic bound