Lookahead scheduling algorithm for input-buffered packet switches

Abstract

An analytical model for evaluating the performance of a packet scheduling algorithm, called lookahead scheduling, is proposed in this paper. 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 discarded for having more room for the packets arrived later on. Based on a set of recursive equations for obtaining buffer occupancy and probability that a packet cannot be placed into a buffer, analytical expressions for switch throughput, packet loss probability and mean packet delay are derived. Analytical results are then compared with the simulation results and good agreement is found.