Fast Algorithms for a Reactive Network Layer

Fast Algorithms for a Reactive Network Layer

Fast Algorithms for a Reactive Network Layer - Abstract

Wider research context. Communication networks today are operated in a fairly static and conservative manner, which entails inefficiencies and slow reaction times. Our project is motivated by the desire to render networks more adaptive, allowing to dynamically re-route flows according to the demand and current contexts, without sacrificing network reliability.

Hypotheses/research questions/objectives. The main hypothesis of this project is that more adaptive network operations will not only greatly improve the efficiency of communication networks, but eventually even benefit network dependability: only a network which can react fast and autonomously to events can ensure seamless communication. To prove our hypothesis, we will design, analyze and evaluate novel algorithms addressing three crucial challenges: (1) With dynamic network algorithms, we will compute new routes after a change in the network very efficiently, significantly speeding up the reaction time of the network control plane, compared to the state-of-the-art algorithms which recompute routes from scratch. (2) Even while changing routes, traffic needs to be routed in a correct and efficient way. With consistent update scheduling algorithms, we will ensure that correctness and performance properties are provided transiently, even during re-routing. (3) After small changes, the recomputation of new routes in the control plane should not even be necessary. With local fast re-routing algorithms, we will study how to efficiently provide a high connectivity and routing in the data plane, leading to extremely fast reaction times.

Approach/methods. We proceed from practice to theory and back: starting from existing network protocols, we derive models and identify bottlenecks, develop and analyze algorithms, and eventually implement our approach. We will build upon the state-of-the-art theory of dynamic and distributed graph algorithms to develop new algorithms as well as prove lower bounds. We will further study graph decomposition algorithms and combinatorial reconfiguration theory.

Level of originality / innovation. This project is the first to make a systematic effort to use modern techniques from dynamic and distributed graph algorithms and related concepts to design an innovative, highly reactive network layer. We believe that now is the right time for this project, as the research community is currently putting significant effort into re-architecting networks, which provides us with a window of opportunity to have impact with our results.

Uni | FH [Universität]

Universität Wien

Projektteam

Projektergebnisse

Paper

Authors: Hendrik Fichtenberger, Monika Henzinger, Wolfgang Ost Title: Differentially Private Algorithms for Graphs Under Continual Observation (ESA 2021)

Paper

Authors: Monika Henzinger, Ami Paz, Stefan Schmid Title: On the Complexity of Weight-Dynamic Network Algorithms. (IFIP Networking Conference 2021)

Paper

Authors: Kathrin Hanauer, Monika Henzinger, Christian Schulz Title: Recent Advances in Fully Dynamic Graph Algorithms. (2021)

Paper

Authors: Klaus-Tycho Foerster, Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid Title: Input-dynamic distributed graph algorithms for congested networks. (2020)

Paper

Authors: Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, Gregory Schwartzman Title: Fast Deterministic Algorithms for Highly-Dynamic Networks. (OPODIS 2020)

Paper

Authors: Klaus-Tycho Foerster, Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid Title: Input-Dynamic Distributed Algorithms for Communication Networks. (2021)

Paper

Authors: Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz Title: Distributed Quantum Proofs for Replicated Data. (ITCS 2021)

Paper

Authors: Klaus-Tycho Foerster, Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid Title: Input-Dynamic Distributed Algorithms for Communication Networks. (2021)

Paper

Authors: Seth Gilbert, Uri Meir, Ami Paz, Gregory Schwartzman Title: On the Complexity of Load Balancing in Dynamic Networks. (2021)

Paper

Authors: Krishnendu Chatterjee, Monika Henzinger, Sagar Sudhir Kale, Alexander Svozil Title: Faster Algorithms for Bounded Liveness in Graphs and Game Graphs (ICALP 2021)