RPR公平算法

公平控制原理

RPR内环和外环都支持独立的公平算法。公平算法保证了低优先级的B_EIR和C类业务在RPR环上的公平接入。通过设置公平算法的权重，可以使不同的结点具有不同的接入速率。节点可以分别在外环和内环上设置不同的权重。

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实现最大化的空间再利用。