On broadcast switching networks
Yuanyuan Yang · 1992
In a broadcast connection through a multi-stage network, an input port can be simultaneously connected to more than one output port (but an output port can be connected to at most one input port at a time). In this dissertation, new designs for both nonblocking and rearrangeable broadcast switching networks for realizing broadcast connections are presented. In the nonblocking broadcast network category, we obtain the results that lead to the currently best known explicit constructions of nonblocking broadcast networks with a constant number of stages relative to both crosspoint and control algorithm complexity. In three-stage versions of our designs, comprised of r switches of size n x m in the input stage, m switches of size r x r in the middle stage, and r switches of size m x n in the output stage, we prove that if $m >$ min($n - 1)(x + r\sp{1/x}$), where 1 $\le x \le$ min$\{n - 1,r\}$, the resulting $v$(m,n,r) network is nonblocking for broadcast assignments. This condition represents an improvement on the minimum number of middle switches from $O$(nr) to $O(n{\log r\over \log\log r}$) relative to previously known results. The results are generalized to ($2k + 1$)-stage networks for $k >$ 1. Moreover, a linear control algorithm is designed for satisfying broadcast connection requests. The sequential and parallel hardware implementations of this control algorithm are also described and analyzed. In the parallel implementation, connection requests can be satisfied in $O({(\log r)\sp2\over \log\log r}$) gate propagations for a $v$(m,n,r) network. This work provides a class of nonblocking broadcast networks for real-time parallel/distributed computing and telecommunication applications which require high-speed network path routings. In the rearrangeable broadcast network category, we present analytical results which permit the rearrangeability of broadcast networks to be evaluated on the basis of fundamental parameters associated with the network structure so that the trade-off between the network rearrangeability and the network cost can be determined. These results permit our broadcast networks to be designed for which the average number of rearrangements for satisfying a connection request in and N x N network can be reduced to $O$(1) in comparison with $O(N)$ in other existing designs while holding the asymptotic crosspoint growth to $O(N$ log $N$). Our analytically derived results are supported by simulation data. This work provides a class of low-cost broadcast networks for broadcasting and conferencing applications wherein only a limited degree of rearrangeability can be tolerated.