An SLA-Aware Cloud Coalition Formation Approach for Virtualized Networks

One of the main challenges faced by cloud providers is the uncertainty in their workload, resulting from the high variability and the dynamic nature of clients' demands. The inability to meet those demands during peak times can lead to high service rejection rates, experienced delays, and consequently profit and reputation losses. The concept of cloud federation has been proposed as a way to address this challenge, by enabling a group of cloud providers to collaborate by dynamically combining their resources as needed, to satisfy received requests. Existing cloud federation approaches fail to consider clients' SLA requirements during the coalition formation process or provide a self-healing mechanism to deal with unexpected resources' shortage during operation. Furthermore, the state of the art approaches suffer from performance issues, such as high execution times, unstable performance, and lack of convergence to a solution in complex scenarios (e.g., requests with mixed, independent types of VMs). This paper proposes a novel social gaming based approach for coalition formation in the cloud that finds the best coalition of cloud providers to answer requests, while satisfying the clients' SLA requirements. The proposed algorithm, dubbed SLA Aware Cloud Coalition Formation algorithm (S-ACCF), leverages Irving's roommate algorithm to form a stable coalition of cloud providers, with a rapid execution time. The S-ACCF algorithm is designed to maximize the coalition's profit, while minimizing the number of participants in the coalition as well as the penalty incurred by providers who fail to offer all or some of the promised resources using a self-healing process. The S-ACCF algorithm was extensively tested using a variety of scenarios, and its performance was compared to two state of the art approaches: 1) the Optimal Cloud Federation Mechanism (OCFM) that relies on an exhaustive search of all possible solutions to find the best coalition; and 2) the Cloud Federation Formation Mechanism (CFFM) that relies on an iterative split-and-merge approach to find the best coalition. While the optimal approach (OCFM) always finds the best coalition leading to the highest collective profit, it has an exponential time complexity, thus leading to very large execution times. On the other hand, the split-and-merge approach (CFFM), which relies on random selection of sub-groups for coalition formation, suffers from instability (different results in repeated runs), high and variable execution time, and a noticeable requests' rejection rate that changes between runs. The test results show that the S-ACCF algorithm addresses the limitations of the OCFM and the CFFM algorithms, and outperforms the optimal and split-and-merge approaches in terms of execution time, individual provider payoff, and the number of providers per coalition. Furthermore, it yields higher stability and zero rejection rate, when compared to the split-and-merge approach. Indeed, our proposed approach yields an execution time that is 12 to 25 times faster than the optimal and split-and-merge approaches, which is a major advantage for real-time applications. Moreover, when compared to the two other approaches, our S-ACCF algorithm always finds the smallest coalition possible satisfying the client requirements, thus leading to the highest individual payoff for providers and lower administration overhead. Finally, unlike the split-and-merge approach, our algorithm shows a stable performance, and converges towards the optimal solution in simple and complex scenarios, thus making it suitable for production environments.