CIRCUIT-SWITCHED BROADCASTING IN TORUS NETWORKS

In this paper we present three broadcast algorithms and lower bounds o n the three main components of the broadcast time for 2-dimensional to rus networks (wrap-around meshes) that use synchronous circuit-switche d routing. The first algorithm is based on a recursive tiling of a tor us and is optimal in terms of both phases and intermediate switch sett ings when the start-up time to initiate message transmissions is the d ominant cost. It is the first broadcast algorithm to match the lower b ound of log(5) N on number of phases (where N is the number of nodes). The second and third algorithms are hybrids which combine circuit-swi tching with the pipelining and are-disjoint spanning trees techniques that are commonly used to speed up store-and-forward routing. When the propagation time of messages through the network is significant, our hybrid algorithms achieve close to optimal performance in terms of pha ses, intermediate switch settings, and total transmission time. They a re the first algorithms to achieve this performance in terms of all th ree parameters simultaneously.