基于對(duì)數(shù)障礙法的網(wǎng)絡(luò)流量管理算法

張 洪， 王俊杰， 李牧澤， 胡 英， 劉 山， 馮大峰， 何 珠

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院， 四川 成都 610106；

2.成都大學(xué) 模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室， 四川 成都 610106;3.四川大學(xué) 出國(guó)留學(xué)預(yù)備學(xué)院， 四川 成都 610065；4.成都大學(xué) 旅游與經(jīng)濟(jì)管理學(xué)院， 四川 成都 610106)

基于對(duì)數(shù)障礙法的網(wǎng)絡(luò)流量管理算法

張 洪1，2， 王俊杰1， 李牧澤3， 胡 英4， 劉 山1， 馮大峰1， 何 珠1

(1.成都大學(xué) 信息科學(xué)與工程學(xué)院， 四川 成都 610106；

2.成都大學(xué) 模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室， 四川 成都 610106;3.四川大學(xué) 出國(guó)留學(xué)預(yù)備學(xué)院， 四川 成都 610065；4.成都大學(xué) 旅游與經(jīng)濟(jì)管理學(xué)院， 四川 成都 610106)

為了有效描述和管理計(jì)算機(jī)網(wǎng)絡(luò)流量問(wèn)題，提出一種基于對(duì)數(shù)障礙法和節(jié)點(diǎn)隊(duì)列的新算法.首先利用對(duì)數(shù)障礙函數(shù)分析影響網(wǎng)絡(luò)流量的關(guān)鍵因素，然后利用對(duì)數(shù)障礙法和節(jié)點(diǎn)隊(duì)列擁塞情況動(dòng)態(tài)調(diào)節(jié)網(wǎng)絡(luò)分布式發(fā)包速率，從而使網(wǎng)絡(luò)獲得最大的聚合效用.仿真實(shí)驗(yàn)結(jié)果顯示，算法具有較好的適應(yīng)性.

網(wǎng)絡(luò)流量；對(duì)數(shù)障礙法；擁塞

0 引 言

隨著現(xiàn)代網(wǎng)絡(luò)技術(shù)的快速發(fā)展，網(wǎng)絡(luò)擁塞已是一個(gè)不可避免的問(wèn)題，網(wǎng)絡(luò)擁塞會(huì)導(dǎo)致信息傳輸時(shí)間的顯著增加和網(wǎng)絡(luò)整體性能的下降.相關(guān)研究發(fā)現(xiàn)，網(wǎng)絡(luò)節(jié)點(diǎn)產(chǎn)生大量數(shù)據(jù)流，而并發(fā)數(shù)據(jù)流是導(dǎo)致網(wǎng)絡(luò)產(chǎn)生擁塞的主要原因.此外，網(wǎng)絡(luò)本身的一些屬性甚至?xí)?duì)網(wǎng)絡(luò)擁塞的產(chǎn)生與傳播起到助長(zhǎng)的作用，例如節(jié)點(diǎn)的容量、節(jié)點(diǎn)處理數(shù)據(jù)包的速度、通信鏈路的帶寬以及網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)等等.對(duì)此，如何進(jìn)行準(zhǔn)確的流量預(yù)測(cè)與合理的流量管理已成為現(xiàn)實(shí)網(wǎng)絡(luò)中一個(gè)亟待解決的問(wèn)題.

