Confronto di protocolli di routing delle richieste per il resource discovery in applicazioni peer-to-peer

1 Introduzione
Esistono diversi tipi di architetture p2p. Queste possono differenziarsi una dal-
l’altra dal punto di vista strutturale1 e/o per il diverso scenario d’utilizzo: le possibili
applicazioni vanno dalle comunit di  le-sharing alle VPN (Virtual Private Network)
aziendali, da sistemi di pubblicazione distribuita ad architetture per la condivisione
delle risorse di calcolo.
Fra le diverse architetture che si possono individuare, le applicazioni di  le-
sharing hanno raggiunto, negli ultimi due anni, una notevole diffusione, e questo
prima che potessero esserne valutati l’impatto sulla rete e la scalabilit .
Osservando il traf co generato da queste grosse comunit di utenti e studiando i
protocolli di ricerca usati, si Ł visto che, a dispetto della loro natura distribuita, questi
sistemi rischiano di essere poco scalabili [SGG01] [pro01] [Rit01] [FKM01].
Infatti, nonostante eliminino la necessit di potenti server (e soprattutto l’esigenza
di introdurne di nuovi qualora il numero di utenti cresca), al crescere del numero di
utenti si possono veri care due problemi:
 un eccessivo volume di traf co associato alle ricerche pu portare al DoS dei
nodi della rete;
 da un nodo della rete non si ha la visibilit di tutte le risorse condivise, ma solo
di una frazione di queste.
Tali questioni sono strettamente legate alla tecnica di routing delle ricerche utilizzata
dal sistema. Si vogliono, quindi, confrontare, rispetto al traf co generato e ai tempi
di risposta, quattro diversi protocolli di resource discovery per individuare quali di
questi, e in quali contesti, assicurino una buona scalabilit del sistema. I primi tre
sono basati sul  ooding (protocollo utilizzato da Gnutella), e il quarto Ł ispirato alla
tecnica di routing implementata in Freenet (sistema per la condivisione, in anonimato,
di documenti).
1Un esempio: Napster sfrutta dei server di indicizzazione delle risorse, mentre in Gnutella anche il
discovery delle risorse Ł distribuito
2
1 Introduzione
1.1 Organizzazione del documento
Questo documento Ł diviso in due parti principali:
 Nella prima parte (§2) daremo una de nizione di peer-to-peer (p2p), vedremo
quali sono gli scenari d’uso di un’architettura di questo tipo e quali i requisiti
che dovrebbe soddisfare. Descriveremo in ne lo stato dell’arte: quali sono
i prodotti, i progetti e le proposte esistenti e come questi si collocano nella
classi cazione precedentemente fatta.
 Nella seconda parte (dal §3 in poi) ci concentreremo su di un modello d’utilizzo
speci co del p2p (il  le-sharing), ed in particolare sul protocollo di routing
delle ricerche. Vedremo quali sono state le misure sperimentali, come sono
state realizzate, e quali sono stati i risultati del confronto tra le diverse tecniche
di routing analizzate.
3
2 Architetture peer-to-peer
In questo capitolo viene proposta una caratterizzazione e una classi cazione delle
diverse architetture p2p, fornendo alcuni esempi reali di sistemi p2p.
Avendo individuato una serie di architetture p2p gi consolidate e studiate in let-
teratura, vengono individuati quali sono i fattori emergenti che hanno riportato viva
l’attenzione verso il p2p e quali sono i requisiti e i servizi che possono caratterizzare
una generica infrastruttura distribuita.
Faremo poi una classi cazione delle diverse architetture secondo due punti di
vista differenti:

in base alla struttura, ovvero il tipo di interazione tra gli elaboratori coinvolti;

