Calibrating a Dependent Failure Model for Computing Reliabilities on Telecommunication Networks Omar Matus, Javiera Barrera, Eduardo Moreno Gerardo Rubino Faculty of Engineering and Sciences I NRIA Rennes – Bretagne Atlantique Universidad Adolfo Ibáñez Campus de Beaulieu Avda. Diagonal Las Torres 2700 35042 Rennes Cedex, FRANCE Peñalolén, Santiago, CHILE 1. Introducción Resumen Durante los últimos 40 años, el estudio del diseño y la evaluación de redes de telecomunicaciones se ha en- frentado de diversas maneras. Tomando en cuenta que In this work, we propose a methodology to ca- existen medidas de funcionamiento que para una red, librate a dependent failure model to compu- como velocidad, conectividad y seguridad entre otros, te the reliability in a telecommunication net- es importante notar que en este trabajo nos centraremos work. We use the Marshall-Olkin (MO) co- en el estudio de la confiabilidad de una red, entendida pula model, which captures failures that arise como la probabilidad de que un conjunto de componen- simultaneously in groups of links. In practi- tes, que pueden tornarse no operativos a medida que ce, this model is difficult to calibrate because pasa el tiempo, estén conectados en un tiempo deter- it requires the estimation of a number of pa- minado. Esta evaluación de la confiabilidad requiere un rameters that is exponential in the number of modelo de fallas, en conjunto con una metodologı́a que links. permita calibrar dicho modelo. El estudio de la con- fiabilidad es un problema difı́cil de enfrentar, incluso We formulate an optimization problem to cali- cuando muchos modelos de estudio de fallas conside- brate a MO copula model to attain given mar- ran el supuesto de independencia entre las fallas de los ginal failure probabilities for all links and the componentes el problema es #P-completo [PB83]. correlations between them. Using a geograp- Si bien el supuesto de independencia es usado en hic failure model, we calibrate various MO varios modelos, la evidencia empı́rica, del estudio de copula models using our methodology, we si- diversos tipos de redes, demuestra que la correlación mulate them, and we benchmark the reliabili- entre las fallas de los componentes existe e impacta sig- ties thus obtained. nificativamente la confiabilidad de redes en diferentes contextos [TLSS10], [HR01], [GHHK10], [GJN11]. Our experiments show that considering the si- Al enfrentarnos al problema de diseñar una red, de- multaneous failures of small and connected bemos tener en consideración que el modelo de fallas subsets of links is the key to obtain a good seleccionado debe entregarnos, por un lado, rigurosi- approximation of reliability, confirming what dad en los resultados, al mismo tiempo que, flexibili- is suggested by the telecommunication litera- dad en su calibración y uso, tal como señalan Barrera, ture. Cancela y Moreno [BCM14]. El problema de elección de un modelo de fallas de- Copyright c by the paper’s authors. Copying permitted for private pendientes ha sido analizado durante los últimos años and academic purposes. por diversos autores. En nuestro caso seleccionamos un modelo ampliamente estudiado y que ofrece una gran flexibilidad en su uso, el modelo de Marshall-Olkin 3. Escogiendo un conjunto apropiado de [MO67]. A pesar de su versatilidad, este modelo ha en- cópulas para MO frentado crı́ticas a lo largo de los años, inducidas por la poca escalabilidad que posee su calibración debido a la Buscamos determinar un conjunto de cópulas para gran cantidad de parámetros requeridos [Sin02]. satisfacer el sistema de ecuaciones, dicho problema no es fácil de resolver ya que el sistema tiene un numero exponencial de variables. Una solución para este pro- 2. Modelo de Marshall-Olkin blema puede obtenerse usando una técnica conocida Sea G un grafo con un conjunto de nodos N , co- como generación de columnas [DW60]. Esta técnica, nectados, no necesariamente todos con todos, por un permite incluir diferentes criterios de forma de priori- conjunto de arcos denotados por C = {1, 2, . . . , n}. zar las cópulas que se utilizarán. El modelo principal, Asumiremos que los nodos no pueden fallar. Para los denominado maestro en generación de columnas, para arcos, tomemos los posibles subconjuntos de arcos, ca- obtener las cópulas está dado en la ecuación (1). da uno de los cuales puede ser afectado por un shock que vuelve no operativo a los componentes de ese sub-   conjunto que estaban operativos al momento del shock. mı́n ∑ ti+j + ti−j (1a) De esta forma, definimos un tiempo de vida de cada i, j∈C componente, que corresponde al mı́nimo tiempo has- √ √ ! ρi, j pi p j ta que un shock afecte a un subconjunto que posee el ∑ λV + ti+j − ti−j = ln p +1 componente. V ⊆C :{i, j}∈V (1 − pi )(1 − p j ) Si se considera que los shocks ocurren de acuerdo a ∀i, j ∈ C , i 6= j (1b) procesos de Poisson, entonces el tiempo de vida de los ∑ λV + tii+ − tii− = − ln(1 − pi ) , ∀i ∈ C componentes es exponencial. En caso de algún subcon- V ⊆C :i∈V junto no tenga un shock asociado, decimos que su tasa (1c) de falla es cero. De esta forma el estado de la red, ope- rativa o no, es una función del tiempo y depende del λV ≥ 0 , ∀V ⊆ C (1d) + − estado de los arcos. Es importante notar que los arcos ti j ,ti j ≥ 0 , ∀i, j ∈ C . (1e) representan en este modelo los componentes de la red estudiada, mientras que los nodos son las conexiones En este modelo se busca encontrar un conjunto de entre dichos componentes. cópulas que se acerquen lo más posible a satisfacer las Estudiamos la confiabilidad R(t) de la red, seleccio- ecuaciones del modelo de Marshall-Olkin, de esta for- nando dos nodos, s y f , de forma tal que R(t) repre- ma tenemos que ti+j y ti−j representan la holgura que senta la probabilidad de que en el tiempo t exista un existe para satisfacer cada una de las ecuaciones, por camino entre estos nodos, formado por los arcos que sobre o bajo el valor del lado derecho de cada una, res- aún permanecen operativos en ese instante. En nues- pectivamente. Mientras que los pi y los ρi, j representan tro caso, analizaremos la conectividad de los nodos en respectivamente las probabilidades marginales de falla el momento t = 1, donde tasa de ocurrencia del shock de cada componente y la correlación entre dos compo- que afecta al subconjunto de arcos i, estará dada por nentes. λi = − ln(1 − pi ), ası́, con R(1) se puede recuperar el Para verificar cuales cópula debe agregarse al pro- modelo estático. Esto representa lo esencial del proce- blema, se puede elaborar un modelo pricing que permi- so de Elperin y Lomonosov [EGL91]. te determinar a través de conocer los costos reducidos Dado un conjunto de probabilidades de fallas margi- de las cópulas candidatas a ingresar nales de los arcos y las correlaciones entre estas fallas, podemos plantear un sistema de n(n + 1)/2 ecuaciones C̄V = − ∑ µi − ∑ νi j , y 2n − 1 variables, una ecuación para cada falla margi- i∈V i, j∈V nal de cada arco y una ecuación para cada correlación entre dos arcos, junto con una variable para cada sub- donde µi y νi j son las variables duales de las ecuacio- conjunto de arcos. nes planteadas en (1c) y (1b), respectivamente. En este Debemos destacar que generalmente el sistema de modelo se probaron diferentes criterios, tales como mi- ecuaciones posee infinitas soluciones, por lo cual es nimizar o maximizar la suma total de las tasas de ocu- importante analizar el impacto que tiene en la estima- rrencia de los shocks y minimizar la suma de las máxi- ción de la confiabilidad la elección de cada una de las mas distancias entre los nodos en cada subconjunto de soluciones posibles. arcos ponderados por su tasa. 4. Experimentos numéricos 5. Conclusiones Para probar las metodologı́as diseñadas, se esco- La dependencia entre las fallas de los componen- gió un sistema de fallas fı́sicas, en donde una red de 36 tes es significativamente importante en el estudio de la arcos y 21 nodos es afectada por terremotos en posicio- confiabilidad de redes e ignorarla puede traer consigo nes y con intensidades aleatorias, tomando como base grandes divergencias en la estimación de la confiabili- el modelo planteado por Agarwal et al. [AEG+ 13]. La dad. simulación de dicho modelo fı́sico nos permite tener Por otro lado, mostramos que es posible calibrar las probabilidades marginales de las fallas de cada ar- MO teniendo las fallas marginales de los componentes co, ası́ como también las correlaciones existentes entre y las correlaciones entre ellos; por medio de generación estos. de columnas, se pueden determinar los parámetros ne- Con esta información aplicamos nuestro modelo cesarios para MO. Ası́ también, considerando que las de generación de columnas con diferentes criterios de correlaciones son la probabilidad de falla simultánea elección, de forma tal de obtener los parámetros para de dos componentes, en caso de poseer la información calibrar MO. Una vez calibrado MO, realizamos simu- de fallas simultáneas de más de dos componentes, el laciones de forma tal de obtener la estimación de la modelo es fácilmente adaptable a esta situación. confiabilidad de la red, para cada criterio escogido. Es- Finalmente corroboramos las conclusiones expues- ta confiabilidad es comparada con la confiabilidad en- tas en la literatura, referentes a que los criterios de pro- tregada por el modelo fı́sico. ximidad de los componentes y la cantidad de compo- Es importante notar que en nuestro experimento co- nentes involucrados en fallas simultaneas pueden ser nocemos el modelo fı́sico detrás del funcionamiento de utilizados para calibrar MO de forma tal de que esti- la red, por lo tanto el objetivo de estimar la confiabili- memos de buena manera la confiabilidad de una red. dad por medio de MO es únicamente comparar la es- timación de nuestro modelo con el resultado fı́sico y 6. Trabajo Futuro analizar qué tanto nos acercamos. En la práctica mu- Como trabajo futuro pretendemos probar los méto- chas veces los modelos que subyacen a las redes son dos y modelos usados en más redes, de forma tal de desconocidos o de difı́cil simulación o modelado. MO analizar si los resultados obtenidos son aplicables a un permite estimar la confiabilidad de las redes incluso sin numero mayor de ellas. Ası́ también buscamos encon- conocer ese modelo. trar otro modelo de fallas distinto al de sismos, para Los resultados muestran que las confiabilidades ob- ver una posible generalización de los resultados usan- tenidas por medio del modelo de MO, calibrado uti- do modelo de fallas de otra naturaleza. lizando nuestra metodologı́a, son muy cercanos a las confiabilidades reales. En todos los casos, el error abso- Agradecimientos luto promedio en la estimación de la confiabilidad es de un 1 % mientras que los errores absolutos máximos son Los autores agradecen el aporte financiero de los menores a 3 %. Dichos resultados están en la siguien- proyectos FONDECYT 1130681 y 1161064 INRIA- te tabla, donde la notación es para cada caso Me para CIRIC y al Programa Iniciativa Cientı́fica Milenio Media, M para máxima, AD para Diferencia Absoluta NC130062. y DR para diferencia relativa. Y los modelos analiza- dos son Independiente, Maximizar suma de Lambdas, Referencias Minimizar suma de Lambdas, Maximizar suma de Dis- [AEG+ 13] Pankaj K Agarwal, Alon Efrat, Shashid- tancias en Lambdas. hara K Ganjugunte, David Hay, Swa- minathan Sankararaman, and Gil Zuss- Cuadro 1: Errores relativos y absolutos man. The resilience of wdm net- works to probabilistic geographical failu- res. IEEE/ACM Transactions on Networ- Model Me DA Me DR M DA M DR king (TON), 21(5):1525–1538, 2013. Indep. 0.041 0.048 0.156 0.196 Max L 0.006 0.007 0.028 0.036 [BCM14] Javiera Barrera, Hector Cancela, and Min L 0.002 0.003 0.016 0.019 Eduardo Moreno. Topological optimi- Max D 0.003 0.003 0.026 0.033 zation of reliable networks under depen- dent failures. Operations Research Let- ters, 32(2):132–136, 2014. [DW60] George B Dantzig and Philip Wolfe. Decomposition principle for linear pro- grams. Operations Research, 8(1):101– 111, 1960. [EGL91] T Elperin, I Gertsbakh, and M Lomo- nosov. Estimation of network reliabi- lity using graph evolution models. Relia- bility, IEEE Transactions on, 40(5):572– 581, 1991. [GHHK10] Andres J. Gonzalez, Bjarne E. Helvik, Jon K. Hellan, and Pirkko Kuusela. Analysis of Dependencies between Failu- res in the UNINETT IP Backbone Net- work. In 2010 IEEE 16th Pacific Rim International Symposium on Dependable Computing, pages 149–156. IEEE, 2010. [GJN11] Phillipa Gill, Navendu Jain, and Nachiap- pan Nagappan. Understanding network failures in data centers. In ACM SIG- COMM Computer Communication Re- view, volume 41, page 350. ACM, 2011. [HR01] Jane Nichols Hagstrom and Shel- don Ross. Component state de- pendence and error in reliability computation. Available in http: //citeseerx.ist.psu.edu/viewdoc/ summary?doi=10.1.1.20.8460, 2001. [MO67] Albert W Marshall and Ingram Olkin. A multivariate exponential distribution. Journal of the American Statistical Asso- ciation, 62(317):30–44, 1967. [PB83] J Scott Provan and Michael O Ball. The complexity of counting cuts and of com- puting the probability that a graph is con- nected. SIAM Journal on Computing, 12(4):777–788, 1983. [Sin02] Nozer D. Singpurwalla. Dependence in network reliability. Proceedings of the 5th International Conference on Information Fusion, FUSION 2002, 2:981–985, 2002. [TLSS10] Daniel Turner, Kirill Levchenko, Alex C. Snoeren, and Stefan Savage. Califor- nia fault lines: understanding the cau- ses and impact of network failures. In ACM SIGCOMM Computer Communica- tion Review, volume 40, pages 315–326. ACM, 2010.