Fault-tolerant routing with regularity restoration in Boolean n -cube interconnection networks

This paper proposes a set of techniques to restore the regularity of a Boolean n-cube network in the presence of node failures, and algorithms to effectively route messages among the surviving nodes. An analytical model to evaluate the degradation of a damaged network is also presented. One way to restore the regularity of a damaged Boolean n-cube network is by simply disabling the nodes with more than one bad neighbor. The remaining network is called a `1-degraded subnet´. A very simple optimal-path routing algorithm, which requires each node to know only its neighbor´s status, is developed for such a subnet. Since many nonfaulty nodes may have to be disabled in constructing a 1-degraded subnet, the authors further develop a heuristic algorithm to restore the network´s regularity by constructing a `subnet connected with optimal paths (SCOP)´, where only a few nodes must be disabled. The routing algorithm used in 1-degraded subnets also works for SCOPs. To preserve the processing power of the network, they also propose a two-level hierarchical fault-tolerant routing scheme without disabling any nodes