Packet Fair Queuing Scheduler
前面介绍的几种简单调度算法，都没有很好的考虑调度的公平性。比如在调度决策时没有考虑实际要发送的这个pkt的长度，如果在一个低优先级上一个长度很长的pkt，将会占用输出端口相对很长的时间，可能造成高优先级的pkt等待时间过长。对于不同优先级的流调度，最理想的情况就是将各个流都想象成为流体的形式，无论何时整个输出管道都可以同时为所有的输入流进行服务，不过不同优先级对输出带宽的占用比例不同，这种理想的调度一般成为Generalized Processor Sharing(GPS)。如下图所示：
上图可以看到，在基于流的模式下可以同时对多个pkt进行发送，而实际在于我们基于pkt的网络中这是不可能实现的，但是这种调度方式代表了一个理想的公平调度，可作为现实比较各种调度算法的标准，也可以给实际的调度算法的研究很多启发。
在上面的基于流的调度算法，在任意时刻t，queue_i收到的调度服务比例为：g_i(t) = r * w_i / sum(w_j, for j in B(t))，其中r为整个输出带宽，w_i是queue_i的weight，B(t)是在时间t所有的active queue。由于GPS无法用于pkt调度，因此只能利用模拟的方法，来使实际的调度算法来逼近GPS的性能。
在实际中，通过在系统中引入一个虚拟系统时间V(t)的概念，来模拟GPS中的流的概念。通常利用V(t) 模拟当采用GPS调度时，每个队列第一个pkt应当离开系统的时间(finish time, FT)，然后按照调度时按照pkt的FT进行调度，这种调度策略一般称为Smallest virtual Finish time First (SFF)。因此对于调度器的设计转变为对V(t)函数的选择和对FT的计算方法的选择。首先我们考虑一个相对简单的情况，就是所有队列都有很多pkt在排队的情况，即不存在空的队列的情况。这种情况下，一个队首pkt的FT，在GPS调度的情况下可以计算为：F(i, k) = F(i, k-1) + L(i, k) / Ri，其中F(i, k)为queue_i的第k的pkt的理想结束时间，L(i, k)为这个pkt的长度，Ri是queue_i在总带宽中分配的带宽。因此queue_i中第k个pkt的结束时间就是第k-1个pkt的结束时间再加上利用queue_i的带宽发送第k个pkt的时间，与GPS中流的概念完全符合。但是，实际情况中queue总是有空的情况，这种情况下此queue中新来的pkt的FT如何进行计算就需要借助V(t)函数，V(t)是系统虚拟时间，函数必须满足时间的性质，即加入t1 > t2，那么V(t1) > V(t2)。此时对于F(i, k)的计算方式为：F(i, k) = max(V(a_k), F(i, k-1) )+ L(i, k) / Ri，其中a_k是队列queue_i中第k个pkt的到达时间，V(a_k)是其到达的系统虚拟时间，因此对于队列为空时，pkt的FT就是其到达时间再加上其发送时间，也符合GPS中流的概念。因此我们利用FT进行调度的方法应该可以完成对GPS算法的模拟，具体算法的调度公平性将很大取决于我们对V(t)函数的选择。
Deficit Round-Robin
DRR也是基于RR的一个调度算法，但是这个算法考虑了pkt length。对于DRR，每个queue都有一个deficit，而且queue的deficit值在每个单位时间都会增加，但是每发送一个pkt将会消耗此pkt length的deficit，而只有一个queue的deficit值大于发送queue head的那个pkt所需要的deficit时，此queue才会成为active queue，而一个active queue在发送完一个pkt后，造成当前的deficit不够完成后续pkt的发送时将会不再是active queue；DRR的调度就是对当前所有的active queue进行RR调度。具体如下图所示：
Weighted Fair Queuing (WFQ)
WFQ是一种基于SFF策略进行调度的算法。他定义其V(t)为
（1）V(0)= 0，
（2）V(t + dt) = V(t) + dt * r / sum(r_i, for i in B(t, t+dt))，
其中r为整个输出带宽，r_i为queue_i的输出带宽，B(t, t+dt)为[t, t+dt]时间内active queue的集合。
这个算法可以解释为，比如对于queue_i，第k个pkt的到达时间为t，第k+1个pkt的到达时间为(t+dt)，那个k+1的pkt的虚拟到达时间就是V(t)再加上dt乘上一个倍数，这个倍数就是在dt时间内所有active queue的带宽和占总带宽的比例的倒数，如此计算是因为当active queue的带宽和小于总带宽的时候，就相当于各个queue受到的服务是多于其实际应有的比例的，因此也可以认为是系统的时间加快了，所以active queue在dt时间内获得了这个倍数比例的服务。
具体FT的计算和前面提到的方法相同，F(i, k) = max(V(a_k), F(i, k-1) )+ L(i, k) / Ri
WFQ是一种经典的packet fair queuing的调度算法，下面我们分析一下他的性能。一个调度算法性能主要从两个方面进行分析，计算复杂度和delay bound。首先对计算复杂度进行分析，通过上面的介绍，我们可以看出WFQ对每个pkt的FT的计算复杂度是O(1)，其中需要维护系统中所有active queue的sum(r_i)，这个采用增量更新的方式O(1)实现，并且保存每个queue最后一个pkt的FT，以及整个调度的最后一个pkt的VT，因此利用上面的结果O(1)可以完成对FT的计算。WFQ调度采用SFF策略，选择所有pkt中FT最小的pkt进行调度，由于每个class的queue都是FIFO，即对一个class当前队列中所有pkt的FT是单调递增的，因此也就是对所有queue的HOL pkt中选择最小的FT进行调度，这个操作的复杂度是O(logN)。因此WFQ的复杂度就是O(logN)。
对于scheduler的delay bound的定义是其调度时间相对于GPS调度时间的最大延迟时间：一个pkt在t1时间入队，如果采用GPS调度在t2时间被调度到，而实际scheduler在t2’时间才调度到，这个scheduler的delay bound就是max(t2’ – t2)。一个scheduler的delay bound越好，说明其对GPS的近似越好，因此公平性也越好。已有证明，WFQ的delay bound为N/2 * Lmax / r，其中N为queue的数目，Lmax为最大包长，r为链路发送速率。也就是说WFQ的delay bound与queue数目呈线性关系，这也是WFQ调度的一个主要缺陷，为此提出了WF2Q的调度方式，可以实现delay bound与queue数目无关，而只由Lmax和r决定。
接下来将会对Linux中QoS实现进行简单介绍。
待续
阅读(1377) | 评论(0) | 转发(0) |
