Weighted Arbitration Algorithms with Priorities for Input-Queued Switches with 100% Throughput
Rainer Schoenen, Gerald Sander · 1999
Input buffered switches have the strong advantage of efficient crossbar usage. Virtual Output Queueing (VOQ) has to be established to circumvent the head-of-line (HOL) blocking which limits the throughput to 58.6%. Arbitration algorithms control the access to the switch fabric in each time slot. Weighted algorithms achieve 100% throughput with lowest delays under all admissible traffic even under highly asymmetric load. In this paper we compare existing algorithms and propose a new algorithm for weighted matching with a delay performance close to the ideal maximum weight matching. As an important step towards implementation we emphasize the finite wordlength required for weights. This can be exploited to support priorities which is required for ATM or IPv6 switches. 1 Introduction Very high speed switches are needed for future ATM and IPv6 networks. Among the switching architectures input queued switches belong to the fastest because the access rate of crossbar and buffer memory is no...