Fair Allocation Of Cloud Resources Under Server Hierarchical Constraint

Cloud computing provides a convenient platform for users to perform large-scale parallel tasks,how to realize the fair sharing of cloud resources to ensure the quality of users'services has always been a hotspot in the field of cloud computing.Since most users restrict their tasks to only be performed on servers that meet the required grade,there is a hierarchical constraint relationship between the user's task and the servers,which makes it more challenging to realize fair allocation of cloud resources under hierarchical constraints.By analyzing the current fair allocation strategy,only the common constrained TSF(Task Share Fairness)strategy satisfies the four characteristics of constrained fairness in the max-min fairness allocation of task share,but the time complexity of the multi-round progressive filling algorithm is high,and it is limited in practice.Therefore,according to the law of hierarchical constraints,this thesis proposed an algorithm G-TSF(Generation-Task Share Fairness)to achieve fair allocation of cloud resources more efficiently and quickly under server hierarchical constraints.This thesis first established a mathematical programming model with the goal of maximizing the lexicographic order of the task share under the hierarchical constraint,and then proved the three lemmas that are satisfied under the model.Based on the three lemmas,the allocation result under server hierarchical constraint can be divided into multiple disjoint substructures according to the task share,users in each substructure have the same task share,and the task shares between substructures satisfy the decrement relationship,users of different substructures do not share machine resources.According to this substructure,this thesis proposed the algorithm G-TSF,this algorithm is executed in combination with the inner and outer layers,the outer layer finds different task share values according to the order from small to large,and the inner layer finds the substructure corresponding to each task share value,then it solve linear programming for each substructure for resource allocation.G-TSF reduces the number of linear programming and reduces the computational scale by the substructure method,which greatly reduces the program execution time.It is proved theoretically that G-TSF algorithm and TSF progressive filling algorithm get the same task share vector.According to the simulation experiment based on the real data of Alibaba cluster,the G-TSF algorithm and TSF algorithm obtain the same task share value for each user,it realizing the fair allocation of cloud resources under the server hierarchical constraints.The number of times of G-TSF linear programming is only related to the number of grades,and its calculation scale and execution time are slightly affected by the number of users,the number of machines and the number of grades,and its execution performance is significantly better than TSF algorithm.Moreover,the number of linear programming,the total calculation scale,and the program execution time of the G-TSF are significantly reduced compared with the TSF,and the G-TSF is more efficient than the TSF algorithm.