An Algorithm for Incrementally Controlling Benes Networks

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