Tutorials & Workshops - ACM SIGMETRICS 2000

Deterministic Service Guarantees in Communication Networks

Department of Electrical Engineering
National Tsing Hua University
 

The beauty of the deterministic theory is that it can be generalized and explained systematically by a filtering theory under the min-plus algebra, where one replaces the usual addition by the min operator and the usual multiplication by the addition operator. As in the classical linear system theory, the filtering theory treats an arrival process (or a departure process) as a signal and a network as a system. There are two basic types of network elements: traffic regulators and servers. A traffic regulator, such as a $(\sigma, \rho)$-leaky bucket, performs traffic regulation for an arrival process. A server, such as a GPS server, deliver service guarantees for an departure process. Both traffic regulators and servers can be viewed as linear time invariant filters under the min-plus algebra. They can be joined by concatenation, ``filter bank summation'', and feedback to form a composite network element. Performance guarantees, such as queue length and delay, is then reduced to the problem of finding the impulse response of the composite network element.
 

• ($\sigma , \rho )$-calculus (30 mins): introducing network elements, such as leaky buckets, multiplexers, and work conserving links, and deriving their associated calculus.

• Filtering theory under the min-plus algebra (30 mins): reviewing the min-plus algebra and discussing its connections to the general traffic characterization.

• Traffic regulation (20 mins): introducing optimal design of traffic regulators and the realizations of leaky buckets under the min-plus algebra.

• Extensions to networks with variable length packets (20 mins): introducing the concept of packetizers and illustrating its use in PGPS links.