Networks for Fast and Efficient Unicast and Multicast Communications

Abstract

This dissertation presents new results on networks for high-speed unicast and multicast communications which play key roles in communication networks and parallel computer systems. Specifically, (1) we present past parallel algorithms for routing any one-to-one assignment over Beneš network, we propose new multicasting networks that can efficiently realize any one-to-many assignments, and we give an explicit construction of linear-size expanders with very large expansion coefficients. Our parallel routing algorithms for Beneš networks are realized on two different topologies. Using these algorisms, we show that any unicast assignment that involves )(k) pairs of inputs and outputs can be routed through and n-input Beneš network in O(log2 k+lg n) time without pipelining and O(lg k) time with pipelining if the topology is complete, and in O(lg4k+lg2k lg n) time without pipelining and O(lg3 k+lg k lg n) time with pipelining if the topology is extended perfect shuffle. These improve the best-known routing time complexities of parallel algorithms of Lev et al. and Nassimi and Sahni by a factor of O(lg n). Our multicasting networks uses a very simple self-routing scheme which requires no separate computer model for routing. Including the routing cost, it can be constructed with O(n lg2 n) bit-level constant fanin logic gates, O(lg2 n) bit-level depth, and can realize any multicast assignment in O(lg3 n) bit-level time. These complexities match or are better than those of multicasting networks with the same cost that were reported in the literature. In addition to its attractive routing scheme, our multicasting network is input-initiated and can pipeline multicast assignments through itself. With pipelining, the average routing time for O(lg2 n) multicast assignments can be reduced to O(lg n) which is the best among those of the multicasting networks previously reported in the literature. Our linear-size expanders are explicitly constructed by following a traditional design and analysis technique. We construct a family of linear-size with density 33 and expansion coefficient 0.868. This expansion coefficient is the larges among the linear-size expanders that were similarly constructed. Using these expanders, we also report a family of explicitly constructed superconcentrators with density 208.