Routing cost based network congestion control for quality of service

• US 20060067213A1
• Filed: 09/24/2004
• Published: 03/30/2006
• Est. Priority Date: 09/24/2004
• Status: Active Grant

• Current Assignee: Current Lighting Solutions, LLC (f/k/a GE Lighting Solutions, LLC) (American Industrial Partners)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Evans, Scott C., Egan, Martin W., Hartman, Michael J., Pearlman, Marc R., Leiva, Manuel A., Rothe, Asavari
• Granted Patent: US 7,489,635 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 41/5003 Managing SLA; Interaction between SLA and QoS
• CPC Class Codes: H04L 41/5025 by proactively reacting to service quality change, e.g. by reconfiguration after service quality degradation or upgrade
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2416 Real-time traffic
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04W 28/0284 detecting congestion or overload during communication monitoring arrangements H04L43/00
• CPC Class Codes: H04W 28/14 using intermediate storage
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: H04W 80/00 Wireless network protocols or protocol adaptations to wireless operation
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A method and system of congestion control in a network are provided. A required quality of service (QoS) parameter, such as a maximum allowable latency, for a packet received at a queue in the network, and a route cost metric, such as accumulated and estimated latency, are determined, and the packet is either discarded if the route cost metric exceeds the required QoS parameter, or a discard bias value is set for the packet. Also, if the required QoS parameter exceeds the route cost metric, the method includes determining whether a congestion condition exists in the network, and if the congestion condition exists, biasing the packet for discard based on its latency if the route cost metric for the packet exceeds a threshold. The network may be an IP network, and a network such as a mobile ad hoc network (MANET).

Claims

1. A network congestion control method, the method comprising:

setting a discard bias value for a packet received at a network node if a route cost metric determined for the packet exceeds a first threshold, such that the discard bias value of the packet is set higher than the discard bias value for a second packet with a lower route cost metric exceeding the first threshold.

2. The network congestion control method of claim 1, comprising:

determining whether a congestion condition exists in the network; and

if the congestion condition exists, judging whether the packet is to be discarded based on the discard bias value, such that the packet is more likely on average to be discarded than the second packet with a lower discard bias value.

3. The network congestion control method of claim 1, comprising:

determining whether a congestion condition exists in the network; and

if the congestion condition exists, discarding the packet if the route cost metric determined for the packet exceeds the first threshold.

4. The network congestion control method of claim 1, further comprising:

estimating a normalized distribution of the route cost metric for a plurality of packets received at a packet queue, such that the route cost metric is normalized according to a quality of service parameter for each packet of the plurality of packets at the queue;

determining a discard percentile of the distribution based on a value of the congestion condition; and

setting as the first threshold the discard percentile.

5. The network congestion control method of claim 1, wherein the route cost metric is a latency value determined for the packet.

6. The network congestion control method of claim 5, wherein the latency value is calculated based on an average time in a packet queue.

7. The network congestion control method of claim 5, wherein the latency value is calculated based on at least one of an accumulated upstream routing latency and a downstream routing latency based on a best route of the packet.

8. The network congestion control method of claim 2, wherein the determining of whether the congestion condition exists is based on at least one of a queue size snapshot relative to a maximum queue size capacity and a rate of change of a queue size.

9. The network congestion control method of claim 1, wherein the first threshold is calculated for a first packet of a first differentiated service priority class, and a second threshold is calculated for a third packet of a second differentiated service priority class.

10. The network congestion control method of claim 2, further comprising signaling, if the congestion condition is determined to exist, to a transmitting node in the network to reduce a packet load transmitted.

11. The network congestion control method of claim 1, wherein the network is an IP network implemented as a mobile ad hoc network.

12. A network congestion control method, the method comprising:

determining a quality of service parameter required for a packet received at a queue in a network;

determining a route cost metric for the packet; and

discarding the packet if the route cost metric exceeds the required quality of service parameter.

13. The network congestion control method of claim 12, wherein if the required quality of service parameter exceeds the route cost metric, the method further comprises:

setting a discard bias value for discarding the packet if the route cost metric for the packet exceeds a first threshold, such that the discard bias value of the packet is set higher than the discard bias value for a second packet with a lower route cost metric exceeding the first threshold.

14. The network congestion control method of claim 13, wherein when it is determined that a congestion condition exists in the network, it is judged whether the packet is to be discarded based on the discard bias value, such that the packet is more likely on average to be discarded than the second packet with a lower discard bias value.

15. The network congestion control method of claim 13, wherein when it is determined that the congestion condition exists in the network, the packet is discarded if the packet has a route cost metric that exceeds the first threshold.

