主动队列管理算法的研究

Ｉ ｐ 。ｖ ｄ ａ ｔｖ ｅ ａ ｇ ｍ ｅ ｌ ｏ ｉｈｍ ｏ ａ ｒ ｓ ｆ ＣＨ ＯＫ ｅ ｍ ｒ ｅ ｃｉ ｅ ｑｕ ｕｅ ｍ ｎａ ｅ ｎｔａ ｇ ｒｔ ｏ ｆ ｒ ｆ ｉｎｅ ｓ ｏ
ＴＩ ＡＮ ｈ ｏ． ＧＡＯ ｏ ｇ ｈ Ｓｕ Ｚｈ ｎ ． ｅ （ ｏ ｐ ｔ ｃｅｃ ｏｌ ｅ Ｑ Ｎ ｒ ａ ｎｖｒｔ，Ｒｉ ａ ｈ ｎｏｇ２ ６ ２ ，Ｃ ｉａ Ｃ ｍ ｕｅ Ｓｉ ｅＣｌｇ， ｒ ｎ ｅ ｏｍ ｌ ｉ ｓｙ ｚ ｏＳ ａ ｄｎ ７ ８ ６ ｈｎ） Ｕ ｅｉ ｈ
仿真结果表明 ，Ｒ － Ｈ Ｋ 相 比 Ｃ Ｏ ｅ和 Ｈ ＨＯ ｅ算 法能更加有 效地惩罚非响应流 ， Ｌ ＵＣ Ｏ ｅ Ｈ Ｋ Ｃ Ｋ 实现 更为公平的带宽分 配。
关键词 ： 主动 队 列 管 理 ； 平 性 ； 响 应 流 ； ＨＯ ｅ 最 近 最 少使 用 公 非 Ｃ Ｋ； 中 图 分 类 号 ： Ｐ ９ ．７ Ｔ ３ ３ ０ 文 献 标 志码 ： Ａ
ｆ ｉｌ ． ａｒｙ
Ｋ ｙｗ ｒ ｓ ｃｉ ｕｕ ｎｇｍ ｎ （ Ｑ ；ａ ｅｓｎｎｒｓｏｓ ｅｆｗ Ｃ Ｏ ｅＬ ａｔ ｅｅｔ ｓｄ（ Ｒ ） ｅ ｏｄ ：Ａ ｔ ｅＱ ｅ ｅＭａａｅ ｅｔ Ａ Ｍ） ｆｉ ｓ；ｏ － ｐｎｉ ｏ ； Ｈ Ｋ ； ｅｓ Ｒ ｃｎ ｙＵ ｅ Ｌ Ｕ ｖ ｎ ｒ ｅ ｖｌ ｌ
Ａ ｓ ａｔ ｃｉ ｕ ｕ ｎｇｍ ｎ ｌ ｓａ ｐｒ ｔ ｏ ｅｃｎｅｔｎｃｎｒｌ ｆ ｅ ｏｋ ｎｏｄｒｔ ｓｌ ｈ ｂｔ ｃ：Ａ ｔｅＱ ｅｅＭａａｅ ｅ ｔ ａ ｎｉ ｏｔ ｌ ｉ ｔ ｏ ｇｓ ｏ ｏｔ ｔ ｒ．Ｉ ｒｅ ｏ ｅｔｅ ｒ ｖ ｐｙ ｍ ａ ｒｅ ｎ ｈ ｎ ｉ ｏｏ ｎ ｗ ｏ ｖ
第３ １卷第 １ １期
２１年 １ ０１ １月

Ｍ ａｋｏ ｒ ｐｔｅｐ ｃ ｅ ； ｒ ｒｄ ｏ ｈ ａ ｋ ｔ
４ 仿真实验
本节采 用 ＮＳ 作为仿真工具 ， Ｅ Ｆ ２ 将 Ｒ Ｕ与 Ｅ Ｅ Ｒ Ｄ相对比。 仿 真环境的拓扑结构如 图 ２所示 ，Ｓ １ ， ｎ为发送端 ， ｉ ， …，） （ ２ Ｄ １ ， ｎ为接收端 ，Ｓ＞ 为瓶颈链路 ，Ｓ点缓存可储 存 ＝ ， …，） ２ －Ｄ 含 ３ ０个数 据包 的队列 ，数据包 固定长度为 １０ ０ Ｂ ｔ，通 ０ ０ ｙｅ 过在 Ｓ点 引入各种算法 ，观察 Ｓ点路 由器缓存状况、平均 延 时性 能及吞 吐率 ，仿真持续 ２ ０Ｓ Ｒ Ｄ设置参照文献［Ｊ ０ 。Ｅ Ｅ ２， Ｅ Ｆ 设置期望队列长度为 ：ｑｅ ２ 。以下分 ２种 网络状况 ＲＵ ｒ＝ ０ ｆ
Ｔ Ｐ源端将拥塞窗口减半 ，从而无论是丢包还是被标记，下 Ｃ
１
一
２ ＴＰ Ｃ 源端的拥塞控制规律的推演
当前对 网络拥塞问题 的解决主要存在 ２个方向，一个是 在源端（ 即数据包的发送方） 的主机上引入策略 ，使其在感 知 到 数据 包 的丢 失 或在 接送 方 反馈 的报 文 中发 现 拥塞 通 知
ｔ ｅｑ ｅ ｅｌ ｎ ｔ ｕ ｃ ｌ ｏ ｖ ｒ ｉ ｇ ｔ ｅ ｉ ｎ ｔｄ ａ ｍ． ｔ ｅ ｄ ｏ ｒ ｑ ｉ ｍｅ ｔａ ｄ ｐ ｒ ｏ ｍｓｓ ｐｅ ｉ ｒ ｎ ｒ ｖ ｓｔ ａ ｅ ｂ ｔｅ ｅ ｆ ｒ ａ ｃ ｈ ｎ ｈ ｕ ｕ ｅ ｇ ｈ ｑ ｉ ｋ ｙ ｃ ｎ ｅ ｇ ｎ ｄ ｓｇ ａ ｅ ｉ Ｉ ｎ ｅ ｓｌ ｗ ｅ ｕ ｒ ｏ ｅ ｎ ｎ ｅ ｆ ｒ ｕ ｒｏ ｌ ａ ｄ ｐ ｏ ｅ ｏ ｈ ｖ ｅｔ ｒｐ ｒ ｏ ｙ ｍ ｎ ｅｔａ
［ ｂ ｔａ ｔ ｈ ＣＰ ｓｕｃ ｏｇ ｓ ｏ ｏ ｔ ｌｄｓｉｌ ｅ ｒ ｎｒｄ ｃｄｔ ｈ ｏ ｔ ｏ ｇ ｓｏ ｏｔ ｌｐｏ ｌ ａ ｄ ａ ｔ ｅＱｕｕ Ａ ｓｒｃ］Ｔ ｅＴ ｏ ｒｅｃ ｎ ｅｔ ｎ ｃ ｎｒ ｉ ｐｉ ｓａｅ ｉｔ ｕｅ ｏ ｔｅｒｕｅ ｃｎ ｅｔ ｎ ｃｎｒ ｒｂｅ ｉ ｏ ｃ ｎ ｏ ｒ ｉ ｏ ｍ， ｎ ｎ Ａｃｉ ｅｅ ｖ

