Introducción Informal

Modelos, Definiciones y Parámetros de Interés

Leslie Murray

Facultad de Ciencias Exactas, Ingeniería y AgrimensuraUniversidad Nacional de Rosario

Rosario, Argentina

Octubre, 2019

Modelos

El curso está basado en dos modelos de red:

Modelo Estático de Red

Cada enlace permite la conexiónentre los nodos en sus extremos.

El objetivo es garantizar la conexión,a través de caminos formados porenlaces sanos, entre nodos de undeterminado conjunto, a pesar de lasfallas

Red Estocástica de Flujo

Cada enlace permite el paso de unadeterminada cantidad de flujo.

El objetivo es garantizar el paso deuna determinada cantidad de flujo, através de enlaces sanos, desde unconjunto de nodos hacia otroconjunto de nodos.

Leslie Murray Introducción Informal 2 / 27

Modelo Estático de Red

• Una red se modela mediante un grafo:

“conjunto de nodos conectado a través de un conjunto de enlaces”.

• Los enlaces y los nodos pueden fallar.

• Es de interés garantizar la conexión entre los nodos a pesar de las fallas.

¿En qué consisten las fallas y qué se entiende por conexión entre los nodos?

Leslie Murray Introducción Informal 3 / 27

Tipo de Falla

• Vamos a abordar modelos en los que:

• las fallas sólo afectan a los enlaces,• la falla de cada enlace es independiente del estado de los demás.

• Reconoceremos dos estados posibles para cada enlace:

sano

fallado

• sano: garantiza la conexión perfecta entre los nodos en sus extremos.

• fallado: está completamente cortado (equivale a retirarlo del grafo).

Leslie Murray Introducción Informal 4 / 27

Modelo Probabilístico

• Si cada enlace está fallado con probabilidad conocida e independiente de la fallade los demás, es simple calcular la probabilidad de una configuración en la quealgunos enlaces están fallados y los demás, sanos.

Objetivo

Dadas las probabilidades de falla de los enlaces, evaluar la probabilidad de que la redsatisfaga algún criterio de conectividad.

Leslie Murray Introducción Informal 5 / 27

Criterio de Conectividad 1

• La red debe garantizar la conectividad entre todos los nodos que la componen.

• Deberán existir caminos de enlaces sanos que conecten “cualquier” par denodos.

Leslie Murray Introducción Informal 6 / 27

Criterio de Conectividad 2

• La red debe garantizar la conectividad entre todos los nodos de un conjunto(nodos terminales).

• Deberán existir caminos de enlaces sanos que conecten “cualquier” par denodos terminales.

Leslie Murray Introducción Informal 7 / 27

Criterio de Conectividad 3

s

t

• La red debe garantizar la conectividad entre dos nodos terminales.

• origen (s= source)• destino (t = target)

• Deberá existir al menos un camino de enlaces sanos que conecte s con t.

Leslie Murray Introducción Informal 8 / 27

Criterios de Conectividad

De aquí en más vamos a trabajar sobre elmodelo con dos nodos terminales, s y t.

La elección de uno u otro criterio de conectividad notiene un peso importante frente al problema a resolverni modifica sustancialmente las formas de resolverlo.

Leslie Murray Introducción Informal 9 / 27

Condición de Operatividad

s

t

• La red se considera operativa si, no obstante las fallas, existe un camino denodos sanos que conecta s con t.

• La red se considera fallada en caso contrario.

Leslie Murray Introducción Informal 10 / 27

Definición de Confiabilidad

s

t

• Dada la probabilidad de falla de cada enlace es posible determinar la probabilidadde que exista un camino de enlaces sanos entre s y t.

• Esa probabilidad es un indicador de la confiabilidad, ζ , de la red.

Confiabilidad, ζ

Dados dos nodos, s y t, la confiabilidad es la probabilidad de que exista un caminoformado por enlaces sanos entre ambos.

Leslie Murray Introducción Informal 11 / 27

Clase de Problema

s

t

• Si hay m enlaces, existen 2m combinaciones diferentes en cada una de lascuales los enlaces están en uno de sus dos estados posibles: sanos o fallados.

• A menos que se trate de una topología particular, los algoritmos conocidos paraevaluar ζ son de complejidad exponencial en el número de enlaces:

