Whether as telecommunications or power systems, networks are very important in everyday life. Maintaining these networks properly functional and connected, even under attacks or failures, is of special concern. This topic has been previously studied with a whole network robustness perspective. This perspective measures the average behavior of the network after its last node has failed. Here, we propose an alternative to well-known studies about the robustness of the backbone Internet: to use a supply network model and the supply availability ratio as metric. Our research question is: if a smart adversary has a limited number of strikes to attack the Internet, how much will the damage be after each one in terms of network supplying?
Redes como la red electrica, de transporte y telecomunicaciones, por nombrar algunas, se han vuelto fundamentales para que el mundo moderno se mantenga en funcionamiento. Por ello mantener estos sistemas operando correctamente es de gran importancia. Sin embargo estos sistemas son propensos a fallos, ya sea por mal funcionamiento del sistema o ataques a este. Estas estructuras han sido estudiadas como redes complejas donde sus componentes se representan como noCopyright c by the paper's authors. Copying permitted for private and academic purposes. This work was partially funded by CORFO 15BPE-47225: "Estudio y recomendaciones sobre la resiliencia de la infraestructura del internet chileno". dos y las relaciones entre dichas componentes como arcos.
Dado que el buen funcionamiento de estos sistemas requiere que la red se encuentre bien conectada es de suma importancia estudiar su capacidad para resistir fallos, ya sean estos accidentales o planeados. Esta capacidad es llamada robustez.
Cabe preguntarse entonces que signi ca que una red se encuentre bien conectada. Para responder esta pregunta primero se debe identi car como funciona la red. En el caso de la red de Internet se tienen usuarios que consumen contenido ya sea a traves de un navegador o alguna aplicacion. Para ambas situaciones el usuario debe ser capaz de contactarse con el proveedor de contenidos. Si los usuarios no pueden consumir contenidos los podemos considerar como desconectados de Internet. Luego para el caso de la red de Internet esta esta bien conectada si los usuarios son capaces de comunicarse con el o los proveedores de contenido.
En este trabajo nos enfocamos en el caso de ataques intencionales ejecutados por un adversario para una red que posee proveedores y consumidores. Para lograr esto se considera como metrica de robustez una metrica que considera la existencia de un proveedor. Se puede observar que el caso de ataques intencionales corresponde a una cota superior en el dan~o que se puede in ingir a la red.
Consideramos que un adversario deber a utilizar una estrategia greedy o glotona, apuntando a maximizar el dan~o con el menor numero de ataques. As , en este art culo se discute el desempen~o de ataques sobre el Backbone de Internet (la red formada por puntos de intermabio de Internet, IXP) y su correlacion con lo que los usuarios de Internet perciben si lo que ellos desean es consumir contenido desde (Google), el mayor proveedor de contenido. Para ello se utiliza como primera aproximacion el Supply Availability Ratio (SAR) donde el proveedor es Google.
La idea de considerar una red basada en IXP como \El Backbone de Internet" no es nueva, esta ha sido previamente utilizada como parte del \core de Internet" para estudiar los patrones de tra co entre SAs (sistemas autonomos) y una evolucion entre estrategias de provider peering [LIJM+11], para optimizar la entrega de contenido de Google a traves de caminos directos [CSR+15] y en el Internet Backbone Market [BFBS05]. Nuestro estudio es novedoso por el uso de la red de IXP como un modelo para \El Backbone de Intenet", el cual nos puede dar una aproximacion de la estructura f sica de Internet, y por considerarla como una red de suministro para estudiar su robustez. Hasta donde los autores tienen conocimiento, esta es la primera vez que la robustez de la red IXP es estudiada.
El art culo se organiza de la siguiente forma: la siguiente seccion presenta trabajo relacionado, seguido por la metodolog a para crear la red IXP, la estrategia de ataque usando SAR (Seccion 4). Las conclusiones son presentadas en la seccion 5. 2
Para estudiar la robustez de una red, su evolucion ante fallos debe ser analizada. En situaciones del mundo real las redes pueden enfrentarse tanto a fallas aleatorias como ataques intencionales. Para esta ultima dos categor as principales de estrategias de ataque han sido de nidas: ataques simultaneos y ataques secuenciales [HKYH02a]. Los ataques secuenciales sobre enlaces eligen un enlace a remover y dado el impacto de su remocion sobre la red, elige el siguiente. Este proceso continua iterativamente hasta remover el numero de enlaces deseado. El caso de nodos es analogo.
Los ataques secuenciales han sido estudiados a fondo para analizar la robustez en redes. Holme et al. probo estrategias de ataques simultaneos y secuenciales usando medidas de centralidad como grado y betweenness.
Betweenness [BMSBJ12] es una metrica que determina la importancia de un arco de acuerdo a la cantidad de caminos m nimos que pasan a traves de el. Betweenness ha sido estudiada como metrica de robustez para la capa de ruteo [SHS+11], como metrica de robustez para redes complejas [IKSW13] y para redes de sistemas autonomos de Internet [MKF+06], entre otros. Betweenness ha sido ampliamente estudiado y estandarizado como base de comparacion para metricas de robustez. Por estas razones en este estudio sera utilizada para comparar desempen~o.
Mas recientemente [VA15] estudio ataques secuenciales multi-estrategia usando multiples medidas de robustez, incluyendo la Unique Robustness Measure o Medida Unica de Robustez (R-index) [SMA+11].
En [BRSBJ15] los autores presentan valores parciales del R-index a medida que los nodos son desconectados, mostrando la importancia de escoger una metrica de robustez apropiada para realizar los ataques.
Para entender mejor el tema de ataques a redes y estrategias, ver [HKYH02b, MR06, RW10, SSYS10]. 3
Construyendo el grafo del backbone de Internet
Dentro de Internet, peering corresponde al contrato entre dos sistemas autonomos (SAs) que acuerdan intercambiar rutas de tra co a traves de un enlace f sico. [DD10] presenta que el core de Internet es una jerarqu a multi-tier de proveedores de transito (Transit Providers o TPs) donde aproximadamente 10-20 de los tier-1 TPs, presentes en muchas regiones geogra cas, estan conectadas a un clique de enlaces de peering. Los ISPs (tier-2) son consumidores de los TPs de tier1 y a su vez los proveedores de residencias o pequen~as empresas (tier-3) corresponden a los TPs de tier-2.
A traves de peeringdb.com recolectamos los sistemas autonomos de cada Punto de Intercambio de Internet (Internet Exchange Point, IXP) y los de nimos como nodos del grafo. De esta forma un SA podr a pertenecer a diferentes IXPs y un IXP podr a tener multiples SAs. Luego, conectamos los nodos mediante un arco si cumplen al menos una de las siguientes reglas: SAs conectados f sicamente que intercambian tra co, SAs que pertenecen a un mismo IXP, SAs que pertenecen a una misma instalacion.
Donde los IXP son considerados como peering publico y las intalaciones como peering privado.
La gura 1 muestra el grafo resultante, este tiene 522 nodos y 14:294 arcos (los arcos naranjos representan peering publico, los arcos azules peering privado y los verdes conexion directa por red). La red resultante tiene un core bien conectado con algunos nodos aislados en su borde. 4
Ratio de Disponibilidad de Suministro (Supply Availability Ratio) En 2013 se reporto que que Google pose a el 40% del tra co de Internet1. En consecuencia, dada las pol ticas de peering de Google2 y sus pol ticas para interconectar datacenters [JKM+13], podemos estudiar Internet como una red de suministro adaptando la metrica SAR presentada en [ZKY11].
1. Supply Availability Ratio (SAR): Porcentaje de sistemas autonomos que tiene acceso a Google a traves de al menos uno de sus SAs.
Cabe observar que Google ha delegado algunos servicios a sistemas autonomos de ISPs [CFH+13], sin embargo estos eventualmente deben conectarse con el backbone de Google para actualizarse.
Utilizando una estrategia de ataque basada en betweenness (ver trabajo relacionado) calculamos SAR para distintos porcentajes de arcos removidos. Los resultados son presentados en la Figura 2.
El Ratio de Disponibilidad de Suministro presenta una alta relacion con el taman~o fraccional de la componente conexa mas grande, la cual, en este estudio, incluye al menos un SA de los dos SAs presentes de Google (marcados en rosado en le gura 1, AS15169 en el centro de la red y AS36040 en la orilla de la red).
Se debe notar que para un usuario dentro del core de la red el principal proveedor de contenidos siempre existe y por lo tanto, para el, no hay indicios de que la red se este desarmando (o perdiendo a la mitad de sus miembros como es el caso luego de remover 20% de sus arcos). Sin embargo la realidad es otra: luego de desconectar solo un 5% de la red uno de los SAs de Google queda aislado, mostrando que en este punto la red esta siendo mantenida unicamente por AS15169. 5
En este art culo hemos presentado que tan robusto ser a el backbone de Internet (la red de SAs de peering) si un adversario escogiera sabiamente que enlace va a cortar. Siguiendo recomendaciones, el enlace elegido ser a aquel con mayor betweenness.
1Ver el art culo de Forbes en http://goo.gl/aHdeiN 2Ver https://peering.google.com/#/options/peering.
Con esta estrategia el adversario es capaz de desconectar la mitad de la red removiendo apenas un 20% de los arcos, mas de un 30% de los nodos luego de remover un 10% de los arcos y un 10% de los nodos luego de remover un 1% de los arcos.
Ademas, hemos considerado Internet como una red de suministro donde Google es el principal proveedor de contenido y proponemos estudiar la robustez del backbone de Internet a traves del Supply Availability Ratio (SAR). Dado que en nuestro contexto SAR se de ne como el porcentaje de sistemas autonomos que tiene acceso a Google a traves de al menos uno de sus SAs, SAR presenta gran concordancia con el taman~o fraccional de la componente conexa mas grande pues dicha componente siempre posee un SA de Google y, por lo tanto, los nodos de la componente conexa mas grande siempre tienen acceso a google.
Como trabajo futuro se planea extender el uso de medidas de suministro que consideren otros parametros de la red, de forma de obtener una vision completa del estado de la red. [BFBS05]
Modern Telecommunications and Control Systems and Workshops, pages 497{503. IEEE, 2010.
Achieving high robustness in supply distribution networks by rewiring. Engineering Management, IEEE Transactions on, 58(2):347{362, 2011.