计算机自顶向下方法第三章课件.ppt

《计算机自顶向下方法第三章课件.ppt》由会员分享，可在线阅读，更多相关《计算机自顶向下方法第三章课件.ppt（69页珍藏版）》请在三一办公上搜索。

1、第3讲 传输层之一,1,传输服务和协议,提供运行在不同主机中进程间的逻辑通信 传输协议仅运行在端系统中 传输 vs.网络层服务:网络层:在端系统间进行通信传输层:在进程间进行通信 依赖于,加强了,网络层的服务,第3讲 传输层之一,2,The blacks The Whites,mike mary,Bill Ann,第3讲 传输层之一,3,传输层协议,Internet 传输服务:可靠,按序点对点递交(TCP)拥塞控制流量控制连接建立不可靠的(“尽力而为”),无序的点对点或广播递交:UDP不能提供的服务:实时性带宽承诺可靠的广播通信,第3讲 传输层之一,4,P2,复用/分用(multiplexin

2、g/Demultiplexing),回顾:segment（段）-传输层实体间交换数据的单位 TPDU:传输层数据单元,receiver,H,t,分用:将接收到的段传递给正确的应用层进程,segment,segment,M,P1,P3,P4,segmentheader,application-layerdata,第3讲 传输层之一,5,复用/分用,复用/分用:基于发送方,接收方的端口号,IP 地址源,目的端口#s 存在于每个段中回顾:用于特定应用的常用端口号（well-known port number）,从多个应用进程获取数据,用首部(便于随后的分用)封装数据,源端口#,宿端口#,32 bit

3、s,应用层数据(报文),其他首部字段,TCP/UDP 段格式,第3讲 传输层之一,6,复用/分用:举例,主机 A,服务器 B,端口的使用:简单的 telnet 应用,Web客户端主机 A,Web服务器 B,Web客户端主机 C,端口的使用:Web 服务器,第3讲 传输层之一,7,UDP:用户数据报协议 RFC 768,“最简约的”Internet 传输协议“尽力而为的”服务,UDP 数据段可以:丢失应用数据不按序到达无连接:在UDP收发双方之间,无需握手信号每个 UDP 数据段的操作都互相独立,为什么需要 UDP?无需建立连接(会增加延迟)简单:在收发双方之间没有连接状态段首较短无拥塞控制:U

4、DP 可按需要随时发送,第3讲 传输层之一,8,UDP:(续),经常为流媒体应用使用允许数据丢失对传输速率敏感其他 UDP用途(why?):DNSSNMP若需要通过 UDP进行可靠传输:在应用层增加可靠性措施在应用程序中-专门的出错恢复机制!,源端口#,宿端口#,32 bits,应用层数据(报文),UDP 数据报格式,length,checksum,长度,UDP段的字节数,包括首部,第3讲 传输层之一,9,UDP 校验和（checksum）,发送方:将段的内容看作一串16位整数checksum:作段内容的加法(补码和)发送方将补码和放入 UDP checksum 字段,接收方:对接收到的段内容

5、进行补码和计算检查计算结果是否与收到的校验和相等:NO 查出错误YES 没查出错误.但是仍有可能存在错误?,目标:检测传输段中的“错误”(e.g.,位错),第3讲 传输层之一,10,可靠数据传输原理,在应用、传输、链路层都十分重要属于网络工程的top-10 课题之一!,不可靠传输通道的特性将决定可靠传输协议(rdt)的复杂性,第3讲 传输层之一,11,可靠数据传输:开始起步,发送方,接收方,第3讲 传输层之一,12,可靠数据传输:开始起步,我们将要:逐步发展收发双方的可靠数据传输协议(rdt)仅考虑单向的数据传输但控制信息将双向流动!使用有限状态机(FSM)来定义发送方,接收方,事件导致状态的

