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，是太复杂的实施。因此，需要开发这种解决方案的简单实现。这个项目将通过利用随机化（一个la马尔可夫链蒙特卡罗）和统计物理学中的自旋玻璃理论的平均场近似来实现这一目标。其次，将用于交换机的调度算法转换为用于数据中心的调度算法是具有挑战性的。该项目将开发一个仿真框架，将允许以无缝的方式进行这种转换。这将是通过利用流级调度与分组级调度的启发可逆排队network.Intellectual优点：该项目将推进通信网络的可实现的调度算法的设计和分析之间的连接。这将在理论上推动随机逼近算法理论、统计物理逼近技术和排队网络仿真方法的发展。该项目的成功结果表明，最好使用传统电话网络和ATM网络设计背后的原则来构建数据中心，而不是使用Internet拥塞控制。更广泛的影响：该项目的成功结果将为低延迟和高效数据中心的发展铺平道路。反过来，这将允许开发以前不可行的计算基础设施。鉴于跨学科的高性能计算基础设施的核心重要性，该项目的成功结果将产生广泛的影响。这项工作将是目前充满活力的网络行业的兴趣，初创企业和大型组织都在试图开发下一代数据中心，依靠软件定义的网络哲学。从某种意义上说，这项工作将提供一条实现其最终目标的途径。拟议的研究将通过期刊、会议和讲习班的出版物向社区传播。研究成果也可能被整合到PI在麻省理工学院定期教授的研究生网络课程中。

项目成果

Censored Demand Estimation in Retail

• DOI: 10.1145/3154489
• 发表时间: 2017-12
• 期刊: Proceedings of the ACM on Measurement and Analysis of Computing Systems
• 作者: M. Amjad;Devavrat Shah

tspDB: Time Series Predict DB

• 发表时间: 2020
• 作者: Anish Agarwal;Abdullah Alomar;Devavrat Shah

mRSC: Multidimensional Robust Synthetic Control

mRSC：多维鲁棒综合控制

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

Approximately Reversible Stochastic Processing Networks

近似可逆随机处理网络

• 发表时间: 2019
• 期刊: INFORMS Applied Probability Society Conference
• 作者: Shah, Devavrat

Q-learning with nearest neighbors

最近邻的 Q 学习

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