Sistema P2P
Persistente e Bilanciato
Estratto da :
Emanuele Spinella
Corso di Reti di Calcolatori LS
Prof. Antonio Corradi
A.A. 2003/2004
Reti Peer To Peer




Una rete Peer To Peer (P2P) è un sistema
distribuito che permette agli utenti in
possesso di una certa applicazione di
connettersi fra loro e condividere
informazioni
Paradigma C/S
Ogni terminale può fungere
alternativamente o simultaneamente da
client e da server
Comunicazione molti-a-molti
Reti Peer To Peer

3 possibili modelli:




Centralizzate
Decentralizzate
Ibride
Ogni modello con proprie
caratteristiche, punti deboli e punti
di forza
Reti P2P Centralizzate




Unico sistema centrale che gestisce il
traffico degli utenti
Il sistema centrale è costituito da uno o più
server coordinati
Il sistema centrale dispone di directories in
cui tiene l’elenco dei files condivisi e tutte le
info necessarie per localizzare i proprietari e
connettersi ad essi
Napster come tipico esempio
Reti P2P Centralizzate

Il peer che necessita di
un file inoltra la
richiesta al sistema
centrale, il quale lo
indirizza verso il
proprietario del
documento e fornisce
il supporto per stabilire
la connessione
Sistema Centrale
Search
file
Peer
Data
Connection
Tranfer
Peer
Detect
source
Peer
Reti P2P Centralizzate

Vantaggi:


Efficienza e velocità di ricerca (servizio simile
a quello di naming)
Svantaggi:


Tempo di aggiornamento delle directories
difficile da dimensionare
Sistema centrale come pericoloso punto di
rottura da cui dipende la disponibilità di
servizio
Reti P2P Decentralizzate

Nessun sistema centrale: ogni peer si fa carico
delle operazioni di ricerca e connessione (es.
Gnutella)
Peer
Search
file
Data
Detect
Connect
transfer
source
Peer
Peer
Reti P2P Decentralizzate

Vantaggi:



Flessibilità: non esistono punti di rottura che
possono inibire il servizio
Anonimato degli utenti
Svantaggi:

La mancanza di registrazione riduce il
controllo sugli utenti: QoS non sempre
garantita
Reti P2P Ibride



Risultato dell’unione delle due
precedenti soluzioni
Presenza di molti supernodi (server)
presso ognuno dei quali sono registrati
un certo numero di utenti
Tutti i moderni sistemi P2P adottano
una soluzione ibrida (WinMX, Kazaa,
eMule, ecc.)
Reti P2P Ibride

Il meccanismo di ricerca è simile a quello delle reti
centralizzate, ma il peer cliente e quello servitore
possono appartenere a supernodi diversi
Search file
Peer
Access
Access
Not
Data
directory:
directory:
Connect
transfer
found!
search
search
file infile in
my subnet
my subnet

Detect
source
Peer
Search file
Peer
Peer
Server
Peer
Server
Peer
Reti P2P ibride


Il server ricerca il file all’interno dei
peers registrati presso di esso e
propaga la richiesta anche verso gli
altri supernodi, che cercheranno nel
proprio gruppo di utenti
A ricerca terminata si effettua la
connessione che precede il
trasferimento dei dati
Reti P2P ibride



Possibilità di gestire il livello di decentralizzazione o
centralizzazione
Un elevato numero di supernodi aumenta la
decentralizzazione e diminuisce l’incidenza
derivante dall’eventuale crash di un server (più
supernodi significa meno peers registrati presso
ognuno di essi, quindi meno utenti isolati dal
servizio in caso di crash), ma si giova meno dei
vantaggi che i server stessi possono offrire
Un basso numero di supernodi sposta l’architettura
verso il modello centralizzato, con tutti i vantaggi e
gli svantaggi che questo comporta
Rete P2P
persistente e bilanciata



Necessità di dotare una rete P2P di
caratteristiche atte ad aumentare la QoS
offerta sui fronti della persistenza e del
bilanciamento del carico
Applicazioni in contesti che richiedono un
alto livello di dependability (es.
condivisione di importanti documenti fra
stazioni di polizia e organizzazioni per la
sicurezza sparse nel mondo e connesse in
rete)
Adozione della architettura ibrida
Persistenza

La persistenza rappresenta la
principale caratteristica del sistema:


Persistenza dell’infrastruttura: necessità di
far fronte ad eventuali crash dei supernodi
per evitare l’isolameto dalla rete dei peers ad
essi connessi
Persistenza dei nodi: ogni singolo nodo
deve garantire la persistenza in quanto
depositario di importanti informazioni.
Necessità di impiego di un modello di
replicazione adeguato
Bilanciamento del carico


