Étude d’un protocole de partage de travail entre systèmes Pair à Pair
Université de Versailles Saint Quentin en YvelinesDEA MISI
Option: Architecture haute performance
Stage réalisé par:
Khaled BENCHERIF
sous la direction de: Olivier RICHARD
• Le contexte du stage
• Les motivations des systèmes Pair à Pair
• L’état de l’art Les systèmes P2P existants Les algorithmes d’équilibrage de charge
• La conception et l’implantation
• Les expériences et l’évaluation
• Conclusion et perspectives
Plan
• Le calcul parallèle évolue.
• Les supercalculateurs coûteux.
• L’évolution d ’Internet (Démocratisation du web).
• L’amélioration des capacités des machines connectées à des réseaux de plus en plus performants.
• La sous utilisation des machines.
La naissance d ’un nouveau concept de l’algorithme parallèle distribuée:
Les systèmes Pair à Pair.
Le contexte général
Les systèmes Pair à Pair
• Faire coopérer plusieurs machines pour résoudre un problème.
• Les machines connectées peuvent être très différentes (Hétérogènes).Supercalculateurs, PC, Téléphones portables,...
• Reliées entre elles par un réseau étendu (WAN).
• L’interface dit être unique et transparente pour l ’utilisateur
Exemples : SETI@home, Distributed.net, et beaucoup d ’autres
variation des débits et disparité des machines.
Les motivations du Pair à Pair
• Nombre important de ressources connectées en permanence à Internet.
• Évolution des capacités des ressources: machines, le réseau (bande
passante, latence).
• Sous utilisation de capacités de calcul et de stockage des machines
connectées à Internet.
• Applications multi paramètres (les simulations).
Propriétés recherchées des systèmes Pair à Pair
• La sécurité (authentification, sûreté)
• L’interactivité
Aspects techniques invisibles à l’utilisateur
• Répartition de charge
• Tolérance aux pannes
• Une meilleur utilisation des ressources
• Le passage à l’échelle
• L’auto organisation dynamique
• La sécurité des calcul (triches)
Importantes pour l’utilisateur
Problématique
Du partage de charge coopération entre représentants de communauté Pair à Pair
ReprésentantTâcheRessource disponible
Positionnement du travail
• L’exploitation à grande échelle des ressources reliées à Internet.
• Équilibrer la charge entre systèmes de calcul global.
• Implanter le partage de travail entre serveurs d’XtremWeb.
• Évaluer l’échange de tâches.
Démarche suivie
• Principe des systèmes Pair à Pair.
• Conception de la solution.
• Étudier les systèmes Pair à Pair existants.
• Étudier les algorithmes d’équilibrage de charge.
• Étudier XtremWeb en détail (installer, tester, examiner les sources).
• Implanter le vol de tâche.
• Évaluer les performances.
État de l’art
• Les plates formes Pair à Pair existantes
• Les algorithmes d’équilibrage de charge (vol de tâche)
Système P2P
Calcul global documents
CentraliséDistribué
DistribuéIndexation, routage
CentraliséIndexation
Partage, échange Stockage persistant
Classification des systèmes globaux
Serv
ice
Arc
hite
ctur
e
OceanStore
Gnutella
Chord, FreeNet
Napster
Seti@HomeXtremWeb
Équilibrage de charge par vol de tâche
La charge des machines dans un système distribué peut être inégale
Amélioration des performances et exploitation des ressources disponibles
Prendre en considération:
1. La charge des processeurs
2. La vitesse d ’exécution sur les nœuds
3. Le temps de transfert des tâches
BUT:
Classe des algorithmes d’équilibrage de charge
• Statiques: cycliques, probabilistes...
• Dynamiques: État du système.
Collecte + stockage de données surcoût.
• Adaptatifs: Changement de politique, changement de paramètres.
Quelques Algorithmes d’équilibrage de charge
• Le vol de tâche aléatoire (Random Stealing RS)
• L’envoi préalable aléatoire (Random Pushing RP)
• Le vol de tâche hiérarchique (Cluster- aware Hierarchical Stealing CHS)
• Le vol de tâche selon la charge (Cluster-aware Load-based Stealing CLS)
• Vol de tâche aléatoire avec prise en considération du cluster : (Cluster-
aware Random Stealing CRS)
Présentation d ’XtremWeb
Le client soumet un travail au serveur.
Le serveur gère les tâches et les affecte aux worker
Le worker fourni des ressources de calculs pour exécuter les tâches qu’il a récupérées du serveur.
Le Result Collector sert à stocker les résultats envoyés par un worker qui a fini son traitement.
WAN
Serveur Pair à Pair
PC worker/Client
PC worker/Client PC worker/Client
PC worker/Client
PC worker/Client
Ensemble d’applications
Ensemble des tâches
Ensemble des résultats
Statistiques
Base de DonnéesSélection des tâchesGestionnaire des
priorités
Scheduleur Collecteur de résultats
Couche de communication
Java-RMI / XMLRPC TCP SSL
Tâches
Résultat
Serveur HTTP
Requêtes du Client
Requêtes du Worker
Soumettre des tâchesRécupération des résultats
Pour une tâche et un hôte donnés :- Sélectionner le binaire et les paramètres de l’application.
- MAJ des infos de statistiques.
- Sauvegarder les résultats.
Architecture du serveur XtremWeb
Architecture du Worker XtremWeb
Contrôleur d’activité
Contrôle
Les threads démons
Contrôleur d’activité
Alive
Requête de fin de tâche
Mode utilisateurMode worker
Vol de tâches entre serveurs XtremWeb
No work
workRequest
workRequest
workRequest
Tâche
Tâche
Résultat
Résultat
Vol de tâches par les workers XtremWeb
@ des serveurs
workRequest
No work
workRequest
hostRegister
workRequest
Tâche
Résultat
L’impact de l’équilibrage de charge
Exécution d ’XW sans équilibrage de charge
Exécution d ’XW avec équilibrage de charge
Rmq: Le vol de tâche est synchrone
Le surcoût de l’équilibrage de charge
Temps d’exécution total avec et sans équilibrage de charge
Exécution d ’XW avec équilibrage de charge
Temps d’attente pour la réception d’une tâche
Le vol de tâche est synchrone
Conclusion
• Une taxonomie des systèmes Pair à Pair. Service, architecture et l’échelle
• Deux algorithmes de distribution de charge: Vol de tâche entre serveurs.
Vol de tâche par le worker.
• Une nouvelle architecture d’XtremWeb.
• Evaluation des algorithmes proposés. Tâches à gros grains.
Surcoût dépend de: nombre, taille des tâches et le temps de recherche d ’une
tâche .
Diminuer la charge sur un seul noeud.
Exploiter toutes les ressources disponibles.
Améliorer le temps d’exécution global.
Perspectives (1)
• Maximiser l’exploitation des ressources par:
L’optimisation et l’amélioration des algorithmes de distribution de charge.
L’atténuation de la complexité de ces algorithmes.
• Notre algorithme fait du vol de tâche synchrone:
L’étendre pour fait du vol de tâche asynchrone (récupérer plus d’une tâche,
prévoire la disponibilité des ressources).
Implanter le deuxième algorithme et les comparer.
Tester avec des application réelles, et dans des conditions variables de charge.
• Proposer de nouvelles architectures pour les systèmes Pair à Pair.
• La coopération entre communautés Pair à Pair peut s’étendre à un
modèle économique.
• Les systèmes Pair à Pair ouvrent la voie à beaucoup d ’axes de
recherche: Le passage à l ’échelle, la tolérance aux pannes, l ’hétérogénéité, la
sécurité...
Perspectives (2)
Étude d’un protocole de partage de travail entre systèmes Pair à Pair
Université de Versailles Saint Quentin en YvelinesDEA MISI
Option: Architecture haute performance
Stage réalisé par:
Khaled BENCHERIF
sous la direction de: Olivier RICHARD