Adaptive multi-path routing for internet traffic engineering

Abstract

Die vorliegende Arbeit stellt das Adaptive Multi-Path Routing (AMP) als einen neuen Algorithmus für dynamisches Traffic Engineering im Internet vor. Das Hauptziel des AMP besteht darin, die Last innerhalb einer Netzdomäne dynamisch zu verteilen, um die überlasteten Verbindungen und Pfade in Realzeit, entsprechend der momentanen Verkehrssituation und den vorhandenen Ausweichmöglichkeiten, zu entlasten. Im Gegensatz zu verwandten Ansätzen, die den Verkehr auf mehrere Pfade aufteilen, führt AMP als seine wichtigste Innovation die Einschränkung der Lastsignalisierung auf den lokalen Umkreis einer Verbindung ein und ermöglicht somit sowohl eine Verringerung der Signalisierungslast, als auch des Speicherbedarfs in den Routern. Dabei ist hervorzuheben, dass AMP trotz seiner lokalen Signalisierungsarchitektur eine globale Ausbreitung der Lastinformation innerhalb der gesamten Netzdomäne ermöglicht und so zu einer effizienten Behandlung von Überlastsituationen im Netz führt. Darüber hinaus stellt diese Arbeit sowohl einen ausführlichen Überblick über die relevante Theorie und die daraus abgeleiteten Ansätze vor, als auch eine tiefgehende Leistungsbewertung des Algorithmus in zwei unterschiedlichen Simulationsumgebungen, die IP-Netze entweder auf Paket- oder auf Flussebene abbilden, und in denen jeweils die gesamte Funktionalität von AMP implementiert wurde. Die untersuchten Simulationsszenarien stellen dabei den letzten Stand der Technik dar, indem ausgeklügelte Topologie- und Verkehrsmodelle verwendet werden, um eine hohe Übertragbarkeit der Erkenntnisse in die Realität zu ermöglichen. Die Ergebnisse der durchgeführten Leistungsbewertung demonstrieren in konsistenter Weise die Effizienz der durch AMP erzielten Lastverteilung, und sie unterstreichen auch das stabile Verhalten des Algorithmus in allen untersuchten Szenarien. Anschließend wird in einer etwas allgemeineren Betrachtung die momentane Bedeutung von Traffic Engineering im aktuellen Kontext der IP-Netze diskutiert, wonach zum Schluss noch wichtige potentielle Anwendungsgebiete für AMP im Bereich von neuen Netzlösungen und -architekturen dargestellt werden.<br />

The present thesis proposes Adaptive Multi-Path routing (AMP) as a novel algorithm for dynamic traffic engineering in the Internet. The main objective of AMP is to distribute load within a network domain in a continuous manner, trying to offload congested links and paths by responding to the observed traffic conditions in real-time. In contrast to similar multi-path routing proposals, the central innovation of AMP lies in the restriction of the exchange of load information to a local scope, thus achieving a significant reduction of signaling overhead and memory consumption in the routers. Most importantly, in spite of its local nature, AMP's signaling mechanism nevertheless enables global propagation of congestion information, leading to an efficient handling of overload events in the network. Apart from providing an extensive overview of the related theory and approaches, this thesis introduces and discusses AMP in depth, after which an exhaustive performance evaluation of the algorithm is presented. This evaluation is carried out using two distinct simulation environments, which model IP networks either at the level of individual packets or individual flows, and for both of which the full functionality of AMP has been implemented in detail. Furthermore, the investigated simulation scenarios represent the state-of-the-art concerning the choice of topologies and traffic models, thus offering a comprehensive insight into the algorithm's behavior in real systems. The results of the performance evaluations consistently demonstrate AMP's efficiency in terms of load balancing performance, and they also underline the stable behavior of the algorithm throughout the investigated scenarios. Finally, the thesis discusses traffic engineering in the current context of IP networks on a more general level, before it presents important potential areas of application for AMP in novel and emerging networking solutions and architectures.