Truthful Mechanism For Multi-resource Allocation In Cloud Computing

Multi-resource allocation is one of the most critical problems to be solved in cloud computing.Recently,existing allocation mechanisms are faced with the diffi-culties of the pricing,untruthful declaration,and the allocation without the actual environment.To address these problems,this dissertation is based on combina-torial auctions to design truthful mechanism considering multi-mapping,dynamic demand,time constraint,Quality of Service,dynamic multiple resource provision and allocation.The main contributions of this dissertation are listed as follows:?1?Aiming at the multi-mapping allocation problem,this dissertation first pro-poses the multi-resource allocation considering multi-mapping model,which permits mapping VMs allocated to one user to physical machines for VM provisioning and allocation.We then propose an approximate mechanism based on the heterogeneous resource fragmentation,and show the approximation ratio is (Nc_max/k_min)^1/2,where N is the number of users,c_maxis the maximum available resources,and k_min is the minimum requested resources.Experimental results demonstrate that,compared with the single-mapping,the multi-mapping can significantly improve allocation efficiency and increase social welfare.?2?Aiming at the dynamic demand problem,this dissertation first proposes the multi-resource allocation considering dynamic demand model.We then propose a truthful approximation mechanism based on dual linear program.In addition,we show the approximation ratio is O(R⁽1/(c_min-1)),where c_minis the minimum avail-able resources.Experimental results demonstrate that our proposed mechanism can effectively meet the needs of users and increase revenue.?3?Aiming at the time constraint problem,this dissertation first proposes the multi-resource allocation considering time constraint model.We then propose a greedy mechanism based on the time-optimized.In addition,we show that our proposed allocation algorithm is a monotone and the payment algorithm implements the critical payment,and thus,our proposed mechanism is truthful.Experimental results demonstrate that our proposed mechanism guarantees time constraint and serves more users.?4?Aiming at the Quality of Service?QoS?problem,this dissertation first proposes the multi-resource allocation considering with QoS model.We then propose a greedy mechanism based on service quality optimization,and show it is truthful.Experimental results demonstrate that our proposed mechanism not only guarantees QoS constraint,but also makes supplies come closer to demand.?5?Aiming at the hardware resource requirements problem,this dissertation first formulates the dynamic multiple resource provision and allocation model.We then propose a truthful greedy mechanism based on minimum resource consumption.In addition,we show the approximation ratio is min(N,c_max/k_min?N?R+2??^1/2.Experi-mental results demonstrate that our proposed mechanism effectively allocates VMs to maximize the social welfare.?6?Aiming at the solution precision and run time problem,this dissertation proposes an approximation mechanism based on a monotone branch-and-bound ap-proach.Experimental results demonstrate that our proposed mechanism obtains the solution at any precision.