Policy-based weighted random early detection method for avoiding congestion in internet traffic

• US 6,996,062 B1
• Filed: 02/28/2001
• Issued: 02/07/2006
• Est. Priority Date: 02/28/2001
• Status: Expired due to Term

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Freed, Michael, Amara, Satish Kumar
• Primary Examiner(s): Lee, Andy
• Application Number:
  US09/795,549
• Time in Patent Office: 1,805 Days
• Field of Search: 370/230, 370/235, 370/252, 370/412, 370/465
• US Class Current: 370/235
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/20 Traffic policing
• 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 method and apparatus for avoiding network congestion. An exemplary packet forwarding device may apply policy rules to incoming packets to assign relative drop probabilities to the packets based on the priority of the packets. In times of network congestion, packets may be selectively dropped according to their associated drop probability.

Claims

1. A method for avoiding network congestion in a packet forwarding device, the method comprising the steps of:

receiving at the packet forwarding device at least one flow of packets;

receiving at the packet forwarding device policy information to be applied to the at least one flow of packets, wherein the policy information includes at least one rule associated with address information and a traffic category;

receiving at the packet forwarding device at least one queue parameter;

continuously calculating, in the packet forwarding device, an average queue size;

assigning a drop probability to the at least one flow of packets based upon (i) the policy information, and (ii) a number of packets transmitted since a packet was last dropped;

selectively dropping packets from the at least one flow of packets based at least in part upon the drop probability, the average queue size, and the at least one queue parameter.

2. The method of claim 1, wherein the address information comprises at least one source address.

3. The method of claim 1, wherein the address information comprises at least one destination address.

4. The method of claim 1, wherein the policy information comprises at least one rule associated with a source or destination port associated with a communication protocol.

5. The method of claim 1, wherein the at least one flow of packets comprises a voice traffic flow, and wherein the traffic category is voice traffic.

6. The method of claim 1, wherein the at least one queue parameter includes a minimum threshold.

7. The method of claim 1, wherein the at least one queue parameter includes a maximum threshold.

8. The method of claim 1, wherein the at least one queue parameter comprises a minimum threshold and a maximum threshold.

9. The method of claim 8, wherein packets are selectively dropped from the at least one flow of packets whenever the average queue size is between the minimum threshold and the maximum threshold.

10. The method of claim 1, wherein the traffic category comprises a category selected from the group consisting of voice, data, and internet traffic.

11. A method for avoiding network congestion in a packet forwarding device, the method comprising the steps of:

receiving at the packet forwarding device at least one flow of packets comprising a voice traffic flow;

receiving at the packet forwarding device at least one policy rule to be applied to voice traffic, wherein the at least one policy rule is associated with address information and traffic category information;

receiving at the packet forwarding device queue parameters comprising a minimum threshold and a maximum threshold;

continuously calculating, in the packet forwarding device, an average queue size;

assigning a drop probability to the voice traffic flow based upon (i) the at least one policy rule, and (ii) a number of packets transmitted since a packet was last dropped; and

selectively dropping packets from the voice traffic flow based upon the drop probability whenever the average queue size is between the minimum threshold and the maximum threshold.

12. The method of claim 11, wherein the traffic category information comprises information selected from the group consisting of voice traffic information, data traffic information, and internet traffic information.

13. A method for avoiding network congestion in a packet forwarding device, the method comprising the steps of:

receiving at the packet forwarding device at least one flow of packets;

receiving policy information to be applied to the at least one flow of packets, wherein the policy information includes at least one rule associated with address information and traffic category information;

receiving at least one queue parameter;

continuously calculating an average queue size;

assigning a drop probability to the at least one flow of packets based upon (i) the policy information, and (ii) a number of packets transmitted since a packet was last dropped;

selectively dropping packets from the at least one flow of packets based at least in part upon the drop probability, the average queue size, and the at least one queue parameter.

14. The method of claim 13, wherein the address information comprises at least one source address.

15. The method of claim 13, wherein the address information comprises at least one destination address.

16. The method of claim 13, wherein the policy information comprises at least one rule associated with a source or destination port associated with a communication protocol.

17. The method of claim 13, wherein the at least one flow of packets comprises a voice traffic flow, and wherein the traffic category information indicates voice traffic.

18. The method of claim 13, wherein the at least one queue parameter includes a minimum threshold.

19. The method of claim 13, wherein the at least one queue parameter includes a maximum threshold.

20. The method of claim 13, wherein the at least one queue parameter comprises a minimum threshold and a maximum threshold.

21. The method of claim 20, wherein packets are selectively dropped from the at least one flow of packets whenever the average queue size is between the minimum threshold and the maximum threshold.

22. A method for avoiding network congestion in a packet forwarding device, the method comprising the steps of:

receiving at the packet forwarding device at least one flow of packets comprising a voice traffic flow;

receiving at least one policy rule to be applied to voice traffic, wherein the at least one policy rule is associated with address information and traffic category information;

receiving queue parameters comprising a minimum threshold and a maximum threshold;

continuously calculating an average queue size;

assigning a drop probability to the voice traffic flow based upon (i) the at least one policy rule, and (ii) a number of packets transmitted since a packet was last dropped; and

selectively dropping packets from the voice traffic flow based upon the drop probability whenever the average queue size is between the minimum threshold and the maximum threshold.

23. A packet forwarding device for avoiding network congestion, comprising:

an input component that receives policy information, wherein the policy information includes at least one rule associated with address information and traffic category information;

at least one input port configured to receive incoming packets;

at least one output port configured to transmit packets, the at least one output port having at least one queue;

a prioritizing component that assigns a drop probability to each incoming packet based upon (i) the policy information and (ii) a number of packets transmitted since a packet was last dropped;

a forwarding engine coupled to the at least one input port and the at least one output port, the forwarding engine configured to queue or drop incoming packets based at least in part on the drop probability of the packets.

24. A computer usable medium having computer readable program code means embodied therein for causing a packet forwarding device to avoid network congestion, the computer readable program code means in the computer usable medium comprising sequences of instructions which, when executed by a processor, cause the processor to perform the steps of:

receiving at the packet forwarding device policy information to be applied to at least one flow of packets, wherein the policy information includes at least one rule associated with address information and traffic category information;

receiving at least one queue parameter;

continuously calculating an average queue size;

assigning a drop probability to the at least one flow of packets based upon (i) the policy information, and (ii) a number of packets transmitted since a packet was last dropped;

selectively dropping packets from the at least one flow of packets based at least in part upon the drop probability, the average queue size, and the at least one queue parameter.