BraconeGiuseppe Progettazione,ImplementazioneeValutazionediunSistemaP2PperVolunteer-Computing IngegneriaInformatica Universit`adegliStudidiRoma“LaSapienza”Facolt`adiIngegneria

Testo completo

(1)` degli Studi di Roma “La Sapienza” Universita ` di Ingegneria Facolta Tesi di Laurea in. Ingegneria Informatica Ottobre, 2012. Progettazione, Implementazione e Valutazione di un Sistema P2P per Volunteer-Computing. Bracone Giuseppe.

(2)

(3) ` degli Studi di Roma “La Sapienza” Universita ` di Ingegneria Facolta Tesi di Laurea in Ingegneria Informatica Sessione Autunnale – Ottobre, 2012. Progettazione, Implementazione e Valutazione di un Sistema P2P per Volunteer-Computing. Bracone Giuseppe. Relatore. Prof. Leonardo Querzoni .............................. Revisore. Prof. Camil Demetrescu ..............................

(4) Indirizzo dell’Autore: Bracone Giuseppe c/da ramitelli, 6 Campomarino (CB) 86042 ITALIA e-mail: [email protected] www:.

(5) Ringraziamenti Riflettendo sull’esigenza o meno di scrivere queste righe, sono stato sommerso da una marea di ricordi legati all’esperienza universitaria che mi appresto a concludere. Ricordi legati a personone che, nel bene e nel male, hanno contribuito a plasmare la mia personalit` a e ad arricchire quel bagaglio di esperienze che mi vanto di possedere. Proseguire con l’elenco di tali persone sarebbe dispendioso e inutile, rischiando peraltro di saltarne qualcuna, mi limito quindi a dei ringraziamenti generici con la certezza che chiunque li legger` a saprà quanti e quali gli sono stati dedicati. Il primo ringraziamento speciale và a coloro che mi hanno fornito gli strumenti per poter iniziare questo lavoro di tesi, accompagnandomi e inocraggiandomi durante il lungo periodo di gestazione necessario per esssere completato. Un ringraziamento di cuore è diretto verso chi mi ha instillato il senso del dovere e mi ha insegnato ad essere umile e al contempo caparbio per affrontare qualsiasi sfida e a coloro che mi hanno saputo tirar fuori la grinta e la tenacia necessarie a superare qualsiasi ostacolo che mi separava dal traguardo. Ringrazio coloro che mi hanno dato la possibilità di poter iniziare e portare fino in fondo questo percorso di studio, le persone che hanno condiviso anche una piccola parte di questo percorso dai quali ho imparato l’importanza della collaborazione e della condivisione e chi mi è stato vicino alla fine alleviando quell’ansia passeggera che accompagna ogni attesa di un evento importante e significativo. L’ultimo ringraziamento è diretto a tutte le persone che sostengono l’università, quell’ambiente dinamico ed eterogeneo in cui ogni giorno ho avuto la possibilità di allargare i miei orizzonti conoscitivi e di incontrare persone di idee e costumi differenti che hanno rafforzato la mia identità culturale e mi hanno insegnato il rispetto verso la diversit` a.. i.

(6) ii. CAPITOLO 0.

(7) Indice Ringraziamenti. i. 1 Introduzione L’evoluzione dei sistemi per la computazione Computing al Volunteer-Computing 1.1 I sistemi distribuiti . . . . . . . . . . . . . . . . 1.2 La tecnologia Grid . . . . . . . . . . . . . . . . 1.3 L’avvento del Cloud-Computing . . . . . . . . . 1.4 Le potenzialit` a del Volunteer-Computing . . . . 1.4.1 XtremWeb . . . . . . . . . . . . . . . . 1.4.2 Cohesion . . . . . . . . . . . . . . . . . 1.4.3 Alchemi . . . . . . . . . . . . . . . . . . 1.4.4 OurGrid . . . . . . . . . . . . . . . . . . 1.5 Il nostro contributo . . . . . . . . . . . . . . . .. distribuita: dal Grid. . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. . . . . . . . . .. 1 1 3 9 12 13 14 14 15 16. 2 Tecnologie P2P per la Computazione Distribuita 17 2.1 La ricerca di risorse in un ambiente dinamico . . . . . . . . . . . . . . . 19 2.2 Allocare risorse senza controllo centralizzato . . . . . . . . . . . . . . . . 22 2.3 La rilevazione dei guasti . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Progettazione e Implementazione del sistema Cloud-to-Peer 3.1 Modello Fisico . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Modello Architetturale . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 User Interface . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Local Cache . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Local Resource Monitor . . . . . . . . . . . . . . . . . . 3.2.4 Remote Resource Catalog . . . . . . . . . . . . . . . . . 3.2.5 Virtual Tree . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.6 Message Handler . . . . . . . . . . . . . . . . . . . . . . 3.2.7 Job Tracker . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.8 Slicing Service . . . . . . . . . . . . . . . . . . . . . . . 3.2.9 Job Manager . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Protocolli e Interazioni tra Moduli . . . . . . . . . . . . . . . . iii. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . .. 27 27 28 28 30 31 31 32 34 35 36 36 37.

(8) iv. INDICE 3.3.1 3.3.2 3.3.3 3.3.4. Sottomissione di Job . . . . . . . . . . . . . . . . Esecuzione/Interruzione/Completamento del job Sostituzione dei nodi guasti . . . . . . . . . . . . Aggiornamento del Remote Resource Catalog . .. 4 Test e Risultati 4.1 Ambienti di test . . . . . . . . 4.2 Benchmarks . . . . . . . . . . . 4.2.1 WordCount . . . . . . . 4.2.2 StringSort . . . . . . . . 4.2.3 SHA-BruteForceAttack 4.3 Consumi energetici . . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. . . . .. 37 38 41 42. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . .. 47 47 48 49 51 52 54. 5 Conclusioni 61 5.1 Sviluppi futuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Scenari di utilizzo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.

(9) Capitolo 1. Introduzione L’evoluzione dei sistemi per la computazione distribuita: dal Grid-Computing al Volunteer-Computing 1.1. I sistemi distribuiti. I sistemi distribuiti nascono dall’esigenza di avere infrastrutture in grado si supportare l’esecuzione di task eseguibili in parallelo per l’analisi e la manipolazione di dati[8]. L’utilit` a dei sistemi distribuiti si riscontra nei campi: • Scientifico: la scienza moderna è basata su simulazioni numeriche, analisi di enormi quantit` a di dati prodotti in real-time da sofisticati strumenti e collaborazione su larga scala, problemi chiave afferenti ai pi` u svariati campi scientifici e ingegneristici necessitano di un’ infrastruttura in grado di fornire computazioni su larga scala, ovvero in grado di estendere il potere computazionali offerto da una singola macchina; • Industriale:ambienti di simulazione sempre pi` u dettagliati richiedono notevoli tempi computazionali; • Aziendale-Controllo:la quantità di informazioni sempre pi` u dettagliate sui clienti e sui cittadini richiedono computazioni data-intensive che necessitano del supporto di infrastrutture adeguate. La nascita e l’espansione dei sistemi distribuiti è stata resa possibile dal progresso ed evoluzione delle tecnologie hardware e software, nel seguito sono descritte le fasi 1.

(10) 2. CAPITOLO 1. fondamentali del percorso evolutivo di ognuno. L’evoluzione dell’hardware può essere riassunto nelle seguenti ere[31]: 1. Era dei mainframe e super-computer, rappresenta gli albori dei dispositivi di calcolo automatico e sono caratterizzati da macchine aventi notevoli dimensioni e altissimi consumi energetici; 2. Era dei minicomputer, nasce tramite la ricerca e l’applicazione di tecniche di miniaturizzazione che permettono di avere dispositivi di calcolo di dimensioni considerevolmente inferiori rispetto ai predecessori; 3. Era dei personal computer, il processo di miniaturizzazione è accompagnato dalla ricerca di tecniche per la riduzione del consumo energetico e dall’abbattimento dei costi di produzione che portano alla diffusione di massa dei dispositivi di calcolo elettronico; 4. Era dei mobile device, alimentata da tecniche sempre pi` u efficienti ed efficaci per ridurre i consumi energetici e le dimensioni dell’hardware e dal potenziamento della rete di comunicazione, l’obiettivo è ottenere dispositivi di calcolo multifunzionali interconnessi tra loro le cui funzionalità siano disponibili in qualsiasi luogo e in ogni momento. Il percorso evolutivo del software prosegue parallelamente a quello dell’hardware, sia per adattarsi alle innovazioni che esso offre, sia per segnare la strada verso cui lo sviluppo dell’hardware stesso deve essere indirizzato, possiamo distinguere le fasi: •. Batch-oriented, le applicazioni sono di tipo batch, l’interattività è limitata, le applicazioni sono specializzate per eseguire determinati task risultando poco parametrizzabili e con notevoli richieste di risorse di calcolo;. • Client-Server, le applicazioni sfruttano le risorse di rete per eseguire task su risorse computazionali remote, le tecniche per la parallelizzazione dei task e le tecniche di scheduling permettono al server di agire come risorsa condivisa in grado di soddisfare le richieste provenienti da un gran numero di clients geograficamente distribuiti; • SOA e Web-Application, le applicazioni permettono di coordinare un maggior numero di risorse e di aumentarne il grado di condivisione tra pi` u utenti, si assiste alla proliferazione di nuovi modelli per il calcolo distribuito e nascono i concetti di QoS e di SLA, l’obiettivo principale delle applicazioni è soddisfare un insieme di richieste sempre pi` u eterogeneo e articolato concentrandosi su come il comportamento di tali applicazioni vengono percepite dall’utente. Una prima classificazione dei sistemi paralleli può essere effettuate sulla base del grado di disaccoppiamento e di condivisione delle risorse che vengono coordinate per eseguire uno specifico task, si hanno dunque[27]:.

