Research | Funded Projects

ALGORITMI DI BIN-PACKING SEMIONLINE RELAXED PER LA GESTIONE DELLE RISORSE NEL CLOUD COMPUTING

In letteratura, esistono diversi tipi di algoritmi di Bin-Packing semionline: bounded-repacking, lookahead, preordering, conoscenza di OPT, tra questi. In particolare, alcuni algoritmi contraddicono direttamente la definizione di bin-packing online, perché usano conoscenze future su elementi che non sono ancora arrivati in input mentre altri, invece, rispettano questo requisito e assegnano un elemento a un bin senza sfruttare nessuna conoscenza futura, ma semplicemente riorganizzando il packing attuale. Normalmente operazioni di riorganizzazione dei dati sono comuni negli algoritmi online.Con questa ricerca si vuole, inannzitutto, classificare, in modo innovativo, gli algoritmi semionline esistenti in letteratura sulla base della loro distanza dalla definizione di online “puro”.Si vuole, inoltre, ridefinire il modello di bin packing semionline detto “relaxed”, introdotto da Gambosi, Postiglione e Talamo in SIAM J. Comput., vol 30 (5), 2000, sulla base del nuovo criterio di classificazione degli algoritmi di bin-packing introdotto da Balogh, Bekesi, Galambos e Reinelt, in SIAM J. Comput., vol 38 (1), 2008 e che prevede la presenza di due componenti, lo scheduòler e il loader, i cui comportamenti definiscono la tipologia di algoritmo.Si vuole, infine, verificare l’applicabilità degli algoritmi di relaxed semionline bin-packing alla gestione delle risorse in un ambiente di cloud computing.Il modello di Bin Packing “Relaxed” (il cui miglior algoritmo è 1.333) permette di ottenere prestazioni molto vicine a quelle degli algoritmi offline (1.222) pur mantenendo una sostanziale appartenenza alla classe online (il cui miglior algoritmo è 1.58). “Relaxed” impone di assegnare un elemento a un bin, non appena esso arriva, senza sfruttare nessuna conoscenza futura, ma semplicemente riorganizzando il packing attuale tramite due operazioni: moving e grouping. Relaxed permette, in un tempo successivo al suo arrivo, di spostare un elemento verso altri bin. Ovviamente il costo dell’operazione è conteggiato nelle prestazioni dell’algoritmo e, inoltre, ad ogni passo, il numero massimo di spostamenti effettuabili è limitato da una (piccola) costante.Il “grouping” permette di raggruppare elementi di dimensioni molto ridotte, tutte nello stesso bin, in un unico gruppo che verrà trattato come un’unica unità indivisibile. Si noti che, nel bin-packing, tale operazione è possibile e conveniente. Ad esempio per caricare una flotta di camion è utile imballare oggetti piccoli in un’unica scatola e da quel momento in poi considerarla come un unico elemento.Il modello “Relaxed” funziona molto bene in tutte le situazioni in cui la lista di input non è nota in anticipo (potrebbe essere infinita) e ciascun elemento (che potrebbe arrivare con notevole ritardo rispetto al precedente) deve essere elaborato immediatamente, mentre il rendimento garantito deve essere mantenuto per il sottoinsieme di elementi fino a quel momento arrivati. Il modello Relaxed permette di sfruttare il tempo di inattività tra l’arrivo di due elementi consecutivi di ingresso. Più in dettaglio, esso è particolarmente adatta quando il tempo trascorso tra due elementi consecutivi è > HK, dove il costo massimo per spostare un elemento e K è il numero massimo di movimenti ammessi ad ogni passo è H.Un'importante applicazione del modello Relaxed potrebbe essere nel mondo cloud. In un cloud, il movimento di dati da un dispositivo (disco) ad un altro è costoso ed è, potenzialmente, una fonte di errori, ma è necessario per mantenere bilanciato il peso di ciascun dispositivo. Ovviamente, se alcune informazioni vengono perse a causa di spostamento dei dati, esse possono essere recuperate grazie ad operazioni di rollback, che sono, però, molto costose. Il modello Relaxed dovrebbe permettere di ottenere rendimenti molto buoni, in termini di tempo di esecuzione, ma anche di ridurre al minimo il rischio di perdita di dati.