=Paper=
{{Paper
|id=Vol-1727/ssn16-final6
|storemode=property
|title=Calibrating a Dependent Failure Model for Computing Reliabilites on Telecommunication Networks
|pdfUrl=https://ceur-ws.org/Vol-1727/ssn16-final6.pdf
|volume=Vol-1727
|authors=Omar Matus,Javiera Barrera,Eduardo Moreno,Gerardo Rubino
|dblpUrl=https://dblp.org/rec/conf/ssn/MatusBMR16
}}
==Calibrating a Dependent Failure Model for Computing Reliabilites on Telecommunication Networks==
https://ceur-ws.org/Vol-1727/ssn16-final6.pdf
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.