Donald Bren School of Information and Computer Sciences

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.