NETWORK CONGESTION ANALYSIS

• US 20080019278A1
• Filed: 07/12/2007
• Published: 01/24/2008
• Est. Priority Date: 07/13/2006
• Status: Active Grant

• Current Assignee: Riverbed Technology, LLC (Riverbed Technology Incorporated)
• Original Assignee: OPNET Technologies Incorporated (Riverbed Technology Incorporated)
• Inventors: Malloy, Patrick, Elsner, Russell, Cohen, Alain, Niemczyk, Steve
• Granted Patent: US 7,839,790 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 43/0852 Delays
• 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]

Abstract

Application messages are segregated into message paths, and the delays of the transmitted packets associated with each message path are independently analyzed to distinguish propagation, bandwidth, congestion, and protocol delays. To further distinguish the congestion delays, all of the paths of the application messages are assessed to identify delays induced by the application, including self-congestion delay, corresponding to pre-congestion delays caused by attempting to send data from a source device faster than the bandwidth of the channel allows, and cross-congestion delay, corresponding to post-congestion delays caused by varying delays beyond a bottleneck link in the channel. The remaining congestion delay is identified as network congestion delay, corresponding to delays caused by network devices other than the source device. After identifying each of the components of delay, the effect of each component on the overall delay is determined to identify where improvements can best be made.

Claims

1. A method of determining delay components of an application sequence comprising:

partitioning the application sequence into a plurality of message paths,

identifying a set of packets corresponding to each message path, each packet having an associated set of packet delay components,

determining a set of message delay components corresponding to each message path, based on the sets of packet delay components associated with the message path,

wherein

the set of packet delay components includes a packet bandwidth delay, and determining the set of message delay components includes;

determining one or more occurrences of message bandwidth delay, based on occurrences of packet bandwidth delay in one or more of the sets of packet delay components associated with the message path, and

determining one or more occurrences of message congestion delay, based on an absence of occurrences of packet bandwidth delay in one or more of the sets of packet delay components associated with the message path.

2. The method of claim 1, wherein

determining the set of message delay components includes

determining one or more occurrences of message self-congestion delay, based on a concurrent occurrence of message bandwidth delay in at least two message paths, and

the method includes:

adjusting the set of message delay components corresponding to at least one of the at least two message paths based on the one or more occurrences of message self-congestion delay.

3. The method of claim 2, wherein

determining the set of message delay components includes

determining one or more occurrences of message cross-congestion delay, based on a concurrent occurrence of message bandwidth delay in at least two message paths, and

the method includes:

adjusting the set of message delay components corresponding to at least one of the at least two message paths based on the one or more occurrences of message cross-congestion delay.

4. The method of claim 1, wherein

the set of packet delay components includes a packet congestion delay, and

determining the set of message delay components includes

determining one or more occurrences of message protocol delay, based on an absence of occurrences of packet congestion delay and packet bandwidth delay associated with the message path.

5. The method of claim 1, wherein

determining the set of message delay components includes

determining one or more occurrences of message latency delay, based on a distance associated with the message path.

6. The method of claim 1, including

determining the associated set of packet delay components for each packet based on a size of each packet and a minimum bandwidth associated with the corresponding message path.

7. The method of claim 6, wherein

determining the associated set of packet delay components for each packet is also based on a distance traveled by the packet.

8. The method of claim 1, including

displaying one or more of the sets of message delay components associated with one or more of the message paths.

9. The method of claim 1, including

modifying one or more components of the determined sets of message delay components to produce a set of modified message delay components for each message path,

adjusting a time of occurrence of the modified message delay components in each message path,

determining one or more occurrences of message self-congestion delay, based on a concurrent occurrence of message bandwidth delay of the modified message delay components in at least two message paths,

adjusting the set of modified message delay components corresponding to at least one of the at least two message paths based on the one or more occurrences of message self-congestion delay, and

identifying one or more differences between the sets of message delay components and the sets of modified delay components.

10. The method of claim 9, including

displaying one or more of the sets of modified message delay components associated with one or more of the message paths.

11. A method of determining delay components of an application sequence, comprising:

partitioning the application sequence into one or more message paths;

identifying a set of packets corresponding to each message path; and

for each message path;

for each packet in the message path;

identifying a time of occurrence of a total packet delay associated with the packet,

identifying a packet latency delay and a packet bandwidth delay within the total packet delay, and

identifying a packet congestion delay within the total packet delay, corresponding to a difference between the total packet delay and a sum of the packet latency delay and the packet bandwidth delay; and

for each time period in the application sequence;

