University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Bessou, mouhamed |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Implémentation d'un algorithme auto-stabilisant pour le calcul d'un ensemble indépendant en utilisant la communication par messages / Bessou, mouhamed
Titre : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un ensemble indépendant en utilisant la communication par messages Type de document : texte imprimé Auteurs : Bessou, mouhamed ; GUELLATI, N, Directeur de thèse Editeur : Setif:UFA Année de publication : 2017 Importance : 1 vol (50f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
systèmes distribués
toléranceauxpannes
auto-stabilisation
clustering
ensemble indépendant maximalIndex. décimale : 004 Informatique Résumé : Résumé
Les progrès remarquables des équipements informatiques et de télécommunications durant ces dernières années ont permis une forte évolution de l'environnement distribué qui
les utilise. On est ainsi passé de réseaux locaux de stations de travail à des réseaux Ã
grande échelle. Cette avancée des équipements a permis de répondre plus ecacement aux
besoins des diérents domaines. La tolérance aux pannes dans les systèmes distribués est
un sujet qui a été largement étudié. La tolérance aux pannes fait référence à la capacité
d'un système de continuer à fonctionner lorsqu'une partie de celui-ci tombe en panne. Une
des solutions proposées pour la tolérance aux pannes est l'auto-stabilisation.
Ce mémoire étudie les algorithmes auto-stabilisants dans le cadre des systèmes distribués. Elle s'intéresse plus particulièrement à l'implémentation de ces algorithmes dans les
réseaux réels.
Dans la première partie, nous présentons le domaine des systèmes distribués, nous citons
leurs objectifs et les types des pannes qui les menaces. Nous présentons aussi l'approche
de l'auto-stabilisation en citons quelques-unes de ses avantages et ses limites.
Dans la deuxième partie, nous présentons les réseaux ad hoc, le clustering dans les
réseaux ad hoc et nous présentons aussi les ensembles indépendants en citons leur utilité
dans les réseaux. Nous terminons cette partie par la présentation de quelques algorithmes
auto-stabilisants permettant de calculés les ensembles indépendants maximaux.
Dans la troisième partie, nous essayons de surpasser les hypothèses fortes des algorithmes auto-stabilisants, pour cela nous proposons une solution pour utiliser l'algorithme
auto-stabilisant d'Ikeda dans un réseau réel. Finalement nous l'implémentons en langage
Java en utilisant les sockets.
Note de contenu : Table des matières
Introduction générale 1
1 Systèmes Distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . 4
1.2.2 Algorithme distribué . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Problème classique en algorithmique distribuée . . . . . . . . 5
1.3 Modèles de communications . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Tolérance au panne . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Auto Stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.3 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Le clustering dans les réseaux ad-hoc et les ensembles indépendants 14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Réseau ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 La communication dans les réseaux ad hoc . . . . . . . . . . 15
2.2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Formation de clusters . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.4 Élection de cluster-head . . . . . . . . . . . . . . . . . . . . . 17
2.2.5 Maintenance des clusters . . . . . . . . . . . . . . . . . . . . . 17
2.2.6 Quelques approches de Clustering . . . . . . . . . . . . . . . . 17
2.3 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . 18
2.3.2 L'utilisation des ensembles indépendants maximaux (MIS) dans
le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Algorithme de Shukla et al . . . . . . . . . . . . . . . . . . . . 19
2.3.4 Algorithme de Shi et al . . . . . . . . . . . . . . . . . . . . . . 20
2.3.5 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 21
2.3.6 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7 Algorithme de Goddard et al . . . . . . . . . . . . . . . . . . 23
2.3.8 Algorithme de Yen et Huang . . . . . . . . . . . . . . . . . . . 23
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Implémentation de l'algorithme d'Ikeda dans un réseau réel 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Proposition d'une solution pour l'utilisation de l'algorithme d'Ikeda
dans les réseaux réels . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Algorithme transformé . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Description de notre travail . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Modélisation avec UML . . . . . . . . . . . . . . . . . . . . . 30
3.4 Description du code Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Le language Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Socket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.3 La classe ServeurdeNom . . . . . . . . . . . . . . . . . . . . . 36
3.4.4 La classe Résultat . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.5 Classe InfoVoisin . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.6 Classe N÷ud . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Description de l'application . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion générale 46Côte titre : MAI/0167 En ligne : https://drive.google.com/file/d/1OksvpU1oZBqDtH_YvMgebD-KIYf8bper/view?usp=shari [...] Format de la ressource électronique : Implémentation d'un algorithme auto-stabilisant pour le calcul d'un ensemble indépendant en utilisant la communication par messages [texte imprimé] / Bessou, mouhamed ; GUELLATI, N, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (50f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
systèmes distribués
toléranceauxpannes
auto-stabilisation
clustering
ensemble indépendant maximalIndex. décimale : 004 Informatique Résumé : Résumé
Les progrès remarquables des équipements informatiques et de télécommunications durant ces dernières années ont permis une forte évolution de l'environnement distribué qui
les utilise. On est ainsi passé de réseaux locaux de stations de travail à des réseaux Ã
grande échelle. Cette avancée des équipements a permis de répondre plus ecacement aux
besoins des diérents domaines. La tolérance aux pannes dans les systèmes distribués est
un sujet qui a été largement étudié. La tolérance aux pannes fait référence à la capacité
d'un système de continuer à fonctionner lorsqu'une partie de celui-ci tombe en panne. Une
des solutions proposées pour la tolérance aux pannes est l'auto-stabilisation.
Ce mémoire étudie les algorithmes auto-stabilisants dans le cadre des systèmes distribués. Elle s'intéresse plus particulièrement à l'implémentation de ces algorithmes dans les
réseaux réels.
Dans la première partie, nous présentons le domaine des systèmes distribués, nous citons
leurs objectifs et les types des pannes qui les menaces. Nous présentons aussi l'approche
de l'auto-stabilisation en citons quelques-unes de ses avantages et ses limites.
Dans la deuxième partie, nous présentons les réseaux ad hoc, le clustering dans les
réseaux ad hoc et nous présentons aussi les ensembles indépendants en citons leur utilité
dans les réseaux. Nous terminons cette partie par la présentation de quelques algorithmes
auto-stabilisants permettant de calculés les ensembles indépendants maximaux.
Dans la troisième partie, nous essayons de surpasser les hypothèses fortes des algorithmes auto-stabilisants, pour cela nous proposons une solution pour utiliser l'algorithme
auto-stabilisant d'Ikeda dans un réseau réel. Finalement nous l'implémentons en langage
Java en utilisant les sockets.
Note de contenu : Table des matières
Introduction générale 1
1 Systèmes Distribués et Auto-Stabilisation 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Systèmes distribués . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Objectifs des systèmes distribués . . . . . . . . . . . . . . . . 4
1.2.2 Algorithme distribué . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.3 Problème classique en algorithmique distribuée . . . . . . . . 5
1.3 Modèles de communications . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Tolérance au panne . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Auto Stabilisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5.1 Token ring de Dijkstra . . . . . . . . . . . . . . . . . . . . . . 9
1.5.2 Avantages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.3 Inconvénients . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5.4 Démon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2 Le clustering dans les réseaux ad-hoc et les ensembles indépendants 14
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2 Réseau ad hoc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1 La communication dans les réseaux ad hoc . . . . . . . . . . 15
2.2.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.2.3 Formation de clusters . . . . . . . . . . . . . . . . . . . . . . . 16
2.2.4 Élection de cluster-head . . . . . . . . . . . . . . . . . . . . . 17
2.2.5 Maintenance des clusters . . . . . . . . . . . . . . . . . . . . . 17
2.2.6 Quelques approches de Clustering . . . . . . . . . . . . . . . . 17
2.3 Etat de l'art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Les ensembles indépendants . . . . . . . . . . . . . . . . . . . 18
2.3.2 L'utilisation des ensembles indépendants maximaux (MIS) dans
le clustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.3 Algorithme de Shukla et al . . . . . . . . . . . . . . . . . . . . 19
2.3.4 Algorithme de Shi et al . . . . . . . . . . . . . . . . . . . . . . 20
2.3.5 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 21
2.3.6 Algorithme de Turau . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7 Algorithme de Goddard et al . . . . . . . . . . . . . . . . . . 23
2.3.8 Algorithme de Yen et Huang . . . . . . . . . . . . . . . . . . . 23
2.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3 Implémentation de l'algorithme d'Ikeda dans un réseau réel 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Proposition d'une solution pour l'utilisation de l'algorithme d'Ikeda
dans les réseaux réels . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Algorithme d'Ikeda et al . . . . . . . . . . . . . . . . . . . . . 27
3.2.2 Algorithme transformé . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Description de notre travail . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Modélisation avec UML . . . . . . . . . . . . . . . . . . . . . 30
3.4 Description du code Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.1 Le language Java . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.2 Socket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.4.3 La classe ServeurdeNom . . . . . . . . . . . . . . . . . . . . . 36
3.4.4 La classe Résultat . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.5 Classe InfoVoisin . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.6 Classe N÷ud . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.5 Description de l'application . . . . . . . . . . . . . . . . . . . . . . . 41
3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Conclusion générale 46Côte titre : MAI/0167 En ligne : https://drive.google.com/file/d/1OksvpU1oZBqDtH_YvMgebD-KIYf8bper/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0167 MAI/0167 Mémoire Bibliothéque des sciences Français Disponible
Disponible