Link inference in large networks

Abstract

A network is partitioned into a set of independent partitions, and the topology of each partition is determined, then merged to form a topology of the entire network. Preferably, the partitioning is hierarchical, wherein the network is partitioned to form individual VLAN partitions, and each of the VLAN partitions is further partitioned based on the nodes that are simply connected to each port of one or more selected root switches within the VLAN partition. Simple connections to each port are efficiently determined based on an aggregate address forwarding table associated with each node. Ancillary information, such as spanning tree or CDP data, may be used to facilitate efficient partitioning and/or to validate inferences that are made with incomplete information.

We claim: 
     
         1 . A non-transitory computer-readable medium that includes a program that, when executed by a processor, causes the processor to:
 receive a plurality of address forwarding tables that define virtual networks associated with ports of nodes in a network;   process the plurality of address forwarding tables to identify a first address forwarding table that contains anomalous forwarding information that does not provide an explicit correspondence between at least one port and each virtual network that is associated with the at least one port,   determine an implicit correspondence between the at least one port and each virtual network that is associated with the at least one port,   replace the first address forwarding table with a second address forwarding table that includes the implicit correspondence between the at least one port and each virtual network that is associated with the at least one port,   partition the network into a plurality of partitions based on the plurality of address forwarding tables, including the second address forwarding table,   determine a topology associated with each of the plurality of partitions,   merge the topologies of the partitions to create a topology of the network, and   present a representation of at least a portion of the topology of the network.   
     
     
         2 . The medium of  claim 1 , wherein the anomalous forwarding information corresponds to information associated with encapsulation of traffic of a first virtual network into traffic of a second virtual network. 
     
     
         3 . The medium of  claim 2 , wherein the second address forwarding table includes the first virtual network. 
     
     
         4 . The medium of  claim 1 , wherein the anomalous forwarding information corresponds to information associated with a cryptographic feature associated with traffic associated with the port. 
     
     
         5 . The medium of  claim 4 , wherein the program causes the processor to replace an identifier of an internal port in the first address forwarding table with an identifier of an external port in the second forwarding table. 
     
     
         6 . The medium of  claim 1 , wherein the program causes the processor to determine the topology of at least one partition via a process that includes identifying a connection between each port of a root node and each node that is directly connected to the port of the root node. 
     
     
         7 . The medium of  claim 6 , wherein the program causes the processor to determine the topology of at least one partition via a process that includes identifying another node that is not included in the at least one partition. 
     
     
         8 . The medium of  claim 6 , wherein the program causes the processor to identify the connection via a process that includes identifying an access node and a trunk node with a native VLAN configuration. 
     
     
         9 . The medium of  claim 1 , wherein the program causes the processor to merge the topologies of the partitions by a process that includes identifying conflicting information among the determined topologies and resolve the conflicting information based on a hierarchy of preferences. 
     
     
         10 . The medium of  claim 9 , wherein the hierarchy of preferences is based on a determination of methods used to determine links between the ports. 
     
     
         11 . A method comprising:
 receiving, by a network analysis system, a plurality of address forwarding tables that define virtual networks associated with ports of nodes in a network;   storing, by the network analysis system, the plurality of address forwarding tables in a memory device;   processing, by the network analysis system, the plurality of address forwarding tables to identify a first address forwarding table that contains anomalous forwarding information that does not provide an explicit correspondence between at least one port and each virtual network that is associated with the at least one port,   determining, by the network analysis system, an implicit correspondence between the at least one port and each virtual network that is associated with the at least one port,   replacing, by the network analysis system, the first address forwarding table with a second address forwarding table that includes the implicit correspondence between the at least one port and each virtual network that is associated with the at least one port,   partitioning, by the network analysis system, the network into a plurality of partitions based on the plurality of address forwarding tables, including the second address forwarding table,   determining, by the network analysis system, a topology associated with each of the plurality of partitions,   merging, by the network analysis system, the topologies of the partitions to create a topology of the network, and   presenting, by the network analysis system, a representation of at least a portion of the topology of the network on a display device.   
     
     
         12 . The method of  claim 11 , wherein the anomalous forwarding information corresponds to information associated with encapsulation of traffic of a first virtual network into traffic of a second virtual network, and the second address forwarding table includes the first virtual network. 
     
     
         13 . The method of  claim 11 , wherein the anomalous forwarding information corresponds to information associated with a cryptographic feature associated with traffic associated with the port, and the second address forwarding table includes an identifier of an external port that replaces an internal port in the first address forwarding table 
     
     
         14 . The method of  claim 11 , wherein determining the topology of each partition includes identifying a connection between each port of a root node and each node that is directly connected to the port. 
     
     
         15 . The method of  claim 14 , wherein identifying the connection includes identifying an access node and a trunk node with a native VLAN configuration. 
     
     
         16 . The method of  claim 11 , wherein merging the topologies of the partitions includes identifying conflicting information among the determined topologies and resolving the conflicting information based on a hierarchy of preferences that is based on a determination of methods used to determine links between the ports. 
     
     
         17 . A system comprising:
 an AFT capture element that receives a plurality of address forwarding tables that define virtual networks associated with ports of nodes in a network;   an AFT processor element that:
 processes the plurality of address forwarding tables to identify a first address forwarding table that contains anomalous forwarding information that does not provide an explicit correspondence between at least one port and each virtual network that is associated with the at least one port, 
 determines an implicit correspondence between the at least one port and each virtual network that is associated with the at least one port, and 
 replaces the first address forwarding table with a second address forwarding table that includes the implicit correspondence between the at least one port and each virtual network that is associated with the at least one port; 
   a network partitioner that:
 partitions the network into a plurality of partitions based on the plurality of address forwarding tables, including the second address forwarding table, and 
 determines a topology associated with each of the plurality of partitions; 
   a link merger that merges the topologies of the partitions to create a topology of the network;   a report generator that creates a representation of at least a portion of the topology of the network; and   a display device that displays the representation.   
     
     
         18 . The system of  claim 17 , wherein the anomalous forwarding information corresponds to information associated with encapsulation of traffic of a first virtual network into traffic of a second virtual network, and the second address forwarding table includes the first virtual network. 
     
     
         19 . The system of  claim 17 , wherein the anomalous forwarding information corresponds to information associated with a cryptographic feature associated with traffic associated with the port, and the second address forwarding table includes an identifier of an external port that replaces an internal port in the first address forwarding table 
     
     
         20 . The system of  claim 17 , wherein the network partitioner determines the topology of each partition by at least identifying a connection between each port of a root node and each node that is directly connected to the port. 
     
     
         21 . The system of  claim 20 , wherein identifying the connection includes identifying an access node and a trunk node with a native VLAN configuration. 
     
     
         22 . The system of  claim 17 , wherein merging the topologies of the partitions includes identifying conflicting information among the determined topologies and resolving the conflicting information based on a hierarchy of preferences that is based on a determination of methods used to determine links between the ports.