Root cause analysis approach with candidate elimination using network virtualization

• US 20080114581A1
• Filed: 06/21/2007
• Published: 05/15/2008
• Est. Priority Date: 11/15/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Meir, Gil, Kor, Liah, Etzioni, Zohar, Lifshitz, Gadi
• Granted Patent: US 8,583,779 B2
• Time in Patent Office: Days
• US Class Current: 703/13
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0631 using root cause analysis; using analysis of correlation between notifications, alarms or events based on decision criteria, e.g. hierarchy, tree or time analysis
• CPC Class Codes: H04L 41/065 involving logical or physical relationship, e.g. grouping and hierarchies
• 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/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]

Abstract

Root cause analysis in a communication network includes eliminating candidate events using a computer-implemented method, comprising creating a virtual network model that describes nodes and links of the network at a plurality of time periods; receiving from the network a first event that indicates a problem in the network; receiving a set of second events comprising candidates for a root cause of the first event; determining a network topological indicator from the first event; determining a network implication of the first event based on the topological indicator; based on the network implication and a time value of the first event, retrieving data from the virtual network model that indicates a path between nodes associated with the first event at a time at which the first event occurred; removing, from the set of second events, all events that are not on the path between devices associated with the first event.

Claims

1. A computer-implemented method, comprising:

creating and storing a virtual network model that describes nodes and links of a data processing network at a plurality of time periods;

receiving from the network a first event that indicates a problem in the network;

receiving a set of second events comprising candidates for a root cause of the first event;

determining a network topological indicator from the first event;

determining a network implication of the first event based on the topological indicator;

based on the network implication and a time value of the first event, retrieving data from the virtual network model that indicates a path between nodes associated with the first event at a time at which the first event occurred;

removing, from the set of second events, all events that are not on the path between devices associated with the first event.

2. The method of claim 1 wherein the virtual network model comprises a directed acyclic graph.

3. The method of claim 1 wherein the topological indicator specifies that a device is unreachable or a BGP neighbor is lost.

4. The method of claim 1 further comprising translating the first event to a source point and a destination point in the virtual network model, wherein the destination point is not reachable in the network from the source point.

5. The method of claim 2 wherein each of the second events represents a broken edge of the graph.

6. The method of claim 2, wherein the virtual network model comprises a directed acyclic graph, further comprising translating the first event to a source point and a destination point in the virtual network model, wherein the destination point is not reachable in the network from the source point, and wherein the retrieving and removing includes processing all paths in the graph from the source point to the destination point.

7. A computer-implemented method, comprising:

creating and storing a directed acyclic graph G=(V, E) that describes nodes and links of a data processing network at a plurality of time periods, wherein V comprises vertices and E comprises edges, and wherein a set S⊂

E is marked in the graph;

receiving from the network a first event that indicates a problem in the network;

receiving a set of second events comprising candidates for a root cause of the first event;

determining a network topological indicator from the first event;

determining a network implication of the first event based on the topological indicator;

determining for the first event a source s and a destination d, wherein s, dε

V;

creating and storing path data P={P₁ . . . P_n} comprising all paths from s to d and wherein

each path P_m={s, . . . ,d} is an ordered list of vertices from V;

creating and storing edge data e=(v_i,v_j)ε

S∉

R iff ∀

P_mε

P;

determining whether v is not followed immediately by v_j on P_m or

P_m={v₁, . . . , v<sub>i−

1</sub>, v_i, v_j, v_j+1, . . . , v_i}, and exist k≦

i, j≦

l forming a path {v_k, . . . , v_l} in G having no marked edges, by iterating through the path and removing all vertices between v_a and v_b if v_b is reachable from v_a through a path with no marked edges;

creating and storing a set R of events that cannot be eliminated comprising edges from S remaining on the path, after all removals are performed.

8. An apparatus comprising:

means for creating and storing a virtual network model that describes nodes and links of a data processing network at a plurality of time periods;

means for receiving from the network a first event that indicates a problem in the network;

means for receiving a set of second events comprising candidates for a root cause of the first event;

means for determining a network topological indicator from the first event;

means for determining a network implication of the first event based on the topological indicator;

means for retrieving from the virtual network model, based on the network implication and a time value of the first event, data that indicates a path between nodes associated with the first event at a time at which the first event occurred;

removing, from the set of second events, all events that are not on the path between devices associated with the first event.

9. The apparatus of claim 8 wherein the virtual network model comprises a directed acyclic graph.

10. The apparatus of claim 8 wherein the topological indicator specifies that a device is unreachable or a BGP neighbor is lost.

11. The apparatus of claim 8 further comprising means for translating the first event to a source point and a destination point in the virtual network model, wherein the destination point is not reachable in the network from the source point.

12. The apparatus of claim 9 wherein each of the second events represents a broken edge of the graph.

13. The apparatus of claim 9, wherein the virtual network model comprises a directed acyclic graph, further comprising translating the first event to a source point and a destination point in the virtual network model, wherein the destination point is not reachable in the network from the source point, and wherein the retrieving and removing includes processing all paths in the graph from the source point to the destination point.

14. Logic encoded in one or more tangible media for execution and when executed operable to:

create and store a virtual network model that describes nodes and links of a data processing network at a plurality of time periods;

receive from the network a first event that indicates a problem in the network;

receive a set of second events comprising candidates for a root cause of the first event;

determine a network topological indicator from the first event;

determine a network implication of the first event based on the topological indicator;

based on the network implication and a time value of the first event, retrieving data from the virtual network model that indicates a path between nodes associated with the first event at a time at which the first event occurred;

remove, from the set of second events, all events that are not on the path between devices associated with the first event.

15. A computer system comprising:

a computing device;

logic coupled to the computing device, wherein the logic when executed is operable to;

create and store a virtual network model that describes nodes and links of a data processing network at a plurality of time periods;

receive from the network a first event that indicates a problem in the network;

receive a set of second events comprising candidates for a root cause of the first event;

determine a network topological indicator from the first event;

determine a network implication of the first event based on the topological indicator;

based on the network implication and a time value of the first event, retrieving data from the virtual network model that indicates a path between nodes associated with the first event at a time at which the first event occurred;

remove, from the set of second events, all events that are not on the path between devices associated with the first event.

16. The system of claim 15 wherein the virtual network model comprises a directed acyclic graph.

17. The system of claim 15 wherein the topological indicator specifies that a device is unreachable or a BGP neighbor is lost.

18. The system of claim 15 further comprising logic which when executed is operable to translate the first event to a source point and a destination point in the virtual network model, wherein the destination point is not reachable in the network from the source point.

19. The system of claim 16 wherein each of the second events represents a broken edge of the graph.

20. The system of claim 16, wherein the virtual network model comprises a directed acyclic graph, further comprising logic which when executed is operable to translate the first event to a source point and a destination point in the virtual network model, wherein the destination point is not reachable in the network from the source point, and wherein the logic to retrieve and remove includes processing all paths in the graph from the source point to the destination point.