A minimum output burstiness traffic scheduling algorithm

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 (sigma(i), sigma(i)) where sigma(i) is the bucket size (or burstiness) and p(i) is the leaky rate. Compared with the totally isolated scheme where connection i is allocated a bandwidth r(i) = max{sigma(i)/d(i),rho(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 [1] algorithm. A packetized version is studied for ATM networks.