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

Kihyun PYUN; Junehwa SONG; Heung-Kyu LEE

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

Kihyun PYUN, Junehwa SONG, Heung-Kyu LEE

Full Text Views

0

Cite this

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 becomes work-conserving for free.

Publication: IEICE TRANSACTIONS on Communications Vol.E86-B No.12 pp.3646-3650

Publication Date: 2003/12/01

Publicized

Online ISSN

DOI

Type of Manuscript: LETTER

Category: Network

Cite this

Copy

Kihyun PYUN, Junehwa SONG, Heung-Kyu LEE, "Removing Unnecessary Buffers and Timers in EDF Scheduler with Regulators in Fixed-Sized Packet Networks" in IEICE TRANSACTIONS on Communications, vol. E86-B, no. 12, pp. 3646-3650, December 2003, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e86-b_12_3646/_p

Copy

@ARTICLE{e86-b_12_3646,
author={Kihyun PYUN, Junehwa SONG, Heung-Kyu LEE, },
journal={IEICE TRANSACTIONS on Communications},
title={Removing Unnecessary Buffers and Timers in EDF Scheduler with Regulators in Fixed-Sized Packet Networks},
year={2003},
volume={E86-B},
number={12},
pages={3646-3650},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Removing Unnecessary Buffers and Timers in EDF Scheduler with Regulators in Fixed-Sized Packet Networks
T2 - IEICE TRANSACTIONS on Communications
SP - 3646
EP - 3650
AU - Kihyun PYUN
AU - Junehwa SONG
AU - Heung-Kyu LEE
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E86-B
IS - 12
JA - IEICE TRANSACTIONS on Communications
Y1 - December 2003
AB - 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.
ER -