
Juggling Networks
Nicholas Pippenger*
email: [email protected]
Department of Computer Science
The University of British Columbia
Vancouver, British Columbia V6T 1Z4
CANADA
Abstract: Switching networks of various kinds have come to occupy a prominent position in computer science as well as communication engineering. The classical switching network technology has been spacedivisionmultiplex switching, in which each switching function is performed by a spatially separate switching component (such as a crossbar switch). A recent trend in switching network technology has been the advent of timedivisionmultiplex switching, wherein a single switching component performs the function of many switches at successive moments of time according to a periodic schedule. This technology has the advantage that nearly all of the cost of the network is in inertial memory (such as delay lines), with the cost of switching elements growing much more slowly as a function of the capacity of the network.
In order for a classical spacedivisionmultiplex network to be adaptable to timedivisionmultiplex technology, its interconnection pattern must satisfy stringent requirements. For example, networks based on randomized interconnections (an important tool in determining the asymptotic complexity of optimal networks) are not suitable for timedivisionmultiplex implementation. Indeed, timedivisionmultiplex implementations have been presented for only a few of the simplest classical spacedivisionmultiplex constructions, such as rearrangeable connection networks.
This paper shows how interconnection patterns based on explicit constructions for expanding graphs can be implemented in timedivisionmultiplex networks. This provides timedivisionmultiplex implementations for switching networks that are within constant factors of optimal in memory cost, and that have asymptotically more slowly growing switching costs. These constructions are based on a metaphor involving teams of jugglers whose throwing, catching and passing patterns result in intricate permutations of the balls. This metaphor affords a convenient visualization of timedivisionmultiplex activities that should be of value in devising networks for a variety of switching tasks.
* This research was partially supported by an NSERC Operating Grant.