Bandwidth Scheduling Algorithms For The QoS Assured Of Big Data Tranfer In High Performance Networks

Many large-scale applications in broad science,engineering,and business domains are generating big data,which must be transferred to remote sites for various storage and analysis purposes.The best-effort service model on the Internet is far away from meeting such unprecedented demands for big data movement.High Performance Networks(HPNs)featuring high capacity and provisioning dedicated channels through bandwidth reservation have proved to be an effective solution.Nowadays,many modern backbone networks connecting geographically distributed data centers provide such networking capability using Software-Definition Network(SDN)technology.SDN makes it possible to fully utilize expensive bandwidth resources through centralized bandwidth scheduling based on the global network view and significantly improve the Quality of Service(QoS)of big data transfer.As a central unit of the SDN control plane,the bandwidth scheduler computes appropriate network paths and allocates link bandwidths based on network topology and bandwidth availability to perform instant bandwidth reservation for one individual data transfer,and periodic bandwidth reservation for multiple data transfers.This dissertation focuses on the theories,mechanisms,and algorithms of bandwidth scheduling based on SDN,to solve a class of problems for multi-path bandwidth reservation,bandwidth co-scheduling,and preemption of multi-type requests in HPNs.The main goal is to optimize the user's satisfaction index,which combines multiple perspectives such as minimizing the earliest completion time,maximizing the number of successfully scheduled requests,and minimize the number of preempted requests.This dissertation investigates and develops various QoS-oriented bandwidth scheduling strategies: instant bandwidth scheduling with multiple paths,periodic bandwidth scheduling of multiple requests of different types,and collaborative bandwidth scheduling of immediate/advance reservation requests with different priorities for preemption minimization.For each problem,we prove its NPCompleteness and propose a heuristic solution.The main contributions of the research are as follows:i)We formulate a generic problem of Bandwidth Scheduling with Two Fixed Node-Disjoint Paths(BS-2FNDP)to support big data transfer.In BS-2FNDP,we further consider two different types of paths: a)two fixed paths with fixed bandwidth(2FPFB),whose goal is to find two fixed node-disjoint paths,each of which has a fixed bandwidth during the entire period of data transfer for the given request,such that the data transfer end time is minimized;and b)two fixed paths with variable bandwidth(2FPVB),whose goal is to find two fixed node-disjoint paths,each of which may use varying bandwidths across different time slots during the data transfer,such that the data transfer end time is minimized.We prove that both 2FPFB and 2FPVB are NP-Complete,and design a heuristic approach for each of them.We implement and evaluate these scheduling algorithms in both simulated and real-life networks.Extensive results show that the proposed heuristics achieve a close-tooptimal performance in small-scale networks,and significantly outperform other heuristic approaches in large-scale networks.ii)We formulate a generic problem of Bandwidth Scheduling with Two Variable NodeDisjoint Paths(BS-2VNDP)to improve network resource utilization for a given big data transfer.We further consider two variable paths of either fixed or variable bandwidth with negligible or non-negligible path switching delay,referred to as 2VPFB-0/1 and 2VPVB-0/1,respectively.We prove that all of these four scheduling problems are NP-Complete,and then propose a heuristic algorithm for each.For performance comparison,we also design several other heuristic algorithms based on a greedy strategy.These scheduling algorithms are implemented and tested in both large-scale simulated and real-life networks,and extensive simulation results show that the proposed heuristic algorithms significantly outperform the others in comparison.iii)We formulate a generic problem of Bandwidth Scheduling with Multiple Requests of Various Types(BS-MRVT)to improve bandwidth resource utilization of high-speed links connecting geographically distributed data centers and satisfy various types of transport requests for Cloud Service Providers.Bulk Data Transfer Requests(BDTRs)with deadline constraints are of two different forms: Fixed Bandwidth Bulk data Request(FBBR)and Variable Bandwidth Bulk data Request(VBBR).The problem of BS-MRVT is to schedule various types of BDTRs to maximize the new index of total satisfaction degree of user requests which we defined rigorously.We prove BS-MRVT to be NP-Complete and Nonapproximable.We design a heuristic algorithm,i.e.,FMS-MVTR,and two comparison algorithms,i.e.,Fixed-MRVT and OptFPFB-MRVT,respectively.Extensive simulation in simulated network and real-life networks results show that our scheduling scheme significantly outperforms existing scheduling schemes in terms of user satisfaction degree and scheduling success ratio.iv)We formulate a collaborative(co)-scheduling problem for a mixed batch of Immediate Reservation(IR)and Advance Reservation(AR)requests with different priorities between cloud data centers,referred to as BS-IRAR.We prove BS-IRAR to be NP-Complete and design a heuristic algorithm MAX-S-IRAR.Firstly,we design a minimum resource occupation priority-based algorithm,i.e.,Min-R-AR,for a batch of AR requests accumulated during a period,to maximize the number of satisfied AR requests;Secondly,we compute multiple paths with the largest bandwidth in different time slots for a high-priority IR request arriving during the transfer of AR requests that have been successfully scheduled.If there is no sufficient resource to meet the demand of the IR request,some previously scheduled AR-based transfers with lower priority may need to be preempted.We design an algorithm MinPreemption to minimize the number and bandwidth of preempted AR-based transfers.We finally design a collaborative scheduling algorithm named MAX-S-IRAR to maximize the overall QoS reflected by a user satisfaction index that collectively considers the number of successfully scheduled AR and IR requests,the completion time of each individual request,the priority of each individual request and the number of preempted AR requests.Extensive simulation results show that our proposed algorithm significantly outperforms greedy algorithm.