Optimization of Computer Networks

Chapter 7Topology Design Problems

7.1 Introduction

Topology design refers to the network problems that optimize the set of nodes and/or links to deploy in a network. These problems typically appear in the elaboration of long-term network planning projects for network deployments or upgrades. When these planning studies correspond to a network to build from scratch, they are referred to as greenfield planning. When they are recommendations for adding or upgrading links/nodes in an existing network, they are commonly called brownfield planning.

Topology planning tasks are typically conducted offline by consultant companies or planning departments within the network operator. Since the deployment of nodes and links involves a high cost and impacts on the performance merits achievable later, an accurate modeling of the problem and a good method to find numerical solutions are critical points. In this context, topology design problems can be solved without major time constraints in a centralized form. However, the problem variants of practical interest are typically -complete, formulated using integer programs and thus it is -hard finding even approximate solutions, and there are no algorithms that guarantee obtaining them in worse case polynomial time. Then, we should get along with ...