On deterministic traffic regulation and service guarantees: a systematic approach by filtering

Abstract

We develop a filtering theory for deterministic traffic regulation and service guarantees under the (min, +)-algebra. We show that traffic regulators that generate f-upper constrained outputs can be implemented optimally by a linear time-invariant filter with the impulse response f/sub */ under the (min, +)-algebra, where f/sub */ is the subadditive closure defined in the paper. Analogous to the classical filtering theory, there is an associate calculus, including feedback, concatenation, "filter bank summation", and performance bounds. The calculus is also applicable to the concept of service curves that can be used for deriving deterministic service guarantees. Our filtering approach not only yields easier proofs for more general results than those in the literature, but also allows us to design traffic regulators via systematic methods such as concatenation, filter bank summation, linear system realization, and FIR-IIR realization. We illustrate the use of the theory by considering a window flow control problem and a service curve allocation problem.