5pVHDX[ 33

Stphane Frnot [email protected]

Materiel initial
I

-RQ &URZFURIW, "Peer-peer and Application-Level Networking" &DPEULGJH .DUO $EHUHU 0DQIUHG +DXVZLUWK, "Peer-to-peer information systems: concepts and models, state-of-the-art, and future systems" EPFL-DSC, TU-Wien DSG 'HMDQ HW DO "Peer-to-Peer Computing", HP Laboratories Palo Alto, 2002

20/10/04

Rseaux classiques

Rseaux Pair Pair

Rseaux Pair Pair

I

Applications
Naptser, Gnutella, Freenet : partage de fichiers Rseaux Ad-Hoc Les Overlays Multicast : distribution vido

Rseaux Pair Pair

I

Questions
Quels sont les nouveaux challenges techniques ? Quels sont les nouveaux services/applications ? Est-ce simplement mettre du rseau au niveau de lapplication ?

Plan du cours
I I I

Introduction Client/Serveur vs. P2P Etude de cas

Napster, Gnutella, Freenet, Bittorrent

Algorithmes de localisation
Chord, Tapestry, CAN

Buts
I

Partage/Rduction des cots

Napster, SETI@home

Amlioration du passage lchelle/tolrance

Pas dadministration centrale --> Algo plus robustes (ex DNS)

Agrgation de ressources et Interoprabilit

cpu : SETI@Home, Distributed.net, Endeavours filespace : gnutella, napster

Augmentation de lautonomie
napster, freenet

Anonymats/zone prive
Freenet, Publius

Dynamisme, apparition / disparition de nuds

IM

Communication ad-hoc et collaboration

Pas d'infrastructure fixe

Client Server vs. P2P

I I I I I I I I I I I I

Grs Configurs Recherche Hirarchique Statique Cycle de vie li au serveur Centr IP Bas sur le DNS RPC/RMI Synchrone Asymtrique Ax sur des modles de liaison et d'intgration du langage de programmation (stub IDL/XDR, compilateurs, etc) Scurit de type Kerberos : acl, crypto

I I I I I I I I I I I I

Auto-Grs Ad-hoc Dcouverte Maillage Mobiles Cycle de vie autonome Non restrictif IP Nommage spcifique Messages Asynchrone Symtrique Ax sur la localisation de services, localisation du contenu, routage applicatif Anonyme, haute-disponible, intgrit Plus difficile dominer

I I

Le client/Server vs P2P
Srv_main_loop(){ while(true){ deque(call) switch(call.procid) case0: call.ret=proc1(call.args) case1: call.ret=proc2(call.args) default: call.ret=exception } } Peer_main_loop(){ while(true){ attendre(event) switch(event.type) case timer_expire: faire une activit p2p(); regnrer timer; break; case inbound message: grermessage; rpondre; break; default: ne rien faire } }

Taxonomie des Systmes

Systmes informatiques Systmes centraliss (mainframe, SMPs, workstation) Systmes distribus

Client-Server

Pairs--Pairs

Plat

Hirarchique

Purs

Hybrides

Taxonomie des systmes P2P

Systmes Pair Pair

,QIRUPDWLTXH GLVWULEXpH Seti@home Avaki 3DUWDJH GH ILFKLHUV Entropia Napster Gnutella Freenet Publius FreeHaven

&ROODERUDWLIV Magi Groove Jabber

,QIUDVWUXFWXUHV JXTA .Net MyServices Globus Chord CAN DHT

Taxonomie des applications P2P

Applications P2P

Gestion de contenu et de fichiers Paralllisation Cpu Intensif 6(7,#+RPH Echange de contenu 1DSVWHU Filtrage Mining RSHQ&2/$ IM -DEEHU Collaboration Jeux TXD]DO Applications Partages %X]]SDG

Composants MDYD%HDQV

Systme de fichiers 2FHDQ6WRUH

Les routeurs IP sont p2p

I I I I I

Ils dcouvrent une topologie et la maintiennent Ne sont ni client ni serveurs Dialoguent continuellement entre eux Sont tolrant aux pannes Sont autonomes

Rseau Ad Hoc et P2P

I I I

Pas de connaissance a priori de la topologie Pas dinfrastructure de base Fabrication partir d'un minimum d'information

Un systme p2p c'est

I I I

Un systme qui n'a pas de rle prdfini Pas de point d'engorgement ou de panne Cependant, ils leur faut des algo distribus pour :
Dcouverte de service (nom, adresse, route, mtrique, etc) Recherche de voisins Routage de niveau applicatif Rmanence, rcupration sur faute de liaison ou d'excution

Etudes de cas : partage de fichiers

I

Les classiques
Napster -->Index Centralis Gnutella -->Innondation Freenet -->Routage documentaire Chord, Tapestry, Can -->Routage documentaire optimis BitTorrent --> Transport optimis

Napster
I I

I I

Le plus connu Pas le premier (Eternity, Ross Anderson, Cambridge) Source dinspiration, pour le bien et le moins bien Egalement un message politique, conomique, lgal...

Napster
I I

Programme de partage de fichiers sur Internet histoire :

5/99 : Shawn Fanning, Boston (aka napster) fonde Napster Online music service 12/99 : premier procs 03/00 : 25% du traffic de l'universit du Wisconsin 07/01 : 160k utilisateurs de napster, 40k Gnutella

Napster principe
I

Protocole client/serveur point point au niveau applicatif !! Quatre tapes :

Connexion au serveur napster Chargement de sa liste de fichiers sur le serveur (push) Envoyer ses critres de recherche sur la liste principale Slectionner la meilleur rponse (pings) Rcuprer le fichier

10

Messages napster
I

[chunkSize] [ChunkInfo] [data] ChunkSize

Intel-endian 16bit integer Size of [data] in bytes Intel-endian 16-bit integer 00 -- login rejected 02 -- login requested 03 -- login accepted 0D -- challenge? (nuprin 17 15) 2D -- added to hotlist 2E -- browse error 2F -- user offline

ChunkInfo: (hex)
5b -- whois query 5c -- whois result 5d -- whois: user is offline! 69 -- list all channels 6a -- channel info 90 -- join channel 91 -- leave channel ...

11

Napster rcupration de fichier

Envoy napster (aprs connexion) 2A 00 CB 00 toto "c:\mp3\Rammstein -- Du Hast.mp3" I Reu de napster 5D 00 CC 00 toto 2965119704 (forme ip = a.b.c.d) 6699 (port) "c:\mp3\Rammstein -- Du Hast.mp3" (morceau) I Envoy au client (32-byte checksum) toto (vitesse ligne) " c:\mp3\Rammstein -- Du Hast.mp3" [connexion a.b.c.d] 0 (port o se connecter) I Reu du client I Reu du client 31 00 00 00 00 00 (taille en octets) I Envoy au client I Envoy napster GET 00 00 DD 00 (notification d ok) I Reu du client I Reu du client 00 00 00 00 00 00 (donnes)
I

Napster : commentaires
I

Serveur centralis
Point de panne Peut quilibrer la charge sur la rotation DNS Congestion Contrle de napster (fausse liberte)

Pas de scurit
Mots de passe en clair Pas d'authentification Pas d'annonymisation

12

Le P2P dcentralis
Un peer , quip dun programme spcifique, se connecte un peer , lui aussi quip de ce programme (point 1). lui annonce ainsi sa prsence sur le rseau. relaie cette information tous les peers auxquels il est connect (point 2).

Ceux-ci signifient alors leur prsence $ et relaient linformation leur tour aux peers auxquels ils sont connects, et ainsi de suite. Le fichier recherch est localis et une rponse est envoye $. $ peut alors directement tlcharger le fichier via une connexion http (point 3).
Source: www.Zdnet.fr

Centralis vs dcentralis
+

Utilisation dun LQGH[ FHQWUDO => localisation rapide

Existence dun VHXO SRLQW GHQWUpH sur le rseau => risque darrt du systme (dfaillances techniques ou dcisions judiciaires)

Aucune dpendance un serveur => UREXVWHVVH du systme Il tire partie de lintermittence des connexions des nuds => les requtes sont poursuivies vers dautres ordinateurs si lun est dfaillant. La bande passante ncessaire pour chaque requte FURvW H[SRQHQWLHOOHPHQW quand le nombre de peers crot linairement => risque dinefficacit

13

Architectures hybrides
I

Des modles hybrides apparaissent afin de tirer parti des points forts des deux modles prcdents, UREXVWHVVH HW UDSLGLWp GHV UHTXrWHV. Le nombre de combinaisons est assez vaste, en voici deux exemples: Architecture en anneau

Architecture hirarchique

Leffet Napster
Depuis Napster, une dchange de fichiers (certains gnralistes et dautres spcialiss dans certains types de fichiers) ont vu le jour:

I I I I I I I

WinMX Blubster FileTopia KaZaa Shareaza Clustone XoloX

  
I I I I I I I I

Freewire Limewire BearShare Morpheus Neti e-mesh e-donkey ...

14

Leffet Napster (2)

Par crainte de fermeture, les logiciels audio les plus rpandus sont actuellement ceux possdant une architecture dcentralise. Nombre de tlchargements depuis leur cration (au 7 janvier 2003):  .D=DD 33 GpFHQWUDOLVp  2. Morpheus (P2P dcentralis) 108141673  L0HVK 33 FHQWUDOLVp  4. Audiogalaxy (P2P centralis) 31303662 devenu payant 5. BearShare (P2P dcentralis) 17939547

=>

Source: download.com

Leffet Napster (2)

Par crainte de fermeture, les logiciels audio les plus rpandus sont actuellement ceux possdant une architecture dcentralise. Nombre de tlchargements depuis leur cration (au 7 janvier 2003):  .D=DD 33 GpFHQWUDOLVp 2. Morpheus (P2P dcentralis)  L0HVK 33 FHQWUDOLVp 4. Audiogalaxy (P2P centralis) 5. BearShare (P2P dcentralis)  108141673  31303662 17939547

=> devenu payant

Source: download.com

15

Gnutella
I I I I

Rsolution des problmes de napster OpenSource Entirement Distribu Trs-Trs politique

Gnutella
I

Rseau p2p :
les pairs se connectent aux pairs

Objectif :
mthode dcentralise de recherche de fichiers

Chaque pair (instance applicative) est utilis pour :

stocker des fichiers spcifiques router les requtes (recherche de fichiers) de et vers ses pairs voisins rpondre aux requtes (servir le fichier) si le fichier est stock localement

Historique
14 jours de dveloppement, NullSoft (winamp) Initialement pour l'change de recettes publi en GNU gpl lanc par AOL (propritaire de NullSoft), immdiatement retir trop tard !!!! : 100k utilisateurs de nombreux bug initiaux Perte d'utilisateurs

16

Gnutella : comment a marche !

I

Pas de serveur central

Pas de poursuite judiciaire (napster)

Broadcast forc (Inondation)

Chaque pair envoie les paquets qu'il reoit tous ses pairs (typiquement 4) Dure de vie d'un paquet limit par un TTL (typiquement 7) Les paquets ont un id unique pour dtecter les boucles (le paquet est quand mme reu deux fois)

Pour rentrer dans un rseau gnutella, il faut connatre au moins 1 hte gnutella
gnutellahosts.com:6346

Gnutella : format du message

I I

Message Id : 16 bytes (oui octets) Function Id : 1 byte

00 ping : recherche d'htes gnutella 01 pong : rponse de ping, nb de fichiers 80 query : recherche chane, b/w minimale 81 query hit : correspondance 80:query, myIP, adresse/port, b/w

I I

Remaining TTL : dcrment chaque pair pour viter les inondations par TTL HopsTaken : Nombre de pairs visits par ce message DataLength : taille du champ data

17

Gnutella
I I

Transfert de fichiers par http lite Push descripteur pour passer les firewalls Les proprits Small-world sont vrifis (tout est proximit) Back-bone + extensions

Gnutella : problmes initiaux

I

Chargement libre (free riding)

Connexion sur gnutella sans apports de donnes, ni routage de requtes

Arrts prmaturs de transferts :

Temps de chargement sur modems
Les utilisateurs sont intermittents, de plus les autres utilisateurs sont bloqus Solution : busy code 2000 : 10% de transferts russis, 2001: 25%

18

Gnutella : problmes initiaux (suite)

I

2000 : 400-800 htes

modems: trous noirs de routage

==> Hirarchie de pairs en fonction des capacit de transport

avant : tous les pairs identiques Prfrence de connexion
Prfrence de route vers les pairs bien-connects Favoriser les rponses vers des pairs fournissant beaucoup de fichiers (viter le freechargement)

Apparition des passerelle limewire

cf napster pour la recherche

Gnutella conclusion
I I I I

Compltement dcentralis Les 'hits' sont levs Haute tolrance de pannes S'adapte trs bien et dynamiquement au changement de population des pairs Le protocole et trs gourmand (3,5 Mbps)
4 connexions C / pair, TTL=7 1 ping peut gnrer : 2*(0,TTL)C*(C-1)i=26240 packets

I I I I I I

Pas de borne sur la dure d'une requte Pas d'estimation sur le rsultat de la requte La topologie est inconnue => pas d'exploitation algorithmique FreeRiding est un problme Pas de rpudiation des pairs Simple, robuste, passe l'chelle (pour le moment)

19

Gnutella Recherche
I I I

Chaque pair connat un nombre fixe G

DXWUHV SDLUV (cd 4) Les pairs se dcouvrent par des messages ping Les requtes de recherches sont propages vers ces pairs dans la limite de 7 TTL Les pairs peuvent rpondre la requte s'ils stockent le fichier correspondant

Gnutella Recherche
a1->search(k7) Table de routage (a2)(a3) a3->search(k7,2) a1 a4->search(k7,1) a2->search(k7,2) a4->search(k7,1) a2 a4->search(k7,1) a4 Donnes locales k7, k8 a4->search(k7,1) a3

20

Gnutella Discussion
I

Type de recherche
Texte libre

Mise l'chelle
Recherche pauvre d'un point de vue global Temps de recherche en O(Log n) (small-world) Mise jour excellent : rien faire Information de routage : cot faible

Robustesse
Eleve, plusieurs chemins sont valus Exploite les proprits small-world

Autonomie
Stockage : pas de restriction, les pairs stockent les cls de leurs fichiers Routage : les pairs sont les cibles de n'importe quelles requtes (pas d'autonomie)

Connaissance globale
Non

Gnutella refs
[Adar00] Eytan Adar and Bernardo A. Huberman. Free Riding on Gnutella. Technical Report. Xerox PARC, 9, Septembre 2000. http://www.parc.xerox.com/istl/groups/iea/papers/gnutella/Gnutella.pdf [Clip01] Clip2. The Gnutella Protocol Specification V0.4 (Document Revision 1.2) June 15, 2001, http://www.clip2.com/GnutellaProtocol04.pdf [Gnutella01] Gnutella homepage, 2001. http://gnutella.wego.com/ [Jovanovic01] M.A. Jovanovic, F.S. Annexstein, and K.A. Berman. Scalability Issues in Large Peer-to-Peer Networks - A case study of Gnutella. University of Cincinnati, Laboratory for Network and Applied Graph Theory, 2001. http://www.ececs.uc.edu/~mjovanov/Research/Paper.ps [Sripanidkuchai01] Kunwadee Sripanidkulchai. The popularity of Gnutella queries and its implication on scalability. February 2001. http://www.cs.cmu.edu/~kunwadee/research/p2p/gnutella.html

21

Gnutella : Non Anonyme

I

La personne qui fourni le fichier connat son destinataire Eternity Freenet

I I

P2p : le point !
I

Modle centralis
Napster Index global maintenu par une autorit centrale Relation directe demandeur/fournisseur

Modle dcentralis
Freenet, Gnutella, Chord Pas d'index central - Connaissance locale uniquement (rponse approximative) Les mise en relation sont indirectes : ce sont des chanes d'intermdiaires

22

Freenet Historique
I I I I

PFE : Ian Clarke, Edimbourg, 1999 Sourceforge : http://www.sourceforge.net V.0.1 (Mars 2000) V.0.4 (Sept. 2001)

Cest quoi et pourquoi ?

I I I

La paranoa Systme de fichiers partags, distribu, p2p Compltement anonyme pour l'metteur et le consommateur de l'info
Impossible de dterminer l'origine ou la destination d'une donne Difficult pour un nud de savoir ce qu'il stocke (les fichiers sont envoys et stocks crypts) ==> Pas de poursuite possible

Les requtes sont routes vers la localisation physique la plus probable

Pas de serveur central Pas de broadcast contraint (cf gnutella)

I I

Les fichiers sont identifis indpendamment de leurs localisation physique Rplication dynamique des donnes Rsistant aux attaques dosde tiers

23

Freenet : comment a marche

I I I

Structure de donnes Gestion de cls Problmes

Comment un nud connat les autres Comment peut-il rcuprer des donnes Comment ajouter de nouveaux nuds Comment freenet gre ses donnes

Dtails du protocole
Information de l'entte

Freenet : Structure de donnes

I

Table de routage
Liste fixe d'autres pairs ip,tcp : cl (1 cl par pair)

Rpertoire de donnes
Prrequis
Trouver rapidement un document connaissant sa cl Trouver rapidement une cl proche Grer la popularit d'un document et savoir quels documents supprimer en cas de congestion...

24

Freenet : Gestion de cl
I

Les cls sont reprsentes par des URI :

freenet:TypeDeCle@data

Avec TypeDeCle
KSK : Keyword Signed Keys, elle reprsente un document SVK : Signature Verification Key SSK : SVK Subspace key, sous-arbre de nomage CHK : Content Hash Keys, signature de documents

Les cls peuvent tre utilises pour des indirections

KSK ---> CHK

Freenet : Keyword-Signed Key (KSK)

I

Bas sur une petite chane de description, classiquement un ensemble de mots cls dcrivant le document
freenet:KSK@cours/INSA/telecom/sfrenot/p2p

Deux amliorations :
Espace de nomage global (SVK, SSK) Encodage du fichiers (CHK)

25

Freenet : Gestion de cl (paranoa)

I

Signed-subspace Key (SSK)

Ajout d'informations concernant l'metteur afin d'viter les conflits de nomage (sous-espace) Cl priv pour signer l'espace/cl publique pour vrifier
freenet:SVK@HDOKWIUn10291jqd097euojhd01 freenet:SSK@1093808JQWIOEh8923Iah10/text/book/1984.html

Content-hash Key (CHK)

Algorithme de signature de message (MD5), calcul de hash du document

Freenet : Insertion d'une cl

I I

La cl est calcule (KSK, CHK,) Un message d'insertion avec la cl et un nombre de sauts alatoire (hop) est envoy sur le rseau Chaque pair contrle si la cl est dans son systme de stockage local
oui ==> la cl doit tre regnre non ==> on route vers le nud suivant hop --(pour choisir un nud suivant, il y a un algorithme de recherche de cls proche) On continue jusqu' hop=0

Si hop==0 et pas de collision, la cl est insre sur tout le chemin de routage

26

Elments de scurit et d'authentification

I

Anonymisation
Les nuds mentent alatoirement sur les requtes et s'annoncent comme tant l'origine ou la destination d'une requte Les Hop-to-live sont alatoires Il est impossible de remonter au nud source d'un document Il est impossible de connatre le nud qui a insr le document

Freenet : Rsum
I I I I I I I I I I I I I

Entirement dcentralis Forte tolrance aux pannes Robuste et passe l'chelle Rplication automatique du contenu S'adapte parfaitement et dynamiquement au changement de population de pairs Le spam peut tre limit (sous-espace) Le routage adaptatif respecte la bw Pas d'estimation de la dure d'une requte Pas d'valuation sur la russite d'une requte Pas de topologie=pas d'algorithme Le routage circonscrit les free-riders Rpudiation de pairs n'est pas pris en compte Prend en compte l'anonymit du producteur et du lecteur

27

Recherche dans freenet

I I

Chaque pair connat un nombre fixe d'autres pairs et XQH FOp que le pair stocke Les recherches sont routes vers le pair avec la cl la plus similaire
Si insuccs, la cl similaire suivante est essaye Distance lexicographique (autre distance possible)

I I

Les requtes de recherche sont limites dans le temps (500 sauts) Un pair peut rpondre s'il stocke la cl Quand la rponse est renvoye les pairs intermdiaires peuvent mettre jour leur information de routage

Freenet Recherche
a1->search(k7) (k3,a2)(k5,a3) a3->search(k7,2) a1 a3 k5, k6 a4->search(k7,1) (k3,a2)(k7,a4)

a2

a4 k7, k8

28

Freenet Dicussion
I

Type de recherche
Uniquement galit Cependant si les cls n'taient pas hashes, une similarit smantique pourrait tre utilis

Passage l'chelle
Bonne recherche O(Log n Mise jour excellente, pas de surcharge Information de routage : une phase de prdiction est ncessaire

Robustesse
Bonne, car les chemins alternatifs sont explors

Autonomie
Pas de restriction sur le stockage Routage : dpendance entre les cls stockes et les requtes reues

Connaissance globale
Cl de hash

Freenet
I

[Clarke01] Ian Clarke, Oskar Sandberg, Brandon Wiley, and Theodore W. Hong. Freenet: A distributed Anonymous Information Storage and Retreival System. Designing Privacy Enhancing Technologies: International Workshop on Design Issue in anonymity and Unobservability, LLNCS 2009, Springer Verlag 2001, http://www.freeenetproject.org/index.php?page=icsi-revised [Freenet01] Freenet project. Protocol Specs. 2001. http://www.freenetproject.org/doc/book.html [Langley01] Adam Langley. The Freenet Protocol 2001. http://www.freenetproject.org/index.php?page=protocol [hong01] Theodore Hong. Performance in Decentralized FileSharing Networks. Presentation given at the OReilly Peer-to-Peer Conference, San Fransisco. February 14-16, 2001. http://www.freenetproject.org/p2p-theo.ppt

29

p2p applicatif --> p2p optimis

I I

Exploitation des principes de small-worlds Extension de plus larges chelles, systmes bass sur les principes de hash
Chord Tapestry CAN

Chord
Service de recherche P2Pextensible pour applications Internet
,RQ 6WRLFD 5REHUW 0RUULV 'DYLG .DUJHU 0 )UDQV .DDVKRHN +DUL %DODNULVKQDQ
MIT & Berkeley

30

Comment retrouver une donne dans un systme de fichiers partag distribu ?

Motivation

N1

Internet

N2

N4

0    & ) ( ' & %$

# " !          

Serveur central (Napster)

La recherche est le point dur !

Solution centralise

N1

Internet

N5

N2

N4

0    & ) ( ' & %$

DB

N5

N3

N3

31
# " !          

Solution distribue (1)

I

Inondation (flooding) : Gnutella, Morpheus, KaZaa

N1
# " !          

N2

N3

Internet N4 N5

Pire cas : O(N) messages par requtes

Solution distribue (2)

I

Routage de messages (Freenet, Tapestry, Chord, CAN) N1

# " !          

N2

N3

Internet N4 N5

Recherche Exacte !

0    & ) ( ' & %$ 0    & ) ( ' & %$

32

Les dfis du routage

I I I I

Dfinir une bonne mtrique de proximit de cl Conserver le nombre de sauts petit Conserver des tables de routage raisonnable Rester robuste mme en cas de changement rapide de communaut de pairs Chord : se focalise sur l'efficacit et la simplicit

Les identifiants de Chord

I I I I I

Identification sur m bits pour les cls et les nuds Identification de Cl: SHA-1(key) Identification de Noeud : SHA-1(@ip) Les deux sont uniformment distribus Comment mapper les ids de cl sur les ids de noeud
# & "         "% $  "% $ " &% $ # " !          

33

Hashage consistent [Karger 97]

0
              

K5 K20 N32

N123 K101 Espace didentifiants circulaire sur 7 bits N90 K60

I

Une cl est stocke sur son nud successeur : le nud avec le plus gros ID suivant

Hashage consistent
I

Chaque nud connat tous les autres

Connaissance globale (! p2p)

Les tables de routages sont larges

O(N)
 0 ) 5  4   3 ( 2 ' ( 1  0 ) % $ "( ' & % $ " ! # " !

Recherche rapide O(1)

0
N123

N90
K60

N10

N32

34

Chord : recherche de base

I

Chaque nud connat sont successeur dans l'anneau 0

N123 N10
 0 ) % $ "( ' & % $ " ! # " !

N32

N90
K60

Recherche O(N) sauts

"Finger table" tables didentification

I I

Chaque nud connat m autres nuds de l'anneau En augmentant la "distance" exponentiellement

N112 N16

N96
 

N80

! ! (

N55

 



  

35

Les recherches sont plus rapides

I

Les recherches sont en O(Log N) sauts

N5 N110 N10 N20 N96 N32
% 4  )$ " ! # " ! 4 )

N80 N60

Rejoindre lanneau
I

Trois tapes
Initialiser les fingers des nouveaux nuds Mise jour des fingers des autres nuds Transfrer les cls des successeurs vers le nouveau nud

Mcanisme moins agressif (mise jour paresseuse des fingers)

N'initialiser que le finger pour le nud suivant Vrifier priodiquement le successeur et le prdcesseur immdiat Rafrachir priodiquement les entres de la table finger

36

Gestion des pannes

I I

Une panne de nud gnre une recherche incorrecte Un nud ne connat pas ses "bons" voisins
Chaque nud connat r successeurs directs Aprs une panne, on connat le premier succ. vivant Des successeurs corrects garantissent une recherche correcte

La garantie sous une certaine probabilit

Choisir r, afin d'avoir un taux de panne suffisamment faible

Evaluation
I I I

Recherche rapide dans de grands systmes Variation faible dans les cots de recherche Robuste mme en cas de panne massive Fond sur un modle thorique Performance dmontre Robuste

I I I

37

Faiblesse
I I

Pas si simple (cf CAN) Ajout dun membre est complexe

Mcanisme agressif ==> bcp de messages et de mise jour Pas d'analyse de la convergence dans le mode paresseux

Mcanisme de gestion des cls partag entre les couches applicatives et chord
Les couche hautes font les insertions et la gestion des pannes de nuds Chord transfert les cls quand les nuds arrivent (pas de mcanisme pour quitter !)

Les tables de routages augmentent avec le nombre de membre du groupe Le pire cas de recherche peut tre lent

Chord discussion
I

Type de recherche
Exacte

Passage l'chelle
Recherche O(Log n) Mise jour ncessite une recherche Fabrication : O(Log2 n) si un nouveau nud arrive

Rsistance (Robustesse)
La rplication peut tre utilise en dposant les rplicats sur les nuds suivants

Autonomie
Stockage et Routage : aucun Les nuds ont, de part leur adresse un rle spcifique

Connaissance globale
Mappage adresse / cl

38

Chord
I

[Karger97]

Tapestry
Routage et Localisation dcentraliss
Ben Y. Zhao CS division, U. C. Berkeley

39

Motivations
I

Les systmes de stockage partags ncessitent un mcanisme de routage et de localisation des donnes
Trouver un pair, tout en passant l'chelle est un problme difficile Mcanisme d'insertion et de recherche de donnes dans un trs grand systme

Solutions actuelles
Centralise : Coteux tendre, moins tolrant aux pannes, vulnrable aux attaques type DoS (napster, dns) Inondation : Pas de passage l'chelle (gnutella)

Cl : localisation et routage
I

Problme difficile
Localisation et envoi de message vers les ressources et les donnes

Approche : infrastructure doverlays large chelle

Passe l'chelle, Dynamique, Tolrant aux pannes, Equilibrage de charge

Hirarchie de localisation dcentralise

Un objet est stock dans une hirarchie de nuds La hirarchie dbute un nud racine qui identifie de manire unique l'objet

40

Tapestry
I

Infrastructure de localisation et de routage, dcentralise, passant l'chelle, tolrante aux fautes et adaptative Couche rseau du systme de stockage de masse OceanStore Routage hypercube bas sur le suffixe
Plaxton Algorithm (Plaxton, Rajamaran, Richa (PRR) SPPAA'97)

Core API
publishObject(ObjectID, [ServerId]) sendmsgToObject(ObjectId) sendmsgToNode(NodeId)

Routage hyper-cube
I

Hyper-cube de dimension 3 :
(1,1,0) +1,x,x (1,1,1) (1,0,1) x,+1,x (0,1,0) (0,1,1) x,x,+1 (0,0,1)

(1,0,0)

(0,0,0)

x,x,+1

41

Routage hyper-cube
I

Hyper-cube de dimension 3 :
N6 (1,1,0) (1,0,1) N5 N7 Routage (1,1,1) N1 (0,0,1) -> N7(1,1,1) ==> 2 sauts, car 2 bits de diffrence N3 N1 --> N5 --> N7 (0,1,1) ou N1 (0,0,1) N1 --> N3 --> N7

N4 (1,0,0)

(0,1,0) N2 N0 (0,0,0)

Routage de base
I I

Exemple : valeur octale, nommage 218, 005712-> 627510 Le routage se fait par rapprochement successif vers lobjectif 005712 340660 743210 434510

367510

727510

627510

==> Le nombre de sauts est 6 ?

42

Chaque nud possde une table de routage hirarchique

I

Ex : table pour de routage pour 5712

xxx0 xxx1 xxx3 xxx4 xxx5 xxx6 xxx7
Niveau 1

xx02 xx22 xx32 xx42 xx52 xx62 xx72

Niveau 2

x012 x112 x212 x312 x412 x512 x612

Niveau 3

0712 1712 2712 3712 4712 5712 6712 7712

Niveau 4

Insertion d'un objet

I

Espace de nommage commun (nud et objets)

Suffisamment grand pour viter les collisions (2160 ) (taille N dans Log2(N) bits)

Insertion
Hash de l'objet dans E ==> ObjectID For (i=0, i< Log2(N), i+j){ //On dfinit la hirachie de l'obj
j est la base de la taille des valeurs utilise (j=4, hex) Insrer l'objet dans le nud le plus proche qui correspond au dernier i bits Quand aucune correspondance n'est trouve, prendre le nud qui correspond (i-n) bits avec le plus grand ID, break

43

Routage vers un objet

I

Recherche dun objet

Traverser le rseau comme pour une insertion, mais en plus rechercher chaque nud l'objet For (i=0; i<Log2(N),i+n) Aller au nud et rechercher si l'objet y est stock Chaque objet est mapp sur la hirarchie dfinie par un nud racine f(ObjectId)=RootId) Publier / Rechercher les deux remontent de manire incrmentale vers la racine

Schma

C S

44

Le modle est un peu plus complexe

I

Il y a une indirection
Pour dposer un objet, le client calcule un identifiant de nud racine, qui connat la localisation exacte de l'objet La hirarchie accde en fait l'identification du nud racine.

store (Object, ObjectLocation) store (ObjectLocation, Root(Object)) pub(Root(Object), Hash(ObjectId))

Commentaires
I

Points forts
Modle thorique (Algo de Plaxton) Entirement dcentralis et passe l'chelle pour la localisation et le routage deterministe

Points faibles
Compliqu
Insertion dynamique de nud est complexe Ajout de nombreux nuds simultanement

Comment choisir le nud racine ?

Panne

45

CAN
Un rseau d'adressage de contenu qui passe l'chelle Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker ACIRI, UC. Berkeley, Tahoe Networks Transparents : (Sigcomm 2001)

Hash tables l'chelle d'internet

I

Hash tables
Structure de donnes essentielles de tous les logiciels

CAN : Internet-Scale Hash tables

Aussi intressant pour des systmes distribus large chelle insert (cl, valeur) valeur=accde(cl)

Objectif
Passage l'chelle Simple mettre en uvre/utiliser Bonne performance

46

Etendue du problme
I

Concevoir un systme qui fournit une interface

qui passe l'chelle robuste performante scurise

Au niveau applicatif
recherche par mot-cl contenu changeant anonyme

Can ide de base

k,v k,v

k,v

k,v

k,v k,v

k,v

k,v

k,v k,v k,v

47

Can ide de base

k,v k,v

k,v

k,v

k,v k,v

k,v

k,v

k,v

Insert (k1,v1)

k,v

k,v

Can ide de base

k,v k,v

k,v

k,v

k,v k,v

k,v

k,v

k,v

Insert (k1,v1)

k,v

k,v

48

Can ide de base

(k1,v1)
k,v k,v

k,v

k,v

k,v k,v

k,v

k,v

k,v k,v k,v

Can ide de base

k,v k,v

k,v

k,v

k,v k,v

k,v

k,v

k,v k,v k,v

accde (k1)

49

CAN : Solution
I I

Coordonnes cartsiennes virtuelles de l'espace Tous l'espace est partitionn par rapport aux diffrents nuds
Chaque nud possde une partie de l'espace

Abstraction
On stoque des donnes sur des points de l'espace On peut router d'un point vers un autre

Point = nud qui contient toute la zone de coordonnes

CAN: example de base

50

CAN: example de base

CAN: example de base

3

51

CAN: example de base

CAN: example de base

52

CAN: example de base

 

KDVK.

[\


I I

Routage dans CAN Construction plan

Insertion de nuds

Maintenance de CAN
Suppression de nud Rcupration de panne Relocalisation

  

Conception de CAN

53

CAN: routage
I

Voisins
4 voisins pour un plan 2d

CAN: routage
 

I I I

Espace dimension d n zones Taille moyenne de la route

(d/4)(n 1/d)

Un nud ne maintient la route que sur ses 4 voisins

54

 ) $ )      (  '  & % $  # "

3 2 10

1RXYHDX 1RHXG

!           

1RXYHDX QRHXG

1XG GH GpPDUUDJH

CAN: construction

CAN: construction

55

CAN: construction

1RXYHDX QRHXG

,  , URXWH YHUV [\ HW WRPEH VXU -

CAN: construction

 6pSDUHU OD ]RQH GH - HQ GHX[ PRLWLpHV OH QRXYHDX SRVVqGH XQH GHV PRLWLpHV

3 2 10

QRXYHDX

56

CAN insertion
I

L'insertion d'un nouveau nud n'affecte qu'un seul autre voisin et ses voisins immdiats

CAN : reprise sur panne

I

Panne simple
On connat les voisins des voisins Quand un nud tombe, un de ses voisins prend possession de la zone

Modle de panne plus complexe

Panne simultane de plusieurs nuds adjacents
Inondation partielle pour trouver les voisins Rare

Normalement seul le nud en panne et ses voisins sont concerns

57

CAN : rsum de la conception

I

CAN de base
Compltement distribu Auto-organis Les nuds ne maintiennent des tats que pour les voisins immdiat

De plus
Espaces indpendant multiples (ralits) Algorithme d'equilibrage de charge en tche de fond Heuristiques simple pour amliorer les performances

CAN : Forces & Faiblesses

I

Forces
Plus absorbant que des rseau d'inondation Efficace pour trouver une info Haute dispo des nuds et des donnes Possibilit de grer les tables de routage et le trafic rseau

Faiblesses
Pas de recherche floues Activit Malicieuses possibles (Dos) Doit maintenir une cohrence globale (Surcharge rseau, Distribution efficace) Latence du routage applicatif Performances faibles par rapport aux amliorations

58

Bittorrent
I

Optimisation du transport de gros volumes

Pas de recherche, Protocole de tlchargement p2p Repose sur un algorithme de type :
Un prt pour un rendu (tit-for-tat) 1/1 upload-download

Interface simple (save As) Les uploaders dcident vers qui envoyer les fichiers

Bittorrent Bram Cohen [email protected] 2003

59

Protocole
Dpose un fichier .torrent - fichier - taille - valeurs de hash - url dun tracker

Serveur Web

Client1

tlcharge le fichier Il devient un seeder Tracker

Commence uploader

Demande une liste de pairs possdant le fichier client3

Client2

Un fichier torrent
I

Segment en morceaux de 256k

Chaque morceau possde un code de hash Une fois quun morceau est tlcharg il est mise disposition des autres

Chaque morceau est galement dcompos en 16k

5 requtes de sous-morceaux sont mises en file dattente

I I

==> Un objectif tout ce qui rendre doit sortir ==> Bittorrent cherche optimiser le tlchargement

60

Algo de Selection des pices

I

Priorit stricte
Si un sous-morceau a t demand, le sous-morceaux suivant doivent appartenir au mme morceau On charge un morceau le plus rapidement possible Un morceau n'est mis en dispo que si sa cl de hash est valide

Le plus rare en premier

On tlcharge le morceau le moins disponible Le seed rpartit plus rapidement les morceaux Si le seed initial disparat cest plus robuste

Le premier est choisi au hasard

Un morceau rare sera plus long charger Aucune connaissance a priori des capacits des pairs

Derniers bits
Tous les sous-morceaux du dernier morceau sont demands simultanment tous les pairs On vite que le dernier download soit ralentit parce qu'on tombe sur un pair lent

Algorithmes de suffocation (choke)

I I

Les nuds doivent optimiser leur chargement sur un mode un prt pour un rendu . 4 pairs sont rgulirement dchok Lesquels
On cherche mettre des pairs directement en contact On dchoke les pair dont le download est le plus lev
Echantillon sur 10s, et attente sur 10s de plus (Pourquoi ?)

Dchokage optimiste alatoire chaque itration un des 4 est choisi alatoirement (30s) (seule manire de trouver des pairs plus rapides) Anti-snobisme : si un pair ne reoit rien d un autre pair pendant 1 minute, il coupe sont upload vers lui. Chargement uniquement : dans ce cas le choix se fait sur les pairs qui ont un meilleur taux d'upload

61

FIN...

62