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

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

如果从分层递归的角度理解Linux的TC框架，很容易将队列分为有类队列和无类队列，这个角度上看，有类队列和无类队列的地位是平等的。但实际上，它们之间是有层次关系的。之所以将其分为有类队列和无类队列，完全是实现意义上的，你可以看到，Linux对于TC框架的实现非常紧凑，正是基于这种递归的“排队规则，类别，过滤器”三元组来进行的。但是抛开实现，我们需要用一种更加合理的方式来彻底理解数据包调度。
1.数据包调度数据包调度是一个层次，隔离了网卡驱动的收发模块和协议栈。也就是说，数据包从协议栈下来并不是直接进入网卡驱动的发送模块，而是进入数据包调度层，然后驱动模块适时地从这个调度层取出数据包来发送，同样的，对于数据包接收也是一样的。你可以将这个数据包调度层看作是协议栈到网卡之间的一个buffer，如果你比较熟悉UNIX块设备文件的IO过程，你可以将这个调度层理解为块设备的buffer，块设备依buffer的元数据解决随机IO以及数据真正进入介质的先来后到问题，而网卡设备依靠这个数据包调度层来解决流量控制问题。
1.1.按照FIFO规则调度

1.2.按照优先级调度

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

1.3.随机公平调度

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

1.4.其他

你能想到的任何Linux内核目前还没有实现的调度方法以及改进已经实现的算法。
1.5.令牌抽象我们都知道，令牌桶是实现流量整形的利器，几乎被所有的网络设备所采用，那么它一定有自己的特别之处。说到令牌桶，不得不提一个问题，那就是如何对一个数据流进行限速，此处的数据流可以任意定义，你可以将其看做是一个FIFO队列里面的数据包集合，也可以是经典五元组定义的数据包集合，也可以是基于数据包某几个字段计算的具有相同hash值的数据包集合。最显而易见的限速方式就是纪录一个数据流的统计信息，然后按照这些信息进行限速，比如纪录一个数据流上次发送的时间以及发送的数据量，然后和历史数据量以及历史发送时间点进行加权求平均，权值当然是越久远越小，当数据包到来被限速系统抉择是否可以发送的时候，通过当前的时间以及上次计算时的时间做一个时间差，然后再让总的数据量除以这个时间差，计算一个速率，以此作为基准权衡数据流是否已经超速。事实上，Linux TC的CBQ队列就是使用的这种方式。但是即使是作者本人也不甚满意，于是就有了HTB，当然，这是后话。

可以看出，分离数据包分类和数据包调度是有好处的，那就是数据包调度系统可以专心完成按照自己的算法进行的调度细节，而不必去识别数据流，数据流的识别和分类由调度系统的上层来完成。
2.数据包调度的上层在第1节，我们谈到了关于“调度”的含义，并且和进程调度做了比较详细的类比，但是到此为止，还未提到和进程调度体系中调度类对应的概念，而仅仅阐述了调度算法的一些细节，在进程调度中，内核中实现了调度类，“属于一个调度类的进程将按照相同的算法来被调度运行”，对应到数据包调度，也有一个类的概念，即属于一个数据包类别的所有数据包，将按照相同的算法参与调度。正如调度类处在进程调度的上层一样，数据包分类也处在数据包调度的上层。
2.1.数据包分类-排入队列的过程 在“数据包调度”的基础上可以实现精确的调度和整形。问题是，如何将一个数据包排队到第1节介绍的各个调度队列中。对于数据包调度的上层，我统称为排队规则，注意这个排队规则和TC文档中的排队规则完全不同，这里的排队规则指的是数据包进入调度系统，直到最终排队到某个队列之间的所有的规则，我想这样理解起来会比那个递归的“排队规则，类别，过滤器”更加容易，毕竟除了最终的队列，中间的过程只是决定数据包下一步将走向哪个分支，并不是真正的排队。

