Research On Techniques Of Bandwidth Allocation And Flow Scheduling In Large-scale Data Centers

With the development of Internet and computer technology,more and more Internet-based applications and services are emerged.As the underlying infrastructure of these applications and services,data centers are increasingly required to be constructed.However,during the process of constructing data centers,there are still many key scientific problems and challenges to be solved.This thesis mainly pays attention to four crucial challenges in large-scale data centers,including scarce bandwidth resource,disperse bandwidth resource,huge volume of traffic,and time-space-varying traffic.After reviewing the existing methods and previous work,this thesis studies two types of problems which are bandwidth allocation and flow scheduling.The detailed research content and contributions are summarized as follows:Within the data center,the traffic triggered by cluster computing applications is significantly increased,which makes link bandwidth often become scarce resource.Therefore,this thesis mainly pays attention to three negative consequences,including skewed usage of link bandwidth,inelastic usage of bandwidth,and extended application completion time,which would be caused by multiplexing cluster computing frameworks in a same data center.After recognizing those consequences,this thesis studies the problem of bandwidth sharing and flow scheduling across multiple cluster computing frameworks,with the aim of improving link bandwidth utilization and reducing application completion time.For bandwidth allocation,this thesis first proposes a virtual link group abstraction to encapsulate all links into a virtual shared bandwidth pool.Based on this pool,this thesis further proposes a three-level bandwidth allocation method,so as to guarantee the network performance of the applications and enable elastic bandwidth sharing among cluster computing frameworks.For flow scheduling,this thesis proposes a virtual link group dependency graph,and designs a 3/2-approximation algorithm,so as to achieve load balancing flow scheduling and mitigate the skewed usage of link bandwidth.The experimental results demonstrate that the proposed method can significantly reduce the application completion time and improve the link bandwidth utilization.In the inter-datacenter network,this paper mainly studies the bandwidth allocation and flow scheduling problems around the objectives of minimizing cost and maximizing performance.First,in terms of cost,this paper observes that there is a considerable amount of free time slots in the percentile billing model that is used by ISPs to charge their customers' traffic.Traffic trans-mitted during these time slots does not affect the overall transmission cost.Therefore,this thesis leverages the advantages of Lyapunov optimization technique to design a bandwidth allocation and flow scheduling method,so as to exploit those free time slots for inter-datacenter traffic,thus reducing the traffic transmission cost.Experimental results reveal that the proposed method can reduce significant cost of inter-datacenter traffic transmission.Second,in terms of performance,this thesis observes that when performing bandwidth allocation and flow scheduling for Coflows running across data centers,leveraging the flexibility in placing the endpoints of network flows can significantly reduce the completion times of Coflows.Hence,this paper studies the prob-lem of jointly optimizing flow endpoint placement and flow scheduling to minimize the average completion time of Coflows running across data centers.To solve this problem,this thesis first proposes an endpoint placement and flow scheduling algorithm for a single Coflow,and then extends this algorithm to multiple Coflow scenarios.Experimental results demonstrate that the proposed method can significantly reduce the average completion time of Coflow.Finally,this thesis studies the bandwidth allocation and flow scheduling problem for inter-datacenter traffic,and develops a distributed algorithm by taking the advantage of alternating direction method of multipliers(ADMM),so as to minimize the supplier's network cost and at the same time provide bandwidth guarantee.The experimental results verify that the proposed method can significantly reduce the network cost,and also provide bandwidth guarantee for inter-datacenter traffic.In terms of serving user service request,this thesis mainly studies the bandwidth allocation and request scheduling problems.For bandwidth allocation,this thesis proposes a new type of service—"inter-datacenter network as a service",so as to shift user's wide-area traffic from the public Internet to the private wide-area networks owned by big companies(e.g.,Google and Microsoft).Under this new service model,this thesis studies the bandwidth allocation problem in a scenario of multiple users and multiple providers.This thesis further designs a bandwidth allocation method based on a two-stage Stackelberg game.The experimental results show that the proposed bandwidth allocation method can guarantee the utilities of both providers and users.In terms of request scheduling,this thesis studies users'service request scheduling problem with the aim of jointly optimizing bandwidth resource efficiency and user delay.To solve this problem,this thesis proposes a request scheduling algorithm based on logarithmic smoothing technique.Experimental results demonstrate that the proposed algorithm can greatly improve the bandwidth utilization of the data centers,and also significantly reduce the user delay.