43-窗口流控和TCP解析课件.ppt

1、4.3窗口流控机制2014-3-25Referencel部分参阅 Ion Stoicahttp:/inst.eecs.berkeley.edu/ee122/fa09/http:/www.cs.berkeley.edu/istoica/classes/cs268/06/以下，哪个传送速率能够更高？以下，哪个传送速率能够更高？本章将研究拥塞控制和流量控制有的作者把两者统称为流量控制l 控制发送端的速率，限制进入网络的流量流量控制：防止接收端能力不足以处理接收到的数据拥塞控制：防止发送过快引发拥塞；一旦网络拥塞，退出拥塞状态；l 要点：1.理解流控的重要性；2.窗口机制和TCP拥塞控制过程；3.基于

2、漏桶的流控原理和缓存计算；4.最大最小公平机制和实现内容l问题的引出拥塞是必然的；拥塞崩溃是可怕的；流量控制是必须的；l基于窗口的控制机制l基于速率的控制机制lMax-Min Fairness6What We KnowlHow to send packets reliablyWe dont know:lHow fast can we send7不仅仅是发送端和接收端的事儿l Flow control keeps one fast sender from overwhelming a slow receiverl Congestion control keeps a set of senders

3、 from overloading the networkl Three congestion control problems:1.Adjusting to bottleneck bandwidth/如何适应瓶颈带宽lWithout any a priori knowledgelCould be a Gbps link;could be a modem2.Adjusting to variations in bandwidth/如何适应带宽变动3.Sharing bandwidth between flows/如何共享带宽8Congestion is Unavoidablel Two pac

4、kets arrive at the same timeThe node can only transmit one and either buffers or drops the otherl If many packets arrive in a short period of timeThe node cannot keep up with the arriving traffic and the buffer may eventually overflow9Congestion Collapsel Definition:网络负载增加到使网络的有效投递量下降l Due to:没有成功传送

5、的分组l它们它们占用了网络资源，但途中因拥塞被丢弃；占用了网络资源，但途中因拥塞被丢弃；大量被重传的分组l被拒绝的分组又被重传，可是又被网络拒绝！被拒绝的分组又被重传，可是又被网络拒绝！lPouring gasoline on a firel Mid-1980s:Internet grinds to a halt幸亏Jacobson/Karels(Berkeley!)发明了TCP 拥塞控制机制原因：拥塞崩溃导致缓存溢出，进而死锁l 如果A缓存被B的分组占满,B缓存被A分组占满A不能接收B的任何流量B不能接收A的任何流量11View from a Single Flow l Knee point

6、 after which Throughput increases very slowly Delay increases quicklyl Cliff point after which Throughput starts to decrease very fast to zero(congestion collapse)Delay approaches infinityLoadLoadThroughputDelaykneecliffcongestioncollapsepacketloss拥塞崩溃也传染l 假定：数据传输没有误码网络采用点-点可靠传输协议l 考虑2个session：1.红的2

7、.黑的ABDCXYZ8641683216Cont.lcase 1：BA=7kbpsCD=0kbpsBYXA上的流量为7kbpsCZXD上的流量为0kbpsABDCXYZ8641683216Cont.l Case 2：BA=8+kbpsCD=0kbpsCZXD上的数据流量为0kbpsBYXA:8kbpsl BY:16kbpslYX:64kbpslXA:8kbpsABDCXYZ8641683216以高于网络能力哪怕一点点的速率发送数据，将导致大量网络资源消耗Cont.l Case 4：BA=8+kbpsCD=7kbpsBA：8kbpslBY：16kbpslYX：64kbpslXA：8kbpsCD：

8、4kpslCZ：16kbpslZX：32kbpslXD：4kbpsABDCXYZ8641683216BA数据量过大，CD也跟着遭殃！拥塞控制，这个必须有！最大化网络吞吐量减少网络时延兼顾公平性17General ApproacheslSend without careMany packet drops(1)ReservationsPre-arrange bandwidth allocationsRequires negotiation before sending packetsLow utilization(2)Pricing Dont drop packets for the high-b

9、iddersRequires payment model18General Approaches(contd)(3)Dynamic Adjustment(窗口式流控-TCP)Probe network to test level of congestionSpeed up when no congestionSlow down when congestionSuboptimal,messy dynamics,simple to implementl All three techniques have their placeBut for generic Internet usage,dynam

10、ic adjustment is the most appropriateDue to pricing structure,traffic characteristics,and good citizenship内容l问题的引出l窗口流控机制窗口机制可行，但窗口要动态调整；网络拥塞探测；建立窗口（速率）调整函数；l慢启动和AIMDl基于速率的控制机制lMax-Min Fairness窗口流控l 用类似基于窗口的ARQ每个会话有一个端到端的窗口WSD；接收端每收到一个分组，都要回送一个ACK；同时发送的没有被确认的分组数 WSD；网络中的分组数和确认的分组数之 WSD；l 因此，发送窗口应反映两

11、个东西1.接收端的缓存大小；2.网络中的缓存数量；21窗口应多大？lcwnd(Congestion Windows)How many bytes can be sent without overflowing routersComputed by congestion control algorithmlrwnd(Advertised Window)How many bytes can be sent without overflowing the senderDetermined by the receiverCWND发送窗口 W，假设只有一个会话设X为分组的平均传输时间,窗口大小为W,端到

