Method and system for traffic management in packet networks using random early marking

• US 20030067878A1
• Filed: 10/04/2001
• Published: 04/10/2003
• Est. Priority Date: 10/04/2001
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Tropic Networks, Inc. (Nokia Corporation)
• Inventors: Zboril, Thomas George
• Granted Patent: US 6,977,943 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames

Abstract

The invention describes a method for traffic management in a packet network using random early marking. For each packet flow, packets are randomly marked at the ingress of the network, while discard of the packets at the egress of the network is performed deterministically, i.e. in accordance with the predetermined rules. The step of random marking includes measuring parameters of the data flow, calculating marking probability by applying a mathematical function to the measured parameters, and generating a mark by applying a random logic function to the calculated marking probability. The packets are dropped at the egress of the network if the corresponding queues where the packets have to be stored are congested or full. A corresponding system for traffic management in packet networks is also provided.

Claims

1. A method for traffic management in a packet network, the method comprising the steps of:

(a) randomly marking a packet at the ingress of a network; and

(b) deterministically discarding the marked packet at the egress of the network.

2. A method as described in claim 1, further comprising the step of repeating the steps (a) to (b) required number of times.

3. A method as described in claim 1, wherein the step (a) comprises:

introducing a measure of the flow at the ingress of the network;

calculating a marking probability based on said measure of the flow; and

randomly generating a mark based on the calculated probability for marking the packet.

4. A method as described in claim 3, wherein the step of introducing the measure of the flow comprises determining one or more parameters of the flow.

5. A method as described in claim 4, wherein the step of introducing the measure of the flow comprises measuring one of the packet rate and bit rate.

6. A method as described in claim 3, wherein the step of introducing the measure of the flow comprises monitoring flow characteristics in accordance with a “

leaky bucket”

method.

7. A method as described in claim 3, wherein the step of calculating the marking probability comprises applying a mathematical function to the measure of the flow.

8. A method as described in claim 3, wherein the step of randomly generating the mark comprises applying a random logical function to the calculated marking probability.

9. A method as described in claims 8, wherein the generated mark has two outcomes, YES and NO.

10. A method as described in claim 1, the method being applied to the TCP (Transmission Control Protocol) data flow.

11. A method as described in claim 1, wherein the step (b) comprises dropping the marked packet in response to a signal regarding a status of an egress queue where the marked packet is to be stored.

12. A method as described in claim 11, wherein the step (b) comprises dropping the marked packet if the status of the egress queue is one of the congested and full.

13. A system for traffic management in a packet network, comprising:

means for randomly marking a packet at the ingress of the network; and

means for deterministically discarding the marked packet at the egress of the network.

14. A system as described in claim 13, wherein the means for marking comprises:

means for determining a measure of the flow at the ingress of the network;

means for calculating a marking probability based on said measure of the flow; and

means for randomly generating a mark based on the calculated probability for marking the packet.

15. A system as described in claim 14, wherein the means for determining the measure of the flow comprises means for determining one or more parameters of the flow.

16. A system as described in claim 15, wherein the means for determining the measure of the flow comprises means for measuring one of the packet rate and bit rate.

17. A system as described in claim 14, wherein the means for determining the measure of the flow comprises means for monitoring flow parameters in accordance with a “

leaky bucket”

method.

18. A system as described in claim 13, wherein the means for discarding comprises means for dropping the marked packet in response to a signal regarding a status of an egress queue where the marked packet is to be stored.

19. A system for traffic management in a packet network having a plurality of switching stages, the system comprising:

means for randomly marking packets in each packet flow at the ingress of the network; and

a plurality of means for deterministically discarding said marked packets in each packet flow after each switching stage and at the egress of the network.

20. A system as described in claim 19, wherein the means for marking comprises:

means for determining a measure of the flow at the ingress of the network;

means for calculating a marking probability based on said measure of the flow; and

means for randomly generating a mark based on the calculated probability for marking the packet.

21. A system as described in claim 19, wherein the means for discarding comprises means for dropping the marked packet in response to a signal regarding a status of a queue where the marked packet is to be stored.

22. A method for traffic management in a packet network having a plurality of switching stages, comprising the steps of:

randomly marking packets for each packet flow at the ingress of the network; and

deterministically discarding said marked packets for each packet flow after each switching stage and at the egress of the network.