TOPOLOGICAL DESIGN OF COMPUTER-COMMUNICATION NETWORKS - THE OVERALL DESIGN PROBLEM

Mathematical formulations of the topological design problem of computer communication networks are developed. The topological design of computer networks involves decisions on where to place network control processors (NCPs), selecting the set of backbone links to connect NCPs, linking end user nodes to the NCPs, and deciding on the set of routes which support communications between communicating end user node pairs. The overall design problem is formulated as a nonlinear combinatorial optimization problem, a Lagrangean relaxation of the problem is presented and effective solution procedures of the Lagrangean problem are developed. The Lagrangean solutions provide lower bounds on the optimal solutions to the complete problem. The Lagrangean-based solutions are further improved using subgradient optimization procedures. Three heuristics are developed for generating feasible solutions to the problem. The heuristic solutions are demonstrated on problems involving 200 end user nodes and up to 30 NCP locations.