Domain based congestion management

• US 6,839,321 B1
• Filed: 07/18/2000
• Issued: 01/04/2005
• Est. Priority Date: 07/18/2000
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Chiruvolu, Girish Vsr
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): Nguyen, Van Kim T.
• Application Number:
  US09/618,196
• Time in Patent Office: 1,631 Days
• Field of Search: 370229-236, 370/400, 370/401, 370/410, 370412-416, 370352-354, 710 52- 57
• US Class Current: 370/230.1
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5636 Monitoring or policing, e.g. compliance with allocated rate, corrective actions
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/215 using token-bucket
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• 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/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

The Domain-based Congestion Management method and apparatus detects and regulates congestion in a Diff-serv network. It use an improvRED method for congestion detection at the core routers and token bucket filters for traffic regulation at the ingress nodes. In addition, improvRED also provides feedback control. ImprovRED uses three thresholds for detecting congestion: a minth, a maxth and a FeedbackThreshold, which lakes a value between the minth and the maxth thresholds. Whenever the average queue size is greater than minth and less than Feedback-Threshold, all outgoing packets are marked appropriately to indicate a potential onset of a congestion period. When the average queue size is greater th FeedbackThreshold (but less than maxth) packets are dropped probabilistically and all the outgoing packets are marked appropriately to denote the dropping phase. When the average queue size is greater than the maximum threshold, all incoming packets are dropped.

Claims

1. A method of detecting congestion, comprising:

setting a minimum threshold, a maximum threshold and a feedback threshold for buffer occupancy;

marking outgoing packets when said average queue size is between said minimum threshold and said feedback threshold;

dropping incoming packets and marking said outgoing packets when said average queue size is between said feedback threshold and said maximum threshold; and

dropping, all of said incoming packets when an average queue size exceeds said maximum threshold.

2. The method according to claim 1, wherein said average queue size is a size of a bucket of a token bucket filter.

3. The method according to claim 1, wherein said packets are marked deterministically in said step of marking outgoing packets when said average queue size is between said minimum threshold and said feedback threshold.

4. The method according to claim 1, wherein said packets are dropped probabilistically in said step of dropping incoming packets when said average queue size is between said feedback threshold and said maximum threshold.

5. The method according to claim 1, wherein said step of marking outgoing packets when said average queue size is between said minimum threshold and said feedback threshold comprises setting at least one bit in at least one of said packets, and said step of marking said outgoing packets when said average queue size is between said feedback threshold and said maximum threshold comprises setting at least one bit in at leas one of said packets.

6. The method according to claim 1, further comprising the step of calculating said average queue size based on a moving average.

7. The method of according to claim 1, further comprising the steps of:

varying a number of tokens consumed by a data packet; and

transmitting said packet if the number of tokens consumed by said packet is less and or equal to available tokens.

8. The method according to claim 5, wherein said bit is part of a type of services byte.

9. The method according to claim 5, wherein a core node performs said step of setting said bit.

10. The method according to claim 5, wherein said bit is a local congestion notification an bit.

11. The method according to claim 6, wherein said moving average is an exponential moving average.

12. The method according to claim 7, wherein said step of varying the number of tokens consumed by a data packet comprises varying the number of tokens consumed by data of unit size.

13. The method according to claim 7, wherein said step of varying said number of tokens comprises the step of decreasing data of unit size monotonically if demand increases monotonically during a congestion free period.

14. The method according to claim 7, wherein said step of said number of tokens comprises the step of increasing data of unit size upon receipt of a message.

15. The method according to claim 8, wherein said type of services byte is a differentiated services code point byte.

16. The method according to claim 11, wherein said packets are masked deterministically in said step of marking outgoing packets when said average queue size is between said minimum thershold and said feedback threshold, wherein said packets arm dropped probabilistically in said step of dropping incoming packets when said average queue size is between said feedback threshold and said maximum threshold, and wherein said step of marking outgoing packets when said average queue size is between said minimum threshold and said feedback threshold comprises a core node setting at least one bit in at least one of said packets and said step of marking outgoing packets when said average queue size is between said feedback threshold and said maximum threshold comprises setting at least one bit in at least one of said packets, wherein said bit is part of a type of services byte.

17. The method according to claim 14, wherein said step of varying said number of tokens comprises further decreasing said data of unit size if an average queue size is greater than a demand threshold.

18. A method of regulating traffic flow between nodes, comprising:

detecting congestion;

sending a message to at least one node;

regulating at least one traffic rate of said at least one node by varying a number of tokens consumed by a data packet by varying the number of tokens consumed by data of unit size, comprising the steps of;

decreasing said data of unit size monotonically if demand increases monotonically during a congestion free period;

further decreasing said data of unit size if an average queue size is greater than a demand threshold;

increasing said data of unit receipt of a message; and

transmitting said packet if a number of tokens consumed by said packet is less than available tokens, wherein said at least one packet is marked deterministically; and

detecting when congestion is clear.

19. The method according to claim 18, further comprising the step of incrementing said at least one traffic rate at random times when said congestion is clear.

20. The method according to claim 18, wherein a core node detects said congestion, and

an output node sends said message to at least one input node.

21. The method of according to claim 18, wherein said stop of regulating at least one traffic rate of said at least one node, comprises:

reducing said at least one traffic rate of said at least one node proportional to the amount of traffic that said at least one node is injecting when said congestion is detected.

22. The method according to claim 18, wherein said step of sending a message to at least one node comprises marking at last one packet.

