Caracterização de Redes Complexas
Aplicação à Modelagem Relacionalentre Sistemas Autônomos da Internet
Caracterização de Redes Complexas
Aplicação à Modelagem Relacionalentre Sistemas Autônomos da Internet
Nilton Alves Jr.Nilton Alves Jr.
2
1. Motivação2. Redes de Conexão3. Modelos de Crescimento4. Topologia da Internet5. Evolução Temporal da Internet6. Algoritmo Friburgo7. Conclusões
1. Motivação2. Redes de Conexão3. Modelos de Crescimento4. Topologia da Internet5. Evolução Temporal da Internet6. Algoritmo Friburgo7. Conclusões
Con
teúd
o
3
1. M
otiv
ação
• “Why we don’t know how to simulate the Internet”(Paxson/Floyd 97)
• “Why we don’t know how to simulate the Internet”(Paxson/Floyd 97)
•Modelagem do Crescimento da Internet
• Caracterização da Internet mundial e nacional
• Aquisição de know-how no tema Redes Complexas
• Fornecer um “acelerador de partículas” para Física Estatística
•Modelagem do Crescimento da Internet
• Caracterização da Internet mundial e nacional
• Aquisição de know-how no tema Redes Complexas
• Fornecer um “acelerador de partículas” para Física Estatística
ObjetivosObjetivos
4
2. R
edes
de
Con
exão
Tipos de redes complexas:
Redes Sociais
Redes Tecnológicas
Redes Biológicas
Redes de Informação
Tipos de redes complexas:
Redes Sociais
Redes Tecnológicas
Redes Biológicas
Redes de Informação
Problema das pontes de Konigsberg
Leonhard Euler, 1735
Problema das pontes de Konigsberg
Leonhard Euler, 1735
5
2.1.
Sis
tem
as C
ompl
exos
“Um sistema é tão mais complexo quanto maior o número de informações para descrevê-lo.”
“Um sistema é tão mais complexo quanto maior o número de informações para descrevê-lo.”
partes que se relacionam/interagem entre si
adaptação ao meio
emergência >> criação espontânea de ordem a partir de estados de desordem >> propriedades emergentes
criticalidade auto-organizada, estrutura fractal, nãolinearidade
leis de potência: y α axb
partes que se relacionam/interagem entre si
adaptação ao meio
emergência >> criação espontânea de ordem a partir de estados de desordem >> propriedades emergentes
criticalidade auto-organizada, estrutura fractal, nãolinearidade
leis de potência: y α axb
CaracterísticasCaracterísticas
2.3.
Inte
rnet
–Q
ual o
tipo
de
rede
? Internet: milhares de ASs conectados de maneira aleatória (!?) ou organizada (!!)Internet: milhares de ASs conectados de maneira aleatória (!?) ou organizada (!!)
8
1
( ) ( ) ii N
jj
kP k k P kk
γ−
=
∝ =
∑
3.1.
Mod
elo
Bar
abás
i-Alb
ert crescimento contínuo
conexão preferencial linear
crescimento contínuo
conexão preferencial linear
3γ =
CaracterísticasCaracterísticas
9
3.2.
Mod
. Bar
abás
i-Alb
ertE
sten
dido
1
( )( ) , 1( )
ii N
ij
k AP k Ak A
=
+= =
+∑
crescimento contínuo
conexão preferencial linear
(prob ≤ p) nova conexão entre nós já existentes
(p < prob ≤ p+q) rearranjo entre nós já existentes
(prob > p+q) inclusão simples
crescimento contínuo
conexão preferencial linear
(prob ≤ p) nova conexão entre nós já existentes
(p < prob ≤ p+q) rearranjo entre nós já existentes
(prob > p+q) inclusão simples
CaracterísticasCaracterísticas
10
3.3.
Mod
elo
Dor
ogov
tsev
-Men
des
1
( ) ( ) ii N
jj
kP k k P kk
γ−
=
∝ =
∑ 121 2C
γ = ++
crescimento contínuo
conexão preferencial linear
C>0, conexões incluídas
C<0, conexões removidas
crescimento contínuo
conexão preferencial linear
C>0, conexões incluídas
C<0, conexões removidas
CaracterísticasCaracterísticas
11
3.4.
Mod
elo
Zhou
-Mon
drag
ón
1
( ) ii N
jj
kP kk
α
α
=
=
∑ Testado na matriz adjacênciaobtida por traceroute.
Testado na matriz adjacênciaobtida por traceroute.
crescimento contínuo
conexão preferencial não linear
(prob ≤ p) nova conexão entre nós já existentes
crescimento contínuo
conexão preferencial não linear
(prob ≤ p) nova conexão entre nós já existentes
CaracterísticasCaracterísticas
12
3.5.
Mod
elo
Pro
post
o
1
( ) ii N
jj
kP kk
α
α
=
=
∑
crescimento contínuo
conexão preferencial não linear
(prob ≤ p) nova conexão entre nós já existentes
(p < prob ≤ p+q) rearranjo entre nós já existentes
(prob > p+q) inclusão simples
crescimento contínuo
conexão preferencial não linear
(prob ≤ p) nova conexão entre nós já existentes
(p < prob ≤ p+q) rearranjo entre nós já existentes
(prob > p+q) inclusão simples
CaracterísticasCaracterísticas
15
4.2.
Tab
ela
BG
P F
ullR
outin
g arquivos 40MB (1998) a 704MB (2007)
desenvolvimento de softwares de (pré) tratamento de dados
ASNs existentes, # ASNs vizinhos de cada ASN
RedeRio/FAPERJ e University of Oregon
arquivos 40MB (1998) a 704MB (2007)
desenvolvimento de softwares de (pré) tratamento de dados
ASNs existentes, # ASNs vizinhos de cada ASN
RedeRio/FAPERJ e University of Oregon
CaracterísticasCaracterísticas
… … …*> 8.15.3.0/24 200.179.69.29 0 4230 701 3356 23249 i*> 8.15.5.0/24 200.179.69.29 0 4230 701 6395 26049 26049 26049 26049 i*> 9.4.0.0/16 200.143.254.17 0 1916 3549 559 i* 200.179.69.29 0 4230 3549 559 i*> 12.0.0.0/9 200.143.254.17 0 1916 3549 7018 i* 200.179.69.29 0 4230 701 7018 i* 12.0.0.0 200.143.254.17 0 1916 3549 7018 i*> 200.179.69.29 0 4230 701 7018 i... ... ...
… … …*> 8.15.3.0/24 200.179.69.29 0 4230 701 3356 23249 i*> 8.15.5.0/24 200.179.69.29 0 4230 701 6395 26049 26049 26049 26049 i*> 9.4.0.0/16 200.143.254.17 0 1916 3549 559 i* 200.179.69.29 0 4230 3549 559 i*> 12.0.0.0/9 200.143.254.17 0 1916 3549 7018 i* 200.179.69.29 0 4230 701 7018 i* 12.0.0.0 200.143.254.17 0 1916 3549 7018 i*> 200.179.69.29 0 4230 701 7018 i... ... ...
Tabela Full Routing BGPTabela Full Routing BGP
16
4.2.
Mat
riz A
daja
cênc
ia
MA é uma forma de representação de um GRAFO
Linhas (l) e colunas (c) são ASNs
Cada elemento m(l,c) guarda informação da conexão [0, 1]
Neste caso, reduzir MAreal para MAvirtual
MA é uma forma de representação de um GRAFO
Linhas (l) e colunas (c) são ASNs
Cada elemento m(l,c) guarda informação da conexão [0, 1]
Neste caso, reduzir MAreal para MAvirtual
1
2 3
41
2 3
4
AS 1 2 3 41 0 1 1 12 1 0 1 03 1 1 0 04 1 0 0 0
0 1 0 0 1 0 1
1 0 0 0 1 1 0
0 0 0 1 1 0 00 0 1 0 0 0 11 1 1 0 0 1 0
0 1 0 0 1 0 0
1 0 0 1 0 0 0
ASNR ASNVM M
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥ 0 1 0 0 1 0 1⎡ ⎤⎢ ⎥ 1 0 0 0 1 1 0⎢ ⎥⎢ ⎥ ⎢ ⎥0 0 0 1 1 0 0⎢ ⎥ ⎢ ⎥= ⇒ = 0 0 1 0 0 0 1⎢ ⎥ ⎢ ⎥1 1 1 0 0 1 0⎢ ⎥ ⎢ ⎥0 1 0 0 1 0 0⎢ ⎥ ⎢ ⎥1 0 0 1 0 0 0⎣ ⎦⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦
CaracterísticasCaracterísticas
17
4.4.
Top
olog
ia N
acio
nal
• RedeRio/FAPERJ, Fev 2004• Comportamento auto-similar (fractal)• Distribuição de vizinhos: -2,08 e -2,07• Ranque: -1,11 e -1,10• Crescimento linear: 2.261 e 24
• RedeRio/FAPERJ, Fev 2004• Comportamento auto-similar (fractal)• Distribuição de vizinhos: -2,08 e -2,07• Ranque: -1,11 e -1,10• Crescimento linear: 2.261 e 24
21
• BA concorda com a teoria,
• BA estendido e DM concordam com experimentos,
• BA estendido apresenta p e q elevados, para Internet
• DM só considera C>0 ou C<0
• Necessidade de um modelo mais realista
• BA concorda com a teoria,
• BA estendido e DM concordam com experimentos,
• BA estendido apresenta p e q elevados, para Internet
• DM só considera C>0 ou C<0
• Necessidade de um modelo mais realista
4.5.
Mod
elos
Bás
icos
ConclusõesConclusões
2,9γ =2,1γ =
26
6. M
étod
o Fr
ibur
go
O algoritmo é:• robusto• muito rápido• confiável
Implementação em linguagem C/C++Optimizações:
• conceitual• implementação
O algoritmo é:• robusto• muito rápido• confiável
Implementação em linguagem C/C++Optimizações:
• conceitual• implementação
Características
27
6. M
étod
o Fr
ibur
go
N=1000 nós, k=10 conexões
distribuição de conexões: modo regular (p=0) até modoaleatório (p=1)
Repetir Watts & Strogatz (Nature, 1998)
N=1000 nós, k=10 conexões
distribuição de conexões: modo regular (p=0) até modoaleatório (p=1)
Repetir Watts & Strogatz (Nature, 1998)
CaracterísticasCaracterísticas
29
7. C
oncl
usõe
s
Modelos de CrescimentoTopologia NacionalEvolução Topologia MundialEvolução Menor Caminho MédioAgoritmo Friburgo
Modelos de CrescimentoTopologia NacionalEvolução Topologia MundialEvolução Menor Caminho MédioAgoritmo Friburgo
Desenvolvimento FuturoContribuições OriginaisDesenvolvimento FuturoContribuições Originais
30
7. C
oncl
usõe
s
Básicos:• Barabási-Albert• Barabási-Albert estendido• Dorogovtsev-Mendes• Zhou-Mondragón
Proposto:• Crescimento contínuo• Conexão preferencial não linear• Novas conexões• Rearranjo
Básicos:• Barabási-Albert• Barabási-Albert estendido• Dorogovtsev-Mendes• Zhou-Mondragón
Proposto:• Crescimento contínuo• Conexão preferencial não linear• Novas conexões• Rearranjo
1,20 0,01α = ±
exp
2,12,09
simγγ
=⎧⎪⎨ =⎪⎩
Modelos de CrescimentoModelos de Crescimento
31
7. C
oncl
usõe
s
• RedeRio/FAPERJ, Fev 2004• Comportamento auto-similar (fractal)• Distribuição de vizinhos: -2,08 e -2,07• Ranque: -1,11 e -1,10• Crescimento linear: 2.261 e 24
• RedeRio/FAPERJ, Fev 2004• Comportamento auto-similar (fractal)• Distribuição de vizinhos: -2,08 e -2,07• Ranque: -1,11 e -1,10• Crescimento linear: 2.261 e 24
Topologia NacionalTopologia Nacional
32
7. C
oncl
usão
Década: 1998 - 2007Histograma:• Mesmo comportamento linear k<15• Degenerescência k>15• Experimental e simulado -2,00
Ranque:• Mesmo comportamento linear -0,91
Década: 1998 - 2007Histograma:• Mesmo comportamento linear k<15• Degenerescência k>15• Experimental e simulado -2,00
Ranque:• Mesmo comportamento linear -0,91
Evolução da Topologia MundialEvolução da Topologia Mundial
33
7. C
oncl
usõe
s
Menor caminho médio: 4,21Concordância entre os dados experimentais e simulados pelo modelo proposto
Menor caminho médio: 4,21Concordância entre os dados experimentais e simulados pelo modelo proposto
Evolução do MCMEvolução do MCM
34
7. C
oncl
usõe
s
O algoritmo é:• robusto• muito rápido• confiável
Implementação em linguagem C/C++Certificação:• Redes pequenas• Redes grandes• Sistemática Watts/Strogatz
O algoritmo é:• robusto• muito rápido• confiável
Implementação em linguagem C/C++Certificação:• Redes pequenas• Redes grandes• Sistemática Watts/Strogatz
Algoritmo FriburgoAlgoritmo Friburgo
35
7. C
oncl
usõe
s
Modelo proposto:• Coeficiente de cluster• Número de triângulos• Proporção ASs hubs e leafs• Auto(vetores/valores) da MA• Mecânica estatística não extensiva
Algoritmo Friburgo:• Pesos variados• Comparação com métodos tradicionais
Modelo proposto:• Coeficiente de cluster• Número de triângulos• Proporção ASs hubs e leafs• Auto(vetores/valores) da MA• Mecânica estatística não extensiva
Algoritmo Friburgo:• Pesos variados• Comparação com métodos tradicionais
Desenvolvimento FuturoDesenvolvimento Futuro
36
7. C
oncl
usõe
s
Redes de conexões de ASs da Internet:
Comparação Internet nacional e mundial
Evolução temporal da década 98/07
Modelo de crescimento de rede complexa
Método Friburgo para cálculo do MCM total
Redes de conexões de ASs da Internet:
Comparação Internet nacional e mundial
Evolução temporal da década 98/07
Modelo de crescimento de rede complexa
Método Friburgo para cálculo do MCM total
OriginalidadeOriginalidade