Towards optimally resilient topologies against optimal attacks
Martin Backhaus, Guenter Schaefer · 2017
By overlay topology optimization with regard to the minimum number of overlay edges that need to breakdown until all communication between two chosen nodes ceases, the robustness against optimal attacks can be maximized and the network can still perform its operation despite (multiple) link-failures. This article presents an approach to construct optimally resilient topologies on the basis of a metric used by an optimal attacker: the minimum overlay cut. We developed a bilevel Integer Linear Program (ILP) formulation for exactly calculating optimal overlay topologies on small problem instances consisting of two-layer networks. Since bilevel optimization is very hard to perform in practice on bigger networks, we propose an approximation algorithm as well, whose quality can be assessed on smaller instances. An evaluation of a typical VPN networking scenario shows that compared to the obvious approach of realizing maximal robustness towards attackers by a fully meshed overlay, our approach reaches the same desired connectivity with far fewer overlay edges.