A Min-Plus System Theory for Constrained Traffic Regulation and Dynamic Service Guarantees

By extending the system theory under the (min,+)-algebra to the time varying setting, we solve the problem of constrained traffic regulation and develop a calculus for dynamic service guarantees. For a constrained traffic regulation problem with maximum tolerable delay d and maximum buffer size q, the optimal regulator that generates the output traffic conforming to a subadditive envelope f and minimizes the number of discarded packets is a concatenation of the g-clipper with g(t) = min[f(t+d), f(t)+q] and the maximal f-regulator. The g-clipper is a bufferless device which optimally drops packets as necessary in order that its output be conformant to an envelope g. The maximal f-regulator is a {\em buffered} device that delays packets as necessary in order that its output be conformant to an envelope f. The maximal f-regulator is a linear time invariant filter with impulse response f, under the (min +)-algebra. To provide dynamic service guarantees in a network, we develop the concept of a dynamic server as a basic network element. Dynamic servers can be joined by concatenation, ``filter bank summation,'' and feedback to form a composite dynamic server. We also show that dynamic service guarantees for multiple input streams sharing a work conserving link can be achieved by a dynamic SCED (Service Curve Earliest Deadline) scheduling algorithm, if an appropriate admission control is enforced. To model more general network elements, such as routers and packetizers, we extend the time varying system theory to a general system theory, where the mapping from the input to the output is required to be sigma-additive under the (min,+)-algebra. Analogous to dynamic servers, network elements with the sigma-additive property can also be joined by concatenation, ``filter bank summation,'' and feedback to form a composite network element