Method and apparatus for aggregating terminals into clusters to assist in the construction of a distributed data communication network

• US 5,652,841 A
• Filed: 06/07/1995
• Issued: 07/29/1997
• Est. Priority Date: 02/06/1990
• Status: Expired due to Term

• Current Assignee: Michael Ball, Paul Nemirovsky, Roy Dahl
• Original Assignee: Michael Ball, Paul Nemirovsky, Roy Dahl
• Inventors: Ball, Michael, Dahl, Roy, Nemirovsky, Paul
• Primary Examiner(s): Weinhardt, Robert A.
• Assistant Examiner(s): Kalidindi, Krishna V.
• Application Number:
  US08/487,342
• Time in Patent Office: 783 Days
• Field of Search: 379/219, 379/220, 379/229, 379/333, 379/334, 379/111, 379/92, 395/200.02, 395/200.1, 364/401 R, 364/402
• US Class Current: 705/1.1
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/46 Cluster building

Abstract

A method and apparatus for aggregating terminals into clusters that assists in the construction of a distributed data communication network. Terminal locations to be clustered are used as input along with a weight for each one representing the traffic carried by that location. The terminals are placed into boxes based on their geographic coordinates and only boxes with substantial traffic are retained. Any terminals included in a box not retained are assigned to the closest retained box. The retained boxes are merged into clusters so long as the maximum cluster traffic and maximum cluster radius are not exceeded. The center of mass of the resulting clusters are then determined. The representative locations of the resulting clusters are determined as the location of the terminal in the cluster closest to the center of mass.

Claims

1. In a communication network having a number of terminals, backbone nodes for routing communication traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said network extending throughout a geographic region, a computer implemented method for aggregating the terminals into clusters comprising steps of:

a) dividing said geographic region over which the network extends into subregions;

b) defining a number of subregions to be used, the square of the number of subregions being less than or equal to the number of terminals;

c) assigning each terminal to a subregion based on its geographic coordinates;

d) computing the total communication traffic within a backbone in each subregion;

e) computing a center of each subregion based on a weighted average of each terminal assigned to the subregion, the weighted average of each terminal corresponding to an amount of traffic associated with that terminal;

f) retaining subregions with computed traffic greater than a predetermined significant traffic value as candidate clusters;

g) assigning those terminals not associated with a retained subregion to the nearest adjacent retained subregion, or if no such subregion is available placing the terminal in its own subregion;

h) merging the clusters based on user-defined parameters by clustering the smallest subregion with its nearest neighbors;

i) determining a center of the newly merged clusters based on a weighted average of each terminal of the cluster, the weighted average of each terminal corresponding to an amount of traffic associated with that terminal;

j) choosing the location of the terminal closest to the center of each newly merged cluster as the representative location of that cluster; and

k) directing communication traffic from a first of said terminals through said terminal closest to the center of the cluster in which said first terminal is located to a second of said terminals through said terminal closest to the center of the cluster in which said second terminal is located.

2. The computer implemented method for aggregating the terminals into clusters of claim 1 further comprising repeating the steps (a) through (h) and selecting a most economically efficient network for operation.

3. The computer implemented method of claim 1, wherein the step of directing communication traffic includes directing communication traffic from the first terminal to the second terminal via at least one of said backbone nodes and at least one of said concentrators.

4. An apparatus for efficiently connecting a number of terminals through backbone nodes, a backbone, and concentrators including a computer based interactive device for aggregating the terminals into clusters of a distributed communications network having a plurality of terminals, backbone nodes for routing traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said computer based interactive device comprising:

a) a user input device of said computer receiving inputs including;

a first set of data corresponding to terminal locations to be clustered, and

a second set of data corresponding to weights corresponding to the traffic carried by each terminal location;

and said user input device of said computer receiving specified parameters including;

a total number of terminal clusters to be formed,

a minimum weight of a smallest of said terminal clusters to be formed,

a maximum weight of a largest of said terminal clusters to be formed, and

