UNIVERSITÀ DEGLI STUDI ROMA TRE
Metodi e strumenti per l’analisi
dell’evoluzione dei rapporti tra
fornitori e fruitori di servizi di
connettività in Internet
Candidato:
Massimo Rimondini
Relatore:
prof. Giuseppe Di Battista
Correlatori: Maurizio Patrignani
Maurizio Pizzonia
28 Maggio 2003
Background: Autonomous
Systems e BGP
2
Background: Autonomous
Systems e BGP
Tabella
BGP
Tabella
BGP
Dati per 193.204.161.0/24
AS1
AS2
193.204.161.0/24
STOP
193.204.161.0/24
Tabella
BGP
AS3
3
Relazioni tra Autonomous
Systems
Provider
Customer
Provider
Provider
Customer
Customer
4
Relazioni tra Autonomous
Systems
Peer
Peer
5
Inferenza delle relazioni
6
Inferenza delle relazioni:
stato dell’arte
• Lixin Gao, 2000: Grado degli AS
• Subramanian, Agarwal, Rexford, Katz,
2001: Multiple Vantage Points
• Di Battista, Patrignani, Pizzonia, 2002:
Soddisfacibilità di Formule Logiche
(2—SAT)
Tabelle BGP
7
Un ambiente per l’analisi
dell’evoluzione
•Efficace
•Flessibile
•Affidabile
•Portabile
•Chiaro
•Modulare
8
Architettura dell’ambiente
(TORQUE)
File1
Nodi
Generatore
di grafi
File
File
File
…
File2
Archi
File3
Orientazioni
File4
AS path
.
.
.
Generatore di
grafi
differenziali
Tabella
BGP
Estrattore
di AS path
Analizzatore
di grafi
File
9
Principio di utilizzo
Tabella
Tabella
Tabella
BGP
BGP
BGP
Estrattore
Estrattore
Estrattore
di
AS path
di
di AS
AS path
path
Algoritmo
Algoritmo
Algoritmo
di
inferenza
di
di inferenza
inferenza
Lista
Lista
Lista
AS
path
AS
AS path
path
Generatore
Generatore
Generatore
di
grafi
di
di grafi
grafi
File
File
Generatore di
grafi differenziali
File
Analizzatore di
grafi
File
File
File
Orientazione
Orientazione
Orientazione
File
File
File
…
Generatore di
grafi differenziali
Analizzatore di
grafi
File
Esempio di utilizzo
- only in 1st tesi]$
[max@gabbiano
graph: ./tdiffGraph
7873
final1.graph \
> *
final2.graph
peering:
0
tdiffGraph
* directed:
1.0
7850
Reading
* unoriented:
graph file `final1.graph'...
23
[max@gabbiano
./tmakeGraph
Reading
Edges
ingraph
2nd tesi]$
graph:
file `final2.graph'...
27555 --file:pnec all.paths \
>--file:sd
finalAssignment.1 -o0 final1.graph
Computing
peering:differences...
tmakeGraph
1.0 graph:
Nodes
directed:
in 1st
10909
27530
Reading
file (step 1 of 2)
- unoriented:
only nodes,
in 1st edges,
graph: path covering
1289
25
`all.paths‘
Nodes
onlyin
in2nd
2ndgraph:
graph:
12708
11611
[**********
[******************************
[****************************************]
( 79.0
29.0 %)
- *
only
peering:
in 2nd graph:
3088
0 •Linux ] (100.0
Reading
edge
directions file11593
(step
2 of 2)
•C++
Common
* directed:
nodes:
9620
`finalAssignment.1‘
Edges
* unoriented:
in 1st graph:
23817
18
[***********
[******************************
[****************************************]
] (100.0
( 80.0
30.0 %)
- peering:
Common
edges:
15944
0
Saving
graph todir.:
file...
- oppositely
directed:
23776
801
[max@gabbiano
- differently
dir.:
801
unoriented:tesi]$
41
- consistently dir.:
15118
11
Algoritmo di inferenza:
scelta ed ottimizzazione
• Lixin Gao:
– implementazione disponibile
• Subramanian, Agarwal, Rexford, Katz:
– implementazione non disponibile
• Di Battista, Patrignani, Pizzonia:
– implementazione disponibile
– possibilità di interagire con gli autori
dell’algoritmo
– ma…
• sviluppato in poco tempo  poco efficiente
12
Algoritmo di inferenza:
ottimizzazione
• Individuazione di
operazioni critiche
(profiling)
• Ottimizzazione
– Copie  aggiornamenti
– Correzione del test di
soddisfacibilità
Tempo totale per una computazione
Prima dell’ottimizzazione
17-24 ore
In seguito all’ottimizzazione
1-2 ore
13
Sperimentazione su situazioni
significative
•Origine dati:
–Sito Subramanian, Agarwal, Rexford, Katz1
•prove con l’algoritmo non ottimizzato
•anomalie nei dati
–Archivio Oregon Route Views2
•indispensabile l’algoritmo ottimizzato
•molti dati disponibili, ad intervalli regolari
•periodo stabile ed instabile (informazioni da 3)
•Prove:
–Stabilità
–Coerenza
1 http://www.cs.berkeley.edu/~sagarwal/research/BGP-hierarchy
http://archive.routeviews.org/oix-route-views
3 http://www.isp-planet.com; http://www.internetnews.com
2
14
Risultati della sperimentazione
Settimana 25-31/03/03
Archi (percentuale del totale nel
grafo unione)
98100
%%
90 %
80 %
70 %
60 %
50 %
40 %
30 %
20 %
10 %
0%
0%
20 %
40 %
60 %
80 %
100 %
Durata orientazione (percentuale degli snapshot)
15
Risultati della sperimentazione
Settimane 25/09/01-08/10/01
Archi (percentuale del totale nel
grafo unione)
100 %
%
90 %
CDF
80 %
70 %
60 %
40 %
50 %
40 %
60
30 %
urata (percentuale deg
20 %
10 %
0%
0%
20 %
40 %
60 %
80 %
Durata orientazione (percentuale degli snapshot)
100 %
16
Dimensione spazio di
indirizzamento (08/10/01 22:00)
Risultati della sperimentazione
1,40E+10
1,20E+10
CDF
1,00E+10
8,00E+09
6,00E+09
4,00E+09
2,00E+09
0,00E+00
0%
20 %
40 %
60 %
80 %
100 %
Percentuale di cambiamenti di orientazione
17
Conclusioni e problemi aperti
•Ambiente funzionale
•Nuove prospettive aperte in
seguito all’ottimizzazione
•Ottima stabilità
– Scarsa sensibilità ad oscillazioni
nelle informazioni di routing
– Oscillazioni quasi soltanto su archi
“poco importanti”
•Grafi delle relazioni
•Exchange points
•Gradi di libertà
•Peering, sibling e backup
•Best practice
18