数据包的分类和调度-Linux TC的另一种解释

如果从分层递归的角度理解Linux的TC框架，很容易将队列分为有类队列和无类队列，这个角度上看，有类队列和无类队列的地位是平等的。但实际上，它们之间是有层次关系的。之所以将其分为有类队列和无类队列，完全是实现意义上的，你可以看到，Linux对于TC框架的实现非常紧凑，正是基于这种递归的“排队规则，类别，过滤器”三元组来进行的。但是抛开实现，我们需要用一种更加合理的方式来彻底理解数据包调度。

1.数据包调度

数据包调度是一个层次，隔离了网卡驱动的收发模块和协议栈。也就是说，数据包从协议栈下来并不是直接进入网卡驱动的发送模块，而是进入数据包调度层，然后驱动模块适时地从这个调度层取出数据包来发送，同样的，对于数据包接收也是一样的。你可以将这个数据包调度层看作是协议栈到网卡之间的一个buffer，如果你比较熟悉UNIX块设备文件的IO过程，你可以将这个调度层理解为块设备的buffer，块设备依buffer的元数据解决随机IO以及数据真正进入介质的先来后到问题，而网卡设备依靠这个数据包调度层来解决流量控制问题。
       正是有了这么一个中间层，才使得网卡设备更像是一个块设备而不是一个简单的FIFO的流式字符设备。在这个调度层，数据包可以经过重新排序，丢弃，阻滞等来实现针对数据包或者数据流的限速或者整形操作。这个隔离的层次不管在网卡还是在块设备，都可以叫做strategy模块，即策略！事实上，它扮演的就是这样一种角色，对于网络数据包而言，上层协议栈并不管“数据包是怎么发送出去的”，而只需要完成协议栈层面的封装即可，将数据包发送到strategy层，其任务就结束了。而对于网卡而言，它并不关心协议栈，不管数据包是经由协议栈下来的，还是通过其它什么手段注入的，它只知道从strategy层拉走一个“最值得发送”的数据包即可，而如何拉取一个“最值得发送”的数据包，正是strategy的体现，也是strategy层即数据包调度层实现的关键之所在！
       熟悉进程调度的应该明白何谓调度，英文中的schedule有时间表的概念，意思是在现在或未来的某个时间做某件事，对于进程调度而言，便是在进程表中找出一个最值得运行的进程来投入运行，具体到怎么找，那就是调度的strategy之体现，对于现代的Linux而言，就是调度类中RT，FAIR了，对于前者采用FIFO等方式调度，对于后者采用CFS算法调度，每一个进程在创建之初或者之后通过API可以将自己归到某一个调度类中，一旦归到那个调度类，在轮到那个调度类调度进程的时候，就要采用那个调度类的调度算法。
       理解进程的调度对于理解数据包的调度非常有帮助，事实上，数据包的调度和进程调度唯一不同的地方在于调度实体的不同，它的含义是“找出最值得发送[使用IMQ或者ifb可以实现ingress调度]的数据包”，基本的调度方式如下。

1.1.按照FIFO规则调度

最简单的调度方式，维护一个队列，先入先出，图示如下：

1.2.按照优先级调度

稍微复杂一点，维护多个队列，每一个优先级一个，调度算法首先选择一个最高优先级的队列，然后在该队列中执行FIFO算法，这是一个二级调度算法，图示如下：

1.3.随机公平调度

和优先级调度相反，它保证所有的数据包拥有相同的发送机会，它也维护多个队列，每个队列就是一个hash桶，每一个数据包根据指定的键值散列到这些hash桶中，调度算法按照从左到右的顺序调度hash队列，每一个队列执行FIFO算法，其要点在于，hash算法会在每间隔一段时间改变一次，图示如下：

1.4.其他

你能想到的任何Linux内核目前还没有实现的调度方法以及改进已经实现的算法。
       除了数据包调度之外，还有一个基本概念，那就是流量整形。基本的整形方式就是令牌桶，注意，整形的目的并非为了找出最值得发送的数据包，而是决定一个已经到达的数据包能不能发送，因为它不应被归为数据包调度的范畴。调度和整形的区分在于，调度是指已经有了很多的数据包堵在那里，挑选一个最值得发送的，相反，整形指的是，没有数据包排队，本来这个数据包可以直接发出，由整形逻辑来抉择它能否立即发送。调度和整形的相同点是，都是在为网卡选择一个要发送(或者接收)的数据包的时候被调用。

