US 6,618,755 B1 · Automatically identifying subnetworks in a network

Abstract

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.

Claims16

Dependent claims

A method in a data processing system for identifying a subnet address range for a subnet being used in a network, the network utilizing addresses each comprising an ordered series of a fixed number of bits, comprising:

(a) determining the addresses of a plurality of hosts within the network;
(b) identifying an address prefix for which at least one determined host address has the form “<identified address prefix> 0 <any address suffix>”, and for which at least one determined address has the form “<identified address prefix> 1 <any address suffix>”;
(c) determining whether the plurality of determined host addresses include either the address “<identified address prefix> 0 <address suffix comprised entirely of 1s>” or the address “<identified address prefix> 1 <address suffix comprised entirely of 0s>”;
(d) if the plurality of determined host addresses include either the address “<identified address prefix> 0 <address suffix comprised entirely of 1s>” or the address “<identified address prefix> 1 <address suffix comprised entirely of 0s>”, identifying the range of addresses that all begin with the identified address prefix as a subnet address range for a subnet being used in a network;
(e) if the plurality of determined host addresses include neither the address “<identified address prefix> 0 <address suffix comprised entirely of 1s>” nor the address “<identified address prefix> 1 <address suffix comprised entirely of 0s>”:
(1) sending one or more test packets requesting a reply each to a determined host address having the form “<identified address prefix> 0 <any address suffix>” from an address having the form “<identified address prefix> 1 <any address suffix>”;
(2) sending one or more test packets requesting a reply each to a determined host address having the form “<identified address prefix> 1 <any address suffix>” from an address having the form “<identified address prefix> 0 <any address suffix>”;
(3) determining the number of test pack sent where a reply to the test packet was sent directly from the test packet's destination address to the test packet's source address;
and
(4) if the number of test packets sent where a reply to the test packet was sent directly from the test packet's destination address to the test packet's source address exceeds a threshold number, identifying the range of addresses that all begin with the identified address prefix as identifying a subnet address range for a subnet being used in a network.

7 more elements

A method in a data processing system for identifying subnet address ranges for a 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 two child nodes, and leaf nodes having no children, 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, both child nodes of each candidate node having 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 a network by, 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;
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 a identified subnet node.

7 more elements

A method in a data processing system for identifying subnet address ranges for a 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 two child nodes, and leaf nodes having no children, 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, both child nodes of each candidate node having 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 a network by, 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;
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 a identified subnet node.

7 more elements

A computer-readable medium whose contents cause a data processing system to identify subnet address ranges for a 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 two child nodes, and leaf nodes having no children, 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, both child nodes of each candidate node having 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 a network by, 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;
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 a identified subnet node.

7 more elements

A computer-readable medium whose contents cause a data processing system to identify subnet address ranges for a 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 two child nodes, and leaf nodes having no children, 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, both child nodes of each candidate node having 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 a network by, 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;
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 a identified subnet node.

7 more elements

Dependencies are inferred from the claim text.

Automatically identifying subnetworks in a network

Life of this patent

Automatically identifying subnetworks in a network

Life of this patent

Abstract

Claims16