12、端传输时延为d如果WXd,则窗口机制不起作用,全速发送(速率=1/X)如果WX=ssthresh后，进入拥塞避免 CASlow Start 慢启动并不慢data packetACKreceiversender1 RTTcwnd12345678cwnd cwnd+1(for each ACK)40不能总保持慢启动l 窗口增长到一定程度时(cwndBW*RTT),慢启动将导致分组批量丢失，这是因为At some point,cwnd is enough to fill“pipe”After another RTT,cwnd is double its previous valueAll the e

13、xcess packets are dropped!l 所以，一旦估计到带宽，窗口算法就该温和一些41Problem#2:Single Flow,Varying BWl 窗口大小应动态跟踪带宽变化(在当前可用带宽附近摆动)l 窗口的可选变动函数:(in terms of RTTs)Multiplicative increase or decrease:cwnd a*cwnd Additive increase or decrease:cwnd cwnd+bl Four alternatives:AIAD:gentle increase,gentle decrease AIMD:gentle i

14、ncrease,drastic decrease MIAD:drastic increase,gentle decrease(too many losses)MIMD:drastic increase and decrease42Problem#3:Multiple Flowsl Want steady state to be“fair”l 公平：两个流能获得相同的资源；l 下面，我们将看到：AIMD is the only remaining solution!43User 1:x1User 2:x2fairnesslineefficiencyline11l 既要公平l 又要高效l 坐标点(

15、x,y)是用户1和用户2的窗口值Inefficient:x1+x2=0.7(0.2,0.5)Congested:x1+x2=1.2(0.7,0.5)Efficient:x1+x2=1Not fair(0.7,0.3)Efficient:x1+x2=1Fair(0.5,0.5)乘性加，线性减 (MIAD)用户 1:x1用户2:x2公平线效率线(x1h，x2h)(x1h-aD，x2h-aD)(bI(x1h-aD)，bI(x2h-aD)l 不能收敛到公平线l 不能收敛到效率线l Increase:x*bIl Decrease:x-aDl Does not converge to fairnessl

16、Does not converges to efficiency线性加，线性减(AIAD)用户1:x1用户2:x2(x1h，x2h)(x1h-aD，x2h-aD)(x1h-aD+aI)，x2h-aD+aI)l 不能收敛到公平线l 不能收敛到效率线公平线效率线Increase:x+aIDecrease:x-aDDoes not converge to fairnessDoes not converge to efficiency乘性加，乘性减 (MIMD)用户1:x1用户2:x2(x1h，x2h)(bdx1h，bdx2h)(bIbDx1h，bIbDx2h)l Increase:x*bIl Dec

17、rease:x*bDl不会收敛到公平线l能收敛到效率线 iff公平线效率线101DIbb(bDx1h+aI，bDx2h+aI)线性加，乘性减(AIMD)（Additive Increase,Multiplicative Decrease）用户1:x1用户2:x2(x1h，x2h)(bDx1h，bDx2h)l 收敛到公平线l 能收敛到效率线公平线效率线l Increase:x+aDl Decrease:x*bDl Converges to fairnessl Converges to efficiencyl Increments smaller as fairness increases线性加乘

18、性减,AIMDl同时满足了2项需求：窗口的动态变化资源的公平分配l奠定了1989年后Internet增长的理论基石Internet发展的里程碑TCP基础Implementing AIMD(1)拥塞避免阶段 Congestion Avoidancel当满足cwnd ssthresh(慢启动门限)时，进入CA阶段每收到一个ACK，cwnd cwnd+1/cwnd相当于，每个RTT，cwnd cwnd+1Congestion Avoidancecwnd1231 RTT4data packetACKcwnd cwnd+1(for each cwnd ACKS)receiversenderImpleme

19、nting AIMD(2)丢包重传l丢包=拥塞：RTO or 3dupACKs 立即重传l调整ssthresh门限flightsize=min(awnd,cwnd)ssthresh max(flightsize/2,2)l进入Slow Start(cwnd=1)52The big picture(with timeouts)TimecwndTimeoutSlowStartAIMDTimeoutssthreshSlowStartSlowStartAIMDInitially:cwnd=1;ssthresh=infinite;New ack received:if(cwnd ssthresh)/*S

20、low Start*/cwnd=cwnd+1;else /*Congestion Avoidance*/cwnd=cwnd+1/cwnd;Timeout:/*Multiplicative decrease*/ssthresh=cwnd/2;cwnd=1;53窗口流控小结l Congestion is inevitableInternet does not reserve resources in advanceTCP actively tries to grab capacityl Congestion control critical for avoiding collapseAIMD:Additive Increase,Multiplicative DecreaseCongestion detected via packet loss(fail-safe)Slow start to find initial sending rate&to restart after timeoutl Next classAdvanced congestion control545 Minute Breakl这个版本的TCP效率会怎样?要求：1 理解拥塞和流量控制的重要性2 慢启动、AIMDOn page 219：l 思考题：TCP的窗口拥塞控制,例题6.3,习题1,3,l 作业题：习题4