（ ｏ ｅｅ ｏ ｈ ｓ ｓａ ｄ Ｅ ｅｔ ｎｃ Ｅ ｇｎ ｅ ｎ ． ｕ ｇ ｉＮ ｒ ｌＵ ｉｅ ｉ ， ｕｌ ， ｕ ｇｉ５ １０ ） Ｃ ｌ ｇ ｆＰ ｙｉ ｌｃｒ ｉ ｎ ｅ ｒ ｇ Ｇ ａ ｘ ｏｍａ ｎｖｒ ｔ Ｇ ｉｎ Ｇ ａ ｘ ４ ０ ４ ｌ ｃ ｎ ｏ ｉ ｉ ｎ ｓ ｙ ｉ ｎ
ｔ ’ ｎ ｒ ｍｅ ｔ ａ ｄ ｄ ｃ ｍｅ ｔ ｆｃ ｏ ｙ ａ ｃ ｌ ． ｙ ｔ ｅ ｓ ｌ ｔ ｎ， ＢＬ Ｅ ｓ ｓ ｏ ｎ ｔ ｅ ｏｍ ｉ ｎｆ ａ ｔ ｅｔ ｒ ｔ ａ ｙ Ｓ ｉｃｅ ｎ ｎ ｅｒ ｅ ｎ ａ ｔ ｒ ｄ ｎ ｍｉａｌ Ｂ ｉ ａ ｏ Ｆ Ｕ ｉ ｈ ｗ ｏ ｐ ｒ ｒ ｓｇ ｉ ｃ ｌ ｂ ｔ ｎ ｙ ｈ ｍｕ ｉ ｆ ｉｎ ｙ ｅ ｈ Ｂ ＵＥ ｉ ｅ ｍｓ ｏ ｅ ｅ ｓｚ ｄ ｌ ｋ ｕ ｉ ｚ ｔ ｎ． Ｌ ｎ ｔｒ ｆ ｑ ｕ ｉ ａ ｉ ｔ ｉａ ｏ ｕ ｅ ｎ ｎ ｌ ｉ
Ｃ ｍ ｉ ｄ ｗｔ ｈｅｈｌ ａ ｄ ｂｓ ｎｔｅ ｆ ｚ ｅｒ，Ｂ Ｕ ｓｓａｅａｅ ｑｅ ｅｔ ｄｕｔｔｅ ｄｏ ｐｎ ｒｂｂｌ ｏ ｂｎ ｉ ａｔｒｓｏ ｎ ａｅ ｏ ｈ ｕ ｙ ｔ ｏ Ｆ Ｌ Ｅ ｕｅ ｖｒｇ ｕ ｏ ａｊｓ ｈ ｒｐ ｉｇ ｐｏａ ｉ— ｅ ｈ ｄ ｄ ｚ ｈ ｙ ｕ ｉ
Ｋｅｗ ｒｓ ｏｇｓｏ ｏ ｔ ｌＡ Ｍ，ｌ ｙｌｇ ， Ｌ Ｅ ｙ ｏｄ ：ｃｎｅｔｎ ｃｎｒ ， Ｑ ｆｚ ｉ Ｂ Ｕ ｉ ｏ Ｉｚ ｏ ｃ
１ 引 言
近年 来 。 随着 计 算 机 和 网络 技 术 的 迅 猛 发 展 以及 多 媒 体 应 用 的 急剧 增 加 ． 们 对 Ｉｔｍｅ 的服 务 质 量 提 出 了更 高 的要 求 。 人 ｎｅ ｔ 虽然 目前 Ｔ Ｐ所 采 用 的基 于窗 口 的 端 到 端 拥 塞 控 制 机 制对 保 Ｃ 证 Ｉｔ ｎ ｔ ｎ ｅ ｅ 的鲁 棒 性 （ ｂ ｓ ｅｓ起 到 了关 键 性 的 作用 ， 中 间 ｒ ｒ ｕｔ ｓ） ｏ ｎ 但 节 点 上 的 队列 管 理 严 重 影 响 着 ’ Ｉ ℃Ｐ的 性 能 。 如 。 统 的 去 尾 例 传 （ ｒｐ Ｔ ｉ 队 列 管 理 方 式 造 成 Ｔ Ｐ连 接 的 全 局 同 步 、 列 长 Ｄｏ ａ ） ｌ Ｃ 队 时 间 处 于满 状 态 、 理 突发 业 务 时 存 在 公 平 性 等问 题 。 此 ， ． 处 为 Ｂ

［ ｓｒｃ］Ｂ ｓｄｏ ｍｕａｉｎａ ａｙｉａ ｍｅｈ ｄ ｔｉ ｐｐ ｒ ｙｔｍａｉａｌ ｖｓｉａｅ ｅｐｒｏｍａｃ ｆ ｅ ｅ ｆ ｅｅ ｔ Ａｂ ｔａｔ ａｅ ｎｓ ｌｔ ｎ ｌｔ ｌ ｔｏ ，ｈｓ ａｅ ｓ ｔ ｌ ｉ ｅｔ ｔ ｔ ｅ ｒ ｎ ｅｏ ｒ ｓ ｃｎ ｉ ｏ ｃ ｓ ｅ ｃ ｙｎ ｇ ｓｈ ｆ ｓｉ ｏ ｒ ＡＱＭ （ｃ ｖ ｕｕ ａｔ ｅ ｅ ｅ ｉ ｑ
［ ｙｗｏｄ ｉＡ ｔ ｅ ｕ ｕ ｎ ｇｍｅ ｔ Ｍ）Ｃｏ ｇｓｉｎｃｎｒｌＳａ ｉｔ； ２ Ｋｅ ｒ ｓ ｃｉ ｅ ｅｍａａ ｅ ｎ（ ｖｑ ＡＱ ； ｎ ｅｔ ｏ ｔ ； ｔｂｌｙ ＮＳ ｏ ｏ ｉ
主 动 队列 管理 （ ｃｉｅ Ｑｕｕ ｎ ｇ ｍ ｎ，ＡＱ 作 为 Ａ ｔ ｅｅ Ｍａａｅ ｅｔ ｖ Ｍ） Ｉｔｒｅ 端到端拥塞控制的一项增强手段 ， ｎｅｎｔ 有效地克服了传统 ＤｏＴｉ ｒｐ ａ ｜缓冲管理策略下的满队列、对业务流的死 锁以及全 局同步 问题 。在现有的 ＡＱ 方案中，链路的拥塞都是通过 Ｍ 队列长度、输入速率、缓冲溢出或空 白等 网络特性 或者是这 些特性 的结合来衡 量的。 Ｅ Ｉ ＡＲ Ｄ Ｒ ＤＩ和 Ｅ 采用队列长度来衡 量拥塞程度 ，分组 的丢弃概率通常是队列长度 的线性 函数 。
Байду номын сангаас
定队列长度在 某个范围内 ，但在特 定的网络环境 中依然会造 成多个 Ｔ Ｐ的同步 ，造成队列震荡、吞 吐量降低和 时延抖动 Ｃ 加剧 。 Ｅ …、 Ｒ Ｄ ｊ Ｃ ＯＫ ［和 Ｐ Ｉ都属于这 一类算法 。 Ｒ Ｄ Ａ Ｅ ¨、 Ｈ ｅ １ Ｉ ３ 。 （） ２基于 网络负载的 Ａ ＱＭｓ 这 类算法通过测量业务流量的输入速率或根据分组的丢
Ｓｍｕａｉｎａ ｄＰ ｒｏ ｍａ ｃ ｖ ｌａｉｎ０ ｏ ｃｉｅ ｅ ｅ ｉ ｌｔ ｎ ｅｆｒ ｎ ｅ ａｕ ｔ ｆ ｍｅ ｔ ｕ ｏ Ｅ ｏ Ｓ Ａ ｖ Ｑｕ

ａ ｄ Ａｐ ｌ ａｉｎ 。０ ７ ４ （ １ ： １ － １ ． ｎ ｐｉ ｔ ｓ ２ ０ 。３ ３ ）１ １ １ ４ ｃ ｏ
Ａｂ ｔ ａ ｔ ｎ ｏ ｄ ｒ ｔ ｖ ｒ ｏ ｈ ｉ ｄ ａ ｔ ｇ ｓ Ｏ ｈ ｒ ｄｔ ｎ ｌ Ｐ Ｄ ｏ ｔ ｌ ｒ Ｏ ｈ ｃ ｉｅ ｑ ｅ ｅ ｓｒ ｃ ：Ｉ ｒ ｅ ｏ ｏ ｅ ｃ ｍｅ ｔ ｅ ｄ ｓ ｖ ｎａ ｅ ｆ ｔ ｅ ｔａ ｉ ｏ ａ Ｉ ｃ ｎ ｒ ｌ ｆ ｔ ｅ ａ ｔ ｕ ｕ ｍａ ａ ｅ ｎ ， ．．ｔ ｅ ｄｆ — ａ ｉ ｏｅ ｖ ｎ ｇ ｍｅ ｔ ｅｇ ，ｈ ｉ ｎ ｃ ｈ ｆｐ ｒ ｍｅｅ ｓ ｔ ｎ ｎ ，ｈ ｓ ｐ ｐ ｒ ｐ ｏ ｏ ｅ ｎ ｉ ｔｒ ａ ｄ ｌ ｃ ｎ ｒ ｌ ｂ ｓ ｄ Ｐ Ｄ ｃ ｎ ｒ ｌ ｒ ｈ ｅ ｅ ｔ ｒ ｆ ｔ ｅ ｐ ｅ ｅ ｔ Ｐ Ｄ ｕ ｙ ｏ ａ ａ ｔｒ ｕ ｉ ｇ ｔ ｉ ａ ｅ ｒ ｐ ｓ ｄ ａ ｎ ｅ ｎ ｌｍｏ ｅ ｏ ｔｏ— ａ ｅ Ｉ ｏ ｔ ｌ ． ｅ ｋ ｙ ｆ ａｕ ｅ ｏ ｈ ｒｓ ｎ Ｉ ｏ ｅＴ ｃ ｎ ｒｌ ｒ ｌ ｓ ｉ ｔ ａ ｎ ｙ ｎ ａ ａ ｔｒ ｎ ｅ ｓ ｔ ｂ ｔ ｎ ｄ Ｆ ｒｈ ｒ ｏ ｅ ｂ ｐ ｌｉ ｇ ｔ ｅ ｒ ｓ ｎ ｔｏ ｎ ｏ ｔ ｅ ｅｗ ｒ ｏ — ｏ ｔ ｌ ｉ ｎ ｈ ｔ ｏ ｌ ｏ ｅ ｐ ｒｍｅｅ ｅ ｄ ｏ ｅ ｕ ｅ ． ｕ ｔ ｅ ｏｅ ｅ ｍ ｒ ， ｙ ａ ｐ ｙ ｎ ｈ ｐ ｅ ｅ ｔ ｍｅｈ ｄ ｉ ｔ ｈ ｎ用的爆炸性增长 ，关于网络 ｎｅ ｔ ｎ
用于 网络拥塞控制 中， 得到 了一种新的主动队列管理算 法一 Ｐ 算法有较强的鲁棒性和较 陕的队长调节速率。 Ｉ
Ｉ Ｃ ＰＤ算 法 ，仿真实验 显示 ， Ｃ Ｐ Ｍ —Ｉ Ｉ —Ｉ 法较 Ｒ Ｄ算法和 Ｍ Ｄ算 Ｅ

