Constructions of given-depth and optimal multirate rearrangeably nonblocking distributors

摘要

Rearrangeable multirate multicast switching networks are customarily called rearrangeable multirate distributors. It has been known for a long time that rearrangeable multirate distributors with cross-point complexity O(nlog2 n) can be constructed, where n is the number of inputs (and outputs) of the switching network. The problem of constructing optimal distributors remains open thus far. This paper gives a general construction of rearrangeable multirate distributors with given depths. One byproduct is a rearrangeable multirate distributor with crosspoint complexity O(nlog n). We also show that this cross-point complexity is optimal, settling the aforementioned open problem. One of the key ingredients of our new construction is the notion of multirate concentrators. The second ingredient is a multirate version of the Pippenger network.We show how to construct given-depth multirate concentrators and given-depth multirate Pippenger networks with small sizes. When the depth is chosen to optimize the size, we obtain the optimal O(nlog n) cross-point complexity.