(11) 1.2. LA TECNOLOGIA GRID. 3. • Array di processori, sono caratterizzati da stretto accoppiamento, co-locazione fisica e condivisione del sistema di clock. • Sistemi multi-processore, sono caratterizzati dall’accesso diretto alla memoria condivisa secondo il modello UMA(UnifiedMemoryAccess). Esempi di tali sistemi sono le reti: Omega,Butterfly,Clos,Shuffle exchange. • Sistemi multi-computer, sono caratterizzati dalla mancanza di accesso diretto alla memoria condivisa secondo il modello NUMA(NotUnifiedMemoryAccess)Esempi di tali sistemi sono: NYU Ultracomputer, CM* Connection Machine, IBM Blue gene. Altre classificazioni possono essere effettuate sulla base di altre caratteristiche dei sistemi distribuiti, tra cui: • Capacit` a di coordinare un insieme di macchine per supportare l’esecuzione di specifici task; • Livello di concorrenza offerto, ovvero impatto dei tempi delle operazioni di sincronizzazione sul tempo totale di esecuzione dei task; • Quantit` a e tipo di risorse condivise; • Modalit` a di accesso alle risorse remote; • Valutazione del rapporto performances/costo; • Misura dell’affidabilit` a, intesa come l’insieme di disponibilità, integrità, tolleranza ai guasti; • Scalabilit` a; • Modularit` a.. 1.2. La tecnologia Grid. Nel seguito verr` a analizzata una classe importante di sistemi distribuiti, tale classe racchiude tutti i sistemi paralleli di tipo multi-computer che permettono di eseguire computazioni garantendo alti livelli di performances. Tali sistemi possono essere suddivisi in 2 sottogruppi: 1. Cluster computing[26], sono composti da collezioni di workstation o PC, chiamati nodi, aventi configurazioni simili connessi da reti LAN che garantiscono comunicazioni ad alta velocit` a. Su ogni nodo è in esecuzione il medesimo sistema operativo..

(12) 4. CAPITOLO 1 2. Grid computing[22], anch’essi sono composti da nodi che però vengono organizzati in sottogruppi chiamati federazioni. I domini amministrativi che gestiscono i nodi possono essere differenti cos`ı come può essere differente l’hardware e il software che compongono ogni nodo e la rete di comunicazione che li interconnette.. La popolarit` a dei sistemi di cluster computing crebbe di pari passo con il miglioramento del rapporto prezzo/performances dei PC e delle workstations. Tale fattore permise di rendere tecnicamente possibile ed economicamente attraente costruire sistemi di supercomputing semplicemente interconnettendo tra loro una collezione di computer in una rete ad alta velocit` a. In tal modo il cluster computing permette di eseguire calcolo parallelo in cui un singolo programma gira su macchine multiple. Esempi di cluster computing sono Beowulf e MOSIX. In Beowulf[28] ogni cluster è composto da collezioni di nodi computazionali che sono controllati e acceduti da un unico nodo master che gestisce l’allocazione dei nodi ad un particolare programma eseguibile in parallelo, mantiene una coda di jobs da eseguire al termine dell’esecuzione del programma corrente, ovvero nel cluster gira un programma per volta e richieste per l’esecuzione di altri jobs vengono accodate, e fornisce un interfaccia per l’utente del sistema. Quindi il master si occupa della gestione del cluster, i nodi eseguono la computazione dei job fornendo semplicemente un sistema operativo standard Linux-based. Il middleware di Beowulf fornisce solo funzionalit` a avanzate di comunicazione message-based, ma non è in grado di gestire i guasti dei processi e di garantire la sicurezza del sistema. I sistemi MOSIX[6] forniscono un cluster computing simmetrico che si oppone all’approccio gerarchico seguito da Beowulf. L’obiettivo di MOSIX è fornire una singola immagine del sistema in modo tale che l’intero cluster appaia come un singolo computer. Tale funzionalit` a e fornita mediante la caratteristica di trasparenza ovvero la possibilità per un processo di migrare dinamicamente tra i nodi che compongono il cluster. La funzionalit` a di migrazione dei processi permette ad un utente di iniziare una applicazione su di un nodo e successivamente spostarla su altri nodi, per ottenere ad esempio un utilizzo pi` u efficiente delle risorse del cluster o per ovviare a possibili guasti, senza interromperne l’esecuzione. La caratteristica principale del cluster computing è l’omogeneità dei nodi di computazione, essi hanno il medesimo sistema operativo e sono connessi alla medesima rete. I sistemi di grid computing sono invece caratterizzati da un alto grado di eterogeneità, ovvero per l’intero insieme di nodi computazionali non vi sono assunzioni sull’hardware, sul sistema operativo, sulla rete, sui domini amministrativi o sulle politiche di sicurezza. Lo scopo dei sistemi di grid computing è permettere che organizzazioni differenti siano in grado di collaborare, tale collaborazione è realizzata secondo la forma della organizzazione virtuale[22]. I providers e i consumatori di risorse definiscono le condizioni sotto le quali interagiscono, ovvero: • cosa è condiviso; • chi pu` o condividere e accedere alle risorse condivise;.

