Inferring connectivity in the presence of conflicting network data
The connectivity information provided by a variety of inference engines is integrated to provide a set of inferred links within a network. A consolidation is performed among inference engines that operate at a base level of connectivity detail to create a model of the network at this base level. The connectivity information provided by inference engines at each subsequent higher level of connectivity abstraction is then overlaid on the base level connectivity. By separately consolidating the connectivity information at each level of abstraction, the rules for dealing with conflicts can be simplified and/or better focused to resolve the conflict. By assuming that the more detailed lower level information is likely to be more accurate, rules can be developed to modify the connectivity models produced by the higher level techniques to conform to the lower level connectivity details while still maintaining the integrity of the higher level connectivity models.
1. A computer-implemented method for identifying a topology between nodes a network, said method comprising:
receiving, from a plurality of data sources, sets of data indicating connectivity information of nodes in the network, wherein each set of data relates to at least one connectivity level within a hierarchy of connectivity levels;
consolidating, at a first level within the hierarchy of connectivity levels, a first set of data into a first connectivity graph indicating connections between nodes in the network at the first level;
consolidating, at a second level higher than the first level within the hierarchy of connectivity levels, a second set of data into a second connectivity graph indicating connections between nodes in the network at the second level; and
overlaying the first and second connectivity graphs to determine at least a portion of a topology of the network.
2. The method of claim 1 , wherein the sets of data indicating connectivity information includes addressing data from configuration files of nodes in the network.
3. The method of claim 1 , wherein the sets of data indicating connectivity information includes neighbor discovery data from nodes in the network.
4. The method of claim 1 , wherein the sets of data indicating connectivity information includes forwarding table data from nodes in the network.
5. The method of claim 1 , wherein the sets of data indicating connectivity information comprises link layer discovery protocol data from nodes in the network.
6. The method of claim 1 , wherein the sets of data indicating connectivity information includes border gateway protocol data from nodes in the network.
7. The method of claim 1 , wherein consolidating sets of data into the first connectivity graph comprises consolidating sets of data at a physical connectivity level.
8. The method of claim 7 , wherein consolidating sets of data into the first connectivity graph comprises resolving conflicts in the physical connectivity level data.
9. The method of claim 7 , wherein consolidating sets of data into the first connectivity graph comprises resolving omissions in the physical connectivity level data.
10. The method of claim 1 , wherein determining at least a portion of the topology of the network comprises: identifying pairs of nodes connected at the first level in the first connectivity graph; identifying pairs of nodes connected at the second level in the second connectivity graph; and determining that the topology of the network comprises a link between a pair of nodes when the pair of nodes are connected at both first and second levels.
11. The method of claim 1 , wherein determining at least a portion of the topology of the network comprises: identifying a pair of nodes connected at the second level in the second connectivity graph; and determining that the topology of the network comprises a link between one of the pair of nodes and at least one additional node in the first connectivity graph based on the pair of nodes in the second connectivity graph.
12. A system for identifying connections among nodes of a network, the system comprising:
an interface configured to receive sets of data from a plurality of sources in the network, wherein each set of data relates to at least one connectivity level within a hierarchy of connectivity levels;
a first inference engine configured to determine, at a first level within the hierarchy of connectivity levels, a first connectivity graph based on a first set of data indicating connections between nodes in the network at the first level;
a second inference engine configured to determine, at a second level higher than the first level within the hierarchy of connectivity levels, a second connectivity graph based on a second set of data indicating connections between nodes in the network at the second level; and
a physical path creator configured to identify at least one physical path between a pair of nodes of the network based on consolidating the first and second connectivity graphs.
13. The system of claim 12 , wherein the first and second inference engines are configured to determine at least one of the first and second connectivity graphs based on at least one inference rule.
14. The system of claim 12 , wherein the physical path creator is configured to resolve conflicts between the first and second connectivity graphs based on a golden rule.
15. The system of claim 12 , wherein the interface is configured to receive at least one of forwarding table information, neighbor discovery information, and link layer discovery information.
16. The system of claim 12 , wherein the first and second connectivity graphs include metadata associated with one or more inferred links that facilitates the consolidating of the first and second connectivity graphs.
17. A non-transitory computer-readable medium that includes a program that, when executed by a processor, causes the processor to:
receive sets of data from a plurality of sources in a network, wherein each set of data relates to a connectivity level within a hierarchy of connectivity levels;
identify the set of data relating to a first level within the hierarchy of connectivity levels,
identify first connections between nodes in the network at the first level based on a first set of inference rules;
provide a first connectivity graph representing the first connections;
identify the set of data relating to a second level within the hierarchy of connectivity levels,
identify second connections between nodes in the network at the second level based on a second set of inference rules;
provide a second connectivity graph representing the second connections;
overlay the first and second connectivity graphs to create a network connectivity graph; and
provide a display based at least in part on the network connectivity graph.
18. The non-transitory computer-readable medium of claim 17 , including:
identify the set of data relating to a third level within the hierarchy of connectivity levels,
identify third connections between nodes in the network at the third level based on a third set of inference rules;
provide a third connectivity graph representing the third connections; and
update the network connectivity graph based on an overlay of the third connectivity graph.
19. The non-transitory computer-readable medium of claim 17 , wherein the sets of data include at least two of forwarding table information, neighbor discovery information, and link layer discovery information.
20. The non-transitory computer-readable medium of claim 17 , wherein the program causes the processor to supersede at least one of the first and second sets of inference rules based on a golden rule specified by a user.