Queue management mechanisms with emphasis on random early detection

Abstract

Der Zusammenbruch des Computernetzes im Lawrence Berkeley Labor 1986 war der unmittelbare Anlass zur Modifizierung der damaligen TCP-Version. Mit der Einführung von TCP Tahoe wurde gewährleistet, dass sich die durchschnittliche Senderate eines TCP-Senders an den Lastzustand des betroffenen Routers anpasst.<br />Der Forschergemeinschaft war die sendeseitige Kontrolle des Datenflusses nicht genug. Ihr Ansatz war: In Situationen hoher Netzbelastung haben auch jene Stellen, an denen Stau unmittelbar erkenntlich ist, d.h. die Router, ihren Beitrag zur Staukontrolle zu leisten. Folglich wurde eine Reihe von Ansätzen publiziert mit dem Ziel, einen optimalen Algorithmus zur Kontrolle der Bufferlänge in Routern zu finden.<br />In dieser Arbeit werden zuerst grundlegende Aspekte der TCP-Technologie behandelt. Verschiedene TCP-Versionen werden erläutert, auf denen die Mechanismen zur Bufferkontrolle aufsetzen können. Um die analytische Behandlung solcher Bufferkontrollmechanismen zu verstehen, sind mathematische Modelle des TCP-Transportprotokolls notwendig. Die wichtigsten TCP-Modelle werden vorgestellt, und einige mehr werden referenziert. Sodann werden in einer chronologischen Betrachtung die wichtigsten Überlegungen zur Erstellung eines passenden Buffermanagements beschrieben. Daran schließt eine eingehende Beschreibung von Random Early Detection (RED), einem der etabliertesten Mechanismen zur Bufferkontrolle an.<br />Der Hauptteil der Arbeit ist diesem RED-Mechanismus gewidmet. Nach Erläuterungen über Vor-und Nachteile von RED in der ursprünglichen Version werden sämtliche spätere und modifizierte Versionen aufgezeigt, die den RED-Gedanken übernommen haben, aber die Ausführung in anderer Form vorsehen. Der Schlussteil stellt den Kern der wissenschaftlichen Arbeit dar. Hier wird durch analytische Ableitung eine nichtlineare RED-Funktion präsentiert, die einen schwingungsfreien Betrieb garantiert und gleichzeitig einer schlechten Bufferauslastung entgegenwirkt. Durch den inhärent geschlossenen Regelkreislauf im TCP-System passt sich der Parameter zur Paketverwerfung selbständig der Last an. Simulationsergebnisse, selbst im Vergleich mit systemexternen Regelungsmechanismen, bestätigen den Ansatz für die nichtlineare RED-Kurve.<br />

The computer crash at the Lawrence Berkeley Laboratory in 1986 was the imminent motivation to look for a modified version of the TCP version of that time. Not until the introduction of TCP Tahoe guaranteed that a TCP sender adapts its average sending rate to the load of the corresponding routers on the path.<br />But for the research community flow control on the sending side was not enough. They favored the approach that those sites where congestion is directly observable, i.e. at the routers, should also contribute to an overall congestion control. This work first describes the main principles of TCP technology and several TCP versions. The design of queue management mechanisms is based on such transport mechanisms. In anticipation of an analytical analysis of queue management methods, the most important mathematical models of the TCP transport protocol are presented.<br />Subsequently, the motivations for and approaches to finding an appropriate queue management mechanism are described in a chronological order. Then we describe the most established queue management mechanism, Random Early Detection (RED), in detail.<br />Furthermore, the main part of this work concentrates on this RED mechanism. After contrasting pros and cons of the original RED version, we point to the modified versions in a comprehensive compendium. We show an analytical derivation of a non-linear RED function which guarantees a stable state in all load situations and at the same time avoids link under-utilization. Owing to the inherent closed loop of the TCP system, the non-linear curve adapts the drop parameter to the load situation autonomously. Results in simulations comparing even typical control mechanisms confirm the approach of the nonlinear RED curve.<br />