Optimal broadcasting in toroidal networks

The authors study routing algorithms for broadcasting in multiprocessors whose interconnection networks have a toroidal structure. A toroidal network is an n-dimensional rectangular mesh with additional edge-to-edge connections. Criteria are proposed for the optimality of these algorithms for broadcasting. On the basis of these criteria two routing algorithms are analyzed, one already known and the other proposed by the authors. The proposed algorithm behaves better than the known algorithm and should therefore be used for broadcasting in toroidal networks.<>