A Parallel Algorithm and Scalable Architecture for Routing in Beneš Networks

Beneš/CLOS architectures are common scalable interconnection networks widely used in backbone routers, data centers, on-chip networks, multi-processor systems, and parallel computers. Recent advances in Silicon Photonic technology, especially MZI technology, have made Beneš networks a very attractive scalable architecture for optical circuit switches.Numerous routing algorithms for Beneš networks were developed starting with linear algorithms having time complexity of O(N log2N) steps. Parallel routing algorithms were developed to satisfy the stringent timing requirements of high-performance switching networks and have time complexity of O((log2N)2).However, their implementation requires O(N2log2N) wires (termed connectivity complexity), and thus are difficult to scale.We present a new routing algorithm for Beneš networks combined with a scalable hardware architecture that supports full and partial input permutations. The processing time of the algorithm is limited to O((log2N)2) steps (iterations) by potentially forfeiting routing of a few input demands; however achieves close to 100% utilization for both full and partial input permutations. The algorithm and architecture allow a reduction of the connectivity complexity to O(N2), a logN improvement over previous solutions.We prove the algorithm correctness, and analyze its performance analytically and with large scale simulations.