Sartomiki.net

Client-server e peer to peer
Esistono due modi distinti di scambiare informazioni all'interno delle reti:
-Approccio client-server, in cui c'è un servitore che fornisce il servizio e gli utenti (client), che lo utilizzano. Il servitore (server) deve essere una macchina con grande capacità di calcolo e con un'ampia banda a disposizione. Esempi tipici di applicazione di questo principio sono il web e l'ftp. Questo sistema ha diversi problemi intrinsechi come la non scalarità (poichè un unico server tenderà a collassare con l'aumento del traffico) e l'impossibilità di avere un servizio senza un fornitore. Questo tipo di approccio era giustificato in passato in quanto c'era una certa differenza tra la banda fruibile da un server e quella destinata ai client. Al giorno d'oggi, invece, la banda dei client è aumentata molto e siamo nella situazione in cui non tutti i client riescono a sfruttarla.
-Approccio peer to peer, in cui non c'è più la figura del server. I ruoli non sono più definiti, in quanto i peer sono dei nodi ambivalenti i quali mentre mettono a disposizione un servizio, ne sfruttano le potenzialità. In un certo senso incorporano al loro interno sia un client, che un server. I peer nascondono l'assenza del server, in quanto ne mettono a disposizione uno virtuale, che è distribuito su tutta la rete. In questo tipo di approccio i nodi sono autonomi e per questo è impossibile controllare i file che sono presenti all'interno di questa nuvola, in quanto variano con il tempo a seconda degli utenti connessi. Se con l'approccio client-server un numero maggiore di client portava al collasso del servizio, nel servizio fornito con approccio peer to peer, un numero maggiore di client, porta a un miglioramento del servizio stesso. L'idea del peer to peer nasce, come già detto, sfruttando l'idea che mediamente i client hanno molte più potenzialità di quelle sfruttate. Il problema principale di questo approccio è che molti client, essendo coperti da firewall o da NAT, non riescono a sfruttare appieno le doti delle reti peer to peer, in quanto non sono in grado di accettare connessioni dirette in ingresso o in uscita.

Vantaggi della rete Peer to Peer
L'idea di base è quella di "rubare" la banda, per creare lo storage della rete peer to peer.
Questo crea una rete molto scalabile, in cui le risorse crescono e si uniscono per formare un'unica entità; con il crescere dei peer, la qualità del servizio migliora.
La rete peer to peer è affidabile, in quanto si ha una ridondanza delle informazioni su più peer: in questo caso se il primo proprietario della risorsa non fosse più disponibile, si avrebbero molti altri peer che, dopo aver assimilato la risorsa, la mettono a disposizione. In più se arrivano nuovi peer è possibile sostituire servizi non più disponibili in modo affidabile.
Le reti peer to peer sono molto facili da amministrare in quanto non richiedono infrastrutture esterne, poichè si organizzano autonomamente.
Le reti più moderne assicurano la fault tolerance e bilanciano il carico fra i nodi in modo automatico.

Applicazioni Peer to Peer
Le reti peer to peer più diffuse sono quelle per il file sharing. A partire da Napster fino a bittorrent. Altri servizi offerti sono l'instant messaging e il voip (ad esempio Skype).
In più sono interessanti in ambito aziendale per creare applicazioni di calcolo distribuito (Desktop Grid, in cui si realizzano griglie di calcolo numerico).

Organizzazione delle reti peer to peer
Le reti peer to peer sono delle reti sulle reti, nel senso che sono reti logiche che funzionano a livello applicativo, che si "appoggiano" su un insieme di reti fisiche. Al loro interno i peer sono connessi direttamente da dei link virtuali (in quanto non importano i collegamenti fisici).
Nella rete internet esistono nodi fissi e mobili, in cui ogni nodo cambia indirizzo ogni volta che cambia posizione geografica. Col paradigma client-server, il server deve essere accessibile sempre allo stesso indirizzo, poichè tutti vanno in quel punto della rete a reperire le informazioni.
All'interno delle reti peer to peer non importa quale sia l'indirizzo dell'apparecchio, ma è necessario un ID univoco, che riconosce la postazione anche in posizioni fisiche diverse. L'insieme degli ID univoci crea l'overlay, che ha il compito di mascherare la rete fisica su cui la rete peer to peer lavora.

