TI Self-Routing Superconcentrators 

LT TR-93-34 

AU Nicholas Pippenger 

MN October 

YR 1993 

PA 17 

OR UBC 

AB 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. .br Specifically, we show how to
construct, for each \fIn\fP, a system \fIS_n\fP with the
following properties.  (1) The system \fIS_n\fP has \fIn\fP
inputs, \fIn\fP outputs, and \fIO(n)\fP 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 aequal number of
outputs, are ``marked'' (by the presentation of a certain
signal), then after \fIO(log n)\fP 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. 

AV ftp ftp.cs.ubc.ca:ftplocaltechreports1993TR-93-34.ps