基于区分服务的改进RED算法(胡啸).ppt

基于区分服务的改进RED算法,报告人：胡啸指导老师：井元伟教授,主要内容,研究背景,RIO-C算法,改进RIO-C算法,下一步工作,研究背景,人们对网络需求量的增加硬件设备的能力，包括路由器处理能力和链路带宽等就Internet的体系结构而言，拥塞的发生是其固有的属性,源端算法：主要是针对TCP/IP协议的研究。链路算法：主要是路由器上对进入缓存的数据的处理方法，RED（随机早期检测）算法。,1、网络现状,2、解决方法,自1993年，S.Floyd和V.Jacobson提出随机早期检测（RandomEarlyDetection：RED）以来，它一直是一个研究热点，先后出现了几种改进方式，如：ARED、SRED、DWRED、WRED、RIO-C、RIO-D、NRED等。,1、RED算法发展过程,研究背景,2、重点研究对象,基本RED算法、RIO-C算法,基本RED算法,基本RED算法：RED，即随机早期检测/丢弃，它是检测初期的拥塞并通过标记或者丢弃分组来向发送端提供反馈。使用RED，可以从一定程度上减少信息突发带来的影响，降低分组丢失率和解决网络同步问题。队列长度avg丢弃概率,RED分组丢弃率,基本RED算法,RED算法可以简单地描述为：For每一到达的包计算平均排队长度avgIf计算丢弃概率P根据丢弃概率标记到达的分组Elseif丢弃到达的分组,RIO-C算法,RIO-C算法：RIO-C是在DiffServ模型中将RIO扩展为三个丢弃优先级或颜色。当业务流到达率小于预约信息速率时，分组将被标记标为绿色(低丢弃优先级);如果业务流到达率大于预约信息速率而小于峰值信息速率时，分组将被标为黄色(中丢弃优先级);如果业务流大于峰值信息速率，分组将被标为红色(高丢弃优先级)。,队列长度丢弃概率,RIO-C分组丢弃率,RIO-C对不同“颜色”的分组计算不同的平均队长。各平均队长的计算之间存在一定的关联。具体来说，是指，“绿”分组的平均队长只用“绿”分组的数目计算；“黄”分组的平均队长用“黄”分组和“绿”分组数目之和计算；“红”分组的平均队长则用“红”、“黄”和“绿”分组的总数来计算。每种“颜色”分组的丢弃率与该“颜色”分组的平均队长和RIO-C参数有关。其参数设置方式如图所示。,RIO-C算法,RIO-C算法参数设置,丢弃概率：,RIO-C算法可以简单地描述为：当有分组到达时if绿色分组分别计算绿色分组、黄色分组和红色分组的平均队长elseif黄色分组分别计算黄色分组、红色分组的平均队长else红色分组计算红色分组的平均队长if绿色分组if计算绿色分组的丢弃概率以概率丢弃到达的绿色分组,RIO-C算法,if丢弃所有到达的绿色分组elseif黄色分组if计算黄色分组的丢弃概率以概率丢弃到达的黄色分组if丢弃所有到达的黄色分组elseif红色分组if计算红色分组的丢弃概率以概率丢弃到达的红色分组if丢弃所有到达的红色分组,RIO-C算法,改进的RIO-C算法,虽然RIO-C算法能够实现服务区分，但仍有不足：低丢弃优先级分组数目变化除影响自身的分组丢弃概率外，还会影响高丢弃优先级分组的丢弃概率，对高丢弃优先级分组过分歧视，并使其难以获得足够的带宽。当网络处于较低业务流时，丢弃概率增长较快，致使网络资源没有得到充分的利用；相反，当网络处于较高业务流时，丢弃概率增长较慢，有可能导致网络拥塞。,改进的RIO-C算法,改进的RIO-C算法用的二次函数来平滑，这样可以使丢包率随着的增长以曲线的方式平稳变化，避免了原RIO-C算法丢包率随着线性的增长。相对于RIO-C算法，在拥塞较轻的情况下改进算法拥有较低的丢包率，而在当增大靠近最大阈值的时候，改进算法也能迅速的提高丢包概率，加大丢弃力度，能较快从严重拥塞状态得到解脱。,丢弃概率表达式如下所示：,改进的RIO-