Runtime minimization of scalable network emulation

Abstract

Network emulation constitutes an approved methodology to evaluate the performance of distributed applications and communication protocols. The approach of network emulation models computer networks by connecting instances of the Software under Test (SuT), representing routers and hosts, using a distributed emulation tool. The emulation tool allows for specifying the parameters of these connections, like bandwidth, delay and loss rate. Therefore, network emulation combines the benefits of network simulation, like controllability and repeatability of network experiments, with the benefits of real world testbeds, like accuracy and realism of running the unmodified implementations of the SuT.

Recently, researchers have spent much effort to increase the scalability of network emulation to allow for the evaluation of distributed systems in large network topologies with thousands of network nodes. Basically two concepts are introduced to reach that goal: node and time virtualization. Node virtualization allows for partitioning the physical nodes of an emulation testbed to run multiple instances of the SuT on each physical node. However, the available resources of the physical nodes limit the number of virtual nodes that can be executed by the physical nodes without overloading the hardware. This overload can be avoided by applying the concept of time virtualization. Executing the network experiment with a virtual time, that runs a factor slower than real time, allows for increasing the resources like CPU and network capacity of the testbed by the same factor. However, the runtime of network experiments is also increased by that factor.

The goal of this work is to reduce the runtime of network experiments and, thus, increase the satisfaction of testbed users and testbed operators. Therefore, this thesis makes the following contributions. First, we present an efficient emulation architecture for testbeds with multi-core processors that provides node and time virtualization and minimizes CPU and memory consumption as well as the communication overhead. Second, we introduce the new concept of adaptive virtual time, that allows for dynamically adjusting the speed of the experiment to the resource requirements during the experiment runtime. Using this approach, the experiment can run with an increased speed during periods of low resource requirements. Third, we provide an accurate testbed model to capture the resource requirements of an experiment. Fourth, based on this model, we introduce an approach to calculate an initial placement of virtual nodes onto the physical nodes that minimizes the experiment runtime based on the experiment specification. Finally, in order to react on varying resource requirements during the experiment, we provide an approach to adapt the placement during the running experiment based on transparent migration of virtual nodes to further reduce the experiment runtime.

The developed concepts are implemented and integrated in our Network Emulation Testbed (NET). Detailed evaluations of our prototype show the efficiency and effectiveness of our concepts to minimize the runtime of experiments based on network emulation.

Die Netzwerkemulation stellt eine weitverbreitete Methode zur Leistungsbeurteilung von verteilten Systemen und Kommunikationsprotokollen dar. Bei dieser Methode werden Instanzen der zu testenden Software durch ein verteiltes Emulationswerkzeug verknüpft und somit Rechnernetze modelliert. Das Emulationswerkzeug erlaubt es hierbei die Eigenschaften der Netzwerkverbindungen, wie beispielsweise die Bandbreite, die Verzögerung und die Verlustrate, festzulegen. Daher kombiniert die Netzwerkemulation die Vorteile der Netzwerksimulation, wie die Kontrollierbarkeit und die Wiederholbarkeit von Netzwerkexperimenten, mit den Vorteilen von Tests in realen Netzwerken, wie der Genauigkeit und dem Realismus durch das Ausführen von unveränderter Implementierungen der zu testenden Software.

Der Hauptfokus der Forschung der vergangen Jahre lag auf der Erhöhung der Skalierbarkeit der Netzwerkemulation um auch große Rechnernetze mit tausenden von Netzwerkknoten evaluieren zu können. Für dieses Ziel wurden hauptsächlich zwei Konzepte entwickelt: die Knoten und die Zeitvirtualisierung. Die Knotenvirtualisierung erlaubt es die Betriebsmittel der physischen Knoten einer Emulationsumgebung aufzuteilen und somit eine Vielzahl an Instanzen der zu testenden Software pro physischen Knoten auszuführen. Ohne Überlastung dieser Betriebsmittel kann hierbei nur eine begrenzte Anzahl an virtuellen Knoten pro physischen Knoten ausgeführt werden. Diese Überlastung kann durch Anwendung von Zeitvirtualisierung verhindert werden. Durch virtuelle Zeit kann ein Netzwerkexperiment um einen Faktor verlangsamt ausgeführt werden und somit die Betriebsmittel, wie die Prozessor- und Netzwerkkapazität, um den gleichen Faktor vergrößert werden. Allerdings wird hierbei auch die Experimentlaufzeit um den gleichen Faktor verlängert.

Das Ziel dieser Arbeit ist es daher, die Laufzeit der Netzwerkexperimente zu verringern und somit die Zufriedenheit der Benutzer und der Betreiber von Emulationsumgebung zu steigern. Hierfür macht diese Arbeit folgende Beiträge: Zunächst wird eine effiziente Architektur für Emulationsumgebungen mit Mehrkernprozessoren und Unterstützung für Knoten- und Zeitvirtualiserung vorgestellt. Hierbei wird sowohl der Rechen-, der Speicher- als auch der Kommunikationsmehraufwand minimiert. Als zweites wird das Konzept der adaptiven virtuellen Zeit eingeführt. Diese erlaubt eine dynamische Anpassung der Experimentgeschwindigkeit an den Betriebsmittelverbrauch zur Laufzeit der Experimente. Mittels dieses Ansatzes kann die Ausführungsgeschwindigkeit in Phasen niedriger Last erhöht werden. Als drittes wird ein detailgenaues Modell für Emulationsumgebungen zur Vorhersage des Betriebsmittelverbrauchs des Experiments vorgestellt. Auf diesem Modell aufbauend, wird ein Ansatz zur Berechnung einer initialen Knotenplatzierung von virtuellen auf physische Knoten zur Minimierung der Experimentlaufzeit vorgestellt. Zuletzt wird ein Verfahren zur Laufzeitminimierung in Experimenten mit wechselndem Betriebsmittelverbrauch eingeführt. Durch Migration von virtuellen Knoten wird hierbei die Platzierung der virtuellen Knoten während eines Experimentlaufs derart angepasst, dass sich die Laufzeit der Experimente reduziert.

Die entwickelten Konzepte wurden implementiert und in unsere Emulationsumgebung (NET) integriert. Eine Vielzahl an Messungen und Experimenten mit unserem Prototyp belegen die Effizienz und Effektivität unser Konzepte zur Minimierung der Laufzeit von Netzwerkexperimenten.