6、转换,在状态转换过程中的动作,状态:当实体处于某个“状态”时，下个状态只能由下个事件来转变,第3讲 传输层之一,13,Rdt1.0:在可靠信道上进行可靠的数据传输,所依赖的信道非常可靠不可能有位错不会丢失数据分别为发送方和接收方建立 FSMs:发送方将数据送入所依赖的信道接收方从所依赖的信道读出数据,第3讲 传输层之一,14,Rdt2.0:在可能发送位错的信道上传输,所依赖的信道有可能在分组数据中出现位错回顾:UDP checksum 可发现位错问题:如何从错误中恢复:进行确认(ACKs):由接收方法送报文向发送方进行确认发送否认(NAKs):由接收方法送报文向发送方进行否认，说明分组有错发送

7、方在收到NAK后进行分组重传在人类交往中是不是也有 ACKs,NAKs?rdt2.0的新机制(在 rdt1.0基础之上):错误检测接收方的反馈:控制信息(ACK,NAK)rcvr-sender,第3讲 传输层之一,15,rdt2.0:有限状态机定义,发送方的FSM,接收方FSM,第3讲 传输层之一,16,rdt2.0:运行过程(未发现错误),发送方 FSM,接收方 FSM,第3讲 传输层之一,17,rdt2.0:运行过程(出错情况),发送方 FSM,接收方FSM,第3讲 传输层之一,18,rdt2.0 有一个致命的缺点!,若ACK/NAK 报文丢失?发送方将不会知道接收端发生了什么!假如进行重

8、传:可能发生数据重复怎么办?发送 ACK/NAK 来回应接收方的 ACK/NAK?那么如果发送方的 ACK/NAK 丢失?重传,但可能可能导致重传了正确的分组!,管理重复的问题:发送方给每个分组加上sequence number（序号）如果ACK/NAK丢失，发送方则重传正确的分组接收方丢弃重复的分组(不向上递交),发送方法送一个分组，然后等待接收方的响应,第3讲 传输层之一,19,rdt2.1:发送方,管理丢失的 ACK/NAK,第3讲 传输层之一,20,rdt2.1:接收方,管理丢失的 ACK/NAK,第3讲 传输层之一,21,rdt2.1:讨论,发送方:给分组加seq#两个#s(0,1)

9、够否，为什么?必须查收ACK/NAK 两倍的状态必须“记忆”状态，是否“正确的”分组具有 0 或 1 seq.#,接收方:必须查验接收到的分组 是否重复状态可以指出0 或 1 是期望中的 seq#注意:接收方不会知道最后的ACK/NAK 是否为发送方正确接收,第3讲 传输层之一,22,rdt2.2:无 NAK的协议,其功能等同 rdt2.1,但仅使用 ACK不使用 NAK,接受方只为最后正确接受的报文发送 ACK接收方必须显式表明ACK 的分组 seq#发送方得到双重ACK导致 NAK的相同结果:重传正确的分组,发送方FSM,!,第3讲 传输层之一,23,rdt3.0:通道上可能出错和丢失数据

10、,新的假设:所依赖的信道会丢失数据(数据或 ACK)checksum,seq.#,ACK,重发机制会有帮助，但还远远不够Q:如何处理数据丢失?发送方可以等待，当某些数据或ACK 丢失时,进行重传想一想:缺点?,方法:发送方等待ACK一段“适当的”时间如果在这段时间里没有收到则进行重传如果分组(或 ACK)仅仅被延迟了(没有丢失):重传将导致重复,但使用seq.#s 可以控制接收方必须定义被 ACK分组的 seq#需要进行倒计时,第3讲 传输层之一,24,rdt3.0 发送方,第3讲 传输层之一,25,rdt3.0 接收方,第3讲 传输层之一,26,rdt3.0 的运行,第3讲 传输层之一,27

