（无线电物理专业论文）基于区分服务的队列管理研究.pdf

中山大学硕士学位论文 基于区分服务的队列管理研究 专业： 硕士生： 指导教师： 无线电物理 周婷 秦家银教授 摘要 区分服务模型通过优先级策略实现相对q o s ，是解决口网络服务质量问题的 主要解决方案之一。在区分服务的体系结构中，队列管理通过丢包来控制队列长 度，是拥塞控制中的重要机制。虽然区分服务与队列管理有着不同的研究目标， 但是两者密不可分。通过在队列管理算法基础上扩展对各矛中流量的处理，我们可 以实现基于优先级的可区分服务。其中，确保转发( a f ) 队列管理的实现是区分服 务的重要研究课题。 本文对队列管理机制及在区分服务模型中的应用问题进行了研究。首先对网 络拥塞控制进行了分析和综述，总结了目前主要的主动队列管理算法。然后在二 维两类分类i i ( t c c ) 算法基础上提出基于区分服务的队列管理算法。本文指出了 原t c c 算法的优缺点，并在此基础上做如下两种改进：针对算法中有限样本和静 态参数的问题，构造了基于主动学习的分类丢弃法；针对不同的q o s 要求，提出 了具有可区分性的子队列管理算法。 在o p n e t 网络仿真环境下对本文中提出的算法进行了仿真实验，结果表明改 进后的算法丢包率减小，并且具有较好的服务可区分性，取得了预期的研究成果。 关键词：区分服务，主动队列管理，服务质量，分类，线性判别 r e s e a r c h e so fq u e u em a n a g e m e n ti nd i f f s e r v m a j o r ： r a d i op h y s i c s n a m e ：z h o ut i n g s n p e r v i s i o r ：p r o f q i nj i a 一 f i n a b s tr a e t d i f f s e r vm o d e li sap r i n c i p a ls o l u t i o no fi pq o s ，w h i c hi m p l e m e n t sr e l a t i v eq o s u s i n gp r i o r i t yp o l i c y i nd i f f s e r va r c h i t e c t u r e ，q u e u em a n a g e m e n ti s a ni m p o r t a n t m e c h a n i s mo fc o n g e s t i o nc o n t r o l ，w h i c hd r o p sp a c k e tt oc o n t r o lq u e u es i z e a l t h o u l g h d i f f s e r vm o d e la n dq u e u em a n a g e m e n th a v ed i f f e r e n t g o a l s ，t h e yg e t l o t so f c o n n e c t i o n s b ye x t e n d i n ga c t i o n st oa l lk i n d so ft r a f f i c ，d i f f e r e n t i a ls e r v i c e sb a s e do n d i f f e r e n tp r i o r i t i e sc o u l db ea c c o m p l i s h e d i m p l e m e n tm e c h a n i s m st oa c h i e v ea yp h b i nd i f f s e r vm o d e lc o n s t i t u t eas i g n i f i c a n tr e s e a r c ht o p i c i nt h i sp a p e r , q u e u em a n a g e m e n ti nd i f f s e r vm o d e lh a sb e e ns t u d i e d t h e p r i n c i p l e so fc o n g e s t i o nc o n t r o lm e c h a n i s m sa r ci n t r o d u c e df i r s t l y ，a n ds o m eo ft h e c u r r e n tp r e v a l e n tq u e u em a n a g e m e n ta l g o r i t l m a sa r ed i s c u s s e d a f t e rb e i n ga n a l y z e dt h e a d v a n t a g e sa n dd i s a d v a n t a g e s ，t w o c a t e g o r yc l a s s i f i e r ( t c c ) a l g o r i t h mi si m p r o v e d i nt w ow a y s o no n eh a n d ac l a s s i e r - d i s c a r d e rb a s e do na c t i v el e a r n i n gm e t h o di s c o n s t r u c t e dt oa p p r o a c h i n gt h ep r o b l e mo fl i m i t e ds a m p l e sa n ds t a t i cp a r a m e t e r s o n t h eo t h e rh a n d ，as u b q u e u em a n a g e m e n ta l g o r i t h mw i t hd i f f e r e n t i a t e dp e r f o r m a n c ei s p r o p o s e df o rt h ep u r p o s eo f d i f f e r e n tq o sr e q u i r e m e n t s t h es i m u l a t i o no ft h ea l g o r i t h mi nt h eo p n e ts h o w st h a tt h ei m p r o v e da l g o r i t h m g i v e s ab e t t e rp a c k e tl o s sr a t i ot h a nt h eo r i g i n a l o n e ，a n dp r o v i d e ss a r i s f y i n g d i f f e r e n t i a t e dp e r f o r m a n c e i tp r e s e n t sas t r e n g t h e ns u p p o r tt ot h ea n t i c i p a t e dr e s u l t so f t h ea n a l y s i s k e yw o r d s ：d i l t s c r v ，a c t i v eq u e u em a n a g e m e n t ，q o s ，c l a s s i f i e r , l i n e a r d i s c r i m i n a t i o n 中山大学硕士学位论文 1 1 研究背景 第1 章引言 在对i pq o s 呼声越来越高的今天，区分服务( d i f f e r e n t i a t e ds e r v i c e s ，d i f f s e r v 或d s ) 模型“2 1 的思想已经被广泛应用到网络核心及边缘部分，并且被认为是解决 i p 网络服务质量问题( q u a l i t y o f s e r v i c e ，q o s ) 的主要解决方案之一。但是，由于 i n t e m e t 上多媒体业务的不断增长，以及数据传输突发性的特点，网络容易出现拥 塞现象，其解决方法是采用拥塞控制，即在网络节点处采用丢弃策略，通过决定 哪些包被丢弃来分配缓存。i ：e t f 已经建议采用主动队列管理算法( a c t i v eq u e u e m a n a g e m e n t ，a q m ) t 3 】实现拥塞控制并保持较高的链路利用率。 区分服务与拥塞控制有着不同的研究目标，但是它们之间的关系密不可分。 主动队列管理不仅可以通过减小丢包率，减小端到端延迟，以及提高吞吐量等方 式来支持q o s ，而且还可通过对不同业务实施不同的队列管理机制来达到区分服 务的目的。因此，面向拥塞控制的主动队列管理算法的思想可用于区分服务模型 中，主要是在原主动队列算法基础上扩展实现对各类流量的处理，以实现不同优 先级流量之间的服务区分性。 1 2 区分服务体系结构 d i f f s e r v 体系模型的核心思想是：在网络边界将数据流按q o s 要求进行简单 分类，标记到口v 4 的t o s 字段或者i p v 6 的t c 字段，作为d s 字段。8 位的d s 字 段中，低6 位( o - 5 位) 用作区分服务编码点( d i f f s e r v c o d e p o i n t ，d s c p ) ，高2 位( 6 、 7 位1 保留。被标记的不同的类别在内部节点的每次转发中实现不同的转发特性， 即不同的“每跳行为”( p e r h o p b e h a v i o r ，p h b ) 4 l 组。d i f f s e r v 体系使得 i s p ( i n t e r n e ts e r v i c e p r o v i d e r ，i n t e r n e t 服务提供者) 能够提供给每个用户不同等 级和质量的服务。但是区分服务本质上只是实现了一种相对优先级策略，因此并 第l 章引言 不能严格保i f _ q k 务端到端f e j q o s 。 在d i f f s e r v 体系中定义t - - 种p h b ，分别为尽力而：, j ( b e s te f f o r t ，b e ) 、加速 转发( e x p e d i t e df o r w a r d i n g ，e f ) 和确保转发( a s s u r e df o r w a r d i n g ，a f ) 。 其中，加速转发为用户所提供的服务质量由用户事先与i s p 通过s l a ( s e r v i c e l e v e ia g r e e m e n t ，服务等级约定) 防商。如果用户传输的分组的质量要求超出协 定，则分组将被丢弃，而其它遵守协议的分组则进入f i f o 队列等候服务。由于 e f 为用户提供低延时、低抖动、低丢失率，以及保证带宽的端到端的传输服务， 因此主要用于实时服务。 而确保转发是提供比尽力而为服务尽可能好的服务质量，它与尽力而为服务 的区别在于当网络拥塞时先丢弃尽力而为分组。a f 为用户提供不同级别的业务 转发，用户实际得到的带宽分为两部分，一部分是用户与i s p 约定的最小保证值， 另一部分是用户传输的流与其它流竞争剩余资源获得的额外带宽。a f 定义了4 个 服务类，每一种a f 类在d s 节点上占有一定的转发资源( 内存空问和带宽) ，每种 服务类又包含3 个丢弃优先级别。在队列管理中，同- - a f 类不同丢弃优先级的分 组共享一个队列。a f 可以用来为包含速率适应机制、对包丢失有反应的应用f 如， 使用t c p 的应用) 提供区分服务。 d i f f s e r v 的特点是，它针对业务流的种类，具有良好的可扩展性；由于只需 要进行数据包的调度转发，而其分类、标记和整形等复杂处理都在网络的边缘完 成，大_ 人降低了核心路由器的性能要求。其实现简单，扩展性好的特点，使得目 前在i p 网中得到绝大部分设备商的支持。 1 3 网络拥塞及拥塞控制 拥塞发生的原凶是，网络中有限的资源被多个用户共享使用所导致的“供不 应求”。日f i 口i n t e m e t 上用户和应用的数量都在迅速增长，如果不使用某种机制协 调资源的使用，必然会导致网络拥塞。拥塞发生位置的不均衡反映t i n t e m e t 的不 均衡性。互联网中资源和流量分布的不均衡都是广泛存在的，由此导致的拥塞不 中山大学硕士学位论文 能使用增加资源的方法来解决，增加资源的某些方法甚至会使得问题变得更严重。 比如网关缓冲的增加会增大报文通过网关的延时，如果总延时超过源端重传时钟 值，就会导致报文重传，反而导致拥塞的加重。 拥塞控制【5 算法包含拥塞避免( c o n g e s t i o na v o i d a n c e ) 和拥塞控铝1 ( c o n g e s t i o n c o n t r 0 1 ) 这两种不同的机制。拥塞控制用于把网络从拥塞状态中恢复出来，两拥塞 避免的目标是避免网络进入拥塞状态，使网络运行在高吞吐量、低延时的状态下。 拥塞避免机制通过监视网络资源( 如队列) 的使用情况，在网络尚未发生严重过载的 情况下采取主动丢弃分组的策略，通过降低网络的负载来缓解或解除网络拥塞。 根据算法的实现位置，可以将拥塞控制算法分为两大类：源算法( s o u r c e a l g o r i t h m ) 和链路算法( 1 i n ka l g o r i t h m ) 。源算法在主机和网络边缘设备中执行，作 用是根据反馈信息调整发送速率，使用最广泛的是t c p 协议中的拥塞控制算法， 已经成为保证互联网稳定性的重要因素：链路算法在网络设备，如路由器和交换 机中执行，作用是检测网络拥塞的发生，产生拥塞反馈信息。链路算法的研究重 点目前集中在主动队列管理算法方面。 队列管理算法主要是在网络发生拥塞时通过丢包来管理队列长度，而对队列 长度进行管理直接影w l 自- n 路由器的拥塞控制能力； i q o s 能力。目前的队列管理机 制可以分为两大类：被动式队列管理( p a s s i v eq u e u em a n a g e m e n t ，p q m ) 和主动式 队列管理( a c t i v eq u e u em a n a g e m e n t ，a q m ) 。 传统的尾丢弃算法( d r o p t a i l ) 【6 】是一种被动式的队列管理方法，对每个队列以 包为单位设置一个最大值，然后接受包进入队列直到队长达到最大值，接下来到 达的包就要被拒绝进入队列直到队列空闲。由于这种方法是在队列满了之后被迫 丢包，因此称为被动式队列管理。虽然d r o p t m l 算法在当前i n t e m e t 上得到了广 泛的使用，但这种方法存在着以下几个问题： ( 1 ) 当网络发生拥塞时，只进行简单的拥塞控制，而不进行捌塞避免处理； ( 2 ) 在某些情况下，由于同步或其他定时作用的结果，算法会让某个流或者少 数几个流独占队列空问，阻止其他流的包进入队列，造成死锁现象。 第1 章引言 ( 3 ) n fd r o p t a i l 算法只有在队列满时才、会发出拥塞信号，队列在长时间内处 于满状态或几乎满的状态，因此i n t e r n e l 数据的突发性使得每个拥塞周期都会引 发网络中的t c p 全局同步现象。 在当前的i n t e m e t 二，丢包是对端节点进行拥塞通知的主要机制，解决被动式 队列管理问题的方法便是在队列满之前丢包，这样端节点便能在队列溢出前对拥 塞作出反应。这种方法便称为主动式队列管理。a q m 是i e t f 推出的基于f i f o 调 度策略的队列管理机制，它使得路由器能够控制在什么时候丢多少包，从而有效 地管理队列长度，以支持端到端的拥塞控制。a q m 的主要优点是： ( 1 ) 保持较小的队列长度，从而增强网关容纳突发流量的能力，减少包丢失： ( 2 ) 由于平均队列长度的减小，数据包在网络设备中的排队延时也将随之减小； ( 3 ) 避免死锁行为的发生。 自从i e t f 提出了a q m 技术以来，己产生了许多a q m 算法，a q m 的一个 代表是r e d ( r a n d o me a r l yd e t e c t i o n ，r e d ) f ”。研究表明r e d 比d r o p t a i l 有更好 的性能。但是r e d 性能对算法的参数设置十分敏感，至今没有在互联网中没有得 到广泛的使用。近年来，控制理论被引入到拥塞控制的研究中来，一些新的a q m 算法不断涌现。目前，国内外的研究大多处于理论研究，实验室仿真阶段。 加权随机早期检测( w c i 曲t e dr a n d o me a r l yd e t e c t i o n ，w r e d ) t s l 和具有t n 0 u t 的随机早期检测f r e dw i t hi n o u t ，r i o ) 1 9 1 从r e d 发展而来，是两个可以提供丢 失率区分的a q m 算法，并在区分服务结构核心路由器被广泛采用，实现保证转发 的主动队列管理机制。区分服务中a fp h b 的实现需要用到多级缓冲队列机制， 一般为3 级。多级缓冲队列的实现可利用r i o 算法的思想o ”1 ，利用多个r e d 队 列来计算分组达到的丢弃概率。由于a f 仅仅向用户提供统计性保证，并不能绝 对保证带宽的稳定性，因此对a f 队列管理机制的争议最大，也是研究中的重要 问题。 ! 些奎兰堕主堂垡堕壅 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ - - _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 4 论文主要工作 在队列管理算法的研究中，应用于区分服务体系结构中的主动队列管理算法 的研究是一个重要的课题。在论文工作期间，作者从队列管理的设计、队列管理 算法对q o s 的支持和服务的可区分性等方面，对网络拥塞问题进行了深入的研 究。论文安排如下： 首先，第1 章简要概述了区分服务体系结构、网络拥塞的发生原因和拥塞控 制原理，指出了研究的方向和目的。 第2 章介绍了一些经典的a q m 算法，包括r e d 及其改进( a p e d 、s r e d 和 d r e d ) 、b l u e 、p i 控制器和在区分意义上发展出来的r i o 和w r e d ，分析了算 法的优缺点并进行了比较，了解这些算法的特定对设计新的a q m 算法有指导意 义。 第3 章本章介绍了分类器的基本原理及几种常见的分类 法b a y e s 判别法、最近 邻法和k 一近邻法、f i s h e r 判别函数法，分析了二维两类分类法( t c c ) 在队列管理中 的应用及具体计算方法。 第4 章指出了队列管理中二维两类分类算法的几个问题，提出了解决方案。其 一是对分类器加入主动学习法进行参数调整，其二是用丢包率代替队长作为参数 调整的判断条件。本章作了仿真实验，并分析比较了原算法和改进算法。 中山大学硕士学位论文 第2 章主动队列管理算法 2 1 随机早期检测算法 2 1 1r e d 设计目标及算法实现 为克服尾丢弃算法的缺陷，提出了随机早期检测( r a n d o m e a r l y d e t e c t i o n ，r e d l 算法，以达到以下目标：最小化包丢失率和排队延迟；避免全局同步现象；避免 对突发业务的偏见；即使在缺乏传输层协议有效配合的情况下也能控制平均队列 长度，从而避免拥塞。 r e d 算法是目前应用最广泛的一种主动队列管理算法，已经被很多商业路 由器所采用。w r e d 、r i o 及其它主动队列管理算法都是基于r e d 发展起来的。 它通过以定概率丢失或标记报文通知端系统网络的拥塞情况。r e d 通过监控路 由器输出端口队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连 接来通知拥塞，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速 度，从而缓解网络拥塞。 在r e d 类算法中，为每个队列都设定一定下限和上限值，当队列的长度小于 下限时，不丢弃分组。 当队列的长度在下限和上限之间时，开始随机丢弃到来的分组。方法是为每 个到来的分组赋予一个随机数，并用该随机数与当前队列的丢弃概率比较，如果 大于则被丢弃。并且队列越长，随机丢弃概率越高。r e d 的目标是控制队列长度。 也就是说，r e d 能够使网络设备更加精确地管理其队列的长度。 当队列的长度超出上限规定时，丢弃所有到来的分组。 第1 章引言 丢弃概率p 6 最大丢弃概率 m a x p 最小门限 n q l n m 最大门限 m a x t h 平均队长 o 、g 图2 1r e d 算法 从上图可以看到，r e d 算法中预先设定三个门限值，m i n 曲、m a x m 和m a x 。 m i n t h 年t l m a x m 分别是队列欧度的最小门限值和最大门限值，m a x 。是随机丢弃概 率门限值，范围是0 m a x 。 1 。 r e d 算法有两个需要计算的参数。一个是平均队列长度a v g 。根据这个值与 两个队列门限r a i n 。和m a x 。相比较。一个是包丢弃概率只，根据该值与最大丢弃 概率m a x 。比较决定是否丢包。下面具体说明如何得到这两个重要的参数。 ( 1 ) 计算平均队列长度 r e d 采用指数加权滑动平均( e x p o n e n t i a lw e i g h t e dm o v i n ga v e r a g e ，e w m a l 来计算平均队长a v g 。路由器在每一个分组到达的时候计算a v g 。其计算方法如 下： a v g 卜a v g + w ( g a v g ) 公x t ( 2 1 ) 其中w 表示没定的权重，q 表示当前队列的实际氏度。这样由于i n t e m e t 数据 的突发本质或者短暂棚塞导致的实际队列氏度暂时的增长将不会使得平均队长有 明显的变化，从而过滤掉短期的队长变化，尽量反映长期的拥塞变化。 当队列为空队列时( 即空闲状态中) ，估计在这个期间到达的最小包数m ，以此 考虑平均队列长度的问题： 中山大学硕士学位论文 a v g _ ( 1 一w ) “a v g 公式( 2 2 ) 其中，m 等于队列空闲时间t i m e q t i m e 除以包传输时间j 。在计算平均队 长的公式中，权值w 相当于低通滤波嚣的时问常数，它决定了路由器对输入流量变 化的反应程度，因此对w 的选择非常重要。 如果w 过大，r e d 就不能有效地过滤短暂的拥塞；如果w 太小，a v g 就会对实 际队列长度的变化反应过慢，不能合理地反映拥塞状况，在这种情况下，路由器就 不能有效检测到早期的拥塞。w 的值应根据不同情况预先设置，一般由路由器中队 列大小和队列长度突变间隔来决定。队列长度的最小门限和最大门限r a i n 。和 m a x m 由期望的队列长度决定。 ( 2 ) 计算丢弃概率 当a v g 在m i n m 和m a x m 之间变化，包丢弃概率n 线性的从o 变化到最大丢弃 概率m a x 。： p 。= m a x q ，竺竺墼 公式( 2 3 ) m a x t h m i n t h 如图2 一l 所示。最终的丢弃概率办随着上次丢弃分组后收到的分组个数” ，的 增加而缓慢增长： 儿2 五彘丽 公式( 2 - 4 ) 这样保汪了路由器在丢弃包之前不会等待太久。c o u n t 越大，丢弃概率越大。当平 均队列长度a v g 超过m a x m 时，路由器丢弃每一个到达的包。 当a v g 小于r a i n 胁时，分组丢弃概率为o ，没有分组被丢弃：当a v g 在最小门 限值m j n m 和最大门限值m a x 抽之间时，分组以丢弃概率丢弃到达的分组；当a v g 大 于m a x 。时，分组丢弃概率为1 ，分组被无条件丢弃，即： 第1 章引言 t o ， 详细的r e d 算法如图2 2 。 a v g l t i l r l m r a i n i a v g m a x 抽 a v g m a x 晴 表2 1r e d 算法参数变量 名称含义 o v g 平均队列长度 q t i m e队列空闲开始时刻 c o u n t 上次丢弃事件后到达的包 w 队列权值 m l n m 队列长度最小门限 m a x , h 队列长度最大门限 m a x p 最大丢弃概率 s 包传输时间 g 当前队列长度 p 。当前丢弃概率 f f 埘已 当前时问 中山大学硕士学位论文 i n i t i a l i z a t i o n a v g = 0 c o u n t = 一1 f o re a c hp a c k e ta r r i v a l c a c u t a t et h en e w a v e r a g eq u e u es i z e ：a v g i ft h eq u e u e i sn o n e m p t y a v g 七- a v g + w ( g a v g ) e l s e m = ( t i m e q t i m e ) s a v g = ( 1 一w ) a v g i f m i n m a v g m a x 岫 c o u n t = c o u n t 4 - 1 c a c u l a t ep a c k e td r o p p i n gp r o b a b i l i t y ：只 p b = m a x q * ! 鲨二里! 竺坐 m a x t h m l r l t h 戌2 五而p b w i t hp r o b a b i l i t yp 。： d r o pt h ea r r i v i n gp a c k e t c o u n t = 0 e l s e i fa v g m a x 聃 d r o p t h ea r r i v i n gp a c k e t c o u n t = 0 e l s e e n q u e u ep a c k e t c o u n t = - 1 w h e nq u e u eb e c o m e se m p t y ： q t i m e + - - t i m e 图2 2 r e d 算法 第2 章主动队列管理算法 2 1 2r e d 性能分析 由于r e d 是基于先入先( f i r s ti nf i r s to u t ，f i f o ) 队列调度策略的，并且只 是丢弃正进入路由器的数据包，因此其实旋起来也较为简单。这种方法能被有效 地实施而无需在路由器中维持每个流( p e r - f l o w ) 的状态信息。其性能优于d r o p t a i l ， 是一种更为有效的拥塞控制机制。但是它存在几个主要问题【1 “。 ( 1 ) 其算法性能剥参数设置和网络的状况很敏感，改变参数对性能影响很大。 比如，r e d 算法的拥塞指示的发送速率时有参数m a x ，来体现的。如果m a x 。太 大，那么丢包比例主要就是由于早期拥塞检测中产生的丢包造成的；如果m a x 太 小，丢包主要就是由于队列溢出造成的。到目前为止，这些参数还没有明确的设 定方法。 ( 2 ) 随着网络中“流”( f l o w ，指一个t c p 连接) 数目的增加，网关的平均队列长度 会逐渐增加。r e d 的一个弱点是平均队长队流量负荷和参数设置很敏感，导致队 列长度波动较大。在特定的网络负载状况下依然会导致多个t c p 的同步，造成队 列震荡、吞吐量降低和时延抖动加剧。并且随着网络中t c p 连接数目的增加，网 关的平均队列长度会逐渐增加。 ( 3 ) r e d 算法没有分组优先级的概念，不能实现i n t e m e t 商业化的现实。算法 通过在高搠塞期到来之前对信息包进行随机丢弃，这种随机丢弃缺乏选择性。 2 2 常见的几种队列管理算法比较 2 2 1r e d 算法的改进 针对网络流增加而引起的队列氏度问题，一些研究提出了解决方案。其乇要思 路是根据网络中负载的情况对标记或者丢失概率进行动态调整。 中山大学硕士学位论文 1 a r e d 算法 基于r e d 算法，提出一种自动配置机制，其主要思想是根据网络负载的 情况调整最大丢弃概率，即通过检查平均队长的变化来决定r e d 是应更激进 还是更保守，从而尽量保持平均队长在m i n m 和m a x ， 之间。具体来说，当平 均队列小于最小门限值m i n 就减小n 大概nm a x ，；当平均队列大于最大 i 1 限nm a x 就增大最大概率m a ) ( 。 a r e d 是对r e d 改动很小的一种算法，它保留t r e d 的基本结构，只 需调节参数m a x 。从而保持平均队长在m i n m 和m a x ， 之间，消除了r e d 的队 2 s r e d 算法【1 6 】 - j t c p 连接，则h i t ( t ) = 1 ，否贝l j h i t ( t ) = 0 ，n n 以概n p 更新记录队列。 首先计算尸( f ) ： p ( ，) = ( 1 一口) p ( f 一1 ) + z h i t ( t ) 公式( 2 6 ) 见印= b 州c q ，m i n ，网1 公式c z 。， 其中，q 为当前队列长度， p 。( q ) = p 。 矿；b 9 b 石1p 。矿吉b g ( 1 3 b 公式( 2 8 ) o i f o g 吉曰 第2 章主动队列管理算法 其中，b 为路由器缓冲区的长度。当队列长度g 在当队列长度g 在_ t b 到b 之 问时，丢弃概率为p 。，达到最大丢弃概率，无条件丢弃该分组；当g 在i b 到曰之间时，丢弃概率为了ip ，即以 p 的概率丢弃该分组；当g 在0 到 j4 4 ；曰之间时，分组不丢弃，进入队列。 3 d r e d 算法旧 d r e d 算法采用简单的反馈控制方式，随机丢弃队列中的包。其包丢弃 概率计算公式为： 既( n ) p d ( ) + 口掣 嫡z _ 9 ) 其中，口为控制参数，b 为路由器缓冲区长度，a ( n ) 为滤波后的误差信号 5 ( 月) = ( 1 一) ；( ”一1 ) + p ( ”) 公式( 2 1 0 ) 其中，0 0 。点和嘎规定了每次调整的幅度，匹嘎，这是因为过于保守或者 过于激烈的拥塞管理方法都有可能造成低链路利用率，而分组丢弃只会在算法过 于保守时才会出现。这样b l u e 就能有效的控制发送拥塞通知信息的速度。 b l u e 算法中有两个重要的参数三和f r e e z e t i m e 。 b l u e 用参数取代缓冲区大小：当队列长度大于最高阈值三时，增大p 。， 以减小排队时间。参数f r e e z e f 咖p 用来调整丢弃速率的变化频率，它规定了两次 丢弃概率更新的时间间隔。在数据包到达时按当前丢弃概率丢弃包。 和r e d 相比，b l u e 算法简单，配置方便，可以有效减小分组丢弃速率和队 列延时，保证高链路利用率，保障语音和视频数据的服务质量。 2 2 3 p i 控制器 p i 2 叭、r e m 2 ”、a v q 2 2 1 等算法都是在a q m 中使用p i 控制器。具体来看 1 p i 控制器 p i ( p r o p o r t i o n a la n di n t e g r a l ，比例积分1 控制器通过增加积分因素来消除比 例控制器中存在的稳态误差。通过在反馈计算中引入积分项，p i 控制器可以 有效的消除p m p o r t i o n a l 控制器中出现的“稳态误差”，从而保证队列长度的稳 定。 p i 控制算法的包丢弃概率计算公式为 p ( 女) = p ( 七一1 ) + 日( g ( 七) 一q r p ，) 一b ( q ( k 一1 ) 一q 阿) 公式( 2 一t 4 ) 其中，口、b 为控制参数，g 村为参考队列长度，q ( e ) 为k 时刻的队列长度。 第2 章主动队列管理算法 在每个采样时刻利用公式( 2 1 6 ) 更新丢弃概率，在数据包到达时按当前丢弃概 率丢包。 当刚络中的流量发生很大变化时，a q m 算法中使用p l 控制器会减慢系 统的反应速度。另外，p i 控制器设置的一组参数只能适应比较有限范围的网 络环境。这使得在实际网络环境中使用p 1 控制器存在一定的困难。 2 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 ) 随机提前标记 r e m 是基于流测量的控制机制。通过分组标已的方法通知源端，并要求 源端相应的调整发送速率，目的是获得高的利用率和可以忽略的包丢失率和 网络延迟。 r e m 算法的包丢弃概率计算公式为 m ( t ) = 1 一一川 f f 式( 2 1 5 ) 其中， 1 为设定的常数，p ( t 1 为价格，其计算公式为 p ( ，+ 1 ) = p ( f ) + y ( 口( 6 ( ，) 一b ) + y ( ，) 一c ) f f 式( 2 1 6 ) 其中，、a 为控制参数，b + 为期望队列长度，b ( t 1 为t 时刻的队列长度， y ( ，) 为f 时刻链路的数据流速率，c 为瓶颈链路的容量。在每个采样时刻利用 上式更新丢弃概率，在数据包到达时按当前丢弃概率丢包。 3 a v q ( a d a p t i v ev i s u a lq u e u e ) 虚拟队列 a v q 是在“虚拟队列”( v i r t u a lq u e u e ，v q ) 基础上设计的主动队列管理算 法，其控制对象是链路的报文到达速度。虚拟队列算法维持一个小于实际缓 冲区容量的虚拟队列，通过调整这个虚拟队列的容量，决定是否接纳到达分 组。 令虚拟队列的容量e 为，那么虚拟队列容量满足差分方程： 0 = a ( r c 一 )公式( 2 1 7 ) 中山大学硕士学位论文 其中， 表示分组到达速率，y 表示理想的链路利用率，盘为平滑因子。 当实际链路利用率高于，时，需要更迅速的标记分组；反之缓慢的标记分组。 这样的做法类似于令牌桶算法：只有等待新的令牌产生，分组才被允许入队， 否则将会被标记或丢弃。虚拟队列的维护和实际缓冲区中队列的维护相互独 立。 和固定虚拟队列容量相比，自适应的调整虚拟队列( a d a p t i v ev i r t u a l q u e u e ，a v q ) 的容量显得更为灵活。a v q 算法结合了队列长度和输入输出速 率度量拥塞的令牌算法。它通过限制虚拟队列长度限制实际队列容忍突发流 量的上限，一旦超过虚拟队列的大小，分组就要遭到标记或丢弃。由于在v q 的计算中使用了积分的形式，这使得a v q 也有反应速度慢的问题。 2 2 4 主要a q m 算法比较 表2 1 对主要的a q m 算法进行了简单的总结，根据拥塞检测方法的不同，将 主动队列管理算法分为以下几种方法，并比较了各种算法的基本设计思想及主要 的性能目标。 表2 2 主动队列管理算法小结 类别算法主要性能目标 设计思想 拥塞避免，防止全局同步根据平均队长检测拥塞，随 r e d 等机标记分组 平均队列长度稳定在约定根据平均队长自适应配置参 a r e d 范围内数 基于队列长度 保持队列长度稳定，与连根据活动流数量调节分组丢 s r e d 接数无关弃概率 d r e d保持队列长度稳定，与连根据队长与期望值之差调整 接数无关，高链路利用率 丢弃概率 第2 章主动队列管理算法 续上表 基于队列长度b l u e低弃率 根据丢包率和链路利用率训 与链路利用率高链路利用率整分组丢弃概率 组合 高链路利用率虚拟队列，自适应流量速率 基于流量速率 a v q 低时延，低丢失率变化 基于队列长度r e m高利用率，低时延优化方法，价格函数 与流量速率组 p i 稳定的队列长度控制论方法，稳定性分析 a 2 3 支持多优先级的随机早期检测 r e d 可以和区分服务模型中的分类、管制和标记机制有效地结合起来。依据 a fp h b 的丢弃优先级设置r e d 参数，即w r e d 、r j o 。 2 3 1w r e d 加权随机早期检测 w r e d 是c i s c o 公司提出的一种支持区分服务的a q m 机制。与r j o 一样， w r e d 基本思路也是在m 包头按照某种策略进行标记，丢包优先级基于该标记。 w r e d 能支持8 个独立的丢包优先级，每个级别配置一套独立的r e d 参数，以红 ( r ) 黄( y ) 绿( g ) - - 色为例，如图2 3 所示。 中山大学硕士学位论文 d r o pp r o b a b i l i t y ( a ) 交错方式 d r o pp r o b a b i l i t y m l n r h ， m l r l ，hy m l n f h g ( b ) 重叠方式 图2 3 w r e d 算法 根据三色的最小门限与最大门限的设置不同，可分为两种方式：交错方式中 m i n 曲r m a x