Evitare la presenza contemporanea di
nodi inattivi e nodi sovraccarichi
Se un nodo richiede un documento
posseduto da più peers, è opportuno
che si valuti lo stato di carico di
ognuno di essi e si effettui il
trasferimento da quello con il numero
inferiore di connessioni correnti
Architettura

Tre attori principali:



LookUpServer: svolge le funzioni tipiche dei
supernodi (supporto per una ricerca efficiente
e veloce dei documenti)
Peer: rappresenta un terminale della rete
P2P (può essere uno dei computer presenti
in una stazione di polizia)
PeerCopy: rappresenta la copia esatta di un
Peer e fornisce il supporto per il modello di
replicazione atto a garantire la persistenza
dei nodi
LookUpServer


Ogni peer, al suo ingresso nella rete, deve
registrarsi presso un LookUpServer
Novità rispetto al modello ibrido standard: il
LookUpServer non possiede nessuna
directory delle risorse condivise (utilizzo di
messaggi di ricerca)



A fronte di una richiesta il LookUpServer del nodo
client (MasterServer) invia dei messaggi di ricerca a
tutti i propri peers e agli altri servers (SlaveServer)
Maggiore overhead di comunicazione
Eliminati i problemi derivanti dalla frequenza di
aggiornamento delle directories
LookUpServer (ricerca)

Il peer client invia la richiesta al proprio
LookUpServer (MasterServer)
Peer
LookUpServer
(SlaveServer)
Peer
Peer
Peer
LookUpServer
(MasterServer)
Peer
LookUpServer
(SlaveServer)
Peer
Search message
Response message
Peer
LookUpServer (ricerca)

Il MasterServer replica la richiesta ai
propri peers e agli SlaveServer
Peer
LookUpServer
(SlaveServer)
Peer
Peer
Peer
LookUpServer
(MasterServer)
Peer
LookUpServer
(SlaveServer)
Peer
Search message
Response message
Peer
LookUpServer (ricerca)

Gli SlaveServer replicano la richiesta ai
propri peers
Peer
LookUpServer
(SlaveServer)
Peer
Peer
Peer
LookUpServer
(MasterServer)
Peer
LookUpServer
(SlaveServer)
Peer
Search message
Response message
Peer
LookUpServer (ricerca)

I peers che hanno ricevuto la richiesta
rispondono ai propri LookUpServer
Peer
LookUpServer
(SlaveServer)
Peer
Peer
Peer
LookUpServer
(MasterServer)
Peer
LookUpServer
(SlaveServer)
Peer
Search message
Response message
Peer
LookUpServer (ricerca)

Il MasterServer riceve le risposte
raccolte dagli SlaveServer
Peer
LookUpServer
(SlaveServer)
Peer
Peer
Peer
LookUpServer
(MasterServer)
Peer
LookUpServer
(SlaveServer)
Peer
Search message
Response message
Peer
LookUpServer (ricerca)

Il MasterServer compone la risposta complessiva e
la invia al client, il quale dovrà poi scegliere il
documento che desidera
Merge
responses
Peer
LookUpServer
(SlaveServer)
Peer
Peer
Peer
LookUpServer
(MasterServer)
Peer
LookUpServer
(SlaveServer)
Peer
Search message
Response message
Peer
Merge responses





Problema dovuto alla formulazione delle richieste
con stringhe che non costituiscono un match esatto
con il nome del documento desiderato
Possibilità di trovare più documenti che contengono
la stringa di query (es. la stringa “ack” può causare
il ritrovamento dei files acknowledge.pdf,
racket.mp3, sacker.doc, pippo.ack, ecc)
Più peers possono avere lo stesso documento
Il MasterServer deve elaborare le risposte ricevute
dai propri peers e dagli SlaveServer raggruppando
le occorrenze uguali
Lo stesso devono fare gli SlaveServer con le
risposte provenienti dai propri peers
RequestFile


E’ una struttura dati che rappresenta
un file il cui nome contiene la stringa di
query
Ogni RequestFile è caratterizzato dal
nome del file che rappresenta e dalla
lista dei peers che lo possiedono
RequestFile
- Name
- PeerList [ ]
+ addPeerList(in pList[ ])
RequestFile



Ogni LookUpServer riceverà un certo numero
di RequestFile e dovrà unire quelli omonimi in
un unico oggetto, aggregando le liste dei
peers proprietari
L’utente che ha inizialmente fatto la richiesta,
alla fine del procedimento di ricerca, potrà
scegliere fra un insieme di files (RequestFile)
diversi senza sapere a chi appartengono
(trasparenza della locazione)
Il download di una risorsa appartenente a più
nodi viene gestita dal sistema scegliendo il
peer ‘migliore’ da cui scaricare, in modo da
bilanciare il più possibile il carico sulla rete
RequestFile (merging)