出之前 就 能对拥 塞 作 出反应．
ｇ ｒ ｈ 和链 路算 法 （ｉｋ ａ ｏ ｉ ｍ） 大类．目前 ， ｏｉ ｍ） ｔ １ ｌ ｒ ｈ 两 ｎ ｇ ｔ 源算 法 中使 用 得最 广 泛 的是 Ｔ Ｐ协议 中 的拥 塞 控 Ｃ
制算 法 ， 而链路 算法 的研究 则 集 中在“ 动式 队列 管 主
理 ” ａｔ ｅ ｕ ｕ ｎ ｇ ｍｅ ｔ简 称 ＡＱＭ ） 面 ＿ ． （ｃｉ ｅ ｅ ｖｑ ｍａ ａ ｅ ｎ ， 方 １ ］
ＡＱＭ 是 Ｉ Ｔ Ｅ Ｆ推 出 的基 于 Ｆ Ｆ 调 度 策 略 的 ＩＯ 队列 管理机 制 ， 自从 Ｉ ＴＦ提 出 了 ＡＱＭ 技 术 并 推 Ｅ
Ｒ Ｄ ３（ ａ ｄ ｍ ａｌ Ｄｅｅｔ ｎ 随 机 早 期 检 Ｅ ＿ Ｒ ｎ ｏ Ｅ ｒ ｔｃｉ ， ｙ ｏ 测） ＡＱＭ 算法 的一 个代 表 ． 究 表 明 ， Ｅ 比传 是 研 Ｒ Ｄ
为 了解 决 传统 的 “ 去尾 ” 法存 在 的 问题 ， 究 算 研 人 员提 出了主 动式 队列 管理 （ ＡＱＭ） 法． 目前 的 算 在 Ｉ ｔｒ ｅ 上 ， 包 是 对 端 节 点 进 行 拥 塞 通 知 的主 要 ｎ ｅｎ ｔ 丢 机制 ， 主动 式 队列 管理 算 法 的特 点 是 在 队 列 满之 前 就 按 一定 的策 略进 行 丢 包 ， 而 使 端 节 点 在 队列 溢 从
和 不 足 之 处 进 行 了分 析 研 究 ．
［ 键 词 ］主 动 式 队 列 管 理 ；随 机 早 期 检 测 算 法 ；自适 应 随 机 早 期 检 测 算 法 关
［ 图分 类号 ］Ｔ ３ ３ 中 Ｐ ９
［ 献标识码］ 文 ：Ａ
网络 中的拥 塞来 源于 网络 资源 和 网络流 量分 布
荐 了 ＲＥ Ｄ算 法 以来 ， 已产 生 了许 多 Ａ ＱＭ 算 法．

摘
要： 实际网络 具有大时滞性和动态特性。针对大时滞特性 ， 根据 内模控制 （ＭＣ 和改进 的 Ｔ Ｐ Ａ Ｍ 控制理 Ｉ ） Ｃ／Ｑ
论模型设计 了一种适合 于大延 时网络环境 的主动 队列管理 算法。而对 于网络 的动 态特性 ， 分析 了网络参数 的 变化给 算法带来 的影响 ， 并以此对算法参数进行在线修正 ， 得到符合 大时滞网络 的 自适应 Ａ Ｍ 算法。最后通过 Ｎ ２仿真 实 Ｑ Ｓ 验验证 了设计的 Ａ Ｍ算 法的可靠性 。 Ｑ
关键词 ： 大时滞 ； 主动队列管理 ； 自适应 ； 内模控制 ； 拥塞控制 中图 分 类 号 ： Ｐ ９ ．３ Ｔ ３ ３０ 文 献 标 志 码 ： Ａ
Ａｄ ｐｔｖ ｃ ｉ ｅ ｑ ｕｅ ｍ ａ ａ ｅ ｅ ｌ ｏ ｉｈｍ ｓ ｄ ｏ ｎｔ ｒ ａ ｏ ｅ ｏ ｒ ｌ ａ ｉ ｅ ａ ｔｖ ｕｅ ｎ ｇ ｍ ｎｔ ａ ｇ ｒ ｔ ｂａ ｅ ｎ ｉ ｅ ｎ ｌｍ ｄ ｌｃ ｎｔ ｏ
Ｌ Ｎ ｉｓ Ｌ Ｎ ｉＷＩ ，ＺＨＡＮＧ Ｉ Ｋａ ．ｉ， Ｉ Ｋａ ． １ Ｌｕ （ ． ｅａｔｅｔｆＭｅｈ ｎｃｌ ｎ ｌ ｔｃｌ ｎ ｉｅｒ ｇ ｏｇｉ ｏａｉ ａ ｎ ｅ ｎ ａ ｏ ｅｅ ｏｇｉ ｎ ｕ ２４ ０ ，Ｃ ｉａ １ Ｄｐ ｒ ｎ ｃａ ｉ ｄＥｅ ｒ ａ Ｅ ｇｎｅ ｎ，Ｔ ｎｌ ｇ Ｖｃｔｎ ｌ ｄ Ｔｃ ｉ ｌＣｌｇ，Ｔｎｌ ｇＡ ｈｉ ４０ ０ ｈｎ ； ｍ ｏ ａａ ｃｉ ｉ ｎ ｏ ａ ｈｃ ｌ ｎ ２ Ｔ ．ｏ Ｎ ｒ Ｔ ｎｇ ａ ｆｒａｉ ｎ ｅ ｎ ｌ ｙＣｍ ａ ｙ ｉ ｉｄ ｏｇ ｎ ｎ ｕ ２ ０ ０ ｈ ａ ｏ ｒ ｏ ｇ ｕ ｎＩ ｏ ｔｎａ Ｔｃ ｏ ｇ ｏ ｐ ｎ ｍ ｔ ，Ｔｎ ｌ ｇ ｈ ｉ ４ ０ ，Ｃ ｉ ） 。 ｎ ｍ ｏ ｄ ｈ ｏ Ｌ ｅ ｉ Ａ ｎ

