Im Laufe des letzten Jahrzehnts haben Forscher aus Industrie und Wissenschaft verschiedene Algorithmen entwickelt, die einen hohen Durchsatz bei gleichzeitig geringer Latenz ermöglichen sollen. Einige dieser Algorithmen, wie beispielsweise der von Google entwickelte BBR-Algorithmus, werden mittlerweile von vielen Websites und Anwendungen eingesetzt.

Ein Forscherteam des MIT hat jedoch herausgefunden, dass diese Algorithmen äußerst unfair sein können. In einer neuen Studie zeigen sie, dass es in Netzwerken immer ein Szenario geben wird, in dem mindestens ein Sender im Vergleich zu anderen Sendern nahezu keine Bandbreite erhält; mit anderen Worten: Das Problem der Bandbreitenknappheit ist unvermeidbar.

„Das wirklich Überraschende an dieser Arbeit und ihren Ergebnissen ist, dass es angesichts der Komplexität realer Netzwerkpfade und all dessen, was diese mit Datenpaketen anstellen können, für verzögerungsbasierte Staukontrollalgorithmen mit den derzeitigen Methoden praktisch unmöglich ist, eine Überlastung zu vermeiden“, sagt Mohammad Alizadeh, außerordentlicher Professor für Elektrotechnik und Informatik (EECS).

Obwohl Alizadeh und seine Koautoren keinen herkömmlichen Algorithmus zur Staukontrolle finden konnten, der eine Ressourcenverknappung verhindern könnte, ist es möglich, dass Algorithmen einer anderen Klasse dieses Problem umgehen können. Ihre Analyse legt zudem nahe, dass eine Anpassung der Funktionsweise dieser Algorithmen, um größere Verzögerungsschwankungen zu ermöglichen, in bestimmten Netzwerksituationen eine Ressourcenverknappung verhindern könnte.

Alizadeh verfasste die Studie gemeinsam mit dem Erstautor und EECS-Absolventen Venkat Arun sowie mit dem Seniorautor Hari Balakrishnan, Professor für Informatik und Künstliche Intelligenz an der Fujitsu University. Die Forschungsergebnisse werden auf der Konferenz der ACM Special Interest Group on Data Communications (SIGCOMM) vorgestellt.

Staukontrolle

Die Staukontrolle ist ein grundlegendes Problem in Kommunikationsnetzen, an dessen Lösung Forscher seit den 1980er Jahren arbeiten.

Der Computer eines Benutzers kann die optimale Übertragungsgeschwindigkeit von Datenpaketen im Netzwerk nicht bestimmen, da ihm Informationen wie die Qualität der Netzwerkverbindung oder die Anzahl anderer Netzwerkteilnehmer fehlen. Zu langsames Senden von Paketen nutzt die verfügbare Bandbreite ineffizient. Zu schnelles Senden hingegen kann das Netzwerk überlasten und zu Paketverlusten führen. Diese Pakete müssen erneut gesendet werden, was weitere Verzögerungen verursacht. Verzögerungen können auch entstehen, wenn Pakete längere Zeit in Warteschlangen warten.

Algorithmen zur Staukontrolle nutzen Paketverluste und Verzögerungen als Indikatoren, um auf eine Überlastung zu schließen und die Übertragungsgeschwindigkeit von Daten anzupassen. Das Internet ist jedoch komplex, und Pakete können auch aus Gründen, die nicht mit einer Netzwerküberlastung zusammenhängen, verzögert werden oder verloren gehen. Beispielsweise können Daten auf dem Übertragungsweg in einer Warteschlange hängen bleiben und dann zusammen mit einer Flut anderer Pakete freigegeben werden, oder die Empfangsbestätigung des Empfängers kann sich verzögern. Die Autoren bezeichnen diese nicht staubedingten Verzögerungen als „Jitter“.

Selbst wenn ein Staukontrollalgorithmus die Verzögerung perfekt misst, kann er nicht zwischen durch Stau und durch Jitter verursachter Verzögerung unterscheiden. Jitterbedingte Verzögerung ist unvorhersehbar und verwirrt den Sender. Aufgrund dieser Mehrdeutigkeit schätzen die Nutzer die Verzögerung unterschiedlich ein und senden Pakete mit ungleichmäßigen Raten. Langfristig führt dies zu einer Situation, in der es zu Datenknappheit kommt und einige Nutzer komplett außen vor bleiben, erklärt Arun.