(13) 1.2. LA TECNOLOGIA GRID. 5. Figura 1.1: Schema organizzativo delle grid • quale qualit` a di servizio pu` o essere garantita. L’organizzazione virtuale è l’insieme di individui e istituzioni che interagiscono secondo le medesime condizioni. Le risorse sono tipicamente costituite da servers, funzionalità di storage e databases, inoltre pu` o essere fornito l’utilizzo di speciali dispositivi come telescopi, sensori,...etc. Mentre la ricerca sulla computazione distribuita è finalizzata a risolvere i problemi dovuti alla separazione geografica delle risorse, la ricerca sui grid ha come obiettivo primario quello di risolvere problemi di integrazione e di gestione di software eterogeneo. Una definizione pi` u formale di grid è la seguente: sistema che coordina risorse geograficamente distribuite utilizzando protocolli e interfacce standard ed è in grado di fornire adeguati livelli di QoS. Quindi si ha che il grid è costituito da protocolli e interfacce che risolvono problemi fondamentali quali autenticazione, autorizzazione, resource discovery e accesso alle risorse. Tali protocolli devono essere standardizzati e aperti per permettere che sistemi differenti possano interagire e integrarsi. Inoltre il grid permette l’utilizzo delle risorse in modo coordinato per poter offrire differenti livelli di QoS definiti in basa a metriche quali: tempo di risposta, throughput, disponibilità e sicurezza, gestendo l’allocazione di tipi di risorse multiple per soddisfare richieste pi` u complesse, in tal modo l’utilit` a del sistema complessivo è significativamente maggiore rispetto a quella della somma delle sue parti. L’ infrastruttura grid deve fornire supporto ad applicazioni che possono essere classificate ini: 1. Applicazioni di monitoraggio e gestione di risorse remote, rappresentate per lo pi` u da fonti di dati permanenti, quali dispositivi di storage, o temporanei, come i sensori. 2. Applicazioni con requisiti minimi di comunicazione , sono anche chiamate embarrassingly parallel-applications e consistono nel dividere un problema in sotto-.

(14) 6. CAPITOLO 1 problemi che possono essere risolti in modo indipendente l’uno dall’altro o tuttalpi` u con modesti overhead per lo scambio di messaggi; 3. Applicazioni con requisiti di linking, includono applicazioni che operano secondo uno scenario in cui l’input è fornito da uno strumento situato al sito A, i dati che lo compongono vengono analizzati nel sito B, il risultato dell’analisi viene visualizzato nel sito C. Tali applicazioni richiedono la coordinazione di risorse eterogenee e geograficamente distribuite come computers, archivi per lo storage, strumenti di visualizzazione e strumenti per la produzione di dati. Le problematiche da risolvere per implementare tecnologia grid riguardano: • Monitoraggio delle risorse, comprende i meccanismi utilizzati per conservare informazioni sullo stato delle risorse nel grid.Tali meccanismi devono essere estendibili, veloci, affidabili, sicuri e scalabili, inoltre occorre implementare tecniche per associare ad ogni risorsa un identificativo univoco. • Ricerca delle risorse, dato l’identificativo di una risorsa o le sue caratteristiche, occorre un meccanismo per localizzare la risorsa dentro il sistema. La natura delle risorse è dinamica, alcune risorse possono essere persistenti, alcune transitorie e altre possono essere create on demand. • Sincronizzazione e coordinazione, riguarda le tecniche adoperate per orchestrare una complessa sequenza di operazioni su una varietà di risorse, ciò può includere la descrizione dei processi, l’implementazione di un sistema event-based, scheduling multilivello e meccanismi per la gestione di workflow. • Tolleranza ai guasti e dependability, riguarda la necessità di gestire il guasto di componenti hardware e/o software garantendo che i livelli di QoS non vengano degradati. • Sicurezza, comprende l’autenticazione, l’autorizzazione e i meccanismi di accounting. • Concorrenza e consistenza, riguarda la necessità di mantenere un appropriato livello di consistenza dei dati in un ambiente dinamico ed eterogeneo e che le informazioni di stato sulle singole risorse rispecchino lo stato reale delle risorse stesse. • Prestazioni, riguarda principalmente l’utilizzo di tecniche di caching e di replicazione per ridurre il tempo di accesso a risorse remote. • Eterogeneit` a, per permettere di utilizzare una moltitudine di risorse di natura differente appartenenti a differenti domini amministrativi. • Scalabilit` a, ovvero necessit` a di espandere il numero di servizi e la dimensione delle applicazioni utilizzando tecniche di automazione e auto-organizzazione..

(15) 1.2. LA TECNOLOGIA GRID. 7. La prima rudimentale grid in grado di rispettarne le caratteristiche e offrire le funzionalit` a sopracitate f` u NFSNET. NFSNET[18] creata nel 1986 con una backbone avente larghezza di banda di 56Kb/sec collegava insieme i 5 centri di supercomputer dell’NFS. I successivi investimenti a tale infrastrutture mirarono ad incrementare la larghezza di banda della backbone, passando a 1,5Mb/sec e infine a 45Mb/sec agli inizi del 1990. Nel 2002 NFS ha fondato TeraGrid che collega i 5 centri di supercomputer con una rete a fibra ottica avente capacità di 40Gb/sec, parallelamente è stato sviluppato il programma Extensible Terascale Facility con l’obiettivo di espandere l’infrastruttura di TeraGrid ad altre istituzioni di ricerca, ovvero per integrare TeraGrid con altri sistemi grid. A NFSNET sono seguiti numerosi altri progetti per dotare diversi paesi di una propria infrastruttura grid[18]: • StatiUniti: NSF Grid Physics Network, DOE Science Grid, NSF International Virtual Data Grid Laboratory; • Europa: EU DataGrid, EUROGRID; • Progetti grid a livello nazionale: e-Science Grid(UK), INFN Grid(Italia), LHC Computing Grid(Svizzera). Al finire degli anni 90 il progetto open-source GlobusToolkit definisce quello che oramai è uno standard de-facto per le infrastrutture grid[22]. Le specifiche che il GlobusToolkit implementa fanno parte dell’OpenGridServicesArchitecture e vengono ampiamente adottate all’interno di realt` a industriali e di ricerca fornendo la base per prodotti grid sia commerciali che open-source. OGSA si occupa soprattutto della definizione di servizi basilari che la grid deve offrire e riguardano: • Sistemi di gestione e di automazione; • Gestione dei workload e delle performances; • Sicurezza; • Sistemi per garantire la disponibilità; • Gestione delle risorse logiche; • Servizi di clustering; • Gestione della connettivit` a; • Gestione delle risorse fisiche. OGSA propone inoltre un’architettura a strati[22] per la gestione delle grid composta principalmente dai seguenti elementi:.

(16) CAPITOLO 1. Increased functionality, standardization. 8. Managed shared virtual systems. Computer science research. Web services, et cetera. Open Grid Services Arch Real standards Multiple implementations. Internet standards. Custom solutions 1990. Globus Toolkit De facto standard Single implementation. 1995. 2000. 2005. Figura 1.2: Fasi di standardizzazione della tecnologia Grid 1. Fabric layer, fornisce le risorse il cui accesso è mediato dai protocolli definiti all’interno della grid. Tali risorse possono essere risorse computazionali, sistemi di storage, catalogs, risorse di rete e sensori.Ogni risorsa dovrebbe implementare meccanismi di introspezione che permettano di scoprire la propria struttura, il proprio stato e la propria capacità, e meccanismi per la gestione della risorsa stessa per poter controllare la qualità del servizio che essa offre. 2. Connectivity layer, definisce le basi della comunicazione e i protocolli necessari per permettere la cooperazione tra le risorse. I protocolli di comunicazione permettono li scambio di dati tra le risorse del fabric layer, i servizi che essi includono riguardano trasporto, routing e indirizzamento. I protocolli di autenticazione vengono costruiti sui servizi di comunicazione e forniscono meccanismi crittograficamente sicuri per verificare l’identità delle risorse e degli utenti. 3. Resource layer, definisce i protocolli per la negoziazione, iniziazione, monitoraggio, controllo e accounting per le operazioni che utilizzano le risorse del grid. Lo scopo è quello di fornire l’interazione tra l’utente e le risorse remote del sistema. 4. Collective layer, contiene i protocolli che non sono associati a specifiche risorse, ma a collezioni di risorse fornendo indicazioni sullo stato globale del sistema e sull’interazione tra collezioni di risorse differenti. 5. User application, comprende le applicazioni che operano all’interno della virtual organization e utilizzano le API e i servizi forniti dagli altri strati, come: gestione delle risorse, accesso ai dati, resource discovery,... ..

(17) 1.3. L’AVVENTO DEL CLOUD-COMPUTING. Tools and applications Directory brokering, diagnostics, and monitoring Secure access to resources and services Diverse resources such as computers, storage media, networks, and sensors. 9. User applications. Collective services. Resource and connectivity protocols. Fabric. Figura 1.3: Architettura a strati proposta dall’OGSA. 1.3. L’avvento del Cloud-Computing. La virtualizzazione e l’accesso on-demand sono gli strumenti con cui la tecnologia grid evolve verso un nuovo tipo di infrastruttura le cui caratteristiche sono ubiquità e trasparenza. Il grid computing è il precursore di un paradigma di computazione pi` u generale chiamato cloud computing. I fattori che hanno permesso il passo evolutivo sono: tecniche di virtualizzazione, miglioramento dei sistemi di comunicazione, sistemi per il monitoraggio delle risorse, tecniche di migrazione delle macchine virtuali, bilanciatori di carico.. Figura 1.4: Cloud-Providers A differenza della tecnologia grid, il cloud-computing[15] è ancora in fase di svi-.

(18) 10. CAPITOLO 1. luppo e non esistono standards condivisi, tuttavia sono presenti numerosi providers che utilizzano il termine servizio-cloud per catturare il concetto di utility-computing. L’utility-computing è un paradigma di computazione secondo cui i servizi rappresentati da capacità computazionali sono offerti a seconda delle necessità degli utenti secondo lo schema gi` a largamente adottato per la fornitura di acqua, elettricità, gas e telefonia, ovvero gli utenti non hanno pi` u l’esigenza di mantenere le proprie risorse computazionali o investire nell’acquisto di nuove e non sono vincolati a specifici computing-service providers, le richieste di utilizzo di capacità computazionali vengono soddisfatte ondemand da uno dei cloud provider, pagando solo le risorse che utilizzano per il solo tempo in cui vengono utilizzate.. Figura 1.5: Fase attuale della tecnologia cloud In termini di infrastruttura, una cloud è un insieme di applicazioni internet-based, di servizi di storage e di computazione sufficienti a supportare la maggior parte dei bisogni degli utenti e a disincentivare l’utilizzo di risorse locali. In termini di servizio offerto, il cloud-computing è semplicemente una tecnologia che permette di allocare risorse di storage e risorse computazionali on-demand. Il cloud-computing offre una combinazione di funzionalità che includono:.

(19) 1.3. L’AVVENTO DEL CLOUD-COMPUTING. 11. • Una infrastruttura dinamica e scalabile; • Accesso universale, ovvero accesso da un qualsiasi punto della rete internet; • Utilizzo, controllo e pagamento di risorse a vari livelli di granularità; • Piattaforme standardizzate; • Gestione di servizi di supporto; L’obiettivo primario della tecnologia cloud-computing è il disaccoppiamento dei servers fisici dalle applicazioni. Nel cloud un utente alloca il numero e il tipo di macchine virtuali necessarie ad eseguire un task senza avere la necessità di sapere dove tali macchine sono fisicamente localizzate. Le macchine virtuali eseguono un task finchè richiesto e vengono spente quando il task è completato. Il disaccoppiamento è implementato anche a livello di risorsa allocabile permettendo all’utente di avere un controllo a granularit` a fine sulle risorse offerte dal cloud, ad esempio i dati generati da un task in esecuzione su una specifica macchina virtuale potrebbero essere utilizzati da task che verranno eseguiti su macchine virtuali differenti create in momenti successivi rispetto al tempo di spegnimento della macchina virtuale in cui i dati risiedevano, l’utilizzo di risorse di storage offerte dal cloud permette ad ogni server del cloud di accedere a tali dati, rispettando adeguati meccanismi di accesso controllato. Nel cloud, i server fisici sono risorse condivise,mentre le macchine virtuali sono risorse utilizzabili esclusivamente dall’utente che le ha create, il numero di macchine virtuali in esecuzione su un insieme di server può variare nel tempo. Il cloud-provider mette a disposizione un insieme di server fisici pronti a rispondere a specifiche richieste per supportare servizi di allocazione, spostamento e spegnimento di macchine virtuali. Ogni macchina virtuale pu` o essere dedicata a task differenti. L’allocazione e la deallocazione rapida di macchine virtuali associato a tecniche di scheduling e di bilanciamento del carico, permette al cloud-provider di riuscire a soddisfare le richieste degli utenti e ad ottenere un utilizzo efficiente delle risorse fisiche. Le macchine virtuali allocate mediante i servizi on-demand possono essere utilizzate per espletare vari task: • Esecuzione di workflows; • Soddisfare i picchi di domanda per la computazione; • Pianificare e attuare strategie di disaster recovery; • Eseguire applicazioni distribuite. Modelli differenti di cloud richiedono o supportano differenti livelli di informazioni di configurazione da parte dell’utente, ovvero l’utente può configurare le risorse di cui richiede l’allocazione in modi differenti e dettagliati, ad esempio un utente potrebbe specificare:.