Ogni peer istanzia un RequestFile per ogni file in
suo possesso che fa match con la query
Request File
Request File
Name = resA
PeerList = {p1}
Name = resA
PeerList = {p2}
Request File
Request File
Name = resB
PeerList = {p1}
Name = resC
PeerList = {p2}
Peer p1
Peer p2
LookUpServer
RequestFile (merging)

Il LookUpServer riceve i RequestFile di tutti i peers e
unisce quelli omonimi modificando opportunamente
la PeerList
Request File
Request File
Request File
Name = resA
PeerList = {p1}
Name = resA
PeerList = {p2}
Name = resA
PeerList = {p1, p2}
Request File
Request File
Request File
Name = resB
PeerList = {p1}
Name = resC
PeerList = {p2}
Name = resB
PeerList = {p1}
Peer p1
Peer p2
Request File
Name = resC
PeerList = {p2}
LookUpServer
Result
Peer



Nodo che può effettuare e/o ricevere
richieste di ricerca di files
In caso di richiesta ricevuta, il Peer deve
controllare nella propria directory di sharing
la presenza di uno o più files nel cui nome
sia contenuta la stringa di query
Per ogni file compatibile con la query il Peer
deve comporre un oggetto RequestFile e
inviarlo al proprio LookUpServer
PeerCopy


Ogni Peer è dotato di una copia, fisicamente
rappresentata da un diverso terminale, che
possiede gli stessi files condivisi
dall’originale
Il modello di replicazione utilizzato è quello
a copie calde e passive:


Calde in quanto vengono create insieme
all’originale e si mantengono aggiornate sullo
stato del sistema
Passive perchè non eseguono fino al crash
del peer associato
PeerCopy


Dal punto di vista logico
il Peer estende il
concetto di copia; infatti
quest’ultima è un Peer a
tutti gli effetti, a parte il
fatto che non può
inoltrare richieste, ma
solo riceverne ed
eventualmente eseguire
l’upload dei files
Esattamente come un
Peer, la copia si deve
registrare presso il
LookUpServer (lo stesso
del Peer cui è associata)
1
PeerCopy
1..*
«estensione»
1..*
LookUpServer
1
Peer
QoS: Persistenza


La persistenza è ottenuta mediante un
sistema di heartbeats che consente di
testare costantemente lo stato di
attività dell’infrastruttura di supporto
(LookUpServer) e dei peers
La mancata ricezione dell’heartbeat
allo scadere di un timeout, provoca
l’innesco di una procedura di recovery
QoS: Persistenza
dell’infrastruttura di supporto


L’eventuale crash di un LookUpServer
può causare l’isolamento dalla rete di
tutti i peers (e delle copie) ad esso
connessi
Iniziativa dei peers e delle copie per
monitorare lo stato del server ed
eseguire l’eventuale procedura di
recovery (monitoring non centralizzato)
QoS: Persistenza
dell’infrastruttura di supporto

Invio periodico di heartbeats (hb) dal
LookUpServer ai peers connessi
Peer
Peer
Peer
Server
Peer
PeerCopy
Server
Peer
Peer
Peer
Server
PeerCopy
Peer
QoS: Persistenza
dell’infrastruttura di supporto

Dopo la ricezione di ogni hb, il Peer fa partire un
timer, prima dello scadere del quale deve essere
ricevuto l’hb successivo
Peer
Peer
Peer
Server
Peer
PeerCopy
Server
Peer
Peer
Peer
Server
PeerCopy
Peer
QoS: Persistenza
dell’infrastruttura di supporto

In caso di guasto, gli hb non possono più essere
inviati e il timer di ogni Peer scade
Peer
timer
Peer
Peer
Server
Peer
PeerCopy
Server
timer
Peer
Peer
Peer
Server
PeerCopy
Peer
QoS: Persistenza
dell’infrastruttura di supporto

Ogni Peer esegue una procedura di recovery che
consiste nel registrarsi presso un altro server e
indurre la copia a fare lo stesso
register
New
Server
Info
Peer
Peer
register
Peer
Server
Peer
PeerCopy
register
New
Server
Info
Peer
Peer
register
Peer
Server
PeerCopy
Peer
QoS: Persistenza
dell’infrastruttura di supporto

Viene ristabilito il sistema di hb
Peer
Peer
Peer
Server
Peer
PeerCopy
Peer
Peer
Peer
Server
PeerCopy
Peer
QoS: Persistenza dei nodi


