A comparison of the sliding window and the leaky bucket

A comparison of the sliding window and the leaky bucket

0.00 Avg rating0 Votes
Article ID: iaor19971620
Country: United States
Volume: 20
Issue: 1/2
Start Page Number: 117
End Page Number: 138
Publication Date: Sep 1995
Journal: Queueing Systems
Authors: ,
Keywords: communication
Abstract:

In this paper the authors compare the sliding-window (SW) and leaky-bucket (LB) input regulators. These regulators reject, or treat as lower priority, certain arrivals to a queueing system, so as to reduce congestion in the queueing system. Such regulators are currently of interest for access control in emerging high-speed communication networks. The SW admits no more than a specified number W of arrivals in any interval of specified length L. The LB is a counter that increases by one up to a maximum capacity C for each arrival and decreases continuously at a given drain rate to as low as zero; an arrival is admitted if the counter is less than or equal to C-1. To indirectly represent the impact of the regulator on the performance of the queueing system, the authors focus on the maximum bursts admissible at the peak rate. They show that the SW admits larger bursts than the LB at any given peak rate and admissible average rate. To make the comparison, the authors use a special construction: They start with a sample path of an arrival process with a given peak rate. The authors choose a window length L for the SW and find the minimum window content W that is just conforming (so there are no rejections). They then set the LB drain rate equal to W/L, so that the two admissible average rates are identical. Finally, the authors choose the LB capacity C so that the given arrival process is also just conforming for the LB. With this construction, they show that the SW will admit larger bursts at the peak rate than the LB. The authors also develop approximations for these maximum burst sizes and their ratio over long time intervals based on extreme-value asymptotics. They use simulations to confirm that these approximations do indeed enable us to predict the burst ratios for typical stochastic arrival processes.

Reviews

Required fields are marked *. Your email address will not be published.