LINK INFERENCE IN LARGE NETWORKS BASED ON INCOMPLETE DATA
First Claim
1. A method comprising:
- receiving a plurality of address forwarding tables that define address sets associated with ports of nodes in a network,selecting a root node from the nodes of the network,creating a partition associated with each port of the root node that includes each of the other nodes of the network that are simply connected to the port,if any nodes remain that have not been included in at least one partition, selecting a node from among the remaining nodes as the root node and repeating the creating of partitions until each node of the network has been included in at least one partition,determining a topology of each partition, andmerging the topologies of the partitions to determine a topology of the network.
21 Assignments
0 Petitions
Accused Products
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.
25 Citations
42 Claims
-
1. A method comprising:
-
receiving a plurality of address forwarding tables that define address sets associated with ports of nodes in a network, selecting a root node from the nodes of the network, creating a partition associated with each port of the root node that includes each of the other nodes of the network that are simply connected to the port, if any nodes remain that have not been included in at least one partition, selecting a node from among the remaining nodes as the root node and repeating the creating of partitions until each node of the network has been included in at least one partition, determining a topology of each partition, and merging the topologies of the partitions to determine a topology of the network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A system comprising:
-
a memory that is configured to store a plurality of address forwarding tables that define address sets associated with ports of nodes in a network, a network partitioner that is configured to; select a root node from the nodes of the network, create a partition associated with each port of the root node that includes each of the other nodes of the network that are simply connected to the port, select a node from among the remaining nodes as the root node if any nodes remain that have not been included in at least one partition, and repeat the creating of partitions until each node of the network has been included in at least one partition, and determine a topology of each partition, and a link merger that is configured to merge the topologies of the partitions to determine a topology of the network. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. A computer program on a computer readable media that, when executed, is configured to cause a processor to:
-
receive a plurality of address forwarding tables that define address sets associated with ports of nodes in a network, select a root node from the nodes of the network, create a partition associated with each port of the root node that includes each of the other nodes of the network that are simply connected to the port, select a node from among the remaining nodes as the root node if any nodes remain that have not been included in at least one partition, and repeat the creating of partitions until each node of the network has been included in at least one partition, and determine a topology of each partition, and merge the topologies of the partitions to determine a topology of the network. - View Dependent Claims (38, 39, 40, 41, 42)
-
Specification