11、,rdt3.0 的运行,第3讲 传输层之一,28,rdt3.0的性能,rdt3.0 可用,不过性能很糟例如:1 Gb/s 链路,15 ms 端对端的延迟,1KB 分组:,1KB 分组每 30 ms-33kB/sec 在 1 Gb/s 链路上的吞吐量网络协议限制了物理资源的利用!,第3讲 传输层之一,29,流水线协议（参见p79-84）,流水作业:发送端允许发送多个,“悬在空中”,等待应答的分组必须增加顺序号的位数在发送和接收端增加缓存,两种常用的流水线协议:第N个分组重发(go-Back-N),选择应答,第3讲 传输层之一,30,从第N个分组重发(Go-Back-N),发送方:在分组首部设置k

12、位 seq#使用尺寸为N的“滑动窗口(p80)”,允许连续的多个分组不被应答,ACK(n):ACK所有n号之前，包括n号在内的分组-“积累式ACK”可能产生重复的ACK(见接收方)为每个未应答（in-flight）的分组设置计时器(timer)当发生超时：timeout(n):重传n号和n号以后的所有分组,第3讲 传输层之一,31,GBN:发送方扩展的 FSM,上层调用：,ACK的接收,超时事件,第3讲 传输层之一,32,GBN:接收方扩展的 FSM,接收方举例:ACK-only:总是对正确接收到的分组中按序（in-order）对最高 seq#进行ACK可以产生重复的ACKs仅仅需要记住 ex

13、pectedseqnum（预期的序号）失序分组:丢弃(不缓存)-不进行接收缓存!接收到的分组中按序对最高 seq#进行ACK,第3讲 传输层之一,33,GBN 的运行,第3讲 传输层之一,34,选择应答(SR)-p84,接收方逐个对所有正确收到的分组进行应答如有必要，对接收到的（失序）分组进行缓存,以便最后对上层进行有序递交发送方仅对未收到应答的分组进行重发发送方未每个unACKed 分组设置计时器 发送方的窗口N 个连续的 seq#s同样对已发送的seq#s,unACKed分组进行限制,第3讲 传输层之一,35,选择应答:发送方,接收方的窗口,第3讲 传输层之一,36,选择应答,上层数据到达

14、:如果窗口中的下一个序号可用，发送分组timeout(n):第n个计时器跳重发分组n,计时器复位 ACK(n)到达sendbase,sendbase+N:标记分组 n 已经收到如n为unACKed分组中的最小值,将窗口下沿前推倒下一个unACKed seq#,分组n到达rcvbase,rcvbase+N-1发送 ACK(n)失序:缓存有序:递交到上层(同时递交缓存中的其他有序分组),将窗口前推倒下一个尚未收到的分组分组n到达 rcvbase-N,rcvbase-1虽然接收方曾经确认，但仍然需要ACK(n)其他情况:忽略分组,第3讲 传输层之一,37,选择应答的运行,第3讲 传输层之一,38,第

15、4讲 传输层之二,本讲目的:Internet传输层的实现和实例教科书参考第8章,本讲概述:面向连接的传输:TCP可靠传输流量控制连接管理TCP拥塞控制拥塞控制原则,第3讲 传输层之一,39,TCP:概述 RFCs:793,1122,1323,2018,2581,全双工数据传输:在同一连接上双向传输MSS:maximum segment size（最大段字节数-1500,536,512）面向连接:握手过程(交换控制信息)在交换数据前初始化收发双方的状态,“三次握手”流量控制:发送方的发送速度不得超过接收方的处理速度,点对点:一个发送方,一个接收方 可靠,按序的字节流:无“报文边界”，无结构但有顺

16、序流水式控制:TCP的拥塞和流量控制，设置窗口大小发送&接收缓存,第3讲 传输层之一,40,TCP 段格式(p238),URG:urgent data（一般不用）,ACK:ACK#valid,PSH:push data now(一般不用),RST,SYN,FIN:connection estab(setup,teardowncommands),#bytes 接收方愿意接受的,按发送数据的字节计算(不是按段数!),Internetchecksum(as in UDP),第3讲 传输层之一,41,TCP seq.#s 和 ACKs,Seq.#s:该数据段第一个字节在（整个报文）字节流中“编号”AC

