An empirical evaluation of messy BGP data sources

Abstract

The Internet is the world's largest human-build system and as such evolved to be rather complex. Operators use the Border Gateway Protocol (BGP)---the Internet's de-facto inter-AS routing protocol---to enable global connectivity. However, routing on the Internet is evolving. Although the specification of BGP has not changed since decades, its additions and usage patterns have. Thus, BGP has become an important topic to study for researchers. They use BGP data to, e.g., understand routing decisions, map the Internet's topology, and improve security. Each autonomous system (AS) uses BGP to realize its routing policies based on the business agreements that they have with its neighboring ASes. ASes typically do not share their business agreements publicly. Yet, ASes need to see the effects of a change in their BGP configuration. Route collector projects such as RouteViews and RIPE RIS collect BGP data from as many ASes as possible and make that data publicly available in BGP archives. In addition, data broker services provide interfaces to these BGP archives. Whereas operators use this data to optimize their networks, researchers frequently use this data to study and understand the routing ecosystem. Until now the consistency and reliability of these data sources was usually assumed to be a given. However, it is not. In this dissertation, we fill this gap by investigating the temporal consistency (are routes recorded when they should be) and internal consistency (are routes recorded correctly). Furthermore, we evaluate whether a popular BGP route collector data broker (BGPStream's broker) reliably returns all data files according to supplied search terms. As a policy-based protocol, BGP is implemented on the border routers of ASes. A border router maintains multiple BGP sessions and selects the best route for a prefix by evaluating all learned routes. This is done via BGP attributes. Adjusting these BGP attributes and/or filtering routes allows an AS to implement its routing policies and manage its relationships with other networks. It is commonly assumed that ASes use the same BGP policies for all sessions with the same neighbor AS, preferring the same next-hop AS for the same prefix. In this dissertation, we show that this is often not the case---we refer to such ASes as being heterogeneous. We propose two inference methods to i) quantify the number of heterogeneous ASes as observed by the route collectors, and ii) identify ASes which explicitly diverge from the conventional BGP behavior. Route collectors yield a public view of the Internet---they do not show privately assigned BGP attributes. Thus, ASes collaborate with each other and operate publicly accessible Looking Glasses (LGs). LGs are websites that allow other operators to perform queries on a subset of routers within the ASes to gather routing information. In this dissertation, we collect a LG dataset that focuses on collecting BGP attributes from more than 149 LGs in 154 ASes from 931 routers via scraping LGs. Hereby, the difficulties relate to the non-uniformity of the LGs---most interfaces differ, the fluctuating accessibility of the LGs, as well as the different output formats. To overcome this we combined manual configuration with an automated scraping process followed by careful post-processing and manual checks.

Das Internet ist das weltweit größte von Menschen geschaffene System und hat sich als solches zu einem komplexen Gebilde entwickelt. Betreiber nutzen das BGP—das defacto verwendete Inter-AS-Routing-Protokoll des Internets—um globale Konnektivität zu ermöglichen. Das Routing im Internet entwickelt sich jedoch weiter. Obwohl sich die Spezifikation von BGP seit Jahrzehnten nicht geändert hat, haben sich seine Ergänzungen und Nutzungsmuster gewandelt. Daher ist BGP zu einem wichtigen Forschungsthema geworden. Forscher nutzen BGP Daten beispielsweise, um Routing-Entscheidungen zu verstehen, die Topologie des Internets zu messen, und Routing sicher zu gestalten. Jedes AS verwendet BGP, um seine Richtlinien auf der Grundlage der Geschäftsvereinbarungen mit seinen benachbarten ASes umzusetzen. ASes geben ihre Geschäftsvereinbarungen in der Regel nicht öffentlich bekannt. Dennoch müssen ASes die Auswirkungen einer Änderung ihrer BGP-Konfiguration erkennen können. Routensammler Projekte wie Routeviews und RIPE RIS sammeln BGP Daten von so vielen ASes wie möglich und machen diese Daten in BGP Archiven öffentlich zugänglich. Darüber hinaus bieten Datenbrokerdienste Schnittstellen zu diesen BGP Archiven. Während Betreiber diese Daten zur Optimierung ihrer Netzwerke nutzen, verwenden Forscher sie häufig, um das Routing-Ökosystem zu untersuchen und zu verstehen. Bislang wurde die Konsistenz und Zuverlässigkeit dieser Datenquellen in der Regel als gegeben vorausgesetzt. Dies ist jedoch nicht der Fall. In dieser Dissertation schließen wir diese Lücke, indem wir die zeitliche Konsistenz (werden Routen zum richtigen Zeitpunkt aufgezeichnet?) und die interne Konsistenz (werden Routen korrekt aufgezeichnet?) untersuchen. Darüber hinaus bewerten wir, ob ein beliebter BGP Routensammler Datenbrokerdienst (BGPStream’s Broker) alle Dateien zuverlässig gemäß den angegebenen Suchbefehle zurückgibt. Als Richtlinien basiertes Protokoll wird BGP auf den Border-Routern von ASes eingesetzt. Ein Border-Router unterhält mehrere BGP Sitzungen und wählt die beste Route für einen IP-Präfix aus, indem er alle erlernten Routen bewertet. Dies geschieht über BGP Attribute. Durch Anpassen dieser BGP Attribute und / oder Filtern von Routen kann ein AS seine Routing Richtlinien implementieren und seine Beziehungen zu anderen Netzwerken verwalten. Es wird allgemein angenommen, dass ASes für alle Sitzungen mit demselben Nachbarn AS dieselben BGP Richtlinien verwenden und für den selben IP-Präfix das selbe benachbarte AS bevorzugen. In dieser Dissertation zeigen wir, dass dies oft nicht der Fall ist—wir bezeichnen solche ASes als heterogen. Wir schlagen zwei Inferenzmethoden vor, um (i) die Anzahl heterogener ASes zu ermitteln, wie sie von den Routensammlern beobachtet werden, und (ii) ASes zu identifizieren, die explizit vom herkömmlichen BGP-Verhalten abweichen. Routensammler bieten einen öffentlichen Einblick in das Internet—sie zeigen keine privat zugewiesenen BGP Attribute an. Daher arbeiten ASes miteinander zusammen und betreiben öffentlich zugängliche LGs. LGs sindWebsites, auf denen andere Betreiber Abfragen zu einer Teilmenge von Routern innerhalb der ASes durchführen können, um Routing-Informationen zu sammeln. In dieser Dissertation sammeln wir einen LG Datensatz, der sich auf die Erfassung von BGP Attributen aus mehr als 149 LGs in 154 ASes von 931 Routern durch das Scannen von LGs konzentriert. Die Schwierigkeiten liegen dabei in der Uneinheitlichkeit der LGs—die meisten Schnittstellen unterscheiden sich, die Zugänglichkeit der LGs schwankt und die Ausgabeformate sind unterschiedlich. Um dies zu überwinden, haben wir die manuelle Konfiguration mit einem automatisierten Scraping-Prozess kombiniert, gefolgt von einer sorgfältigen Nachbearbeitung und manuellen Überprüfungen.