網(wǎng)絡(luò)資源的均衡化調(diào)度算法研究

元元+曹海英

摘 要： 針對(duì)傳統(tǒng)輪詢算法對(duì)網(wǎng)絡(luò)資源的均衡化調(diào)度存在負(fù)載均衡性差、網(wǎng)絡(luò)資源浪費(fèi)嚴(yán)重以及資源調(diào)度效果差的問題，提出一種新的網(wǎng)絡(luò)資源均衡化調(diào)度算法?；诰W(wǎng)絡(luò)資源的均衡化算法運(yùn)行過程，設(shè)計(jì)異構(gòu)集群的并行計(jì)算熵的計(jì)算矩陣，實(shí)現(xiàn)虛擬機(jī)的調(diào)度，對(duì)調(diào)度目標(biāo)的物理節(jié)點(diǎn)進(jìn)行分析，完成網(wǎng)絡(luò)資源多線程負(fù)載均衡調(diào)度。采用基于處理時(shí)間的網(wǎng)絡(luò)資源負(fù)載動(dòng)態(tài)均衡算法，對(duì)每個(gè)物理節(jié)點(diǎn)建立負(fù)載調(diào)度機(jī)制，使物理節(jié)點(diǎn)按照內(nèi)部最優(yōu)調(diào)度方式實(shí)施均衡調(diào)度，實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)資源的均衡化調(diào)度。實(shí)驗(yàn)結(jié)果表明，所提算法的調(diào)度效率高，且具有較高的負(fù)載均衡穩(wěn)定性，可以減少網(wǎng)絡(luò)資源的浪費(fèi)，增強(qiáng)網(wǎng)絡(luò)資源的調(diào)度效果。

關(guān)鍵詞： 網(wǎng)絡(luò)資源調(diào)度； 負(fù)載均衡； 云平臺(tái)； 物理節(jié)點(diǎn)； 均衡調(diào)度； 負(fù)載調(diào)度機(jī)制

中圖分類號(hào)： TN711?34； TN929 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2018）04?0034?03

Abstract： In allusion to the problems that there exist poor load balance， serious waste of network resources and poor resource scheduling efficiency in network resource equalization scheduling by using traditional polling algorithm， a new network resource equalization scheduling algorithm is proposed. The computing matrix of parallel computing entropy for heterogeneous cluster is designed on the basis of operation process of network resource equalization algorithm to realize the scheduling of fixed virtual machines. The physical nodes of scheduling targets are analyzed to complete the multithreading load balance scheduling of network resources. The dynamic network resource load balance algorithm based on processing time is adopted to establish load scheduling mechanism for each physical node， so that balanced scheduling of physical nodes can be implemented according to the internal optimal scheduling mode， and balanced scheduling of network resources realized. The experimental results show that the proposed algorithm has high scheduling efficiency and high load balancing stability， which can reduce the waste of network resources and enhance the scheduling effect of network resources.

Keywords： network resource scheduling； load balance； cloud platform； physical node； balanced scheduling； load scheduling mechanism

0 引 言

隨著互聯(lián)網(wǎng)通信技術(shù)的不斷發(fā)展，網(wǎng)絡(luò)資源的數(shù)據(jù)規(guī)模也逐漸變大，人們對(duì)網(wǎng)絡(luò)資源掌握的要求也越來越高，對(duì)網(wǎng)絡(luò)資源均衡化調(diào)度的研究關(guān)注度較高，加強(qiáng)網(wǎng)絡(luò)資源的綜合管理[1]，實(shí)現(xiàn)網(wǎng)絡(luò)資源均衡化調(diào)度成為互聯(lián)網(wǎng)發(fā)展的關(guān)鍵。傳統(tǒng)輪詢法對(duì)網(wǎng)絡(luò)資源的均衡化調(diào)度存在網(wǎng)絡(luò)資源利用率低、資源調(diào)度效果差的問題。面對(duì)該問題，本文提出一種新的網(wǎng)絡(luò)資源多線程負(fù)載均衡調(diào)度算法，以提高網(wǎng)絡(luò)資源均衡化調(diào)度效率，減少網(wǎng)絡(luò)資源的浪費(fèi)。

1 網(wǎng)絡(luò)資源的均衡化調(diào)度算法

1.1 基于云平臺(tái)網(wǎng)絡(luò)資源多線程負(fù)載均衡調(diào)度算法

