A branch and price approach for deployment of multi-tier software services in clouds. (November 2016)

• Record Type: Journal Article
• Authors: Gullhav, Anders N.; Nygreen, Bjørn
• Is Part Of: Computers & operations research. Volume 75(2016)
• Page Start: 12
• Page End: 27
• Publication Date: 2016-11
• Subjects: Branch and price -- Shortest path problem with resource constraints -- Multi-tier service -- Replication -- Cloud computing; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.05.007
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: This paper considers a service deployment problem that combines service placement and replication level decisions in a cloud computing context. The services are composed of multiple components that are to be placed on nodes in the private cloud of the service provider or, if the private cloud has limited capacity, partly in a public cloud. In the service delivery, the provider has to take into account the quality of service guarantees offered to his end-users. To solve the problem, we develop a branch and price algorithm, where the subproblems both are formulated as a linear mixed integer program and a shortest path problem with resource constraints (SPPRC) on a network with a special structure. The SPPRC can be solved by an exact label-setting algorithm, but to speed up the solution process, we develop a heuristic label-setting algorithm based on a reduced network and simplified dominance rule. Our results show that using the heuristic subproblem solver is efficient. Furthermore, the branch and price algorithm performs better than a previously developed pre-generation algorithm for the same problem. In addition, we analyze and discuss the differences in solutions that utilize resources in a public cloud to different degrees. By conducting this analysis we are able to identify some essential characteristics of good solutions. Abstract : Highlights: We model placement and replication level decisions for multi-tier cloud services. The models are solved using a branch and price algorithm. Different solution methods for the subproblem are compared. Using a heuristic solution method for the subproblem speed up the solution process. The branch and price algorithm performs better than a priori column generation.