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.