在網(wǎng)絡(luò)資源的均衡化算法的研究過程中，先收集各個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的負(fù)載信息，并根據(jù)其攜帶的信息種類實(shí)施分類，根據(jù)已知節(jié)點(diǎn)樣本的負(fù)載特征值，對(duì)其余節(jié)點(diǎn)負(fù)載特征值進(jìn)行計(jì)算[2]，將計(jì)算出節(jié)點(diǎn)的特征值隨心跳包傳導(dǎo)至根節(jié)點(diǎn)，實(shí)現(xiàn)根節(jié)點(diǎn)對(duì)子節(jié)點(diǎn)的信息反饋?zhàn)饔?。本文在此基礎(chǔ)上建立云平臺(tái)網(wǎng)絡(luò)資源均衡化算法，采用該算法進(jìn)行網(wǎng)絡(luò)資源的均衡化調(diào)度時(shí)，需要利用云平臺(tái)網(wǎng)絡(luò)資源的均衡化原理、模型中的時(shí)間、費(fèi)用等參數(shù)?；谠破脚_(tái)網(wǎng)絡(luò)資源多線程負(fù)載均衡調(diào)度算法，設(shè)計(jì)了異構(gòu)集群的并行計(jì)算熵的計(jì)算矩陣，對(duì)虛擬機(jī)的調(diào)度[3]、調(diào)度目標(biāo)的物理節(jié)點(diǎn)及其判斷方式進(jìn)行定義，其定義步驟如下：

式中，[ptotali]為物理節(jié)點(diǎn)處理能力的量化體現(xiàn)。

用[?]表示網(wǎng)絡(luò)資源的采樣周期，對(duì)網(wǎng)絡(luò)資源的對(duì)應(yīng)并行熵進(jìn)行求值。若計(jì)算出的并行熵大于或等于負(fù)載閾值，判斷此時(shí)的網(wǎng)絡(luò)資源處于負(fù)載均衡狀態(tài)。

上述過程基于云平臺(tái)網(wǎng)絡(luò)資源均衡化模型的基本原理，以及異構(gòu)集群的并行計(jì)算熵的計(jì)算矩陣，實(shí)現(xiàn)虛擬機(jī)的調(diào)度，對(duì)調(diào)度目標(biāo)的物理節(jié)點(diǎn)進(jìn)行分析，完成網(wǎng)絡(luò)資源多線程負(fù)載均衡調(diào)度。endprint

1.2 基于處理時(shí)間的網(wǎng)絡(luò)資源負(fù)載動(dòng)態(tài)均衡算法

上文分析的網(wǎng)絡(luò)資源的均衡化調(diào)度算法，在物理節(jié)點(diǎn)處于數(shù)據(jù)繁忙狀態(tài)時(shí)，其向中央服務(wù)器進(jìn)行網(wǎng)絡(luò)資源負(fù)載信息提交過程中，負(fù)載信息反饋不及時(shí)[5]，會(huì)降低網(wǎng)絡(luò)資源均衡化的效率，因此需要建立一種基于處理時(shí)間的網(wǎng)絡(luò)資源負(fù)載動(dòng)態(tài)均衡算法，提高網(wǎng)絡(luò)資源均衡化效率。假設(shè)有[n]個(gè)物理節(jié)點(diǎn)參與計(jì)算，任務(wù)總量為[Ti1]，[Vi]和[Ti]分別為物理點(diǎn)的平均處理時(shí)間和運(yùn)行時(shí)間，對(duì)第一個(gè)物理節(jié)點(diǎn)實(shí)施均衡調(diào)度。將剩余物理節(jié)點(diǎn)按照內(nèi)部最優(yōu)調(diào)度方式實(shí)施均衡調(diào)度，對(duì)于物理節(jié)點(diǎn)[Nj（j≤n≤2）]，存在處理時(shí)間最大的節(jié)點(diǎn)[p1]，理論上[T1]和[Tp1]存在式（3）所示的函數(shù)關(guān)系，函數(shù)關(guān)系表達(dá)式為：