In caso di crash di un Peer deve essere
automaticamente messa in esecuzione la
copia, per garantire la continuità del servizio
La copia, calda e passiva, mantiene
monitorato lo stato di attività dell’originale
ricevendo da questo dei segnali di hb
PeerCopy
Peer
QoS: Persistenza dei nodi

In caso di crash del Peer, la copia non riceve più
alcun hb e, allo scadere di un timeout, inizia la
propria procedura di recovery
PeerCopy timer
Peer
Server
hb
Server
PeerCopy
QoS: Persistenza dei nodi

PeerCopy disattiva l’originale sul server: il binomio
Peer/PeerCopy è sempre presente, un flag
stabilisce quale dei due è attivo
Deactivate
original Peer
PeerCopy
Peer
Server
hb
Server
QoS: Persistenza dei nodi

I parametri dell’originale vengono mantenuti all’interno
del server anche in caso di crash, in modo da poter
essere riutilizzati in seguito a una futura riattivazione e
per mantenere la corrispondenza con la copia
Deactivate
original Peer
PeerCopy
Peer
Server
hb
Server
QoS: Persistenza dei nodi

Le richieste di files arrivano al Peer originale o alla
copia a seconda dello stato del flag. PeerCopy è
perciò in grado di effettuare l’upload di un file
Deactivate
original Peer
PeerCopy
Peer
Server
hb
Server
QoS: Persistenza dei nodi

La seconda fase del protocollo di recovery prevede la
redirezione degli hb del server verso la copia: poiché
l’originale è down spetta alla copia monitorare lo stato
di attività del LookUpServer
PeerCopy
Server
hb
Peer
Server
hb
Server
QoS: Persistenza dei nodi




Il crash di un Peer può avvenire in un momento di
inattività, ma anche durante il trasferimento di un
file
Oltre al protocollo di recovery bisogna gestire
anche il fallimento del trasferimento dati
Il Peer sorgente invia al nodo ricevente, prima
dell’inizio del trasferimento, l’indirizzo della propria
copia
In caso di fallimento del Peer il nodo ricevente può,
senza effettuare nuove ricerche, rivolgersi
direttamente alla copia per riiniziare il trasferimento
QoS: Persistenza generale


E’ anche possibile che i guasti non
colpiscano isolatamente il
LookUpServer o il Peer, ma entrambe
le entità
Di particolare interesse il caso di
guasto di un LookUpServer in un
momento in cui anche il Peer originale
è down
Registrazione virtuale


Peer e PeerCopy sono due entità che
collaborano per rappresentare un
unico concetto di nodo persistente
Finchè la copia è attiva, l’utente
percepisce il nodo come attivo, in
quanto è in grado di fornire il servizio
(anche se l’originale è down)
Registrazione virtuale




Esattamente come nel caso di crash del solo Peer
originale, il binomio Peer/PeerCopy deve rimanere
presente a livello di LookUpServer
Se cade anche il LookUpServer, spetta alla copia
effettuare una nuova registrazione presso un altro
server, sia di se stessa, sia dell’originale andato in
crash (registrazione virtuale)
Sul nuovo server vengono inseriti i parametri della
copia e dell’originale, esattamente come sul
vecchio. Viene infine opportunamente settato il flag
che segnala l’attività della copia
Quando il Peer originale verrà riattivato si ritroverà
registrato presso un server differente
Bilanciamento del carico


Aspetto relativo alla QoS avente la finalità di
distribuire, con politiche che rispettano il
principio di minima intrusione, il carico in
modo omogeneo sui diversi nodi
Bilanciamento a livello di:


Peer/Copia: per quanto riguarda il
trasferimento dati
LookUpServer: per quanto riguarda il
numero di registrazioni
Registration Balancing



L’ingresso nella rete da parte di un Peer
presuppone la sua registrazione presso un
LookUpServer
Ogni Peer dispone di una lista di server
memorizzata in locale sotto forma di file
Il Peer contatta il primo server attivo della lista, il
quale:


Aggiorna la server-list del Peer con l’elenco
attuale dei server attivi
Rileva il numero di connessioni di tutti i server
attivi e dirige la registrazione del peer verso il
LookUpServer meno carico
Data Transfer Balancing




In seguito a un processo di ricerca l’utente
può decidere di scaricare un documento
posseduto da più peers
Rilevazione del ‘best peer to download’
Il peer richiedente contatta tutti i nodi
presenti nella peer list dell’oggetto
RequestFile associato alla risorsa
desiderata, per conoscere quello meno
carico e connettersi ad esso
Viene stabilita la connessione con il nodo
che sta effettuando il numero minimo di
trasferimenti