Assigning telecommunications nodes to community of interest clusters

• US 8,495,201 B2
• Filed: 08/21/2012
• Issued: 07/23/2013
• Est. Priority Date: 11/13/2007
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Klincewicz, John Gregory
• Primary Examiner(s): Chan, Wing F
• Assistant Examiner(s): KATSIKIS, KOSTAS J
• Application Number:
  US13/590,359
• Publication Number:
  US 20120317264A1
• Time in Patent Office: 336 Days
• Field of Search: 709/223, 709/224, 709/226, 370/400
• US Class Current: 709/223
• CPC Class Codes: H04L 41/048 mobile agents
• CPC Class Codes: H04L 41/0813 characterised by the conditions triggering a change of settings
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements

Abstract

The present invention provides techniques for assigning network nodes to community of interest clusters. A seed point representing a cluster is selected. One or more nodes are added to the cluster based on each node'"'"'s geographic proximity to the selected seed point. Nodes that are adjacent to the cluster are identified and a clustering metric is computed that is representative of the affinity that each identified adjacent node has for the cluster. One or more of the identified nodes are added to the cluster when the clustering metric for the one or more identified nodes exceeds a predetermined value.

Claims

1. A method for assigning network nodes to community of interest clusters, the method comprising:

selecting, with a processor, two seed points in a network, each seed point representing a cluster, wherein the two seed points are selected so that a distance between the two seed points is as far apart as possible, via a network path selected from a plurality of network paths;

adding, with the processor, a node to a particular cluster based on a distance between the node and one of the two seed points representing the particular cluster;

computing, with the processor, a clustering metric representative of an affinity that each of a plurality of nodes adjacent to the particular cluster has for the particular cluster, the clustering metric based on a distance between the plurality of nodes and the one of the two seed points; and

adding, with the processor, one of the plurality of nodes to the particular cluster when the clustering metric for the one of the plurality of nodes exceeds a predetermined value.

2. The method of claim 1, wherein the clustering metric is further based on one of demand and network connectivity and wherein the clustering metric further comprises one of a termination demand component, a via demand component, and a network connectivity component.

3. The method of claim 1, further comprising:

recomputing, with the processor, the clustering metric until all of the plurality of nodes are added to a respective cluster.

4. The method of claim 1, further comprising:

identifying, with the processor, any hanging nodes in the particular cluster, and moving any hanging nodes to a neighboring cluster.

5. The method of claim 1, further comprising:

replacing, with the processor, a seed point of the two seed points with a third seed point if the third seed point reduces distances between each other node in the plurality of nodes and the seed point.

6. The method of claim 1, further comprising:

identifying, with the processor, a particular node in the particular cluster as a pinch-point if a sub-network formed by nodes in the particular cluster would be disconnected if the particular node were removed from the sub-network;

identifying, with the processor, boundary nodes in the particular cluster if a particular node is determined to be a pinch-point;

selecting, with the processor, a boundary cluster based on the boundary nodes, to generate a selected boundary cluster; and

moving, with the processor, the particular node identified as a pinch-point to the selected boundary cluster.

7. The method of claim 1, further comprising:

identifying a link having a first end node in the particular cluster and a second end node in a second cluster;

computing an amount of traffic that originates at the first end node and terminates on the second cluster; and

overlapping the particular cluster with the second cluster by assigning one of the first end node and the second end node to the second cluster when the amount of traffic exceeds a predetermined threshold.

8. A non-transitory computer readable medium storing computer program instructions for assigning network nodes to community of interest clusters, which, when executed on a processor, cause the processor to perform operations comprising:

selecting two seed points in a network, each seed point representing a cluster, wherein the two seed points are selected so that a distance between the two seed points is as far apart as possible, via a network path selected from a plurality of network paths;

adding a node to a particular cluster based on a distance between the node and one of the two seed points representing the particular cluster;

computing a clustering metric representative of an affinity that each of a plurality of nodes adjacent to the particular cluster has for the particular cluster, the clustering metric based on a distance between the plurality of nodes and the one of the two seed points; and

adding one of the plurality of nodes to the particular cluster when the clustering metric for the one of the plurality of nodes exceeds a predetermined value.

9. The non-transitory computer readable medium of claim 8, wherein the clustering metric is further based on one of demand and network connectivity and wherein the clustering metric further comprises one of a termination demand component, a via demand component, and a network connectivity component.

10. The computer readable medium of claim 8, further comprising operations to perform:

recomputing the clustering metric until all of the plurality of nodes are added to a respective cluster.

11. The non-transitory computer readable medium of claim 8, further comprising operations to perform:

identifying any hanging nodes in the particular cluster, and moving any hanging nodes to a neighboring cluster.

12. The non-transitory computer readable medium of claim 8, further comprising operations to perform:

replacing a seed point of the two seed points with a third seed point if the third seed point reduces distances between each other node in the plurality of nodes and the seed point.

13. The non-transitory computer readable medium of claim 8, further comprising operations to perform:

identifying a link having a first end node in the particular cluster and a second end node in a second cluster;

computing an amount of traffic that originates at the first end node and terminates on the second cluster; and

overlapping the particular cluster with the second cluster by assigning one of the first end node and the second end node to the second cluster when the amount of traffic exceeds a predetermined threshold.

14. An apparatus comprising:

a processor; and

a memory to store computer program instructions, the computer program instructions, which, when executed on the processor cause the processor to perform operations comprising;

selecting two seed points in a network, each seed point representing a cluster, wherein the two seed points are selected so that a distance between the two seed points is as far apart as possible, via a network path selected from a plurality of network paths;

adding a node to a particular cluster based on a distance between the node and one of the two seed points representing the particular cluster;

computing a clustering metric representative of an affinity that each of a plurality of nodes adjacent to the particular cluster has for the particular cluster, the clustering metric based on a distance between the plurality of nodes and the one of the two seed points; and

adding one of the plurality of nodes to the particular cluster when the clustering metric for the one of the plurality of nodes exceeds a predetermined value.

15. The apparatus of claim 14, wherein the clustering metric is further based on one of demand and network connectivity and wherein the clustering metric further comprises one of a termination demand component, a via demand component, and a network connectivity component.

16. The apparatus of claim 14, wherein the processor performs further operations comprising:

recomputing the clustering metric until all of the plurality of nodes are added to a respective cluster.

17. The apparatus of claim 14, wherein the processor performs further operations comprising:

identifying any hanging nodes in the particular cluster, and moving any hanging nodes to a neighboring cluster.