a maximum radius of said terminal clusters to be formed;

said user input device selecting a system output mode;

b) a processor of said computer creating a number of subdivisions based on said total number of terminal clusters to be formed, wherein a square of the number of subdivisions is less than or equal to the number of terminals;

said processor assigning each terminal to one of said group of subdivisions based on its location;

said processor determining a total traffic for each of said group of subdivisions based on the weights of the terminals assigned to it by said processor;

said processor determining a center of each of said group of subdivisions based on the weights and the locations of the terminals assigned to it by said processor;

said processor forming a set of candidate subdivisions based on the total traffic for each of said group of subdivisions;

said processor defining a location for each of said group of subdivisions;

said processor assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions;

said processor merging subdivisions in said set of candidate subdivisions into clusters;

said processor updating centers of said clusters of merged subdivisions based on the weights and the locations of terminals of said clusters; and

said processor determining the representative locations of said clusters of said merged subdivisions; and

said processor directing communication traffic from a first of said terminals through said representative location of the cluster in which said first terminal is located to a second of said terminals through said representative location of the cluster in which said second terminal is located.

5. The apparatus including the computer based interactive device of claim 4 wherein

said processor creates a group of subdivisions by executing a first group of processor implemented instructions;

said processor assigns each terminal to one of said group of subdivisions by executing a second group of processor implemented instructions;

said processor determines a total traffic for each of said group of subdivisions by executing a third group of processor implemented instructions;

said processor determines a center of each of said group of subdivisions by executing a fourth group of processor implemented instructions;

said processor forms a set of candidate subdivisions by executing a fifth group of processor implemented instructions;

said processor defines a location for each or said group of subdivisions by executing a sixth group of processor implemented instructions;

said processor assigns terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions by executing a seventh group of processor implemented instructions;

said processor merges subdivisions in said set of candidate subdivisions into clusters by executing an eighth group of processor implemented instructions;

said processor updates centers of said clusters of merged subdivisions by executing a ninth group of processor implemented instructions;

said processor determines the representative locations of said clusters of said merged subdivisions by executing a tenth group of processor implemented instructions; and

said processor directs communication traffic by executing an eleventh group of processor implemented instructions.

6. The apparatus including the computer based interactive device of claim 4 wherein said system output mode is selected from a group of output modes consisting of virtual terminals, candidate backbone sites, and candidate concentrator sites.

7. The apparatus including the computer based interactive device of claim 4 wherein said parameters specified by said user input device further includes a minimum fraction of retained subdivisions and a minimum fraction of retained weight, and

wherein said processor forming a set of candidate subdivisions,

calculates a threshold traffic value based on the average traffic of terminals in a subdivision,

compares the total traffic for each subdivision determined by said processor with the calculated threshold traffic value, and

adds a subdivision to said set of candidate subdivisions if its total traffic is at least equal to said calculated threshold traffic value.

8. The apparatus including the computer based interactive device of claim 7 wherein if the number of subdivisions in said set of candidate subdivisions divided by the total number of subdivisions is less than the minimum fraction of retained subdivisions, some subdivisions having a total traffic less than said calculated threshold traffic value are added to said set of candidate subdivisions.

9. The apparatus including the computer based interactive device of claim 7 wherein if the total weight of the subdivisions in said set of candidate subdivisions divided by the total weight of all subdivisions is less that the minimum fraction of retained weight, some subdivisions having a total traffic less than said calculated threshold traffic value are added to said set of candidate subdivisions.

10. The apparatus including the computer based interactive device of claim 4 wherein said maximum radius is the maximum allowable distance from a terminal to the center of the subdivision to which it is assigned.

11. The apparatus including the computer based interactive device of claim 4 wherein said processor determining a location for each of said group of subdivisions makes its determination based on the center of the subdivision determined by the processor.

12. The apparatus including the computer based interactive device of claim 4 wherein said processor assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions assigns such terminals to the nearest adjacent subdivision included in said set of candidate subdivisions.

