公平算法 _生活百科

公平算法【公平算法】公平算法保证了低优先权的B_EIR和C类业务在RPR环上的公平接入。通过设定公平算法的权重，可以使不同的结点具有不同的接入速率。节点可以分别在外环和内环上设定不同的权重。
基本介绍中文名：公平算法
保证：低优先权的B_EIR
通过：设定公平算法的权重
结合：速率控制机制对本节点
公平算法公平控制原理公平算法保证了低优先权的B_EIR和C类业务在RPR环上的公平接入。通过设定公平算法的权重，可以使不同的结点具有不同的接入速率。节点可以分别在外环和内环上设定不同的权重。公平算法的目标就是结合速率控制机制对本节点接入的所有C业务和B2EIR业务(以后统称为低优先权业务)採用基于反馈控制机制的公平控制算法,实现频宽的动态公平分配,使得所有节点按照本节点的权重值公平的占用频宽,同时使频宽利用率最大化,避免了某些节点无限制接入数据而使得下游节点处于饥饿状态。公平控制的原理就是当节点监测出输出链路拥塞时(如图1所示),就启动公平算法机制,计算本地的公平速率,然后通过反馈机制向上游传送公平速率信息,使得环上其他节点可随时了解拥塞节点处的流量情况,并根据公平信息调整自己的接入速率,当下游拥塞消除后,就逐渐提高自己的传送速率,在经过一段收敛时间之后,环上所有节点将会基于各自的权重值所分得的速率进行传送,对于等权值的RPR环,则应该以统一的速率传送,从而实现了频宽分配的公平性其他信息SRP算法在RPR中採用了SRP作为频宽分配算法。其基本原理是在算法中设定两个变数FORWARD_RATE和MY_RATE,二者分别表示转发业务的传送速率和本地站点业务的传送速率。当FORWARD_RATE+MY_RATE>LOW_THRESHOLD时,我们就称节点n是拥塞的,这里LOW_THRESHOLD是一个低于链路能力的固定值。当节点n发生拥塞,它就传送一个控制信息给它的上游节点,这个控制信息中包含着它自己站点业务的传送速率MY_RATE[n] 。当上游节点i接收到包含MY_RATE[n]值的拥塞控制信息后,它将降低自己的速率控制器值,我们称之为ALLOWED_RATE 。如果从节点n接收到拥塞信息的上游节点n-1也是拥塞的,那幺它将把节点最近计算的ALLOWED_RATE值和它自己的测量值MY_RATE[n-1]相比较,取较小值送给上游节点。这样,站点的业务速率将不再超过这一流量所经过的下游任一节点所广播的MY_RATE值。如果节点n-1没有拥塞,它将把MY_RATE[n-1]设定为全空的值,以指示没有发生拥塞。接收到全空值的节点将间歇性地增加它们自己的ALLOWED_RATE值。值得注意的是,节点n-1虽然处于拥塞状态,但MY_RATE[n-1]>FORWARD_RATE[n-1]时,节点n-1同样将MY_RATE[n-1]设定为全空值,这是因为,这种情况表示,节点的拥塞状况是由节点n-1传送的业务导致的,而不是由上游节点所传送的业务导致的。这个算法的基本思想是如果所有的节点以接收到的MY_RATE的最小值来分享瓶颈链路,那幺流量的速率将会相等,公平性也由此而来。在没有拥塞的情况下,流量将间歇性地增加它们自己的ALLOWED_RATE,以保证获得最大化的频宽利用率。总的说来SRP具有较好的有效性、简单性和可拓展性,但也存在一些问题。①算法必须设定恰当的算法参数,如控制信息的传送间隔、转发快取器的容量和低优先权门限的大小等。这些参数的设定将会对网路中处于不同位置的节点,及不同优先权的业务产生影响。②由于SRP只有一个单独的速率控制器,这将会产生如下的一些问题：如队头阻塞问题和不平衡业务情形下的频宽分配不公平问题等。DVSR算法VioletaGambiroza等人基于RIAS公平模型设计了一种新的RPR频宽分配算法,称为DVSR(DistributedVirtual-timeSchedulinginRings) 。RRIAS公平模型由两个关键部分组成,第一部分定义了IA流在链路上的公平性需求流量粒度,第二部分确保在第一部分限制下的最大化空间复用,即IA流可以使用那些因各种原因其他流暂时无法使用的频宽。RIAS力图实现最大化的空间再利用和更大的网路吞吐量。?与RPR标準公平算法只在拥塞节点计算全局统一公平速率不同,DVSR为针对不同终节点的每个流量都设定一个速率控制器,所有站点业务的传送速率首先要受速率控制器所控制。在DVSR中最主要的问题就是如何确定每个流量速率控制器的值。这可以通过在RPR节点上的业务监视器测量,并由公平频宽分配器计算出的结果来确定。设为从节点i(包括n)出发抵达节点n的流量的速率,DVSR公平速率满足这实际上是一个基于节点观测流量速率的Max_min运算。它假设rn代表节点i的频宽需求。公平频宽分配器通过公平算法,并结合从下游节点接收到的控制讯息,为本节点的每个流量计算出一个公平速率,并将本站点的业务以计算出的公平速率传送,同时将各流量的公平速率写入到循环控制包的相应位置,传送给上游。接收到控制讯息的上游节点同样利用这些讯息,并综合本地讯息考虑,为每一个流量设定一个速率。这样,DVSR实现最大化的空间再利用。