基于线性均方误差的无线自组网TCP定时器改进
李庆华1, 2,陈志刚1,邓晓衡1
(1. 中南大学 信息科学与工程学院,湖南 长沙,410083;
2. 宜春学院 计算机系,江西 宜春,344000)
摘要:对无线自组网TCP数据流重传定时器(RTO)与传输回路时间(RTT)的关系进行仿真和分析;指出在RTT剧烈振荡的无线多跳网络环境下RTO值(TRTO)的变化会滞后于RTT值(TRTT)的变化,导致TRTO估计不准确;利用线性均方(LMS)误差估计理论改进TRTO的估计算法。实验结果表明:基于LMS的TRTO估计算法能准确的估计TCP数据传输的TRTT,减少TCP数据传输中的伪重传,提升无线环境下TCP协议的数据吞吐量。
关键词:无线自组网;802.11协议;TCP定时器;线性均方估计;吞吐量
中图分类号:TP393 文献标志码:A 文章编号:1672-7207(2012)05-1780-07
Improving TCP timer in wireless ad hoc networks based on linear mean squares
LI Qing-hua1, 2, CHEN Zhi-gang1, DENG Xiao-heng1
(1. School of Information Science and Engineering, Central South University, Changsha 410083, China;
2. Department of Computer, Yi Chun University, Yichun 344000, China)
Abstract: The relationship between retransmission time-out (RTO) and round-trip time (RTT) of TCP data flow in wireless ad hoc networks was simulated and analyzed, then the RFC 2988 RTO estimated value was not accurate as the change of RTO value (TRTO) was late to catch up the change of RTT value (TRTT) over wireless ad hoc networks. The RTO estimated algorithm was improved by using linear mean square (LMS) theory. Simulation results show that the LMS RTO algorithm can estimate RTT accurately, so the TCP data flow based on LMS timer can reduce the TCP spurious retransmission, and then promote the TCP data throughput in wireless ad hoc networks.
Key words: wireless ad hoc network; 802.11 protocol; TCP timer; linear mean squares; throughput
近来,无线自组网在网络研究领域受到了广泛关注。它没有中心访问节点或者固定的基础设施,网络中的每个节点既是通信节点又是路由节点,各个节点通过分布式控制算法相互协调完成网络的通信功 能[1]。TCP协议可为用户在不可靠的网络上提供可靠的端到端的数据传输服务[2]。因为传输的可靠性,TCP协议现已成为互联网上一种最为广泛配置的协议[3]。随着无线网络技术的发展,在无线网络上采用TCP协议为可靠的数据传输提供服务成了人们的第一选 择[4]。TCP协议源端判断数据发送是否超时的工具是重传定时器(RTO),它通过对TCP数据报传输回路时间的估计来判断当前的数据发送是否超时[5]。过低的RTO估计值(TRTO)会导致TCP频繁的伪重传,加重网络拥塞,减小TCP发送窗口的大小;同时,过高的RTO估计值会在网络发生丢包时使TCP发送端超时等待,降低TCP的效率[6]。现有TCP-Newreno的RTO估算方法是根据RFC 2988标准[7]来进行计算的。在传输回路时间(RTT)值变化较平缓的有线网络环境下,根据此标准计算的RTO值的变化能准确的反映出RTT值(TRTT)的变化,使得TCP定时器在有线环境下性能较好[8]。研究人员对无线网络环境下的TCP协议进行较多研究[1, 3-4],如对无线环境下的TCP定时器进行了分析,指出在无线环境下RTT值变化较大,容易出现TCP伪重传,导致TCP协议在无线环境下性能低下,并提出了一种针对TCP伪重传的快速恢复方法[9-10]。Tamura等[11]分析了无线局域网中的伪重传问题,并提出一种有效的TCP重传机制;张文彬等[12]提出一种ad hoc环境下提升TCP吞吐量的新定时器方案。但是,已有研究没有涉及到无线环境下基于RFC 2988标准的 TCP定时器本身的有效性问题。本文作者基于802.11协议的无线自组网TCP数据流的TRTT和TRTO指标进行详细仿真,指出基于指数滑动平均方法的RFC 2988 标准RTO计算方法在TRTT剧烈振荡的无线网络环境下会出现TRTO的变化滞后于TRTT变化的现象,从而导致RTO估计值过高或者过低,这种现象在TCP数据报大小不等的数据传输过程中还会加剧。为改进无线环境下TCP定时器RTO值估计不准确的情况,采用线性均方估计理论[13]改进无线环境下TCP定时器的RTO计算方法。实验结果表明:基于线性均方估计(LMS)的RTO估计算法在无线自组网TCP数据传输过程中不会出现TRTO的变化滞后TRTT变化的现象,并且能减少TCP协议的伪重传,提升TCP协议在无线环境下的数据吞吐量。
1 无线自组网TCP定时器性能仿真与分析
根据RFC 2988标准[7],计算TCP重传定时器RTO的表达式为:
TRTO=TSRTT+max(G, 4TRTTVAR) (1)
其中:G表示TCP的时针滴答,TSRTT和TRTTVAR的表达式分别为:
TSRTT=7/8TSRTT+TRTTVAR/8 (2)
TRTTVAR=3/4TRTTVAR+|TSRTT-TRTT|/4 (3)
其中:TRTT表示当前数据包传输回路时间,TSRTT表示平滑环回时间,TRTTVAR表示环回传输时间的变化值。从式(1)可知,TCP定时器的TRTO由数据报传输回路时间RTT的平均值和变化值组成。文献[1]在有线环境下对RTO计算方法的有效性进行深入的仿真和分析,指出在有线环境下RTT值变化较平滑,没有出现较大的波动,所以根据此标准的TRTO计算方法在有线环境下性能较好。而对于无线多跳网络,需要考虑TCP数据流的TRTT是否类似有线环境下变化平滑以及TRTO是否能准确的根据TRTT的变化而变化。
采用NS2网络模拟器对TCP定时器在无线环境下的性能进行仿真,网络拓扑采用如图1所示的线形拓扑,MAC层协议为IEEE 802.11,TCP版本为Newreno[14],有关仿真的详细参数设置如表1所示。
图1 含5个节点的线形拓扑无线自组网
Fig.1 Line topology wireless ad hoc network with 5 nodes
表1 实验参数配置
Table 1 Experiment parameters
首先,在节点1和节点5之间建立1条TCP连接,在其上承载FTP数据流,FTP数据流的仿真持续时间为80 s,图2给出不同数据报长度的TRTT和TRTO。图2(a)对应的实验TCP数据报长度为500字节,图2(b)对应的实验TCP数据报长度为1 500字节。从图2(a)可见,在无线网络环境下,TRTT和TRTO都有较大幅度的振荡。例如,在图2(b)中TRTT可以在0.1 s内由 134 ms降到49 ms。同时,仿真数据流的TRTO曲线与TRTT曲线总体上呈现出相同的变化规律,但是,TRTO出现变化的时间明显滞后于TRTT变化的时间约0.2~0.3 s,即TRTO曲线的变化滞后于TRTT曲线约0.2~0.3 s。
上述实验结论是在整个仿真过程中TCP数据报长度不变的情况下获得的,在实际的TCP数据传输中,所有TCP数据报的大小不可能都相等。为此,本文作者简单修改了NS2中TCP的实现代码,使TCP连接在仿真传输过程中随机产生大小为500字节或 1 500字节的数据报。实验仍采用图1所示拓扑和表1所示参数,其实验结果如图3所示。
图2 不同TCP数据报长度的TRTT和TRTO
Fig.2 TRTT and TRTO for different TCP datagrams
图3 TCP数据报长度为500或1 500字节随机值的TRTT和TRTO
Fig.3 TRTT and TRTO when TCP datagram length is 500 or 1 500 bytes
从图3可见:TRTO曲线与TRTT曲线总体上还是与图2呈现相同的变化规律,即TRTT与TRTO波动幅度较大,TRTO曲线的变化滞后于TRTT曲线约0.2~0.3 s。但是,在仿真的TCP数据传输过程中多处出现TRTO与TRTT非常接近和差距较大的情况,通过对实验的数据文件分析,TRTT与TRTO非常接近和差距较大的具体情况如表2和3所示。从表2和3的实验数据可知,TRTO与TRTT在仿真过程的某些时间非常接近,最小相差仅1 ms。同时,在一些时间点也会出现TRTO与TRTT相差较悬殊的情况。如当t=57 s时,TRTO为120 ms,而TRTT仅为14 ms,相差约8.5倍。
表2 TRTO和TRTT值(非常接近)
Table 2 TRTO and TRTT value (Very close) ms
表3 TRTO和TRTT(差值很大)
Table 3 RTO and RTT value (Big difference) ms
在无线的数据传输过程中,因为无线信道的共享特点,1个节点的数据发送会干扰其传输范围内的其他节点的数据传输,造成无线节点在不同发送过程中出现不同的发送概率和冲突概率,使得数据报的传输时间和传输回路时间产生较大幅度的振荡。而对于数据报大小不一的TCP数据流,因为无线节点在发送大的数据分组时其发送成功概率相对于小的数据分组会急剧降低[1],进而加剧TRTT的振荡。而基于RFC 2988标准的TRTO估算方法对初值敏感,对TRTT的剧烈振荡反应滞后,其估算方法采用的指数滑动平均方法属于非自适应算法,预测值与实测值之间的误差不能反映到新的预测过程中来。所以,当TRTT出现由小到大或者由大到小的剧烈变化时,基于RFC 2988标准的TCP定时器就会出现估计值过小或者过大,造成TCP的伪重传或超时等待,降低TCP在无线网络环境下的 效率。
2 基于线性均方估计的无线自组网定时器改进
在TCP数据传输过程中,记第n次RTT采样值的前M拍RTT值为输入向量为X(n),其对应的权重向量为W(n),即:
(4)
(5)
根据线性均方估计理论,第n+1次的RTT估计值可通过对其前M拍RTT采样值进行加权求和后得到,即:
(6)
根据式(6)可知,第n+1次的RTT估计只需要知道前M拍RTT的观测样本和其对应的权值就可算出。观测样本值在实验中可以得到。在线性最小均方估计中,算法的计算输出和期望响应存在误差,定义第n次的估计误差为:
(7)
定义代价函数为估计误差的均方值:
(8)
为求解最小的估计误差值,定义如下的梯度算符:
k=1, 2, …, M (9)
对于实数的RTT采样值输入,其对应的权系数也应为实数。将式(8)代入到式(9),则代价函数的梯度算符可表示为:
k=1, 2, …, M (10)
根据最小均方误差算法,要对观测数据进行准确的估计,估计误差e(n)最小时其均方误差才能达到最小;而要使e(n)最小,其代价函数的导数必须为0。令eopt(n)为均方误差最小时的估计误差,则式(10)可以表示为:
, k=1, 2, …, M (11)
定义梯度向量:
(12)
将式(11)代入式(12),可得:
(13)
根据Widrow[16]提出的最小均方误差自适用算法,其权重向量W(n)可表示为:
(14)
将式中代价函数的梯度向量的期望值用瞬时值代替,即:
(15)
将式(15)代入式(14),得:
(16)
只要确定参数M和步长因子,通过式(16)就可求出权重向量W(n),从而实现对第n+1次RTT值的估计。M值越大,估计精度越高,但是其算法复杂度也随之增大。对于步长因子,其值越小,算法收敛越慢,但稳态误差也越小,且其值必须满足以下条件:
(17)
令,为了算法的简便,我们将设置为常数。令u(n)=u/6,u/3,u/2,2u/3和5u/6,同时,令M分别为2,3,4,5和6;采用前面仿真实验数据报长度为500字节的RTT实验数据(30~40 s时间段),比较不同参数所产生的均方误差,结果如表4所示。
表4 不同参数的均方误差比较
Table 4 Square error for different parameters
从表3可知:随着M的增大,其均方误差减少,但是当M=4以及M>4时,其均方误差基本上收敛于某一常数,因此我们选取M=4作为TRTT估计的拍数;而对于步长因子u(n),当其值为u/2以及小于u/2时,均方误差基本上收敛于某一常数,基于算法复杂度和计算精度的折中,选择步长因子u(n)= u/2。
3 性能仿真与分析
本文作者在NS2平台上实现了基于LMS的无线自组网TCP定时器RTO计算方法,方法如下:
(18)
其中:G表示TCP的时针节拍;和的表达式分别为:
(19)
(20)
用此方法与原有的RFC 2988标准算法进行性能比较,仍采用图1所示拓扑和表1所示实验参数,对改进的RTO算法的进行仿真,实验结果如图4所示。
图4 不同TCP数据报长度的RFC 2988 RTO与LMS RTO曲线
Fig.4 RFC 2988 RTO and LMS RTO for different TCP datagrams
从图4可见:基于最小LMS的RTO算法比RFC 2988标准算法具有较小的RTO估计值;基于LMS算法的TRTO变化曲线比以RFC 2988标准计算的TRTO曲线要左移0.2~0.3 s左右,刚好与RFC 2988 RTO曲线滞后于RTT曲线0.2~0.3 s相抵消。图5给出数据报长度为500字节或1 500字节随机值的TRTT与TRTO。根据图5可见:基于LMS的RTO算法不会出现TRTO 的变化滞后于TRTT从而导致TRTO估计不准确现象。
图5 数据报长度为500字节或1 500字节随机值的TRTT和TRTO
Fig.5 TRTT and TRTO when TCP datagram length is 500 or 1 500 bytes
另外,通过表5的实验数据发现,基于LMS的RTO算法所得的RTO平均值要少于RFC 2988标准算法所得的平均值,说明基于LMS的重传定时器性能要优于RFC 2988标准定时器算法。图6证实本文研究的结论,即基于LMS的重传定时器在TCP的吞吐量性能上要优于RFC 2988标准的定时器。图7给出了没TCP定时器的吞吐量性能比较。从图7可见:数据报为500字节的TCP数据流在20~35 s的时间内有1次伪重传(同样的实验环境,同样的传输控制算法,基于LMS的重传定时器数据流没有出现重传而基于RFC标准的重传定时器数据流则出现重传,据此可以判断为伪重传),而数据报随机选择的500或1 500字节的数据流则出现了2次伪重传,证实了本文第2节的分析,即当TCP数据报长度大小不一时,因为TRTT变化更大,RFC 2988定时器的性能会更差。同时,表明基于LMS的重传定时器能有效的适用TRTT的波动,从而减少TCP数据流在无线环境下的伪重传,提升TCP数据流的吞吐量。
表5 LMS RTO, RFC RTO, LMS RTT和RFC RTT的平均值
Table 5 Average value for LMS RTO, RFC RTO, LMS RTT and RFC RTT
图6 网格拓扑环境下基于不同TCP定时器的FTP1数据流吞吐量性能比较
Fig.6 FTP1 throughput performance with different timers in grid topology environment
图7 不同TCP定时器的吞吐量性能比较(20~35 s时间段)
Fig.7 TCP throughput performance for different timer (20~35 s)
为验证基于LMS的RTO定时器在不同拓扑环境下的性能,设计如图8所示的网格拓扑[17],在其上同时运行4个FTP数据流(只统计其中的FTP1数据流)。采用TCP发送端数据发送的字节数作为不同TCP定时器协议性能的评价指标。实验中节点之间距离为200 m,MAC层选用表1所示的参数,路由层采用静态路由机制。
图8 附加4个FTP数据流的网格拓扑无线自组网
Fig.8 Grid topology wireless ad hoc network with 4 FTP data flows
从图6可见:在网格形式的无线自组网环境下,基于LMS的重传定时器在TCP的吞吐量性能上要优于RFC 2988 标准的定时器,同时也验证了基于RFC2988标准的TCP定时器在数据报大小不一的情况下其性能会更差,而改进的LMS定时器则能适用数据报大小不同的数据流。
4 结论
(1) 针对无线多跳网络环境下TCP数据流的TRTT变化较大,RTO估计值的变化滞后于TRTT变化从而导致TRTO估计不准确的现状,本文利用线性均方误差估计理论实现对传输回路时间的精确估计,并以此改进TRTO的估计算法。
(2) 仿真实验表明:基于LMS定时器的TCP数据流能有效估计数据传输过程中的TRTT,能克服基于RFC 2988标准定时器在无线环境下TRTO变化滞后于TRTT变化的现象,能减少TCP数据流的伪重传,提升了TCP协议在无线自组网环境下的效率。
参考文献:
[1] 周建新, 邹玲, 石冰心. 无线网络TCP研究综述[J]. 计算机研究与发展, 2004, 41(1): 53-59.
ZHOU Jian-xin, ZOU Ling, SHI Bing-xin. A survey of TCP performance in wireless networks[J]. Journal of Computer Research and Development, 2004, 41(1): 53-59.
[2] 邓晓衡, 陈志刚, 张连明, 等. TCP Yuelu: 一种基于有线/无线混合网络端到端的拥塞控制机制[J]. 计算机学报, 2005, 28(8): 1342-1350.
DENG Xiao-heng, CHEN Zhi-gang, ZHANG Lian-ming, et al. TCP Yuelu: An end-to-end congestion control mechanism for wired/wireless hybrid networks[J]. Chinese Journal of Computers, 2005, 28(8): 1342-1350.
[3] Ahmad A H, Eitan A, Philippe N. A survey of TCP over Ad hoc networks[EB/OL]. [2010-05]. http://www-sop.inria.fr/maestro/ personnel/Philippe.Nain/PAPERS/TCP/TCP-Survey-Ad-Hoc. pdf.
[4] Zheng F, Petros Z, Haiyun L, et al. The impact of multihop wireless channel on TCP throughput and loss[C]//IEEE INFOCOM. San Francisco, USA: IEEE, 2003: 7753-7803.
[5] Sarolahti P, Kojo M, Raatikainen K. F-RTO: An enhanced recovery algorithm for TCP retransmission timeouts[C]// Proceedings of ACM SIGCOMM: ACM, 2003: 985-994.
[6] Gurtov A, Ludwig R. Responding to spurious timeouts in TCP[C]//Proceedings of IEEE INFOCOM, 2007.
[7] RFC 2988. Computing TCP’s Retransmission Timer[S].
[8] Ioannis P, Vassilis T. Why TCP timers (still) don’t work well[J]. Computer Networks, 2007, 51: 2033-2048.
[9] Gavin H, Nitin V. Analysis TCP performance over mobile Ad hoc networks[J]. Wireless Networks, 2002, 8(2): 275-288.
[10] Ying J Z, Lilly K J. On making TCP robust against spurious retransmissions[J]. Computer Communications, 2005, 28(8): 25-36.
[11] Tamura Y, Tobe Y, Tokuda H. EFR: A retransmit scheme for TCP in wireless LANs[C]//Local Computer Networks. LCN ’98. Proceedings, 23rd Annual Conference, 1998: 205-218.
[12] 张文彬, 张中兆, 王孝. 提高ad hoc网络中TCP吞吐量的新定时方案[J]. 吉林大学学报: 工学版, 2008, 38(1): 233-238.
ZHANG Wen-bin, ZHANG Zhong-zhao, WANG Xiao. New timing scheme for increasing TCP throughput in ad hoc network[J]. Journal of Jilin University: Engineering and Technology Edition, 2008, 38(1): 233-238.
[13] 张贤达. 现代信号处理[M]. 北京: 清华大学出版社, 2002: 1-348.
ZHANG Qian-da. Modern signal procession[M]. Beijing: Tsinghua University Press-Springer, 2002: 1-348.
[14] RFC 2582. The newreno modification to TCP’s fast recovery algorithm[S].
[15] Widrow B, Stearns S D. Adaptive signal processing[M]. New York: Prentice-Hall, 1985: 1-457.
[16] Joshua R, Edward W K. A performance study of deployment factors in wireless mesh networks[C]//INFOCOM 2007 Anchorage, Alaska, 2007: 3415-3428.
(编辑 邓履翔)
收稿日期:2011-05-03;修回日期:2011-08-14
基金项目:国家自然科学基金资助项目(60873082);江西省教育厅科技计划项目(GJJ12602)
通信作者:李庆华(1976-),男,湖南湘乡人,博士,讲师,从事无线网络研究;电话:15279851959;E-mail: netow@163.com