A packet scheduling algorithm in high performance routers

The Internet is facing two problems simultaneously: there is a need for a faster switching/routing infrastructure and a need to introduce guaranteed qualities-of-service (QoS). Each problem can be solved independently: high performance routers can be made faster by using input-queued crossbars instead of shared memory systems; QoS can be provided using packet fair queueing (PFQ) algorithms. Until now, however, the two solutions have been mutually exclusive-all of the work on PFQ algorithms has required that routers use output-queueing or centralized shared memory. In this paper, we design and implement a packet scheduling algorithm, DF²Q (distributed feedback fair queueing), on the basis of CIOQ (combined input output queueing) architecture. The most important feature of this scheduling algorithm is the introduction of a feedback mechanism. We analyze and discuss the performance of DF²Q, and the experimental results show that it can avoid internal congestion effectively and improve the efficiency of resource utilization