Forscher entdecken ein großes Hindernis für die Verringerung der Netzwerküberlastung

Wenn Benutzer Daten schneller als das Netzwerk über das Internet senden möchten, können Staus auftreten, ähnlich wie Staus den morgendlichen Pendelverkehr in eine Großstadt verlangsamen.

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. Diese Überlastungskontrollalgorithmen versuchen, verfügbare Netzwerkkapazität zu entdecken und vollständig 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 Netzwerkwarteschlangen 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 von ihnen, wie der von Google entwickelte BBR-Algorithmus, werden mittlerweile von vielen Websites und Anwendungen verwendet.

Aber ein Team von MIT-Forschern hat herausgefunden, 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; Das heißt, ein Problem, das als Hunger bekannt ist, kann nicht vermieden werden.

"Was wirklich überraschend an diesem Artikel und den Ergebnissen ist, ist, dass es angesichts der tatsächlichen Komplexität von Netzwerkpfaden und allem, was sie mit Datenpaketen anstellen können, grundsätzlich unmöglich ist, Verzögerungsalgorithmen für die Überlastungssteuerung zu steuern, um eine Aushungerung mit Strom zu vermeiden Methoden“, sagt Mohammad Alizadeh, außerordentlicher Professor für Elektrotechnik und Informatik (EECS).

Obwohl Alizadeh und ihre Co-Autoren keinen herkömmlichen Algorithmus zur Staukontrolle finden konnten, der Hunger verhindern könnte, gibt es möglicherweise Algorithmen einer anderen Klasse, 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, eine Aushungerung in bestimmten Netzwerksituationen zu verhindern.

Alizadeh war Co-Autorin des Artikels zusammen mit der Erstautorin und EECS-Doktorandin Venkat Arun und der Hauptautorin Hari Balakrishnan, 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.

Überlastung kontrollieren

Die Staukontrolle ist ein grundlegendes Problem in Netzwerken, das Forscher seit den 1980er Jahren zu lösen versuchen.

Der Computer eines Benutzers weiß nicht, wie schnell er Datenpakete über das Netzwerk senden soll, weil ihm Informationen fehlen, wie z. B. die Qualität der Netzwerkverbindung oder die Anzahl anderer Absender, die das Netzwerk verwenden. Durch zu langsames Senden von Paketen wird die verfügbare Bandbreite schlecht genutzt. Wenn Sie sie jedoch zu schnell senden, kann dies das Netzwerk überlasten, und dadurch werden Pakete gelöscht. 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 Paketverlust und -verzögerung als Signale, um auf eine Überlastung zu schließen und zu entscheiden, wie schnell Daten gesendet werden. 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önnen Daten unterwegs in einer Warteschlange hängen bleiben und dann mit einem Burst von anderen Paketen freigegeben werden, oder die Empfangsbestätigung kann 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 nicht den Unterschied zwischen einer durch Überlastung verursachten Verzögerung und einer durch Jitter verursachten Verzögerung erkennen. Die durch Jitter verursachte Verzögerung ist unvorhersehbar und verwirrt den Sender. Aufgrund dieser Mehrdeutigkeit beginnen Benutzer, die Verzögerung anders einzuschätzen, was dazu führt, dass sie Pakete mit ungleichen Raten senden. Letztendlich 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 theoretisches Wissen über das Verhalten 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 fähig war um einige der Feinheiten des Internets zu erfassen. Es war sehr bereichernd zu sehen, wie die Mathematik uns Dinge sagt, die wir nicht wussten und die praktische Relevanz haben", sagt er.

Hunger lernen

Die Forscher fütterten ihr mathematisches Modell mit einem Computer, gaben ihm eine Reihe häufig verwendeter Algorithmen zur Staukontrolle und baten den Computer, einen Algorithmus zu finden, der unter Verwendung ihres Modells eine Hungersnot vermeiden könnte.

"Wir konnten es nicht. Wir haben alle Algorithmen ausprobiert, die wir kennen, und einige neue, die wir entwickelt haben. Nichts hat funktioniert. Der Computer hat immer eine Situation gefunden, in der einige Leute die ganze Bandbreite bekommen und mindestens eine Person die nächste ist zu nichts“, sagt Arun.

Die Forscher waren von diesem Ergebnis überrascht, zumal diese Algorithmen breit gefächert sind...