Chapter1(new)_1_拥塞控制和流量控制

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,Chapter,1,Congestion Control and Flow Control,in Data Networks and Internets,School of Computer,张沪寅,1,Introduction,拥塞发生在通过网络传输的分组数量,开始接近,网络的分组处理能力时。,Objective of congestion control:,目标是将网络中的,分组数量,维持在一定的水平之下，以免发生拥塞。,2,队列理论,(,Queuing Theory,), 数据网络是由一个队列组成的网络。, 如果分组到达的速率,大于等于,分组传输的速率，队列大小就不停地增长且分组经历的时延,(,Delay,),变得越来越长。,If arrival rate ,transmission rate,3,队列理论,(,Queuing Theory,),4,1.1,拥塞的结果,达到饱和点时采用的两种策略：,如果没有缓存空间则,丢弃,进入的,分组, 分组到达太快来不及作路由处理, 分组到达缓存速度快于从缓存输出速率,达到,饱合节点,对,其,相邻节点实施流量控制,措施,可能会导致拥塞扩散到整个网络,参见下页图,5,10.1,拥塞的结果,5,6,1.1,拥塞的结果,1.,理想的性能,(,Ideal Performance,),每个节点有,无限大的缓存,，又不存在与分组传输或拥塞控制相关的额外开销。, 网络吞吐量随着负载的增加而增加，直到供给负载等于网络全部容量，归一化的吞吐量对于更高的输入负载仍保持在,1.0,。,当供给负载等于网络的全部容量时，分组时延增加, 网络能力为吞吐量与时延之比,Power = throughput / delay,吞吐量越大时延越大,7,8,1.1,拥塞的结果,2.,实际的性能,(,Practical Performance,),有限,的缓存，每个分组的处理都有,额外,的,开销, 若不进行拥塞控制，负载的增长会导致网络进入,中等,的拥塞状态；网络吞吐量的增长速率,慢于,负载的增长速度（,A,点）, 负载,不可能均匀,地分布在整个网络上, 网络试图选择,低拥塞,区平衡负载，路由选择产生额外开销降低数据分组的容量, 网上的,负荷进一步增加导致时延增长，最终使吞吐量降到,0,（,B,点）,9,10,1.2,拥塞控制,(,Congestion Control,),1.,反压,(,Backpressure,),请求,源端,减小向,目的,站的数据发送速率,流量限制方向传到各信源，限制新分组进入网络, 选择,流量大的链路采用反压, 用于,逐跳流控,的,面向连接,的网络,2.,阻流分组,(,Choke packet,),网络中的拥塞节点产生的,控制分组,，它被传回源节点以便限制通信量进入网络，要求源端系统减小向目的端系统的数据发送速率,阻流分组的例子：,ICMP,的源站抑制,因,缓存溢出,而丢弃数据包时，可用,源站抑制方法,11,1.2,拥塞控制,(,Congestion Control,),3.,隐式拥塞信令,(,Implicit congestion signaling,),源端通过,传输时延增加,和,分组丢失,检测到拥塞后减少流量。由,端系统,完成，无需其他节点参与,适合无连接或数据报方式的网络,(IP),适合面向连接的网络,(,帧中继网络,LAPF,控制协议,),12,1.2,拥塞控制,(,Congestion Control,),4.,显示拥塞信令,(,Explicit congestion signaling,),网络会对网络中正形成的拥塞向端系统,发出警告,，而端系统则应,采取措施,降低对网络的供给负担。,方向,(,Direction,),：显示拥塞,信令,信号可向,2,个方向传送,反向,(,Backward,),：通知,源站,对与收到分组方向,相反,的流量采取拥塞避免措施。,反向信息：改变数据分组头部某些位，或者是单独发控制分组,前向,(,Forward,),：通知,用户,对与收到分组方向,相同,的流量采取措施，前向信息如上述。端系统可返回源端或上层进行流量控制。,分类,(,Categories,),二进制,(,Binary,),：拥塞节点对转发的数据分组某位置,1,，源站收到降低流量, 基于信用量,(,Credit-based,):,表示,允许源站,发送的,字节数,或,分组数, 基于速率,(,rate-based,),:,在一逻辑连接上,源站,发送的控制分组有明确的,数据率上限,13,1.2,拥塞控制,(,Congestion Control,),14,1.3,通信量管理,(,Traffic Management,),1.,公平性,(,Fairness,),最后到达首先丢弃的策略是,不公平的,，可以采用一些技术实现,公平性,(,如,每个队列的缓存大小相同,),2.,服务质量,(,Quality of Service,),网络拥塞时，不同需求的流量应得到的,QoS,的不同,声音，视频：对时延敏感，对丢失不敏感,文件传送，邮件：对时延不敏感，对丢失敏感,交互计算：对时延和丢失都敏感,不同的流量应有不同的优先级,(,网络管理的通信量比较高,),3.,预留,(,Reservations,),策略：制订一个,通信量合约,，过量的通信量要么丢弃要么以尽力而为传输的方式处理,15,1.4,分组交换网中拥塞控制,1.,从拥塞节点向一些或所有源点发送一个控制分组。,2.,依据路由选择信息。,3.,利用端到端的探测分组。,4.,允许分组交换节点在分组经过时添加拥塞信息。,16,1.5,帧中继拥塞控制,1.,流量速率管理,(,Traffic Rate Management,),约定的信息速率,(,Committed Information Rate ,CIR,),网络认同的用于支持某个特定,帧模式,连接的速率，当网络出现拥塞时，首先丢弃超过,CIR,的连接所传输的帧,整体,CIR,节点的容量,整体,CIR,也不应超过用户,-,网络接口上的物理数据率,(,接入速率,),利用,两个参数,进行流量速率管理,约定突发长度,(,B,c,),在测量间隔,T,内网络,同意,传输的最大数据量,超量突发长度,(B,e,),在测量间隔,T,内网络,试图,传输的,超过,B,c,的最大数据量,17,例：假设某节点接入速度为,64kb/s,该节点被指派的,CIR,32kb/s,CIR,的测量时间间隔,T,500ms,，帧长,L 4000bit,。,在时间,T,内，虚电路只能发送,CIRT/L 4,个高优先级的帧，其,DE 0,。,由于,CIR,的数值只是接入速率的一半，因此用户在,500ms,内再发送,4,个低优先级的帧，其,DE=1,。,1.5,帧中继拥塞控制,18,18,19,20,2.,使用显示信令的拥塞避免,(,Congestion Avoidance with Explicit Signaling,),对于解决拥塞问题应,可控制,和,公平的,方式,显示拥塞避免技术的两种策略：,拥塞情况的出现是,缓慢的,，且绝大多数拥塞发生在网络的,出口节点,上,前向显示拥塞避免,(,forward explicit congestion avoidance,),拥塞在,内部,节点迅速增长，要求采取,果断,的措施来防止拥塞,反向显示拥塞避免,(,backward explicit congestion avoidance),1.5,帧中继拥塞控制,21,显示信令中的,两个位,(BECN,，,FECN),反向显示拥塞指示,(,Backward Explicit Congestion Notification,),对与,接收帧相反方向上的流量,起作用, 指出在这条逻辑连接上传输的,可能,会遇到拥塞,前向显示拥塞指示,(,Forward Explicit Congestion Notification,),对与,接收帧方向相同的流量,起作用,指出在这条逻辑连接上传输的帧,已经,遇到了拥塞,1.5,帧中继拥塞控制,22,1.6.1,Flow Control,1.,Flow Control,限制数据发送的数量或发送速率,Reasons:,源站,发送,PDUs,的速率,超过,了,目的站,对分组头部的处理能力,目的端的高层协议用户接收数据缓慢,目的站需要,转发数据流,，故源站不可发送太快，,目的端要限制,入流量,以便与,出流量,匹配,1.6 Flow Control and Error Control,23,2.,在多个协议层次上实施的流量控制, 多条,X.25,虚电路,(,第三级,),复用到一条,LAPB,的数据链路上,(,属于,X.25,第二级,),多条,TCP,连接复用到一条,HDLC,链路, 在高级别逻辑连接上，一个逻辑连接上流量控制的实施与其它级上逻辑连接上的流量控制无关, 高级连接上的通信量,总和,在低级别上受到进一步的流量控制,1.6 Flow Control and Error Control,24,1.6 Flow Control and Error Control,25,3.,流量控制的范围,(,Flow Control Scope,),一跳的范围, 在两个直接连接的中间系统之间，流量控制可在链路级实施, 网络接口, 端系统与一个网络之间的接口链路上，可在网络协议层实施, 进网到出网, 在进网到出网节点,间, 端到端, 端系统之间，可在,TCP,连接和数据链路层上进行实施,1.6 Flow Control and Error Control,26,1.6 Flow Control and Error Control,27,1.6.2,Error Control,1.,差错控制技术的用途：恢复丢失和损坏的数据。,2.,差错控制技术原理：包括差错检测以及,PDU,重传。,3.,差错控制和流量控制在一个单一的机制中,一同实现,。,4.,可在多种协议级别上实现，差控与流控一样,。,1.6 Flow Control and Error Control,28,3 techniques at link level:,Stop-and-wait,Go-back-N,Selective-reject,后二种是滑动窗口的特例！,1.6 Flow Control and Error Control,29,Sequence of Frames reasons,：,理由如下：, 接受端的缓存大小可能有限。, 传输数据越长，出错的可能性越大，较小的帧可能更快的检测出差错，需重传的数据量也较小。, 在共享媒体上，要避免一个站占据媒体时间过长，以免造成其他发送站很长的时延。,1.6 Flow Control and Error Control,30,1.7 Performance of ARQ,1.7.1,停止等待,ARQ (Stop and Wait ARQ),1.,无差错停止等待流控,(Error-Free Stop and Wait),T =,T,frame,+,T,prop,+,T,proc,+,T,ack,+,T,prop,+,T,proc,发送数据的总时间可以表达为,nT,，其中,T,是发送一个帧和收到一个确认并准备发送下一帧的时间,T,frame,传送一帧的时间，即发送端将所有位都发出的时间,T,prop,发送端和接收端之间的传播时延,T,proc,每个站的处理时间,T,ack,传送一个确认的时间,假定,T,proc,和,T,ack,都相对较小,T =,T,frame,+ 2T,prop,31,假定帧是定长大小，则停止等待流量控制允许数据以每,T,秒一帧的速率传送，,T,近似为：,T,T,frame,+ 2T,prop,表示每,T,秒一帧的速率传送,吞吐量,(,Throughput,),= 1/T = 1/(T,frame,+ 2T,prop,) frames/sec,如果一个帧可以在,T,frame,秒内传送完，该链路的,实际数据率,为：,1/,T,frame,frames/sec,归一化吞吐量,S,可以表示为：,S,吞吐量,/,实际数据率,1/(T,frame,+ 2T,prop,),T,frame,1,1/,T,frame,T,frame,+ 2T,prop,1 + 2,a,其中：,a,=,T,prop,/,T,frame,S,=,=,=,1.7 Performance of ARQ,32,2. Stop-and-Wait ARQ with Errors,P =,单个帧出现差错的概率,1,1 P,(,N,x,是由于出现差错，每个帧需要传输的平均次数,),发送成功一帧所需的平均时间,T =,N,x,(,T,frame,+ 2T,prop,),归一化吞吐量,S =,T,frame,/,N,x,(,T,frame,+ 2T,prop,),1 1 - P,N,x,(1 + 2,a,) (1 + 2,a,),S,=,N,x,=,=,1.7 Performance of ARQ,33,3. Error-Free Sliding Window ARQ,1.7 Performance of ARQ,34,1.7 Performance of ARQ,35,线路的吞吐量取决于窗口大小,W,和,a,的值,Case 1: W 2a + 1,对帧,1,的确认在,A,消耗完其窗口,前,就到达了,A,。,A,可以不停地连续传输。,Case 2: W 2a +1,A,在,t=W,时刻就耗尽了它的窗口，直到,t= 2a +1,时刻前都不能再发送帧。,1.7 Performance of ARQ,36,Normalized Throughput,1 W, 2a+1,S =,W,W 2a+1,2a + 1,1.7 Performance of ARQ,37,4. Selective Reject ARQ,1 - P W, 2a+1,S =,W(1 - P),W 2a+1,2a + 1,P,：单个帧出错的概率。,1.7 Performance of ARQ,38,5. Go-Back-N ARQ,1 - P W, 2a + 1,1 + 2aP,S =,W(1 - P),W RD / 4,此连接上可得到最大可能的吞吐量,S =,4W W RD / 4,W,与,RD/4,的比率,RD,1.8 TCP Flow Control,44,1.8 TCP Flow Control,45,1.8.1,窗口大小对性能的影响,(3),TCP,连接要考虑的因素：,许多,TCP,连接,复用,到同一个网络接口上，每条连接只分到可得容量的一部分，,降低了,R,因子,的大小并因此降低了传输效率,许多,TCP,连接,跨越,多个网络，,D,是穿过每个,网络的时延,加上在每个,路由器,上经受的,时延,，路由器时延经常是主要成分，尤其在拥塞时,如果源端,TCP,实体处连接的数据率,R,超过,从源端到目的端某一跳的数据率，,这一跳,将会是数据传输的瓶颈，从而使,D,增加,若报文段丢失进行,重传,，也会降低吞吐量，影响程度的大小取决于重传策略,1.8 TCP Flow Control,46,1.8.2,重传策略,(,Retransmission Strategy,),1. TCP,的差错控制方案,TCP,完全依靠确认应答，当确认在给定的一个,超时时段,中没有到达时就进行重传,在两种情况下，报文段应该重传,1.,报文段中携带的,效验和,让接受端检测到报文有,差错,，随即丢弃这个报文，不会发,ACK,2.,报文段,没有达到目的地,，不会发,ACK,1.8 TCP Flow Control,47,1.8.2,重传策略,(,Retransmission Strategy,),2.,定时器,(,Timers,),对发送出去的每个报文段都要设置一个,定时器,如果在收到一个报文段的确认之前定时器就超时了，发送方必须重传,(1),关键设计问题为,(Key Design Issue):,如何确定重传定时器的取值,时间,太小,:,会造成许多不必要的重传而浪费了网络容量,时间,太大,:,协议对于报文段丢失的反应就会很迟缓,1.8 TCP Flow Control,48,(2),确定重传定时器取值的,两种策略,(Two Strategies):,定时器应该设定为一个比,往返时延,(,发送报文段，接收,ACK),稍大,的值,但是往返时延会发生变化，并且时延的统计特性会随互联网状况的变化而变化,可采用的两种策略是：,1.,固定的定时器,(,Fixed timer,),2.,自适应,(,Adaptive,),1.8 TCP Flow Control,49,(3),自适应方案存在的问题,(Problems with Adaptive Scheme),对等的,TCP,实体进行,累积确认,，并不立即确认一个报文段,如果一个报文段被重传,过,，发送方无法了解收到的,ACK,是对,最初,传输的还是对重新传输的确认,互联网的状态可能,突然,发生变化,1.8 TCP Flow Control,50,1.8.3,自适应重传定时器,(,Adaptive Retransmission Timer,),关注,最近,的报文段时延模式估计目前的往返时延。将定时器设置为一个比估计的往返时延,大一些,的值,平均往返时间,(,Average Round-Trip Time,),K + 1,1 ,RTT(i,),K + 1,i = 1,K 1,K + 1 K + 1,ARTT(K + 1) =,=,ARTT(K),+,RTT(K + 1),1.8 TCP Flow Control,51,1.8.3,自适应重传定时器,(,Adaptive Retransmission Timer,),基于一个时间序列的,过去值预测,其,下一个值,有一种常用的技术即,指数平均,。,平滑往返时间估值,(,Smoothed Round-Trip Time,),SRTT(K + 1) =, SRTT(K) + (1 ,) RTT(K + 1),=,2,SRTT(K-1)+ (1- )RTT(K)+(1- )RTT(K+1),=(1-)RTT(k+1)+(1-)RTT(K)+,2,(1-),RTT(k-1),+ ,k,(1- )RTT(1),常数,0,1,观察值越陈旧，在平均值中计入的就越少,1.8 TCP Flow Control,52,=0.5,=0.875,1.8 TCP Flow Control,53,1.8 TCP Flow Control,54,3.,RFC 793,重传定时器时间,RTO(K + 1)= SRTT(K + 1)+,公式的问题：,对于,较大,的,SRTT,值,相对,较小,实际,RTT,的波动就会造成不必要的,重传, 对于,较小,的,SRTT,，,相对,较大,，这在重传丢失报文段时会引起不必要的,延迟,RTO(K + 1) =,Min(UB,Max(LB, SRTT(K + 1,),UB, LB:,预先选定的定时器值的固定上限值和下限值,Example values for,:,0.8 , 0.9 1.3 , 2.0,1.8 TCP Flow Control,55,动态选路可通过将,负载均匀分布,到交换机和链路上来帮助缓解拥塞的目的, 但这种措施,只在处理不平衡负载的,短期,通信量集聚的情况时有效, 最终,拥塞,只能通过,将,进入,互联网的,数据总量限制,为互联网可以承载的量的,方法控制,ICMP,源站抑制报文手段原始，但不是有效的手段能控制拥塞,RSVP,可能在控制拥塞上会起作用，但离,广泛,实施还有一段距离,1.9 TCP Congestion Control,56,基于,TCP/IP,的互联网中拥塞控制是复杂而困难的,IP,是一个,无连接,、,无状态,的协议，它没有提供检测更不用说控制拥塞的机制,TCP,只提供,端到端,流量控制，,间接推测,拥塞，而且网络或互联网中,时延,可变且,很长,，对网络状况了解并不可靠,各,TCP,实体之间,并没有相互合作,的分布式算法将它们联结在一起，不可能将总流量维持在一定水平上，更可能,相互竞争资源,1.9 TCP Congestion Control,57,1.9.1,TCP Flow and Congestion Control,TCP,实体可以发送数据的速率，取决于对以前报文段确认的,ACK,的速率所确定，并可携带新的,信用量,ACK,到达速率,是由,源端,与,目的端,之间,往返路径,上的,瓶颈,所确定；,TCP,能自动感知网络瓶颈并对其流量作出调整，它称为,TCP,自同步行为,瓶颈可能是,目的端,也可能是,互联网,源端无法知道瓶颈是,目的端,(,流量控制,),还是,互联网,(,拥塞控制,),互联网上的瓶颈是由拥塞造成，源端应比,ACK,速率,更慢,的速率传输报文段，以缓解拥塞,(,拥塞控制,),由目的端流控造成的,低,速率，则发方,TCP,实体应以该速率传播,(,流量控制,),1.9 TCP Congestion Control,58,1.9 TCP Congestion Control,59,1.9 TCP Congestion Control,60,1.9.2,重传定时器管理,(,Retransmission Timer Management,),三种技术用于解决重传定时器,(RTO),的计算问题：,(1) RTT,方差估计,(2),指数,RTO,退避,(3),Karn,算法,1.9 TCP Congestion Control,61,1. RTT,方差估算（,Jacobson,算法）,3,种高方差的来源, 如果,TCP,连接上的数据率,较低,，,传播时间,与,传输时延,的比值相对,较大,。而且,IP,数据报大小的变化引起的,时延的方差,也很大，,SRTT,估算值会受到数据特性而不是网络特性的很大影响, 负载可能由于其它信源而突然变化，造成,RTT,的,突然变化, 对等,TCP,实体可能不对每个报文段,立即确认，而是累计确认,1.9 TCP Congestion Control,62,RTT,方差估计（,Jacobson,算法）,(1) Jacobson,算法,SRTT(K + 1) = (1 g), SRTT(K) + g RTT(K + 1),SERR(K + 1) = RTT(K + 1) SRTT(K),SDEV(K + 1) = (1 h) SDEV(K) + h |SERR(K + 1)|,RTO(K + 1) = SRTT(K + 1) + f SDEV(K + 1),g = 0.125,h = 0.25,f = 2 or f = 4,1.9 TCP Congestion Control,63,1.9 TCP Congestion Control,64,(2),两个要考虑的因素,Jacobson,算法可以显著提高,TCP,的性能，但本身不完整。, 对于重传的报文段应使用什么样的,RTO,值？,指数退避算法用于这一目的, 哪些往返时间采样值应用做,Jacobson,算法的输入？,karn,算法决定使用哪些采样,1.9 TCP Congestion Control,65,2.,指数,RTO,退避,TCP,源端在同一报文段重传时,增加其,RTO,退避过程, 方法是对一个报文段的每次重传都将,RTO,乘以一个参数值,q,RTO,qRTO, q,2,时为二进制指数退避,1.9 TCP Congestion Control,66,3.,往返采样值如何选取？, 对于重传过的报文,没有有效的方法计算,RTT:,是第一次传输到收到,ACK,这段时间呢？,还是第二次传输到收到,ACK,这段时间呢？,1.9 TCP Congestion Control,67,karn,算法解决了上述问题, 不要使用对重传报文段测得的,RTT,更新,SRTT,和,SDEV,当发生重传时计算退避,RTO,qRTO,对后续各报文段使用退避,RTO,值，直到收到一个未被重传过的报文段的确认为止, 然后使用,Jacobson,算法计算以后的,RTO,1.9 TCP Congestion Control,68,1.9.3,窗口管理,(,Window Management,),窗口管理的五种技术：,慢启动（,Slow start,）,出现拥塞时动态调整窗口大小,快速重传（,Fast retransmit,）,快速恢复（,Fast recovery,）,受限传输（,Limited transmit,）,1.9 TCP Congestion Control,69,