17、Ks:seq#为预期从对方发来的“下一个”字节的编号积累的 ACKQ:接收方如何接受失序的数据段A:TCP 没有定义,-由程序设计者决定,Host A,Host B,Seq=42,ACK=79,data=C,Seq=79,ACK=43,data=C,Seq=43,ACK=80,UsertypesC,host ACKsreceipt of echoedC,host ACKsreceipt ofC,echoesback C,简单的 telnet 场景,第3讲 传输层之一,42,TCP:可靠数据传输,简化的发送方,假设,waitfor event,waitfor event,event:data r

18、eceived from application above,event:timer timeout for segment with seq#y,event:ACK received,with ACK#y,create,send segment,retransmit segment,ACK processing,单向数据传输无流量,拥塞控制,第3讲 传输层之一,43,TCP:可靠数据传输,00 sendbase=initial_sequence number 01 nextseqnum=initial_sequence number 0203 loop(forever)04 switch(e

19、vent)05 event:data received from application above 06 create TCP segment with sequence number nextseqnum 07 start timer for segment nextseqnum 08 pass segment to IP 09 nextseqnum=nextseqnum+length(data)10 event:timer timeout for segment with sequence number y 11 retransmit segment with sequence numb

20、er y 12 compue new timeout interval for segment y 13 restart timer for sequence number y 14 event:ACK received,with ACK field value of y 15 if(y sendbase)/*cumulative ACK of all data up to y*/16 cancel all timers for segments with sequence numbers y 17 sendbase=y 18 19 else/*a duplicate ACK for alre

21、ady ACKed segment*/20 increment number of duplicate ACKs received for y 21 if(number of duplicate ACKS received for y=3)22/*TCP fast retransmit*/23 resend segment with sequence number y 24 restart timer for segment y 25 26/*end of loop forever*/,简化的TCP发送方,第3讲 传输层之一,44,TCP ACK 规则 RFC 1122,RFC 2581,事件

22、有序数据段到达,没有缺失的段,所有其他数据段已经 ACKed有序数据段到达,没有缺失的段,有一个延迟 ACK 等待失序数据段到达seq.#高于预期值测到间隔到达的数据段部分或全部填满了缺失的段,TCP 接收方的动作延迟 ACK.等待 500ms看是否还有数据段到达.如果没有,发送ACK立即发送一个积欠的 ACK 发送重复的 ACK,说明 seq.#为下一个期望的字节立即 ACK，如果数据段处于缺失的段的较低端,第3讲 传输层之一,45,TCP:重传场景,Host A,Seq=100,20 bytes data,ACK=100,Seq=92 timeout,过早超时,积欠 ACKs,Host B

23、,Seq=92,8 bytes data,ACK=120,Seq=92,8 bytes data,Seq=100 timeout,ACK=120,第3讲 传输层之一,46,TCP 流量控制,接收端:显式通知发送端(动态变化中的)自由缓存空间 RcvWindow TCP 数据段的字段发送端:需要保存已经发送,unACKed 数据可少于最近收到的RcvWindow,发送端不可发送的太多、太快以至于使得接收端的缓存溢出,接收端缓存,RcvBuffer=接收端的 TCP 缓存大小RcvWindow=缓存中空闲的部分,第3讲 传输层之一,47,TCP 交互的往返时间（RTT）和超时,Q:如何设置 TCP

24、 超时的值?应较RTT长一点注意:RTT 会变！太短了:过早出现超时造成不必要的重传太长了:减缓了对数据段丢失的反应,Q:如何估算 RTT?SampleRTT:对数据段发送到收到ACK 回应的时间进行测量忽略重传,积欠 ACKed 数据段SampleRTT 是会变化的,要使得估算的 RTT“更平滑”使用若干新近的测量结果,而不仅仅是最近一次的 SampleRTT,第3讲 传输层之一,48,TCP RTT 和超时(p246),EstimatedRTT=(1-x)*EstimatedRTT+x*SampleRTT,指数加权移动平均（EWMA）给定样本的影响随指数形式快速递减X的典型量值:0.125

