Research On Topology Aware Resource Allocation Algorithm For Virtual Clusters

It has been nearly50years since virtualization technology was born. With thedevelopment of virtualization technology, its security, isolation, customization featuresincreasingly draw people’s attention. Virtualization technology is no longer just confined onsingle computer field, but development to the virtualization of traditional distributedcomputing field, give a good way to solve the problems in traditional distributed computingarea, such as, the difficulty in matching the heterogeneity of physical resources and therequirement of user applications; system security; collaborative management of systemresources.Virtual cluster resource allocation problem is a basic and critical problem in building avirtual cluster. The quality of virtual cluster resource allocation is very important to theperformance of the distributed and parallel application running in virtual cluster and theutilization of physical resources. However, current virtual cluster resource allocationalgorithms mainly focus on minimizing the implementation time of virtual cluster, improvingthe resource utilization, load balancing, and lack of resource allocation optimization for thedistributed and parallel application which actually running in virtual cluster. Since thedistributed and parallel applications are the real resource users, only if we optimize theresource allocation for applications we can achieve better outcomes.Since the topological structure and the resource requirement of virtual cluster are decidedby the parallel application running in it, at the same time, virtual cluster is composed bymultiple virtual nodes which interconnected by virtual network. The virtual cluster resourceallocation problem is closed related with task mapping problem[4]and virtual networkmapping problem[12], all of them can be transferred to as how to map a weighted andundirected graph into another weighted and undirected graph with constrains satisfied andobject function optimized. By comparing and researching on the related problems: taskmapping problem[4]and virtual network mapping problem[12], in this paper, we propose atopology-aware based virtual cluster resource allocation algorithm, mainly focus on twoaspects of resource allocation issues:(1) How to improve the quality of resource allocation for single virtual cluster. Thequality of resource allocation for single virtual cluster determines the efficiency of theapplication running in it, in order to ensure the efficiency of application we need to improveits resource allocation quality.(2) How to improve the utilization of physical resource. Increase the effective utilization of resources means the increase the throughput and the revenue created by physical resources,which is of most concern to the suppliers of physical resources.The virtual cluster resource allocation algorithm we proposed is based on an extendedclassic sub-graph isomorphism detection algorithm[9], we did the following works for theabove two issues:(1) We propose the concept of―Communication Skeleton‖(CS). CS is use to describethe main topology structure attribute of a VC. It shows the major communication bandwidthrequirement of the parallel application which running in the VC. Our resource allocationalgorithm will first allocate resources to CS, make sure that the main resource requirement ofVC to be satisfied with priority; also CS simplifies the original topology graph of VC, reducesthe amount of calculation in sub-graph isomorphism search process.(2) We propose the concept of―Resource Density‖. Resource Density is use to describethe attribute of resource requirement of a VC and resource availability of a substrate networkarea. By using Resource Density combined with the total resource requirement of VC, ouralgorithm try to find the area in sub-physical networks which best fits the resourcerequirement of virtual cluster, effectively reducing the fragmentation of resources caused byresource allocation and increase the effective utilization of physical resources.(3) We propose the method of―Topology-aware node Evaluation‖. Topology-aware nodeevaluation incorporates the topology attribute of node when doing the evaluation of virtualnodes and physical nodes. On one hand, it improves the mapping order of virtual nodes inresource allocation process; on the other hand, it improves the selection of host substratenodes of virtual nodes, effectively optimize the quality of VC resource allocation.Through extensive simulation experiments, our algorithm presents better resultscompared with the current state of the art virtual network mapping algorithm in the quality ofresource allocation, the total revenue of physical resources, and the algorithm performance,attained the expected results of our work.