Resource Allocation And Scheduling In Cloud Data Center Networks

Cloud computing has become a public resource of the information society at the moment,and the data center is the infrastructure that supports cloud computing services.All of the work in this thesis revolves around the resource allocation and scheduling problem in cloud data centers.The second chapter studies the multi-resource fair queueing(or multi-resource flow scheduling)problem on a server or a middlebox;The third chapter studies the multi-resource fair sharing problem in a cloud data center;The forth chapter studies the online load balancing problem of VNFs with placement constraints;And the fifth chapter explores the online social welfare maximization(SWM)problem for non-preemptive jobs.(1)Hierarchical multi-resource fair queueing for Network Function VirtualizationThe second charpter focuses on the hierarchical multi-resource fair queueing problem on a single server or a middlebox in NFV.Existing multi-resource fair queueing algorithms regard each flow as an individual,thus providing flat scheduling.However,flows derived from multiple tenants or service classes are usually grouped together to be served.In order to schedule grouped flows,this thesis proposes two hierarchical multi-resource fair queueing algorithms,collapsed Hierarchical Dominant Resource Fair Queueing(collapsed H-DRFQ)and dove-tailing H-DRFQ.Implementation and simulation results show that,both H-DRFQ algorithms can provide correct hierarchical share guarantee.Meanwhile,according to the scheduling delay results,both algorithms have their pros and cons.(2)Low-complexity hierarchial multi-resource fair allocationThe third charpter studies the low-complexity hierarchical multi-resource fair allocation problem in a data center.As the workload surges,the data center scheduler needs to make thousands of decisions per second and thus requires decision making at high speeds.Existing hierarchical multi-resource fair sharing algorithms require O(q~2) work,whereis close to the number of users in a data center.This thesis proposes a low-complexity hierarchical multi-resource fair sharing algorithm,Multi-resource Collapsed Hierarchies(MCH),that has only a linear complexity O(q).Moreover,according the practical features of user demands,the complexity of MCH can be further simplified to the logarithmic form of the number of part of the users.Simulation results show that MCH provides proper hierchical share guarantee and reduces the runtime effectively.(3)Online load balancing for the VNF deployment with placement constraintsThe forth charpter studies the online load balancing problem for the Virtual Network Functions(VNFs)with placement constraints.Despite the rich bodies of recent work on the constrained load balancing problem using the network flow algorithms,they all suffer polynomial complexities,leading to unbearable running time in practical executions.This thesis proposes a new load balancing policy termed Constrained Min-max Placement(CMMP)that schedules VNFs in a way similar to the max-min fairness,where we try to assign the most possible VNFs to the poorest loaded server.The online scheduler for CMMP has a logarithmic time complexity and is simple enough to implement in practice.Trace-driven simulations show that the online CMMP speeds up at least two orders of magnitude of running time comparing to other network flow algorithms.(4)Online multi-resource social welfare maximization for non-preemptive jobsThe last part of the research studies the online multi-resource SWM for non-preemptive users.The cloud provider usually wants to maximize the social welfare.Conventional solutions to SWM are offline,that every time the system status changes,a task of a user has to stop due to reconfiguration of resources,leading to the preemptions of user scheduling.In order to overcome this,this thesis proposes an online algorithm,Cumulative Adaptive Dominant Resource Fairness(C-ADRF),that can provide a near-optimal social welfare,as well as being able to schedule the tasks in an non-preemptive manner.Simulation results show an impressive behavior of C-ADRF in providing social welfare,only 3%and 2%away from the optimal social welfare,respectively.