Method for detecting congestion in internet traffic

• US 7,337,206 B1
• Filed: 07/15/2002
• Issued: 02/26/2008
• Est. Priority Date: 07/15/2002
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Network Physics, Inc. (Riverbed Technology Incorporated)
• Inventors: Pavel, Tomas J., Wen, Han C.
• Primary Examiner(s): Meky; Moustafa M.
• Application Number:
  US10/195,904
• Time in Patent Office: 2,052 Days
• Field of Search: 709/235, 709200-202, 709220-231, 370229-238
• US Class Current: 709/200
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/022 by sampling
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0864 Round trip delays
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/0888 Throughput
• CPC Class Codes: H04L 43/0894 Packet rate
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• 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/29 using a combination of thresholds

Abstract

A baseline for internet traffic duration is established by (i) collecting internet traffic data regarding file size, server response time, packet loss and round trip time, (ii) removing from this data outliers associated with file size, server response time and packet loss per client type, and (iii) organizing any remaining data into round trip time bins according to median values of round trip time per client type. Thereafter, historical or newly collected Internet traffic data is compared against threshold values for each round trip time bin to locate duration outliers. These duration outliers are indicators of congestion and congestion episodes may be identified by the continued presence of such outliers over successive time intervals.

Claims

1. A method to detect congestion in a network traffic, comprising:

for a first set of data points, each having a number of associated parameters, eliminating first outliers as determined according to first statistical properties of a first one of the associated parameters;

establishing a first baseline based on remaining first set of data points without the first outliners; and

examining a second set of data points against the first baseline for second outliers according to second statistical properties of a second one of the associated parameters.

2. The method of claim 1 wherein the first statistical properties are different than the second statistical properties.

3. The method of claim 1 wherein the second one of the associated parameters comprises end-to-end response time within a computer network.

4. The method of claim 1 wherein the second one of the associated parameters comprises end-to-end response time within an internetwork.

5. The method of claim 1 wherein the first one of the associated parameters affects the second one of the associated parameters.

6. A method to detect congestion in a network traffic, comprising:

for a first set of data points, each having a number of associated parameters, eliminating first outliers as determined according to statistical properties of a first group of the associated parameters;

establishing a first baseline based on remaining first set of data points without the first outliers; and

examining a second set of data points against the first baseline for second outliers according to statistical properties of one of the associated parameters that is not included in the first group of associated parameters.

7. The method of claim 6 wherein the first group of the associated parameters includes file size, server response time, packet loss and latency.

8. The method of claim 7 wherein the one of the associated parameters that is not included in the first group of associated parameters comprises duration.

9. The method of claim 6 wherein outliers as determined according to statistical properties of a first group of the associated parameters are eliminated in part by sorting the first set of data points according to a first one of the first group of associated parameters and eliminating outliers as determined according to statistical properties of the first one of the first group of associated parameters.

10. A method to detect congestion in a network traffic, comprising

collecting Internet traffic duration information for a client;

characterizing the Internet traffic duration information by client type and latency;

removing packet loss outliers for each client type;

partitioning remaining data without packet loss outliers into bins;

setting latency threshold values for the bins; and

examining the Internet traffic duration information for duration outliers as determined by the latency threshold values.

11. A method to detect congestion in a network traffic, comprising:

establishing a baseline for internet traffic duration by (i) collecting internet traffic data regarding file size, server response time, packet loss and round trip time, (ii) removing from this data outliers associated with file size, server response time and packet loss per client type, and (iii) organizing any remaining data into round trip time bins according to median values of round trip time per client type; and

comparing historical or newly collected Internet traffic data against threshold values for each round trip time bin to locate duration outliers.

12. The method of claim 11 wherein outliers associated with file size are removed by sorting all file size measurements in ascending order and eliminating any of the data associated with file size measurements that exceed a file size threshold value.

13. The method of claim 12 wherein the file size threshold value represents a 95^th percentile for the file size measurements.

14. The method of claim 11 wherein outliers associated with file size are removed by first categorizing all file size measurements into distinct file size ranges and, for each category of file size ranges, sorting file size measurements in ascending order and eliminating any of the data associated with file size measurements that exceed a file size threshold value.

15. The method of claim 11 wherein outliers associated with server response time are removed by sorting all server response time measurements in ascending order and eliminating any of the data associated with server response time measurements that exceed a server response time threshold value.

16. The method of claim 15 wherein the server response time threshold value represents a 95^th percentile for the server response time measurements.

17. The method of claim 11 wherein outliers associated with packet loss are removed by categorizing all packet loss measurements by client type and then, for each client type, sorting packet loss measurements in ascending order and eliminating any of the data associated with packet loss measurements that exceed a packet loss threshold value.

18. The method of claim 17 wherein the client type is either low or high RTT.

19. The method of claim 18 wherein the packet loss threshold value represents a 95^th percentile for packet loss measurements per client type.

20. The method of claim 11 wherein the round trip time bins are established according to median round trip time per client type.

21. The method of claim 20 wherein the client type is either low or high RTT.