Nonblocking multirate broadcast networks for parallel and distributed computing systems

Designing efficient interconnection networks with powerful connecting capability remains a key issue in parallel and distributed computing systems. Much progress has been made in nonblocking broadcast networks, which can realize all one-to-many connections between any network input port and a set of output ports without any disturbance (that is, rearrangement) of other existing connections. However, all results obtained so far for broadcast networks are for the circuit-switching or single-rate communication model. Meanwhile, there has been growing interest in large networks operating in a packet-switching manner. This type of network can be modelled as a multirate network wherein a single link can be shared by multiple connections with arbitrary data rate. Previous work has focused on the blocking behaviour of multirate one-to-one connection or permutation networks; very little is known about the behaviour of multirate one-to-many connection or broadcast networks. In this paper, the author determines nonblocking conditions for υ(m, n₁, r₁, n₂, r₂) networks under which any multirate broadcast connection request from a network input port to a set of network output ports can be satisfied without any disturbance of the existing connection in the network. The results show that more general multirate broadcast networks can be constructed in the same order of hardware complexity as the best available single-rate nonblocking broadcast networks. The proofs for the theorems also imply an efficient routing algorithm for such networks. Multirate broadcast networks can provide strong support for parallel and distributed computing systems that are required to broadcast multirate data in a random-access environment.