A Minimum Output Burstiness Traffic Scheduling Algorithm

Yaw-Wen KUO  Tsern-Huei LEE  

IEICE TRANSACTIONS on Communications   Vol.E82-B    No.11    pp.1834-1843
Publication Date: 1999/11/25
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Communication Theory
quality of service,  burstiness,  scheduling,  admission control,  

Full Text: PDF(568.4KB)>>
Buy this Article

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 (σii) 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 ri=maxi/dii} (di 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.