Implementing distributed packet fair queueing in a scalable switch architecture

To support the Internet's growth, there is a need for cost effective switching technologies that can simultaneously provide high capacity switching and advanced QoS. Unfortunately, these two goals are largely believed to be contradictory in nature. To support QoS, sophisticated packet scheduling algorithms, such as fair queueing, are needed to manage queueing points. However, the bulk of current research in packet scheduling algorithms assumes an output buffered switch architecture, whereas most high performance switches are input buffered. While output buffered systems may have the desired QoS, they lack the necessary scalability. Input buffered systems, while scalable, lack the necessary QoS features. We propose the construction of switching systems that are both input and output buffered with the scalability of input buffered switches and the robust QoS of output buffered switches. We call the resulting architecture distributed packet fair queueing (D-PFQ) as it enables physically dispersed line cards to provide a service that closely approximates an output-buffered switch with fair queueing. By equalizing the growth of the virtual time functions across the switch system, most of the PFQ algorithms in the literature can be properly defined for distributed operation. We present our system using a cross bar for the switch core. Buffering techniques are used to enhance the system's latency tolerance, which enables the use of pipelining and variable packet sizes internally. We evaluate the delay and bandwidth sharing properties.