P2P (o quasi): Peer To Peer (o quasi) Gennaro Cordasco P2P (o quasi) Cosa vuol dire Peer to Peer (P2P)? • Sistema distribuito nel quale ogni nodo ha identiche capacità e responsabilità e tutte le comunicazioni sono potenzialmente simmetriche; • Peer to peer (obiettivi): condividere risorse e servizi (dove per risorse e servizi intendiamo: scambio di informazioni, cicli di CPU, spazio sul disco …); • Scalabilità: il lavoro richiesto a un determinato nodo nel sistema non deve crescere (o almeno cresce lentamente) in funzione del numero di nodi nel sistema; •Per migliorare la scalabilità sono nati i cosiddetti protocolli P2P di seconda generazione che supportano DHT (Distributed Hash Table); P2P (o quasi) DHT Routing • La scalabilità di un protocollo è direttamente legata all’efficienza dell’algoritmo usato per il routing; • In questo senso sostanzialmente gli obiettivi sono due: • Minimizzare il numero di messaggi necessari per fare lookup; • Minimizzare, per ogni nodo, le informazioni relative agli altri nodi; • I vari DHT conosciuti differiscono proprio nel routing; P2P (o quasi) DHT Routing: Lookup • Trovare l’indirizzo IP del nodo responsabile di una determinata chiave; • Obiettivi: • Minimizzare la dimensione dello spazio richiesto ai nodi per memorizzare le tabelle di routing; • Minimizzare il numero di hop necessari per il Lookup; • Fornire un servizio fidato anche con Peer inaffidabili; • Resistere ad attachi di tipo Denial of Service; P2P (o quasi) Ip address DHT: Routing(Sommario) • Esistono un bel po’ di soluzioni; (Ce ne sono altre!!!) • Le prestazioni sono più o meno uguali (in teoria); • La domanda da porsi però è “Il gioco vale la candela …”; P2P (o quasi) Hybrid – Centralized index, P2P file storage and transfer Super-peer – P2P(quasi): Classificazione A “pure” network of “hybrid” clusters Pure – functionality completely distributed P2P (o quasi): errata corrige Viceroy Network vs Butterfly • In una Viceroy Network a r dimensioni due nodi u=<w,i > e v=<w’,i+1> sono connessi se: • w = w’; (archi diretti non mostrati); • w’ = (w+2r-i)mod 2r. • In una butterfly a r dimensioni due nodi u=<w,i > e v=<w’,i+1> sono connessi se: • w = w’; (archi diretti non mostrati); • w e w’ differiscono esattamente nell’i-esimo bit. P2P: un’applicazione Gennaro Cordasco P2P: un’applicazione Tanto per intenderci…(1) • Le applicazioni P2P sono costituite da tre fasi principali: • boot; (nessuno o quasi fa boot P2P) • lookup; (pochi sono P2P, alcuni usano SuperPeer) • scambio di file; (sono tutti P2P) P2P: un’applicazione Tanto per intenderci…(2) • Parleremo di applicazioni: • P2P pure se: • le fasi di boot, lookup e scambio di file sono P2P;(forse Overnet?) • P2P se: • le fasi di lookup e scambio di file sono P2P; • la fase di boot utilizza qualche SERVER; (Gnutella, Freenet) • P2P Ibride se: • la fase di scambio dei file è P2P; • la fase di boot utilizza qualche SERVER; • nella fase di lookup vengono usati Peer particolari: Hub (Direct Connect) SuperPeer , Ultra Peer(Gnutella2) Supernodo (KaZaA) NodoRandezVous (JXTA) MainPeer (EDonkey) Server (WinMX) P2P: un’applicazione Sommario • Gnutella: un po’ di informazioni; • Gnutella: vantaggi e svantaggi; • Gnutella2; • Overnet !!!P2P PURO!!! P2P: un’applicazione Gnutella(1) • 14 / 03 / 2003 Justin Frankel e Tom Pepper realizzano la prima release di Gnutella (!!! Solo 14 ore !!! ); • La taglia della rete cresce in 7 mesi da 2K a 48K nodi; • Tuttavia nel 95% delle query il diametro è di 7-8 hop; • Le applicazioni più conosciute che si basano sul protocollo Gnutella sono: • BearShare; • LimeWire; •… P2P: un’applicazione Gnutella • Gnutella è un protocollo P2P; • La lista degli host presenti nella rete è disponibile sul server gnutellahost.com; • Il Server gnutellahost.com(127.186.112.097) viene usato dai nodi per il boot: • Single point of failure; • Gnutella non è P2P Puro!!!; • La Ricerca di un file usa il flooding (non è scalabile): • controllo dei cicli; • TTL per evitare di congestionare la rete; P2P: un’applicazione Il protocollo Gnutella (v0.4) • PING – Notifica a un Peer la propria esistenza; Boot • PONG – Reply to a PING (contiene alcune informazioni sulla rete); • QUERY – Cerca un file nella rete (Sulla base di una determinata chiave); Lookup • RESPONSE(QUERY HIT) – Risposta a una query (contiene la locazione del file); • GET – Permette di richiedere un file; • PUSHREQUEST – Permette di scavalcare i firewall; Scambio P2P: un’applicazione Gnutella Search Example GET X.mp3 X X C A B A’s query (e.g., X) C’s query hit E’s query hit D E X P2P: un’applicazione Gnutella: Flooding P2P: un’applicazione Gnutella2: Concetti • New Protocol; • A new data trasport architecture; • New base services, including search: Gnutella Addressing System (GAS); • An implementation standard; P2P: un’applicazione Gnutella2: meglio un uovo oggi…. • L’obbiettivo della lookup in Gnutella è trovare tutti i peer che dispongono di un determinato oggetto (non ci sono limitazioni sul tempo); • L’obbiettivo della lookup in Gnutella2 è trovare, nel minor tempo possibile, almeno un peer (se c’è) che dispone di un determinato oggetto; una volta trovata un’istanza dell’oggetto desiderato è possibile scegliere se fermarsi o continuare la ricerca; • L’abilità di trovare almeno un’istanza di un oggetto è molto importante, altrimenti non sono possibili altre azioni; • Bisogna trovare un modo per tenere sotto controllo la ricerca; P2P: un’applicazione Gnutella2: Ricerca…(1) • Esistono tre approcci per controllare la ricerca; • Random walker approach;(il nodo che origina la query ne controlla l’esecuzione e in ogni istante può decidere se continuare o abortire la ricerca). Gnutella2 • Random or crawling mesh approach;(il nodo che origina la query iterativamente contatta alcuni nodi della rete, finché non si verifica una determinata condizione). Future • Guided mesh approach;(DHT) P2P: un’applicazione Gnutella2: Ricerca…(2) • Su una rete pubblica di grandi dimensioni non è possibile effettuare direttamente la ricerca di un oggetto: • ci sono troppi nodi da contattare; • il costo per mettersi in contatto con un nodo è troppo alto paragonato alla probabilità di successo su quel nodo; • la maggior parte dei nodi non dispongono di risorse sufficienti per far fronte a un numero notevole query; • non tutti i nodi si possono contattare direttamente (es. firewall); P2P: un’applicazione Gnutella2: Ricerca…(3) Nodo Hub • Soluzione? P2P Ibrido: • Gnutella2 organizza i nodi in un sistema gerarchico a due livelli dove i nodi ad alta capacità chiamati Hub rispondono alle query per le proprie foglie; • La restizione della rete agli Hub è P2P; • Hub vantaggi: • Viene ridotto il numero totale dei nodi da contattare; • Un Hub contiene informazioni relative a tanti oggetti, quindi è maggiore la probabilità che una query trovi un’istanza di un oggetto; • E’ possibile avere informazioni su nodi down; P2P: un’applicazione Gnutella2: Ricerca…(4) • Per evitare che questo sistema degeneri in un sistema centralizzato viene limitato il numero di leaves per ogni hub;(circa 150) • La comunicazione fra leaves e hub è diretta; • Problema Inter-Hub Communication; P2P: un’applicazione Gnutella2: Inter-Hub Communication(1) Nodo Hub • Ogni hub conosce solo i propri vicini; • Quando un hub riceve una query dal nodo di origine, oltre a elaborarla, la inoltra ai propri vicini che non la inoltrano ulteriormente; (in pratica TTL = 2) • Ad esempio se la ricerca viene inviata ad un hub che ha 5 vicini in un solo passo (con una query) vengono analizzate le foglie relative a 6 hub; • L’insieme dei nodi raggiunto in un passo viene chiamato cluster; P2P: un’applicazione Gnutella2: Inter-Hub Communication(2) Nodo Hub • Quando un nodo richiede la ricerca di un oggetto al proprio hub: • Viene ricercato l’elemento nel proprio cluster; • Viene ricercato l’elemento nei cluster vicini(a distanza 1) più qualche cluster lontano scelto a caso; • Viene ricercato l’elemento nei cluster vicini dei vicini (a distanza 2) più qualche cluster lontano scelto a caso; •… P2P: un’applicazione Gnutella2: Inter-Hub Communication(3) Nodo Hub • Non è possibile per ogni hub mantenere la lista di tutti gli hub; (Non è scalabile); • La lista dei cluster a distanza i+1 è ottenuta in risposta alla ricerca effettuata sui cluster a distanza i; • Le risposte contengono inoltre altre informazioni utili per le statistiche (es. numero di nodi presenti nel cluster); P2P: un’applicazione Gnutella2: Inter-Hub Communication(4) Nodo Hub • Ogni hub mantiene la lista degli hub vicini (direttamente connessi) più una cache di hub lontani aggiornata di tanto in tanto; • Viene mantenuta una done list; • Le ricerche all’interno del cluster sono fatte usando TCP; • Le ricerche fra cluster sono fatte usando UDP; UDP SEARCH TCP SEARCH P2P: un’applicazione Gnutella2: Inter-Hub Communication(Esempio) try list cluster P2P: un’applicazione Gnutella2: Inter-Hub Communication(5) Nodo Hub • Ogni hub deve mantenere quindi: • la lista dei propri vicini; • una lista di hub lontani(da aggiornare di tanto in tanto); • una done list (i nodi a cui abbiamo inviato una query più i loro vicini); • una try list; (i vicini dei vicini dei nodi a cui abbiamo inviato una query); per ogni query Gnutella2: Boot • Come fa un nuovo nodo a connettersi alla rete? • E’ necessario conoscere almeno un host attivo; • Chi mantiene la lista degli host attivi? • un Server; (Gnutella) • tanti Server; (Gnutella2) • Idee!!! Overnet • Sistema P2P per il file sharing sviluppato dalla MetaMachine; • Non ci sono server; (P2P puro) • Usano DHT(Distribuited Hash Table) con ID a 128 bit; • Purtroppo non è Open Source; Overnet:boot • Ogni nodo mantiene una cache dei nodi connessi alla rete; • Durante la fase di boot il nodo tenta di connettersi ai nodi presenti nella cache; • Se questa fase non ha successo viene richiesto l’indirizzo di un nodo on-line;(A regime non capita praticamente mai) • In ogni caso è stato creato un canale IRC per mantenere queste informazioni; Risorse • www.gnutella.com • www.gnutella2.com • www.shareaza.com • www.overnet.com • www.openp2p.com