基于圖形分類(lèi)的令牌桶流控算法

王 勇,葉明川

基于圖形分類(lèi)的令牌桶流控算法

王 勇1,葉明川2

(1.桂林電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院,廣西桂林 541004; 2.桂林電子科技大學(xué)信息與通信學(xué)院,廣西桂林 541004)

針對(duì)接入多維網(wǎng)關(guān)的異構(gòu)網(wǎng)絡(luò)因信道速率不同而引起的網(wǎng)絡(luò)擁塞,在GPON技術(shù)的DBA算法和流控算法基礎(chǔ)上,提出一種基于預(yù)測(cè)和分級(jí)輪詢的動(dòng)態(tài)帶寬分配算法,并結(jié)合基于圖形分類(lèi)的令牌桶算法,通過(guò)對(duì)不同類(lèi)型的服務(wù)進(jìn)行動(dòng)態(tài)帶寬分配,實(shí)現(xiàn)流量控制。實(shí)驗(yàn)結(jié)果表明,該算法能有效地提高網(wǎng)關(guān)的服務(wù)質(zhì)量。

DBA;預(yù)測(cè)輪詢;圖形分類(lèi);令牌桶

多維嵌入式Web服務(wù)網(wǎng)關(guān)是為異構(gòu)網(wǎng)絡(luò)提供數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)的網(wǎng)關(guān),同時(shí),利用WebService技術(shù)可為用戶在互聯(lián)網(wǎng)上實(shí)現(xiàn)直接的控制和查詢[1]。為了提升系統(tǒng)的性能,流量控制機(jī)制的作用日趨明顯。如何防止網(wǎng)關(guān)可能遭到同一時(shí)間用戶大量訪問(wèn)而造成網(wǎng)關(guān)崩潰,以及由于各種異構(gòu)網(wǎng)絡(luò)的通信速率差距太大而造成網(wǎng)絡(luò)擁塞、數(shù)據(jù)丟失[2],成了亟需解決的問(wèn)題。針對(duì)以上情況,提出了基于圖形分類(lèi)的令牌桶流控算法。該算法針對(duì)即將流入子網(wǎng)內(nèi)的請(qǐng)求數(shù)據(jù)進(jìn)行分類(lèi)調(diào)度,創(chuàng)建了一個(gè)4種形狀的四速令牌桶,把不同的請(qǐng)求分成4類(lèi),分別放到4個(gè)速率和桶深不同的子桶內(nèi),令牌桶的桶深、速率及漏桶的大小閾值定期更新,對(duì)不同類(lèi)型的業(yè)務(wù)請(qǐng)求進(jìn)行動(dòng)態(tài)帶寬的分配。

1 算法設(shè)計(jì)

DBA技術(shù)在GPON系統(tǒng)具有重要的作用[3-7],能動(dòng)態(tài)分配上行的帶寬,提高系統(tǒng)的寬帶利用率、網(wǎng)絡(luò)時(shí)延,保證良好的服務(wù)質(zhì)量。參照GPON系統(tǒng)中的動(dòng)態(tài)帶寬分配機(jī)制,網(wǎng)關(guān)把帶寬分為固定帶寬、確保帶寬、非確保帶寬和盡力而為帶寬4個(gè)級(jí)別,其級(jí)別優(yōu)先級(jí)如圖1所示。

圖1 網(wǎng)關(guān)中帶寬類(lèi)型Fig.1 The bandwidth types in gateway

本算法4種類(lèi)型的帶寬分別對(duì)應(yīng)4種T-CONT類(lèi)型,4種帶寬都可參與網(wǎng)關(guān)帶寬的動(dòng)態(tài)分配,在每個(gè)更新周期Tu內(nèi)被重新分配,以此提供網(wǎng)關(guān)的QoS、提高帶寬利用率。

在優(yōu)先級(jí)別的設(shè)立機(jī)制上,網(wǎng)關(guān)把所有的單位服務(wù)劃分為4種服務(wù)類(lèi)型:1)緊急控制命令業(yè)務(wù),該業(yè)務(wù)擁有最高級(jí)別的優(yōu)先級(jí),擁有固定帶寬;2)即時(shí)數(shù)據(jù)請(qǐng)求業(yè)務(wù),屬于次優(yōu)先級(jí),擁有確保帶寬和非確保帶寬;3)非緊急數(shù)據(jù)業(yè)務(wù),擁有確保帶寬和非確保帶寬;4)普通數(shù)據(jù)請(qǐng)求業(yè)務(wù),優(yōu)先級(jí)別最低,擁有盡力而為帶寬。網(wǎng)關(guān)對(duì)這4種業(yè)務(wù)分別標(biāo)記為A、B、C、D業(yè)務(wù),優(yōu)先級(jí)別依次降低。4種帶寬的服務(wù)類(lèi)型如表1所示