按照这种理解，Linux TC框架的入队逻辑就简单多了，但是它和经典三元组解释是殊途同归的。我们可以在每一个中间节点配置一个filter，如果它和父亲filter采用了不同的抉择算法，那就重新定义一个Qdisc，虽然这个名字在排队过程中总是容易被误解(注意，在出队过程中，它是正确的，因为出队和入队不同，它是递归的)。对应到经典“排队规则，分类，过滤器”三元组，分类代表一棵子树下面的孩子节点，而过滤器则是用来按照数据包的特征抉择它选炸ky"http://www.Bkjia.com/kf/web/php/" target="_blank" class="keylink">PHPwsPm0ruy47XExMS49rqi19O92rXjoaM8YnIgLyZndDsgICAgICAgy/nS1Mu1o6xMaW51eLXESFRCuebU8srH1+6+rbXktcSjrMv8sb7J7dfutPPP3rbIsdzD4sHLzvO94rXEt6LJ+qOs0vLOqsv8xazBpsq5y/nT0LXEt9bWp77x1PHL47eo0rvWwijTydPay/y/ydLUt9bOqrbgsuMpo6zL/Mq1vMrJz8rH1NrDv9K7uPbW0Lzkvdq147a8t8XWw8HL0ru49sHuxcbNsKOs1eLR+b7Nv8nS1L/Y1sa9+MjryM7S4tK7uPa31tantcTK/b7dsPy1xMvZwsqjrNei0uKjrNXi0KnB7sXGzbDU2sXFttO1xLn9s8zW0MrHsrvKudPDtcSjrLb41Nqz9rbTtcTKsbryyrnTw6GjPGJyIC8mZ3Q7PGgzPjIuMi6197bILbP2ttO1xLn9s8w8L2gzPsjnufvLtcr9vt2w/MjrttO1xLn9s8zKx9fUuPmyv8/y0rbX073ateO08s2o0rvM9c6o0rvCt762tcS5/bPMo6zEx8O0s/a207XEuf2zzNTyysfU2sr3tcTDv9K7uPay47Xduem197bItcS5/bPMoaPV4r7NysfOqrrOTGludXjE2rrLtcRUQ87EtbXJz8q508OhsMXFttO55tTyo6y31sDgo6y5/cLLxvehscj91KrX6cC0w+jK9lRDv/K83LXE1K3S8qGjtavKx8fr16LS4qOssrvE3LC019bD5silwO294qOsyv2+3bD8tcTX7tbVtfe2yLrNt9bA4MrHw7vT0LnYz7W1xKOst9bA4Na7yse5/cLLxve7+dPayv2+3bD8tcTM2NX3vfjQ0LXE0NDOqqOszazR+aOsyv2+3bD8tcTX7tbVtfe2yLrNxcW207nm1PLSssO709C52M+1o6zFxbbT1rvKx9K7uPbI67bT0NDOqqOstvi197bI1PLKx9K7uPaz9rbT0NDOqqGjPGJyIC8mZ3Q7ICAgICAgIMjnufvLtcjrttOy2df3ysfU2sO/0ru49r3ateOwtNXVuf3Cy8b3xeTWw7XEst/C1M6q0ru49sr9vt2w/Mz00aHSu7j2t9bWp9fu1tW9+Mjr0rbX073atePV5sq1ttPB0LXEu7CjrMTHw7Sz9rbTstnX99TyysfSu7j219S4+bK/v6rKvNTaw7/Su7j2vdq147C01dW197bIy+O3qMz00aHSu7j2t9bWp6Os0rvWsdfftb3SttfTvdq148ihs/bSu7j2yv2+3bD8tcS5/bPMoaOyu7ncysfI67bTstnX97u5ysez9rbTstnX97a8yse007j5sr+1vdK219O1xKOs1L290738uPmyv7XEvdq149S9z8iyztPrt9bA4LrNtfe2yKGjPGJyIC8mZ3Q7ICAgICAgILTTs/a207XEuf2zzKOsztLDx7/J0tS/tLW91eLKx9K7uPbU2sO/0ru/w9fTyve1xMO/0ruy47C01dW4w9fTyve1xLj5uea2qLXEtfe2yMvjt6i9+NDQyv2+3bD8tfe2yLXEuf2zzKOsus3I67bTuf2zzNK70fmjrNXi0rLKx9K7uPa31rLjtd256bXEveG5ucr3o6zI58/CzbzL+cq+o7o8YnIgLyZndDs8cD48YnIgLyZndDs8L3A+PHAgYWxpZ249"center">

按照这种理解，Linux TC框架的出队逻辑可以叫做一个新的三元组，即“调度规则，调度实体，调度算法”，其中，调度实体就是树中的每一个节点，当然也包括叶子节点，对于叶子节点，调度实体可以在任何数据结构中而不必非要是树节点(因为它不会有任何子树了)，调度算法来抉择选择下面一层的哪个调度实体。
3.TC调度体系对于进程调度而言，内核将调度算法和调度类统称为进程调度体系，同样的，数据包分类和数据包调度也可以统称为数据包调度。我们将整个数据包调度模块分为了调度模块和调度模块的上层出入队模块，其中出入队模块又可以分为入队和出队两个过程，对于出队过程，新引入一个“调度规则，调度实体，调度算法”三元组来和入队过程的经典“排队规则，分类，过滤器”相对应，这对理解Linux TC框架是有好处的。整个Linux TC框架的结构如下：

vcD48cCBhbGlnbj0="center">Linux的TC实现中ingress这个点上不能拥有队列，此谓控发不控收。但是这并不意味着Linux无法实现ingress的流控。