EE Seminar :Routing Algorithms in Benes and CLOS Networks

Electrical Engineering Systems Seminar

Speaker: Rami Zecharia

Ph.D. student under the supervision of Prof. Yuval Shavitt

Wednesday, 14^th August 2024, at 15:00

Room 011, Kitot Building, Faculty of Engineering

Routing Algorithms in Benes and CLOS Networks

Abstract

Benes/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 in Mach–Zehnder Interferometer (MZI) technology which is the building block for low-cost high-speed 2x2 optical switch, have made Benes networks a very attractive scalable architecture for optical circuit switches.
Numerous routing algorithms for Benes networks were developed starting with sequential routing algorithms with time complexity of O(Nlog₂N) steps and, in some cases, requires backtracking, which makes them even less efficient. Parallel routing algorithms were developed to satisfy the stringent timing requirements of high-performance switching networks and have time complexity of O((log₂N)²). However, their implementation requires O(N²log₂N) wires (termed connectivity complexity), and thus are difficult to scale. Online (Adaptive) routing algorithms do not utilize the re-arrangeable characteristics of a network as they establish a single path at a time without interrupting already established paths. Such online algorithms yield poor utilization, resulting in low throughput and high latency which impedes their usage.

In this thesis, we present three new and improved routing algorithms for Benes network:

• A parallel routing algorithm combined with a unique scalable hardware architecture that supports full and partial input permutations. The algorithm achieves close to 100% utilization for both full and partial input permutations. Time complexity is limited to O((log₂N)²) steps to match the performance of parallel algorithms. The algorithm and architecture allow a reduction of the connectivity complexity to O(N²), a log₂N improvement over previous solutions.
• An engineering approach to the already known sequential routing algorithm along with a unique scalable hardware architecture. The new algorithm supports full and partial input permutations with a significantly lower time complexity of O(N^3/5) and connectivity complexity of O(N²) and achieves 100% complete routing of a given full or partial input permutation with probability of 99.9999%. The achieved time complexity is comparable to parallel algorithms.
• An online (adaptive) routing algorithm achieving significant increase of utilization (number of established paths for a given input permutation) compared to prior work hence increased throughput and reduce latency while operating within the same time complexity as prior works, hence enabling the usage of Benes network based optical switches for a wide range of applications. We further applied this algorithm to CLOS network achieving even higher average utilization as compared to a single Benes network-based switch of the same size. Hence, enabling the usage of large-scale CLOS-based optical networks for various applications.

השתתפות בסמינר תיתן קרדיט שמיעה = עפ"י רישום שם מלא + מספר ת.ז. בדף הנוכחות שיועבר באולם במהלך הסמינר