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 · 2003
SUMMARY 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