Université Louis Pasteur Strasbourg I UFR de Mathématique et d'Informatique

Damien Magoni

Description

Niveau: Supérieur, Doctorat, Bac+8
Université Louis Pasteur – Strasbourg I UFR de Mathématique et d'Informatique LSIIT – UMR N˚7005 du CNRS N˚ d'ordre : 3978 THÈSE Pour l'obtention du grade de Docteur de l'Université Louis Pasteur – Strasbourg I Discipline : Informatique Présentée par Damien MAGONI SERVICE DE RECHERCHE D'AGENT PAR DIFFUSION MULTIPOINT ORIENTÉE Soutenue publiquement le 3 janvier 2002 devant le jury composé de : M. Serge FDIDA, Rapporteur externe Professeur à l'Université Pierre et Marie Curie – Paris VI M. Eric FLEURY, Examinateur Chargé de recherche au LORIA – UMR N˚7503 du CNRS M. Jean-Claude KÖNIG, Rapporteur externe Professeur à l'Université Montpellier II – Sciences et Techniques du Languedoc M. Jerzy KORCZAK, Rapporteur interne Professeur à l'Université Louis Pasteur – Strasbourg I M. Jean-Jacques PANSIOT, Directeur de thèse Professeur à l'Université Louis Pasteur – Strasbourg I

• multipoint ip


• examinateur chargé de recherche au loria


• protocole de diffusion multipoint


• agent réseau


• membre du jury en qualité d'examinateur


• analyse des besoins des protocoles

Sujets

• Fleury
• Université Montpellier 2
• Louis Pasteur University
• Korczak
• Magoni
• Hannibal

Informations

• Publié par: profil-zyak-2012
• Publié le: 01 janvier 2002
• Nombre de lectures: 68
• Langue: Français
• Poids de l'ouvrage: 1 Mo

Extrait

