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 PatrignaniMaurizio Pizzonia

28 Maggio 2003

2

Background: Autonomous Systems e BGP

3

STOP

Background: Autonomous Systems e BGP

AS1 AS2

193.204.161.0/24

Dati per 193.204.161.0/24

AS3193.204.161.0/24

TabellaBGP

TabellaBGP

TabellaBGP

4

Relazioni tra Autonomous Systems

Provider

Customer

Provider

Customer

Provider

Customer

5

Relazioni tra Autonomous Systems

Peer

Peer

6

Inferenza delle relazioni

7

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

8

Un ambiente per l’analisi dell’evoluzione

•Efficace•Flessibile•Affidabile•Portabile•Chiaro

•Modulare

9

Architettura dell’ambiente (TORQUE)

File1Nodi

File2Archi

File3Orientazioni

.

.

.

File File

Generatore di grafi

differenziali

File

…

File

File4AS path

Generatoredi grafi

Analizzatoredi grafi

TabellaBGP

Estrattore di AS path

File FileFileFile File

Principio di utilizzo

…

TabellaBGP

Estrattore di AS path

Algoritmo di inferenza

ListaAS path

OrientazioneGeneratore di grafi

File

TabellaBGP

Estrattore di AS path

Algoritmo di inferenza

Generatore di grafi

File

ListaAS path

Orientazione

TabellaBGP

Estrattore di AS path

Algoritmo di inferenza

Generatore di grafi

File

ListaAS path

Orientazione

…

FileFile

Generatore di grafi differenziali

Generatore di grafi differenziali

Analizzatore di grafi

Analizzatore di grafi

11

Esempio di utilizzo

•Linux•C++

[max@gabbiano tesi]$[max@gabbiano tesi]$ ./tmakeGraph --file:pnec all.paths \> --file:sd finalAssignment.1 -o final1.graph[max@gabbiano tesi]$ ./tmakeGraph --file:pnec all.paths \> --file:sd finalAssignment.1 -o final1.graphtmakeGraph 1.0Reading nodes, edges, path covering file (step 1 of 2)`all.paths‘[********** ] ( 29.0 %)

[max@gabbiano tesi]$ ./tmakeGraph --file:pnec all.paths \> --file:sd finalAssignment.1 -o final1.graphtmakeGraph 1.0Reading nodes, edges, path covering file (step 1 of 2)`all.paths‘[****************************** ] ( 79.0 %)

[max@gabbiano tesi]$ ./tmakeGraph --file:pnec all.paths \> --file:sd finalAssignment.1 -o final1.graphtmakeGraph 1.0Reading nodes, edges, path covering file (step 1 of 2)`all.paths‘[****************************************] (100.0 %)

[max@gabbiano tesi]$ ./tmakeGraph --file:pnec all.paths \> --file:sd finalAssignment.1 -o final1.graphtmakeGraph 1.0Reading nodes, edges, path covering file (step 1 of 2)`all.paths‘[****************************************] (100.0 %)Reading edge directions file (step 2 of 2)`finalAssignment.1‘[*********** ] ( 30.0 %)

[max@gabbiano tesi]$ ./tmakeGraph --file:pnec all.paths \> --file:sd finalAssignment.1 -o final1.graphtmakeGraph 1.0Reading nodes, edges, path covering file (step 1 of 2)`all.paths‘[****************************************] (100.0 %)Reading edge directions file (step 2 of 2)`finalAssignment.1‘[****************************** ] ( 80.0 %)

[max@gabbiano tesi]$ ./tmakeGraph --file:pnec all.paths \> --file:sd finalAssignment.1 -o final1.graphtmakeGraph 1.0Reading nodes, edges, path covering file (step 1 of 2)`all.paths‘[****************************************] (100.0 %)Reading edge directions file (step 2 of 2)`finalAssignment.1‘[****************************************] (100.0 %)Saving graph to file...

[max@gabbiano tesi]$ ./tmakeGraph --file:pnec all.paths \> --file:sd finalAssignment.1 -o final1.graphtmakeGraph 1.0Reading nodes, edges, path covering file (step 1 of 2)`all.paths‘[****************************************] (100.0 %)Reading edge directions file (step 2 of 2)`finalAssignment.1‘[****************************************] (100.0 %)Saving graph to file...[max@gabbiano tesi]$

[max@gabbiano tesi]$[max@gabbiano tesi]$ ./tdiffGraph final1.graph \> final2.graph[max@gabbiano tesi]$ ./tdiffGraph final1.graph \> final2.graphtdiffGraph 1.0Reading graph file `final1.graph'...

[max@gabbiano tesi]$ ./tdiffGraph final1.graph \> final2.graphtdiffGraph 1.0Reading graph file `final1.graph'...Reading graph file `final2.graph'...

[max@gabbiano tesi]$ ./tdiffGraph final1.graph \> final2.graphtdiffGraph 1.0Reading graph file `final1.graph'...Reading graph file `final2.graph'...Computing differences...Nodes in 1st graph: 10909- only in 1st graph: 1289Nodes in 2nd graph: 12708- only in 2nd graph: 3088Common nodes: 9620Edges in 1st graph: 23817- peering: 0- directed: 23776- unoriented: 41

- only in 1st graph: 7873 * peering: 0 * directed: 7850 * unoriented: 23Edges in 2nd graph: 27555- peering: 0- directed: 27530- unoriented: 25- only in 2nd graph: 11611 * peering: 0 * directed: 11593 * unoriented: 18Common edges: 15944- oppositely dir.: 801- differently dir.: 801- consistently dir.: 15118

12

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

13

Algoritmo di inferenza:ottimizzazione

• Individuazione di operazioni critiche (profiling)

• Ottimizzazione– Copie aggiornamenti– Correzione del test di

soddisfacibilità

1-2 oreIn seguito all’ottimizzazione

17-24 orePrima dell’ottimizzazione

Tempo totale per una computazione

14

Sperimentazione su situazioni significative

•Prove:–Stabilità–Coerenza

1 http://www.cs.berkeley.edu/~sagarwal/research/BGP-hierarchy2 http://archive.routeviews.org/oix-route-views3 http://www.isp-planet.com; http://www.internetnews.com

•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)

15

Risultati della sperimentazioneSettimana 25-31/03/03

0 %

10 %

20 %

30 %

40 %

50 %

60 %

70 %

80 %

90 %

100 %

0 % 20 % 40 % 60 % 80 % 100 %

Durata orientazione (percentuale degli snapshot)

Arc

hi

(perc

en

tuale

del

tota

le n

el

gra

fo u

nio

ne)

98 %

16

0 %

10 %

20 %

30 %

40 %

50 %

60 %

70 %

80 %

90 %

100 %

0 % 20 % 40 % 60 % 80 % 100 %

Durata orientazione (percentuale degli snapshot)

Arc

hi

(perc

en

tuale

del

tota

le n

el

gra

fo u

nio

ne)

CDF

Risultati della sperimentazioneSettimane 25/09/01-08/10/01

17

0,00E+00

2,00E+09

4,00E+09

6,00E+09

8,00E+09

1,00E+10

1,20E+10

1,40E+10

0 % 20 % 40 % 60 % 80 % 100 %

Percentuale di cambiamenti di orientazione

Dim

en

sio

ne s

pazio

di

ind

iriz

zam

en

to (

08

/1

0/

01

22

:00

)

CDF

Risultati della sperimentazione

18

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