多令牌桶流量控制排隊算法的設計與實現

任春云 沙啟鑫 尚傳進 劉玉海

（1、中國海洋大學信息科學與工程學院，山東 青島 266100 2、阿爾卡特-朗訊青島研發中心，山東 青島 266100）

1 引言

隨著網絡應用的日益廣泛和一些新的網絡技術的出現,網絡流量控制和帶寬管理成了一個亟待解決的問題[1][2]。Linux的TC模塊提供了強大的流量控制功能[3][4]，其中TBF就是一種很精確的流量控制方式，它對網絡和處理器的影響都很小[5]。但是tbf與其他流量控制算法一樣，要對連續網段內的每個IP分配固定帶寬，必須使用多條規則，否則就會共享帶寬。

2 tbf算法的工作原理

令牌桶過濾器(TBF)[4]是一個簡單的隊列規則：它只允許以不超過事先設定的速率到來的數據包通過，但可能允許短暫突發流量朝過設定值。它很精確,對于網絡和處理器的影響都很小。圖1揭示了令牌桶的基本原理

圖1 tbf原理示意圖

令牌桶的控制機制是基于令牌桶中是否存在令牌來指示什么時候可以發送流量。令牌桶中的每一個令牌都代表一個字節。如果令牌桶中存在足夠的令牌，則允許發送流量；而如果令牌桶中不存在足夠的令牌，則不允許發送流量,直到等到有足夠令牌。在linux中令牌桶過濾器是上述機制的一個擴展（一個雙重令牌桶）兩個個令牌桶背靠靠背設置，一個用來保證平均速率，另一個用來設置峰值速率。

3 etbf的工作原理

為了實現在局域網中對每臺機器平分帶寬，我們可以在一個class下建立多個速率相同的tbf隊列，但是這明顯存在兩個問題：a.每一個class下建多個隊列，隨著隊列數的增加系統系能會急劇下降，b.過多的隊列導致書寫的困難。為了解決這個問題，我們根據tbf的令牌桶原理發展了etbf，一個etbf隊列規則就可以為一個IP網段分配相同的帶寬。在etbf中我們根據IP地址的數目來確定令牌桶的個數，每個令牌桶對應一個令牌桶隊列來存儲數據報。當一個數據報到達時，根據源地址或者目的地址將此數據報放入對應的令牌桶隊列的末尾，如果沒有相匹配的則放入到默認序列中。下面將從etbf數據結構、數據報的出對入隊等方面介紹。

3.1 etbf的數據結構

我們把內核中tbf_sched_data數據結構擴展為 etbf_sched_data，etbf_sched_data 相對于tbf_sched_data增加五個變量

saddr，eaddr分別表示要控制的網段的開始和結束IP地址，flattr表示開始結束地址是源IP還是目的IP，subQueueList是一個鏈表，它的大小為subQueueListSize（等于eaddr減去saddr），鏈表中的每一個元素都是一令牌桶隊列結構

其中tokens，ptokens表示對應序列中的普通令牌桶和峰值令牌桶，subQueue用來存儲數據報。當一個數據報到達時根據IP分配到相應隊列結構體中subQueue成員末尾。

3.2 入隊處理

etbf_enqueue()函數進行入隊處理。首先，提取數據報中IP地址，若此IP地址在（saddreaddr）范圍內，根據IP將此數據報分配到sub－QueueList鏈表中相應的令牌桶對列中，如下所示：skb_queue_tail(&q->subQueueList[subQidx].subQueue,skb);如果不在，那么則將此數據報放入默認隊列中，默認隊列處理過程與tbf的處理過程相同

3.3 重入隊處理

etbf_requeue()函數將先前移除的報文放回到隊列中，處理的過程同入隊處理，所不同的是入隊是將數據報放在隊尾，而重入對是放到對頭，如下所示：skb_queue_head(&q->sub－QueueList[subQidx].subQueue,skb);

3.4 出隊處理

出隊函數etbf_dequeue(),是完成流量整形的關鍵所在。具體步驟如下：

①決定出隊序列，并執行出隊列操作以獲取數據報skb,并檢測skb的有效性。

若skb有效則執行下一步，否則繼續執行這一步，直到找到有數據報的令牌桶序列。如果所有隊列已經被遍歷，那么執行默認隊列出隊處理。

②若skb有效，則根據當前隊列的prokens和tokens及已用時間計算令牌的數量，若是有足夠令牌返回，否則再重入對。

3.5 etbf shell腳本書寫

etbf書寫格式如下：

4 實驗結果

我們選擇實驗環境如下一共十臺機器，一臺作為ftp服務器，一臺運行etbf流量控制程序（eth0上傳，eth1下載），其他八臺作為ftp客戶端下載（192.168.3.3-192.168.3.11）。

Linux為紅旗6.0，內核為2.6.24.4。運行于網關狀態下。

控制下行流量腳本如下

其中一個ip的控制效果圖2，其他ip的效果圖類似:

圖2 etbf下行效果控制圖

由圖可見，開始時沒有實施帶寬管理策略，ftp下載占用了大量的帶寬，且帶寬波動較大。在實施帶寬管理策略后，ftp服務占用的帶寬迅速降低，最終每一個IP占用的帶寬分別維持在351.6KB/s，(策略所實施的帶寬分別為3000kbps)，且幾乎沒有波動。然后在撤銷了帶寬管理策略后，又恢復至原來狀態。實驗結果表明本文的etbf算法可以有效地限制每一個ip的帶寬，并且不存在帶寬共享問題,效果較好。

[2]陳蓓,蔡淮.基于Linux系統的IP服務質量(QoS)管理[J].計算機應用,2003,23,17~19.

[3]Bert Hubert.Linux Advanced Routing&Traffic Control HOWTO [DB/OL].http://lartc.org/ HOWTO/ cvs/ 2. 4routing/output/2.4routing.html,2002205201.

[4]Klaus Wehrle[等]2006 Linux網絡體系結構:Linux內核中網絡協議的設計與實現清華大學出版社,2006