e incrementato se la query `e soddisfatta, mentre `e decrementato se la query non trova alcun matching.Tale tecnica possiede buona robustezza rispetto ai cambia-menti nella topologia della rete, ma pu`o 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`a, l’invio di ogni query `e 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`a 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`a 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.
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 `e centrate sulle applicazioni,poich`e il suo scopo `e 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’esecu-zione del primo task alla fine dell’ultimo task di cui il job `e 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 `e centrate sulle risorse, il suo fine `e quello di ottimizzare le performances delle risorse. In tal caso con il termine performances ci si riferisce al throughput, ovvero capacit`a 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 `e 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 decentraliz-zato 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`a.
Una prima classificazione delle tecniche di allocazione pu`o 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`a, 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 `e la quantit`a di informazioni conservate da ogni nodo, migliore `e la scelta delle risorse da allocare.
Negli schedulers di tipo dinamico[23], ogni task pu`o essere assegnato pi`u volte a nodi differenti, l’allocazione iniziale pu`o essere modificata eseguendo una migrazione del task da un nodo ad un altro, ci`o permette di evitare la stima iniziale del tempo di completamento dei task. Tale approccio consente di tener maggiormente in considera-zione 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`o 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`o non risulter`a quello ottimale.
• 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 ese-guita una stima del tempo di esecuzione sul nuovo nodo, se il costo di migrazione del task `e maggiore rispetto al tempo di esecuzione stimato, allora il task non viene spostato. L’efficienza di tale tecnica `e tanto maggiore quanto maggiori sono gli overheads di comunicazione della rete con cui sono connessi i nodi.
Un’altra classificazione degli schedulers `e 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 diffe-renti da quelle tradizionali citate finora. L’utilizzo di tali tecbiche `e 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`a 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 `e 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 `e il makespan dei mapping task-nodo e il cross-over `e lo scambio dell’assegnazione dei task tra due nodi differenti.
• Simulated annealing[3], in cui l’equilibrio termico `e rappresentato dall’assegna-zione ottimale tra task e nodi, la temperatura `e il tempo totale di completamento dei task secondo l’attuale allocazione, il cambio di temperatura `e 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