Confiabilidad diámetro acotada para el modelo hostil. Construcción de estrategias de selección de cortes minimales para el método de la reducción recursiva de la varianza

Abstract

Los Sistemas Binarios Estocásticos (SBS por sus siglas en inglés) son modelos matemáticos que permiten generalizar la noción clásica de confiabilidad de redes de comunicación. Los SBS consisten en un conjunto finito de componentes sujetos a fallas aleatorias, y una función lógica que describe la operación o falla del sistema, para cada estado posible de sus componentes. Instancias particulares de estos problemas pueden ser modelados bajo funciones monótonas, clasificándolos como Sistemas Binarios Estocásticos Monótonos (SMBS), los cuales heredan el orden natural del producto cartesiano. En el marco de Internet e inspirado en aplicaciones sensibles a la latencia, el problema de Confiabilidad Diámetro Acotado analiza la probabilidad de que dos o más nodos que desean comunicarse estén conectados por caminos acotados, ante fallas en los elementos de la red. Este problema ha sido estudiado principalmente en estructuras de redes donde fallan únicamente aristas o únicamente fallan nodos, y no tanto en fallas conjuntas (o "fallas simultáneas" de nodos y aristas). El problema de Confiabilidad Diámetro Acotada para el modelo hostil es una instancia de los sistemas binarios estocásticos monótonos, y la complejidad de su evaluación se clasifica como NP-difícil. Las contribuciones de este documento son las siguientes. En primera instancia se implementa el método de Reducción Recursiva de la Varianza (RVR) para el cálculo de Confiabilidad Diámetro Acotada del modelo hostil. Se realiza un estudio de sensibilidad del método RVR ante distintas estrategias de selección de cortes minimales. Finalmente, se brinda un estudio comparativo entre el método Monte Carlo Crudo y RVR, observando el desempeño de los métodos elegidos.

Stochastic Binary Systems (SBS) are mathematical models that allow extend the classical notion of reliability in communication networks. An SBS consists of a set of finite components subject to random failures, and a logical function that describes the operation or failure of the system, for each possible configuration. Particular instances of these problems are modeled under monotone functions, known as Stochastic Monotone Binary System (SMBS), which inherit the natural order of the cartesian product. Within the framework of the Internet and inspired by latency-sensitive applications, the Diameter Constrained Reliability is the probability that two or more target nodes are connected by bounded paths, in the resulting network after potential failures on its components. The scientific literature considers structural links or node failures. Here, we consider joint failures instead, what is known as the Hostile Network model. The Diameter Constrained Reliability problem for the hostile model is an instance of Stochastic Monotone Binary System, and its reliability evaluation belongs to the N P-Hard class. The contributions of this thesis can be summarized as follows. First, the Recursive Variance Reduction (RVR) method is implemented to estimate the Diameter Constrained Reliability in this novel hostile environment with joint node/link failures. Then, a sensibility analysis of RVR method is performed, following different cut-selection strategies. Finally, a performance analysis between Monte Carlo Crudo and RVR methods is provided.