云計算下漏桶算法的改進研究

潘彩田　胡俊鵬

摘 要 漏桶算法廣泛運用于對傳輸業(yè)務流進行流量管理和資源分配。但是漏桶算法并不能減弱流量波動和負載增加時對網(wǎng)絡系統(tǒng)的惡性影響、彈性較弱。云計算分布式環(huán)境下，需要流量波動幅度更小的整流算法，本文提出了改進的漏桶算法，可以增強其對突發(fā)流量的承受能力。通過仿真實驗，證明改進的漏桶算法在服務性能上有所提高。

關鍵詞 漏桶算法；整流優(yōu)化；云計算；負載均衡

中圖分類號：TP311 文獻標識碼：A 文章編號：1671-7597（2014）16-0038-02

漏桶算法（Leaky Bucket）是云計算環(huán)境下實現(xiàn)流量整形（Traffic Shaping）、速度限制（Rate Limiting）時最常用的一種算法，它的主要目的是控制數(shù)據(jù)注入到網(wǎng)絡的速度，平滑網(wǎng)絡上的突發(fā)流量。漏桶算法平滑流量服務主要通過在輸出端組成輸出隊列[1]，對輸入報文以額定速率向外發(fā)送，也稱虛輸出排隊，突發(fā)流量可以被整形以便為網(wǎng)絡提供一個穩(wěn)定的流量。但傳統(tǒng)的漏桶算法存在缺陷，不能減弱流量波動和負載增加時對網(wǎng)絡的惡性影響[2]，基于漏桶的流量控制策略稍有不慎便會對數(shù)據(jù)安全、用戶體驗、經(jīng)濟效益都將產(chǎn)生巨大的影響；云計算中流量控制性能和安全的提升將會成為制約云計算發(fā)展的關鍵所在?；诖?，提出了通過變速標記手段進行改進的漏桶算法，提高了漏桶吞吐量，使漏桶性能有一定改進，Qos有所提高。

1 國內外研究現(xiàn)狀分析

目前國內外業(yè)界廣泛采用的單速三色漏桶算法，是目前最為通用和先進的算法。以下就基本算法、流行的算法和國內一種新型算法作了介紹。

1）基本漏桶算法。漏桶算法進行整流時，在輸入報文進行輸入時，如有足夠帶寬可提供服務，則讓其進入網(wǎng)絡，否則讓到來數(shù)據(jù)進入緩沖區(qū)排隊等待，具體設計時一般與令牌桶結合來達到限定額定速率的目的，主要用緩沖器和令牌發(fā)生器實

現(xiàn)[3]。令牌桶是網(wǎng)絡設備的內部存儲池，而令牌則是以給定速率填充令牌桶的虛擬信息包。每個到達的數(shù)據(jù)包分組塊都會從令牌桶中取走一定數(shù)量的令牌[4]。

2）單速三色標記算法（Single Rate Three Color Market，srTCM）。該算法也是基于漏桶的重要的流量整形算法，目前在業(yè)界中運用最為廣泛，如Cisco的Polices管制器即用到這項技術[5]。單速三色標記算法基于區(qū)分服務[6]理念，維持兩個桶，C（Commitied Brust Size，CBS）桶和E（Excess Brust Size，EBS）桶，二者以CIR（Commited Information Rate）產(chǎn)生令牌，數(shù)據(jù)報文到來先入C桶，后入E桶，兩桶均滿載后，新產(chǎn)生令牌一般情況下將被丟棄，數(shù)據(jù)包進入緩存器前，按照一定規(guī)則進行顏色標記，決定丟棄優(yōu)先級。一般根據(jù)長度區(qū)分到來的分組，標記為紅黃綠三色，綠色界定為長度小于CBS的尺寸，黃色為長度介于CBS和EBS之間的報文，最后紅色標記超過超額突發(fā)尺寸的報文。單速以報文尺寸為依據(jù)來進行分組，承諾桶資源不足時，采用備用超額E桶令牌，兩桶令牌均以用完時還能以預先支取方式發(fā)送報文，在處理穩(wěn)定速率下優(yōu)勢明顯。

