Constructions of given-depth and optimal multirate rearrangeably nonblocking distributors

Yang Wang (), Hung Q. Ngo () and Thanh-Nhan Nguyen ()
Additional contact information
Yang Wang: State University of New York at Buffalo
Hung Q. Ngo: State University of New York at Buffalo
Thanh-Nhan Nguyen: State University of New York at Buffalo

Journal of Combinatorial Optimization, 2012, vol. 24, issue 4, No 6, 468-484

Abstract: Abstract 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(nlog 2 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.

Keywords: Multirate distributor; Multirate concentrator; Multirate super-concentrator; Switching networks (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-011-9402-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:24:y:2012:i:4:d:10.1007_s10878-011-9402-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-011-9402-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().