Loading…
Inter-Domain Routing Under Scrutiny: Routing Models and Alternative Routing Architectures
Mühlbauer, Wolfgang
Inter-Domain Routing, also die Verkehrslenkung zwischen Autonomen Systemen (ASen), ist seit Jahren ein lebendiges Forschungsgebiet. Hauptursache hierfür ist dessen Komplexität: Zusammenspiel zwischen Interior und Exterior Gateway Protokollen, eine Vielfalt unterschiedlicher Routing Policies, komplexe Verbindungsstrukturen zwischen ASen, usw. Ein wesentliches Ziel der vorliegenden Dissertation besteht in einem verbesserten Allgemeinverständnis des Inter-Domain Routings. Desweiteren werden neuartige Ansätze vorgestellt, um mit Hilfe von Routing-Modellen Vorhersagen zu treffen, und es werden alternative Konzepte für eine Routing-Architektur im zukünftigen Internet erarbeitet. Im ersten Teil der Dissertation wird zunächst umfassend untersucht, welche Metriken für die Charakterisierung der Optimalität und Vielfalt der berechneten Pfade empfindlich sind für Faktoren wie Routing Policies, AS Größe, Topologie, IGP Gewichte, etc. Die Ergebnisse verdeutlichen, dass intra-domain Faktoren die globalen Pfadeigenschaften nur am Rande beeinflussen, während Routing-Policies und die Größe von ASen (bezüglich Anzahl der Router) die dominierenden Faktoren darstellen. Überdies erscheint es schwierig, die globalen Eigenschaften der Wegefindung durch existierende Mechanismen, wie z.B. die Manipulation von BGP Attributen oder die Modifikation von IBGP Graphen, zu verbessern. Auf Grundlage der gewonnenen Erkenntnisse werden anschließend inter-domain Routing-Modelle zur Vorhersage von BGP Pfaden erläutert. Zunächst wird begründet, dass es wichtig ist, einzelne ASe durch mehrere Router zu modellieren. Das Konzept der Quasi-Router wird eingeführt, um die Pfadvielfalt zu erfassen, die man in Routing-Daten beobachten kann. Mit Hilfe von Quasi-Routern lassen sich genaue Vorhersagen auch für solche Pfade treffen, die nicht beobachtet wurden. Anschließend begründet die vorliegende Arbeit, dass die Granularität von Routing Policies überwiegend "Nachbar-zu-Nachbar" ist, obwohl das weitverbreitete Modell der AS Relationships keine Übereinstimmung zwischen den in einem Modell propagierten Routen und jenen Routen, die in der Realität beobachtet werden, erzielt. Angesichts vorhandener Mängel wie beispielsweise Wachstum der Routing-Tabellen, hohe Anzahl an Update-Nachrichten oder ungenügende Möglichkeiten des Traffic Engineerings, werden im letzten Teil langfristige Lösungen für ein "Internet der Zukunft" erörtert. Dieser Abschnitt gliedert sich in zwei Teile: Auf der einen Seite wird Trellis vorgestellt, eine Netzwerk-Testumgebung, die zur Implementierung, zum Test und zur Evaluation von "clean-slate" Lösungen für das Internet der Zukunft verwendet werden kann. Das System erlaubt die Partitionierung eines physikalischen Netzes in mehrere logische oder virtuelle Netze, wobei jedes virtuelle Netz seine eigene Topologie, Routing-Protokolle und Forwarding-Tabellen definieren kann. Auf der anderen Seite, wird HAIR vorgestellt, eine skalierbare Routing-Architektur für ein zukünftiges Internet. HAIR ist ein "rand-basierter" (edge-based) Hybrid zwischen Netz- und Host-basierten Architekturen und stützt sich auf folgende Grundideen: (i) Verwendung von hierarchischem Routing, (ii) Trennung von Locator und Identifier, und (iii) Verwendung eines hierarchischen Mapping Systems. Es erfolgt eine Abschätzung des erwarteten Nutzens von HAIR für das heutige Internet und eine kurze Diskussion einer Prototyp-Implementierung für HAIR.
Much of the mystery behind inter-domain routing in the Internet comes from its complexity: A large number of independently administered autonomous systems (ASs), interactions between intra- and inter-domain routing protocols, manifold routing policies, diverse peering structures between ASs, etc. The thesis at hand aims to improve the understanding of inter-domain routing in general, presents novel approaches for the construction of inter-domain routing models with predictive capabilities, and suggests an alternative routing architecture for a future Internet. We start with a comprehensive study of how sensitive routing optimality and diversity metrics are to factors such as policies, AS size, topology, and IGP weights, etc. Our findings reveal that intra-domain factors only have marginal impact on global path properties while routing policies and AS size (in number of routers) are the dominating factors. Moreover, it is apparently hard to improve the global properties of route selection by existing means, i.e., tweaking BGP attributes, changing iBGP graphs, etc. Based on the obtained insights, we then discuss how to construct models of inter-domain routing with predictive capabilities regarding BGP paths. We start by showing the importance of considering more than one router per AS and introduce quasi-routers to capture path diversity as seen in observed routing data. Relying on the abstraction of quasi-routers, we show that our model provides accurate predictions for unobserved routes. Regarding routing policies our work then reveals that the granularity of actual routing policies is close to per-neighbor although the widely used AS relationship model fails to provide consistency between the routes propagated in our routing model and those seen in observed data. Given several shortcomings of Internet routing such as routing table growth, high update rates, or lack of traffic engineering, we finally discuss long-term solutions for the future Internet. Our research in this area consists of two distinctive parts. First, we present Trellis, a network testbed that can be used by network researchers to implement, test, and evaluate (clean-slate) solutions for a future Internet. As such, it allows to partition a physical network into multiple logical or virtual networks, where each virtual network can define its own topology, routing protocols, and forwarding tables. Second, we introduce HAIR, a scalable routing architecture for a future Internet. HAIR uses a hybrid "edge-based" approach to reconcile network- and host-based routing architectures and is based on the following ideas: (i) use of hierarchical routing, (ii) separation of locators from identifiers, and (iii) use of a hierarchical mapping system. We estimate the expected benefits of deploying HAIR in today's Internet and report our promising experiences with a proof-of-concept implementation of HAIR.
