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

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

2.成都大學 模式識別與智能信息處理四川省高校重點實驗室， 四川 成都 610106;3.四川大學 出國留學預備學院， 四川 成都 610065；4.成都大學 旅游與經濟管理學院， 四川 成都 610106)

基于對數(shù)障礙法的網絡流量管理算法

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

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

2.成都大學 模式識別與智能信息處理四川省高校重點實驗室， 四川 成都 610106;3.四川大學 出國留學預備學院， 四川 成都 610065；4.成都大學 旅游與經濟管理學院， 四川 成都 610106)

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

網絡流量；對數(shù)障礙法；擁塞

0 引 言

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

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

1 基于對數(shù)障礙函數(shù)的網絡效用最大化

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

subjecttoHx≤c

(1)

這是一個帶線性約束的凸優(yōu)化.對于式(1)，因為源在包損失后只能減小其速率，從而對貪心流的收斂性很差.此外，因為效用僅是基于吞吐量的，一些鏈路幾乎是滿容量運行，從而導致大的延遲，對于突發(fā)流量問題尤其突出，通過對偶分解可以得出其分布式解決方案，即考慮凸優(yōu)化問題，

subjecttoHx+r=c

(2)

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

subjecttoHx+r=c

(3)

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

subjecttoHx+r≤c

(4)

(5)

其中，

(6)

(7)

從而得到式(4)的對偶問題為，

(8)

subjecttoHx≤c

(9)

的解，且λ*是與之對應的Lagrange乘子.

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

(10)

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

對所有S有，

中西方因歷史和社會因素不同，英國偏向直線思維方式，我國則偏向曲線思維，因此中西方人認識事物的出發(fā)點不同，語言表達習慣也有所不同，這也是商務英語翻譯中易出問題的關鍵。

(11)

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

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

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

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

Step3.更新源S的路徑r的流速率，對于給定的價格向量λ(t)，由式(11)知，xs(t)是每個子問題的解當且僅當，

(12)

Step5.引入加權因子γ來避免在每次迭代中產生巨大的變化.實驗中，取γ=0.1.基于以上分析可得出源速率更新為，

(13)

(14)

Step8.重復Step3～Step7，直到網絡穩(wěn)定在最大流量運行.

Step9.算法結束.

3 數(shù)學仿真

本研究通過實際仿真環(huán)境中本算法與其他經典算法的最大流數(shù)據與性能對比來驗證算法的有效性.

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

圖1 3種算法仿真實驗對比

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

其次，本研究對3種算法的丟包情況進行了測試，圖2給出了90 s仿真時間內3種算法的丟包統(tǒng)計結果.

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

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

圖2 3種算法丟包比較

4 結 論

本研究首先通過對數(shù)障礙函數(shù)對計算機網絡中流量管理問題進行描述，采用適當?shù)牧髁抗芾聿呗钥梢燥@著提升網絡性能.基于對數(shù)障礙法的流量管理算法使用動態(tài)調整源發(fā)包速率，充分考慮節(jié)點底層排隊隊列情況以及節(jié)點擁塞度，使得網絡發(fā)包總速率可以維持在一個比較穩(wěn)定的最大流狀態(tài).實驗表明，本研究提出的算法對改善網絡最大流性能有一定的提升，對維護網絡的穩(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]魏娟,張麗,張洪,等.基于離散消失排隊的網絡最大流計算方法[J].計算機工程與設計,2016,37(10):2608-2612.

[7]趙姝,蘇建忠,劉倩倩,等.分層法求解網絡最大流的研究[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.

成都大學?；?2016XJZ14)、 模式識別與智能信息處理四川省高校重點實驗室2017開放課題(2017KFKT12)、 成都大學2016年國家級大學生創(chuàng)新訓練計劃(CDU-CX-2016013)、 四川省網絡智能信息處理實驗室開放課題(szjj2017-008)資助項目.

張 洪(1980 — )， 男， 博士， 副教授， 從事計算機網絡技術研究.