Operazioni del peer to peer
All'interno di una rete peer to peer esistono alcune funzioni di base, comuni a tutte le reti di questo genere:
-boot, fase di ingresso nell'overlay peer to peer. Nel momento in cui un nodo peer si connette deve conoscere gli indirizzi e gli ID di alcuni nodi fissi, con cui si è già stati connessi. Nel caso di nodi di bootstrap centralizzati  esistono dei server, che "suggeriscono" i nodi a cui andare a chiedere i servizi, i cui indirizzi cambiano nel tempo.
-lookup di risorse e servizi, in cui ogni nodo cerca i servizi che gli interessano. Siccome le risorse sono distribuite la fase di lookup è essenziale.
-utilizzo di risorse e servizi, fase con la quale, una volta trovato il servizio di interesse, il nodo inizia a sfruttarlo. Nello stesso momento anche altri nodi potrebbero usufruire dello stesso servizio.

Infrastrutture peer to peer
Esistono principalmente due approcci per gestire l'operazione di look-up e di boot:
-approccio centralizzato, con la quale l'operazione di look-up avviene per mezzo di un server, che conserva l'indice di tutti i servizi contenuti nella rete. In questo caso se il server non è disponibile, tutta la rete peer to peer non funziona. Questo significa che la fase di look up è gestita secondo il principio di client-server. Un esempio di tecnologia che sfrutta questa tecnologia è il Voip.
-approccio decentralizzato, in cui l'operazione di lookup è distribuita. Per accedere alle risorse è quindi necessario rivolgersi ad alcuni nodi, i quali hanno l'informazione. L'operazione di look-up è quindi più complessa in quanto la richiesta della risorsa avviene in modo distribuito, con un protocollo per il quale ogni nodo a cui è richiesta la risorsa, richiede a sua volta la risorsa finchè essa non viene trovata. Questo metodo in cui i vicini rimandano ad altri vicini è detto "non strutturato" (o gossip) e non assicura il ritrovamento della risorsa in un tempo stabilito. Nell'approccio strutturato, al contrario, i nodi si organizzano secondo una topologia precisa. In questo caso si conoscono gli ID dei nodi chiave e da loro si può costruire una mappa dell'overlay. Questo meccanismo si ottiene mediante una tabella di hash distribuita e un vero e proprio processo di routing, il quale permette di trovare le informazioni passando da un nodo all'altro.