(20) 12. CAPITOLO 1 • Il numero di server che verranno utilizzati per l’esecuzione di uno specifico task; • Il numero di server e il ruolo che ognuno di tali server assumerà, ovvero potrebbe specificare i server che fungeranno da web-server e quelli che assumeranno invece il ruolo di application-server. • Una specifica immagine di macchina virtuale da eseguire su ognuna delle macchine richieste.. All’utente è concessa anche la possibilità di selezionare i livelli si servizio che pi` u si adattano alle proprie esigenze. Gli attributi dei servizi cloud percepiti dall’utente sono[32]: • On-demand self-service, ovvero capacità di allocare, utilizzare e gestire risorse computazionali, di storage e applicazioni senza dover richiedere l’intervento dello staff IT di supporto; • Ubiquit` a dell’accesso, ovvero la possibilità di accedere alle risorse cloud da qualsiasi punto di accesso della rete internet; • Scalabilit` a elastica, gli utenti possono decidere quanta risorsa utilizzare in ogni momento, l’allocazione è effettuata a seconda della domanda corrente evitando un over-provisioning di capacit` a delle risorse per gestire i picchi di domanda; • Pagamento flessibile, il modello utilizzato per pagare i servizi cloud si basa sul “pay-as-you-go”, ovvero ogni utente paga solamente le risorse che effettivamente sta utilizzando in ogni dato momento.. 1.4. Le potenzialit` a del Volunteer-Computing. Con volunteer computing si intende la tecnologia con la quale è possibile sfruttare le risorse sottoutilizzate di macchine connesse alla rete internet per poter offrire servizi equivalenti a quelli forniti dal cloud. I fattori che alimentano la ricerca nel campo del volunteer computing sono: • Possibilit` a di ottenere hardware a basso costo; • Progressiva diffusione della banda larga per la connessione ad internet; • Maggior sensibilit` a verso le tecnologie green; • Possibilit` a di avere enorme potere computazionale a costo 0. Il primo progetto che dimostr` o le potenzialità del volunteer computing f` u SETI@HOME[14] che offrendo la possibilit` a di collezionare potere computazionale dai cicli CPU in stato idle dei desktop-pc ha permesso di risolvere problemi compute-intensive in modo.

(21) ` DEL VOLUNTEER-COMPUTING 1.4. LE POTENZIALITA. 13. pi` u efficiente rispetto al pi` u veloce supercomputer esistente. Da SETI@HOME è nato il sistema BOINC[13], capostipite di una serie di altri sistemi (Condor, Entropia e GridSat) in grado di fornire tecniche efficienti per l’individuazione e l’allocazione di risorse computazionali sottoutilizzate. Essi operano principalmente in reti stabili, ovvero reti con basso dinamismo in cui i nodi sono omogenei e sicuri, e sfruttano un architettura centralizzata che se da un lato permette di avere maggior controllo sul sistema e di garantire un certo livello di performance, dall’altro limita la scalabilità ed espone il sistema ai classici problemi delle architetture centralizzate: presenza di un single-point-of-failure, vulnerabilità ad attacchi di tipo Denial-of-Service e possibilità che il nodo master diventi un collo di bottiglia per le performance globali del sistema. Quindi anche se i sistemi sopracitati ottengono significativi risultati all’interno di reti piccole e controllate, essi non si adattano ad ambienti come internet in cui è possibile sfruttare una quantit` a enorme di risorse che però risultano estremamente eterogenee e inaffidabili. Da tali osservazioni sono nati progetti per l’implementazione di sistemi di volunteercomputing che limitano l’utilizzo di strutture centralizzate, nelle prossime sezioni sono analizzati alcuni di tali sistemi.. 1.4.1. XtremWeb. In XtremWeb[17] i nodi sono funzionalmente suddivisi in 3 categorie: 1. Clients, sono i nodi che possono richiedere al sistema l’esecuzione dei job. 2. Workers,comprende i nodi che eseguono la computazione distribuita. 3. Cooordinators, è formata dai nodi che gestiscono le richieste dei clients e monitorano l’attivit` a dei workers. A differenza di sistemi come Boinc o Condor, i nodi godono di maggiore autonomia, ma servizi come indicizzazione e gestione delle risorse restano centralizzati. XtremeWeb permette l’esecuzione di un gran numero di job caratterizzati da bassa correlazione tra task paralleli, come ad esempio BoT (Batch of Task) o MPI (Message Passing Interface). La comunicazione tra i nodi è gestita dal protocollo RPC(Remote Procedure Call). Le procedure di scheduling delle risorse sono espletate dai nodi coordinatori. La sicurezza è garantita a vari livelli: • Per la gestione dei task vengono utilizzati sistemi di protezione della privacy dei dati e verifica dei risultati. • Per lai gestione delle risorse vengono utilizzate tecniche di sandboxing per proteggere il sistema da codice malevolo. Infine sono utilizzate tecniche di replicazione e checkpointing per garantire tolleranza ai guasti..

(22) 14. CAPITOLO 1. 1. 0. 7. XtremWeb Root Server. Personal Devices. ISP Server. Workers LAN. 6. 2. Personal Devices. Collaborators LAN. 3. 5. Legend 4. Results Collector. Application dedicated. Private LAN. Worker. Workers Transactions. XtremWeb Server. Servers Transactions. Figura 1.6: XtremWeb. 1.4.2. Cohesion. Cohesion[37] utilizza JXTA per mantenere una rete P2P non strutturata e altamente configurabile, ottenendo adattivit` a ad ambienti distribuiti caratterizzati da instabilità e volatilità. Cohesion adotta una architettura a micro-kernel in cui sono incluse solo funzionalit` a minime, in tal modo garantisce un controllo a granularità fine delle risorse e mitiga la complessita dello scheduling. Cohesion risulta inoltre flessibile per gestire vari modelli di esecuzione parallela fornendo strumenti per la decomposizione dinamica dei job. Il bilanciamento del carico viene effettuato mediante migrazione dei task e le informazioni sulle risorse sono aggregate mediante una struttura ad albero. La sicurezza è ottenuta mediante tecniche di sandboxing e di trust-management per attribuire un valore di reputazione agli host. Il fallimento dell’esecuzione dei task viene tollerato mediante la replicazione dei task stessi.. 1.4.3. Alchemi. Alchem[4]i permette l’aggregazione di Windows PC-Desktop in stato idle per l’esecuzione di applicazioni resource-intensive. La comunicazione e la sicurezza sono gestite dal framework .NET. L’architettura adoperata è di tipo gerarchico. Le richieste di esecuzione dei job sono gestite dal nodo manager che provvede a schedularle ai nodi secondo un modello FCFS. Alchemi non offre alcuna soluzione per i problemi di gestione dei guasti e ripristino delle funzionalità..

(23) ` DEL VOLUNTEER-COMPUTING 1.4. LE POTENZIALITA. 15. Applications. Virtualization. Discovery. Communication. Fault Tolerance. Task Pool Failure Detection. Group Membership. Composable Channels. Endpoint Management. Substrate (XMPP, JXTA) Host System Integration. Application Container. Sensing Framework. Management & Security. Task Model. Termination Detection. OSGi Platform Core. Programming Models Load Balancing. Desktop Integration. Java Virtual Machine (JVM) Solaris. Windows. Linux. Others. Figura 1.7: Cohesion. Figura 1.8: Alchemi. 1.4.4. OurGrid. OurGrid[2] è un middleware open-source che ha lo scopo di permettere la collaborazione tra differenti comunit` a di ricerca. Tutti gli utenti sono suddivisi in gruppi, gli utenti all’interno del medesimo gruppo interagiscono direttamente tra loro mediante un clientbroker chiamato MyGrid. Il fenomeno del free-riding, ovvero la possibilità che utenti fungano esclusivamente da consumatori di risorse senza condividere le proprie, è gestito mediante un insieme di metodi chiamato Network of Favors. La protezione dei dati locali è garantita da una tecnica di isolamento basata sulla macchina virtuale Xen..

(24) 16. CAPITOLO 1. Figura 1.9: OurGrid. 1.5. Il nostro contributo. L’obiettivo del lavoro che verr` a presentato nel seguito è quello di definire un’architettura di un sistema completamente decentralizzato che sia in grado di offrire le medesime funzionalit` a del volunteer-computing. A tal scopo saranno analizzate le tecniche disponibili per poter implementare, secondo un approccio di tipo P2P, le funzionalità base del sistema: • Ricerca delle risorse; • Allocazione delle risorse; • Gestione del churn. Verrà infine sviluppato un prototipo per testare l’efficacia delle tecniche descritte e per fornire una valutazione in termini di prestazione e utilità del sistema e per individuare possibili utilizzi e migliorie da apportare..

