Performance analysis of lookahead scheduling algorithm for input-buffered packet switches

In this paper, an analytical model for evaluating the performance of a pack et scheduling algorithm, called lookahead scheduling, is proposed. Using lo okahead scheduling, each input port of a switch has B packet buffers. A pac ket arrives at an input port is scheduled for conflict-free transmission fo r 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 algo rithm, we first construct a set of recursive equations for obtaining the bu ffer occupancy and the probability that a packet cannot be placed into a bu ffer. Based on that, analytical expressions for switch throughput, packet l oss probability and mean packet delay are derived. Analytical results are t hen compared with the simulations and good agreement is Found. A pipeline i mplementation of the lookahead scheduling is also proposed in this paper.