Schnelle Algorithmen fuer eine reaktive Netzwerkschicht

Durch neue, datenintensive Anwendungen in Bereichen wie Unterhaltung, Business und Gesundheit, wächst der Datenverkehr im Internet und in Rechenzentren explosionsartig. Da Kommunikationsnetzwerke eine teure Infrastruktur sind, ist es sinnvoll, die Netzwerke möglichst optimal und effizient auszulasten. Dafür haben Internet Service Providers (ISPs) wie Telekom Austria und Firmen wie Google in den letzten Jahren innovative Lösungen entwickelt. In Kommunikationsnetzwerken wird Information in Form von Paketen mittels intelligenten Geräten, sogenannten Routern, übermittelt. Die Router nutzen eine Vielzahl von Kommunikationsprotokollen, die Teil der Netzwerkschicht sind. Das Projekt zielt darauf ab, die Logik der Router so zu verbessern, dass Pakete schneller übermittelt werden können und es zu weniger Staus auf den Links kommt. Aktuell wird die Logik der Router noch hauptsächlich von Menschen definiert, den Netzwerk Operatoren. Der manuelle Betrieb ist aber nicht nur mühsam, sondern auch anfällig für Fehler; viele Netzwerkausfälle derzeit lassen sich auf menschliches Versagen zurückführen. Zudem kommt es durch den manuellen Betrieb zu langsamen Reaktionszeiten. In diesem Projekt entwickeln und testen wir Algorithmen, die (1) Operatoren unterstützen ihre Netzwerke besser zu konfigurieren, und (2) Netzwerke automatisch optimieren. Im Gegensatz zu den Software Tools, die Operatoren aktuell benutzen und die Konfigurationen bei jeder Änderung komplett neu berechnen, interessieren wir uns für dynamische Algorithmen. Sie können schneller auf Änderungen im Netzwerk reagieren. Wir modellieren das Netzwerk als einen Graphen, der aus Knoten (den Routern) und Kanten (den Kommunikationslinks) besteht. Eine Route von A nach B entspricht einer Sequenz von Knoten und Links in diesem Netzwerk. In aktuellen Kommunikationsnetzwerken hat jede Kante ein Gewicht, über das ein Operator indirekt die Routen im Netzwerk bestimmen kann. Ziel des Projektes ist es, ein Tool zu entwickeln, das bei der Änderung des Linkgewichtes schnell die neuen Routen berechnet. Neben der Frage, wie man die Berechnung von effizienten Routen beschleunigen kann, interessiert uns, wie man die Routen im Netzwerk effizient ändern kann. Beim Wechsel von alten auf neue Routen kann es derzeit zu Loops und Paketverlusten kommen, die sich negativ auf die Leistung des Netzwerkes auswirken können. Kurzzeitig können sogar sicherheitskritische Eigenschaften verletzt werden. In diesem Forschungsprojekt entwickeln wir Algorithmen, die genannte Probleme vermeiden. Dadurch wird die Zuverlässigkeit des Netzwerkes erhöht. In Zusammenarbeit mit einem ISP werden wir versuchen, unsere Erkenntnisse auch praktisch umzusetzen.

Seit September 2020 beschäftigt sich dieses Forschungsprojekt mit der Frage, wie Netzwerke - Systeme, die aus vielen miteinander verbundenen Elementen bestehen - auch dann zuverlässig funktionieren können, wenn sich ihre Strukturen ständig verändern. Beispiele solcher Netzwerke sind soziale Netzwerke, große Computersysteme oder das Internet. Unser Forschungsteam entwickelte neue Methoden, um solche dynamischen Netzwerke effizienter und leistungsfähiger zu machen. Ein zentrales Thema war die Verbreitung von Informationen. Wir untersuchten, wie lange es dauert, bis eine Nachricht alle Mitglieder eines Netzwerks erreicht - selbst wenn die Kontakte zwischen den Teilnehmern zufällig stattfinden. Wir konnten zeigen, dass sich Informationen im Durchschnitt deutlich schneller verbreiten als im schlechtesten Fall - nämlich nach etwa n log(n) Kontakten (wobei n die Anzahl der Teilnehmer ist). Außerdem haben wir die Entscheidungsfindung in Gruppen untersucht: Wenn viele Teilnehmer unterschiedliche Meinungen haben, wie kann sich die Gruppe auf die Mehrheitsmeinung einigen, ohne dass sich jeder alle Ansichten merken muss? Unser Team entwickelte einfache Regeln für solche Prozesse, die wenig Speicher und Rechenleistung erfordern, aber dennoch zuverlässig zum richtigen Ergebnis führen. Besonders praxisrelevant ist die Forschung zur Kommunikation in Rechenzentren - großen Serveranlagen, die Internetdienste bereitstellen. Diese Einrichtungen nutzen sowohl schnelle als auch langsamere Datenverbindungen. Wir entwickelten Methoden, mit denen sich die Nutzung der schnellen Verbindungen kontinuierlich und zügig an den aktuellen Bedarf anpassen lässt - ohne nennenswerte Verzögerungen. Ein weiteres wichtiges Thema war die Aktualisierung von Netzwerken. Wenn sich Verbindungen im Netzwerk ändern - etwa durch Wartung, Ausfälle oder Umstrukturierungen - müssen neue Datenpfade gefunden werden. In Arbeiten zum "Consistent Network Update Problem" zeigte unser Team, dass viele Aktualisierungen deutlich schneller umgesetzt werden können, wenn man eine kurze, gezielte "Überbuchung" von Netzwerkverbindungen erlaubt. Anstatt die Kapazitätsbegrenzung strikt einzuhalten, darf für kurze Zeit etwas mehr Datenverkehr über eine Verbindung laufen, als normalerweise zulässig ist. Insgesamt trägt dieses Projekt dazu bei, moderne Netzwerke schneller, robuster und anpassungsfähiger zu machen - besser gerüstet für die Herausforderungen einer zunehmend digitalen und sich ständig wandelnden Welt.