表1 4種帶寬的服務(wù)類(lèi)型Tab.1 Service for four bandwidth types

TSC-DBA算法對(duì)帶寬的分配,通過(guò)令牌桶算法實(shí)現(xiàn),TSC算法為每一類(lèi)服務(wù)設(shè)置一種形狀進(jìn)行標(biāo)記。這4種類(lèi)型服務(wù)對(duì)應(yīng)的形狀為:1)A類(lèi)型對(duì)應(yīng)的令牌形狀為正方形,該形狀的請(qǐng)求優(yōu)先級(jí)最高,對(duì)應(yīng)固定帶寬和確保帶寬;2)B類(lèi)型對(duì)應(yīng)的令牌形狀為三角形,該形狀擁有確保帶寬和非確保帶寬;3)C類(lèi)型對(duì)應(yīng)的令牌形狀為圓形,擁有的帶寬同B類(lèi)型的帶寬,但是分配優(yōu)先級(jí)低于B;4)D類(lèi)型對(duì)應(yīng)的令牌形狀為菱形,優(yōu)先級(jí)最低,只擁有盡力而為帶寬,令牌不足時(shí),最先被丟棄。TSC-DBA算法原理如圖2所示。

對(duì)于網(wǎng)關(guān)收到來(lái)自sink節(jié)點(diǎn)的請(qǐng)求,算法根據(jù)其sink節(jié)點(diǎn)請(qǐng)求的服務(wù)類(lèi)型優(yōu)先等級(jí)進(jìn)行區(qū)分,給當(dāng)前的請(qǐng)求標(biāo)記不同的形狀。其標(biāo)記含義如下:正方形代表優(yōu)先級(jí)最高的請(qǐng)求,該請(qǐng)求直接使用A桶中的令牌,若A桶中令牌不足,可優(yōu)先使用B桶中的令牌;三角形請(qǐng)求時(shí),將使用B桶中的令牌,若B桶中令牌不足,優(yōu)先使用C桶中的令牌;圓形請(qǐng)求時(shí),使用C桶中的令牌,若C桶令牌不足,使用D桶中的令牌;菱形請(qǐng)求使用D桶中令牌,若D桶中令牌不足,則丟棄該請(qǐng)求。請(qǐng)求丟棄的順序?yàn)榱庑?、圓形、三角形、正方形,通過(guò)該種方式既可保證高優(yōu)先級(jí)的業(yè)務(wù)的服務(wù)質(zhì)量,又能充分利用網(wǎng)絡(luò)帶寬,從而保證網(wǎng)關(guān)的性能。

圖2 TSC-DBA算法原理Fig.2 Principle of TSC-DBA algorithm

由于在傳統(tǒng)的DBA算法中,當(dāng)前周期的網(wǎng)關(guān)數(shù)據(jù)決定下一個(gè)周期網(wǎng)關(guān)的帶寬分配策略,這樣會(huì)造成嚴(yán)重的滯后性。TSC-DBA算法引入了新的基于輪詢的流量預(yù)測(cè)機(jī)制,動(dòng)態(tài)分配令牌桶中的桶深和令牌速率。網(wǎng)關(guān)計(jì)算本周期的流量請(qǐng)求大小,再關(guān)聯(lián)之前的所有周期實(shí)際轉(zhuǎn)發(fā)的數(shù)據(jù)量,根據(jù)算法的預(yù)測(cè)機(jī)制對(duì)即將到達(dá)的流量進(jìn)行預(yù)測(cè)。網(wǎng)關(guān)定義為:

1)設(shè)i和j分別為sink節(jié)點(diǎn)和周期,取值范圍為1≤i≤N,N為sink節(jié)點(diǎn)或子網(wǎng)的個(gè)數(shù)。

2)設(shè)t為令牌的形狀類(lèi)型,t∈{1,2,3,4},分別為正方形、三角形、圓形和菱形類(lèi)型的令牌。

3)設(shè)Pti,j為sink節(jié)點(diǎn)i在第j個(gè)周期內(nèi)預(yù)測(cè)接收到的t類(lèi)形狀的令牌請(qǐng)求數(shù),Ntj為實(shí)際接收到的t類(lèi)形狀的令牌請(qǐng)求數(shù)。

預(yù)測(cè)機(jī)制為:

