Some Properties Of Variable Length Packet Shapers

The min-plus theory of greedy shapers has been developed after Cruz`s results on the calculus of network delays. An example of greedy shaper is the buffered leaky bucket controller. The theory of greedy shapers establishes a number of properties such as the series decomposition of shapers or the conservation of arrival constraints by re-shaping. It applies in all rigor either to fluid systems, or to packets of constant size such as ATM. For variable length packets, the distortion introduced by packetization affects the theory, which is no longer valid. In this paper, we elucidate the relationship between shaping and packetization effects. We show a central result, namely, the min-plus representation of a packetized greedy shaper. We find a sufficient condition under which series decomposition of shapers and conservation of arrival constraints still hold in presence of packetization effects. This allows us to demonstrate the equivalence of implementing a buffered leaky bucket controller based on either virtual finish times or on bucket replenishment. However, we show on some examples that if the condition is not satisfied, then the property may not hold any more. This indicates that, for variable size packets, unlike for fluid systems, there is a fundamental difference between constraints based on leaky buckets, and constraints based on general arrival curves, such as spacing constraints. The latter are used in the context of ATM to obtain tight end-to-end delay bounds. In this paper, we use a min-plus theory, and obtain results on greedy shapers for variable length packets which are not readily explained with the max-plus theory of Chang.