拥塞控制机制包括哪个技术 拥塞控制机制算法介绍【详解】

拥塞控制机制包括哪个技术 拥塞控制机制算法介绍【详解】

  拥塞控制机制是什么意思

  拥塞是当多个用户竞争访问相同的资源(带宽、缓冲区和队列)时发生在共享网络上的问题。就像高速公路发生的拥塞,很多车辆进入高速公路而不考虑即将发生或已经发生的拥塞,随着越来越多的车辆进入高速公路,拥塞会变得越来越严重。最后,斜坡上的车辆可能后退下滑,从根本上阻止车辆上去。

  在数据分组交换网络中,数据分组在通过网络时,在交换设备的缓冲区和队列中移入和移出。实际上,数据分组交换网络通常称作“队列网络”。数据分组交换网络的特征是数据分组可能从一个或多个源成群到达。缓冲区帮助路由器吸收突发数据分组,直到它们可以自己解决这些数据分组为止。如果业务流量过大,则缓冲区被占满并且新来的数据分组被丢弃。增加缓冲区的大小不是解决办法,因为过大的缓冲区会导致过大的延迟。

  拥塞通常发生在多个链路向单个链路填入数据分组时,如内部LAN被连接到WAN链路时。拥塞也发生在核心网络的路由器上,其中节点承受的业务流量超过其设计所能处理的业务流量。TCP/IP网络(如因特网)尤其易于发生拥塞,因为其具有基本的无连接的性质,虚电路的带宽没有保证。数据分组在任意时间由任意主机发送,并且这些数据分组大小可变,这就使得预测业务流量模式和提供有保证的服务变得不太可能。而无连接网络也有优点,除了服务质量以外。

  下列基本技术用于管理拥塞。

  端系统流控制 这不是一个拥塞控制方案,而是一个阻止发送方使接收方缓冲区溢出的方法。流控制是由接收实体执行的一种功能,用以限制传输实体所发送的数据量或速率。最简单的流控制就是停止等待过程,此时在下一个PDU发送之前,所有PDU必须被确认。效率更高的协议则涉及到向发送器提供的某种形式的信用关系,就是说在没有收到确认之前能够发送的数据量。HDLC滑动窗口技术就是这种机制的一个例子。

  网络拥塞控制 网络拥塞指的是在包交换网络中由于传送的包数目太多,而存贮转发节点的资源有限而造成网络传输性能下降的情况。拥塞的一种极端情况是死锁(Deadlock),退出死锁往往需要网络复位操作。在本方案中,端系统减小流量以避免网络拥塞。该机制类似于端对端流控制,但目的是减少网络中而不是接收方的拥塞。

  基于网络的拥塞避免 在本方案中,路由器检测可能发生的拥塞并尝试在队列变满之前减慢发送方的发送。

  资源分配 本技术包括安排物理电路或其他资源的使用,或许是对于某特定时间段。建立虚电路,以有保证的带宽通过一系列交换机,是资源分配的一种形式。这种难度技术很大,但是可以通过阻止超过网络容量的通信量来消除网络拥塞。相关主题的列表在本主题结尾处给出。

  高速缓存可能是最终的拥塞控制方案。通过将内容移近用户,大量的通信可以从本地获得,而不必沿着可能发生拥塞的路由路径从远程服务器上获得。高速缓存成为因特网上的重要事务。

  队列和拥塞

  任何关于拥塞的讨论都要涉及到队列。网络上的缓冲区使用不同的队列技术来管理。适当的管理队列可以使丢失数据分组和网络拥塞最小化,并改进网络性能。

  最基本的技术是FIFO(先进先出),即按报文到达接口的先后顺序让报文进入队列,在队列的出口让报文按进队的顺序出队,先进的报文将先出队,后进的报文将后出队。此外,优先级队列方案使用具有不同优先级的多个队列,以便可以首先发送最重要的数据分组。

  一项重要的队列技术是将数据流分配到它们自己的队列中。这样区分数据流的目的是分配不同的优先级。同样重要的是,每个数据流负责确保它不会溢出自己的队列。这样分离的队列确保每个队列只包含来自单个源的数据分组。

  帧中继中的拥塞控制

  帧中继用户与服务提供商协商CIR(保证信息速率)。CIR是保证的服务级别,但如果网络容量允许,则提供商通常允许用户超出这一级别的突发数据。然而,超出CIR的帧被标记为可丢弃的。如果网络上的交换机发生拥塞,则它将丢失可丢弃的帧。这就确保服务提供商可以满足与用户协商的CIR级别。

  丢弃帧决不是个好办法,所以有两个拥塞避免机制可用:

  BECN(反向显式拥塞通知) 帧中继网络在与数据帧遇到拥塞路径的反方向传输的数据帧中设置的位。交换机开始发生拥塞(如缓冲区/队列已满)时,它可以用BECN位组将一个帧反向发送回发送方,以通知发送方减速。

  FECN(正向显式拥塞通知) 是由来源(发送)终端传输的要求目的地(接收)终端减缓数据要求的请求的首位。交换机开始拥塞时,它可以用FECN位组将一个帧正向发送到接收节点。这就通知接收节点:应该通知发送方减速。

  发送方或接收方不必响应BECN或FECN,但最终网络交换机将由于拥塞继续增长而丢失帧。

  TCP中的拥塞控制和避免

  直到20世纪80年代中期,因特网有出现“拥塞崩溃”的倾向。发生这种现象是因为对于管理大量的网络负载缺乏控制。个别连接在发送方和接收方之间使用数据流控制,以防止发送方发送太多以至接收方无法处理。

  但是这些早期的数据流控制的设计,是为防止接收方的缓冲区溢出而不是网络节点的缓冲区的溢出。然而,早期的因特网包含大量相对较慢的链路,所以拥塞问题不象现今这样严重。

  在20世纪80年代末期,Van Jacobson提出了拥塞控制机制,使TCP响应网络中的拥塞。基本“信号”是丢弃的数据分组,它使主机停止或减速。

  通常,当主机接收一个数据分组(或一组数据分组)时,它发送ACK(确认)给发送方。窗口机制允许主机发送多个数据分组,而只有单个ACK。接收ACK失败表明,接收主机溢出或者网络拥塞。在任一种情况下,发送方都减少或停止发送。

  一个称为加法增加/乘法减少的策略管理一次发送的数据分组的数目。如果将数据流绘成图表,将可看到锯齿状形式,其中,数据分组数目增加(加法增加),直到拥塞发生为止,然后当开始丢弃数据分组时减少(乘法减少)。窗口大小通常在拥塞信号出现时减半。

  主机所做的是通过不断以某个较高的速率测试网络,以找到最佳传输速率。有时,允许较高的传输速率,但是如果网络正忙,开始丢失数据分组,则主机相应的降低速率。这一方案将网络看成是发生拥塞时丢弃数据分组的“黑盒子”。因此,拥塞控制由端系统运行,端系统将丢失数据分组看成是惟一的网络拥塞表示。

  正在传输大文件的发送方将尽量争取更高的速率,直到最后它占用全部带宽。其他主机的数据分组在通过时可能遇到麻烦。经常是,已占用带宽的主机正在进行最不重要的通信。这样的后果对于话音之类的实时通信尤其具有破坏性。即使一个链路具有足够的带宽处理它的负载,但性能不良的主机还是会使该链路饱和(尽管是暂时的),以至于破坏话音通信,使用户无法通话。

  当然,在管理拥塞时网络会起到积极的作用,那就是“主动式队列管理”和拥塞避免开始发挥作用。RFC l254(Gateway Congestion Control Survey, August l991)描述了IETF性能和拥塞控制工作组审查的拥塞控制和避免机制。该工作组将拥塞处理分成下列:

  拥塞恢复 当需求超过容量时,恢复网络的操作状态。

  拥塞避免 预见拥塞并避免它,从而永远不发生拥塞。

  RFC 1254指出,若没有拥塞恢复,因特网将停止操作,但没有拥塞避免,它却已经工作了很长时间。现今,拥塞避免是改进因特网的性能和服务质量的重要方法。

  RFC 2309(Recommendations on Queue Management and Congestion Avoidance in the Internet ,April 1998)指出,用于控制拥塞的基于路由器的机制可以划分为“队列管理”算法和“调度”算法。有关拥塞控制、拥塞避免方案和队列调度技术的有用信息,请参阅本RFC。

  一个重要的目标是使丢失数据分组的数目最小化。如果主机正在以高速传输并且网络发生拥塞,则将丢失大量的数据分组。拥塞避免试图在不限制网络吞吐量的情况下防止数据丢失。RFC 2309指出,最好接受突发使队列溢出这一事实,而不是试图将队列维持在未满状态。这将从根本上变得有利于高吞吐量时较低的端对端延迟。RFC还给出这样的注释:网络中的缓冲区吸收数据突发,并在随后有希望出现的突发空闲期间传输它们。这是允许传输突发数据的本质所在。我们希望路由器中含有正常的小队列的原因很清楚:希望有吸收突发数据的队列容量。与直觉相反的结果是,维持正常的小队列会导致较高的吞吐量,以及较低的端对端延迟。总之,队列限制不应该反映我们希望在网络中维持的稳定状态的队列,相反,它们应该反映我们要吸收的突发数据的多少。

  突发数据会破坏多台主机。如果单个主机填充正由多个主机使用的队列,则所有主机将需要后退。这导致网络在一段时期内未充分使用,因为主机正在以较低的速率发送数据分组。但是最终,出于重新传输丢弃的数据分组的需要,它们开始建立备份。然后发生的是,已经后退的所有主机试图在大约同一时间重新发送,这将再次导致拥塞状态。这被称为“全局同步”问题。

  应当记住,TCP处理拥塞控制。UDP通常用于实时音频和视频流,因为不需要恢复丢失的数据分组。UDP是不可靠的传输协议,不能将ACK信号发送回数据源。由于没有ACK,因此无法用传统的TCP拥塞控制来控制UDP流。

  Lawrence G. Roberts,这位因特网的早期创建者,在1997年发表的名为《Explicit Rate Flow Control,A100 Fold Improvement over TCP》的论文中,对TCP和它的拥塞控制方案进行了有趣的评论。他认为:只要TCP仅在终端站中运行,就无法从本质上改进它的操作。如果不取代TCP,在像因特网这样的长距离网络上,TCP将导致重大的超载和中断。TCP固有的慢启动速度和高延迟变差会严重影响用户。IETF甚至没有考虑修订TCP,实际上,IETF没有进行关于流控制的任何研究,因为似乎每个人都相信“如果它在过去能工作,则它将能继续工作”。必须尽可能快地用与显式速率流控制一样好的新的流控制来代替TCP。

  RFC 2581(TCP Congestion Control,APnll999)定义了TCP的四个相关的拥塞控制算法:慢速启动、拥塞避免、快速重发和快速恢复。下面介绍每个算法。

  慢速启动和拥塞避免算法必须被TCP发送端用来控制正在向网络传送的数据量。为了实现这些算法,必须向TCP每个连接状态加入两个参量。拥塞窗口(cwnd)是对发送端收到确认(ACK)之前能向网络传送的最大数据量的一个发送端限制,接收端通知窗口(rwnd)是对未完成数据量的接收端限制。Cwnd和rwnd的最小值决定了数据传送。另一个状态参量是慢启动阀值(ssthresh),被用来确定是用慢速启动还是用拥塞避免算法来控制数据传送。

  慢速启动拥塞控制当主机首次传输时,慢启动可减少突发影响。它要求主机缓慢的开始传输,然后增大到拥塞开始发生。主机最初并不知道它可以发送的数据分组的数目,所以它使用慢速启动的方式测量网络容量。主机通过将两个数据分组发送到接收方开始传输。当接收方接收到该段数据,它返回ACK(确认)作为确认。发送方将窗口增加到两个并发送四个数据分组。随着发送方加倍发送数据分组,发送量继续增加,直到接收不到ACK为止,这表明数据流到达了网络处理通信的能力极限或者接收方处理接收通信的能力极限。

  慢速启动并不防止拥塞,它只是阻止主机立即进入拥塞状态。如果主机正在发送一个大文件,最终它将到达使网络超载并开始丢失数据分组的状态。慢速启动在避免拥塞崩溃问题上很关键。但新的应用程序,如IP上的话音,不能容忍慢速启动导致的延迟,某些情况下,禁用慢速启动,所以用户可以“抢占”带宽。这种趋势只会导致问题的出现。

  快速重发和快速恢复(Reno) 快速重发和快速恢复是为丢失数据分组对网络吞吐量所造成的影响最小化而设计的算法。快速重发机制从另一个TCP机制推断信息,接收方使用该机制将其已经收到失序数据分组的信号发送到发送方。该技术是将几个重复的ACK发送到发送方。

  快速重发通过假设重复的ACK表示丢失数据分组来利用这一功能。这种方法不是等待ACK直到计时器终止,而是如果收到三个这样的重复ACK,数据源将重新发送数据分组。这发生在超时之前,从而提高了网络吞吐量。例如,如果主机接收到数据分组5和7,但没有6,它将在它收到数据分组7(但没有数据分组6)时发送对于数据分组5的重复ACK。

  在快速重发算法发送了看来已经丢失的数据段之后,“快速恢复”算法支配了新数据的传送,直到一个非重复ACK到达。不进行慢启动的原因是收到重复ACK不仅意味着一个数据段已经丢失,而且意味着数据段非常可能从网络丢失(尽管网络产生大量的重复数据段可以保证不丢失)。换句话说,因为接收端只有在当一个数据段已经到达时才产生一个重复ACK,由此我们可以知道,已经脱离网络,存储在接收端的缓冲区里的数据段不会再消耗网络资源。另外,因为ACK"clock"保存起来了,TCP发送端可以继续发送新的数据段(尽管传送必须继续使用一个减小的cwnd)。

  快速恢复是当使用快速重发时代替慢速启动的机制。注意,尽管重复ACK表示已经丢失一段数据,但它也表示既然数据源收到序列号高于丢失的数据分组的数据分组,则数据分组仍在流动。在这种情况下,假设单个数据分组已经丢失,网络没有完全拥塞,因此,发送方不需要完全降低到慢速启动模式,而是降低到先前速度的一半。

  注意,上述机制称为Reno。RFC 258 (The NewReno Modification to TCP’s Fast Recovery Algorithm,April 1999)描述了对Reno的修改,使其可以覆盖这种情况,即ACK在检测到数据丢失时不能覆盖全部未解决的数据的情况。主动队列管理和拥塞避免丢失数据分组使效率降低。如果主机遇到突发传输和拥塞,将丢失大量数据分组。因此,检测即将发生的拥塞情况并在拥塞失控之前积极进行管理是很有用的。

  主动队列管理是这样一项技术,路由器主动从队列中丢失数据分组,作为通知发送方应该减速的信号。RFC 2309列出了主动队列管理的下列优点:

  突发是不可避免的。保留较小的队列并主动管理队列提高了路由器吸收突发数据分组和不丢失过多数据分组的能力。

  如果数据源使共享队列溢出,则共享该队列的所有设备将减速(“全局同步”问题)。

  从多个丢失的数据分组中恢复要比从单个丢失的数据分组中恢复更困难。

  大队列可能导致延迟。主动队列管理允许队列比较小,这将提高吞吐量。

  当主机填满队列并且防止其他主机使用该队列时,发生封锁。主动队列管理可以防止这种情况发生。

  下面描述几个拥塞避免方案。超越这些技术的下一步包括业务流量调整、资源预留、虚电路和QoS技术。后面还将做更多讨论。

  RED(随机早期丢弃) RED是主动队列管理方案,为拥塞避免提供一种机制。

  与丢失已满队列末尾的数据分组的传统拥塞控制方案不同,RED使用统计方法,在队列溢出之前以“随机”方式丢弃数据分组。以这种方式丢弃数据分组会将数据源的速度降到足够低,以至于当队列溢出以及主机正以高速率传输时,可以保持队列稳定并减少丢失的数据分组数。

  RED作出了两个重要决定。它决定何时丢弃数据分组和丢弃哪些数据分组。RED跟踪平均队列大小,并且当平均队列大小超过已定义的极限值时丢弃数据分组。每当新数据分组到达队列时,重新计算队列的平均值。RED有两个和队列长度相关的阈值:minth和maxth。RED根据minth和maxth作出丢弃数据分组的决定:

  最小极限值(minth) 规定一个在该值以下将不丢弃任何数据分组的平均队列大小。

  最大极限值(maxth) 规定一个在该值以上将丢弃所有数据分组的平均队列大小。

  当有包达到路由器时,RED计算出平均队长avgQ。若avgQ小于minth,则没有包需要丢弃;当minth≤avgQ≤maxth时,计算出概率P,并以此概率丢弃包;当avgQ>maxth时,所有的包都被丢弃。由于RED使用的是基于时间的平均队长,就有可能会发生实际队长大于平均队长的情况,如果队列已满,则到达的包只能被丢弃。

  计算概率P的方法如下:

  Pb = maxp×(avgQ-minth) / (maxth-minth)   P = Pb / (1-count×Pb)

  P不仅和avgQ有关,而且还和从上一次丢包开始到现在进入队列的包的数量count有关。随着count的增加,下一个包被丢弃的可能性也在缓慢增加。这主要是为了在到来的包之间均匀间隔地丢包,避免连续丢包,从而避免对突发流的偏见和产生全局同步现象。

  RED使用时间平均法,即如果最近队列通常是空的,则RED将不会像对主要拥塞事件那样对付意外突发。然而,如果队列保持接近全满的状态,则RED将假设拥塞并开始以较高的速率丢弃数据分组。

  RFC 2309论述到因特网上的主动队列管理机制具有大量的性能优点并且使用RED算法似乎没有缺点。

  WRED(加权RED)是基于通信类型、通信目的地或其他因素决定丢弃数据分组的技术。WRED也根据网络外数据分组的标记丢弃数据分组。

  ECN(显式拥塞通知) 在RED机制中,当平均队长超过一定的阈值时便开始丢包了,也就是说RED是在队列未满的情况下丢包的,并不是由于队列溢出而被迫丢包的。在这种情况下丢包,虽然使得RED有效地管理了平均队长,但也浪费了网络资源,并且对时延有一定要求地多媒体应用不是很理想。更有效的技术是路由器在数据分组中设置拥塞通知位,再将该数据分组发送到接收方。然后,接收方可以通过ACK中的消息通知发送方减速。这样接收方将一直收到它的数据分组,而且可以避免使用数据分组丢弃的方法来发送拥塞信号。

  ECN是采用了这项技术的端对端拥塞避免机制。正如其名称所暗示的那样,ECN提供直接的拥塞通知,而不是通过丢弃数据分组间接发送拥塞信号。ECN在中等程度的拥塞时起作用。当拥塞过分严重时,就采用数据分组丢弃技术。

  ECN需要在IP包头设置一个两位(bit)的ECN域,一个是ECT(ECN-Capable Transport)位,由源端设置以显示源端节点的传输协议是支持ECN的;另一个是CE( Congestion Experienced )位,由路由器设置,以显示是否发生了拥塞。

  当队列长度超过某个极限值时,启用ECN的路由器在来自可用ECN的主机的数据分组的包头中设置CD(遭遇拥塞)位。数据分组转发给接收方,然后接收方向发送方发送一个包含拥塞指示符的ACK。这个ACK称为ECN-Echo。当发送方收到这个显式信号时,它将发送数据分组的速率降低到原来的一半。

  注意,ECN要求修改TCP。在RFC 2481(Aproposal ADD Explicit Congestion Notification to IP,January 1999)中描述ECN。

  TCP速率控制 TCP速率控制是这样一项技术,端点可以根据那些执行速率控制的网络设备的反馈来调整自己的传输。

  TCP速率控制也称为ERC(显式速率控制)。ERC的一种形式在ATM网络中使用。

  Packeteer公司的PacketShaper保存关于各个TCP连接的状态信息。这允许它将反馈发送到控制其性能的数据源。主要目的是通过平滑数据源的传输速率控制突发。随着突发的减少,业务流量管理变得更容易。

  在端系统间的网络内执行速率控制进程。PacketShaper截获来自接收方的ACK并保留一段时间,这段时间经过精确计算,以便发送方可以用消除突发的方式传输它的下一个数据分组。

  例如,数据源将数据分组发送到接收方。接收方将ACK返回到发送方。PacketShaper截获ACK并更改某些内部设置,如TCP窗口的大小。恰好这时,PacketShaper发送数据分组和数据分组的内容(ACK序号加上窗口大小)并通知发送方该传输另一个数据分组了。

  结果是,来自源的数据分组稳定流动,并改进了资源管理。不利方面是路由器必须主动跟踪每个数据流。此外,更改传输中的数据分组的内容不是个好方法,这取决于网络。通信量管理和QoS设备执行TCP速率控制。

  其他方案

  上面描述的大多数方案是队列管理方案。如果希望使用这些方案之外的解决方法来管理网络业务流量,则需要考虑优先权方案、数据分组标记方案、虚电路方案和QoS方案。

  拥塞管理资源

  SallyFloyd的Web站点是有关拥塞控制,尤其是拥塞避免的信息的最佳来源之一。IETF端点拥塞管理(ecm)工作组具有有关新拥塞控制方案的信息和评价当前的拥塞控制方案的文档。SallyFloyd撰写了RFC 2914 ( Congestion Control Principles, September2000)。IETF Transport Area (传输区域)工作组(tsvwg)正在制订新的传输规范。

推荐阅读