Virtual Private Network Design Under Traffic Uncertainty

by

Aysegul Altin
Bilkent University 

A Virtual Private Network (VPN) service is similar to a private network service, which
enables a group of nodes over a large underlying network to communicate with each
other. The important difference between the two is VPN does that using an already
available physical network like the Internet.

The focus of our research is the design of a VPN under traffic uncertainty. We deal with the
general traffic uncertainty case, where the traffic vector belongs to a polytope defined by
some customer specific constraints. Moreover, the solution, which is the set of edges
of the underlying backbone graph with positive capacity reservation, is allowed to be
an arbitrary subgraph of the underlying graph. Hence, we call this problem as Poly-G
for which we offer three different linear programming formulations and this is our main

contribution. Finally, we propose a Column Generation Algorithm and a Cutting Plane
Algorithm so as to solve these formulations efficiently.