摘 ?要： 越來(lái)越多的高性能網(wǎng)絡(luò)通過(guò)電路交換或MPLS/GMPLS技術(shù)提供專用信道，支持大數(shù)據(jù)傳輸。為帶寬預(yù)留服務(wù)開(kāi)發(fā)有效的調(diào)度算法已成為提高網(wǎng)絡(luò)資源利用率和滿足應(yīng)用用戶傳輸要求的關(guān)鍵任務(wù)。高性能網(wǎng)絡(luò)中即時(shí)帶寬的研究集中關(guān)注在單次性能，本文對(duì)于即時(shí)調(diào)度中的周期性能優(yōu)化，考慮一個(gè)新的問(wèn)題：即時(shí)調(diào)度中的周期調(diào)度最大化問(wèn)題。本文證明此問(wèn)題是NP問(wèn)題，針對(duì)此問(wèn)題提出并實(shí)現(xiàn)了一個(gè)啟發(fā)式算法：FBMHA，對(duì)FBMHA與Greed-MSR算法進(jìn)行了大量的實(shí)驗(yàn)進(jìn)行評(píng)估。實(shí)驗(yàn)結(jié)果表明，F(xiàn)BMHA算法相比于Greed-MSR算法在成功率和傳輸數(shù)據(jù)量方面有大的提升，表現(xiàn)出了FBMHA算法的優(yōu)越性。

關(guān)鍵詞： 高性能網(wǎng)路;帶寬調(diào)度;服務(wù)質(zhì)量;軟件定義網(wǎng)絡(luò)

中圖分類號(hào)： TN915.9 ? ?文獻(xiàn)標(biāo)識(shí)碼： A ? ?DOI：10.3969/j.issn.1003-6970.2019.12.027

本文著錄格式：王濤，王永強(qiáng)，王康. 即時(shí)調(diào)度中周期調(diào)度最大化的帶寬預(yù)留策略[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 ?引言

信息化是當(dāng)今時(shí)代發(fā)展的大趨勢(shì)，科學(xué)、工程和商業(yè)應(yīng)用各領(lǐng)域的軟件應(yīng)用如雨后春筍出現(xiàn)，生成的海量數(shù)據(jù)需要及時(shí)進(jìn)行傳輸以便存儲(chǔ)和分析。傳統(tǒng)互聯(lián)網(wǎng)盡力而為的服務(wù)模式已經(jīng)難以應(yīng)對(duì)，而如Internet2-ION [1]和能源科學(xué)網(wǎng)絡(luò)（ESnet）[2]的高性能網(wǎng)絡(luò)（HPN）成為公認(rèn)的一種有效解決方案。這些網(wǎng)絡(luò)通過(guò)軟件定義網(wǎng)絡(luò)技術(shù)（Software Defined Networking，SDN）實(shí)現(xiàn)基于網(wǎng)絡(luò)拓?fù)浜蛶?、延遲等信息預(yù)先計(jì)算合適的網(wǎng)絡(luò)路徑，在數(shù)據(jù)準(zhǔn)備傳輸時(shí)提供通信信道并提供帶有各種服務(wù)質(zhì)量（QOS）的帶寬預(yù)留服務(wù)。許多高速骨干網(wǎng)也可通過(guò)SDN技術(shù)方便的實(shí)現(xiàn)這些功能。軟件定義網(wǎng)絡(luò)是當(dāng)今熱門網(wǎng)絡(luò)架構(gòu)之一[3]，目前有很多關(guān)于SDN的控制器結(jié)構(gòu)、安全策略和流量控制等的研究[4-6]。

帶寬調(diào)度的方式可分為以下兩種：1）即時(shí)調(diào)度：每接收一個(gè)請(qǐng)求便立即調(diào)度[7];2）周期調(diào)度：將特定時(shí)間間隔中累積的多個(gè)請(qǐng)求視為整體進(jìn)行調(diào)度[8，9]。網(wǎng)絡(luò)服務(wù)提供商希望成功調(diào)度所有收到的請(qǐng)求，以提高系統(tǒng)吞吐量和資源利用率。即時(shí)調(diào)度的研究集中關(guān)注單個(gè)BRR的性能如最早完成時(shí)間和最短持續(xù)時(shí)間，周期調(diào)度關(guān)注一個(gè)時(shí)間間隔內(nèi)的這批請(qǐng)求總體性能。