13. The apparatus including the computer based interactive device of claim 12 wherein if there is no adjacent subdivision included in said set of candidate subdivisions, such a terminal remains in its own subdivision.

14. The apparatus including the computer based interactive device of claim 4 wherein said processor merging subdivisions in said set of candidate subdivisions into clusters does so based on the centers of said subdivisions in said set of candidate subdivisions.

15. The apparatus including the computer based interactive device of claim 14 wherein said processor merges nearest-neighbor subdivisions.

16. The apparatus including the computer based interactive device of claim 15 wherein the merging of nearest-neighbor clusters continues as long as the weight of the proposed merged cluster does not exceed the maximum weight of the largest of said terminal dusters and the radius of the proposed merged cluster does not exceed the maximum radius of said terminal clusters.

17. The apparatus including the computer based interactive device of claim 4 wherein said processor determining the representative locations of said clusters of said merged subdivisions does so by assigning the location of a terminal closest to the updated center of said clusters.

18. The apparatus including the computer based interactive device of claim 4 wherein each cluster can be constrained to a single local access and transport area.

19. The apparatus including the computer based interactive device of claim 4 wherein the location of the cluster centers can be manually selected.

20. The apparatus including the computer based interactive device of claim 4 wherein said user input device includes a data storage device in which said received set of terminal locations, said received set of weights and said received specified parameters are stored.

21. The apparatus including the computer based interactive device of claim 4, wherein the processor directs communication traffic from the first terminal to the second terminal via at least one of said backbone nodes and at least one of said concentrators.

22. The apparatus including the computer based interactive device of claim 4, wherein said backbone nodes comprise data switches.

23. The apparatus including the computer based interactive device of claim 4, wherein said concentrators comprise multiplexers.

24. An apparatus for effectively connecting a number of terminals through backbone nodes, a backbone, and concentrators, including a computer based interactive device for aggregating the terminals into clusters of a distributed communications network having a plurality of terminals, backbone nodes for routing traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said computer based interactive device comprising:

a) a user input device of said computer receiving inputs including;

a first set of data corresponding to terminal locations to be clustered, and

a second set of data corresponding to weights corresponding to the traffic carried by each terminal location;

and said user input device of said computer receiving specified parameters including;

a total number of terminal clusters to be formed,

a minimum weight of a smallest of said terminal clusters to be formed,

a maximum weight of a largest of said terminal clusters to be formed, and

a maximum radius of said terminal clusters to be formed;

said user input device selecting a system output mode;

b) a processor of said computer creating a number of subdivisions, wherein the square of the number of subdivisions is less than or equal to the number of terminals;

said processor assigning each terminal to one of said number of subdivisions;

said processor determining a total traffic for each of said number of subdivisions;

said processor determining a center of each of said number of subdivisions;

said processor forming a set of candidate subdivisions including some of said number of subdivisions;

said processor defining a location for each of said number of subdivisions;

said processor assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions;

said processor merging subdivisions in said set of candidate subdivisions into clusters;

said processor updating centers of said clusters of merged subdivisions;

said processor determining the representative locations of said clusters of said merged subdivisions; and

said processor directing communication traffic from a first of said terminals through said representative location of the cluster in which said first terminal is located to a second of said terminals through said representative location of the cluster in which said second terminal is located.

25. The apparatus including the computer based interactive device of claim 24, wherein said backbone nodes comprise data switches.

26. The apparatus including the computer based interactive device of claim 24, wherein said concentrators comprise multiplexers.

27. The apparatus including the computer based interactive device of claim 24, wherein the processor directs communication traffic from the first terminal to the second terminal via at least one of said backbone nodes and at least one of said concentrators.

28. A method for efficiently connecting a number of terminals through backbone nodes, a backbone, and concentrators including a computer based interactive method for aggregating the terminals into clusters of a distributed communications network having a plurality of terminals, backbone nodes for routing traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said computer based interactive method comprising steps of:

