[PDF] Prévalence de la fibrose hépatique et de la cirrhose chez les

View - Download Prévalence de la fibrose hépatique et de la cirrhose chez les

Previous PDF

Next PDF

Γ>ΓσΓG ΓAΓ/Γ, ΓiΓ2ΓHΓ∂ΓyΓjΓeΓeΓeΓdΓdΓR

T m # H B + b Q m T ' B p û b X

ΓJΓQΓ/ΓûΓHΓBΓbΓτΓiΓBΓQΓM Γ?ΓQΓ?ΓmΓbΓiΓ2 Γ/Γm Γ/ΓûΓHΓτΓB ΓAΓMΓiΓ2Γ?ΓMΓ2Γi Γ2Γi ΓbΓ+Γ?ΓûΓKΓτΓb Γ/Γ2

ΓQΓpΓ2Γ?ΓHΓτΓv

ΓJΓτΓtΓBΓKΓ2 ΓJΓQΓmΓ+Γ?Γ2Γi ΓhΓQ Γ+ΓBΓiΓ2 ΓiΓ?ΓBΓb ΓpΓ2Γ?ΓbΓBΓQΓMΓ,

THESE DE DOCTORAT DE L'ÉCOLE NATIONALE SUPERIEURE MINES-TELECOM ATLANTIQUE BRETAGNE PAYS DE LA LOIRE - IMT ATLANTIQUE ECOLE DOCTORALE N° 601 Mathématiques et Sciences et Technologies de l'Information et de la Communication Spécialité : Informatique

Modélisation Robuste du Délai Internet et Schémas de Mesure Intelligents pour l'Automatisation des Réseaux Overlay Thèse présentée et soutenue en visioconférence, le 27 novembre 2020

Unité de recherche : Lab-STICC

Thèse N° : 2020IMTA0209

Par

Maxime MOUCHET

Rapporteurs avant soutenance :

Mme. Hind CASTEL-TALEB Professeure Télécom SudParis M. Kavé SALAMATIAN Professeur Université Savoie Mont Blanc

Composition du Jury :

Président : Mme. Cristel PELSSER Professeure Université de Strasbourg Examinateurs : Mme. Hind CASTEL-TALEB Professeure Télécom SudParis M. Kavé SALAMATIAN Professeur Université Savoie Mont Blanc M. Emmanuel HYON Maître de conférences Sorbonne Université Mme. Cristel PELSSER Professeure Université de Strasbourg M. Jean-Louis ROUGIER Professeur Télécom Paris Dir. de thèse : Mme. Sandrine VATON Professeure IMT Atlantique Co-encadrant : M. Thierry CHONAVEL Professeur IMT Atlantique

Invité :

M. Olivier BRUN Directeur de recherche LAAS-CNRS REMERCIEMENTSJe me dois de remercier en premier mes encadrants, Sandrine et Thierry. Merci pour votre bienveillance, votre disponibilité et les connaissances que vous m"avez transmises. Je n"aurais pas imaginé faire de thèse dans de meilleures conditions. Je remercie également les membres du jury, Mme Hind Castel-Taleb, professeure, M. Kavé Salamatian, professeur, M. Emmanuel Hyon, maître de conférences, Mme Cristel Pelsser, professeure, M. Jean-Louis Rougier, professeur, et M. Olivier Brun, directeur de recherche CNRS, d"avoir accepté d"évaluer mes travaux. Il n"y aurait évidemment pas de thèse sans financement. Merci à l"Institut Mines-Télécom, à la Fondation Mines-Télécom et au Carnot Télécom & Société d"avoir financé ma thèse au travers du programme Futur & Ruptures. Merci également au RIPE NCC, à l"IFIP, au NL-ix et au GDR RSD d"avoir financé les déplacements aux conférences. Durant ces trois années, j"ai eu la chance de pouvoir collaborer avec de nombreuses personnes, en France et à l"étranger : Bala, Emile, Isabel, Jasper, Marine, Martín, Olivier et Pablo. Merci à vous! En particulier, merci à Pablo et Claudina de m"avoir accueilli un mois à l"Universidad de la Repúblicaà Montévidéo, et à Robert et Emile pour m"avoir accueilli un mois au RIPE NCC à Amsterdam. Si ma thèse a pu se dérouler sans encombre, c"est grâce à l"aide infaillible d"Armelle. Merci pour tout le temps passé sur les procédures administratives. Merci à mes amis : Jean-Baptiste pour m"avoir convaincu de pour- suivre en thèse; Maxime pour tous les moments passés à refaire le monde; Yann et Johann pour nos conversations sans fin; David pour nos séances de running; Stéphane, Noémie, Geoffrey et Vanessa pour nos week-ends marins bien mérités. Merci à mes parents et à mes grands-parents de m"avoir intéressé à la science dès le plus jeune âge, et de m"avoir permis de poursuivre les études de mon choix dans les meilleures conditions. Enfin, merci Fiona pour ta patience et ton soutien sans faille lors de cette dernière année de thèse. Bien sûr, il m"est impossible de citer toutes les personnes m"ayant permis d"obtenir mon doctorat, tant nous sommes le produit de nos rencontres et de nos discussions tout au long de notre vie. Merci à toutes les personnes que j"ai pu rencontrer d"avoir partagé vos idées, vos connaissances et vos opinions et de m"avoir permis de devenir la personne que je suis. C"est bien beau tout ça mais, Internet, ça se mange? - Kinder le chat

