System and method for router queue and congestion management

• US 20060062233A1
• Filed: 11/14/2005
• Published: 03/23/2006
• Est. Priority Date: 12/19/2000
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Chiaro Networks, Ltd.
• Inventors: Brewer, Tony M., Palmer, Gregory S., Shaw, Keith W., Kleiner, Jim
• Granted Patent: US 7,813,365 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• 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-34. -34. (canceled)

35. A method of instantaneous queue congestion management of drop probabilities of packets using a queue congestion management algorithm applied to a plurality of queues sharing a common memory pool.

36. The method of claim 35 wherein said queue congestion management algorithm is implemented in hardware.

37. The method of claim 35 wherein said queue congestion management algorithm uses a floating point format.

38. The method of claim 37 wherein said floating point format comprises:

a four-bit normalized mantissa;

a six-bit biased exponent; and

performing multiply and divide operations with a mantissa table lookup.

39. The method of claim 38 wherein the most significant bit of said mantissa is implied.

40. The method of claim 38 wherein said biased exponent is in a range of −

32 to +31.

41. The method of claim 38 wherein said mantissa table lookup uses two three-bit inputs and generates one four-bit output.

42. The method of claim 38 wherein said floating point format comprises only positive numbers.

43. The method of claim 35 wherein said queue congestion management algorithm comprises:

determining the total amount of shared memory space in bytes;

monitoring the instantaneous actual sizes of each of said queues;

dynamically calculating minimum and maximum queue sizes of a drop probability curve for each of said queues;

comparing said instantaneous actual sizes with said maximum and minimum queue sizes;

if said instantaneous queue size is less than said minimum queue size, then assigning said packet to said queue;

otherwise if said instantaneous queue size is between said maximum and said minimum queue sizes, then calculating and applying a drop probability using the slope of said drop probability curve; and

otherwise

if said instantaneous queue size is greater than said maximum queue size, then dropping said packet.

44. The method of claim 35 wherein non-utilized shared memory space is allocated simultaneously to all of said queues sharing said common memory pool.

45. A method of time averaged congestion management of drop probabilities of packets using a weighted random early discard (WRED) algorithm applied to a plurality of arrays sharing a common memory pool.

46. The method of claim 45 wherein said arrays are queues, each of said queues being assigned to a different quality of service (QOS) priority level.

47. The method of claim 45 wherein said WRED algorithm is implemented in hardware.

48. The method of claim 45 wherein said WRED algorithm uses a floating point format.

49. The method of claim 48 wherein said floating point format comprises:

a four-bit normalized mantissa;

a six-bit biased exponent; and

performing multiply and divide operations with a mantissa table lookup.

50. The method of claim 49 wherein the most significant bit of said mantissa is implied.

51. The method of claim 49 wherein said biased exponent is in a range from −

32 to +31.

52. The method of claim 49 wherein said mantissa table lookup uses two three-bit inputs and generates one four-bit output.

53. The method of claim 49 wherein said floating point format comprises only positive numbers.