(25) Capitolo 2. Tecnologie P2P per la Computazione Distribuita Le caratteristiche dei sistemi per il P2P computing sono: • Mancanza di relazioni di tipo client-server; • Comunicazione simmetrica; • Tempi di vita dei peers impredicibili; • Diretto scambio di informazioni tra i peers. Il P2P computing permette di: • Migliorare la scalabilit` a evitando la dipendenza da punti di controllo centralizzati; • Eliminare il bisogno di costose infrastrutture permettendo la comunicazione diretta tra peers; • Facilitare l’aggregazione di risorse. La maggiore scalabilit` a ottenuta dalla decentralizzazione del sistema di controllo della computazione risulta per` o limitato da fattori quali la quantità di operazioni che devono essere eseguite con un approccio centralizzato (come ad esempio le operazioni di sincronizzazione e coordinazione), la quantità sulle informazioni sullo stato della computazione che devono essere conservate, il grado di parallelismo delle applicazioni. Il requisito basilare del p2p computing è quello di poter suddividere una computazione complessa in unit` a di computazione di minore complessità chiamati task e di poterli assegnare a differenti peers affinchè vengano processati in parallelo. Il processo di suddividere un programma in task è chiamato decomposizione. Il processo di decomposizione pu` o dar luogo a task indipendenti, ovvero un insieme di task che può essere eseguito in qualsiasi sequenza, o task dipendenti, ovvero insieme di task che per essere 17.

(26) 18. CAPITOLO 2. completati devono attendere la ricezione dei dati prodotti dal completamento di altri task. Il numero e la dimensione dei tasks in cui un problema è decomposto determinano la granularit` a della decomposizione, il processo di decomposizione si dice a granularità fine se genera un gran numero di task, a granularità grossolana altrimenti. Pi` u la granularità è fine maggiore sar` a il livello di concorrenza della computazione e migliore sarà la distribuzione tra i nodi, d’altro canto la possibile condivisione di dati di input, di output e intermedi implica un numero maggiore di interazione tra i task che su reti con alta latenza potrebbero comportare un notevole overhead che verrebbe ridotto utilizzando processi di decomposizione pi` u grossolani. I paradigmi di computazione possono essere classificati in base al programma assegnato ad ogni task . . . : • Programma Singolo, tutti i task eseguono il medesimo programma, i dati utilizzati come input sono differenti per ogni task; • Programma Multiplo, i task eseguono programmi differenti utilizzando come input il medesimo insieme di dati oppure insiemi di dati differenti. . . . e dal modo in cui i task interagiscono tra loro: • Data partitioning, ogni task lavora su una porzione di un insieme di dati. I nodi hanno accesso alla medesima memoria condivisa, oppure ricevono i dati da una sorgente dati esterna al nodo. Solitamente si preferisce l’approccio code-to-data, ovvero utilizzare come nodi computazionali i nodi che già conservano i dati da elaborare. I task sono indipendenti e il risultato della computazione è conservato anch’esso in una porzione di memoria condivisa. • Message Passing, ogni task comunica con gli altri tramite invio e ricezione di messaggi, tali messaggi contengono informazioni necessarie al task per essere completato. I nodi non condividono porzioni di memoria, ma cooperano utilizzando la rete di comunicazione. • Ibrido, fonde alcuni aspetti dei paradigmi precedenti per poter eseguire task pi` u complessi. La classe di applicazioni descritta è detta classe di applicazioni parallelizzabili ed è per lo pi` u costituita da applicazioni compute-intensive. Altri tipi di applicazioni p2p sono: • Applicazione per la gestione dei dati, sono focalizzate sulla conservazione e il recupero di dati da vari peers che compongono la rete. Il modello di maggior successo di tali applicazioni è quello basato sullo scambio, come Napster e Gnutella, in cui ad ogni peer è consentito la ricerca e il download di dati resi disponibili dagli altri peers. • Applicazioni collaborative, permettono agli utenti di collaborare in tempo reale per collezionare e trasmettere informazioni. A tale classe appartengono i sistemi di Instant Messaging come AOL, Skype e Jabber..

(27) 2.1. LA RICERCA DI RISORSE IN UN AMBIENTE DINAMICO. 2.1. 19. La ricerca di risorse in un ambiente dinamico. Con ricerca delle risorse si intende l’insieme delle operazioni finalizzate alla ricerca e individuazione di risorse del sistema che rispettino determinate caratteristiche. Il metodo per la ricerca delle risorse adatto al sistema in analisi deve: • Utilizzare un approccio totalmente decentralizzato; • Essere scalabile; • Supportare vari tipi di query; • Essere robusto nei confronti del dinamismo della rete. Per implementare un algoritmo adatto a risolvere il problema della ricerca occorre: • Definire il concetto di risorsa; • Descrivere come indicizzare e/o caratterizzare le risorse; • Descrivere il formalismo utilizzato per esprimere le query e le tecniche per sottometterle al sistema; • Descrivere il protocollo con cui il sistema processa la query, comprendendo protocolli di routing e condizioni di matching. Nel sistema in analisi, la ricerca è indirizzata verso le risorse di tipo computazionali, ovvero l’insieme della configurazioni hardware che permettono ad un nodo di ricevere, processare e inviare un insieme di dati secondo uno schema computazionale non noto a priori. In genere tali risorse possono essere caratterizzate da 2 tipi di attributi classificabili come: • Statici, il cui valore non varia nel tempo, come tipo di sistema operativo, larghezza di banda, locazione nella rete, dimensione della memoria RAM, architettura e frequenza di clock della CPU e capacità di storage. • Dinamici, il cui valore pu` o subire importanti variazioni al trascorrere del tempo, come utilizzazione della CPU, utilizzazione della memoria RAM, spazio di storage disponibile, utilizzazione della larghezza di banda. La query è lo strumento con cui un nodo descrive e richiede le risorse che desidera, possono essere rappresentante mediante una combinazione di valori o intervalli di valori degli attributi delle risorse e possono essere classificate in: • Esatte: specificano i desiderati valori per tutti gli attributi delle risorse. Esempio: Architettura=x64 and CPU- Speed=1.8 Ghz and RAM=512MB and Spazio libero di memoria secondaria=300 GB and larghezza di banda=10 GB/s and OS=linux..

