Validation of routing information in a network fabric

• US 10,411,996 B2
• Filed: 07/27/2017
• Issued: 09/10/2019
• Est. Priority Date: 06/19/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Pani, Ayas, Harneja, Sanchay
• Primary Examiner(s): Siddiqui, Kashif
• Application Number:
  US15/661,927
• Publication Number:
  US 20180367449A1
• Time in Patent Office: 775 Days
• CPC Class Codes: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 41/0686 Additional information in the notification, e.g. enhancement of specific meta-data
• CPC Class Codes: H04L 41/0853 by actively collecting configuration information or by backing up configuration information
• CPC Class Codes: H04L 41/0873 Checking configuration conflicts between network elements
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 41/22 comprising specially adapted graphical user interfaces [GUI]
• CPC Class Codes: H04L 41/40 using virtualisation of network functions or resources, e.g. SDN or NFV entities
• CPC Class Codes: H04L 43/0817 by checking functioning
• 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 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 45/488 using root node determination
• CPC Class Codes: H04L 45/586 of virtual routers
• CPC Class Codes: H04L 45/748 using longest matching prefix
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/70 Virtual switches

Abstract

Systems, methods, and computer-readable media for validating routing table information in a network. A network assurance appliance may be configured to retrieve routing table information from a plurality of nodes in a network fabric. The routing table information includes path information from at least one source node to at least one destination node. A graph representation of the routing table information is constructed with the at least one destination node as a sink vertex for the graph representation. The network assurance appliance determines, for each leaf node in the network fabric, whether the leaf node can reach the sink vertex based on the graph representation and determines that there is a misconfiguration of the network fabric based on whether each leaf node in the fabric can reach the sink vertex.

Claims

1. A computer-implemented method comprising:

retrieving routing table information from a plurality of nodes in a network fabric, the routing table information including path information from at least one source node to at least one destination node;

constructing a graph representation of the routing table information with the at least one destination node as a sink vertex for the graph representation;

determining whether each leaf node in the network fabric can reach the sink vertex based on the graph representation to yield a determination; and

determining a misconfiguration of the network fabric based on the determination and without testing the network fabric and/or data packet flow.

2. The computer-implemented method of claim 1, further comprising:

generating an event specifying the misconfiguration.

3. The computer-implemented method of claim 2, further comprising:

providing, based on the event, a user interface comprising network status information.

4. The computer-implemented method of claim 3, further comprising:

calculating, based on the event, a health score for one or more endpoints, wherein the network status information comprises the health score for the one or more endpoints.

5. The computer-implemented method of claim 2, wherein the event is associated with a severity level and an event type.

6. The computer-implemented method of claim 1, wherein the network fabric comprises a software-defined network (SDN).

7. The computer-implemented method of claim 1, further comprising:

determining that a loop exists in the graph representation of the routing table information; and

generating a node loop event based on the loop.

8. The computer-implemented method of claim 1, further comprising:

determining that no leaf node in the network fabric can reach the sink vertex based on the graph representation; and

generating a node isolation event.

9. The computer-implemented method of claim 1, further comprising:

determining that at least one leaf node in the network fabric cannot reach the sink vertex based on the graph representation; and

generating a node black hole event.

10. The computer-implemented method of claim 1, further comprising:

querying each node the plurality of nodes in the network fabric for information contained in a Longest Prefix Match (LPM) routing table,

wherein the routing table information comprises the information contained in the LPM routing table for each node in the plurality of nodes.

11. A system comprising:

one or more processors; and

at least one computer-readable storage medium having stored therein instructions which, when executed by the one or more processors, cause the system to;

retrieve routing table information from nodes in a network fabric, the routing table information including path information from at least one source node to a destination node;

determine whether each source node in the network fabric can reach the destination node based on the routing table information to yield a determination;

determine a misconfiguration of the network fabric based on the determination and without testing the network fabric and/or data packet flow; and

generate an event specifying the misconfiguration.

12. The system of claim 11, wherein the instructions further cause the system to provide, based on the event, a user interface comprising network status information.

13. The system of claim 11, wherein the instructions further cause the system to generate, based on the event, a notification comprising network status information for a network administrator.

14. The system of claim 13, wherein the instructions further cause the system to calculate, based on the event, a health score for one or more endpoints,

wherein the network status information comprises the health score for the one or more endpoints.

15. The system of claim 11, wherein the instructions further cause the system to:

construct a graph representation of the routing table information with the destination node as a sink vertex for the graph representation;

determine that a loop exists in the graph representation of the routing table information; and

generate a node loop event based on the loop.

16. The system of claim 11, wherein the instructions further cause the system to:

determine that no leaf node in the at least one source node can reach the destination node based on the routing table information; and

generate a node isolation event.

17. The system of claim 11, wherein the instructions further cause the system to:

determine that the at least one source node cannot reach the destination node based on the routing table information; and

generate a node black hole event.

18. A non-transitory computer-readable storage medium comprising instructions stored therein instructions which, when executed by one or more processors, cause the one or more processors to perform operations including:

querying each node of a plurality of nodes in a network fabric for routing table information, the routing table information including path information from at least one source node to a destination node;

determining whether each source node in the network fabric can reach the destination node based on the routing table information to yield a determination;

determining a misconfiguration of the network fabric based on the determination and without testing the network fabric and/or data packet flow; and

providing a user interface based on the misconfiguration.

19. The non-transitory computer-readable storage medium of claim 18, wherein the instructions further cause the one or more processors to perform operations including:

determining that the at least one source node cannot reach the destination node based on the routing table information,

wherein the misconfiguration is a black hole event.

20. The non-transitory computer-readable storage medium of claim 18, wherein the instructions further cause the one or more processors to perform operations including:

constructing a graph representation of the routing table information with the destination node as a sink vertex for the graph representation; and

determining that a loop exists in the graph representation of the routing table information,

wherein the misconfiguration is a node loop event.