System and method for router queue and congestion management

• US 7,974,208 B2
• Filed: 05/10/2010
• Issued: 07/05/2011
• Est. Priority Date: 12/19/2000
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Foundry Networks Incorporated (Broadcom, Inc.)
• Inventors: Brewer, Tony M., Palmer, Gregory S., Shaw, Keith W., Kleiner, Jim
• Primary Examiner(s): Pezzlo; John
• Application Number:
  US12/777,069
• Publication Number:
  US 20100220742A1
• Time in Patent Office: 421 Days
• Field of Search: 370/229, 370/230, 370/235, 370/412, 370/413, 370/414, 370/417, 370/418, 370/429, 370/252, 370/419, 370/235.1, 709/232, 709/233, 709/235, 709/252
• US Class Current: 370/235.1
• CPC Class Codes: H04L 2012/5648 Packet discarding, e.g. EPD, PTD
• CPC Class Codes: H04L 2012/5681 Buffer or queue management
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/43 Assembling or disassembling of packets, e.g. segmentation and reassembly [SAR]
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

In a multi-QOS level queuing structure, packet payload pointers are stored in multiple queues and packet payloads in a common memory pool. Algorithms control the drop probability of packets entering the queuing structure. Instantaneous drop probabilities are obtained by comparing measured instantaneous queue size with calculated minimum and maximum queue sizes. Non-utilized common memory space is allocated simultaneously to all queues. Time averaged drop probabilities follow a traditional Weighted Random Early Discard mechanism. Algorithms are adapted to a multi-level QOS structure, floating point format, and hardware implementation. Packet flow from a router egress queuing structure into a single egress port tributary is controlled by an arbitration algorithm using a rate metering mechanism. The queuing structure is replicated for each egress tributary in the router system.

Claims

1. A method comprising:

receiving packets into a number of queues;

allocating memory to the queues;

determining a memory utilization;

over-subscribing unused memory;

allocating the over-subscribed memory to the queues; and

adjusting packet drop probabilities of one or more queues based at least on the allocation of the over-subscribed memory among the queues.

2. The method of claim 1, further comprising:

assigning the received packets to the queues in accordance with their quality of service (QOS) priority levels.

3. The method of claim 1, further comprising dropping received packets based at least on each queue'"'"'s packet drop probability.

4. The method of claim 3, wherein the packet dropping is performed by hardware.

5. The method of claim 3, wherein dropping the packets comprises applying a weighted random early discard method with the packet drop probabilities.

6. The method of claim 1, further comprising dynamically calculating a minimum and maximum size of a respective queue.

7. The method of claim 1, wherein the queues are at an egress side of a router.

8. A switching system, comprising:

a receiving mechanism configured to receive packets into a number of queues;

a memory allocation mechanism configured to;

allocate memory to the queues;

determine a memory utilization;

over-subscribe unused memory; and

allocate the over-subscribed memory to the queues; and

a packet-dropping mechanism configured to adjust packet drop probabilities of one or more queues based at least on the allocation of the over-subscribed memory among the queues.

9. The switching system of claim 8, wherein the receiving mechanism is further configured to assign the received packets to the queues in accordance with their quality of service (QOS) priority levels.

10. The switching system of claim 8, wherein the packet-dropping mechanism is configured to drop received packets based at least on each queue'"'"'s packet drop probability.

11. The switching system of claim 10, wherein the packet dropping is performed by hardware.

12. The switching system of claim 10, wherein while dropping the packets the packet-dropping mechanism is configured to apply a weighted

random early discard method with the packet drop probabilities.

13. The switching system of claim 8, wherein the memory allocation mechanism is further configured to calculate dynamically a minimum and maximum size of a respective queue.

14. The switching system of claim 8, wherein the queues are at an egress side of the switching system.

15. A switching means, comprising:

a receiving means for receiving packets into a number of queues;

a memory allocation means for;

allocating memory to the queues;

determining a memory utilization;

over-subscribing unused memory; and

allocating the over-subscribed memory to the queues; and

a packet-dropping means for adjusting packet drop probabilities of one or more queues based at least on the allocation of the over-subscribed memory among the queues.

16. The switching means of claim 15, wherein the receiving means is for assigning the received packets to the queues in accordance with their quality of service (QOS) priority levels.

17. The switching means of claim 15, wherein the packet-dropping means is further for dropping received packets based at least on each queue'"'"'s packet drop probability.

18. The switching means of claim 17, wherein the packet dropping is performed by hardware.

19. The switching means of claim 17, wherein while dropping the packets the packet-dropping means applies a weighted random early discard method with the packet drop probabilities.

20. The switching means of claim 15, wherein the memory allocation means is further for calculating dynamically a minimum and maximum size of a respective queue.

21. The switching means of claim 15, wherein the queues are at an egress side of the switching system.