High-speed hardware implementation of MDRR algorithm over a large number of queues

• US 6,778,546 B1
• Filed: 02/14/2000
• Issued: 08/17/2004
• Est. Priority Date: 02/14/2000
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Epps, Garry P., Laor, Michael
• Primary Examiner(s): Hsu, Alpus H.
• Assistant Examiner(s): TRAN, THIEN D
• Application Number:
  US09/503,976
• Time in Patent Office: 1,646 Days
• Field of Search: 370/389, 370/392, 370/394, 370/412, 370/413, 370/414, 370/416, 370/417, 370/418, 370/419, 370/410, 370/422, 370/429
• US Class Current: 370/413
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/527 Quantum based scheduling, e.g. credit or deficit based scheduling or token bank
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9052 with buffers of different sizes

Abstract

A pipelined linecard architecture for receiving, modifying, switching, buffering, queuing and dequeuing packets for transmission in a communications network. The linecard has two paths: the receive path, which carries packets into the switch device from the network, and the transmit path, which carries packets from the switch to the network. In the receive path, received packets are processed and switched in an asynchronous, multi-stage pipeline utilizing programmable data structures for fast table lookup and linked list traversal. The pipelined switch operates on several packets in parallel while determining each packet'"'"'s routing destination. Once that determination is made, each packet is modified to contain new routing information as well as additional header data to help speed it through the switch. Each packet is then buffered and enqueued for transmission over the switching fabric to the linecard attached to the proper destination port. The destination linecard may be the same physical linecard as that receiving the inbound packet or a different physical linecard. The transmit path consists of a buffer/queuing circuit similar to that used in the receive path. Both enqueuing and dequeuing of packets is accomplished using CoS-based decision making apparatus and congestion avoidance and dequeue management hardware. The architecture of the present invention has the advantages of high throughput and the ability to rapidly implement new features and capabilities.

Claims

1. An apparatus for switching packets, said packets having a header portion, a tail portion, and a class of service indicator, comprising:

a pipelined switch comprising a plurality of pipeline stage circuits connected in a sequence;

a dequeue circuit that dequeues a packet using a round robin algorithm;

wherein each said stage circuit begins an operation substantially simultaneously with each other said stage circuit and each said stage circuit passes data to a next stage circuit in said sequence when every said operation performed by all said stage circuits is completed; and

an output queue, wherein the output queue has an associated quantum value and an associated deficit value.

2. The apparatus as recited in claim 1, wherein said round robin algorithm is a modified deficit round robin algorithm.

3. The apparatus of claim 1 further comprising:

a memory coupled to the dequeue circuit and operable to store a queue pointer.

4. The apparatus of claim 3 wherein the dequeue circuit is operable to fetch the queue pointer from the memory.

5. The apparatus of claim 1 further comprising:

a plurality of output queues.

6. The apparatus of claim 5 wherein at least one of the plurality of output queues is associated with a class of service (CoS) level.

7. The apparatus of claim 5 wherein a first one of the plurality of output queues is associated with a first class of service (CoS) level, wherein a second one of the plurality of output queues is associated with a second CoS level, and wherein the first CoS level is different from the second CoS level.

8. The apparatus of claim 5 wherein at least one of the plurality of output queues is a high priority output queue.

9. The apparatus of claim 1 wherein the dequeue circuit is operable to dequeue data from a first queue and data from a second queue substantially in parallel.

10. The apparatus of claim 1 further comprising a switch fabric interface.

11. The apparatus of claim 1 wherein the dequeue circuit is further configured to perform at least one of subtracting a packet length from the deficit value, adding the quantum value to the deficit value, and setting the deficit value to zero substantially in parallel with dequeuing a packet.

12. The apparatus of claim 1 wherein the output queue is a first output port high priority queue, the apparatus further comprising:

a plurality of first output port low priority queues;

a second output port high priority queue; and

a plurality of second output port low priority queues;

