Determining locations of network failures

• US 9,197,495 B1
• Filed: 02/11/2013
• Issued: 11/24/2015
• Est. Priority Date: 02/11/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Roy, Sonali, Thompson, James Michael, Rauser, John Michael
• Primary Examiner(s): Hamza, Faruk
• Assistant Examiner(s): DECKER, CASSANDRA L
• Application Number:
  US13/764,706
• Time in Patent Office: 1,016 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: H04L 41/0677 Localisation of faults
• 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
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/0894 Packet rate

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 and optimization of an objective function.

Claims

1. A computer-implemented method for detecting locations of network failures, the method comprising:

representing a network using a binomial likelihood function;

measuring a packet transfer rate across each of a plurality of network paths in the network respectively, wherein each one of the network paths includes at least two nodes and at least one link;

for at least one path among the plurality of network paths, determining a respective packet transfer rate for each of the at least two nodes and the at least one link included in the at least one path by applying a limited memory Broyden-Fletcher-Goldfarb-Shanno with bound constraints (L-BFGS-B) algorithm to update a respective estimate of the respective packet transfer rate for each of the at least two nodes and the at least one link based on the measured packet transfer rate across the at least one path; and

determining at least one location for at least one network failure based on the determined respective packet transfer rate for each of the at least two nodes and the at least one link included in the at least one path.

2. The method of claim 1, wherein determining a respective packet transfer rate for each of the at least two nodes and the at least one link in the at least one path comprises:

initializing an estimate for the respective packet transfer rate for each of the at least two nodes and the at least one link;

determining a number of packets sent on the at least one path;

determining a number of packets not received on the at least one path;

determining a likelihood of observing the measured packet transfer rate across the at least one path given the respective estimates for the respective packet transfer rate for the at least two nodes and the at least one link in the at least one path, the determined number of packets sent and the determined number of packets not received; and

updating the respective estimates for the respective packet transfer rates for the at least two nodes and the at least one link, using the limited memory Broyden-Fletcher-Goldfarb-Shanno with bound constraints (L-BFGS-B) algorithm, based on the likelihood determined.

3. The method of claim 2, wherein initializing the estimate for the respective packet transfer rate is based on the measured packet transfer rate across the at least one path.

4. The method of claim 2, wherein determining a likelihood of observing the measured packet transfer rate is repeated for a number of iterations.

5. The method of claim 2, wherein the binomial likelihood function comprises the likelihood of observing the determined number of packets sent and the determined number of packets not received on the at least one path given the measured packet transfer rate across the at least one path.

6. The method of claim 2, further comprising:

processing the measured packet transfer rate across the at least one path using z-scores.

7. The method of claim 6, wherein using z-scores comprises:

determining a respective packet transfer rate for each of the at least two nodes and the at least one link included in the at least one path; and

determining if the respective packet transfer rate exceeds a predetermined threshold on the at least one path.

8. The method of claim 1, further comprising:

storing the measured packet transfer rates, the determined respective packet transfer rates, and the determined at least one location.

9. The method of claim 1, further comprising:

making available for display the determined at least one location.

10. 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;

represent a network using a binomial likelihood model;

measure a communication attribute across each of a plurality of network paths in the network respectively, wherein each one of the network paths includes at least two nodes and at least one link;

for at least one path among the plurality of network paths, 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 by applying a limited memory Broyden-Fletcher-Goldfarb-Shanno with bound constraints (L-BFGS-B) algorithm to update a respective estimate of the respective communication attribute for each of the at least two nodes and the at least one link based on the measured communication attribute across the at least one path; and

determine at least one location for at least one network failure based on the determined respective communication attributes associated with the at least two nodes and the at least one link included in the at least one path.

11. The system of claim 10, wherein the communication attribute is at least one of a packet transfer rate, a loss, or a packet loss rate.

12. The system of claim 10, wherein the communication attribute is at least one of jitter and latency.

13. The system of claim 10, wherein the network failure location detection component is further operable to process the measured communication attribute across the at least one path using z-scores.

14. The system of claim 10, wherein the network failure location detection component is operable to determine at least one location for at least one network failure based on the determined respective communication attributes by identifying at least one node or link with a determined respective communication attribute above a predetermined threshold.

15. The system of claim 10, wherein the at least one path is a subset of the plurality of network paths.

16. The system of claim 15, wherein the subset of the plurality of network paths is determined based on the respective communication attribute measured across each of the plurality of network paths.

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

a network failure location detection component for;

representing a network using a binomial likelihood function;

measuring a communication attribute across each of a plurality of paths in the network respectively, wherein each path includes at least two nodes and at least one link, and wherein the communication attribute is indicative of a network failure;

for at least one path among the plurality of network paths, determining 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 by applying a limited memory Broyden-Fletcher-Goldfarb-Shanno with bound constraints (L-BFGS-B) algorithm to update a respective estimate of the respective communication attribute for each of the at least two nodes and the at least one link based on the measured communication attribute across the at least one path; and

determining at least one location for the network failure based on the respective determined communication attributes associated with the at least two nodes and at least one link on the at least one path.

18. The non-transitory, computer-readable medium of claim 17, wherein determining at least one location for the network failure comprises determining an entity with a respective communication attribute beyond a predetermined threshold.