Resource Fair Allocation In Cloud Computing Systems With Multi-Constraints

In the multi-resource fair allocation in cloud computing,multiple constraint situations are likely to occur,such as resource constraints,task placement constraints,and time-varying resource requirements.A fair and efficient algorithm can take these constraints into account and then allocate resources rationally,which has important to ensure the efficiency of each user’s task execution and improving the resource utilization.Existing studies mostly model the resource allocation problem as a single constraint or static resource demand situation,which is difficult to ensure fairness and efficiency in practice.To address these problems,based on the method of algorithm mechanism design theory,this thesis carries out research on algorithm mechanism design for the multiresource allocation problem of cloud computing with multiple constraints,which ensure the allocation fairness and efficiency.The main contents are as follows:1.To address the resource allocation problem that users have limited time-varying resource requirements,this thesis proposes a multi-resource fair allocation algorithm based on the concept of resource sharing fairness.Firstly,the thesis develops a linear programming model according to users’ dynamic limited tasks resource requirements and the amounts of resources shared by users,and its aims to make the global cumulative dominant resource share vector be lexicographical max-min fairness.This algorithm is further proved which satisfies four significant fairness properties: Sharing incentive,Pareto efficiency,Envy fairness,and Truthfulness.The experimental results base on the Alibaba cluster trace shows that,compared with the non-sharing case,the proposed algorithm achieves good results in ensuring the fairness of resource allocation and ensuring high resource utilization.Compared with existing algorithm,the algorithm can improve the task execution efficiency.2.To solve the problem of fair sharing allocation of time-varying resources with task placement constraints,this thesis proposes a multi-resource fair allocation algorithm,which based on the concept of cumulative task share fairness.The algorithm considers the user allocation history,and it aims to make the user cumulative task share vector be max-min fairness.The theoretical results show that this algorithm satisfies four significant fairness properties: Sharing incentive,Pareto optimality,Envy-freeness,and Truthfulness.The results of the micro-benchmark show that the algorithm can guarantee the Sharing incentive property and the fairness of allocation.The trace-driven simulation results based on the Alibaba cluster tracer data show that,compared with the existing algorithms,the algorithm can effectively reduce user waiting time,job queuing time,and job completion time.3.To deal with the problem of fair allocation with task placement constraints in mobile edge computing,this thesis proposes an allocation algorithm based on the concept of task share fairness.This algorithm considers the fair allocation of computing resources of edge servers and the wireless bandwidth resources respectively.The goal of this algorithm is to make the user task share vector in lexicographical order.The theoretical results show that,this algorithm satisfies four significant fairness properties: Sharing incentive,Pareto optimality,Envy-freeness,and Truthfulness.Experimental results based on on the Alibaba cluster trace show that compared to the current algorithm,this algorithm can achieve higher bandwidth resource utilization and guarantee the Sharing incentive property.