CNS Core: Small: Towards Hybrid Data Center Switching Using Partially Reconfigurable Circuit Switch

CNS 核心：小型：使用部分可重构电路交换机实现混合数据中心交换

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

Fueled by the growth of cloud computing, data center networks (DCN) continue to grow relentlessly in both size and speed. A highly cost-effective approach to this scalability problem, called hybrid DCN architecture, has received considerable research attention in recent years. A hybrid DCN employs two technologies to interconnect racks of computers in data center: a much faster and less expensive circuit switch that is reconfigurable with some performance cost, and a traditional packet switch. The research problem of hybrid switching is to near-optimally schedule the circuit switch, so that it removes as much traffic as possible from the packet switch. Previous work on hybrid switching solves this optimization problem based on a convenient assumption that the circuit switch is not partially reconfigurable. This is however an outdated and unnecessarily restrictive assumption because electronic and optical technologies underlying today's circuit switches can readily support partial reconfiguration in the following sense: Only the input ports affected by the reconfiguration need to pay a reconfiguration delay, while unaffected input ports can continue to transmit data during the reconfiguration. Allowing partial reconfiguration can significantly increase the throughput and reduce system delay, thus significantly improving data center operation. However, it also leads to a host of challenging research questions that will be tackled in this project. This project will engage students through integrated classroom curriculum and research training that span multiple disciplines, and includes outreach efforts to underrepresented minorities. The PI will work closely with leading networking and systems providers to facilitate technology transfer. Under the assumption of partial reconfiguration, the non-preemptive scheduling of the circuit switch in a hybrid switching system can be modeled as an Open Shop Scheduling Problem (OSSP), referred to as switching OSSP. Switching OSSP has opened up a new research direction teeming with open problems, because many algorithmic results (approximation ratio, NP-hardness, etc.) on general OSSP no longer apply. This project will investigate the following five research tasks on switching OSSP. First, it will study the approximation ratios of BFF (Best Fit First) under various traffic workloads, and design deterministic or randomized algorithms that can, with high probability, avoid or mitigate the worst-case scenarios. Second, the project will investigate research challenges that arise when a DCN is interconnected by a giant virtual switch comprised of a network of interconnected bufferless circuit switches. Third, it will study partially reconfigurable hybrid and optical switching when each rack has multiple transmitters/receivers, which appears to be a new and challenging problem that is fundamentally different than anything found in the literature. Fourth, for a data center with 100 or more racks, BFF still takes tens of milliseconds to compute, which is roughly an order of magnitude longer than the ideal level of latency (no more than a few milliseconds) desired by cloud providers. The reseearchers will study how to significantly reduce the computation time of BFF so that it remains fast enough when the DCN size becomes much larger in the future. Last, they will investigate how to accommodate ``last-minute" traffic arrivals during the transmission of the current batch (corresponding to arrivals during a previous scheduling epoch), which if successful, can further improve the delay performance of their solutions.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.

随着云计算的增长，数据中心网络（DCN）的尺寸和速度都不断增长。 近年来，一种称为混合DCN体系结构的可扩展性问题的高度成本有效的方法，称为混合DCN体系结构。 混合动力DCN使用两种技术来互连计算机中的计算机：一个更快，更便宜的电路开关，可以通过某些性能成本重新配置，以及传统的数据包开关。混合开关的研究问题是近距离安排电路开关，以便从数据包开关中消除尽可能多的流量。 基于方便的假设，即电路开关无法部分重新配置，因此在混合开关上的先前工作解决了此优化问题。 但是，这是一个过时且不必要的限制性假设，因为当今电路开关的电子和光学技术可以从下面的意义上轻易地支持部分重新配置：只有由重新配置影响的输入端口才需要支付重新配置延迟，而未置于重新配置的输入输入部分则可以继续传输重新配置的数据。 允许部分重新配置可以显着增加吞吐量并减少系统延迟，从而显着改善数据中心的操作。 但是，这也导致了许多具有挑战性的研究问题，这些问题将在该项目中解决。 该项目将通过综合的课堂课程和研究培训来吸引学生，这些课程涵盖了多个学科，并包括对代表性不足的少数群体的宣传工作。 PI将与领先的网络和系统提供商紧密合作，以促进技术传输。在局部重新配置的假设下，混合开关系统中电路开关的非首次调度可以建模为开放式商店调度问题（OSSP），称为Switching OSSP。 Switching OSSP已为开放问题打开了一个新的研究方向，因为许多算法结果（近似值率，NP硬度等）不再适用。 该项目将研究有关切换OSSP的以下五项研究任务。 首先，它将在各种交通工作负载下研究BFF（最佳拟合）的近似值，并设计确定性或随机算法，这些算法可以避免或减轻最坏情况。 其次，该项目将调查当DCN与由互连无卧电路交换机网络组成的巨型虚拟开关相互联系时出现的研究挑战。 第三，当每个机架都有多个发射机/接收器时，它将研究部分可重构的混合动力和光学切换，这似乎是一个与文献中发现的新问题，这似乎是一个新的且具有挑战性的问题。 第四，对于具有100架或更多架子的数据中心，BFF仍然需要数十毫秒来计算，这大约比云提供商所需的理想延迟水平（不超过几毫秒）长的数量级。重新搜索者将研究如何显着减少BFF的计算时间，以便在将来DCN大小变大时保持足够快。 最后，他们将调查如何在当前批次传输期间（对应于先前的时间表时期的到达）期间如何适应``最后一刻''的交通，如果成功的话，这可以进一步改善其解决方案的延迟性能。该奖项反映了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

QPS-r: A cost-effective iterative switching algorithm for input-queued switches

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

• DOI: 10.1016/j.peva.2021.102197
• 发表时间: 2021
• 期刊: Performance Evaluation
• 影响因子: 2.2
• 作者: Gong, Long;Xu, Jun;Liu, Liang;Maguluri, Siva Theja
• 通讯作者: Maguluri, Siva Theja

RECIPE: Rateless Erasure Codes Induced by Protocol-Based Encoding

RECIPE：基于协议的编码引发的无速率纠删码

• DOI: 10.1109/isit54713.2023.10206874
• 发表时间: 2023
• 期刊: IEEE International Symposium on Information Theory
• 作者: Meng, Jingfan;Liu, Ziheng;Wang, Yiwei;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
• 期刊: Proceedings of the VLDB Endowment
• 影响因子: 2.5
• 作者: Jingfan Meng, Huayi Wang