Towards construction of efficient and optimally resilient VPN topologies by exactly calculating Maximum Disjoint Paths
Martin Backhaus, Guenter Schaefer · 2017
By carefully selecting and establishing overlay edges and computing multiple underlay-edge-disjoint paths, the ability to still fulfill demands in a VPN in case of edge-failures can be significantly increased. This article presents an approach to construct efficient and optimally resilient VPN overlay topologies together with the corresponding overlay paths to fulfill a given set of demands (connectivity between pairs of nodes). For this, we developed an Integer Linear Programming (ILP) formulation for exactly calculating the metric of Maximum Disjoint Paths in two-layer network topologies which also computes the respective overlay paths. By careful adaptation of the ILP formulation, it is possible to compute solutions for networks of significant size. Based on this ILP, an algorithm is presented that computes efficient and optimally stable overlay topologies. An evaluation of a typical VPN networking scenario shows that compared to the obvious approach of realizing maximal possible connectivity by a fully meshed overlay, our approach reaches the same desired connectivity with far fewer overlay edges.