即时调度中周期调度最大化的带宽预留策略

摘  要： 越来越多的高性能网络通过电路交换或MPLS/GMPLS技术提供专用信道，支持大数据传输。为带宽预留服务开发有效的调度算法已成为提高网络资源利用率和满足应用用户传输要求的关键任务。高性能网络中即时带宽的研究集中关注在单次性能，本文对于即时调度中的周期性能优化，考虑一个新的问题：即时调度中的周期调度最大化问题。本文证明此问题是NP问题，针对此问题提出并实现了一个启发式算法：FBMHA，对FBMHA与Greed-MSR算法进行了大量的实验进行评估。实验结果表明，FBMHA算法相比于Greed-MSR算法在成功率和传输数据量方面有大的提升，表现出了FBMHA算法的优越性。

关键词： 高性能网路;带宽调度;服务质量;软件定义网络

中图分类号： TN915.9    文献标识码： A    DOI：10.3969/j.issn.1003-6970.2019.12.027

本文著录格式：王涛，王永强，王康. 即时调度中周期调度最大化的带宽预留策略[J]. 软件，2019，40（12）：118123

Bandwidth Reservation Strategy For Maximizing Periodic

Scheduling in Real-time Scheduling

WANG Tao1， WANG Yong-Qiang2， WANG Kang3

（1. School of Information Science and Technology， Northwest University， Xi'an， Shaanxi 710127， China; 2. College of Physics，

Northwest University， Xi'an， Shaanxi， China， 710127; 3. Xichang Satellite Launch Center， Xichang， Sichuan， China， 615000）

【Abstract】： More and more high-performance networks provide dedicated channels through circuit switching or MPLS/GMPLS technology to support big data transmissions. Developing effective scheduling algorithms for bandwidth reservation services has become a key task to improve network resource utilization and meet application user transmission requirements. The research on real-time bandwidth in high-performance networks focuses on single-time performance. This paper proposes a new problem for the optimization of periodic performance in real-time scheduling： the problem of maximizing the number of periodic scheduling in real-time scheduling.

This paper proves that this problem is an NP problem. A heuristic algorithm is proposed and implemented for this problem： FBMHA， and a lot of experiments are carried out on the FBMHA and Greed-MSR algorithms. The experimental results show that the FBMHA algorithm has a significant improvement in the success rate and the amount of transmitted data compared to the Greed-MSR algorithm， showing the superiority of the FBMHA algorithm.

【Key words】： High performance network; Bandwidth scheduling; Quality of service; Software defined networking

0  引言

信息化是當今时代发展的大趋势，科学、工程和商业应用各领域的软件应用如雨后春笋出现，生成的海量数据需要及时进行传输以便存储和分析。传统互联网尽力而为的服务模式已经难以应对，而如Internet2-ION [1]和能源科学网络（ESnet）[2]的高性能网络（HPN）成为公认的一种有效解决方案。这些网络通过软件定义网络技术（Software Defined Networking，SDN）实现基于网络拓扑和带宽、延迟等信息预先计算合适的网络路径，在数据准备传输时提供通信信道并提供带有各种服务质量（QOS）的带宽预留服务。许多高速骨干网也可通过SDN技术方便的实现这些功能。软件定义网络是当今热门网络架构之一[3]，目前有很多关于SDN的控制器结构、安全策略和流量控制等的研究[4-6]。

带宽调度的方式可分为以下两种：1）即时调度：每接收一个请求便立即调度[7];2）周期调度：将特定时间间隔中累积的多个请求视为整体进行调度[8，9]。网络服务提供商希望成功调度所有收到的请求，以提高系统吞吐量和资源利用率。即时调度的研究集中关注单个BRR的性能如最早完成时间和最短持续时间，周期调度关注一个时间间隔内的这批请求总体性能。

本文将即时调度模式和提高时间间隔内调度成功率这两者结合起来，考虑即时调度模式中的一个时间间隔内调度尽可能多的BRR。即时调度拥有响应快的优势，在即时调度的情景下，提高一个时间间隔内BRR的成功率是一个全新且具有研究前景的方向。本文称之为即时调度周期最多调度问题，说明此问题是NP问题并提出一个启发式算法：最小跳数给定带宽路径调度算法（FBMHA），与提出的贪婪式算法Greed-MSR（maximum success rate）进行了实验评估。大量的实验结果表明，FBMHA算法相比于Greed算法在成功率和传输数据量方面有大的提升，表现出了FBMHA算法的优越性。

