In this paper, we describe an 
-node nonblocking network
for which each connection can be made on-line in 
bit
steps. The path selection algorithm works even if many calls are made
at once -- every call still gets through in 
bit steps, no
matter what calls were made previously and no matter what calls are
currently active, provided that no two inputs try to access the same
output at the same time. (If many inputs inadvertently try to access
the same output at the same time, all but one of the inputs will
receive a busy signal. The busy signals are also returned in 
bit steps, but, at present, we require the use of a sorting
circuit [2, 20] to generate the busy signals.
Alternatively, we could merge the calling parties together, but this
also requires the use of a sorting circuit.) In all scenarios, the
size of the network and the speed of the path selection algorithm are
asymptotically optimal.
In addition to providing the first optimal solution to the abstract
telephone switching problem, our results significantly improve upon
previously known algorithms for bit-serial packet routing.
Previously, 
-bit-step algorithms for packet routing were
known only for the special case in which all packet paths are created
or destroyed at the same time, and even then only by resorting to the
AKS sorting circuit [2], or by using randomness on the
hypercube [1]. In many circuit-switched parallel
machines, however, packets are of varying lengths and packet paths are
created and destroyed at arbitrary times, thereby requiring that paths
be routed in a nonblocking fashion - which is something that
previously discovered algorithms were not capable of doing. Even
without worrying about the nonblocking property, our results provide
the first non-AKS 
-bit-step algorithms for bit-serial
packet routing on a bounded-degree network. (Since this work first
appeared, Leighton and Plaxton have developed an 
-bit-step
randomized sorting algorithm for the butterfly
[20].)