Head of the line arbitration of packet switches with combined input and output queueing

Abstract

A single‐stage non‐blocking N × N packet switch is considered. Data units may be stored before switching at the inputs as well as after switching at the outputs. Some output buffering capacity is intended to achieve high throughput, whereas an additional input buffering capacity keeps losses due to input‐buffer overflow reasonably low. The paper studies the impact on performance of the head of the line arbitration policy, i.e. the sequence which is used to transfer data units from the heads of input queues to each output queue. The investigation is based on two performance measures: the average delay and the maximum throughput of the switch. Closed‐form expressions for the FCFS, LCFS and the ROS policies are obtained. The result of the average delay with the FCFS policy leads to a lower bound, and that with the LCFS policy to an upper bound for the average delay, corresponding to an arbitrary symmetric policy which does not use information related to the state of the input queues. It is shown that the maximum throughput does not depend on the head of the line arbitration policy. It depends only on the output‐buffer size and the packet‐size distribution. The cases of fixed and exponentially distributed packet sizes are studied. The effects of asymmetric policies which result in different behaviours of some of the input queues is also considered. Copyright © 1991 John Wiley & Sons, Ltd.