TABLE DES MATIÈRES

1 introduction

1

1.1Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . .1

1.2Contributions . . . . . . . . . . . . . . . . . . . . . . . .1

1.3Structure de la thèse . . . . . . . . . . . . . . . . . . . .2

2modélisation du délai avec des modèles de mar-

kov cachés non paramétriques 3

2.1Problème . . . . . . . . . . . . . . . . . . . . . . . . . . .3

2.2Modèles existants . . . . . . . . . . . . . . . . . . . . . .4

2.2.1Observations indépendantes . . . . . . . . . . .5

2.2.2Modèles autorégressifs et réseaux de neurones .6

2.2.3Modèles de Markov cachés . . . . . . . . . . . .6

2.3Modèles de mélange non paramétriques . . . . . . . . .7

2.3.1Modèles de mélange . . . . . . . . . . . . . . . .7

2.3.2Processus de Dirichlet . . . . . . . . . . . . . . .14

2.3.3 Modèles de mélange à base de processus de Dirichlet . . . . . . . . . . . . . . . . . . . . . . .16

2.4Modèles de Markov cachés non paramétriques . . . . .18

2.4.1Modèles de Markov cachés . . . . . . . . . . . .18

2.4.2Processus de Dirichlet hiérarchiques . . . . . . .20

2.4.3 Modèles de Markov cachés à base de processus de Dirichlet hiérarchique . . . . . . . . . . . . .21

2.5Modélisation du délai à l"aide du HDP-HMM . . . . .25

2.5.1Un modèle d"observation non paramétrique . .26

2.5.2 Implémentation du HDP-HMM à émissions DPMM29

2.5.3Considérations pratiques pour l"inférence . . . .29

2.6Validation de la modélisation HDP-HMM du délai . .32

2.6.1Validation sur un jeu de changements labélisés32

2.6.2Test du rapport de vraisemblance . . . . . . . .35

2.6.3 Distribution des temps de séjour dans chaque état37

2.7Discussion . . . . . . . . . . . . . . . . . . . . . . . . . .39

3 application au traitement de données à grande

échelle

40

3.1La mesure de la performance d"Internet . . . . . . . . .40

3.1.1Mesure du délai . . . . . . . . . . . . . . . . . . .41

3.1.2Mesure des chemins . . . . . . . . . . . . . . . .42

3.1.3Infrastructures de mesure publiques . . . . . . .44

3.2Caractérisation des données RIPE Atlas . . . . . . . . .45

3.2.1 Correspondance entre état caché et chemin réseau46

3.2.2Distribution du nombre d"états cachés . . . . . .46

3.2.3Durée moyenne et coefficient de variation . . .50

3.3Segmentation intégrée à RIPE Atlas . . . . . . . . . . .51

3.3.1Architecture . . . . . . . . . . . . . . . . . . . . .52

iii table des matièresiv

3.3.2Terminaisons . . . . . . . . . . . . . . . . . . . .53

3.4Détection d"anomalies sur des infrastructures d"Internet55

3.4.1Couverture et choix des mesures . . . . . . . . .55

3.4.2Incident du13mai2015à AMS-IX . . . . . . . .57

3.4.3Incident du9avril2018à DE-CIX . . . . . . . .58

3.5Autres types de mesures réseau . . . . . . . . . . . . . .59

