Analyse empirique et modélisation de la dynamique de la topologie de l’Internet

Analyse empirique et modélisation de ladynamique de la topologie de l’Internet

Sergey KirgizovDirectrice de thèse: Clémence Magnien

Complex Networks, LIP6, (UPMC, CNRS)

Paris, 12 décembre 2014

Plan

1 Introduction

2 Mesures égo-centrées

3 Modèle

4 Caractérisation de la dynamique

5 Taille du sous-graphe observable

6 Dynamique réelle et dynamique observée

7 Conclusion et perspectives

2

Introduction :l’Internet, étude de la topologie de l’Internet

Carte de l’Internet // Barrett Lyon, 2003

Topologie au niveau IP

Mon ordinateur

paris.fr lip6.fr

Nœuds : ordinateursLiens : connections IP

4

Petite note historique

temps

1960s — ARPANET1980s — Internet1993 — Dynamics of internet routing information

[Chinoy]1997 — Measurements and Analysis of End-to-End Internet Dynamics

[Paxon]1998 — On routes and multicast trees in the Internet

[Pansiot et Grad]2000s — de nombreux travaux sur la topologie

(et la dynamique) de l’Internet à grande échelleseulement quelques œuvres considèrent l’échelle fine

5

Étude de la topologie de l’Internet

Pas de carte officielle de l’Internet

Une carte statique ?Mesures longues et coûteuses;Biais sur la structure observée.

}=⇒Pas de carte fiable

Étude de la dynamique ?Tous les problèmes statiques;Répéter les mesures

}=⇒Pas si facile

6

Mesures égo-centrées :Routes entre un moniteur et plusieurs destinations fixes

[Latapy, Magnien, Ouédraogo, 2011]

Vues ego-centrées

m

d1 d2

Carte complète

7

Vues ego-centrées

m

d1 d2

Routes entre un moniteur et des destinations

7

Vues ego-centrées

m

d1 d2

Une mesure par l’outil tracetree[Latapy, Magnien, Ouédraogo, 2011]

7

Vues ego-centrées

m

d1 d2

Une autre mesure par l’outil tracetree

7

Vues ego-centrées

m

d1 d2

Une autre mesure par l’outil tracetree

7

Dynamique des vues ego-centrées

m

d1 d2

m

d1 d2

m

d1 d2

Temp

Mesures périodiques rapides =⇒ étude de la dynamique

8

Caractérisation de la dynamique

Mesures : M1, M2, . . . , Mi , . . .

Nombre de liens vus depuis le début : t 7→

∣∣∣∣∣∣

⋃

i∈[0,t ]

Mi

∣∣∣∣∣∣# liens

0

20000

40000

60000

80000

100000

120000

140000

160000

180000

200000

220000

Sep Oct Nov Dec J an Feb Mar Apr May J un J ul Aug Sep Oct

Nom

bre

de li

ens

IP

Date

1ère — 9 938 liens

2ème — 11 149 liens

dernière — 207 782

3000 destinationsune mesure toutes les 15 minutes pendant 1 an

découverte en permanence de nouveaux liens IPà une vitesse élevée

9

Causes de la dynamique observée

Causes

Load-balancingM DL

Évolution du routageM D

10

Load-balancing vs évolution du routage

0

20000

40000

60000

80000

100000

120000

140000

160000

180000

200000

220000


Nom

bre

de lie

ns IP

Date

pas d'évolution du routage

11


0

20000

40000

60000

80000

100000

120000

140000

160000

180000

200000

220000


Nom

bre

de lie

ns IP

Date

12


0

20000

40000

60000

80000

100000

120000

140000

160000

180000

200000

220000


Nom

bre

de lie

ns IP

Date

pente

load-balancing

dynamique structurelle+ load-balancing

+ dynamique structurelle

évolution du routage

évolution du routage

13

Modèle :Load-balancing + évolution du routage

Modélisation

Topologie : Graphe aléatoire (Erdős-Rényi ou configurationmodel)

Un nœud aléatoire −→ moniteurd nœuds aléatoires −→ destinations

Mesure : plus courts chemins (aléatoires) M L

Evolution du routage : “échange de liens”

14


Nombre de liens distincts vus depuis le début de la mesure

1000

2000

3000

4000

5000

6000

7000

