EFFICIENT ADMISSION CONTROL OF PIECEWISE-LINEAR TRAFFIC ENVELOPES AT EDF SCHEDULERS

In this paper, we present algorithms for flow admission control at an earliest deadline first link scheduler when the flows are characterize d by piecewise linear traffic envelopes, We show that the algorithms h ave very low computational complexity and, thus, practical applicabili ty, The complexity can be further decreased by introducing the notion of discretized admission control. Through discretization, the range of positions for the end points of linear segments of the traffic envelo pes is restricted to a finite set. Simulation experiments show that di scretized admission control can lend to two orders of magnitude decrea se in the amount of computation needed to make admission control decis ions over that incurred when using exact (nondiscrete) admission contr ol, with the additional benefit that this amount of computation no lon ger depends on the number of flows. We examine the relative performanc e degradation tin terms of the number of flows admitted) incurred by t he discretization and find that it is small.