Today's Internet is conformed by thousands of autonomous systems that exchange information using the BGP protocol, which has become the most important routing system since it allows Internet to carry out each of its tasks correctly. Given the above, it is highly important to identify routing problems with an easy to read and analyze mechanism. For this reason, this work proposes to design visualizations of the current state of the BGP routes from both a national and international view. It also proposes a subsequent study to nd daily routing changes, and possible nodes that would cause routing failures after being removed from the network. Lastly, through these investigations it is intended to design BGP monitors, indicating where they should be located; as well as the mechanism for extracting the data necessary for them to work correctly.
BGP (Border Gateway Protocol) nace por la necesidad de controlar la seleccion y propagacion de rutas dentro de un Internet en expansion, transformandose en el sistema de enrutamiento mas importante y complejo de todos los protocolos existentes puesto que permite el correcto funcionamiento de Internet. Por esta razon es importante la busqueda de herramientas capaces de identi car problemas de enrutamiento. Asimismo, debido al gran numero de rutas BGP existentes, ser a util facilitar este proceso de identi cacion mediante un sistema de monitoreo BGP que se encargue de recopilar y proveer informacion importante para luego llevar a cabo el analisis de la misma. Ademas, para comprender de mejor manera los datos recopilados por el sistema, as como tambien su analisis, es imprescindible utilizar un mecanismo de visualizacion mediante el cual sea posible observar tanto las rutas BGP existentes como la informacion relevante de los analisis realizados.
A partir de lo anterior, el trabajo propuesto se basa en disen~ar una visualizacion de las rutas BGP que muestre el estado actual de las mismas. Esta representacion debe ser capaz de mostrar toda la informacion requerida (rutas y las redes IP) en forma clara. Ademas, se realizara un estudio focalizado en dos puntos diferentes; por una parte esta la identi cacion de cambios en las rutas BGP, para lo cual es necesario llevar a cabo un proceso comparativo del estado actual de la informacion con el anterior; el otro punto se basa en analizar el enrutamiento con el objetivo de obtener puntos cr ticos en el grafo, es decir, un nodo que al ser eliminado provoque, por ejemplo, un aislamiento completo de alguna red IP. Lo anterior conlleva al disen~o de un sistema de monitoreo BGP, lo que implica establecer la cantidad y ubicacion de puntos de control dentro de la red, as como tambien determinar el proceso de extraccion de los datos y su posterior almacenamiento, procesamiento, analisis y visualizacion de los mismos. 2
BGP ha sido un protocolo de constante estudio debido a la importancia que este representa para la comunicacion entre redes. Trabajos anteriores han estudiado la vulnerabilidad de BGP, midiendo incluso el efecto que genera un ataque en el sistema de ruteo [ND04]; debido a esto es necesario identi car problemas que puedan signi car algun riesgo potencial para el env o y recepcion de paquetes. Por esto, se han llevado a cabo diferentes investigaciones para disen~ar monitores BGP. Estos trabajos proponen sistemas de recoleccion y analisis automatizado de la informacion de ruteo BGP, ayudando en la deteccion de comportamientos anormales en las rutas [Bor07], as como tambien alertando de cambios en las mismas [Yan+09], los cuales, segun estudios realizados, pueden producir un efecto signi cativo en el ujo de informacion [TAR05].
Ademas, dadas las di cultades enfrentadas debido a la gran cantidad de datos obtenidos, es necesaria la busqueda de un mecanismo de analisis simpli cado. Respecto a esto ultimo se han planteado o realizado varios mecanismos capaces de representar, visualmente, las rutas BGP tales como Link-Rank [LMZ04] [LMZ06], vizAS1 (desarrollada por APNIC ) y ASViewer [Hel11]. Junto a estas posibles formas de visualizacion para las rutas BGP se an~aden los estudios realizados por CAIDA (Center for Applied Internet Data Analysis) que ha generado diferentes grafos de Internet2. Todas las investigaciones permiten generar una idea respecto al posible disen~o a realizar para poder observar las rutas BGP. 3
El sistema propuesto unira dos trabajos independientes, es decir, el disen~o de un sistema de monitoreo junto con visualizaciones de rutas BGP. Ademas incorporara nuevas funcionalidades, tal como la generacion de grafos que entreguen una visibilidad tanto nacional como internacional de las rutas, lo cual permitira analizar si estas son similares tanto desde dentro como desde fuera del pa s. Lo anterior corresponde a la diferencia principal con respecto a BGPmon dado que esta ultima no es georreferenciada. Este nuevo disen~o tendra tambien la particularidad de mostrar visualmente los cambios de ruteo identi cados, lo cual, ademas de observar el tipo de modi cacion ocurrida, permitira focalizar mejor el analisis de donde puede estar el problema o razon del cambio de ruteo. Por otra parte, este sistema se diferencia de los demas dado que busca identi car puntos claves que puedan conllevar, en un futuro, a un posible problema de ujo dentro de la red, siendo routers cr ticos en caso de ataques, fallas, entre otros. 4
Actualmente se cuenta con 3.485.877 datos reales que corresponden a rutas BGP, los cuales vienen al1vizAS: https://blog.apnic.net/2015/09/09/ visualise-your-countrys-bgp-network-with-vizas/ 2AS Core: https://www.caida.org/publications/posters/ #ascore macenados en archivos que contienen diferentes tablas BGP. Estos datos fueron obtenidos por NIC Chile (administrador dominios punto CL) desde los distintos puntos de entrada de router de este. Es importante sen~alar que los datos utilizados corresponden a una muestra diaria obtenida a partir de la tabla BGP de solamente 7 Sistemas Autonomos diferentes (AS6429, AS6471, AS7004, AS14259, AS18747, AS19338 y AS27986) debido a que son estos a los que tiene acceso NIC Chile.
En la Figura 1 se observa un ejemplo de la tabla BGP obtenida. Aqu se puede apreciar que presenta diferentes campos, donde los campos Network y Path son los unicos importantes para conformar una ruta, y por ende los que se utilizaran para trabajar. Cada una de las las de esta tabla corresponde a una ruta BGP donde Network indica la IP de la red a la cual se desea llegar, mientras que Path es una serie de Sistemas Autonomos por los cuales se debe pasar para llegar a dicha IP; la union de estos \puntos" conformara una ruta. En la Figura 2 se aprecia la ruta BGP obtenida a partir de la primera la de la tabla de ruteo de la Figura 1. Cabe destacar que el nodo terminal del camino (IP Network) tambien corresponde a un Sistema Autonomo.
Figura 1: Muestra un extracto de la tabla de ruteo del AS18747.
Figura 2: Muestra un ejemplo de ruta BGP, desde el AS18747 a la red IP 1.0.0.0/24, creada usando la librer a D3 para JavaScript. 5
Dado que se quiere realizar una investigacion de las rutas BGP, y utilizando como base diferentes estudios que indican que utilizar una representacion gra ca para llevar a cabo esta labor permite identi car de mejor manera errores de ruteo, se propone el desarrollo de visualizaciones que presenten, de manera correcta, los datos recopilados desde las tablas de ruteo de los diferentes routers a estudiar. Estas visualizaciones deben dar un panorama tanto nacional como internacional de las rutas BGP, respondiendo a las siguientes preguntas: >Como se ven las redes chilenas desde Chile?, >Como se ven las redes chilenas de manera internacional? y >Como se ven las redes internacionales desde una vision chilena? Para esto sera necesario un estudio previo respecto a cada una de las direcciones IP obtenidas con el objetivo de identi car cuales de estas corresponden a IPs nacionales y cuales a internacionales.
En base al sistema disen~ado, se llevara a cabo un estudio de estas para encontrar cambios generados en las rutas BGP, para esto se debe implementar una forma de poder recuperar diariamente la informacion de ruteo para que, tras su procesamiento, se logre obtener automaticamente su representacion y, ademas, los cambios de enrutamiento con respecto a la informacion antigua, lo cual implica desde la ausencia de un Sistema Autonomo previo hasta el cambio como tal de una ruta (utilizar otros Sistemas Autonomos). Ademas, se realizara un analisis del grafo generado para lograr identi car nodos cr ticos, es decir, routers que al ser desconectados o presentar alguna falla generen, por ejemplo, que redes IP no sean alcanzables por ninguna otra ruta provocando un aislamiento completo de dicha red.
Figura 3: Esquema del sistema de monitoreo. Cada punto de control se representa por un \ojo".
Finalmente, se disen~ara un sistema de monitoreo el cual une cada una de las caracter sticas anteriores, es decir, se dispondran puntos de control encargados de recopilar, diariamente, informacion de las tablas de ruteo de diferentes routers para luego, enviar todos los datos obtenidos a una base de datos \global" de manera automatica; esto dara paso al procesamiento y analisis de estos datos y su posterior visualizacion (ver Figura 3). 6
La metodolog a de trabajo se divide en diferentes etapas de desarrollo. 6.1
Se deben establecer los campos de extraccion de las tablas de ruteo, tales que estos permitan de nir una ruta BGP. Debido a lo anterior, se deben realizar diferentes parser que se encarguen de extraer la informacion y llevarla, nalmente, al formato que sera utilizado para crear la visualizacion.
En cuanto a este punto es posible mencionar que ya se establecieron los parametros de extraccion, tal y como se menciono anteriormente, siendo estos campos: Network y Path. Ademas, se han realizado diferentes programas en Python, encargados de la sustraccion de dichos datos y su transformacion al formato utilizado actualmente, el cual consiste en un json donde cada nodo presenta la siguiente estructura: f " node " : f " i d " : i d n o d e , " group " : group node , " l a b e l " : l a b e l n o d e gg
Donde id node corresponde al AS o a la red, por ejemplo, si el nodo representa al AS 7004, entonces id node tendra el valor 7004; group node identi cara si el nodo en cuestion corresponde a un AS, en cuyo caso group node sera 1, o si es una IP, por lo que tendra el valor 2; mientras que label node sera un identi cador interno de cada nodo dentro de su grupo respectivo. 6.2
Se analizaran diferentes tipos de visualizaciones para encontrar la que mejor se adapte a los objetivos planteados. Para llevar a cabo este proceso se utilizara JavaScript, junto con la librer a gra ca D3.
Actualmente se cuenta con un modelo basico de visualizacion, el cual nacio de las representaciones ya realizadas en trabajos previos, como por ejemplo CAIDA. Este modelo se caracteriza por ser un grafo circular, donde su frontera se conforma por los nodos correspondientes a las IPs, mientras que los nodos internos son los sistemas autonomos utilizados en el ruteo de informacion.
Cabe destacar que debido a la gran cantidad de informacion, el grafo disen~ado contiene agrupacion de IPs segun su ruteo, es decir, se unieron en un solo nodo aquellas redes que presentaban el mismo camino de sistemas autonomos, permitiendo disminuir en gran medida el exceso de informacion visual, clari cando las rutas existentes.
En la Figura 4 se encuentra la representacion desarrollada hasta ahora la cual se debe seguir modi cando, dado que se debe mejorar el posicionamiento y distribucion actual de los nodos, puesto que varios de estos se ubican alejados de sus puntos de conexion inmediatos, generando aristas de gran longitud, lo que provoca que la visualizacion sea mas compleja y dif cil de entender. ya existentes tales como: MaxMind3, LacNic4, entre otros.
A largo plazo se deben desarrollar las caracter sticas principales del sistema de monitoreo, es decir, analizar y desarrollar otros tipos de representaciones gra cas, y establecer como desarrollar las visualizaciones espec cas, eligiendo la representacion que mejor se adapte para solucionar el problema. Ademas, se deben implementar programas de analisis de rutas para identi car cambios de ruteo y puntos cr ticos en la red. Finalmente, se debe determinar el proceso de extraccion de los datos reales utilizados por el sistema de monitoreo, de manera que sea automatizado, y su posterior procesamiento y visualizacion.
Figura 4: Prototipo de visualizacion desarrollada actualmente.
Ademas, se seguira analizando la forma de agrupar los datos de manera tal que disminuya la congestion de informacion, por ejemplo por pre jos de IPs; as como tambien agregar diferentes caracter sticas al modelo, que permitan que la informacion sea mas facil de analizar por un observador externo, por ejemplo, an~adir interactividad, gama de colores, transparencia, entre otros, para resaltar zonas relevantes. Esta medida es vital debido a la gran cantidad de datos que deben contener cada uno de los gra cos a generar, permitiendo focalizar la atencion del observador en ciertos puntos de interes segun el sistema de monitoreo, facilitando un seguimiento y estudio mas focalizado de un posible problema de ruteo. 6.3
Es necesario identi car la localizacion geogra ca tanto de las IPs como de los sistemas autonomos, debido a que se deben realizar visualizaciones de caracter tanto nacional como internacional de las rutas BGP. Para esto se utilizaran trabajos y/o herramientas [Bor07] [Hel11] [LMZ04] [LMZ06] [ND04] [TAR05] [Yan+09]
System". En: Diploma Thesis in Computer Science, Technische Universitat Munchen (mar. de 2007).
tion of global routing dynamics". En: Bachelor Thesis in Informatics, Technische Universitat Munchen (jun. de 2011).
\Link-Rank: A Graphical Tool for Capturing BGP Routing Dynamics". En: Network Operations and Management Symposium (NOMS) (abr. de 2004).
En: IEEE Transactions on Visualization and Computer Graphics (nov. de 2006).
Comput. Commun. Rev. 34.2 (abr. de 2004), pags. 1-8.
SIGCOMM Comput. Commun. Rev. 35.5 (oct. de 2005), pags. 79-82.