Analysis of network topologies and fault-tolerant routing algorithms using binary decision diagrams

Abstract

In the past a plethora of network topologies together with fault-tolerant routing algorithms have been proposed. Some properties have been analyzed analytically or by simulation. In most cases only some properties can be derived. There is renewed interest in the topic for application as networks-on-chip. The availability of higher computing performance and libraries for manipulating binary decision diagrams allows the complete analysis in an automated fashion. The approach is presented in this paper together with some insights on strategies to keep the computational effort reasonable when scaling the network size. © 2010 IEEE.