On the speedup required for combined input- and output-queued switching

Architectures based on a non-blocking fabric, such as a crosspoint switch, are attractive for use in high-speed LAN switches, IP routers, and ATM swit ches. When operating at the highest speed, memory bandwidth limitations dic tate that queues be placed at the input of the switch. But it is well known that input-queueing can lead to low throughput, and does not allow the con trol of latency through the switch. This is in contrast to output-queueing which maximizes throughput and permits the accurate control of packet laten cy through scheduling. We ask the question: Can a switch with combined inpu t and output queueing be designed to behave identically to an output-queued switch? In this paper, we prove that if the switch uses virtual output que ueing and has an internal speedup of just four, it is possible for it to be have identically to an output-queued switch, regardless of the nature of th e arriving traffic. Our proof is based on a novel scheduling algorithm, cal led Most Urgent Cell First. We find that with a speedup of four the most ur gent cell first algorithm (or MUCFA) enables perfect emulation of a FIFO ou tput-queued switch, i.e. one in which packets depart in the same order that they arrived. We extend this result to show that with a small modification , the MUCFA algorithm enables perfect emulation of a variety of output sche duling policies, including strict priorities and weighted fair-queueing. Th is result makes possible switches that perform as if they were output-queue d, yet use memories that run more slowly. (C) 1999 Elsevier Science Ltd. Al l rights reserved.