0 500 1000 1500 2000 2500 3000

Nom

bre

de lie

ns

Nombre de passes

pente

load-balancing

évolution du routage+ load-balancing

+ évolution du routage

15

Caractérisationde la dynamique :la pente d’évolution

[Magnien, Medem, Kirgizov et Tarissan, 2013]

La pente

0

10000

20000

30000

40000

50000

60000

70000

Sep Oct Nov Dec Jan Feb Mar Apr May Jun Jul Aug Sep Oct

Nom

bre

de lie

ns

Date

y = α x + β

α est la pente de la partie linéaire

16

α = f (paramètres du modèle)nombre total de liens

0

10000

20000

30000

40000

50000

60000

70000

80000

0 500 1000 1500 2000 2500 3000

# lie

ns

# rounds

m = 200 000

m = 800 000

m = 1200 000

Impact du nombre total de liensGraphes Erdős–Rényi (n = 100 000, d = 100, sw = 100)

17

α = f (paramètres du modèle)nombre total de destinations

0

20000

40000

60000

80000

100000

120000

0 500 1000 1500 2000 2500 3000

# lie

ns

# rounds

d = 500

d = 300

d = 100

Impact du nombre de destinationsGraphes Erdős–Rényi (n = 100 000, m = 200 000, sw = 100)

18

α = f (paramètres du modèle)

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

200000 400000 600000 800000 1e+06

α

m

d500200100

Un graphe aléatoire G (n,m)avec n nœuds et m liens

d nœuds comme destinations

19

La taille du sous-graphe des plus courts cheminscette taille augmente avec le nombre de destinations

α ∝ |sous-graphe||graphe| =

Sl

m

20

Impact de la taille du sous-graphe des plus courts chemins

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

200000 400000 600000 800000 1e+06

α

m

d500200100


d nœuds aléatoires commedestinations

α ≈ KSl

m

21

Impact de la taille du sous-graphe des plus courts chemins

0

5e-05

0.0001

0.00015

0.0002

0.00025

200000 400000 600000 800000 1e+06

α Sl

m


d nœuds aléatoires commedestinations

α ≈ KSl

m

21

Caractérisation de la dynamiqueConclusion

Erdős–Rényi : α ≈ KSlm

Power-law : α ≈ K ′Slm

Prévoir la pente sans exécuter les simulations coûteuses

Quelques comportements non linéaires et non-monotones

Comparison aux mesures réelles

Probabilité d’un changement à la place de la pente

22

La taille du sous-graphedes plus courts chemins :1 moniteur, 1 destination

[Kirgizov et Magnien, soumis]

Graphes aléatoires

G (n,p) est un graphe aléatoire à n sommets. Chacune desn(n − 1)/2 arêtes est présente avec probabilité p.

1951–1952 Solomonoff et Rapoport1959 Gilbert, Erdős et Rényi

SPS : sous-graphe des plus courts cheminsS : taille du sous-graphe des plus courts chemins

23

Graphes aléatoires




u v

23

Graphes aléatoires




u v

23

Graphes aléatoires




u v

23

Proportion des liens qui se trouvent sur les plus courts chemins

Graphe Erdős-Rényi (n = 1000).Proportion des liens sur les plus courts chemins.Tous les noeuds sont les destinations.

[Guillaume et Latapy, 2005][Blondel, Guillaume, Hendrickx et Jungers, 2007]

24

Taille moyenne de SPS dans des graphes aléatoires

Fixons np 7→ E[S ]

0.0 0.2 0.4 0.6 0.8 1.0

220

40

60

80

p

E [S

]

25

Moyenne et tailles réelles de SPS

Fixons np 7→ {S}

0.0 0.2 0.4 0.6 0.8 1.0

2200

400

p

S

26

Moyenne et tailles réelles de SPS

Fixons np 7→ {S}

0.0 0.2 0.4 0.6 0.8 1.0

2200

400

p

S ???Un “trou” ?

26

Graphe complet : Kn

p = 1

Kn

SPS(u, v ) =u v

S(u, v ) = 2

27

Graphe quasi-complet : Kn − ab

p = 1− ε

a bKn−2

