Chapter 12

Survivable Networks

Abstract

Network topologies should be designed to provide resilience against link failures. A network with good resilience properties is referred to as a survivable network. There are many possible measures of resilience. k-Connectivity is often used as a design criterion. We present a primal-dual approximation algorithm due to Goemans and Williamson. A local search procedure for survivable network design is also discussed.

The reliability polynomial is a probabilistic measure of network reliability. The difficulty is calculating its factors, a problem which is NP-complete. We present a randomized method to calculate these factors approximately. Some special topologies with known resilience robustness are discussed, ...

Get Design of Modern Communication Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.