Asymptotically Optimal Interconnection Networks from Two-State Cells

Some special classes of interconnection networks for n terminals are considered, namely, partitioning networks and full switches. Constructions for them are presented. For the former, the resulting total count of (two-state) cels is n log2n + n − log2n − 1, and the maximum delay is 6 log2n − 4. For the latter, the cell count is (n/2)log2n − (n/2) and the maximum delay is 2 log2n − 1. By establishing appropriate lower bounds, we show that these networks are asymptotically optimal as far as cell count is concerned.