FRED算法

FRED算法

FRED算法被提出的初衷是为了解决RED算法中的公平性问题,即各个TCP流之间以及TCP和UDP混合流之间能公平的共享带宽。其基本思想是在路由器节点处记录每个活动流(在缓冲区队列中有分组存在的流)的状态信息,当拥塞发生时,FRED综合考虑各流的状态、在缓冲区中存在的分组的数量、队列长度以及距离上次丢弃分组的时间等信息来确定丢弃概率和将要被丢弃的分组所在的数据流。

FRED将在网络中传输的数据流分成三类:Fragile流、Robust流、Non-adacptive流。

Fragile流一般指那些RTT较大,发送窗口较小,能对拥塞通知做出响应,但或者对分组丢弃过于敏感,或者对可用带宽的适应性慢的TCP流;Robust流是指那些RTT较小,发送窗口较大,能对拥塞通知做出响应并能充分利用现有的网络条件发送数据的TCP流;Non-adaptive流一般指不能对拥塞通知做出响应的UDP流。

FRED在RED的基础上做了些扩展,新引入参数和,分别表示每个Flow的允许缓存的最小分组数和最大分组,引入一个表示所有Flow的平均队列长度的全局变量avgcq;为每个Flow设置两个保存状态的变量和,表示第i个Flow在缓冲区中的分组数,表示第i个流过度占用带宽的次数,该变量主要用来鉴别Non-adaptive流。

当一个数据分组进入路由器时,比较和、,按照RED算法决定如何处理的的分组,当<时,标记第j个Flow的概率大于标记第i个流的概率,当<时,标记第i个Flow的概率就会大大增加,这样就保护了Fragile流。如果某个Flow的strike大于1,则说明该流为Non-adaptive 流,那么将不允许该流的qlen超过avgcq,从而达到对响应流的保护。

同时,FRED不仅在有数据分组到达时计算平均队列长度,在数据分组离开时也会计算平均队列长度,这样使得平均队列长度更加及时准确地反映了队列的变化情况。

FRED有效的鉴别和限制非响应流,保护了脆弱流,平均传输时间更为公平,但它需要在路由器中维护每个流的状态信息,增加的路由器的计算开销和存储开销。

FRED有效的鉴别和限制非响应流,保护了脆弱流,平均传输时间更为公平,但它需要在路由器中维护每个流的状态信息,增加的路由器的计算开销和存储开销。

 

 

 

 

 

 

点赞

发表评论