多令牌桶流量控制排隊(duì)算法的設(shè)計(jì)與實(shí)現(xiàn)

任春云 沙啟鑫 尚傳進(jìn) 劉玉海

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

1 引言

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

2 tbf算法的工作原理

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

圖1 tbf原理示意圖

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

3 etbf的工作原理

為了實(shí)現(xiàn)在局域網(wǎng)中對每臺(tái)機(jī)器平分帶寬，我們可以在一個(gè)class下建立多個(gè)速率相同的tbf隊(duì)列，但是這明顯存在兩個(gè)問題：a.每一個(gè)class下建多個(gè)隊(duì)列，隨著隊(duì)列數(shù)的增加系統(tǒng)系能會(huì)急劇下降，b.過多的隊(duì)列導(dǎo)致書寫的困難。為了解決這個(gè)問題，我們根據(jù)tbf的令牌桶原理發(fā)展了etbf，一個(gè)etbf隊(duì)列規(guī)則就可以為一個(gè)IP網(wǎng)段分配相同的帶寬。在etbf中我們根據(jù)IP地址的數(shù)目來確定令牌桶的個(gè)數(shù)，每個(gè)令牌桶對應(yīng)一個(gè)令牌桶隊(duì)列來存儲(chǔ)數(shù)據(jù)報(bào)。當(dāng)一個(gè)數(shù)據(jù)報(bào)到達(dá)時(shí)，根據(jù)源地址或者目的地址將此數(shù)據(jù)報(bào)放入對應(yīng)的令牌桶隊(duì)列的末尾，如果沒有相匹配的則放入到默認(rèn)序列中。下面將從etbf數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)報(bào)的出對入隊(duì)等方面介紹。

3.1 etbf的數(shù)據(jù)結(jié)構(gòu)

我們把內(nèi)核中tbf_sched_data數(shù)據(jù)結(jié)構(gòu)擴(kuò)展為 etbf_sched_data，etbf_sched_data 相對于tbf_sched_data增加五個(gè)變量

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

其中tokens，ptokens表示對應(yīng)序列中的普通令牌桶和峰值令牌桶，subQueue用來存儲(chǔ)數(shù)據(jù)報(bào)。當(dāng)一個(gè)數(shù)據(jù)報(bào)到達(dá)時(shí)根據(jù)IP分配到相應(yīng)隊(duì)列結(jié)構(gòu)體中subQueue成員末尾。

3.2 入隊(duì)處理

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

3.3 重入隊(duì)處理

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

3.4 出隊(duì)處理

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

①?zèng)Q定出隊(duì)序列，并執(zhí)行出隊(duì)列操作以獲取數(shù)據(jù)報(bào)skb,并檢測skb的有效性。

若skb有效則執(zhí)行下一步，否則繼續(xù)執(zhí)行這一步，直到找到有數(shù)據(jù)報(bào)的令牌桶序列。如果所有隊(duì)列已經(jīng)被遍歷，那么執(zhí)行默認(rèn)隊(duì)列出隊(duì)處理。

②若skb有效，則根據(jù)當(dāng)前隊(duì)列的prokens和tokens及已用時(shí)間計(jì)算令牌的數(shù)量，若是有足夠令牌返回，否則再重入對。

3.5 etbf shell腳本書寫

etbf書寫格式如下：

4 實(shí)驗(yàn)結(jié)果

我們選擇實(shí)驗(yàn)環(huán)境如下一共十臺(tái)機(jī)器，一臺(tái)作為ftp服務(wù)器，一臺(tái)運(yùn)行etbf流量控制程序（eth0上傳，eth1下載），其他八臺(tái)作為ftp客戶端下載（192.168.3.3-192.168.3.11）。

Linux為紅旗6.0，內(nèi)核為2.6.24.4。運(yùn)行于網(wǎng)關(guān)狀態(tài)下。

控制下行流量腳本如下

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

圖2 etbf下行效果控制圖

由圖可見，開始時(shí)沒有實(shí)施帶寬管理策略，ftp下載占用了大量的帶寬，且?guī)挷▌?dòng)較大。在實(shí)施帶寬管理策略后，ftp服務(wù)占用的帶寬迅速降低，最終每一個(gè)IP占用的帶寬分別維持在351.6KB/s，(策略所實(shí)施的帶寬分別為3000kbps)，且?guī)缀鯖]有波動(dòng)。然后在撤銷了帶寬管理策略后，又恢復(fù)至原來狀態(tài)。實(shí)驗(yàn)結(jié)果表明本文的etbf算法可以有效地限制每一個(gè)ip的帶寬，并且不存在帶寬共享問題,效果較好。

[2]陳蓓,蔡淮.基于Linux系統(tǒng)的IP服務(wù)質(zhì)量(QoS)管理[J].計(jì)算機(jī)應(yīng)用,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網(wǎng)絡(luò)體系結(jié)構(gòu):Linux內(nèi)核中網(wǎng)絡(luò)協(xié)議的設(shè)計(jì)與實(shí)現(xiàn)清華大學(xué)出版社,2006