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.
