ACM Home
SIGMETRICS 2001 / Performance 2001 Home
Call for Papers
Organizing Committee
Technical Program Committee
Registration Information
Advanced Technical Program
Travel Support for Students
Travel Related Information
Other Links of Interest


SIGMETRICS 2001 / Performance 2001

Some Properties Of Variable Length Packet Shapers

Jean-Yves Le Boudec
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.

[Last updated Fri Mar 23 2001]