inputting to said computer a first set of data corresponding to terminal locations to be clustered;

inputting to said computer a second set of data corresponding to weights corresponding to the traffic carried by each terminal location;

receiving in said computer specified parameters including a total number of terminal clusters to be formed, a minimum weight of a smallest of said terminal clusters to be formed, a maximum weight of a largest of said terminal clusters to be formed, and a maximum radius of said terminal clusters to be formed;

selecting a system output mode;

creating a number of subdivisions based on said total number of terminal clusters to be formed, wherein the square of the number of subdivisions is less than or equal to the number of terminals;

assigning each terminal to one of said subdivisions based on its location;

determining a total traffic for each of said subdivisions based on the weights of the terminals assigned to it by said assigning step;

determining a center of each of said subdivisions based on the weights and the locations of the terminals assigned to it by said assigning step;

forming a set of candidate subdivisions based on the total traffic for each of said subdivisions;

defining a location for each of said subdivisions;

assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions;

merging subdivisions in said set of candidate subdivisions into clusters;

updating centers of said clusters of merged subdivisions based on the weights and the locations of terminals of said clusters;

determining the representative locations of said clusters of said merged subdivisions; and

directing communication traffic from a first of said terminals through said representative location of the cluster in which said first terminal is located to a second of said terminals through said representative location of the cluster in which said second terminal is located.

29. The method including the computer implemented interactive method of claim 28 wherein:

said step of creating the number of subdivisions is performed by executing a first group of processor implemented instructions;

said step of assigning each terminal to one of said subdivisions is performed by executing a second group of processor implemented instructions;

said step of determining a total traffic for each of said subdivisions is performed by executing a third group of processor implemented instructions;

said step of determining a center of each of said subdivisions is performed by executing a fourth group of processor implemented instructions;

said step of forming a set of candidate subdivisions is performed by executing a fifth group of processor implemented instructions;

said step of defining a location for each or said subdivisions is performed by executing a sixth group of processor implemented instructions;

said step of assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions is performed by executing a seventh group of processor implemented instructions;

said step of merging subdivisions in said set of candidate subdivisions into clusters is performed by executing an eighth group of processor implemented instructions;

said step of updating centers of said clusters of merged subdivisions is performed by executing a ninth group of processor implemented instructions;

said step of determining the representative locations of said clusters of said merged subdivisions is performed by executing a tenth group of processor implemented instructions; and

said step of directing communication traffic is performed by executing an eleventh group of processor implemented instructions.

30. The method including the computer implemented interactive method of claim 28, wherein said system output mode is selected from a group of output modes consisting of virtual terminals, candidate backbone sites, and candidate concentrator sites.

31. The method including the computer implemented interactive method of claim 28, wherein said specified parameters further include a minimum fraction of retained subdivisions and a minimum fraction of retained weight, and wherein said step of forming a set of candidate subdivisions further includes steps of:

calculating a threshold traffic value based on the average traffic of terminals in a subdivision,

comparing the total traffic for each determined subdivision with the calculated threshold traffic value, and

adding a subdivision to said set of candidate subdivisions if its total traffic is at least equal to said calculated threshold traffic value.

32. The method including the computer implemented interactive method of claim 31, wherein if the number of subdivisions in said set of candidate subdivisions divided by the total number of subdivisions is less than the minimum fraction of retained subdivisions, some subdivisions having a total traffic less than said calculated threshold traffic value are added to said set of candidate subdivisions.

33. The method including the computer implemented interactive method of claim 31, wherein if the total weight of the subdivisions in said set of candidate subdivisions divided by the total weight of all subdivisions is less that the minimum fraction of retained weight, some subdivisions having a total traffic less than said calculated threshold traffic value are added to said set of candidate subdivisions.

34. The method including the computer implemented interactive method of claim 28, wherein said maximum radius is the maximum allowable distance from a terminal to the center of the subdivision to which it is assigned.

