An Algorithm for Incrementally Controlling Benes Networks

Publication Year:
Usage 17
Downloads 17
Repository URL:
Pitt D-Scholarship Id:
Richard A Thompson
School of Library and Information Science, University of Pittsburgh
report description
A two-part algorithm selects optimal paths through a rearrangeably nonblocking Benes network. In a complex one-time computation, the first part of the algorithm constructs a finite-state machine data base in which each state represents an equivalence class of network configurations. In a brief real-time computation, the second part of the algorithm accepts a call request, consults this base, and determines the optimal path by which to complete the call. Path optimality is based on reducing the chance that existing connections will need to be rearranged to allow new connections.