Medindo a robustez de uma rede com o fator de resiliência presentation ciawi2009

RoteiroIntroducao

Resiliencia em Redes de ComputadoresMedindo a Robustez de Uma Rede com o Fator de Resiliencia

Testes com Topologias e Validacao do FatorConsideracoes Finais

Referencias

Medindo a Robustez de Uma Rede com o Fatorde Resiliencia

Donato Antonio Marino JuniorRonaldo Moreira Salles

Universidad de Alcala

Marino e Salles (IME) Medindo a Robustez de Uma Rede com o Fator de Resiliencia Outubro/2009 1 / 32

RoteiroIntroducao



Referencias

Roteiro I

1 IntroducaoResiliencia em Redes de ComputadoresObjetivosMotivacao

2 Resiliencia em Redes de ComputadoresTrabalhos RelacionadosMetricas de Topologias

3 Medindo a Robustez de Uma Rede com o Fator de ResilienciaO Fator de Resiliencia

4 Testes com Topologias e Validacao do FatorAtaques e Medidas de CentralidadeTestes com as MetricasComparacao de MetricasConclusoes

5 Consideracoes FinaisConclusoes do TrabalhoTrabalhos Futuros

6 Referencias


RoteiroIntroducao



Referencias

Resiliencia em Redes de ComputadoresObjetivosMotivacao

Resiliencia em Redes de Computadores

Definicao

Resiliencia em redes e a habilidade de uma entidade de tolerar(resistir e automaticamente se recuperar de) desafios nas condicoesda rede, ataques coordenados e anomalias no trafego.[Aggelou, 2008]


RoteiroIntroducao



Referencias


Objetivos do Trabalho

Obtencao de uma metrica que possa avaliar quao resiliente euma rede

Validacao da metrica proposta, comparando-a com metricaspublicadas em artigos cientıficos


RoteiroIntroducao



Referencias


Motivacao

Permitir a avaliacao da robustez de uma rede

Permitir a comparacao de duas ou mais redes

Permitir a avaliacao de estrategias de alteracao de topologias


RoteiroIntroducao



Referencias

Trabalhos RelacionadosMetricas de Topologias

Trabalhos Relacionados

Network Robustness and Graph Topology[Dekker and Colbert, 2004]Apresenta a conectividade do no e a similaridade entre os nos comoprincipais metricas para a avaliacao da robustez da topologia.Analisa topologias simetricas, livres de escala, aleatorias e outras.


RoteiroIntroducao



Referencias


Trabalhos Relacionados

Improving Network Robustness by Edge Modification[Beygelzimer et al., 2005]Considera tres importantes metricas para avaliar a robustez deuma rede diante de falhas aleatorias e ataques direcionados e testaestrategias de insercao e remanejamento de enlaces para amelhoria da resiliencia. Metricas utilizadas:

Diametro

LCC - Largest Connected Component

AISPL - Average Inverse Shortest Path Length


RoteiroIntroducao



Referencias


Metricas de Topologias

AISPL - Average Inverse Shortest Path Length

Media inversa do tamanho de todos os caminhos geodesicosde uma rede.

LCC - Largest Connected Component

Quantidade de nos do maior subgrafo resultante dadesconexao da rede causada por falha ou ataque.


RoteiroIntroducao



Referencias


Metricas de Topologias

k-conectividade

Definicao

Seja G um grafo k-conexo. Entao para qualquer par de vertices,existem pelo menos k caminhos vertice-disjuntos entre eles.[Skiena, 2008]


RoteiroIntroducao



Referencias

O Fator de Resiliencia

Metrica de Resiliencia Proposta

k-conectividade parcial

A k-conectividade parcial de um grafo e expressa pelo percentualde testes no calculo da k-conectividade que mantiveram atopologia conexa, apos a remocao de combinacoes de k − 1vertices.


RoteiroIntroducao



Referencias


k-conectividade parcial - Exemplo

Figura: Combinacoes para uma topologia de cinco nos


RoteiroIntroducao



Referencias





RoteiroIntroducao



Referencias





RoteiroIntroducao



Referencias



O Fator de Resiliencia utiliza a k-conectividade parcial paramedir a robustez de uma rede.

Calcula da 2-conectividade parcial ate a (n − 1)-conectividadeparcial da rede

Considera duas importantes propriedades de grafos conexos:

Todo grafo conexo e 1-conexo.Todo grafo conexo e n-conexo, sendo n o numero total devertices.


RoteiroIntroducao



Referencias



A expressao obtida para calculo do Fator de Resiliencia e:

FR =

n−1∑i=2

k(i)

(n−2)

Para a topologia utilizada como exemplo, o calculo seria:

k(2)+k(3)+k(4)(5−2) = 1+0,9+0,7

