Groupe d’études et de recherche en analyse des décisions

Design of a Survivable VPN Topology over a Service Provider Network

Brigitte Jaumard Professeure titulaire, Department of Computer Science & Software Engineering, Université Concordia, Canada

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 traffic requests. In this paper, we study the multi layer survivable design of a virtual topology in the context of multiple-hop working routing for IP layer traffic requests. The design problem is composed of two problems which are simultaneously solved: (i) Finding the most efficient or economical multi-hop routing of the IP traffic flows with different bandwidth granularities over 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 physical topology, if such a mapping exists. In order to solve such a complex multi layer resilient network design problem, we propose a column generation ILP model. It allows exploiting the natural decomposition of the problem and helps devising a scalable solution scheme. We conducted numerical experiments on a German network with 50 nodes and 88 physical links. Not only we could solve much larger data instances than those published in the literature, but also observe than multi-hop routing allows a saving of up to 10% of the number of lightpaths, depending on the traffic load.