Wissenschaft & Technik

Algorithmen, die sicherstellen sollen, dass sich viele Benutzer ein Netzwerk ausreichend teilen, können einige Benutzer nicht daran hindern, die gesamte Bandbreite zu beanspruchen. – ScienceDaily

Wenn Benutzer Daten schneller über das Internet senden wollen, als das Netzwerk verarbeiten kann, kann es zu Staus kommen – genauso wie Staus den morgendlichen Pendelverkehr in einer 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. 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, die Verzögerung zu minimieren, die durch das Warten auf Daten in Warteschlangen im Netzwerk verursacht wird.

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 heute von vielen Websites und Anwendungen verwendet.

Aber ein Team von MIT-Forschern entdeckte, dass diese Algorithmen zutiefst unfair sein können. In einer neuen Studie zeigen sie, dass es immer ein Netzwerkszenario geben wird, bei dem mindestens ein Sender im Vergleich zu anderen Sendern fast keine Bandbreite erhält. Das heißt, ein als Hunger bekanntes Problem kann nicht vermieden werden.

„Das wirklich Erstaunliche an diesem Papier und den Ergebnissen ist, dass es angesichts der tatsächlichen Komplexität von Netzwerkpfaden und all der Dinge, die sie mit Datenpaketen tun können, im Grunde unmöglich ist, Algorithmen zur Überlastungssteuerung zu vermeiden, die Verzögerungen kontrollieren. Hunger mit aktuellen Methoden.“ sagt Mohammad Alizadeh, außerordentlicher Professor für Elektrotechnik und Informatik (EECS).

Während Alizadeh und seine Kollegen keinen herkömmlichen Algorithmus zur Staukontrolle finden konnten, der Hunger vermeiden 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 Latenzvariationen zulassen, dazu beitragen könnte, eine Aushungerung in bestimmten Netzwerksituationen 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.

Staukontrolle

Staukontrolle ist ein grundlegendes Problem bei der Vernetzung, 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, da ihm Informationen wie die Qualität der Netzwerkverbindung oder wie viele andere Absender das Netzwerk verwenden, nicht vorliegen. Das zu langsame Senden von Paketen nutzt die verfügbare Bandbreite schlecht aus. Wenn sie jedoch zu schnell gesendet werden, kann das Netzwerk überlastet werden, und daher 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 komplex, und Pakete können aus Gründen, die nichts mit einer Netzwerküberlastung zu tun haben, verzögert werden und verloren gehen. Beispielsweise könnten Daten unterwegs in eine Warteschlange gestellt und dann durch einen Burst anderer Pakete 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. Die durch Jitter verursachte Verzögerung ist unvorhersehbar und für den Absender verwirrend. Aufgrund dieser Mehrdeutigkeit beginnen Benutzer, die Verzögerung unterschiedlich einzuschätzen, was dazu führt, dass sie Pakete mit ungleichen Raten senden. Das führe schließlich dazu, dass Hunger eintritt und man komplett ausgeschlossen wird, erklärt Arun.

„Wir haben das Projekt gestartet, weil wir kein theoretisches Verständnis des Verhaltens der Staukontrolle bei Vorhandensein von Jitter hatten. Um es auf eine solidere theoretische Grundlage zu stellen, haben wir ein mathematisches Modell erstellt, das einfach genug ist, um darüber nachzudenken, aber in der Lage ist, einige davon zu erfassen Komplexität des Internets. Es war sehr befriedigend, die mathematischen Dinge zu erfahren, die wir nicht wussten, die aber praktische Bedeutung haben”, sagt er.

Hunger studieren

Die Forscher speisten ihr mathematisches Modell in einen Computer ein, fütterten ihn mit einer Reihe häufig verwendeter Staukontrollalgorithmen und baten den Computer, einen Algorithmus zu finden, der mit ihrem Modell Hunger vermeiden könnte.

„Wir haben es nicht geschafft. Wir haben alle Algorithmen ausprobiert, die wir kennen, und einige neue entwickelt. 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“, sagt Arun .

Die Forscher waren von diesem Ergebnis überrascht, zumal diese Algorithmen allgemein als einigermaßen fair angesehen werden. Sie begannen zu ahnen, dass Hunger, eine extreme Form der Ungerechtigkeit, möglicherweise nicht zu vermeiden sei. Dies motivierte sie dazu, eine Klasse von Algorithmen zu definieren, die sie „Verzögerungskonvergenzalgorithmen“ nennen und von denen sie bewiesen haben, dass sie in ihrem Netzwerkmodell immer unter Hunger leiden würden. Alle existierenden Überlastungssteuerungsalgorithmen, die die Verzögerung steuern (den Forschern bekannt), sind verzögerungskonvergent.

Die Tatsache, dass solch einfache Möglichkeiten zum Scheitern dieser weit verbreiteten Algorithmen so lange unbekannt blieben, zeigt, wie schwierig es ist, die 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. Während alle von ihnen versuchten Algorithmen fehlschlugen, gibt es möglicherweise andere nicht verzögerungskonvergente Algorithmen, die Hunger vermeiden könnten. Die Reichweite ist also größer als jede Verzögerung, die aufgrund von Jitter im Netzwerk auftreten kann.

„Um Latenzen zu kontrollieren, versuchten die Algorithmen, auch die Verzögerungsvarianzen um ein gewünschtes Gleichgewicht zu binden, aber es ist nichts falsch daran, möglicherweise mehr Verzögerungsvarianzen für bessere Verzögerungsmetriken zu schaffen. Es ist nur eine neue Designphilosophie, die übernommen werden sollte“, fügt Balakrishnan hinzu.

Jetzt wollen die Forscher weiter darauf drängen, zu sehen, ob sie einen Algorithmus finden oder erstellen können, der den Hunger 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 sehr kritischen Dingen immer mehr auf Computersysteme, und wir müssen ihre Zuverlässigkeit auf eine solidere konzeptionelle Grundlage stellen. Wir haben die erstaunlichen Dinge gezeigt, die Sie entdecken können, wenn Sie sich die Zeit nehmen, diese offiziellen Spezifikationen von Was ist eigentlich das Problem“, sagt Alizadeh.

.

About the author

m-admin

Leave a Comment