1  研究现状

Balman等人考虑了即时调度中的最早完成时间和最短持续时间[7]，接收到用户请求后，在期望时间间隔内，遍历所有时间窗，取其中拥有最早结束时间和最大带宽的选项。

Lin和Wu考虑了以下四个带宽调度问题[10]：（1）固定带宽固定路径（FPFB），（2）带可变带宽的固定路径（FPVB），（3）固定的可变路径带宽（VPFB），以及（4）带可变带宽的可变路径（VPVB）。目标是最小化数据传输结束时间。作者对这些问题进行了详细的问题复杂性分析，并提出了对应的算法。

Zuo等人研究了在HPN中调度具有不同优先级的多个BRR的问题[8]。在该研究中，提出了两种最优算法，对于每个BRR，所提出的算法计算并向用户返回带有最早完成时间（ECT）或最短持续时间（SD）的带宽预留选项。

Tong Shu和Wu制定了一个即时带宽调度问题：在调度完成的前提下尽量减少数据传输期限约束下的能耗，作者采用了一种实用的功率模型評价，并针对模型提出一个多项式时间最优解的算法[11]。

Sharma等人研究了周期调度中在尽可能容纳更多BRR的同时缩短在一条预留路径上完成所有数据传输的总时间的问题[12]。所提出的算法为每个预留请求识别最佳预留选项，以实现多个预留请求的最小总数据传输时间。

Wang等人制定了一个最大化总带宽的问题：最大化k个边缘不相交路径的总带宽，其中k>1。并对网络资源进行了特殊定义，使得每一条路径提高带宽利用率进而使得总带宽提高[13]。

刘静等人给出了一种基于独立生成树的网络多路径传输方式，并在传输时间、传输速度上进行了网络传输性能分析[14]。

Greed-MSR是贪心算法，使用Dijkstra-最大带宽算法即文献[10]中FPFB计算路径时的算法依次调度BRR，Dijkstra-最大带宽算法是即时调度调度单个BRR时的最优解，本文将其作为对比算法。

周期性调度算法一般以除BRR接收顺序之外的某种顺序如文献[15]采用按D降序排列BRR。这不适应于BRR信息未知的即时调度。FixBW算法借鉴了文献[13]的思路，将多个路径视为多个请求，原文是采用一批次计算的多个路径选择一个资源分数最低的，本文选择带宽等于D（）的路径，即倾向于选择充分使用当前链路带宽的选项，尽量避免小额带宽的链路而尽量留下大额带宽的链路，有利于后续的用户请求调度。

2  网络模型

本章介绍了许多定义和参数，以详细说明带宽预留的概念和数学模型。参数列于表1。

HPN表示为具有n个节点和m个链路的图G（V，E），V和E分别表示节点集合和链路集合。假设拓扑图如图1所示，则V = {， a，，}，E = {-a， a-， -b， b- }。网络路径为从源节点到目的节点的途经节点组成的有序节点集。

对于链路e∈E，其可用带宽随时间而变化，这些带宽表示为时间的分段常量函数，存储每个时隙中链路的剩余带宽。所有链路的时隙带宽列表（TB）组合在一起构成聚合TB列表（ATB），如图1所示。

假设G的拓扑图显示在图1左侧。在时间点0接收到BRR，请求在时间间隔[0 s， 10 s]内将24 Gb

表1  部分参数及释义

Tab.1  Some parameters and definitions

vs 起始节点

Vd 结束节点

Bmax 最大带宽约束

D 传输数据量

ts 最早传输时间

TE 最晚截至时间

p 数据传输路径

ts 数据传输开始时间

Te 数据传输结束时间

tS 时间步长

tW 时间窗

B（e， tS） 链路e在时间步长tS时的带宽

B（p， tW） 路径P在时间窗tW时的带宽

B（PS，tW） 路径集在时间窗tW时的带宽

H 跳数

图1  拓扑图及时隙带宽例