参数 采 川 交错 设 置 ． ： 即
ｐ ＜Ｐ ＜ 一 … ＜ 一 ． ｌ Ｐ ・ Ｐ ｍ ｘＪ ｉ １ ａｄ ｍ ｎ ａ ｒ ｎ ≥ｍ ｘ ＞ ｉ屺≥ …ｌ ｘ ＞ ｄ ｍ ＞ ａ ｌ ｎ ｎ ｌ ａ ≥…Ｙ￣ ｒ ｎ ． ＩＸ ＞ ｉ Ｉ ｔ ａ
： 条件（ １ ） 条件 （ ２ ）
摘 要 ： 向 Ｑｏ 面 Ｓ的 ＤｉＳｅｖ模 型 ， 改进 ＲＩ Ｃ 算 法的 基 础 上 ， 出 了一 种 新的 主 动 队 列 管 理 算 法 ——Ｆ ｋＩ）．通 过 理 沦分析 和 ｌ ｆ ｒ 在 Ｏ— 提 ｐ Ｌ 仿 真 实验验 证 ， 明该 算 法是 一种 适 合 于 ＤｉＳ ｒ 证 ｆ ｅｖ模 型 的 主动 队 列 管理 算法 。
１ｔ＿ ｌｌｌ ｌ ｕ ｆ ｄ ・Ｈ ｘ ］Ｘ ｌ ｌｌ＞ｎ ｘ —ｎｎ ・ ｌ 一Ｉ １ ＞ ｎｘ 一ｌｉ ｌ ｈ ｉｌ ａ ｉ ＞ ・ ａ ｌ —Ｉ ｈ １ １ …ｌ ｎｌ １ １ ａ ｌ
ｒｔ ｎｌｉ ｅｅ ｅ Ｔｈ ｏｕ ｈ ｏｒ ｔ ａ ｎａｙｓ ｎｄ ｅ ｐｅｉ ｅ ｔｌ ｅ ｆ ａｉ ｉｈ ｓｐｒ ｓｎｔｄ ｒ ｇｈ ｔ ｅ ｅｉ ｌａ ｌ ｉ ａ ｘ ｒｍ ｎ ａ ｃ ｓ ｖ ｒｉ ｔ ｉ ｃ ｏｎ，ｔ ｌｏ ｉｈ ｓａ ｃｉ ｅ ｑｕ ｕｅ ｎｌｎａ ｅ ｅ ｔａｇ ｉｈｍ ｈｒ ｈｅ ａｇ ｒｔｍ ｉ ｎ ａ ｔｖ ｅ ａ ｇ ｍ ｎ ｌｏｒｔ ｔ
Ｖｏ ．，Ｎｏ １ ，Ｍａ ０１ ， Ｐ ３ ８ — ０ ３ １ ７ ．３ ｙ２ Ｐ ０ １ ３ ８ １
一
种 Ｄｆ ｅｖ模 型 的主 动 队列 管理 算法 Ｆ ＲＯ ｉＳ ｒ Ｐ Ｉ
孙 丽 刘 良姜 群 俊 ， 家 ，利
（ 国矿 业 大 学 计 算 机科 学 与技 术 学 院 ， 苏 徐 州 ２ １ １ ） 中 江 ２ １６

Ｒ Ｄ 与 Ｅ Ｎ 的 区 别 在 于 ．Ｅ 算 法 是 根 据 概 率 丢 弃 到 达 的 分 Ｅ Ｃ ＲＤ 组 ． Ｅ Ｎ算 法是 根 据 概 率 在 到 达 的 分 组 中 设 置 Ｅ Ｎ位 ， 过 而 Ｃ Ｃ 通 图 １仿 真 网络 拓 扑 结 构 ： 接 收方 返 回 的 Ａ Ｋ 消 息 反 馈 给 发 送 方 ． 指 示 拥 塞 ， 发送 方 Ｃ 以 当 图 １中 各 参 数 意 义 如 下 ： 为 发 送 和接 收 节 点 的个 数 ． 其 接 收 到 带 有 Ｅ Ｎ 标 记 的 Ａ Ｋ分 组 时 ．就 像 检 测 到 丢 分组 一 样 Ｎ 在 Ｃ Ｃ 应 用 层 上 运 行 ｍ 服 务 。Ｂ 为 瓶 颈 链 路 带 宽 ，Ｐ 链 路 传 输 延 执 行 Ｔ Ｐ拥 塞 避 免 机 制 来 响应 拥 塞指 示 丢 分组 或 标 记 的 概率 Ｔ为 Ｃ 迟 。其 中非 瓶 颈 链 路 带 宽 均 为 １Ｍｂ ｓ传 输 延 迟 为 ２ ｓ采 用 尾 由动 态 变 化 的 平 均 队列 长 度 所 决 定 ．算 法 的 关 键是 如 何计 算 队 ０ ｐ， ｍ． 丢 弃 策 略 。 分 组 大 小 为 ５ ０ ｙｅ ．瓶 颈 链 路 的 队列 长 度 为 １０ 列 平 均 长 度 和 分组 的标 记， 弃 概 率 。 ０ Ｂ ｔｓ ０ 丢 Ｐ ｃｋ ｔ ａ ｅｓ。 具体做法是 ． 当分 组 到达 时 ． 法 采 用 指数 加权 平 均 算 法 计 算 ２１尾 丢 弃算 法（ ｒｐ ａ １ ． Ｄ ｉ ｏ Ｔ ｌ 算 系统 的平 均 队列 长 度 ａｇ ｖ ，另外 还 设 定 了两 个 控 制 阈 值 ｒｉｔ ａ ｎｈ 算法原理 ： 和 ｍ ｘｈ ａｔ。算 法 以这 三个 参 数 作 为 判 断拥 塞是 否将 要 发 生 的 依 Ｄ ｐＴ ｉ的基 本 思 想 是 当 队 列 长 度 没 有 达 到 缓 存 容 量 时 ， 据 ． 依此 计 算 分 组 的 标 记， 弃 概 率 。 ｏ ｒ ａ ｌ 并 丢 不 丢 弃 任 何 到 达 的 分 组 （ 弃 概 率 为 ０ ； 列 长 度 达 到缓 存 容 丢 ）队 平均 队列 长 度 的 计 算公 式 为 ： ＝ ．倒 Ｊ 倒ｇ — Ｉ ） （ ｇ 量 时 ， 不加 选 择 地 丢 弃 所 有 到 达 的 分 组 （ 弃 概 率 为 １ 。这 是 则 丢 ） 其 中 ｑ为 当 前 队 列 长 度 ； ｑ为 当前 队 列 长 度 加 权 系数 ， ｍ 它 种开关控制策略。其算法如下 ： 介 于 ０到 １之 问 ；ｖ 为 平 均 队列 长度 。 ａｇ 若 当前 平 均 队 列 长 度 小 于 ｒｉ ， 到 达 的 分 组 以概 率 ０被 ａｎ 则 ｉ（ｉ ） ｆｑ≤Ｂ ｐ￣Ｏ； － 标 记／ 弃 ； 当前 平 均 队 列 长度 介 于 ｌｉ 和 埘 之 问 ， 到 达 丢 若 ｎ ａ 则 ｅｓ ｌｅ 的 分 组 以概 率 Ｐ 被 标 记 ， 弃 ；若 当 前 的 平 均 队 列 长 度 大 于 ． 丢 ｐ＝１； ｉ ｍ ｘｈ ， 到 达 的分 组 以概 率 １被 标 记， ａｔ 则 丢弃 。 概 率 Ｐ 的 计 算 公 ． 其 中 ｐ 是报 文标 记 ， 失 的 概 率 ， 队 列 长 度 。 ｉ 丢 ｑ是 式如下 ： 仿 真 实 验 １ 使 用 Ｄ ｐＴ ｉ尾 丢弃 作 为 瓶颈 链 路 的 队 列 管 ： ｏ ｒ ａｌ ｐ＝ 】 （ Ｖ＿ Ｉ ｄ（ Ｉ ｍａ ｂｍａ （ ｇ Ⅱ ｎ ／Ⅱ ｎ一 ｘ ａ ｉ ｉ 理 算 法 ， 真 参 数 Ｎ ３ Ｂ ＝ ０ ｋ ｐ ，ｒ２ ｍｓ仿 真 时 间 ５ ｓ 仿 仿 ＝ ， ｗ ７０ ｂｓＴ＝ ０ ， ０。 ｐ＝ ｔ １ｃ ｕ ｔｐ ．Ｐ （ －ｏ ｎｘ ￣ ／ ） 真 结 果 如 图 ２ 图 ３ 、 。 其 中 ｍａ． 预 先 设 置 的标 记 或 丢 弃 概 率 ． ｕｔ 上 次 标 ｘ是 ｃ ｎ是 ｏ 记， 弃 分 组后 收 到 的分 组 数 目 丢 仿真实验 ２ ：使 用 Ｒ Ｄ 作 为 瓶 颈 链 路 的 队列 管理 算 法 ， Ｅ 仿 真参数尽量与仿真实验 １ 同 ． 相 只是 根据 Ｒ Ｄ算 法 的 需 要 增 设 Ｅ ｍ ｒ０１ｍ ｎ＝ ０ ｍ ｘ＝ ０ ｏ － ． ２ 目的 是 通 过 两 次 实 验 的 ｘ ａ － ．， ｉ￣ １ ， ａ， ３ ， － ０ 。 ￣０ ０ 对 比 ． 究 在 相 同 的 网 络 负载 条 件 下 ， 用 不 同 的 队 列 管理 算法 研 采