1.5.令牌抽象

我们都知道，令牌桶是实现流量整形的利器，几乎被所有的网络设备所采用，那么它一定有自己的特别之处。说到令牌桶，不得不提一个问题，那就是如何对一个数据流进行限速，此处的数据流可以任意定义，你可以将其看做是一个FIFO队列里面的数据包集合，也可以是经典五元组定义的数据包集合，也可以是基于数据包某几个字段计算的具有相同hash值的数据包集合。最显而易见的限速方式就是纪录一个数据流的统计信息，然后按照这些信息进行限速，比如纪录一个数据流上次发送的时间以及发送的数据量，然后和历史数据量以及历史发送时间点进行加权求平均，权值当然是越久远越小，当数据包到来被限速系统抉择是否可以发送的时候，通过当前的时间以及上次计算时的时间做一个时间差，然后再让总的数据量除以这个时间差，计算一个速率，以此作为基准权衡数据流是否已经超速。事实上，Linux TC的CBQ队列就是使用的这种方式。但是即使是作者本人也不甚满意，于是就有了HTB，当然，这是后话。
       但是，这种计算极其不准确，受操纵系统协议栈的实现，网卡驱动的实现，以及定时器实现的影响极大，所以就需要另外一种抽象作为参照，这就是令牌。令牌按照一定的速率以字节或者位为单位匀速进入令牌桶，当数据包到达的时候，只需要看看令牌桶里面是否拥有足够的令牌即可，如果有就说明可以发送。由于令牌桶是一个容器，可以积累令牌，因此可以很容易满足突发数据的需求。

       注意，到此为止，我们只是描述了数据包如何被调度，也就是如何找出最值得发送的那个数据包，但这有一个基本前提，就是数据包已经在那里了，在例子中，我使用了队列这种基本的数据结构，实际上也是使用的队列。还有一个问题没有解决，那就是数据包是如何到队列里面的，对于进程调度而言，进程在被创建或者运行的时候，可以调用setscheduler系统调用来把进程放进某一个调度类的链表或者队列或者红黑树中以便让进程调度模块进行调度，但是对于数据包呢？肯定也有这么一个机制，可以统称为排队的规则。到目前为止，数据包调度的总图景如下：

可以看出，分离数据包分类和数据包调度是有好处的，那就是数据包调度系统可以专心完成按照自己的算法进行的调度细节，而不必去识别数据流，数据流的识别和分类由调度系统的上层来完成。

2.数据包调度的上层

在第1节，我们谈到了关于“调度”的含义，并且和进程调度做了比较详细的类比，但是到此为止，还未提到和进程调度体系中调度类对应的概念，而仅仅阐述了调度算法的一些细节，在进程调度中，内核中实现了调度类，“属于一个调度类的进程将按照相同的算法来被调度运行”，对应到数据包调度，也有一个类的概念，即属于一个数据包类别的所有数据包，将按照相同的算法参与调度。正如调度类处在进程调度的上层一样，数据包分类也处在数据包调度的上层。
       对于进程调度中的调度类而言，各个调度类之间是不平等的，在调度真正的进程之前，首先要在调度类之间进行调度，即选出一个调度类，然后在属于该调度类的所有进程间进行调度。同样的，数据包按照其特征分出的类别也是不平等的，首先要在各个类别之间进行调度，其调度算法无外乎也就是数据包的调度算法那几样，不同的是，正如调度类处在进程调度的上层一样，数据包类别的调度也处在数据包调度的上层。

