21
13-15 Septembre 2004 1 Exploitation de l’affinité dans les réseaux pair à pair Anne-Marie Kermarrec Projet PARIS INRIA Rennes/IRISA Porquerolles 2004

Exploitation de l’affinité dans les réseaux pair à pair

  • Upload
    edward

  • View
    32

  • Download
    3

Embed Size (px)

DESCRIPTION

Exploitation de l’affinité dans les réseaux pair à pair. Anne-Marie Kermarrec Projet PARIS INRIA Rennes/IRISA Porquerolles 2004. 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 - PowerPoint PPT Presentation

Citation preview

Page 1: Exploitation de l’affinité dans les réseaux pair à pair

13-15 Septembre 2004 1

Exploitation de l’affinité dans les réseaux pair à pair

Anne-Marie KermarrecProjet PARISINRIA Rennes/IRISA

Porquerolles 2004

Page 2: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 3: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 4: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 5: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 6: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 7: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 8: Exploitation de l’affinité dans les réseaux pair à pair

13-15 Septembre 2004 8

Réseau non structuré

(a) (b) (c)

ij

k

ij

k

Reconnexions locales [Massoulié, Kermarrec, Ganesh SRDS03]

Page 9: Exploitation de l’affinité dans les réseaux pair à pair

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é

Page 10: Exploitation de l’affinité dans les réseaux pair à pair

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))

Page 11: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 12: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 13: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 14: Exploitation de l’affinité dans les réseaux pair à pair

13-15 Septembre 2004 14

Création de liens sémantiques

Page 15: Exploitation de l’affinité dans les réseaux pair à pair

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)

Page 16: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 17: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 18: Exploitation de l’affinité dans les réseaux pair à pair

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

Page 19: Exploitation de l’affinité dans les réseaux pair à pair

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)

Page 20: Exploitation de l’affinité dans les réseaux pair à pair

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 ?

Page 21: Exploitation de l’affinité dans les réseaux pair à pair

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…