另外也有雙速三色標記算法（Two Rate Three Color Market，trTCM），對數(shù)據(jù)分為CBS桶和PBS（Peak Brust Size）桶，突發(fā)峰值尺寸在以峰值更新信息速率，更適合處理大速率突發(fā)流量較大的情況。但是，雖然雙速在報文速率突發(fā)性能上做的更好，較于srTCM，具有丟包率較高、數(shù)據(jù)不夠平緩、混合轉發(fā)大小包時性能較差的缺點。

3）雙速漏桶監(jiān)管算法。雙速漏桶監(jiān)管主要是基于漏桶速率不夠靈活，不足以達到整流且充分利用資源的目的來設計的。算法思想主要是：在對輸入數(shù)據(jù)流判斷是否輸出前排隊，每次從隊首取額定數(shù)量的報文進行服務供給，當突發(fā)流量過大，達到可能導致?lián)砣呐R界值時即輸入數(shù)據(jù)總數(shù)大大超過可以提供的輸出速率時，進行變速加快傳輸，主要通過令牌控制器來實現(xiàn)。令牌控制器采用兩個令牌生成器，一個以R1速度生產(chǎn)令牌，另一個以R2速度生產(chǎn)令牌，其中R1

由此可以看出雙速漏桶對于監(jiān)管選擇的優(yōu)化，通過設置臨界變速器達到對流量容納量的增加，提高預期服務能力，同時其平均等待時間和數(shù)據(jù)丟失率上也有所改善。文獻證實，利用雙漏桶控制流量能有效避免網(wǎng)絡擁塞，降低網(wǎng)絡傳輸時延和丟包率[8]。

2 改進的漏桶算法

合理設置漏桶令牌更新是流控系統(tǒng)要解決的關鍵問題，過快會影響限速效果造成波動，過慢會使令牌處于欠缺狀態(tài)，浪費資源。故對漏桶令牌采用更恰當?shù)母略O置是改進算法和衡量性能的關鍵。同時，交換機和路由器控制著不同數(shù)據(jù)流的包的離開順序，所采用的交換結構、數(shù)據(jù)排隊位置和調度算法決定了網(wǎng)絡可以提供的Qos[9]。單速三色標記算法達到了對平流的要求，以兩層過濾來控制好了流量速度，適當加大時延來達到穩(wěn)定效果，并采用選擇性丟包，可以在大小包混合轉發(fā)時效率明顯改善，對云計算不同任務的適應性強，而雙速漏桶在時間延遲和數(shù)據(jù)包丟失上明顯改善，通過對二者適當整合可以達到更好的效果。

改進算法的核心思想為：對報文在輸入端進行排隊，設置兩個區(qū)分參數(shù)和兩個漏桶B桶和E桶，分別以額定速率（CBS和EBS）產(chǎn)生令牌，對到來數(shù)據(jù)首先進行三色標記，對于綠色數(shù)據(jù)包，在有令牌時提供網(wǎng)絡服務，對于黃色數(shù)據(jù)包，在B桶令牌充足時（如假定B桶令牌剩余數(shù)大于容量的二分之一），讓其從B桶通過，當B桶容量不足時，查看E桶令牌剩余數(shù)，如果充足，提高CBS速率至PBS，對于已經(jīng)處于PBS速率的B桶，盡量讓黃色數(shù)據(jù)包在B桶排隊，否則讓其進入E桶，E桶數(shù)據(jù)統(tǒng)一標記為紅色，以額定速率傳輸。E桶發(fā)生擁塞時自動采用RED丟包。這樣，對流量空閑時速率與流量緊張速率進行調整。

從算法描述圖可以看出在C桶速率變換時必須采用一定的控制策略，可選策略如試探性反饋調度策略，在B桶、E桶、緩沖區(qū)間建立通訊，根據(jù)通訊協(xié)議來實現(xiàn)消息傳遞。緩存器數(shù)據(jù)結構實現(xiàn)上，對于丟棄開關設置為環(huán)形結構向前丟包，在一定程度上抑制數(shù)據(jù)重發(fā)帶來的過載。