其中:Ei,j-k為當(dāng)前周期j之前的k個(gè)周期中請(qǐng)求數(shù)序列的算術(shù)平均值;ΔNti,j為Nti,j與Nti,j-1的差值; ω1,ω2,…,ωk為權(quán)重因子。經(jīng)過(guò)多次實(shí)驗(yàn),權(quán)重因子為4階,依次為0.4、0.3、0.2、0.1。

為了更好地描述TSC-DBA算法,先定義以下幾個(gè)概念:

1)Bti,j為sink節(jié)點(diǎn)在第j輪發(fā)送請(qǐng)求時(shí),緩存區(qū)中還未轉(zhuǎn)發(fā)的t類(lèi)令牌的數(shù)據(jù)數(shù)量。

2)Wr1,Wr2,Wr3,Wr4分別為當(dāng)t=1,2,3,4時(shí)當(dāng)前的令牌數(shù)量。

3)Wtotal為可分配的令牌總數(shù)。

4)Rti,j、Gti,j分別為sink節(jié)點(diǎn)i在第j個(gè)周期請(qǐng)求和分配的t類(lèi)形的令牌數(shù)量。

關(guān)于TSC-DBA算法的桶深和分配速率,遵循準(zhǔn)則為:

1)網(wǎng)關(guān)給優(yōu)先級(jí)最高的A桶分配固定的桶深和令牌速率,在算法上實(shí)現(xiàn)了A類(lèi)型服務(wù)所需的固定帶寬。固定帶寬由正方形令牌類(lèi)型組成,對(duì)時(shí)延的敏感程度最高。算法先預(yù)測(cè)在下一個(gè)周期即將到達(dá)的正方形類(lèi)型的請(qǐng)求數(shù)據(jù)大小,然后再向網(wǎng)關(guān)報(bào)告。因此,A類(lèi)的傳輸為:

更新剩余桶深和令牌數(shù)量,得

2)為確保帶寬分配對(duì)應(yīng)的桶深和令牌數(shù)量,分成兩部分:三角形類(lèi)型令牌桶的確保帶寬和圓形類(lèi)型令牌桶的確保帶寬。

a)在本算法中,三角形類(lèi)型令牌中的確保帶寬部分的分配有著和正方形類(lèi)型令牌相同的預(yù)測(cè)方法。因此,B類(lèi)型的傳輸為:

b)分配圓形令牌桶中的確保帶寬,圓形令牌桶的確保帶寬優(yōu)先級(jí)小于三角形令牌桶,因此,圓形令牌桶的傳輸為:

其中,Mmin為每個(gè)周期內(nèi)sink的圓形令牌傳輸?shù)淖钚〈_保帶寬。更新剩余桶深和令牌數(shù)量,得

3)為非確保帶寬分配對(duì)應(yīng)的桶深和令牌,由圓形令牌桶組成,只有在分配完了確保帶寬需求的令牌數(shù)量,然后再檢測(cè)剩余的令牌數(shù),如果還有剩余,才為非確保帶寬分配所需求的令牌數(shù)量。即-Mmin),t=3時(shí),

更新剩余的桶深和令牌數(shù)量,得

4)為盡力而為帶寬分配對(duì)應(yīng)的桶深和令牌數(shù)量。菱形令牌桶優(yōu)先級(jí)最低,對(duì)時(shí)延最不敏感,因此,菱形令牌桶的分配在所有其他高優(yōu)先級(jí)的業(yè)務(wù)沒(méi)有需求后才進(jìn)行。如果最后還有剩余的令牌,就為菱形令牌桶分配令牌。

更新剩余的桶深和令牌數(shù)量,得

5)若Wr4＞0,則從步驟3)開(kāi)始進(jìn)行第2次桶深和令牌分配,如此循環(huán),直至分配完畢,退出循環(huán)。

2 實(shí)驗(yàn)仿真

實(shí)驗(yàn)在流量控制的TSC-DBA算法中進(jìn)行仿真,驗(yàn)證TSC-DBA算法的正確性和優(yōu)勢(shì)。本仿真程序使用C#語(yǔ)言編寫(xiě)程序,構(gòu)造虛擬流量源和虛擬交換機(jī),并在虛擬交換機(jī)上實(shí)現(xiàn)TSC-DBA算法,監(jiān)測(cè)統(tǒng)計(jì)流量源產(chǎn)生的數(shù)據(jù)包轉(zhuǎn)化情況。

通過(guò)不同的參數(shù)設(shè)置,進(jìn)行多次實(shí)驗(yàn),如圖3所示。從圖3可看出,隨著數(shù)據(jù)包的發(fā)包數(shù)逐漸增加, TSC-DBA算法的請(qǐng)求響應(yīng)成功率呈下降趨勢(shì),但TSC-DBA算法下降緩和,說(shuō)明TSC-DBA算法對(duì)請(qǐng)求響應(yīng)成功率有所提升,間接地提高了整個(gè)多維網(wǎng)關(guān)的QoS,達(dá)到了預(yù)期目的。