in base ai diversi scenari d’uso (e quindi allo scopo del sistema e al tipo di utenti
che lo utilizzano.
2.1 Architetture e applicazioni consolidate
Da diversi anni determinate branche dell’informatica si dedicano alla ricerca su pro-
blemi  distribuiti e, spesso, hanno cercato di risolverli con architetture serverless
(cioŁ p2p).
4
2 Architetture peer-to-peer
2.1.1 Database Distribuiti
La gestione di un Database (DB) distribuito Ł un problema piuttosto complicato. Si
possono distinguere due casi che vengono trattati in modo molto diverso.
Il primo caso Ł quello di un DB distribuito con un registro, che mantenga l’in-
formazione su dove sono  sicamente dislocati i dati. In questo caso si pu ancora
riuscire a fare transazioni  ACIDE 1: l’utente  nale non si rende conto che la sua
interrogazione coinvolge tanti DB sparsi su una rete.
Nel caso non ci sia un registro, la soluzione possibile Ł basata su agenti mobili
che si spostano per la rete alla ricerca delle informazioni richieste.
2.1.2 Calcolo distribuito
Lo studio di architetture multiprocessore porta a considerazioni analoghe a quelle che
si possono fare su di un sistema di computazione distribuita realizzato con calcola-
tori in rete fra loro. In questa particolare architettura p2p, i peer sono rappresentati
da processori che si scambiano messaggi o che condividono zone di memoria. Ri-
spetto alle reti di computer cambia la scala di diversi ordini di grandezza, la rete di
comunicazione Ł piø piccola e piø veloce, e quindi la valutazione delle prestazioni Ł
differente. Comunque le considerazioni sulla  partizionabilit  di un problema che
si fanno studiando il calcolo parallelo restano un buon punto di partenza anche per
architetture p2p su scala piø larga.
2.1.3 GRID
GRID signi ca griglia, rete a maglia, e infatti quello che i progetti di questo tipo si
propongono Ł di utilizzare le risorse di un’enorme infrastruttura di rete che gi esiste
ma che non viene sfruttata appieno nelle sue potenzialit globali. Obiettivi che ci si
pu porre sono:
1 Acide Ł la traduzione impropria dell’acronimo inglese  ACID , che sta per Atomicity Consistency
Isolation Durability
5
2 Architetture peer-to-peer

la creazione di un’architettura distribuita di calcolo, che, su scala abbastanza
vasta, costituirebbe uno strumento molto potente per la comunit scienti ca.
Questo genere di infrastrutture vengono dette computational grids;

la realizzazione di un sistema per la distribuzione dell’informazione che garan-
tisca aggiornamento, accessibilit , anonimato degli utenti, diffusione capillare.
Nell’ambito del Global Grid Forum [For] sono state studiate tante possibili applica-
zioni, e non solo nei due ambiti qui evidenziati.
2.1.4 File sharing su rete locale
Il concetto di condivisione dei  le su rete locale non Ł nuovo, sia i sistemi Microsoft
che quelli Unix/Linux prevedono la possibilit di condividere cartelle in modo sicuro
(con controllo degli accessi)2.
2.2 Caratteristiche e fattori emergenti
Possiamo individuare quattro fattori dominanti che hanno riacceso l’attenzione sul
p2p:

la diffusione sempre maggiore dell’accesso a larga banda alla rete, non solo su
 bra ottica, ma anche con le nuove tecnologie xDSL e via satellite;

la potenza dei moderni PC da casa (assai piø veloci delle workstation di qualche
anno fa), che resta inutilizzata per una consistente frazione del tempo;

la continua crescita delle dimensioni dei dischi (hard disk - HD), che ormai
raggiungono capacit nell’ordine delle decine di Gigabyte, e una contempora-
nea diminuzione dei prezzi: un moderno disco da 40 Gigabyte costa ora quanto
costava un paio d’anni fa un HD dieci volte piø piccolo;
2Tramite Samba Ł possibile condividere cartelle anche tra due computer con  le system diverso (FAT,
NTfs, EXT2fs).
6
2 Architetture peer-to-peer

i nuovi dispositivi che accedono alla rete: telefoni cellulari, computer palmari;
ma anche, nel caso della domotica, tutti gli elettrodomestici di casa.
I primi tre fattori sono estremamente correlati: la potenza di calcolo e le memorie
di massa sono dif cilmente sfruttabili se i dispositivi che li forniscono sono troppo
spesso off-line, e se la loro connessione alla rete, quando c’Ł, Ł molto lenta.
Il quarto fattore pone invece problemi diversi: la continua nascita di dispositivi
nuovi fa pensare che sia improponibile realizzare ogni volta soluzioni di accesso alla
rete  ad hoc . C’Ł bisogno di un standard, e un’architettura p2p si presta bene allo
scopo. Ai produttori basterebbe implementare pochi protocolli all’interno dei loro
dispositivi per renderli automaticamente  network-enabled , senza dover creare altre
infrastrutture di supporto, magari poco scalabili e molto costose.
2.3 Il  PLUS-valore del p2p
Si possono individuare tre  ambiti particolari in cui un’architettura p2p porta notevo-
li vantaggi: il groupware, i problemi non partizionabili, la gestione di dati dinamici.
2.3.1 Il groupware
Bob Metcalfe e Reed hanno studiato quello che si chiama  Connettivit potenziale
per transazione .3 In particolare, Reed illustra come in uiscano su questo parametro
l’introduzione del p2p, e successivamente del  grouping [Ree99]. Se le connessio-
ni sono punto-punto, l’andamento Ł proporzionale a N, dove N sono i nodi diretta-
mente raggiungibili. In una rete p2p, come dimostra Metcalfe, l’andamento diventa
proporzionale a


. In una Group Forming Network (GFN) la connettivit cresce
esponenzialmente con N (vedi  g. 2.1).
Questo signi ca che l’unione tra due o piø GNF porta con sØ un plus-valore
notevole.
3Potential Connectivity for Transaction, ovvero il numero di peer raggiungibili quando ci sia
necessit di inoltrare una richiesta
7
2 Architetture peer-to-peer
  
  ,   
   
 ,   
 	  
 	

N 
V
a
l
u
e
 
Figura 2.1: Gra ci delle tre leggi: Sarnoff, Metcalfe, Reed
Legge: Sarnoff Metcalfe GFN(Reed)
Rete con N membri   
 
Combinazione di reti con N
e M membri
  
 
   
 
Tabella 2.1: Plus-valore nella connettivit 
2.3.2 Problemi partizionabili e non partizionabili
Un problema si dice partizionabile se Ł scomponibile in diverse parti abbastanza
scorrelate tra di loro. Il punto sta proprio nell’ abbastanza : un problema si pu con-
siderare partizionabile  nchØ l’overhead dato dalla comunicazione tra le varie parti
del sistema non rende piø conveniente una soluzione  monolitica [Hou00c]. Se il
sistema Ł centralizzato, il server che gestisce lo scambio di messaggi diventa facil-
mente un collo di bottiglia. Un’architettura p2p elimina questo collo di bottiglia e,
quindi, sposta la soglia tra sistema partizionabile e non partizionabile.4
Per questo si pu dire che in generale un’architettura p2p funziona meglio di una
client/server per problemi poco partizionabili.
4
Il problema Ł simile a quello che si sperimenta quando si programma un OS (Operative System) e
si deve scegliere se realizzare un kernel monolitico piuttosto che a moduli.
8
2 Architetture peer-to-peer
2.3.3 La ricerca: dati statici e dati dinamici
Circa l’80% del web Ł costituito da HTML dinamico, e questa percentuale Ł in cre-
scita [Hel00]. Normalmente le informazioni dinamiche vengono prelevate da un DB
o da un repository presente sulla LAN (Local Area Network) del web server. Queste
informazioni non sono accessibili a un motore di ricerca classico, in quanto un craw-
ler5 non potr mai superare i  rewall della LAN e andare ad analizzare direttamente il
repository. In uno scenario di  le-sharing un’azienda pu decidere di condividere (in
modo sicuro) alcuni  le contenenti informazioni pubbliche. Un motore di ricerca po-
trebbe allora fornire risultati in tempo reale sul contenuto di questi  le. Il  le-sharing
alla  ne porta al p2p: come visto nel §2.3.1 il groupware in una rete p2p porta un
plus-valore davvero notevole.
2.4 Requisiti di un’architettura p2p
Come vedremo piø in dettaglio nel §2.6, i modelli d’utilizzo del p2p sono diversi, ma,
ci nonostante, si possono individuare alcuni requisiti chiave che dovrebbero caratte-
rizzare un’architettura p2p. Non Ł detto che tutti i modelli d’utilizzo e le applicazioni
speci che necessitino di ciascun requisito. Un’infrastruttura p2p che volesse esse-
re  general-purpose , e magari proporre uno standard, dovrebbe soddisfare almeno
i primi sette tra i vincoli illustrati di seguito: scalabilit , accessibilit , governabilit ,
controllo, condivisione, sicurezza, standard, mobilit delle informazioni, specializza-
zione e lavoro off-line. Una proposta del genere Ł quella della Endeavors Technology
con MagiTM [BGH  00].
Alcuni di questi requisiti appaiono irrimediabilmente in contrasto l’uno con l’al-
tro. Sta alla bont di un’architettura p2p trovare il giusto compromesso tra le necessit 
opposte.
5Agente mobile dei motori di ricerca che si sposta in Internet alla ricerca di pagine web da catalogare.
9
2 Architetture peer-to-peer
2.4.1 Scalabilit 
La de nizione di p2p fa pensare a un sistema di per sØ scalabile: quanto manca quello
che normalmente Ł il collo di bottiglia: il server. In realt non Ł solo questo il fattore
che determina la scalabilit del sistema: il meccanismo di comunicazione tra i peer Ł
un’altro fattore determinante sotto questo punto di vista. Vedremo piø avanti, parlan-
do di Gnutella (cfr. §2.8.3.2) come una tecnica di routing delle ricerche inadeguata
rischi di portare al collasso del sistema qualora il numero degli utenti cresca troppo.
2.4.2 Accessibilit 
Come abbiamo visto nel §2.2, una delle novit che ha reso nuovamente interessan-
te il p2p Ł la nascita di nuovi dispositivi che accedono alla rete. La possibilit di
recuperare informazioni da un terminale generico Ł quindi un requisito fondamentale.
L’accessibilit implica la necessit di un sistema che  traduca i contenuti in una
forma fruibile anche da dispositivi dalle capacit gra che o di elaborazione molto
limitate.
2.4.3 Governabilit 
Uno dei primi dubbi che sorgono quando ci si avvicina al p2p Ł cosa potr succedere
in assenza di un controllo centrale sui contenuti che vengono messi in circolazione.
Ci si chiede chi si occuper di proteggere il copyright, chi si preoccuper di evitare la
libera circolazione di contenuti osceni e/o violenti.
In particolare, nel caso delle VPN, l’infrastruttura p2p assomiglia molto ad un  le
system distribuito, e la governabilit include allora anche la gestione delle versioni, il
locking dei documenti e il controllo degli accessi a livello di gruppo e/o di utente.
2.4.4 Controllo
De niamo il controllo tramite un esempio. Supponiamo di voler accendere il forno di
casa per scaldare il pranzo prima di partire dall’uf cio tramite un telefono cellulare:
10
2 Architetture peer-to-peer
i due dispositivi sono pari per l’architettura, eppure uno dei due pu esercitare con-
trollo sull’altro. Questo privilegio di controllo non dev’essere, per , concesso anche
ad altri dispositivi sulla rete. Altre applicazioni del concetto di controllo nel p2p sono
simili all’odierno network management.
2.4.5 Condivisione
La condivisione Ł una caratteristica  famosa , nel senso che Ł quella che ha contribui-
to maggiormente, attraverso Napster e altri programmi simili, a rinnovare l’attenzione
verso il p2p. Il requisito di condivisione Ł, per , piø generale, e quella dei  le Ł solo
una sua specializzazione. Le altre possibili realizzazioni sono:

condivisione delle risorse di calcolo;
 condivisione dei dischi come capacit di memorizzazione;

condivisione delle attivit , cioŁ quello che gi realizzano strumenti come Lotus
Notes o MS Outlook;

condivisione di interessi e opinioni, come avviene nelle attuali comunit di
internet, ma con la possibilit in piø di essere indipendenti da un server che
fornisce il servizio.
2.4.6 Sicurezza
La condivisione dei propri dischi, la manipolazione di dati sensibili, ad esempio in
una VPN, comportano diversi rischi per cui una buona infrastruttura p2p deve fornire
uno strato di sicurezza che possa assicurare:

autenticazione, cioŁ identi cazione univoca di un utente;
 controllo degli accessi, cioŁ restrizione della possibilit di azione di ogni utente
o gruppo, in base ai rispettivi diritti;
11
2 Architetture peer-to-peer

con denzialit , cioŁ gestione della riservatezza: i contenuti privati e/o sensibili
devono poter essere disponibili solo per gli interessati;

integrit , ovvero non dev’essere possibile modi care o deteriorare delle infor-
mazioni senza lasciare traccia di questa operazione.
Esistono gi delle soluzioni standard a tutti e quattro i requisiti, tutto sta nel
riportarle all’interno di un’architettura p2p.
2.4.7 Standard
Il successo di un’architettura p2p dipender profondamente da quanto questa sapr 
imporsi come standard. Molte delle considerazioni fatte  nora sui vantaggi del p2p
(cfr. §2.3), come anche i requisiti di accessibilit e condivisione, perdono gran parte
del loro valore in uno scenario popolato da tante piccole soluzioni proprietarie non
interoperanti.
2.4.8 Portabilit 
Un altro fattore che pu in uire sullo  scope di un’infrastruttura p2p Ł la portabilit .
Se il client per accedere alla rete Ł disponibile solo per piattaforme Unix, tutti gli
utenti Microsoft o Macintosh non possono accedervi. Inoltre un client troppo  pesan-
te non potrebbe essere installato su PC con risorse limitate o su dispositivi con poca
potenza di calcolo come i palmari.
La portabilit di un’architettura non Ł data solo dalle caratteristiche del client,
ma anche dai servizi offerti dall’infrastruttura. La possibilit di sfruttare la potenza
di calcolo distribuita sulla rete o la capacit di demandare le procedure piø onerose,
come quelle che gestiscono la sicurezza, a dei  proxy-peer , rende un’architettura
portabile anche su macchine  piccole .
12
2 Architetture peer-to-peer
2.4.9 Disposizione delle informazioni - mobilit e caching
In uno scenario di condivisione  le (anche VPN) o di pubblicazione bisogna de nire
dove risiederanno  sicamente le informazioni, se andranno replicate e secondo quali
politiche. Una caratteristica auspicabile Ł che le informazioni  migrino verso le zone
della rete dove sono piø richieste.
Un altro elemento interessante Ł la possibilit di de nire delle politiche di con-
servazione dei documenti: ad esempio un documento scienti co, anche se Ł poco
richiesto, non si vorrebbe venisse cancellato, al limite si pu evitare che venga troppo
replicato. Per altri documenti pu essere invece utile che sia proprio il numero di
accessi a decidere l’eliminazione o meno degli stessi.
Le attuali tecnologie di caching potrebbero essere una buona soluzione per gestire
la mobilit e la  vita dei documenti. Ogni macchina potrebbe avere una parte di
documenti  ssi e non eliminabili, e un’altra parte di documenti  transitori , gestiti
dal meccanismo di caching e che migrano verso le zone della rete dove sono piø
richiesti.
2.4.10 Specializzazione e personalizzazione dei servizi
La specializzazione pu essere vista in due direzioni: dal singolo peer verso la rete
e viceversa. Nel primo caso Ł una funzione complementare all’accessibilit : de ni-
sce quali servizi pu fornire un determinato peer in base al tipo di device  sico e in
base alle funzionalit installate. Nel secondo caso permette all’utente di  ltrare l’in-
formazione in ingresso in base alle proprie preferenze. Ad esempio in una VPN un
utente pu scegliere di non vedere tutto il materiale relativo a dei progetti che non lo
interessano.
2.4.11 Gestione della connessione intermittente
L’accesso a larga banda (e continuo) Ł uno dei fattori che stanno favorendo la diffu-
sione del p2p (vedi §2.3), ma un’infrastruttura p2p deve permettere di gestire anche
13
2 Architetture peer-to-peer
quegli utenti che hanno ancora una connessione alla rete intermittente. Infatti alcuni
terminali, in particolare telefoni cellulari e palmari, solo in futuro saranno in grado
di mantenere una connessione permanente alla rete. La connessione pu essere in-
termittente anche quando questa Ł soggetta a una tariffa a tempo, oppure nel caso di
utenti mobili, dotati di pc portatili che possono connettersi al sistema tramite la rete
cellulare e tramite quella  ssa nel momento in cui si trovino in un uf cio.
2.4.12 Interazioni, con itti e soluzioni
Come gi accennato nel §2.4, i requisiti di un’architettura p2p sono spesso legati
uno all’altro, nel senso che possono concorrere ad uno stesso scopo come possono
risultare in contrasto su un determinato punto. Vediamo quali sono queste interazioni:
 Accessibilit e Specializzazione:
Per garantire accessibilit non bastano un canale  sico e un protocollo comu-
ne a tanti dispositivi diversi: Ł necessario che anche i contenuti vengano di
volta in volta rielaborati in una forma fruibile dai vari tipi di terminali. La
specializzazione si preoccupa anche di questa  conversione di formato ;
 Connessione intermittente e Accessibilit :
La diversit dei vari dispositivi sta anche nei modi e nei tempi con cui questi si
connettono alla rete. La gestione della connessione intermittente Ł quindi uno
dei fattori che contribuiscono ad assicurare l’accessibilit ;
 Accessibilit vs. Sicurezza:
La tanto auspicata accessibilit comporta per notevoli problemi: Ł dif cile
trasferire su dispositivi  piccoli come un telefono cellulare le funzionalit di
sicurezza illustrate nel paragrafo §2.4.6. Queste due caratteristiche sembrano
proprio essere incompatibili; in realt , a costo di un aumento di complessit ,
si pu trovare una soluzione. Ad esempio, alcuni peer possono richiedere che
i servizi di autenticazione, crittogra a, controllo d’accesso e validazione ven-
gano svolti da un proxy-peer. Questo dispositivo dovr essere per de nizione
14
2 Architetture peer-to-peer
sicuro, costituendo il punto debole di questo approccio. Di certo Ł impossibile
trovare una soluzione al contrasto tra accessibilit e sicurezza nell’ambito di
un’architettura pura;

Accessibilit , Specializzazione vs. Governabilit :
Gli aspetti dell’accessibilit piø legati alla specializzazione dei contenuti (vedi
sopra) sono in contrasto con il requisito di governabilit . La gestione del copy-
right e il controllo dei contenuti diventano dif cili su documenti che vengono
rielaborati dinamicamente per garantire la loro fruibilit . Il watermarking
6
di
 le audio, immagini  sse e  lmati pu aiutare a risolvere questa situazione;

Governabilit e Sicurezza:
La governabilit pu agire a livello dei documenti (watermarking), ma pu an-
che lavorare a livello di controllo degli accessi, ad esempio sui dischi dove sono
conservati i contenuti coperti da copyright. Questo Ł anche uno dei requisiti di
sicurezza, che si sposa bene, quindi, con la governabilit del sistema;

Sicurezza vs. Condivisione:
Condividere il proprio disco, o parte di esso, signi ca concedere l’accesso a dei
potenziali malintenzionati. Se da un lato lo sharing di documenti Ł facilitato dal
rilassamento dei vincoli d’accesso (cos da aumentare le informazioni reperibili
e sempli care la procedura di recupero), dall’altro la gestione dell’autenticazio-
ne e del controllo degli accessi, la crittogra a e la validazione proteggono da
intrusioni indesiderate, de niscono il limite tra privato e pubblico e caricano il
sistema di un overhead notevole.
6
Tecnica di marcatura per documenti audio e video resistente a  ltraggi e manipolazioni varie
15