Minimum-Latency Dual-Leaky-Bucket Shapers for Packet Multiplexers: Theory and Implementation

The need of integrating per-flow dual-leaky-bucket regulators with a scheduler that enforces strict bandwidth guarantees is becoming a crucial issue in networks that provide differentiated services. Despite the increasing relevance of the topic, existing solutions either lack accuracy in their shaping action, or compromise the provision of strict bandwidth guarantees to the shaped flows, or suboptimally utilize the output link. In this paper, we present the Monolithic Shaper-Scheduler (MSS), which integrates the shaping and scheduling functions while preserving the bandwidth guarantees of the shaped flows. The MSS handles shaped and unshaped flows simultaneously. It allows to prevision per-flow shaping parameters that are independent of the corresponding bandwidth requirements; thus, the available link bandwidth can be fully utilized. The latency and worst-case-fairness properties of the new scheduler are optimal among GPS-related schedulers. We describe how the MSS can be easily implemented in practice, with minimal overhead with respect to a conventional GPS-related scheduler.