為了充分考慮網(wǎng)絡(luò)資源的有效利用，提高任務(wù)的并行能力[6]，調(diào)度發(fā)生的最合適時(shí)間應(yīng)為圖1中的臨界點(diǎn)上，其滿足[T1=Tpj]，并進(jìn)行一次負(fù)載均衡調(diào)度，必然存在某一個(gè)物理節(jié)點(diǎn)的運(yùn)行時(shí)間為[Tn（j≤n≤1）]，當(dāng)一個(gè)響應(yīng)時(shí)間最短的網(wǎng)絡(luò)資源調(diào)度方式，需要所有物理節(jié)點(diǎn)的共同參與[7]，不能間斷。為了讓網(wǎng)絡(luò)資源的均衡度更高，需要為每一個(gè)物理節(jié)點(diǎn)設(shè)置一個(gè)臨時(shí)變量[ti（n≤i≤1）]，初始值為0，記錄起始運(yùn)行時(shí)間，當(dāng)物理節(jié)點(diǎn)完成網(wǎng)絡(luò)資源調(diào)度任務(wù)后，用當(dāng)前時(shí)間減去起始時(shí)間即為任務(wù)用時(shí)[Δt]，其能精準(zhǔn)地反應(yīng)出目標(biāo)物理節(jié)點(diǎn)的網(wǎng)絡(luò)資源任務(wù)處理能力和負(fù)載均衡能力[8]，本文令[ti=ti+Δt]，[ti]表示目標(biāo)物理節(jié)點(diǎn)處理任務(wù)總用時(shí)。假設(shè)未完成的網(wǎng)絡(luò)資源任務(wù)按當(dāng)前處理速度繼續(xù)進(jìn)行，設(shè)當(dāng)前物理節(jié)點(diǎn)[i]已完成任務(wù)為[Nh]，提交完成任務(wù)量為[Nhi]，提交任務(wù)數(shù)為[Nsi]，該物理節(jié)點(diǎn)[i]網(wǎng)絡(luò)資源處理用時(shí)[Ti]為：

式中，[t0]為對(duì)物理節(jié)點(diǎn)預(yù)期的單位任務(wù)用時(shí)，通常設(shè)為0.01。從式（4）得到網(wǎng)絡(luò)資源的動(dòng)態(tài)均衡調(diào)整策略，從所有物理節(jié)點(diǎn)中選擇處理時(shí)間最短的物理節(jié)點(diǎn)，未進(jìn)行網(wǎng)絡(luò)資源任務(wù)分配時(shí)，[ti=0]。因此在網(wǎng)絡(luò)資源任務(wù)均衡調(diào)度初始狀態(tài)[9]，遵從物理節(jié)點(diǎn)的順序進(jìn)行任務(wù)提交。因?yàn)閇Ti]處于動(dòng)態(tài)變化中，因此該網(wǎng)絡(luò)資源負(fù)載動(dòng)態(tài)均衡算法能夠?qū)崿F(xiàn)對(duì)網(wǎng)絡(luò)資源的均衡調(diào)度，并降低網(wǎng)絡(luò)資源均衡化用時(shí)，提高網(wǎng)絡(luò)資源均衡化效率[10]。

2 實(shí)驗(yàn)分析

實(shí)驗(yàn)以國(guó)外某個(gè)制藥公司的網(wǎng)絡(luò)資源均衡調(diào)度過程為例，對(duì)比分析本文算法和傳統(tǒng)輪詢算法對(duì)該公司網(wǎng)絡(luò)資源的均衡調(diào)度效果，分別選取不同規(guī)模的實(shí)驗(yàn)數(shù)據(jù)，實(shí)驗(yàn)采用本文算法和傳統(tǒng)輪詢算法對(duì)網(wǎng)絡(luò)資源均衡調(diào)度過程中資源利用率和負(fù)載均衡穩(wěn)定性實(shí)施分析。圖2為兩種算法對(duì)網(wǎng)絡(luò)資源的利用率結(jié)果，圖3為兩種算法對(duì)負(fù)載均衡穩(wěn)定性分析結(jié)果。

從圖2和圖3可以分析得出，采用本文算法進(jìn)行網(wǎng)絡(luò)資源負(fù)載均衡調(diào)度的資源利用率和負(fù)載均衡穩(wěn)定性均要好于傳統(tǒng)輪詢算法，且本文算法隨著實(shí)驗(yàn)任務(wù)數(shù)量的擴(kuò)大，負(fù)載均衡的波動(dòng)較小，因?yàn)槔帽疚乃惴▽?shí)施網(wǎng)絡(luò)資源負(fù)載均衡時(shí)，采用云平臺(tái)網(wǎng)絡(luò)資源均衡化模型，得到云平臺(tái)環(huán)境下網(wǎng)絡(luò)資源任務(wù)所需要的時(shí)間、費(fèi)用和安全性函數(shù)，將多線程的負(fù)載均衡調(diào)度問題轉(zhuǎn)化為離線空間優(yōu)化問題，提高了網(wǎng)絡(luò)資源的利用率和負(fù)載均衡調(diào)度質(zhì)量。

3 結(jié) 論

本文設(shè)計(jì)的網(wǎng)絡(luò)資源的均衡化調(diào)度算法，能有效地對(duì)網(wǎng)絡(luò)資源實(shí)施均衡調(diào)度，提高網(wǎng)絡(luò)資源的利用效率，降低能量消耗，實(shí)現(xiàn)高效的網(wǎng)絡(luò)資源均衡調(diào)度。