本文將即時(shí)調(diào)度模式和提高時(shí)間間隔內(nèi)調(diào)度成功率這兩者結(jié)合起來(lái)，考慮即時(shí)調(diào)度模式中的一個(gè)時(shí)間間隔內(nèi)調(diào)度盡可能多的BRR。即時(shí)調(diào)度擁有響應(yīng)快的優(yōu)勢(shì)，在即時(shí)調(diào)度的情景下，提高一個(gè)時(shí)間間隔內(nèi)BRR的成功率是一個(gè)全新且具有研究前景的方向。本文稱之為即時(shí)調(diào)度周期最多調(diào)度問(wèn)題，說(shuō)明此問(wèn)題是NP問(wèn)題并提出一個(gè)啟發(fā)式算法：最小跳數(shù)給定帶寬路徑調(diào)度算法（FBMHA），與提出的貪婪式算法Greed-MSR（maximum success rate）進(jìn)行了實(shí)驗(yàn)評(píng)估。大量的實(shí)驗(yàn)結(jié)果表明，F(xiàn)BMHA算法相比于Greed算法在成功率和傳輸數(shù)據(jù)量方面有大的提升，表現(xiàn)出了FBMHA算法的優(yōu)越性。

1 ?研究現(xiàn)狀

Balman等人考慮了即時(shí)調(diào)度中的最早完成時(shí)間和最短持續(xù)時(shí)間[7]，接收到用戶請(qǐng)求后，在期望時(shí)間間隔內(nèi)，遍歷所有時(shí)間窗，取其中擁有最早結(jié)束時(shí)間和最大帶寬的選項(xiàng)。

Lin和Wu考慮了以下四個(gè)帶寬調(diào)度問(wèn)題[10]：（1）固定帶寬固定路徑（FPFB），（2）帶可變帶寬的固定路徑（FPVB），（3）固定的可變路徑帶寬（VPFB），以及（4）帶可變帶寬的可變路徑（VPVB）。目標(biāo)是最小化數(shù)據(jù)傳輸結(jié)束時(shí)間。作者對(duì)這些問(wèn)題進(jìn)行了詳細(xì)的問(wèn)題復(fù)雜性分析，并提出了對(duì)應(yīng)的算法。

Zuo等人研究了在HPN中調(diào)度具有不同優(yōu)先級(jí)的多個(gè)BRR的問(wèn)題[8]。在該研究中，提出了兩種最優(yōu)算法，對(duì)于每個(gè)BRR，所提出的算法計(jì)算并向用戶返回帶有最早完成時(shí)間（ECT）或最短持續(xù)時(shí)間（SD）的帶寬預(yù)留選項(xiàng)。

Tong Shu和Wu制定了一個(gè)即時(shí)帶寬調(diào)度問(wèn)題：在調(diào)度完成的前提下盡量減少數(shù)據(jù)傳輸期限約束下的能耗，作者采用了一種實(shí)用的功率模型評(píng)價(jià)，并針對(duì)模型提出一個(gè)多項(xiàng)式時(shí)間最優(yōu)解的算法[11]。

Sharma等人研究了周期調(diào)度中在盡可能容納更多BRR的同時(shí)縮短在一條預(yù)留路徑上完成所有數(shù)據(jù)傳輸?shù)目倳r(shí)間的問(wèn)題[12]。所提出的算法為每個(gè)預(yù)留請(qǐng)求識(shí)別最佳預(yù)留選項(xiàng)，以實(shí)現(xiàn)多個(gè)預(yù)留請(qǐng)求的最小總數(shù)據(jù)傳輸時(shí)間。

Wang等人制定了一個(gè)最大化總帶寬的問(wèn)題：最大化k個(gè)邊緣不相交路徑的總帶寬，其中k>1。并對(duì)網(wǎng)絡(luò)資源進(jìn)行了特殊定義，使得每一條路徑提高帶寬利用率進(jìn)而使得總帶寬提高[13]。

劉靜等人給出了一種基于獨(dú)立生成樹(shù)的網(wǎng)絡(luò)多路徑傳輸方式，并在傳輸時(shí)間、傳輸速度上進(jìn)行了網(wǎng)絡(luò)傳輸性能分析[14]。

