O'Reilly logo

Optimization of Computer Networks by Pablo Pavón Mariño

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 c7-math-0001-complete, formulated using integer programs and thus it is c7-math-0002-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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required