Identifying a source of packet drops in a network

• US 9,979,619 B2
• Filed: 11/24/2015
• Issued: 05/22/2018
• Est. Priority Date: 11/24/2015
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Thubert, Pascal, Wetterwald, Patrick, Levy-Abegnoli, Eric
• Primary Examiner(s): HSU, ALPUS
• Application Number:
  US14/950,042
• Publication Number:
  US 20170149639A1
• Time in Patent Office: 910 Days
• CPC Class Codes: H04L 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/44 Star or tree networks
• 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/0835 One way packet loss
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: Y04S 40/00 Systems for electrical power generation, transmission, distribution or end-user application management characterised by the use of communication or information technologies, or communication or information technology specific aspects supporting them
• CPC Class Codes: Y04S 40/18 Network protocols supporting networked applications, e.g. including control of end-device applications over a network

Abstract

In one embodiment, a device in a network performs a first comparison between observed and expected packet error rates for a first path in the network. The device identifies one or more intersecting paths in the network that intersect the first path. The device performs one or more additional comparisons between observed and expected packet error rates for the intersecting paths that intersect the first path. The device identifies a particular node along the first path as a source of packet drops based on the first comparison between the observed and expected packet error rates for the first path and on the one or more additional comparisons between the observed and expected packet error rates for the intersecting paths that intersect the first path.

Claims

1. A method, comprising:

obtaining, by a device in a network, observed and expected packet error rates for a first path in the network;

performing, by the device, a first comparison between the observed and expected packet error rates for the first path in the network;

identifying, by the device, one or more intersecting paths in the network that intersect the first path, wherein an intersecting path is a network path that shares at least one node or link with first path;

obtaining, by the device, observed and expected error rates for the interesting paths that intersect the first path;

performing, by the device, one or more additional comparisons between observed and expected packet error rates for the intersecting paths that intersect the first path; and

identifying, by the device, a particular node along the first path as a source of packet drops by process elimination based on the first comparison between the observed and expected packet error rates for the first path and on the one or more additional comparisons between the observed and expected packet error rates for the intersecting paths that intersect the first path, wherein the device analyzes behaviors of the intersecting paths to identify the particular node through process of elimination.

2. The method as in claim 1, wherein performing the first comparison between the observed and expected packet error rates for the first path comprises:

determining that a set of packets were communicated via the first path; and

analyzing the set of packet to determine the observed packet error rate for the first path.

3. The method as in claim 2, wherein performing the first comparison between the observed and expected packet error rates for the first path further comprises:

calculating the expected packet error rate for the first path using link metrics for links along the first path.

4. The method as in claim 1, further comprising:

in response to device not having enough information to identify the source of packet drops;

causing, by the device, one or more nodes along the one or more intersecting paths that intersect the first path to send packets along the one or more intersecting paths for observation; and

determining, by the device, the observed packet error rates for the one or more intersecting paths by analyzing the packets sent along the one or more intersecting paths.

5. The method as in claim 4, wherein causing the one or more nodes along the one or more intersecting paths to send packets along the one or more intersecting paths for observation comprises:

sending an instruction to the one or more nodes to send the packets along the one or more intersecting paths for observation, wherein the instruction specifies one or more of;

a time at which the packets should be sent, a priority, or a packet size for the packets.

6. The method as in claim 4, wherein causing the one or more nodes along the one or more intersecting paths to send packets along the one or more intersecting paths for observation comprises:

sending a multicast instruction to all nodes along the intersecting path to send the packets along the one or more intersecting paths for observation.

7. The method as in claim 4, wherein the device causes the one or more nodes along the one or more intersecting paths to send the packets along the one or more intersecting paths for observation, in response to determining that the source of the packet drops along the first path cannot be identified from existing traffic in the network.

8. The method as in claim 1, wherein performing the first comparison between observed and expected packet error rates for the first path in the network comprises:

using, by the device, a machine learning process to determine whether a discrepancy exists between the observed and expected packet error rates for the first path.

