（通信与信息系统专业论文）基于令牌桶测速的red改进算法.pdf

j b 宝蛮通太堂亟堂僮监塞生重撞要 中文摘要 摘要；随着网络的爆炸性发展，网络拥塞日益严重，网络服务质量差强人意 如何的解决网络拥塞、提高网络的服务质量，已成为目前研究的热点。 本文主要研究网络拥塞的解决方法。对r e d 算法及其改进算法的进行了比较、 分析和总结。提出了一种新的令牌桶实现方式，这种实现方式将令牌添加与网络 流量状况结合起来，能更准确地对网络流量进行评估；提出了一种改进的r e d 算 法，该算法能较好的稳定平均队列长度、控制网络时延和抖动，尤其在应对网络 突发流量时，算法在保证低时延、低抖动的前提下，提高了随机突发流的吞吐量， 优势明显；最后，本文对令牌桶、拥塞队列和r e d 的测试方法进行了分析和研究， 并通过实际的测试案例，对测试方法进行验证，对测试效果进行了总结。 关键词：r e d ；令牌桶；平均队长；时延；抖动；吞吐量 分类号：t n - 9 1 5 0 4 ，t p 3 9 3 - 5 3 3 a b s t r a c t a b s t r a c t ：w i t ht h ee x p l o s i v ed e v e l o p m e n to ft h en e t w o r k , n e t w o r kc o n g e s t i o ni s b e c o m i n gs e r i o u s l y n e t w o r k5 e 1 v i c e so a n tr e a c ha l la c c e p t a b l eq u a l i t y , h o wt os o l v e n 酏v o r kc o n g e s t i o n , i m p r o v en e t w o r kq u a l i t yh a sb e c o m eah o tr e s e a r c h t h i sp a p e rs t u d i e dt h en e t w o r kc o n g e s t i o ns o l u t i o n s b yr e s e a r c ho f r e da n di t s i m p r o v e da l g o r i t h ma n dc o m p a r i s o n , a n a l y s i st h e s ea l g o r i t h m , p u tf o r w a r da n e ww a y t oi m p l e m e n tt o k e n b u c k e t s c o m b i n i n gt h i sp u tf o r w a r d al l e wm o d i f i e dr e d a l g o r i t h m 皿ef l g wi m p r o v e da l g o r i t h mo a na d j u s tt h ed i s c a r d e dt h r e s h o l da n dd i s c a r d p r o b a b i l i t yw i t ht h ec h a n g e so f f l o w si m m e d i a t e l y , g i v e nah i g hs t a b i l i t yo f t h ea v e r a g e q u e u el e n g t ha n dc o n t x o lt h en e t w o r kd e l a ya n d j i t t e re x c e l l e n t l y f o rn e t w o r kr a n d o m f l o w , t h ei m p r o v e da l g o r i t l m a sh a v em a n yo b v i o u sa d v a n t a g e s , i te n s u r i n gl o wl a t e n c y a n dl o w j i t t e r u n d e rt h ep f e m i o f r a n d o mf l o wi ti n e r e s s ot h r o u g h p u to f t h ed e v i c e i na d d i t i o nt h i sp a p e rs t u d i e dt h et e s ti d e a so ft o k e nb u c k e t sa n dr e d ，a n d c o n c l u d e dt h ea c t u a lt e s tr e s u l t so f t h et e s t s k e y w r 0 r d s ：r e d ；t o k e nb u c k e t ；a v e r a g e _ l e n g t h ；d e l a y ；, j i t t e r ；, t h u o u g h p u t c i 。a s s n o ：t n 9 1 5 0 4 ，t p 3 9 3 5 3 3 图目录 图 c s f q 算法功能结构图。 8 l o 图3 w r e d 与r e d 丢弃原理图1 1 图4 w r e d 的丢弃流程图 图5 c i s c o 的令牌桶的结构 图6 当前实现方式的令牌添加流程2 0 图7 当前实现方式的报文转发流程 图8 新实现方式令牌桶的结构2 l 图9 新实现方式令牌添加与报文转发流程2 2 图l o 不同的令牌桶实现方式效果比较测试组网图2 3 图1 1 新的实现方式的效果图2 4 图1 2 原有实现方式的效果图2 4 图1 3 基于令牌桶测速的r e d 改进算法的工作流程2 6 图1 4 令牌桶测速的示意图2 8 图1 5 s e l f - c o n f i g u r a t i o nr e d 示意图。2 9 图1 6 动态r e d 示意图3 0 图1 7 基于令牌桶测速的r e d 改进算法示意图3 l 图1 8 基于令牌桶测速的r e d 改进算法示意图3 1 图1 9 基于令牌桶测速的r e d 改进算法示意图3 2 图2 0 利用令牌桶测速计算p a r am o d i 参数的流程3 3 图2 l 实验一拓扑图3 6 图2 2 队列长度为5 时改进r e d 和g e n g e l r e d 的效果比较图3 6 图2 3 队长为7 0 - 2 0 、5 0 - 3 0 、9 0 - 1 0 的改进算法和g e n g e l r e d 的比较3 7 图2 4 一条流时改进算法和g e n g e l r e d 算法平均队长比较图3 8 图2 5 五条流时改进算法和g e n g e l r e d 算法平均队长比较图3 8 图2 6 十条流时改进算法和g e n g e l r e d 算法平均队长比较图3 8 图2 7 三条流时改进算法和g e n g e l r e d 算法t o p 窗口比较图3 9 图2 8 改进算法和g e n g e l r e d 算法时延对比图 图2 9 改进算法和6 e n g e l r e d 算法抖动对比图4 0 图3 0 五条流时改进算法和g e n g e l r e d 算法吞吐量对比图4 0 图3 1 十条流时改进算法和g e n g e l r e d 算法吞吐量对比图4 l 图3 2 实验二拓扑图 图3 3 随机流量时改进算法和g e n g e l r e d 算法平均队长对比图4 3 图3 4 随机流量时改进算法和6 e n g e l r e 平均队长及当前队长对比图4 4 图3 5 随机流时改进算法和g e n g e l g e o 平均队长及当前队长对比放大图4 4 图3 6 随机流量时改进算法和g e n g e l r e d 算法吞吐量对比圈。4 5 图3 7 q o s 测试模型 图3 8 速率限制输入流量速率的选择区间 图3 9 计算方法示意图 图4 0 令牌桶测试拓扑图 4 6 图4 l 拥塞管理输入流量速率的选择区间。5 4 图4 2 队列测试拓扑图 图4 3 r e d 测试组网图 图4 4 r e d 效果测试拓扑图 图4 5 p c 网卡属性设置图 图4 6 e a s y b t 流量示意图 图4 7 使能w r e d 之前网卡的接收速率 图铝使能w r e d 之后网卡的接收速率。 6 2 6 3 6 3 6 4 图4 9 未使能w r e d 与使能w r e d 网卡的接收速率对比图。6 4 表目录 表格l 发送端3 a i 流量设置 表格2 接收端3 a 2 的流量速率 表格3 稳定后的流量速率 5 l 5 1 5 l 。5 2表格4b u r s t 的长度为2 0 0 0 0 表格5 不丢包的b u r s t 长度 表格6 丢包的妇t 长度。 表格7t 时间内收发包数量 表格8 统计流量速率确认报文标记正确。 5 2 5 2 5 3 5 3 5 7 5 7 表格9 统计报文总数确认报文标记正确 表格1 0 队列测试结果一 表格1 1 队列测试结果二 表格1 2 队列测试结果三 表格1 3 不配置r e d 的丢包情况6 0 表格1 4 起始丢弃队列长度为0 ，丢包概率l o o 的丢包情况6 0 表格1 5 起始丢包队列长度不为0 ，丢包概率1 0 0 的情况6 l 表格1 6 起始长度1 2 8 k ，结束长度5 1 2 k 时不同丢包概率下的丢包情况6 l 表格1 7 起始长度1 2 8 2 6 2 1 2 9 k 时不同丢包概率时的丢包情况6 1 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：墨_ 云雾 签字日期：加7 年肛月，日 导师签名： 恕孓镡 f 签字日期：私习年7 功2 7 日 j 丘京交通太堂亟堂僮诠塞独剑性直明 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名： 豢p 而形 签字日期： 矽甲年，月歹厂日 8 9 致谢 本论文的工作是在我的导师赵永祥副教授的悉心指导下完成的，赵教授严谨 的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢三年来赵 老师对我的关心和指导。 胡师舜老师悉心指导我们完成了实验室的科研工作，在学习上和生活上都给 予了我很大的关心和帮助，在此向胡师舜老师表示衷心的谢意。 陈常嘉教授、郭宇春副教授对于我的科研工作和论文都提出了许多的宝贵意 见，在此表示衷心的感谢。 在实验室工作及撰写论文期间，赵森、关学攀等f 司学对我论文中的n s 2 仿真 研究工作给予了热情帮助，在此向他们表达我的感激之情。 另外也感谢家人、朋友和同学的理解和支持使我能够在学校专心完成我的学 业。 1 引言 1 1 课题背景 计算机的普及和网络技术的飞速发展，给人民的生活带来了前所未有的 方便和快捷。i n t e r n e t 已成为全球性的信息基础设施，成为人民生活中不 可或缺的一部分。随着网络爆炸性发展，网络用户里指数增加，网络业务的 不断丰富，人民对网络的依赖程度和挑剔程度与日俱增。目前i n t e r n e t 的 服务质量在很多方面已经不能满足人们的需求，在这样的背景下q o s ( q u a l i t y o f s e r v i c e ) 技术应运而生。q o s 研究的主要方向是提出一种与业务无关的通用 的网络流量服务质量保证机制，在这种思路下，如何保证整个网络的总体q o s 性能是关键。q o s 是一项系统工程，需要各个转发节点的参与。典型的i e t f 提出的d i f t s e r v ( d i f f e r e n t i a t e ds e r v i c e s ) 模型”，又称为区分服务模型。为在 各个单点解决q o s 提供了思路。区分服务模型实现简单，扩展性好，在口网 中得到了绝大部分厂家的支持。其具体实现技术包括分类、重标记、速率限 制、流量整形、拥寨避免、队列调度等。目前主要的研究成果除了区分服务 ( d i f f s e r v ) 还有集成服务( i n t s e r v ) 体系架构。 用户的指数增长和固有的网络服务能力造成了越来越严重的网络拥塞。 拥塞是影响数据传输、造成时延、抖动和吞吐量等q o s 性能指标下降和带宽、 缓存等网络资源利用率降低的关键因素。如果不在互联网中使用拥塞控制算 法，拥塞崩溃的发生会严重降低网络的性能。网络中的拥塞来源于网络资源 和网络流量分布的不均衡性，拥塞不会随着网络处理能力的提高而消除，所 以在互联网中使用的拥塞控制算法对于互联网的稳定具有十分重要的意义。 拥塞控制算法的分布性、互联网的复杂性和对拥塞控制算法的性能要求又使 拥塞控制算法的设计具有很高的难度。虽然学术界在拥塞控制领域已经开展 了大量的研究工作，但是到目前为止拥塞的问题还没有得到很好的解决。 在传统的t c p f l p 网络中，所有的数据包的传输都是采用先进先出( f i f o ， f i r s ti n , f i r s to u t ) 的调度算法。当网络拥塞时。简单的把数据丢弃来处理拥塞。 在早期网络数据量和关键业务数据不多的时候，这种调度算法并没有体现出 非常大的缺点，但是随着计算机网络的发展。数据量的急剧增长，尤其是多 媒体，v 0 1 p 数据等对延时要求高的应用的增加，这种简单的无差别的丢弃数 据包的处理方法会造成高时延、高抖动以及t c p 全局同步问题 2 1 。 目前玳t e r n e t 上9 5 的数据流使用t c p 口协议，因此对t c p ，口拥塞 控制的性能是确保i n t e r a c t 稳定性的关键因素之一，也是各种管理控制机制和 应用的基础。在拥塞控制的源算法方面，大量的工作也是集中在对t c p 协议 的研究上。近年来，t c p 中采用了很多新的算法包括慢启动( s l o ws t m ) 【3 】、 拥塞避免、快速重传( f a s tr e a n s m i t ) 【3 1 、快速恢复( f a s tr e c o v e r y ) 4 1 、选 择性应答( s a c k ) 5 1 等，大大提高了网络传输的性能。目前，源算法方面的 研究热点包括【6 】：对“慢启动”过程的改进；基于速率的控制策略；a c k 过 滤；减少不必要的“超时重传”和“快速重传”；e c n ( e x p l i c i tc o n g e s t i o n n o t i f i c a t i o n ) 的使用；t c p - f r i e n d l y 的拥塞控制；在特殊网络环境( 如无线链 路、卫星链路和非对称链路等) 中的拥塞控制。 链路算法的研究目前集中在“a q m ( 主动队列管理) ”算法方耐7 ，s 9 - 0 1 ， 和传统的“队尾丢弃”( d r o p t a i l ) 相比，a q m 在网络设备的缓冲溢出之前就 丢弃或标记报文。a q m 的主要优点是：减少网关的报文丢失；减少报文通过 网关的延迟；避免l o c k - o u t 行为的发生。a q m 的一个代表是r e d 7 1 研究表 明r e d 比d r o p t a i l 具有更好的性能。但是r e d 的性能对算法的参数设置十 分敏感i s ，至今还没有在互联网中得到广泛的使用。近年来，非线性规划理论 【i l l 和系统控制理论【卅被引入到拥塞控制的研究中来，一些研究者尝试使用严格 的数学模型来描述由端系统和网关共同组成的系统，这对拥塞控制的研究有 很大的推动作用。另外，在a q m 方面又提出了一些新的算法，如p l f l 2 1 、r e m ( r a n d o me x p o n e n t i a lm a r k i n g ) t t 3 、a v q ( a d a p t i v ev i r t u a lq u e u e ) 【1 4 】等。 但是这些算法在实用性方面还存在一些问题，需要进一步的研究【2 l 】。 实现区分服务的队列管理算法方面，目前还没有提出十分有效的算法。 目前常用的算法包括：p a d 切( r e d i na n d o u t 和w r e d ( w e i g h t e d r e d ) 。 这些算法都使用在网络的核心节点上。不幸的是它们都有着很明显的缺陷， 如：参数配置比较困难；不能实现“比例区分模型”；不能适应广泛的网络环境 等。虽然拥塞控制和区分服务有着不同的研究目标，但是它们之间的关系是 密不可分的如何将主动队列管理算法应用到区分服务体系结构中是一个很 好的课题。 互联网中数据传输的公平性一直是一个很受关注的问题。从用户的角度 出发，每个连接应该获得相同的吞吐量，而不管这些连接的“往返延迟”限肌 r o u n dt r i pt i m e ) 和通过拥塞网关数目是否相同。目前在互联网中，公平性主 要通过端系统和中间系统之问的协调来实现。具体说就是t c p 中的a i m d 策 略。在为多媒体传输而专门设计的t f r c 机制中，实现t c pf r i e n d l y 的目的也 是为了继续保持网络中传输的公平性。但是t c p 在“往返延迟”不同的情况下 2 和多拥塞网关的情况下会出现传输的不公平的现象，这是一个需要解决的问 题【2 l 】。另外，在互联网变的很庞大之后，要求每个用户都自觉的使用规定的 机制来传输数据也变得越来越困难。如何在这种新的环境中继续保持互联网 传输的公平性是一个很大的挑战。 1 2 论文的主要工作 拥塞控制的主要目标就是【4 】： 1 通过随机丢弃或标记分组来通知源端采取措施避免可能发生的拥塞； 2 公平地处理包括突发性、持久性和间隙性的各种t c p 业务流； 3 避免多个t c p 连接由于队列溢出而造成同步进入“慢启动”状态； 4 维持较小的队列长度，在高吞吐量和低时延之间做出合理平衡。 目前，在s a l l y 的r e d 的基础上提出的拥塞控制的改进算法，主要体现在 两方面：一是调节r e d 的配置参数，修改概率计算函数；二是注重公平性和 稳定性的研究改进。 本文在总结拥塞控制算法的基础上，提出了一种基于令牌桶测速的r e d 改进算法，这种算法在队列的保持、吞吐量、时延和抖动之间作了均衡，能 较好维持队列的长度稳定，在保证吞吐量的前提下有效的减小了时延和抖动。 主要工作： 1 总结r e d 的各种变种算法的技术特点及其性能表现； 2 提出一种新的令牌桶实现方法，并对其效果进行分析； 3 详细论述基于笔者设计的令牌桶实现方式，利用令牌桶测速实现的 r e d 算法原理、实现及其在n s 2 上仿真分析； 4 对笔者在测试q o s 中的有关令牌桶、队列管理和r e d 的测试方法做 了研究、分析和实践。 1 3 论文的组织 本论文一共分为6 章。第一章是引言，这部分对互联网端到端拥塞控制的研 究现状和课题的意义作了概述，并对论文所作的工作进行概述第二章对r e d 的 各种变种算法进行了总结、归纳和比较分析，指出各种算法的技术特点及其性能 表现，为论文的研究工作做了充分的铺垫，指明了论文研究的合理方向。第三章 介绍了令牌桶的工作原理，对目前主流厂商的实现作了概述。在此基础上，提出 了一种新的令牌桶实现方式，并对实现的效果进行了实验分析。第四章详细介绍 3 基于令牌桶测速的r e d 改进算法原理和实现流程，并对算法在n s 2 种的仿真结果 和改进算法的性能表现进行了系统的全面的分析。第五章对q o s 中关于令牌桶、 队列管理和r b d 的测试方法做了研究，并对测试方法作了实际的验证和分析。最 后一章总结全文，指出下一步的研究方向。 4 2r e d 研究现状及改进算法概述 1 9 9 3 年s a l l yf l o y d 等人提出了随机早期检灏 ( r e d , r a n d o me a r l yd e t e c t i o n ) 的 丢弃机制f l 】，为解决拥塞控制提供了新的思路。由于r e d 算法初衷的局限性，该算 法存在两个很重要的缺陷。一个是对于参数的设置很敏感，改变参数的设置会对 性能产生很大的影响，目前对于r e d 参数的设定仍没有明确的设定方法；另一个 是随着网络中“流”数目的增加，r e d 不能对流之间进行公平管理。针对这两种 缺陷，各种各样的改进和变种算法，如雨后春笋般涌现出来。根据算法针对性和 侧重点的不同，这些改进或变种算法可以分为以下三个方向： 1 修改r e d 配置参数或丢弃概率曲线； 2 改进流的公平性； 3 改进算法的稳定性。 针对修改参数设置或丢弃概率曲线的有：c r e d 垌、a r e i ) 【2 孤、d w r e d 1 8 】等 算法；针对流公平性进行改进有：f r e d 1 9 1 、b r e d t 2 0 l 等算法；针对算法稳定 性的有：w r e d i s 堋1 、s p e d f l 9 1 、s e l f - c o n f i g u r a t i o nr e d l 2 2 等算法。此外还有针对 i e t f 模型的r lo f 2 射、q p r e d u 等算法。下面对上述算法的特点及其性能进行分析 和比较。 2 1 针对r e d 参数设置提出的改进算法 自适应的随机早检测机制( a l 也d ) 】和动态的随机早检测机制( d r e d ) 都是 通过动态的调节r e d 参数实现的改进算法，这两种算法目标是：使平均队列长度保 持在某一个目标长度t a r g e t 附近，从而使网络流量更平稳。但是算法实现的关注 点不同。 2 1 1a r e d 算法 a r e d ( a d a p t i v er e d ) 算法的拥塞指示的发送速率是由参数m a xp 来体现的 如果m a xp 太大，那么丢包比例主要就是由于早期拥塞检测中产生的丢包造成的； 如果m a xp 太小，丢包主要就是由于队列溢出造成的。r e d 的一个缺点就是平均 队长对流量负荷和参数设置很敏感，导致队列长度波动较大，结果造成平均排队 时延对流量负荷和参数设置很敏感。 a r e d 提出了一种自动配置机制，根据流量的变化来配置参数m a xp 。其基 5 本思想是根据平均队长的变化来，判断r e d 是应更激进还是更保守，从而尽量保 持平均队长在m i n 和m a x 之问。具体的说就是，如果平均队长是在m i i lt h 附近 振荡，说明拥塞控制太激进了，那么就减小m a xp ( m a xp = l v l a xp q ) ；如果在 m a xt h 附近振荡，说明拥塞控制太保守了，那么就增大m a xp ( m a xp f m a x 矿 b ) ，其中 d l 。a r e d 是对r e d 改动很小的一种算法，它保留了r e d 的基 本结构，只需调节参数m 甄p ，从而保持平均队长在m 缸t h 和m a xt h 之阀，消 除了鼬d 的队列延时问题和参数敏感性问题。 a r e d 是对r e d 改动很小的一种算法，它保留了r e d 的基本结构，只需调 节参数m a x p 从而保持平均队长在r a i nt h 和m 甑t h 之间，消除了r e d 的队列延 时问题和参数敏感性问题。但其自身也带来了参数设置问题。a 、1 3 设置太大，m a x p 振荡过于频繁，不利于网络性能稳定；a 、p 设置太小，m a x p 就要经过多次调整荡 才能达到期望值。 2 1 2d r e d 算法 动态r e d ( d r e d , d y n a n d cr e d ) 根据队列长度的变化，动态调节丢弃门限 值，从而实现对不同队列的报文进行不同丢弃。 动态r e d 算法为不同优先级队列分配了不同的丢弃门限，其中丢弃门限的上 限在初始化时确定为一个固定值，不随网络拥塞状况而变化下限值随着网络拥 塞状况，按照事先定义的调节幅度，在最小值n m 缸和最大值8 m 缸之间离散变化。 本地实体按照拥塞状况动态调节r e d 参数，使之较好的适应网络流量变化该算 法可以表示为： 1 当a r g , s 0 时减小一个s t e p 步长，最小值为n m i n ( t ) ： 2 当a v g , m a xt h 时，标 记该流的概率就会大大增加。如果流对拥塞通知没有反应的次数s t r i k e 大子1 ，说 明该流为非适应流，那么就不允许该流占用的队长q l e n 超过每流的平均队长a v g 。 从而保护适应流，惩罚非适应流。但是，f r e d 也存在以下的缺陷： 1 f r e d 算法是与状态相关的，不适宜大型网络和核心路由器； 2 f r e d 对n o n - a d a p t i v eu d p 流的抑制矫枉过正，只要f l o w 中缓冲的分组 数超过允许缓冲的最大分组数m a x ，以后到达的分组就会被全部丢弃。这 在抑制u d p 流的同时也限制了基于u d p 的多媒体应用，不能适宜网络多 媒体化的发展趋势； 3 m a x a 不能随网络负载的变化而动态变化，使得算法不能适应网络负载的 变化情况。 2 2 2c s f q 算法 c s f q ( c o r e - s t a t e l e s sf a i rq u e u e i n g ) 算法 1 0 , 1 1 1 是针对带宽享用的公平性提出 的一种分布式算法。它把网络中的路由器区分为边缘路由器和核心( 非边缘) 路 由器，在其上分别执行不同的动作。 c s f q 算法在边缘路由器处保持每个流的状态信息，对于每个进入网络的包， 边缘路由器判断它所属的流并根据所记录的流状态估计该流的速率，然后在包头 部插入一个标签来记录这个估计值。核心路由器不再保存流的状态信息，当有包 到达时，它和边缘路由器都使用f i f o 队列进行包调度，包的丢弃概率依赖包头的 7 标签和此时路由器处平均份额速率( f a i rs h a r er a t e ) 。同时，核心路由器还负责根 据本地的业务流量汇聚信息重写包头标签的内容边缘路由器和核心路由器的功 能结构图如图l 所示，其中，r i ( t ) 和a ( t ) 分别表示t 时刻流i 的估计速率和路由器处 的平均份额速率。 圈l c s f q 算法功能结构图 f 哂1r o w c h a r t o f c s f q c s f q 算法主要有以下四个重要的模块。 ( 1 ) 流到达速率的估计 c s f q 在边缘路由器处使用指数平均来估计流的速度r i ，指数平均能够更准确 的反映流的变化，并且不受具体包结构的影响。每次有新的包达到，：作如下更新： ，k = ( 1 一膳) 善+ e - z * , f 其中t t k - - t i k - t i k - 1 ，是前后两个包到达的时间差。k 是常数。 ( 2 ) 平均份额速率a ( t ) 的估计 啪依赖于业务在该处的汇聚流量。为了计算a ( o 的估计值a ，( t ) ，先定义包的 接收速率f “t ) ) ，本地的总到达速率a ( t ) 和链路输出速率c 。 ，( 口( f ) ) = n c m ( r , ( t ) ，口( f ) ) 一( f ) = ( d f 和a ? 分别表示接收速率和总到达速率的估计值。当链路拥塞( a ( f ) c ) 时， f ( x 即的唯一解就是a ( t ) ；否则，当链路不拥塞( a ( 嗲 c ) 时， a ( t ) = m a x l - - i = n ( r i ( t ) ) 。有包到达时，f 和臀也采用类似r j 的方法进行更新。 ( 3 ) 丢弃概率的计算 对属于流i 的包，记其丢弃概率为p ，则： p 2 m a x ( o i 一鬻) ( 4 ) 重写标签 如果某个流的一些包被丢弃，则余下包的标签中便不再是对流速率的准确估 计。这时需要重写标签。此时已经不知道每个流的状态信息，因此无法用原来的 估计算法。由以上的描述可知，出队速率是入队速率和平均速率中的较小者。所 以，新的标签l n e w 由厶。= m i n ( 上钳，口( f ) ) 给出。 c s f q 算法只需要在边缘路由器处记录流的状态，大大减轻了核心路由器的负 担。当流的数目较大时，c s f q 能很好的处理突发的t c p 业务，因为一旦有突发 业务，一段时间后估计速率才能赶上实际速率，在这段时间内，即使流的实际速 率高于平均速率，该流的包也有可能被允许入队。从网络结构上讲，c s f q 和 d i 妇 s e f v 模型，m p l s ( m u l t i p r o t o c o ll a b ds w i t c h ) 模型一样都在边缘路由器进行 分类标记工作，而后两者是未来骨干网络的发展趋势，这使c s f q 能更好的和它 们结合。但是，c s f q 需要边缘路由器记录所有存在过的流的信息，当网络规模较 大时，边缘路由器可能会不堪重负。该算法在核心路由器处的复杂性和此处的活 动流数目有关，所以在大规模的网络中要求核心路由器有高速的计算能力。另外 值得注意的是，c s f q 算法中缺乏有效的队列管理机制，它不能像r e d 和b l u e 等算法一样在拥塞发生前探测到拥塞的逼近并避免拥塞。 2 2 3c h 眯e 算法 c h o k e ( c h o o s ea n d 融砷f o rr e s p o n s i v ef l o w s , c h o o s ea n dk i l lf o r u n r e s p o n s i v ef l o w ) 算法【1 2 l 是目前花销最小的针对公平性的主动队列管理算法。它 借鉴了l d q ( l o n g e s tq u e u ed r o p ) 算法【l3 】优先丢弃队列中较长的流的思想。 c h o k e 算法基本思想是：把路由器的缓冲f i f o 队列的内容看作是已到达业 务的“有效统计”，基于该统计当包到达拥塞的路由器之后，c h o k e 算法会从缓 存队列中随机的取出一个数据包和这个到达的数据包进行比较，如果这两个包属 于同一条流，那么这两个包都将被丢弃；否则，从队列中随机选取的数据包被完 好的保存在队列中，新到达的报文以概率p 进入队列。概率p 的大小和当前队列 拥塞的状况有关，其具体的计算方法和r e d 相同。这样做的目的就是在队列中存 在的数据包大部分都会是那些“不守规矩”流的报文，这样，这些“不守规矩” 流的数据包被选择比较的几率就比较大，被丢弃的概率也会加大，从而保护了流 之间的公平性( 此概率依赖于拥塞程度，和r e d 中的算法一致) 。其算法流程如 图2 所示。 根据非响应流的特性可知，缓冲队列中存在非响应流的包的可能性较大，所 以很有可能被选出来与新到达的包做比较。而且较之响应流，属于非响应流的包 到达次数更多，更容易触发比较。因此，非响应流的包被丢弃的可能性要大于响 应流的包。c h o k e 就是以这种机制来实现对非响应流的惩罚以解决带宽占用的公 9 平性问题。类似r e d 算法，c h o k e 中也预先设定了缓冲区的最大阀值m a x t h 和 最小f 困值m i n t h 以及丢弃概率的最大值m a x p 。当新的包到达缓冲队列时，c h o k e 使用指数滑动平均计算队列的平均长度a v g ，如果a v g 小于m i n t h ，允许该包进入 缓冲对列；如果a v g 大于m a x t h ，丢弃所有新到达的包# 当a v g 在m i n t h 和m a x t h 之间时，触发比较机制。 在存在多个非响应流的情况下，适当增加丢弃候选包的个数可以大大提高 c h o k e 算法的性能。实现时，对流d 的比较可以由硬件来完成；候选包的丢弃， 并不是真的在缓冲区中将其丢弃，而是在该包的包头多加一位标记，直到队列的 出口处，依据该标记包才被丢弃。因此，c h o k e 算法实现简单，路由器不需要保 存任何流的状态信息。但是由于对候选包的选择与各流的状态无关，完全是随机 的，所以该算法并不能识别出非响应流，它对非响应流的惩罚也是基于概率的， 这使得c h o k e 算法在公平性上比基于流状态的算法要差，但是却优于传统的r e d 等算法。在没有非响应流存在的情况下，c h o k e 的性能和r e d 相似。 圈2 c h o k e 算法流程图 f 幻2f l o wc h a r to fc h o k e 2 3 针对算法稳定性提出的改进算法 基l 墅班究强拭厦改进簋法抠述 2 3 1w r e d 算法 针对i e t f 提出的区分服务( d i f f - s e r v e ) 策略引入了具备加权功能的w r e d 8 1 0 1 丢弃机制。在w r e d 丢弃机制中对不同优先权数据，采用不同的丢弃策略。对低 优先级报文的丢弃概率大于高优先级的报文。每一个丢弃策略都包含有r e d 的三 个参数：下限阀值、上限阀值以及最大丢弃概率。每一丢弃策略丢弃报文的原则 和r e d 相同。图3 给出了w r e d 和r e d 丢弃原理的比较图，通过对比很容易理 解w r e d 丢弃的原理。在图4 种给出了w r e d 的丢弃流程图，该丢弃流程为c i s c o 设备的w r e d 采用的丢弃流程。目前w r e d 优先权可以根据d s c p 和m 优先级 进行划分。 曩a 圈3 w r e d 与r e d 丢弃原理图 f i g3 p r i n c i p l eo fw r e d a n dr e dd i s c a r d 圈4 w r e d 的丢弃流程圈 f i g4f l o wc h a r to fw r e dd i s c a r d o 蛳 妇 j e 塞銮煎盍堂亟堂焦监塞 2 3 2b l u e 算法 b l u e 1 4 1 与r e d 最大的区别在于前者使用实际队长来反映拥塞状况，并且使用 丢包事件和链路空闲事件来管理拥塞，而r e d 则使用平均队长。b l u e 使用了一 个概率p 用以丢弃数据包。如果由于队列溢出导致连续地丢包，b l u e 就增加p ， 这样会使更多的数据包被丢弃，也增加了向源端发送拥塞通知的速度。相反，如 果由于链路空闲导致队列空，b l u e 就减小p 。这样b l u e 就能有效地控制发送拥 塞通知信息的速度。为了避免丢包过于激进，b l u e 设置了一个最小时间问隔f r e e z e 矗m c 在该时间间隔内，概率p 只能更改一次。b l u e 另外定义两个重要参数 d l 、北。d l 定义了当队列溢出时p 增加的量，d 2 定义了当链路空闲时p 减少的量 一般来说，d l 要比d 2 大很多，这主要是因为通过赋予丢包事件更大的比重，b l u e 能够对流量的增加迅速地作出反应这种算法与r e d 相比丢失率更低，链路的利 用率较高，但算法的稳定性存在问题。 2 3 3s r e d 算法 s v e d t s l 设计的目的是保持f i f o 队列长度的稳定而与活跃流( a c t i v ef l o w ) 数量 无关其基本思想是进行比较。当有一个包到达队列时，就从队列中随机选出的 一个包进行比较，若这两个包属于同一个流，则称为“击中”( h i t ) 。s r e d 设计了 一种数据结构，称为z o m b i el i s t ，相当于一种流c a t , h e ，其中记录了最近流经该队 列的m 个流。每个z o m b i el i s t 包含了两个状态信息，其中c o o a t 表示被击中的次 数；时问戳则记录了该z o m b i e 产生的时间或最近一次被“击中”的时间( c o u a t 大 于o ) 起初列表为空，当有一个包到达时，则将该包的流标识( 源、目的地址等) 加入列表，这样，就产生了一个新的z o m b i e 一旦z o m b i e l i s t 满了，那么就将新 来的数据包和z o m b i el i s t 中随机选出的z o m b i e 进行比较：( 1 ) 如果击中，则此 z o m b i e 的c o t i n t 加l ，时间戳改为当前的时间；( 2 ) 如果未击中，则以某个概率用 新数据包的流标识覆盖选出来的z o m b i e 。$ r e d 用一个函数h i t ( t ) 来记录第t 个包 是否击中，如果击中，则h i t ( t ) 取值为l ，否则为0 然后计算第t 个数据包到达时 击中的概率p ( t ) ： p o ) = o a ) p ( t 一1 ) + 础i t ( o ，0 口“l ( 1 ) 其中口是一个常数。p ( f ) 1 可以被认为是在第t 个包到达前很短时间内对活跃流数 量的估计计算数据包的丢弃概率依赖于队列的占用情况和活跃流的估计值。 ip 。( i 3 ) b s q b p 耐( g ) = ( 1 4 ) p r o , 0 6 ) b q ( 1 3 ) b ( 2 ) 【0 q ( 1 1 6 ) b 1 p 一2p ( g ) m i n ( 1 ，面韶 3 ) 其中，b 是队列大小，q 是当前队列长度。p 脚为丢包概率，对连接数的变化不敏 感。 2 3 4s e l f c o n f i g u r a t i nr e d 算法 s e l f - c o n f i g u r a t i n r e d i s 算法通过m i nt h 和m a x _ t h 把整个区间分成了三段。 如果平均队长a v g 小于m i nt h 称丢弃状态为b e l o w ，如果a v g 大于m a x _ t h 则称 丢弃状态a b o v e ，在a v g 位于m i nt h 和m a x _ t h 之间的时候丢弃状态为b e t w e e n 。 根据丢弃处于不同的状态调节不同的丢弃概率，当位于b e t w e e n 状态是丢弃概率 为p ，当位于b e l o w 时丢弃概率调节为p a ，当位于a b o v eh 寸丢弃概率调节为p b 。 i f ( m i n m q ( a v e ) = m a xo u t ，m a xpo u t m a xpi n ，并且h 包的 丢包率依赖于h 包的平均队长a v & ，而 包的丢包率依赖于总的平均队长_ q l i n o u t