Removing Unnecessary Buffers and Timers in EDF Scheduler with Regulators in Fixed-Sized Packet Networks

Kihyun PYUN  Junehwa SONG  Heung-Kyu LEE  

IEICE TRANSACTIONS on Communications   Vol.E86-B    No.12    pp.3646-3650
Publication Date: 2003/12/01
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Network
quality-of-service,  guaranteed service,  packet scheduling,  

Full Text: PDF>>
Buy this Article

Among the many scheduling algorithms which can guarantee delay bounds of sessions, the EDF scheduler with regulators has received wide attention since it can admit a very high number of sessions. However, due to regulators, EDF with regulators has difficulty in scalable implementation. To implement a regulator, a buffer and a timer are needed to restrict the incoming traffics. Given N number of sessions, N regulators are required. Moreover, due to regulators, the entire scheduling algorithm is not work-conserving. To enforce work-conserveness, it is known in the literature that additional buffers and a complex mechanism are required to bypass regulators. Thus, scalable implementation becomes much more difficult in the case of the work-conserving EDF with regulators. In this paper, however, we show that the buffers and timers used to implement regulators are unnecessary to guarantee delay bounds of admitted sessions in fixed-sized packet networks. Then, we can remove those unnecessary buffers and timers. By the removal, the resulting scheduling algorithm can be implemented in a scalable way and becomes work-conserving for free.