NEURAL NETWORK DESIGN OF A BANYAN NETWORK CONTROLLER

Packet switching networks require queueing due to output blocking that is unavoidable. If internal blocking is also present, such as with the Banyan switching network, then longer queues can be expected. The algorithm for choosing nonblocking sets of data cells from the queues can significantly affect the throughput and queueing behavior. We present an algorithm that we show to have maximum throughput. Using a novel equivalence class approach, we reduce this algorithm on a Banyan network to a constraint satisfaction problem. To gain the required computational speed, we use the massive parallelism of neural networks. A neural network design is defined using multiple overlapping winner-take-all circuits. This is shown to be stable and only result in nonblocking sets of data cells. An efficient interface between the neural network and the queue is also defined. The performance of the Banyan with a neural network controller is compared to a noninternal-blocking switch with various controllers. Surprisingly, the Banyan is within a factor of two of the nonblocking switch. © 1990 IEEE