Network clustering
A network clustering facility is described. The network clustering facility receives a message having a location identification that identifies a destination for the message and comprises at least two components, selects a network node identified by the components of the location identification, determines whether a link exists to the selected network node, and identifies a best link to the selected network node. The network clustering facility comprises a clustering subsystem, an advertising subsystem, and a routing layer.
1. A system for creating a clustering data communications network, the clustering data communications network having a plurality of clusters each with network nodes, the plurality of clusters each having one representative network node and at least one other network node, comprising:
a clustering subsystem that, for a node, is adapted to identify a cluster with which the network node is to be associated, that is adapted to assign a location identification that identifies at least a representative network node for the cluster of the network node, wherein the representative network node represents the cluster with which the network node is to be associated, wherein the representative network node of the cluster is interconnected using links with all other network nodes of the cluster, and wherein the representative network node is adapted to link to the other network nodes of the cluster;
an advertising subsystem that is adapted to send advertising messages, each advertising message sent by an advertising network node to indicate that the network node exists in the clustering data communications network, and wherein the advertising message identifies at least the representative network node of the cluster of the advertising network node; and
a routing layer that is adapted to determine whether each advertising message is to be forwarded to another network node by evaluating a rank of the network node that sent the advertising message.
2. The system of claim 1 wherein the cluster comprises at least two network nodes.
3. The system of claim 1 wherein the representative node of each of a plurality of clusters has a link to every other network node in its cluster, and wherein the other network nodes do not link to other nodes of the clustering data communications network that are outside of its cluster.
4. The system of claim 1 wherein the routing layer contains at least the clustering subsystem and the advertising subsystem.
5. The system of claim 1 wherein the routing layer is associated with at least one node of the clustering data communications network.
6. The system of claim 1 wherein the advertising message indicates the rank of the network node that sent the advertising message.
7. The system of claim 1 wherein the routing layer determines the rank of the network node that sent the advertising message.
8. The system of claim 1 wherein the clusters are related hierarchically to determine the rank wherein the rank is identified by a network node's level in the hierarchy.
9. The system of claim 8 wherein network nodes that are leaf vertices in a graph representing the hierarchy have a lowest level.
10. The system of claim 1 wherein the routing layer is associated with at least one node of the clustering data communications network, and has a routing table that identifies all links from the network node to other network nodes with which the network node is connected.
11. The system of claim 10 wherein the routing table identifies a cost associated with each link.
12. A non-transitory computer-readable medium having computer-executable instructions operable to enable a first network node to perform a method of managing a clustering data communications network, the method comprising:
receiving an advertising message;
identifying from the advertising message a rank of a network node that sent the advertising message wherein the advertising message includes location information about the sending network node, wherein the location information identifies a cluster where the sending network node resides and a representative network node of the cluster, and wherein each network node of the cluster is directly linked to the representative network node associated with its cluster and is not linked to another network node outside of its cluster;
determining whether to forward the received advertising message based on the identified rank; and
forwarding the advertising message if the rank exceeds a specified amount.
13. The computer-readable medium of claim 12 wherein the specified amount relates to a rank of the first network node.
14. The computer-readable medium of claim 12 further comprising providing a location identification to a network node from which the advertising message was received.