3.5.1Mesures de congestion CAIDA MANIC . . . . .59

3.5.2Mesures de temps de chargement Orange Web

View . . . . . . . . . . . . . . . . . . . . . . . . .61 4 métrologie parcimonieuse avec des processus de décision markoviens 62

4.1Problème . . . . . . . . . . . . . . . . . . . . . . . . . . .62

4.2Travaux connexes . . . . . . . . . . . . . . . . . . . . . .64

4.3Optimisation du routage . . . . . . . . . . . . . . . . . .64

4.3.1Filtrage et prédiction . . . . . . . . . . . . . . . .65

4.4Optimisation1-pas en avant . . . . . . . . . . . . . . . .67

4.4.1Solution pour1chemin stochastique . . . . . .68

4.4.2Solution pour2chemins stochastiques . . . . .71

4.5Optimisation à horizon de temps infini . . . . . . . . .74

4.5.1Formulation MDP . . . . . . . . . . . . . . . . .74

4.5.2Solution pour n chemins stochastiques . . . . .77

4.6Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . .78

4.6.1 1chemin stochastique . . . . . . . . . . . . . . .78

4.6.2 2chemins stochastiques . . . . . . . . . . . . . .80

4.6.3 2chemins entre des sondes RIPE Atlas . . . . .83

4.6.4Simulation d"un overlay de routage . . . . . . .85

5 heuristiques pour la métrologie parcimonieuse

89

5.1Structure du problème . . . . . . . . . . . . . . . . . . .89

5.1.1Espace d"état . . . . . . . . . . . . . . . . . . . .89

5.1.2Transitions . . . . . . . . . . . . . . . . . . . . . .91

5.1.3Complexité . . . . . . . . . . . . . . . . . . . . .92

5.2Optimisation à horizon de temps reculant . . . . . . . .93

5.2.1Complexité . . . . . . . . . . . . . . . . . . . . .94

5.3Agrégation de chemins . . . . . . . . . . . . . . . . . . .95

5.4Résultats . . . . . . . . . . . . . . . . . . . . . . . . . . .96

5.4.1Données synthétiques . . . . . . . . . . . . . . .96

5.4.2Données réelles . . . . . . . . . . . . . . . . . . .98

6 conclusion

102

6.1Travaux futurs . . . . . . . . . . . . . . . . . . . . . . . .104

6.1.1Apprentissage en ligne . . . . . . . . . . . . . . .104

6.1.2Partitionnement des modèles . . . . . . . . . . .104

6.1.3Détection d"incidents . . . . . . . . . . . . . . . .105

bibliographie 106
publications 118

TABLE DES FIGURES

Figure2.1Segmentation du RTT entre deux ancres RIPE

Atlas sous la modélisation HDP-HMM. . . . .4

Figure2.2

Segmentation du RTT entre deux ancres RIPE

Atlas avec un modèle de mélange gaussien :

comparaison avec la modélisation HDP-HMM.6

Figure2.3

Représentation graphique d"un modèle de mé- lange bayésien. . . . . . . . . . . . . . . . . . . .8 Figure2.4Le processusstick-breaking. . . . . . . . . . . . .15

Figure2.5

Représentation graphique d"un modèle de Mar- kov caché bayésien. . . . . . . . . . . . . . . . .18

Figure2.6

Représentation graphique d"un modèle de Mar- kov caché à base de processus de Dirichlet hié- rarchique. . . . . . . . . . . . . . . . . . . . . . .22

Figure2.7

Segmentation du RTT entre deux ancres RIPE

Atlas sous la modélisation HDP-HMM, et den-

sité des modèles de mélange inférés. . . . . . .27

Figure2.8

Segmentation d"une série temporelle de RTT

avec des modèles de mélange et de HMMs pa- ramétriques et non paramétriques. . . . . . . .28

Figure2.9

Comparaison de la performance des implémen-

tations du HDP-HMM. . . . . . . . . . . . . . .30

Figure2.10

Taux de rejet deH0en fonction de la probabilité de fausse alarme. . . . . . . . . . . . . . . . . .37

Figure2.11

Diagramme quantile-quantile des temps de sé-

jours normalisés observés contre la loi expo- nentielle de moyenne1. . . . . . . . . . . . . . .38

Figure3.1

Composantes du délai dans les réseaux infor- matiques. . . . . . . . . . . . . . . . . . . . . . .42

Figure3.2

