In this article, we study capacitated network design problems. We unify and extend polyhedral results for directed, bidirected, and undirected link capacity models. Valid inequalities based on a network cut are known to be strong in several special cases. We show that regardless of the link model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Our investigation of the facial structure of the cutset polyhedra allows to complement existing polyhedral results for the three variants by presenting facet-defining flow-cutset inequalities in a unifying way. In addition, we present a new class of facet-defining inequalities, showing as well that flow-cutset inequalities alone do not suffice to give a complete description for single-commodity, single-module cutset polyhedra in the bidirected and undirected case – in contrast to a known result for the directed case. The practical importance of the theoretical investigations is highlighted in an extensive computational study on 27 instances from the Survivable Network Design Library (SNDlib). © 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(2), 141–156 2011

Abstract This article describes the Survivable Network Design Library (SNDlib), a data library for fixed telecommunication network design available at http://sndlib.zib.de . In the current version 1.0, the library contains data related to 22 networks which, combined with a set of selected planning parameters, leads to 830 network design problem instances. In this article, we discuss the data concepts of SNDlib and describe a mathematical model for each design problem considered in the library. We also provide information on characteristic features and the origin of the SNDlib problem instances. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract — The recent surge of new viruses and host attacks in the Internet and the tremendous propagation speed of selfdistributing attacks has made network security a pressing issue. To protect an end-system, it must continuously be patched and additional security tools like an Intrusion Prevention System (IPS) are needed. The main problems are the effort for the users and network performance: The last years have shown that many users neither maintain their computers nor run an IPS. Accordingly, their systems remain vulnerable. On the other hand, the operation of an IPS inevitably decreases network performance as all packets are analyzed for malicious content before being forwarded. We recently proposed the operation of a flexible overlay network of intrusion prevention systems running on top of programmable routers to mitigate these issues. With this architecture, security services can be dynamically distributed in the network. In this paper, we leverage this flexibility for minimizing the impact of intrusion prevention on network performance. Based on measurement from experiments with a prototype implementation of a programmable router, we derive an analytical description of the impact of a single active router on the network. This is then used to formulate two mixed integer optimization models for finding placement strategies for security services. Using detailed simulations on two example networks we show that the optimized strategies perform significantly better than reference placement strategies, including centralized intrusion prevention. I.