For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
The SCED Service Discipline with O(1) Complexity for Deadline Calculation
Kihyun PYUN Heung-Kyu LEE
IEICE TRANSACTIONS on Communications
Publication Date: 2002/05/01
Print ISSN: 0916-8516
Type of Manuscript: PAPER
quality of service, service discipline, packet scheduling, O(1) complexity, deadline-based algorithm,
Full Text: PDF(228.7KB)>>
In order for a service discipline to be used for guaranteed service networks at very high speed, its overall implementation must be scalable while it provides as wide a network schedulability region as possible. From this point of view, GPS-based service disciplines provide a narrow network schedulability region while EDF-based disciplines suffer from the implementation complexities of rate-controllers and admission control. Alternatively, although service disciplines based on service-curves can provide a wider network schedulability region than GPS-based and EDF-based disciplines, they may have even worse implementation complexities than EDF-based disciplines. In this paper, we propose to employ a service discipline based on our specific service-curves. We show that our service discipline has comparable implementation complexity to GPS-based disciplines while providing the same wide network schedulability region that EDF-based disciplines can provide. In fact, this service discipline is an SCED service discipline proposed in . However, our specific service-curves provide the SCED service discipline with the same network schedulability region that EDF-based disciplines can provide, O(1) complexity for deadline calculation, and O(N) complexity for admission control where N is the number of sessions.