Olivier Soyez Directeurs de Thse : Cyril Randriamaro Vincent
Villain Stockage dans les systmes Pair Pair
Page 2
2 Un pair? Internet
Page 3
3 Emule
Page 4
4 14 Millions dutilisateurs 1,4 Milliards de fichiers =
Plusieurs Po
Page 5
5 Pair Pair (P2P) ? Qui possde les ressources qui alimentent le
systme ? lensemble des pairs
Page 6
6 Plan Les systmes de stockage Pair Pair Le projet Us
Politiques de distribution Conclusion / Perspectives
Page 7
7 Applications du P2P Partage des fichiers Diffusion de MP3,
DIVX Pionnier : Napster (Shawn Fanning) Emule (Open Source) Partage
de CPU Applications scientifiques Seti@Home (Berkeley) Dcrypthon
(Tlthon) XtremWeb (Paris XI - LRI) Partage des disques
Page 8
8 OceanStore (Berkeley) CFS (MIT) PAST (Rice) PASTA (Microsoft)
Farsite (Microsoft) InterMemory (NEC) Ivy (MIT) PlanetP (Rutger U.)
Mnemosyne (sprintlab) Clique (HP) Mammoth (BC U) Ficus (UCLA)
Tornado (Tsing Hua U.)... Projet IRIS (12 M$) MIT, Berkeley,
Rice,... (http://project-iris.net) Projet DELIS
(http://delis.upb.de) Projet IRIS (12 M$) MIT, Berkeley, Rice,...
(http://project-iris.net) Projet DELIS (http://delis.upb.de)
Projets stockage P2P
Page 9
9 Indexation centralise IBP (LoCI) Intermemory (NEC) Indexation
distribue PAST (Rice) PASTIS (Paris VI - LIP 6) Ivy (MIT)
OceanStore (Berkeley) Deux grandes classes DHT
Page 10
10 Table de Hachage Distribue (DHT) Ensemble des identifiants
cods sur m bits 1 2 3 5 4
Page 11
11 Modle en couches (CFS : Chord File System ) Primitives
simples (put, get) Table de hachage distribue Application distribue
get (cl) donne put(cl, donne) Service de localisation lookup(cl)
Adresse IP (Application) (DHT) (Overlay) Table de Hachage Distribue
(DHT) (Pairs) (Routage) (Prennit)
Page 12
12 Routage dynamique (Overlay) 0 2 m-1 1 9 Chaque pair mmorise
k pairs de distance 2 i, 1 i k 64 32 16 8 4 2 128 137 Chord
21 A)Rplication (DHT) - Donnes dupliques : k fois - Espace
utile : 1/k - Tolrance : k-1 pannes k = 2 vs (s,r)=(4, 4)
Redondances B)Codes Correcteurs (Us) - Donnes fragmentes : s -
Redondance : r - Espace utile : s / (s+r) - Tolrance : r pannes
Reconstruction = s quelconques parmi s+r
Page 22
22 Redondance : vie des donnes ? Temps Fragments disponibles
s+r s 0 Seuil critique Fragments d1 bloc avec s=3, r=5
Page 23
23 Redondance + Maintien Temps s+r s 0 Fragments d1 bloc avec
s=3, r=5 Fragments disponibles
Page 24
24 Us = Disque Dur Virtuel P2P Prenne
Page 25
25 Architecture Us Systme de fichier UsFS Client Us Utilisateur
Us Fragments Blocs Fournisseur
Page 26
26 Stockage dun fichier f=s+r fragments s fragments blocs
fichier fragmentation redondance dcoupage Us UsFs
Page 27
27 Distribution des donnes
Page 28
28 Environnement Pair Pair Pannes Dconnections frquentes Couche
communication Internet (ADSL) : Rception >> Envoi Bande
passante limite des Pairs Contexte Us
Page 29
29 Chaque pair stocke 100 fragments de taille 1 Mo Un bloc est
compos de f=31 fragments Rgnrer un fragment perdu Envoi des f-1
fragments Exemple A la mort dun seul pair 100*30=3000 fragments 3
Go
Page 30
30 Exemple 2 minutes ! 128 Kb 10 Mb 4 heures !
Page 31
31 Cot de reconstruction lev Nombreuses reconstructions
Problmatique XY Cot de reconstruction = Nombre maximum de fragments
envoys dans le pire des cas
Page 32
32 Le cot de reconstruction est linaire et facteur du nombre de
blocs stocks Thorme du repliement XY Cot=2 X Y Trouver une
distribution optimale de cot de reconstruction = 1
Page 33
33 Maximiser le nombre de blocs Cot de reconstruction = 1
Intersection entre 2 blocs 1 Formulation du problme XY
Page 34
34 Cas idal BiBi BjBj Et a, pour tous les pairs !
Page 35
35 Trouver un ensemble maximal de listes de f lments parmi N
Intersection entre 2 listes distinctes 1 1 liste de f lments = 1
bloc f=5 X : {1,2,3,4,5} et Y : {5,6,7,8,9} N = nombre total de
pair Formulation mathmatique SOLUTION ?