A Unified Algorithm for Designing Multidrop Teleprocessing Networks

Abstract

The problem of designing minimum-cost multidrop lines which connect remote terminals to a concentrator or a central data-processing computer is studied. In some cases, optimal solutions can be obtained by using either linear integer programming or a branch-bound method. These approaches are not practical, since they lack flexibility and require an enormous amount of computer time for most practical problems. As a consequence, heuristic algorithms have been developed by various authors. In this paper, we point out that all of these algorithms fall into the class of minimum spanning tree (MST) problems, constrained by traffic or response time requirements. The difference between them is mainly the sequential order with which a branch or a line is selected into the tree. Without the constraints, all algorithms converge to a MST. With the constraints, they form different subtrees. Most of the algorithms can be unified into a modified Kruskal's MST algorithm. In the modified algorithm, a weight is associated with each terminal. Let w <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> be the weight associated with terminal <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</tex> , and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d_{i}{j}</tex> be the cost for the line directed from terminal <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</tex> to terminal <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</tex> . When the algorithm fetches the cost for the line, it replaces it with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d_{i}{j} - w_{i}</tex> . In some cases, w <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> 's need to be readjusted in the middle of the algorithm. The difference between all existing heuristic algorithms is in the way w <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> 's are defined. If w <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> is zero for all <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</tex> , the algorithm reduces to the unmodified Kruskal's algorithm; if w <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> is set to zero whenever a line incident to terminal <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</tex> is selected as a tree branch, the algorithm reduces to Prim's MST algorithm. An extension of the algorithm to the solution of an associated problem of partitioning the terminals with respect to a predetermined set of concentrators, multiplexers, terminal interface processors, or central computers is also derived. The efficiency of an algorithm depends greatly on how it is implemented. The computational complexity of the unified algorithm is in the order of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N^{2} log N</tex> for the most general case, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</tex> is the number of terminals. By using good heuristics, it reduces to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K_{1}N log N + K_{2}N</tex> , where K <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</inf> and K <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</inf> are constants, for many practical applications. The algorithm has been applied to large networks with over 1000 terminals, yielding excellent results and using only 15 seconds of computer time on a CDC 6600 computer. Designs obtained by using different w <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> 's are compared.