General methods for computer network design
Irina Neuman, Bezalel Gavish · 1987
This dissertation deals with several issues in the design of backbone networks. Models for the cost effective routing of messages and selection of link capacities in the network are developed. Since the models obey a single philosophy, namely the formalization of the tradeoffs existing between the system costs and the costs associated with the level of performance achieved by a given design, together they form a coherent design tool. The novelty of the approach consists in the inclusion of economic aspects that explicitly express the cost-performance tradeoffs, and in using new modeling and solution techniques. First, the problem of routing and capacity assignment is discussed. A mathematical model, that simultaneously captures both aspects of the problem is developed. Lower bounds and heuristic procedures are suggested. From the results of computational experiments it is concluded that the algorithm is both efficient in terms of its speed of convergence, and effective in identifying robust solutions to the problem. The implicit assumption, common to most of the work done in the field, that all the messages in the network are identical in terms of their characteristics and service requirements is dropped in the following chapter. A group of related models dealing with the flow and capacity assignment in networks that support different classes of messages is presented. Lower and upper bounding procedures are imbedded in a fast converging algorithm that succeeds in generating feasible solutions very close to optimality. The results of the computational experiments clearly evidence the impact that distinguishing between the different types of messages has on the characteristics of the final solutions. The last chapter concentrates on the cost effective routing of messages in a network with unreliable components. The survey of the existing literature shows that, in spite of its importance, this type of design problem is seldom mentioned, mainly due to its complexity. The model and solution procedure developed in this chapter deal with the simultaneous selection of primary and secondary routes, to be used as backups. A solution procedure for the model is presented and tested in computational experiments.