Infrastrutture DHT
Le infrastrutture DHT sono presenti in reti peer to peer decentralizzate con approccio strutturato e sono in grado di rappresentare una tabella di hash distribuita. Questa tabella di hash contiene le informazioni riguardanti le macchine che possiedono un determinato servizio a cui viene assegnata una chiave. La tabella di hash è condivisa tra i nodi, i quali si organizzano in una struttura fissa in modo che ciascuno di essi ne contenga una piccola porzione.
Affinchè questa tabella funzioni correttamente e renda possibili le ricerche è necessario che esista un algoritmo che sia in grado di gestire la metrica delle chiavi. Questo algoritmo si basa sulle distanze tra le chiavi.
L'ID di ogni nodo non serve solo per riconoscere un nodo ma anche per localizzare le chiavi, in quanto grazie ad esse è possibile individuare gli indirizzi  a cui sono localizzati i diversi servizi. Il protocollo definisce il concetto di distanza tra due nodi: ogni nodo è considerato vicino se di esso si conoscono tutti i nodi collegati (servizi e indirizzi), un nodo è considerato intermedio se di esso si conosce solo l'indirizzo ed infine un nodo è considerato lontano se di esso non si conosce nulla (neanche l'indirizzo preciso). In questo modo è possibile mediante la richiesta di una chiave, che ha lo stesso formato degli ID nodi, stabilire la zona della rete in cui è memorizzato un determinato puntatore ad un servizio. In questo modo ad ogni richiesta di un servizio, verrà prodotta la sua chiave. Verranno cercati i nodi della rete con ID nodo più prossimi alla chiave e, una volta trovato l'indirizzo del servizio, verrà richiesto l'inizio del servizio stesso.
Secondo questo algoritmo ogni nodo deve gestire una serie di chiavi e una parte della tabella di routing. Con queste informazioni ogni nodo è in grado di dire quale dei nodi da esso conosciuti è più vicino al nodo che contiene la risorsa che si sta cercando.

Modellazione delle reti peer to peer
Per distribuire il carico fra i vari nodi le reti peer to peer vengono modellate in base a reti ad arco. Bisogna quindi definire:
-distanza tra due nodi, che è il numero di passi da fare per spostarsi dal nodo di partenza all'altro.
-eccentricità tra due nodi, che è il numero massimo di stadi necessari a connettere due nodi.
-degree di un nodo, che è il numero di archi che partono/arrivano ad un nodo (quanti nodi sanno della mia presenza sulla rete).
-grafo (orientato o non), con il quale si può modellare una rete peer to peer.
-clustering coefficient, che misura il rapporto fra il numero di archi e il numero di archi che sarebbe possibile connettere.

Napster
Napster è la prima rete peer to peer che possiamo considerare, in quanto ha dato origine al primo software peer to peer utilizzato a livello globale. Ha avuto numerosi problemi legali, a causa del fatto che era presente un server centrale, che indicizzava anche file protetti da copyright.
Per chiudere questa rete, infatti, è bastato chiudere il server centrale. Nel momento in cui un peer accedeva alla rete faceva l'upload della lista dei propri file aggiornati. Una volta connesso, un peer poteva fare richiesta di ottenere un file al server centrale (query), il quale rispondeva (answer) con la lista degli  indirizzi dal quale si poteva iniziare il download.

Gnutella e Skype
Gnutella è il primo client peer to peer che realizza un overlay non strutturato. Questa rete è nata nel 2000 e, a partire dal progetto iniziale, sono nati una serie di software open source che utilizzavano il codice Gnutella (Limewire e molti altri). In un primo momento questa rete considerava tutti i peer allo stesso modo e chiunque poteva mettere in condivisione informazioni sulla posizione delle risorse. I peer erano chiamati "servent", ma l'approccio non era scalare, in quanto per localizzare una risorsa era necessario chiedere ai nodi conosciuti per mezzo di flooding. All'interno della rete si creava un notevole traffico non controllabile.
Gnutella è diventata in un secondo momento una rete a due livelli di gerarchia: sono presenti, infatti, degli ultrapeer (nodi a banda larga accessibili a tutti), che realizzano l'indicizzazione vera e propria. Gli altri peer costituiscono dei nodi foglia, che sono fuori dall'overlay, ma che hanno la possibilità di condividere i file. I nodi foglia non contengono informazioni sull'indice, ma affidano agli ultrapeer il lavoro di indicizzazione. In base alle caratteristiche (banda, firewall…) un nodo foglia può essere promosso a ultrapeer.
Per la connessione tra peer e ultrapeer a livello di protocollo si realizza un threeway handshake, in cui ci sono degli header concatenati. I tre messaggi in questione sono una richiesta di "gnutella connect", un messaggio di "ack" da parte dell'ultrapeer, una lista dei file condivisi. I nodi foglia possono anche essere sotto NAT. In questo caso il nodo ultrapeer memorizzerà l'informazione relativa all'indirizzo privato e la porta usata per comunicare. In questo modo si ottiene un indirizzo pubblico, utilizzabile anche da altri peer che vogliono scaricare. Gli ultrapeer si connettono tra di loro mediante un meccanismo analogo alla connect degli altri nodi.
I nodi foglia, dopo un'ora di connessione, possono essere promossi ultrapeer. Questo delicato procedimento avviene mediante una richiesta da parte del peer (ultrapeer connect). Se le caratteristiche di banda sono soddisfatte esso viene promosso ad ultrapeer, altrimenti si dovrà attendere un'altra ora prima di effettuare una nuova richiesta. Questa politica di promozione viene accostata a una certa ridondanza delle connessioni. Infatti ogni peer si collega a tre ultrapeer contemporaneamente e gli ultrapeer si connettono con al massimo altri 32 ultrapeer. Ogni ultrapeer crea connessioni con 30 nodi foglia.
Skype è un'altra rete non strutturata gerarchica in cui gli ultrapeer si chiamano supernodi. I supernodi, oltre al lavoro di indicizzazione, hanno anche l'onere di supportare i nodi che hanno dei NAT. La procedura di connessione a una rete come Skype si articola in due passi fondamentali:
-overlay discovery, in cui ogni nuovo nodo deve trovare almeno un supernodo a cui collegarsi direttamente in modo da avere accesso all'indice.
-ricerca di nuovi nodi, in modo da infittire la maglia di connessioni, per aumentare il numero di peer con cui comunicare. Per ottenere questo elenco di nodi si manda un ping al supernodo, che risponde con un pong contente una lista di indirizzi IP e di porte conosciute (gossip).

Algoritmo di lookup di Gnutella
L'algoritmo di lookup utilizzato è il "dynamic quering", che ha come obiettivo quello di localizzare una risorsa con il numero minore di messaggi, contattando il numero minore di ultrapeer disponibili. Esso si basa sul concetto che alcune risorse sono più diffuse di altre. E' quindi possibile trovare le risorse più diffuse contattando un numero modesto di ultrapeer. Nel caso in cui questa ricerca non vada a buon fine si cerca di contattare un numero maggiore di ultrapeer, sempre però con l'obiettivo di non esagerare.
Per evitare il problema del sovraccarico questo meccanismo è implementato in tre fasi distinte:
-search our leaves, in cui si chiede alle altre foglie dei propri ultrapeer se si hanno le informazioni (TTL=0). Tutte le foglie che ricevono una richiesta di lookup devono rispondere entro 2,4s, nel caso non si trovi la risorsa si passa alla fase successiva
-probe query, in cui si manda una richiesta a tutti i propri ultrapeer (TTL=1). Ogni ultrapeer inoltra la query a tutte le proprie foglie. Se si ottengono 150 risposte positive l'algoritmo termina altrimenti si passa alla fase successiva. (in questo modo si limita il flooding)
-controlled broadcasting, in cui si usa il meccanismo di ricerca precedente con TTL>1, in cui quindi vengono contattati non solo i propri ultrapeer, ma anche i vicini… In questo modo anche se in un tempo abbastanza lungo si riescono a trovare le risorse. Normalmente si tende a non utilizzare TTL>3.
Il "query routing protocol" è un'ottimazione del protocollo precedente, che prevede semplicemente, che tutti gli ultrapeer contengano al loro interno la lista dei servizi delle foglie, in modo da non dover replicare la query ad ogni ricezione.

Progetto Chord
E' un progetto del MIT, che prevede di creare un protocollo peer to peer per la gestione di una tabella di hash completamente distribuita. In più vuole garantire il bilanciamento della rete. Mediante questa tabella le operazioni di lookup devono essere efficienti, in quanto si passa da un nodo all'altro in maniera ordinata, raggiungendo il proprio nodo di interesse in un numero limitato di passi (log(n), con n pari al numero di peer). Ogni nodo deve avere una routing table e una parte della tabella di hash, con relative chiavi. La routing table deve essere dinamica.
Il sistema Chord non è un protocollo peer to peer in senso stretto ma è solo un modo per accedere alla tabella di hash distribuita. Secondo questo meccanismo i nodi e le chiavi sono rappresentabili sullo stesso dominio. L'algoritmo di hashing utilizzato è "SHA1", gli ID dei nodi sono ottenuti per mezzo dell'indirizzo IP, mentre gli ID delle chiavi sono codici hash delle chiavi stesse.
L'algoritmo si basa su una "finger table", che funziona ad intervalli. Nel momento in cui è richiesta una risorsa ad un qualunque nodo, se questa non la possiede affida il link ad un nodo successivo con una precisione maggiore a seconda se si trova con un ID più o meno vicino a quello della chiave. In questo modo la ricerca va avanti con passi via a via più piccoli, fino ad arrivare alla risorsa.
Essendo una rete p2p i nodi possono entrare o uscire nella rete in qualunque momento. Questo continuo entrare e uscire potrebbe portare alla perdita dei next-hop e quindi al malfunzionamento della tabella di hash. Per risolvere questo problema ogni nodo deve conoscere in qualunque momento almeno l'id del successore, in modo da non perdere la linearità delle chiavi.
La join di un nodo avviene nel seguente modo:
-il nuovo nodo si crea la finger table, cercando il proprio successore e altri nodi.
-si verifica uno scambio di messaggi con altri nodi in modo da generare o aggiornare le altre finger table con il proprio nodo.
Nel momento della disconnessione si applica un sistema di graceful leave, nel senso che si trasferiscono le proprie chiavi al successore e i puntatori al nodo successivo vengono aggiornati.

Kademlia
Il progetto di Kademlia è un'evoluzione di Chord. In questo caso si tratta di una rete strutturata che sostituisce la topologia basata sulla distanza con una topologia ad albero. L'ID di un nodo è dato dalla sequenza dei bit dove si trova il nodo all'interno dell'albero binario. Anche in questo caso per ogni nodo è presente una finger table, ma in essa sono contenute le informazioni riguardanti una lista di nodi (k-bucket) a cui chiedere informazioni (il nodo e tutti quelli al di sopra di esso). Grazie a questa tecnica si ottiene la convergenza molto più velocemente che nel caso precedente, si ha quindi una fase di lookup molto più veloce.
Kademlia utilizza principalmente quattro tipi di messaggi:
-PING, per verificare se un nodo è attivo oppure no.
-STORE, per memorizzare la coppia chiave-valore relativa a un nodo.
-FIND_NODE, per cercare altri nodi. Il nodo che riceve questo tipo di messaggio invia una risposta nella quale sono contenute le informazioni relative ai k-nodi del proprio k-bucket più prossimo all'ID ricercato.
-FIND_VALUE, come nel caso precedente a meno che il ricevente non abbia la chiave richiesta. In questo caso invia il valore corrispondente della chiave.
Ogni coppia messaggio-risposta è identificato da un ID generato da chi effettua la richiesta, mediante un numero casuale.

Confronto tra CHORD e Kademlia
Entrambi i progetti implementano un meccanismo di routing table distribuita, anche se in CHORD essa è pericolosa, in quanto ha una sola entry come next hop. In Kademlia la tabella è molto più flessibile ed è munita di un algoritmo di lookup molto più evoluto: Kademlia è più robusto, in quanto ci sono ogni nodo possiede due o tre nodi come next hop.

Limitazioni delle DHT
Le DHT sono delle strutture molto complesse, perchè associano dei ruoli specifici a determinati nodi. Nonostante si abbiano ottime prestazioni nella fase di lookup esse hanno forti limitazioni:
-i client peer to peer hanno normalmente un tempo di connessione lungo, e quindi creano ritardi nelle ricerche.
-le reti peer to peer variano molto velocemente e le reti non riescono ad organizzarsi in tempo.
-per non perdere le chiavi delle risorse è necessaria una disconnessione da parte della maggior parte dei nodi di tipo graceless.
-le DHT non si prestano a delle ricerche non precise.

Bittorrent
La rete si basa su un nodo centrale, detto tracker, che è costituito da un server web e che fornisce il supporto per i download. Per condividere un file bisogna generare un torrent che non è altro che un metadata che descrive il file. Ci deve essere un tracker per quel file e bisogna creare una copia completa (seed) per permettere agli altri peer di scaricarlo.
L'obiettivo principale di bittorrent è quello di migliorare la velocità di download, garantendo la massima replicabilità delle risorse. I peer si dividono in due categorie:
-seed, che hanno una copia integrale del file.
-leechers, peers che non hanno ancora una copia integrale del file.
La procedura di connessione è semplice. A partire da un torrent si risale al tracker. Il peer si unisce al torrent, tramite il tracker, che indica l'indirizzo di almeno 50 peer che gestiscono il file. Il peer crea e mantiene delle connessioni aperte con almeno 20 peer. A questo punto si cerca di scaricare il file in parallelo, scaricando più pezzettini. Ciascun peer invia un report al tracker, inviando le informazioni di stato e se si sta per disconnettere.
Le tecniche di swarming servono a scaricare da più peer in parallelo. Questo obiettivo si ottiene dividendo il file in pezzi da 256Kb. Il download avviene per frammenti. Per garantire una corretta distribuzione dei vari frammenti, è necessario scaricare prima le parti meno condivise, in modo da aumentarne la loro diffusione.
Una nuova tecnica si chiama Bittorrent trackerless, che è un tentativo di sostituire il tracker con una DHT (quindi creare un tracker distribuito).