基于預約帶寬的HTB 改進算法的研究?

孟祥奎 張瓊聲 李村合 徐晨升

（中國石油大學（華東）計算機與通信工程學院 青島 266580）

1 引言

在互聯(lián)網(wǎng)時代，網(wǎng)絡上的數(shù)據(jù)量出現(xiàn)了爆炸式的增長，如何實現(xiàn)高帶寬低延遲的網(wǎng)絡通信具有現(xiàn)實意義。網(wǎng)絡通信對數(shù)據(jù)處理的延遲要求往往會很高，比如使用即時聊天軟件時，用戶幾乎感覺不到數(shù)據(jù)處理和傳輸?shù)难舆t。如何實現(xiàn)這種高效率的網(wǎng)絡數(shù)據(jù)的處理，在操作系統(tǒng)層面減小數(shù)據(jù)傳輸延遲相關的理論和技術研究具有重要意義。

在數(shù)據(jù)包的傳輸過程中，操作系統(tǒng)內核負責完成對數(shù)據(jù)包的封裝和解封裝；帶寬分配以及數(shù)據(jù)包發(fā)送方式；采用輪詢或觸發(fā)中斷的方式，查看網(wǎng)卡是否有數(shù)據(jù)包到達，以及是否接收。因此，數(shù)據(jù)包在傳輸?shù)倪^程中的延遲主要包括五個部分：數(shù)據(jù)包的封裝、數(shù)據(jù)包的發(fā)送、數(shù)據(jù)包在網(wǎng)絡中間設備中的傳輸、數(shù)據(jù)包的接收以及數(shù)據(jù)包的解封裝。為了提高帶寬的利用率，降低數(shù)據(jù)包發(fā)送延遲，系統(tǒng)為每個網(wǎng)絡設備設置隊列規(guī)則。將到達的數(shù)據(jù)包按照一定的規(guī)則進行分類，并為每個分類分配不同的帶寬，根據(jù)隊列規(guī)則的設置，每次選擇一個數(shù)據(jù)包進行發(fā)送。本文針對常用的HTB 帶寬分配算法，在數(shù)據(jù)包發(fā)送的過程中，通過對各個應用程序的帶寬使用的歷史狀況進行分析，將帶寬合理地分配給各個應用程序，降低數(shù)據(jù)包在發(fā)送過程中的時間消耗，降低數(shù)據(jù)包傳輸?shù)臅r延，提高帶寬的利用率。

本文主要闡述HTB 算法、HTB 的改進算法、實驗與性能評估。

2 HTB算法

HTB 算法，全稱為Hierarchical Token Bucket，分層令牌桶算法，是一種功能強大的流量整型算法。

2.1 HTB算法的基本結構

HTB算法在Linux內核中被實現(xiàn)為一種樹形分層結構，如圖1所示。

圖1 HTB算法結構圖

HTB 算法主要包括三個部分：隊列規(guī)則（Qdisc，Queue Discipline）、分類（Classes）以及分類器（Filters）。Linux 內核為每個網(wǎng)絡設備設置一個隊列規(guī)則，規(guī)定到達這個網(wǎng)絡設備的數(shù)據(jù)包如何分類、如何獲取、如何發(fā)送，以及帶寬如何分配［3］。

在HTB 算法中，節(jié)點分為兩類：內部節(jié)點和葉子節(jié)點［5］。內部節(jié)點中，根節(jié)點作為入口與數(shù)據(jù)流進行交互，其余內部節(jié)點實現(xiàn)對流量的整形、令牌租借等功能。內部節(jié)點不掛載數(shù)據(jù)包，只有葉子節(jié)點中才掛載數(shù)據(jù)包。每個節(jié)點中設置如下參數(shù)，實現(xiàn)高效的令牌租借機制：節(jié)點模式（cmode）、保證速率（AR，Assured Rate）、最大速率（CR，Ceil Rate）、額定量（Quantum）、優(yōu)先級（priority）以及節(jié)點層級（level）。

Linux 內 核 中 節(jié) 點 模 式 有 三 種 ：HTB_CANT_SEND （ 無 法 發(fā) 送 模 式） 、HTB_MAY_BORROW（ 可 租 借 模 式）以 及HTB_CAN_SEND（可發(fā)送模式）。