目前，在流量預(yù)測(cè)與管理上，研究者們普遍專(zhuān)注于對(duì)網(wǎng)絡(luò)最大流的研究，并取得了系列成果[1-7].其中，魏娟等[6]基于離散消失排隊(duì)和三維元胞自動(dòng)機(jī)提出了一種新的計(jì)算方法QCA，該算法具有較好的適應(yīng)性，但網(wǎng)絡(luò)穩(wěn)定性還有待提升；趙姝等[7]通過(guò)構(gòu)造原有網(wǎng)絡(luò)的層次，計(jì)算各相鄰節(jié)點(diǎn)之間的最大流，然后獲得整個(gè)網(wǎng)絡(luò)最大流估算，為大規(guī)模網(wǎng)絡(luò)中快速計(jì)算最大流的求解提出解決方法，實(shí)驗(yàn)也表明該算法能夠把近似誤差控制在1%左右，但由于該算法實(shí)現(xiàn)較為復(fù)雜，運(yùn)行時(shí)間會(huì)稍有增加.在此基礎(chǔ)上，本研究利用對(duì)數(shù)障礙函數(shù)法和基于節(jié)點(diǎn)隊(duì)列長(zhǎng)度提出一種新的網(wǎng)絡(luò)流量管理算法(logarithmic barrier and queuing method，LBQM)，并通過(guò)仿真實(shí)驗(yàn)對(duì)比研究該算法和其他算法的性能差異，以期獲得網(wǎng)絡(luò)效用最大化.

1 基于對(duì)數(shù)障礙函數(shù)的網(wǎng)絡(luò)效用最大化

單徑路由在當(dāng)今的互聯(lián)網(wǎng)被廣泛應(yīng)用，然而單徑路由將會(huì)限制系統(tǒng)的吞吐量.如果將數(shù)據(jù)流進(jìn)行靈活的分割，然后通過(guò)多條路徑發(fā)送，預(yù)期可以獲得更高的有效性和穩(wěn)健性.對(duì)于多徑路由，可用矩陣H的列來(lái)表示所有可用的路徑，這樣，多徑網(wǎng)絡(luò)效用最大化問(wèn)題可以表示為，

subjecttoHx≤c

(1)

這是一個(gè)帶線(xiàn)性約束的凸優(yōu)化.對(duì)于式(1)，因?yàn)樵丛诎鼡p失后只能減小其速率，從而對(duì)貪心流的收斂性很差.此外，因?yàn)樾в脙H是基于吞吐量的，一些鏈路幾乎是滿(mǎn)容量運(yùn)行，從而導(dǎo)致大的延遲，對(duì)于突發(fā)流量問(wèn)題尤其突出，通過(guò)對(duì)偶分解可以得出其分布式解決方案，即考慮凸優(yōu)化問(wèn)題，

subjecttoHx+r=c

(2)

其中，f是凸的、非減的二次可微函數(shù)，ω是效用和成本之間的權(quán)衡參數(shù).當(dāng)鏈路負(fù)載增加時(shí)，f給出更嚴(yán)重的約束，比如ey1/c1.通過(guò)對(duì)數(shù)障礙函數(shù)可以對(duì)式(2)進(jìn)一步優(yōu)化，以提高其最優(yōu)性和改善收斂性.

subjecttoHx+r=c

(3)

其中，ωl是與約束rl≥0，即yl≤cl，相聯(lián)系的障礙參數(shù).然而，如果直接求解式(3)，則因?yàn)槟繕?biāo)函數(shù)不是嚴(yán)格凹函數(shù)，從而對(duì)偶函數(shù)是不可微的，這種情況很難得到穩(wěn)定的速率控制算法.對(duì)此，本研究在目標(biāo)函數(shù)中引入與速率非負(fù)約束xr≥0相聯(lián)系的對(duì)數(shù)懲罰項(xiàng)，從而考慮，

subjecttoHx+r≤c

(4)

(5)

其中，

(6)

(7)

從而得到式(4)的對(duì)偶問(wèn)題為，

(8)

subjecttoHx≤c

(9)

的解，且λ*是與之對(duì)應(yīng)的Lagrange乘子.

基于式(8)，本研究利用對(duì)偶分解得到穩(wěn)定的分布式速率控制算法——投影梯度法，即，令β>0是常數(shù)步長(zhǎng)，則對(duì)所有l(wèi)∈L，有，

(10)

其中，對(duì)所有l(wèi)，有，

對(duì)所有S有，

