Automatically identifying subnetworks in a network
View Patent ↗A software facility for automatically identifying subnetworks in a network is described. The facility receives a plurality of addresses of hosts in the network, and accesses a binary tree. The nodes of the binary tree each represent a range of addresses within the network. A facility traverses the binary tree to identify candidate nodes where both child nodes have one or more descendent leaf nodes representing host addresses. The facility tests the address range represented by each candidate node visited in the traversal to determine whether the address range is a subnet address range for a subnet being used on the network. If testing indicates that a visited candidate node represents such an address range, the facility identifies the visited candidate node as a subnet node. The facility skips, in the traversal, any candidate notes that are descendents of an identified subnet node.
1. A method in a data processing system for identifying subnet address ranges for subnets being used in a network, comprising:
determining a plurality of addresses of hosts in the network;
accessing a binary tree, the binary tree having a root node having no parents, parent nodes including the root node each having a pair of child nodes, and leaf nodes having no child nodes, such that the root node represents the entire range of addresses available in the network, such that each child node in a pair of child nodes represents a distinct half of the range represented by the parent node of the pair of child nodes, and such that each leaf node represents a single network address that is within the address ranges represented by all of the ancestors of the leaf node, each determined host address being represented by a leaf node;
traversing the binary tree in preorder to identify candidate nodes such that both child nodes of each candidate node have one or more descendant leaf nodes representing a determined host address;
testing the address range represented by each visited candidate node to determine whether the address range is a subnet address range for a subnet being used in the network;
if testing indicates that a visited candidate node represents an address range that is a subnet address range for a subnet being used in a network, identifying the visited candidate node as a subnet node; and
skipping, in the traversal, any candidate nodes that are descendants of an identified subnet node.
2. The method of claim 1 wherein testing comprises, for the two subranges represented by the child nodes of the candidate node:
sending one or more packets each from a source address to a destination address, each packet requesting a reply, the source and destination addresses being in different subranges for each packet;
for each packet, determining whether a reply to the packet is sent directly from the destination address back to the source address; and
if, for a number of packets exceeding a threshold number, a reply to the packet is sent directly from the destination address back to the source address, determining that the candidate node represents an address range that is a subnet address range for a subnet being used in a network.
3. The method of claim 1 wherein testing comprises, for the two subranges represented by the child nodes of the candidate node:
selecting the address within each subrange that is closest to the addresses of the other subrange;
determining whether the network contains a host responding to either of the selected addresses; and
if the network contains a host responding to either of the selected addresses, determining that the candidate node represents an address range that is a subnet address range for a subnet being used in a network.
4. The method of claim 1 , further comprising, before traversing the binary tree, trimming the binary tree by deleting nodes not on the path between the root node and any leaf node representing a determined host address.
5. The method of claim 1 , further comprising, before traversing the binary tree, trimming the binary tree by deleting all nodes not on a path between the root node and any leaf node representing a determined host address.
6. A computer-readable medium whose contents cause a data processing system to identify subnet address ranges for subnets being used in a network by:
receiving a plurality of addresses of hosts in the network;
accessing a binary tree, the binary tree having a root node having no parents, parent nodes including the root node each having a pair of child nodes, and leaf nodes having no child nodes, such that the root node represents the entire range of addresses available in the network, such that each child node in a pair of child nodes represents a distinct half of the range represented by the parent node of the pair of child nodes, and such that each leaf node represents a single network address that is within the address ranges represented by all of the ancestors of the leaf node, each received host address being represented by a leaf node;
traversing the binary tree in preorder to identify candidate nodes such that both child nodes of each candidate node have one or more descendant leaf nodes representing a received host address;
testing the address range represented by each candidate node in the traversal visited to determine whether the address range is a subnet address range for a subnet being used in the network; if testing indicates that a visited candidate node represents an address range that is a subnet address range for a subnet being used in a network, identifying the visited candidate node as a subnet node; and
skipping, in the traversal, any candidate nodes that are descendants of an identified subnet node.
7. The computer-readable medium of claim 6 wherein testing comprises, for the two subranges represented by the child nodes of the candidate node:
sending one or more packets each from a source address to a destination address, each packet requesting a reply, the source and destination addresses being in different subranges for each packet;
for each packet, determining whether a reply to the packet is sent directly from the destination address back to the source address; and
if, for a number of packets exceeding a threshold number, a reply to the packet is sent directly from the destination address back to the source address, determining that the candidate node represents an address range that is a subnet address range for a subnet being used in a network.
8. The computer-readable medium of claim 6 wherein testing comprises, for the two subranges represented by the child nodes of the candidate node:
selecting the address within each subrange that is closest to the addresses of the other subrange;
determining whether the network contains a host responding to either of the selected addresses; and
if the network contains a host responding to either of the selected addresses, determining that the candidate node represents an address range that is a subnet address range for a subnet being used in a network.
9. The computer-readable medium of claim 6 wherein the contents of the computer-readable medium further cause the data processing system to trim the binary tree by deleting nodes not on the path between the root node and any leaf nodes representing a received host address before traversing the binary tree.
10. The computer-readable medium of claim 6 wherein the contents of the computer-readable medium further caused the data processing system to trim the binary tree by deleting all nodes not on the path between the root node and any leaf nodes representing a received host address before traversing the binary tree.
11. A data processing system for identifying subnet address ranges for subnets being used in a network, comprising:
a receiver that receives a plurality of addresses of hosts in the network;
a tree memory storing a binary tree, the binary tree having a root node having no parents, parent nodes including the root node each having a pair of child nodes, and leaf nodes having no child nodes, such that the root node represents the entire range of addresses available in the network, such that each child node in a pair of child nodes represents a distinct half of the range represented by the parent node of the pair of child nodes, and such that each leaf node represents a single network address that is within the address ranges represented by all of the ancestors of the leaf node, each determined host address being represented by a leaf node; and
a tree traversal subsystem that traverses the binary tree stored in the tree memory in preorder, skipping any candidate nodes that are descendents of an identified subnet node, to identify candidate nodes such that both child nodes of each candidate node have one or more descendent leaf nodes representing a determined host address, that tests the address range represented by each visited candidate node to determine whether the address range is a subnet address range for a subnet being used in the network, and that identifies a visited candidate node as a subnet node if testing indicates that the visited candidate node represents an address range that is a subnet address range for a subnet being used in the network.
12. The data processing system of claim 11 , further comprising a tree trimming subsystem that, before the tree traversal subsystem traverses the binary tree, trims the binary tree by deleting nodes not on the path between the root node and any leaf node representing a determined host address.
13. The data processing system of claim 11 , further comprising a tree trimming subsystem that, before the tree traversal subsystem traverses the binary tree, trims the binary tree by deleting all nodes not on the path between the root node and any leaf node representing a determined host address.