TCP协议的拥塞控制策略及改进
摘 要:TCP是针对固定网络设计的一种传输协议,其错误控制机制是基于将所有丢包原因都归结于网络拥塞的假设。这种错误控制机制在有线网络上获得了很大的成功;但由于移动计算环境有着明显不同于有线网络环境的特点,如较高的位出错率、可用带宽小、衰减信道等,因此针对传统有线网络设计的TCP协议,其性能受到了很大影响。本文对目前移动计算环境下TCP协议的一些主要改进方案进行了综述,在对这些方案进行分类的基础上,对其优缺点进行了分析,并且对这些方案进行了比较。最后,提出了进一步研究的方向。
要害词:TCP, 移动计算,无线网络,错误控制
1. 引言
互联网最初源于美国国防部的ARPANET计划。在上世纪60年代中期,正是冷战的高峰,美国国防部希望有一个命令和控制网络能够在核战争的条件下幸免于难,而传统的电路交换的电话网络则显得太脆弱。国防部指定其下属的高级研究计划局(ARPA)解决这个问题,此后诞生的一个新型网络便称为ARPANET,其最大特点是采用无连接的端到端包交换服务。随后ARPANET开始与美国国家科学基金会(NSF)建成的NSFNET及加拿大、欧洲和太平洋地区的网络互联。到了80年代中期,人们开始把互联的网络称为互联网。
早在70年代中期,ARPA为了实现异种网络之间的互联与互通,推出了TCP/ip体系结构和协议规范。时至今日,TCP/IP协议也成为最流行的网际互联协议,并由单纯的TCP/IP协议发展成为一系列以IP为基础的TCP/IP协议簇。TCP/IP协议簇为互联网提供了基本的通信机制。
互联网采用的是无连接的端到端数据包交换,提供“尽力而为”(best effort)服务模型的设计机制。这种机制的最大优势是设计简单,可扩展性强。互联网在过去的十几年中经历了爆炸式的增长,这已经充分证实了这种设计机制的成功。然而这种优势并不是没有代价的,随着互联网用户数量的膨胀,网络的拥塞问题也越来越严重。例如由于队列溢出,互联网路由器会丢弃约10%的数据包。据统计,互联网上95%的数据流使用的是TCP/IP协议,因此,互联网上主要的互连协议TCP/IP的拥塞控制(congestion control)机制对控制网络拥塞具有非凡重要的意义。拥塞控制是确保互联网鲁棒性(robustness)的要害因素,也是各种治理控制机制和应用(如多媒体通信中QoS控制、区分服务(differentiated services))的基础,因此关于互联网的拥塞控制问题一直是网络研究的一个热点。
TCP是目前Internet上使用最广泛的一种传输协议,根据MCI的统计,Internet上总字节数的95%及总数据包数的90%使用TCP协议传输[25]。TCP的目的是为了解决Internet的稳定性、异质性(接受端缓冲区大小、网络带宽及延迟等)、各流之间享用带宽的公平性、使用效率及拥塞控制等问题,从而为Internet提供可靠、健壮(robust)的端到端通讯。Internet近十年来的迅猛发展已证实TCP协议在设计上是成功的。
但是,TCP是为固定主机及有线网络设计的一种滑动窗口协议,它在位出错率(bit rate error,BER)很低、丢包的主要原因是网络拥塞的传统网络上的成功在移动计算环境下受到了巨大的挑战。移动计算带来的新问题主要是无线链路传输的可靠性、移动操作的特点以及对效率进行评估的性能尺度等。因此,对TCP协议的改进已经成为近几年网络通讯领域的一个研究热点。
本文第二部分对网络拥塞的基本概念进行了简要介绍;第三部分TCP的拥塞控制机制及有线网络环境下的改进进行了介绍;第四部分分析了TCP在移动计算环境下的缺点及其需要增加的功能;第五部分对增强移动环境下TCP的技术方案进行了分类介绍,分析了各自的优缺点,并对这些方案进行了比较。最后进行了总结,并提出了有待进一步研究的一些热点方向。
2. 网络拥塞的基本概念
2.1 拥塞的基本概念和互联网模型
当网络中存在过多的数据包时,网络的性能就会下降,这种现象称为拥塞。在网络发生拥塞时,会导致吞吐量下降,严重时会发生“拥塞崩溃”(congestion collapse)现象。一般来说,拥塞崩溃发生在网络负载的增加导致网络效率的降低的时候。最初观察到这种现象是在1986年10月,在这个过程中,LBL与UC Berkeley之间的吞吐量从32kbps下降到了40bps。Floyd总结出拥塞崩溃主要包括以下几种:传统的崩溃、未传送数据包导致的崩溃、由于数据包分段造成的崩溃、日益增长的控制信息流造成的崩溃等。
图1:网络负载与吞吐量及响应时间的关系
对于拥塞现象,我们可以进一步用图1来描述。当网络负载较小时,吞吐量基本上随着负载的增长而增长,呈线性关系,响应时间增长缓慢。当负载达到网络容量时,吞吐量呈现出缓慢增长,而响应时间急剧增加,这一点称为Knee。假如负载继续增加,路由器开始丢包,当负载超过一定量时,吞吐量开始急剧下降,这一点称为Cliff。拥塞控制机制实际上包含拥塞避免(congestion avoidance)和拥塞控制(congestion control)两种策略。前者的目的是使网络运行在Knee四周,避免拥塞的发生;而后者则是使得网络运行在Cliff的左侧区域。前者是一种“预防”措施,维持网络的高吞吐量、低延迟状态,避免进入拥塞;后者是一种“恢复”措施,使网络从拥塞中恢复过来,进入正常的运行状态。
拥塞现象的发生和前面提到的互联网的设计机制有着密切关系,我们对这种设计机制作一个简单的归纳:
数据包交换(packet switched)网络:与电路交换(circuit switched)网络相比,由于包交换网络对资源的利用是基于统计复用(statistical multiplexing)的,因此提高了资源的利用效率。但在基于统计复用的情况下,很难保证用户的服务质量(quality of service,QoS),并且很轻易出现数据包“乱序”的现象,对乱序数据包的处理会大大增加拥塞控制的复杂性。
无连接(connectionless)网络:互联网的节点之间在发送数据之前不需要建立连接,从而简化了网络的设计,网络的中间节点上无需保留和连接有关的状态信息。但无连接模型很难引入接纳控制(admission control),在用户需求大于网络资源时难以保证服务质量;此外,由于对数据发送源的追踪能力很差,给网络安全带来了隐患;无连接也是网络中出现乱序数据包的主要原因。
“尽力而为”的服务模型:不对网络中传输的数据提供服务质量保证。在这种服务模型下,所有的业务流被“一视同仁”地公平地竞争网络资源,路由器对所有的数据包都采用先来先处理(First Come First Service,FCFS)的工作方式,它尽最大努力将数据包包送达目的地。但对数据包传递的可靠性、延迟等不能提供任何保证。这很适合Email、FTP、WWW等业务。但随着互联网的飞速发展,IP业务也得到了快速增长和多样化。非凡是随着多媒体业务的兴起,计算机已经不是单纯的处理数据的工具。这对互联网也就相应地提出了更高的要求。对那些有带宽、延迟、延迟抖动等非凡要求的应用来说,现有的“尽力而为”服务显然是不够的。
2.2 拥塞产生的原因
拥塞发生的主要原因在于网络能够提供的资源不足以满足用户的需求,这些资源包括缓存空间、链路带宽容量和中间节点的处理能力。由于互联网的设计机制导致其缺乏“接纳控制”能力,因此在网络资源不足时不能限制用户数量,而只能靠降低服务质量来继续为用户服务,也就是“尽力而为”的服务。
图2(a) 图2(b)
拥塞虽然是由于网络资源的稀缺引起的,但单纯增加资源并不能避免拥塞的发生。例如增加缓存空间到一定程度时,只会加重拥塞,而不是减轻拥塞,这是因为当数据包经过长时间排队完成转发时,它们很可能早已超时,从而引起源端超时重发,而这些数据包还会继续传输到下一路由器,从而浪费网络资源,加重网络拥塞。事实上,缓存空间不足导致的丢包更多的是拥塞的“症状”而非原因。另外,增加链路带宽及提高处理能力也不能解决拥塞问题,例如,图2(a)中,四个节点之间的链路带宽都是19.2kbps,传输某个文件需要用时5分钟;当第一个节点和第二个节点之间的链路带宽提高到1Mbps时(如图2(b)所示),传输完该文件所需时间反而大大增加到了7个小时!这是因为在路由器R1中,数据包的到达速率远远大于转发的速率,从而导致大量数据包被丢弃,源端的发送速度被抑止,从而使得传输时间大大增加。即使所有链路具有同样大的带宽也不能解决拥塞问题,例如图3中,
所有链路带宽都是1Gbps,假如A和B同时向C以1Gbps的速率发送数据,则路由器R的输入速率为2Gbps,而输出速率只能为1Gbps,从而产生拥塞。
单纯地增加网络资源之所以不能解决拥塞问题,是因为拥塞本身是一个动态问题,它不可能只靠静态的方案来解决,而需要协议能够在网络出现拥塞时保护网络的正常运行。目前对互联网进行的拥塞控制主要是依靠在源端执行的基于窗口的TCP拥塞控制机制。网络本身对拥塞控制所起的作用较小,但近几年这方面的研究已经成了一个新的热点。
3. TCP拥塞控制及其改进
3.1 TCP拥塞控制机制介绍
基于源端的拥塞控制策略中,使用最为广泛的是TCP协议中的拥塞控制策略,TCP协议是目前互联网中使用最为广泛的传输协议。根据MCI的统计,互联网上总字节数的95%及总数据包数的90%使用TCP协议传输。
早期的TCP协议只有基于窗口的流控制(flow control)机制而没有拥塞控制机制,因而易导致网络拥塞。1988年Jacobson针对TCP在网络拥塞控制方面的不足,提出了“慢启动”(Slow Start)和“拥塞避免”(Congestion Avoidance)算法。1990年出现的TCP Reno版本增加了“快速重传 ”(Fast Retransmit)、“快速恢复”(Fast Recovery)算法,避免了网络拥塞不严重时采用“慢启动”算法而造成过度减小发送窗口尺寸的现象,这样TCP的拥塞控制就主要由这4个核心算法组成。
TCP协议的目的是为上层应用提供可靠的服务,其主要特征在于:
确保各流享用带宽的公平性。
动态发现当前可利用的带宽。
拥塞避免及控制机制以避免拥塞崩溃(congestion collapse)的发生。
标准版本的TCP使用基于窗口的的和式增加积式减小(Additive Increase Multiplicative Decrease,AIMD)方式控制发送速率,以保证稳定性及带宽享用的公平性。
错误控制机制是一个可靠传输协议的要害部分。它对协议的性能有很大的影响,包括吞吐量、能量消耗及可靠性。错误控制通常包括错误检测和错误恢复两部分。为了保证数据传输的可靠性,TCP要求接受端在正确接收到数据段(data segment)后向发送端发送一个确认包,确认包中包含了期望接收到的下一个数据段的序号。TCP发送端通过监测确认包的序号来检测是否发生了错误。假如发生超时或者发送端收到一定数量(通常是3个)重复的确认包,则认为传输过程中发生了错误,数据段被丢弃。由于有线网络的位出错率很低(例如光纤的BER通常只有10-12[22]),因此TCP假设丢包是由于网络拥塞引起的。在错误恢复处理过程中,TCP重传丢弃的数据段、减小发送端窗口大小并且在超时情况下重置超时时钟。
最初的TCP协议只有基于窗口的流控制(flow control)机制而没有拥塞控制机制。流控制作为接受方治理发送方发送数据的方式,用来防止接受方可用的数据缓存空间的溢出。流控制是一种局部控制机制,其参与者仅仅是发送方和接收方,它只考虑了接收端的接收能力,而没有考虑到网络的传输能力;而拥塞控制则注重于整体,其考虑的是整个网络的传输能力,是一种全局控制机制。正因为流控制的这种局限性,从而导致了拥塞崩溃现象的发生。
1986年初,Jacobson开发了现在在TCP应用中的拥塞控制机制。运行在端节点主机中的这些机制使得TCP连接在网络发生拥塞时回退(back off),也就是说TCP源端会对网络发出的拥塞指示(congestion notification)(例如丢包、重复的ACK等)作出响应。1988年Jacobson针对TCP在控制网络拥塞方面的不足,提出了“慢启动”(Slow Start)和“拥塞避免”(Congestion Avoidance)算法。1990年出现的TCP Reno版本增加了“快速重传 ”(Fast Retransmit)、“快速恢复”(Fast Recovery)算法,避免了网络拥塞不严重时采用“慢启动”算法而造成过大地减小发送窗口尺寸的现象,这样TCP的拥塞控制就由这4个核心部分组成。近几年又出现TCP的改进版本如NewReno和选择性应答(selective acknowledgement,SACK)等。正是这些拥塞控制机制防止了今天网络的拥塞崩溃。
TCP拥塞控制四个主要过程(如图4(a)和(b)所示)简要介绍如下:
慢启动阶段:早期开发的TCP应用在启动一个连接时会向网络中发送大量的数据包,这样很轻易导致路由器缓存空间耗尽,网络发生拥塞,使得TCP连接的吞吐量急剧下降。由于TCP源端无法知道网络资源当前的利用状况,因此新建立的TCP连接不能一开始就发送大量数据,而只能逐步增加每次发送的数据量,以避免上述现象的发生。具体地说,当建立新的TCP连接时,拥塞窗口(congestion window,cwnd)初始化为一个数据包大小。源端按cwnd大小发送数据,每收到一个ACK确认,cwnd就增加一个数据包发送量,这样cwnd就将随着回路响应时间(Round Trip Time,RTT)呈指数增长,源端向网络发送的数据量将急剧增加。事实上,慢启动一点也不慢,要达到每RTT发送W个数据包所需时间仅为RTT×logW。由于在发生拥塞时,拥塞窗口会减半或降到1,因此慢启动确保了源端的发送速率最多是链路带宽的两倍。
拥塞避免阶段:假如TCP源端发现超时或收到3个相同ACK副本时,即认为网络发生了拥塞(主要因为由传输引起的数据包损坏和丢失的概率很小(ssthresh,TCP就执行拥塞避免算法,此时,cwnd在每次收到一个ACK时只增加1/cwnd个数据包,这样,在一个RTT内,cwnd将增加1,所以在拥塞避免阶段,cwnd不是呈指数增长,而是线性增长。
快速重传和快速恢复阶段:快速重传是当TCP源端收到到三个相同的ACK副本时,即认为有数据包丢失,则源端重传丢失的数据包,而不必等待RTO超时。同时将ssthresh设置为当前cwnd值的一半,并且将cwnd减为原先的一半。快速恢复是基于“管道”模型(pipe model)的“数据包守恒”的原则(conservation of packets PRinciple),即同一时刻在网络中传输的数据包数量是恒定的,只有当“旧”数据包离开网络后,才能发送“新”数据包进入网络。假如发送方收到一个重复的ACK,则认为已经有一个数据包离开了网络,于是将拥塞窗口加1。假如“数据包守恒”原则能够得到严格遵守,那么网络中将很少会发生拥塞;本质上,拥塞控制的目的就是找到违反该原则的地方并进行修正。
图4(a):慢启动和拥塞避免
图4(b):快速重传和快速恢复
经过十多年的发展,目前TCP协议主要包含有四个版本:TCP Tahoe、TCP Reno、TCP NewReno和TCP SACK。TCP Tahoe是早期的TCP版本,它包括了3个最基本的拥塞控制算法-“慢启动”、“拥塞避免”和“快速重传”。TCP Reno在TCP Tahoe基础上增加了“快速恢复”算法。TCP NewReno对TCP Reno中的“快速恢复”算法进行了修正,它考虑了一个发送窗口内多个数据包丢失的情况。在Reno版中,发送端收到一个新的ACK后旧退出“快速恢复”阶段,而在NewReno版中,只有当所有的数据包都被确认后才退出“快速恢复”阶段。TCP SACK关注的也是一个窗口内多个数据包丢失的情况,它避免了之前版本的TCP重传一个窗口内所有数据包的情况,包括那些已经被接收端正确接收的数据包,而只是重传那些被丢弃的数据包。
另外,在1994年,L.S.Brakmo等提出了一种新的拥塞控制策略-TCP Vegas。由于RTT值与网络运行情况有密切关系,因此,TCP Vegas通过观察TCP连接中RTT值改变感知网络是否发生拥塞,从而控制拥塞窗口大小。假如发现RTT值变大,Vegas就认为网络正在发生拥塞,于是开始减小拥塞窗口;另一方面,假如RTT变小,Vegas就认为网络拥塞正在解除,于是再次增加拥塞窗口。这样,拥塞窗口在理想情况下就会稳定在一个合适的值上。TCP Vegas的最大优点在于拥塞机制的触发只与RTT的改变有关,而与包的具体传输时延无关。由于TCP Vegas不是利用丢包来判定网络可用带宽,而是以RTT的变化来判定,因此能更精确地猜测网络的可利用带宽,其公平性、效率都较好。但TCP Vegas之所以未能在互联网上大规模使用,主要是因为使用TCP Vegas的流在带宽竞争能力方面不及未使用TCP Vegas的流,从而导致网络资源享用不公平,而不是算法本身的问题。
3.2 拥塞控制的主要问题
拥塞控制的问题主要集中在效率和公平性(fairness)上。网络资源的使用效率是指源端要求的总资源与网络所能提供的资源之间的关系。假如二者刚好相等或者很接近,那么这种算法的效率就是高的,否则都是效率不高的表现。
公平性是指在网络发生拥塞时各连接能公平地共享网络资源。产生公平性的根本原因在于拥塞发生必然导致数据包丢失,而数据包丢失会导致各数据流之间为争抢有限的网络资源发生竞争,竞争能力强的数据流将到更多网络资源,从而损害了其他流的利益。所以说没有拥塞,也就没有公平性问题。公平性问题表现在两方面:一是拥塞响应的TCP流和非拥塞响应的UDP流之间资源享用不公平;二是TCP流之间资源享用的不公平。前者主要是在发生拥塞时对拥塞指示作出的不同反应造成的。由于TCP流具有拥塞控制机制,在收到拥塞指示后,源端会主动降低发送速率;而UDP流由于没有端到端的拥塞控制机制,因此在收到拥塞指示后,UDP不会降低数据发送速率。结果在网络拥塞时,拥塞适应的TCP流得到的资源越来越少,非拥塞适应的UDP得到的资源越来越多,从而导致了网络资源分配的不公平。网络资源分配的不公平反过来会加重拥塞情况,甚至可能导致拥塞崩溃。对于第二个不公平性问题,研究表明,不同的窗口大小、RTT值及数据包的尺寸都会影响TCP流对带宽的占用。窗口较大,或者RTT较小,或者数据包较大的流往往能占用更多的带宽。
3.3 有线网络中TCP拥塞控制机制的改进
3.3.1 针对对不必要的超时重传和快速重传
我们知道,当前的TCP应用主要有两种重传机制-快速重传和超时重传。当TCP源端收到3个ACK副本时,就会触发快速重传机制,此时源端重传丢失的数据包并且将拥塞窗口大小减半。这种情况下,TCP流往往能够很快从丢包中恢复过来,重新回到原先的发送速率。但假如TCP源端没有收到3个ACK副本,例如拥塞窗口大小小于4,那么TCP源端则需要等待相当长时间,以便超时重发。这样,小窗口的TCP流就很轻易陷入不必要的超时重发,使其吞吐量大大下降。
为了避免这种不必要的超时重传,一种改进办法就是只要TCP源端收到一个或者两个ACK副本,并且假如通告窗口答应,便继续发送新的数据包。这是因为只要收到ACK副本,就表明有数据包已经离开网络被接受端接收了,而此时源端还无法判定数据包是否被丢弃,根据“数据包守恒”原则,只要遵守拥塞窗口的规范,也即同时在网络中传送的数据包数量不能超过拥塞窗口的大小(以数据包为单位),源端就可以继续发送新的数据包。这种机制称为限制传输机制(Limited Transmit mechanism),这种机制对排序的数据包尤其有效。
限制传输机制可以使小窗口的TCP流很快从丢包中恢复过来。例如,对于拥塞窗口大小为4地TCP流,假如其第二个数据包丢失,那么按传统地做法需要等待超时重传。而在限制传输机制下,当源端收到对第三个数据包确认的ACK副本时(ACK中要求源端发送第二个数据包),继续发送新的数据包,最终源端可以收到三个ACK副本从而触发快速重传,从而减少了不必要的超时重传。
3.3.2 针对乱序包和延迟包引起的重传
在不少情况下,TCP源端推断认为数据包被丢弃了,从而导致重传及拥塞窗口的减小,而实际上数据包并没有被丢弃。假如超时时钟过早地到时了(事实上数据包或者ACK并没有丢失,只要能够再等待一会儿并可收到ACK),源端便毫无必要地重发了数据包,更严重的是拥塞窗口的减小,而实际上并没有数据包被丢弃。类似地,假如由于数据包的乱序导致源端接收到3个ACK副本,便会导致快速重传,TCP源端也毫无必要地重发了数据包,并且减小了拥塞窗口。对于前者,虽然可以通过更为精确地调节超时时钟来减少不必要地超时重传,但要完全避免却是不可能的。同样,对于后者,虽然可以通过提高快速重传算法的性能来减少不必要的快速重传,但也不可能完全避免。
对于拥塞窗口较大的流,比如大小为W,不必要地减小拥塞窗口会导致其至少花费W/2 RTT时间恢复到原来拥塞窗口的大小,从而使其性能大大下降,非凡是在数据包持续出现乱序或者对RTT的估算不很精确的情况下。持续乱序的数据包往往是由于路由的改变或者链路层重传受损的数据包引起的。
为了使得在出现不必要的超时重传和快速重传情况下,TCP性能能够更加健壮(robust),一种方法就是在出现这些情况时向TCP源端发送有关的信息。这个工作已经由D-SACK扩展(duplicate-SACK extension)完成了。D-SACK扩展答应TCP接受端在利用SACK选项来通报收到重复的数据包,从而TCP源端能够正确地推断出接受端是否收到了重复地数据包。因此,D-SACK扩展使得TCP源端在重发后一个RTT时间内正确地推断出重发是否必要。假如源端认为重发是不必要的,那么拥塞窗口减半也就没必要了,源端就会将拥塞窗口大小和慢启动阈值分别恢复到原来的值,这样拥塞窗口恢复到原来的大小只需1RTT时间而不是W/2 RTT时间了。
3.3.3一种新的拥塞控制机制XCP
针对目前基于窗口的TCP拥塞控制机制的不足,最近MIT的D.Katabi、C.Rohrs和UC Berkeley的M.Handley共同提出了一种新的互联网拥塞控制机制XCP(eXPlicit Control Protocol)。XCP源端维持有拥塞窗口cwnd和回路响应时间RTT并且通过数据包中的拥塞头(congestion header)将这两个值与路由器进行通信。当XCP连接刚刚建立时,与TCP一样,初始cwnd较小,XCP将其理想的发送速率填入到拥塞头中,假如链路带宽答应,则在一个RTT后就以次速率发送数据;假如链路带宽不足,则网络会给出一个发送速率,在一个RTT后源端就以此速率发送数据。
在随后的数据包传输过程中,根据数据流入速率和链路带宽之间的关系,路由器通知每个流是要增加还是减少拥塞窗口并将有关信息填入到拥塞头中。假如在后面的传输过程中,有路由器拥塞更加严重,则该路由器将拥塞头中的有关信息改写。最终该数据包将获得传输过程中的瓶颈链路信息,并将传送给接收端。接收端再将次信息写入到确认包中传送给源端,源端依此信息对拥塞窗口进行调整。通过将拥塞状态信息放入数据包中,XCP无需路由器维持每流状态信息,扩展性较好。
实验表明,与传统的TCP拥塞控制机制相比,XCP具有链路利用效率高、公平性好、可扩展性强、排队时延小的优点,并且路由器的开销也非常小。但XCP最终能否被标准化作为下一代互联网的传输协议我们将拭目以待。
作者:姜明
(未完待续)