改进QoS的技术-调度算法：加权公平队列（WeightedFairQueueing）算法

今天从论坛上看到一个要求实现网络通信当中，路由器实现QoS的调度算法--加权公平队列（WeightedFairQueuing）算法。

翻了翻以前的教科书，感觉理解起来还是比较容易的，于是，编程实现了一下。

算法介绍：

    改进QoS的技术，一般从四个方面来改进，分别是：调度、通信量整形、许可证控制和资源预留。

    调度方面，主要有三种，分别是：先进先出（first-in，first-out，FIFO）、优先权队列（priority queuing）和 加权公平队列（weighted fair queuing）。

    FIFO会将数据分组放入队列（缓冲区）当中等待，直到节点（路由或交换器）处理它们为止。如果分组的到达速率超过处理速率，队列将被填满，新分组将被丢弃。

    PQ将数据分组先分配到不同优先权的队列中，较高优先权的队列会优先处理，直到处理为空，再处理较低优先权的队列。到达的分组通过分类器将不同的分组分往不同优先权的队列。若高优先权队列始终有数据，低优先权的队列将得不到处理。

    WFQ仍然会将数据分组分往不同的队列，但是，每个队列都有各自的权重，系统以轮换的方式来处理每个队列中的分组，并且所处理的分组数量等于相应队列的权重。

代码展示：

package houlei.csdn.net.qos; import java.util.LinkedList; import java.util.Queue; /** * 23.6 改进QoS的技术。<p/> * 调度算法：加权公平队列（WeightedFairQueueing）算法<p/> * @author HouLei * * @param <E> */ public class WeightedFairQueueing<E>{ /** * 默认加权队列的大小 */ public static final int DefaultSizeOfQueue = 8; /** * 分类器。将不同的数据分组分往不同的队列。 * * @param <E> 数据分组 */ public static interface Classifier<E>{ /** * @param data 数据分组对象 * @return 队列的Index */ int classify(E data); } private int [] weights;//每个队列的权重 private int [] sizes;//每个队列的大小 private Classifier<E> classifier;//分类器 private Queue<E> queues [] ;//优先权队列 private int currentQueue = 0;//当前队列 private int polledDatas = 0;//当前队列中已取出的分组数量 public WeightedFairQueueing(int[] weights, int[] sizes, Classifier classifier) { init(weights, sizes, classifier); } public WeightedFairQueueing(int[] weights, Classifier classifier) { int sizes [] = new int[weights.length]; for(int i=0;i<sizes.length;i++){ sizes[i]=DefaultSizeOfQueue; } init(weights,sizes,classifier); } @SuppressWarnings("unchecked") private void init(int[] weights, int[] sizes, Classifier classifier) { if(weights==null || sizes==null || weights.length!=sizes.length){ throw new IllegalArgumentException(); } this.weights = weights; this.sizes = sizes; this.classifier = classifier; queues = new Queue[weights.length]; for(int i=0;i<weights.length;i++){ queues[i]=new LinkedList<E>(); } } /** * 向队列中插入待处理的数据分组 * @param e 待处理的分组 * @return 是否插入成功,未成功则意味着本次插入操作的分组将被丢弃。 */ public synchronized boolean offer(E e){ int num = classifier.classify(e); if(queues[num].size()<sizes[num]){ return queues[num].offer(e); } return false; } /** * 从队列中取出数据分组，若队列中没有数据分组，则返回<code>null</code>。 * @return 从队列中取出的数据分组。 */ public synchronized E poll(){ E e = null;//待取出的数据分组 //从当前队列中取出数据分组 e = pollCurrentQueue(); if(e!=null)return e; //当前队列是空队列的处理，去其他队列尝试取数 for(int i=1;i<queues.length;i++){ polledDatas=0;currentQueue++; ensureCycle(); if((e=pollCurrentQueue())!=null){ break; } } return e; } /** * 指针记录的容错处理。<p/> * 当前队列和当前队列已取出分组数 发生变化时，做容错处理，使之构成循环取数操作。 */ private void ensureCycle(){ if(currentQueue>=weights.length){ currentQueue=0;polledDatas=0; } if(polledDatas>=weights[currentQueue]){ polledDatas=0;currentQueue++; } if(currentQueue>=weights.length){ currentQueue=0;polledDatas=0; } } /** * 从当前队列中取出数据分组，若当前队列为空，则返回null。 */ private E pollCurrentQueue(){ E e = null;//待取出的数据分组 polledDatas++; e = queues[currentQueue].poll(); ensureCycle(); return e; } /** * 测试用例 */ public static void main(String[] args) { //自定义数据分组对象，简单点，num作为分类器的判断条件。 class DataPackage{ int num; Object other; public DataPackage(int right,Object other){ this.num=right;this.other=other; } public String toString(){ return "num= "+num+" /tother= "+other; } } //加权队列的权重 int weights[] = new int []{5,3,2}; //自定义分类器，将数据分组分往不同的队列。 Classifier cf = new Classifier(){ public int classify(Object data) { if(data instanceof DataPackage){ return ((DataPackage)data).num; } return 0; } }; //创建WFQ对象 WeightedFairQueueing<DataPackage> wfq = new WeightedFairQueueing<DataPackage>(weights,cf); //添加数据分组 int index=1; for(int i=0;i<6;i++){ wfq.offer(new DataPackage(0,index++)); } for(int i=0;i<4;i++){ wfq.offer(new DataPackage(1,index++)); } for(int i=0;i<3;i++){ wfq.offer(new DataPackage(2,index++)); } //取出分组数据 for(int i=0;i<15;i++){ System.out.println(wfq.poll()); } } }

最后

以上就是自然金鱼为你收集整理的改进QoS的技术-调度算法：加权公平队列（WeightedFairQueueing）算法的全部内容，希望文章能够帮你解决改进QoS的技术-调度算法：加权公平队列（WeightedFairQueueing）算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。