S(u, v ) ={n si {u, v} = {a, b} ,2 sinon .

Si n > 3, alors il y a un “trou”.

0.0 0.2 0.4 0.6 0.8 1.0

2200

400

p

S ici

28

Taille du SPS dans des graphes aléatoires

0.0 0.2 0.4 0.6 0.8 1.0

22

00

40

0

p

S

29

Taille du SPS dans des graphes aléatoires

0.0 0.2 0.4 0.6 0.8 1.0

22

00

40

0

p

S

dist=1

dist=2

dist=3dist=4

Y :nombre de nœuds qui sont directement liés à la fois à u et vY ∼ B(n − 2, p2)

29

Taille du SPS dans des graphes aléatoireséchelle logarithmique

1e−04 1e−03 1e−02 1e−01 1e+00

25

10

20

50

10

05

00

p

S

dist=1

dist=2

dist=3

30

Conclusion

Prévoir la taille du sous-graphe observable sans exécuter lessimulations coûteuses

Oscillations ont été expliquées

dist(u,v) = 2 : la loi exacte

dist(u,v) > 2 : une approximation de la taille attendue

31

Dynamique réelle etdynamique observée :

[Kirgizov, Magnien, Tarissan, Liu, 2013][Kirgizov et Queyroi, preprint, 2014]

α = f (∆)

0

10000

20000

30000

40000

50000

60000

70000

Sep Oct Nov Dec Jan Feb Mar Apr May Jun Jul Aug Sep Oct

Nom

bre

de lie

ns

Date

∆1 = 1m 25s

∆2 = 2m 50s

α = f (∆), où ∆ est le délai entre les mesuresα(∆1) > α(∆2)

32

α = f (∆)

0

10000

20000

30000

40000

50000

60000

70000

Nom

bre

de lie

ns

Date

∆1 = 1m 25s

∆2 = 2m 50s

RéalitéA→ . . .→ B → . . .→ C

∆1

A→ B → C

∆2

A→ C

|A ∪ C | ≤ |A ∪ B ∪ C |∆1 ≤ ∆2 ⇒⇒ α(∆1) ≥ α(∆2)

33

Situation attendueα

∆

∆m

αm

αm est la pente maximale possible

34

Autre approche. Estimation du taux dechangements

Changements 〈X 〉: ◦′ ◦′′ ◦′′′ · · ·

Observations 〈Y 〉: •′ •′ •′′ · · ·pas de changement

changement

Question : estimer le taux des changements réelsPoisson paramétré par λ

λ 〈X 〉

〈Y 〉?

35

Estimateur

λ̂ = −∆−1 logW

N,

où

∆ – taille de l’intervalle de temps entre les observations ;W – nombre d’intervalles sans changement ;N – nombre total d’intervalles .

E[λ̂− λ

]≈ 1

2N∆

(eλ∆ − 1

)

limN→∞

E[λ̂]

= λ

36

λ estimée en fonction de ∆

0 2 4 6 8

0.04

0.06

0.08

∆

λ̂

Processus de Poisson

0 2 4 6 8

0.04

0.06

0.08

∆λ̂

Modèle avec un graphesous-jacent Erdős-Rényi, SPSest mesurée à chaque round.

37

λ estimée en fonction de ∆

0 50 100 150 200 250 300

0.00

0.02

0.04

0.06

0.08

∆

λ̂

Erdős-Rényi

0 50 100 150 200 250 300

0.00

0.02

0.04

0.06

0.08

∆

λ̂

Power-law

0 20 40 60 80 100

0.0

0.5

1.0

1.5

2.0

∆

λ̂

Mesures réelles

λ̂ pour SPT (m

d1 d2

) et SPS (m

d1 d2

) séquences.

38

Estimation de λConclusion

� Processus de Poisson =⇒ estimation possible

� Les autres cas ouvrent des directions de la recherche future.

39

Conclusion

� Modèle de la dynamique de l’Internet

� Relations entre les paramètres du modèle et lescaractéristiques de la dynamique

� La taille du sous-graphe des plus courts chemins

� Estimation du taux de changements

40

Perspectives

� Améliorer le modèle

� Etude plus approfondie de la taille du sous-grapheobservable

� Appliquer les méthodes développées à d’autres réseaux

41

Merci beaucoup

http://kirgizov.complexnetworks.fr/

http://kirgizov.complexnetworks.fr/

Science

Analyse empirique et modélisation de la dynamique de la topologie de l’Internet