NeTS: Small: Low Latency Scheduling for Data Centers

NeTS：小型：数据中心的低延迟调度

• 批准号: 1523546
• 负责人: Devavrat Shah
• 金额: $ 50万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-10-01 至 2021-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1523546&HistoricalAwards=false
• 关键词: NeTS; Small; Low; Latency; Scheduling

A data center is the backbone of any modern computational infrastructure. Therefore, it is of utmost importance to operate data center at high resource utilization and low latency to build a high-performance computation system. The primary goal of this project is to develop such a data center.Historically, the data center architecture has been inspired by congestion control in the Internet, where decisions are made at the end-points in a distributed manner. This has led to robust, scalable architecture for data center, but suffers from high latency and low resource utilization. In contrast to the Internet congestion control, scheduling in a switch ? core of modern high-bandwidth Internet router ? fundamentally relies on the ability to exercise centralized control. Over the past two decades, much progress has been made in the context of switch scheduling resulting into algorithm with high resource utilization and extremely low latency. Therefore, by applying design principles from switch scheduling, there is a potential to achieve data center architecture that has high resource utilization and low latency. In summary, there is a massive opportunity for developing extremely low-latency, high-performance scheduling architecture for data center by deriving design principles from Internet routers rather than Internet congestion control. This is precisely the focal point of this project. There are two major challenges in achieving this goal. First, developing an implementable and high-performance solution for switch scheduling. The existing theoretically optimal solutions, recently developed by PI, are too complex to implement. Therefore, developing a simple implementation of such a solution is required. This project will achieve this goal by utilizing randomization (a la Markov Chain Monte Carlo) and mean-field approximations from spin glass theory in Statistical Physics. Second, transforming a scheduling algorithm for a switch to a scheduling algorithm for data center is challenging. This project shall develop an emulation framework that will allow for such a transformation in a seamless manner. This will be achieved by utilizing connections between flow-level scheduling with packet-level scheduling inspired by reversible queuing networks.Intellectual Merit: This project will advance the design and analysis of implementable scheduling algorithms for communication networks. Intellectually, this will advance theory of randomized approximation algorithm, approximation techniques from statistical physics and emulation approaches from queuing network. The successful outcome of this project will suggest that it is better to architect a data center using principles behind the design of classical telephone network and ATM network rather than that of Internet congestion control. Broader Impacts: The successful outcome of this project will pave way for the development of low latency and efficient data centers. This, in turn, will allow for developing computational infrastructures that were not feasible before. Given the central importance of high-performance computational infrastructure across disciplines, successful outcome of this project will have a broad impact. This work will be of interest to currently vibrant networking industry where start-ups and big organizations alike are trying to develop the next generation data center riding on the software defined networking philosophy. In a sense, this work will provide a path to achieve their end goal. The proposed research will be disseminated to the community via publications in journals, conferences and workshops. The research outcome is also likely to be integrated in the graduate networking course that PI regularly teaches at MIT.

数据中心是任何现代计算基础设施的支柱。因此，以高资源利用率和低延迟运行数据中心以构建高性能计算系统至关重要。该项目的主要目标是开发这样一个数据中心。从历史上看，数据中心架构受到互联网拥塞控制的启发，其中决策是在端点以分布式方式做出的。这为数据中心带来了稳健、可扩展的架构，但存在高延迟和低资源利用率的问题。与互联网拥塞控制相比，交换机中的调度 ?现代高带宽互联网路由器的核心？根本上依赖于集中控制的能力。在过去的二十年中，交换机调度方面取得了很大进展，从而产生了具有高资源利用率和极低延迟的算法。因此，通过应用交换机调度的设计原理，有可能实现具有高资源利用率和低延迟的数据中心架构。总之，通过从互联网路由器而不是互联网拥塞控制中导出设计原则，为数据中心开发极低延迟、高性能的调度架构有巨大的机会。这正是该项目的重点。实现这一目标面临两大挑战。首先，开发一个可实施的高性能交换机调度解决方案。 PI 最近开发的现有理论最优解决方案过于复杂，难以实施。因此，需要开发此类解决方案的简单实现。该项目将通过利用随机化（马尔可夫链蒙特卡罗）和统计物理学中自旋玻璃理论的平均场近似来实现这一目标。其次，将交换机的调度算法转变为数据中心的调度算法是具有挑战性的。该项目应开发一个仿真框架，允许以无缝方式进行此类转换。这将通过利用受可逆排队网络启发的流级调度与数据包级调度之间的连接来实现。智力优点：该项目将推进通信网络可实现调度算法的设计和分析。从智力上讲，这将推进随机逼近算法理论、统计物理学的逼近技术和排队网络的仿真方法。该项目的成功结果表明，最好使用经典电话网络和 ATM 网络设计原理而不是互联网拥塞控制原理来构建数据中心。更广泛的影响：该项目的成功成果将为低延迟和高效数据中心的发展铺平道路。反过来，这将允许开发以前不可行的计算基础设施。鉴于跨学科高性能计算基础设施的核心重要性，该项目的成功成果将产生广泛的影响。这项工作将引起当前充满活力的网络行业的兴趣，初创企业和大型组织都在尝试开发基于软件定义网络理念的下一代数据中心。从某种意义上说，这项工作将为他们实现最终目标提供一条途径。拟议的研究将通过期刊、会议和研讨会上的出版物向社区传播。研究成果也可能会被纳入 PI 定期在麻省理工学院教授的研究生网络课程中。

项目成果

mRSC: Multidimensional Robust Synthetic Control

mRSC：多维鲁棒综合控制

• DOI: 10.1145/3309697.3331507
• 发表时间: 2019-07
• 期刊: ACM SIGMETRICS
• 作者: Amjad, Muhammad Jehangir;Misra, Vishal;Shah, Devavrat;Shen, Dennis
• 通讯作者: Shen, Dennis

Censored Demand Estimation in Retail

零售业的审查需求估计

• 发表时间: 2017-10
• 期刊: ACM SIGMETRICS performance evaluation review
• 作者: Amjad; Muhammad J
• 通讯作者: Muhammad J

tspDB: Time Series Predict DB

tspDB：时间序列预测数据库

• 发表时间: 2024-09-14
• 作者: Anish Agarwal;Abdullah Alomar;Devavrat Shah
• 通讯作者: Devavrat Shah

Q-learning with nearest neighbors

最近邻的 Q 学习

• 发表时间: 2018-10
• 期刊: Nips
• 作者: Shah, Devavrat;Xie, Qiaomin
• 通讯作者: Xie, Qiaomin

Approximately Reversible Stochastic Processing Networks

近似可逆随机处理网络

• 发表时间: 2019-07
• 期刊: INFORMS Applied Probability Society Conference
• 作者: Shah; Devavrat
• 通讯作者: Devavrat