Uma Análise Conceitual sobre a Reorganização
da Topologia da Internet Provendo Eficiência e
Tolerância a Ataques
Caio Ruan Nichele
Curitiba
30 de Novembro de 2009
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Roteiro
Roteiro
- Introdução
- Motivação
- Trabalhos Relacionados
- Métricas Utilizadas
- Reorganizações Propostas
- Proposta
- Resultados Esperados
Caio Ruan Nichele
2
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Introdução
Introdução
- Topologia Scale Free;
- Alguns nodos ligados a poucos nodos, outros nodos
ligados a muitos nodos (hubs);
- 4 estratégias de reorganização propostas;
- Diminuir o número de saltos entre quaisquer dois
nodos;
- Necessária análise sobre conceitos de scale free.
Caio Ruan Nichele
3
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Motivação
Motivação
- Análise sobre conceitos de scale free;
- Validar Conceitualmente as Reorganizações Propostas;
- Mostrar os benefícios de se utilizar uma Topologia
baseada em Scale Free.
Caio Ruan Nichele
4
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Trabalhos Relacionados
Trabalhos Relacionados
- Y. Sato, S. Ato, I. Oka “A Strategic Approach for Reorganization of Internet Topology for Improving both Efficiency
and Attack Tolerance”, NOMS 2008;
- P. Crucitti, V. Latora, M. Marchiori, A. Rapisarda,
“Efficiency of scale-free networks: error and attack tolerance”,
Physica A, vol. 320, pp. 622–642, March 2003;
- C.-Y. Yin, B.-H. Wang, W.-X. Wang, T. Zhou, and H.-J.
Yang, “Efficient routing on scale-free networks based on local
information”, Physics Letters A, vol. 351, pp. 220–224, May
2006.
Caio Ruan Nichele
5
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Métricas Utilizadas
Métricas Utilizadas
- Coeficiente de Aglomeração
- Mostra como os nodos adjacentes a i se
conectam com os demais;
- Avalia quão disperso um nodo está em relação
aos demais.
l (Gi )
Ci 
ki (ki  1) 2
Caio Ruan Nichele
6
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Métricas Utilizadas
- Eficiência
- Avalia o menor número de saltos entre dois
nodos analisados;
- Redes com maior E(G) são mais eficientes,
porém mais vulneráveis a ataques.
1
1
E (G) 

N N  1 i  jG dij
Caio Ruan Nichele
7
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Métricas Utilizadas
- Acessibilidade
- Enumera a quantidade de nodos acessíveis
dentro de um raio de cobertura;
- A acessibilidade mede a conexidade dos nodos
da rede.
1
R
Rij

N N  1 i  jG
Caio Ruan Nichele
8
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Métricas Utilizadas
- Número de Trajetos Compartilhados
- Esta métrica indica o nível de concentração de
tráfego;
- Sua ação está relacionada ao coeficiente de
aglomeração, porém analisa também a
densidade.
W  maxlD wl
V  maxiN vi
Caio Ruan Nichele
9
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Reorganizações Propostas
Reorganizações Propostas
- Rand-based preference
- Os nodos obtém seu rank de acordo com o
número de links;
Está reorganização consiste em utilizar o rank a
fim de escolher o melhor host para se conectar.

RP
(rI ) 
1
ri  j 1
Caio Ruan Nichele
rj
10
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Reorganizações Propostas
- Exponential distribution based preference
- A probabilidade de escolher um nodo é definido
pela distribuição exponencial;
- São utilizados como parâmetros o rank,
juntamente com mudanças significativas da rede.

(
r
)


e
I
EDP
Caio Ruan Nichele
 ri
11
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Reorganizações Propostas
- Gamma distribution based preference
- A probabilidade de escolher um nodo é definido
pela distribuição gamma;
- Estratégia consiste em buscar conexões com
nodos de baixo rank, uma vez que suas
probabilidades são praticamente zero.
e  ri  k 1
GDP (rI )  (k ) k ri , k ,  0
Caio Ruan Nichele
12
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Reorganizações Propostas
- Rank-based random selection
- O nodo é selecionado através de uma lista M de
nodos com alto rank;
- O número de hubs aumenta conforme tamanho
de M, porém caso seu número aumente, é fixado
o valor M.
Caio Ruan Nichele
13
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Proposta
Proposta
- Para validar tal reorganização, é necessário validar
conceitualmente se as características de scale free estão sendo
empregadas;
- É necessário tal análise, uma vez que a Eficiência e a
Tolerância a Ataques são conseqüências da topologia
empregada;
- Análise consiste em:
- Buscar conceitos sobre a topologia Scale Free;
- Verificar cada etapa, entre as métricas, até as
estratégias de reorganização.
Caio Ruan Nichele
14
Uma Análise Conceitual sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
-> Resultados Esperados
Resultados Esperados
- É esperado que os conceitos tenham relação ao
proposto pelo artigo inicial, isto é, o resultado terá maior valor,
uma vez que terá maior embasamento teórico;
- Caso as estratégias não estejam seguindo os conceitos,
serão feitas sugestões de melhoria.
Caio Ruan Nichele
15
Uma Análise sobre a Reorganização da
Topologia da Internet Provendo Eficiência e Tolerância a Ataques
OBRIGADO !
Caio Ruan Nichele
16