Studying the Importance of Content Providers on Internet Robustness Metrics Ivana Bachmann Javier Bustos-Jiménez NIC Labs, Universidad de Chile, Chile NIC Labs, Universidad de Chile, Chile ivana@niclabs.cl jbustos@niclabs.cl Fernando Morales Alonso Silva NIC Labs, Universidad de Chile, Chile Bell Labs, Nokia, Francia fernando@niclabs.cl alonso.silva@nokia-bell-labs.com dos y las relaciones entre dichas componentes como arcos. Abstract Dado que el buen funcionamiento de estos sistemas requiere que la red se encuentre bien conectada es de Whether as telecommunications or power sys- suma importancia estudiar su capacidad para resistir tems, networks are very important in every- fallos, ya sean estos accidentales o planeados. Esta day life. Maintaining these networks properly capacidad es llamada robustez. functional and connected, even under attacks Cabe preguntarse entonces qué significa que una red or failures, is of special concern. This topic se encuentre bien conectada. Para responder esta pre- has been previously studied with a whole net- gunta primero se debe identificar cómo funciona la red. work robustness perspective. This perspective En el caso de la red de Internet se tienen usuarios que measures the average behavior of the network consumen contenido ya sea a través de un navegador o after its last node has failed. alguna aplicación. Para ambas situaciones el usuario Here, we propose an alternative to well-known debe ser capaz de contactarse con el proveedor de con- studies about the robustness of the backbone tenidos. Si los usuarios no pueden consumir contenidos Internet: to use a supply network model and los podemos considerar como desconectados de Inter- the supply availability ratio as metric. Our re- net. Luego para el caso de la red de Internet esta está search question is: if a smart adversary has a bien conectada si los usuarios son capaces de comuni- limited number of strikes to attack the Inter- carse con el o los proveedores de contenido. net, how much will the damage be after each En este trabajo nos enfocamos en el caso de ataques one in terms of network supplying? intencionales ejecutados por un adversario para una red que posee proveedores y consumidores. Para lo- 1 Introducción grar esto se considera como métrica de robustez una métrica que considera la existencia de un proveedor. Redes como la red eléctrica, de transporte y telecomu- Se puede observar que el caso de ataques intencionales nicaciones, por nombrar algunas, se han vuelto fun- corresponde a una cota superior en el daño que se damentales para que el mundo moderno se mantenga puede inflingir a la red. en funcionamiento. Por ello mantener estos sistemas Consideramos que un adversario deberı́a utilizar operando correctamente es de gran importancia. Sin una estrategia greedy o glotona, apuntando a maxi- embargo estos sistemas son propensos a fallos, ya sea mizar el daño con el menor número de ataques. Ası́, por mal funcionamiento del sistema o ataques a este. en este artı́culo se discute el desempeño de ataques so- Estas estructuras han sido estudiadas como redes com- bre el Backbone de Internet (la red formada por puntos plejas donde sus componentes se representan como no- de intermabio de Internet, IXP) y su correlación con lo que los usuarios de Internet perciben si lo que el- Copyright c by the paper’s authors. Copying permitted for private and academic purposes. This work was partially funded los desean es consumir contenido desde (Google), el by CORFO 15BPE-47225: ”Estudio y recomendaciones sobre mayor proveedor de contenido. Para ello se utiliza la resiliencia de la infraestructura del internet chileno”. como primera aproximación el Supply Availability Ra- tio (SAR) donde el proveedor es Google. En [BRSBJ15] los autores presentan valores par- La idea de considerar una red basada en IXP como ciales del R-index a medida que los nodos son de- “El Backbone de Internet” no es nueva, esta ha sido sconectados, mostrando la importancia de escoger previamente utilizada como parte del “core de Inter- una métrica de robustez apropiada para realizar los net” para estudiar los patrones de tráfico entre SAs ataques. (sistemas autónomos) y una evolución entre estrate- Para entender mejor el tema de ataques a redes y gias de provider peering [LIJM+ 11], para optimizar la estrategias, ver [HKYH02b, MR06, RW10, SSYS10]. entrega de contenido de Google a través de caminos directos [CSR+ 15] y en el Internet Backbone Market 3 Construyendo el grafo del backbone [BFBS05]. Nuestro estudio es novedoso por el uso de de Internet la red de IXP como un modelo para “El Backbone de Intenet”, el cual nos puede dar una aproximación 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 sigu- iente sección presenta trabajo relacionado, seguido por la metodologı́a para crear la red IXP, la estrategia de ataque usando SAR (Sección 4). Las conclusiones son presentadas en la sección 5. 2 Trabajo relacionado Para estudiar la robustez de una red, su evolución ante fallos debe ser analizada. En situaciones del mundo real las redes pueden enfrentarse tanto a fallas aleato- rias como ataques intencionales. Para esta última dos categorı́as principales de estrategias de ataque han sido definidas: ataques simultáneos y ataques secuenciales [HKYH02a]. Los ataques secuenciales sobre enlaces eligen un enlace a remover y dado el impacto de su remoción sobre la red, elige el siguiente. Este proceso Figure 1: Grafo de Peering continúa iterativamente hasta remover el número de enlaces deseado. El caso de nodos es análogo. Dentro de Internet, peering corresponde al contrato Los ataques secuenciales han sido estudiados a entre dos sistemas autónomos (SAs) que acuerdan in- fondo para analizar la robustez en redes. Holme et tercambiar rutas de tráfico a través de un enlace fı́sico. al. probó estrategias de ataques simultáneos y secuen- [DD10] presenta que el core de Internet es una jer- ciales usando medidas de centralidad como grado y arquı́a multi-tier de proveedores de tránsito (Transit betweenness. Providers o TPs) donde aproximadamente 10-20 de los Betweenness [BMSBJ12] es una métrica que deter- tier-1 TPs, presentes en muchas regiones geográficas, mina la importancia de un arco de acuerdo a la can- están conectadas a un clique de enlaces de peering. tidad de caminos mı́nimos que pasan a través de él. Los ISPs (tier-2) son consumidores de los TPs de tier- Betweenness ha sido estudiada como métrica de ro- 1 y a su vez los proveedores de residencias o pequeñas bustez para la capa de ruteo [SHS+ 11], como métrica empresas (tier-3) corresponden a los TPs de tier-2. de robustez para redes complejas [IKSW13] y para re- A través de peeringdb.com recolectamos los sis- des de sistemas autónomos de Internet [MKF+ 06], en- temas autónomos de cada Punto de Intercambio de In- tre otros. Betweenness ha sido ampliamente estudi- ternet (Internet Exchange Point, IXP) y los definimos ado y estandarizado como base de comparación para como nodos del grafo. De esta forma un SA podrı́a métricas de robustez. Por estas razones en este estudio pertenecer a diferentes IXPs y un IXP podrı́a tener será utilizada para comparar desempeño. múltiples SAs. Luego, conectamos los nodos medi- Más recientemente [VA15] estudió ataques secuen- ante un arco si cumplen al menos una de las siguientes ciales multi-estrategia usando múltiples medidas de ro- reglas: SAs conectados fı́sicamente que intercambian bustez, incluyendo la Unique Robustness Measure o tráfico, SAs que pertenecen a un mismo IXP, SAs que Medida Única de Robustez (R-index) [SMA+ 11]. pertenecen a una misma instalación. Donde los IXP son considerados como peering público y las intalaciones como peering privado. La figura 1 muestra el grafo resultante, este tiene 522 nodos y 14.294 arcos (los arcos naranjos represen- tan peering público, los arcos azules peering privado y los verdes conexión directa por red). La red resul- tante tiene un core bien conectado con algunos nodos aislados en su borde. 4 Ratio de Disponibilidad de Sumin- istro (Supply Availability Ratio) En 2013 se reportó que que Google poseı́a el 40% del tráfico de Internet1 . En consecuencia, dada las Figure 2: Supply Availability Ratio o Ratio de polı́ticas de peering de Google2 y sus polı́ticas para Disponibilidad de Suministro interconectar datacenters [JKM+ 13], podemos estu- diar Internet como una red de suministro adaptando Con esta estrategia el adversario es capaz de de- la métrica SAR presentada en [ZKY11]. sconectar la mitad de la red removiendo apenas un 20% de los arcos, más de un 30% de los nodos luego 1. Supply Availability Ratio (SAR): Porcentaje de remover un 10% de los arcos y un 10% de los nodos de sistemas autónomos que tiene acceso a Google luego de remover un 1% de los arcos. a través de al menos uno de sus SAs. Además, hemos considerado Internet como una red Cabe observar que Google ha delegado algunos ser- de suministro donde Google es el principal proveedor vicios a sistemas autónomos de ISPs [CFH+ 13], sin de contenido y proponemos estudiar la robustez del embargo éstos eventualmente deben conectarse con el backbone de Internet a través del Supply Availability backbone de Google para actualizarse. Ratio (SAR). Dado que en nuestro contexto SAR se Utilizando una estrategia de ataque basada en be- define como el porcentaje de sistemas autónomos que tweenness (ver trabajo relacionado) calculamos SAR tiene acceso a Google a través de al menos uno de sus para distintos porcentajes de arcos removidos. Los re- SAs, SAR presenta gran concordancia con el tamaño sultados son presentados en la Figura 2. fraccional de la componente conexa más grande pues El Ratio de Disponibilidad de Suministro presenta dicha componente siempre posee un SA de Google y, una alta relación con el tamaño fraccional de la com- por lo tanto, los nodos de la componente conexa más ponente conexa más grande, la cual, en este estudio, grande siempre tienen acceso a google. incluye al menos un SA de los dos SAs presentes de Como trabajo futuro se planea extender el uso Google (marcados en rosado en le figura 1, AS15169 de medidas de suministro que consideren otros en el centro de la red y AS36040 en la orilla de la red). parámetros de la red, de forma de obtener una visión Se debe notar que para un usuario dentro del core completa del estado de la red. de la red el principal proveedor de contenidos siempre existe y por lo tanto, para él, no hay indicios de que References la red se esté desarmando (o perdiendo a la mitad de sus miembros como es el caso luego de remover 20% [BFBS05] Paolo Buccirossi, Laura Ferrari Bravo, de sus arcos). Sin embargo la realidad es otra: luego and Paolo Siciliani. Competition in the de desconectar solo un 5% de la red uno de los SAs de internet backbone market. World Com- Google queda aislado, mostrando que en este punto la petition, 28(2):233–252, 2005. red está siendo mantenida únicamente por AS15169. [BMSBJ12] Nicolás Ignacio Bersano-Méndez, 5 Conclusiones y trabajo futuro Satu Elisa Schaeffer, and Javier Bustos- Jiménez. Metrics and models for social En este artı́culo hemos presentado qué tan robusto networks. In Computational Social serı́a el backbone de Internet (la red de SAs de peering) Networks, pages 115–142. Springer, 2012. si un adversario escogiera sabiamente que enlace va a cortar. Siguiendo recomendaciones, el enlace elegido [BRSBJ15] I. Bachmann, P. Reyes, A. Silva, and serı́a aquel con mayor betweenness. J. Bustos-Jimenez. Miuz: measuring the 1 Ver el artı́culo de Forbes en http://goo.gl/aHdeiN impact of disconnecting a node. In Inter- 2 Ver https://peering.google.com/#/options/peering. national Conference of the Chilean Com- puter Science Society, pages 1–6, Nov [MKF+ 06] Priya Mahadevan, Dmitri Krioukov, Ma- 2015. rina Fomenkov, Xenofontas Dimitropou- los, Amin Vahdat, et al. The inter- [CFH+ 13] Matt Calder, Xun Fan, Zi Hu, Ethan net as-level topology: three data sources Katz-Bassett, John Heidemann, and and one definitive metric. ACM SIG- Ramesh Govindan. Mapping the expan- COMM Computer Communication Re- sion of google’s serving infrastructure. view, 36(1):17–26, 2006. In Proceedings of Internet Measurement Conference, pages 313–326. ACM, 2013. [MR06] Wojciech Molisz and Jacek Rak. End- to-end service survivability under attacks [CSR+ 15] Yi-Ching Chiu, Brandon Schlinker, Ab- on networks. Journal of Telecommunica- hishek Balaji Radhakrishnan, Ethan tions and Information Technology, pages Katz-Bassett, and Ramesh Govindan. 19–26, 2006. Are we one hop away from a better inter- [RW10] Jacek Rak and Krzysztof Walkowiak. net? In Proceedings of Internet Measure- Survivability of anycast and unicast flows ment Conference, pages 523–529. ACM, under attacks on networks. In Ultra 2015. Modern Telecommunications and Control Systems and Workshops, pages 497–503. [DD10] Amogh Dhamdhere and Constantine IEEE, 2010. Dovrolis. The internet is flat: Modeling the transition from a transit hierarchy to [SHS+ 11] Paul Smith, David Hutchison, James PG a peering mesh. In Proceedings of Co- Sterbenz, Marcus Scholler, Ali Fessi, NEXT, pages 21:1–21:12, New York, NY, Merkouris Karaliopoulos, Chidung Lac, USA, 2010. ACM. and Bernhard Plattner. Network re- silience: a systematic approach. Commu- [HKYH02a] Petter Holme, Beom Jun Kim, Chang No nications Magazine, IEEE, 49(7):88–97, Yoon, and Seung Kee Han. Attack vul- 2011. nerability of complex networks. Physical Review E, 65(5):056109, 2002. [SMA+ 11] Christian M Schneider, André A Mor- eira, José S Andrade, Shlomo Havlin, [HKYH02b] Petter Holme, Beom Jun Kim, Chang No and Hans J Herrmann. Mitigation of Yoon, and Seung Kee Han. Attack vul- malicious attacks on networks. Proceed- nerability of complex networks. Physical ings of the National Academy of Sciences, Review E, 65(5):056109, 2002. 108(10):3838–3841, 2011. [SSYS10] Ali Sydney, Caterina Scoglio, Mina [IKSW13] Swami Iyer, Timothy Killingback, Bala Youssef, and Phillip Schumm. Charac- Sundaram, and Zhen Wang. Attack ro- terising the robustness of complex net- bustness and centrality of complex net- works. International Journal of Inter- works. PloS one, 8(4):e59613, 2013. net Technology and Secured Transactions, 2(3-4):291–320, 2010. [JKM+ 13] Sushant Jain, Alok Kumar, Subhasree Mandal, Joon Ong, Leon Poutievski, Ar- [VA15] Mario Ventresca and Dionne Aleman. jun Singh, Subbaiah Venkata, Jim Wan- Network robustness versus multi-strategy derer, Junlan Zhou, Min Zhu, et al. sequential attack. Journal of Complex B4: Experience with a globally-deployed Networks, 3(1):126–146, 2015. software defined wan. ACM SIG- [ZKY11] Kang Zhao, Akhil Kumar, and John Yen. COMM Computer Communication Re- Achieving high robustness in supply dis- view, 43(4):3–14, 2013. tribution networks by rewiring. Engineer- ing Management, IEEE Transactions on, [LIJM+ 11] Craig Labovitz, Scott Iekel-Johnson, 58(2):347–362, 2011. Danny McPherson, Jon Oberheide, and Farnam Jahanian. Internet inter- domain traffic. ACM SIGCOMM Com- puter Communication Review, 41(4):75– 86, 2011.