Online cloud scheduling with fare classes: a combined theoretical and simulation-based analysis

Online cloud scheduling is becoming a key factor in today's market due to the ubiquity of cloud computing. From the cloud providers' point of view, many online algorithms have been created to decide which customers' requests to accept or reject, in order to maximize profits. However, these solutions give performance guarantees based on strict assumptions, such as the input coming from a probability distribution, or by having the customer wait for a decision. A different setting that employs online algorithms to serve similar purposes is the airline industry, and some of its work ensures a certain level of performance without any assumptions or system parameter knowledge. This thesis addresses online cloud scheduling issues using techniques and models from the airline industry revenue management. In particular, it divides the incoming requests into fare classes and applies a Nested Protection Level policy to make acceptance decisions, whose revenue is analyzed through competitive analysis and operations research techniques. Theoretical results provide bounds on the resulting competitive ratio. A simulation environment is built to validate the theoretical results, employing randomly generated requests: different combinations of workload intensity show the impact of requests characteristics on the revenue in plausible real-world scenarios.

Lo scheduling online in ambito cloud computing sta sempre più diventando un fattore chiave nel mercato odierno, dovuto alla diffusione del cloud computing. Dal punto di vista dei provider cloud, sono stati creati numerosi algoritmi online per decidere quali richieste dei clienti accettare e quali rifiutare, in modo da massimizzare i profitti. Nonostante ciò, queste soluzioni riescono a garantire certe performance basandosi unicamente su ipotesi stringenti, come il fatto che i parametri dell'input siano campionati da distribuzioni di probabilità, o che le decisioni sull'input vengano ritardate, obbligando i clienti ad aspettare. Un altro campo che utilizza algoritmi online per uno scopo simile è il settore dei voli di linea, e alcuni risultati in questo campo assicurano un certo livello di performance senza essere vincolati da ipotesi sull'input o dalla conoscenza di parametri di sistema. Questa tesi affronta il problema dell'online cloud scheduling, utilizzando tecniche e modelli presi dalla letteratura riguardante il revenue management per i voli di linea, i cui ricavi vengono studiati tramite tecniche di analisi competitiva e ricerca operativa. Nello specifico, le richieste in entrata vengono divise in classi tariffarie e viene applicato il vincolo "Nested Protection Level" per decidere quali richieste accettare. Risultati teorici forniscono limiti sul competitive ratio trovato. Questi risultati sono validati in un ambiente di simulazione, utilizzando delle richieste generate aleatoriamente: diverse combinazioni di carico sul sistema evidenziano l'impatto delle caratteristiche delle richieste sui ricavi, in possibili scenari reali.