Greed-MSR是貪心算法，使用Dijkstra-最大帶寬算法即文獻(xiàn)[10]中FPFB計(jì)算路徑時(shí)的算法依次調(diào)度BRR，Dijkstra-最大帶寬算法是即時(shí)調(diào)度調(diào)度單個(gè)BRR時(shí)的最優(yōu)解，本文將其作為對(duì)比算法。

周期性調(diào)度算法一般以除BRR接收順序之外的某種順序如文獻(xiàn)[15]采用按D降序排列BRR。這不適應(yīng)于BRR信息未知的即時(shí)調(diào)度。FixBW算法借鑒了文獻(xiàn)[13]的思路，將多個(gè)路徑視為多個(gè)請(qǐng)求，原文是采用一批次計(jì)算的多個(gè)路徑選擇一個(gè)資源分?jǐn)?shù)最低的，本文選擇帶寬等于D（）的路徑，即傾向于選擇充分使用當(dāng)前鏈路帶寬的選項(xiàng)，盡量避免小額帶寬的鏈路而盡量留下大額帶寬的鏈路，有利于后續(xù)的用戶請(qǐng)求調(diào)度。

2 ?網(wǎng)絡(luò)模型

本章介紹了許多定義和參數(shù)，以詳細(xì)說(shuō)明帶寬預(yù)留的概念和數(shù)學(xué)模型。參數(shù)列于表1。

HPN表示為具有n個(gè)節(jié)點(diǎn)和m個(gè)鏈路的圖G（V，E），V和E分別表示節(jié)點(diǎn)集合和鏈路集合。假設(shè)拓?fù)鋱D如圖1所示，則V = {， a，，}，E = {-a， a-， -b， b- }。網(wǎng)絡(luò)路徑為從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的途經(jīng)節(jié)點(diǎn)組成的有序節(jié)點(diǎn)集。

對(duì)于鏈路e∈E，其可用帶寬隨時(shí)間而變化，這些帶寬表示為時(shí)間的分段常量函數(shù)，存儲(chǔ)每個(gè)時(shí)隙中鏈路的剩余帶寬。所有鏈路的時(shí)隙帶寬列表（TB）組合在一起構(gòu)成聚合TB列表（ATB），如圖1所示。

假設(shè)G的拓?fù)鋱D顯示在圖1左側(cè)。在時(shí)間點(diǎn)0接收到BRR，請(qǐng)求在時(shí)間間隔[0 s， 10 s]內(nèi)將24 Gb

表1 ?部分參數(shù)及釋義

Tab.1 ?Some parameters and definitions

vs 起始節(jié)點(diǎn)

Vd 結(jié)束節(jié)點(diǎn)

Bmax 最大帶寬約束

D 傳輸數(shù)據(jù)量

ts 最早傳輸時(shí)間

TE 最晚截至?xí)r間

p 數(shù)據(jù)傳輸路徑

ts 數(shù)據(jù)傳輸開(kāi)始時(shí)間

Te 數(shù)據(jù)傳輸結(jié)束時(shí)間

tS 時(shí)間步長(zhǎng)

tW 時(shí)間窗

B（e， tS） 鏈路e在時(shí)間步長(zhǎng)tS時(shí)的帶寬

B（p， tW） 路徑P在時(shí)間窗tW時(shí)的帶寬

B（PS，tW） 路徑集在時(shí)間窗tW時(shí)的帶寬

H 跳數(shù)

圖1 ?拓?fù)鋱D及時(shí)隙帶寬例

Fig.1 ?Topology diagram and time slot bandwidth example

