互联网 qkzz.net
全刊杂志网:首页 > 女性 > 文章正文
刊社推荐

一种新型的网络包公平调度算法的研究


□ 钟琳华 吴志美 郑 重 王显雷 江 何

  摘要:针对现有分组轮转法的局限,提出一种新的分组策略——虚拟权重队列分组策略。在这个新的分组策略的基础上,结合DRR和WF2Q,提出了虚拟权重队列分组轮转法。仿真实验表明,虚拟权重队列分组轮转调度算法比现有的分组轮转法拥有更好的延时性能和公平性能。
  关键词:网络包调度; 分组轮转; 虚拟队列; 权重
  中图分类号:TP393文献标志码:A
  文章编号:1001-3695(2008)04-1178-03
  
  0引言
  
  包调度技术是实现网络QoS(quality of service)保障的核心技术之一。提供QoS保障的网络交换节点通常采用CQS(classification, queuing, scheduling)结构[1],即网络包到达节点后,经过交换结构转移到相应的输出接口,然后经过分类器分类,进入不同的队列,调度算法根据一定的规则来决定从等待队列中选择哪个网络包进行发送。
  通常来说,调度算法应该达到如下三个目标:a)低复杂度和可扩展性。调度复杂度最好能与队列的数目无关,以利于扩展。b)良好的公平性。已提出的算法公平性能指标有服务公平指数SFI[2](service fairness index)和最坏公平指数WFI[3](worst case fairness index)。c)低调度延时界限。一个好的调度算法,其最大调度延时应该只与此队列的参数(如权重、分组长度等)有关系,而与其他队列无关。
  网络包公平调度算法可分为两类,基于时间戳的方法和基于轮转的方法。基于时间戳的方法包括WFQ(weighted fair queuing)[4]、WF2Q(worst-case weighted fair queuing)[5]、WF2Q+[6]、VC(virtual clock)[7]、SCFQ(self-clock fair queuing)[3]等,这些算法都是对理想流体模型GPS[8]的模拟逼近。时间戳表示网络包在对应的GPS系统中的发送时间,这类算法为每个网络包计算时间戳,然后通过对时间戳排序选择网络包进行发送。基于时间戳的调度算法比较精确,公平性和延时特性较好,但是要涉及到时间戳的排序操作。O(log N)排序计算复杂度不可避免。其中WFQ和WF2Q算法复杂度高达O(N)(N是系统中队列的数目)。文献[9]证明了单纯的基于时间戳方法获得O(l)的延时界限需要O(log N)的时间戳计算复杂度。这类算法还需要比较复杂的数据结构,不利于硬件实现,因此在实际应用中难以推广。基于轮转的方法具有调度复杂度,且实现简单。其中的余额轮转法DRR(deficit round ro-bin)[1]以字节为单位为每个队列分配一个量化权重quantum和一个余额计数器deficit,解决了传统RR算法在变长分网络包环境下的不公平性的缺点,得到了很广泛的应用。但是DRR只能提供长时间尺度的公平性,从短时间尺度来看,DRR的输出很不平滑,延时特性和公平性较差。研究人员对DRR作了一些改进,Aliquem[10]法通过权重比例缩小的办法减小了DRR输出的突发性,而SRR[11]则通过权重散列的办法改进了DRR的相对公平性。后来研究人员又提出了分组轮转法GRR(group round robin)[12~14],将网络包按照权重进行分组,权重相近的网络包分在同一个组里,调度分两层进行,即组间调度和组内调度。在组内使用轮转法DRR,而在组间按照时间戳进行排序。图1给出了GRR算法的整体框架。GRR结合了时间戳法和轮转法,在调度复杂度和调度延时界限之间进行折中,是一种比较实用的公平调度算法。 ......
很抱歉,暂无全文,若需要阅读全文或喜欢本刊物请联系《计算机应用研究》杂志社购买。
欢迎作者提供全文,请点击编辑
分享:
 

了解更多资讯,请关注“木兰百花园”
分享:
 
精彩图文


关键字
支持中国杂志产业发展,请购买、订阅纸质杂志,欢迎杂志社提供过刊、样刊及电子版。
关于我们 | 网站声明 | 刊社管理 | 网站地图 | 联系方式 | 中图分类法 | RSS 2.0订阅 | IP查询
全刊杂志赏析网 2017