- View PDF version of TR-93-34 (142744 bytes)
- View PostScript version of TR-93-34
- Save PostScript version of TR-93-34
- Save gzipped PostScript version of TR-93-34 (44622 bytes)

- Self-Routing Superconcentrators, October 1993 Nicholas Pippenger, 17 pages
Superconcentrators are switching systems that solve the generic problem of interconnecting clients and servers during sessions, in situations where either the clients or the servers are interchangable (so that it does not matter which client is connected to which server). Previous constructions of superconcentrators have required an external agent to find the interconnections appropriate in each instance. We remedy this shortcoming by constructing superconcentrators that are ``self-routing'', in the sense that they compute for themselves the required interconnections.

Specifically, we show how to construct, for each n, a system S_n with the following properties. (1) The system S_n has n inputs, n outputs, and O(n) components, each of which is of one of a fixed finite number of finite automata, and is connected to a fixed finite number of other components through cables, each of which carries signals from a fixed finite alphabet. (2) When some of the inputs, and an equal number of outputs, are ``marked'' (by the presentation of a certain signal), then after O(log n) steps (a time proportional to the ``diameter'' of the network) the system will establish a set of disjoint paths from the marked inputs to the marked outputs.

If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.