Topological Design of Teleprocessing Networks Using Linear Regression Clustering

Cost-effective design of networks linking many remote terminals to a central computer (CPU) involves use of low-speed data lines to link geographically close terminals to concentrators. The concentrators are connected via high-speed data lines to the CPU. A design algorithm based on clustering of terminals followed by optimization of location, capacity and number of concentrators in each cluster is developed and evaluated. Evaluation is based on network designs for sets of 20 randomly (uniformly) generated locations of up to 500 terminals, with specific (realistic) cost versus capacity schedules being used for data lines and concentrators. In comparison with the popular Add algorithm, our linear regression clustering (LRC) algorithm has the following advantages: 1) the total cost of the concentrators, low-speed terminal lines, and high-speed CPU lines is typically 8 percent less; 2) the average transmission time delay at the terminals is typically 40 percent less; 3) the cost of adding low-speed data lines to connect additional terminals to concentrators in existing networks is typically 50 percent less; 4) the computational cost of design is typically 20 times less for 100-terminal networks and 150 times less for 500-terminals networks. Implications of the results and suggestions for further work are discussed.