AR 和CR 是為每個節(jié)點設置的兩個閾值。AR表示系統(tǒng)保證該節(jié)點可以獲得的數(shù)據(jù)包的發(fā)送速率。當數(shù)據(jù)包發(fā)送速率小于AR 時，節(jié)點處于可發(fā)送模式，無限制。CR 為系統(tǒng)能為該節(jié)點提供的最大的數(shù)據(jù)包發(fā)送速率。當數(shù)據(jù)包發(fā)送速率大于CR時，節(jié)點變?yōu)椴豢砂l(fā)送模式。當數(shù)據(jù)包發(fā)送速率介于AR和CR之間時，表明該節(jié)點處于可租借模式。

Quantum 為額定量參數(shù)，系統(tǒng)從某節(jié)點獲取數(shù)據(jù)包時，累計數(shù)據(jù)包的字節(jié)總數(shù)超過此數(shù)值或者數(shù)據(jù)包剩余個數(shù)為0 時，就要停止從此節(jié)點中獲取數(shù)據(jù)包，轉向處理其他的節(jié)點。同時，在節(jié)點向其父節(jié)點租借令牌時，也是以Quantum為單位。

Linux 內核中，共設置8 個不同的優(yōu)先級，用于描述數(shù)據(jù)包發(fā)送的先后順序。

節(jié)點層級表示該節(jié)點在HTB 算法的樹結構中所處的層次，葉子節(jié)點為0層。

2.2 HTB算法執(zhí)行流程

HTB算法的執(zhí)行流程主要包括兩個部分：數(shù)據(jù)包的入隊列和出隊列。當數(shù)據(jù)包到達網(wǎng)絡設備時，根據(jù)數(shù)據(jù)包的優(yōu)先級、目的IP 地址等信息進行分類，進入到不同的數(shù)據(jù)鏈路中，加入到葉子節(jié)點的數(shù)據(jù)包隊列。以圖2為例，介紹HTB算法的執(zhí)行流程。

圖2 HTB算法樹結構圖

網(wǎng)絡設備的名稱為eth0，在eth0上根據(jù)HTB算法設置隊列規(guī)則，并為該隊列規(guī)則分配ID 為1。樹節(jié)點的id 包括兩部分，左側部分表示隊列規(guī)則的id，右側表示節(jié)點id。根節(jié)點的id 為1：1。其余四個id 的節(jié)點如圖2 所示。假設該網(wǎng)絡設備可用的帶寬總量為10M。在根節(jié)點時還未進行帶寬的分配，所以根節(jié)點的Rate 和Ceil 參數(shù)相同，均為10M。HTB 算法為不同的數(shù)據(jù)流分配不同量的帶寬，以保證不同應用的帶寬需求。將節(jié)點1：10 的Rate 值設置為5M，節(jié)點1：20 的Rate 值設置為2M，兩個節(jié)點的Rate參數(shù)之和小于10M，但是兩個節(jié)點的Ceil 參數(shù)之和大于10M，當有節(jié)點流量突增時，存在調節(jié)的空間，使系統(tǒng)具有一定應對流量突發(fā)狀況的能力。在Linux 系統(tǒng)中，Quantum 參數(shù)的設置默認為Rate 參數(shù)的1/10。在此處，節(jié)點1：10 的Quantum 設 置 為50000，1：20 的Quantum 設 置 為20000，其余節(jié)點的Rate、Ceil 和Quantum 參數(shù)設置均如圖2 所示，單位為字節(jié)，使得不同的數(shù)據(jù)鏈路占用網(wǎng)絡設備的時間不同，體現(xiàn)出HTB 算法對帶寬的分配作用。節(jié)點的優(yōu)先級均設置為最高的0。數(shù)據(jù)包i1、i2和j 到達網(wǎng)絡設備eth0 之后，根據(jù)在內部節(jié)點中得到的判決，進入到相應數(shù)據(jù)鏈路中，最終加入到葉子節(jié)點的數(shù)據(jù)包隊列中。

