Performance Analysis of Lookahead Scheduling Algorithm for Input-Buffered Packet Switches

Kwan L. YEUNG  Hai SHI  Ngai Han. LIU  

Publication
IEICE TRANSACTIONS on Communications   Vol.E82-B   No.8   pp.1296-1303
Publication Date: 1999/08/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Switching and Communication Processing
Keyword: 
input-buffered switch,  packet scheduling algorithm,  head-of-line blocking,  

Full Text: PDF>>
Buy this Article




Summary: 
In this paper, an analytical model for evaluating the performance of a packet scheduling algorithm, called lookahead scheduling, is proposed. Using lookahead scheduling, each input port of a switch has B packet buffers. A packet arrives at an input port is scheduled for conflict-free transmission for up to B time slots in advance. If it cannot be scheduled for transmission in the next B slots, the packet is immediately dropped to prevent it from blocking the subsequently arrived packets. To evaluate this scheduling algorithm, we first construct a set of recursive equations for obtaining the buffer occupancy and the probability that a packet cannot be placed into a buffer. Based on that, analytical expressions for switch throughput, packet loss probability and mean packet delay are derived. Analytical results are then compared with the simulations and good agreement is found. A pipeline implementation of the lookahead scheduling is also proposed in this paper.