高性能网络中面向大数据传输QoS的带宽调度研究

发布时间：2020-06-07 20:25

【摘要】：许多科学、工程及商业领域的大规模应用产生了海量数据,需要及时进行远程传输以便存储、共享与分析,传统互联网尽力而为的服务模式已经远远不能胜任。具有高带宽及带宽预留特点的高性能网络(High Performance Network,HPN)可通过带宽预留为大数据传输提供专用通道,已被科学界和工业界公认为一种高效的解决方案,从而成为该领域的一个研究热点。目前,许多高速骨干网通过软件定义网络(Software Defined Networking,SDN)技术可以方便地实现高性能网络的功能,利用控制平面全局视图通过集中式调度充分地利用昂贵的带宽资源,极大地提高传输服务质量(Quality of Service,QoS)。在HPN中,作为控制平面中心单元的带宽调度器,可基于网络拓扑和可用带宽计算合适的网络路径,以满足特定大数据的即时带宽预留需求,以及多种类型的批量大数据的周期性提前带宽预留需求。本文的研究核心是基于SDN技术,研究高性能网络中面向大数据传输的带宽调度理论、机制和算法,以解决HPN中多路径带宽调度、不同类型请求的联合带宽调度及带宽抢占等带宽调度的难点问题,目标是优化用户满意度指标,包含最小化完成时间、最大化满足的用户请求数及最小化抢占数量等参数。本文的主要贡献是提出并建立若干个可应用于HPN中以提高大数据传输性能的问题模型:多路径即时带宽调度问题、不同类型的多个大数据传输请求的周期性带宽调度问题,及高优先级的实时预留与低优先级的提前预留的协同调度及带宽抢占问题,证明这些问题都是NP-完全问题,并分别提出了若干启发式带宽调度算法。主要创新性工作如下:i)首先,针对现有单路径带宽调度吞吐量有限及可靠性不能保证等问题,采用多路径进行带宽预留。提出并建立了两条节点不相交的固定路径即时带宽调度模型(BS-2FNDP)。根据是否允许带宽变化,进一步将该模型分为两个子问题:两条固定路径固定带宽(2FPFB)及两条固定路径可变带宽(2FPVB)。证明了这两个问题均为NP-完全问题,并分别提出了接近最优解的启发式提高算法Imp2FPFB和Imp2FPVB。经大量实验评估本文提高算法的性能,在小规模网络应用中接近最优算法,在大规模网络中明显优于其它启发式算法。ii)其次,针对多条固定路径调度方法缺乏灵活性、带宽利用不充分的问题,提出了两条可变路径即时带宽调度模型(BS-2VNDP)。进一步根据两条可变路径(2VP)在不同时隙是带宽固定/可变(FB/VB)、路径切换延迟可/否忽略(0/1),将BS-2VNDP分为2VPFB-0/1和2VPVB-0/1四个子问题。分别证明了其NP-完全性并提出启发式提高算法Imp2VPFB-0/1,Imp2VPVB-0/1。经大量在随机网络及实际网络拓扑中对算法性能的实验仿真,本文提高算法性能明显优于其它启发式算法。iii)针对截止期限约束下不同类型的多个大数据传输请求,提出了周期性调度BS-MVTR问题模型。考虑固定/可变带宽两种类型的大数据传输请求(FBBR/VBBR),结合满足的用户请求数最大化及每个用户请求的完成时间最小化,定义了一个量化的用户满意度新指标。证明了该问题的NP-完全性及不可逼近性,并提出启发式算法FMS-MVTR,其中对两类请求分别设计了不同的调度算法BS-FBBR和BS-VBBR。通过大量仿真网络及实际网络拓扑的实验,表明本文FMS-MVTR算法的用户满意度及调度成功率性能均远好于利用已有算法的比较算法。iv)针对云数据中心之间不同优先级的传输应用,研究高优先级实时带宽预留(Immediate Reservation,IR)和低优先级的提前带宽预留(Advance Reservation,AR)的协同调度问题,定义为BS-IRAR。证明该问题的NP-完全性并提出一个启发式协同调度算法Max-S-IRAR。首先,对一个周期内累积的一批AR请求提出了一个最小资源占用优先算法Min-R-AR使满足的AR请求的数量最大化;其次,在已成功预留带宽的AR传输期间,为随机到来的IR计算一条每个时隙带宽最大的可变路径,若该路径不能满足IR传输需求,则需要抢占已预留成功的低优先级的AR的固定路径,采用可变路径与固定路径双通道并行调度IR。设计了一个最小抢占算法MinPreemption以减少抢占的AR数量和带宽。综合AR和IR请求成功调度的用户数、单个请求完成时间、请求的优先级及抢占的AR请求数等因素,定义了一个协同调度的用户满意度性能指标。经大量仿真实验证明,本文所提出的协同调度算法Max-S-IRAR性能大大优于其它启发式算法。
【学位授予单位】：西北大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：TN919.1

【参考文献】