CNS Core: Small: Ultra-Low-Complexity Switching Algorithms for Scalable High Network Performance

由于现有和新兴的数据密集型应用程序，整个互联网和数据中心的网络流量持续不断地增长。为了将这些海量的流量传输并“引导”到其各自的目的地，迫切需要能够连接大量输入输出端口(这些交换机称为高基)并以非常高的速度运行的网络交换机。交换机必须为每个时隙(比方说持续时间为10纳秒)计算一个匹配，该匹配指定在输入端口和输出端口之间通过交换机的一组同时连接，每个连接允许在对应的端口对之间和从交换机向其目的地传输分组。设计快速高基开关的主要挑战是开发能够在时隙持续时间内计算高质量匹配的算法，即使在开关大小(基数)N很大的情况下也是如此。然而，现有的匹配(交换)算法在计算效率和可伸缩性方面都不足以满足未来快速高基交换机的要求。该项目将通过研究下一代匹配算法来弥补这一差距，这些算法运行得更快，但具有出色的吞吐量和延迟性能。这个项目还将开发分析这种算法的吞吐量保证所必需的新的数学技术。这个项目将建立在主要研究人员和他的学生最近取得的三项研究突破的基础上并加以扩展。第一个突破是一种名为队列比例采样(QPS)的附加算法，该算法可以用来提高现有匹配算法的性能，例如Serena和Islip，而几乎不需要额外的计算成本。第二个突破是QPS-r，这是一种分布式匹配算法，它运行固定r轮(迭代)的QPS来计算匹配。仅在单个迭代中(即，当r=1时)，QPS-1输出的匹配通常甚至不是最大的，但具有与最大匹配完全相同的质量，后者的计算成本要高得多。第三个突破是小夜曲，它有效地并行化了Serena，并且具有每个端口O(LogN)的低计算复杂度。这个项目将开发小批量QPS(SB-QPS)，这是一种建立在QPS和QPS-r基础上的批量匹配算法，似乎具有下一代匹配算法的所有期望特性。该项目还将在Lyapunov稳定性理论的框架内开发新的数学技术，用于确定和证明几种现有或下一代匹配算法的吞吐量保证，如QPS-ISLIP、QPS-r、SB-QPS和O-小夜曲。作为这个项目的一个重要的教育组成部分，PI正在编写第二版教科书，其主题包含了此类算法的设计和分析作为一个子主题。PI将与思科等领先的网络解决方案提供商密切合作，促进技术转让。该奖项反映了NSF的法定使命，通过使用基金会的学术价值和更广泛的影响审查标准进行评估，被认为是值得支持的。

The volumes of network traffic across the Internet and in data-centers continue to grow relentlessly, thanks to existing and emerging data-intensive applications. To transport and "direct" this massive amount of traffic to its respective destinations, network switches capable of connecting a large number of input-output ports (these switches are called high-radix) and operating at very high speeds are badly needed. A switch has to compute, for each time slot (say 10 nanoseconds in duration), a matching that specifies the set of simultaneous connections through the switch between the input ports and the output ports, each of which allows for the transmission of a packet between the corresponding port pair and out the switch toward its destination. A major challenge in designing fast high-radix switches is to develop algorithms that can compute high-quality matchings within the duration of a time slot, even when the switch size (radix) N is large. However, existing matching (switching) algorithms are not computationally efficient nor scalable enough for future fast high-radix switches. This project will bridge this gap via investigating next-generation matching algorithms that run much faster yet have excellent throughput and delay performances. This project will also develop new mathematical techniques that are necessary for analyzing the throughput guarantees of such algorithms.This project will build on and extend three recent research breakthroughs made by the principal investigator and his students. The first breakthrough is an add-on algorithm called Queue-Proportional Sampling (QPS) that can be used to boost the performance of existing matching algorithms, such as SERENA and iSLIP, at virtually no additional computation cost. The second breakthrough is QPS-r, a distributed matching algorithm that runs a constant r rounds (iterations) of QPS to compute a matching. In just a single iteration (i.e., when r = 1), QPS-1 outputs a matching that is in general not even maximal, yet has exactly the same quality as maximal matchings, which are much more expensive to compute. The third breakthrough is SERENADE, which effectively parallelizes SERENA and has a low computational complexity of O(log N) per port. This project will develop among others Small Batch QPS (SB-QPS), a batch matching algorithm that builds on QPS and QPS-r and appears to have all the desired properties of next-generation matching algorithms. This project will also develop new mathematical techniques, within the framework of Lyapunov stability theory, for determining and proving the throughput guarantees of several existing or next-generation matching algorithms such as QPS-iSLIP, QPS-r, SB-QPS, and O-SERENADE. As an important educational component of this project, the PI is writing the second edition of a textbook on a topic that contains the design and analysis of such algorithms as a subtopic. The PI will work closely with leading networking solution providers, such as Cisco, to facilitate the transfer of technology. The PI will further broaden the participation of under-represented groups, such as women and minority, in research and higher education.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.