=Paper=
{{Paper
|id=Vol-2178/SSN2018_paper_13
|storemode=property
|title=A Proposal for the Study, Analysis and Visualization of BGP Routes
|pdfUrl=https://ceur-ws.org/Vol-2178/SSN2018_paper_13.pdf
|volume=Vol-2178
|authors=Alexandra Ibarra
|dblpUrl=https://dblp.org/rec/conf/ssn/Ibarra18
}}
==A Proposal for the Study, Analysis and Visualization of BGP Routes==
https://ceur-ws.org/Vol-2178/SSN2018_paper_13.pdf
A Proposal for the Study, Analysis and Visualization of
BGP Routes
Alexandra Ibarra Cuesta
ale@niclabs.cl
NIC Chile Research Labs
University of Chile
Asimismo, debido al gran número de rutas BGP exis-
tentes, serı́a útil facilitar este proceso de identificación
Abstract mediante un sistema de monitoreo BGP que se encar-
gue de recopilar y proveer información importante pa-
Today’s Internet is conformed by thousands
ra luego llevar a cabo el análisis de la misma. Además,
of autonomous systems that exchange infor-
para comprender de mejor manera los datos recopila-
mation using the BGP protocol, which has
dos por el sistema, ası́ como también su análisis, es
become the most important routing system
imprescindible utilizar un mecanismo de visualización
since it allows Internet to carry out each of its
mediante el cual sea posible observar tanto las rutas
tasks correctly. Given the above, it is highly
BGP existentes como la información relevante de los
important to identify routing problems with
análisis realizados.
an easy to read and analyze mechanism. For
A partir de lo anterior, el trabajo propuesto se ba-
this reason, this work proposes to design vi-
sa en diseñar una visualización de las rutas BGP que
sualizations of the current state of the BGP
muestre el estado actual de las mismas. Esta repre-
routes from both a national and international
sentación debe ser capaz de mostrar toda la informa-
view. It also proposes a subsequent study to
ción requerida (rutas y las redes IP) en forma clara.
find daily routing changes, and possible nodes
Además, se realizará un estudio focalizado en dos pun-
that would cause routing failures after being
tos diferentes; por una parte está la identificación de
removed from the network. Lastly, through
cambios en las rutas BGP, para lo cual es necesario lle-
these investigations it is intended to design
var a cabo un proceso comparativo del estado actual
BGP monitors, indicating where they should
de la información con el anterior; el otro punto se basa
be located; as well as the mechanism for ex-
en analizar el enrutamiento con el objetivo de obtener
tracting the data necessary for them to work
puntos crı́ticos en el grafo, es decir, un nodo que al
correctly.
ser eliminado provoque, por ejemplo, un aislamiento
completo de alguna red IP. Lo anterior conlleva al di-
1 Introducción seño de un sistema de monitoreo BGP, lo que implica
establecer la cantidad y ubicación de puntos de con-
BGP (Border Gateway Protocol) nace por la nece- trol dentro de la red, ası́ como también determinar el
sidad de controlar la selección y propagación de rutas proceso de extracción de los datos y su posterior al-
dentro de un Internet en expansión, transformándo- macenamiento, procesamiento, análisis y visualización
se en el sistema de enrutamiento más importante y de los mismos.
complejo de todos los protocolos existentes puesto que
permite el correcto funcionamiento de Internet. Por
esta razón es importante la búsqueda de herramien- 2 Trabajo Relacionado
tas capaces de identificar problemas de enrutamiento. BGP ha sido un protocolo de constante estudio de-
bido a la importancia que este representa para la co-
Copyright c by the paper’s authors. Copying permitted for
private and academic purposes.
municación entre redes. Trabajos anteriores han estu-
In: Proceedings of the IV School of Systems and Networks
diado la vulnerabilidad de BGP, midiendo incluso el
(SSN 2018), Valdivia, Chile, October 29-31, 2018. Published efecto que genera un ataque en el sistema de ruteo
at http://ceur-ws.org [ND04]; debido a esto es necesario identificar proble-
mas que puedan significar algún riesgo potencial pa- macenados en archivos que contienen diferentes ta-
ra el envı́o y recepción de paquetes. Por esto, se han blas BGP. Estos datos fueron obtenidos por NIC Chile
llevado a cabo diferentes investigaciones para diseñar (administrador dominios punto CL) desde los distin-
monitores BGP. Estos trabajos proponen sistemas de tos puntos de entrada de router de este. Es impor-
recolección y análisis automatizado de la información tante señalar que los datos utilizados corresponden
de ruteo BGP, ayudando en la detección de comporta- a una muestra diaria obtenida a partir de la tabla
mientos anormales en las rutas [Bor07], ası́ como tam- BGP de solamente 7 Sistemas Autónomos diferentes
bién alertando de cambios en las mismas [Yan+09], los (AS6429, AS6471, AS7004, AS14259, AS18747, AS19338
cuales, según estudios realizados, pueden producir un y AS27986) debido a que son estos a los que tiene ac-
efecto significativo en el flujo de información [TAR05]. ceso NIC Chile.
Además, dadas las dificultades enfrentadas debido En la Figura 1 se observa un ejemplo de la tabla
a la gran cantidad de datos obtenidos, es necesaria BGP obtenida. Aquı́ se puede apreciar que presenta
la búsqueda de un mecanismo de análisis simplifica- diferentes campos, donde los campos Network y Path
do. Respecto a esto último se han planteado o realiza- son los únicos importantes para conformar una ruta,
do varios mecanismos capaces de representar, visual- y por ende los que se utilizarán para trabajar. Cada
mente, las rutas BGP tales como Link-Rank [LMZ04] una de las filas de esta tabla corresponde a una ruta
[LMZ06], vizAS1 (desarrollada por APNIC ) y AS- BGP donde Network indica la IP de la red a la cual
Viewer [Hel11]. Junto a estas posibles formas de vi- se desea llegar, mientras que Path es una serie de Sis-
sualización para las rutas BGP se añaden los estudios temas Autónomos por los cuales se debe pasar para
realizados por CAIDA (Center for Applied Internet llegar a dicha IP; la unión de estos “puntos” confor-
Data Analysis) que ha generado diferentes grafos de mará una ruta. En la Figura 2 se aprecia la ruta BGP
Internet2 . Todas las investigaciones permiten generar obtenida a partir de la primera fila de la tabla de ruteo
una idea respecto al posible diseño a realizar para po- de la Figura 1. Cabe destacar que el nodo terminal del
der observar las rutas BGP. camino (IP Network) también corresponde a un Siste-
ma Autónomo.
3 Particularidad del trabajo propuesto
El sistema propuesto unirá dos trabajos indepen-
dientes, es decir, el diseño de un sistema de monito-
reo junto con visualizaciones de rutas BGP. Además
incorporará nuevas funcionalidades, tal como la gene-
ración de grafos que entreguen una visibilidad tanto
nacional como internacional de las rutas, lo cual per-
mitirá analizar si estas son similares tanto desde den-
tro como desde fuera del paı́s. Lo anterior corresponde
a la diferencia principal con respecto a BGPmon da- Figura 1: Muestra un extracto de la tabla de ruteo del
do que esta última no es georreferenciada. Este nuevo AS18747.
diseño tendrá también la particularidad de mostrar vi-
sualmente los cambios de ruteo identificados, lo cual,
además de observar el tipo de modificación ocurrida,
permitirá focalizar mejor el análisis de donde puede es-
tar el problema o razón del cambio de ruteo. Por otra
parte, este sistema se diferencia de los demás dado que
busca identificar puntos claves que puedan conllevar,
en un futuro, a un posible problema de flujo dentro
de la red, siendo routers crı́ticos en caso de ataques,
fallas, entre otros. Figura 2: Muestra un ejemplo de ruta BGP, desde el
AS18747 a la red IP 1.0.0.0/24, creada usando la li-
4 Análisis Preliminar brerı́a D3 para JavaScript.
Actualmente se cuenta con 3.485.877 datos reales
que corresponden a rutas BGP, los cuales vienen al-
1 vizAS: https://blog.apnic.net/2015/09/09/ 5 Trabajo a Desarrollar
visualise-your-countrys-bgp-network-with-vizas/
2 AS Core: https://www.caida.org/publications/posters/ Dado que se quiere realizar una investigación de las
#ascore rutas BGP, y utilizando como base diferentes estudios
que indican que utilizar una representación gráfica pa- ruteo de diferentes routers para luego, enviar todos
ra llevar a cabo esta labor permite identificar de mejor los datos obtenidos a una base de datos “global” de
manera errores de ruteo, se propone el desarrollo de manera automática; esto dará paso al procesamiento
visualizaciones que presenten, de manera correcta, los y análisis de estos datos y su posterior visualización
datos recopilados desde las tablas de ruteo de los dife- (ver Figura 3).
rentes routers a estudiar. Estas visualizaciones deben
dar un panorama tanto nacional como internacional 6 Metodologı́a
de las rutas BGP, respondiendo a las siguientes pre-
guntas: ¿Cómo se ven las redes chilenas desde Chile?, La metodologı́a de trabajo se divide en diferentes
¿Cómo se ven las redes chilenas de manera internacio- etapas de desarrollo.
nal? y ¿Cómo se ven las redes internacionales desde
una visión chilena? Para esto será necesario un estu- 6.1 Manejo de la tabla de ruteo
dio previo respecto a cada una de las direcciones IP Se deben establecer los campos de extracción de
obtenidas con el objetivo de identificar cuales de estas las tablas de ruteo, tales que estos permitan definir
corresponden a IPs nacionales y cuales a internaciona- una ruta BGP. Debido a lo anterior, se deben reali-
les. zar diferentes parser que se encarguen de extraer la
En base al sistema diseñado, se llevará a cabo un información y llevarla, finalmente, al formato que será
estudio de estas para encontrar cambios generados en utilizado para crear la visualización.
las rutas BGP, para esto se debe implementar una for- En cuanto a este punto es posible mencionar que
ma de poder recuperar diariamente la información de ya se establecieron los parámetros de extracción, tal y
ruteo para que, tras su procesamiento, se logre ob- como se mencionó anteriormente, siendo estos campos:
tener automáticamente su representación y, además, Network y Path. Además, se han realizado diferentes
los cambios de enrutamiento con respecto a la infor- programas en Python, encargados de la sustracción de
mación antigua, lo cual implica desde la ausencia de dichos datos y su transformación al formato utilizado
un Sistema Autónomo previo hasta el cambio como actualmente, el cual consiste en un json donde cada
tal de una ruta (utilizar otros Sistemas Autónomos). nodo presenta la siguiente estructura:
Además, se realizará un análisis del grafo generado pa-
{ ” node ” : {
ra lograr identificar nodos crı́ticos, es decir, routers que
” id ” : id node ,
al ser desconectados o presentar alguna falla generen, ” group ” : g r o u p n o d e ,
por ejemplo, que redes IP no sean alcanzables por nin- ” label ” : label node
guna otra ruta provocando un aislamiento completo de }}
dicha red.
Donde id node corresponde al AS o a la red, por
ejemplo, si el nodo representa al AS 7004, entonces
id node tendrá el valor 7004; group node identificará
si el nodo en cuestión corresponde a un AS, en cuyo
caso group node será 1, o si es una IP, por lo que tendrá
el valor 2; mientras que label node será un identificador
interno de cada nodo dentro de su grupo respectivo.
6.2 Diseño de visualización
Se analizarán diferentes tipos de visualizaciones pa-
ra encontrar la que mejor se adapte a los objetivos
planteados. Para llevar a cabo este proceso se utilizará
JavaScript, junto con la librerı́a gráfica D3.
Actualmente se cuenta con un modelo básico de vi-
sualización, el cual nació de las representaciones ya
realizadas en trabajos previos, como por ejemplo CAI-
Figura 3: Esquema del sistema de monitoreo. Cada DA. Este modelo se caracteriza por ser un grafo circu-
punto de control se representa por un “ojo”. lar, donde su frontera se conforma por los nodos corres-
pondientes a las IPs, mientras que los nodos internos
Finalmente, se diseñará un sistema de monitoreo son los sistemas autónomos utilizados en el ruteo de
el cual une cada una de las caracterı́sticas anteriores, información.
es decir, se dispondrán puntos de control encargados Cabe destacar que debido a la gran cantidad de in-
de recopilar, diariamente, información de las tablas de formación, el grafo diseñado contiene agrupación de
IPs según su ruteo, es decir, se unieron en un solo ya existentes tales como: MaxMind3 , LacNic4 , entre
nodo aquellas redes que presentaban el mismo camino otros.
de sistemas autónomos, permitiendo disminuir en gran
medida el exceso de información visual, clarificando las 6.4 Trabajo futuro
rutas existentes. A largo plazo se deben desarrollar las caracterı́sticas
En la Figura 4 se encuentra la representación desa- principales del sistema de monitoreo, es decir, analizar
rrollada hasta ahora la cual se debe seguir modifican- y desarrollar otros tipos de representaciones gráficas, y
do, dado que se debe mejorar el posicionamiento y establecer cómo desarrollar las visualizaciones especı́fi-
distribución actual de los nodos, puesto que varios de cas, eligiendo la representación que mejor se adapte
estos se ubican alejados de sus puntos de conexión in- para solucionar el problema. Además, se deben imple-
mediatos, generando aristas de gran longitud, lo que mentar programas de análisis de rutas para identificar
provoca que la visualización sea más compleja y difı́cil cambios de ruteo y puntos crı́ticos en la red. Final-
de entender. mente, se debe determinar el proceso de extracción de
los datos reales utilizados por el sistema de monito-
reo, de manera que sea automatizado, y su posterior
procesamiento y visualización.
Referencias
[Bor07] Gunnar Bornemann. “Data Analysis and
Design of a BGP Monitoring and Alarm
System”. En: Diploma Thesis in Computer
Science, Technische Universität München
(mar. de 2007).
[Hel11] Mathias Helminger. “Interactive visualiza-
tion of global routing dynamics”. En: Ba-
chelor Thesis in Informatics, Technische
Universität München (jun. de 2011).
[LMZ04] Mohit Lad, Dan Massey y Lixia Zhang.
Figura 4: Prototipo de visualización desarrollada ac- “Link-Rank: A Graphical Tool for Captu-
tualmente. ring BGP Routing Dynamics”. En: Net-
work Operations and Management Sympo-
sium (NOMS) (abr. de 2004).
Además, se seguirá analizando la forma de agrupar
los datos de manera tal que disminuya la congestión de [LMZ06] Mohit Lad, Dan Massey y Lixia Zhang.
información, por ejemplo por prefijos de IPs; ası́ como “Visualizing Internet Routing Changes”.
también agregar diferentes caracterı́sticas al modelo, En: IEEE Transactions on Visualization
que permitan que la información sea más fácil de ana- and Computer Graphics (nov. de 2006).
lizar por un observador externo, por ejemplo, añadir [ND04] Ola Nordström y Constantinos Dovrolis.
interactividad, gama de colores, transparencia, entre “Beware of BGP Attacks”. En: SIGCOMM
otros, para resaltar zonas relevantes. Esta medida es Comput. Commun. Rev. 34.2 (abr. de
vital debido a la gran cantidad de datos que deben con- 2004), págs. 1-8.
tener cada uno de los gráficos a generar, permitiendo [TAR05] Renata Teixeira, Sharad Agarwal y Jen-
focalizar la atención del observador en ciertos puntos nifer Rexford. “BGP Routing Changes:
de interés según el sistema de monitoreo, facilitando Merging Views from Two ISPs”. En:
un seguimiento y estudio más focalizado de un posible SIGCOMM Comput. Commun. Rev. 35.5
problema de ruteo. (oct. de 2005), págs. 79-82.
[Yan+09] He Yan y col. “BGPmon: A Real-Time,
6.3 Identificación de IPs Scalable, Extensible Monitoring System”.
En: 2009 Cybersecurity Applications Tech-
Es necesario identificar la localización geográfica nology Conference for Homeland Security
tanto de las IPs como de los sistemas autónomos, debi- (2009), págs. 212-223.
do a que se deben realizar visualizaciones de carácter
tanto nacional como internacional de las rutas BGP. 3 https://www.maxmind.com/en/home
Para esto se utilizarán trabajos y/o herramientas 4 https://rdap-web.lacnic.net/