In this work, we propose a methodology to calibrate a dependent failure model to compute the reliability in a telecommunication network. We use the Marshall-Olkin (MO) copula model, which captures failures that arise simultaneously in groups of links. In practice, this model is difficult to calibrate because it requires the estimation of a number of parameters that is exponential in the number of links.
We formulate an optimization problem to calibrate a MO copula model to attain given marginal failure probabilities for all links and the correlations between them. Using a geographic failure model, we calibrate various MO copula models using our methodology, we simulate them, and we benchmark the reliabilities thus obtained.
Our experiments show that considering the simultaneous failures of small and connected subsets of links is the key to obtain a good approximation of reliability, confirming what is suggested by the telecommunication literature.
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
INRIA Rennes – Bretagne Atlantique
Campus de Beaulieu 35042 Rennes Cedex, FRANCE 1.
Durante los u´ltimos 40 an˜os, el estudio del disen˜o y la evaluacio´n de redes de telecomunicaciones se ha enfrentado de diversas maneras. Tomando en cuenta que existen medidas de funcionamiento que para una red, como velocidad, conectividad y seguridad entre otros, es importante notar que en este trabajo nos centraremos en el estudio de la confiabilidad de una red, entendida como la probabilidad de que un conjunto de componentes, que pueden tornarse no operativos a medida que pasa el tiempo, este´n conectados en un tiempo determinado. Esta evaluacio´n de la confiabilidad requiere un modelo de fallas, en conjunto con una metodolog´ıa que permita calibrar dicho modelo. El estudio de la confiabilidad es un problema dif´ıcil de enfrentar, incluso cuando muchos modelos de estudio de fallas consideran el supuesto de independencia entre las fallas de los componentes el problema es #P-completo [PB83].
Si bien el supuesto de independencia es usado en varios modelos, la evidencia emp´ırica, del estudio de diversos tipos de redes, demuestra que la correlacio´n entre las fallas de los componentes existe e impacta significativamente la confiabilidad de redes en diferentes contextos [TLSS10], [HR01], [GHHK10], [GJN11].
Al enfrentarnos al problema de disen˜ar una red, debemos tener en consideracio´n que el modelo de fallas seleccionado debe entregarnos, por un lado, rigurosidad en los resultados, al mismo tiempo que, flexibilidad en su calibracio´n y uso, tal como sen˜alan Barrera, Cancela y Moreno [BCM14].
El problema de eleccio´n de un modelo de fallas dependientes ha sido analizado durante los u´ltimos an˜os por diversos autores. En nuestro caso seleccionamos un modelo ampliamente estudiado y que ofrece una gran 3.
co´ pulas para MO
Buscamos determinar un conjunto de co´pulas para satisfacer el sistema de ecuaciones, dicho problema no es fa´cil de resolver ya que el sistema tiene un numero exponencial de variables. Una solucio´n para este problema puede obtenerse usando una te´cnica conocida como generacio´n de columnas [DW60]. Esta te´cnica, permite incluir diferentes criterios de forma de priorizar las co´pulas que se utilizara´n. El modelo principal, denominado maestro en generacio´n de columnas, para obtener las co´pulas esta´ dado en la ecuacio´n (1). m´ın å i; j2C
ti+j + ti j å V C :fi; jg2V
å V C :i2V lV + ti+j
ti j = ln 8i; j 2 C ; i 6= j lV + ti+i flexibilidad en su uso, el modelo de Marshall-Olkin [MO67]. A pesar de su versatilidad, este modelo ha enfrentado cr´ıticas a lo largo de los an˜os, inducidas por la poca escalabilidad que posee su calibracio´n debido a la gran cantidad de para´metros requeridos [Sin02]. 2.
Sea G un grafo con un conjunto de nodos N , conectados, no necesariamente todos con todos, por un conjunto de arcos denotados por C = f1; 2; : : : ; ng. Asumiremos que los nodos no pueden fallar. Para los arcos, tomemos los posibles subconjuntos de arcos, cada uno de los cuales puede ser afectado por un shock que vuelve no operativo a los componentes de ese subconjunto que estaban operativos al momento del shock. De esta forma, definimos un tiempo de vida de cada componente, que corresponde al m´ınimo tiempo hasta que un shock afecte a un subconjunto que posee el componente.
Si se considera que los shocks ocurren de acuerdo a procesos de Poisson, entonces el tiempo de vida de los componentes es exponencial. En caso de algu´n subconjunto no tenga un shock asociado, decimos que su tasa de falla es cero. De esta forma el estado de la red, operativa o no, es una funcio´n del tiempo y depende del estado de los arcos. Es importante notar que los arcos representan en este modelo los componentes de la red estudiada, mientras que los nodos son las conexiones entre dichos componentes.
Estudiamos la confiabilidad R(t) de la red, seleccionando dos nodos, s y f , de forma tal que R(t) representa la probabilidad de que en el tiempo t exista un camino entre estos nodos, formado por los arcos que au´n permanecen operativos en ese instante. En nuestro caso, analizaremos la conectividad de los nodos en el momento t = 1, donde tasa de ocurrencia del shock que afecta al subconjunto de arcos i, estara´ dada por li = ln(1 pi), as´ı, con R(1) se puede recuperar el modelo esta´tico. Esto representa lo esencial del proceso de Elperin y Lomonosov [EGL91].
Dado un conjunto de probabilidades de fallas marginales de los arcos y las correlaciones entre estas fallas, podemos plantear un sistema de n(n + 1)=2 ecuaciones y 2n 1 variables, una ecuacio´n para cada falla marginal de cada arco y una ecuacio´n para cada correlacio´n entre dos arcos, junto con una variable para cada subconjunto de arcos.
Debemos destacar que generalmente el sistema de ecuaciones posee infinitas soluciones, por lo cual es importante analizar el impacto que tiene en la estimacio´n de la confiabilidad la eleccio´n de cada una de las soluciones posibles.
En este modelo se busca encontrar un conjunto de co´pulas que se acerquen lo ma´s posible a satisfacer las ecuaciones del modelo de Marshall-Olkin, de esta forma tenemos que ti+j y ti j representan la holgura que existe para satisfacer cada una de las ecuaciones, por sobre o bajo el valor del lado derecho de cada una, respectivamente. Mientras que los pi y los ri; j representan respectivamente las probabilidades marginales de falla de cada componente y la correlacio´n entre dos componentes.
Para verificar cuales co´pula debe agregarse al problema, se puede elaborar un modelo pricing que permite determinar a trave´s de conocer los costos reducidos de las co´pulas candidatas a ingresar
C¯V = å mi i2V å ni j; i; j2V donde mi y ni j son las variables duales de las ecuaciones planteadas en (1c) y (1b), respectivamente. En este modelo se probaron diferentes criterios, tales como minimizar o maximizar la suma total de las tasas de ocurrencia de los shocks y minimizar la suma de las ma´ximas distancias entre los nodos en cada subconjunto de arcos ponderados por su tasa.
tii = ln(1
pi) ; 8i 2 C lV ti+j ; ti j 0 ; 8V 0 ; 8i; j 2 C :
C ri; jppipp j p(1 pi)(1 p j)
! (1a) + 1 (1b) (1c) (1d) (1e)
Para probar las metodolog´ıas disen˜adas, se escogio´ un sistema de fallas f´ısicas, en donde una red de 36 arcos y 21 nodos es afectada por terremotos en posiciones y con intensidades aleatorias, tomando como base el modelo planteado por Agarwal et al. [AEG+13]. La simulacio´n de dicho modelo f´ısico nos permite tener las probabilidades marginales de las fallas de cada arco, as´ı como tambie´n las correlaciones existentes entre estos.
Con esta informacio´n aplicamos nuestro modelo de generacio´n de columnas con diferentes criterios de eleccio´n, de forma tal de obtener los para´metros para calibrar MO. Una vez calibrado MO, realizamos simulaciones de forma tal de obtener la estimacio´n de la confiabilidad de la red, para cada criterio escogido. Esta confiabilidad es comparada con la confiabilidad entregada por el modelo f´ısico.
Es importante notar que en nuestro experimento conocemos el modelo f´ısico detra´s del funcionamiento de la red, por lo tanto el objetivo de estimar la confiabilidad por medio de MO es u´nicamente comparar la estimacio´n de nuestro modelo con el resultado f´ısico y analizar que´ tanto nos acercamos. En la pra´ctica muchas veces los modelos que subyacen a las redes son desconocidos o de dif´ıcil simulacio´n o modelado. MO permite estimar la confiabilidad de las redes incluso sin conocer ese modelo.
Los resultados muestran que las confiabilidades obtenidas por medio del modelo de MO, calibrado utilizando nuestra metodolog´ıa, son muy cercanos a las confiabilidades reales. En todos los casos, el error absoluto promedio en la estimacio´n de la confiabilidad es de un 1 % mientras que los errores absolutos ma´ximos son menores a 3 %. Dichos resultados esta´n en la siguiente tabla, donde la notacio´n es para cada caso Me para Media, M para ma´xima, AD para Diferencia Absoluta y DR para diferencia relativa. Y los modelos analizados son Independiente, Maximizar suma de Lambdas, Minimizar suma de Lambdas, Maximizar suma de Distancias en Lambdas.
Cuadro 1: Errores relativos y absolutos Model Indep.
Max L Min L Max D
Me DA 0.041 0.006 0.002 0.003
Me DR 0.048 0.007 0.003 0.003
M DA 0.156 0.028 0.016 0.026
M DR 0.196 0.036 0.019 0.033 5.
La dependencia entre las fallas de los componentes es significativamente importante en el estudio de la confiabilidad de redes e ignorarla puede traer consigo grandes divergencias en la estimacio´n de la confiabilidad.
Por otro lado, mostramos que es posible calibrar MO teniendo las fallas marginales de los componentes y las correlaciones entre ellos; por medio de generacio´n de columnas, se pueden determinar los para´metros necesarios para MO. As´ı tambie´n, considerando que las correlaciones son la probabilidad de falla simulta´nea de dos componentes, en caso de poseer la informacio´n de fallas simulta´neas de ma´s de dos componentes, el modelo es fa´cilmente adaptable a esta situacio´n.
Finalmente corroboramos las conclusiones expuestas en la literatura, referentes a que los criterios de proximidad de los componentes y la cantidad de componentes involucrados en fallas simultaneas pueden ser utilizados para calibrar MO de forma tal de que estimemos de buena manera la confiabilidad de una red. 6.
Como trabajo futuro pretendemos probar los me´todos y modelos usados en ma´s redes, de forma tal de analizar si los resultados obtenidos son aplicables a un numero mayor de ellas. As´ı tambie´n buscamos encontrar otro modelo de fallas distinto al de sismos, para ver una posible generalizacio´n de los resultados usando modelo de fallas de otra naturaleza.
Agradecimientos
Los autores agradecen el aporte financiero de los proyectos FONDECYT 1130681 y 1161064 INRIACIRIC y al Programa Iniciativa Cient´ıfica Milenio NC130062. [BCM14]
Javiera Barrera, Hector Cancela, and Eduardo Moreno. Topological optimization of reliable networks under dependent failures. Operations Research Letters, 32(2):132–136, 2014. [EGL91] [TLSS10]