2.1.数据包分类-排入队列的过程

       在“数据包调度”的基础上可以实现精确的调度和整形。问题是，如何将一个数据包排队到第1节介绍的各个调度队列中。对于数据包调度的上层，我统称为排队规则，注意这个排队规则和TC文档中的排队规则完全不同，这里的排队规则指的是数据包进入调度系统，直到最终排队到某个队列之间的所有的规则，我想这样理解起来会比那个递归的“排队规则，类别，过滤器”更加容易，毕竟除了最终的队列，中间的过程只是决定数据包下一步将走向哪个分支，并不是真正的排队。
       所以说，整个数据包调度的上层就是一系列的决定，最终画出了一条到达最终调度队列的一条唯一的路径，按照图论以及实现效率来理解，确定唯一的一条路径的最好的图就是树，从树根到达某个叶子节点，存在唯一的一条路径。那么，这一系列决定的过程正是数据包向下到达叶子的过程，决策点的唯一问题就在数据包到达数据的枝干节点后如何分支的问题。很显然，这棵树可以是N叉的，每个分支的高度也不一定相同，最终只要能到达一个叶子节点代表的调度队列即可。
       具体抉择数据包走向哪个分支的动作内置在中间节点内部，每一个中间节点的决策算法可以相同也可以不同，这就形成了一个分层递归的结构树，如下图所示：

按照这种理解，Linux TC框架的入队逻辑就简单多了，但是它和经典三元组解释是殊途同归的。我们可以在每一个中间节点配置一个filter，如果它和父亲filter采用了不同的抉择算法，那就重新定义一个Qdisc，虽然这个名字在排队过程中总是容易被误解(注意，在出队过程中，它是正确的，因为出队和入队不同，它是递归的)。对应到经典“排队规则，分类，过滤器”三元组，分类代表一棵子树下面的孩子节点，而过滤器则是用来按照数据包的特征抉择它选择下面一层的哪个孩子节点。
       所以说，Linux的HTB规则是最经典的，它本身最大限度避免了误解的发生，因为它努力使所有的分支抉择算法一致(由于它可以分为多层)，它实际上是在每一个中间节点都放置了一个令牌桶，这样就可以控制进入任意一个分支的数据包的速率，注意，这些令牌桶在排队的过程中是不使用的，而在出队的时候使用。

2.2.调度-出队的过程

如果说数据包入队的过程是自根部向叶子节点打通一条唯一路径的过程，那么出队的过程则是在树的每一个层递归调度的过程。这就是为何Linux内核的TC文档上使用“排队规则，分类，过滤器”三元组来描述TC框架的原因。但是请注意，不能按字面去理解，数据包的最终调度和分类是没有关系的，分类只是过滤器基于数据包的特征进行的行为，同样，数据包的最终调度和排队规则也没有关系，排队只是一个入队行为，而调度则是一个出队行为。
       如果说入队操作是在每一个节点按照过滤器配置的策略为一个数据包挑选一个分支最终进入叶子节点真实队列的话，那么出队操作则是一个自根部开始在每一个节点按照调度算法挑选一个分支，一直走到叶子节点取出一个数据包的过程。不管是入队操作还是出队操作都是从根部到叶子的，越接近根部的节点越先参与分类和调度。
       从出队的过程，我们可以看到这是一个在每一棵子树的每一层按照该子树的根规定的调度算法进行数据包调度的过程，和入队过程一样，这也是一个分层递归的结构树，如下图所示：

按照这种理解，Linux TC框架的出队逻辑可以叫做一个新的三元组，即“调度规则，调度实体，调度算法”，其中，调度实体就是树中的每一个节点，当然也包括叶子节点，对于叶子节点，调度实体可以在任何数据结构中而不必非要是树节点(因为它不会有任何子树了)，调度算法来抉择选择下面一层的哪个调度实体。

3.TC调度体系

对于进程调度而言，内核将调度算法和调度类统称为进程调度体系，同样的，数据包分类和数据包调度也可以统称为数据包调度。我们将整个数据包调度模块分为了调度模块和调度模块的上层出入队模块，其中出入队模块又可以分为入队和出队两个过程，对于出队过程，新引入一个“调度规则，调度实体，调度算法”三元组来和入队过程的经典“排队规则，分类，过滤器”相对应，这对理解Linux TC框架是有好处的。整个Linux TC框架的结构如下：

我一直都没有提到ingress流控，因为在Linux的TC实现中ingress这个点上不能拥有队列，此谓控发不控收。但是这并不意味着Linux无法实现ingress的流控。