Rapid optimal scheduling for Time-Multiplex Switches using a cellular automaton.

In a Time-Multiplex switching system, the incoming traffic must be scheduled to avoid conflict at the switch output (two or more users converging simultaneously upon a single output). Optimal scheduling, as its name implies, provides a means to assign traffic on demand such that either blocking probability is minimized (unbuffered system) or packet waiting time is minimized (buffered system). However, computation of an optimal schedule for switches of a reasonable size (i.e.,N=100) may require many seconds or even minutes, whereas the traffic demand may vary much more rapidly. Furthermore, the computation time varies as N sup 2. In order to over come this computational bottleneck, an optimal scheduling algorithm is developed herein which can be readily implemented on a simple special-purpose parallel computer (cellular automation). Increases in computation speed by several orders of magnitude should be possible with a VLSI implementation of this scheduling machine; the time to compute a schedule for a 1000 input switch would be measured in milliseconds rather than minutes. With such a scheduler, assignment-on-demand scheduling of large switches may become possible.