13-15 Septembre 2004 1
Exploitation de l’affinité dans les réseaux pair à pair
Anne-Marie KermarrecProjet PARISINRIA Rennes/IRISA
Porquerolles 2004
13-15 Septembre 2004 2
Contexte
Trafic P2P dominant sur Internet (60-70%) Application majeure déployée: systèmes de partage de fichiers
Réseaux P2P génériques Auto-organisation & disponibilté Symétrie entre pairs/ équilibrage de charge Connaissance locale du système
Les pairs ne sont pas tous égaux entre eux Proximité géographique Proximité sociale Proximité sémantique
Exploitation de l’affinité entre pairs pour améliorer la performance, disponibilité…
Mesure de la distance dépendante de l’application Ajouter ou remplacer des connections entre pairs
13-15 Septembre 2004 3
Réseaux pair à pair
ISP3
ISP1 ISP2
Site 1
Site 4
Site 3Site 2 N
N N
N
N
N N
• Système distribué • Absence de contrôle centralisé• Auto-organisation
• Agrégation de ressource
•(bande passante, éléments de stockage et de calcul)
• Partage de fichiersNapster, Gnutella, Morpheus, KaZaA, EDonkey, etc
13-15 Septembre 2004 4
Structuration des réseaux P2P
Expansion incrémentale, passage à l’échelle
Mise en oeuvre efficace de tels réseaux complexe Réseaux non structurés (Gnutella,Freenet) :
construction aléatoire du graphe de connections Réseaux structurés
(CAN,Chord,Pastry,Tapestry,PNRP) : structure conforme de graphe
13-15 Septembre 2004 5
Itinéraire
Exploitation de la proximité géographique dans les réseaux de pairs
Exploitation du réseau social ou amical
Exploitation de la proximité d’intérêt dans les systèmes de partage de fichiers
13-15 Septembre 2004 6
Exploitation de la localité géographique
Pas de corrélation à priori entre les liens logiques et le réseau sous-jacent
Large surcoût Charge réseau Latence entre deux points
Prise en compte de la topologie réseau dans le choix des liens
13-15 Septembre 2004 7
Réseau structuré : routage de proximité
d46a1c
Route(d46a1c)
d462ba
d4213f
d13da3
65a1fc
d467c4d471f1
Espace de nommage
d467c4
65a1fcd13da3
d4213f
d462ba
Espace géographiquePastry [Rowstron & Druschel 2001]
IP*1.6
13-15 Septembre 2004 8
Réseau non structuré
(a) (b) (c)
ij
k
ij
k
Reconnexions locales [Massoulié, Kermarrec, Ganesh SRDS03]
13-15 Septembre 2004 9
2 – Exploitation des liens sociaux
SPROUT (Social Path Routing) [Marti & al, IPTPS 2004] Limiter l’impact des utilisateurs malicieux Corrélation entre la fiabilité du routage et
la distance sociale des pairs traversés Liens additionnels aux amis Utilisation des services Instant Messaging
pour détecter cette proximité
13-15 Septembre 2004 10
SPROUT, Algorithme
Mis en œuvre au dessus d’une DHT (Chord) Liens aux voisins séquenciels dans l’espace de
nommage O(log(n)) liens distant
Route (msg,k)1. Localisation des amis plus proches de k (<)2. Transmission à l’un d’eux le cas échéant3. Sinon utilisation standard de Chord
Optimization Cache à plusieurs niveaux Minimum hop distance pour assurer un routage
en O(log(n))
13-15 Septembre 2004 11
Résultats
Simulations 8 liens sociaux/nœud 130000 utilisateurs AOL 1000 pairs 40% de nœuds malicieux
Distance moyenne
Fiabilité moyenne
Chord 5.343 0.3080
Chord augmenté 4.532 0.3649
SPROUT 4.569 0.4661
13-15 Septembre 2004 12
Détection de misconfigurations
Friends troubleshooting network [Wand & al IPTPS04] Identification des misconfigurations par
comparaison avec un ensemble de pairs de référence (statistiques)
Détermination de cet ensemble Réseau P2P: liens entre machines reflète
des liens réels entre les utilisateurs des machines
13-15 Septembre 2004 13
3 – Exploitation de la localité d’intérêt
Applications de partage de fichiers Présence de localité d’intérêt
Intuition confirmée par l’analyse des traces du réseau edonkey
Forte corrélation entre les caches clients observés Tendance plus marquée pour les fichiers rares et
audio Comment détecter cette affinité ?
LRU [Sripanidkulchain & al 03] History [Voulgaris & al 04]
Comment l’utiliser Amélioration des mécanismes de recherche
13-15 Septembre 2004 14
Création de liens sémantiques
13-15 Septembre 2004 15
Création de liens sémantiques
Réseaux structurés et non structurés : 1ère phase avant la recherche classique
Réseau hiérarchique: 1ère phase pour éviter les serveurs Evaluation des liens sémantiques
Analyse de la popularités fournit des résultats similaires Dans Kazaa, exprimé en nombre de requêtes Dans eDonkey, exprimé en nombre de répliques
Comportement Fetch-once [Gummadi & al SOSP03] Simulation des listes de requêtes
Crawl des caches eDonkey (Nov 2003) 12,000 clients, 923,000 fichiers
En collaboration avec S. Handurukande, F. Le Fessant et L. Massoulié (SIGOPS EW 2004)
13-15 Septembre 2004 16
Impact sur le taux de hit
0
10
20
30
40
50
60
5 10 20 100 200 2000
Contacted Peers
Hit
s %
History-based Random LRU
13-15 Septembre 2004 17
Cliques sémantiques
0
10
20
30
40
50
60
70
80
5 10 20 100
List Size
Hit
s %
2nd Hop Semantic One Hop
13-15 Septembre 2004 18
Generous uploaders syndrome
0
10
20
30
40
50
60
0 50 100 150 200 250
List Size (with LRU)
Top 15% of Uploaders removed
With All UploadersTop 10% of Uploaders RemovedTop 5% of Uploaders Removed
13-15 Septembre 2004 19
Liens raffinés
0
10
20
30
40
50
60
5 10 20Number of semantic links
Hits
for
Aud
io f
iles
%
With 1 cache for all files (LRU) One cache for Audio files (LRU)
13-15 Septembre 2004 20
Conclusion
Les pairs ne sont pas tous égaux Nombreuses formes d’affinité émergent Exploitation de l’affinité améliore la performance Challenge: détecter et utiliser ces liens privilégiés
sans compromettre les capacités de passage à l’échelle de ces réseaux
Critères et détection de l’affinité propre à chaqueapplication
Remise en cause des réseaux génériques ?
13-15 Septembre 2004 21
Symposium on Operating
Systems PrinciplesOctober 23-26, 2005The Grand Hotel, Brighton, United Kingdom
Submission deadline: March 25, 2005http://www.sosp-20.com/
SIGOPS
Dependability and fault-tolerance
Scalability and Performance
Mobile computing Power Management
Security System design
Storage systems Sensor Networks
Overlay networks etc…