Home Wissenschaften Forscher entdecken eine große Hürde bei der Verringerung von Netzwerküberlastungen
Computernetzwerk

Forscher entdecken eine große Hürde bei der Verringerung von Netzwerküberlastungen

by nwna_de

Bildnachweis: CC0 Public Domain

Wenn Benutzer Daten schneller über das Internet senden möchten, als das Netzwerk bewältigen kann, kann es zu Staus kommen – genauso wie Verkehrsstaus den morgendlichen Pendelverkehr in eine Großstadt stören.

Computer und Geräte, die Daten über das Internet übertragen, zerlegen die Daten in kleinere Pakete und verwenden einen speziellen Algorithmus, um zu entscheiden, wie schnell diese Pakete gesendet werden sollen. Diese Überlastungskontrollalgorithmen versuchen, die verfügbare Netzwerkkapazität vollständig zu entdecken und zu nutzen, während sie sie fair mit anderen Benutzern teilen, die möglicherweise dasselbe Netzwerk teilen. Diese Algorithmen versuchen, Verzögerungen zu minimieren, die durch Daten verursacht werden, die in Warteschlangen im Netzwerk warten.

In den letzten zehn Jahren haben Forscher in Industrie und Wissenschaft mehrere Algorithmen entwickelt, die versuchen, hohe Raten zu erreichen und gleichzeitig Verzögerungen zu kontrollieren. Einige davon, wie der von Google entwickelte BBR-Algorithmus, werden mittlerweile von vielen Websites und Anwendungen verwendet.

Aber ein Team von MIT-Forschern hat entdeckt, dass diese Algorithmen zutiefst unfair sein können. In einer neuen Studie zeigen sie, dass es immer ein Netzwerkszenario geben wird, in dem mindestens ein Sender im Vergleich zu anderen Sendern fast keine Bandbreite erhält, ein Problem, das als Hunger bekannt ist, lässt sich nicht vermeiden.

„Das wirklich Überraschende an diesem Artikel und den Ergebnissen ist, dass, wenn man die reale Komplexität von Netzwerkpfaden und all die Dinge, die sie mit Datenpaketen anstellen können, berücksichtigt, es für verzögerungskontrollierende Überlastungskontrollalgorithmen im Grunde unmöglich ist, dies zu vermeiden Verhungern mit aktuellen Methoden”, sagt Mohammad Alizadeh, außerordentlicher Professor für Elektrotechnik und Informatik (EECS).

Während Alizadeh und seine Co-Autoren keinen traditionellen Algorithmus zur Staukontrolle finden konnten, der Hunger verhindert, könnte es Algorithmen einer anderen Klasse geben, die dieses Problem verhindern könnten. Ihre Analyse deutet auch darauf hin, dass eine Änderung der Funktionsweise dieser Algorithmen, sodass sie größere Verzögerungsvariationen zulassen, dazu beitragen könnte, in einigen Netzwerksituationen eine Aushungerung zu verhindern.

Alizadeh verfasste den Artikel zusammen mit dem Erstautor und EECS-Doktoranden Venkat Arun und dem leitenden Autor Hari Balakrishnan, dem Fujitsu-Professor für Informatik und künstliche Intelligenz. Die Forschungsergebnisse werden auf der Konferenz der ACM Special Interest Group on Data Communications (SIGCOMM) vorgestellt.

Stau kontrollieren

Staukontrolle ist ein grundlegendes Problem bei der Vernetzung, das Forscher seit den 1980er Jahren zu lösen versuchen.

Der Rechner eines Nutzers weiß nicht, wie schnell er Datenpakete über das Netz schicken soll, weil ihm Informationen fehlen, etwa zur Qualität der Netzverbindung oder wie viele andere Absender das Netz nutzen. Durch zu langsames Senden von Paketen wird die verfügbare Bandbreite schlecht genutzt. Aber ein zu schnelles Senden kann das Netzwerk überlasten, und dadurch werden Pakete verworfen. Diese Pakete müssen erneut gesendet werden, was zu längeren Verzögerungen führt. Verzögerungen können auch durch Pakete verursacht werden, die lange in Warteschlangen warten.

Überlastungskontrollalgorithmen verwenden Paketverluste und -verzögerungen als Signale, um auf eine Überlastung zu schließen und zu entscheiden, wie schnell Daten gesendet werden sollen. Aber das Internet ist kompliziert, und Pakete können aus Gründen, die nichts mit Netzwerküberlastung zu tun haben, verzögert werden und verloren gehen. Beispielsweise könnten Daten auf dem Weg in einer Warteschlange aufgehalten und dann mit einem Burst von anderen Paketen freigegeben werden, oder die Bestätigung des Empfängers könnte verzögert werden. Verzögerungen, die nicht durch Staus verursacht werden, nennen die Autoren „Jitter“.