中西方因歷史和社會(huì)因素不同，英國(guó)偏向直線(xiàn)思維方式，我國(guó)則偏向曲線(xiàn)思維，因此中西方人認(rèn)識(shí)事物的出發(fā)點(diǎn)不同，語(yǔ)言表達(dá)習(xí)慣也有所不同，這也是商務(wù)英語(yǔ)翻譯中易出問(wèn)題的關(guān)鍵。

(11)

式(11)表示源S在時(shí)刻t根據(jù)路徑擁塞水平極大化的凈效用.

2 基于對(duì)數(shù)障礙法的流量管理算法

本研究基于對(duì)數(shù)障礙法的流量管理算法步驟如下：

Step2.在式(10)和式(11)中忽略反饋延遲，對(duì)r∈s，源S需要對(duì)基于Tr更新發(fā)送速率，這里Tr是源S收到沿路徑r的所有鏈路的反饋需要時(shí)間.

Step3.更新源S的路徑r的流速率，對(duì)于給定的價(jià)格向量λ(t)，由式(11)知，xs(t)是每個(gè)子問(wèn)題的解當(dāng)且僅當(dāng)，

(12)

Step5.引入加權(quán)因子γ來(lái)避免在每次迭代中產(chǎn)生巨大的變化.實(shí)驗(yàn)中，取γ=0.1.基于以上分析可得出源速率更新為，

(13)

(14)

Step8.重復(fù)Step3～Step7，直到網(wǎng)絡(luò)穩(wěn)定在最大流量運(yùn)行.

Step9.算法結(jié)束.

3 數(shù)學(xué)仿真

本研究通過(guò)實(shí)際仿真環(huán)境中本算法與其他經(jīng)典算法的最大流數(shù)據(jù)與性能對(duì)比來(lái)驗(yàn)證算法的有效性.

首先，在NS2中建立網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，并且設(shè)置每個(gè)數(shù)據(jù)包大小為256 Byte，到達(dá)速率為2 000 Kibit/s，時(shí)延20 ms，各條鏈路容量為20 Mibit/s，各節(jié)點(diǎn)緩存容量為2 000 Kibit[6].同時(shí)將本研究所提方法與網(wǎng)絡(luò)單純形法(Simplex)及最短增載軌算法(distance-directed augmenting path，DDAP)應(yīng)用到仿真環(huán)境中進(jìn)行對(duì)比.在上述參數(shù)的設(shè)定下網(wǎng)絡(luò)穩(wěn)定運(yùn)行100 s，然后截取后50 s 3種算法獲得的網(wǎng)絡(luò)最大流數(shù)據(jù)，結(jié)果如圖1所示.

圖1 3種算法仿真實(shí)驗(yàn)對(duì)比

從圖1中可以看出，本研究提出的LBQM算法與實(shí)際統(tǒng)計(jì)的最大流最為接近，而Simplex算法預(yù)測(cè)結(jié)果誤差最大.經(jīng)過(guò)殘差分析，LBQM、DDAP和Simplex算法的誤差分別為10.32%、15.34%和20.16%.

其次，本研究對(duì)3種算法的丟包情況進(jìn)行了測(cè)試，圖2給出了90 s仿真時(shí)間內(nèi)3種算法的丟包統(tǒng)計(jì)結(jié)果.

從圖2可以看出，DDAP和Simplex算法的丟包波動(dòng)較為頻繁，而LBQM算法因采用了線(xiàn)性分形穩(wěn)定運(yùn)動(dòng)來(lái)降低數(shù)據(jù)包的突發(fā)性，使丟包性能得到了優(yōu)化.

從圖1和圖2的結(jié)果能夠看出，本研究提出的LBQM算法較DDAP和Simplex算法性能有較大提高，具有較好的適應(yīng)性.

圖2 3種算法丟包比較

4 結(jié) 論