23. A method of regulating traffic flow between nodes, comprising:

detecting congestion;

sending a message to at least one node;

regulating at least one traffic rate of said at least one node, wherein said step of regulating at least one traffic rate of said at least one node, comprises;

varying a number of tokens consumed by a data packet by decreasing data of unit size monotonically if demand increases monotonically during a congestion free period; and

transmitting said packet if a number of tokens consumed by said packet is less than or equal to available tokens; and

detecting when congestion is clear.

27. The method according to claim 23, wherein said step of varying said number of tokens comprises further decreasing said data of unit size if an average queue size is greater than a demand threshold.

24. A method of regulating traffic flow between nodes, comprising:

detecting congestion;

sending a message to at least one node;

regulating at least one traffic rate of said at least one node, wherein said step of regulating at least one traffic rate of said at least one node, comprises;

varying a number of tokens consumed by a data packet by increasing data of unit size upon receipt of a message; and

transmitting said packet if a number of tokens consumed by said packet is less than or equal to available tokens; and

detecting when congestion is clear.

25. A method of regulating traffic flow between nodes, comprising:

detecting congestion;

sending a message to at least one node by marking at one packet, wherein said packet is marked deterministically;

regulating at least one traffic rate of said at least one node; and

detecting when congestion is clear.

26. A method of regulating traffic flow between nodes comprising:

detecting congestion;

sending a message to at least one node by at least one packet wherein said step of marking packets comprises setting at least one bit in at least one of said packets;

regulating at least one traffic rate of said at least one node; and

detecting when congestion is clear.

28. The method according to claim 26, wherein said bit is part of a type of services byte.

29. A method of controlling traffic flow in a differentiated services domain, comprising:

determining available bandwidth by calculating an average queue size at token bucket filter;

determining if said average queue size is greater than a demand threshold;

varying a number of tokens consumed by a data packet; and

transmitting said data packet if a number of tokens consumed by said data packet is less than or equal to available tokens.

30. The method according to claim 29, wherein said step of varying the number of tokens consumed by a data packet comprises varying the number of tokens consumed by data of unit size.

31. The method according to claim 29, wherein said number of tokens consumed by a data packet is varied based on state and demand.

34. The method according to claim 30, wherein said step of varying the number of tokens consumed by data of unit size comprises varying the number of tokens consumed by a byte of data.

35. The method according to claim 30, wherein said step of varying the number of tokens consumed by data of unit size, comprises varying the number of tokens consumed by a bit of data.

41. The method according to claim 31, wherein said state is a congestion state.

32. A method of controlling traffic flow in a differentiated services domain, comprising:

varying a number of tokens consumed by a data packet, wherein said step of varying said number of tokens consumed by a data packet comprises a step of decreasing data of unit size monotonically if demand increases monotonically during a congestion free period; and

transmitting said data packet if a number of tokens consumed by said data packet is less than available tokens.

42. The method according to claim 32, wherein said step of varying said number of tokens comprises further decreasing said data of unit size if an average queue size is greater than a demand threshold.

33. A method of controlling traffic flow in a differentiated services domain, comprising:

varying a number of tokens consumed by a data packet, wherein said step of varying said number of tokens comprises a step of increasing data of unit size upon receipt of a message; and

transmitting said data packet if a number of tokens consumed by said data packet is less than available tokens.

36. A method of controlling traffic flow in a differentiated services domain, comprising:

varying a number of tokens consumed by a data packet by varying the number of tokens consumed by data of unit size, wherein a minimum number of tokens consumed by said data of unit size equals a depth of a token bucket filter divided by a min-max fair share of the buffer; and

transmitting said data packet if a number of tokens consumed by said data packet is less than or equal to available tokens.

37. A method of controlling traffic flow in a differentiated services domain, comprising:

varying a number of tokens consumed by a data packet by varying the number of tokens consumed by data of unit size, wherein a minimum number of tokens consumed by said data of unit size equals a depth of a token generation rate divided by a min-max fair share of the bandwidth; and

transmitting said data packet if a number of tokens consumed by said data packet is less than or equal to available tokens.

38. A method of controlling traffic flow in a differentiated services domain, comprising:

varying number of tokens consumed by a data packet by varying the number of tokens consumed by data of unit size, wherein a maximum number of tokens consumed by said data of unit size equals a depth of a token bucket filter divided by a maximum transmission unit; and

transmitting said data packet if a number of tokens consumed by said data packet is less than or equal to available tokens.

39. A method of controlling traffic flow in a differentiated services domain, comprising:

varying a number of tokens consumed by a data packet by varying the number of tokens consumed by data of unit size wherein a maximum member of tokens consumed by said data of unit size equals a token generation rate divided by a minimum data buffer drain rate; and

transmitting said data packet if a number of tokens consumed by said data packet is less than or equal to available tokens.

40. A method of controlling traffic flow in a differentiated services domain, comprising:

varying a number of tokens consumed by a data packet by varying the number of tokens consumed by data of unit size, wherein said step of varying the number of tokens consumed by data of unit size, comprise the steps of;

decreasing said data of unit size monotonically if demand increases monotonically during a congestion free period;

further decreasing said data of unit size if an average queue size is greater than a demand threshold; and

increasing said data of unit size upon receipt of a message, wherein said number of tokens consumed by a data packet is varied based on state and demand; and

transmitting said data packet if a number of tokens consumed by said data packet is less than or equal to available tokens.