The SCED Service Discipline with O(1) Complexity for Deadline Calculation

Kihyun PYUN  Heung-Kyu LEE  

IEICE TRANSACTIONS on Communications   Vol.E85-B   No.5   pp.1012-1019
Publication Date: 2002/05/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network
quality of service,  service discipline,  packet scheduling,  O(1) complexity,  deadline-based algorithm,  

Full Text: PDF(228.7KB)>>
Buy this Article

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 [14]. 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.