35. The method including the computer implemented interactive method of claim 28, wherein said step of determining a location for each of said subdivisions makes its determination based on the center of the determined subdivision.

36. The method including the computer implemented interactive method of claim 28, wherein said step of assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions assigns such terminals to the nearest adjacent subdivision included in said set of candidate subdivisions.

37. The method including the computer implemented interactive method of claim 36, wherein if there is no adjacent subdivision included in said set of candidate subdivisions, such a terminal remains in its own subdivision.

38. The method including the computer implemented interactive method of claim 28, wherein said step of merging subdivisions in said set of candidate subdivisions into clusters does so based on the centers of said subdivisions in said set of candidate subdivisions.

39. The method including the computer implemented interactive method of claim 38, wherein said step of merging merges nearest-neighbor subdivisions.

40. The method including the computer implemented interactive method of claim 39, wherein the merging of nearest-neighbor clusters continues as long as the weight of the proposed merged cluster does not exceed the maximum weight of the largest of said terminal clusters and the radius of the proposed merged cluster does not exceed the maximum radius of said terminal clusters.

41. The method including the computer implemented interactive method of claim 28, wherein said step of determining the representative locations of said clusters of said merged subdivisions does so by assigning the location of a terminal closest to the updated center of said clusters.

42. The method including the computer implemented interactive method of claim 28, wherein each cluster can be constrained to a single local access and transport area.

43. The method including the computer implemented interactive method of claim 28, wherein the location of the cluster centers can be manually selected.

44. The method including the computer implemented interactive method of claim 28, further comprising a step of storing said received set of terminal locations, said received set of weights and said received specified parameters.

45. The method including the computer implemented interactive method of claim 28, wherein said backbone nodes comprise data switches.

46. The method including the computer implemented interactive method of claim 28, wherein said concentrators comprise multiplexers.

47. The method for efficiently connecting terminals including the computer implemented method of claim 28, wherein the step of directing communication traffic further includes directing communication traffic from the first terminal to the second terminal via at least one of said backbone nodes and at least one of said concentrators.

48. A method for effectively connecting a number of terminals through backbone nodes, a backbone, and concentrators, including a computer implemented interactive method for aggregating the terminals into clusters of a distributed communications network having a plurality of terminals, backbone nodes for routing traffic within a backbone, and concentrators connected between said terminals and said backbone nodes, said computer implemented interactive method comprising steps of:

inputting to said computer a first set of data corresponding to terminal locations to be clustered;

inputting to said computer a second set of data corresponding to weights corresponding to the traffic carried by each terminal location;

receiving in said computer specified parameters including a total number of terminal clusters to be formed, a minimum weight of a smallest of said terminal clusters to be formed, a maximum weight of a largest of said terminal clusters to be formed, and a maximum radius of said terminal clusters to be formed;

selecting a system output mode;

creating a number of subdivisions, wherein the square of the number of subdivisions is less than or equal to the number of terminals;

assigning each terminal to one of said subdivisions;

determining a total traffic for each of said subdivisions;

determining a center of each of said subdivisions;

forming a set of candidate subdivisions including some of said subdivisions;

defining a location for each of said subdivisions;

assigning terminals in a subdivision not included in said set of candidate subdivisions to a subdivision in said set of candidate subdivisions;

merging subdivisions in said set of candidate subdivisions into clusters;

updating centers of said clusters of merged subdivisions;

determining the representative locations of said clusters of said merged subdivisions; and

directing communication traffic from a first of said terminals through said representative location of the cluster in which said first terminal is located to a second of said terminals through said representative location of the cluster in which said second terminal is located.

49. The method including the computer implemented interactive method of claim 48, wherein said backbone nodes comprise data switches.

50. The method including the computer implemented interactive method of claim 48, wherein said concentrators comprise multiplexers.

51. The method for efficiently connecting terminals including the computer implemented method of claim 48, wherein the step of directing communication traffic includes directing communication traffic from the first terminal to the second terminal via at least one of said backbone nodes and at least one of said concentrators.