For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Performance Analysis of Lookahead Scheduling Algorithm for Input-Buffered Packet Switches
Kwan L. YEUNG Hai SHI Ngai Han. LIU
IEICE TRANSACTIONS on Communications
Publication Date: 1999/08/25
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Switching and Communication Processing
input-buffered switch, packet scheduling algorithm, head-of-line blocking,
Full Text: PDF>>
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.