Universitatea Politehnica Bucuresti Faculatea de Electronica, Telecomunicatii si

Universitatea Politehnica Bucuresti Faculatea de Electronica, Telecomunicatii si

Universitatea Politehnica Bucuresti Faculatea de Electronica, Telecomunicatii si Tehnologia Informatiei Retele peer-to-peer (P2P) Retele de Calculatoare si Internet proiect 2012 Indrumator Prof.dr. Stefan STANCESCU Student Bogdan ALECU Generaliti (1/3) Reea acoperit i reea de baz Reeaua de baz (underlay) este reprezentata prin nivelul 3 OSI (RETEA) si foloseste protocolul IP. Rutarea IP se face

folosind cea mai buna care existenta. Reeaua acoperit (overlay) este o reea virtual ce utilizeaz reeaua de baz. Nodurile (peerurile) folosesc algoritmi de rutare specifici ce difera de cei ai retelei de baza. Generaliti (2/3) Arhitectura reelelor peer-to-peer 1. Nivelul reea (Network layer) sau reeaua de baz, descrie caracteristicile de reea ale calculatoarelor conectate la internet. 2. Nivelul de management al nodurilor (Overlay Nodes Management layer) asigur managementul peer-urilor (descoperirea peer-urilor, algoritmi de rutare).

4. Stratul specific serviciilor (Services Specific layer) susine 5. Nivelul de aplicaie (Application-level layer) infrastructura P2P, componentele specifice aplicaiilor prin administrare temporala i paralelizarea operaiunilor exhaustive, prin managementul de continut i de fisiere. este format din instrumente, aplicaii si servicii care sunt implementate cu funcionalitai specifice peste infrastructura P2P. 3. Nivelul de management al caracteristicilor (Features Management layer) se ocup de securitate, stabilitatea, rezistenta la

eecuri. Generaliti (3/3) Reele peer-to-peer structurate. DHT. Reea P2P structurat nseamn c topologia reelei este controlat strict, datele sunt plasate n locaii cunoscute i nu aleator pentru eficientizarea cutrilor. Distributed Hash Tables (DHT) sunt tabele ce conin mai multe nregistrri de tip pereche cheievaloare. Cheile sunt indici unici obinuti printr-un algoritm de hashing aplicat obiectelor de date. Coloana de valori conine segmente din obiectele de date. Fiecare peer administeaz cte o astfel de tabel. Interaciunea aplicaiilor cu peer-urile prin intermediul DHT (privit aici ca sistem ce administreaz i distribuie tabelele) se face prin intermediul unei interfee API ce utilizeaza trei funcii pentru stocarea, stergerea i citirea valorilor (obiectelor de date): put(cheie, valoare); remove(cheie); get(cheie);

Cu ajutorul funciilor, o aplicaie P2P structurat ofer accesul la informaii aflate pe mai multe peer-uri. Identificarea peer-ului corespunztor unei chei revine tipului de sistem P2P bazat pe DHT folosit: CAN, Chord, etc. Distributed Hash Table (DHT) Funciile de hashing sunt folosite pentru a genera chei unice cu dimensiuni fixe pe baza unor coninuturi de date cu dimensiuni mari. Unicitatea cheilor nu este 100% asiguratat nsa algoritmii criptografici folosii au o rat a coliziunilor rezultatelor suficient de mic pentru a se preta unor astfel de aplicatii. Funcii: SHA-1, MD5, etc. Apelurile put(cheie, valoare); get(cheie); remove(cheie); se transmit sub form de mesaje n cadrul reelei acoperite i efectueaz salturi logice de la un peer la altul (prin intermediul referintelor stocate in peer-uri) pan cnd parametrul cheie satisface o relatie anume (specific sistemului P2P folosit) fa de identificatorul NodeID al peer-ului curent. Raspunsul primit ca urmare a apelului get(cheie); nu urmeaza aceeasi cale ca la dus. Rutarea in aceasta situatie pica in seama retelei de baza (care gaseste ruta optima spre adresa IP a initiatorului cererii). Content Addressable Network (CAN) CAN este un sistem P2P distribuit ce mparte un spaiu cartezian virtual cu d-dimensiuni n n subspatii pentru fiecare dintre peer-uri. Fiecare peer administeaza o tabela cu perechi cheie-valoare pentru toate obiectele de date stocate n cadrul su. In plus fiecare peer pastreaza o tabela cu adresele topologic relative si IP ale celor 2*d vecini. Rutarea mesajelor (apelurilor de functii API) se face folosind metoda greedy de cautare a celui mai aproiat vecin catre destinatie. Pentru identificarea peer-ului destinatiei (coordonatele pe cele d axe), cheia