Université Louis Pasteur – Strasbourg I
UFR de Mathématique et d’Informatique
LSIIT – UMR N˚7005 du CNRS
N˚ d’ordre : 3978
THÈSE
Pour l’obtention du grade de
Docteur de l’Université Louis Pasteur – Strasbourg I
Discipline : Informatique
Présentée par
Damien MAGONI
SERVICE DE RECHERCHE D’AGENT PAR
DIFFUSION MULTIPOINT ORIENTÉE
Soutenue publiquement le 3 janvier 2002 devant le jury composé de :
M. Serge FDIDA, Rapporteur externe
Professeur à l’Université Pierre et Marie Curie – Paris VI
M. Eric FLEURY, Examinateur
Chargé de recherche au LORIA – UMR N˚7503 du CNRS
M. Jean-Claude KÖNIG, Rapporteur externe
Professeur à l’Université Montpellier II – Sciences et Techniques du Languedoc
M. Jerzy KORCZAK, Rapporteur interne
Professeur à l’Université Louis Pasteur – Strasbourg I
M. Jean-Jacques PANSIOT, Directeur de thèse
Professeur à l’Université Louis Pasteur – Strasbourg IEither we will find a way, or we will make one.
– General Hannibal
à l’Atma.
2Remerciements
Merci beaucoup à Messieurs Serge Fdida, Jean-Claude König et Jerzy Korczak d’avoir
accepté d’être les rapporteurs de ma thèse. Je remercie également Monsieur Eric Fleury d’avoir
accepté d’être membre du jury en qualité d’examinateur. Je remercie Jean-Jacques Pansiot de
m’avoir guidé brillamment dans mes recherches et de m’avoir fait entière confiance
concernant l’organisation de mon travail. Je suis reconnaissant à tous les membres de l’équipe R2 de
m’avoir chaleureusement accueilli parmi eux. Enfin je remercie de tout coeur mes proches et
ma famille pour leur soutien sans faille.
34Table des matières
Introduction 11
I Rôle des agents dans les réseaux et techniques de découverte 15
1 Rôle des agents 17
1.1 Agent réseau . .................................. 17
1.1.1 Définition d’un agent . .......................... 17
1.1.2 Contexte des agents . . 17
1.2 Agents de protocoles point-à-point . . ...................... 18
1.2.1 Informateurs . .............................. 18
1.2.2 Passerelles . . 19
1.3 Agents de protocoles multipoint . . . 21
1.3.1 Arbres multipoint . . . 21
1.3.2 Retransmetteurs 29
2 Techniques de recherche d’agent 37
2.1 Définition d’une recherche d’agent . . ...................... 37
2.2 Les techniques statiques . . . .......................... 37
2.2.1 Le protocole DHCP . . 37
2.2.2 Le DNS . . 38
2.2.3 Le protocole SLP . . . 38
2.3 Les techniques dynamiques . . 39
2.3.1 La diffusion et le multipoint IP 39
2.3.2 L’anycasting . .............................. 40
2.3.3 La recherche par anneaux croissants . .................. 43
2.4 Analyse des besoins des protocoles et applications en techniques de recherche . 44
2.4.1 Recensement des besoins des protocoles et des applications . . . . . . 44
2.4.2 Proposition d’un service fédérateur . 44
II Protocoles de diffusion orientée et de recherche d’agent 47
3 Architecture des protocoles 49
3.1 Protocole de diffusion multipoint orientée . . .................. 49
3.1.1 Contexte . . . .............................. 49
3.1.2 Multipoint orienté . . .......................... 50
3.1.3 Variantes de diffusion multipoint orientée . . .............. 51
3.1.4 Applications de la diffusion multipoint orientée . . . .......... 52
3.2 Service et protocole de recherche d’agent au niveau réseau . 53
53.2.1 Problématique .............................. 53
3.2.2 Définition d’une recherche d’agent au niveau réseau .......... 54
3.2.3 Contexte d’utilisation du protocole de recherche d’agent . . . . . . . . 55
3.2.4 Description du service de recherche . .................. 56
3.2.5 du protocole de 56
4 Algorithmes de diffusion et de recherche 59
4.1 Algorithme de diffusion multipoint orientée . 59
4.1.1 Structures de données .......................... 59
4.1.2 Algorithme . . .............................. 60
4.2 Algorithme de recherche dynamique d’agent au niveau réseau . . . . . . . . . 63
4.2.1 Structures de données 63
4.2.2 Algorithme . . 65
4.3 Commentaires . .................................. 68
5 Implémentation des protocoles 69
5.1 du protocole OMP . . ...................... 69
5.1.1 Mécanismes employés dans les routeurs . . . .............. 69
5.1.2 Entête du protocole OMP . . . 70
5.2 Implémentation du NASP . 71
5.2.1 Traitement dans les noeuds . . 71
5.2.2 Entête du protocole NASP . . 72
5.3 Perspectives . . 74
III Évaluation du service de recherche d’agent 75
6 Analyse de la topologie d’Internet 77
6.1 Analyse de la topologie des Systèmes Autonomes d’Internet .......... 77
6.1.1 Travaux précédents . . .......................... 78
6.1.2 Présentation du réseau d’AS . ...................... 78
6.1.3 Analyse des données BGP . . 79
6.1.4 Le réseau d’AS aujourd’hui . 84
6.1.5 Évolution du réseau d’AS . . 91
6.1.6 Lois puissances .............................. 94
6.1.7 Perspectives . . 99
6.2 Analyse de la topologie des routeurs d’Internet . . . .............. 100
6.2.1 Cartes de l’Internet . . .......................... 100
6.2.2 Analyse des propriétés topologiques . .................. 100
6.2.3 Invariants topologiques 101
7 Génération de topologies réseaux de type Internet 105
7.1 Contexte...................................... 105
7.2 Travaux précédents . . .............................. 106
7.3 Modélisation d’Internet 107
7.3.1 Principe .................................. 107
7.3.2 Types de données et variables utilisés dans l’algorithme . . . . . . . . 107
7.3.3 Spécification de l’algorithme . ...................... 108
7.4 Performances des variantes de l’algorithme . .................. 112
7.4.1 Méthodologie . 112
67.4.2 Résultats . . . .............................. 113
7.5 Comparaison des performances des générateurs de topologies de type Internet . 115
7.5.1 Présentation des générateurs évalués . .................. 115
7.5.2 Paramètres des . . ...................... 116
7.5.3 Méthode d’évaluation .......................... 116
7.5.4 Performances . 117
8 Simulations des protocoles OMP et NASP 123
8.1 Topologies réseaux utilisées . 123
8.2 Paramètres des simulations . . 124
8.3 Résultats des . . . 126
Conclusion 135
Bibliographie 144
A network manipulator 149
A.1 Architecture de nem................................ 149
A.2 Module d’analyse de nem ............................. 149
B network simulator 151
B.1 Script de simulation OMP/NASP . . . ...................... 151
B.2 Script de traitementASP . . . 153
78Résumé
Beaucoup de protocoles et d’applications nécessitent un mécanisme de découverte pour
permettre à des clients de localiser un ou plusieurs noeuds spécifiques engagés dans la même
communication. Ces noeuds spécifiques qui peuvent être des routeurs ou des machines hôtes
sont usuellement appelés agents. Il n’existe pas actuellement de protocole de recherche d’agent
prêt à remplir ce service au niveau de la couche réseau. Chaque implémente
habituellement sa propre solution. En particulier les protocoles multipoints utilisent souvent une
technique de recherche appelés recherche par anneaux croissants. Cette méthode recherche des
noeuds spécifiques dans toutes les directions et donc utilise beaucoup de bande passante.
Cependant une recherche typique peut habituellement se limiter à une direction spécifique. Pour
répondre à ce problème, nous proposons un service de recherche au niveau réseau en
remplacement de la recherche par anneaux croissants. Ce service est basé sur un protocole de diffusion
multipoint orientée de façon à obtenir une efficacité plus élevée que celle de la recherche par
anneaux croissants. Le principe de la diffusion multipoint orientée est de canaliser la diffusion
multipoint des paquet de recherche en direction d’un noeud spécial impliqué dans la
communication de façon à balayer seulement une zone limitée du réseau. Nous décrivons le service et
le protocole dynamique de recherche d’agent au niveau réseau ainsi que le protocole de
diffusion multipoint orientée et nous fournissons des résultats de simulations comparatifs entre notre
service et la recherche par anneaux croissants.
Mots-clés
Réseaux, protocoles, services, Internet, topologie, communication multipoint, diffusion
orientée, agents, recherche, anneaux croissants.
910