[發明專利]基于令牌桶的數據傳輸流量調度方法及其系統

有效

• 申請號: 201310716789.6
• 申請日: 2013-12-23
• 公開（公告）號: CN104734989B
• 公開（公告）日: 2018-09-14
• 發明（設計）人: 洪志國;鄧大付;陳卓;羅韓梅;余意
• 申請（專利權）人: 騰訊數碼(天津)有限公司
• 主分類號: H04L12/819
• 分類號: H04L12/819
• 代理公司: 廣州華進聯合專利商標代理有限公司 44224
• 代理人: 王茹;黃曉慶

本發明提供一種基于令牌桶的數據傳輸調度方法及其系統，對各個調度實體設置普通令牌桶，并設置各個調度實體共用的共享令牌桶。所述普通令牌桶記錄分配給對應的調度實體的令牌數，當所述普通令牌桶空閑時，通過所述普通令牌桶和所述共享令牌桶的令牌生成速率的調整，將所述普通令牌桶的令牌生成速率轉移到所述共享令牌桶的令牌生成速率中疊加；當所述普通令牌桶不空閑時，將轉移到所述共享令牌桶的令牌生成速率再轉回到所述普通令牌桶，不需要計算溢出的令牌數。因此所述共享令牌桶可以分配各個調度實體的空閑帶寬資源，且不需要設置定時器來計算所述一般令牌桶溢出的令牌，大大減少了普通令牌桶設置定時器的計算量，降低對處理資源的消耗。

技術領域

本發明涉及數據傳輸的技術領域，特別是涉及一種基于令牌桶的數據傳輸流量調度方法，以及一種基于令牌桶的數據傳輸流量調度系統。

背景技術

令牌桶算法是網絡流量整形和速率限制中最常使用的一種算法。典型情況下，令牌桶算法用來控制發送到網絡上的數據的數目。

令牌桶這種控制機制基于令牌桶中是否存在令牌來指示什么時候可以發送流量。如果令牌桶中存在令牌，則允許發送流量；而如果令牌桶中不存在令牌，則不允許發送流量。

在多個調度單元共享帶寬資源的情況下，使用令牌桶控制機制對每個調度單元進行限速可以改善隔離性，避免某個調度單元占用過多的資源而使其他單元的資源得不到保證。

但是當部分調度單元并沒有用盡其對應的令牌配額，或者根本就空閑的情況下，分配給這些調度單元的令牌配額，并不能被其他調度單元所利用。從而造成一部分資源的閑置和資源利用率的低下。

為了既能在調度單元有需求的時候保證其令牌配額的使用，又能在某些調度單元的令牌配額有空閑時，能夠分配給其他需要的單元使用，目前有兩種方案實現。分別為：

分層令牌桶（Hierarchical Token Bucket，HTB），是在多個調度單元各自的令牌桶之上，還設置有一個速率為系統總帶寬的根令牌桶。每個報文，既要消耗各調度單元自己令牌桶的令牌，還要消耗同樣數量的根令牌桶的令牌。也就是說，每個報文即要穿個一個調度單元的令牌桶，還要穿過根令牌桶。如果根令牌桶令牌不足，則暫時不能讓任何報文通過。如果根令牌桶有足夠的令牌，則優先選擇令牌充足的非空隊列，然后選擇令牌不足的非空隊列。這時的效果，就是這些令牌不足的隊列，在超額使用系統中空閑的資源。

而另一種方法是將調度實體的令牌桶滿溢出的令牌，留存在一個共享令牌池，供需要超額占用空閑資源的調度實體使用。

其基本思想是：空閑或者流量不足其令牌配額的調度單元，其令牌桶消耗令牌的速率低于令牌生成速率，令牌桶中的令牌會超過令牌桶的深度而溢出。溢出的令牌，不是丟棄，而是留存起來供其他調度單元使用。為了防止無限累積溢出的令牌，這些溢出的令牌也是儲存在一個具有固定深度的共享令牌桶(shared token bucket)中。

普通令牌桶算法，是在有報文需要通過令牌桶的時候，才去計算新生成的令牌。而在上述方法中，要將溢出的令牌儲存在共享令牌桶，就需要通過定時器來定期計算每個空閑的令牌桶生產的令牌，并將其儲存到共享令牌桶中。

定時器的目的是為了在指定的時間觸發異步事件，執行指定的回調函數。比如對于一個令牌桶，產生令牌的速率是2000000/秒（20M），令牌桶的深度是2000（2k），那么就需要啟動周期為0.1毫秒的定時器，每0.1毫秒去更新(或轉移)一次令牌數量，也就是每秒觸發1萬次計算，這將消耗大量的處理資源。而且，這還只是一個令牌桶的情況，如果系統中有幾十或者幾百個令牌桶，那造成的處理資源的消耗將會大大增加。

發明內容

針對現有基于令牌桶的資源調度方法對處理資源的消耗大的問題，本發明提出一種基于令牌桶的數據傳輸調度方法，不需要對每個調度實體的令牌桶設置定時器來轉移溢出的令牌，降低對處理資源的消耗。