es necesario evaluar las 2m posibles configuraciones.

• Este problema pertenece a la clase NP–difícil (NP–hard), luego, es altamenteimprobable que exista una algoritmo de complejidad polinomial que lo resuelva.

Leslie Murray Introducción Informal 12 / 27

Ejemplo ilustrativo

Supóngase que un programa es capaz de simular una configuración y determinar si,para esa configuración s y t están conectados o no, en 10−9 seg., cualquiera sea elnúmero de enlaces de la red, m.

La siguiente tabla muestra los tiempos de ejecución de una rutina que evalúa las 2m

posibles configuraciones:

Número de Enlaces (m) Tiempo de Ejecución (2m× 10−9 seg.)

20 1 milisegundo25 34 milisegundos30 1 segundo35 34 segundos40 18 minutos45 10 horas50 13 días55 14 meses60 37 años65 12 siglos

Leslie Murray Introducción Informal 13 / 27

Metodología

• Para redes de tamaño mediano a grande la determinación de ζ mediantealgoritmos de cálculo exacto es inviable, cualquiera sea el criterio deconectividad.

• Una posible alternativa al cálculo exacto es la estimación mediante simulación.

• La estimación estándar consiste en generar “sólo algunas” configuraciones de lared, elegidas en forma aleatoria, y determinar la proporción de ellas en las quese garantiza la conectividad.

• Si la confiabilidad es extremadamente alta, en todas las configuracionesgeneradas las condiciones de conectividad serán satisfechas, por lo que laestimación de ζ resultará imposible o casi imposible.

• Este problema se resuelve mejorando el rendimiento de las simulacionesmediante técnicas de reducción de varianza.

Objetivo del curso

Estudiar métodos de simulación que permitan estimar eficientemente la confiabilidadde redes de gran tamaño, altamente confiables.

Leslie Murray Introducción Informal 14 / 27

Modelo de Red Estocástica de Flujo

• Algunos nodos generan flujo, otros reciben flujo y otros sólo le dan paso.

• Los enlaces son atravesados por flujo, en una única dirección, hasta un máximollamado capacidad.

• El conjunto de capacidades determina el máximo flujo que puede salir de losnodos que lo generan y llegar hasta los que lo reciben.

Leslie Murray Introducción Informal 15 / 27

Modelo de Red Estocástica de Flujo

• Dado un conjunto de capacidades de los enlaces, hay un máximo valor posiblede flujo, F , generado en un conjunto de nodos terminales que puede llegarhasta otro conjunto de nodos terminales.

• Las capacidades varían debido a fallas.

• La condición satisfactoria es que, a pesar de las fallas, F esté por encima decierta cota o límite, d, llamada demanda: F > d.

Leslie Murray Introducción Informal 16 / 27

Modelo de Red Estocástica de Flujo

s

t

• El razonamiento es idéntico para un modelo en el que un flujo, F , generado enun único nodo terminal, s, debe llegar hasta un único nodo terminal t.

Leslie Murray Introducción Informal 17 / 27

Cantidad de Nodos Terminales

De aquí en más vamos a trabajar sobre elmodelo con dos nodos terminales, s y t.

La elección de un número mayor de nodos terminales notiene un peso importante frente al problema a resolverni modifica sustancialmente las formas de resolverlo.

Leslie Murray Introducción Informal 18 / 27

Tipo de Falla

• Vamos a abordar modelos en los que:

• las fallas sólo afectan a los enlaces,• la falla de cada enlace es independiente del estado de los demás.

• Reconoceremos múltiples estados (valores de capacidad) para cada enlace:

c sano

c1 < c fallado

c2 < c1 fallado

cn = 0 fallado

......

• sano: el enlace está a máxima capacidad → c.

• fallado: la capacidad se reduce, eventualmente a cero → algún ci, i= 1, . . . ,n.

Leslie Murray Introducción Informal 19 / 27

Modelo Probabilístico

s

t

• Si cada valor de capacidad se da con una probabilidad conocida, es posiblecalcular la probabilidad de una configuración determinada por el valor decapacidad de cada enlace.

Objetivo

Dadas las probabilidades de cada valor de capacidad, evaluar la probabilidad de que lared satisfaga una cierta demanda de flujo.

