ILP-based design of survivable broadcast trees

Abstract

We study survivable broadcast in high-speed networks against a single link/node failure. We follow the classic approach of blue/red tree [1] to construct a pair of spanning trees (i.e. a blue tree and a red tree) such that the connectivity between the root and an arbitrary node is ensured (via at least one tree) in the presence of a single link/node failure. To ensure that the blue and red trees are constructed in a cost-efficient way, heuristic algorithms have been designed to minimize the cost involved in tree construction. In this paper, we tackle the same problem but resorting to Integer Linear Programming (ILP) for optimal solutions. Two efficient ILPs are formulated, one for protecting against single link failure (MinCost-E) and the other for node failure (MinCost-V). Numerical results show that our ILPs can generate optimal solutions in relatively short amount of time. As compared with the existing heuristic algorithms, we observe a significant improvement in performance. © 2009 IEEE.