Fault free shortest path routing on the de Bruijn networks

It is shown that the de Bruijn graph (dBG) can be used as an architecture for interconnection networks and a suitable structure for parallel computation. Recent works have classified dBG based routing algorithms into shortest path routing and fault tolerant routing but investigation into shortest path in failure mode in dBG has been non-existent. In addition, as the size of the network increase, more faults are to be expected and therefore shortest path algorithms in fault free mode may not be suitable routing algorithms for real interconnection networks, which contain several failures. Furthermore, long fault free path may lead to high traffic, high delay time and low throughput.In this paper we investigate routing algorithms in the condition of existing failure, based on the Bidirectional de Bruijn graph (BdBG). Two Fault Free Shortest Path (FFSP) routing algorithms are proposed. Then, the performances of the two algorithms are analyzed in terms of mean path lengths. Our study shows that the proposed algorithms can be one of the candidates for routing in real interconnection networks based on dBG.