Método RVR en la simulación de medidas de confiabilidad en redes

Abstract

Una red está compuesta por un conjunto de nodos y un conjunto de aristas que comunican pares de nodos. La confiabilidad de una red es una medida que refleja la capacidad de la misma de continuar operativa frente a posibles fallos de algunos de sus componentes, y se define como la probabilidad de comunicación exitosa entre cierto conjunto de nodos de la red, dadas las probabilidades de funcionamiento de los componentes y la topología de la red. La evaluación exacta de esta medida es un problema NP-difícil, por lo que los algoritmos de cálculo exacto se hacen impracticables para redes de tamaño considerable. Una alternativa es utilizar métodos de simulación y en particular el método Monte Carlo. El algoritmo Monte Carlo estándar, directo o crudo requiere de un gran esfuerzo computacional para lograr estimaciones precisas en redes muy confiables. Por este motivo es de interés el estudio de algoritmos denominados de reducción de varianza. En este trabajo se estudia en particular la técnica de Reducción Recursiva de la Varianza aplicada al cálculo de confiabilidad en redes. Se realiza un estudio comparativo de tres algoritmos: el algoritmo exacto de Generación Completa de Estados y los algoritmos estimativos Monte Carlo Crudo y Reducción Recursiva de la Varianza. Se presentan los detalles de implementación de los algoritmos, los casos de prueba seleccionados para su testeo y los resultados numéricos obtenidos, así como las conclusiones extraídas a partir de los mismos. También se muestra la incorporación de las implementaciones realizadas a la herramienta HEIDI y la construcción de un sitio web para la difusión de este trabajo.