Embedding Of Fault-Tolerant Trees in the Josephus Cube

摘要

The tree interconnection network lends itself to several suitably structured applications. However, the low connectivity at each node, traffic congestion and single point of failure "at the root node reduce reliability and availability. Both the hypertree and X-tree are fault-tolerant variants of the basic tree network and have been the focus of more recent implementation and research interest. In this paper, we introduce a recently proposed family of interconnection networks known as the Josephus Cubes and show how hypertrees, X-trees and ringed X-trees of arbitrary height can be near-optimally embedded in this novel interconnection network. Embedding techniques used for both hypertree and X-trees are simple and may be recursively applied.