Hardware implementation of fair queuing algorithms for asynchronous transfer mode networks

Providing quality-of-service guarantees in both cell- and packet-based networks requires the use of a scheduling algorithm in the switches and network interfaces. These algorithms need to be implemented in hardware in a high-speed switch. In this article the author present a number of approaches to implement scheduling algorithms in hardware. The authors begin by presenting a general methodology for the design of timestamp-based fair queuing algorithms that provide the same bounds on end-to-end delay and fairness as those of Weighted Fair Queuing, yet have efficient hardware implementations. Based on this general methodology, the authors describe two specific agorithms, Framed Fair Queuing and Starting Potential-Based Fair Queuing, and discuss illustrative implementations in hardware. These algorithms may be used in both cell switches and packet switches with variable-size packets. A methodology for combining a traffic shaper with this class of fair queuing schedulers is also presented for use in network interface devices, such as an ATM segmentation and reassembly device.