Description

Highlights

• In this paper, a genetic algorithm based approach is proposed to compose services in cloud computing.
• It combines QoS-aware service composition approaches and resources matching and scheduling approaches.
• For small-scale scenarios, the proposed approach finds optimal solutions; for larger scale problems, it outperforms the integer programming approach.

Introduction

Cloud computing is emerging as the new paradigm for next-generation distributed computing. A genetic algorithm-based service composition approach is proposed for cloud computing.  A composite service is specified as a collection of abstract application services according to a combination of control-flow and data-flow. Any solution to a composition problem in cloud computing includes 1) Map the abstract application services to concrete application services and corresponding UCSs (VM, database and network services). 2) Schedule the execution order of the application services This execution order is a topological sort [7] of the data-flow graph, i.e. a total ordering of the nodes in the DAG that obeys the precedence constraints.

QoS Model

QoS attributes contain (1) ascending QoS attributes, i.e. a higher value is better; (2) descending QoS attributes, i.e. a smaller value is better; (3) equal QoS attributes, i.e. no order but only equality, e.g. security protocol should be X.509. Four QoS attributes are considered in this work: response time, price, availability and reputation. QoS values of an application service consist of three parts: execution, network and storage QoSs. Existing QoS models in SOC [3] only consider the execution QoSs. Execution QoS refers to the QoS value for executing an application service in a specified VM. Network QoS values are only calculated at the destination services. Storage QoS refers to the QoS for storing a certain amount of data for a certain time using a specified database service. The QoS value for service equals the sum of execution QoS, network QoS and storage QoS. QoS constraints for composite services have two types: Global Constraints and Local Constraints. Global Constraints are the QoS constraints for the overall composite service, while Local Constraints apply to component services within the composition. Constraints on equal QoS attributes can be transformed using this function: QC ⇐ |QC| − ≤ 0, where is the tolerance allowed range

Genetic Algorithms

Genetic Algorithms (GAs) are heuristic approaches to iteratively find near-optimal solutions in large search spaces.

• In this solution, ms represents the mapping string, e.g., abstract service S1 is mapped to application service S11, S11 is further deployed on virtual machine VM and database db.
• The new ordering of the services in one bottom part is the relative positions of these services in the other original scheduling string in the pair.
• This guarantees that the newly generated scheduling strings are valid schedules.
• After crossover and mutation operators, GA will evaluate the chromosomes using a fitness function.

Handling Multiple Data Flow Graphs

Assume the composite service has multiple data-flow graphs. For each data-flow graph, an optimal composition solution can be generated using the proposed GA-based approach. Assume the composite service has f data-flow graphs.

• Given an abstract service Si, if Si only belongs to one data-flow graph, the proposed approach selects df gj’s solution chromosome to execute abstract service Si.
• Given an abstract service Si, if Si belongs to more than one data-flow graph, there are many solutions that can be used to execute Si. The proposed approach will select the most frequently used solution, or ask end-users to select a preferable solution.

Comparisons are conducted between the proposed approach and other approaches in small-scale scenarios.  All the experiments are conducted on computers with Intel Core 2 Duo 6400 CPU (2.13GHz and 2GB RAM)

Creation of Experimental Scenarios

Generated scenarios are used for the experiments. Each scenario contains a control-flow graph and a data-flow graph.

QoS values of different concrete services, virtual machines, database services and network services for each abstract service are generated randomly with uniform probability. The system first determines a root pattern with uniform probability for the control-flow Within this root, the system chooses with equal probability to either place abstract services into it or to choose another composition pattern as a substructure. The system chooses with equal probability to either place abstract services into it or to choose another composition pattern as a substructure This procedure ends until the generation system has spent the predefined number (n) of abstract services. Each concrete service can be lodged in m virtual machines, p database services and q network services These variables are predefined and used as input to the generation system.

Conclusion

A genetic algorithm-based approach is presented for service compositions in cloud computing.

• Service compositions in cloud computing involve the selections of application services and utility computing services.
• The number of possible application services and utility computing services only augments the search space.
• For small-scale scenarios, the proposed approach finds optimal solutions.
• For larger-scale problems, it outperforms the integer programming approach.
• This is a beginning to propose robust service composition approaches in cloud computing.
• Future work may focus to eliminate several assumptions: 1) QoS values for each component are known in this research.
• Calculating the QoS values at runtime is one direction; 2) penalty factor in the fitness function is static.
• More dynamic fitness functions can be used to improve the performance of the approach.
• More dynamic fitness functions can be used to improve the performance of the approach. 3) novel crossover and mutation operators may accelerate the converge