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 an d network interfaces. These algorithms need to be implemented in hardw are in a high-speed switch. In this article the authors present a numb er of approaches to implement scheduling algorithms in hardware. The a uthors begin by presenting a general methodology for the design of tim estamp-based fair queuing algorithms that provide the same bounds on e nd-to-end delay and fairness as those of Weighted Fair Queuing, yet ha ve efficient hardware implementations. Based on this general methodolo gy, the authors describe two specific algorithms, Frame-Based Fair Que uing and Starting Potential-Based Fair Queuing, and discuss illustrati ve implementations in hardware. These algorithms may be used in both c ell switches and packet switches with variable-size packets. A methodo logy for combining a traffic shaper with this class of fair queuing sc hedulers is also presented for use in network interface devices, such as an ATM segmentation and reassembly device.