Broadcasting in all-output-port cube-connected cycles with distance-insensitive switching

In this paper, we consider the problem of one-to-all broadcast (OAB) in an interconnection network with the topology of the n-dimensional cube-connected cycles, CCCn, under the following conditions. Routers use distance insensitive switching, e.g., wormhole. A OAB proceeds in rounds that consist of message passing between pairs of nodes using disjoint paths. Routers also have all-output-port functionality, i.e., they can send a packet via all output ports simultaneously. In CCCn, this assumption implies that the lower bound on the number rounds of the OAB is log4(|V(CCCn)|). The main result of this paper is an algorithm for the OAB in CCCn whose number of rounds is greater than the lower bound by at most 1 for all n<123. The algorithm is depth-contention-free and therefore, it works correctly even if nodes participating in the broadcast run asynchronously. We also show how to make the algorithm deadlock-free.