En este proyecto se ha estudiado la técnica de Reducción Recursiva de la Varianza aplicada al cálculo de confiabilidad en redes. Se ha implementado el modelo para la representación de grafos estocásticos en lenguaje C++, y 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 han generado casos de prueba para la validación y comparación de la eficiencia de los algoritmos. También se ha integrado el trabajo realizado a la herramienta HEIDI y se ha construído un sitio web para la difusión de los resultados.

Algoritmos

Las principales conclusiones con respecto a los algoritmos extraídas de las pruebas son las siguientes:

• El algoritmo GCE admite una implementación sencilla y da resultados exactos, pero resulta prohibitivo en términos de tiempo de ejecución para redes de tamaño medio-grande (su orden de complejidad es exponencial en la cantidad de componentes de la red). Para redes pequeñas (confiables o no) es sin dudas la opción más adecuada.
• El algoritmo MCC también admite una implementación sencilla y da resultados razonablemente precisos para redes de confiabilidad medio-baja. El orden de complejidad del algoritmo es lineal con respecto a la cantidad de componentes de la red. Para redes muy confiables (cualquiera sea su tamaño) deben realizarse gran cantidad de replicaciones para obtener resultados aceptables, por lo que el tiempo de ejecución aumenta en función de la confiabilidad de la red. Por lo tanto, este algoritmo es adecuado para redes de cualquier tamaño y confiabilidad medio-baja.
• El algoritmo RVR no es tan sencillo de implementar (se deben tener en cuenta algunas sutilezas e implementar varias funciones auxiliares). Los resultados son más precisos que para MCC (básicamente la varianza es menor) pero los tiempos de ejecución son mayores (el orden de complejidad es cuadrático en la cantidad de componentes de la red). Este algoritmo es adecuado para el cálculo de confiabilidad en redes muy confiables de cualquier tamaño (si bien para redes grandes los tiempos de ejecución son bastante mayores que para MCC, no son imposibles como en GCE).

Para la generación de los casos de prueba se utilizó el editor gráfico de la herramienta HEIDI, donde se pudo apreciar la ventaja de contar con este tipo de herramientas.

Las pruebas se realizaron en entorno Unix, utilizando scripts que realizaban los cálculos para las distintas topologías y conjuntos de valores de confiabilidades en componentes. Los resultados se almacenaron en archivos de texto con determinado formato, que luego se procesaron en la herramienta Microsoft Excel. En relación a dicho procesamiento de datos se advirtió la necesidad de contar con una herramienta automatizada (que realizara cálculos de errores, confección de gráficos y otros), ya que se debieron realizar varias veces las mismas pruebas con un relativamente grande volumen de datos, lo que involucraba gran cantidad de tareas repetitivas que insumieron una importante cantidad de tiempo.

También se ha integrado el trabajo realizado a la herramienta HEIDI y se ha construido un sitio web para la difusión de los resultados obtenidos. Con respecto a la integración con HEIDI, se aprecia el hecho de contar con un diseño de módulos adecuado para realizar extensiones, ya que se requirió de relativamente poco trabajo para lograr la integración de los nuevos algoritmos a la herramienta. En relación a la construcción del sitio web, se apreciaron las facilidades del lenguaje Perl para la manipulación de textos; el mismo se utilizó en la construcción del servidor de cálculo, tanto para procesar los datos de entrada como para la generación de los scripts que realizan los cálculos y envían los resultados.

Los trabajos futuros interesantes, básicamente se distribuyen en los siguientes grupos:

Implementaciones de los algoritmos

El algoritmo GCE admite dos mejoras importantes:

• Llevar el cálculo de la probabilidad del subgrafo (o estado de la red) acumulado y modificarlo en cada invocación (ya que lo único que varía es la presencia o no de un componente). Esto evitará la invocación a la función que calcula la probabilidad del subgrafo en cada estado generado de la red.
• Se pueden agregar predicados de poda al algoritmo de Backtracking utilizado, de forma de no examinar ciertos estados para los cuales se puede predecir que no son operativos.

• Si en la ejecución de varias replicaciones del algoritmo se han recorrido todos los caminos desde la raíz del árbol de la computación hasta alguna hoja (ver ejemplo de RVR) no es necesario seguir ejecutando más replicaciones. Se puede entonces controlar esta condición de forma de no realizar replicaciones innecesarias.
• Para el caso particular de la medida R_st y para algunas topologías particulares se podría mejorar la performance del algoritmo condicionando el cálculo a un camino s-t y no a un corte. Esto se puede ver observando que la varianza de la variable aleatoria utilizada para estimar la medida Q es igual a (Q(G) - Q_D)R(G), por lo que la reducción de la varianza está directamente ligada a la probabilidad de falla del corte extendido D. De forma análoga, en el cálculo de R_st condicionando a un camino s-t, la reducción de varianza está ligada a la probabilidad de funcionamiento de dicho camino. Por lo observado anteriormente, para el caso particular del cálculo de la medida R_st, se puede evaluar el uso de un condicionamiento por cortes o por caminos, dependiendo de las probabilidades del corte "menos confiable" y del camino "más confiable".

En este trabajo se comparó la performance del algoritmo RVR frente a los algoritmos GCE y MCC, y algunos resultados se compararon con los obtenidos mediante otros algoritmos en otros trabajos. En una etapa posterior sería útil realizar una comparación más completa frente a otros algoritmos, por ejemplo utilizando los datos encontrados en [19].

HEIDI, automatización de pruebas y sitio web

Las mejoras que admite la herramienta HEIDI tienen que ver básicamente con su interfase gráfica:

• Actualización de los componentes utilizados (menúes, botones y cajas de texto) a los del nuevo entorno gráfico.
• Utilización del botón derecho del mouse en el editor, para realizar algunas acciones tales como cambiar las propiedades de nodos y aristas.
• Agrupación de componentes en una red mediante ventanas.

La principal mejora a incorporar al sitio web tiene que ver con el servidor de cálculo, al cual podría integrarse un editor gráfico (similar al de HEIDI) que permita dibujar la red, asignar valores a los componentes y marcar nodos terminales. Este editor puede construirse como un applet en lenguaje Java, el que sustituiría a la actual caja de texto donde debe ingresarse el texto del caso en formato de exportación/importación de HEIDI (que de no disponer el usuario de tal herramienta, debe generarlo de forma manual).