圖3 整體請(qǐng)求成功率Fig.3 The overall request success ratio

在如圖4所示的分類(lèi)業(yè)務(wù)曲線中,隨著請(qǐng)求數(shù)據(jù)包的增加,A、B、C、D四種類(lèi)型的丟包率都有所增加,但是優(yōu)先級(jí)別最高的A類(lèi)數(shù)據(jù)包的丟包率增加比較緩慢,說(shuō)明之前分析的結(jié)果吻合,TSC-DBA算法能保證重要請(qǐng)求業(yè)務(wù)的QOS,對(duì)于低優(yōu)先級(jí)的請(qǐng)求只是盡力而為而已,只有滿足了最高優(yōu)先級(jí)的請(qǐng)求后才給其分配桶深和令牌。

圖4 分類(lèi)業(yè)務(wù)丟包率Fig.4 Loss rate of classification business

3 結(jié)束語(yǔ)

結(jié)合DBA算法和流量整形[8-9],提出了基于形狀分類(lèi)的令牌桶流控算法,仿真測(cè)試實(shí)現(xiàn)了動(dòng)態(tài)帶寬的分配。仿真結(jié)果表明,算法能判斷業(yè)務(wù)請(qǐng)求的優(yōu)先級(jí)別,并且分配所需要的帶寬,提高網(wǎng)關(guān)的服務(wù)質(zhì)量。

[1] 尼四凱,王勇,鐘明旸.多維Web服務(wù)網(wǎng)關(guān)的高并發(fā)問(wèn)題研究[J].微型機(jī)與應(yīng)用,2014(7):34-36.

[2] 屈偉平.物聯(lián)網(wǎng)掀起新的信息技術(shù)革命浪潮[J].物流技術(shù)與應(yīng)用,2009(11):42-45.

[3] 張勇,朱祥華.基于周期輪詢的GPON上行鏈路動(dòng)態(tài)帶寬分配算法[J].現(xiàn)代傳輸,2006,32(4):75-79.

[4] 劉楊.GPON系統(tǒng)中一種高性能的DBA分配算法研究[D].上海:復(fù)旦大學(xué),2011:23-25.

[5] 孫捷,杜江,譚毅,等.GPON中一種二端動(dòng)態(tài)帶寬分配算法的設(shè)計(jì)與分析[J].光通信技術(shù),2009,33(4):15-17.

[6] 裘紫清,陳雪.一種基于改進(jìn)AR模型的預(yù)測(cè)型GPON動(dòng)態(tài)帶寬分配算法[C]//全國(guó)第十三次光纖通信暨第十四屆集成光學(xué)學(xué)術(shù)會(huì)議,2007:908-913.

[7] 雷震洲.千兆比無(wú)源光網(wǎng)——GPON[J].電信網(wǎng)技術(shù), 2003,29(8):12-15.

[8] 陳彪.IP接入網(wǎng)絡(luò)面向QOS的分組調(diào)度和流量整形研究[D].浙江:浙江大學(xué),2003:15-17.

[9] 涂文偉,張進(jìn),張興明.分級(jí)統(tǒng)籌分配令牌參數(shù)的流量整形算法[J].計(jì)算機(jī)應(yīng)用,2006,26(9):21-24.

編輯:梁王歡

A token bucket flow control algorithm based on pattern classification

Wang Yong1,Ye Mingchuan2
(1.School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,China; 2.School of Information and Communication Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

Aiming at network congestion of heterogeneous network accessing to multidimensional gateway caused by different channel rate,a dynamic bandwidth allocation algorithm based on prediction and grading polling is proposed according to DBA and flow control algorithm of GPON technology.Combining token bucket algorithm based on graphics categorization, flow control is realized by dynamic bandwidth allocation on different types of services.Experimental results show that the algorithm can improve effectively service quality of gateway.

DBA;prediction of polling;pattern classification;token bucket

TP393

A

1673-808X(2015)05-0391-04

2015-04-20

國(guó)家自然科學(xué)基金(61163058,61363006);廣西可信軟件重點(diǎn)實(shí)驗(yàn)室開(kāi)放基金(KX201306)

王勇(1964-),男,四川閬中人,教授,博士,研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù)與應(yīng)用、信息安全。E-mail:ywang@guet.edu.cn引文格式:王勇,葉明川.基于圖形分類(lèi)的令牌桶流控算法[J].桂林電子科技大學(xué)學(xué)報(bào),2015,35(5):391-394.