Algorithms for Network-Aware Application Component Placement for Cloud Resource Allocation

Due to the soaring popularity of cloud-based services over the last years, the size and the complexity of cloud environments has been growing quickly. In the context of cloud systems, mapping a number of application components to a set of physical servers and assigning cloud resources to those components is challenging. Traditional resource allocation systems which rely on a centralized management paradigm suffer from scalability issues, making them inappropriate for large-scale cloud environments. Therefore, there is a need for providing new management solutions that scale well to large size cloud systems. In this article, we present optimal and heuristic solutions for network-aware placement of multicomponent applications with differing component characteristics. The optimal integer linear programming (ILP)-based solution minimizes the application rejection rate and the cost of mapping while respecting application component requirements and physical network limitations. As the execution time of the optimal model scales exponentially, we also offer scalable heuristic solutions for centralized and hierarchical application placement, which are thoroughly explained and evaluated and compared to the optimal solution. Our evaluations show that while the proposed centralized heuristic is near-optimal, the hierarchical approach is much faster and offers higher scalability compared to a centralized approach, e.g., mapping 2.7 million application components onto 512k servers. Moreover, the percentage of servers used and fully placed applications remain close to that of the centralized and optimal solutions.