RR
轮询调度
Round-Robin,轮询调度,通信中信道调度的一种策略,该调度策略使用户轮流使用共享资源,不会考虑瞬时信道条件。
简介
Round-Robin,轮询调度,通信中信道调度的一种策略,该调度策略使用户轮流使用共享资源,不会考虑瞬时信道条件。从相同数量无线资源(相同调度时间段)被分配给每条通信链路的角度讲,轮询调度可以被视为公平调度。然而,从提供相同服务质量给所有通信链路的角度而言,轮询调度是不公平的,此时,必须为带有较差信道条件的通信链路分配更多无线资源(更多时间)。此外,由于轮询调度在调度过程中不考虑瞬时信道条件,因此它将导致较低的整体系统性能,但与最大载干比调度相比,在各通信链路间具有更为均衡的服务质量。
队列调度算法的公平性、分组排队时延等性能是影响路由设备QoS特性的中央因素。队列调度算法可用循环调度(RR,Round Robin)等算法。
传统的轮询算法对不同的分组业务流队列进行同样的无差别的循环调度服务,这样的调度方式对于等长业务流队列是公平的,但是互联网的业务流是由不定长分组流构成的,因此不同的队列就可能具有不同的分组长度,结果分组长度大的业务流队列将可能会比分组长度小的业务流队列接收更多的服务,是队列之间产生不公平的现象;而且,这种算法也无法事先对业务需要的时延保证。
分类
为了改进RR算法的时延特性和其在变长分组环境下的不公平性,人们又提出了一些改进算法,如加权轮询(WRR,Weight RR),差额轮询(DRR,Defict RR),紧急轮询(URR,Urgency-based RR)。这些算法都力图在尽量保持RR算法实现简单性的同时,从不同的方面改进RR算法的时延特性和其在可变长分组环境下的不公平性。
WRR
WRR也是周而复始地轮询分组业务流队列,但不同的是WRR算法为每个业务流队列分配一个权值,当轮询到某个业务流队列时,将根据它所具有权值的大小决定其可转发分组的个数,而不是只转发一个。由于WRR是基于轮询的,因此它只是在大于一个轮询周期的时间上才能显示是公平的,同时,当队列的分组大小不等时,它也不能公平地分配带宽。
DRR
DRR算法通过为各业务流分配服务权值来解决RR调度在变长分组环境中的不公平性。DRR算法规定,每个调度循环中的的业务流队列i可接收的服务量定额为Q。在首轮循环中,若业务流队列i的队首分组的长度大于Q,就不能在本轮得到服务,其服务量定额Q被累加到分组下一轮;若队首分组长度小于Q,则该分组可接收服务,本轮未用完的服务质量定额也将累加到下一轮;在以后的调度循环中一次类推。由此可见,即使分组长度不同各业务不会流队列获得的服务量也不会超过其定额,从而隔离了各业务流之间的相互影响。DRR算法提高了变长分组环境中算法的公平性,又没有增加RR算法原有的复杂度。但DRR算法在时延特性上有明显的缺点,即在每个调度循环中,队列的服务顺序是静态指定的,不能根据业务的属性进行动态调整,因此难以有效地支持实时业务。
URR
URR算法是为改善RR算法时延特性而提出的另一种算法。URR个紧急性指数算法为每个队列分配U;在每个调度循环前,算法首先计算各队列的U值,然后按照U的大小顺序为各队列提供服务。尽管URR算法改善了时延特性,但其原有的公平性问题仍然存在。
参考资料
最新修订时间:2022-08-25 11:45
目录
概述
简介
参考资料