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]
Projektteam
Projektergebnisse
Authors: Hendrik Fichtenberger, Monika Henzinger, Wolfgang Ost
Title: Differentially Private Algorithms for Graphs Under Continual Observation (ESA 2021)
Authors: Monika Henzinger, Ami Paz, Stefan Schmid
Title: On the Complexity of Weight-Dynamic Network Algorithms. (IFIP Networking Conference 2021)
Authors: Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, Gregory Schwartzman
Title: Fast Deterministic Algorithms for Highly-Dynamic Networks. (OPODIS 2020)
Authors: Klaus-Tycho Foerster, Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid
Title: Input-Dynamic Distributed Algorithms for Communication Networks. (ACM SIGMETRICS 2021)
Authors: Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, Ami Paz
Title: Distributed Quantum Proofs for Replicated Data. (ITCS 2021)
Authors: Klaus-Tycho Foerster, Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid
Title: Input-Dynamic Distributed Algorithms for Communication Networks. (POMACS 2021)
Authors: Seth Gilbert, Uri Meir, Ami Paz, Gregory Schwartzman
Title: On the Complexity of Load Balancing in Dynamic Networks. (SPAA 2021)
Authors: Krishnendu Chatterjee, Monika Henzinger, Sagar Sudhir Kale, Alexander Svozil
Title: Faster Algorithms for Bounded Liveness in Graphs and Game Graphs (ICALP 2021)
Authors: Monika Henzinger, Andrea Lincoln, Barna Saha
Title: The Complexity of Average-Case Dynamic Subgraph Counting (SODA 2022)
Authors: Amir Abboud, Karen Censor-Hillel, Seri Khoury, Ami Paz
Title: Smaller Cuts, Higher lower Bounds (ACM Transactions on Algorithms 2021)
Authors: Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, Jukka Suomela
Title: sinkless orientation is hard also in the supported LOCAL model (DISC 2021)
Authors: Monika Henzinger, Alexander Noe, Christian Schulz
Title: Faster Parallel Multiterminal Cuts (ACDA 2021)
Autors: Monika Henzinger, Xiaowei Wu
Title: Upper and Lower Bounds for Fully Retroactive Graph Problems (WADS 2021)
Authors: Kathrin Hanauer, Monika Henzinger, Stefan Schmid, Jonathan Trummer
Title: Fast and Heavy Disjoint Weighted Matchings for Demand-Aware Datacenter Topologies (INFOCOM 2022)
Authors: Monika Henzinger, Alexander Noe, Christian Schulz
Title: Practical Fully Dynamic Minimum Cut Algorithms (ALENEX 2022)
Authors: Kathrin Hanauer, Monika Henzinger, Qi Cheng Hua
Title: Fully Dynamic Four-Vertex Subgraph Counting (SAND 2022)
Authors: Kathrin Hanauer, Monika Henzinger, Christian Schulz
Title: Recent Advances in Fully Dynamic Graph Algorithms (invited talk) (SAND 2022)
Authors: Antoine El-Hayek, Monika Henzinger, Stefan Schmid
Title: Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear (PODC 2022)
Authors: Monika Henzinger, Ami Paz, Sricharan A.R.
Title: Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs (ESA 2022)
Authors: Monika Henzinger, Charlotte Peale, Omer Reingold, Judy Hanwen Shen
Title: Leximax Approximations and Representative Cohort Selection (FORC 2022)
Authors: Monika Henzinger, Ami Paz, Arash Pourdamghani, Stefan Schmid
Title: The augmentation-speed tradeoff for consistent network updates (SOSR 2022)
Authors: Monika Henzinger, Billy Jin, Richard Peng, David P. Williamson
Title: A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems (ITCS 2022)
Authors: Monika Henzinger, Jalaj Upadhyay, Sarvagya Upadhyay
Title: Almost Tight Error Bounds on Differentially Private Continual Counting (to appear at SODA 2023)
Authors: Kathrin Hanauer, Monika Henzinger, Christian Schulz
Title: Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide (Journal of Experimental Algorithmics, JEA 2022)
Authors: Ashish Chiplunkar, Monika Henzinger, Sagar Sudhir Kale, Maximilian Vötsch
Title: Online Min-Max Paging (to appear at SODA23)
Authors: Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen
Title: Fully Dynamic Exact Edge Connectivity in Sublinear Time (SODA 2023)
Authors: Mohammad Hossein Bateni, Hossein Esfandiari, Hendrik Fichtenberger, Monika Henzinger, Rajesh Jayaram, Vahab Mirrokni, Andreas Wiese
Title: Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries (SODA 2023)
Authors: Monika Henzinger, Stefan Neumann, Harald Räcke, Stefan Schmid
Title: Dynamic Maintenance of Monotone Dynamic Programs and Applications (STACS 2023)
Authors: Antoine El-Hayek, Monika Henzinger, Stefan Schmid
Title: Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks (ITCS 2023)
Authors: Gramoz Goranci, Monika Henzinger
Title: Efficient Data Structures for Incremental Exact and Approximate Maximum Flow (ICALP 2023)
