AitF: Theory and Practice of Probabilistic Network Programming

AitF：概率网络规划的理论与实践

• 批准号: 1637532
• 负责人: John Foster
• 金额: $ 79.9万
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-10-01 至 2020-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1637532&HistoricalAwards=false
• 关键词: AitF; Theory; Practice; Probabilistic; Network

A common objective in many computer networks is to balance traffic across multiple paths in order to improve throughput, reduce congestion, and achieve higher utilization. Although there is an extensive theoretical literature on how best to route traffic through a capacitated network, most networks today rely on schemes that are easy to implement but do not always perform well in practice. This is due, in part, to the gap between the community of theory researchers who study advanced routing schemes and the community of systems researchers who design, build, and operate networks. It is also partly due to the lack of high-level programming languages that make it easy to program advanced routing functionalities in networks and to reason about the performance of such programs.This project will advance the theory and practice of routing by developing oblivious and semi-oblivious routing algorithms that can be implemented on top of current network hardware, accompanied by a probabilistic network programming language and compiler. The intellectual merit of this research lies in developing new routing algorithms that optimize for objectives such as minimizing congestion and balancing load, designing new programming languages based on probabilistic semantics that can be used to express and reason about these algorithms, and building prototype implementations that can be deployed on software-defined networking platforms. This project will have broad impact on society by developing algorithms and tools that could help make networks more reliable and efficient while simplifying network management. To reinforce this broad impact, the project incorporates organizing an interdisciplinary workshop at the intersection between algorithms and networking.

许多计算机网络中的一个共同目标是平衡跨多个路径的流量，以改善吞吐量，减少拥塞并实现更高的利用率。尽管有广泛的理论文献，即如何最好地通过电容网络路由流量，但当今的大多数网络都依赖于易于实施但在实践中并不总是表现良好的方案。这部分归因于研究高级路由方案的理论研究人员与设计，建立和运营网络的系统研究人员社区之间的差距。 It is also partly due to the lack of high-level programming languages that make it easy to program advanced routing functionalities in networks and to reason about the performance of such programs.This project will advance the theory and practice of routing by developing oblivious and semi-oblivious routing algorithms that can be implemented on top of current network hardware, accompanied by a probabilistic network programming language and compiler.这项研究的智力优点在于开发新的路由算法，这些算法优化了诸如最小化拥堵和平衡负载之类的目标，设计基于概率语义的新的编程语言，可用于表达这些算法和推理这些算法，以及可以在软件定义的网络平台上部署的原型实现。该项目将通过开发算法和工具对社会产生广泛的影响，这些算法和工具可以帮助使网络更加可靠，效率更高，同时简化网络管理。为了增强这种广泛的影响，该项目结合了在算法和网络之间的交集中组织跨学科研讨会。

项目成果

Universal Semantics for the Stochastic λ-Calculus

随机 δ 微积分的通用语义

• 发表时间: 2021
• 期刊: ACM/IEEE Symposium on Logic in Computer Science
• 作者: Azevedo de Amorim, Pedro;Kozen, Dexter;Mardare, Radu;Panangaden, Prakash;Roberts, Michael
• 通讯作者: Roberts, Michael

Online Flow Computation on Unit-Vertex-Capacitated Networks

单位顶点容量网络上的在线流计算

• DOI: 10.1137/1.9781611976021.9
• 发表时间: 2020
• 期刊: 1st Symposium on Algorithmic Principles of Computer Systems
• 作者: Arsenis, Makis;Kleinberg, Robert
• 通讯作者: Kleinberg, Robert

Scalable verification of probabilistic networks

概率网络的可扩展验证

• DOI: 10.1145/3314221.3314639
• 发表时间: 2019
• 期刊: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation
• 作者: Smolka, Steffen;Kumar, Praveen;Kahn, David M.;Foster, Nate;Hsu, Justin;Kozen, Dexter;Silva, Alexandra
• 通讯作者: Silva, Alexandra