數(shù)據(jù)包在出隊列時，首先尋找一個可以發(fā)送數(shù)據(jù)包的葉子節(jié)點，隨后從該節(jié)點的數(shù)據(jù)包隊列里選擇一個數(shù)據(jù)包進行發(fā)送。在圖2 所示的結構圖中，假設所有的節(jié)點的優(yōu)先級均為0。節(jié)點1：10 為1：101 和1：102 的父節(jié)點，1：1 為1：10 和1：20 的父節(jié)點。在HTB 算法中，使用紅黑樹來管理每層的節(jié)點，不同優(yōu)先級的節(jié)點屬于不同的紅黑樹。在紅黑樹中，根據(jù)節(jié)點ID的大小進行排序，因此1：20節(jié)點為左孩子，1：101 節(jié)點為根節(jié)點，1：102 為右孩子。以圖2為示例說明數(shù)據(jù)包出隊列的過程。

1）最初三個節(jié)點均處于可發(fā)送模式，當有報文掛載到三個節(jié)點下時，節(jié)點被激活。

2）從第0 層節(jié)點開始尋找處于可發(fā)送模式且優(yōu)先級最高的節(jié)點。在圖2 所示的示例中找到1：101/1：102/1：20三個節(jié)點構成的紅黑樹，選取ID 最小的節(jié)點1：20，發(fā)送該節(jié)點數(shù)據(jù)包隊列中的數(shù)據(jù)包。

3）當從1：20 中獲取的數(shù)據(jù)包的字節(jié)總數(shù)達到其Quantum 參數(shù)設置的值，即20000 字節(jié)時，開始尋找下一個葉子節(jié)點，此時找到的是ID 較小的節(jié)點1：101。節(jié)點1：101 和1：102 的發(fā)送模式與1：20相同。

4）三個節(jié)點不斷發(fā)送數(shù)據(jù)包，三個節(jié)點陸續(xù)達到參數(shù)Rate 的設置，節(jié)點的模式變?yōu)榭勺饨枘Ｊ?，并對?jié)點進去行激活處理，同時激活父節(jié)點，將1：20 加入到其父節(jié)點的供給樹中。供給樹是為內部節(jié)點維護的一個字段，用于管理向該節(jié)點借用帶寬的節(jié)點，按優(yōu)先級，分為8個紅黑樹結構。

5）此時第0 層已經(jīng)沒有激活的節(jié)點，轉而向高層即第1 層尋找激活的節(jié)點。此時找到節(jié)點1：10。由于節(jié)點1：10 為非葉子節(jié)點，因此首先找到1：10 的優(yōu)先級最高的供給樹，然后從樹中找到ID最小的節(jié)點，作為發(fā)送數(shù)據(jù)包的節(jié)點。

6）繼續(xù)發(fā)送數(shù)據(jù)包，當節(jié)點的數(shù)據(jù)包發(fā)送速率達到其設置的Ceil 參數(shù)后，節(jié)點變?yōu)椴豢砂l(fā)送模式，無法再發(fā)送數(shù)據(jù)包。

7）隨著時間的推移，令牌會不斷生成。令牌生成的數(shù)量足夠多時，節(jié)點的模式可以從不可發(fā)送模式變?yōu)榭勺饨枘Ｊ交蚩砂l(fā)送模式。

8）重復上面的過程，繼續(xù)發(fā)送數(shù)據(jù)包，直到數(shù)據(jù)包發(fā)送完成。

在HTB 算法中，將數(shù)據(jù)包按照優(yōu)先級、目的ip等信息進行分類，優(yōu)先保障高優(yōu)先級的數(shù)據(jù)包被發(fā)送出去。同時設置參數(shù)quantum，可以保證高優(yōu)先級的數(shù)據(jù)包優(yōu)先發(fā)送的前提下，優(yōu)先級較低的數(shù)據(jù)包不會因為饑餓而失去發(fā)送的機會。Ceil 參數(shù)大于rate 參數(shù)的設置，可以使系統(tǒng)擁有一定的應對流量突發(fā)狀況的能力。當數(shù)據(jù)包流量突然增大時，通過從父節(jié)點中借用帶寬的方式，完成數(shù)據(jù)包的發(fā)送。

3 HTB的改進算法

在HTB 算法中，為節(jié)點設置了三種模式，隨著數(shù)據(jù)包的不斷發(fā)送，節(jié)點的模式變化可能有多種情況。

