Monitoring and detecting causes of failures of network paths

• US 9,385,917 B1
• Filed: 03/31/2011
• Issued: 07/05/2016
• Est. Priority Date: 03/31/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Khanna, Richendra, Wallace, Edward L., Brar, Jagwinder Singh, Marr, Michael David, McKelvie, Samuel J., DeSantis, Peter N., Nowland, Ian P., Klein, Matthew D., Mason, Justin, Gabrielson, Jacob
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Shand, Roberta A
• Application Number:
  US13/077,589
• Time in Patent Office: 1,923 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 41/0645 by additionally acting on or stimulating the network after receiving notifications
• CPC Class Codes: H04L 41/065 involving logical or physical relationship, e.g. grouping and hierarchies
• CPC Class Codes: H04L 41/0668 by dynamic selection of recovery network elements, e.g. replacement by the most appropriate element after failure
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/0835 One way packet loss
• CPC Class Codes: H04L 43/0858 One way delays
• CPC Class Codes: H04L 43/103 with adaptive polling, i.e. dynamically adapting the polling rate
• CPC Class Codes: H04L 45/22 Alternate routing

Abstract

Generally described, systems and methods are provided for monitoring and detecting causes of failures of network paths. The system collects performance information from a plurality of nodes and links in a network, aggregates the collected performance information across paths in the network, processes the aggregated performance information for detecting failures on the paths, analyzes each of the detected failures to determine at least one root cause, and initiates a remedial workflow for the at least one root cause determined. In some aspects, processing the aggregated information may include performing a statistical regression analysis or otherwise solving a set of equations for the performance indications on each of a plurality of paths. In another aspect, the system may also include an interface which makes available for display one or more of the network topology, the collected and aggregated performance information, and indications of the detected failures in the topology.

Claims

1. A computer-implemented method for determining the performance of a network, the method comprising:

generating a topology for the network;

identifying two or more available paths between a first origin node and a first destination node based on the generated topology;

sending two or more packets from the first origin node to the first destination node, wherein the two or more packets travel through intermediate nodes and links between the first origin node and the first destination node;

causing the intermediate nodes to transmit the two or more packets on the two or more available paths between the first origin and destination nodes, wherein causing the intermediate nodes to transmit the two or more packets comprises adjusting at least one port address for each of the two or more packets along all of the two or more available paths;

determining a respective indication of performance for each of the two or more available paths based on the transmission of the two or more packets, at a specified frequency; and

determining an indication of performance for at least one of the intermediate nodes or at least one of the links based on indications of performance of the two or more available paths.

2. The computer-implemented method of claim 1, wherein causing the intermediate nodes to transmit the two or more packets comprises adjusting a destination port address for each of the two or more packets.

3. The computer-implemented method of claim 1, wherein causing the intermediate nodes to transmit the two or more packets comprises adjusting a source port address on at least one of the first origin node and the first destination node.

4. The computer-implemented method of claim 1, further comprising sending two or more other packets from a second origin node to a second destination node, wherein at least one of the second origin node is different than the first origin node and the second destination node is different than the first destination node.

5. The computer-implemented method of claim 1, wherein determining a respective indication of performance for each of the two or more available paths comprises calculating a packet loss on each of the two or more available paths.

6. The computer-implemented method of claim 1, wherein determining a respective indication of performance for each of the two or more available paths comprises calculating a latency on each of the two or more available paths.

7. The computer-implemented method of claim 1, further comprising generating the topology of the network again, based on the indications of performance of the two or more available paths.

8. The computer-implemented method of claim 1, wherein the specified frequency is static.

9. The computer-implemented method of claim 1, further comprising dynamically adjusting the specified frequency.

10. The computer-implemented method of claim 9, wherein the specified frequency is dynamically adjusted based on business logic rules.

11. The computer-implemented method of claim 9, wherein the specified frequency is adjusted based on the indication of performance determined.

12. A computing system for determining performance of a network path, the system comprising:

a network topology generator to generate topology of a network;

a controller to;

identify two or more available paths between an origin node and a destination node based on the generated topology; and

control intermediate nodes between the origin node and the destination node in the network in order to transmit two or more packets between the origin and destination nodes on the two or more available paths,

wherein the controller controls at least one of the intermediate nodes to adjust at least one port address for each of the two or more packets along all of the two or more available paths, and

wherein the two or more packets travel through at least one of the intermediate nodes and at least one link between the origin node and the destination node; and

a collector to;

determine a respective indication of performance for each of the two or more available paths based on the transmission of the two or more packets, at a specified frequency; and

determine an indication of performance for at least one of the intermediate nodes or the at least one link based on indications of performance of the two or more available paths.

13. The computing system of claim 12, wherein the controller controls the intermediate nodes by adjusting a destination port address associated with at least one of the origin node and the destination node for each of the two or more packets.

14. The computing system of claim 12, wherein the respective indication of performance for each of the two or more available paths comprises a respective packet loss on each of the two or more available paths.

15. The computing system of claim 12, wherein the respective indication of performance for each of the two or more available paths comprises a respective latency on each of the two or more available paths.

16. The computing system of claim 12, wherein the network topology generator further generates the topology of the network again, based on the indications of performance collected for the two or more available paths.

17. The computing system of claim 12, wherein the specified frequency is static.

18. The computing system of claim 12, wherein the specified frequency is dynamically adjustable.

19. The computing system of claim 18, wherein the specified frequency is dynamically adjustable based on business logic rules.

20. A non-transitory, computer-readable medium having a computer-executable component, the computer-executable component comprising:

a network topology generating component for generating a topology of the network;

a path selecting component for;

identifying two or more available paths between an origin node and a destination node based on the generated topology; and

causing intermediate nodes between the origin node and the destination node in the network to transmit two or more packets between the origin node and the destination node on the two or more available paths,

wherein causing the intermediate nodes to transmit the two or more packets comprises adjusting at least one port address associated for each of the two or more packets along all of the two or more available paths, and

wherein the two or more packets travel through at least one of the intermediate nodes and at least one link between the origin node and the destination node; and

a collecting component for;

determining a respective indication of performance for each of the two or more available paths based on the transmission of the two or more packets, at a specified frequency; and

determining an indication of performance for at least one intermediate node or the at least one link based on indications of performance of the two or more available paths.

21. The non-transitory, computer-readable medium of claim 20, wherein causing the intermediate nodes to transmit two or more packets comprises adjusting a destination port address associated with at least one of the origin node and the destination node for each of the two or more packets.

22. The non-transitory, computer-readable medium of claim 20, wherein the network topology generating component generates the topology of the network again, based on the indications of performance of the two or more available paths.

23. The non-transitory, computer-readable medium of claim 20, wherein the specified frequency is static.

24. The non-transitory, computer-readable medium of claim 20, wherein the specified frequency is dynamically adjustable.

25. The non-transitory, computer-readable medium of claim 20, wherein the specified frequency is dynamically adjustable based on business logic rules.