綜上，通過對桶容量和速率變換策略的調整，可以提高漏桶效率，增強其協(xié)調性，同時優(yōu)化丟棄策略，使遭受擁堵的可能性大大降低。但是這種改進算法還是無法應對突發(fā)流量極大時的過載問題。在云計算流量分流做的比較好的情況下，足以處理相關事務。

3 實驗仿真及結果

實驗仿真采用了偽隨機概率選擇規(guī)則，在突發(fā)流量數(shù)值選擇和數(shù)據(jù)包上采是用隨機生成，對三種算法進行對比，試驗結果證明了改進算法的優(yōu)越性。隨機生成20組數(shù)據(jù)進行突發(fā)流量的模擬，在大容量突發(fā)流量下，基本漏桶算法丟包率較高，雙速漏桶算法丟包率明顯降低，而改進漏桶算法丟包率比雙速監(jiān)管算法略低，基本漏桶算法最好的丟包率為47%，雙速監(jiān)管算法約為37%，改進算法的丟包率最低為36%。在數(shù)據(jù)容量越來越大的情況下，改進算法的性能逐漸體現(xiàn)出來，得到的平均丟包率最低，在普通流量下其優(yōu)勢較弱。根據(jù)數(shù)據(jù)傳輸速率、緩沖區(qū)消耗得出隨著緩沖區(qū)容量的增大，改進算法的服務能力提高

最快。

4 結束語

該算法對于突發(fā)流量進行兩次整流，可以達到較好效果，采用分層過濾，報文處理速度較快，數(shù)據(jù)丟失率明顯有所改善。由于對桶進行細分，B桶在占用和返還令牌上速率較快，可以在一定程度上應對大量突發(fā)流量，實驗結果證明了算法的效率和服務能力。但是基于分配而采用標記也會增加一定的資源消耗，對于漏桶算法做進一步改進還可以對輸出流進行更為嚴格的控制，加強對后續(xù)流入流量的預估，選定難以傳遞的數(shù)據(jù)快速丟棄，這樣會使網(wǎng)絡更為暢通，同時對于選擇規(guī)則可以根據(jù)時間進行變換，使丟包更為平衡、算法更加公平。

基金項目

本課題得到湖民族學院國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目（No.201210517019）資助。

參考文獻

[1]李印海，扈紅超，龐琳.基于CICQ的動態(tài)重路由交換機制[J].計算機工程，2010（21）.

[2]林豐成，竺紅衛(wèi)，李立.數(shù)字集成電路設計與技術[M].北京：科學出版社，2008.

[3]牛淼，蔣林.基于多令牌桶流量整形算法的研究與設計[J].微電子學與計算機，2011（11）.

[4]高永輝，蔣林.基于多令牌桶的組播擁塞控制[J].計算機技術與發(fā)展，2012（02）.

[5]劉振宇.基于令牌桶算法的網(wǎng)絡流量控制技術的研究與實現(xiàn)[D].內蒙古大學，2012.

[6]郝俊瑞，余少華.一種在區(qū)分服務網(wǎng)絡中新的三色標記器[J].計算機科學，2008（06）.

[7]張子紅.一種基于兩級許可的過載控制改進算法[J].通信技術，2009，03（42）.

[8]李捷，呂冰，韓志杰.基于混合預測模型VBR流擁塞控制機制[J].計算機工程，2008（12）.

[9]郭子榮，汪海鷹，曾華燊.一種可提供QoS保證的交換結構[J].計算機工程與應用，2010，46（12）.

[10]洪雁兵，王一軍，劉桂波，席斌.基于網(wǎng)絡演算的簇樹WSN性能上界分析[J].計算機工程與應用，2012，48（19）.endprint

從算法描述圖可以看出在C桶速率變換時必須采用一定的控制策略，可選策略如試探性反饋調度策略，在B桶、E桶、緩沖區(qū)間建立通訊，根據(jù)通訊協(xié)議來實現(xiàn)消息傳遞。緩存器數(shù)據(jù)結構實現(xiàn)上，對于丟棄開關設置為環(huán)形結構向前丟包，在一定程度上抑制數(shù)據(jù)重發(fā)帶來的過載。

