Single cycle weighted random early detection circuit and method

• US 7,286,550 B2
• Filed: 12/13/2002
• Issued: 10/23/2007
• Est. Priority Date: 12/14/2001
• Status: Active Grant

• Current Assignee: IDT Canada Incorporated (Renesas Electronics Corporation)
• Original Assignee: Tundra Semiconductor Corp. (Renesas Electronics Corporation)
• Inventors: Saxena, Nirmal Raj, Modali, Prasad
• Primary Examiner(s): NGUYEN, BRIAN D
• Application Number:
  US10/318,769
• Publication Number:
  US 20030112814A1
• Time in Patent Office: 1,775 Days
• Field of Search: 370/412, 370/235
• US Class Current: 370/412
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/24 Traffic characterised by specific attributes, e.g. priority or QoS
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes
• CPC Class Codes: H04L 47/326 with random discard, e.g. random early discard [RED]

Abstract

A system and method is provided for traffic management and regulation in a packet-based communication network, the system and method facilitating proactive, discriminating congestion control on a per flow basis of packets traversing the Internet via use of a Weighted Random Early Detection (WRED) algorithm that monitors the incoming packet queue and optimizes enqueuing or discard of incoming packets to stabilize queue length and promote efficient packet processing. During optimized discard conditions, the system and method discern a relative priority among incoming packets, distribute packets with a relatively high priority and discard packets with a relatively low priority. Additionally, packet traffic are policed and discarded according to packet type, quantity or other predetermined criteria. The present invention performs in periodic mode, demand mode or both, and can be implemented as a hardware solution, a software solution, or a combination thereof.

Claims

1. A method for regulating network packet traffic, the method comprising the steps of:

determining a minimum threshold and a maximum threshold;

calculating an average queue size according to a following formula;

average=(old_average*(1−

½

^n))+(current_queue_size*½

^n),

wherein the average is the average size of a queue;

the old-average is a previous average of the queue;

the current_queue_size is a current size of the queue; and

n is an exponential weight factor and a user-configurable value;

when the average queue size is less than the minimum threshold, enqueuing an arriving packet;

when the average queue size is greater than the maximum threshold, dropping the packet;

when the average queue size is between the minimum threshold and the maximum threshold,

calculating a packet drop probability (Pdrop); and

performing one of a set consisting of enqueuing and dropping the packet, according to the calculated probability.

2. The method of claim 1 wherein the minimum threshold and the maximum threshold are individually determined based on at least one criterion selected from a group consisting essentially of traffic pattern, flow, and computer system capacity.

3. The method of claim 1, wherein the step of calculating a packet drop probability further comprises calculating the packet drop probability according to formula:

Pdrop=Pdmax*(avqlen−

min_th)/(max_th−

min_th)

wherein Pdmax is a maximum probability;

avqlen is one of a set consisting of a periodic and a per packet average queue length;

min_th is a minimum threshold under which all packets must be accepted; and

max_th is a maximum threshold over which all packets can be dropped.

4. The method of claim 1, wherein the step of calculating a packet drop probability is performed in a single cycle.

5. The method of claim 1, further comprising the step of policing packets according to a predetermined criterion.

6. The method of claim 1, further comprising the step of calculating the packet drop probability on at least one of a set consisting of a demand basis and a periodic basis.

7. The method of claim 1, further comprising the step of generating a new average queue length per flow.

8. A method for regulating network packet traffic, the method comprising the steps of:

determining a minimum threshold and a maximum threshold;

calculating an average queue size according to a following formula,

average=(old average*(1−

½

^n))+(current_queue_size*½

^n),

wherein the average is the average size of a queue;

the old-average is a previous average of the queue;

the current_queue_size is a current size of the queue; and

n is an exponential weight factor and a user-configurable value;

when the average queue size is less than the minimum threshold, enqueuing an arriving packet;

when the average queue size is greater than the maximum threshold, dropping the packet;

when the average queue size is between the minimum threshold and the maximum threshold,

calculating a packet drop probability in a single cycle, and

either enqueuing or dropping the packet according to the calculated probability; and

policing packets according to a predetermined criterion.

9. The method of claim 8, wherein the step of calculating a packet drop probability further comprises calculating the packet drop probability according to formula:

Pdrop=Pdmax*(avqlen−

min_th)/(max_th−

min_th)

wherein Pdmax is a maximum probability;

avqlen is one of a set consisting of a periodic and a per packet average queue length;

min_th is a minimum threshold under which all packets must be accepted; and

max_th is a maximum threshold over which all packets can be dropped.

10. A system for management of packet traffic, the system comprising:

an interface block for initiating memory references for label reads and updates, and interacting with an Ingress Control Unit (ICU);

a calculation block for calculating an average queue size according to a formula and calculating packet drop probability depending on the average queue size, the calculation block associated with the interface block, the formula being;

average=(old average*(1−

½

^n))+(current_queue_size*½

^n),

wherein the average is the average size of a queue;

the old-average is a previous average of the queue;

the current_queue_size is a current size of the queue; and

n is an exponential weight factor and a user-configurable value; and

a policing block for performing police updates, the policing block associated with the interface block.

11. The system of claim 10, wherein the packet drop probability is calculated in a single cycle.

12. The system of claim 10, wherein the interface block further comprises a timer.

13. The system of claim 10, further comprising at least one interface signal.

14. The system of claim 13, wherein the at least one interface signal is selected from a group essentially consisting of wru_enable;

first_flowid_addr max_flowcnt;

wred_cyclecnt;

zcu_rddata;

zcu_rddata_calid;

zcu_readvalid; and

icu_rddata.

15. The system of claim 10, wherein the calculation block performs packet drop probability calculations on a periodic basis.

16. The system of claim 10, wherein the calculation block performs packet drop probability calculations on a demand basis.

17. The system of claim 10, wherein the calculation block further calculates a new average queue size.