分层令牌桶原理

分层令牌桶原理

原文地址:http://luxik.cdi.cz/~devik/qos/htb/manual/theory.htm

定义

先定义一些全局名词:

  • 有与其相关的担保速度AR,峰值速度CR,优先级Plevel和quantum Q。它可以有双亲点节。我们知道真实的速度或R,这个速度是在很短的周期内数据离开类测得。对于内部类R是所有子类的之和。
  • 叶子是没有子类的类。只有叶子可以保存数据包队列。
  • 类的Level决定了它在层次结构的什么位置。叶子的Level是0,根类的Level是“总层级-1”,并且每一个内部类的level都比其父类少1。下面的图片(LEVEL_COUNT=3)
  • 类的模式是人为设定的值,可以由R,AR,CR计算得来。可能的模式有:红:R>CR ; 黄:R<=CR AND R>AR绿:其它
  • D(c)是所有c的子类的叶子节点的储备(储备了多余的流量)的列表,并且在叶子节点和c之前(包含其本身)是“黄色”。换句话说,D(c)是所有想从借流量的叶子的列表。

链接共享目的

现在我们能为R定义链接共享目的了。对于每一个c类,它应该保存
Rc = min(CRc, ARc + Bc) [eq1]
Qc Rp
这里Bc=————————————— iff min[Pi over D(p)]>=Pc [eq2]
sum[Qi over D(p) where Pi=Pc]
Bc = 0 otherwise [eq3]
这里的p是c的父类。如果没有p那么Bc=0。对于Bc的两个定义反映了队列的优先级——当在D(p)中有储备流量时,子类中有大量的高优先级的分类时,流量应该分给高优先级的类使用,而不是自己。根据Q的值,有一小部分多余的流量被分配到所有优先级相同的叶子节点上。因为Rp在[2]中被公式[1]递归定义。换句话说如果流量没有超过峰值流量CR,那么担保速度(AR)可以得到保证。根据Q的比例,超出的流量bw,会被分给有流量储备的叶子节点。

备用延迟目的

我们想确定类是孤立的。所以改变一个类的速度应该不会对其它类造成延迟。除非都向同一个祖先类借用流量。同样高优先级的类应该有低延迟(假设他们都从同一级借用流量)。

CBQ注意

如果你注意到[1],你会发现我们的目的是对CBQ的子集有更多的限制。所以如果我们更容易能满足HTB,因此HTB比CQB更友好。(不懂作者在说什么,原文:【 If you look at [1] you will see that our goals are more restricted subset of CBQ goals. So that if we can satisfy HTB goals than we also satisfy CBQ’s one. Thus HTB is kind of CBQ. 】)

HTB架构

这里会经常将LINUX实现的函数或变量名放到括号中,这方便你阅读源代码。

这里有HTB架构的类树(struct htb_class),在全局也被成为self feed列表(htb_sched::row)。在图片的最右边。self feed是由self slots组成。每层每个优先级都有一个slot。所以在例子中有6个self slots(现在忽略白色slot)。每个self slot保存着一个类的列表——这个列表由有色的线从slot连接到类。在slot中的所有类有相同的层(level)和优先级。self slot包含了所有绿色的列表。

每一个内部类(不含叶子)都有一个内部feed slots(htb_class::inner.feed)。同样每个优先级(红高,蓝低)和每个内部类都有一个内部feed slot。与self slots一样,与slot相同优先级的类列表必须是slot所有者的子集。内部slot保存了 D(c)中黄色子类的列表。

在self feed中白色slot不是真正属于那里,但是出于方便才把它画在哪里。它是每层的等待队列(htb_sched::wait_pq, htb_class::pq_node)。它保存该级别上的所有类的列表, 这些类要么是红色的, 也可以是黄色的。类AR由wall time排序(htb_class::pq_key)在其中改变颜色(htb_class::mode)。这是因为颜色的改变的异步的。

实在是看不动了,好难~有兴趣的人自己看吧!

http://luxik.cdi.cz/~devik/qos/htb/manual/theory.htm

发表评论