Leslie Murray Introducción Informal 20 / 27

Condición de Operatividad

s

t

• La red debe garantizar que, a pesar de las fallas, el máximo valor posible de flujogenerado en s que puede llegar hasta t sea mayor que una cierta cota o límite.

Leslie Murray Introducción Informal 21 / 27

Definición de Confiabilidad

s

t

• Si se conoce la probabilidad con la que cada enlace asume un valor decapacidad, es posible determinar la probabilidad de que el máximo flujo posible,F , desde s hacia t sea mayor que una cierta cota o límite d: F > d

• Esa probabilidad es un indicador de la confiabilidad, ζ , de la red.

Confiabilidad, ζ

La confiabilidad es la probabilidad de que el máximo flujo generado en s que puedellegar hasta t sea mayor que una cierta cota o límite, d.

Leslie Murray Introducción Informal 22 / 27

Clase de Problema

s

t

• Si hay m enlaces que pueden asumir, respectivamente, N1, N2, . . ., Nm valores decapacidad, existen N1×N2× . . .×Nm combinaciones diferentes en cada una delas cuales los enlaces están en uno de sus estados posibles.

• Si todos los enlaces admiten N valores de capacidad, habrá Nm combinaciones.

Leslie Murray Introducción Informal 23 / 27

Clase de Problema

s

t

• A menos que se trate de una topología particular, los algoritmos conocidos paraevaluar ζ son de complejidad exponencial en el número de enlaces:

es necesario evaluar las N1×N2× . . .×Nm posibles configuraciones.

• Este problema pertenece a la clase NP–difícil (NP–hard), luego, es altamenteimprobable que exista una algoritmo de complejidad polinomial que lo resuelva.

• Para redes medianas o grandes, los tiempos de ejecución son inviables.

Leslie Murray Introducción Informal 24 / 27

Metodología

• Para redes de tamaño mediano a grande la determinación de ζ mediantealgoritmos de cálculo exacto es inviable.

• Una posible alternativa al cálculo exacto es la estimación mediante simulación.

• La estimación estándar consiste en generar “sólo algunas” configuraciones de lared, elegidas en forma aleatoria, y determinar la proporción de ellas en las quese garantiza la demanda de flujo.

• Si la confiabilidad es extremadamente alta, en todas las configuracionesgeneradas la demanda de flujo será satisfecha, por lo que la estimación de ζresultará imposible o casi imposible.

• Este problema se resuelve mejorando el rendimiento de las simulacionesmediante técnicas de reducción de varianza.

Objetivo del curso

Estudiar métodos de simulación que permitan estimar eficientemente la confiabilidadde redes de gran tamaño, altamente confiables.

Leslie Murray Introducción Informal 25 / 27

Resumen

Red

Pequeña→

Método

Cálculo Exacto

Red

Grande→

Método

Simulación estándar

Red

Grandey

Altamente Confiable

→

Método

Simulación estándar+

Reducción de Varianza

ր

En el curso se analizarán métodos para mejorar la simulación estándar mediantetécnicas de reducción de varianza a fin de poder hacer estimaciones de confiabilidadde redes de gran tamaño, altamente confiables.

Leslie Murray Introducción Informal 26 / 27

Lineamientos Principales

Existe una diversidad de técnicas de reducción de varianza, algunas de las cuales sehan aplicado a mejorar la estimación de de confiabilidad de estos modelos de redes.Algunas se basan en técnicas como por ejemplo:

1 Cambiar las distribuciones de probabilidad de los componentes por otras quefaciliten la ocurrencia de los eventos de interés, corrigiendo al final el resultado,sesgado por la modificación de las distribuciones (Muestreo de Importancia).

2 Introducir un tiempo artificial, para convertir los modelos estáticos endinámicos y así abordarlos a través de su evolución temporal (sucesiones defallas y/o reparaciones).

3 Considerar las evoluciones de estos modelos como trayectorias dentro delespacio de estados y clonar o multiplicar las trayectorias que más se acerquena los eventos de interés en procura de generar ocurrencias más frecuentes(Splitting).

4 Combinar adecuadamente 2 y 3 ← LA PARTE CENTRAL DEL CURS0

Leslie Murray Introducción Informal 27 / 27