25、或1/8,设置超时EstimtedRTT 加上“安全边际(safety margin)”如果 EstimatedRTT变化较大-加大安全边际,Timeout=EstimatedRTT+4*Deviation,Deviation(偏差)=(1-x)*Deviation+x*|SampleRTT-EstimatedRTT|,第3讲 传输层之一,49,TCP 连接管理,回顾:TCP 收发双方在数据交换开始之前需要建立连接初始化 TCP变量:seq.#s缓存,流量控制信息(e.g.RcvWindow)客户端:连接的发起者 Socket clientSocket=new Socket(hostname,

26、port number);-JAVA服务器:接受客户端的连接 Socket connectionSocket=welcomeSocket.accept();,(建立连接)三次握手:Step 1:客户端的end system向服务器发送 TCP SYN 控制数据段定义并初始化 seq#Step 2:服务器的end system接收 SYN,用SYNACK控制数据段回答ACKs 接收到的 SYN分配缓存定义 server-receiver 初始化 seq.#Step 3:客户端的end system向服务器发送ACK ACKs 接收到的连接承诺分配缓存,第3讲 传输层之一,50,TCP 连接管理(

27、续),关闭连接:客户端关闭插口:clientSocket.close();Step 1:客户端 end system 发送 TCP FIN 控制段给服务器 Step 2:服务器 收到 FIN,用 ACK应答.关闭连接,发送 FIN.,第3讲 传输层之一,51,TCP 连接管理(续),Step 3:客户端 收到 FIN,用 ACK进行应答.随着对接收到的FIN发送ACK-同时进入“timed wait（计时等待）”Step 4:服务器,接收 ACK.连接关闭.注意:稍加修改,即可管理同时发生的多个FINs.,client,FIN,server,ACK,ACK,FIN,closing,closin

28、g,closed,timed wait,closed,第3讲 传输层之一,52,TCP 连接管理(续),TCP 客户端实例的生命周期,TCP 服务进程的生命周期,第3讲 传输层之一,53,拥塞控制原理,拥塞:非正式的说法:“过多信源以过快的速率发送了过多的数据、导致网络穷于应付”不同于流量控制!后果:丢失数据分组(路由器缓存溢出)长时间的延迟(在路由器的缓存中排队)在网络发展的技术中的a top-10 problem!,第3讲 传输层之一,54,缘由/代价-拥塞问题:场景1,两个发送端,两个接收端一个路由器,有限缓存 无重传机制,发生拥塞时的延迟可达到的最大吞吐量,第3讲 传输层之一,55,缘

29、由/代价-拥塞问题:场景 2,一个路由器,有限 缓存 发送端重传丢失的分组,第3讲 传输层之一,56,缘由/代价-拥塞问题:场景 2,设计期望:(goodput)“完美的”重传仅仅是在分组丢失时:重传被延迟的(而不是丢失的)分组造成大量无意义的(比起完美的情况)对同样的,拥塞的“代价”:在给定的“goodput”下需要做更多的工作(重传)不必要的重传:链路上充斥着分组的多个拷贝,第3讲 传输层之一,57,缘由/代价-拥塞问题:场景 3,四个发送端多步跳路径超时/重传,Q:当 和 增加时发生了什么?,第3讲 传输层之一,58,缘由/代价-拥塞问题:场景 3,另一种拥塞的“代价”:当分组被丢弃时,

30、所有“上游”信道为该分组所作的工作统统被浪费了!,第3讲 传输层之一,59,拥塞问题的解决方案,端对端的拥塞控制:没有来自网络的反馈信息对拥塞问题的了解来自于对数据丢失和延迟的推断有 TCP来解决,网络辅助的拥塞控制:路由器向端系统提供反馈一个比特位的说明(SNA,DECNet,TCP/IP ECN,ATM)显式告知发送方所应采用的数据速率,两大类拥塞控制的办法:,第3讲 传输层之一,60,案例研究:ATM ABR 拥塞控制,ABR:available bit rate（可用数据速率）:“弹性服务”如果发送方的路径“欠负载”发送端应该把带宽用足如果发送端路径拥塞:发送端将其数据速率约束到最小承

