一種基於主副桶的高精度令牌桶限速的方法
2023-05-30 22:39:26 1
專利名稱：一種基於主副桶的高精度令牌桶限速的方法
技術領域：
本發明涉及網絡流量控制領域，尤其涉及一種基於主副桶的高精度令牌桶限速的方法。
背景技術：
QoS (Quality of Service,服務質量)中的流量監管(Traffic Policing)就是對流量進行控制，通過監督進入網絡埠的流量速率，對超出部分的流量丟棄或是延遲發送，使進入埠的流量被限制在一個合理的範圍之內。QoS流量監管功能是採用令牌桶(Token-Bucket)機制進行的。令牌桶是指網絡設備的內部存儲池，而令牌則是指以給定速率填充令牌桶的虛擬信息包。交換機在接收每一幀數據時都將添加一個令牌到令牌桶中，但這個令牌桶底部有一個孔，不斷地按照指定的速度(即平均通信速率，單位為b/s)從桶中刪除令牌(相當於一個水桶的上邊連接一根進水管，而下邊又連接一根連接到用水的地方的出水管)。在每次向令牌桶中添加新的令牌時，交換機都會檢查令牌桶中是否有足夠容量(相當於向水桶中加水前，先要檢查是桶內是否已滿)，如果沒有足夠的空間，新添加的令牌將被標記為不符規定的包，將其丟棄或緩存(就相當於如果當前水桶滿了，但進水管還要進水，那麼就是讓這些水流到桶外，或者把這些水用其它容器先裝起來，等水桶中不滿時再倒進去)，整個令牌桶的基本工作原理如圖1來表示。令牌桶填滿的時間長短是由令牌桶深度(類似於水桶的深度，單位為bit)、令牌漏出速率(類似桶出水管的水速)和超過平均速率的突發通信流(類似於進水管突發的急速水流)持續的時間三個方面共同決定的。令牌桶的大小利用突發時長上限乘以點對點傳輸時的幀數限制得出(也就類似突發水流持續的時間*突發水流的流速)。如果突發時間比較短，令牌桶不會溢出，在通信流上不會發生行為。但是，如果突發時間比較長，並且速率比較高，令牌桶將溢出，這時將對突發過程中的幀採取相應的流監管策略行為。
令牌桶算法是網絡流量整形(Traffic Shaping)和速率限制(Rate Limiting)中最常使用的一種算法。典型情況下，令牌桶算法用來控制發送到網絡上的數據的數目，並允許突發數據的發送。當網絡設備衡量流量是否超過額定帶寬時，需要查看令牌桶，而令牌桶中會放置一定數量的令牌，一個令牌允許接口發送或接收Ibit數據，當接口通過Ibit數據後，同時也要從桶中移除一個令牌。令牌桶按用戶設定的速度向桶中放置令牌，如果令牌桶中有足夠的令牌可以用來發送報文，則報文直接被繼續發送下去，同時令牌桶中的令牌量按報文的長度做相應的減少。當桶裡沒有令牌的時候，任何流量都被視為超過額定帶寬，只有當桶中有令牌時，數據才可以通過接口。令牌桶中的令牌不僅僅可以被移除，同樣也可以往裡添加，所以為了保證接口隨時有數據通過，就必須不停地往桶裡加令牌，由此可見，往桶裡加令牌的速度，就決定了數據通過接口的速度。因此，可以通過控制往令牌桶裡加令牌的速度從而控制用戶流量的帶寬。但是在現有技術中，當令牌桶限制流量值較大時會產生精度低、誤差大的問題。
發明內容
(一)要解決的技術問題針對上述缺陷，本發明要解決的技術問題是如何避免限速值精度低、誤差大的問題，增大令牌桶的限速值範圍。(二)技術方案為解決上述問題，本發明提供了一種使用主副桶的高精度令牌桶限速的方法，所述方法具體包括:S1:將所述令牌桶分為主桶和副桶，並分別計算主桶限速值和副桶限速值； S2:根據所述令牌桶中總的令牌數量和所述主桶限速值計算所述主桶的一個單位限速值對應的令牌數量，根據所述令牌桶中總的令牌數量和所述副桶限速值計算所述副桶的一個單位限速值對應的令牌數量；S3:當有報文需要處理時，首先從給所述副桶中提取令牌進行報文處理，當所述副桶中的令牌數量不足時向所述主桶借用令牌將所述副桶填滿再進行報文處理。進一步地，所述計算主桶限速值和副桶限速值具體包括:根據所述令牌桶的總限速值對精度取餘得到所述副桶限速值，根據所述令牌桶的總限速值和所述精度相除得到所述主桶限速值。進一步地，在所述令牌桶計算之前還包括:
對所述主桶限速值進行放大，將所述主桶限速值放大到與所述副桶限速值相同的數量級，即將所述主桶限速值乘以所述精度得到放大的主桶限速值。進一步地，當所述主桶中令牌數量也不足時才達到令牌桶的總限速值。(三)有益效果本發明提供了一種基於主副桶的高精度令牌桶限速的方法，通過設置主桶和副桶，依靠副桶提高限速值精度，避免限速值大時精度低、誤差大，增大了令牌桶限速值的範圍，實現了全範圍的高精度限速。
圖1為現有技術中令牌桶的基本工作原理圖2為本發明實施例中的一種基於主副桶的高精度令牌桶限速的方法的步驟流程圖。
具體實施例方式下面結合附圖和實施例，對本發明的具體實施方式
作進一步詳細描述。以下實施例用於說明本發明，但不用來限制本發明的範圍。本發明實施例中提供了一種基於主副桶的高精度令牌桶限速的方法，步驟流程如圖2所示，具體包括以下步驟:步驟S1:將令牌桶分為主桶和副桶，並分別計算主桶限速值和副桶限速值。在令牌桶算法中，令牌桶最關鍵的就是令牌的使用和填充，與現有技術不同的是本實施例中就是將令牌桶分為了主桶和副桶兩個令牌桶，其中副桶用來控制小流量的精度，主桶用來控制大流量的精度。其中，計算主桶限速值和副桶限速值具體包括:根據令牌桶的總限速值X對精度P取餘得到副桶限速值m，即m=x%p ;根據令牌桶的總限速值X和精度P相除得到主桶限速值n，即n=x/p。在令牌桶計算之前還包括:對主桶限速值η進行放大，將主桶限速值η放大到與副桶限速值m相同的數量級，即將主桶限速值η乘以精度P得到放大的主桶限速值n&±!g =n*p。步驟S2:根據令牌桶中總的令牌數量y和主桶限速值計算主桶的一個單位限速值對應的令牌數量yl，yl=y/n 根據令牌桶中總的令牌數量y和副桶限速值m計算副桶的一個單位限速值對應的令牌數量y2, y2=y/m。步驟S3:當有報文需要處理時，首先從給副桶中提取令牌進行報文處理，當副桶中的令牌數量不足時向主桶借用令牌將副桶填滿再進行報文處理。其中副桶需要向主桶借用(m/n)*y個令牌將副桶填滿。只有當主桶中令牌數量也不足時才達到令牌桶的總限速值。因為計算主要是依賴副桶中的令牌對流量進行控制，本實施例中的精度是由副桶決定的，而副桶的精度比主桶的精度高，所以依賴於副桶的精度比不分主副桶的精度高，因而對流量控制的誤差也大大減小。通過上述方法，通過設置主桶和副桶，依靠副桶提高限速值精度，避免限速值大時精度低、誤差大，增大了令牌桶限速值的範圍，實現了全範圍的高精度限速。以上實施方式僅用於說明本發明，而並非對本發明的限制，有關技術領域的普通技術人員，在不脫離本發明的精神和範圍的情況下，還可以做出各種變化和變型，因此所有等同的技術方案也屬於本發 明的範疇，本發明的專利保護範圍應由權利要求限定。
權利要求
1.一種基於主副桶的高精度令牌桶限速的方法，其特徵在於，其中所述令牌桶分為主桶和副桶，所述方法具體包括: S1:將所述令牌桶分為主桶和副桶，並分別計算主桶限速值和副桶限速值； 52:根據所述令牌桶中總的令牌數量和所述主桶限速值計算所述主桶的一個單位限速值對應的令牌數量，根據所述令牌桶中總的令牌數量和所述副桶限速值計算所述副桶的一個單位限速值對應的令牌數量； 53:當有報文需要處理時，首先從給所述副桶中提取令牌進行報文處理，當所述副桶中的令牌數量不足時向所述主桶借用令牌將所述副桶填滿再進行報文處理。
2.如權利要求1所述的方法，其特徵在於，所述計算主桶限速值和副桶限速值具體包括: 根據所述令牌桶的總限速值對精度取餘得到所述副桶限速值，根據所述令牌桶的總限速值和所述精度相除得到所述主桶限速值。
3.如權利要求1所述的方法，其特徵在於，在所述令牌桶計算之前還包括: 對所述主桶限速值進行放大 ，將所述主桶限速值放大到與所述副桶限速值相同的數量級，即將所述主桶限速值乘以所述精度得到放大的主桶限速值。
4.如權利要求1所述的方法，其特徵在於，當所述主桶中令牌數量也不足時才達到令牌桶的總限速值。
全文摘要
本發明公開了一種基於主副桶的高精度令牌桶限速的方法，將令牌桶分為主桶和副桶，並分別計算主桶限速值和副桶限速值；根據令牌桶中總的令牌數量和主桶限速值計算主桶的一個單位限速值對應的令牌數量，根據令牌桶中總的令牌數量和副桶限速值計算副桶的一個單位限速值對應的令牌數量；當有報文需要處理時，首先從給副桶中提取令牌進行報文處理，當副桶中的令牌數量不足時向主桶借用令牌將副桶填滿再進行報文處理。本發明通過設置主桶和副桶，依靠副桶提高限速值精度，避免限速值大時精度低、誤差大，增大了令牌桶限速值的範圍，實現了全範圍的高精度限速。
文檔編號H04L12/851GK103248580SQ20131011948
公開日2013年8月14日 申請日期2013年4月8日 優先權日2013年4月8日
發明者朱志博 申請人:漢柏科技有限公司