Science of Communication and Computation

Exhibition Program 9

Designing fault-tolerant networks

Maximizing network reliability via binary decision diagrams

Abstract

We show an optimization algorithm that can automatically find the positions to add links to infrastructure networks, including communication networks and road networks, that maximizes reliability of the network. Network reliability is the measure that shows how robust a network is against failures of its components. The optimization problem is known to be a hard problem since we have to count up exponentially many failure patterns. We use Binary Decision Diagram (BDD), data structure that can represent the set of failure patterns in a compact form, to solve the network reliability maximization problem. Our algorithm can find optimal solutions of the problems whose size is 10 times larger than those can be solved with existing methods. Our algorithm enables to design more reliable infrastructure networks with lower costs. In the future, we are planning to improve scalability of the algorithm to apply the algorithm to wider range of network designing problems.

Reference

  • [1] M. Nishino, T. Inoue, N. Yasuda, S. Minato, M. Nagata, “Optimizing network reliability via best-first search over decision diagrams,” In Proc. IEEE Conference on Computer Communications (INFOCOM 2018), April 2018.

Poster

Photos

Presenters

Masaaki Nishino
Masaaki Nishino
Innovative Communication Laboratory