Josephus Cube: A Novel Interconnection

Abstract: In this paper we present a novel interconnection topology, The Josephus Cube that satisfies greater flexibility in network sizes, more efficient embeddings, incremental scalability, reduced diameter and fault tolerance. Josephus Cube is a super graph of the N-cube and several of its variants i.e. hyper-tree and X-trees. The topology can systematically interconnect an arbitrary number of nodes; its scalability, diameter, communication performance and total number of edges compare favourably with the N-cube. It also supports a simple routing strategy that is minimal, deadlock-free and· live lock-free.

Keywords: Interconnection network, Embedding, Routing Strategy; traffic congestion; deadlock and live-lock free.