Wormhole Broadcast in Hypercubes

Abstract

We consider the problem of broadcasting a message in the n-cube, Q_n, equipped with wormhole switching. The communication model assumed is one-port, and the broadcasting scheme is path-based whereby, during broadcasting along a path by a node, all the nodes on that path will receive the message. The wormhole path length is m where <m≤n, and thus this is a generalization of an earlier work which considered a path length of n. First, a method is proposed which is based on recursively partitioning the cube to subcubes of dimension m, and then calling the previously developed algorithm on such Q₋m's concurrently (cube-based broadcast). The second method is based on the concept of Gray codes (GCs), and at every given step, it forms the Hamiltonian path of appropriate size as the broadcast path (GC-based broadcast). It is shown that the steps required in GC-based broadcast is fewer than or equal to those needed by cube-based broadcast. Furthermore, comparison of time complexity of GC-based broadcast to the lower bound reveals that this algorithm is near-optimal, and in fact optimal in many cases. This work improves on the best algorithm developed for path-based broadcast in one-port hypercube both in complexity and in simplicity.