基于圖形分類的令牌桶流控算法

王 勇,葉明川

基于圖形分類的令牌桶流控算法

王 勇1,葉明川2

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

針對接入多維網關的異構網絡因信道速率不同而引起的網絡擁塞,在GPON技術的DBA算法和流控算法基礎上,提出一種基于預測和分級輪詢的動態帶寬分配算法,并結合基于圖形分類的令牌桶算法,通過對不同類型的服務進行動態帶寬分配,實現流量控制。實驗結果表明,該算法能有效地提高網關的服務質量。

DBA;預測輪詢;圖形分類;令牌桶

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

1 算法設計

DBA技術在GPON系統具有重要的作用[3-7],能動態分配上行的帶寬,提高系統的寬帶利用率、網絡時延,保證良好的服務質量。參照GPON系統中的動態帶寬分配機制,網關把帶寬分為固定帶寬、確保帶寬、非確保帶寬和盡力而為帶寬4個級別,其級別優先級如圖1所示。

圖1 網關中帶寬類型Fig.1 The bandwidth types in gateway

本算法4種類型的帶寬分別對應4種T-CONT類型,4種帶寬都可參與網關帶寬的動態分配,在每個更新周期Tu內被重新分配,以此提供網關的QoS、提高帶寬利用率。

在優先級別的設立機制上,網關把所有的單位服務劃分為4種服務類型:1)緊急控制命令業務,該業務擁有最高級別的優先級,擁有固定帶寬;2)即時數據請求業務,屬于次優先級,擁有確保帶寬和非確保帶寬;3)非緊急數據業務,擁有確保帶寬和非確保帶寬;4)普通數據請求業務,優先級別最低,擁有盡力而為帶寬。網關對這4種業務分別標記為A、B、C、D業務,優先級別依次降低。4種帶寬的服務類型如表1所示

表1 4種帶寬的服務類型Tab.1 Service for four bandwidth types

TSC-DBA算法對帶寬的分配,通過令牌桶算法實現,TSC算法為每一類服務設置一種形狀進行標記。這4種類型服務對應的形狀為:1)A類型對應的令牌形狀為正方形,該形狀的請求優先級最高,對應固定帶寬和確保帶寬;2)B類型對應的令牌形狀為三角形,該形狀擁有確保帶寬和非確保帶寬;3)C類型對應的令牌形狀為圓形,擁有的帶寬同B類型的帶寬,但是分配優先級低于B;4)D類型對應的令牌形狀為菱形,優先級最低,只擁有盡力而為帶寬,令牌不足時,最先被丟棄。TSC-DBA算法原理如圖2所示。

對于網關收到來自sink節點的請求,算法根據其sink節點請求的服務類型優先等級進行區分,給當前的請求標記不同的形狀。其標記含義如下:正方形代表優先級最高的請求,該請求直接使用A桶中的令牌,若A桶中令牌不足,可優先使用B桶中的令牌;三角形請求時,將使用B桶中的令牌,若B桶中令牌不足,優先使用C桶中的令牌;圓形請求時,使用C桶中的令牌,若C桶令牌不足,使用D桶中的令牌;菱形請求使用D桶中令牌,若D桶中令牌不足,則丟棄該請求。請求丟棄的順序為菱形、圓形、三角形、正方形,通過該種方式既可保證高優先級的業務的服務質量,又能充分利用網絡帶寬,從而保證網關的性能。

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

由于在傳統的DBA算法中,當前周期的網關數據決定下一個周期網關的帶寬分配策略,這樣會造成嚴重的滯后性。TSC-DBA算法引入了新的基于輪詢的流量預測機制,動態分配令牌桶中的桶深和令牌速率。網關計算本周期的流量請求大小,再關聯之前的所有周期實際轉發的數據量,根據算法的預測機制對即將到達的流量進行預測。網關定義為:

1)設i和j分別為sink節點和周期,取值范圍為1≤i≤N,N為sink節點或子網的個數。

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

3)設Pti,j為sink節點i在第j個周期內預測接收到的t類形狀的令牌請求數,Ntj為實際接收到的t類形狀的令牌請求數。

