基于预约带宽的HTB 改进算法的研究∗

2020-11-02孟祥奎张琼声李村合徐晨升

计算机与数字工程 2020年9期

孟祥奎张琼声李村合徐晨升

（中国石油大学（华东）计算机与通信工程学院青岛 266580）

1 引言

在互联网时代，网络上的数据量出现了爆炸式的增长，如何实现高带宽低延迟的网络通信具有现实意义。网络通信对数据处理的延迟要求往往会很高，比如使用即时聊天软件时，用户几乎感觉不到数据处理和传输的延迟。如何实现这种高效率的网络数据的处理，在操作系统层面减小数据传输延迟相关的理论和技术研究具有重要意义。

在数据包的传输过程中，操作系统内核负责完成对数据包的封装和解封装；带宽分配以及数据包发送方式；采用轮询或触发中断的方式，查看网卡是否有数据包到达，以及是否接收。因此，数据包在传输的过程中的延迟主要包括五个部分：数据包的封装、数据包的发送、数据包在网络中间设备中的传输、数据包的接收以及数据包的解封装。为了提高带宽的利用率，降低数据包发送延迟，系统为每个网络设备设置队列规则。将到达的数据包按照一定的规则进行分类，并为每个分类分配不同的带宽，根据队列规则的设置，每次选择一个数据包进行发送。本文针对常用的HTB 带宽分配算法，在数据包发送的过程中，通过对各个应用程序的带宽使用的历史状况进行分析，将带宽合理地分配给各个应用程序，降低数据包在发送过程中的时间消耗，降低数据包传输的时延，提高带宽的利用率。

本文主要阐述HTB 算法、HTB 的改进算法、实验与性能评估。

2 HTB算法

HTB 算法，全称为Hierarchical Token Bucket，分层令牌桶算法，是一种功能强大的流量整型算法。

2.1 HTB算法的基本结构

HTB算法在Linux内核中被实现为一种树形分层结构，如图1所示。

图1 HTB算法结构图

HTB 算法主要包括三个部分：队列规则（Qdisc，Queue Discipline）、分类（Classes）以及分类器（Filters）。Linux 内核为每个网络设备设置一个队列规则，规定到达这个网络设备的数据包如何分类、如何获取、如何发送，以及带宽如何分配［3］。

在HTB 算法中，节点分为两类：内部节点和叶子节点［5］。内部节点中，根节点作为入口与数据流进行交互，其余内部节点实现对流量的整形、令牌租借等功能。内部节点不挂载数据包，只有叶子节点中才挂载数据包。每个节点中设置如下参数，实现高效的令牌租借机制：节点模式（cmode）、保证速率（AR，Assured Rate）、最大速率（CR，Ceil Rate）、额定量（Quantum）、优先级（priority）以及节点层级（level）。

Linux 内核中节点模式有三种：HTB_CANT_SEND （无法发送模式）、HTB_MAY_BORROW（可租借模式）以及HTB_CAN_SEND（可发送模式）。

AR 和CR 是为每个节点设置的两个阈值。AR表示系统保证该节点可以获得的数据包的发送速率。当数据包发送速率小于AR 时，节点处于可发送模式，无限制。CR 为系统能为该节点提供的最大的数据包发送速率。当数据包发送速率大于CR时，节点变为不可发送模式。当数据包发送速率介于AR和CR之间时，表明该节点处于可租借模式。

Quantum 为额定量参数，系统从某节点获取数据包时，累计数据包的字节总数超过此数值或者数据包剩余个数为0 时，就要停止从此节点中获取数据包，转向处理其他的节点。同时，在节点向其父节点租借令牌时，也是以Quantum为单位。

Linux 内核中，共设置8 个不同的优先级，用于描述数据包发送的先后顺序。

节点层级表示该节点在HTB 算法的树结构中所处的层次，叶子节点为0层。

2.2 HTB算法执行流程

HTB算法的执行流程主要包括两个部分：数据包的入队列和出队列。当数据包到达网络设备时，根据数据包的优先级、目的IP 地址等信息进行分类，进入到不同的数据链路中，加入到叶子节点的数据包队列。以图2为例，介绍HTB算法的执行流程。

图2 HTB算法树结构图