维普资讯
第
＂ 期 ２ ０ ７月 ０ 年 ７
计 算 机 技 术 与 发 展
ＣＯＭ Ｕ１ ＥＲ ＴＥ（ Ｎ（ＬＯＧＹ Ｈ ） ＡＮＤ ＤＥＶＥＬＯＰＭ ＥＮＴ
Ｖｏ． ７ Ｎｏ ７ １１ ．
Ｊｄ ２ ０ ｃ． ０ ７
状态 无关 主动 队列管理算 法博弈 的 Ｎ ｓ ａｈ均衡
Ａｂ ｔａ ｔＡｎｏ ｌ ｉｕ ｃｉｅｑ ｅ ｅｍａ ｇ ｍｅ ｔｓｈ ｍｅｉ ｎｅｗｈｃ ｏ ｓｒ ｔｄｆｅｅ ｔａｅｂ ｔ ｅ ａ ｋ ｔ ｌｎ ｉｇｔ ｉ ｅｅ ｔｆ ｗｓ ｓｒｃ ： ｂｉ ｏ ｓａ ｔ ｕ ｕ ｎａ ｅ ｎ ｃ ｅ ｏ ｉｈｄ ｅ ｉ ｉ ｒｎ ｉｔ ｅｗｅｎ ｐ ｃ ｅｓｂ ｏ ｇｎ ｏｄｆ ｒｎ ｌ ｖ ｖ ｓ ｏ ｆ ｅ ｆ ｏ ，
送速率 ） 可信性的 同时 ， 保持 了核心 网络 的简单性 ＿ ， １ Ｊ
所 以 Ｔ Ｐ协议一直是 Ｉｔ ｔ Ｃ ｎｅ 稳定性 的保 障。但视频 ｍｅ
算法 （ Ｑ 来避免和 管理拥 塞。几 年来 ， Ａ Ａ Ｍ） 对 ＱＭ 的 研究与性 能评价都是从 工程技术 的角度 出发 ， 如资源 利用率 、 用户公平性等 ， 这些方法着重去改进 和提高技
ｅｆ ｉ ｔ Ｍ ｓｈ ｍｅｔａ ｉ ｏ ｅａＮ ｓ ｑ ｕ ｉｒ ｓａ ｏｐ ｅｅ ｔｄ ｆ ｃ ｎ ＡＱ ｃ ｅ ｉｅ ｈ ｔｍｐ ｓ ａ ｈｅ ｉｂ ａｉ ｌ ｒｓｎ ｅ ． ｌｉ ｓ Ｋ ｙｗ ｒ ｓ ｃ ｎ ｅｔ ｎ ｃｎ ｒ ｌ ｅ ｏｄ ：ｏ ｓ ｉ ｔｏ： ｇ ｏ ｏ ＡＱＭ ； ａ ｈｅ ｕｌ ｒ ； Ｄ； ＨＯ Ｎ ｑ ｑ ｉｂ ａＲＥ Ｃ Ｋｅ ｉｉ
ＦＥ ＮＧ ｉｎ， Ｊａ ＹＡＮＧ — ｎ Ｌｕｍｉｇ
（ｎｏ ｔｎＳｉ ｃ ｎ ｅｈ ｏ ｇ ａ ｅ ｆ ｅ ｔ ｌ ｏ ｔ ｉ ｒ ｔ， ｈｎ ｓａ４ ０ ８ ， ｈｎ ） Ｉｆ ｍａｏ ｃ ｎ ｅ ｄＴ ｃｎｌ ｙ ｄｍｙｏ ｎｒ ｕｈＵｎｖ ｓ ｙＣ ａｇｈ １０ ３ Ｃ ｉａ ｒ ｉ ｅ ａ ｏ Ａｃ Ｃ ａＳ ｅｉ

Ａｂ ｔａ ｔ Ｔｏ ｏ ｅ ｃ ｍｅｔ ｅｗｅ ｋ ｅ ｓｏ ｘｓｉ ｇＡ ＱＭ ｌｏ ｉｈ ａ ｅ ｎ ｔ ｅｃ ｎ ｒ ｌ ｈ ｏ ｙ ｓቤተ መጻሕፍቲ ባይዱ ｃ ｖ ｒ ｏ ｈ ａ ｎ ｓ ｆｅ ｉｔ ｎ ａｇ ｒｔ ｍｓｂ ｓ ｄｏ ｈ ｏ ｔｏ ｅ ｒ ，ａ ｔ
ｎ ｖ ｌＡＱＭ ｌｏ ｉ ｍ ａｌｄ Ｉ ＴＥ— ｓｄ ｓｇ ｅ ｙｎ ｔｉｎ ｒｎ ｈ ｉ ｅａ ｅ ｍ ｎｔ ｅＴＣＰ ｏ ｅ ａｇ ｒｔ ｃ ｌ Ｓ ｈ ｅ ＰＩｉ ｅ ｉｎ ｄｂ ｏ ｇ ｏ ｉｇ ｔ ｅｔｍｅｄ ｌｙｔｒ ｉ ｈ ／
关键词 拥 塞 控 制 ； 动 队列 管 主
ＴＰ ９ ３３
（ ＡＱＭ） 时 间 加 权 平 方 误 差 积 分 （Ｓ Ｅ ； 时 滞 网络 ； 干 扰 ； ＩＴ ） 大 抗
中图法分类号
Ｄ Ｉ ：１ ． ７ ４ Ｓ ． ． ０ ６ ２ １ ． ０ ５ Ｏ 号 ０ ３ ２ ／ Ｐ Ｊ １ １． ０ ２ ０ ９ １
ＡＱＭ ｏ ｅ ，ｉ ｔｏ ｕ ｉｇ ｓ ｏ ｔｌ ｅ ｍ ｄ ｌ ｎ ｒ ｄ ｃｎ ｈ ｒ ｉ ｄ ＴＣＰ ｆｏ ｎ ＤＰ ｆ ｗｓａ ｈ ｉｔ ｒ ａ ｃ ｎ ｓｎ ｈ ｖ ｌｗｓａ ｄＵ ｌ ｓｔ ｅｄ ｓｕ ｂ ｎ ｅａ ｄ ｕ ｉｇ ｔ ｅ ｏ
Ａ Ｎｏ ｅ Ａ ｖ ｌ ＱＭ ｇ ｒｔ ｍ ａ ｅ ｎ ｔ ｅＰ ｏ ｔｏｌｒｗ ｔ ｉ ｉ ｍ Ｓ Ｅ Ａｌｏ ｉ ｈ Ｂ ｓ ｄ ｏ ｈ ＩＣ ｎ ｒ ｌ ｉ Ｍ ｎ ｍｕ Ｉ Ｔ ｅ ｈ
Ｗ ＡＮＧ ｏ” Ｈａ ＬＩＸｉｏ Ｍ ｉ ｇ ａ— ｎ ＹＡＮ ｅ 孙 Ｗ ｉ Ｈ ＵＡＮＧ ｉ ｇ Ｈｅ Ｍ ｎ—
备 响 应速 度快 、 干扰 能 力 强 、 用 于 大 时滞 网络 环 境 且 鲁 棒 性 好 等 特 点 ． 于 ｌｔｒｅ 网络 流 量 由 Ｔ Ｐ长 流 、 Ｃ 抗 能 鉴 ｎｅｎ ｔ Ｃ Ｔ Ｐ 短 流 和 ＵＤ Ｐ流 构 成 ， 是 大 时滞 网 络 ， 且 因此 ＩＴＥ Ｐ 算 法 能 更 好 地 适 应 Ｉｔｒｅ 网络 环 境 下 的 主 动 队列 管理 ． Ｓ —Ｉ ｎｅｎｔ

RED（Random Early Detection）算法是一种主动队列管理（AQM）算法，它主要用于网络中的路由器和交换机中，以避免拥塞的发生。

当网络中的流量接近设备处理能力的极限时，拥塞控制就变得至关重要。

RED算法的目的是在网络队列变得过满之前，提前通过丢弃一部分网络包来通知发送端减少发送速率。

RED算法的工作原理如下：1. 平均队列长度计算：RED算法维护一个对队列长度的加权移动平均值。

对于每个到达的数据包，RED会更新这个平均队列长度。

这个长度并不是实时队列长度，而是过去一段时间内的平均值，它可以平滑短期的流量突增。

2. 低阈值和高阈值：在RED算法中，设置两个阈值，分别是最小阈值（minth）和最大阈值（maxth）。

