Making High-Speed OQ Switches with QoS Guarantees Practical

A store-and-forward packet switched network consists of switches or routers (nodes) and the links connecting them as shared resources. Ideally, network switches employ output queueing. When a packet arrives at an output-queued (OQ) switch, it is immediately placed in a queue that is dedicated to its output link. Separating switching from scheduling makes it easier to design scheduling algorithms to achieve performance guarantees. Many packet scheduling algorithms for OQ switches have been proposed and shown capable of providing QoS guarantees. Output queueing, however, has been considered either impossible or impractical for high-speed networks, because it requires the switching fabric and memory to run N times as fast as the line rate. Memory with bandwidth sufficient for implementing a high-speed OQ switch with a large number of ports simply does not exist. In practice, input-queued (IQ) switches and combined input and output queued (CIOQ) switches are used. In this paper, we present an innovative framework for implementing a class of high-speed OQ switches with QoS guarantees. Internal speedup is implemented by memory interleaving, and O(1)-time scheduling is realized by special hardware. This shows that for high-speed networks, OQ switch with QoS guarantees is not only possible, but also feasible.