本研究首先通過(guò)對(duì)數(shù)障礙函數(shù)對(duì)計(jì)算機(jī)網(wǎng)絡(luò)中流量管理問(wèn)題進(jìn)行描述，采用適當(dāng)?shù)牧髁抗芾聿呗钥梢燥@著提升網(wǎng)絡(luò)性能.基于對(duì)數(shù)障礙法的流量管理算法使用動(dòng)態(tài)調(diào)整源發(fā)包速率，充分考慮節(jié)點(diǎn)底層排隊(duì)隊(duì)列情況以及節(jié)點(diǎn)擁塞度，使得網(wǎng)絡(luò)發(fā)包總速率可以維持在一個(gè)比較穩(wěn)定的最大流狀態(tài).實(shí)驗(yàn)表明，本研究提出的算法對(duì)改善網(wǎng)絡(luò)最大流性能有一定的提升，對(duì)維護(hù)網(wǎng)絡(luò)的穩(wěn)定性有較大的幫助.

[1]Goldberg A V,Rao S.Beyondtheflowdecompositionbarrier[J].J ACM,1998,45(5):783-797.

[2]Ford L R,Fulkerson D R.Marimumflowthroughanetwork[J].Can J Math,1956,8(5):359-373.

[3]Dantzig G B.Applicationofthesimplexmethodtoatransportationproblem[C]//ActivityAnalysisandProductionandAllocation.New York，USA:Wiley,1951：359-373.

[4]Dinic E A.Algorithmforsolutionofaproblemofmaximumflowinnetworkswithpowerestimaton[J].Sov Math Dokl,1970,11(8):1277-1280.

[5]Edomonds J，Karp R M.Theoreticalimprovenmentsinalgorithmicefficiencyfornetworksflowproblems[J].J ACM,1972,19(2):248-264.

[6]魏娟,張麗,張洪,等.基于離散消失排隊(duì)的網(wǎng)絡(luò)最大流計(jì)算方法[J].計(jì)算機(jī)工程與設(shè)計(jì),2016,37(10):2608-2612.

[7]趙姝,蘇建忠,劉倩倩,等.分層法求解網(wǎng)絡(luò)最大流的研究[J].計(jì)算機(jī)研究與發(fā)展,2014,51(8):1845-1853.

Abstract:In order to describe and manage computer network flow effectively,this paper proposes a new method based on the logarithmic barrier and queuing method(logarithmic barrier and queuing method,LBQM).At first,this algorithm uses the logarithmic barrier function to analyze the key factors which influence the network flow,and then utilizes the logarithmic barrier method and the congestion condition of queuing to adjust the packet rate of distributed network dynamically,so that the network obtains the largest aggregation utility.The simulation experimental results show that LBQM has better adaptability.

Keywords:network flow;logarithmic barrier method;congestion

NetworkFlowManagementAlgorithmBasedonLogarithmicBarrierMethod

ZHANGHong1,2，WANGJunjie1，LIMuze3，HUYing4，LIUShan1，F(xiàn)ENGDafeng1，HEZhu1

(1.School of Information Science and Engineering， Chengdu University， Chengdu 610106, China;2.Key Laboratory of Pattern Recognition and Intelligent Information Processing, Chengdu University, Chengdu 610106, China;3.College of International Studies Education Ministry， Sichuan University, Chengdu 610065, China;4.School of Tourism, Economics and Management, Chengdu University, Chengdu 610106, China)

TP393.06

A

1004-5422(2017)03-0265-04

2017-06-20.

成都大學(xué)校基金(2016XJZ14)、 模式識(shí)別與智能信息處理四川省高校重點(diǎn)實(shí)驗(yàn)室2017開(kāi)放課題(2017KFKT12)、 成都大學(xué)2016年國(guó)家級(jí)大學(xué)生創(chuàng)新訓(xùn)練計(jì)劃(CDU-CX-2016013)、 四川省網(wǎng)絡(luò)智能信息處理實(shí)驗(yàn)室開(kāi)放課題(szjj2017-008)資助項(xiàng)目.

張 洪(1980 — )， 男， 博士， 副教授， 從事計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)研究.