Architetture distribuite per il Cloud (Sistemi P2P)

2020/2021

ARCHITETTURE DISTRIBUITE PER IL CLOUD –

RETI P2P - APPUNTI

CORSO LAUREA MAGISTRALE – CLOUD COMPUTING

Sommario

1. Introduzione .............................................................................................................................................. 5

2. Performance di un algoritmo ................................................................................................................... 8

2.1. Array lineari ....................................................................................................................................... 8

2.1.1. P=N ............................................................................................................................................ 8

2.1.2. Ordinare N numeri con meno di N processori ....................................................................... 10

2.2. Il Sorting nel modello a bit ............................................................................................................. 10

2.2.1. Modello lineare ....................................................................................................................... 10

2.2.2. due stringhe k bit con array lineare e un albero binario a k foglie ....................................... 10

2.3. Lower Bounds.................................................................................................................................. 11

3. Architetture ............................................................................................................................................. 12

3.1. Ipercubo .......................................................................................................................................... 12

3.2. Butterfly .......................................................................................................................................... 14

3.3. Wrapped Butterfly .......................................................................................................................... 15

3.4. Rete di Benes................................................................................................................................... 15

3.5. CCC (Cube-connected cycles) .......................................................................................................... 16

3.6. Shuffle exchange ............................................................................................................................. 16

3.7. De Bruijn graph ............................................................................................................................... 17

4. Reti P2P non strutturate ......................................................................................................................... 18

4.1. Caratteristiche di base delle reti di 1° e 2° generazioni ................................................................. 18

4.2. Reti P2P centralizzate ..................................................................................................................... 19

4.2.1. Esempio: protocollo Napster .................................................................................................. 20

4.3. Reti P2P Pure ................................................................................................................................... 20

4.3.1. Esempio Gnutella 0.4 .............................................................................................................. 20

4.4. Reti P2P ibride ................................................................................................................................. 21

4.4.1. Esempio Gnutella 0.6 .............................................................................................................. 21

4.4.2. FreeNet .................................................................................................................................... 22

4.5. Conclusioni ...................................................................................................................................... 23

5. Random Graphs, Small-Worlds and Scale-free Networks ..................................................................... 23

5.1. Motivazioni e proprietà .................................................................................................................. 23

5.1.1. Graph Theory .......................................................................................................................... 23

5.2. Random graph ................................................................................................................................. 24

5.2.1. Grafi casuali di Edos-Rényi...................................................................................................... 25

5.2.2. grafi casuali di Gilbert ............................................................................................................. 25

5.3. Regular Network ............................................................................................................................. 25

5.4. Small-world Networks .................................................................................................................... 25

5.4.1. The Miligram’s Experiment..................................................................................................... 25

5.4.2. Watt and Strogatz model ........................................................................................................ 25

5.4.3. Il modello di Kleinberg ............................................................................................................ 26

5.5. Scale-free Networks ........................................................................................................................ 26

5.5.1. Barabasi-Albert Model ............................................................................................................ 27

5.6. Peer to Peer Networks .................................................................................................................... 27

5.6.1. Symphony ................................................................................................................................ 27

6. Reti P2P strutturate ................................................................................................................................ 28

6.1. Distributed Hash Tables (DHT) ....................................................................................................... 28

6.2. Chord ............................................................................................................................................... 29

6.2.1. Routing .................................................................................................................................... 29

6.2.2. Algoritmo lookup .................................................................................................................... 30

6.2.3. Risultati ................................................................................................................................... 30

6.2.4. Join e Stabilization .................................................................................................................. 31

6.2.5. Failure and replication ............................................................................................................ 32

6.2.6. Leave........................................................................................................................................ 33

6.2.7. Realistic Analysis ..................................................................................................................... 33

6.2.8. Conclusioni .............................................................................................................................. 34

6.2.9. Sistemi P2P Uniformi .............................................................................................................. 34

6.2.10. Consistant Hashing .................................................................................................................. 35

6.3. Altre DHT ......................................................................................................................................... 35

6.3.1. Rete Tapestry .......................................................................................................................... 35

6.3.2. Rete CAN ................................................................................................................................. 35

6.3.3. Rete Viceroy ............................................................................................................................ 36

7. Lower Bound ........................................................................................................................................... 37

7.1. Lower Bound Sistemi uniformi ....................................................................................................... 37

8. Reti non uniformi .................................................................................................................................... 37

8.1. Grafi di De Bruijn ............................................................................................................................. 37

