[發明專利]一種可動態配置的流水化令牌桶限速方法與裝置

在審

• 申請號: 201711089803.9
• 申請日: 2017-11-08
• 公開（公告）號: CN107800644A
• 公開（公告）日: 2018-03-13
• 發明（設計）人: 呂高鋒;卓超;全巍;李韜;趙國鴻;毛席龍;楊惠
• 申請（專利權）人: 中國人民解放軍國防科技大學
• 主分類號: H04L12/819
• 分類號: H04L12/819
• 代理公司: 湖南省國防科技工業局專利中心43102
• 代理人: 馮青

技術領域

本發明涉及網絡通信技術領域，尤其涉及一種可動態配置的流水化令牌桶限速方法與裝置。

背景技術

現有數據網絡中，報文流量突發經常會導致網絡擁塞，在接收端對報文的速率進行限制是解決其網絡擁塞的一種方法，即若報文的速率低于規定的速率則正常接收，否則將報文丟棄或者降低其優先級。

利用令牌桶算法對報文限速是一種常用方法。如圖1所示，系統以規定的速率向令牌桶中添加令牌，直到令牌桶滿則溢出；若有報文到來則將報文長度與令牌桶中的令牌比較，若令牌充足則允許報文正常通過，同時減去報文長度對應的令牌；否則將報文丟棄或降低優先級發送。

上述令牌桶算法中，系統每隔一定的時間間隔向令牌桶中添加一定數量的令牌，常將時間間隔或者每次向令牌桶中添加的令牌數取固定值。若將時間間隔取固定值，其大小決定了向令牌桶添加令牌的頻率，較小則系統需頻繁地添加令牌，負荷較重，因此難以實現大規模數據流的令牌桶限速；較大則系統需較長時間才會添加一次令牌，對于速率較大的報文，當快速消耗完令牌桶的令牌后，直到下次重新添加令牌前報文會一直丟棄或者降級，進而造成報文的速率波動較大。若將每次向令牌桶添加的令牌數取固定值，較小則可支持的最大限速值較?。惠^大則限速值的精度較低，且精度會隨著限速值的變大而急劇降低。

另一種添加令牌的方法則以報文到來作為添加令牌的觸發條件。當一個報文到來，系統計算當前報文與上一報文到來的時間間隔，然后將此時間間隔與令牌添加速率相乘即得到此時需向令牌桶添加的令牌數。此種方式添加令牌的時間間隔完全取決于報文之間的時間間隔，而報文之間的時間間隔與報文的長度、速率等多種因素有相關，若報文之間的時間間隔過長，超出系統計時范圍，或者在此時間間隔內改變了令牌添加速率，則都會對添加的令牌數造成較大的誤差。

發明內容

為解決上述問題，本發明基于FPGA(Field Programmable Gate Array)提供了一種可動態配置的流水化令牌桶限速方法與裝置，該方法對于不同的限速要求可通過參數的動態配置實現，同時使用雙端口RAM(Random Access Memory)分別存儲令牌桶算法所需的相關信息，以形成流水化讀寫，提高管理令牌的效率，進而實現大規模數據流的限速。

為實現上述目的，本發明實現方法如下：

1)將時間粒度以及令牌增加粒度均作為可配置的參數，按照各條流對于限速的要求由外部計算后進行動態配置。時間粒度即添加令牌的時間間隔；令牌增加粒度為每次向令牌桶中添加的令牌數量；

2)使用雙端口RAM分別存儲上述動態配置的參數、計時器以及令牌桶中的令牌數，以便于各自獨立進行讀寫，避免三種信息的訪問沖突，進而實現全流水化訪問；

3)在一個RAM單元存儲多條流的相關信息，則讀寫一個RAM單元即可同時訪問多條流的信息，進一步提高令牌管理效率。所述RAM單元即表示一個RAM地址對應的存儲空間；

4)計時則是通過計數器對系統時鐘周期的計數實現，分別流水化循環訪問配置的參數與計數器進行比較：當所訪問的RAM單元中有流的計數器所計時間大于或等于其時間粒度時，那么應該向其令牌桶中添加數量為其令牌增加粒度的令牌，則此時發出信號通知更新令牌桶中的令牌數，然后重新開始計時；否則無需添加令牌，繼續計時；

5)當一個報文到來時，由輸出管制模塊根據其對應令牌桶中的令牌數決策報文是否允許正常轉發；若令牌不夠，則將報文丟棄或降級；若令牌充足，則正常轉發報文且應該從令牌桶中減去消耗的令牌數(報文長度)，那么此時亦發出信號通知更新令牌桶中的令牌數。所述輸出管制模塊即決策報文是否正常轉發的邏輯；

6)更新令牌桶中的令牌數：根據上述的添加令牌或者消耗令牌的信號讀取相應令牌桶中的令牌數，然后加上添加的令牌數或者減去消耗的令牌數后重新寫入；

7)將令牌管理模塊與處理報文的輸出管制模塊分開實現，以便于以后拓展。所述令牌管理模塊即上述生成令牌以及更新令牌的邏輯。

本發明對于不同的限速要求可通過參數的動態配置實現，同時使用雙端口RAM(Random Access Memory)分別存儲令牌桶算法所需的相關信息，通過對時間粒度以及令牌增加粒度的動態配置，以形成流水化讀寫，適用眾多流的不同的限速要求；而流水化的令牌管理方式明顯提高效率，進而實現大規模數據流的限速。

附圖說明

圖1為令牌桶算法的基本工作原理圖；

圖2為令牌桶限速裝置的令牌管理模塊結構圖；