Chapter 5Capacity Assignment Problems

5.1 Introduction

Given a network topology c5-math-0001, with c5-math-0002 the set of nodes and c5-math-0003 the set of links, the capacity assignment problem decides on the capacity c5-math-0004 allocated to each link c5-math-0005. 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 ...

Get Optimization of Computer Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.