identifying each of the total packet delays in the message path occurring at this time period,

if any of the total packet delays include a packet bandwidth delay occurring at this time period, identify this time period as including a message bandwidth delay, and

if none of the total packet delays include a packet bandwidth delay occurring at this time period, and any of the total packet delays include a packet congestion delay occurring at this time period, identify this time period as including a message congestion delay, and

providing a report based on one or more of the identified message congestion delays.

12. The method of claim 11, including

adjusting a time of occurrence of one or more packet bandwidth delays based on a concurrent time of occurrence of packet bandwidth delays among two or more conflicting packets.

13. The method of claim 12, including

identifying an ending time period corresponding to the packet latency delay of a last packet associated with an application message in the application sequence, and

identifying the ending time period as including a message latency delay.

14. The method of claim 13, including

identifying an interim time period between the ending time period and a start of a corresponding reply message in the application sequence, and

identifying the interim time period as including a message processing delay.

15. The method of claim 14, including

identifying each time period in the application sequence that has not been identified as including message congestion delay, message bandwidth delay, message latency delay, and message processing delay as including a message protocol delay.

16. The method of claim 12, including

identifying a message time period associated with one or more messages of the application sequence, and

identifying time periods in the message time period that have not been identified as including message congestion delay or message bandwidth delay as including a message protocol delay.

17. The method of claim 12, wherein

adjusting the time of occurrence includes identifying a time interval corresponding to the adjusting as including an application induced congestion delay.

18. The method of claim 17, including

identifying a concurrent period of occurrence of message bandwidth delay in a first message path and message congestion delay in one or more other message paths, and

identifying the concurrent period in the one or more other message paths as also including application induced congestion delay.

19. The method of claim 18, including

identifying each time period that includes a message congestion delay and does not include a message induced congestion delay as including a network congestion delay.

20. The method of claim 11, including

identifying a concurrent period of occurrence of message bandwidth delay in a first message path and message congestion delay in one or more other message paths, and

identifying the concurrent period in the one or more other message paths as including application induced congestion delay.

21. The method of claim 20, including

identifying each time period that includes a message congestion delay and does not include a message induced congestion delay as including a network congestion delay.

22. A method of determining one or more effects of modifying delays in an application sequence, comprising:

identifying a first sequence of message delay components in each message path of the application sequence, the message delay components including at least a network congestion delay, a self congestion delay, and a message bandwidth delay;

modifying one or more of the message delay components in the first sequence of each message path and correspondingly adjusting a time of occurrence of the message delay components to provide a contiguous second sequence of message delay components in each message path;

determining occurrences of self congestion delay in the second sequence of message delay components in each message path and correspondingly adjusting a time of occurrence of the message delay components to provide a contiguous third sequence of message delay components in each message path based on the occurrences of self congestion delay; and

identifying one or more differences between the first sequence of message delay components and the second sequence of message delay components of at least one message path.

23. The method of claim 22, wherein

modifying the one or more message delay components in the first sequence includes automatically removing occurrences of self congestion delay.

24. The method of claim 22, wherein

the message delay components also include a message latency delay and a message protocol.

25. The method of claim 24, wherein

the message delay components also include a message processing delay.

26. The method of claim 22, wherein

each message in each message path of the application sequence includes one or more packets, each packet having associated occurrences of packet bandwidth delay and packet congestion delay;

and

determining occurrences of self congestion delay includes determining periods of concurrent occurrences of packet bandwidth delay in a first message path and packet congestion delay in one or more second message paths.

27. A computer program on a computer readable medium that, when executed, causes a processor to effect a process comprising:

partitioning an application sequence into a plurality of message paths,

identifying a set of packets corresponding to each message path, each packet having an associated set of packet delay components,

determining a set of message delay components corresponding to each message path, based on the sets of packet delay components associated with the message path,

wherein

the set of packet delay components includes a packet bandwidth delay, and

determining the set of message delay components includes;

determining one or more occurrences of message bandwidth delay, based on occurrences of packet bandwidth delay in one or more of the sets of packet delay components associated with the message path, and

determining one or more occurrences of message congestion delay, based on an absence of occurrences of packet bandwidth delay in one or more of the sets of packet delay components associated with the message path.

28. The program of claim 27, wherein

determining the set of message delay components includes

determining one or more occurrences of message self-congestion delay, based on a concurrent occurrence of message bandwidth delay in at least two message paths, and

the process includes:

adjusting the set of message delay components corresponding to at least one of the at least two message paths based on the one or more occurrences of message self-congestion delay.

29. The program of claim 28, wherein

determining the set of message delay components includes

