Algorithms for Flexible Networks

• Applicants: Professor Dr. Harald Räcke; Professor Dr. Stefan Schmid
• Subject Area: Theoretical Computer Science ; Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: since 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 470029389

Networked systems have become an important infrastructure of our society: a high availability, but also performance and resource-efficiency, are critical. After a period of stagnation, we have witnessed several significant technological innovations over the last years, in an effort to make networked systems more flexible. Most prominently, compute infrastructure such as datacenters are highly virtualized today, introducing great flexibilities in terms of where and when services can be embedded. But also the interconnecting network has become very flexible and “software-defined" over the last years, offering unprecedented opportunities for efficient traffic engineering. The next frontier in this journey toward more flexible networks is the physical network topology itself: emerging optical technologies allow to reconfigure the physical network at run-time. However, while these flexibilities enable great optimization opportunities, today, only little is known about how to optimally exploit them, and many important underlying algorithmic problems are not well-understood: networked systems technology progressed faster than its foundations. The goal of this project is to close this gap and provide the theoretical and algorithmic underpinnings of more flexible networked systems. In particular, we will develop algorithmic toolkits that can be used to optimize routing, embedding and topology, toward a more efficient and reliable operation of modern networked systems. We identify the common themes of the optimizations to be performed in these different dimensions (routing, embedding, topology design) and derive upper bounds on what can be achieved. Our approach is to proceed from practice to theory and back: we consider state-of-the-art systems, question existing models and propose new ones, revisit existing algorithms and develop more practical ones, and eventually evaluate our solutions.

• DFG Programme: Research Grants