Premium
Head of the line arbitration of packet switches with combined input and output queueing
Author(s) -
Iliadis Ilias
Publication year - 1991
Publication title -
international journal of digital and analog communication systems
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.344
H-Index - 49
eISSN - 1099-1131
pISSN - 1047-9627
DOI - 10.1002/dac.4510040302
Subject(s) - queue , arbitration , queueing theory , computer science , throughput , upper and lower bounds , network packet , line (geometry) , transfer (computing) , control theory (sociology) , real time computing , computer network , topology (electrical circuits) , mathematics , telecommunications , parallel computing , control (management) , combinatorics , mathematical analysis , geometry , artificial intelligence , political science , law , wireless
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.