folosita ca parametru este aplicata unei functii uniforme deterministe. Media lungimilor rutelor in cadrul retelei CAN este de (d/4) x (n1/d) iar in general distanta catre orice destinatie scade cu cresterea d. La intrarea n sistem a unui peer nou, un peer bootstrap alege aleator o locatie a unui peer existent. Se trimite comanda JOIN catre acea locatie iar peer-ul existent imparte spatiul sau si aloca cealalta jumatate noului venit. Perechile cheie-valoare din peer-ul vechi, corespunzatoare locatiei peer-ului nou, vor fi mutate. Se fac actualizarile necesare in peer-urile implicate. La plecarea din sistem a unui peer, unul dintre vecini va prelua zona si perechile de la acesta. In plus, va anunta toti vecinii sa-si actualizere tabelele de rutare cu noii vecini (sa ia cunostinta de plecarea si inlocuirea sa cu alt peer). Lungimea cailor va avea un grad de crestere O(n1/d) cu numarul de peer-uri din sistem. Disparitia brusca a unor peer-uri nu cauzeaza esecul retelei deoarece exista mai multe peer-uri raspunzatoare pentru fiecare obiect de date. In plus, n acest caz, reteaua rencearc accesarea cheii. Alte sisteme P2P structurate (1/2) Chord prezint un spaiu de valori circular pentru NodeID-uri i directional. Pentru identificarea peer-urilor specifice unor chei, se folosete funcia de egalitate. Parametrul principal ce influieneaza performana sistemului este N (numrul de peer-uri). Performana rutrii este O(logN) n timp ce numrul de nregistrari din tabelele de rutare necesare peer-urilor sunt logN. Numrul de actualizri necesare datorate unui peer ce intr sau iese din sistem este (logN)2. Disparitia brusca a unor peer-uri nu conduce la esecul retelei deoarece acest sistem permite replicarea datelor pe noduri consecutive pe cercul spatiului de valori i, in caz de eec, reeaua rencearc.

Atunci cnd un peer intr n sistem, pointerii de succesiune ai unor peer-uri trebuie s sufere modificri. Este important ca pointerii de succesiune sa fie la zi in orice moment deoarece corectitudinea cutarilor nu este garantata altfel. Inel Chord cu un cerc de identificatori compus din 10 peer-uri si 5 chei de date. Arata calea urmata de o cerere initiata de peer-ul 8 de cautare a cheii 54. Utilizeaza un protocol de stabilizare ce ruleaza periodic in fundal pentru a actualiza poointerii de succesiune si inregistrarile din tabela de fingers. Corectitudinea protocolului Chord se bazeaza pe faptul ca fiecare peer este constient de succesorii sai. Alte sisteme P2P structurate (2/2) Tapestry propune o structur de date distribuit, cunoscut drept plasa Plaxton (Plaxton mesh), optimizat pentru a suporta o reea acoperit pentru localizarea obiectelor de date caracterizate prin nume ce sunt conectate

la un peer radacin (root peer). Pe de alta parte, Tapestry utilizeaza mai multe peer-uri radacin pentru fiecare obiect de date pentru a evita efectul eecului cauzat de un singur peer (single point of failure). Utilizeaz hrti locale de rutare (routing maps) la fiecare peer pentru a ruta incremental, cifr cu cifr, mesajele ctre NodeID-ul de destinaie, de exemplu: ***7 => **97 => *297 => 3297, unde caracterul * reprezint un wildcard. Parametrii ce influieneaz performanele reelei sunt numrul de peer-uri N i baza indentificatorilor peer-urilor B. Performaa rutarii este O(logBN). Numrul de rute stocate de un peer este logBN. Numarul de actualizari datorate peer-urilor de vin si pleaca este logBN. Eecul unor peer-uri nu cauzeaz eecul reelei. Replicarea datelor pe mai multe peer-uri asigura acest lucru iar in plus se tine evidena mai multor ci ctre fiecare peer. Pastry aloc in mod aleator un NodeID de 128 de bii fiecarui peer din sistem fapt ce asigura distributia uniforma a peer-urilor in spatiul circular. Protocolul de lookup implica potrivirea cheii si a prefixului NodeID-ului peer-ului. Parametrii care afecteaza performaa sistemului sunt N (numarul de peer-uri) i B (B=2b baza identificatorului peer-ului ales). Rutarea mesajelor se face dintr-un numar de salturi ce variaza O(logBN) cu parametrii mentionati. Numrul de stari de rutare pentru fiecare peer este egal cu BlogBN + BlogBN iar actualizarile datorate dinamicii peer-urilor este logBN . Eecul unor peer-uri in Pastry nu cauzeaz eecul reelei. Se face replicarea datelor pe mai multe peer-uri. Se pastreaza evidena mai multor ci ctre fiecare peer.

Recently Viewed Presentations