Research On Algorithms Of Service Resource Provisioning And Job Scheduling For Social Welfare Maximization

There are mainly three service modes of cloud computing:infrastructure-as-a-service(IaaS),platform-as-a-service(PaaS)and software-as-a-service(SaaS).Due to the professionalism,affordability and convenience,SaaS services have become important choices for governments,enterprises,organizations and individuals to apply cloud computing.At the same time,in consideration of cost-saving,pay-as-you-go,elastic scaling,and other aspects,SaaS providers choose to purchase IaaS resources from IaaS providers to operate their services.Therefore,in cloud environments,a three-level service market of IaaS providers-SaaS providers-users is formed,with SaaS providers as the center.In this service market,the main process of dynamic service provisioning is as follows:users arrive dynamically and submit their service requests(called jobs),then SaaS providers purchase IaaS resources with appropriate types and quantities according to actual require-ments,process the submitted service requests on these resources and charge users correspondingly.From the perspective of maximizing the social overall revenue,to achieve ef-ficient service provisioning,the following three small problems are needed to be solved:(1)Effective resource provisioning.That is,according to the actual needs of users,determine the type and quantity of IaaS resources purchased from IaaS providers to prevent over-provisioning and under-provisioning.(2)Efficient job scheduling.That is,schedule users' jobs to appropriate resources in the right order,so as to realize the full utilization of resources and efficient execution of jobs.(3)Reasonable service pricing.That is,calculate the appropriate prices for users' service requests,so as to regulate the process of service provisioning,and achieve the maximum social overall revenue.Generally speaking,resource provisioning,job scheduling,and service pricing are mutually complementary,mutually affecting and inseparable.They jointly determine the efficiency of ser-vice provisioning.In order to achieve the above objectives,when the worth of services is difficult to determine,this paper focuses on pleasingly parallel jobs and makes decisions based on users' values to their jobs.Pleasingly parallel jobs have flexible degrees of parallelism and can be divided into any number of tasks to execute in parallel on different resources,without extra cost.In this context,how to provision resources,schedule jobs,and price services effectively in order to optimize dynamic service provisioning becomes an urgent problem to be solved.Meanwhile,there are some unique characteristics for open,autonomous and large-scale cloud computing environments which bring severe challenges to ser-vice provisioning.For example,the heterogeneity and variability of resources,the diversity of jobs'resource demands,the otherness of users'QoS requirements and value preferences,etc.Meanwhile,users arrive dynamically and randomly.Their future arrivals and information of service requests are often difficult to accurately predict,which results in the uncertainty of future information.Besides,rational users may adopt strategic behaviors.They probably increase their personal util-ities by misreporting their true values.Therefore,from the perspective of SaaS providers,this paper comprehensively analyzes the characteristics of resources and users as well as the process of service provisioning in cloud environments.Centering on the optimization of service provisioning in the three-level service markets,a series of studies have been carried out in this paper.Specifically,the main work and contributions are:1.Focusing on the problem of job scheduling and service pricing,this pa-per first proposes an optimization algorithm based on linear programming.Considering the strategic behaviors of users,this algorithm can extract the true values from users and improve the efficiency of service provisioning in the case of limited resources,which achieves maximum social welfare.Then,in view of the possible collusion of users,this paper further proposes a collusion-resistant optimization algorithm.This algorithm can help SaaS providers efficiently provision services to guarantee social welfare,while preventing collusion among users.2.Focusing on the problem of resource provisioning and job scheduling,this paper proposes an online multi-objective optimization algorithm.Consid-ering the variable resources and the uncertain future information,with the goal of SaaS providers ' revenue and user satisfaction rate optimization,this algorithm can help SaaS providers provide services to users in real time and efficiently,when future information is unknown and cannot be accurately predicted.It can optimal social welfare and guarantee long-term revenue while improving short-term revenue.3.Focusing on the problem of mixed resource provisioning,job scheduling,and service pricing,this paper first proposes an online optimization algo-rithm for on-demand IaaS resources.Considering the real and complex cloud environments with variable resources,uncertain future information and strategic user behaviors,this algorithm can help SaaS providers make decisions in real time and efficiently on the basis of incentivizing users to reveal their values truthfully,which achieves social welfare optimization.Then,based on the above algorithm and combined with the online mixed resource provisioning algorithm,this paper proposes an online optimiza-tion algorithm for on-demand and reserved mixed IaaS resources.This algorithm can help SaaS providers further save costs and improve social welfare.In conclusion,centering on the problem of service provisioning in the three-level service markets,this paper proposes a series of resource provisioning,job scheduling,and service pricing algorithms for different scenarios.These algo-rithms optimize the social welfare and take into account the revenues of short-term and long-term.These algorithms have both theoretical significance and practical value,which can not only promote the progress of cloud computing theory and technology,but also be widely used in the cloud computing markets.Therefore,they can promote the benign and healthy development of service computing and cloud computing ecology.