|
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; for example,
re-shaping keeps original arrival constraints. The existing theory
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. Chang has introduced the concept of
packetizer, which models the effect of variable length packets,
and has also developed a max-plus theory of shapers. In this
paper, we start with the 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. We show a
fundamental result, namely, the min-plus representation of a
packetized greedy shaper. This allows us to prove that, under some
assumptions, re-shaping a flow of variable length packets does
keep original arrival constraints. However, we show on some
examples that if the assumptions are not satisfied, then the
property may not hold any more. We also demonstrate the
equivalence of implementing a buffered leaky bucket controller
based on either virtual finish times or on bucket replenishment.
|
