即時調度中周期調度最大化的帶寬預留策略

摘 ?要： 越來越多的高性能網絡通過電路交換或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]。……