An Algorithm for Incrementally Controlling Benes Networks

Publication Year:
1991
Usage 19
Downloads 19
Repository URL:
http://d-scholarship.pitt.edu/id/eprint/18246
Pitt D-Scholarship Id:
18246
Author(s):
Richard A Thompson
Publisher(s):
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.