(28) 20. CAPITOLO 2 • Parziali : sono specificati i valori di solo un sottoinsieme degli attributi. Esempio: Architettura=Macintosh and RAM=1024MB. • Vincolanti: sono specificati gli intervalli dei valori per alcuni o tutti gli attributi. Esempio 1.8 Ghz < CPU-Speed < 3 GHz and 128MB < RAM < 1024 MB. • Booleane: sono specificate le condizioni booleane che gli attributi devono soddisfare. Esempio: RAM > 512 MB or Spazio libero di memoria secondaria>4GB.. Il processo della ricerca delle risorse è strettamente correlato alla tecnica di indicizzazione delle risorse, cioè possibilit` a di individuare in modo univoco le risorse all’interno del sistema, e dalla raggiungibilit` a delle risorse, ovvero la possibilità per ogni nodo di interagire con ogni altro nodo della rete che possiede le risorse richieste. Le risorse sono strettamente correlate ai nodi della rete, ogni nodo mette a disposizione le proprie risorse ed ogni risorsa è associata ad un solo nodo, all’interno della rete l’identificativo che permette di individuare ogni nodo è l’indirizzo di rete. Una volta formulata, la query deve essere sottoposta al sistema, in una rete P2P in assenza di entit` a centrali che coordinino tale processo, la sottomissione di query equivale all’applicazione di un protocollo di routing. Questo processo è inevitabile poiché non è possibile conservare all’interno di ogni singolo nodo le informazioni che possano descrivere l’intero insieme delle risorse della rete. I metodi per il forwarding delle query, ovvero per la scelta dei nodi a cui inviare la query, può essere di tipo deterministico, se è basato su una conoscenza a priori della rete, o probabilistico, se il routing è casuale o si basa su un certo tipo di probabilità. Le DHT sono la tecnologia dominante per il resource discovery in reti P2P di tipo strutturato, vengono utilizzate in sistemi come Chord, Pastry e Tapestry, e sono in grado di fornire servizi di query routing mediante O(log N) messaggi e l’aggiornamento della rete mediante O(log2 N) messaggi. I nodi sono organizzati secondo una topologia ad anello, ogni nodo mantiene una piccola finger table che è utilizzata per reindirizzare le query agli altri nodi finchè raggiungono il nodo corretto, ovvero il nodo che indicizza le risorse aventi determinati attributi. La DHT fornisce un metodo veloce e sicuro per il routing delle richieste, ma pu` o non rappresentare la soluzione migliore. Infatti la DHT possiede lo svantaggio di poter garantire il routing efficiente di query 1-dimensionali, ovvero query che esprimono vincoli su uno solo degli attributi delle risorse. Tecniche per poter estendere la capacit` a delle DHT per supportare query d-dimensionali prevedono l’utilizzo di: • Curve Space filling, come ad esempio la curva di Hilbert[9] o la curva-Z[19]; • Strutture dati basate sugli alberi, come i Quad-Tree[16] o gli R-Tree[5]; • Hashing tramite SHA[40]; Questi se da un lato risolvono il problema della limitazione delle risorse ricercabili, dall’altro inducono un overhead maggiore perdendo l’upper bound logaritmico che le DHT originarie erano in grado di fornire..

(29) 2.1. LA RICERCA DI RISORSE IN UN AMBIENTE DINAMICO. 21. Per le reti non strutturate il routing delle query è invece effettuato tramite la tecnica del flooding. Il flooding è utilizzato con successo in reti come Gnutella e FreeNet, in cui permette di supportare la ricerca di file in un ambiente distribuito e altamente dinamico, ma presenta alcuni svantaggi. Tali svantaggi riguardano l’impredicibilità dei tempi necessari a completare il processamento della query e la possibilità che la query non produca risultati poiché la risorsa desiderata si trova su di un nodo posto al di fuori dell’orizzonte della query, ovvero non appartiene all’insieme dei nodi raggiunti dalla query. Quella basata sul flooding è una tecnica di ricerca definita di tipo cieco, i nodi non hanno alcun tipo di conoscenza a priori sulla rete, esempi di utilizzo di tale tecnica sono: • BFS(Breadth First Search)[29], utilizza il flooding delle query tramite broadcast e associa ad ogni query un Time-To-Live per limitare la profondità della ricerca. Tale tecnica utilizza un enorme quantità di traffico dati non necessario e nella scalabilit` a limitata al valore del Time-To-Live, le risorse al di fuori dell’orizzonte della query non vengono mai scoperte; • RBFS(RandomBreadthFirstSearch)[20], la scelta del numero di nodi a cui inviare la query è casuale. In tal modo è possibile ovviare al problema del traffico eccessivo di messaggi generato dal BFS, ma la probabilità che la query non raggiunga i nodi che possiedono le risorse desiderate è maggiore. • Ricerca Iterativa in Profondit` a [11], consiste nell’eseguire pi` u BFS con diversi valori del Time-To-Live. Questo metodo permette di avere maggiore scalabilità rispetto al BFS, ma risulta lento e ogni nodo può dover processare un gran numero di repliche della medesima query. • Random Walks[25], il numero di nodi a cui la query è inviata è limitata ad un numero scelto in modo casuale, tale numero è diverso per ogni nodo che reinvia la query ricevuta, la terminazione è assicurata dall’utilizzo del Time-To-Live. Il vantaggio principale di questa tecnica è quello di avere un bilanciamento del carico locale ad ogni nodo per il processamento di query, ma le performances dell’algoritmo sono variabili e dipendono dalla scelta del numero casuale effettuata da ogni nodo. • Flooding con k Random Walks Indipendenti [34], effettua dapprima un BFS che ha l’obiettivo di scoprire k nuovi nodi, dopodichè vengono eseguite k random walks a partire dai k nodi scoperti.Combina i vantaggi del flooding e del random walks, ma l’overhead per lo scambio dei messaggi nella rete è molto alto. Nella ricerca informata i peers mantengono informazioni di routing per il forwarding delle query. Tali informazioni sono basate su parametri che possono indirizzare la query verso nodi in grado di fornire le risorse richieste. Le tecniche basate sulla ricerca.

(30) 22. CAPITOLO 2. informata hanno performances migliori rispetto alle tecniche di ricerca cieca, ma richiedono che ogni nodo conservi e aggiorni un insieme di indici. Un elenco di algoritmi che implementano tale tecnica è costituito dai seguenti: • DFBS(DirectedBreadthFirstSearch)[41], ogni nodo invia la query a un sottoinsieme dei suoi nodi vicini, la scelta di tali nodi si basa su informazioni ottenute da precedenti BFS e comprendono il numero di risultati che sono stati ottenuti da ogni nodo e la latenza con cui la query è stata processata. L’obiettivo è quello di ridurre i tempi di risposta delle query, migliorare la probabilità di trovare la risorsa desiderata, migliorare la scalabilità di BFS. Gli svantaggi di questa tecnica sono rappresentati dall’elevato numero di informazioni che ogni peer deve conservare e dalla mancanza di flessibilità nei confronti del churn-rate. • Ricerca Probabilistica Adattiva[10], la ricerca è basata su k probabilistic walks., in cui ogni nodo invia la query al vicino con probabilità data dall’indice di tale vicino. L’indice di ogni nodo è calcolata in base al risultato di ogni walk, l’indice è incrementato se la query è soddisfatta, mentre è decrementato se la query non trova alcun matching.Tale tecnica possiede buona robustezza rispetto ai cambiamenti nella topologia della rete, ma può presentare forti sbilanciamento di carico, le query sono indirizzate verso i primi peers scoperti dall’algoritmo trascurando gli altri vicini che potrebbero fornire risultati simili. • GIA[42], ogni nodo invia la query al vicino avente maggior capacità, l’invio di ogni query è preceduta da un protocollo di handshake in cui il nodo ricevente informa il nodo mittente del proprio carico di lavoro per il processamento delle query. Tale tecnica offre un efficiente metodi per il bilanciamento del carico, ma induce overhead di comunicazione tra i nodi ed esclude dal routing delle query i nodi che hanno minor capacit` a ma maggior probabilità di poter trovare la risorsa richiesta. • Ricerca Adattiva Basata sulla Popolarit` a [30], invece di basarsi sulle caratteristiche dei nodi, tale protocollo utilizza una stima della popolarità di ogni risorsa richiesta per scegliere i paramentri con cui inizializzare le random walks. Gli svantaggi di tale algoritmo sono la mancanza di meccanismi per il bilancimento del carico di ogni nodo e la necessit` a di dover conservare un gran numero di informazioni risultando poso scalabile rispetto al numero di risorse differenti che risiedono nel sistema.. 2.2. Allocare risorse senza controllo centralizzato. In questa sezione si analizzano le tecniche esistenti per l’allocazione, o scheduling, delle risorse, ovvero la possibilit` a che un utente possa richiedere l’utilizzo esclusivo per un certo periodo di tempo di risorse condivise per l’esecuzione di job..

(31) 2.2. ALLOCARE RISORSE SENZA CONTROLLO CENTRALIZZATO. 23. Durante l’allocazione delle risorse, i consumatori e i fornitori di risorse possiedono differenti funzioni obiettivo: • La funzione obiettivo del consumatore è centrate sulle applicazioni,poichè il suo scopo è quello di ottimizzare le performances di ogni job. Le performances di un job riguardano il makespan, ovvero il tempo che intercorre tra l’inizio dell’esecuzione del primo task alla fine dell’ultimo task di cui il job è composto, e, nel caso dell’introduzione di un modello economico per l’utilizzo delle risorse, del costo necessario per completare l’esecuzione. • La funzione obiettivo del fornitore è centrate sulle risorse, il suo fine è quello di ottimizzare le performances delle risorse. In tal caso con il termine performances ci si riferisce al throughput, ovvero capacità di una risorsa di processare un certo numero di jobs in un dato intervallo di tempo, e utilizzazione, definita come percentuale di tempo in cui la risorsa è occupata. L’incentivo alla condivisione delle risorse pu` o essere ottenuto mediante l’introduzione di un modello economico basato sulle metriche sopracitate. L’entit` a che stabilisce quali e a quale utente le risorse possono essere allocate viene chiamata scheduler. Il processo di allocazione deve essere completamente decentralizzato e deve fornire la garanzia che le richieste di allocazione vengano soddisfatte entro un certo intervallo di tempo. Gli strumenti adottati dallo scheduler sono la scoperta dei peers che compongono la rete, la stima dello stato di ogni peer e la disseminazione all’interno della rete di informazioni sulle proprie attività. Una prima classificazione delle tecniche di allocazione può essere effettuata tra schedulers statici e schedulers dinamici. Negli schedulers statici[21] ogni task che compone il job viene assegnato una volta sola alle risorse. La stima del costo dell’esecuzione di un task su un determinato nodo viene effettuata prima dell’inizio dell’esecuzione.Possono essere utilizzate euristiche per stimare il tempo di completamento dei task su un determinato nodo e l’affidabilità, ovvero la probabilit` a che la risorsa allocata non si guasti, o lasci il sistema, prima di terminare il task. Tale approccio richiede una conoscenza della rete globale per poter allocare le risorse migliori disponibili, maggiore è la quantità di informazioni conservate da ogni nodo, migliore è la scelta delle risorse da allocare. Negli schedulers di tipo dinamico[23], ogni task può essere assegnato pi` u volte a nodi differenti, l’allocazione iniziale può essere modificata eseguendo una migrazione del task da un nodo ad un altro, ciò permette di evitare la stima iniziale del tempo di completamento dei task. Tale approccio consente di tener maggiormente in considerazione la natura dinamica della rete, consentendo il rescheduling dei task quando risorse migliori sono rese disponibili o per ottenere un miglior bilanciamento del carico. La scelta del nodo dove migrare il task può basarsi sulle seguenti tecniche: • Opportunistica, viene selezionato il nodo con il minor numero di task accodati. E’ l’approccio pi` u semplice per effettuare il bilanciamento del carico che però non risulter` a quello ottimale..