网络设备的名称为eth0，在eth0上根据HTB算法设置队列规则，并为该队列规则分配ID 为1。树节点的id 包括两部分，左侧部分表示队列规则的id，右侧表示节点id。根节点的id 为1：1。其余四个id 的节点如图2 所示。假设该网络设备可用的带宽总量为10M。在根节点时还未进行带宽的分配，所以根节点的Rate 和Ceil 参数相同，均为10M。HTB 算法为不同的数据流分配不同量的带宽，以保证不同应用的带宽需求。将节点1：10 的Rate 值设置为5M，节点1：20 的Rate 值设置为2M，两个节点的Rate参数之和小于10M，但是两个节点的Ceil 参数之和大于10M，当有节点流量突增时，存在调节的空间，使系统具有一定应对流量突发状况的能力。在Linux 系统中，Quantum 参数的设置默认为Rate 参数的1/10。在此处，节点1：10 的Quantum 设置为50000，1：20 的Quantum 设置为20000，其余节点的Rate、Ceil 和Quantum 参数设置均如图2 所示，单位为字节，使得不同的数据链路占用网络设备的时间不同，体现出HTB 算法对带宽的分配作用。节点的优先级均设置为最高的0。数据包i1、i2和j 到达网络设备eth0 之后，根据在内部节点中得到的判决，进入到相应数据链路中，最终加入到叶子节点的数据包队列中。

数据包在出队列时，首先寻找一个可以发送数据包的叶子节点，随后从该节点的数据包队列里选择一个数据包进行发送。在图2 所示的结构图中，假设所有的节点的优先级均为0。节点1：10 为1：101 和1：102 的父节点，1：1 为1：10 和1：20 的父节点。在HTB 算法中，使用红黑树来管理每层的节点，不同优先级的节点属于不同的红黑树。在红黑树中，根据节点ID的大小进行排序，因此1：20节点为左孩子，1：101 节点为根节点，1：102 为右孩子。以图2为示例说明数据包出队列的过程。

1）最初三个节点均处于可发送模式，当有报文挂载到三个节点下时，节点被激活。

2）从第0 层节点开始寻找处于可发送模式且优先级最高的节点。在图2 所示的示例中找到1：101/1：102/1：20三个节点构成的红黑树，选取ID 最小的节点1：20，发送该节点数据包队列中的数据包。

3）当从1：20 中获取的数据包的字节总数达到其Quantum 参数设置的值，即20000 字节时，开始寻找下一个叶子节点，此时找到的是ID 较小的节点1：101。节点1：101 和1：102 的发送模式与1：20相同。

4）三个节点不断发送数据包，三个节点陆续达到参数Rate 的设置，节点的模式变为可租借模式，并对节点进去行激活处理，同时激活父节点，将1：20 加入到其父节点的供给树中。供给树是为内部节点维护的一个字段，用于管理向该节点借用带宽的节点，按优先级，分为8个红黑树结构。

5）此时第0 层已经没有激活的节点，转而向高层即第1 层寻找激活的节点。此时找到节点1：10。由于节点1：10 为非叶子节点，因此首先找到1：10 的优先级最高的供给树，然后从树中找到ID最小的节点，作为发送数据包的节点。

6）继续发送数据包，当节点的数据包发送速率达到其设置的Ceil 参数后，节点变为不可发送模式，无法再发送数据包。

7）随着时间的推移，令牌会不断生成。令牌生成的数量足够多时，节点的模式可以从不可发送模式变为可租借模式或可发送模式。

8）重复上面的过程，继续发送数据包，直到数据包发送完成。

在HTB 算法中，将数据包按照优先级、目的ip等信息进行分类，优先保障高优先级的数据包被发送出去。同时设置参数quantum，可以保证高优先级的数据包优先发送的前提下，优先级较低的数据包不会因为饥饿而失去发送的机会。Ceil 参数大于rate 参数的设置，可以使系统拥有一定的应对流量突发状况的能力。当数据包流量突然增大时，通过从父节点中借用带宽的方式，完成数据包的发送。

3 HTB的改进算法

在HTB 算法中，为节点设置了三种模式，随着数据包的不断发送，节点的模式变化可能有多种情况。

1）数据包发送之后节点的模式不变，对节点发送数据包的个数和字节数进行统计，不做其他操作。

2）数据包发送之后节点的模式发生改变，由可发送模式变为不可发送模式或可租借模式时，需要将节点插入到该节点所在层次的等待队列中，将节点去激活；节点模式在可租借模式和不可发送模式之间变化时，首先将节点从等待队列中取出，然后重新加入到等待队列中；节点模式由可租借模式或不可发送模式变化为可发送模式时，需要将节点从等待队列中取出并激活节点。在完成上述操作后，两种情况都需要对节点发送数据包的个数和字节数进行统计。