„Wir haben das Projekt gestartet, weil uns ein theoretisches Verständnis des Verhaltens der Staukontrolle bei Jitter fehlte. Um eine solidere theoretische Grundlage zu schaffen, entwickelten wir ein mathematisches Modell, das einfach genug ist, um es zu verstehen, aber dennoch einige der Komplexitäten des Internets abbilden kann. Es war sehr bereichernd, dass uns die Mathematik Dinge aufgezeigt hat, die wir noch nicht wussten und die praktische Relevanz besitzen“, sagt er.

Hungerforschung

Die Forscher speisten ihr mathematisches Modell in einen Computer ein, gaben ihm eine Reihe gebräuchlicher Algorithmen zur Staukontrolle und baten ihn, mithilfe ihres Modells einen Algorithmus zu finden, der eine Verhungern der Ressourcen verhindern kann.

„Wir haben es nicht geschafft. Wir haben jeden uns bekannten Algorithmus ausprobiert und auch einige selbst entwickelte. Nichts hat funktioniert. Der Computer hat immer eine Situation gefunden, in der einige Nutzer die gesamte Bandbreite erhielten und mindestens eine Person praktisch gar nichts bekam“, sagt Arun.

Die Forscher waren von diesem Ergebnis überrascht, insbesondere da diese Algorithmen im Allgemeinen als recht fair gelten. Sie vermuteten, dass ein Ressourcenmangel, eine extreme Form der Ungerechtigkeit, nicht möglich sein könnte. Dies motivierte sie, eine Klasse von Algorithmen zu definieren, die sie „verzögerungskonvergente Algorithmen“ nennen. Sie zeigten, dass diese Algorithmen in ihrem Netzwerkmodell stets einen Ressourcenmangel erleiden. Alle ihnen bekannten Staukontrollalgorithmen, die Verzögerungen berücksichtigen, sind verzögerungskonvergent.

Die Tatsache, dass solch simple Fehlermechanismen dieser weit verbreiteten Algorithmen so lange unbekannt geblieben sind, verdeutlicht, wie schwierig es ist, Algorithmen allein durch empirische Tests zu verstehen, fügt Arun hinzu. Dies unterstreicht die Bedeutung einer soliden theoretischen Grundlage.

Doch es besteht noch Hoffnung. Obwohl alle getesteten Algorithmen versagten, existieren möglicherweise andere, die hinsichtlich der Verzögerung nicht konvergieren und dennoch eine Überlastung vermeiden können. Dies deutet darauf hin, dass ein Lösungsansatz darin bestehen könnte, Algorithmen zur Staukontrolle zu entwickeln, die den Verzögerungsbereich stärker variieren, sodass dieser Bereich größer ist als jede Verzögerung, die durch Jitter im Netzwerk entstehen könnte.

„Um Verzögerungen zu kontrollieren, haben Algorithmen auch versucht, Verzögerungsschwankungen um ein gewünschtes Gleichgewicht zu begrenzen. Es spricht jedoch nichts dagegen, potenziell größere Verzögerungsschwankungen in Kauf zu nehmen, um bessere Messungen von Überlastungsverzögerungen zu erhalten. Es handelt sich lediglich um eine neue Designphilosophie, die übernommen werden sollte“, fügt Balakrishnan hinzu.

Die Forscher wollen nun weiter daran arbeiten, einen Algorithmus zu finden oder zu entwickeln, der das Verhungern von Organismen verhindert. Sie beabsichtigen außerdem, diesen Ansatz der mathematischen Modellierung und der computergestützten Tests auf andere komplexe, ungelöste Probleme in vernetzten Systemen anzuwenden.

„Wir sind in kritischen Bereichen zunehmend auf Computersysteme angewiesen, und ihre Zuverlässigkeit muss auf einer solideren konzeptionellen Grundlage beruhen. Wir haben gezeigt, welche überraschenden Erkenntnisse sich gewinnen lassen, wenn man sich die Zeit nimmt, diese formalen Spezifikationen für das eigentliche Problem zu entwickeln“, sagt Alizadeh.

###

Verfasst von Adam Zewe, MIT-Pressestelle