Design of Modern Communication Networks

Chapter 4

Topological Design

Abstract

A fundamental step toward a cost-efficient and well-performing network is designing the network topology. The problem is finding a network topology with allocated resources so that the end-to-end flow requirements are met, at minimum cost. The problem is -complete. Some common topologies and their properties are shown.

Central to the topology design problem is the cost function representing link costs. Two approximate combinatorial algorithms for general topology design are presented. The first is built on a generalization of spanning trees, called spanners. The second is an extension of an algorithm originally ...