（无线电物理专业论文）高速路由器的主动队列管理算法研究.pdf

中山大学硕十论文 高速路由器的主动队列管理算法研究 专业：无线电物理 硕士生：陈云生 指导教师：秦家银教授 摘要 i n t e r n e t 的体系结构是以i p 协议提供的无连接端到端报文传输服务为基础， 提供“尽力而为 服务模型的设计机制。这种机制的最大优点是设计简单、实现 容易、可扩展性强。i n t e r n e t 自出现以来得到了快速发展，然而t c p i p 的这种优 势是有代价的，随着i n t e r n e t 用户数量的不断膨胀，网络的拥塞问题也越来越趋 严重。因此，设计一种简单而有效的拥塞控制算法成为网络管理中急待解决的问 题。作为高速路由器的一个重要模块，主动队列管理( a c t i v eq u e u em a n a g e m e n t ， a q m ) 算法近年来受到越来越多的重视，在高速路由器中实施a q m 策略是为了提供 小的分组丢失、高的吞吐量和链路利用率以及低的队列延时，它与t c p 端到端的 拥塞控制相结合，是解决目前i n t e r n e t 拥塞控制问题的一个主要途径。 主动队列管理算法在实现上又包括基于平均队列长度和基于速率变化来进 行拥塞判断两个方面。本文针对现有算法在实现性能上存在的缺点和不足，在实 现经典算法r e d 算法( 随机早期检测算法，是一种基于平均队列长度的拥塞判定 方法) 的基础上，采用一种新的基于速率变化判断拥塞的算法r a q m 算法，然后结 合r e d 算法吞吐量高但延迟大且不稳定，而r a q m 算法延迟小、稳定但吞吐量较小 的特点，对这两种算法进行有机的结合、取长补短，实现基于平均队列长度和基 于速率变化的双重拥塞判定法r q 算法和r q c 算法。通过仿真分析，对比r e d 算法、 r a q m 算法和r q 、r q c 算法，可以发现r q 和r q c 算法降低了r e d 和r a q m 算法单独拥塞 判断模式上的不足，同时也极大的提高了性能。 关键字：主动队列管理、拥塞控制、双重拥塞判定、速率变化 中山大学硕十论文 a c t i v eq u e u em a n a g e m e n tr e s e a r c h e s i i lh i 曲- s p e e dr o u t e r m a j o r ：r a d i op h y s i c s n a m e ：c h e ny u n s h e n g s u p e r v i s o r ：p r o q i n ，j i a - y m a b s t r a c t t h ei n t e m e tp r o t 0 0 0 la r c h i t e c t u r ei sb a s e do nac 0 彻e c t i o n l e s se n d t o - e n dp a c k e t s e r v i c eu s i i l gt h ei pp r o t o c o l s ，a n dp r o v i d e so n l yb e s ts e r v i c e s 1 n h em o s ta d v a n t a g eo f t h i sm e c h a n i s mi ss i i n p l ed e s i g n i i l ga n ds t r o n ge x p a n s i b i l i t y ，s 0i i l t e m e th a sg a i l l e d n o u r i s hd e v e l o p m e n ts i n c ei ta p p e a r e d b u tt h i ss u p e 哟 all p a c k e t l o s t 、h 远h t h r o u g h p u t 、l o wq u e u el e n g t h a n d low d e l a y w h i c hc o m b i i l i i l gw i t ht c p e n d t o e n dc o n g e s t i o nc o n t r o l i st h e maill w a yt os o l v ct h ep r o b l e mo f i l l t e m e t0 0 n g e s t i o nc o n t f o la t p r e s e m a c t i v eq u euem a m g e m e n ti i l c l u d e sa v e r a g e q u e u e - b a s e d a q ma n d r a t e - b a s e da q m i no rd e rt 0 illlpr0ve t h e 拉a d v a n t a g e 柚ds h o n a g e o fthe a l g o r i t h m sa tp r e s e n t ，t h ed j s s e natione m u l a t e st h er e da 培o r i t h m ( r a n d o me a r l yd e t e c t i o n ，a v e r a g eq u e u e baseda q m ) a tfirstthen itsearchesanewalgorithmwhichisssssa88&33$ 中山大学硕士论文 一一_ - 一 q u e u ct h r o u g h p u t a n d1 0 w q u e u ed e 埘a n d 姗妇n c wa 1 9 0 r i t h 傩c a u c d r a t e q u c u e b 蹴da q m ( r q ) a n dr a t e q u c u c - b a s c d c o n t r o u c da q m ( r q c ) c o m p a r i n gt h ce 删l a t i o nr e s u n so f t h cf o u ra 培o r i t h 璐，r qa n dr q ca l g o r i t l l n ll l a v e h 蟾h e rq u e u et h r o u g h p u ta n dl o w e rq u e u ed e l a y a n dg e tb c t t e rp c r f o 加a n c e k e yw o m s ：c o n g e s t i o nc o n t r o l 、 d o u b l ej u d g e m e n t 、a c t i v eq u e u e 撇腑g e m c m 、 r a t e b a s e d 中山大学硕士论文 异构系统，仅仅依靠tcp拥塞控制机制不能有效的阻止拥塞的发生，中间的路由节点必须参与资源的控制和分配。 基于路由节点的拥塞控制技术包括：队列调度( q u e u es c h e d u l i n g ) 策略和队列管理( q u e u e m a n a g e m e n t ) 策略。d r o p t a 订是最早的队列管理算法，但是是一 种被动的响应性的管理策略。当队列充满也就是达到可容纳数据包的最大值时，d r o p t a i l不分区别的丢弃此刻以后到来的任意数据包，也就是“结尾丢弃。 droptail存在三个显著的缺点：死锁问题，满队列问题，tcp全局同步问题。 针对如何解决“死锁问题、“满队列问题”和“t c p 全局同步问题”，b r a d e n 等人于1 9 9 8 年在i e t f ( i n t e r n e te n g i n e e r i n gt a s kf o r c e ，i n t e r n e t 工程任务 壁i 给网蚕羹矍甭葛罐筒塥镐崭糯蓁t 晷藩孥羹藕冀蕃掣蕾商弹赫释堇驯型季 盒罂烈毗霎垣薹失率和囊餮酗曾燮瑟氅烈i 巨曩癸蓉覆毂签器筇翅幕雾函延蓄奈 霪雾仔，i 喾奏篓；拦缀； 引墓羹珲建蠢坚雾露酲鞋l 善毒国黼雏拍粪漂；黪藩答摩落萋| | 毒；耋i 冀童嚏爹秀童刿西酃| f f o 主塞蓁蓬蓁蓁簿二墅瞎墼例醪巾i 眦鲤露嘤趔咧哂雾吲雠鞴蓁，磬窜；氢匿昼瘴二萎皇 霎垦朝 萋 重降低网络的性能。 现有的t c p 拥塞控制机制必须在源端检测到包丢弃时才可能降低其发送数据 包的速率，从路由器丢包到源端检测到拥塞并降低发送数据的速率之间花去了大 量的时间，而在这段时间内，源端仍以链路不能承受的速率持续发送数据，从而 导致更大的包丢失率，致使网络更加拥塞。所以对于i n t er n e t 这样复杂的异构系 统，仅仅依靠t c p 端到端拥塞控制机制是不能确保q o s (q u a l i t yo fs e r v i c e ) 的， 网络中间节点必须参与对资源的控制和分配。路由器中采用队列调度和队列管理 策略来对链路缓存进行管理和分配，当路由器处理能力不足时，队列管理算法对 来不及处理的数据包进行丢弃或标记，调度算法直接管理输出链路的带宽资源。 1 9 9 8 年，b r a d e n 等人在i e t f 提出了主动队列管理( a c t i v eq u e u em a n a g e m e n t ， a q m ) 哺1 算法，作为高速路由节点进行拥塞控制的一种技术手段，期望a q m 在减 小排队时延的同时保证较高的吞吐量。a q m 主要通过对拥塞进行早期的检测并向 端系统发出拥塞指示，端系统通过相应的机制在路由器缓冲区队列溢出和丢包产 生之前降低数据的发送速度，从而达到降低丢包率和提高链路 摹 2 中山大学硕士论文 了p d c o n t r o l l e r 控制器驯、p i d 控制器2 们、p d _ r e d 算法等。 国内在a q m 雾霾鹱爹；鞠幺弼奏黝蹩匿邑列囊镩蓁薹鲐雾酬誊一螳瑗臻型型； 殴耸翼藿拥搴垂批为絮瑗岔；蓁冀邶割匕奄丢弃数量增痂霎宦篙借型篡i ； 鹾毕点 猛噩弦孵臻霪囊霸萤奏；羹鲥艇割影鳓r 戮甫囊耋聋弦唧溷嫩骧溶! 落型篓酗翻刻 卜姗羁蜘刳刚割纠j 眇墅鞫弹萋善耄蒹丽； 蓁 现出缓慢增长，而响应时间急剧增加，这一点称为膝 点( k n e e ) 。如果负载继续增加，路由器开始丢包，当负载超过一定量时吞吐量开 始急剧下降，这一点称为崖点( c l i f f ) 。通常将膝点附近称为拥塞避免区间，膝 点和崖点之间是拥塞恢复区间，崖点之外是拥塞崩溃区间。 拥塞控制机制实际上包含拥塞避免和拥塞恢复两种策略。前者的目的是使网 络运行在k n e e 附近，避免拥塞的发生；而后者则是使得网络运行在c l i f 的左侧区 域。前者是一种“预防措施，维持网络的高吞吐量、低延迟状态，避免进入拥 塞：后者是一种“恢复”措施，使网络从拥塞中恢复过来，进入正常的运行状态。 腿 图2 1 拥塞关系示意图 根据算法实施位置的不同，又可以将拥塞控制算法分为两大类：端到端拥塞 控制算法和基于中间扑惴；谥屑浣诘愕挠等刂扑惴窃谕 7 x 中山大学硕士论文 析，结果比较，得出结论等； 第五章主要是对本文进行一个大致的总结，以及简要介绍今后的一些研究目 标和方向。 6 中山大学硕士论文 络设备( 如路由器和交换机) 上执行，其作用是检测网络拥塞的发生，并产生拥塞 反馈信息；端到端的拥塞控制算法则是在主机和网络边缘设备上执行，其作用是 根据反馈信息调整发送数据包的速率。两种算法共同作用j 完成拥塞控制的功能。 2 1 基于t c p 的端到端拥塞控制机制 据统计，互联网上9 5 的数据流量使用的是t c p 协议，非弹性的u d p 业务只占 据很小的份额，所以对t c p 的流量控制是互联网正常运作的基础。目前端到端的 拥塞控制研究主要集中在对t c p 传输机制的改进上。 2 1 1 传统t c p 端到端拥塞控制机制 传统t c p 拥塞控制4 3 经历了一个从初步设计到不断完善的过程，产生了一系 列的控制机制，包括“窗口机制”慢启动 “拥塞避免，2 3 等。 2 1 1 1 滑动窗口机制 在互联网设计的初期，对于分组的流量控制是通过滑动窗口机制来完成的。 滑动窗口机制简要叙述如下： ( 1 ) 发送端维持一个发送窗口s w n d ，接收端维持一个通告窗口a w n d ，发送端每次 发送的数据量不能超过m i n ( s w n d ，a w n d ) 。 ( 2 ) 发送端每次发送报文( 假设报文大小为s e n t ) 时：s w n d 随之减小为 s w n d = s w n d s e n t 。 ( 3 ) 接收端每次接收到报文时，将会对接收到的报文进行确认，假设确认了a w n d 个字节。 ( 4 ) 发送端接收到确认时，s w n d 增加被确认的报文大小，s w n d = s w n d + a w n d 。 这种设计有着自同步的功能，对网络的流量控制起到了很大的作用，但是发 送窗口s w n d 的初始化是个难题，因为刚开始无法预知网络状况和接收端窗口大 小，盲目地发送任意大小的数据容易加重网络的拥塞状况。鉴于这种情况， 8 中山大学硕士论文 j a c o b s o n 提出了“慢启动 和“拥塞避免 两种机制。 2 1 1 2 “慢启动 和“拥塞避免机制 由于在初始化时发送大量的分组相当危险，非常容易导致拥塞的发生，这时 可以采取更为保守的做法，初始化发送窗口为一很小值，逐步增加发送窗口的大 小，直到同步机制起作用为止。这就是所谓的“慢启动”机制。 如图2 2 ( a ) m 所示：“慢启动”为发送端的t c p 增加了一个窗口，称为拥塞窗 口( c o n g e s t i o n w i n d o w ) ，记为c w n d 。当与另一个网络的主机建立t c p 连接时，c w n d 被初始化为一个报文段大小。每收到一个a c k ，拥塞窗口就增加一个报文段，发 送端取而m i n c w n d ，a w n d ) 作为发送上限。拥塞窗口是发送方的流量控制，而通 告窗口是接收方使用的流量控制。发送方开始时发送一个报文段，然后等待a c k ， 当收到该a c k 时，拥塞窗口从1 增加为2 ，即可以发送2 个报文段，当收到这两个报 文段的应答时，拥塞窗口就增加为4 ，这是一种指数增加的关系。当网络上的某 些节点上的分组速率达到了链路容量时，中间路由器开始丢弃分组。由于分组被 丢弃而导致长时间没有接收到a c k 包，源端超时，然后将拥塞窗口设为一个报文 段大小，重新开始“慢启动”的过程。 争耀矸 f 稻珂 期誊它日喇 ：1 $ 熹t 瓢他硝r 啊诚忽 图2 2 拥塞控制示意图 h “拥塞避免”算法维持两个变量：一个拥塞窗口c w n d 和一个“慢启动门限 s s t h r e s h ( 初始值为6 5 5 3 5 字节，当拥塞发生时，s s t h r e s h 被设置为当前c w n d 大小 的一半，启动“慢启动过程) 。拥塞避免算法要求每收到一个a c k 时将c w n d 增加 l c w n d ，即每发送c w n d 个报文时最多只增加一个报文段，与“慢启动”的指数增 9 叶l 山大学硕七论文 加相比，这是一个加性增长的过程。当c w n d 小于或等于s s t h r e s h 时，执行“慢启 动过程，否则进入“拥塞避免”阶段。 为了防止对r t 0 ( 重传超时) 估计过小可能导致的正反馈，通常将重传定时器 设计的比r t t 大很多。这样就有了一个不利因素：如果一个报文丢失，t c p 便不能 及时的重传；如果接收端采用按序接收，那么后续到来的包将会被丢弃。 2 1 2 改进t c p 拥塞控制算法 在b s du n i x 中t c p 拥塞控制在不断改进，b s d 网络1 0 版本( b n r l ) 也称为t c p t a h o e 例，它是拥塞控制机制的最早实现，包括慢启动、拥塞避免和快速重传机 制。t c pt a h o e 加速了丢失报文的重传：如果t c p 目的端收到一个失序的报文段， 便立即发出一个对最后一个有序报文的a c k 包，而不是等到重传超时，对接着到 来的报文也重复上述过程，直到丢失的报文段到达。源端在接收到3 个重复的a c k 报文后( 总共4 个重复的a c k 包) ，立刻启动重传，这就是“快速重传”机制。 b s d 网络2 0 版本( b n r 2 ) 也称为t c pr e n o 比副中引入了快速恢复机制。t c pr e n o 算法仍然有不足，当一个窗口只有一个数据分组丢失时，t c pr e n o 比t c pt a h o e 有更好的性能，但当一个窗口有多个数据分组丢失时，t c pr e n o 的性能就变得很 糟糕。t c pr e n o 在每个r t t 内最多重传一个数据分组。针对这个不足，近年来又 提出了一些改进的算法： 2 1 2 1n e wr e n ot c p 算法 n e wr e n ot c p l 叫的变化涉及到在快速恢复阶段对数据发送者行为的更改。 在r e n ot c p 中，通过减小可用窗口到拥塞窗口的大小，部分确认信息使t c p 退出 快速恢复。在n e wr e n ot c p 中，部分确认信息没有使t c p 退出快速恢复，相反， 在快速恢复阶段收到的部分确认信息被当作用来指示在此部分确认信息编号之 后的数据分组已经丢失并且需要重新传送的指示信息。这样，在一个窗口中丢失 多个数据分组时，n e w r e n o t c p 就不需要重传定时器，而是每个r t t 重传一个丢失 的数据分组，直到从拥塞中恢复过来才退出快速重传算法。显然，n e wr e n ot c p 1 0 中山大学硕士论文 只需修改源端代码，综合来看，即使源端不通过等待超时来恢复一个窗口数据中 丢失的包，r e n ot c p 和n e wr e n ot c p 在一个r t t 内也至多只能重传一个丢弃的包， 当然，t a h o e 并不局限于此，然而这也说明缺乏s a c k 算法时源端只能选择两种丢 失数据的恢复策略： 第一种是每一个r t t 时间内至多重传一个丢弃的包： 第二种是重传所有包，其中也包括可能已经正确发送的包。r e n ot c p 和n e wr e n o t c p 使用第一种策略，而t a h o e 使用第二种策略。 2 1 2 2s a c k 算法 s a c k 心副使用了两个t c p 选项：第一个是“使能 选项，也就是说允许使用s a c k ， 这个选项在s y n 数据包中发送，用来显示一旦连接建立，s a c k 选项就可以使用； 另一个s a c k 选项是选项本身，一旦s a c k 选项被允许使用( 即s a c k 被“使能 ) ，它 就可以在已经建立的连接上发挥作用。s a c k 选项字段包括许多s a c k 块，每一个 s a c k 块记载了已经被接收端接收并在缓存中排队的非连续数据块。s a c k 选项中的 第一块必须是数据接收者最近接收的数据分组，其它的s a c k 块重复最近已经向数 据发送者报告过的s a c k 块。一个s a c k 选项指定n 个s a c k 块就需要8 半n + 2 个字节，4 0 个字节的t c p 选项可以最多指定4 个s a c k 块。 x 中山大学硕士论文 不同队列具有不同的分组长度，则分组长度大的队列会比分组长度小的队列占用 更多的输出带宽，使队列之间产生不公平现象。而且，这种策略不能提供延迟保 障，为弥补其在变长度分组环境下的不公平性、改善时延特性，提出了加权轮循、 差额轮循等算法。 ( 3 ) 公平队列f q “是一种侧重公平性的轮循调度算法。主要是为了解决变长 度分组存在的不公平性，同时考虑到按比特单位轮循的复杂性。f q 采用了一种近 似的方法：首先计算一个数据包按轮循方式发送时完成的时间，再按这个完成的 时间对数据包进行排序。f q 的带宽分配独立于数据包大小，各业务的队列几乎是 同时开始的；f q 的缺点是实现复杂，因为它需要对每个数据流进行排队处理、状 态统计、数据包分类和数据包调度等。 ( 4 ) 加权公平队列( w f q ) 瞄是f q 的改进。w f q 是一种基本的q o s 保障机制， 当分组较小时，网络中端到端延迟存在确定的上限。为解决w f q 、f q 计算复杂的 问题，提出了w w f q 、自同步公平队列等算法。 网络中间节点上的调度功能对于保障拥塞控制机制的公平性具有重要的作 用，虽然网络拥塞控制的研究一直以来将注意力主要放在端到端的性能上，即在 实现尽可能小的延迟的基础上实现较高的吞吐量。但随着应用需求的增加，为保 证网络的公平性，基于队列调度的策略将是加强网络捐j 塞控制的一个重要途径。 2 2 2 队列管理策略 队列管理通常是指用特定的分组丢弃策略来维护队列长度的大小，实现对网 络的控制。同时，丢包的信息可以反馈到端主机的上层进行拥塞控制。队列管理 策略主要是针对于中间节点的拥塞控制策略。根据路由器对队列长度的参与性， 可以将队列管理策略分为“丢尾”算法和a q m 主动队列管理。“丢尾 算法对队 列不主动采取动作，是早期提出并采取的队列策略；由于网络的发展要求网络本 身参与到拥塞控制中，由此提出了主动队列管理策略，目前a q m 已经成为网络拥 塞控制研究中的主要方向。 1 4 中山大学硕十论文 第3 章队列管理及算法 广义的队列管理是指以队列为依托，对到达的数据分组、数据流进行传输控 制的多种机制，主要涵盖缓冲管理和分组调度两个方面的内容。 狭义的队列管理仅指对网络传输节点中队列缓冲资源的管理和分配一即缓 冲管理。 本文所指队列管理只针对缓冲管理进行讨论。在分组传输过程中，其流经的 网络传输节点通常采用队列缓存、延迟转发的服务方式以提高输出链路的带宽利 用率。队列管理机制在分组到达队列前端时依据一定的策略和信息决定是否允许 该分组进入缓冲对列，从另一个角度看，也就是做出是否丢弃该分组的决策，因 此，也称为丢弃控制。队列管理通过选择何时丢弃何种业务流分组来控制队列长 度，队列管理和拥塞控制存在着密切的联系。队列管理在网络传输控制中发挥着 相当大的作用，是网络服务质量控制的核心技术之一，是实现网络拥塞控制的重 要手段，也是拥塞控制研究的重点课题比。 3 1 队列管理机制的分类 目前关于路由器的队列管理机制可分为两类：被动式队列管理( p a s s i v e q u e u em a n a g e m e n t ，p q m ) 和主动式队列管理( a e t i v e q u e u em a n a g e m e n t ，a q m ) 。 3 1 1 被动式队列管理 管理路由器队列长度的传统技术是对每个队列都设置一个最大值( 以包为单 位) ，然后接受包进入队列直到队长达到最大值，接下来到达的包就要被拒绝进 入队列直到队长下降。这种技术也就是所谓的“队尾丢弃 算法。从拥塞控制的 1 6 中山大学硕十论文 角度分析，它是一种拥塞恢复机制，其存在几个重要缺陷乜们啪1 ： ( 1 ) 死锁( l o c k o u t ) ：在某些情况下，由于同步( s y n c h r o n i z a t i o n ) 或其它定时作 用的结果，“队尾丢弃 算法会让某个流或者少数几个流独占队列空间，阻止其 它流的包进入队列。 ( 2 ) 满队列( f u l l q u e u e s ) ：由于“队尾丢弃算法只有在队列满时才会发出拥塞 信号，因此会使得队列在相当长时间内处于充满( 或几乎充满) 的状态。而队列管 理最重要的目标之一就是降低稳定状态下队列的长度，因为端到端的延迟主要就 是由于在队列中排队等待造成的。 ( 3 ) t c p 全局同步( t c pg l o b a ls y n c h r o n i z a t i o n ) ：由于互联网上数据的突发本 质，到达路由器的包也往往是突发的。如果队列是满的或者几乎是满的，就会导 致在短时间内连续大量地丢包。而t c p 流具有自适应特性，源端发现包丢失就会 急剧地减小拥塞窗口，包到达速率就迅速下降，于是网络拥塞得以解除，但源端 得知网络不再拥塞后又开始增加发送速度，最终又造成网络拥塞。而且这种现象 常常会周而复始地进行下去，从而在一段时间内网络处于链路利用率很低的状 态，降低了整体吞吐量，这就是所谓的“t c p 全局同步”现象。 除了“队尾丢弃机制，另外两种在队列满时进行队列管理的机制是“随机 丢弃 ( r a n d o i l l d r o p ) 和“前部丢弃( d r o p f r o n t ) 机制。当队列满时，前者从队 列中随机找出一个包丢弃以让新来的包进入队列；后者从队列头部丢包，以便让 新包进入队列。这两种方法虽然都解决了“死锁问题，但仍然没有解决“满队 列 问题。由于这几种方法都是在队列满了之后被迫丢包，因此称为被动式队列 管理比。 3 1 2 主动式队列管理 “首丢弃 和“随机丢弃对避免死锁和全局同步是有效的，但没有解决持 续的满队列问题。如果路由器在拥塞发生前采取一些预防措施，那么满队列问题 是可以得到解决的。主动的而非响应性的分组丢弃就是一种有效的手段，相应的 队列管理策略被称为“主动队列管理”( a q m ，它是近年来端到端拥塞控制研究中 的一个热点) 。a q m 与e c n 结合，通告拥塞的信号不再是唯一的分组丢弃，而可以 1 7 中山大学硕士论文 采用标记分组来通知信源减速，这样会进一步提高连接的有效吞吐量。a q m 的主 要技术目标是在减小排队时延的同时保证较高的吞吐量，具体分析a q m 解决的问 题主要包括以下4 方面2 副： ( 1 ) 早期探测路由器可能发生的拥塞，并通过随机丢弃或标记分组来通知源端采 取措施避免可能发生的拥塞。 ( 2 ) 公平地处理包括突发性、持久性和间隙性的各种t c p 业务流。 ( 3 ) 避免多个t c p 连接由于队列溢出而造成同步进入“慢启动”状态。 ( 4 ) 较小的队列长度，在高吞吐量和低时延之间做出合理平衡。 1 9 9 3 年，f 1 0 y d 和j a c o b s o n 提出了r e d 瑚。，因为在提出a q m 研究时，r 凹是唯一 能实现这一技术目标的算法，所以r f c 2 3 0 9 将其推荐为a q m 的唯一候选算法。 模拟结果显示r e d 在性能方面优于d r o p t a i l 。但是r 即存在两个很严重的缺 陷。一个问题是r e d 对于参数的设置很敏感。另外一个问题是随着网络中流数目 的增加，网关的平均队列长度会逐渐增加。 针对第二个问题，很多研究者提出了解决方案。其中大部分是在r e d 的基础 上对算法进行改进，主要思路是根据网络中负载的情况对标记丢失概率进行动 态调整。主要的算法包括a r e d 、s r 叻、f r e d ，这几种算法我们将在后面详细介绍。 在“主动队列管理 算法上又提出了r e m ( r a n d o me a r l ym a r k i n g ) 、p i 和a v q ( a d a p t i v e m r t u a l q u e u e ) 等，在a q m 中使用p i 、p i d 等控制器的思想得到越来越深 入的研究。 3 2 主动队列管理算法 队列管理算法方面主要集中在主动队列管理算法上，主动队列管理算法又主 要包括基于平均队列长度作为拥塞判定、基于队列负载( 即队列数据包传送速率 的变化) 做为拥塞判定、以及将控制理论引入a q m 中等算法，下面将会详细介绍 各个方面的典型代表算法： 1 8 中山大学硕士论文 3 2 1 基于平均队列长度的主动队列管理算法 基于平均队列长度的主动队列管理算法主要是通过计算队列的平均队列长 度，并将其作为判定拥塞是否发生的标志，并以此来计算相关的数据包的丢弃概 率，它包括下面的几种主要的算法： 3 2 1 1r e d 算法( 随机早期检测算法) r e d 旧1 的基本思想是通过概率丢失或标记来通知端系统网络拥塞的情况。在 r e d 中使用平均队列长度来度量网络拥塞的程度，然后使用线性的方式将拥塞控 制程度反馈给端系统。 算法原理乜引：r e d 队列管理增添了两种新机制：其一，不是等队列全满后再 丢弃到来的分组，而是在拥塞发生之前，利用概率判定机制事先丢掉部分分组来 预防可能发生的拥塞：其二，通过计算平均队列长度而非即时队列来调整分组丢 弃概率，由此来尽可能地避免因部分短暂的突发流量而导致的判定失误。 平均队列长度是用指数加权滑动平均( e 眦) 来计算的： q a v = ( 1 w q ) x q a v + w q x q( 3 1 ) 当分组到达队列时，如果平均队列长度q a v 小于最小门限值q 【i l i n ，分组全部 进入队列：当q a v 大于q i l l a x ，丢弃所有到达报文；如果平均队列长度q a v 位于q i l i n ( 最小门限值) 和q i l l a x ( 最大门限值) 之间，按如下计算分组丢弃概率p b ： p b = p m a x ( q a v q i l l in ) ( q i i l a x q l i l in )( 3 2 ) p a = p b ( 1 c o u n t x p b )( 3 3 ) 其中，p i i l a x 是最大丢弃概率，q a v 是加权平均队列长度，c o u n t 是连续成功传 输的分组数。在算法的实际实现中，为了使被标记的分组散布得更均匀，对标记 概率p b 作如下修正以得到p a 作为实际标记概率。式( 3 3 ) 即是为了保证被丢弃分 组间隔的均匀分布。因为p b 是一个很小的正数，l c o u n t x p b 很接近于1 ，所以p b 是丢失率的主要决定因素，对p a 的修正用于避免连续丢包，故以后仅考虑p a 。由 于p a 是随着当前队列长度的变化而变动的，该机制的最大适应范围为丢包率在 0 ，p m a x 流量，当然，实际范围要小得多。综上所述，总结出丢弃概率p b 的表 1 9 中山大学硕+ 论文 达式： 晗 q ；a “q m 证 q 岫i t a r g e ta n dm a x p 1 ； 一 i f ， 报文端到端的标记概率为：1 一妒- 。 r e m 链路1 的价格仍o ) 按式( 3 4 ) 来计算，不考虑饱和特性，设采样间隔为q ， 可得： p ，( ( 七+ 1 ) 6 ) = 鼽( 七6 ) + ，( 仍( ( 七+ 1 ) 6 ) 一( 1 一口，) 仍( 幻) 一口，q + ) ( 3 5 ) 上式可转化为： a ( ( 七+ 1 ) 6 ) 一所( 后6 ) = ，( 研( ( 七+ 1 ) 6 ) 一口) 一( 吼( 尼6 ) 一g ) ) + 朋，( 劬( 七6 ) 一留。) ( 3 6 ) 令留o ) 一仍o ) 一留，可得 p 研( ( 七+ 1 ) 6 ) 一a ( 七6 ) = ，( 吼( ( 七+ 1 ) 6 ) 一日( 七6 ”+ ，口，口( 七6 ) ( 3 7 ) 上式两边除以采样间隔6 ，可得 半= ，芈+ 等删) ( 3 - 8 ) 666 、 7 式( 3 8 ) 的解满足如下形式： 掣；彳掣+ 却o ) ( 3 9 ) md l 一。 对式( 3 9 ) 做拉普拉斯变换可得： 鼢o ) = 舢q o ) + b q o ) ( 3 一l o ) 因此价格传递函数为： 尝；么+ 旦 ( 3 _ 1 1 ) q ( s ) s 7 计算报文的标记概率时取驴。1 0 0 1 ，因此有p = 1 一p 一蚋( 其中口= l n 驴) ，做泰勒 展开： p = 口奉易o ) 一0 5 ( 以术p ，o ) ) 2 + ( 口木易o ) ) 3 6 + ( 3 一1 2 ) a = 1 n 1 0 0 1 1 ，考虑p ，o ) 的物理意义和实际应用中的取值范围，有a 木p ，o ) 1 ， 中山大学硕士论文 3 3 算法性能的评价标准 算法的实现过程主要集中在算法设计和实现方面，在实现有效的拥塞控制的 同时，应尽可能优化算法，降低算法的计算复杂性，减少对存储器的占用。对于 算法的应用性能，需要从以下几个方面考虑瞄： ( 1 ) 网络的服务数量：网络的服务数量可以用吞吐量表示。 ( 2 )网络的服务质量：有带宽、丢包率、迟延、迟延抖动等几个指标。其中带 宽的分配主要由算法的调度策略决定，包的迟延主要是由队列长度和调度策略决 定，丢弃概率主要由当前拥塞状况和主动队列管理算法决定。其中丢包率和迟延 是衡量服务质量的两个重要参数，之所以选择这两个参数，是因为大部分网络应 用都对这两个参数提出了较高的要求。 ( 3 ) 公平性：一般来讲，每个流都应该得到平等的对待，即每个流都应该得到 一样的带宽。但是随着网络环境的变化和一些特殊应用的兴起，如网络视频、网 络电话，需要区别对待不同的数据流，对不同优先级的数据流提供不同的带宽和 优先级，这样提出了比例公平性的概念。 ( 4 ) 资源分配的效率：拥塞控制算法的目的就在于有效的管理网络资源，使有 限的资源能够得到合理运用以达到资源最大化，因此资源分配的效率就是评价拥 塞控制算法有效性的一个重要的指标嵋引。 资源分配的效率可以用p o w e r 函数来评价。p o w e r 函数定义为： 在上式中，一般取a = 1 。如果评价偏重吞吐量，则取护l ：如果评价偏重反应时问， 则取a 1 。p o w e r 函数更加侧重于单一资源分配的合理性问题，本文正是基于p o w e r 函数的评价标准来实现对网络性能的优劣判断，由此来比较算法的优劣。 中山大学硕士论文 3 4o p n e t 仿真工具介绍 o p n e t 3 们3 5 儿蚓是一款用于网络仿真的软件，它主要面向网络设计专业人士， 能够满足大型复杂网络的仿真需要，为技术人员提供一个网络技术和产品开发平 台，可以帮助他们设计和安装网络、网络设备和通信协议。0 p n e tm o d e l e r 具有 三层建模机制、离散事件驱动、完备的模型库、基于数据包的通信等特点，大大 方便了网络仿真的方便性和灵活性。 3 4 1o p n e t 简介 ( 1 ) 离散仿真机制 o p n e t 采用基于离散事件驱动的仿真机制。事件是网络模型状态的变化或者 某种决策。只有模型状态发生变化，模拟机才进行仿真，状态不发生变化的时间 段，不进行仿真。仿真的时间是离散的，每当有一个事件出现后时间往前推进， 也就是时间是跳跃前进的。一个仿真时间点上可以同时出现多个事件，事件的发 生可以有疏密的区别。仿真中的各个模块之间通过事件中断方式传递事件信息。 每当出现一个事件中断时都会触发一个描述通信网络系统行为或者系统处 理的进程模型的运行。通过离散事件驱动的仿真机制实现了在进程级描述通信的 并发性和顺序性，再加上事件发生时刻的任意性，决定了可以仿真计算机和通信 网络中的任何情况下的网络状态和行为。 ( 2 ) 仿真调度机制 在0 p n e t 中使用基于事件列表的调度机制，合理安排调度事件，以便执行合 理的进程来仿真网络系统的行为。调度的完成通过仿真软件的仿真核和仿真工 具模块以及模型模块来实现。 首先，每个o p n e t 仿真都维持一个单独的全局时间表，其中的每个项目和执 行都受到全局仿真时钟的控制，仿真中以时间顺序调度事件列表中的事件，需要 先执行的事件位于表的头部。当一个事件执行后将从事件列表中删除该事件。 其次，仿真核作为仿真的核心管理机构，采用高效的办法管理维护事件列表。 中山大学硕十论文 ( 6 ) 发布结果。 其仿真流程过程如下： 3 5 本章小节 图3 3 系统仿真的基本过程 本章主要对队列管理机制和队列管理算法进行总体的介绍，重点介绍了一些 经典或者通用的算法。队列管理算法方面包括被动队列管理算法和主动队列管理 算法，其中被动队列管理算法主要是常说的“尾丢弃、随机丢弃、首丢弃 等队 列管理机制，但是被动队列管理其实是一种拥塞恢复机制，存在很大的缺陷：包 括死锁、满队列和t c p 全局同步问题，严重的影响到网络的性能；主动队列管理 主要是一种拥塞避免机制，其算法主要有三个发展的方向：基于平均队列长度为 拥塞发生标志的r e d 算法和它的衍生算法，包括s r e d 、f r e d 、a r e d 、b l u e 等等； 基于队列负载变化或者队列速率变化为拥塞发生标志的r a q m 算法，包括r e m 等； 3 3 中山大学硕士论文 第4 章算法研究和仿真实现 4 1r e d 算法的仿真实现 为了对r e d 算法性能进行研究分析，我们使用o p n e t 网络仿真软件对r e d 算法 进行了一系列仿真实验，主要是针对p o w e r 函数性能评价标准中的两个方面吞吐 量和队列延迟进行仿真结果分析。实验中使用的网络拓扑结构如图4 1 所示，采 用网络队列管理算法仿真中常用的哑铃式仿真拓扑图： 图4 1r e d 仿真拓扑图 其中，n o ，n l ，n 2 和n 3 为网络终端，每个终端均可发送和接收数据包： r o u t e r l 和r o u t e r 2 为路由器。终端到路由器的链路带宽均为3 m b i t s ，路由器间 链路带宽为2 m b i t s ，这样两个路由器之间形成瓶颈链路，r e d 算法在路由器中实 现。n 0 ，n l 与n 2 ，n 3 的通信通过r o u t e r l 和r o u t e r 2 进行转发。数据包长度固定为 10 0 0b y t e ，路由器缓存设为6 4 k ，仿真时间为10 0 0s 。其中的参数设置为： ( i ) q = 0 0 0 2 ，m a x p = 0 0 2 ，m i n t h = 5 1 2 0 0 0 b i t s ，m a x t h = 1 0 2 4 0 0 0 b i t s 每个源端采用f ，i p 流作为输入流形式。 路由器处的节点模型如下图： 山大学硕十论文 队列q u e u e 中的进程图如下： 图4 2 节点模型 r e d 算法描述如下： f o re a c hp a e k e ta r r i v a l 图4 3 节点的进程图 c a l c u l a t et h en e wa v e r a g eq u e u es i z eq a v i fq i i l i n q a v q i i l a x u e e m p t y 】 中山大学硕士论文 i n c r e a s ec o u n t c a l 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