determining one or more occurrences of message cross-congestion delay, based on a concurrent occurrence of message bandwidth delay in at least two message paths, and

the process includes:

adjusting the set of message delay components corresponding to at least one of the at least two message paths based on the one or more occurrences of message cross-congestion delay.

30. The program of claim 27, wherein

the set of packet delay components includes a packet congestion delay, and

determining the set of message delay components includes

determining one or more occurrences of message protocol delay, based on an absence of occurrences of packet congestion delay and packet bandwidth delay associated with the message path.

31. The program of claim 27, wherein the process includes

displaying one or more of the sets of message delay components associated with one or more of the message paths.

32. The program of claim 27, wherein the process includes:

modifying one or more components of the determined sets of message delay components to produce a set of modified message delay components for each message path,

adjusting a time of occurrence of the modified message delay components in each message path,

determining one or more occurrences of message self-congestion delay, based on a concurrent occurrence of message bandwidth delay of the modified message delay components in at least two message paths,

adjusting the set of modified message delay components corresponding to at least one of the at least two message paths based on the one or more occurrences of message self-congestion delay,

identifying one or more differences between the sets of message delay components and the sets of modified delay components, and

displaying one or more of the sets of modified message delay components associated with one or more of the message paths.

33. The program of claim 27, wherein determining the one or more occurrences of message bandwidth delay and message congestion delay includes:

for each message path;

for each packet in the message path;

identifying a time of occurrence of a total packet delay associated with the packet,

identifying a packet latency delay and a packet bandwidth delay within the total packet delay, and

identifying a packet congestion delay within the total packet delay, corresponding to a difference between the total packet delay and a sum of the packet latency delay and the packet bandwidth delay; and

for each time period in the application sequence;

identifying each of the total packet delays in the message path occurring at this time period,

if any of the total packet delays include a packet bandwidth delay occurring at this time period, identify this time period as including a message bandwidth delay, and

if none of the total packet delays include a packet bandwidth delay occurring at this time period, and any of the total packet delays include a packet congestion delay occurring at this time period, identify this time period as including a message congestion delay.

34. The program of claim 33, wherein the process includes:

adjusting a time of occurrence of one or more packet bandwidth delays based on a concurrent time of occurrence of packet bandwidth delays among two or more conflicting packets.

35. The program of claim 34, wherein the process includes:

identifying an ending time period corresponding to the packet latency delay of a last packet associated with an application message in the application sequence, and

identifying the ending time period as including a message latency delay,

identifying an interim time period between the ending time period and a start of a corresponding reply message in the application sequence, and

identifying the interim time period as including a message processing delay, and

identifying each time period in the application sequence that has not been identified as including message congestion delay, message bandwidth delay, message latency delay, and message processing delay as including a message protocol delay.

36. The program of claim 33, wherein the process includes:

identifying a message time period associated with one or more messages of the application sequence, and

identifying time periods in the message time period that have not been identified as including message congestion delay or message bandwidth delay as including a message protocol delay.

37. The program of claim 33, wherein the process includes:

identifying a concurrent period of occurrence of message bandwidth delay in a first message path and message congestion delay in one or more other message paths, and

identifying the concurrent period in the one or more other message paths as including application induced congestion delay, and

identifying each time period that includes a message congestion delay and does not include a message induced congestion delay as including a network congestion delay.

38. A computer program on a computer readable medium that, when executed, causes a processor to determine one or more effects of modifying delays in an application sequence by effecting a process comprising:

identifying a first sequence of message delay components in each message path of the application sequence, the message delay components including at least a network congestion delay, a self congestion delay, and a message bandwidth delay;

modifying one or more of the message delay components in the first sequence of each message path and correspondingly adjusting a time of occurrence of the message delay components to provide a contiguous second sequence of message delay components in each message path;

determining occurrences of self congestion delay in the second sequence of message delay components in each message path and correspondingly adjusting a time of occurrence of the message delay components to provide a contiguous third sequence of message delay components in each message path based on the occurrences of self congestion delay; and

identifying one or more differences between the first sequence of message delay components and the second sequence of message delay components of at least one message path.

39. The program of claim 38, wherein

modifying the one or more message delay components in the first sequence includes automatically removing occurrences of self congestion delay.

40. The program of claim 38, wherein

each message in each message path of the application sequence includes one or more packets, each packet having associated occurrences of packet bandwidth delay and packet congestion delay;

and

determining occurrences of self congestion delay includes determining periods of concurrent occurrences of packet bandwidth delay in a first message path and packet congestion delay in one or more second message paths.