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

CNS 核心：小型：超低复杂度交换算法，实现可扩展的高网络性能

• 批准号: 1909048
• 负责人: Jun Xu
• 金额: $ 43.27万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2022-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1909048&HistoricalAwards=false
• 关键词: CNS; Core; Small; Ultra; Low

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.

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

项目成果

LESS: A Matrix Split and Balance Algorithm for Parallel Circuit (Optical) or Hybrid Data Center Switching and More

LESS：用于并行电路（光纤）或混合数据中心交换等的矩阵拆分和平衡算法

• DOI: 10.1145/3344341.3368807
• 发表时间: 2019-12
• 期刊: New Zealand
• 作者: Liu, Liang;Xu, Jun;Singh, Mohit
• 通讯作者: Singh, Mohit

Sliding-Window QPS (SW-QPS): A Perfect Parallel Iterative Switching Algorithm for Input-Queued Switches

滑动窗口 QPS (SW-QPS)：一种用于输入队列交换机的完美并行迭代切换算法

• DOI: 10.1145/3453953.3453969
• 发表时间: 2021-03
• 期刊: ACM SIGMETRICS Performance Evaluation Review
• 作者: Meng, Jingfan;Gong, Long;Xu, Jun
• 通讯作者: Xu, Jun

ONe Index for All Kernels (ONIAK): A Zero Re-Indexing LSH Solution to ANNS-ALT (After Linear Transformation)

ONe Index for All Kernels (ONIAK)：ANNS-ALT 的零重新索引 LSH 解决方案（线性变换后）

• 发表时间: 2022-10
• 期刊: Proceedings of the VLDB Endowment
• 影响因子: 2.5
• 作者: Jingfan Meng; Huayi Wang
• 通讯作者: Huayi Wang

QPS-r: A Cost-Effective Iterative Switching Algorithm for Input-Queued Switches

QPS-r：一种用于输入队列交换机的经济高效的迭代切换算法

• DOI: 10.1145/3388831.3388836
• 发表时间: 2020-05
• 期刊: Proc. of Valuetools 2020
• 作者: Gong, Long;Xu, Jun Jim;Liu, Liang;Maguluri, Siva Theja
• 通讯作者: Maguluri, Siva Theja

iDEC: indexable distance estimating codes for approximate nearest neighbor search

iDEC：用于近似最近邻搜索的可索引距离估计代码

• DOI: 10.14778/3397230.3397243
• 发表时间: 2020-05
• 期刊: Proceedings of the VLDB Endowment
• 影响因子: 2.5
• 作者: Gong, Long;Wang, Huayi;Ogihara, Mitsunori;Xu, Jun
• 通讯作者: Xu, Jun