Performance Analysis of Weighted Round Robin Cell Scheduling and Its Improvement in ATM Networks

Hideyuki SHIMONISHI
Hiroshi SUZUKI

Publication
IEICE TRANSACTIONS on Communications   Vol.E81-B    No.5    pp.910-918
Publication Date: 1998/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Issue on ATM Traffic Control and Performance Evaluation)
Category: Buffer Management
Keyword: 
ATM,  scheduler,  weighted round robin,  delay bound,  burstiness,  

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


Summary: 
Weighted Round Robin (WRR) scheduling is an extension of round robin scheduling. Because of its simplicity and bandwidth guarantee, WRR cell scheduling is commonly used in ATM switches. However, since cells in individual queues are sent cyclically, the delay bounds in WRR scheduling grow as the number of queues increases. Thus, static priority scheduling is often used with WRR to improve the delay bounds of real-time queues. In this paper, we show that the burstiness generated in the network is an even greater factor affecting the degradation of delay bounds. In ATM switches with per-class queueing, a number of connections are multiplexed into one class-queue. The multiplexed traffic will have a burstiness even if each connection has no burstiness, and when the multiplexed traffic is separated at the down stream switches, the separated traffic will have a burstiness even if the multiplexed traffic has been shaped in the upstream switches. In this paper, we propose a new WRR scheme, namely, WRR with Save and Borrow (WRR/SB), that helps improving the delay bound performance of WRR by taking into account the burstiness generated in the network. We analyze these cell scheduling methods to discuss their delay characteristics. Through some numerical examples, we show that delay bounds in WRR are mainly dominated by the burstiness of input traffic and, thus WRR/SP, which is a combination of WRR and static priority scheduling, is less effective in improving delay bounds. We show that WRR/SB can provide better delay bounds than WRR and that it can achieve the same target delay bound with a smaller extra bandwidth, while large extra bandwidth must be allocated for WRR.