預測機制為:

其中:Ei,j-k為當前周期j之前的k個周期中請求數序列的算術平均值;ΔNti,j為Nti,j與Nti,j-1的差值; ω1,ω2,…,ωk為權重因子。經過多次實驗,權重因子為4階,依次為0.4、0.3、0.2、0.1。

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

1)Bti,j為sink節點在第j輪發送請求時,緩存區中還未轉發的t類令牌的數據數量。

2)Wr1,Wr2,Wr3,Wr4分別為當t=1,2,3,4時當前的令牌數量。

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

4)Rti,j、Gti,j分別為sink節點i在第j個周期請求和分配的t類形的令牌數量。

關于TSC-DBA算法的桶深和分配速率,遵循準則為:

1)網關給優先級最高的A桶分配固定的桶深和令牌速率,在算法上實現了A類型服務所需的固定帶寬。固定帶寬由正方形令牌類型組成,對時延的敏感程度最高。算法先預測在下一個周期即將到達的正方形類型的請求數據大小,然后再向網關報告。因此,A類的傳輸為:

更新剩余桶深和令牌數量,得

2)為確保帶寬分配對應的桶深和令牌數量,分成兩部分:三角形類型令牌桶的確保帶寬和圓形類型令牌桶的確保帶寬。

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

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

其中,Mmin為每個周期內sink的圓形令牌傳輸的最小確保帶寬。更新剩余桶深和令牌數量,得

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

更新剩余的桶深和令牌數量,得

4)為盡力而為帶寬分配對應的桶深和令牌數量。菱形令牌桶優先級最低,對時延最不敏感,因此,菱形令牌桶的分配在所有其他高優先級的業務沒有需求后才進行。如果最后還有剩余的令牌,就為菱形令牌桶分配令牌。

更新剩余的桶深和令牌數量,得

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

2 實驗仿真

實驗在流量控制的TSC-DBA算法中進行仿真,驗證TSC-DBA算法的正確性和優勢。本仿真程序使用C#語言編寫程序,構造虛擬流量源和虛擬交換機,并在虛擬交換機上實現TSC-DBA算法,監測統計流量源產生的數據包轉化情況。

通過不同的參數設置,進行多次實驗,如圖3所示。從圖3可看出,隨著數據包的發包數逐漸增加, TSC-DBA算法的請求響應成功率呈下降趨勢,但TSC-DBA算法下降緩和,說明TSC-DBA算法對請求響應成功率有所提升,間接地提高了整個多維網關的QoS,達到了預期目的。

圖3 整體請求成功率Fig.3 The overall request success ratio

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

圖4 分類業務丟包率Fig.4 Loss rate of classification business

3 結束語

結合DBA算法和流量整形[8-9],提出了基于形狀分類的令牌桶流控算法,仿真測試實現了動態帶寬的分配。仿真結果表明,算法能判斷業務請求的優先級別,并且分配所需要的帶寬,提高網關的服務質量。

[1] 尼四凱,王勇,鐘明旸.多維Web服務網關的高并發問題研究[J].微型機與應用,2014(7):34-36.

[2] 屈偉平.物聯網掀起新的信息技術革命浪潮[J].物流技術與應用,2009(11):42-45.

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

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

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

[6] 裘紫清,陳雪.一種基于改進AR模型的預測型GPON動態帶寬分配算法[C]//全國第十三次光纖通信暨第十四屆集成光學學術會議,2007:908-913.

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

[8] 陳彪.IP接入網絡面向QOS的分組調度和流量整形研究[D].浙江:浙江大學,2003:15-17.

[9] 涂文偉,張進,張興明.分級統籌分配令牌參數的流量整形算法[J].計算機應用,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

國家自然科學基金(61163058,61363006);廣西可信軟件重點實驗室開放基金(KX201306)

王勇(1964-),男,四川閬中人,教授,博士,研究方向為計算機網絡技術與應用、信息安全。E-mail:ywang@guet.edu.cn引文格式:王勇,葉明川.基于圖形分類的令牌桶流控算法[J].桂林電子科技大學學報,2015,35(5):391-394.