Fast Algorithms for a Reactive Network Layer

The traffic in the Internet and inside datacenters is growing explosively, also because of the new datacentric applications related to entertainment, business, health, etc. As communication networks are often an expensive infrastructure, making best use of them is important. Over the last decades, Internet Service Providers (ISPs) such as Telekom Austria and companies such as Google, have made great efforts to improve the routing and hence utilization of their part of the network. In communication networks such as the Internet, information is sent in form of packets which are shipped from the origin to the destination via various routers. To achieve this, routers rely on a set of protocols which are part of the so-called network layer. The goal of this project is to improve the decisions made at these routers to lead to faster delivery of the packets as well as less congestion of network links. Currently, some crucial decisions at these routers are set by humans, so-called network operators. However, configuring routers manually is cumbersome and error-prone, and many network outages today are due to human errors. Furthermore, a manual operation of computer networks only allows for slow adjustments. This project will develop and test algorithms to (1) help the network operations make better decisions by allowing them to simulate various decisions and, more ambitiously to (2) design programs that can automatically make the decisions at the routers. In particular, unlike the few existing software tools supporting human operators today, which rely on re-computations from scratch, we are interested in fast dynamic algorithms which enable faster reactions to both planned and unplanned changes in the network. To do so we model the network as a graph, consisting of vertices that represent the routers and edges between pairs of vertices that represent a communication link between the corresponding routers. A routing from vertex A to vertex B corresponds to a path from A to B in this network. Usually each link has a value that is set manually by a network operator, to control how many routing paths use a given link. One of the goals of this project is to develop a tool which computes very quickly how a link value change will affect all existing routing paths, much faster than the existing tools. . In addition to making the computation of efficient routes faster, we in this project also explore mechanisms to ensure a smooth transition when changing from old routes to new routes: today, such changes can temporarily lead to loops, performance drops and packet losses, or even short violations of the network policy. In our project, we aim to develop algorithms which provably avoid such problems, and hence further improve the dependability of computer networks. Furthermore, we will also explore the deployment our technology in collaboration with ISPs. This is important as communication networks have become a critical infrastructure of our digital society.

Since September 2020, this research project has focused on how networks-systems made up of many interconnected elements-can continue to function reliably even when their structure is constantly changing. This applies, for example, to social networks, large computer systems, or the Internet. Our team developed new methods to make such dynamic networks more efficient and powerful. A central topic was the spread of information. We investigated how long it takes for a message to reach all members of a network-even when contacts between participants occur randomly. We showed that information circulates much faster on average than in the worst-case scenario-namely after about n log(n) contacts (where n is the number of participants). We also looked at group decision-making: When many participants hold different opinions, how can the group agree on the majority opinion without everyone needing to keep track of all views? Our team developed simple rules for such processes that require little memory and computing power but reliably lead to the correct result. Particularly practical is the research on communication in data centers, large server facilities that run Internet services. These facilities use both fast and slower data connections. We developed methods that allow the use of the fast connections to be continuously and quickly adapted to current demand-without significant delays. Another important topic was updating networks. When connections in the network change-due to maintenance, outages, or restructuring-new data paths must be found. In work on the Consistent Network Update Problem, our team showed that allowing a short, targeted "oversubscription" of network links enables many updates to be implemented much faster. Instead of strictly following every step, slightly more data can be sent over a link than normally allowed for a short time. Overall, this project contributes to making modern networks faster, more robust, and more adaptable-better prepared to meet the challenges of an increasingly digital and constantly changing world.