CNS Core: Medium: Approximation and Randomization in the Programmable Data Plane

CNS 核心：中：可编程数据平面中的近似和随机化

• 批准号: 2107078
• 负责人: Minlan Yu
• 金额: $ 120万
• 依托单位: Harvard University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-07-01 至 2025-06-30
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2107078&HistoricalAwards=false
• 关键词: CNS; Core; Medium; Approximation; Randomization

The Internet is now a critical infrastructure underlying every aspect of the US economy and enabling new applications in smart health, transportation, energy, education, etc. The Internet is composed of many networks, which are constantly evolving as new technologies develop. A key, recent development in networking is the arrival of the programmable data plane (e.g., programmable network switches). The programmable data plane enables a wide range of applications that make networks more efficient, including not only traditional forwarding, routing, and load-balancing of packets flowing through the network, but also new methods for advanced network monitoring and troubleshooting. However, the programmable data plane now and for the foreseeable future will be highly constrained, due to memory and computational resource constraints of networked devices. To reduce these constraints, this research leverages approximation and randomization for various network problems. The goal of the project is for the research to realize methods and technologies that can enable more efficient, robust, and secure networks for the future. Approximation algorithms provide an answer that is only approximately correct, and randomized algorithms may only be correct with high probability or introduce other randomness in their performance, such as requiring a variable amount of latency. However, utilizing approximate and randomized algorithms can greatly reduce resource requirements while still providing suitably effective results for handling many real-world problems. These will be leveraged towards the main goals of this project: (1) Designing novel methods and algorithms for distributed network applications, making use of the programmable data plane. In particular, the project aims to improve network telemetry approaches, as well as additional applications. (2) Providing libraries of utilities, from low-level functions to higher-level data structures and algorithms, for approximation algorithms and randomized algorithms in switch architectures. (3) Devising theoretical formalizations that provide a framework for designing algorithms in current and future switch architectures, with the goal of influencing the future development of switches. Project contributions will therefore include new algorithms and approaches for multiple network applications, tools and libraries for others to use and adopt, and theoretical frameworks to spur additional development. Indeed, these three focus areas can provide a synergistic virtuous cycle, creating a positive feedback loop for this line of research. The project will facilitate the interdisciplinary research between networking and theory. The project will also engage underrepresented groups and undergraduates in research.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由许多网络组成，这些网络随着新技术的发展而不断发展。网络最近的一个关键发展是可编程数据平面（例如，可编程网络交换机）的出现。可编程数据平面支持广泛的应用，使网络更高效，不仅包括传统的转发，路由和负载均衡的数据包流经网络，而且还提供了高级网络监控和故障排除的新方法。然而，由于网络设备的内存和计算资源的限制，可编程数据平面现在和可预见的未来将受到高度限制。为了减少这些约束，本研究利用近似和随机化来解决各种网络问题。该项目的目标是研究实现方法和技术，使未来的网络更加高效、健壮和安全。近似算法只提供近似正确的答案，而随机算法可能只在高概率下是正确的，或者在其性能中引入其他随机性，例如要求可变的延迟量。然而，利用近似和随机算法可以大大减少资源需求，同时仍然为处理许多现实世界的问题提供适当有效的结果。这些将有助于实现本项目的主要目标：(1)为分布式网络应用程序设计新颖的方法和算法，利用可编程数据平面。特别是，该项目旨在改进网络遥测方法，以及其他应用。(2)为交换机架构中的近似算法和随机算法提供实用程序库，从低级函数到高级数据结构和算法。(3)设计理论形式化，为当前和未来交换机架构中的算法设计提供框架，目标是影响交换机的未来发展。因此，项目贡献将包括多种网络应用程序的新算法和方法、供其他人使用和采用的工具和库，以及促进进一步发展的理论框架。事实上，这三个重点领域可以提供一个协同的良性循环，为这条研究路线创造一个积极的反馈循环。该项目将促进网络与理论之间的跨学科研究。该项目还将吸引代表性不足的群体和本科生参与研究。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

SNARF: A Learning-Enhanced Range Filter

• DOI: 10.14778/3529337.3529347
• 发表时间: 2022-04
• 期刊: Proc. VLDB Endow.
• 作者: Kapil Vaidya;Tim Kraska;Subarna Chatterjee;Eric R. Knorr;M. Mitzenmacher;Stratos Idreos

SwitchV: automated SDN switch validation with P4 models

SwitchV：使用 P4 模型进行自动 SDN 交换机验证

• DOI: 10.1145/3544216.3544220
• 发表时间: 2022
• 期刊: ACM SIGCOMM
• 作者: Albab, Kinan Dak;DiLorenzo, Jonathan;Heule, Stefan;Kheradmand, Ali;Smolka, Steffen;Weitz, Konstantin;Timarzi, Muhammad;Gao, Jiaqi;Yu, Minlan
• 通讯作者: Yu, Minlan

Zero-CPU Collection with Direct Telemetry Access

• DOI: 10.1145/3484266.3487366
• 发表时间: 2021-10
• 期刊: Proceedings of the 20th ACM Workshop on Hot Topics in Networks
• 作者: Jonatan Langlet;Ran Ben Basat;Sivaramakrishnan Ramanathan;G. Oliaro;M. Mitzenmacher;Minlan Yu;G. Antichi

Algorithmic Tools for Understanding the Motif Structure of Networks

• DOI: 10.1007/978-3-031-26390-3_1
• 发表时间: 2022
• 作者: Tianyi Chen;Brian Matejek;M. Mitzenmacher;Charalampos E. Tsourakakis

DRIVE: One-bit Distributed Mean Estimation

• 发表时间: 2021-05
• 期刊: ArXiv
• 作者: S. Vargaftik;Ran Ben Basat;Amit Portnoy;Gal Mendelson;Y. Ben-Itzhak;M. Mitzenmacher