Robustez de la red óptica chilena

Introducción

En esta charla, el Dr. Javier Bustos nos presentó su trabajo sobre la mejora en la robustez de la red óptica chilena, propuesta presentada a la Subsecretaría de Telecomunicaciones de Chile (SUBTEL) en el marco del proyecto Yafün. Este trabajo surge a raíz de la necesidad de mejorar la infraestructura digital en el país ante los desastres naturales que afectan cada año. Entre los alcances del proyecto estuvo la documentación de los caminos principales, secundarios y comunas, además del cálculo de métricas de resiliencia y aplicación de metodologías de optimización matemática.

Resumen

El Dr. Javier Bustos comenta que al inicio del proyecto fue necesario definir robustez en la red, lo que la SUBTEL entendía como: “Si se cae la conexión, ¿cuál es el porcentaje de red afectada? o ¿cuántos quedarían aislados al servicio?”. La idea de SUBTEL era tener un sistema dividido en cuatro componentes: analizador de robustez, análisis rápido de los datos, la cantidad de dinero que se necesitaba invertir y consultas online que debían ser respondidas rápidamente.

El proyecto tenía como información el mapa de la fibra óptica nacional, mapas de caminos, rutas de ferry y mapas de red eléctrica, por los cuales sería posible instalar la fibra. Por otra parte, Chile se divide en regiones, cada región se divide en provincias, y a su vez, las provincias se dividen en comunas. A partir de esto, quedó definida la robustez del servicio como la interconexión de dos comunas con por lo menos dos caminos disjuntos. Una vez teniendo la información de las posibles trayectorias de la fibra, un primer intento de obtención de la solución fue calcular las rutas o caminos entre cada par de comunas, de las 346 existentes, con la ayuda del algoritmo de Dijkstra, en una primera ejecución se encontró la ruta más corta entre dos comunas; posteriormente se quitaba esta ruta de la red y se ejecutaba nuevamente el algoritmo, encontrándose de esta manera una segunda ruta; sin embargo, en esta primera solución se presentaron algunos inconvenientes como, los elevados costos de agregar líneas debido a la gran cantidad de caminos encontrados en la solución, los cuales fueron 78,209 caminos, además era necesario verificar si los caminos propuestos eran factibles o viables, ya que en algunos casos no era posible la conexión entre comunas y hacía necesario ejecutar el algoritmo nuevamente.

Debido a la necesidad de encontrar una mejor solución, se reformuló el problema con una matriz de incidencia más pequeña, también se definió una nueva métrica de robustez en la que cada comuna debía estar conectada de forma disjunta con otras dos comunas. El nuevo problema fue planteado con programación entera y fue resuelto con el motor de optimización CPLEX, el método encontró una solución con una cobertura del 76.6% de conectividad de las comunas, que si bien era una solución mejor que la primera, dejaba sin los beneficios de robustez a algunas zonas alejadas de por ejemplo, Santiago y sus alrededores.

Con el objetivo de mejorar la solución actual y al tener algunas limitaciones de la propuesta hecha con la solución simplificada, como lo es el que no siempre se podían tomar las dos rutas más cortas o que simplemente al eliminar la primera ruta encontrada, el grafo resultante era disconexo, se implementó el algoritmo de Suurballe & Tarjan, buscando encontrar un óptimo a la primera definición de robustez, este algoritmo generó una gran componente conectada que cumple con los criterios de robustez originales y además es un 27% más barata. Sin embargo, a pesar que la solución simplificada era un poco más cara, tenía algunas ventajas, por ejemplo los caminos se desviaban de rutas más propensas a desastres naturales, lo que la hacía más robusta la solución.

Conclusiones

Al comparar la solución simplificada propuesta con la solución óptima encontrada con el algoritmo de Suurballe & Tarjan, se encontró que la primera solución se desviaba un poco de la ruta de red óptica existente en el país, por lo que resulta ser más costosa en comparación con la solución óptima previamente encontrada, la cual se ajusta más a la red, sin embargo, resultó ser más robusta y confiable ante los eventos naturales que afectan al país. El Dr. Bustos nos menciona que se sigue trabajando en el desempeño del algoritmo y la definición de otras métricas que evalúen la solidez del sistema enfatizando en que los métodos utilizados deberían de alguna manera considerar la vulnerabilidad ante los frecuentes desastres naturales que afectan al país.

Ligas de interés

• Internet Resilience [GITHUB]
• Space Geometry Effect over the Internet as a Physical-Logical Interdependent Network [EN LÍNEA]
• Suurballe's algorithm [WIKIPEDIA]
• EA Survey on Frameworks Used for Robustness Analysis on Interdependent Networks". [EN LÍNEA]
• Analyzing the Robustness of the Chilean Optical Network. [PDF]
• Measuring and Improving Network Robustness: A Chilean Case Study. [EN LÍNEA]
• Improving the Chilean Internet Robustness: Increase the Interdependencies or Change the Shape of the Country? [EN LÍNEA]