论文部分内容阅读
[摘要]随着Internet广泛应用,拥塞控制技术已成为网络研究热点之一,描述Internt端到端产生拥塞的基本原因,重点阐述TCP拥塞控制策略和拥塞控制四种算法的性能及应用,进一步分析TCP拥塞控制技术最新研究成果及方向。
[关键词]Internet TCP协议 拥塞控制 算法
中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)0810062-02
随着Internet广泛应用,用户对网络服务质量要求更高,同时越来越严重的网络拥塞问题引起广泛关注。当前人们对Internet拥塞控制理论研究主要集中在2个方面:首先是在Internet的端系统(或源系统),本质上是一种基于信源的拥塞控制策略;其次是在Internet的中间链路节点系统,本质上是一种基于路由器等网络中间链路节点的拥塞控制策略。Internet系统的可靠性、鲁捧性越来越依赖于拥塞控制机制,由于当前网络拥塞控制的大部分工作是由TCP协议完成的。因此,分析和研究更有效的TCP拥塞控制策略及算法具有重要的意义。
一、拥塞控制基本概念
许多学者和网络专家认为网络拥塞现象产生的根本原因或判断标准是用户(或叫源系统)提供给网络的负载(Load)超过网络系统资源容量和处理能力(Overload)[1][17],直接表现为数据包延时增加、丢弃概率增大、吞吐量(goodput)急剧下降、上层应用系统性能下降,甚至导致网络崩溃(congestioncollapse)的发生。目前公认比较权威的“拥塞”解析是由Jacobson(1988)[2]提出:当一个子网或者子网的一部分出现太多分组的时候,网络性能开始下降,这种情况称为拥塞(congestion)。文献[3][4][5]比较一致形象描述了网络拥塞情况,如图(1):当源系统(用户)发送的数据分组总量小于系统容量范围的时候,所有分组可以被递交,也就是理想的范围。当源系统(用户)发送的数据分组总量超过系统容量范围的时候,拥塞就开始出现,分组开始丢失率增大、延时加大、网络性能随分组数量增大急速下降,甚至整个系统发生崩溃。[6]
Meom C(2000)提出网络负载情况分析:图(2)、(3)描述了当网络发生拥塞崩溃时,微小的负载增量都将使网络的有效吞吐量(goodput)急剧下降。网络负载较小时,吞吐量与网络负载之间呈线性关系,网络延迟缓慢增加;网络负载超过(Knee)后,网络吞吐量增长缓慢,网络延迟增长变快;网络负载到达(Cliff)后,网络吞吐量急剧下降,网络延迟急剧上升。原先有学者提出拥塞产生最基本的原因是由存储空间不够、带宽容量不够、处理器处理能力低引起的,但实践表明:即使提供足够的空间、带宽、无限提高处理器能力也无法避免网络拥塞发生。研究表明:拥塞控制涉及到Internet、通信、物理、非线性规划、系统控制、优化等理论系统,是个复杂的系统工程。[7]
二、TCP拥塞控制策略
Internet拥塞控制策略实施一般在传输层进行,因为TCP协议一直是主要的端到端(end-to-end)的资源分配方案。TCP拥塞控制策略一般实现拥塞避免(congestion avoidance)和拥塞控制(congestion control)2种相辅相成的功能。拥塞避免是“预防”机制,它的目标是避免网络进入拥塞状态,使网络运行在高吞吐量、低延迟的状态下;拥塞控制是“恢复”机制,它用于把网络从拥塞状态中恢复出来。TCP拥塞控制目标保证网络运行在轻微拥塞的最佳状态,即使发生拥塞也保证网络系统不会崩溃。[8]
三、TCP拥塞控制算法分析
目前的TCP拥塞控制算法是基于Jacobson于1988年提出的,TCP协议采用的拥塞控制算法已经成为保证Internet稳定性的重要因素,大大提高了网络传输的性能。其实要真正解决拥塞的方案是减慢数据率,理论上采用分组守恒的原则。TCP通过动态管理维护拥塞窗口(congestion window就是传送端可以连续传送封包的大小,简称cwnd)来实现拥塞检测、拥塞避免功能。TCP拥塞控制算法一般采用如下策略:慢启动(Slow Start),拥塞避免(Congestion Avoidance)、快速重传(Fast Retransmit)和快速恢复(Fast Recovery)。与此对应的TCP拥塞控制算法主要有:TCP Tahoe、TCP Reno、New-Reno TCP、TCPSACK、TCP Vegas。
(一)TCP Tahoe
TCP Tahoe算法是拥塞控制早期版本,它实现三个最基本的功能:即Tahoe=Slow Start+Congestion Avoidance+Fast Retransmit。它检测网络拥塞的基本思路是:每当送出一个封包,会启动一个计时器,如果计时器在约定时间內沒有收到该封包的ACK,就表示网络出现拥塞。当收到重复的ACK封包时,表示接收端一直没有收到某一个封包,也代表网络出現拥塞。TCP Tahoe的工作机制是:当网络连接启动时,cwnd=1 segment,ssthresh
=65535 bytes。每收到一个ACK,cwnd就会增加,而增加的方式有2种方法:Slow Start及Congestion Avoidance。进入Slow Start或Congestion Avoidance是由cwnd是否超过ssthresh來判断,若cwnd (二)TCP Reno and New-Reno TCP
Jacobson(1990)等人在Tahoe TCP的基础上加入了快速恢复形成了RenoTCP算法Reno=Slow Start+Congestion Avoidance+Fast Retransmit+Fast Recovery。快速恢复算法的目的是在快速重传之后提高TCP算法的吞量。NewReno TCP(1996年,Fall和Floy在Reno的基础上提出了New Reno)算法是Reno TCP算法的基础上对快速恢复算法进行修改,添加了恢复应答判断功能,以增强TCP终端通过ACK报文信息分析报文传输状况的能力。NewReno TCP算法使TCP终端可以把一次拥塞丢失多个报文的情形与多次拥塞的情形区分开来,进而在每一次拥塞发生后拥塞窗口只减半一次,从而提高了TCP的顽健性和吞吐量。[12]
(三)TCP-SACK
SACK TCP(1996年,Mathis、Mahdavi、Floy和Romanow提出了Reno的另一变形:SACK)算法也是在Reno TCP算法的基础上增加了选择确认SACK和选择重传功能。SACK的基本思想是接受方TCP发送SACK分组来通知发送方接受数据的情况,这样发送方只重传丢失的分组。SACK在进入快速重传状态时,如果网络中的所有分组已经得到确认,那就会退出快速重传状态。
(四)TCP Vegas
L S Brakmo(1996)等提出了一种新的拥塞控制算法TCP Vegas。即“选择性重复”(selective repeat)策略。Vegas对Reno进行了三项重要的技术改进:(1)采用了新的重传触发机制,即用一个重复ACK(而非Reno中的3个)来启动超时判定规程,这样可以更及时地检测到拥塞的发生;(2)在慢启动阶段采用了更加谨慎的方式来增加窗口大小,减少了不必要的分组丢失;(3)改进“拥塞避免”阶段的窗口调整法。[6]
四、结束语
随着TCP拥塞控制研究的深入,已经有相当完善的拥塞控制算法理论,许多学者在文献[2][3][4]基础上对TCP拥塞控制进行深入研究,提出把系统控制理论引进拥塞控制,对TCP连接的公平性、建模等方面对TCP进行了扩展和改良。文献[13][14]等提出改进“慢启动”算法、用数学建模方式、优化理论来解决网络拥塞和算法组合策略;文献[15][16]等对最新TCP拥塞控制算法最新研究动态作了较好的分析总结,把线性规划、资源分配、竞争机制理论引入算法思想;文献[10]等对TCP拥塞控制在特殊网络中(高速网络、无线网络)进行深入的研究,并对TCP拥塞法进一步改良和组合、完善利用NS2仿真模型做了一些有意义数据和案例,为研究拥塞控制算法作了重要工作。总之,TCP拥塞控制算法还在不断发展中,将来会有更加完善的算法运用到实践中,由于作者水平有限,文中不足之处,恳请批评指正!
参考文献:
[1]Tanenbaum A S.Co mputer letworks.The third edition.B Pret.ice HalI.1996,374-378.
[2]Jacobson Congestion avoidance and contro1.ACM Co mputer Co mmunication Review,1988,18(4):314-329.
[3]Jacobson v.Co ngestion Avoidance and Co ntro1.IEEE/ACM Transaction Networking,1998,6(3):314-329.
[4]Gevros P,Crowcroft J,Kirstein P,et a1.Co ngestion contromechanisms and the best effort service mode1.IEEE Network,2001,15(3):16-26.
[5]Steves W.TCP S1ows Start,Co ngestion Avoidance,Fast Retransmit,and Fast Recovery Algorithms.RFC2001,1997.
[6]刘拥民、蒋新华、年晓红等,Internet端到端拥塞控制研究综[J].计算机科学,2008,Vo1.35№.2:6-12.
[7]Meom C.A new approach to model the stationary behavior ofTCP Co nnections.IEEE Co mputer Society,2000.
[8]Jain,R.Ramakrishnan,K.K.Chiu,Dah-Ming.Congestion avoidance in computer networks with a connectionless network layer.Technical Report,DEC-TR-506,Digital Equipment Corporation,1988.
[9]Floyd,S.Fall,K.Promoting the use of end-to-end congestion controlin theInternet.IEEE/ACMTransactionsonNetworking,1999,7(4):458-472.
[10]http://www.cs.nctu.edu.tw/-cmtsai/cgi-bin/wiki.pl?action=bro
wse;diff=2;id=TCP_Tahoe.Comments on TCP_Tahoe.
[11]章淼、吴建平、林闯,互联网端到端拥塞控制研究综述[J].软件学报,2002,Vol.13,No.3:354-363.
[12]封宁、白光伟,TCP拥塞控制算法的组合策略研究[J].微计算机信息(管控一体化),2009,第25卷,第4-3期:159-161.
[13]曹雪峰,TCP拥塞控制算法建模分析[J].现代计算机(总第二九九期)2009.1:120-122.
[14]马义忠、司颖、窦战伟,基于接收驱动的拥塞控制算法分析[J].计算机工程,2009.02,第35卷,第4期:119-124.
[15]何炎祥、熊乃学、杨燕,一种改进的TCP拥塞控制算法[J].计算机研究与发展,2005,42(12):2070-2076.
[16]贺婷婷、谢高岗、张广兴等,802.11无线接入TCP连接本地延迟抖动的理论模型[J].计算机应用研究,2009.01,第26卷,第1期:272-279.
[17]Audrew S.Tanenbaum著,潘爱民译,计算机网络(第四版)[M].北京:清华大学出版社,2004:256-271.
作者简介:
刘国栋(1980-),广东河源人,中山大学信息科学与技术学院计算机科学系2008级计算机软件与理论硕士研究生,任职于广州南洋理工职业学院,主要从事计算机教学工作。
[关键词]Internet TCP协议 拥塞控制 算法
中图分类号:TP3文献标识码:A文章编号:1671-7597(2009)0810062-02
随着Internet广泛应用,用户对网络服务质量要求更高,同时越来越严重的网络拥塞问题引起广泛关注。当前人们对Internet拥塞控制理论研究主要集中在2个方面:首先是在Internet的端系统(或源系统),本质上是一种基于信源的拥塞控制策略;其次是在Internet的中间链路节点系统,本质上是一种基于路由器等网络中间链路节点的拥塞控制策略。Internet系统的可靠性、鲁捧性越来越依赖于拥塞控制机制,由于当前网络拥塞控制的大部分工作是由TCP协议完成的。因此,分析和研究更有效的TCP拥塞控制策略及算法具有重要的意义。
一、拥塞控制基本概念
许多学者和网络专家认为网络拥塞现象产生的根本原因或判断标准是用户(或叫源系统)提供给网络的负载(Load)超过网络系统资源容量和处理能力(Overload)[1][17],直接表现为数据包延时增加、丢弃概率增大、吞吐量(goodput)急剧下降、上层应用系统性能下降,甚至导致网络崩溃(congestioncollapse)的发生。目前公认比较权威的“拥塞”解析是由Jacobson(1988)[2]提出:当一个子网或者子网的一部分出现太多分组的时候,网络性能开始下降,这种情况称为拥塞(congestion)。文献[3][4][5]比较一致形象描述了网络拥塞情况,如图(1):当源系统(用户)发送的数据分组总量小于系统容量范围的时候,所有分组可以被递交,也就是理想的范围。当源系统(用户)发送的数据分组总量超过系统容量范围的时候,拥塞就开始出现,分组开始丢失率增大、延时加大、网络性能随分组数量增大急速下降,甚至整个系统发生崩溃。[6]
Meom C(2000)提出网络负载情况分析:图(2)、(3)描述了当网络发生拥塞崩溃时,微小的负载增量都将使网络的有效吞吐量(goodput)急剧下降。网络负载较小时,吞吐量与网络负载之间呈线性关系,网络延迟缓慢增加;网络负载超过(Knee)后,网络吞吐量增长缓慢,网络延迟增长变快;网络负载到达(Cliff)后,网络吞吐量急剧下降,网络延迟急剧上升。原先有学者提出拥塞产生最基本的原因是由存储空间不够、带宽容量不够、处理器处理能力低引起的,但实践表明:即使提供足够的空间、带宽、无限提高处理器能力也无法避免网络拥塞发生。研究表明:拥塞控制涉及到Internet、通信、物理、非线性规划、系统控制、优化等理论系统,是个复杂的系统工程。[7]
二、TCP拥塞控制策略
Internet拥塞控制策略实施一般在传输层进行,因为TCP协议一直是主要的端到端(end-to-end)的资源分配方案。TCP拥塞控制策略一般实现拥塞避免(congestion avoidance)和拥塞控制(congestion control)2种相辅相成的功能。拥塞避免是“预防”机制,它的目标是避免网络进入拥塞状态,使网络运行在高吞吐量、低延迟的状态下;拥塞控制是“恢复”机制,它用于把网络从拥塞状态中恢复出来。TCP拥塞控制目标保证网络运行在轻微拥塞的最佳状态,即使发生拥塞也保证网络系统不会崩溃。[8]
三、TCP拥塞控制算法分析
目前的TCP拥塞控制算法是基于Jacobson于1988年提出的,TCP协议采用的拥塞控制算法已经成为保证Internet稳定性的重要因素,大大提高了网络传输的性能。其实要真正解决拥塞的方案是减慢数据率,理论上采用分组守恒的原则。TCP通过动态管理维护拥塞窗口(congestion window就是传送端可以连续传送封包的大小,简称cwnd)来实现拥塞检测、拥塞避免功能。TCP拥塞控制算法一般采用如下策略:慢启动(Slow Start),拥塞避免(Congestion Avoidance)、快速重传(Fast Retransmit)和快速恢复(Fast Recovery)。与此对应的TCP拥塞控制算法主要有:TCP Tahoe、TCP Reno、New-Reno TCP、TCPSACK、TCP Vegas。
(一)TCP Tahoe
TCP Tahoe算法是拥塞控制早期版本,它实现三个最基本的功能:即Tahoe=Slow Start+Congestion Avoidance+Fast Retransmit。它检测网络拥塞的基本思路是:每当送出一个封包,会启动一个计时器,如果计时器在约定时间內沒有收到该封包的ACK,就表示网络出现拥塞。当收到重复的ACK封包时,表示接收端一直没有收到某一个封包,也代表网络出現拥塞。TCP Tahoe的工作机制是:当网络连接启动时,cwnd=1 segment,ssthresh
=65535 bytes。每收到一个ACK,cwnd就会增加,而增加的方式有2种方法:Slow Start及Congestion Avoidance。进入Slow Start或Congestion Avoidance是由cwnd是否超过ssthresh來判断,若cwnd
Jacobson(1990)等人在Tahoe TCP的基础上加入了快速恢复形成了RenoTCP算法Reno=Slow Start+Congestion Avoidance+Fast Retransmit+Fast Recovery。快速恢复算法的目的是在快速重传之后提高TCP算法的吞量。NewReno TCP(1996年,Fall和Floy在Reno的基础上提出了New Reno)算法是Reno TCP算法的基础上对快速恢复算法进行修改,添加了恢复应答判断功能,以增强TCP终端通过ACK报文信息分析报文传输状况的能力。NewReno TCP算法使TCP终端可以把一次拥塞丢失多个报文的情形与多次拥塞的情形区分开来,进而在每一次拥塞发生后拥塞窗口只减半一次,从而提高了TCP的顽健性和吞吐量。[12]
(三)TCP-SACK
SACK TCP(1996年,Mathis、Mahdavi、Floy和Romanow提出了Reno的另一变形:SACK)算法也是在Reno TCP算法的基础上增加了选择确认SACK和选择重传功能。SACK的基本思想是接受方TCP发送SACK分组来通知发送方接受数据的情况,这样发送方只重传丢失的分组。SACK在进入快速重传状态时,如果网络中的所有分组已经得到确认,那就会退出快速重传状态。
(四)TCP Vegas
L S Brakmo(1996)等提出了一种新的拥塞控制算法TCP Vegas。即“选择性重复”(selective repeat)策略。Vegas对Reno进行了三项重要的技术改进:(1)采用了新的重传触发机制,即用一个重复ACK(而非Reno中的3个)来启动超时判定规程,这样可以更及时地检测到拥塞的发生;(2)在慢启动阶段采用了更加谨慎的方式来增加窗口大小,减少了不必要的分组丢失;(3)改进“拥塞避免”阶段的窗口调整法。[6]
四、结束语
随着TCP拥塞控制研究的深入,已经有相当完善的拥塞控制算法理论,许多学者在文献[2][3][4]基础上对TCP拥塞控制进行深入研究,提出把系统控制理论引进拥塞控制,对TCP连接的公平性、建模等方面对TCP进行了扩展和改良。文献[13][14]等提出改进“慢启动”算法、用数学建模方式、优化理论来解决网络拥塞和算法组合策略;文献[15][16]等对最新TCP拥塞控制算法最新研究动态作了较好的分析总结,把线性规划、资源分配、竞争机制理论引入算法思想;文献[10]等对TCP拥塞控制在特殊网络中(高速网络、无线网络)进行深入的研究,并对TCP拥塞法进一步改良和组合、完善利用NS2仿真模型做了一些有意义数据和案例,为研究拥塞控制算法作了重要工作。总之,TCP拥塞控制算法还在不断发展中,将来会有更加完善的算法运用到实践中,由于作者水平有限,文中不足之处,恳请批评指正!
参考文献:
[1]Tanenbaum A S.Co mputer letworks.The third edition.B Pret.ice HalI.1996,374-378.
[2]Jacobson Congestion avoidance and contro1.ACM Co mputer Co mmunication Review,1988,18(4):314-329.
[3]Jacobson v.Co ngestion Avoidance and Co ntro1.IEEE/ACM Transaction Networking,1998,6(3):314-329.
[4]Gevros P,Crowcroft J,Kirstein P,et a1.Co ngestion contromechanisms and the best effort service mode1.IEEE Network,2001,15(3):16-26.
[5]Steves W.TCP S1ows Start,Co ngestion Avoidance,Fast Retransmit,and Fast Recovery Algorithms.RFC2001,1997.
[6]刘拥民、蒋新华、年晓红等,Internet端到端拥塞控制研究综[J].计算机科学,2008,Vo1.35№.2:6-12.
[7]Meom C.A new approach to model the stationary behavior ofTCP Co nnections.IEEE Co mputer Society,2000.
[8]Jain,R.Ramakrishnan,K.K.Chiu,Dah-Ming.Congestion avoidance in computer networks with a connectionless network layer.Technical Report,DEC-TR-506,Digital Equipment Corporation,1988.
[9]Floyd,S.Fall,K.Promoting the use of end-to-end congestion controlin theInternet.IEEE/ACMTransactionsonNetworking,1999,7(4):458-472.
[10]http://www.cs.nctu.edu.tw/-cmtsai/cgi-bin/wiki.pl?action=bro
wse;diff=2;id=TCP_Tahoe.Comments on TCP_Tahoe.
[11]章淼、吴建平、林闯,互联网端到端拥塞控制研究综述[J].软件学报,2002,Vol.13,No.3:354-363.
[12]封宁、白光伟,TCP拥塞控制算法的组合策略研究[J].微计算机信息(管控一体化),2009,第25卷,第4-3期:159-161.
[13]曹雪峰,TCP拥塞控制算法建模分析[J].现代计算机(总第二九九期)2009.1:120-122.
[14]马义忠、司颖、窦战伟,基于接收驱动的拥塞控制算法分析[J].计算机工程,2009.02,第35卷,第4期:119-124.
[15]何炎祥、熊乃学、杨燕,一种改进的TCP拥塞控制算法[J].计算机研究与发展,2005,42(12):2070-2076.
[16]贺婷婷、谢高岗、张广兴等,802.11无线接入TCP连接本地延迟抖动的理论模型[J].计算机应用研究,2009.01,第26卷,第1期:272-279.
[17]Audrew S.Tanenbaum著,潘爱民译,计算机网络(第四版)[M].北京:清华大学出版社,2004:256-271.
作者简介:
刘国栋(1980-),广东河源人,中山大学信息科学与技术学院计算机科学系2008级计算机软件与理论硕士研究生,任职于广州南洋理工职业学院,主要从事计算机教学工作。