8.2. Koorde ............................................................................................................................................. 38

8.2.1. Koorde base 2.......................................................................................................................... 38

8.2.2. Koorde base k .......................................................................................................................... 40

Sistemi P2P

1. Introduzione

Sistema distribuito nel quale ogni nodo ha identiche capacità e responsabilità e tutte le comunicazione

sono potenzialmente simmetriche;

Non essendoci il server, il sistema è attivo finché un nodo qualunque è attivo, conoscere quanti nodi ci sono

è un problema, così come sapere dov’è situato un file.

Negli anni 90’ c’erano connessioni che non permettevano in nessun modo di condividere risorse e servizi,

siccome le risorse delle macchine erano molto basse. C’erano troppe risorse non utilizzate, è importante

usare sia le risorse lato server che lato client (c’è spazio su disco lato client non utilizzato) quindi si decide

di creare questi sistemi distribuiti che usano tutte le risorse non utilizzate precedentemente.

 Permettono di sfruttare risorse altrimenti non utilizzate

 Controllo decentralizzato (niente server, non puoi attaccare il sistema senza server, si deve

attaccare ogni nodo e se sono tanti è impossibile)

 Assenza di punti nevralgici (single point to failure)

 Si organizzano da soli (una volta messo su il sistema si organizza da solo se sono ben progettati e si

è considerato tutte le possibili dinamiche che possono accadere)

Tutto ciò che gli permette di comunicare ha un sovraccosto

Applicazioni

Il 90% delle volte su client lo spazio su disco vengono usati per File Sharing (condividiamo link, ma risorse

memorizzate nel loro responsabile, solo online sarà accessibile).

Altri utilizzi File storage system (entrati si fa il push di tutto ciò che c’è dentro e si può richiedere quel file

quando si vuole anche quando si è offline poiché risiederà sul nostro disco)

File system distribuito (file persistente da qualche parte nel sistema senza sapere con chi si sta gestendo

questa cosa), Grid Computing riguarda la computazione, dove ci sono degli slot di computazione che

possiamo andare a occupare, Redundant storage una copia di quello che viene memorizzato è disponibile a

qualche altro nodo, Anonymity system sistema anonimo di comunicazione (utilizzato magari per delle

aziende in cui gerarchie possono intimorire le persone coinvolte e quindi in forma anonima si ha più libertà

di pensiero), Collaboration system, Instant messaging system

Il problema è sapere in quale nodo si trova un certo file nella rete, poiché le risorse nell’architettura

server/client le risorse sono sul server.

Storia del P2P

ARPAnet era una rete P2P, l’introduzione del web ha spostato l’attenzione su strutture client/server

I primi sistemi P2P ICQ e Seti@Home

L’interesse per questo tipo di protocollo è aumentato verso il 2000 con i primi sistemi per file-sharing

(Napster, Gnutella)

Uno dei problemi iniziali era, ed è, il boot del sistema, gnutella trovò una soluzione conservando su un host

(come un server) i vari ip da poter poi andare ad accendere. Considerato come single point of failure visto

che buttato giù si potrebbe non accedere alla rete, abbiamo invece nei vari host una cache che tiene

memorizzati gli ultimi host contattati, cosi da poter usare sempre la rete.

Riposta back crowded, dove non vogliamo far capire da chi arriva la query, se vogliamo anonimia, il sistema

è meno efficiente, perché dobbiamo fare con la richiesta “un giro nella rete”.

P2P Scalabilità

Il lavoro richiesto a un determinato nodo nel sistema non deve crescere in funzione del numero di nodi del

sistema

Difficile che rimanga costante ma il sistema deve avere Overhead che cresce in maniera logaritmica

E sono nati così i cosiddetti protocolli P2P di terza generazione con DHTs (tabelle hash distribuite) (unica

cosa che ci basta per far funzionare un sistema P2P distribuito): Chord, Koorde, ecc..

Con DHT ad ogni risorsa e ad ogni nodo è associata una chiave (dovrebbe essere univoci visto la dimensione

dei bit utilizzati, non si controlla), lookup restituisce una risorsa ma se un nodo va via la risorsa viene

migrata ad un altro nodo e si deve rifare la lookup per capire dove è migrata la risorsa. Unica operazione

che ci serve è quella di lookup, data una chiave ci restituisce l’identità del responsabile (nodo) di quella

chiave.

