Network usage analysis system and method for detecting network congestion

• US 7,571,181 B2
• Filed: 12/22/2004
• Issued: 08/04/2009
• Est. Priority Date: 04/05/2004
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Rhodes, Lee
• Primary Examiner(s): Fleurantin; Jean B
• Application Number:
  US11/021,956
• Publication Number:
  US 20050223089A1
• Time in Patent Office: 1,686 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 705/54, 709201-203, 709/217, 709/219, 709223-229, 709/235, 370/252, 370/447, 718100-107, 702/179
• US Class Current: 1/1
• CPC Class Codes: H04L 43/0876 Network utilisation, e.g. volume of load or congestion level
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00

Abstract

A system and method is provided herein for detecting congested locations within a network. The method includes receiving a stream of UDRs from one or more observation points within the network. The method further comprises computing an amount of bandwidth utilized by each UDR as each UDR is received from the observation point, generating a statistical distribution of the UDRs based on the amount of bandwidth utilized by each UDR, and analyzing the statistical to detect a congested location associated with the observation point.

Claims

1. A method for analyzing a stream of usage detail records (UDRs), the method comprising:

receiving the stream of UDRs from an observation point within a network;

computing an amount of bandwidth utilized by each UDR as each UDR is received from the observation point;

generating a statistical distribution of the UDRs based on the amount of bandwidth utilized by each UDR; and

analyzing the statistical distribution to detect a congested location associated with the observation point.

2. The method as recited in claim 1, wherein said receiving the stream of UDRs comprises receiving a plurality of UDRs from a network device associated with the observation point.

3. The method as recited in claim 1, wherein each of the UDRs is associated with a packet of information traveling between two points in the network.

4. The method as recited in claim 3, further comprising collecting relevant portions of each UDR as the UDR is received from the observation point.

5. The method as recited in claim 4, wherein the relevant portions comprise a packet volume, a travel start time and a travel end time.

6. The method as recited in claim 5, wherein said computing an amount of bandwidth comprises dividing the packet volume by a difference between the travel end time and the travel start time.

7. The method as recited in claim 1, wherein said generating a statistical distribution comprises applying a statistical model to each UDR as soon as its bandwidth utilization is computed.

8. The method as recited in claim 7, wherein the statistical model is selected from a group of models comprising a linear histogram, a log histogram, a probability distribution function and a cumulative distribution function.

9. The method as recited in claim 1, wherein said analyzing the statistical distribution comprises determining whether a majority of the bandwidth utilization in the statistical distribution is less than or equal to a percentage of total bandwidth available to the observation point.

10. The method as recited in claim 9, wherein the congestion location associated with the observation point is detected if a majority of the bandwidth utilization in the statistical distribution is less than or equal to the predetermined percentage.

11. The method as recited in claim 10, wherein the predetermined percentage is chosen from a range of percentages comprising about 50% to about 95%.

12. A method for detecting a congested location within a network, the method comprising:

collecting a stream of UDRs from a plurality of observation points within the network;

computing bandwidth utilization for each of at least a plurality of said UDRs as each such UDR is collected from the plurality of observation points;

generating a plurality of statistical distributions by grouping the UDRs by observation point and by computed bandwidth utilization; and

detecting a congested location when a majority of the bandwidth utilization in at least one of the plurality statistical distributions is less than or equal to a predefined percentage of total bandwidth available to a corresponding observation point.

13. The method as recited in claim 12, wherein said collecting a stream of UDRs comprises obtaining the UDRs from one or more network devices arranged along a boundary of the network.

14. The method as recited in claim 12, wherein said generating a plurality of statistical distributions comprises applying a statistical model to each UDR as soon as its bandwidth utilization is computed.

15. The method as recited in claim 14, wherein the statistical model is a histogram comprising one or more bins each associated with a different range of bandwidth utilization.

16. The method as recited in claim 15, wherein said generating a plurality of statistical distributions further comprises creating additional bins, if needed, based on the bandwidth utilization of a recently collected UDR.

17. The method as recited in claim 16, further comprising updating a corresponding one of the plurality of statistical distributions to reflect the recently collected UDR.

18. The method as recited in claim 17, further comprising storing the plurality of statistical distributions in lieu of storing the stream of UDRs.

19. A system for analyzing a statistical distribution of a stream of UDRs, comprising:

a data analysis system server coupled to a network, the data analysis system server comprising congestion logic;

wherein the congestion logic generates the statistical distribution by grouping UDRs according to bandwidth utilization upon receiving the stream of UDRs from a network device; and

wherein the congestion logic further analyzes the statistical distribution to determine if an observation point associated with the network device is a source of network congestion.

20. The system as recited in claim 19, wherein the network device comprises a routing device arranged on a boundary of the network.

21. The system as recited in claim 20, further comprising a data collection system coupled to the data analysis system server for collecting the stream of UDRs from the routing device.

22. The system as recited in claim 20, wherein the observation point comprises the routing device, an additional network device arranged within the network, or a link arranged between the routing device and the additional network device.

23. The system as recited in claim 20, further comprising a data storage system coupled to the data analysis system server for storing the statistical distribution in lieu of storing the stream of UDRs.

24. The system as recited in claim 20, further comprising a user interface coupled to the data analysis system server for displaying the statistical distribution and/or for displaying results of analyzing the statistical distribution.

25. A computer-readable storage medium having computer executable instructions for analyzing a statistical distribution of a stream of UDRs, the computer executable instructions comprising:

first program instructions that cause a computer to generate the statistical distribution by grouping UDRs according to bandwidth utilization as the stream of UDRs is received from a network device; and

second program instructions that cause the computer to analyze the statistical distribution to determine if an observation point associated with the network device is a source of network congestion.

26. The computer-readable storage medium as recited in claim 25, further comprising third program instructions for predicting future sources of network congestion based on extrapolated results obtained from execution of the first and second program instructions.