贝内什网络中路由的并行算法与可扩展架构

《IEEE Transactions on Networking》：A Parallel Algorithm and Scalable Architecture for Routing in Bene? Networks

Bene?网络作为可扩展互连架构，其光交换应用面临连接复杂度高的问题。本文提出融合全部分量和部分输入排列的新路由算法，通过硬件架构优化将处理时间降至O((log N)^2)步，同时将连接复杂度从O(N2 log N)降至O(N log N)，实现技术突破。

　　

摘要：

Bene?/CLOS架构是一种常见的可扩展互连网络，广泛应用于骨干路由器、数据中心、片上网络、多处理器系统和并行计算机中。近年来，硅光子技术的进步，尤其是在Mach-Zehnder干涉仪技术方面的发展，使得Bene?网络成为光电路交换机的一种非常有吸引力的可扩展架构。针对Bene?网络，已经开发出了多种路由算法，最初是从时间复杂度为O(NlogN)的线性算法开始的。为了满足高性能交换网络的严格时序要求，还开发了并行路由算法，其时间复杂度为O(NlogN^2)。然而，这些并行算法的实现需要大量的连线（称为连接复杂性），因此难以实现大规模扩展。我们提出了一种新的Bene?网络路由算法，并结合了一种支持全输入排列和部分输入排列的可扩展硬件架构。该算法的处理时间被限制在O(NlogN^2)的步骤内（通过可能放弃部分输入请求来实现），但在全输入排列和部分输入排列的情况下都能接近100%的利用率。与之前的解决方案相比，这种算法和架构将连接复杂性降低了O(NlogN)，提高了大约logN倍的效率。我们证明了该算法的正确性，并通过分析和大规模仿真对其性能进行了验证。

引言

交叉开关网络是最简单的并行交换机实现方式，但由于需要大量的交叉点，因此在N较大时成本较高[1]。Clos[2]提出了一种三层交叉开关网络结构，大幅降低了交换机的成本。事实上，CLOS拓扑结构已成为大规模路由器的标准配置[1]。