当平均队列长度低于最小阈值时，所有到达的数据包都会被接受。

当平均队列长度超过最大阈值时，所有到达的数据包都有可能被丢弃或标记（例如，TCP/IP网络中的ECN标记）。

3. 随机早期检测：当平均队列长度位于最小阈值和最大阈值之间时，RED会以一定的概率丢弃到达的数据包。

这个概率随着平均队列长度的增加而增加，意味着队列越拥挤，数据包被丢弃的几率就越高。

这个概率是动态计算的，用于平滑的调控传输速率，而不是突然阻断。

4. 随机性：之所以称为“随机”早期检测，是因为当队列长度介于两个阈值之间时，数据包被丢弃的决策是基于一定的随机性的。

这样做的目的是为了防止全局同步现象，即多个流同时减少他们的发送速率，然后又同时增加速率，造成网络效率的波动。

RED算法通过这种方法提前向发送方发送拥塞即将发生的信号，目的是让发送方降低数据发送速率，减少数据包丢失，从而使网络运行更加平滑，提高整体的吞吐量。

在TCP网络中，当发送方检测到数据包丢失时，它会减少其拥塞窗口的大小，减慢数据发送速率，从而减轻网络拥塞。

ｎ ｏ ｌｔ ｅ ｖ ｔ ｎ ａ ｚ ｎ ｓ ｏ ｄ ｓｇ ｅ Ｃｏ ｉ ｃ ｍｐ ｅ ｅｄ ｒ ａ ｏ ｄ ｆ ｚ ｉ ｅ ｓｉ ａｓ ｅ ｉ ｎ 、 ｍｐ ｄ ｗｉ ｅ ｅ ａ Ｉ ，ｈ ｓ ａｇ ｒ ｈ Ｃ ｏ ｎ ｙ ｅｉ ｎ ｔ ｇ ｉ ｉ ｎ ｕ ｓｌ ｄ ￣ｅ ｔ ｇ ｎ ｒ Ｐ Ｄ ｔ ｉ ｌ ｏ ｔ ｍ ａ ｎ ｔ ｌ ｌ ｈ ｌ ｉ ｎ ｏ ｍｉ ａｅ ｈ ｈ ｉ
Ｋｅ ｏ ｄ ：ＡＱ ；ｎｔ ｏｋｃｎ ｅｔ ｎ ｎｃｍｐｅ ｅ ｖｔ ｎ ｕ ｚ —Ｉ ｃ ｎｒｌ ｒ ｙｗ ｒｓ Ｍ ｅ ｒ ｇ ｓ ｏ ；ｉ ｏ ｌｔ ｄｒ ａ ｏ ；Ｆ ｚｙＰＤ ｔ ｌ ｗ ｏ ｉ ｅ ｉ ｉ ｏ ｏｅ
Ｌ Ｕ ａ ｇ 。 Ｚ Ｉ Ｘｉ ｎ ＨＡＮＧ ｎ — ｕ ， Ｍ ＡＩ ｉ ｉ ｇ ， Ｔ Ｘｉ ｇ ｈ ｉ — ｎ Ｊｐ ＯＮＧ ｏ ｇ ｍ ａ Ｙ ｎ — 拍
（ 、 ｐｒ ｎ ｆ ｔｍａ ｏ ，ｉｎｉ ｏｙｅｈ ｉ Ｕ ｉｅｓｙ Ｔａｊ ０ １０ Ｃ ｉａ ２ Ｔａｊ ｉｖｒｉ ｆ ｅｈ ｏｏ ｙ １Ｄｅ ａ ｍｅｔ Ａｕｏ ｔ ｎ Ｔａｊ Ｐ ｌ ｃ ｎｃ ｎｖ ｒ ｔ， ｉ ｉ ３０ ６ ， ｈｎ ；、 ｉｎｉ Ｕｎ ｅ ｔ ｏ Ｔ ｎ ｌｇ ｔ ｏ ｉ ｎ ｔ ｉ ｎｎ ｎ ｓ ｙ ｃ ａｄＥ ｕａ ｏ ，． ｅ ａｔ ｎ ｆ ｏ ｕｅ， ． ｐ ｒ ｎ ｏ ｌ ｔ ｎｃ ｎｉｅｒ ｇ Ｔａｊ ０２ ２ Ｃ ｉａ ｎ ｄ ｃｔ ｎ ａ Ｄ ｐｒ ｉ ｍｅ ｔ ｍｐ ｔ ｂ Ｄｅａｔ ｔ ｆ ｅ ｒｉ ｇ ｅｉ ， ｉ ｉ ３ ０ ２ ， ｈｎ ） ｏＣ ｒ ｍｅ Ｅ ｃ ｏ Ｅ ｎ ｎ ｎｎ
要 的作 用。文章介绍 了 Ａ Ｍ 算法的研 究现状 ， Ｑ 分析 了 Ａ Ｍ 中的 ＰＤ 算法 ， Ｑ Ｉ 并用不完全微分和模糊的方法改进 了