wherein the dequeue circuit operates to service the first output port high priority queue and the second output port high priority queue according to a simple round-robin algorithm until the first output port high priority queue and the second output port high priority queue are clear, and then operates to service at least one of;

the plurality of first output port low priority queues, and the plurality of second output port low priority queues, according to a deficit round-robin algorithm.

13. The apparatus of claim 1 wherein output queue is a first output port high priority queue, the apparatus further comprising:

a plurality of first output port low priority queues;

wherein the dequeue circuit operates to dequeue a first quantum of data from the first output port high priority queue, and then operates to dequeue a second quantum of data from at least one of the plurality of first output port low priority queues according to a deficit round-robin algorithm.

16. The method of claim 4 further comprising:

performing, substantially in parallel with the dequeuing a packet, at least one of;

subtracting a packet length from the deficit value;

adding the quantum value to the deficit value; and

setting the deficit value to zero.

14. A method of switching packets, said packets having a header portion and a tail portion, which comprises:

switching said packets through a pipelined switch having a plurality of pipeline stage circuits connected in a sequence; and

dequeuing a packet from an output queue using a round robin algorithm;

wherein each said stage circuit begins an operation substantially simultaneously with each other said stage circuit and each said stage circuit passes data to a next stage circuit in said sequence when every said operation performed by all said stage circuits is completed, and wherein the output queue has an associated quantum value and an associated deficit value.

15. The method as recited in claim 14, wherein said round robin algorithm is a modified deficit round robin algorithm.

17. The method of claim 14 wherein the output queue is a first output port high priority queue, the method further comprising:

providing a plurality of first output port low priority queues;

providing a second output port high priority queue;

providing a plurality of second output port low priority queues;

dequeuing data from the first output port high priority queue and the second output port high priority queue according to a simple round-robin algorithm; and

dequeuing data from at least one of;

the plurality of first output port low priority queues, and the plurality of second output port low priority queues, according to a deficit round-robin algorithm.

18. The method of claim 14 wherein the output queue is a first output port high priority queue, the method further comprising:

providing a plurality of first output port low priority queues;

dequeuing a first quantum of data from the first output port high priority queue; and

dequeuing a second quantum of data from at least one of the plurality of first output port low priority queues according to a deficit round-robin algorithm.

19. An apparatus for switching packets, the packets having a header portion and a tail portion, the apparatus comprising:

a means for switching the packets through a plurality of stage circuits connected in a sequence;

a means for storing a packet, wherein the means for storing a packet has an associated quantum value and an associated deficit value; and

a means for dequeuing the packet according to a round robin algorithm;

wherein each of the plurality of stage circuits of the means for switching the packets begins an operation substantially simultaneously with each other and passes data to a next stage circuit when every operation performed by the plurality of stage circuits is completed.

20. The apparatus of claim 19, wherein the round robin algorithm is a modified deficit round robin algorithm.

21. The apparatus of claim 19 further comprising:

a means for performing, substantially in parallel with dequeuing a packet, at least one of;

subtracting a packet length from the deficit value;

adding the quantum value to the deficit value; and

setting the deficit value to zero.

22. The apparatus of claim 19 wherein the means for storing a packet is a first output port high priority queue, the apparatus further comprising:

a means for providing a plurality of first output port low priority queues;

a means for providing a second output port high priority queue; and

a means for providing a plurality of second output port low priority queues,

wherein the means for dequeuing is further for

dequeuing data from the first output port high priority queue and the second output port high priority queue according to a simple round-robin algorithm; and

dequeuing data from at least one of;

the plurality of first output port low priority queues, and the plurality of second output port low priority queues, according to a deficit round-robin algorithm.

23. The apparatus of claim 19 wherein the means for storing a packet is a output port high priority queue, the apparatus further comprising:

a means for providing a plurality of first output port low priority queues;

a means for dequeuing a first quantum of data from the first output port high priority queue; and

a means for dequeuing a second quantum of data from at least one of the plurality of first output port low priority queues according to a deficit round-robin algorithm.