Design of a Survivable VPN Topology over a Service Provider Network

Speaker : Brigitte Jaumard
Concordia University, Canada
Date: 14/05/2013
Time: 2:00 pm - 3:00 pm
Location: LINCS Meeting Room 40


Survivability in IP-over-WDM networks has already been extensively discussed in a series of studies. Up to date,most of the studies assume single-hop working routing of trafficrequests. In this paper, we study the multi layer survivable designof a virtual topology in the context of multiple-hop workingrouting for IP layer traffic requests. The design problem iscomposed of two problems which are simultaneously solved:( i ) Finding the most efficient or economical multi-hop routingof the IP traffic flows with different bandwidth granularitiesover the virtual topology, which involves some traffic grooming,( ii ) Ensuring that the virtual topology is survivable throughout an appropriate mapping of the virtual links over the physicaltopology, if such a mapping exists.In order to solve such a complex multi layer resilient networkdesign problem, we propose a column generation ILP model. Itallows exploiting the natural decomposition of the problem andhelps devising a scalable solution scheme.We conducted numerical experiments on a German networkwith 50 nodes and 88 physical links. Not only we could solve muchlarger data instances than those published in the literature, butalso observe than multi-hop routing allows a saving of up to 10%of the number of lightpaths, depending on the traffic load.