31、诺速率,RM(resource management)cells（资源管理信元）:由发送端发送,掺和在数据信元一起在 RM 信元中的数据位由交换机设定(“网络辅助”)NI bit:不得增加发送速率(轻微拥塞)CI bit:拥塞指示RM信元由接收端返回给发送端,所有数据位保持原样,第3讲 传输层之一,61,案例研究:ATM ABR 拥塞控制,在RM信元中有2字节的 ER(explicit rate)字段处于拥塞的交换机可降低信元中的ER 值发送端的发送速率可以在路径上得到最低程度的支持数据信元的EFCI 位:在拥塞的交换机中被设成 1如果在RM信元之前的数据信元的EFCI置1,发送端将在返回的

32、RM的RM信元中将CI置1,第3讲 传输层之一,62,TCP 拥塞控制,端到端的控制(无需网络协助)传输速率限制由建立在数据段之上的拥塞窗口尺寸Congwin决定:,w=数据段数量,每个具有 MSS字节,在一个 RTT周期内发送:,Congwin,第3讲 传输层之一,63,TCP 拥塞控制:,两个“阶段”slow start（慢启动）congestion avoidance（拥塞避免）重要变量:Congwinthreshold:定义两个慢启动之间，拥塞控制阶段的门限值,“刺探”可用带宽:理想情况:全速传输(Congwin 越大越好)没有数据丢失增加 Congwin 直到出现数据丢失(拥塞)数据

33、丢失:减小 Congwin,然后重新开始进行刺探(增加Congwin),第3讲 传输层之一,64,TCP Slowstart（慢启动）,窗口尺寸按指数递增(每隔 RTT)(不算太慢!)丢失事件:超时(Tahoe TCP)和/或三次重复 ACKs(Reno TCP),initialize:Congwin=1for(each segment ACKed)Congwin+until(loss event OR CongWin threshold),Host A,one segment,RTT,Host B,two segments,four segments,第3讲 传输层之一,65,TCP 拥塞避

34、免,/*slowstart is over*/*Congwin threshold*/Until(loss event)every w segments ACKed:Congwin+threshold=Congwin/2Congwin=1perform slowstart,拥塞避免,1,1:在出现三次重复的ACK后，TCP Reno 将跳过 slowstart(快速恢复)在此阶段，Congwin以线性方式增长，发生超时，门限值减半,第3讲 传输层之一,66,TCP 拥塞避免策略:AIMD:additive increase（加法形式增加）；multiplicative decrease（倍数形

35、式减少）每个RTT将窗口尺寸加1当发生数据丢失时用2除窗口尺寸,AIMD,教科书：p244-245,第3讲 传输层之一,67,TCP 公平性,公平性目标:如果 N TCP 会话共享瓶颈链路,每个应该分得 1/N 链路传输能力,TCP connection 1,bottleneckroutercapacity R,TCP connection 2,第3讲 传输层之一,68,为什么说TCP是公平的?,两个竞争性的会话:当吞吐量增加时，加法的结果斜率为 1而成倍递减则会等比减少连接的吞吐量,R,R,同等的带宽共享,连接 1 的吞吐量,连接 2 的吞吐量,congestion avoidance:additive increase,loss:decrease window by factor of 2,拥塞避免:加法形式增加窗口尺寸,丢包:以2为除数减小窗口来进行,带宽的充分使用,第3讲 传输层之一,69,第4讲:小结,传输层服务原理:复用/分用可靠数据传输流量控制拥塞控制因特网传输层的实现和实例UDPTCP,下一步:离开网络的“边缘”(应用/传输层)进入网络的“核心”,