Selbst wenn ein Überlastungskontrollalgorithmus die Verzögerung perfekt misst, kann er den Unterschied zwischen einer durch Überlastung verursachten Verzögerung und einer durch Jitter verursachten Verzögerung nicht erkennen. Durch Jitter verursachte Verzögerungen sind unvorhersehbar und verwirren den Sender. Aufgrund dieser Mehrdeutigkeit beginnen Benutzer, die Verzögerung unterschiedlich zu schätzen, was dazu führt, dass sie Pakete mit ungleichen Raten senden. Schließlich führt dies zu einer Situation, in der es zu Hunger kommt und jemand komplett ausgeschlossen wird, erklärt Arun.

„Wir haben das Projekt gestartet, weil uns ein theoretisches Verständnis des Verhaltens der Staukontrolle bei Vorhandensein von Jitter fehlte. Um es auf eine solidere theoretische Grundlage zu stellen, haben wir ein mathematisches Modell erstellt, das einfach genug war, um darüber nachzudenken, aber dennoch einen Teil davon erfassen konnte Komplexität des Internets. Es war sehr bereichernd, dass uns die Mathematik Dinge erzählt, die wir nicht wussten und die praktische Relevanz haben”, sagt er.

Hunger studieren

Die Forscher speisten ihr mathematisches Modell in einen Computer ein, gaben ihm eine Reihe häufig verwendeter Staukontrollalgorithmen und baten den Computer, einen Algorithmus zu finden, der mithilfe ihres Modells Hunger vermeiden könnte.

„Wir konnten es nicht. Wir haben jeden Algorithmus ausprobiert, den wir kennen, und einige neue, die wir erfunden haben. Nichts hat funktioniert. Der Computer hat immer eine Situation gefunden, in der einige Leute die ganze Bandbreite bekommen und mindestens eine Person im Grunde nichts bekommt “, sagt Arrun.

Die Forscher waren von diesem Ergebnis überrascht, zumal diese Algorithmen allgemein als einigermaßen fair angesehen werden. Sie begannen zu vermuten, dass es nicht möglich sein könnte, Hunger zu vermeiden, eine extreme Form der Ungerechtigkeit. Dies motivierte sie dazu, eine Klasse von Algorithmen zu definieren, die sie „verzögerungskonvergente Algorithmen“ nennen und von denen sie bewiesen haben, dass sie unter ihrem Netzwerkmodell immer unter Hunger leiden werden. Alle bestehenden Überlastungskontrollalgorithmen, die die Verzögerung kontrollieren (die den Forschern bekannt sind), sind verzögerungskonvergent.

Die Tatsache, dass solch einfache Fehlermodi dieser weit verbreiteten Algorithmen so lange unbekannt blieben, zeigt, wie schwierig es ist, Algorithmen allein durch empirische Tests zu verstehen, fügt Arun hinzu. Es unterstreicht die Bedeutung einer soliden theoretischen Grundlage.

Aber alle Hoffnung ist nicht verloren. Obwohl alle von ihnen getesteten Algorithmen fehlgeschlagen sind, gibt es möglicherweise andere Algorithmen, die nicht verzögerungskonvergent sind und in der Lage sein könnten, Hunger zu vermeiden. Die Reichweite ist also größer als jede Verzögerung, die aufgrund von Jitter im Netzwerk auftreten könnte.

„Um Verzögerungen zu kontrollieren, haben Algorithmen versucht, auch die Verzögerungsvariationen um ein gewünschtes Gleichgewicht zu begrenzen, aber es ist nichts Falsches daran, möglicherweise größere Verzögerungsvariationen zu erzeugen, um bessere Messungen von Stauverzögerungen zu erhalten. Es ist nur eine neue Designphilosophie, die man haben müsste adoptieren”, fügt Balakrishnan hinzu.

Jetzt wollen die Forscher weiter darauf drängen, zu sehen, ob sie einen Algorithmus finden oder bauen können, der das Hungern beseitigt. Sie wollen diesen Ansatz der mathematischen Modellierung und rechnerischen Beweise auch auf andere heikle, ungelöste Probleme in vernetzten Systemen anwenden.

„Wir verlassen uns bei kritischen Dingen zunehmend auf Computersysteme, und wir müssen ihre Zuverlässigkeit auf eine solidere konzeptionelle Grundlage stellen. Wir haben die überraschenden Dinge gezeigt, die Sie entdecken können, wenn Sie sich die Zeit nehmen, diese formalen Spezifikationen von was zu entwickeln das Problem ist eigentlich”, sagt Alizadeh.


Reduzierung von Verzögerungen in drahtlosen Netzwerken


Bereitgestellt vom Massachusetts Institute of Technology

Diese Geschichte wurde mit freundlicher Genehmigung von MIT News (web.mit.edu/newsoffice/), eine beliebte Website, die Neuigkeiten über MIT-Forschung, -Innovation und -Lehre enthält.

Zitat: Forscher entdecken große Straßensperre bei der Linderung von Netzwerkstaus (2022, 4. August), abgerufen am 5. August 2022 von https://techxplore.com/news/2022-08-major-roadblock-alleviating-network-congestion.html

Dieses Dokument ist urheberrechtlich geschützt. Abgesehen von einem fairen Handel zum Zwecke des privaten Studiums oder der Forschung darf kein Teil ohne schriftliche Genehmigung reproduziert werden. Der Inhalt dient nur zu Informationszwecken.



Aus dem englischem, Quelle angegeben.