无线有线网络中基于自适应丢包区分的TCP改进.doc

无线 有线网络中基于自适应丢包区分的 TCP 改进 叶进 1 2 王建新1 龚皓1 1 中南大学 信息科学与工程学院 湖南 长沙 410083 2 桂林电子科技大学 通信与信息学院 广西 桂林 541004 摘 要 分析指出 BQM 方法无法适应网络状态的变化 提出了 A BQM adaptive bias queue management 方法 其关键思想是根据网络事件动态调节模式匹配参数 使得算法在瓶颈拥塞和误码错误增加的情况下 依然能够 保持有效性 实验表明 A BQM 方法在不同的网络状态下都具有比较高的丢包区分准确率 可以自适应网络状 态的变化 相对 BQM 方法 A BQM 方法在网络吞吐量 公平性 传输延迟抖动等方面都有明显提高 关键词 异构网络 丢包识别 区分队列管理 链路错误通告 中图分类号 TP393文献标识码 A文章编号 1000 436X 2007 05 0015 07 Improved TCP based on adaptive loss differentiation algorithm over wired wireless networks YE Jin1 2 WANG Jian xin1 GONG Hao1 1 School of Information Science and Engineering Central South University Changsha 410083 China 2 School of Communication and Information Guilin University of Electronic Technology Guilin 541004 China Abstract BQM discriminator can not be fit to different network states was pointed and an adaptive BQM whose key idea is adjusting the important parameters for pattern matching according to network states so that the scheme can keep validity while congestion loss and or channel error increasing was proposed The experiment results show that the accuracy of A BQM discriminator is higher than BQM in different network states and A BQM can adjust itself adaptively according to network states A BQM gets better performance than BQM in some metrics such as network throughput fairness delay jitter and can be implemented and used easily in wired cum wireless networks Key words heterogeneous network loss differentiation algorithm bias queue management error link notice 1 引言 1 与有线网络不同的是 无线网络具有较高的比 特误码 复杂的信道衰落 突发的设备噪声 这 些特点将导致频繁产生丢包 可是传统 TCP 把所 有的丢包简单归结为网络拥塞而盲目采取控制策 略 从而极大降低了 TCP 的性能 因此在有线 无 线混合网络中 TCP 除了进行原有的拥塞控制外 收稿日期 2006 07 24 修回日期 2007 02 06 还必须增加错误控制的任务 近年来 以增强无 线链路上吞吐量 公平性等性能为目标的 TCP 改 进已成为研究的热点之一 1 3 本文提出的 A BQM adaptive bias queue management 方法是一种基于丢包区分的 TCP 改 进方法 其基本思想是根据某种特定的队列管理 模式 基金项目 国家自然科学基金资助项目 60673164 60403032 湖南省杰出青年基金资助项目 06JJ10009 新世纪优秀人 才支持计划基金资助项目 NCET 05 0683 Foundation Items The National Natrual Science Foundation of China 60673164 60403032 The Natural Science Foundation of Hunan Province 06JJ10009 The Program for New Century Excellent Talents in University NCET 05 0683 第 28 卷第 5 期通 信 学 报Vol 28 No 5 2007 年 5 月Journal on CommunicationsMay 2007 16 通 信 学 报第 28 卷 进行丢包区分 并通过反馈机制影响 TCP 的窗口 调控 该方法能够在瓶颈拥塞和无线错误增加的 时候 通过参数的自适应调节保证区分的准确率 实验表明该方法具有的较好的健壮性和伸缩性 能够有效提高有线 无线混合网络中的 TCP 性能 2 相关工作 针对错误控制的问题 传统TCP 在有线 无线混 合网络中的改进主要集中在区分无线丢包和拥塞丢 包 减少无线信道上的数据量这2 个方面 本文重 点讨论的是前者 它主要由2 个部分组成 1 如何 对丢包原因进行分析 2 如何根据不同的丢包类型 进行窗口调整 目前这个方面的改进主要有以下策 略 链路层策略 已经提出的 FEC ARQ 以及 ELN 4 等方法分别采用向前纠错 选择重发 错误 通告等措施 来提高无线链路的质量并向高层屏 蔽底层错误 这类方法需要节点具有探测并报告 网络状态的能力 还需要各层的共同参与 增加 了协议实现的复杂度 基站策略 对于目前应用得最多的最后一跳 是无线链路的混合网络 实施 TCP Split 5 TCP Snoop 6 等机制可以将基站作为 TCP 的代理 负责在 TCP 不受影响的情况下进行无线错误的重 传和相应的控制 这类方法需要基站大量的缓存 和处理能力 端到端策略 这是研究和应用得最多的一类 方法 文献 7 将丢包分为短期可恢复和不可恢复 两大类 对于前者统一采用 冻结 TCP 的方法 来避免不必要的拥塞控制调节 TCP DCR 8 TCP DOOR 9 等也采取了类似的方法 试图在 TCP 无知 的情况下恢复无线错误 它们的关键 在于如何选取 冻结 的时间 使得该方法既容 忍大多数无线错误又不影响拥塞控制 这在复杂 的异构网络中是一件比较困难的事情 因此端到端策略的重点是如何进行丢包识别 识别的方法有基于往返时延的 NCPLD 10 基于包 的到达间隔的 TCP Biaz 11 基于 ROTT 的 TCP Spike 12 基于 RTT 变化的 TCP Bayes 13 基于头 部校验和的 TCP HACK 14 等 除了直接进行丢包识别外 还有一些隐性的 丢包识别方法 其中最具代表性的是 TCP Westwood 15 它通过监测返回 ACK 速率来持续 测量有效带宽 并用当前有效带宽估算拥塞窗口 和慢启动门限值 该方法的瓶颈在于 ACK 到达的 时延和累积效应使得带宽估计的准确性受到影响 为 此 TCP New Jersey 16 TCP Prairie 17 都试图在TCP Westwood 的基础上进一步提高带宽估算的精度 但是由于丢包并没有直接发生在端节点上 这些使用端到端测度的丢包区分方法 其准确性 显得越来越难以保证 而在发生无线丢包的底层 和基站上部署策略代价较大 因此文献 18 提出根 据路由器上的特定队列管理来进行丢包识别 本 文通过实验分析表明该方法的准确性受到网络状 态变化的影响 并提出了一种自适应丢包区分的 方法 A BQM 3 A BQM 方法 3 1 BQM 方法及其存在的问题 BQM biased queue management 机制仿照区 分服务中的标记算法 在发送端将数据包等间隔 标记为 in 和 out 当路由器缓存溢出时 标记为 out 的包由于优先级较低会以概率 1 被丢弃 BQM 中在接收端对队列中丢包模式的分析使 用了一个函数 r x kkrxF1 r x kkrxF1 其中 x 是标记为 out 的丢包数目 r 是失序的数据包序列中丢包的 总数 k 是一个可调的匹配因子 与该段 TCP 序 列中标记的模式相关 如果该函数计算的结果大 于零 说明该丢包不是由拥塞引起的 那么在接 收端给丢包反馈的 ACK 加上 ELN 标记 从而使 得 TCP 源端不会错误地降低窗口大小 在有线 无 线网络中使用 BQM 方法能够在一定程度上消除无 线链路的影响 提高 TCP 的性能 要使BQM 方法区分准确率接近1 标记out 的 间隔必须小于1 PC PC 拥塞丢包率 一般来说 随着标记间隔的加大 正确判断拥塞丢包的概率将 下降 而正确判断无线丢包的概率将升高 因此存 在一个最优的标记间隔 文献 18 中通过实验得到了 在一个特定拓扑结构下的最优值 取标记间隔为8 BQM 方法采用固定的间隔标记 即out 包的数目和 分布是相同的 但是这种固定间隔的取值是否在任 何情况下都是最优的呢 为此 设计了实验来分析 BQM 的参数设置对丢包区分准确性产生的影响 实验拓扑结构如图 1 所示 TCP1 和 TCP2 共 享 R1 R2 间的瓶颈链路 UDP0 为占据 20 带宽 第 5 期叶进等 无线 有线网络中基于自适应丢包区分的 TCP 改进 17 的背景流 TCP1 是着重考察的最后一跳为无线链 路的 TCP 连接 图 1 中除无线链路 R2 R3 的传输 延时设为 10ms 外 其余链路的传输延时均为 2ms 图 1 网络拓扑 表 1 列出了不同参数下的实验结果 其中 Loss rate 为无线链路错误率 Biasmax 代表标记间 隔 KPattern 代表对路由器丢包特征进行模式匹配 的可调因子 算法中KPattern 一般取 0 6 Biasmax 因此以后的讨论中仅用Biasmax 代表 算法中的参数设置 表 1不同参数下的 BQM 准确率 Loss rate0 010 02 Biasmax8205082050 KPattern5123051230 P C C 0 970 570 460 840 810 40 P W W 0 730 820 850 610 740 95 总体正确率0 870 730 660 690 790 63 除了总体正确率之外 表1 中还使用了另外的 测量指标P t t 其中t t 是 2 个独立的事件 假设 T 是事件的集合 它表示对于t t T 某个丢包事 件 t 属于t 同时在算法中划分为t 的概率 具体可描 述为 P C C 丢包是拥塞导致的并且在算法中区 分为拥塞丢包的概率 P W W 丢包是无线错误导致的并且在算法 中区分为无线丢包的概率 总体正确率 区分正确的丢包数目与所有丢 包数目之比 表 1 中相同的参数在不同的无线链路错误率 下丢包准确率发生了较大的变化 当错误率为 0 01 时取标记间隔 8 可以获得最满意的准确率 而当错误率为 0 02 时取标记间隔 20 性能最优 这 是由于随着无线信道错误率的增加 相对较小的 标记间隔 Biasmax 8 会使得 out 包与其他包一 起丢失 从而造成了部分无线丢包的误判 同样 改变瓶颈链路的带宽 最佳标记间隔 也将发生变化 因为 out 包的数目应随着拥塞丢包 的增加而增加 因此提高 BQM 方法准确性的途径 应当是动态调节标记间隔以适应网络状态的变化 3 2 A BQM 方法描述 针对队列的丢包特征 实现一种自适应的模 式匹配方法有以下需要解决的关键问题 1 如何调节匹配的模式 严格的方法应该是 基于丢包率来进行调节 即在时间轴上对丢包率等 间隔采样 根据历史数据和当前采样调节标记间隔 但这种基于时间驱动的方法需要额外的测量和统计 工作量较大 在此设计了基于事件驱动的方法 将 发送方收到的ACK 事件作为调节的依据 当连续3 个 ACK 到达时 表明网络状态正常 应当加大标 记间隔 当连续3 个带out 标记的重复ACK 到达时 表明拥塞丢包严重 应当减少标记间隔 通过实验发现采用加性增加 乘性减少的方式 对标记间隔进行调整 可以使该方法较为平滑和 有效地适应网络状态的变化 另外 为了保证方 法的正确性 在调节时应当对标记间隔的变化范 围进行限制 因为过小的标记间隔 有可能使得 队列中几乎全为 out 包 过大的标记间隔 有可能 使得队列中几乎全为 in 包 这些都将导致算法失 效 如果将变化范围定义在 min max 之间 那么 min 是一个合理的小数 max 则与发送方缓存数据 包的大小有关 以下的实验中 min 取 4 max 取 buffersize 2 2 如何在收发双方通告调节的参数 当发送 方根据 ACK 到达的情况调节标记间隔 Biasmax 时 接收端需要得知这种变更以重新确定匹配因子 K 这里可以发送控制包来通知接收端 但是这种做 法需要额外的开销 更重要的是会带来附加的时 延 在此用简单的概率统计代替接收端的模式匹 配 即发送方收到某个数据包的重复 ACK 时 分 析它是否带有 out 标记 如果有 就把该数据包归 为拥塞丢包 否则归为错误丢包 对于连续丢包 的情形 则从最小序号开始搜索序列中缺失的包 一旦搜到带有 out 标记的包 就将该次丢包归为拥 塞丢包 否则归为无线丢包 3 如何处理严重的无线错误 混合网络中 TCP 除了拥塞控制之外 还需要完成错误控制的 任务 因此 ELN 机制不能一味地向发送方屏蔽信 18 通 信 学 报第 28 卷 道错误 当比特错误严重时不采取任何措施将影 响 TCP 的性能 在一些已有的工作中都提出了这 个问题 19 认为当收到连续 3 个带 ELN 标志的 ACK 时 应当降低 TCP 发送速率以避免不必要的 信道浪费 提出的A BQM 方法需要对TCP 进行如下修改 1 TCP 发送方 根据 ACK 事件设置标记间 隔 然后以此间隔对正常发送的数据包进行等间 隔标记 伪码描述见图 2 2 路由器 在尾丢弃的队列管理中对带 out 标记的数据包进行优先丢弃 3 TCP 接收方 收到连续失序的数据包时 要在已收到的序列中搜索丢失的数据包 其中如果 有带 out 标记的包 就将该丢包归为拥塞引起的 否则传回一个带ELN 标志的 ACK 给发送方 图3 给出了相应的伪码描述 其中next 指当前期待的数 据包序号 seq 指当前收到的数据包序号 maxseen 指当前滑动窗口 0 wndmask 内已收到的最大包序 号 Recv Packet pkt update in out ack 触发 biasmax 的调节 if eln 为 1 执行 tcp eln do not halve cwnd else As Newreno 误码严重时降低窗口发送速率以减少信道浪费 if in 均为 1 cwnd cwnd 2 Output int seqno 生成的数据包每间隔 biasmax 标记为 0 相当于 out if 正常数据包 tcph bias bias bias bias 1 biasmax else bias biasmax 重传数据包标记最大值 Update int in out ack 统计连续发生 3 次的 ack 事件 if Dupack if pkt bias out out 计数器加 1 else in 计数器减 1 else ack 计数器加 1 if 完成 3 次统计 out in ack 数组初始化 if out i 均为 1 i 1 将该数据包的 ack 标记的 eln 位置 1 图 3 A BQM 方法的 TCP 接收方伪码 3 3 A BQM 方法分析 BQM 方法的核心是对队列的丢包特征按照模 式函数 r x kkrxF1 r x kkrxF1 进行匹配 而 A BQM 方 法则将判断的方法简化为在连续丢包序列中对 out 包的搜索 那么这种简化是否合理呢 已知有序集合 Pnxt Phi 中数据包的数目为 S 其中有 y 个 out 包 假设标记间隔等于 b 那么 队列中的包序列可表示为 110110 nxtnxt 1nxt nxt 1nxt 2 1nxt 2 bb bbbbb PPPPPP 相当于 ininoutininout nxtnxt 1nxt nxt 1nxt 2 1nxt 2 bbbbb PPPPPP 现在 S 个包中有 r 个包丢失 如果这次丢包是 无线错误引起的 那么丢失的包将成为 S 个元素 中的 r 次随机采样 设其中包含 x 个 out 包 令 X 为 x 分布的随机变量 则 yrx xsy p Xx s r 1 A BQM 认为若1x 则 Xxp 极小 值 下面对这个假设进行论证 将 x 1 代入式 1 可得 1 1 1 1 1 sysrys rsrry r s ys ry XP 假设 A BQM 能够准确设置标记间隔 Biasmax 即 在每次丢包行为中使得yr 那么 1 1 1 21 21 y yy syy yy P X syys sys s 第 5 期叶进等 无线 有线网络中基于自适应丢包区分的 TCP 改进 19 2 1 1 1 21 21 y yy syy yy P X syys sys s 理想状态下 A BQM 方法标记的 out 包正好全 部被丢掉 即ysp p 为丢包率 代入式 2 1 12 1 1 sps spspsp XP 2 spsp sp sps 1 12 1 2 1 spsp 1 1 1 spss 3 1 2 可见 P X 1 0 5 1 2 以一次 TCP 连接为例 S 10 P 0 1 则 P X 1 0 14 10 6 因此理想的 A BQM 方法中 若1x 则 xXP 的假设成立 4 性能分析 在 NS2 中实现了 A BQM 方法 将使用该方 法后的 TCP 性能与文献 18 中的 BQM 方法 以及 传统的 TCP Reno 进行了比较 为了分析三者的性 能 在图 1 所示的拓扑结构中设计了以下 3 个实 验 实验 1 只有长流的情况 即图 1 的拓扑中有 一个背景流 UDP0 和最后一跳为无线链路的 TCP 流 TCP1 无线链路上的错误模型采用恒定 为 0 02 的误码率 实验 2 短流和长流混合的情况 在 5 15s 期间加入一个突发的短流 TCP2 其他设置与实 验 1 相同 实验 3 无线链路上的错误模型的错误率不再 恒定 而是周期性地在不同的错误状态间转换 我们采用了 NS2 中的两状态 Markov 模型 从 好 状态 错误率为 0 01 到 坏 状态 错误率为 0 07 之间的转移概率均为 0 5 其他设置与实验 2 相同 4 1 丢包区分正确率的比较 为了验证丢包区分正确率 将 3 个实验中丢 包的正确模型 与 BQM ABQM 方法区分的结果 进行比较 表 2 列出了统计得到的准确率指标 表 2不同实验中的 BQM ABQM 准确率 实验 1实验 2实验 3 算法BQMA BQMBQMA BQMBQMA BQM P C C 0 380 380 760 820 180 91 P W W 0 800 820 130 690 330 86 总体正确率 0 540 550 48 0 790 310 88 如表2 所示 A BQM 方法在实验1 中正确率 与 BQM 几乎一样 这是由于该状态中没有加入突 发的竞争流量 恒定误码率的错误模型表现为等间 隔丢包 因此没有触发改变标记间隔的事件发生 区分算法始终在原来的参数条件 Biasmax 8 下运 行 在其他 2 个实验中对无线错误的区分能力大 有提高 尤其在实验 3 中 ABQM 的优势非常明显 说明这种自适应调节能够较为准确地跟踪信道状 态的变化 在瓶颈带宽和链路错误突变的情况下 仍然保持了较为理想的丢包区分能力 4 2 TCP 性能的比较 在实验 3 环境下 进一步分析丢包识别方法 对 TCP 性能的改进 从图 4 图 5 可见 1 采用丢包区分方法后 TCP 流总的吞吐量较 TCP Reno 有一定的提高 A BQM 方法较 BQM 方 法表现更好 t s 图 4 TCP 吞吐量 t s a TCP Reno 拥塞窗口 拥塞窗口 20 通 信 学 报第 28 卷 t s b BQM t s c A BQM 图 5 TCP 发送窗口变化情况 2 在 TCP Reno 中由于无线链路的影响 TCP1 流在竞争中占较大的劣势 采用 BQM 方法 后情况有明显的改善 包含无线链路的 TCP1 连接 窗口平均值增加了 但是两者的不公平性依然存 在 与 BQM 相比 A BQM 在突发 TCP 流时更好 地保持了两者的公平性 3 TCP1 流窗口的抖动在采用 BQM 后明显减 少了 采用 A BQM 后抖动性进一步减少了 在表 3 中进一步将实验 2 和实验 3 中的 TCP 性能进行了对比 表中除了抖动率指的是 TCP1 流 的时延抖动外 其余指标均指 TCP1 流和 TCP2 流 的特性 表 3 不同错误模型下不同方法的 TCP 性能 模型方法吞吐量公平性抖动率 Reno7090 9460 006 70 BQM7960 9770 006 45实验 2 A BQM8240 9830 006 27 Reno8380 9380 006 25 BQM9220 9870 006 12实验 3 A BQM9600 9990 005 85 从表 3 可以看到 相对 TCP Reno 协议 采用 BQM 和 A BQM 方法进行丢包区分后 3 个指标 得到了不同程度的改善 并且 A BQM 在 BQM 的 基础上也有较大提高 尤其在采用动态错误模型 的实验 3 中性能的改善最为显著 由于有线和无线信道的不同特征 在混合网 络中通过不同信道的 TCP 流之间将存在严重的不 公平性 随着无线错误率和网络拥塞的加剧 经 过无线链路的 TCP 流最后将因为竞争不到任何带 宽而默默饿死 因此在动态网络中保持丢包区分 的准确性 对改善这种不公平性将起到较为显著 的作用 正是由于 A BQM 方法使得丢包区分的 准确率提高 能够更好地屏蔽复杂多变的无线错 误 从而使之能够与其他 TCP 流公平竞争瓶颈带 宽 5 结束语 本文提出了一种自适应丢包区分方法 A BQM 它能够动态调节与队列的丢包特征相匹 配的模式 从而能够在瓶颈拥塞和无线错误增加 的情况下 保证丢包区分的准确率 与 BQM 方法 只适用于轻度拥塞和较低误码相比 A BQM 的伸 缩性有较大的提高 并且实现简单 开销较小 实验证明 A BQM 方法在不同网络状态下都具有 较高的丢包区分能力 能够自适应于网络状态的 变化 同时 A BQM 有效提高了网络总吞吐量和 TCP 流的公平性 致谢 感谢 Saad Biaz 教授提供文献 18 中使 用的 BQM 源代码 参考文献 1 BARAKAT C ALTMAN E DABBOUS W On TCP Performance in a heterogeneous network a survey EB OL http www2 univ reunion fr panelli enseignment TRA documentation Barakat01 pdf 2004 2 冯彦君 孙利民 钱华林等 MANET 中 TCP 改进研究综述 J 软件 学报 2005 16 3 434 444 FENG Y J SUN L M QIAN H L et al Improving TCP performance over MANET a survey J Journal of Software 2005 16 3 434 444 3 叶进 王建新 异构计算机网络中端到端丢包控制研究综述 J 计 算机科学 2006 33 12 19 22 YE J WANG J X The research of loss differentiation algorithm in heterogeneous networks J Computer Secience 2006 33 12 19 22 4 BALAKRISHNAN H KATZ R Explicit loss notification and wireless Web performances A Mobecom 98 C 1998 拥塞窗口 拥塞窗口 第 5 期叶进等 无线 有线网络中基于自适应丢包区分的 TCP 改进 21 5 KOPPARTY S KRISHNAMURTHY S FALOUTOUS M Split TCP for mobile ad hoc networks A Proc of IEEE GLOBECOM C Taipei Taiwan 2002 6 BALAKRISHNAN H SECHAN S AMIR E Improving TCP IP performance over wireless networks A ACM MOBICOM 95 C Berkeley CA 1995 2 11 7 王波 范平志 基于无线自组织网络的 TCP Freeze Probing 改进 协议 英文 J 软件学报 2005 16 5 878 885 WANG B FAN P Z TCP freeze probing enhancement for mobile ad hoc networks J Journal of Software 2005 16 5 878 885 8 BHANDARKAR S SADRY N A REDDY L N et al TCP DCR a novel protocol for tolerating wireless chaneel errors J Lecture Notes in Computer Science 2004 2 1 17 9 WANG F ZHANG Y Improving TCP performance over mobile ad hoc networks with out of order detection and response A Proc of ACM MOBIHOC C Lausanne Switzerland 2002 217 225 10 SAMARAWEERA N K G Non congestion packet loss detection for TCP error recovery using wireless links A IEEE Proceedings Communications C 1999 11 BIAZ S VAIDYA N Discriminating congestion losses from wireless losses using interrival times at the receiver A Proc IEEE Symp Application Specific Systems and Software Engineering and Technology C Richardson TX 1999 10 17 12 TOBE Y TAMURA Y MOLANO A et al Achieving mode