3）当节点长时间处于不可发送状态时，会消耗大量时间等待令牌的生成，因此会降低带宽利用率，增加数据包发送的延迟。

当节点的模式频繁发生改变时，会频繁触发这些操作，从而增加在OS 内核层面发送数据包需要的时间，增加了数据包发送的延迟。本文提出一种HTB算法的改进算法，通过定期对每个节点的带宽使用情况进行分析，对于带宽使用量较大的节点，由系统为其预留出部分带宽，变相地增大其rate 和Ceil 参数的设置，从而减少节点的模式改变次数，降低延迟，提高带宽的利用率。

在HTB 算法中，使用结构体struct HTB_class来描述节点。此结构体中有一个联合类型的字段un，其中定义了两种结构体，struct leaf 和struct in⁃ner，分别用于表示叶子节点和内部节点。在struct leaf结构中添加三个字段：

unsigned long tokens_reserved；

unsigned long tokens_used；

unsigned long pkts_nums；

tokens_reserved用于记录父节点为孩子节点预留下令牌数量，tokens_used用于记录该节点在一段时间内的令牌消耗数量，pkts_nums 记录发送的数据包个数。这两个参数的初值均设置为0。当从该节点中获取数据包时，便进行统计，对数据包的长度进行累计，一共参数调节时使用，当参数调节完成后清0，重新开始计数。

在struct inner结构中添加字段：

struct list_reserved*head_reserved；

此字段用于记录该节点为其子节点预留的令牌数量。由于HTB 算法为多叉树结构，因此struct list_reserved结构体的定义如下：

struct list_reserved｛

u32 classid；

unsigned long tokens；

struct list_reserved*next；｝

tokens 字段表示该节点为id 为classid 的节点预留的令牌数量。

在得到上述参数之后，对节点进行令牌使用情况的分析。

1）在系统中设置参数调节的频率，当系统发送出相应数量（程序中设置的数量为1000，参数可调）的数据包之后，便进行分析。

2）分析时，遍历所有的叶子节点，再由叶子节点，上溯到根节点，对节点的参数进行处理。针对之前获取的该节点在此此发送过程中的表现（即从该节点中获取的数据包的个数和字节数），计算其数据包发送的速率，若数据包发送的速率超过了该节点的rate 参数的限制，则认为此节点属于带宽消耗量较高的节点，为其预留带宽，预留带宽数量设置为其参数quantum，即tokens_reseved 字段设置为quantum，并且可以累加，并以此参数来增加节点的rate和Ceil参数。

3）在后续进行使用情况的分析时，首先保留tokens_reserved 字段不清除，从rate 和Ceil 参数中减去tokens_reserved 字段的值，即恢复初值。而且如果此时节点的数据包发送速率仍然高于rate 参数的限制，则在tokens_reserved 值的基础上递加quantum 参数的值；若此时节点的数据包发送速率小于rate 参数的限制，则将tokens_reserved 减去quantum的值，而非立即清0。

4 实验与性能评估

4.1 实验平台

在64 位Ubuntu16.04LTS 系统下，在应用层实现HTB 算法，模拟在内核代码中HTB 算法实现过程中所需要的所有数据结构和函数调用，并在原HTB 算法的基础上，实现HTB 改进算法。让两个算法在相同的数据集上执行，得到发送数据包所消耗的时间。

为了测试程序在不同带宽下数据量大小不同情况下的性能，实验中设置了2000 个数据集。一共设置了12 种不同的带宽，800KB，1200KB，1600KB，2000KB，2400KB，2800KB，3200KB，4800KB， 6400KB， 8000KB， 9600KB 以及11200KB，每种带宽下设置200种不同的数据量，以数据包的个数为单位，512 个数据包为步长，从512个数据包一直到102400 个数据包，每个数据包的大小被随机设置为500/600/800/1000/1200 五种值之一。

在应用层环境中，仿真实现两种算法，并在相同的数据集上运行，得到发送数据包花费的时间数据。

4.2 性能评估

图3 表示的是带宽为11200KB 时的算法运行时间的对比图，每25 个数据为一组，取平均值，得到表1中的数据。表1中耗时改进比率一栏表示为改进前后耗时之差与改进前耗时比值，用以表示算法的改进效果。由此可以看到，当数据包个数较少时，可以看到改进后的HTB 算法的改进效果比较明显，但随着数据包个数的增多，改进后的HTB 算法的效果迅速减小，但趋于稳定，能够有效降低数据包发送的时间延迟。