Method for dynamical identification of network congestion characteristics

• US 20020159386A1
• Filed: 04/30/2001
• Published: 10/31/2002
• Est. Priority Date: 04/30/2001
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: Network Physics, Inc. (Riverbed Technology Incorporated)
• Inventors: Grosdidier, Gilbert, Blankenbecler, Richard, Duong-van, Minh, Pavel, Tomas J., Wen, Han C., Adam, Ian
• Granted Patent: US 7,072,297 B2
• Time in Patent Office: Days
• US Class Current: 370/229
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 41/147 for predicting network behaviour
• 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 47/10 Flow control; Congestion control

Abstract

Congestion within a traffic stream of interest in a communication network is characterized as self-induced congestion or cross-induced congestion by analyzing a correlation result of a time series of throughput data of the traffic stream of interest and making the characterization based on power spectrum features found in the correlation result. The correlation result may be obtained through a Fourier analysis, a wavelet analysis or any mathematical process based on locating periodicities in the time series. In some cases, the characterization is made at a node in the communication network that is downstream from the congestion, while in other cases, the characterization is made at a node in the communication network that is upstream of the congestion.

Claims

1. A method, comprising characterizing congestion within a traffic stream of interest in a communication network as self-induced congestion or cross-induced congestion by analyzing a correlation result of a time series of throughput data of the traffic stream of interest and making the characterization based on power spectrum features found in the correlation result.

2. The method of claim 1 wherein the correlation result is obtained through a Fourier analysis of the time series.

3. The method of claim 1 wherein the correlation result is obtained through a wavelet analysis of the time series.

4. The method of claim 1 wherein the correlation result is obtained through a mathematical process based on locating periodicities in the time series.

5. The method of claim 1 wherein the characterization is made at a node in the communication network that is downstream from the congestion.

6. The method of claim 1 wherein the characterization is made at a node in the communication network that is upstream of the congestion.

7. The method of claim 1 wherein the power spectrum features comprise one or more of a distinctive peak within the power spectrum and area content of the power spectrum at low frequencies.

8. The method of claim 7 wherein the congestion is characterized as self-induced when the power spectrum exhibits one or more well-defined peaks and little power at low frequencies.

9. The method of claim 7 wherein the congestion is characterized as cross-induced when the power spectrum does not exhibit well-defined peaks and has relatively high power at low frequencies.

10. A communication network, comprising:

one or more nodes at which traffic streams are buffered; and

at least one monitor node coupled in a communication path with one of the nodes at which traffic streams are buffered, the monitor node configured to take a sample of throughput data for a traffic stream of interest, to compute a correlation result for the sample, and to determine whether congestion exists along the communication path of the traffic stream of interest according to whether or not certain features are found in the correlation result.

11. The communication network of claim 10 wherein the correlation result is obtained through a Fourier analysis of the time series.

12. The communication network of claim 10 wherein the correlation result is obtained through a wavelet analysis of the time series.

13. The communication network of claim 10 wherein the correlation result is obtained through a mathematical process based on locating periodicities in the time series.

14. The communication network of claim 10 wherein the monitor node is configured to determine that self-induced congestion exists along the communication path of the traffic stream of interest if the correlation result exhibits one or more well-defined peaks and little power at low frequencies in the face of packet loss within the traffic stream of interest.

15. The communication network of claim 10 wherein the monitor node is configured to determine that cross-induced congestion exists along the communication path of the traffic stream of interest if the correlation result exhibits one or more not well-defined peaks and relatively high power at low frequencies in the face of packet loss within the traffic stream of interest.

16. The communication network of claim 10 wherein the monitor node is further configured to implement a congestion control process according to whether or not cross-induced congestion or self-induced congestion is found in the communication path of the traffic stream of interest.

17. The communication network of claim 10 further comprising a control node configured to implement a congestion control process according to whether or not cross-induced congestion or self-induced congestion is found in the communication path of the traffic stream of interest.

19. The method of claim 18 wherein peaks of the power spectrum of the sample are compared to peaks of the stored replicas of the power spectrums of the known congestion sources.

20. The method of claim 18 further comprising applying a congestion control process to the traffic stream of interest based on results of the comparison.

18. A method comprising analyzing a sample of throughput data for a traffic stream of interest in a communication network to produce a power spectrum of the sample and comparing the power spectrum to stored replicas of power spectrums of known congestion sources within the communication network to determine a source of congestion for the traffic stream of interest.

21. A method, comprising analyzing a sample of throughput data for a traffic stream of interest in a communication network to produce a power spectrum of the sample, the power spectrum having one or more peaks, and identifying bandwidth mismatches within the networks by the peaks.

22. The method of claim 21 wherein the analyzing is performed at a control node in the network and further comprising setting a control bandwidth of the control node according to the identified bandwidth mismatches.

23. The method of claim 22 wherein the analyzing comprises using a fast Fourier transform process.

24. The method of claim 22 wherein the analyzing comprises using a wavelet transform process.

25. The method of claim 22 wherein the analyzing comprises using a process that reveals periodicities in a time series.

26. The method of claim 21 wherein periodic of the peaks correspond to bandwidths of bottlenecks within the network.