View
31
Download
1
Category
Preview:
Citation preview
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
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]
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
Load-balancing vs évolution du routage
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 lie
ns IP
Date
pas d'évolution du routage
11
Load-balancing vs évolution du routage
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 lie
ns IP
Date
12
Load-balancing vs évolution du routage
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 lie
ns IP
Date
pente
load-balancing
dynamique structurelle+ load-balancing
+ dynamique structurelle
évolution du routage
évolution du routage
13
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
Load-balancing vs évolution du routage
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
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
Un graphe aléatoire G (n,m)avec n nœuds et m liens
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
Un graphe aléatoire G (n,m)avec n nœuds et m liens
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
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
u v
23
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
u v
23
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
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 ???Un “trou” ?
26
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
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
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
Recommended