(32) 24. CAPITOLO 2 • Bilanciata, la migrazione dei task accodati viene effettuata in modo periodico per ottenere il medesimo numero di task allocati su tutti i nodi. Con tale tecnica si ottiene un bilanciamento di carico migliore rispetto al primo, ma richiede un considerevole traffico dati per lo scambio di informazioni sullo stato della coda di ogni nodo. Tale traffico pu` o essere minimizzato limitando il bilanciamento solo al vicinato del nodo considerato. • Vincolata dal costo, oltre allo spostamento periodico dei task accodati viene eseguita una stima del tempo di esecuzione sul nuovo nodo, se il costo di migrazione del task è maggiore rispetto al tempo di esecuzione stimato, allora il task non viene spostato. L’efficienza di tale tecnica è tanto maggiore quanto maggiori sono gli overheads di comunicazione della rete con cui sono connessi i nodi.. Un’altra classificazione degli schedulers è basata sul concetto di cooperazione. Negli scheduling di tipo cooperativo[7], ogni scheduler agisce in accordo con gli altri per raggiungere un obiettivo comune, ovvero massimizzare il throughput globale del sistema. Nel caso di scheduling non-cooperativo[35], ogni scheduler agisce in modo autonomo per ottimizzare la propria funzione obiettivo, agendo quindi in modo egoistico senza curarsi dell’effetto delle proprie decisioni sul resto del sistema. Altri tipi di scheduling sono stati sviluppati mediante l’utilizzo di tecniche differenti da quelle tradizionali citate finora. L’utilizzo di tali tecbiche è giustificata da caratteristiche del sistema come autonomia dei nodi,modelli di interazione tra di essi e cambiamenti dinamici dello stato delle risorse. Tra gli approcci di scheduling non tradizionali vi sono quelli basati su: • Modello di asta[43], in cui ogni scheduler a seconda della propria disponibilità economica, propone un offerta per allocare una determinata risorsa. Lo scheduler che effettua la migliore offerta si aggiudica l’allocazione della risorsa, il nodo proprietario di tale risorsa ottiene un guadagno con cui effettuare a sua volta offerte per future operazioni di allocazione di risorse remote. • Equilibrio di Nash[24], in cui ogni task è modellato come un giocatore e le possibili strategie sono i nodi su cui pu` o essere eseguito. • Algoritmi genetici [24], in cui le possibili soluzioni sono l’assegnazione dei task a specifici nodi, il valore di fitness è il makespan dei mapping task-nodo e il cross-over è lo scambio dell’assegnazione dei task tra due nodi differenti. • Simulated annealing[3], in cui l’equilibrio termico è rappresentato dall’assegnazione ottimale tra task e nodi, la temperatura è il tempo totale di completamento dei task secondo l’attuale allocazione, il cambio di temperatura è il processo di modifica del mapping task-nodo. • Ricerca Tabu[1], in cui l’allocazione iniziale viene modificata mediante la ricerca di un nodo la cui allocazione riduce il makespan del job. La ricerca termina.

(33) 2.3. LA RILEVAZIONE DEI GUASTI. 25. quando la riduzione del makespan ottenuta dall’ultimo cambiamento è inferiore rispetto ad una data soglia.. 2.3. La rilevazione dei guasti. La scalabilit` a delle reti P2P permette di avere sistemi formati da un numero di nodi considerevole, se da un lato ci` o permette di poter usufruire di maggior risorse, dall’altro espone il sistema ad una maggior probabilità che al suo interno si verfiichino guasti, che possono essere: • Guasto fisico del nodo; • Guasto del link di comunicazione che connette il nodo alla rete; • Disconnessione del nodo dalla rete. Le tecniche utilizzate per individuare tali guasti in un ambiente decentralizzato si basano sull’utilizzo del gossip in cui ogni nodo mantiene una tabella locale, ogni entry di tale tabella è associata ad un nodo che conosce, in ogni entry è contenuto un contatore chiamato heartbeat, durante l’esecuzione del protocollo di rilevamento dei guasti si ha che: 1. Ogni nodo sceglie un gruppo di altri nodi; 2. Ad ogni nodo scelto viene inviata la tabella locale in cui il nodo mittente ha incrementato il proprio heartbeat; 3. Quando un nodo riceve una tabella, la fonde con la tabella locale adottando per ogni entry comune l’heartbeat maggiore; 4. Se dopo un certo intervallo di tempo un nodo rileva che un dato heartbeat non è stato incrementato, allora il nodo a cui è associato tale heartbeat viene sospettato di guasto; 5. Per ogni nodo sospettato di guasto viene eseguito un protocollo di consenso per mantenere le informazioni coerenti su tutti i nodi. Un sistema per il rilevamento di nodi guasti si basa su 3 parametri: • Tempo di gossip, è l’intervallo di tempo che intercorre tra l’invio di due messaggi di gossip consecutivi; • Timeout, è il tempo massimo dopo il quale un nodo viene sospettato di guasto; • Tempo per il consenso, è l’intervallo di tempo necessario per raggiungere il consenso sul guasto di un dato nodo..

(34) 26. CAPITOLO 2. La difficolt` a maggiore per l’implementazione di un rilevatore di guasti è la scelta del timeout, utilizzare valori troppo piccoli può generare falsi positivi causando un notevole aumento del traffico di rete per completare il protocollo di consenso, mentre valori troppo grandi causano un ritardo nella procedura di identificazione dei nodi guasti che potrebbero compromettere le funzionalità del sistema. Alcune variazioni sono state proposte con l’intento di migliorare il protocollo precedentemente descritto, tra queste: • Invio dei messaggi in Round-Robin, ha lo scopo di minimizzare e rendere pià uniforme il traffico dei messaggi. Ad ogni round di esecuzione dell’algoritmo, ogni nodo riceve ed invia un solo messaggio, la scelta del nodo d a cui inviare il messaggio è basata sull’identificativo del nodo mittente s e dal numero di round corrente r, d = r+s. Dopo l’esecuzione di un numero di round pari alla dimensione della rete meno uno, ogni nodo avrà comunicato con ogni altro nodo della rete. • Invio dei messaggi in Round-Robin binario, riduce la banda utilizzata per l’invio dei messaggi eliminando i messaggi di gossip ridondanti. La scelta del nodo destinatario di ogni messaggio è data da d = (s + 2r−1 )mod(n) dove n è la dimensione della rete..

(35) Capitolo 3. Progettazione e Implementazione del sistema Cloud-to-Peer In questo capitolo è presentato Cloud-to-Peer. Cloud-to-Peer è un sistema che può essere inserito nella classe dei sistemi di volunteer-computing, la sua peculiarità rispetto ai sistemi esistenti è la completa decentralizzazione di tutte le sue funzionalità. L’utente che utilizza Cloud-to-Peer è in grado di eseguire task complessi che richiedono notevoli risorse computazionali e tempi di completamento non banali sfruttando le risorse remote offerte dal sistema. L’intero processo di sottomissione e allocazione dei jobs è trasparente all’utente, ricalcando il modello di servizio Infrastructure as a Service(IaaS) offerto dalla tecnologia cloud: il sistema fornisce le risorse, l’utente definisce il software che può essere eseguito su tali risorse. Nel seguito viene fornita una descrizione pi` u dettagliata di Cloud-To-Peer utilizzando: • Modello Fisico, viene analizzata la composizione hardware del sistema con riferimento all’insieme di computers e altri dispositivi e rete di interconnessione tra di essi. • Modello Architetturale, analizza il middleware che coordina e controlla il sistema fornendo una descrizione delle funzionalità e dell’interfaccia fornita da ogni modulo. • Protocolli e Interazioni tra i Moduli utilizzati per garantire che le funzionalità offerte dal sistema vengano rispettate.. 3.1. Modello Fisico. Il sistema è composto da una piattaforma hardware composta da un numero indefinito di computers, o host, connessi tra loro, la rete viene gestita mediante la suite di protocolli TCP/IP. Non vi sono assunzioni sulla particolare configurazione hardware 27.

