TOPOLOGICAL OPTIMIZATION OF COMPUTER COMMUNICATION NETWORKS: APPROXIMATE ALGORITHMS AND BOUNDS

摘要

The need to share data and computing facilities among several remotely located users has become increasingly important. We deal with the problem of finding the lowest cost interconnection network observing certain performance and reliability constraints. The networks treated are centralized. Three major network models, namely the Star-Star (SS), the Multidrop (MD), and the Multiloop (ML), are considered. The main problem is divided into three subproblems, namely the Terminal Layout Problem (TLP), the Terminal Assignment Problem (TAP), and the Concentrator Location Problem (CLP). The generic problem P(X,Y:Z) is to solve problem Y (i.e., TLP, TAP, or CLP) with the constraint set Z and the model X (i.e., SS,MD, or ML). The problem SSCLP is P(SS,CLP:CC). The computational complexity of various computer network design problems is considered. It is proven that P(SS,CLP:CC) with the capacity constraint K (LESSTHEQ) 2 can be solved in O((n + m)('3)) time, where n is the number of terminals and m is the number of potential concentrator sites, and P(SS,CLP:(SLASHCIRC)) is NP-complete. P(SS,CLP:CC) with K = 3 is strongly NP-complete, and all the six problems P(ML,Y:Z) are NP-complete, where Y is CLP, TAP, or TLP, and Z is (SLASHCIRC) or CC. We show that SSCLP can be formulated as a Minimization of a Supermodular Set Function (MSSF). The equivalence of the chain-property and local-optimality for the MSSF is established. A performance bound for the GREEDY and STINGY heuristics applied to MSSF is established. Three systems of inequalities are derived and they are used to obtain lower bounds. The Lagrangian Relaxation (LR) method is considered. Three forms of the LR method are used for SSCLP. The resulting relaxed problems are shown to be equivalent to (different) linear programming problems. A heuristic is suggested for SSCLP that produces both a feasible solution and a lower bound. It is shown that if z an z are the lower and upper bounds found by the heuristic, respectively, then z/z (LESSTHEQ) K. Some computational examples with up to 50 terminals and 20 potential concentrator sites are considered. All the network designs obtained are shown to be within 2.8% of optimal.