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) cells is n lo g2n + 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. Copyright © 1979 by The Institute of Electrical and Electronics Engineers, Inc.