Detection of failures in network devices

• US 10,461,992 B1
• Filed: 09/26/2017
• Issued: 10/29/2019
• Est. Priority Date: 09/26/2017
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sagar, Gaurav, Nguyen, Mike Dang, Parini, Alessandro
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): Loo, Juvena W
• Application Number:
  US15/716,253
• Time in Patent Office: 763 Days
• Field of Search: None
• CPC Class Codes: H04L 41/046 comprising network management agents or mobile agents therefor
• 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/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 43/028 by filtering
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 43/20 the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV
• CPC Class Codes: H04L 43/50 Testing arrangements
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric

Abstract

In one embodiment, detection of failures in a network device can be achieved by obtaining a last hop of partial traceroutes. For example, the last hops of the partial traceroutes detected in a time period can be sorted by frequency of occurrence. Multiple clusters can be generated, one with last hops that are most frequent and at least one other with the last hops that are less frequent. The hop with the highest frequency and the last hop with the second highest frequency can be compared. If the last hop with the highest frequency exceeds the second highest frequency by a predetermined amount, then the last hop with the highest frequency is alarmable.

Claims

1. A method of monitoring network devices for failures, the method comprising:

transmitting packets in a network using a network monitoring agent executing on a server computer;

determining that multiple packets transmitted by the network monitoring agent did not reach respective destination addresses of the multiple packets;

transmitting traceroute packets in order to determine why the multiple packets did not reach the destination addresses;

determining a set of frequencies of last hops associated with the traceroute packets that did not reach the destination addresses;

clustering the set of frequencies into first and second groups, wherein the first group is a high-frequency group of last hops and the second group is a lower-frequency group of last hops;

comparing a most frequent last hop in the first group with another last hop in the second group within the set of frequencies; and

determining a network device associated with the most frequent last hop is defective when its frequency exceeds the other last hop frequencies by a predetermined amount; and

re-routing network traffic around the network device.

2. The method of claim 1, further including tracking the traceroute packets that were transmitted over a predetermined period of time.

3. The method of claim 1, further including inserting dummy last hops with a predetermined frequency count into the second group so as to obtain the second group that is within the set of frequencies.

4. The method of claim 1, further including filtering non-border network nodes from the set of frequencies.

5. The method of claim 1, further including determining that there are at least two failures for a same device over different time periods.

6. One or more computing devices, comprising:

one or more processing units; and

one or more network interfaces;

wherein the one or more computing devices are configured to perform operations for monitoring a plurality of network devices in a computer network, the operations comprising;

transmitting traceroutes through the plurality of network devices;

for traceroutes that do not reach a destination, performing frequency analysis on last hops associated with the traceroutes, wherein the frequency analysis includes determining a set of frequencies of last hops associated with the traceroutes that did not reach the destination, clustering the set of frequencies into first and second groups of different frequencies and comparing a most frequent last hop in the first group with another last hop in the second group within the set of frequencies; and

determining that at least one network device is defective based on the frequency analysis including that the most frequent last hop in the first group exceeds a frequency of the last hop in the second group by a predetermined amount.

7. The one or more computing devices of claim 6, wherein the transmitting of the traceroutes is over multiple rolling time windows, and wherein the frequency analysis is repeated for each rolling time window.

8. The one or more computing devices of claim 7, wherein the determining that the at least one network device is defective includes determining that the at least one network device is defective in multiple of the rolling time windows.

9. The one or more computing devices of claim 6, the operations further including inserting data for faux network devices into the frequency analysis;

and

comparing the frequency analysis of the at least one network device to a frequency analysis of one of the faux network devices and determining the at least one network device is defective based on the comparison.

10. The one or more computing devices of claim 6, the operations further including grouping results of the frequency analysis using a clustering algorithm to form at least two groups of the network devices.

11. The one or more computing devices of claim 6, wherein the plurality of network devices are within a border network coupling a multi-tenant environment to a single-tenant environment.

12. The one or more computing devices of claim 11, the operations further including filtering network devices that are not within the border network.

13. The one or more computing devices of claim 6, wherein the plurality of network devices are within a network fabric and wherein the one or more computing devices are server computers positioned external to the network fabric.

14. The one or more computing devices of claim 6, the operations further including if a number of network devices that are defective is greater than a predetermined number, discarding the frequency analysis.

15. A computer-readable storage medium, which is non-transitory, including instructions that upon execution cause a computer system to:

transmit traceroutes through a network fabric;

determine partial traceroutes;

determine last hops associated with the partial traceroutes;

calculate a frequency associated with each of the last hops;

clustering the frequency associated with each of the last hops into first and second groups including a high-frequency group and low-frequency group; and

determine whether a network device within the network fabric is defective based on the frequency by comparing a most frequent last hop in the first group with another last hop in the second group.

16. The computer-readable storage medium according to claim 15, wherein the determining whether the network device is defective includes determining two most frequent last hops;

and

wherein the instructions, upon execution, further cause the computer system to;

compare a difference between the frequency of each of the two most frequent last hops; and

determine the network device is defective if a result of the comparison exceeds a threshold.

17. The computer-readable storage medium according to claim 15, wherein the instructions, upon execution, further cause the computer system to:

filter the partial traceroutes so that only partial traceroutes for network devices in a border network are analyzed.

18. The computer-readable storage medium according to claim 15, wherein the instructions, upon execution, further cause the computer system to:

transmit the partial traceroutes from an agent within a multi-tenant environment, or single-tenant environment, or border fabric.

19. The computer-readable storage medium according to claim 15, wherein the instructions, upon execution, further cause the computer system to:

perform a clustering algorithm on the calculated frequencies to determine two sets of frequencies that are the largest.

20. The computer-readable storage medium according to claim 19, wherein the instructions, upon execution, further cause the computer system to:

compute a difference between the at least two frequencies within the two sets, and wherein the determining whether the network device is defective includes determining if the difference exceeds a threshold.