Fig.1  Topology diagram and time slot bandwidth example

数据从传输到，最大LAN带宽为8 Gb/s。G表示为：V{，a，b，，E{-a，a-， -b，b-}。链路的可用带宽表显示在图1中右图。此BRR表示为：（，， 24 Gb， 8 Gb/s， [0，10 s]）。

时间点：对于任何时刻t，如果G的任何链路在时刻tΔ和时刻t +Δ处具有不同的可用带宽，Δ←0，则我们将时刻t称为时间点。例如，图1中G有四个时间点，即{0 s， 4s， 6s， 10 s}。

假设有n个时间点：{，…，}。时间步长被定义为[]，0≤i

时间窗是由数个连续时间步长组成的时间间隔。由表示的时间窗j可以表示为[，]，其中和分别表示相应时间间隔的开始时间和结束时间。将G中的三个时间步长排列组合，共有个时间窗口。

给定由时间步长，，···，组成的时间窗口，链路e在内的的可用带宽表示为：B（e，）或B（e，[，]），值为包含的所有时间步长中最小可用带宽，即：

（1）

例如，时间窗口[0， 6 s]由= [0，4 s]和= [4s，6s]组成。B（–b，）= 7Gb/s， B（–b，）= 3Gb/s。通过使用公式（2.1），B（–b，[0，6s]） = min（B（–b，），B（–b，））） = min（7 Gb/s，3 Gb/s） = 3 Gb/s。带宽在时间窗内被视为静态。假设路径p由边，，…，组成，p表示为––…–。时间窗内G中路径P的可用带宽表示为：B（P，）或B（P，[，]）。时间窗内的路径P的可用带宽受P上的瓶颈链路限制，即其中最小可用带宽的链路：

（2）

例如，路径–b–包括边–b和b–。通过使用公式（2），B（–b–，[0，10s]）= min（B（–b，[0，10s]），B（b–，[0，10s]））= min（3 Gb/s，5 Gb/s）= 3 Gb/s。

用户请求为DCBRR，它是生产带宽预留系统中最常见的带宽预留服务模型，表示为BRR（D，， ，，（，））。其中和分别指的是开始节点和目的地节点，和D表示容许最高带宽以及从VS传输到VD的数据总数量，为用户允许的最早傳输开始时间，为用户允许的最晚传输截至时间。

如果成功安排此BRR，返回预留选项（QR），表示为：（P，B，[，]），其中P，B，和分别表示带宽预留路径，路径带宽，数据传输开始时间和数据传输结束时间。

3  问题定义与复杂度分析

3.1  问题定义

给定网络G（V，E），依次调度在给定的时间间隔内到达的BRR，时间间隔内到达的BRR数量未知，除当前到达的BRR外BRR的信息未知，成功调度则返回QR，失败返回NULL。是否存在一种调度方式调度至少数量n的BRR？

3.2  问题复杂性分析

定理：即时调度周期最多调度问题是非确定性问题。

评估性能是周期性且输入存在未知信息，则这个问题是非确定性问题， 非确定性问题不存在确定的最优解决方法。已知即时调度问题的评估性能为一段时间内，这段时间内的BRR数量和BRR的信息是未知的，所以此问题是非确定性问题。

4  算法

最小跳给定带宽路径调度算法循环遍历每个时间窗，调用给定带宽路径算法，存储其中最小跳数的路径以此法依次调度LBRR。

表2  最小跳数给定带宽路径调度算法

Tab.2  Minimum hop count given bandwidth path scheduling algorithm

输入：图G（V，E），LBRR。

输出：LQR，其中成功调度返回的为QR，调度失败的为NULL。

具体步骤：

1：for brr  LBRR do

2：  for i = 0;T_slot，i++ do

3：    for j =i;T_slot;j++ do

4：    P = 给定带宽路径算法（）;//表7

5：    if （B（P，[i，j]） > D/（j–i+1） && Hop < MinHop） ||（ Hop == MinHop） && B（P，[i，j]） < B（，[i，j]）;

6：       MinHop = Hop;

7：       QR = （P， D/（j–i+1）， [i，j]）;

8：  LQR .add（QR）;

9：  将路径P中含有的链路在时间步长（LP[m]， LP[m + 1]）， （LP[m + 1]， LP[m +2]）， . . .（LP[n ? 1]， LP[n]）的可用带宽减去B（P，[i，j]）;

10：return（LQR）;

表3  给定带宽路径算法

Tab.3  Given bandwidth path algorithm

输入：图G（V，E），源节点，目标节点，请求路径的带宽BW。

输出：若找到带宽值为BW的路径，则返回此路径集合，若不存在返回大与BW且与BW差值最小的路径，若上述两者都不存在，返回NULL。

具体步骤：

1：while（！selectNode[curNode]） do

2：  for i = 0; node; i++ do

3：    distance = B[curNode][i];

4：    for j = 0; k; j++ do

5：      distance = min;

6：        distanced降序插入;

7：        if distanced == 保留min（H）;

8：          if Hop = MinHop 保留min（带宽利用率）;

9：  curNode = max（BW） && ！select（）;

10：for i = 0; k; i++ do

11：  if （BW[][i] == BW）

12：    x = i;

13：  else

14：    x = min（BW[][i] –BW）;

15： while（！select[]） do

16：    for i = 0; k; i++ do

17： if BW[curNode][x] == BW[nextNode][i] && ！select（parNode[nextNode][i]）;

18：        parNode = parNode[nextNode][i]; x = i; return;

19：       else

20：       parNode = min（BW[nextNode][i] – BW[curNode][x]）; x = i; return;

21：    if not find parNode

23：      将curNode加入禁止并回滚;

24：    path.add（parNode）;

25：ruturn（path）;

给定带宽路径算法分为三个部分：行1-8更新信息，行9-13选择路径，行14-23从终点回溯路径。第一部分和第三部分是基于Dijkstra-最大带宽算法的修改版，更新信息时每个节点存储多个路径的信息而不是一个（相同带宽的路径存储跳数最小的），回溯路径部分也做出了相应的修改。

5  实验与评估

5.1  实验参数

本文安排了两组网络，每个网络给定节点和链路的数量，网络拓扑图随机生成。每个链路分配0GB/s到10GB/s范圍内的随机带宽。LBRR含有100个BRR，每个BRR随机生成源节点vs、目标节点vd、传输数据量D和允许传输时间范围[，]。对于每个网络使用不同的随机种子模拟100次，最后取平均值展示。

5.2  实验

表4  初始组网路

Tab.4  Initial group network

网络规模索引号 1 2 3 4 5 6 7 8

节点数 6 6 7 7 8 8 10 10

链路数 10 15 15 20 20 25 25 30

第一组实验的网络参数如表4所示，实验结果如图2所示，图2左图显示调度BRR个数，图2右图为传输数据量。FBMHA算法和Greed-MSR算法在十组网络平均调度数量分别为59和53，平均传输数据量分别为358和311 GB，两者分提升了6个和47 GB。观察第一组和第二组数据，在网络链路增多时FBMHA算法提升的幅度增大，说明一定的链路资源对于FBMHA算法有更好的发挥，而在第

图2  平均调度数量和平均传输数据量

Fig.2  Average number of scheduled

and average transmitted data

四个网络后随着网络索引递增节点数增多，观察第五组和第六组数据，差值几乎没有增幅。两种算法数据量的提升和调度成功率提升幅度基本一致。

第二组实验的网络参数如表5所示，实验结果如图3所示，图3左图显示调度BRR个数，右图为传输数据量。FBMHA算法和Greed-MSR算法在十组网络平均调度数量分别为72和69，平均传输数据量分别为491和458GB，两者分提升了3个和 33GB，两种算法数据量的提升和调度成功率提升幅度基本一致。FBMHA算法相对于Greed-MSR算法调度BRR个数的差值随着网络链路逐渐增大而后在第六组数据后增速平缓，观察第一组数据FBMHA算法相对于Greed-MSR算法基本无提升，因为链路资源太少;观察第八组数据带宽资源富足时，已几乎足以调度所有的BRR，此时性能效果也不好。

表5  增加链路数量网路

Tab.5  Increase the number of links in the network

网络规模索引号 1 2 3 4 5 6 7 8

节点数 30 30 30 30 30 30 30 30

链路数 30 40 50 60 80 100 120 160

图3  第二组实验网络平均调度数量和平均传输数据量

Fig.3  Average number of scheduled

and average transmitted data

5.3  评估与分析

首先，FixBW相对于Greed-MSR在调度BRR数量和传输数据量上都有比较大的提升。其次实验印证FBMHA的思路是充分利用了网络资源，在网络资源相对匮乏时FBMHA的效果会更好。

6  结论及展望

结合了即时调度和周期调度各自的特点，研究一个新的问题：即时调度周期最大化调度问题。说明此问题是非确定性问题，不存在确定性的最优解。针对即时调度对于信息未知只能尽力调度的特点，提出一个合理利用资源的启发式算法：FBMHA算法。将提出的算法FBMHA与Greed-MSR算法进行了实验以评估其性能，大量的实验结果表明，FBMHA算法相比于Greed算法在成功率和传输数据量方面有大的提升，且在链路带宽相对缺乏时有更好的性能，表现出了FBMHA算法的优越性。

未来作者首先会关注采用一些技术如随机优化进一步提升成功率，其次关注加入准入控制来限制需求过高传输数据量的BRR，最后关注即时调度中其它的周期性能如总延迟等。

参考文献

[1]Internet2， “Internet2 Interoperable On-Demand Network （ION） service， ”2011[Online]. Available ： http：//www.internet2.edu/ion.

[2]ESnet， “OSCARS：On-demand Secure Circuits and Advance Reservation System” 2011[Online]. Available：http：//www.es. net/Oscars.

[3]陈凡， 刘果， 李剑锋， 等. 主要软件定义网络控制器的对比和分析[J]. 软件， 2015， 36（6）： 97-102.

[4]李洁. 云平台SDN 关键技术的研究与展望[J]. 软件， 2015， 36（7）： 71-74.

[5]王天明， 符天. 基于扩展OpenFlow流标结构增强SDN网络安全性研究[J]. 软件， 2018， 39（7）： 01-05.

[6]刘文. 基于大数据优化网络的安全性策略的研究[J]. 软件， 2018， 39（9）： 205-208

[7]M. Balman， E. Chaniotakisy， A. Shoshani， and A. Sim， “A ?exible reservation algorithm for advance network provisioning， ” in Proc. of the 2010 ACM/IEEE Int. Conf. for High Perform. Comput.， Netw.， Storage and Anal.， Washington， DC， USA，

2010， pp. 1-11.

[8]L. Zuo， M. Zhu， and C. Wu， “Fast and ef?cient bandwidth reservation algorithms for dynamic network provisioning， ” J. of Network and Syst. Manage.， pp. 1–25， 2013.

[9]A. Schill， S. K¨uhn， and F. Breiter， Design and evaluation of an advance reservation protocol on top of RSVP. Boston， MA： Springer US， 1998， pp. 23–40.

[10]Lin Y， Wu Q. Complexity analysis and algorithm design for advance bandwidth scheduling in dedicated networks[J]. IEEE/ACM Transactions on Networking （TON）， 2013， 21（1）： 14-27.

[11]T. Shu， C. Wu， and D. Yun， “Advance bandwidth reservation for energy ef?ciency in high-performance networks， ”inProc. IEEE38thConf.Local Comput. Netw.， Oct. 2013， pp. 541- 548.

[12]S. Sharma， D. Katramatos， and D. Yu， “End-to-end network qos via scheduling of ?exible resource reservation requests， ” in Proc. of 2011 Int. Conf. for High Perform. Comput.， Netw.， Storage and Anal.， 2011， pp. 1-10.

[13]WANG， Tao， et al. Multi-Path Routing for Maximum Bandwidth with K Edge-Disjoint Paths. In： 2018 14th International Wireless Communications & Mobile Computing Conference （IWCMC）. IEEE， 2018. p. 1178-1183.

[14]刘静. 基于独立生成树的网络多路径传输方法研究[J]. 软件， 2016， 37（4）： 25-28.

[15]Zuo L， Zhu M M， Wu C Q. Bandwidth reservation strategies for scheduling maximization in dedicated networks[J]. IEEE Transactions on Network and Service Management， 2018， 15（2）： 544-554.