Determining locations of network failures

• US 9,104,543 B1
• Filed: 04/06/2012
• Issued: 08/11/2015
• Est. Priority Date: 04/06/2012
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Cavanagh, Eoin F., Stewart, Michael S., Sequeira, Karlton D.
• Primary Examiner(s): Ko, Chae
• Application Number:
  US13/441,179
• Time in Patent Office: 1,222 Days
• Field of Search: 714/43
• US Class Current: 1/1
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/221 to test buses, lines or interfaces, e.g. stuck-at or open line faults
• CPC Class Codes: H04L 41/0677 Localisation of faults
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/142 using statistical or mathematical methods
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters

Abstract

Generally described, systems and methods are provided for detecting locations of failures of network paths. The system collects 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, and determines at least one location for network failures. In some aspects, processing the aggregated information may include determining the performance information on each of the nodes and links in the network. The performance information on each of the nodes and links may be determined by application of a stochastic gradient descent (SGD) technique.

Claims

1. A system for detecting locations of network failures, the system comprising:

a network failure location detection component comprising one or more computing devices configured to execute specific instructions, the network failure location detection component operable to;

measure a communication attribute across each of a plurality of network paths between an origin node and a destination node in a network based on at least one packet delivered between the origin node and the destination node, wherein each one of the network paths includes at least two nodes and at least one link, and wherein the communication attribute is indicative of at least one network failure;

for at least one path among the plurality of network paths, process the measured communication attribute measured for each of plurality of network paths to determine a respective communication attribute for each of the at least two nodes and the at least one link included in the at least one path;

determine at least one location for the at least one network failure, among the at least two nodes and the at least one link included in the at least one path, based on the respective communication attribute of the at least two nodes and the at least one link in the at least one path, wherein the respective communication attribute is derived from the communication attribute measured based on at least one packet delivered between the origin node and the destination node;

store at least one of the measured communication attributes, the determined communication attributes and the determined at least one location; and

make available for display the determined at least one location.

2. The system of claim 1, wherein the network failure location detection component is operable to determine the respective communication attribute for each of the at least two nodes and the at least one link included in the at least one path by applying a stochastic gradient descent technique.

3. The system of claim 2, wherein applying a stochastic gradient descent technique comprises:

initializing an estimate for the respective communication attribute associated with the at least two nodes and the at least one link; and

adjusting the estimate for the respective communication attribute associated with the at least two nodes and the at least one link based on the measured communication attribute across the at least one path.

4. The system of claim 3, wherein initializing the estimate for the respective communication attribute associated with the at least two nodes and the at least one link is based on the measured communication attribute across the at least one path.

5. The system of claim 3, wherein the adjusting the estimate for the respective communication attribute is repeated for a number of iterations.

6. The system of claim 3, wherein adjusting the estimate is based on minimizing a loss function.

7. The system of claim 6, wherein the loss function is a square of a difference between the measured communication attribute across the at least one path and an estimated communication attribute across the at least one path.

8. The system of claim 7, wherein the estimated communication attribute across the at least one path comprises a product of the estimates of the respective communication attributes associated with the at least two nodes and the at least one link on the at least one path.

9. The system of claim 7, wherein the estimated communication attribute across the at least one path comprises a sum of the estimates of the respective communication attributes associated with the at least two nodes and the at least one link on the at least one path.

10. A computer-implemented method comprising:

measuring a communication attribute across each of a plurality of network paths from an origin node and a destination node in a network based on at least one packet delivered between the origin node and the destination node, wherein each one of the network paths includes at least two nodes and at least one link, and wherein the communication attribute is indicative of at least one network failure;

for at least one path from the plurality of network paths, processing the measured communication attribute across at least one path for determining a respective communication attribute for each of at least two nodes and at least one link included in the at least one path;

determining at least one location for the at least one network failure, among the at least two nodes and the at least one link included in the at least one path, based on the respective communication attributes associated with the at least two nodes and the at least one link on the at least one path, wherein each respective communication attribute is derived from the communication attribute measured based on at least one packet delivered between the origin node and the destination node.

11. The computer-implemented method of claim 10, wherein determining at least one location based on the determined respective communication attributes comprises identifying at least one of a node and a link with a determined respective communication attribute above a predetermined threshold for that communication attribute.

12. The computer-implemented method of claim 10, wherein the measured communication attribute is processed for only a subset of the plurality of network paths for which the communication attribute is measured.

13. The computer-implemented method of claim 12, wherein the subset is determined based on a value of the measured communication attribute.

14. The computer-implemented method of claim 10, wherein the communication attribute comprises a packet transfer rate.

16. The non-transitory, computer-readable medium of claim 14, wherein processing a subset of the measured performance indicators comprises selecting at least one of the plurality of paths based on the measured performance indicators.

17. The non-transitory, computer-readable medium of claim 16, wherein selecting a subset of the plurality of links based on the measured performance indicators comprises selecting a path for which respective measured performance indicator is below a predetermined threshold.

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

a network failure location detection component for;

determining a plurality of paths between two nodes in the network;

measuring performance indicators of the plurality of paths between the two nodes based on at least one packet delivered between the two nodes, wherein at least one of the performance indicators is indicative of at least one network failure;

processing a subset of the measured performance indicators to determine a respective communication attribute for components of a subset of the plurality of paths; and

determining at least one location associated with the at least one network failure, among the components of the subset of the plurality of paths, based on the respective communication attribute of the components, wherein the respective communication attribute is derived from the performance indicators measured based on at least one packet delivered between the two nodes.