Least Common Ancestor Networks (LCANs) comprise levels of switches that enable communication in two directions. LCANs are a generalization of previously developed networks including fat-trees, baseline networks, SW-banyans and the router networks of the TRAC and the CM-5. In this paper, LCANs are characterized and the routing capabilities of important subclasses are analyzed.

Multistage interconnection networks (MIN's) allow communication between terminals on opposing sides of a network. Lowest Common Ancestor Networks (LCAN's) [1] have switches capable of connecting bi-directional links in a permutation pattern that additionally permits communication between terminals on the same side. Self-routing LCAN's have interesting permutation routing capabilities and are highly partionable. This paper characterizes self-routing LCAN's and analyzes their permutation routing capabilities. It is shown that the routing network of the CM-5 is a particular instance of an LCAN.

Lowest Common Ancestor (LCA) networks are built using switches capable of connecting u + d inputs/outputs in a permutation pattern. For n source nodes and I stages of switches, n/d switches are used in stage l - n/d - u/d in stage l - 2, and in general , n-u^l-i-l/d^l-i switches in stage i. The resulting hierarchical structure possesses interesting connectivity and permutational properties. A full characterization of LCA networks is presented together with a permutation routing algorithm for a family of LCA networks. The algorithm uses the network itself to collect and disseminate information about the permutation. A schedule of O(dp log_d/u n) passes is obtained with a switch set-up cost factor of O(log_d/u n) (p is the minimum number of passes that an algorithm with global knowledge schedules).