Exemple de traceroute de H1vers H2sans équi-

librage de charge. . . . . . . . . . . . . . . . . .43

Figure3.3

Exemple de traceroute de H1vers H2en pré-

sence d"équilibrage de charge. . . . . . . . . . .43

Figure3.4

Principe du système d"ancres Atlas avec4ancres.45

Figure3.5

Exemple de correspondance entre état inféré et chemin réseau. . . . . . . . . . . . . . . . . . . .47

Figure3.6

Correspondance entre état inféré et chemin IP dans des mesures RIPE Atlas. . . . . . . . . . .47

Figure3.7

Correspondance entre état inféré et chemin AS dans des mesures RIPE Atlas. . . . . . . . . . .48

Figure3.8

Exemples de segmentation de mesures vers les

ancres elle-même. . . . . . . . . . . . . . . . . .49 v table des figuresvi Figure3.9Distribution du nombre d"états inféré en fonc- tion de la durée d"observations. . . . . . . . . .50

Figure3.10

Distribution de la durée moyenne des états en fonction du coefficient de variation (écart type / moyenne). . . . . . . . . . . . . . . . . . . . .52

Figure3.11

Segmentation du délai sous la modélisation

HDP-HMM entre deux ancres RIPE Atlas. Chaque

couleur identifie un état. . . . . . . . . . . . . .54

Figure3.12

Fréquence de changements le13mai2015pour

les20k paires qui ont vu AMS-IX dans leurs traceroutes la veille. . . . . . . . . . . . . . . . .58

Figure3.13

Fréquence de changements entre le9et le10

avril2018pour les60k paires qui ont vu DE- CIX Francfort dans leurs traceroutes la veille. .58

Figure3.14

MéthodeTime Series Latency Probingpour es-

timer le délai entre deux routeurs de bordure d"AS. . . . . . . . . . . . . . . . . . . . . . . . .59

Figure3.15

Segmentation d"une série temporelle de diffé- rence de RTT (lointain - proche) obtenue avec des sondes TSLP du projet CAIDA MANIC. .60

Figure3.16

Densité de probabilité des états de préconges- tion et de congestion sur une série de différence temporelle de RTT segmentée. . . . . . . . . . .60

Figure3.17

Segmentation d"une série temporelle de temps

de chargement de page obtenue à partir d"une sonde Web View. . . . . . . . . . . . . . . . . .61

Figure4.1

Overlay de routage avec6noeuds et15ar-

rêtes (chemins directs). Un chemin alternatif est construit en transmettant les paquets par un ou plusieurs noeuds intermédiaires. . . . . . .63 Figure4.2Configuration à deux noeuds. . . . . . . . . . .67 Figure4.3Politique à seuil. . . . . . . . . . . . . . . . . . .71

Figure4.4

Schéma de principe de la métrologie parcimo- nieuse. . . . . . . . . . . . . . . . . . . . . . . .78

Figure4.5

Simulation de quatre politiques : ne jamais me-

surer, toujours mesurer, myope et MDP (=0.99).79

Figure4.6

Décisions de mesure pour la politique myope

et MDP (=0.01) dans le cas de deux chemins stochastiques à deux états. . . . . . . . . . . . .81

Figure4.7

Simulation de la politique MDP (=0.9)entre

deux sondes RIPE Atlas. . . . . . . . . . . . . .84

Figure4.8

Nombre de mesures en fonction du coût de

mesure. . . . . . . . . . . . . . . . . . . . . . . .88

Figure4.9

Écart au délai de la politique toujours mesu- rer en fonction du nombre moyen de mesures (regroupés dans des intervalles de0.1). . . . .88quotesdbs_dbs4.pdfusesText_8

[PDF] Maximes de la Rochefoucauld

[PDF] maximes de la rochefoucauld fiche de lecture

[PDF] Maximiliens Robespierre

[PDF] Maximisation d'une aire

[PDF] Maximisation de l'aire d'un quadrilatère tournant

[PDF] maximisation définition

[PDF] maximisation des provisions

[PDF] maximisation du profit

[PDF] maximisation du profit en cpp

[PDF] maximisation du profit exercice corrigé

[PDF] maximisation maths

[PDF] Maximiser les bénéfices d'un fermier

[PDF] maximum et minimum d'une fonction du second degré

[PDF] maximum et minimum d'une fonction exercices

[PDF] maximum minimum fonction seconde