Optimization of Computer Networks

Chapter 5Capacity Assignment Problems

5.1 Introduction

Given a network topology , with the set of nodes and the set of links, the capacity assignment problem decides on the capacity allocated to each link . This problem appears in two main (quite diverse) contexts: (i) as a problem to be solved periodically at long time scales (e.g., every 6 months) to upgrade the capacity of deployed links in a network and (ii) as a control problem to solve at subsecond time scale, to allocate capacity to users in a dynamic environment. We provide two examples:

• (Slow) Capacity planning: In Internet Service Provider (ISP) backbone networks, network links are virtual circuits hired to a network carrier,or transport connections established in an own network infrastructure. The link costs depend on the link distance and capacity according to the carrier tariffs or the infrastructure cost structure. ISPs periodically (e.g., every 6 months) execute a so-called capacity planning process [1] or capacity expansion ...