（控制理论与控制工程专业论文）多瓶颈链路下的主动队列管理算法研究.pdf

硕 士 论 文多瓶颈链路下的主动队列管理算法研究 a bs t r act as th e 找 甲 l d e x p ansi onofth e n e 。 刃 。 比 edu ser gro叩 明 d e m er g e n c e ofn 巴 胃 netwo rk 即p li ca ti ons ， 玩 肥 m 以。 习 币c b asb e e nin c 氏 笼 is i n gd . ln 坦 ti c ally，an dn e two 比 c ong e s ti on a p 侧 浓 rsto be am 眼 叨 dm o re币ti cal p r o bi enl alth ough t c pc ong es ti on c onti 劝 1 m 既 h hasm b as ed佣 s o u r c e n odesise 价 双i v e inth e p r e v en ti onofcon g es t l on c o l a p se ， it als。 几 。 留 刀 1日 11 y n ew crises i 七 。 吧 fo r e ， it isn e c e s s 鲜 for the n e t w o rki 。 祀 l f top a 比 i d p ate in con g es ti on coo ti d i . as oneofth e m os t i 州 pe枷 t con g es ti on co n tl o 1 5 加t e g yinth e n e tw o 改n 侧es ， a q m ( a 比vequeue m ana g a 叮 ent)b a s b e c o m e a h o t n 芝 记 al c h 别 比 么in c o n g es 石 on c o . tr olth e s e y e aj 名 ， h this p a 拼 甄we fi rs t inti 丫 刃 uce sev e n drepr 邸enta 石 ve a q m al g o 6 thi习 5 . in o r d erto re v eal th e a q mal gori t 址 ns ， 讲 而仙助ce ， th ese al g o n th 且 招价 s i ln u l at 曰 u s l n gn e 。 浑 。 谁 si m u l ation so ft w are n s 一in咖9 】 e bo旧 enec k netwo rk s . m ore ov er， w e p ayo ura tt en t i on on the m ul ti ple botd en“ kn e 卜 刃 。 6 沼 ， 撇 ng about the a ct in gofa q m al g orith 双 und er c o mp】 exenv 止 0 刊 m e n 七 山 阅we gi vea g e n er 幻1 已 n n onit. d ue 句th e w 比kn 已 邓ofold a q mal g o ri 比 叮 招 ， a ne wa q mc o m 户 沈 到0 叮ai g o n t 加 肚 b as edon q u e u e l eng t h and m u . 面 v e la t e o f queue l e n g thi s 户 ro p o ， 刘in而s p a 户 抓仕 叮 。 u gh 加p ro v in gth e of d a q mat g o ri 山 批， 。 e wa q matgori如nsh a v e b 已 以 er详r fo 加a n ceth an 山e o l d o n es.5 1 和l1月 行 onsu n d e ry 面 o u sn e 口 胃 。 比 即v n 山 旧 由招 sh0 w that then e w ai g o n t h l nisa 七 l e to引 泊 b ili zethe q u e u e 蜘 沙 tothe targ e t v al 哪， 姗p m v e the sy s te n l n 治 户 加 d s pe曰， 明d h ave g 以 记robus 加 es s 朋d ada p tab ili ty k e y 叭 勺 r ds: c o n g es ti onco n ti 劝 1 ， a q m ， m u lti ple b o tt l e n e c k n e 。 刀 。 比 5 ， 5 妇 力 u 】a d o n 声明 本学位论文是我在导师的 指导下取得的研究成果， 尽我所知， 在本 学位论文中， 除了加以 标注和 致谢的 部分外， 不包含其他人已 经发表或 公布过的研究成果， 也不包含我为获得任何教育机构的学位或学历而使 用过的材料。 与我一同工作的同 事对本学位论文做出的贡献均己 在论文 中作了明确的说明。 研究生签名凉 充 可2 了 年了 月 口 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电 子和纸质文档， 可以 借阅或 上网公布本学位论文的部分或全部内容， 可以向 有关部门或机构送交并 授权其保存、 借阅或上网公布本学位论文的部分或全部内容。 对于保密 论文，按保密的有关规定和程序处理. 研 究 生 签 名 二 遗 二 鱼 五2 “ 7年7 月 0 日 硕士论文 多瓶颈链路下的主动队列管理算法研究 1绪论 1 . 1网络拥塞控制的研究背景 在最近的二 十年内h t o m et取得了 突飞 猛进的 发展， 与此同时， 用户需求的增长 速度也 丝毫 不逊色于加 记 m 以的发 展速度。随 着用户需求的复杂 化以 及多样化， 传统 的h t e n l et己 经难以 满足用户的需 求， 渐渐 显露出 疲态。 对于 初期的in t 曰 旧 e t 而言， 其业务以文 件传输、 电子邮 件以 及远程接入为主， 19 90 年，这三种业务占到 加 怡 m et骨干网中总业务量的 70%。到了 1 995 年，这三种业务 所占比 重迅 速突降 到38% ， 而w w w ( m 勺 d d widsw 七 b ) 业务所占 比 重上升到24%， 2 仪 巧 年的m c in et骨干网 数 据统计表明， w w w应用业务数据量已 经上升到了79% ， 一跃成为h tern et中 最为主 要的 应用业务。 hi t 。 刀 et应用需求的 不断 变化给in t e m et技 术施加了巨 大的压力， 有限 的网络 资源被 越来越多的 用户所共享， 现有的网 络带宽己 经不能满足用户日 益增长的 需求， 再加上许多新的 流媒体、 视频和音频数据业务的不 断涌现，网络拥塞问题不可避免地产生了。 当网络 用户提交给网 络的 负载超过路由器等网络设 备的 处理能力 即资源短缺) ， 造成网络吞吐量急 剧下降， 分组大量丢失， 严重时会致使网 络瘫痪， 这种现象就称为 网络拥塞11 。 虽然拥塞源于资 源短 缺， 但仅仅是增加资源并 不能 避免拥塞的 发生， 有 时甚至 会加 重拥塞程度阁 。 例如:当 路由 器的缓冲区资源 成为网 络的瓶颈时， 增加缓 冲区将会增大分组的 排队 延迟， 如果总延迟超过端系统重 传时 钟的 值， 就会导致数据 重传， 反而加重了 拥塞。 所以 说， 拥塞产生的 一个重要的原因是资 源的“ 相对” 短缺。 当 解决了一 种资 源短缺的“ 瓶颈” 时， 另 一种原本充足的资 源就 会随之 转化成为 “ 瓶 颈” ， 这是 一个不可调和的矛盾。 另 外， 由 于h t 。 刀 et的 异构性和负载的不确定 性， 流 量 在时 间 空 间 上的 分 布 不 均 网 ， 也 将 导 致 局 部 或 者 暂 时 的 拥 塞， 所以 必 须引 入 有 效的 拥塞 控制 机制对网 络资 源进行 合理 分配。 拥塞控制的 研究始于80年代中 期，19 84 年， n a gl e 首 次指出由 路由 器连接的 带 宽差 距较大的 复杂网络中 存在着网 络拥塞的隐患， 然而当 时的科 研界并没 有予以 足够 的 重 视。 直 到1 9 86年 ， in teln et 首 次出 现了 一 系 列的 拥 塞 崩 溃( c on g es ti onc o l】a p se ) ， 致 使网 络 吞 吐 量 急 剧 下 降 ， 其 中 为 人 所 熟 知的lbl 到uc b 吐el ey的 网 络 流 量 突降 现象即发生 在这段时期. 至此 之后， 大量的网络 拥塞控制研究工作迅 速开 展起来. 绪论硕士论文 1 . 2拥塞控制简介 拥塞控制的主 要目 标是控制 输入网 络的 流量， 保证通信子网的正常运作， 合理利 用链路瓶颈资源， 实现网 络资 源利用率和传输延迟等综 合性能 指标的 最优化。 需要进 一步的了 解的是， 网络 拥塞控制的目 的不是要完全 避免 拥塞， 而 是要把拥塞的 程度控 制在合适的范围 之内， 这样才能实 现对网 络资 源的 充分利用。这是因为 在in t 。 刀 et中 采取分组交换技 术来提高链路的 利用率， 因 而路由 器的队列缓存 空间 若经常处于满状 态， 此时 链路利用率较高然而 传输延迟较大; 反之， 如果 路由器的队 列缓存处于空状 态， 那么传输延迟 将减小 ， 但是链路利用率也随之降 低。 所以， 采取合适的网 络拥塞 控制策略 来提高网 络的总体 性能、 维持网 络系 统的 长期稳定工 作具有重要意义。 拥塞控制根据其作用和实 现位置的 不同， 可以 分为两大 类: 基于源端的 t c p拥 塞控制12 和基于网 络端的 拥塞控制 3 。前者用于源端节点 处， 其作用是使源端根据接 收到的 反馈信息调整发送 速率; 后者用于网 络中间 节点 ( 主要为路由 器) 中， 作用是 检测网 络拥塞的 发生， 向 源端发 送反馈信息。 下面将对两 种不同 的拥塞控制机制做一 下简单介绍。 众 所 周 知 ， in te m et 采 用 的 是 统 计 复 用 ( s tatisti calm ul tip i如 9 ) 【5 司 技 术， 因 此 必 须提供拥塞控制机制。 tcp 端到 端的 拥塞控制机制是确保in t 。 刀 et鲁 棒性( r obus tn es s) 的重要因素。 当 链路发生拥塞时， 代p 源端会降 低数 据的 发送速率， 从而使 得大量的 tc p连接能够共享一条拥塞的 链路。 tc p拥塞控 制机制已 被证明在防止 拥塞崩溃方 面 取 得巨 大 的 成 功 59。 在 基 于 源 端的tcp 拥塞 控 制 方 面 ， 大 量 的 研 究 工 作 主 要 集中 在协议参数的修改以 及考虑加入一 些与网络层配合的 新的 机制。 近年来， 犯p中 采用 了 很 多 新 的 算 法 ， 包 括 慢 启 动(s lo w s iaxt) 14 、 拥 塞 避 免( c on g estion av oi danee ) 图 、 快 速 重 传( f ” t r e 忆 劝 5 恤) 141 、 快 速 恢 复( fast r ec o v 。 丁 ) 陈 润 、 选 择 性 应 答(s el ective a cknowledg 周 旧 ent) 【刀 等 。 而 进 一步 的 研究 工 作 包 括 对 慢启 动的 改 进 1明 、 减 少 不 必 要 的 超 时 重 传 和 快 速 重 传 111 、 基 于 速 率 的 控 制 策 略 lln、 a c k 过 滤 1131、 tcp 一而 en d lsl l 的 拥塞 控 制 和 特 殊网 络 环 境( 如 无 线 链 路、 卫 星 链路 和 非 对 称 链 路 等 ) 115 ，1幻 刀 中 的 拥 塞 控 制 等 。 经 过 多 年的 发 展， t c ，衍变出 许 多 不同 的 版 本， 包 括r eno 阔， tah 砂 气 n e 切 r en oll 刃 ， s ackl却” ， 垅 g as 圈 等. 对于网 络端的 拥塞控制方面，由于in tern et数据分组本质上是突发的，因 此允许 传输突发的 分组非常必 要，而路由 器中缓冲队列的 重要作 用就是吸收突发的数据分 组。 较大的队列能 够吸收更多的突发数 据，提高吞吐 量， 但tc p 机制往往会保持较 高的队列占 用，从 而增加了 分组的排队延迟。所以 必 需对路由 器中的队列 进行管理， 以维持较小的队列 长度。 维持较小的队列长度除了降 低排队延迟、 提高 吞吐量外， 还 能保持较大的队列空间来吸收突发数据分组，因而非常必要。网络端的拥塞控制机制 硕士论文多瓶颈链路下的主动队列管理算法研究 研 究目 前 集 中 在“ 主 动 队 列 管 理” ( aqm ) 算 法 阁 . 在 这 方 面 发 展 极 为 迅 速 ， 近 几 年 来 提 出 的 算 法以 及 改 进 算 法 主 要 有red 13n， a r e d i钩 ， s r e d 149i ， b u je 150jij ， r e m 147 52 ， 脚q 15 3) ， 州54 ， d r 卫 d 14di， c h o 既14 1 ， p d14 21 ， 即一r e d 拼 3 ，v s c i44 1等 。 s r e d 等的 主要思路是根据网 络中负载的 情况对丢弃概率进行动态调整; r e m 利用了网络 流量优化理论中 链路影子价格的概念来探测和控制网络的 拥塞状态; pl 等算法应用 控制理论非线性模型， 在链路中 设置比 例积分控制器以 增加系 统的稳定 性与 适应能 力; avq利用了 虚拟队 列的概念，用简单的微分方程在线调 节虚容量， 借助利用率 因子 和阻 尼因 子的调整在高利 用率 和小队 长之间实现恰当 的平衡， 本 质上也是一种早 期分组丢弃技术。 1 . 3选题的目的 及意义 玩 t 。 旧 et发展的初期采用的是 基于源端的t c p 拥塞控制， 所有的 工作都将研究重 点集中 在端系统上，对于网 络中间 节点 考虑的较少。 随着加 t 曰 旧 et的 迅速发展，网 络 规模日 益庞大， 网络结构日 趋复 杂， 仅仅依靠t c r端到端的 拥塞 控制是远远不够的。 于是人们把研究的重点转向了 网 络端中 的路由器等中间节点设备， 期望通过增强它们 的功能 来实现端系统所 难以 达到的 技术目 标. 较之端系统而言， 网络中间节点 具有其不 可替代的 优势， 它能够 更及时了解、 甚 至提前了解网络的拥塞状态， 并采取恰当的拥塞控制策略， 使网络能有效的避免拥塞 以 及尽早从拥塞 状态中恢复过 来。 所以， 网络中间节点的 拥塞 控制 策略的 研究对于改 善网络性能，提高网络的稳定 性， 提供更好的伽5( q u 川 i tyofs erv i ce) 保证具有重 要的 意义。 而 主动队 列管理作为网络中间节点 的重要 拥塞控制手段， 越来越受到人们 的重视。 虽 然 到目 前 为 止， 主 动队 列 管 理 算 法 的 研 究 取得了 不 少 的 成 就 14 润， 然 而 主 动 队 列管理算法仍未 得到广泛的实际 应用。 由于 算法的分 布性、 网 络的复 杂性和对算法的 性能要 求使得主动队列管理算 法的 设计具有很高的难度。 就目 前而言， 对主 动队列管 理算法的 研究还不是很完善， 其中很重要的一 方面体现在网 络拓扑的 研究上。 现有的 对主 动队 列管理算法的 研究绝大多 数采用单瓶颈链路拓扑， 而对于多 瓶颈链路拓扑 却 少有涉及。 在单 瓶颈链路条 件下研究各种主动队列管理算法的理论 性能 是可行的， 然 而现实的网 络却是更为复杂的， 瓶颈链路之间的 相互影响、 源端及交叉 流量 端对瓶颈 资源的争夺、 交叉流量 对网 络的影响等 等， 这些因素是单瓶颈链路所无法 模拟的， 而 这些却正是影响 实际网 络性能的重要因素。 相 对于单瓶颈链路拓扑 而言， 多 瓶颈链路 拓扑 是 一 种 更 接 近 于实 际 的 网 绍 模 型 ， 通 过 在多 瓶 颈 链 路 条 件 下 对 各 种 主 动 队 列管 理 算法进行研究， 更能揭露算法在实际网 络中 可能遇到的问 题， 因 而对多瓶颈链 路网络 绪论硕士论文 进行深入研究对于推动主动队列管理算法与实际网络的融合具有重要意义。 1 . 4本文的组织结构 . 第一章 绪论 对 in t e m e t 拥塞控制进行分析和综述，介绍拥塞控制概况，阐述k t 。 刀 et拥塞控 制研究的背景和现状; . 第二章 主动队列管理算法及算法仿真 重点 研究 几 种典型的 主 动队列管理 算 法， 利用n s 一 2( n e t w ork s l m u l at or ， 2 ) 仿真 软件， 在单瓶颈链路条件下， 对现有主动队列管理算法进行模拟仿真， 并对仿真 结果作出分析评价; . 第三章 多 瓶颈链路下a q m算法性能 研究 多瓶颈链路条件下主动队列管理算法的详细性能分析总结， 通过全面的仿真， 揭 示出 各种典型主动队列管理算法的实际性能; . 第四 章a q m 毛算 法 提出一种新型的主动队列管理补偿算法， 并在多瓶颈链路条件下进行仿真， 考察 改进后的a q m算法在多瓶颈链路网 络中的性能表现; . 第五章 结论 总结本文的研究工作，并提出进一步的研究方向。 硕士论文 多瓶颈链路下的主动队列管理算法研究 2主动队列管理算法及算法仿真 2 . 1引子 正如前面所说的， t c p拥塞控制机制是必须的，而且是有效的， 但这种机制的 有效性依赖于两个基本的假 绝大部分的流都采用了 设工3 幻 : t c p 拥塞控制机制; 这些流所采用的机制的控制方式是同质的，即在 相似的环境下不会占用比t p 流更多的带宽，也即是1 p 友好流。 : 然 而 ， 种 种 迹 象 表明 这 两 个 假 设 并 不 是经 常 能 够 成 立的 困， 导 致 假 设 不 成 立 的 主 要原因如下: . 些用户有意或无意使用了n on. t c p的拥塞 控制算法。比 如修改t c p ，使得窗 口 的初始值很大并且保持不变; . 一些应用没有采用拥塞控制机制，因 而不能 对拥塞 作出反 应。 在现实网 络中， 大 量的 多媒体应用和组播应用都属于此类; . 一些应用采用了 拥塞控制算法，但并不是t c p 友好的。 另外， t c p拥塞控制还存在着自 相似、效率、公 平性等方面的问题 123，因而仅 仅依靠 t c p拥塞控制机制是远远不 够的，必须 采用基于网络端的拥塞控制机制进行 补充，让路由器等网络中间节点设备也参与进行拥塞控制。 路由 器上的拥塞控制机制 ( 确切的说是拥塞避免机制)主要包括 被动队 列管理 ( p assl veq u e u e m an a g eme n t ， p q m ) 圆和 主 动 队 列 管 理( a ctivequeu e m anag 曰 的 e d t ， a q m) . 管理路由 器队 列长度的 传统技术是为每 个队 列设置一个缓冲区 ( 以 分组为单 位) ， 然后接受到达的分组 进入缓 冲队 列直到队 列溢出 ，接下来到达的 分组就要被拒 绝 进入 队 列直 到 队 列 长 度 下降 。 这 种 技 术 也 就 是 所 谓 的 尾 丢 弃( drop- tail ) 算 法 124。 虽然这个 方法在当前玩 记 m et上得到了广泛的使用，但 是存在着重大 缺陷: . 导 致 全 局 同 步 ( glo b als 卯 c hro吐 za t ion) 。由 于h te rr !e t 上 数 据的 突 发 本 质， 到 达 路由 器的分组也往往是突发的。 如果队列是 满的 或者几乎是满的， 就会导致在短 时间内 连续大量地将到 达分组丢 弃。 而t c p 流具 有自 适应特性， 一旦 源端发 现分 组丢失，就会采用慢启 动算 法， 急剧减小发 送窗口， 降低分组发送速率，于是网 络拥塞得以 解除， 但源端得知网 络不再拥塞后又开 始增加发送速率， 最 终又不 可 避免地造成网 络拥塞， 而且 这种现象会周而复始地 进行下去， 从而在一 段时间内 网络处于低链路利用率状态，降低了整体吞吐量; 主动队列管理算法及算法仿真硕士论文 . 资源分配不合理， 容易 产生死锁 ( l x k 切 0 。 在某些情况下， “ 尾丢弃” 算法会 让某个流或者少数几个流独占 队列空间， 由于队列空间 被少数流占 据， 其它流就 会因为空间缺乏而被抑制。这种 “ 死锁” 现象通常是由于同步或其他定时作用的 结果; . 持续满队列状态， 缓冲反复 溢出。 由于 “ 尾丢 弃” 算法只 有在队 列缓冲区满时 才 会通过丢弃到达分组， 向 源端发出 拥塞信号，因此 在队 列未满的 情况下， 到达 路 由器的分组都将入队 直至队 列溢出， 这样会使得队 列在 相当 长时间内 处于充满 状 态，这也是导致全局同步现象的导火索。 在当 前的in t e rn et上，分 组丢弃是对源端进行拥塞通告的 重要机制， 解决路由 器 满队列的 方法便 是在队列充满 之前丢弃到达分组， 这样源端便能 在队列溢出 前对拥塞 作出反应，这种方法便称为 “ 主 动队 列管理” 。 主动队 列管理是一种积极的管理资源 的 机制， 它对网 络上可能出 现的 拥塞情况 进行预判， 然后在 情形恶化之前采取一定的 机制来通知发 送方， 从而可能避 免严重拥塞的 发生。 较之于 传统的队列管理或调度机 制， 主动队列管 理算法 具有以 下的一些优点: . 避免 死锁的发生。主动队 列管理几乎可以 保证随时为新 来的分组提供缓存空间 ， 从而能 够避免死锁行为的 发生。同 样的， 主动队列管 理可以 阻止路由器对 低带宽 高突发性流形 成偏见; . 维持较低的时 延。 主动队列管 理可以 通过 维持较小的 平均队列长度来减少分组的 传输延迟， 这对于交互的 或实时的应用尤为重要， 例如现在 越来越 流行的 视频会 议， 多媒体应用等等。 这种类型的应用可以 容忍部分的分 组丢失，然而延迟对这 类应用的影响将是巨大的; . 有效减少分组丢弃数量。 网 络中流的突发性是不可 避免的， 如果路由 器的队列缓 冲区己 经为稳定状态的流所占 用或者缓存空间不足， 那么路由 器就 没有能力来缓 存突发流。 主动队列管 理通过维持一 个较小的队列 长度， 可以 提供更大的能力 来 吸收自 突发流， 而不用被迫丢 弃到达分组。 下面就对几种具有代表性的主动队列管理算法进行说明分析。 2 . 2几种具有代表性的a q m 算法 2 . 2.ir e d算法 讲到主动队列管理， 有一 个算法不得不提到， 那就是著名的r e d算法脚 橄 口 刀 . r e d通过在网 络中间 节点 处监视平均队列长度来进行拥塞控 制，其出 发点是为了与 tcp 拥 塞 控制 进 行 有 效 配 合 . r e d的 意图 是 在 拥 塞 发 生 早 期 ， 通 过 计 算 平 均队 列长 硕士论文多蔽预链路下的主动队列曹理算法研究 度检测最初的拥塞， 然后用丢弃 ( 或标 记) 到达的分组的 方法向 源端通报拥塞， 这 意 味着路由 器以后不必丢弃更多的 分组，这样对面向 连接的tc p 流来说， r e d就有可 能避免丢弃属于同一连接的 连续分组， 从而提高连 接的 吞吐量. r 日 算法的基本思 想是当 有新的 分组到达时， 采用指数加权滑动平均的 方法计算平均队 列长度qave， 并 把qave 与 两 个 预 设 的阐 值 ， 即 最 小 闭 值m in*和 最 大 闽 值爪 “ 、， 进 行比 较 。 若平 均 队 列 长 度 qav e 小 于m 气则 不 丢 弃 分 组 ; 若q av 。 大 于加 味 人 则 丢 弃 所 有 分 组 ; 若qa ve 介 于， inte 与加 叭几 之间， 则根据平均队列 长度卯v 己 计算丢 弃概率尸， 并以 概率尸 丢弃到 达的分组。 其具体算法如下: 每次分组到达时，计算平均队列长度q ave: 卯v e= ( 1 一 礼) x 心 a v e + 气x 叮 扩( q a v e m a x，h) 丢弃到达分组 其中 ，气 为计 算 平均 队列 长 度的 权 值， 爪 ax ， 为最 大丢 弃 概率 ， q 为当前队列长度 r e d算法能够在维持较低的队列长度的同 时容忍一定的突发 流量， 但是该算法 仍 然 存 在以 下 主 要 缺陷 叨: . 没有充分考虑到公平性。 对于不响 应拥塞通告的 连接 ( 如u d p 连接) ， r e d算法 无法对其进行有效的 控制，因 为此类 连接不受拥塞 通告的 影响， 经常会占 用大量 的网 络带宽，导致了 公平性缺陷.由 于 r e d基于平均队列长度， 这就可能 存在 瞬时队 列长度大于平均队列长度的 情况发生。 如果瞬时队 列长度过长， 到达的分 组由于缓冲区已满而必须丢弃， 这时r e d就不发生作用， 相当于“ 尾丢弃” 。 r e d 设计的目 标之一就是尽量避免“ 尾 丢弃” 的发 生， r e d丢弃一个 连接中 分组的概 率与这个连接在路由器中所占用的带宽成正比例关系， 这是因为一个发送速率相 对较大的 连接可供随 机丢弃的分组的数量也相 对较多，因 此在 r e d算法中需要 主动队列管理算法及算法仿真 硕 士 论 文 考虑公平性问 题; . 参数的 设置存在很大困 难。自r e d算法 提出 至今， 它的 参数配置 就是一 个没有 完全解决的问 题，虽 然 r e d允许路由器同时 获得较高的 吞吐量和较低的 延时， 但是r 卫 d参 数的设置十分 敏感， 同样的参 数设 置只能 适应于小部分的 网 络环境. 同时如何配置参 数， 使得 算法在吞吐量、 时 延等方面 均达到较好的 性能也 有待解 决; . 对 拥 塞 程 度 的 判 断 不 准 确问 题 ， r e d 需 要 确 保 反 馈 给 源 端的 拥 塞 通 告 信 息 能 够 充 分降低了 源端的 发送速率， 而不是降低了 链路利用率。 但当有大量活 跃的 t c p 连接时，总的流 量突发 性是非常高的，队列 长度的 增减也非常迅速， 而 r e d无 法根据队列长度 对拥塞程度作出有效的估计， 所以 也就来不及作出 适当的反应。 为此，围 绕r e d算法本身，专 家学者 展开了 许多的研究工作 既有从 理论角 度分 析r e d算 法缺陷 的， 也有从仿真或实验入手验 证r e d算 法有效性的， 大多数工 作试图完 善和改 进r e d存在的问 题. 一系列的r e d的改 进算法也随 之产生， 下面 将 要介绍的a 丑 卫 d就是最为常见的一种。 2 . 2.2a 卫 e d算法 r e d 的一个弱点是平均队列 长度对拥塞程度和参数设置很敏感。 为了 提高 r 卫 d 算 法 性能 的 鲁 棒 性 ， 一 种自 适 应 调 整 控 制 参 数 的 算 法 a r e d( a da p ti v e r e d ) 【从 调 产 生t。 a 只 e d 是比较成 功的 r e d 簇改进算法，其思路 很简单。 在r e d 的 基础上， a 卫 卫 d 通过检查平均队列长度qa ve的变 化来感知r e d 的 控制是应该更积极还是更 保守。 如. 果 平 均队 列 长 度 是 在 m i 、附 近 波 动， 那 么 现 有 的 拥 塞 控制 就 太 激 进了 ; 如 果 平 均队 列 长 度 在用 在 、附 近 波 动 ， 那 么 现 有的 拥 塞 控 制 就 过 于 保 守 。 基 于 所 观 察 到 的 平 均队 列 长 度 ， 判 断 平 均 队 列 长 度是 否 在m inte和护彻 凡之 间 ， 对 最 大 丢 弃 概 率p 采 用 加 式 增 加 积 式 减 小( a 卫 以 d ) 的 方 式， 动 态调 整户 的 值，以 达 到 保 持 平 均 队 列 长 度 稳定的目的。 其具体的改进如下: 硕士论文 多瓶颈链路下的主动队列管理算法研究 对于每次平均队列长度叮 ave 的 计算， q d v 召 增加 ta 馆 e t 而如果该分组将导致虚拟 队列溢出，则在虚拟队列中将该分组丢弃，并在实际队列中也丢弃该分组。 其具体算法如下: 每次分组到 达时， 计算虚 拟队列长度 v q: vq =v c一c x( t 一5 ) 如果 vq b) 在实际队 列中丢弃该 分组 e ls心 vq= vq十 b c. = nt in( c +a x 洲c x ( t 一5 ) ， c) 一a k b 如果 c 厂 仔时， 即 在两次 采 硕士论文多瓶颈链路下的主动队列管理算法研究 样间隔内队列长度的变化量大于2 万时， 队列长度的变化速率即是不正常的，应当加 以限制。 4.2 . 2区域问题 区域问 题关系到a q m 一 c算 法所起控制作用的强弱，下面作详细说明。 以最典型的主动队 列管理算法r e d 为例， r e d 的思想是计算平均队 列长度qave， 并把qave与 两个 预设的 闽 值m in.和加 叭 汤 进行比 较。 若 平 均队 列长 度叼 翻 君 小于m in 若q av 。 介 于爪 1 、与尸瓜 城 内 之间 ， 则 根 据平 均队 列 长度叼 仰 计算丢 弃 概率p ， 并以 概率p 丢 弃 到 达的 分 组; 若qa ve大 于放 玫 1、 则 丢弃 所有 到 达分 组。 那么， 由队列长度的 变化所引起的对到达分组的丢弃或入队的判断， 丢弃( 入队) 概率的大小的确定就形成了 所谓的区域问题。下面给出r e d算法具体的区域划分情 况。如图4. 1 所示，图中箭头朝上代表队列长度增加区 域， 箭头朝下代表队列长度减 小区域; 在图4. 1 (a)中， 0 区 域、 1 区域分别代表入队区域和丢弃区域; 在图4 . 1 (b ) 中， l( 1 卫 电 e)区 域、 m( 珑翻e)区 域、 5( s m al l ) 区 域 分 别 代 表大 概率区 域、中 等概 率区域、 小概率区 域;图4 . l( a) 、图4 . i( b) 两者的结合 就是图4 . 1 ( c) 了 ， 其中， 犷0 区 域代表大概率一 入队区域，5 一 1 区域代表小概率一 丢弃区域，依此类推。 云叻f勺，o 臼盆既nr 叹曰r。u凌 子份 。舟兴。 七 uff e r 曰j 伯 叼 r e f . 1 、 !日ro 子份 :升六l . ( a ) r e d的于1 区域图 . (b) r 印的控制强度区 域图 汗专 s仁 曰尹1六认 b uff er . 日 工 . q r . f .1 口 . ( 。 ) r e o 的综合区域图 图 4 . ，咫0 的区域分布图 a q m补偿算法 a q m， c )设计 硕士论文 图4 . 1 中 ， ze ro代 表 空 队 列; b 科 价 r 代 表 缓 冲 区 长 度; 。 in 如 果 参 数 选 择 合 适的 话 ， 期 望队 列 长 度叮 r 扩将处 于加 inm和胭 双 认 中心。 由图4 . 1(c) 可以 看出， 虚线两侧的区 域划分水平对称， 故而r e d算法是一种 对称型结构算法，即不论处于队列长度增长区域还是队列长度减小区域，r e d对到 达分组的 处理 ( 包括到 达分组的 丢弃或入队， 丢弃 ( 入队) 概率大小的判断) 完全一 致。 不仅是r e d ， 其它的一些主动队列管理算法诸如pl， b l u e ， a r e d等也是对称 型结构算法。 对称型结构有一个很大的缺陷， 它只能实现在垂直方向上对队列长度区 分控制， 而在水平方向 上无法 对其区分对待， 这就使得算法在对队列长度控制的 准确 程度上有所欠缺。 如果能够将对称结构进行拆分， 对于不同的区域采取不同的控制策 略，那么将使得算法对队列长度控制的准确性得到很大的提高。 a q m 一 c算法就是一 种非对称型结构算法， a q m 一 c 算法 将从垂直方向以 及水平方 向 对队列长度进行二维控制， 使得区域的划分更为细致， 从而使队列长度得到更为准 确的 控制。图4 2给出了a q m 一 c算法的区 域划分具体情况. .一j 子份 。舟六。 b uf f e r q ref+r 翻 刀 9 日 一 r 盆 0日 吧 矛号 一l升六l r吕 幻皿 . q 代f q 了 . f r 目目 妞 日 r+1 ffff bqq叼 件 ( a ) a 湘一 的0-1 区域图( b ) 八 洲一 的控制强度区域图 带号 : 舟 卖 刁 入曰 七 朋 f f . r 口 ref+r a 刀 9 . 口 ref 口 r . f一r an幼 ( 。 ) a 洲刃 的综合区域图 图 4 . 2加卜c 的区域分布图 图4 2中，朋 刀 召 代 表期 望队 列长 度波动范围 . 可以 认 为( q 可十 洲召 仑 ) 相当 于 刀 以 、 ， 而(q rof一 朋 昭 目 相当 于m inte。 比 较图4. 1 (a) 与图4 2( a) ，图4. 1( a) m in.到q 可 这 个区 域中， 无论队 列 长 度是处于增长区域部分还是处于减小区 域部分， r e d算法都 将以 一定概率丢弃到达 3 8 硕士论文 多瓶颈链路下的 主动队列管理算法研究 分组。 而 在图4. 2( a) 中， 如果队 列长 度处 于增长区 域部 分， a q m 一 c算 法对以 一定 概率丢弃到达分组:如果队列长度处于减小区域部分， a q m 毛算法以 一定概率将到 达分组 入队。 因 为m 气是期望队 列 长度 波动范围 的 下限，当 队 列 长度 位于m inte到 q 可 这 个区 域中， 我 们 期望队 列 长 度能 够 达到 期 望 值q 可 ， 即 队 列 长 度能 够增长， 然而队列长度的增长速度又不能过快， 以致于算法来不及控制， 从而使队列长度超出 刀 以 、。 当 队 列 长度是 处 于 增 长区 域时， 需 要 通过 提 前丢 弃， 对队 列 长 度的 增 长速度 作出 一定的限制， 使增长速度减缓， 减小队列长度的 波动; 当队 列长度处于减小区域 时， 如果再丢弃到达分组， 将使得队 列长度的 减小速度加剧， 从而 很可能会使队列长 度超出 期望 下限m i 飞， 所以 在这 个区 域应该适当 地将到 达分组入队， 使队 列长度减 小速度减缓，减小队列长度的波动。 再比 较图4. 1 ( b) 与图4 2( b)， 图4. 1 ( b) 中 用 摆 、到五 咧 斤 ; 这个 区 域中， 无 论 队列长度是处于增长区域部分还是处于减小区域部分， r e d算法对到达分组都起到 强的控制作用。而在图4. 2( b) 中，如果队列长度处于增长区域部分， a q m一 c算法 对到达分组对到达分组起到强的控制作用; 如果队 列长度处于减小区 域部分， a q m -c 算法对到达分组对到达分组都起中 等控制作用。 前人的实验结果表明， 在队列长度增 长区域， r e d的强控制作用将使得队列长度的增长趋势在这个区域会得到很大的抑 制直至发生转折， 队列长度由 增长转为减小。 由于控制算法的作用不是实时的， 而是 有一定的时 延，故而在队 列长度下降区域， r e d算法仍然会保持强 控制作用，从而 使得队列长度的减小速度加剧， 很可能使得在以后的一段时间内， 队列长度的减小趋 势 得不 到 有 效 抑 制， 使队 列 长 度 超出 期 望 下限 m in * 。 所以aqm-c 算 法 对此 作出 改 进， 在队列长度增长区域起强控制作用， 扭转队列长度的增长趋势; 在队 列长度下降区域 起到中等的 控制作用，既减小了队列长度，又有效地减缓了队列长度的减小速度。 在叮 可到 加 戏 这 个 区 域 中 ， 原 理 与 刀 姐 、 到 石 州 介 ; 区 域 类 似 ， 可 参 考 上 面 的 解 释 。 屯2.3丢弃 ( 入队) 概率 在系统的负载情况不确定时， 分组丢弃 ( 入队) 概率p 与n u m、用 存在如下 关系 尸 = 丝 塑二 竺 nl 助 汪 ( 4 . 1 ) 其中c为基准值，一般取c=1 ， c x一 nu m 即有: 尸= nu m 一了 万 nu mz ( 4 2) 尸 代表了 每n u m个分组进入路由器缓冲区的这段间隔内， 队列长度的增长或者 a q m补偿算 法( a q m . c ) 设计 硕士论文 减小幅度超过了规定允许范围7h 的概率。利用式 ( 4 .2)计算出所有符合 p10 7h 八 亿 朋 才 ， 0 4 00 m : 的大时延条件下的适应能力。 其中， r l 习 ， 在4 00， 540 毫秒内 服从均匀分布，发送端的tc p 连接数为40， 交叉流量端的t c p 连接数均为 2 0 。 硕士论文多瓶颈链路下的主动队列管理算法研究 2弓 ) j 1 8 0 16 0 1 魂 0 1 2 0 1 d0 80 60 今 0 20 o 2以 1 80 1 60 1 4 d 飞 即 1 00 砚 石 0 4 o 20 0 队列长度分细 5o10 0 1 5 02 0 0 时 国( 5 1 2 50只d日 5 0 王 001 5 02 0 0 时间 (s j 2万 03 0们 ( a l ) ( a z ) r e d + 算法 ji30 队咧长度一分组 20o 1 幻 0 1 6 0 1 40 1 2 0 1 口 0 即 6 0 4o 2o o 3 0 0 1 日 0 1 6 0 1 4 0 1 20 1 0 0 8 0 阶 曦 0 2 0 0 队列长度分如 50i d o ( b l 1 5 02 ( 刃 时 何(万 1 25 0 久 n口 5oi o 01 5 q2 0 0 时 间 5 ) 25 0 ) a 尺 印 算法( b z ) a r e d + 算法 队列长度一分姐甘 20o 1 8 0 1 6 0 1 4 0 1 2 0 1 0o 田 石 0 40 2 0 d 20o 卫 肋 16 0 1 4 0 1 2 0 1 0 q 印 6o 4 0 2 0 门 队列长度分组 5o1 0( ) 1 503 00 时 何( 5 2 5 030 05 010 0 1 5 02 0 0 时甸 ( 5 2 503 00 ( 。 1 ) pj 算法 ( c z ) p i + 算法 队列长度分如勺 z dd 1 8d 1 60 1 峨 0 1 20 1 00 8 0 石 0 4 0 2o d 20 0 18 0 6 0 1 魂 0 1 2 0 1 0o 印 印 4o 习o o 取列长度分组 3 o1洲 1 5 02 0 0 时 旧(5 25 03 005o1 0 0 1 5 02 ( 汉 时问(5 2 5d3 0 0 d l ) r e m算法 ( d z ) r e m + 算法 4 9 a qm补偿算法 ( a q人 1 一 c)设计 硕 士 论 文 00806040即0080的40 几冲，土1，1，11 队列长度分组) 时肠( 5) 200180160140120100圈印 队列长度一分用) ( e l ) avq算法 ( e z ) a v q + 算法 图 4 . 6r t t在 4 0 0 ，5 4 0 1 时的队列长度 表4 . 4大时延下链路利用率及丢包率对比 仿 真 算 法!娜比 较 犷 一 辰 丽 一 r 蔽 狂 二 赞比 较 i a r e o一 爵 又 r e o * pl 比 较 r e m 比 较人 vq比较 讨 一 不 一 诫一 健rem一 rem 、一 av q ) av q+ 叮哥 耳 片 口 牛 耳 弃 耳 弃 要 由于在多瓶颈链路拓扑中， 时延值一般都处于 一 个较高的水平， 所以要求算法需 要具备一定的预测能力。 由 于a q m 一 c 算法利 用队列长度及队列长度变化的趋势来判 断系统的拥塞程度，所以经a q m一改进的 算法能 够在一定程度上抵消时延的影响， 达到控制队列长度的目的; 在链路利用率方面， p l+ 出现小 幅下降，其它算法均有所 上升;在丢包率方面，人 卫 e d 十 与 a r e i ) 相同，其它算法均有所下降。 4 . 3 . 2 . 5大链路容量情况下算法性能对比 本次仿真考察改进算法在瓶颈链路的带宽较大的情况下的综合性能表现。 将瓶颈 链路容量增加到 巧入 夕 勿 ， : 而其 它链路容量不变时， 队列氏 度的变化情况如图4. 7 所示。 其中发送端的t c p连接数为4 0 ，交叉流量端的t c p连接数均为 2 0a 硕 士 论 文 多瓶颈链路下的主动队列管理算法研究 2oo 15 0 1 6 0 1 0 12 q 1 0 0 80 60 4 0 20 n 艺dd 18 0 1 6d 1 4 0 1 2 0 1 0 0 日 o 60 40 2o o p列长度分组 以列长厦分组 5o100 巧02 0 0 时 倒(5 ) 25 03 00 时伺(5 ( a l ) r e d 算法( a z ) r e d + 算法 卜列长度分组 20 0 18 0 1 6 0 1 4 0 12 0 1 00 bd 右 0 4 0 2o 0 卜列长度分砚 5o1 0 01 5 02 0o2 5 0 习 0d 1 50 1 60 1 4 0 1 20 1 0o 日 0 6 0 40 2 o