Optimization of Computer Networks

Chapter 12Heuristic Algorithms

12.1 Introduction

This chapter is devoted to the development of offline algorithms for non-convex -hard network problems, typically executed in centralized servers, and without major running time requisites (e.g, from minutes to hours). These problems typically appear in contexts like:

• Capacity planning: Planning departments elaborate upgrade plans for the link and node capacities or the placement of new links/nodes for the upcoming year, to cope with a forecasted traffic growth. These tasks typically receive the name of capacity planning.
• Greenfield network planning: A greenfield plan involves designing a network from scratch, for example to plan a network deployment in a region where the operator is currently absent.
• Brownfield network planning: Brownfield planning tasks refer to aredesign of a large portion of an existing network, reusing some or all of the legacy equipment in place, for example, in a migration plan to a new network technology.
• Online network optimization: The increasing introduction of Software Defined Networking (SDN) instruments in the network, permits automating multiple tasks that traditionally required manual intervention. For instance, the unified collection of traffic measurements, routing, and topology information from diverse databases, can now be managed by so-called SDN controllers. Then, the updated network state ...