綜上，通過對桶容量和速率變換策略的調整，可以提高漏桶效率，增強其協(xié)調性，同時優(yōu)化丟棄策略，使遭受擁堵的可能性大大降低。但是這種改進算法還是無法應對突發(fā)流量極大時的過載問題。在云計算流量分流做的比較好的情況下，足以處理相關事務。

3 實驗仿真及結果

實驗仿真采用了偽隨機概率選擇規(guī)則，在突發(fā)流量數(shù)值選擇和數(shù)據(jù)包上采是用隨機生成，對三種算法進行對比，試驗結果證明了改進算法的優(yōu)越性。隨機生成20組數(shù)據(jù)進行突發(fā)流量的模擬，在大容量突發(fā)流量下，基本漏桶算法丟包率較高，雙速漏桶算法丟包率明顯降低，而改進漏桶算法丟包率比雙速監(jiān)管算法略低，基本漏桶算法最好的丟包率為47%，雙速監(jiān)管算法約為37%，改進算法的丟包率最低為36%。在數(shù)據(jù)容量越來越大的情況下，改進算法的性能逐漸體現(xiàn)出來，得到的平均丟包率最低，在普通流量下其優(yōu)勢較弱。根據(jù)數(shù)據(jù)傳輸速率、緩沖區(qū)消耗得出隨著緩沖區(qū)容量的增大，改進算法的服務能力提高

最快。

4 結束語

該算法對于突發(fā)流量進行兩次整流，可以達到較好效果，采用分層過濾，報文處理速度較快，數(shù)據(jù)丟失率明顯有所改善。由于對桶進行細分，B桶在占用和返還令牌上速率較快，可以在一定程度上應對大量突發(fā)流量，實驗結果證明了算法的效率和服務能力。但是基于分配而采用標記也會增加一定的資源消耗，對于漏桶算法做進一步改進還可以對輸出流進行更為嚴格的控制，加強對后續(xù)流入流量的預估，選定難以傳遞的數(shù)據(jù)快速丟棄，這樣會使網(wǎng)絡更為暢通，同時對于選擇規(guī)則可以根據(jù)時間進行變換，使丟包更為平衡、算法更加公平。

基金項目

本課題得到湖民族學院國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目（No.201210517019）資助。

參考文獻

[1]李印海，扈紅超，龐琳.基于CICQ的動態(tài)重路由交換機制[J].計算機工程，2010（21）.

[2]林豐成，竺紅衛(wèi)，李立.數(shù)字集成電路設計與技術[M].北京：科學出版社，2008.

[3]牛淼，蔣林.基于多令牌桶流量整形算法的研究與設計[J].微電子學與計算機，2011（11）.

[4]高永輝，蔣林.基于多令牌桶的組播擁塞控制[J].計算機技術與發(fā)展，2012（02）.

[5]劉振宇.基于令牌桶算法的網(wǎng)絡流量控制技術的研究與實現(xiàn)[D].內蒙古大學，2012.

[6]郝俊瑞，余少華.一種在區(qū)分服務網(wǎng)絡中新的三色標記器[J].計算機科學，2008（06）.

[7]張子紅.一種基于兩級許可的過載控制改進算法[J].通信技術，2009，03（42）.

[8]李捷，呂冰，韓志杰.基于混合預測模型VBR流擁塞控制機制[J].計算機工程，2008（12）.

[9]郭子榮，汪海鷹，曾華燊.一種可提供QoS保證的交換結構[J].計算機工程與應用，2010，46（12）.

[10]洪雁兵，王一軍，劉桂波，席斌.基于網(wǎng)絡演算的簇樹WSN性能上界分析[J].計算機工程與應用，2012，48（19）.endprint