數(shù)據(jù)從傳輸?shù)剑畲驦AN帶寬為8 Gb/s。G表示為：V{，a，b，，E{-a，a-， -b，b-}。鏈路的可用帶寬表顯示在圖1中右圖。此BRR表示為：（，， 24 Gb， 8 Gb/s， [0，10 s]）。

時(shí)間點(diǎn)：對(duì)于任何時(shí)刻t，如果G的任何鏈路在時(shí)刻tΔ和時(shí)刻t +Δ處具有不同的可用帶寬，Δ←0，則我們將時(shí)刻t稱為時(shí)間點(diǎn)。例如，圖1中G有四個(gè)時(shí)間點(diǎn)，即{0 s， 4s， 6s， 10 s}。

假設(shè)有n個(gè)時(shí)間點(diǎn)：{，…，}。時(shí)間步長(zhǎng)被定義為[]，0≤i

時(shí)間窗是由數(shù)個(gè)連續(xù)時(shí)間步長(zhǎng)組成的時(shí)間間隔。由表示的時(shí)間窗j可以表示為[，]，其中和分別表示相應(yīng)時(shí)間間隔的開(kāi)始時(shí)間和結(jié)束時(shí)間。將G中的三個(gè)時(shí)間步長(zhǎng)排列組合，共有個(gè)時(shí)間窗口。

給定由時(shí)間步長(zhǎng)，，···，組成的時(shí)間窗口，鏈路e在內(nèi)的的可用帶寬表示為：B（e，）或B（e，[，]），值為包含的所有時(shí)間步長(zhǎng)中最小可用帶寬，即：

（1）

例如，時(shí)間窗口[0， 6 s]由= [0，4 s]和= [4s，6s]組成。B（–b，）= 7Gb/s， B（–b，）= 3Gb/s。通過(guò)使用公式（2.1），B（–b，[0，6s]） = min（B（–b，），B（–b，））） = min（7 Gb/s，3 Gb/s） = 3 Gb/s。帶寬在時(shí)間窗內(nèi)被視為靜態(tài)。假設(shè)路徑p由邊，，…，組成，p表示為––…–。時(shí)間窗內(nèi)G中路徑P的可用帶寬表示為：B（P，）或B（P，[，]）。時(shí)間窗內(nèi)的路徑P的可用帶寬受P上的瓶頸鏈路限制，即其中最小可用帶寬的鏈路：

（2）

例如，路徑–b–包括邊–b和b–。通過(guò)使用公式（2），B（–b–，[0，10s]）= min（B（–b，[0，10s]），B（b–，[0，10s]））= min（3 Gb/s，5 Gb/s）= 3 Gb/s。

用戶請(qǐng)求為DCBRR，它是生產(chǎn)帶寬預(yù)留系統(tǒng)中最常見(jiàn)的帶寬預(yù)留服務(wù)模型，表示為BRR（D，， ，，（，））。其中和分別指的是開(kāi)始節(jié)點(diǎn)和目的地節(jié)點(diǎn)，和D表示容許最高帶寬以及從VS傳輸?shù)絍D的數(shù)據(jù)總數(shù)量，為用戶允許的最早傳輸開(kāi)始時(shí)間，為用戶允許的最晚傳輸截至?xí)r間。

如果成功安排此BRR，返回預(yù)留選項(xiàng)（QR），表示為：（P，B，[，]），其中P，B，和分別表示帶寬預(yù)留路徑，路徑帶寬，數(shù)據(jù)傳輸開(kāi)始時(shí)間和數(shù)據(jù)傳輸結(jié)束時(shí)間。

3 ?問(wèn)題定義與復(fù)雜度分析

3.1 ?問(wèn)題定義

給定網(wǎng)絡(luò)G（V，E），依次調(diào)度在給定的時(shí)間間隔內(nèi)到達(dá)的BRR，時(shí)間間隔內(nèi)到達(dá)的BRR數(shù)量未知，除當(dāng)前到達(dá)的BRR外BRR的信息未知，成功調(diào)度則返回QR，失敗返回NULL。是否存在一種調(diào)度方式調(diào)度至少數(shù)量n的BRR？

3.2 ?問(wèn)題復(fù)雜性分析

定理：即時(shí)調(diào)度周期最多調(diào)度問(wèn)題是非確定性問(wèn)題。

評(píng)估性能是周期性且輸入存在未知信息，則這個(gè)問(wèn)題是非確定性問(wèn)題， 非確定性問(wèn)題不存在確定的最優(yōu)解決方法。已知即時(shí)調(diào)度問(wèn)題的評(píng)估性能為一段時(shí)間內(nèi)，這段時(shí)間內(nèi)的BRR數(shù)量和BRR的信息是未知的，所以此問(wèn)題是非確定性問(wèn)題。

