Este trabajo trata sobre el tema confiabilidad en redes. Las entidades relevantes en una red son nodos y conexiones entre nodos, y en general el principal objetivo buscado es lograr una comunicación segura entre nodos de la red. Las aplicaciones de modelos de redes se dan en los siguientes contextos:

• Redes telefónicas y de comunicación de datos.
• Redes de transporte.
• Arquitecturas de computadores.
• Redes de energía eléctrica.
• Sistemas de comando y control.

1. Dado un conjunto de nodos que se desean comunicar entre sí, obtener una red óptima en algún sentido (por ejemplo, obtener la máxima cantidad posible de caminos distintos entre pares de nodos), sujeto a determinadas restricciones (por ejemplo, costo de conexión entre pares de nodos).
2. Dada una red, evaluar de algún modo su confiabilidad (en el sentido de la comunicación entre nodos). Este tipo de problemas están fuertemente relacionados con problemas del tipo 1, donde en el proceso de búsqueda de la red óptima se deben comparar las confiabilidades de dos redes para escoger la mejor, o luego de obtener un resultado a partir de cierto procedimiento se debe evaluar su confiabilidad.

Cabe aclarar que el modelo utilizado se adecua a realidades donde la información a comunicarse entre dos nodos se rutea de forma dinámica a través de la red. Esto significa que si bien puede existir un camino predeterminado para comunicar dos nodos, se puede escoger un camino alternativo en caso de falla de algún componente intermedio del camino predeterminado (pensar en el ruteo de paquetes entre dos hosts de Internet). Se dejan de lado detalles como el control de congestión y retrasos en la comunicación (problemas clásicos en redes de datos y de transporte; ver análisis de performabilidad en [2]).

Al trabajar con nodos y conexiones entre nodos, para la construcción de un modelo formal se utilizan grafos (en lo que sigue se utilizarán las palabras red y grafo como sinónimos). En particular interesa definir una medida (o índice) de confiabilidad para una red, que esté basada en su topología y en la confiabilidad de sus componentes. La forma de obtener dichos índices varía dependiendo de los datos con que se cuente. Un dato imprescindible es el referente a la topología de la red, pero según se cuente o no con datos sobre las confiabilidades elementales de los componentes, se pueden adoptar dos enfoques (ver [1]):

• Solidez o resistencia a fallos: Es un índice calculado en base a parámetros usuales de grafos (cintura, cohesión, conectividad y otros). Se asume que todos los componentes son idénticos desde el punto de vista de sus eventuales fallos, por lo que este enfoque es útil cuando no se cuenta con información acerca de la confiabilidad de cada componente por separado (ver [21]).
• Confiabilidad: Se calcula la probabilidad de funcionamiento de la red en base a las confiabilidades elementales de cada componente, dadas mediante probabilidades de funcionamiento de los mismos.

• R_v (confiabilidad global): Probabilidad de existencia de por lo menos un camino entre todo par de nodos del grafo.
• R_st (confiabilidad fuente-terminal): Probabilidad de existencia de por lo menos un camino entre los nodos s y t.
• R_k (confiabilidad entre terminales): Probabilidad de existencia de por lo menos un camino entre todo par de nodos del subconjunto K de nodos (denominados terminales).

• Q_v = 1 - R_v
• Q_st = 1 - R_st
• Q_k = 1 - R_k

Los cálculos exactos de estas medidas son problemas NP-difíciles, por lo tanto, no se conocen algoritmos de orden polinómico en la cantidad de componentes del grafo para resolverlos. Existen algoritmos exactos eficientes para tipos particulares de redes, pero en el caso general los métodos exactos se hacen impracticables por sus excesivos tiempos de ejecución, para redes relativamente grandes. Una alternativa es utilizar métodos de simulación. La opción más simple es utilizar el método Monte Carlo estándar o crudo como forma de simular el comportamiento estocástico del sistema. En el contexto del cálculo de confiabilidad en redes, el método Monte Carlo crudo consiste en sortear un estado del grafo (equivalente a sortear el funcionamiento de sus nodos y aristas) y verificar su conexidad (o la condición que defina a la red como operativa o funcionando correctamente). Realizando varias replicaciones del mismo experimento, se obtiene una estimación de la medida requerida como la frecuencia de aparición del suceso "la red se encuentra en estado operativo". La desventaja importante de este método es la excesiva varianza de las estimaciones (que como consecuencia aumenta el tamaño del intervalo de confianza), lo que hace que sus resultados sean poco precisos. En particular esto se da para redes de alta confiabilidad, donde se hace necesario realizar un número considerable de replicaciones para obtener estados de falla o no operativos. Esto motiva el estudio de métodos de reducción de la varianza para la simulación de medidas de confiabilidad. En particular, en este trabajo se estudia el método de reducción recursiva de la varianza (RVR, siglas en inglés de "recursive variance reduction"). El mismo surge como una alternativa dentro de la familia de algoritmos de reducción de varianza, donde para los ya conocidos (ver estado del arte en [19]), se observan las siguientes características:

• Utilización excesiva de memoria.
• Excesivo tiempo de ejecución (ya sea por la complejidad del algoritmo o por los tiempos de pre-procesamiento requerido en algunos).
• Buena performance solo para algunas clases de topologías y valores particulares de confiabilidades elementales de los componentes.