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.

由于现有和新兴的数据密集型应用程序，整个Internet和数据中心的网络流量量继续不断增长。 为了运输和“直接”到各自目的地的大量流量，网络交换机能够连接大量输入输出端口（这些交换机称为高radix）并在非常高速的情况下运行。 一个开关必须在每个时间插槽中计算（例如持续时间10纳秒），该匹配指定通过输入端口和输出端口之间的开关指定同时连接的集合，每个连接允许在相应的端口对之间传输数据包，并朝向其目的地。 设计快速高音开关的主要挑战是开发算法，即使开关大小（radix）n很大，可以在时间插槽的时间内计算高质量匹配。 但是，现有的匹配（开关）算法在计算上不可效率不足，对于将来的快速高音开关而言。 该项目将通过调查下一代匹配算法来弥合这一差距，这些算法的运行速度更快却具有出色的吞吐量和延迟性能。 该项目还将开发出新的数学技术，这些技术对于分析此类算法的吞吐量保证所需的必要条件。该项目将在主要研究人员及其学生的最新研究基础上进行并扩展三个最新的研究突破。 第一个突破是一种称为Queue-Portortional采样（QP）的附加算法，可用于提高现有匹配算法的性能，例如Serena和Islip，几乎没有其他计算成本。 第二个突破是QPS-R，这是一种分布式匹配算法，该算法运行QPS的常数R弹性（迭代）以计算匹配。 在仅一次迭代（即，当r = 1时）中，QPS-1输出的匹配通常不是最大的，但具有与最大匹配的质量完全相同，该匹配的计算要昂贵得多。第三个突破是小夜曲，有效地使Serena并行，并且每个端口的计算复杂性低。 该项目将开发出小批量QP（SB-QP），这是一种批量匹配算法，该算法构建在QPS和QPS-R上，并且似乎具有下一代匹配算法的所有所需属性。 该项目还将在Lyapunov稳定理论的框架内开发新的数学技术，以确定和证明几种现有或下一代匹配算法的吞吐量保证，例如QPS-ISLIP，QPS-RISSIP，QPS-R，SB-QPS和O-Serenade。 作为该项目的重要教育组成部分，PI正在撰写第二版教科书，内容涉及一个包含该算法的设计和分析，例如该算法。 PI将与领先的网络解决方案提供商（例如Cisco）紧密合作，以促进技术的转移。 PI将进一步扩大代表性不足的群体（例如妇女和少数群体）在研究和高等教育中的参与。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子和更广泛影响的评估评估标准来通过评估来支持的。

项目成果

Space- and Computationally-Efficient Set Reconciliation via Parity Bitmap Sketch (PBS)

• DOI: 10.14778/3436905.3436906
• 发表时间: 2020-07
• 期刊: ArXiv
• 作者: Long Gong;Ziheng Liu;Liang Liu;Jun Xu;Mitsunori Ogihara;Tong Yang

Jump-Starting Multivariate Time Series Anomaly Detection for Online Service Systems

• 发表时间: 2021
• 作者: Minghua Ma;Shenglin Zhang;Junjie Chen;Jim Xu;Haozhe Li;Yongliang Lin;Xiaohui Nie;Bo Zhou;Yong Wang;Dan Pei

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
• 期刊: New Zealand
• 作者: Liu, Liang;Xu, Jun;Singh, Mohit
• 通讯作者: Singh, Mohit

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
• 期刊: Proceedings of the VLDB Endowment
• 影响因子: 2.5
• 作者: Jingfan Meng, Huayi Wang

SERENADE: A Parallel Iterative Algorithm for Crossbar Scheduling in Input-Queued Switches

SERENADE：输入队列交换机中交叉开关调度的并行迭代算法

• DOI: 10.1109/hpsr48589.2020.9098995
• 发表时间: 2020
• 期刊: 2020 IEEE 21st International Conference on High Performance Switching and Routing (HPSR
• 作者: Gong, Long;Liu, Liang;Yang, Sen;Xu, Jun Jim;Xie, Yi;Wang, Xinbing
• 通讯作者: Wang, Xinbing