Problem description

Suppose we want to design a Telecommunication network. We are given a set of routers, a set of links, and a set of traffic demands (measured in MB/s) between pairs of routers; for convenience we can assume each of them sits in a city. We want to find the capacity to be installed on each link in order to satisfy all traffic demands. There are several variants of this problem in the scientific literature, and an important subclass deals with the problem of provisioning virtual private networks, or VPNs for short.

In general, in VPN traffic demand is difficult to predict even in the short term, and hence the traffic demands are uncertain; however, there exist uncertainty models for such traffic demands. Here we consider one that has attracted considerable attention and that is realistic enough in VPNs. We suppose that there are two parameters s_i⁺ and s_i^- which estimate the maximum total outgoing and incoming traffic, respectively, at node i. The problem is hence that of finding the value of the capacity of every arc of the network (which is a multiple of a given unit capacity C) so as to accommodate any traffic demand d_hk from node h to node k, subject to uncertainty on these demands modeled by the upper bounds on the incoming and outgoing traffic for each node of the network.