4 ?算法

最小跳給定帶寬路徑調(diào)度算法循環(huán)遍歷每個(gè)時(shí)間窗，調(diào)用給定帶寬路徑算法，存儲(chǔ)其中最小跳數(shù)的路徑以此法依次調(diào)度LBRR。

表2 ?最小跳數(shù)給定帶寬路徑調(diào)度算法

Tab.2 ?Minimum hop count given bandwidth path scheduling algorithm

輸入：圖G（V，E），LBRR。

輸出：LQR，其中成功調(diào)度返回的為QR，調(diào)度失敗的為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中含有的鏈路在時(shí)間步長(zhǎng)（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），源節(jié)點(diǎn)，目標(biāo)節(jié)點(diǎn)，請(qǐng)求路徑的帶寬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）;

給定帶寬路徑算法分為三個(gè)部分：行1-8更新信息，行9-13選擇路徑，行14-23從終點(diǎn)回溯路徑。第一部分和第三部分是基于Dijkstra-最大帶寬算法的修改版，更新信息時(shí)每個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)路徑的信息而不是一個(gè)（相同帶寬的路徑存儲(chǔ)跳數(shù)最小的），回溯路徑部分也做出了相應(yīng)的修改。

5 ?實(shí)驗(yàn)與評(píng)估

5.1 ?實(shí)驗(yàn)參數(shù)

本文安排了兩組網(wǎng)絡(luò)，每個(gè)網(wǎng)絡(luò)給定節(jié)點(diǎn)和鏈路的數(shù)量，網(wǎng)絡(luò)拓?fù)鋱D隨機(jī)生成。每個(gè)鏈路分配0GB/s到10GB/s范圍內(nèi)的隨機(jī)帶寬。LBRR含有100個(gè)BRR，每個(gè)BRR隨機(jī)生成源節(jié)點(diǎn)vs、目標(biāo)節(jié)點(diǎn)vd、傳輸數(shù)據(jù)量D和允許傳輸時(shí)間范圍[，]。對(duì)于每個(gè)網(wǎng)絡(luò)使用不同的隨機(jī)種子模擬100次，最后取平均值展示。

5.2 ?實(shí)驗(yàn)

表4 ?初始組網(wǎng)路

Tab.4 ?Initial group network

網(wǎng)絡(luò)規(guī)模索引號(hào) 1 2 3 4 5 6 7 8

節(jié)點(diǎn)數(shù) 6 6 7 7 8 8 10 10

鏈路數(shù) 10 15 15 20 20 25 25 30

第一組實(shí)驗(yàn)的網(wǎng)絡(luò)參數(shù)如表4所示，實(shí)驗(yàn)結(jié)果如圖2所示，圖2左圖顯示調(diào)度BRR個(gè)數(shù)，圖2右圖為傳輸數(shù)據(jù)量。FBMHA算法和Greed-MSR算法在十組網(wǎng)絡(luò)平均調(diào)度數(shù)量分別為59和53，平均傳輸數(shù)據(jù)量分別為358和311 GB，兩者分提升了6個(gè)和47 GB。觀察第一組和第二組數(shù)據(jù)，在網(wǎng)絡(luò)鏈路增多時(shí)FBMHA算法提升的幅度增大，說(shuō)明一定的鏈路資源對(duì)于FBMHA算法有更好的發(fā)揮，而在第

圖2 ?平均調(diào)度數(shù)量和平均傳輸數(shù)據(jù)量

Fig.2 ?Average number of scheduled

and average transmitted data

四個(gè)網(wǎng)絡(luò)后隨著網(wǎng)絡(luò)索引遞增節(jié)點(diǎn)數(shù)增多，觀察第五組和第六組數(shù)據(jù)，差值幾乎沒(méi)有增幅。兩種算法數(shù)據(jù)量的提升和調(diào)度成功率提升幅度基本一致。

