Packet Scheduling
所有的QoS服务都是基于各种调度方式，packet scheduling是包交换网络中QoS最核心的要素，因为调度方法负责决定现在应该对那个排队queue进行服务，对哪个packet进行传输。如何选择一个合适的调度算法，需要对自身的需求进行分析，另外不同调度方法提供的性能也不同，当然也有不同的复杂度。
评估一个调度算法的性能，除了一般算法的那些性能参数外，还有一个参数就是要评估调度的公平性(fairness)，其中常用的公平标准，比如Jain’s fairness index:
，其中n是queue的数量，x_i是queue_i在单位时间内接受服务的百分比。
另外还有通过Fair Index(FI)和Service Fair Index(SFI)共同来判断调度公平性的方法，其中FI定义为
，其中Si(t1, t2)为queue_i在时间t1到t2内接受的服务的次数，SFI定义为SFI = |FI_i – FI_j|，即queue间FI的差值。如果一个调度算法的SFI始终为0，那么这个调度算法对于任意的queue都是公平的。另外还有一种比较好的描述公平性的方法是调度的最大延迟作为指标的方法（worst-case packet fair），比如如果是一个公平的调度算法，如果queue_i当前队列长度为Qi，其CIR为ri，那么如果是完全公平的调度算法，那么当前queue_i新接收的packet的得到调度最大延迟应该是Qi / ri，假设当前算法实际能保证的最大延迟是（Qi / ri + Ci），那么将各个queue的Ci归一化后Ci = Ci * ri / r，那个这个调度算法的WFI（Worst-case Fair Index）为WFI = max(Ci)。
下面介绍几种简单的调度算法。
First In, First Out
FIFO方法没有优先级的概念，完全按照packet进入系统的时间来决定的，对各个queue来说，也没有什么FI的概念，如下图所示：
Strict Priority
这个就是完全按照优先级进行调度，每次调度按照优先级顺序依次检查各个队列是否有packet要发送，也没有什么FI的概念，高优先级的queue永远阻塞低优先级的queue，如下图所示
Round Robin
这个也没有优先级，调度时依次对各个queue进行轮询，每次调度首先检查上次调度的下一个queue，如果有pkt要发送就选择此pkt，否则检查下一个queue。某种程度上，这个调度算法考虑了一定的公平性，但是完全忽略的pkt的优先级。如下图所示：
Weighted Round-Robin
综合考虑priority和RR就是WRR方法。WRR方法为每个queue指定一个weight，这个值和queue的优先级成正比；WRR调度时也是基于RR，但是对于一个queue每调度一次将此queue的weight值减一，如果此queue的weight已经为0，那么在此轮中此queue将不会被调度直到所有的queue的weight都为0，此轮结束；在一轮结束后将会把所有queue的weight值恢复到指定值。这样weight值高的queue在一轮中被调度的次数将多于weight低的queue，从而实现优先级。比如三个queue，A,B,C，各自的weight分别为1，2，3那么如果各个queue都始终有packet要发送的情况下，调度情况可能是ABCBCCABCBCC，也可能是ABBCCCABBCCC，也可能是ACBCBCACBCBC，很明显最后一个的调度的公平性较好。方法如下图所示：
上面介绍的各个调度算法都有很大局限性，没有对各个priority的queue的公平性进行很多考虑，下面介绍几种packet fair queueing方法
待续
阅读(503) | 评论(0) | 转发(0) |
