Wormhole broadcast in hypercubes

We consider the problem of broadcasting a message in the n-cube, Q(n), equi pped with wormhole switching. The communication model assumed is one-port, and the broadcasting scheme is path-based whereby, during broadcasting alon g a path by a node, all the nodes on that path will receive the message. Th e wormhole path length is m where < m less than or equal to n, and thus thi s 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 t he cube to subcubes of dimension m, and then calling the previously develop ed algorithm on such Q(-)m's concurrently (cube-based broadcast). The secon d method is based on the concept of Gray codes (GCs), and at every given st ep, 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 broa dcast is fewer than or equal to those needed by cube-based broadcast. Furth ermore, comparison of time complexity of GC-based broadcast to the lower bo und reveals that this algorithm is near-optimal, and in fact optimal in man y cases. This work improves on the best algorithm developed for path-based broadcast in one-port hypercube both in complexity and in simplicity.