第二組實(shí)驗(yàn)的網(wǎng)絡(luò)參數(shù)如表5所示，實(shí)驗(yàn)結(jié)果如圖3所示，圖3左圖顯示調(diào)度BRR個(gè)數(shù)，右圖為傳輸數(shù)據(jù)量。FBMHA算法和Greed-MSR算法在十組網(wǎng)絡(luò)平均調(diào)度數(shù)量分別為72和69，平均傳輸數(shù)據(jù)量分別為491和458GB，兩者分提升了3個(gè)和 33GB，兩種算法數(shù)據(jù)量的提升和調(diào)度成功率提升幅度基本一致。FBMHA算法相對(duì)于Greed-MSR算法調(diào)度BRR個(gè)數(shù)的差值隨著網(wǎng)絡(luò)鏈路逐漸增大而后在第六組數(shù)據(jù)后增速平緩，觀察第一組數(shù)據(jù)FBMHA算法相對(duì)于Greed-MSR算法基本無(wú)提升，因?yàn)殒溌焚Y源太少;觀察第八組數(shù)據(jù)帶寬資源富足時(shí)，已幾乎足以調(diào)度所有的BRR，此時(shí)性能效果也不好。

表5 ?增加鏈路數(shù)量網(wǎng)路

Tab.5 ?Increase the number of links in the network

網(wǎng)絡(luò)規(guī)模索引號(hào) 1 2 3 4 5 6 7 8

節(jié)點(diǎn)數(shù) 30 30 30 30 30 30 30 30

鏈路數(shù) 30 40 50 60 80 100 120 160

圖3 ?第二組實(shí)驗(yàn)網(wǎng)絡(luò)平均調(diào)度數(shù)量和平均傳輸數(shù)據(jù)量

Fig.3 ?Average number of scheduled

and average transmitted data

5.3 ?評(píng)估與分析

首先，F(xiàn)ixBW相對(duì)于Greed-MSR在調(diào)度BRR數(shù)量和傳輸數(shù)據(jù)量上都有比較大的提升。其次實(shí)驗(yàn)印證FBMHA的思路是充分利用了網(wǎng)絡(luò)資源，在網(wǎng)絡(luò)資源相對(duì)匱乏時(shí)FBMHA的效果會(huì)更好。

6 ?結(jié)論及展望

結(jié)合了即時(shí)調(diào)度和周期調(diào)度各自的特點(diǎn)，研究一個(gè)新的問(wèn)題：即時(shí)調(diào)度周期最大化調(diào)度問(wèn)題。說(shuō)明此問(wèn)題是非確定性問(wèn)題，不存在確定性的最優(yōu)解。針對(duì)即時(shí)調(diào)度對(duì)于信息未知只能盡力調(diào)度的特點(diǎn)，提出一個(gè)合理利用資源的啟發(fā)式算法：FBMHA算法。將提出的算法FBMHA與Greed-MSR算法進(jìn)行了實(shí)驗(yàn)以評(píng)估其性能，大量的實(shí)驗(yàn)結(jié)果表明，F(xiàn)BMHA算法相比于Greed算法在成功率和傳輸數(shù)據(jù)量方面有大的提升，且在鏈路帶寬相對(duì)缺乏時(shí)有更好的性能，表現(xiàn)出了FBMHA算法的優(yōu)越性。

未來(lái)作者首先會(huì)關(guān)注采用一些技術(shù)如隨機(jī)優(yōu)化進(jìn)一步提升成功率，其次關(guān)注加入準(zhǔn)入控制來(lái)限制需求過(guò)高傳輸數(shù)據(jù)量的BRR，最后關(guān)注即時(shí)調(diào)度中其它的周期性能如總延遲等。

參考文獻(xiàn)

[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]陳凡， 劉果， 李劍鋒， 等. 主要軟件定義網(wǎng)絡(luò)控制器的對(duì)比和分析[J]. 軟件， 2015， 36（6）： 97-102.

[4]李潔. 云平臺(tái)SDN 關(guān)鍵技術(shù)的研究與展望[J]. 軟件， 2015， 36（7）： 71-74.

[5]王天明， 符天. 基于擴(kuò)展OpenFlow流標(biāo)結(jié)構(gòu)增強(qiáng)SDN網(wǎng)絡(luò)安全性研究[J]. 軟件， 2018， 39（7）： 01-05.

[6]劉文. 基于大數(shù)據(jù)優(yōu)化網(wǎng)絡(luò)的安全性策略的研究[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]劉靜. 基于獨(dú)立生成樹(shù)的網(wǎng)絡(luò)多路徑傳輸方法研究[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.