Embeddability and recovery of a bubblesort star graph interconnection network
The bubblesort star graph interconnection network is a merging network of the star graph and the bubblesort graph, and have many advantages over the latter two networks'. In this paper, a new approach is proposed for embedding a (2n - 5) level or a (2n - 4) level complete binary tree (CBT) with dilation one into an n-dimensional bubblesort star graph interconnection network (BSn). A recovery scheme which can recover a single fault in one step and with dilation less than or equal to 3 is also presented. Furthermore, a large number, one-third, of the nodes in the CBT can be recovered in the smallest number of recovery steps and with dilation less than or equal to 4. The fault-tolerant embedding approach can be extended to embed [n/2] CBT2n-5's or [n/4] CBT2n-4's into the BSn, and-the capability of multiple faults recovery is still remained. Therefore, the expansion of the proposed approach is as small as n!/([n/2] x (2(2n-5) - 1)) or n!/([n/4] x (2(2n-4) - 1)).
embeddability recovery bubblesort star graph interconnection network