Circuit-switched row-column broadcasting in torus and mesh networks

This paper is concerned with broadcasting on 2-dimensional torus and mesh networks using circuit-switched, half-duplex, and link-bound communication. It is assumed that there are α and β physical channels in the X- and Y-dimensions, respectively, and path selection between any two nodes is done using row-column routing. Given an n × n mesh or torus, we first discuss the lower bounds of broadcasting time; any broadcasting algorithm requires at least [log(2α + 2β + 1)n²] time steps and no broadcasting algorithm achieves this lower bound if α < β(2β + 1). We then show that broadcasting on a (2α + 2β + 1)^p × (2α + 2β + 1)^p torus can be done in 2p time steps, which is optimum, for any α ≥ 3 and β = 1. We also present approximation algorithms for the cases of mesh when α ≥ 1 and β = 1 and torus when α ≤ 2 and β = 1.