16. The network congestion control method of claim 13, further comprising:

estimating a distribution of the route cost metric for a plurality of packets received at the queue, such that the route cost metrics of the distribution are first normalized based on the quality of service parameter for each packet of the plurality of packets at the queue;

determining a discard percentile of the distribution based on a value of the congestion condition; and

setting the discard percentile as the first threshold.

17. The network congestion control method of claim 12, wherein the route cost metric is a latency value of the packet.

18. The network congestion control method of claim 12, wherein the network is an IP network implemented as a mobile ad hoc network.

19. A network congestion control system, the system comprising:

a route costs determiner for determining a route cost metric for a packet received at a network node; and

a threshold setter for setting a discard bias value for discarding the packet if the route cost metric for the packet exceeds a first threshold, such that the discard bias value of the packet is set higher than the discard bias value for a second packet with a lower route cost metric exceeding the first threshold.

20. The network congestion control system of claim 19, comprising:

a congestion detector for determining whether a congestion condition exists in the network, wherein if the congestion condition exists, the threshold setter judges whether or not the packet is to be discarded based on the discard bias value, such that the packet is more likely on average to be discarded than the second packet with a lower discard bias value.

21. The network congestion control system of claim 19, comprising:

a congestion detector for determining whether a congestion condition exists in the network,

wherein if the congestion condition exists, the packet is discarded if the packet'"'"'s discard bias value exceeds the first threshold.

22. The network congestion control system of claim 20, further comprising:

a packet distribution estimator for estimating a normalized distribution of the route cost metric for a plurality of packets received at a queue, such that the distribution reflects the route cost metric normalized according to a quality of service parameter for each packet of the plurality of packets,

wherein the threshold setter determines as the first threshold a discard percentile of the normalized distribution based on a value of the congestion condition.

23. The network congestion control system of claim 20, wherein the route cost metric is a latency value for the packet.

24. The network congestion control system of claim 23, wherein the latency value is calculated based on an average time at a queue.

25. The network congestion control system of claim 23, wherein the latency value is calculated based on at least one of a downstream routing latency and an accumulated upstream routing latency.

26. The network congestion control system of claim 21, wherein the determining of whether the congestion condition exists is based on at least one of a queue size snapshot relative to a maximum queue size capacity and a rate of change of a queue size.

27. The network congestion control system of claim 20, wherein the first threshold is calculated for a first packet of a first differentiated service priority class, and a second threshold is calculated for a third packet of a second differentiated service priority class.

28. The network congestion control system of claim 21, further comprising signaling, if the congestion condition is determined to exist, to a transmitting node in the network to reduce a packet load transmitted.

29. The network congestion control system of claim 20, wherein the network is an IP network implemented as a mobile ad hoc network.

30. A network congestion control system, the system comprising:

a quality of service parameter determiner for determining a quality of service parameter required for a packet received at a queue in a network; and

a route costs determiner for determining a latency value for the packet;

wherein the system is configured to discard the packet if the latency value exceeds the required quality of service parameter.

31. The network congestion control system of claim 30, the system further comprising:

a threshold setter for setting a discard bias value for the packet if the latency value for the packet exceeds a first threshold, such that the discard bias value of the packet is set higher than the discard bias value for a second packet with a lower route cost metric exceeding the first threshold.

32. The network congestion control method of claim 31, comprising:

a congestion detector for determining, if the required quality of service parameter exceeds the latency value, whether a congestion condition exists in the network.

33. The network congestion control method of claim 32, wherein if the congestion condition exists, the threshold setter judges whether or not the packet is to be discarded based on the discard bias value of the packet, such that the packet is more likely on average to be discarded than the second packet with a lower discard bias value.

34. The network congestion control method of claim 30, wherein the required quality of service parameter is a maximum allowed latency for the packet.

35. The network congestion control system of claim 31, further comprising:

a packet distribution estimator for estimating a normalized distribution of the latency values for a plurality of packets received at a queue, such that the distribution reflects the latency values normalized according to a quality of service parameter for each packet of the plurality of packets,

wherein the threshold setter determines as the first threshold a discard percentile of the normalized distribution based on a value of the congestion condition.

36. The network congestion control system of claim 34, wherein the latency value is calculated based on an average time at a queue.

37. The network congestion control system of claim 34, wherein the latency value is calculated based on at least one of a downstream routing latency and an accumulated upstream routing latency.

38. The network congestion control method of claim 30, wherein the network is an IP network implemented as a mobile ad hoc network.