本文涉及的队列规则(Qdisc)都可以作为接口上的主qdisc,或作为一个classful qdiscs的叶子类。这些是Linux下使用的基本调度器。默认的调度器为pfifo_fast
。
注:虽然FIFO是队列系统中最简单的元素之一,但pfifo和bfifo都不是Linux接口上的默认qdisc。参见 Section 6.2, “
pfifo_fast
, the default Linux qdisc”了解更多关于默认qdisc(pfifo_fast
)的信息。
FIFO算法是所有Linux网络接口的默认qdisc(pfifo_fast
)。它不会对报文进行整流和重排,仅在接收到报文并在报文入队列后尽快将其发送出去。这也是新创建的类使用的qdisc(除非使用其他的qdisc或类替换FIFO)。
FIFO算法维护了一个报文列表,当一个报文入队列后,会将其插入队列末尾。当需要将一个报文发送到网络上时,会将列表首部的报文进行发送。
真实的FIFO qdisc必须限制列表的大小(缓冲大小)来防止溢出,这种情况下无法将接收到的报文入队列。Linux实现了两个基本的FIFO qdisc,一个基于字节数,另一个基于报文。如果不考虑使用的FIFO类型,队列的大小由参数limit
决定。对于pfifo(Packet limited First In, First Out queue)
,其单位为报文,对于bfifo(Byte limited First In, First Out queue)
,其单位为字节。
对于pfifo,大小默认等于接口的txqueuelen,可以使用ifconfig或ip查看。该参数的范围为[0, UINT32_MAX]。
对于bfifo,大小默认等于txqueuelen乘以接口MTU。该参数的范围为[0, UINT32_MAX]字节。在计算报文长度时会考虑链路层首部。
例6. 为一个报文FIFO或字节FIFO指定一个limit
[root@leander]# cat bfifo.tcc
/*
* make a FIFO on eth0 with 10kbyte queue size
*
*/
dev eth0 {
egress {
fifo (limit 10kB );
}
}
[root@leander]# tcc < bfifo.tcc
# ================================ Device eth0 ================================
tc qdisc add dev eth0 handle 1:0 root dsmark indices 1 default_index 0
tc qdisc add dev eth0 handle 2:0 parent 1:0 bfifo limit 10240
[root@leander]# cat pfifo.tcc
/*
* make a FIFO on eth0 with 30 packet queue size
*
*/
dev eth0 {
egress {
fifo (limit 30p );
}
}
[root@leander]# tcc < pfifo.tcc
# ================================ Device eth0 ================================
tc qdisc add dev eth0 handle 1:0 root dsmark indices 1 default_index 0
tc qdisc add dev eth0 handle 2:0 parent 1:0 pfifo limit 30
tc -s qdisc ls
的输出包含limit(报文数或字节数),以及实际发送的字节数和报文数。未发送和丢弃的报文使用括号括起来,并不计算在Sent
之内。
本例中,队列长度为1000个报文,发送的681个报文的大小为45894 字节。没有丢包,由于pfifo不会降低报文的速率,因此没有overlimits
:
$ tc -s qdisc ls dev eth0
qdisc pfifo 8001: dev eth0 limit 100p
Sent 45894 bytes 681 pkts (dropped 0, overlimits 0)
如果出现积压(overlimits),也会显示出来。
与所有非默认的qdisc一样,pfifo和bfifo会维护统计数据。
pfifo_fast (three-band first in, first out queue)
qdisc是Linux上所有接口使用的默认qdisc。当创建一个接口后,会自动使用pfifo_fast qdisc队列。如果附加了其他qdisc,这些qdisc则会抢占默认的pfifo_fast,当移除现有的qdisc时,pfifo_fast会自动恢复运行。
pfifo_fast
算法该算法基于传统的FIFO qdisc
,但同时也提供了一些基于优先级的处理。它使用三个不同的band(独立的FIFO)来分割流量。具有最高优先级的流量(交互式流量)会进入band 0,总是会被优先处理。类似地,在band 2出队列之前,band 1中不会存在未处理的报文。
该算法与classful prio qdisc非常类似。pfifo_fast qdisc就像三个并排的pfifo队列,一个报文可以根据其服务类型(ToS)位进入其中某一个FIFO。三个band并不能同时入队列(当具有最小值,即优先级高的band包含流量时,具有高数值的,即优先级低的band就不能出队列)。这样可以优先处理交互流量,或者对“最低成本”的流量进行惩罚。每个band最多可以容纳txqueuelen 大小的报文,可以使用ifconfig
或ip
配置。当接收到额外的报文时,如果特定的band满了,则会丢弃该报文。
参见下面的6.2.3章节来了解ToS为如何转换为band。
三个band的长度取决于接口的txqueuelen
。
终端用户无需对pfifo_fast qdisc进行配置。下面是默认配置。
priomap
决定了报文的优先级,由内核分配并映射到bands。内核会根据报文的八个比特位的ToS进行映射,ToS如下:
四个ToS位的定义如下:
可以使用 tcpdump -v -v 显示整个报文的ToS字段(不仅仅是四个比特位的内容)。
上面展示了很多数值,第二列包含于ToS比特位相关的数值,后面是其对应的意义。例如15表示期望最小货币开销,最大可靠性,最大吞吐量以及最小延迟。
上述四列的内容给出了Linux是如何解析ToS 比特位的,以及它们被映射到的优先级,如优先级4映射到的band 号为1。允许映射到更高的优先级(>7),但这类优先级与ToS映射无关,表示其他意义。
最后一列给出了默认的优先级映射的结果。在命令行中,默认的优先级映射为:
1, 2, 2, 2, 1, 2, 0, 0 , 1, 1, 1, 1, 1, 1, 1, 1
与其他非标准的qdisc不同,pfifo_fast不会维护信息,且不会展示在tc qdisc ls
命令中。这是因为它是默认的qdisc。
随机公平队列是tc命令使用的用于流量控制的classless qdisc。SFQ不会整流,仅负责根据流来调度传输的报文,目的是保证公平,这样每个流都能够依次发送数据,防止因为单条流影响了其他流的传输速率。SFQ使用一个哈希函数将流分到不同的FIFO中,使用轮询的方式出队列。因为在哈希函数的选择上存在不公平的可能性,该函数会周期性地改变,通过扰动(参数perturb)来设置此周变动期性(参见6.3.3参数)。
因此,SFQ qdisc会在任意多的流中,尝试给每条流分配相同的机会来发送数据。
在进入队列之后,会基于报文的哈希值给每个报文分配一个哈希桶。该哈希值可能是从外部的流分类器获取到的,如果没有配置外部分类器,则使用默认的内部分类器。当使用内部分类器时,sfq会使用:
SFQ能够区分ipv4,ipv6,以及UDP,TCP和ESP等。其他协议的报文会基于32位的目的和源进行哈希。一条流大多数对应一个TCP/IP连接。
每个桶都应该表示唯一的一条流。由于多条流可能哈希到同一个桶,sdq的内部哈希算法可能会在可配置的时间间隔内受到干扰,但不公平仅会持续很短的一段时间。然而,扰动可能会在无意中导致发送报文的重排。在Linux 3-3之后,就不会存在报文重排的问题,但可能在重哈希达到上限(流的数目或每条流的报文数)后丢弃报文。
当出队列时,会以轮询的方式请求每个哈希桶的数据。
在Linux3-3之前,SFQ 的最大长度为128个报文,即最多可以分布在128个桶(1024个可用桶)上。当发生溢出时,满的桶会发生尾部丢弃,从而保持公平性。
在Linux3-3之后,SFQ 的最大长度为65535 个报文,除数的极限是65536。当发生溢出时,除非明确要求头部丢弃,否则满的桶会发生尾部丢弃,
tc qdisc ... [divisor hashtablesize] [limit packets] [perturb seconds] [quantum bytes] [flows number] [depth number] [head drop] [redflowlimit bytes] [min bytes] [max bytes] [avpkt bytes] [burst packets] [probability P] [ecn] [harddrop]
SFQ中比较容易混淆的是参数:limit,depth,flows这三个参数。limit用于限制SFQ的队列数目,depth用于限制每条流的数目,flows用于限制流的数目。SFQ会对报文进行哈希,将哈希结果相同的报文作为同一条流上的报文,然后将这条流单独放到一个队列中(受限于哈希算法,有可能存在实际上多个不同的流被哈希成了SFQ中的同一条流,因此引入了perturb)。
附加到ppp0口。
$ tc qdisc add dev ppp0 root sfq
请注意SFQ和其他非整流的qdisc一样,仅对其拥有的队列有效。链路速度等于实际可用的带宽时就是这种情况。 适用于常规电话调制解调器,ISDN连接和直接非交换式以太网链接。
大多数情况下,有线调制解调器和DSL设备不属于这一类。 当连接到交换机并尝试将数据发送到同样连接到该交换机的拥塞段时,情况也是如此。在这种情况下,有效队列并不在Linux内,因此不能用于调度。在classful qdisc中嵌入SFQ可以确保它拥有该队列。
可以在sfq中使用外部分类器,例如基于源/目的IP地址对流量进行哈希:
$ tc filter add ... flow hash keys src,dst perturb 30 divisor 1024
注意给定的divisor应该匹配sfq使用的一个哈希表。如果修改了sfq的divisor的默认值1024,则流哈希过滤器也会使用相同的值。
例7. 带可选RED模块的SFQ
[root@leander]# tc qdisc add dev eth0 parent 1:1 handle 10: sfq limit 3000 flows 512 divisor 16384 redflowlimit 100000 min 8000 max 60000 probability 0.20 ecn headdrop
例8. 创建一个SFQ
[root@leander]# cat sfq.tcc
/*
* make an SFQ on eth0 with a 10 second perturbation
*
*/
dev eth0 {
egress {
sfq( perturb 10s );
}
}
[root@leander]# tcc < sfq.tcc
# ================================ Device eth0 ================================
tc qdisc add dev eth0 handle 1:0 root dsmark indices 1 default_index 0
tc qdisc add dev eth0 handle 2:0 parent 1:0 sfq perturb 10
不幸的是,一些聪明的软件(如Kazaa和eMule等)会通过打开尽可能多的TCP会话(流)来消除公平排队带来的好处。在很多网络中,对于行为良好的用户,SFQ可以充分地将网络资源分配给竞争的流,但当遭受恶意软件入侵网络时,可能需要采取其他措施。
可以参见说明文档:man tc-sfq。 SFQ是多队列算法,RED是单队列算法,可以通过结合两个算法来达到更好的流量控制的目的。
从概念上而言,虽然这类qdisc相比SFQ给用户提供了更多的参数,但它与SFQ并没有什么不同。该qdisc旨在解决上述SFQ的缺点。通过允许用户控制用于分配网络带宽的哈希算法(hash
参数),有可能实现更加公平的带宽分配。
例9. ESFQ用法
Usage: ... esfq [ perturb SECS ] [ quantum BYTES ] [ depth FLOWS ]
[ divisor HASHBITS ] [ limit PKTS ] [ hash HASHTYPE]
Where:
HASHTYPE := { classic | src | dst }
随机早期探测(Random Early Detection)是一种灵活的用于管理队列大小的classless qdisc。一般的队列在满后会从尾部丢弃报文,这种行为有可能不是最优的。RED也会执行尾部丢弃,但是以一种更平缓的方式。
一旦队列达到特定的平均长度,入队列的报文会有一定的(可配置)概率会被标记(有可能意味着丢弃该报文),这个概率会线性地增加到某一点,称为最大平均队列长度(队列也可能会变更大)。
相比简单的尾部丢弃,这样做有很多好处,且不会占用大量处理器。这种方式可以避免在流量突增之后导致的同步重传(这些重传会导致更多的重传)。这样做的目的是使用一个比较小的队列长度,在信息的交互的同时不会因为在流量突增之后导致的丢包而干扰TCP/IP流量。
取决于配置的ECN,标记有可能意味着丢弃或仅仅表示该报文是超限的报文。
平均队列大小用于确定标记的概率,该概率是使用指数加权平均算法计算出来的,通过该值可以调节对流量突发的敏感度。当平均队列大小低于最小字节时,此时不会标记任何报文;当超过最小字节时,概率会直线上升到probability(参数指定),直到平均队列大小达到最大字节数。因为通常不会将概率设置为100%,而队列大小也可能会超过最大字节,因此,limit参数用于硬性设置队列大小的最大值。
大致工作方式为:
$ tc qdisc ... red limit bytes [min bytes] [max bytes] avpkt bytes [burst packets] [ecn] [harddrop] [bandwidth rate] [probability chance] [adaptive]
probability
,以达到目标平均队列:(max-min)/2。# tc qdisc add dev eth0 parent 1:1 handle 10: red limit 400000 min 30000 max 90000 avpkt 1000 burst 55 ecn adaptive bandwidth 10Mbit
GRED用在DiffServ 实现中,且在物理队列中包含虚拟队列(VQ)。当前,虚拟队列的数值限制为16。
GRED分两步配置:首先是通用的参数,用于选择虚拟队列DPs的数目,以及是否打开类RIO的缓冲区共享方案。此时会选择一个默认的虚拟队列。
其次为单独的虚拟队列设置参数。
... gred DP drop-probability limit BYTES min BYTES max BYTES avpkt BYTES burst PACKETS probability PROBABILITY bandwidth KBPS [prio value]
OR
... gred setup DPs "num of DPs" default "default DP" [grio]
该qdisc构建在令牌和桶上。它会对接口上传输的流量进行整形(支持整流)。为了限制特定接口上出队列的报文的速度,TBF qdisc是个不错的选择。它仅会将传输的流量下降到特定的速率。
只有在包含足够的令牌时才能传输报文。否则,会推迟报文的发送。以这种方式延迟的报文将报文的往返时间中引入人为的延迟。
如其名称所示,对流量的过滤会基于消耗的令牌。令牌会大致对应到字节数,每个报文会消耗一个令牌,无论该报文有多小。这样会导致零字节的报文占用一定的链路时间。在创建时,TBF会保存一定的令牌,以应对一次性流量突发的量。令牌会以稳定的速率放到桶中,直到桶满为止。如果没有可用的令牌,则报文会保留在队列中(队列中的报文不能超过配置的上限)。TBF会计算令牌的亏空,并进行节流,直到可以发送队列中的第一个报文。如果不能接收最大速度的报文突发,可以配置峰值速率来限制桶清空的速度。峰值速率使用第二个TBF来实现,其桶相对较小,因此不会发生突发。
例10. 创建一个 256kbit/s 的TBF
[root@leander]# cat tbf.tcc
/*
* make a 256kbit/s TBF on eth0
*
*/
dev eth0 {
egress {
tbf( rate 256 kbps, burst 20 kB, limit 20 kB, mtu 1514 B );
}
}
[root@leander]# tcc < tbf.tcc
# ================================ Device eth0 ================================
tc qdisc add dev eth0 handle 1:0 root dsmark indices 1 default_index 0
tc qdisc add dev eth0 handle 2:0 parent 1:0 tbf burst 20480 limit 20480 mtu 1514 rate 32000bps