《一种新型的网络包公平调度算法的研究.doc》由会员分享，可在线阅读，更多相关《一种新型的网络包公平调度算法的研究.doc（8页珍藏版）》请在三一文库上搜索。
1、一种新型的网络包公平调度算法的研究0引言 ?调度技术是实现网络QoS(quality of service)保障的核心技术之一。提供QoS保障的网络交换节点通常采用CQS（classification, queuing, scheduling）结构1，即网络包到达节点后，经过交换结构转移到相应的输出接口，然后经过分类器分类，进入不同的队列，调度算法根据一定的规则来决定从等待队列中选择哪个网络包进行发送。 ?此担?调度算法应该达到如下三个目标：a)低复杂度和可扩展性。调度复杂度最好能与队列的数目无关，以利于扩展。b)良好的公平性。已提出的算法公平性能指标有服务公平指数SFI2（service f
2、airness index）和最坏公平指数WFI3（worst case fairness index）。c)低调度延时界限。一个好的调度算法，其最大调度延时应该只与此队列的参数（如权重、分组长度等）有关系，而与其他队列无关。 ?络包公平调度算法可分为两类，基于时间戳的方法和基于轮转的方法。基于时间戳的方法包括WFQ(weighted fair queuing)4、WF2Q(worstcase weighted fair queuing)5、WF2Q+6、VC(virtual clock)7、SCFQ(selfclock fair queuing)3等，这些算法都是对理想流体模型GPS8的模拟
3、逼近。时间戳表示网络包在对应的GPS系统中的发送时间，这类算法为每个网络包计算时间戳，然后通过对时间戳排序选择网络包进行发送。基于时间戳的调度算法比较精确，公平性和延时特性较好，但是要涉及到时间戳的排序操作。O（log N)排序计算复杂度不可避免。其中WFQ和WF2Q算法复杂度高达O（N）（N是系统中队列的数目）。文献9证明了单纯的基于时间戳方法获得O（l)的延时界限需要O（log N)的时间戳计算复杂度。这类算法还需要比较复杂的数据结构，不利于硬件实现，因此在实际应用中难以推广。基于轮转的方法具有调度复杂度，且实现简单。其中的余额轮转法DRR（deficit round robin）1以字节
4、为单位为每个队列分配一个量化权重quantum和一个余额计数器deficit，解决了传统RR算法在变长分网络包环境下的不公平性的缺点，得到了很广泛的应用。但是DRR只能提供长时间尺度的公平性，从短时间尺度来看，DRR的输出很不平滑，延时特性和公平性较差。研究人员对DRR作了一些改进，Aliquem10法通过权重比例缩小的办法减小了DRR输出的突发性，而SRR11则通过权重散列的办法改进了DRR的相对公平性。后来研究人员又提出了分组轮转法GRR（group round robin）1214，将网络包按照权重进行分组，权重相近的网络包分在同一个组里，调度分两层进行，即组间调度和组内调度。在组内使用
5、轮转法DRR，而在组间按照时间戳进行排序。图1给出了GRR算法的整体框架。GRR结合了时间戳法和轮转法，在调度复杂度和调度延时界限之间进行折中，是一种比较实用的公平调度算法。 本文对现有GRR算法的延时性能进行了分析，指出了GRR的分组策略的局限性，提出一种新的分组策略虚拟权重队列分组策略。在这个新的分组策略的基础上，结合DRR和WF2Q，提出了虚拟权重队列分组轮转法VWQGRR。 1公平调度算法的系统模型 ?偕柘低持杏歇?N个队列f1, f2, fn共享一个带宽为R的输出链路，队列fi的保证带宽为ri，有Ni=1riR。每个队列的归一化权重i定义为保证带宽与链路输出带宽的比值，即i=ri/R
6、。i是个分数，为了处理方便，通常使用整数权重wi。假设系统保证带宽的最小计量单位是r，则定义系统总权重W=R/r，通常W是个整数。每个队列的权重wi=Wi=ri/r。对于公平调度算法，必须保证每个队列获得的带宽不小于其保证带宽，且各个队列按权重成比例地共享输出链路的带宽。假设在时间区间t1,t2上，持续非空队列没有发生变化，B(t1,t2)是系统在时间区间t1,t2上的持续非空队列集合，fiB(t1,t2)，则fi获得的理想带宽应为Rwi/fiB(t1,t2)wj。 2现有分组轮转法及其局限 ?谙钟蟹肿槁肿?法算法中，组定义为权重相似的队列的集合：Gj=fi|j-1wi ?入了虚拟权重队列以后
7、，队列fi不再直接参与调度，而是由属于VQi的虚拟权重队列代表fi参与调度。每当属于VQi的虚拟权重队列被调度算法选中时，实际发送的是队列fi中的数据包。因为虚拟权重队列的权重都是2的幂，只有k种可能，对虚拟权重队列实行分组处理更加简单。 4虚拟权重队列分组轮转法 ?谛槟馊囟恿蟹肿椴呗缘幕?础上，参照现有的GRR算法提出了虚拟权重队列分组轮转法VWQGRR。VWQGRR也是一个两层的调度模式，即组间调度和组内调度。图2给出了VWQGRR算法的整体框架。 VWQGRR首先将每个队列拆分成不同的虚拟权重队列，然后对虚拟权重队列进行分组。组间应用WF2Q进行调度，选出一个组获得发送包的机会，在组内应
8、用DRR，选出一个虚拟权重队列。当一个虚拟权重队列被选中时，发送这个虚拟队列指向的实际队列中的数据包。 6结束语 ?疚奶岢鲆恢中碌姆肿椴呗浴?虚拟权重队列分组策略，打破了现有的分组轮转法中一个队列只能隶属于一个组的局限，将每个队列按照权重拆分成不同的虚拟权重队列；然后对虚拟权重队列进行分组，保证每个组内的虚拟权重队列的权重相同，改善了分组轮转法的延时性能。在这个新的分组策略的基础上，结合DRR和WF2Q，提出了虚拟权重队列分组轮转法。仿真实验表明，虚拟权重队列分组轮转调度算法比现有的分组轮转法拥有更好的延时性能和公平性能。 ?慰嘉南祝? 1ARMITAGE G. Quality of serv
9、ice in IP networks M. S.l.: Pearson Higher Education, 2000: 134135. 2GOYAL P, START H M V. Time fair queuing:a scheduling algorithm for integrated services packet switching networksJ. IEEE/ACM Trans on Networking, 1997, 5(5): 690703. 3GOLESTANI S J. A self clocked fair queuing scheme for broadband a
10、pplicationsC/Proc of IEEE INFOCOMM94. Toronto:s.n.,1994: 636645. 4PAREKB A K, GALLAGER R G. A generalized processor sharing approach to flow control in integrated services networks: the single node caseJ. IEEE/ ACM Trans on Networking,1993，1(3): 344357. 5BENNETT R, ZHANG H. WF2Q: worst case fair wei
11、ghted fair queuingC/Proc of IEEE INFOCOM96. San Francisco:s.n., 1996: 120128. 6BENNETT J, ZHANG H. Hierarchical packet fair queuing algorithmsJ. IEEE/ACM Trans on Networking, 1997, 5(5): 675689. 7ZHANG L. Virtual clock: a new traffic control algorithm for packet switching networksC/Proc of ACM SIGCO
12、MM90. New York:s.n.,1990: 1929. 8PAREKB A K,GALLAGER R G. A generalized processor sharing approach to flow control in integrated services networks : the multiple node caseC/Proc of IEEE INFOCOM93. San Francisco:s.n., 1993: 521530. 9VALENTE P. Exact GPS simulation with logarithmic complexity and its
13、application to an optimally fair schedulerC/Proc of SIGCOMM04.Portland:s.n.,2004: 269280. 10LENZINI L, MINGOZZI E, STEA G. Aliquem: a novel DRR implementation to achieve better latency and fairness at O(1) complexityC/Proc of the 10th IEEE International Workshop on Quality of Service. Miami:s.n., 20
14、02: 7786. 11GUO Chuanxiong. SRR: an O(1) time complexity packet scheduler for flows in multiservice packet networksJ. IEEE/ACM Trans on Networking,2004,12(6): 11441155. 12RAMABHADRAN S, PASQUALE J. Stratified round robin: a low complexity packet scheduler with bandwidth fairness and bounded delayC/P
15、roc of ACM SIGCOMM03. Karlsruhe:s.n., 2003: 239249. 13CAPRITA B,WONG Chunchan, NIEH J. Group round robin: improving the fairness and complexity of packet schedulingC/Proc of the 1st ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS 2005). Princeton: s.n.,2005:2940. 14YUAN Xin, DUAN Zhenhai. FRR: a proportional and worstcase fair round robin schedulerC/Proc of INFOCOM 2005. Miami: s.n., 2005:831842. 15NS2EB/OL. 200607. http:/www.isi.edu/nsnam/ns. “本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文”