Patent US1967533A successfully refreshed from Google Patents.
Patent US5652841A successfully refreshed from Google Patents.
US5652841A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for aggregating terminals into clusters to assist in the construction of a distributed data communication network
Assignee: Individual
•
Filing: 1995-06-07
•
Granted: 1997-07-29
•
Expires: 2015-06-07
Abstract
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.
Inventors
- 👤 Paul Nemirovsky
- 👤 Michael Ball
- 👤 Roy Dahl
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 16:59
CPC Classifications
H; H04; H04L; H04L45/00; H04L45/02; H04L45/04; H04L45/46
Claims Analysis
Total Claims: 56
Claim 1
Independent Claim
318 words
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.
Claim 2
Dependent Claim
318 words
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.
Claim 3
Dependent Claim
30 words
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.
Claim 4
Dependent Claim
41 words
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.
Claim 5
Independent Claim
430 words
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.
Claim 6
Independent Claim
430 words
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.
Claim 7
Dependent Claim
240 words
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.
Claim 8
Dependent Claim
35 words
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.
Claim 9
Dependent Claim
101 words
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.
Claim 10
Dependent Claim
60 words
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.
Claim 11
Dependent Claim
63 words
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.
Claim 12
Dependent Claim
34 words
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.
Claim 13
Dependent Claim
38 words
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.
Claim 14
Dependent Claim
51 words
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.
Claim 15
Dependent Claim
33 words
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.
Claim 16
Dependent Claim
39 words
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.
Claim 17
Dependent Claim
17 words
The apparatus including the computer based interactive device of claim 14 wherein said processor merges nearest-neighbor subdivisions.
Claim 18
Dependent Claim
59 words
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.
Claim 19
Dependent Claim
42 words
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.
Claim 20
Dependent Claim
25 words
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.
Claim 21
Dependent Claim
22 words
The apparatus including the computer based interactive device of claim 4 wherein the location of the cluster centers can be manually selected.
Claim 22
Dependent Claim
41 words
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.
Claim 23
Dependent Claim
40 words
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.
Claim 24
Dependent Claim
18 words
The apparatus including the computer based interactive device of claim 4, wherein said backbone nodes comprise data switches.
Claim 25
Dependent Claim
16 words
The apparatus including the computer based interactive device of claim 4, wherein said concentrators comprise multiplexers.
Claim 26
Independent Claim
368 words
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.
Claim 27
Independent Claim
368 words
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.
Claim 28
Dependent Claim
18 words
The apparatus including the computer based interactive device of claim 24, wherein said backbone nodes comprise data switches.
Claim 29
Dependent Claim
16 words
The apparatus including the computer based interactive device of claim 24, wherein said concentrators comprise multiplexers.
Claim 30
Dependent Claim
40 words
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.
Claim 31
Independent Claim
384 words
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.
Claim 32
Independent Claim
384 words
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.
Claim 33
Dependent Claim
265 words
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.
Claim 34
Dependent Claim
35 words
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.
Claim 35
Dependent Claim
98 words
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.
Claim 36
Dependent Claim
60 words
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.
Claim 37
Dependent Claim
63 words
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.
Claim 38
Dependent Claim
34 words
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.
Claim 39
Dependent Claim
34 words
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.
Claim 40
Dependent Claim
52 words
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.
Claim 41
Dependent Claim
33 words
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.
Claim 42
Dependent Claim
40 words
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.
Claim 43
Dependent Claim
19 words
The method including the computer implemented interactive method of claim 38, wherein said step of merging merges nearest-neighbor subdivisions.
Claim 44
Dependent Claim
59 words
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.
Claim 45
Dependent Claim
43 words
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.
Claim 46
Dependent Claim
25 words
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.
Claim 47
Dependent Claim
22 words
The method including the computer implemented interactive method of claim 28, wherein the location of the cluster centers can be manually selected.
Claim 48
Dependent Claim
33 words
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.
Claim 49
Dependent Claim
18 words
The method including the computer implemented interactive method of claim 28, wherein said backbone nodes comprise data switches.
Claim 50
Dependent Claim
16 words
The method including the computer implemented interactive method of claim 28, wherein said concentrators comprise multiplexers.
Claim 51
Dependent Claim
49 words
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.
Claim 52
Independent Claim
321 words
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.
Claim 53
Independent Claim
321 words
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.
Claim 54
Dependent Claim
18 words
The method including the computer implemented interactive method of claim 48, wherein said backbone nodes comprise data switches.
Claim 55
Dependent Claim
16 words
The method including the computer implemented interactive method of claim 48, wherein said concentrators comprise multiplexers.
Claim 56
Dependent Claim
48 words
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.
References Cited (Backward Citations)
US5253161A
Cited
US5426674A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-07-28 | 2001-01-27 | 2001-07-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-07-28 | 2005-01-27 | 2005-07-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-07-28 | 2009-01-27 | 2009-07-29 | $7700.00 | Window Closed / Lapsed |