1）數(shù)據(jù)包發(fā)送之后節(jié)點的模式不變，對節(jié)點發(fā)送數(shù)據(jù)包的個數(shù)和字節(jié)數(shù)進行統(tǒng)計，不做其他操作。

2）數(shù)據(jù)包發(fā)送之后節(jié)點的模式發(fā)生改變，由可發(fā)送模式變?yōu)椴豢砂l(fā)送模式或可租借模式時，需要將節(jié)點插入到該節(jié)點所在層次的等待隊列中，將節(jié)點去激活；節(jié)點模式在可租借模式和不可發(fā)送模式之間變化時，首先將節(jié)點從等待隊列中取出，然后重新加入到等待隊列中；節(jié)點模式由可租借模式或不可發(fā)送模式變化為可發(fā)送模式時，需要將節(jié)點從等待隊列中取出并激活節(jié)點。在完成上述操作后，兩種情況都需要對節(jié)點發(fā)送數(shù)據(jù)包的個數(shù)和字節(jié)數(shù)進行統(tǒng)計。

3）當節(jié)點長時間處于不可發(fā)送狀態(tài)時，會消耗大量時間等待令牌的生成，因此會降低帶寬利用率，增加數(shù)據(jù)包發(fā)送的延遲。

當節(jié)點的模式頻繁發(fā)生改變時，會頻繁觸發(fā)這些操作，從而增加在OS 內核層面發(fā)送數(shù)據(jù)包需要的時間，增加了數(shù)據(jù)包發(fā)送的延遲。本文提出一種HTB算法的改進算法，通過定期對每個節(jié)點的帶寬使用情況進行分析，對于帶寬使用量較大的節(jié)點，由系統(tǒng)為其預留出部分帶寬，變相地增大其rate 和Ceil 參數(shù)的設置，從而減少節(jié)點的模式改變次數(shù)，降低延遲，提高帶寬的利用率。

在HTB 算法中，使用結構體struct HTB_class來描述節(jié)點。此結構體中有一個聯(lián)合類型的字段un，其中定義了兩種結構體，struct leaf 和struct in?ner，分別用于表示葉子節(jié)點和內部節(jié)點。在struct leaf結構中添加三個字段：

unsigned long tokens_reserved；

unsigned long tokens_used；

unsigned long pkts_nums；

tokens_reserved用于記錄父節(jié)點為孩子節(jié)點預留下令牌數(shù)量，tokens_used用于記錄該節(jié)點在一段時間內的令牌消耗數(shù)量，pkts_nums 記錄發(fā)送的數(shù)據(jù)包個數(shù)。這兩個參數(shù)的初值均設置為0。當從該節(jié)點中獲取數(shù)據(jù)包時，便進行統(tǒng)計，對數(shù)據(jù)包的長度進行累計，一共參數(shù)調節(jié)時使用，當參數(shù)調節(jié)完成后清0，重新開始計數(shù)。

在struct inner結構中添加字段：

struct list_reserved*head_reserved；

此字段用于記錄該節(jié)點為其子節(jié)點預留的令牌數(shù)量。由于HTB 算法為多叉樹結構，因此struct list_reserved結構體的定義如下：

struct list_reserved｛

u32 classid；

unsigned long tokens；

struct list_reserved*next；｝

tokens 字段表示該節(jié)點為id 為classid 的節(jié)點預留的令牌數(shù)量。

在得到上述參數(shù)之后，對節(jié)點進行令牌使用情況的分析。

1）在系統(tǒng)中設置參數(shù)調節(jié)的頻率，當系統(tǒng)發(fā)送出相應數(shù)量（程序中設置的數(shù)量為1000，參數(shù)可調）的數(shù)據(jù)包之后，便進行分析。

2）分析時，遍歷所有的葉子節(jié)點，再由葉子節(jié)點，上溯到根節(jié)點，對節(jié)點的參數(shù)進行處理。針對之前獲取的該節(jié)點在此此發(fā)送過程中的表現(xiàn)（即從該節(jié)點中獲取的數(shù)據(jù)包的個數(shù)和字節(jié)數(shù)），計算其數(shù)據(jù)包發(fā)送的速率，若數(shù)據(jù)包發(fā)送的速率超過了該節(jié)點的rate 參數(shù)的限制，則認為此節(jié)點屬于帶寬消耗量較高的節(jié)點，為其預留帶寬，預留帶寬數(shù)量設置為其參數(shù)quantum，即tokens_reseved 字段設置為quantum，并且可以累加，并以此參數(shù)來增加節(jié)點的rate和Ceil參數(shù)。