9. The method as in claim 1, further comprising:

causing, by the device, a change to the first path in the network based on the identified source of the packet drops.

10. The method as in claim 1, further comprising:

performing, by the device, an analysis of performance requirements associated with traffic sent along the first path; and

causing, by the device, at least a portion of the traffic sent along the first path to be routed via the identified source of the packet drops based on the analysis of the performance requirements associated with the traffic.

11. The method as in claim 1, further comprising:

causing, by the device, the node identified as the source of the packet drops to become a leaf in a routing topology used in the network.

12. The method as in claim 1, further comprising:

causing, by the device, a source of traffic sent via the first path to send packets according to a different 6TiSCH track, wherein 6TiSCH track represents a given path in the network.

13. An apparatus, comprising:

one or more network interfaces to communicate with a network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed configured to;

obtain observed and expected packet error rates for a first path in the network;

perform a first comparison between the observed and expected packet error rates for the first path in the network;

identify one or more intersecting paths in the network that intersect the first path, wherein an intersecting path is a network path that shares at least one node or link with first path;

obtain observed and expected error rates for the interesting paths that intersect the first path;

perform one or more additional comparisons between observed and expected packet error rates for the intersecting paths that intersect the first path; and

identify a particular node along the first path as a source of packet drops by process elimination based on the first comparison between the observed and expected packet error rates for the first path and on the one or more additional comparisons between the observed and expected packet error rates for the intersecting paths that intersect the first path, wherein the device analyzes behaviors of the intersecting paths to identify the particular node through process of elimination.

14. The apparatus as in claim 13, wherein the apparatus performs the first comparison between the observed and expected packet error rates for the first path by:

determining that a set of packets were communicated via the first path; and

analyzing the set of packet to determine the observed packet error rate for the first path.

15. The apparatus as in claim 14, wherein the apparatus performs the first comparison between the observed and expected packet error rates for the first path further by:

calculating the expected packet error rate for the first path using link metrics for links along the first path.

16. The apparatus as in claim 13, wherein the process when executed is further configured to:

in response to device not having enough information to identify the source of packet drops;

cause one or more nodes along the one or more intersecting paths that intersect the first path to send packets along the one or more intersecting paths for observation; and

determine the observed packet error rates for the one or more intersecting paths by analyzing the packets sent along the one or more intersecting paths.

17. The apparatus as in claim 16, wherein the apparatus causes the one or more nodes along the one or more intersecting paths to send packets along the one or more intersecting paths for observation by:

sending an instruction to the one or more nodes to send the packets along the one or more intersecting paths for observation, wherein the instruction specifies one or more of;

a time at which the packets should be sent, a priority, or a packet size for the packets.

18. The apparatus as in claim 16, wherein the apparatus causes the one or more nodes along the one or more intersecting paths to send the packets along the one or more intersecting paths for observation, in response to determining that the source of the packet drops along the first path cannot be identified from existing traffic in the network.

19. The apparatus as in claim 13, wherein the process when executed is further configured to:

perform analysis of performance requirements associated with traffic sent along the first path; and

cause at least a portion of the traffic sent along the first path to be routed via the identified source of the packet drops based on the analysis of the performance requirements associated with the traffic.

20. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor configured to:

obtain observed and expected packet error rates for a first path in the network;

perform a first comparison between the observed and expected packet error rates for the first path in the network;

identify one or more intersecting paths in the network that intersect the first path, wherein an intersecting path is a network path that shares at least one node or link with first path;

obtain observed and expected error rates for the interesting paths that intersect the first path;

perform one or more additional comparisons between observed and expected packet error rates for the intersecting paths that intersect the first path; and

identify a particular node along the first path as a source of packet drops by process elimination based on the first comparison between the observed and expected packet error rates for the first path and on the one or more additional comparisons between the observed and expected packet error rates for the intersecting paths that intersect the first path, wherein the device analyzes behaviors of the intersecting paths to identify the particular node through process of elimination.