3 = 0, 8666


RoteiroIntroducao



Referencias

Ataques e Medidas de CentralidadeTestes com as MetricasComparacao de MetricasConclusoes

Ataques e Medidas de Centralidade

Simulacoes de Ataques aos nos de maior importancia

Nas simulacoes foram utilizadas medidas de centralidadeoriundas do estudo de Redes Sociais [Wasserman et al., 1994]:

Closeness Centrality (CC)Betweeness Centrality (BC)

Comparacao dos resultados com as metricas do trabalhorelacionado


RoteiroIntroducao



Referencias


Topologias usadas nos testes

Figura: Telcordia - 15 nos e 28 enlaces


RoteiroIntroducao



Referencias



Figura: Cost-239 - 19 nos e 40 enlaces


RoteiroIntroducao



Referencias



Figura: JaNet - 29 nos e 45 enlaces


RoteiroIntroducao



Referencias



Figura: Renater - 30 nos e 42 enlaces


RoteiroIntroducao



Referencias



Figura: RNP - 27 nos e 26 enlaces


RoteiroIntroducao



Referencias



Figura: UKNet - 30 nos e 51 enlaces


RoteiroIntroducao



Referencias


Softwares utilizados nos Testes

Vertex

Indica Topologia Conexa/Nao ConexaIndica Topologia Completa/Nao CompletaPermite identificar a k-conectividade “completa”Calcula o Fator de Resiliencia

SocNetV - Social Network Visualizer

Calcula CC e BCCalcula DiametroCalcula Average Shortest Path LengthTabela de caminhos geodesicos da topologia


RoteiroIntroducao



Referencias


AISPL - Ataques aos nos de maior CC e BC

* Apresentou inconsistencia quando o ataque desconecta a topologia

* O AISPL realiza calculo no LCC


RoteiroIntroducao



Referencias


LCC - Ataques aos nos de maior CC e BC

* Nao diferencia as topologias em seu estado original

* Sua queda refletia apenas a quantidade de nos atacados


RoteiroIntroducao



Referencias


Fator de Resiliencia - Ataques aos nos de maior CC e BC


RoteiroIntroducao



Referencias


Fator de Resiliencia x AISPL e LCC

Topologia Telcordia Topologia Renater


RoteiroIntroducao



Referencias


Conclusoes dos Testes da Metrica Proposta

O Fator de Resiliencia foi a metrica mais consistente naanalise da robustez de uma rede

Apresentou boa precisao no seu valor permitindo acomparacao de topologias

Nos testes de simulacao de ataques apresentou coerencia emtodos os resultados, diferente das metricas do trabalhorelacionado

Na comparacao com as outras metricas nos seus melhorescasos, os resultados do Fator de Resiliencia seguiramcorretamente a tendencia de queda apos os ataques


RoteiroIntroducao



Referencias

Conclusoes do TrabalhoTrabalhos Futuros

Conclusoes do Trabalho

O trabalho apresentou o Fator de Resiliencia como a medidade robustez de uma rede.

Foram utilizadas topologias reais de backbones comerciais eacademicos, em simulacoes de ataques aos nos de maiorimportancia da rede, baseados em conceitos de redes sociais.

Os testes realizados com o Fator de Resiliencia foram maisprecisos e mais consistentes do que com outras metricaspropostas em trabalhos anteriores.


RoteiroIntroducao



Referencias

Conclusoes do TrabalhoTrabalhos Futuros

Trabalhos Futuros

Pesquisa de novos algoritmos ou heurısticas para o calculo dak-conectividade parcial

Analise de estrategias para a alteracao de topologias visando oaumento da resiliencia

Estudo de um procedimento para o projeto de redes resilientescom base no fator proposto


RoteiroIntroducao



Referencias

Referencias I

Aggelou, G. (2008).Wireless Mesh Networking.McGraw-Hill Professional.

Beygelzimer, A., Grinstein, G., Linsker, R., and Rish, I. (2005).Improving network robustness by edge modification.Physica A: Statistical Mechanics and its Applications, 357(3-4):593–612.

Dekker, A. H. and Colbert, B. D. (2004).Network robustness and graph topology.In Estivill-Castro, V., editor, ACSC, volume 26 of CRPIT, pages 359–368.Australian Computer Society.

Skiena, S. S. (2008).The Algorithm Design Manual.Springer, 2nd edition.


RoteiroIntroducao



Referencias

Referencias II

Wasserman, S., Faust, K., and Iacobucci, D. (1994).Social Network Analysis : Methods and Applications (Structural Analysis in theSocial Sciences).Cambridge University Press.


Technology

Medindo a robustez de uma rede com o fator de resiliência presentation ciawi2009