A Minimum Output Burstiness Traffic Scheduling Algorithm

Yaw-Wen KUO; Tsern-Huei LEE

A Minimum Output Burstiness Traffic Scheduling Algorithm

Yaw-Wen KUO, Tsern-Huei LEE

Full Text Views

0

Cite this

Summary :

In this paper, we present a traffic scheduling algorithm, called the Delay-Bound Monotonic with Average Rate Reservation (DM/ARR), which generates minimum output burstiness streams. We assume that connection i is policed by the leaky bucket algorithm with parameters (σ_i,ρ_i) where σ_i is the bucket size (or burstiness) and ρ_i is the leaky rate. Compared with the totally isolated scheme where connection i is allocated a bandwidth r_i=max{σ_i/d_i,ρ_i} (d_i is the delay bound requirement of connection i), the DM/ARR algorithm has a better performance in the sense that it has a larger admission region. We prove that, among all possible scheduling algorithms that satisfy the delay bound requirements of established connections, DM/ARR results in the minimum output burstiness. This is important because a smaller burstiness implies a smoother traffic and thus the receiver (or next switch node in a multihop network) can handle it more easily. Numerical results show that the admission region of the DM/ARR algorithm is close to that of the earliest deadline first algorithm. A packetized version is studied for ATM networks.

Publication: IEICE TRANSACTIONS on Communications Vol.E82-B No.11 pp.1834-1843

Publication Date: 1999/11/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Communication Theory

Cite this

Copy

Yaw-Wen KUO, Tsern-Huei LEE, "A Minimum Output Burstiness Traffic Scheduling Algorithm" in IEICE TRANSACTIONS on Communications, vol. E82-B, no. 11, pp. 1834-1843, November 1999, doi: .
Abstract: In this paper, we present a traffic scheduling algorithm, called the Delay-Bound Monotonic with Average Rate Reservation (DM/ARR), which generates minimum output burstiness streams. We assume that connection i is policed by the leaky bucket algorithm with parameters (σ_i,ρ_i) where σ_i is the bucket size (or burstiness) and ρ_i is the leaky rate. Compared with the totally isolated scheme where connection i is allocated a bandwidth r_i=max{σ_i/d_i,ρ_i} (d_i is the delay bound requirement of connection i), the DM/ARR algorithm has a better performance in the sense that it has a larger admission region. We prove that, among all possible scheduling algorithms that satisfy the delay bound requirements of established connections, DM/ARR results in the minimum output burstiness. This is important because a smaller burstiness implies a smoother traffic and thus the receiver (or next switch node in a multihop network) can handle it more easily. Numerical results show that the admission region of the DM/ARR algorithm is close to that of the earliest deadline first algorithm. A packetized version is studied for ATM networks.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e82-b_11_1834/_p

Copy

@ARTICLE{e82-b_11_1834,
author={Yaw-Wen KUO, Tsern-Huei LEE, },
journal={IEICE TRANSACTIONS on Communications},
title={A Minimum Output Burstiness Traffic Scheduling Algorithm},
year={1999},
volume={E82-B},
number={11},
pages={1834-1843},
abstract={In this paper, we present a traffic scheduling algorithm, called the Delay-Bound Monotonic with Average Rate Reservation (DM/ARR), which generates minimum output burstiness streams. We assume that connection i is policed by the leaky bucket algorithm with parameters (σ_i,ρ_i) where σ_i is the bucket size (or burstiness) and ρ_i is the leaky rate. Compared with the totally isolated scheme where connection i is allocated a bandwidth r_i=max{σ_i/d_i,ρ_i} (d_i is the delay bound requirement of connection i), the DM/ARR algorithm has a better performance in the sense that it has a larger admission region. We prove that, among all possible scheduling algorithms that satisfy the delay bound requirements of established connections, DM/ARR results in the minimum output burstiness. This is important because a smaller burstiness implies a smoother traffic and thus the receiver (or next switch node in a multihop network) can handle it more easily. Numerical results show that the admission region of the DM/ARR algorithm is close to that of the earliest deadline first algorithm. A packetized version is studied for ATM networks.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - A Minimum Output Burstiness Traffic Scheduling Algorithm
T2 - IEICE TRANSACTIONS on Communications
SP - 1834
EP - 1843
AU - Yaw-Wen KUO
AU - Tsern-Huei LEE
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E82-B
IS - 11
JA - IEICE TRANSACTIONS on Communications
Y1 - November 1999
AB - In this paper, we present a traffic scheduling algorithm, called the Delay-Bound Monotonic with Average Rate Reservation (DM/ARR), which generates minimum output burstiness streams. We assume that connection i is policed by the leaky bucket algorithm with parameters (σ_i,ρ_i) where σ_i is the bucket size (or burstiness) and ρ_i is the leaky rate. Compared with the totally isolated scheme where connection i is allocated a bandwidth r_i=max{σ_i/d_i,ρ_i} (d_i is the delay bound requirement of connection i), the DM/ARR algorithm has a better performance in the sense that it has a larger admission region. We prove that, among all possible scheduling algorithms that satisfy the delay bound requirements of established connections, DM/ARR results in the minimum output burstiness. This is important because a smaller burstiness implies a smoother traffic and thus the receiver (or next switch node in a multihop network) can handle it more easily. Numerical results show that the admission region of the DM/ARR algorithm is close to that of the earliest deadline first algorithm. A packetized version is studied for ATM networks.
ER -