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

Kwan L. YEUNG; Hai SHI; Ngai Han. LIU

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

Kwan L. YEUNG, Hai SHI, Ngai Han. LIU

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Communications Vol.E82-B No.8 pp.1296-1303

Publication Date: 1999/08/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Switching and Communication Processing

Cite this

Copy

Kwan L. YEUNG, Hai SHI, Ngai Han. LIU, "Performance Analysis of Lookahead Scheduling Algorithm for Input-Buffered Packet Switches" in IEICE TRANSACTIONS on Communications, vol. E82-B, no. 8, pp. 1296-1303, August 1999, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/e82-b_8_1296/_p

Copy

@ARTICLE{e82-b_8_1296,
author={Kwan L. YEUNG, Hai SHI, Ngai Han. LIU, },
journal={IEICE TRANSACTIONS on Communications},
title={Performance Analysis of Lookahead Scheduling Algorithm for Input-Buffered Packet Switches},
year={1999},
volume={E82-B},
number={8},
pages={1296-1303},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={August},}

Copy

TY - JOUR
TI - Performance Analysis of Lookahead Scheduling Algorithm for Input-Buffered Packet Switches
T2 - IEICE TRANSACTIONS on Communications
SP - 1296
EP - 1303
AU - Kwan L. YEUNG
AU - Hai SHI
AU - Ngai Han. LIU
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Communications
SN -
VL - E82-B
IS - 8
JA - IEICE TRANSACTIONS on Communications
Y1 - August 1999
AB - 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.
ER -