Fault-tolerant message routing in the extended hypercube

In real-time computing applications, it is important to have parallel computing systems that not only exhibit high performance but also continue to perform reliably under faulty conditions. The hypercube is one of the most popular and robust network topologies used for building distributed memory message passing multiprocessor systems. However, the hypercube does not have a constant building block and it is difficult to build hypercubes of large dimensions on account of the logarithmic degree of connectivity. The extended hypercube architecture exhibits such good properties as constant degree of node, low diameter and a constant basic building block. In addition it has a hierarchical; recursive and highly scalable structure. The extended hypercube is also robust to link faults. However the extended hypercube suffers from poor fault-tolerance to node faults as it has articulation points. In this paper we present a fault-tolerant variation of the extended hypercube, the extended hypercube with symmetrical connections. The latter topology retains all the positive features of the former and in addition exhibits improved fault-tolerant characteristics. We design efficient fault-tolerant routing algorithms for the extended hypercube architectures and report simulation results