Tutti i nodi condividono una tabella hash, ma non conoscono il responsabile di una determinata entry. Una

volta fatto lookup viene restituito il nodo e si va a chiedere al nodo restituito di fare la get della risorsa.

La rete è in continua evoluzione, ci sono nodi che si uniscono e vanno via in continuazione, le risorse si

spostano da una parte all’altra, ma la rete deve continuare a funzionare.

Rete di overlay, rete che si sovrappone a rete esistente e che aggiunge funzionalità, noi vogliamo una sola

funzionalità aggiuntiva, cioè la lookup.

Performance: abbiamo due obiettivi in contrapposizione, il primo è minimizzare il grado dei nodi, perché

più connessioni abbiamo e più traffico avremo (nodi che fanno join e leave), ma d’altro canto vorremmo

trovare velocemente una risorsa, quindi minimizzare il diametro (i passi da fare nel grafo per raggiungere

una risorsa), e per farlo dobbiamo aggiungere connessioni (nodi), ciò va in conflitto con il punto di prima, in

poche parole vorremo avere da un lato la rete sparsa e da un lato densa, dobbiamo trovare un

compromesso.

Queste condizioni sono necessarie ma non sufficienti, se abbiamo un diametro di 10, non è detto che

raggiungiamo in 10 passi la risorsa (solo con flooding, ma in una rete P2P non possiamo permettercela)

dobbiamo fornire un algoritmo che permette di raggiungere queste condizioni, si stabiliscono dei lower

bound. tabella di routing è la lista dei vicini (una

rete P2P deve essere sempre connessa,

quindi c’è almeno 1 vicino e al massimo n-1);

 Rete con grado 1 non abbiamo

scelta, anello, richiede n-1 passi e non

scalabile, non va bene

 grafo totalmente connesso,

possiamo raggiungere qualsiasi risorsa con

un passo, ma non è scalabile perché la

tabella dei vicini sa tutto di tutti mantiene n-

1 id

 La scelta migliore che possiamo

ottenere è quando il grado di nodi è

logaritmico in funzione del numero di nodi

del sistema e la lookup (diametro del

sistema) logaritmico anch’esso (Chord e altri

si trovano qui)

 Chord e altri non sono ottimali perché non si trovano nella curva del lower bound c’è ancora

qualcosa che dovrebbe essere migliorato. Ci sono alcune reti che si trovano su quella curva ma

hanno degli svantaggi che precludono il loro utilizzo come rete.

Classificazione un server per la lookup e poi comunicazione P2P pura (come

napster)

attraverso una gerarchia quando un web server non riesce a

gestire, si usano più web server per gestire le richieste, una volta

scoperto la risorsa si avvia una comunicazione P2P (server

sostituito da una gerarchia)

ciò che ci interessa nel corso, comunicazione e lookup P2P, ma ci

servono meccanismi di comunicazioni

Sistemi P2P che utilizzano SuperPeer: 3 tipi di comunicazioni

P2P tra i super peer, poi comunicazioni client/server tra

superpeeer e i peer gestiti dal superpeer, comunicazione P2P

tra i peer

P2P Classificazione in base all’applicazione fornite: File Sharing, Communication, Distribuited computing,

collaboration.

P2P proprietà desiderate: Scalabilità (crescita senza far aumentare l’overhead sui nodi), stabilità (il fatto

che entrano ed escono continuamente nodi non deve causare instabilità nella rete), performance (es se

facciamo richiesta di una risorsa vogliamo che arrivi in pochi millesimi di secondo), decentralizzazione

(impatterebbe sulla scalabilità se fosse centralizzato), load balancing (anche il bilanciamento del carico

impatta sulla scalabilità), topology awarness (conoscenza di quello che è la struttura della rete per rendere

il sistema più efficiente, vengono randomizzati le id dei nodi e vengono assegnate le risorse sulle id senza

considerare dove si trovano questi nodi, questo però impatta su altre proprietà come scalabilità e il

bilanciamento del carico), flessibilità (funzionare bene con qualunque carico).

P2P far fronte a fallimenti

Bisogna tener in considerazione che sono possibili informazioni e quindi il sistema deve auto-configurarsi

nel momento in cui c’è una perdita da parte di un nodo e dal punto di vista topologico devono essere

riprogettati e recuperati i link caduti e le risorse sul nodo possono essere recuperate solo se erano

duplicate, quindi tipicamente le risorse aggiunte al sistema vengono duplicate più volte in modo che è

improbabile perdere una