參考文獻(xiàn)

[1] 張忠平，馮玉鵬，張雪楠.基于標(biāo)準(zhǔn)差及二次分配的啟發(fā)式網(wǎng)格資源調(diào)度算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2016，37（2）：259?263.

ZHANG Zhongping， FENG Yupeng， ZHANG Xuenan. Heuristic grid resource scheduling algorithm based on standard deviations and secondary distribution [J]. Journal of Chinese computer systems， 2016， 37（2）： 259?263.

[2] 李曉峰.云計(jì)算光纖網(wǎng)絡(luò)下的云資源調(diào)度方法研究與改進(jìn)[J].激光雜志，2016，37（5）：99?103.

LI Xiaofeng. Research and improvement of cloud resource scheduling method in cloud computing optical fiber network [J]. Laser journal， 2016， 37（5）： 99?103.

[3] 劉迅，畢遠(yuǎn)志.基于微粒群算法的工程網(wǎng)絡(luò)計(jì)劃多資源均衡優(yōu)化研究[J].科技管理研究，2014，34（11）：182?187.

LIU Xun， BI Yuanzhi. Multi?resources leveling optimization in project network planning based on PSO algorithm [J]. Science and technology management research， 2014， 34（11）： 182?187.

[4] 封岸松，王宏，張彥武.無線HART網(wǎng)絡(luò)節(jié)點(diǎn)變速率資源調(diào)度算法實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用，2016，42（3）：95?97.

FENG Ansong， WANG Hong， ZHANG Yanwu. Implementation of variable?rate resources scheduling algorithm of wireless HART node [J]. Application of electronic technique， 2016， 42（3）： 95?97.

[5] 王勇，劉美林，李凱，等.云環(huán)境下基于可靠性的均衡任務(wù)調(diào)度算法研究[J].計(jì)算機(jī)科學(xué)，2015，42（z1）：325?331.endprint

WANG Yong， LIU Meilin， LI Kai， et al. Reliability?based job scheduling algorithm in cloud computing [J]. Computer science， 2015， 42（S1）： 325?331.

[6] 宋玉堅(jiān)，葉春明，黃佐钘.多智能體布谷鳥算法的網(wǎng)絡(luò)計(jì)劃資源均衡優(yōu)化[J].計(jì)算機(jī)工程與應(yīng)用，2015，51（15）：56?61.

SONG Yujian， YE Chunming， HUANG Zuoxing. Multi?agent cuckoo search algorithm for resource leveling problem of network planning [J]. Computer engineering and applications， 2015， 51（15）： 56?61.

[7] 王鵬，黃焱，李坤，等.云計(jì)算集群相空間負(fù)載均衡度優(yōu)先調(diào)度算法研究[J].計(jì)算機(jī)研究與發(fā)展，2014，51（5）：1095?1107.

WANG Peng， HUANG Yan， LI Kun， et al. Load balancing degree first algorithm on phase space for cloud computing cluster [J]. Journal of computer research and development， 2014， 51（5）： 1095?1107.

[8] 何立華，張連營(yíng).基于資源波動(dòng)成本的工程項(xiàng)目資源均衡優(yōu)化[J].管理工程學(xué)報(bào)，2015，29（2）：167?174.

HE Lihua， ZHANG Lianying. Resource leveling optimization based on resource fluctuation cost in construction projects [J]. Journal of industrial engineering and engineering management， 2015， 29（2）： 167?174.

[9] 鄧志龍，段哲民，李劉濤.OpenStack環(huán)境下的資源動(dòng)態(tài)調(diào)度研究[J].西北工業(yè)大學(xué)學(xué)報(bào)，2016，34（4）：650?655.

DENG Zhilong， DUAN Zhemin， LI Liutao. Research of dynamic scheduling of resources under the environment of OpenStack [J]. Journal of Northwestern Polytechnical University， 2016， 34（4）： 650?655.

[10] ZHANG Peng. Simulation research on load balancing scheduling of cloud platform network [J]. Computer simulation， 2017， 34（6）： 372?375.

[11] 田春子，邵曉康.局域網(wǎng)限速狀態(tài)下的資源調(diào)度模型仿真[J].計(jì)算機(jī)仿真，2015，32（4）：248?251.

TIAN Chunzi， SHAO Xiaokang. Simulation of resource scheduling model under LAN speed limit state [J]. Computer simulation， 2015， 32（4）： 248?251.endprint