從算法描述圖可以看出在C桶速率變換時必須采用一定的控制策略，可選策略如試探性反饋調度策略，在B桶、E桶、緩沖區(qū)間建立通訊，根據(jù)通訊協(xié)議來實現(xiàn)消息傳遞。緩存器數(shù)據(jù)結構實現(xiàn)上，對于丟棄開關設置為環(huán)形結構向前丟包，在一定程度上抑制數(shù)據(jù)重發(fā)帶來的過載。

綜上，通過對桶容量和速率變換策略的調整，可以提高漏桶效率，增強其協(xié)調性，同時優(yōu)化丟棄策略，使遭受擁堵的可能性大大降低。但是這種改進算法還是無法應對突發(fā)流量極大時的過載問題。在云計算流量分流做的比較好的情況下，足以處理相關事務。

3 實驗仿真及結果

實驗仿真采用了偽隨機概率選擇規(guī)則，在突發(fā)流量數(shù)值選擇和數(shù)據(jù)包上采是用隨機生成，對三種算法進行對比，試驗結果證明了改進算法的優(yōu)越性。隨機生成20組數(shù)據(jù)進行突發(fā)流量的模擬，在大容量突發(fā)流量下，基本漏桶算法丟包率較高，雙速漏桶算法丟包率明顯降低，而改進漏桶算法丟包率比雙速監(jiān)管算法略低，基本漏桶算法最好的丟包率為47%，雙速監(jiān)管算法約為37%，改進算法的丟包率最低為36%。在數(shù)據(jù)容量越來越大的情況下，改進算法的性能逐漸體現(xiàn)出來，得到的平均丟包率最低，在普通流量下其優(yōu)勢較弱。根據(jù)數(shù)據(jù)傳輸速率、緩沖區(qū)消耗得出隨著緩沖區(qū)容量的增大，改進算法的服務能力提高

最快。

4 結束語

該算法對于突發(fā)流量進行兩次整流，可以達到較好效果，采用分層過濾，報文處理速度較快，數(shù)據(jù)丟失率明顯有所改善。由于對桶進行細分，B桶在占用和返還令牌上速率較快，可以在一定程度上應對大量突發(fā)流量，實驗結果證明了算法的效率和服務能力。但是基于分配而采用標記也會增加一定的資源消耗，對于漏桶算法做進一步改進還可以對輸出流進行更為嚴格的控制，加強對后續(xù)流入流量的預估，選定難以傳遞的數(shù)據(jù)快速丟棄，這樣會使網(wǎng)絡更為暢通，同時對于選擇規(guī)則可以根據(jù)時間進行變換，使丟包更為平衡、算法更加公平。

基金項目

本課題得到湖民族學院國家級大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目（No.201210517019）資助。

參考文獻

[1]李印海，扈紅超，龐琳.基于CICQ的動態(tài)重路由交換機制[J].計算機工程，2010（21）.

[2]林豐成，竺紅衛(wèi)，李立.數(shù)字集成電路設計與技術[M].北京：科學出版社，2008.

[3]牛淼，蔣林.基于多令牌桶流量整形算法的研究與設計[J].微電子學與計算機，2011（11）.

[4]高永輝，蔣林.基于多令牌桶的組播擁塞控制[J].計算機技術與發(fā)展，2012（02）.

[5]劉振宇.基于令牌桶算法的網(wǎng)絡流量控制技術的研究與實現(xiàn)[D].內蒙古大學，2012.

[6]郝俊瑞，余少華.一種在區(qū)分服務網(wǎng)絡中新的三色標記器[J].計算機科學，2008（06）.

[7]張子紅.一種基于兩級許可的過載控制改進算法[J].通信技術，2009，03（42）.

[8]李捷，呂冰，韓志杰.基于混合預測模型VBR流擁塞控制機制[J].計算機工程，2008（12）.

[9]郭子榮，汪海鷹，曾華燊.一種可提供QoS保證的交換結構[J].計算機工程與應用，2010，46（12）.

[10]洪雁兵，王一軍，劉桂波，席斌.基于網(wǎng)絡演算的簇樹WSN性能上界分析[J].計算機工程與應用，2012，48（19）.endprint