Efficient Admission Control 
             of Piecewise Linear Traffic Envelopes 
                      at EDF Schedulers

            Victor Firoiu, Jim Kurose, Don Towsley


                         ABSTRACT


In this paper we present algorithms for flow admission control at an
EDF link scheduler when the flows are characterized by piecewise
linear traffic envelopes. We show that the algorithms have very low
computational complexity and thus, practical applicability. The
complexity can be further decreased by introducing the notion of
discrete admission control. Through discretization, the range of
positions for the end points of linear segments of the traffic
envelopes is restricted to a finite set. In simulation experiments, we
obtain two orders of magnitude decrease in the amount of computation
needed to make admission control decisions over the case of exact
(non-discrete) admission control, with the additional benefit that
this amount of computation no longer depends on the number of
flows. We examine the relative performance degradation (in terms of
the number of flows admitted) incurred by the discretization and find
the tradeoff to be small.