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

由于现有和新兴的数据密集型应用程序，互联网和数据中心的网络流量持续无情地增长。 为了将这种大量的流量传输和“引导”到其各自的目的地，迫切需要能够连接大量输入输出端口（这些交换机被称为高基数）并且以非常高的速度操作的网络交换机。 交换机必须为每个时隙（比如持续时间为10纳秒）计算一个匹配，该匹配指定了通过交换机在输入端口和输出端口之间的一组同时连接，每个连接都允许在相应的端口对之间传输分组，并从交换机向外传输到其目的地。 在设计快速高基数开关的一个主要挑战是开发算法，可以计算高质量的匹配的持续时间内的时隙，即使当开关的大小（基数）N是大的。 然而，现有的匹配（交换）算法计算效率不高，也不足以扩展为未来的快速高基数开关。 本项目将通过研究下一代匹配算法来弥补这一差距，这些算法运行速度更快，但具有出色的吞吐量和延迟性能。 该项目还将开发分析此类算法的吞吐量保证所需的新数学技术。该项目将建立并扩展首席研究员及其学生最近取得的三项研究突破。 第一个突破是一种名为“按比例采样”（QPS）的附加算法，该算法可用于提高现有匹配算法（如SERENA和iSLIP）的性能，而几乎不需要额外的计算成本。 第二个突破是QPS-r，这是一种分布式匹配算法，它运行QPS的常数r轮（迭代）来计算匹配。 只需一次迭代（即，当r = 1时），QPS-1输出通常甚至不是最大的匹配，但具有与最大匹配完全相同的质量，最大匹配的计算成本要高得多。第三个突破是SERENADE，它有效地并行化了SERENA，每个端口的计算复杂度为O（log N）。 该项目将开发小批量QPS（SB-QPS），这是一种基于QPS和QPS-r的批量匹配算法，似乎具有下一代匹配算法的所有所需属性。 该项目还将在李雅普诺夫稳定性理论的框架内开发新的数学技术，用于确定和证明几种现有或下一代匹配算法（如QPS-iSLIP，QPS-r，SB-QPS和O-SERENADE）的吞吐量保证。 作为该项目的一个重要的教育组成部分，PI正在编写一本关于一个主题的教科书的第二版，该主题包含作为子主题的此类算法的设计和分析。 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.