Least Common Ancestor Networks

Least Common Ancestor Networks (LCANs) are introduced and shown to be a class of networks that include fattrees, baseline networks, SW-banyans and the router networks of the TRAC 1.1 and 2.0 and the CM-5. Some LCAN properties are stated and the circuit-switched permutation routing capabilities of an important subclass are analyzed. Simulation results for three permutation classes verify the accuracy of an iterative analysis for a randomized routing strategy. These results indicate that the routing strategy provides highly predictable router performance for all permutations. An off-line routing algorithm is also given, and it is shown how to realize certain classes of permutations by adapting Nassimi and Sahni′s, and Raghavendra and Boppana′s self-routing algorithms for Benes networks.