Topological optimization of fault-tolerant networks meeting reliability constraints.

Abstract

The relevant entities in a network are its nodes, and the links between them. In general, the goal is to achieve a reliable communication between dierent pairs of nodes. Examples of applications are telephonic services, data communication, transportation systems, computer systems, electric networks and control systems. The predominant criterion for the design of a reliable and survivable system is the minimum-cost in most contexts. An attractive topic for research is to consider a minimum-cost topological optimization design meeting a reliability threshold. Even though the cost has been the primary factor in the network design, recently, the network reliability has grown in relevance. With the progress of Fiber-To-the-Home (FTTH) services for the backbone design in most current networks, combined with the rapid development of network communication technologies, and the explosive increase of applications over the Internet infrastructure, the network reliability has supreme importance, for traditional communication systems but for the defense, business and energy, and emergent elds such as trusted computing, cloud computing, Internet of Things (IoT) and Next Generation Networks (NGN), the fault tolerance is critical. We can distinguish two main problems to address in the analysis and design of network topologies. First, the robustness is usually met under multi-path generation. Therefore, we require certain number of node-disjoint paths between distinguished nodes, called terminals. The second problem is to meet a minimum-reliability requirement in a hostile environment, using the fact that both nodes and links may fail. Both problems are strongly related, where sometimes the minimum-cost topology already meets the reliability threshold, or it should be discarded, and the design is challenging. This thesis deals with a topological optimization problem meeting reliability constraints. The Generalized Steiner Problem with Node-Connectivity Constraints and Hostile Reliability (GSP-NCHR) is introduced, and it is an extension of the well-known Generalized Steiner Problem (GSP). Since GSP-NCHR subsumes the GSP, it belongs to the class of N P-Hard problems. A full chapter is dedicated to the hardness of the GSP-NCHR, and an analysis of particular sub-problems. Here, the GSP-NCHR is addressed approximately. Our goal is to meet the topological x requirements intrinsically considered in the GSP-NCHR, and then test if the resulting topology meets a minimum reliability constraint. As a consequence a hybrid heuristic is proposed, that considers a Greedy Randomized construction phase followed by a Variable Neighborhood Search (VNS) in a second phase. VNS is a powerful method that combines local searches that consider dierent neighborhood structures, and it was used to provide good solutions in several hard combinatorial optimization problems. Since the reliability evaluation in the hostile model belongs to the class of N P-Hard problems, a pointwise reliability estimation was adopted. Here we considered Recursive Variance Reduction method (RVR), since an exact reliability evaluation is prohibitive for large-sized networks. The experimental analysis was carried out on a wide family of instances adapted from travel salesman problem library (TSPLIB), for heterogeneous networks with dierent characteristics and topologies, including up to 400 nodes. The numerical results show acceptable CPU-times and locally-optimum solutions with good quality, meeting network reliability constraints as well.

En una red las entidades relevantes son nodos y conexiones entre nodos, y en general el principal objetivo buscado es lograr una comunicación segura entre nodos de esta red, ya sea para redes telefónicas y de comunicación de datos, de transporte, arquitectura de computadores, redes de energía eléctrica o sistemas de comando y control. La optimización relativa al costo de una red y la contabilidad de la misma, relacionada con la supervivencia de esta, son los criterios predominantes en la selección de una solución para la mayor parte de los contextos. Un tema interesante que ha atraído un gran esfuerzo es cómo diseñar topologías de red, con un uso mínimo de recursos de red en términos de costo que brinde una garantía de contabilidad. A pesar que por años el costo ha sido el factor primario, la contabilidad ha ganado rápidamente en relevancia. Con sistemas de transmisión de fibra óptica de alta capacidad formando la columna vertebral de la mayoría de las redes actuales y junto con el rápido desarrollo de la tecnología de comunicación de redes y el crecimiento explosivo de las aplicaciones de Internet, la contabilidad de la red parece cada vez más importante, tanto para áreas tradicionales como la industria de defensa, finanzas y energía, y áreas emergentes como la computación contable, la computación en la nube, internet de las cosas (IoT) y la próxima generación de Internet, la supervivencia del tráfico por sobre los fallos de red se ha convertido aún en más crítica. En ese sentido podemos diferenciar, a grandes rasgos, dos de los principales problemas a resolver en el análisis y diseño de topologías de red. Primeramente la obtención de una red óptima en algún sentido, siendo este definido por ejemplo mediante la obtención de la máxima cantidad posible de caminos disjuntos entre pares de nodos, esto sujeto a determinadas restricciones definidas según el contexto. El segundo problema es la evaluación de la contabilidad de la red en función de las contabilidades elementales de los nodos y conexiones entre nodos que componen la red. Estas contabilidades elementales son probabilidades de operación asociadas a los nodos y conexiones entre nodos. Ambos problemas están fuertemente relacionados, pudiendo tener que comparar en el proceso de búsqueda de redes óptimas la contabilidad entre soluciones candidatas, o luego de obtener una solución candidata tener que evaluar la contabilidad de la misma y de esta forma descartarla o no. El presente trabajo se centra en la resolución del problema enfocado en ambos puntos planteados. Para ello modelamos el problema de diseño de la topología de red sobre la base de un modelo de nido como Generalized Steiner Problem with Node-Connectivity Constraints and Hostile Reliability (GSP-NCHR) extensión del más conocido Generalized Steiner Problem (GSP). El presente problema es NP-duro, dedicamos un capítulo para presentar resultados teóricos que lo demuestran. Nuestro objetivo es atacar de forma aproximada el modelo GSP-NCHR de tal modo de poder resolver la optimización de la red y luego medir la contabilidad de la solución obtenida. Para ello optamos por desarrollar la metaheurística Variable Neighborhood Search (VNS). VNS es un método potente que combina el uso de búsquedas locales basadas en distintas definiciones de vecindad, el cual ha sido utilizado para obtener soluciones de buena calidad en distintos problemas de optimización combinatoria. En lo referente al cálculo de contabilidad de la red, nuestro modelo GSP-NCHR pertenece a la clase NP-duro, por eso desarrollamos Recursive Variance Reduction (RVR) como método de simulación, ya que la evaluación exacta de esta medida para redes de tamaño considerable es impracticable. Las pruebas experimentales fueron realizadas utilizando un conjunto amplio de casos de prueba adaptados de la librería travel salesman problem (TSPLIB), de heterogéneas topologías con diferentes características, incluyendo instancias de hasta 400 nodos. Los resultados obtenidos indican tiempos de cómputo altamente aceptables acompañados de óptimos locales de buena calidad.