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

Harvard University, Cambridge MA

Investigators

Abstract

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.