Scalable real-time architectures and hardware support for high-speed QoS packet schedulers

Conventional wire-speed QoS packet scheduling architectures are inflexible and incur ASIC overhead costs. New hardware architectures are required to meet the QoS requirements of different streams at wire-speeds, without ASIC engineering overheads. An architectural framework is developed that helps guide development of architectures and physical realizations to meet the QoS needs of different streams, while balancing constraint-performance goals. A taxonomy of packet scheduling disciplines is developed that classifies into three different families—priority-class, fair-queueing and window-constrained. Software-based QoS packet schedulers can provide flexible scheduling support for application-level protocol data units. They are unable to exploit packet-level and stream-level parallelism efficiently for concurrent stream state maintenance. Also, bit-level parallelism in scheduler rules cannot be exploited efficiently for ordering streams. The ShareStreams (Scalable Hardware and Architectures for Stream Schedulers) hardware architecture exploits stream-level and packet-level parallelism. Stream service attributes are stored in Register Base blocks. Decision blocks are used to compare stream service attributes pairwise by exploiting bit-level parallelism in scheduler rules. Total priority ordering is provided by organizing Decision blocks in a recirculating shuffle-exchange network. ShareStreams is a scalable architecture and provides a number of architectural variants to trade execution time for lower hardware complexity in a predictable manner. A window-constrained scheduling discipline mapped to the ShareStreams architecture implemented in Xilinx Virtex II technology FPGAs can process 256 stream queues at 10 Gbps line-rates. A service-tag or priority-class scheduling discipline mapped to the ShareStreams architecture can process 4096 stream queues at 10 Gbps line-rates or 1024 stream queues at 40 Gbps line-rates with a Xilinx Virtex II FPGA. The ShareStreams system architecture uses a network or embedded processor, called a Stream processor for queueing and data movement, while decisions and stream selection are accelerated on a reconfigurable FPGA array. The system architecture can provide scheduling support for a mix of real-time and best-effort traffic streams. A host-based router implementation of the ShareStreams architecture can provide comparable performance with the MIT Click router, nearly 299,065 packets/second. The ShareStreams line-card configuration far exceeds the decision throughput provided by a number of vendor line-cards.