Research On QoS-aware Service Deployment Problem

Recently, service oriented computing is becoming a a new computing paradigm. It uses services as the basic building blocks, and can facilitate fast, low-cost modular development of distributed applications, thus becoming a key technology for provid-ing on-demand services. In a service-oriented distributed system, one fundamental issue is the service deployment problem, i.e., which network nodes the services are placed and run on. Generally, a well deployment can not only increase the system re-source utilization and reduce system cost, but also improve the QoS of user requests. However, due to the complexity of decision parameters of QoS, the uncertainty of user requests, as well as the the dynamics of system operations, service deployment problem is full of challenges. Meanwhile, along with the increasingly wide range of service applications, and the expansion'of service functionalities, together with the development of service systems, service deployment has to face the user growing demands and system expansion needs. Although the service deployment problem has been studied for several years, it has to be further investigated to improve the QoS of more and more users, to make the system resource utilization better, and to deal with the service serialization and variety in composited services.Since the QoS-aware service deployment is closely related to user request pat-tern, in this dissertation, we conduct a comprehensive study on the QoS-aware service deployment problem, considering both cases where user request pattern is prior known or not.The contributions of this dissertation are summarized as follows:1) For those applications where user request pattern can be known or estimated beforehand, we can optimize the initial service deployment. We aim at minimizing the service deployment cost while ensuring that all the QoS of users can be satisfied. With respect to the user request rates, we investigate the deployment problem for different cases step by step, i) stable user demands case:On condition that the servers are CPU uncapacitated, we first show that the QoS-aware deployment prob-lem is NP-hard, and then propose a set-cover based greedy algorithm which has a logarithmic approximation factor. When the CPU capacity constraints on servers are taken into account, we prove that the QoS-aware deployment problem cannot be approximated unless P=NP. Therefore, we propose two heuristic algorithms, one is iterated set-cover based algorithm (ISCA), and the other is knapsack-based algo-rithm (KBA). ii) increasing user demands case:for both cases that user demand increasing models are prior or unprior, we define two optimization objectives called system lifetime and system extension factor, respectively, and show that both cases can be solved by extending the algorithms ISCA and KBA. Experimental results show that ISCA and KBA have distinct effects on different demand sizes. ISCA is more efficient when client demands are relatively small, while KBA performs better for larger demands.2) For those applications where user request pattern cannot be known or es-timated prior, the initial service deployment is random to some extent. With the growing user requests, the system will become unbalanced with respect to resource consumption, and some user requests would not be satisfied with QoS guarantee. In this case, we study how to find the bottle-neck service component, and how to choose proper positions to deploy more replicas to balance system overload and increase user QoS levels. We propose LDCS to select the bottle-neck service component by evaluating the realtime performance of all service components. We also propose MACP algorithm to select a suitable node to deploy this service component replica. Theoretical analysis shows that both LDCS and MACP have low time complexities, and simulation results approve that our approach is effective and efficient.3) In a service system where user request pattern cannot be known or estimated prior, although the approach in (2) can improve the whole system performance, it cannot guarantee the QoS of each individual user request.Therefore, for those ap-plications where user request QoS needs to be satisfied restrictly, we consider how to incrementally deploy a set of replicas simultaneously, such that all individual requests can be satisfied with QoS guarantee. We formally define this service de-ployment problem, and prove that it is NP-hard to decide whether an arbitrary instance of this problem has a feasible solution. Therefore, this problem does not admit any approxiamation algorithm unless P=NP. In this case, we employ a tech-nique named parametric prunning, and propose a practical, low-time complexity heuristic algorithm SRA. Experimental results show that, SRA can greatly reduce the deployment cost, while ensuring the QoS strictly of most of user requests.