Systems and methods for managing network congestion

• US 10,153,980 B2
• Filed: 07/19/2016
• Issued: 12/11/2018
• Est. Priority Date: 07/19/2016
• Status: Active Grant

• Current Assignee: CoCo Communications, Corp.
• Original Assignee: CoCo Communications, Corp.
• Inventors: Eller, A. Riley, Edwards, Dennis M.
• Primary Examiner(s): Cosme, Natasha W
• Application Number:
  US15/213,759
• Publication Number:
  US 20180026897A1
• Time in Patent Office: 875 Days
• Field of Search: 370234
• CPC Class Codes: H04L 43/045 for graphical visualisation of monitoring data
• CPC Class Codes: H04L 43/067 using time frame reporting
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 47/127 by using congestion prediction
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets

Abstract

Techniques for managing congestion in a computer network are described. In some examples a network node uses a dynamic moving average to determine a level of network congestion a computer network. The dynamic moving average uses a window that is dynamically resized based on the contents of the window. For example, when the contents of the half of the window containing older samples are sufficiently different from the contents of the half of the window containing newer samples, the older samples are discarded and an average is calculated using just the newer samples.

Claims

1. A method for managing congestion in a computer network, the method comprising:

by a network node having a processor, a memory, and a network interface,

recording in the memory a history of network performance measurements provided by the network interface,

wherein the history includes a dynamic window defined by a current window size that holds a plurality of samples,

wherein the plurality of samples is divided between a first portion having a plurality of first samples and a second portion with a plurality of second samples,

wherein for each of multiple times, each sample is defined by one of a first value and a second value, wherein the first value and the second value each represent a different performance characteristic of the network measured at the time of sampling of the network performance measurement,

wherein the second portion has a window size that is equal to or less than a predefined maximum size and that is equal to or less than a predefined minimum size, and

wherein the plurality of samples in the dynamic window is at least equal to two times the minimum size of the second portion;

identifying the plurality of first samples of the first portion and the plurality of second samples of the second portion, wherein the first portion corresponds to earlier performance measurements, and wherein the second portion corresponds to later performance measurements that occur after the measurements represented by the first portion;

determining whether or not a difference between the first values of the first portion and the first values of the second portion is statistically significant;

when the difference is statistically significant, resizing the current window size of the dynamic window to a new window size, wherein the new window size holds only the plurality of second samples; and

determining a network congestion level using only second values in the second portion of the history.

2. The method of claim 1, further comprising:

when the difference is statistically significant, discarding the first portion of the, dynamic window stored in the history.

3. The method of claim 1, wherein the determining whether or not the difference between first values of the first portion and first values of the second portion is statistically significant includes:

performing a t-test to compare an average of the values in the first portion with an average of the values of the second portion.

4. The method of claim 1, further comprising:

when the difference is not statistically significant, determining the network congestion level using second values in the entire dynamic window stored in the history.

5. The method of claim 1, wherein the first and second values each represent one of a packet transmission success or failure, a packet delivery success or failure, a network data rate, and a network noise level.

6. The method of claim 1, wherein the identifying a first and second portion of the dynamic window stored in the history includes:

identifying a first half of the dynamic window stored in the history and a second half of the dynamic window stored in the history, the first half corresponding to the earlier performance measurements, and the second half corresponding to the later performance measurements.

7. The method of claim 1, further comprising:

establishing a maximum and minimum size for the dynamic window stored in the history; and

when new performance measurements are to be recorded and the dynamic window has a current size that is equal to the maximum size, discarding the values corresponding to the oldest measurements.

8. The method of claim 7,

wherein the maximum size is 64 entries;

and

wherein the minimum size is 8 entries.

9. The method of claim 1, wherein determining the network congestion level includes:

determining an average based on second values in the dynamic window stored in the history.

10. The method of claim 1, further comprising:

in response to the determined network congestion level, instructing the network interface to adjust transmission parameters in response.

21. The method of claim 1,

when a number of the plurality of samples of the dynamic window is an even number of samples, the window size of the second portion is the same as a window size of the first portion, and

when a number of the plurality of samples of the dynamic window is an odd number of samples, the window size of the second portion is one less that a window size of the first portion.

22. The method of claim 1, the window size of the second portion is one third of the window size of the dynamic window.

23. The method of claim 1, where in response to receiving a new network performance measurement defined by one of the first value or the second value, the method further comprising:

discarding an oldest one of the of the second portion;

adding the new network performance measurement into the second portion; and

determining a new network congestion level using only the second values in the second portion of the resized dynamic window.

24. The method of claim 1, further comprising:

determining a desired run-time factor at the network node;

increasing the maximum size and the minimum size of the window size of the second portion when the run-time factor is to be increased; and

decreasing the maximum size and the minimum size of the window size of the second portion when the run-time factor is to be decreased.

