Falhas em cascata

Abstract

Mitigar os efeitos das falhas em cascata tem sido um desafio para a comunidade cientifica. Este tipo de falhas é originado num dado nó e propaga-se a nós adjacentes podendo resultar num colapso da rede. O presente trabalho focou-se neste tipo de falhas e foi motivado inicialmente pelo estudo da interdependência entre a rede elétrica e a rede de comunicação, que a controla (rede elétrica inteligente), embora o trabalho final não se foque especificamente nessa interdependência. Na presente dissertação estudaram-se estratégias para limitar os efeitos de falhas com potencial para se propagarem em cascata em qualquer tipo de rede com topologia em árvore. Assim, existe a necessidade de identificar os nós críticos na rede, i.~e. os nós com maior potencial de propagação de falhas, e torná-los mais robustos. Embora não se tenha estudado neste trabalho a forma de tornar robustos os nós, dado que isso depende do tipo de nós em questão e do tipo de rede, considerou-se que se um nó estiver protegido ele não vai falhar se ocorrer uma falha nos nós adjacentes. Para identificar os nós críticos foi estudada uma métrica de centralidade e foram desenvolvidos algoritmos baseados nesta métrica seguindo uma estratégia proposta em [5]. Basicamente a estratégia baseia-se em encontrar os nós de maior centralidade na rede em árvore e nas sub-árvores que vão surgindo à medida que esses nós centrais vão sendo protegidos. Foi feita uma análise exaustiva do desempenho da estratégia proposta, usando redes de referência, e comparou-se o desempenho da rede na presença de falhas em cascata quando os nós críticos são escolhidos com essa estratégia e quando o mesmo número de nós críticos são escolhidos entre os nós de maior grau. Concluiu-se que, de numa forma de geral, a estratégia proposta conduz a bons resultados, embora haja situações pontuais em que a métrica grau do nó conduz a melhores resultados.

Mitigating the effects of cascading failures has been a challenge for the scientic community. This type of failure is originated in a given node and can be propagated to adjacent nodes and may result in a network collapse. The present work focused on these types of failures and was initially motivated by the study of the interdependence between the power grid and the communication network that controls it (smart grid), although the final work doesn't specifically focus on this interdependence. In the present dissertation, were studied strategies to limit the effects of failures with potential to propagate in cascade in any network with tree topology. Thus, there is a need to identify the critical nodes in the network, ie. nodes with the greatest potential for failure propagation, and make them more robust. Although we didn't study how to make the nodes robust, as this depends on the type of nodes in question and the type of network, it was considered that if a node is protected it will not fail if the adjacent nodes fail. To identify critical nodes a centrality metric was studied and algorithms based on this metric were developed following a strategy proposed in [5]. Basically the strategy is based on finding the most central nodes in the tree network and in the subtrees that appear successively after the most central nodes are becoming protected. An extensive analysis of the performance of the proposed strategy using reference networks was performed and the performance of the network in the presence of cascading failures was compared when critical nodes are chosen with this strategy and when the same number of critical nodes are chosen among the nodes with highest degree. It was concluded that in general the new centrality metric leads to good results, although thereare occasional situations where the node degree metric leads to better results.