High performance concentrators and superconcentrators using multiplexing schemes
- 1 January 1994
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Communications
- Vol. 42 (11) , 3045-3050
- https://doi.org/10.1109/26.328986
Abstract
Concentrators are used to interface and combine together low speed communication channels onto higher speed transmission links to alleviate transmission costs. They are also used to construct more powerful switching fabrics such as permutation and broadcast networks. Using an adaptive binary sorting network model, this paper constructs new concentrators and superconcentrators. Unlike the previously reported concentrators and superconcentrators, these new constructions are fast, and can easily be implemented using simple switching devices. More specifically, for n inputs, they can be constructed with O(n lg lg n) constant fanin bit-level multiplexers and demultiplexers, and can be routed in O(lg(2) n) bit-level time.This publication has 17 references indexed in Scilit:
- Adaptive binary sorting schemes and associated interconnection networksIEEE Transactions on Parallel and Distributed Systems, 1994
- A self-routing permutation networkJournal of Parallel and Distributed Computing, 1990
- A new broadcast switching networkIEEE Transactions on Communications, 1988
- Eigenvalues and expandersCombinatorica, 1986
- Control Algorithms for Rearrangeable Clos NetworksIEEE Transactions on Communications, 1983
- Telephone switching networksProceedings of Symposia in Applied Mathematics, 1982
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- On Concentrators, Superconcentrators, Generalizers, and Nonblocking NetworksBell System Technical Journal, 1979
- SuperconcentratorsSIAM Journal on Computing, 1977
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite GraphsSIAM Journal on Computing, 1973