Título: Splitting aplicado a la Estimación de Confiabilidad de Redes

Marco de Trabajo: Doctorado

Área de desarrollo: Investigación Operativa

Autor: Leslie Murray

Contacto: leslie@eie.fceia.unr.edu.ar

Día: LUNES

Hora: 10:45

Palabras Claves: confiabilidad, redes, splitting

Resumen:
Director Dr. Héctor Cancela - InCo UDELAR

El cálculo exacto de la confiabilidad (o anticonfiabilidad) de una red, definida como la probabilidad de que haya conectividad entre los nodos de un determinado subconjunto del total cuando sólo los enlaces fallan con probabilidades conocidas, pertenece a la clase de problema NP-duro. Las técnicas de simulación Monte Carlo son por lo tanto una eficiente alternativa para evitar este tipo de cálculo y realizar, en su lugar, estimaciones.
Si la red bajo análisis es altamente confiable, una estimación de su anticonfiabilidad arrojará valores muy cercanos a cero. Siendo Q el verdadero valor de anticonfiabilidad y Qe una estimación del mismo, la calidad de dicha estimación puede evaluarse mediante el coeficiente de variación SD(Qe)/E(Qe) visto como error relativo (SD() indica desviación estándar y E(), valor esperado). En las variantes de Monte Carlo crudas o estándar, el error así definido crece a medida que la red se se hace más confiable. Además este error es inversamente proporcional al número de replicaciones, por lo que para alcanzar valores bajos de error (elevada precisión) se hace necesario ejecutar un elevado, a veces inalcanzable, número de replicaciones. Existe una gran número de variantes de simulación, cuya finalidad es superar la eficiencia del algoritmo crudo o estándar. En general estas variantes procuran lograr una reducción de la varianza del estimador y, con ella, un incremento en la precisión de las estimaciones.
Splitting es una técnica de reducción de varianza aplicada con gran éxito en la simulación de sistemas markovianos. En el presente trabajo se aplica a la estimación de confiabilidad de redes, contexto en el que no ha sido aplicado hasta el momento. Se presenta un modelo de redes, luego se comentan brevemente los principios fundamentales de Splitting, se muestra seguidamente una adaptación de Splitting al el modelo de redes presentado y finalmente se muestran los resultados de una serie de experimentos realizados sobre diversas topologías de red, a fin de evaluar el rendimiento de la implementación propuesta. Se cierra el trabajo con las conclusiones y con algunas consideraciones acerca del trabajo futuro vinculado a esta implementación.