3）在后續(xù)進行使用情況的分析時，首先保留tokens_reserved 字段不清除，從rate 和Ceil 參數(shù)中減去tokens_reserved 字段的值，即恢復初值。而且如果此時節(jié)點的數(shù)據(jù)包發(fā)送速率仍然高于rate 參數(shù)的限制，則在tokens_reserved 值的基礎上遞加quantum 參數(shù)的值；若此時節(jié)點的數(shù)據(jù)包發(fā)送速率小于rate 參數(shù)的限制，則將tokens_reserved 減去quantum的值，而非立即清0。

4 實驗與性能評估

4.1 實驗平臺

在64 位Ubuntu16.04LTS 系統(tǒng)下，在應用層實現(xiàn)HTB 算法，模擬在內核代碼中HTB 算法實現(xiàn)過程中所需要的所有數(shù)據(jù)結構和函數(shù)調用，并在原HTB 算法的基礎上，實現(xiàn)HTB 改進算法。讓兩個算法在相同的數(shù)據(jù)集上執(zhí)行，得到發(fā)送數(shù)據(jù)包所消耗的時間。

為了測試程序在不同帶寬下數(shù)據(jù)量大小不同情況下的性能，實驗中設置了2000 個數(shù)據(jù)集。一共設置了12 種不同的帶寬，800KB，1200KB，1600KB，2000KB，2400KB，2800KB，3200KB，4800KB， 6400KB， 8000KB， 9600KB 以 及11200KB，每種帶寬下設置200種不同的數(shù)據(jù)量，以數(shù)據(jù)包的個數(shù)為單位，512 個數(shù)據(jù)包為步長，從512個數(shù)據(jù)包一直到102400 個數(shù)據(jù)包，每個數(shù)據(jù)包的大小被隨機設置為500/600/800/1000/1200 五種值之一。

在應用層環(huán)境中，仿真實現(xiàn)兩種算法，并在相同的數(shù)據(jù)集上運行，得到發(fā)送數(shù)據(jù)包花費的時間數(shù)據(jù)。

4.2 性能評估

圖3 表示的是帶寬為11200KB 時的算法運行時間的對比圖，每25 個數(shù)據(jù)為一組，取平均值，得到表1中的數(shù)據(jù)。表1中耗時改進比率一欄表示為改進前后耗時之差與改進前耗時比值，用以表示算法的改進效果。由此可以看到，當數(shù)據(jù)包個數(shù)較少時，可以看到改進后的HTB 算法的改進效果比較明顯，但隨著數(shù)據(jù)包個數(shù)的增多，改進后的HTB 算法的效果迅速減小，但趨于穩(wěn)定，能夠有效降低數(shù)據(jù)包發(fā)送的時間延遲。

圖3 帶寬為11200KB時的數(shù)據(jù)包獲取時間對比圖

表1 帶寬為11200KB的實驗用例中的數(shù)據(jù)

下面以45056個數(shù)據(jù)包為例，計算帶寬利用率。

在數(shù)據(jù)集中，45056 個數(shù)據(jù)包中的數(shù)據(jù)總量為36945920B，即36080KB，3602.56ms 間獲取了總量為36080KB 數(shù)據(jù)，帶寬為11200KB，因此帶寬利用率為

由表1中數(shù)據(jù)可以看出，改進后的HTB 算法能夠有效提高帶寬利用率，降低數(shù)據(jù)包發(fā)送的時間延遲。

5 結語

雖然HTB 改進算法能夠在一定程度上降低數(shù)據(jù)包發(fā)送的延遲，提高帶寬利用率，但是該算法的魯棒性較差，有較小的概率程序會運行崩潰，且對復雜環(huán)境的適應能力較弱。因此下一步的工作目標就是針對算法在不同應用場景下都能取得較好效果以及提高魯棒性的改進。