Fast Admission Control for Rate Monotonic Schedulers

Tsern-Huei LEE  An-Bang CHANG  

Publication
IEICE TRANSACTIONS on Communications   Vol.E82-B   No.1   pp.39-47
Publication Date: 1999/01/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Switching and Communication Processing
Keyword: 
real-time applications,  delay jitter,  scheduling,  admission control,  

Full Text: PDF>>
Buy this Article




Summary: 
Rate monotonic traffic scheduling algorithm had been shown to be the optimal static priority assignment scheme. The system model studied in can be considered (although not realistic) as a preemptive multiplexer which accepts constant bit rate connections that generate packets periodically. The multiplexer adopts a service discipline such that a lower priority packet can be preempted at any stage by a higher priority one without any loss. The constraint is that every packet has to complete its service before the arrival of its succeeding packet generated by the same connection. In this paper, we study the schedulability problem of rate monotonic schedulers for a fixed-length packet switched network such as the ATM network. A necessary and sufficient condition for a set of m constant bit rate connections to be rate monotonic schedulable is first derived and then utilized to design fast admission control algorithms. One of our algorithms computes in advance the minimum period of a connection which can be accepted given a set of existing connections.