A STUDY OF ODD GRAPHS AS FAULT-TOLERANT INTERCONNECTION NETWORKS

In this paper, we analyze odd graphs for building communication architecture for large multiprocessor systems. An odd graph consists of [GRAPHICS] nodes, where d is the degree of the graph. The topology is shown to possess many attractive features, noted among them is its capability of maximal fault tolerance and possession of the widest possible container, strong resilience, and higher density. It admits simple distributed routing algorithms both for the faulty and fault-free network and is easy to diagnose. The most important property of these networks is their ability to partition into symmetrical regions. This property is based on a combinatorial structure, known as the Hadamard matrix, and can be effectively utilized for the purpose of expansion and self-diagnostic.