11. A system configured to manage congestion in a computer network, the system comprising:

a first network node having a processor, a memory, and a network interface;

wherein the processor is configured to;

record in the memory a history of network performance measurements provided by the network interface, wherein the history includes, for each of multiple times, a first and second value that each represent a different performance characteristic of the network measured at the time;

define a dynamic window that is stored in the history,

wherein the dynamic window has a current window size that holds a plurality of samples,

wherein the plurality of samples is divided between a first portion having a plurality of first samples and a second portion with a plurality of second samples,

wherein the second portion has a window size that is equal to or less than a predefined maximum size and that is equal to or less than a predefined minimum size,

wherein the plurality of samples in the dynamic window is at least equal to two times the minimum size of the second portion;

wherein the first portion corresponds to earlier performance measurements, and

wherein the second portion corresponds to later performance measurements that occur after the measurements represented by the first portion;

determine whether or not a difference between first values of the first portion and first values of the second portion is statistically significant;

when the difference is statistically significant, resize the current window size of the dynamic window to a new window size, wherein the new window size holds only the plurality of second samples; and

determine a network congestion level using only second values in the second portion of the history.

12. The system of claim 11, wherein the first network node is configured to:

initially transmit packets to a second network node via an intermediary network node, wherein the intermediary network node forwards packets to the second network node; and

in response to the determined network congestion level, transmit packets to the second network node directly, without use of the intermediary network node.

13. The system of claim 12, wherein the first network node is configured to:

determine a first network congestion level based on a recorded first history of network performance measurements for a link between the first network node and the second network node;

determine a second network congestion level based on a recorded second history of network performance measurements for a link between the first network node and the intermediary network node; and

determine, based on a comparison of the first network congestion level to the second network congestion level, to transmit packets to the second network node directly instead of via the intermediary network node.

14. The system of claim 11, wherein the first network node discards the first portion of the dynamic window stored in the history when the difference is statistically significant, wherein only the plurality of second samples remains in the dynamic window that has been resized to the new window size.

15. The system of claim 11, wherein the first network node determines whether or not the difference between first values of the first portion and first values of the second portion is statistically significant by:

determining whether an average of the values of the first portion is within a predetermined confidence interval of an average of the values of the second portion.

16. The system of claim 11, wherein the first network node is further configured to:

when the difference is not statistically significant, determine the network congestion level using the second values in the entire history.

17. The system of claim 11, wherein the first and second values each represent one of a packet transmission success or failure, a packet delivery success or failure, a network data rate, and a network noise level.

18. A non-transitory computer-readable medium including contents that are configured, when executed, to cause a network node to perform a method for managing congestion in a computer network, wherein the network node includes a processor, a memory, and a network interface, the method comprising:

by the network node,

recording in the memory a history of network performance measurements provided by the network interface, wherein the history includes, for each of multiple times, a first and second value that each represent a different performance characteristic of the network measured at the time;

defining a dynamic window that is stored in the history,

wherein the dynamic window has a current window size that holds a plurality of samples,

wherein the plurality of samples is divided between a first portion with a plurality of first samples and a second portion with a plurality of second samples,

wherein the second portion has a window size that is equal to or less than a predefined maximum size and that is equal to or less than a predefined minimum size,

wherein the plurality of samples in the dynamic window is at least equal to two times the minimum size of the second portion, and

wherein the first portion corresponds to earlier network performance measurements, and wherein the second portion corresponds to later network measurements that occur after the measurements represented by the first portion;

determining whether or not the difference between first values of the first portion and first values of the second portion is statistically significant;

when the difference is statistically significant, resizing the current window size of the dynamic window to a new window size, wherein the new window size holds only the plurality of second samples; and

determining a network congestion level using only second values in the second portion of the history.

19. The non-transitory medium of claim 18, wherein the method further comprises:

discarding the first portion of the history when the difference is statistically significant;

when the difference is not statistically significant, determining the network congestion level using second values in the entire history;

establishing a maximum and minimum size for the history; and

when new network performance measurements are to be recorded and the history has a current size that is equal to the maximum size, discarding the values corresponding to the oldest measurements;

wherein the first and second values each represent one of a packet transmission success or failure, a packet delivery success or failure, a network data rate, and a network noise level;

wherein the identifying the first and second portion of the history includes identifying a first half of the history and a second half of the history, the first half corresponding to the earlier performance measurements, and the second half corresponding to the later performance measurements.

20. The non-transitory medium of claim 19, wherein the method further comprises:

determining a first congestion level based on a recorded first history of performance measurements for a link between the first network node and a second network node;

determining a second congestion level based on a recorded second history of performance measurements for a link between the first network node and an intermediary network node; and

determining, based on a comparison of the first congestion level to the second congestion level, to transmit packets to the second network node directly instead of via the intermediary network node.