(36) 28. CAPITOLO 3. che ogni computer deve possedere, nel sistema possono essere presenti varie architetture hardware con risorse computazionali (CPU e memoria di lavoro) e dispositivi di storage eterogenei. Tra gli host non vi sono divisioni di ruolo, ognuno è sia fornitore che consumatore di risorse, l’ unica eccezione è rappresentata dal server utilizzato per il bootstrap della rete. Il server di bootstrap consente ad ogni host di connettersi alla rete P2P, costituisce dunquei il punto di aggancio degli host al sistema. L’utilizzo di un server per l’accesso alla rete è reso necessario dal ben noto problema del bootstrapping che affligge ogni rete P2P e di cui ad oggi vi sono soluzioni decentralizzate solo per reti di piccole dimensioni[12]. Ogni host non è vincolato a possedere specifici componenti software come ad esempio un particolare sistema operativo, l’unico requisito è quello di possedere una java virtual machine che fornisce la virtualizzazione necessaria per l’ambiente di esecuzione dei task.. 3.2. Modello Architetturale. L’architettura utilizzata per implementare il middleware del sistema è rappresentata in figura 3.1. Ogni utente è in grado di interagire direttamente con il sistema utilizzando l’interfaccia utente, le comunicazioni tra nodi avvengono mediante socket utilizzando i protocolli forniti dalla rete di comunicazione a cui ogni host è connesso. Nel seguito è fornita la descrizione di ogni componente che costituisce il middleware utilizzando l’astrazione della composizione basata su eventi asincroni[36] in cui ogni componente del sistema, denominato modulo, fornisce una interfaccia composta dagli eventi che riceve e che produce. Ogni evento può essere associato ad un insieme di attributi, ovvero un insieme di informazioni associate all’evento, e possono essere di tipo: • Richiesta, sono prodotte dai moduli per richiedere un servizio da un altro modulo; • Conferma, sono generate da un modulo per notificare il completamento del soddisfacimento di una richiesta; • Indicazione, sono utilizzati per consegnare informazioni ad un altro modulo.. 3.2.1. User Interface. E’ il modulo che si occupa di gestire l’interazione tra utente e sistema. Dal punto di vista dell’utente, il sistema è un’unica entità a cui è possibile richiedere l’esecuzione di jobs che possono essere scomposti ed eseguiti in parallelo. Per sottomettere un job, l’utente specifica: • Nome del jar che costituisce il codice eseguibile del programma parallelo; • Nome del file che contiene i dati di input; • Numero dei nodi da allocare per eseguire il jar;.

(37) 3.2. MODELLO ARCHITETTURALE. 29. Figura 3.1: architettura a strati del sistema • Configurazione hardware minima dei nodi da allocare; • Eventuali parametri per la configurazione dei task; La suddivisione dei dati di input avviene tramite partizionamento del file in chunck di dati aventi dimensione pari a: Dimensione file di input / numero nodi allocati Il partizionamento non tiene conto del contenuto o tipo di file da partizionare, ogni nodo ricever` a un chunck di dati avente la medesima dimensione e tali che la concatenazione di tutti i chunck permette di ricostruire il file di input originario. Le indicazioni sulla configurazione hardware dei nodi da allocare consiste nella definizione di vincoli sulla: • Frequenza di clock della CPU; • Dimensione della memoria di lavoro; • Capacit` a di storage. L’interfaccia offerta dal modulo è composta da: SUBMIT JOB(req) Richiede l’esecuzione di un determinato job con un determinato input. Req è il path del file contenente la richiesta dell’utente. Tale file conterrà.

(38) 30. CAPITOLO 3 il nome del codice eseguibile (in formato jar) del job, il nome del file che verrrà utilizzato come input, la configurazione hardware minima dei nodi che verranno allocati per eseguire il job.. STATUS(state) indica all’utente lo stato di avanzamento della computazione. La computazione pu` o trovarsi in uno dei seguenti stati: • RESOURCE ALLOCATION, indica che il sistema è nella fase di allocazione delle risorse che rispettano la configurazione hardware fornita dall’utente. • DATA PARTITIONING, indica che è in esecuzione la funzione di partizionamento dei dati e di invio di ogni partizione ai nodi allocati. • WAITING, indica che il sistema ha terminato l’invio dei dati di input ed è in attesa che la computazione distribuita termini. • RETRIVING OUTPUT, indica che la computazione distribuita è terminata e il risultato è in fase di trasmissione verso il nodo locale. • COMPLETED, indica che la computazione distribuita è terminata e l’output si trova in un file del dispositivo di storage locale. • INTERRUPTED, indica che la computazione è stata interrotta senza portare a termine il job. JOB TERMINATED(output) , indica che il job è terminato e l’output è conservato in un file del dispositivo di storage locale. DISCONNECT() , richiede la disconessione del nodo dalla rete P2P, l’utente può in qualsiasi momento eseguire la disconnessione interrompendo la condivisione delle risorse locali. CONNECT() , richiede la connessione dell’host alla rete e abilita la condivisione delle risorse locali.. 3.2.2. Local Cache. E’ il componente del sistema che interagisce con il sistema operativo per accedere ai dispositivi di storage del nodo. I dati utilizzati dal sistema sono contenuti in files organizzati in 4 directory nelle quali verrannno conservati i file di input, i file di output, i file eseguibili e i file di log utilizzati per registrare eventi significativi verificatisi ad ogni nodo e per scopi di debugging. L’interfaccia del modulo è costituita da: GET DATA(type,name) , richiede i dati contenuti nel file il cui tipo è specificato da type(specifica se i dati sono di input, ouptut o codice eseguibile) e l’identificativo da name; PUT DATA(type,name) , richiede l’allocazione di un file di tipo specificato da type con identificativo name;.

(39) 3.2. MODELLO ARCHITETTURALE. 31. GET PATH(type,name) , richiede il path completo del file di tipo type corrispondente a name.. 3.2.3. Local Resource Monitor. Il LocalResourceMonitor(LRM) è il modulo che si occupa di individuare le risorse computazionali locali e di monitorarne l’utilizzo. Le risorse monitorate sono: • CPU; • Memoria di lavoro. L’interfaccia del modulo è costitita da: GET N CPU() , richiede il numero di CPU presenti nel nodo; GET CPU SPEED() , richiede le frequenze di clock delle CPU locali al nodo; GET RAM() , richiede la dimensione della memoria di lavoro; GET RAM UTILIZATION() , richiede la percentuale di utilizzo medio della memoria di lavoro. Tra le risorse monitorate vi è anche la percentuale di utilizzo della CPU, il cui valore non viene notificato agli altri nodi del sistema, ma viene utilizzato per stabilire una condizione di disconnessione del nodo dal sistema, quando il suo valore supera la soglia del 30%, viene automaticamente attivata la procedura di leave che consentirà all’host di disconnettersi dalla rete P2P e quindi interrompere la condivisione delle risorse locali. In modo analogo, quando il valore percentuale dell’utilizzo della CPU scende al di sotto della soglia del 30%, il nodo eseguirà la procedura di join per tornare a far parte della rete P2P e condividere nuovamente le risorse computazionali locali. L’automazione della procedura di join/leave appena descritta, consente all’utente di non percepire alcun cambiamento nelle performances del proprio PC-Desktop, dato che l’utilizzo del nodo da parte dell’utente locale avrà sempre priorità maggiore rispetto all’utilizzo da parte di utenti remoti.. 3.2.4. Remote Resource Catalog. Il RemoteResourceCatalog(RRC) si occupa di conservare informazioni sulle risorse dei nodi che compongono la rete. Le informazioni sulle risorse remote sono rappresentate mediante tuple del tipo: < ID nodo,<tupla risorse computazionali>, delay comunicazione > dove: • ID nodo è l’identificativo del nodo all’interno della rete, corrisponde all’indirizzo IP;.

(40) 32. CAPITOLO 3 • <Tupla risorse computazionali> è composta da: <numero di CPU, frequenza di clock delle CPU, dimensione della memoria di lavoro, percentuale di utilizzo della memoria di lavoro, spazio di storage disponibile>; • Delay di comunicazione è il tempo necessario a trasferire uno stream di dati pari a 100KB verso il nodo.. Conservare le informazioni sulle risorse remote nel nodo locale permette di avere tempi di query costanti, il tempo necessario per ottenere informazioni sulle risorse remote corrisponde al tempo necessario per interrogare la tabella per cercare i nodi i cui attributi rispettino i vincoli richiesti dalla query. L’interfaccia è costituita da: GET NODE( n,<tupla risorse computazionali> ) richiede gli identificativi di un numero di nodi pari a n le cui risorse computazionali hanno attributi con valori pari o maggiore a quelle indicate in <tupla risorse computazionali>, a parità di valore vengono scelti i nodi associati al minor valore di delay comunicazione; UPDATE NODE( ID nodo, <tupla risorse computazionali> richiede l’aggiornamento dei valori degli attributi delle risorse computazionali associate al nodo identificato con ID nodo; DELETE NODE(ID nodo) richiede la rimozione dal catalog della entry associata al nodo identificato con ID nodo;. 3.2.5. Virtual Tree. Il Virtual Tree [33] è il modulo che si occupa di gestire la rete P2P sulla quale si poggia il sitema di ricerca delle risorse, ovvero è il modulo che implementa l’ Overlay Management Protocol(OMP). Tale rete utilizza l’astrazione del virtual node, ovvero i nodi sono suddivisi in piccoli gruppi, i nodi all’interno del medesimo gruppo sono connessi l’uno con l’altro secondo la topologia della clique. All’interno di ogni virtual node sono definte: • Le interconnessioni verso gli altri virtual nodes per formare la virtual overlay; • Gli attrattori che hanno il compito di spostare i nodi fisici tra i virtual nodes. L’utilizzo degli attrattori permette di avere virtual nodes composti da un numero di nodi fisici compreso tra due intervalli: max-size e min size. Quando la dimensione del virtual node è inferiore alla soglia del min-size, vengono attivati gli attratori, ovvero una procedura atta a spostare all’interno del virtual node nodi fisici che appartengono ad altri virtual nodes, la scelta del virtual node da cui prelevare il nodo fisico è basata su una regola deterministica. Quando invece la dimensione del virtual node è superiore al valore di max-size, il virutal node non accetterà pi` u nuovi nodi, se le dimensioni di tutti i virtual nodes raggiungono la soglia definita.