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

在云计算增长的推动下，数据中心网络（DCN）在规模和速度上都在不断增长。 一种高成本效益的方法来解决这个可扩展性问题，称为混合DCN架构，近年来受到了相当大的研究关注。 混合DCN采用两种技术来互连数据中心中的计算机机架：一种更快且更便宜的电路交换机，其可重新配置，具有一定的性能成本，以及传统的分组交换机。混合交换的研究问题是对电路交换进行近似最优的调度，使其从分组交换中去除尽可能多的业务。 以前的工作混合开关解决了这个优化问题的基础上，一个方便的假设，电路开关不是部分可重构的。 然而，这是一个过时的和不必要的限制性假设，因为作为当今电路交换机基础的电子和光学技术可以在以下意义上容易地支持部分重新配置：只有受重新配置影响的输入端口需要支付重新配置延迟，而未受影响的输入端口可以在重新配置期间继续传输数据。 允许部分重新配置可以显著增加吞吐量并减少系统延迟，从而显著改善数据中心的操作。 然而，它也导致了一系列具有挑战性的研究问题，将在这个项目中解决。 该项目将通过跨多个学科的综合课堂课程和研究培训吸引学生，并包括对代表性不足的少数群体的外联工作。 PI将与领先的网络和系统供应商密切合作，以促进技术转让。在部分重构的假设下，混合交换系统中电路交换机的非抢占调度问题可以建模为一个开放车间调度问题（OSSP），简称为交换OSSP。 开关OSSP开辟了一个新的研究方向，许多算法结果（逼近比，NP-困难等）都是开放问题。一般的OSSP不再适用。 本计画将探讨以下五个交换式OSSP的研究课题。 首先，它将研究BFF（最佳拟合优先）在各种流量负载下的近似比，并设计确定性或随机算法，可以以高概率，避免或减轻最坏的情况。 第二，该项目将调查当DCN通过由互连的无缓冲电路交换机网络组成的巨大虚拟交换机互连时所出现的研究挑战。 第三，它将研究部分可重构的混合和光交换时，每个机架有多个发射机/接收机，这似乎是一个新的和具有挑战性的问题，从根本上不同于文献中发现的任何东西。 第四，对于拥有100个或更多机架的数据中心，BFF仍然需要数十毫秒的计算时间，这比云提供商所期望的理想延迟水平（不超过几毫秒）大约长一个数量级。研究人员将研究如何显着减少BFF的计算时间，以便在将来DCN规模变得更大时保持足够快。 最后，他们将研究如何适应“最后一分钟”的交通到达在当前批次的传输（对应于到达在前一个调度时期），如果成功的话，可以进一步提高他们的解决方案的延迟性能。这个奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

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.