几种典型主动队列管理(AQM)算法黄燕琴【摘要】网络拥塞控制按照不同的标准可以分为不同的控制机制和相应的拥塞控制策略.主动队列管理(AQM)算法是一种运行于网络中心节点的积极的闭环控制的链路算法.RED(随机早期丢弃)算法是IEIF推荐的主动队列管理算法的唯一侯选算法,然而算法在响应速度、稳定性等方面仍有缺陷.阐述了当前拥塞控制算法和几种典型的主动队列管理AQM算法,分析总结原始的RED算法的不足.【期刊名称】《曲阜师范大学学报（自然科学版）》【年(卷),期】2019(045)002【总页数】5页(P104-108)【关键词】拥塞控制;队列算法;主动队列管理【作者】黄燕琴【作者单位】漳州职业技术学院电子工程学院,363000,福建省漳州市【正文语种】中文【中图分类】TM3931 RED算法(Original RED算法)RED拥塞控制机制的基本思想是通过监控路由器缓冲区队列的平均长度来探测拥塞，一旦发现拥塞逼近，就随机地选择连接来通知拥塞，使他们在队列溢出导致丢包之前减小拥塞窗口，降低发送数据速度，从而缓解网络拥塞.由于RED算法是基于FIFO队列调度策略的，并且只是丢弃正进入路由器的分组，因此其实施起来也较为简单.RED算法主要试图达到以下目标[1]:(1)最小包丢失率和排队延迟.(2)避免全局同步现象.(3)避免对突发业务的偏见:网络中含有大量的突发数据，而“丢尾”算法对突发业务有很大的偏见.在采用“丢尾”算法的路由器中，如果某个流的突发性越高，则当该流的包进入队列时越容易造成队列溢出，从而导致连续地丢弃大量的该流的包.(4)即使在缺乏传输层协议有效配合的情况下也能控制平均队列长度，从而避免拥塞.为了达成以上目标，RED算法按照指数权值移动均值 EWMA(Exponential Weighted Moving Average)的方法来计算平均队列长度，并且随机地选择正进入路由器的包进行丢弃.这种方法能被有效地实施而无需在路由器中维持每个流(Per-Ffow)的状态信息.RED算法主要分为2个部分.首先是计算平均队列长度，以此作为对拥塞程度的估计.另一个就是计算丢弃包的概率.a 计算平均队列长度由于Internet数据的突发性，如果一个队列在很多时候是空的，然后迅速被充满，又很快被取空，这时就不能判定路由器发生拥塞而向源端发送拥塞指示.因此，RED算法在计算平均队长Qavg时采用了类似低通滤波器(Low Pass Filter)带权值的方法Qavg(new)=(1-Wq)*Qavg(old)+Wq*Queue,(1)其中，Wq为权值，Queue为队列采样数据.由于Internet数据的突发本质或者短期拥塞导致的实际队列长度暂时的增长将不会使平均队长有明显变化，从而“过滤”掉短期瞬间的队长变化，尽量反映长期的拥塞变化.在计算平均队长的公式中，权值Wq相当于低通滤波器的时间常数，它决定了路由器对输入流量变化的反应程度.因此对Wq的选择非常重要，如果Wq过大，那么RED算法就不能有效地过虑短暂的拥塞;如果Wq太小，那么Qavg就会对实际队列长度的变化反应过慢，不能合理地反映拥塞状况，在这种情况下，路由器就不能有效检测到早期的拥塞.Wq的值应根据不同情况预先设置，一般来说，它是由路由器允许发生的突发业务的大小和持续的时间所决定的.b 计算丢包概率计算平均队长的目的就是为了反映拥塞状况，根据拥塞的程度来计算丢弃包的概率，从而有效地控制平均队列长度.RED算法有2个和队列长度相关的闭值:Qmin和Qmax.当有包到达路由器时，RED算法计算出平均队长Qavg.(2)计算丢包概率Pa的方法如式(2)、公式(3),(3)算法的第1部分决定了所允许的突发长度，而第二部分决定了在给定的当前拥塞级别时分组的丢弃频度.如果Qavg<Qmin，则进入分组就要排队，但如果Qavg>Qmax则进入分组自动地被丢弃.临界区就是当Qavg的值处于2个门限之间时.在此区域内，RED给进入分组指派了一个丢弃概率，取决于2个因素：若Qavg越接近于Qmax，则丢弃的概率就越高.图1 RED算法只要Qavg处在临界的范围，则保留一个count说明有多少个连接的分组避免了被丢弃；count的值越大，分组丢弃的概率也就越高.图1中的计算步骤较难看出所发生的细节，因此还是要简单地讨论一下.首先，要计算一个临时的概率值Pb.这个值在Qavg<Qmin时从0线性地增长到某个最大值Pmax(在Qavg<Qmax时的取值).如果我们定义一个量F就可以更容易地看出(4)它是小于Qavg的临界区的一部分.这样有Pb=F×Pmax, 0≤F≤1.(5)概率的现象有时会产生聚焦.例如，我们多次抛掷一个硬币，那么我们不会期望能够看到均匀出现的正面和反面交替出现的序列.相反，我们会看到全部是正面或全部是反面的聚焦，或较多的正面的聚焦，等等，而且其长期的平均值是50-50.对于RED算法，丢弃可能会相对地均匀分布着，因此对一个突发的信源不会受到惩罚.所以，丢弃中不直接使用概率Pb，而是用它来计算第2个概率Pa,它是用来确定丢弃的.将F带入图2中的算法，就可以得出以下的定义(6)下页图2给出了对这个函数的一些理解.对于一个给定的count值，当Qavg的值趋向于Qmax时，Pa均匀地增长.Pa从Qavg=Qmin时的Pa=0逐渐增加到在Qacg=Qmax时的最大值.如果保持F为恒定，并且画出Pa作为count的函数，那么这个函数真正的性质就更加清楚了.Pa 的值开始缓慢增加，然后急剧增长，直到它在count=(1/F×Pmax-1时达到Pa=1.这样，对count的大部分的数值，丢弃的概率极低，而当count接近其最大值时变得非常接近于1.这种效果是迫使丢弃间隔或多或少地更加均匀些.可以证明，如果我们令Pa为丢弃概率，而X为从一个分组被丢弃到下一个分组被丢弃之间的分组到达数，则X就是一个均匀分布的随机变量，从{1,2,…,1/Pb}中取值[2]：图2 RED概率的参数图3 RED和尾丢弃规一化吞吐量比较(4)(5)作为一个例子，文献[1]中推荐Pmax的值为0.02.当平均队列长度在minth和maxth之间时(F=0.5)，粗略地讲，大约有即的到达的分组被丢弃.图3给出了一个模拟的结果[1]，并将RED和尾丢弃策略相比.可以明显看出后者在队列已满时就简单地丢弃一个刚到达的分组.在高度拥塞时，RED可提供较高的吞吐量，因而比尾丢弃要好.RED不仅可以位于区域CDHG，也可以位于ABFE和BCGF，这取决于它是采用TD,FD还是RD.但Floyd认为，既然RED可以将平均排队时延控制在较短的范围内，FD并不能给RED带来明显的好处，RED采用TD已足够[3].RED为了限制了平均时延的大小，在平均队长超过了最大阈值后就丢包，而不是采用诸如设置CE 位之类的标记包的方法，从而有效地控制了平均队长.因为发送速度更快的流，其供随机标记的包也更多,在发生拥塞时，RED标记某个流的数据包的概率基本上和该流在路由器中的带宽成比例.从而消除了对突发流的偏见.由于RED算法存在着诸多问题，导致了改进算法的产生.这些算法主要有:Gentle RED,ARED,New ARED 等.2 Gentle RED算法1999年，Floyd又提出改进的RED算法Gentle RED，Gentle RED算法继承了RED算法的主要思想，当平均队列小于最大门阀值时，其丢弃概率的计算与RED 算法完全一致，而当平均队列Qavg大于2Qmax时，则不象RED算法一样丢弃概率由Pmax到1的跳跃，而是以另一种线性关系计算Pb的概率，然后以Pa概率来丢弃新到达路由器的分组，原理图所示.其算法函数表示为公式(7)、公式(8).(7)(8)注意到Pa不仅与Qavg有关，还与从上一次丢包开始到现在进入队列的包的数量Count有关.随着Count的增加，下一个包被丢弃的可能性也在缓慢增加.这主要是为了在到来的包之间均匀间隔地丢包，避免连续丢包，从而避免对突发流的偏见和产生全局同步现象.3 ARED算法在拥塞严重的网络中，路由器必须将足够多的拥塞信息通知到源端，以充分降低负载，避免由于队列溢出而丢包.另一方面，路由器也要防止拥塞信息过多地传给源端，从而造成瓶颈链路利用率的下降.因此，进行拥塞通知时应充分考虑到瓶颈链路上流的数量.而RED算法并没有考虑到这一点.为此ARED(A self-configuring RED)提出了一种自动配置机制，根据流量的变化来配置适当的参数.RED算法中，拥塞指示的发送速度是由参数Pmax来体现的.如果Pmax太大，那么丢包主要就是由于早期拥塞检测中产生的丢包造成的;如果Pmax太小，丢包主要就是由于队列溢出造成的.RED算法的一个弱点是平均队长对拥塞程度和参数设置很敏感.如果拥塞不太严重或者Pmax很大，则平均队长接近Qmin;如果拥塞很严重或者Pmax很小，则平均队长接近或大于Qmax.结果造成平均排队时延对流量负荷和参数设置很敏感.ARED算法的基本思想就是通过检查平均队长的变化来感知RED算法是应更激进(Aggressive)还是更保守(Conservative).如果平均队长是在Qmin附近振荡，那么拥塞控制就太激进了;如果在Qmax附近振荡，那么拥塞控制就太保守了.根据所观察到的平均队长，ARED算法动态地Pmax调整的值.其算法如下:Every Qavg Update:If (Qmin<Qavg && Qavg<Qmax)Status=between;Else if(Qavg<Qmin && Status!=below)Status=below：Pmax=Pmax/αElse if(Qavg>Qmax && Status!=above)Status=above：Pmax=Pmax*β.各参数变量含义,Status:平均队长状态, Between:Qmin和Qmax之间, Below:小于Qmin, Above:大于Qmax, α: Pmax减少量, β: Pmax增加量.ARED算法的思想很简单，就是根据平均队长是否在Qmin和Qmax之间，对Pmax采用乘法增加和乘法减少(Multiplicative Increase Multiplicative Decrease，MIMD)从而尽量保持平均队长在Qmin和Qmax之间.ARED算法是对RED算法改动很小的一种算法，它保留了RED算法的基本结构，只需调节参数Pmax从而保持平均队长在Qmin和Qmax之间，消除了RED算法的队列延时问题和参数敏感性问题.4 改进的New ARED算法为了提高ARED算法的鲁棒性， Sally Floyd等人提出了一种新的ARED算法New ARED(又称为Adaptive RED).其基本思想和ARED算法一样，都是采用自适应的Pmax以保持平均队长在Qmin,Qmax之间.不同之处在于New ARED算法保持平均队长在Qmin和Qmax的一半左右;Pmax不是每来一个包都改变，而是有一定时间间隔; Pmax不采用乘法增加和乘法减少，而是加法增加和乘法减少(Additive Increase MultiPlieative Decrease，AIMD); Pmax限制在[0.01，0.5].具体算法如下:Every interval seconds:If(Qavg>target && Pmax≤0.5)Increase Pmax:Pmax=Pmax+aElse if(Qavg<target && Pmax≥0.01)Decrease Pmax:Pmax=Pmax*β.各参变量含义,Interval:时间间隔，通常为0.05，target: Qavg的目标范围[Qmin+0.4*(Qmax-Qmin),Qmin+0.6*(Qmax-Qmin].New ARED算法的鲁棒性主要来自于Pmax不是很频繁的变化.但如果拥塞程度急剧变化，则Pmax需要过一段时间才能适应.为了保证ARED算法在这段时间里性能不会过度下降，因此将Pmax限制在[0.01,0.5]之间.这样，即使这段时间内平均对长不在目标范围内，平均延时和吞吐量也不会下降太多.RED标记包的概率依赖于拥塞水平，并且均匀地间隔丢包，避免了由于连续丢包导致地全局同步现象.但它依旧存在一些缺陷，譬如：参数敏感问题，RED算法的性能在一定程度上依赖于设计参数和网络状况[4,5].另外RED算法的公平性和稳定性也存在问题[6,7].因此，出现了一些RED改进和派生算法.丢包概率的计算很大程度上是依赖于平均队列长度的计算.参考文献：【相关文献】[1] Floyd S, Jacobson V. Random early detection gateways for congestion avoidance[J]. IEEE/ACM Trans on Network, 1993,1:397-413.[2] 夏高，刘斌. 用于高速网络入侵检测系统的并行TCP/IP协议栈[J]. 清华大学学报(自然科学版)，2011，7(8)：942-948.[3] 朱海婷，丁伟. 基于RED的差异型丢包队列管理算法[J]. 计算机学报，2014，567-577.[4] 任丰原，王福豹. RED算法的稳定性：基于非线性控制理论的分析[J]. 计算机学报，2002，25(12)：1302-1307．[5] 汤德佑，骆嘉伟，张大方. 参数自适应的随机早期检测算法[J]. 系统仿真学报，2003，15(12)：1741-1744．[6] Christiansen M, Jeffay K, Ott D, et al. Tuning RED for Web traffic[C]. Proceedings of ACM SIGCOMM 2000[A], Stockholm, Sweden, 2000. 139-150.[7] Firoiu V, Borden M. A study of active queue management for congestion control[C]. Proceedings of INFOCOM 2000[A], Tel Aviv, Israel, 2000. 1435-1444.。

向： 网络 拥 塞 控 制 。
式 （ ） ，（） Ｔ Ｐ连 接的 源端 的数 据发 送速 率 ， １中 ， 为 Ｃ ．
ｑ ｔ 为路 由器 的瞬时 队列 长度 ， 为 Ｔ Ｐ连 接 的 （） Ｎ（） Ｃ
１ ３期
叶成 荫 ： 基于 自适应 全局滑模控制 的主动队列管理算法
负载 因 子 ， ｔ 为往 返 时 延 ， 为传 播 时延 ， 。为 Ｒ（ ） ｃ 链 路 带宽 ， ｐ（） ０≤ ｔ ≤１为分 组 丢弃／ 标记 概 率 。
第 １卷 １
第 ｌ期 ３
２ １ 年 ５月 ０１
科
学
技
术
与
工
程
Ｖｏ．１ Ｎｏ ３ Ｍａ １ １ ．１ ｙ２０１ ｌ
ｌ７ — １１ （０ １ ２ －９ ６０ ６ １ ８ ５ ２ ２ ）３２ ８ —４
Ｓ ｉ ｃ ｅ ｈ ｏｏｙａ ｄＥ ￣ ｅ ｒ ｇ ｃｅ ｅＴ ｃ ｎ ｌｇ ｎ ｎ ｎ ｅｌ ｎ ｎ
的情 况下 ， 该算 法优 于传统 的 Ｐ 控 制和滑模 控制 。 Ｉ
随着 滑模 控制 理论 的发 展 ， 滑模 控 制理 论在 网 络拥 塞控 制 问题 上得 到 了广泛 的应用 。文献 ［ ， ５ ６］ 设 计 了一 个 基 于 滑模 控 制 器 的 Ａ Ｍ 算 法 ， 队列 Ｑ 使 长 度 在滑动模 态 阶段具 有 较 好 的稳 定 性 。但 是 ， 该
现直 接针对 动态 的 Ｔ Ｐ非 线性 网络 系统 ， 考 Ｃ 并 虑 了 Ｕ Ｐ流 干扰 的情况 ， Ｄ 设计 了基 于 自适应 全局滑
的问题 。基 于 路 由器 的 主 动 队列 管 理 Ａ Ｍ（ ｃ ｖ Ｑ ａｔ ｅ ｉ
ｑｅｅｍ ｎｇｍｅｔ 算 法 成 为 网 络 拥塞 控 制 的 研究 ｕｕ ａａｅ ｎ）

图 １ 实验拓扑结构
低通滤波器 （ ｗ—ａｓ ｉｅ）ｌ １ ｐ ｓ ｆｔ ］权 的方法计算见式（） 丢包概 ｏ ｌ ｒ ｊ ｌ １，
率计算见式（） ２。
Ｑａ ＝（一ｗ）Ｑａ １ 。 ＋Ｗ‘ 。 Ｑｔ
Ｐｍ ＝ ａ・ Ｐ
实验 １分别观察 １０ ０ 条、２０ ０ 条、５０ ０ 条、１ ０ 条 Ｆ Ｐ ０ ０ Ｔ
文 献标识码： Ａ
中 图分类号：Ｔ３１ Ｐ０． ６
种 自适应 主 动 队列 管理 算 法 ＡＢ ｕ ｌｅ
冯 伟 ，陈元琰 ，胡 愚 ，王 斌
（ 广西师范大学计算机科学与信息工程学院 ，广 西 桂林 ５ １０ ） ４０４
摘
要 ：Ｂｕ 是一种典 型的主 动管理 算法 ， ｌ ｅ 但其队列和延时波动较大 ， 尤其在连接数较大 或连接数突然发 生变化 时容易造成 队列溢 出或空
［ ｓｒ ｃ］ ｌｅｉａｔｐｃ ｌｃｉｅｍａ ａｅ ｎ ｇ ｒｈ ｂ ｔｔ ｕｆｒｆｏ ｕ ｕ ｚ ｓｉａｉｎ ｎ ｅａ ｓｉａｉｎ， ａｔ ｕａｌ ｔｅｎ ｍｂ ｒ Ａｂｔａｔ Ｂ ｕ ｉａ ａｔ ｎｇ ｍｅ ｔｌｏｉ ｍ， ｕ ｆ ｓ ｒｍ ｑ ｅｅｓ ｅｏｃｌｔ ｓ ｄｄ ｌｙｏｃｌ ｔ ｓｐ ｒｃｌｒ ｕ ｅ ｓ ｙ ｖ ａ ｔ ｉｓ ｅ ｉ ｌｏ ａ ｌｏ ｉ ｙｈ
３ Ｂｕ 算法 Ａ ｌ ｅ
针对 Ｂ ｕ ｌｅ算法的缺陷，本文提 出一种改进 的 Ｂ ｕ 算法 ， ｌｅ 记为 Ａ ｌｅ算法 。 Ｂｕ 它首先引入 Ｒ Ｄ 的早期检 测技术 ， 用平 Ｅ 使
２ ｌｅ Ｂｕ 算法
Ｂｕ ｌｅ算法使 用队列溢 出和链路空闲事件管理队列，它维
护 一个标记概 率 Ｊ Ｄ ，如果 队列溢 出连 续发生丢包 ，则增大
但是 ，Ｂｕ ｌ ｅ算法的队列 长度抖动较大 ，在参数设置问题

S-CHOKe：一种增强CHOKe公平性的主动式队列管理算法龚静;吴春明
【期刊名称】《电子学报》
【年(卷),期】2010(038)005
【摘要】CHOKe是一种无状态的近似公平的主动式队列管理算法,利用CHOKe 击中能近似识别并惩罚非响应流,CHOKe击中的有效性以及惩罚非响应流的力度,是提高算法公平性的关键因素.本文提出了一种增强CHOKe公平性的算法S-CHOKe,以采样击中取代CHOKe击中,提高CHOKe击中的有效性;利用队列击中,自适应确定丢包数,适度惩罚非响应流.仿真实验表明,S-CHOKe能适应流数量变化,是有效的、公平的.
【总页数】5页(P1100-1104)
【作者】龚静;吴春明
【作者单位】铜仁学院计算机科学系,贵州铜仁,554300;浙江大学人工智能研究所,浙江杭州,310027
【正文语种】中文
【中图分类】TP393
【相关文献】
1.主动队列管理算法：CHOKe性能分析 [J], 聂敏
2.SBlue:一种增强Blue稳定性的主动式队列管理算法 [J], 吴春明;姜明
3.改进的基于CHOKe击中历史的公平主动式队列管理 [J], 姜明;边浩;张少丽
4.一种基于gCHOKe公平性的主动队列管理算法 [J], 黄亮亮;周井泉;李琴
5.改进的CHOKe公平性主动队列管理算法 [J], 田硕;高仲合
因版权原因，仅展示原文概要，查看原文内容请购买。